CSC263 Problem Set 3
Question 1: Consulting on Board Game Design
You have been hired as a consultant by the board game company to help them analyze
potential designs for a new game. The game will have a map of cities and villages and two
ports. Playing the game will involve travelling from the starting port to an ending port
through some cities and villages. Some cities and villages are connected while others are
not. This diagram shows one possible board layout. The red circle indicates that B is a city.
A, C, and D are villages. Travel is permitted in both directions on all roads. You can not
travel through a port – only start or end at one.
The board game company wants to consider three different scenarios:
Scenario 1: Routes can travel through any city or village at most once.
Scenario 2: Routes can travel through any village at most once, but they can pass
through a city multiple times.
Scenario 3: There is a special village passport card. A player may play it on one village
and then is permitted to travel a route that passes through that village one extra time.
Routes can still travel through cities multiple times and all the other villages at most
once. The village passport can not be played on a port. The village passport does not
have to be played, so all the routes from scenario 2 are still permitted under scenario 3.
The company has a number of board configurations under consideration and for each config-
uration, they wish to know how many legal routes will go from start to finish under each of
the three scenarios. For example, using the board configuration in the diagram above, there
are 3 possible routes for scenario 1, 8 routes for scenario 2 and 39 for scenario 3. It starts
to get hard to calculate the numbers of possible routes by hand as the board configurations
get more complicated. So that’s why they have hired you!
(a) Your first task is to design efficient algorithms and associated data structures to count
the number of possible routes under each of the three scenarios for an arbitrary board
configuration.
The designers have realized that if two cities are directly connected then there will be
an infinite number of routes in both scenario 2 and scenario 3. So they will not ever
propose a configuration with connected cities. Also, every configuration they propose
1
will have one start port and one end port. The configurations never have two roads
connecting the same two places directly.
Submit a written description of the three algorithms. Your algorithms should be based
directly on a graph algorithm we learned in class and you should be explaining how
that algorithm is adapted and applied to this problem. Specifically, describe
the data structures you are using to support your algorithm. The audience is someone
who already understands the algorithms we learned and the specific terminology we
used in lectures so you can refer to those terms.
(b) Design your own concise text (i.e. human readable) representation of a board config-
uration. Write clear specifications for this representation. Make sure that your design
can represent any board that meets the assumptions specified above. As an example in
your explanation, include the representation for the small board above and then also
submit the input file for this board to MarkUs using the filename example board.txt.
(c) Implement your algorithm in Python. You must have a single file Routes.py and it
must not import any Python modules other than sys (which you need for command-line
argument processing) and optionally typing. The output of your program should be
a message giving the number of possible routes under the three scenarios. The exact
format of this output is up to you. You are not asked to list all the possible routes.
Your program must run on teach.cs with the following command
python3 Routes.py inputfilepath. You can assume that the inputfilepath passed to
your program in the command-line argument corresponds to a valid board configuration
file according to your representation in part b. It is fine to fail spectacularly if this
assumption is violated. Don’t spend time on error checking the input, but do use
excellent coding style including variable names and comments that will help the marker
see immediately how your code connects to the algorithm you described in part a.
We will separately post some extra advice about writing your program including some
sample code for reading the command-line argument and opening and reading from a
file.
(d) Design a set of tests for your program and use them to demonstrate to the marker that
your program works correctly. You should focus on algorithmically important and
interesting tests not boundary cases that are uninteresting algorithmically. Each test
case is a board configuration, NOT a unittest, and should be in its own .txt file.
Suppose your first test was in the board configuration file called test1.in.txt. Then the
TA should be able to run your code by typing python3 Routes.py test1.in.txt at
the command line on teach.cs.
In Q1.pdf (where you provide the English solution to parts a, b and d of this question),
expand on each test case you designed, explaining what it is that you are testing, the
specific input, and the actual output when you ran the test. You should reference the
exact filenames of your test files which you will submit to MarkUs separately as part
of your submission but a reader should be able to understand your testing without
opening any other files. You may wish to provide a visual picture of the boards
2
(inside the discussion in Q1.pdf) if that makes it clearer for the reader.1. A word of
advice, keep the input files small. It is fine to hand-draw board examples or to not have
pictures at all.
In order to earn full marks for correctness for your algorithms and their implementation,
you need to convey to the marker (in the time that they have available to read and
understand your Q1.pdf ) that your code has been tested properly. Conveying technical
information clearly, concisely and in a way that can be understood quickly is the skill
we are practicing here. It isn’t easy. If you say too much, the reader won’t have time to
dig through all your tests. If you say too little, they won’t be convinced that the code
was tested thoroughly. Finding the correct balance and presenting the information in
a way that can be grasped quickly is the goal.
Expectations for Question 1
There are multiple learning goals for this question. One is for you to solidify your knowledge
of graph algorithms by doing some actual implementation and designing test cases. The
second is for you to practice concisely communicating to a technical audience. While it is
important that your program works correctly, the majority of the marks will not come from
part (c). Do not leave the testing or the written explanations as after thoughts or assign
either of these tasks to a single person. Both partners should be involved in the designing,
coding, testing and writing.
Question 2: Amortized Analysis
Let [O1, O2, O3, ..., On] be a list of n operations each of which is either TASK1 or TASK2. O1
is TASK1 and O2 is TASK2 but the others are specified in the cases below. The running time
of TASK2 operations is always constant. The running time of the first TASK1 operation
(O1) is also constant, but the running time of each TASK1 operation Oi after the first is twice
as long as the previous TASK1 operation. Calculate the amortized time of the operations in
the following three scenarios.
(a) There are a constant number of TASK2 operations between consecutive TASK1 oper-
ations.
(b) There are Θ(
√
(n)) TASK2 operations between consecutive TASK1 operations.
(c) The number of TASK2 operations between a TASK1 operation (Oi) and the previous
TASK1 operation (Oj) is always twice the number between (Oj) and its previous TASK1
operation.
1You might need to compress the images to keep Q1.pdf within the Markus submission size limits
3
Question 3
Consider a connected undirected graph G. Design an algorithm based on BFS to find a
vertex v whose removal (deleting the vertex and all its incident edges) does NOT disconnect
the graph.
(a) Describe your algorithm in clear and precise English.
(b) Justify that your algorithm works correctly.
(c) Analyse the worst-case running time of your algorithm if G is represented by an adja-
cency matrix. Express the result in asymptotic notation with a tight bound.
Question 4: Minimum Spanning Trees
T is a minimum spanning tree for an arbitrary connected undirected graph G. G is repre-
sented as a matrix of edge weights where a 0 indicates no edge and negative weights are not
allowed. T is stored as an unsorted list of edges.
Now we add to G a new vertex v. We add a set of edges {e1, e2, ...ek} that connect v to
some vertices in G. The resulting graph is G′.
Describe an efficient2 algorithm for computing a minimum spanning tree for G′.
Briefly justify the correctness of your algorithm.
State and briefly justify the efficiency of your algorithm.
2We have intentionally not provided the required complexity for your algorithm. Your solution should be as efficient as
possible. An algorithm that correctly computes the result but is more complicated than necessary (in terms of running time or
space), will not receive as many marks as a more efficient solution.