=========================preview======================
(COMP271)[2010](f)midterm~ckngaa^_10197.pdf
Back to COMP271 Login to download
======================================================
For each subquestion, points are counted only when all relations are answered correctly. Points should not be counted when answers are partially correct, i.e. missing or including extra relations.
(a)
O, , (2 points)

(b)
O, , (2 points)

(c)
(2 points)

(d)
(2 points)

(e)
O, , (2 points)


2 Q2
Set h = log4 n
n
T (n)= n 2 +5T ()
4
nn
= n 2 +5( )2 +52T ()
442
nn n
= n 2 +5( )2 +52()2 +53T () (2points)
442 43

nn nn
= n 2 +5( )2 +52()2 + +5h.1()2 +5hT () (2points)
442 (42)h.1 4h 55 5 n
= n 2[1+ +( )2 + +( )h.1]+5hT ()
1616 16 4h 1 . ( 5 )h n
2 16
= n +5hT () (2points)
5 4h
1 .
16
16 5 n
= n 2[1 . ()log4 n]+5log4 nT ()
4log4 n
11 16
log4 5.log4 log4
= 16 n 2(1 . n16)+ n5T (1) (2points)
11
16 16

log4 5 log4
= n 2 . n+ n5T (1) (1point)
11 11
T (n)= O(n 2) (1point)

(a)
1.
Decrease the value of node x to k.

2.
Set Currnode = x.

3.
If Currnode is the root of T , done. Otherwise, set p = parent of Currnode.

4.
If value of Currnode < value of p, swap the value of Currnode and p, set Currnode = p and goto step


3.
We are traversing the path from x to the root of T and the height of T is O(log n). The comparison at each step worth O(1). Therefore, the running time of this algorithm is O(log n).
Marking Scheme: -Algorithm with min-heap concept worth 7 marks: Search for node x in O(log n) (-1 mark). Not mention stop at the root node in the recursive case (-2 marks). Bubble down after bubble up (-3 marks). Only determine whether to swap with parent, but not recursively do this until root node (-3 marks). -The running time analysis worth 3 marks. No explanation on why the algorithm runs in O(log n) (-2 marks).
(b)
-Build a min heap T contains the n integers // O(n log n) (or O(n) by the best well-known algorithm.)
-Extract-min on T for k times to extract and return the k smallest elements. // O(k log n) since each extract-min operation on T worth O(log n).
Therefore, the total running time of this algorithm is O(n log n) (or O(n + k log n)).
Marking Scheme: -Algorithm runs in O(n log n) worth 5 marks. Use sorting/selection algorithm runs in O(n2) in worst-case (-2 marks). Only return the k-th smallest element, but not the k smallest elements. (-2 marks).
(a) Denote the number of indices picked before x is found as a random variable Y .
..j.1
n . 11
P (Y = j)=
nn
(3 points)
The expected number of indices picked is

..j.1
n . 11
E[Y ]= j P (Y = j)= j
nn
j=1 j=1
(4 points)
which can be simpli.ed (this one possible way)

..j ..j.1
n . 1 n . 1 n . 11 n . 11
E[Y ]= j P (Y = j)= j =(j . 1)
nn nnnn
j=1 j=1 j=2
..j.1
1 n . 1 n . 11
E[Y ]= E[Y ] . E[Y ]=
n nnn
j=1
since
..j.1
n . 1
= n
n
j=1
therefore
E[Y ]= n
(3 points for the correctness of the derivation)
(b)
Algorithm 1: randomBi