Using python

1. Write the full, unambiguous pseudo-code for your divide-and-conquer algorithm for finding the convex hull of a set of points Q . Be sure to label the parts of your algorithm. Also, label each part with its worst-case time efficiency.
2. Analyze the whole algorithm for its worst-case time efficiency. State the Big-O asymptotic bound. Discuss how this relates to the Master Theorem estimate for runtime.
3. Implement your divide and conquer algorithm in Python in the following method:
   1. ConvexHullSolver.compute_hull( self, unsorted_points )
   2. Use the divide and conquer algorithm from step #1 to find the convex hull of the points in pointList.
   3. You may use the GUI method addLines() to draw the line segments of the convex hull on the UI once you have identified them.
4. Conduct an empirical analysis of your algorithm by running several experiments as follows:
   1. For each value n {10, 100, 1000, 10,000, 100,000, 500,000, 1,000,000}
      1. Generate 5 sets of n points ( x , y ) in the plane. You may use either provided point generator: the 2-D Gaussian (Normal) distribution or the uniform distribution. For every point, x and y are real numbers (doubles). You may use the provided project scaffold code to assist you.
      2. For each point set,
         1. find the convex hull
         2. record the elapsed time
      3. For each size n , compute the mean time t required.
   2. Plot n (independent variable) versus t (dependent variable). Note that if you use a logarithmic graph to fit the data (preferable) then that may change the expected shape of your distribution. Make sure you explain that.
5. Find the relation of your plot to your theoretical analysis. In other words, if your theoretical analysis says that for a set of n points Q , the convex hull CH( Q ) O( g ( n )), does g ( n ) actually fit your empirical data? If so, what is the constant of proportionality k so that CH( Q ) = k g ( n )? If not, then which function g ( n ) best fits your empirical data, and what is the constant of proportionality? You can fit a function analytically using software or by trial and error in a spreadsheet, for example.
6. If your theoretical and empirical analyses differ, discuss the reason(s) for the difference.