- Section 8.10

And… that’s it! We’re skipping 8.6 (which I would have liked to assign) and 8.9 (which is not as important).

Leave a reply

- Section 8.10

And… that’s it! We’re skipping 8.6 (which I would have liked to assign) and 8.9 (which is not as important).

- Section 8.7
- Section 8.8

Two readings, I know. Sorry! Then again, it is a full week between the classes!

Enter your password to view comments.

- Section 8.5
- Chapters 7, 9, and 11
- Moby Dick

(**VERY IMPORTANT** note on all but 8.5: http://goo.gl/CjHH.)

Here’s the PDF of the 2015/03/27 notes.

- Section 8.4

Enter your password to view comments.

PDF document: Assignment #7

Due Wednesday 2015/04/08 at 5PM in our submission box (#32). **NOTE THE UNUSUAL DUE DATE!**

- Use the assignment cover page.
- Read the academic conduct guidelines or expect horrendous consequences for you.
- Please work with a partner; you’ll learn more, and we’ll spend less time on marking and more on making the course awesome.

- Section 8.3

This problem is based on 8.4 from the Kleinberg and Tardos textbook.

Suppose you’re consulting for a group that manages a high-performance real-time 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*. 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* (RR) as follows: Given a set of processes 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?

- For this part and the next part
**only**, assume you**do**have a polynomial-time algorithm for RR. Give a polynomial-time algorithm to determine the**largest***k*for which you can allocate resources to processes so that at least*k*processes will be active. - Still assuming you have a polynomial-time algorithm for RR, give a polynomial-time algorithm to determine a maximum-size set of processes that can be simultaneously active. (The specific processes, not just how many there are.)
- Now stop assuming you have a polynomial-time algorithm for RR, and consider the following list of problems. For each problem either give a polynomial-time algorithm or prove that the problem is NP-complete. (In the former case, your “algorithm” may be a reduction to another problem that you know can be solved in polynomial time.
*Hint:*One of these can be solved in polynomial time by reduction to the “maximum matching problem”, which can be solved in polynomial time.)- The general Resource Reservation Problem defined above.
- The special case of the problem when
*k*= 2. - The special case of the problem when
*k*= 10. - The special case of the problem when there are two types of resources—say, robotic dogs and robotic cats—and each process requires exactly one resource of each type. (In other words, each process requires one specific robotic dog and one specific robotic cat.)
- The special case of the problem when each resource is requested by at most two processes.