PSU CS 584/684 - Algorithm Design and Analysis (Spring 2014)

Weekly outline

• 
  

  General

  • News forum
  • Syllabus Page
  • Crossgrade URL
  • Crossgrade - June 13, 2014 Page
  • Homework Grading Rubric Page
• 
  

  1 April - 7 April

  1 April: Course Intro and Setup; Entrance Evals
  3 April: Reading and Writing Algorithms
  Reading: Chapters 1, 2

  • Reading and Writing Algorithms Page
  • HW 1: Algorithm Design Page
• 
  

  8 April - 14 April

  8 April: Analyzing Algorithms
  10 April: Proving Algorithms Correct
  Reading: Chapter 3, Appendix A–C

  • Analyzing Algorithms Page
  • Proving Algorithms Correct Page
• 
  

  15 April - 21 April

  15 April: Algorithm Design Patterns
  17 April: Algorithm Complexity and Performance

  • Algorithm Design Patterns Page
  • Algorithm Complexity and Performance Page
  • HW 2: Analysis, Trees, Dynamic Programming Page
• 
  

  22 April - 28 April

  22 April: Trees and Balancing
  24 April: Memoization and Dynamic Programming
  Reading: Chapter 13, 15

  • HW 1 Sample Solution File
  • Trees and Balancing Page
  • Dynamic Programming Page
• 
  

  29 April - 5 May

  29 April: String Matching
  1 May: Amortized Analysis
  Reading: Chapter 32, 17

  • String Matching Page
  • Amortized Analysis Page
  • HW 3: String Matching, Amortized Algorithms Page
• 
  

  6 May - 12 May

  6 May: Midterm Exam
  8 May: Triangulation

  Lecture: Andrew Black
  Notes: Bryant York

  • Triangulation File
• 
  

  13 May - 19 May

  13 May: Matrix Operations
  15 May: Linear Sorting and Order Statistics
  Reading: Chapter 28, 8, 9

  • Matrix Operations Page
  • Linear Sorting and Order Statistics Page
• 
  

  20 May - 26 May

  20 May: Graph Representations and Algorithms
  22 May: Graph Coloring
  Readings: Chapter 22; A. Kozowski and K. Manuszewski, Classical Coloring of Graphs, ch. 1 of Graph Coloring, ed. M. Kubale, AMS 2004

  • Graphs Page
  • Graph Coloring Page
  • HW3 Sample Solution Page
• 
  

  27 May - 2 June

  27 May: Maximum Flow
  29 May: Randomization
  Reading: Chapter 26, 5.3; Bart Massey, Fast Perfect Weighted Resampling, Proceedings of the 33rd International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2008), Las Vegas, Nevada, March 2008

  • Maximum Flow Page
  • CS 684 Final Paper Page
  • HW 4: Graph Coloring Sudoku Solver Page
  • Randomization Page
• 
  

  3 June - 9 June

  3 June: State Space Search
  5 June: Quickfire Design Competition
  Reading: Matthew L. Ginsberg, Essentials of Artificial Intelligence, chapters 2–3, Morgan Kaufmann Publishers 1993

  • State-Space Search Page
• 
  

  10 June - 16 June

  Final Exam: Take home: turn in Thursday 12 June 10:15–10:45 or by email submission of PDF to grader.

  • Final Exam File
  • HW 4 Sample Solution Page