An Elementary Approach To Design And Analysis Of Algorithms (Primers In Electronics And Computer Science): 4

Description

In computer science, an algorithm is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculation, data processing and automated reasoning tasks. As an effective method, an algorithm can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input. This book introduces a set of concepts in solving problems computationally such as Growth of Functions; Backtracking; Divide and Conquer; Greedy Algorithms; Dynamic Programming; Elementary Graph Algorithms; Minimal Spanning Tree; Single-Source Shortest Paths; All Pairs Shortest Paths; Flow Networks; Polynomial Multiplication, to ways of solving NP-Complete Problems, supported with comprehensive, and detailed problems and solutions, making it an ideal resource to those studying computer science, computer engineering and information technology. Contents Preface About the Authors Chapter 1. Algorithms 1.1. Some Sorting Algorithms 1.1.1. Bubble sort 1.1.2. Insertion sort 1.1.3. Selection sort 1.1.4. Quick sort 1.2. Algorithm Performance/Algorithm Complexity 1.3. Heap Sort Exercise 1.1 Chapter 2. Growth of Functions 2.1. Introduction 2.2. Asymptotic Notations 2.2.1. O-notation (big oh notation) 2.2.2. Ω-notation (big omega notation) 2.2.3. θ-notation (big theta notation) 2.3. Some Asymptotic Notations Using Limits Exercise 2.1 2.4. Asymptotic Notations in Equations 2.5. Comparison of Growth of Some Typical Functions Exercise 2.2 Exercise 2.3 2.6. Some Typical Examples Exercise 2.4 Chapter 3. Backtracking 3.1. Backtracking Procedure 3.2. Graph Coloring 3.3. n-Queen Problem 3.4. n-Queen Problem and Permutation Tree 3.5. Solving Sudoku Problem Using Backtracking Exercise 3.1 Chapter 4. Divide and Conquer 4.1. Divide and Conquer General Algorithm 4.2. Max–Min Problem 4.3. Round-Robin Tennis Tournament 4.4. The Problem of Counterfeit Coin 4.5. Tiling a Defective Chess Board with Exactly One Defective Square Using Triominoes 4.6. Strassen’s Matrix Multiplication Algorithm 4.7. Medians and Order Statistic 4.7.1. Worst-case running time of select (order statistic) Exercise 4.1 Chapter 5. Greedy Algorithms 5.1. Some Examples 5.2. Knapsack Problem 5.3. Job Sequencing with Deadlines 5.4. Huffman Code Exercise 5.1 Chapter 6. Dynamic Programming 6.1. Matrix-Chain Multiplication 6.2. Multistage Graphs 6.3. A Business/Industry Oriented Problem 6.4. Largest Common Subsequence 6.5. Optimal Binary Search Tree Exercise 6.1 6.6. Optimal Triangulation of a Polygon Exercise 6.2 Exercise 6.3 Chapter 7. Elementary Graph Algorithms 7.1. Representations of Graphs 7.2. Queues Exercise 7.1 7.3. Shortest Paths 7.4. Breadth-First Search Exercise 7.2 7.4.1. Breadth-first tree Exercise 7.3 7.5. Depth-First Search 7.6. Directed Acyclic Graphs 7.6.1. Topological sort 7.7. Strongly Connected Components Exercise 7.4 Chapter 8. Minimal Spanning Tree 8.1. Prim’s Algorithm 8.2. Kruskal’s Algorithm 8.3. Some Examples Exercise 8.1 Chapter 9. Single-Source Shortest Paths 9.1. Preliminaries 9.2. Dijkstra’s Algorithm 9.3. Bellman–Ford Algorithm Exercise 9.1 9.4. Predecessor Subgraph 9.5. Difference Constraints and Shortest Paths Exercise 9.2 Chapter 10. All Pairs Shortest Paths 10.1. A Recursive Algorithm for Shortest Path Lengths 10.2. The Floyd–Warshall Algorithm 10.2.1. Construction of a shortest path 10.3. Transitive Closure Exercise 10.1 10.4. Johnson’s Algorithm Exercise 10.2 Chapter 11. Flow Networks 11.1. Ford and Fulkerson Theorem 11.2. Labeling Procedure for Maximal Flow and Flow Pattern 11.3. Maximum Bipartite Matching Exercise 11.1 Exercise 11.2 Chapter 12. Polynomial Multiplication, FFT and DFT 12.1. Evaluation of a Polynomial 12.2. Discrete Fourier Transforms and Polynomial Multiplication 12.2.1. Representation of polynomials 12.3. Primitive Roots of Unity 12.4. Discrete Fourier Transforms Exercise 12.1 Chapter 13. String Matching 13.1. Preliminaries 13.2. The Naïve String-Matching Algorithm 13.3. The Rabin–Karp Algorithm Exercise 13.1 13.4. Pattern-Matching with Finite Automata Exercise 13.2 13.5. The Knuth–Morris–Pratt Algorithm 13.5.1. Some auxiliary functions 13.5.2. The KMP procedure Chapter 14. Sorting Networks 14.1. Comparison Networks 14.2. Batcher’s Odd–Even Mergsort Exercise 14.1 14.3. The Zero-One Principle 14.4. A Bitonic Sorting Network Exercise 14.2 Exercise 14.3 14.5. Another Merging Network 14.6. A Sorting Network Exercise 14.4 Chapter 15. NP-Complete Problems 15.1. Classes P, NP and NP-Complete 15.2. Optimization Problems as Decision Problems 15.3. Reducibility or Reductions Exercise 15.1 15.4. Some NP-Complete Problems Exercise 15.2 Bibliography Index