COMPUTER SCIENCE
99
PAPER-II
Time Allowed Three hours Maximum Marks 300
The figures in the margin indicate full marks fot the questions

Candidates should answer Question Nos. 1 and 5 which are compulsory and three of the remaining questions, selecting at least. one from each Section
SECTION-A

1. Write a computer program or an algorithm to implement the insertion sort algorithm. 12
(ii)Discuss how the elements in a two-dimensional array are stored in the computer memory. 10
Using any programming language, write down the allocate and release memory space dynamically. statements to 12
Draw a binary search tree when the following sequentially elements are given
5 15 -10 16 20 0 2 60 12
Draw the tree after deleting the element 16. 6

Discuss in short two programming paradigms. 16

(ii)What do you mean by data type? What are the basic elements of the specification of a data type? 4

2. (a)(i)Write a computer program C?r an algorithm to travel a binary tree in inorder and preorder traversal techniques. 16
Trace the binary search algorithm while searching the element 15 in the following array 4
10 1530 40 48 60 70
Differentiate between syntax and semantics of a programming language with examples. 10
(ii)What is binding time? Discuss different classes of binding time: 10

In the context of relational model, distinguish among a primary key, superKey and a candidate key with suitable examples. 16
What is functional dependency? Give one example. What is transitive dependency? Give one example. 8
What is data independence? 2

3. Write a brief note on functional programming or logic programming. 12
are type checking and type conversion essential in a programming language? Briefly describe with programming segment. 8
What is a join operation in DBMS? Explain various types of join operations with examples. 20

(c)Give the layers of the ISO-OSI reference model and explain in brief the functions of each layer. 20


Define spectrum and bandwidth of signal. 6
Define simplex, half-duplex and full-duplex transmissions. 8
Name any three guided transmission media. State one application of each. 6

Discuss briefly the three-me organization techniques. 18

(ii)Give one example each of continuous and non-continuous data structure. 2

Define 3NF and BCNF. Give an example of a relation-that is in 3NF but not in BCNF. 7

Discuss the benefits of connecting computers in a network (any four). 8
(iii)What is a circular-linked list? Differentiate between a circular-linked list and a doubly-linked list. 5

SECTION-B

5. What is entity integrity and referential integrity? Explain each. 8
Explain how redundant information in a database leads to updation anomalies. 6
Consider the relation with X as the primary key. The other functional dependencies are as shown below Is R in BCNF? Given reason. If not, decompose R into an appropriate collection of BCNF relations. 10
What is a data dictionary? Why is a database system called integrated? 6
Define and compare connection-oriented and connectionless service. 12
In the context of computer networks, explain the following terms: 15
Protocol
Interface between layers
Service primitive

(iii)What is pulse code modulation? 3

6. Write a computer program to merge two sorted arrays. What is the
minimum and maximum number of comparisons needed? 12+4=16

Write a program to implement binary search on a sorted array. What·
is the complexity of the algorithm? 4

(b)(i)Briefly discuss on the concept of inheritance and polymorphism in
the· context of OOP. 16
What is static binding? Give one example. 4

Given the relational schema R {Truck Capacity Date Cargo Destination Value with the following functional dependencies . T TY D and CG V Is the decomposition of R into R1(TDC) and R2 (TGDVY) dependency preserving and lossless? Justify. In what normal form are the relations R1 and R 2 If they are not in BCNF, then find a BCNF decomposition of R. 15

List three major responsibilities of a DBA. 5

7. (i)Discuss briefly on dynamic scope and run-time binding. 4+6=10
What is l-value and r-value of a variable? What is a dangling reference?
How can you specify a logical data type? 3

The following describes a database concerning students teachers departments and courses offered by the departments of an educational Institute. The table names and the field names are shown' below. The primary keys are shown by underlining
T TNAME, DNO)
C CNAME, CTYPE, DURATION, DNO, TNO)
D DNAME, HOD)
S SNAME, DNO)
C-S RNO, DATE)

Write appropriate statements in SQL for the following queries 4x5=20
(i)Get names of all courses in which the student with roll number 10 got admitted.
(ii)How many teachers are there in the department D1
(iii)Get names of all teachers in the department offering course numb@r Cl.
(iv)Get details of all courses offered by the department of Physics.
Get names of all teachers in .the department in which A. KALITA is the HOD.

Describe the functions of the Data-link layer and the Network layer. 8+8.=16
(ii)What are the different phases of a PPP protocol? 4

8 What services are expected from the transport layer? Explain briefly. 10
(ii)Which of the transport layer functions are similar to that of data-link layers? How do they differ? 10
Write a program for searching for a given element in a binary search. tree. Use a suitable data structure. 10
(ii)Write down an implementation of stack using dynamic memory allocation technique. Also write functions for PUSH and POP operations. 10
Compare array and linked-list structures with reference to the operations of adding, deleting elements and accessing the i-th element for a given value of i. 15
(ii)Discuss the problem of concurrency suggesting ways of handling it in a database system. 5