Homework Assignment #5 Solution

Question 1. (1 marks) We want a data structure that maintains a set I of integers and supports the following two operations:

1. Insert(x), insert a new integer x into I (assume that x is not already in I).

2. Search(x), which returns True if integer x is currently in I, and returns False otherwise.

If we keep I in a sorted array A, then, using binary search, the worst-case time for a Search(x) is O(log n), where n is the size of I. But the worst-case time for an Insert(x) is O(n), and the amortized insertion time (i.e., the worst-case total time to execute n Inserts divided by n) is also O(n). Our goal is to decrease the amortized insertion time, may be at the cost of increasing the worst-case time of Search.

To do so, we keep I in a doubly linked list L of sorted arrays as follows. Let n be the number of elements in I,

and < bk 1; bk 2; : : : ; b0 > be the binary representation of n; note that ii==0k 1bi2i = n and k = O(log2 n).

For every i = 0; 1; : : : ; k 1 such that bi = 1, the doubly-linked list L contains a sorted array Ai of size 2i; Ai stores 2i elements of I in increasing sorted order. The arrays of L are listed in order of increasing size. Each integer of I is in exactly one of the sorted arrays of L. Note that although each array of L is sorted, there is no particular relationship between the elements in di erent arrays of L.

a. Draw two instances of the data structure L, one for set I = f6; 8; 4; 13; 9g and one for set

• = f21; 12; 7; 14; 5; 16; 10g.

In the questions below, you should give as e cient algorithms as possible. Describe your algorithms in clear and concise English, there is no need to use pseudocode.

b. Describe an algorithm to perform a Search(x) operation with this data structure. Give a good upper bound on the worst-case time complexity of your algorithm (using the O notation) and justify your answer.

c. Describe an algorithm to perform an Insert(x) operation with this data structure. Give a good upper bound on the worst-case time complexity of your algorithm (using the O notation) and justify your answer.

Hint: Think about how we insert an element in a Binomial Heap, and use the Merge part of MergeSort.

d. Suppose we execute a sequence of n Inserts starting from an empty set I. Determine a good upper bound on the amortized time of an Insert (i.e., the worst-case total time to execute these n Inserts divided by n). Justify your answer in two di erent ways, i.e., give two separate proofs, each proof using a di erent argument (e.g., use aggregate analysis and the accounting method).

e. Describe an algorithm to perform a Delete(x) operation, i.e., given a pointer to integer x in one of the arrays of L, remove x, in O(n) time in the worst case. Explain why the worst-case time complexity of your algorithm is O(n).

Question 2. (1 marks) You are given an undirected, unweighted, and connected graph G = (V; E) that represents a set of houses and hospitals connected by roads as follows: each vertex in V is colored white if it represents a house, or black if it represents a hospital, and each edge (u; v) in E represents a road between vertices u and v that can be traversed in one unit of time.

Assume that you are given G by its adjacency list. We are seeking an algorithm to solve the following problem P: compute for each house vertex, the shortest time to reach some hospital vertex.

An example of a graph G and the shortest time to hospitals from each house in G is shown below:

a. Furio, an infamous csc263 alumnus, claims that if the number of houses is constant, then a graph algorithm that he learned in csc263 can be used in a very simple way to solve problem P in O(jV j + jEj) time in the worst-case.

Brie y explain why Furio is right; in particular, state which algorithm he has in mind and how it can be used to solve P.

In the questions below, the number of houses is not constant and the number of hospitals is k 1 (also not a constant).

b. Paulie, another infamous csc263 alumnus, claims the csc263 algorithm that Furio used in part (a) can be used to solve problem P in O(k(jV j + jEj)) time in the worst-case. Brie y explain why Paulie is right.

c. Tony, their csc263 teacher, claims he can do better than Paulie: he claims that there is an algorithm that can solve problem P in only O(jV j + jEj) time in the worst-case.

Is Tony right or is he just bragging? If he is right, describe Tony’s algorithm in clear and concise English. You should also brie y argue why its worst-case time complexity is O(jV j + jEj). If Tony is just bragging, please ignore this question.

[The questions below will not be corrected/graded. They are given here as interesting problems that use material that you learned in class.]

Question 3. (0 marks) A multi-set is like a set where repeated elements matter. For example, f1; 8; 3g and f3; 3; 8; 1; 8g represent the same set but di erent multi-sets. Consider the abstract data type that consists of a multi-set of integers S and supports the following operations:

Insert(S; x): insert integer x into multi-set S;

Diminish(S): delete the djSj=2e largest integers in S.

(For example, if S = f3; 3; 8; 1; 8g, then after Diminish(S) is performed, S = f3; 1g.)

A simple data structure for this ADT, and the corresponding algorithms for each operation, are as follows:

The elements of S are stored in an unsorted linked list, and the size of S is stored in a variable n.

Insert(S; x): Append x at the end of the list; increment n. Diminish(S):

i. m Med(S) nd the median of the elements in S

ii. loop over all elements in S: keep all those < m, delete all those m

iii. add as many copies of m as required to have exactly bn=2c elements remaining

iv. n bn=2c

The above uses an algorithm Med that returns the \median" of any list of integers. To simplify this question, we use a slightly non-standard de nition of \median": Med returns the dn=2e-th largest integer in the list (including duplicates); for example Med([3; 2; 1; 1; 3; 3; 3]) returns 3. Also for this question, assume that Med performs at most 5n pairwise comparisons between integers during its execution on any list of length n.

Prove that when we execute an arbitrary sequence of Insert and Diminish operations starting from an empty set S, the amortized cost of an operation, in terms of the number of pairwise comparisons between the elements of the set, is constant. To prove this, use the accounting method to analyse the amortized complexity of the Insert and Diminish algorithms: (a) state clearly what charge you assign to each operation, (b) state and prove an explicit credit invariant, and (c) use your credit invariant to justify that the amortized cost of an operation is constant.

Question 4. (0 marks) Consider the abstract data type maxqueue that maintains a sequence S of integers and supports the following three operations:

dequeue(S): removes the rst element of S and returns its value.

enqueue(S; x): appends the integer x to the end of S.

maximum(S): returns the largest integer in S, but does not delete it.

An element x is a su x maximum in a sequence if all elements that occur after x in the sequence are strictly smaller in value. For example, in the sequence 1,6,3,5,3, the su x maxima are the second, fourth, and fth elements.

One way to implement the maxqueue abstract data type is to use a singly linked list to represent the sequence S, with additional pointers first(S) and last(S) to the rst and last elements of that list; and to have a doubly linked list of the su x maxima (arranged in the same order as they are in the sequence), with an additional pointer suffix-max(S) to the rst element of that list. For example, the sequence

• = 1; 6; 3; 5; 3 would be represented as follows:

first(S)

1

6

3

5

3

last(S)

suffix-max(S)

a. Describe algorithms to implement each of the three operations (namely, dequeue(S), enqueue(S; x), and maximum(S)) for the maxqueue abstract data type using the above representation. For each oper-ation, rst explain the basic idea of how your algorithm works in a few clear English sentences; you can then give more details using English (and pseudo-code if necessary).

Your algorithms should be such that the operations have amortised complexity O(1), assuming that initially the maxqueue contains the empty sequence.

b. Prove that your algorithms achieve the desired amortised complexity. Hint: Use the accounting method.

c. Determine an asymptotic tight bound for the worst-case cost of an individual operation in a sequence of m operations. Justify your bound.

d. Find an alternative implementation of this abstract data type such that the worst-case time needed for an individual operation is O(log n), where n is the number of elements in the sequence. The amortised complexity in this case need not be O(1).

Question 5. (0 marks) Prove that every connected undirected graph G contains at least one vertex whose removal (along with all incident edges) does not disconnect the graph. Give an algorithm that for any connected graph G = (V; E), given by its adjacency list, nds such a vertex in O(jV j + jEj) time in the worst case. Justify your algorithm’s correctness and worst-case time complexity.

Question 6. (0 marks) Let G = (V; E) be an undirected graph. G is bipartite if the set of nodes V can be partitioned into two subsets V0 and V1 (i.e., V0 [ V1 = V and V0 \ V1 = ?), so that every edge in E connects a node in V0 and a node in V1. For example, the graph shown below is bipartite; this can be seen by taking V0 to be the nodes on the left and V1 to be the nodes on the right.

Note that G is bipartite if and only if every connected component of G is bipartite.

a. Prove that if G is bipartite then it has no simple cycle of odd length.1 Hint: Give a proof by contradiction.

b. Prove that if G has no simple cycle of odd length (i.e., every simple cycle of G has even length) then G is bipartite. (Hint: Suppose every simple cycle of G has even length. Perform a BFS starting at any node s. Assume for now that G is connected, so that the BFS reaches all nodes; you can remove this assumption later on. Use the distance of each node from s to partition the set of nodes into two sets, and prove that no edge connects two nodes placed in the same set.)

c. Describe an algorithm that takes as input an undirected graph G = (V; E) in adjacency list form. If G is bipartite, then the algorithm returns a pair of sets of nodes (V0; V1) so that V0 [ V1 = V , V0 \ V1 = ?,

• Recall that a cycle is simple if it contains each node at most once.

1

2 6

3 7

4 8

5

and every edge in E connects a node in V0 and a node in V1; if G is not bipartite, then the algorithm returns the string \not bipartite." Your algorithm should run in O(n + m) time, where n = jV j and m = jEj. Explain why your algorithm is correct and justify its running time. (Hint: Use parts (a) and (b).)

Question 7. (0 marks) You are riding your bike and you have an aerial map of the routes you could take. This map contains the (x; y)-coordinates of n bike pump stations. There is a straight bikeway that goes directly between any two bike pump stations. You want to travel from station s to station t. Since your tires aren’t very good, the best route from s to t is one that minimizes the distance that you have to travel between any two successive stations on this route. Your task is to design an O(n2 log n)-time algorithm for nding a best route.

a. Restate this task as a graph problem. To do so: (i) describe the graph: its vertices, edges, and edge weights, and (ii) restate the task as a graph problem on this graph.

b. We learned several algorithms that construct trees from an input graph. One these trees can be used to nd the desired path e ciently. Explain how and prove it.

c. Describe a corresponding algorithm for solving this problem in plain and clear English.

d. Explain why the worst-case running time of your algorithm is O(n2 log n).

Note: your algorithm can use any algorithms that we studied in the course as \black-boxes," and you can refer to their worst-case time complexity as stated in lecture or in the textbook.