ALCCS

** **

**NOTE: **

·
**Question
1 is compulsory and carries 28 marks. Answer any FOUR questions from the rest.
Marks are indicated against each question.**

·
**Parts
of a question should be answered at the same place.**

** **

** **

**Q.1 **a.** **Compute the average case
complexity of linear search algorithm.

** **b.** **Derive the equation for
computing the address of the memory location of an element stored in n-dimensional
array.

c. Write the advantages of doubly linked list over singly linked list.

d. Convert the following infix expression into postfix expression

A*B+C/D-A*F

e. Write binary search algorithm.

f. In array implementation of Queue without shifting the element of queue after deletion of an element from the queue. Explain the mechanism used to clearly distinguish between queue full and queue empty?

g.
Define minimum spanning tree and also explain it with the help of an example. **(7
**** 4)**

**Q.2 **a.** **In algorithmic
complexity show that the lower order terms and constant do not matter and are
ignored.

** **

b. Work out the time complexity of merge sort in the worst case.

c. Write algorithm for Push and Pop operations of a stack implemented using linked list.

**(6+6+6)**

**Q.3** a. A
Binary search tree contains integers in each node. Write a function which
examines a BST and returns 1 if a target value is found on the BST, else it
returns 0.

b. Explain the basic principle of
dynamic programming using a simple example. **(10+8)**

** **

** Q.4 **a. Write algorithm for
addition of two polynomial represented by linked list.** **

** **b. Show the outcome of
different passes for sorting the following sequence of data using quick sort
algorithm. ** **

8, 11, 3, 15, 6, 9, 12, 39

Choose the first element as pivot.

c. Construct
AVL tree for the days of week on their lexicographical order. Initial order of
the days is as they occur in a week from Sunday to Saturday. **(6+6+6)**

**Q.5** a. In a
circular queue show the conditions that differentiate between empty queue and
full queue. Also explain disadvantages of implementing queue (non circular)
using array.

** **

b. Construct a binary tree for the following postorder and inorder traversal sequences.

Postorder: GHDIEBFCA

Inorder: GDHBEIACF

c. Construct a B tree of order 5 for the following sequence of data. Also show the tree after deletion of 106 from the tree constructed.

87, 140, 23, 62, 74, 90, 100, 106, 152, 186, 194, 102 **(6+6+6)**

**Q.6** a. What
is adjacency list representation of a graph? Explain with the help of an
example. Also write its advantages over adjacency matrix representations of
graph.

b. Given
the following graph apply Depth First search and list the vertices in the order
they would be visited. If nodes at same level, then do alphabetical ordering.
Start with node K.

** **

** **c. Write Dijkstra’s algorithm
to find shortest path in a Graph. **(6+6+6)**

**Q.7** a. What is threaded
binary tree? Write its advantages over binary tree.

b. Write a recursive algorithm that determine the height of a binary tree.

** **

** **

** **c. Write a function which
deletes the last element of a singly linked list. **(6+6+6)**