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.

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?

How many arcs are in the component graph of the following digraph?

How many strongly connected components does the graph below have?

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.

Consider the following directed graph. 1. Perform depth-first search with timing (DFS-with-timing) on the above graph; whenever there's a choice of vertices, pick the one that is alphabetically first: give the pre and post number of each vertex.

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.

ots.) Consider the following directed graph. 1. What are the sources and sinks of the graph? 2. Give one linearization of this graph. 3. How many linearization does this graph have?