CSE 373 SU23 Section 3

Recurrence Party 🎉and Hashing

​

Agenda

• Announcements

​

• IntelliJ Debugging Demo

​

• Recurrence Analysis Review

​

• Master Theorem

​

• Hashing Intro

​

Announcements

P2 will be released on tomorrow, July 7

• Two weeks to complete. Harder than P1! Please start early!!!
• Due Friday, July 21st at 11:59PM.
• Late Deadline: Sunday, July 23rd at 11:59PM

IntelliJ Debugging Demo

JGrasp Plugin Installation

• Make sure you have installed the JGrasp plugin for IntelliJ (you should have downloaded it when completing the System Setup for P0)
• In IntelliJ go to File>Settings>Plugins. Then search for JGrasp and click Install

​

​

Debugging in IntelliJ

• To start debugging in IntelliJ, you must set a breakpoint in your test file by clicking on the line number you want to break at
• Then, Click the Green Bug button on the toolbar to start debugging

Debugging in IntelliJ

• When you click ‘Debug’ a window will pop up on the bottom of your screen, allowing you to step through your code
• There are four buttons you can use to step through your code
• Step Over: goes to the next line of code
• Step Into: goes into a function that is called
• Step Out: goes out out of the current function
• Run To Cursor: runs until it reaches the line which your cursor is on

Debugging with JGrasp Visualizer

• To use the JGrasp Visualizer, click on ‘JGrasp’ in the Debugging Window
• You can drag variables or values from the left in the IntelliJ debugger onto the viewer canvas on the right
• As you step through your code, you should be able to watch as the variables change in the viewer

​

​

Additional Resources

• More info on the JGrasp Plugin for IntelliJ can be found here
• Another visualizer that you can try is Java Visualizer.
• Draws out environmental diagrams like our slides.
• Try them both out and switch between them freely during debugging!

Recurrence Analysis Review

What is a Recurrence?

An expression that lets us express the runtime of a function recursively.��

​

Base Case

​

Recursive Case

​

Recursive Call

Do Problems 1A + 3A Together!

​

​

Hint 2: You should use the answer from 1A to get 3A more quickly!

​

Hint 1: Gauss’s Identity is helpful for 1A (see “cheat-sheet” at end of PDF):

​

1A: Finding Bounds

1A: Finding Bounds

Constant Work

Outer Loop runs n times

Inner Loop depends on Outer Loop

Constant Work

1A: Finding Bounds

Outer loop runs from i = 0 to i = n - 1

​

Inner loop runs from j = 0 to j = i-1

​

Since the inner loop depends on the outer loop, we can express the runtime as the summation below.

1A: Finding Bounds

POSSIBLE RUNTIME:

T(N) = N(N-1)/2 = ½ N² - ½ N

​

WORST CASE RUNTIME:

Θ(N²)

N²/2 + N/2 => N²

^{Best/worst cases agree!}

3A: Code To Recurrence

3A: Code To Recurrence

3A: Code To Recurrence Solution

Base Case

We saw the runtime for this code earlier! It’s N(N-1)/2

Call f(N/2)

Constant addition

Call f(N/2)

Call f(N/2)

Call f(N/2)

3A: Code To Recurrence

4 recursive calls. the input is cut in half each level

Work happening in both outer and inner loops

(see 1A)

Can also simplify non-recursive term (and only this term) using Big-O rules.

​

So you could also have put N² here.

In fact, you should simplify before doing Tree Method!

Master Theorem

Master Theorem: A “Cheat Code” (Kinda)

NOTE: If you get lucky and your recurrence matches the Master Theorem form, then you may use this formula to jump right to the final closed form.

​

(Of course, a lot of the time

it won’t match. That’s why tree method is still important.)

Use Master Theorem to find closed form

Original recurrence:

Step 1: Does T(n) match Master Theorem form?

a = 4

b = 2

e = 1

c = 2

Recall: could also have put N² here.

Use Master Theorem to find closed form

Original recurrence:

Step 2: Calculate log_b(a) and compare it to c

a = 4

b = 2

e = 1

c = 2

log_b(a) = log₂(4)

log₂(4) = 2

c = 2 so log_b(a) = c

log_b(a) = c so T(n) ∈ Θ(n²log n)

Ta-da!

4. Master Theorem

Use the cheat sheet attached to your section handout!

Question 4A

Question 4A Solution

Question 4B

Question 4B Solution

Question 4C

Question 4C Solution

Question 4D

Question 4D Solution

Question 4E

Question 4E Solution

Hashing Intro

Hash Tables

One way to implement the dictionary ADT.

​

Stores item with key x in array index (or “bucket”) h(x).�(The choice of h(x)is important for many reasons.)��

Collisions?

One approach: Separate chaining uses Linked Lists to handle collisions.

​

0

1

​

​

​

3124

​

​

4583

​

​

20382827

​

​

553256591

553256592

​

snack

...

...

potato

rotato

totato

dog

cat

...

...

Using Mod (Compression)

We use the modulus of the hashcode when it exceeds the number of buckets.

​

0

1

2

3

4

5

6

7

8

9

Q: If we use the 10 buckets below, where should our six items go?�

A: Put in bucket = h(x) % 10

potato

rotato

totato

snack

0

1

​

​

​

3124

​

​

4583

​

​

20382827

​

​

553256591

553256592

​

snack

...

...

potato

rotato

totato

dog

cat

...

...

cat

dog

Hash Function Quality

Note: The more h(x)evenly distributes the keys, the faster get is! (Why?)

0

1

2

3

4

5

6

7

8

9

potato

rotato

totato

snack

0

1

​

​

​

3124

​

​

4583

​

​

20382827

​

​

553256591

553256592

​

snack

...

...

potato

rotato

totato

dog

cat

...

...

cat

dog

Problem 1A + 1B:��Hash Table Insertion

Problem 1A

Hash Table With Separate Chaining

Remember you use hash function with key not with value!

Suppose we have a hash table implemented using separate chaining. This hash table has an internal capacity of 10. Its buckets are implemented using a linked list where new elements are appended to the end. Do not worry about resizing.

Show what this hashtable internally looks like after inserting the following key-value pairs in the order given using the hash function h(x) = 4x:

(1, a), (4, b), (2, c), (17, d), (12, e), (9, e), (19, f), (4, g), (8, c), (12, f)

​

Hash Table With Separate Chaining

​

Input: (1,a)

Hash function: h(x) = 4x

h(1) = 4

4% 10 = 4

​

0 1 2 3 4 5 6 7 8 9

Hash Table With Separate Chaining

​

Input: (4,b)

Hash function: h(x) = 4x

h(4) = 16

16 % 10 = 6

​

​

0 1 2 3 4 5 6 7 8 9

Hash Table With Separate Chaining

​

Input: (2,c)

Hash function: h(x) = 4x

h(2) = 8

8 % 10 = 8

​

​

0 1 2 3 4 5 6 7 8 9

Hash Table With Separate Chaining

​

Input: (17,d)

Hash function: h(x) = 4x

h(17) = 68

68 % 10 = 8

​

​

0 1 2 3 4 5 6 7 8 9

Hash Table With Separate Chaining

​

Input: (12,e)

Hash function: h(x) = 4x

h(12) = 48

48 % 10 = 8

​

​

0 1 2 3 4 5 6 7 8 9

Hash Table With Separate Chaining

​

Input: (9,e)

Hash function: h(x) = 4x

h(9) = 36

36 % 10 = 6

​

​

0 1 2 3 4 5 6 7 8 9

Hash Table With Separate Chaining

​

Input: (19,f)

Hash function: h(x) = 4x

h(19) = 76

76 % 10 = 6

​

​

0 1 2 3 4 5 6 7 8 9

Hash Table With Separate Chaining

​

Input: (4,g)

Hash function: h(x) = 4x

h(4) = 16

16 % 10 = 6

​

​

0 1 2 3 4 5 6 7 8 9

Since the key already exists, we update its value!

Hash Table With Separate Chaining

​

Input: (8,c)

Hash function: h(x) = 4x

h(8) = 32

32 % 10 = 2

​

​

0 1 2 3 4 5 6 7 8 9

Hash Table With Separate Chaining

​

Input: (12,f)

Hash function: h(x) = 4x

h(12) = 48

48 % 10 = 8

​

​

0 1 2 3 4 5 6 7 8 9

Problem 1B

Evaluating Hash Functions

​

Evaluating Hash Functions

​

​

​

h(x) = 4x

0 1 2 3 4 5 6 7 8 9 10 11

Issue with the hash function:

Keys will initially only be hashed to at most one of three spots

​

Collisions are very likely, decreasing performance!

​

0

6

93

1

7

94

2

8

95

Evaluating Hash Functions

​

​

​

h(x) = 4x

0 1 2 3 4 5 6 7 8 9 10 11

Issue with the resize:

12 13 14 15 16 17 18 19 20 21 22 23

We still only map to a fourth of the available indices!

​

Evaluating Hash Functions

Possible Fixes?

​

• Pick a new hash function that’s relatively prime to 12 (e.g. h(x) = 5x)

​

• Choose a different initial table capacity (11, 13)

​

• Resize differently (such as choosing a prime that’s roughly double the size

​

Prime numbers will almost always improve our hashing!

​

Problem 4A-C:��Hashing and Mutation

Hashing and Mutation

​

Hashing and Mutation

This will look up the bucket (1 + 2) mod 4 = 3.

​

In the bucket 3, IntList.of(1, 2) is equivalent to [1, 2], so "dog" which is the stored value is returned.

a)

Hashing and Mutation

​

This will look up the bucket (1 + 2) mod 4 = 3.

​

In the bucket 3, IntList.of(1, 2) is NOT equivalent to [1, 2, 3], so we cannot find the matched key.

​

Hence, return null.

b)

Hashing and Mutation

​

This will look up the bucket (1 + 2 + 3) mod 4 = 2.

​

Since the bucket 2 is empty, we definitely cannot find the matched key.

​

Hence, return null.

b)

Hashing and Mutation

​

We changed a key while it was inside the hashtable, and caused it to be in the wrong bucket.��Never do this. The elements getting put in the hash table must be immutable!

c)

Thank you & see you next week!