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).
There are three possible ways to fix the problem in this algorithm. Therefore, there are three correct answers to parts 1b) and 1c).
Indicate which are invalid, if any. For those that are valid, compute the result.
a) 9 4 + 2 3 *  6 3  5 * + 7 
= 15
b) 8 3 2 4 * +  7 8 2 3 *  + is invalid
There are not enough operators. 8 3 2 4 * +  gives the answer 3 and 7 8 2 3 *  + gives the answer 9, but there is no operator remaining to finish the calculation.
c) 3 2 + 4 2 * 7 5  2 3 * +  +
= 5
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.
The following operations are done before the  is reached:
(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.
procedure InsertionSort(n)
4a) å (3i+2) =
(i ranges from 0 to n.)
= 3n^{2}/2 + 7n/2 + 2
Since å i _{(i = 0 to n)} = (n(n+1))/2 and å 1 _{(i = 0 to n)} = n+1 then
å (3i+2) _{(i = 0 to n)} = 3(n(n+1))/2 + 2(n+1) = 3n^{2}/2 + 7n/2 + 2
4b) å (2i3) =
(i ranges from 50 to 200.) = 37297
2å i _{(i = 50 to 200)} = 2å i _{(i = 1 to 200)}  2å i _{(i = 1 to 49)} =
2( 200(201)/2  49(50)/2 ) = 200(201)  49(50) = 40200  2450 = 37750 and
3å i _{(i = 50 to 200)} = 3å i _{(i = 1 to 200)}  3å 1 _{(i = 1 to 49)} = 3( 200  49 ) = 3(151) = 453 and
37750  453 = 37297
4c) S = 5 + 6 + 7 + 8 + … + (n2) + (n1)
= (n^{2}  n)/2  10
4d) t(n) = t(n1) + 2, where t(0) = 1 = 2n + 1
a) For an O(n) algorithm, an instance with n = 50 takes 4 seconds.
How long will it take with n = 250?
(50/4) = (250/x) thus, x = 20
b) For an O(n^{3}) algorithm, an instance with n = 30 takes 20 seconds.
How long will it take when n = 60?
(30^{3}/4) = (60^{3}/x) thus, x = 160
c) For an O(2^{n}) algorithm, an instance with n = 2 takes 12 seconds.
How long will it take when n = 3?
(2^{2}/12) = (2^{3}/x) thus, x = 24
Or, 3 = 2 + 1 and anytime you increase the power of 2 by 1, it doubles the amount.
So, increasing n by 1 doubles the time.
Show, in order, the output from executing the procedure:
If n = 1 is false, the procedure makes a recursive call to Print_it with the parameter (n  1). It must then wait on the completion of that call before it can print its own number (n). If n = 1 is true, that "clone" of the procedure can print its number (which is 1) and does not make a recursive call to Print_it. Thus the recursion ends and Print_it(2) can print its number (which is 2) and end also. Then Print_it(3) gets to print, etc., until Print_it(5) prints and ends. So, the numbers are printed in the following order.
1 2 3 4 5
Which is the most appropriate set for each of the following?
Evaluate a postfix expression P
Finding the most distant pair in a list of n items P
Reverse a character string of n characters P
Find a cycle containing every node in a graph NP
Finding the closest pair in a list of n items P
Search a list of n items for a given value P
Fitting a set of final exams into the shortest number of days NP
Sort a list of n values P
Towers of Hanoi EXP
Find a subset of numbers which sum exactly to X NP
Back to the Oct 16 Foundation Exam page.