USA: +1(669)289-8683 
Sign in
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
