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

0 votes
and how do we choose in each step which 2 nodes to apply the "apply algorithm" on?

for example how do we come to apply(->, N19, N22)?

I mean from the first BDD (φ) we choose the nodes regarding the order (a<b<c...) and run the apply algorithm but how do we choose from the second BDD (β)?
related to an answer for: solution week 2
in * TF "Emb. Sys. and Rob." by (1.7k points)

1 Answer

+1 vote
Best answer

Have a look at the code of the Apply algorithm: When being called for two nodes a and b and some operation op, it inspects first the variables v_a and v_b in the labels of the root nodes of the given BDDs. The maximum of them becomes the label of the new root node, and the two children are computed by recursive calls of the Apply algorithm. The arguments of these recursive calls are determined by three cases:

  1. v_a = v_b : low = Apply(op,low(a),low(b)) and high = Apply(op,high(a),high(b))
  2. v_a < v_b : low = Apply(op,a,low(b)) and high = Apply(op,a,high(b))
  3. v_a > v_b : low = Apply(op,low(a),b) and high = Apply(op,high(a),b)

The result BDD is then (max(v_a,v_b) ? high : low), but before creating such a new node, we check whether it already exists. Does this help? You may also check slide 103 for a one page description of the algorithm covering all cases.

by (166k points)
selected by
Imprint | Privacy Policy