Yioop - PHP Search Engine

Mar 23 In-Class Exercise.

Please post your solutions to the Mar 23 IN-Class Exercise to this thread.

Best,

Chris

Please post your solutions to the Mar 23 IN-Class Exercise to this thread. Best, Chris

-- Mar 23 In-Class Exercise

List = 9 6 4 4 5 6 3 6 9 5 2 3 
 
9.
0 -> 9 
 
6.
0 -> 9, 6 
 
4.
0 -> 9, 6
1 -> 4 
 
4.
0 -> 9, 6
1 -> 4 
 
5.
0 -> 9, 6
1 -> 4
2 -> 5 
 
6.
0 -> 6, 9
1 -> 4
2 -> 5 
 
3.
0 -> 6, 9, 3
1 -> 4
2 -> 5 
 
6.
0 -> 6, 9, 3
1 -> 4
2 -> 5 
 
9.
0 -> 9, 6, 3
1 -> 4
2 -> 5 
 
5.
0 -> 9, 6, 3
1 -> 4
2 -> 5 
 
2.
0 -> 9, 6, 3
1 -> 4
2 -> 5, 2 
 
3.
0 -> 3, 9, 6
1 -> 4
2 -> 5, 2

(Edited: 2022-03-23)

-- Mar 23 In-Class Exercise

Insert in the following order - 9 6 4 4 5 6 3 6 9 5 2 3 
 
(9)
0 -> 9 (0)
1 ->
2 -> 
 
(6)
0 -> 9 (0), 6 (1)
1 ->
2 -> 
 
(4)
0 -> 9 (0), 6 (1)
1 -> 4 (2)
2 -> 
 
(4)
0 -> 6 (1), 9 (0)
1 -> 4 (2,3)
2 -> 
 
(5)
0 -> 6 (1), 9 (0)
1 -> 4 (2,3)
2 -> 5 (4) 
 
(6)
0 -> 6 (1, 5), 9 (0)
1 -> 4 (2,3)
2 -> 5 (4) 
 
(3)
0 -> 6 (1, 5), 9 (0), 3 (6)
1 -> 4 (2,3)
2 -> 5 (4) 
 
(6)
0 -> 6 (1, 5, 7), 9 (0), 3 (6)
1 -> 4 (2,3)
2 -> 5 (4) 
 
(9)
0 -> 9 (0, 8), 6 (1, 5, 7), 3 (6)
1 -> 4 (2,3)
2 -> 5 (4) 
 
(5)
0 -> 9 (0, 8), 6 (1, 5, 7), 3 (6)
1 -> 4 (2,3)
2 -> 5 (4, 9) 
 
(2)
0 -> 9 (0, 8), 6 (1, 5, 7), 3 (6)
1 -> 4 (2,3)
2 -> 5 (4, 9), 2 (10) 
 
(3)
0 -> 3 (6, 11), 9 (0, 8), 6 (1, 5, 7)
1 -> 4 (2,3)
2 -> 5 (4, 9), 2 (10)

(Edited: 2022-03-23)

<pre> Insert in the following order - 9 6 4 4 5 6 3 6 9 5 2 3 (9) 0 -> 9 (0) 1 -> 2 -> (6) 0 -> 9 (0), 6 (1) 1 -> 2 -> (4) 0 -> 9 (0), 6 (1) 1 -> 4 (2) 2 -> (4) 0 -> 6 (1), 9 (0) 1 -> 4 (2,3) 2 -> (5) 0 -> 6 (1), 9 (0) 1 -> 4 (2,3) 2 -> 5 (4) (6) 0 -> 6 (1, 5), 9 (0) 1 -> 4 (2,3) 2 -> 5 (4) (3) 0 -> 6 (1, 5), 9 (0), 3 (6) 1 -> 4 (2,3) 2 -> 5 (4) (6) 0 -> 6 (1, 5, 7), 9 (0), 3 (6) 1 -> 4 (2,3) 2 -> 5 (4) (9) 0 -> 9 (0, 8), 6 (1, 5, 7), 3 (6) 1 -> 4 (2,3) 2 -> 5 (4) (5) 0 -> 9 (0, 8), 6 (1, 5, 7), 3 (6) 1 -> 4 (2,3) 2 -> 5 (4, 9) (2) 0 -> 9 (0, 8), 6 (1, 5, 7), 3 (6) 1 -> 4 (2,3) 2 -> 5 (4, 9), 2 (10) (3) 0 -> 3 (6, 11), 9 (0, 8), 6 (1, 5, 7) 1 -> 4 (2,3) 2 -> 5 (4, 9), 2 (10) </pre>

-- Mar 23 In-Class Exercise

 
 
9 6 4 4 5 6 3 6 9 5 2 3
(x) where x represents position of posting list 
 
Insert 9
0 -> 9(0)
1 ->
2 ->
Insert 6
0 -> 9(0) , 6(1)
1 ->
2 ->
Insert 4
0 -> 9(0) , 6(1)
1 -> 4(2)
2 ->
Lookup 4
0 -> 9(0) , 6(1)
1 -> 4(2,3)
2 ->
Insert 5
0 -> 9(0) , 6(1)
1 -> 4(2,3)
2 -> 5(4)
Lookup 6
0 -> 6(1,5) , 9(0)
1 -> 4(2,3)
2 -> 5(4)
Insert 3
0 -> 6(1,5) , 9(0), 3(6)
1 -> 4(2,3)
2 -> 5(4)
Lookup 6
0 -> 6(1,5,7) , 9(0), 3(6)
1 -> 4(2,3)
2 -> 5(4)
Lookup 9
0 -> 9(0,8), 6(1,5,7), 3(6)
1 -> 4(2,3)
2 -> 5(4,9)
Lookup 5
0 -> 9(0,8), 6(1,5,7), 3(6)
1 -> 4(2,3)
2 -> 5(4,9)
Insert 2
0 -> 9(0,8), 6(1,5,7), 3(6)
1 -> 4(2,3)
2 -> 5(4,9), 2(10)
Lookup 3
0 -> 3(6,11), 9(0,8), 6(1,5,7)
1 -> 4(2,3)
2 -> 5(4,9), 2(10)

(Edited: 2022-03-23)

<pre> 9 6 4 4 5 6 3 6 9 5 2 3 (x) where x represents position of posting list Insert 9 0 -> 9(0) 1 -> 2 -> Insert 6 0 -> 9(0) , 6(1) 1 -> 2 -> Insert 4 0 -> 9(0) , 6(1) 1 -> 4(2) 2 -> Lookup 4 0 -> 9(0) , 6(1) 1 -> 4(2,3) 2 -> Insert 5 0 -> 9(0) , 6(1) 1 -> 4(2,3) 2 -> 5(4) Lookup 6 0 -> 6(1,5) , 9(0) 1 -> 4(2,3) 2 -> 5(4) Insert 3 0 -> 6(1,5) , 9(0), 3(6) 1 -> 4(2,3) 2 -> 5(4) Lookup 6 0 -> 6(1,5,7) , 9(0), 3(6) 1 -> 4(2,3) 2 -> 5(4) Lookup 9 0 -> 9(0,8), 6(1,5,7), 3(6) 1 -> 4(2,3) 2 -> 5(4,9) Lookup 5 0 -> 9(0,8), 6(1,5,7), 3(6) 1 -> 4(2,3) 2 -> 5(4,9) Insert 2 0 -> 9(0,8), 6(1,5,7), 3(6) 1 -> 4(2,3) 2 -> 5(4,9), 2(10) Lookup 3 0 -> 3(6,11), 9(0,8), 6(1,5,7) 1 -> 4(2,3) 2 -> 5(4,9), 2(10) </pre>

-- Mar 23 In-Class Exercise

9: 0-> 9

6: 0-> 9,6

4: 0-> 9,6; 1-> 4

5: 0-> 9,6; 1-> 4; 2-> 5

6: 0-> 6,9; 1-> 4; 2-> 5

3: 0-> 6,9,3; 1-> 4; 2-> 5

6: 0-> 6,9,3; 1-> 4; 2-> 5

9: 0-> 9,6,3; 1-> 4; 2-> 5

5: 0-> 9,6,3; 1-> 4; 2-> 5

2: 0-> 9,6,3; 1-> 4; 2-> 5,2

3: 0-> 3,9,6; 1-> 4; 2-> 5,2

(Edited: 2022-03-23)

9: 0-> 9 6: 0-> 9,6 4: 0-> 9,6; 1-> 4 4: 0-> 9,6; 1-> 4 5: 0-> 9,6; 1-> 4; 2-> 5 6: 0-> 6,9; 1-> 4; 2-> 5 3: 0-> 6,9,3; 1-> 4; 2-> 5 6: 0-> 6,9,3; 1-> 4; 2-> 5 9: 0-> 9,6,3; 1-> 4; 2-> 5 5: 0-> 9,6,3; 1-> 4; 2-> 5 2: 0-> 9,6,3; 1-> 4; 2-> 5,2 3: 0-> 3,9,6; 1-> 4; 2-> 5,2

-- Mar 23 In-Class Exercise

Inserting 9
{0: [9], 1: [], 2: []} 
 
Inserting 6
{0: [9, 6], 1: [], 2: []} 
 
Inserting 4
{0: [9, 6], 1: [4], 2: []} 
 
Inserting 4
Moving 4 to front
{0: [9, 6], 1: [4], 2: []} 
 
Inserting 5
{0: [9, 6], 1: [4], 2: [5]} 
 
Inserting 6
Moving 6 to front
{0: [6, 9], 1: [4], 2: [5]} 
 
Inserting 3
{0: [6, 9, 3], 1: [4], 2: [5]} 
 
Inserting 6
Moving 6 to front
{0: [6, 9, 3], 1: [4], 2: [5]} 
 
Inserting 9
Moving 9 to front
{0: [9, 6, 3], 1: [4], 2: [5]} 
 
Inserting 5
Moving 5 to front
{0: [9, 6, 3], 1: [4], 2: [5]} 
 
Inserting 2
{0: [9, 6, 3], 1: [4], 2: [5, 2]} 
 
Inserting 3
Moving 3 to front
{0: [3, 9, 6], 1: [4], 2: [5, 2]}

<pre> Inserting 9 {0: [9], 1: [], 2: []} Inserting 6 {0: [9, 6], 1: [], 2: []} Inserting 4 {0: [9, 6], 1: [4], 2: []} Inserting 4 Moving 4 to front {0: [9, 6], 1: [4], 2: []} Inserting 5 {0: [9, 6], 1: [4], 2: [5]} Inserting 6 Moving 6 to front {0: [6, 9], 1: [4], 2: [5]} Inserting 3 {0: [6, 9, 3], 1: [4], 2: [5]} Inserting 6 Moving 6 to front {0: [6, 9, 3], 1: [4], 2: [5]} Inserting 9 Moving 9 to front {0: [9, 6, 3], 1: [4], 2: [5]} Inserting 5 Moving 5 to front {0: [9, 6, 3], 1: [4], 2: [5]} Inserting 2 {0: [9, 6, 3], 1: [4], 2: [5, 2]} Inserting 3 Moving 3 to front {0: [3, 9, 6], 1: [4], 2: [5, 2]} </pre>

-- Mar 23 In-Class Exercise

Given : 9 6 4 4 5 6 3 6 9 5 2 3
Insert 9
{0: [9], 1: [], 2: []} 
 
Insert 6
{0: [9, 6], 1: [], 2: []} 
 
Insert 4
{0: [9, 6], 1: [4], 2: []} 
 
Insert 4
Move 4 to front
{0: [9, 6], 1: [4], 2: []} 
 
Insert 5
{0: [9, 6], 1: [4], 2: [5]} 
 
Insert 6
Move 6 to front
{0: [6, 9], 1: [4], 2: [5]} 
 
Insert 3
{0: [6, 9, 3], 1: [4], 2: [5]} 
 
Insert 6
Move 6 to front
{0: [6, 9, 3], 1: [4], 2: [5]} 
 
Insert 9
Move 9 to front
{0: [9, 6, 3], 1: [4], 2: [5]} 
 
Insert 5
Move 5 to front
{0: [9, 6, 3], 1: [4], 2: [5]} 
 
Insert 2
{0: [9, 6, 3], 1: [4], 2: [5, 2]} 
 
Insert 3
Move 3 to front
{0: [3, 9, 6], 1: [4], 2: [5, 2]}

(Edited: 2022-03-23)

<pre> Given : 9 6 4 4 5 6 3 6 9 5 2 3 Insert 9 {0: [9], 1: [], 2: []} Insert 6 {0: [9, 6], 1: [], 2: []} Insert 4 {0: [9, 6], 1: [4], 2: []} Insert 4 Move 4 to front {0: [9, 6], 1: [4], 2: []} Insert 5 {0: [9, 6], 1: [4], 2: [5]} Insert 6 Move 6 to front {0: [6, 9], 1: [4], 2: [5]} Insert 3 {0: [6, 9, 3], 1: [4], 2: [5]} Insert 6 Move 6 to front {0: [6, 9, 3], 1: [4], 2: [5]} Insert 9 Move 9 to front {0: [9, 6, 3], 1: [4], 2: [5]} Insert 5 Move 5 to front {0: [9, 6, 3], 1: [4], 2: [5]} Insert 2 {0: [9, 6, 3], 1: [4], 2: [5, 2]} Insert 3 Move 3 to front {0: [3, 9, 6], 1: [4], 2: [5, 2]} </pre>

-- Mar 23 In-Class Exercise

(Edited: 2022-03-23)

((resource:Screenshot (41).png|Resource Description for Screenshot (41).png))

-- Mar 23 In-Class Exercise

9 6 4 4 5 6 3 6 9 5 2 3 hash function -> n%3

9 0 -> 9 PostingList [0]

1 ->

2 ->

6

0 -> 9 PostingList [0] , 6 PostingList [1]

1 ->

2 ->

4

0 -> 9 PostingList [0] , 6 PostingList [1]

1 -> 4 PostingList [2]

2 ->

4

0 -> 9 PostingList [0] , 6 PostingList [1]

1 -> 4 PostingList [2,3]

2 ->

5

0 -> 9 PostingList [0] , 6 PostingList [1]

1 -> 4 PostingList [2,3]

2 -> 5 PostingList [4]

6

0 -> 6 PostingList [1,5] , 9 PostingList [0]

1 -> 4 PostingList [2,3]

2 -> 5 PostingList [4]

3

0 -> 6 PostingList [1,5] , 9 PostingList [0], 3 PostingList [6]

1 -> 4 PostingList [2,3]

2 -> 5 PostingList [4]

6

0 -> 6 PostingList [1,5,7] , 9 PostingList [0], 3 PostingList [6]

1 -> 4 PostingList [2,3]

2 -> 5 PostingList [4]

9

0 -> 9 PostingList [0,8], 6 PostingList [1,5,7], 3 PostingList [6]

1 -> 4 PostingList [2,3]

2 -> 5 PostingList [4,9]

5

0 -> 9 PostingList [0,8], 6 PostingList [1,5,7], 3 PostingList [6]

1 -> 4 PostingList [2,3]

2 -> 5 PostingList [4,9]

2

0 -> 9 PostingList [0,8], 6 PostingList [1,5,7], 3 PostingList [6]

1 -> 4 PostingList [2,3]

2 -> 5 PostingList [4,9], 2 PostingList [10]

3

0 -> 3 PostingList [6,11], 9 PostingList [0,8], 6 PostingList [1,5,7]

1 -> 4 PostingList [2,3]

2 -> 5 PostingList [4,9], 2 PostingList [10]

(Edited: 2022-03-24)

9 6 4 4 5 6 3 6 9 5 2 3 hash function -> n%3 9 0 -> 9 PostingList [0] 1 -> 2 -> 6 0 -> 9 PostingList [0] , 6 PostingList [1] 1 -> 2 -> 4 0 -> 9 PostingList [0] , 6 PostingList [1] 1 -> 4 PostingList [2] 2 -> 4 0 -> 9 PostingList [0] , 6 PostingList [1] 1 -> 4 PostingList [2,3] 2 -> 5 0 -> 9 PostingList [0] , 6 PostingList [1] 1 -> 4 PostingList [2,3] 2 -> 5 PostingList [4] 6 0 -> 6 PostingList [1,5] , 9 PostingList [0] 1 -> 4 PostingList [2,3] 2 -> 5 PostingList [4] 3 0 -> 6 PostingList [1,5] , 9 PostingList [0], 3 PostingList [6] 1 -> 4 PostingList [2,3] 2 -> 5 PostingList [4] 6 0 -> 6 PostingList [1,5,7] , 9 PostingList [0], 3 PostingList [6] 1 -> 4 PostingList [2,3] 2 -> 5 PostingList [4] 9 0 -> 9 PostingList [0,8], 6 PostingList [1,5,7], 3 PostingList [6] 1 -> 4 PostingList [2,3] 2 -> 5 PostingList [4,9] 5 0 -> 9 PostingList [0,8], 6 PostingList [1,5,7], 3 PostingList [6] 1 -> 4 PostingList [2,3] 2 -> 5 PostingList [4,9] 2 0 -> 9 PostingList [0,8], 6 PostingList [1,5,7], 3 PostingList [6] 1 -> 4 PostingList [2,3] 2 -> 5 PostingList [4,9], 2 PostingList [10] 3 0 -> 3 PostingList [6,11], 9 PostingList [0,8], 6 PostingList [1,5,7] 1 -> 4 PostingList [2,3] 2 -> 5 PostingList [4,9], 2 PostingList [10]

-- Mar 23 In-Class Exercise

1.

 Bin 0 -> 9 (PL 0 )
 Bin 1 ->
 Bin 2 ->

2.

 Bin 0 -> 9 (PL 0 )-> 6 (PL1)
 Bin 1 ->
 Bin 2 ->

3.

 Bin 0 -> 9 (PL 0 )-> 6 (PL1)
 Bin 1 -> 4 (PL 2)
 Bin 2 ->

4.

 Bin 0 -> 9 (PL 0 )-> 6 (PL1)
 Bin 1 -> 4 (PL 2, PL 3)
 Bin 2 ->

5.

 Bin 0 -> 9 (PL 0 )-> 6 (PL1)
 Bin 1 -> 4 (PL 2, PL 3)
 Bin 2 -> 5 (PL 4)

6.

 Bin 0 -> 6 (PL1, PL 5) - >9 (PL 0 )
 Bin 1 -> 4 (PL 2, PL 3)
 Bin 2 -> 5 (PL 4)

7.

 Bin 0 -> 6 (PL1, PL 5) - >9 (PL 0) -> 3 (PL6)
 Bin 1 -> 4 (PL 2, PL 3)
 Bin 2 -> 5 (PL 4)

8.

 Bin 0 -> 6 (PL1, PL 5, PL 7) - >9 (PL 0) -> 3 (PL6)
 Bin 1 -> 4 (PL 2, PL 3)
 Bin 2 -> 5 (PL 4)

9.

 Bin 0 -> 9 (PL 0, PL 8) -> 6 (PL1, PL 5, PL 7) -> 3 (PL6)
 Bin 1 -> 4 (PL 2, PL 3)
 Bin 2 -> 5 (PL 4)

10.

 Bin 0 -> 9 (PL 0, PL 8) -> 6 (PL1, PL 5, PL 7) -> 3 (PL6)
 Bin 1 -> 4 (PL 2, PL 3)
 Bin 2 -> 5 (PL 4, PL 9)

10.

 Bin 0 -> 9 (PL 0, PL 8) -> 6 (PL1, PL 5, PL 7) -> 3 (PL6)
 Bin 1 -> 4 (PL 2, PL 3)
 Bin 2 -> 5 (PL 4, PL 9) -> 2 (PL 10)

11.

 Bin 0 -> 3 (PL6, PL 11) -> 9 (PL 0, PL 8) -> 6 (PL1, PL 5, PL 7)
 Bin 1 -> 4 (PL 2, PL 3)
 Bin 2 -> 5 (PL 4, PL 9) -> 2 (PL 10)

(Edited: 2022-03-24)

1. Bin 0 -> 9 (PL 0 ) Bin 1 -> Bin 2 -> 2. Bin 0 -> 9 (PL 0 )-> 6 (PL1) Bin 1 -> Bin 2 -> 3. Bin 0 -> 9 (PL 0 )-> 6 (PL1) Bin 1 -> 4 (PL 2) Bin 2 -> 4. Bin 0 -> 9 (PL 0 )-> 6 (PL1) Bin 1 -> 4 (PL 2, PL 3) Bin 2 -> 5. Bin 0 -> 9 (PL 0 )-> 6 (PL1) Bin 1 -> 4 (PL 2, PL 3) Bin 2 -> 5 (PL 4) 6. Bin 0 -> 6 (PL1, PL 5) - >9 (PL 0 ) Bin 1 -> 4 (PL 2, PL 3) Bin 2 -> 5 (PL 4) 7. Bin 0 -> 6 (PL1, PL 5) - >9 (PL 0) -> 3 (PL6) Bin 1 -> 4 (PL 2, PL 3) Bin 2 -> 5 (PL 4) 8. Bin 0 -> 6 (PL1, PL 5, PL 7) - >9 (PL 0) -> 3 (PL6) Bin 1 -> 4 (PL 2, PL 3) Bin 2 -> 5 (PL 4) 9. Bin 0 -> 9 (PL 0, PL 8) -> 6 (PL1, PL 5, PL 7) -> 3 (PL6) Bin 1 -> 4 (PL 2, PL 3) Bin 2 -> 5 (PL 4) 10. Bin 0 -> 9 (PL 0, PL 8) -> 6 (PL1, PL 5, PL 7) -> 3 (PL6) Bin 1 -> 4 (PL 2, PL 3) Bin 2 -> 5 (PL 4, PL 9) 10. Bin 0 -> 9 (PL 0, PL 8) -> 6 (PL1, PL 5, PL 7) -> 3 (PL6) Bin 1 -> 4 (PL 2, PL 3) Bin 2 -> 5 (PL 4, PL 9) -> 2 (PL 10) 11. Bin 0 -> 3 (PL6, PL 11) -> 9 (PL 0, PL 8) -> 6 (PL1, PL 5, PL 7) Bin 1 -> 4 (PL 2, PL 3) Bin 2 -> 5 (PL 4, PL 9) -> 2 (PL 10)