CSCI 280: Algorithms (Spring 2016)

Documents

• Syllabus

• Final exam

Assignments

• HW 0 [ TeX ] : due Friday, January 22 @ 4pm

• HW 1 [ TeX, hranks, sranks ] : due Friday, January 29 @ 4pm

• HW 2 [ TeX ] : due Friday, February 5 @ 4pm

• HW 3 [ TeX ] : due Friday, February 12 @ 4pm

• HW 4 : due Friday, February 19 @ 4pm
  • Demo: demo-dag.in | demo-dag.out | demo-cycle.in | demo-cycle.out
  • Checker script: check-graph.py
  • Tiny: graph-tiny-1.in | graph-tiny-2.in
  • Small: graph-small-1.in | graph-small-2.in
  • Medium: graph-med-1.in | graph-med-2.in
  • Big: graph-big-1.in | graph-big-2.in

• HW 5 [ TeX ] : due Friday, February 26 @ 4pm

• HW 6 [ TeX ] : due Friday, March 4 @ 4pm March 11 @ 4pm

• HW 6b [ TeX ] : due Friday, March 11 @ 4pm

• HW 7 [ TeX, justify, lorem.txt, neruda.tgz ] : due Friday, March 18 @ 4pm

• HW 8 [ TeX ] : due Friday, April 8 @ 4pm

• Week of April 8-15: no HW

• HW 10 [ TeX ] : due Friday, April 22 @ 4pm

• HW 11 [ TeX | Yices ] : due Friday, April 29 @ 4pm

• Optional bonus problems: due Tuesday, May 10 @ 4pm

Many of the assignments are gratefully based on materials from Brent Heeringa.

Lectures

Assigned readings are in italics. K&T refers to Algorithm Design by Kleinberg and Tardos.

Introduction to Algorithms

• W 20 Jan — Stable matchings and the Gale-Shapley algorithm
  K&T Ch. 1, including Solved Exercises

• F 22 Jan — snow day

• M 25 Jan — Proof of Gale-Shapley algorithm correctness

• W 27 Jan — Data representations for Gale-Shapley, largest sum subinterval
  K&T Ch. 2

• F 29 Jan — Largest sum subinterval, Asymptotic analysis I (definitions and facts)

• M 1 Feb — Asymptotic analysis II (Complexity zoo)

Graphs

• W 3 Feb — Graphs (representation, paths, cycles, trees)
  K&T 3.1

• F 5 Feb — BFS
  K&T 3.2, 3.3

• M 8 Feb — Bipartite graphs, directed graphs
  K&T 3.4, 3.5

• W 10 Feb — DAGs and topological sorting
  K&T 3.6

Greedy Algorithms

• F 12 Feb — Dijkstra’s Algorithm
  K&T 4.4

• W 17 Feb — Kruskal’s and Prim’s MST algorithms
  K&T 4.5

• F 19 Feb — Implementing Kruskal and Prim, Union-Find structure
  K&T 4.6

• M 22 Feb — Huffman coding
  K&T 4.8

Divide and Conquer

• W 24 Feb — Integer multiplication, Master Theorem
  K&T 5.1, 5.2, 5.5

• F 26 Feb — Matrix multiplication, FFT
  K&T 5.6

• M 29 Feb — FFT [ slides ]
  K&T 5.6

Dynamic Programming

• W 1 Mar — Intro to Dynamic Progragmming
  K&T 6.1, 6.2

• F 3 Mar — no class (SIGCSE)

• M 7 Mar — Matrix chain multiplication
  K&T 6.5

• W 9 Mar — Matrix chain, subset sum, knapsack [ Matrix chain code ]
  K&T 6.4

• F 11 Mar — Longest Common Subsequence

Network Flow

• M 14 Mar — Network flow I (definitions)
  K&T 7.1

• W 16 Mar — Network flow II (max flow/min cut theorem)
  K&T 7.2

• F 18 Mar — Network flow III (applications)
  K&T 7.5, 7.6

Amortized analysis

• M 28 Mar — Intro to amortized analysis. Aggregate method, accounting method

• W 30 Mar — Potential method, binomial trees

• F 1 Apr — no class (CCSC)

• M 4 Apr — Binomial heaps, splay trees

• W 6 Apr — Analysis of splay trees

Intractability

• F 8 Apr — Reductions
  K&T 8.1

• M 11 Apr — SAT, 3-SAT
  K&T 8.2

• W 13 Apr — NP, NP-completeness
  K&T 8.3

• F 15 Apr — CIRCUIT-SAT is NP-complete
  K&T 8.4

• M 18 Apr — Lots of things are NP-complete
  (3-SAT, SAT, independent set, vertex cover, set cover, travelling salesman, hamiltonian circuit)
  K&T 8.4, 8.5

Strings

• F 22 Apr — Rabin-Karp matching