This course is an introduction to the formal study of algorithms, a study which is a core part of almost every area of computer science. The course has two goals. The first is to introduce you to particular algorithms, and we'll discuss algorithms for a variety of foundational problems. The second is to introduce you to the tools needed to analyze algorithms and to techniques that are commonly used in their construction. These skills will let you begin to design and analyze algorithms of your own.

Textbook: Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein, 3rd ed.
Syllabus: Download here
Office hours: Mon., Wed., Fri. 3-4 in Library 390 (or by appointment)

The table below gives a rough idea of what we'll be covering when and associated textbook chapters. The topics covered each day are tentative. They can (and will!) change as some things take longer/shorter than expected. The textbook chapters associated with each topic are also meant only as a rough guide to where you can find the material. The fact that given chapters are listed does not mean we will cover every detail in those chapters, but rather that those chapters are where you can look if you want to see a review of the material or if you want to look over it ahead of time.

Date Topics Textbook Homework
1/25 Introduction; insertion sort Ch. 1, 2.1, 2.2
1/27 Asymptotic notation Ch. 3
1/29 HW1 due 2/5
2/1 Merge sort; recurrence relations; substitution method Ch. 2.3, 4.3
2/3 Recursion-tree method; max subarray Ch. 4.1, 4.4
2/5 Models of computation; elementary operations HW2 due 2/12
2/8 Priority queues; heaps; heapsort; start quicksort Ch. 6
2/10 Quicksort; average and worst-case order statistics Ch. 7, 9
2/12 Homework review; lower bounds on sorting Ch. 8.1 HW3 due 2/19
2/15 Counting sort; radix sort; bucket sort Ch. 8.2-4
2/17 Direct address tables; hash tables Ch. 11.1-3
2/19 Homework review; open addressing Ch. 11.4 Quiz 1 due 2/23
2/22 Binary search trees; in-order traversal; search Ch. 12.1-2
2/24 Binary search tree insert; delete; quiz review Ch. 12.3 HW4 due 2/29
2/26 AVL trees supplement
2/29 Augmenting data structures; dynamic order statistics Ch. 14.1-2 HW5 due 3/4
3/2 Interval trees Ch. 14.3
3/4 Review for midterm
3/7 Midterm
3/9 Midterm review HW6: 15-4, 15-5, and 15-8 from book, due 3/18
3/11 Rod cutting Ch. 15.1
3/14 Longest common subsequence Ch. 15.3-4
3/16 Activity scheduling; greedy algorithms Ch. 16.1-2
3/18 Homework review Quiz 2 due 3/28
3/28 Huffman codes Ch. 16.2-3 HW7 due 4/4
3/30 Graph representations; BFS Ch. 22.1-2
4/1 Quiz review
4/4 BFS finished; DFS Ch. 22.2-3 HW8 due 4/8
4/6 Minimum spanning trees; Kruskal's algorithm Ch. 23
4/8 Prim's algorithm Ch. 23.2 HW9 due 4/15
4/11 Shortest paths; Bellman-Ford algorithm; Dijkstra's algorithm Ch. 24.1, 24.3
4/13 Finish Dijkstra's; All-pairs shortest paths Ch. 25.1
4/15 Floyd-Warshall algorithm Ch. 25.2 Quiz 3 due 4/18
4/18 Maximum flow Ch. 26.1 HW10 due 4/29
4/20 Maximum flow cont. Ch. 26.1
4/22 Bipartite matching Ch. 26.2
4/25 Amortized analysis Ch. 17.1-4
4/27 Course wrap-up