[SOLVED] data structure algorithm theory CSCI 4101/5101 Test No. 2

CSCI 4101/5101 Test No. 2
Wednesday, April 6, 2016
MINI-ESSAYS. Answer the questions as completely as you can without being too wordy. The space provided should be a good indication of the length of answer required. If you do need additional space, you can write on the back of the sheets but clearly indicate where the continuation is located.
Explain how the textbook can even have a Ch. 8 about sorting with an O(n) complexity in light of the (nlgn) lower bound established in that very same chapter. Your answer should be substantive and should adequately cover the differences between sorting algorithms that submit to the (nlgn) lower bound and those that can achieve O(n) complexity. Supply examples as necessary. (10 pts.)
NAME _______________________________________________
Part I.
1.

CSCI 4101/5101 Test No. 2 2. Explain why MERGE-SORT is not an in-place sorting algorithm. (5 pts.)
3. Explain the differences and similarities (if any) between a heap and a binary search tree. Can a binary tree be both? Explain. (5 pts.)
Page 2

CSCI 4101/5101 Test No. 2
Part II. MULTIPLE CHOICE. Indicate the best answer from the five choices presented for each of the following questions. Record the answers in the provided scantron sheet. (1 pt. each)
1. Any correct sorting algorithm (of any type whatsoever binary-comparison-based and otherwise) admits this as a lower bound to the worst-case complexity of its performance.
a. (n2)
b. (n lg n)
c. (n)
d. (1)
e. None of these is an appropriate answer
2. Sorting algorithms that sort objects in place require O(1) auxiliary storage (on top of the space needed to store the values to be sorted). Assess the validity of this statement.
a. It is a valid statement.
b. It is not a valid statement.
3. All of these sorting algorithms sort objects in place except:
a. INSERTION-SORT
b. COUNTING-SORT
c. HEAP-SORT
d. BUBBLE-SORT
e. None of these is an appropriate answer
4. All of these sorting algorithms sort objects in linear time (worst-case or expected) except:
a. COUNTING-SORT
b. RADIX-SORT
c. BUCKET-SORT
d. All of these are linear time algorithms
e. None of these is a linear time algorithm
6.
7.
8.
9.
10.
In a binary search tree, the largest element is stored at _____.
a. a leaf
b. an internal node
c. the root
d. a node without a right child
e. a node without a left child
In a min-heap, the smallest element is stored at _____.
a. a leaf
b. an internal node
c. the root
d. a node without a right child
e. a node without a left child
In a binary search tree, the smallest element is stored at _____.
a. a leaf
b. an internal node
c. the root
d. a node without a right child
e. a node without a left child
Building a binary search tree from an input stream of sortable values can be done in at worst ____ time.
a. O(n2)
b. O(nlg n)
c. O(n)
d. O(1)
e. None of these is an appropriate answer
Building a binary search tree from an input stream of sortable values can be done in at best ____ time.
a. (n2)
b. (nlg n)
c. (n)
d. (1)
e. None of these is an appropriate answer
5. In
at _____.
a max-heap, the smallest element is stored
a. a leaf
b. an internal node
c. the root
d. There is not enough information to form
an answer.
e. None of these answers is valid.
Page 3

CSCI 4101/5101
Test No. 2
11. ________ is an optimal sorting algorithm 16. that makes use of a special binary tree that
can be used to efficiently implement priority
queues.
a. MERGE-SORT
b. INSERTION-SORT c. ATROCIOUS-SORT d. BUBBLE-SORT
e. HEAP-SORT
12. In HEAP-SORT, if the incoming array A is in reverse order, such as:
Then one can skip the preliminary BUILD- MAX-HEAP step because A is already a max-heap. Assess the validity of this statement.
a. It is a valid statement.
b. It is not a valid statement.
13. Binary search trees can be used to implement this data structure efficiently:
a. dictionary
b. priority queue
c. ordered list
d. stack
e. set
14. HEAP-SORT admits this as a lower bound on
its best-case running time:
a. (2n) 19.
b. (n2)
c. (nlg n)
d. (n)
e. (1)
15. HEAP-SORT admits this as an upper bound on
its worst-case running time:
a. O(2n)
b. O(n2)
c. O(nlg n)
d. O(n)
e. O(1)
Linear time sorting is impossible because ____.
a. objects cannot be sorted without binary comparisons
b. the (nlg n) lower bound to sorting is universal
c. not all input are presented in a linear container such as an array or a list
d. All of these are valid answers.
e. None of these is a valid answer (that is,
linear time sorting is, in fact, possible).
17. A decision tree is a binary tree that represents operations involving elements in sorting algorithms based on _____ comparisons.
a. unary
b. binary
c. imaginary d. real
e. deterministic
18. COUNTING-SORT determines the cumulative frequency distribution of the elements to be sorted. This information is then used to place those elements directly into their position in the sorted output. Assess the validity of this statement.
a. It is a valid statement.
b. It is not a valid statement.
COUNTING-SORT depends on this key assumption about the elements to be sorted:
a. They are in random order.
b. They have been normalized.
c. They are all distinct.
d. They are integers in the interval [0, k].
e. They are reals in the interval [0, 1).
20. COUNTING-SORT makes use of auxiliary storage that is more than O(1) thus making it an in-place sorting algorithm. Assess the validity of this statement.
a. The statement is valid.
b. The statement is not valid.
Page 4

CSCI 4101/5101
Test No. 2
21. RADIX-SORT is the algorithm that was once 26. used by sorting machines invented by _____
for the census of 1890, whose company later
became IBM.
a. Hermann Goering
b. Herman Hollerith
c. Hermans Hermits
d. Herman & Katnip
e. Hermann Hesse
22. RADIX-SORT requires that the intermediate sorting algorithm (the one that sorts on the basis of the digits) be stable, which means that numbers with the same value appear in the output array in the same ________ as they do in the input array.
a. order
b. location
c. index
d. cardinality e. parameter
23. If RADIX-SORT makes use of COUNTING-SORT as its intermediate sorting algorithm (the one that sorts on the basis of the digits) then it becomes an in-place sorting algorithm. Assess the validity of this statement.
a. The statement is valid.
b. The statement is not valid.
24. BUCKET-SORT assumes that the input is generated by a random process that distributes elements over [0,1) in this manner:
a. uniformly
b. normally
c. following a Poisson distribution
d. All of these are valid answers.
e. None of these is a valid answer.
25. The pseudo-code for BUCKET-SORT assumes that the input is an n-element array A and makes use of an auxiliary array B[0 .. n1]. This makes it an in-place sorting algorithm. Assess the validity of this statement.
a. The statement is valid.
b. The statement is not valid.
BUCKET-SORT has an expected time complexity of _______. In theory, it can have a worst-case time complexity of O(n2), although this is highly improbable.
a. (2n)
b. (n2)
c. (nlgn)
d. (n)
e. (1)
27. A hash table is effective for implementing a dictionary, a data structure that supports these functionalities: INSERT, SEARCH, and DELETE. Assess the validity of this statement.
a. The statement is valid.
b. The statement is not valid.
28. In an ordinary array, we store the element whose key is k in position k of the array. By contrast, in a hash table, we use an oracle to generate from the key k a value O(k) to index into the hash table. Assess the validity of this statement.
a. The statement is valid.
b. The statement is not valid.
29. The expected time to search for an element in a hash table is ______ under reasonable assumptions. However, the worst-case search time is (n).
a. O(2n)
b. O(n2)
c. O(nlg n)
d. O(lg n)
e. O(1)
30. Hash functions are one-to-one functions since they take whole numbers (i.e., keys) as argument and produce yet another whole number (array indices) as functional value. Assess the validity of this statement.
a. The statement is valid.
b. The statement is not valid.
Page 5

CSCI 4101/5101
Test No. 2
31. The analysis of hash table operations using chaining to resolve collisions is performed in terms of the load factor , which is the ratio of n, the number of elements in the table, and m, the number of slots in the table. This ratio can also be understood as this:
a. Best case performance of searches.
b. Average number of items in each of the
hash tables linked lists.
c. Best case performance of inserts.
d. All of these are appropriate answers.
e. None of these is an appropriate answer.
32. Hash functions assume that the keys are natural numbers. This assumption is not too severe because all keys are stored in binary anyway and can readily be interpreted as unsigned binary numbers. Assess the validity of this statement:
a. It is a valid statement
b. It is not a valid statement
33. Hash functions that use the division method, e.g., h(k) = k mod m, are fast but have the disadvantage of having to avoid certain values of m (e.g., powers of 2). Assess the validity of this statement:
a. It is a valid statement
b. It is not a valid statement
34. Hash functions that use the multiplication method, e.g., h(k) = m (k A mod 1), have the advantage of not having to avoid certain values of m but may be:
a. faster
b. slower
c. non-halting
d. incorrect
e. None of these is a valid answer.
35. In open addressing, the action of _________ a slot in the hash table is known as a probe.
a. clearing
b. examining
c. filling
d. destroying
e. rehashing
36. The technique known as linear probing suffers from the increasing probability of _____. This is when long runs occupied (or once occupied) hash table slots build up.
a. primary schooling
b. primary clustering
c. primary bundling
d. primary defragmenting e. prime numbers
37. The analysis of chained hashing resulted in the expected complexity of searches to be ______, where is the load factor.
a. O()
b. O(2)
c. O(lg )
d. O(1)
e. None of these is a valid answer.
38. Stringy binary search trees, such as those illustrated to the right, can be avoided by randomizing the input values. Assess the validity of this statement:
a. It is a valid statement
b. It is not a valid statement
39. There are this many maximally stringy binary search trees (where the height of the tree is n1 if there are n nodes in the tree):
a. n
b. n2
c. 2n1
d. n!
e. None of these is a valid answer.
40. There are these many shapes that a binary search tree can have where n is the number of nodes in the tree:
a. n
b. n2
c. 2n
d. n!
e. The nth Catalan number Cn , where
Page 6

CSCI 4101/5101 Test No. 2
Part III.
1.
PROBLEM-SOLVING. Perform the required operation(s) to achieve the desired solution(s). [Questions may look like the practice test but may, in fact, be different!]
Build a min-heap from the array A of integers below, by running BUILD-MIN-HEAP(A):
Your answer can be supplied as an array or as a binary tree like the one below (showing the initial configuration of the heap). Use the space below for your answer. (10 pts.)
Page 7

CSCI 4101/5101 Test No. 2
2. Supply the sequence of permutations that the following values undergo when RADIX-SORT is applied to them (they are illustrated here in column format). Supply your answer in the four columns below (the right-most one should list the values in increasing order; the intermediate columns should show the intermediate results of this O(n) sorting algorithm). (5 pts.)
Page 8

CSCI 4101/5101 Test No. 2 3. Suppose we were supplied a hash function h(k) = k mod 13. Let our hash table T consist of a
modest 13 slots, addressed by index values 0 through 12:
Supply the result of the insertion of the following key-value pairs (k, v) where the values v are letters of the alphabet. The desired result would show the letters as entries of the hash table. The first key-value pair has been processed for you. [NOTE: Useful multiples of 13 are listed for you at the bottom of the page.] (10 pts.)
Useful multiples of 13: 117 130 143 156 169 182 195 Page 9

CSCI 4101/5101 Test No. 2
4. Given the binary search tree T below that contains integers in its nodes, show the trees configuration after the execution of TREE_DELETE( T, 15). We supply the pseudo-code for the procedure below. Use the space below to illustrate your answer. (10 pts.)
Page 10

CSCI 4101/5101 Test No. 2
5. We discussed binary search trees in the context of implementing dictionaries. However, we can use them to implement a sorting algorithm BST-SORT that is also optimal on the average, that is has expected time complexity that is (nlg n). Below we list functionalities we assume are supported by binary search trees:
INORDER-TREE-HARVEST(A, T)
deposits in array A the keys in the binary search tree T in sorted order
TREE-INSERT(T, x)
inserts the value x into the binary search tree T
TREE-DELETE(T, x)
deletes the value x from the binary search tree T
Supply the missing elements of the algorithm BST-SORT using the functionalities listed above. The comments should give valuable hints as to what the correct answers should be. (5 pts.)
BST-SORT(A)
1 2 3
4 5
Let T be an empty binary search tree for i = 1 to A.length
x = A[i] ____________________________
(3 pts.)
_______________________________
(2 pts.)
insert contents of A into T insert x into T
deposit contents of T into A in sorted order
Estimate the worst-case time complexity of BST-SORT. Supply your answer below. Give a short explanation of your answer. (5 pts.)
BONUS:
Page 11