Design And Analysis Of Algorithm
UNIT-I
Mathematical foundations, summation of arithmetic and geometric series, n, n2 , bounding summations using integration, recurrence relations, solutions of recurrence relations using technique of characteristic equation, Complexity calculation of various standard functions, principles of designing algorithms
UNIT-II
Asymptotic notations of analysis of algorithms, analysing control structures, worst case and average case analysis, amortized analysis, application of amortized analysis, advanced data structures like Fibonacci heap, disjoint set representation, and their applications, Divide and
conquer basic strategy, binary search, quick sort, merge sort, matrix operations, Multiplication Algorithm
UNIT-III
Greedy method – basic strategy, Knapsack Problem, application to job sequencing with deadlines problem, minimum cost spanning trees, single source shortest path, Optimal Search Patterns.
UNIT-IV
Dynamic Programming basic strategy, multistage graphs, all pairs shortest path, single source shortest paths, optimal binary search trees, traveling salesman problem, Longest Common Subsequence, 0/1 Knapsack problem.
UNIT-V
Connected components, Backtracking basic strategy, 8-Queen’s problem, sum of subsets, Knight tour’s problem, graph coloring, Hamiltonian cycles etc, Introduction to Approximation algorithm.
UNIT-VI
NP-hard and NP-complete problems, basic concepts, non-deterministic algorithms, NP-hard and NP-complete, decision and optimization problems, graph based problems on NP Principle.
Course objective
Obtaining efficient algorithms is very important in modern computer engineering as the world wants applications to be time and space and energy efficient. This course enables to understand and analyze efficient algorithms for various applications.
Course Outcome:
After learning the course the students should be able to:
1. Define the basic concept of algorithm and Analyze the asymptotic performance of algorithms.
2. Derive and solve recurrences describing the performance of divide and Conquer algorithms.
3. Find optimal solution by applying greedy approach
4. Find optimal solution by applying dynamic approach, backtracking. 5 Explain the major graph algorithms and their analyses and Differentiate polynomial and non-polynomial problems
Introduction of Algorithm
An algorithm is a set of steps of operations to solve a problem performing calculation, data processing, and automated reasoning tasks. An algorithm is an efficient method that can be expressed within finite amount of time and space.
An algorithm is the best way to represent the solution of a particular problem in a very simple and efficient way. If we have an algorithm for a specific problem, then we can implement it in any programming language, meaning that the algorithm is independent from any programming languages.
Characteristics of Algorithms
The main characteristics of algorithms are as follows −
• Algorithms must have a unique name
• Algorithms should have explicitly defined set of inputs and outputs • Algorithms are well-ordered with unambiguous operations
• Algorithms halt in a finite amount of time. Algorithms should not run for infinity, i.e., an algorithm must end at some point
Differentiate between Dynamic Programming and Greedy Method Dynamic Programming Greedy Method
1. Dynamic Programming is used to obtain the optimal solution.
2. In Dynamic Programming, we choose at each step, but the choice may depend on the solution to sub-problems.
3. Less efficient as compared to a greedy approach
1. Greedy Method is also used to get the optimal solution.
2. In a greedy Algorithm, we make whatever choice seems best at the moment and then solve the sub-problems arising after the choice is made.
3. More efficient as compared to a greedy approach
4. Example: 0/1 Knapsack 4. Example: Fractional Knapsack
5. It is guaranteed that Dynamic Programming will generate an optimal solution using Principle of Optimality.
5. In Greedy Method, there is no such guarantee of getting Optimal Solution.
Greedy Method
The basic idea of the greedy approach is to calculate the ratio value/weight for each item and sort the item on basis of this ratio. Then take the item with the highest ratio and add them until we can't add the next item as a whole and at the end add the next item as much as we can.
Knapsack Problem
In 0-1 Knapsack, items cannot be broken which means the thief should take the item as a whole or should leave it. This is reason behind calling it as 0-1 Knapsack.
Hence, in case of 0-1 Knapsack, the value of xi can be either 0 or 1, where other constraints remain the same.
0-1 Knapsack cannot be solved by Greedy approach. Greedy approach does not ensure an optimal solution. In many instances, Greedy approach may give an optimal solution.
The following examples will establish our statement.
Example-1
Let us consider that the capacity of the knapsack is W = 25 and the items are as shown in the following table.
Without considering the profit per unit weight (pi/wi), if we apply Greedy approach to solve this problem, first item A will be selected as it will contribute maximum profit among all the elements.
After selecting item A, no more item will be selected. Hence, for this given set of items total profit is 24. Whereas, the optimal solution can be achieved by selecting items, B and C, where the total profit is 18 + 18 = 36.
Example-2
Instead of selecting the items based on the overall benefit, in this example the items are selected based on ratio pi/wi. Let us consider that the capacity of the knapsack is W = 60 and the items are as shown in the following table.
Using the Greedy approach, first item A is selected. Then, the next item B is chosen. Hence, the total profit is 100 + 280 = 380. However, the optimal solution of this instance can be achieved by selecting items, B and C, where the total profit is 280 + 120 = 400.
Hence, it can be concluded that Greedy approach may not give an optimal solution.
Greedy algorithm ( Fractional Knapsack problem ) The greedy algorithm, actually it’s not an algorithm it is a
technique with the which we create an algorithm to solve a particular problem. So as its name suggests we have to greedy about the choice that we made, which seems best for that moment, regardless of the fact the choice we made right would turn out to be the worst choice.
Today we will understand how greedy really works, and how we break items for maximizing the total value of knapsack problem.
First, we have to understand, what is knapsack and what really this knapsack problem is?.
So knapsack means bag. And the problem statement of the knapsack problem is like this…
We have some objects, that you want to import for us to India to sell. And object can be fractional means could be choose in fractional format. If we sell some units of an object in the Indian market we will get some amount of profit form that object
So now as shown in the above image if we sell 18 units of object1, we will get a profit of 25 in the Indian market. The same logic applies to the remaining two objects like for object 2 if weight is 15 units the profit will be 24. But the moment we have reach airport with our objects we came to know that, we have some limitation in luggage transportation at the airport, and we are allowed only to take a bag with us of max 20 units of Wight max.
Now we have to arrange objects in our bag in such a way that when we sell the objects in Indian market we will get maximum profit out of it.
So we will try different approaches to solve this problem. Here we will use the greedy technique to find the solution.
First Approach (Greedy about profit):- First, approach of every single person would be greedy about profit. Since I want to maximize the profits, I will take the objects which can give maximum profit. Therefore it seems, if we take object1 (profit — 25 ) first and put it in the bag, then we would get the max profit right. So after adding, let’s see what happens.
As we can see in the above picture if we took object1 (whose weight is 18 unit and profit of 18 units is 25,) and put it in the bag. Now the weight that remains in the bag is 2 units. So the next item with the maximum profit available is object2 whose
profit is 24, only if, we put 15 units of weight. But we don’t have enough space left in the bag.
So if I put 15 u — — — I will get the profit of — — — — 24 of object2
but bag is only left with 2 unit of space
so for 2 u — — — — I will get the profit of — — — — (24/15)*2
So as we went greedy about profit, then after filling the bag completely we have got profit 28.2. So is this the best possible solution?. Or Is there is any other method which we can apply and get the maximum profit out of it. Let’s observe that…
This time we will try to put as many as objects in the bag to maximize the profit. so for that, we will take the object which
will be having the least weight, and we should put it first. So that bag would b filled with as many as objects. Therefore this time we are greedy about weights.
Second Approach (Greedy about Weight):- This time we have to choose the object with the least weight and that is object3. Therefore we will put object3 first whose weight is 10 as shown in the below
2. Second Approach (Greedy about Weight):- This time we have to choose the object with the least weight and that is object3. Therefore we will put object3 first whose weight is 10 as shown in the below
Now after putting object3, the bag still has 10 units of weight remaining. Now next object with the least weight is object2. So
now we are going to put object2 in the bag, but we can’t pul all the 15 units of weight because only 10 units of wight are available in the bag. So just like we did before….
So if I put 15 u — — — I will get the profit of — — — — 24 of object2
But if I have only 10 u — — — — I will get the profit of — — — — (24/15)*10
This time we got total profit is 31. This time profit is more than when we were greedy about profits. It is not applicable for all the instances, only for this problem, we are getting more profit if we go greedy for weight rather than greedy for profit.
But still, we are not sure that the last total is the best possible solution to our problem. So what could be other property for which we would be greedy about for maximum profit? So now we won’t either by profits or by weights. This time we will go by the ratio of profit/weight (Fraction Knapsack).
obj1 obj2 obj3
p/w
object 1 — (25/18) = 1.4
object2 — (24/15) =1.6
object3 — (15/10) =1.5
Now we feel that the one with the maximum profit per unit, that has to be placed in the knapsack. So first object to be placed is object2 and then object3 as shown in the below picture.
his time we get the profit is 31.5. This is true for all instances, so whenever we try to find the profit per unit weight ratio and then place the object which has the max p/w ratio. we will always get the maximum profit.
Fractional Knapsack Problem
In Fractional Knapsack Problem,
• As the name suggests, items are divisible here. • We can even put the fraction of any item into the knapsack if taking the complete item is not possible.
• It is solved using Greedy Method.
Fractional Knapsack Problem Using Greedy Method
Fractional knapsack problem is solved using greedy method in the following steps
Step-01:
For each item, compute its value / weight ratio.
Step-02:
Arrange all the items in decreasing order of their value / weight ratio.
Step-03:
Start putting the items into the knapsack beginning from the item with the highest ratio.
Put as many items as you can into the knapsack.
Time Complexity
The main time taking step is the sorting of all items in decreasing order of their value / weight ratio.
If the items are already arranged in the required order, then while loop takes O(n) time.
The average time complexity of Quick Sort is O(nlogn). Therefore, total time taken including the sort is O(nlogn). Problem
For the given set of items and knapsack capacity = 60 kg, find the optimal solution for the fractional knapsack problem making use of greedy approach.
OR
Find the optimal solution for the fractional knapsack problem making use of greedy approach. Consider
n = 5
w = 60 kg
(w1, w2, w3, w4, w5) = (5, 10, 15, 22, 25)
(b1, b2, b3, b4, b5) = (30, 40, 45, 77, 90)
Solution
Step-01:
Compute the value / weight ratio for each item
Step-02:
Sort all the items in decreasing order of their value / weight ratio
I1 I2 I5 I4 I3
(6) (4) (3.6) (3.5) (3)
Step-03:
Start filling the knapsack by putting the items into it one by one.
Now,
• Knapsack weight left to be filled is 20 kg but item-4 has a weight of 22 kg.
• Since in fractional knapsack problem, even the fraction of any item can be taken.
• So, knapsack will contain the following items-
< I1 , I2 , I5 , (20/22) I4 >
Total cost of the knapsack
= 160 + (20/22) x 77
= 160 + 70
= 230 units
Important Note
Had the problem been a 0/1 knapsack problem, knapsack would contain the following items-
< I1 , I2 , I5 >
The knapsack’s total cost would be 160 units.
Algorithm:
Greedy
Knapsack
{
for i=1 to n //step1 {
compute pi/wi; //step2
}
sort objects in non- increasing order p/w; //step3 for i=1 to n //step4
if(m>0 && wi<=m) //step5
m = m - wi; //step6
P = P + pi; //step7
else //step8
break; //step9
if(m>0) //step10
P=P+ pi*(m/wi); //step11
}
Comments
Post a Comment