Transcript Review Slides - University of Hawaii

Course Review
ICS 211
Cam Moore
Information and Computer Sciences
University of Hawaii, Manoa
(1)
Java Concepts
Objects vs. Primitives
• References
• Equality
• Comparison
Generic Types
Collections
• iterators
(2)
Data Structures
Arrays
• Fixed size
• System.arrayCopy(src, srcPos, dest, destPos,
length)
• Constant time access
• Can have empty space
(3)
Data Structures
Lists
/** An ordered collection. The user can access elements by their
* integer index, and search for elements in the list. */
public interface List<E> extends Collection<E> {
E get(int index);
// returns object at given position
E set(int index, E element); // sets element, returns old value
int indexOf(Object o); // returns index of object in list
E remove(int index); // removes object at the given position
int size();
// returns number of elements in list
boolean add(E element); // add element at the end of the list
void add(int index, E element); // add element at given position
}
• Variable size
• Linked and Array Implementations
- Performance
(4)
Data Structures
Stacks
/** A Stack represents a Last-In-First-Out (LIFO) stack of objects. */
public interface Stack<E> {
boolean empty();
// returns true if the stack is empty
E peek(); // looks at the top item of the stack w/o removing it.
E pop(); // removes the top item in the stack, returning it.
E push(E element); // pushes an item onto the top of the stack.
}
• Linked vs Array Implementation
- Performance
• Uses
(5)
Pre, In, Post fix Notation
Prefix Notation
• Operator, Operand1, Operand2
• No operator precedence
Infix Notation
• Operand1, Operator, Operand2
• Has operator precedence and parentheses
Postfix Notation
• Operand1, Operand2, Operator
• No operator precedence
(6)
Data Structures
Queues
/**A collection designed for holding elements prior to processing. */
public interface Queue<E> extends Collection<E> {
public boolean add(E e); // Inserts element to end of queue, throws exception
public boolean offer(E e); // Inserts element to end of queue
public E element(); // Retrieves, but doesn’t remove, the head of the queue
public E peek(); // Retrieves, but doesn’t remove, the head or null
public E poll(); // Retrieves and removes the head or null if queue is empty
public E remove(); // Retrieves and removes the head of the queue
public int size(); // Returns the number of elements in the queue.
}
• Add to the rear, remove from the front
• Array vs Linked implementation
- Performance
• Uses
(7)
Data Structures
Trees
• Terminology:
- root, child, siblings, parent, height/depth,
branch, leaf
• Binary Trees
- Full, Perfect, Complete
- Traversals: pre order, in order, post order
• Binary Search Trees
(8)
• Huffman Trees
Data Structures
Heaps
• Helper data structure
• Parents are > or < children
• Implemented in complete binary tree
- left child = 2 * p + 1, right child = 2 * p + 2
- parent = (c – 1) / 2
- Add, reheap
- Remove root, swap rightmost child, reheap
(9)
Data Structures
Hash tables
• Goal constant time access to keyed value
• Calculate index given key
• Open Addressing vs chaining
(10)
Recursion
Problem solving technique
if can solve problem
else solve simpler problem and combine
Data structure definition
• Linked lists, trees
Java Activation Stack
(11)
Sorting Algorithms
Quadratic
• Implementation using an array
• Selection
- Best O(n2), Ave O(n2), Worst O(n2)
• Bubble
- Best O(n), Ave O(n2), Worst O(n2)
• Insertion
- Best O(n), Ave O(n2), Worst O(n2)
(12)
Sorting Algorithms
n log n
• Merge
- Recursive, split then merge
- O(n log n), O(n log n), O(n log n)
• Heap
- Insert to heap then remove
- O(n log n), O(n log n), O(n log n)
(13)
• Quick
- Recursive, Pick pivot then swap
- O(n log n), O(n log n), O(n2)