prof hayward     cmput 304 homepage     fall 2014

text

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

course outline
  • week 1: CMPUT 204 review

  • 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)

  • 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