Divide-and-Conquer: Recurrence relations, Mergesort (recap), integer multiplication

Slides:

https://www2.compute.dtu.dk/courses/02110/2023/slides/Divide-and-conquer-1x1.pdf

Problems:

https://www2.compute.dtu.dk/courses/02110/2023/weekplans/divide-and-conquer.pdf

• KT 4.1, 4.2, 4.5
• (KT 5.1, 5.2, 5.5 in the American edition)

Divide and conquer

• Divide -and-Conquer. • Break up problem into several parts. • Solve each part recursively. • Combine solutions to subproblems into overall solution.

https://www.youtube.com/watch?v=YOh6hBtX5l0&ab_channel=KantanCoding

Mergesort

Divide the arrays into size 1