1
LOYOLA COLLEGE (AUTONOMOUS), CHENNAI 600 034
M.C.A.DEGREE EXAMINATION COMPUTER APPLICATIONS
FIRSTSEMESTER APRIL 2018
17PCA1MC04- DATA STRUCTURES AND ALGORITHMS
Date: 30-04-2018 Dept. No. Max. 100 Marks
Time: 09:00-12:00
PART A
Answer ALL Questions (10 X 2 20)
1. Define queue.
2. Change the following from infix to prefix and postfix expressions:
A C D B
3. Define heap Tree
4. What is open addressing?
5. What is the degree of a Graph?
6. What is completed graph?
7. Define Knapsack Problem.
8. What is the time complexity of Merge sort?
9. Define Bellman's Principle of Optimality.
10. What is branch and bound?
PART B
Answer ALL Questions X 8 40)
11a. Write down the applications of linked list.

b. What are the abstract data types? Justify with an example.
12 a. Explain Polynomial addition using linked list

b. Explain bubble sort with an example.
13 a. Write Prim's algorithm to find a minimum spanning tree. Illustrate the algorithm with an
example.

b. Explain Warshall's algorithm with an example
14 a. Explain the role of Asymptotic notations in analysis of algorithms.

b. Explain Merge sort with an example.
15 a. Explain the role of multi stage graphs in problem solving.

b. Describe the algorithm to solve 8-Queen Problem.
2
PART C
Answer any TWO Questions x 20 40)
16 Explain the basic operations on Arrays with examples.
ii) Explain binary search tress with the operations and 'search'.
17 Explain Dijkstra's Algorithm with an example .
ii) How Strassen's matrix multiplication improves computational efficiency of sorting.
Explain with example.
18 How can the Traveling Salesman problem be solved using branch and bound method?
Explain.
ii) Explain quick sort with an example.