Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


538 users

+1 vote


I´ve got another question according the tutors presentation. It´s about the Compose Algorithm this time.

I don´t quite understand the steps made from Screenshot 1 to Screenshot 2. Please explain with the corresponding lines of the algorithm since in my opinion the only two ways to stop the algorithm:

  1. x (the variable that gets replaced) is greater than label(phi) (the tree in which x gets replaced) in terms of the variable order
  2. x = label(phi)
But I don´t see any of those two cases in Screenshot 1, since the left subtree is always phi and the right subtree is always alpha (or am I wrong?).
Thanks in advance for any responses.
Best regards
Marvin Ballat
in # Mandatory Modules Bachelor by (1.2k points)

1 Answer

+2 votes
Best answer

There are again multiple steps happening at once. If we simply follow the algorithm, then the b node is "pulled up" and the Compose-Node goes down one level. Once phi is only True or False case 1 (from your question) applies.

Here we can see this directly, because a does not occur in phi. Therefore case 2 will never apply. We will simply go down recursively until finally case 1 applies. Intuitively: We want to replace a. a does not occur in phi. Therefore we leave phi as it is.

This is a shortcut that is easy to see for humans, and you are allowed to do that in the exam (but better write a comment next to it). The computer can't see that since it only goes through the tree node by node and does not have an "overview".

by (2.4k points)
selected by
Alright, that makes a lot of sense. Thank you!

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
+1 vote
1 answer
+1 vote
1 answer
Imprint | Privacy Policy