$29
Programming Assignment 4:Divide-and-Conquer Solution
Introduction
In this programming assignment, you will be practicing implementing divide-and-conquer solutions.
Learning Outcomes
Upon completing this programming assignment you will be able to:
1. Apply the divide-and-conquer technique to solve various computational problems efficiently. This will usually require you to design an algorithm that solves a problem by splitting it into several disjoint subproblems, solving them recursively, and then combining their results to get an answer for the initial problem.
2. Design and implement efficient algorithms for the following computational problems:
(a) searching a sorted data for a key;
(b) finding a majority element in a data;
(c) improving the quick sort algorithm;
(d) checking how close a data is to being sorted;
(e) organizing a lottery;
(f) finding the closest pair of points.
Passing Criteria: 3 out of 6
Passing this programming assignment requires passing at least 3 out of 6 programming challenges from this assignment. In turn, passing a programming challenge requires implementing a solution that passes all the tests for this problem in the grader and does so under the time and memory limits specified in the problem statement.
1
• Binary Search
Problem Introduction
In this problem, you will implement the binary search algorithm that allows searching very efficiently (even huge) lists, provided that the list is sorted.
Problem Description
Task. The goal in this code problem is to implement the binary search algorithm.
Input Format. The first line of the input contains an integer and a sequence 0 < 1 < . . . < −1 of pairwise distinct positive integers in increasing order. The next line contains an integer and positive integers 0, 1, . . . , −1.
Constraints. 1 ≤ , ≤ 104; 1 ≤ ≤ 109 for all 0 ≤ < ; 1 ≤ ≤ 109 for all 0 ≤ < ;
Output Format. For all from 0 to − 1, output an index 0 ≤ ≤ − 1 such that = or −1 if there is no such index.
Sample 1.
Input:
51581213
58123111
Output:
20-10-1
In this sample, we are given an increasing sequence 0 = 1, 1 = 5, 2 = 8, 3 = 12, 4 = 13 of length five and five keys to search: 8, 1, 23, 1, 11. We see that 2 = 8 and 0 = 1, but the keys 23 and 11 do not appear in the sequence . For this reason, we output a sequence 2, 0, −1, 0, −1.
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
3
• Majority Element
Problem Introduction
Majority rule is a decision rule that selects the alternative which has a majority, that is, more than half the votes.
Given a sequence of elements 1, 2, . . . , , you would like to check whether it contains an element that appears more than /2 times. A naive way to do this is the following.
MajorityElement( 1, 2, . . . , ):
for from 1 to :
currentElement ←
count ← 0
for from 1 to :
if = currentElement:
count ← count + 1
if count > /2:
return
return “no majority element”
The running time of this algorithm is quadratic. Your goal is to use the divide-and-conquer technique to design an ( log ) algorithm.
Problem Description
Task. The goal in this code problem is to check whether an input sequence contains a majority element.
Input Format. The first line contains an integer , the next one contains a sequence of non-negative integers 0, 1, . . . , −1.
Constraints. 1 ≤ ≤ 105; 0 ≤ ≤ 109 for all 0 ≤ < .
Output Format. Output 1 if the sequence contains an element that appears strictly more than /2 times, and 0 otherwise.
Sample 1.
Input:
5
23922
Output:
1
2 is the majority element.
Sample 2.
Input:
4
1234
Output:
0
There is no majority element in this sequence.
4
Sample 3.
Input:
4
1231
Output:
0
This sequence also does not have a majority element (note that the element 1 appears twice and hence is not a majority element).
What To Do
As you might have already guessed, this problem can be solved by the divide-and-conquer algorithm in time ( log ). Indeed, if a sequence of length contains a majority element, then the same element is also a majority element for one of its halves. Thus, to solve this problem you first split a given sequence into halves and make two recursive calls. Do you see how to combine the results of two recursive calls?
It is interesting to note that this problem can also be solved in ( ) time by a more advanced (non-divide and conquer) algorithm that just scans the given sequence twice.
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
5
• Improving Quick Sort
Problem Introduction
The goal in this problem is to redesign a given implementation of the random-ized quick sort algorithm so that it works fast even on sequences containing many equal elements.
Problem Description
Task. To force the given implementation of the quick sort algorithm to efficiently process sequences with few unique elements, your goal is replace a 2-way partition with a 3-way partition. That is, your new partition procedure should partition the array into three parts: < part, = part, and > part.
Input Format. The first line of the input contains an integer . The next line contains a sequence of integers 0, 1, . . . , −1.
Constraints. 1 ≤ ≤ 105; 1 ≤ ≤ 109 for all 0 ≤ < .
Output Format. Output this sequence sorted in non-decreasing order.
Sample 1.
Input:
5
23922
Output:
22239
Starter Files
In the starter files, you are given an implementation of the randomized quick sort algorithm using a 2-way partition procedure. This procedure partitions the given array into two parts with respect to a pivot : ≤ part and > part. As discussed in the video lectures, such an implementation has ( 2) running time on sequences containing a single unique element. Indeed, the partition procedure in this case splits the array into two parts, one of which is empty and the other one contains − 1 elements. It spends time on this. The overall running time is then
+ ( −1)+ ( −2)+...= ( 2).
What To Do
Implement a 3-way partition procedure and then replace a call to the 2-way partition procedure by a call to the 3-way partition procedure.
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
6
4 Number of Inversions
Problem Introduction
An inversion of a sequence 0, 1, . . . , −1 is a pair of indices 0 ≤ < < such
that > . The number of inversions of a sequence in some sense measures how
close the sequence is to being sorted. For example, a sorted (in non-descending
6
1
5
2
3
order) sequence contains no inversions at all, while in a sequence sorted in de-
scending order any two elements constitute an inversion (for a total of ( − 1)/2
inversions).
Problem Description
Task. The goal in this problem is to count the number of inversions of a given sequence.
Input Format. The first line contains an integer , the next one contains a sequence of integers 0, 1,..., −1.
Constraints. 1 ≤ ≤ 105, 1 ≤ ≤ 109 for all 0 ≤ < .
Output Format. Output the number of inversions in the sequence.
Sample 1.
Input:
5
23929
Output:
2
The two inversions here are (1, 3) ( 1 = 3 > 2 = 3) and (2, 3) ( 2 = 9 > 2 = 3).
What To Do
This problem can be solved by modifying the merge sort algorithm. For this, we change both the Merge and
MergeSort procedures as follows:
• Merge( , ) returns the resulting sorted array and the number of pairs ( , ) such that ∈ , ∈ , and > ;
• MergeSort( ) returns a sorted array and the number of inversions in .
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
7
• Organizing a Lottery
Problem Introduction
You are organizing an online lottery. To participate, a person bets on a single integer. You then draw several ranges of consecutive integers at random. A participant’s payoff then is proportional to the number of ranges that contain the participant’s number minus the number of ranges that does not contain it. You need an efficient algorithm for computing the payoffs for all participants. A naive way to do this is to simply scan, for all participants, the list of all ranges. However, you lottery is very popular: you have thousands of participants and thousands of ranges. For this reason, you cannot afford a slow naive algorithm.
Problem Description
Task. You are given a set of points on a line and a set of segments on a line. The goal is to compute, for each point, the number of segments that contain this point.
Input Format. The first line contains two non-negative integers and defining the number of segments and the number of points on a line, respectively. The next lines contain two integers , defining the -th segment [ , ]. The next line contains integers defining points 1, 2, . . . , .
Constraints. 1 ≤ , ≤ 50000; −108 ≤ ≤ ≤ 108 for all 0 ≤ < ; −108 ≤ ≤ 108 for all 0 ≤ < .
Output Format. Output non-negative integers 0, 1, . . . , −1 where is the number of segments which contain . More formally,
=|{: ≤ ≤ }|.
Sample 1.
Input:
• 3
0 5
7 10
1611
Output:
1 0 0
Here, we have two segments and three points. The first point lies only in the first segment while the remaining two points are outside of all the given segments.
Sample 2.
Input:
1 3
-10 10
-100 100 0
Output:
0 0 1
8
Sample 3.
Input:
• 2
0 5 -3 2 7 10 1 6
Output:
2 0
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
9
• Closest Points
Problem Introduction
In this problem, your goal is to find the closest pair of points among the given points. This is a basic primitive in computational geometry having applications in, for example, graphics, computer vision, traffic-control systems.
Problem Description
Task. Given points on a plane, find the smallest distance between a pair of two (different) points. Recall
√
that the distance between points ( 1, 1) and ( 2, 2) is equal to ( 1 − 2)2 + ( 1 − 2)2.
Input Format. The first line contains the number of points. Each of the following lines defines a point (,).
Constraints. 2 ≤ ≤ 105; −109 ≤ , ≤ 109 are integers.
Output Format. Output the minimum distance. The absolute value of the difference between the answer of your program and the optimal value should be at most 10−3. To ensure this, output your answer with at least four digits after the decimal point (otherwise your answer, while being computed correctly, can turn out to be wrong because of rounding issues).
Sample 1.
Input:
2
0 0
3 4
Output:
5.0
There are only two points here. The distance between them is 5.
Sample 2.
Input:
4
7 7
• 100
4 8
7 7
Output:
0.0
There are two coinciding points among the four given points. Thus, the minimum distance is zero.
10
Sample 3.
Input:
11
4 4
-2 -2
-3 -4
-1 3
• 3 -4 0 1 1 -1 -1 3 -1 -4 2 -2 4
Output:
1.414213
√
The smallest distance is 2. There are two pairs of points at this distance: (−1, −1) and (−2, −2); (−2, 4) and (−1, 3).
What To Do
This computational geometry problem has many applications in computer graphics and vision. A naive algorithm with quadratic running time iterates through all pairs of points to find the closest pair. Your goal is to design an ( log ) time divide and conquer algorithm.
To solve this problem in time ( log ), let’s first split the given points by an appropriately chosen vertical line into two halves 1 and 2 of size 2 (assume for simplicity that all -coordinates of the input points are different). By making two recursive calls for the sets 1 and 2, we find the minimum distances 1 and 2 in these subsets. Let = min{ 1, 2}.
1 2
11
It remains to check whether there exist points 1 ∈ 1 and 2 ∈ 2 such that the distance between them is smaller than . We cannot afford to check all possible such pairs since there are 2 · 2 = ( 2) of them. To check this faster, we first discard all points from 1 and 2 whose -distance to the middle line is greater than . That is, we focus on the following strip:
1 2
Stop and think: Why can we narrow the search to this strip? Now, let’s sort the points of the strip by their -coordinates and denote the resulting sorted list by = [ 1, . . . , ]. It turns out that if | − | > 7, then the distance between points and is greater than for sure. This follows from the Exercise Break below.
Exercise break: Partition the strip into × squares as shown below and show that each such square contains at most four input points.
1 2
This results in the following algorithm. We first sort the given points by their -coordinates and then split the resulting sorted list into two halves 1 and 2 of size 2 . By making a recursive call for each of the sets 1 and 2, we find the minimum distances 1 and 2 in them. Let = min{ 1, 2}. However, we are not done yet as we also need to find the minimum distance between points from different sets (i.e, a point from 1 and a point from 2) and check whether it is smaller than . To perform such a check, we filter the initial point set and keep only those points whose -distance to the middle line does not exceed . Afterwards, we sort the set of points in the resulting strip by their -coordinates and scan the resulting list of points. For each point, we compute its distance to the seven subsequent points in this list and compute ′, the minimum distance that we encountered during this scan. Afterwards, we return min{ , ′}.
The running time of the algorithm satisfies the recurrence relation
( ) = 2 · ( 2 ) + ( log ) .
The ( log ) term comes from sorting the points in the strip by their -coordinates at every iteration.
Exercise break: Prove that ( ) = ( log2 ) by analyzing the recursion tree of the algorithm.
Exercise break: Show how to bring the running time down to ( log ) by avoiding sorting at each
recursive call.
12
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
13
