ADVANCED PROGRAMMING

QUESTION BANK
Total questions: 35
Q1. Given a linked list with even and odd numbers, given an algorithm for making changes to the list in
such a that all even numbers appear at the beginning.
Q2. How can we convert a binary tree to a doubly linked list?
Q3. Discuss infix to postfix conversion algorithm using stack.
Q4. How to implement 3 stacks using one array?
Following are the two extra arrays are used:

1) top[]: This is of size k and stores indexes of top elements in all stacks.

2) next[]: This is of size n and stores indexes of next item for the items in array arr[].

Here arr[] is actual array that stores k stacks. Together with k stacks, a stack of free slots in arr[] is also
maintained. The top of this stack is stored in a variable ‘free’. All entries in top[] are initialized as -1 to
indicate that all stacks are empty. All entries next[i] are initialized as i+1 because all slots are free initially
and pointing to next slot. Top of free stack, ‘free’ is initialized as 0.
Q5. A queue is set up in a circular array A[0, n-1] with front and rear defined as usual. Assume that n-1
locations in the array are available for storing the elements (with the order element being used to detect
full/empty conditions). Give a formula for the number of elements in the queue in terms of rear, front, and n.
Q6. Write an algorithm to find the total number of nodes in CBT with height h.
Q7. Give an algorithm for constructing BT from given In-order and Pre-order traversal.
Q8. Give an algorithm for counting the number of BSTs possible with n nodes.
Q9. Take singly linked lists where elements are sorted in ascending order and convert them to a height-
balanced BST.
Q10. Given a big file containing billions of numbers. How to find the maximum of 10 numbers from those
files?
Q11. Design a heap data structure that supports finding the median.
Q12. Considering the sorting algorithms: Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Heap sort,
and Quick Sort. Which of these is stable?
Q13. Can we implement linked list sorting with quick sort? If yes then how.
Q14. Show how to implement one queue efficiently using two stacks. Analyze the running time of the stack
operations.
Q15. For a given array with n symbols how many stack permutations are possible?
Q16. Give an algorithm for shuffling the deck of cards.
Q17. We are given a recursive algorithm that, given an input of size n, splits it into 2 problems of size n/2,
solves each recursively, and then combines the two parts in time O(n). Thus, if T(n) denotes the runtime for
the algorithm on an input of size n, then we have: T(n) = 2T(n/2) + O(n)
Prove that T(n) = O(n log n).
Q18. how to solve T(n)=4T(√n)+3^5n with the master theorem how do I apply the master theorem to this?
Q19. Two alternative packages, A and B, are available for processing a database with 10^k records.
Package A requires 0.0001n^2 time units and package B requires 10nlog10^n time units to
process n records. What is the smallest value of k for which package B will be preferred over A?
Q20. Given a sorted array, what can be the minimum worst-case time complexity to find the ceiling of a
number x in a given array? The ceiling of an element x is the smallest element present in the array, greater
than or equal to x. The ceiling is not present if x is greater than the maximum element present in the array.
For eg., if the given array is {12, 67, 90, 100, 300, 399} and x = 95, then the output should be 100.

Q21. Consider the following undirected, weighted graph:

Step through Dijkstra’s algorithm to calculate the single-source shortest paths from A to every other vertex.
Show your steps in the table. Cross out old values and write in new ones, from left to right within each cell,
as the algorithm proceeds. Also, list the vertices in the order in which you marked them known. Finally,
indicate the lowest-cast path from node A to node F.
Q22. Use Kruskal's algorithm to find a minimum spanning tree of the given graph below. Draw the resulting
spanning tree and list the edges in the order they are picked by Kruskal's algorithm.
Q23. Use Prim's algorithm, starting at H, to find a minimum spanning tree of the graph given above
(Question no. 22). Draw the resulting spanning tree and list the edges in the order they are picked by Prim's
algorithm.
Q24. Given n ropes of different lengths, connect them into a single rope with minimum cost. Assume that
the cost to connect two ropes is the same as the sum of their lengths. Find an algorithm to find out the
minimum cost.
Q25. Consider the following splay tree:

Perform a delete for the key 3 under the assumption that this is a bottom‐up splay tree. Show each step.
Q26. Using DYNAMIC PROGRAMMING, find the minimum number of coins required to solve make a
change problem for given data: Set of denominations, D =<1,3,4>, Amount N = 6.
Q27. Find the DFS and BFS traversal sequence for given graph.
Q28. Show the construction of the recursion tree for the recurrence T(n)=2T(n/2)+cn.
Q29. How Compressed Tries work explains its operations. Also, Explain Standard Tries with an example.
Q30. Use the Chinese Remainder Theorem to find an x such that
x ≡ 2 (mod 5)
x ≡ 3 (mod 7)
x ≡ 10 (mod 11)

Q31. You have a collection of r three-Rupee coins, s seven-Rupee coins, t eleven-Rupee coins, and u sixteen
rupees coins. (These need not be actual coins, but tokens worth these values.) Given an integer n > 0, your
task is to determine whether a sum of n Rupees can be exchanged exactly by coins from your collection. As
an example, let r = 1, s = 2, t = 3, and u = 4. Thirty Rupees can be exchanged as 7 + 7 + 16 or as 3 + 11 + 16
(but not as 3 + 3 + 3 + 3 + 7 + 11, since you do not have so many three-rupee coins), whereas 31 Rupees
cannot at all be exchanged by the coins in this collection (try it!). Describe an O(n 2 )-time algorithm to
solve this problem. Your algorithm does not have to find a change (when it exists). It suffices to find out
only whether a change is possible or not.
Q32. Design an O(h(T))-time algorithm to insert a value x with priority y in a treap. And Demonstrate how
your algorithm inserts the value 19 with priority 23 in the treap.
Q33. Explain the property of the Fibonacci heap.
Q34. The keys 12, 18, 13, 2, 3, 23, 5, and 15 are inserted into an initially empty hash table of length 10 using
open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
Q35. Suppose we perform a sequence of n operations on a data structure in which the i th operation costs i if
i is an exact power of 2, and 1 otherwise. Use aggregate analysis or accounting methods to determine the
amortized cost per operation.