Scribd Logo
Upload

Welcome to Scribd!

  • 6 views

    Algorithm Class Lecture 2

    Uploaded by

    minjoopjjm
    Algorithm Class lecture 2

    Copyright:

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

    Algorithm Class Lecture 2

    Uploaded by

    minjoopjjm
    6 views17 pages
    Algorithm Class lecture 2

    Original Title

    Algorithm Class lecture 2

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Algorithm Class lecture 2

    Copyright:

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

    Algorithm Class Lecture 2

    Uploaded by

    minjoopjjm
    Algorithm Class lecture 2

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 17

    CSE 347 Lecture 2

    Divide and Conquer

    1
    Review of CSE 247
    1. Divide the problem into (generally equal) smaller
    subproblems
    2. Recursively solve the subproblems
    3. Combine the solutions of subproblems to get the
    solution of the original problem
    Examples: Merge Sort, Binary Search

    2
    Recurrence
    Your favorite equation:

    𝑛
    𝑇 𝑛 = 𝑎𝑇 + Θ(𝑓 𝑛 )
    𝑏

    Master Method:

    3
    Example 1: Multiplying 2 numbers
    𝑋 = 𝑥!"# 𝑥!"$ 𝑥!"% … 𝑥&
    𝑌 = 𝑦!"# 𝑦!"$ 𝑦!"% … 𝑦&

    Normal Algorithm:

    4
    Complexity
    Running Time:

    5
    Divide and Conquer Approach
    𝑋 = 𝑥!"# 𝑥!"$ 𝑥!"% … … … … 𝑥&
    𝑌 = 𝑦!"# 𝑦!"$ 𝑦!"% … … … … 𝑦&

    𝑇 𝑛 =

    6
    Lets look at it deeply
    𝑋𝑌 = 𝑍'' 2! + 𝑍'( 2!/$ + 𝑍((
    𝑍'' =
    𝑍'( =
    𝑍(( =

    𝑍'( =

    Now, 𝑇 𝑛 =

    1963: Θ 𝑛#.+, 1971: Θ(𝑛 log 𝑛 log log 𝑛)


    7
    Example 2: Closest Pairs
    Input: P is a set of 𝑛 points in the plane.
    𝑝- = (𝑥- , 𝑦- )
    $ $
    𝑑 𝑝- , 𝑝. = 𝑥- − 𝑥. + 𝑦- − 𝑦.
    Goal: Find the distance between the closest pair of points

    Example:

    Naively,

    8
    A Divide and Conquer Algorithm
    Example:

    Sort all points by their x coordinate – Array 𝑃/


    !
    Mid point: 𝑃/
    $
    !
    𝑄 = all points to the left of mid point. 𝑃/ [0, … , ]
    $
    !
    𝑅 = all points to the right of mid point.𝑃/ [$ + 1, … , 𝑛]

    9
    A Divide and Conquer Algorithm
    Preprocessing: Sort 𝑃 by 𝑥 coordinate to get 𝑃!
    Base Case:

    Divide Step:

    Recursive Step:

    Combine Step:

    Total Runtime:

    10
    !
    Hmmm, runtime still Θ 𝑛 , how to
    make it faster?
    Use Geometry!
    Look through and only
    keep points that are
    close to the midline.

    11
    Important Insight: Can reduce the
    number of checks
    Lemma: If all points within this square are at least 𝛿
    apart, there are at most 4 points in this square.

    What does this imply? Only 4 points need to check!

    12
    A better algorithm
    1. Divide 𝑃! into 2 halves using the mid point
    2. Recursively compute 𝑑" and 𝑑# , take 𝛿 = min(𝑑" , 𝑑# ).
    3. Filter points into y-strip: points which are within (𝑚𝑖𝑑! −
    𝛿, 𝑚𝑖𝑑! + 𝛿)
    4. Sort 𝑦-strip by y coordinate. For every point 𝑝, we look at
    this 𝑦-strip in sorted order starting at this point and stop
    when we see a point with 𝑦 coordinate > 𝑝$ + 𝛿

    Runtime Analysis:

    13
    Can we even make it better?
    Preprocessing!
    𝑃! : All points sorted by x coordinate
    𝑷𝒚: All points sorted by y coordinate
    Closest Pair (𝑷𝒙, 𝑷𝒚)
    1. Divide into 𝑄 and 𝑅 using the middle points.
    2. Recursively compute 𝑑" and 𝑑# , take 𝛿 = min(𝑑" , 𝑑# ).
    3. Filter points into y-strip: points which are within (𝑚𝑖𝑑! −
    𝛿, 𝑚𝑖𝑑! + 𝛿), stay sorted by y coordinate. Calculate
    distance for points such that 𝑦 coordinate < 𝑝$ + 𝛿

    14
    Example of Step #4
    𝑃/ =
    𝑃0 =
    3
    5
    4
    𝑄/ =
    6 𝑄0 =
    2
    1 𝑅/ =
    𝑅0 =

    15
    Algorithm Pseudocode

    16
    Conclusion: Divide and Conquer
    • Revisit Master Theorem
    • Divide and Conquer Algorithm
    – Algorithm Description
    – Correctness Proof: induction
    • Example: Number Multiplication
    – Reduce the number of recursive tasks
    • Example: Closest Pairs
    – Use geometry to reduce the runtime for each recursion
    – Use of memorization and preprocessing in D&C

    17

    You might also like