comp 110
Sample Solution for Exam 2

1) [5 points]  Define the following.  Be as concise as possible.	
	i)  Constructor.  What is it, and what are its responsibilities?

[2 points] A constructor is a special method of a class that is called when you use the
new operator.  

[3 points] It creates and initializes an object of the class in which it
is defined.

Grading - they must mention 'class' somewhere in their answer.  The sample solution
mentions 'class' in both parts.  Mentioning in only one part is sufficient for
full credit.

2) [5 points]  Compare and contrast the following. Briefly explain each, their similarities, and their differences.
	i)  class vs. object


A class is is a definition (blueprint) for a kind of object.  It defines a pattern.
An object is an instance of a class - full credit.
An object is a variable of type class - full credit

Example:
    Alien alien = new Alien();
      1     2           3

1 is the class
2 is the object (variable)
3 is the call to the constructor method


3) [15 points]  Given the following code segment
a) [7 points] What is the output?

Output
s = 0
t = 2
s = 1
t = 4
t = 5
s = 3
3 5

b) [8 points] Convert the code so that it uses nested while statements instead of for statements.

		int s = 0;
		int t = 1;
		for (int index = 0; index < 3; index++) {
			s = s + index;
			for (int j = index; j > 0; j--) {
				t = t + j;
				System.out.println("t = " + t);
			}
			System.out.println("s = " + s);
		}
		System.out.println(s + " " + t);




		int s = 0;
		int t = 1;
		int index = 0;
		while(index < 3 ) {
			s = s + index;
			int j = index;
			while( j > 0) {
				t = t + j;
				System.out.println("t = " + t);
				j--;
			}
			System.out.println("s = " + s);
			index++;
		}
		System.out.println(s + " " + t);
	


4) [30 points]  Given a string, we want to check if the characters are in alphabetical order.  For example, the string s1 = “brttu” is in alphabetical order but s2 = “brutz” is not.
Additionally, ignore any blank spaces (character ‘ ‘) that occur in the string. For example,
“  brtt u  “ and “bru t z” evaluate the same as s1 and s2, respectively.  Return the index of the first character in the string that is out of alphabetical order (or return -1 if all characters are in alphabetical order). The signature for the method is

public static int isAlpha(String str) {
…
}

isAlpha(s1) returns -1 and  isAlpha(s2) returns 3

This answer shows in detail the thought process used to derive the solution.  You are
not expected to show any of these steps.

The solution to this problem is shown at the very bottom. This is all that is required
for full credit.  You do not need to show your individual steps, test method, etc.
However, the following shows these as an example of careful, step by step
program development. You are free to approach the problem any way you want, but the
following is clear and systematic.  It aids in getting partial credit should you not
complete the problem.

The following shows how to grow the program one step at a time.
Growing your program is not required for full credit but
--- it helps you get the correct program
--- you can get substantial partial credit if you show your work and demonstrate
that you are going in the right direction (even though there may be mistakes
in your final code).

This question also requires problem solving - break a big problem down into
smaller ones.  This semester, we have seen two basic methods:
--- Linear - break problem into a series of smaller problems (the individual
steps in the Implementation Plan)
---  Layers- solve a simplified version of the problem then extend it.
Both of these are shown in the following development of the solution.


Problem solving by layering.  Ignoring blanks in the string complicates things.
The essential problem is checking for alphabetical order.  Lets do this first,
then add on to finish the code.

Version 1 - check for alphabetical order assuming no blanks in the string
Version 2 - add to Version 1 to accomodate blanks

Problem solving by linear growth. We grow Version 1 one small step at a time.
The following steps illustrate how your answer may have grown.



**********************************************************
Version 1 - Step 1 - skeleton and test method (optional).
**********************************************************

	// Version 1 - assume no blank spaces in str
	public static int isAlpha( String str ) {
		int result = -1;
	
		
		return result;
		
	}
	
	// Test method shown for completeness. It is not required
	// for full credit to this test question.
	public static void testVersion1() {
		System.out.println(isAlpha("abcdefg")); // Y - simple
		System.out.println(isAlpha("abbcdeeefg")); // Y - duplicates
		System.out.println(isAlpha("abcdefeg"));  // N
		System.out.println(isAlpha("a")); // Y
	}

*****************************************************************
Step 2 - loop executes for index 0,1,..., str.length()-1

Our robot algorithm is.
    1. Walk thru the string one character at a time.
    2. Compare each character to the following character.
    3. if they are out of alphabetical order, we are done
       otherwise move to the next character.

Programming this in Java requires a loop (a linear scan of the string)
with a test for alphabetical order as the body of the loop.
When writing loops:
  1. Get the loop to execute the correct number of times
  2. Add the useful work.
The indices into the string are 0, 1, ..., str.length()-1
We will compare a character to the character to its right so we must
be careful to stop the loop at index str.length()-2.
On the exam, -3 if you missed this.
*****************************************************************


	public static void main(String[] args) {
		isAlpha1("abcdefg");
	}
	
	// Version 1 - assume no blank spaces in str
	public static int isAlpha( String str ) {
		int result = -1;
	    int index = 0;
	    while( index < str.length() - 1) {

		// Trace output. Not required for test answer.
	    	System.out.println(index);    	
	    	index++;
	    }	
		return result;		
	}

*****************************************************************
Step 3 - check for alphabetical order

In Step 2, the loop executes the correct number of times. Now we
add the useful work as the loop body.
*****************************************************************
	// Version 1 - assume no blank spaces in str
	public static int isAlpha( String str ) {
		int result = -1;
	    int index = 0;
	    while( index < str.length() - 1) {

		//*********************
	    	if(str.charAt(index) > str.charAt(index+1))  
	    		return index;

	    	index++;
	    }		
		return result;		
	}

Output from my test program - whoops this fails on the last test case
-1
-1
5
-1

On the exam, -3 if you missed this.

We fix this by adding a check for length 1 at the start of the method.

	// Version 1 - assume no blank spaces in str
	public static int isAlpha( String str ) {

            //****************
            if(str.length() == 1) return -1;

	    int result = -1;
	    int index = 0;
	    while( index < str.length() - 1) {
	    	if(str.charAt(index) > str.charAt(index+1))  
	    		return index;
	    	index++;
	    }		
		return result;		
	}

This is a complete solution to the simplified Version 1.
25 out of 30 points for coming this far.


*****************************************************************
Version 2 - handle blanks. Full credit for this code or
   similar code.

Now we have a solution to the simplified problem (checking for
alphabetical order in a string with no blanks).  How can we use this
to solve the exam question? One way is to  make a copy of str
removing the blanks from the copy. This is acceptable for full credit.
*****************************************************************

	// Version 2 - handle blanks
	public static int isAlpha1( String str ) {
		if(str.length() == 1) return -1;
		
		//*********************************
		String strNoBlanks = "";
		for(int index = 0; index < str.length(); index++ )
			if(str.charAt(index) != ' ')
				strNoBlanks = strNoBlanks + str.charAt(index);
		System.out.println(strNoBlanks);
		
		int result = -1;
	    int index = 0;
	    while( index < strNoBlanks.length() - 1) {
	    	if(strNoBlanks.charAt(index) > strNoBlanks.charAt(index+1))  
	    		return index;
	    	index++;
	    }		
		return result;		
	}



*****************************************************************
Version 2 - handle blanks. Full credit for this code or
   similar code.
Another, even simpler way is to add skipping blanks to our
Version 1 loop.
*****************************************************************

	public static int isAlpha( String str ) {
            if(str.length() == 1) return -1;

	    int result = -1;
	    int index = 0;
	    while( index < str.length() - 1) {

		//*********************************
		if(str.charAt(index) == ' ') index++;
	    	else { if(str.charAt(index) > str.charAt(index+1))  
	    			return index;
	    	       index++;
		    }
	    }		
		return result;		
	}
****************************************************************