SCS Curriculum Reinvention Committee

From Soma-notes

This page contains notes and discussions related to the SCS Curriculum Reinvention Committee.

The content below has gratuitous markup so as to make it obvious how to add more stuff.

To edit this page, you first need to create an account - click the link in the top-right of the page. Then click on the edit tab just about the page headline. Or, you can edit individual sections.

Requests for more data

  • Why are students leaving SCS?
    • What are the grades in SCS-related courses for students who change majors out of SCS?
    • What majors do they switch to? After how many terms?
  • DFW and A/B rates for 2009/2010 versus past years in 1405, 1406, 1805?

Courses to be examined

Introductory Programming

  • COMP 1405 - Introduction to Object-Oriented Programming
  • COMP 1406 - Design and Implementation of Computer Applications

Theory

  • COMP 1805 - Discrete Structures
  • COMP 2805 - Introduction to Theory of Computation
  • COMP 2402 - Abstract Data Types and Algorithms
  • COMP 3804 - Design and Analysis of Algorithms I

Intermediate Programming

  • COMP 1402 - Introduction to Systems Programming
  • COMP 2404 - Programming in C++

Other Core-ish Courses

  • COMP 2003 - Computer Organization
  • COMP 2405 - Internet Application Programming
  • COMP 3000 - Operating Systems
  • COMP 3002 - Compiler Construction
  • COMP 3004 - Object-Oriented Software Engineering
  • COMP 3005 - Database Management Systems
  • COMP 3007 - Programming Paradigms
  • COMP 3008 - User Interface Architecture
  • COMP 3203 - Principles of Computer Networks
  • STAT 2507
  • STAT 2605

COMP 1405/1406 Redesign

Topic Brainstorming

Add topics here at the end of the section. Please don't remove anything!

  • WHAT IS COMPUTER SCIENCE
    • problem solving
    • algorithms
    • abstraction and problem decomposition
    • efficiency ??
  • PSEUDO-CODE ??
  • SEQUENCING INSTRUCTIONS
    • top down coding in sequence (e.g., draw a house)
  • VARIABLES
    • declaring vs. assigning
    • memory usage ??
    • constants
    • examples:
      • compute simple math formulas
      • interactive input (e.g., use mouse position)
      • motion (if doing graphics)
  • Numbers
    • integers
    • floats
  • CONDITIONALS
    • simple IF/ELSE
    • nested IF
    • booleans(AND/OR)
    • examples:
      • make choices based on runtime input
      • basic state machine
      • edge cases / error checking
  • ITERATION
    • repeating X times (REPEAT)
    • counting (FOR)
    • repeating until condition (WHILE)
    • nested loops
    • examples
      • sum/avg/max/min
      • counting matches
      • MonteCarlo approximation
      • loop until user input
      • searching (find first match)
  • ARRAYS (1D and 2D)
    • initializing and memory usage
    • simple 1D (sum.avg/max/min)
    • insert/remove
    • copy/growing array
  • Optimization
    • e.g., knapsack
    • greedy
  • Simulation
    • virus clearing
    • Roomba
  • Abstract data types
  • Sorting
  • Search
    • linear
    • binary
    • exhaustive
  • Divide and conquer
  • Dynamic programming
  • FORMATTING
    • string manipulation
    • display in columns (i.e., tabbing)
    • display dates/times
  • Data structures
    • lists
    • structures
    • tuples
    • binary trees
    • dictionaries
    • sets
    • stacks, queues
  • Complexity analysis
    • informal
  • OBJECTS
    • instance variables
    • initialization (constructors)
    • shared references
    • static vs. instance
  • FUNCTIONS and PROCEDURES
    • simple computations and return values
    • passing parameters
    • passing arrays as parameters
    • helper methods
  • RECURSION (likely 1406 material?)
    • inductive definitions of data and associated recursion patterns.
    • direct vs. indirect
    • tail recursion
    • examples:
      • math problems (factorial/sum/avg)
      • searching mazes
      • iterate a non recursive data structure (array)
      • iterate a recursive data structure (e.g., tree)
  • PERSISTENCE (likely 1406 material?)
    • writing files
    • reading files
    • parsing files
  • WINDOWING
    • display text output
    • get textfield input
    • buttons
    • design and layout
    • handling events
    • menus
    • dialog boxes
  • GRAPHICS
    • drawing with lines/shapes
    • grabbing/selecting/moving graphical objects
  • User interaction
  • PROPER CODING STYLE
    • encapsulation
    • polymorphism
    • private/public/protected data
  • INHERITANCE
    • class hierarchies
    • abstract vs. concrete classes ?
    • overriding/inheriting methods
    • type-casting (needed if JAVA used) ?
  • NETWORKING ?? (1406 ... as interesting examples)
    • read internet page
    • two applications talk over network
  • Event-driven programming
  • Model-View-Controller (more for 1406)
  • Database APIs
    • Allow use of key/value stores as used by standard websites
  • Testing and debugging
    • design vs. implementation errors
    • basic test cases, regression testing?
    • basic debugger usage
    • strategies for identifying and fixing programming problems
  • Software licenses
    • open source and commercial
    • restrictions on reuse
  • How to read code
  • editing and building software
    • basic IDE usage
  • commenting, code formatting guidelines
  • revision control
    • have students grab class code from this, pull updates
    • make commits/push to submit?
  • Understanding APIs
    • basic idea of contract, side effects
  • Concurrency/parallel code
    • maybe not standard locking but some clean parallel constructs?
  • Relative costs of operations
    • memory vs. I/O vs. computation
    • very basic benchmarking
    • main idea: know that you can't predict what is going to be fast in practice w/o tests
  • my first wiki entry ever! - djh

Should we copy the MIT 6.00 outline here?

Sub categories?

Yes, we can add sub categories here.

COMP1405 LIST OF TOPICS (UNORDERED) FOR WEEKLY OUTLINE

  • WHAT IS COMPUTER SCIENCE
    • problem solving
    • algorithms
    • abstraction and problem decomposition
    • divide and conquer
    • efficiency (just an intro to the ideas behind it)
  • PSEUDO-CODE
  • SEQUENCING INSTRUCTIONS
    • top down coding in sequence (e.g., draw a house)
  • VARIABLES
    • declaring vs. assigning
    • memory usage (how memory is affected) LATER
    • constants LATER
    • examples:
      • compute simple math formulas
      • interactive input (e.g., use mouse position)
      • motion (if doing graphics)
  • Numbers
    • integers
    • floats MINIMAL HERE --- MAKE SURE THIS TOPIC IS TAUGHT SOMEWHERE IN CURRICULUM
  • CONDITIONALS
    • simple IF/ELSE
    • nested IF
    • booleans(AND/OR)
    • examples:
      • make choices based on runtime input
      • basic state machine
      • edge cases / error checking
  • ITERATION
    • repeating X times (REPEAT)
    • counting (FOR)
    • repeating until condition (WHILE)
    • nested loops
    • examples
      • sum/avg/max/min
      • counting matches
      • MonteCarlo approximation
      • loop until user input
      • searching (find first match)
      • Make sure to have examples with non-trivial loop invariants (e.g., gcd, searching)
  • COMMENTING / CODE FORMATTING GUIDELINES
  • ARRAYS (1D and 2D)
    • initializing
    • simple 1D (sum.avg/max/min)
    • insert/remove
    • copying as needed for examples
  • OBJECTS
    • as mutable data structures only, no methods
    • instance variables
    • initialization (constructors)
    • shared references
  • FUNCTIONS and PROCEDURES
    • simple computations and return values
    • passing parameters
    • passing arrays as parameters
    • modular programming using functions and procedures
    • recursion; possible examples: math problems (factorial/sum/avg); searching mazes
  • USER INTERACTION
    • input and output interaction with environment (e.g. user)
  • RELATIVE COSTS OF OPERATIONS
    • memory vs. I/O vs. computation
    • very basic benchmarking
    • often, but not always, you can't predict what is going to be fast in practice w/o tests
  • SORTING
    • teach in context of indexing (e.g., search engines)?
    • illustration of: algorithms, complexity, recursion, divide-and-conquer
  • SEARCH
    • linear
    • binary
    • exhaustive
  • SIMULATION
    • possible examples: robots, Monte Carlo, virus clearing, Roomba
  • Course work should include some code reading

COMP1406 LIST OF TOPICS (UNORDERED) FOR WEEKLY OUTLINE

Top-level goals - Java - developing a complete OO applications

  • EDITING AND BUILDING SOFTWARE
    • JAVA language basics (make comparision with Processing)
    • explain IDE usage (Eclipse), program creation, etc..
  • OBJECTS
    • defining classes
    • writing methods within classes
    • having multiple objects interact with each other
  • PROPER CODING STYLE
    • encapsulation
    • polymorphism
    • private/public/protected data
    • exception handling (needed for JAVA)
  • INHERITANCE
    • class hierarchies
    • abstract vs. concrete classes
    • interfaces (JAVA specific...not "user" interfaces)
    • overriding/inheriting methods
    • type-casting (needed if JAVA used)
  • GRAPHICAL USER INTERFACES
    • display text output
    • get textfield input
    • buttons
    • design and layout
    • handling events
    • menus and dialog boxes
    • model view controller
    • GRAPHICS -- not here, but it should be somewhere?
      • grabbing/selecting/moving graphical objects
  • FILE I/O
    • writing files
    • reading/parsing files
  • RECURSION
    • programming and recursive data structures
  • FORMATTING output nicely
    • string manipulation
    • display in columns (i.e., tabbing)
    • display dates/times
  • NETWORKING
    • read internet page
    • two applications talk over network
  • ABSTRACT DATA TYPES / DATA STRUCTURES
    • lists (?? ArrayLists already used in 1405)
    • structures (?? already done in 1405)
    • tuples (?? Points already used in 1405)
    • binary trees
    • dictionaries
    • sets
    • stacks, queues
  • TESTING AND DEBUGGING
    • design vs. implementation errors
    • basic test cases, regression testing?
    • basic debugger usage
    • strategies for identifying and fixing programming problems
  • OPTIMIZATION
    • e.g., knapsack
    • greedy
  • DYNAMIC PROGRAMMING

EXTRA LIST OF TOPICS TO ADD IF TIME PERMITS (Mark's Opinion)

  • UNDERSTANDING APIs
    • basic idea of contract, side effects
  • DATABASE APIs ???
    • Allow use of key/value stores as used by standard websites
  • SOFTWARE LICENSES
    • open source and commercial
    • restrictions on reuse
  • REVISION CONTROL
    • have students grab class code from this, pull updates
    • make commits/push to submit?
  • CONCURRENCY/PARALLEL CODE
    • maybe not standard locking but some clean parallel constructs?

Sample weekly outline (Fall 2006)

1. Introduction Sept 7-8 

    - intro to CS
    - class stuff

2. Algorithms Sept 11-15 

    - what are they
    - intro to problem solving
    - statements
    - pseudocode

3. Variables Sept 18-22 

    - concept
    - identifiers
    - assignment
    - expressions, arithmetic

4. Conditionals Sept 25-29 

    - Decision statements
    - boolean operators
    - if / then / else
    - case / switch
    - going from problem description to conditional statement

5. Iteration Oct 2-6 

    - idea of looping
    - starting / stopping / stepping
    - loop bodies
    - top and bottom loops
    - for loops
    - while loops
    - going from problem to loop statements

6. Subprograms Oct 9-13 

    - idea of modularization
    - functions and procedures
    - parameter passing
    - variable scope
    - when to modularize (problem solving)

7. Computer architecture Oct 16-20 

    - basic von Neumann architecture
    - linear memory organization
    - possibly midterm post-mortem in this week

8. Data structures 1: Arrays Oct 23-27 

    - idea of data structures & collections
    - arrays & linear memory
    - array operations, initialization
    - relation to loops
    - 2D arrays
    - going from problem to array specification

9. Data structures 2: Structs Oct 30-Nov 3 

    - idea of user-defined structures
    - why and when to use
    - examples

10. Searching Nov 6-10 

    - a larger problem domain
    - linear and binary search
    - 'putting it all together' (arrays, loops, variables, etc)
    - introduction to algorithm analysis (just the idea that different

algorithms can take different time)

11. Sorting Nov 13-17 

    - same basic structure as searching week
    - bubble sort and selection sort

12. Recursion Nov 20-24 

    - introduction to the idea
    - base cases & recursive cases
    - composition steps (returning a value)

13. Review Nov 27-Dec 4 

    - lab exam postmortem
    - review for the final

Textbooks

Assignment problems

Please list your ideas for assignment problems below in your own subsection. Note that we are currently focusing on smaller problems that can be assembled into weekly assignments.

David's Processing Problems

Draw a face, draw a house, draw a robot. (basic straight-line code)

Logical drawing (draw simple forms based on mouse position)

Using for loops to augment drawing.

Grass:

Stars:

- change the size, color distribution of stars - draw stars only above the horizon - draw stars only inside a circle (telescope view)

- add freckles to the face, hair

Skyscraper: - drawing location based on loop variable

variants: some windows dark, some lit

draw entire city (collection of buildings)

base sky color and window distribution on mouse pointer (windows get dark as it gets later)

Simple image processing:

Convert colored image to greyscale

Convert image to black and white; variant: base proportion of blackness on mouse position

Convert image to red and white -- only keep red pixels (problem: how to define?)

Robot behaviour:

Move small robot image or drawing primitive based on obstacles, mouse pointer - e.g., flee from mouse - e.g., attracted to mouse - e.g., want to maintain certain distance from mouse

David's Paper problem solving examples

  • Suppose you have two jugs, one with a capacity of three liters and the other with a capacity of five liters. Write an algorithm that uses these two jugs, and no other measuring devices, to get exactly one liter of water in the five-gallon jug.
  • The Greeks of classical Athens assemble to choose a new leader, and they vote by placing voting stones into an urn: a black stone, to vote for Castor, or a white stone, to vote for Pollux. You are put in charge of the election results. Write a specific algorithm for determining which of the candidates (Castor or Pollux) is the winner.
  • You are the in charge of the Royal mint, which produces a single type coin, the grote. There are ten machines producing grotes. One machine is producing grotes weighing one gram less than they should (each coin should weigh 10 grams). You have a scale that can be used exactly once before it explodes (don't ask), but will give an accurate reading of the weight of whatever is on the scale. Using only this one weighing, identify the single faulty machine. (Note; no algorithm required, just solve the puzzle if you can).
  • The Royal Mint has run out of exploding scales, and now has balances instead. (A balance will tell you whether the items in the left pan or the items in the right pan are heavier, but not how much heavier.) You have nine grote-minting machines, and one of them is producing grotes that are too light. Write an algorithm for using the balance to determine which machine's grotes are too light. (Challenge: do it with only two balance operations.)
  • Four travellers are trying to cross an old, rickety bridge, so decrepit that only two can cross at once. They reached the bridge at night, and have only one flashlight among them; there are enough holes in the bridge that it can only be crossed safely by a group carrying a light. Now, the travellers have reached the bridge at different levels of exhaustion: one will take 1 minute to walk across; one will take 2 minutes; one will take 5 minutes to limp across; and one will take 10 minutes to crawl across. A group moves at the speed of its slowest member. Give a general algorithm for getting everyone safely to the far side of the bridge. Using your algorithm, how long does it take the travellers to cross? (There are no tricks, like throwing the flashlight back to the other side.) (Challenge: get the group across in under 20 minutes.) (Challenge #2: get the group across in under 18 minutes.)
  • An old story has a grateful king granting a wish to a favored advisor, and the advisor describing the following process. A chess board is to be brought out, and one grain of rice placed on the first square, two grains on the second, four on the third, and so on, doubling for each square. There are 64 squares on the chessboard. Write pseudocode for an algorithm to determine how many pounds of rice the unlucky king has to give to the advisor, assuming 1000 grains per pound.
  • Suppose you are trying to pay off credit card debt. You have an initial balance, and the credit card charges 1.5% additional interest each month. Write pseudocode for an algorithm that gets a monthly payment amount from the user and then reports (a) how long it will take to pay off the debt; (b) how much of the payment is for interest (total paid minus initial balance). Make sure not to allow infinite loops! (How would a bank avoid an infinite loop on a credit card?)
  • You have a spaceship that runs on gold, consuming 1 ton of gold for each parsec traveled. It can carry a maximum of 1000 tons, but can also eject gold into space and pick it up later. You have 3000 tons of gold and want to get as much as possible to your destination 1000 parsecs away (just at the limits of what you could reach, arriving empty). Describe a general algorithm for getting to your destination with as much gold as you can. (Challenge: reach the destination with more than 425 tons.)
  • Consider the following exchange:
    • ``My dog is precisely one-third Dalmatian.
    • ``How can that be?
    • ``Well, his father was one-third Dalmatian, and his mother is one-third Dalmatian, and so he is too.

What is wrong with the reasoning in the last statement? (Note: this is a question about recursion, NOT genetics! Pretend that the amount of Dalmatian in the offspring is the average of the amounts in the parents.)

  • The Greek hero Achilles has the ability to stride half the distance to his goal in just a single step. He also has the ability to take a normal step, which will take him at most 1 meter. Write pseudocode for a recursive function that takes a float argument (the initial distance to the goal) and returns the smallest number of steps Achilles has to take to reach his goal. Notice that Achilles's best strategy will be to take giant steps (halving the distance) until the distance remaining is one meter or less, which he can finish with one normal step.

Anil M's example problems

Anil S's example problems

  • Build an adventure game (2D graphics or text). This can turn into a huge assignment; however it can break down into a number of small tasks. Adventure games are a great way to teach about objects, persistence, conditionals, for example.
  • draw fractals: recursion, numerical methods (limits of precision), basic graphics, complexity (fractals can take a while to render)
  • find patterns in an image (squares, lines) - specific pixel patterns are easy, but scale and rotation invariant searches are much more challenging.
  • spirograph
  • file visualization - learn file I/O, basic data visualization, string processing, bit of recursion
  • core wars? You just need arrays and a simple bytecode interpreter (bunch of conditionals)

Doug's example problems

Michiel's example problems

  • Monte-Carlo estimation of pi: Throw N points randomly in the unit-square, and count how many of them are in the unit-circle. Do experiments with larger and larger values of N, and see how the result improves.
  • Monte-Carlo estimation of integrals. Take some integrals that students learned in calculus (and that are not completely trivial). Choose random real numbers and count how many of them are underneath the function. Do experiments as for pi.
  • Monty Hall problem. First let students guess what is the best strategy. Do a large number of experiments (put the prize behind a random door; choose a random door first, then follow the strategy) and count how many times you win the car. Based on this, students may be convinced that their initial strategy is not correct. In this case, revise the strategy and repeat the experiments.
  • In all these problems, students may use different random number generators and see if they give the same results.

Mark's paper problem solving examples

  • Part A - Mary Melody has an apartment building high up in the sky. On her balcony is a ledge with 10 flower pots on it. The ledge is so narrow that it only holds exactly 10 pots. Mary has named each of her 10 flowers by placing a piece of masking tape on the bottom of the pot with the name on it. One day Mary decided to have a maid come and clean. The maid was so thorough and she was a kind of "neat freak". The maid wants to sort the flowers by name from left to right so that the leftmost flower has the name which comes first alphabetically. Assume that the maid can pick up only 1 pot in each hand at a time and that the pots must either be in the maid's hand or on the ledge (that is, she cannot put them down anywhere else). Note that the maid may pick one pot up in her hand and slide another pot along the ledge with her free hand. Explain (i.e. give an algorithm) how the maid can sort the pots properly.
    • Part B - Assume now there are exactly two ledges and that the maid can make use of the second ledge to place the pots on. Can you describe a better way of sorting the pots ? Perhaps there is a quicker way or a way that involves the use of only one hand.
  • Assume that you want a robot to follow along the walls of a building and that the walls have always 90 degree turns. Explain how to get the robot to follow the walls. Draw a picture of your robot and indicate any kinds of sensors that you would need. Make sure to explain how you use the sensors.

Mark's programming problems

  • Write a program to compute how many balls can be packed into a box. This can be done 2D or 3D. In 2D, the user can draw a rectangle and a circle and then use their dimensions to compute the number of circles that fit into the rectangle and display them packed in there. It can be done in 3D as well without too much difficulty. (This will help students understand the differences between using floats and ints because only WHOLE balls are to be fit into the rectangle, not partial balls).
  • Part A - Write a program that determines whether or not cell phone access is continuously available along a planned path between various cities. In this program, the user will click a set of arbitrary locations on the screen that represent city centers. Assume that a cell phone tower is placed at each city center and is represented as a circle with some radius. Assuming that the user then drives from one city center to the others in sequence, the user then needs to compute whether or not there is cell phone access along the whole path. The solution is to make sure that the circles intersect for each consecutive pair of cities.
    • Part B - Assume that internet access is available throughout the whole trip. If it costs $0.20 per minute to use the cellphone and the person traveled an average (non-stop) speed of 50km/h ... for the whole trip, staying connected to the internet the whole time ... what will be the maximum cell phone cost from this trip ? (They would calculate the distances between adjacent cities to compute the total distance and will need to determine how many minutes of travel time was made on the trip ... assuming constant speed of 50km/h to keep things simple).
  • Simulate Cars parking in ParkingLots over time. Define Car and ParkingLot data structures, where cars maintain the time that they entered the parking lot (if they take a ticket stub) and perhaps whether or not they have a parking pass. As cars enter the lot, their entry time is stored in the Car data structure, based on the current time. When they leave, the cost is computed based on their entry time and current time at some fixed cost (e.g., $1.50 per hour). The ParkingLot maintains the total money made so far as well as its capacity and the number of cars parked there. (The students could draw the parking lot and grab cars with the mouse to place them in the lot (perhaps showing their entry time as well). The cars can then be clicked on to leave the lot (no need to animate it). We could then have two parking lots of different capacities and rates and then have the cars go into each one. This is a nice way to get them used to using data structures)

Recommendations Summary

  • "Objects first" is not working, too many students DFW in first year. Also, we've already moved away from objects first in practice. Some leading CS departments, e.g. Waterloo, UofT, & MIT, do not teach objects first (objects are just one topic among many). We're proposing to do the same.
  • Only cover objects as data structures in first year: no inheritance until last few weeks of 1406.
  • Inheritance will be covered in 2404 (Programming in C++) - title should change to "Object-Oriented Programming in C++". 2401 covers C and UNIX in the Fall, 2404 covers C++ in the Winter.
  • Emphasize problem solving in a general-purpose programming language.
  • Teach only basic programming language structures: loops, conditionals, functions, procedures, exceptions.
  • No required special applications in 1406.
  • 1405 is an introduction to problem solving through programming, 1406 is a second course on the same topic.
  • Advanced students would start with 1406 and skip 1405; 1406 shouldn't require knowledge of the specific language syntax used in 1405.
  • 3007 becomes Functional and Concurrent programming. (e.g., cover MapReduce)
  • 2402 will give students extra experience with Java beyond 1405 and 1406.
  • Challenge: where do students get more experience with object-oriented Java? (How much do they need?) Question: could 3004 provide this, or do we need a new course, maybe just for the software engineering stream?

Required Programming Courses

  • 1405 and 1406
  • 2401, 2402, & 2404
  • 3004 and 3007

Old Course Descriptions

COMP 1405 [0.5 credit] Introduction to Object-Oriented Programming A first course in problem solving and computer programming designed for B.C.S. students. Introduction to object-oriented programming; syntactic constructs, data abstraction, classification and inheritance, typing and polymorphism, testing and debugging. Precludes additional credit for COMP 1005 and SYSC 1100. Prerequisite: Restricted to students registered in the B.C.S. program, combined Honours in Computer Science and Mathematics, Honours Computer Mathematics, and Honours Computer Statistics. Lectures three hours a week, tutorial one and a half hours a week.

COMP 1406 [0.5 credit] Design and Implementation of Computer Applications A continuation of COMP 1405 focusing on the design and implementation of complete applications. Topics covered include persistence, graphical user interface design and implementation, event-driven programming, recursion, drawing and manipulating 2D graphics and networking. Precludes additional credit for COMP 1006 and SYSC 1101. Prerequisite: COMP 1405. Restricted to students registered in the B.C.S. program, combined Honours in Computer Science and Mathematics, Honours Computer Mathematics, and Honours Computer Statistics. Lectures three hours a week, tutorial one and a half hours a week.

New Course Descriptions

COMP 1405 [0.5 credit] Introduction to Programming I

A first course in programming emphasizing problem solving and computational thinking. Topics include an introduction to computer science, pseudocode, variables, conditionals, iteration, arrays, objects, functions, sorting, searching, and simulation.


COMP 1406 [0.5 credit] Introduction to Programming II

A second course in programming emphasizing problem solving and computational thinking. Topics include object-oriented programming, abstract data types, linked data structures, testing and debugging, recursion, encapsulation and information-hiding, specification, program efficiency, state machines, and exception handling.


Links for May 10, 2010

From Doug

Toronto [1] CSC108 and CSC 148 (150 is an accelerated combo)

Topics:

Program structure: elementary data types,statements, control flow, functions, classes, objects, methods, fields. Lists; searching, sorting and complexity.

Abstract data types and data structures for implementing them. Linked data structures. Encapsulation and information-hiding. Object-oriented programming. Specifications. Analyzing the efficiency of programs. Recursion.

Waterloo [2] CS 135 and 136

Topics:

Syntax and semantics of a functional programming language. Tracing via substitution. Design, testing, and documentation. Linear and nonlinear data structures. Recursive data definitions. Abstraction and encapsulation. Generative and structural recursion. Historical context.

It introduces the design and analysis of algorithms, the management of information, and the programming mechanisms and methodologies required in implementations. Topics discussed include iterative and recursive sorting algorithms; lists, stacks, queues, trees, and their application; abstract data types and their implementations.

Princeton [3]

Potential topics from Princeton: hardware and software systems; programming in Java; algorithms and data structures; fundamental principles of computation; and scientific computing, including simulation, optimization, and data analysis.


Alberta [4] CMPUT 174 and 175

Potential topics from Alberta for 1405 and 1406:

  1. computation, states, events, transitions
  2. state machines, simple pattern matching
  3. programming basics (variables, input, output, while, if, etc.)
  4. search
  5. lists, arrays, and hashes
  6. regular expressions and pattern matching
  7. functions, subroutines, and testing
  8. recursion
  9. references and data structures
  10. expression and binary trees
  11. abstract data types
  12. simulation
  13. sorting
  14. abstract data types
  15. objects
  16. graph algorithms
  17. exceptions
  18. little languages
  19. closures

Email to Faculty

The "curriculum reinvention" committee (Anil x 2, Michiel, Mark, Doug, Dave) have been discussing revising our curriculum with the goal of improving engagement and retention of our students, i.e. doing a better job of teaching them. Lately, we've been focusing on the first year programming courses, and would like to get your input on a proposal for a substantial change to 1405 and 1406 (leaving 1005 and 1006 aside for now). Below is a summary of the changes followed by a calendar-like description of the courses.

We're interested in any views you might have. Nothing is set in stone at this point.

The key change we are proposing is to change their focus from learning Java to learning how to solve problems using programs. Key programming concepts are to be taught in as language-independent a manner as possible, e.g., through the use of pseudo-code. Object-oriented programming concepts are present in the courses but are not presented first. 1405 will cover objects as simple data structures, but methods, inheritance etc will be postponed until 1406. Instead, a wide range of basic programming skills will be taught.

The new courses will be structured in some ways as a unit; however, the topics are partitioned so that students with substantial programming experience in any language will have a decent chance of going directly to 1406 (via a placement test).

For the initial course delivery, we are tentatively planning on emphasizing weekly assignments structured around multiple small problems rather than fewer, larger assignments. Also, while Java will be used for both courses, 1405 will use Processing, a Java "subset" designed for image creation. We believe Processing will facilitate more engaging assignments.

These changes will have limited impact on the rest of the curriculum. 2402 (Abstract Data Types) will continue to be taught in Java. 2404, our C++ course, will focus more on problem solving using object-oriented programming and design with C++.


Old Course Descriptions (prereqs etc omitted)

COMP 1405 [0.5 credit] Introduction to Object-Oriented Programming

A first course in problem solving and computer programming designed for B.C.S. students. Introduction to object-oriented programming; syntactic constructs, data abstraction, classification and inheritance, typing and polymorphism, testing and debugging.

COMP 1406 [0.5 credit] Design and Implementation of Computer Applications

A continuation of COMP 1405 focusing on the design and implementation of complete applications. Topics covered include persistence, graphical user interface design and implementation, event-driven programming, recursion, drawing and manipulating 2D graphics and networking.


New Course Descriptions

COMP 1405 [0.5 credit] Introduction to Programming I

A first course in programming emphasizing problem solving and computational thinking. Topics include an introduction to computer science, pseudocode, variables, conditionals, iteration, arrays, objects, functions, sorting, searching, and simulation.

COMP 1406 [0.5 credit] Introduction to Programming II

A second course in programming emphasizing problem solving and computational thinking. Topics include object-oriented programming, abstract data types, linked data structures, testing and debugging, recursion, encapsulation and information-hiding, specification, program efficiency, state machines, and exception handling.

1805 redesign

Jit's comments

Hi Everyone,

Currently, the textbook used is Kenneth H. Rosen, Discrete Mathematics and its Applications, (sixth edition), McGraw-Hill, 2007. This textbook and all other textbooks I have seen so far in Discrete Math all suck. The reason I used this one is because the online materials available to students is quite helpful. I am thinking of converting my notes into a document to either compliment the text or even replace it.

The topics that are currently scheduled to be covered in COMP 1805 are (chapters/sections are in brackets):


1. Logic and Proof, Sets, and Functions: Propositional calculus, predicates and quantifiers. Methods of proof. (1.1 - 1.7) 2. Sets and Functions (2.1-2.4) 3. Algorithms and Their Complexity (Selected material from 3.1 - 3.8) 4. Induction and Recursion. (4.1 - 4.5) 5. Counting: Basic definitions, pigeonhole principle, permutations and combinations. (5.1 - 5.5) 6. Discrete Probability (6.1 - 6.4) 7. Relations: Basic definitions, representation of relations, closures, equivalence relations, partial orderings. (8.1 - 8.6)

8. Elementary Graph Theory: Basic definitions, planar graphs, connectivity, and computer representations of graphs. (9.1 - 9.8)

9. Trees: Paths, cycles, directed trees, search trees, spanning trees. (10.1 - 10.5) 10. Boolean Algebra: Boolean functions and their representation. (11.1 - 11.3)

Over the last 5 or 6 times that I have taught this course, I have never been able to cover everything. I usually decide on the fly which topics to omit or which ones to spend more time on based on feedback that I get from the students via their test marks, assignments and tutorials (I used to teach the tutorials as well). Some years, I did not cover boolean algebra, others I did not teach discrete probability.

After the double cohort, there was a noticeable drop in the level of the students. Prior to the double cohort, the 2 times that I taught this course, in fact, I co-taught with Frank Fiala, I was able to cover everything. So we need to address the reality of our current situation which is that students coming in are weaker and/or do not have as much of a mathematical background/maturity as they used to have. This is why I believe that we should actually introduce a second year course. This would give us the opportunity to spend more time on certain basic topics in first year and more advanced topics in second year.

I believe that one of the main difficulties that the students are having with the material covered in this course is that there are too many new concepts that are taught in a very short period of time. In the past, students in highschool were supposed to take a math course (I forget the number) that actually covered induction, logic and proofs. Many students used to tell me that the first half of the course was a nice review for them. However, I believe we dropped this requirement in our admission criterion, as such, this is the first time that students are seeing many of these concepts.

As I mentioned above, our proposal is to take a few of the topics and move them into a second year discrete math course. Pat Morin, Anil, Michiela and I had looked into finding a nice division of the topics that would give two coherent courses with basic topics being covered in the first year course and more advanced topics in a second year course. I have attached the description below of what we had come up with.

Suggestions for 1805:

I think that the topics that should be kept in 1805 are: Logic/Proofs, Sets and Functions, Intro to Algorithms, Induction/Recursion, Relations/Graphs.

I think that the approach on how the material is taught should be changed. I have been thinking a lot about various ways of introducing/presenting this material. I believe that the best way to present this material is to use many visual examples. I really liked David Mould's idea of using processing as a way of introducing both Logic and Induction/Recursion. Furthermore, I think that Graphs should play a more central role since that is the topic that I found students were able to grasp most easily. In fact, I was thinking that everything (sets, logic, proofs etc) can be taught from a graph point of view. Students are able to relate to finding paths in graphs etc. As such, presenting proof techniques, logic, set theoretic concepts etc from a graph theoretic point of view may really help them grasp the material more easily. For example, when I show them depth first search as a graph exploration method, most students understood the recursion right away. Now, I must admit that I am uncertain if this is because by the time I teach graphs, we are nearing the end of the term and they have seen all the concepts already or if graphs are really a structure they are able to grasp and relate to easily. In either case, this is something I think is worth considering.


COURSE DESCRIPTIONS (Including the new second year course):

COMP1805 Discrete Structures I

Introduction to discrete mathematics and discrete structures. Topics include: propositional logic, predicate calculus, set theory, complexity of algorithms, mathematical reasoning and proof techniques, recurrences, induction, functions, relations and graph theory. Material is illustrated through examples from computing.

Rationale: 1805 is notoriously difficult for first-year students because in the current course, too many topics are covered for a one term introductory first-year discrete math course. Therefore, to address this situation, we propose to move some of the more advanced material into a second course (COMP2804 Discrete Structures II). Specifically, we will move Boolean algebra, counting, discrete probability, some of the more advanced functions and advanced sequences and sums, and methods on how to solve recurrence relations.

COMP2804 Discrete Structures II

Introduction to discrete mathematics and discrete structures. Topics include: counting, Boolean algebra, sequences and sums, discrete probability (including random variables, expectation, linearity of expectation, dependence, concentration results, distributions), recurrence relations. Material is illustrated through examples from computing.

Prerequisite: COMP1805

Rationale: This is the course that contains the more advanced material from the original version of COMP1805. As noted above, we cover Boolean algebra, counting, discrete probability, some of the more advanced functions and advanced sequences and sums, and methods on how to solve recurrence relations. These are topics that are currently covered in COMP1805. However, students are having too much difficulty grasping all of the different topics in a one term course at the first year level.


2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, graphs, sorting and searching .

Precludes additional credit for COMP 2002 and SYSC 2002.

Prerequisite: COMP 1406, COMP1805. Restricted to students registered in the B.C.S. program, combined Honours in Computer Science and Mathematics, Honours Computer Mathematics, and Honours Statistics. Lectures three hours a week.

Rationale: Updated the calender description and added COMP1805 as a prerequisite. It seems that this was an oversite and that this course assumes that students are familiar with topics covered in 1805. Specifically, complexity of algorithms and graph theory are assumed when students take this course.

COMP 3804 Design and Analysis of Algorithms I

An introduction to the design and analysis of algorithms. Topics include: recurrence relations, sorting and searching, divide-and-conquer, dynamic programming, greedy algorithms, graph algorithms, NP-completeness.

Prerequisites: COMP 2002 or COMP 2402, and COMP 2805 or COMP2804 or both of MATH 2007 and MATH 2108, or equivalents.

Rationale: Added COMP2804 in the list of courses that can be considered as a prereq. Revised the course description to add Graph Algorithms as one of the topics that are covered. Graph Algorithms have always been covered in this course but did not appear in the course description.


COMP 4804 Design and Analysis of Algorithms II

A second course on the design and analysis of algorithms. Topics include: randomized algorithms, amortized analysis, approximation algorithms for NP-Complete problems, advanced graph algorithms. Also offered at the graduate level, with additional or different requirements, as COMP 5703, for which additional credit is precluded.

Prerequisite: COMP 3804 and one of (COMP 2804, Stat 2605) or permission of the School.


Rationale: Updated the course description to reflect what will be taught in the course and also updated the prereqs.


Other CS approaches to Math/Theory

Dalhousie

(Howe) 

 Program specs
- http://ug.cal.dal.ca/CSCI.htm

Summary
- First year: calculus.
- Second year: data structures and algorithms, 2 discrete
   math, linear algebra, prob and stats.
- Third year: algorithms.
- Fourth year: no specific courses.

Comparison
- Same number of CS theory courses: 2 Discrete Math for 1805/2805;
  2402 equivalent; third-year algorithms.
- one fewer math courses: one each of calculus, algebra, prob/stats.
  Note: Dal is accredited, so they must be using DSII as a math course
  (it's actually taught by the math dept).
			
Courses required in BCS Honours
- First year
  - Differential and Integral Calculus I, MATH 1000.03
- Second year
  - Computer Science III, CSCI 2110.03 -- data structures and algorithms
  - Discrete Structures I, CSCI 2112.03 
  - Discrete Structures II, CSCI 2113.03 
  - Matrix Theory and Linear Algebra I, MATH 2030.03
  - Introduction to Probability and Statistics I, STAT 2060.03
- Third year
  - Design and Analysis of Algorithms I, CSCI 3110.03
  - Operating Systems, CSCI 3120.03
- Fourth year
  - no specific courses, but some strict area requirements, e.g. one
    of four theory courses


Theory/math course calendar descriptions

- Computer Science III, CSCI 2110.03.  This course provides a
  comprehensive introduction to data structures and algorithms,
  including their design, analysis, and implementation. In discussing
  design and analysis there is a strong emphasis on abstraction. In
  discussing implementation, general approaches that are applicable in
  a wide range of procedural programming language are emphasized, in
  addition to a focus on the details of Java implementations. Topics
  include an introduction to asymptotic analysis and a review of basic
  data structures (stacks, queues, lists, vectors), trees, priority
  queues, dictionaries, hashing, search trees, sorting (MergeSort,
  QuickSort, RadixSort) and sets, and graphs (traversals, spanning
  trees, shortest paths). 

- Discrete Structures I, CSCI 2112.03.  This class together with MATH
  2113.03 offers a survey of the following areas: set theory,
  mathematical induction, number theory, relations, functions,
  algebraic structures and introductory graph theory. The topics to be
  discussed are fundamental to most areas of Mathematics and have wide
  applicability to Computer Science.

- Discrete Structures II, CSCI 2113.03.  This class covers some basic
  concepts in discrete mathematics which are of particular relevance
  to students of computer science, engineering, and mathematics. The
  topics to be covered will ninclude solution of recurrence relations,
  generating functions, number theory, chinese remainder theorem,
  trees and graphs, finite state machines, abstract algorithms,
  boolean algebra.

- Differential and Integral Calculus I, MATH 1000.03.  This class
  offers a self-contained introduction to differential and integral
  calculus.  The topics include functions, limits, differentiation of
  polynomial, trigonemetric, exponential and logarithmic functions,
  product, quotient and chain rules, applications of differentiation,
  antiderivatives and definite integrals,integration by substitution.

- Matrix Theory and Linear Algebra I, MATH 2030.03. This class is a
  self-contained introduction to Matrix Theory and Linear
  Algebra. Topics include: subspaces, linear transformations,
  determinants, eigenvalues and eigenvectors, systems of linear
  equations. Students should note that this is a second-year class
  and, although it has no formal first-year prerequisites, certain
  mathematical maturity is expected.

- Introduction to Probability and Statistics I, STAT 2060.03.
  Rigorous introduction to probability and statistical theory. Topics
  covered include elementary probability, random variables,
  distributions, estimation and hypothesis testing. Estimation and
  testing are introduced using maximum likelihood and the generalized
  likelihood ratio.

- Design and Analysis of Algorithms I, CSCI 3110.03.  This class
  covers techniques for the design and analysis of efficient
  algorithms and data structures. Topics include asymptotic analysis,
  divide and conquer algorithms, greedy algorithms, dynamic
  programming, data structure design, optimization algorithms, and
  amortized analysis. The techniques are applied to problems such as
  sorting, searching, identifying graph structure, and manipulating
  sets.

U. Waterloo

(Anil M.)


UBC

(Anil S.)


U. Toronto

(Howe) 

Summary.  
- First year: calculus; math reasoning.  Note: second of the two
  required programming courses looks partly like 2402.
- Second year: induction and automata; linear algebra; data structures
  (2404/3804 combo?); prob/stats.
- Third year:  [numerical methods?]; complexity and computability;
  algorithms. 

Comparison
- No second calculus or algebra course required. Only three required
  math total.
- They have one extra CS "theory" course.  Both have a data structures
  and an algorithms course.  Instead of 1805 and 2805, they have math
  reasoning, induction and automota, and complexity+computability.

Program specs
- http://www.artsandscience.utoronto.ca/ofr/calendar/prg_csc.htm

Courses required by all programs (the major and all the "specialist"
programs).  
- http://www.artsandscience.utoronto.ca/ofr/calendar/crs_csc.htm
- First year
    - Mathematical Expression and Reasoning for Computer Science
      CSC165H1 (has advanced version)
    - Calculus MAT137Y1
- First or second year
  - Introduction to the Theory of Computation CSC236H1 (has advanced
    version) 
  - Linear Algebra I MAT223H1
- Second year
  - Data Structures and Analysis CSC263H1 (has advanced version)
  - Choice of
    - Probability with Computer Applications TA247H1
    - Statistical Theory STA255H1
    - Probability and Statistics I STA257H1
- Third and fourth year
  - none

Courses required by all "specialist" programs
- [Numerical Methods CSC336H1 ?]
- Computational Complexity and Computability CSC363H1
- Algorithm Design & Analysis CSC373H1


Theory/math course calendar descriptions

 - Calculus. A conceptual approach for students with a serious interest
  in mathematics. Geometric and physical intuition are emphasized but
  some attention is also given to the theoretical foundations of
  calculus. Material covers first a review of trigonometric functions
  followed by discussion of trigonometric identities. The basic
  concepts of calculus: limits and continuity, the mean value and
  inverse function theorems, the integral, the fundamental theorem,
  elementary transcendental functions, Taylor’s theorem, sequence and
  series, uniform convergence and power series.  - There is a more
  theoretical version.

- Mathematical Expression and Reasoning for Computer Science CSC165H1.
  Introduction to abstraction and rigour. Informal introduction to
  logical notation and reasoning. Understanding, using and developing
  precise expressions of mathematical ideas, including definitions and
  theorems. Structuring proofs to improve presentation and
  comprehension. General problem-solving techniques. Unified
  approaches to programming and theoretical problems. Representation
  of floating point numbers and introduction to numerical computation.

- Introduction to the Theory of Computation.  The application of logic
  and proof techniques to Computer Science. Mathematical induction;
  correctness proofs for iterative and recursive algorithms;
  recurrence equations and their solutions (including the “Master
  Theorem”); introduction to automata and formal languages.

- Linear Algebra I.  Matrix arithmetic and linear systems. Rn subspaces,
  linear independence, bases, dimension; column spaces, null spaces,
  rank and dimension formula. Orthogonality orthonormal sets,
  Gram-Schmidt orthogonalization process; least square
  approximation. Linear transformations Rn—>Rm. The determinant,
  classical adjoint, Cramer’s Rule. Eigenvalues, eigenvectors,
  eigenspaces, diagonalization. Function spaces and application to a
  system of linear differential equations.

- Data Structures and Analysis CSC263H1.  Algorithm analysis:
  worst-case, average-case, and amortized complexity. Standard
  abstract data types, such as graphs, dictionaries, priority queues,
  and disjoint sets. A variety of data structures for implementing
  these abstract data types, such as balanced search trees, hashing,
  heaps, and disjoint forests. Design, implementation, and comparison
  of data structures. Introduction to lower bounds.

- Probability with Computer Applications TA247H1.  Introduction to the
  theory of probability, with emphasis on applications in computer
  science. The topics covered include random variables, discrete and
  continuous probability distributions, expectation and variance,
  independence, conditional probability, normal, exponential,
  binomial, and Poisson distributions, the central limit theorem,
  sampling distributions, estimation and testing, applications to the
  analysis of algorithms, and simulating systems such as queues.

- Statistical Theory STA255H1.  This courses deals with the
  mathematical aspects of some of the topics discussed in
  STA250H1. Topics include discrete and continuous probability
  distributions, conditional probability, expectation, sampling
  distributions, estimation and testing, the linear model.

- Probability and Statistics I STA257H1. Course descriptions can be
  all to generic in their brevity. Suffice to know, then, that this
  course, and its sequel-in crime, STA261H1, is mathematically quite
  challenging, the target audience includes those proceeding directly
  to a specialist degree in statistics, as well as anyone with serious
  and special interest in some other of the identifiably
  statistical-physical sciences. Topics, albeit very rigorously
  covered, are, nevertheless, very standard introductory fare:
  abstract probability and expectation, discrete and continuous random
  variables and vectors, with the special mathematics of distribution
  and density functions, all realized in the special examples of
  ordinary statistical practice: the binomial, poisson and geometric
  group, and the gaussian (normal), gamma, chi-squared complex.

- Computational Complexity and Computability CSC363H1.  Introduction
  to the theory of computability: Turing machines, Church’s thesis,
  computable and noncomputable functions, recursive and recursively
  enumerable sets, reducibility. Introduction to complexity theory:
  models of computation, P, NP, polynomial time reducibility,
  NP-completeness, further topics in complexity theory.

- Algorithm Design & Analysis CSC373H1.  Standard algorithm design
  techniques: divide-and-conquer, greedy strategies, dynamic
  programming, linear programming, randomization, network flows,
  approximation algorithms, and others (if time permits). Students
  will be expected to show good design principles and adequate skills
  at reasoning about the correctness and complexity of algorithms.

MIT

(Smid)

Another School

(Dave)

Retrieved from "https://homeostasis.scs.carleton.ca/wiki/index.php?title=SCS_Curriculum_Reinvention_Committee&oldid=2189"