L-2/T-lICSE Date: 17/12/2012

BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY, DHAKA

L-2/T-l B. Sc. Engineering Examinations 2011-2012 '

Sub: CSE 203 (Data Structures)

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.

3
1. (a) Prove that 0(n ) O(n) = O(n \ (5)
(b) Write the main three reasons why we usually concentrate on finding the worst-case
running time of an algorithm. (5)
(c) Write an algorithm for DFS traversal of a given graph. Analyze the time-complexity
of the algorithm. (10+5=15)
(d) Write the sequences of the vertices if you explore the following graph G using BFS
and DFS. Classify the edges ofG for your DFS traversal. (4+6=10)

Figure for Question l(d)

2. (a) What is the divide-and-conquer technique? (5)

(b) Write the merge sort algorithm. Analyze the time-complexity of the algorithm. (10+5=15)
(c) Write the recurrence relation of the merge sort algorithm. Draw the recursion tree for
,the recurrence relation of the merge sort algorithm. (7)
(d) Sort the array 15~ 13, 9, 5, 12,8, 7, 4, 10,6,2, 1,26,23 using heap sort showing the
values in the right of the nodes. (8)

3. (a) Write the quick sort algorithm. Simulate the quick sort algorithm on the array of ,
Question 2(d) showing in detail how partition routine works. (8~7=15)
(b) What is a priority queue? Write three applications of a priority queue. (2+3=5)
(c) What are the main operations of a priority queue? Explain how one can implement
these operations using a heap. (15)
eontd P/2 L-.-"

, "
 •.
=2=

CSE 203

4. (a) Explain the advantages and disadvantages of arrays and linked-lists. (5)
(b) What is a tree? Write an algorithm for finding the height of a tree. Analyze the time-

complexity of the algorithm. (2+5+5=12)

(c) .Let T be a binary tree with height h. Then prove that the number of nodes in T is at

least 2h + 1 and at most 2 +

h 1
- 1. (12)

(d) Write pseudocodes for Insert and Delete operations of a 'circular queue. (6)

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

5. (a) Explain the insertion and deletion operations in a binary search tree with illustrative

examples. (14)
(b) Sort the following data set using counting sort showing every step of the algorithm. (11)
A= {6, 0, 2, 0,1,3,4,6,1,3, 2}
(c) "An important property of counting sort is that it is stable" - explain. (4)

(d) Analyze the average case running time for bucket sort. (6)

6. (a) Draw the skip-list for the following table. that shows the keys and consecutive

numbers of the heads found in toss while inserting the keys in, a probabilistic skip-list. (7+8~15)
key 3 6 7 9 12 17 19 21 25 26

No. of consecutive heads 1 4 1 2 1 2 1 1 3 1

Do the following operations on the skip-list and show the procedures.

(i) Search 21
(ii) Insert 22 with 3 consecutive heads

(iii) Delete 19
(iv) Search 18
(b) Show that the expected running time of searching in a probabilistic skip-list is

o (log n). (6)

(c) Consider inserting the keys 18, 41, 22, 44, 59, 32, 31, 73 into a hash table of length

m = 13 using double hashing with hl(k) = k mod 13,

h2(k) = 8 - (k mod 8). .

Draw the hash table. (10)

(d) What are the properties ofa good hash function? (4)

Contd P/3
 =3=

~SE 317
Contd ... Q. No.6

(c) Solve the following problem using Third-Order RK method over the interval from x =

o to x = 1 with a step size ofh = 0.5 where yeO) = 1. (11)

3
y' = x y - 1.5y
Use the following version of Third-Order RK method.

Yi+1= Yi+ h (k1 + 4k2 + k3)/6

where,

kl = f(Xi, Yi)
k2 = f(Xi + h/2, Yi + k1h/2)

k3 = f(xj+ h, Yi- k1h + 2k2h)

7. (a) Derive the integral. of the following tabular data using best combination ofl

Trapezoidal rule and Simpson's rule. (10)

I
j
o

(b) Finhe function f(x;a, b) = a (1- e-

bx
) to the data: ji (25)

x 0.25 0.75. 1.25 1.75 2.25.

Y 0.28. 0.57 0.68 0.74 0.79

Use initial guesses of a = 1.0 and b = 1.0 for the parameters.

8
8. (a) Use Romberg integration with an accuracy of 0(h ) to integrate the following

function from x = 0 to X = 0.8. (15)

3 2
f(x) = 7x + 4x + 5x + 3

(b)Integrate y' = 4eO.8x - O.Sy from x = 0 to x = 1 with a step size of 0.5 using the

following methods: (20)

(i) Heun's method
(ii) Midpoint method
Given, yeO) = 2.

...•
,\
L-2/T-l/CSE Date: 12/05/2014.
BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY, DHAKA
L-2/T -1 B. Sc. Engineering Examinations 2012-2013

Sub: CSE 203 (Data Structures)

Full Marks: 210 Time: 3 Hours
USE SEPARATE SCRIPTS FOR EACH SECTION
The figures in the margin indicate full marks.

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

1. (a) What is a data structure? Write the properties of a linear data structure. (1+4=5)
(b) Prove that 5n3 + 3n = O(n4), but 5n3 + 3n * O(n2
). (5+5=10)
(c) Let a : array[ZI"uI,l2"u2,l3"U3] be a 3-dimensional array. Assume that b and c are
the base address and component length of the array a, respectively. Then write the Array
Mapping Function to calculate addr(a[i,j, k]). (10)
(d) Write the advantages and disadvantages of arrays and linked-lists. (10)

2. (a) Write the differences between a standard queue and a priority queue. Write the
property of a Max-Heap. Write an algorithm for building a Max-Heap. Analyze the
time-complexity of the algorithm. (3+3+7+7=20)
(b) Explain the divide-and-conquer technique? What is the function of the pivot element
in the quick sort algorithm? (3+2-5)
(c) Write two functions for the insertion and deletion operations in a circular linked list, (5+5=10)

3. (a) Write an algorithm for DFS traversal of a given graph. Analyze the time-complexity
of the algorithm. (8+7=15)
(b) Consider a graph G as shown in Figure for Question 3(b). Then (6+4+4+6=20)
(i) Write the adjacency matrix and adjacency list of the graph G.
....
(ii) Draw the BFS forest of the graph G by assuming b as the starting vertex.
(iii) Write the sequence of vertices if you explore the graph G starting from vertex b
inDFS.
(iv) Write the tree edges, back edges, forward edges, and cross edges.

Figure for Question 3(b)

Contd P/2
 ..
:

=2=

CSE203

4. (a) What is a tree? Write a linear-time algorithm for finding the height of a tree. Analyze

the time-complexity of the algorithm. (1+4+4=9)

(b) Let T be a proper binary tree with height h. Then, prove that the number of internal

nodes in T is at least h and at most 2h - 1. (4+4=8)

(c) Construct the binary tree whose inorder and postorder traversals '.lfe given as: (10)
Inorder : iJdjgeabkhme
Postorder: ijgdJkmhebae
(d) Draw the Linked Structure for the binary tree of Question 4(c). (8)

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

5. (a) Sort the following dataset using "quicksort" in descending order when pivot element
is the first element. (12)
D = {6, 0, 2, 0, 1, 3, 6, I}
(show the steps)
(b) If you use "merge-sort", what will be the merge-tree for the data set mentioned in

Q. Sea)? Show that merge 'Sort runs in time e (nlgn) in the wrost-case. (6+4=10)
(c) Analyze the average case running time, for "bucket sort". (8)
(d) Write the "counting sort" steps for the dataset of Q. Sea). (5)

.6. (a) Write pseudo-code for finding a key, inserting a key and deleting a key in a hash

table using quadratic probing. Explain your method with an example. (12)
(b) Prove that in a hash table in which collisions are resolved by "chaining", a successful
search takes average case time B(l + a), under the assumption of uniform hashing,

where a is the load factor. (10)

(c) Insert key in a hashtable of size 13 using double hashing with (13)
hI (k) == k mod hash-table size

and ~(k)=8-(kmat8),
where k is the key, hI and h2 are hash functions. Key insertion order is-
18,41,22,44,59,32,31,73.

Contd P/3
• ••

=3=

CSE203

7. (a) (4+4+7=15)

1fT! has height h-I, what will be the heights ofTz, TJ, and T4? What will happen if you
delete an element from T!? Discuss. different cases (all possible) for deletion operation
in an "AVL tree".

(b) Design an AVL tree with keys 5, 12,3, -2, -5, -'3, I. Show the steps. (15)
(c) What is the height for AVL tree? (Assume that the number ofintemal nodes of the

AVL tree is n.) (5)

8. (a) Write down the properties of a "red-black tree". With an example show insertion and

deletion operations and their, costs of a "red-black" tree. (5+15 20)

(b) Build "2-3-4 tree" with the keys 12,5,6, 10, 15,8, 13, 17, 11, 14,4. Delete elements

in the following sequence: 4, 12, 13. (show the steps). (15)

L-2rr~1/CSE Date: 07/12/2014
BANGLADESH UNIVERSITY OF ENOINEERING AND TECHNOLOGY, DHAKA
L-2fT-l B. Sc. Engineering Examinations 2013-2014
Sub; CSE 203 (Data Structures)
Full Marks: 210_ Time: 3 Hours
USE SEPARATE SCRIPTS FOR EACH SECTION
The figures in the margin indicate full marks.
------------ -------- -_ .._---------- ----_._---- ----
SECTION -A
There are FOUR questions in this section. Answer any THREE.

1. (a) Write a sorting algorithm thai can always sort n elements in O(n log n) time. Analyze
the best-case and worst-case time complexity of the algorithm. (7+8=15)
(b) Prove that any comparison sort algorithm requires Q(n log n) comparisons in the

worst case. (8)

(c) Write the counting sort algorithm. Prove that the algorithm runs in linear time;
Explain why oounting sort is smble. (3x4==12)

2. (a) Write algorithms for the search, insertion and deletion operations of skip lists. Show
that the expected search, insertion and deletion time is o(log n) in a skip list with n
entries. Also show that the expected space used is O(n). (18)
(b) Draw the l1-item hash table (hat results from using the hash function h(i)= (2i + 5)
mod II, to hash the keys 12, 44. 13, 88, 23, 94, II, 39, 20, 16, and 5, assuming
collisions are handled by double hashing using a secondary hash function
h'(k)=7-(kmod7). (12)
(c) Compare linked Jists and skip lists. (5)

3. (a) What is an AVL tree? Show that the height of an AVL tree T storing n items is
o(logn). (10)
(b) Explain with examples the single rotation and double rotation operations on AVL
",0- (10)
(c) Write the differences between a binary-search tree and a min-heap. (4+6+5=15)
Write two procedures for rmding the tree-successor and the tree-predecessor in a binary-
search tree.
For the set of {ll, 4, 25, 10, 36, 17,21} of keys. draw a binary search tree of height 3.

4. (a) Write
, the properties of a red-black tree. Show the red-black trees that result after
succl:ssive1yinserting the keys 51, 46, 41, 22, 29,18 into an initially empty red-black
tree. (15)
(b) Explain the divide-and-conqucr tcchnique. Write the quick sort algoritlun, and
analyze the time-complexity of the algorithm. (15)
(c) Write the properties of a B-tree. (5)
Contd PI2
 "'2=
CSE 203/CSE

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

5. (a) What is a data structure? When is a data structure called a linear data structure?
Write 4 (four) properties ofa linear data structure. (1.5+1.5+4=7)
(b) Let a: array[I] ...uj.I •.. ,uJ be a'2D integer array. Asswne b is the base address of

the array a. Then write the Array Mapping Function to calculate address(a Ii, jJ) in (5+5='10)

(i) Column-major order

(ii) Row-major order
(c) Given a doubly linked list and an integer n, write a function deleteLastNElementsQ

that deletes last n nodes from the given linked list. (8)

(d) What is a proper binary tree? Construct the proper binary tree whose inorder and

postorder traversals are given as: (2+8=10)

loorder : BUETCSEl2
Postorder : BEUCTES21

6. (a) How do you implement a Queue using a Stack? What are the running time ';If
enqueue and dequeue operations of such implementation? (8+2=10)
(b) Which type of traversal will traverse the binary tree in figure for Question 6(b) as:
BUETCSE12? Write an algoritlun for such traversal of a binary tree using a Stack or
Queue. (2+10=12)
B

T s
1

(c) Give a brief description of (1.5+ 1.5+1.5+2.5=7)

(i) Graph
(ii) Forest
(iii) Tree
(iv) Spanning subgraph
(d) Give a comparison of adjacency matrix and adjacency list representation of a graph. (6)

Contd ,.. P/3

,
=3=
CSE203/CSE

7. (a) Give 2 (two) real life applications each for (2+2+2=6)

(i) Stack
(ii) Queue
(iii) Priority Queue
(b) Write pseudocodes for enqueue and dequeue operations for the IlITIIY

implementations of a circular queue. (7)

(e) Assume an object which has lWO elements {key, element}. An array of such object is

given in fib'U1'efor Question 7(0). Then (8+8+6=22)

(i) Coovert the array into Max-heap.
(H) Insert (36, B) in the resultant Max-heat of 7(0)(i)
(iii) Show each step ofthc Heap sort over the resultant Max-heap of7(c)(il).

26; 19, 20, 24, 18, 17, 7, 8, 9, 1O,

14, 11, 13, 12,
S E W P 0 L A S H 1
U E T C

8. (a) Givea comparisonof arrayand linkedlist. (6)

(b) Draw a binary tree whose preorder and inorder traversals both yield BUETCSE12. (7)

(c) Consider a graph G as shown in figure for Question 8(c). Then (6+6+4+6=22)
(1) Write the adjacency matrix and adjacency list of the Gmph G.
(ii) Dmw the BFS forest of the graph G by assuming B as the starting vertex.
(iii) Write the sequences of vertices if you explore the graph G starting from vertex
Bin DFS.
(iv) Write the tree edges, heck edges, forward edges and cross edges.

c (0
I
CD
L-2/T-1/CSE Date: 27/01/2016
BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY, DHAKA
L-2/T-l B. Sc. Engineering Examinations 2014-2015

Sub: CSE 203 (Data Structures)

Full Marks: 210 Time: 3 Hours

USE SEP ARA TE SCRIPTS FOR EACH SECTION
The figures in the margin indicate full marks.

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

1. (a) Prove that any comparison sort algorithm requires n(n log n) comparisons in the

worst case. (10)

(b) Write a linear-time Bucket Sort algorithm. Prove that time complexity of the

algorithm is linear. (10)

(c) Write the Quick Sort algorithm. Analyze the best-case and worst-case time

complexity of the algorithm. (15)

2. (a) Write an algorithm for building a heap. Show that an n-e1ement heap can be built

using O(n) time. (10)

(b) What are the main operations of a priority queue? How could we implement these

operations using a heap? (10)

(c) Compare linked lists and skip lists. Show that the expected space used by a skip list

with n entries is O(n). (15)

Draw the skip-list for the following table that shows the keys and consecutive numbers
of the heads found in toss while inserting the keys in the skip-list.

Key 15 40 35 28 21 65 84 79 50

No. of consecutive heads 1 4 1 0 3 2 2 3 1

3. (a) Explain, with examples, the single rotation and double rotation operations on AVL

trees. (10)
(b) What is a Multiway Search tree? How do we search a key in a Multiway Search

tree? (10)
(c) What makes a good hash function? Explain the three commonly used techniques to

compute the probe sequences required for open addressing in a hash table. (15)

4. (a) Draw the binary search tree that results after successively inserting the keys 15, 8,
24, 12, 40, 18, 20, 23 into an initially empty binary search tree. Then, by using

necessary rotations, redraw the binary search tree so that it becomes an AVL tree. (10)
Contd P/2
•

=2=

CSE 203
Contd ... Q. NO.4

(b) Write the properties of a red-black tree. Show that the height of a red-black tree T

storing n items is O(log n) . (10)

(c) Explain, with examples, the four cases that may arise for deleting a node from a red-

black tree. (15)

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

5. (a) Suppose that you are given the following doubly linked list implementation that uses

head and tail pointers: (15)

I
struct listNode
{
int item; //will store data
struct listNode *next //will keep address of next node
struct listNode *prev ; //will keep address of previous'node
} ;
struct listNode * head //points to the ,first node of the list
struct listNode * tail //points to the last node of the'list

Implement the function "void delete(int N)" that deletes all Mth nodes of the list such
that M mod N = 0 where N >0. F?r example if N = 3, the function should delete 3rd
node, 6th node, 9th node, and so on. The node pointed by head is the 151 node. Your
implementation should be as efficient as possible.
(b) Compare the worst case run times of ArrayList and LinkedList (doubly with heat and

tail pointers) for the following operations: (4x3=12)

(i) Insert an item at the Nth position of the list (need to preserve order of items)
(ii) Remove the first item of the list (need to preserve order of item)
(iii) Remove the Nth item of the list (need to preserve order of item)
(iv) Get (without removing) the Nth iteni of the list

(c) Give two advantages and disadvantages of using array based lists over linked lists. (8)

6. (a) Suppose we create a binary search tree by inserting the following values in the given

order: 50,10, 13,45,55, 110,5,31,64, and 47. Answer the following questions: (5+4+4+6=19)
(i) Draw the binary search tree.
(ii) Show the output values if we visit the tree using pre-order traversal technique.
(iii) Show the output values if we visit the tree using post-order traversal teclmicjue.
(iv) Show the resulting trees after we delete 47, 110, and 50. (Each deletion is
applied on the original tr~e.)
Contd P/3

o
•

=3=

CSE 203
Contd ... Q. No.6

(b) Suppose that we are given the following definition of a rooted binary tree (not

binary search tree): (12)

--_. __ ._----------------'-~------------
;tr"ct treeNode ,,,' ." ~

int item; ,I /stores the value

" ~~.'struct t~~eNode * left; //P9ints to left~hild
, I
struct tree~ode* right j //points to right child
}
., st~uct treeNode * root j / /global. variable to store tree root node

Implement the following function clone (must be recursive) that makes a copy of a
binary tree (keeping the original tree intact). The function will be called using the
original root pointer as input argument. The function should return the root node of the

new copy. For example calling x = clone(root) will return the new root (of the tree

copy) into variable x.

i struct treeNode * clone(struct treeNode * node);

(c) Give two reasons why we should use restrictive data structures (e.g., Stack and

Queue) instead of general purpose data structures. (e.g., List) (4)

7. (a) Suppose you are given the following definition of a singly linked list having head

and tail pointers; (15)

struct listNode
{
int,item; //will be 'used to store 'value
struct listNode *next ; //will keep address of next node
} ;
struct listNode * head //points to first node of the list
struct listNode * tail //points to last node of the list

Implement a stack data structure using the above linked list definition. You need to
implement only the following functions: push, pop, and size. The size function returns
the current size (number of items) of the stack. You cannot use any other global or static
variable in your implementation except head and tail pointers given above. Your
implementations should be as efficient as possible.
(b) Suppose that we double the memory of an array based list every time we see that the
memory is full during insertion of a new item. Show that the average time required per
insertion to copy the existing items from the old memory to the new memory is

constant. (12)
Contd P/4
•

=4=

CSE 203
Contd ... Q. No.7

(c) Give the idea of a data structure that can be used to implement a general tree where
nodes can have more than two children. Re-draw the binary search tree shown in Fig.

for Q. 7(c) using your proposed data structure .. (8)

5

Ji
(;.,.-,'
•

~ F_ig.for Q~(:) _
8. (a) Consider the directed graph shown in Fig. for Q. 8(a). Answer the following

questions: (6+6=12)
(i) Perform depth first search on the graph starting from vertex A. Choose the
smallest (in alphabetical order) vertex when there is a choice. Find the
discovery time and finishing time of each vertex.
(ii) Perform breadth first search on the graph starting from vertex A. Choose the
smallest (in alphabetical order) vertex when there is a choice. Find the distance
and parent of each vertex.

J
Fig. for Q. 8(a)
(b) For each of the following operations in an undirected graph, find the worst case
running times in Big-O notation if we use an adjacency matrix; and if we use an

adjacency list: (4+4+6=14)

(i) Determine whether a given vertex is connected to no other vertex.
(ii) Determine whether the graph has a vertex that is connected to no other vertex.
(iii) Determine whether a given vertex is connected to every other vertex. Give the
idea (in two to three sentences) of your algorithm for adjacency list.
(c) Recall that an undirected graph is "connected" if there is a path from any vertex to
any other vertex. If an undirected graph is not connected, it has multiple cOlmected
components. A "'connected component" consists of all the vertices reachable from a
given vertex, and the edges incident on those vertices. Suggest an algorithm based on .
DFS that counts the number of connected components in a graph. Give only the idea or

skeleton ofthe algorithm. (9)

"

L-2/T-l/CSE Date: 27/0712016

BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY, DHAKA
L-2/T-l B. Sc. Engineering Examinations 2015-2016

Sub: CSE 203 (Data Structures)

Full Marks: 210 Time: 3 Hours

USE SEP ARA TE SCRIPTS FOR EACH SECTION
The figures in the margin indicate full marks.

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

1. (a) What is a stable sorting? Write a sorting algorithm that is stable. Analyze the time-

complexity of the algorithm. (10)

(b) Prove that 15n3 + 13n2 + lIn = O(n4 ), but 15n3 + 13n2 + lIn :;t O(n2 ). (10)
(c) Explain 'Chaining' and 'Open Addressing' methods for solving the problem of
collisions in a hash table. Explain the three commonly used techniques to compute the

probe sequences required for open addressing in a hash table. (15)

2. (a) Write the Insertion. Sort algorithm. Analyze the worst case and best case time-

complexities of the algorithm. (10)

(b) Write a function to find the largest element in a min binary heap. (10)
Assume that the array representing a min binary heap contains the values 2, 8, 3, 10,
16,7,18, 13, 15. Show the contents of the array after deleting the minimum element.
(c) What is an In-place sorting? Write an In-place sorting algorithm. Analyze the worst

case and best case time-complexities of the algorithm. (15)

3. (a) What is an AVL tree? Draw the AVL tree that results after successively inserting

the keys 11,4, 15,25,36,47,61,53,75 into an initially empty AVL tree. (10)
(b) Write two procedures for finding the successor element and the predecessor

element in a binary-search tree. (10)

(c) Show that the height of a red-black tree T storing n items is O(logn). (15)

Explain, with examples, the three cases that may arise for inserting a node in a red-
black tree.

4. (a) Show that the expected space used by a skip list with n entries is O(n) and the

expected height of a skip list is O(log n) . (10)

(b) Prove that a min binary heap can be built in linear-time. (10)
(c) By writing a procedure, explain the three cases, that may arise for deleting a node

from a binary search tree. (15)

Contd P/2
 =2=
CSE 203

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

5. (a) Define graph, path, cycle, sub graph with examples. (10)

Figure 0.5 (b)

(b) Show the adjacency matrix and adjacency list for the graph in Figure Q. 5(b).
Calculate the number of bytes required in both representations. Assume that the storage

requirement of a pointer and an integer is 4 bytes. (5+5+5=15)

(c) Your friend has employed two different traversal algorithms, namely, Algo I and
Algo II on a graph. Then he has shown the output of his two traversal algorithms in
Figure Q. 5(c)-I and Figure Q. 5(c)-II. In both cases, the traversal starts at the node
shown by the block right arrow. In the output, nodes are labeled with the order they are
traversed. Identify the traversal algorithm for Figure Q. 5(c)-I and Figure Q. 5(c)-II and

justify your answer. (10)

-----------_.---- -~--------

Figure 0.5 (c)-J Figure 0.5 (cHI

6. (a) Your teacher has given you the following assignment: you will be given an input
string x and you need to check whether x is of the fonn w#wr, where w is a nonempty
string, wI' is the reverse of w. Suggest a data structure for this assignment and show

how it can be used efficiently to solve this assignment. (15)

Contd P12
•

=3=
CSE 203
Contd ... Q. No.6

(b) Suppose you have implemented a pointer based single linked list where each node
contains an integer called key and appropriate pointers. Now, your friend asked your
help to implement an efficient algorithm using your data structure with the following

input and output: (15)

input: k, n
Output: Return the key of the n-th node before the one containing k as the key value.
Suggest a solution. You may assume that each node will have different values for key.
(c) Your group has to implement an array based stack. You have proposed that the
beginning of the array would be the top of the stack. Your friend is claiming that this is

inefficient. Do you agree with your friend? Justify your answer. (5)

7. (a) Suppose the tree in Figure 7.a is an unordered tree, i.e., the order in which the
children appear is not relevant. Now determine whether each of the following breadth-

first traversals is valid or not. You need to justify your answer: (16)
GFBKECAINJDHMLO
GFBKECAINJDHMLO
GKFBIJNEACOMLHD
GFBKECAINJOMLHD

Figure 7.a

(b) Discuss the Drifting Queue Problem with the help of an illustrative example.
Propose a solution to the problem. Will there be any problem in recognizing when the

queue is empty or full in your solution? If yes, then solve the problem as well. (5+5+5+4=19)

8. (a) Suppose we are implementing a list of integers. Deduce the condition in which an
array based implementation would be better in space utilization than a linked based

implementation. (10)
Contd P/4
 =4=
CSE 203
Contd ... Q. NO.8

(b) Suppose Figure 8.b-I gives a snapshot of the memory at one point. Now you are
running your program for a linked list based list implementation. In your
implementation each node has two variables: an integer key and a pointer ptr. Now the
current situation of the list is illustrated in Figure 8.b-II. You have further implemented
concept of freelist so as to minimize the number of calls to 'new' and 'delete'. The first,
second, third and fourth(i.e., last) node correspond to address 1, 2, 3 and 4 in the
memory respectively. Suppose at this point a delete operation is done for the node
containing 29 followed by two append operations of two nodes containing values 1111

and 2222 respectively. (5+10+10=25)

Address Values at Memory Location

0 -3 I
I 12
2 14
3 29
4 100
.

5 112
6 4
... ...
Figure 8.b-I

1
12 _~1291t-- __ ~1
100

Figure 8.b-II

(i) Draw the updated list after each operation.

(ii) Provide the value of ptr variable for each node in Figure 8.b-II before and
after the delete operation. If a node remains in the memory after your
deletion operation, you would need to provide the value of the ptr variable of
that node as well.
(iii) Provide the updated values of each memory cell after the two operations
(delete and append) are complete.
You can assume that the next cal of C++ 'new' operator will return the address 5.
 L-2/T-lICSE Date: 16/08/2017
BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY, DHAKA
L-2/T-1 B. Sc. Engineering Examinations 2016-2017

Sub: CSE 203 (Data Structures)

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.
J
1. (a) Write a function to find the smallest element in a max binary heap. (5)
(b) What is a tree? Write a linear-time algorithm for finding the height of a tree. ~rJ
. '<tt
Analyze the time-complexity of the algorithm . (10)
.(c) Compare adjacency matrix and adjacency lists representations of a graph. (10)
(d) Consider the weighted graph G as shown in Figure 1. Then draw the adjacency lists
of the weighted graph G. Whenever there is a choice of vertices to explore, always

pick the one that is alphabetically first. (10)

!
I
I

I
I
I

.Figure I: A weighted graph G.

2. (a) Write the differences between a standard queue and a priority queue. Write two
functions that implement the Decrease-Key and Increase-Key operations in a Max-

heap. (10)
(b) Write an algorithm that sorts the keys of a binary search tree. (10)
Draw the binary search tree that results after successively inserting the keys 43, 34,48,
59,65, 73, 88, 81, 92, 79 into an initially empty binary search tree. Also draw a binary
search tree of height three using these keys.
(c) Explain the three cases of the deletion operation in a binary search tree with

illustrative examples. (15)

Contd P/2
 =2=
CSE 203

3. (a) Given a single linked-list and two integers m and k. Write a function that first finds

the node with item value m and then deletes next k nodes from the linked list. (10)
(b) Write two procedures for finding the successor element and the predecessor

element ina binary-search tree. (10)

(c)Write push and pop functions of two stacks that are implemented in a single array.
Write the pre order, inorder and postorder traversal sequences of the binary tree whose
Euler tour traversal sequence is a e h i h e a c b f b g bed j de a. Also draw the binary

tree. (15)

4. (a) Write enqueue and dequeue functions of a FIFO queue that is implemented by a

single linked list. (10)

(b) Prove that a min binary heap can be built in linear-time. (10)
(c) What is an in-place sorting? Write an in-place sorting algorithm. Analyze the worst

case and the best case time-complexities of the algorithm. (15)

SECTION-B
There are NINE questions in this section. Answer any SEVEN.

5. (a) Define big O-notation, Q-notation and 8-notation. (6+9)

(b) Arrange the following functions in ascending order of growth rate. That is, if
functionf(n) pr~cedes function g(n) in your list, thenf(n) should be O(g(n)). Provide
justifications.

/'- rn,n f 2 -log

J I - '\j - 2'
n f 3 -- 2...jiOg;n , J/'4 -- n.,, J/'5 -- nil , J/'6 -- 211

6. Suppose you are choosing among the following three (possibly hypothetical)

algorithms for multiplying two n x n matrices: (15)

Algorithm A (Strassen's algorithm) solves the problem by dividing each n x n
matrix into four n I 2 x n I 2 matrices, makes seven recursive calls to compute
intermediate results and then combines them in 8(n2) time to get the result.
Algorithm B solves the problem by dividing each n x n matrix into twelve
n I 3 x n I 3 matrices, makes nine recursive calls to compute intermediate results

and then combines them in 8(n2) time to get the result.

Algorithm C solves the problem by first multiplying two (n-l) x (n-l) matrices,
then combining the result with two vectors of size n in time 8(n2).
Determine asymptotic running times of the three algorithms (use the master theorem if
applicable). Which one would you choose?
Contd P/3
 =3=
CSE 203

7. (a) Prove that any comparison based sorting algorithm requires n(n log n) comparisons

in the worst case. (7+8)

(b) Describe a sorting algorithm that achieves the above lower bound I.e. runs III

O(nlogn) in the worst case.

8. Design linear time algorithms for the following. Briefly describe the ideas (pseudo-

code is not needed). (7+8)

(a) Given an undirected graph G and a particular edge (u v) in it, determine whether
G has a cycle containing (u v).
(b) Given an undirected and unweighted graph G, a particular edge (u, v) and two
vertices sand t, determine whether there is a shortest path from s to t containing
the edge (u, v).

9. Run depth first search (DFS) on the following graph starting from vertex A and show
discovery and finishing times for each vertex as well as edge types. Decompose the

graph into strongly connected components (SCCs). (15)

I,
,

10. You are given a set of points byP = (JJt, ""Pllj, where Pi has coordinates (Xi,Yi) and for
two points Pi, PjEP, we use d(Pi, Pi) to denote the standard Euclidean distance between
them. Give an algorithm to find a pair of points Ph Pi that minimizes d(Pi, p) which

runs in O(nlogn) time. Justify the running time of your algorithm. (15)

11. (a) Huffman's algorithm is used to obtain an encoding of alphabet {a, b, c} with
frequencies fa, fi, and fe. In each of the following cases, either give an example of
frequencies ifa, fi, fe) that would yield the specified code, or explain why the code

cannot possibly be obtained (no matter what the frequencies are).

(i) Code: {a, 10,11}

(ii) Code: {a, 1, OO}
(iii) Code: {la, 01, OO}.
Contd P/4
•

=4=
CSE 203
Contd ... Q. No. 11

(b) Following is a set of characters and corresponding frequencies:

Character Frequency
A 24
B 12 -& .
.it
C 10
D 8
E 9
F 37

.~"-
Construct Huffman codes for the characters using the greedy algorithm. /~'
'". . ..

12. Suppose you are given n white and n black dots, lying on a line. The dots are equally
spaced but they may appear in any order of black and white (black and white may be
interleaved). Design a greedy algorithm to connect each black dot with a (different)
white dot so that the total length of wires used to connect the dots is minimal. The
length of wire used to connect two dots is equal to their distance along the line. Prove

that your algorithm is optimal. (15)

• •
1 2 3
0
4 5
• 6
0
7 8
0 0
•
For example, an optimal solution to solve the above example is (l,3), (2,5), (4,6), (7,8)
with total wire length = 2+3+2+ 1=8.

13. Recall the Weighted Interval Scheduling Problem from class. You are given n intervals
with the starting and finishing times of the i-th interval given by Si and fi respectively
and it is associated with a value Vi. A subset of the intervals is compatible if no two of
.them overlap in time. The goal is to find a compatible subset of intervals; S to

maximize the sum of the values of the selected intervals, LieS VI . Give a dynamic

programming algorithm to solve the problem. Your algorithm (including any pre-

processing needed) should run in O(nlogn) time. (15)

L-2ff-1/CSE Date: 09/11/2019
BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY, DHAKA
L-2/T- I B. Sc. Engineering Examinations 2018-2019
Sub: CSE 203 (Data Structured and Algorithms I)
Full Marks: 210 Time: 3 Hours
The figures in the margin indieate full marks.
USE SEPARATE SCRIPTS FOR EACH SECTION
SECTlON-A

There are FOUR questions in this section. Answer any THREE.

I. (a) Dream coins are used by the people of the Dreamland. Assume that only the following
coins are available at this land: SI, S7, SI I, and S15. (10)
(i) Write an example of an amount where the greedy strategy for the Coin- Change
. problem does not provide an optimal solution. You must mention the optimal solution,
and the greedy solution.
(ii) By using Dynamic Programming, find the minimum number of eoins that add up to a
given amount of money of S20.
(b) Write a divide-and-conquer algorithm that finds the Maximum and the Minimum of
an array of n distinct elements. First write the reeurrence relation for the running time
T(n) of the algorithm, and then solve it by Recursion Tree Method. (10)
(c) Consider the following instance of the 0/1 knapsack problem. Solve this instance
using dynamic programming. Assume that the knapsack capaeity is 7. You have to show
the dynamie programming table and find all solutions using this table. (15)

Item Weight Value

I 50
2 3 60
3 5 100
4 2 70
5 2 80

2. (a) Consider a divide-and-conquer algorithm as follows: if the problem size is less than or
equal to 5, then it solves the problem at constant time. Otherwise, it divides the problem

of size n into 4 subproblems, each with a size of n/3. This division takes 0(;;; log n)
time. The algorithm then solves the subproblems recursively, and merges their solutions
at time O(n). Write the recurrence relation for the running time T(n) of this algorithm. (10)
Solve the following recurrences by using the Master theorem.

(i) T(n) =9T(n/3) + 5 n;;; + 810g n

(ii) T(n) = 3T(n/4) + 3n2 + 4n + 5

(iii) T(n) = 4T(n/2) + 5n2 + 7;;;

(b) Suppose that you run a bus lending business, and each request is at the fonnat: (start
time, end time). A bus can be used by one user at time. Suppose that you have got the
following bus-one requests for the next day. (12)
Contd P/2
 =2=

CSE 203
Conld ..... Q. No. 2(b)

{[I, 6), [4, 8), [6, 8), [9,15), [6, 9), [11,15), [2, 6)}
Find all solutions of the maximum number of requests that can be satisfied by using
(i) earliest start time,
(ii) shortest interval, and
(iii) earliest end time.
(c) Let AI (lx4), A2(4x5), A3(5x3), A4 (3x6), As (6x7), A6 (7xl) be six matrices.
Compute m[l, 6] by assuming m[l, 3] = 35, m[2, 4] = 132, m[l, 5] = 95, m[2, 5] = 270,

m [2, 6] = 95, m [4, 5] = 126, m [4, 6] = 60. (13)

3. (a) Briefly explain the steps that are to be followed for solving a problem using dynamic

programming method. (10)

(b) Show that the fractional knapsack problem has the optimal substructure property.

Also show that the 0-1 knapsack problem has the overlapping subproblems property. (10)
(c) Write the quick sort algorithm. Analyzc the best case and worst case time-

complexities of the algorithm. (15)

4. (a) Explain, with examples, the union-by-rank and the path-compression heuristics that

are used in UNION and FIND operations of disjoint-set data structures. (10)
(b) Assume that you are given a Max Priority Queue of n elements. Write a function that

first finds and then deletes the minimum element of the priority queue. (10)
(c) Find all longest common subsequences of X = (TAAGUATU) and Y = (AUAGTUT)
by using dynamic programming method. Also find a shortest common supersequence of

X and Y using an LCS of X and Y. (15)

The shortest common supersequence problem is defined as: Given two sequences X and
Y, find the shortest sequence that has both X and Y as subsequences. For example, for
two sequences X = (BUET) and Y = (CSE), a shortest common supersequence is

(BCUSET).

SECTION -B

There are FOUR questions in this section. Answer any THREE.

5. (a) You are given two sorted lists of size m and n. Give an O(1ogm + logn) time

algorithm for computing the kth smallest element in the union of two lists. (12)
(b) Describe the worst case running time of the following code in "big-Oh" notation in

terms of the variable n. You should give the tightest bound possible. (5)

Contd P/3
 =3=
CSE 203
Coutd ..... Q. No. 5(b)

int f(int n)
{ . - .', . .
if (n <' 10) , .
. (sys.tein.out.println{".!"); return n+3; )
else .
, } .'( return 1(n-l) +.f(n-l) ~ } . \
~
(c) Suppose that you observe that a program takes 30 seconds to complete on inputs of
size 600, 4.5 minutes to complete on inputs of size 1800 and 20 minutes to complete on
inputs of size 2000. Develop a reasonable assumption for the order of growth of the
running time. (10)
(d) Given two arrays a [ ] and b [ ], each containing N distinct points in the plane, design
an algorithm whose running time is linear under reasonable assumptions and uses at most
linear extra space to determine whethcr the two arrays contains precisely the same set of
points (but possibly in a different order). (8)

6. (a) Give the algorithm for converting an infix expression to postfix, evaluating a postfix
expression using a stack. (10)
(b) Give a concise accurate description of a good way for quicksort to choose a pivot
element. Your approach should be better than "use the entry at location [0]". (5)
(c) Ternary search, like binary search, is a divide-and-conquer algorithm. It is mandatory
for the array (in which you will search for an element) to be sorted before you begin the

search. In this search, after each iteration it neglects X part of the array and repeats the
same operations on the remaining X. Write an algorithm for ternary search and show its
complexity. (12)
(d) Given a directed graph with N vertices and M edges that may contain cycles, write a
function to find the lexicographically smallest topological ordering of the graph if it
exists otherwise print-] (if the graph has cycles). (8)
Lexicographycally smallest topological ordering means that if two vertices in a graph do
not have any incoming edge then the vertex with the smaller number should appear first
r----..
in the ordering.
L:
7. (a) Consider the following max-heap of letters: (7)

Contd P/4
,

=4=
CSE 203
Contd ..... Q. NO.7

(b) Suppose you have a set of numbers where you do a constant number of insertions and
a linear number oflookups of the maximum over some time period. To maintain your set
of numbers, you can choose between using either a heap or a binary search tree. i)
Assume you are interested in minimizing the average total runtime over the time period.
For each structure, what is the asymptotic upper bound on the average case runtime, and

which of the two structures should you choose? (12)

ii) Suppose you realize that you are actually interested in the worst case. For each
structure, what is the asymptotic upper bound on the worst case runtime, and which of the
two structures should you choose now?

(c) Explain when there is no back edge, ifDFS is perfonned on an undirected graph. (8)
(d) Give the running times of DFS in terms of IVI and lEI, when using adjacency lists and

adjacency matrix to represent the graph, respectively. (8)

8. (a) Write a function int treeHeight ( ) for a Binary Search Tree that computes the height
of the tree. Give a worst-case big-Oh running time in terms ofn, where n is the number of

nodes in the trce. (8)

(b) Write functions void deleteMax ( ) for a Binary Search' Tree that deletes the
maximum element in the tree (or does nothing if the tree has no elements). Give a worst-
case big-Oh running time in terms of n, where n is the number of nodes in the tree. Do

not assume the tree is balanced. (7)

(c) Suppose you have a graph like the one below. The dots signify some part of the graph
,
that you don't know exactly, not a straight link. You know however, that there are many
paths from the start to the goal. You also know that they tend to be rather long. Suppose
that you want to implement a program that searches for a path and returns the first one it
can find. You have no need for finding the optimal path in any sense, just any path will
do. Would you want to use BFS or DFS as the basis for your program? Justify your

answer. (10)

(d) Describe a situation where storing items in an array is clearly better than storing items
on a linked list. (5)
(e) Write a method isHeap() which determines whether a particular binary tree is a heap.
What is the big-Oh bound on the running time of this algorithm? (5)
L-2/T-1/CSE Date: 31/08/2021

BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY, DHAKA

L-2/T-1 B. Sc. Engineering Examinations 2019-2020
Sub: CSE 203 (Data Structures and Algorithms I)
Full Marks: 210 Time: 2 hours and 30 minutes
USE SEPARATE SCRIPTS FOR EACH SECTION
The figures in the margin indicate full marks.
SECTION – A
There are FOUR questions in this section. Answer any THREE.
1. (a) Apply dynamic programming to calculate edit distance of the following two (15)
DNA sequences:
TGCATAT
ATCCGA
where,
cost of insertion or deletion = 2
cost of substitution = 1

Write the recurrence relation and explain the intuition behind it, populate the
DP table according to that recurrence relation and calculate the edit distance
of the given DNA sequences from that table.

(b) A set of tasks with deadlines and the total profit earned on completing each (10+10
task have been given below. =20)

Task Deadline Profit

T1 7 9
T2 3 14
T3 2 5
T4 6 10
T5 8 3
T6 5 15
T7 6 5
T8 3 7
T9 2 8
T10 4 6

Assume that a task takes one unit of time to execute, and it can’t execute
beyond its deadline. Also assume that only a single task will be executed at a
time.

Write an algorithm to calculate the maximum profit earned by executing the

tasks within the specified deadlines and calculate the maximum profit from
the given data using the algorithm.

2. (a) Propose the pseudocode of merge sort algorithm where the array is divided in (10+8+7
three equal parts at each step of divide. Derive the asymptotic runtime of this =25)
algorithm. Compare the runtime of this algorithm with the usual merge sort
algorithm (i.e. where the array is divided in two equal parts at each step of
divide) and mention the cases when one will outperform another.
(b) Explain how a recursion tree can help substitution method of runtime (5)
analysis.

(c) Describe a scenario where an “in-place” sorting algorithm is necessary and (5)
explain the reasons.
L-2/T-1/CSE Date: 31/08/2021

3. (a) Apply partition procedure of Quicksort once on the following array, where the (10+7
partition procedure chooses the element of the middle index (i.e. index ⌈(𝑝 + =17)
𝑞)/2⌉) as pivot, assuming that the indices of the elements range from 𝑝 to 𝑞
(inclusive).
[10, 30, 50, 70, 90, 100, 80, 60, 40, 20]

You can assume that indexing of array starts from 0. Show all the steps.
Prove or disprove the fact that if we choose the element at middle index as
pivot during partition (as stated above), the Quicksort algorithm will never
have a runtime of Θ(𝑛2 ).

(b) Write an algorithm to find a peak element of a 𝑛 × 𝑛 matrix in O(𝑛) time (10+8
using divide and conquer approach. A peak element of a 2-dimensional matrix =18)
is an element which has left, right, top and bottom elements (if available)
lower than it. Define the recurrence relation and derive the runtime from it.

4. (a) Write an algorithm to detect cycle in an undirected graph using disjoint set (10+5
data structure. Mention the cases where this algorithm will perform more =15)
efficiently than BFS or DFS based approach.

(b) Explain whether we can apply master method to any recurrence relation of the (8)
form 𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑓(𝑛). If we cannot, explain a case where the
theorem cannot be applied.

(c) Express the following function in Θ notation with proper explanation: (7)
𝑓(𝑛) = 5𝑛 − 2𝑛2

(d) Traditional insertion sort uses a linear search to scan (backward) through the (5)
sorted subarray A[1 .. j-1], where A[j] is the element to be inserted next.
Prove or disprove the idea that we can use a binary search instead to improve
the overall worst-case running time of insertion sort to Θ(𝑛𝑙𝑔𝑛).
L-2/T-1/CSE Date: 31/08/2021

BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY, DHAKA

L-2/T-1 B. Sc. Engineering Examinations 2019-2020
Sub: CSE 203 (Data Structures and Algorithms I)
Full Marks: 210 Time: 2 hours and 30 minutes
USE SEPARATE SCRIPTS FOR EACH SECTION
The figures in the margin indicate full marks.
SECTION – B
There are FOUR questions in this section. Answer any THREE.
5. (a) You are given the following undirected graph that you need to traverse by following (10+10)
both BFS and DFS techniques. You will start the search from vertex u. Show the
simulation steps of your algorithm for labeling the vertices in order of the visits. In
case of BFS, the label of a vertex will be the level of the BFS search; whereas in case
of DFS, you have to put two labels: first time and the last time of visiting the vertex.
Also, write the pseudo-codes of BFS and DFS that you will be using to run the
simulations.

(b) Write a Graph (directed) data structure using a linked list. Write a delete node (8+7)
operation for the data structure.

6. (a) Show the steps of building a max-heap by inserting the following numbers one-by- (10+5)
one 45, 36, 27, 14, 86, 19, 69, and 10. Also, show the memory representation of the
heap.
(b) Write down the steps of sorting the above numbers (in Question 6 (a)) using heap-sort. (10)
(c) Show the analysis how the build max-heap can be done in big-Theta (n), where n is (10)
the input size.

7. (a) What does the term Asymptotic mean in complexity analysis? Can we show the (5+5+5)
worst case and average case case time complexity using big-Theta notation? If yes,
how and when can we do that?
(b) (5+5)
L-2/T-1/CSE Date: 31/08/2021

Consider the above code snippet for a binary search, where you are searching for an
item x from an array a of size n. If all primitive operations (addition/subtraction,
comparison, assignment, etc.) take one unit of time each to execute, what will be the
time complexity of the above algorithm by counting all the primitive operations
performed. Can you show the worst case time complexity of the above algorithm using
big-Oh notation?

(c) int i, j, k = 0; (10)

for (i = n / 2; i <= n; i++) {
for (j = 2; j <= n; j = j * 2) {
k = k + n / 2;
}
}
Derive the time complexity of the above code snippet, and write down the asymptotic
complexity using big-Oh notation. Can we show the complexity using big-Theta
notation? What is the difference in meaning between complexities while you use big-
Oh or big-Theta?

8. (a) Write a code snippet to implement a queue using a circular array, where each element (13)
of the queue contains the ID, name, and department of a student.
(b) How do you determine whether a given graph is bipartite? (10)
(c) Consider the following hierarchical structure of a file system. Write a program to print (12)
the directory hierarchy of the file system, where all children of a parent will be placed
one tab-space right from the parent. Use depth-first tree traversal technique to perform
the above task.