This assignment is due on April 28 and should be submitted on Gradescope. All sub- mitted work must be done individually without consulting someone else’s solutions in ac- cordance with the University’s“Academic Dishonesty and Plagiarism”policies.

As a first step go to the last page and read the section: Advice on how to do the assignment.

Problem 1. (20 points)

Consider the following algorithm for testing if a given binary tree has the binary search tree property.

where rightmost-desc(v) is v if v.right = null and rightmost-desc(v.right) otherwise.

Your task is to either prove the correctness of this algorithm or provide a counter exam- ple where it fails to return the correct answer.

Problem 2. (40 points)

Suppose you have k sorted arrays A1, A2, . . . , Ak storing n = |A1|+|A2|+ · · · +|Ak| distinct keys. We want a data structure for maintaining a pinning pair (x, y), where x < y are keys in the union of the arrays. The data structure must support the following operations:

• initialize(): where x is set to the smallest key and y is set to the largest key in the union

• left-forward(): where x is set to the key that comes after x in the union (in sorted order)

• right-backward():  where y is set to the key that comes before y in the union (in sorted order)

Your task is to design a data structure that uses O(k) space (not counting the space used by the arrays), initialize takes O(k) time and the other operations run in O(log k) time.

Remember to

a) Design a data structure that supports the required operations in the required time and space.

b) Briefly argue the correctness of your data structure and operations.

c) Analyse the running time of your operations and space of your data structure. 

Problem 3. (40 points)

Let G = (V, E) be a connected undirected graph.  We define the risk factor of a vertex u as the number of pairs of vertices that cannot reach one another after removing u from G; more formally,

risk factor of u = |{(x, y) ∈ V − u × V − u : ∄ x-y path in G[V − u]1}|.

For example, in the following graph u has risk factor 6 because removing u disconnects the graph into two connected components having 2 and 3 nodes respectively.

Design an algorithm that computes the risk factor of a given vertex u in O(n + m) time.

Remember to:

a) describe your algorithm in plain English,

b) prove it correctness, and

c) analyze its time complexity.

To get full marks your algorithm must run in O(n + m) time. If you cannot make the stated bound, you can get partial credit by submitting a slower algorithm.