Data Structures and Algorithms

The course does not follow a single textbook. The following six works will be drawn on throughout the semester.

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. 4th ed., MIT Press, 2022.
• Donald E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms. 3rd ed., Addison-Wesley, 1997.
• Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching. 2nd ed., Addison-Wesley, 1998.
• Chris Okasaki. Purely Functional Data Structures. Cambridge University Press, 1998.
• Robert Sedgewick and Kevin Wayne. Algorithms. 4th ed., Addison-Wesley, 2011.
• Niklaus Wirth. Algorithms + Data Structures = Programs. Prentice-Hall, 1976.

Visualisations: These interactive sites are useful for building intuition about how data structures and algorithms behave over time.

• Data Structure Visualizations (David Galles, University of San Francisco)
• VisuAlgo (Steven Halim, NUS)
• CS Visualizer

OCaml: For learning the language we will use in class.

• Functional Programming with OCaml (KC Sivaramakrishnan, IIT Madras; NPTEL / SWAYAM)
• OCaml Programming: Correct + Efficient + Beautiful (Michael R. Clarkson et al., Cornell CS 3110 textbook)
• Real World OCaml (Anil Madhavapeddy, Yaron Minsky, and Jason Hickey)

Setting up OCaml: Install the OCaml compiler, the opam package manager, and the dune build system. The official install guide at ocaml.org/install covers macOS, Linux, and Windows. Once opam is installed, run opam init, then opam install dune utop to get the interactive top-level and the build tool used throughout the course.