1. Course Syllabus¶
The list of topics below is a subject of possible minor changes.
- Week 01
- Introduction
- Testing OCaml Code
- Correctness of Recursive Algorithms
- From Recursion to Imperative Loops
- Sorting Lists via Insertion Sort
- Week 02
- Arrays and Operations on Them
- Insertion Sort and Selection Sort on Arrays
- Complexity of Algorithms and Order Notation
- Sums of Series and Complexities of Loops
- Week 03
- Complexity of Simple Recursive Algorithms
- Generating Arrays
- Searching in Arrays
- Merge Sort
- Week 04
- Quicksort and its Variations
- Complexity of Divide-and-Conquer Algorithms
- Generalising Comparison-Based Sorting
- Best-Worst Case for Comparison-Based Sorting
- Sorting in Linear Time
- Week 05
- Printing and Validating Generic Arrays
- Binary Heaps
- Maintaining Binary Heaps
- Heapsort and Priority Queues
- Week 06
- Abstract Data Types
- Stacks and Queues
- Testing Abstract Data Types
Mid-Term Project
- Week 07
- Hash-tables
- Scalable Hash-Tables
- Bloom Filters and Their Applications
- Week 08
- Substring Search
- Rabin-Karp Search
- Knuth–Morris–Pratt Algorithm
- Week 09
- Equivalance Classes and Union-Find
- Constraint Solving via Backtracking
- Optimisation Problems and Dynamic Programming
- Week 10
- File Input and Output in OCaml
- Binary Encoding of Data
- Run-Length Encoding
- Huffman Encoding
- Week 11
- Representing Sets via Binary Search Trees
- Representing Graphs
- Week 12
- Reachability and Graph Traversals
- Single-Source Shortest Paths
- Minimal Spanning Trees
- Week 13
- Basics of Computational Geometry
- Points, Segments and their Properties
- Working with Polygons
- Convex Hulls
Final Project