This project was my final for a complexity class where we had to implement knapsack and 3SAT algorithms. It was also required to implement Travelling Salesman Problem algorithms, but I did not have enough time on my plate to finish those. You can see that I began the minimum spanning tree and disjoint set algorithms, but I did not complete them to the fullest.
Prior to this project I did not have almost any experience in python. I learned python from LinkedIn Learning course to be able to complete this project. I started from scratch and created this project.
On my free time I will be coming back to this project in the hopes of improving the algorithms and their efficeny. And, of course, to finish the TSP algorithms.
runKnapSackTests.py contains all the algorithms in the same file and runs the tests on them as well as gathers data. runSATTests.py does the same as former but for 3SAT problems.
Under UTILS you can find my problem instance generators, report generator (that uses matplotlib in most basic ways), and knapsack item class (I stored knapsack items as objects)
Under Algorithms folder you can see all the algorithms separately. Some of them I have included the pseudocode as well.
I am not entirely sure my DPLL works properly, eventhough it seems to be working. I would be glad to hear any feedbac you have to offer in order for me to improve.
This is my humble attempt and I am sure I will be coming back to it and reflecting. This will act as my timestamp of my experience.