Analysis and Synthesis of Algorithms: Programming Project II

Overview

This repository contains the source code, documentation, and presentation slides for Programming Project II of the Design of Algorithms (DA) course, Spring 2024 edition.

Project Description

In this project, we tackle the Travelling Salesperson Problem (TSP) in the context of routing for ocean shipping and urban deliveries. The main objectives are to implement various algorithms to find optimal routes for vehicles and to design efficient heuristics for solving the TSP. The project is divided into several tasks, including implementing backtracking and approximation algorithms, developing heuristics, and analyzing their performance.

Project Structure

• src: This folder contains the source code of our implementation, organized into modules for each algorithm and heuristic.
• docs: Here you can find the HTML documentation generated using Doxygen. It provides detailed information about the implemented algorithms, their time complexity, and usage instructions.
• Presentation: The presentation slides in PDF format are located here. These slides summarize our implementation, highlight key findings, and discuss the performance of our algorithms.

Getting Started

To get started with our project, follow these steps:

1. Clone this repository to your local machine.
2. Navigate to the src folder and explore the source code for each algorithm and heuristic.
3. Refer to the documentation in the docs folder for detailed information about each algorithm's implementation and time complexity.
4. Review the presentation slides in the Presentation folder to gain insights into our approach and results.

Contributors

This project was developed by :

• Ana Carolina Coutinho
• xxx
• xxx

as part of the Programming Project II assignment for the Design of Algorithms (DA) course.