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

3. an analysis of running time and space
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  Clever input order
Suppose we have a super-fast computer that can in fact find the optimal solution for Load Balancing. That is, given the number of machines m and the job durations t1, t2, . . . tn it returns to us an assignment A of the jobs to the m machines, such that the makespan is minimum. (No- tation: A[i] is a list of jobs assigned to machine i) Unfortunately we don’t have access to this super-computer, but we are given the assignment A. Can we ”force” the greedy LoadBalancing algorithm from class (on October 6, slide 6.) to produce this optimal assignment by inputting the jobs in some clever order?

Describe a very simple algorithm that takes as input t1, . . . , tn and A and returns an order of the jobs that we should input to the greedy LoadBalancing algorithm so that it indeed returns A. Prove that your solution is correct.

Problem 2 Cycles 
Given a directed graph G(V, E), find an O(|V | + |E|) algorithm that deletes at most half of its edges so that the resulting graph doesn’t contain any directed cycles.

Problem 3 Seamstresses 
You are running a small Halloween costume shop that prides itself in the unique costumes that they sell. To stay truly unique, your shop designs and makes a new set of costumes each year. You are in the middle of planning for this year’s costume making and want to find a work schedule so that all costumes are ready in time for Halloween. You employ five seamstresses, some of them are more experienced and work faster while others are still learning and are slower. You know for each seamstress how many yards of fabric they can sew in a day, these are given to you as s1, s2, s3, s4, s5. Further, you know for each of the n costumes how many yards of fabric they use, f1, f2, . . . fn.

Find an approximation algorithm to decide which costume to assign to which seamstress so that all the costumes are finished as soon as possible. Define the algorithm and prove its approximation factor.

Problem 4  Vaccine testing
You are developing a new vaccine and want to identify a small representative sample of people to test it on. The target population of this vaccine has size n. Each person has some health- characteristics, e.g. age, weight, disease history, etc. Based on these characteristic we can compute how similar two people are. You don’t have to worry about how to get these values, we assume that they are given.

As input we are given for each pair of people p and q their distance d(p,q) (which quantifies how dissimilar they are). We may assume that d(p, q) is a proper distance function
 
Given a positive number ∆, we say that a set S of persons is representative of the population, if for any person p there is at least one person q in S that is within ∆ distance, that is d(p, q) ≤ ∆.

Design a (ln n)-approximation algorithm to find a minimal representative set in the population. As input we are given the