Instructor | Hamed Hatami | |
Teaching assistants: |
|
|
Lecture | 112 Maass Chemistry Building 13:05 pm - 14:25 pm (Monday-Wednesday) | |
Office hours: |
|
|
Optional Textbook | Jon Kleinberg and Eva Tardos, Algorithm Design, 2006 | |
Course Outline in PDF format | download | |
Recording | Lectures are NOT going to be recorded. |
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. You must be comfortable with basic concepts from logic and linear algebra, and you must be able to read and write precise mathematical statements.
Here are some questions that can help you decide if you have the background to take this course. If you have trouble understanding or answering these questions, in order to succeed in this course, you need to improve your background before enrolling in this course.
Homework (20% = 5 x 4%). There will be five homework assignments. The due dates are going to be announced. The homework and the exams will be graded based on correctness rather than effort alone. Each assignment will be posted on the course web page. Your grades will be posted on mycourses.
Late homeworks can be submitted until 48 hours after the deadline. There will be a penalty of -10 percent of points for one-day delays and -20 percent for two-day delays on late homework unless the student provides a valid reason. Some personal circumstances for which accommodation may be warranted include but are not limited to Student illness (mental/physical), Family/partner illness, Death in the immediate family or of a person with whom the student has a similarly close relationship, Religious Observances, Pregnancy, Delivery of a child, Parenting issues.
The following are reasons for which an extension request will normally NOT be granted: Employment reasons, Travel/vacation/social plans, Airline flights and schedules, Other assignments and exams due on or about the due date.
Midterm (20% ). There will be an in-class midterm.
Final grade is the highest of (Homework 20% + Midterm 20% + Final exam 60%) or (Homework 20% + Midterm 10% + Final exam 70%). However you must still receive a grade higher than 30% in the final exam in order to pass this course. Both midterm and final are closed-book, but a crib-sheet will be allowed.
Class participation: Although not a formal component of the course grade, active participation can effect your grade in a positive way.
Your (i) background, your (ii) efforts, and, more importantly, (iii) the efficiency of your efforts will be the main determining factors on how well you will master the subject.
The grades will give you some feedback, but you are the only person who can interpret them. Some people are good at exams, and some are not; we all have good and bad days. Your main goal should be to acquire and improve your relevant problem-solving skills rather than obtaining a good grade. The good grade hopefully will be a consequence of that.
Review | |||
Lecture | Topic | Reading | Optional |
0 | Background | Lecture 0 on Mycourses | |
Part I | |||
Lecture | Topic | Reading | Optional |
1 | The Ford-Fulkerson Algorithm | Lecture 1 on Mycourses | 7.1 of KT book |
2 | Max flow-Min cut Theorem, correctness of the Ford-Fulkerson | Lecture 2 on Mycourses | 7.2 |
3 | Choosing good augmenting paths (Scaling FF) | Lecture 3 on Mycourses | 7.3 |
4 | Bipartite Matching | Lecture 4 on Mycourses | 7.5 |
5 | Hall and Konig's theorem | Lecture 5 on Mycourses | 7.5 |
6 | Multi Source/Sink, Circulation with demands, Flow with lower-bounds. | Lecture 6 on Mycourses | 7.7 |
Part II | |||
Lecture | Topic | Reading | Optional |
7 | Linear programming. Formulating problems as LPs. | Lecture 7 on Mycourses | N/A |
8 | Standard form, Geometric intuition. | Lecture 8 on Mycourses | Sections 1 and 2 of Luca Trevisan's Lecture 5. |
9 | introduction to duality. | Lecture 9 on Mycourses | Finishing Lecture 5 and starting Lecture 6 from Luca's notes. |
10 | Writing the Dual of a Linear program. Strong Duality. | Lecture 10 on Mycourses | |
11 | Complementary Slackness | Lecture 11 on Mycourses | |
12 | Mini-Max Theorem and Game Theory | Lecture 12 on Mycourses | |
Part III | |||
Lecture | Topic | Reading | Optional |
13 | Complexity Theory. Decision Problems. The complexity classes P, NP. | Lecture 13 on Mycourses | 8.3, 8.9 |
14 | Polynomial reductions, Cook-Levin: NP-completeness of SAT. | Lecture 14 on Mycourses | 8.3, 8.9 |
15 | NP-completeness of 3SAT, Hamiltonian cycle and path, Traveling Salesman Problem. | Lecture 15 on Mycourses | 8.1, 8.2, 8.4 |
16 | NP-completeness of the Maximum Independent Set problem, Max Clique, Vertex Cover, Set Cover. | Lecture 16 on Mycourses | 8.2, 8.5, 8.7, 8.8, 8.10, 9. |
17 | NP-completeness of 3-Coloring | Lecture 17 on Mycourses | 8.2, 8.5, 8.7, 8.8, 8.10 |
18 | SubsetSum, Knapsack, PSPACE | Lecture 18 on Mycourses | 9.1 and 9.2 |
Academic honesty. McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences 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, and they will be reported to disciplinary office.
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.