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.

Update on the joys of hashing

I got an offer from Apress for The Joys of Hashing and I’ve signed the contract. Because of my current condition, I asked for a very late deadline, so I don’t have to finish the book until December 1st. I only need to finish two chapters and then do some editing, so that should be doable without any problems.

If it was just writing, I could have it done in a few weeks, but I need to implement and test a lot, so it will take a bit of time. Especially because I really have to limit how much time I do every day. I haven’t been able to work on the book for a few weeks, because of that, but I plan to look a little at it today.

Because I have now sold the book, I will soon have to pull it from the places where you can currently get it, Leanpub, Payhip, and Gumroad. What I plan to do, is to finish the hash function chapter and leave it for a little bit after that, and then pull it. The last chapter, on more advanced hash tables, will only appear in the Apress version.