Week 
Date

Topic(s)

Homework

Required reading(s)

01 
May 18,
Mon (Recitation)

 Introduction
 Topics covered
 HW, exam and grading policy
 Review : Recursion etc



No reading on 1st recitation.
Bring some questions like "How to do/find/decide/... ...?"
E.g.

How to find out the list of my friends' friends in Facebook/Orkut?

How to find the shortest path from my home to FA class?

How to decide whether our favorite Jewel thief can fool
the guards in the museum or not?


May 20,
Wed (Lecture)

 Big Oh notation etc
 Recurrence


 CLRS : 2.3 Designing algorithms
 CLRS : 3.1 Asymptotic notation
 CLRS : 3.2 Standard notations and common functions
 CLRS : 4.1 The substitution method
 CLRS : 4.2 The recursiontree method
 CLRS : 4.3 The master method

02 
May 25,
Mon (Recitation)

Memorial Day Holiday




May 27,
Wed (Lecture)

 Reduction among problems
 Subproblem(s) and recursion
 Divide and conquer
 Binary search
 Powering
 Fibonacci
 Strassen
 Proof of correctness by induction
 Some sorting algorithms
 Insertionsort
 Mergesort
 Quicksort

hw01.pdf assigned.


CLRS 7.4 Analysis of quicksort

CLRS 28.2 Strassen's algorithm for matrix multiplication

03  June 01, Mon (Recitation) 
 Growth of polynomial.
 Hints for HW01.


June 03,
Wed (Lecture)

 Introduction to graphs
 Maximizing the subgraph with minimum vertex degree
 BFS and DFS on graphs
 Binary heap


 CLRS 22.1: Representations of graphs
 CLRS 22.2: Breadthfirst search
 CLRS 22.3: Depthfirst search

04 
June 08,
Mon (Recitation)

Review : Heap

HW01 due.



June 10, Wed (Lecture) 
 Quiz on heap
 Shortest path algorithms on graph
 Linear time median finding

hw02.pdf assigned.

 CLRS : 6.1 Heaps
 CLRS : 6.2 Maintaining the heap property
 CLRS : 6.3 Building a heap
 CLRS : Part of Chapter 24 on Relaxation (Page 585  586)
 CLRS : 24.3 Dijkstra's algorithm
 CLRS 9.3 Selection in worstcase linear time

05  June 15, Mon (Recitation) 



 June 17, Wed (Lecture) 
 quiz on B.F.S., D.F.S., Dijkstra's
 Prim's algorithm for M.S.T.
 Count sort
 Radix sort
 Heapsort
 Big Oh and &le


 CLRS 23.2: The algorithms
of Kruskal and Prim
 CLRS 8.2: Counting sort
 CLRS 8.3: Radix sort
 CLRS 6.4: The heapsort algorithm

06  June 22, Mon (Recitation) 
Midterm week starts
 Disjointset forests
 Hash table as a black box


 CLRS 21.3: Disjointset forests

 June 24, Wed (Lecture) 
 Dynamic programming
 Matrixchain multiplication
 Longest common subsequence
 All pair shortest path (The FloydWarshall algorithm)
 M.S.T. using Kruskal's algorithm
 Single source shortest path with negative edge weight
(The BellmanFord algorithm)
 Bit flips in binary counter


 CLRS 15.2: Matrixchain multiplication
 CLRS 15.4: Longest common subsequence
 CLRS 25.2: The FloydWarshall algorithm
 CLRS 23.2: The algorithms of Kruskal
and Prim
 CLRS 24.1: The BellmanFord algorithm

07  June 29, Mon (Recitation) 
 Amortized Analysis
 Incrementing a binary counter
 Stack operations


 CLRS 17.3 The potential method

 July 01, Wed (Lecture) 
 More examples of dynamic programming


 CLRS: Problems 154: Planning a company party
 CLRS: Problems 156: Moving on a checkerboard
 CLRS: Problems 157: Scheduling to maximize profit

08  July 06, Mon (Recitation) 
 Some more examples of dynamic programming
 Reduction revisited
 Longest path in a D.A.G.


 CLRS: Problems 157: Scheduling to maximize profit
 CLRS: Exercises 15.45

 July 08, Wed (Lecture) 
 RedBlack Trees
 Augmenting Data Structures
 BTrees
 Maximum flow in a graph


 CLRS: 13: RedBlack Trees
 CLRS: 14: Augmenting Data Structures
 CLRS: 18: BTrees
 CLRS: Chapter 26: Maximum Flow

09  July 13, Mon (Recitation) 
 Solutions for hw03
 Problems : Augmenting Data Structures
 Exercises 14.17
 Exercises 14.21



 July 15, Wed (Lecture) 
 max flow (continued)
 234 trees
 Greedy algorithms
 Lower bound for sorting
 Topological sorting
 Driving and gas stations

hw04.pdf assigned.

 CLRS 16.3: Huffman codes
 CLRS 8.1: Lower bounds for sorting
 CLRS 22.4: Topological sort

10  July 20, Mon (Recitation) 



 July 22, Wed (Lecture) 
 Strongly connected component


 CLRS 16.1: An activityselection problem
 CLRS 16.2: Elements of the greedy strategy
 CLRS 22.5: Strongly connected components

11  July 27, Mon (Recitation) 



 July 29, Wed (Lecture) 
 Introduction to Decidability (not in Final)
 Flow in graph
 Bipartite matching
 NPcompleteness


 CLRS 26.1: Flow networks
 CLRS 26.2: The FordFulkerson method
 CLRS 26.3: Maximum bipartite matching
 CLRS 34.3 NPcompleteness and reducibility
 CLRS 34.5 NPcomplete problems

12  Aug 03, Mon (Recitation) 



 Aug 05, Wed 
Final exam
