NB Foundations: Algorithms
Bart Massey
Winter 2018
Schedule
Week 1: Introduction
- Mon 8 January: Course Overview; Algorithms and Analysis; Lab: Multiplication
- Wed 10 January: Asymptotic Analysis Lab: Chapter 1 Problems
Week 2: Mathematics
- Mon 15 January: Martin Luther King Jr Day — No Class Meeting
- Wed 17 January: Summation and Iterative Algorithms; Recurrences and Recursive Algorithms; Lab: Chapter 1 Problems
Week 3: Data Structures
Mon 22 January: Data Structures I of II; Lab:_BST_vs_List
Wed 24 January: Data Structures II of II; Lab:_Hash_Functions; Homework
Week 4: Searching and Sorting
- Mon 29 January: Selection, Merge, and Insertion Sort; Heapsort; Binary Search
- Wed 31 January: Quicksort; Comparison-Sort Lower Bound; (Radix Sort); Homework
Week 5: Graph Traversal
Mon 5 February: Midterm Review; Graph Algorithms; Lab: Graph Representations
Wed 7 February: Depth-First;Breadth-First;Topo Sort
Midterm due Monday 12 February before class.
Week 6: Weighted Graph Algorithms
- Mon 12 February: Minimum-Weight Spanning Trees
- Wed 14 February: Pathfinding; Homework
Week 7: Combinatorial Search; Heuristic Methods
- Mon 19 February: Complete Search
- Wed 21 February: Local Search
Week 8: Dynamic Programming
- Mon 26 February: Memoization and Tabular DP
- Wed 28 February: DP Examples
Week 9: Intractability
- Mon 5 March: NP Completeness; Homework
- Wed 7 March: NP Reduction and Approximation
Week 10: Bonus Topics; Review
- Mon 12 March: Fantasy Movie League
Wed 14 March: Review