COMP-251: Data Structures and Algorithms

Fall 2007

Lecture contents and suggested readings, to be filled in as we go along:

Note that most, but not all, lecture material can be found in the course text (CLRS). Topics not covered in the text are italicized.

Lecture 1 (4 Sept. 2007):

Computational models (Turing machines, RAM, quantum circuits)

Loop invariants

Best-and worst-case analysis of insertion sort

Read chapters 1, 2, 3

Lecture 2 (6 Sept. 2007):

Divide-and-conquer recurrences

Recursion trees

Read chapter 4

Lecture 3 (11 Sept. 2007):

Solving recurrences by induction

Keep reading chapter 4!

You are not responsible for the proof of the full Master Theorem

Lecture 4 (13 Sept. 2007):

The Nerd’s Guide to Dating and Marriage(indicator random variables)

Read chapters 5.1, 5.2

Lecture 5 (18 Sept. 2007):

Quicksort: correctness, worst-case and expected running time

Chapter7

If you have forgotten about heaps and heapsort, read chapter 6

Lecture 6 (20 September 2007):

Medians and order statistics

Select in worst-case linear time

Read chapter 9

Lecture 7 (25 September 2007):

Decision tree lower bounds (sorting)

Adversary lower bounds (maximum; max and min)

Read chapter 8.1

Lecture 8 (27 September 2007):

Building a random permutation in linear time

Counting collisions (problem)

Read chapters 5.3, 5.4

Lecture 9 (2 October 2007):

Sorting in linear time

Read chapter 8.2, 8.3

Data structures – intro and review

Read chapter 10

Lecture 10 (9 October 2007):

Data structures – intro and review

Hash tables: hashing with chaining

Read chapters 10, 11.1, 11.2

Lecture 11 (11 October 2007):

Choosing a hash function

Fibonacci hashing

Universal hashing

Read chapter 11.3, 11.4

Lecture 12 (16 October 2007):

Problem day

See slides on Web CT

Lecture 13 (18 October 2007):

Midterm

Lecture 14 (23 October 2007):

Balanced search trees

Binary search tree / Quicksort connection

Treaps: Problem 13-4

B-trees: Chapter 18

Lecture 15 (25 October 2007):

Data structures for disjoint sets: union-find

Read 21.1-21.3

Lecture 16 (30 October 2007):

            Introduction to greedy algorithms

           Making change

           Fractional knapsack problem

Scheduling

I’m not super-enthusiastic about the book’s section on greedy algorithms, which doesn’t make much sense

If you don’t already understand dynamic programming. I therefore don’t recommend reading it at this point

But you’ll want to come back to it later in the semester.

Lecture 17 (1 November 2007):

Data structures for representing graphs

Minimum spanning tree (Kruskal and Prim)

Read chapters 22.1 and 23.

If graphs bewilder you, read Appendices B.4 and B.5.

Lecture 18 (6 November 2007):

Midterm plus recap on iterated logarithm

Huffman coding

Read chapter 16.3.

Lecture 18 (8 November 2007):

Breadth-first search as a shortest paths algorithm: Read 22.2

Single-source shortest paths (Dijkstra): Read 24.2-24.3

Lecture 19 (13 November 2007):

Intro to dynamic programming

Fibonacci, binomial coefficients, making change

Lecture 20 (15 November 2007):

All pairs shortest paths (Floyd-Warshall algorithm) (chapter 25.2)

Minimal perimeter triangulation of a convex polygon

Lecture 21 (20 November 2007):

Longest common subsequence (chapter 15.4)

Edit distance (variation on problem 15-3)

Independent set in trees

Lecture 22 (23 March 2006):

            Depth-first search revisited (chapter 22.3)

            Topological sort of a dag (chapter 22.4)

Lecture 23 (28 March 2006):

            Strongly connected components (chapter 22.5)

Lecture 24 (30 March 2006):

            Fast Fourier transform (chapters 30.1 and 30.2) (Not on exam)