Q.1

Given a linked list of integers sorted in the ascending order, and a pointer to a single node containing

an integer, insert the node in the linked list so that it remains sorted.

Q.2

Given two null terminated linked lists, combine their nodes so that the nodes of the new list alternate

between those of the two original nodes: <first node of first list, first node of second list, second node

of first list, second node of second list, ... >.

Q.3

A stirling number of the first kind is defined as follows:

o s(0,0) = 1

o s(n,0) = 0, for all n > 0

o s(n+1,k) = s(n,k-1) – n * s(n, k), for all n =0 and k>0

Write a recursive routine to calculate stirling numbers of the first kind.

Q.5

A deque is a data structure consisting of a list of items, on which the following operations are

possible:

· push(x): Insert x on the front end of the deque.

· pop( ): Remove the front item from the deque and return it.

· inject(x): Insert x on the rear end of the deque.

· eject( ): Remove the rear item from the deque and return it.

Describe routines to support the deque that take constant number of steps for each operation. You may

use array-based or pointer-based implementation.

Q.6

For each of the following program fragments, give an analysis of the running time. You may use

summations to evaluate the running times of nested loops.

(a) sum = 0

for i = 1 to n

for j = 1 to i * i

for k = 1 to j

sum ++

(b) sum = 0

for i = 1 to n

for j = 1 to i * i

if j mod i == 0

for k = 1 to j

sum ++

SOLUTIONS:

• Mathematics-1996
  (60 downloads)