CPSC 221H-200: Data Structures & Algorithms
Programming Assignment #1
Spring 2009

General Guidelines for Programs

• Your code should be well designed and documented. You WILL 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. 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: Monday February 2, 2009 by 11:59pm. 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 lab on February 3, 2009; the hardcopy must include the signed coverpage.

This programming assignment concerns an array-based implementation of the stack ADT. You will add a variant of one of the existing stack operations (size) that uses a different implemention and you will compare the performance of your version, mySize(), with the already provided size(). This will allow you to see how the choice of implementation can affect performance.

Coding Portion. (50 points)

• Start with the following template programs: ArrayStack.h and RuntimeException.h, and complete the implementation of the method mySize(). Your implementation of mySize() should only use public methods such as the StackArray constructor, push(), pop(), and isEmpty() - you cannot use size() or any private data or methods. You should turn in your modified version of ArrayStack.h and the test program you used to generate the results you report.

• You might find the following template program useful to time the size() and mySize() methods: ElapsedTime.cpp.

Report. (50 points) 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 provide an analysis of the running time of your mySize() method assuming there are N elements in the stack when mySize() is invoked. Express your answer using asymptotic notion. Compare the theoretical efficiency of this new version of mySize() with the version of size() in the text that uses the internal variable t.
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 is your timing mechanism?
   • How did you generate the test inputs? What input sizes did you test? Why?
   • How many times did you repeat each experiment?
4. Experimental Results. In this section, you should compare the performance (running time) of size() and mySize() to each other and to their theoretical complexity.
   • Make a plot showing the running time (y-axis) vs. the stack size (x-axis) of both size() and mySize() 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.
   • Experimentally determine the constants hidden in your asymptotic analysis using the method described in lab; show these constants on the plots. Determine the values of N 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:
     • Which of the two size operations performs the best? Does it depend on the input?
     • To what extent does theoretical analysis agree with the experimental results? Attempt to understand and explain any discrepancies you note.
     • Report on the constants you determined for the asymptotic analysis, and the values of N 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 this data structure.

   ---