Week 
Date

Topic(s)

Homework

Required reading(s)

01 
May 19,
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 21,
Wed (Lecture)

 Big Oh notation etc
 Recurrence

hw01.txt assigned.
hw01soln.pdf .

 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 26,
Mon (Recitation)

No meeting.
Enjoy Memorial Day holiday.




May 28,
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
 Linear time median finding

HW01 due.
hw02.pdf assigned.
hw02soln.pdf .


CLRS 7.4 Analysis of quicksort

CLRS 28.2 Strassen's algorithm for matrix multiplication

CLRS 9.3 Selection in worstcase linear time

03  June 02, Mon (Recitation) 
 Review (hw01): Growth of polynomial.
 Hints for HW02.


June 04,
Wed (Lecture)

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

HW02 due.

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

04 
June 09,
Mon (Recitation)

Review : Heap




June 11, Wed (Lecture) 
 Quiz on heap
 Shortest path algorithms on graph


 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

05  June 16, Mon (Recitation) 

hw03.pdf assigned. 

 June 18, 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 23, Mon (Recitation) 
Midterm week starts
 Disjointset forests
 Hash table as a black box


 CLRS 21.3: Disjointset forests

 June 25, 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 30, Mon (Recitation) 
 Amortized Analysis
 Incrementing a binary counter
 Stack operations


 CLRS 17.3 The potential method

 July 02, 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 07, 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 09, Wed (Lecture) 
 RedBlack Trees
 Augmenting Data Structures
 BTrees

hw04.pdf assigned. 
 CLRS: 13.1: Properties of redblack trees
 CLRS: 13.2: Rotations
 CLRS: 13.3: Insertion
 CLRS: 14.1: Dynamic order statistics
 CLRS: 18.1: Definition of Btrees

09  July 14, Mon (Recitation) 
 Hints for hw04
 Problems : Augmenting Data Structures
 Exercises 14.17
 Exercises 14.21



 July 16, Wed (Lecture) 
 RedBlack Trees(continued)
 Augmenting Data Structures(continued)
 BTrees(continued)


 CLRS: 13.4: Deletion(RB tree)
 CLRS: 14.2: How to Augment a Data Structure
 CLRS: 14.3: Interval Trees
 CLRS: 18.2: Basic operations on Btrees
 CLRS: 18.3: Deleting a key from a Btree

10  July 21, Mon (Recitation) 



 July 23, Wed (Lecture) 
 Greedy algorithms
 Lower bound for sorting
 Topological sorting
 Strongly connected component


 CLRS 16.1: An activityselection problem
 CLRS 16.2: Elements of the greedy strategy
 CLRS 16.3: Huffman codes
 CLRS 8.1: Lower bounds for sorting
 CLRS 22.4: Topological sort
 CLRS22.5: Strongly connected components

11  July 28, Mon (Recitation) 



 July 30, 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 04, Mon (Recitation) 



 Aug 06, Wed 
Final exam
