ESO207A-Data Structures and Algorithms Homework 1 Solved

1.   Solutions have to be submitted on Gradescope. For this, each problem should start on a newsheet. If this is not followed then it may not be possible to grade your answers.

2.   For each problem, write your name, Roll No., problem number, the date and the names ofany students with whom you collaborated. Remember that you must write the answer and the algorithm in your own words.

3.   For questions in which algorithms are asked for, your answer should provide the following: (a) A clear description of the algorithm in English and/or pseudo-code, where, helpful, (b) A proof/argument of the correctness of the algorithm, and, (c) an analysis of the running time of the algorithm.

Full marks will be given only to correct solutions which are described clearly. Convoluted and unclear descriptions will receive low marks.



Problem 1. Order Notation and Recurrence Equations                                                                                          (30)
(a)   State whether each of the following statement is true or false, with a brief reason. (i) n2 = O(2n), (ii) n3 = O(n4 logn), (iii) n2 = Ω(n3), (iv) 3n = Θ(n!) (v) 2n = Θ(2n+c), for any constant c.       (10)

(b)  Solve the following recurrence equations. Assume that T(1) = Θ(1) and T(2) = Θ(1) for all the functions below. Use the recursion tree method (unrolling the recurrence eqn as done in class). Do not use the master formula. Make and state appropriate simplifying assumptions if needed.      (4 × 5 = 20).

1.   T(n) = T(n/2) + n.

2.   T(n) = 4T(n/3) + n2.

3.   T(n) = 3T(n/3) + n.

4.   T(n) = 2T(n/2) + nlogn.

Problem 2. Non-dominated points                                                                                                                                           (35)
A two-dimensional point (x,y) is said to dominate another two-dimensional point (u,v) if x ≥ u and y ≥ v. Non-dominated points are also called maximal points. Given a set P of points, a point p = (x,y) is said to be a non-dominated point of P if no other point q in P dominates p. See Figure 1 for examples. Given a set of n points P placed in arbitrary order in an array, give a time efficient algorithm find non dom(P,n) to find the set of all non-dominated points in P. Notes:

1.   For simplicity, assume that no two points have the same x-coordinate or the same y-coordinate.

2.   A point p is represented as a structure with two attributes p.x and p.y. The set of points P, is represented as an array P[1,...,n] of points in arbitrary order.

3.   You can find the index of the median of the points in P[k,...,l] by the x coordinate by using an informal statement like “let i = median(P,k,l) by x-coordinate” Similarly, a statement like “let i =median(P,k,l) by y coordinate” can be used to find the index of the median of the points in P[k,...,l] by the y coordinates. These functions run in time O(l − k + 1). The median of n points is returned as the b(n + 1)/2c th ranked point (by x-coordinate or y-coordinate as the case may be).

4.   Full marks will be provided for a correct solution that takes O(nlogn) time.

5.   A correct solution of O(n2) time will earn only 15 points in total.

 

Figure 1: Dominated and non-dominated points in a point-set

Problem 3.                                                                                                                                                                                                     (35)
An important court trial is going on that has N witnesses. However, not all witnesses are honest; a witness is either true or false. A true witness always speaks the truth, whereas a false witness may lie and cannot be relied upon. To test the witnesses’ credibility, the judge speaks to them in pairs (e.g., W1 and W2). Both are asked the same questions about the case and the answers given by each one is presented to the other. Each of them (e.g., Wi) is now asked whether the other person (i.e. W2) is telling the truth or not (and vice-versa). The possibilities are as follows:

W1 says
W2 says
Conclusion


W2 is true
W1 is true
Both are true, or both are false witnesses
W2 is true
W1 is false
At least one is a false witness
W2 is false
W1 is true
At least one is a false witness
W2 is false
W1 is a false
At least one is a false witness
a.    Show that if there are more than N/2 false witnesses, the judge cannot necessarily pick out the true witnesses, irrespective of the pairwise test strategy used. Assume that the false witnesses can conspire to fool the judge.

b.    Assuming that more than N/2 witnesses are true, the judge now wants to identify one true witness. Show that bN/2c pairwise tests are sufficient to reduce this problem to that of approximately half its size.

c.    Show that the true witnesses can be identified with Θ(N) pairwise tests, assuming that more than N/2 witnesses are true. Argue and solve the recurrence that describes the number of tests.