५१
| 3 4 ١ 049/21

24. Write a pseudocode to reverse a natural number n. For example, ifn = 12345, then the output required
is 54321. Use only numeric variables in the pseudocode (use of arrays or any other data structure is
not allowed). Also, show the asymptotic complexity of your pseudocode. (10 Marks)

25. Let h be a pointer to the first node of a linear linked list with nodes having the following structure :

x ‏ج‎ data, the data ೫ ‏جه‎ next, address
stored at node x. of the next node.

Write a pseudocode to reverse the linked list. (10 Marks)

26. Argue that the problem of checking whether a given undirected graph 6 = (४ E) is Hamiltonian, is in
the complexity class NP. (10 Marks)

27. Consider the computational problem to search for an element e in an ordered sequence of n elements.

Argue that the minimum asymptotic time complexity is O(log n) for any comparison-based algorithm
to solve this problem. (10 Marks)

28. What is meant by normalisation in database systems ? What are the conditions to be satisfied for the
second normal form (2NF) ? Normalise the following database table to make it satisfy the conditions
for 2NF : (10 Marks)

103

29. Consider a set-associative cache or size 4 KB (1 KB = 270 bytes) with a cache block size of 64 bytes.
Assume that the cache is byte-addressable and a 32-bit address is used for accessing the cache.
Calculate the associativity of the cache if the width of the tag field is 21 bits ? (10 Marks)

30. Consider four processes (say Pp. நன ಗ ‏زی‎ assumed to have arrived at time 0. Their burst times
are 7, 6, 1 and 3 respectively. These processes are scheduled on a uniprocessor using Round Rabin (RR)
algorithm, in the order ‏ب۲‎ Py [छि Py The time quantum for RR is 4 ms. Calculate the average
turn-around time (in ms) of RR. (10 Marks)

31. Consider four processes (say ॥,, 02, ಗೃ, P,) assumed to have arrived at time 0. Their burst times are
9, 8, 3 and 5 respectively. These processes are scheduled on a uniprocessor using Non-preemptive
Shortest Job First (SIF) algorithm, Calculate the average turn-around time (in ms) of SIF. (10 Marks)

32. What 15 the maximum number of nodes possible at level d in a rooted binary tree ? Here, level of a
node x is the number of edges to be traversed to reach the node x from the root node. Prove that
your answer is correct. (10 Marks)