for zext only..hw help
pravglad
m482_exam1_su12key.pdf
M482 Exam #1-KEY
Thursday, June 7, 2012
Name_____________________
1_____ 20 max
2_____ 20 max
3_____ 20 max
4_____ 20 max
5_____ 20 max
∑ _____ 100 max possible
2
1. Check each box that is true. One point for each correctly checked-or unchecked- box. One point for each correct mark, or lack of a mark. 20 points max.
€
f n( ), g n( )
€
f n( ) = Ω g n( )( )
€
f n( ) = Ο(g(n)) ________________________________________________
€
lglg n n, n ☒
€
n!, 2πn ⋅ n e ⎛
⎝ ⎜ ⎞
⎠ ⎟ n +1
☒
€
1 + 1
lgn ⎛
⎝ ⎜
⎞
⎠ ⎟
lg n
, 1 ☒ ☒
€
e1.14471n, πn ☒
€
Fn, 1.6181 n ☒
where
€
Fn is the
€
nth Fibonacci number
€
lgn, ln n( ) ☒ ☒
€
lgn⎣ ⎦!, lgn⎡ ⎤! ☒
€
lg 1⋅ 3⋅ 5⋅ 7⋅ ... ⋅ 2n + 1( )( ), lg 2n( )!( )☒ ☒
€
n ⋅ Hn, lg n!( ) ☒ ☒ where
€
Hn is the
€
nth Harmonic number
€
kk
k! ekk=1
n
∑ , Hn ☒
3
2. In each of the following five problems below, the running times of two algorithms are described by recurrences as given. The solutions to the recurrences are given. If the Master Method (MM) is relevant to a given recurrence, specify which case applies. If the MM does not apply, write N/A next to the recurrence. Finally, identify which algorithm runs faster (in each pair). If equal, then write, “equal.” One point for each correct identification of method, and two points for identifying the fastest one-or for writing “equal,” if they have the same asymptotic speed. Max 4 points per problem, 20 points max.
I
€
T1 n( ) = 6T1 n 2 ⎛
⎝ ⎜ ⎞
⎠ ⎟ + n lg 5 =
MM 1 Θ n lg 6( )
€
T2 n( ) = 152T2 n 7 ⎛
⎝ ⎜ ⎞
⎠ ⎟ + n log 7 152 =
MM 2 Θ n log7 152 lgn( ) FASTER
II
€
T3 n( ) = 3T3 n 2 ⎛
⎝ ⎜ ⎞
⎠ ⎟ + n2 lgn =
MM 3 Θ n2 lgn( ) FASTER
€
T4 n( ) = 3T4 n 2 ⎛
⎝ ⎜ ⎞
⎠ ⎟ + lg2 n!( ) =
MM 3 Θ n2 lg2 n( )
III
€
T5 n( ) = T5 n 2 ⎛
⎝ ⎜ ⎞
⎠ ⎟ +
e.6934n
n3 =
MM 3 Θ
e.6934 n
n3 ⎛
⎝ ⎜
⎞
⎠ ⎟
€
T6 n( ) = 8T6 n 2 ⎛
⎝ ⎜ ⎞
⎠ ⎟ + n2 ⋅ 2n =
MM 3 Θ n2 ⋅ 2n( ) FASTER
IV
€
T7 n( ) = 8T7 n 2 ⎛
⎝ ⎜ ⎞
⎠ ⎟ + lgn( )
2 lg n = MM 1
Θ n3( ) FASTER
€
T8 n( ) = 16T8 n 2 ⎛
⎝ ⎜ ⎞
⎠ ⎟ + lgn⎡ ⎤! =
MM 3 Θ lgn⎡ ⎤!( )
V
€
T9 n( ) = 2T9 n 2 ⎛
⎝ ⎜ ⎞
⎠ ⎟ + 2( )
lg n 2 =
MM 1 Θ n( )
€
T10 n( ) = 2T10 n 3 ⎛
⎝ ⎜ ⎞
⎠ ⎟ + 3 2 lg n =
MM 1 Θ n log 3 2( ) FASTER
4
3. Consider the following sorting algorithm (which you may assume is correct), called initially with i = 1 and j = n to sort a list of n numbers in array A:
Sort(A, i, j)
1 if A[i] > A[j] 2 then exchange
€
A[i]↔ A[ j] 3 if i + 1 ≥ j 4 then return 5
€
k ← j − i +1( )/3⎣ ⎦ 6 Sort(A, i, j - k) 7 Sort(A, i + k, j) 8 Sort(A, i, j - k)
Suppose SORT takes as input list
€
7, 2, 3, 4, 5, 6, 1( ). During its execution, how many comparisons are made between elements in A?
ANSWER ONLY _____121_____ (20 points)
5
4. Consider the Merge-‐Sort algorithm as presented (via pseudocode) in the text, and analyzed in the homework. Create an input list from the numbers in the set
€
1, 2, 3, 4, 5, 6, 7{ } that elicits the worst-‐case performance, if performance is measured solely in terms of comparisons between elements in the list. (Do not count comparisons to sentinels.) How many comparisons are made?
ANSWER ONLY-‐input list: There are many possibilities. For instance,
(1, 3, 2, 7, 4, 5, 6) elicits the worst case. (10 points)
ANSWER ONLY-‐number of comparisons made: 14 (10 points).
6
5. Consider the following decision tree for determining the median of five numbers a, b, c, d, and e, with at most five comparisons. Note that the comparison b:e occurs on the right and left children of a:c.
Determine which of the five numbers is
L1 (answer only) ______b_____
L2 (answer only) ______b_____
L3 (answer only) _____c____
L4 (answer only) _____d____ (5 points per correct answer, 20 max)
[Note: For the decision tree below, L5 is not uniquely determined. Therefore this tree does not determine the median in less than six comparisons. A correct right branch from the node a:c is drawn in blue on the bottom of the page, replacing the section drawn in red.]
a:b
c:d symm
a:c symm
b:e b:e
b:c e:c d:b d:e
e:c b:d b:c e:d d:a L1 e:a d:a
e c b d L2 L3 e d a d e d L4 L5
a:d
e:a e:d
a e:b d e:a
e b e a
