3. (10 pts.) You are in charge of the United States Mint. The money-printing machine has developed a strange bug: it will only print a bill if you give it one first. If you give it a d-dollar bill, it is only willing to print bills of value d² mod 400 and d² + 1 mod 400. For example, if you give it a $6 bill, it is willing to print $36 and $37 bills, and if you then give it a $36-dollar bill, it is willing to print $96 and $97. You start out with only a $1 bill to give the machine. Every time the machine prints a bill, you are allowed togive that bill back to the machine, and it will print new bills according to the rule described above. You want to know if there is a sequence of actions that will allow you to print a $20 bill, starting from your $1 bill.Model this task as a graph problem: give a precise definition of the graph (what are the vertices and edges)involved and state the specific question about this graph that needs to be answered. Give an algorithm to solve the stated problem and give the running time of your algorithm.

[10 pts] Suppose John's biking environment consists of n ≥ 3 landmarks, which are linked by bike route in a cyclical manner. That is, there is a bike route between landmark 1 and 2, between landmark 2 and 3, and so on until we link landmark n back to landmark 1. In the center of these is a mountain which has a bike route to every single landmark. Besides these, there are no other bike routes in the biking environment. You can think of the landmarks and the single mountain as nodes, and the bike routes as edges, which altogether form a graph G. A path is a sequence of bike routes. (a) [6 pts] Find the number of paths of length 2 in the graph in terms of n. Justify your answer. (b) [6 pts] Find the number of cycles of length 3 in the graph in terms of n. Justify your answer. (c) [6 pts] Find the number of cycles in the graph in terms of n. Justify your answer.

3. Consider the following network of computers: E 3 The numbers labelling each edge indicate the number of Macquariecoin it costs to send a message along that network connection. We wish to minimise the costs of sending messages by finding paths of minimal length in this weighted graph. Use Dijkstra's algorithm to construct a shortest-path spanning tree rooted at computer C. In your an- swer, you should: (a) [3 marks]. Draw the graph and illustrate the spanning tree you construct within it. (b) [5 marks]. Show your working by displaying, at each step of execution, the contents of the fringe list, clearly identifying the edge which will be added to the tree next. (c) [3 marks]. List the length of each shortest path starting from the chosen root computer C to each of the other computers in the network.

[10 pts] This problem will use the concept of a graph's degree sequence. This is a list of the degrees of all the vertices in the graph, in descending order of degree. For example, the graph a C (†) has degree sequence (4,3,3,2,2,0) because there is one node with degree 4 (c), two nodes with degree 3 (b and d), two nodes with degree 2 (a and e), and one node with degree 0 (f). For each of the following, either list the set of edges of a tree with vertex set {a, b, c, d, e, f} that has the stated degree sequence, or show that no such tree exists. There's no need to draw out the tree here, but it may help you to do so on paper. (a) [4 pts] (3,3,3,1, 1, 1) (b) [4 pts] (3,3,1, 1, 1, 1) (c) [4 pts] (4,3, 1, 1, 1, 1)

2. A simple connected graph G has ten vertices of degree 7 and one of degree 6, and no other vertices. (a) [3 marks]. How many edges does it have? Be sure to state clearly any results that you use to get your answer. (b) [2 marks]. If this graph had a planar drawing, how many faces would it have? Be sure to state clearly any results that you use to get your answer. (c) [4 marks]. Explain why it follows that G cannot be planar.

Q1 Because of the incredible popularity of his class Math for Computer Science, TA Mike decides to give up on regular office hours. Instead, he arranges for each student to join some study groups. Each group must choose a representative to talk to the staff, but there is a staff rule that a student can only represent one group. The problem is to find a representative from each group while obeying the staff rule. a) Explain how to model the delegate selection problem as a bipartite matching problem. (This is a{modeling problem); we aren't looking for a description of an algorithm to solve the problem.) b) The staff's records show that each student is a member of at most 4 groups, and all the groups have 4 or more members. Is that enough to guarantee there is a proper delegate selection? Explain.

[10 pts] Imagine a country that has n N cities that are linked by highways, where a highway (which can be traversed in either direction) links exactly two cities and the only way to enter or exit a city is via highway(s). The president of this country hates wastefulness, so she ensured that for any pair of cities in the country, there exists only one sequence of highway(s) linking the two cities; in other words, the graph formed by the cities (vertices) and the highways (edges) is a tree. Further, suppose that there exists at least one city in this country such that there exist d EN distinct highways via which you can enter or exit the city. Prove that there are at least d cities such that: for each of the d cities, there is only one highway to enter or exit the city.

1. The citizens of the Scandinavian town of Garnsholm are trying to solve a puzzle: is it possible to take a wundertur, that is, a cycle ride through Garnsholm that crosses each of its seven bridges exactly once? (Note that a wundertur does not have to start and end at the same point). North Island B South Island M (a) [3 marks]. Turn this map of Garnsholm into a graph, and find its degree sequence. Is this graph simple? (b) [4 marks]. Explain why there can be no wundertur through Garnsholm. (You can assume any results we proved in the lectures, but you should state what they are.) (c) [3 marks]. The citizens of South Island are so annoyed by your argument that they decide to demolish one of the three bridges connecting them to the rest of Garnsholm. Indicate on your graph which of the bridges they could choose to remove if they want to make it possible to take a wundertur. Give a brief justification.

Q2 6.042 at MIT is often taught using recitations. Suppose it happened that 8 recitations were needed, with two or three staff members running each recitation. The assignment of staff to recitation sections, using their secret code names, is as follows: \item R1: Maverick, Goose, Iceman R2: Maverick, Stinger, Viper R3: Goose, Merlin R4: Slider, Stinger, Cougar R5: Slider, Jester, Viper R6: Jester, Merlin R7: Jester, Stinger R8: Goose, Merlin, Viper Two recitations can not be held in the same 90-minute time slot if some staff member is assigned to both recitations. The problem is to determine the minimum number of time slots required to complete all the recitations. a) Recast (translate) this problem as a question about coloring the vertices of a particular graph. b) Draw the graph and explain what the vertices, edges, and colors represent. (One free flow-chart building application that will work to make such an image is https://draw.io c) Show a coloring of this graph using the fewest possible colors; prove why no fewer colors will work. d) What is the resulting schedule of recitations implied by the coloring?

We saw in the lectures how to convert a 2-SAT instance into a digraph. Which arcs are created in the digraph from a clause (a V b) in the 2- SAT instance? Select all that apply.