Belief Propagation

The belief propagation calculations were done primarily in java. I setup classes for the different gates, which allowed graphs to be interconnected manually. Initially my gates were unidirectional (defining a single output connection for each gate), which didn't seem to work well for problem #2. I expanded the gates to propagate messages along each of the connections, but I haven't quite worked out all the bugs.
[ source code ]

Problem #1


                    X = (0.396774308501206,0.603225691498794)

                    X = (0.5495434492859159,0.4504565507140841)

                    X = (0.5717498162969694,0.4282501837030306)

                    X = (0.3276120778585072,0.6723879221414928)

                    X = (0.20222102786127988,0.7977789721387201)

                    X = (0.193958776691716,0.806041223308284)

                    X = (0.24935708266630935,0.7506429173336906)

                    X = (0.28262238905946857,0.7173776109405314)

                    X = (0.26663320526667134,0.7333667947333287)

                    X = (0.24331080777804376,0.7566891922219563)

                    X = (0.23869201890133354,0.7613079810986665)

                    X = (0.2477513494926365,0.7522486505073636)

                    X = (0.2547054602401131,0.7452945397598869)

                    X = (0.2534838379502617,0.7465161620497383)

                    X = (0.24941834481724728,0.7505816551827527)

                    X = (0.24798328731083005,0.7520167126891699)

                    X = (0.24928292304456828,0.7507170769554317)

                    X = (0.25065527002814425,0.7493447299718557)

                    X = (0.25068686040445265,0.7493131395955474)

Problem #2

(b)

8x8 : On the order of 2^8²
9x9 : On the order of 2^9² (≅ 131,072x longer than 8x8)
10x10 : On the order of 2^10² (≅ 68,719,476,736x longer than 8x8)

Belief Propagation

Problem #1

Problem #2

(a)

(b)