algorithm Bsort(n)
It SHOULD take this first list…
…and produce this list.
1a) But, it doesn't. What does it produce?






1b) There is one error in the algorithm. In which line does it occur? __________
1c) Write the correct pseudocode for the line identified in 1b).
Indicate which are invalid, if any. For those that are valid, compute the result.
a) 9 4 + 2 3 *  6 3  5 * + 7 
___________________________
b) 8 3 2 4 * +  7 8 2 3 *  +
________________________
c) 3 2 + 4 2 * 7 5  2 3 * +  + ________________________
d) Given the following Postfix expression, show in the boxes below what the stack would contain immediately before the  operation is processed. Do not find the final result. Assume that the stack is initially empty.
(top of stack)






Procedure Insert(k)
Write a recursive "InsertionSort" algorithm using Insert.
You may assume a globally defined array a[1..n] of integer values that is already initialized.
4a) å (3i+2) =
(i ranges from 0 to n.) _______________________
4b) å (2i3) =
(i ranges from 50 to 200.) ____________________
4c) S = 5 + 6 + 7 + 8 + … + (n2) + (n1) = _____________________
4d) t(n) = t(n1) + 2, where t(0) = 1 ________________________
a) For an O(n) algorithm, an instance with n = 50 takes 4 seconds.
How long will it take with n = 250? ____________________
b) For an O(n^{3}) algorithm, an instance with n = 30 takes 20 seconds.
How long will it take when n = 60? ____________________
c) For an O(2^{n}) algorithm, an instance with n = 2 takes 12 seconds.
How long will it take when n = 3? ____________________
Show, in order, the output from executing the procedure:
___________ ___________ ___________ ___________ ___________
Which is the most appropriate set for each of the following?
Evaluate a postfix expression _________________
Finding the most distant pair in a list of n items _________________
Reverse a character string of n characters _________________
Find a cycle containing every node in a graph _________________
Finding the closest pair in a list of n items _________________
Search a list of n items for a given value _________________
Fitting a set of final exams into the shortest number of days_________________
Sort a list of n values _________________
Towers of Hanoi _________________
Find a subset of numbers which sum exactly to X _________________
Solutions to the CSI questions.