ALCCS -
NEW SCHEME

**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 (7
**× **4 = 28)**

** **a.** **What is the condition that a
circular queue is full if the queue is implemented using arrays?

** **b.** **Explain boundary tag method.

c. Discuss algorithm for deletion of a node
having two children from binary search tree.

d. An array is defined as A[2:8, -4:1, 6:10]
requires 4 words per memory cell. Find the location of the [5, -1, 8] if the
array is implemented in row major order. The base address is given as 200.

e. Define B tree, B+ Tree. Among the two which one is better and why?

f. What do you mean by complete threaded binary
tree? How null pointers are replaced in it?

g.
Explain heap sorting algorithm.

**Q.2 **a.** **Define binary tree. Prove that maximum
number of nodes in a binary tree of height *h*
can be 2* ^{h }*- 1

** **

b. What is spanning tree? What is a minimum spanning tree? Work out the
Kruskal’s algorithm to find the minimum spanning tree of the following graph: **(8+10)**

** **** **

** **

**Q.3** a. Write an algorithm for quick sort. Compare its
complexities for worst case, average case and best case. Sort the following
using quick sort

5, 4, 2, 8, 7, 9, 1, 3

b. Discuss different ways of collision resolution
with open addressing. **(10+8)**

** Q.4 **a. What is priority queue? How priority queue can be represented in
memory? ** **

b. Convert the following infix expression into
postfix using stack:

** **A + ( B * C - ( D / E ↑ F) * G) * H

** **c. Write
an algorithm to evaluate a postfix expression using stack. Explain the steps of
the algorithm. **(6+4+8)**

**Q.5** a. What is AVL tree? Why height balancing is
required? For the given sequence, create AVL tree (show each step with all
rotations)

** **H, I, J, B, A, E, C, F, D

b. Explain single source shortest path algorithm.
Find the shortest path for the following graph taking ‘v_{0}’ as
starting node. **(9+9)**

** **

** **

** **

**Q.6** a. What do you mean by buddy system memory
allocator? What are its drawbacks?

b. Explain first fit and best fit approaches of
memory management. Write an algorithm for best fit approach.

c. What is scheduling problem?

d. Write a program to reverse a singly linked
list without using any more memory. **(5+5+4+4 = 18)**

**Q.7** a. What do you mean by Huffman trees? Write the algorithm for the same. Draw
Huffman tree for the set of weights {1, 2, 3, 3, 4}

** **b. Explain in detail depth first traversal
algorithm of a graph. **(10+8)**