Projects
City Tasks Assigment
This projects consists on assigning some tasks to some teams during a campaign (e.g. cleaning and maintenance of a city or packages distribution) minimising the time and cost. To solve the problem we’ve implemented an exact method that uses linear programming techniques (such as branch and bound algorithm) in order to obtain the optimal solution, and, because this method has a hi complexity, we also implement the simulated annealing metaheuristic. With performance in mind, algorithms will be implemented using C and later extended to Python for ease of use.
Aditionaly, because in real life the times and costs of doing each tasks are known with certain uncertainty (assumed to be normal), we implement a Monte Carlo simulation to analyse how the objetives vary. A similar simulation can be done to observe how different preferences on the objectives affect to the overall time and cost.
Topological Data Analysis (TDA)
TDA aims to extract information from noisy, incomplete or complex dataset using techniques from topology like persistent homology. This projects provide multiple data structures and algorithms used in TDA. The main class, AlphaComplex, is a simple implementation can be used to compute the persistence homology of a set of points.
Advanced Encryption Standard (AES)
AES algorithm is a symmetric key encryption block cipher capable of handling 128 bits (16 bytes) blocks using keys of size 128, 192 or 256 bits. AES consists of multiple encryption rounds. On each, the cipher performs a series of mathematics transformations. With performance in mind, the algorithm will be implemented using cython.
Assembly Line Balancing Problem (ALBP)
The ALBP consists of assigning tasks to an ordered sequence of stations such that the precedence relations among the tasks are satisfied, and some performance measure is optimized. There are some algorithms designed for this problem. The genetic algorithm approach is easy to program and can be easily adapted for other problems such as the travelling salesman problem. To try to find a better solution faster we defined an heuristic mutation operator. It assigns a random station to a task that violates the precedence relations. We also include multiple selection methods (roulette, tournament, rank), mutation operators (random, swap, scramble, inverse), crossover operators (Double Point, Single Point, Uniform). To compare the performance, we define comparations methods.
Network
A network (also known as graph) is a mathematical structure made up by a set of points or nodes and a set of edges (links between two nodes). Euler is regarded as the father of graph theory since he published the first (known) paper on this field. Since Euler graph theory has been used to solve a whole host of problems, such as route planning or even to fight an outbreak of a disease.
This project provides a simple implementation of a graph data structure and multiple algorithms in the blazingly fast C++.
First steps of a JavaScript compiler
Compilers translate the programming language’s source code to machine code dedicated to a specific machine. The compilation process is divided into 6 phases:
- Lexical analysis
- Syntax analysis
- Semantic analysis
- Intermediate code generation
- Optimization
- Code generation
This project focuses on the first 3 phases for a simplified version of JavaScript.
Tokyo Subway
A* is a path search algorithm. In this project we will use it for finding the shortest path between two stations of a simplified version of the Tokyo subway. A* achieves better performance than Dijkstra algorithm using an heuristic to guide the search. For ease of use we implemented a GUI to execute the A* search.
