Introductory Data Structures and Algorithms

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

• Lectures: Fridays, 2:30-5:30pm
• Location: ERC-SR10 Seminar Room 10, UTown (two storeys above Starbucks)
• Instructor: Ilya Sergey
• Office hours: Wednesdays, 5:00-7:00pm, #RC3-01-03E (Cendana)
• Peer Tutors:
  • Tram Hoang, Wednesdays, 7pm-9pm, CR20 (RC3-01-02)
  • Gabriel Petrov, Thursdays, 6pm-8pm, CR20 (RC3-01-02)

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

Lecture notes will be posted gradually as we progress through the material.

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: each week N is a separate branch weekN.
• Example OCaml project with graphics
• GitHub Organisation (please, email me your GitHub handle to have access)

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. Introduction to Objective Caml by Jason Hickey
2. Real World OCaml by Yaron Minsky, Anil Madhavapeddy, and Jason Hickey