Explain how to implement two stacks in one array

Reference no: EM131021864

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.

Reference no: EM131021864

Questions Cloud

Identify your dream job and what kind of job youd die to do : Identifying your dream job and/or discussing what kind of job you'd die to do (and why) and b) describing or discussing the things you do best and most love to do

What is parkview opportunity cost of producing one book : Using the given information in the above table and in the introduction, draw the production-possibility frontiers (PPF) for both Parkview and Glenview (on two separate graphs). Measure the number of books produced on the Y axis and the number of p..

What was the crime and who was involved : What was the crime? (Murder, bank robbery, kidnapping). Who was involved? How, when, where did the crime occur? Results of the investigation/Trial? Apply the theories of criminology discussed in the textbook to the crime and criminal(s) involved.

How being an effective follower can translate : Discuss areas in your life where you might fill leadership roles and where you might fill follower roles. Explain how being an effective follower can translate into developing yourself further as a leader.

Explain how to implement two stacks in one array : 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 approac..

How did the interviewer handle the initial ice-breaking : How did the interviewer handle the initial 'ice-breaking'? Was there any effective transition from fact -gathering into learning the client's goals? How was the fact -finding conducted?

Why people make more payments using checks than cash : Consider why people make more payments using checks than cash. Are there additional advantages for business owners to make payments by check?

Who are they and how does hulu serve each of them : P&G is considering using a single, large, third party vendor versus multiple specialist third party vendors for outsourcing its GBS division. Discuss the pros and cons of these two sourcing models.

What are moral pitfalls of removing correctional facilities : What are the "moral pitfalls" of removing correctional facilities from the public sector (and therefore public review) and placing large segments of society into private correctional facilities?

User Account

All Pages