return to: course home page also check: announcements

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

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

Assignments are to be emailed to the instructor.

Late assignments will not be accepted or marked.

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

McConnell 301 breed@cs.mcgill.ca
Office Hours:Email for an appointment or ask a question via email

**Teaching Assistant: ** Taha Ghassemi

taha.ghassemi@mail.mcgill.ca
Office Hours:Tuesday and Thursday 10:30-11:30 in Trottier 3110

**Midterm:** in class February 21st

**Final:** 9-12 April 19

*Last update:January 8 2018*