**Note: **Include your Cornell NetID on your each section of your
homework. This simplifies the process of recording your grades.

- Problem 7 at the end of Chapter 11.
Some friends of your are working with a system that performs real-time scheduling of jobs on multiple servers, and they've come to you for help in getting around an unfortunate piece of legacy code that can't be changed.

Here's the situation. When a batch of jobs arrive, the system allocates them to servers using the simple

*Greedy-Balance*algorithm from the first section of this chapter, which provides an approximation to within a factor of 2. In the decade and a half since this part of the system was written, the hardware has gotten faster to the point where, on the instances that the system needs to deal with, your friends find that it's generally possible to compute an optimal solution.The difficulty is that the people in charge of the system's internals won't let them change the portion of the software that implements the

*Greedy-Balance*algorithm, so as to replace it with one that finds the optimal solution. (Basically, this portion of the code has to interact with so many other parts of the system that it's not worth the risk of something going wrong if it's replaced.)After grumbling about this for a while, your friends come up with an alternate idea. Suppose they could write a little piece of code that takes the description of the jobs, computes an optimal solution (since they're able to do this on the instances that arise in practice), and then feeds the jobs to the

*Greedy-Balance*algorithm*in an order that will cause it to allocate them optimally*. In other words, they're hoping to be able to re-order the input in such a way that when*Greedy-Balance*encounters the input in this order, it produces an optimal solution.So their question to you is simply the following: Is this always possible? Their conjecture is,

For every instance of the load balancing problem from the first section of this chapter, there exists an order of the jobs so that when

*Greedy-Balance*processes the jobs in this order, it produces an assignment of jobs to machines with the minimum possible makespan.Decide whether you think this conjecture is true or false, and give either a proof or a counterexample.

- Problem 9 at the end of Chapter 11.
Suppose you are given an n-by-n

*grid graph*G, as in Figure 11.13 in the text. (*The figure is an n-by-n grid consisting of n*.)^{2}nodes; each node, except for those on the boundary, is connected to 4 neighbors, one neighbor in each direction: north, south, east, and westAssociated with each node v is a

*weight*w(v), which is a non-negative integer. You may assume that the weights of all nodes are distinct. Your goal is to choose an independent set S of nodes of the grid, so that the sum of the weights of the nodes in S is as large as possible. (The sum of the weights of the nodes in S will be called its*total weight*.)Consider the following greedy algorithm for this problem:

The "heaviest-first" greedy algorithm: Start with S equal to the empty set. While some node remains in G Pick a node v

_{i}of maximum weight. Add v_{i}to S. Delete v_{i}and its neighbors from G. end while Return SLet S be the independent set returned by the "heaviest-first" greedy algorithm, and let T be any other independent set in G. Show that for each node v in T, either v in S, or there is a node v' in S so that w(v)

__<__w(v')$ and (v,v') is an edge of G.Show that the "heaviest-first" greedy algorithm returns an independent set of total weight at least ¼ times the maximum total weight of any independent set in the grid graph G.

- Problem 2 at the end of Chapter 12.
Recall that for a problem in which the goal is to maximize some underlying quantity, gradient descent has a natural "upside-down" analogue, in which one repeatedly moves from the current solution to a solution of strictly greater value. Naturally, we could call this a

*gradient ascent*algorithm (though often in the literature you'll also see such methods referred to as*hill-climbing*algorithms).By straight symmetry, the observations we've made in this chapter about gradient descent carry over to gradient ascent: for many problems you can easily end up with a local optimum that is not very good. But sometimes one encounters problems --- as we saw, for example, with the maximum cut and multi-label classification problem (

*we didn't talk about this topic this year, but you don't need this to solve this problem*) --- for which a local search algorithm comes with a very strong guarantee: every local optimum is close in value to the global optimum. We now consider the maximum bipartite matching problem, and find that the same phenomenon happens here as well.Thus, consider the following gradient ascent algorithm for finding a matching in a bipartite graph:

As long as there is an edge whose endpoints are unmatched, add it to the current matching. When there is no longer such an edge, terminate with a locally-optimal matching.

- Give an example of a bipartite graph G for which this gradient ascent algorithm does not return the maximum matching.
- Let M and M' be matchings in a bipartite graph G. Suppose that |M'| > 2 |M|. Show that there is an edge e' in M' such that (M union {e'}) is a matching in G.
- Use (b) to conclude that any locally optimal matching returned by the
gradient ascent algorithm in a bipartite graph G is at least
*half*as large as a maximum matching in G.