Algorithms and ComplexityThis first part presents chapters on models of computation, complexity theory, data structures, and efficient computation in many recognized sub-disciplines of Theoretical Computer Science. |
Contents
| 67 | |
CHAPTER 3 MachineIndependent Complexity Theory | 163 |
CHAPTER 4 Kolmogorov Complexity and its Applications | 187 |
CHAPTER 5 Algorithms for Finding Patterns in Strings | 255 |
CHAPTER 6 Data Structures | 301 |
CHAPTER 7 Computational Geometry | 343 |
CHAPTER 8 Algorithmic Motion Planning in Robotics | 391 |
CHAPTER 9 AverageCase Analysis of Algorithms and Data Structures | 431 |
CHAPTER 12 Algorithms in Number Theory | 673 |
CHAPTER 13 Cryptography | 717 |
CHAPTER 14 The Complexity of Finite Functions | 757 |
CHAPTER 15 Communication Networks | 805 |
CHAPTER 16 VLSI Theory | 835 |
CHAPTER 17 Parallel Algorithmsfor SharedMemory Machines | 869 |
CHAPTER 18 General Purpose Parallel Architectures | 943 |
| 973 | |
Common terms and phrases
ACM Symp algebraic algorithm applications asymptotic augmenting path binary bits Boolean Boolean circuit combinatorial Computer Science configuration construction convex cycle data structures decision problems defined definition denote depth deterministic edge efficient elements example exponential EXPTIME factor fan-in finite Foundations of Computer function given graph G hash IEEE Symp integer isomorphism Kolmogorov complexity language LEMMA length linear logarithmic lower bound machine model matching Math matrix maximum flow method minimum motion planning multiplication nodes nondeterministic Notes in Computer NP-complete O(log O(n log obtained operations optimal oracle output parallel permutation planar planar graphs polygon polynomial polynomial-time PRAM priority queue probabilistic Proc processors proof proved PSPACE query random recursive regular expression result search trees Section sequence SIAM simulation solved sorting sorting networks space Subsection System Sci tape TARJAN techniques theorem Theory of Computing transitive closure Turing machine VLSI Voronoi diagram