CSCI 570 Homework 3 Due Sunday Mar 08 by 23 30 For all divide and conquer algorithms follow these steps 1 Describe the steps of your algorithm in plain English 2 Write a recurrence equation for the runtime complexity 3 Solve the equation by the master theorem For all dynamic programming algorithms follow these steps 1 Define in plain English subproblems to be solved 2 Write the recurrence relation for subproblems 3 Write pseudo code to compute the optimal value 4 Compute its runtimecomplexity in terms of the input size 1 1 Suppose we define a new kind of directed graph in which positive weights are assigned to the vertices but not to the edges If the length of a path is defined by the total weight of all nodes on the path describe an algorithm that finds the shortest path between two given points A and B within this graph Solution We have to reduce a vertex weighted graph G into an edge weighted graph G1 Create a new graph G1 as follows Split each vertex v in G into two vertices vin and vout with an edge weight between them equals to the vertex weight in G1 And the original edges from G have weights as 0 in G1 Edges coming to v in G will come to vin in G1 Edges leaving v in G will leave vout in G1 Run Dijkstra s algorithm In the shortest path tree T1 for G1 an edge between vin and vout means that vertex v is in the shortest path tree T for G Collapse all such edges vin vout in T1 by merging vin and vout This will create the shortest path tree T Rubric 10 points 10 points The algorithm is stated clearly And the algorithm is correct 2 For each of the following recurrences give an expression for the runtime T n if the recurrence can be solved with the Master Theorem Otherwise indicate that the Master Theorem does not apply T n 3T n 2 n2 T n 4T n 2 n2 T n T n 2 2n T n 2n T n 2 nn T n 16T n 4 n T n 2T n 2 nlogn T n 2T n 4 n0 51 T n 0 5T n 2 1 n T n 16T n 4 n T n 10T n 3 n2 Solution T n 3T n 2 n2 case 3 T n n2 2 T n 4T n 2 n2 case 2 T n n2 logn T n T n 2 2n case 3 T n 2n T n 2n T n 2 nn Does not apply a is not constant T n 16T n 4 n case 1 T n n2 T n 2T n 2 nlogn case 2 T n nlog 2 n T n 2T n 4 n0 51 case 3 T n n0 51 T n 0 5T n 2 1 n Does not apply a 1 T n 16T n 4 n case 3 T n n T n 10T n 3 n2 case 1 T n nlog3 10 Rubric 10 points 10 points 1 point for each item One for getting the case right and one for the runtime justification of case 3 Suppose that we are given a sorted array of distinct integers A 1 n and we want to decide whether there is an index i for which A i i Describe an efficient divide and conquer algorithm that solves this problem and explain the time complexity Solution If the array has just one integer then we check whether A 1 1 with one comparison Otherwise divide the list into two parts the first half and the second half as equally as possible Consider the largest element A m of the left half We compare A m with m If A m m the answer is yes and we are done If A m m then we can throw away the right half and continue recursively in the left half Indeed then for every integer k 0 using the fact that the integers are distinct and sorted A m k A m k m k If A m m then we can throw away the left half and continue recursively in the right half Indeed then for every integer k 0 using the fact that the integers are distinct and sorted A m k A m k m k Thus for the number of comparisons we get the following recursion T n T n 2 O 1 T 1 O 1 According to Master Theorem the time complexity is log n 3 Rubric 15 points 10 points The algorithm is stated clearly 10 points if the time complexity of the algorithm is equal or less than log n And it is using divide and conquer algorithm 5 points if the time complexity of the algorithm is is larger than log n And it is using divide and conquer algorithm 0 points if the algorithm is not correct or the algorithm is not using divide and conquer 3 points The recurrence equation for run time complexity is correct 2 points Solving the equation by master theorem and the time complexity is log n 4 We know that binary search on a sorted array of size n takes O log n time Design a similar divide and conquer algorithm for searching in a sorted singly linked list of size n Describe the steps of your algorithm in plain English Write a recurrence equation for the runtime complexity Solve the equation by the master theorem Solution If the array has just one integer then we easily find this value Otherwise firstly we find the middle element of the list this can be done in O n And we split the list into left list and right list Compare this middle element with the search element If they are equal and we are done If the middle element is larger than the search element we throw away the right half list and continue recursively on the left sublist Otherwise we continue recursively on the left sublist We have T n T n 2 O n T n n according to Master Theorem Rubric 15 points 10 points The algorithm is stated clearly 10 points if the algorithm is using divide and conquer algorithm and it is correct 0 points if the algorithm is not correct or the algorithm is not using divide and conquer 3 points The recurrence equation for run time complexity is correct 2 points Solving the equation by master theorem and the time complexity is n 4 5 Given n balloons indexed from 0 to n 1 Each balloon is painted with a number on it represented by array nums You are asked to burst all the balloons If the you burst balloon i you will get nums i 1 nums i nums i 1 coins Here left and right are adjacent indices of i After the burst the left and right then becomes adjacent You may assume nums 1 nums n 1 and they are not real therefore you cannot burst them Design a dynamic …
View Full Document