E Lesson 4

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

MCA 2 All right are reserved with CU-IDOL DESIGN AND ANALYSIS OF ALGORITHMS Course Code: MCA 632 Semester: Third e-Lesson: 4  SLM Unit: 5 www.cuidol.in Unit-5(MCA 632)

Design and Analysis of Algorithms 33 OBJECTIVES INTRODUCTION  Student will be able to define concept of algorithm  In this unit we are going to learn about algorithm analysis quick sort and merge sort specification and analysis.  Student will be able to learn about divide and conquer  Student will be able to learn about quick sort and  Under this you will learn and understand the merge sort concept of divide and conquer.  Knowledge about Topological sort  Topological sort www.cuidol.in Unit-5(MCAC6M3-26)13) INASllTIrTiUghTEt aOrFe DreISsTeArNveCdE wANithD COUN-LIIDNOELLEARNING

TOPICS TO BE COVERED 4 Divide and Conquer: General method Binary search Merge sort Quick sort Advantages and disadvantages of divide and conquer. Decrease and Conquer approach: Topological Sort.. www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Divide and Conquer 5 Divide-and conquer is a general algorithm design paradigm:  Divide: divide the input data S in two or more disjoint subsets S1, S2, …  Recursive: solve the sub problems recursively  Conquer: combine the solutions for S1, S2, …, into a solution for S www.cuidol.in Fig. 2.1: Divide & Conquer All right are reserved with CU-IDOL Unit-5(MCA 632)

Binary Search 6 • The binary search algorithm uses the divide-and-conquer strategy to search through an array • The array must be sorted – the “zeroing in” strategy for looking up a word in the dictionary won’t work it the words are not in alphabetical order. – binary search will not work unless the array is sorted. www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Binary Search(Cont..) 7 To search a list of n items, • first look at the item in location n/2 • then search either the region from 0 to n/2-1 or the region from n/2+1 to n-1 • Example: searching for 57 in a sorted list of 15 numbers start in the middle www.cuidol.in Fig. 2.2: Binary Search All right are reserved with CU-IDOL Unit-5(MCA 632)

Binary Search(Cont..) 8 • The heart of the algorithm contains these operations: mid = (lower + upper) / 2 return mid if k == a[mid] upper = mid if k < a[mid] lower = mid if k > a[mid] • The first iteration when searching for 57 in a list of size 15: lower = -1 mid = 14 / 2 = 7 upper for next iteration: upper = 15 7 Fig. 2.3: Binary Search www.cuidol.in All right are reserved with CU-IDOL Unit-5(MCA 632)

Translating a Problem into 9 an Algorithm(cont..) • Step III - Coding void sort(int *a, int n) { for (i= 0; i< n; i++) { int j= i; for (int k= i+1; k< n; k++){ if (a[k ]< a[ j]) j= k; int temp=a[i]; a[i]=a[ j]; a[ j]=temp; } } www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Contd… mid = (lower + upper) / 2return mid if k == a[mid]upper = mid if k < 10 a[mid]lower = mid if k > a[mid] • To heart of the algorithm contains these operations: mid = (lower + upper) / 2 return mid if k == a[mid] upper = mid if k < a[mid] lower = mid if k > a[mid] • The first iteration when searching for 57 in a list of size 15: [ * ] • ... ] [ * Fig. 2.4: Binary Search www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Divide and Conquer Sorting 11 Algorithms • The divide and conquer strategy used to make a more efficient search algorithm can also be applied to sorting • Two well-known sorting algorithms: QuickSort – divide a list into big values and small values, then sort each part Merge Sort – sort subgroups of size 2, merge them into sorted groups of size 4, merge those into sorted groups of size 8, ... • The remaining slides will have an overview of each algorithm, and a look at how Merge Sort can be implemented in Ruby www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Merge Sort 12 • The merge sort algorithm works from “the bottom up” • start by solving the smallest pieces of the main problem • keep combining their results into larger solutions • eventually the original problem will be solved • Example: sorting playing cards • divide the cards into groups of two • sort each group -- put the smaller of the two on the top • merge groups of two into groups of four • merge groups of four into groups of eight www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Merge sort Algorithm 13 Algorithm For Merge Sort: Algorithm MergeSort(low,high) //a[low:high] is a global array to be sorted //Small(P) is true if there is only one element //to sort. In this case the list is already sorted. { if (low<high) then //if there are more than one element { //Divide P into subproblems //find where to split the set mid = [(low+high)/2]; www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Merge sort algorithm 14 //solve the subproblems. mergesort (low,mid); mergesort(mid+1,high); //combine the solutions . merge(low,mid,high); } } www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Merge Sort Algorithm 15 • Algorithm: Merging 2 sorted subarrays using auxiliary storage. • Algorithm merge(low,mid,high) • //a[low:high] is a global array containing • //two sorted subsets in a[low:mid] • //and in a[mid+1:high].The goal is to merge these 2 sets into • //a single set residing in a[low:high].b[] is an auxiliary global array. •{ • h=low; I=low; j=mid+1; • while ((h<=mid) and (j<=high)) do www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

{ 16 if (a[h]<=a[j]) then { Unit-5(MCA 632) All right are reserved with CU-IDOL b[I]=a[h]; h = h+1; } else { b[I]= a[j]; j=j+1; } I=I+1; } if (h>mid) then for k=j to high do www.cuidol.in

Merge Sort Algorithm 17 { b[I]=a[k]; I=I+1; } else for k=h to mid do { b[I]=a[k]; I=I+1; } for k=low to high do a[k] = b[k]; } www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Merge Sort 18 All right are reserved with CU-IDOL • The merge sort algorithm works from “the bottom up” • start by solving the smallest pieces of the main problem • keep combining their results into larger solutions • eventually the original problem will be solved • Example: sorting playing cards • divide the cards into groups of two • sort each group -- put the smaller of the two on the top • merge groups of two into groups of four • merge groups of four into groups of eight www.cuidol.in Unit-5(MCA 632)

Quick Sort 19 • Quick Sort is another divide-and-conquer sorting algorithm • The main idea is to partition the array into two regions: • small items are moved to the left side of the array • large items are moved to the right side • After partitioning, repeat the sort on the left and right sides • each region is a sub-problem, a smaller version of the original problem • Main question: how do we decide which items are “small” and which are “large”? • A common technique: use the first item in the region as a pivot • everything less than the pivot ends up in the left region • items greater than or equal to the pivot go in the right region www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Quick Sort Algorithm 20 Quick Sort Pivot Algorithm Step 1 − Choose the highest/lowest index value has pivot Step 2 − Take two variables to point left and right of the list excluding pivot Step 3 − left points to the low index Step 4 − right points to the high Step 5 − while value at left is less than pivot move right Step 6 − while value at right is greater than pivot move left Step 7 − if both step 5 and step 6 does not match swap left and right Step 8 − if left ≥ right, the point where they met is new pivot www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Quick Sort Algorithm 21 Quick Sort Algorithm Using pivot algorithm recursively, we end up with smaller possible partitions. Each partition is then processed for quick sort. We define recursive algorithm for Quick sort as follows : Step 1 − Make the right-most index value pivot Step 2 − partition the array using pivot value Step 3 − quick sort left partition recursively Step 4 − quick sort right partition recursively www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Best Case of Quick 22 Sort Using big-Θ notation, we get the same result as for merge sort:Θ(nlog2​n). www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Worst Case of Quick Sort 23 www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Worst case complexity 24 When we total up the partitioning times for each level, we get cn + c(n-1) + c(n-2) +….+ 2c = c(n + (n-1) + (n-2) + …. + 2) = c((n+1)(n/2) - 1) ​ We subtract 1 because for quicksort, the summation starts at 2, not 1. We have some low-order terms and constant coefficients, but when we use big-Θ notation, we ignore them. In big-Θ notation, quicksort's worst-case running time is Θ(n^2) www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Advantages of Divide and 25 Conquer •Complexity can be reduced using the concepts of divide and conquer. •Logical structures ensure clear flow of control. •Increase in productivity by allowing multiple programmers to work on different parts of the project independently at the same time. •Modules can be re-used many times, thus it saves time, reduces complexity and increase reliability. •Easier to update/fix the program by replacing individual modules rather than larger amount of code. •Ability to either eliminate or at least reduce the necessity of employing GOTO statement. www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Disadvantages of Divide and Conquer 26 • Problem decomposition may be very complex and thus not really suitable to divide and conquer. • Recursive nature of the solution may end up duplicating sub-problems, dynamic solutions may be better in some of these cases, like Fibonacci. • Recursion into small/tiny base cases may lead to huge recursive stacks, and efficiency can be lost by not applying solutions earlier for larger base cases. www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Topological Tsooporlotgical Sorting 27 A directed acyclic graph or DAG is a directed graph with no directed cycles: Topological sort of a DAG: Linear ordering of all vertices in graph G such that vertex u comes before vertex v if edge (u, v) G We have a set of tasks and a set of dependencies (precedence constraints) of form “task A must be done before task B” Topological sort: An ordering of the tasks that conforms with the given dependencies Two methods of topological sort are Adjacent metrics and DFS. www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Topological Sorting 28 A topological sorting of this graph is: 1 2 3 4 5 There are multiple topological sorting possible for a graph. For the graph given above one another topological sorting is: 1 2 3 5 4 www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

Topological Sort(Kahn) Algorithm L ← Empty list that will contain the sorted elements 29 S ← Set of all nodes with no incoming edge while S is non-empty do remove a node n from S add n to tail of L for each node m with an edge e from n to m do remove edge e from the graph if m has no other incoming edges then insert m into S if graph has edges then return error (graph has at least one cycle) else return L (a topologically sorted order) www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONES 1 Which of the following algorithms is a divide & conquer algorithm by nature? 30 a) Euclidian algorithm to give GCD b) Heap Sort c) Fourier Transform d) Quick Sort 2 The time complexity of quick sort is ........ b) O(logn) a) O(n) d) O(n logn) c) O(n2) 3 Quick sort uses b) Greedy approach a) Divide and Conquer d) Backtracking c) linear method 4. The complexity of merge sort is b) O(n^2) a)O(n) d)O(n log n) c) O (log n) 5. Merge sort uses b) Greedy approach a) Divide and Conquer d) Backtracking c) linear method Answers:1.d) 2.d) 3.a) 4.d) 5.a) www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

SUMMARY 31 This presentation includes unit 5 for Design and analysis of algorithms. Divide and Conquer is one of the most important concept of this subject. We need to divide the array in two or multiple parts then solve the subproblems and again combine the solution to get the answer of main problem. Merge sort,Quick sort, Topological sort are based on divide and conquer and Decrease and conquer. www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

FREQUENTLY ASKED QUESTION 32 Q1. What do you mean by divide and conquer technique. Ans. A large problem is divided into multiple subproblems and then solve and further combine the solutions to get the solution of major problem.. (For Further details please refer to the SLM) Q2. Discuss the complexity of binary search . Ans. O(log n) (For Further details please refer to the SLM) Q3. Discuss about pivot element. Ans. Pivot element is an element which is used in quick sort to sort the element first. (For Further details please refer to the SLM) www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

REFERENCES 33 1) Data Structures and Algorithms made easy By Narasimha Karumanchi. 2) The Algorithm Design Manual, 2nd Edition by Steven S Skiena 3) Fundamentals of Computer Algorithms - Horowitz and Sahani 4) https://www.geeksforgeeks.org/quick-sort/ 5)https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_divide _conquer.htm www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL

34 THANK YOU www.cuidol.in Unit-5(MCA 632) All right are reserved with CU-IDOL