Divide and Conquer

Directions: Some of the questions on this assignment will appear on the quiz on Monday, April 11th.

Design and analyze means:

Give pseudocode for your algorithm. Prove that your algorithm is correct.

Give the recurrence relation for the running time for your algorithm. Solve the recurrence relation.

1. Rank the following running times in order from fastest to slowest:

17n
n3
2n

n!

36
logb(n)

48n logb(n)

367n2 logb(n)
nn

    2. Solve the following recurrence relations:

T (n) = T (n=2) + O(n) T (n) = T (n=2) + O(n2) T (n) = 3T (n=3) + O(1) T (n) = T (n=3) + O(n)

    3. In justifying our matrix multiplication algorithm, we accepted the following property: If X and Y are
n    n matrices and
X =
C  D
Y =
G  H

A  B

E  F

where A; B; C; D; E; F; G and H are n=2 by n=2 matrices, then the product XY can be expressed as:
XY =
C  D
G  H
=
CE+DG
CF +DH

A  B
E  F

AE+BG
AF +BH

Prove this property.

    4. Suppose that you are given a sorted list of distinct integers fa1; a2; : : : ang. Design and analyze a divide-and-conquer algorithm that determines whether there exists an index i such that ai = i. For

example, in f 10;    4; 3; 41g, a3 = 3, and in f4; 7; 19; 20g there is no such i.

    5. Suppose you are given 3n marbles that look identical, with one special marble that weighs more than the other marbles. You are also given a balancing scale that takes two items (or sets of items) and compares their weights. Design and analyze a divide and conquer algorithm to find the heavy marble using the balancing scale at most n times.

    6. Suppose that you are given an integer, x, and a sorted list of integers. Design and analyze a divide and conquer algorithm that counts the number of occurrences of x in the list.

Example: Suppose x = 4 and the list is f1; 2; 2; 2; 4; 4; 12; 20; 20; 20g. Your algorithm should return 2.



1 of 2

CPE 349 - Algorithms
Divide and Conquer
Spring 2022
Due: Monday, April 11th

    7. Suppose that you are given a list of n elements. Design and analyze a divide and conquer algorithm to remove all duplicates from the list in time O(n log n).

    8. A list A is said to have a majority element if more than half of its entries are the same. There is not necessarily an order on the list, so there can’t be comparisons of the form “Is A[i] A[j]?”. However,
in constant time, the question “Is A[i] = A[j]?” can be answered. Given an array, design a divide and
In-class exercises: Divide-and-conquer
conquer algorithm to determine if there is a majority element, and, if so, to find that element. Your algorithm should run in time O(n log n).

    9. Suppose we are given a list of n numbers representing stock prices on a single day. We want to find a pairThe(skylinebuy;sellproblem/the)withbuyupper envelopesellsuchproblem:that if we bought the stock on buy day and sold the stock on sell
day,Inthisweproblemwould wemaximizedesigndivideour- andprofit-conquer. algorithm for computing the skyline of a set of
    • buildings.
DesignAbuildingandBi analyzeisrepresentedadivideasatripletand( Lconqueri,Hi,Ri) wherealgorithmLiand Rthatidenotefindsthe theleftandoptimalrightx (buy; sell) pair.
coordinates of the building, and Hi  denotes the height of the building (note that the x coordinates

10.areIndrawnthis problemboldfaced.) we find the closest pair of points in the Euclidean plane. Suppose you are given a set of
A skyline of a set of   buildings is   list of x coordinates and the heights connecting them
n points in the plane. The goal is to find the two points that are the closest. Recall that the distance
arranged in order from left to right (note that the list is of length at most 4n).
bx)2 + (ay
by)2.
between two points, a = (ax; ay) and b = (bx; by) is p(ax



Design and analyze a divide and conquer algorithm to solve this problem.

11. We will compute skylines in this problem. A building, Bi, is given as a triplet (Li; Hi; Ri) where Li
Example: The skyline of the buildings
and Ri denote the left and right x-coordinates of the building and Hi represents the height. A skyline
of a set of buildings is a list of x coordinates and the heights connecting them arranged in order from
{(3, 13, 9), (1, 11, 5), (12, 7, 16), (14, 3, 25), (19, 18, 22), (2, 6, 7), (23, 13, 29), (23, 4, 28)}
left to right.
is
Example: Given:{1f,11(3,;313,;,9),0;,(112;,117,16;5),3;, (1219,18;7,;2216),3,;23(14,13;,329;25),0}; (19; 18; 22); (2; 6; 7); (23; 13; 29); (23; 4; 28)g,
the skyline is: f1; 11; 3; 13; 9; 0; 12; 7; 16; 3; 19; 18; 22; 3; 23; 13; 29; 0g
(note that the x coordinates in a skyline are sorted).

20

15

10

5

0

















20





















15











































10

































































5











































0
5


20
25
30
























5

10
15
20
25

30


10
15









buildings








skyline





Design and analyze a divide-and-conquer algorithm to compute the skyline for a list of n buildings.

        1. Let the size of a skyline be the total number of elements (coordinates and heights) in its list.
    12. You are given a list of numbers. Your goal is to return the sum of the contiguous sublist of numbers
Describe an algorithm for combining a skyline A of size n    and a skyline B of size n    into
that has the largest sum.    1    2
one skyline S of size O(n1 + n2). Your algorithm should run in time O(n1 + n2).
For example, if you are given the list f1;    4; 3; 7;    5; 6;    9; 5g, your algorithm should return 11.
2. Describe an O(n log n) algorithm for finding the skyline of n buildings.
Design and analyze a divide and conquer algorithm to solve this problem.



1












2 of 2