Lecture 8: Hash Maps - University of Washington

Lecture 8: Hash Maps (with separate chaining)

CSE 373: Data Structures and Algorithms

1

Warm Up!

Take 2 Minutes

1. cse373

activity for participating

Keep an eye on loop bounds! Write a mathematical model of the following code

in our active learning questions.

for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { System.out.println("Hello!"); +1 }

}

n

n

f(n) = n2

2. /cse373studentqs to ask your own questions

Which of the following is a mathematical model for the runtime of the code given? a.) ! " = 2"

b.) ! " = " + "

c.) ! " = "&

*+, -+,

d.) ! " = ' ' 1

()* -).

CSE 373 SP 20 ? CHUN & CHAMPION

2

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)

How do we model this part?

Summations!

%

1 + 2 + 3 + 4 +... + n = ! &

"#$

+1

0 + 1 + 2 + 3 +...+ i-1

n

Definition: Summation

(

! )(&) = f(a) + f(a + 1) + f(a + 2) + ... + f(b-2) + f(b-1) + f(b)

"#'

T(n) =

%-$ "-$

!!1

"#, .#,

What is the Big O?

CSE 373 19 WI - KASEY CHAMPION

3

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

%&' +&'

closed form

()* %)*

! " = $$1

%&' +&'

()*

= $ 1-

%&'

Summation of a constant

()*

$ 0 = 0"

%&'

()*

=1$-

%&'

Factoring out a constant

2

2

$ 03 - = 0 $ 3(-)

%&1

%&1

" "-1 =2

=

1 2

"6

-

1 2

"

Gauss's Identity ()* " " - 1 $-= 2

%&'

simplified tight big O = 7(89)

CSE 373 19 SP ? KASEY CHAMPION (THANKS TO MICHAEL LEE)

4

Traversing Data

Array

for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]);

}

List

for (int i = 0; i < myList.size(); i++) { System.out.println(myList.get(i));

} for (T item : list) {

System.out.println(item); }

Iterator!

CSE 373 SP 18 - KASEY CHAMPION

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download