A public repository of some of the materials of the CISC320 Spring 2021 AlgoTutorBot Adventure

This project is maintained by acbart

  • Watch the video below.
  • You will not need to join the Ohyay workspace today.
  • This assignment will be an individual submission; do not work with others.
  • You will submit your Python code to GradeScope for this assignment.
  • This assignment has a Leaderboard on GradeScope.



Direct Ada to quickly navigate between all the energy cores!

  1. Read in a file containing the distances between all the cores
  2. Find the shortest path that takes you to all the cores and back to the first one.
  3. Print out the order you attack the cores and then the total cost of the tour

Formal Specification

Problem: Find the approximately shortest path that visits every vertex and returns to the first one.

Input: The filename of a local file containing a sequence of distances in a 2D matrix. Unlike previous assignments, the first line is not the number of items. Instead, every line consists of N numbers, and there are N lines. Each individual number represents the distance between the vertices given by the indices of the matrix.

An example input file is below:

0  3  4  2  7
3  0  4  6  3
4  4  0  5  8
2  6  5  0  6
7  3  8  6  0

In this example, there are 5 vertices. The distance between the first vertex and the second vertex is 3. The distance between the first vertex and the fourth vertex is 2. A vertex will always be 0 units away from itself.

Output: The sequence of indices chosen to minimize the total distance travelled, and the calculated total cost of that tour.

An example of output is below:


The total distance calculation is broken down below:

Distance from 4 to 1: 3
              1 to 0: 3
              0 to 3: 2
              3 to 2: 5
              2 to 4: 8
                      = 21


This problem is known as the Travelling Salesman Problem, and it is NP-Hard. You are not going to be able to find optimal solutions for most reasonable sized inputs - and most of the floors have a lot more than 5 energy cores.

Instead, you will want to find approximate solutions: answers that are valid tours (connect every vertex without repeats), but may not be as short as possible.

I strongly recommnd this excellent webpage for more background on this problem and suggestions on approximation algorithms that can work surprisingly well:

I also recommend this video, which can help explain some of the more common, but complex, approaches:

Autograder Points

The autograder will accept any output tours that visit each core once and calculate their cost correctly. This means that, to earn the minimal number of points, you do not need to actually find very good answers. As long as you produce correct tours, you will earn the autograder points. Once you submit an answer that has all correct tours, you will be given access to a video and ????.

However, for every input, I have written my own baseline solution. For every test case of mine that you meet or outperform, you earn half a point of extra credit - with twenty test cases, that means you have the potential to earn up to 10 extra credit points. Further, if you manage to meet or outperform my baseline for every answer, then you will unlock a small minor prize.

Time Complexity

You will not need to explain the time complexity of your solution. In fact, there is no target threshold that we care about. Your algorithm can be as inefficient as you want, as long as it works fast for the given inputs.

However, you must still explain your program and algorithms that you used.


You will be submitting this assignment through GradeScope. The same rules will apply for all coding assignments in this course, so you should read them all carefully: GradeScope Instructions

Critically, this is an individual assignment. Do not share code with any of your group mates! Again, do not share code with other students on this assignment.

For this project, you will need to create an that solves the problem above, a that explains your solution at a high level, and a that tests your solution in some way.

All parts of your solution, including both the program, the tests, and the file should be submitted on GradeScope:


You will be graded on the following components:

Note that unclear code and answers can cause a huge penalty to your grade. We are not being strict on coding style, but we shouldn’t have to run your code through a deobfuscator to figure out what it does. You might also lose points if you ignore instructions in this assignment, or bypass the autograder, even if the autograder gives you points.