class Dog {
   private String name;
   private double weight;
   public Dog(String name, double weight) {
      this.name= name;
      this.weight= weight;
   }
}
class ListNode {
   int data;
   ListNode next;
}
class MyStack {
   // internal implementation not specified, but does have these methods
   public void push(char elem) {}
   public char pop() {}
   public boolean isEmpty() {}
}

1. (4 pts) Expand the acronym FIFO. What data structure is it associated with?

2. (4 pts) Name two assumptions that must be true for a binary search to be possible.

3. Refer to the Dog class defined on the first page of this exam and to the following function and then answer these questions about containers and sorting:

   public static void sortDogs(Dog [] dogs, int n) {
      int i,j;
      Dog temp;
      for (i=0; i<n-1; i++)
         for (j=i+1; j<n; j++)
            if (dogs[i]<dogs[j]) {
               temp= dogs[i];
               dogs[i]= dogs[j];
               dogs[j]= temp;
            }
   }
   

   1. (2 pts) What is the name of the sort depicted above?
   2. (2 pts) Upon completion of the sortDogs() function, what order would the objects in the dogs parameter be placed?
   3. (6 pts) Write a standard .compareTo() method for the Dog class that will compare dogs by comparing their weight.
   4. (3 pts) Show how the if-statement in the sort above would be modified to use a standard .compareTo() method to cause the sort to list the dogs in order of weight with heaviest weight first.
   5. (8 pts) Write a section of code that will declare/create a Java ArrayList to hold Dog objects. Insert 4 Dog objects into that ArrayList. Then use a loop to iterate the ArrayList and display to the screen each dog object. You can assume an appropriate .toString() method has been defined for the Dog class.

4. (6 pts) Show how the following array would be processed if it were partitioned one time using the partition algorithm that accompanies Quicksort.

   (NOTE: This question is asking you to partition the array once ... not do an entire quicksort).

5. (4 pts) Using words, give a recursive description of how a binary search finds an element in a sorted list.

6. Use the ListNode class given at the beginning of the exam to to answer these questions.
   1. (8 pts) Write a method called removeLast that will accept the head of a linked list (i.e., a ListNode) as a parameter and will traverse to the end of the list and remove the last element of the list.
   2. (6 pts) Write a method called isOrdered that will accept the head of a linked list as a parameter and will return true if the elements in the list are arranged from smallest to largest. It should return false otherwise. If the list is empty it should return true.

7. Answer these questions about stacks and the MyStack class given above.
   1. (4 pts) Suppose that when a letter is encountered we push it on the stack and when an asterisk is encountered we pop the stack. Show the sequence in which letters would be popped for the following string:

         RM*RAEE**RNIT***IC***LC*U*****MO*O**
      

   2. (4 pts) Contrast an array-based stack implementation with a list-based stack implementation. Give advantages of each over the other.

   3. (10 pts) Write a method called matchParens() that accepts a String parameter containing an expression with square brackets and braces (e.g., “[[x+y-z]+[a-b]/c]+5-2]”). The method will return true if the brackets are properly matched and false if not.

      Assume the existence of a working MyStack class outlined on the first page of this exam. Use the stack to help determine whether or not the expression is valid.

8. Answer these questions about queues.
   1. (4 pts) Suppose that when a letter is encountered we put it in the queue and when an asterisk is encountered we remove from the queue. Show the sequence in which letters would be removed for the following string:

         RM*RAEE**RNIT***IC***LC*U*****MO*O**
      

   2. (4 pts) Briefly describe (using words) how to provide an efficient array-based solution to implementing a queue.

9. (4 pts) Which homework assignment in this course was your favorite? Why?

10. (4 pts) Which topic in this course was your favorite?