###
CSC 427: Data Structures and Algorithm Analysis

Fall 2008

Test 1 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
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(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
inheritance and efficiency
derived classes
extending a class vs. implementing an interface
overriding methods, calling parent methods/constructors with super
polymorphism
List --> ArrayList --> SortedArrayList
divide-and-conquer algorithms
examples: merge sort, quick sort, Euclid's gcd, ...