October 23 2019 Term Test CSC 263 H1F Question 1. Multiple Choice using Bubble Sheet. 50 marks
Instructions. Indicate your answers on the bubble sheet at the end of this booklet. Fill exactly one bubble per question. Use a pencil, and fully erase your bubble if you change your mind. Only the bubble sheet will be marked. Bubble sheets will be marked by a computer.
Marking scheme. Correct selection: 2 points. Incorrect or missing selection: zero points.
1. The definition of an abstract data type requires a description of a assumptions and values
b values and operations
c operations and algorithms
d algorithms and data representation e data representation and assumptions
ANSWER: B
2. The definition of an data structure implementation requires a description of
a assumptions and values b values and operations
c operations and algorithms
d algorithms and data representation
e data representation and assumptions ANSWER: D
3. Consider Insertion Sort on an array of size n. The worst case number of comparisons performed is a O1
b On
c Onlogn
d On2
e none of the above
ANSWER: D
4. Consider Insertion Sort on an array of size n. The best case number of comparisons performed is
a O1 b On
c Onlogn d On2
e none of the above ANSWER: B
5. Which of the following is a true statement? a fnOn2fnn2
b fnn2fnn2
c fnn2fnOn2
d more than one of the above e none of the above
ANSWER: E
6. Consider Insertion Sort on an array of size n. The best case number of comparisons occurs when
a the input is already sorted
b the selected pivots produce balanced partitions
c the pivots are in decreasing order d the input is randomized
e none of the above ANSWER: A
page 1 of 12
over…
CSC 263 H1F Term Test October 23 2019
7. An indicator random variable
a is a uniform random permutation
b is selected with equal probability from the sample space c is one if the associated event occurs and zero otherwise
d is used to transform a deterministic algorithm into a randomized algorithm e none of the above
ANSWER: C
8. Deterministic QuickSort has
a the same asymptotic worst case and average case complexity b the same asymptotic worst case and best case complexity
c the same asymptotic average case and best case complexity d more than one of the above
e none of the above ANSWER: C
9. Which of the following inputs yields guaranteed Onlogn runtime for Randomized QuickSort? a input is already sorted ascending
b input is already sorted descending
c input selected from a uniform random permutation
d more than one of the above e none of the above
ANSWER: E
10. Which of the following is correct about randomized quicksort and deterministic quicksort?
a they have different worstcase time complexity
b randomized quicksort has better space complexity than deterministic quicksort
c randomized quicksort has better averagecase time complexity than deterministic quicksort
d randomized quicksort has better worstcase expected time complexity than deterministic quick
sort
ANSWER: D contains typo
11. Consider the transformation of this tree from left to right:
58
2 85
727
This is known as a
a left rotation
b right rotation
c leftright rotation
d rightleft rotation e none of the above
ANSWER: A
page 2 of 12
contd. . .
October 23 2019 Term Test
12. Consider the transformation of this tree from left to right:
24
1 62 6
471357
35
This is known as a
a left rotation
b right rotation
c leftright rotation
d rightleft rotation e none of the above
ANSWER: D
13. Consider the transformation of this tree from left to right:
24
1 62 5
47136357
This is known as a
a left rotation
b right rotation
c leftright rotation
d rightleft rotation e none of the above
ANSWER: E
14. The time complexity of a leftright rotation is
a O1, because the subtree heights do not change
b O1, because a constant number of pointers are permuted
c O1, because the balance factor is always between 1 and 1 d more than one of the above
e none of the above ANSWER: B
CSC 263 H1F
page 3 of 12
over…
CSC 263 H1F
15. Consider the following algorithm:
InOrderTreeWalkx
1if xNIL then return
2InOrderTreeWalkx.left
3InOrderTreeWalkx.right
4Print x.key
Term Test
October 23 2019
This algorithm accepts the root node of a binary search tree and prints the stored keys in sorted order. This pseudocode
a would be correct if lines 1 and 2 were swapped b would be correct if lines 2 and 3 were swapped c would be correct if lines 3 and 4 were swapped d would be correct if lines 4 and 1 were swapped
e none of the above ANSWER: C
16. Consider the following algorithm:
TreeSearchx,k
1 if xNIL or kx.key then return x
2 if kx.key then return TreeSearchx.left, k
3 else return TreeSearchx.right, k
This algorithm accepts the root node of a binary search tree, and a target key value, and returns a pointer to the node storing the target key, or NIL if that key is not in the tree. This pseudocode
a has a bug on line 1 b has a bug on line 2 c has a bug on line 3
d more than one of the above e none of the above
ANSWER: E
17. Consider the following algorithm:
Unknownx
1 if x.right not NIL then return Unknownx.right
2 else return x.key
A better name for the function Unknown is a GetLeaf
b GetDepth
c GetMax
d GetMin e GetBF
ANSWER: C
page 4 of 12
contd. . .
October 23 2019 Term Test CSC 263 H1F
18. Consider these properties of a node in a binary search tree:P1. the node is a leaf
P2. the node is a parent of a leaf
P3. the node is a parent of one child
P4. the node is a parent of two chidren
P5. the balance factor of the node is 1, 0, or 1
A binary search tree is ideally balanced if and only if a every node satisfies at least one of P1, P3, P5 b every node satisfies at least one of P1, P2, P4
c every node satisfies at least one of P2, P3, P4
d every node satisfies at least one of P3, P4, P5 e none of the above
ANSWER: E
19. Referring to the same properties as above, a binary search tree is height balanced if and only if
a every node satisfies at least one of P1, P5 b every node satisfies at least one of P1, P4 c every node satisfies at least one of P2, P4 d every node satisfies at least one of P3, P5
e none of the above ANSWER: A
20. Universal hashing selects a hash functionin a way that isof the keys that are actually going to be stored. The missing words are:
a randomly, independent b randomly, dependent
c deterministically, independent d deterministically, dependent
e none of the above ANSWER: A
21. Consider a binary heap containing n elements. We want to insert n additional elements into this heap. The total time required for this is:
a logn b n
c nlogn d n2
ANSWER: C
22. In a binary maxheap containing n elements, the smallest element can be found in worstcase time:
a O1
b Ologlogn
c Ologn d On
ANSWER: D
23. A binary maxheap is given as an array as follows: 30, 14, 20, 13, 10, 8, 12. What is the content of the
array after two extractmin operations? a 14,13,8,12,10
b 14,12,13,10,8
c 14,13,12,8,10
d 14,13,12,10,8
ANSWER: C question contains a typo
page 5 of 12
over…
CSC 263 H1F Term Test October 23 2019
24. In hash tables, one advantage of chaining as opposed to open addressing is: a worst case time complexity of search operations is less
b worst case time complexity of insert operation is less
c space used is less
d deletion is easier ANSWER: B or D
25. Consider the following binomial heap:
1202
10 6414
8 13 15
11
Which of the following sequences of keys would not produce the binomial heap insert the leftmost item first.
a 15,4,14,2,8,11,13,6,10,0,12 b 11,8,6,13,4,15,2,14,10,0,12 c 4,15,2,14,13,8,6,11,10,0,12 d 13,6,11,8,4,15,2,14,10,12,0
ANSWER: C or D
page 6 of 12
contd. . .
October 23 2019 Term Test CSC 263 H1F
Question 2. Complexity. 15 marks
To earn exactly 20 write I dont know how to answer this question and cross out all other text. The 20 election applies to the entire question and cannot be selectively elected for subquestions.
A palindrome is a string of characters such that it reads the same backwards and forwards. The following algorithm takes a string S and determines whether or not it is a palindrome.
ispalindromeS:
1 2 3 4
for i0 to S.length1:
if Si ! SS.length i 1:
return False
return True
Parta 1mark
Give an example of a worstcase input of size n for ispalindrome.
Solution: an
Partb 6marks
Give functions f and g such that T nf n and T nOgn where T n is the worstcase running time of ispalindrome on an input of length n. Justify both choices.
Solutions: f ngnn. We have the worstcase behaviour when the if condition is never true, so i iterates from 0 to n1. This result is achieved when the input is a palindrome.
Solution:
Partc 2marks
Note that the slicing operation S0 : p takes constant time.
palindromeprefixS:
1 2 3
for pS.length to 1:
if ispalindromeS0:p:
return p
Give an example of a worstcase input of size n for palindromeprefix. 22
Solution: a n ba nPartd 6marks
Give functions f and g such that T nf n and T nOgn where T n is the worstcase running time of palindromeprefix on an input of length n. Justify both choices.
Solution: f ngnn2. We get the upper bound since the outer loop iterates n times, which in turn calls ispalindrome which runs in On.
We get the lower bound when running on the input described above. ispalindromeS0 : p returns false for pn to p n 1, with each call taking pn iterations of the loop inside ispalindrome. Next
2n2 ispalindrome return true in2iterations.
Total number of iterations is
n n n 2 p2
pn1 2
1
2
3 n2 4
nn
n2 2 j
j1 n
n2 2 j
j1
n nn1
2 2 22
page 7 of 12
over…
CSC 263 H1F Term Test October 23 2019 Question 3. Hashing. 20 marks
To earn exactly 20 write I dont know how to answer this question and cross out all other text. The 20 election applies to the entire question and cannot be selectively elected for subquestions.
Consider a hash table with m7 slots 0…6, hash function hkk mod 7, for integervalued keys in the range 0k42. We have two such hash tables. The hash table HC uses closedaddressing chaining, whereas the hash table HO uses openaddressing with linear probing. Our hash table implementations assume duplicate keys are not inserted. Our goal is to compare the behaviour of HC and HO under the same sequence of operations.
Parta 4marks
Starting with an empty hash table, consider inserting the keys 1, 9, 3, 10, 22 in that order. The same sequence of insertions is performed for both hash tables. Draw the configuration of HC after all values have been inserted.
Solution:
0 123 456 this legend is optional
nilnilnilnil VVV
22 9 10
VVV
1 nil 3
VV nil nil
Partb 4marks
Similarly, draw the configuration of HO after all values have been inserted. Solution:
1, 9, 3, 10, 22
0 1 2 3 4 5 6 legendisoptional
empty 1 9 31022 empty
Partc 2marks
After these five insertions have completed, consider performing a sixth insertion operation. List in order
the values of those stored keys that are read accessed by the operation HC .Insert15.
page 8 of 12 contd. . .
October 23 2019 Term Test CSC 263 H1F Solution:
No key values are readkey 15 is prepended to the linked list at
slot 1 this does not require reading the key value of the first node
at slot 1.
Partd 2marks
Similarly, list in order the values of those stored keys that are read accessed by the operation HO .Insert15. Solution:
1, 9, 3, 10, and 22 are read before an empty bucket is found.
Parte 2marks
After all six insertions have completed, consider performing a search operation. List in order the values
of those stored keys that are read accessed by the operation HC .Search22. Solution:
15, 22.
Partf 2marks
Similarly, list in order the values of those stored keys that are read accessed by the operation
HO .Search22. Solution:
1, 9, 3, 10, 22.
Partg 4marks
Modify the divisor in the hash function such that the same insertion sequence 1, 9, 3, 10, 22 has no
collisions. Show the sequence of five hashed values to prove that no collision occurs.
Solution: Ifhkk mod5,andsince9 mod54,10mod50,22 mod52,thenthefivekeyshash in this order to 1,4, 3, 0, 2, and so there are no collisions.
page 9 of 12 over…
CSC 263 H1F Term Test October 23 2019 Question 4. Design. 20 marks
To earn exactly 20 write I dont know how to answer this question and cross out all other text. The 20 election applies to the entire question and cannot be selectively elected for subquestions.
Cumulative sum. Let S be a finite set of integers without duplicates. Let Sbe an increasing sequence of integers containing exactly the values of S. The ith cumulative sum of S, denoted QiS, is the sum of the first i values of S , i.e., QiSik1 S k For example, if S3,1,9,5,2, then S 1,2,3,5,9, Q0S0, Q1S1, Q2S123, Q3S1236, Q4S123511, Q5S1235920.
Abstract Data Type. Consider the CSum abstract data type ADT. Values: The value of the CSum data type is any finite set of integers without duplicates, i.e., a set S. Operations: The operations on a CSum data type are:
Insertxinserts an integer x into the set S. It is assumed that x is not already in S.
CumulativeSumireturns QiS, the ith cumulative sum of S. It is assumed that in, where n is
the number of elements in S.
Example. Consider this example use case: CSum.Insert3
CSum.Insert1
CSum.Insert9
CSum.CumulativeSum3 … returns 13note: 139 CSum.Insert5
CSum.Insert2
CSum.CumulativeSum3 … returns 6note: 123 CSum.CumulativeSum5 … returns 20note: 12359
Problem statement. Describe an implementation of CSum that has worst case cost Ologn for both operations, Insert and CumulativeSum, where n is the number of elements in the set S.
Marking criteria. Your a data representation, b algorithms, and c argument showing Ologn com plexity must be clear, correct, and compelling. Do not reproduce pseudocode for algorithms covered in class, supplementary notes, or the textbook. If you build on such algorithms, clearly describe where and how your algorithm differs. Provide the simplest implementation that satisfies the requirements; overly complex solutions may receive no credit.
Solution: Student solutions may differ. One solution is to being with AVLs that have been already augmented to account for rank queries, and further augment to maintain for each node the sum of all values in the subtree. Given the rank information and the sum of values in the subtree, it becomes possible to compute the cumulative sum in log time.
page 10 of 12 contd. . .
October 23 2019 Term Test CSC 263 H1F Question 5. Heaps. 15 marks
To earn exactly 20 write I dont know how to answer this question and cross out all other text. The 20 election applies to the entire question and cannot be selectively elected for subquestions.
Parta 10marks
True or False: there exists a heap min or max T storing seven distinct elements such that an inorder
traversal visits the elements of T in sorted order. Justify your answer.
Solution: False. In any heap with at least 3 elements, the top two levels must be full by the heapshape property. Therefore, the root storing some value y has a left internal child storing some value x and a right internal child storing some value z. By the heaporder property and the fact that the keys are distinct, yx and yz. In any inorder traversal, x is visited before y, and y is visited before z. But xyz, so the inorder traversal does not visit x, y, z in sorted order.
Partb 5marks
True or False: In a minheap whose elements are all distinct, each element at depth i is less than each
element at depth i1. Justify your answer. Solution: False, counterexample:
152 6734
52 but is at a lower depth.
page 11 of 12
over. . .
CSC 263 H1F Term Test October 23 2019 Question 6. Expected Value. 10 marks
Assume we have an empty binary search tree not AVL or Red Black T and we do the following operations
INSERTT,1,INSERTT,2,,INSERTT,n
in some order. Assume all orders are equally likely. Since all operations on BST trees depend on the height of the tree, we are interested in Havgnthe expected height of T after the n inserts.
Parta 2marks
Define In, the set of possible INSERT orders.
Solution: All permutations of 1, 2,, n. There are n! such permutations, so each one has probability 1 . n!
Partb 4marks
Let Ai be the event that we insert i first. Write an expression for tAi, the expected height of the final tree
given that we insert i first, in terms of Havg.
Solution: If i gets inserted first, then i will be the root, the left subtree, L, will contain 1, 2,, i1 and the right subtree, R, will contain i1, i2,, n. L is just a tree built using a random permutation of 1, ,i1 and R is a tree built using a random permutation of i1, ,n but this tree will have the same height as a tree built using a random permutation of 1,, ni , since the operations dont depend onactualnumbers,justonorder. SoweexpectLtohaveheightHavgi1andRtohaveheightHavgni. Therefore,
.
Partc 4marks
Write a recurrence relation for Havg n.
Solution:
Each event Ai has probability 1 . We know n
tAimaxHavgi1,Havgni1
so we get the recurrence
n
Havgn tAiPrAi i1
1 n
Havgn n
maxHavgi1,Havgni1
page 12 of 12
end of test
i1
Reviews
There are no reviews yet.