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 3 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
   

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 (4 points) 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 (6 points)

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 (10 points)

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 (10 points) 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