Fall 2013 CSE310 Midterm 2B in class Instructions There are six problems in this paper Please use the space provided below the questions to write the answers Budget your time to solve various problems roughly 15 minutes for each problem and avoid spending too much time on a particular question This is a closed book examination You may not consult your books notes Cell phones and computers are not allowed However you can use a basic calculator You are NOT supposed to use a pencil If you use a pencil you cannot challenge your grade after the midterm is graded NAME ASUID Question Score P1 P2 P3 P4 P5 P6 Total 0 Problem 1B 10 points 2 2 2 2 2 Array A contains 10 elements from index 1 to index 10 as shown in the following i 1 A i 18 2 3 4 5 6 7 16 14 12 10 8 6 8 9 10 4 2 0 Suppose you are applying the linear time buildheap algorithm to build a min heap from the 10 elements of array A For i 5 4 3 2 1 show the array structure after the call to min heapify A i is completed using the table provided below After min heapify A 5 the array structure is i 1 A i 18 2 3 4 5 6 7 16 14 12 0 8 6 8 9 10 4 2 10 After min heapify A 4 the array structure is i 1 A i 18 2 3 4 5 6 7 16 14 2 0 8 6 8 9 10 4 12 10 After min heapify A 3 the array structure is i 1 A i 18 2 3 4 5 6 7 16 6 2 0 8 14 8 9 10 4 12 10 After min heapify A 2 the array structure is i 1 A i 18 2 3 4 5 6 7 0 6 2 10 8 14 8 9 10 4 12 16 After min heapify A 1 the array structure is i 1 A i 0 2 3 4 5 6 7 2 6 4 10 8 14 1 8 9 10 18 12 16 Problem 2B 10 points 2 2 2 2 2 Array B contains 10 elements from index 1 to index 10 as shown in the following i 1 2 B i 0 2 3 4 5 6 7 4 6 8 10 12 8 9 10 14 16 18 Suppose you are inserting these 10 elements in the given order into an originally empty min heap implemented in array A For i 6 7 8 9 10 show the array structure after the first i elements are inserted into the min heap using the table provided below After inserting the first 6 elements the array structure is i 1 2 3 4 A i 0 2 4 6 5 6 7 8 9 10 8 10 After inserting the first 7 elements the array structure is i 1 A i 0 2 3 4 5 6 7 2 4 6 8 10 12 8 9 10 After inserting the first 8 elements the array structure is i 1 2 3 4 A i 0 2 4 6 5 6 7 8 9 10 8 10 12 14 After inserting the first 9 elements the array structure is i 1 A i 0 2 3 4 5 6 7 2 4 6 8 10 12 8 9 10 14 16 After inserting the first 10 elements the array structure is i 1 A i 0 2 3 4 5 6 7 2 4 6 8 10 12 2 8 9 10 14 16 18 Problem 3B 20 points 5 5 5 5 In class we have studied the linear time selection algorithm with group size 5 Suppose we will use group size 13 instead of 5 Again we are using the median of medians as the pivot element Assume that there are n elements and all elements are distinct 5pts What is the maximum number of elements that can appear on either side of the pivot element You should not use the asymptotic notations Answer 19n 26 14 5pts Let T13 n denote the worst case time complexity of your algorithm Write down the recurrence formula for T13 n n T13 19n 14 bn Answer T13 n T13 13 26 5pts Use the asymptotic notations to denote T13 n as a function of n Answer T n O n 5pts Suppose you modify the original quicksort algorithm by using the median computed by the linear time selection algorithm as the pivot element Let T n denote the worst case time complexity of this modified quicksort algorithm for sorting n elements Use the asymptotic notations to denote T n as a function of n Answer T n O n log n 3 Problem 4B 20 points 4 4 4 4 4 A disjoint set structure is given by the following array structure We are using union by rank and find with path compression i 1 A i 3 2 3 4 5 6 7 1 1 3 1 5 5 8 9 10 7 3 9 11 12 13 14 15 16 9 11 9 13 13 15 4pts Given the array structure at the top of this page apply the operation union 7 16 Write down the resulting array structure in the following table i 1 2 3 4 5 6 A i 9 1 1 3 1 5 7 8 9 1 7 4 10 11 12 13 14 15 9 9 11 9 13 9 16 9 4pts Given the array structure at the top of this page apply the operation find set 8 Write down the resulting array structure in the following table i 1 2 3 4 A i 3 1 1 3 5 6 7 8 9 10 11 12 13 1 5 1 1 3 9 9 11 9 14 15 16 13 13 15 4pts Given the array structure at the top of this page apply the operation link 1 9 Write down the resulting array structure in the following table i 1 2 3 4 5 6 A i 9 1 1 3 1 5 7 8 9 5 7 4 10 11 12 13 14 15 9 9 11 9 13 9 16 15 4pts Given the array structure at the top of this page apply the operation union 5 10 Write down the resulting array structure in the following table i 1 2 3 4 5 6 A i 9 1 1 3 1 5 7 8 9 5 7 4 10 11 12 13 14 15 9 9 11 9 13 13 16 15 4pts Suppose we are using union by rank and find with path compression Applying a total of m operations to a disjoint set with n elements what is the total number of basic operations required You should use asymptotic notation to give the most accurate bound Answer O m m n 4 Problem 5B 20 points 5 5 5 5 The following four questions deal with binary search trees …
View Full Document
Unlocking...