CSCI 3110 - Summer 2011
Design and Analysis of Algorithms I


Instructor: Christopher Whidden
Office: CS 320 (Thursdays only)
  Mona Campbell Building 4236
E-mail: whidden@cs.dal.ca
   
TA: Jeremy Porter
E-mail: jporter@cs.dal.ca

Class: TR 11:35-12:55 in CS 127
Tutorial: W 11:05-11:55 in CS 127
Office Hours: R 1:30-3:30 in CS 320
    and by appointment
       
Office Hours: M 1:00-2:00 in the Learning Centre (CS 233)

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.

Textbook
Algorithms by Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani
McGraw-Hill (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    

Note: Assignments must be handed in by the end of the class on the day they are due.

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  
NP-completeness 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%  
Mid-Term 20% June 30 (In-class)
Final 40%  

The letter grade will be assigned according to the standard table: 90-100 A+, 85-89 A, 80-84 A-, 77-79 B+, 73-76 B, 70-72 B-, 65-69 C+, 60-64 C, 55-59 C-, 50-54 D, 0-49 F.
There will be about 10 assignments but only the best 8 assignments count, each with equal weight.
The final exam will be 3 hours long in early August; it is scheduled by the registrar.

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/ .