COS 226 Programming Assignment #1

Program Report

Your program report should answer the following questions.  This should be submitted in hard copy with your written exercises.

  1. Explain briefly how you implemented brute force. What Point methods did you add?
     
  2. Explain briefly how you implemented the sorting solution.  If you used the quicksort implementation from Sedgewick, what (if any) modifications did you make?
     
  3. Empirical Analysis:  Create a table showing the actual running times in seconds of both the brute and sorting methods for N=10, 20, 40, 100, 200, 400, 1000, 2000, 4000, 10000, 20000.  You can omit results when the running time becomes unreasonable, say more than three minutes.
     
  4. Estimate how long it would take to solve an instance of size N = 1,000,000 for each of the two algorithms using your computer.
     
  5. Theoretical Analysis: Estimate the worst case running time of your programs as a function of N. Justify your answer briefly.
     
  6. Any known bugs / limitations?
     
  7. List whatever help (if any) that you received.
     
  8. Describe any serious problems you encountered.
     
  9. Any other comments or feedback?