Problem Set 3

Assigned: Mar. 1.
Due: Mar. 22.

Problem 1

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

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.

Problem 2

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.
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: