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

Abstract Data Types (ADTs) define two things:
____________________
and____________________
.  A class can be built in two ways:
____________________
(using instances of previously defined classes)____________________
(extending a previously defined class)

If a method in a superclass is redefined (overridden) in one or more subclasses, that is a
____________________
method. 
The two
Bag
implementations that we discussed used____________________
and____________________
as their underlying data implementations. 
A program that executes operations for a problem of size N has a BigO runtime of
____________________
.  Recursive methods have three things:
____________________
case(s)____________________
case(s)____________________
(an important property  so that it won’t run forever)

Getting the ith item in an array is a
O(__)
operation, while getting the ith item in a linked list is aO(__)
operation.  Divideandconquer is a problemsolving technique where each subproblem is
____________________
of the size of the larger problem.
Short answer

Given this method signature, what kind of objects can be passed to it?
<T extends MyInterface> void doSomething(T thing);

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.

Can singlyrecursive functions do anything that a loop cannot? Justify your answer.

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

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()); } }

Figure out the bigO 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); }

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

Evaluate this postfix expression using the algorithm we learned. Show each step in the table.
3 5 + 2 10 4  * 
Remaining tokens Operand stack 
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
 Fixedsize array
 Resizable array
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
 fixedsize 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
 infixtopostfix
 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
 divideandconquer
 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)