CS305 Class Notes
Fall 2021 Semester

Michael Eckmann
Skidmore College

Thursday December 09, 2021
Topics list for final exam, Graph Algorithms review sheet, solutions to midterm in-class exam, discuss solutions to take-home midterm, Course evaluations
Tuesday December 07, 2021
Floyd-Warshall algorithm, Johnson's algorithm
Monday December 06, 2021
finish Dynamic Programming solution based on number of edges, start DP solutions based on numbering vertices leading to Floyd-Warshall
Thursday December 02, 2021
Dijkstra's pseudocode, analysis and proof of correctness, All-pairs Shortest Path (APSP) problems - repeated Bellman-Ford, repeated Dijkstra's, start Dynamic Programming solution based on number of edges
Tuesday November 30, 2021
Bellman-Ford algorithm and example, how to detect NWCs using Bellman-Ford, Dijkstra's example
Monday November 29, 2021
Shortest Path progblems, Negative Weight Cycles (NWCs), Relaxation of an edge, leading to Bellman-Ford
Tuesday November 23, 2021
MST example, Prim's and Kruskal's algorithms
Monday November 22, 2021
Dynamic Prog. Problem: Longest Palindromic Subsequence
Thursday November 18, 2021
Topological Sort runtime analysis, Strongly Connected Components, start Minimum Spanning Trees
Tuesday November 16, 2021
DFS, DAGs, Topological Sort
Monday November 15, 2021
Sparse and Dense Graph meanings, bounds on number of Edges in a connected graph, BFS, DFS (with start and finish times)
Thursday November 11, 2021
Amortized runtime of m ops of Disjoint Set with Union-by-rank and Path-compression, alpha function, start Graphs and BFS
video recording of zoom lecture
Tuesday November 09, 2021
Connected Components w/ Disjoint Sets Data Structure
video recording of zoom lecture
Monday November 08, 2021
class was cancelled
Thursday November 04, 2021
finish dynamic size list analysis (Potential method), start Connected Components
Tuesday November 02, 2021
continue Amortized Analysis - Potential method
Monday November 01, 2021
continue Amortized Analysis - review Aggregate and Accounting methods, start Potential method
Thursday October 28, 2021
Amortized Analysis with Aggregate and Accounting methods
Tuesday October 26, 2021
Solved Problems 4-2 from text, Heaps, Heapsort
Monday October 25, 2021
conference room scheduling problem (consider Dynamic Programming and Greedy)
handwritten notes for this lecture
Thursday October 21, 2021
0-1 Knapsack, Fractional Knapsack problems
Tuesday October 19, 2021
More dynamic programming
Monday October 18, 2021
More dynamic programming
Thursday October 14, 2021
More dynamic programming
Tuesday October 12, 2021
Change making problem, Memoization / dynamic programming
Thursday October 07, 2021
Counting Sort, Radix Sort, Bucket Sort
Tuesday October 05, 2021
Decision Trees, Lower Bound on Comparison Sorts, Counting Sort
Monday October 04, 2021
Analysis of Expected running time of Randomized Quicksort using Indicator R.V.'s, start Decision Trees, Lower Bound on Comparison Sorts
notes I wrote on the board
Thursday September 30, 2021
Expected Value, Indicator Random Variables, using Ind. R.V.s to analyze randomized quicksort
notes I wrote on the board
Tuesday September 28, 2021
Probability topics
notes I wrote on the board
Monday September 27, 2021
Quicksort
notes I wrote on the board
Example Induction Proof
Thursday September 23, 2021
Prove case 3 Master Theorem, do some examples, start Quicksort
notes I wrote on the board
Tuesday September 21, 2021
Prove cases 1 and 2 Master Theorem
notes I wrote on the board
Monday September 20, 2021
logarithm properties, Master Theorem
notes I wrote on the board
Thursday September 16, 2021
a-ary trees, logarithm properties
Tuesday September 14, 2021
Sorting algorithms analysis, Arithmetic series, MergeSort, logarithm properties
notes I wrote on the board
Monday September 13, 2021
More asymptotics, Sorting algorithms analysis, Arithmetic series
Thursday September 09, 2021
Introduction