Scribd Logo
Upload

Welcome to Scribd!

  • 25 views

    Divide Conquer

    Uploaded by

    sadekinborno07
    Data Structure and Algorithm Divide and Conquer

    Copyright:

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

    Divide Conquer

    Uploaded by

    sadekinborno07
    25 views7 pages
    Data Structure and Algorithm Divide and Conquer

    Original Title

    Divide Conquer

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Data Structure and Algorithm Divide and Conquer

    Copyright:

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

    Divide Conquer

    Uploaded by

    sadekinborno07
    Data Structure and Algorithm Divide and Conquer

    Copyright:

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

    Divide and conquer

    In computer science, divide and conquer is an algorithm design paradigm. A divide-and-


    conquer algorithm recursively breaks down a problem into two or more sub-problems of the
    same or related type, until these become simple enough to be solved directly. The solutions to
    the sub-problems are then combined to give a solution to the original problem.

    Divide and conquer steps:


    1. Divide the problem into a number of subproblems that are smaller instances of the
    same problem
    2. Conquer the subproblems by solving them recursively
    3. Combine the solutions to the subproblems into the solution for the original problem
    4. The base case for the recursion is subproblems of constant size

    Practice problems:
    Instructions:
    1. Do not adopt unfair means. 10 marks will be deducted from the final marks for
    adopting unfair means.
    2. No more than 40% marks for uncompilable codes.

    1. Find the max and min element of an array.


    For loop version:
    Divide and conquer

    Divide and Conquer version:

    Recursion Tree:

    2. X^Y
    Hint:
    100 100
    3100 = 350 . 350 = (3 2 ). (3 2 )

    350 = 325 . 325


    325 = 312 . 312 . 3
    312 = 36 . 36
    36 = 33 . 33
    33 = 31 . 31 . 3
    31 = 30 . 30 . 3
    Divide and conquer

    3. Merge sort

    4. Count Inversion
    https://www.cp.eng.chula.ac.th/~prabhas//teaching/algo/algo2008/count-inv.htm
    The sequence 2, 4, 1, 3, 5 has three inversions (2,1), (4,1), (4,3).
    The idea is similar to "merge" in merge-sort. Merge two sorted lists into one output list,
    but we also count the inversion.

    • divide: size of sequence n to two lists of size n/2


    • conquer: count recursively two lists
    • combine: this is a trick part (to do it in linear time)

    5. Quick Sort
    The quick sort uses divide and conquer just like merge sort but without using additional
    storage.
    The steps are:
    1. Select an element q, called a pivot, from the array. In this algorithm we have
    chosen the last index as the pivot.
    Divide and conquer

    2. The PARTITION function finds the location of the pivot in such a way that all the
    elements smaller than the pivot is on the left side and all the element on the
    right-hand side of the pivot is greater in value. (Items with equal values can go
    either way).
    3. Recursively call the QUICKSORT function which perform quicksort on the array
    on the left side of the pivot and then on the array on the right side, thus dividing
    the task into sub tasks. This is carried out until the arrays can no longer be split.
    Implement Quick sort algorithm. The pseudo code is given below:

    6. Binary Search
    Divide and conquer

    Sample Input Sample Output

    Number of Elements: 5
    Enter elements: 3 4 5 7 2 4 found in index 1
    Key: 4
    Number of Elements: 5
    Enter elements: 3 4 5 7 2 14 not found
    Key: 14

    7.
    Write a function print_odd using divide-and-conquer algorithm to print the odd numbers of
    an array of n integers.

    8.
    Write a function calc_sum using divide-and-conquer algorithm to calculate the sum of an
    array of n integers.

    9.
    Write a function calc_sum using divide-and-conquer algorithm to calculate the sum of the
    even numbers of an array of n integers.
    Divide and conquer

    10. Maximum-sum subarray

    11. Longest common prefix of n strings

    Sample Input Sample Output

    3
    Algolab Alg
    Algorithms
    Algeria
    4
    Algolab No common prefix
    Algorithms
    Algeria
    UIU
    Divide and conquer

    12. Closest pair of points


    Ref: https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/05DivideAndConquer.pdf

    Running time:
    𝑛
    𝑇(𝑛) ≤ 2𝑇 ( ) + 𝑂(𝑛 log 𝑛) 𝑇(𝑛) = 𝑂(𝑛 log 2 𝑛)
    2

    Can we achieve 𝑶(𝒏 𝒍𝒐𝒈 𝒏)?


    Yes. Don't sort points in strip from scratch each time.

    • Each recursive returns two lists: all points sorted by y coordinate, and all points sorted
    by x coordinate.
    • Sort by merging two pre-sorted lists.
    𝑛
    • 𝑇(𝑛) ≤ 2𝑇 ( 2) + 𝑂(𝑛)  𝑇(𝑛) = 𝑂(𝑛 log 𝑛)

    13. More practice problems


    https://leetcode.com/tag/divide-and-conquer/

    Reference:
    • Slides of Dr. Md. Abul Kashem Mia, Professor, CSE Dept, BUET

    You might also like