CS305 Class Notes
Fall 2022 Semester

Michael Eckmann
Skidmore College

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