CS 20, Summer 2009
Project 2

Due: Tuesday, July 14, 9:00pm
Worth: 100 homework points

1. Write LinkedStringLog2.java to complete item b of Chapter 2 Exercise 50 on page 152.
   • Begin with ~cs20/p2/part1/LinkedStringLog.java (essentially the class on pp. 120-122). Your solution must be more efficient for at least one of the methods.
   • The ~cs20/p2/part1/ directory also contains StringLogInterface.java from page 72, LLStringNode.java from page 104, and IDTLinkedStringLog2.java (a slight modification of class ITDArrayStringLog from pp. 94-96) to test your work. But for your convenience (and ours), the package statements are removed from all files.
   • Your testing should insure that size() still returns correct results after inserts and after clear() is used.
2. Solve the problem introduced in Chapter 3 Exercise 35 on page 231, and fully test your solution.
   1. Complete EvenOddStack.java. Begin with ~cs20/p2/part2/EvenOddStack.java-skeleton.
      • The problem is to implement this (admittedly strange type of) stack using a single array, and therefore you must obey the following restrictions:
        1. Do not declare any additional instance variables. One array and two integers are sufficient to solve the problem.
        2. Do not use java.util.Stack or any other data structure class for any method.
      • The class must implement EvenOddStackInterface - see ~cs20/p2/part2/EvenOddStackInterface.java. Both pop and both peek methods must throw java.util.EmptyStackException if they are invoked for an empty (part of a) stack.
      • In addition to the 11 methods, include a no-argument constructor that creates the array to hold CAPACITY int values, and initializes the two index variables according to your solution's strategy.
      • Use ~cs20/p2/part2/EvenOddStackTester.java to test your class. See part b for execution instructions.
   2. Create stacktest.txt to fully test EvenOddStackTester.java and your EvenOddStack.java.
      • The application does not prompt the user. It reads commands from System.in.
      • Comment lines (first non-blank character is '#') and blank lines are ignored. Include comments in stacktest.txt to explain your testing plan.
      • Test routine, extreme and error cases as appropriate.
      • Just four commands are legal (case should not matter), and they all require at least one parameter.
        1. push d1 [d2 d3 ...] where the d values are the data to push. At least one d is required, and all d must be integers.
        2. pop s - where s is the stack section from which to pop, either even or odd.
        3. peek s - where s is the stack section at which to peek, either even or odd.
        4. clear s - where s is the stack section to clear, either even, odd or all.
      • The program terminates if it encounters an end-of-file mark or the word "quit" on a line by itself.
      • If these incomplete sample test data are input, these sample results must be printed.
3. Complete Palindrome.java to solve both parts c and d of Chapter 4 Exercise 22 on page 285. Begin with ~cs20/p2/Palindrome.java-skeleton, and just revise the two methods, pal1 and pal2. Notice that main already strips out any non-letters, and converts all letters to lower case before passing the string.
   1. Implement pal1 recursively (part c of the exercise).
   2. Implement pal2 without using recursion (part d of the exercise).
4. Improve a recursive method to raise a value to an integer power.
   • Start with a copy of ~cs20/p2/part4/Power1.java and write Power2.java with a more efficient power method.
   • See powers.txt for additional instructions and sample results.
   • There is no need to change main or any other part of the class. The application is run by including 2 command line arguments, the value to raise, and the power to which the value should be raised. The power must be a non-negative integer.
5. Turn in the five required files at once from your engineering account. Store all 5 files in the current directory, then:
   
   turnin p2@cs20 LinkedStringLog2.java EvenOddStack.java stacktest.txt Palindrome.java Power2.java
   Late projects may not be accepted.

Updated 6/30/09 by C. Michael Costanzo