New version page

USC CSCI 270 - Algorithms

Upgrade to remove ads

This preview shows page 1 out of 3 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

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)


View Full Document
Download Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?