Mcs 021
Mcs 021
This assignment has 10 questions of 8 Marks each, answer all questions. Rest 20 marks are
for viva voce. You may use illustrations and diagrams to enhance the explanations. Please
go through the guidelines regarding assignments given in the Programme Guide for the
format of presentation.
Q1. Elaborate various asymptotic notations used to evaluate the efficiency of the algorithm. (8)
Q2. Write a program that accepts two polynomials as input and displays the resultant polynomial after
multiplication of input polynomials. (8)
Q3. Write a C programme to implement a doubly linked list. Also write functions to perform insertion
and deletion operations in it. (8)
Q4. What is a Circular Queue? Write an algorithm to perform insertion and deletion operation in a
Circular Queue (8)
Q5. Write a program in C for insertion sort. Write the step-by-step working of the insertion sort for the
following set of data: 10, 25, 86, 1, 16, 95, 37, 56, 5, 15, 20, 4. Also count the number of swaps and
comparison operations performed for it. (8)
Q7. Create the binary tree for which the in-order and post order traversal are given as below: (8)
In-order: QUVTMPSYZXR
Post-order: VUTQZYXSRPM
Q8. Create a B tree of order-5 for the following keys, inserted in the sequence. (8)
25, 5, 10, 2, 3 35, 45, 30, 50, 55, 60, 12, 18, 20, 1
Further, delete the keys 1, 2, 10, and 12. Show all the intermediate steps.
Q9. Create AVL tree for the following keys inserted in the order: (8)
Further, delete the keys 2, 5, 7, and 8. Show all the intermediate steps.
Q10. Solve the following instance of single source shortest paths problem with vertex 'a' as the source
using suitable method. (8)
3
4