CPSC 221H-200: Data Structures & Algorithms
Programming Assignment #3
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. 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

Design Due: Thursday February 26, 2009 in lab. The code design should be submitted in hardcopy at the beginning of lab.

Code Due: Wednesday March 4, 2009 by midnight => Extended March 9, 2009. Code (including Makefile or .sln file) should be turned in electronically using the mechanism described above.

Project Report Due: Monday March 9, 2009 by midnight => Extended March 13, 2009.

Schedule.

• Discuss the problem in Lab (Tuesday February 17, 2009).
• Turn in proposed class definitions and data structure(s) to use, i.e., interface designs of your solution (Thursday February 26, 2009 at the beginning of lab).
• Implement proposed solution (March 4, 2009 => Extended March 9, 2009).
• Performance analysis and Project Report (March 9, 2009 => Extended March 13, 2009).

This programming assignment is to solve the fully parenthesized arithmetic expression problem with multiple data structures.

The fully parenthesized arithmetic expression problem includes expressions such as (((x1+x2)*(x1-x3))/(x2*x3)). Current operators in expression include +,-,*, and /, but this set may be extended to include additional operators taking two operands.

You will create two implementations, one with a Stack and one with a Tree. You will work in a group of two students; each student in the group will provide the implementation using one of the above data structures, but not the same data structure as their partner. The operands x1, x2, x3 and etc. are variables. But later operands may include constants.

Data Format.

• Input data: The first line represents an expression as a string of parentheses, operators, and numbers such as (((1+2)*(1-3))/(2*3)), where the number i refers to the ith variable xi. Every line from line 2 to the end of the file is a sequence of integer values for the variables x1 x2, ..., xn to be used for testing. For example, the input file
  

  (((1+2)*(1-3))/(2*3))
  2 5 3
  0 1 100
  

  would represent the expression e(x1,x2,x3) = (((x1 + x2)*(x1-x3))/(x2*x3)), and two test inputs, (x1=2, x2=5, x3=3) and (x1=0, x2=1, x3=100).

• Output: A string (((x1+x2)*(x1-x3))/(x2*x3)) = X for each line of test data, where xi is replaced by the value of xi and X is the value after expression is evaluated (fractional number). For example, the output for the above sample input should be:
  

  (((2+5)*(2-3))/(5*3))=-0.4667
  (((0+5)*(0-3))/(5*3))=-1.0 
  

Coding Portion. (50 points)

You should coordinate with your partner about who will be the primary coder of the Stack and the Tree implementation; each partner must code one portion. You need to design the algorithm and program for this problem by yourself. You may use the Standard Template Library (STL).

You will turn in your proposed design, including class definitions, interface designs of your solution, and data structure(s) to use on Thursday, February 26, 2009 at the beginning of lab. The complete program will be due on Monday, March 9, 2009 as described above. The initial design will be worth 15 points and the final program will be worth 35 points.

Report. (50 points) Due: March 13, 2009

The objective of your report will be to compare the Tree and Stack approaches. You will trade code with your partner and individually you will each compare the two approaches 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 your algorithm for this problem using pseudo code and words.
   • Decide what is the input size (number of variables, operators, or parentheses) and describe why you selected what you did.
   • Provide an analysis of the running time of your solution using asympotitic notation.
   • Discuss the constants C and N0 for your solution. What are they? What affects them?
   • Compare the bound using your data structure to your partners. Which one is better and why? You must explain your reasoning to receive full credit.
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?
4. Experimental Results. In this section, you should compare the performance (running time) of the experiments to their theoretical complexity.
   • Make a plot showing the running time (y-axis) vs. your input size (x-axis) of your solution 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 discussed in class; show these constants on plots. 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:
     • 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 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 this data structure.
     • Which data structure provides the best performance? Does it depend on the input or any other factor?
5. Conclusion. In this section, you should summarize your thoughts and opinions about this assignment.
   • What did you learn from this assignment?
   • What was most interesting to you?
   • What did you think about the difficulty level of this assignment (too difficult, too easy, about right, challenging, etc)?
   • How can this assignment be improved?

   ---