Cover -- Design and Analysis of Algorithms -- Copyright -- Preface -- Brief Contents -- Contents -- Timeline of Algorithms -- Algorithm Design -- Introduction -- Objectives -- Basic Concerns -- Relationship Between Algorithms and other Aspects of Software -- The Evolution of Algorithm -- Summary -- Key Terms -- Exercises -- Web Resources -- Problem Solving with a Computer -- Objectives -- Introduction -- Solving a Problem with a Computer -- Statement of the Problem or Problem Definition -- Development of a Model -- Design of the Algorithm -- Checking the Correctness of the Algorithm -- Implementation in Some Programming Language -- Analyze and Study the Complexity of the Algorithm -- Program Testing-Debugging and Profiling -- Documentation preparation -- Some More Examples -- Finding the square root of a number -- Smallest divisor of an integer number -- Generation of prime numbers -- Generation of pseudo-random numbers -- Problem Solving in General -- The STAIR steps for solving problems -- Problem solving as applied to numerical algorithms -- Reduction to known problems -- Strategy if we are stuck -- Summary -- Key Terms -- Exercises -- Web Resources -- Top-Down Design -- Objectives -- Introduction -- Structured Programming -- Control Constructs -- If-Then-Else -- For-Do -- Case -- Repeat-Until -- While-Do -- Goto and ExitLoop -- Procedures and Functions -- Recursion -- Order of Execution of Statements in a Recursive Function -- Summary -- Key Terms -- Exercises -- Web Resources -- Iterative Algorithm Design Issues -- Objectives -- Introductio -- Use of Loops -- Efficiency of Algorithms -- Removing Redundant Computations Outside Loops -- Referencing of Array Elements -- Inefficiency Due to Late Termination -- Early Detection of Desired Output Conditions -- Estimating and Specifying Execution Times.

Justification for the Use of Problem Size as a Measure -- Computational Cost as a Function of Problem Size for a range of Computational complexities -- Order Notation -- Big-Oh notation -- Theta notation -- Omega Notation -- Small-oh Notation -- (S}(B Notation -- Measuring the Execution Times -- Other Trade-offs -- Algorithm Strategies -- Summary -- Key Terms -- Exercises -- Web Resources -- Computation Models and Design by Refinement -- Objectives -- Introduction -- Functional Model -- Features of Functional Model -- Recursive Processes -- Analysis of Correctness and Efficiency -- More Examples of Recursive Algorithms -- Scope Rules -- Tail-Recursion and Iterative Processes -- Correctness of an Iterative Process -- More Examples of Iterative Processes -- Imperative Model -- The Primitives for the Imperative Model -- Specifications and Prototyping -- Examples of Step-wise Refinement -- Summary -- Key Terms -- Exercises -- Web Resources -- Proof Rules-Basics -- Objectives -- Introduction -- Computer Model for Program Execution -- Assertions at Input and Output of Blocks -- Symbolic Execution -- Proof Rules -- Compound Statements -- Conditional Statements -- Case Statements -- Repetitive Statements -- Repeat-Until Statement -- Example: The Division Algorithm -- Correct Termination of Algorithms -- Proof Rules for more Advanced Constructs -- For Loops -- GoTo and ExitLoop -- Program Transformation -- Functions and Procedures -- Recursive Functions -- Summary -- Key Terms -- Exercises -- Web Resources -- Design by Proof Rules -- Objectives -- A Fresh Look at Proof Rules -- Referring to Previous Values of Variables -- Proof Rules -- Designing Correct Programs -- The Interface Specification -- Applying the Rules to Deduce the Program Statement Types -- Design Example -- Design of a Loop -- Loop Termination.

A Simple Design Procedure for Loops Based on Proof-Rules -- Example 1: Linear Search -- Example 2: Linear Search without Assurance -- Example 3: Searching a 2-D Array -- Example: Selection Sort -- Example: Partition -- Summary -- Key Terms -- Exercises -- Web Resources -- Design Using Recursion -- Objectives -- Introduction -- Execution Trace -- Regular Expressions -- An Interesting Recursive Function -- Another Look at Iteration and Recursion -- Summary -- Key Terms -- Exercises -- Web Resources -- Abstract Algorithms-1-Divide-and-Conquer -- Objectives -- Introduction -- A Multiplication Algorithm -- Analysis of the Multiplication Algorithm -- Application to Graphics Algorithms -- Introduction to Triangulation -- Convex Hulls -- Where D & C Fails -- Characteristics of Problems for which D & C is Unsuitable -- Timing Analysis -- Summary -- Key Terms -- Exercises -- Web Resources -- Abstract Algorithms 2-Greedy Methods -- Objectives -- Introduction -- Example-Knapsack Problem -- Job Sequencing with Deadlines -- Example-Minimum Spanning Trees -- Prim's Algorithm -- Kruskal's Algorithm -- 1st Version-Kruskal.c -- Union-Find Data-Structure -- Tree-Based Disjoint sets and the Quick-Union Algorithm -- Implementing Quick-Union with an Array -- Complexity Analysis of Quick-Union -- Using Union-find in Kruskal Algorithm -- Matroids -- Correctness of Kruskal's Algorithm -- Example [Shortest Path] -- Dijkstra's Shortest Path Algorithm -- Summary -- Key Terms -- Exercises -- Web Resources -- Abstract Algorithms 3-Dynamic Programming -- Objectives -- Introduction -- Example-Multistage Graphs -- Example-Traveling Salesman -- Example-Matrix Multiplication -- Brute Force Solution-Try all Possible Parenthesisations -- Dynamic Programming -- Example-Longest Common Sub-sequence -- Brute Force Method -- Dynamic Programming -- Example-Optimal Polygon Triangulation.

Problem -- Single Source Shortest Paths -- Shortest Paths Problem -- Shortest Paths Tree -- All-Pairs Shortest Paths -- Maximum Flow Problems -- Flow Networks -- Maximum-Flow Problem -- Analysis of Ford-Fulkerson Algorithm -- Conclusion -- Summary -- Key Terms -- Exercises -- Web Resources -- Abstract Algorithms 4-Backtracking -- Objectives -- Combinatorial Search -- Search and Traversal -- Breadth First Search -- Depth First Search -- The Backtracking Strategy -- Example 1: 8-Queens Problem -- Backtracking Framework -- Efficiency of Backtracking -- Example 2: M-Colouring Problem -- Example 3: Hamiltonian Circuits -- Some Typical State Spaces -- Constructing all Subsets -- Constructing all Permutations -- Constructing all Paths in a Graph -- Bandwidth Minimization -- Covering Chess Boards -- Convex Hull -- Summary -- Key Terms -- Exercises -- Web Resources -- Natural Algorithms-GA, SA, ANN, TS -- Objectives -- Introduction -- Evolutionary Algorithms and Evolutionary Computing -- Genetic Algorithms -- An example problem -- Observations -- Simulated Annealing -- Sample implementation -- Artificial Neural Networks -- Analogy to the Brain -- How they Work? -- Electronic Implementation of Artificial Neurons -- Artificial Network Operations -- Training an Artificial Neural Network -- Feed-Forward Network -- Hopfield Feedback Connected Neural Network -- How Neural Networks Differ from Traditional Computing and Expert Systems -- Artificial neural network applications -- Tabu Search -- Application Domain -- The Reactive Tabu Search -- Summary -- Key Terms -- Web Resources -- Algorithm Analysis -- Efficiency of Algorithms -- Objectives -- Polynomial-Time and Non-Polynomial-Time Algorithms -- Worst and Average Case Behaviour -- Probabilistic Average Case Analysis -- Time Analysis of Algorithms -- Example-Matrix Multiplication -- More Timing Analysis.

Efficiency of Recursion -- Complexity -- The Notion of Complexity -- Profiling -- Suppressing Multiplicative Constants -- Counting Dominant Operations -- Growth-Rate -- Upper Bounds -- Asymptotic Growth-Rate -- The 'O' Notation -- Discussion -- Simplified Definition of 'O' -- 'O' Notation Rules -- Analyzing Growth of Exotic Functions -- Derivative Rule -- Order-of-Magnitude Comparisons -- Doubling Comparisons -- Estimating Complexity Experimentally -- Experimental comparison of sorting procedures -- Key Terms -- Summary -- Exercises -- Web Resources -- Examples of Complexity Calculation -- Objectives -- Examples from the Sorting World -- Bucket Sort -- Radix Sort -- Simple Insertion Sort -- Quick Sort -- Heap sort-using a Tree to Sort -- Merge Sort -- Summary of Complexity and Characteristics of Sorting Algorithms -- Complexity of Set Operations and Mappings -- Sets Implementation Using an Unordered Array -- Binary Search Principle -- Binary Search Trees -- Bit Vectors -- Analysis Of Hashing -- The Trie Principle -- Sets vs. Bags and Mappings -- Amortized Analysis -- Potential Functions -- Example-Binary, Binomial And Fibonacci Heaps -- Binomial Heap -- Fibonacci Heap -- Dijkstra's Shortest-Path Algorithm -- Analysis -- Splay Trees -- Basics Of Splay Trees -- Splay Operation -- Amortized Timing Analysis -- Summary -- Key Terms -- Exercises -- Web Resources -- Time-Space Trade-off -- Objectives -- Introduction -- An Example Of Time-Space Trade-Off -- A Quick Review of Complexity -- Time-Space Trade-Off -- Some Simple Examples -- Time-Space Trade-Off in Algorithm Research -- Case Study-Perrin Numbers -- Perrin Numbers -- First Try-Straight-Forward Implementation -- Second Try-Dynamic Programming -- Third Try-Reduction And Divide & Conquer -- The Final Results -- Summary -- Key Terms -- Exercises -- Web Resources -- Tractable and Non-tractable Problems.

Objectives.

Design and Analysis of Algorithms is the outcome of teaching, research and consultancy done by the authors over more than two decades. All aspects pertaining to algorithm design and algorithm analysis have been discussed over the chapters.

Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2018. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.