Scribd
Upload
16 views2 pages

Data Structures

The document outlines an assignment focused on stack, queue, and priority queue operations, including specific sequences of operations and the expected outcomes. It requires students to illustrate the state of data structures after certain operations, determine values from pop and dequeue actions, and provide pseudocode for basic operations. Additionally, it presents problems involving merging sorted arrays using heaps and finding a peak in a unimodal array efficiently.

Uploaded by

ahona.mukherjee
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views2 pages

Data Structures

The document outlines an assignment focused on stack, queue, and priority queue operations, including specific sequences of operations and the expected outcomes. It requires students to illustrate the state of data structures after certain operations, determine values from pop and dequeue actions, and provide pseudocode for basic operations. Additionally, it presents problems involving merging sorted arrays using heaps and finding a peak in a unimodal array efficiently.

Uploaded by

ahona.mukherjee
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithms Assignment 3: Stack, Queue and Priority Queue

1. Following is a sequence of stack operations on an empty stack s:

Push (s, 15);


Push (s, -50);
y1 = Pop(s);
Push (s,-18);
Push (s,12);
y2 = Pop(s);
Push (s,14);

(a) Assuming all instructions execute in the given sequence, draw three diagrams,
showing the contents of the stack, after executing the second, fourth, and sixth
instructions. In each diagram, include the values of all elements in the stack,
and a pointer denoting the current ”top” of the stack.
(b) What are the values of y1 and y2 after the code executes?
(c) Finally give pseudocodes for basic stack operations: Push, Pop and Empty using
array.
2. Following is a sequence of queue operations on an empty queue q of size four using a
circular array of size four:

enqueue (q,9);
enqueue (q,2);
enqueue (q,-6);
y1=dequeue (q);
enqueue (q,14);
enqueue (q,56);
y2=dequeue (q);

(a) Assuming all instructions execute in the given sequence, draw three diagrams,
showing the contents of the queue, after executing the second, fourth, and sev-
enth instructions. In each diagram, include the values of all elements in the
queue, and two pointers denoting the current ”front” and ”back” of the queue.
(b) What are the values of y1 and y2 after the code executes?
(c) Finally, give the code that would implement the same sequence of operations to
a queue using a circular array.
3. Suppose you have k sorted arrays, each with n elements, and you want to combine
them into a single sorted array of kn elements. Give an efficient solution to this
problem, using a heap.
4. Suppose you are given an array with n entries, with each entry holding a distinct
number. You are told that the sequence of values A[1], A[2], . . ., A[n] is unimodal.
For some index p between 1 and n, the values in the array entries increase up to
position p in A and then decrease the remainder of the way until position n. We
would like to find the “peak entry” p without having to read the entire array, by
reading as few entries of A as possible. Show how to find the index p by reading at
most O(log n) entries of A.

You might also like