Lectures - CSCI 570, Summer 2012, Session Two

• Lecture 1 (PDF) (6-up PDF) (Jun 27, 2012) - administrative, hw1
• Lecture 2 (PDF) (6-up PDF) (Jun 28, 2012) - hw1
• Lecture 3 (PDF) (6-up PDF) (Jul 2, 2012) - hw1, course introduction, stable matching
• Lecture 4 (PDF) (6-up PDF) (Jul 3, 2012) - stable matching
• (Jul 4, 2012) - independence day holiday
• (Jul 5, 2012) - class canceled, SGM shutdown by fire department
• Lecture 5 (PDF) (6-up PDF) (Jul 9, 2012) - stable matching, five representative problems
• Lecture 6 (PDF) (6-up PDF) (Jul 10, 2012) - hw2
• Lecture 7 (PDF) (6-up PDF) (Jul 11, 2012) - algorithm analysis, priority queues
• Lecture 8 (PDF) (6-up PDF) (Jul 12, 2012) - priority queues, graphs
• Lecture 9 (PDF) (6-up PDF) (Jul 16, 2012) - graphs, greedy algorithms basics
• Lecture 10 (PDF) (6-up PDF) (Jul 17, 2012) - greedy algorithms basics, shortest path algorithms
• Lecture 11 (PDF) (6-up PDF) (Jul 18, 2012) - shortest path algorithms, coin changing, selecting breakpoints, minimum spanning tree
• Lecture 12 (PDF) (6-up PDF) (Jul 19, 2012) - minimum spanning tree, clustering, exams, divide & conquer basics
• Lecture 13 (PDF) (6-up PDF) (Jul 23, 2012) - divide & conquer basics, closest pair of points, integer multiplication
• Lecture 14 (PDF) (6-up PDF) (Jul 24, 2012) - hw3, convolution, FFT
• Lecture 15 (PDF) (6-up PDF) (Jul 25, 2012) - dynamic programming basics
• (Jul 26, 2012) - midterm exam (firm)
• Lecture 16 (PDF) (6-up PDF) (Jul 30, 2012) - dynamic programming basics, sequence alignment, Bellman-Ford algorithm
• Lecture 17 (PDF) (6-up PDF) (Jul 31, 2012) - Bellman-Ford algorithm, network flow basics
• Lecture 18 (PDF) (6-up PDF) (Aug 1, 2012) - flow basics, application of network flows
• Lecture 19 (PDF) (6-up PDF) (Aug 2, 2012) - application of network flows
• Lecture 20 (PDF) (6-up PDF) (Aug 6, 2012) - application of network flows

Preview:

• (Aug 7, 2012) - final exam (firm)

• Administrative
  • course administration (PDF) (6-up PDF)
  • exams (PDF) (6-up PDF)

• Programming Assignments
  • HW1 (PDF) (6-up PDF)
  • HW2 (PDF) (6-up PDF)
  • HW3 (PDF) (6-up PDF)

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

• Stable Matching
  • first problem: stable matching (PDF) (6-up PDF)
  • five representative problems (PDF) (6-up PDF)

• Basics of Algorithm Analysis
  • algorithm analysis (PDF) (6-up PDF)
  • priority queues (PDF) (6-up PDF)

• Graphs (PDF) (6-up PDF)

• Greedy Algorithms
  • greedy algorithms basics (PDF) (6-up PDF) - interval scheduling, scheduling to minimize lateness, optimal caching
  • shortest path algorithms, coin changing, selecting breakpoints (PDF) (6-up PDF)
  • minimum spanning tree, clustering (PDF) (6-up PDF)

• Divide and Conquer
  • divide & conquer basics (PDF) (6-up PDF) - mergesort, counting inversions
  • closest pair of points, integer multiplication (PDF) (6-up PDF)
  • convolution, FFT (PDF) (6-up PDF)

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

• Network Flow
  • network flow basics (PDF) (6-up PDF) - max flow, min cut, Ford-Fulkerson algorithm, capacity scaling
  • 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 (Skip)
  • basic reduction strategies (PDF) (6-up PDF)
  • NP (PDF) (6-up PDF)
  • polynomial-time reduction (PDF) (6-up PDF)