Lectures - CSCI 570, Spring 2013, Section 30097D

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

Preview:

• (May 15, 2013) - final exam (firm)

• Administrative
  • course administration (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)