CS345-Assignment I Solved

Difficult
Faster algorithm for Non-dominated points in a plane
Recall the problem of non-dominated problem discussed in the second lecture of this course. We discussed two algorithms for this problem. The first algorithm takes O(nh) time, where h is the number of non-dominated points in the given set P. The second algorithm, which was based on the divide and conquer paradigm, takes O(nlogn) time. As a part of this assignment, you have to design an O(nlogh) time algorithm for nondominated points. Interestingly, you have to use the insight from the first algorithm to just slightly modify the second algorithm so that its running time is improved to O(nlogh). You must describe the algorithm and also provide the complete details of the analysis of its running time.

Remark: Note that O(nlogh) is superior to O(nlogn) in those cases where the number of non-dominated points are very few. In fact, it can be shown that if n points are selected randomly uniformly from a unit square, then the expected(average) number of non-dominated points is just O(logn).

OR
Non-dominated points in 3 dimensions
You can extend the notion of non-dominated points to 3 dimensions as well. Spend some time to realize that it is not so simple to apply divide and conquer strategy to compute the non-dominated points in 3 dimensions. Some of you may be tempted to solve this problem by reducing an instance of this problem to three instances of 2-dimensional problem (by projecting the points on x-y, y-z, x-z plane). But that will be wrong (think over it to convince yourself). Interestingly, there is a very simple elegant algorithm using a simple data structure that computes non-dominated points in 3 dimensions. The purpose of this exercise is to make you realize this fact.

1.    Design an algorithm that receives n points in x-y plane one by one and maintains the non-dominated points in an online fashion. Upon insertion of ith point, the algorithm should take O(logi) time to update the set of non-dominated points. Note: It is perfectly fine if your algorithm only guarantees a bound of O(ilogi) on the total time for insertion of i points. It is not necessary that your algorithm achieves O(logi) bound on the processing carried out during insertion of ith point.

2.    Design an O(nlogn) time algorithm to compute non-dominated points of a set of n points in 3 dimensions. You must use part (a) above carefully.

Moderate
Convex Hull
In Lecture 2, we discussed an O(nlog2 n) time algorithm to compute the convex hull of a given set of n points in a plane. If we can improve the time complexity of the Conquer step of this algorithm to linear, this will result in an O(nlogn) time algorithm for convex hull. You have to modify the current Conquer step so that it takes at most linear time. You must provide a complete analysis of the modified Conquer step as well.

Easy
Counting Double-Inversions
You are given an array A storing n numbers. A pair (i,j) with 0 ≤ i < j ≤ n − 1 is said to be a double-inversion if A[i] > 2A[j]. Design and analyze an O(nlogn) time algorithm based on divide and conquer paradigm to compute the total number of double-inversions in A.