Lectures - CSCI 570, Fall 2013, Both Sections

• Lecture 1 (PDF) (6-up PDF) (Aug 27, 2013) - administrative
• Lecture 2 (PDF) (6-up PDF) (Aug 29, 2013) - introduction, (K&T 1.1, 2.3) first problem: stable matching
• Lecture 3 (PDF) (6-up PDF) (Sep 3, 2013) - (K&T 1.1, 2.3) first problem: stable matching
• Lecture 4 (PDF) (6-up PDF) (Sep 5, 2013) - (K&T 1.1, 2.3) first problem: stable matching
• Lecture 5 (PDF) (6-up PDF) (Sep 10, 2013) - (K&T 1.1, 2.3) first problem: stable matching, (K&T 1.2) five representative problems
• Lecture 6 (PDF) (6-up PDF) (Sep 12, 2013) - (K&T 1.2) five representative problems, (K&T 2.1, 2.2, 2.4) algorithm analysis
• Lecture 7 (PDF) (6-up PDF) (Sep 17, 2013) - (K&T 2.1, 2.2, 2.4) algorithm analysis, (K&T 2.5) priority queues
• Lecture 8 (PDF) (6-up PDF) (Sep 19, 2013) - (K&T 2.5) priority queues, (K&T 3.1-3.6) graphs
• Lecture 9 (PDF) (6-up PDF) (Sep 24, 2013) - (K&T 3.1-3.6) graphs
• Lecture 10 (PDF) (6-up PDF) (Sep 26, 2013) - (K&T 3.1-3.6) graphs
• Lecture 11 (PDF) (6-up PDF) (Oct 1, 2013) - notes on exams, (K&T 4.1-4.3) greedy algorithms basics
• Lecture 12 (PDF) (6-up PDF) (Oct 3, 2013) - (K&T 4.1-4.3) greedy algorithms basics
• Lecture 13 (PDF) (6-up PDF) (Oct 8, 2013) - (K&T 4.1-4.3) greedy algorithms basics, (K&T 4.4) shortest path algorithms
• (Oct 10, 2013) - midterm #1
• Lecture 14 (PDF) (6-up PDF) (Oct 15, 2013) - (K&T 4.4) shortest path algorithms, coin changing, selecting breakpoints, (K&T 4.5-4.7) minimum spanning tree
• Lecture 15 (PDF) (6-up PDF) (Oct 17, 2013) - (K&T 4.5-4.7) minimum spanning tree, clustering, (K&T 4.8) huffman codes and data compression
• Lecture 16 (PDF) (6-up PDF) (Oct 22, 2013) - (K&T 4.8) huffman codes and data compression, (K&T 5.1-5.3) divide & conquer basics
• Lecture 17 (PDF) (6-up PDF) (Oct 24, 2013) - (K&T 5.1-5.3) divide & conquer basics, (K&T 5.4, 5.5) closest pair of points
• Lecture 18 (PDF) (6-up PDF) (Oct 29, 2013) - (K&T 5.4, 5.5) integer multiplication, (K&T 5.6) convolution, FFT
• Lecture 19 (PDF) (6-up PDF) (Oct 31, 2013) - (K&T 6.1-6.5) dynamic programming basics
• Lecture 20 (PDF) (6-up PDF) (Nov 5, 2013) - (K&T 6.1-6.5) dynamic programming basics
• Lecture 21 (PDF) (6-up PDF) (Nov 7, 2013) - (K&T 6.1-6.5) dynamic programming basics, (K&T 6.6-6.10) sequence alignment
• Lecture 22 (PDF) (6-up PDF) (Nov 12, 2013) - (K&T 6.6-6.10) sequence alignment, Bellman-Ford algorithm, (K&T 7.1-7.3) network flow basics
• (Nov 14, 2013) - midterm #2 (firm)
• Lecture 23 (PDF) (6-up PDF) (Nov 19, 2013) - (K&T 7.1-7.3) network flow basics
• Lecture 24 (PDF) (6-up PDF) (Nov 21, 2013) - (K&T 7.1-7.3) network flow basics
• Lecture 25 (PDF) (6-up PDF) (Nov 26, 2013) - (K&T 7.5-7.12) application of network flows
• (Nov 28, 2013) - Thanksgiving holiday
• Lecture 26 (PDF) (6-up PDF) (Dec 3, 2013) - (K&T 7.5-7.12) application of network flows
• Lecture 27 (PDF) (6-up PDF) (Dec 5, 2013) - (K&T 7.5-7.12) application of network flows

Preview:

• (AM section) (Dec 12, 2013) - final exam (firm)
  (PM section) (Dec 17, 2013) - final exam (firm)

• Administrative
  • course administration (PDF) (6-up PDF)
  • housekeeping (PDF) (6-up PDF)
  • notes on exams (PDF) (6-up PDF)

• Course Introduction (PDF) (6-up PDF)

• Stable Matching
  • (K&T 1.1, 2.3) first problem: stable matching (PDF) (6-up PDF)
  • (K&T 1.2) five representative problems (PDF) (6-up PDF)

• Basics of Algorithm Analysis
  • (K&T 2.1, 2.2, 2.4) algorithm analysis (PDF) (6-up PDF)
  • (K&T 2.5) priority queues (PDF) (6-up PDF)

• Graphs (K&T 3.1-3.6) (PDF) (6-up PDF)

• Greedy Algorithms
  • (K&T 4.1-4.3) greedy algorithms basics (PDF) (6-up PDF) - interval scheduling, scheduling to minimize lateness, optimal caching
  • (K&T 4.4) shortest path algorithms, coin changing, selecting breakpoints (PDF) (6-up PDF)
  • (K&T 4.5-4.7) minimum spanning tree, clustering (PDF) (6-up PDF)
  • (K&T 4.8) huffman codes and data compression (PDF) (6-up PDF)

• Divide and Conquer
  • (K&T 5.1-5.3) divide & conquer basics (PDF) (6-up PDF) - mergesort, counting inversions
  • (K&T 5.4, 5.5) closest pair of points, integer multiplication (PDF) (6-up PDF)
  • (K&T 5.6) convolution, FFT (PDF) (6-up PDF)

• Dynamic Programming
  • (K&T 6.1-6.5) dynamic programming basics (PDF) (6-up PDF) - weighted interval scheduling, segmented least squares, knapsack, RNA secondary structure
  • (K&T 6.6-6.10) sequence alignment, Bellman-Ford algorithm (PDF) (6-up PDF)

• Network Flow
  • (K&T 7.1-7.3) network flow basics (PDF) (6-up PDF) - max flow, min cut, Ford-Fulkerson algorithm, capacity scaling
  • (K&T 7.5-7.12) application of network flows (PDF) (6-up PDF) - bipartite matching, disjoint paths, circulation with demands, survey design, airline scheduling, image segmentation, project selection, baseball elimination

• NP & Computational Intractability
  • (K&T 8.1-8.3) basic reduction strategies (PDF) (6-up PDF)
  • (K&T 8.4) NP (PDF) (6-up PDF)
  • (K&T 8.5-8.8, 8.10) polynomial-time reduction (PDF) (6-up PDF)

• (skip) PSPACE: A Class of Problems Beyond NP (K&T 9.1, 9.3-9.5) (PDF) (6-up PDF)

• (skip) Extending the Limits of Tractability (K&T 10.1-10.3) (PDF) (6-up PDF)

• Miscellaneous
  • blank slides (for use by instructor) (PDF)