Exam 1 Review Session Greedy Algorithm Chi Zhang TRUE FALSE In a dynamic programming formulation the sub problems must be mutually independent False That is a requirement for divide and conquer not dynamic programming TRUE FALSE In dynamic programming you must calculate the optimal value of a sub problem twice once during the bottom up pass and once during the top down pass False Dynamic programming either uses the top down approach memoization or the bottom up one tabulation but not both TRUE FALSE In a divide conquer algorithm the size of each sub problem must be at most half the size of the original problem False This is not a requirement for divide and conquer However divide and conquer requires them to be mutually independent For example T n T n 10 T n 10 9 O n We will see an example in three slides TRUE FALSE Amortized cost of operations in a Fibonacci heap is at least as good as the worst case cost of those same operations in a binomial heap True TRUE FALSE False The Master theorem can always be used to find the complexity of T n if it can be written as a recurrence relation T n aT f n Does case 1 2 3 cover every possibilities No Similar to Case 2 but k 0 Other examples TRUE FALSE Suppose we are given an array A of n distinct elements and we want to find n 2 elements in the array whose median is also the median of A Any algorithm that does this must take n log n time Alternative solution without sorting Step 1 Find the median number O n using SELECT Step 2 Iterate over the list select n 4 elements larger than the median and another n 4 elements smaller than the median O n SELECT https en wikipedia org wiki Median of medians QuickSort Partition Sort Core idea To partition an array a on element x a i is to rearrange a so that x moves to position j may be the same as i All entries to the left of x are x All entries to the right of x are x Observations Element x is already in place Recursively partition left and right Called the pivot i 10 5 550 4 10 9 330 4 9 5 10 330 10 550 Partition Scan the list once swap the element larger than x with the last element smaller than x Time complexity O N i 10 i 10 5 550 4 10 9 330 5 5 9 9 4 10 550 330 i 10 4 10 550 330 QuickSort Time Complexity Time complexity of partition O N Assume the pivot points partition the array into N b and b T n T n b 1 T b O n Best case b n 2 T n 2T n 2 O n Which case T n O nlogn Worst case b n T n T n 1 O n T n O n 2 General case b n k e g k 10 T n O nlogn Since the pivot is chosen randomly the probability of the worst case is extremely low Thus on average it is a O nlogn algorithm N N 10 9N 10 N 100 9N 100 9N 100 81N 100 Find the median using Partition Expected Linear Once we partition the array we only need to recursively partition the half that contains the median until the index of the pivot is at the median position Time complexity T n T n b O n Best case b n 2 T n O n Which case Worst case b 1 T n O n 2 On average b n k T n O n Called the pivot Only need to partition the right half 10 550 4 10 9 330 4 5 10 550 10 9 330 i 5 Find the median Worst Case Linear The problem of the previous approach is that there is a tiny probability that the selected pivot point creates unbalanced partitions Worst case linear time complexity can be obtained by always creating balanced partitions We refer kth smallest for further reading Question 3 Important Theorem In any simple connected planar graph with at least 3 vertices E 3V 6 Question 3 a If 5 then is not a planar graph 3pts Answer In K5 E 10 V 5 E 3V 6 Contradiction Question 3 b If is a simple planar graph with 12 then has a vertex of degree 4 or less In order to apply the theorem we have to make sure V 3 So 1 2 If V 2 then every vertex has degree at most 1 If V 3 we obtain E 3V 6 Proof by contradiction Assume every vertex in G has degree at least 5 Then we obtain E 5V 2 Combine both inequalities we can 5V 2 E 3V 6 3V 6 5V 2 V 12 Contradiction Question 4 Question 4 Cont Analysis A B C D E L miles Which ones can be removed B and D B Because A fully covers B D Because C and E fully covers D Insights 1 for any position x it must be covered by at least one store Which one do we pick Pick the one whose ending distance is maximized Solution A B C D E L miles Let the left and right position be L A and R A for store A L B and R B for store B etc 1 2 3 4 The leftmost uncovered position 0 a A or B b A The leftmost uncovered position R A a Only C The leftmost uncovered position R C a D or E b E The leftmost uncovered position R E L Done Algorithm Time complexity Step 1 will take time to construct intervals Not required Step 2 will take log for sorting 1pt Step 3 We will visit each interval at most three times one for finding the intervals covering one for finding the maximum ending point and another one for deleting from the list Therefore the time complexity of step 3 is 2pts Thus the total time complexity is log 1pt Proof Feasibility the greedy approach must find a solution Optimality the greedy solution finds the one with minimum stores he can keep Feasibility Prove by contradiction The proposed greedy approach selects stores whose coverage is connected If position x can t be covered by our approach That means x can t be covered by any store in the original list which is a contradiction Optimality Core idea establish a quantity that the greedy solution is always better than the optimal solution For the same number of stores the distance covered by greedy solution is greater than the optimal solution because we always choose the one that has the maximum ending position 1 1 2 2 3 3 4 4 L miles 5 5 Optimal Solution Greedy Solution Proof The letter e denotes the ending position Proof Greedy Optimal Proof Algorithm thinking Advanced Heaps Jiao True False The shortest path between two points in a graph could change …