Fall 2022 Semester

Michael Eckmann

Skidmore College

Thursday December 08, 2022 |
Dynamic Programming for APSP leading to Floyd-Warshall, how to remove negative weights and use repeated Dijkstra's leading to Johnson's algorithm |
copy of handwritten notes I presented on the board |
||

Tuesday December 06, 2022 |
All Pairs Shortest Paths (APSP) problems, Dynamic Programming for APSP using Extend-SP and repeated squaring (b/c similar to matrix multiplication) |
|||

Monday December 05, 2022 |
Shortest Path problems - DAG - use Topological sort before relaxing edges, Dijkstra's algorithm for SSSP (negative weights not allowed), repeated Bellman-Ford, repeated Dijkstra's |
copy of handwritten notes I presented on the board |
||

Thursday December 01, 2022 |
Shortest Path problems - NWC (negative weight cycles), Relax function, proof that d is maintained as an upper bound on the shortest path (dist), Bellman-Ford algorithm for SSSP allowing negative weight edges, how to determine a NWC exists |
|||

Tuesday November 29, 2022 |
review Prim's for Minimum Spanning Trees, generic approach, Kruskal's algorithm, start Shortest Path problems |
|||

Monday November 28, 2022 |
Minimum Spanning Trees, Prim's algorithm, analysis using binary min heap, unsorted array, fibonacci heap |
Prim's algorithm and analysis using three different implementations of PQ |
||

Tuesday November 22, 2022 |
in-class exercises on counting running time, Strongly Connected Components (SCC), Start Minimum Spanning Trees |
|||

Monday November 21, 2022 |
Directed Acyclic Graphs (DAGs), Topological Sort, Strongly Connected Components (SCC) |
|||

Thursday November 17, 2022 |
Searching in graphs - Breadth First Search (BFS), Depth First Search (DFS) |
|||

Tuesday November 15, 2022 |
Introduce functional iteration, Ak(j) fast growing function, the very slow growing inverse of Ak(j), Sparse and Dense graphs, space requirements for edge storage |
copy of handwritten notes I presented on the board |
||

Monday November 14, 2022 |
covered last seven pages of pdf posted below (for Nov. 10th) |
|||

Thursday November 10, 2022 |
Amortized analysis - finish potential method, start graphs and connected compenents algorithm, disjoint set data structure |
copy of handwritten notes I presented on the board |
||

Tuesday November 08, 2022 |
Amortized analysis - continue potential method |
|||

Monday November 07, 2022 |
Amortized analysis - accounting method, start potential method |
|||

Thursday November 03, 2022 |
Dynamic programming problem(s) |
|||

Tuesday November 01, 2022 |
In-class exam |
|||

Monday October 31, 2022 |
Dynamic programming problem(s) |
|||

Thursday October 27, 2022 |
Amortized analysis (aggregate method) |
|||

Tuesday October 25, 2022 |
continue Binary Min Heaps, start Amortized analysis |
|||

Monday October 24, 2022 |
HW questions, Greedy Solutions to Maximizing Room Scheduling activites, proof that it works, start discussing Binary Min Heaps |
image of choices ideas for rod cutting problem |
image of choices ideas for Inventory problem |
copy of handwritten notes I presented on the board |

Tuesday October 18, 2022 |
Longest Common Subsequence (LCS) problem, start 0-1 Knapsack problem |
copy of handwritten notes I presented on the board (last 4.5 pages not presented --- ran out of time --- will present those on 10/20) |
||

Monday October 17, 2022 |
more Dynamic Programming |
copy of handwritten notes to be presented on the board |
||

Thursday October 13, 2022 |
more Dynamic Programming problems |
|||

Tuesday October 11, 2022 |
Dynamic Programming |
copy of handwritten notes presented on the board |
||

Monday October 10, 2022 |
Study day - no class |
|||

Thursday October 06, 2022 |
finish analyzing Radix Sort, Bucket Sort, Change Making (Fewest coins) problem, Greedy algorithms, Memoization |
|||

Tuesday October 04, 2022 |
finish determining lower bound on comparison sorts, Counting sort, idea of a Stable sort, Radix Sort |
|||

Monday October 03, 2022 |
revisit end of analysis of Randomized Quicksort, revisit Decision Trees, finish determining lower bound on comparison sorts |
|||

Thursday September 29, 2022 |
finish analysis of Randomized Quicksort, Decision Trees, determine lower bound on comparison sorts |
|||

Tuesday September 27, 2022 |
Random Variables, Linearity of Expectation, Indicator R.V.s |
|||

Monday September 26, 2022 |
more Probability |
|||

Thursday September 22, 2022 |
Partition, Quicksort, Randomized QS, start Probability |
copy of handwritten notes presented on the board |
||

Tuesday September 20, 2022 |
Finish proof of Master Theorem case 1, Prove cases 2 and 3 of Master Theorem, use Master Method on some examples |
|||

Monday September 19, 2022 |
Recurrence relations, logarithm properties, start proving cases of Master Theorem |
|||

Thursday September 15, 2022 |
Recurrence relations, logarithm properties |
|||

Tuesday September 13, 2022 |
Reminder of Arithmetic Series, Analyze SelectionSort and InsertionSort, start discussion of MergeSort |
|||

Monday September 12, 2022 |
Review Asymptotics, Loop Invariants, Arithmetic Series, Analyze SelectionSort |
|||

Thursday September 08, 2022 |
Introduction |