| 
|
Topic: algorithmic complexity analysis
topics >
computer science >
automatic selection of algorithm for abstract data type
Topic:
computational geometry
Topic:
handling complexity
Topic:
Kolmorgorov and algorithmic complexity
Topic:
parallel algorithms
Topic:
probabilistic and randomized algorithms
Topic:
programming as mathematics
Subtopic: big-Oh notation
Quote: users and programs make assumptions about operator complexity; e.g., push and pop should be amortized constant time, string copy should be linear [»dehnJC4_1998]
Subtopic: NP-complete
Quote: use big-Oh, Omega and Theta notations for complexity analysis; first appearance in 1894 [»knutDE4_1976]
Subtopic: 3-SAT
Quote: with NP-complete problems, one knows how to solve the problem but does not have enough time [»rabiMO8_1974] Note: perhaps P != NP is true but unproveable [»cbb_2000, OK]
Subtopic: survey
Note: how many truth tables are 3-SAT problems? Must they include incompressible functions [»cbb_2000, OK]
Subtopic: worst-case complexity
Quote: survey of cryptology and computational complexity; cryptographic protocols, one-way functions, public-key, interactive proof systems, and zero-knowledge protocols [»rothJ12_2002]
Subtopic: history
Quote: the maximal series-parallel circuits are sum_over_n of X_k and its inverse; O(2^n) elements [»shanCE6_1938]
Subtopic: limitations of complexity analysis
Quote: what is the fastest method to calculate a result with the analytical engine?
Quote: for search, speed and character comparisons may not be related; e.g., diagram search is 386x better by comparisons and 240x to 13x better by speed [»fenwP7_2001a] Quote: simple algorithms often faster because easily optimized and good cache performance
Topic: automatic selection of algorithm for abstract data type (7 items)
Topic: computational geometry (20 items)
Topic: handling complexity (60 items)
Topic: Kolmorgorov and algorithmic complexity (10 items)
Topic: parallel algorithms (15 items)
Topic: probabilistic and randomized algorithms (11 items)
Topic: programming as mathematics
(27 items)