D&A -- Learning Objectives Week 3
---------------------------------
students
* see common algorithms for sorting
* extend their knowledge on how to apply the principle of divide and conquer and corresponding recurrences (from week 1) at relevant problems of sorting
* students see recursion trees and how they relate to the derivation of the Master Theorem and see how the Master theorem is applied for solving simple recurrences.
* are not required to be able to prove the Master Theorem, are not required to know the Master Theorem by heart.
* extend their knowledge on randomized algorithms by analyzing the QuickSort algorithm
* see another example of a problem complexity consideration: sorting is indeed Theta(n log n)
* see linear-time sorting algorithms based on assumptions about the keys: radix-sort / bucket sort