ALGORITHMS AND THEORY

Algorithms

• Complexity analysis
  • Asymptotic analysis
    • Average case complexity bound
    • Asymptotic analysis: worst case complexity bounds
  • Identifying differences among best, average, and worst case behaviors
  • Big O
  • Big Omega
  • Big Theta
  • Little o asymptotic notation
  • Little omega asymptotic notation
  • Empirical measurements of performance
    • Profiling programs
  • Time and space tradeoffs in algorithms
  • Recurrrence relations
  • Amortized analysis
  • Other advanced algorithmic analysis
• Algorithmic Design strategies
  • Brute-force algorithms
  • Greedy algorithms
  • Divide-and-conquer
  • Backtracking
  • Branch-and-bound
  • Dynamic programming
• Algorithms for different computational environments
  • Distributed algorithms
    • Consensus and election
    • Termination detection
    • Fault tolerance
    • Stabilization
  • Algorithms for parallel architectures
    • PRAM model
    • Exclusive versus concurrent reads and writes
    • Pointer jumping
    • Brent’s theorem and work efficiency
    • Online and offline algorithms
  • Quantum computing algorithms
• Methods with different notions of success
  • Approximation algorithms
  • Randomized algorithms
  • Heuristics
• Algorithms: Important (ISAructional or practical) particular examples
  • Search
    • Sequential search
    • Binary search
    • Interpolation search
    • Jump Search
    • Hash-based retrieval

• • Hashing
    • Hash tables
    • Open Hashing
    • Bucket Hashing
    • collision resolution techniques
      • chaining
      • probing
      • clustering
    • Hash functions
      • collision-avoidance techniques
  • Sorting
    • Comparison-based sorts
      • Quadratic sorts (eg.selection sort,insertion sort)
      • n log n sort
        • Quicksort
        • Heapsort
        • Merge sort
      • Shell sort * Non-Comparison-based sorts
      • Bucket sort
      • Radix sort * Sorting Networks * Graph and tree algorithms
    • Depth-first Binary Tree traversals (pre, in, post order)
    • Breadth-first Tree traversal (level order)
    • Depth-first search of graphs
    • Breadth-first search of graphs
    • Single-source shortest paths
    • All-pairs shortest paths
      • Transitive closure
        • Floyd’s algorithm
        • Dijkstras alogrithm
    • Minimum-cost spanning tree
      • Kruskal’s algorithm
      • Prim's algorithm
    • Topological sort
  • Pattern matching and string/text algorithms
  • Numerical (floating-point numbers) algorithms
    • Matrix algorithms
    • Transforms (e.g., FFT)
  • Medians and order statistics
  • Network Flow
  • Combinatorial optimization
  • Pseudo random number generation
  • Computational Number Theory
  • Cryptographic algorithms
    • Unkeyed cryptography
      • Parabolic encryption
    • Symmetric cryptography
      • Secret-key encryption
    • Asymmetric cryptography
      • Public-key encryption
    • Steganography
  • Geometric algorithms
    • Line segments: properties, intersections
    • Convex hull finding algorithms
    • Other
  • Routing and layout
  • Scheduling
• Advanced Data Structures
  • Search Trees
    • Binary search trees
      • AVL Trees
      • Splay Trees
  • Red-black trees
  • Threaded Binary Trees
  • Tries
  • Fibonacci Heaps
  • Binomial Heaps
  • Union-find data structure
  • B-Trees
    • 2-3 Trees
    • 2-3-4 Trees
    • B+ Trees
    • B* Trees
  • Spatial Data Structures
    • R-Trees
    • Region representations
    • Point representations
    • Rectangle Representations
    • Line representations
  • Other

Theory

• Automata and formal language theory
  • Languages, strings, alphabets
  • DFAs (Deterministic Finite Automata)
  • NFAs (Nondeterministic Finite Automata)
  • Regular expressions
  • Equivalence of DFA, NFA, and Regular Expressions
  • Context-free grammars
  • Push-down automata
  • Equivalence of CFGs and PDAs
  • Pumping Lemma
  • Cellular automata
  • Other automata theory
• Complexity Theory
  • Tractable vs. intractable problems
  • Theory of P, NP, etc.
    • Complexity Class P
    • Complexity Class NP
    • NP Completeness
    • The P =? NP problem
    • Famous NP-complete problems (e.g., 3SAT, Traveling Salesperson, Vertex Cover, Integer Programming)
  • Other complexity classes
  • Reductions
    • Poly-time reductions
    • Log space reductions
  • Complete problems for a complexity class
  • Other time-based complexity classses
  • Space complexity classes
  • Relations among complexity classes
  • Complexity classes based on mode of computing
    • Alternating
    • Randomized
    • Online
    • Parallel
    • Interactive
  • Circuits and circuit complexity
• Computability Theory
  • Notion of decision problem
  • Recursive (decidable) problems
  • Recursively enumerable problems
  • Undecidable problems
  • Halting problem
  • Turing machines
    • Universal Turing Machine
    • Nondeterministic Turing machines
  • Other models of computable functions
    • RAM model
    • Lambda calculus
    • Partial recursive functions
  • Advanced computability theory
  • Chomsky hierarchy
  • The Church-Turing thesis