Information

Author(s) Guillaume Derval
Deadline No deadline
Submission limit No limitation

Sign in

[Part 10] Theta trees

In the following exercises, we give you four activities, which must be inserted in a theta tree. It will form a tree like this:

theta-trees/ect.png

You then have to enter the content of the theta-tree in the following form:

ectA,ectB,ectC,ectD,ectE,ectF,ectG

with ectA being (obviously) the earliest completion time of the node A in the theta-tree.


Question 1:
  • est: 23; duration: 26
  • est: 0; duration: 26
  • est: 24; duration 3
  • est: 22; duration: 3
Question 2:
  • est: 24; duration 26
  • est: 23; duration: 3
  • est: 0; duration: 3
  • est: 22; duration: 26
Question 3:
  • est: 20; duration: 13
  • est: 0; duration 12
  • est: 10; duration: 5
  • est: 30; duration: 2
Question 4:
  • est: 20; duration: 13
  • est: 10; duration: 14
  • est: 0; duration 12
  • est: 30; duration: 2
Question 5: Complexity

What is the (amortized) complexity of adding a new activity in a theta-tree?