An Elementary Approach To Design And Analysis Of Algorithms

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