BinarySearch(A[1..n], v)
//considering the array is sorted in increasing order
low = 0
high = n – 1
while low <= high
mid = (low + high) / 2
if A[mid] > v
high = mid – 1
else if A[mid] < v
low = mid + 1
else
return mid
return v_not_found
Complexity: O(log n)
b) Iterative Binary Search
BinarySearch(A[1..n], v, low, high)
//considering the array is sorted in increasing order
if high < low
return v_not_found
mid = (low + high) / 2
if A[mid] > v
return BinarySearch(A[], v, low, mid-1) //recursive call with first half of array
else if A[mid] < v
return BinarySearch(A[], v, mid+1, high) //recursive call with last half of array
else
return mid
Complexity: O(log n)
For Binary Search, T(N) = T(N/2) + O(1) This is the recurrence relation.
Applying Masters Theorem to compute Run time complexity of recurrence relation:
T(N) = aT(N/b) + f(N)
Now,
a = 1 and b = 2
=> log (a base b) = 1
f(N) = n^c log^k(n) //k = 0 & c = log (a base b)
So, T(N) = O(N^c log^(k+1)N)
= O(log(N))
Question 2
a) Separate Chaining
Hash function h(i) = (3i + 5) mod 13
Set of keys= 14, 42, 15, 81, 27, 92, 3, 39, 20, 16, and 5
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
20 |
42 |
39 |
5 |
14 |
15 |
|||||||
|
81 |
27 |
|||||||||||
|
3 |
92 |
|||||||||||
|
16 |
Linear Probing
Hash function h(i) = (3i + 5) mod 13
Set of keys= 14, 42, 15, 81, 27, 92, 3, 39, 20, 16, and 5
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
20 |
42 |
81 |
3 |
16 |
39 |
5 |
14 |
27 |
92 |
15 |
Quadratic Probing
Hash function h(i) = (3i + 5) mod 13
Set of keys= 14, 42, 15, 81, 27, 92, 3, 39, 20, 16, and 5
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
20 |
42 |
92 |
5 |
16 |
39 |
27 |
81 |
14 |
3 |
15 |
Secondary Hashing
Hash function h(i) = (3i + 5) mod 13
Hash function h’(i) = 11 − (i mod 11)
Set of keys= 14, 42, 15, 81, 27, 92, 3, 39, 20, 16, and 5
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
42 |
27 |
81 |
14 |
15 |
Method failed with the attempt to insert 92.
Question 3
Keys: 2, 7, 3, 12, 5, 20, 14, 6, 11, 8, 15, 17, 1, 19, 23, 14
Question 4
A = (1, 1, 1, 0, 0, 0, 1, 0, 1)
B = (0, 1, 0, 1, 0, 0, 1, 1)
LCS of A and B is (1, 0, 0, 0, 1, 1)
Question 5
Using the given matrix-chain <7, 10, 5, 18, 20, 40, 10, 15>,
A1 7 × 10
A2 10 × 5
A3 5 × 18
A4 18 × 20
A5 20 × 40
A6 40 × 10
A7 10 × 15
p0=7, p1=10, p2=5, p3=18, p4=20, p5=40, p6=10, p7=15
m[i, j] = 0, if i = j,
m[i,j]= {min {m[i,k] + m[k+1, j] + pi –1pkpj}}, if i < j
[1,1] = m[2,2] = m[3,3] = m[4,4] = m[5,5] = m[6,6] = m[7,7] = 0
m[1,2] = p0xp1xp2 = 7x10x5 = 350
m[2,3] = p1xp2xp3 = 10x5x18 = 900
m[3,4] = p2xp3xp4 = 5x18x20 = 1800
m[4,5] = p3xp4xp5 = 18x20x40 = 14400
m[5,6] = p4xp5xp6 = 20x40x10 = 8000
m[6,7] = p4xp5xp6 = 40x10x15 = 6000
|
m |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
1 |
0 |
350 |
|||||
|
2 |
0 |
900 |
|||||
|
3 |
0 |
1800 |
|||||
|
4 |
0 |
14400 |
|||||
|
5 |
0 |
8000 |
|||||
|
6 |
0 |
6000 |
|||||
|
7 |
0 |
A) Brute-force algorithm
|
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|||||||||
|
l |
l |
i |
s |
a |
l |
a |
b |
e |
l |
a |
b |
e |
l |
b |
|||||||||
|
l |
a |
b |
e |
l |
a |
||||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
Found pattern at index: 16
B) Boyer-Moore Algorithm
Indexes:
Formula for BAD-MATCH TABLE values = length-index-1
|
Letter |
b |
e |
l |
a |
* |
|
Value |
3 |
2 |
1 |
8 |
8 |
|
b |
e |
l |
l |
i |
s |
a |
l |
a |
b |
e |
l |
a |
b |
e |
l |
b |
e |
l |
a |
b |
e |
l |
a |
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
||||||||||||||||
|
b |
e |
l |
a |
b |
e |
l |
a |
Match Found
Build Comparisons= 7
Search Comparisons= 27
Match Found
Question 8
|
|
A |
B |
C |
D |
E |
F |
|
A |
1 |
1 |
1 |
1 |
1 |
1 |
|
B |
1 |
1 |
1 |
1 |
1 |
1 |
|
C |
1 |
1 |
1 |
1 |
1 |
1 |
|
D |
1 |
1 |
1 |
1 |
1 |
1 |
|
E |
1 |
1 |
1 |
1 |
1 |
1 |
|
F |
1 |
1 |
1 |
1 |
1 |
1 |
Essay Writing Service Features
Our Experience
No matter how complex your assignment is, we can find the right professional for your specific task. Contact Essay is an essay writing company that hires only the smartest minds to help you with your projects. Our expertise allows us to provide students with high-quality academic writing, editing & proofreading services.
Free Features
Free revision policy
$10Free bibliography & reference
$8Free title page
$8Free formatting
$8How Our Essay Writing Service Works
First, you will need to complete an order form. It's not difficult but, in case there is anything you find not to be clear, you may always call us so that we can guide you through it. On the order form, you will need to include some basic information concerning your order: subject, topic, number of pages, etc. We also encourage our clients to upload any relevant information or sources that will help.
Complete the order form
Once we have all the information and instructions that we need, we select the most suitable writer for your assignment. While everything seems to be clear, the writer, who has complete knowledge of the subject, may need clarification from you. It is at that point that you would receive a call or email from us.
Writer’s assignment
As soon as the writer has finished, it will be delivered both to the website and to your email address so that you will not miss it. If your deadline is close at hand, we will place a call to you to make sure that you receive the paper on time.
Completing the order and download