% Created 2022-04-30 Sat 17:49
% Intended LaTeX compiler: pdflatex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\input{../preamble}
\author{Instructor: Mehmet Emre}
\date{CS 32 Spring '22}
\title{Homework 9: Hashing}
\hypersetup{
pdfauthor={Instructor: Mehmet Emre},
pdftitle={Homework 9: Hashing},
pdfkeywords={},
pdfsubject={},
pdfcreator={Emacs 28.1 (Org mode 9.5.2)},
pdflang={English}}
\begin{document}
\maketitle
\textbf{Due: 5/11 12:30pm} \\
\vspace{1em}
\textbf{Name \& Perm \#:} \\
\textbf{Homework buddy (leave blank if you worked alone):}
\textbf{Reading:} DS 12.2
\section{}
\label{sec:org07b2aca}
From DS (12.2): There is a technique known as "double hashing".
\begin{enumerate}
\item (4 pts) What is the problem that double hashing is designed to solve?
\textbf{Briefly explain.}
\vspace{8em}
\item (4 pts) How does double hashing solve that problem? \textbf{Briefly explain.}
\vspace{8em}
\end{enumerate}
\section{}
\label{sec:orgbd9e3a4}
From DS 12.2: The abstract data type (ADT) known as a "dictionary" provides a
way to look up keys and find values. We define these abstract operations for
the ADT:
\begin{description}
\item[{lookup(key)}] returns either value, or an indication that the value is not
present
\item[{remove(key)}] removes the item with that key (if it exists)
\item[{insert(key,value)}] inserts the new key, and the value (or replaces the
value if it is already present)
\end{description}
We could implement a dictionary by having an array of (key,value) pairs,
sorted by key. We could use binary search for lookup. We'd have to figure out a
way to put new values into the sorted list, and remove values. Or we could use
hashing, as described in DS 12.2
(question continues on the next page)
\begin{enumerate}
\item (2 pts) If we use binary search on a sorted array, what is the worst case
time for lookup(key) in terms of big-O? (No explanation needed; just state
the answer)
\vspace{4em}
\item (4 pts) If we use binary search on a sorted array, what is the worst case
big-O time for remove(key)? This time, \emph{briefly} explain your
answer.
\vspace{8em}
\item (2 pts) If we use hash tables instead, what is the worst case big-O time
for lookup(key)? Just state it.
\vspace{4em}
\item (2 pts) Is the worst case for lookup(key) for hash tables better or worse
than the binary search approach?
\vspace{4em}
\item (2 pts) If we use hash tables instead, what is the average (expected) case
big-O time for lookup(key) assuming no collisions? Just state it.
\vspace{4em}
\item (2 pts) Is the average (expected) case for lookup(key) for hash tables
better or worse than the binary search approach?
\end{enumerate}
\end{document}