CSCI 203 Exam 1   name_________________________________________

Short answer

1. What is 1+2+3+...+n?  Prove this using induction.
2. Show the operator and operand stack when processing of the infix expression has reached the next-to-last close-parenthesis.

(20 + 10 * 30 / 3 – (( 15 * 2 -10) -10) ) +5

3. For problem 1 show an equivalent postfix form of the expression.

4.

Suppose we have declared

public class Node{

public int data;

public Node next;

…}

And also

class List{

public Node front;

…}

Further suppose in some application we have

List MyList=new List();

Write (2) recursive List functions: to print the (int) contents of MyList forwards and also backwards. Show all necessary code in the List class. The call to print in the List API might be

MyList.print();

MyList.printBackwards();

5. Some, but not all permutations, of a sequence of (say) ints can be generated by passing the sequence “through” a stack, where every value must be pushed exactly once, and then written to output when it is popped. For the sequence 1,2,3, we might push 1, then push 2, then push 3, and then pop 3 times, creating the permutation 3,2,1. Which other permutations of the sequence 1,2, 3 are possible if the ints must be moved through a stack before outputting?
6. We discussed the 8-queens problem in class. The text describes an n-queen problem where n queens are to be (attempted to be) placed on an nXn chess board. Clearly the 1-queen problem is easy to solve. Which is the next integer n for which the problem can be solved? (Show a solution)

“Long answer” Code writing

1. Create a stack class that stores data type Object using an array for storage. Write the default constructor, the push, pop, peek, empty and full methods as we did in class. Throw StackExceptions for a call to pop when empty or a call to push when full.
2. Show the class StackException.
3. Add an int size to the stack class field declarations which is initialized in the constructor. Add a private method makeItBigger() to the class which could be called in push() for example, if the stack is full. In this method, reallocate the array to be 3/2 as big as it previously was and properly adjust the array and other fields.

4. .  Suppose there is an iterator for a link-list List class (as above). A separate class ListIterator could implements Iterator. (This example is in your notes). Show this class definition (fields, constructor, next() and hasNext(), omit method remove())

5. Write the recursive version of Euclid's greatest common divisor algorithm
if we have declarations:

int m,n;
//m and n have been initialized and m>=n then the call could be:
int answer= gcd(m,n);

What is the order of complexity of this function?