a) Write an algorithm to add and multiply two large integers, which cannot be

represented by built-in types.
b) Write a “c” function to find recursively the maximum and minimum element of

an array A of size “n” elements. Find also the number of comparisons required for

this.

Q.2
a) How do you represent a stack and a queue by using one-dimensional array?
b) Write “c” functions for pushing into or popping from a stack.
c) Write “c” functions for adding an element to a queue and removing an element

from a queue.
Q.3
a) Define directed and undirected graphs. Give examples. Show that the sum of

degrees of all vertices in an undirected graph is twice the number of edges.
b) Define weighted graph and sub-graph. Give examples.

Q.4
a) Show that a tree with “n” nodes has exactly (n – 1) edges.
b) Prove that a binary tree with “n” internal nodes has (n + 1) external nodes.
c) If “E” and “I” denote the external and internal path lengths of a binary tree having

“n” internal nodes then the following identity holds
E = I + 2*n. Prove it.
Q.5
a) Determine with the help of an example whether the initial order of elements is

preserved in the case of bubble sort.
b) Write a “c” function to sort a list of integers using insertion sort technique where

the list is represented through links using pointers.

 

 

 

Assignment B

Q.1

Define algorithm. Explain the space and time complexity of the algorithm with an

example.
Q.2

a) What is linked list? Write a ‘C’ function to delete every alternate node starting with first node (i.e. first, third, fifth and so on) in a singly linked list.

b) Define hash functions. Explain the Division method, Mid square method and Folding method of hash functions.

Q.3

a) Write a note on priority queue by giving suitable example.
b) Write a C function to evaluate a postfix expression using stack.

Case Study

Q.1

Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.

 

a)Consider the following values sorted in an array. Sort it in ascending order using Bubble sort technique showing all the iterations:
15, 43, 5, 18, 27, 3, 10

b)Also write a C function to sort one dimensional integer array in ascending order using Bubble Sort technique.