Comp 360 Algorithm Design

 

Office hours for the final exam: Friday and Saturday 3:00-5:00.

Instructor   Hamed Hatami
TA   Liana Yepremyan, Xing Shi Cai. TAs are only responsible for grading, and you should only contact them regarding the grading of your assignment and exams.
Lecture   Monday-Wednesday 11:35 AM-12:55 PM in MCMED 1034
Outline course outline
Office hours   Monday-Wednesday 2:30-3:30pm in McConnell 308. If you want to meet outside office hours, the best thing is to send me an email, but you can also just drop by my office, and if I'm not busy I will answer your questions.
Textbook Jon Kleinberg and Eva Tardos, Algorithm Design, 2006

Description

This course is an undergraduate course on advanced algorithmic techniques and applications. Topics include Network Flows, Linear programming, Complexity and NP-completeness, Approximation Algorithms, Randomized Algorithms, and Online Algorithms.

This is a rigorous course with an emphasis on mathematical proofs rather than implementations. The prerequisites are Comp 251 and one of Math 240/Math 235/Math 363.

Grading

Homework (20% = 5 x 4%). There will be six biweekly homework assignments, and your five highest grades will count towards your overall grade. The due dates are going to be announced. No late homework will be accepted (as your lowest score on an assignment will be dropped). The homework will be graded based on correctness rather than effort alone. Each assignment will be posted on the course web page. The homework must be submitted to the drop-off box at Trottier building before the deadline. Your grades will be posted on mycourses.

Midterm (20%) and final (60%). There will be two exams: a midterm and a final exam. The exams are closed-book, and closed-notes.

Attendance and class participation: Although not a formal component of the course grade, attendance is essential for success in this course. Active participation can effect your grade in a positive way.

Course Schedule

Review
Lecture Topic Reading
1(1/11) Running Time and Big O notation
2(1/13) Dynamic programming 6.4
Part I
Lecture Topic Reading
3(1/18) The Ford-Fulkerson Algorithm 7.1
4(1/20) Max flow-Min cut Theorem, correctness of the Ford-Fulkerson 7.2
5(1/25) Choosing good augmenting paths,
Optional reading: the fattest path algorithm
7.3
6(1/27) Bipartite matching, Konig's theorem Theorem 3.14 here. 7.5
7(2/1) Disjoint path problem (directed and undirected). 7.6
8(2/3) Further Applications of the Max-Flow problem 7.12
Part II
Lecture Topic Reading
9(2/8) Linear programming. Formulating problems as LPs,
geometric interpretation of LPs.
This and Luca Trevisan's Lecture 5.
10(2/15) LP's in standard form,
introduction to duality.
Finishing Lecture 5 and starting Lecture 6 from Luca's notes.
11(2/17) Strong duality, duality and MaxFlow-MinCut. Finishing Lecture 6 from Luca's notes. Dual in general. Section 1.5 here
12(2/22) Midterm Group I.
13(2/24) Midterm Group II.
Part III
Lecture Topic Reading
14(7/3) The complexity classes P, NP, CoNP, EXP. 8.3, 8.9
15(9/3) NP-completeness of SAT and Max Independent Set. 8.1, 8.2, 8.4
16(14/3) NP-completeness of Max Clique, Vertex Cover, 3SAT. 8.2
17(16/3) NP-completeness of Set Cover, 3-Colourability, k-Colourability. 8.2, 8.7
18(21/3) NP-completeness of Hamiltonian cycle and path, Traveling Salesman Problem, SubsetSum. PSPACE contains NP,CoNP, and is contained in EXP, and QSAT is in PSPACE. 8.5, 8.8, 8.10, 9
Part IV
Lecture Topic Reading
19(23/3) Approximation algorithms for Load balancing and vertex cover. 11.1
20(30/3) Approximation algorithm for the center selection problem, and a 2-factor Approximation algorithm for Vertex Cover based on rounding LP. 11.2 and this
21(4/4) Approximation algorithm for the Set Cover problem. Chapter 6 of these notes
22(6/4) Approximation algorithm for the Knapsack problem. 11.8
23(11/4) Randomized algorithms: Verifying matrix multiplication (Not in the final exam) Freivalds' algorithm
24(13/4) Online algorithms (Not in the final exam)

Assignments and exams

Midterm: The midterm covers flow networks and linear programming. If your student id ends in an even number (for example 260000000), you will be taking the exam on Monday 22nd, and if it ends in an odd number (for example 260000001) you will be taking it on Wednesday 24th. If you are registered to take the exam with OSD, then your exam is on 22nd regardless of your student id. Here is the exam from the previous semester: link. (We have not covered the complementary slackness yet, so it won't be in this semester's exam).

Policies

Academic honesty. McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offenses under the Code of Student Conduct and Disciplinary Procedures (see http://www.mcgill.ca/integrity for more information). Most importantly, work submitted for this course must represent your own efforts. Copying assignments or tests from any source, completely or partially, allowing others to copy your work, will not be tolerated.

Submission of written work in French. In accord [sic] with McGill University's Charter of Students' Rights, students in this course have the right to submit in English or in French any written work that is to be graded.