Design and Analysis of Algorithms

Table of contents

1. Cover
2. Title page
3. Brief Contents
4. Contents
5. Dedication
6. Preface
7. Part 1. Algorithm Design
   1. Chapter 1. Introduction
      1. 1.1 Basic Concerns
      2. 1.2 Relationship between Algorithms and other aspects of Software
      3. 1.3 The Evolution of Algorithm
      4. Summary
      5. Key Terms
      6. Exercises
      7. Web Resources
   2. Chapter 2. Problem Solving with a Computer
      1. 2.1 Introduction
      2. 2.2 Solving a Problem with a Computer
         1. 2.2.1 Statement of the problem or problem definition
         2. 2.2.2 Development of a model
         3. 2.2.3 Design of the algorithm
         4. 2.2.4 Checking the correctness of the algorithm
         5. 2.2.5 Implementation in some programming language
         6. 2.2.6 Analyze and study the complexity of the algorithm
         7. 2.2.7 Program testing—debugging and profiling
         8. 2.2.8 Documentation preparation
      3. 2.3 Some More Examples
         1. 2.3.1 Finding the square root of a number
         2. 2.3.2 Smallest divisor of an integer number
         3. 2.3.3 Generation of prime numbers
         4. 2.3.4 Generation of pseudo-random numbers (PN)
      4. 2.4 Problem Solving in General
         1. 2.4.1 The STAIR steps for solving problems
         2. 2.4.2 Problem solving as applied to numerical algorithms
         3. 2.4.3 Reduction to known problems
         4. 2.4.4 Strategy if we are stuck
      5. Summary
      6. Key Terms
      7. Exercises
      8. Web Resources
   3. Chapter 3. Top-Down Design
      1. 3.1 Introduction
      2. 3.2 Structured Programming
      3. 3.3 Control Constructs
         1. 3.3.1 If-Then-Else
         2. 3.3.2 For-Do
         3. 3.3.3 Case
         4. 3.3.4 Repeat-Until
         5. 3.3.5 While-Do
         6. 3.3.6 Goto and ExitLoop
      4. 3.4 Procedures and Functions
      5. 3.5 Recursion
         1. 3.5.1 Order of execution of statements in a recursive function
      6. Summary
      7. Key Terms
      8. Exercises
      9. Web Resources
   4. Chapter 4. Iterative Algorithm Design Issues
      1. 4.1 Introduction
      2. 4.2 Use of Loops
      3. 4.3 Efficiency of Algorithms
         1. 4.3.1 Removing redundant computations outside loops
         2. 4.3.2 Referencing of array elements
         3. 4.3.3 Inefficiency due to late termination
         4. 4.3.4 Early detection of desired output conditions
      4. 4.4 Estimating and Specifying Execution Times
         1. 4.4.1 Justification for the use of problem size as a measure
         2. 4.4.2 Computational cost as a function of problem size for a range of computational complexities
      5. 4.5 Order Notation
         1. 4.5.1 Big-oh notation
         2. 4.5.2 Theta notation
         3. 4.5.3 Omega notation
         4. 4.5.4 Small-oh notation
         5. 4.5.5 ω notation
         6. 4.5.6 Measuring the execution times
         7. 4.5.7 Other trade-offs
      6. 4.6 Algorithm Strategies
      7. Summary
      8. Key Terms
      9. Exercises
      10. Web Resources
   5. Chapter 5. Computation Models and Design by Refinement
      1. 5.1 Introduction
      2. 5.2 Functional Model
         1. 5.2.1 Features of functional model
         2. 5.2.2 Recursive processes
         3. 5.2.3 Analysis of correctness and efficiency
         4. 5.2.4 More examples of recursive algorithms
         5. 5.2.5 Scope rules
         6. 5.2.6 Tail-recursion and iterative processes
         7. 5.2.7 Correctness of an iterative process
         8. 5.2.8 More examples of iterative processes
      3. 5.3 Imperative Model
         1. 5.3.1 The primitives for the imperative model
         2. 5.3.2 Specifications and prototyping
         3. 5.3.3 Examples of step wise refinement
      4. Summary
      5. Key Terms
      6. Exercises
      7. Web Resources
   6. Chapter 6. Proof Rules—Basics
      1. 6.1 Introduction
      2. 6.2 Computer Model for Program Execution
      3. 6.3 Assertions at Input and Output of Blocks
         1. 6.3.1 Symbolic execution
      4. 6.4 Proof Rules
         1. 6.4.1 Compound statements
         2. 6.4.2 Conditional statements
         3. 6.4.3 Case statements
         4. 6.4.4 Repetitive statements
         5. 6.4.5 Repeat-Until statement
         6. 6.4.6 Example: The division algorithm
      5. 6.5 Correct Termination of Algorithms
      6. 6.6 Proof Rules for more Advanced Constructs
         1. 6.6.1 For loops
         2. 6.6.2 GoTo and ExitLoop
         3. 6.6.3 Program transformation
         4. 6.6.4 Functions and procedures
         5. 6.6.5 Recursive functions
      7. Summary
      8. Key Terms
      9. Exercises
      10. Web Resources
   7. Chapter 7. Design by Proof Rules
      1. 7.1 A Fresh Look at Proof Rules
         1. 7.1.1 Referring to previous values of variables
         2. 7.1.2 Proof rules
      2. 7.2 Designing Correct Programs
         1. 7.2.1 The interface specification
         2. 7.2.2 Applying the rules to deduce the program statement types
         3. 7.2.3 Design example
      3. 7.3 Design of a Loop
         1. 7.3.1 Loop termination
      4. 7.4 A Simple Design Procedure for Loops based on Proof-Rules
         1. 7.4.1 Example 1: Linear search
         2. 7.4.2 Example 2: Linear search without assurance
         3. 7.4.3 Example 3: Searching a 2-D array
      5. 7.5 Example: Selection Sort
      6. 7.6 Example: Partition ()
      7. Summary
      8. Key Terms
      9. Exercises
      10. Web Resources
   8. Chapter 8. Design using Recursion
      1. 8.1 Introduction
      2. 8.2 Execution Trace
         1. 8.2.1 Regular expressions
         2. 8.2.2 An interesting recursive function
      3. 8.3 Another Look at Iteration and Recursion
      4. Summary
      5. Key Terms
      6. Exercises
      7. Web Resources
   9. Chapter 9. Abstract Algorithms-1-Divide-and-Conquer
      1. 9.1 Introduction
      2. 9.2 A Multiplication Algorithm
         1. 9.2.1 Analysis of the multiplication algorithm
      3. 9.3 Application to Graphics Algorithms
         1. 9.3.1 Introduction to triangulation
         2. 9.3.2 Convex hulls
      4. 9.4 Where D & C Fails
         1. 9.4.1 Characteristics of problems for which D & C is unsuitable
      5. 9.5 Timing Analysis
      6. Summary
      7. Key Terms
      8. Exercises
      9. Web Resources
   10. Chapter 10. Abstract Algorithms 2—Greedy Methods
       1. 10.1 Introduction
       2. 10.2 Example—Knapsack Problem
       3. 10.3 Job Sequencing with Deadlines
       4. 10.4 Example—Minimum Spanning Trees
          1. 10.4.1 Prim’s algorithm
          2. 10.4.2 Kruskal’s algorithm
          3. 10.4.3 1st Version—Kruskal.c
          4. 10.4.4 Union-find data-structure
          5. 10.4.5 Tree-based disjoint sets and the quick-union algorithm
          6. 10.4.6 Implementing quick-union with an array
          7. 10.4.7 Complexity analysis of quick-union
          8. 10.4.8 Using union-find in Kruskal algorithm
          9. 10.4.9 Matroids
          10. 10.4.10 Correctness of Kruskal’s algorithm
       5. 10.5 Example [Shortest Path]
          1. 10.5.1 Dijkstra’s shortest path algorithm
       6. Summary
       7. Key Terms
       8. Exercises
       9. Web Resources
   11. Chapter 11. Abstract Algorithms 3—Dynamic Programming
       1. 11.1 Introduction
       2. 11.2 Example—Multistage Graphs
       3. 11.3 Example—Traveling Salesman (TS)
       4. 11.4 Example—Matrix Multiplication
          1. 11.4.1 Brute force solution—try all possible parenthesisations
          2. 11.4.2 Dynamic programming
       5. 11.5 Example—Longest Common Sub-sequence (LCS)
          1. 11.5.1 Brute force method
          2. 11.5.2 Dynamic programming
       6. 11.6 Example—Optimal Polygon Triangulation
          1. 11.6.1 Problem
       7. 11.7 Single Source Shortest Paths
          1. 11.7.1 Shortest paths problem
          2. 11.7.2 Shortest paths tree (single source)
          3. 11.7.3 All-pairs shortest paths
       8. 11.8 Maximum Flow Problems
          1. 11.8.1 Flow networks
          2. 11.8.2 Maximum-flow problem
          3. 11.8.3 Analysis of Ford-Fulkerson algorithm
       9. 11.9 Conclusion
       10. Summary
       11. Key Terms
       12. Exercises
       13. Web Resources
   12. Chapter 12. Abstract Algorithms 4—Backtracking
       1. 12.1 Combinatorial Search
       2. 12.2 Search and Traversal
          1. 12.2.1 Breadth First Search (BFS)
          2. 12.2.2 Depth First Search (DFS)
       3. 12.3 The Backtracking Strategy
          1. 12.3.1 Example 1: 8-Queens problem
       4. 12.4 Backtracking Framework
          1. 12.4.1 Efficiency of backtracking
          2. 12.4.2 Example 2: M-colouring problem
          3. 12.4.3 Example 3: Hamiltonian circuits
       5. 12.5 Some Typical State Spaces
          1. 12.5.1 Constructing all subsets
          2. 12.5.2 Constructing all permutations
          3. 12.5.3 Constructing all paths in a graph
          4. 12.5.4 Bandwidth minimization
          5. 12.5.5 Covering chess boards
          6. 12.5.6 Convex Hull (Graham’s scan)
       6. Summary
       7. Key Terms
       8. Exercises
       9. Web Resources
   13. Chapter 13. Natural Algorithms—GA, SA, ANN, TS
       1. 13.1 Introduction
       2. 13.2 Evolutionary Algorithms and Evolutionary Computing
       3. 13.3 Genetic Algorithms
          1. 13.3.1 An example problem
          2. 13.3.2 Observations
       4. 13.4 Simulated Annealing
          1. 13.4.1 Sample implementation
       5. 13.5 Artificial Neural Networks (ANN)
          1. 13.5.1 Analogy to the brain
          2. 13.5.2 How they work?
          3. 13.5.3 Electronic implementation of artificial neurons
          4. 13.5.4 Artificial network operations
          5. 13.5.5 Training an artificial neural network
          6. 13.5.6 F eed-forward network
          7. 13.5.7 Hopfield feedback connected neural network
          8. 13.5.8 How neural networks differ from traditional computing and expert systems
          9. 13.5.9 Artificial neural network applications
       6. 13.6 Tabu Search
          1. 13.6.1 Application domain
          2. 13.6.2 The Reactive Tabu Search (RTS)
       7. Summary
       8. Key Terms
       9. Web Resources
8. Part 2. Algorithm Analysis
   1. Chapter 14. Efficiency of Algorithms
      1. 14.1 Polynomial-Time and Non-Polynomial-Time Algorithms
      2. 14.2 Worst and Average Case Behaviour
         1. 14.2.1 Probabilistic average case analysis
      3. 14.3 Time Analysis of Algorithms
         1. 14.3.1 Example —Matrix multiplication
         2. 14.3.2 More timing analysis
      4. 14.4 Efficiency of Recursion
      5. 14.5 Complexity
         1. 14.5.1 The notion of complexity
         2. 14.5.2 Profiling
         3. 14.5.3 Suppressing multiplicative constants
         4. 14.5.4 Counting dominant operations
         5. 14.5.5 Growth-Rate
         6. 14.5.6 Upper bounds
         7. 14.5.7 Asymptotic growth-rate
         8. 14.5.8 The ‘O’ notation
         9. 14.5.9 Discussion
         10. 14.5.10 Simplified definition of ‘O’
         11. 14.5.11 ‘O’ notation rules
         12. 14.5.12 Analyzing growth of exotic functions
         13. 14.5.13 Derivative rule
         14. 14.5.14 Order-of-magnitude comparisons
         15. 14.5.15 Doubling comparisons
         16. 14.5.16 Estimating complexity experimentally
         17. 14.5.17 Experimental comparison of sorting procedures
      6. Summary
      7. Key Terms
      8. Exercises
      9. Web Resources
   2. Chapter 15. Examples of Complexity Calculation
      1. 15.1 Examples from the Sorting World
         1. 15.1.1 Bucket sort
         2. 15.1.2 Radix sort
         3. 15.1.3 Simple insertion sort
         4. 15.1.4 Quick sort
         5. 15.1.5 Heap sort—using a Tree to sort
         6. 15.1.6 Merge sort
      2. 15.2 Summary of Complexity and Characteristics of Sorting Algorithms
      3. 15.3 Complexity of Set Operations and Mappings
         1. 15.3.1 Sets implementation using an unordered array
         2. 15.3.2 Binary search principle
         3. 15.3.3 Binary search trees
         4. 15.3.4 Bit vectors
         5. 15.3.5 Analysis of hashing
         6. 15.3.6 The trie principle
         7. 15.3.7 Sets vs. bags and mappings
      4. 15.4 Amortized Analysis
         1. 15.4.1 Potential functions
         2. 15.4.2 Example—binary, binomial and fibonacci heaps
         3. 15.4.3 Binomial heap
         4. 15.4.4 Fibonacci heap
      5. 15.5 Dijkstra’s Shortest-Path Algorithm
         1. 15.5.1 Analysis
      6. 15.6 Splay Trees
         1. 15.6.1 Basics of splay trees
         2. 15.6.2 Splay operation
         3. 15.6.3 Amortized timing analysis
      7. Summary
      8. Key Terms
      9. Exercises
      10. Web Resources
   3. Chapter 16. Time-Space Trade-Off
      1. 16.1 Introduction
         1. 16.1.1 An example of time-space trade-off
      2. 16.2 A Quick Review of Complexity
      3. 16.3 Time-Space Trade-Off
         1. 16.3.1 Some simple examples
      4. 16.4 Time-Space Trade-Off in Algorithm Research
      5. 16.5 Case Study—Perrin Numbers
         1. 16.5.1 Perrin numbers
         2. 16.5.2 First try—straight-forward implementation
         3. 16.5.3 Second try—dynamic programming
         4. 16.5.4 Third try—reduction and divide & conquer
         5. 16.5.5 The final results
      6. Summary
      7. Key Terms
      8. Exercises
      9. Web Resources
   4. Chapter 17. Tractable and Non-Tractable Problems
      1. 17.1 Introduction
      2. 17.2 Upper and Lower Bounds
         1. 17.2.1 Algorithmic gap
      3. 17.3 Efficiency and Tractability
         1. 17.3.1 Problem description
         2. 17.3.2 A quick and operating definition of NP-complete problems
         3. 17.3.3 Some known NP-complete problems
         4. 17.3.4 What is a certificate?
         5. 17.3.5 Non-deterministic algorithms
      4. 17.4 NP-Completeness
      5. 17.5 Polynomial Time Reductions
      6. 17.6 Problem Classes P, NP, and Others
      7. 17.7 Bounded Halting is in NPC
      8. 17.8 Cook’s Theorem
         1. 17.8.1 An example reduction to SAT
         2. 17.8.2 Examples of problems in different classes
      9. 17.9 Is P = NP?
         1. 17.9.1 NP-completeness
         2. 17.9.2 How to prove NP-completeness in practice
         3. 17.9.3 Primality test
      10. 17.10 Approximate Solutions to NPC Problems
      11. 17.11 Provably Intractable Problems
          1. 17.11.1 Example—an intractable SAT
      12. 17.12 Even Harder Problems
      13. 17.13 Unreasonable Requirements of Memory
      14. 17.14 Complexity Classes and Intractability
      15. 17.15 Non-Computability and Undecidability
      16. 17.16 Algorithmic Program Verification
          1. 17.16.1 Halting Problem (HP)
      17. 17.17 Partially and Highly Undecidable Problems
      18. 17.18 The Four Levels of Algorithmic Behaviour
      19. Summary
      20. Key Terms
      21. Web Resources
   5. Chapter 18. Some NP and NP-Complete Problems
      1. 18.1 Introduction
         1. 18.1.1 NP-hardness
         2. 18.1.2 NP-completeness
         3. 18.1.3 Consequences of being in P
         4. 18.1.4 Reduction source problems
      2. 18.2 Turing Machine (TM)
         1. 18.2.1 Relation between problems and languages
         2. 18.2.2 Decision problems and languages
      3. 18.3 Reductions
         1. 18.3.1 Definition of reductions
         2. 18.3.2 Reduction in P
         3. 18.3.3 Transitivity of reductions
         4. 18.3.4 NP-completeness to NP = P
         5. 18.3.5 Circuit satisfiability problem
         6. 18.3.6 Reductions in NPC
         7. 18.3.7 Steps for proving NP-completeness
      4. 18.4 Reductions for Some Known Problems
         1. 18.4.1 Propositional formulae
         2. 18.4.2 SAT problem
         3. 18.4.3 3-Conjunctive normal form (3-CNF)-SAT problem
         4. 18.4.4 Cliques of a graph
         5. 18.4.5 Vertex Cover (VC)
         6. 18.4.6 Hamiltonian Cycle (HC)
         7. 18.4.7 Traveling Salesman Problem (TSP)
         8. 18.4.8 Independent set
      5. 18.5 Certificates and Verification
      6. Summary
      7. Key Terms
      8. Exercises
      9. Web Resources
   6. Chapter 19. Randomized and Approximate Algorithms
      1. 19.1 Introduction
      2. 19.2 Randomized Algorithms
         1. 19.2.1 Reasons for using randomized algorithms
         2. 19.2.2 Background—Review of probability theory
         3. 19.2.3 Examples
         4. 19.2.4 Generation of large prime numbers
      3. 19.3 Randomized Complexity Classes
         1. 19.3.1 RP: Randomized polynomial time
         2. 19.3.2 co-RP: Complement of RP
         3. 19.3.3 ZPP: Zero-error probabilistic polynomial time
         4. 19.3.4 BPP: Bounded-error probabilistic polynomial time
      4. 19.4 Approximate Algorithms
         1. 19.4.1 NP-hard optimization problems
         2. 19.4.2 Examples—approximation algorithms
         3. 19.4.3 Analysis of approximation algorithms
         4. 19.4.4 Traveling salesman problem
         5. 19.4.5 Colouring 3-colourable graphs
         6. 19.4.6 Decision problems
         7. 19.4.7 Approximation algorithms
         8. 19.4.8 Approximation of TSP
      5. Summary
      6. Key Terms
      7. Exercises
      8. Web Resources
   7. Chapter 20. Formal Specifications—1 Model Oriented
      1. 20.1 Formal Specifications
         1. 20.1.1 A first specification language
         2. 20.1.2 What is a software specification?
         3. 20.1.3 What is a formal specification?
         4. 20.1.4 An apparent disadvantage of FSL
      2. 20.2 Introduction to VDM
         1. 20.2.1 The implicit specification of operations
         2. 20.2.2 Examples of implicit specifications
         3. 20.2.3 The logical condition
         4. 20.2.4 Reasoning with pre- and post-conditions
         5. 20.2.5 Introduction to VDM data types
         6. 20.2.6 The primitive types
         7. 20.2.7 The set type
         8. 20.2.8 Implicit definition of sets
         9. 20.2.9 Creating VDM state models
         10. 20.2.10 Composites
      3. 20.3 A Systematic Approach to the Construction of VDM Specifications
         1. 20.3.1 Creation of a system state
         2. 20.3.2 Construction of data type invariants
         3. 20.3.3 Modeling of the system’s operations
         4. 20.3.4 Discharging proof obligations
         5. 20.3.5 Specification refinement
         6. 20.3.6 Formal proof obligations
         7. 20.3.7 Recapitulation
      4. 20.4 The Sequence and Map Types
         1. 20.4.1 The sequence data type
         2. 20.4.2 The map data type
         3. 20.4.3 A small example
      5. Summary
      6. Key Terms
      7. Exercises
      8. Web Resources
   8. Chapter 21. Formal Specifications—2 Algebraic
      1. 21.1 Introduction
         1. 21.1.1 Specification of abstract data types
         2. 21.1.2 Algebraic specification of abstract data types
         3. 21.1.3 An algebraic specification language
      2. 21.2 Algebraic Specification of an Unbounded Stack
         1. 21.2.1 Comparison with VDM
         2. 21.2.2 Completeness
         3. 21.2.3 Examples of evaluations
         4. 21.2.4 Axioms and term rewriting
         5. 21.2.5 Pattern matching and unification
      3. Summary
      4. Key Terms
      5. Exercises
      6. Web Resources
9. Appendix A. Essential Mathematical Background
   1. A.1 What is Discrete Mathematics?
   2. A.2 Formal Logic: A Language for Mathematics
      1. A.2.1 Assertions and propositions
      2. A.2.2 Logical connectives
      3. A.2.3 Tautologies, contradictions, and contingencies
      4. A.2.4 Proof techniques
      5. A.2.5 Predicates
      6. A.2.6 Quantifiers
      7. A.2.7 Free and bound variables
      8. A.2.8 Implications and equivalences
      9. A.2.9 Classification of assertions in predicate logic
      10. A.2.10 Inference rules in predicate logic
   3. A.3 Sets
      1. A.3.1 Notations for sets
      2. A.3.2 Relationships between sets
      3. A.3.3 Set operations
      4. A.3.4 Properties of sets
      5. A.3.5 Functions
      6. A.3.6 Operations on functions
      7. A.3.7 Classification of total functions
      8. A.3.8 Cardinality of a set
      9. A.3.9 Sequences and series
   4. A.4 Asymptotic Notations
   5. A.5 Number Theory
      1. A.5.1 LCM and GCD
      2. A.5.2 Primes and factorization
      3. A.5.3 Congruences and modular arithmetic
      4. A.5.4 Applications of mathematics in computer science
   6. A.6 Formal Languages
      1. A.6.1 Strings
      2. A.6.2 Binary operation on strings
      3. A.6.3 Relationships between strings
      4. A.6.4 Inductive definitions
      5. A.6.5 Languages
      6. A.6.6 Binary operation on languages
      7. A.6.7 Power X1 of a language X
      8. A.6.8 Closure of a language
   7. A.7 Proof by Induction
      1. A.7.1 First principle of mathematical induction
      2. A.7.2 Second principle of mathematical induction
   8. A.8 Introduction to combinatorics
      1. A.8.1 Principles of combinatorics
      2. A.8.2 Choosing elements from sets
      3. A.8.3 Permutations
      4. A.8.4 Multiset (or bag)
      5. A.8.5 Permutations in circular order
      6. A.8.6 Samples
      7. A.8.7 Combinations
      8. A.8.8 Selections
      9. A.8.9 Pigeonhole principle or Dirichlet Drawer principle
   9. A.9 Random Variables
      1. A.9.1 Discrete distribution functions
      2. A.9.2 Expected values
      3. A.9.3 Variance and standard deviation
      4. A.9.4 Central limit theorem
   10. A.10 Relations
       1. A.10.1 Binary relations and digraphs
       2. A.10.2 Classification of binary relations
       3. A.10.3 Operations on relations
       4. A.10.4 Equivalence relations and equivalence classes
       5. A.10.5 Partitions
       6. A.10.6 Order relations
       7. A.10.7 Upper bounds and lower bounds
   11. A.11 Graph Theory
       1. A.11.1 Directed graph or digraph
       2. A.11.2 Undirected graphs
       3. A.11.3 Trees
       4. A.11.4 Matrix representations of graphs
   12. Exercises
10. Appendix B. Some Useful Mathematical Formulae
    1. B.1 Definitions
    2. B.2 Sums
    3. B.3 Identities
    4. B.4 Trees
    5. B.5 Recurrences
       1. B.5.1 Generating functions
    6. B.6 Some Constants
    7. B.7 General
    8. B.8 Trigonometry
    9. B.9 Number Theory
    10. B.10 Graph Theory
        1. B.10.1 Definitions
        2. B.10.2 Notations
    11. B.11 Value Of π
    12. B.12 Partial Fractions
    13. B.13 Calculus
        1. B.13.1 Derivatives
        2. B.13.2 Integrals
        3. B.13.3 Finite calculus
    14. B.14 Series
11. Appendix C. Overview of Essential Data Structures
    1. C.1 Introduction
    2. C.2 Primitive Data Structures
    3. C.3 Arrays and Lists
       1. C.3.1 Linked storage
       2. C.3.2 Pointers and linked allocation
       3. C.3.3 Linked linear list
       4. C.3.4 Operations on linked lists
       5. C.3.5 Circularly linked linear lists
       6. C.3.6 Doubly linked linear lists
    4. C.4 Stacks
       1. C.4.1 Operations on stacks
    5. C.5 Queues
       1. C.5.1 Circular queues
       2. C.5.2 Double ended queues
    6. C.6 Priority Queues
    7. C.7 Trees
       1. C.7.1 Operations on a binary tree
       2. C.7.2 Storage representation and manipulation
       3. C.7.3 Linked storage
       4. C.7.4 Threaded storage
    8. C.8 Binary Search Trees
       1. C.8.1 Searching
       2. C.8.2 Binary search trees
       3. C.8.3 Analysis of binary search trees
       4. C.8.4 Balanced binary trees and AVL trees
    9. C.9 Skip Lists
       1. C.9.1 Shortcuts
       2. C.9.2 Skip lists
       3. C.9.3 Implementation
    10. C.10 Hash Tables
        1. C.10.1 Hash functions
        2. C.10.2 Collision resolution
    11. C.11 Graphs
        1. C.11.1 Matrix representation
    12. C.12 Linked List-Structure
12. Appendix D. Solutions of Recurrence Relations
    1. D.1 Introduction
    2. D.2 Preliminaries
       1. D.2.1 Sequences and generating functions
       2. D.2.2 Characteristic polynomial
       3. D.2.3 Recurrence systems
       4. D.2.4 Solutions of recurrence systems
       5. D.2.5 Classification of recurrence systems
       6. D.2.6 Uniqueness of a solution to a linear recurrence system
       7. D.2.7 Principle of superposition
    3. D.3 Methods of Solution of Recurrence Relations
       1. D.3.1 Method of iteration
       2. D.3.2 Method of substitution
       3. D.3.3 Using Master Theorem
       4. D.3.4 Method of generating function
       5. D.3.5 Method of characteristic roots
       6. D.3.6 Method of undetermined coefficients
       7. D.3.7 Higher-order recurrence systems
    4. D.4 Algorithm Analysis by Recurrence Relations
       1. D.4.1 Tower of Hanoi
       2. D.4.2 A Nested loop program
       3. D.4.3 Divide and conquer
    5. D.5 Examples
       1. D.5.1 A frequently occurring form
13. Appendix E Additional Exercises with Solutions
    1. E.1 Additional Exercises
       1. E.1.1 Chapter 4: Loop design issues
       2. E.1.2 Chapter 6: Proof rule basics
       3. E.1.3 Chapter 7: Design by proof rules
       4. E.1.4 Chapter 9: Divide and conquer
       5. E.1.5 Chapter 10: Greedy methods
       6. E.1.6 Chapter 11: Dynamic orogramming
       7. E.1.7 Chapter 14: Efficiency of algorithms
       8. E.1.8 Chapter 15: Complexity calculation
       9. E.1.9 Chapter 17: Tractable and non-tractable problems
       10. E.1.10 Chapter 18: Some NP and NPC problems
       11. E.1.11 Chapter 19: Approximate solutions
       12. E.1.12 Appendix D: Solutions of recurrence relations
    2. E.2 Hints and Solutions
       1. E.2.1 Chapter 4: Loop design issues
       2. E.2.2 Chapter 6: Proof rules basic
       3. E.2.3 Chapter 7: Design by proof rules
       4. E.2.4 Chapter 9: Divide and conquer
       5. E.2.5 Chapter 10: Greedy algorithms
       6. E.2.6 Chapter 11: Dynamic programming
       7. E.2.7 Chapter 14: Efficiency of algorithms
       8. E.2.8 Chapter 15: Complexity calculations
       9. E.2.9 Chapter 17: Tractable and non-tractable problems
       10. E.2.10 Chapter 18: Some NP and NPC problems
       11. E.2.11 Chapter 19: Approximate solutions
       12. E.2.12 Appendix D: Solutions of recurrence relations
14. Bibliography
15. Notes
16. Copyright
17. Back Cover