Implementation of 4th problem (chapter 3) from Algorithm Design Book by Kleinberg and Tardos
This script will first generate 400 test cases and dump them in test_cases.json file. For first 10 test cases, brute force method will be used to find out the solution. Then we will see that the implemented algorithm will produce the same results for the first 10 test cases as obtained from brute force method.
Finally, a runtime graph will be plotted for the validation of performance of the algorithm.
This assignment was done in Ubuntu 18.04. For linux system, Install the following packages
$ sudo apt install python-pip
$ pip install numpy
$ pip install matplotlib
$ sudo apt-get install python-tkRun the run.sh file as
./run.sh