Slide 1CST 5320Design/Analysis of AlgorithmsLecture 1: Asymptotic Complexity (1)Instructor: Debzani Deb*Things that are ImportantSyllabus is available in Canvas. Read it...

I have an exam( mid-term ). this exam includes four lectures.


Slide 1 CST 5320 Design/Analysis of Algorithms Lecture 1: Asymptotic Complexity (1) Instructor: Debzani Deb * Things that are Important Syllabus is available in Canvas. Read it carefully. Reading Material Asymptotic Complexity Cormen Chapter 2 and 3. Insertion sort Chapter 4:Page 131 to 136. https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/InsertionSort.html Review: Asymptotic Performance Asymptotic performance: How does algorithm behave as the problem size gets very large? Running time Memory/storage requirements Remember that we use the RAM model: All memory equally expensive to access No concurrent operations All reasonable instructions take unit time Except, of course, function calls Constant word size Unless we are explicitly manipulating bits Review: Running Time Number of primitive steps that are executed Except for time of executing a function call most statements roughly require the same amount of time Worst case vs. average case vs. best case * Measuring Input Sizes Algorithm efficiency/complexity is defined as a function of input size. Input size depends on the problem. Sorting – The number of items to be sorted. Graphs – The number of vertices and/or edges Numerical – the number of bits needed to represent a number * * Units for Measuring Running Time Measure the running time using standard unit of time measurements, such as seconds, minutes? Depends on computer speed, # of programs running, etc. count the number of times each of an algorithm’s operations is executed. Difficult and unnecessary count the number of times an algorithm’s basic operation is executed. Basic operation: the most important operation of the algorithm, the operation contributing the most to the total running time. For example, the basic operation is usually the most time-consuming operation in the algorithm’s innermost loop. * Basic Operations Example Basic Operations one arithmetic operation (e.g., +, *). one assignment one comparison (e.g., x >= 0) one read one write When we consider the complexity of an algorithm, we don't really care about the exact number of basic operations that are performed; instead, we care about how the number of basic operations relates to the problem input size. If the input size doubles, does the number of basic operations stay the same? double? increase in some other way? * * Input Size and Basic Operation Examples ProblemInput size measureBasic operation Search for a key in a list of n itemsNumber of items in list, ncomparison Sort a list of n elementsNumber of items in the list, ncomparison Add two n by n matricesMatrix dimension or total number of elements Addition Find the first element of a listNumber of items in list, nread Initialize all items of a list with value 99.Number of items in list, nassignment * * Worst case Efficiency Efficiency (# of times the basic operation will be executed) for the worst case input of size n. The algorithm runs the longest among all possible inputs of size n. Best case Efficiency Efficiency (# of times the basic operation will be executed) for the best case input of size n. The algorithm runs the fastest among all possible inputs of size n. Average case Efficiency: Efficiency (#of times the basic operation will be executed) for a typical/random input of size n. Worst-Case, Best-Case, and Average-Case Efficiency * Algorithmic complexity/efficiency To find the efficiency of an algorithm, follow the below steps What is the input size? What is its basic operation? How many times is the basic operation executed? Is there any best, worst or average case for this algorithm, or all cases are equal? What is the efficiency class of this algorithm? An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 30 10 40 20 0 1 2 3 i =  j = key =  A[j] =  A[j+1] =  An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 30 10 40 20 0 1 2 3 i = 1j = 0key = 10 A[j] = 30 A[j+1] = 10 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 30 30 40 20 0 1 2 3 i = 1j = 0key = 10 A[j] = 30 A[j+1] = 30 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 30 30 40 20 0 1 2 3 i = 1j = 0key = 10 A[j] = 30 A[j+1] = 30 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 30 30 40 20 0 1 2 3 i = 1j = -1key = 10 A[j] =  A[j+1] = 30 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 30 30 40 20 0 1 2 3 i = 1j = -1key = 10 A[j] =  A[j+1] = 30 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 10 30 40 20 0 1 2 3 i = 1j = -1key = 10 A[j] =  A[j+1] = 10 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 10 30 40 20 0 1 2 3 i = 2j = -1key = 10 A[j] =  A[j+1] = 10 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 10 30 40 20 0 1 2 3 i = 2j = -1key = 40 A[j] =  A[j+1] = 10 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 10 30 40 20 0 1 2 3 i = 2j = -1key = 40 A[j] =  A[j+1] = 10 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 10 30 40 20 1 2 3 4 i = 2j = 1key = 40 A[j] = 30 A[j+1] = 40 0 1 2 3 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 10 30 40 20 1 2 3 4 i = 2j = 1key = 40 A[j] = 30 A[j+1] = 40 0 1 2 3 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 10 30 40 20 1 2 3 4 i = 2j = 1key = 40 A[j] = 30 A[j+1] = 40 0 1 2 3 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 10 30 40 20 1 2 3 4 i = 2j = 1key = 40 A[j] = 30 A[j+1] = 40 0 1 2 3 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 10 30 40 20 1 2 3 4 i = 3j = 1key = 20 A[j] = 30 A[j+1] = 40 0 1 2 3 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 10 30 40 20 1 2 3 4 i = 3j = 1key = 20 A[j] = 30 A[j+1] = 40 0 1 2 3 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 10 30 40 20 1 2 3 4 i = 3j = 2key = 20 A[j] = 40 A[j+1] = 20 0 1 2 3 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } } 10 30 40 20 1 2 3 4 i = 3j = 2key = 20 A[j] = 40 A[j+1] = 20 0 1 2 3 An Example: Insertion Sort InsertionSort(A, n) { for i = 1 to n { key = A[i] j = i - 1; while (j >= 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } 10 30 40 40 1 2 3 4 i = 3j = 2key = 20