CMPT307 21-1 Assignment 3 Answers 1
Due 16:00 March 1 (Monday). There are 100 points in this assignment.
Submit your answers (must be typed) in pdf file to CourSys
https://coursys.sfu.ca/2021sp-cmpt-307-d1/.
The work you submitted must be your own. Any collaboration and consulting outside
resources must be explicitly mentioned on your submission.
1. 10 points (Ex 10.1-2 of text book)
Explain how to implement two stacks in one array A[1..n] in such a way that neither
stack overflows unless the total number of elements in both stacks is n. Give the pseudo
codes for PUSH and POP operations in your implementation. The PUSH and POP
operations should run in O(1) time.
Ans: We call the two stacks L and R, L uses the first (left) part of A and R uses the
last (right) part of A. The top of L is the most right element of L and the top of R is
the most left element of R. Initially, L.top = 0 and R.top = n + 1.
PUSH(S, x)
if S = L then
if L.top + 1 = R.top then error ”overflow”
else {L.top = L.top + 1; L[L.top] = x}
if S = R then
if R.top− 1 = L.top then error ”overflow”
else {R.top = R.top− 1; R[R.top] = x}
(5 points)
POP(S)
if S = L then
if L.top = 0 then error ”underflow”
else {L.top = L.top− 1; return L[L.top + 1]}
if S = R then
if R.top = n+ 1 then error ”underflow”
else {R.top = R.top+ 1; return R[R.top− 1]}
(5 points)
2. 10 points (Ex 10.2-6 of text book)
The dynamic-set operation UNION takes two disjoint sets S1 and S2 as input, and it
returns a set S = S1 ∪ S2 consisting of all the elements of S1 and S2. Show how to
support UNION in O(1) time using a suitable list data structure.
Ans: Let L1 be a doubly linked list containing the elements of S1 and L2 be a dou-
bly linked list containing the elements of S2. We implement UNION as follows: Set
L1.nil.prev.next = L2.nil.next and L2.nil.next.prev = L1.nil.prev so that the last el-
ement of L1 is followed by the first element of L2. Then set L1.nil.prev = L2.nil.prev
and L2.nil.prev.next = L1.nil, so that L1.nil is the sentinel for the doubly linked list
containing all the elements of L1 and L2.
CMPT307 21-1 Assignment 3 Answers 2
3. 10 points (Ex 11.2-1 of text book)
A hash function h hashes n distinct keys into an array T of m elements. Assuming
simple uniform hashing, what is the expected number of all collisions, that is, the
expected value of |{{k, l}|k 6= l and h(k) = h(l)}|.
Ans: Assume the keys are totally ordered k1 ≤ .. ≤ kn. Let Xi be the number of keys
kj, j = i+ 1, .., n, so that h(kj) = h(ki). Then
E(Xi) =
n∑
j=i+1
Pr[h(kj) = h(ki)] =
n∑
j=i+1
1/m = (n− i)/m.
(5 points)
The expected number of all collisions is
n∑
i=1
E[Xi] =
n∑
i=1
(n− i)/m = (n2 − n(n+ 1)/2)/m = (n2 − n)/(2m).
(5 points)
4. 10 points (Ex 11.2-2 11.3-4 of text book)
(a) Hash function h(k) = k mod 9 is used to insert keys 5, 28, 19, 15, 20, 33, 12, 17, 10
into a hash table T [0..8] with collisions resolved by chaining. Show the result of the
hash table.
(b) Hash function h(k) = ⌊m(kA− ⌊kA⌋)⌋ for A = (√5 − 1)/2 is used to insert keys
61, 62, 63, 64, 65 into a hash table T [0..999]. Show the locations of the hash table to
which these keys are mapped.
Ans: (a) 10, 19, 28 are mapped to T [1], 20 is mapped to T [2], 12 is mapped to T [3], 5
is mapped to T [5], 33, 15 are mapped to T [6], 17 is mapped to T [8]. (5 points)
(b) 61 is mapped to T [700], 62 is mapped to T [318], 63 is mapped to T [936], 64 is
mapped to T [554], 65 is mapped to T [172]. (5 points)
5. 20 points (P 11-4 of text book)
A class H of hash functions which map the universe U of keys to {0, 1, .., m − 1} is
k-universal if, for every fixed sequence of k distinct keys (x1, .., xk) and for any hash
function h chosen at random from H, the sequence (h(x1), .., h(xk)) is equally likely to
be any of the mk sequences of length k with elements drawn from {0, 1, .., m− 1}.
(a) Show that if H is 2-universal then H is universal (1-universal).
(b) Assume that Alice and Bob secretly agree on a hash function h from a 2-universal
class H of hash functions. Each h ∈ H maps from a universe U of keys to Zp =
{0, 1, .., p − 1}, where p is prime. Later, Alice sends a message k to Bob over the
Internet, where k ∈ U . She authenticates this message to Bob by also sending an
authentication tag t = h(k), and Bob checks that the pair (k, t) he receives indeed
CMPT307 21-1 Assignment 3 Answers 3
satisfies t = h(k). Assume that an adversary intercepts (k, t) en route and tries to fool
Bob by replacing the pair (k, t) with a different pair (k′, t′) with k′ ∈ U and t′ = h′(k′)
for a randomly selected h′ ∈ H. Prove that the probability that the adversary succeeds
in fooling Bob into accepting (k′, t′) is at most 2/p.
Ans: (a) H is universal if for any distinct k, l ∈ U and h randomly selected from H,
Pr[h(k) = h(l)] = 1/m. For a 2-universal H, (h(k), h(l)) is equally likely to be any of
the m2 sequences of 2 elements of U . So, Pr[h(k) = h(l)] = Pr[(h(k), h(l)) = (x, x)] for
some x ∈ U which is m/m2 = 1/m. Hence, H is universal. (10 points)
(b) SinceH is 2-universal, there are at least p functions inH and thus, Pr[h′ = h] ≤ 1/p.
Further, for h′ 6= h, Pr[h′(k′) = h(k′)] ≤ 1/p. Therefore, the probability that the
adversary succeeds in fooling Bob to accept (k′, t′) is at most 1/p + 1/p = 2/p. (10
points) (A more detailed calculation on the probability: Let Pr[h′ = h] = q1 and
Pr[h′ 6= h and h′(k′) = h(k′)] = q2. Then the probability that the adversay fools Bob
is q1 + (1− q1)q2 = q1 + q2 − q1q2 ≤ q1 + q2 ≤ 1/p+ 1/p = 2/p.)
6. 15 points (P 12-2 of text book)
Given two strings a = a0a1..ap and b = b0b1..bq, where each ai and each bj is in some
ordered set of characters, string a is lexicographically less than string b, denoted as
a < b, if either
1 there exists an integer j with 0 ≤ j ≤ min{p, q}, such that ai = bi for all
i = 0, 1, .., j − 1 and aj < bj , or
2 p < q and ai = bi for all i = 0, 1, .., p.
For example, for binary strings a = 10100 and b = 10110, a < b (rule 1); for binary
strings a = 10100 and b = 101000, a < b (rule 2). This ordering is similar to that used
in English-language dictionaries.
Given a set A of binary strings, a radix tree data structure T can be used to store the
strings: T has a root node r. If there is prefix 0 (resp. prefix 1) in any string a ∈ A
then r has a left child (resp, right child). The edge between r and its left child (resp.
right child) is labelled 0 (resp. labelled 1). For any node x, let a0..aj be the labels
of edges visited when traversing from r to x. If there is prefix a0..aj0 (resp. prefix
a0..aj1) in any string a ∈ A then x has a left child (resp, right child). String a = a0..ap
is represented by the node x in T to which the labels of edges visited when traversing
from r are a0..ap. Figure 1 gives an example for strings 1011, 10, 011, 100, and 0. When
searching for a key a = a0..ap, we go left at a node of depth i if ai = 0 and right if
ai = 1. Given a set A of strings whose lengths sum to n represented by a radix tree T ,
design an algorithm in pseudo code to sort A using T lexicographically in O(n) time.
For the example in Figure 1, the output of the sort should be the sequence 0, 011, 10,
100, 1011. Prove the correctness and analyze the running time of your algorithm.
Ans: The sorting algorithm traverses T in preorder:
Preorder-Tree-Walk(T, x)
CMPT307 21-1 Assignment 3 Answers 4
if x 6= nil then
if x represents a string then print x;
Preorder-Tree-Walk(T, x.left);
Preorder-Tree-Walk(T, x, right);
The initial call is Preorder-Tree(T, r). (5 points)
Correctness: By the definition of the radix tree T , the word at a node u of T has a
smaller order than any word in the subtrees of u, and the word at a node in the left
subtree u has a smaller order than any word in the right subtree of u. Therefore, the
preorder traversal of T visits the words in T exactly in their lexicographical order. (5
points)
Running time: Since each node of T is visited one time and each visit takes O(1) time,
the running time of the algorithm is O(n). (5 points)
0 1
0
1
1
011
0
10
0 1
1
1011
Figure 1: A radix tree example.
7. 10 points (Ex 15.1-4 of text book)
Modify MEMOIZED-CUT-ROD to return not only the value but the actual solution,
too.
Ans: Create a new array s and initialize s to all 0 in MEMOIZED-CUT-ROD(p, n) and
pass it as an additional argument to MEMOIZED-CUT-ROD-AUX(p, n, r, s). Replace
line 7 in MEMOIZED-CUT-ROD-AUX by the following:
t = p[i]+MEMOIZEDCUTRODAUX(p, n − i, r, s).
Following this, if t > q, set q = t and s[n] = i. Upon termination, s[i] will contain the
size of the first cut for a rod of size i.
8. 15 points
Implement the algorithms Cut-Rod(p, n) (slide page 4), Memoized-Cut-Rod(p, n) (slide
page 6) and Bottom-Up-Rod(p, n) (slide page 7) discussed in class for the rod-cut
problem. Submit the code and report the running times of the three algorithms on a
same computer for n = 5, 10, 15, 20, 25, 30, respectively. For each instance size n, use
a same price table p to run the three algorithms.




































































































































































学霸联盟