The Art of Algorithm Design

Cover
Half Title
Title Page
Copyright Page
Dedication
Table of Contents
Preface
Authors
Chapter 1 Fundamental Concepts of Data Structure
	1.1 ARRAY
		1.1.1 Array Element in Memory
		1.1.2 Initialization
		1.1.3 Retrieving and Storing Some Values from/into the  Array
	1.2 STACK
		1.2.1 Algorithm for Push Operation
		1.2.2 Algorithm for Pop Operation
		1.2.3 Algorithm for Traverse Operation
		1.2.4 Algorithm for Peep Operation
		1.2.5 Algorithm for Update Operation
	1.3 QUEUE
		1.3.1 Algorithm for Insert Operation
		1.3.2 Algorithm for Delete Operation
		1.3.3 Algorithm for Traverse Operation
		1.3.4 Algorithm for Peep Operation
		1.3.5 Algorithm for Update Operation
	1.4 LINKED LIST
		1.4.1 Single Link List
			1.4.1.1 Structure of the Node of a Linked List
	1.5 TREE
		1.5.1 Questions
Chapter 2 Concepts of Algorithms and Recurrences
	2.1 ALGORITHM
	2.2 DESIGN OF ALGORITHMS
	2.3 ALGORITHMIC NOTATIONS
		2.3.1 Calculation for Method Calls
	2.4 GROWTH OF FUNCTION
		2.4.1 Asymptotic Notations
		2.4.2 O – Notation (Big – Oh Notation)
		2.4.3 (Ω)  Omega Notation
		2.4.4 (θ) Theta Notation
		2.4.5 o– Notation (Little–Oh Notation)
		2.4.6 ω – Notation (Little-Omega Notation)
		2.4.7 Comparison of Functions
			2.4.7.1 Transitivity
			2.4.7.2 Reflexivity
			2.4.7.3 Symmetry
			2.4.7.4 Transpose Symmetry
		2.4.8 Summary
	2.5 PROBLEMS RELATED TO NOTATIONS
		2.5.1 Stirling’s Approximations
	2.6 RECURRENCES
		2.6.1 Recurrence Relations
		2.6.2 Substitution Method
		2.6.3 Recursion Tree
		2.6.4 Master Method
	2.7 QUESTIONS
		2.7.1 Short questions
		2.7.2 Long Questions
Chapter 3 Divide-and-Conquer Techniques
	3.1 DIVIDE-AND-CONQUER APPROACH
	3.2 BINARY SEARCH
		3.2.1 Analysis of Binary Search
			3.2.1.1 Best-Case complexity
			3.2.1.2 Worst-Case complexity
	3.3 MERGE SORT
		3.3.1 Analysis of Merge Sort
	3.4 QUICK SORT
		3.4.1 Good Points of Quick Sort
		3.4.2 Bad Points of Quick Sort
		3.4.3 Performance of Quick Sort
			3.4.3.1 Worst Case
			3.4.3.2 Best Case
	3.5 HEAP SORT
		3.5.1 Building a Heap
	3.6 PRIORITY QUEUE
		3.6.1 Operations for Min Priority Queue
	3.7 LOWER BOUND FOR SORTING
	3.8 QUESTIONS
		3.8.1 Short Questions
		3.8.2 Long Questions
Chapter 4 Dynamic Programming
	4.1 DYNAMIC PROGRAMMING
	4.2 DEVELOPING DYNAMIC PROGRAMMING ALGORITHMS
		4.2.1 Optimal Substructure
		4.2.2 The Principle of Optimality
	4.3 MATRIX CHAIN MULTIPLICATION
		4.3.1 Chains of Matrices
			4.3.1.1 How to Order Multiplications?
	4.4 LONGEST COMMON SUBSEQUENCE PROBLEM
	4.5 DIVIDE AND CONQUER VS. DYNAMIC PROGRAMMING
	4.6 QUESTIONS
		4.6.1 Short Questions
		4.6.2 Long Questions
Chapter 5 Greedy Algorithms
	5.1 GREEDY ALGORITHMS
		5.1.1 Characteristics and Features of Problems Solved by Greedy Algorithms
		5.1.2 Basic Structure of Greedy Algorithm
		5.1.3 What Is Feasibility
			5.1.3.1 How to Prove Greedy Algorithms Optimal
	5.2 AN ACTIVITY – SELECTION PROBLEM
	5.3 KNAPSACK PROBLEM
	5.4 HUFFMAN ENCODING
		5.4.1 Prefix-Free Code Representation
	5.5 GREEDY VERSUS DYNAMIC PROGRAMMING
	5.6 DATA STRUCTURES FOR DISJOINT SETS
		5.6.1 Application of Disjoint Set Data Structures
		5.6.2 Linked List Representation of Disjoint Sets
		5.6.3 Disjoint Set of Forests
		5.6.4 By Path Compression
	5.7 QUESTIONS
		5.7.1 Short Questions
		5.7.2 Long Questions
Chapter 6 Graph
	6.1 TRAVERSAL OF GRAPH
		6.1.1 Breadth First Search
		6.1.2 Depth First Search
	6.2 SPANNING TREE
		6.2.1 Minimum Spanning Tree
		6.2.2 Kruskal Algorithm
		6.2.3 Prim’s Algorithm
	6.3 SINGLE-SOURCE SHORTEST PATH
		6.3.1 Negative Weighted Edges
		6.3.2 Relaxation Technique
		6.3.3 Bellman–Ford Algorithm
		6.3.4 Dijkstra’s Algorithm
	6.4 ALL PAIR SHORTEST PATH
		6.4.1 Floyd–Warshall’s Algorithm
	6.5 QUESTIONS
		6.5.1 Short Questions
		6.5.2 Long Questions
Chapter 7 Approximation Algorithms
	7.1 HAMILTONIAN CYCLE
	7.2 APPROXIMATION ALGORITHMS
		7.2.1 Traveling Salesman Problem
			7.2.1.1 Special Case of TSP
	7.3 BACKTRACKING
		7.3.1 Hamiltonian Circuit Problem
	7.4 N-QUEEN PROBLEM/8 – QUEEN PROBLEM
	7.5 BACKTRACKING ALGORITHM
	7.6 BRANCH AND BOUND
		7.6.1 Knapsack Problem
	7.7 QUESTIONS
		7.7.1 Short Questions
		7.7.2 Long Questions
Chapter 8 Matrix Operations, Linear Programming, Polynomial and FFT
	8.1 MATRICES
		8.1.1 Operations with Matrix
		8.1.2 Rank of a Matrix
		8.1.3 Application of Matrices
		8.1.4 Boolean Matrix Multiplication
	8.2 POLYNOMIALS
	8.3 POLYNOMIAL AND FFT
	8.4 QUESTIONS
		8.4.1 Short Questions
		8.4.2 Long Questions
Chapter 9 Number Theoretic Algorithms
	9.1 NUMBER THEORETIC ALGORITHMS
	9.2 GREATEST COMMON DIVISOR
	9.3 LINEAR DIOPHANTINE EQUATIONS
	9.4 MODULAR ARITHMETIC
	9.5 LINEAR CONGRUENCE
		9.5.1 Single-Variable Linear Equations
		9.5.2 Set of Linear Equations
	9.6 GROUPS
	9.7 RING
	9.8 FIELD
	9.9 QUESTIONS
		9.9.1 Short Questions
		9.9.2 Long Questions
Chapter 10  Programming Implementations of the Algorithms
	10.1  PROGRAM FOR THE LONGEST COMMON SUBSEQUENCES
	10.2  MATRIX CHAIN MULTIPLICATION
	10.3  PROGRAM FOR KNAPSACK PROBLEM
	10.4  BELLMAN–FORD PROGRAM
	10.5  WRITE A PROGRAM FOR TRAVELLING SALESMAN PROBLEM USING BACKTRACKING
	10.6  TRAVELING SALESMAN PROBLEM USING BRANCH AND BOUND
	10.7  PROGRAM FOR HEAP SORT
	10.8  PROGRAM FOR QUICK SORT
	10.9  PROGRAM FOR MERGE SORT
	10.10 PROGRAM FOR DFS
	10.11 PROGRAM FOR PRIMS ALGORITHM
	10.12 PROGRAM FOR THE WARSHALL METHOD
	10.13 PROGRAM FOR THE KRUSKAL METHOD
	10.14 PROGRAM FOR DIJKSTRA METHOD
	10.15 BFS USING COLOR CODE
INDEX