book

Design and Analysis of Algorithms, 2nd Edition by Pearson

by Parag H. Dave, Himanshu B. Dave

May 2024

Intermediate to advanced

1112 pages

29h 44m

English

Pearson India

Read now

Unlock full access

Cover
Title Page
Brief Contents
Contents
Dedication
Preface
Preface to the First Edition
Timeline of Algorithms
Part 1: Algorithm Design
Chapter 1: Introduction
1.1 Basic Concerns 1.2 Relationship Between Algorithms and Other Aspects of Software 1.3 The Evolution of Algorithm 1.4 Why We Need Correctness Proof—A DemonstrationSummary Key TermsExercisesWeb Resources

Chapter 2: Problem Solving with a Computer
2.1 Introduction 2.2 Solving a Problem with a Computer 2.2.1 Statement of the Problem or Problem Definition 2.2.2 Development of a Model 2.2.3 Design of the Algorithm 2.2.4 Checking the Correctness of the Algorithm 2.2.5 Implementation in Some Programming Language 2.2.6 Analyze and Study the Complexity of the Algorithm 2.2.7 Program Testing—Debugging and Profiling 2.2.8 Documentation Preparation 2.3 Some More Examples 2.3.1 Finding the Square Root of a Number 2.3.2 Smallest Divisor of an Integer Number 2.3.3 Generation of Prime Numbers 2.3.4 Generation of Pseudo-random Numbers (PN) 2.4 Problem Solving in General 2.4.1 The STAIR Steps for Solving Problems 2.4.2 Problem Solving as Applied to Numerical Algorithms 2.4.3 Reduction to Known Problems 2.4.4 Strategy if we Are Stuck SummaryKey Terms ExercisesWeb Resources
Chapter 3: Top-Down Design
3.1 Introduction 3.2 Structured Programming 3.3 Control Constructs 3.3.1 IF-THEN-ELSE 3.3.2 FOR-DO 3.3.3 CASE 3.3.4 REPEAT-UNTIL 3.3.5 WHILE-DO 3.3.6 Goto and ExitLoop 3.4 Procedures and Functions 3.5 Recursion 3.5.1 Order of Execution of Statements in a Recursive FunctionSummary Key TermsExercisesWeb Resources
Chapter 4: Iterative Algorithm Design Issues
4.1 Introduction 4.2 Use of Loops 4.3 Efficiency of Algorithms 4.3.1 Removing Redundant Computations Outside Loops 4.3.2 Referencing of Array Elements 4.3.3 Inefficiency Due to Late Termination 4.3.4 Early Detection of Desired Output Conditions 4.4 Estimating and Specifying Execution Times 4.4.1 Justification for the Use of Problem Size as a Measure4.4.2 Computational Cost as a Function of Problem Size for a Range of Computational Complexities4.5 Order Notation 4.5.1 Big-Oh Notation 4.5.2 Theta Notation 4.5.3 Omega Notation 4.5.4 Small-Oh Notation 4.5.5 w Notation 4.5.6 Measuring the Execution Times 4.5.7 Other Trade-offs 4.5.8 Changes in Complexity Achieved by a Small Adjustment in the Algorithm4.6 Algorithm Strategies SummaryKey TermsExercisesWeb Resources
Chapter 5: Computation Models and Design by Refinement
5.1 Introduction 5.2 Functional Model 5.2.1 Features of Functional Model 5.2.2 Recursive Processes 5.2.3 Analysis of Correctness and Efficiency 5.2.4 More Examples of Recursive Algorithms 5.2.5 Scope Rules 5.2.6 Tail-recursion and Iterative Processes 5.2.7 Correctness of an Iterative Process 5.2.8 More Examples of Iterative Processes 5.3 Imperative Model 5.3.1 The Primitives for the Imperative Model 5.3.2 Specifications and Prototyping 5.3.3 Examples of Step-wise RefinementSummary Key TermsExercisesWeb Resources
Chapter 6: Proof Rules—Basics
6.1 Introduction 6.2 Computer Model for Program Execution 6.3 Assertions at Input and Output of Blocks 6.3.1 Symbolic Execution 6.4 Proof Rules 6.4.1 Compound Statements 6.4.2 Conditional Statements 6.4.3 Case Statements 6.4.4 Repetitive Statements 6.4.5 Repeat-Until Statement 6.4.6 Example: The Division Algorithm 6.5 Correct Termination of Algorithms 6.6 Proof Rules for More Advanced Constructs 6.6.1 For Loops6.6.2 GoTo and ExitLoop6.6.3 Program Transformation6.6.4 Functions and Procedures6.6.5 Recursive FunctionsSummaryKey TermsExercisesWeb Resources
Chapter 7: Design by Proof Rules
7.1 A Fresh Look at Proof Rules7.1.1 Referring to Previous Values of Variables7.1.2 Proof Rules7.2 Designing Correct Programs7.2.1 The Interface Specification7.2.2 Applying the Rules to Deduce the Program Statement Types 7.2.3 Design Example7.3 Design of a Loop7.3.1 Loop Termination7.4 A Simple Design Procedure for Loops Based on Proof-rules7.4.1 Example 1: Linear Search7.4.2 Example 2: Linear Search Without Assurance7.4.3 Example 3: Searching a 2-D Array7.5 Example: Selection Sort7.6 Example: Partition() Summary Key TermsExercises Web Resources
Chapter 8: Design Using Recursion
8.1 Introduction 8.2 Execution Trace8.2.1 Regular Expressions8.2.2 An Interesting Recursive Function8.3 Another Look at Iteration and RecursionSummary Key Terms Exercises Web Resources
Chapter 9: Abstract Algorithms 1—Divide-and-Conquer
9.1 Introduction9.2 A Multiplication Algorithm9.2.1 Analysis of the Multiplication Algorithm9.3 Application to Graphics Algorithms 9.3.1 Introduction to Triangulation9.3.2 Convex Hulls 9.4 Where D&C Fails 9.4.1 Characteristics of Problems for Which D&C is Unsuitable 9.5 Timing Analysis 9.6 Decrease-and-Conquer9.6.1 Examples of Decrease-and-Conquer9.6.2 Permutation Generation 9.6.3 Generating Gray Code Summary Key Terms Exercises Web Resources
Chapter 10: Abstract Algorithms 2—Greedy Methods
10.1 Introduction 10.2 Example—Knapsack Problem 10.3 Job Sequencing with Deadlines 10.4 Example—Minimum Spanning Trees 10.4.1 Prim’s Algorithm 10.4.2 Kruskal’s Algorithm 10.4.3 1st Version—Kruskal.c 10.4.4 Union-Find Data-structure 10.4.5 Tree-based Disjoint Sets and the Quick-Union Algorithm 10.4.6 Implementing Quick-Union with an Array 10.4.7 Complexity Analysis of Quick-Union 10.4.8 Using Union-Find in Kruskal Algorithm10.4.9 Matroids 10.4.10 Correctness of Kruskal’s Algorithm 10.5 Example [Shortest Path] 10.5.1 Dijkstra’s Shortest Path Algorithm 10.6 Optimal Merge Patterns 10.6.1 Greedy Optimal Merge Patterns 10.6.2 The Greedy Algorithm 10.6.3 Greedy Choice Property SummaryKey Terms Exercises Web Resources
Chapter 11: Abstract Algorithms 3—Dynamic Programming
11.1 Introduction 11.2 Rod Cutting Problem 11.3 Example—Multistage Graphs 11.4 Example—Traveling Salesman (TS) 11.5 Example—Matrix Multiplication 11.5.1 Brute Force Solution—Try All Possible Parenthesisations 11.5.2 Dynamic Programming 11.6 Example—Longest Common Sub-sequence (LCS) 11.6.1 Brute Force Method 11.6.2 Dynamic Programming 11.7 Example—Optimal Polygon Triangulation 11.7.1 Problem 11.8 Single Source Shortest Paths 11.8.1 Shortest Paths Problem 11.8.2 Shortest Paths Tree (Single Source) 11.8.3 All-Pairs Shortest Paths 11.9 Maximum Flow Problems 11.9.1 Flow Networks 11.9.2 Maximum-flow Problem 11.9.3 Analysis of Ford–Fulkerson Algorithm 11.10 Conclusion Summary Key Terms Exercises Web Resources
Chapter 12: Abstract Algorithms 4—Backtracking, Branch and Bound
12.1 Combinatorial Search 12.2 Search and Traversal 12.2.1 Breadth First Search (BFS) 12.2.2 Depth First Search (DFS) 12.3 The Backtracking Strategy 12.3.1 Example 1: 8-Queens Problem 12.4 Backtracking Framework 12.4.1 Efficiency of Backtracking 12.4.2 Example 2: M-Colouring Problem 12.4.3 Example 3: Hamiltonian Circuits 12.5 Some Typical State Spaces 12.5.1 Constructing All Subsets 12.5.2 Constructing All Permutations 12.5.3 Constructing All Paths in a Graph 12.5.4 Bandwidth Minimization 12.5.5 Covering Chess Boards 12.5.6 Convex Hull (Graham’s Scan) 12.6 Branch-and-Bound Algorithms 12.6.1 Example: Shortest Path 12.6.2 Branch-and-Bound Based on Partial Solutions 12.6.3 Example: 16-Puzzle and 8-Puzzle 12.6.4 Example: Scale Balancing 12.6.5 From DFS to Branch-and-Bound 12.6.6 Example: 0/1 Knapsack Problem 12.6.7 Example: TSP 12.6.8 Example: Integer Linear Programming 12.6.9 Example: TSP—On Bounding Function 12.6.10 Example: Locating Warehouses 12.6.11 Limitations of Branch and Bound 12.6.12 Branch and Cut SummaryKey Terms Exercises Web Resources
Chapter 13: Natural Algorithms—GA, SA, ANN, TS
13.1 Introduction 13.2 Evolutionary Algorithms and Evolutionary Computing 13.3 Genetic Algorithms 13.3.1 An Example Problem 13.3.2 Observations 13.4 Simulated Annealing 13.4.1 Sample Implementation 13.5 Artificial Neural Networks (ANN) 13.5.1 Analogy to the Brain 13.5.2 How they Work? 13.5.3 Electronic Implementation of Artificial Neurons 13.5.4 Artificial Network Operations 13.5.5 Training an Artificial Neural Network 13.5.6 Feed-Forward Network 13.5.7 Hopfield Feedback Connected Neural Network13.5.8 How Neural Networks differ from Traditional Computing and Expert Systems13.5.9 Artificial Neural Network Applications 13.6 Tabu Search (TS) 13.6.1 Application Domain 13.6.2 The Reactive Tabu Search (RTS)SummaryKey Terms Web Resources
Part 2: Algorithm Analysis
Chapter 14: Efficiency of Algorithms
14.1 Polynomial-Time (P) and Non-polynomial-Time (NPT) Algorithms 14.2 Worst and Average Case Behaviour 14.2.1 Probabilistic Average Case Analysis 14.3 Time Analysis of Algorithms 14.3.1 Example—Matrix Multiplication 14.3.2 More Timing Analysis 14.4 Efficiency of Recursion 14.5 Complexity 14.5.1 The Notion of Complexity 14.5.2 Profiling 14.5.3 Suppressing Multiplicative Constants 14.5.4 Counting Dominant Operations 14.5.5 Growth-Rate 14.5.6 Upper Bounds 14.5.7 Asymptotic Growth-Rate 14.5.8 The ‘O’ Notation 14.5.9 Discussion 14.5.10 Simplified Definition of ‘O’ 14.5.11 ‘O’ Notation Rules14.5.12 Analyzing Growth of Exotic Functions 14.5.13 Derivative Rule 14.5.14 Order-of-Magnitude Comparisons 14.5.15 Doubling Comparisons 14.5.16 Estimating Complexity Experimentally 14.5.17 Experimental Comparison of Sorting Procedures Summary Key Terms Exercises Web Resources
Chapter 15: Examples of Complexity Calculation
15.1 Examples from the Sorting World 15.1.1 Bucket Sort 15.1.2 Radix Sort 15.1.3 Simple Insertion Sort 15.1.4 Quick Sort 15.1.5 Heap Sort—Using a Tree to Sort 15.1.6 Merge Sort 15.1.7 Counting Sort 15.2 Summary of Complexity and Characteristics of Sorting Algorithms 15.3 Complexity of Set Operations and Mappings 15.3.1 Sets Implementation Using an Unordered Array15.3.2 Binary Search Principle 15.3.3 Binary Search Trees 15.3.4 Bit Vectors 15.3.5 Analysis of Hashing 15.3.6 The Trie Principle 15.3.7 Sets vs. Bags and Mappings 15.4 Amortized Analysis 15.4.1 Potential Functions 15.4.2 Example—Binary, Binomial and Fibonacci Heaps 15.4.3 Binomial Heap 15.4.4 Fibonacci Heap 15.5 Dĳkstra’s Shortest-path Algorithm 15.5.1 Analysis 15.6 Splay Trees 15.6.1 Basics of Splay Trees 15.6.2 Splay Operation 15.6.3 Amortized Timing Analysis 15.7 Van Emde Boas Trees 15.7.1 Direct Addressing of Bit-array 15.7.2 Binary Search Tree Over Bit-array 15.7.3 A Constant Height Tree Over Bit-array 15.7.4 A Prototype vEB Tree 15.7.5 Van Emde Boas Tree 15.7.6 Complexity Analysis of vEB Trees 15.7.7 Sample Implementation of vEB TreesSummary Key Terms Exercises Web Resources
Chapter 16: Time-Space Trade-Off
16.1 Introduction 16.1.1 An Example of Time-Space Trade-Off 16.2 A Quick Review of Complexity 16.3 Time-Space Trade-Off 16.3.1 Some Simple Examples16.4 Pattern Matching and String Processing 16.4.1 Naïve Algorithm16.4.2 Rabin-Karp String Matching algorithm16.4.3 Boyer-Moore String Search Algorithm 16.5 Time-Space Trade-Off in Algorithm Research 16.6 Case Study—Perrin Numbers16.6.1 Perrin Numbers16.6.2 First Try—Straight-Forward Implementation16.6.3 Second Try—Dynamic Programming16.6.4 Third Try—Reduction and Divide & Conquer16.5.5 The Final ResultsSummaryKey TermsExercisesWeb Resources
Chapter 17: Tractable and Non-tractable Problems
17.1 Introduction 17.1.1 Complexity for the Impatient 17.2 Upper and Lower Bounds17.2.1 Algorithmic Gap 17.3 Efficiency and Tractability 17.3.1 Problem Description17.3.2 A Quick and Operating Definition of NP-Complete Problems17.3.3 Some Known NP-Complete Problems17.3.4 What is a Certificate?17.3.5 Non-deterministic Algorithms 17.4 NP-Completeness 17.5 Polynomial Time Reductions17.6 Problem Classes P, NP, and Others17.6.1 Class P-Complete17.7 Bounded Halting is in NPC 17.8 Cook’s Theorem 17.8.1 An Example Reduction to SAT17.8.2 Examples of Problems in Different Classes17.9 Is P = NP?17.9.1 NP-Completeness17.9.2 How to Prove NP-Completeness in Practice17.9.3 Primality Test17.10 Approximate Solutions to NPC Problems17.11 Provably Intractable Problems 17.11.1 Example—An Intractable SAT17.12 Even Harder Problems 17.13 Unreasonable Requirements of Memory 17.14 Complexity Classes and Intractability17.15 Non-computability and Undecidability17.16 Algorithmic Program Verification 17.16.1 Halting Problem (HP)17.17 Partially and Highly Undecidable Problems17.18 The Four Levels of Algorithmic Behaviour SummaryKey Terms Web Resources
Chapter 18: Some NP and NP-Complete Problems
18.1 Introduction 18.1.1 NP-Hardness18.1.2 NP-Completeness18.1.3 Consequences of being in P18.1.4 Reduction Source Problems18.2 Turing Machine (TM)18.2.1 Relation Between Problems and Languages18.2.2 Decision Problems and Languages 18.3 Reductions18.3.1 Definition of Reductions 18.3.2 Reduction in P18.3.3 Transitivity of Reductions18.3.4 NP-Completeness to NP = P 18.3.5 Circuit Satisfiability Problem18.3.6 Reductions in NPC 18.3.7 Steps for Proving NP-Completeness18.4 Reductions for Some Known Problems18.4.1 Propositional Formulae18.4.2 SAT Problem18.4.3 3-Conjunctive Normal Form (3-CNF)-SAT Problem 18.4.4 Cliques of a Graph18.4.5 Vertex Cover (VC) 18.4.6 Hamiltonian Cycle (HC)18.4.7 Traveling Salesman Problem (TSP)18.4.8 Independent Set 18.5 Certificates and Verification Summary Key TermsExercisesWeb Resources
Chapter 19: Randomized and Approximate Algorithms
19.1 Introduction 19.1.1 A Very Simple Randomized Algorithm 19.2 Randomized Algorithms 19.2.1 Reasons for using Randomized Algorithms19.2.2 Background—Review of Probability Theory 19.2.3 Examples 19.2.4 Generation of Large Prime Numbers 19.3 Randomized Complexity Classes 19.3.1 RP: Randomized Polynomial Time 19.3.2 co-RP: Complement of RP19.3.3 ZPP: Zero-Error Probabilistic Polynomial Time19.3.4 BPP: Bounded-Error Probabilistic Polynomial Time 19.4 Approximate Algorithms 19.4.1 NP-Hard Optimization Problems 19.4.2 Examples—Approximation Algorithms 19.4.3 Analysis of Approximation Algorithms 19.4.4 Traveling Salesman Problem19.4.5 Colouring 3-Colourable Graphs19.4.6 Decision Problems 19.4.7 Approximation Algorithms 19.4.8 Approximation of TSP 19.5 Case Study: An Implementation of Sudoku-solver Using Randomized Algorithm 19.5.1 Introduction 19.5.2 Overview of the Program 19.5.3 Major Functions 19.5.4 Testing and Results19.5.5 Discussion and Conclusion Annexure-I Summary Key Terms Exercises Web Resources
Chapter 20: Formal Specifications—1 Model Oriented
20.1 Formal Specifications 20.1.1 A First Specification Language20.1.2 What Is a Software Specification? 20.1.3 What Is a Formal Specification?20.1.4 An Apparent Disadvantage of FSL20.2 Introduction to VDM 20.2.1 The Implicit Specification of Operations 20.2.2 Examples of Implicit Specifications20.2.3 The Logical Condition 20.2.4 Reasoning with Pre- and Post-conditions20.2.5 Introduction to VDM Data Types20.2.6 The Primitive Types20.2.7 The Set Type 20.2.8 Implicit Definition of Sets 20.2.9 Creating VDM State Models20.2.10 Composites20.3 A Systematic Approach to the Construction of VDM Specifications 20.3.1 Creation of a System State20.3.2 Construction of Data Type Invariants20.3.3 Modeling of the System’s Operations20.3.4 Discharging Proof Obligations20.3.5 Specification Refinement 20.3.6 Formal Proof Obligations20.3.7 Recapitulation 20.4 The Sequence and Map Types20.4.1 The Sequence Data Type20.4.2 The Map Data Type20.4.3 A Small ExampleSummary Key Terms Exercises Web Resources
Chapter 21: Formal Specifications—2 Algebraic
21.1 Introduction 21.1.1 Specification of Abstract Data Types21.1.2 Algebraic Specification of Abstract Data Types 21.1.3 An Algebraic Specification Language21.2 Algebraic Specification of an Unbounded Stack21.2.1 Comparison with VDM21.2.2 Completeness21.2.3 Examples of Evaluations21.2.4 Axioms and Term Rewriting 21.2.5 Pattern Matching and Unification SummaryKey TermsExercises Web Resources
Appendix A: Essential Mathematical Background
A.1 What is Discrete Mathematics? A.2 Formal Logic: A Language for Mathematics A.2.1 Assertions and Propositions A.2.2 Logical Connectives A.2.3 Tautologies, Contradictions, and Contingencies A.2.4 Proof Techniques A.2.5 Predicates A.2.6 Quantifiers A.2.7 Free and Bound Variables A.2.8 Implications and Equivalences A.2.9 Classification of Assertions in Predicate Logic A.2.10 Inference Rules in Predicate Logic A.3 Sets A.3.1 Notations for Sets A.3.2 Relationships Between Sets A.3.3 Set Operations A.3.4 Properties of Sets A.3.5 Functions A.3.6 Operations on Functions A.3.7 Classification of Total Functions A.3.8 Cardinality of a Set A.3.9 Sequences and Series A.4 Asymptotic Notations A.5 Number Theory A.5.1 LCM and GCD A.5.2 Primes and Factorization A.5.3 Congruences and Modular Arithmetic A.5.4 Applications of Mathematics in Computer Science A.6 Formal Languages A.6.1 Strings A.6.2 Binary Operation on Strings A.6.3 Relationships Between Strings A.6.4 Inductive Definitions A.6.5 Languages A.6.6 Binary Operation on Languages A.6.7 Power Xi of a Language X A.6.8 Closure of a Language A.7 Proof by Induction A.7.1 First Principle of Mathematical Induction A.7.2 Second Principle of Mathematical Induction A.8 Introduction to Combinatorics A.8.1 Principles of Combinatorics A.8.2 Choosing Elements from Sets A.8.3 Permutations A.8.4 Multiset (or Bag) A.8.5 Permutations in Circular Order A.8.6 Samples A.8.7 Combinations A.8.8 Selections A.8.9 Pigeonhole Principle or Dirichlet Drawer Principle A.9 Random Variables A.9.1 Discrete Distribution Functions A.9.2 Expected Values A.9.3 Variance and Standard Deviation A.9.4 Central Limit Theorem A.10 Relations A.10.1 Binary Relations and Digraphs A.10.2 Classification of Binary Relations A.10.3 Operations on Relations A.10.4 Equivalence Relations and Equivalence Classes A.10.5 Partitions A.10.6 Order Relations A.10.7 Upper Bounds and Lower Bounds A.11 Graph Theory A.11.1 Directed Graph or Digraph A.11.2 Undirected Graphs A.11.3 Trees A.11.4 Matrix Representations of GraphsExercises
Appendix B: Overview of Essential Data Structures
B.1 Introduction B.2 Primitive Data Structures B.3 Arrays and Lists B.3.1 Linked Storage B.3.2 Pointers and Linked Allocation B.3.3 Linked Linear List B.3.4 Operations on Linked Lists B.3.5 Circularly Linked Linear Lists B.3.6 Doubly Linked Linear Lists B.4 StacksB.4.1 Operations on StacksB.5 QueuesB.5.1 Circular Queues B.5.2 Double Ended Queues B.6 Priority Queues B.7 TreesB.7.1 Operations on a Binary Tree B.7.2 Storage Representation and Manipulation B.7.3 Linked Storage B.7.4 Threaded Storage B.8 Binary Search Trees B.8.1 Searching B.8.2 Binary Search Trees B.8.3 Analysis of Binary Search Trees B.8.4 Balanced Binary Trees B.8.5 2-3 Trees B.8.6 B-Trees B.8.7 Tries B.8.8 Huffman Tree B.9 Skip Lists B.9.1 Shortcuts B.9.2 Skip Lists B.9.3 Implementation B.10 Hash Tables B.10.1 Hash Functions B.10.2 Collision Resolution B.10.3 Separate Chaining B.11 Graphs B.11.1 Matrix Representation B.11.2 Topological Sort B.12 Linked List-Structure B.13 Augmenting Data Structures B.13.1 An Augmentation Strategy B.13.2 Interval Overlap or Interval Tree
Appendix C: Solutions of Recurrence Relations
C.1 IntroductionC.2 PreliminariesC.2.1 Sequences and Generating Functions C.2.2 Characteristic Polynomial C.2.3 Recurrence Systems C.2.4 Solutions of Recurrence Systems C.2.5 Classification of Recurrence Systems C.2.6 Uniqueness of a Solution to a Linear Recurrence System C.2.7 Principle of Superposition C.3 Methods of Solution of Recurrence Relations C.3.1 Method of Iteration C.3.2 Method of SubstitutionC.3.3 Using Master TheoremC.3.4 Method of Generating Function C.3.5 Method of Characteristic RootsC.3.6 Method of Undetermined CoefficientsC.3.7 Higher-order Recurrence SystemsC.4 Algorithm Analysis by Recurrence RelationsC.4.1 Tower of HanoiC.4.2 A Nested Loop ProgramC.4.3 Divide and ConquerC.5 ExamplesC.5.1 A Frequently Occurring Form Exercises
Appendix D: Additional Exercises with Solutions
D.1 Additional ExercisesD.1.1 Chapter 4: Loop Design Issues D.1.2 Chapter 6: Proof Rule BasicsD.1.3 Chapter 7: Design by Proof RulesD.1.4 Chapter 9: Divide and ConquerD.1.5 Chapter 10: Greedy MethodsD.1.6 Chapter 11: Dynamic ProgrammingD.1.7 Chapter 12: Backtracking and Branch-and-BoundD.1.8 Chapter 14: Efficiency of AlgorithmsD.1.9 Chapter 15: Complexity Calculation D.1.10 Chapter 17: Tractable and Non-tractable ProblemsD.1.11 Chapter 18: Some NP and NPC ProblemsD.1.12 Chapter 19: Approximate SolutionsD.1.13 Appendix D: Solutions of Recurrence RelationsD.2 Hints and Solutions D.2.1 Chapter 4: Loop Design IssuesD.2.2 Chapter 6: Proof Rules BasicD.2.3 Chapter 7: Design by Proof Rules D.2.4 Chapter 9: Divide and Conquer
D.2.5 Chapter 10: Greedy Algorithms
D.2.6 Chapter 11: Dynamic ProgrammingD.2.7 Chapter 12: Backtracking and Branch-and-Bound
D.2.8 Chapter 14: Efficiency of Algorithms
D.2.9 Chapter 15: Complexity CalculationsD.2.10 Chapter 17: Tractable and Non-tractable ProblemsD.2.11 Chapter 18: Some NP and NPC ProblemsD.2.12 Chapter 19: Approximate SolutionsD.2.13 Appendix D: Solutions of Recurrence Relations
Appendix E: Examples of Algorithms
E.1 Existence of a TriangleE.2 GCD—Recursive ImplementationE.3 Knight’s TourE.4 Tail Recursion—Factorial() E.5 Recursive Implementation of Fibonacci() E.6 Power FunctionE.7 Amicable NumbersE.8 Premature ExitsE.9 Vertex CoverE.10 Context Free LanguageE.11 Optimum Places for Line Breaks E.12 Car Travel ProblemE.13 Activity Selection Problem E.14 Scheduling with Deadlines, Profits and Duration E.15 Longest Up-sequence E.15.1 On the Longest Upsequence Problem for PermutationsE.15.2 Introduction E.15.3 Finding the Longest Upsequence E.16 Unary PartitionE.17 Upper Bound on Time ComplexityE.17.1 Program a E.17.2 Program b E.17.3 Program c E.17.4 Program d E.17.5 Program e E.17.6 Program f E.17.7 Program gE.17.8 Program h E.18 van Emde Boas Tree Space UsageE.19 Empirical Study of Space Used by van Emde Boas Trees E.20 Reducing the Space in the van Emde Boas StructureE.20.1 insert() for the Modified vEB TreeE.20.2 succ() for the Modified vEB TreeE.20.3 member() for the Modified vEB TreeE.20.4 Space Occupied by the Modified vEB Tree E.21 Binary Trie E.22 X-fast_trie E.23 Y-fast_trie E.24 Numerical Algorithms—Correlation E.25 Numerical Algorithms—ConvolutionE.26 Numerical Algorithms—Discrete Fourier TransformE.26.1 Discrete Cosine Transform (DCT) E.27 Numerical Algorithms—Fast Fourier Transform E.28 Numerical Algorithms—Wavelet TransformsE.29 Numerical Algorithms—Digital Signal ProcessingE.29.1 Examples of Simple Digital Filters E.30 Numerical Algorithms—Z Transform E.30.1 Relation Between Z and FTE.30.2 Properties of Z TransformE.30.3 Convolution of SequencesE.30.4 Implementation of a Digital FilterE.30.5 Numerical Algorithms—Reference Books
Bibliography
Copyright
Back Cover

Overview

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.

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9789332524606

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills