TRIBHUVAN UNIVERSITY
INSTITUTE OF SCIENCE AND TECHNOLOGY
2082 B.S.
Candidates are required to give their answers in their own words as far as practicable.
Group A
Long Answer QuestionsAttempt any Two questions.
- 1Distinguish between data type and abstract data type. List any three characteristics of algorithm. Evaluate the postfix expression $33+2^{*}40-$, using stack.
- 2Define height, depth and level of the tree. Find the minimum spanning tree of the following weighted graph using Kruskal and Prims algorithm. [diagram/image to be added manually]
- 3Define queue as ADT and discuss about primitive operations in queue. Trace the output generated by following recursive function for the statement TOH(4,1,3). ``` TOH(n,s,d) { if (n==1) { printf(" move the top disk from rod %d to rod %d",s,d) } else { TOH (n-1,s,6-s-d) printf("move the top disk from rod %d to rod %d",s,d) TOH (n-1, 6-s-d, d) } } ```
Group B
Short Answer QuestionsAttempt any Eight questions.
- 4Why do we need algorithms for searching? Trace the binary search operation for the key = 6, in the set {3, 6, 8, 12, 67, 89, 90, 100}
- 5How do you implement single linked list using stack? Explain.
- 6Trace the merge sort algorithm for the input {8, 7, -4, 19, 3, 45, 12}.
- 7Explain about any three hash collision resolution techniques.
- 8Describe the process of deleting the node at start, end and specified position of singly linked list.
- 9Write the algorithm of Quick sort with its efficiency analysis.
- 10Why do we always prefer the worst case for algorithm analysis? Describe the insertion and deletion operation in BST.
- 11Define overflow and underflow. Discuss the advantages and limitations of circular queue.
- 12What are the advantages of circular queue over linear queue? Sort the array {4, 7, 3, 2, 1} using insertion sort.