Comp 360 Algorithm Design

Preparation for the final exam

• Office Hours for the final exam:
  • (Tsun Ming Cheung MC 303) Tuesday April 25th, 12:00-13:00
  • (Ben Davis MC 303) Friday April 21st, 16:00-17:00
  • (Hamed MC 308) Monday April 24th, 13:00-16:00
  • (Hamed MC 308) Tuesday April 25th, 13:00-15:00
• The final exam covers Linear Programming, NP-completeness, Approximation algorithms, and randomized algorithms.
• Note that Linear Programming can appear as part of Approximation algorithms, randomized algorithms, and even NP-completeness. Make sure to study it well.
• Front page of the Final Exam.
• Several sample final exams are posted on mycourses. Please ignore the last part of the last question of SampleFinal4, as it is not covered in the class.
• I will hold office hours closer to the final exam. I will announce the details later.

Important Dates

• Homework 1 (Release date:Jan 18 - Due date:Jan 31)
• Homework 2 (Release date:Jan 30 - Due date:Feb 14)
• Midterm Feb 17 in class (Covers Flow Networks + Linear Programming)
• Homework 3 (Release date:Feb 13 - Due date:Feb 28)
• Homework 4 (Release date:Mar 6 - Due date:Mar 21)
• Homework 5 (Release date:Mar 24 - Extended Due date due to power outage:April 10)

• Quiz 1: Solution
• Quiz 2: Solution
• Quiz 3: Solution
• Quiz 4: Solution
• Quiz 5: Solution
• Sample Midterm + Solution
• Sample Midterm + Solution

Description

This course is an undergraduate course on advanced algorithmic techniques and applications. Topics include Network Flows, Linear programming, Semi-definite 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 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.

Grading

Surprise Quizzes (10%): There will be 5 surprise quizzes in the class. The purpose of these short quizzes is to enforce attendance and also to provide a practice for the final exam. These quizzes will not be graded and participation in them will suffice. Each quiz is worth 2.5% (with a maximum total 10%). Therefore, you only need to take 4 quizzes to receive the full 10%.

Homework (15% = 5 x 3%). 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 (out of 100) points for one-day delays, and -20 points for two-day delays on late homeworks unless a valid reason is provided by the student. 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 (15% ). There will be an in-class midterm.

Final grade is (Homework 15% + Midterm 15% + Quizzes 10% + Final exam 60%). 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, and closed-notes.

Class participation: Although not a formal component of the course grade, active participation can effect your grade in a positive way.

Some advice on how to do well in this course:

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 are to give you some feedback, but you are the only person who can interpret them. They have some correlation with how well you have understood and learned the subject (that is why people will look at your grades, and GPA), but by no means this is definite. Some people are good at exams, and some are not, and we all have good days 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.

• Your background is the most important factor on how you will do in this course. If you are coming with a good understanding of logic, proofs, and have good problem-solving skills, you will do well in this course. If you lack in these skills, it is better to postpone this course until you acquire them, but if you absolutely have to take this course now, you will benefit more from focusing on those rather than being overwhelmed with the new material. In this case, try to consult more elementary books, and find just easy math problems, and try to write the proofs as precisely as possible. Imagine another person reading your solution. Will that person understand what you mean? Will they understand why this is correct?
• Solve problems: Solve as many problems as you can. Avoid the temptation to look at the solution, avoid searching the Internet, or discussing it with other students. Try your absolute hardest before giving up. If it didn't work, then look for some hints, and then the last stage is to actually read the solution. Try to understand why you couldn't solve it by yourself. In my experience solving a problem by yourself, without any hints, has the greatest learning effect, and reading the solution to a problem has the least effect. Solving one difficult problem is probably better than reading the solutions to 100 problems.
• Be skeptical of your solutions, and learn to distinguish between correct and incorrect solutions. Sometimes students complain to me that their incorrect proof or solution deserves more partial marks. Such solutions are sometimes an indication that the student has not been able to tell that their proof was incorrect. It happens very often that I see the students who understood the course better and solve the harder questions, leave the answer to some difficult questions blank as they are well aware of the fact that they were not able to solve that particular question. Because of this high partial marks are only given to solutions that are correct but have some minor mistakes.

Tentative Course Schedule

Some relevant talks

• Avi Widgerson's talk on P vs NP.
• Bill Cook's talk on how to use Linear Programming to solve or approximate TSP.
• Scott Aaronson's Ten reasons to believe that P!=NP.

Sample Midterm

• sample midterm and sample midterm.

Policies

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.