|
Date |
Topic |
Reading (in the book/handout) |
Sep 1 |
General overview; Stable marriage problem |
Chapter 1 |
Sep 6 |
Stable marriage problem, proof of optimality; Graphs, Representation of graphs |
Chapter 1 |
Sep 8 |
DFS, Order notation, BFS, Top sort |
Chapter 2-3 |
Sep 13 |
Top sort, Directed DFS |
Chapter 2-3 |
Sep 15 |
Cut nodes |
Biconnected Components
Biconnected Components Algorithm |
Sep 20 |
Strong connectivity and strong components |
Chapter 22.5 from CLRS |
Sep 22 |
Minimum Spanning Tree, basic MST proofs of correctness
Kruscal algorithm for MST |
Chapter 4 |
Sep 27 |
MST finished
Heaps
Prim's algoritm
Finding maximum collection of disjoint intervals |
Section 4.1 |
Sep 29 |
Amortized analysis
UNION-FIND data structure
Interval graph coloring |
Chapter 17 from CLRS
Chapter 4.1 |
Oct 4 |
Huffman coding |
Chapter 4 |
Oct 6 |
QUIZ: 45 minutes in class; closed notes, books, etc.
AVERAGE: 64.84 |
|
Oct 11 |
Dijkestra Algorithm
Bellman-Ford Algorithm |
Chapter 4.4
from CLRS
|
Oct 13 |
Solving quiz problems
Dynamic Programming algorithm for KNAPSACK |
|
Oct 18 |
Toothpick game
| Chapter 6.1
Toothpick game
|
Oct 20 |
Practice problems for midterm exam
Singly connected graphs |
Singly connected graphs
|
Oct 25 |
MIDTERM
AVERAGE: 60.33 |
|
Oct 27 |
Midterm discussion
|
Chapter 6.3
|
Nov 1 |
Dynamic Programming
Exercise 1 and 2 (solved exercises from book)
Line fitting problem
|
Chapter 6.3 |
Nov 3 |
Homework 5 discussion
Dynamic Programming
Sequence alignment
|
Chapter 6.6
|
Nov 8 |
2 algorithms for all pairs shortest paths:
First one from the book;
Second one Floyd Warshall |
Chapter 6
|
Nov 10 |
Divide and conquer closest pair algorithm |
Chapter 5
|
Nov 15 |
Randomized and deterministic SELECTION (median finding) algorithms |
|
Nov 17 |
Devide and Conquer:
Long number multiplication;
Counting inversions
|
Chapter 5 |
Nov 22 |
NP-Completeness |
NP-Completeness
|
Nov 29 |
Review of NP-Completeness
Reduction from Independent Set to Vertex Cover problem
Reduction from 3SAT to Independent Set problem
Introduction to Dominating Set problem |
Chapter 8
|
Dec 1 |
Reduction from 3SAT to SUBSET SUM problem
|
Section 34.5.5 from CLRS
|
Dec 6 |
Reduction from SUBSET SUM to PARTITION problem
Reduction from PARTITION to Scheduling with release time/deadline
Reduction from Hamiltonian Cycle to Hamiltonian Path problem
|
|
Dec 8 |
Reduction from Vertex Cover to Dominating Set problem
|
|