Design and analysis of Algorithms, 2nd Edition

Design and analysis of Algorithms, 2nd Edition

Released June 2013
Publisher(s): Pearson India
ISBN: 9789332520158

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

This second edition of Design and Analysis of Algorithms continues to provide a comprehensive exposure to the subject with new inputs on contemporary topics in algorithm design and algorithm analysis. Spread over 21 chapters aptly complemented by five appendices, the book interprets core concepts with ease in logical succession to the student's benefit.

Table of contents

  1. Cover
  2. Title Page
  3. Brief Contents
  4. Contents
  5. Dedication
  6. Preface
  7. Preface to the First Edition
  8. Timeline of Algorithms
  9. 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. 1.4 Why We Need Correctness Proof—A Demonstration
      5. Summary
      6. Key Terms
      7. Exercises
      8. 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 w Notation
        6. 4.5.6 Measuring the Execution Times
        7. 4.5.7 Other Trade-offs
        8. 4.5.8 Changes in Complexity Achieved by a Small Adjustment in the Algorithm
      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. 9.6 Decrease-and-Conquer
        1. 9.6.1 Examples of Decrease-and-Conquer
        2. 9.6.2 Permutation Generation
        3. 9.6.3 Generating Gray Code
      7. Summary
      8. Key Terms
      9. Exercises
      10. 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. 10.6 Optimal Merge Patterns
        1. 10.6.1 Greedy Optimal Merge Patterns
        2. 10.6.2 The Greedy Algorithm
        3. 10.6.3 Greedy Choice Property
      7. Summary
      8. Key Terms
      9. Exercises
      10. Web Resources
    11. Chapter 11: Abstract Algorithms 3—Dynamic Programming
      1. 11.1 Introduction
      2. 11.2 Rod Cutting Problem
      3. 11.3 Example—Multistage Graphs
      4. 11.4 Example—Traveling Salesman (TS)
      5. 11.5 Example—Matrix Multiplication
        1. 11.5.1 Brute Force Solution—Try All Possible Parenthesisations
        2. 11.5.2 Dynamic Programming
      6. 11.6 Example—Longest Common Sub-sequence (LCS)
        1. 11.6.1 Brute Force Method
        2. 11.6.2 Dynamic Programming
      7. 11.7 Example—Optimal Polygon Triangulation
        1. 11.7.1 Problem
      8. 11.8 Single Source Shortest Paths
        1. 11.8.1 Shortest Paths Problem
        2. 11.8.2 Shortest Paths Tree (Single Source)
        3. 11.8.3 All-Pairs Shortest Paths
      9. 11.9 Maximum Flow Problems
        1. 11.9.1 Flow Networks
        2. 11.9.2 Maximum-flow Problem
        3. 11.9.3 Analysis of Ford–Fulkerson Algorithm
      10. 11.10 Conclusion
      11. Summary
      12. Key Terms
      13. Exercises
      14. Web Resources
    12. Chapter 12: Abstract Algorithms 4—Backtracking, Branch and Bound
      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. 12.6 Branch-and-Bound Algorithms
        1. 12.6.1 Example: Shortest Path
        2. 12.6.2 Branch-and-Bound Based on Partial Solutions
        3. 12.6.3 Example: 16-Puzzle and 8-Puzzle
        4. 12.6.4 Example: Scale Balancing
        5. 12.6.5 From DFS to Branch-and-Bound
        6. 12.6.6 Example: 0/1 Knapsack Problem
        7. 12.6.7 Example: TSP
        8. 12.6.8 Example: Integer Linear Programming
        9. 12.6.9 Example: TSP—On Bounding Function
        10. 12.6.10 Example: Locating Warehouses
        11. 12.6.11 Limitations of Branch and Bound
        12. 12.6.12 Branch and Cut
      7. Summary
      8. Key Terms
      9. Exercises
      10. 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 Feed-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 (TS)
        1. 13.6.1 Application Domain
        2. 13.6.2 The Reactive Tabu Search (RTS)
      7. Summary
      8. Key Terms
      9. Web Resources
  10. Part 2: Algorithm Analysis
    1. Chapter 14: Efficiency of Algorithms
      1. 14.1 Polynomial-Time (P) and Non-polynomial-Time (NPT) 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
        7. 15.1.7 Counting 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. 15.7 Van Emde Boas Trees
        1. 15.7.1 Direct Addressing of Bit-array
        2. 15.7.2 Binary Search Tree Over Bit-array
        3. 15.7.3 A Constant Height Tree Over Bit-array
        4. 15.7.4 A Prototype vEB Tree
        5. 15.7.5 Van Emde Boas Tree
        6. 15.7.6 Complexity Analysis of vEB Trees
        7. 15.7.7 Sample Implementation of vEB Trees
      8. Summary
      9. Key Terms
      10. Exercises
      11. 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 Pattern Matching and String Processing
        1. 16.4.1 Naïve Algorithm
        2. 16.4.2 Rabin-Karp String Matching algorithm
        3. 16.4.3 Boyer-Moore String Search Algorithm
      5. 16.5 Time-Space Trade-Off in Algorithm Research
      6. 16.6 Case Study—Perrin Numbers
        1. 16.6.1 Perrin Numbers
        2. 16.6.2 First Try—Straight-Forward Implementation
        3. 16.6.3 Second Try—Dynamic Programming
        4. 16.6.4 Third Try—Reduction and Divide & Conquer
        5. 16.5.5 The Final Results
      7. Summary
      8. Key Terms
      9. Exercises
      10. Web Resources
    4. Chapter 17: Tractable and Non-tractable Problems
      1. 17.1 Introduction
        1. 17.1.1 Complexity for the Impatient
      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
        1. 17.6.1 Class P-Complete
      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
        1. 19.1.1 A Very Simple Randomized Algorithm
      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. 19.5 Case Study: An Implementation of Sudoku-solver Using Randomized Algorithm
        1. 19.5.1 Introduction
        2. 19.5.2 Overview of the Program
        3. 19.5.3 Major Functions
        4. 19.5.4 Testing and Results
        5. 19.5.5 Discussion and Conclusion
      6. Annexure-I
      7. Summary
      8. Key Terms
      9. Exercises
      10. 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 Xi 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: Overview of Essential Data Structures
      1. B.1 Introduction
      2. B.2 Primitive Data Structures
      3. B.3 Arrays and Lists
        1. B.3.1 Linked Storage
        2. B.3.2 Pointers and Linked Allocation
        3. B.3.3 Linked Linear List
        4. B.3.4 Operations on Linked Lists
        5. B.3.5 Circularly Linked Linear Lists
        6. B.3.6 Doubly Linked Linear Lists
      4. B.4 Stacks
        1. B.4.1 Operations on Stacks
      5. B.5 Queues
        1. B.5.1 Circular Queues
        2. B.5.2 Double Ended Queues
      6. B.6 Priority Queues
      7. B.7 Trees
        1. B.7.1 Operations on a Binary Tree
        2. B.7.2 Storage Representation and Manipulation
        3. B.7.3 Linked Storage
        4. B.7.4 Threaded Storage
      8. B.8 Binary Search Trees
        1. B.8.1 Searching
        2. B.8.2 Binary Search Trees
        3. B.8.3 Analysis of Binary Search Trees
        4. B.8.4 Balanced Binary Trees
        5. B.8.5 2-3 Trees
        6. B.8.6 B-Trees
        7. B.8.7 Tries
        8. B.8.8 Huffman Tree
      9. B.9 Skip Lists
        1. B.9.1 Shortcuts
        2. B.9.2 Skip Lists
        3. B.9.3 Implementation
      10. B.10 Hash Tables
        1. B.10.1 Hash Functions
        2. B.10.2 Collision Resolution
        3. B.10.3 Separate Chaining
      11. B.11 Graphs
        1. B.11.1 Matrix Representation
        2. B.11.2 Topological Sort
      12. B.12 Linked List-Structure
      13. B.13 Augmenting Data Structures
        1. B.13.1 An Augmentation Strategy
        2. B.13.2 Interval Overlap or Interval Tree
    11. Appendix C: Solutions of Recurrence Relations
      1. C.1 Introduction
      2. C.2 Preliminaries
        1. C.2.1 Sequences and Generating Functions
        2. C.2.2 Characteristic Polynomial
        3. C.2.3 Recurrence Systems
        4. C.2.4 Solutions of Recurrence Systems
        5. C.2.5 Classification of Recurrence Systems
        6. C.2.6 Uniqueness of a Solution to a Linear Recurrence System
        7. C.2.7 Principle of Superposition
      3. C.3 Methods of Solution of Recurrence Relations
        1. C.3.1 Method of Iteration
        2. C.3.2 Method of Substitution
        3. C.3.3 Using Master Theorem
        4. C.3.4 Method of Generating Function
        5. C.3.5 Method of Characteristic Roots
        6. C.3.6 Method of Undetermined Coefficients
        7. C.3.7 Higher-order Recurrence Systems
      4. C.4 Algorithm Analysis by Recurrence Relations
        1. C.4.1 Tower of Hanoi
        2. C.4.2 A Nested Loop Program
        3. C.4.3 Divide and Conquer
      5. C.5 Examples
        1. C.5.1 A Frequently Occurring Form
      6. Exercises
    12. Appendix D: Additional Exercises with Solutions
      1. D.1 Additional Exercises
        1. D.1.1 Chapter 4: Loop Design Issues
        2. D.1.2 Chapter 6: Proof Rule Basics
        3. D.1.3 Chapter 7: Design by Proof Rules
        4. D.1.4 Chapter 9: Divide and Conquer
        5. D.1.5 Chapter 10: Greedy Methods
        6. D.1.6 Chapter 11: Dynamic Programming
        7. D.1.7 Chapter 12: Backtracking and Branch-and-Bound
        8. D.1.8 Chapter 14: Efficiency of Algorithms
        9. D.1.9 Chapter 15: Complexity Calculation
        10. D.1.10 Chapter 17: Tractable and Non-tractable Problems
        11. D.1.11 Chapter 18: Some NP and NPC Problems
        12. D.1.12 Chapter 19: Approximate Solutions
        13. D.1.13 Appendix D: Solutions of Recurrence Relations
      2. D.2 Hints and Solutions
        1. D.2.1 Chapter 4: Loop Design Issues
        2. D.2.2 Chapter 6: Proof Rules Basic
        3. D.2.3 Chapter 7: Design by Proof Rules
        4. D.2.4 Chapter 9: Divide and Conquer
        5. D.2.5 Chapter 10: Greedy Algorithms
        6. D.2.6 Chapter 11: Dynamic Programming
        7. D.2.7 Chapter 12: Backtracking and Branch-and-Bound
        8. D.2.8 Chapter 14: Efficiency of Algorithms
        9. D.2.9 Chapter 15: Complexity Calculations
        10. D.2.10 Chapter 17: Tractable and Non-tractable Problems
        11. D.2.11 Chapter 18: Some NP and NPC Problems
        12. D.2.12 Chapter 19: Approximate Solutions
        13. D.2.13 Appendix D: Solutions of Recurrence Relations
    13. Appendix E: Examples of Algorithms
      1. E.1 Existence of a Triangle
      2. E.2 GCD—Recursive Implementation
      3. E.3 Knight’s Tour
      4. E.4 Tail Recursion—Factorial()
      5. E.5 Recursive Implementation of Fibonacci()
      6. E.6 Power Function
      7. E.7 Amicable Numbers
      8. E.8 Premature Exits
      9. E.9 Vertex Cover
      10. E.10 Context Free Language
      11. E.11 Optimum Places for Line Breaks
      12. E.12 Car Travel Problem
      13. E.13 Activity Selection Problem
      14. E.14 Scheduling with Deadlines, Profits and Duration
      15. E.15 Longest Up-sequence
        1. E.15.1 On the Longest Upsequence Problem for Permutations
        2. E.15.2 Introduction
        3. E.15.3 Finding the Longest Upsequence
      16. E.16 Unary Partition
      17. E.17 Upper Bound on Time Complexity
        1. E.17.1 Program a
        2. E.17.2 Program b
        3. E.17.3 Program c
        4. E.17.4 Program d
        5. E.17.5 Program e
        6. E.17.6 Program f
        7. E.17.7 Program g
        8. E.17.8 Program h
      18. E.18 van Emde Boas Tree Space Usage
      19. E.19 Empirical Study of Space Used by van Emde Boas Trees
      20. E.20 Reducing the Space in the van Emde Boas Structure
        1. E.20.1 insert() for the Modified vEB Tree
        2. E.20.2 succ() for the Modified vEB Tree
        3. E.20.3 member() for the Modified vEB Tree
        4. E.20.4 Space Occupied by the Modified vEB Tree
      21. E.21 Binary Trie
      22. E.22 X-fast_trie
      23. E.23 Y-fast_trie
      24. E.24 Numerical Algorithms—Correlation
      25. E.25 Numerical Algorithms—Convolution
      26. E.26 Numerical Algorithms—Discrete Fourier Transform
        1. E.26.1 Discrete Cosine Transform (DCT)
      27. E.27 Numerical Algorithms—Fast Fourier Transform
      28. E.28 Numerical Algorithms—Wavelet Transforms
      29. E.29 Numerical Algorithms—Digital Signal Processing
        1. E.29.1 Examples of Simple Digital Filters
      30. E.30 Numerical Algorithms—Z Transform
        1. E.30.1 Relation Between Z and FT
        2. E.30.2 Properties of Z Transform
        3. E.30.3 Convolution of Sequences
        4. E.30.4 Implementation of a Digital Filter
        5. E.30.5 Numerical Algorithms—Reference Books
  11. Bibliography
  12. Copyright
  13. Back Cover

Product information

  • Title: Design and analysis of Algorithms, 2nd Edition
  • Author(s):
  • Release date: June 2013
  • Publisher(s): Pearson India
  • ISBN: 9789332520158