Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

So, I had a quiz last night in my discrete structures class and this question came up:

"There are 3 processors in a computer. The instructions to a computer are labeled 1,2,3,4,5,6,7,8,9,10 each taking 1 second to execute. The relation between a pair of instructions (x,y) is given by R:'x' is executed at the same time or before 'y'. Using the properties of relations, design an execution process including the sequence of execution that takes the minimum time. Relation between the instructions is R={(1,1)(2,2)(3,3)(4,4)(5,5)(6,6)(7,7)(8,8)(9,9)(10,10)(1,7)(5,8)(2,3)(8,10)(5,10)}"

How would I go about solving this? I want to understand how to do it....but I don't know where to start...

share|cite|improve this question
up vote 1 down vote accepted

I dont think so. youve got the first instruction called more than once. ive got this:

P1: 1 | 4 | 7 | 10

P2: 2 | 5 | 8

P3: 3 | 6 | 9

Its simple. It only takes four seconds, and all the relationships are satisfied. It is partial order (transitive, reflexive, and antisymmetric) so there is more than one right answer. Also, the 10 could be executed by any of the processors.

share|cite|improve this answer
I sat in tutoring for 40 minutes trying to figure this one out with our tutor. We had 20 minutes to take the quiz. I'm not sure how anyone could have got this right.. – user7988 Mar 9 '11 at 21:32

The interesting part of $R$ is $$ \begin{align*} &1 \leq 7 \\ &2 \leq 3 \\ &5 \leq 8 \leq 10 \end{align*} $$ Missing are $4,6,9$.

Does that help?

share|cite|improve this answer
So, would the sequence be (1,7)(2,3)(4,4)(5,8)(8,10)(6,6)(9,9)? – OghmaOsiris Mar 9 '11 at 7:00
The execution process is not a list of pairs, rather a list of which processor runs what instruction at each point in time. – Yuval Filmus Mar 9 '11 at 13:09
So: 'Processor1-1,2,4,5 ,6,9 Processor2-7,3,.,8 ,.,. Processor3-.,.,.,10,.,.?' – OghmaOsiris Mar 9 '11 at 16:49
Remember you want to minimize the total time. I have a solution that works in 4 seconds versus your 6 seconds. – Yuval Filmus Mar 9 '11 at 17:13
So: $$ \begin{align*} P1: 1, 2, 4, 5 \\ P2: 1, 3, 6, 8\\P3: 7, ., 9, 10\end{align*} $$ – OghmaOsiris Mar 9 '11 at 19:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.