CSCI 3110 Assignment 1 posted: 05.05.2021
Instructor: Travis Gagie due: midnight 14.05.2021
You can work in groups of up to three people. One group member should submit a copy of the solutions on
Brightspace, with all members’ names and banner numbers on it; the other group members should submit text
files with all members’ names and banner numbers (otherwise Brightspace won’t let us assign them marks!).
You may consult with other people but each group should understand the solutions: after discussions with
people outside the groups, discard any notes and do something unrelated for an hour before writing up your
solutions; it’s a problem if no one in a group can explain one of their answer. For programming questions
you should submit your code, which should compile and run correctly to receive full marks.
This assignment is unusually short so that it can be completed, marked and returned before the deadline
to drop courses without academic penalty. It may seem pretty hard at first, but the trick is not to give
up, break things down into sub-problems, and think about whether you can solve each sub-problem (and
pay attention to overflow!). There is an optional tutorial on Friday to help you and two TA office hours
next week, but the tutorial next week — on the day when this is due — will be for the next homework.
You should submit your code, in whatever programming language you can convince the TAs and markers to
accept. Good luck!
1. Use divide-and-conquer to count the valid 4-colourings of the map shown in Figure 1. (Apologies to
New Zealand and Antarctica!) In this case, let’s say a valid 4-colouring is an assignment of the colours
red, green, yellow and purple to the regions of the map (ignore water and the current colours) such
that no two regions assigned the same colour share a border of positive length (they can touch at a
point) or have a line drawn between them. The adjacency-list representation of the corresponding
graph (with the vertices names A1 through F4) is on the back of this sheet and will be posted as a text
file on Brightspace. If you find a discrepancy between the map and the adjacency lists, please email
Travis as soon as possible!
Figure 1: How many ways can this map be 4-coloured?
1
A1: A2, A5, A6
A2: A1, A3, A4, A5, A6, B7
A3: A2, A5, B7, D5
A4: A2, A6
A5: A1, A2, A3, D5, D7, F2
A6: A1, A2, A4
B1: B2, B3, B7, B11, D6
B2: B1, B3, B8, B9, B10, B11
B3: B1, B2, B7, B9
B4: B6, B8, B10, B12
B5: B6, B8
B6: B4, B5, B8, B12, E1
B7: A2, A3, B1, B3, D5, D6
B8: B2, B4, B5, B6, B10
B9: B2, B3, C2
B10: B2, B4, B8, B11, B12
B11: B1, B2, B10, D6
B12: B4, B6, B10
C1: C3, C4
C2: B9, C3, C4
C3: C1, C2, C4
C4: C1, C2, C3
D1: D2, D3, D4, D7
D2: D1, D4, E5
D3: D1, D4, D5, D6, D7
D4: D1, D2, D3, D6
D5: A3, A5, B7, D3, D6, D7
D6: B1, B7, B11, D3, D4, D5
D7: A5, D1, D3, D5
E1: B6, E2, E6
E2: E1, E6, E7, E9
E3: E4, E9, F4
E4: E3, E7, E8, E9
E5: D2, E6, E7, E8
E6: E1, E2, E5, E7
E7: E2, E4, E5, E6, E8, E9
E8: E4, E5, E7
E9: E2, E3, E4, E7
F1: F2, F3
F2: A5, F1, F3, F4
F3: F1, F2, F4
F4: E3, F2, F3
2