CSC 427: Data Structures and Algorithm Analysis
Fall 2010
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
Stack class, Queue interface
inheritance, polymorphism
Data Structures
Java Collections and list implementations
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
Sets & Maps
Set interface (extends Collection)
TreeSet: O(log N) add/remove/search
HashSet: O(1) add/remove/search expected*, O(N) worst case
Map interface
TreeMap: O(log N) add/remove/search
HashMap: O(1) add/remove/search expected*, O(N) worst case
extending data structures via inheritance
List --> ArrayList --> SortedArrayList
Algorithm Design and Analysis
big-Oh notation
intuitive definition, formal definition
rate-of-growth analysis
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(N2) worst/average case, O(N) best case
selection sort: O(N2) worst/average/best case
merge sort: O(N log N) worst/average/best case
quick sort: O(N log N) average/best case, O(N2) 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
brute force algorithms
examples: league standings, enigma
exhaustive search: musical themes, string matching
generate & test: N-queens, Traveling Salesman, Knapsack