Notice: The list of marks to date has been updated and is available as a PDF file.
Notice: In case you didn't take a copy after the exam (or lost it), the Midterm exam is available here for study purposes.
Notice: Mark Lanthier has asked me to announce that there will be a 4th year robotics course (a special topics course) that will be offerred in the fall. In the course, students will have labs in which they will get hands-on experience with real robots. The course description will not be listed in the regular calendar, but will be posted soon on professor Lanthier's webpage and probably the school webpage.
5802 Students: The deadline for your projects is Monday April 24th.
5802 Students: The seminars will take place on Thursday April 6th at the usual time and place. Please prepare a 20 minute talk so we have time for questions between talks. I will bring a projector and PowerPoint-equipped laptop for you to use.
The prerecorded lecture (part 1 and part2) will stay here until the end of the semester. To download it you will have to install Dijjer. If you've downloaded it and are having problems viewing it I've been told that VideoLan works well.
5802 Students: It's time to think about your final project and seminar. For your project/seminar you will select on of the papers on this list, give a 20 minute presentation about it and write a 10-20 page summary of the results in the paper, discuss the main techniques used to prove those results, and do a forward search of subsequent papers that cite this one to see what impact the paper has had and what further results have been obtained. Everyone must present a different paper and it's first-come-first-served so as soon as you choose your paper send me an email so I can prevent other people from choosing the same paper.
An introduction to the design and analysis of algorithms. Topics include: recurrence relations, sorting and searching, divide-and-conquer, dynamic programming, greedy algorithms, amortized analysis. (Also listed as MATH 3804.) Prerequisites: COMP 2002 or COMP 2402, and either COMP 2805 or both of MATH 2007 and MATH 2108, or equivalents. Lectures three hours a week.
The course text is
In addition, the following images are scanned from my personal course notes. They are quite terse and probably only useful as a reminder of what was talked about in class.
| First day | Theoretical Computer Science Cheat Sheet! | |
| Interesting | The top 10 algorithms of all time! | |
| Jan. 5 | Chapters 3 & 4 App. A |
Asymptotic notation, summations, and recurrences |
| Source code for Bentley's problem | ||
| Jan. 12 | Chapters 6-9 | Sorting |
| Jan. 19 | Chapter 6 | Linear-time selection |
| Section 28.2 | Fast multiplication algorithms | |
| Sorting algorithms code | Jan. 26 | Chapters 12-14 | Red-black trees, 2-4 trees, order statistics trees |
| Feb. 2 | Chapter 15 | Dynamic programming |
| Feb. 9 | Section 15.4 | Longest common subsequence and edit distance |
| Section 22.4 | Topological sort | |
| Section 24.3 | Dijkstra's algorithm | |
| Feb. 16 | Section 24.1 | Bellman-Ford single-source shortest path algorithm |
| Chapter 25 | All-pairs shortest paths and related problems | |
| Feb. 23 | Study week | |
| Mar. 2 | Midterm exam | |
| Mar. 9 | Chapter 23 | Midterm review and Minimum spanning trees |
| Mar. 16 | Chapter 34 | P, NP, and Cooke's Theorem (notes) (notes) |
| Mar. 23 | Chapter 34 | NP-completeness and 7 NP-hard problems (notes) (notes) (notes) |
| Mar. 30 | Chapter 23 | Review lecture |
My office hours are Thursday from 14:30-17:30 in room 5177HP. Any other meeting time will have to be arranged by email. The TAs office hours (in room 1175 HP, as usual) are as follows:
| Stefanie Wuhrer | Tuesday | 10:00-12:00 |
| Jiehua Yie | Friday | 10:00-12:00 |
COMP3804 grades will be assigned using the following grading scheme.
| Assignment 1 | 10% |
| Assignment 2 | 10% |
| Mid-term | 20% |
| Assignment 3 | 10% |
| Assignment 4 | 10% |
| Final exam | 40% |
| Total | 100% |
COMP/SYSC/ISYS/MATH5802 grades will be assigned using the following grading scheme:
| Assignment 1 | 10% |
| Assignment 2 | 10% |
| Mid-term | 20% |
| Assignment 3 | 10% |
| Assignment 4 | 10% |
| Presentation | 20% |
| Project | 20% |
| Total | 100% |
I may, at my discretion, increase the grades of certain students to raise the class average or change the distribution. This will never cause a student's grade to go down, nor will it change the relative rankings of students so, e.g., it is not possible for a student who earned an 80% to receive a lower grade than a student who earned a 75%.
The following is a (tentative) schedule for assignments and exams.
| January 19 | Assignment 1 due |
| February 2 | Guest lecturer, office hours cancelled |
| February 16 | Assignment 2 due |
| March 2 | Midterm exam |
| March 9 | Assignment 3 due |
| March 30 | Assignment 4 due |
| TBA | Final exam |
Students are encouraged to collaborate on assignments, but at the level of discussion only. That is, they may work together to solve problems, but when writing down the solutions they should do so on their own. No student should show another student his or her written solutions.
Any student who is caught submitting work that they did not do themselves will receive a mark of 0 (zero) on that assignment. Any group of two or more students handing in sufficiently similar assignments will all receive mark of zero.
Students with special needs should obtain documentation from the Paul-Menton Center and notify me as soon as possible.