Homework 10: Analyzing Reverse

Assigned: Tuesday, February 27, 2007
Due: Friday, March 2, 2007

Summary: In this assignment, you will further experiment with analyzing procedures.

Purpose: To get further experience analyzing procedures.

Expected Time: One hour.

Collaboration: You may work in a group of any size between one and four, inclusive. You may consult others outside your group, provided you cite those others. You need only submit one assignment per group.

Submitting: Email me your work, using a subject of CSC151 Homework 10.

Warning: So that this exercise is a learning assignment for everyone, I may spend class time publicly critiquing your work.

Assignment

In the lab on analyzing procedures, we attempted to come up with formulas characterizing the number of calls to myappend by reverse-1, and the number of calls to kernel within reverse-2. We discovered that reverse-2's calls to kernel can be described as a linear function: it uses n+1 calls for a list of size n. However, we didn't have enough information to easily see a pattern in reverse-1's calls to myappend.

1. Explain in your own words why reverse-2 uses n+1 calls to kernel for a list of size n.
2. Run reverse-1 on lists of size 1, 2, 3, 4, 5, 6, 7, and 8 and determine how many calls it makes to myappend. You should start to see a pattern. 
3. Give a formula or describe a procedure for predicting the number of calls reverse-1 will make to myappend for a list of size n. (You may wish to try some even larger lists to test your predictions.) Why does reverse-2 use so many more procedure calls than reverse-1?

Important Evaluation Criteria

In evaluating your work, I will look for a clear explanation of the behavior you observed. Exceptionally clear or precise explanations will receive a plus.