Comp 362 Honours Algorithm Design

Important Dates

• Homework 1 (Release date: Jan 19 - Due date: Feb 2)
• Homework 2 (Release date: Feb 2 - Due date: Feb 16)
• Midterm Feb 20 in class (Covers Flow Networks + Linear Programming)
• Homework 3 (Release date: Feb 16 - Due date: Mar 1)
• Homework 4 (Release date: Mar 11 - Due date: Mar 21)
• Homework 5 (Release date: Mar 22 - April 5)

Description

This course is an undergraduate course on advanced algorithmic techniques and applications. Topics include the following:

• Network Flows
• Linear programming
• Semi-definite programming
• Complexity and NP-completeness
• Approximation Algorithms
• Randomized Algorithms
• Fast Fourier Transform.

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.

Grading

Homework (30% = 5 x 6%). 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 30% + Midterm 20% + Final exam 50%) or (Homework 30% + Midterm 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, 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.

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 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.

• Your background is the most crucial factor in how you will do in this course. If you have a good understanding of logic and proof and have good problem-solving skills, you will do well in this course. If you lack these skills, it is better to postpone this course until you acquire them, but if you 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, consult more elementary books, find easy math problems, and 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 looking at the solution, searching the Internet, or discussing it with other students. Try your absolute hardest before giving up. If it doesn't work, look for some hints, and the last stage is to 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 most significant learning effect, and reading the solution to a problem has the most minor effect. Solving one complex problem is 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 sometimes indicate that the student cannot tell that their proof was incorrect. It happens very often that I see the students who understood the course better and solved the harder questions leave the answers to some difficult questions blank, as they are well aware that they were unable to solve that particular question. Because of this, high partial marks are only given to solutions that are correct but have some minor mistakes.

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.

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.