Problem Set 3
Assigned: Mar. 1.
Due: Mar. 22.
Problem 1
The KPROCESSOR 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:
 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.
For instance, with the DAG below
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
TPI, which is true in a schedule
if task T is executed on processor P at time I. For
instance in the above schedule, A12 is true whereas E11 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.
Problem 2
Let U be a universe of web pages, web sites, people, and topics. Let
L be a firstorder language with the following primitives.
S(w,s)  Predicate. Page w is on site s.
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
turtles.
Represent the following sentences in L:
 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
MySite.
 4. Elizabeth's pages only link to pages about turtles and pages about
frogs.
 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.