Information Structures

 COMP610      Winter 2018   McConnell 103   MW 8:30-10:00

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.


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.

Assumed Background

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 Office Hours:Email for an appointment or ask a question via email

Teaching Assistant:  Taha Ghassemi Office Hours:Tuesday and Thursday 10:30-11:30 in Trottier 3110

Midterm: in class February 21st 

Final: 9-12 April 19  

In 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 8 2018