Lectures - CSCI 570, Spring 2010, MW Section

• Lecture 1 (PDF) (6-up PDF) (Jan 11, 2010) - administrative, hw1
• Lecture 2 (PDF) (6-up PDF) (Jan 13, 2010) - hw1, course introduction, stable matching
• (Jan 18, 2010) - holiday
• Lecture 3 (PDF) (6-up PDF) (Jan 20, 2010) - stable matching
• Lecture 4 (PDF) (6-up PDF) (Jan 25, 2010) - stable matching
• Lecture 5 (PDF) (6-up PDF) (Jan 27, 2010) - stable matching, five representative problems, algorithm analysis
• Lecture 6 (PDF) (6-up PDF) (Feb 1, 2010) - algorithm analysis, priority queues, graphs
• Lecture 7 (PDF) (6-up PDF) (Feb 3, 2010) - hw2
• Lecture 8 (PDF) (6-up PDF) (Feb 8, 2010) - graphs
• Lecture 9 (PDF) (6-up PDF) (Feb 10, 2010) - graphs, greedy algorithms basics
• (Feb 15, 2010) - holiday
• Lecture 10 (PDF) (6-up PDF) (Feb 17, 2010) - greedy algorithms basics
• Lecture 11 (PDF) (6-up PDF) (Feb 22, 2010) - greedy algorithms basics, shortest path algorithms
• Lecture 12 (PDF) (6-up PDF) (Feb 24, 2010) - shortest path algorithms, hw3
• Lecture 13 (PDF) (6-up PDF) (Mar 1, 2010) - cashier's algorithm, truck driver's algorithm, minimum spanning tree
• Lecture 14 (PDF) (6-up PDF) (Mar 2, 2010) - minimum spanning tree, exams, divde and conquor basics
• (Mar 8, 2010) - midterm review
• (Mar 10, 2010) - midterm exam
• (Mar 15, 2010) - spring break
• (Mar 17, 2010) - spring break
• Lecture 15 (PDF) (6-up PDF) (Mar 22, 2010) - divde and conquor basics, closest pair of points
• Lecture 16 (PDF) (6-up PDF) (Mar 24, 2010) - solutions to some midterm problems, closest pair of points, convolution and FFT
• Lecture 17 (PDF) (6-up PDF) (Mar 29, 2010) - hw4, convolution and FFT
• Lecture 18 (PDF) (6-up PDF) (Mar 31, 2010) - dynamic programming basics
• Lecture 19 (PDF) (6-up PDF) (Apr 5, 2010) - dynamic programming basics
• Lecture 20 (PDF) (6-up PDF) (Apr 7, 2010) - sequence alignment
• Lecture 21 (PDF) (6-up PDF) (Apr 12, 2010) - Bellman-Ford algorithm, network flow basics
• Lecture 22 (PDF) (6-up PDF) (Apr 14, 2010) - network flow basics
• Lecture 23 (PDF) (6-up PDF) (Apr 19, 2010) - network flow basics
• Lecture 24 (PDF) (6-up PDF) (Apr 21, 2010) - application of network flows - bipartite matching
• Lecture 25 (PDF) (6-up PDF) (Apr 26, 2010) - application of network flows - bipartite matching
• Lecture 26 (PDF) (6-up PDF) (Apr 28, 2010) - application of network flows - bipartite matching

Preview:

• (May 10, 2010) - 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)
  • HW4 (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)
  • shortest path algorithms (PDF) (6-up PDF)
  • minimum spanning tree (PDF) (6-up PDF)

• Divide and Conquor
  • divde and conquor basics (PDF) (6-up PDF)
  • closest pair of points (PDF) (6-up PDF)
  • convolution and FFT (PDF) (6-up PDF)

• Dynamic Programming
  • dynamic programming basics (PDF) (6-up PDF)
  • sequence alignment & Bellman-Ford algorithm (PDF) (6-up PDF)

• Network Flow
  • network flow basics (PDF) (6-up PDF)
  • application of network flows - bipartite matching (PDF) (6-up PDF)
  • assignment problem (skip) (PDF) (6-up PDF)

• NP and Computational Intractability (skip)
  • basic reduction strategies (PDF) (6-up PDF)
  • NP (PDF) (6-up PDF)
  • polynomial-time reduction (PDF) (6-up PDF)