Question 1. Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time. You may provide your approach in words, though a pseudo code would be preferred.
Question 2. Describe an algorithm that, given n integers in the range 0 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range [a,b] in O(1) time. Your algorithm should use Θ(n+k) preprocessing time. Provide a pseudocode.
Question 3: Programming Exercise
Attempt any one of the following 3. Provide .in and .out files(as per the format accepted/output by your code) along with the .C file
- Write a C program for Question 1
- Write a C program for Question 2
- Implement a queue by using a singly linked list. The operations ENQUEUE and DEQUEUE should still take O(1) time.