Question 1
Four tasks (Task 3, Task 4, Task 2, Task 1) must be scheduled with these constraints:
1. Task 3 must be before Task 4
2. Task 4 must be before Task 2
3. Task 3 must be before Task 2
4. Task 1 must be after Task 2
Which constraint is REDUNDANT (does not add new information beyond the others)?
Step-by-step solution (Redundancy Detection):
1. List all constraints:
1. Task 3 must be before Task 4
2. Task 4 must be before Task 2
3. Task 3 must be before Task 2
4. Task 1 must be after Task 2
2. Check for transitive relationships:
- From Constraint 1: Task 3 before Task 4
- From Constraint 2: Task 4 before Task 2
- By transitivity: Task 3 before Task 2
- This makes Constraint 3 unnecessary (redundant)
3. Verify other constraints are independent:
- Constraint 4 (Task 1 after Task 2) adds unique information
Answer: Constraint 3 is redundant
Key Strategy: Look for transitive relationships (A→B, B→C implies A→C).
1. List all constraints:
1. Task 3 must be before Task 4
2. Task 4 must be before Task 2
3. Task 3 must be before Task 2
4. Task 1 must be after Task 2
2. Check for transitive relationships:
- From Constraint 1: Task 3 before Task 4
- From Constraint 2: Task 4 before Task 2
- By transitivity: Task 3 before Task 2
- This makes Constraint 3 unnecessary (redundant)
3. Verify other constraints are independent:
- Constraint 4 (Task 1 after Task 2) adds unique information
Answer: Constraint 3 is redundant
Key Strategy: Look for transitive relationships (A→B, B→C implies A→C).