Algorithm Implementations and Performance for algorithms from the Algorithms and Data Structures (Part 1) course from Princeton University. Please see the Repository Wiki for algorithm performance results.
Each sub-project (except HelloWorld) comes with full maven support and can be built using mvn package. To run the application, refer to the sections below.
All projects require Apache Maven and JDK to be installed and relevant paths set up on the target machine. Some projects have scripts which might require Python 3.5 or higher in order to function correctly.
- cd DynamicConnectivity
- mvn clean && mvn package
- cd unionfind/
The performance testing client can be run using any of the 3 algorithms (QuickFind, QuickUnion or WeightedUnion) to analyze their performance. To change the algorithm used, simply change the object creation line in the client file by commenting and uncommenting the respective object initalization lines.
The client takes 2 arguments as inputs - the first is a file containing all the union operations to perform using the algorithm and the second is a file containing all the connection test queries. Sample files have been provided in largeDataSet_.txt. under the input directory. A python script has also been provided under inputGenerator.py to create custom sized large random datasets for performance testing.
Sample client command:
java -cp target/java -cp ./target/unionfind-1.0-SNAPSHOT.jar algorithms.UnionFind_Client .\input\largeDataSet_UnionInput.txt .\input\largeDataSet_FindInput.txt
Sample Dataset Generation
python inputDataGenerator.py <numElements> <numOperations> <Union||Find> <outputFilePath>- numElements - Maximum number of elements in connectivity set
- numOperations - Number of query / union operations to generate
- Union || Find - File type (Query vs Union)
- outputFilePath - Path of output file (will be created if it doesnt exist or will be overwritten if it does)