OCaml Implementation of Binary Decision Diagrams
Binary decision diagrams (BDDs) belong to a class of data structures that represent Boolean functions. In particular, they are very useful in finding solutions to such functions as the number of variables increases because they do so efficiently, or in general O(n) time in the where n is the number of variables appearing in the function. This is an implementation of this data structure written in Ocaml.
This project was a team submission for a class final assignment. We chose BDDs because of their utility in a variety of combinatorial problems such as circuit testing and finding shortest paths. Their importance was recognized by Donald Knuth who called them "one of the only really fundamental data structures that came out in the last twenty-five years."
I am proud of this project because I took the lead and wrote majority of the code implementing the actual algorithms while my partners wrote the lexer and parser. I ensured our team learned how to use Github as version control and a way to consolidate the code written on separate machines. The project became a full-fledged application with a primitive GUI and a well-designed backend.