Topic: 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: importance of complexity analysis
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: bigOh notation
Quote: use bigOh, Omega and Theta notations for complexity analysis; first appearance in 1894 [»knutDE4_1976]
 Subtopic: NPcomplete
Quote: with NPcomplete 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: 3SAT
Note: how many truth tables are 3SAT problems? Must they include incompressible functions [»cbb_2000, OK]
 Subtopic: survey
Quote: survey of cryptology and computational complexity; cryptographic protocols, oneway functions, publickey, interactive proof systems, and zeroknowledge protocols [»rothJ12_2002]
 Subtopic: worstcase complexity
Quote: the maximal seriesparallel circuits are sum_over_n of X_k and its inverse; O(2^n) elements [»shanCE6_1938]
 Subtopic: history
Quote: what is the fastest method to calculate a result with the analytical engine?
 Subtopic: limitations of complexity analysis
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

Related Topics
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)
