Test#2 Answers CS 5333

CS5333.501 F18 Exam #2 Name:_______________________________________ NetID:____________________________ Score:________________ 1. 10 In questions A–E find the “best” big-O notation to describe the complexity of the algorithm. Choose your answers from the following and write them in the ( ) with matching question numbers: 1, log2 n, n, n log2 n, n 2 , n3 , . . . , 2 n , n! . A. A binary search of n elements. B. A linear search to find the smallest number in a list of n numbers. C. An algorithm that prints ALL bit strings of length n. D. The number of print statements in the following: i := 1, j := 1 while i ≤ n while j ≤ i print “hello”; j := j + 1 i := i + 1 E. The best-case analysis of a linear search of a list of size n (counting the number of comparisons). Write Your Answers: A. ( log2 n,) B. ( n, ) C. ( 2 n , ) D. ( n, ) E. ( 1, ) 2. 20 In questions A – E write your answers in the parentheses ( ): A. What is the symbol for Average-Case Complexity? ( Θ ) B. What is the symbol for Best-Case Complexity? ( Ω ) C. Which Induction Principle is used to show results of the recursively defined set? Your Answer: Principle of ( c. ) Induction a. mathematical b. strong c. structural d. hypothetical e. weak D. A problem that is solvable using an algorithm with polynomial (or better) worst-case complexity is called ( d. ). These problems are said to belong to class P. b. checkable b. traceable c. countable d. trackable e. calculable E. Problems for which a solution can be ( a. ) in polynomial time are said to belong to the class NP. a. checked b. traced c. counted d. tracked e. calculated 1 3. 10 How many cards must be selected from the standard 52 deck to guarantee that at least 3 cards of the same suit are chosen? (show or explain your work, not just the answer) Here the pigeons are the cards and the pigeonho