READ THE INSTRUCTIONS CAREFULLY AND ANSWER THE BELOW ATTACHED QUESTION CLEARLY:

If your solution uses dynamic programming, we need you to provide the following: (a) If there is any preprocessing stage before mentioning subproblem definition, state that. If the preprocessing algorithm uses something known from some tutorial or some earlier course, e.g. DSA, then just mention that as a subroutine. No need to describe that. (b) A precise description of the subproblems you want to solve in the dynamic program. Notice this is just the subproblem, not how to solve it, or how it was obtained. (c) A recurrence which relates a subproblem to smaller (whatever you define smaller to mean) subproblems. Notice this is just the recurrence, not the algorithm or why the recurrence is correct. (d) Identify the subproblem that solves the original problem (e) A description of your dynamic programming algorithm which solves the recurrence efficiently. The description must be in English containing mathematical symbols or it can be a pseudocode in plain text. A C++/Java program etc with variable declaration etc will not be accepted. You do not need to prove correctness of the pseudocode (f) An argument for the running time of your dynamic algorithm.

If your solution uses divide and conquer paradigm, then we need you to provide the following. (a) If there is any preprocessing stage before mentioning subproblem definition, state that. If the preprocessing algorithm uses something known from some tutorial or some earlier course, e.g. DSA, then just mention that as a subroutine. No need to describe that. (b) A precise description of the subproblems, i.e. how you divide the actual problem into smaller subproblems. (c) A precise description on how you combine the solutions of the subproblems to solve the actual problem. (d) A description of your complete recursive algorithm. You can refer to the subroutines of (a) and (b). The description must be in English containing mathematical symbols or it can be a pseudocode in plain text. A C++/Java program etc with variable declaration etc will not be accepted. (e) Analysis of running time of the algorithm including a recurrence relation and the solution the recurrence relation.

QUESTION :

Question 2 Suppose we are given a set L of n line segments in 2D plane. Each line segment has one endpoint on the line y=0, one endpoint on the line y=1 and all the 2n points are distinct. Give an algorithm that uses dynamic programming and computes a largest subset of L of which every pair of segments intersects each other. You must also give a justification why your algorithm works correctly. (20 Marks)