CSCI 280: Algorithms (Spring 2017)

Documents

• Syllabus
• LECTURE NOTES

Assignments

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

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

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

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

• HW 4 [ TeX ] : due Friday, February 17 @ 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, March 3 @ 4pm

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

• HW 7 [ TeX, lorem.txt, neruda.tar ] : due Friday, March 17 @ 4pm

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

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

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

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

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

Lectures

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

LECTURE NOTES PDF

Introduction to Algorithms

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

• F 20 Jan — Proof of Gale-Shapley algorithm correctness

• M 23 Jan — Data representations for Gale-Shapley
  K&T Ch. 2

• W 25 Jan — Asymptotic analysis

• F 27 Jan — Asymptotic analysis II (Complexity zoo)

• M 30 Jan — Largest sum subinterval problem

Graphs

• W 1 Feb — More LSS, intro to graphs (representation, paths, cycles, trees)
  K&T 3.1

• F 3 Feb — BFS (definitions, properties, asymptotics)
  K&T 3.2, 3.3

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

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

Greedy Algorithms

• F 10 Feb, M 13 Feb — Dijkstra’s Algorithm
  K&T 4.4

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

• F 17 Feb — Implementing Prim’s algorithm
  K&T 4.6

• W 22 Feb — Implementing Kruskal’s algorithm, Union-Find structure
  K&T 4.6

Exam 1

• F 24 Feb — Exam 1
  Covering asymptotic analysis, graphs, and greedy algorithms

Divide and Conquer

• M 27 Feb — Integer multiplication, Master Theorem
  K&T 5.1, 5.2, 5.5

• W 1 Mar — Matrix multiplication, FFT intro
  K&T 5.6

• F 3 Mar — FFT [ slides ]
  K&T 5.6

Dynamic Programming

• M 6 Mar — Intro to Dynamic Progragmming (Fibonacci, hi/lo stress jobs)
  K&T 6.1, 6.2

• W 8 Mar — Matrix chain multiplication (MatrixChainFull.java)
  K&T 6.5

• F 10 Mar — Floyd-Warshall algorithm
  K&T 6.8

Network Flow

• M 13 Mar — Network flow I (definitions, Ford-Fulkerson algorithm)
  K&T 7.1

• W 15 Mar — Network flow II (F-F algo examples, flows and cuts)
  K&T 7.2

• F 17 Mar — Network flow III (max flow/min cut theorem)
  K&T 7.5, 7.6

Spring break

Amortized analysis

• M 27 Mar — Intro to amortized analysis. Direct counting method.

• W 29 Mar — More amortized analysis. Accounting method.

• F 31 Mar — Binomial trees and heaps

• M 3 Apr — Potential method, splay trees

• W 5 Apr — Analysis of splay trees

Exam 2

• F 7 Apr — Exam 2
  Covering divide & conquer, dynamic programming, network flow, and amortized analysis (through 29 March)

Intractability

• M 10 Apr — Reductions
  K&T 8.1

• W 12 Apr — Reductions, decision problems

• F 14 Apr — SAT, 3-SAT
  K&T 8.2

• M 17 Apr — NP, NP-completeness
  K&T 8.3

• W 19 Apr — CIRCUIT-SAT is NP-complete
  K&T 8.4

• F 21 Apr — special guest lecture

Strings, matching, and linear sorting

• M 24 Apr — Rabin-Karp matching

• W 26 Apr — Rabin-Karp matching, bucket sort

• F 28 Apr — radix sort

• M 1 May — radix sort

Final exam

• M 8 May — Final exam (Cumulative)