algorithms/Homework3.html at master · rakshitsareen/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
<html>
    <head>
        <link href="style.css" rel="stylesheet" type="text/css"/>
        <title>
            Design and Analysis of Algorithms: Homework 3
        </title>
    </head>

    <body>
        <h1>
            Design and Analysis of Algorithms: Homework 3
        </h1>
        <ol>
            <li>Demonstrate, in a double hashing situation, how the choice of the
                table size can lead to the algorithm working as designed, or
                completely failing. Buy "demonstrate", I mean show how a small
                table of the right size will fill up properly in double hashing
                while a table with a badly chosen size will stop accepting
                data before it is filled. Your answer should be something like,
                "First we will insert x and that will go in slot y... But when
                we come to insert z that will fail because..."

            <li>In the hiring problem with a randomized candidate list, please
                explain why the odds of hiring the i<sup>th</sup> candidate are
                1 / i.

            <li>Explain the difference between implementing a dictionary using
                direct addressing and simply using array indices to access some
                piece of data.

            <li>Explain why linear probing will tend to produce clusters.

            <li>Consider the following hashing scheme:
                <br>
                <em>h(k) = k mod m</em>
                <br>
                <em>m = 7</em>
                <br>We convert a string into a hashable key by treating it as a
                base-8 number.
                <br>So 'abc', where a = 1, b = 2, and c = 3, is converted to a
                key as follows: 1 * 8<sup>2</sup> + 2 * 8 + 3 = 83.
                <br>In this hashing scheme, what do the strings 'cba' and 'bac'
                hash to?
                <br>Can you write a more general statement about a pattern we
                can detect here? Something along the lines of, "If the table
                size is 2<sup>P</sup> - 1, and strings are interpreted in radix
                2<sup>P</sup>..."
                <br>
                <br>
                <b>Answer:</b>
                <br>
                <br>
                If <em>h(k) = k mod m</em>, where <em>m = 2<sup>P</sup> -
                    1</em>, and <em>k</em> is a character string interpreted in
                radix 2<sup>P</sup>, then all permutations of a given string
                will hash to the same value. So in the example above, 'abc',
                'cba', and 'bac' all hash to the same value.
                <br>
                <br>
                <b>Proof</b>:
                <br>
                <br>
                Assumed (could be proven, but we won't do it here):
                <ol>
                    <li> (x + y) mod z ==
                            (x mod z + y mod z) mod z
                        <br><b>Example:</b> (10 + 12) mod 7 ==
                        (10 mod 7 + 12 mod 7) mod 7
                    <li> (x * y) mod z ==
                            (x mod z) * (y mod z)
                        mod z
                        <br><b>Example:</b> (10 * 12) mod 7 ==
                        (10 mod 7) * (12 mod 7) mod 7
                        <br>(7 * 17 = 119)
                    <li>if x mod z == 1, then x<sup>n</sup> mod z == 1
                        <br><b>Example:</b> 8 mod 7 == 1, and
                        8<sup>2</sup> mod 7 == 1
                        <br>This is a special case of 2!
                </ol>
                <br>
                So, we have:
                <br>
                <br>
                <img src="https://raw.githubusercontent.com/gcallah/algorithms/master/graphics/H3Eq1.gif">
                <br>
                <br>
                <img src="https://raw.githubusercontent.com/gcallah/algorithms/master/graphics/H3Eq2.gif">
                <br>
                <br>
                <img src="https://raw.githubusercontent.com/gcallah/algorithms/master/graphics/H3Eq3.gif">
                <br>
                <br>
                <img
                src="https://raw.githubusercontent.com/gcallah/algorithms/master/graphics/H3Eq4.gif">
                &nbsp;&nbsp;(By 1)
                <br>
                <br>
                <img
                src="https://raw.githubusercontent.com/gcallah/algorithms/master/graphics/H3Eq5.gif">
                &nbsp;&nbsp;(By 2)
                <br>
                <br>
                <img
                src="https://raw.githubusercontent.com/gcallah/algorithms/master/graphics/H3Eq6.gif">
                &nbsp;&nbsp;(By 3)
                <br>
                <br>
                <img
                src="https://raw.githubusercontent.com/gcallah/algorithms/master/graphics/H3Eq7.gif">
              </ol>
    </body>
    <!-- google_analytics -->
    <script>
        (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
        (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
        m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
        })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
        ga('create', 'UA-97026578-2', 'auto');
        ga('send', 'pageview');
    </script>
    <!-- end google_analytics -->
</html>