This repository contains three related projects developed as part of the Análise e Síntese de Algoritmos course for the 2023/2024 academic year. These projects focus on optimization, simulation, and algorithm design, applying fundamental concepts in computer science and algorithm analysis.
The projects tackle real-world problems, such as optimizing the cutting of materials, simulating the spread of diseases in a population, and maximizing profit from toy production during the holiday season. Each project demonstrates the application of advanced algorithms to achieve optimal solutions.
- Tiago Branquinho (GitHub: tsbranquinho)
- Rafael Avelar (GitHub: RafaelAvelar14)
The repository is organized into three separate sub-projects, each with its own directory and related files. Below is a brief description of each sub-project:
- Description: This project focuses on optimizing the cutting process of marble slabs, aiming to produce the maximum possible value by making vertical and horizontal cuts. It uses dynamic programming to calculate the best combination of cuts.
- Directory Contents:
p1.cpp: C++ implementation for the marble cutting optimization.p1.pdf: Problem description and specifications for Project 1.Makefile: Build configuration for the project.README.md: Detailed instructions for Project 1.
- Description: This project simulates the transmission of diseases in a population using a directed graph representing social relationships. The goal is to compute the maximum number of transmission steps a disease can take through the network.
- Directory Contents:
p2.cpp: C++ implementation for the disease transmission simulation using Tarjan’s Algorithm for Strongly Connected Components (SCC).p2.pdf: Problem description and specifications for Project 2.Makefile: Build configuration for the project.README.md: Detailed instructions for Project 2.
- Description: This project optimizes toy production and sales during the Christmas season. The task is to determine the maximum profit obtainable by producing a set of toys and special packages, taking production limits into account. The solution is implemented using Python and the PuLP library for Linear Programming (LP).
- Directory Contents:
p3.py: Python implementation using the PuLP library to solve the toy production optimization problem.p3.pdf: Problem description and specifications for Project 3.Makefile: Build configuration for the project.README.md: Detailed instructions for Project 3.
Each sub-project is designed to be self-contained, and you can explore each project independently by navigating to its respective directory. You can find detailed instructions and specifications for each project in their individual README.md files.
The Makefile in each project provides build instructions to easily compile and execute the code.
These three projects demonstrate the application of algorithmic principles and optimization techniques to solve different types of real-world problems. From optimizing material cutting processes to simulating disease transmission and maximizing holiday season profits, each project showcases essential concepts in algorithm design and computational problem-solving.