Key Ideas of CS 483
  1. Abstraction

    • Abstraction and Organization overcome Complexity
    • Objects
    • Subroutines
    • Diagrams
    • Pseudocode
    • Generic Algorithms
  1. Repertoire

    • Some new Algorithms ... and Data Structures
    • Data Structures keep results handy for algorithms
    • Algorithms maintain data structures
  1. Design

    • Extend and combine to solve real problems
    • Divide, conquer and combine
    • Greedy algorithms
    • Dynamic programming
  1. Verification

    • Maintain data structure properties
    • Loop invariants
    • Mathematical induction
  1. Analysis

    • Time, space, processors
    • Input parameters
    • Asymptotic function growth
    • Polynomial degree and beyond
  1. Analysis Techniques

    • Loop nesting
    • Tree height and balance
    • Combinatorics
    • Recurrences
  1. Problem Complexity

    • Unsolvable and intractable problems
    • Best possible result
    • Approximation