Design and Analysis of Algorithms
Selected Reading
- DAA - Discussion
- DAA - Useful Resources
- DAA - Quick Guide
- DAA - Hill Climbing Algorithm
- NP Hard & NP-Complete Classes
- DAA - Cook’s Theorem
- DAA - P and NP Class
- DAA - Vertex Cover
- DAA - Max Cliques
- Deterministic vs. Nondeterministic Computations
- DAA - Sublist Search
- DAA - Fibonacci Search
- DAA - Exponential Search
- DAA - Jump Search
- DAA - Interpolation Search
- DAA - Binary Search
- DAA - Linear Search
- Searching Techniques Introduction
- DAA - Radix Sort
- DAA - Counting Sort
- DAA - Bucket Sort
- DAA - Heap Sort
- DAA - Shell Sort
- DAA - Selection Sort
- DAA - Insertion Sort
- DAA - Bubble Sort
- DAA - Extract Method
- DAA - Heapify Method
- DAA - Insert Method
- DAA - Binary Heap
- Optimal Cost Binary Search Trees
- DAA - Multistage Graph
- DAA - Shortest Paths
- DAA - Spanning Tree
- Travelling Salesperson Approximation Algorithm
- Set Cover Problem
- Vertex Cover Problem
- Approximation Algorithms
- Fisher-Yates Shuffle
- Karger’s Minimum Cut
- Randomized Quick Sort
- Randomized Algorithms
- Travelling Salesman Problem | Dynamic Programming
- Longest Common Subsequence
- DAA - 0-1 Knapsack
- Floyd Warshall Algorithm
- Matrix Chain Multiplication
- DAA - Dynamic Programming
- DAA - Optimal Merge Pattern
- DAA - Job Sequencing with Deadline
- DAA - Fractional Knapsack
- Map Colouring Algorithm
- Dijkstra’s Shortest Path Algorithm
- Kruskal’s Minimal Spanning Tree
- Travelling Salesman Problem
- DAA - Greedy Method
- Towers of Hanoi
- Karatsuba Algorithm
- Strassen’s Matrix Multiplication
- DAA - Binary Search
- DAA - Merge Sort
- DAA - Max-Min Problem
- DAA - Divide & Conquer
- DAA - Space Complexities
- Master’s Theorem
- Time Complexity
- Asymptotic Notations & Apriori Analysis
- DAA - Methodology of Analysis
- DAA - Analysis of Algorithms
- DAA - Introduction
- Home
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
DAA - Methodology of Analysis
Design and Analysis Methodology
To measure resource consumption of an algorithm, different strategies are used as discussed in this chapter.
Asymptotic Analysis
The asymptotic behavior of a function f(n) refers to the growth of f(n) as n gets large.
We typically ignore small values of n, since we are usually interested in estimating how slow the program will be on large inputs.
A good rule of thumb is that the slower the asymptotic growth rate, the better the algorithm. Though it’s not always true.
For example, a pnear algorithm $f(n) = d * n + k$ is always asymptotically better than a quadratic one, $f(n) = c.n^2 + q$.
Solving Recurrence Equations
A recurrence is an equation or inequapty that describes a function in terms of its value on smaller inputs. Recurrences are generally used in spanide-and-conquer paradigm.
Let us consider T(n) to be the running time on a problem of size n.
If the problem size is small enough, say n < c where c is a constant, the straightforward solution takes constant time, which is written as θ(1). If the spanision of the problem yields a number of sub-problems with size $frac{n}{b}$.
To solve the problem, the required time is a.T(n/b). If we consider the time required for spanision is D(n) and the time required for combining the results of sub-problems is C(n), the recurrence relation can be represented as −
$$T(n)=egin{cases}::::::::::::::::::::::: heta(1) & if:nleqslant c\a T(frac{n}{b})+D(n)+C(n) & otherwiseend{cases}$$
A recurrence relation can be solved using the following methods −
Substitution Method − In this method, we guess a bound and using mathematical induction we prove that our assumption was correct.
Recursion Tree Method − In this method, a recurrence tree is formed where each node represents the cost.
Master’s Theorem − This is another important technique to find the complexity of a recurrence relation.
Amortized Analysis
Amortized analysis is generally used for certain algorithms where a sequence of similar operations are performed.
Amortized analysis provides a bound on the actual cost of the entire sequence, instead of bounding the cost of sequence of operations separately.
Amortized analysis differs from average-case analysis; probabipty is not involved in amortized analysis. Amortized analysis guarantees the average performance of each operation in the worst case.
It is not just a tool for analysis, it’s a way of thinking about the design, since designing and analysis are closely related.
Aggregate Method
The aggregate method gives a global view of a problem. In this method, if n operations takes worst-case time T(n) in total. Then the amortized cost of each operation is T(n)/n. Though different operations may take different time, in this method varying cost is neglected.
Accounting Method
In this method, different charges are assigned to different operations according to their actual cost. If the amortized cost of an operation exceeds its actual cost, the difference is assigned to the object as credit. This credit helps to pay for later operations for which the amortized cost less than actual cost.
If the actual cost and the amortized cost of ith operation are $c_{i}$ and $hat{c_{l}}$, then
$$displaystylesumpmits_{i=1}^n hat{c_{l}}geqslantdisplaystylesumpmits_{i=1}^n c_{i}$$
Potential Method
This method represents the prepaid work as potential energy, instead of considering prepaid work as credit. This energy can be released to pay for future operations.
If we perform n operations starting with an initial data structure D0. Let us consider, ci as the actual cost and Di as data structure of ith operation. The potential function Ф maps to a real number Ф(Di), the associated potential of Di. The amortized cost $hat{c_{l}}$ can be defined by
$$hat{c_{l}}=c_{i}+Phi (D_{i})-Phi (D_{i-1})$$
Hence, the total amortized cost is
$$displaystylesumpmits_{i=1}^n hat{c_{l}}=displaystylesumpmits_{i=1}^n (c_{i}+Phi (D_{i})-Phi (D_{i-1}))=displaystylesumpmits_{i=1}^n c_{i}+Phi (D_{n})-Phi (D_{0})$$
Dynamic Table
If the allocated space for the table is not enough, we must copy the table into larger size table. Similarly, if large number of members are erased from the table, it is a good idea to reallocate the table with a smaller size.
Using amortized analysis, we can show that the amortized cost of insertion and deletion is constant and unused space in a dynamic table never exceeds a constant fraction of the total space.
In the next chapter of this tutorial, we will discuss Asymptotic Notations in brief.
Advertisements