I. Some Basics on Line Fitting Suppose that there is a set P of n points in the two-dimensional plane, denoted by (x1, y1), (2, 92),, (In, Yn), and suppose x < x 35 30 25 that minimizes the cost function 20 15 10 5 50 40 30 20 10 2.5 4 6 Fig. 2. Two lines that fit 12 points. 12 Input: We have the following inputs: 1) A set of n points in a 2-dimensional plane 5.0 7.5 10.0 12.5 15.0 17.5 20.0 Fig. 3. Three lines that fit 18 points. problem is essentially a "modeling" problem: we want to model a set of "observed points" using a simple yet accurate model, and in this case, the model is a set of lines, each for a different interval of x. If too many lines are used, the model would not be "simple" any more. Thus, intuitively, we would like a problem formulation that requires us to fit the points well, using as few lines as possible. Let's formulate our problem, which we shall call the "Multi-Line Fitting Problem": 14 P = {(1, ), (x2, y2), , (n. Yn)} with 1 < x2 < 0. Output: A partition of the points P into k segments: P = {P, P2, Pm} P2 {Pm+1, Pm+2, P3 = {Pm2 +1:Pm2+2, Pm} Pms} E Pk = {Pmk 1+1, Pm-1+2, Pm = Pn} cost(P, C) = (P) + E(P) + + (Pk) + Ck. In the cost function cost(P, C), the part (P) + (P) + +(P) is the total error of using k lines to fit the n points, and Ck is the penalty for using k lines (namely, for partitioning the n points into k segments). The greater k is, the greater the penalty term Ck is. Note that the value of k, as well as the turning points Pm Pm," are what an algorithm solving the problem needs to decide on. 5 Pm-1 III. What to Submit In this project, you need to submit three items: (1) an algorithm report, (2) a program that implements your algorithm, (3) output of your program on test instances. 3) The proof of correctness for your algorithm. 4) the analysis of time complexity for your algorithm. A. Submission Item One: An Algorithm Report First, you are to design an efficient algorithm for the "Multi-Line Fitting Problem", and submit it as a report. The report is just like what we usually do for algorithm design in a homework, and should have the four elements as usual: 1) The main idea of your algorithm. 2) The pseudo code of your algorithm. B. Submission Item Two: A Program That Implements Your Algorithm You need to implement your algorithm using a commonly used programming language, such as Python, C++, Java, etc. We encourage you to use Python if possible, but other languages are fine, too. Your program will take a list of instances of the "Multi-Line Fitting Problem" as input, and return a list of solutions (corresponding to those instances) as its output. To test your program, we will provide you with input instances as a "dictionary" in Python (after you have submitted the program), and ask you to submit the output solutions as a "dictionary" in Python. (Details on the two files, including their formats, will be explained in the next subsection for "Submission Item Three".) When you submit your program, you need to explain clearly how to run your code. If your programming language is not Python, then you also need to include an explanation on how you turned the provided "dictionary" of "input instances" in Python to your programming language, and how you turned your "output solutions" in your programming language to a "dictionary" in Python (following the formats specified in the next subsection).