D&A -- Learning Objectives Week 2
---------------------------------
students
* see common algorithms for searching and selecting
* learn to know how to apply the principle of divide and conquer and corresponding recurrences (from week 1) to relevant problems of searching and selection
* apply the correctness proof techniques from week 1 to relevant problems such as searching and selection
* learn, by ways of a simple example (linear and binary search) how to prove lower bounds for algorithms and thus derive the asymptoctic complexity of a *problem*
* learn to know expected asymptotic bounds for a randomized algorithm (quick select)
* learn to know a non-trivial recursive algorithm to solve the selection problem in O(n).
* learn to know useful tools offered by C++ (such as the ranged-for, type inference with the keyword auto, subscript operators and iterators) in order to implement and efficiently use container classes.
* learn to know and apply the mechanisms for efficient memory management in C++, therewith deepening and extending the knowledge gained in course Computer Science (rule of three, rule of five).