Administrivia. Introduction: models of computation, algorithms. Insertion sort, mergesort and their analysis. Reading: Chapters 1, 2.

Lecture 1 Slides

O-notation, growth of functions. Divide and conquer, recurrences.

Reading: Chapters 3, 4.

Lecture 2 Slides

[No class – Martin Luther King day holiday]

More on recurrences, the master theorem. Reading: Chapters 4, 5.

Homework 1 out.

Lecture 3 Slides

Probabilistic analysis, randomized algorithms. Quicksort and randomized quicksort. Reading: Chapter 7.

Lecture 4 Slides

Selection: medians, order statistics. Reading: Chapter 9.

Homework 1 due. Homework 2 out.

Lecture 5 Slides

Sorting: heapsort, priority queues. Reading: Chapter 6.

Lecture 6 Slides

Sorting: lower bounds, counting sort, radix sort. Reading: Chapter 8.

Homework 2 due. Homework 3 out.

Lecture 7 Slides

Data structures: hashing, collision resolution, chaining, universal hashing, open addressing. Reading: Chapter 11.

[Guest Lecture: Greg Valiant]

Lecture 8 Slides

Notes from Prof. Valiant

Data structures: binary search trees, tree walks, relation to quicksort. Reading: Chapter 12.

[Guest Lecture: Mary Wootters]

Homework 3 due. Homework 4 out.

Lecture 9 Slides

Data structures: red-black trees, rotations, insertion, deletion. Reading: Chapter 13.

Lecture 10 Slides

Dynamic programming: shortest paths; longest common subsequence; martrix products. Reading: Chapter 15.

Homework 4 due. Homework 5 out.

Lecture 11 Slides

[No class – President day holiday]

Augmenting data structures: dynamic order statistics, interval trees. Amortized analysis: the accounting and potential methods. Reading: Chapter 15, 17.

Homework 5 due. Programming project out.

Lecture 12 Slides

Midterm examination, in class, closed book.

Introduction to graph algorithms: representation, breadth first search, depth first search, topological sort. Reading: Chapter 22.

Homework 6 out.

Lecture 13 Slides

Graph algorithms: minimum spanning tree algorithms, Prim's algorithm, Kruskal's algorithm. Reading: Chapter 22, 23.

Lecture 14 Slides

Graph algorithms: Single-source shortest paths, Dijkstra's algorithm, Bellman-Ford Algorithm, difference constraints. Reading: Chapter 24.

Homework 6 due.

Lecture 15 Slides

Graph algorithms: all-pairs shortest paths, matrix multiplication, Floyd-Warshall algorithm. Reading: Chapter 25.

Lecture 16 Slides

Class summary.

Programming project due.

All course work is due by this date.