CSE310-HW06

CSE310 HW06, Wednesday, 04/19/2023, Due: Wednesday, 04/26/2023 Please read the instructions carefully. You have to use the companion answer sheet (which is a fillable PDF file) to type/select your answers to the questions described here . Hand-written assignment (or photo of it) will not be graded. Submit the filled PDF file of the answer sheet on Gradescope, following the link on Canvas . You should name your file using the format CSE310-HW06-LastName-FirstName.pdf . Make sure that your submission can be viewed clearly on gradescope for auto-grading. Q1 (12 points: 4 + 4 + 4) We have studied the linear time selection algorithm applied on n elements. Assume that all n elements are different. In the algorithm we have studied, we used group size of 5. We proved that the number of elements that are guaranteed to be larger than the median of medians is lower bounded by G ( n, 5) = 3 10 n − 6. Similarly, the number of elements that are guaranteed to be smaller than the median of medians is also lower bounded by G ( n, 5). Therefore, the number of elements on either side of the median of medians after the partition is upper bounded by U ( n, 5) = n − G ( n, 5) = 7 10 n +6. We concluded that the time complexity T 5 ( n ) of the algorithm satisfy the relation T 5 ( n ) ≤ T 5 ( ⌈ n 5 ⌉ ) + T 5 ( 7 n 10 + 6) + Θ( n ). This lead to T 5 ( n ) = Θ( n ). Answer the following questions. (a) Suppose we use group size of 11. What is G ( n, 11) (the number of elements that are guaranteed to be larger than the median of medians)? What is U ( n, 11)? What is the corresponding recurrence relation for the time complexity of the algorithm (denoted by T 11 ( n )? Is T 11 ( n ) = Θ( n )? (b) Suppose we use group size of 13. What is G ( n, 13) (the number of elements that are guaranteed to be larger than the median of medians)? What is U ( n, 13)? What is the corresponding recurrence relation for the time complexity of the algorithm (denoted by T 13 ( n )? Is T 13 ( n ) = Θ( n )? (c) Suppose we use group size of 3. What is G ( n, 3) (the number of elements that are guaranteed to be larger than the median of medians)? What is U ( n, 3)? What is the corresponding recurrence relation for the time complexity of the algorithm (denoted by T 3 ( n )? Is T 3 ( n ) = Θ( n )? Q2 (20 points) Given two sequences X=<C,A,D,B,A> and Y=<C,A,B,A> , you need to use dynamic programming to compute a longest common subsequence of X and Y . On the answer sheet, answer questions regarding the values of c[i, j] . Q3 (12 points) Suppose that we are using hashing with open addressing, where the (linear) probing sequence is defined by h ′ ( k ) = k mod 13 1