I am working on some lecture notes that should become a book at some point. It is for a class on “Computational Thinking”, which I guess is just a fancy term for algorithms and data structures. I am only teaching a third of the class, so I need four topics for the autumn term. Those will be
- Introduction to algorithms — invariants and termination and such.
- Algorithmic efficiency — big-Oh notation and how to reason about running times.
- Searching and sorting — linear and binary search plus some quadratic time sorting algorithms. Maybe bucket sort as well.
- Recursion and divide-and-conquer — pretty self explanatory. Will include some log-linear sorting algorithms here.
I managed to get a lot written the last two days, and today I finished the chapter on algorithmic efficiency. The plan is to get the non-red chapters in my progress-spreadsheet done by August and then work on the other chapters over the next year.
Here, the yellow chapters are where I have complete drafts (but haven’t proofread or edited them yet) while the orange chapters are those that I have started on, but haven’t completed the draft of.
I know it is notoriously easy to get some details wrong, so if there are any algorithmic-inclined people out there, I would love some feedback. I will also be very greatful if you could suggest some exercises for these topics; those are very important but I find it hard to think of good ones.