Resources
The links to the resources on this page were verified on March 7, 2018. Let Alex know if you find any of them broken!
Books
We don’t have an official course book, since the lectures are fairly self-contained and you can find so much online. If you feel like buying a book anyway, we can recommend Algorithms, by Robert Sedgewick and Kevin Wayne. This is an excellent book that covers much of the stuff in the course in a very clear way.
If you have Sedgewick’s book, then the course covers most of chapters 1-3 (Fundamentals, Sorting, Searching) and some of chapter 4 (Graphs). The main differences are:
-
We also cover AVL trees, skew heaps, skip lists, and queues implemented as a pair of lists (see e.g. the Chalmers FP course).
-
Sedgewick treats AA trees slightly differently and calls them “red-black BSTs”. If you prefer to use this variant then that’s fine.
-
We don’t cover: union-find, selection sort, shellsort, bottom-up mergesort, heapsort, and several of the graph algorithms. In particular, the graph algorithms we cover are breadth-first search, depth-first search, topological sorting, strongly-connected components, Dijkstra’s algorithm and Prim’s algorithm.
Note that this is not meant to be an exhaustive list; you should look at the lectures to see everything in the course.
Other literature
-
One of the real classic computer science books is Programming Pearls by Jon Bentley (ISBN 9780201657883), and it’s very relevant for the course. It’s a collection of articles, most of them describing an imaginative solution to some programming problem. It’s also well written and quite short. If you read it you will be a better programmer!
-
Here is a Haskell compendium (in Swedish) which contains implementations of several data structures and algorithms from the course. The code from the compendium is also available.
-
For data structures in functional languages, the classic reference is Chris Okasaki’s book, Purely Functional Data Structures. Instead of buying the book, you can download his PhD thesis, which contains much of the same stuff.
-
If you want to brush up on your Haskell skills, try Learn You a Haskell for Great Good. You can read it free online.
-
Real World Haskell is also good, and also free to read online.
Links
Two nice sites for visualising data structures are VisuAlgo and Data Structure Visualizations.
For doing the labs you will want to look up library documentation: Java collections library, Haskell standard libraries.
-
The de facto standard Haskell compiler GHC
-
The Oracle Java compiler
-
The IntelliJ IDE for Java. Note that it is fine to use any IDE you like (e.g. Eclipse)
