Guide
User Manual:
Open the PDF directly: View PDF 
.
Page Count: 2
POTD41.1. Problem of the Day #41
Download and Extract
An initial setup of files is provided to you via a shell script: Download potd-q41
Using a terminal, extract the initial files by running the shell script you just downloaded (you
will need to navigate to the directory where you saved the file):
sh potd-q41.sh
Your files for this problem will be in the potd-q41 directory.
The Problem
Task 1: Implement the Bernstein hash function
Today, weʼll construct a more sophisticated hash function, called the Bernstein hash. For a
string str, the Bernstein hash, b_hash, is computed by iterating over its characters. The
pseudo-code is as shown below:
b_hash = 5381
for all character in str:
b_hash *= 33 + character //use the ASCII value of the character here
The magic number 33 is used simply because it works! Why it works better than many other
constants, prime or not, has never been adequately explained. Your task is to write a
function unsigned long int bernstein(string str) that takes in a string as an input and
returns its hash. Notice how quickly the hash grows with the length of the input string.
Task 2: Effect of character ordering on the Bernstein hash
Weʼll now test the hash function with various inputs. Recall that the additive hash (the one
you implemented in the last POTD) is invariant to the ordering of the letters in a string. Thus,
POTS and STOP have the same additive hash. This is usually not desirable. Weʼd first like to
see if the Bernstein hash function is sensitive to the ordering of characters. To do so, weʼll
compare the hashes of a string and its reverse. Write a function reverse() to invert a string,
and check if the Bernstein hash for a string changes if the string is inverted.
Example Output:
Bernstein hash of POTS with range 13 is: 6
Bernstein hash of the reverse of POTS - STOP - with range 13, is: 7
Compile and Test
A complete Makefile and a main.cpp file containing one simple test has been provided for
you. To compile and run, run:
make
./main
Upload Solution
Drop files here or click to upload.
Only the files listed below will be accepted—others will be ignored.
POTD 41
Total points: 0/1
Score:
0%
Question
Value:
History:
Awarded points:
Report an error in this question
1
0/1
Previous question
Next question
Files
Hash.cpp
not uploaded
Hash.h
not uploaded
Save & Grade
Save only
