1. What does computational complexity measure? Choose One 5 points The amount of time and memory required to solve a problem The amount of logic gates required in a circuit The number of messages that need to be transmitted to solve a problem Whether a problem requires Calculus to reach a solution 2. Functions with the Slowest Growth Group 4 questions 2.1 Which of these functions grows the most slowly? Choose One 5 points This is also asking: which is the most efficient algorithm? 2.2 Which of these functions grows the most slowly? Choose One 5 points This is also asking: which is the most efficient algorithm? 2.3 Which of these functions grows the most slowly? Choose One 5 points This is also asking: which is the most efficient algorithm? 2.4 Which of these functions grows the most slowly? Choose One 5 points This is also asking: which is the most efficient algorithm? 3. Functions with the Fastest Growth Group 4 questions 3.1 Which of these functions grows the most quickly? Choose One 5 points This is also asking: which is the least efficient algorithm? 3.2 Which of these functions grows the most quickly? Choose all that apply 5 points This is also asking: which is the least efficient algorithm? 3.3 Which of these functions grows the most quickly? Choose One 5 points This is also asking: which is the least efficient algorithm? 3.4 Which of these functions grows the most quickly? Choose One 5 points This is also asking: which is the least efficient algorithm? 4. Recursion: "Towers of Hanoi" Problem Group 2 questions 4.1 What is the minimum number of steps would it take to transfer a tower of 9 discs from Tower 1 to Tower 3? Choose One 5 points The Towers of Hanoi game/puzzle is a visual example of a type of recursive algorithm. Visit the site (through the link above) and try to move the towers of different sizes. Watch the example solution for the increasing number of discs. It does not include a tower of that size, so look for a pattern for the number of steps! 362880 Steps 59049 Steps 511 Steps 81 Steps 4.2 What is the estimated Big-O complexity for solving a Tower of Hanoi Problem of size n ? Choose One 5 points "Solving a Tower of Hanoi Problem for Size n" means moving a tower with "n" discs from Tower 1 to Tower 3. 5. Linear Search vs. Binary Search Group 6 questions 5.1 How many guesses would you need to determine the number out of 1 through 100 in worst case using a linear search? Choose One 5 points The Guess the Number game is essentially a search for an unknown number. You can also try your strategy using a web app available here Note: The questions are about the method (algorithm) used for finding the number, not the verification process the game does. 100 guesses 50 guesses 13 guesses 7 guesses 6 guesses 5.2 How many guesses would you need to determine the number out of 1 through 100 in worst case using a binary search? Choose One 5 points The Guess the Number game is essentially a search for an unknown number. You can also try your strategy using a web app available here Note: The questions are about the method (algorithm) used for finding the number, not the verification process the game does. 100 guesses 50 guesses 13 guesses 7 guesses 6 guesses 5.3 What is the etimated Big-O complexity of a Linear Search? Choose One 5 points 5.4 What is the estimated Big-O complexity for a Binary Search? Choose One 5 points 5.5 Given the information below about the data set, would a linear search or a binary search locate this element more rapidly? Choose One 5 points The element you are searching for is known to be among the first four elements in a list of 100 elements. Linear Search Binary Search 5.6 With no special information, would a linear search or a binary search locate this element more rapidly? Choose One 5 points We do not have information about where in the list of 100 elements an element appears. Linear Search Binary Search 6. What is the initial value for variable "i" in the for-loop below? Choose One 5 points 1 For i = 1 To 6 2 ... 3 Next VBSCRIPT 0 1 7 7. Give a big-O estimate for the number of additions used in this segment of an algorithm. Choose One 5 points 1 Dim total=0 2 For i = 1 To n 3 For j = 1 To n 4 total = total + i + j 5 Next 6 Next 7 response.write(t) VBSCRIPT Not comfortable reading code yet? The algorithm is peforming the following calculation 8. What is the Big-O for an algorithm that counts the number of duplicate pairs in a sequence? Choose One 5 points