Introduction to Algorithms, Cormen, Leiserson, Rivest, SteinLinear Programming, Vasek Chvatal, W.H. Freeman, 1983 (this text will be made available online)
There will be one midterm exam, in class on march 8th, and a final exam in the exam period. There will be 4 or 5 homework assignments. The assignments will be worth 25% of the grade, the midterm 25%,and the final 50%.
Assignments are to be emailed to the instructor.
Late assignments will not be accepted or marked.
Lists, stacks, queues, trees, binary search trees, quicksort,
Discrete Probability definitions: Event, Probability, random variable, expected value, Bin(n,p). The inequalities of Markov and Chebyshev. Chernoff Bounds.
Graph: Vertex, edge, connected component, Breadth first search, Depth first search tree, The shortest path algorithm of Dijkstra, Floyd-Warshall all pairs shortest path algorithm. Adjacency list data structure, adjacency matrix.
Vague definition of NP-complete.
Selection and Priority Queues(2 lectures)
Solving Recurrence Relations(1 lecture)
An Algorithm for 2-satisfiability(1 lecture)
Probabilisitc Analysis of Binary Search Trees(2 lectures)
Graph Algortihsm(11 lectures)
Red-Black trees(1 lecture)
Data Compression(1 lecture)
Data Structures for Disjoint Sets(1 lecture)
Iterative Compression(2 lectures)
Instructor: Bruce Reed
McConnell 301 firstname.lastname@example.org Office Hours: Wednesday; 10:00-12:00
Midterm: in class March 8th
Final: MC103 9-12 April 22ndIn case you have not heard: 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 here for more information.)
Last update:January 12 2016