Java

1.pdf

Home >Computer Science homework help >Java

CIS36A day 20 Recursion, Hashing, Big O notation

AGENDA Note: this is probably the "mathiest" class session of all semester. This material will be useful regardless of whichever programming language you work in.

Computer science isn't about learning language syntax. It's about learning and applying tools for analysis like the ones we'll discuss today.

• Big O notation • Recursion in Java • Fibonacci sequence by recursion • Recursive binary search

• More on hashing • The .hashCode() method • .equals() / .hashCode() contract

Big O notation • Consider what it takes to add an item to the front of a sorted array:

4 9 13 31 137 1848 1905 1917 1968 2021

(our sorted array)

1871

Big O notation

(our sorted array)

4 9 13 31 137 1848 1905 1917 1968 20211871

6Say we wanted to add an item near the start of the array…

Big O notation

(our sorted array)

4 9 13 31 137 1848 1905 1917 1968 20211871

6We can see it's supposed to go right here…

Big O notation

(our sorted array)

4 9 13 31 137 1848 1905 1917 1968 20211871

6We can see it's supposed to go right here…

…. but to add it there, we have to shift every other element down.

Big O notation

However many operations it takes to shift one array element, it takes that number of operations times the number of elements in the array to shift the entire array.

4 9 13 31 137 1848 1905 1917 1968 202118716

Big O notation

However many operations it takes to shift one array element, it takes that number of operations times the number of elements in the array to shift the entire array.

4 9 13 31 137 1848 1905 1917 1968 202118716

Call the number of elements in the array n. In the worst-case scenario (we're inserting at the very start of the list) it takes:

n * (however many operations)

to insert an item

Big O notation • n * (however many operations) isn't bad when n is small • In this case, n is 12 – not so bad, not even if it takes a thousand operations

to shift one element (it doesn't). • But what if n were 1,000,000,000,000? No matter how few operations it

takes to shift an array element (even just 1), it's going to take a very long time to shift the whole array.

4 9 13 31 137 1848 1905 1917 1968 202118716

(assume this array is very long)

Big O notation • Big O notation is how we represent how the speed of an algorithm

changes as the number of items we're working on gets large. • (Or, slightly more formally, as the number of items approaches infinity)

• Say it takes 137 operations to shift one array element. We see that it takes 137 * n operations to shift the whole array

4 9 13 31 137 1848 1905 1917 1968 202118716

Big O notation • Say it takes 137 operations to shift one array element. We see that it

takes 137 * n operations to shift the whole array.

• Here is 137 * n as n gets large

Big O notation • Consider the other data structure we’ve: the LinkedList

4 6

9 13 31

Big O notation • Each list element consists of the value, plus the address of the next

element in the list. • Inserting an element at the start of a linked list isn't dependent upon

the number of items in the list.

4 6

9 13 31

Big O notation • Inserting an element at the start of a linked list isn't dependent upon

the number of items in the list. • Just make the new element's pointer point to the first element in the list. • No shifting required!

4 6

9 13 31

Big O notation • Inserting an element at the start of a linked list isn't dependent upon

the number of items in the list. • Just make the new element's pointer point to the first element in the list. • No shifting required!

4 6

9 13 31

Big O notation • Inserting an element at the start of a linked list isn't dependent upon

the number of items in the list. • Just make the new element's pointer point to the first element in the list. • No shifting required!

• Because the operation doesn't depend on the number of items, this is called a constant time operation.

4 6

9 13 31

Big O notation • Because the operation doesn't depend on the number of items, this

is called a constant time operation. • Let's say our code to change an item's link were wildly inefficient.

Let's say it took 10,000 operations to do it. • (it doesn't – but let's pretend it does)

4 6

9 13 31

10,000 operations!

Big O notation • Let's say our code to change an item's link were wildly inefficient.

Let's say it took 10,000 operations to do it. • (it doesn't – but let's pretend it does)

• Let's graph the time it takes to add an item to a LinkedList vs the time it takes to add an item to an array, as the number of items already in the list or array gets large:

The blue line is 137 * n

The red line at the bottom is 10000

Big O notation • Let's say our code to change an item's link were wildly inefficient.

Let's say it took 10,000 operations to do it. • (it doesn't – but let's pretend it does)

• Let's graph the time it takes to add an item to a LinkedList vs the time it takes to add an item to an array, as the number of items already in the list or array gets large:

Let's zoom in…

even with a REALLY inefficient process for adding LinkedList items, LinkedList head insertion outperforms the array… even if the array is only 150 elements long.

Big O notation • Let's say our code to change an item's link were wildly inefficient.

Let's say it took 10,000 operations to do it. • Because constant factors tend to not matter as the size of your data

structure goes, when writing the speed of an algorithm, we totally ignore them. All we care about is how it behaves in terms of n, the number of items in the structure.

Big O notation • Writing Big O notation (finally): • Ignore all constants. 137 * n is just n. If everything is a constant, reduce it to 1. • Write what remains after the constants are gone in parentheses after a big O:

Adding to a sorted array is O(n) Adding to the front of a LinkedList is O(1)

Big O notation • LinkedLists are good when you need to insert at the start a lot. But

there are some things LinkedLists are really bad at. For example, if you want to get the last element in the list, you have to look at every single item in the list.

4 6

9 13 31

2 If we want to read 31, we have to visit 2, then follow the link to 4, then follow the link to 6…

Big O notation • Reading from a LinkedList takes O(n) time.

4 6

9 13 31

2 If we want to read 31, we have to visit 2, then follow the link to 4, then follow the link to 6…

Big O notation • Quadratic runtimes: • Say you had two arrays, each of size n. Say you wanted to compare every

element in the first array to every element in the second. You might write it like this:

Notice this double for loop…

Big O notation • Quadratic runtimes: • Say you had two arrays, each of size n. Say you wanted to compare every

element in the first array to every element in the second. You might write it like this:

… if we have n items in each list, and if it takes 10 operations to do a comparison this part of the code takes n * n * 10 operations to run.

Big O notation • Quadratic runtimes: • Say you had two arrays, each of size n. Say you wanted to compare every

element in the first array to every element in the second. You might write it like this:

When writing big O notation, we throw out constants. So forget about the 10. We see that the big O runtime is O(n * n), or O(n2)

Big O notation • Quadratic runtimes: • Let's add 10 * n2 to our graph from a few slides back:

Big O notation • Quadratic runtimes: • Let's add 10 * n2 to our graph from a few slides back. • Notice that our O(n2) algorithm takes way more operations, even if we only

have about 40 elements.

recursion recursion

recursion

WHAT IS A RECURSIVE FUNCTION?

• A recursive function is any function that works by calling itself.

• Anything you can do with recursion, you could also do by ordinary means… but some problems are much easier to write solutions for if you solve them recursively.

WHAT IS A RECURSIVE FUNCTION?

• Here's something you could easily do without recursion… but we're going to do it recursively, just to get a handle on how it works.

• This method takes a number and then prints it out vertically. If our number were 137, it would print: 1 3 7

WHAT IS A RECURSIVE FUNCTION?

• We'll talk about how (and why) this works in a second. First, though, some terminology:

Every recursive function needs to have at least two cases: at least one base case, and at least one recursive case.

WHAT IS A RECURSIVE FUNCTION?

• We'll talk about how (and why) this works in a second. First, though, some terminology:

The base case is the case where the function doesn't call itself again. We need to hit a base case eventually, or else our function will never stop making new copies of itself.

WHAT IS A RECURSIVE FUNCTION?

• We'll talk about how (and why) this works in a second. First, though, some terminology:

The recursive case is the case where the function does call itself. Without this case, the function wouldn't be recursive.

Notice how writeVertical() calls itself again whenever number is greater than or equal to 10.

WHAT IS A RECURSIVE FUNCTION?

• We'll talk about how (and why) this works in a second. First, though, some terminology:

Notice how writeVertical() calls itself again whenever number is greater than or equal to 10.

Also notice that each time we call writeVertical(), the value we pass in gets smaller. Our recursive case gets us closer to the base case.

WHAT IS A RECURSIVE FUNCTION?

• We'll talk about how (and why) this works in a second. First, though, some terminology:

Question: what happens if the recursive case doesn't get us closer to the base case?

WHAT IS A RECURSIVE FUNCTION?

• We'll talk about how (and why) this works in a second. First, though, some terminology:

Question: what happens if the recursive case doesn't get us closer to the base case?

… We have an infinite loop… sad panda

TRACING OUR RECURSIVE FUNCTION

[DEMO ON BOARD]

RECURSIVE FUNCTIONS THAT RETURN VALUES

One classical mathematical sequence is the Fibonacci sequence.

It starts out like this: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…

What's the pattern here?

RECURSIVE FUNCTIONS THAT RETURN VALUES

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…

Each number in the sequence (after the first two) is the number before it plus the number two before it.

Slightly more formally, element n in the Fibonacci sequence is element(n-2) + element(n-1)

This suggests that a recursive solution might be something worth trying, because each number is defined in terms of previous numbers.

55 is 21 plus 34

RECURSIVE FUNCTIONS THAT RETURN VALUES

[SEE LIVECODING EXERCISE]

[SEE DEMO ON BOARD]

RECURSION EXAMPLE 3: PALINDROME CHECKING

• This one is super fun: checking if a string is a palindrome using recursion.

• We know a string is a palindrome if it reads the same forward and backwards.

• It stands to reason that if the first letter and the last letter of a string aren’t the same, that it is therefore not a palindrome.

• We know that any string that’s 0 or 1 characters long is a palindrome.

• Let’s use these facts (and the magic of recursion) to check if a word is a palindrome.

TACOCAT

RECURSION EXAMPLE 3: PALINDROME CHECKING

Designing the algorithm:

TACOCAT

RECURSION EXAMPLE 3: PALINDROME CHECKING

Designing the algorithm:

This is definitely longer than one letter…

TACOCAT

RECURSION EXAMPLE 3: PALINDROME CHECKING

Designing the algorithm:

Let’s compare the first and last character… they’re the same!

TACOCAT

RECURSION EXAMPLE 3: PALINDROME CHECKING

Designing the algorithm:

0) Let’s check if a string is only 0 or 1 characters long. If it is, we return true. 1) We know that if a string has different first and last characters, it is therefore not a palindrome. So let’s compare them, and return false if they’re not the same. 2) What do we do if the first and last characters are the same? Well, we need to keep comparing characters – are the second character and the second-from-last characters the same?

How can we do this using recursion?

Let’s compare the first and last character… they’re the same!

TACOCAT

RECURSION EXAMPLE 3: PALINDROME CHECKING

Designing the algorithm:

We cut off the first and last character, then call the function again!

Let’s compare the first and last character… they’re the same!

TACOCAT

RECURSION EXAMPLE 3: PALINDROME CHECKING

Designing the algorithm:

We cut off the first and last character, then call the function again!

Same! Let’s do it again…

TACOCAT

RECURSION EXAMPLE 3: PALINDROME CHECKING

Designing the algorithm:

We cut off the first and last character, then call the function again!

Same! Let’s do it again…

TACOCAT

RECURSION EXAMPLE 3: PALINDROME CHECKING

Designing the algorithm:

We cut off the first and last character, then call the function again!

We’re down to one letter… so we return true. It’s a palindrome!

TACOCAT

RECURSION EXAMPLE 3: PALINDROME CHECKING

Designing the algorithm:

We cut off the first and last character, then call the function again!

We’re down to one letter… so we return true. It’s a palindrome!

TACOCAT

RECURSION EXAMPLE 3: PALINDROME CHECKING

Let's try it on a non-palindrome. Here we're testing the word "tacocrat," which refers to a taco- obsessed dictator

• We check the first and last characters. They're the same!

We’re down to one letter… so we return true. It’s a palindrome!

TACOCRAT

RECURSION EXAMPLE 3: PALINDROME CHECKING

Let's try it on a non-palindrome. Here we're testing the word "tacocrat," which refers to a taco- obsessed dictator

• We cut off the first and last characters, then repeat.

• They're still the same! We cut off the first and last characters, then repeat…

We’re down to one letter… so we return true. It’s a palindrome!

TACOCRAT

RECURSION EXAMPLE 3: PALINDROME CHECKING

Let's try it on a non-palindrome. Here we're testing the word "tacocrat," which refers to a taco- obsessed dictator

• We cut off the first and last characters, then repeat.

• They're still the same! We cut off the first and last characters, then repeat…

• … whoops! C and R are not the same. We return false, because this is not a palindrome.

• (full disclosure: I'd give the tacocrat a taco, even though tacocrat isn't a palindrome. he's so cute!!)

We’re down to one letter… so we return true. It’s a palindrome!

TACOCRAT

RELEVANT TANGENT

Notice how every recursive step in this process gets us closer to the base case.

For our palindrome program, each recursive step cuts two letters off the word – thereby causing us to get just a little bit closer to our base case (a string of only 0 or 1 characters).

(or, if it’s not a palindrome, it gets us closer to the other base case – it produces a string that might have different first and last characters)

WHEN DESIGNING RECURSIVE ALGORITHMS, _ALWAYS_ MAKE SURE THAT YOUR RECURSIVE CASES GET YOU CLOSER TO A BASE CASE.

TACOCAT

BINARY SEARCH

• Binary search is a very fast way to find where a value is stored in a sorted array. • It's also fairly intuitive to implement recursively • See video:

https://www.youtube.com/watch?v=FOwCCvHEfY0

TACTICS: 1) FIGURE OUT WHAT YOUR BASE CASE IS. When do you know you're

done? • Whenever this condition is true – whenever you know you're done – that's

when you return from the method without doing further recursion

2. Figure out something you can do to get just one small step closer to the base case. This is what your recursive case will do – just get you one step closer to the base case.

3. Write your recursive case to keep calling itself – to keep taking that one small step – until you get to the base case.

4. You generally should not have to use loops within your recursive functions. The recursion does what you'd ordinarily use loops to do.

BACK TO HASHING Hashing, Big O notation, Recursion

• A HashMap is a data structure that associates a key with a value. Consider the HashMap declared below:

Review: HashMap

• A HashMap is a data structure that associates a key with a value. Consider the HashMap declared below:

• You add an item to a HashMap by using the .put() method:

firstHashMap.put(137, "Ben");

Review: HashMap

• A HashMap is a data structure that associates a key with a value. Consider the HashMap declared below:

• You add an item to a HashMap by using the .put() method:

firstHashMap.put(137, "Ben");

Review: HashMap

This is the key

• A HashMap is a data structure that associates a key with a value. Consider the HashMap declared below:

• You add an item to a HashMap by using the .put() method:

firstHashMap.put(137, "Ben");

Review: HashMap

This is the value

• A HashMap is a data structure that associates a key with a value. Consider the HashMap declared below:

• You add an item to a HashMap by using the .put() method: firstHashMap.put(137, "Ben");

• You retrieve an item from the HashMap by using the .get() method: String result = firstHashMap.get(137);

Review: HashMap

returns "Ben", because that's the value associated with the key 137.

Maps and HashMaps

• Just like ArrayList is a derived class from the List base class, HashMap is a derived class from the Map base class.

so we can (and should) declare our HashMaps as just Maps

HashMap

• In the case of an ArrayList, we associate items in the list with an index – with their location in the array. We can look items up by index.

• In the case of a HashMap, we associate items in the list with whatever we want – with a key that we define – and then can look up items using that key.

• You really can use whatever you want as a key value

HashSet

Another commonly used container is the HashSet. This stores data by hashing, as in a HashMap.

A HashSet (and Sets in general) are data structures that have the following features:

• They are unordered (so looking up an element by index makes no sense) • They contain no duplicates. (this can be very useful)

Why use hashing? • The simple answer: It's fast.

• Okay, but what does it mean for a data structure to be "fast"?

Why use hashing? • The simple answer: It's fast.

• Okay, but what does it mean for a data structure to be "fast"?

• One of our main tools for understanding algorithm speed is what's called "Big O notation." Let's discuss it briefly.

Return to HashMaps • HashMaps are kind of magic: inserting into a HashMap takes

O(1) time, searching for an element in a HashMap takes O(1) time, deleting an element takes O(1) time…

or "constant time"

• Here's an image on how hashing works, that I've shamelessly stolen from Wikipedia

Keys, values, and hash functions • We have a bunch of keys and values. In our stolen example, the

HashMap is being used in a contacts list: the key is the name of a person, and the value is their phone number.

• Our hash function is any function that can convert the key into a numerical index. We store the value associated with the key at whatever index the hash function produces.

Return to HashMaps • Our hash function is any function that can convert the key into a

numerical index. We store the value associated with the key at whatever index the hash function produces.

• A good hash function is one that produces few collisions.

• What's a collision? That's when two keys happen to hash to the same value.

Return to HashMaps • In this case, the names John Smith and Sandra Dee both happen to

hash to the value 152. They can't both be stored in the exact same space, so we have a problem.

Collision!

Return to HashMaps • In this case, the names John Smith and Sandra Dee both

happen to hash to the value 152. They can't both be stored in the exact same space, so we have a problem.

• We resolve this problem by having each bucket store a linked list.

• We try to avoid collisions… but if we do, we can store two elements in a list in one bucket.

Return to HashMaps • In this case, the names John Smith and Sandra Dee both

happen to hash to the value 152. They can't both be stored in the exact same space, so we have a problem. • We resolve this problem by having

each bucket store a linked list. • We try to avoid collisions… but if

we do, we can store two elements in a list in one bucket. • … and if we have too many

collisions, we can just increase the number of buckets.

Return to HashMaps • Because looking up an element just requires putting the key

through a hash function, lookup doesn't depend on the number of items in the HashMap: it's O(1) • Likewise deleting an element

just requires putting the key through the hash function and deleting the value stored in the bucket. O(1) • Adding an item is similar. O(1)

Return to HashMaps • In short: HashMaps are really really really fast. • Arrays are fast at retrieving items. LinkedLists are good at adding items

to the start… but HashMaps are good at (nearly) everything.

(even if your hash function takes a lot of operations to run).

The .hashCode() method • The .hashCode() method is used by HashMap and HashSet to determine

where to store hashed values • One way to make a hashCode() meethod is to autogenerate it. • On the next slide is a recipe for writing a reliable hashCode() method.

This isn't something you need to memorize – the point is that: 1. The .hashCode() method returns an int that should be (relatively) unique for

each object 2. The hashCode() method should produce this int in a way that relies upon all of

the member variables that are tested by the .equals() method

One strategy for the .hashCode() method

1.Create a int result and assign a non-zero value. 2.For every field f tested in the equals() method, calculate a hash code c by:

1. If the field f is a boolean: calculate (f ? 0 : 1); 2. If the field f is a byte, char, short or int: calculate (int)f; 3. If the field f is a long: calculate (int)(f ^ (f >>> 32)); 4. If the field f is a float: calculate Float.floatToIntBits(f); 5. If the field f is a double: calculate Double.doubleToLongBits(f) and handle the

return value like every long value; 6. If the field f is an object: Use the result of the hashCode() method or 0 if f ==

null; 7. If the field f is an array: see every field as separate element and calculate the

hash value in a recursive fashion and combine the values as described next. 3.Combine the hash value c with result: 4.result = 37 * result + c 5.Return result

originally from the book Effective Java – I believe this is the algorithm that IntelliJ’s autogenerator uses, though I haven't tested everything

.hashCode()/.equals() contract • It is expected that every object that overrides .equals() should have its own

.hashCode() method. • (for the purposes of this class, it is totally fine to use an autogenerated one produced

by your IDE)

• This is the .hashCode()/.equals() contract: if a pair of objects are considered equal by the .equals() method, the results of their .hashCode() methods should also be equals.

• Repeat: if two objects are .equals(), they should have the same hash code. • However, this doesn't work the other way around. Just because the

.hashCode() methods of two objects return the same value doesn't necessarily mean that they're equal.

• This is because hash collisions occur

.hashCode()/.equals() contract • This is because hash collisions occur:

In this case there's a hash collision between John Smith and Sandra Dee. That's fine! A hash function can return the same value for two objects without those objects actually being equals.