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

-- Mar 17 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: 1 4 2: 2 5 Lookup 6 0: 6 3 1: 1 4 2: 2 5 Lookup 6 0: 6 3 1: 1 4 2: 2 5 Lookup 6 0: 6 3 1: 1 4 2: 2 5 Insert 9 0: 6 3 9 1: 1 4 2: 2 5 Lookup 5 0: 6 3 9 1: 1 4 2: 5 2 Lookup 2 0: 6 3 9 1: 1 4 2: 2 5 Lookup 3 0: 3 6 9 1: 1 4 2: 2 5

-- Mar 17 In-Class Exercise Thread

n%3->index<br> |----------|<br> 1%3->1<br> 2%3->2<br> 3%3->0<br> 4%3->1<br> 5%3->2<br> 6%3->0<br> 9%3->0<br> Steps 1 through 6 are basic insertions, so our dictionary will look like this:<br> 0: 3 6<br> 1: 1 4<br> 2: 2 5<br> <br> Steps 7 and 8 move 6 to the front of its index (0):<br> 0: 6 3<br> 1: 1 4<br> 2: 2 5<br> <br> Step 9 inserts 9, which goes to the end of index 0:<br> 0: 6 3 9<br> 1: 1 4<br> 2: 2 5<br> <br> Step 10 looks up 5, which moves 5 to the front of index 2:<br> 0: 6 3 9<br> 1: 1 4<br> 2: 5 2<br> <br> Step 11 looks up 2, which moves 2 to the front of index 2:<br> 0: 6 3 9<br> 1: 1 4<br> 2: 2 5<br> <br> Step 12 looks up 3, which moves 3 to the front of index 0:<br> 0: 3 6 9<br> 1: 1 4<br> 2: 2 5<br>

-- Mar 17 In-Class Exercise Thread

<nowiki> n%3 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 : 1 -> 4 2 : 2 -> 5 move 6 to front 0 : 6 -> 3 1 : 1 -> 4 2 : 2 -> 5 move 6 to front 0 : 6 -> 3 1 : 1 -> 4 2 : 2 -> 5 insert 9 0 : 6 -> 3 -> 9 1 : 1 -> 4 2 : 2 -> 5 move 5 to front 0 : 6 -> 3 -> 9 1 : 1 -> 4 2 : 5 -> 2 move 2 to front 0 : 6 -> 3 -> 9 1 : 1 -> 4 2 : 2 -> 5 move 3 to front 0 : 3 -> 6 -> 9 1 : 1 -> 4 2 : 2 -> 5 </nowiki>

-- Mar 17 In-Class Exercise Thread

<nowiki> Corpus: 1 2 3 4 5 6 6 6 9 5 2 3 Hash Function n%3 n = 1; 1%3 = 1 LL 0: LL 1: 1 LL 2: n = 2; 2%3 = 2 LL 0: LL 1: 1 LL 2: 2 n = 3; 3%3 = 0 LL 0: 3 LL 1: 1 LL 2: 2 n = 4; 4%3 = 1 LL 0: 3 LL 1: 1 -> 4 LL 2: 2 n = 5; 5%3 = 2 LL 0: 3 LL 1: 1 -> 4 LL 2: 2 -> 5 n = 6; 6%3 = 0 LL 0: 3 -> 6 LL 1: 1 -> 4 LL 2: 2 -> 5 n = 6; term exist -> move to front LL 0: 6 -> 3 LL 1: 1 -> 4 LL 2: 2 -> 5 n = 6; term exist -> move to front LL 0: 6 -> 3 LL 1: 1 -> 4 LL 2: 2 -> 5 n = 9; 9%3 = 0 LL 0: 6 -> 3 -> 9 LL 1: 1 -> 4 LL 2: 2 -> 5 n = 5; term exists -> move to front LL 0: 6 -> 3 -> 9 LL 1: 1 -> 4 LL 2: 5 -> 2 n = 2; term exists -> move to front LL 0: 6 -> 3 -> 9 LL 1: 1 -> 4 LL 2: 2 -> 5 n = 3; term exists -> move to front LL 0: 3 -> 6 -> 9 LL 1: 1 -> 4 LL 2: 2 -> 5 </nowiki>

-- Mar 17 In-Class Exercise Thread

insert 1 hash table: [0:[], 1:[1], 2:[]] insert 2 hash table: [0:[], 1:[1], 2:[2]] insert 3 hash table: [0:[3], 1:[1], 2:[2]] insert 4 hash table: [0:[3], 1:[1, 4], 2:[2]] insert 5 hash table: [0:[3], 1:[1, 4], 2:[2, 5]] insert 6 hash table: [0:[3, 6], 1:[1, 4], 2:[2, 5]] lookup 6 hash table: [0:[6, 3], 1:[1, 4], 2:[2, 5]] lookup 6 hash table: [0:[6, 3], 1:[1, 4], 2:[2, 5]] insert 9 hash table: [0:[6, 3, 9], 1:[1, 4], 2:[2, 5]] lookup 5 hash table: [0:[6, 3, 9], 1:[1, 4], 2:[5, 2]] lookup 2 hash table: [0:[6, 3, 9], 1:[1, 4], 2:[2, 5]] lookup 3 hash table: [0:[3, 6, 9], 1:[1, 4], 2:[2, 5]]

-- Mar 17 In-Class Exercise Thread

steps 1-6: 0=> 3,6 1=>1,4 2=>2,5 steps 7 & 8: 0=> 6,3 1=>1,4 2=>2,5 step 9: 0=> 6,3,9 1=>1,4 2=>2,5 step 10: 0=> 6,3,9 1=>1,4 2=>5,2 step 11: 0=> 6,3,9 1=>1,4 2=>2,5 step 12: 0=> 6,3,9 1=>1,4 2=>2,5 step 13: 0=> 3,6,9 1=>1,4 2=>2,5

-- Mar 17 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 -> 1 4 2 -> 2 5 move-to-front for 6 and inserts in index 0 0 -> 6 3 1 -> 1 4 2 -> 2 5 insert-at-back for 9 and inserts in index 0 0 -> 6 3 9 1 -> 1 4 2 -> 2 5 lookups 5, move-to-front for 5 in index 2: 0 -> 6 3 9 1 -> 1 4 2 -> 5 2 lookups 2, move-to-front for 2 in index 2: 0 -> 6 3 9 1 -> 1 4 2 -> 2 5 lookups 3, move-to-front for 2 in index 0: 0 -> 3 6 9 1 -> 1 4 2 -> 2 5 final dictionary looks like 0 -> 3 6 9 1 -> 1 4 2 -> 2 5

-- Mar 17 In-Class Exercise Thread

1 2 3 4 5 6 6 6 9 5 2 3 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->1 4 2->2 5 insert 6: move to front 0->6 3 1->1 4 2->2 5 insert 6: move to front 0->6 3 1->1 4 2->2 5 insert 9: 0->6 3 9 1->1 4 2->2 5 insert 5: move to front 0->6 3 9 1->1 4 2->5 2 insert 2: move to front 0->6 3 9 1->1 4 2->2 5 insert 3:move to front 0->3 6 9 1->1 4 2->2 5 final: 0->3 6 9 1->1 4 2->2 5

-- Mar 17 In-Class Exercise Thread

1 2 3 4 5 6 6 6 9 5 2 3 * ;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: [1, 4], 2: [2, 5]} * ;Lookup 6 and move it to front: {0: [6, 3], 1: [1, 4], 2: [2, 5]} * ;Lookup 6 and move it to front: {0: [6, 3], 1: [1, 4], 2: [2, 5]} * ;Insert 9: {0: [6, 3, 9], 1: [1, 4], 2: [2, 5]} * ;Lookup 5 and move it to front: {0: [6, 3, 9], 1: [1, 4], 2: [5, 2]} * ;Lookup 2 and move it to front: {0: [6, 3, 9], 1: [1, 4], 2: [2, 5]} * ;Lookup 3 and move it to front: {0: [3, 6, 9], 1: [1, 4], 2: [2, 5]} Final dictionary: {0: [3, 6, 9], 1: [1, 4], 2: [2, 5]}