Lab 6 – Hashing in Exhibition Layout Design

Format: 3 groups, 1 problem each
Github Classroom link

Goal: Use hashing as an algorithmic tool (not just lookup tables)

Overview

In this lab, each group will solve a different subproblem from the Art Gallery Exhibition Planning project using hashing for a different purpose:

Group 1 → State Deduplication (Avoiding repeated layouts)
Group 2 → Fast Constraint Checking (Conflict detection)
Group 3 → Load Balancing and Randomized Assignment

Each group must:

  1. Clearly define their data representation.
  2. Design a suitable hash function.
  3. Decide how to handle collisions.
  4. Test on a small dataset (for debugging).
  5. Test on a larger dataset (performance).

GROUP 1 — Detecting Duplicate Layouts

Problem Description

When generating candidate exhibition layouts (via greedy or backtracking), we may accidentally generate the same layout multiple times.

Your task:

Design a system that detects whether a layout has already been seen.

A layout consists of placements of artworks into locations.

We want to avoid re-evaluating identical layouts.

Subproblem

Given:

  • A list of artwork placements
  • Each placement = (room, wall, artwork, orientation)

Detect whether this layout has already been evaluated.

Small Dataset (Debug)

Rooms: R1, R2
Walls per room: W1, W2
Artworks: A1, A2, A3

Example Layout 1:
(R1, W1, A1, 0°)
(R1, W2, A2, 90°)
(R2, W1, A3, 0°)

Example Layout 2 (duplicate of 1, but listed in different order):
(R2, W1, A3, 0°)
(R1, W2, A2, 90°)
(R1, W1, A1, 0°)

These must be detected as identical.

Large Dataset (Performance Test)

Rooms: R1–R5
Walls per room: W1–W6
Artworks: A1–A20
Orientations: 0°, 90°, 180°, 270°

Randomly generate 10,000 candidate layouts (with possible duplicates).

Tasks

  1. Create a canonical representation:
    • Sort placements lexicographically.
    • Convert to a single string.
    • Hash the string.
  2. Store layout hashes in a hash set.
  3. Measure:
    • How many duplicates detected?
    • Time without hashing vs with hashing.

Hash Function Ideas

  • Polynomial rolling hash over the canonical string.
  • std::hash<string> (if in C++).
  • Combine fields:
    h = room_id * P1 + wall_id * P2 + artwork_id * P3 + orientation * P4

Collision Handling

  • Use separate chaining (hash set of strings).
  • Or store full canonical string alongside hash for verification.

Goal Insight

Hashing as state-space pruning.

GROUP 2 — Fast Conflict Detection

Problem Description

When placing an artwork, we must check constraints:

  • A wall can hold at most one artwork.
  • A room can hold at most 3 sculptures.
  • No two artworks by the same artist in the same room.
  • Certain walls conflict (e.g., W2 conflicts with W3 if both hold sculptures).

We need fast membership and conflict checking.

Small Dataset (Debug)

Rooms: R1, R2
Walls: W1, W2, W3
Artists:
A1 → Picasso
A2 → Monet
A3 → Picasso

Placements:
(R1, W1, A1)
(R1, W2, A2)

Now test adding:
(R1, W3, A3)

Should reject (same artist Picasso in same room).

Large Dataset (Performance Test)

Rooms: R1–R6
Walls per room: W1–W8
Artworks: A1–A50
Artists randomly assigned
Randomly generate 5,000 placement attempts.

Tasks

Design hash-based structures:

  1. occupied_walls = hash set of (room, wall)
  2. room_artist_map = hash map:
    key: (room, artist)
    value: count
  3. sculpture_count = hash map:
    key: room
    value: count

Each constraint check must be O(1).

Hash Function Ideas

  • Combine integers using:
    hash = room_id * 1000 + wall_id
  • Or use pair hashing.
  • Or concatenate “R1-W2”.

Collision Handling

  • Use separate chaining.
  • For custom hash maps, compare full key on match.

Goal Insight

Hashing as fast constraint enforcement.

GROUP 3 — Randomized Room Assignment and Load Balancing

Problem Description

We want to distribute artworks evenly across rooms.

Artworks = balls
Rooms = bins

Goal:

  • Even load
  • No room exceeds capacity B

Subproblem

Given:
n artworks
m rooms
capacity B per room

Assign artworks randomly using hashing:
room = h(artwork_id) mod m

Detect overflow.

Small Dataset (Debug)

Rooms: R1, R2, R3
Capacity: B = 2
Artworks: A1–A6

Test hash assignments manually.

Large Dataset (Performance Test)

Rooms: R1–R10
Capacity: B = 6
Artworks: A1–A200

Tasks

  1. Design hash function for artwork_id.
  2. Assign each artwork to a room via hashing.
  3. Track load factor α = n/m.
  4. Detect overflow.
  5. Measure:
    • Maximum load
    • Number of overflows
    • Distribution histogram

Then repeat with:

  • Different hash multipliers
  • Different m
  • Different α

Hash Function Ideas

  • h(x) = (a*x + b) mod large_prime
  • Then mod m
  • Try different constants.

Collision Handling

Here collision = multiple artworks assigned to same room.

Use:

  • Vector/list per room (chaining model).

Goal Insight

Hashing as randomized load balancing.

Deliverables (All Groups)

Each group must submit:

  1. Problem summary
  2. Data representation
  3. Hash function design and justification
  4. Collision handling strategy
  5. Small dataset demonstration
  6. Large dataset performance test
  7. Reflection:
    • What happens when load factor increases?
    • What failure cases did you observe?
Scroll to Top