## Problem Set 2

Assigned: Feb. 15.

Due: Mar. 1.
### Problem 1

The MULTIPROCESSOR PRECEDENCE CONTRAINED SCHEDULING problem is defined
as follows: You are given:
- M identical processors.
- A set T of tasks.
- A partial ordering on the tasks in T, representing precedence constraints
(that is T1 < T2 means that T2 cannot be begun until T1 is complete.)
- For each task t in T, a length l(t).
- An overall deadline D.

The object is to give a *schedule* for T that observes all these
constraints. A schedule is an assignment of a processor and a starting
time to each task such that each processor is running at most one task at a
time; each task runs for the specified length; and the precedence
constraints are observed.
For example, suppose M=3, T1 ... T6 have respective lengths 3, 2, 3, 4, 2,
and 1, and T2 < T3, T1 < T4, T2 < T4, T3 < T5, and D=8. Then one valid
schedule would be the following:

M1: Task T1 from 0 to 3, idle from 3 to 5, task T5 from 5 to 7, idle from 7 to 8
M2: Task T2 from 0 to 2, idle from 2 to 3, task T4 from 3 to 7, idle from 7 to 8
M3: Idle from 0 to 2, Task T3 from 2 to 5, task T6 from 5 to 6.

If l(T), M, and D are all small integers, then the problem can be compiled into
propositional satisfiability using propositional atoms of the form T_P_K meaning
that task T begins on processor P at time K, where K=0 ... D-1. The
number of propositional atoms is thus |T| * M * D.
Describe the constraints
you need for the general case. Illustrate each category of constraint
with a sample constraint from the above example. As a function of M, |T|,
and D, how many constraints are there (order of magnitude)?
### Problem 2

Consider a first-order language L over a universe of people with the
following primitives:
p(X,Y) --- Predicate. X is a parent of Y.

fa(X,Y) --- Predicate. X is a father of Y.

mo(X,Y) --- Predicate. X is a mother of Y.

fe(X) --- Predicate. X is female

a(X) --- Predicate. X is alive.

o(X) --- Predicate. X is an orphan.

s,a,b --- Constant. Sarah, Andy, Bob.

Express the following statements in L.
- 1. A mother is a female parent.
- 2. A father is a parent who is not female.
- 3. An orphan is someone with no living parents.
- 4. Sarah is not an orphan.
- 5. Sarah either has a living father or a living mother.
- 6. Everyone has a father and a mother.