Introductory Data Structures and Algorithms

This course on classic imperative data structures and algorithms has been offered by Ilya Sergey at Yale-NUS College in 2019-2021. Feel free to use all the materials and submit pull requests on GitHub (the links to the sources are given below).

Please, get in touch is you’d like to get access to the homework assignments or to the model solutions for the midterm/final projects.

• 1. Course Syllabus
• 2. Software Prerequisites
• 3. OCaml Style Guide

Lecture Notes

• 1. Week 01: Introduction
  • 1.1. Introduction
  • 1.2. Testing OCaml Code
  • 1.3. Correctness of Recursive Algorithms
  • 1.4. From Recursion to Imperative Loops
  • 1.5. Sorting Lists via Insertion Sort
  • 1.6. Exercises
• 2. Week 02: Working with Arrays
  • 2.1. Arrays and Operations on Them
  • 2.2. Insertion Sort on Arrays
  • 2.3. Selection Sort
  • 2.4. Exercises
• 3. Week 03: Complexity of Algorithms and Order Notation
  • 3.1. Generating Arrays
  • 3.2. Complexity of Algorithms
  • 3.3. Order Notation
  • 3.4. Sums of Series and Complexities of Loops
  • 3.5. Complexity of Simple Recursive Algorithms
  • 3.6. Exercises
• 4. Week 04: Divide-and-Conquer Algorithms
  • 4.1. Searching in Arrays
  • 4.2. Merge Sort
  • 4.3. Quicksort and its Variations
  • 4.4. Complexity of Divide-and-Conquer Algorithms
  • 4.5. Generalising Comparison-Based Sorting
  • 4.6. Exercises
• 5. Week 05: Binary Heaps and Priority Queues
  • 5.1. Printing and Validating Generic Arrays
  • 5.2. Best-Worst Case for Comparison-Based Sorting
  • 5.3. Sorting in Linear Time
  • 5.4. Binary Heaps
  • 5.5. Maintaining Binary Heaps
  • 5.6. Heapsort
  • 5.7. Priority Queues
  • 5.8. Exercises
• 6. Week 06: Abstract Data Types
  • 6.1. Equivalence Classes and Union-Find
  • 6.2. Information Hiding and Abstraction
  • 6.3. Stacks
  • 6.4. Queues
  • 6.5. Exercises
• 7. Midterm Project: Memory Allocation and Reclamation
  • 7.1. Coding Assignment
  • 7.2. Report
• 8. Week 07: Hashing-Based Data Structures
  • 8.1. Hash-tables
  • 8.2. Generalised Hash-Tables
  • 8.3. Bloom Filters and Their Applications
• 9. Week 08: Searching in Strings
  • 9.1. Substring Search
  • 9.2. Rabin-Karp Search
  • 9.3. Knuth–Morris–Pratt Algorithm
  • 9.4. Exercises
• 10. Week 09: Backtracking and Dynamic Programming
  • 10.1. Constraint Solving via Backtracking
  • 10.2. Optimisation Problems and Dynamic Programming
• 11. Week 10: Data Encoding and Compression
  • 11.1. File Input and Output in OCaml
  • 11.2. Binary Encoding of Data
  • 11.3. Run-Length Encoding
  • 11.4. Huffman Encoding
  • 11.5. Installing GraphViz
• 12. Week 11: Binary Search Trees
  • 12.1. Representing Sets via Binary Search Trees
• 13. Week 12: Graph Algorithms
  • 13.1. Representing Graphs
  • 13.2. Graphs as Linked Data Structures
  • 13.3. Reachability and Graph Traversals
  • 13.4. Single-Source Shortest Paths
  • 13.5. Minimal Spanning Trees
  • 13.6. Exercises
• 14. Week 13: Elements of Computational Geometry
  • 14.1. Basics of Computational Geometry
  • 14.2. Points, Segments and their Properties
  • 14.3. Working with Polygons
  • 14.4. Convex Hulls
• 15. Final Project: Vroomba Programming
  • 15.1. Coding Assignment
  • 15.2. Report

Slides and Supplementary Materials

• Week 01 Introductory Slides
• Matrix determinants in Haskell
• Week 04 Slides on Advanced Sorting
• Week 05 Slides on Best-Worst Sorting Complexity
• Week 09 Slides on Hamiltonian Paths
• Board shots from the Backtracking lecture
• Week 13 Slides (Wrapping Up)

Examples and Code

• Code from the lectures
• Example OCaml project with graphics
• Midterm project starter code
• Final project starter code
• Sources of these lecture notes

Pull requests are welcome!

Textbooks

On Algorithms and Data Structures

1. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
2. (Optional) Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne. This book has some great in-depth examples of basic algorithms.

On OCaml

1. Real World OCaml by Yaron Minsky and Anil Madhavapeddy