profile pic
⌘ '
raccourcis clavier
Search

LLRB and hash tables

  • Étiquette

    • publié à

    • modifié à

    • durée

      9 min de lecture

    • source

      llms.txt

    Problème 1.

    Consider the sequence of values S=[3,42,39,86,49,89,99,20,88,51,64]S=[3, 42, 39, 86, 49, 89, 99, 20, 88, 51, 64]

    1.1

    Draw a left-leaning red-black tree obtained by adding the values in S in sequence. Show each step.

    Let the following format as node: [R|B]-<value> where [R|B] denotes whether the node is red or black, followed by its value.

    The left-leaning red-black tree obtained by adding the values in S in sequence is as follows:

    1. S=[3]S=[3]
    B-3
    1. S=[3,42]S=[3, 42] New node become red, 42
    B-3
  \
   R-42
    1. S=[3,42,39]S=[3, 42, 39] New root 39, rotate color for 3, 42
      B-39
 /    \
R-3   R-42
    1. S=[3,42,39,86]S=[3, 42, 39, 86] Add 86, rotate color for tree
      B-39
 /    \
R-3   R-42
        \
        R-86
    1. S=[3,42,39,86,49]S=[3, 42, 39, 86, 49] Add 49, rotate color for tree 49, 42
      B-39
 /    \
R-3   R-49
      /  \
    R-42   R-86
    1. S=[3,42,39,86,49,89]S=[3, 42, 39, 86, 49, 89] Add 89, rotate color for 42, 86
      B-39
 /    \
R-3   R-49
      /  \
    B-42  B-86
            \
           R-89
    1. S=[3,42,39,86,49,89,99]S=[3, 42, 39, 86, 49, 89, 99] Add 99, rotate color for 86, 89
      B-39
 /    \
R-3   R-49
      /  \
    B-42  B-89
          /  \
        R-86 R-89
    1. S=[3,42,39,86,49,89,99,20]S=[3, 42, 39, 86, 49, 89, 99, 20] Add 20, right of 3, red. Rotate color of 3
          B-39
     /    \
    B-3   R-49
     |    |   \
    R-20 B-42 B-89
              /  \
            R-86 R-89
    1. S=[3,42,39,86,49,89,99,20,88]S=[3, 42, 39, 86, 49, 89, 99, 20, 88] Add 88, correct root of 49, balance tree to L-39. R-89
          B-49
     /    \
    R-39   R-89
    /  |    |   \
  B-3 R-42 B-86 B-99
   |        |
  R-20     R-88
    1. S=[3,42,39,86,49,89,99,20,88,51]S=[3, 42, 39, 86, 49, 89, 99, 20, 88, 51] Add 51, left of 86
          B-49
     /    \
    R-39   R-89
    /  |    |   \
  B-3 R-42 B-86 B-99
   |       /  \
R-20     R-51 R-88
    1. S=[3,42,39,86,49,89,99,20,88,51,64]S=[3, 42, 39, 86, 49, 89, 99, 20, 88, 51, 64] Add 64, 86 comes red, 64 becomes right of 51, rotate color 51, 88, 86
          B-49
     /    \
    R-39   R-89
    /  |    |   \
  B-3 R-42 R-86 B-99
   |       /  \
R-20     B-51 B-88
          |
         R-64

    1.2

    Consider the hash function h(x)=(x+7) mod 13h(x) = (x+7) \text{ mod } 13 a hash-table of 13 table entries that uses hashing with separate chaining. Draw the hash-table obtained by adding the values in SS in sequence. Show each step.

    The hash-table obtained by adding the values in SS in sequence is as follows:

    1. S=[3]S=[3] h(3)=10 mod 13=10h(3) = 10 \text{ mod } 13 = 10
    0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10: 3
11:
12:
    1. S=[3,42]S=[3, 42] h(42)=49 mod 13=10h(42) = 49 \text{ mod } 13 = 10 Collision with 3, chaining with 3
    0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10: 3 -> 42
11:
12:
    1. S=[3,42,39]S=[3, 42, 39] h(39)=46 mod 13=7h(39) = 46 \text{ mod } 13 = 7
    0:
1:
2:
3:
4:
5:
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:
    1. S=[3,42,39,86]S = [3, 42, 39, 86] h(86)=93 mod 13=2h(86) = 93 \text{ mod } 13 = 2
    0:
1:
2: 86
3:
4:
5:
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:
    1. S=[3,42,39,86,49]S = [3, 42, 39, 86, 49] h(49)=56 mod 13=4h(49) = 56 \text{ mod } 13 = 4
    0:
1:
2: 86
3:
4: 49
5:
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:
    1. S=[3,42,39,86,49,89]S = [3, 42, 39, 86, 49, 89] h(89)=96 mod 13=5h(89) = 96 \text{ mod } 13 = 5
    0:
1:
2: 86
3:
4: 49
5: 89
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:
    1. S=[3,42,39,86,49,89,99]S = [3, 42, 39, 86, 49, 89, 99] h(99)=106 mod 13=2h(99) = 106 \text{ mod } 13 = 2 Collide with 86, chaining with 86
    0:
1:
2: 86 -> 99
3:
4: 49
5: 89
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:
    1. S=[3,42,39,86,49,89,99,20]S = [3, 42, 39, 86, 49, 89, 99, 20] h(20)=27 mod 13=1h(20) = 27 \text{ mod } 13 = 1
    0:
1: 27
2: 86 -> 99
3:
4: 49
5: 89
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:
    1. S=[3,42,39,86,49,89,99,20,88]S = [3, 42, 39, 86, 49, 89, 99, 20, 88] h(88)=95 mod 13=4h(88) = 95 \text{ mod } 13 = 4 Collide with 49, chaining with 49
    0:
1: 27
2: 86 -> 99
3:
4: 49 -> 88
5: 89
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:
    1. S=[3,42,39,86,49,89,99,20,88,51]S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51] h(51)=58 mod 13=6h(51) = 58 \text{ mod } 13 = 6
    0:
1: 27
2: 86 -> 99
3:
4: 49 -> 88
5: 89
6: 51
7: 39
8:
9:
10: 3 -> 42
11:
12:
    1. S=[3,42,39,86,49,89,99,20,88,51,64]S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51, 64] h(64)=71 mod 13=6h(64) = 71 \text{ mod } 13 = 6 Collide with 51, chaining with 51
    0:
1: 27
2: 86 -> 99
3:
4: 49 -> 88
5: 89
6: 51 -> 64
7: 39
8:
9:
10: 3 -> 42
11:
12:

    1.3

    Consider the hash function h(x)=(x+7) mod 13h(x) = (x+7) \text{ mod } 13 a hash-table of 13 table entries that uses hashing with linear probing. Draw the hash-table obtained by adding the values in SS in sequence. Show each step.

    1. S=[3]S=[3] h(3)=10 mod 13=10h(3) = 10 \text{ mod } 13 = 10
    0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10: 3
11:
12:
    1. S=[3,42]S=[3, 42] h(42)=49 mod 13=10h(42) = 49 \text{ mod } 13 = 10 Collision with 3, increment index to 11
    0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10: 3
11: 42
12:
    1. S=[3,42,39]S=[3, 42, 39] h(39)=46 mod 13=7h(39) = 46 \text{ mod } 13 = 7
    0:
1:
2:
3:
4:
5:
6:
7: 39
8:
9:
10: 3
11: 42
12:
    1. S=[3,42,39,86]S = [3, 42, 39, 86] h(86)=93 mod 13=2h(86) = 93 \text{ mod } 13 = 2
    0:
1:
2: 86
3:
4:
5:
6:
7: 39
8:
9:
10: 3
11: 42
12:
    1. S=[3,42,39,86,49]S = [3, 42, 39, 86, 49] h(49)=56 mod 13=4h(49) = 56 \text{ mod } 13 = 4
    0:
1:
2: 86
3:
4: 49
5:
6:
7: 39
8:
9:
10: 3
11: 42
12:
    1. S=[3,42,39,86,49,89]S = [3, 42, 39, 86, 49, 89] h(89)=96 mod 13=5h(89) = 96 \text{ mod } 13 = 5
    0:
1:
2: 86
3:
4: 49
5: 89
6:
7: 39
8:
9:
10: 3
11: 42
12:
    1. S=[3,42,39,86,49,89,99]S = [3, 42, 39, 86, 49, 89, 99] h(99)=106 mod 13=2h(99) = 106 \text{ mod } 13 = 2 Collide with 86, increment index to 3
    0:
1:
2: 86
3: 99
4: 49
5: 89
6:
7: 39
8:
9:
10: 3
11: 42
12:
    1. S=[3,42,39,86,49,89,99,20]S = [3, 42, 39, 86, 49, 89, 99, 20] h(20)=27 mod 13=1h(20) = 27 \text{ mod } 13 = 1
    0:
1: 27
2: 86
3: 99
4: 49
5: 89
6:
7: 39
8:
9:
10: 3
11: 42
12:
    1. S=[3,42,39,86,49,89,99,20,88]S = [3, 42, 39, 86, 49, 89, 99, 20, 88] h(88)=95 mod 13=4h(88) = 95 \text{ mod } 13 = 4 Collide with 49, index to 5 at 5, collide with 89, index to 6
    0:
1: 27
2: 86
3: 99
4: 49
5: 89
6: 88
7: 39
8:
9:
10: 3
11: 42
12:
    1. S=[3,42,39,86,49,89,99,20,88,51]S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51] h(51)=58 mod 13=6h(51) = 58 \text{ mod } 13 = 6 Collide with 88, index to 7 at 7, collide with 39, index to 8
    0:
1: 27
2: 86
3: 99
4: 49
5: 89
6: 88
7: 39
8: 51
9:
10: 3
11: 42
12:
    1. S=[3,42,39,86,49,89,99,20,88,51,64]S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51, 64] h(64)=71 mod 13=6h(64) = 71 \text{ mod } 13 = 6 Collide with 88, index to 7 at 7, collide with 39, index to 8 at 8, collide with 51, index to 9
    0:
1: 27
2: 86
3: 99
4: 49
5: 89
6: 88
7: 39
8: 51
9: 64
10: 3
11: 42
12:

    Problème 2.

    Consider a list LL of NN sorted values. Show how to construct a valid left-leaning red-black tree holding the values in LL in Θ(N)\Theta(N)

    Solution

    The following depicts the pseudocode implementation of the program

    "\\begin{algorithm}\n\\caption{BuildLLRBTree($L, \\text{start}, \\text{end}$)}\n\\begin{algorithmic}\n\\IF{$\\text{start} > \\text{end}$}\n \\RETURN $NULL$\n\\ENDIF\n\\STATE $\\text{mid} \\gets (start + end) / 2$\n\\STATE $\\text{left} \\gets BuildLLRBTree(L, start, mid-1)$\n\\STATE $\\text{right} \\gets BuildLLRBTree(L, mid+1, end)$\n\\STATE $\\text{node} \\gets$ new Node($L[mid]$)\n\\STATE $\\text{node.left} \\gets left$\n\\STATE $\\text{node.right} \\gets right$\n\\STATE $\\text{node.color} \\gets \\text{BLACK}$\n\\RETURN $node$\n\\end{algorithmic}\n\\end{algorithm}"

    Algorithm 35 BuildLLRBTree(L,start,endL, \text{start}, \text{end})

    1:if start>end\text{start} > \text{end} then

    2:return NULLNULL

    3:end if

    4:mid←(start+end)/2\text{mid} \gets (start + end) / 2

    5:left←BuildLLRBTree(L,start,mid−1)\text{left} \gets BuildLLRBTree(L, start, mid-1)

    6:right←BuildLLRBTree(L,mid+1,end)\text{right} \gets BuildLLRBTree(L, mid+1, end)

    7:node←\text{node} \gets new Node(L[mid]L[mid])

    8:node.left←left\text{node.left} \gets left

    9:node.right←right\text{node.right} \gets right

    10:node.color←BLACK\text{node.color} \gets \text{BLACK}

    11:return nodenode

    Problème 3.

    Consider a set of strings SS. We want to figure out whether SS has duplicates efficiently. We do not want to do so by sorting SS and then checking for duplicates: comparing strings can be a lot of work (e.g., they might differ in only a single character). Assume that you have a hash function hh that can compute a suitable hash code for any string s∈Ss \in S in O(∣s∣)\mathcal{O}(|s|). Show how one can use hashing to find whether SS has duplicates without performing many comparisons between strings. Your algorithm should have an expected runtime of O(∣S∣)\mathcal{O}(|S|) in which ∣S∣=∑s∈S∣s∣|S| = \sum_{s \in S}|s| represents the total length of all strings in SS.

    Solution

    "\\begin{algorithm}\n\\caption{Check for Duplicates Using Hashing}\n\\begin{algorithmic}\n\\Require A set of strings $S$\n\\Ensure True if there are duplicates in $S$, False otherwise\n\\State Initialize an empty hash table $H$\n\\For{each string $s \\in S$}\n \\State Compute $h(s)$ using the hash function\n \\If{$h(s)$ is in $H$}\n \\For{each string $s' \\in H[h(s)]$}\n \\If{$s = s'$}\n \\State \\Return True\n \\EndIf\n \\EndFor\n \\State Append $s$ to $H[h(s)]$\n \\Else\n \\State Insert $s$ into $H$ at $h(s)$\n \\EndIf\n\\EndFor\n\\State \\Return False\n\\end{algorithmic}\n\\end{algorithm}"

    Algorithm 36 Check for Duplicates Using Hashing

    Require: A set of strings SS

    Ensure: True if there are duplicates in SS, False otherwise

    1:Initialize an empty hash table HH

    2:for each string s∈Ss \in S do

    3:Compute h(s)h(s) using the hash function

    4:if h(s)h(s) is in HH then

    5:for each string s′∈H[h(s)]s' \in H[h(s)] do

    6:if s=s′s = s' then

    7:

    8:return True

    9:end if

    10:end for

    11:Append ss to H[h(s)]H[h(s)]

    12:else

    13:Insert ss into HH at h(s)h(s)

    14:end if

    15:end for

    16:

    17:return False

    Vous pourriez aimer ce qui suit

  • Threaded LED
  • Monte-Carlo methods
  • AGI
  • CIFAR100 with CNN
  • Linear regression
  • Moral
  • PCA and Kernels, from scratch