### Course Schedule (tentative)

Last revised on: 08/15/03 3:19 PM

Reading assignments are given according to the main text book (Cormen et al).

 Lec# Date Topic and/or Event Reading Notes 1 9/4 Class Organization       Class Webpage       Introduction and Readings (Guest Lecturer) Chapters 1, 2; Appendix A, B1-3 2 9/9 algorithms in the real world binary search Chapter 3; Appendix C slides HW1 is assigned 3 9/11 Divide and Conquer I:      Merge sort      Master Theorem Chapters 4, 7 slides 4 9/16 Randomized Algorithm I and Divide and Conquer II: (Guest Lecturer)      Quick Selection      Quicksort Chapters 5,7 slides 5 9/18 Divide and Conquer III:     Multiplication     Finding the closest pair of points Chapter 33.4; Problem 30-1, page 844 and slides of this lecture on multiplication slides HW 1 is due and HW2 is assigned 6 9/23 Sorting in linear time:      Radix sort      Bucket sort Chapter 8 slides 7 9/25 Greedy Algorithm I:      Huffman codes Chapter 16 slides 8 9/30 Greedy Algorithm II:      Scheduling and Selection      what are heuristics? Chapter 16 slides 9 10/2 Dynamic Programming I Chapter 15 slides HW2 is due and HW3 is assigned 10 10/7 Dynamic Programming II Chapter 15 slides 11 10/9 Hashing Chapter 11 slides 12 10/14 No Class 13 10/16 Quiz 1 (Cover Lectures 1-10) 14 10/21 Search Tree I Chapters 10, 12 slides HW3 is due and HW4 is assigned 15 10/23 Search Trees II Chapters 12, 13 slides 16 10/28 Search Tree III Chapters 13, 14 17 10/30 Graph Search Algorithm I:      BFS Chapter 22 slides 18 11/4 Graph Search Algorithm II:      DFS Chapter 22 slides 19 11/6 Midterm (Cover Lectures 1-17) Chapters all before 20 11/11 Graph Search Algorithm III Chapter 22 slides HW4 is due and HW5 is assigned; 21 11/13 DFS, DAG and Strongly Connected Components Chapter 21 slides 22 11/18 Union-Find Chapter 21 slides 23 11/20 Minimum Spanning Trees Chapter 23 slides 24 11/25 Quiz 2 (Cover Lectures 1-22) Chapters all before HW6 is assigned 25 11/27 No Class Happy Thanksgiving 26 12/2 Shortest Path I Chapter 24,25 slides HW5 is due 27 12/4 Shortest Path II Chapter 25 slides 28 12/9 Matrix Operations Chapter 28-1, 28-2 slides 29 12/11 Matrix Operations and All Pair Shortest Paths I Chapter 25 slides HW6 is due Finally Dec. 16th, 3--5 pm FINAL (Cover ALL Lectures) ALL Chapters GOOD LUCK and THANKS FOR YOUR HARD WORK