CSCE 620:
Programming Assignment #1
Fall 2009

General Guidelines for Programs

• Your code should be well designed and documented. You may be graded on programming style.
• If the question is not fully specified, you may need to make some assumptions. In this case, you must state any assumptions you make, and justify why they are reasonable.
• Everyone must turn in their own copy of the assignment. You may consult outside material or work with others (this is encouraged), but you must reference your sources (people, books, webpages, etc.). These must be listed on the cover sheet mentioned below.
• Be clear and precise. Write neatly and legibly. Justify all answers, even if not specified in the question. Use good judgement concerning how detailed to make your answer.
• Code will be turned in electronically using the turnin program on CSNet.
• The report portion of the assignment, if any, follows conventions for other written assignments in this course. In particular, all assignments in this course must include a completed and signed coverpage available on the course homepage. Any assignment turned in without a fully completed and signed coverpage will receive ZERO POINTS.

Assignment

Due: Tuesday September 22, 2009 by 9:35am. Code should be turned in electronically using the mechanism described above. You should also turn in an electronic copy of your report using the same mechanism as you do for the code; the electronic copy does not need to have the signed coverpage. In addition, you should submit a hardcopy of your report (but no code). This is due at the beginning of class on Tuesday September 22, 2009; the hardcopy must include the signed coverpage.

The purpose of this "programming" assignment is to get you familiar with the CGAL library. You will need to install CGAL and write a simple program to execute some CGAL algorithms. You will also time the algorithms and write a report that compares their theoretical and their experiemental performance.

The CGAL tutorial presented in class provides some helpful information and pointers to other resources. The course homepage also has some other useful CGAL links.

Coding Portion. (25 points)

CGAL includes five different algorithms for computing 2D Convex Hulls. You should implement a program that executes and measures the running times of these five convex hull algorithms.

Report. (75 points)

You should prepare a report that examines the performance of the five convex hull algorithms. You should compare the algorithms both theoretically and experimentally. You will write a brief report that includes theoretical analysis, a description of your experiments, and discussion of your results. At a minimum, your report should include the following sections:

1. Introduction. In this section, you should describe the objective of this assignment.
2. Theoretical analysis. In this section, you should describe the theoretical complexity of the five convex hull algorithms using asymptotic analysis (e.g., Big Oh).
3. Experimental Setup. In this section, you should provide a description of your experiment setup, which includes but is not limited to
   • Machine specification.
   • What experiments did you run and why? That is, explain what you believe you will learn from each experiment.
   • How did you generate the test inputs? What input sizes did you test? Why?
   • What is your timing mechanism?
   • How many times did you repeat each experiment? How did you determine this?
4. Experimental Results. In this section, you should compare the performance (running time) of the algorithms with each other, and you should also compare each algorithm's experimental and theoretical complexity.
   • Make a plot showing the running time (y-axis) vs. your input size (x-axis) of the algorithms on the same graph. You must use some electronic tool (e.g., matlab, gnuplot, excel) to create the plot - handwritten plots will NOT be accepted.
   • For each algorithm, make plots that allow you to experimentally determine the constants hidden in the asymptotic analysis; show these constants on a plot. Determine the values of N0 for which the asymptotic analysis holds; this should also be determined from a plot.
   • Provide a discussion of your results, which includes but is not limited to:
     • How do the algorithms compare with each other? Does the experimental behavior of the algorithms match their theoretical complexity? Attempt to understand and explain any discrepancies you note.
     • Report on the constants you determined for the asymptotic analysis, and the values of N0 for which you found the asymptotic analysis holds. Explain how you determined these values, and what you can infer from them about the behavior of the algorithms.
5. Conclusion. In this section, you should summarize your conclusions.

   ---