What is the time complexity of the verifier

Assignment Help Computer Engineering

Reference no: EM132087453

[P and NP] In a university, several classes are conducted on the same day. Each class is given a time interval [tbegin, tend] which indicates the starting and ending times of the class. Suppose that you are given n-classes C = {c1, c2, . . . , cn} with the meeting times, the CLASSROOM problem is to decide whether k classrooms are sufficient to run all the classes. Formally,

CLASSROOM = {<C, k> | classes C can be scheduled with k classrooms }

1) Show that CLASSROOM is in NP. That is, given an instance ? CLASSROOM, what is the certificate and verifier algorithm for . Writing a pseudo-code for the verifier algorithm suffices.

2) What is the size of the certificate in terms of the input size? What is the time complexity of the verifier? You need not prove your answer, providing explanation for the time complexity suffices.

Hint: Consider an instance of CLASSROOM as a dependency graph and apply known graph algorithms.

Reference no: EM132087453

Questions Cloud

Determine if it is a standard palindrome a perfect palindrom : A palindrome is a word or phrase that is identical forward or backward, such as the word "racecar."

What was the straight-line interest expense on the december : Interest is paid semiannually. What was the straight-line interest expense on the December 31 annual income statement

Common complaint among grammatical purists : A common complaint among grammatical purists is the following sentence type:

Describe what the procedure should accomplish : A painting company has determined that for every 115 square feet of wall space, one gallon of paint and eight hours of labor are required.

What is the time complexity of the verifier : What is the size of the certificate in terms of the input size? What is the time complexity of the verifier?

How african americans approached the federal state : Topic: Analyze the various ways that WWII and the Cold War affected how African Americans approached the federal state in the late 1950's through the mid 1960s.

Write a boolean method that users recursion : Write a boolean method that users recursion to determine where a String argument is a palindrome.

How does each speaker establish credibility : How does each speaker establish credibility?

How do you all feel about speaking : How do you ALL feel about speaking in front of an audience as opposed to presenting your ideas in writing? Why?

User Account

All Pages