Lecture 4: Introduction to Code Analysis CSE 373:

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

Recently Viewed Presentations

  • Ch. 14 Revolutions in Russia

    Ch. 14 Revolutions in Russia

    Czars Resist Change. In 1881 Alexander III assumed the Russian throne and stopped all reforms. Will cling to principles of autocracy (gives him total power) Anyone who questioned his authority questioned the government, the Russian Orthodox church and society as...
  • The Reading Revelations 7:9-17 Revelation Victory of Christ

    The Reading Revelations 7:9-17 Revelation Victory of Christ

    Hello Brother Eric, can you help me understand what exactly is the meaning, of the 144,000 thousand that God sealed in the book of Revelation?. Also, there are two . groups. T. he "144,000 and the Great multitude", who are...
  • Cliche is an over used common expression. The

    Cliche is an over used common expression. The

    Literary analysis of theme within a thesis statement: Though F. Scott Fitzgerald's The Great Gatsby is a timeless work of fiction, the novel shows how unbridled materialism destroyed the American Dream in the Jazz Age. In The Great Gatsby, F....
  • Topic 1: Understanding Place Value

    Topic 1: Understanding Place Value

    Essential Question: What are the standard procedures for estimating and finding quotients involving decimals?
  • Mass Communication

    Mass Communication

    Verdana Arial Wingdings Competition 1_Competition MASS COMMUNICATION THEORY THEORIES OF MASS COMMUNICATION THEORIES OF MASS COMM Cultivation Theory - Gerbner CULTIVATION THEORY ASSUMPTIONS OF CULTIVATION THEORY USES & GRATIFICATION THEORY - Katz, Blumer & Gurevitch USES & GRATIFICATION ASSUMPTIONS OF...
  • Identification & Management of Red and Blue Species/Ecological

    Identification & Management of Red and Blue Species/Ecological

    INTRODUCTION. The conservation of species and plant communities at risk is a fundamental component of sustainable forest management. Rare and endangered species, their habitats, and plant communities need to be addressed and managed with a particular level of urgency, due...
  • The Just War Theory - University of Aberdeen

    The Just War Theory - University of Aberdeen

    2. Right intention. The war must be pursued for a just cause. United Nations Charter Article 2: "All members shall refrain in their international relations from the threat or the use of force against the territorial integrity or political independence...
  • Graduate Application Project Design Concept Walkthrough BACKGROUND  Design

    Graduate Application Project Design Concept Walkthrough BACKGROUND Design

    Design concept for new graduate application built from feedback from: Associate Deans, meeting (September 2011) Graduate Assistants, town hall meetings, survey (December 2011) Oracle Training (March 2012) Prototyping (May 2012 to November 2012)