Use algorithm np completeness of any of the problems

Assignment Help Theory of Computation

Reference no: EM1370349

The final is individual work. Please do not discuss these questions with anyone expect with Swamy, Tom and Eva. We will do our best to answer your emails promptly during the week, and also will have office hours every day (see Web). In writing down your solutions you may use any algorithm without writing out the details of the algorithm. In proving a problem NP-complete, you may use the NP completeness of any of the problems that we proved NP-complete in class or as a homework.

You may use the course packet, Kozen's book, hand outs, or any of the recommended books. If you use books other than the course packet, or Kozen's book in your solutions, please give clear reference to the source you used. (1) Suppose you are managing a system in which asynchronous processes make use of shared resources. Thus, the system has a set of n processes and a set of m resources. At any given point in time, each process specifies a set of resources that it requests to use. Each resource might be requested by many processes at once; but it can only be used by a single process at a time. Your job is to allocate resources to processes that request them. If a process is allocated all the resources it requests, then it is active; otherwise it is blocked. You want to perform the allocation so that as many processes as possible are active. Thus, we phrase the Resource Reservation problem as follows: given a set of process and resources, the set of requested resources for each process, and a number k, is it possible to allocate resources to processes so that at least k processes will be active? Consider the following list of problems, and for each problem either give a polynomial time algorithm or prove that the problem is NP-complete.

(a) The general Resource Reservation problem defined above.
(b) The special case of the problem when k=2.
(c) The special case of the problem when there are two types of resources, say rooms and equipments, each process requires at most one resource of each type.
(d) The special case of the problem when each resource is requested by at most two processes.

Reference no: EM1370349

Questions Cloud

Explain monotone instance of satisfiability : Given monotone instance of Satisfiability, together with number k, problem of Monotone Satisfiability with Few True Variables asks: is there satisfying assignment for instance in which at most k variables are set to 1.

Suppose that anthony had contacted various users of yahoo : Suppose that Anthony had contacted various users of Yahoo's online dating service only to discover that each user's profile exaggerated the user's physical appearance

Calculate the profit maximizing activity level : PL offers mail-order storage containers for china. The company is the low cost provider of these quilted boxes with fixed costs of $480000 a year, plus variable costs of $30 a box.

Explain what values or assumptions do the laws : Explain What values or assumptions do the laws of these countries make about the employment relationship?

Use algorithm np completeness of any of the problems : Use any algorithm we without writing out details of algorithm. In proving problem NP-complete, you may utilize NP completeness of any of the problems.

Explain what is the difference between a standard and budget : Explain What is the difference between a standard and a budget andf Manage by exception is a term often used by management

Question based on value added : What value added means is not a higher price for certain goods. Value added means adding value to a raw product at its present stage of production and possibly taking that product to the next stage of production.

Explain what economic concept is central to proving risk : Explain What economic concept is central to proving that risk neutral pricing functions in the establishing of option prices?

Multiple choice questions based on competitive market : A perfectly competitive market company realizes an average of $11 and an average total cost of $10.00. Marginal cost curve crosses marginal revenue curve at an output level of 100 units.

User Account

All Pages