1 of 14

Divide and Conquer Recursion

2 of 14

Week 2�Agenda

Day 1:

[20m] Breakout: with at least two different people, review and make corrections to sorting_iterative.py

[15m] Reading: Gauss' Day of Reckoning (18m read time)� ASK YOURSELF: What does this have to do with sorting!?� NEED A HINT? Triangular Series

[10m] BREAK

[40m] TT: Algorithm Analysis (Bubble, Selection, Insertion)��Day 2:

  1. [30m] Worksheet: Recursion Review
  2. [20m] Live Code: Linear + Binary Search Review
  3. [10m] BREAK
  4. [30m] TT: Merge Sort
  5. [LAB] Start Challenges: Divide and Conquer �

​

3 of 14

Recursion Review

4 of 14

What are the two main components of a recursive algorithm?

5 of 14

How would you describe how recursion works?

6 of 14

What is the purpose of the base case?

7 of 14

Activity: Recursion Worksheet

In pairs, work on this Recursion Worksheet

​

8 of 14

Recursion Review

9 of 14

Divide and Conquer Algorithms

  1. Breaks a problem into subproblems that are similar to the original problem
  2. Recursively solves the subproblems
  3. Combines the solutions to the subproblems to solve the original problem

10 of 14

Merge Sort

  1. Recursively break the problem of sorting the entire list into smaller and smaller subproblems
  2. If the list only has one element in the list it is already sorted, return.
  3. Divide the list recursively into two halves until it can no more be divided.
  4. Merge the smaller lists into new list in sorted order

​

https://medium.com/karuna-sehgal/a-simplified-explanation-of-merge-sort-77089fe03bb2

11 of 14

Merge Sort

12 of 14

Let’s visualize merge sort

13 of 14

Write some pseudocode for merge sort

​

Use this card deck

14 of 14

Let’s code merge sort!