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)