SCS Curriculum Reinvention Committee

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

• Sedgewick and Wayne, Introduction to Programming in Java

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 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)

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

(Michiel)

BCS Waterloo

http://www.cs.uwaterloo.ca/current/

http://www.cs.uwaterloo.ca/current/programs/require/2010-2011/bcs.pdf

=============================================================

The following 7 math-courses are required (note: each of these courses has an alternative advanced version which students may take):

MATH 135 LEC,TST,TUT 0.50 Course ID: 006878 Algebra for Honours Mathematics A study of the basic algebraic systems of mathematics: the integers, the integers modulo n, the rational numbers, the real numbers, the complex numbers and polynomials.

MATH 136 LAB,LEC,TST,TUT 0.50 Course ID: 006879Linear Algebra 1 for Honours Mathematics Systems of linear equations, matrix algebra, elementary matrices, computational issues. Real and complex n-space, vector spaces and subspaces, basis and dimensi on, rank of a matrix, linear transformations and matrix representations. Inner p roducts, angles and orthogonality, applications.TH 128 LEC,TUT 0.50 Course ID: 006872

MATH 127 LEC,TUT 0.50 Course ID: 006871Calculus 1 for the SciencesFunctions of a real variable: powers, rational functions, trigonometric, exponential and logarithmic functions, their properties and inverses. Intuitive discuss ion of limits and continuity. Definition and interpretation of the derivative, d erivatives of elementary functions, derivative rules and applications. Riemann s ums and other approximations to the definite integral. Fundamental Theorems and antiderivatives; change of variable. Applications to area, rates, average value.

MATH 128 LEC,TUT 0.50 Course ID: 006872 Calculus 2 for the Sciences Transforming and evaluating integrals; application to volumes and arc length; improper integrals. Separable and linear first order differential equations and applications. Introduction to sequences. Convergence of series; Taylor polynomials, Taylor's Remainder Theorem, Taylor series and applications. Parametric/vector representation of curves; particle motion and arc length. Polar coordinates in the plane. Functions of two variables, partial derivatives, the linear approximation/tangent plane.

MATH 239 LEC,TST,TUT 0.50 Course ID: 006915 Introduction to Combinatorics Introduction to graph theory: colourings, matchings, connectivity, planarity. Introduction to combinatorial analysis: generating series, recurrence relations, binary strings, plane trees.

STAT 230 LEC,TST,TUT 0.50 Course ID: 008864 Probability The laws of probability, discrete and continuous random variables, expectation, central limit theorem.

STAT 231 LEC,TST,TUT 0.50 Course ID: 008865 Statistics Empirical problem solving, measurement systems, causal relationships, statistical models, estimation, confidence intervals, tests of significance.

============================================================

The following four CS-theory-courses are required:

CS 136 LAB,LEC,TST,TUT 0.50 Course ID: 012041 Elementary Algorithm Design and Data Abstraction This course builds on the techniques and patterns learned in CS 135 while making the transition to use of an imperative language. 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.

CS 240 LAB,LEC,TST 0.50 Course ID: 004377 Data Structures and Data Management Introduction to widely used and effective methods of data organization, focusing on data structures, their algorithms, and the performance of these algorithms. Specific topics include priority queues, sorting, dictionaries, data structures for text processing.

CS 245 LEC,TST,TUT 0.50 Course ID: 011405 Logic and Computation Propositional and predicate logic. Soundness and completeness and their implications. Unprovability of formulae in certain systems. Undecidability of problems in computation, including the halting problem. Reasoning about programs. Correctness proofs for both recursive and iterative program constructions.

CS 341 LAB,LEC 0.50 Course ID: 004392 Algorithms The study of efficient algorithms and effective algorithm design techniques. Program design with emphasis on pragmatic and mathematical aspects of program efficiency. Topics include divide and conquer algorithms, recurrences, greedy algorithms, dynamic programming, graph search and backtrack, problems without algorithms, NP-completeness and its implications.

==========================================================

For the CS breadth requirement, one of the following theory courses is required:

CS 360 LEC 0.50 Course ID: 004398 Introduction to the Theory of Computing Models of computers including finite automata and Turing machines. Basics of for mal languages with applications to the syntax of programming languages. Alternat e characterizations of language classes. Proving unrecognizability. Unsolvable problems and their relevance to the semantics of programming.

CS 365 LAB,LEC 0.50 Course ID: 011347 Models of Computation Finite automata and regular expressions. Pushdown automata and context-free gram mars. Turing machines and undecidability. Time and space complexity. Diagonaliza tion and hierarchies. CS 365 covers the material in CS 360 at an accelerated pace plus additional topics in computational complexity.

CS 370 LAB,LEC 0.50 Course ID: 004400Numerical ComputationPrinciples and practices of basic numerical computation as a key aspect of scientific computation. Visualization of results. Approximation by splines, fast Fourier transforms, solution of linear and nonlinear equations, differential equations, floating point number systems, error, stability. Presented in the context of specific applications to image processing, analysis of data, scientific modeling.

CS 371 LAB,LEC 0.50 Course ID: 011363 Introduction to Computational Mathematics A rigorous introduction to the field of computational mathematics. The focus is on the interplay between continuous models and their solution via discrete processes. Topics include: pitfalls in computation, solution of linear systems, interpolation, discrete Fourier transforms and numerical integration. Applications are used as motivation.

CS 462 LEC 0.50 Course ID: 004424 Formal Languages and Parsing Languages and their representations. Grammars --Chomsky hierarchy. Regular sets and sequential machines. Context-free grammars -- normal forms, basic properties. Pushdown automata and transducers. Operations on languages. Undecidable problems in language theory. Applications to the design of programming languages and compiler construction.

Algorithm Design and Analysis Algorithmic approaches and methods of assessment that reflect a broad spectrum of criteria, including randomized algorithms, amortized analysis, lower bounds, approximation algorithms, and on-line algorithms. Particular examples will be chosen from different areas of active research and application.

CS 467 LEC 0.50 Course ID: 011497 Introduction to Quantum Information Processing Basics of computational complexity; basics of quantum information; quantum phenomena; quantum circuits and universality; relationship between quantum and classical complexity classes; simple quantum algorithms; quantum Fourier transform; Shor factoring algorithm; Grover search algorithm; physical realization of quantum computation; error-correction and fault-tolerance; quantum key distribution.

CS 475 LAB,LEC 0.50 Course ID: 011444 Computational Linear Algebra Basic concepts and implementation of numerical linear algebra techniques and their use in solving application problems. Special methods for solving linear systems having special features. Direct methods: symmetric, positive definite, band, general sparse structures, ordering methods. Iterative methods: Jacobi, Gauss-Seidel, SOR, conjugate gradient. Computing and using orthogonal factorizations of matrices. QR and SVD methods for solving least squares problems. Eigenvalue and singular value decompositions. Computation and uses of these decompositions in practice.

CS 487 LAB,LEC 0.50 Course ID: 004436 Introduction to Symbolic Computation An introduction to the use of computers for symbolic mathematical computation, involving traditional mathematical computations such as solving linear equations (exactly), analytic differentiation and integration of functions, and analytic solution of differential equations.

UBC

(Anil S.)

UBC CS Program Options and Requirements

Summary of UBC's Computer Science Degree Requirements

Summary of observations

• They have 2402 at second year
• No automata course
• No discrete math, but lots of general math requirements, particularly for honours
• basic stats for all, probability for honours

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)

Alberta

(Dave)

Course list here: http://www.cs.ualberta.ca/undergraduate-students/course-directory

Honors students take two-course problem-solving sequence in first year. The honors program is incredibly open: its requirements are

• COMP 174/175
• 2 first-year English courses
• 6 courses COMP 300+
• 4 courses COMP 400+
• 12 Science courses
• 4 Arts courses
• 10 other courses (any faculty)

"Specialization" students (non-honours, typically combined with another field such as business or music) take 2 CS and 2 math in first year.

First-year CS course descriptions follow:

• Introduction to Computing Science

Overview

This course introduces you to the basic concepts of object-oriented programming. You learn how to write simple but useful programs using Java, and attain a solid grasp of programming principles in general. Assignments will give you the opportunity to apply the theory in interesting and fun ways.

Objectives

Know the mechanical requirements of getting a Java program to compile and run Know how to write different kinds of Java programs: applets and applications Be able to write code which performs small tasks Be able to build simpler operations into larger, integrated solutions Know how to debug programs (find and fix errors) Have experience organizing large sets of data Know how to design programs so that they are easy to maintain and update later

• Programming with Data Structures

Overview

This course is the second in the series of CMPUT 114-115 series for introduction to Computing Science, with an emphasis on dynamic data structures such as sets, lists, stacks, queues, dictionaries and so on, and their associated algorithms.

Many problems demand a dynamic data structure because you don't know in advance how much data is needed until the program is run. It takes more programming to implement a reliable dynamic data structure than any other kind of data structures

Objectives

Understand fundamental concepts such as data structures, stacks, queues, lists, trees, dictionaries, linked lists pre-conditions, post-conditions, exceptions, recursion inheritance, algorithms, complexity searching, sorting and hashing Be able to use these concepts to construct robust programs that solve complex problems

• Introduction to the Foundations of Computation I

Overview

This two course sequence is a small introduction to the foundations of a major part of Computing Science: expressing problems precisely, solving them algorithmically by showing how to construct a solution, and then implementing that solution by writing a program.

Our emphasis will be more on computation than on programming. That is, we are going to be more interested in the underlying process behind the solution and less interested in a particular programming language or programming style for implementing the solutions. In fact, our goal is to develop your intuitions for a variety of complementary styles of computation.

Our approach in this course is problem-driven. We will take a problem and attempt to solve it. In the process of developing an algorithmic solution we will introduce key computing concepts. Our intention is that every abstract concept should be grounded in concrete examples.

• Introduction to the Foundations of Computation II

Overview

This two course sequence is a small introduction to the foundations of a major part of Computing Science: expressing problems precisely, solving them algorithmically by showing how to construct a solution, and then implementing that solution by writing a program.

Our emphasis will be more on computation than on programming. That is, we are going to be more interested in the underlying process behind the solution and less interested in a particular programming language or programming style for implementing the solutions. In fact, our goal is to develop your intuitions for a variety of complementary styles of computation.

Our approach in this course is problem-driven. We will take a problem and attempt to solve it. In the process of developing an algorithmic solution we will introduce key computing concepts. Our intention is that every abstract concept should be grounded in concrete examples.

New course descriptions and rationale

COMP 1405

Old Course Description

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.

New Course Description

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.

Rationale

• COMP 1405 has high DFW rate and students who pass do not necessarily know how to solve problems using a programming language. Existing course material is oriented towards the specifics of Java.
• This new course description allow flexibility in first course to use languages other than Java.
  • Java has lots of syntax to teach, takes away time from teaching general programming and problem solving.
  • Many other universities (MIT, UofT, Waterloo) have moved towards problem solving-focused courses using syntactically simpler languages than Java (Python, Scheme).
  • It forces to use OO when OO isn't useful for very small programming problems. Students will see the object view of data; inheritance & methods are covered in 1406.
• Course should teach basics of imperative programming that are common across programming languages.
• First run will use Processing, a Java subset designed for graphics and interaction.
• Students with significant programming experience in any programming language should be able to skip this course.
• One potential structure will use weekly assignments with multiple small problems that will require students to solve problems systematically.

COMP 1406

Old Course Description

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 Description

COMP 1406 [0.5 credit] Introduction to Programming II

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

Rationale

• Before 1406 had no clear rationale other than giving students additional programming experience.
• The new 1406 will instead have a mandate of teaching OO principles and Java. Students should be up to speed with basic Java programming by the end of the course.
• Students with an existing programming background will be able to skip 1405 and directly take this course.

COMP 1805

New Course Description

• COMP 1805 (Mathematical Reasoning for Computer Science): Practice in mathematical arguments sufficient to prepare students for 2402. Cover logic, basic complexity, proof techniques including induction. Other material should be used to illustrate these key concepts.
• Calc 1
• Algebra 1

Topics for somewhere

• counting
• basic probability
• recurrence relations
• number representations (floating point, numerical stability)
• graphs
• proof techniques (1805, 2805, & 3804)
• partial orders
• equivalence relations
• randomized algorithms
• modular arithmetic

• COMP 2003 (Architecture)
• COMP 2401 (Systems Programming/C & UNIX)
• COMP 2402 (Data Structures in Java): Be able to analyze simple algorithms over simple data structures. n^2 versus nlogn, for example. Should be able to analyze sorting algorithms, but need not learning sorting.
• COMP 2404 (Intro to Software Engineering with C++)
• COMP 2805 (Finite Automata)
• Prob. & Stats

• COMP 3000 (Operating Systems)
• COMP 3004 (Software Engineering)
• COMP 3005 (Databases)
• COMP 3007 (Programming Paradigms)
• COMP 3804 (Design and Analysis of Algorithms)

Survey of theory requirements in other Canadian Honours programs

            THEORY COURSES AT OTHER CANADIAN UNIVERSITIES
            =============================================

Definition.  A "theory" course is any course, taught by any
department, that is mainly: data structures + algorithms, discrete
math, or theory of computation.

Note.  Quebec universities not included (weird system), ditto small,
non-research-intensive places.

There's a summary, followed by a complete listing of courses for the
chosen institutes.


SUMMARY
-------

The following table shows for each number of theory courses, how many
programs require that number.  The third column is the number of
programs that additionally require a course in logic.
 
Courses   Programs   +Logic
0         1          -
3         3          -
4         13         5
5         3          1
 
The next table shows the universities associated with each number of
courses.  A * indicates an additional course in logic.

0   Alberta
3   McMaster, UBC, Victoria
4   Dal, Calgary, Guelph, Manitoba, Memorial, Regina, Windsor, UNB
    Queen's*, Victoria*, Waterloo*, Sask*, Ottawa*
5   Western*, SFU, U of T

Averages: 3.7 theory courses; 4.0 theory+logic courses

 
Caveats/Notes
- Some programs required a choice of one of several courses.  This was
counted as a theory course if all the choices were theory by our
definition, e.g. Sask.  Programs where the choice was not counted:
Waterloo, SFU, Calgary, Dal.  
- We were looking at the wrong programs for U of T and Waterloo.
Waterloo: we were looking at the BMath Computer Science instead of the
BCS.  Toronto: the appropriate program to compare with is the BSc
Honours Computer Science, Specialist Program - Flexible Option.
- At Sask, one of the counted theory courses is a first-year course
that is probably not theory but has substantial keyword overlap with
2402. 
 
  
 
ALBERTA
-------

Notes 
- only formal requirements: programming 1 and 2, 6 3rd-year+ courses,
12 4th-year+.


No required theory courses
- third year choices will be limited without at least the second-year
algorithms course 204 (Algorithms I) which is a somewhat a combo of
2402 and 3804.



CALGARY
-------

Notes
- seems course number starts at 2XX?  There are first year courses,
  but they're weird, e.g. first year CS is Unix 1 + 2.
- there's a choice of one of six math-ish courses in fourth-year
  which includes complexity and algorithms II, and also
  e.g. distributed algorithms and computer algebra

Computer Science 331 Information Structures I 
Algorithms: searching, sorting, graph navigation. Data structures:
arrays, lists, stacks, queues, graphs, trees, hash tables; time and
space efficiency of associated algorithms.

MATH 271 - Discrete Mathematics
Proof techniques. Sets and relations. Induction. Counting and
probability. Graphs and trees.

Computer Science 313	Introduction to Computability
An introduction to abstract models of sequential computation,
including finite automata, regular expressions, context-free grammars,
and Turing machines. Formal languages, including regular,
context-free, and recursive languages,

Computer Science 413	Design and Analysis of Algorithms I
Techniques for the analysis of algorithms, including counting,
summation, recurrences, and asymptotic relations; techniques for the
design of efficient algorithms, including greedy methods, divide and
conquer , and dynamic programming; examples of their application; an
introduction to tractable and intractable problems.



GUELPH
------

CIS*1910 Discrete Structures in Computing I
An introduction to discrete structures and formal methodologies used
in computer science, including Boolean, prepositional and predicate
logic, finite set theory, functions, relations, and proof techniques.

CIS*2520 Data Structures F (3-2) [0.50]
Basic data structures are studied including: stacks, queues, lists,
trees, hashing, search trees, and graphs. Topics include their
representation, uses, and algorithms for their traversal and
manipulation. The emphasis is on using these structures and assessing
the relative effectiveness of alternative implementations.

IS*2910 Discrete Structures in Computing II F (3-2) [0.50]
This course introduces graph theory, combinatorics and other discrete
structures used in computer science, including graph representations,
traversal and simple graph algorithms, trees, counting strategies,
summations, and an introduction to finite probability, recursion, and
finite state machine models.

CIS*3490 The Analysis and Design of Computer Algorithms W (3-2) [0.50]
The design and analysis of efficient computer algorithms are
studied. Topics which will be studied include: standard methodologies,
asymptotic behaviour, optimality, lower bounds, implementation
considerations, graph algorithms, matrix computations (e.g. Strassen's
method), NP-completeness.



MANITOBA
--------

COMP 2080 - Analysis of Algorithms
(Formerly 074.208) Methods of analyzing the time and space
requirements of algorithms. Average case and worst case
analysis. Models of computation.

COMP 2130 - Discrete Mathematics for Computer Science
An introduction to the set theory, logic, integers, combinatorics and
functions for today's computer scientists.

COMP 2140 - Data Structures and Algorithms
Introduction to the representation and manipulation of data
structures. Topics will include lists, stacks, queues, trees, and
graphs.

COMP 3170 - Analysis of Algorithms and Data Structures
Fundamental algorithms for sorting, searching, storage management,
graphs, databases and computational geometry. Correctness and analysis
of those algorithms using specific data structures. An introduction to
lower bounds and intractability.



MCMASTER
--------

COMP SCI 1FC3  MATHEMATICS FOR COMPUTING
Introduction to logic and proof techniques; functions, relations, and
sets; cou trees and graphs; concepts are illustrated using
computational tools.

COMP SCI 2C03  DATA STRUCTURES AND ALGORITHMS
Searching, sorting, dynamic programming, greedy algorithms, abstract
structures, balanced trees, hashing, graphs, design principles, comple
organization of libraries.

COMP SCI 2MJ3      THEORY OF COMPUTATION
Finite state machines, regular languages, regular expressions,
applications of regular languages, grammars, context-free languages,
models of computation, introduction to complexity theory.



MEMORIAL
--------

2320 Discrete Mathematics 
2711 Introduction to Algorithms and Data Structures
2742 Logic for Computer Science
3719 Theory of Computation and Algorithms



UOTTAWA
-------

MAT1348	Discrete Mathematics for Computing
Introduction to discrete structures as a foundation to
computing. Propositional logic. Fundamental structures: functions,
relations, sets. The basics of counting: counting arguments, the
pigeonhole principle, permutations and combinations. Introduction to
proofs: direct, by contradiction, by cases, induction. Rudiments of
the analysis of algorithms and order analysis. Topics in graph theory:
isomorphism, planarity, circuits, trees, directed graphs. Recursive
definition of functions and methods for solving recurrence
relations. Whenever possible applications from computing and
information technology will be included.

CSI2101	Discrete Structures	(3,1.5,0) 3 cr.
Discrete structures as they apply to computer science, algorithm
analysis and design. Predicate logic. Review of proof techniques;
application of induction to computing problems. Graph theory
applications in information technology. Program correctness,
preconditions, postconditions and invariants. Analysis of recursive
programs using recurrence relations. Properties of integers and basic
cryptographical applications.

CSI2110	Data Structures and Algorithms	(3,1.5,1.5) 3 cr.
The concept of abstract data types. Simple methods of complexity
analysis. Trees. The search problem: balanced trees, binary-trees,
hashing. Sorting. Graphs and simple graph algorithms: traversal,
minimum spanning tree. Strings and pattern matching.

CSI3104	Introduction to Formal Languages	(3,0,0) 3 cr.
Regular languages, finite automata, transition graphs Kleene's
theorem. Finite automata with output. Context-free languages,
derivation trees, normal form grammars, pumping lemma, pushdown
automata, determinism. Decidability. Recursively enumerable languages,
Turing machines, the halting problem.

CSI3105	Design and Analysis of Algorithms I	(3,0,0) 3 cr.
Analysis of algorithms: worst-case analysis, complexity analysis,
asymptotic notations and basic complexity classes. Algorithm design
techniques: brute force, divide and conquer, dynamic programming,
greedy, backtracking. Computational complexity of problems: lower
bound arguments, the classes P, NP, NP-complete, dealing with
NP-complete problems.



QUEEN'S
-------

CISC 121* Introduction to Computing Science I
Introduction to design and analysis of algorithms. Control structures:
recursion, backtracking, exits. Data structures: structures,
sequences, linked lists and references, binary search
trees. Elementary searching and sorting. Introduction to assertions
and loop invariants. Introduction to order-of-magnitude
complexity. Introduction to numerical computation. Documentation,
testing and debugging.

CISC 203* Discrete Mathematics for Computing Science
Introduction to mathematical discourse and proof methods. Sets,
functions, sequences, and relations. Properties of the
integers. Introduction to graph theory. Introduction to combinatorics.

CISC 204* Logic for Computing Science
Elements of mathematical logic with computing applications. Formal
proof systems for propositional and predicate logic. Interpretations,
validity, and satisfiability. Introduction to soundness, completeness
and decidability.

CISC-235* Data Structures
Design and implementation of advanced data structures and related
algorithms, including correctness and complexity analysis. Efficient
implementation of lists, sets, dictionaries, priority queues, trees,
graphs, and networks using arrays, hash tables, heaps, and
hierarchical linked structures. String and graph problems, such as
string matching and shortest path. External storage and input-output
complexity.

CISC-365* Algorithms I
Principles of design, analysis and implementation of efficient
algorithms. Case studies from a variety of areas illustrate divide and
conquer methods, the greedy approach, branch and bound algorithms and
dynamic programming.



REGINA
------

CS 210 Data Structures and Abstractions 
This course introduces data abstraction, data structures, the basics
of algorithmic analysis, and the fundamental computing
algorithms. Topics will include: unsorted lists, stacks, queues,
recursion, asymptotic notation, computational complexity, and hashing,
sorting, and searching algorithms.

CS 310 Discrete Computational Structures 
Finite and discrete algebraic structures relating to computers; sets,
functions, relations. Machine-oriented logic. Combinatorial problems
and algorithms. Finite automata and formal language theory.

CS 340 Advanced Data Structures and Algorithm Design 
Design, implementation, and manipulation of complex abstract data
types, including trees and graphs. Fundamental algorithms: sorting,
searching, depth- and breadth-first traversals, string manipulation,
pattern matching, and graph algorithms. Algorithmic strategies: brute-
force, greedy, divide-and-conquer, backtracking, branch-and-bound,
dynamic programming, randomized, and parallel. Introduction to
algorithm analysis and complexity theory.

CS 412 Algorithm Analysis A formal algorithmic language. 
Measures of complexity for time and space. Worst-case, average-case,
and best-case analysis. Lower and upper bounds of algorithms
(techniques include comparison trees, adversary arguments, and
reduction). P and NP classes. NP- hardness and NP-
completeness. Introduction to parallel computational models and
algorithms.



SASK
----

CMPT 115: Principles of Computer Science
Introduces more of the basic concepts of computer science and
object-oriented software development with an emphasis on fundamental
data structures (lists, stacks, queues, trees) and associated
algorithms. This course includes recursion, abstract data types and
selected topics exploring some of the breadth of computer science.

CMPT 260: Mathematical Logic and Computing
An introduction to elementary applied propositional and predicate
logic. Fundamental proof techniques with an emphasis on induction. The
theory of sets, relations and functions. Course concepts are related
to Computer Science areas, with an emphasis on relational databases.

CMPT 280: Intermediate Data Structures and Algorithms
Formal abstract data types; tree representations and searching:
ordered trees, balanced trees, simple spacial trees; graph
representations and searching: path algorithms, dfs, bfs,
backtracking; direct and Btree files; and sorting algorithms.

CMPT 360: Machines and Algorithms
The first part develops and analyzes some standard techniques for
algorithm development which are widely applicable to computer science
problems. The second part analyzes several formal models of computers
so that their capabilities are known.

Choice of one of three: automata, complexity, advanced algs.



SFU
---

MACM 101-3 Discrete Mathematics I
Introduction to counting, induction, automata theory, formal
reasoning, modular arithmetic. 

MACM 201-3 Discrete Mathematics II
A continuation of MACM 101. Topics covered include graph theory,
trees, inclusion-exclusion, generating functions, recurrence
relations, and optimization and matching.

CMPT 225 Data Structures and Programming
Introduction to a variety of practical and important data structures
and methods for implementation and for experimental and analytical
evaluation. Topics include: stacks, queues and lists; search trees;
hash tables and algorithms; efficient sorting; object-oriented
programming; time and space efficiency analysis; and experimental
evaluation. 

CMPT 307 Data Structures and Algorithms A 
nalysis and design of data structures for lists, sets, trees,
dictionaries, and priority queues. A selection of topics chosen from
sorting, memory management, graphs and graph algorithms.

CMPT 405  Design and Analysis of Computing Algorithms
Models of computation, methods of algorithm design; complexity of
algorithms; algorithms on graphs, NP-completeness, approximation
algorithms, selected topics

Choice: one out of "theory" courses.



TORONTO
-------

Notes 
- the closest program to our core honours degree seems to be the BSc
in Computer Science, Specialist Program - Flexible Option.  Their
advising material says those who want to do an honours degree but
don't have any specialty in mind should take this option.

CSC165H1 Mathematical Expression and Reasoning for Computer Science
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.

CSC236H1 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.

CSC263H1 Data Structures and Analysis
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.

CSC363H1 Computational Complexity and Computability
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. 

CSC373H1 Algorithm Design & Analysis
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. 

UBC
---

Notes
- tons of math!

CPSC 121 Models of Computation 
Physical and mathematical structures of computation. Boolean algebra
and combinations logic circuits; proof techniques; functions and
sequential circuits; sets and relations; finite state machines;
sequential instruction execution.

CPSC 221 Basic Algorithms and Data Structures 
Design and analysis of basic algorithms and data structures; algorithm
analysis methods, searching and sorting algorithms, basic data
structures, graphs and concurrency.

CPSC 320 Intermediate Algorithm Design and Analysis 
Systematic study of basic concepts and techniques in the design and
analysis of algorithms, illustrated from various problem areas. Topics
include: models of computation; choice of data structures;
graph-theoretic, algebraic, and text processing algorithms.



VICTORIA
--------

MATH 122 Logic and Foundations
Logic and quantifiers, basic set theory, mathematical induction and
recursive definitions, divide and conquer recurrence relations,
properties of integers, counting, functions and relations, countable
and uncountable sets, asymptotic notation.

CSC 225 Algorithms and Data Structures: I
An introduction to algorithm design and analysis. Random access
machine model. Time and space complexity, average and worst case
analysis, upper and lower bounds. Application of correctness proof
techniques. Algorithms: internal searching, merging, sorting,
selection, hashing; graphs: traversals, topological sort, transitive
closure, strongly connected components, shortest path, minimum
spanning tree. The existence of intractable problems, heuristics. Data
structures: B-trees, heaps and graphs.

CSC 320
Foundations of Computer Science
A survey of formal models and results that form the theoretical
foundations of computer science; typical topics include finite
automata, Turing machines, undecidable problems, context free
languages and computational complexity.



WATERLOO
--------

Notes
- lots of math (calculus, algebra, stats)
- used the Bachelor of Computer Science, not the B Math in Computer
Science. 

CS 136 Elementary Algorithm Design and Data Abstraction
This course builds on the techniques and patterns learned in CS 135
while making the transition to use of an imperative language. 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.

MATH 239 Introduction to Combinatorics
Introduction to graph theory: colourings, matchings, connectivity,
planarity. Introduction to combinatorial analysis: generating series,
recurrence relations, binary strings, plane trees.

CS 341 Algorithms
The study of efficient algorithms and effective algorithm design
techniques. Program design with emphasis on pragmatic and mathematical
aspects of program efficiency. Topics include divide and conquer
algorithms, recurrences, greedy algorithms, dynamic programming, graph
search and backtrack, problems without algorithms, NP-completeness and
its implications.

CS 240 Data Structures and Data Management
Introduction to widely used and effective methods of data
organization, focusing on data structures, their algorithms, and the
performance of these algorithms. Specific topics include priority
queues, sorting, dictionaries, data structures for text processing.

CS 245 Logic and Computation
Propositional and predicate logic. Soundness and completeness and
their implications. Unprovability of formulae in certain
systems. Undecidability of problems in computation, including the
halting problem. Reasoning about programs. Correctness proofs for both
recursive and iterative program constructions.

Choice of one of 9 "mathematical foundations" courses.



WESTERN
-------

Computer Science 2209A/B Applied Logic for Computer Science
Propositional and predicate logic; representing static and dynamic
properties of real-world systems; logic as a tool for representation,
reasoning and calculation; logic and programming.

Computer Science 2210A/B Data Structures and Algorithms
Lists, stacks, queues, priority queues, trees, graphs, and their
associated algorithms; file structures; sorting, searching, and
hashing techniques; time and space complexity.

Computer Science 3331A/B Foundations of Computer Science I
Languages as sets of strings over an alphabet; operations on
languages; finite automata, regular expressions; language hierarchy;
Turing machines; models of computation.

Computer Science 3340A/B Analysis of Algorithms I
Upper and lower time and space bounds; levels of intractability; graph
algorithms; greedy algorithms; dynamic algorithms; exhaustive search
techniques; parallel algorithms.

Mathematics 2155A/B Discrete Structures I
This course provides an introduction to logical reasoning and
proofs. Topics include sets, counting (permutations and combinations),
mathematical induction, relations and functions, partial order
relations, equivalence relations, groups and applications to
error-correcting codes.

Mathematics 2156A/B Discrete Structures II
This course continues the development of logical reasoning and proofs
begun in Mathematics 2155A/B. Topics include elementary number theory
(gcd, lcm, Euclidean algorithm, congruences, Chinese remainder
theorem) and graph theory (connectedness, complete, regular and
bipartite graphs; trees and spanning trees, Eulerian and Hamiltonian
graphs, planar graphs; vertex, face and edge colouring; chromatic
polynomials).





WINDSOR
-------

60-231.	Theoretical Foundations of Computer Science
An introduction to Mathematical Logic, Set Theory, and Graph
Theory. Topics include propositional logic, first order logic, proof
techniques, mathematical induction, sets, operations on sets,
relations, operations on relations, functions, countable an
uncountable sets, graph-theoretic concepts, such as graph
connectivity, graph isomorphism, trees, Euler graphs.

60-254.	Data Structures and Algorithms
An introduction to the programming and time-complexity analysis of
internal (main store) and external data structures. Topics include
linear lists, stacks, queues, linked structures, trees, binary trees;
sorting techniques, including heap sort, quick sort, merge sort, shell
sort; searching techniques including binary search, binary search
trees, red-black trees, hashing. Algorithm design paradigms like
divide-and-conquer, dynamic programming, greedy, external sorting,
B-trees.

60-454.	Design and Analysis of Computer Algorithms
The intent of this course is to introduce the fundamental techniques
in the design and analysis of computer algorithms. Topics include:
asymptotic bounds, advanced data structures, searching, sorting, order
statistics, oracle arguments, divide-and-conquer, greedy algorithms,
dynamic programming, graph algorithms, NP completeness, and
approximation algorithms.

60-354.	Theory of Computation
Finite Automata, regular expressions and languages; properties of
regular languages; context-free grammars and languages; pushdown
automata; properties of context-free languages. Introduction to Turing
machines; recursive functions; undecidability.



NEW BRUNSWICK
-------------

Notes
- Has "basic" and "specialization" options for BScCS Honours.  Using
"basic". 

CS 1303 Discrete Structures I 
Introduces topics in discrete mathematics important in Computer
Science, including propositional logic, predicate logic, proofs, sigma
notation, mathematical induction, elementary set theory and asymptotic
analysis.

CS 2303 Discrete Structures II
Continues CS 1303. Topics covered include: advanced set theory,
functions, relations, elementary permutations and combinations, graph
theory, and finite state machines.

CS 3323 Data Structures
Covers mathematical and experimental techniques for algorithm analysis
and their application to the major techniques for representing and
manipulating data structures in main memory. Considers worst-case,
average-case and amortized analyses. Structures include queues, binary
search trees, balanced search trees, hash tables, binary heaps, graphs
and mergeable priority queues. Analyzed sorting algorithms include
radix sort, quicksort, mergesort and heapsort. Implementation aspects
are addressed during unsupervised lab work.

CS 3913 Algorithmics
Continues the study of algorithms begun in CS3323. Covers advanced
techniques for analyzing recursive algorithms, examines major
algorithm-design approaches including greedy, divide and conquer,
dynamic programming, and graph-based approaches. Considers randomized
algorithms and introduces complexity theory, including
NP-completeness. One or more advanced topics will be chosen from the
following areas: algorithmic problems arising in artificial
intelligence, state spaces and search strategies, parallel and
distributed algorithms.

S 4913 Theory of Computation
Models of sequential and parallel computation, automata theory, formal
languages, the Chomsky hierarchy, decidability and computability,
sequential and parallel complexity theory.



YORK
----

Notes
- CS can be done as a BA or BSc.  Info here is from BSc.

SC/CSE 1019 Discrete Mathematics for Computer Science
Introduction to abstraction. Use and development of precise
formulations of mathematical ideas. Informal introduction to logic;
introduction to naïve set theory; induction; relations and functions;
big O-notation; recursive definitions, recurrence relations and their
solutions; graphs and trees.

SC/CSE 2001 Introduction to the Theory of Computation
Introduction to the theory of computing, including automata theory,
formal languages and Turing machines; theoretical models and their
applications in various fields of computer science. The emphasis is on
practical applications of the theory and concepts rather than formal
rigour.

SC/CSE 2011 Fundamentals of Data Structures
A study of fundamental data structures and their use in the efficient
implementation of algorithms. Topics include abstract data types,
lists, stacks, queues, trees and graphs.

SC/CSE 3101 Design and Analysis of Algorithms
Review of fundamental data structures. Analysis of algorithms: time
and space complexity. Algorithm design paradigms: divide-and-conquer,
exploring graphs, greedy methods, local search, dynamic programming,
probabilistic algorithms, computational geometry. NP-complete
problems.

SC/MATH 1090 Introduction to Logic for Computer Science
The syntax and semantics of propositional and predicate
logic. Applications to program specification and
verification. Optional topics include set theory and induction using
the formal logical language of the first part of the course.


DALHOUSIE
---------

Notes
- Couldn't copy and paste course descriptions.  Course details at
http://ug.cal.dal.ca/CSCI.htm#2.
- The math requirements have a choice between Calculus II and Discrete
Structures II.

CSCI 2110.03: Computer Science III [2402-ish]

CSCI 2112.03: Discrete Structures I

CSCI 2113.03: Discrete Structures II

CSCI 3110.03: Design and Analysis of Algorithms I

Choice of
  CSCI 4112.03: Theory of Computation
  CSCI 4113.03: Analysis of Algorithms II
  CSCI 4115.03: Topics in Graph Theory
  CSCI 4116.03: Cryptography