\documentclass[12pt]{article}
\usepackage[letterpaper, margin=0.5in]{geometry}
\geometry{letterpaper}
\usepackage[parfill]{parskip}
\usepackage{framed}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{qtree}
\usepackage{makecell}
\usepackage{lmodern}
\renewcommand*\familydefault{\sfdefault}
\usepackage{tikz}
\usetikzlibrary{matrix}
\usepackage{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\DeclarePairedDelimiter\abs{\lvert}{\rvert}%
\DeclarePairedDelimiter\norm{\lVert}{\rVert}%
% \abs & \norm resizes brackets, starred version doesn’t
\makeatletter
\let\oldabs\abs
\def\abs{\@ifstar{\oldabs}{\oldabs*}}
%
\let\oldnorm\norm
\def\norm{\@ifstar{\oldnorm}{\oldnorm*}}
\makeatother
\newcommand\graytag[1]{\text{\textsl{\color{gray}{#1}}}}
\newcommand\tab[1][0.4cm]{\hspace*{#1}}
\newcommand\imp{\rightarrow}
\newcommand\thfr{\tab \therefore \tab}
\newcommand\sameas{\tab \equiv \tab}
\renewcommand{\arraystretch}{1.5}
\graphicspath{{../pdf/}{D:\Users\elizabethhoward\Documents\Courses\Current\csc263\extras\wk-2-binomial-heaps\figures}}
\title{CSC263 – Week 5, Lecture 1}
\author{Cristyn Howard}
\date{Monday, February 5, 2018}
\begin{document}
\maketitle
\texttt{Q: A webserver needs to reference a large list of blacklisted websites. The entire list cannot be stored in main memory, because it is too large. How can we store it? \\ \\
A: In a BLOOM FILTER}
\subsection*{Bloom Filters}
\begin{itemize}
\item probablistic (i.e. approximate) dictionary that stores $F_S:$ a summary/fingerprint of a dynamic set S
\begin{center}\graytag{
\begin{tabular}{r@{$\:\: : \:\:$}l}
BF$[0, …, m-1]$ & array of $m$ bits, initialized to $0$. \\
$\{h_1, …, h_t \}$ & set of $t