Problem Set 3
Assigned: Mar. 1.
Due: Mar. 22.
The K-PROCESSOR SCHEDULING WITH PRECEDENCE problem is defined as follows:
You are given a DAG G whose vertices are tasks and whose edges express
precedence constraints. Assume that each task takes unit time to execute,
and that, if there is an edge from task U to V, then U must be scheduled
before V. You are given an integer K, which is a number of
processors, and an integer M, which is a deadline. The problem is
to come up with a valid schedule: An assignment of tasks to
processors in which:
For instance, with the DAG below
- 1. No processor executes more than 1 task at a time.
- 2. If there is an arc from U to V then U is executed before V.
- 3. All tasks are completed no later than M.
K=2, and M=3, one valid schedule is
| Task || Processor || Time
| B || 1 || 1
| C || 2 || 1
| A || 1 || 2
| E || 2 || 2
| D || 1 || 3
| F || 2 || 3
This problem can be encoded in propositional logic using atoms of the form
T-P-I, which is true in a schedule
if task T is executed on processor P at time I. For
instance in the above schedule, A-1-2 is true whereas E-1-1 is false.
Describe the types of propositional constraints that arise in expressing
this problem in propositional logic and give one example of each type from
the above problem. THE TYPES
OF CONSTRAINTS SHOULD BE DESCRIBED FOR THE GENERAL CASE, NOT FOR
THIS PARTICULAR PROBLEM. THE EXAMPLE SHOULD REFLECT THE PROBLEM,
NOT THE PARTICULAR SOLUTION ABOVE. Programming assignment 2 is a good model
for the form of the answer to this problem. You do not have to state the
constraints in clausal form.
Let U be a universe of web pages, web sites, people, and topics. Let
L be a first-order language with the following primitives.
S(w,s) --- Predicate. Page w is on site s.
Represent the following sentences in L:
L(w1,w2) -- Predicate. There is a link from page w1 to w2.
A(w,t) --- Predicate. Page w contains information about topic t.
W(p,w) --- Predicate. Person p wrote page w.
R(p,w) --- Predicate. Person p has read page w.
E, F, J, M, T --- Constants representing Elizabeth, frogs, Jim, MySite, and
- 1. Elizabeth has written a page about turtles.
- 2. All of the pages that Elizabeth has written are on site MySite.
- 3. Every page on MySite has a link to some page that is not on
- 4. Elizabeth's pages only link to pages about turtles and pages about
- 5. Jim has written a page that has a link to every page on the web
that is either about turtles or frogs.
- 6. Jim has read every page that he has linked to.
- 7. Jim has read some paper outside MySite.