This assignment is unusually short so that it can be completed,marked and returned before the deadlineto drop courses without academic penalty

This assignment is unusually short so that it can be completed,marked and returned before the deadlineto drop courses without academic penalty. It may seem pretty hard at first?but the trick is not to giveup, break things down into sub-problems, and think about whether you can solve each sub-problem (andpay attention to overflow!). .You should submit your code, in whatever programming language you can convince the TAs and markers toaccept. Good luck!

1.Use divide-and-conquer to count the valid 4-colourings of the map shown in Figure 1.(Apologies toNew Zealand and Antarctica!) In this case, let 's say a valid 4-colouring is an assignment of the coloursred, green,yellow and purple to the regions of the map (ignore water and the current colours) suchthat no two regions assigned the same colour share a border of positive length (they can touch at apoint) or have a line drawn between them. The adjacency-list representation of the correspondinggraph (with the vertices names A1 through F4) is on the back of this sheet and will be posted as a textfile on Brightspace. If you find a discrepancy between the map and the adjacency lists? please emailTravis as soon as possible!