Jan2006 B4.1-R3: COMPUTER BASED STATISTICAL AND NUMERICAL TECHNIQUES

1.

a) Compute

using Simpson’s rule of integration with h=0.2.

b) Let f(x) = ln x . Given the table of values

x:	0.40	0.50	0.70	0.80
In x:	-0.916291	-0.693147	-0.356875	-0.223144

Estimate the value of ln (0.60).

c) An infinite sequence of independent trials is to be performed. Each trial results in a success with probability p and a failure with probability 1 – p. What is the probability that

i) at least 1 success occurs in the first n trials;

ii) exactly k successes occur in the first n trials;

iii) all trials result in successes?

d) Suppose that the joint density of X and Y is given by

exp[-(x+y)] , 0≤x,y<¥

f(x,y)=

0 , otherwise

Find E[X] and P(Y>1).

e) The average working-set size X of a program is normally distributed with unknown mean m and a known variance s ² = 81. The program was executed 36 times and the average working-set size for each run recorded. The sample mean was computed to be 100 page frames. Assuming successive runs of the program are independent, find the 95 percent confidence interval for the mean average working-set size.

f) Write down probability density functions of

i) Uniform Variate

ii) Exponential Variate

iii) Normal Variate

iv) Gamma Variate

g) State the axioms of probability. Using these axioms, show that P(A)≤P(B) if A Í B.

(7×4)

2.

a) Consider the set of equations:

6 x + 2 y - z = 4

x + 5 y + z = 3

2x + y + 4 z = 27

Determine approximate solution of the system of equations using Gauss-Seidel method taking the initial solution as x=y=z=1.

b) For the data given below, write the Newton interpolating polynomial of degree 3 for f(x) = x² e^-x/2.

x:	1.10	2.00	3.50	5.00	7.10
f(x):	0.6981	1.4715	2.1287	2.0521	1.4480

Hence, find the error of the interpolate for x=1.75. (Given the tabulated value f(1.75) = 1.28611)

(9+9)

3.

a) In answering a question on a multiple choice test, an examinee either knows the answer or he guesses or he copies. Suppose each question has four choices. Let the probability that examinee copies the answer is 1/6 and the probability that he guesses is 1/3. The probability that his answer is correct given that he copied the answer is 1/8. Suppose an examinee answers a question correctly, what is the probability that he really knows the answer?

b) If X and Y are independent Poisson random variables with respective parameters l₁ and l₂, calculate

P(X=k | X+Y=n).

(8+10)

4.

a) The chances of three persons Mr. X, Y and Z becoming managers of a company are 4:2:3. The probabilities that bonus scheme shall be introduced if X, Y and Z become managers are 0.3, 0.5, 0.8 respectively. Find the probability that the bonus scheme will be introduced. What is the probability that X is appointed as the manager?

b) State central limit theorem. Using this theorem argue that if X is binomially distributed with parameters n and p, the distribution of approaches as standard normal Variate as n ® ¥.

c) If and are the standard deviations of independent random samples of size n₁=61 and n₂=31 from normal populations with =12 and =18, find .

(6+6+6)

5.

a) Let X_i, i=1,…,10 , be independent random variables, each uniformly distributed over (0, 1). Calculate an approximation to P( Σ X_i > 6).

b) Ifis a random sample from a Normal population with mean and variance unity, then show that is an unbiased estimator of.

c) X is Poisson Variate with parameters l. Obtain its Mgf. Hence find E[2X+3].

(6+6+6)

6.

a) Let X denote the main memory requirement of a job as a fraction of the total user-allocatable main memory of a computing center. The density function of X has the form:

k + 1) x^k ,if 0 < x < 1, k > 0,

f(x) = 0 , otherwise

A large value of k implies a preponderance of large jobs. If k =0, the distribution-of-memory requirement is uniform. Suppose you have a sample of size 8 given by:

0.25, 0.45, 0.55, 0.75, 0.85, 0.85, 0.95, 0.90

Estimate the value of k, using the method of moments.

b) It is suspected that the number of errors discovered in a system program is Poisson distributed. The number of errors discovered in each one-week period is given as follows:

Number of errors in one-week period (i)	Number of one-week period with i errors	Poisson probabilities	Expected frequencies
0	14	0.150	7.50
1	11	0.284	14.20
2	9	0.270	13.50
3	6	0.171	8.55
4	5	0.081	4.05
5+	5	0.044	2.20

Assume that the total number of errors observed in the 50 weeks was 95. Estimate the rate parameter λ for the Poisson probabilities given above. Test the hypothesis that errors occur according to Poisson distribution using significance level of 0.05.

(8+10)

7.

a) Find the coefficient of linear correlation between the variables X and Y given in the table.

X	1	3	4	6	8	9	11	14
Y	1	2	4	4	5	7	8	9

Also obtain the regression equation of Y on X for the data.

b) State the principle of least squares.

c) Show that cov(aX,Y) = a cov(X,Y).

(10+4+4)

Jan 2006 B3.5-R3: NETWORKING AND MOBILE COMMUNICATIONS

1.

a) How do the layers of the TCP/IP protocol suite correlate to the layers of the OSI?

b) Compare the performance of slotted aloha with that of pure aloha. What is the limitation of aloha protocol in general?

c) Explain the concepts of handoff and dropped call rate. What are soft and hard handoffs.

d) Draw and discuss the conceptual model of DECT (Digital European Cordless Telephone). Give its application areas.

e) If 20 MHz of total spectrum is allocated for a duplex wireless cellular system, with Simplex channel has 25KHz RF bandwidth, find the number of duplex channels and number of channels per cell site, if N=12 cell reuse is used.

f) Compare and contrast the various 2.5G technology paths that each of the major 2G standards provide. Which path has the highest Internet access speed?

g) Draw and explain the wireless LAN architecture and also explain the terms infrastructure mode and Adhoc mode.

(7×4)

2.

a) What are connection oriented and connectionless services? What are service primitives? Explain with an example how these are used.

b) Discuss the role of transport layer and data link layer in the OSI model.

c) What is spread spectrum communication. Explain the terms processing gain, pseudo random code generator and Walsch code.

(6+6+6)

3.

a) What are mobile data communication services and name them. Describe the architecture of HSCSD (High Speed Circuit Switched Data).

b) Draw the detailed block diagram of a cellular system and explain. Also explain the different strategies implemented to avoid interferences in TDMA, FDMA & CDMA systems.

(9+9)

4.

a) Give an account of radio specifications for cordless telecommunication systems such as CT 2 and DECT.

b) What is VSAT? Give the components of VSAT systems.

c) Draw and explain the functional architecture for PACS (Personal Access Communications System). Discuss the frame structure and its radio aspects.

(6+4+8)

5.

a) Draw CDMA based mobile system architecture and explain, how it provides reliable basic phone services. Write the benefits of CDMA to users.

b) Draw the basic reference architecture and signaling interfaces for GSM. Why is Smart card needed in GSM, while it is not required in AMPS?

(9+9)

6.

a) How do you compare D-AMPS and GSM systems in terms of coverage area, transmitted power and error control system, explain what you can do to address adjacent channel and co-channel interference.

b) With the help of a neat diagram explain the UMTS (Universal Mobile Telecommunication System) network architecture. Discuss in detail the logical parts: i) user equipment and ii) core network. How is the number of handoffs reduced for the fast moving traffic?

(9+9)

7.

a) Draw and explain the WAP network configuration. Also discuss the WAP protocol stack.

b) What is frequency management? Discuss different fixed channel assignment strategies. What are its limitations are compared to non-fixed channel assignment methods.

(9+9)

B3.4-R3: OPERATING SYSTEMS

1.

a) Does a process incur more execution overhead compared to a thread? Justify your answer.

b) Distinguish between multiprocessing and multiprogramming.

c) What are the “special files” in Unix?

d) What is the main difference between worm and virus?

e) State the practical limitations of implementing non-preemptive SJF algorithm.

f) What is the difference between a long-term scheduler and a short-term scheduler?

g) How can a single copy of a text editor be used to serve multiple users in a time-sharing system?

(7×4)

2.

a) What is TLB? Find out the effective memory-access time with an 80% hit ratio and the following access times:

TLB access time: 20ns; MM access time: 100ns

b) Describe the public-key encryption scheme and mention how is it advantageous to the data-encryption standard.

(8+10)

3. Consider the following page reference during a given time interval for a memory consisting of 5 frames: y,c,z,c,d,a,y,a,e,a,y,f,d,e. Using the i) FIFO replacement strategy and ii) the LRU replacement strategy compare the results. Repeat both FIFO and LRU replacement strategies for memory with 3 frames and same page reference pattern. Comment on the findings and draw a conclusion justifying the adoption of a particular replacement strategy.

(18)

4.

a) What does ‘init’ do? What happens to the parent process id of a child when the parent terminates before its child? When does a child become ‘zombie’?

b) With reference to Unix when do the following situations occur?

i) Single process table entry contains pointers to the same file table entry.

ii) Different file table entries point to the same i-node table entry.

iii) Shell ‘forks’ a copy of itself and ‘waits’ for the child to terminate.

c) How does CPU time-slice affect the Round-Robin algorithm?

(8+6+4)

5.

a) Show and explain an implementation of the classical producer-consumer (producer produces an item, keeps it in a buffer from where the consumer is picking it up) problem using semaphore.

b) What is dynamic loading? Mention its advantage. How is dynamic linking performed? Mention any disadvantage that you can think of for both the schemes.

(10+8)

6.

a) What is meant by a domain and the rights on it? Describe a Capability list and ways of protecting it from user tampering.

b) Rewrite the following code introducing code parallelism wherever applicable:

For i = 1 to k

a(i) = b(i) + c(i)

For j = 1 to k

d(j) = x(j) – y(j)

For p = 1 to k

x(p) = y(p) + b(p)

read(m,n,o,r)

q = m*n + r/o

write(q)

c) Using preemptive SJF(shortest-job-first) algorithm draw the Gannt chart and calculate the average waiting time for the following processes:

Process Arrival time Burst time

P₀ 0 6

P₁ 2 4

P₂ 3 10

P₃ 7 9

(9+4+5)

7.

a) Where and how “bit vector/table” is used? What are the advantages and disadvantages of the technique?

b) What is deadlock? How can deadlock be prevented by not allowing “Hold and Wait” ? Is it a feasible policy?

c) How can synchronization be achieved when two processes communicate by message passing?

d) Provide a programming example of multithreading giving improved performance over a single-threaded solution.

(5+5+5+3)

B3.3-R3: SOFTWARE ENGINEERING & CASE TOOLS

1.

a) Which production process model is useful for developing very large complex software?

b) Discuss how can one improve visibility of software design and code.

c) What is software reverse engineering?

d) What are the desirable characteristics of a good software design?

e) How can CASE tools help in reverse engineering of software?

f) Why is it necessary to carry out verification and validation of a software product? Who should carry out these activities in software projects?

g) What is big-bang integration testing? Is it suitable for large software systems?

(7×4)

2.

a) What is requirement analysis? What are some fact-finding techniques useful in the context of requirement analysis?

b) Bring out clearly the features of a good SRS document. What are the techniques to ensure quality of an SRS document?

c) Discuss the contents of a software requirement specification document (SRS document). Differentiate between functional and non-functional requirements.

(6+4+8)

3.

a) Define the key concepts of Abstraction, Encapsulation and Polymorphism in the context of Object-oriented Software Engineering.

b) What do you mean by Multiple Inheritance? Show an Inheritance Tree with Multiple Inheritances.

c) What are Abstract Classes? What is their use? Discuss with an example.

(9+4+5)

4.

a) What is coupling? Which form of coupling among software modules is the best? What are the various forms of coupling? Explain.

b) Define Cohesion. What is Functional Cohesion? Does Functional Cohesion within a module bring about good software design? Give an example. What type of coupling and cohesion between/among modules is preferred for good quality software?

(9+9)

5.

a) Define software quality. What are the different metrics of software quality? Discuss in brief.

b) What do you mean by Software Quality Assurance? What are the seven major activities of software quality assurance?

c) Identify some problems associated with the implementation of a successful quality assurance plan in a software development organization.

(8+6+4)

6.

a) What is the purpose of software testing? What is a test case? How is it different from a test suite? Illustrate by a simple example.

b) What is white box testing? Name some white box testing methods.

c) Define maintainability in the context of software. Explain the significance of different types of maintenance.

(8+5+5)

7. Write short notes on any three of the following:

a) Program complexity and its significance

b) Design patterns

c) Version Control and Change Control in the context of Software Configuration Management

d) Software agents

(3×6)

B3.2-R3: BASIC MATHEMATICS

1.

a) If and , then find a vector of magnitude 4 perpendicular to both and .

b) Find

c) Find the value of the determinant

1 1 1

D= a b c

b+c c+a a+b

d) Evaluate

e) Find the area of region bounded by the parabola y²=4x and its latus rectum.

f) Find the equation of the tangent to the curve x=cos q and y=sin q at q = .

g) Test the convergence/divergence of the series:

(7×4)

2.

a) Find the value of the constant p so that the vectors and are coplanar.

b) Using DeMoivre’s theorem, find the value of .

c) Reduce the matrix to echelon form and hence find its rank.

(6+6+6)

3.

a) Examine the continuity of the following function at x = 0

, if x¹0

f(x)=

5 , if x=0,

b) If y=log(1+cosx), and =c, determine the value of c.

d) Solve the following system of equations by Cramer’s rule:

2x + y + z = 7

3x - y – z = -2

x + 2y – 3z = -4

(6+6+6)

4.

a) If and , find .

b) Examine the convergence and absolute convergence of the series: .

c) Find the points of local maxima or local minima, if any, of the function

, .

d) Evaluate .

(3+6+6+3)

5.

a) Obtain the asymptotes of the curve: (x+y)²=xy².

b) Find the vertex and focus of the parabola

y²-4y-2x-8=0

c) Obtain the Taylor’s series for the function at x=0.

d) Draw the graph of the function

x, when o£x<½

f(x)= 1, when x=½

1-x, when ½<x£1.

Is f(x) continuous at x = ?

(6+4+4+4)

6.

a) i) Examine the validity of the Rolle’s theorem for the function

f(x) = cosx in .

ii) Verify Lagrange’s mean value theorem for the function

in [2, 4].

b) Evaluate dx.

c) Find the equation of the circle which touches y-axis and whose center is (1, 2).

d) If and , then find

(6+4+4+4)

7.

a) Classify the following Conics in terms of parabola, ellipse or hyperbola:

i) x²-3xy+y²+10x-10y+21=0

ii) 22x²-12xy+17y²-112x+92y+178=0

b) Find the values of x and y if and (A+B)²=A²+B².

c) Find , when .

d) Show that the following system of equations has infinite number of solutions:

x-2y+3z=0, 2x+4y+z=0, 3x+2y+4z=0

(6+4+4+4)

B3.1-R3: MANAGEMENT FUNDAMENTALS & INFORMATION TECHNOLOGY

1.

a) Explain the role of SWOT Analysis in planning.

b) State the objectives of production planning and control.

c) Discuss various steps of planning process

d) “Investment decisions are irreversible in nature and hence, more risky.” Discuss.

e) Explain how the Internet is changing business model in present day firms.

f) What is an effective control system? Discuss.

g) Distinguish between:

i) Job Rotation and Job Enrichment

ii) Authority and Responsibility

(7×4)

2.

a) What is meaning and scope of marketing research? What are the main steps involved in marketing research? Discuss.

b) Describe various capital budgeting techniques.

c) Discuss any two types of control charts.

(9+5+4)

3.

a) Discuss concepts and perspective of human resource management.

b) What is e-commerce? How is e-commerce business model is different from that of traditional commerce?

c) “Balance Sheet records stock of assets and liabilities while Profit and Loss Account records flows of income and expenses.” In the light of this statement, distinguish balance sheet from Profit and Loss account.

(7+6+5)

4.

a) What are the functions performed by distribution channels.

b) How can information system support strategies at the firm level?

c) Define-

i) ERP

ii) SQC

iii) DSS

iv) CAM

d) Specify any two informational needs of a finance manager that can be satisfied through a suitable information system.

(7+5+4+2)

5.

a) What are the factors determining production control procedures? Explain.

b) What is the goal of installing supply chain management software? Do we need to have ERP software before we install supply chain software?

(9+9)

6.

a) What is information? What is the need of information? What is information technology? Discuss properties and scope of information.

b) What is decision making? Discuss various types of decision-making environments.

c) What is knowledge based expert system? Discuss.

(10+5+3)

7.

a) Discuss briefly Technical Approach, Behavioural Approach and Socio-Technical Approach to information systems.

b) Write short notes on any three of the following:

i) Informal organisations

ii) Knowledge Level Systems in an organisation

iii) Role of information in supply chain management

iv) Intranet and Internet

(9+[3x3])

B2.4-R3: DATA COMMUNICATION AND COMPUTER NETWORKS

PART ONE

(Answer all the questions)

1. Each question below gives a multiple choice of answers. Choose the most appropriate one and enter in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

1.1 Which of the following are the smallest and largest possible values for an IP octet?

A) 0 and 512

B) 255 and 512

C) 0 and 256

D) 0 and 255

1.2 The parameter Bit Error Rate (BER) plays more important role as compared to delay while transmitting

A) Data

B) Audio

C) Video

D) Compressed Video

1.3 Seamless networking refers to

A) A complete end-to-end digital network.

B) Use of a single platform for end-to-end communication where geographical distance between communicating entities is hidden to the end user.

C) Use of a single platform for end-to-end communication where geographical distance between communication entities is visible to the end user.

D) Use of a single platform to transmit data, audio and video.

1.4 In which of the following shape light pulses should be transmitted in order to cancel out nearly all the dispersion effects

A) Cosine

B) Triangular

C) Hyperbolic Cosine

D) Reciprocal of Hyperbolic Cosine

1.5 ARP is used to find

A) IP address

B) MAC address

C) Subnet address

D) Host address

1.6 Throughput of simple ALHOHA is

A) 18%

B) 18.8%

C) 36%

D) 36.8%

1.7 If satellite is in geosynchronous orbit, it completes one orbit in

A) One day (24 hours)

B) One hour

C) One month

D) One year

1.8 Baud is

A) Number of bits per second

B) Number of signal changes per second

C) Number of bytes per second

D) Number of characters per second

1.9 Router operates in

A) Data Link Layer

B) Network Layer

C) Transport Layer

D) All of the above

1.10 In which ARQ, when a NAK is received, all frames sent since the last frame acknowledge are retransmitted

A) Stop-and-Wait

B) Go back n

C) Selective Reject

D) Both A and B

2. Each statement below is either TRUE or FALSE. Choose the most appropriate one and ENTER in the “tear-off” sheet attached to the question paper, following instructions therein. (1 x 10)

2.1 All WANs are necessarily packet switched networks.

2.2 Frame relay uses large variable sized packets in contrast to ATM.

2.3 ASK is a technique to convert digital data to an analog signal.

2.4 Executable files can be transmitted using SMTP.

2.5 Today’s Cellular networks employ all three multiple access schemes namely FDMA, TDMA and CDMA.

2.6 TCP uses a credit-based flow and error control technique that is somewhat different from the sliding-window flow control found in X.25 and HDLC.

2.7 Two computers cannot be connected via USB cable.

2.8 A bridged network allows communication between two computers on one segment to occur simultaneously as communication between two computers on another segment.

2.9 ADSL provides a lower bit rate downstream than upstream.

2.10 HTTP use port 80.

3. Match words and phrases in column X with the closest related meaning/ word(s)/phrase(s) in column Y. Enter your selection in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

X		Y
3.1	Connection Oriented WAN Technology	A.	Telnet
3.2	Circuit Switched B Channels and Packet Switched D Channel	B.	HDLC
3.3	RF based physical layer	C.	CBR
3.4	Remote Login Protocol	D.	HTTP
3.5	Connectionless protocol	E.	Frame Relay
3.6	World Wide Web	F.	TCP
3.7	Real Time Service	G.	ISDN
3.8	Optical Transmission Systems	H.	UDP
3.9	Number of hexadecimal digits in Ethernet address	I.	8
3.10	Data Link layer	J.	ATM
		K.	ABR
		L.	FHSS
		M.	12
		N.	WDM

4. Each statement below has a blank space to fit one of the word(s) or phrase(s) in the list below. Enter your choice in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

A.	CSMS/CD	B.	X.25	C.	Distance vector
D.	QAM	E.	Congestion control	F.	Token bus
G.	ATM	H.	48 Bytes	I.	PSK
J.	Encryption	K.	CSMA/CA	L.	Masquerade
M.	Routing	N.	Ethernet	O.	Link-state
P.	64 Bytes	Q.	Starting Delimiter	R.	SONET

4.1 IEEE 802.3 is popularly known is ________.

4.2 ________ is the network technology that can be used in both LAN and WAN.

4.3 The main characteristics of ________ are link-by-link flow control, sequence numbering and error checking.

4.4 In order to ensure that collisions can be detected by all nodes on the Ethernet network, the lower bound on Ethernet packet length is ________.

4.5 In order to share the transmission media wireless LANs use the ________ scheme.

4.6 ________ is the analog signaling technique used in ADSL and is a combination of amplitude and phase modulation.

4.7 Optimality principle is used in ________.

4.8 A(n) ________ takes place when one entity pretends to be a different entity.

4.9 The first field in a Token Ring frame is called ________.

4.10 Routing protocols based on ________ does not exchange their routing tables periodically.

PART TWO

(Answer any FOUR questions)

5.

a) Write in brief the features of the following transmission media:

i) Coaxial Cable

ii) Fiber Optic Cable

b) Find out the capacity of a telephone line that transmits frequencies from 300 Hz to 3400 Hz with a signal to noise ratio of 35dB.

c) What is pulse code modulation? What is the equivalent bit rate of a PCM channel having bandwidth of 4 KHz?

(8+3+4)

6.

a) What is the difference between: -

i) datagram subnet and virtual-circuit subnet.

ii) circuit switching and packet switching.

b) What advantages does TCP have over UDP? What are the features, which make TCP a reliable protocol?

c) Explain the function of: Repeater, Bridge and Gateways.

(8+[2+2]+3)

7.

a) Explain the operation of CRC error detection method. By means of an example show how:

i) The error detection bits are generated

ii) The received frame is checked for transmission errors

Use the generator polynomial x⁵ + x⁴ + x² + x + 1

b) What is static routing? How does it differ from dynamic routing?

c) Discuss the problem of count to infinity associated with distance vector routing technique.

(8+4+3)

8.

a) What are the reasons for congestion in a network? Describe any one method for congestion control.

b) Could HDLC be used as a data link protocol for a LAN? Explain your answer.

c) Describe the advantages of a small cell size in ATM.

(7+4+4)

9. Write short notes on any three:

a) SNMP

b) VPN

c) Firewall

d) GSM

(5+5+5)

B2.3-R3: BASICS OF OS, UNIX AND SHELL PROGRAMMING

PART ONE

(Answer all the questions)

1. Each question below gives a multiple choice of answers. Choose the most appropriate one and enter in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

1.1 Which one of the following is used to replace a single character in “vi”?

A) O

B) x

C) r

D) N

1.2 Which one of the following lets you know the line number of the current cursor position in “vi” ?

A) <ctrl> g

B) <ctrl> <shift> g

C) <ctrl> <alt> h

D) <ctrl.> h

1.3 The available disk space can be determined under Unix using the command

A) dir

B) df

C) du

D) file

1.4 “init” run-level for system shutdown is:

A) 3

B) 2

C) 1

D) 0

1.5 Which one of the following is a multipurpose tool?

A) grep

B) sed

C) awk

D) editor

1.6 Shell is:

A) Interactive command interpreter

B) Programming language

C) Both A) and B)

D) None of the above

1.7 Which one is an “awk” built-in variable

A) NFS

B) RF

C) OFS

D) None of the above

1.8 Which of the following keys when pressed will generate a shell signal?

A) <shift> <ctrl> a

B) <del>

C) <ctrl> a

D) <ctrl. <del>

1.9 State of a process changes from “run” to “ready” when:

A) Time slice expires

B) Waiting for disk read occurs

C) Waiting for user response occurs

D) All of the above

1.10 A new process executes in Unix by the following command:

A) execute ( )

B) exec ( )

C) exct ( )

D) xcute ( )

2. Each statement below is either TRUE or FALSE. Choose the most appropriate one and ENTER in the “tear-off” sheet attached to the question paper, following instructions therein. (1 x 10)

2.1 In “vi” A appends text at the end of line.

2.2 In “vi” cc changes a line.

2.3 A shell is a user interface.

2.4 i-node is a unix command.

2.5 awk is only a command.

2.6 passwd asks for the old password to every category of users.

2.7 init run level 3 is a full multi-user mode.

2.8 init startup file is /etc/initd.

2.9 forkp ( ) is used to create a process in Unix.

2.10 URL provides the location of the content searched for

3. Match words and phrases in column X with the closest related meaning/ word(s)/phrase(s) in column Y. Enter your selection in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

X		Y
3.1	~	A.	Scheduling process
3.2	File restore	B.	Encryption of password
3.3	SMTP	C.	vi
3.4	IP	D.	HTML
3.5	/etc/shadow	E.	Toggle case of text in “vi”
3.6	File compression	F.	grep
3.7	lpsched	G.	tar
3.8	DNS	H.	A mail protocol
3.9	cron	I.	gzip
3.10	Request – reply protocol	J.	HOME
		K.	Domain Name Service
		L.	FTP
		M.	Client server protocol
		N.	WWW
		O.	An Internet protocol for transmission of data
		P.	Daemon

4. Each statement below has a blank space to fit one of the word(s) or phrase(s) in the list below. Enter your choice in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

A.	sleep	B.	trap	C.	telnet
D.	nice	E.	awk	F.	head
G.	i-node	H.	magic-no	I.	getty
J.	startx	K.	in-core inode	L.	wait
M.	command	N.	a.out	O.	umask
P.	exec	Q.	PCB	R.	command

4.1 ________ can be used to change the default access permission of file.

4.2 Most of the function in “vi” operate in ________ mode.

4.3 To start X server manually ________ command is needed.

4.4 ________ can be single-line programs also.

4.5 init spawns a(n) ________ at every serial port connected to a Terminal.

4.6 The shell built-in command ________ setup a sequence of commands to be executed when a signal occurs.

4.7 Remote login to a machine can be done via ________ command.

4.8 The ________ command provides output from the beginning of the concerned file.

4.9 ________ contains the necessary information about a process.

4.10 ________ keeps description of an open file.

PART TWO

(Answer any FOUR questions)

5.

a) Using “vi” (i) how do you save your work without leaving the editor?

Using “vi” (ii) how will you write selected lines to a file? Mention all options. Give suitable examples.

(iii) What is “yanking”? What does the “!” operator do in “vi”?

b) What do the following commands in “vi” specify? How are they used?

i) map

ii) ?pat

iii) set

iv) ab

(9+6)

6.

a) What are the advantages of having distinct disk partitions?

b) What are the components of every file system?

c) How does kernel access a file?

(5+5+5)

7.

a) How does the “login:” prompt appear?

b) What is the use of sticky bit?

c) How does cron work?

d) What does shell’s & operator do?

(4+4+5+2)

8.

a) What types of variables are PATH and HOME? Why are they called variables? In what ways are they used? What is sed?

b) What are the advantages of cpio over tar?

c) How a client-server environment is created in X?

d) What is xterm?

(6+4+3+2)

9.

a) Write a script to check whether right number of arguments (say, 4) have been entered.

b) Consider the following table:

Employee id	Name	Designation	Department	Date of birth	Salary
2256	A. SINHA	Manager	Sales	01/01/50	12000
2334	R. KUMAR	Sp. Officer	Accounts	02/12/66	15000
2987	B. ROY	Director	Personnel	03/02/58	20000
3214	M. PRAKASH	Manager	R & D	04/06/70	12500

Using awk find the employees who are either born in 1966 or drawing a salary greater than 12000/-.

c) What is grep used for? What are its various options? Give the syntax of the command.

d) What is the purpose of nice command?

(5+4+4+2)

B2.2-R3: INTRODUCTION TO DATABASE MANAGEMENT SYSTEMS

PART ONE

(Answer all the questions)

1. Each question below gives a multiple choice of answers. Choose the most appropriate one and enter in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

1.1 Pick the odd one out

A) Primary key

B) Super key

C) Candidate key

D) Foreign key

1.2 Relational Algebra is

A) Data Definition Language

B) Meta Language

C) Procedural query language

D) Non procedural language

1.3 One of the following is a valid record -based data models

A) Object-oriented model

B) Relational model

C) Entity-relationship model

D) None of the above

1.4 One of the following steps is not involved in processing a query

A) Parsing and translation

B) Optimization

C) Evaluation

D) Distribution

1.5 Which one of the following describes the timestamp-based protocols correctly?

A) This protocol requires that each transaction issue lock and unlock requests in two phases.

B) This protocol employs only exclusive locks.

C) This protocol selects an ordering among transaction in advance.

D) None of the above

1.6 Which one of the following is not a valid relational database?

A) SYBASE

B) ORACLE

C) IMS

D) UNIFY

1.7 4NF is designed to cope with

A) transitive dependency

B) join dependency

C) multi valued dependency

D) none of these

1.8 Which one of the following is a valid join type?

A) natural

B) full outer join

C) on

D) using

1.9 Which one of the following is not a valid aggregation function in SQL?

A) avg

B) min

C) where

D) sum

1.10 Which of the following is not a valid unary operation in the relational algebra?

A) select

B) min

C) project

D) rename

2. Each statement below is either TRUE or FALSE. Choose the most appropriate one and ENTER in the “tear-off” sheet attached to the question paper, following instructions therein. (1 x 10)

2.1 A relationship is an association among several entities.

2.2 Physical data models are used to describe data at the highest level.

2.3 QBE is based on the tuple relational calculus.

2.4 The database schema and the database instance are the same thing.

2.5 Functional dependencies are constraints on the set of legal relations.

2.6 Integrity constraint guard against accidental damage to the database.

2.7 One-way to ensure serializability is to require that access to data items be done in a mutually I exclusive manner.

2.8 The cost of processing a query is not dependent on disk access.

2.9 The recovery scheme does not depend on the concurrency control scheme.

2.10 Deadlocks can be described precisely in terms of a directed graph.

3. Match words and phrases in column X with the closest related meaning/ word(s)/phrase(s) in column Y. Enter your selection in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

X		Y
3.1	Dense index	A.	data are represented by collection of records and relationship among data are represented by links
3.2	Transaction	B.	Query language based on both the relational algebra and the tuple relational calculus
3.3	Shadow Paging	C.	The index structure is the most widely used to several index structures that maintain their efficiency despite insertion and deletion of data
3.4	Referential integrity constraint	D.	A record appears for every search key value in the file
3.5	Committed	E.	A recovery technique
3.6	B+ tree index	F.	This ensures that a value that appears in one relation for a given set of attributes also appears for a certain set of attributes in another relation
3.7	Network Model	G.	The successful completion of a transaction
3.8	Entity	H.	A unit of program execution that accesses and possibly updates various data items
3.9	DMI	I.	A powerful declarative query language
3.10	Embedded SQL	J.	An object in the real world that is distinguishable from all other objects
		K.	The number of entities to which another entity can be associated via a relationship set
		L.	BCNF

4. Each statement below has a blank space to fit one of the word(s) or phrase(s) in the list below. Enter your choice in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

A.	merge-join	B.	natural join	C.	starvation
D.	rollback	E.	from	F.	replicate
G.	cartesian product	H.	relational algebra	I.	fragmented
J.	ordered	K.	transaction	L.	division
M.	hash	N.	trigger	O.	super key

4.1 The _________________ operation allows to combine information from any two relations.

4.2 A(n) ___________________ is a statement that is executed automatically by the system as a side effect of a modification to the database.

4.3 The __________________ algorithm can be used to compute natural joins and equi-joins.

4.4 If a relation is __________________ a copy of that is stored in two or more sites.

4.5 A(n) _______________________is a set of one or more attributes that taken collectively allows us to identify uniquely an entity in the entity set.

4.6 A(n) ______________________ is a collection of operations that performs a single logical function in a database application.

4.7 The ______________________ clause by itself defines a Cartesian product of the relations in the clause.

4.8 ________________________ indices are based on the values being distributed informally across a range of buckets.

4.9 The___________________ is a situation where a transaction never completes its designated task.

4.10 The___________________ operation is suited to queries that include the phase “for all”.

PART TWO

(Answer any FOUR questions)

5.

a) Construct an E-R diagram for a hospital with a set of patients and a set of medical doctors. Associate with each patient a log of the various tests and examinations conducted.

b) Explain the advantages and disadvantages of Database Processing?

(10+5)

6.

a) List and explain with suitable example five primary relational algebra operators.

b) What is meant by Heuristic Optimization? Discuss the main heuristics that are applied to query optimization?

(10+5)

7.

a) Consider the insurance database given below:

person (driver-id, name, address)

car (license, model, year)

accident (report-number, date, location)

owns (driver-id, license)

participated (driver-id, car, report-number, damage-amount)

Construct the following SQL queries for this relational database.

i) Find the total number of people who owned cars that were involved in accidents in 2004.

ii) Find the number of accidents in which the cars belonging to “Thakre” were involved.

iii) Delete the Mazda belonging to “S Khan”.

b) How does SQL allow implementation of entity and integrity constraints?

(9+6)

8.

a) List and explain Armstrong’s Axioms.

b) Explain the purpose and utility of different normal forms. Specifically define and differentiate between third normal form and BCNF.

c) What is referential integrity? Explain with suitable examples.

(5+5+5)

9.

a) Explain ACID property of transactions.

b) What do you understand by lock granularity? Explain

c) Explain in brief working of two-phase locking protocol.

(5+5+5)

B2.1-R3: DATA STRUCTURE THROUGH ‘C’ LANGUAGE

PART ONE

(Answer all the questions)

1. Each question below gives a multiple choice of answers. Choose the most appropriate one and enter in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

1.1. Adjacency matrix for a digraph is

A) Unit Matrix

B) Symmetric Matrix

C) Asymmetric matrix

D) none of the above

1.2. Time complexity of insertion sort algorithm in the best case is

A) O(n)

B) O(n log₂ n)

C) O(n²)

D) none of the above

1.3. The prefix expression for the infix expression a * ( b + c ) /e – f is

A) /* a + bc – ef

B) -/ * + abc ef

C) - / * a + bcef

D) none of the above

1.4. In linked list representation, a node contains at least

A) node address field, data field

B) node number, data field

C) next address field, information field

D) none of the above

1.5. Number of nods in a complete binary tree of depth k is

A) 2^k

B) 2k

C) 2^k-1

D) none of the above

1.6. The smallest number of keys that will force a B-Tree of order 3 to have a height 3 is:

A) 12

B) 10

C) 7

D) none of the above

1.7. Given two sorted lists of size “m” and “n” respectively, the number of comparisons needed in the worst case by the merge sort will be:

A) m*n

B) max(m,n)

C) min(m.n)

D) m + n – 1

1.8 Any string of bits of length n represents a unique non-negative integer between

A) 0 and 2^n-1 -1

B) 0 and 2^n-1

C) 1 and 2^n-1

D) none of the above

1.9 Which of the following expressions accesses the (i,j)^th entry of a m ´ n matrix stored in a column major form ?

A) m * ( i –1 ) + j

B) m * ( j –1 ) + i

C) m * ( n – j ) + i

D) m * ( m – i ) + j

1.10 The following sequence of operation is performed on a stack

push(1), push (2), pop, push(1), push(2), pop, pop, pop, push(2), pop.

The sequences of popped out values are

A) 2, 2, 1, 2, 1

B) 2, 2, 1, 1, 2

C) 2, 1, 2, 2, 1

D) 2, 1, 2, 2, 2

2. Each statement below is either TRUE or FALSE. Choose the most appropriate one and ENTER in the “tear-off” sheet attached to the question paper, following instructions therein. (1 x 10)

2.1 All primitive recursive functions can be solved iteratively.

2.2 Breadth – first search algorithm can only be used for undirected graph.

2.3 De-referencing operator * has the same effect when it is applied to a pointer or to a structure.

2.4 Binary search performs efficiently on a linked list.

2.5 A symbol table can be constructed using binary tree.

2.6 A pre-order and post-order traversal sequence uniquely defines a tree.

2.7 If an undirected graph is of “n” vertices and “e” edges then the sum of degrees of all vertices is 2e.

2.8 The adjacency matrix corresponding to a graph consisting of “n” nodes but no edges is a unit matrix.

2.9 Recursion cannot be removed without using a stack.

2.10 Pointers are used for dynamically allocated memory.

3. Match words and phrases in column X with the closest related meaning/ word(s)/phrase(s) in column Y. Enter your selection in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

X		Y
3.1	Order notation	A.	Stack
3.2	Pattern matching	B.	Dynamic storage allocation
3.3	Dynamic data structure	C.	Two’s compliment
3.4	Height Balanced Trees	D.	Primitive data type
3.5	Data structure for back tracking	E.	Finite automata
3.6	Circular list with “head” pointing to the last node	F.	Adjacency list
3.7	Suitable data structure for efficiently computing adjacent vartices of a given vertex	G.	Adjacency matrix
3.8	Partition exchange sort	H.	AVL Trees
3.9	Stable sorting Algorithm	I.	Adjacency multi list
3.10	Unique representation for zero	J.	Queue
		K.	Tree
		L.	Breadth – first
		M.	Depth – first
		N.	Quick sort
		O.	merge sort
		P.	Complexity measurement

4. Each statement below has a blank space to fit one of the word(s) or phrase(s) in the list below. Enter your choice in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

A.	circular queue	B.	stack	C.	simple queue
D.	band	E.	sparse	F.	many-to-many
G.	one-to-many	H.	depth-first-search	I.	breadth-first search
J.	log2 n	K.	n log2 n	L.	E / (n + 1)
M.	Insertion	N.	Log2 n + 1	O.	recursive
P.	Compaction	Q.	N

4.1 Matrices in which non-zero entries tend to cluster around the middle of each row are called __________ matrix.

4.2 A graph represents ________ relationship between nodes.

4.3 ___________ can be used to find the shortest distance between given two nodes in a graph.

4.4 Time complexity of inserting an element to a heap of “n” elements is of the order of _________.

4.5 If “E” is the total external length of a binary tree with “n” nodes then average number of comparisons for unsuccessful search is ________________.

4.6 _________ data structure may give overflow error, even though the current number of elements in it is less than its size.

4.7 Conversion of infix arithmetic expression to prefix expression requires the use of __________.

4.8 The minimum number of edges in a connected cyclic graph of “n” vertices is_________.

4.9 Linked list is preferred over an array for _________ operation.

4.10 Recursion often provides elegant solution to programming task but _______ function chew up a lot of memory.

PART TWO

(Answer any FOUR questions)

5.

a) What are the limitations of array data structure?

b) Show with the help of an example, how the above limitations can be avoided by “linked” representation of lists?

c) Show the representation of linked lists using arrays.

d) What do you mean by linear list and generalized list?

(4+4+4+3)

6.

a) Write a “C” function to copy one stack to another assuming the stack is implemented using array.

b) Write an algorithm to evaluate Postfix expression with the help of a stack.

(8+7)

7.

a) Write a “C” function to implement the Knuth Mooris Pratt algorithm for string searching.

b) A function A(m,n) is defined as follows.

A(m,n) = n + 1, if m = 0

= A ( m – 1, 1), if n = 0

= A(m – 1, A(m, n-1)), otherwise

write a recursive “C” function to compute A(m,n)

(8+7)

8.

a) Prove that the maximum number of nodes in a binary tree of height “k” is 2^k+1-1.

b) Consider the following binary tree

Indicate the output in the following cases: -

i) When the tree is traversed in an “inorder” fashion.

ii) When the tree is traversed in an “preorder” fashion.

iii) When the tree is traversed in an “Postorder” fashion.

(6+[3×3])

9.

a) Show with the help of an example that the simple selection sort is not data sensitive.

b) Find the time complexity of the simple selection sort.

c) Write a recursive “C” function to implement binary search.

(6+3+6)

10.

a) Write a “C” function to compute the in-degree and out-degree of a vertex of a directed graph when the graph is represented by an adjacency list.

b) What is a spanning tree? What do you mean by minimal spanning tree?

(9+[3+3])