Description
Objective:
(1) Design and analyze an algorithm using divide and conquer strategy
(2) Establish recurrence equation and solve it.
(3) Enhance the concept of proof of correctness for algorithms.
There are two parts in this assignment: (A) Theory part and (B) programming part
[Part A] Theory [79%]:
1. (9%) Given an image which shows two white regions, design an algorithm to fill the region 1 by the red color, and fill the region 2 by the blue color. Assume the image is represented by a Matrix with the size of N by N (e.g., color[x, y]), use the recursive algorithm to solve this problem. (Assume the value of color is either WHITE, or RED, or BLUE). White a pseudo-code.
2. (8%) Given a sorted array of distinct integers A[1, …, n], you want to find out whether there is an index i for which A[i]=i. Give a divide-and-conquer algorithm to solve this problem. Derive the time complexity. (Note: the running time much be less than O(n)).
3. [10%] Write a piece of pseudo-code to plot the following graph. Assuming that the plotting function has been provided as DrawSquare(x, y, r), which draw a square of size 2r with center (x, y).
(1) Pseudo-Code to plot following graph. (4%)
(2) Write the recurrence equation for your algorithm. (3%)
(3) Plot the recursion tree to derive the solution of T(r). (3%)
(Note: r is the input size, which is the power of 2. The time complexity for drawing one square is O(1)). (Hint: The input of function can be: int x, int y, int r)
4. (9%) An Array A[1,…,n] is said to have a majority element if more than half of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element. Show how to solve this problem in O(nlgn) time.(Hint: Split the array A into two arrays A1 and A2 of half the size. Does knowing the majority elements of A1 and A2 help you figure out the majority element of A?) Note that it is required to use a divide-and-conquer approach with O(nlgn) time complexity.
5. (6%) Suppose you are choosing between the following three algorithms:
• Algorithm A solves problems by dividing them into five sub-problems of half size, recursively solving each sub-problem, and then combining the solutions in linear time.
• Algorithm B solves problems of size n by recursively solving two sub-problems of size n-1 and then combining the solutions in constant time.
• Algorithm C solves problems of size n by dividing them into nine sub-problems of size n/3, recursively solving each sub-problem, and then combining the solutions in O(n2) time.
What are the running times of each of these algorithms (in big-O notation), and which would you choose? (Note: strategy for solving the problem and its sub-problems is same).
6. [10%]
a. [3%]Write the recurrence equation for the code below. Use the number of comparisons as your barometer operation (The min operation requires 1 comparison and the max operation requires 1 comparison): ): (Note: you can count min and max as the comparison operation and skip the rt-lt <=1)
MinMax(A,lt,rt)
// return a pair with the minimum and the maximum
if (rt - lt 1)
return (min(A[lt], A[rt]), max(A[lt],A[rt]));
(min1, max1) = MinMax(A,lt, (lt+rt)/2 );
(min2, max2) = MinMax(A, (lt+rt)/2 +1,rt);
return (min (min1, min2), max(max1, max2));
b. [4%] Show the recursion tree and solve the recurrence equation for this code. For simplicity assume n = 2k.
c. [3%] Prove the solution using induction
7. [5%] Find the asymptotic bound of the divide and conquer recurrence T(n) using master method: (1) T(n)=16T(n/4)+n^4+3;
8. [5%] Solve the following recurrence equation using methods of characteristic equation.
T(n)=5T(n-1)-8T(n-2)+4T(n-3) for n>2
T(0)=0
T(1)=1
T(2)=2
Hint: if there are two same roots, the solution template is T(n) = C1*r1^n + C2*r2^n + C3*n*r3^n
9. (9%)
(1) What is the time complexity of the above algorithm; (2%)
(2) Improve the above algorithm with an asymptotically better running time. Show your algorithm, and the time complexity (4%)
(3) Proof of correctness of your algorithm (3%)
10 (8%) Design an algorithm for visible lines detection: Given n non-vertical lines in a plane, labeled L1…., Ln, with line equation y=ai*x +bi (i=1, …n). We can make an assumption that no three of the lines all meet at a single point.
Definition: line Li is uppermost at a given x-coordinate x0 if its y-coordinate at x0 is greater than the y-coordinates of all the other lines at x0. Line Li is visible if there is some x-coordinate at which it is uppermost – intuitively, some portion of it can be seen if you look from infinity of y (y = ); For example: following figure is an instance of visible lines (labeled 1-5). All the lines except for 2 are visible.
Give an algorithm that takes n lines as input and in no more than O(n^3) time returns all of the ones that are visible. Show the time complexity.
[Part B]: Divide and Conquer Programming (21%)
1. [12%] Implement the algorithm for finding the closest pair of points in two dimension plane using divide and conquer strategy.
A system for controlling air or sea traffic might need to know which are the two closest vehicles in order to detect potential collisions. This part solves the problem of finding the closest pair of points in a set of points. The set consists of points in R2 defined by both an x and a y coordinate. The “closest pair” refers to the pair of points in the set that has the smallest Euclidean distance, where Euclidean distance between points p1=(x1,y1) and p2=(x2,y2) is simply sqrt((x1-x2)2+(y1-y2)2). If there are two identical points in the set, then the closest pair distance in the set will obviously be zero.
Input data: n points with coordinates:
X coordinates: p[0].x, p[1].x, p[2].x,…., p[n].x
Y coordinates: p[0].y, p[1].y, p[2].y,…., p[n].y
Output: minimum distance between points p[i] and p[j] (index i and j should be identified)
Input data for test:
n = 10000;
for(i=0; i
X=1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ……,19995, 19997, 19999 (odd numbers)
Y=int( )
Else
X=0, -2, -4, -6, -8, -10, -12, ……, -19996, -19998, -20000 (even number)
Y= int( )
2. (9%) Use the brute-force approach to solve the above problem. Compare the two implemented algorithms in terms of time complexity. Print out the time cost during the execution of these two algorithms.
3. (Extra 9%) apply the close-pair algorithm to the three dimensional case.
Note 1:
Your report (.doc) of the programming part should follow the following format:
(1) Algorithm description
(2) Major codes
(3) Running results
(4) Report of any bugs
Note 2:
2.1 For Part B, your code package includes your code, makefile, executable file, and write-up (.doc).
2.2 Your program will read an input file and write an output file.
2.3 Your program should be invoked like this…
prompt>submission inputFile.txt outputFile.txt
where inputFile.txt is referring to an input file,
ouputFile.txt is referring to an output file.
