Printed Page: 1 of 2

Subject Code: MTCS101

0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

MTECH
(SEM I) THEORY EXAMINATION 2023-24
FOUNDATION OF COMPUTER SCIENCE
TIME: 3HRS M.MARKS: 70

Note: 1. Attempt all Sections. If require any missing data; then choose suitably.

SECTION A
1. Attempt all questions in brief. 2 x 7 = 14
a. Compare and contrast the operations of enqueue and dequeue in a queue data
structure.
b. Explain the concept of a doubly linked list.
c. Define the term PDA.
d. Explain the concept of Distributed Databases.
e. Define Paging.
f. What do you mean by DDL and DML?
g. What is Critical Section?

SECTION B
2. Attempt any three of the following: 7 x 3 = 21
a. Explain the concept of a binary search tree (BST). How does a BST differ from
29
a regular binary tree?

98
b. Consider the set of 6 processes whose arrival time and burst time are given
_0

9.
below-
P2

24
1.
4D

.2
P2

25
Q

|1
5 8
3:
:2
13

If the CPU scheduling policy is shortest remaining time first, calculate the
4
02

average waiting time and average turn around time.

c. Explain the closure properties of regular languages.
-2

d. Explain the concept of deadlock. Also Discuss the concepts of deadlock

03

detection and avoidance in the context of database management systems

2-

(DBMS).
|2

e. Construct the minimum spanning tree (MST) for the given graph using Prim’s
Algorithm-

1|Page
QP24DP2_029 | 22-03-2024 13:23:58 | 125.21.249.98
 Printed Page: 2 of 2
Subject Code: MTCS101
0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

MTECH
(SEM I) THEORY EXAMINATION 2023-24
FOUNDATION OF COMPUTER SCIENCE
TIME: 3HRS M.MARKS: 70

SECTION C
3. Attempt any one part of the following: 7x1=7
(a) Discuss step by step procedure for sorting the following elements using
MERGE SORT
30,12,38,8,5,15,1,40,42.
(b) Explain the concept of depth-first search (DFS) and breadth-first search (BFS)
algorithms. Provide pseudocode for each algorithm and discuss their
applications in solving different problems.
4. Attempt any one part of the following: 7x1=7
(a) Explain the concept of virtual Memory. Also discuss how it is implemented?
(b) Explain the producer-consumer problem in concurrent programming. What are
the roles of producers and consumers?
5. Attempt any one part of the following: 7x1=7
(a) Construct a DFA equivalent to the NFA 29

98
_0

9.
P2

24
1.
4D

.2
P2

25
(b) Construct a minimum state automata equivalent to a DFA
Q

|1
5 8
3:
:2
13
4
02
-2
03

6. Attempt any one part of the following: 7x1=7

2-

(a) Define Serializability? Explain conflict and view serializability.

|2

(b) Explain Time Stamp Based Protocol with the help of an example.

7. Attempt any one part of the following: 7x1=7

(a) Explain the concept of log-based recovery in database systems. How does it
ensure data consistency and recoverability?
(b) Explain the concept of normalization in database design. Why is it important,
and what are the different normal forms?

2|Page
QP24DP2_029 | 22-03-2024 13:23:58 | 125.21.249.98