

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 redblack 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 highlevel pseudocode and then analyze these
algorithms to formally prove their correctness and efficiency.
Textbook
Algorithms by Sanjoy Dasgupta, Christos Papadimitriou and Umesh
Vazirani
McGrawHill (ISBN 0073523402)
Assignments
Posted  Due  
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 
Sample Midterm  Solutions  
Assignment 8  Solutions  July 5  July 13 
Assignment 9  Solutions  July 12  July 19 
Assignment 10  Solutions  July 19  July 28 (Extended) 
Sample Final  Solutions 
Topics and Tentative Schedule
Introduction  May 3  
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 
Randomization  Annotated  Jul 19  
NPcompleteness  Annotated  Jul 19, 26  
Tree Distance Metrics  Annotated  Jul 26  Not on Final 
Final Review  Jul 28 
Tutorials
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 
Evaluation
Current Marks  
Assignments  40%  
MidTerm  20%  June 30 (Inclass) 
Final  40% 
Late Policy
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.
Withdraw Dates
The last day to withdraw without a ``W'' is May 31st and the last day
to withdraw with a ``W'' is June 29th.
Academic Integrity
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/ .