programming-assignment-1-algorithms

Students:

• CJ Alexander, 51691777
• Gabriel Burger, 89739553

Instructions

To run the matcher + verifier, you must have the latest version of python installed. Navigate to the src directory and run python3 main.py To test with different input files, add them to the data/input/ directory and then change the path in Line 13 of main.py

To test the verifier with invalid outputs, you must have the latest version of python installed. Navigate to the src/test/ directory and run python3 verifier_test.py

To view a visualization of our algorithm, you must have the latest version of python and seaborn installed. Seaborn is a visulization library, pip install seaborn to install, then Navigate to the src directory and run python3 algorithm_analysis.py

Sample Algorithm Visualization

As n increases the running time increases.

Directory Layout/Structure

• data/
  • inputs/: Sample Input Files
  • outputs/: Sample Output Files
• src/: All Source Code
  • modules/: Each component of our system: File Manipulation, Matcher, Plotter(For Data Visualization), and Verifier
  • test/: Tests for Verifier (Incorrect Cases)
    • test_verifier.py: A variety of tests for the Verifier on invalid outputs
  • main.py: Run matcher + verifier on input file
  • algorithm_analysis.py: Visualize algorithm complexity
• images/: Images: Images for this ReadMe

Assumptions

• Input files have completely randomized preference lists.

• Updating hospital preference list after they propose is currently O(n), on inputs of 64 and higher if the algorithm is too slow we can speed it up to O(1) using queues.

• Running time measured using perf_ counter() which provides better accuracy for performance testing.