You can expect similar questions on the exam. Try to answer all the questions before looking at the solutions linked at the bottom.

## Fill in the blank

1. Abstract Data Types (ADTs) define two things: ____________________ and ____________________.

2. A class can be built in two ways:
• ____________________ (using instances of previously defined classes)
• ____________________ (extending a previously defined class)
3. If a method in a superclass is redefined (overridden) in one or more subclasses, that is a ____________________ method.

4. The two Bag implementations that we discussed used ____________________ and ____________________ as their underlying data implementations.

5. A program that executes $4n^2 + 100n + 10000$ operations for a problem of size N has a Big-O runtime of ____________________.

6. Recursive methods have three things:
• ____________________ case(s)
• ____________________ case(s)
• ____________________ (an important property - so that it won’t run forever)
7. Getting the ith item in an array is a O(__) operation, while getting the ith item in a linked list is a O(__) operation.

8. Divide-and-conquer is a problem-solving technique where each subproblem is ____________________ of the size of the larger problem.

## Short answer

1. Given this method signature, what kind of objects can be passed to it?

<T extends MyInterface> void doSomething(T thing);

2. Describe the binary search algorithm. It doesn’t have to be highly detailed, but it should be detailed enough that you could convert it to code relatively simply.

3. Can singly-recursive functions do anything that a loop cannot? Justify your answer.

4. Subtype polymorphism is very commonly used in Java, but there are really two kinds: class inheritance, and interface implementation. What is an advantage of each?

## Tracing and Analysis

1. Show what this code outputs.

interface Eats {
String getFood();
}

class Cat implements Eats {
String getFood() { return "meat"; }
}

class Cow implements Eats {
String getFood() { return "grass"; }
}

class Dog implements Eats {
String getFood() { return "who knows"; }
}

public static void main(String[] args) {
Eats[] eaters = new Eats[] {
new Cat(), new Cow(), new Dog()
};

for(Eats e : eaters) {
System.out.println(
"The " + e.getClass() +
" eats " + e.getFood());
}
}

2. Figure out the big-O runtime of these methods.

int one(int[] arr) {
int sum = 0;

for(int item : arr) {
sum += item;
}

return sum / arr.length;
}

int[] two(int[] arr) {
int[] ret = new int[arr.length];

for(int i = 0; i < arr.length; i++) {
int[] copy = Arrays.copyOf(arr, i);
ret[i] = one(copy);
}

return ret;
}

double three(int n) {
if(n == 0 || n == 1)
return 1.0;
else
return three(n - 1) + (1.0 / n);
}

3. Draw the linked list as it appears at the two indicated points.

class Node {
int value;
Node next;
Node(int v) { value = v; }
}

public static void main(String[] args) {
Node a = new Node(10);
Node b = new Node(20);
Node c = new Node(30);
c.next = b;
c.next.next = a;
// >>>>>>>>>>>>>HERE<<<<<<<<<<<<<<<<
Node d = new Node(40);
Node e = new Node(50);

d.next = c.next.next;
c.next.next = d;

Node n = c;
while(n.next != null)
n = n.next;

n.next = e;
// >>>>>>>>>>>>>HERE<<<<<<<<<<<<<<<<
}

## Application

1. Evaluate this postfix expression using the algorithm we learned. Show each step in the table.

3 5 + 2 10 4 - * -

Remaining tokens Operand stack

2. You are making a system for reserving seats on airplanes. You need to keep track of which seats are taken and which are available. Airplane seats are built into the airplane and there are a limited number of them. Of the following three implementations, which would you choose and why?

• Linked list
• Fixed-size array
• Resizable array

Now check your answers here.

# Topics to study

### Java Programming

• subtyping
• class subtyping
• interface subtyping
• virtual methods
• what they are
• what they’re useful for
• how it knows which one to call at runtime
• polymorphism
• the general idea
• kinds of polymorphism
• generics
• what they let you do
• how to write them
• what type bounds are and how to write them
• how generics and interfaces work together

### Data Structures

• ADTs
• what they define
• what they don’t define
• what Java constructs correspond to one
• what Java constructs can’t handle
• Bag
• its ADT description
• fixed-size array implementation
• upsides and downsides
• resizable array implementation
• how it works
• upsides and downsides
• linked list implementation
• what a linked list is
• how it differs from an array
• Stack
• its ADT description
• common uses
• Parsing
• matching braces
• infix-to-postfix
• expression evaluation

### Theory

• Algorithm analysis
• the idea (behavior “in the long run”)
• O() notation
• how to analyze something
• sequential steps add (and then O() drops lower terms)
• loops multiply
• intuition behind worst and best case
• intuition behind “average case”
• Amortized analysis
• the idea (“when you spread it all out”)
• used for situations where runtime fluctuates over time
• look at behavior of a sequence of operations; total it; and divide by n
• recursion
• what it is
• what it really is
• recursive/base cases
• termination
• single vs. multiple recursion
• tail recursion
• divide-and-conquer
• idea (splitting problem into fractionally sized subproblems)
• taking advantage of “symmetry” of problems to avoid duplicating work
• binary search
• backtracking
• just the idea of it
• what the parts of the template do
• will have more involved questions on final (after you have proj3)