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