CS305 Class Notes
Spring 2024 Semester

Michael Eckmann
Skidmore College

Wednesday April 10, 2024
Shortest Path distances, Triangle Inequality, Relaxing an edge, Proof about a sequence of Relaxations, Bellman-Ford algorithm to do SSSP (and can detect NWC), DAG-SHORTEST-PATH
handwritten notes presented
Monday April 08, 2024
Kruskal's for MST, start discussion of shortest path problems, BFS solves single-source to all-destinations on an unweighted graph, introduce Negative Weight Cycle (NWC)
handwritten notes presented
Friday April 05, 2024
Prim analysis with three PQ implementations, proof of correctness
Prim w/ analysis
Wednesday April 03, 2024
Strongly Connected Components (SCC), Minimum Spanning Tree (MST) - Prim's, analysis with PQ implemented w/ heap
Monday April 01, 2024
Depth First Search (DFS) w/ start and end times, topological sort
Friday March 29, 2024
Graphs, edge storage options, dense and sparse, Breadth First Search (BFS)
Wednesday March 27, 2024
Functional Iteration, Ak(j) function and inverse, amortized runtime of m operations for Disjoint Set data structure
Monday March 25, 2024
in class exam
Friday March 22, 2024
Solved the maximizing WAR baseball agent problem, Solved Minimizing completion time problems from HW
Wednesday March 20, 2024
continue Potential method - applied to arrays / python lists (table doubling)
Monday March 18, 2024
more Potential method - applied to arrays / python lists
Friday March 08, 2024
Amortized Analysis - Potential method - my handwritten notes
Wednesday March 06, 2024
Amortized Analysis - Aggregate and Accounting methods
Monday March 04, 2024
revisited the room activities to minimize unscheduled time, and reanalyzed Build-heap from a list
Friday March 01, 2024
fractional Knapsack, heapsort
Wednesday February 28, 2024
more Dynamic Programming and Greedy, Knapsack
Monday February 26, 2024
more Dynamic Programming problems
Friday February 23, 2024
more Dynamic Programming problems
complete grid problem dynamic programming solution (started WED, finished today)
Wednesday February 21, 2024
Memoization, start Dynamic Programming
Monday February 19, 2024
RadixSort and analysis, BucketSort and analysis --- all linear time sorts
my handwritten notes
Friday February 16, 2024
finish randomized QS analysis, Prove worst case lower bound on comparison sorts, Introduce Counting sort
Wednesday February 14, 2024
Hiring problem, Indicator Random Variables, Expected runtime of randomized hiring, analyze randomized quicksort
Monday February 12, 2024
More probability - Random Variables, Expected Value of a R.V., Linearity of Expectation
my handwritten notes
Friday February 09, 2024
Quicksort, Probability - Sample Space, Outcomes, Probability rules, etc.
my handwritten notes
Wednesday February 07, 2024
more examples using the Master Method, quicksort
Monday February 05, 2024
Master Theorem, prove Case 2 and Case 3, example(s)
Friday February 02, 2024
counting up the work in a perfect a-ary tree, equations for # of leaves and work in internal nodes, Master Theorem, prove Case 1 result, example(s)
Wednesday January 31, 2024
Recurrence Relations for divide and conquer algorithms, 6 log facts from section 3.3, look at perfect a-ary tree (a=# of recursive calls)
Monday January 29, 2024
MergeSort analysis via recursion tree, comparison to SelectionSort and InsertionSort
Friday January 26, 2024
Review Asymptotics, Arithmetic Series, Analyze SelectionSort and InsertionSort
Wednesday January 24, 2024
Introduction