General Information

News:

• Prof Jeff Edmonds is going to give a talk on Machine Learning on Mar 28 at 7 pm in Bergeron (room TBA). Details. All are welcome.S
• There is no tutorial this week (i.e. Jan 4, 2019)
• Welcome to EECS 3101M!

Assignments

• Assignment 1.
• Assignment 2.
• Assignment 3.

Tutorials

• Tutorial 1 (Jan 11) will be led by Prof Jeff Edmonds
• Tutorial 2 (Jan 18) will be led by Amir Rasouli. The problems covered are here.
• Tutorial 3 (Jan 25): The problems to be covered are here and perhaps some questions from the old test (placed on moodle).

Lecture schedule

1. Jan 3: Administrivia. Introduction to algorithm analysis . Loop invariants. We reached slide 11 of this set
2. Jan 8: Finish correctness of FindMax. Analysis of FindMax (slides) We covered all but the last 3 slides.
3. Jan 10: More on proofs of correctness using loop invariants (slides). We did not reach the proof of correctness of insertion sort.
4. Jan 15: Finish the proof of insertion sort. Discussion on the assignment. More proofs of correctness (slides).
5. Jan 17: More correctness examples. Divide and Conquer Algorithms (slides).
6. Jan 22: Solving Recurrences to analyze Divide and Conquer algorithms (slides); typos in slides fixed. We did not cover the last 7 slides.
7. Jan 24: Finish Divide and Conquer. Start more sorting algorithms (slides)
8. Jan 31: Finish sorting slgorithms (4 slides were added to the previous set). Lower Bounds (slides).
9. Feb 5: Linear time sorting (slides). If time permits, Medians and order statistics (slides).
10. Feb 7: Finish order statistics. Dynamic programming (slides).
11. Feb 12: Dynamic programming continued
12. Feb 26: More Dynamic programming (slides).
13. Feb 28: Still more Dynamic programming (slides).
14. Mar 7: Finish Dynamic programming. Start greedy algorithms (slides).
15. Mar 12: More greedy algorithms (slides).
16. Mar 14: Finish greedy algorithms, start graph algorithms (slides).
17. Mar 19: More graph algorithms (slides).
18. Mar 21: Graph search algorithms (slides).
19. Mar 28: Shortest path algorithms (slides).
20. Apr 2: Intractibility (NP-completeness) (slides).

 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: for brushing up on proof techniques.
• Michael R. Garey, and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979: the original textbook on NP-completeness.

Course policies:

• Academic honesty: It is important that you look at the departmental guidelines on academic honesty.

  Although you may discuss the general approach to solving a problem with other people, you should not discuss the solution in detail. You must not take any written notes away from such a discussion. Also, you must list on the cover page of your solutions any people with whom you have discussed the problems. The solutions you hand in should be your own work. While writing them, you may look at the course textbook and your own lecture notes but no other outside sources.

• Missed tests: If you miss a test or the final due to medical reasons you are required to contact the instructor within 7 days of the scheduled exam with documentation. York University has a new form that your doctor should fill out. You can download it by clicking here.

  If you miss an assignment or test the weight will be transferred to the final. If you miss the final, you have to get the instructor to sign a deferred standing agreement within 7 days of the scheduled exam (the instructor has the right to refuse to agree, and in that case the student can petition to take the deferred examination). The department will arrange for a deferred examination at the beginning of the following term.

Important Dates:

• Jan 3: First day of class
• Feb 16-22: Reading week (no classes or tests)
• March 8: Drop deadline
• Apr 3: Classes end
• April 4: Study day
• April 19: Good Friday
• Apr 5-20: Exam period

Grades

• Assignments: 15%, We will try to have at least 4 short assignments.
• Tests (35%). Three in-class tests (15% each): [Note that the test in which a student gets her/his minimum mark will be weighted down to 5%]
  1. Test 1 (15%): Jan 29, in class. Syllabus: Proofs of correctness of iterative algorithms, divide and conquer algorithms, run-time analyses and asymptotic notation. A sample test is available on moodle.
  2. Test 2 (15%): Mar 5, in class. Syllabus: Recursive algorithms, divide and conquer technique [Ch 2.3, 4]; Sorting algorithms and lower bounds [Ch 6,7,8]; Selection [Ch 9]. Dynamic Programming is not included on this test.
  3. Test 3 (15%): Mar 26, in class. Syllabus: Dynamic Programming, Greedy Algorithms. Graph Algorithms are not included.
• Final Exam: 50%, scheduled by the registrar -- Syllabus: Everything covered in the course.