A Competition-based Learning Environment

A Classroom Competition to celebrate Euler’s 300th Birthday

CJ Chung

Associate Professor of Computer Science

Lawrence Technological University

Southfield, MI 48075

chung@LTU.edu

We can learn more, if we are motivated. As an educator, I believe one of the best ways to motivate students is to introduce competitions in class. In the fall 2007 semester in my Intelligent Systems class, we had a special classroom competition to solve the traveling salesman problem (TSP) that searches for the shortest route to visit a collection of cities and return to the starting point. Despite an intensive study by mathematicians, computer scientists, operations researchers, and others, it remains an open question whether or not an efficient general solution method exists.

This problem was chosen especially in 2007 in order to celebrate Euler’s 300^th Birthday since one of the first instances of the traveling salesman problem was from him.

The classroom competition problem, however, was more difficult with an additional constraint: there exists a list of two neighbor cities, n and m that must be visited right after. For example, if n is visited, then m must be visited right next. (Or m is visited, then n must be visited next).

Students were asked to use either branch-and-bound based A* algorithm or Evolutionary search algorithms learned in class to solve the “NP (nondeterministic polynomial time) Hard” problem. The competition was held on December 4^th, 2007.

The winner of the competition was Erica Stephens (1^st picture above). Her program using A* like algorithm was flawless and solved all 5 test cases. She received a LTU cup (soup bowl) as well as a $10 bookstore gift certificate as prizes sponsored by Math and Computer Science Department. There were two special prizes winners:

Nathan Lucas (2^nd picture above) gave the best result for the 14 cities problem in Burma. His evolutionary algorithm gave 34.88. Best known solution is 33.23. He received a $10 bookstore gift certificate as prizes sponsored by Math and Computer Science Department.

Ghassan Tahhan (3^rd picture above) won an LTU cup sponsored by Math and Computer Science Department. His solution was the best for the 51 city problem created by Elion and Christofides. The best known solution is 426. Ghassan’s solution was 513.61.

This problem was chosen especially in 2007 in order to celebrate Euler’s 300th Birthday since one of the first instances of the traveling salesman problem was from him.

The classroom competition problem, however, was more difficult with an additional constraint: there exists a list of two neighbor cities, n and m that must be visited right after. For example, if n is visited, then m must be visited right next. (Or m is visited, then n must be visited next).

This problem was chosen especially in 2007 in order to celebrate Euler’s 300^th Birthday since one of the first instances of the traveling salesman problem was from him.