Lectures 3 & 4 – Divide and Conquer

The main slides for the introduction to Divide and Conquer design template.

DivideAndConquer_Part1Download

A helpful video on D&C design technique.

There are 3 techniques for sovling recurrence relations:

  • Unfolding
  • Substitution (Guess and Prove)
  • Master Theorem Cookbook Method

Some applications of D&C Technique.

DivideAndConquer_Part2Download

A helpful video on algorithms for finding median in linear time.

Closest pair of points is a fun problem that uses divide and conquer approach.