β Scribed by Soubhik Chakraborty, Prashant Pranav, Naghma Khatoon, Sandip Dutta
No coin nor oath required. For personal study only.
As there can be more than one algorithm for the same problem, designing and analyzing an algorithm becomes important in order to make it as efficient and robust as possible. This book will serve as a guide to design and analysis of computer algorithms. Chapter One provides an overview of different algorithm design techniques and the various applications of such techniques. Chapter Two reviews the divide and conquer strategy and the algorithm types that employ it. Chapter Three explores greedy algorithms and some problems that can be solved with this approach. Chapter Four discusses in depth the dynamic programming approach. Chapter Five provides a solution to the N-Queens problem utilizing a backtracking approach. Chapter Six elucidates the reader to branch and bound techniques and provides three solutions to problems implementing them. Part II of this book begins with Chapter Seven, where two different approaches to the analysis of algorithms are discussed. Chapter Eight reviews randomized algorithms through an empirical lens. Chapter Nine discusses Master Theorem and the many kinds of problems this Theorem can solve. Chapter Ten, the final chapter, provides notes on the empirical complexity analysis of algorithms.
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
π SIMILAR VOLUMES
<p>Presenting a complementary perspective to standard books on algorithms, <strong>A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis</strong> provides a roadmap for readers to determine the difficulty of an algorithmic problem by finding an optimal solution or proving complexi
Based on a new classification of algorithm design techniques and a clear delineation of analysis methods, Introduction to the Design and Analysis of Algorithms presents the subject in a coherent and innovative manner. Written in a student-friendly style, the book emphasizes the understanding of idea