USC CSD Home
 

Lectures - CSCI 570, Spring 2013, Section 30097D

 
Lecture Slides
(Please note that access to lecture notes is restricted.)

Preview:

  • (May 15, 2013) - final exam (firm)
 
Tentative Slides
The following are tentative slides (in PDF format) for this semester.
  • Administrative

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

  • Stable Matching

  • Basics of Algorithm Analysis

  • 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

  • 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

  • (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)
 

[Last updated Sat Sep 19 2020]    [Please see copyright regarding copying.]