Journal: CS 25 Fall 2009
In the following, "CLRS" indicates readings from Introduction to Algorithms,
Third edition, by Cormen, Leiserson, Rivest, and Stein.
Week 2
- Wednesday, September 23:
- Course Syllabus discussed
- What is an algorithm?
- Thursday, September 24, X-hour:
- Examples to motivate algorithm design
- Reading: CLRS Chapters 1, 2
- Friday, September 25:
- Review of asymptotic notation
- Reading CLRS: Skim Chapter 3, Appendix A.
Week 2
- Monday, September 28:
- Proof that log n! = Theta(n logn)
- How recurrences arise in algorithms analysis: examples of MergeSort and Matrix Multiplication
- Master theorem with examples
- CLRS: Chapter 4.5
- Wednesday, September 30:
- Master theorem with examples
- Proof by induction of an exact recurrence
- CLRS: Chapter 4.3, 4.5
- Homework 1 given out.
- Thursday, October 1, X-hour:
- Substitution proofs
- Substitution proofs: strengthening induction hypothesis
- CLRS: Chapter 4.3
- Friday, October 2:
- Recursion trees
- Lower bound for comparison based sorting
- CLRS: Chapter 4.4, 8.1
Week 3
- Monday, October 5:
- Counting sort
- Radix Sort
- CLRS: Chapter 8.2, 8.3
- Wednesday, October 7:
- Radix Sort
- Partition algorithm (version done in class is finer than
the one in Section 7.1 of the book)
- Selection algorithm
- CLRS: 8.3, 7.1, 9.3
- Homework 2 out.
- Thursday, October 8, X-hour:
- Selection algorithm is completed
- CLRS: 9.3
- Friday, October 9:
- Review of Binary Search Trees
- CLRS: 12.1-12.3
Week 4
- Monday, October 12:
- Red-Black Trees
- CLRS: 13.1-13.2
- Wednesday, October 15:
- Insertion and Deletion in Redblack Trees
- CLRS: 13.3
- Homework 3 given out.
- Thursday, October 15, X-hour:
- Deletion in Red-Black Trees
- CLRS: 13.4
- Friday, October 16:
- Augmenting for order-statistics
- A general theorem for augmenting red-black trees
- CLRS: 14.1-14.2
Week 5
- Monday, October 19:
- A general theorem for augmenting red-black trees
- Interval trees
- CLRS: 14.2-14.3
- Wednesday, October 21:
- Dynamic Programming: Rod cutting
- CLRS: 15.1
- Homework 4 given out.
- Thursday, October 22, X-hour:
- Least Common Subsequence (LCS) Problem
- CLRS: 15.4
- Friday, October 23:
- Matrix chain multiplication problem
- CLRS: 15.2, 15.3
Week 6
- Monday, October 26:
- Matrix chain multiplication problem completed
- Activity selection problem: dynamic programming
- CLRS: 16.1
- Wednesday, October 28:
- Activity selection problem: dynamic programming completed
- Activity selection problem: greedy solution
- CLRS: 16.1
- Midterm (pdf file) given out.
- Thursday, October 29, X-hour
- Activity selection problem: greedy solution discussion
- Friday, October 30:
- Fractional and 0-1 Knapsack problem
- CLRS: 16.2
Week 7
- Monday, November 2
- Amortized Analysis: aggregate & accounting methods
- Applications to multi-stack and binary counter
- CLRS: 17.1-17.2
- Wednesday, November 4:
- Potential method: application to multi-stack and binary counter
- CLRS: 17.3
- HW 5 out.
- Thursday, November 6, X-hour:
- Potential method: Dynamic table that expands and contracts
- CLRS: Chapter 17.4
- Friday, November 7, X-hour
- Disjoint sets data structure
- CLRS: Chapter 21.2
Week 8
- Monday, November 9:
- Disjoint sets data structure (representation as a forest)
- CLRS: 21.3
- Wednesday, November 11:
- Representation of graphs
- breadth-first-search
- depth-first-search
- CLRS: 22.1-22.3
- HW 6 out.
- Thursday, November 12, X-hour
- depth-first search and its properties
- CLRS: 22.3
- Friday, November 13:
- Topological Sort
- CLRS: 22.4
Week 9
- Monday, November 16:
- Strongly connected components
- CLRS: 22.5
- Wednesday, November 18:
- Minimum spanning trees
- CLRS: B.5, 23.1
- HW 7, Part 1 out. Due Tuesday, November 24
- Thursday, November 19, X-hour:
- Kruskal's algorithm for MST
- Prim's algorithm for MST
- CLRS: 23.2
- Friday, November 20:
- Single Source Shortest Paths: Bellman-Ford Algorithm
- CLRS: 24.1