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(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
	
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, ...