Computer Algorithms: Correctness Proofs and Performance Analyses

Title
COMPUTER ALGORITHMS
Correctness Proofs andPerformance Analyses
Copyright
Dedication
Contents
List of Figures
Preface
1. Basics of Computer Algorithms
	1.1 Simplified Model of Modern Computers
	1.1.1 Compilers
	1.1.2 Pseudocode
	1.2 Some Examples
	1.2.1 Greatest Common Divisor
	1.2.2 Proof of Correctness of the GCD Algorithm
	1.2.3 Largest Group of Mutually Known People
	1.2.4 Bubble Sort
	1.2.5 Maximum Facility Usage Problem
	1.2.6 Improving the Algorithm Using Binary Search
	1.3 Algorithms that Do Not Compute Exact Answer
	1.4 Efficiency Analysis of an Algorithm
	1.4.1 The Concept of Problem Instance Size
	1.4.2 Measure of Time and Space
	1.4.3 Worst-Case Time/Space Compelxity
	1.4.4 Dealing with Non-Smooth Functions
	1.4.5 Time/Space for Basic Arithmetic/Logic Operations
	1.4.6 Where Time Complexity is Not a Deciding Factor
	1.5 Time and Space Analysis of Some Simple Algorithms
	1.5.1 Maximum Facility Usage Problem
	1.5.2 Analysis of Bubble Sort
	1.5.3 Analysis of GCD Algorithm
	1.6 More Examples of Algorithms
	1.6.1 Merging Two Sorted Sequences
	1.6.2 Quick Sort
	1.6.3 A Special Case
	1.7 Sorting Algorithms Which Do Not Use Comparison
	1.7.1 Stable Sorting
	1.7.2 Counting Sort
	1.7.3 Radix Sort
	1.7.4 Bucket Sort
	1.8 Lower Bound for Sorting
	1.8.1 Decision Tree
	1.9 P and NP Classes
	Notes
	Exercises
2. Elementary Data Stuctures
	2.1 Role of Data Structures in Programming
	2.1.1 Structure Topologies
	2.1.2 List Operations
	2.1.3 List Implementations
	2.1.4 Operations on a List
	2.1.5 Operations on Tree-Based Data Structures
	2.2 Stack
	2.2.1 An Application of a Stack
	2.3 Queue
	2.3.1 Implementation of a Queue in an Array
	2.3.2 Implementation of a Queue Using a Linked List
	2.3.3 Applications of a Queue
	2.4 Heap Data Structure
	2.4.1 An Application: Heap Sort
	2.5 Binary Search Trees
	2.5.1 Search
	2.5.2 Insertion
	2.5.3 Deletion
	2.5.4 Balanced BST
	2.5.5 Red-Black Tree
	2.5.6 Operations on RB Trees
	2.6 Hashing
	2.7 Direct Access Table
	2.8 Open Hashing
	2.8.1 Chaining
	2.8.2 Chaining: Analysis
	2.8.3 Hash Functions
	2.8.4 Universal Hashing
	2.8.5 Two Level Hashing Scheme
	2.9 Closed Hashing
	2.9.1 Hash Functions
	2.9.2 Analysis
	Notes
	Exercises
3. Graph Exploration Algorithms
	3.1 Graph Basics
	3.1.1 Data Structures to Store Graphs
	3.1.2 Distance Measure in Unweighted Graphs
	3.1.3 Distance Measure in Edge-weighted Graphs
	3.2 Broadcast to Compute a Shortest Path Spanning Tree
	3.2.1 Proof of Correctness and Analysis of Algorithm
	3.2.2 Time and Space Complexity
	3.3 Breadth First Search for Shortest Path
	3.3.1 Exploring the Breadth-First Way
	3.3.2 2.0
	3.4 BFS Based Shortest Path Algorithm
	3.4.1 Proof of Correctness
	3.4.2 Breadth-First Tree
	3.4.3 Time and Space Complexities of the Algorithm
	3.4.4 Algorithm
	3.4.5 Proof of Correctness
	3.4.6 Time and Space Complexity
	3.5 Shortest Path Using Matrix Method
	3.5.1 Improved Algorithm
	3.5.2 Time and Space Complexity of the Improvement Algorithm
	3.5.3 Transitive Closure and Connected Components
	3.6 All Pair Shortest Paths: Floyd Warshall Algorithm
	3.6.1 Complexity of Floyd Warshall Algorithm
	3.6.2 Transitive Closure and Connected Components
	3.7 Depth First Search
	3.7.1 DFS Algorithm for General Graphs with Departure/Arrival Time
	3.7.2 Biconnected Components
	3.7.3 Algorithm to Compute Biconnected Components
	3.8 Algorithms for Directed Graphs
	3.8.1 Bellman Ford Algorithm
	3.8.2 Dijkstra’s Algorithm
	3.8.3 All Pair Shortest Path: Matrix Method
	3.8.4 All Pair Shortest Path: Floyd Warshall Algorithm
	3.8.5 In the Presence of Negative Weight Closed Walks
	3.8.6 Minimum Weight Cycle in a Directed Graph
	3.8.7 Minimum Mean-Weight Cycle in a Graph
	3.8.8 Depth First Search
	3.8.9 Strongly Connected Components
	Notes
	Exercises
4. String Matching and String Isomorphism
	4.1 String Matching Problem
	4.2 Brute Force Algorithm
	4.3 Knuth-Morris-Pratt Approach
	4.3.1 Efficient Computation of f
	4.3.2 KMP Algorithm
	4.4 Rabin Karp String Matching Approach
	4.4.1 Dealing with Large Numbers
	4.4.2 Analysis
	4.4.3 Further Improvement
	4.5 String Homomorphism/Isomorphism Problem
	4.5.1 Algorithm for Strings of Equal Length
	4.5.2 Substring Isomorphism/Homomorphism Problem:
 Brute Force Algorithm
	4.5.3 Extension of KMP Algorithm to Substring Isomorphism
	4.6 Regular Language Membership of Substrings
	4.6.1 Construction of an NFA from R
	4.6.2 Execution of the NFA
	4.6.3 An Example
	4.6.4 Algorithm to Compute D
	4.6.5 Searching a String of L(R) Starting from ai
	Notes
	Exercises
5. Divide and Conquer and Dynamic Programming
	5.1 Problem Size
	5.2 Reduce and Solve
	5.3 Divide and Conquer
	5.3.1 Example 1: Sorting
	5.3.2 Example 2: Integer Multiplication
	5.3.3 Example 3: Closest Pair of Points
	5.3.4 Remarks about Divide and Conquer Technique and Memoization
	5.4 Dynamic Programming
	5.4.1 Elements of Dynamic Programming
	5.4.2 Example 1: Longest Common Sub-sequence
	5.4.3 Example 2: Matrix-Chain Multiplication
	5.4.4 Example 3 Decorative Garden Problem
	5.4.5 An Insight into Sub-structure Optimality and Conditional
 Optimality
	Notes
	Exercises
6. Matching in an Unweighted Graph
	6.1 Maximum Matching Problem
	6.1.1 Alternating Walk and its Computation
	6.2 Algorithm Using Alternating Walks
	6.2.1 Reduction and Extension of Graph and Matching
	6.2.2 A Recursive Algorithm
	6.2.3 An Application of Matching
	6.3 Gallai Edmonds Decomposition
	6.4 Vertex Cover/Independent Set in Bipartite Graphs
	6.4.1 Vertex Cover in Bipartite Graphs
	Notes
	Exercises
7. Greedy Paradigm and Matroid Algorithms
	7.1 Greedy Paradigm
	7.1.1 Problem of Maximum Non-overlapping Intervals
	7.1.2 A Greedy Solution
	7.1.3 Maximum Weight Basis
	7.2 Matroids
	7.2.1 Definitions and Properties
	7.2.2 Maximum Weight Maximal Independent Set
	7.2.3 An Application of the Matroid Algorithm: Kruskal’s Algorithm
	7.3 Union and Find: Linked-List Based Data Structure
	7.4 Connected Sub-Matroid
	7.4.1 Minimum Weight Spanning Tree: Prim’s Algorithm
	7.5 Matroid Intersection Algorithm
	7.5.1 Algorithm for Matroid Intersection Problem
	7.6 More Applications of Matroid Intersection Algorithm
	7.6.1 Arborescence
	7.6.2 Edge Disjoint Spanning Trees
	7.7 Union and Find: Tree-Based Data Structure
	7.7.1 Path Compression
	Notes
	Exercises
8. Flow and Circulation Networks
	8.1 Basics of Flow Networks
	8.2 Ford Fulkerson Method
	8.3 The Edmonds Karp Approach
	8.4 A Local Approach: Push and Relabel Algorithm
	8.4.1 Flow Control
	8.4.2 Push and Relabel Algorithm
	8.4.3 Correctness and Time Complexity
	8.4.4 The Case of Multiple Sources and Sinks
	8.5 Minimum Cost Circulation
	8.5.1 Weighted Flow
	8.5.2 Circulation
	8.5.3 Minimum Mean Cost Strategy
	8.5.4 Goldberg Tarjan Theorem
	Notes
	Exercises
9. System of Linear Equations and Matrix Operations
	9.1 Planes in .n
	9.2 System of Linear Equations
	9.2.1 Consistency in Linearly Dependent System of Equations
	9.2.2 Rank and Determinant
	9.2.3 Some Related Properties
	9.3 Solution of a System of Linear Equations
	9.3.1 By Cramer’s Rule
	9.3.2 By Matrix Inversion
	9.4 Matrix Multiplication
	9.4.1 A Simple Divide and Conquer Approach
	9.4.2 Strassen’s Approach
	9.5 Matrix Inversion
	9.5.1 A Divide and Conquer Approach
	9.5.2 Inverse of a Triangular Matrix
	9.5.3 Algorithm
	9.6 L-U Decomposition by Gaussian Elimination
	9.6.1 Row Operation on a Matrix
	9.6.2 Gaussian Elimination
	9.6.3 Permutation Matrices
	9.6.4 Managing the Pivot
	9.6.5 Gaussian Elimination Algorithm
	9.7 L-U Decomposition by Divide and Conquer
	9.7.1 Decomposition Algorithm
	9.7.2 Analysis
	9.8 “Determinant” of a Non-Square Matrix
	9.8.1 Gram-Schmidt Orthogonalization and Volume Computation
	Exercises
	10. Linear Programs and Simplex Algorithm
	10.1 Linear Programs (LPs
	10.1.1 Forms of Linear Programs (LPs
	10.1.2 Examples of Problems Formulated as LPs
	10.1.3 Geometry of Linear Programs in Standard Form
	10.1.4 Geometry of Linear Programs in Slack Form
	10.1.5 Extreme Point Solutions of LP in Slack Form
	10.2 Simplex Algorithm
	10.2.1 Pivoting
	10.2.2 Algorithm
	10.3 Computation of an Initial Feasible State
	10.4 Performance of Simplex Algorithm and Klee-Minty Example
	10.4.1 Klee-Minty Linear Program
	10.5 Gallai-Edmonds Decomposition Using Linear Programming
	Notes
	Exercise
11. Interior Point Methods for Linear Programs
	11.1 Introduction
	11.1.1 Duality in Linear Programs
	11.1.2 The Projection of c on P
	11.2 Primal Affine Scaling Algorithm
	11.2.1 Moving through the Interior
	11.2.2 Optimality and Termination
	11.2.3 Algorithm
	11.2.4 Problem of the Initial Solution
	11.3 Dual Affine Scaling Algorithm
	11.3.1 Movement in the Dual Space
	11.3.2 Selecting a Good Direction
	11.3.3 Step Size
	11.3.4 Computing a Primal Solution in Each Iteration
	11.3.5 Algorithm
	11.3.6 Problem of the Initial Solution
	11.4 A Complete Solution Using Primal-Dual Technique
	11.4.1 Progressing in the Interior
	11.4.2 A Balanced Path
	11.4.3 Termination of Progression
	11.4.4 Computation of an Optimal Solution
	11.4.5 Detection of Unbounded Feasible Region
	11.4.6 Modified Linear Program
	11.4.7 Determination of Q
	11.4.8 Initial Balanced Interior State
	11.4.9 Algorithm
	11.4.10 Time Complexity
	Notes
12. Weighted Matching: An Application of Primal Dual Technique
	12.1 Minimum Weight Perfect Matching in Bipartite-Graphs
	12.1.1 Linear Programming Formulation for Perfect Matching in
 General Graphs
	12.1.2 Special Property of Linear Programs for Bipartite Graphs
	12.1.3 Alternating Breadth-First Tree in General Graphs
	12.1.4 A Primal-Dual Approach for Bipartite Graphs
	12.1.5 Extension of Gtight
	12.1.6 The Algorithm
	12.1.7 Correctness and Complexity of the Algorithm
	12.2 Minimum Weight Perfect Matching in General Graphs
	12.2.1 Primal Dual Approach for General Graphs
	12.2.2 Extension of Gtight
	12.2.3 Modification in Potential
	12.2.4 Contraction and Expansion of G
	12.2.5 Algorithm
	12.3 More Matching Problems on Weighted Graphs
	12.3.1 Minimum Weight Perfect Matching with Mixed Weights
	12.3.2 Maximum Weight Perfect Matching with Mixed Weights
	12.3.3 Minimum Weight Maximum Matching with Non-Negative Weights
	12.3.4 Minimum Weight Maximum Matching with Mixed Weights
	12.3.5 Maximum Weight Matching with Non-Negative Weights
	12.3.6 Maximum Weight Matching with Mixed Weights
	12.3.7 Minimum Weight Matching with Mixed Weights
	Notes
	Exercises
13 Complexity of Elementary Arithmetic and
 Polynomial Operations
	13.1 Reciprocal of an n-bit Number in O(M(n)) Time
	13.1.1 Problem
	13.1.2 An Iterative Approach
	13.1.3 The Algorithm
	13.1.4 Proof of Correctness
	13.1.5 Complexity Analysis
	13.1.6 Problems of Arbitrary n and Arbitrary Accuracy
	13.2 Square of an n-Bit Number in O(R(n
	13.2.1 Proof of Correctness
	13.2.2 Time Complexity
	13.3 Multiplication of two n-Bit Numbers in O(S(n
	13.4 Division of 2n-Bit Number by n-Bit Number in-Q(R(n)) Time
	13.5 Theorem
	13.6 Polynomial Algorithms
	13.6.1 Reciprocal of a Polynomial
	Exercise
14. Modular Arithmetic Computations
	14.1 Integral Computations
	14.2 The Finite Ring ZN
	14.2.1 Some Formal Definitions
	14.2.2 Multiplicative Inverse
	14.2.3 Fermat’s Little Theorem
	14.2.4 Linear Modular Equations
	14.2.5 Montgomery Method for Modular Multiplication
	14.3 Multi-Modular Representation of Integers
	14.3.1 Algorithm to Compute ru
	14.3.2 Time Complexity
	14.3.3 Reverse Computation
	14.4 RSA Cryptosystem
	14.4.1 Message Packet
	14.4.2 Operations Under RSA System
	14.4.3 The Mappings
	14.4.4 A Toy Example
	14.4.5 Non-Uniqueness Problem
	14.4.6 How Secure is this Encryption
	14.4.7 Efficient Computation of PA(x) and SA(x
	14.5 Modular Computations for Polynomials
	14.5.1 Elementary Facts about Polynomial Rings
	14.5.2 Modular Representation for Polynomials
	14.5.3 Computation of the Representation
	14.6 Polynomial Evaluation and Interpolation
	14.6.1 Algorithm
	Exercises
15. Discrete Fourier Transform
	15.1 Modules
	15.2 Definition
	15.2.1 DFT
	15.2.2 Inverse DFT
	15.2.3 Fast Fourier Transform: A Divide and Conquer Approach
	15.3 Convolution of Vectors and Efficient Polynomial Multiplication
	15.3.1 Two Variants of Convolution
	15.4 DFT in Modulo m Ring
	15.4.1 Computation in R = .m
	Exercises
16. Two Integer-Algorithms
	16.1 Schonhage-Strassen’s Integer Multiplication Algorithm
	16.1.1 Computation in Z2n+1
	16.1.2 Computation of zi (mod 22l + 1
	16.1.3 Computation of zi (mod b
	16.1.4 Combining to Compute zi
	16.1.5 Analysis of the Algorithm
	16.1.6 Example Run of the Algorithm
	16.2 Agarwal Kayal Saxena’s Primality Testing Algorithm
	16.2.1 Restricted Criterion
	16.2.2 Correctness of the Algorithm
	16.2.3 AKS Algorithm and Time Complexity
	Notes
Exercise
Bibliography
Index
Back cover