10/13/21, 5:39 PM Sample Midterm (Summer 21 Midterm): Attempt review https://ilearn.sfsu.edu/ay2122/mod/quiz/review.php attempt=319087&cmid=503452 1/5 My Courses / CSC051002-F21R-3801 / Exams / Sample Midterm (Summer 21 Midterm) Started on Wednesday, October 13, 2021, 1:22 PM State Finished Completed on Wednesday, October 13, 2021, 1:24 PM Time taken 1 min 59 secs Grade 15.00 out of 15.00 (100%) Question 1 Correct 1.50 points out of 1.50 Question 2 Correct 1.50 points out of 1.50 Average Case Sequential Search in Array: Assume that the probability that the item is not in the array is . When the item is in the array, the probability that the item is found in index is , the probability that the item is found in index is , and the probability that the item is found in index is The probabilities of matching any of the remaining items are all equal. Assuming that comparison of an array item where the search key is the basic operation, what is the average case complexity function for sequential search of matching 1st through (n-3) items Select one: a. b. c. d. Can’t be determined because the probabilities given don’t add to one. 1 7 1 2 ( 1) 1 4 ( 2) 1 8 53 30 56 12 2 36 43 10 160 The correct answer is: 53 30 56 Select one: True False () = + ∈ ( ) 2 81 +1log 9 8 +2log 2 The correct answer is ‘True’. 10/13/21, 5:39 PM Sample Midterm (Summer 21 Midterm): Attempt review https://ilearn.sfsu.edu/ay2122/mod/quiz/review.php attempt=319087&cmid=503452 2/5 Question 3 Correct 1.50 points out of 1.50 Question 4 Correct 1.50 points out of 1.50 Given the following recurrence: Assume for this problem T(1) = 0, and Back Substitution is performed. After k steps we get: Which of the following complexity functions represents this recurrence Select one: a. b. c. d. () = 2 ( ) + + 1 3 2 () = ( ) + (1+ )+ (2+ )+ ( + )+ ( + )+. . . +( + )2 3 2 2 2 3 2 2 2 2 2 2 3 4 2 3 2 3 2 3 6 2 1 2 1 2 3 2( 1) () = (1 ) + ( 1) 9 2 7 2log 3 2 2log 3 () = (1 ) + + 1 3 2 7 2 3 2 () = Θ( )log 2 () = (1 ) 3 2 7 2 2log 3 3 2log 3 The correct answer is: () = (1 ) + ( 1)9 2 7 2log 3 2 2log 3 Select one: True False () = + ∈ Ω( ) 2 81 +1log 9 8 +2log 2 The correct answer is ‘False’. 10/13/21, 5:39 PM Sample Midterm (Summer 21 Midterm): Attempt review https://ilearn.sfsu.edu/ay2122/mod/quiz/review.php attempt=319087&cmid=503452 3/5 Question 5 Correct 1.50 points out of 1.50 Question 6 Correct 1.50 points out of 1.50 Select one: True False () = 10 ( ) + ∈ Θ( ) 5 3 ￣￣ √ 3 2 The correct answer is ‘True’. for ( k=0; k for ( p=1; p<(n-3); p++ ) { for ( j=2; j print("Algos are fun!") } } } Assuming that the print statement is the basic operation, What is the Big O time complexity (worst case) of this code Select one: a. b. c. d. = 2 ( log ) 2 ( ) 3 ( ) 4 ( log(log )) 2 The correct answer is: ( log(log ))2 10/13/21, 5:39 PM Sample Midterm (Summer 21 Midterm): Attempt review https://ilearn.sfsu.edu/ay2122/mod/quiz/review.php attempt=319087&cmid=503452 4/5 Question 7 Correct 1.50 points out of 1.50 Question 8 Correct 1.50 points out of 1.50 Question 9 Correct 1.50 points out of 1.50 T(n) = 81n + 81log9 n+1 ∈ ω(8log2 n+2) Select one: True False The correct answer is ‘False’. When computing the average case complexity of a function, ALL the probabilities within (P_{out}) are multiplied by (n), and ALL the ones within (P_{in}) are multiplied by (frac{1}{n}) Select one: True False The correct answer is ‘False’. (T(n) = 10T(frac{n}{5}) + sqrt{n^3} in O{(n^{frac{3}{2}})}) Select one: True False The correct answer is ‘True’. 10/13/21, 5:39 PM Sample Midterm (Summer 21 Midterm): Attempt review https://ilearn.sfsu.edu/ay2122/mod/quiz/review.php attempt=319087&cmid=503452 5/5 Question 10 Correct 1.50 points out of 1.50 func midterm(n) { if n <= 1 return 1; for(i=0; i<(n-3); i++) { for(j=n; j>1; (j = frac{j}{2})) { print(“Csc510”); } } midterm((frac{n}{2})) midterm((frac{n}{2})) midterm((frac{n}{2})) midterm((frac{n}{2})) } What is the Theta time complexity of this function Select one: a. (T(n) = Theta(nlog_2^2 n)) b. (T(n) = Theta(n^2)) c. (T(n) =Theta(n^2log_2 n)) d. (T(n) = Theta(nlog_2 log_2 n)) The correct answer is: (T(n) = Theta(n^2)) Recursive Analysis Jump to… San Francisco State University A California State University Campus Academic Technology
