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 M's example problems
Anil S's example problems
- Build an adventure game (2D graphics or text). This can turn into a huge assignment; however it can break down into a number of small tasks. Adventure games are a great way to teach about objects, persistence, conditionals, for example.
- draw fractals: recursion, numerical methods (limits of precision), basic graphics, complexity (fractals can take a while to render)
- find patterns in an image (squares, lines) - specific pixel patterns are easy, but scale and rotation invariant searches are much more challenging.
- spirograph
- file visualization - learn file I/O, basic data visualization, string processing, bit of recursion
- core wars? You just need arrays and a simple bytecode interpreter (bunch of conditionals)
Doug's example problems
Michiel's example problems
- Monte-Carlo estimation of pi: Throw N points randomly in the unit-square, and count how many of them are in the unit-circle. Do experiments with larger and larger values of N, and see how the result improves.
- Monte-Carlo estimation of integrals. Take some integrals that students learned in calculus (and that are not completely trivial). Choose random real numbers and count how many of them are underneath the function. Do experiments as for pi.
- Monty Hall problem. First let students guess what is the best strategy. Do a large number of experiments (put the prize behind a random door; choose a random door first, then follow the strategy) and count how many times you win the car. Based on this, students may be convinced that their initial strategy is not correct. In this case, revise the strategy and repeat the experiments.
- In all these problems, students may use different random number generators and see if they give the same results.
Mark's paper problem solving examples
- Part A - Mary Melody has an apartment building high up in the sky. On her balcony is a ledge with 10 flower pots on it. The ledge is so narrow that it only holds exactly 10 pots. Mary has named each of her 10 flowers by placing a piece of masking tape on the bottom of the pot with the name on it. One day Mary decided to have a maid come and clean. The maid was so thorough and she was a kind of "neat freak". The maid wants to sort the flowers by name from left to right so that the leftmost flower has the name which comes first alphabetically. Assume that the maid can pick up only 1 pot in each hand at a time and that the pots must either be in the maid's hand or on the ledge (that is, she cannot put them down anywhere else). Note that the maid may pick one pot up in her hand and slide another pot along the ledge with her free hand. Explain (i.e. give an algorithm) how the maid can sort the pots properly.
- Part B - Assume now there are exactly two ledges and that the maid can make use of the second ledge to place the pots on. Can you describe a better way of sorting the pots ? Perhaps there is a quicker way or a way that involves the use of only one hand.
- Assume that you want a robot to follow along the walls of a building and that the walls have always 90 degree turns. Explain how to get the robot to follow the walls. Draw a picture of your robot and indicate any kinds of sensors that you would need. Make sure to explain how you use the sensors.
Mark's programming problems
- Write a program to compute how many balls can be packed into a box. This can be done 2D or 3D. In 2D, the user can draw a rectangle and a circle and then use their dimensions to compute the number of circles that fit into the rectangle and display them packed in there. It can be done in 3D as well without too much difficulty. (This will help students understand the differences between using floats and ints because only WHOLE balls are to be fit into the rectangle, not partial balls).
- Part A - Write a program that determines whether or not cell phone access is continuously available along a planned path between various cities. In this program, the user will click a set of arbitrary locations on the screen that represent city centers. Assume that a cell phone tower is placed at each city center and is represented as a circle with some radius. Assuming that the user then drives from one city center to the others in sequence, the user then needs to compute whether or not there is cell phone access along the whole path. The solution is to make sure that the circles intersect for each consecutive pair of cities.
- Part B - Assume that internet access is available throughout the whole trip. If it costs $0.20 per minute to use the cellphone and the person traveled an average (non-stop) speed of 50km/h ... for the whole trip, staying connected to the internet the whole time ... what will be the maximum cell phone cost from this trip ? (They would calculate the distances between adjacent cities to compute the total distance and will need to determine how many minutes of travel time was made on the trip ... assuming constant speed of 50km/h to keep things simple).
- Simulate Cars parking in ParkingLots over time. Define Car and ParkingLot data structures, where cars maintain the time that they entered the parking lot (if they take a ticket stub) and perhaps whether or not they have a parking pass. As cars enter the lot, their entry time is stored in the Car data structure, based on the current time. When they leave, the cost is computed based on their entry time and current time at some fixed cost (e.g., $1.50 per hour). The ParkingLot maintains the total money made so far as well as its capacity and the number of cars parked there. (The students could draw the parking lot and grab cars with the mouse to place them in the lot (perhaps showing their entry time as well). The cars can then be clicked on to leave the lot (no need to animate it). We could then have two parking lots of different capacities and rates and then have the cars go into each one. This is a nice way to get them used to using data structures)
Recommendations Summary
- "Objects first" is not working, too many students DFW in first year. Also, we've already moved away from objects first in practice. Some leading CS departments, e.g. Waterloo, UofT, & MIT, do not teach objects first (objects are just one topic among many). We're proposing to do the same.
- Only cover objects as data structures in first year: no inheritance until last few weeks of 1406.
- Inheritance will be covered in 2404 (Programming in C++) - title should change to "Object-Oriented Programming in C++". 2401 covers C and UNIX in the Fall, 2404 covers C++ in the Winter.
- Emphasize problem solving in a general-purpose programming language.
- Teach only basic programming language structures: loops, conditionals, functions, procedures, exceptions.
- No required special applications in 1406.
- 1405 is an introduction to problem solving through programming, 1406 is a second course on the same topic.
- Advanced students would start with 1406 and skip 1405; 1406 shouldn't require knowledge of the specific language syntax used in 1405.
- 3007 becomes Functional and Concurrent programming. (e.g., cover MapReduce)
- 2402 will give students extra experience with Java beyond 1405 and 1406.
- Challenge: where do students get more experience with object-oriented Java? (How much do they need?) Question: could 3004 provide this, or do we need a new course, maybe just for the software engineering stream?
Required Programming Courses
- 1405 and 1406
- 2401, 2402, & 2404
- 3004 and 3007
Old Course Descriptions
COMP 1405 [0.5 credit] Introduction to Object-Oriented Programming A first course in problem solving and computer programming designed for B.C.S. students. Introduction to object-oriented programming; syntactic constructs, data abstraction, classification and inheritance, typing and polymorphism, testing and debugging. Precludes additional credit for COMP 1005 and SYSC 1100. Prerequisite: Restricted to students registered in the B.C.S. program, combined Honours in Computer Science and Mathematics, Honours Computer Mathematics, and Honours Computer Statistics. Lectures three hours a week, tutorial one and a half hours a week.
COMP 1406 [0.5 credit] Design and Implementation of Computer Applications A continuation of COMP 1405 focusing on the design and implementation of complete applications. Topics covered include persistence, graphical user interface design and implementation, event-driven programming, recursion, drawing and manipulating 2D graphics and networking. Precludes additional credit for COMP 1006 and SYSC 1101. Prerequisite: COMP 1405. Restricted to students registered in the B.C.S. program, combined Honours in Computer Science and Mathematics, Honours Computer Mathematics, and Honours Computer Statistics. Lectures three hours a week, tutorial one and a half hours a week.
New Course Descriptions
COMP 1405 [0.5 credit] Introduction to Programming I
A first course in programming emphasizing problem solving and computational thinking. Topics include an introduction to computer science, pseudocode, variables, conditionals, iteration, arrays, objects, functions, sorting, searching, and simulation.
COMP 1406 [0.5 credit] Introduction to Programming II
A second course in programming emphasizing problem solving and computational thinking. Topics include object-oriented programming, abstract data types, linked data structures, testing and debugging, recursion, encapsulation and information-hiding, specification, program efficiency, state machines, and exception handling.
Links for May 10, 2010
From Doug
Toronto [1] CSC108 and CSC 148 (150 is an accelerated combo)
Topics:
Program structure: elementary data types,statements, control flow, functions, classes, objects, methods, fields. Lists; searching, sorting and complexity.
Abstract data types and data structures for implementing them. Linked data structures. Encapsulation and information-hiding. Object-oriented programming. Specifications. Analyzing the efficiency of programs. Recursion.
Waterloo [2] CS 135 and 136
Topics:
Syntax and semantics of a functional programming language. Tracing via substitution. Design, testing, and documentation. Linear and nonlinear data structures. Recursive data definitions. Abstraction and encapsulation. Generative and structural recursion. Historical context.
It introduces the design and analysis of algorithms, the management of information, and the programming mechanisms and methodologies required in implementations. Topics discussed include iterative and recursive sorting algorithms; lists, stacks, queues, trees, and their application; abstract data types and their implementations.
Princeton [3]
Potential topics from Princeton: hardware and software systems; programming in Java; algorithms and data structures; fundamental principles of computation; and scientific computing, including simulation, optimization, and data analysis.
Alberta [4] CMPUT 174 and 175
Potential topics from Alberta for 1405 and 1406:
- computation, states, events, transitions
- state machines, simple pattern matching
- programming basics (variables, input, output, while, if, etc.)
- search
- lists, arrays, and hashes
- regular expressions and pattern matching
- functions, subroutines, and testing
- recursion
- references and data structures
- expression and binary trees
- abstract data types
- simulation
- sorting
- abstract data types
- objects
- graph algorithms
- exceptions
- little languages
- 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 for B.C.S. students, 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 our 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).
- Java forces the use of object oriented programming when such techniques are not useful for very small programming problems. Students will see the object view of data; inheritance & methods are covered in 1406.
- The first run of the new 1405 will use Processing, http://www.processing.org.
- Course should teach basics of imperative programming that are common across programming languages.
- 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 second course in programming for BCS students, emphasizing problem solving and computational thinking in an object-oriented language. Topics include abstraction, mutable data structures, methods, inheritance, polymorphism, recursion, program efficiency, testing and debugging.
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.
COMP 1805
Old Course Description
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
Rationale
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
Reducing the Core Size
Anil S. proposes that we attempt to shrink our core requirements, particularly at the third year, in order to add flexibility to our program. Note this flexibility benefits the faculty as much, if not more, than the students: it allows us to have more "ephemeral" courses without compromising the core CS content of our degrees.
To that end, here is the Software and Computing stream, current and proposed version. Note that this proposal is merely a strawman - it is a starting point for discussion, not the end!
Note in both cases a full degree consists of 20 credits.
New Software and Computing Stream
First Year
COMP 1405 Problem Solving through Programming I (Fall) COMP 1805 Discrete Structures I (Fall) COMP 1406 Problem Solving through Programming II (Winter) MATH 1007 Elementary Calculus I (Fall) MATH 1104 Linear Algebra for Engineering & Computer Science students (Winter) ??? Technical Writing course
2.0 credits in Additional Requirements (see below)
Total: 5 credits
Second Year
COMP ???? Stack I: OS, Architecture, UNIX, C, TCP/IP (recursive DNS) COMP ???? Stack II: compilers/interpreters, languages, databases, web applications COMP ???? Software Engineering I (C++, basic SE, concurrency) COMP 2402 Abstract Data Types and Algorithms COMP 2804 Discrete Structures II
0.5 credit in MATH or STAT at the 2000-level or above 0.5 credit in COMP at the 2000-level or above 1.0 credit in Additional Requirements (see below)
Total: 5 credits
Third Year
COMP 3004 Software Engineering II COMP 2805 (3805) Computability, Complexity, Automata COMP 3804 Design and Analysis of Algorithms I
0.5 credit in COMP, MATH, or STAT at the 2000-level or above 1.0 credit in COMP, MATH, or STAT at the 3000-level or above
2.0 credits in Additional Requirements (see below)
Total: 5 credits
Fourth Year
COMP 4905 Honours Project
1.5 credits in Computer Science at the 4000 level 3.0 credits in Additional Requirements (see below)
Total: 5 credits
Additional Requirements
5.0 credits in Approved Arts or Social Sciences or Science or Business electives 3.5 credits in free electives
Current Software and Computing Stream
First Year
COMP 1405 Introduction to Object-Oriented Programming (Fall) COMP 1805 Discrete Structures I (Fall) COMP 1406 Design and Implementation of Computer Applications (Winter)
MATH 1007 Elementary Calculus I (Fall) MATH 1104 Linear Algebra for Engineering & Computer Science students (Winter)
2.5 credits in Additional Requirements (see below)
Total: 5 credits
Second Year
COMP 2003 Computer Organization COMP 2401 Introduction to Systems Programming(same as old COMP 1402) COMP 2402 Abstract Data Types and Algorithms COMP 2404 Programming in C++ COMP 2805 Discrete Structures II
0.5 credit in Computer Science at the 2000 level or above
0.5 credit from MATH 2007, MATH 2107 or MATH 3101 0.5 credit from STAT 2507 or STAT 2605
1.0 credit in Additional Requirements (see below)
Total: 5 credits
Third Year
COMP 3000 Operating Systems COMP 3004 Object-Oriented Software Engineering COMP 3005 Database Management Systems COMP 3007 Programming Paradigms COMP 3804 Design and Analysis of Algorithms I
0.5 credit in COMP or MATH at the 2000-level or above
2.0 credits in Additional Requirements (see below)
Total: 5 credits
Fourth Year
COMP 4905 Honours Project
1.5 credits in Computer Science at the 4000 level 3.0 credits in Additional Requirements (see below)
Total: 5 credits
Additional Requirements
5.0 credits in Approved Arts or Social Sciences or Science or Business electives 3.5 credits in free electives