PHP Search Engine

Oct 2 In-Class Exercise Thread .

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

Best,

Chris

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

-- Oct 2 In-Class Exercise Thread

((resource:c568830d-e0fb-4dd4-a1a4-03735ca7a692.jpg|Resource Description for c568830d-e0fb-4dd4-a1a4-03735ca7a692.jpg))

-- Oct 2 In-Class Exercise Thread

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

(Edited: 2019-10-02)

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

-- Oct 2 In-Class Exercise Thread

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

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

(Edited: 2019-10-02)

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

-- Oct 2 In-Class Exercise Thread

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]

1 2 3 4 5 6 6 6 9 2 3 hash function n % 3 Hash_Table Key -> [Values] 1. hash(1) = 1 **insert-at-back** Hash_Table 1 -> [3] 2. hash (2) = 2 **insert-at-back** Hash_Table 1 -> [1] 2 -> [2] 3. hash(3) = 0 **insert-at-back** Hash_Table 0 -> [3] 1 -> [1] 2 -> [2] 4. hash(4) = 1 **insert-at-back** Hash_Table 0 -> [3] 1 -> [1, 4] 2 -> [2] 5. hash (5) = 2 **insert-at-back** Hash_Table 0 -> [3] 1 -> [1, 4] 2 -> [2, 5] 6. hash (6) = 0 **insert-at-back** Hash_Table 0 -> [3, 6] 1 -> [1, 4] 2 -> [2, 5] 7. hash(6) = 0 **move-to-front** Hash_Table 0 -> [6, 3] 2 -> [2, 5] 1 -> [1, 4] 8. hash(6) = 0 **move-to-front** Hash_Table 0 -> [6, 3] 2 -> [2, 5] 1 -> [1, 4] 9. hash(9) = 0 **insert-at-back** Hash_Table 0 -> [6, 3, 9] 2 -> [2, 5] 1 -> [1, 4] 10. hash(2) = 2 **move-to-front** Hash_Table 0 -> [6, 3, 9] 2 -> [2, 5] 1 -> [1, 4] 11. hash(3) = 0 **move-to-front** Hash_Table 0 -> [3, 6, 9] 2 -> [2, 5] 1 -> [1, 4]

-- Oct 2 In-Class Exercise Thread

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

(Edited: 2019-10-02)

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

-- Oct 2 In-Class Exercise Thread

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

(Edited: 2019-10-02)

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

-- Oct 2 In-Class Exercise Thread

((resource:IMG_20191002_144615.jpg|Resource Description for IMG_20191002_144615.jpg))

-- Oct 2 In-Class Exercise Thread

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 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

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

-- Oct 2 In-Class Exercise Thread

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

(Edited: 2019-10-02)

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