E Lesson 2

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: 2 Unit: 3 www.cuidol.in Unit-3(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 specification and analysis. algorithm analysis of sorting and searching algorithms.  Student will be able to calculate time complexity  Under this you will learn and understand the and space complexity of sorting algorithms. concept of string processing and  Student will be able to do searching and string combinatorial problems. processing .  Different types of graph problems. Student will be able to learn about combinatorial  problems. www.cuidol.in Unit-3(MCAQ-613021)) INSTITUTE OF DAIlSlTAriNgChEt aArNeDreOsNeLrvINeEd LwEiAthRNCIUN-GIDOL

TOPICS TO BE COVERED 4 Important Problem Types: Sorting Searching String processing Graph Problems Combinatorial Problems www.cuidol.in Unit-3(MCA 632) All right are reserved with CU-IDOL

Sorting 5 Sorting is the process of arranging a list of elements in a particular order (Ascending or Descending). Insertion Sort Selection Sort Radix Sort Quick Sort Heap Sort www.cuidol.in Unit-3(MCA 632) All right are reserved with CU-IDOL

Searching 6 Search is a process of finding a value in a list of values. In other words, searching is the process of locating given value position in a list of values  Linear Search Binary Search www.cuidol.in Unit-3(MCA 632) All right are reserved with CU-IDOL

Selection sort 7 Algorithm • Step 1 − Set MIN to location 0 • Step 2 − Search the minimum element in the list • Step 3 − Swap with value at location MIN • Step 4 − Increment MIN to point to next element • Step 5 − Repeat until list is sorted This algorithm is not suitable for large data sets as its average and worst case complexities are of Ο(n2), where n is the number of items. www.cuidol.in Unit-3(MCA 632) All right are reserved with CU-IDOL

Bubble Sort 8 • Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted. • Best Case Time Complexity: O(n). Best case occurs when array is already sorted. We assume list is an array of n elements. We further assume that swapfunction swaps the values of the given array elements. begin BubbleSort(list) Unit-3(MCA 632) All right are reserved with CU-IDOL for all elements of list if list[i] > list[i+1] swap(list[i], list[i+1]) end if end for return list end BubbleSort www.cuidol.in

Insertion Sort 9 Step 1 − If it is the first element, it is already sorted. return 1; Step 2 − Pick next element Step 3 − Compare with all elements in the sorted sub-list Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted Step 5 − Insert the value Step 6 − Repeat until list is sorted Average and worst case complexity are of Ο(n2), www.cuidol.in Unit-3(MCA 632) All right are reserved with CU-IDOL

Linear SeLairncehar Search 10 Linear Search ( Array A, Value x) Step 1: Set i to 1 Step 2: if i > n then go to step 7 Step 3: if A[i] = x then go to step 6 Step 4: Set i to i + 1 Step 5: Go to Step 2 Step 6: Print Element x Found at index i and go to step 8 Step 7: Print element not found Step 8: Exit 13-w03w-2w0.c2u0idol.in Unit-3(MCA 632) A1ll0 right are reserved with CU-IDOL

Iterative Binary Search ( Array A, Value x) Binary Search 11 Step 1: Start Step 2: Set Low =0 and High=n-1 Step 3: Repeat step 4 and 5 while(Low<=High) Step 4: Set mid=(Low+High)/2 Step 5: if(A[mid]==x) Print x is at index mid and go to step 7 else if(A[mid]<x) Low=mid+1 else high=mid-1 Step 6: x is not found Step 7: Exit www.cuidol.in Unit-3(MCA 632) A1ll1 right are reserved with CU-IDOL

Data Structures 12 Data structures is a method of organizing large amount of data more efficiently so that any operation on that data becomes easy. Data structures are divided into two types.  Linear Data Structures  Non - Linear Data Structures www.cuidol.in Unit-3(MCA 632) All right are reserved with CU-IDOL

String Processing 13 Definition. A string is a sequence of characters taken from an alphabet A. Example. Given the alphabet A = {a,b,d,y}, one can construct the string a bad baby. Example. Given the modern English alphabet A = {a,b,...,z,A,B,...Z}, one can view this sentence as a string (inclusive of punctuation such as period, space, and comma, as well as delimiters such as parentheses, braces, and brackets). Operations on Strings. Strings can be manipulated by operations such as concatenation, length, substring and pattern recognition. We discuss each of these operations as follows. Definition. Given two strings s and t, the concatenation operation, written as s || t or s + t, appends t to s, such that the last character of s is followed by the first character of t and the remainder of t. Example. Given s = \"hello\" and t = \"dave\" s + t = \"hellodave\". www.cuidol.in Unit-3(MCA 632) All right are reserved with CU-IDOL

Graph 14 A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph can be defined as, A Graph consists of a finite set of vertices(or nodes) and set of Edges which connect a pair of nodes. www.cuidol.in Unit-3(MCA 632) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONES 15 1 The complexity of Binary search algorithm is b) O(log n ) a) O(n) d) O(n log n) c) O(n2) 2 What is the worst case time complexity of insertion sort where position of the data to be inserted is calculated using binary search? A) O(n) B) O(n log n) C) O(n2) D) O(log n2) 3. Which sorting algorithm is faster : b) O(nlog n) a) O(n^2) d) O(n^3) c)O(n+k) www.cuidol.in Unit-3(MCA 632) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONES 16 4. What is the complexity of Selection Sort ? B) O(n^2) A) O(n) D) O(n log n) C) O (log n) 5. Finding the location of any element with given value is called as A) Sorting B) Searching C) Insertion D) Deletion 6. Which sorting algorithm is faster? B) O(n^2) A) O(n) D) O(n log n) C) O (log n) Answers: Unit-3(MCA 632) All right are reserved with CU-IDOL 1.b) 2.c) 3.c) 4.d) 5.b) 6.c) www.cuidol.in

SUMMARY 17 This presentation includes unit 3 for Design and Analysis of Algorithms. It includes searching, sorting , graph problems and combinatorial problems. Sorting has various types like insertion sort, bubble sort, selection sort and heap sort. Searching includes linear search and binary search. Further graph and combinatorial are some advance topics in DAA Multiple sorting and searching techniques are there but we need to choose the best one based on our requirement. www.cuidol.in Unit-3(MCA 632) All right are reserved with CU-IDOL

FREQUENTLY ASKED QUESTION 18 Q1.Differentiate between searching and sorting. Ans. Searching is to locate any existing item and sorting is to arrange existing items. (For Further details please refer to the SLM) Q2. Explain linear search. Ans. Linear search is a method to sort elements in linearly with O(n) complexity. (For Further details please refer to the SLM) Q3. Differentiate between insertion sort and bubble sort. Ans. Check the methods of both sorting in previous slides. (For Further details please refer to the SLM) www.cuidol.in Unit-3(MCA 632) All right are reserved with CU-IDOL

REFRENCES 19 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/string-data-structure/ www.cuidol.in Unit-3(MCA 632) All right are reserved with CU-IDOL

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