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 efficient 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) Define µ(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 sufficiently 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 find 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 find 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 specified in the
following implicit way: for each node v, you can determine the value xv by probing the node
v. Show how to find 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 |i − k| + |j − l| = 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 find a local
minimum of G using only O(n) probes to the nodes of G. (Note that G has n
2 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 |{i | T[i] = x}| > 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 find 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 = {1, 2, . . . , n} and f : S → S. If R ⊂ S, define f(R) = {f(x) | x ∈ R}.
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 find 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 finds 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 finds 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 find 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 find 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 find 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 efficient algorithm for finding which
value appears only once.
Here are some example inputs to the problem:
1 1 2 2 3 4 4 5 5 6 6 7 7 8 8
10 10 17 17 18 18 19 19 21 21 23
1 3 3 5 5 7 7 8 8 9 9 10 10
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 finding the lowest floor of a building from which a box would
break when dropping it. The building has n floors, numbered from 1 to n, and we have k
boxes. There is only one way to know whether dropping a box from a given floor will break
it or not. Go to that floor 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 floor from which dropping a box
will break it. The algorithm returns n + 1 if a box does not break when thrown from the n
th
floor. 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 +
n
2
k−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
find 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 find 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 finding 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 sufficient to
reduce the problem to one of nearly half the size.
(c) Show that the good chips can be identified 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 efficient algorithm for finding 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 ⊆ {1, . . . , 2n} 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 finite set S to another
natural number in the same finite set S and an initial value x0 ∈ N, the sequence of iterated
function values: {x0, x1 = f(x0), x2 = f(x1), . . . , xi = f(xi−1), . . .} must eventually use the
same value twice, i.e. ∃i 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-finding problem is defined as the problem of finding µ 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? { Number of swap operations }
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.
