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.
  • You will submit your Python code to GradeScope for this assignment.
  • There is a second video on GradeScope after you pass all the instructor unit tests.



Hello students, thank you for agreeing to help me recapture Dr. Bart. I am sure that with your coding prowess, and my AlgoDeathBots, we will have no trouble finding him efficiently. My strategy is simple, you just have to:

  1. Read in a file containing the rooms, connections, and robots in the house.
  2. Construct a graph from that data.
  3. Traverse the graph to find Dr. Bart.
  4. Calculate the shortest paths from the robots to Dr. Bart.
  5. List the path each robot will take to reach Dr. Bart.

Some details you must follow:

Formal Specification

Problem: Find the last visited node in a traversal and calculate shortest path to it from certain other nodes.

Input: The filename of a local file containing a sequence of rooms and their neighbors, each on their own line. The first line contains the number of rooms in the house, and is not included in the number of vertices. You can assume that each line will contain only one room’s information. The lines are ordered alphabetically by the name of the room. The neighbors within a line are also ordered alphabetically.

A room’s information consists of the following information, separated by spaces:

  1. The unique name of the room, without spaces and no more than 256 characters long.
  2. Either the text robot or empty to indicate whether that room has an AlgoDeathBot in it.
  3. The names of one or more neighbor rooms, still separated by spaces.

So each line contains at least 3 space-separated substrings, possibly more. All room links are provided bidirectionally - if room A has an edge to room B, then room B has an edge back to room A.

An example of several records are below:

Kitchen empty Office Parlor
Office robot Kitchen
Parlor robot Kitchen Stairs
Stairs empty Patio

Output: A series of paths that the robots will take. Each robot’s path should be printed on its own line, with the room names separated by spaces. The path should be given from the robot’s room to Dr. Bart’s room. Report the paths in alphabetical order by the robot’s room name.

An example of output is below:

Office Kitchen Parlor Stairs
Parlor Stairs

Traversal Algorithms

There are two major traversal algorithms that you will need to learn:

You will use the same algorithm both to find Dr. Bart and to find the shortest path back. You will not use the other graph traversal algorithm in this assignment.

Research and understand both algorithms, because both are important to understand them. There are many applications for both kinds of traversals, and you will see them again and again. I have included links to two videos that might explain them, but you should look at other resources too.

Time Complexity

Be sure to choose an appropriate data structure for your operations, keeping the time complexities of Python’s data structures in mind.


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!

For this project, you will need to create an that solves the problem above and create a that explains your solution at a high level. Inside your file, make sure you clearly explain the algorithmic runtime of your program in terms of Big O. For full credit, you must be able to justify your program’s complexity as expected case O(RE+RV).

All parts of your solution, including both the program 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.


Students often ask me questions, even though my assignments are perfect. This is because humans are not as good as AlgoTutorBots. I have collected the questions here, for your benefit.