Description
Divide and Conquer
1. Kleinberg, Jon. Algorithm Design (p. 248, q. 5) Hidden surface removal is a problem in computer
graphics where you identify objects that are completely hidden behind other objects, so that your
renderer can skip over them. This is a common graphical optimization.
In a clean geometric version of the problem, you are given n non-vertical, infinitely long lines in a plane
labeled L1 . . . Ln. You may assume that no three lines ever meet at the same point. (See the figure for
an example.) We call Li “uppermost” at a given x coordinate x0 if its y coordinate at x0 is greater than
that of all other lines. We call Li “visible” if it is uppermost for at least one x coordinate.
x
y
(a) Give an algorithm that takes n lines as input and in O(n log n) time returns all the ones that are
visible.
Solution:
CS 577 Assignment 6 – Divide and Conquer 2
(b) Write the recurrence relation for your algorithm.
Solution:
(c) Prove the correctness of your algorithm.
Solution:
Page 2 of 7
CS 577 Assignment 6 – Divide and Conquer 2
2. In class, we considered a divide and conquer algorithm for finding the closest pair of points in a plane.
Recall that this algorithm runs in O(n log n) time. Let’s consider two variations on this problem:
(a) First consider the problem of searching for the closest pair of points in 3-dimensional space. Show
how you could extend the single plane closest pairs algorithm to find closest pairs in 3D space. Your
solution should still achieve O(n log n) run time.
Solution:
(b) Now consider the problem of searching for the closest pair of points on the surface of a sphere
(distances measured by the shortest path across the surface). Explain how your algorithm from
part a can be used to find the closest pair of points on the sphere as well.
Solution:
(c) Finally, consider the problem of searching for the closest pair of points on the surface of a torus
(the shape of a donut). A torus can be thought of taking a plane and “wrap” at the edges, so a
point with y coordinate MAX is the same as the point with the same x coordinate and y coordinate
MIN. Similarly, the left and right edges of the plane wrap around. Show how you could extend the
single plane closest pairs algorithm to find closest pairs in this space.
Solution:
Page 3 of 7
CS 577 Assignment 6 – Divide and Conquer 2
3. Erickson, Jeff. Algorithms (p. 58, q. 25 d and e) Prove that the following algorithm computes gcd(x, y)
the greatest common divisor of x and y, and show its worst-case running time.
BINARYGCD(x,y):
if x = y:
return x
else if x and y are both even:
return 2*BINARYGCD(x/2,y/2)
else if x is even:
return BINARYGCD(x/2,y)
else if y is even:
return BINARYGCD(x,y/2)
else if x > y:
return BINARYGCD( (x-y)/2,y )
else
return BINARYGCD( x, (y-x)/2 )
Solution:
4. Here we explore the structure of some different recursion trees than the previous homework.
(a) Asymptotically solve the following recurrence for A(n) for n ≥ 1.
A(n) = A(n/6) + 1 with base case A(1) = 1
Solution:
Page 4 of 7
CS 577 Assignment 6 – Divide and Conquer 2
(b) Asymptotically solve the following recurrence for B(n) for n ≥ 1.
B(n) = B(n/6) + n with base case B(1) = 1
Solution:
(c) Asymptotically solve the following recurrence for C(n) for n ≥ 0.
C(n) = C(n/6) + C(3n/5) + n with base case C(0) = 0
Solution:
(d) Let d > 3 be some arbitrary constant. Then solve the following recurrence for D(x) where x ≥ 0.
D(x) = D
x
d
+ D
(d−2)x
d
+ x with base case D(0) = 0
Solution:
Page 5 of
CS 577 Assignment 6 – Divide and Conquer 2
5. Implement a solution in either C, C++, C#, Java, Python, or Rust to the following problem.
Suppose you are given two sets of n points, one set {p1, p2, . . . , pn} on the line y = 0 and the other
set {q1, q2, . . . , qn} on the line y = 1. Create a set of n line segments by connecting each point pi to
the corresponding point qi
. Your goal is to develop an algorithm to determine how many pairs of these
line segments intersect. Your algorithm should take the 2n points as input, and return the number
of intersections. Using divide-and-conquer, you should be able to develop an algorithm that runs in
O(n log n) time.
Hint: What does this problem have in common with the problem of counting inversions in a list?
Input should be read in from stdin. The first line will be the number of instances. For each instance,
the first line will contain the number of pairs of points (n). The next n lines each contain the location x
of a point qi on the top line. Followed by the final n lines of the instance each containing the location x
of the corresponding point pi on the bottom line. For the example shown in Fig 1, the input is properly
formatted in the first test case below.
Figure 1: An example for the line intersection problem where the answer is 4
Constraints:
• 1 ≤ n ≤ 106
• For each point, its location x is a positive integer such that 1 ≤ x ≤ 106
• No two points are placed at the same location on the top line, and no two points are placed at the
same location on the bottom line.
• Note that in C\C++, the results of some of the test cases may not fit in a 32-bit integer. If you
are using C\C++, make sure you use a ‘long long’ to store your final answer.
Page 6 of 7
CS 577 Assignment 6 – Divide and Conquer 2
Sample Test Cases:
input:
2
4
1
10
8
6
6
2
5
1
5
9
21
1
5
18
2
4
6
10
1
expected output:
4
7
