Skip to topic | Skip to bottom
Home
Main
Main.AlgorithmsComplexityr1.10 - 27 Sep 2007 - 15:28 - Main.novatopic end

Start of topic | Skip to actions

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

to top

You are here: Main > VillanovaWikiPages > OntologyProject > AlgorithmsComplexity

to top

Copyright © 1999-2009 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback