CS5333.501 F18 Exam #2
Name:_______________________________________ NetID:____________________________ Score:________________
1. In questions A–E find the “best” big-O notation to describe the complexity of the
algor
...
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
[Show More]
