M, Jan 13: Introduction; Insertion sort; algorithm analysis. (Chapters 1, 2)

W, Jan 15: Growth of functions; asymptotic analysis. (Chapter 3)

M, Jan 20: NO CLASS (MLK DAY)

W, Jan 22: Merge sort; divide-and-conquer; recurrence relations. (Chapters 2,4) HW1 OUT

M, Jan 27: Recurrences and summations. (Chapter 4, Appendix A)

W, Jan 29: Randomized algorithms. (Chapter 5, Appendix C) HW1 IN

M, Feb 3: Randomized algorithms. (Chapter 5, Appendix C) HW2 OUT

W, Feb 5: Quicksort; randomized Quicksort. (Chapter 7)

M, Feb 10: Heapsort; priority queue. (Appendix B.5, Chapter 6)

W, Feb 12: Lower bound for comparison-based sorting; integer and radix sort. (Chapter 8) HW2 IN

M, Feb 17: Selection (order statistics). (Chapter 9) HW3 OUT

W, Feb 19: Elementary data structures; hashing. (Chapters 10, 11)

M, Feb 24: Hashing (continued). (Chapter 11)

W, Feb 26: Binary search trees; red-black tree. (Chapters 12, 13) HW 3 IN

M, Mar 3: Augmenting data structures. (Chapter 14)

W, Mar 5: IN-CLASS TEST

M, Mar 10: SPRING BREAK

W, Mar 12: SPRING BREAK

M, Mar 17: Hand out test. Amortized analysis. (Chapter 17)

W, Mar 19: Amortized analysis (continued)

M, Mar 24: Disjoint sets; graph representation. (Chapter 21, Appendix B.4) HW4 OUT

W, Mar 26: Greedy algorithms and dynamic programming. (Chapters 15 and 16)

M, Mar 31: Greedy algorithms and dynamic programming. (Chapters 15 and 16)

W, Apr 2: BFS, DFS (chapter 22) HW4 IN

M, Apr 7: Minimum spanning tree. (Chapter 23)

W, Apr 9: Single-source shortest paths. (Chapter 24) TAKE-HOME TEST OUT

M, Apr 14: All-pairs shortest paths. (Chapter 25) TAKE-HOME TEST IN

W, Apr 16: Linear programming (Chapter 29)

M, Apr 21: P, NP, verification algorithms. (Chapter 34) HW5 OUT

W, Apr 23: NP-completeness (Chapter 34)

M, Apr 28: Approximation algorithms for NP-hard problems. (Chapter 35)

W, Apr 30: Wrap up. HW5 IN

W, MAY 7, 2-5 p.m. FINAL EXAM in WEL 2.256

This is a tentative schedule and is subject to change beyond today's date.