Instructor |
Hamed Hatami | |

TA |
Shuonan Dong, Vincent Antaki, Zilun Peng, Jaspal Singh, Hossein Aboutalebi, Scott Fujimoto. TA's are only responsible for grading, and you should only contact them regarding the grading of your assignments and exams. | |

Prerequisite |
Comp 250 | |

Corequisite |
MATH 235 or MATH 240 or MATH 363. (This course relies on the material from MATH 240 or MATH 353). | |

Lecture |
Tuesday-Thursday 8:35-9:55 AM, Leacock Building 26. The lectures will be Video Recorded. | |

Outline |
course outline | |

Office hours |
Tuesday 2:00-3:00 pm 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. There is also a facebook group "COMP 251 Fall 2017" where you can post questions, and have discussions. | |

Textbook |
Jon Kleinberg and Eva Tardos, Algorithm Design, 2006. Official slides for the book can be found here |

This course is an undergraduate course on the design of algorithms and data structures. Topics include Basics of Algorithms Analysis, Greedy Algorithms, Divide and Conquer technique, Dynamic Programming, and Network Flows.

This is a rigorous course with an emphasis on mathematical proofs rather than implementations. Hence it is important that you are already familiar with the material covered in Math 240, Math 235, or Math 363.

*Homework (20% = 5 x 4%).* 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 through ** mycourses**. Your grades will be posted on mycourses.

*Late homeworks* can be submitted until 48 hours after the deadline. There will be a penalty of -25% for one-day delays, and -40% for two-day delays on late homeworks.

* Final grade* is whichever of (Homework 20% + Midterm 30% + final 50%) or (Homework 20% + Midterm 15% + final 65%) that results in a better grade. There will be two exams: a midterm in October and a final exam in December. The exams are closed-book, and closed-notes.

Lecture |
Topic |
Reading |

1(9/5) | Stable Matching | 1.1, slides |

2(9/7) | Finished Stable Matching, Some examples: Interval scheduling, weighted interval scheduling, independent set. | 1.1, 1.2, slides |

3(9/12) | Running time, Big-O notation | 2, slides |

4(9/14) | More asymptotic notation, Data structure for Stable matching | 2, slides |

5(9/19) | sick, no voice, no class. | |

6(9/21) | Graph algorithms. BFS. (Taught by Lianna) | 3 |

7(9/26) | Heap Data structure | 2 |

8(9/28) | BFS and DFS, bipartiteness, strong connectivity in digraphs | 3.3, 3.4, 3.5, slides |

9(10/3) | Strongly connected components in digraphs, topological ordering. (Taught by Lianna) | 3.6, slides |

10(10/5) | Greedy algorithms: Interval scheduling. (Taught by Lianna) | 4.1, 4.2, slides |

11(10/10) | Greedy algorithms: Interval Partitioning. Minimum Lateness. | 4.2, slides |

12(10/12) | Midterm. | |

13(10/17) | Optimal Caching | 4.3, slides |

14(10/19) | Shoretest Path in Graphs | 4.4, slides |

15(10/24) | Minimum Spanning Trees | 4.5, slides |

16(10/26) | Minimum Spanning Trees, Clustering | 4.7, slides |

17(10/31) | Huffman coding | 4.8, slides |

18(11/2) | Divide and Concquer: Merge Sort | 5.1, 5.3, slides |

19(11/7) | Divide and Concquer: Inversions, Closest Pair | 5.3, 5.4, slides |

20(11/9) | Divide and Concquer: Integer Multiplication, Fast Matrix Multiplication | 5.5 slides |

21(11/14) | Dynamic programming: Weighted interval scheduling, Knapsack problem | 6.1, 6.2, 6.4 slides |

22(11/16) | Dynamic programming: RNA secondary structure | 6.5 slides |

23(11/21) | Dynamic programming: Segment Alignment | 6.6 slides |

24(11/23) | Dynamic programming: Bellman-Ford (Shortest path), Negative cycles | 6.8,6.9,6.10 slides |

25(11/28) | Max-flow problem, Ford-Fulkerson Algorithm | 7.1 slides |

26(11/30) | Correctness of Ford-Fulkerson. Max-flow=Min-cut | 7.2 slides |

- Assignment 1, and Solution Due: 11:59pm, Sept 22.
- Assignment 2, and Solution Due: 11:59pm, Oct 13.
- Midterm. Oct 12.
- Assignment 3, and Solution Due: 11:59pm, Nov 3.
- Assignment 4, and Solution Due: 11:59pm, Nov 18.
- Assignment 5, and Solution Due: 11:59pm, Dec 3rd.
- Final exam.

- As I promised, the midterm grade is going to be curved: So here is the new scheme:
*Final grade*is whichever of (Homework 20% + (Midterm + 20) 30% + final 50%) or (Homework 20% + (Midterm + 20) 5% + final 75%) that results in a better grade. If your midterm grade is higher than 80, then add to this (midterm grade - 80) 15% - The final example covers the following topics:
- Big O notation
- Graph algorithms: DFS, BFS, strongly connected components, topological sort
- Greedy algorithms and Huffman Coding
- Divide and Conquer, analyzing the running time using Master Theorem
- Dynamic Programming, Bellman Ford

- Sample Final, and the solution. The actual final exam is easier, and has 8 questions.
- Office hours before the exam: Dec 4th (3:00-4:00), Dec 5th (2:00-3:00), Dec 7th (3:00-5:00), Dec 12th (1:00-5:00)

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