Just as a reminder, the Final Exam will be Saturday August 6 from
1:00 PM to 4:00 PM in Room C332 of the Life Sciences Centre. Good Luck!!!
Note: As we discussed in class on Tuesday May 10, the midterm date is now Thursday June 30
May 18: In the tutorial it was sucessfully argued that the range query operations on sorted arrays and red-black trees as well as the delete operations on linked lists were misleading, so every assignment 1 has had 4 marks added.
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.
There are two prerequisite courses, CSCI 2110: Computer
Science III and CSCI 2112: Discrete Structures I, and you are expected
to know the basic data structures and proof techniques from those courses.
There is no real programming in this course. We will design
efficient algorithms in high-level pseudocode and then analyze these
algorithms to formally prove their correctness and efficiency.
Algorithms by Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani
McGraw-Hill (ISBN 0073523402)
|Assignment 1||Solutions||May 3||May 10|
|Assignment 2||Solutions||May 10||May 17|
|Assignment 3||Solutions||May 17||May 25|
|Assignment 4||Solutions||May 24||May 31|
|Assignment 5||Solutions||May 31||June 7|
|Assignment 6||Solutions||June 7||June 14|
|Assignment 7||Solutions||June 14||June 21|
|Assignment 8||Solutions||July 5||July 13|
|Assignment 9||Solutions||July 12||July 19|
|Assignment 10||Solutions||July 19||July 28 (Extended)|
Topics and Tentative Schedule
|Fundamentals||Annotated||May 3, 5|
|Graph Algorithms||Annotated||May 10, 12, 17|
|Greedy Algorithms||Annotated||May 19, 24, 26|
|Divide and Conquer||Annotated||May 31, Jun 2, 7, 9|
|Dynamic Programming||Annotated||Jun 14, 16, 21, 23|
|Midterm Review||Jun 28|
|Data Structuring||Annotated||Jul 5, 7, 12, 14||Lecture Notes|
|NP-completeness||Annotated||Jul 19, 26|
|Tree Distance Metrics||Annotated||Jul 26||Not on Final|
|Final Review||Jul 28|
|Tutorial 1: Contradiction and Induction||May 4|
|Tutorial 2: Asymptotic Notation||May 11|
|Tutorial 3: Graph Problems||May 18|
|Tutorial 4: Greedy Problems||May 25|
|Tutorial 5: Lower Bounds||June 1|
|Tutorial 6: Recurrence Relations||June 8|
|Tutorial 7: Divide and Conquer||June 15|
|Tutorial 8: Closest Pair and Midterm Review||June 22|
|Tutorial 9: Midterm Review||June 27|
|Tutorial 10: Midterm Answers and Dynamic Programming||July 6|
|Tutorial 11: Sweep Line||July 13|
|Tutorial 12: Sweep Line||July 20|
|Tutorial 13: Sample Final||July 27|
|Mid-Term||20%||June 30 (In-class)|
I do not accept late assignments without a doctor's note or other official document. Late assignments delay posting and discussing solutions and add extra hassle for marking. I can only make an exception to this rule if you discuss the circumstances with me in advance and ask for a reasonable extension.
The last day to withdraw without a ``W'' is May 31st and the last day to withdraw with a ``W'' is June 29th.
You are allowed to discuss assignment problems and solutions with other students, but you are expected to complete and submit only your own work. All assignment problems can be completed based on the material covered in lectures and in the text - do not look to outside sources (such as the internet) and document any help you receive. Academic Integrity offences are very serious with penalties ranging from 0 marks on an assignment to failure or even expulsion. Please read and make sure you understand the University policies: http://academicintegrity.dal.ca/Policies/ .