book

Design and Analysis of Algorithms

Name: Design and Analysis of Algorithms
ISBN: 9788177585957

by Parag H. Dave, Himanshu B. Dave

September 2007

Intermediate to advanced

832 pages

23h 49m

English

Pearson India

Read now

Unlock full access

Cover
Title page
Brief Contents
Contents
Dedication
Preface
Part 1. Algorithm Design
Chapter 1. Introduction
1.1 Basic Concerns1.2 Relationship between Algorithms and other aspects of Software1.3 The Evolution of AlgorithmSummaryKey TermsExercisesWeb Resources
Chapter 2. Problem Solving with a Computer
2.1 Introduction2.2 Solving a Problem with a Computer2.2.1 Statement of the problem or problem definition2.2.2 Development of a model2.2.3 Design of the algorithm2.2.4 Checking the correctness of the algorithm2.2.5 Implementation in some programming language2.2.6 Analyze and study the complexity of the algorithm2.2.7 Program testing—debugging and profiling2.2.8 Documentation preparation2.3 Some More Examples2.3.1 Finding the square root of a number2.3.2 Smallest divisor of an integer number2.3.3 Generation of prime numbers2.3.4 Generation of pseudo-random numbers (PN)2.4 Problem Solving in General2.4.1 The STAIR steps for solving problems2.4.2 Problem solving as applied to numerical algorithms2.4.3 Reduction to known problems2.4.4 Strategy if we are stuckSummaryKey TermsExercisesWeb Resources
Chapter 3. Top-Down Design
3.1 Introduction3.2 Structured Programming3.3 Control Constructs3.3.1 If-Then-Else3.3.2 For-Do3.3.3 Case3.3.4 Repeat-Until3.3.5 While-Do3.3.6 Goto and ExitLoop3.4 Procedures and Functions3.5 Recursion3.5.1 Order of execution of statements in a recursive functionSummaryKey TermsExercisesWeb Resources

Chapter 4. Iterative Algorithm Design Issues
4.1 Introduction4.2 Use of Loops4.3 Efficiency of Algorithms4.3.1 Removing redundant computations outside loops4.3.2 Referencing of array elements4.3.3 Inefficiency due to late termination4.3.4 Early detection of desired output conditions4.4 Estimating and Specifying Execution Times4.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 Notation4.5.1 Big-oh notation4.5.2 Theta notation4.5.3 Omega notation4.5.4 Small-oh notation4.5.5 ω notation4.5.6 Measuring the execution times4.5.7 Other trade-offs4.6 Algorithm StrategiesSummaryKey TermsExercisesWeb Resources
Chapter 5. Computation Models and Design by Refinement
5.1 Introduction5.2 Functional Model5.2.1 Features of functional model5.2.2 Recursive processes5.2.3 Analysis of correctness and efficiency5.2.4 More examples of recursive algorithms5.2.5 Scope rules5.2.6 Tail-recursion and iterative processes5.2.7 Correctness of an iterative process5.2.8 More examples of iterative processes5.3 Imperative Model5.3.1 The primitives for the imperative model5.3.2 Specifications and prototyping5.3.3 Examples of step wise refinementSummaryKey TermsExercisesWeb Resources
Chapter 6. Proof Rules—Basics
6.1 Introduction6.2 Computer Model for Program Execution6.3 Assertions at Input and Output of Blocks6.3.1 Symbolic execution6.4 Proof Rules6.4.1 Compound statements6.4.2 Conditional statements6.4.3 Case statements6.4.4 Repetitive statements6.4.5 Repeat-Until statement6.4.6 Example: The division algorithm6.5 Correct Termination of Algorithms6.6 Proof Rules for more Advanced Constructs6.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 types7.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 ()SummaryKey TermsExercisesWeb Resources
Chapter 8. Design using Recursion
8.1 Introduction8.2 Execution Trace8.2.1 Regular expressions8.2.2 An interesting recursive function8.3 Another Look at Iteration and RecursionSummaryKey TermsExercisesWeb 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 Algorithms9.3.1 Introduction to triangulation9.3.2 Convex hulls9.4 Where D & C Fails9.4.1 Characteristics of problems for which D & C is unsuitable9.5 Timing AnalysisSummaryKey TermsExercisesWeb Resources
Chapter 10. Abstract Algorithms 2—Greedy Methods
10.1 Introduction10.2 Example—Knapsack Problem10.3 Job Sequencing with Deadlines10.4 Example—Minimum Spanning Trees10.4.1 Prim’s algorithm10.4.2 Kruskal’s algorithm10.4.3 1st Version—Kruskal.c10.4.4 Union-find data-structure10.4.5 Tree-based disjoint sets and the quick-union algorithm10.4.6 Implementing quick-union with an array10.4.7 Complexity analysis of quick-union10.4.8 Using union-find in Kruskal algorithm10.4.9 Matroids10.4.10 Correctness of Kruskal’s algorithm10.5 Example [Shortest Path]10.5.1 Dijkstra’s shortest path algorithmSummaryKey TermsExercisesWeb Resources
Chapter 11. Abstract Algorithms 3—Dynamic Programming
11.1 Introduction11.2 Example—Multistage Graphs11.3 Example—Traveling Salesman (TS)11.4 Example—Matrix Multiplication11.4.1 Brute force solution—try all possible parenthesisations11.4.2 Dynamic programming11.5 Example—Longest Common Sub-sequence (LCS)11.5.1 Brute force method11.5.2 Dynamic programming11.6 Example—Optimal Polygon Triangulation11.6.1 Problem11.7 Single Source Shortest Paths11.7.1 Shortest paths problem11.7.2 Shortest paths tree (single source)11.7.3 All-pairs shortest paths11.8 Maximum Flow Problems11.8.1 Flow networks11.8.2 Maximum-flow problem11.8.3 Analysis of Ford-Fulkerson algorithm11.9 ConclusionSummaryKey TermsExercisesWeb Resources
Chapter 12. Abstract Algorithms 4—Backtracking
12.1 Combinatorial Search12.2 Search and Traversal12.2.1 Breadth First Search (BFS)12.2.2 Depth First Search (DFS)12.3 The Backtracking Strategy12.3.1 Example 1: 8-Queens problem12.4 Backtracking Framework12.4.1 Efficiency of backtracking12.4.2 Example 2: M-colouring problem12.4.3 Example 3: Hamiltonian circuits12.5 Some Typical State Spaces12.5.1 Constructing all subsets12.5.2 Constructing all permutations12.5.3 Constructing all paths in a graph12.5.4 Bandwidth minimization12.5.5 Covering chess boards12.5.6 Convex Hull (Graham’s scan)SummaryKey TermsExercisesWeb Resources
Chapter 13. Natural Algorithms—GA, SA, ANN, TS
13.1 Introduction13.2 Evolutionary Algorithms and Evolutionary Computing13.3 Genetic Algorithms13.3.1 An example problem13.3.2 Observations13.4 Simulated Annealing13.4.1 Sample implementation13.5 Artificial Neural Networks (ANN)13.5.1 Analogy to the brain13.5.2 How they work?13.5.3 Electronic implementation of artificial neurons13.5.4 Artificial network operations13.5.5 Training an artificial neural network13.5.6 F eed-forward network13.5.7 Hopfield feedback connected neural network13.5.8 How neural networks differ from traditional computing and expert systems13.5.9 Artificial neural network applications13.6 Tabu Search13.6.1 Application domain13.6.2 The Reactive Tabu Search (RTS)SummaryKey TermsWeb Resources
Part 2. Algorithm Analysis
Chapter 14. Efficiency of Algorithms
14.1 Polynomial-Time and Non-Polynomial-Time Algorithms14.2 Worst and Average Case Behaviour14.2.1 Probabilistic average case analysis14.3 Time Analysis of Algorithms14.3.1 Example —Matrix multiplication14.3.2 More timing analysis14.4 Efficiency of Recursion14.5 Complexity14.5.1 The notion of complexity14.5.2 Profiling14.5.3 Suppressing multiplicative constants14.5.4 Counting dominant operations14.5.5 Growth-Rate14.5.6 Upper bounds14.5.7 Asymptotic growth-rate14.5.8 The ‘O’ notation14.5.9 Discussion14.5.10 Simplified definition of ‘O’14.5.11 ‘O’ notation rules14.5.12 Analyzing growth of exotic functions14.5.13 Derivative rule14.5.14 Order-of-magnitude comparisons14.5.15 Doubling comparisons14.5.16 Estimating complexity experimentally14.5.17 Experimental comparison of sorting proceduresSummaryKey TermsExercisesWeb Resources
Chapter 15. Examples of Complexity Calculation
15.1 Examples from the Sorting World15.1.1 Bucket sort15.1.2 Radix sort15.1.3 Simple insertion sort15.1.4 Quick sort15.1.5 Heap sort—using a Tree to sort15.1.6 Merge sort15.2 Summary of Complexity and Characteristics of Sorting Algorithms15.3 Complexity of Set Operations and Mappings15.3.1 Sets implementation using an unordered array15.3.2 Binary search principle15.3.3 Binary search trees15.3.4 Bit vectors15.3.5 Analysis of hashing15.3.6 The trie principle15.3.7 Sets vs. bags and mappings15.4 Amortized Analysis15.4.1 Potential functions15.4.2 Example—binary, binomial and fibonacci heaps15.4.3 Binomial heap15.4.4 Fibonacci heap15.5 Dijkstra’s Shortest-Path Algorithm15.5.1 Analysis15.6 Splay Trees15.6.1 Basics of splay trees15.6.2 Splay operation15.6.3 Amortized timing analysisSummaryKey TermsExercisesWeb Resources
Chapter 16. Time-Space Trade-Off
16.1 Introduction16.1.1 An example of time-space trade-off16.2 A Quick Review of Complexity16.3 Time-Space Trade-Off16.3.1 Some simple examples16.4 Time-Space Trade-Off in Algorithm Research16.5 Case Study—Perrin Numbers16.5.1 Perrin numbers16.5.2 First try—straight-forward implementation16.5.3 Second try—dynamic programming16.5.4 Third try—reduction and divide & conquer16.5.5 The final resultsSummaryKey TermsExercisesWeb Resources
Chapter 17. Tractable and Non-Tractable Problems
17.1 Introduction17.2 Upper and Lower Bounds17.2.1 Algorithmic gap17.3 Efficiency and Tractability17.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 algorithms17.4 NP-Completeness17.5 Polynomial Time Reductions17.6 Problem Classes P, NP, and Others17.7 Bounded Halting is in NPC17.8 Cook’s Theorem17.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 Problems17.11.1 Example—an intractable SAT17.12 Even Harder Problems17.13 Unreasonable Requirements of Memory17.14 Complexity Classes and Intractability17.15 Non-Computability and Undecidability17.16 Algorithmic Program Verification17.16.1 Halting Problem (HP)17.17 Partially and Highly Undecidable Problems17.18 The Four Levels of Algorithmic BehaviourSummaryKey TermsWeb Resources
Chapter 18. Some NP and NP-Complete Problems
18.1 Introduction18.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 languages18.3 Reductions18.3.1 Definition of reductions18.3.2 Reduction in P18.3.3 Transitivity of reductions18.3.4 NP-completeness to NP = P18.3.5 Circuit satisfiability problem18.3.6 Reductions in NPC18.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 problem18.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 set18.5 Certificates and VerificationSummaryKey TermsExercisesWeb Resources
Chapter 19. Randomized and Approximate Algorithms
19.1 Introduction19.2 Randomized Algorithms19.2.1 Reasons for using randomized algorithms19.2.2 Background—Review of probability theory19.2.3 Examples19.2.4 Generation of large prime numbers19.3 Randomized Complexity Classes19.3.1 RP: Randomized polynomial time19.3.2 co-RP: Complement of RP19.3.3 ZPP: Zero-error probabilistic polynomial time19.3.4 BPP: Bounded-error probabilistic polynomial time19.4 Approximate Algorithms19.4.1 NP-hard optimization problems19.4.2 Examples—approximation algorithms19.4.3 Analysis of approximation algorithms19.4.4 Traveling salesman problem19.4.5 Colouring 3-colourable graphs19.4.6 Decision problems19.4.7 Approximation algorithms19.4.8 Approximation of TSPSummaryKey TermsExercisesWeb Resources
Chapter 20. Formal Specifications—1 Model Oriented
20.1 Formal Specifications20.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 VDM20.2.1 The implicit specification of operations20.2.2 Examples of implicit specifications20.2.3 The logical condition20.2.4 Reasoning with pre- and post-conditions20.2.5 Introduction to VDM data types20.2.6 The primitive types20.2.7 The set type20.2.8 Implicit definition of sets20.2.9 Creating VDM state models20.2.10 Composites20.3 A Systematic Approach to the Construction of VDM Specifications20.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 refinement20.3.6 Formal proof obligations20.3.7 Recapitulation20.4 The Sequence and Map Types20.4.1 The sequence data type20.4.2 The map data type20.4.3 A small exampleSummaryKey TermsExercisesWeb Resources
Chapter 21. Formal Specifications—2 Algebraic
21.1 Introduction21.1.1 Specification of abstract data types21.1.2 Algebraic specification of abstract data types21.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 rewriting21.2.5 Pattern matching and unificationSummaryKey TermsExercisesWeb Resources
Appendix A. Essential Mathematical Background
A.1 What is Discrete Mathematics?A.2 Formal Logic: A Language for MathematicsA.2.1 Assertions and propositionsA.2.2 Logical connectivesA.2.3 Tautologies, contradictions, and contingenciesA.2.4 Proof techniquesA.2.5 PredicatesA.2.6 QuantifiersA.2.7 Free and bound variablesA.2.8 Implications and equivalencesA.2.9 Classification of assertions in predicate logicA.2.10 Inference rules in predicate logicA.3 SetsA.3.1 Notations for setsA.3.2 Relationships between setsA.3.3 Set operationsA.3.4 Properties of setsA.3.5 FunctionsA.3.6 Operations on functionsA.3.7 Classification of total functionsA.3.8 Cardinality of a setA.3.9 Sequences and seriesA.4 Asymptotic NotationsA.5 Number TheoryA.5.1 LCM and GCDA.5.2 Primes and factorizationA.5.3 Congruences and modular arithmeticA.5.4 Applications of mathematics in computer scienceA.6 Formal LanguagesA.6.1 StringsA.6.2 Binary operation on stringsA.6.3 Relationships between stringsA.6.4 Inductive definitionsA.6.5 LanguagesA.6.6 Binary operation on languagesA.6.7 Power X1 of a language XA.6.8 Closure of a languageA.7 Proof by InductionA.7.1 First principle of mathematical inductionA.7.2 Second principle of mathematical inductionA.8 Introduction to combinatoricsA.8.1 Principles of combinatoricsA.8.2 Choosing elements from setsA.8.3 PermutationsA.8.4 Multiset (or bag)A.8.5 Permutations in circular orderA.8.6 SamplesA.8.7 CombinationsA.8.8 SelectionsA.8.9 Pigeonhole principle or Dirichlet Drawer principleA.9 Random VariablesA.9.1 Discrete distribution functionsA.9.2 Expected valuesA.9.3 Variance and standard deviationA.9.4 Central limit theoremA.10 RelationsA.10.1 Binary relations and digraphsA.10.2 Classification of binary relationsA.10.3 Operations on relationsA.10.4 Equivalence relations and equivalence classesA.10.5 PartitionsA.10.6 Order relationsA.10.7 Upper bounds and lower boundsA.11 Graph TheoryA.11.1 Directed graph or digraphA.11.2 Undirected graphsA.11.3 TreesA.11.4 Matrix representations of graphsExercises
Appendix B. Some Useful Mathematical Formulae
B.1 DefinitionsB.2 SumsB.3 IdentitiesB.4 TreesB.5 RecurrencesB.5.1 Generating functionsB.6 Some ConstantsB.7 GeneralB.8 TrigonometryB.9 Number TheoryB.10 Graph TheoryB.10.1 DefinitionsB.10.2 NotationsB.11 Value Of πB.12 Partial FractionsB.13 CalculusB.13.1 DerivativesB.13.2 IntegralsB.13.3 Finite calculusB.14 Series
Appendix C. Overview of Essential Data Structures
C.1 IntroductionC.2 Primitive Data StructuresC.3 Arrays and ListsC.3.1 Linked storageC.3.2 Pointers and linked allocationC.3.3 Linked linear listC.3.4 Operations on linked listsC.3.5 Circularly linked linear listsC.3.6 Doubly linked linear listsC.4 StacksC.4.1 Operations on stacksC.5 QueuesC.5.1 Circular queuesC.5.2 Double ended queuesC.6 Priority QueuesC.7 TreesC.7.1 Operations on a binary treeC.7.2 Storage representation and manipulationC.7.3 Linked storageC.7.4 Threaded storageC.8 Binary Search TreesC.8.1 SearchingC.8.2 Binary search treesC.8.3 Analysis of binary search treesC.8.4 Balanced binary trees and AVL treesC.9 Skip ListsC.9.1 ShortcutsC.9.2 Skip listsC.9.3 ImplementationC.10 Hash TablesC.10.1 Hash functionsC.10.2 Collision resolutionC.11 GraphsC.11.1 Matrix representationC.12 Linked List-Structure
Appendix D. Solutions of Recurrence Relations
D.1 IntroductionD.2 PreliminariesD.2.1 Sequences and generating functionsD.2.2 Characteristic polynomialD.2.3 Recurrence systemsD.2.4 Solutions of recurrence systemsD.2.5 Classification of recurrence systemsD.2.6 Uniqueness of a solution to a linear recurrence systemD.2.7 Principle of superpositionD.3 Methods of Solution of Recurrence RelationsD.3.1 Method of iterationD.3.2 Method of substitutionD.3.3 Using Master TheoremD.3.4 Method of generating functionD.3.5 Method of characteristic rootsD.3.6 Method of undetermined coefficientsD.3.7 Higher-order recurrence systemsD.4 Algorithm Analysis by Recurrence RelationsD.4.1 Tower of HanoiD.4.2 A Nested loop programD.4.3 Divide and conquerD.5 ExamplesD.5.1 A frequently occurring form
Appendix E Additional Exercises with Solutions
E.1 Additional ExercisesE.1.1 Chapter 4: Loop design issuesE.1.2 Chapter 6: Proof rule basicsE.1.3 Chapter 7: Design by proof rulesE.1.4 Chapter 9: Divide and conquerE.1.5 Chapter 10: Greedy methodsE.1.6 Chapter 11: Dynamic orogrammingE.1.7 Chapter 14: Efficiency of algorithmsE.1.8 Chapter 15: Complexity calculationE.1.9 Chapter 17: Tractable and non-tractable problemsE.1.10 Chapter 18: Some NP and NPC problemsE.1.11 Chapter 19: Approximate solutionsE.1.12 Appendix D: Solutions of recurrence relationsE.2 Hints and SolutionsE.2.1 Chapter 4: Loop design issuesE.2.2 Chapter 6: Proof rules basicE.2.3 Chapter 7: Design by proof rulesE.2.4 Chapter 9: Divide and conquerE.2.5 Chapter 10: Greedy algorithmsE.2.6 Chapter 11: Dynamic programmingE.2.7 Chapter 14: Efficiency of algorithmsE.2.8 Chapter 15: Complexity calculationsE.2.9 Chapter 17: Tractable and non-tractable problemsE.2.10 Chapter 18: Some NP and NPC problemsE.2.11 Chapter 19: Approximate solutionsE.2.12 Appendix D: Solutions of recurrence relations
Bibliography
Notes
Copyright
Back Cover

Content preview from Design and Analysis of Algorithms

Chapter 18 Some NP and NP-Complete Problems

Objectives

After reading this chapter, you should understand:

A few important Real Life NP-Hard and NP-Complete Problems in detail
An Informal definition of NP-Hardness and NP-Completeness
P and NP classes in terms of the Turing Machine
Reducibility of problems so that NP Completeness can be proven
How to use the notion of reducibility to prove NP-Completeness for several Classical Problems

Chapter Outline

18.1 Introduction

18.1.1 NP-Hardness

18.1.2 NP-Completeness

18.1.3 Consequences of being in P

18.1.4 Reduction Source Problems

18.2 Turing Machine (TM)

18.2.1 Relation between Problems and Languages

18.2.2 Decision Problems and Languages

18.3 Reductions

18.3.1 Definition of Reductions

18.3.2 Reduction ...

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: 9788177585957

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Design and Analysis of Algorithms

by Parag H. Dave, Himanshu B. Dave

Chapter 18