Prove that finding an acceptable arrangement

Assignment Help Computer Engineering

Reference no: EM132118896

Question :

You're in charge of choreographing a musical for your local community theater, and it's time to figure out the final pose of the big show-stopping number at the end. ("Streetcar!"')

You've decided that each of the n cast members in the show will be positioned in a big line when the song finishes, all with their arms extended and showing off their best spirit fingers.

The director has declared that during the final flourish, each cast member must either point both their arms up or point both their arms down; it's your job to figure out who points up and who points down.

Moreover, in a fit of unchecked power, the director has also given you a list of arrangements that will upset his delicate artistic temperament.

Each forbidden arrangement is a subset of the cast members paired with arm positions; for example: "Marge may not point her arms up while Ned, Apu, and Smithers point their arms down." Prove that finding an acceptable arrangement of arm positions is NP-hard.

Reference no: EM132118896

Questions Cloud

How to read a html file using python : How to read a html file using python, then extract id and links in that file.

How knowledge management systems could be used : Consider your degree program (Business Study with Accounting Concentration) or your selected industry (Restaurant Business).

How would you write a piece of code that throws : How would you write a piece of code that throws a RuntimeException with the message "An incorrect parameter was given"?

Which data structures should you use for the address book : Suppose we want to create an address book which contains names, phone numbers, emails, and other personal information.

Prove that finding an acceptable arrangement : "Marge may not point her arms up while Ned, Apu, and Smithers point their arms down." Prove that finding an acceptable arrangement of arm positions is NP-hard.

Compute the greatest common divisor of two given numbers : Based on these observations, implement a function to compute the greatest common divisor of two given numbers >= 1.

What information do you need to carry out the proposal : You're called in to consult for a company that's issuing about 100 new wireless mobile devices to selected employees.

What is the recurrence for the running time : We're given an array of n numbers, A[1 · · · n] and want to add up the n numbers. What is the recurrence for the running time? Solve it.

Give an algorithm with polynomial running time to do this : Naturally, they're not sure that all these facts are correct; memories are not so good, and a lot of this was passed down by word of mouth.

User Account

All Pages