Divide and Conquer Algorithms - Dr. Maram Bani Younes

This chapter on divide and conquer algorithms introduces key concepts such as dividing the problem into smaller subproblems, solving them, and combining the solutions. It covers techniques like finding maximum and minimum elements, maximum contiguous subsequence sum, binary search, quick sort, merge sort, and heap sort. The algorithm for finding maximum and minimum elements in a set of numbers is explained in detail. Additionally, examples and explanations are provided to help understand the core principles of divide and conquer algorithms effectively.

• Divide and Conquer
• Algorithms
• Dr. Maram Bani Younes
• Maximum Contiguous Subsequence Sum
• Binary Search

ale_sc Follow

Uploaded on Sep 24, 2024 | 1 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. DIVIDE AND CONQUER CHAPTER 4 DR. MARAM BANI YOUNES

2. CONTENTS Divide and conquer Algorithm Max and Min Maximum Contiguous Subsequence SUM Binary Search Quick Sort Merge Sort Heap Sort

3. DIVIDE AND CONQUER: (DIVIDE, CONQUER, COMBINE) The idea is to divide the problem into smaller but similar sub problems (divide), solve it (conquer), and (combine) these solutions to create a solution to the original problem. - - -

4. PROBLEM Finding the maximum and minimum elements in a set of (n) elements using the straightforward algorithm.

5. ALGORITHM: MAX AND MIN Algorithm straightforward (a, n, max, min) Input: array (a) with (n) elements Output: max: max value, min: min value max = min = a(1) for i = 2 to n do begin if (a(i)>max) then max=a(i) if (a(i)<min) then min=a(i) end end best= average =worst= 2(n-1) comparisons

6. ALGORITHM: MAX AND MIN If we change the body of the loop as follows: best case: elements in increasing order No. of comparisons = (n-1) Worst case: elements in decreasing order No. of comparisons = 2(n-1) Average case: a(i) is greater than max half the time No. of comparisons= 3n/2 3/2 ((n-1)+(2n-2)) max=min=a(1) for i=2 to n do begin if (a(i)>max) then max=a(i) else if (a(i)<min) then min=a(i) end

7. PROBLEM: IS TO FIND THE MAXIMUM AND MINIMUM ITEMS IN A SET OF (N) ELEMENTS.

8. EXAMPLE Given a set of n elements. Write an algorithm using divide and conquer, to find the summation of its elements.

10. THE MAXIMUM CONTIGUOUS SUBSEQUENCE SUM Given (possibly negative) integers , find (and identify the sequence corresponding to) the maximum value of . The maximum contiguous subsequence sum is zero if all the integers are negative. Suppose we are given the following input {-2, 11, -4, 13, -5, 2} The maximum contiguous subsequence sum is (20), which encompassing items 2 through 4.

11. DIVIDE AND CONQUER APPROACH Let consider a divide and conquer algorithm: We divide the input into two halves. The max contiguous subsequence sum can occur in one of 3 ways: Case1: It resides entirely in the 1st half. Case2: It resides entirely in the 2nd half. Case3: It begins in the 1st half but ends in the 2nd half. 1) Recursively compute the max contiguous subsequence sum that resides entirely in the 1st half. 2) Recursively compute the max contiguous subsequence sum that resides entirely in the 2nd half. 3) Compute via two consecutive loops the max contiguous subsequence sum that begins in the 1st but ends in the 2nd. 4) Choose the largest of the 3 sums.

12. + 2 1 C n for n n = C 2 n = 1 1 n = + 2 C C n n n 2 = + + 4 C n n n 4 k = = + k 2 C n 1 1 i = + ( lg ) O n n n

13. BINARY SEARCH , 1 ai i n Let nondecreasing order. Consider the problem of determining whether a given element x is present in the list. If x is present, we are to determine a value j such that . x aj= If x is not in the list, then j is set to be zero. , be a list of elements that are sorted in

15. QUICK SORT ALGORITHM Given the following set of data: 42 23 74 11 65 58 94 36 99 87 1st pass {11 23 36} 42 {65 58 94 74 99 87} 2nd pass 11 {23 36} 42 {65 58 94 74 99 87} Last pass 11 23 36 42 58 65 74 87 94 99

17. QUICK SORT DISCUSSION Quick Sort uses about (1.38nlgn) comparisons on the average. The precise recurrence formula for the number of comparisons used by Quick Sort for a random permutation of n elements is: ( 1 1 1 = = C C With Worst Case + = 0 n C n This is equal to: ( ) ( 2 1 2 k k = = = There is a simple solution to the problem of poor performance instead of using the 1st element of the array as the partitioning element; we could generate a random number (r), where r is in the range of 1 to the number of elements in the partition. n ) = k = + + + 2 C n C C for n 1 n k n k n 0 1 0 2 C n for n 1 n = 1 ( 1 ) n n n 2 ) n

18. QUICK SORT DISCUSSION Although the worst case is still , it is extremely unlikely that we will encounter it. The probability of encounter the worst case is , where n is the number of elements in the file. Another method is the median-of-three. We choose the median of the left element, the right element, and the one halfway between them. Unless this median is already the left element, we exchange it with left.

19. SPACE USAGE Quick Sort is not working in-place sort. While the algorithm is working on one sublist, the beginning and ending indexes (borders) of all the other sublists must be saved on a stack. The size of the stack depends on the no. of sublists into which the list will be split. The worst case amount of space used by stack is .

20. MERGE SORT We use the merge procedure as the basis for merge sort. If we have two sets of numbers that are already sorted, we can merge them together with one scan. Let the 1st set be ( n a a a , , , 2 1 ( ) m b b b , , , 2 1 . Assume that both sets are sorted in increasing order. Scan the 1st set until the right place to insert from that place until the right place to insert and so on. ) , and the 2nd set be 1 b is found, and insert it, then continue the scan b is found 2

21. MERGE SORT It is not working in-place algorithm, since it requires additional storage to copy the merged set.

22. ex: 36 20 17 13 28 14 2315 20 36 13 17 13 17 20 36 14 28 15 23 14 15 23 28 13 14 15 17 20 23 28 36 Notes: The running time of merge sort does not depend on the arrangement of the input values, thus it does not have poor worst case performance. It has the advantage that it sorts a file of n elements in time proportional to (nlgn) even in the worst case. The disadvantage is the extra space proportional to n.

23. HEAP SORT

24. HEAP Is a data structure that is defined by two properties: It is a complete binary tree (implemented using array representation) The values stored in a heap are partially ordered. i.e. there is a relationship between the value stored at any node and the values of its children. (Complete binary trees have all levels except the bottom filled out completely, and the bottom level has all of its nodes filled in from left to right). Heaps are often used to implement priority queues and for external sorting algorithms. There are many situations, both in real life and in computing applications, where we wish to choose the next most important from a collection of people, tasks, or objects.

25. EXAMPLE 19 2 46 16 12 54 64 22 17 66 37 35 Heap 66 64 54 17 37 35 46 2 16 12 22 19 Sorted 2 12 16 17 19 22 35 37 46 54 64 66

26. Building a Heap Example: Build a Heap for the following set of data: 20,15, 3, 12, 81, 7, 70, 20, 10, 1, 102

27. HEAP SORT One way to build a heap is to insert the elements one at a time. Each insertion takes (lg n since the value being inserted can move at most the distance from the bottom of the tree to the top of the tree. We need to insert (n) values with cost of Heap Sort does at most ( 2(n-1)lgn) comparisons of keys in the worst case. It uses fewer than (2nlgn) comparisons to sort n elements. No extra working storage area, except for one record position is required (working in place). ) times in the worst case, ( lg ) n n .

28. lg n n ( ) n = = ) 1 1 ( lg O n = 2 1 i j

29. lg n 2 ( ( ) ) n = = 1 1 lg O n = 1 i n j

30. EXAMPLE Sort the following characters in a decreasing order using the heap sort, showing the steps of building the heap and then the sorting process: COMPLEXITY