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

 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]

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]

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