Day 29: Design Techniques

Hello Dear Students,
 Hope you all are doing good.

So, aaj hum data structure ke algorithms ki designing techniques ke baare mein study karenge,

Let's get started...

For designing and analyzing algorithms we use various approaches, Jab data structure mein algorithms bante hain, so use design and analyse karne ke liye hum various techniques ko use karte hain, which are as follows-
  1. Divide and Conquer
  2. Greedy Method
  3. Dynamic programming
  4. Back tracking
  5. Branch and Bound, etc.

1. DIVIDE AND CONQUER
  • Divide and Conquer technique mein hum sabse pehle problem ko small units or pieces mein divide kar lete hain and then us par processing karte hain, then wo divided small units ko hum combine kar dete hain so that it should be processed and problem is solved. 
  • Divide and Conquer technique ko hum merge sort and quick sort mein bhi apply karte hain. 
  • Sorting techniques ke lecture mein humne ise discuss kiya tha. 
  • Simple example is real world mein jab hum kuch kaam kar rahe hote hain, then agar 1 person wo kaam karega so it takes more time and efforts, but agar 2 or more persons same kaam ko mil kar karenge then it takes far less time and efforts. 
  • This is an example of divide and conquer technique, jisme hum 2 or more unites mein divide karke then use combine kar lete hain and the problem is solved. 
  • The divide and conquer technique is used in - 
  1. Binary Search
  2. Quick Sort
  3. Merge Sort
  4. Closest Pair of points
  5. Strassen's Matrix Multiplication, and so on.

2. GREEDY METHOD
  • Greedy method ke name se hi pata chal raha hai ki is technique mein 'greedy' ho kar optimum result provide kiya ja sakta hai.
  • Greedy means the one who have selfish desires basically.
  • So greedy method mein hum ek problem ko solve karne ke liye optimum solutions ko use karte hain.
  • For example, agar hum 2,2,2,2,2 ka sum karenge. So, there are 2 methods, first one is- 2+2+2+2+2=10 and the second one is 2*5=10. So we know that the optimum solution is 2*5 = 10, so we use this to solve the problem. So, this is the real world example of greedy method, jisme hum various solutions mein se sabse jyada effective solution ko use karke problem ko solve karte hain.
  • The greedy method is used in -
  1. Dijkstra's Tree Algorithm
  2. Travelling Salesman Problem
  3. Kruskal's Tree Algorithm
  4. Graph (Map coloring and Vector cover)
  5. Job scheduling problem, and so on.

3. DYNAMIC PROGRAMMING
  • Dynamic programming same divide and conquer rule par based hai.
  • But the difference is that, divide and conquer technique mein hum jo small units mein divide karte hain wo small units ko hum process bhi karte hain but dynamic programming mein aisa nahi hota hai.
  • Jab small units mein divide karte hain, so that their result can be re-used.
  • Dynamic programming mein memoization concept ko use kiya jata hai. 
  • Optimum solution is achieved.
  • The dynamic programming is used in - 
  1. Fibonacci number series
  2. Tower of hanoi
  3. Dijkstra's shortest path
  4. Knapsack problem
  5. Project scheduling, and so on.

4. Back Tracking
  • Back tracking technique mein hum ek problem ke multiple solutions ko apply karke dekhta hain and then jo efficient hai usse problem ko solve kiya jata hai.
  • It uses brute force approach.
  • Hum multiple solutions ko use karte hain hai problem solving ke liye.
  • Dynamic programming mein optimum solution ko consider karte hain but back tracking mein nahi .
  • Jaise ek puzzle hota hai, usme multiple solutions hote hain and hum sabhi solutions ko apply karke dekhte hain then jo bhi uska combination hota hai wo use kiya jata hai. So, puzzle is a real wold example of backtracking technique. 
  • Back tracking is used in -
  1. Puzzle, crosswords, Sudoku
  2. Graph coloring problem
  3. n queen problem
  4. Tower of hanoi problem
  5. Hamilton cycle problem, and so on.

5. BRANCH AND BOUND
  • Branch and bound technique bhi same backtracking ki tarah hoti hai.
  • Branch and bound mein bhi hum multiple solutions ko consider karte hain.
  • Difference between branch and bound and backtracking is that, branch and bound mein hum optimum solution and minimization ko hi consider karte hain but backtracking mein hum ise consider nahi karte hain.
  • Branch and bound is used in -
  1. Knapsack 
  2. Travelling salesman problem
  3. Water jug problem, and so on..


Best of Luck Students,
 Do visit our website regularly for more content and for daily tests.

Regards,
UGC NET EXPERTS