COMPUTER SCIENCE AND ENGINEERING

Category L T P Credit Year of

CST 308 COMPREHENSIVE Introduction
COURSE WORK PCC 1 0 0 1 2019

Preamble:
The objective of this Course work is to ensure the comprehensive knowledge of each student in
the most fundamental core courses in the curriculum. Six core courses credited from
Semesters 3, 4 and 5 are chosen for the detailed study in this course work. This course helps
the learner to become competent in cracking GATE, placement tests and other competitive
examinations
Prerequisite:
1. Discrete Mathematical Structures
2. Data Structures
3. Operating Systems
4. Computer Organization And Architecture
5. Database Management Systems
6. Formal Languages And Automata Theory

Course Outcomes: After the completion of the course the student will be able to

CO1 Comprehend the concepts of discrete mathematical structures (Cognitive Knowledge

Level: Understand)
CO2 : Comprehend the concepts and applications of data structures (Cognitive Knowledge
Level: Understand)
CO3 : Comprehend the concepts, functions and algorithms in Operating System (Cognitive
Knowledge Level: Understand))
CO4 : Comprehend the organization and architecture of computer systems (Cognitive
Knowledge Level: Understand)

CO5 : Comprehend the fundamental principles of database design and manipulation

(Cognitive Knowledge Level: Understand)
CO6 : Comprehend the concepts in formal languages and automata theory Cognitive
Knowledge Level: Understand)

184
 COMPUTER SCIENCE AND ENGINEERING

Mapping of course outcomes with program outcomes

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO1 PO11 PO1
0 2
CO1

CO2

CO3

CO4

CO5

Assessment Pattern

Bloom’s Category End Semester Examination

Remember 10
Understand 20
Apply 20
Analyse
Evaluate

Create

Mark distribution

Total Marks CIE ESE ESE Duration

50 0 50 1 hour

End Semester Examination Pattern: Objective Questions with multiple choice (Four). Question paper
include fifty questions of one mark each covering the five identified courses.

185
 COMPUTER SCIENCE AND ENGINEERING

Syllabus
Full Syllabus of all six selected Courses.

1. Discrete Mathematical Structures

2. Data Structures
3. Operating Systems
4. Computer Organization And Architecture
5. Database Management Systems
6. Formal Languages And Automata Theory

Course Contents and Lecture Schedule

No Topic No. of
Lectures

1 DISCRETE MATHEMATICAL STRUCTURES (14 hours)

1.1 Mock Test on Module 1 and Module 2 1 hour

1.2 Mock Test on Module 3, Module 4 and Module 5 1 hour

2 DATA STRUCTURES

2.1 Mock Test on Module 1, Module 2 and Module 3 1 hour

2.2 Mock Test on Module 4 and Module 5 1 hour

3 OPERATING SYSTEMS

3.1 Mock Test on Module 1 and Module 2 1 hour

3.2 Mock Test on Module 3, Module 4 and Module 5 1 hour

3.3 Feedback and Remedial 1 hour

4 COMPUTER ORGANIZATION AND ARCHITECTURE

4.1 Mock Test on Module 1, Module 2 and Module 3 1 hour

4.2 Mock Test on Module 4 and Module 5 1 hour

5 DATABASE MANAGEMENT SYSTEMS

186
 COMPUTER SCIENCE AND ENGINEERING

5.1 Mock Test on Module 1, Module 2 and Module 3 1 hour

5.2 Mock Test on Module 4 and Module 5 1 hour

6 FORMAL LANGUAGES AND AUTOMATA THEORY

6.1 Mock Test on Module 1, Module 2 and Module 3 1 hour

6.2 Mock Test on Module 4 and Module 5 1 hour

6.3 Feedback and Remedial 1 hour

Model Question Paper

QP CODE:

Reg No: _______________

Name: _________________ PAGES : 10

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

SIXTH SEMESTER B.TECH DEGREE EXAMINATION, MONTH & YEAR
Course Code: CST 308
Course Name: Comprehensive Course Work
Max. Marks: 50 Duration: 1 Hour
Objective type questions with multiple choices. Mark one correct answer for each question.
Each Question Carries 1 Mark

1. What is the maximum possible number of relations from a set with 5 elements to another set
with 4 elements?

(A) 2^10 (B)2^16 (C)2^20 (D)2^25

2. The set {1,2,4,7,8,11,13,14} is a group under multiplication modulo 15. Find the inverse of
element 13

(A) 7 (B) 13 (C) 1 (D) 8

3. Consider the recurrence relation a1 = 2, an = 3n+an-1 Then a72 is

187
 COMPUTER SCIENCE AND ENGINEERING

(A) 7882 (B) 7883 (C) 7884 (D) 7885

4. Which among the following is a contradiction?

(A) (𝑝𝑝 ∧ 𝑞𝑞) ∨ ¬(𝑝𝑝 ∨ 𝑞𝑞) (B) (𝑝𝑝 ∨ 𝑞𝑞) ∧ ¬(𝑝𝑝 ∧ 𝑞𝑞)
(C) (𝑝𝑝 ∧ 𝑞𝑞) ∧ ¬(𝑝𝑝 ∨ 𝑞𝑞) (D) (𝑝𝑝 ∧ 𝑞𝑞) ∨ (𝑝𝑝 ∧ ¬𝑞𝑞)

5. The number of non-negative solutions to 𝑥𝑥 + 𝑦𝑦 + 𝑧𝑧 = 18, with conditions 𝑥𝑥 ≥ 3, 𝑦𝑦 ≥ 2, 𝑧𝑧 ≥

1𝑖𝑖𝑖𝑖
(A) 84 (B) 91 (C) 105 (D) 121
6. The solution of the recurrence relation 𝑎𝑎𝑛𝑛 = 𝑎𝑎𝑛𝑛−1 + 2𝑎𝑎𝑛𝑛−2 with initial conditions 𝑎𝑎0 =
2, 𝑎𝑎1 = 7, is
(A) 3(2)𝑛𝑛 − (−1)𝑛𝑛 (B) 3(2)𝑛𝑛 + (−1)𝑛𝑛
(C) -3(2)𝑛𝑛 − (−1)𝑛𝑛 (D) -3(2)𝑛𝑛 + (−1)𝑛𝑛

7. Which among the following is not a subgroup of the set of Complex numbers under
addition?
(A) 𝑅𝑅, the set of all Real numbers.
(B) Q+, the set of positive rational numbers.
(C) 𝑍𝑍, the set of all integers.
(D) The set 𝑖𝑖𝑖𝑖 of purely imaginary numbers including 0

8. Minimum number 𝑛𝑛 of integers to be selected from 𝑆𝑆 = {1,2, . . . . ,9} to guarantee that the
difference of two of the n integers is 5 is
(A) 3 (B) 4 (C) 6 (D) 9

9. Find the contrapositive the of statement “If it is a sunday, then I will wake up late”
(A) If I am not waking up late, then it is a suniday
(B) If I am not waking up late, then it is not a suniday
(C) If it is not a sunday, then I will not wake up late.
(D) It is not a sunday or I will wake up late

10. In the poset (Z+, |) (where Z+ is the set of all positive integers and | is the divides relation),
which of the following are false?
I. 3 and 9 is comparable
II. 7 and 10 is comparable
III. The poset (Z+, |) is a total order
(A) I and III (B) II only (C) II and III (D) III only

11. Consider the following sequence of operations on an empty stack.

push(22); push(43); pop(); push(55); push(12); s=pop();

188
 COMPUTER SCIENCE AND ENGINEERING

Consider the following sequence of operations on an empty queue.

enqueue(32);enqueue(27); dequeue(); enqueue(38); enqueue(12); q=dequeue();
The value of s+q is ___________
(A) 44 (B) 54 (C) 39 (D) 70

12. The following postfix expression with single digit operands is evaluated using a stack:
822^/43*+51*-
Note that ^ is the exponentiation operator. The top two elements of the stack after the first *
is evaluated are:
(A) 12,2 (B) 12,5 (C) 2,12 (D) 2,5

13. Construct a binary search tree by inserting 8, 6, 12, 3, 10, 9 one after another. To make the
resulting tree as AVL tree which of the following is required?
(A) One right rotation only
(B) One left rotation followed by two right rotations
(C) One left rotation and one right rotation
(D) The resulting tree itself is AVL

14. In a complete 4-ary tree, every internal node has exactly 4 children or no child. The number
of leaves in such a tree with 6 internal nodes is:
(A) 20 (B) 18 (C) 19 (D) 17

15. Consider the following graph with the following sequences

I. a b c f d e
II. a b e d f c
III. a b f c d e
IV. a f c b e d

a
e
b

c
f

Which are Depth First Traversals of the above graph?

189
 COMPUTER SCIENCE AND ENGINEERING

(A) I, II and IV only (B) I and IV only

(C) II, III and IV only (D) I, III and IV only

16. Consider a hash table of size seven, with starting index zero, and a hash function (2x + 5)
mod7. Assuming the hash table is initially empty, which of the following is the contents of
the table when the sequence 1, 4, 9, 6 is inserted into the table using closed hashing? Note
that ‘_’ denotes an empty location in the table.
(A) 9, _, 1, 6, _, _, 4 (B) 1, _, 6, 9, _, _, 4
(C) 4, _, 9, 6, _, _, 1 (D) 1, _, 9, 6, _, _, 4

17. Consider the following C program where TreeNode represents a node in a binary tree
struct TreeNode{
struct TreeNode *leftChild;
struct TreeNode *rightChild;
int element;
};
int CountNodes(struct TreeNode *t)
{
if((t==NULL)||((t->leftChild==NULL) && (t->rightChild==NULL)))
return 0;
else
{
return 1+CountNodes(t->leftChild)+CountNodes(t->rightChild)
}
}

The value returned by CountNodes when a pointer to the root of a binary tree is passed as its
argument is
(A) number of nodes
(B) number of leaf nodes
(C) number of non leaf nodes
(D) number of leaf nodes-number of non leaf nodes

18. How many distinct binary search trees can be created out of 6 distinct keys?
(A) 7 (B) 36 (C) 140 (D) 132

19. Suppose a disk has 400 cylinders, numbered from 0 to 399. At some time the disk arm is at
cylinder 58, and there is a queue of disk access requests for cylinder 66, 349, 201, 110, 38,
84, 226, 70, 86. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk
access, the request for cylinder 86 is serviced after servicing ____________ number of

190
 COMPUTER SCIENCE AND ENGINEERING

requests.
(A) 1 (B) 2 (C)3 (D)4

20. If frame size is 4KB then a paging system with page table entry of 2 bytes can address
_______ bytes of physical memory.
(A) 2^12 (B) 2^16 (C) 2^18 (D) 2^28

21. Calculate the internal fragmentation if page size is 4KB and process size is 103KB.
(A) 3KB (B) 4KB (C) 1KB (D) 2KB

22. Which of the following scheduling policy is likely to improve interactiveness?

(A) FCFS (B) Round Robin
(C) Shortest Process Next (D) Priority Based Scgeduling

23. Consider the following program

Semaphore X=1, Y=0
Void A ( ) Void B ( )
{ {
While (1) While (1)
{ {
P(X); P(Y);
Print’1’; P(X);
V(Y); Print’0’;
} V(X);
} }
}
The possible output of the program:
(A) Any number of 0’s followed by any number of 1’s.
(B) Any number of 1’s followed by any number of 0’s.
(C) 0 followed by deadlock
(D) 1 followed by deadlock

24. In a system using single processor, a new process arrives at the rate of 12 processes per
minute and each such process requires 5 seconds of service time. What is the percentage of
CPU utilization?
(A) 41.66 (B) 100.00 (C) 240.00 (D) 60.00

25. A system has two processes and three identical resources. Each process needs a maximum of
two resources. This could cause
(A) Deadlock is possible (B) Deadlock is not possible

191
 COMPUTER SCIENCE AND ENGINEERING

(C) Starvation may be present (D) Thrashing

26. Which of the following is true with regard to Round Robin scheduling technique?
(A) Responds poorly to short process with small time quantum.
(B) Works like SJF for larger time quantum
(C) Does not use a prior knowledge of burst times of processes.
(D) Ensure that the ready queue is always of the same size.

27. The size of the physical address space of a 32-bit processor is 2^W words. The capacity of
cache memory is 2^N words. The size of each cache block is 2^K words. For a M-way set-
associative cache memory, the length (in number of bits) of the tag field is
(A) W – N + log2M (B) W – N – log2M
(C) W − N − K − log2M (D) W − N − K + log2M

28. A 64-bit processor can support a maximum memory of 8 GB, where the memory is word-
addressable (one word is of 64 bits). The size of the address bus of the processor is atleast
____ bits.
(A) 30 (B) 31 (C) 32 (D) None

29. The stage delays in a 4-stage pipeline are 900, 450, 400 and 350 picoseconds. The first stage
(with delay 900 picoseconds) is replaced with a functionally equivalent design involving two
stages with respective delays 600 and 550 picoseconds. The throughput increase of the
pipeline is _______ percent.
(A) 38 (B) 30 (C) 58 (D) 50

30. Consider a direct mapped cache of size 256 Kilo words with block size 512 words. There are
6 bits in the tag. The number of bits in block (index) and word (offset) fields of physical
address are is:
(A) block (index) field = 6 bits, word (offset) field = 9 bits
(B) block (index) field = 7 bits, word (offset) field = 8 bits
(C) block (index) field = 9 bits, word (offset) field = 9 bits
(D) block (index) field = 8 bits, word (offset) field = 8 bits

31. The memory unit of a computer has 1 Giga words of 64 bits each. The computer has
instruction format, with 4 fields: an opcode field; a mode field to specify one of 12
addressing modes; a register address field to specify one of 48 registers; and a memory
address field. If an instruction is 64 bits long, how large is the opcode field?
(A) 34 bits (B) 24 bits (C) 20 bits (D) 14 bits

32. A computer has 64-bit instructions and 28-bit address. Suppose there are 252 two-address
instructions. How many 1-address instructions can be formulated?

192
 COMPUTER SCIENCE AND ENGINEERING

(A) 2^24 (B) 2^26 (C) 2^28 (D) 2^30

33. Determine the number of clock cycles required to process 200 tasks in a six-segment
pipeline.(Assume there were no stalls),each segment takes 1 cycle.
(A) 1200 cycles (B) 206 cycles (C) 207 cycles (D) 205 cycles

34. Match the following Lists:

P.DMA 1.Priority Interrupt
Q. Processor status Word 2.I/O Transfer
R. Daisy chaining 3.CPU
S. Handshaking 4.Asynchronous Data Transfer
(A) P-1, Q-3, R-4, S-2 (B) P-2, Q-3, R-1, S-4
(C) P-2, Q-1, R-3, S-4 (D) P-4, Q-3, R-1, S-2

35. Let E1, E2 and E3 be three entities in an E/R diagram with simple single-valued attributes.
R1 and R2 are two relationships between E1 and E2, where R1 is one-to-many, R2 is many-
to-many. R3 is another relationship between E2 and E3 which is many-to-many. R1, R2 and
R3 do not have any attributes of their own. What is the minimum number of tables required
to represent this situation in the relational model?
(A) 3 (B) 4 (C) 5 (D) 6

36. Identify the minimal key for relational scheme R(U, V, W, X, Y, Z) with functional
dependencies F = {U → V, V → W, W → X, VX → Z}
(A) UV (B) UW (C) UX (D) UY

37. It is given that: “Every student need to register one course and each course registered by
many students”, what is the cardinality of the relation say “Register” from the “Student”
entity to the “Course” entity in the ER diagram to implement the given requirement.
(A) M:1 relationship (B) M:N relationship
(C) 1:1 relationship (D) option (B) or(C)

38. Consider the relation branch( branch_name, assets, branch_city)

SELECT DISTINCT T.branch_name FROM branch T, branch S WHERE T.assets > L.assets
AND S.branch_city = "TVM" .
Finds the names of
(A) All branches that have greater assets than all branches located in TVM.
(B) All branches that have greater assets than some branch located in TVM.
(C) The branch that has the greatest asset in TVM.
(D) Any branch that has greater asset than any branch located in TVM.

193
 COMPUTER SCIENCE AND ENGINEERING

39. Consider the following relation instance, where “A” is primary Key.
A1 A2 A3 A4
1 1 1 Null
5 2 5 1
9 5 13 5
13 13 9 15
Which one of the following can be a foreign key that refers to the same relation?
(A) A2 (B) A3 (C) A4 (D) ALL

40. A relation R(ABC) is having the tuples(1,2,1),(1,2,2),(1,3,1) and (2,3,2). Which of the
following functional dependencies holds well?
(A) A → BC (B) AC → B (C) AB → C (D) BC → A

41. Consider a relation R with attributes A, B, C, D and E and functional dependencies A → BC,
BC → E, E →DA. What is the highest normal form that the relation satisfies?
(A) BCNF (B) 3 NF (C) 2 NF (D) 1 NF

42. For the given schedule S, find out the conflict equivalent schedule.
S : r1(x); r2(Z) ; r3(X); r1(Z); r2(Y); r3(Y);W1(X); W2(Z); W3(Y); W2(Y)
(A) T1→T2→T3 (B) T2->T1->T3
(C) T3→T1→T2 (D) Not conflict serializable

43. Which of the following strings is in the language defined by the grammar:
S → aX
X → aX | bX | b
(A) aaaba (B) babab (C) aaaaa (D) ababb

44. Consider the regular expression (x+y)*xyx(x+y)* where Σ = (x,y). If L is the language
represented by this regular expression, then what will be the minimum number of states in a
DFA recognizing L ?
(A) 2 (B) 3 (C) 4 (D) 5

45. Which of the following cannot handle the same set of languages?
(A) Deterministic Finite Automata and Non-Deterministic Finite Automata
(B) Deterministic Push Down Automata and Non-Deterministic Push Down Automata
(C) All of these
(D) None of these

46. Consider L be a context-free language and M be a non-context-free language. Which among

the following is TRUE?

194
 COMPUTER SCIENCE AND ENGINEERING

(I) L will definitely pass the pumping lemma test for CFLs.
(II) M will definitely pass the pumping lemma test for CFLs.
(III) L will not definitely pass the pumping lemma test for CFLs.
(IV) M will not definitely pass the pumping lemma test for CFLs.
(V) L may or maynot pass the pumping lemma test for CFLs.
(VI) M may or maynot pass the pumping lemma test for CFLs.
(A) I, II (B) II, V (C) I, VI (D) IV, V

47. Which of the following problem(s) is/are decidable?

(I) Whether a CFG is empty or not.
(II) Whether a CFG generates all possible strings.
(III) Whether the language generated by a Turing Machine is regular.
(IV) Whether the language generated by DFA and NFA are same.
(A) I and II (B) II and III (C) II and IV (D) I and IV

48. Which of the following is/are TRUE?

(I) Regular languages are closed under complementation.
(II) Recursive languages are closed under complementation.
(III) Context free languages are closed under complementation.
(IV) Context free languages are not closed under complementation.
(A) I, II and III (B) I, II and IV (C) II and III (D) III only

49. Which of the following regular expressions defined over the alphabet Σ = {0,1} defines the
language of all strings of length l where l is a multiple of 3?
(A) (0 + 1 + 00 + 11 + 000 +111)* (B) (000 + 111)*
(C) ((0 + 1)(0 + 1)(0 + 1))* (D) ((000 + 01 + 1)(111 + 10 + 0))*

50. Determine the minimum number of states of a DFA that recognizes the language over the
alphabet {a,b} consisting of all the strings that contain at least three a's and at least four b's.

(A) 6 (B) 12 (C) 15 (D) 20

ANSWER KEY:-

QNo Ans. QNo Ans. QNo Ans. QNo Ans. QNo Ans.
Key Key Key Key Key

1 (C) 11 (C) 21 (C) 31 (B) 41 (A)

195
 COMPUTER SCIENCE AND ENGINEERING

2 (A) 12 (A) 22 (B) 32 (D) 42 (D)

3 (B) 13 (A) 23 (D) 33 (D) 43 (D)

4 (C) 14 (C) 24 (B) 34 (B) 44 (C)

5 (B) 15 (A) 25 (B) 35 (C) 45 (B)

6 (A) 16 (D) 26 (C) 36 (D) 46 (C)

7 (B) 17 (C) 27 (A) 37 (A) 47 (D)

8 (C) 18 (D) 28 (A) 38 (B) 48 (B)

9 (B) 19 (C) 29 (D) 39 (B) 49 (C)

10 (C) 20 (D) 30 (C) 40 (D) 50 (D)

196