Demo Video
This video demonstrates the BST equivalence detection process and showcases the project's capabilities.
Project Overview
I created a three-step parallel algorithm for computing binary search tree equivalences. My approach avoids the inefficiency of directly comparing BSTs (e.g., via in-order traversals) by using the following steps:
- Hashing: I hashed each BST to create a unique identifier. I explored two implementations: (1) one goroutine per BST and (2) a limited number of "hash-worker" goroutines.
- Hash Grouping: I grouped BSTs with the same hash. I compared four implementations: (1) a central manager goroutine updating the hash map, (2) each hash-worker goroutine directly updating the map with a mutex lock, and two hybrid approaches with multiple "data-worker" goroutines (⅓ and ⅔ of the hash worker count) receiving work from hash workers and updating the map with a mutex lock.
- In-Order Traversal Comparison: I compared BSTs within the same hash group (potential duplicates) via in-order traversal to confirm equivalence. I tested two implementations: (1) one goroutine per comparison and (2) a limited number of "comp-worker" goroutines handling comparisons through a custom buffer. Due to the potential size of the comparison matrix, I used a single test case.
I utilized parallel programming throughout to significantly improve efficiency. This project provided valuable experience with Go's simplified concurrency model, including goroutines and channels. Key learning outcomes include:
- Understanding and applying Go's concurrency primitives (goroutines and channels).
- Comparing different concurrent approaches and reasoning about tradeoffs.
- Analyzing the balance between lock contention, communication overhead, and the degree of parallelism.
- Implementing a custom concurrent communication channel (concurrent buffer).
My project demonstrates a scalable and performant method for identifying equivalent BSTs.