###
CSC 321: Data Structures

Fall 2012

Midterm Review

Java review
class, object, fields, methods, private vs. public, parameters
variables, primitive vs. objects, expressions, if, if-else, while, for
object-oriented design: cohesion, coupling
String, Math, arrays, ArrayList, generics
interfaces, List, LinkedList, iterators
searching and sorting, algorithm efficiency, recursion
interfaces, inheritance, polymorphism
GUI building
Data Structures
Collection interface, many useful static methods in Collections
List interface (extends Collection)
ArrayList (implements List): underlying array representation
O(1) add/remove at end, O(N) add/remove from beginning/middle
O(1) access, O(N) search
LinkedList (implements List): underlying doubly-linked list representation
O(1) add/remove at beginning/end, O(N) add/remove from middle
O(1) add/remove if have access to location, O(N) access/search
iterators
Iterator interface: hasNext, next, remove
ListIterator interface: hasPrevious, previous, add, set
Stack class (extends Collectio, implements List)
FILO/LIFO list
operations: push, pop, peek, empty
Queue interface (extends Collection)
FIFO/LILO list
operations: add, remove, peek, empty
implemented by LinkedList class
linked structures
nodes, references
singly-linked lists, next references, front and/or back references
doubly-linked lists, previous & next references, front & back
dummy nodes
Algorithm Analysis
best vs. average vs. worst case analysis
big-Oh notation
intuitive definition, formal definition
rate-of-growth analysis
big-Omega, big-Theta
searching
sequential search: O(N) worst/average case, O(1) best case
binary search: O(log N) worst/average case, O(1) best case
sorting
insertion sort: O(N^{2}) worst/average case, O(N) best case
selection sort: O(N^{2}) worst/average/best case
merge sort: O(N log N) worst/average/best case
quick sort: O(N log N) average/best case, O(N^{2}) worst case
specialized sorts
if limited range of values, sort via frequency list: O(range * N)
if can compare by digit/char, radix sort: O(maxLength * N)
recursion
base case(s), recursive case(s)
analysis via recurrence relation
counting techniques
mappings, sequences
rules: bijection, product, sum, generalized product, division
inclusion/exclusion, pigeonhole principle