Class on Design and Analysis of Algorithms, Lecture 1 Notes

Lecture 1 Introduction 6.046J Spring 2015 Lecture 1: Introduction 6.006 pre-requisite: • Data structures such as heaps, trees, graphs • Algorithms for sorting, shortest paths, graph search, dynamic programming Course Overview This course covers several modules: 1. Divide and Conquer - FFT, Randomized algorithms 2. Optimization - greedy and dynamic programming 3. Network Flow 4. Intractibility (and dealing with it) 5. Linear programming 6. Sublinear algorithms, approximation algorithms 7. Advanced topics Theme of today’s lecture Very similar problems can have very different complexity. Recall: • P: class of problems solvable in polynomial time. O(nk ) for some constant k. Shortest paths in a graph can be found in O(V 2 ) for example. • NP: class of problems verifiable in polynomial time. Hamiltonian cycle in a directed graph G(V, E) is a simple cycle that contains each vertex in V . Determining whether a graph has a hamiltonian cycle is NP-complete but ver­ ifying that a cycle is hamiltonian is easy. • NP-complete: problem is in NP and is as hard as any problem in NP. If any NPC problem can be solved in polynomial time, then every problem in NP has a polynomial time solution. 1 Lecture 1 6.046J Spring 2015 Introduction Interval Scheduling Requests 1, 2, . . . , n, single resource s(i) start time, f (i) finish time, s(i) < f (i) (start time must be less than finish time for a request) Two requests i and j are compatible if they don’t overlap, i.e., f (i) ≤ s(j) or f (j) ≤ s(i). In the figure below, requests 2 and 3 are compatible, and requests 4, 5 and 6 are compatible as well, but requests 2 and 4 are not compatible. 1 2 4 3 5 6 Goal: Select a compatible subset of requests of maximum size. Claim: We can solve this using a greedy algorithm. A greedy algorithm is a myopic algorithm that processes the input one piece at a time with no apparent look ahead. Greedy Interval Scheduling 1. Use a simple rule to select a request i. 2. Reject all requests incompatible with i. 3. Repeat until all requests are processed. 2 Lecture 1 6.046J Spring 2015 Introduction Possible rules? 1. Select request that starts earliest, i.e., minimum s(i). Long one is earliest. Bad :( 2. Select request that is smallest, i.e., minimum f (i) − s(i). Smallest. Bad :( 3. For each request, find number of incompatibles, and select request with mini­ mum such number. Least # of incompatibles. Bad :( 4. Select request with earliest finish time, i.e., minimum f (i). Claim 1. Greedy algorithm outputs a list of intervals < s(i1 ), f (i1 ) >, < s(i2 ), f (i2 ) >, . . . , < s(ik ), f (ik ) > such that s(i1 ) < f (i1 ) ≤ s(i2 ) < f (i2 ) ≤ . . . ≤ s(ik ) < f (ik ) Proof. Simple proof by contradiction – if f (ij ) > s(ij+1 ), interval j and j +1 intersect, which is a contradiction of Step 2 of the algorithm! Claim 2. Given list of intervals L, greedy algorithm with earliest finish time produces k ∗ intervals, where k ∗ is optimal. Proof. Induction on k ∗ . Base case: k ∗ = 1 – this case is easy, any interval works. Inductive step: Suppose claim holds for k ∗ and we are given a list of intervals whose optimal schedule has k ∗ + 1 intervals, namely S ∗ [1, 2, . . . , k ∗ + 1] =< s(j1 ), f (j1 ) >, . . . , < s(jk∗ +1 ), f (jk∗ +1 ) > 3 Lecture 1 Introduction 6.046J Spring 2015 Say for some generic k, the greedy algorithm gives a list of intervals S[1, 2, . . . , k] =< s(i1 ), f (i1 ) >, . . . , < s(ik ), f (ik ) > By construction, we know that f (i1 ) ≤ f (j1 ), since the greedy algorithm picks the earliest finish time. Now we can create a schedule S ∗∗ =< s(i1 ), f (i1 ) >, < s(j2 ), f (j2 ) >, . . . , < s(jk∗ +1 ), f (jk∗ +1 ) > since the interval < s(i1 ), f (i1 ) > does not overlap with the interval < s(j2 ), f (j2 ) > and all intervals that come after that. Note that since the length of S ∗∗ is k ∗ + 1, this schedule is also optimal. Now we proceed to define L' as the set of intervals with s(i) ≥ f (i1 ). Since S ∗∗ is optimal for L, S ∗∗ [2, 3, . . . , k ∗ + 1] is optimal for L' , which implies that the optimal schedule for L' has k ∗ size. We now see by our initial inductive hypothesis that running the greedy algorithm on L' should produce a schedule of size k ∗ . Hence, by our construction, running the greedy algorithm on L' gives us S[2, . . . , k]. This means k − 1 = k ∗ or k = k ∗ + 1, which implies that S[1, . . . , k] is indeed optimal, and we are done. Weighted Interval Scheduling Each request i has weight w(i). Schedule subset of requests that are non-overlapping with maximum weight. A key observation here is that the greedy algorithm no longer works. Dynamic Programming We can define our sub-problems as Rx = {j ∈ R|s(j) ≥ x} Here, R is the set of all requests. If we set x = f (i), then Rx is the set of requests later than request i. Total number of sub-problems = n (one for each request) Only need to solve each subproblem once and memoize. We try each request i as a possible first. If we pick a request as the first, then the remaining requests are Rf (i) . 4 Lecture 1 Introduction 6.046J Spring 2015 Note that even though there may be requests compatible with i that are not in R , we are picking i as the first request, i.e., we are going in order. f (i) opt(R) = max (w(i) + opt(Rf (i) )) 1≤i≤n 2 Total running time is O(n ) since we need O(n) time to solve each sub-problem. Turns out that we can actually reduce the overall complexity to O(n log n). We leave this as an exercise. Non-identical machines As before, we have n requests {1, 2, . . . , n}. Each request i is associated with a start time s(i) and finish time f (i), m different machine types as well τ = {T1 , . . . , Tm }. Each request i is associated with a set Q(i) ⊆ τ that represents the set of machines that request i can be serviced on. Each request has a weight of 1. We want to maximize the number of jobs that can be scheduled on the m machines. This problem is in NP, since we can clearly check that a given subset of jobs with machine assignments is legal. Can k ≤ n requests be scheduled? This problem is NP-complete. Maximum number of requests that should be scheduled? This problem is NP-hard. Dealing with intractability 1. Approximation algorithms: Guarantee within some factor of optimal in poly­ nomial time. 2. Pruning heuristics to reduce (possible exponential) runtime on “real-world” examples. 3. Greedy or other sub-optimal heuristics that work well in practice but provide no guarantees. 5