Topics/Algorithms ● Gale Shapley Algorithm ● Greedy algorithms ○ 1. Greedy algorithm stays ahead ■ If someone measures the algorithm’s progress step-by-step, you can see it does better than any other algorithm at any point and is the optimal solution (how to prove optimality) ○ 2. Exchange argument ■ Consider any possible solution to the problem and gradually transform it into the solution found by the greedy algorithm without hurting its quality ■ Solution is at least as good as any other solution ● Interval Scheduling Problem ● Lateness Problem ● Kruskal’s ● Prim’s ● MST ● Bipartite graphs ● Dijkstra’s ● Reverse-delete algorithm ● Union-find data structure ● Merge sort ● Binary heap ○ To build heap in O(N) == bottom up appraoch ● Binomial heap ○ although inserting an single element into a binomial heap is ○ O(log(n)) ○ , inserting ○ n ○ elements is ○ O(n) ○ . ● Fibonacci heap ○ decrease the value of a key in ○ O(1) ○ and that this lets Dijkstra’s and Prim’s run in ○ O(m+nlog(n)) ● Master’s theorem ● Topological order TO DO● Amortized runtime practice problems ● Heaps / binomial heaps (wk3 slides) ● Master theorem ● Inversions !! ● Accoutning method vs aggregate method ● Fib Chapter 4 Problems 1. e* is cheapest edge ⇒ then there is a MST a. True because e* would be first edge in Kruskal’s algorithm 2. e^2 ⇒ Kruskal’s algorithm only cares about actual values and not relative order of values 3. Greedy algorithms ● packing/subset ○ “Pick something to do” ○ Ex. base station ○ Ex. picking which assignment to skip ○ Proof ■ Start with induction ● Use that at every point ur solution stays ahead or not behind ■ Then use proof by contradiction ● Permutation ○ Ex. swimming/inversion ○ Ex. Lateness ○ Prove ■ Inversions ● Example problem (discussion 3) == base station and minimize lateness ○ List of free food events that have a start time Si and end time fi ○ In order to get free food, you need to attend the entire event ○ Which events do we go to to maximize the # of number of events you go to? ■ Ex. earliest endtime ○ Proof of correctness ■ 1. ● BC = only 1 event ● IS = say we are going to k events and we need to pick the k+1 st. we have OUR and OPT solution ○ Assume our last free food events ends before optimal last free food event ○ Thus we can also assume our K =1 st events ends no later than OPTs○ We had at least some set of free food problems if not more than and we always pick earliest ending ■ 2. Prove we will have the maximum (contradiction) ● Say OPT has n+1 events and we have only have n ● Because we end no later than OPT did, we have to have n+1 events ⇒ we also have option for more events because we always stay ahead or in line with OPT ● Thus OPT can’t be optimal ● Example 2 ○ Schedule of workers with start time and finish time ○ Want to get smallest rep set ○ Pick smallest group of people who overlap with everyone ○ Algorithm (similar to base station) ■ 1. What if you pikc people who overlap with the most and delete the people they overlap with ● Doesnt work ■ 2. Pick first uncovered person A. Let the set of people who overlap shifts with A. take the people from S with latest end time and delete all that overlap with S ● Works!!! ○ Graphs / trees ● Finding shortest path ○ d(t) = d(s) + c || d(u) + b ○ If u can’t store predecessor ○ And find smallest d(t) ● BFS with queue implementation ● t/f O(m+n) is O(m) ○ M <= n^2 ○ M = n-1 ○ O(n-1+n) = O(2n) = O(n) = O(m)