xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

扫码添加客服微信

扫描添加客服微信

算法代写-CMPT307 21-Assignment 3

时间：2021-03-11

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.

学霸联盟

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.

学霸联盟