YSC2229: Introductory Data Structures and Algorithms
1. Course Syllabus
2. Software Prerequisites
3. OCaml Style Guide
1. Week 01: Introduction
2. Week 02: Working with Arrays
3. Week 03: Complexity of Algorithms and Order Notation
4. Week 04: Divide-and-Conquer Algorithms
5. Week 05: Binary Heaps and Priority Queues
6. Week 06: Abstract Data Types
7. Midterm Project: Memory Allocation and Reclamation
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
10. Week 09: Backtracking and Dynamic Programming
11. Week 10: Data Encoding and Compression
12. Week 11: Binary Search Trees
13. Week 12: Graph Algorithms
14. Week 13: Elements of Computational Geometry
15. Final Project: Vroomba Programming
YSC2229: Introductory Data Structures and Algorithms
Docs
»
8. Week 07: Hashing-Based Data Structures
8. Week 07: Hashing-Based Data Structures
¶
8.1. Hash-tables
8.1.1. Allocation by hashing keys
8.1.2. Operations on hash-tables
8.1.3. Implementing hash-tables
8.1.4. Hash-tables in action
8.2. Generalised Hash-Tables
8.2.1. OCaml’s universal hashing
8.2.2. Redefining hash-table signature
8.2.3. A framework for testing hash-tables
8.2.4. A simple list-based hash-table
8.2.5. Testing a Simple Hash-Table
8.2.6. A Resizable hash-table
8.2.7. Comparing performance of different implementations
8.3. Bloom Filters and Their Applications
8.3.1. High-level intuition
8.3.2. Bloom filter signature
8.3.3. Implementing a Bloom filter
8.3.4. Experimenting with Bloom filters
8.3.5. Testing Bloom Filters
8.3.6. Improving Simple Hash-table with a Bloom filter
8.3.7. Comparing performance