Determine if these sequences could represent valid operation

Assignment Help Computer Engineering

Reference no: EM133371028

You are given two sequences - a PUSH sequence and a POP sequence each consisting of n integers that are suppose to represent the sequence of values pushed and values popped from a stack that starts empty and ends empty. The goal is to determine if these sequences could represent valid operation of the stack. In other words, while we are given the order of the values pushed and the order of the values popped, we want to know if there is a way to interleave the push and pop operations to make this the legal behavior of a stack.

(a) First suppose that all values in the PUSH sequence are distinct. Give an O(n) algorithm to deter- mine if the two sequences are valid.

(b) Next, at the other extreme, suppose that the only values in the PUSH sequence are 0 and 1. Again give an O(n) algorithm to determine if the two sequences are valid.

(c) Finally, consider the general case, where the values may repeat but are not restricted to be 0 or 1. Give an O(n4) dynamic programming algorithm to determine if the input represents a valid pair of sequences and prove that your algorithm is correct.

Reference no: EM133371028

Questions Cloud

Summarize the negotiation and prioritization process : Provide a summary of each group member's community/culture and the health-related goal. Summarize the negotiation and prioritization process your

Write a program that reads two input numbers : write a program that reads two input numbers that represent feet and inches and convert this answer to be just inches. Write another program to do the reverse

Discusses militant theology : The text briefly discusses militant theology. how would you explain it to a lay person?

Hobbes or locke social contract theory : Are you more aligned with Hobbes or Locke social contract theory? Would you define some things differently?

Determine if these sequences could represent valid operation : Determine if these sequences could represent valid operation of the stack. In other words, while we are given the order of the values pushed and the order

Should convicted drug offenders : Should convicted drug offenders, who suffer from Substance dependence, be given the same sentencing as offenders who do not suffer from dependence?

Why is it important to have a personal life philosophy : Why is it important to have a personal life philosophy? Please include all information. Define and explain the differences between: A behavior change philosophy

Create a survey questionnaire that could be used to gather : Create a survey questionnaire that could be used to gather feedback from trainees to gauge the effectiveness of the training and inform you about changes

Most important to least important in your life : Why are health, religion, Emotional well-being, love, loyalty, some values from most important to least important in your life.

User Account

All Pages