Information Structures

 308-610B              Winter 2016    McConnell 320   TR 8:30-10:00

return to:  course home page      also check:  announcements

Texts:

Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein

Linear Programming, Vasek Chvatal, W.H. Freeman, 1983 (this text will be made available online)
Chvatal is out of print but the appropriate sections will be provided to students.                               

Assessment:
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.


Assumed Background

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.


Topics: (tentative)

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  breed@cs.mcgill.ca Office Hours: Wednesday; 10:00-12:00

Professor Reed's office hours on March 23,30, and April 6th are cancelled, He will hold office hours from 10-12 on March 24th and April 7th, and be available for consultation by email the week of the 30th.

Midterm: in class March 8th 

Final: MC103 9-12 April 22nd 

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 12 2016