CS787: Advanced AlgorithmsScribe: Shuchi Chawla Lecturer: Shuchi ChawlaTopic: Introduction and Greedy Algorithms Date: Sept 5, 20071.1 Introduction and Course OverviewIn this course we will study techniques for designing and analyzing algorithms. Undergraduatealgorithms courses typically cover techniques for designing exact, efficient (polynomial time) al-gorithms. The focus of this course is different. We will consider pr ob lems for which polynomialtime exact algorithms are not known, problems under stringent resource constraints, as well asproblems for which the notion of optimality is not well defined. I n each case, our emphasis will beon designing efficient algorithms with provable guarantees on their performance. Some topics thatwe will cover are as follows:• Approximation algorithms for NP-hard problems. NP-hard problems are those forwhich there are no polynomial time exact algorithms unless P = NP. Our focus will be onfinding n ear-optimal solutions in polynomial time.• Online algorithms. In these problems, the input to the problem is not known apriori, butarrives over time, in an “online” fashion. The goal is to design an algorithm that performsnearly as well as one that has the full information before-hand.• Learning algorithms. T hese are s pecial kinds of online algorithms that “learn” or determinea function based on “examples” of the function value at various inputs. The output of thealgorithm is a concise representation of the function.• Streaming algorithms. These algorithms solve problems on huge datasets under severestorage constraints—the extra s pace used for running the algorithm s hould be no more thana constant, or logarithmic in the length of the input. Such constraints arise, for example, inhigh-speed networking environments.We begin with a quick revision of basic algorithmic techniques including greedy algorithms, divide& conquer, dynamic programming, n etwork flow and basic randomized algorithms. Students areexpected to have s een this material before in a basic algorithms course.Note that some times we will not explicitly analyze the r unning times of the algorithms we discuss.However, this is an important part of algorithm analysis, and readers are highly encouraged towork out the asymptotic running times th emselves.1.2 Greedy AlgorithmsAs the name suggests, greedy algorithms solve problems by making a series of myopic decisions,each of wh ich by itself solves some subproblem optimally, b ut that altogether may or may not be1optimal for the problem as a whole. As a result these algorithms are usually very easy to designbut may be tricky to analyze, and don’t always lead to the optimal solution. Nevertheless thereare a few broad arguments that can be utilized to argue their correctness. We will demonstratetwo such techniques through a few examples.1.2.1 Interval SchedulingGiven: n jobs, each with a start and finish time (si, fi).Goal: Schedule the maximum number of (non-overlapping) jobs on a single machine.To apply the greedy approach to this problem, we will schedule jobs successively, while ensuringthat no picked job overlaps with those previously scheduled. The key design element is to decidethe order in which we consider jobs. There are several ways of doing so. Suppose for example, thatwe pick jobs in increasing order of size. It is easy to see that this does not necessarily lead to theoptimal solution (see the figure below for a counter-example). Likewise, scheduling jobs in orderof their arrivals (start times), or in increasing order of the number of conflicts that they have, alsodoes not work.(a) Bad example for the shortest job first algorithm (b) Bad example for the earliest start first algorithm(c) Bad example for the fewest conflicts first algorithmWe will now show th at picking jobs in increasing order of finish times gives the optimal solution. Ata high level, our proof will employ induction to show that at any point of time the greedy solutionis no worse than any partial optimal solution up to that point of time. In short, we will show thatgreedy always stays ahead.Theorem 1.2.1 The “earliest finish time first” algorithm described above generates an optimalschedule for the interval scheduling problem.Proof: Consider any solution S with at least k jobs. We claim by induction on k that the greedyalgorithm schedules at least k jobs and that the first k jobs in the greedy schedule finish no later2than the fi rst k jobs in the chosen solution. This imm ed iately implies th e result because it showsthat the greedy algorithm schedules at least as many jobs as the optimal solution.We now prove the claim. The base case, k = 0 is trivial. For the inductive step, consider the(k + 1)th job, say J, in the solution S. Then this job begins after the kth j ob in S ends, whichhappens after the kth job in the greedy schedule ends (by the induction hypothesis). Therefore, itis possible to augment the greedy schedule with the job J without introducing any conflicts. Thegreedy algorithm finds a candidate to augment its solution and in particular, picks one that finishesno later than the time at which J ends. This completes th e proof of the claim.1.2.2 Minimum Spanning TreeOur second problem is a network design problem.Given: A graph G with n vertices or machines, and m edges or potential cables. Each edge has aspecified length—`efor edge e.Goal: Form a network connecting all the machines using th e minimum amount of cable.Our goal is to select a subset of the edges of minimum total length such that all the vertices areconnected. It is immediate that the resulting set of edges forms a spanning tree—every vertex mustbe included; Cycles do not improve connectivity and only increase the total length. Therefore, theproblem is to find a spanning tree of minimum total length.The greedy approach to this problem involves picking edges one at a time while avoiding formingcycles. Again, the order in which we consider edges to be added to the tree forms a crucialcomponent of the algorithm. We mention two variants of this approach below, both of which leadto optimal tree constructions:1. Kruskal’s algorithm: Consider ed ges in increasing order of length, and pick each edge thatdoes not form a cycle with previously included edges.2. Prim’s algorithm: Start with an arbitrary node and call it the root component; at everystep, grow the root component by adding to it the shortest edge that has exactly one end-pointin the component.A