General Information

News:

• There is no tutorial tomorrow Aug 6. I will be in my office 3-5:45 pm and can answer questions.
• Please note that we did not cover Network Flow and therefore it is not on the final.
• Quiz 2 marks are on ePost.
• The final is cumulative, the syllabus is everything we covered in the course. An old final is here.
• Assignment 1 marks are on ePost. If you emailed me your solutions, your marks may not be included. They will be added shortly.
• Class forum set up -- can be reached here.

Assignments

• Assignment 1 is here. The deadline is postponed by one week, i.e., the same times on May 21. Solutions are here.
• Assignment 2 is here. Solutions are here.
• Assignment 3 is here. Solution pointers are here.
• Assignment 4 is here. Solutions are here.
• Assignment 5 is here. The assignment can be submitted without penalty upto noon, Aug 6, in the dropbox, or by email. For question 1, do not answer the part that asks for the most efficient implementation of each part. For Q3, look up the Set covering problem from Ch 35.3 (just the problem, not the algorithm) and try to use the fact that this problem is known to be NP-complete. Solutions are here.

• The first tutorial will be held on Wed May 8, 4-6 pm in CB 115. We covered these slides and these problems -- problem 3 was left as an exercise.
• The second tutorial will be held on Mon 13 May, 5:30-7pn in Lassonde/CSEB 3033. We covered these problems.
• Tutorial 3 on Wed May 22, 4:30 - 6 pm in CB 115. We covered these problems and one generalization of solving recurrences.
• Tutorial 4 on Thu May 30, 5:30 - 7 pm in TEL 0005. We went over solutions to some problems in the two old tests published as samples.
• Tutorial 5 on Wed June 5, 4:30 - 6 pm in CB 115. We solved some recurrences that cannot be solved using the Master Theorem, including these.
• Tutorial 6 on Wed June 12, 4:30 - 6 pm in LSB 105. We covered most of these problems.
• No formal tutorial on Wed June 18. I will be available to solve problems and answer questions in my office.
• Tutorial 7 will be on Wed July 17, 7-8:30 pm, TEL 1016. We covered solutions to quiz 2 and some greedy algorithms.
• Tutorial 8 will be on Mon July 22, 7-8:30 pm, CB 129. We covered several problems on MSTs.
• Tutorial 9 will be on Wed July 31, 7-8:30 pm, TEL 1016. We will go over the posted old final.

Lecture schedule

1. May 7: Administrivia. Introduction to algorithm analysis. My slides are here (pdf).
2. May 14: Introduction to algorithm analysis - continued. My slides are here (pdf). Here are some solved problems on proving correctness using loop invariants.
3. May 21: Introduction to divide and conquer. My slides are here (pdf).
4. May 28: Recurrence relations and the Master Theorem (Ch 4). Same slides as before. More sorting algorithms (Ch 6,7). My slides are here (pdf).
5. June 4: Lower Bounds. Sorting in Linear time (Ch 8). My slides are here (pdf).
6. June 11: Selection in Linear time (Ch 9). My slides are here (pdf).
7. June 18: Dynamic Programming: Ch 15. My slides are here (pdf).
8. July 2: Dynamic programming, no new slides. Some practice problems are here.
9. July 9: Introduction to greedy algorithms. Ch 16. My slides are here (pdf).
10. July 16: Quiz 2. Finish greedy algorithms (same slides as before). Start graph algorithms. My slides are here (pdf).
11. July 23: Continue graph algorithms. BFS, DFS, Topological sort. Start shortest path problems (Ch 23, 24). My slides are here (pdf) and here (pdf).
12. July 30: Finish shortest paths, transitive closure (same slides as last class). Introduction to NP-completeness. My slides are here (pdf).

 Course summary:

• Mathematical background (asymptotic notation, recurrence relations, bounding sums, induction, etc.) [Ch 1, 2.2, 3, 4]
• Proofs of correctness, including loop invariants [Ch 2]
• Recursive algorithms; divide and conquer technique [Ch 2.3, 4]
• Sorting algorithms and lower bounds [Ch 6,7,8]
• Selection [Ch 9]
• Greedy algorithms [Ch 16]
• Dynamic programming [Ch 15]
• Graph algorithms (searching, spanning trees, shortest path, etc.) [Ch 22,23,24,25,26]
• (If time permits) A brief introduction to NP-completeness. [Ch 34]

Enrollment

Textbook (required)

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 3rd edition, MIT Press & McGraw-Hill, 2009. For solutions to some problems and known errata, follow this link. This book will be carried by the University Bookstore

Optional Supplementary Reading

• Jeff Edmonds, How to Think About Algorithms.
• Ian Parberry's book, Problems on Algorithms, is a terrific source for practice problems on many topics covered in this course. Solutions to selected problems are also given. Follow this link to access the book.

Other References 

• Daniel Solow, How to Read and Do Proofs (3rd edition), Wiley, 2002.
• Gilles Brassard and Paul Bratley, Fundamentals of Algorithmics, Prentice Hall, 1996.
• Michael R. Garey, and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979.
• Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science (2nd edition), Addison-Wesley, 1994.
• Robert Sedgewick, Algorithms (2nd edition), Addison-Wesley, 1988.
• Other references may be added later.
  

Course policies:

• Academic honesty: We take matters of academic honesty very seriously. If you wish to have more information on this topic, please visit this page.
• Missed tests: Any student missing a test for any reason other than medical automatically gets a score of zero for the test. If the student has medical grounds and provides proper documentation, then the marks will be transferred to the final. There will NOT be any substitute or make up tests. If you do need to supply medical documentation, please be sure to use the updated form downloadable from here. Details of York policies on deferred exams are here.

Important Dates:

• May 7: First class
• Drop deadline: July 9
• July 30: Last class
• Holidays : May 20, July 1, Aug 5 (none of these coincide with lectures)
• Finals: scheduled by the registrar's office during Aug 6-16.

Grades

• Assignments: 20%, We will try to have at least 5 short assignments.
• Quiz 1 (10%): 8:40 pm, June 4. There will be a lecture before the test. The syllabus is Ch 1,2,3,4.1,4.2,4.3,4.4. You are expected to remember the formulas for sums of the first n integers and the sum of squares of the first n integers.
  Two sample tests are here and here-- note that the format will be similar but the sample tests were on smaller syllabi than your quiz.
  Please try the questions before reading the solutions.
  Quiz 1 marks are on ePost. Solutions are here and here.
• Quiz 2: 10%, in class, July 16. The syllabus for the quiz is Linear time Selection and Sorting and Dynamic programming.
  The quiz will be from 7 - 8 pm on July 16. There will be a lecture afterwards.
  Solutions to quiz 2 are here.
• Midterm, June 25, in class, 7:30-9:30 pm.
  Syllabus: Ch 1,2,3,4,(except 4.6), 6, 7 (except 7.3), 8, 9 (except 9.2).
  An old test is here. Please note that this was a shorter test in terms of both duration and syllabus, and is provided to give you some practice examples.
  This list of formulas will be provided with the midterm.
  Here are some practice problems on Ch 8,9. Please try them before looking at these solution sketches.
  Midterm marks are on ePost. Solutions are here and here
• Final Exam: 40%, Wed, Aug 7, 2:00-5:00, CLH B, as scheduled by the registrar.