June 2010 paper 3

Section-A(Elective)-40 marks
TOC-
Q.1
a)Design a TM for a^nb^n c^n.
b)NFA for
    -strings (0,1) with 1 at even places
    -with substrings 000 and 010

Q.2.What is the difference between bit rate and baud rate?For manchester encoding what is the baud rate for 1 mbps?
Given a complete binary tree its inorder is given ACGHBDE.., Find the preorder and postorder.
  OR
Given the relations and Functional dependency,if its decomposed into other relations.Is the dependency preserved and is it lossless?
Given the memory size what is first fit,best fit and worst fit

Section-b(Elective)-Essay Type
Section-C
 Each question carries 10 marks-

 Q.1.What is the role of entities in XML?What are the different types of entities in XML?

 Answer: Entities are variables used to define shortcuts to standard text or special characters.They can be thought of as macros or aliases. 
When you use the entity name elsewhere within a DTD, or in an XML document, language parsers replace the name with the corresponding characters.This helps you avoid typing name everytime.
There are three different types  of entities in XML-
a)Internal Entity:-
   <!Entity UGC "University grant commission">
  The replacement text is stored in the declaration itself.To use this entity you insert an entity reference in your document "&UGC;"
b)External entity:-
   <!Entity course SYSTEM "/standard/course.xml">
   when the replacement text is long then it is placed in some other file.External entities allow an XML document to refer to an external file.They contain either text or binary data(as images).
c)Parameter entity:-is used for shortcuts within the DTD
   <!Entity %name "replacement text">
these entities are identified by placing % instead of &,also for refering " % "is used.
eg
<!ENTITY book "UGC NET: BPB, &#xA9; 1947 %pub; &rights;">

Q.2.Write the function of 8:1 multiplexer for (0,3,4,6,8,9,12,14)
Q.3.Draw a conceptual dependency graph for the statement "Smoking kills...."
Q.4.On what basis does the window make a selection whether a line will be clipped,displayed or discarded.
given the window has bottom  right at (200,50) and top left given and the line points given?
Q.5.For a college an attendence sheet has to be maintained.Which data structure will you use?How would your choice change in the following conditions-
a)the students are 50 to 1000 only in number
b)the students are 10,000 to 50,000 and data is to be maintained centrally.
c)the students are 10,000 to 50,000 and data is to be distributed.
Q.6.Explain with example that Quick Sort is divide and conquer.
Q.7.What are the factors that determine the cost of software maintenance.

Section-D

Given some paragraph-
a)Draw Use case diagram
b)draw Class diagram
c)draw Sequence Diagram
d)draw state diagram
e)draw activity diagram