%---------
% place your email id between the braces so that your homework has a name
\def\yourname{}
% -----------------------------------------------------
\def\duedate{8/4/2025}
\def\duelocation{via \href{https://www.gradescope.com/courses/1007022}{Gradescope}}
\def\hnumber{5}
\def\prof{Konstantinos Ameranis}
\def\course{\href{https://canvas.uchicago.edu/courses/64693}{CMSC 14300 - Summer 2025}}
%-------------------------------------

\documentclass[10pt]{article}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[osf]{mathpazo}
\usepackage{amsmath,amsfonts,graphicx}
\usepackage{latexsym}
\usepackage{subfig}
\usepackage{algpseudocode}
\usepackage[shortlabels]{enumitem}
\usepackage{algorithm}
\usepackage{listings}
%\usepackage[top=1in,bottom=1.4in,left=1.5in,right=1.5in,centering]{geometry}
\usepackage{fullpage}
\usepackage{color}
\usepackage{tikz}
\definecolor{mdb}{rgb}{0.3,0.02,0.02}
\definecolor{cit}{rgb}{0.05,0.2,0.45}
%\pagestyle{myheadings}
\markboth{\yourname}{\yourname}

\thispagestyle{empty}

\newenvironment{proof}{\par\noindent{\it Proof.}\hspace*{1em}}{$\Box$\bigskip}
\newcommand{\qed}{$\Box$}
\newcommand{\alg}[1]{\mathsf{#1}}
\newcommand{\handout}{
   \renewcommand{\thepage}{H\hnumber-\arabic{page}}
   \noindent
   \begin{center}
      \vbox{
    \hbox to \columnwidth {\sc{\course} --- \prof \hfill}
    \vspace{-2mm}
    \hbox to \columnwidth {\sc due \MakeLowercase{\duedate} \duelocation\hfill {\Huge\color{mdb}H\hnumber.\yourname}}
      }
   \end{center}
   \vspace*{2mm}
}
\newcommand{\solution}[1]{
\vspace{2mm}

\noindent Collaborators:

\vspace{5mm}

\medskip\noindent{\color{cit}\textbf{Solution:} #1}}

\newcommand{\bit}[1]{\{0,1\}^{ #1 }}
\newcommand{\extraspace}{\medskip\noindent{\color{cit} Extra space for your solution}\newpage}
%\dontprintsemicolon
%\linesnumbered=
\newtheorem{problem}{\sc\color{cit}Problem}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}

\newcommand\BigCircle[1][2.5]{\tikz[baseline=-#1]{\draw[thick](0,0)circle[radius=#1mm];}}

\begin{document}
\handout

\begin{problem}[Bad Hash functions]

Catherine (our grader) tried suggesting some alternative hash functions that should help with performance.
The first one is $f_1(k) = 1$, which she claims is better since it is super fast. 

\begin{enumerate}[(a)]
    \item (2 points) Using $f_1$ turns the hash table into which known data structure?

    \vfill

\item (2 points) The second one she suggested was
\begin{verbatim}
uint64_t string_hash(void *key) {
    char *str = key;
    uint64_t hash = 0;
    int c;

    while ((c = *str++))      
        hash = c + (hash << 6)

    return hash;
}
\end{verbatim}

This one is a variation on the sdbm, but performs a single addition instead of three.

Given the string "information" construct an English word {\tt s} such that $f_2(\text{"information"}) == f_2(s)$. Is there a simple way to construct a collision for any input?

    \vfill

\item (2 points) Another way that Catherine is trying to help is by trying to make sure the hash function is truly random. Her proposal is $f_3(k) = \text{hash}(k) ^ randint(2**64)$.\\
Why is this not a valid hash function?

\vfill
\end{enumerate}

\end{problem}
\newpage
\begin{problem}[Timing comparisons (4 points)]
Compare the running time of {\tt groups} using a hash table and a binary search
tree, how long does it take to group the largest input in each case?\\
Try: 
\begin{verbatim}
/usr/bin/time ./groups -t tests/large.txt > /dev/null
/usr/bin/time ./groups -m tests/large.txt > /dev/null
\end{verbatim}
There are primarily two parts in the {\tt groups} program:
\begin{enumerate}
    \item insert all lines into the dictionary, and
    \item visit all key-value pairs in sorted order
\end{enumerate}
Which implementation is better at accomplishing Step 1? Which implementation is
better at Step 2?

\vfill
\end{problem}

\begin{problem}
How many hours did you spend for this assignment?
\vfill 
\end{problem}

\begin{problem}
What is the most difficult aspect of this assignment, if any?
\vfill
\end{problem}

\begin{problem}
Document your collaboration here.
\vfill    
\end{problem}
\end{document}                                                                                                                                                                                                

