Elementary Approach To Design And Analysis Of Algorithms, An

Description

‘The book under review is an interesting elaboration that fills the gaps in libraries for concisely written and student-friendly books about essentials in computer science … I recommend this book for anyone who would like to study algorithms, learn a lot about computer science or simply would like to deepen their knowledge … The book is written in very simple English and can be understood even by those with limited knowledge of the English language. It should be emphasized that, despite the fact that the book consists of many examples, mathematical formulas and theorems, it is very hard to find any mistakes, errors or typos.’ zbMATHIn 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.

Table of Contents

1. Cover
2. Halftitle
3. Series
4. Title
5. Copyright
6. Dedication
7. Preface
8. About the Author
9. Contents
10. Chapter 1. Algorithms
    1. Some Sorting Algorithms
    2. Bubble sort
    3. Insertion sort
    4. Selection sort
    5. Quick sort
    6. Algorithm Performance/Algorithm Complexity
    7. Heap Sort
    8. Exercise 1.1
11. Chapter 2. Growth of Functions
    1. Introduction
    2. Asymptotic Notations
    3. O-notation (big oh notation)
    4. Ω-notation (big omega notation)
    5. θ-notation (big theta notation)
    6. Some Asymptotic Notations Using Limits
    7. Exercise 2.1
    8. Asymptotic Notations in Equations
    9. Comparison of Growth of Some Typical Functions
    10. Exercise 2.2
    11. Exercise 2.3
    12. Some Typical Examples
    13. Exercise 2.4
12. Chapter 3. Backtracking
    1. Backtracking Procedure
    2. Graph Coloring
    3. n-Queen Problem
    4. n-Queen Problem and Permutation Tree
    5. Solving Sudoku Problem Using Backtracking
    6. Exercise 3.1
13. Chapter 4. Divide and Conquer
    1. Divide and Conquer General Algorithm
    2. Max–Min Problem
    3. Round-Robin Tennis Tournament
    4. The Problem of Counterfeit Coin
    5. Tiling a Defective Chess Board with Exactly One Defective Square Using Triominoes
    6. Strassen’s Matrix Multiplication Algorithm
    7. Medians and Order Statistic
    8. Worst-case running time of select (order statistic)
    9. Exercise 4.1
14. Chapter 5. Greedy Algorithms
    1. Some Examples
    2. Knapsack Problem
    3. Job Sequencing with Deadlines
    4. Huffman Code
    5. Exercise 5.1
15. Chapter 6. Dynamic Programming
    1. Matrix-Chain Multiplication
    2. Multistage Graphs
    3. A Business/Industry Oriented Problem
    4. Largest Common Subsequence
    5. Optimal Binary Search Tree
    6. Exercise 6.1
    7. Optimal Triangulation of a Polygon
    8. Exercise 6.2
    9. Exercise 6.3
16. Chapter 7. Elementary Graph Algorithms
    1. Representations of Graphs
    2. Queues
    3. Exercise 7.1
    4. Shortest Paths
    5. Breadth-First Search
    6. Exercise 7.2
    7. Breadth-first tree
    8. Exercise 7.3
    9. Depth-First Search
    10. Directed Acyclic Graphs
    11. Topological sort
    12. Strongly Connected Components
    13. Exercise 7.4
17. Chapter 8. Minimal Spanning Tree
    1. Prim’s Algorithm
    2. Kruskal’s Algorithm
    3. Some Examples
    4. Exercise 8.1
18. Chapter 9. Single-Source Shortest Paths
    1. Preliminaries
    2. Dijkstra’s Algorithm
    3. Bellman–Ford Algorithm
    4. Exercise 9.1
    5. Predecessor Subgraph
    6. Difference Constraints and Shortest Paths
    7. Exercise 9.2
19. Chapter 10. All Pairs Shortest Paths
    1. A Recursive Algorithm for Shortest Path Lengths
    2. The Floyd–Warshall Algorithm
    3. Construction of a shortest path
    4. Transitive Closure
    5. Exercise 10.1
    6. Johnson’s Algorithm
    7. Exercise 10.2
20. Chapter 11. Flow Networks
    1. Ford and Fulkerson Theorem
    2. Labeling Procedure for Maximal Flow and Flow Pattern
    3. Maximum Bipartite Matching
    4. Exercise 11.1
    5. Exercise 11.2
21. Chapter 12. Polynomial Multiplication, FFT and DFT
    1. Evaluation of a Polynomial
    2. Discrete Fourier Transforms and Polynomial Multiplication
    3. Representation of polynomials
    4. Primitive Roots of Unity
    5. Discrete Fourier Transforms
    6. Exercise 12.1
22. Chapter 13. String Matching
    1. Preliminaries
    2. The Naïve String-Matching Algorithm
    3. The Rabin–Karp Algorithm
    4. Exercise 13.1
    5. Pattern-Matching with Finite Automata
    6. Exercise 13.2
    7. The Knuth–Morris–Pratt Algorithm
    8. Some auxiliary functions
    9. The KMP procedure
23. Chapter 14. Sorting Networks
    1. Comparison Networks
    2. Batcher’s Odd–Even Mergsort
    3. Exercise 14.1
    4. The Zero-One Principle
    5. A Bitonic Sorting Network
    6. Exercise 14.2
    7. Exercise 14.3
    8. Another Merging Network
    9. A Sorting Network
    10. Exercise 14.4
24. Chapter 15. NP-Complete Problems
    1. Classes P, NP and NP-Complete
    2. Optimization Problems as Decision Problems
    3. Reducibility or Reductions
    4. Exercise 15.1
    5. Some NP-Complete Problems
    6. Exercise 15.2
    7. Bibliography
    8. Index