Previous Lecture

lect16

Next Lecture

lect16,

Mergesort: Divide and Conquer

Code from lecture

https://github.com/ucsb-cs24-w26/cs24-w26-lectures/tree/main/lect16

Handout

• Link to practice handout: https://bit.ly/Divide-and-Conquer-Practice
• Link to leetcode medium problem: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Topics

• Divide and Conquer Algorithms
• Subdivide a larger problem into smaller problems
• Solve each smaller part

• Combine solutions of smaller sub problems back into the larger problem

• Mergesort as an example of efficient sorting algo that uses the divide and conquer approach and runs in O(n log n)
• Practice by solving leetcode problem