Get Instant Help From 5000+ Experts For

Writing: Get your essay and assignment written from scratch by PhD expert

Rewriting: Paraphrase or rewrite your friend's essay with similar meaning at reduced cost

(a) Write pseudo-code for an iterative binary search algorithm, looking for v. Show that the running time of your algorithm is Θ(lg n).
(b) Write pseudo-code for a recursive binary search algorithm, looking for v. Show that the running time of your algorithm is Θ(lg n).
2. Draw the 13-entry hash table that results from using the hash function h(i) = (3i + 5) mod 13 to hash the keys 14, 42, 15, 81, 27, 92, 3, 39, 20, 16, and 5, assuming collisions are handled by:
(a) separate chaining;
(c) quadratic probing (up to the point where the method fails).
(d) Using the secondary hash function h

3. Insert entries with keys, 2, 7, 3, 12, 5, 20, 14, 6, 11, 8, 15, 17, 1, 19, 23, 14 (in this order), into an empty:
(a) heap.
(b) binary search tree.
(c) AVL tree.
(d) (2, 4) tree.
4. Consider the set of keys, 2, 15, 7, 33, 21, 5, 14, 17, 19, 11, 9, 41, 31, 71, 52, 67, 29, 27, 49. Using prune-and-search paradigm by picking the first element as pivot, determine the 9th element of these keys when they are sorted in ascending order.
5. Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is (7, 10, 5, 18,
20, 40, 10, 15). That is:
matrix dimension
———– —————
A1 7 × 10
A2 10 × 5
A3 5 × 18
A4 18 × 20
A5 20 × 40
A6 40 × 10
A7 10 × 15

6. Determine an LCS (Longest Common Subsequence) of sequences A = (1, 1, 1, 0, 0, 0, 1, 0, 1) and B =(0, 1, 0, 1, 0, 0, 1, 1).
7. Show all the steps for performing any of the following algorithms for matching the pattern ‘belabela’ in
the text ‘bellisalabelabelbelabela’.
(a) brute-force
(b) Boyer-Moore
(c) Knuth-Morris-Pratt

8. Consider a directed graph G, where its adjucency list is: Adjacent Vertices
————– ————————–
A B, C, D, E
B D, E
C A, B, E
D B, C, F
E A, C, F
F A, C, E
(a) Determine whether or not the graph G is strongly connected.
(b) Draw the transitive closure of graph G (show graphs GA, GB, GC, GD, GE, GF after each step of the Floyd-Warshall algorithm).

## Iterative and Recursive Binary Search with Pseudo-Code

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

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

1. a) Yes, graph G is a strongly connected graph as all the nodes are reachable from every other node in the graph as visible from the transitive closure chart below.
2. b) Transitive Closure
 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
Cite This Work

My Assignment Help. (2021). Binary Search, Hashing, Tree Insertion And Search, Longest Common Subsequence, Pattern Matching, Transitive Closure Of A Directed Graph. Retrieved from https://myassignmenthelp.com/free-samples/cp5602-advanced-algorithm-analysis/binary-search-algorithm.html.

"Binary Search, Hashing, Tree Insertion And Search, Longest Common Subsequence, Pattern Matching, Transitive Closure Of A Directed Graph." My Assignment Help, 2021, https://myassignmenthelp.com/free-samples/cp5602-advanced-algorithm-analysis/binary-search-algorithm.html.

My Assignment Help (2021) Binary Search, Hashing, Tree Insertion And Search, Longest Common Subsequence, Pattern Matching, Transitive Closure Of A Directed Graph [Online]. Available from: https://myassignmenthelp.com/free-samples/cp5602-advanced-algorithm-analysis/binary-search-algorithm.html
[Accessed 12 September 2024].

My Assignment Help. 'Binary Search, Hashing, Tree Insertion And Search, Longest Common Subsequence, Pattern Matching, Transitive Closure Of A Directed Graph' (My Assignment Help, 2021) <https://myassignmenthelp.com/free-samples/cp5602-advanced-algorithm-analysis/binary-search-algorithm.html> accessed 12 September 2024.

My Assignment Help. Binary Search, Hashing, Tree Insertion And Search, Longest Common Subsequence, Pattern Matching, Transitive Closure Of A Directed Graph [Internet]. My Assignment Help. 2021 [cited 12 September 2024]. Available from: https://myassignmenthelp.com/free-samples/cp5602-advanced-algorithm-analysis/binary-search-algorithm.html.

Get instant help from 5000+ experts for

Writing: Get your essay and assignment written from scratch by PhD expert

Rewriting: Paraphrase or rewrite your friend's essay with similar meaning at reduced cost