Skip to topic | Skip to bottom
Home
Main
Main.AlgorithmsComplexityr1.11 - 29 Jul 2009 - 17:00 - Main.novatopic end

Start of topic | Skip to actions

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

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