CPSC 225, Spring 2019
Information About the First Test

The first test will be given in class on Wednesday,February 27. The test will cover everything that we have done from the beginning of the term through class on Friday, February 22. This includes: subclasses, inheritance and interfaces; preconditions, postconditions, and invariants; exceptions and the try..catch..finally statement; the analysis of algorithms; recursion; linked lists; the concept of abstract data types; and stacks and queues. The reading for this material is Sections 5.5, 5.6, 5.7, 8.2, 8.3, 8.5, 9.1, 9.2, and 9.3. We have also talked about a few things that are not in the textbook, such as doubly-linked lists and turtle graphics.

You can expect a variety of questions on the test. There will be some definitions and essay-type questions. There could be one or two questions that ask you to analyze the run time of some code. Some questions will ask you to write code segments or methods or possibly even complete classes. There might also be some questions that ask you to read some code and figure out what it does.

Here are some terms and ideas that you should be familiar with:

    extending a class
    subclasses and superclasses
    class hierarchies
    overriding a method in a subclass
    "protected" access modifier
    using "super" to call a method from the superclass or to refer to a variable in the superclass
    using "this" and "super" to call constructors
    abstract classes and abstract methods
    "implementing" an interface
    class Object; every class is a direct or indirect subclass of Object
    the toString() method

    loop invariants
    class invariants
    thinking about program correctnexx
    exceptions are represented in Java by objects in subclasses of Throwable
    how exception handling compares to other ways of dealing with errors
    handling exceptions: the try..catch statement
    the finally clause in a try statement, and why it might be used
    throwing exceptions:   throw new ExceptionClass(errorMessage);
    checked exceptions and mandatory exception handling
    questions of efficiency of a program
    run-time analysis of algorithms
    worst-case analysis, best-case analysis, and average case analysis
    log2(n) and how it arises in analysis of some algorithms
    "Big Theta" and "Big Oh" notation ( Θ(f(n)) and O(f(n)) )
    comparing Θ(n) to Θ(log(n)), or Θ(n2) to Θ(n*log(n))
    disregarding "constant multiples" and "lower order terms"
    Linear Search (run time Θ(n)) versus Binary Search (run time Θ(log(n)))
    Selection Sort and Insertion Sort have run time Θ(n2)
    recursive subroutines
    direct recursion and indirect recursion
    base case of a recursion, and why base cases are essential
    infinite recursion
    maze-solving, blob-counting and similar recursions
    why "marking" locations as already visited is important
    recursive geometric objects such as the Koch Curve and Sierpinski Triangle
    using turtle graphics and recursion to draw pictures of recursive geometric objects
    the QuickSort recursive sorting algorithm
    the general idea of why QuickSort has average case run time Θ(n*log(n))
    the worst case run time of QuickSort is Θ(n2)
    linked data structures
    understanding names such as "employee.boss.name" and "node.next.next"
    simple linked lists
    the head of a list; why you always need to keep a pointer to the head
    traversing a linked list; using a "runner" to move down the list
    basic linked list processing, such as searching, or adding up items in a list
    the meaning of "while (runner != null)" and "runner = runner.next"
    adding a node to the head of a list
    why working at the head of a list is often a special case
    inserting and deleting nodes in a list
    doubly-linked lists; next and prev pointers
    using a "sentinel node" at the head of a list
    Abstract Data Types (ADTs)
    an ADT can have more than one implementation
    the "Stack" ADT
    stack operations: push, pop, isEmpty
    how to implement a stack as an array
    how to implement a stack as a linked list
    the "Queue" ADT
    queue operations: enqueue, dequeue, isEmpty
    how to implement a queue as a linked list with tail pointer
    how recursion is implemented using the stack of activation records
    using a stack or a queue instead of recursion

Here are a couple of sample essay-style questions, to give you an idea of what kinds of questions might be asked:

1. Explain what it means to override a method in a subclass, and why you might want to do that.

2. Briefly explain how the binary search algorithm searches for an item in a list of items, and why it is much faster than simple linear search.

3. When your program encounters an error at run time, why is it a good idea to throw an exception rather than, for example, print an error message or terminate the program?

4. Explain what is meant by an Abstract Data Type (ADT). What is the definition of a stack as an ADT?

Here are a few practice questions about pointers and linked data structures. These questions use the following classes and variable:

         class ListNode {               class IntNode {
            String item;                    int item;
            ListNode next;                  IntNode next;
         }                              }
         ListNode head;  

1. Draw the data structure that is created by the following code segment (the result will NOT be a proper linked list):

          ListNode n1, n2;
          n1 = new ListNode();
          n1.next = new ListNode();
          n1.item = "Johnny";
          n1.next.item = "Jane";
          n2 = new ListNode();
          n2.item = "Jill";
          n2.next = n1;
          n2.next.next.next = n1;

2. Write a code segment that will print every other string in the list that head points to. That is, print the second, fourth, sixth, eighth, ... elements, but not the first, third, fifth, seventh, ..., elements.

3. Write a code segment that will find and print the longest string in the list that head points to. (If there are several strings with the same maximal length, output the one that comes first in the list.)

4. Suppose that front is a variable of type IntNode that points to a linked list of integers. Write a code segment that will print out all the non-zero numbers in the list.

5. Write a method with one parameter of type IntNode, representing a list of integers, and a return type of boolean. The method should test whether the integers in the list are already sorted into increasing order.

6. Write a recursive method with one parameter of type IntNode that finds the number of nodes in the list in which the item is equal to 17.

Here is a practice problem on subclasses:

Suppose that a class named Document has a method public void print() that prints the document. A subclass is needed that will do everything Document does, but it will also keep track of how many times the document has been printed. The subclass will have a counter to count the number of times the document is printed and a method that returns the number of times it has been printed. In addition to printing the document, the print() method in the subclass must also increment the counter. Write the specified subclass.

Here are two practice problems about recursion.

1.  Consider this recursive method:   |   2.  Consider the following recursive
                                      |       method using turtle graphics:
       void guess(int level) {        |          
       if (level == 0) {              |       void draw(double size, int level) {
          System.out.print("*");      |          if (level == 0) {
       }                              |              turtle.forward(size);
       else {                         |          } else {
          System.out.print("(");      |              turtle.forward(size/2);
          guess(level - 1);           |              turtle.turn(90);
          System.out.print(("|");     |              draw( size/2, level-1 );
          guess(level - 1);           |              turtle.turn(180);
          System.out.print(")");      |              turtle.forward(size/2);
       }                              |              draw( size/2, level-1 );
    }                                 |              turtle.turn(180);
                                      |              turtle.forward(size/2);
    a) Show the output from guess(1)  |              turtle.turn(-90);
    b) Show the output from guess(2)  |              turtle.forward(size/2);
    c) Show the output from guess(3)  |         }
                                      |      } 
                                      |        a) Show the drawing from draw(10, 0)
                                      |        b) Show the drawing from draw(10, 1)
                                      |        c) Show the drawing from draw(10, 2)
                                      |        d) Show the drawing from draw(10, 3)

And here are some practice problems on analysis of algorithms.

Consider the following subroutines. Each subroutine processes an array, A, of integers. In each case, discuss the run time of the code as a function of the array size, N. (The subroutines are not necessarily meant to do anything useful!)

 1)     static void One(int[] A) {
            int sum = 0;
            for (int i = 0; i < N; i++) {
               for (int j = 0; j < N; j++)
                  sum = sum + A[i]*A[j];

 2)     static boolean Two(int[] A) {
            int N = A.length;
            for (int i = 1; i < N; i++) {
               for (int j = 0; j < i; j++) {
                  if (A[i] == A[j])
                     return false;
            return true;
 3)     static int Three(int[] A) {
            int N = A.length;
            int s = 0;
            int i = 1;
            while (i < N) {
               s = s + A[i];
               i = 2 * i;
            return s;