\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}

\addtolength{\topmargin}{-.875in}
\addtolength{\oddsidemargin}{-.8in}
\addtolength{\textwidth}{1.6in}
\addtolength{\textheight}{1.75in}


\newcommand{\solution}[1]{
\begin{quote}\color{red}Solution:\quad 
\color{black}\end{quote}
}
\newcommand{\Ber}{\hbox{Ber}}
\newcommand{\p}[1]{\mathbb{P}(#1)}
\newcommand{\e}[1]{\mathbb{E}(#1)}
\newcommand{\Po}[1]{\hbox{Po}(#1)}
\newcommand{\var}[1]{\hbox{Var}(#1)}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}

\begin{document}
\title{Math 301: Homework 6}
\author{Mary Radcliffe}
\date{due 19 Oct 2015}
\maketitle

Complete the following problems. Fully justify each response.

\begin{enumerate}

\item Suppose you have random variables $X_1, X_2, \dots, X_n$, each of which is drawn independently, such that $\p{X_i=0}=\p{X_i=1}=\p{X_i=2}=\frac{1}{3}$ for all $i$. Let $X=\sum X_i$. Derive a Chernoff-type bound for $\p{|X-\e{X}|>a}$. 

\item Let $G=G(n, p)$ be a random graph such that each edge is included independently and with probability $p$, such that $p$ is a constant. Note that the expected degree of each vertex is $np$. Let $\delta$ be the minimum degree in $G$. Prove that for any constant $c>0$, 
\[\lim_{n\to\infty} \p{\delta<np-c\sqrt{n\log n}} = 0.\]

That is to say, the probability that $\delta > np-c\sqrt{n\log n}=np(1-o(1))$ tends to 1 as $n\to \infty$.

\item We here consider the runtime of Quicksort, a popular sorting algorithm for an array of distinct numbers. Given an array $A$, having $n$ entries, here is the algorithm.
\begin{enumerate}
\item[1.] Choose an element of $A$ at random. Call this element the pivot.
\item[2.] By comparing elements of $A$ to the pivot, divide $A$ into two subarrays, $A_{less}$ and $A_{more}$, according to whether the elements of $A$ are less or more than the pivot.
\item[3.] Recursively sort $A_{less}$ and $A_{more}$ using the same algorithm.
\end{enumerate}

We shall say that the runtime of Quicksort is $X$, where $X$ is the number of times we must compare two elements. Hence, when we choose the first pivot, we must make $n-1$ comparisons. 

\begin{enumerate}
\item Show that the worst case runtime of Quicksort is on order $n^2$.
\item Show that $\p{X > 8n\log n}\leq \frac{1}{n^2}$. 
\end{enumerate}

Hence, although the worst case runtime is quadratic, with high probability, Quicksort runs in subquadratic time.




\end{enumerate}

\end{document}