Code Analysis and Modeling Techniques in Data Structures and Algorithms

Lecture 6: More Code Analysis, Testing CSE 373: Data Structures and Algorithms CSE 373 19 SP - KASEY CHAMPION 1

Warm Up - Code Modeling Take 3 Minutes Take 3 Minutes public static boolean isPrime(int n) { for (int i = 2; i < n; i++){ if (n % i == 0) { return false; } } return true; } Approach 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) +2 +2 n n - - 2 2 +1 +1 +1 +1 Extra Credit: Extra Credit: Go to PollEv.com/champk Text CHAMPK to 22333 to join session, text 1 or 2 to select your answer Answer: code model: 3? 5or ?1? + ?2 simplified tight-O bound: ?(?) CSE 373 SP 19 - KASEY CHAMPION 2

Administrivia Homework 2 is out! - You should have a repo - If you have issues submitting post on piazza CSE 373 19 SP - KASEY CHAMPION 3

Modeling Complex Loops Write a mathematical model of the following code for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { System.out.println( Hello! ); } } n n +1 +1 n n f(n) = n f(n) = n2 2 Keep an eye on loop bounds! CSE 373 19 WI - KASEY CHAMPION 4

Modeling Complex Loops for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { System.out.print( Hello! ); } Sysem.out.println(); } T(n) = (0 + 1 + 2 + 3 + + i-1) +1 +1 0 + 1 + 2 + 3 + + i 0 + 1 + 2 + 3 + + i- -1 1 n n Definition: Summation How do we model this part? Summations! 1 + 2 + 3 + 4 + + n = ? ? ? = f(a) + f(a + 1) + f(a + 2) + + f(b-2) + f(b-1) + f(b) ?(?) ?=1 ?=? ith iteration iteration On the On the ith of the outer loop of the outer loop 0 1 2 3 Output of Output of ith iteration iteration Hello! Hello! Hello! Hello! Hello! ith ? 1 ? 1 T(n) = What is the Big O? 1 ?=0 ?=0 CSE 373 19 WI - KASEY CHAMPION 5

Simplifying Summations Find closed form using summation identities (given on exams) for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { System.out.println( Hello! ); } } ? 1 ? 1 simplified tight big O closed form ? ? = 1 ?=0 ?=0 ? 1 ? 1 ? 1 ? 1 1 2?2 1 =? ? 1 = ?(??) 1 ? ? ? = 1 = 1 ? = = 2? 2 ?=0 ?=0 ?=0 ?=0 Factoring out a constant ? Gauss s Identity Summation of a constant ? 1 ? ? 1 ? =? ? 1 ? = ?? ?? ? = ? ?(?) 2 ?=0 ?=0 ?=? ?=? CSE 373 19 SP KASEY CHAMPION (THANKS TO MICHAEL LEE) 6

Practice Worksheet #2 Take 3 Minutes Take 3 Minutes public static void primesUpToN(int n) { System.out.print("1 2 "); for (int i = 3; i <= n; i++) { for (int j = 2; j < i; j++){ if (j != i && j % i == 0) { System.out.print(i + " "); break; } } System.out.println(); } +1 +1 +4 +4 ? 1 ? ? 1 +1 +1 5 5 ?=2 ?=3 ?=2 +1 +1 ? 32) =1 + 5((? 2) ? 3 ? ? 15 = 1 + ?=0 ? 3 ?=0 ? 35 = 1 + ?=0 ? 35(? 2) = 1 + 5( ?=0 ? 3? ?=0 ? ? = 1 + ?=3 ?=2 - (n-2)(2)) 2 Adjusting summation bounds Summation of a constant Factoring out a constant Gauss s identity CSE 373 SP 19 - KASEY CHAMPION 7

Definition: Big-O Why ?0? ? ? ? ? = ? We wanted to find an upper bound on our algorithm s running time, but -We don t want to care about constant factors. -We only care about what happens as ? gets large. Big-O ? ? = 10log(?) ? 100 ?(?)is?(? ? )if there exist positive constants ?,?0 such that for all? ?0, ? ? ? ? ? Why ?? ? ? ? ? = 2log(?) We also say that ? ? dominates ?(?) O(g(n)) O(g(n)) is the family or set of all functions that are dominated by g(n) ? ? = log(?) ? 100 CSE 332 SU 18 - ROBBIE WEBER 8

Practice Worksheet #3 Take 3 Minutes Take 3 Minutes Prove the function ? ? =?2 2 3? 2 ? ?2 by finding a ? and ?0. Show your work ?2 2 ? ?2 ? ?? ? =1 3? 2 ? ?2 ? ?? ? = 1 ??? ?0= 1 ??????? ?? ??? ????? ?? ?2 2 3? ? =3 2 ??? ?0= 1 ? ?? ? ?? ? ? ?(?) 2 ??? ?0= 1 2 1 2?2+ ?2 3 2?2 ? ?? ?0= 1 CSE 373 SP 19 - KASEY CHAMPION 9

O, Omega, Theta [oh my?] Big-O is an upper bound upper bound - My code takes at most this long to run Big-Omega is a lower bound lower bound 3.5 3 Big-Omega 2.5 ?(?)is (? ? )if there exist positive constants ?,?0 such that for all ? ?0, ? ? ? ? ? 2 1.5 1 Big Theta is equal to equal to 0.5 0 Big-Theta 0.6 1.2 1.8 2.4 3 3.6 4.2 4.8 5.4 6.6 7.2 7.8 8.4 9.6 0 6 9 12 15 10.2 10.8 11.4 12.6 13.2 13.8 14.4 15.6 16.2 16.8 17.4 f(n)2 O(f(n)) (f(n)) ?(?) is (? ? )if ? ? is ?(? ? ) and ? ? is (? ? ). CSE 332 SU 18 - ROBBIE WEBER 10

Practice Worksheet #4 Take 2 Minutes Take 2 Minutes What is the tight big-O bound? O(n) isPrime runtime 600 O(n) 500 What is the tight big- bound? 400 (1) 300 What is the big- bound? 200 Doesn t exist :/ 100 (1) 0 111 123 135 147 159 171 183 195 207 219 231 243 255 267 279 291 303 315 327 339 351 363 375 387 399 411 423 435 447 459 471 483 495 3 15 27 39 51 63 75 87 99 CSE 373 SP 19 - KASEY CHAMPION 11

Viewing O as a class Big-O can also be defined as a family or set of functions. O(? ? )is the set of all functions ? ?such that there exist positive constants?,?0such that for all ? ?0, ? ? ? ? ? ?2 ? ? Big Big- -O (alternative definition) O (alternative definition) ? log(?) 1 You can write ? ? ? ? ? Equivalent to ? ? is ?(? ? ) or ? ? = ? ? ? The set of all functions that run in linear time (i.e. ?(?)) is a complexity class. We never write ?(5?)instead of ?(?) they re the same thing! It s like writing 6 2instead of 3. It just looks weird. CSE 332 SU 18 - ROBBIE WEBER 12

3 Minutes Practice Big-O ?(?) ?(? ? )if there exist positive constants ?,?0 such that for all? ?0, ? ? ? ? ? 5n + 3 O(n) n O(5n + 3) 5n + 3 = O(n) O(5n + 3) = O(n) O(n2) = O(n) n2 O(1) n2 O(n) n2 O(n2) n2 O(n3) n2 O(n100) True True True Big-Omega True ?(?) (? ? )if there exist positive constants ?,?0 such that for all ? ?0, ? ? ? ? ? False False False Big-Theta True ?(?) (? ? )if ? ? is ?(? ? ) and ? ? is (? ? ). True True CSE 373 WI 18 MICHAEL LEE 13

Examples Big-O ?(?) ?(? ? )if there exist positive constants ?,?0 such that for all? ?0, ? ? ? ? ? 4n2 O(1) false false 4n2 O(n) false false 4n2 O(n2) true true 4n2 O(n3) true true 4n2 O(n4) true true 4n2 (1) true true 4n2 (n) true true 4n2 (n2) true true 4n2 (n3) false false 4n2 (n4) false false Big-Omega ?(?) (? ? )if there exist positive constants ?,?0 such that for all ? ?0, ? ? ? ? ? Big-Theta ?(?) (? ? )if ? ? is ?(? ? ) and ? ? is (? ? ). CSE 373 SP 18 - KASEY CHAMPION 14

Testing Your Code CSE 373 19 WI - KASEY CHAMPION 17

Testing Computers don t make mistakes- people do! I m almost done, I just need to make sure it works Naive 14Xers Software Test: Software Test: a separate piece of code that exercises the code you are assessing by providing input to your code and finishes with an assertion of what the result should be. 1. 2. Build in increments - Make a plan from simplest to most complex cases 3. Test as you go - As your code grows, so should your tests Isolate - break your code into small modules CSE 373 SP 18 - KASEY CHAMPION 18

Types of Tests Black Box Black Box - Behavior only ADT requirements - From an outside point of view - Does your code uphold its contracts with its users? - Performance/efficiency White Box White Box - Includes an understanding of the implementation - Written by the author as they develop their code - Break apart requirements into smaller steps - unit tests break implementation into single assertions CSE 373 SP 18 - KASEY CHAMPION 19

What to test? Expected behavior Expected behavior - The main use case scenario - Does your code do what it should given friendly conditions? Forbidden Input Forbidden Input - What are all the ways the user can mess up? Empty/Null Empty/Null - Protect yourself! - How do things get started? - 0, -1, null, empty collections Boundary/Edge Cases Boundary/Edge Cases - First items - Last item - Full collections Scale Scale - Is there a difference between 10, 100, 1000, 10000 items? CSE 373 SP 18 - KASEY CHAMPION 20

Testing Strategies You can t test everything - Break inputs into categories - What are the most important pieces of code? Test behavior in combination - Call multiple methods one after the other - Call the same method multiple times Trust no one! - How can the user mess up? If you messed up, someone else might - Test the complex logic CSE 373 19 WI - KASEY CHAMPION 21

5 Minutes Thought Experiment Discuss with your neighbors: Discuss with your neighbors: Imagine you are writing an implementation of the List interface that stores integers in an Array. What are some ways you can assess your program s correctness in the following cases: Expected Behavior - Create a new list - Add some amount of items to it - Remove a couple of them Forbidden Input - Add a negative number - Add duplicates - Add extra large numbers Empty/Null - Call remove on an empty list - Add to a null list - Call size on an null list Boundary/Edge Cases - Add 1 item to an empty list - Set an item at the front of the list - Set an item at the back of the list Scale - Add 1000 items to the list - Remove 100 items in a row - Set the value of the same item 50 times CSE 373 SP 18 - KASEY CHAMPION 22

JUnit JUnit: JUnit: a testing framework that works with IDEs to give you a special GUI experience when testing your code @Test public void myTest() { Map<String, Integer> basicMap = new LinkedListDict<String, Integer>(); basicMap.put( Kasey , 42); assertEquals(42, basicMap.get( Kasey )); } Assertions: - assertEquals(item1, item2) - assertTrue(Boolean expression) - assertFalse(bollean expression) - assertNotNull(item) More: https://junit.org/junit5/docs/5.0.1/api/org/junit/jupiter/api/Assertions.html CSE 373 SP 18 - KASEY CHAMPION 23