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