Accounting and Financial Management (3) Analog and Digital Communication (2) Artificial Intelligence (2) BE(Civil) (2) BE(CSE) (83) BE(ECE) (11) BE(Mech) (10) Business Processes (3) C# and .NET Framework (2) Communication Skills (1) Compiler Design (1) COMPONENT BASED TECHNOLOGY (1) COMPUTER ARCHITECTURE (1) COMPUTER GRAPHICS and MULTIMEDIA SYSTEMS (6) COMPUTER INTEGRATED MANUFACTURING (1) Computer Networks (9) Computer Organization (2) Computer Programming (1) Consumer Behaviour (1) Control Systems (1) Cryptography and Network Security (3) Datastructures and Algorithms (10) Datawarehousing and Mining (1) DBMS (5) DESIGN AND ANALYSIS OF ALGORITHMS (9) DESIGN OF MACHINE ELEMENTS (1) DIGITAL PRINCIPLES AND SYSTEMS DESIGN (3) Discrete Mathematics (1) DISTRIBUTED COMPUTING (2) DSP (8) DYNAMICS OF MACHINERY (2) Economic Foundations (1) ELECTRICAL ENGINEERING (1) ELECTRICAL ENGINEERING AND CONTROL SYSTEMS (1) Electromagnetic Fields (3) ELECTRONIC CIRCUITS (1) ELECTRONIC COMMERCE (4) ELECTRONIC DEVICES AND CIRCUITS (1) EMBEDDED SYSTEMS (1) FUNDAMENTALS OF COMPUTING (2) Graphics and Multimedia (3) HEAT AND MASS TRANSFER (1) HUMAN RESOURCE MANAGEMENT (1) Internet Programming (9) INTRODUCTION TO FINITE ELEMENT ANALYSIS (1) Legal Aspects of Business (1) MANAGEMENT INFORMATION SYSTEMS (1) Marketing Management (1) MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE (4) MATHEMATICS - I (1) MBA (9) MCA (83) MCA QUESTION BANK (2) MECHATRONICS (1) MicroProcessor and Controllers (4) MICROPROCESSORS AND APPLICATIONS (5) MIDDLE WARE TECHNOLOGIES (3) MOBILE COMPUTING (5) NETWORK PROGRAMMING (1) NUMERICAL METHODS (1) OBJECT ORIENTED ANALYSIS AND DESIGN (5) Object Oriented Programming (18) Operating System (2) OPERATING SYSTEMS (9) Organizational Behaviour (2) POWER ELECTRONICS (1) Principles of Management (8) PROBABILITY AND QUEUEING THEORY (2) Probability and Statistics (1) PROBLEM SOLVING AND PROGRAMMING (2) PROCESS PLANNING AND COST ESTIMATION (1) PROFESSIONAL ETHICS AND HUMAN VALUES (1) RANDOM PROCESSES (1) RESOURCE MANAGEMENT TECHNIQUES (2) ROBOTICS (1) Security analysis (1) Service Marketing (1) SIGNALS AND SYSTEMS (1) Software Engineering (8) SOFTWARE PROJECT MANAGEMENT (4) SOFTWARE QUALITY MANAGEMENT (2) System Software (2) TCP/IP PROTOCOL SUITE (3) Theory of Computation (4) Total Quality Management (2) UNIX AND NETWORK PROGRAMMING (4) Visual Programming (2) WEB GRAPHICS (2) WEB TECHNOLOGY (2) XML AND WEB SERVICES (4)

Friday, July 4, 2008


PART A-(10 X 2=20 marks)

1.When will you say an algorithm efficient? Give the notations for time complexity.

2.What is a ‘top-down’ design? Is ‘C’ language a top down design? Justify your answer.

3.Why is linked list used for polynomial arithmetic?

4.Write the role of stack in function call.

5.What is the minimum number of nodes in an AVL tree of height 5?

6.What is the use of sentinel value in binary heap?

7.Which is the best way of choosing the pivot element in quick sort?

8.Merge sort is better than insertion sort. Why?

9.Define a graph. How it differs from tree?

10.What is minimum spanning tree? Name any two algorithms used to find MST.

PART B-(5 X 16=80 marks)

11.(a).(i).Given two lists L1 and L2, write the routines to compute L1 n L2 using basic operations.

(ii).Write the routines for inserting and deleting elements from a queue. Check for the conditions Q-empty and Q-full.


11.(b).(i).How would you implement a stack of queues? Write routines for creation and inserting of elements into it.

(ii).Write routines to insert heterogeneous data into the list.

12.(a).(i).Write the routines to insert and remove a node from Binary Search Tree.

(ii).A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a binary tree.


12.(b).(i).Show the resulting of inserting 2,1,4,5,9,3,6,7 into an empty AVL tree.

(ii).Write the procedure to implement single and double rotations while inserting nodes in an AVL tree.

13.(a).Explain with suitable examples the basic heap operations and algorithms for the same.


13.(b).How will you resolve the collisions, while inserting elements into the hash table using separate chaining and linear probing? Write the routines for inserting, searching and removing elements from the hash table using the above mentioned techniques.

14.(a).(i).Write the routine for sorting n elements in increasing order using heap sort.

(ii).Sort 3,1,4,1,5,9,2,6 in decreasing order using heap sort.


14.(b).(i).Explain with example about the insertion sort.

(ii).What is external sorting? Discuss the algorithms with proper examples.

15.(a).(i).Discuss and write the program to perform topological sorting.

(ii).What is single source shortest path problem? Discuss Dijikstra’s single source shortest path algorithm with an example.


15.(b).(i).Write an algorithm to find the minimum cost spanning tree of an undirected, weighted graph.

(ii).Find the MST for the following graph.

No comments:

Post a Comment