Last revised on: 1/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

1/14

Learning Algorithms by Examples Guest Lecturer Professor Gene Itkis 
Chapters 1, 2; Appendix A, B13  
2

1/16

Administrivia algorithms in the real world binary search 
Chapter 3; Appendix C slides 
HW1 is assigned 
3

1/21

Divide and Conquer I:
Merge sort Master Theorem 
Chapters 4, 7 slides 

4

1/23

Randomized Algorithm I and Divide and Conquer II:
Quick Selection Quicksort 
Chapters 5,7 slides 
HW 1 is due and HW2 is assigned 
5

1/28

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 

6

1/30

Sorting in linear time: Radix sort Bucket sort 
Chapter 8 slides 

7

2/04

Greedy Algorithm I: Huffman codes 
Chapter 16 slides 

8

2/06

Greedy Algorithm II: Scheduling and Selection what are heuristics? 
Chapter 16
slides 
HW 2 is due and HW3 is assigned 
8

2/11

Dynamic Programming I 
Chapter 15
slides 

10

2/13

Dynamic Programming II
Guest Lecturer: Benjamin Hescott 
Chapter 15 slides 
Friday, February 14, 2003 is the without getting a W 
11

2/18

No Class 
Tuesday with Monday's Schedule  
12

2/20

Hashing  Chapter 11; slides 
HW3 is due and HW4 is assigned 
13

2/25

Quiz (Cover Lectures 110)  HW4 is assigned;  
14

2/27

Search Tree I  Chapters 10, 12 slides  
15

3/4

Search Trees II  Chapters 12, 13 slides  
16

3/6

Search Tree III: Guest lecture by Professor Steve Homerb  Chapters 13, 14 (no slides)  HW4 is due and HW5 is
assigned; 
17

3/11

No Class 
Spring Break  
18

3/13

No Class 
Spring Break  
19

3/18

Graph Search Algorithm I:S BFS 
Chapter 22 slides  
20

3/20

Graph Search Algorithm II: DFS 
Chapter 22 slides 

21

3/25

DFS, DAG and Strongly Connected Components  Chapter 21 slides 

22

3/27

UnionFind  Chapter 21 slides  HW5 is due and HW6 is assigned 
23

4/1

Minimum Spanning Trees  Chapter 23 slides  
24

4/3

Midterm (Cover Lectures 122)  Chapters all before  
25

4/8

Shortest Path I  Chapter 24,25 slides  
26

4/10 
Midterm and Quiz reviewing  Chapter 25  HW6 is due and HW7 is assigned 
27

4/15

Shortest Path II  Chapter 25 slides  
28

4/17

Matrix Operations  Chapter 281, 282 slides  
29

4/22

Matrix Operations and All Pair Shortest Paths I  Chapter 25 slides  
30

4/24
 Stable Marriage Problem 


31

4/29

Approximation Algorithms: Travelingsalesman problem 
Chapter 35.2  
32

5/01

Algorithm for the New Age: What to learn next?
Complexity Cryptography Parallel Algorithms Randomized Algorithms Approximation Algorithm OnLine Algorithms Mathematical Programming Computational Geometry Numerical Algorithms Algorithms in the real world smoothed analysis 
HW7 is due  
Finally

May 8 Thursday
9:0011:00 am in Room MCS 148. 
FINAL (Cover ALL Lectures)  ALL Chapters  GOOD LUCK and THANKS FOR YOUR HARD WORK 