Sudipta

DSA Topic wise analysis

Runtime
Sudipta
Sudipta
 Sudipta

Divide and Conquer

 Sudipta

Heapsort
Sudipta
 Sudipta

Quicksort
 Sudipta

Sorting in linear time

Elementary data structure

Sudipta
Sudipta
 Sudipta

BST
Sudipta
Sudipta
 Sudipta

Dynamic programming
Sudipta
Sudipta
Sudipta
 Sudipta

Matrix multiplication এর সেম টাইপ একটা বিশাল প্রশ্ন আেছে। ওটা আর বিচ্ছি না।
Sudipta
 Sudipta

Greedy
Sudipta
Sudipta
 Sudipta

Elementary graph algorithm

Sudipta
 Sudipta

MST+djikstra

Disjoint set operations

 Sudipta

Priority Queue

Misc.
"

L-lrr -21CSE Date: 29/10/2023

BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY, DHAKA
L-l/T -2 B. Sc. Engineering Examinations 202 I -2022

Sub: CSE 105 (Data Structures and Algorithms I)

Full Marks: 210 Time: 3 Hours

The figures in the margin indicate full marks
USE SEPARATE SCRIPTS FOR EACH SECTION

SECTION-A
There are FOUR questions in this section. Answer any THREE.

1. (a) Derive the time complexity of the following code fragments: (4x4=16)

Code Fragment J Code Fral!menl 2

for (i = 0; i < n', ++i) { for (i = e; i < n', ++i) {
for (j = 8; j < i' , ++j) { for (j = 0; j < i*i; ++j) {
sum += i + j; sum += i + j;
} }
} }

Code Fraument 3 Code Fral'ment 4

for (i = 0; i < n*n; ++i) { sum = e;
for (t j = e; j < i' , ++j) { for (k=l; k<=n; k*=2) {
sum += i + j; for (j=l; j<=k; j++) {
} sum++;
} }
}

(b) In an array based implementation of a stack when the array space runs out, the
array capacity is increased. Now, analyze and explain the following scenarios through

an amortized analysis of the pushO function. (2X7=14)

(i) Increasing the Capacity of the Array by I
(ii) Doubling the Capacity of the Array

cg(ul

cgll/)

1/
1/
I/o
I/o

Figure I (i) Figure l(ii) Figure I (iii)

--_.--' -- --- _.,--.- &_- ~

Explain what do the three figures, i.e., Figure 1(i-iii) signify with respect to asymptotic
notations.
Contd P/2
:

=2=
CSE 105/CSE

2. (a) You are given the following numbers to insert into an empty Binary Search Tree
(BST): (5)
5,7,8,12, 15,27
Determine which insertion order below would yield the tree with the least height?
0) 15,5,27,8,7,12
(ii) 12,7, 15,27,5,8
(iii) 8,27,7,5, IS, 12
(iv) 7,5,12,8, 15,27
(b) A perfect balanced BST requires all interior nodes to contain two children and all
leaf nodes to be on the same level. A perfect balanced BST of h = ° would have n = I
node, h = I would have n = 3 nodes, h = 2 would have n = 7 nodes, and so on. Here, h
is tree height and n is the number of nodes in the tree. Providing appropriate
arguments, derive the worst-case running time, in terms of n, for successfully
searching for an element in a perfect balanced BST. (10)
(c) Present a recursive method count/nRange(root, low, high), without any helper
functions, to count, in a BST, all keys that are within a given range. Assume that keys
in the BST are unique, i.e., there are no duplicates. For example, suppose that the keys
in a BST are 4,7,10,14, IS, 17,20,30. Then, count/nRange(root, 8, 17) returns 4 and
count/nRange(root, 21, 29) returns 0. For your convenience a code snippet in C++ is
given below, but, you need not follow any particular programming language. (10)

public class BSTNode {

int key;
Value value;
BSTNode left;
BSTNode right;

}
II counts number of keys in BST that are in the range low to high, inclusive
II i.e. all keys k such that low (= k (= high
public static int countInRange(BSTNode root, int low, int high) {
II COMPLETE THIS METHOD
}

(d) Present an algorithm to delete a full node in a binary search tree. Explain how it
works with illustrative examples. (10)

3. (a) Suppose the numbers 0, 1,2, ..., 9 were pushed onto a stack in that order, but that
pops occurred at random points between the various pushes. Now you randomly wrote
the following two sequences, S I and S2 as example sequences in which the values in
the stack could have been popped: (5)
SI:3,2,6,5, 7,4,1,0,9,8
S2: 3,2,6,4,7,5,1,0,9,8
Noticing this, your genius little brother winked at you and said that only one of your
sequences is valid! Can you determine why?
Contd P/3
 =3=
CSE IOS/CSE
Contd .... for Q. NO.3

(b) Consider the following C++ fragment. A stack is being used to parse the matching
parentheses I brackets I braces- (,[, and {. Show the state of the stack at the end of this
fragment. (5)
1 #include <iostream>
2 using namespace std;
3
4 int main() {
5 const int M = 313;
6 int N = 11324;
7 int parent[N], height[N], depth[N];
8 int maxheights[lee];
9
113for ( int i = 13; i < lee; ++i ) {
11 maxheights[i] = 13;
12 }
13
14 double minmeandepth = 1e3ee;
15 double meandepths = e.,
16 double maxmeandepth = 8;
17
18 for ( int j = e; j < M; ++j ) {
19 for ( int i = 8; i < N; ++i ) {
213 parent[i] -1 ;
21 height[i] = e.,
22 )
23
24 for ( int i = 13; i < N - 1; ++i ) {
25 while ( true ) {
26 int p1 = rand() & (N 1);
27 int p2 = rand() & (N 1) ;
28
28 int 51 = p1;
313 int 52 = p2;
31
32 while ( parent[sl

(c) You are given access to the following functions of a list data structure: (25)
• init(n) 1* Initialize an array L[O .. n - 1] of length n for integers. Current
position 'points to' L[O]. All the functions below are applied on this array
which is not accessible directly. *1
• inser/(item) 1* Inserts an element at the current position and current position is
'incremented' (so if current position pointed to L[k] before the call, after the
call it points to L[k + 1]). Here, i1em is the element to be inserted. In case the
list is full, it returns ERR (a large negative constant). *1
• removeO 1* Removes the element at the current position and current position
is 'decremented' (so if current position pointed to L[k] before the call, after the
call it points to L[k - I]). In case the list is empty, it returns ERR (a large
negative constant). *1
• valueO I*Returns the value of the element at the current position. Current
position remains unchanged. In case the list is empty, it returns ERR (a large
negative constant). *1
Contd P/4
 =4=
CSE 105/CSE
Coutd .... for Q. No. 3(c)

• moveToStartO I*Sets the current position to L[OJ.*1

• moveToEndO I*Sets the current position to L[n -IJ*I
• nextO I*Increments the current position (so if current position pointed to L[kJ
before the call, after the call it points to L[ k + I]). If k = n - I, it returns ERR
(a large negative constant). *1
• prevO 1*Decrements the current position (so if current position pointed to L[kJ
before the call, after the call it points to L[k - I]). If k = n - I, it returns ERR
(a large negative constant). *1
Now you have to build one queue and one stack in one List data structure as defined
above. The queue should grow from the beginning of the list (i.e., first element of the
queue should be at L[O]) and the stack should grow from the end of the list (i.e., the
first element of the stack should be at L[ n - I]). You have no access to the code of the
above implementation and can only call these functions in your code. You need to
write appropriate codes (no specific programming language is required; pseudo code is
fine) for implementing the queue and stack simultaneously as described above. Please
explain your code by giving appropriate comments. In particular, you need to
implement the following four functions:
• push(item) 1* push a positive integer, item in the stack. If there is an error
(e.g., no more space available for growing the stack in the list, it should output
an appropriate error message and returns with -1. *1
• popO 1* pop an element from the stack. If there is an error, it should output an
appropriate error message and returns with -1. *1
• enqueu(item) 1* enqueue a positive integer, item in the queue. If there is an
error (e.g., no more space available for growing the queue in the list, it should
output an appropriate error message and returns with -1.*1
• dequeueO 1* dequeue an element from the queue. If there is an error, it should
output an appropriate error message and returns with -I. *1

4. (a) Compute the best alignments (i.e., alignments with the minimum edit distance) of
two DNA sequences, ATCGGT and ACCGT using dynamic programming. Use 2 as
the gap penalty, I as the mismatch penalty, and 0 as the penalty for a match. If there
are multiple optimal alignments, find all of them. You do not need to write the
algorithm, just show the dynamic programming (DP) table. Show the alignments and
mark the paths (which correspond to the alignments), in the DP table. (18)
(b) Given two strings, the longest common subsequence problem is to find the longest
subsequence present in both strings. A common subsequence is a sequence that
appears in both string in the same relative order, but not necessarily contiguous. For
example, for two strings SI = "ALGORITHM" and S2 = "LITHIUM", the longest
common subsequence is "LITHM". Present a dynamic programming algorithm to find
the length of the longest common subsequence of two strings. Derive a proof of
correctness of the algorithm and also derive its running time. (8+6+3=17)
Contd PIS
 =5=
CSE 10S/CSE

SECTION -B
There are FOUR questions in this section. Answer any THREE questions.

5. (a) Consider the following array (A) of integers. (20)

2345678910

A:

Verify whether the array is a max heap. Derive the complexity of your verification
algorithm. Justify whether the algorithm max_heapify (A, i) will establish the max
heap property of the array, if you apply algorithm with index i = 2. Analyze the time
complexity of max _heapify algorithm.
(b) Explain why topological sort algorithm cannot run on a directed graph that cycle(s).
Derive the component graph of the directed graph G represented by the adjacency
matrix give in Fig. for Q. No. S(b) and 6. Then find the topological sorting of the
vertices of the component graph. Show every steps. (15)

6. (a) Consider the adjacency matrix representation of a directed graph G given in Fig.
for Q. No. S(b) and 6. Draw the graph and find its adjacency list representation
considering the vertices in ascending order. Find the shortest path distance of every
vertex from vertex 1 using BFS. Show the queue status when the vertex 10 is just
enqueued. Prove that the distance of the most recent vertex (tail in the queue) is at
most one larger than the distance of the oldest vertex (head in the queue). (20)
(b) Classify the edges of the graph G represented by the adjacency matrix given in Fig.
for Q. No. S(b) and 6 after you run DFS on the graph considering the vertices in
ascending order. Prove that an edge (u, v) is a tree edge. (15)
if u.d < v.d < vI < uf.
Notations bear their usual meaning.

7. (a) Given a set U = {x" x" ... , x,,} of n integers and an integer k (k < n), gIve an
optimal greedy algorithm to find a subset S of size k in U such that the summation of
the numbers in S is maximum (over all the subsets of size k in U). Prove the
correctness of your algorithm, and analyze the running time. (15)
(b) Given a sequence of n numbers al .... , an, which we assume are all distinct, we
define an inversion to be a pair i < j such that a > aj• Present an O(n log n) divide-
j

and-conquer algorithm to count the number of inversions between two orderings. One
might feel that this measure of inversion is too sensitive and may want to change it.
Let's call a pair a modified-inversion if i < j and a > 20j. What modifications do you
j

need to make in the divide-and-conquer algorithm (for counting inversion) to count the
number of modified-inversions? (20)
Contd P/6
 =6=
CSE 105/CSE

8. (a) Given n points (x" y,), (x" y,)"'" (xn, Yn) in the plane, give an efficient divide-
and-conquer algorithm to find the pair of points that is closest together. Prove the

correctness and analyze the running time of your algorithm. (18)

(b) Calculate the number of swap operations (data interchanges) required if you apply

Build_Max_Heap algorithm on the array A = {S,3, 17, 10, 84, 19, 6, 22, 9}. Justify

whether the max heap you produced can be used as a priority queue. Show that
Heap_Extract_Max algorithm is essentially a part of Heapsort algorithm. Derive and
compare the time complexities of these two algorithms. (Heapsort and Heap_Extract_ (17)
Max).

1 2 3 4 5 6 7 8 9 10
1 0 0 1 0 0 0 1 0 1 0

2 0 0 0 0 1 0 0 0 0 0

3 0 0 0 0 0 1 0 0 0 0

4 1 0 0 0 0 0 0 1 0 0

5 0 0 0 0 0 0 0 0 1 0

6 0 0 0 0 0 0 1 0 0 0

7 0 0 1 0 0 0 0 0 0 0

8 0 0 0 0 0 0 0 0 0 1
,
9 0 • 1 0 1 0 0 0 0 0 1

10 0 0 0 0 0 0 0 1 0 0

Fig. for Q. No. S(b) and 6