Introduction to Algorithms
December 16, 2011
Massachusetts Institute of Technology
6.006 Fall 2011
Professors Erik Demaine and Srini Devadas
Final Exam Solutions
Final Exam Solutions
Problem 1. True/False
[36 points] (18 parts)
Circle (T)rue or (F)alse. You don’t need to justify your choice.
(a) T F
[2 points] Polynomial: good. Exponential: bad.
Solution:
True. This is a general rule-of-thumb mentioned in lecture.
(b) T F
[2 points] Radix sort runs correctly when using any correct sorting algorithm to
sort each digit.
Solution:
False. It must use a stable sorting algorithm.
(c) T F
[2 points] Given an array
A
[1
: : n
]
of integers, the running time of Counting Sort
is polynomial in the input size
n
.
Solution:
False. Counting Sort’s running time depends on the size of the num-
bers in the input, so it is pseudo-polynomial.
(d) T F
[2 points] Given an array
A
[1
: : n
]
of integers, the running time of Heap Sort is
polynomial in the input size
n
.
Solution:
True. Heap Sort runs in
O
(
n
log
n
)
time on a RAM machine.
(e) T F
[2 points] Any
n
-node unbalanced tree can be balanced using
O
(log
n
)
rotations.
Solution:
False. The worst-case unbalanced tree is a list, and balancing it re-
quires
(
n
)
rotations.
(f) T F
[2 points] If we augment an
n
-node AVL tree to store the size of every rooted
subtree, then in
O
(log
n
)
we can solve a
range query
: given two keys
x
and
y
,
how many keys are in the interval
[
x; y
]
?
Solution:
True. The question describes range trees, as implemented in Problem
Set 3.
(g) T F
[2 points] AVL trees can be used to implement an optimal comparison-based
sorting algorithm.
6.006 Final Exam Solutions
Name
2
Solution:
True. AVL trees can be used to sort
N
numbers in
O
(
N
log
N
)
time,
by inserting all the numbers in the tree, and iteratively calling N
EXT
-L
ARGEST
N
times.
(h) T F
[2 points] Given a connected graph
G
= (
V; E
)
, if a vertex
v
2
V
is visited
during level
k
of a breadth-first search from source vertex
s
2
V
, then every path
from
s
to
v
has length at most
k
.
Solution:
False. The level of a vertex only provides the length of the
shortest
path from
s
.
(i) T F
[2 points] Depth-first search will take
(
V
2
)
time on a graph
G
= (
V; E
)
repre-
sented as an adjacency matrix.
Solution:
True. In this case, finding the neighbors of a vertex takes
O
(
V
)
time,
which makes the total running time
(
V
2
)
.
6.006 Final Exam Solutions
Name
3
(j) T F
[2 points] Given an adjacency-list representation of a directed graph
G
= (
V; E
)
,
it takes
O
(
V
)
time to compute the in-degree of every vertex.
Solution:
False. The adjacency list structure needs to be traversed to find the
incoming edges for each vertex. This structure has total size
(
V
+
E
)
, so this
takes
(
V
+
E
)
time to compute.
(k) T F
[2 points] For a dynamic programming algorithm, computing all values in a
bottom-up fashion is asymptotically faster than using recursion and memoization.
Solution:
False. A bottom-up implementation must go through all of the sub-
problems and spend the time per subproblem for each. Using recursion and mem-
oization only spends time on the subproblems that it needs. In fact, the reverse
may be true: using recursion and memoization may be asymptotically faster than
a bottom-up implementation.
(l) T F
[2 points] The running time of a dynamic programming algorithm is always
(
P
)
where
P
is the number of subproblems.
Solution:
False. The running time of a dynamic program is the number of
subproblems times the time per subproblem. This would only be true if the time
per subproblem is
O
(1)
.
(m) T F
[2 points] When a recurrence relation has a cyclic dependency, it is impossible
to use that recurrence relation (unmodified) in a correct dynamic program.
Solution:
True. We need to first perform a modification like the one seen in the
recitation notes.
(n) T F
[2 points] For every dynamic program, we can assign weights to edges in the
directed acyclic graph of dependences among subproblems, such that finding a
shortest path in this DAG is equivalent to solving the dynamic program.
Solution:
False. We saw a counter-example where we couldn’t do this in the
matrix parenthesization problem.
(o) T F
[2 points] Every problem in NP can be solved in exponential time.
Solution:
True. NP is contained in EXP.
(p) T F
[2 points] If a problem
X
can be reduced to a known NP-hard problem, then
X
must be NP-hard.
6.006 Final Exam Solutions
Name
4
Solution:
False. The reverse, however, is true: if a known NP-hard problem
can be reduced to
X
then
X
must be NP-hard.
(q) T F
[2 points] If P equals NP, then NP equals NP-complete.
Solution:
True. A problem
X
is NP-hard iff any problem in NP can be reduced
in polynomial time to
X
. If P equals NP, then we can reduce any problem in NP
to any other problem by just solving the original problem.
(r) T F
[2 points] The following problem is in NP: given an integer
n
=
p
q
, where
p
and
q
are
N
-bit prime numbers, find
p
or
q
.
Solution:
True. An answer
a
to the problem can be checked in polynomial time
by verifying that
n
mod
a
= 0
(and
a
is not 1 or
n
). So the factoring problem is
in NP. Cryptographic systems (e.g. RSA) often assume that factoring is not in P.
False was also accepted because this is not a decision problem.
