Solved–Assignment 2: Decremental Design– Solution

Description

1. Binary GCD algorithm: Most computers can perform the operations of subtraction, testing the parity (odd or even) of a binary integer, and halving more quickly than computing remainders. This problem investigates the binary gcd algorithm, which avoids the remainder computations used in Euclid’s algorithm.

(a) Prove that if a and b are both even, then gcd(a; b) = 2 gcd(a=2; b=2).

(b) Prove that if a is odd and b is even, then gcd(a; b) = gcd(a; b=2).

(c) Prove that if a and b are both odd, then gcd(a; b) = gcd((a b)=2; b).

(d) Design an e cient binary gcd algorithm for input integers a and b, where a b, that runs in O(lg a) time. Assume that each subtraction, parity test, and halving takes unit time. [ lg a is the same as log2 a. ]

2. Analysis of bit operations in Euclid’s algorithm.

(a) Consider the ordinary \paper and pencil” algorithm for long division: dividing a by b, which yields a quotient q and remainder r. Show that this method requires O((1 + lg q) lg b) bit operations.

(b) De ne (a; b) = (1 + lg a)(1 + lg b). Show that the number of bit operations performed by Euclid(a; b) in reducing the problem of computing gcd(a; b) to that of computing gcd(b; a mod b) is at most c( (a; b) (b; a mod b)) for some su ciently large constant c > 0.

(c) Show that Euclid(a; b) requires O( (a; b)) bit operations in general and O( 2) bit operations when applied to two -bit inputs.

(d) If a > b 0, show that the call Euclid(a; b) makes at most 1 + log b recursive calls. Improve this bound to 1 + log (b=gcd(a; b)).

3. Suppose you are given an array A with n entries, with each entry holding a distinct number. You are told that the sequence of values A[1]; A[2]; : : : ; A[n] is unimodal: For some index p between 1 and n, the values in the array entries increase up to position p in A and then decrease the remainder of the way until position n. (So if you were to draw a plot with the array position j on the x-axis and the value of the entry A[j] on the y-axis, the plotted

points would rise until x-value p, where they’d achieve their maximum, and then fall from there on.)

You’d like to nd the \peak entry” p without having to read the entire array-in fact, by reading as few entries of A as possible. Show how to nd the entry p by reading at most O(log n) entries of A.

4. Consider an n-node complete binary tree T , where n = 2d 1 for some d. Each node v of T is labelled with a real number xv. You may assume that the real numbers labelling the nodes are all distinct. A node v of T is a local minimum if the label xv is less than the label xw for all nodes w that are joined to v by an edge.

You are given such a complete binary tree T , but the labelling is only speci ed in the following implicit way: for each node v, you can determine the value xv by probing the node v. Show how to nd a local minimum of T using only O(log n) probes to the nodes of T .

5. Suppose now that you’re given an n n grid graph G. (An n n grid graph is just the adjacency graph of an n n chessboard. To be completely precise, it is a graph whose node set is the set of all ordered pairs of natural numbers (i; j), where 1 i n and 1 j n;

the nodes (i; j) and (k; l) are joined by an edge if and only if ji kj + jj lj = 1.

We use some of the terminology of the previous question. Again, each node v is labeled by a real number xv; you may assume that all these labels are distinct. Show how to nd a local minimum of G using only O(n) probes to the nodes of G. (Note that G has n2 nodes.)

6. Majority Element.

(a) Let T [1 : : : n] be an array of n elements. An element x is said to be a majority element

in T if jfi j T [i] = xgj > n=2. Give an algorithm that can decide whether an array T [1 : : : n] includes a majority element (it cannot have more than one), and if so nd it. Your algorithm must run in linear time.

(b) Rework the above problem with the supplementary constraint that the only comparisons allowed between elements are tests of equality. You may therefore not assume that an order relation exists between the elements.

7. Suppose S = f1; 2; : : : ; ng and f : S ! S. If R S, de ne f(R) = ff(x) j x 2 Rg. Device an O(n) algorithm for determining the largest R S, such that f(R) = R.

8. You are a contestant on the hit game show \Beat Your Neighbours!” You are presented with an m n grid of boxes, each containing a unique number. It costs $100 to open a box. Your goal is to nd a box whose number is larger than its neighbours in the grid (above, below, left, and right). If you spend less money than any of your opponents, you win a week-long trip for two to Las Vegas and a year’s supply of Rice-A-RoniTM, to which you are hopelessly addicted.

Page 2

(a) Suppose m = 1. Describe an algorithm that nds a number that is bigger than any of its neighbours. How many boxes does your algorithm open in the worst case?

(b) Suppose m = n. Describe an algorithm that nds a number that is bigger than any of its neighbours. How many boxes does your algorithm open in the worst case?

(c) Prove that your solution to part (b) is optimal up to a constant factor.

9. Suppose we are given two sorted arrays A[1 : : : n] and B[1 : : : n] and an integer k. Describe an algorithm to nd the k-th smallest element in the union of A and B in O(log n) time. (For example, if k = 1, your algorithm should return the smallest element of A [B; if k = n, your algorithm should return the median of A [B.) You can assume that the arrays contain no duplicate elements. [Hint: First solve the special case k = n.]

(a) Now suppose we are given three sorted arrays A[1 : : : n], B[1 : : : n], and C[1 : : : n], and an integer k. Describe an algorithm to nd the k-th smallest element in A [ B [ C in O(log n) time.

(b) Finally, suppose we are given a two dimensional array A[1 : : : m][1 : : : n] in which every row A[i][ ] is sorted, and an integer k.Describe an algorithm to nd the k-th smallest element in A as quickly as possible. How does the running time of your algorithm depend on m? [Hint: Use the linear-time Select algorithm as a subroutine.]

10. For this problem, a subtree of a binary tree means any connected subgraph. A binary tree is complete if every internal node has two children, and every leaf has exactly the same depth. Describe and analyze a recursive algorithm to compute the largest complete subtree of a given binary tree. Your algorithm should return the root and the depth of this subtree.

The largest complete subtree of this binary tree has depth 2.

11. You are given a sorted array of numbers where every value except one appears exactly twice; the remaining value appears only once. Design an e cient algorithm for nding which value appears only once.

Here are some example inputs to the problem:

112234455667788

10 10 17 17 18 18 19 19 21 21 23

133557788991010

Page 3

Clearly, this problem can be solved in O(n) time, where n is the number of elements in the array, by just scanning across the elements of the array one at a time and looking for one that isn’t paired with the next or previous array element. But can we do better?

12. You are given n balls with some of them coloured red and some black. Your mission is to identify a ball with a majority colour (if it exists). Here, majority means strictly more than other colour. You may pick two balls and ask if these two balls have same colour. What is the minimum number of queries needed for the task?

13. You are given n identical looking gold coins where some are genuine and some are fake. Coins of same type have same weight, i.e., all fakes have weight and all genuine ones have weight b, but you do not know the values or relative values of a or b. You are given a balance which can be used to test if two coins have same weight or not. It is known that number of genuine coins is more than number of false coins. Find a genuine coin in as few weighings as possible.

14. The problem consists of nding the lowest oor of a building from which a box would break when dropping it. The building has n oors, numbered from 1 to n, and we have k boxes. There is only one way to know whether dropping a box from a given oor will break it or not. Go to that oor and throw a box from the window of the building. If the box does not break, it can be collected at the bottom of the building and reused. The goal is to design an algorithm that returns the index of the lowest oor from which dropping a box will break it. The algorithm returns n + 1 if a box does not break when thrown from the nth oor. The cost of the algorithm, to be kept minimal, is expressed as the number of boxes that are thrown (note that re-use is allowed).

(a) For k > log(n), design an algorithm with O(log(n)) boxes thrown.

(b) For k < log(n), design an algorithm with O(k + 2kn 1 ) boxes thrown.

(c) For k = 2, design an algorithm with O(n) boxes thrown.

15. Alice controls 2 cops and Bob controls one thief in an n n rectangular grid. On a move Alice can move each cop to a neighbour or leave there without moving. Bob can do that for the thief. Show how Alice can nab the thief in 3n moves.

16. We have n threads with each one having a bead. We want to line up all the beads vertically by moving them along the threads. The objective is to minimize the total distance moved. Given n numbers denoting the positions of beads, design a linear time algorithm to nd the minimum total distance the beads have to be moved in order to line them up.

Page 4

17. Let F be an array of size n 1 whose elements are 0 or 1. A section [i; : : : ; j] of consecutive elements of F , with 1 i j n, is balanced if it contains as many 0 as 1

elements. The length of a balanced section [i; : : : ; j] is its number of elements, j i + 1.

Design an algorithm to nd the longest balanced section of F.

18. Professor Diogenes has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The professor’s test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the professor cannot trust the answer of a bad chip. Thus, the four possible outcomes of a test are as follows:

Chip A says Chip B says Conclusion

B is good A is good Both are good or both are bad
B is good A is bad At least one is bad
B is bad A is good At least one is bad
B is bad A is bad At least one is bad

(a) Show that if more than n = 2 chips are bad, the professor cannot necessarily determine which chips are good using any strategy based on this kind of pairwise test. Assume that the bad chips can conspire to fool the professor.

(b) Consider the problem of nding a single good chip from among n chips, assuming that more than n = 2 of the chips are good. Show that bn=2c pairwise tests are su cient to reduce the problem to one of nearly half the size.

(c) Show that the good chips can be identi ed with (n) pairwise tests, assuming that more than n = 2 of the chips are good. Give and solve the recurrence that describes the number of tests.

19. You are given a sorted array of numbers where every value except one appears exactly twice; the remaining value appears only once. Design an e cient algorithm for nding which value appears only once. Clearly, this problem can be solved in O(n) time, where n is the number of elements in the array, by just scanning across the elements of the array one at a time and looking for one that isn’t paired with the next or previous array element. But can we do better?

20. There are n identical boxes in which 2n balls are equally distributed. The balls are labelled from 1 to 2n. We don’t know which ball is in which box, but do know that each box contains two balls. The objective is to learn the arrangement of balls. For any set of balls S f1; : : : ; 2ng we can ask a query of the form ‘How many boxes contain the balls in S?’. Prove that we can learn the distribution of balls by asking O(n log n) queries. Note that we cannot tell which ball is in which box. We only need to report the set of n pairs of balls.

Page 5

21. Given a function f : S ! S (that maps a natural number from a nite set S to another natural number in the same nite set S and an initial value x0 2 N, the sequence of iterated
function values: fx0; x1 = f(x0); x2 = f(x1); : : : ; xi = f(xi 1); : : :g must eventually use the same value twice, i.e. 9i 6= j such that xi = xj. Once this happens, the sequence must then repeat the cycle of values from xi to xj 1. Let (the start of cycle) be the smallest index i and (the cycle length) be the smallest positive integer such that x = x + . The cycle- nding problem is de ned as the problem of nding and given f(x) and x0.

22. Given an array A[1 n] of, say n integers and an integer k, 1 k n 1, your mission is to swap the segments A[1 k] and A[k + 1 n], in place without using any auxiliary array.

Eg:- A[1 8] = [10; 20; 30; 40; 50; 60; 70; 80].

k = 3, output must be A[1 8] = [40; 50; 60; 70; 80; 10; 20; 30].

What is the exact complexity of your algorithm? f Number of swap operations g

23. How many times is the print statement executed?

for i1 = 1 to n do

for i2 = 1 to i1 do

for i3 = 1 to i2 do

.

.

.

for ik = 1 to ik 1 do

print i1; i2; ; ik

Notice that each line in the output consists of k integers

i1; i2; ik,

where

n i1 i2 ik 1.

Page 6