Design and Analysis of Algorithms

Description

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 ω 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 Introduction Upper and Lower Bounds Algorithmic Gap Efficiency and Tractability Problem Description A quick and Operating Definition of NP-Complete Problems Some known NP-Complete Problems What is a Certificate? Non-Deterministic Algorithms NP-Completeness Polynomial Time Reductions Problem Classes P, NP, and Others Bounded Halting is in NPC Cook’s Theorem An Example Reduction To SAT Examples of Problems in Different Classes Is P = NP? Np-Completeness How to Prove NP-Completeness in Practice Primality test Approximate Solutions to NPC Problems Provably Intractable Problems Example—an Intractable SAT Even Harder Problems Unreasonable Requirements of Memory Complexity Classes and Intractability Non-Computability and Undecidability Algorithmic Program Verification Halting Problem Partially and Highly Undecidable Problems The Four Levels of Algorithmic Behaviour Summary Key Terms Web Resources Some NP and NP-Complet e Problems Objectives Introduction NP-Hardness NP-Completeness Consequences of Being in P Reduction Source Problems Turing Machine Relation Between Problems And Languages Decision Problems And Languages Reductions Definition of reductions Reduction in P Transitivity Of Reductions NP-completeness to NP = P Circuit Satisfy Ability Problem Reductions in NPC Steps for Proving NP-Completeness Reductions for Some Known Problems Propositional Formulae SAT Problem Conjunctive Normal Form (3-Cnf)-SAT Problem Cliques Of A Graph Vertex Cover Hamiltonian Cycle Traveling Salesman Problem Independent Set Certificates and Verification Summary Key Terms Exercises Web Resources Randomized and Approximate Algorithms Objectives Introduction Randomized Algorithms Reasons for Using Randomized Algorithms Background—Review Of Probability Theory Examples Generation Of Large Prime Numbers Randomized Complexity Classes RP: Randomized Polynomial Time co-RP: Complement of RP ZPP: Zero-Error Probabilistic Polynomial Time BPP: Bounded-Error Probabilistic Polynomial Time Approximate Algorithms NP-Hard Optimization Problems Examples—Approximation Algorithms Analysis Of Approximation Algorithms Traveling Salesman Problem Colouring 3-Colourable Graphs Decision Problems Approximation Algorithms Approximation of TSP Summary Key Terms Exercises Web Resources Formal Specifications—1 Model Oriented Objectives Formal Specifications A First Specification Language What is a Software Specification? What is a Formal Specification? An Apparent Disadvantage of FSL Introduction to VDM The Implicit Specification of Operations Examples of Implicit Specifications The Logical Condition Reasoning with pre- and post-conditions Introduction to VDM Data Types The Primitive Types The Set Type Implicit Definition of Sets Creating VDM State Models Composites A Systematic Approach to the Construction of VDM Specifications Creation of a System State Construction of Data Type Invariants Modeling of the System’s Operations Discharging Proof Obligations Specifi cation Refi nement Formal Proof Obligations Recapitulation The Sequence and Map Types The Sequence Data Type The Map Data Type A Small Example Summary Key Terms Exercises Web Resources Formal Specifications—2 Algebraic Objectives Introduction Specification of Abstract Data Types Algebraic Specification of Abstract Data Types An Algebraic Specification Language An Algebraic Specification Language Comparison with VDM Completeness Examples of Evaluations Axioms and Term Rewriting Pattern Matching and Unification Summary Key Terms Exercises Web Resources Appendices Essential Mathematical Background What is Discrete Mathematics? Formal Logic: A Language for Mathematics Assertions And Propositions Logical Connectives Tautologies, Contradictions, and Contingencies Proof Techniques Predicates Quantifiers Free and Bound Variables Implications and Equivalences Classification of Assertions in Predicate Logic Inference Rules in Predicate Logic Sets Notations for Sets Relationships Between Sets Set Operations Properties of Sets Functions Operations on Functions Classification of Total Functions Cardinality of a Set Sequences and Series Asymptotic Notations Number Theory LCM and GCD Primes and Factorization Congruences and Modular Arithmetic Applications of Mathematics in Computer Science Formal Languages Strings Binary Operation on Strings Relationships between Strings Inductive Definitions Languages Binary Operation on Languages Power Xi of a Language X Closure of a Language Proof by Induction First Principle of Mathematical Induction Second Principle of Mathematical Induction Second Principle of Mathematical Induction Principles of Combinatorics Choosing Elements from Sets Permutations Multiset (or Bag) Permutations in Circular Order Samples Combinations Selections Pigeonhole Principle or Dirichlet Drawer Principle Random Variables Discrete Distribution Functions Expected Values Variance and Standard Deviation Central Limit Theorem Relations Binary Relations and Digraphs Classification of Binary Relations Operations on Relations Equivalence Relations and Equivalence Classes Partitions Order Relations Upper Bounds and Lower Bounds Graph Theory Directed Graph or Digraph Undirected Graphs Trees Matrix Representations of Graphs Exercises Some Useful Mathematical Formulae Definitions Sums Identities Trees Recurrences Generating Functions Some Constants General Trigonometry Number Theory Graph Theory Definitions Notations Value Of π Partial Fractions Calculus Derivatives Integrals Finite Calculus Series Overview of Essential Data Structures Introduction Primitive Data Structures Arrays and Lists Linked Storage Pointers and Linked Allocation Linked Linear List Operations on Linked Lists Circularly Linked Linear Lists Doubly Linked Linear Lists Stacks Operations on Stacks Queues Circular Queues Double Ended Queues Priority Queues Trees Operations on a Binary Tree Storage Representation and Manipulation Linked Storage Threaded Storage Binary Search Trees Searching Binary Search Trees Analysis of Binary Search Trees Balanced Binary Trees and AVL Trees Skip Lists Shortcuts Skip Lists Implementation Hash Tables Hash Functions Collision Resolution Graphs Matrix Representation Linked List-Structure Solutions of Recurrence Relations Introduction Preliminaries Sequences and Generating Functions Characteristic Polynomial Recurrence Systems Solutions of Recurrence Systems Classification of Recurrence Systems Uniqueness of a Solution to a Linear Recurrence System Principle of Superposition Methods of Solution of Recurrence Relations Method of Iteration Method of Substitution Using Master Theorem Method of Generating Function Method of Characteristic Roots Method of Undetermined Coefficients Higher-Order Recurrence Systems Algorithm Analysis by Recurrence Relations Tower of Hanoi A Nested Loop Program Divide and Conquer Examples A Frequently Occurring Form Additional Exercises with Solutions Additional Exercises Chapter 4: Loop Design Issues Chapter 6: Proof Rule Basics Chapter 7: Design by Proof Rules Chapter 9: Divide and Conquer Chapter 10: Greedy Methods Chapter 11: Dynamic Programming Chapter 14: Effi ciency of Algorithms Chapter 15: Complexity Calculation Chapter 17: Tractable and Non-Tractable Problems Chapter 18: Some NP and NPC Problems Chapter 19: Approximate Solutions Appendix D: Solutions of Recurrence Relations Hints and Solutions Chapter 4: Loop Design Issues Chapter 6: Proof Rules Basic Chapter 7: Design by Proof Rules Chapter 9: Divide and Conquer Chapter 10: Greedy Algorithms Chapter 11: Dynamic Programming Chapter 14: Effi ciency of Algorithms Chapter 15: Complexity Calculations Chapter 17: Tractable and Non-Tractable Problems Chapter 18: Some NP and NPC Problems Chapter 19: Approximate Solutions Appendix D: Solutions of Recurrence Relations Bibliography Index