Comp201: Principles of Object-Oriented Programming I
Spring 2008 -- HW05   

See Assignments Page for due date!

Save all of your work in a directory called HW05 on your U: drive (Owlnet account) inside a directory called Comp201 .

In these next 5 problems, you are to complete the stated exercises from Lab05 in addition to what is detailed below.

  1. (10 pts) Lab05 Exercise 7: Name your test method "test_ex07" so the graders can easily identify it. Be sure that your test method has complete "coverage", e.g. emtpy list, one element list, two element list, negative values, etc.
     
  2. (10 pts) Lab05 Exercise 8: Name your test method "test_ex08". Be sure to have complete testing coverage.
     
  3. (10 pts) Lab05 Exercise 9: Name your test method "test_ex09". Be sure to have complete testing coverage.
     
  4. (10 pts) Lab05 Exercise 10: Write the code for toString() using forward accumulation. Your algorithm should be tail-recursive. Name your test method "test_ex10fwd". Be sure to have complete testing coverage.
     
  5. (10 pts) Lab05 Exercise 10: Write the code for toString() (call it toString_rev() to avoid overwriting your previous code) using reverse accumulation but unlike the algorithm done in class, your helper method's base case should not return the closing paranthesis. Which way to you think is better? Name your test method "test_ex10rev". Be sure to have complete testing coverage.

    6. The next problems are not from the lab:
     

  6. (10 pts) Write the algorithm to calculate the sum of the squares of the Integer elements of a list, using forward accumulation. Name your test method "test_prob06". Be sure to have complete testing coverage.
     
  7. (15 pts) Consider the following interface, which defines two methods: 
    	package listFW.fold;  // sub-package of listFW
	
	public interface IFoldInp {

		/**
		* Accessor for base case value
		*/ 
		public abstract Object getBase();

		/***
		* Calculate the inductive case result, given first and the recursive result.
		*/
		public abstract Object calcInduct(Object first, Object recurResult);

	}
    Create a method of IList with the following signature: public abstract Object foldr(IFoldInp inp);
    which the following behaviors
    1. An empty list returns the base case value from the IFoldInp object.
    2. A non-empty list returns the result of the calcInduct method of the IFoldInp object where it was given _first and the result of recursively calling foldr on the _rest with the same IFoldInp object.
       

      You will need to add the line import listFW.fold.*; to the top of your list files in order to access the IFoldInp interface.

      Show that the following implementation of IFoldInp will sum all the Integer elements in a list: 

    	package listFW.fold;
		
	public class SumList implements IFoldInp {

		public Object getBase() {
			return 0;
		}

		public Object calcInduct(Object first, Object recurResult) {
			return ((Integer)first) + ((Integer)recurResult);
		}
	}

    Name your test method "test_prob07" and have it test the foldr method with an instance of SumList. Be sure to have complete testing coverage.

  8. (10 pts) foldr is called "fold right" and is an example of what we call a "higher order function" because it is a function (method) that takes another function (IFoldInp with its methods) as one of its inputs. foldr is a function that works on functions, or in OO terms, a behavior that uses other behaviors. Higher-order functions will be extremely important in achieving our OOP goals.

    Write an implementation of IFoldInp called MultList that will multiply all the Integer values in a list together. Name your test method "test_prob08" and have it test the foldr method with an instance of MultList.
     
  9. (10 pts) Write and test an implementation of IFoldInp called CopyList that returns a copy of a list when used with foldr. Name your test method "test_prob09".
     
  10. (15 pts) Compare the code between the methods of the list to sum, multiply and copy a list with the code in foldr and the corresponding IFoldInp classes. Explain what you see in terms of variant and invariant behaviors. Can foldr, when combined with an appropriate IFoldInp object, produce the result of any purely reverse accumulation algorithm? Why? Create a new text document file in your HW05 directory called HW05Prob10.txt (or .doc if you'd like to use Word) and write your answer in there.

 

 

110 points total.

 

When you have completed your homework, zip up the entire HW05 directory and submit the zipped file using the file upload link on the Assignments Page.

Last Revised Thursday, 03-Jun-2010 09:50:22 CDT

©2008 Stephen Wong and Dung Nguyen