Lecture 2
Lecture 2ΒΆ
The book Algorithms illuminated swiftly describes three algorithms for solving the problem of sorting an array in less than a page. It immediatelly discards the three solutions because they all have quadratic running time.
In this lecture we will try to walk you through the material that allows you to understand this statement in detail and provides you with the concepts you need for you yourself to decide whether to discard algorithms because of their running time behaviour.
We continue to guide you to implement algorithms with Python programs. We start by doing it for you but we add more and more exercises for you to test yourself.
We also continue to test the programs we write using programs that generate random data for the programs we want to test. And finally, we continue to experiment and write programs that allow us to explore the running time behaviour of the programs we write.
This lecture attempts to do the following:
We introduce you to the problem of sorting arrays.
We program two of the three solutions that the book describes briefly and discards.
We show how to test these programs.
We expose you to the running time of these programs.
We refer you to the book Algorithms Illuminated for explanations on how to analyze algorithms, including what principles we use for doing so.
We expose you to the math you need in order to understand your analyses.
We explain how to program experiments that can be used to test your analyses or to explore execution time of your programs.
We do this in the context of a well known algorithm that we implement with three different programs.
We expose you to a technique called Divide and Conquer for designing algorithms.