Post your solutions to the Oct 2 In-Class Exercise to this Thread.

Best,

Chris

1 2 3 4 5 6 6 6 9 2 3

For 1,2,3,4,5,6

Key List

0 -> 3,6

1 -> 1,4

2 -> 2,5

For 6, key = 0, move 6 to front

Key List

0 -> 6,3

1 -> 1,4

2 -> 2,5

For 6, key = 0, found, return from first

Key(Hashed) List

0 -> 6,3

1 -> 1,4

2 -> 2,5

For 9 = insert fot key=0, for=2 return from the first, for=3, found

Key(Hashed) List

0 -> 3,6,9

1 -> 1,4

2 -> 2,5

Insert(1) 0: 1:1 2:

Insert(2) 0: 1:1 2:2

Insert(3) 0:3 1:1 2:2

Insert(4) 0:3 1:1->4 2:2

Insert(5) 0:3 1:1->4 2:2->5

Insert(6) 0:3->6 1:4->1 2:2->5

LookUp(6) -> MoveToFirst() 0:6->3 1:4->1 2:2->5

LookUp(6) -> MoveToFirst() 0:6->3 1:4->1 2:2->5

Insert(9) 0:6->3->9 1:4->1 2:2->5

LookUp(2) -> MoveToFirst() 0:6->3->9 1:4->1 2:2->5

LookUp(3) -> MoveToFirst() 0:3->6->9 1:4->1 2:2->5

1 2 3 4 5 6 6 6 9 2 3

hash function n % 3

Hash_Table

Key -> [Values]

hash(1) = 1 

insert-at-back Hash_Table 1 -> [3]

hash (2) = 2

insert-at-back Hash_Table 1 -> [1] 2 -> [2]

hash(3) = 0

insert-at-back Hash_Table 0 -> [3] 1 -> [1] 2 -> [2]

hash(4) = 1

insert-at-back Hash_Table 0 -> [3] 1 -> [1, 4] 2 -> [2]

hash (5) = 2

insert-at-back Hash_Table 0 -> [3] 1 -> [1, 4] 2 -> [2, 5]

hash (6) = 0

insert-at-back Hash_Table 0 -> [3, 6] 1 -> [1, 4] 2 -> [2, 5]

hash(6) = 0

move-to-front Hash_Table 0 -> [6, 3] 2 -> [2, 5] 1 -> [1, 4]

hash(6) = 0

move-to-front Hash_Table 0 -> [6, 3] 2 -> [2, 5] 1 -> [1, 4]

hash(9) = 0

insert-at-back Hash_Table 0 -> [6, 3, 9] 2 -> [2, 5] 1 -> [1, 4]

hash(2) = 2

move-to-front Hash_Table 0 -> [6, 3, 9] 2 -> [2, 5] 1 -> [1, 4]

hash(3) = 0

move-to-front Hash_Table 0 -> [3, 6, 9] 2 -> [2, 5] 1 -> [1, 4]

insert-at-back (1,2,3,4,5,6): 0 -> 3 1 -> 1, 4 2 -> 2, 5 move-to-front(6, hash_table[0]) move-to-front (6, hash_table[0]): 0 -> 6, 3 1 -> 1, 4 2 -> 2, 5 insert-at-back (9, hash_table[0]): 0 -> 6, 3, 9 1 -> 1, 4 2 -> 2, 5 move-to-front (2, hash_table[2]) 0 -> 6, 3, 9 1 -> 1, 4 2 -> 2, 5 move-to-front (3, hash_table[0]) 0 -> 3, 6, 9 1 -> 1, 4 2 -> 2, 5

corpus : 1 2 3 4 5 6 6 6 9 2 3. Available Hash Table of Size=3

corpus : 1....... 2 3 4 5 6 6 6 9 2 3. h=1%3=1 so, a[0]=() a[1]=( 1 ) . a[2]=()

corpus : 2...... 3 4 5 6 6 6 9 2 3. h=2%3=2 so, a[0]=() a[1]=(1 ) . a[2]=(2)

corpus : 3...... 4 5 6 6 6 9 2 3. h=3%3=0 so, a[0]=(3) a[1]=(1) . a[2]=(2)

corpus : 4........ 5 6 6 6 9 2 3. h=4%3=1 so, a[0]=(3) a[1]=(1,4 ) . a[2]=(2) insert-at-back

corpus : 5...... 6 6 6 9 2 3. h=5%3=2 so, a[0]=(3) a[1]=(1,4 ) . a[2]=(2,5) insert-at-back

corpus : 6....... 6 6 9 2 3. h=6%3=0 so, a[0]=(3,6) a[1]=(1,4 ) . a[2]=(2,5) insert-at-back

corpus : 6 ..... 6 9 2 3. h=6%3=0 so, a[0]=(6,3) a[1]=(1,4 ) . a[2]=(2,5) move 6 in front as it is more frequently accessed. move-to-front

corpus : 6 ......9 2 3. h=6%3=0 so, a[0]=(6,3) a[1]=(1,4 ) . a[2]=(2,5)

corpus : 9 .......2 3. h=9%3=0 so, a[0]=(6,3,9) a[1]=(1,4 ) . a[2]=(2,5) insert-at-back

corpus : 2 ......3. h=2%3=2 so, a[0]=(6,3,9) a[1]=(1,4 ) . a[2]=(2,5)

corpus : 3......... h=3%3=0 so, a[0]=(3,6,9) a[1]=(1,4 ) . a[2]=(2,5) move-to-front

Corpus : 1 2 3 4 5 6 6 6 9 2 3

Lookup 1; not present in hash table Insert at back 1 [0] : [1] : 1 [2] :

Lookup 2; not present in hash table Insert at back 2 [0] : [1] : 1 [2] : 2

Lookup 3; not present in hash table Insert at back 3 [0] : 3 [1] : 1 [2] : 2

Lookup 4; not present in hash table Insert at back 4 [0] : 3 [1] : 1, 4 [2] : 2

Lookup 5; not present in hash table Insert at back 5 [0] : 3 [1] : 1, 4 [2] : 2, 5

Lookup 6; not present in hash table Insert at back 6 [0] : 3, 6 [1] : 1, 4 [2] : 2, 5

Lookup 6; present in hash table Move to front 6 [0] : 6, 3 [1] : 1, 4 [2] : 2, 5

Lookup 6; present in hash table Move to front 6 [0] : 6, 3 [1] : 1, 4 [2] : 2, 5

Lookup 9; not present in hash table Insert 9 [0] : 6, 3, 9 [1] : 1, 4 [2] : 2, 5

Lookup 2; present in hash table Move to front 2 [0] : 6, 3, 9 [1] : 1, 4 [2] : 2, 5

Lookup 3; present in hash table Move to front 3 [0] : 3, 6, 9 [1] : 1, 4 [2] : 2, 5

1 2 3 4 5 6 6 6 9 2 3

for 1,2,3,4,5,6

keys:

0 -> 3,6

1 -> 1,4

2 -> 2,5

for 6, key = 0, move 6 to front

Keys:

0 -> 6,3

1 -> 1,4

2 -> 2,5

for 6, key = 0, found, return from first

Keys Hashed:

0 -> 6,3

1 -> 1,4

2 -> 2,5

For 9 = insert fot key=0, for=2 return from the first, for=3, found

Keys Hashed

0 -> 3,6,9

1 -> 1,4

2 -> 2,5