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.
Author(s): Lekh Raj Vermani, Shalini Vermani
Series: Primers In Electronics And Computer Science, 4
Publisher: World Scientific Europe
Year: 2019
Language: English
Pages: 536
City: London
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
