|
|
(24 intermediate revisions by the same user not shown) |
Line 1: |
Line 1: |
| This page contains notes and discussions related to the 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= | | =Requests for more data= |
Line 41: |
Line 37: |
| *STAT 2605 | | *STAT 2605 |
|
| |
|
| =COMP 1405/1406 Redesign= | | =Detailed Discussions= |
| | |
| ==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 [http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-00Fall-2008/CourseHome/ 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, [http://www.cs.princeton.edu/introcs/home/ 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)
| |
| [[File:Example.jpg]]
| |
| | |
| Using for loops to augment drawing.
| |
| | |
| Grass:
| |
| | |
| [[File:Example.jpg]]
| |
| | |
| Stars:
| |
| | |
| [[File:Example.jpg]]
| |
| - 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
| |
| [[File:Example.jpg]]
| |
| | |
| 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
| |
| | |
| [[File:Example.jpg]]
| |
| | |
| 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
| |
| [http://www.artsandscience.utoronto.ca/ofr/calendar/crs_csc.htm]
| |
| 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
| |
| [http://www.ucalendar.uwaterloo.ca/1011/COURSE/course-CS.html]
| |
| 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
| |
| [http://registrar.princeton.edu/course-offerings/course_details.xml?courseid=002051&term=1112]
| |
| | |
| 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
| |
| [http://cs.ualberta.ca/undergraduate-students/course-directory]
| |
| 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.)
| |
| | |
| [http://www.cs.ubc.ca/ugrad/info/planning/programRequirements.shtml UBC CS Program Options and Requirements]
| |
| | |
| [http://www.calendar.ubc.ca/vancouver/index.cfm?tree=12,215,410,421 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 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
| |
| | |
| | |
| ===New Course Descriptions===
| |
| | |
| '''COMP 2010: Stack I'''
| |
| | |
| An introduction to the lower computational stack: computer architecture, operating systems, and networking. Topics: processor and I/O architectures, device drivers, file systems, memory hierarchy, virtual memory, kernels, hypervisors, scheduling, TCP/IP, socket programming. Implementation exercises and experiments are in C and shell programming on a UNIX-like environment.
| |
| | |
| | |
| '''COMP 2011: Stack II'''
| |
| | |
| An introduction to the upper computational stack: language-based virtual machines, desktop environments, and web applications. Topics: dynamic libraries, scripting and functional languages, interpreters, compilation, databases, remote procedure calls, and performance and security concerns in modern distributed applications.
| |
| | |
| '''COMP 1805: 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, countability, functions, relations, boolean algebra. Material is illustrated through examples from computing.
| |
| | |
| | |
| '''COMP 2804: Discrete Structures II'''
| |
| | |
| Introduction to discrete mathematics and discrete structures. Topics include: counting, sequences and sums, discrete probability (including random variables, expectation, linearity of expectation, dependence, concentration results, distributions), simulation, randomized algorithms.
| |
| | |
| | |
| '''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, NP-completeness.
| |
| | |
| ==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
| | *[[CR: COMP 1405/1406 Redesign|COMP 1405/1406 Redesign]] |
| electives
| | *[[CR: Theory course redesign|Theory course redesign]] |
| 3.5 credits in free electives
| | *[[CR: Other CS approaches to Math/Theory]] |
| | *[[CR: New course descriptions and rationale|New course descriptions and rationale]] |
| | *[[CR: Survey of theory requirements in other Canadian Honours programs|Theory requirements survey]] |
| | *[[CR: Reducing the Core Size|Reducing the Core Size]] |
| | *[[CR: Learning Objectives]] |
| | *[[CR: Proposal to Faculty May 2011]] |
| | *[[CR: stream changes]] |
| | *[[CR: Proposal to Faculty September 2011]] |
| | *[[CR: Third and Fourth Year]] |
| | *[[CR: Attracting advanced students]] |
| | *[[CR: Curriculum Changes April 2012]] |
| | *[[CR: to do list]] |
| | *[[CR: Notes Fall 2012]] |
| | *[[CR: New 3rd year courses]] |
| | *[[CR: Curriculum Changes for 2015/2016]] |
| | *[[CR: Winter 2014]] |
| | *[[CR: Summer 2014]] |