YSC2229: Introductory Data Structures and Algorithms
1. Software Prerequisites
2. OCaml Style Guide
3. Policies
4. Midterm Project: Memory Allocation and Reclamation
5. Final Project: Vroomba Programming
1. Chapter 01: Introduction
2. Chapter 02: Working with Arrays
3. Chapter 03: Complexity of Algorithms and Order Notation
4. Chapter 04: Divide-and-Conquer Algorithms
5. Chapter 05: Binary Heaps and Priority Queues
6. Chapter 06: Abstract Data Types
7. Chapter 07: Hashing-Based Data Structures
7.1. Hash-tables
7.2. Generalised Hash-Tables
7.3. Bloom Filters and Their Applications
8. Chapter 08: Searching in Strings
9. Chapter 09: Backtracking and Dynamic Programming
10. Chapter 10: Data Encoding and Compression
11. Chapter 11: Binary Search Trees
12. Chapter 12: Graph Algorithms
13. Chapter 13: Elements of Computational Geometry
YSC2229: Introductory Data Structures and Algorithms
»
7.
Chapter 07: Hashing-Based Data Structures
7.
Chapter 07: Hashing-Based Data Structures
7.1. Hash-tables
7.1.1. Allocation by hashing keys
7.1.2. Operations on hash-tables
7.1.3. Implementing hash-tables
7.1.4. Hash-tables in action
7.2. Generalised Hash-Tables
7.2.1. OCaml’s universal hashing
7.2.2. Redefining hash-table signature
7.2.3. A framework for testing hash-tables
7.2.4. A simple list-based hash-table
7.2.5. Testing a Simple Hash-Table
7.2.6. A Resizable hash-table
7.2.7. Comparing performance of different implementations
7.3. Bloom Filters and Their Applications
7.3.1. High-level intuition
7.3.2. Bloom filter signature
7.3.3. Implementing a Bloom filter
7.3.4. Experimenting with Bloom filters
7.3.5. Testing Bloom Filters
7.3.6. Improving Simple Hash-table with a Bloom filter
7.3.7. Comparing performance