Weighted precedence and scheduling

Try

A synthetic workshop must complete six tasks. The durations below are fixed positive numbers of minutes, not measured estimates. An arrow means the first task must finish before the second starts. There are unlimited identical workers, no setup delays and no other resource constraints. A task runs continuously once started: this is nonpreemptive execution. All starts must be at or after time zero.

Task	Duration	Immediate prerequisites
A	3	none
B	2	none
C	4	none
D	5	A and B
E	2	B and C
F	3	D and E

Sketch a schedule before adding the six durations. A, B and C may run together. D cannot start until both A and B finish, so its earliest start is minute three, not minute five. E waits until minute four. Then F waits until minute eight. The workshop can finish at minute eleven, even though the total work is nineteen worker-minutes.

Total work and elapsed completion time answer different questions. The first adds all processing; the second accounts for which tasks can overlap. Unlimited workers is a consequential assumption, not a claim about real workshops.

Predict

Predict whether swapping the order in which you calculate A and B changes the answer. It should not: neither depends on the other. By contrast, calculating F before its predecessors have numerical finish times leaves necessary information missing.

A topological order lists every prerequisite before its dependents. It is an order for evaluating the calculation, not a demand that all tasks execute sequentially. One valid order is A, B, C, D, E, F; another is C, B, E, A, D, F. Both can describe the same parallel execution.

Now predict whether reducing E from two minutes to one makes the whole project faster. E would finish at five instead of six, but F would still wait for D until eight. Improving one task need not improve the final completion time. Explain which incoming constraint controls F before calculating again.

Experiment

Draw each interval from the table on a common minute axis. The supplied chart is a worked example, not a simulation of measured workers. Compare its overlaps with the prerequisite table and check every edge.

Task	Start	Finish
A	0	3
B	0	2
C	0	4
D	3	8
E	4	6
F	8	11

Change C’s duration to seven minutes and redraw only affected intervals. E now runs from seven to nine, so F runs from nine to twelve; D stays at three through eight. The path C→E→F now takes twelve minutes. This changed example gives a lower bound that matches your new schedule. When an affected predecessor changes, recompute maxima rather than adding the change blindly to every downstream time.

Understand

Let d(v) be task v’s duration and E(v) its earliest finish. A task must wait for the latest predecessor finish, not the sum of predecessor finishes. Thus

E(v)=d(v)+max(all E(u) with u→v, together with 0).

The extra zero handles sources: they can start at zero. Set the start of v to E(v)−d(v). Evaluating this recurrence in topological order produces the worked schedule. Here is why it works for every finite DAG, rather than merely this table.

Maintain the invariant that the processed set contains every predecessor of each of its members, and that every processed E(v) is the greatest total duration of a directed path ending at v. Initially the processed set is empty, so both assertions hold. Remove a source of the remaining graph. All its original predecessors are already processed. Every path ending at this new vertex is either that single vertex or a predecessor path extended by this vertex. The recurrence takes exactly the largest of those possibilities. It therefore preserves both parts of the invariant.

Why can the process continue? Every nonempty finite DAG has a source. Otherwise, repeatedly following an incoming predecessor must eventually revisit a vertex because there are only finitely many; the intervening directed edges form a cycle, contradicting the DAG assumption. Removing a vertex cannot create a cycle. Each step decreases the number of unprocessed vertices by one, proving termination. The empty graph needs no steps and has completion time zero.

Feasibility and optimality are separate claims. For feasibility, each chosen start is at least every predecessor’s finish. Starts are nonnegative, and unlimited workers allow all overlaps. For optimality, tasks along any directed path must run in sequence, so that path’s total duration is a lower bound on every feasible completion time. The invariant says our schedule ends at the greatest of these path totals, attaining a lower bound. In the worked example A→D→F takes eleven minutes. This proves that ten minutes is impossible under the stated model.

Different legal source choices compute the same E values because the longest-path characterization does not depend on the order of calculation. This is stronger than checking two lists that happen to agree.

Apply

Repair the claim “A valid topological order is already an optimal parallel schedule.” It specifies precedence but neither durations nor simultaneous starts. The recurrence and lower-bound argument supply what is missing.

Next impose two workers. The supplied chart cannot run as drawn because three tasks overlap initially. Nevertheless, eleven minutes is still achievable here: run A during 0–3, B during 0–2, C during 2–6, D during 3–8, E during 6–8 and F during 8–11. Assign A then D then F to one worker, and B then C then E to the other. All prerequisites hold. Failure of one chart is not proof that its completion-time target is impossible.

In other instances the unlimited-worker bound is unattainable. Three independent one-minute tasks require at least two minutes on two workers, although every prerequisite path lasts only one minute. The recurrence remains a lower bound; it no longer automatically gives a feasible resource-constrained schedule.

Finally, add F→B to the original workshop. This creates B→D→F→B. If s(v) denotes a start time, each edge imposes s(v)≥s(u)+d(u). Adding these inequalities around the cycle gives zero at least the sum of the positive durations, an impossibility. This conclusion uses positive durations and the specified finish-before-start rule. If zero-duration tasks are admitted, an all-zero cycle can satisfy these non-strict inequalities with simultaneous starts. A source-removal failure alone would then need a more careful interpretation.

How many workers can the same job count and chain height require?

Restrict this question to n≥1 jobs, each taking exactly one discrete time slot, with all jobs available initially. Every worker performs at most one job per slot, and a predecessor must finish in an earlier slot. There are no setup times, release delays or preemption. The precedence order has height t: its longest chain contains t jobs, with 1≤t≤n. We want to finish in exactly t slots, the fastest possible completion time even with unlimited workers.

Let mbe the fewest workers allowing that deadline for a particular precedence graph. Across all graphs with these same n and t, the smallest possible m is ceil(n/t), while the largest possible m* is n−t+1. Prove both an inequality for every graph and an example attaining it; an example alone is not an extremal proof.

Same work and longest chain, different workforce needs

Every job takes one slot on one worker; all jobs are released initially, with no preemption, setup or communication delay. An arrow requires completion in an earlier slot. The deadline is the precedence height t.

Jobs n12345678 Height t123456 Workers123456 Precedence familyDisjoint chains, last possibly shorterWide starting layer, then one chainOne full chain plus isolated jobsReset workforce comparison

Predict whether 2 workers meet the 3-slot deadline before opening the exact schedule. These graphs all have n=6 jobs and height t=3.

Inspect exact schedule and certificates

Minimum finish with the selected crew: 3 slots. Deadline met. Minimum crew to meet t for this family: 2; width: 2. These last values follow from the family proofs below, and the bounded solver checks the selected crew independently.

1. Run jobs 1, 4.
2. Run jobs 2, 5.
3. Run jobs 3, 6.

The complete completed-set search visited 16 states and examined 33 nonempty ready-job subsets, including subsets rejected for capacity. This is subset-search work, not measured runtime or all implementation operations. At eight jobs the bounds are256states and6561subset candidates.

A large antichain need not run in one slot unless a deadline and precedence force it. Compare the starting bottleneck with the chain-plus-isolates case. All displayed schedules are temporary; written proofs and unfamiliar graphs supply the learning evidence.

The lower extreme: pack independent chains

Any m workers can complete at most mt unit jobs in t slots. Therefore m≥ceil(n/t), regardless of precedence. To attain the bound, set m=ceil(n/t) and partition the jobs into m independent chains: the first m−1 have length t and the last has length n−(m−1)t, which lies between one and t. The height is t; when m=1, the assumption t≤n and the ceiling force n=t. Give each chain one worker. Every chain finishes within t slots and a full chain takes exactly t, proving m=ceil(n/t) for this construction.

The upper extreme: a forced wide layer

For an arbitrary precedence graph, assign each job its longest-chain rank: one plus the greatest rank among its predecessors, or one for a source. A topological evaluation proves each rank lies between one and t. Jobs of the same rank are incomparable: a precedence path strictly increases the rank. Executing all rank-one jobs in slot one, rank-two jobs in slot two, and so on is a feasible t-slot schedule if enough workers are supplied.

Fix one chain containing t jobs. An antichain contains at most one of its jobs, plus at most the n−t jobs outside it. Thus every antichain, and in particular every rank level, has at most n−t+1 jobs. This proves that n−t+1 workers suffice for every graph of height t. It does not assert this workforce is necessary for every graph.

To attain the upper bound, take n−t+1 independent starting jobs and require all of them to precede a single chain of t−1 further jobs. A longest chain has one starting job followed by the tail, so its length is t. To finish by slot t, every starting job must finish in slot one: the dependent tail still needs t−1 slots. Hence at least n−t+1 workers are necessary, and using that many attains the deadline. When t=1, the tail is empty and all n jobs must run in the one available slot. When t=n, the construction is one chain and one worker suffices. These boundaries agree with both formulas.

Width is not the crew needed for this deadline

Take one chain of length t and n−t isolated jobs. Its width is n−t+1: all isolated jobs plus one chain job form an antichain. Nevertheless ceil(n/t) workers suffice. Put the chain on one worker for all t slots. The remaining workers have at least n−t available job slots because (ceil(n/t)−1)t≥n−t, so place the independent jobs there. The total-work bound proves this is optimal. For n=6,t=3, width is four but two workers meet the deadline; the forced-layer graph with the same n,t instead needs four workers.

An antichain means jobs may run concurrently, not that they must. Precedence plus the deadline forces the starting layer into a single slot in the upper-extreme construction. Without that argument, equating width to required crew would confuse possibility with necessity.

Why the bounded schedule search is complete

A state records the set of jobs already finished. In each next slot, choose any nonempty subset of jobs whose predecessors are all in that set, with subset size at most the worker count. This gives every possible next slot of a legal discrete schedule. Conversely each such transition respects capacity and precedence. No optimal schedule needs an entirely empty slot because jobs are released initially and an empty slot can be removed. The minimum number of transitions to the full set is therefore the exact optimum. Transitions only add jobs, so states can be processed in increasing bitmask order. The implementation examines at most256 states and6561 nonempty ready subsets at eight jobs; these count subset choices, not all machine operations or elapsed time. Large scheduling problems need different algorithms and complexity analysis.

The source comparison is the Spring2015 MIT6.042J final scheduling item, whose parameterized workforce constructions remained open in the source audit. These proofs make both general bounds and equality constructions explicit. They do not transfer unchanged to the earlier unequal-duration model, release-time changes or resource constraints not stated here.

Continue

The fresh tasks below ask you to prove the recurrence, change a bottleneck, add release times, and distinguish path bounds from worker constraints. Keep assumptions beside each claim. A numerical completion time without an attaining schedule and a lower-bound argument is not yet an optimality proof.

For a recap, revisit directed graphs and topological order and algorithm invariants and termination. They supply the source theorem and proof structure reused here; no advanced graph course is required before attempting these scheduling tasks.

Choose a focused return, then bring back a proof

Open only the group you need. These links reuse existing explanations and specific practice tasks; you do not need to complete their surrounding courses. Read the short preparation below, attempt a linked task before opening its worked solution, and record the assumptions and evidence you would use in your current argument.

Matching, Hall’s condition and König certificates

Preparation: A bipartite graph separates vertices into left and right parts, with edges only between parts. A matching uses no vertex twice. For a left subset S, its neighbor set N(S) contains all right vertices adjacent to at least one member. A vertex cover meets every edge.

Hall’s condition checks every left subset: its neighbors must number at least as many as its members. Checking individual degrees is insufficient. A matching and a vertex cover of the same size certify optimality, because disjoint matching edges require distinct covering vertices.

• Read Hall’s explanation and alternating-path construction.
• Translate distinct representatives into a matching problem.
• Prove the alternating-reachability cover meets every edge, then prove its size equals the maximum matching’s size.

Bring back: either an explicit deficient subset with fewer neighbors, or a matching and equal-size cover. Explain why the displayed objects are valid certificates; a claimed matching size alone is not the proof.

Partial orders, chains and Dilworth’s theorem

Preparation: A partial order is reflexive, antisymmetric and transitive. Distinct elements may be incomparable. A chain has every pair comparable; an antichain has no distinct comparable pair. A chain partition uses each element once.

For the split graph, make left and right copies of each element and join a left copy to a right copy when the first is strictly smaller. Selected matching edges become directed paths: strict order rules out cycles. A chain partition needs at least as many chains as any antichain has elements.

• Read the finite-poset and Dilworth proof; the separate Sperner material is optional for this return.
• Prove why a size-m matching gives n−m chains.
• Extract an antichain from the split-graph cover.

Bring back: a chain partition and an antichain of the same size, checking comparability and coverage element by element. Explain the lower bound that makes their equal sizes an optimality certificate.

Planarity: necessary bounds and actual obstructions

Preparation: A planar graph admits a drawing without edge crossings except at shared endpoints. In a connected plane drawing, n−m+f=2 counts vertices, edges and faces, including the unbounded face. “Simple” excludes loops and parallel edges.

For simple planar graphs with n≥3, m≤3n−6; if also bipartite, m≤2n−4. These are necessary bounds, not complete tests. Do not apply them without their hypotheses or conclude planarity merely because one inequality holds.

• Read the face-counting explanation.
• Derive the simple planar edge bound.
• Explain why the weaker bound does not certify planarity.

Bring back: the vertex and edge counts, the relevant graph assumptions, and a violated necessary bound when available. If no bound is violated, report that this test is inconclusive; a planar drawing would supply different evidence.

RSA correctness for all residue classes

Preparation: Work modulo n=pq with distinct primes p and q and positive exponents e,d satisfying ed≡1 modulo lcm(p−1,q−1). Congruence means the difference is divisible by the modulus. The Chinese remainder theorem combines agreement modulo p and modulo q into agreement modulo pq.

A message need not be relatively prime to n. For each prime separately, its residue is either zero, whose positive powers remain zero, or nonzero, where Fermat’s theorem applies. This case split extends decryption correctness to every residue; using Euler’s theorem only on units would leave a gap.

• Read modular exponentiation and the RSA correctness argument.
• Prove decryption when a message is divisible by a prime factor.
• Prove the repeated-squaring invariant.

Bring back: the zero/nonzero cases for both primes and the final CRT step. State separately what the arithmetic proves: toy decryption correctness does not establish secure encryption.

Finite probability: counting, indicators and Markov’s bound

Preparation: State a finite sample space and its probabilities, which are nonnegative and sum to one. Counting favorable outcomes divided by total outcomes is valid only when those outcomes are equally likely. An indicator is 1 when its event happens and 0 otherwise; its expectation is that event’s probability.

Finite linearity of expectation needs no independence. Independence may still be needed to multiply probabilities when calculating a particular indicator’s expectation. For a nonnegative random variable X and positive t, Markov gives P(X≥t)≤E(X)/t; a bound exceeding one can be replaced by one.

• Count subsets by a disjoint, exhaustive partition.
• Explain finite linearity for dependent indicators, then turn an average into an existence argument.
• Check a finite Markov bound; only the nonnegative-variable argument is needed here, not the later limit theorems.
• Combine a triangle indicator count with Markov’s inequality; focus on that task rather than the whole second-moment sequence.

Bring back: your sample space, an indicator sum, the marginal probabilities and a justified tail or existence conclusion. Name exactly where independence enters and distinguish a probability bound from an exact probability.

These are selected preparation and proof opportunities. Following links or recording answers does not establish mastery, independent review or equivalence to a full discrete-mathematics course.