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.