The exam is open book and open notes. Remember to bring your text with you since no sharing of books will be allowed. You may not bring any other texts besides our own.

Here's a list of major topics to help you get started in studying. This is not a complete list. Anything in lecture or the text is your responsibility. A complete list of reading assignments can be found in the Full Schedule on our web page.

Java and Object-Oriented Programming (OOP)

• arrays
  • random access
  • contiguous
• public vs protected vs private variables, classes, methods
• objects vs instances
• instance, local, and parameter variables (and criteria for determining when you should use each type of variable)
• messages
• instance methods, constructors (and how to write them)
• prototypes, signatures, access modifiers, return types
• getters and setters
• writing your own classes
• primitive types vs. object types
• inheritance, polymorphism, overridden vs. overloaded methods
• pass-by-value mechanism of parameter passing
• this
• linked lists
• explicit and implicit casting
• short-circuiting
• Javadocs (how to write, how to read)

Good Program Design (OO goals)

• coherency
• reuseability
• modularity
• efficiency
• understandability
• debugging techniques
• testing techniques
• top-down design
• memory diagrams (how to read, how to draw)

Time Complexity

• Determing exact running time and Big-O running time for
  • an algorithm
  • an implementation
• Where Big-O comes from and why we use it

1. (answerable following Wednesday's class) A circular linked list is a variation on a regular linked list where instead of the last node pointing to null, it points to the first node. Like this for a linked list holding integers:
   

   So if the linked list had only 1 node in it, that node would point to itself. And if the linked list had 0 nodes in it, firstNode would point to null.

   Given the following classes to create the above circular linked list:

   public class LinkedList
   {
      private int length;          //# of nodes in the chain
      private ListNode firstNode;  //pointer to 1st node in chain
   
      public LinkedList()
      {
          length=0;
          firstNode=null;
      }
   }
   
   public class ListNode
   {
      public int data;            //the integer this node has
      public ListNode next;       //pointer to next node
   
      public ListNode(int value)
      {
          data=value;
          next=null;
      }
   }
   

   Write a method called findInteger() that will go into the LinkedList class. This method takes a single integer called "key" as a parameter. It will return a pointer to the first ListNode in the circular linked list that has key as its data value. It will return null if "key" doesn't exist.

2. For the method above, what cases would you want to test to ensure that this method is working properly?

3. For the following code fragment, compute (1) the EXACT number of times that the array A will be accessed in terms of n and (2) the running time in Big-O notation:

   for (int i=1; i<=n; i++)
     for (int j=1; j<=i; j++)
       for (int k=1; k<=5; k++)
          A[i,j] = k;
   

4. Consider the following class:

   public class Pasta
   {
       protected String flour;  //flour type used in making this pasta
   	
       public Pasta()
       {
           flour = "semolina";
       }
   }
   

   Write three new classes as follows:

   1. A Ravioli class which is a child of Pasta. It should have just one instance variable: filling (a String) that stores the type of filling this ravioli has. It should have just a single non-default constructor, and no default constructor. This constructor will take a single parameter, filling_type, which is the filling this ravioli object ought to have. The flour type will be semolina flour.

   2. A MeatRavioli class which is a child of Ravioli. Representing meat-filled ravioli, this class has no instance variables of its own, but it does have two constructors: one default, one non-default. The non-default constructor will take a single parameter representing the type of meat to be used with this object. The default constructor will create beef-filled ravioli. No matter which constructor is used in creating meat ravioli, the flour used will still be semolina flour.

   3. A CheeseRavioli class which is similar to the MeatRavioli class. This class repesents cheese-filled ravioli, and the default constructor will create ricotta cheese-filled ravioli. In all other respects, CheeseRavioli should be the same as MeatRavioli.

Answers are on a separate page. Try the problems yourself before looking at them!