CS 381: Material Covered and Reading Assignments

---

Friday, December 11
Review

Wednesday, December 9
Dealing with NP-complete problems; approximation algorithms: two algorithms for vertex vover
Reading: 35.1

Monday,  December  7
Reductions: scheduling within untervals; dealing with NP-complete problems
Reading:  34.4-5

Friday, December 4
Reductions: Clique
Reading: 34.4-5

Wednesday, December 2
NP-completeness: reductions, 3SAT,
Reading: 34.1-4

---

Monday, Nobember 30
Introduction to NP-completeness
Reading:  34.1-2, CACM paper posted on BB

Wednesday, November 25 + Friday November 27
Thanksgiving break - no class

Monday, November 23
Finish shortest paths; computability, classes P and NP
Reading: 25, 34

Friday, November 20
All pairs shortest paths algorithms 
Reading: 25

Wednesday, November 18
Single source shortest paths algorithms 
Reading:  24, BB

Monday, November 16
Finish strongly connected componentsm, introduction to shortest paths 
Reading: 24

Friday, November 13
Using DFS: biconnected components,  stronlgy connected components
Reading: 22

Wednesday, November 11
DFS on directed and undirected garphs, biconnected components
Reading:  22, BB

Monday, November 9
Graph traversals: BFS, topological search/sort
Reading: 22

Friday, November 6
Queries on augmented balanced tress
Reading: 14

Wednesday, November 4
Operations on RB-trees, augmenting balanced trees
Reading:  13, 14

Monday, November 2
Balanced Trees: Red-Black Trees
Reading: 13

---

Friday, October 30

Longest common subsequence; memoization

Reading:  15.3-4, BB

Wednesday, October 28

Dynamic Programming: Knapsack, Longest common subsequence

Reading:  15.3-4, BB

Monday, October 26

Dynamic Programming: Matrix-chain Product, Knapsack

Reading:  15.2, 15.3, BB

Friday, October 23

Dynamic Programming: Matrix-chain Product

Reading:  15.2, 15.3

Wednesday, October 21

Union-Find implementations

Reading: 21.1-3

Monday, October 19

Lecture by Professor Prabhakar: data structures and queries on spatial data

Reading: take notes

Friday, October 16

Greedy graph algorithms: Kruskal's algorithm 

Reading: 23

Wednesday, October 14

Return midterms; greedy graph algorithms: Prim's algorithm

Reading: 23

Monday, October 12

no class, October break

Friday, October 9

Introduction to graphs; minimum cost spanning trees

Reading: 23

Wednesday, October 7

Review for midterm

Monday, October 5

Greedy algorithms: fractional bin packing, Huffmann codes

Reading: BB, 16.3

Friday, October 2

Review of assignments 1-3

---

Wednesday , September  30

no class (makup-up for evening midterm)

Monday, September  28

Greedy algortirthms: 0/1 bin packing
Reading: 16.1-2; BB

Friday, September 25

Introduction to greedy algorithms; activity selection

Reading : 16.1-2

Wednesday, September 23

Lower bound for comparision-based sorting; sorting wothout comparisons

Reading: 8

Monday, September 21

Finish selection; lower bounds

Reading: 9.3, 8

Friday, September 18

Linear Time Selection (randomized, deterministic)
Reading: 9.1-3; MIT slides on BB

Wednesday, September 16

Celebrity problem

Reading: notes on BB

Monday, September 14

Hire Assistant Problem; Review of data structures; heaps as priority queue

Reading:: 5.1, parts of 5.3, 10

Friday, September 11

Probabilistic Analysis and Randomized Algorithms - an Overview

Reading: 5.1

Wednesday, September 9

Master Theorem; how to apply the three cases

Reading: 4.3, first two pages of 4.4

Monday, September 7

Labor Day - no class 

Friday, September 4

Solving recurrence relations. Master Theorem

Reading: 4.1-3; 

Wednesday, September 2

Designing algorithms for the Skyline problem. 
Reading: see http://acm.uva.es/p/v1/105.html  for the definition of the skyline problem; additional nortes on BB..

---

Monday, August 31
More on asymptotic notation: Theta and Omega. Complexity classes
Reading: 3.1, 3.2.

Friday, August 28
Asymptotic notation in algorithm design. Example of divide-and-conquer: Mergesort
Reading: 2.3, 3.1.

Wednesday, August 26
Performance of Insertion Sort. Review of mathematical induction. Important sums.
Reading: 2.2, Appendix A.1.

Monday, August 24
Course introduction, organization, and expectations. How could Insertion Sort insert?
Reading: Chapters 1, 2.1.

---