The Project was done as part of University of Waterloo ECE650 Graduate coursework.
The project is to help the local police department with their installation of security cameras at traffic intersections. We will solve a particular kind of optimization problem, called the Vertex Cover problem, in this context. The idea is for the police to be able to minimize the number of cameras they need to install, and still be as effective as possible with their monitoring.
For this assignment, you need to: i)Take as input a series of commands that describe streets. ii)Use that input to construct a particular kind of undirected graph.
To Describe the the Project briefly it is Divided into 4 Assignments and a Analysis Report.
a) Assignment1 Deals with gathering GPS Coordinate Input of the Streets and Calculating the Intersections (Using Vertices and Edges Concept of an Undirected Graph) (Python)
b) Assignment2 Deals with Given a Set of Street Coordinates in the form of Vertices,Edges We used the BFS Algorithm to find the shortest path between two Vertices in the Graph. (C++)
c) In Assignment3 We create a random generate program in python to generate street coordinates for providing the Input to our Python program from assignment1. The Output from Assignment1 was provided to the Input of Assignment2 to calculate the shortest path between any two vertices. We incorporate Multi-threaded programming, IPC(Inter-Process Communication) using Pipes to connect the Standard Output,Input of various programs. (C++,Python)
d) In Assignment4 we solve the Vertex cover problem using CNF-SAT solver
e) In the Analysis Report we compare the performance of SAT Solver with two Approximation Algorithms and compare the results
Please Refer to Individual PDFs in the folder for more details and Information on the Project and how to execute them.