Description

Most Important guidelines
• Refrain from collaborating with the students of other groups. If any evidence is found that confirms copying, the penalty will be very harsh. Refer to the website at the link: https://cse.iitk.ac.in/pages/AntiCheatingPolicy.html regarding the departmental policy on cheating.
General guidelines
1. There are four problems in this assignment: 2 Difficult problems, 1 Moderate, and 1 Easy. Each difficult problem carries 100 marks, the moderate one carries 75 marks, and the easy one carries 50 marks. Attempt only one of the 4 problems.
2. You are strongly discouraged to submit the scanned copy of a handwritten solution.Instead, you should prepare your answer using any text processing software (LaTex, Microsoft word, …). The final submission should be a single pdf file.
3. You need to justify any claim that you make during the analysis of the algorithm.But you must be formal, concise, and precise.
5. Naming the file:
The submission file has to be given a name that reflects the information about the assignment number, version attempted (difficult/moderate/esay), and the roll numbers of the 2 students of the group. For example, you should name the file as D 1 Rollnumber1 Rollnumber2.pdf if you are submitting the solution for the difficult version of the 1st assignment. In a similar manner, the name should be M 1 Rollnumber1 Rollnumber2.pdf and E 1 Rollnumber1 Rollnumber2.pdf if you are submitting the solution for the moderate problem and the easy problem respectively of the 1st assignment.
6. Both students of a group have to upload the identical copy of their final submission.Be careful during the submission of an assignment. Once submitted, it can not be re-submitted.
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
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.