Algorithms, Computability & Complexity

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 (instructional or practical) particular examples

• Search
  • Sequential search
  • Binary search
  • Hash-based retrieval

• Hashing
  • Hash tables
  • collision resolution techniques
    • chaining
    • probing
    • clustering
  • Hash functions
    • collision-avoidance techniques

• Sorting
  • Quadratic sorting (e.g., selection and insertion sort)
  • O(n log n) sort: Quicksort
  • O(n log n) sort: Heapsort
  • O(n log n) sort: Merge sort
  • Shell sort
  • Linear time sorting: Bucket sort
  • Linear time sorting: Radix sort
• 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
  • Dijkstra’s shortest path algorithm
  • All-pairs shortest paths
  • Transitive closure (Floyd’s algorithm)
  • Minimum spanning tree: Prim’s algorithms
  • Minimum spanning tree: Kruskal’s algorithms
  • 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

^^^ Consider http://www.esecurity.ch/Books/cryptography.html for expansion of this section

• 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 (of e.g., VLSI)
• Scheduling

Advanced Data Structures

• Balanced Binary trees (e.g., Red-black)
• Threaded Binary Trees
• Tries
• Fibbonacci Heaps
• Binomial Heaps
• Union-find data structure
  • Disjoint-sets data structure
• Splay Trees
• B-Trees
• Other

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
• RAM model
• Lambda calculus
• Partial recursive functions
• Other models of computable functions
  • RAM model
  • Lambda calculus
  • Partial recursive functions
• Advanced computability theory
• Chomsky hierarchy
• The Church-Turing thesis