CP5602 Assignment SP2: Algorithms and Data Structures Solutions

This document presents solutions to a comprehensive assignment from the CP5602 course, focusing on algorithms and data structures. The assignment covers several key areas, including searching problems with iterative and recursive binary search algorithms, hash table implementations with separate chaining and probing techniques, and various tree structures such as heaps, binary search trees, AVL trees, and (2,4) trees. It also explores the prune-and-search paradigm, matrix chain product optimization, and the longest common subsequence problem. Furthermore, the assignment delves into string matching algorithms like brute-force, Boyer-Moore, and Knuth-Morris-Pratt, as well as graph theory concepts such as strongly connected graphs and transitive closures. The solutions include pseudocode, code snippets, and step-by-step explanations to facilitate understanding. The assignment is designed to improve critical thinking, problem-solving skills, and information literacy.

[Document title]
[Company name] | [Company address]

Searching Problem:
1. Input: an array A [1...n] of n elements and a value v.
Output: an index I such that A[i] =v or the special value NIL if v does not appear in A.
Assuming that array A is sorted (in ascending order):
(a) Write pseudo-code for an iterative binary search algorithm, looking for v. Show that the
running time of your algorithm is Θ (lg n).
Answer:
#include <stdio.h>
int binarySearch(int arr[], int v, int r, int x){
while (m<= r)
{
int v = m + (r-v)/2;
if (arr[v] == x)
return v;
if(arr[v] < x)
I =v+1;
else
r = v-1;
}
return -1;
}
(b) Write pseudo-code for a recursive binary search algorithm, looking for v. Show that the
running time of your algorithm is Θ(lg n)
Answer:
#include <stdio.h>
int binarySearch(int arr[], int v, int r, int x){
if(r>v){
int mid = v+(r-v)/2;
if(arr[mid]==x)
return mid;
pg. 1

if (arr[mid]>x)
return binarySearch(arr,v,mid-1,x);
return binarySearch(arr,v,mid-r,x);
}
return -1;
}
2. Draw the 13-entry hash table that results from using the hash function h(i) = (3 I + 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;
(b) linear probing.
0 1 2 3 4 5 6 7 8 9 10 11 12
14 42 15 81 27 92 3 39 non
e
none 20 16 5
(c) quadratic probing (up to the point where the method fails).
pg. 2

(d) Using the secondary hash function h′(i) = 11−(I mod 11).
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 _rst element as pivot,
determine the 9th element of these keys when they are sorted in ascending order.
Answer
/**
02.* Prune and search
03.* @param array array to be searched in
04.* @param index order of the searched value (indexed starting at 0)
05.* @param left first elemenent, which can be touched
06.* @param right first element, which cant be touched
07.* @return n-th largest value
08.*/
09.public static int pruneAndSearch(int[] array, int index, int left, int right)
{
10.int boundary = left;
11.for (int i = left + 1; i < right; i++) {
12.if (array[i] > array[left]) { //place after the pivot every value, which is
larger than the pivot
13.swap(array, i, ++boundary);
14.}
15.}
16.swap(array, left, boundary); //place pivot in the middle
17.//quicksort end
18.
19.if (boundary == index) return array[boundary]; //found
20.else if (boundary > index) return pruneAndSearch(array, index, left,
boundary); //prune the right branch
21.else return pruneAndSearch(array, index, boundary + 1, right); //prune the
left branch
22.}
pg. 3

23.
24./**
25.* Swap elements in the given array
26.* @param array array
27.* @param left index of the element 1
28.* @param right index of the element 2
29.*/
30.private static void swap(int[] array, int left, int right) {
31.int tmp = array[right];
32.array[right] = array[left];
33.array[left] = tmp;
34.}
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
Answer
/* A naive recursive implementation that simply
follows the above optimal substructure property */
#include<stdio.h>
#include<limits.h>
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
int MatrixChainOrder(int p[], int i, int j)
{
if(i == j)
return 0;
int k;
int min = INT_MAX;
int count;
// place parenthesis at different places between first
// and last matrix, recursively calculate count of
// multiplications for each parenthesis placement and
// return the minimum count
for (k = i; k <j; k++)
{
count = MatrixChainOrder(p, i, k) +
MatrixChainOrder(p, k+1, j) +
p[i-1]*p[k]*p[j];
if (count < min)
min = count;
}
pg. 4

// Return minimum count
return min;
}
// Driver program to test above function
int main()
{
int arr[] = {1, 2, 3, 4, 3};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Minimum number of multiplications is %d ",
MatrixChainOrder(arr, 1, n-1));
getchar();
return 0;
}
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).
Answer
0 0 0 0 0 0
0 1 1 1 1 1
0 1 1 1 2 2
0 1 2 2 2 3
0 1 2 2 3 3
0 1 2 3 3 3
0 1 2 3 4 4
Pseudo code
i=n,j=m
index=LCS[n][m] //We start from the bottom right corner and add the characters
to the LCS from the last
while(i>0 and j>0)
if(a[i]=b[j])
LCS_String[index]=a[i]
index=index-1
i=i-1
j=j-1
else
if(LCS[i][j-1]=LCS[i][j])
j=j-1
else
i=i-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
txt[] = " bellisalabelabelbelabela'";
pat[] = " belabela' ";
pg. 5

(b) Boyer-Moore
Input: txt[] = " bellisalabelabelbelabela'"
pat[] = "AABA"
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
(c) Knuth-Morris-Pratt
Input: txt[] = " belabela' "
pat[] = " bellisalabelabelbelabela'"
Output: Pattern found at index 10
8. Consider a directed graph G, where its adjucency list is:
Vertex 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.
Answer
Given an adjacency matrix we can check in constant time whether a given edge existsTo discover
whether there is an edge u
(c) Draw the transitive closure of graph G (show graphs GA;GB;GC;GD;GE;GF after each step of
theFloyd-Warshall algorithm).
Answer
Given an adjacency matrix we can check in constant time whether a given edge existsTo discover
whether there is an edge u.
pg. 6

Bibliography
Hyvärinen, A., & Oja, E. (2010). Independent component analysis: algorithms and applications. Neural
networks, 13(4-5), 411-430.
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2009). On spectral clustering: Analysis and an algorithm.
In Advances in neural information processing systems (pp. 849-856).
pg. 7