PSU CS 350: Algorithms and Complexity

Bart Massey
Fall 2017

Syllabus

Schedule

Week 1: Algorithms and Analysis

• Tue 26 September: Course Overview; Algorithms and Analysis (1)
• Thu 28 September: Asymptotic Analysis (2.1-2.2)
• HW 1 due Thursday 5 October before class

Week 2: Iteration and Recursion

• Tue 3 October: Summation and Iterative Algorithms (2.3)
• Thu 5 October: Recurrences and Recursive Algorithms (2.4)
• HW 2 due Tuesday 17 October before class

Week 3: Sorting

• Tue 10 October: Selection, Merge, and Insertion Sort (3.1, 4.1, 5.1)
• Thu 12 October: Quicksort; Comparison-Sort Lower Bound (5.2, 11.2)

Week 4: Advanced Sorting

• Tue 17 October: Heapsort; Midterm Review (4.2)
• Thu 19 October: Midterm 1

Week 5: Graphs, Trees and Optimization

• Tue 24 October: DFS, BFS; Topo Sort; Dijkstra's Algorithm (6.4, 9.1)
• Thu 26 October: Kruskal's Algorithm; Prim's Algorithm (9.3, 9.2)

Week 6: Distance Algorithms

• Tue 31 October: Closest Pair (3.3, 5.5)
• Thu 2 November: Convex Hull (3.3, 5.5)
• HW 3 due Thursday 9 November before class

Week 7: Dynamic Programming

• Tue 7 November: Memoization and Dynamic Programming (8.1); Midterm Review

• Thu 9 November: Midterm 2

Week 8: NP-hard Problems and Search

• Tue 14 November: Knapsacks (3.4, 8.2)
• Thu 16 November: Traveling Salesfolk (12.2)

Week 9: Special Topics

• Tue 21 November: NP-Completeness (11.3)
• Thu 23 November: Thanksgiving, no class meeting
• HW 4 due Friday 1 December before class

Week 10: Algorithms and Theory of Computation

• Tue 28 November: Randomized Algorithms
• Thu 30 November: Randomness; Final Review

Week 11: Final Exam

• Thu 7 December 10:15-12:05

(archived)