Data Structure and Algorithm Design II

Chapter 6

Xingang (Ian) Fang

Sections

  • Divide and Conquer

Divide and Conquer

Xingang (Ian) Fang

Outline

  • Overview

  • Stages

  • Pro and Con

  • Applications

  • Complexity

Overview

  • An algorithmic paradigm that solves a problem by breaking it into subproblems, solving the subproblems recursively, and combining the solutions to the subproblems to solve the original problem.

  • Real-world example: Jigsaw puzzle

    • Group pieces by color, border/non-border, etc.

    • Solve each group separately

    • Combine the finished parts

Jigsaw Puzzle

Credit: Photo by Bianca Ackermann on Unsplash

Stages

  1. Divide - Break the problem into subproblems

  2. Conquer - Solve the subproblems recursively

  3. Combine - Combine the solutions to the subproblems to solve the original problem

Sometimes, the three stages of Divide and Conquer may not be distinct. For example, in Quick Sort, the division and combination steps are combined into a single partitioning step.

Pro and Con

  • Pros

    • Simplification of Complex Problems

    • Efficiency Improvements

    • Parallel Processing Potential

    • Flexibility and Versatility

  • Cons

    • Recursive Overhead

    • Risk of Stack Overflow

    • Not Always Optimal for Small Inputs

    • Complexity in Design

Applications

  • Binary Search

  • Quick Sort

  • Merge Sort

  • Max Subarray Sum

  • Closest Pair of Points

  • Strassen’s Matrix Multiplication

  • Fast Fourier Transform (FFT) for Discrete Fourier Transform (DFT)

Time Complexity

  • Steps

    • Find recurrence relation

    • Solve recurrence relation using Master Theorem

  • Quick Sort \(T(n) = T(k) + T(n-k-1) + \Theta (n)\), where \(k\) is the number of elements which are smaller than pivot

  • Merge Sort \(T(n) = 2T(n/2) + \Theta (n)\)

  • Binary Search \(T(n) = T(n/2) + \Theta (1)\)

  • Max Subarray Sum \(T(n) = 2T(n/2) + \Theta (n)\)

  • Closest Pair of Points \(T(n) = 2T(n/2) + \Theta (n \log n)\)

  • Strassen’s Matrix Multiplication \(T(n) = 7T(n/2) + \Theta (n^2)\)

  • Fast Fourier Transform (FFT) \(T(n) = 2T(n/2) + \Theta (n)\)

Exercise: Solve the recurrence relation for each of the above algorithms

Relationships to Other Paradigms

  • Dynamic Programming

    Properties

    Divide and Conquer

    Dynamic Programming

    Subproblems

    Distinct

    Overlapping

    Direction

    Top-down

    Bottom-up/Top-down

    Parallelism

    Friendly

    Friendly

    Dynamic Programming is considered an extension of Divide and Conquer in many cases. However, we employed a narrower definition of Divide and Conquer in this lecture so they are treated as separate paradigms.