A Guide to Design and Analysis of Algorithms

Description

Contents Preface Chapter 1 Introduction to the Design of Algorithms 1.1. Brute Force Approach 1.2. Divide and Conquer 1.3. Greedy Technique 1.4. Dynamic Programming 1.5. Branch and Bound 1.6. Randomized Algorithms 1.7. Backtracking Algorithm Chapter 2 Divide and Conquer 2.1. Recurrence Relation 2.2. Binary Search 2.3. Merge Sort Chapter 3 Greedy Algorithms 3.1. Job Sequencing Problem with Deadline 3.2. Dijkstra Algorithm Chapter 4 Dynamic Programming 4.1. Stagecoach Problem 4.2. Optimal Binary Search Tree (Optimal BST) 4.3. Subset Sum Problem 4.4. 0/1 Knapsack Problem Chapter 5 Backtracking 5.1. N – Queens Problem Chapter 6 Branch and Bound 6.1. Assignment Problem 6.1.1. Branch and Bound Technique to Solve Assignment Problem 6.2. O/1 Knapsack Problem 6.3. Travelling Salesman Problem Chapter 7 Introduction to the Analysis of Algorithms 7.1. Asymptotic Analysis 7.1.1. Big – Oh 7.1.2. Big - Omega 7.1.3. Theta 7.2. Empirical Analysis of Computer Algorithms: Why Statistics? 7.2.1. Computer Experiments and Algorithmic Complexity 7.2.2. Statistical (Complexity) Bound (Definition) Chapter 8 Randomized Algorithms 8.1. Randomized Quick Sort 8.2. Randomized Binary Search Chapter 9 Master Theorem 9.1. Master Theorem for Decreasing Function 9.2. Limitations of Master Theorem Chapter 10 A Note on Empirical Complexity Analysis 10.1. The Fundamental Theorem of Finite Difference 10.2. Empirical Complexity of Merge Sort 10.3. Empirical Complexity of Quick Sort 10.4. Empirical Complexity of Bubble Sort 10.5. Empirical Complexity of Selection Sort References About the Authors Index Blank Page Blank Page