This repository contains all the exercises and assessments of the UC Desenho de Algoritmos, taught by Rosaldo Rossetti and Ana Paula Tomás at Integrated Master in Informatics and Computing Engineering [MIEIC] at the Faculty of Engineering of the University of Porto [FEUP].
Pieces of code for exercises and assessments, notes that I take during practical classes and other experiences using C and C++ languages. It is an authentic disorganized notebook.
Notes that I take during theoretical lectures, in Cpp files or Markdown
Varied exercises of easy, medium and difficult level, about the subject taught in the present week. They complement the weekly work developed during the practical classes.
A delivery company wants to see its business maximized according to the following scenarios:
- Optimization of the number of couriers;
- Optimization of the company's profit bgity delivering orders using lower cost vans;
- Optimization of express deliveries, improving average delivery time;
The following project implements solutions for each of the cases using some studied algorithms, such as greedy, bin-packing, knapsack and job scheduling.
The original repository can be viewed here.
In addition to the C++ language, we also use Python and Bash to assess the complexity of the algorithms. We built a script (packagesGenerator.py) that generates N orders based on the original data provided by the teachers, ensuring that a percentage are express orders. Then the project script is called via a Bash script, which injects the orders file and the necessary parameters into a caseX.sh, returning the time in seconds of each execution to the output.csv file. The cycle is repeated 10 times in increments of 2000 units for each case. The advantage of .csv is that it can be interpreted by Excel and that's where we were able to build a graph, with regression lines to evaluate the linearity of each case.
- Francisco João Gonçalves Calado Araújo
- Fábio Araújo de Sá
- Marcos William Ferreira Pinto
A travel agency wants to organize routes and connections for its customers in the best possible way. For this you need different features:
- Groups without separation:
- Maximization of the number of elements of the group to be transported;
- Minimization of the number of transfers of the trip;
- Split groups:
- Determine a referral for a group;
- Change an existing route if the group size increases;
- Determine the maximum size of a group and a forwarding;
- Determining when the full group would meet again at the destination;
- Determine the maximum waiting time that group members can wait at intermediate stops;
The following project implements solutions for each of the cases using some studied algorithms. The original repository can be viewed here.
In addition to the C++ language, we also use Python and Bash to assess the complexity of the algorithms. We built a script (graphGenerator.py) that generates a DAG graph with N nodes and N * FACTOR edges, which are based on the original data provided by the teachers, ensuring time and cost bounds. Then the project script is called via a Bash script, which injects the orders file and the necessary parameters into a timer.sh, returning the time in seconds of each execution to the output.csv file. For some cases we vary the number of nodes (and consequently the size of the graph) with increments of 1000 for 10 cycles. In other cases, we vary the number of people traveling and the necessary paths with increments of 10 for 10 cicles. The advantage of .csv is that it can be interpreted by Excel and that's where we were able to build a graph, with regression lines to evaluate the linearity of each case.
The tests for each case were semi-automatic. We created a small graph of 10 nodes but complex enough to serve as a basis for all possible scenarios. Then we created a script in Bash that injected the necessary parameters, showing the input and the output. All tests passed, both with small graphs (10 nodes) and large graphs (5000 nodes).
- Fábio Araújo de Sá
- Marcos William Ferreira Pinto
@ Fábio Araújo de Sá
2021/2022