Final Exam Flashcards
Declaring a class to be Iterable
public class SimpleLinkedList implements Iterable {
// class body goes here up to the Cursor definition
private class Cursor implements Iterator {
// Same code for Cursor as before
}
public Iterator iterator() {
return new Cursor();
}
}
base case
The exit condition describes the base case condition. The base case is the easiest problem to solve. Every recursive solution must have at least one base case.
exit condition
The body of the recursive method is controlled by a selection statement (if, etc). At least one of the alternatives does not contain a recursive call. The condition associated with that alternative is the exit condition.
tail recursive
That is, the recursive call as the last statement in the method. Tail recursive methods are usually easy to convert to loops. Recursive methods that are not tail recursive can be more difficult. To convert those, you essentially have to mimic what the virtual machine does with your own stack.
recursive method finds the largest element in an array.
public int max(int x, int y){
if (x >= y)
return x;
return y;
}
/**
* Find the largest element in the array.
* @param start is the smallest index to start looking.
* @return the largest element in an array, beginning at index start.
*/
public int largest(int[] array, int start){
if (start == array.length - 1)
return array[start];
return max(array[start], largest(array, start + 1));
}
The sum of digits in 1246 is- recursive method ex
/**
* Find the sum of digits in an integer.
* @param num is a non-negative integer (num > -1).
* This method fails if num < 0.
* @return the sum of digits in number
*/
public int digitSum(int num){
if (num == 0)
return 0;
return (num%10) + digitSum(num/10); // num%10 is the one's digit
// num/10 has the rest of the digits
}Recursive list methods code
public class RecursiveList {
private List list;
public RecursiveList() {
list = null;
}
public void addToFront(String element) {
list = new List(element, list);
}
public int size() {
if (list == null)
return 0;
return list.size();
}
private class List {
public String element;
public List next;
public List(String element, List next) {
this.element = element;
this.next = next;
}
public int size() {
if (next == null)
return 1;
else
return 1 + next.size();
}
} }
components
The graphical elements of GUIs are components. Components such as windows that hold other components are containers. The top-level window, which has a border and a title bar, is a kind of component called a frame. Components also include widgets that the frame contains, such as buttons, text fields, labels, and menus. The frame layout refers to how the contents of the frame are arranged. Containers add widgets to their display. A widget must add an event listener in order to detect when a user interacts with it.
event-driven
GUI programs are event-driven. That means they respond to user interactions or events. Events are generated when the user clicks a button, presses a key, selects text, or such. With an event-driven programs, there is no “loop to request input followed by process the input,” which is the norm for console-based programs.
Model-View-Controller
The model is the backend logic. It maintains the state and data for the program.
The view is the part of the user interface that displays information about the model to the user. An example is a label that indicates the result of a calculation.
The controller is the part of the user interface for manipulating the application. An example is code that requests a calculation when the user clicks a particular button.
Event listeners
Event listeners are objects that determine when events occur. Buttons or other components with which the user can interact must register listeners. For example, an action listener for a button can determine (“listen for”) when the user clicks the button.
content pane
Content panes are lower level containers, typically embedded into primary windows. They are used to organize the structure of the main window. Swing examples of content panes include JPanel, JOptionPane, JTabbedPane, and JSplitPane among others. Every JFrame has a content pane, which you can access via the JFrame method getContentPane(). In order to put a component on a JFrame, you must add the component to the JFrame’s content pane.
Dialogs
Dialogs are secondary windows. They are typically opened on special conditions and must be closed by the user. JDialog is the Swing class for dialogs.
linear search
A linear search of a collection requires looking at every element in the collection, one-at-a-time, stopping when the value is found. If you get through the entire collection without finding the value, then the search is unsuccessful.
binary search
can be used on ordered arrays. The algorithm for a binary search is as follows. O(log n)
Compare the searched for value to the middle array item
value == middle ==> quit. You’ve found it.
value < middle ==> consider the sublist making up the first half of the array (before the middle item)
value > middle ==> consider the sublist making up the last half of the array (after the middle item)
If you didn’t find the value, repeat the search on the sublist. You are done as soon as you find the item or whenever the sublist that you are supposed to search is empty.
public int binarySearch(int [] a, int start, int stop, int toFind)
{
if (start > stop) // There’s no place to look. Quit.
return -1;
int middle = (start + stop) / 2; // Look here first
if (toFind == a[middle]) // Found item. Quit.
return middle;
if (toFind > a[middle]) // Look in the last half
return binarySearch(a, middle + 1, stop, toFind);
else // OR look in the first half
return binarySearch(a, start, middle - 1, toFind);
}
Logarithmic complexity
This means binary search is O(log n). We say that binary search has logarithmic complexity.
Sorting a collection
Sorting a collection means arranging the elements in the collection into a particular order. Classes that implement Comparable are eligible as elements in a sorted collection. That means they must define compareTo(T). Some sorts on primitives are also available.
Classes in the Java API that support sorts include Arrays and Collections. Both are in the java.util package.
There are three elementary sorts that are useful for small amounts of data:
Selection sort. The front part of the collection consists of the smallest elements and is completely sorted. Technique: look for the smallest remaining element in the collection and move it to the end of the sorted front part. O(n^2)
Insertion sort. The front part of the collection is sorted (though the elements are not necessarily the smallest in the collection). Technique: take the first element of the unsorted part and insert it into the proper position in the sorted front part. O(n^2)
Bubble sort. Swap out of order adjacent pairs of elements. Continue to do this until the collection is sorted.
Merge sort
Merge sort is a classic example of a divide and conquer algorithm. The algorithm is simply described:
Break the list into two pieces.
Sort each piece.
Merge the sorted pieces together to form a sorted list.
The computational complexity of merge sort is O(n log n)
The application of the merge sort algorithm to an array of ints is shown below. It requires copying parts of arrays. This is done by Arrays.copyOfRange(array, from, upto)
Quicksort
Select any particular element as a pivot element.
Move all elements smaller than the pivot into the first part of the list.
Move all elements larger than the pivot into the second part of the list. (The pivot will wind up in the middle.)
Quicksort the first part and the second part.
O(n log n)
binary tree
A binary tree is a hieararchical data structure that consists of nodes. Each node contains an element and two other trees, which are called the a left subtree and a right subtree. In the picture below, each node is a circle with a letter (element) and 0, 1, or 2 arrows , which point the subtrees of the node.
The node at the top of the tree is called the root node. The root node in the figure above is A; it is colored gold. The nodes that have empty subtrees are called leaf nodes. The leaf nodes in the figure are C, F, and G; they are colored green. A branch node is any internal node (neither root nor leaf).
B is a left child of A, D is a right child of A. D is the parent of E. Two nodes such as B andD with a common parent are siblings. Any node in a subtree rooted at a given node is a descendant of the node. The given node is an ancestor.
full binary tree
very node in a full binary tree has either 0 or 2 children.
traversal types
Preorder traversal. The root of a tree is visited first. The left subtree is visited next. The right subtree is visited last.
Inorder traversal. The left subtree is visited first. The root of a tree is visited next. The right subtree is visited last.
Postorder traversal. The left subtree is visited first. The right subtree is visited next. The root of a tree is visited last
binary search tree
A binary search tree is a binary tree in which:
the elements are comparable
the root element is greater than all the elements of the left subtree
the root element is less than all the elements of the right subtree
the right and left subtrees of the root are also binary search trees
