Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Divide and Conquer Algorithms.
• Analyzing Divide-and-Conquer Algorithms.
• Estimating Recurrence Relations.
• Solving Recurrence Relations with Recursion Trees.
• Proving Recurrence Relations with the Substitution Method.
• Solving Recurrence Relations with the Master Theorem.

Preliminaries

Admin

• My normal office hours are MWF 11:00-11:50. I've added MWF 8:30-9:00. You sign up for those at https://rebelsky.youcanbook.me.

Upcoming Work

• For Wednesday: Problems 2-1, 2-2, 2-3, 2-8, 2-13, 2-14, 2-15, 2-18, 2-23, 2-32, 2-37, any two interview problems from chapter 2.
• Revised: Problems 2-1, 2-2, 2-8, 2-13, 2-18, 2-23, two interview problems
  • Turn in hardcopy.
  • I prefer that you write your homework in LaTeX. If you don't know LaTeX, now is a good time to start learning!
• For Wednesday: Read Skiena 4-10. (Optionally: Read CLRS 4.)

Extra Credit

Academic

• CS Table, Tuesdays, topic Cellular Networks for Developing Countries
• CS Extras, Thursdays, topics forthcoming.
• Convo, Thursday, 11am.

Peer

• Congrats to Men's Soccer! (And to EE for the picture!)
• Congrats to Women's Soccer!

Questions

Divide and Conquer Algorithms

Basic strategy

• Take a large problem and divide it into smaller problems (does smaller = simpler)
• Solve the smaller problems (often using the same technique)
• Compose the solved problems into a solution to the bigger problem.

What divide and conquer algorithms do you already know?

• Merge sort
  • Split values in half
  • Sort each half
  • Merge by repeatedly removing the smallest element from either sorted half
• Binary search
  • Requirement on data: Sorted!
  • Split values in half
  • Look at middle
  • Search in appropriate half
• Quicksort
  • Pick a pivot
  • Separate into smaller than pivot and larger than pivot
  • Sort the two halves
  • Join them together (can happen automatically)

Analyzing Divide-and-Conquer Algorithms

How do we normally analyze algorithms (informally)

• Identify all the loops
• Count the number of times each loop repeats
• Count the number of steps in each loop
• Multiply and add as appropriate

Will this strategy work for divide and conquer?

    define Quicksort(A)
      if (small(A))
        return
      else
        partition(A)
        Quicksort(firsthalf(A))
        Quicksort(secondhalf(A))

In general, we write equations to carefully specify the cost. Merge sort

    define mergesort(A)
      if (oneelement(A))
        return
      merge(sort(firsthalf(A)),sort(secondhalf(A)))

    T(n) is supposed to be "bound on steps to sort an array
    of size n using mergesort"

    T(1) = 1
    T(n) = T(n/2) ; sort(firsthalf(A))
           + T(n/2) ; sort(secondhalf(A))
           + Theta(n) ; merge

As mathematicians, we'd like to find an exact bound for that function. (As computer scientists, we're okay with an extra constant multiplier.) How do we do so?

Estimating Recurrence Relations

    T(n) <= 2*T(n/2) + c*n
    T(1) = 1

Top-down expansion

• Repeatedly expand the right-hand side using the recurrence relation and look for a pattern.

  T(n) <= 2*T(n/2) + c*n
          ; T(n/2) <= 2*T(n/4) + c*n/2
       <= 2*(2*T(n/4) + c*n/2) + c*n
       =  4*T(n/4) + 2*c*n 
          ; T(n/4) <= 2*T(n/8) + c*n/4
       <= 4*(2*T(n/8) + c*n/4) + 2*c*n
       =  8*T(n/8) + cn + 2cn 
       =  8*T(n/8) + 3cn
          ; T(n/8) <= 2*T(n/16) + c*n/8
       <= 8*(2*T(n/16) + c*n/8) + 3cn
       =  16*T(n/16) + 4cn
  

Look at the main results

    T(n) <= 2*T(n/2) + c*n
         <= 4*T(n/4) + 2*c*n 
         <= 8*T(n/8) + 3cn
         <= 16*T(n/16) + 4cn
         <= 2^k*T(n/2^k) + k*c*n

Solve for 2^k = n; k = log_2(n)

        <= n*T(1) + log_2(n)*c*n
        <= 1 + c*n*log_2(n)

Bottom-up expansion

• Build up from T(1) to T(2) to T(4) to T(8) to .... And look for a pattern.

  T(1) = 1
  T(2) <= 2*T(1) + 2c = 2 + 2c
  T(4) <= 2*T(2) + 4c <= 2*(2 + 2c) + 4c <= 4 + 8c
  

Solving Recurrence Relations with Recursion Trees

    T(n) = 3*T(n/4) + Theta(n^2)

Proving Recurrence Relations with the Substitution Method

Solving Recurrence Relations with the Master Theorem