Introduction
IntroductionΒΆ
In this part about algortithm design paradigms we want to expose you to two of the most powerful techniques for coming up with algorithms.
We follow chapters 1 and 3 of Algorithms Illuminated (in part 1), to introduce and give examples of Divide & Conquer. You should make sure to also read chapter 4 that presents a recipe, the Master method, that will help you calculate the execution time of algorithms designed using Divide and COnquer. You will do experiments for a sorting algorithm that is a case of Divide and Conquer (Quicksort) in the first assignment: Laboration 1.
We follow chapter 16 of Algorithms Illuminated (in part 3), to introduce and give examples of Dynamic programming. You will use this technique and do experiments to estimate execution time behaviour in the second assignment for the course: Laboration 2.
Hopefully, when you are confronted with a problem of your own and need to come up with a solution you will know about these two techniques and will be able to test whether they help you come up with a feasible algorithm.
The ideas and most of the material are taken from the book Algorithms Illuminated.