To complete Quiz 1, fill out this form after 12:20 on Friday, Jan 5 and before 6:00PM Sunday, Jan 7.
Sample questions. These are intended to be suggestive, but they
are not a comprehensive representation of the style or content of the exam.
None of them is guaranteed to appear on the exam.
Note : n^2 means n squared. Omega means the greek letter capital omega, etc.
1. Which of the following is impossible for a function f(n) to
be ?
[A] O(n^2) and Omega(n^3) [B] O(n) and O(1),
[C] Theta(3n) and Theta(4n), [D] Omega(n) and Omega(n^2).
Answer: A.
2. Let A = {a, b} and D = {d, e}. Then A X D = ?
[A] {a, b, d, e}, [B] the empty set, [C] { (a, d), (b,
e) }, [D] { (a, d), (a, e), (b, d), (b, e) }, [E] { (a, a), (b, b), (d,
d), (e, e) }
Answer: D.
3. Let S = {a, b, c}. Then which relation is reflexive on S?
[A] {}, [B] { (a, a) }, [C] { (a, b), (b, a) }, [D] { (a, b),
(a, c), (a, c) }, [E] { (a, a), (a, b), (a, c), (b, b), (c, c) }
Answer: E.
4. Let S be the same set as in the previous question and let R = { (a,
b), (b, c), (a, c) }. Consider the statement ( $x
in S ) (x, x) in R
Is this true or false?
Answer: false.
5. Write a Java function that takes a String as input and returns a
Vector of the words occuring in that string.
(Answer not given here)
6. If a set is implemented using a linked list, then what should be
the asymptotic time complexity (in terms of n, the number of elements in
the set) for worst-case behavior, for inserting a new element into the
set?
Answer: Theta(n).
Sample questions:
1. In the UNION-FIND ADT it is common to use representative elements
a. to be the keys for hashing the sets;
b. to identify the set to which some given element belongs.
Ans: b.
2. Let B be a binary relation on a set S. If B is an equivalence
relation then it must be
a. reflexive but not necessarily symmetric
b. symmetric but not necessarily symmetric.
c. reflexive, symmetric, and transitive.
d. transitive and symmetric, but not necessarily reflexive.
Ans: c.
3. Show the sequence of AVL trees obtained by inserting the following
sequence of elements into an empty tree,
with each insertion being followed by any rebalancing that might be
necessary. 17, 20, 5, 13, 2, 6, 15, 14.
4. Suppose that a B-tree of order 5 contains a root and two other internal
nodes. The maximum number of keys
it can contain is therefore....
Ans 9 (1 in the root and 4 in each child of the root).
5. In the puzzle the Seven Bridges of Konigsberg, interpreted as a multigraph,
the number of Euler paths is
Ans. 0.
6. Describe the important properties of a hash function.
Ans. It should map any of the keys in its domain to an integer
index into the hash table; it should tend to scatter the keys uniformly
into the table; it should be fast to compute.
Note: Bring a standard answer sheet and some number 2 pencils to the
second midterm.
Sample questions:
1. Which of the following methods is part of the
Priority Queue ADT?
a. Delete-min
b. Dequeue
Ans: a.
2. Beginning with the 8 values 8,7,6,5,4,3,2,1 in elements
A[0] to A[7] of an array, create a binary heap. Assume that
A[0] is used to hold the root of the heap, the left child of
A[i] is at A[2i+1] and the right child of A[i] is at A[2i+2].
Initial tree:
8
7 6
5 4 3 2
1
Ans:
1
4 2
7 5 3 6
8
3. Suppose that an instance of the UNION-FIND ADT is created with
n singleton subsets containing integers: {1}, {2}, ..., {n}.
Suppose the implementation uses up-trees, but the UNION(x,y) operation
always makes the root of the tree for x be a child of the root of
the tree for y, regardless of the weights or heights of the trees.
What is the maximum height that any tree can have after a sequence
of UNION operations has been performed?
1 2 3
o------o------o------o
| | | |
4| 5| 6| 7|
| | | |
| 8 | 9 | 10 |
o------o------o------o
| | | |
11| 12| 13| 14|
| | | |
| 15 | 16 | 17 |
o------o------o------o
| | | |
18| 19| 20| 21|
| | | |
| | | |
o------o------o------o
22 23 24
Give a minimum spanning tree for this graph.
1 2 3
o------o------o------o
| | | |
4| 5| 6| 7|
| | | |
| | | |
o o o o
| | | |
11| 12| 13| 14|
| | | |
| | | |
o o o o
| | | |
18| 19| 20| 21|
| | | |
| | | |
o o o o
9. Consider the 0/1 Knapsack problem with a
knapsack of capacity 4 and the following available items:
(A) PC with value $800 and size 2, (B) stereo with value $500 and size 1,
and (C) violin with value $1200 and size 3.
Show the table of maximum values that would be created by the
dynamic programming method for solving this problem.
Capacity
1 2 3 4
________________________
Allowing A | 0 800 800 800
Allowing A,B | 500 800 1300 1300
Allowing A,B,C | 500 800 1300 1700