CS180 Midterm Exam

1. (20 pt) Determine whether the following statements are true or false.

(a) (5 pt) 2n = Θ(3

n

)

(b) (5 pt) Suppose G is a connected, undirected graph. If removing an edge disconnects the graph, then

the edge is a tree edge in the DFS tree.

(c) (5 pt) Suppose G is a DAG and s is the first node in the topological ordering, t is the last node in the

topological ordering, then there is always a path from s to t.

(d) (5 pt) For any undirected connected graph G, there exists at least two nodes such that removing the

nodes won’t disconnect the graph.

2. (20 pt) As we learned in the class, a min-heap is useful when we are interested in the minimum value of

set of numbers. Now, instead of the min, we are interesting in the K-th smallest value.

(a) (10 pt) Please design a data structure to allow the following two operations: push (insert a new

number) and find_Kmin (return the value of the K-th smallest number without removing it). Both

operations should be done in O(log K) time.

(b) (10 pt) In addition to push and find_Kmin, now we also want to support the pop operation to

return and remove the K-th smallest element. Please design a data structure to support these three

operations, and each operation should take O(log n) time with n being the size of the current set.

3. (20 pt) For a stable marriage problem with n men and n women, let m1

, m2 be two of the men, w1

, w2 be

two of the women. Suppose m1

’s preference list is w1 > w2 > . . . ; m2

’s preference list is w2 > w1 > . . . ;

w1

’s preference list is m2 > m1 > . . . ; w2

’s preference list is m1 > m2 > . . . (we only know the favorite and

the second favorite of each of these four persons).

(a) (10 pt) Show that in every stable matching, m1

, m2 are matched to w1

, w2

(which means we either

have (w1

, m1

),(w2

, m2

) or (w1

, m2

),(w2

, m1

) in a stable matching).

(b) (10 pt) For any even n, construct an instance of stable matching problem (i.e., provide a set of preferences) with at least 2n/2

stable matchings. Justify your claim.

4. (20 pt) Indiana Jones is stuck in the Emperor’s Tomb and needs to find a way out. In front of him, there

are n consecutive doors, each door is behind the previous, and he needs to open all the doors to get out. In

the control room, there are n switches where each switch connects to a different door but he doesn’t know

which switch controls which door. Each switch can either be in an up or down position. but unfortunately,

for some doors the “up” position will open the door while for others the “down” position will open the

door. He needs to place all the n switches in the correct configuration to open all the doors. In order to

find the correct configuration, each time Indiana Jones can walk to the control room, set the switches to

any configuration, and walk back to check which is the first closed door (since the doors are consecutive,

he cannot observe the status of doors behind the first closed one). Design an algorithm to find the correct

configuration to open all the doors within O(n log n) trials.

Figure 1: Illustration of Problem 3. In this case there are n = 4 doors, and 4 switches controlling those doors. He

can only see the state of doors 1 and 2, not 3 or 4

5. (20 pt) There’s a 1D segment and you want to travel from west-most point (s) to the east-most point (t).

There are n teleporters on this 1D segment and each teleporter has two endpoints. Whenever you reach one

endpoint, it will teleport you to another endpoint (it may transport you from east to west or west to east,

depending on which endpoint you reach). All the endpoints are located between s and t and none of the

endpoints are located at the same position. We assume you must always move eastward on the segment.

Figure 2: An example for Problem 5. We are given an input with 4 teleporters with endpoints a1

, a2

; b1

, b2

; c1

,c2

,

d1

, d2

. Starting from s, you should keep moving to the right, so the path will be s (walk to) a1

(teleport to) a2

(walk to) c1

(teleport to) c2

(walk to) b2

(teleport to) b1

(walk to) a2

(teleport to) a1

(walk to) b1

(teleport to)

b2

(walk to) t, and the path has reward t since you are teleported 5 times.

(a) Prove that no matter how those teleporters are placed, you will always reach the t. (Hint: you can

view this as a graph problem, where each segment is a node, and each one has an edge pointing to

the next segment)

(b) Now you are allowed to add another set of K teleporters (each with two endpoints). How to place

those endpoints to maximize the number of times you get teleported in your trip from left-most point

to right-most point? Given the input of the locations of existing teleporters and the number K, design

an algorithm to solve this problem in O(n)

Sale!