%
% 6.006 homework template
%
% NOTE:
% Be sure to define your name with the \name command
% Be sure to use the \answer command for each of your answers 
%   (first argument: problem name
%   second argument: collaborators (write 'none' if you solved it alone))
\documentclass[12pt]{article}

\newcommand{\name}{YOUR NAME HERE}
\newcommand{\problemset}{ Problem Set 2, Part B }

%\pagestyle{headings}
\usepackage[dvips]{graphics,color}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{enumerate}
\setlength{\parskip}{1pc}
\setlength{\parindent}{0pt}
\setlength{\topmargin}{-3pc}
\setlength{\textheight}{9.5in}
\setlength{\oddsidemargin}{0pc}
\setlength{\evensidemargin}{0pc}
\setlength{\textwidth}{6.5in}

\newcommand{\answer}[2]{
\newpage
\noindent
\framebox{
	\vbox{
		6.006 Homework \hfill {\bf \problemset}
		\hfill \# #2 \\ 
		\name \hfill \today 
	}
}
\bigskip

}


\begin{document}

\answer{1 --  Augmented BST: \texttt{max-gap} }
{INSERT COLLABORATORS HERE}
%Write `none' if solved alone.



\begin{enumerate}[(a)]
	\item DESCRIBE BST AUGMENTATION HERE
	
		
	\item \texttt{max-gap}
	
		DESCRIBE METHOD
		%% you may use text to describe your method
		%% or write in psuedocode
	
		The running time of \texttt{max-gap} is
			\begin{equation*} 
				\Theta(\text{INSERT RUNNING TIME HERE})
			\end{equation*}
		because INSERT EXPLANATION HERE
	
	
	\item \texttt{insert}
		
		DESCRIBE METHOD
		%% you may use text to describe your method
		%% or write in psuedocode
			
		The running time of \texttt{insert} is
			\begin{equation*} 
				\Theta(\text{INSERT RUNNING TIME HERE})
			\end{equation*}
		because INSERT EXPLANATION HERE
	

	\item \textit{optional:}
		\begin{enumerate}[(i)]
			\item ANSWER
			\item ANSWER
		\end{enumerate}
	
\end{enumerate}



\answer{2 -- chain length in hashing}
{INSERT COLLABORATORS HERE}
%Write `none' if solved alone.

\begin{enumerate}[(a)]
	\item
		ANSWER : why $ Q_k = {n\choose{k}}  (1-\frac{1}{m})^{n-k}  (\frac{1}{m})^k $
		
		%% $ \frac{n!}{k! (n-k)!} $
	\item
		ANSWER : explain $ Q_k(m,n) \approx P_k(\frac{n}{m}) $
		
		%% $ P_k(\lambda) = \frac{\lambda^k e^{-k}}{k!}$
	 	%% $ \lim_{n \to \infty}(1+\frac{x}{n})^n = e^x$ 
	 	%% remember $ \sqrt{\frac{n}{n+k} \approx 1} $
	\item
		ANSWER : estimate expected # of empty slots
	\item
		ANSWER : show $ \hat{k} = \Theta(\lg{n} / \lg{\lg{n}}) $
	\item
		ANSWER : do your results match the graphs?
\end{enumerate}

\end{document}