Specific references for each lecture are given in the lecture list. Three texts from which some of this material will be drawn are the following. None need to be purchased.
Introduction to Algorithms, Cormen, Leiserson,
Rivest, Stein Third Edition, MIT Press, 2009. This Book is available for free online here Algorithm Design Kleinberg and Tardos, Firat Edition, Pearson Education, 2006. Chapter 7 of this book will be made available
via MyCourses. In pursuit of the Travelling Salesman W. Cook, Princeton University Press, 2014. The relevant sections of this book will
be ade available online via MyCourses. Assessment: Assignments are to be emailed to the instructor.
The following elementary data structures and tier implementation: Arrays, Lists, Stacks, Queues, Trees.
Recursive Algorithms and their Analysis
Graphs and Graph Traversal Algorithms including
Breadth-first search, Depth first search, The shortest path algorithm of Dijkstra, Adjacency List data structure, Adjacency Matrix data structure.
Sorting and searching ordered lists: quicksort, mergesort, insertion sort and their worst case analysis.
Selection and Priority Queues(4 lectures) An Algorithm for 2-satisfiability(1 lecture) Graph Algortihsm(13 lectures) Red-Black trees(2 lecture) Data Compression(2 lecture) Instructor: Bruce Reed Teaching Assistant: Taha Ghassemi Midterm: in class February 21st
Final: 9-12 April 19
Last update:January 8 2018
There will be one midterm exam, in class on February 21st,
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%.
Late assignments will not be accepted or marked.
Assumed Background
Topics:
McConnell 301 breed@cs.mcgill.ca
Office Hours:Email for an appointment or ask a question via email
taha.ghassemi@mail.mcgill.ca
Office Hours:Tuesday and Thursday 10:30-11:30 in Trottier 3110