Skip to topic
|
Skip to bottom
Jump:
Main
TWiki.org
Welcome
Register
Main Web
Main Web Home
Users
Groups
Offices
Changes
Changes detailed
Topic list
Search
TWiki Webs
Main
Sandbox
TWiki
Create
personal sidebar
Edit
Attach
Printable
Main.AlgorithmsComplexity
r1.11 - 29 Jul 2009 - 17:00 - Main.nova
topic 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
End of topic
Skip to action links
|
Back to top
Edit
|
Attach image or document
|
Printable version
|
Raw text
|
More topic actions
Revisions: | r1.11 |
>
|
r1.10
|
>
|
r1.9
|
Total page history
|
Backlinks
You are here:
Main
>
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