4TH SEM CSE MODEL QUES

M.C.A DEGREE EXAMINATION, JUNE/JULY 2009
SECOND SEMESTER
CA5153 DESIGN AND ANALYSIS OF ALGORITHMS
(REGULATION 2007)
Time: Three hours Maximum: 100 marks
Answer all questions.

PART A – [10 X 2 = 20 marks]

1. What is amortized efficiency?
2. Write the names of the basic asymptotic efficiency classes with their growth functions.
3. Define the internal path length of an extended binary tree.
4. State the Triomino Puzzle problem.
5. What are the differences between dynamic programming and divide-and-conquer techniques?
6. Give two reasons why the memory function approach is unattractive for the problem of computing a binomial coefficient.
7. Write the differences between backtracking and branch-and-bound techniques.
8. Write the three reasons to terminate a search path at the current node in a state-space tree of a branch-and-bound algorithm.
9. What are the two types to show a decision problem is NP-Complete?
10. What is halting problem?

PART B – [5 X 16 = 80 marks]

11.(a) Briefly discuss the sequence of steps typically required in designing and analyzing an algorithm. (10)
(b) Design a recursive algorithm for computing 2n for any nonnegative integer n which is based on the formula 2n = 2n-1 + 2n-1. (6)
Or
11(ii).(a) Write a recursive algorithm for the Tower of Hanoi puzzle. Obtain the recurrence equation. (8)
(b) Solve the recurrence equation which is to be obtained the above by the method of backward substitution. (8)

12.(a) Write a Merge sort algorithm and explain with an example using divide-and-conquer technique. (8)
(b) Explain the working of binary search algorithm using divide-and-conquer with an example. (8)
Or
12(ii).(a) Write the Quick sort algorithm and illustrate the operation of the algorithm with an example. (8)
(b) Describe the Stassen’s Matrix Multiplication technique. (8)

13.(a) Write and explain the dynamic programming algorithm for computing a binomial coefficient. Obtain the time efficiency of the algorithm. (8)
(b) Explain the importance of optimal binary search tree. (8)
Or
13(ii).(a) Explain the Warshall’s algorithm for computing the transitive closure of a directed graph. (8)
(b) Design a dynamic programming algorithm and explain for finding an optimal order of multiplying n matrices. (8)

14.(a) State and explain the n-Queen problem using backtracking. (8)
(b) Apply the branch-and-bound technique in solving the Traveling Salesman Problem. (8)
Or
14(ii).(a) Illustrate the Branch-and-Bound approach of solving assignment problem. (8)
(b) Solve the following instance of the knapsack problem by the branch-and-bound algorithm, with W = 16. (8)
Item Weight Value
1 10 100
2 7 63
3 8 56
4 4 12

15.(a) Explain the procedure to solve the Traveling salesman Problem with approximation algorithms. (10)
(b) Give short notes on decision problems, un decidable problem, and NP-Complete problem. (6)
Or
15 (ii) (a) Explain how the knapsack problem is solved with approximation algorithm. (8)
(b) Apply the nearest algorithm to the instance defined by the distance matrix below. Start the algorithm at the first city, assuming that the cities are numbered from 1 to 5. (8)

microprocessor 4th sem questions

B.E DEGREE EXAMINATION, APRIL/MAY 2007

CS1304 – MICROPROCESSORS AND MICROCONTROLLERS

PART A – (10 x 2 = 20 marks)

1. How address and data lines are demultiplexed in 8085?
2. What is the function performed by SIM instruction in 8085?
3. What is pipelined architecture?
4. How the interrupts can be masked/unmasked in 8086?
5. What are the signals involved in memory bank selection in 8086
micro processor?
6. How clock signal is generated n 8086? What is the maximum internal clock
frequency of 8086?
7. What is the function of gate signal in 8254 timer?
8. Write the format of KW1 in 8259.
9. List the interrupts of 8051 micro controller.
10. What are register banks in 8051 microcontroller?

PART B – (5 x 16 = 80 marks)

11. (a) (i) Explain the various logical and arithmetic instructions available in 8085
microprocessor. (10)
(ii) Explain the function of various flags of 8085 microprocessor (6)
(Or)
(b) (i) Differentiate between I/O mapped I/O and memory mapped I/O. (6)
(ii) Write an 8085 assembly language program to convert 8 bit binary to
ASCII code. (10)

12. (a) (i) Describe the action taken by 8086 when INTR pin is activated. (6)
(ii) Write an assembly language program in 8086j to search the largest data in
an array. (10)
(Or)

(b) (i) Discuss the various addressing modes of 80896 microprocessor. (10)
(ii) Explain the following assembler directives used in 8086
(1) ASSUME
(2) EQU
(3) DW (

13. (a) (i) Explain in detail about memory access mechanism in 8086 (
(ii) Explain the function of following 8086 signals.
(1) HLDA
(2) RQ/GTO
(3) DEN
(4) ALE. (
(Or)
(b) (i) Draw and explain a block diagram showing 8086 in maximum mode
configuration. (12)
(ii) What are the advantages of the multiprocessor systems? (4)

14. (a) (i) With the help of block diagram explain the operation of USART (8251A)
(10)
(ii) Discuss the salient features of 8259 – programmable interrupt controller.
(6)
(Or)
(b) (i) Describe the various modes of operations in 8253 programmable interval
Timer. (
(ii) Explain the operation of DMA controller (8237).

15. (a) With a suitable block diagram, explain the architecture of 8051 microcontroller.
(16)
(Or)
(b) Discuss in detail about 8051 based stepper motor control along with necessary
hardware and software. (16)

2006

PART A – (10 ´ 2 = 20 marks)

1. Name the various Flag bits available in an 8085 microprocessor.
2. Give the significance of SIM and RIM instruction available in 8085.
3. What do you mean by pipelining in an 8086 processor?
4. How the 20 bit effective, address is calculated in an 8086 processor?
5. What is the purpose of CLK signal in an 8086 system?
6. What is the use of Latch signal on the AD0 – AD15 bus in an 8086 system?
7. Name the two modes used by the DMA processes to transfer data.
8. Name the six modes of operations of an 8253 programmable interval timer.
9. Differentiate a microprocessor and a microcontroller.
10. Differentiate RRA and RRCA instruction in 8051 microcontroller.

PART B – (5 ´ 16 = 80 marks)

11. (a) (i) With a neat block diagram explain the architecture of an 8085
Microprocessor? (12)
(ii) List out the Mask able and Non – Mask able interrupts available in an
8085 processor. (4)
(Or)
(b) (i) How do the instructions of 8085 is classified based on their functions
and word length? Give an example. (10)
(ii) Write an ALP to add two 8 bit numbers.

12. (a) (i) With the neat sketch explain the architecture of an 8086 processor.
(ii) Give the significance of O Flag, T Flag and I Flag, D Flag of 8086. (4)
(Or)

(b) (i) Explain in detail about the various addressing modes used in 8086
processor? Give an example. (12)
(ii) Name the various segment registers and their usage in 8086 processor. (4)

13. (a) (i) Explain the MIN/MAX mode operation of an 8086 processor. (10)
(ii) Give a note on the role of a decoder in memory interfacing with
example. (6)
(Or)
(b) (i) Explain in detail about the 8086 memory banks and the associated
signals for byte and word operations.
(ii) Give the significance of RQ/GTO and IO/M signals. (4)

14. (a) (i) With a neat sketch kand explain the operation of an Interrupt
controller(8259) (14)
(ii) What jis the use of CAS0, CAS1 and CAS2 signals?
(Or)
(b) Draw the block diagram of a DMA controller (8237) and explain its
operation.

15. (a) (i) With the help of a functional block diagram explain any one application
of 8051 microcontroller. (16)
(Or)
(b) Give the PIN details of an 8051 microcontroller and explain. (16)

dbms-4th sem previous question papers

B.E/B.Tech DEGREE EXAMINATION Nov/Dec 2007

Fifth semester

Computer Science and Engineering

CS1301 -DATABASE MANAGEMENT SYSTEMS

Answer ALL questions

PART A (10 x 2 =20 marks)

1. List any two advantages of database systems.

2. Give the reasons why null values might be introduces into the database.

3. What is static SQL? How does it differ from dynamic SQL?

4. What are the different types of integrity constraints used in designing a relational database?

5. Compare sequential access devices versus random access devices with an example.

6. What can be done to reduce the occurrences of bucket overflows in a hash file organization?

7. Give the ACID properties.

8. State the benefits of strict two-phase locking.

9. What is the need for complex data types?

10. What is data mining?

PART B (5 x 16 = 80)

11. (a) Explain the system structure of a database system with neat block diagram. (16)

(or)

(b) (i) Construct an ER-diagram for 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.

(ii) Discuss on various relational algebra operators with suitable Example.

12. (a) (i) Consider the employee database, where the primary keys are underlined.

Employee (empname, street, city)

Works (empname, companyname, salary)

Company (companyname, city)

Manages (empname, managername)

And given an expression in SQL for the following queries:

(1) Find the names of all employees who work for First Bank Corporation.

(2) Find the names, street addresses, and cities of residence of all employees who work for First Bank Corporation and earn more than 200000 per annum.

(3) Find the names of all employees in this database who live in the same city as the companies for which they work.

(4) Find the names of all the employees who earn more than every employees of Small Bank Corporation.

(ii) Discuss the strengths and weaknesses of the trigger mechanism. Compare triggers with other integrity

(or)

(b) (i) What is normalization? Explain the various normalization

techniques with suitable example. (12)

(ii) Give the comparison between BCNF and 3NF. (4)

13. (a) (i) Explain how the RAID system improves performance and reliability.

(ii) Describe the structure of B+ tree and list the characteristics of a B+ tree.

(or)

(b) (i) Explain the steps involved in processing a query.

(ii) Give the algorithm for hash join.

14. (a) (i) Describe about the testing of serializability. (6)

(ii) Discuss on two-phase locking protocol. (10)

(or)

(b) (i) Explain the differed and immediate-modification versions of the log-based recovery scheme (10)

(ii) Write the short notes on shadow paging (6)

15 (a) (i) Highlight the features of OODBMS

(ii) Write short notes on distributed databases

(or)

(b) (i) Give the structure of XML data. (4)

(ii) Explain the architecture of a typical data warehouse and describe the various components of data warehouse. (12)

B.E/B.Tech DEGREE EXAMINATION Nov/Dec 2006

Fifth semester

Computer Science and Engineering

Database Management Systems

(Regulation 2004)

Answer ALL questions

PART A (10 x 2 =20 marks)

1. Compare database systems with file systems.

2. Give the distinction between primary key, candidate key and super key.

3. Write a SQL statement to find the names and loan numbers of all customers who have a loan at Chennai branch.

4. What is multi-valued dependency?

5. Give the measures of the quality of the disk?

6. What are the two types of ordered indices?

7. List out the ACID properties.

8. What is shadow paging?

9. Compare DBMS versus object oriented DBMS.

10. What is Data warehousing?

PART B (5 x 16 = 80)

11. (a) (i) Describe the system structure of database system. (12)

(ii) List out the functions of DBA (4)

(or)

(b) (i) Illustrate the issues to be considered while developing an ER-diagram.

(ii) Consider the relational database

employee (empname, street, city)

works (empname, companyname, salary)

company (companyname, city)

manages (empname, managername).

Give an expression in the relational algebra for each request.

Find the names of all employees who work for first bank Corporation.

Find the names, street addresses and cities of residence of all employees who work for first Bank Corporation and earn more than 200000 per annum.

Find the names of all employees in this database who live in the same city as the company for which they work.

Find the names of all employees who earn more than every Employees of small Bank Corporation.

12. (a) (i) Discuss about triggers. How do triggers offer a powerful mechanism for dealing with the changes to database with suitable example. (10)

(ii) What are nested queries? Explain with example. (6)

(or)

(b) (i) What is normalization? Give the various normal forms of relational schema and define a relation which is in BCNF and explain with suitable example. (12)

(ii)Compare BCNF versus 3NF. (4)

13. (a) (i) Describe about RAID levels. (10)

13.(a)(ii) Explain why allocations of records to blocks affects database system performance significantly. (6)

(or)

(b) (i) Describe the structure of B+ tree and give the algorithm for search in the B+ tree with example. (12)

(ii) Give the comparison between ordered indexing and hashing

14. (a) (i) Explain the different forms of Serializability. (10)

(ii) What are different types of schedules are acceptable for recoverability? (6)

(or)

(b) (i) Discuss on two-phase locking protocol and timestamp-based protocol. (12)

(ii) Write short notes on log-based recovery. (4)

15. (a) (i) Discuss in detail about the object relational database and its advantages.

(ii) Illustrate the issues to implement distributed database.

(b) (i) Give the basic structure of XML and its document schema.

(ii) What are the two important classes of data mining problems?

Explain about rule discovery using those classes.

B.E/B.Tech DEGREE EXAMINATION Apr/May 2008

Fifth semester

Computer Science and Engineering

CS1301 -DATABASE MANAGEMENT SYSTEMS

(Regulation 2004)

Time: 3 hours Maximum marks: 100

Answer ALL questions

PART A (10 x 2 =20 marks)

1. Define Data independence.

2. Distinguish between primary key and candidate key

3. With an example explain a weak entity in an ER diagram.

4. With an example explain referential integrity.

5. What is domain integrity? Give example.

6. Distinguish between dense and sparse indices.

7. List the properties that must be satisfied by a transaction,

8. Define deadlock.

9. State the advantages of distributed systems.

10. What is data warehousing?

PART B (5 x 16 = 80)

11. (a) (i) Construct an ER diagram for a car insurance company that has a set of customers, each of whom owns one/more cars. Each car has associated with it zero to any number of recorded accidents. (Cool

(ii) Construct appropriate tables for the above ER diagram. (Cool

(or)

(b) (i) Define data model. Explain the different types of data models with relevant examples. (10)

(ii) Explain the role and functions of the database administrator. (6)

12 (a) (i) with relevant examples discuss the following in SQL.

(i) Data Definition Language. (4)

(ii) Data Manipulation Language (4)

(iii) Data Control Language (4)

(iv) Views (4)

(or)

(b) What is normalization? Explain normalization techniques using functional dependencies with relevant examples. (16)

13 (a) Explain following with relevant examples:

(i) B tree (5)

(ii) B+ tree (5)

(iii) Static and dynamic hashing (6)

(or)

(b) With a relevant example discuss the steps involved in processing a query. (16)

14 (a) Explain testing for serializability with respect to concurrency control schemes. How will you determine, whether a schedule is serializable or not. (16)

(or)

(b) Explain the following concurrency control:

(i) Lock based protocol (Cool

(ii) Time stamp based protocol (Cool

15 (a) State and explain the object oriented data model. Use banking application as an example. (16)

(or)

(b) Write detail notes on following:

(i) Distributed Databases (Cool

(ii) Data Mining (Cool

PART-A

1. List five reponsibilities of the DB manager.
2. Give the limitations of ER model? How do you overcome this?
3. Define query language.Give the calssification of query language.
4. Why it is necessary to decompose a relation?
5. Give any two advantages of spare index over dense dense index.
6. Name the different types of joins supported in SQL.
7. What are the types of transperencies that a distributed database must support? why?
8. What benefit is provided by strict-two phase locking? What are the disanvantages result?
9. Briefly write the overall process of dataware housing.
10. What is an active database?

PART - B
11 (a) (i) What are the types of knowledge discovered during data mining? Explain with suitable examples.
(ii) HIghlight the features of object oriented database.

OR
(b) (i) What is nested relationls? Give example.
(ii) Explain the structure of XML with suitable example.


12 (a) (i) Compare file system with database system.
(ii) Explain the architecture of DBMS.

OR
(b) (i) What are the steps involved in designing a database application? Explain with an example
(ii) List the possible types of relations that may exist between two entities. How would you realise that into tables for a binary relation?

13. (a) (i) What are the relational algebra operations supported in SQL? Write the SQL statement for each operation.
(ii) Justify the need of normalization with examples
OR
(b) (i) What is normalization? Explain 1NF,2NF,3NF and BCNF with suitable example.
(ii) What is FD? Explain the role of Fd in the process of normalization.

14.(a) (i) Explain the security features provided in commercial query languages.
(ii) What are the steps involved in query processing? How would you estimate the cost of the query?
OR
(b) (i) Explain the different properities of indexes in detail.
(ii) Explain various hashing techniques.

15.(a) (i) Explain the four important properities of transaction that a DBMS must ensure to maintain database .
(ii) What is RAID? List the different levels in RAID technology and explain its features.
OR
(b) (i) What is concurrenct control? How is it implemented in DBMS? Explain.
(ii) Explain various recovery techniques during ttansaction in detail.

PART-A

1. List five reponsibilities of the DB manager.
2. Give the limitations of ER model? How do you overcome this?
3. Define query language.Give the calssification of query language.
4. Why it is necessary to decompose a relation?
5. Give any two advantages of spare index over dense dense index.
6. Name the different types of joins supported in SQL.
7. What are the types of transperencies that a distributed database must support? why?
8. What benefit is provided by strict-two phase locking? What are the disanvantages result?
9. Briefly write the overall process of dataware housing.
10. What is an active database?

PART - B
11 (a) (i) What are the types of knowledge discovered during data mining? Explain with suitable examples.
(ii) HIghlight the features of object oriented database.

OR
(b) (i) What is nested relationls? Give example.
(ii) Explain the structure of XML with suitable example.


12 (a) (i) Compare file system with database system.
(ii) Explain the architecture of DBMS.

OR
(b) (i) What are the steps involved in designing a database application? Explain with an example
(ii) List the possible types of relations that may exist between two entities. How would you realise that into tables for a binary relation?

13. (a) (i) What are the relational algebra operations supported in SQL? Write the SQL statement for each operation.
(ii) Justify the need of normalization with examples
OR
(b) (i) What is normalization? Explain 1NF,2NF,3NF and BCNF with suitable example.
(ii) What is FD? Explain the role of Fd in the process of normalization.

14.(a) (i) Explain the security features provided in commercial query languages.
(ii) What are the steps involved in query processing? How would you estimate the cost of the query?
OR
(b) (i) Explain the different properities of indexes in detail.
(ii) Explain various hashing techniques.

15.(a) (i) Explain the four important properities of transaction that a DBMS must ensure to maintain database .
(ii) What is RAID? List the different levels in RAID technology and explain its features.
OR
(b) (i) What is concurrenct control? How is it implemented in DBMS? Explain.
(ii) Explain various recovery techniques during ttansaction in detail.