text

Algorithms, by dasgupta,papadimitriou,vazirani isbn 9780073523408 website (with errata) more errata

course outline

week 1: CMPUT 204 review

collatz runtime for n a power of 2

big O

runtime ? two cases, depends whether input fits in one memory location

prologue

week 2: more 204 review

numeric algorithms (chap 1)

week 3: dynamic programming (chap 6)

knapsack (multiples version)

week 4: more DP

knapsack (no multiples), edit distance

paths in graphs (chap 4) dfs, bfs, single source shortest path: unweighted (bfs), weighted (Dijkstra), d.a.g. (topsort: dfs, reverse postorder)

week 5: more DP

sssp in dags, longest increasing subsequence, all-pairs shortest path, tsp, independent sets in trees

week 6: linear programming (chap 7)

intro, network flow, bipartite matching

week 7: more LP

duality, zero-sum games

week 8: NP-complete problems (chap 8)

search problems, np-c, cook's theorem

sample reduction rudratan path to sat

week 9: more NP-complete problems (chap 8)

week 10 (short due to fall break):

chromatic number, k-coloring

3-sat reduces to 3-coloring here

week 11-13 np-hard: now what?

last class Edmond's matching algorithm

assignments etc

extra