(In this post, Rensselaer graduate student Salles Viana Gomes de Magalhães talks about his First Place Overall Award in the 2016 TripAdvisor programming challenge, held September 17. Graduate and undergraduate students from 18 select universities in the United States and Canada were invited to compete in the event, with cash prizes awarded to top two students from each school, and additional prizes to the top three students overall.

Prior to this win, Gomes de Magalhães had already racked up an impressive trophy case within his field. His wins include: second place in GISCUP 2015, and fourth place at GISCUP 2014 – the Geographic Information Systems (GIS) focused algorithm competition, a programming competition co-located with the Association for Computing Machinery SIGSPATIAL GIS conference; three first place and one second place win in Upsilon Pi Epsilon honor society contests hosted at Rensselaer; first place as part of a two-person team competing in the Microsoft College Code Competition, and a recent first place win in the Bloomberg CodeCon competition, both of which were held at Rensselaer.)

Can you explain the challenge that TripAdvisor posed?

Usually the hosts of programming contests propose one or more challenges and the competitors have a deadline to solve these problems. Thus, it is important to find a balance between the quality of the solutions, number of problems tried to solve, and the efficiency of the algorithms developed.

In the TripAdvisor challenge, a job-scheduling problem was proposed and the competitors were given four hours to develop algorithms to solve that problem. In the proposed problem, we had to develop algorithms to schedule robots such that these robots can efficiently complete jobs. In other words, we were given a set of jobs (that could represent, for example, the construction of a house, the assembly of a car, etc.) each one composed of a set of tasks (for example a car assembly is composed of: assembling the engine, installing the electric wires, painting the car body, etc). The objective was to find a good way to manage the limited amount of resources (robots) so that they can complete all the jobs as efficiently as possible.

There are several variations of the job-scheduling problem (with many practical applications like optimizing the assembly line of a company) and the main challenges of the variation proposed by TripAdvisor are the many constraints our solutions had to satisfy. For example, each job can have a different importance and the solutions should try to complete the jobs with highest importance first. Also, jobs had different starting times (that is, the robots should not start working on some jobs before a certain time).

During the evaluation, several instances of the problem (each instance is represented by a set of jobs and robots) were given as input for our programs and the quality of the schedule generated by our algorithms was evaluated. The quality of our code was also evaluated.

What was your approach?

There are several possible ways to develop good algorithms for solving this kind of problem. However, since we were given four hours to submit the solutions, I had to find a balance between the quality of the solution and the time required to implement and test it. My approach was to develop an algorithm that was simple enough to be coded quickly so that, after I had this initial solution working, I had time to tune it in order to try to obtain better solutions. Indeed, the first algorithm I submitted was very simple and the solutions it obtained were not as good as the solutions obtained by the competitors (during the competition, TripAdvisor provided feedback informing how good our algorithms were in comparison with the competitors).

What got you into programming?

I have liked programming since I was a computer science undergraduate student at Universidade Federal de Viçosa (UFV) in Brazil. Indeed, the courses I liked most were related to algorithms.

One of my professors at UFV, Professor Andre Gustavo dos Santos, started a project where the idea was to practice for programming competitions. In this project, he taught a course called “Programming Challenges” where several topics related to algorithms and data structures were practiced, and hosted competitions (often on weekends) where the students could practice problem solving. Attending this course and practicing with my colleagues was very important to me because I not only learned how to code better, but also how to manage the time to solve the problems quickly.

Furthermore, since the beginning of my undergraduate studies I’ve been working on research projects where the objective is to develop efficient computer algorithms. During that time, my academic adviser, Professor Marcus V.A. Andrade at UFV, visited Rensselaer Polytechnic Institute and developed several projects in collaboration with Rensselaer Professor W. Randolph Franklin. After being involved in these projects, I decided to apply to the doctoral program in computer science at RPI and I started my studies here in 2014.

Similar to the experience I had at UFV, at RPI I had several opportunities to continue practicing for programming competitions. For example, since 2014 my adviser (Prof. Randolph) has been motivating our research group to attend the Geographic Information Systems (GIS) focused algorithm competition GISCUP, a programming competition co-located with the Association for Computing Machinery SIGSPATIAL GIS conference. Also, the Upsilon Pi Epsilon honor society and some companies often host programming contests at RPI. Finally, since the beginning of my doctoral studies I’ve been working as a teaching assistant in courses on graph theory and data structures, two subjects directly related to development of algorithms, what is also an excellent way to improve my programming skills.

What are your long-term goals?

I plan to finish my doctoral studies by the end of next year and work as a professor in Brazil, where I intend to continue working on research projects related to my thesis topic. Furthermore, I intend to join projects where the objective is to motivate students to attend programming competitions and to enjoy computer programming.