Exam 1 Rubric Q12 21 True False 12 Finding the k th minimum element in an array of size n using a binary min heap takes O k log n time False 13 We can merge any two arrays each of size n into a new sorted array in O n False 14 The shortest path in a weighted directed acyclic graph can be found in linear time True 15 Given a weighted planar graph Prim s algorithm using a binary heap implementation will outperform Prim s algorithm using an array implementation True Explanation In Planar graph E 3 V 6 Prim s algorithm using array has the complexity of O V 2 E O V 2 Prim s algorithm using binary heap has the complexity of O V logV E logV O V logV Therefore Prim s algorithm using array will run slower than Prim s algorithm using binary heap 16 If f n n log n and g n O n2 log n then f n O g n False 17 If we have a dynamic programming algorithm with n2 subproblems it is possible that the space usage could be O n True 18 There are no known polynomial time algorithms to solve the fractional knapsack problem False 19 In a knapsack problem if one adds another item one must solve the whole problem again in order to find the new optimal solution False 20 Given a dense undirected weighted graph the time for Prim s algorithm using a Fibonacci heap is O E True 21 In a binomial min heap with n elements the worst case runtime complexity of finding the second smallest element is O 1 False Q22 31 Multiple Choice 22 The solution to the recurrence relation T n 8 T n 4 O n1 5 log n by the Master theorem is O n1 5 log2 n 23 There are four alternatives for solving a problem of size n by diving it into subproblems of a smaller size Assuming that the problem can be divided into subproblems in constant time which of the following alternatives has the smallest runtime complexity we solve 5 subproblems of size n 3 with the combing cost of n log n 24 Which of the following statements is true If an operation takes O n expected time then it may take O 1 amortized time 25 Which of the following properties does not hold for binomial heaps FINDMIN takes O log n worst case time 26 There are n people who want to get into a movie theater The theater charges a toll for entrance The toll policy is the following the i th person is charged k2 when i 0 mod k this means that i is a multiple of k or zero otherwise What is the amortized cost per person for entering the theater Assume that n k k 27 What is the runtime complexity of the following code void exam1 int n int count 0 for int i n 2 i n i for int k 1 k n k 2 k for int j 1 j n j j 2 count n log2 n 28 Given an order k binomial tree Bk deleting its root yields k binomial trees 29 Kruskal s algorithm cannot be applied on directed and weighted graphs 30 Consider a recurrence T n T a n T b n n where 0 a b 1 and a b 1 Which of the following statements is true T n n log n 31 Consider an undirected connected graph G with all distinct weights and five vertices A B C D E and Suppose CD is the minimum weight edge and AB is the maximum weight edge Which of the following statements is false No minimum spanning tree contains edge AB Long Questions Q1 Amortized Cost Consider a singly linked list data structure that stores a sequence of items in any order To access the item in the i th position requires i time units Also any two contiguous items can be swapped in constant time The goal is to allow access to a sequence of n items in a minimal amount of time The TRANSPOSE is a heuristic that improves accessing time if the same is accessed again TRANSPOSE works in the following way after accessing x if x is not at the front of the list swap it with its next neighbor toward the front What is the amortized cost of a single access Solutions Aggregate method Suppose the singly linked list is Considering the worst case of accessing these n items we start access from a n to a 1 head a 1 a 2 a n We first access to a n which takes n cost Then we swap it with a n 1 the next step we want to access to the a n 1 again it takes n cost Accessing a n and a n 1 takes 2 n cost Then we access the a n 2 which takes n 2 cost Then we swap it with a n 2 In the next step we want to access to the a n 3 again it takes n 2 cost Accessing a n 2 and a n 3 takes 2 n 2 cost Repeatedly do that we will get the following summation of cost 2 2 2 4 2 6 2 n 2 2 n n cost of swap 4 1 2 3 n 2 n n n 2 2 n O n 2 Therefore the amortized cost per access is O n Please read the textbook about the definition of amortized cost Amortized analysis gives the average performance of each operation in the worst case Rubrics 12 pts 5 pts State the worst case scenario is to access from a n to a 1 We cannot perform swap along The order of accessing a sequence of n elements is not the worst case 1 pt accessing order is not specified 2 pts only considering accessing one element 2 pts 6 pts Analyze and state the summation of total cost which is O n 2 Wrong explanation or no explanation 6pt Explaining using i this is not the worst case 4 pt Correct explanations Swap can not be performed once after each access It swaps i 1 th element with i th element incorrect statement about it will get 1 pt lack of sufficient explanation for example how to calculate the total cost 2 pts The cost of transpose is not considered 2 pts Transpose actually degrade the performance in the worst case any statement that transpose increase the performance 1 pt 1 pts Analyze and state the amortized cost per access which is O n the total cost is incorrect 2 pts Answer is not O n 1 pt Q2 Shortest Path Problem Consider a network of computers represented by a directed weighted graph where each vertex is a computer and each edge is a wire between two computers An edge weight w u v represents the probability that a network packet unit of binary data going from computer u reaches computer v Our goal is to …