THINK FIRST·CODE LATER

← All labs

Linear versus quadratic probing

Problem

Write ProbingCompare. Read the table size m, then non-negative keys. Insert each key into two open-addressing tables with h(k) = k mod m: one with linear probing (h + i), one with quadratic probing (h + i²), trying i = 0, 1, …, m − 1. Print the number of slots examined for each insertion (FAILED if quadratic probing finds no free slot), both tables (_ for an empty slot), the load factor, the total probes and the longest run of occupied slots in each table.

For the input

11 22 33 44 55 12 23

the program prints

insert 22 (home 0): linear 1 probe(s), quadratic 1 probe(s)
insert 33 (home 0): linear 2 probe(s), quadratic 2 probe(s)
insert 44 (home 0): linear 3 probe(s), quadratic 3 probe(s)
insert 55 (home 0): linear 4 probe(s), quadratic 4 probe(s)
insert 12 (home 1): linear 4 probe(s), quadratic 2 probe(s)
insert 23 (home 1): linear 5 probe(s), quadratic 3 probe(s)
linear:    22 33 44 55 12 23 _ _ _ _ _
quadratic: 22 33 12 _ 44 23 _ _ _ 55 _
Load factor: 0.55
Total probes: linear 19, quadratic 15
Longest cluster: linear 6, quadratic 3

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d14-3-data-1.txt

11 22 33 44 55 12 23
What your program must print for d14-3-data-1.txt
insert 22 (home 0): linear 1 probe(s), quadratic 1 probe(s)
insert 33 (home 0): linear 2 probe(s), quadratic 2 probe(s)
insert 44 (home 0): linear 3 probe(s), quadratic 3 probe(s)
insert 55 (home 0): linear 4 probe(s), quadratic 4 probe(s)
insert 12 (home 1): linear 4 probe(s), quadratic 2 probe(s)
insert 23 (home 1): linear 5 probe(s), quadratic 3 probe(s)
linear:    22 33 44 55 12 23 _ _ _ _ _
quadratic: 22 33 12 _ 44 23 _ _ _ 55 _
Load factor: 0.55
Total probes: linear 19, quadratic 15
Longest cluster: linear 6, quadratic 3

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d14-3-data-1.txt

Windows PowerShell does not understand <:

Get-Content d14-3-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.