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. 1-2, Wed. 4-5, Thur. 3-4, Fri. 1-2 (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/26 Introduction; insertion sort Ch. 1, 2.1, 2.2
1/28 Asymptotic notation Ch. 3 HW1 due 2/4
1/30 Finish asymptotic notation; merge sort 2.3
2/2 Analyzing recurrences 4.3, 4.4
2/4 Finish recurrences; models of computation HW2 due 2/11
2/6 Elementary operations; homework review
2/9 Priority queues; heaps Ch. 6
2/11 Heap sort; quicksort HW3 due 2/18 Solutions
2/13 Quicksort; order statistics Ch. 7, 9.1-2
2/16 Worst-case linear time order statistics 9.3
2/18 Sorting lower bound; counting sort 8.1, 8.2
2/20 Radix sort; bucket sort 8.3, 8.4 Quiz 1 due 2/24
2/23 Dynamic sets 10.1, 10.2, 11.1
2/25 Quiz review; hash tables 11.2
2/27 Hash functions; open addressing 11.3, 11.4
3/2 Review for test HW4 due 3/11
3/4 Class canceled
3/6 Test
3/9 Binary search trees 12.1, 12.2
3/11 Binary search tree insert/delete; Red-black tree properties 12.3, 13.1
3/13 Test review; rotations 13.2 HW5 due 3/20
3/16 Red-black tree insert and delete 13.3, 13.4
3/18 Dynamic order statistics 14.1
3/20 Interval trees 14.3 Quiz 2 due 3/30
3/30 Quiz review; rod-cutting
4/1 Dynamic programming 15.1
4/3 Longest common subsequence 15.4 HW6: 15-4, 15-5, and 15-8 from book, due 4/10
4/6 Greedy algorithms; activity scheduling 16.1
4/8 Huffman codes 16.3
4/10 Graphs; breadth-first search; depth-first search 22.1-3 HW7 due 4/17
4/13 Minimum spanning trees; Kruskal's algorithm; Prim's algorithm 23.1-2
4/15 Bellman-Ford algorithm 24.1
4/17 Dijkstra's algorithm 24.3 Quiz 3 due 4/20
4/20 Floyd-Warshall algorithm 25.2
4/22 Maximum flow 26.1-2 HW7: 24.3-2, 24-3, and 26-4 from book, due 5/1
4/24 Bipartite matching 26.3