Work all problems on these sheets. Please write neatly.
1. For each of the pseudocode segments given below, what is the computational complexity (in terms of the size of input data set) ? Give your answer in terms of ⇥(f(n)), where f(n) is one of our standard CS comparison functions, or O(f(n) if the code cannot necessarily be classified as ⇥(f(n)). The “//” is a comment delimiter.
(a) Let A = [a1,...,an] and B = [b1,...,bn] be arrays of doubles. DotProduct(A,B)
sum = 0.0; for i = 1 to n
sum = sum + A[i]*B[i] ; end // for-loop
return sum
(b) Let C = [ci,j ]i=1,...,n;j=1,...,n be an n ⇥ n two dimensional array of doubles. Let X = [x1, . . . , xn] be an array of doubles.
MatrixVectorProd(C,X)
// allocate space for Y = [y1,...,yn] for ii = 1 to n
sum = 0.0; for j = 1 to n
sum = sum + C[i,j]*X[j] ; end // for-j-loop
Y[i] = sum
end // for-i-loop return Y
(c) Let n be a non-negative integer. Someoneimportant(n)
L = 0;
n = n/10 // integer division, no remainder while ( n > 0 )
L = L + 1;
n =n/10;
end // while-loop return L
Can you guess what the value that “Someoneimportant(n)” is returning in L?
(d) Let n be a non-negative integer. SomeoneSilly(n)
L = 0;
n = n/10 // integer division, no remainder while(n>0)and! (n==42)
L = L + 1;
n =n/10;
end // while-loop return L
2. Recall the pseudocode for MergeSort(A), where A is an array A = [a1, . . . , an]:
MergeSort(A) // it is assumed that n = length(A) is available if n == 0 or n == 1
return A
end // end if (this is our base case)
split(A) // inline code (not a function call): defines Aleft and Aright, with Aleft = [a1,...,a(n/2)], n/2 rounded up, and
//Aright =[an/2+1,...,an]
// split is O(n) complexity
Aleftsorted= MergeSort(Aleft)
Arightsorted=MergeSort(Aright)
A = merge(Aleftsorted,Arightsorted ) // inline code (not a function call): // merges two sorted arrays into one array in increasing order.
// merge is O(n) complexity return A
(a) Trace, using a recursion tree, MergeSort(A), where
A = [42,2,13,11,6,7,4]
Show the arrays being passed on each function call, and the arrays being returned.
(b) Show a snapshot of the activiation stack in the execution of MergeSort(A) when the first base case function call is executed.
(c) Show a snapshot of the activation stack when the final base case function call is executed.
3. Let R be the relation from X = {1, 2, 3, 4, 5} back into X, given by the following (list representation): R(1) = {1, 2, 3}
R(2) = {2, 4}
R(3) = {1, 3}
R(4) = {2, 4} R(5) = {5}
(a) From this description of R, give the directed graph representation.
(b) Give the adjacency table (matrix) representation of R.
(c) Is R reflexive? Why or why not.
(d) Is R symmetric? Why or why not.
(e) Is R transitive? Why or why not.
(f) Is R and equivalence relation on X? Why or why not. If so, give the equivalence classes induced by R.
4. Let S be the relation from X = {1, 2, 3, 4, 5} back into X, given by the following (list representation): S(1) = {1, 2}
S(2) = {2, 4}
S(3) = {1, 3}
S(4) = {2, 4} S(5) = {5}
(a) From this description of S, give the directed graph representation.
(b) Give the adjacency table (matrix) representation of S.
(c) Is S reflexive? Why or why not.
(d) Is R symmetric? Why or why not.
(e) Is S transitive? Why or why not.
(f) Is S and equivalence relation on X? Why or why not. If so, give the equivalence classes induced by S.
5. Suppose I have the infix expression:
V =((2+4)/(1+2)+3)((52)⇤(4+(10/2)))
(a) Draw the evaluation tree that results from parsing this infix expression.
(b) Perform a post-order traversal of this tree, where the action at each node is “print”, to obtain the postfix string which represents the evaluation of V . Show this traversal, and the resulting string.
(c) Recall the evaluation of a postfix expression using a stack, which starts empty.
Rules (process string from Left to Right):
- when you hit a value, “push” the value onto the stack,
- when you hit an operator, then “ pop pop op push” , with the popped values feeding into the operator “op” from right to left, and the result pushed back onto the stack.
When the string has been traversed, the (only) value remaining on the stack should be V
(If you hit a spot where there aren’t values to pop, or if there is more than one value on the stack at the end, then the postfix expression is malformed.)
Show the state of the stack directly before and directly after the point where the only “*” is hit.
6. Given the array
B = [41,2,13,11,6,7,42,4]
(a) Show the resulting Max Heap implementation of a Priority Queue (PQ) that results from inserting the elements in B into the PQ succesively from first to last. Show the final Max Heap, as a nearly complete binary tree, and as its array implementation.
(b) Show the resulting Max Heap after serving (removing) the highest priority item, and re-heapifying. You need only show the tree representation.
(c) Show the resulting Max Heap if 57 is now added to the PQ (the one resulting from 6b) ), after re-heapifying. You need only show the tree representation.
Subject | Mathematics |
Due By (Pacific Time) | 05/09/2013 09:00 pm |
Tutor | Rating |
---|---|
pallavi Chat Now! |
out of 1971 reviews More.. |
amosmm Chat Now! |
out of 766 reviews More.. |
PhyzKyd Chat Now! |
out of 1164 reviews More.. |
rajdeep77 Chat Now! |
out of 721 reviews More.. |
sctys Chat Now! |
out of 1600 reviews More.. |
sharadgreen Chat Now! |
out of 770 reviews More.. |
topnotcher Chat Now! |
out of 766 reviews More.. |
XXXIAO Chat Now! |
out of 680 reviews More.. |