Stack generability. Suppose that we have a sequence of intermixed push and pop operations as with our test stack client, where the integers 0, 1, ..., N-1 in that order (push directives) are intermixed with N minus signs (pop directives). Devise an algorithm that determines whether the intermixed sequence causes the stack to underflow. (You may use only an amount of space independent of Nyou cannot store the integers in a data structure.) Devise a linear-time algorithm that determines whether a given permutation can be generated as output by our test client (depending on where the pop directives occur).

Hint: By linear-time algorithm, think of an algorithm that touches/looks into a stack element at most a constant number of times, say 2 or 3 times.

This is a textbook questions (Algorithms Fourth Edition) so no other specifications are given so best options is to include assumptions.