Table of Contents

Divide-and-Conquer

  1. Divide-and-Conquer:
    The divide-and-conquer strategy solves a problem by:
    1. Breaking it into subproblems that are themselves smaller instances of the same type of problem
    2. Recursively solving these subproblems
    3. Appropriately combining their answers

    The real work is done piecemeal, in three different places:

    1. in the partitioning of problems into subproblems
    2. at the very tail end of the recursion, when the subproblems are so small that they are solved outright
    3. and in the gluing together of partial answers.

    These are held together and coordinated by the algorithm’s core recursive structure.

  2. Asynchronous:

  3. Asynchronous:

  4. Binary Search:
    img1

  5. Mergesort:
    The problem of sorting a list of numbers lends itself immediately to a divide-and-conquer strategy: split the list into two halves, recursively sort each half, and then merge the two sorted sublists.

    img2

    Merge Function:
    Given two sorted arrays \(x[1 . . . k]\) and \(y[1 . . . l]\), how do we efficiently merge them into a single sorted array \(z[1 . . . k + l]\)?
    img3

    Here ◦ denotes concatenation.

    Run-Time:
    This merge procedure does a constant amount of work per recursive call (provided the required array space is allocated in advance), for a total running time of \(O(k + l)\). Thus merge’s are linear, and the overall time taken by mergesort is:

    $$T(n)=2 T(n / 2)+O(n) = O(n \log n)$$

    ☹️

    Iterative MergeSort:
    img4

  6. \(n \log n\) Lower Bound for (comparison-based) Sorting (Proof):
    img5

  7. Medians:


  8. Asynchronous:


SECOND

  1. Asynchronous:

  2. Asynchronous:

  3. Asynchronous:

  4. Asynchronous:

  5. Asynchronous:

  6. Asynchronous:

  7. Asynchronous:

  8. Asynchronous:

THIRD

  1. Asynchronous:

  2. Asynchronous:

  3. Asynchronous:

  4. Asynchronous:

  5. Asynchronous:

  6. Asynchronous:

  7. Asynchronous:

  8. Asynchronous:

FOURTH

  1. Asynchronous:

  2. Asynchronous:

  3. Asynchronous:

  4. Asynchronous:

  5. Asynchronous:

  6. Asynchronous:

  7. Asynchronous:

  8. Asynchronous:

FIFTH

  1. Asynchronous:

  2. Asynchronous:

  3. Asynchronous:

  4. Asynchronous:

  5. Asynchronous:

  6. Asynchronous:

  7. Asynchronous:

  8. Asynchronous:

Sixth

  1. Asynchronous:

  2. Asynchronous:

  3. Asynchronous:

  4. Asynchronous:

  5. Asynchronous:

  6. Asynchronous:

  7. Asynchronous:

  8. Asynchronous:{: .bodyContents6 #bodyContents68

Seven

  1. Asynchronous:

  2. Asynchronous:

  3. Asynchronous:

  4. Asynchronous:

  5. Asynchronous:

  6. Asynchronous:

  7. Asynchronous:

  8. Asynchronous: