Binary Search, Hashing, Tree Insertion And Search, Longest Common Subsequence, Pattern Matching, Transitive Closure Of A Directed Graph

(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

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

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

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

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>,

A₁ 7 × 10

A₂ 10 × 5

A₃ 5 × 18

A₄ 18 × 20

A₅ 20 × 40

A₆ 40 × 10

A₇ 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

A) Brute-force algorithm

Found pattern at index: 16

 B) Boyer-Moore Algorithm

Indexes:

Formula for BAD-MATCH TABLE values = length-index-1

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