Comp 251 Algorithms and Data Structures

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

Description

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.

Grading

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.

Course Schedule

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

Assignments and exams

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.