2010 Dec.pdf
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View 2010 Dec.pdf as PDF for free.
More details
- Words: 2,659
- Pages: 28
(DMCS 01) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. (Examination at the end of First Year) Computer Science Paper I — DATA STRUCTURES Time : Three hours
Maximum : 75 marks
SECTION A — (3 15 = 45 marks) Answer any THREE questions. 1.
Explain in detail about the overview of Data structures.
2.
Explain circular linked list and double-linked list.
3.
Explain CPU scheduling in Multiprogramming Environment.
4.
Explain the operations on B-trees.
5.
(a)
Explain metrix representation using graphs. (8)
(b)
Explain Euler’s and Hamiltonian circuits. (7)
SECTION B — (5 5 = 25 marks) Answer any FIVE questions. 6.
Write a routine for adding an item in a double linked list.
7.
How do you represent a Queue using linked list?
8.
Explain Heshing techniques.
9.
Write a routine to merge two Binary Trees.
10.
Explain Threaded Binary Tree.
11.
Explain Quicksort with an example.
12.
Explain shortest path problem.
13.
Explain Sparse Matrix Manipulation. SECTION C — (5 1 = 5 marks) Answer ALL questions.
14.
Define dequeue.
15.
What is Height Balanced Binary tree?
16.
What are the operations performed on stack?
17.
Define Forest.
18.
Define minimum spanning tree. ———————––– 2
(DMCS 01)
(DMCS 02) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. (Examination at the end of First Year) Computer Science Paper II — OBJECT ORIENTED PROGRAMMING Time : Three hours
Maximum : 75 marks
SECTION A — (3 × 15 = 45 marks) Answer any THREE questions. 1.
Explain with suitable example about various flow control statements in C++.
2.
Define constructor. Explain different types of constructors.
3.
What is operator overloading? Write a program to demonstrate ( ) operator overloading.
4.
Write about streams and describe stream classes hierarchy.
5.
Briefly explain about try and catch blocks. How can you handle multiple catch blocks?
in
detail
about
SECTION B — (5 × 5 = 25 marks) Answer any FIVE questions. 6.
Discuss about different casting operators in C++.
7.
Write a note on pointers and arrays.
8.
Explain about call-by-value and call-by-reference.
9.
Explain about information hiding.
10.
Write about function template.
11.
Define hierarchical inheritance and give an example.
12.
Explain briefly about writing data to a file and reading a file.
13.
Discuss about pure-virtual function. SECTION C — (5 × 1 = 5 marks) Answer ALL questions.
14.
Define void pointer.
15.
What is in-line function?
16.
Define friend class.
17.
Define polymorphism.
18.
What is template? ––––––––––––––– 2
(DMCS 02)
(DMCS 03) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. (Examination at the end of First Year) Computer Science Paper III — COMPUTER ORGANIZATION Time : Three hours
Maximum : 75 marks
SECTION A — (3 15 = 45 marks) Answer any THREE questions. 1.
(a) (b)
2.
(a) (b)
Explain with suitable sketch decoder with 3 inputs. (8) Explain the programmable logic array. (7) Explain the types of registers with suitable diagrams. (8) Simplify the following expression
A Y (W X Y Z )Z . 3.
Explain : (a) Bus and memory transfer (b) Instruction cycle (c) Input output interface.
(7)
4.
5.
(a)
Explain the design issues and data transfer in DMA.
(b)
Explain the design and implementation of hardwired control unit.
(a)
Explain the synchronous and asynchronous date transfer.
(b)
Explain auxiliary memory and associative memory. SECTION B — (5 5 = 25 marks) Answer any FIVE questions.
6.
What is register transfer language?
7.
What is timing and control?
8.
What are the types of ROM?
9.
What is address sequencing?
10.
What are the floating point arithmetic operations?
11.
What is instruction format and explain the types of IF?
12.
Explain the physical characteristics of a magnetic disk.
13.
Explain the riple counter with diagram. 2
(DMCS 03)
SECTION C — (5 1 = 5 marks) Answer ALL questions. 14.
What is adder?
15.
What is a binary counter?
16.
What are the computer instructions?
17.
What is decimal arithmetic unit?
18.
What are the modes of transfer?
—————————
3
(DMCS 03)
(DMCS 04) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. (Examination at the end of First Year) Computer Science Paper IV — DISCRETE MATHEMATICAL STRUCTURES Time : Three hours
Maximum : 75 marks
SECTION A — (3 × 15 = 45 marks) Answer any THREE of the following. 1.
(a)
Construct truth table of the formula
P (b)
Q
R
P Q P R
Obtain the principal conjunctive normal form of
2.
P
Q
P R.
(a)
Show that S R is tautologically implied by
(b)
Show that
P Q P
R Q S .
x P ( x ) Q( x ) x P ( x ) ( x ) Q( x ) .
3.
(a)
Show that
n B Ai i 1
(b)
n
B A . i
i 1
Show that the function f ( x, y ) x y is
primitive recursive. 4.
(a)
For any commutative monoid ( M , ) , show that the set of idempotent elements of M forms a submonoid.
5.
(b)
Show that every distributive lattice is modular, but not conversely.
(a)
If G is a connected plane graph, then show that | V | | E | | R | 2 .
(b)
Prove that every simple planar graph is 5-colorable. SECTION B — (5 × 5 = 25 marks) Answer any FIVE questions.
6.
Show that
7.
P
Q R Q R P R R .
Show that R P Q is a valid conclusion from the premises P Q , Q R , P M and 2
M.
(DMCS 04)
8.
Show that
A B A ~ B B ~ A A B . 9.
Find the POLISH notation of the infix expression
a b c d /e h. 10.
Show that ( a b) a b and a b a b .
11.
In any Boolean algebra, show that ( a b)( a c ) ac a b ac a b bc .
12.
Define isomorphism of graphs. Give two graphs which are isomorphic.
13.
Find the chromatic number of the ‘wheel’ graph. SECTION C — (5 × 1 = 5 marks) Answer ALL questions.
14.
Define free and bound variable.
15.
What is Hasse diagram?
16.
Define partially ordered set.
17.
Define bipartite graph.
18.
Define cut set. ––––––––––––––– 3
(DMCS 04)
Wk 9
(DMCS 05) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. Computer Science Paper V — SOFTWARE ENGINEERING Time : Three hours
Maximum : 75 marks
SECTION A — (3 15 = 45 marks) Answer any THREE of the following. 1.
Discuss the following process models. (a)
RAD
(b)
Prototyping.
2.
Explain how do you create (a) Data flow model (b) Control flow model.
3.
What are golden rules of interface design? Elaborate each of them.
4.
Explain briefly about different software quality attributes.
5.
Explain Block-Box testing in detail.
Wk 9
SECTION B — (5 5 = 25 marks) Answer any FIVE of the following. 6.
Discuss about various characteristics of software.
7.
Briefly explain about the metrics for software quality.
8.
Explain the software quality assurance activities.
9.
What are the elements of analysis model? Explain them.
10.
Explain about cohesion and coupling.
11.
Explain architectural design using context diagram write about different parts used in the diagrams.
12.
Explain the interface design evaluation cycle with the help of a diagram.
13.
Discuss various debugging strategies. SECTION C — (5 1 = 5 marks) Answer ALL the questions.
14.
What is software myth?
15.
What are the phases of waterfall model?
16.
What is modularity? 2
(DMCS 05)
Wk 9
17.
What is validation?
18.
What is performance testing? ——————
3
(DMCS 05)
(DMCS 06) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. Computer Science Paper VI — DISTRIBUTED OPERATING SYSTEM Time : Three hours
Maximum : 75 marks
SECTION A — (3 × 15 = 45 marks) Answer any THREE questions. 1.
Explain Hardware and Software concepts.
(15)
2.
(a)
Explain Layered protocols.
(10)
(b)
What do you mean by Remote Procedure Cell? (5)
3.
Explain Deadlocks in Distributed Systems.
4.
(a)
Explain Scheduling in Distributed Systems. (10)
(b)
Explain processor allocation.
5.
(15)
(5)
Explain Distributed File System Implementation.
SECTION B — (5 × 5 = 25 marks) Answer any FIVE questions. 6.
Explain the goals of Distributed Systems.
7.
Explain Asynchronous Transfer Mode Networks.
8.
Explain Election algorithms.
9.
Explain clock synchronozation.
10.
Explain client-server model.
11.
Explain page-based distributed shared memory.
12.
Explain fault tolerance.
13.
What is the difference between a distributed operating system and a Network operating systems? SECTION C — (5 × 1 = 5 marks) Answer ALL questions.
14.
Define Distributed System.
15.
What is the significance of Threads? 2
(DMCS 06)
16.
Define Shared Memory.
17.
What do you mean by Mutual exclusion?
18.
What is system model?
———————
3
(DMCS 06)
(DMCS 07) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. (Examination at the end of First Year) Computer Science Paper VII — DATA BASE MANAGEMENT SYSTEMS Time : Three hours
Maximum : 75 marks
SECTION A — (3 15 = 45 marks) Answer any THREE questions. 1.
(a)
Explain database languages, database users and administrators. (9)
(b)
Explain constraints and keys in entityrelationship model. (6)
2.
Explain the overview of SQL.
3.
(a)
Explain B+ tree index files.
(8)
(b)
Explain function dependencies.
(7)
4.
(15)
Explain the following : (a)
Concurrent executions.
(5)
(b)
Serializability
(5)
(c)
Recoverability.
(5)
5.
(a)
Explain timestamp-based protocols.
(8)
(b)
Explain deadlock handling.
(7)
SECTION B — (5 5 = 25 marks) Answer any FIVE questions. 6.
Explain the design of an E-R database scheme.
7.
Explain relational model.
8.
Explain assertions and triggers.
9.
Explain file organisation.
10.
Compare static hashing and dynamic hashing.
11.
Explain Boyce-Codd normal form.
12.
How do you test for serializability?
13.
Explain multiple granularity. SECTION C — (5 1 = 5 marks) Answer ALL questions.
14.
Define database management system.
15.
Define view. 2
(DMCS 07)
16.
What do you mean by encryption?
17.
What is data dictionary?
18.
Define normal form. ——————
3
(DMCS 07)
(DMCS 08) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. (Examination at the end of First Year) Computer Science Paper VIII — THEORY OF AUTOMATA AND FORMAL LANGUAGE Time : Three hours
Maximum : 75 marks
SECTION A — (3 15 = 45 marks) Answer any THREE questions. 1.
Explain Moore machine and Mealy machine. Let M 1 Q , , , , , q0 be a Mealy machine, then prove that there is a Moore machine M 2 equivalent to M1 .
2.
State and prove the Myhill-Nerode theorem.
3.
Convert to Greibach normal form, the grammar G A1 , A2 , A3 , a, b, P , A1 where P consists of the following : A1 A2 A3 A2 A3 A1 |b A3 A1 A2 | a.
4.
Design a turning machine M to recognise the language 1n 2n3n |n 1 .
5.
Prove that the complement of a DCFL is a DCFL.
SECTION B — (5 5 = 25 marks) Answer any FIVE questions. 6.
Construct NDFSA accepting ab, ba and use it to find DFSA accepting the same set.
7.
Show that the class of regular sets is closed under subtraction.
8.
Show that language.
9.
Reduce the following grammar to GNF :
L a nb n / n 1
is not a regular
S A0 ; A 0 B; B A0 B 1 . 10.
Construct PDA grammar :
equivalent
to
the
following
S aAA , A as |bs / a . 11.
Design a Turing machine to recognize the language L 0 n1n | n 1 .
12.
Explain about Church’s hypothesis.
13.
Discuss about the universal turning machine.
2
(DMCS 08)
SECTION C — (5 1 = 5 marks) Answer ALL questions. 14.
Define finite state machine.
15.
Define DFA.
16.
Define regular grammar.
17.
What is CFL?
18.
What is DPDA? ——————
3
(DMCS 08)
(DMCS 09) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. Computer Science Paper IX — COMPUTER NETWORKS Time : Three hours
Maximum : 75 marks
SECTION A — (3 15 = 45 marks) Answer any THREE questions. 1.
Discuss the layers present in OSI model.
2.
(a)
Write short note on transmission media.
(b)
Explain how CRC encoder work.
(a)
Discuss briefly about the DNS in the
3.
Internet. (b)
Explain the network address translation.
4.
(a)
Compare OSI and TCP/IP reference models.
(b)
Discuss on the communication options in the DCS.
5.
Explain different error detection and correction techniques. SECTION B — (5 5 = 25 marks) Answer any FIVE questions.
6.
Discuss the wireless LAN MAC sublayers.
7.
Discuss about high speed network.
8.
Explain low in packet-switched networks.
9.
Discuss NAPs.
10.
Discuss the file transfer protocol.
11.
Discuss about UDP.
12.
Discuss the properties of LAN.
13.
Explain the routing principles.
2
(DMCS 09)
SECTION C — (5 1 = 5 marks) Answer ALL questions. 14.
Define a burst error.
15.
Define SMTTP and HTTP.
16.
Name the layers of OSI model.
17.
What are gate ways?
18.
State the need of an Ethernet in DCS. ————————
3
(DMCS 09)
(DMCS 10) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. Computer Science Paper X — DESIGN AND ANALYSIS OF ALGORITHMS Time : Three hours
Maximum : 75 marks
SECTION A — (3 × 15 = 45 marks) Answer any THREE of the following. 1.
2.
(a)
Write an algorithm to insert an element x from a binary search tree. What is its time complexity?
(b)
Explain the significance of 0, , performance of analysis of algorithms.
(a)
Apply merge sort algorithm on the array of element
in
a1 : 10 310,285, 179, 652, 351, 423, 861, 254, 450, 520 . (b)
Write the Prim’s minimum cost spanning tree algorithm.
3.
(a)
Write
an
algorithm
for
0/1
Knapsack
problem. (b)
Show that algorithm BFS visits all vertices reachable from v.
4.
Derive sum of subsets problem. Explain a back tracking approach for the sum of subsets problem using the state space tree corresponding to the fixed tuple size formulation.
5.
(a)
Write the FIFO branch-and-bound algorithm for job sequencing problem.
(b)
Discuss the travelling sales person problem. SECTION B — (5 × 5 = 25) Answer any FIVE of the following.
6.
Discuss about the analysis of algorithm.
7.
Write the Kruskal’s algorithm.
8.
Write an algorithm for searching a binary search tree with an example.
9.
Write the Bellman and Ford algorithm to compute shortest paths.
2
(DMCS 10)
10.
Generate the sets S i ,0 i 4 , when w1 , w2 , w3w4 = (10, 15, 6, 9) and p1 , p2 , p3 , p4
2, 5, 8, 1 . 11.
What is biconnected graph? Write an algorithm for DFS traversal.
12.
Discuss the 8-queens problem.
13.
Explain the graph coloring problem. SECTION C — (5 × 1 = 5 marks) Answer ALL questions.
14.
Define heap property.
15.
What is space complexity?
16.
What is dictionary?
17.
What is multistage graph?
18.
What is least cost search? —————————–
3
(DMCS 10)
Maximum : 75 marks
SECTION A — (3 15 = 45 marks) Answer any THREE questions. 1.
Explain in detail about the overview of Data structures.
2.
Explain circular linked list and double-linked list.
3.
Explain CPU scheduling in Multiprogramming Environment.
4.
Explain the operations on B-trees.
5.
(a)
Explain metrix representation using graphs. (8)
(b)
Explain Euler’s and Hamiltonian circuits. (7)
SECTION B — (5 5 = 25 marks) Answer any FIVE questions. 6.
Write a routine for adding an item in a double linked list.
7.
How do you represent a Queue using linked list?
8.
Explain Heshing techniques.
9.
Write a routine to merge two Binary Trees.
10.
Explain Threaded Binary Tree.
11.
Explain Quicksort with an example.
12.
Explain shortest path problem.
13.
Explain Sparse Matrix Manipulation. SECTION C — (5 1 = 5 marks) Answer ALL questions.
14.
Define dequeue.
15.
What is Height Balanced Binary tree?
16.
What are the operations performed on stack?
17.
Define Forest.
18.
Define minimum spanning tree. ———————––– 2
(DMCS 01)
(DMCS 02) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. (Examination at the end of First Year) Computer Science Paper II — OBJECT ORIENTED PROGRAMMING Time : Three hours
Maximum : 75 marks
SECTION A — (3 × 15 = 45 marks) Answer any THREE questions. 1.
Explain with suitable example about various flow control statements in C++.
2.
Define constructor. Explain different types of constructors.
3.
What is operator overloading? Write a program to demonstrate ( ) operator overloading.
4.
Write about streams and describe stream classes hierarchy.
5.
Briefly explain about try and catch blocks. How can you handle multiple catch blocks?
in
detail
about
SECTION B — (5 × 5 = 25 marks) Answer any FIVE questions. 6.
Discuss about different casting operators in C++.
7.
Write a note on pointers and arrays.
8.
Explain about call-by-value and call-by-reference.
9.
Explain about information hiding.
10.
Write about function template.
11.
Define hierarchical inheritance and give an example.
12.
Explain briefly about writing data to a file and reading a file.
13.
Discuss about pure-virtual function. SECTION C — (5 × 1 = 5 marks) Answer ALL questions.
14.
Define void pointer.
15.
What is in-line function?
16.
Define friend class.
17.
Define polymorphism.
18.
What is template? ––––––––––––––– 2
(DMCS 02)
(DMCS 03) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. (Examination at the end of First Year) Computer Science Paper III — COMPUTER ORGANIZATION Time : Three hours
Maximum : 75 marks
SECTION A — (3 15 = 45 marks) Answer any THREE questions. 1.
(a) (b)
2.
(a) (b)
Explain with suitable sketch decoder with 3 inputs. (8) Explain the programmable logic array. (7) Explain the types of registers with suitable diagrams. (8) Simplify the following expression
A Y (W X Y Z )Z . 3.
Explain : (a) Bus and memory transfer (b) Instruction cycle (c) Input output interface.
(7)
4.
5.
(a)
Explain the design issues and data transfer in DMA.
(b)
Explain the design and implementation of hardwired control unit.
(a)
Explain the synchronous and asynchronous date transfer.
(b)
Explain auxiliary memory and associative memory. SECTION B — (5 5 = 25 marks) Answer any FIVE questions.
6.
What is register transfer language?
7.
What is timing and control?
8.
What are the types of ROM?
9.
What is address sequencing?
10.
What are the floating point arithmetic operations?
11.
What is instruction format and explain the types of IF?
12.
Explain the physical characteristics of a magnetic disk.
13.
Explain the riple counter with diagram. 2
(DMCS 03)
SECTION C — (5 1 = 5 marks) Answer ALL questions. 14.
What is adder?
15.
What is a binary counter?
16.
What are the computer instructions?
17.
What is decimal arithmetic unit?
18.
What are the modes of transfer?
—————————
3
(DMCS 03)
(DMCS 04) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. (Examination at the end of First Year) Computer Science Paper IV — DISCRETE MATHEMATICAL STRUCTURES Time : Three hours
Maximum : 75 marks
SECTION A — (3 × 15 = 45 marks) Answer any THREE of the following. 1.
(a)
Construct truth table of the formula
P (b)
Q
R
P Q P R
Obtain the principal conjunctive normal form of
2.
P
Q
P R.
(a)
Show that S R is tautologically implied by
(b)
Show that
P Q P
R Q S .
x P ( x ) Q( x ) x P ( x ) ( x ) Q( x ) .
3.
(a)
Show that
n B Ai i 1
(b)
n
B A . i
i 1
Show that the function f ( x, y ) x y is
primitive recursive. 4.
(a)
For any commutative monoid ( M , ) , show that the set of idempotent elements of M forms a submonoid.
5.
(b)
Show that every distributive lattice is modular, but not conversely.
(a)
If G is a connected plane graph, then show that | V | | E | | R | 2 .
(b)
Prove that every simple planar graph is 5-colorable. SECTION B — (5 × 5 = 25 marks) Answer any FIVE questions.
6.
Show that
7.
P
Q R Q R P R R .
Show that R P Q is a valid conclusion from the premises P Q , Q R , P M and 2
M.
(DMCS 04)
8.
Show that
A B A ~ B B ~ A A B . 9.
Find the POLISH notation of the infix expression
a b c d /e h. 10.
Show that ( a b) a b and a b a b .
11.
In any Boolean algebra, show that ( a b)( a c ) ac a b ac a b bc .
12.
Define isomorphism of graphs. Give two graphs which are isomorphic.
13.
Find the chromatic number of the ‘wheel’ graph. SECTION C — (5 × 1 = 5 marks) Answer ALL questions.
14.
Define free and bound variable.
15.
What is Hasse diagram?
16.
Define partially ordered set.
17.
Define bipartite graph.
18.
Define cut set. ––––––––––––––– 3
(DMCS 04)
Wk 9
(DMCS 05) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. Computer Science Paper V — SOFTWARE ENGINEERING Time : Three hours
Maximum : 75 marks
SECTION A — (3 15 = 45 marks) Answer any THREE of the following. 1.
Discuss the following process models. (a)
RAD
(b)
Prototyping.
2.
Explain how do you create (a) Data flow model (b) Control flow model.
3.
What are golden rules of interface design? Elaborate each of them.
4.
Explain briefly about different software quality attributes.
5.
Explain Block-Box testing in detail.
Wk 9
SECTION B — (5 5 = 25 marks) Answer any FIVE of the following. 6.
Discuss about various characteristics of software.
7.
Briefly explain about the metrics for software quality.
8.
Explain the software quality assurance activities.
9.
What are the elements of analysis model? Explain them.
10.
Explain about cohesion and coupling.
11.
Explain architectural design using context diagram write about different parts used in the diagrams.
12.
Explain the interface design evaluation cycle with the help of a diagram.
13.
Discuss various debugging strategies. SECTION C — (5 1 = 5 marks) Answer ALL the questions.
14.
What is software myth?
15.
What are the phases of waterfall model?
16.
What is modularity? 2
(DMCS 05)
Wk 9
17.
What is validation?
18.
What is performance testing? ——————
3
(DMCS 05)
(DMCS 06) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. Computer Science Paper VI — DISTRIBUTED OPERATING SYSTEM Time : Three hours
Maximum : 75 marks
SECTION A — (3 × 15 = 45 marks) Answer any THREE questions. 1.
Explain Hardware and Software concepts.
(15)
2.
(a)
Explain Layered protocols.
(10)
(b)
What do you mean by Remote Procedure Cell? (5)
3.
Explain Deadlocks in Distributed Systems.
4.
(a)
Explain Scheduling in Distributed Systems. (10)
(b)
Explain processor allocation.
5.
(15)
(5)
Explain Distributed File System Implementation.
SECTION B — (5 × 5 = 25 marks) Answer any FIVE questions. 6.
Explain the goals of Distributed Systems.
7.
Explain Asynchronous Transfer Mode Networks.
8.
Explain Election algorithms.
9.
Explain clock synchronozation.
10.
Explain client-server model.
11.
Explain page-based distributed shared memory.
12.
Explain fault tolerance.
13.
What is the difference between a distributed operating system and a Network operating systems? SECTION C — (5 × 1 = 5 marks) Answer ALL questions.
14.
Define Distributed System.
15.
What is the significance of Threads? 2
(DMCS 06)
16.
Define Shared Memory.
17.
What do you mean by Mutual exclusion?
18.
What is system model?
———————
3
(DMCS 06)
(DMCS 07) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. (Examination at the end of First Year) Computer Science Paper VII — DATA BASE MANAGEMENT SYSTEMS Time : Three hours
Maximum : 75 marks
SECTION A — (3 15 = 45 marks) Answer any THREE questions. 1.
(a)
Explain database languages, database users and administrators. (9)
(b)
Explain constraints and keys in entityrelationship model. (6)
2.
Explain the overview of SQL.
3.
(a)
Explain B+ tree index files.
(8)
(b)
Explain function dependencies.
(7)
4.
(15)
Explain the following : (a)
Concurrent executions.
(5)
(b)
Serializability
(5)
(c)
Recoverability.
(5)
5.
(a)
Explain timestamp-based protocols.
(8)
(b)
Explain deadlock handling.
(7)
SECTION B — (5 5 = 25 marks) Answer any FIVE questions. 6.
Explain the design of an E-R database scheme.
7.
Explain relational model.
8.
Explain assertions and triggers.
9.
Explain file organisation.
10.
Compare static hashing and dynamic hashing.
11.
Explain Boyce-Codd normal form.
12.
How do you test for serializability?
13.
Explain multiple granularity. SECTION C — (5 1 = 5 marks) Answer ALL questions.
14.
Define database management system.
15.
Define view. 2
(DMCS 07)
16.
What do you mean by encryption?
17.
What is data dictionary?
18.
Define normal form. ——————
3
(DMCS 07)
(DMCS 08) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. (Examination at the end of First Year) Computer Science Paper VIII — THEORY OF AUTOMATA AND FORMAL LANGUAGE Time : Three hours
Maximum : 75 marks
SECTION A — (3 15 = 45 marks) Answer any THREE questions. 1.
Explain Moore machine and Mealy machine. Let M 1 Q , , , , , q0 be a Mealy machine, then prove that there is a Moore machine M 2 equivalent to M1 .
2.
State and prove the Myhill-Nerode theorem.
3.
Convert to Greibach normal form, the grammar G A1 , A2 , A3 , a, b, P , A1 where P consists of the following : A1 A2 A3 A2 A3 A1 |b A3 A1 A2 | a.
4.
Design a turning machine M to recognise the language 1n 2n3n |n 1 .
5.
Prove that the complement of a DCFL is a DCFL.
SECTION B — (5 5 = 25 marks) Answer any FIVE questions. 6.
Construct NDFSA accepting ab, ba and use it to find DFSA accepting the same set.
7.
Show that the class of regular sets is closed under subtraction.
8.
Show that language.
9.
Reduce the following grammar to GNF :
L a nb n / n 1
is not a regular
S A0 ; A 0 B; B A0 B 1 . 10.
Construct PDA grammar :
equivalent
to
the
following
S aAA , A as |bs / a . 11.
Design a Turing machine to recognize the language L 0 n1n | n 1 .
12.
Explain about Church’s hypothesis.
13.
Discuss about the universal turning machine.
2
(DMCS 08)
SECTION C — (5 1 = 5 marks) Answer ALL questions. 14.
Define finite state machine.
15.
Define DFA.
16.
Define regular grammar.
17.
What is CFL?
18.
What is DPDA? ——————
3
(DMCS 08)
(DMCS 09) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. Computer Science Paper IX — COMPUTER NETWORKS Time : Three hours
Maximum : 75 marks
SECTION A — (3 15 = 45 marks) Answer any THREE questions. 1.
Discuss the layers present in OSI model.
2.
(a)
Write short note on transmission media.
(b)
Explain how CRC encoder work.
(a)
Discuss briefly about the DNS in the
3.
Internet. (b)
Explain the network address translation.
4.
(a)
Compare OSI and TCP/IP reference models.
(b)
Discuss on the communication options in the DCS.
5.
Explain different error detection and correction techniques. SECTION B — (5 5 = 25 marks) Answer any FIVE questions.
6.
Discuss the wireless LAN MAC sublayers.
7.
Discuss about high speed network.
8.
Explain low in packet-switched networks.
9.
Discuss NAPs.
10.
Discuss the file transfer protocol.
11.
Discuss about UDP.
12.
Discuss the properties of LAN.
13.
Explain the routing principles.
2
(DMCS 09)
SECTION C — (5 1 = 5 marks) Answer ALL questions. 14.
Define a burst error.
15.
Define SMTTP and HTTP.
16.
Name the layers of OSI model.
17.
What are gate ways?
18.
State the need of an Ethernet in DCS. ————————
3
(DMCS 09)
(DMCS 10) M.Sc. (Previous) DEGREE EXAMINATION, DECEMBER 2010. Computer Science Paper X — DESIGN AND ANALYSIS OF ALGORITHMS Time : Three hours
Maximum : 75 marks
SECTION A — (3 × 15 = 45 marks) Answer any THREE of the following. 1.
2.
(a)
Write an algorithm to insert an element x from a binary search tree. What is its time complexity?
(b)
Explain the significance of 0, , performance of analysis of algorithms.
(a)
Apply merge sort algorithm on the array of element
in
a1 : 10 310,285, 179, 652, 351, 423, 861, 254, 450, 520 . (b)
Write the Prim’s minimum cost spanning tree algorithm.
3.
(a)
Write
an
algorithm
for
0/1
Knapsack
problem. (b)
Show that algorithm BFS visits all vertices reachable from v.
4.
Derive sum of subsets problem. Explain a back tracking approach for the sum of subsets problem using the state space tree corresponding to the fixed tuple size formulation.
5.
(a)
Write the FIFO branch-and-bound algorithm for job sequencing problem.
(b)
Discuss the travelling sales person problem. SECTION B — (5 × 5 = 25) Answer any FIVE of the following.
6.
Discuss about the analysis of algorithm.
7.
Write the Kruskal’s algorithm.
8.
Write an algorithm for searching a binary search tree with an example.
9.
Write the Bellman and Ford algorithm to compute shortest paths.
2
(DMCS 10)
10.
Generate the sets S i ,0 i 4 , when w1 , w2 , w3w4 = (10, 15, 6, 9) and p1 , p2 , p3 , p4
2, 5, 8, 1 . 11.
What is biconnected graph? Write an algorithm for DFS traversal.
12.
Discuss the 8-queens problem.
13.
Explain the graph coloring problem. SECTION C — (5 × 1 = 5 marks) Answer ALL questions.
14.
Define heap property.
15.
What is space complexity?
16.
What is dictionary?
17.
What is multistage graph?
18.
What is least cost search? —————————–
3
(DMCS 10)
Related Documents
2010
May 2020 35
2010
May 2020 34
2010
June 2020 18
2010
June 2020 20
2010
June 2020 26
2010
August 2019 42More Documents from "Aishila Cerys Dahlia"
2010 Dec.pdf
August 2019 32
Legal Entity Identifier
August 2019 30
Marketing Research System
August 2019 38
Quizz
November 2019 23
Mcq Book It-sm-1 By Saket Ghiria.pdf
May 2020 13