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. Differentiate between best, average, and worst case complexities.
b. Derive the equation for computing the address of the memory location of an element stored in a twodimensional array.
c. How does doubly linked list differ from singly linked list?
d. Convert the following infix expression into postfix expression
A+B*CD/A*F
e. Differentiate between Stack and Queue data structure.
f. Compute minimum height of binary tree of n nodes
g. Make a complete graph of 4 vertices and compute adjacency matrix for it. (7 4)
Q.2 a. Differentiate between bigO, Ω, and θ notations used to specify algorithmic complexity.
b. Obtain the values of c and n_{0} for the following.
c. Show which of the following function grows faster? Also define the order.
(6+6+6)
Q.3 a. Assume that a lower triangular matrix is stored in a linear array in lexicographical order. If is stored in , where is stored in array B for n=100?
b. What are the advantages of circular linked list over linked list?
c. Write an algorithm for binary search method. Also derive its time complexity. (6+6+6)
Q.4 a. Show the outcome of different passes for sorting the following sequence of data using quick sort algorithm.
25, 57, 48, 37, 12, 92, 86, 33
b. Show the step to evaluate the following expression using a stack. Also compute the final value for A=8, B=2, C=3, D=1,E=4.
c. Construct AVL tree for the following set of data for the months of year based on their lexicographical order. Initial order of the month is as occur from January to December. (6+6+6)
Q.5 a. In a circular queue show the conditions that differentiate between empty queue and full queue. Also explain the disadvantages of implementing queue (non circular) using array.
b. Construct a binary tree for the following preorder and inorder traversal sequences.
Preorder: ABCDEFGHIJKLMPRQNO
Inorder: BDEFCAIJKHGRPQMNOL
c. Delete 14 from the following BTree of order 5. Show all the steps of deletion. In the figure, children of the node(100, 120) are not shown since it does not affect the deletion. (6+6+6)

Q.6 a. What is linked representation of a graph? Explain with the help of an example. Also write its advantages over other representations of graph.
b. Define a connected graph. For a connected graph of n vertices, how many minimum and how many maximum edges should be in the graph? Prove it.
c. Write Kruskal algorithm to find a minimum spanning tree of a Graph. (6+6+6)
Q.7 a. What is Garbage? Write advantages of bestfit and worstfit memory allocation methods.
b. Write an algorithm that reverses a given string of length n.
c. Write an algorithm that adds two polynomials of degree n and m. (6+6+6)