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, B13  
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 301, 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 110)  
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 117)  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

UnionFind  Chapter 21 slides  
23

11/20

Minimum Spanning Trees  Chapter 23 slides  
24

11/25

Quiz 2 (Cover Lectures 122)  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 281, 282 slides  
29

12/11

Matrix Operations and All Pair Shortest Paths I  Chapter 25 slides  HW6 is due 
Finally

Dec. 16th, 35 pm

FINAL (Cover ALL Lectures)  ALL Chapters  GOOD LUCK and THANKS FOR YOUR HARD WORK 