CSCI 382: Algorithms (Fall 2017)

Documents

• Syllabus
• POGIL roles
• Lecture notes from the previous semester. The lecture notes will not always match up perfectly with what we do in class, but you may find them to be a helpful resource.
• Induction exemplars
• 1D dynamic programming exemplar
• Final exam

Assignments

• HW 0 [ TeX ] : due Friday, August 25 @ 3pm

• HW 1 [ TeX ] : due Friday, September 1 @ 3pm

• HW 2 [ TeX ] : due Friday, September 8 @ 3pm

• HW 3 [ TeX ] : due Friday, September 15 @ 3pm
  Torn2PiecesSkeleton.java, torn2pieces-skeleton.py

• HW 4 [ TeX ] : due Friday, September 22 @ 3pm
  • 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
  • ALL GRAPHS IN ONE ARCHIVE: graphs.tar.gz

• HW 5 [ TeX ] : due Friday, October 6 @ 3pm

• HW 6 [ TeX ] : due Monday, October 16 @ 3pm

• HW 7 [ TeX ] : due Friday, October 27 @ 3pm

• HW 8 [ TeX ] : due Friday, November 3 @ 3pm

• HW 9 [ TeX ] : due Friday, November 17 @ 3pm

• HW 10 [ TeX ] : due Friday, December 1 @ 3pm

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

Activities/Lectures

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

Introduction to Algorithms

• W 23 Aug — introduction to POGIL, brute-force algorithms

• F 25 Aug — reasons for POGIL, GCD

• M 28 Aug — Proving algorithms correct (Euclidean algorithm)

• W 30 Aug — Asymptotic Analysis I (Big-O, Ω, Θ)

• F 1 Sep — Asymptotic Analysis II (limit theorems, proofs)

Graphs

• W 6 Sep — Graphs

• F 8 Sep — BFS (definitions, properties, asymptotics)
  K&T 3.2, 3.3

• M 11 Sep — BFS applications (bipartite)
  K&T 3.4, 3.5

• W 13 Sep — DAGs and topological sorting
  K&T 3.6

Greedy Algorithms

• F 15 Sep — topological sorting, intro to Dijkstra’s algorithm
  K&T 4.4

• M 18 Sep — no class

• W 20 Sep — Dijkstra’s algorithm
  K&T 4.4

• F 22 Sep — Dijkstra’s algorithm, minimum spanning trees
  K&T 4.5

• M 25 Sep — Implementing Kruskal’s MST algorithm, Union-find structure
  K&T 4.6

• W 27 Sep — Union-find K&T 4.6

Exam 1

• F 29 Sep — Exam 1

Divide and Conquer

• M 2 Oct — Intro to Divide & Conquer

• W 4 Oct — Finish intro activity; Karatsuba’s algorithm

• F 6 Oct — Median/select

Dynamic Programming

• M 9 Oct — Intro to dynamic programming

• W 11 Oct — DP example: hi/lo-stress jobs

• M 16 Oct — 2D dynamic programming

• W 18 Oct — More 2D dynamic programming

• F 20 Oct — Floyd-Warshall algorithm (all-pairs shortest paths with arbitrary weights + cycle detection)

Network flow (oops)

• M 23 Oct — Introduction to network flow

Amortized analysis

• W 25 Oct — Binary counters; accounting method

• F 27 Oct — Amortized analysis examples

• M 30 Oct — More examples; direct method

• W 1 Nov — Binomial heaps

Network flow

• F 3 Nov

• M 6 Nov

• W 8 Nov

Exam 2

• F 10 Nov — Exam 2