Lecture notes on Computational Thinking

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

  1. Introduction to algorithms — invariants and termination and such.
  2. Algorithmic efficiency — big-Oh notation and how to reason about running times.
  3. Searching and sorting — linear and binary search plus some quadratic time sorting algorithms. Maybe bucket sort as well.
  4. 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.

You can get the current draft, containing the yellow chapters, on Leanpub, Gumroad and Payhip.

Author: Thomas Mailund

My name is Thomas Mailund and I am a research associate professor at the Bioinformatics Research Center, Uni Aarhus. Before this I did a postdoc at the Dept of Statistics, Uni Oxford, and got my PhD from the Dept of Computer Science, Uni Aarhus.

Leave a Reply