Guide

User Manual:

Open the PDF directly: View PDF PDF.
Page Count: 2

DownloadGuide
Open PDF In BrowserView PDF
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):

POTD 41
Total points:
Score:

0%

Question
Value:

sh potd-q41.sh

Your files for this problem will be in the potd-q41 directory.

1

History:
Awarded points:

The Problem

0/1

0/1

Report an error in this question

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.

Previous question
Next question

Files
Hash.cpp
not uploaded

Hash.h
not uploaded

Save & Grade

Save only
Source Exif Data: 
File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
Linearized                      : No
Page Count                      : 2
PDF Version                     : 1.4
Title                           : PrairieLearn
Author                          : DYT
Subject                         : 
Producer                        : Mac OS X 10.12.6 Quartz PDFContext
Creator                         : Safari
Create Date                     : 2019:04:01 02:16:32Z
Modify Date                     : 2019:04:01 02:16:32Z
Apple Keywords                  :
EXIF Metadata provided by EXIF.tools

Navigation menu