Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 25 views

    MIT6 046JS15 Lec01

    Uploaded by

    Cajun Sef
    The document provides an overview of the topics that will be covered in the 6.046J course, including divide and conquer algorithms, optimization techniques like greedy algorithms and dynamic programming, network flows, and more. It then discusses the complexity classes P, NP, and NP-complete. As an example, it shows that the interval scheduling problem can be solved optimally using a greedy algorithm by always selecting the interval with the earliest finish time. However, the weighted version cannot be solved greedily. Dynamic programming is presented as an alternative approach. The lecture concludes by discussing intractable problems and techniques for dealing with them such as approximation algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    MIT6 046JS15 Lec01

    Uploaded by

    Cajun Sef
    25 views6 pages
    The document provides an overview of the topics that will be covered in the 6.046J course, including divide and conquer algorithms, optimization techniques like greedy algorithms and dynamic programming, network flows, and more. It then discusses the complexity classes P, NP, and NP-complete. As an example, it shows that the interval scheduling problem can be solved optimally using a greedy algorithm by always selecting the interval with the earliest finish time. However, the weighted version cannot be solved greedily. Dynamic programming is presented as an alternative approach. The lecture concludes by discussing intractable problems and techniques for dealing with them such as approximation algorithms.

    Original Description:

    mit lec

    Original Title

    MIT6_046JS15_lec01

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides an overview of the topics that will be covered in the 6.046J course, including divide and conquer algorithms, optimization techniques like greedy algorithms and dynamic programming, network flows, and more. It then discusses the complexity classes P, NP, and NP-complete. As an example, it shows that the interval scheduling problem can be solved optimally using a greedy algorithm by always selecting the interval with the earliest finish time. However, the weighted version cannot be solved greedily. Dynamic programming is presented as an alternative approach. The lecture concludes by discussing intractable problems and techniques for dealing with them such as approximation algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    25 views6 pages

    MIT6 046JS15 Lec01

    Uploaded by

    Cajun Sef
    The document provides an overview of the topics that will be covered in the 6.046J course, including divide and conquer algorithms, optimization techniques like greedy algorithms and dynamic programming, network flows, and more. It then discusses the complexity classes P, NP, and NP-complete. As an example, it shows that the interval scheduling problem can be solved optimally using a greedy algorithm by always selecting the interval with the earliest finish time. However, the weighted version cannot be solved greedily. Dynamic programming is presented as an alternative approach. The lecture concludes by discussing intractable problems and techniques for dealing with them such as approximation algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 6

    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 Introduction 6.046J Spring 2015

    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.

    2 3

    4 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 Introduction 6.046J Spring 2015

    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
    f (i)
    R , we are picking i as the first request, i.e., we are going in order.

    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
    MIT OpenCourseWare
    http://ocw.mit.edu

    6.046J / 18.410J Design and Analysis of Algorithms


    Spring 2015

    For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.

    You might also like