Bellow you can find some reports, source codes, and presentations about academic projects developed through graduate and postgraduate studies. Some reports are only available in Portuguese. Sorry about that :/.
Developed in the Prof. Daniel Schwabe's “Semantic Web” course at Departamento de Informática of PUC-Rio.
This presentation contains information about the following popular ontologies: Dublin Core and Bibliographic Ontology.
Developed in the Prof. Marcus V. S. Poggi de Aragão's “Combinatorial Optimization” course at Departamento de Informática of PUC-Rio.
This presentation includes the Network Simplex method, the Cunningham's Anti-Cycling pivot rule, and the Ahuja at al.'s Anti-Stalling Pivot Rule.
Developed in the “Machine Learning II” course given by Prof. Ruy L. Milidiú at Departamento de Informática of PUC-Rio.
Joint work with Bernardo A. Pires.
Clause identification is a kind of shallow parsing and is important for several more elaborated Natural Language Processing tasks like Semantic Role Labeling and Dependency Parsing. This project aims in developing a machine learning system for clause identification using the technique called Entropy Guided Transformation Learning.
Developed in the “Polyhedral Combinatorics” course given by Prof. Marcus V. S. Poggi de Aragão at Departamento de Informática of PUC-Rio.
The Orienteering Problem (OP) is related to the Prize-Collecting Traveling Salesman Problem (PCTSP). OP consists of finding a tour on a graph with edge weights and node prizes such that the total amount of collected prizes is maximum and the tour length not exceed a given limit. The difference between OP and PCTSP is that in OP the aim is to maximize the collected prizes amount and there is a constraint on the maximum tour length. In PCTSP, conversely, the aim is to minimize the tour length and there is a constraint on the minimum collected prizes amount.
This project consists of developing a method to generate sub-tour elimination constraints in a branch-and-cut algorithm for the OP. This separation problem can be formulated as a min-cut problem. The min-cut algorithm used is the one provided in the Concorde package. The CPLEX package is used to provide the branch-and-cut framework. The Concert C++ technology is used to interact with the framework. The cuts are generated using the callback scheme.
Developed in the “Machine Learning I” course given by Prof. Ruy L. Milidiú at Departamento de Informática of PUC-Rio.
Joint work with Carlos Crestana.
Semantic Role Labeling (SRL) is an important problem in the field of Natural Language Processing. SRL consists in identifying the modifiers and arguments of each verb in a sentence. Some examples of arguments are subject and direct object. This problem was proposed as shared task in three editions of the Conference on Computational Natural Language Learning (CoNLL 2004, 2005, and 2008). This project aims in developing a SRL machine learning system for English language texts. The system is based on the machine learning technique Entropy Guided Transformation Learning. More specifically, the system uses committees of ETL models.
This is my Master's Thesis taken in 2005 at PUC-Rio. My advisor was Prof. Celso C. Ribeiro.
Sequencing by hybridization is an attractive alternative for DNA sequencing. This novel method can be less time and cost consuming than the techniques applied nowadays. A very important step of this method is to solve a combinatorial problem formulated as a special case of the prize-collecting traveling salesman problem. In this work, we propose a new multistart construtive heuristic to solve this problem. A learning strategy based on adaptive memory and a vocabulary building procedure are used to improve the performance of the multistart heuristic. The adaptive memory is used to intensify the construction of new solutions with the elements that appear frequently in the best solutions previously found by the multistart heuristic. The objective of the vocabulary building procedure is to construct new solutions combining parts of good solutions. Computational experiments have shown that these two methods significantly improves the performance of the multistart heuristic and are particularly suitable for scheduling problems whose best solutions are in most cases built by blocks of elements that appear together very often. The proposed heuristic obtains systematically better solutions and is less time consuming than the best algorithms found in the literature.
Developed in the “Design and Analysis of Algorithms” course given by Prof. Ruy L. Milidiú at Departamento de Informática of PUC-Rio.
This work consists of the implementation of three algorithms for generating Minimum Spanning Tree (MST) on a graph. The algorithms are: (i) the Kruskal's algorithm, (ii) the Prim's algorithm using binomial heaps, and (iii) the Prim's algorithm using Fibonacci heaps.
Developed in the “Computational Geometry” course given by Prof. Luiz Henrique de Figueiredo at Instituto de Matemática Pura e Aplicada (IMPA).
Joint work with Michel Alain Quintana Truyenque.
Java Applet illustrating the execution of two geometry algorithms for the problem of finding the Minimal Enclosing Circle (MEC) of a given set of points. The first algorithm has O(n^2) time complexity and the second is the Welzl's randomized algorithm with O(n) time complexity.
Developed in the “Metaheuristics” course given by Prof. Celso C. Ribeiro at Departamento de Informática of PUC-Rio.
In this report we present a review of two works. The first one is a survey about the Ant Optimization Colony (ACO) metaheuristic. It presents a historical evolution of that metaheuristic. The second work presents several ACO algorithms for the Quadratic Assignment Problem (QAP). This work presents a detailed experimental comparison among these algorithms.
Developed in the “Metaheuristics” course given by Prof. Celso C. Ribeiro at Departamento de Informática of PUC-Rio.
This work presents the Quadratic Assignment Problem (QAP) from two perspectives: theoretically and practically. First, it discusses the computational complexity of the problem. Then, it presents different heuristics from the literature for this important problem. More specifically, a randomized constructive heuristic and local search heuristics based on different neighborhood structures are presented. From these algorithms, two metaheuristic algorithms are derived: (i) a Greedy Randomized Adaptive Search Procedure (GRASP) and (ii) an Ant Colony Optimization (ACO). The ACO algorithm is based on the MAX-MIN version. All these algorithms are developed and several experimental evaluations are performed on them.
Developed in the “Concurrent and Parallel Programming” course given by Prof. Noemi Rodriguez at Departamento de Informática of PUC-Rio.
Joint work with Bruno Oliveira Silvestre.
This project presents different implementations of parallel methods for numerical integration. A simple static method and different strategies for an adaptive method are presented. The implementation is based on the LAM-MPI package, a Message Passing Interface (MPI) implementation.
Developed in the “Concurrent and Parallel Programming” course given by Prof. Noemi Rodriguez at Departamento de Informática of PUC-Rio.
Joint work with Alexandre Rocha Duarte.
This project presents and evaluates different strategies for parallel implementation of Ant Colony Optimization (ACO) heuristics. The Quadratic Assignment Problem (QAP) is used as case study. Experimental evaluation of the developed algorithms is presented and discussed. The implementation is based on the LAM-MPI package, a Message Passing Interface (MPI) implementation.
Developed in the “Hardware Laboratory” course given by Prof. Paulo A. Pagliosa at Departamento de Computação e Estatística of UFMS.
Joint work with Delair O. Martinelli Jr.
This report presents a tutorial on Win32 Communication API.
Developed in the “Parallel Algorithms” course given by Profs. Henrique Mongelli and Édson Cáceres at Departamento de Computação e Estatística of UFMS.
Implementation of the parallel algorithm called Bitonic sort. This algorithm respect the BSP/CGM model. The LAM-MPI package (an Message Passing Interface implementation) is used.
Developed in the “Parallel Algorithms” course given by Profs. Henrique Mongelli and Édson Cáceres at Departamento de Computação e Estatística of UFMS.
This work presents a report and an implementation of the Fox's parallel algorithm for matrix multiplication. This algorithm is based on the BSP/CGM model. The implementation is based on LAM-MPI package (an Message Passing Interface implementation).
Developed in the “Database II” course given by Prof. Kelly Adriana de Oliveira at Departamento de Computação e Estatística of UFMS.
Joint work with Delair O. Martinelli Jr. and Marcos Leal Medeiros.
This work presents a tutorial on recovery control on MySQL Database Server.
Developed in the “Algorithm Complexity” course given by Prof. Celso C. Ribeiro at Departamento de Computação e Estatística of UFMS.
Joint work with Delair O. Martinelli Jr. and Marcos Leal Medeiros.
This work presents complexity analysis, implementation and experimental evaluation of seven sorting algorithms. The algorithms are: bubble sort, insertion sort, selection sort, merge sort, heap sort, quick sort, and box sort.
Developed in the “Algorithm Complexity” course given by Prof. Celso C. Ribeiro at Departamento de Computação e Estatística of UFMS.
Joint work with Delair O. Martinelli Jr. and Marcos Leal Medeiros.
This work presents complexity analysis, implementation, and experimental evaluation of two algorithms for the 2-D Closest Pair Problem. The algorithms are: brute force and divide-and-conquer.
Developed in the “Algorithm Complexity” course given by Prof. Celso C. Ribeiro at Departamento de Computação e Estatística of UFMS.
Joint work with Delair O. Martinelli Jr. and Marcos Leal Medeiros.
This work presents a literature review and some implementations for the classic Knapsack Problem. Two algorithms are implemented: the trivial brute force and the classic dynamic programming.
Developed in the “Algorithm Complexity” course given by Prof. Celso C. Ribeiro at Departamento de Computação e Estatística of UFMS.
Joint work with Delair O. Martinelli Jr. and Marcos Leal Medeiros.
This work presents complexity analysis, implementation, and experimental evaluation of several heuristics for the Traveling Salesman Problem (TSP).
Except where otherwise noted, content on this wiki is licensed under the following license:Public Domain