Homework Guidelines

Collaboration policy   Collaboration on homework problems, with the exception of programming assignments and reading quizzes, is permitted, but not encouraged. If you choose to collaborate on some problems, you are allowed to discuss each problem with at most 5 other students currently enrolled in the class. Before working with others on a problem, you should think about it yourself for at least 45 minutes.  Finding answers to problems on the Web or from other outside sources (these include anyone not enrolled in the class) is strictly forbidden.

You must write up each problem solution by yourself without assistance, even if you collaborate with  others  to  solve  the problem.  You must also identify your collaborators.  If you did not work with anyone, you should write ”Collaborators:  none.” It is a violation of this policy to submit a problem solution that you cannot orally explain to an instructor or TA.

Typesetting   Solutions should be typed and submitted as a PDF file on Gradescope.  You may use any program you like to type your solutions. LATEX, or “Latex”, is commonly used for technical writing (overleaf.com is a free web-based platform for writing in Latex) since it handles math very well. Word, Google Docs, Markdown or other software are also fine.

Solution guidelines   For problems that require you to provide an algorithm, you must provide:

1. pseudocode and, if helpful, a precise description of the algorithm in English.   As always, pseudocode should include

● A clear description of the inputs and outputs

● Any assumptions you are making about the input (format, for example)

● Instructions that are clear enough that a classmate who hasn’t thought about the prob- lem yet would understand how to turn them into working code.  Inputs and outputs of any subroutines should be clear, data structures should be explained, etc.

If the algorithm is not clear enough for graders to understand easily, it may not be graded.

2.  a proof of correctness (except for on Homework 1),

3.  an analysis of running time and space (except for on Homework 1).

You may use algorithms from class, discussions, textbook, past assignments as subroutines.  (You may also call algorithms that you designed as part of the same problem.  )You may also use facts – such as correctness, running times – that we proved in class.

You should be as clear and concise  as possible in your write-up of solutions.  A simple, direct description or analysis is worth more points than a convoluted one, both because it is simpler and less prone to error and because it is easier to read and understand.  (Please make use of algorithms already studied, don’t write them down again.)

Problem 1  (6 points) Dance competition

’Jack and Jills’ are a popular type of event at swing dance competitions.  Here leaders and followers are paired up at random to dance in the competition as partners. Dancers are considered to have truly mastered the skills of leading or following if they can do it well with any partner, this competition is meant to demonstrate this skill.

This time however the assignment is not going to be entirely at random, you are in charge of assigning leaders to followers based on some rules:

● You are given the list of leaders and the list of followers.  The number of leaders is denoted by L, followers by F .  It’s possible that some dancers end up without a partner and can’t compete.

● Dancers belong to dance clubs, also given is the club affiliation of each dancer.  To stay in the spirit of Jack and Jills only dancers from different clubs may dance together.  You may assume that each competitor is in the same club with at most half of the leaders/followers.

● at most 10 couples can dance in the competition.

1.  Design an instance of network flow that can model the above setup.  Make sure to clearly describe every part of the graph. Briefly explain your design choices, e.g. why did you add a specific edge.

2.  Compute the minimum number of edges in this graph as a function of L and F .   Briefly explain how you came up with this number.

3.  Suppose you found a maximum flow in the above graph. Explain how to find which leader is dancing with which follower given the flow. What is the maximum number of pairs that can compete given the value of the max flow?

Problem 2  (6 points) Binary magic squares .

We are given a list of k integers (row1 , row2 , ..., rowk) and l integers (col1 , col2 , ..., coll) such that     i(k)=1 rowi =    j(l)=1 colj  Design an algorithm that can decide whether there is a K · L square table of 0s and 1s, such that each row i sums to rowi  and each col j sums to cj?

Problem 3  (8 points) Network flow with constant degrees

In this problem you are asked to investigate the properties of network flow in graphs with constant outdegree.  Let G(V, E, s, t, c, d) be an input to the Maximum Flow problem.  Note that there is an additional input variable, the integer d.  c is the function prescribing the capacity on each edge, in this case c(u, v) = 1 for every vertex u and v .

This graph G has the property that each node v has outdegree(v) = d, where d is a constant that is given as part of the input (including s but with the exception of the sink t).

1.  Draw1  two examples of graphs, in both cases the graph G has to have lV l = 11 vertices (two of the vertices are s and t and 9 intermediary vertices) and d = 3 further