Information

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

Sign in

[Part10] Theta-Trees

In the following exercises, there are four activities, which must be inserted into 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 the earliest completion time of the node ectA in the theta-tree, etc.


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 time complexity of adding a new activity into a theta-tree of \(n\) activities?