PRESENTATION OF DIVIDE AND CONQUER

Download
Share  Add to  Flag Embed
Views:
 
Category: Education
     
 
License:   All Rights Reserved

Presentation Description

VERY UNDERSTANDABLE

Comments

 

By: danz123 (24 month(s) ago)

very informative presentation

Presentation Transcript

In The Name Of Allah Most Beneficial The Most Merciful : 

5A-1 In The Name Of Allah Most Beneficial The Most Merciful

Slide 2: 

What is divide and conquer Implementation on merge sort What is decrease and conquer Implementation on binary search For difficult problems SUB-TOPICS:

DIVIDE & CONQUER : 

DIVIDE & CONQUER Divide problem into sub-problems. Conquer by solving sub-problems recursively. Combine the solutions of sub-problems into a solution of the original problem.

MERGESORT: DIVIDE STEP : 

5A-4 MERGESORT: DIVIDE STEP Step 1 – Divide

MERGESORT: CONQUER STEP2 : 

5A-5 MERGESORT: CONQUER STEP2 Step 2 – Conquer

DECREASE AND CONQUER : 

5A-6 DECREASE AND CONQUER In some where each problem generates only one subproblem. Such as the binary search algorithm for finding a record in a sorted list. Although some authors call this case decrease and conquer.

Binary Search : 

5A-7 Binary Search Binary search can perform operation find(k) on a dictionary implemented by means of an array-based sequence, sorted by key similar to the high-low game at each step, the number of candidate items is halved terminates after O(log n) steps Example: find(7) 1 3 4 5 7 8 9 11 14 16 18 19 1 3 4 5 7 0 0 m l h l h 8 9 11 14 16 18 19 m 4 5 7 l=m =h 1 3 4 5 7 0 m l h

SOLVING DIFFICULT PROBLEMS : 

5A-8 SOLVING DIFFICULT PROBLEMS Divide and conquer is a powerful tool for solving conceptually difficult problems. such as the classic Tower of Hanoi puzzle.

Slide 9: 

9 TOWER OF HANIO

Slide 10: 

5A-10 Continou...! By M.Faizan Khan

TOPIC ARE…! : 

5A-11 TOPIC ARE…! ALGORITHM EFFICIENCY PARALLELISM MEMORY ACCESS RECURSION

ALGORITHM EFFICIENCY : 

5A-12 ALGORITHM EFFICIENCY The divide-and-conquer paradigm often helps in the discovery of efficient algorithms. It was the key. for example, to Karatsuba's fast multiplication method The algorithm invented by A.Karatsuba in 1960 that could multiply to n-digit no in operation Operation may be O(n2) would be required for task.

PARALLELISM : 

5A-13 PARALLELISM Divide and conquer algorithms are naturally adapted for execution in multi-processor machines, Especially shared-memory systems. Where the communication of data between processors does no need to be planned in advance.

MEMORY ACCESS : 

5A-14 MEMORY ACCESS Divide-and-conquer algorithms naturally tend to make efficient use of memory caches. The reason is that once a sub-problem is small enough, it and all its sub-problems can, in principle, be solved within the cache, without accessing the slower main memory. An algorithm desinged to exploit the cache in this way is called cache oblivious.

RECURSION : 

5A-15 RECURSION Divide and conquer algorithms are naturally implemented as Recursive Procedures. The partial sub-problems leading to the one currently being solved are automatically stored in the Procedure call stack.

Slide 16: 

5A-16 Continou...! By M.Owais Siddique

TOPIC ARE…! : 

5A-17 TOPIC ARE…! EXPLICIT STACK STACK SIZE SHARING REPEATED SUBPROBLEMS

EXPLICIT STACK : 

5A-18 EXPLICIT STACK Divide and conquer algorithms can also be implemented by a non-recursive program. Stores the partial sub-problems in some explicit data structure. This approach allows more freedom in the choice of the sub-problem that is to be solved next,

STACK SIZE : 

5A-19 STACK SIZE In D & Conquer there is sufficient memory allocated for the recursion stack. Fortunately, D&C algorithms that are time-efficient

SHARING REPEATED SUBPROBLEMS : 

5A-20 SHARING REPEATED SUBPROBLEMS In such cases it may be worth identifying and saving the solutions to these overlapping subproblems. A technique commonly known as memoization.

Slide 21: 

5A-21 END THANK YOU