Lecture 4: Introduction to Code Analysis CSE 373:

Lecture 4: Introduction to Code Analysis CSE 373: Data Structures and Algorithms CSE 373 19 SP - KASEY CHAMPION 1 5 Minutes Warm Up Read through the code on the worksheet given Come up with a test case for each of the described test categories Expected Behavior add(1) add(null) Forbidden Input Empty/NullAdd into empty list Add enough values to trigger internal array double and copy Boundary/Edge ScaleAdd 1000 times in a row Socrative: www.socrative.com Room Name: CSE373 Please enter your name as: Last, First CSE 373 SP 18 - KASEY CHAMPION

2 Administrivia - Fill out HW 2 Partner form Posted on class webpage at top Due TONIGHT Monday 4/8 by 11:59pm - Fill out Student Background Survey, on website announcements - Read Pair Programming Doc (on readings for Wednesday on calendar) CSE 373 SP 18 - KASEY CHAMPION 3 Algorithm Analysis CSE 373 SP 18 - KASEY CHAMPION 4 Code Analysis How do we compare two pieces of code? -Time needed to run -Memory used -Number of network calls -Amount of data saved to disk -Specialized vs generalized -Code reusability -Security CSE 373 SP 18 - KASEY CHAMPION

5 Comparing Algorithms with Mathematical Models Consider overall trends as inputs increase - Computers are fast, small inputs dont differentiate - Must consider what happens with large inputs Identify trends without investing in testing Model performance across multiple possible scenarios - Worst case - what is the most expensive or least performant an operation can be - Average case what functions are most likely to come up? - Best case if we understand the ideal conditions can increase the likelihood of those conditions? CSE 373 SP 19 - KASEY CHAMPION 6 Review: Sequential Search sequential search: Locates a target value in a collection by examining each element sequentially - Example: Searching the array below for the value 42: 1 index 0 1 2

value -4 2 7 3 4 5 6 7 8 9 10 15 20 22 25 30 36 0 4 2 11 12 13 14 15 16

50 56 68 85 92 103 i public int search(int[] a, int val) { for (int i = 0; i < a.length; i++) { if (a[i] == val) { return i; } } return 1; } How many elements will be examined? - What is the best case? element found at index 0, 1 item examined, O(1) - What is the worst case? element found at index 16 or not found, all elements examined, O(n) - What is the average case? most elements examined, O(n) f(n) = n CSE 373 SP 19 KASEY CHAMPION (THANKS TO ZORAH FUNG) 8 Review: Binary Search binary search: Locates a target value in a sorted array or list by successively eliminating half of the array from consideration. - Example: Searching the array below for the value 42: index 0 1 2 value -4 2 7 3 4 5 6 7 8 9 10 15 20 22 25 30 36

public static void binarySearch(int[] a, int val){ min while (first <= last){ if (arr[mid] < key ){ first = mid + 1; } else if ( arr[mid] == key ){ return mid; } else{ last = mid - 1; } mid = (first + last)/2; } return -1; } mid 1 0 11 12 13 14 15 16 4 2 50 56 68 85 92 103 ma x How many elements will be examined? - What is the best case? element found at index 8, 1 item examined, O(1) - What is the worst case? element found at index 9 or not found, elements examined, O(?) - What is the average case? CSE 373 SP 19 KASEY CHAMPION (THANKS TO ZORAH FUNG) 9 Analyzing Binary Search Finishes when =1 2 =1 2 What is the pattern? - At each iteration, we eliminate half of the remaining elements -> multiply right side by 2K How long does it take to

finish? N = 2K - 1st iteration N/2 elements remain - 2nd iteration N/4 elements remain - Kth iteration - N/2k elements remain index 0 1 2 value -4 2 7 3 4 5 -> isolate K exponent with logarithm

log2N = k 6 7 8 9 10 15 20 22 25 30 36 1 0 11 12 13 14 15 16 4 2 50 56 68 85 92 103 CSE 373 SP 18 - KASEY CHAMPION 10 Asymptotic Analysis asymptotic analysis the process of mathematically representing runtime

of a algorithm in relation to the number of inputs and how that relationship changes as the number of inputs grow Two step process 1. Model reduce code run time to a mathematical relationship with number of inputs 2. Analyze compare runtime/input relationship across multiple algorithms CSE 373 SP 18 - KASEY CHAMPION 11 Code Modeling CSE 373 SP 18 - KASEY CHAMPION 12 Code Modeling code modeling the process of mathematically representing how many operations a piece of code will run in relation to the number of inputs n Examples: - Sequential search ( )= - Binary search ( )= 2 Assume all operations run in equivalent time What counts as an operation? Basic operations

Function calls - Adding ints or doubles - Count runtime of function body - Variable assignment Conditionals - Variable update - Time of test + worst case scenario branch - Return statement - Accessing array index or object field Loops Consecutive statements - Sum time of each statement - Number of iterations of loop body x runtime of loop body CSE 373 SP 18 - KASEY CHAMPION 13 Modeling Case Study Goal: return true if a sorted array of ints contains duplicates Solution 1: compare each pair of elements public boolean hasDuplicate1(int[] array) { for (int i = 0; i < array.length; i++) { for (int j = 0; j < array.length; j++) { if (i != j && array[i] == array[j]) { return true; } } } return false;

} Solution 2: compare each consecutive pair of elements public boolean hasDuplicate2(int[] array) { for (int i = 0; i < array.length - 1; i++) { if (array[i] == array[i + 1]) { return true; } } return false; } CSE 373 WI 18 MICHAEL LEE 14 Modeling Case Study: Solution 2 ( ) Goal: produce mathematical function representing runtime array.length where n = Solution 2: compare each consecutive pair of elements public boolean hasDuplicate2(int[] array) { loop = (n 1)(body) for (int i = 0; i < array.length - +4 1; i++) { If statement = 5 if (array[i] == array[i + 1]) { +1 return true; } } return false; +1 } Approach ( )=5 ( 1 ) +1 linear -> O(n) -> start with basic operations, work inside out for control structures - Each basic operation = +1 - Conditionals = worst case test operations + branch - Loop = iterations (loop body) CSE 373 WI 18 MICHAEL LEE 15 Modeling Case Study: Solution 1 Solution 1: compare each consecutive pair of elements public boolean hasDuplicate1(int[] array) { for (int i = 0; i < array.length; i++) { x n for (int j = 0; j < array.length; j++) { x n if (i != j && array[i] == array[j]) { +5 return true; +1 } } } return false; +1 } Approach ( )=5 ( 1 ) +1 quadratic -> O(n2) 6 6n 6n2 -> start with basic operations, work inside out for control structures - Each basic operation = +1 - Conditionals = worst case test operations + branch - Loop = iterations (loop body) CSE 373 WI 18 MICHAEL LEE 16 5 Minutes Your turn! Write the specific mathematical code model for the following code and indicate the big o runtime. public void foobar (int k) { int j = 0; +1 while (j < k) { +k/5 (body) for (int i = 0; i < k; i++) { +k(body) System.out.println(Hello world); +1 ( ) = ( +2 ) 5 quadratic -> O(k^2) } j = j + 5; } } +2 Approach -> start with basic operations, work inside out for control structures Each basic operation = +1 Conditionals = worst case test operations + branch Loop = iterations (loop body) CSE 373 SP 18 - KASEY CHAMPION 17