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