CS100J    About Prelim III (Tuesday evening, 7:30--9:00PM, 18 November 2003, Uris Auditorium)

You should know everything that you needed to know for the first two tests --we review this below. Also, you should know:

While loops and for loops. We will give you a precondition, postcondition, a loop invariant, and you will have to develop the loop plus initialization from it. The grade will depend on how well you deal with the four loopy questions and the given invariant.

Arrays. Everything on Sects 8.1 and 8.2 of the class text--these pages discuss the technical details for using arrays in Java and for reasoning about array. We will not deal with two-dimensional arrays.

Algorithms. You should know the following algorithms. For example, if we ask "what is algorithm partition", you should be able to write the function: give the precondition and postcondition, write down the invariant, and then develop the loop with initialization. All these algorithms are discussed in the text or on the ProgramLive CD:

Algorithm Linear search (Sec. 8.5.1)
Algorithm Finding the minimum (Sec. 8.5.1)
Algorithm Partitioning an array segment (PLive activity 8-5.5)
Algorithm Binary search (Sec. 8.5.3)
Algorithm Selection sort (Sec. 8.5.4)
Algorithm Insertion sort (Sec. 8.5.5)

On selection sort and insertion sort, we will NOT want to see the inner loops. The repetends of these algorithms should be written at a high level, stating WHAT is done and not how it is done, as discussed in the text and in lecture.

With regard to classes and subclasses. You will have to write parts of classes/subclasses as on prelims II and II. Two ways to study: (1) Make sure you know the definitions below, and (2) Practice writing classes and subclass definitions. Take a look at other texts on Java and see what exercises they have for writing classes. And, when writing classes, write them in DrJava so you can test your syntax.

Definitions. Below is a collection of meanings of various terms. You are expected to know these backward and forward. On the test, wishywashy definitions will not get much credit. They must be the same as, or similar to the ones below --and they must be correct. Learn these not by reading but by practicing writing them down, or have a friend ask you these and repeat them out loud. You should be able to write programs that use the concepts defined below, and you should be able to draw folders and execute method calls, drawing the frames for the calls.

Variable: A named box that can contain a value of some type or class. For a type like int, the value is an integer. For a class, it is the name of (or reference to) an instance of the class —the name that appears on the folder.

Declaration of a variable: a definition of the name of the variable and the type or class of value it can contain. Syntax: type variable-name ;

Four kinds of variables: parameter, local variable, instance variable(or field), static variable (or class variables).

Parameter: A variable that is declared within the parentheses of a method header. The variable is drawn in a frame for a call on the method.

Local variable: A variable that is declared in the body of the method. The variable is drawn in a frame for a call on the method.

Instance variable: A variable that is declared in a class without modifier static. An instance variable is drawn in every folder of the class.

Static variable: A variable that is declared in a class with modifier static. An static variable is placed in the file drawer for the class in which it is declared.

Three kinds of methods: procedure, function, constructor:

A procedure definition has keyword void before the procedure name. The procedure call is a statement.

A function definition has the result type in place of void. The function call is an expression, whose value is the value returned by the function.

Argument: An expression that occurs within the parentheses of a method call (arguments are spearated by commas).

A constructor definition has neither keyword void nor a type, and its name is the same as the name of the class in which it appears. The constructor call is a statement, whose purpose is to initialize (some of) the fields of a newly created folder.

Folder (manila folder, object, or instance) of a class. An entity that is drawn like a manila folder. It has a name or label on its tab. Its contents are the instance methods and instance fields defined in the class definition.

New-expression. An expression of the form new class-name (arguments). It is evaluated as follows: (1) create a new folder of class class-name and put it in class-name's file drawer. (2) Execute the constructor call class-name (arguments); where the method called is one that appears in the newly created folder. (3) Yield as the result of the new-expression the name of the folder created in step (1).

Frame for a method call. The frame for a method call contains: (1) the name of the method and the program counter, in a box in the upper left, (2) the scope box (see below), (3) the local variables of the method, (4) the parameters of the method.

The scope box for a call contains: For a static method, the name of the class. For an instance method, the name of the folder in which the instance appears.

Call stack. The stack of frames for method calls that have been started but haven't yet completed.

To execute a method call:

1. Push the values of the arguments onto the call stack
2. Draw a frame for the call on the call-stack; it includes the values just pushed onto the call stack. Fill in its name and proam counter in the upper left box. Fill in its scope box on the upper right with either the name of the class in which the method is defined (static method) or the name of the folder in which the method appears (nonstatic method). Make the values of the argument on the call stack into the parameters. Draw local variables (uninitialized).
3. Execute the method body. When a name is used, look for it in the frame for the call. If it is not there, look in the place given by the scope box.
4. Erase the frame for the call.

Folder. We assume you can draw a folder, or instance of a class. For subclasses, remember that the folder has more than one partition. Look at the homework we had on drawing folders.

Class Object. Every class that does not explicitly extend another subclass automatically extends class Object. Class Object has at least two instance methods: toString and equals.

Calling one constructor from another. In one constructor, the first statement can be a call on another constructor in the same class (use keyword this instead of the class-name or a call on a constructor of the superclass (use keyword super instead of the class-name).

Overriding a method. In a subclass, one can redefine a method that was defined in a superclass. This is called overriding the method. In general, the overriding method is called. To call the overriden methodm (say) of the superclass, use the notation super.m(...).

Real and apparent class. A variable x defined using, say, CLASS x; has apparent class CLASS. The apparent class is used in determint whether a reference to a field or method is syntacally legal or not. One can write x.m(...), for example, if and only if method mis declared or is referenceable in class CLASS. The real class of x is the class of an object that is in x. It could be a subclass. If x.m(...) is legal, then it calls the method that is accessible in the real class, not the apparent class.

Casting. Just as one can cast an int i to another type, using, say, (byte) i or (double) i, one can cast a variable of some class-type variable to a superclass or subclass. Look in PLive to see about this.