Assignment 1
1. For proving the bound Θ ( f ( n ) ) it is enough to prove that the algorithm has O ( f ( n ) )∧Ω(f ( n ) )
bounds.
O ( f ( n ) ) proof:
The outer loop runs max n times.
The inner loop also runs max n times
The addition operations are at max over n times.
3
¿> f ( n )=n
And the algorithm is O(n 3)
2. Let b = 11
The binary representation of b = 1011
Calculating by repeated squares:
Bit 1 is 1, so r->r^2(=a^0), so we compute r->r.a(=a^1)
Bit 2 is 0, r ->r^2(a^2), but since bit 2 is 0 , we don’t compute r
Bit 3 is 1, r->r^2(a^4), r->r.a(a^5)
Bit 4 is 1, r->r^2(a^10), r->r.a=a^11
3. p=11
q = 13
Product N = (p-1)(q-1) = 10*12 = 120
For e, we find relatively prime numbers to 120.
Three such numbers are 7,11 and 13.
Now d is the inverse of e modulo N
d = e-1 (modulo 120)
de=1(mod 120)
To find d, we solve the equation9olr
de + Ny = 1
In the following steps, we calculate the value of d with each corresponding value of e:
First, e=7:
The equation becomes:
7d+120y=1
GCD(120,7)
120 = 7.17+1
1 = 120-7.17
We get -17
To convert it to a positive value, we use the equality:
-a(mod n) = (n-a)(mod n)
Which gives us,
(120-17)(mod 120) = 103
So d = 103 for e=7
Next, e = 11:
The equation:
11d+120y = 1
120 = 10*11+10
11 = 1*10 + 1
1 = 11 – 10*1
= 11 – (120-10*11)
= -120+11*11
So, d = 11 for e = 11
Last, e = 13:
120 = 9*13+3
13 = 4*3 + 1
1 = 13 – 4*3
= 13 – 4*(120-9*13)
= -480 + 37*13
So, d = 37 for e = 13
Final Answer:
The three pairs of d and e are:
d = 103,e=7
d = 11,e=11
d=37,e=13
4(a).
Sequence = {9, 16, 4, 5, 12, 27, 3, 10, 14, 1330}
Hash function = 3k+1(mod 11)
Calculating the hash values= {6, 5, 2, 5, 4, 5, 10, 9, 10, 9}
Inserting the values in the hash table:
H(k) = 3k+1(mod 11) Keys
0
1
2 4
3
4 12
5 16->5->27
6 9
7
8
9 10->1330
10 3->14
4(b). Characterstics of a good hash function:
1. 1) The hash value is fully determined by the data being hashed – This is true for this case
2. 2) The hash function uses all the input data. – This Is also true as we use all the input integers
from 1 to 1000
3. The hash function "uniformly" distributes the data across the entire set of possible hash values –
For this, I wrote a python program to calculate the hash values and plotted it using a histogram.
modfunlist = [((math.floor(math.sqrt(i)*math.log(i)))%31)for i in range(1,1001)]
plt.hist (modfunlist,bins=range(0,32),density=True)
As we can see, the it is a uniform distribution.
Hence, this is a good hash function.
4(c).
Any function that would give the same hash values with respect to the input sequence S = {1, 5, 8, 9}
would be a worst hash function.
Now, given that the hash function is of the form:
ha,b(x) = ((ax + b) (mod N)) (mod m)
N=11 and m=4
Suppose let y = (ax + b) (mod N), then ha,b(x) = y (mod m)
Ha,b = y (mod 4) will give the same value if the value of y is less than 4.
Now considering our function y:
y = (ax + b) (mod 11)
If a=11, then y is of the form y = 11x+ b, and it would always leave b as the remainder. If this remainder
be is less than 4, it would always be of the same value and would be unaltered by the mod 4. So let b=1.
So our function y becomes of the form y = 11x+1, which when mod by 11 would always give 1 and would
have no effect when mod by 4.
So finally,
a = 11, b=1 and the “worst” hash function is ((11x + 1) (mod 11)) (mod 4)
Some other examples are a=11, b=0, a=11, b=2 and a=11, b=3
