\documentclass{article}
\usepackage{amsthm, amssymb, amsmath,verbatim}
\usepackage[margin=1in]{geometry}
\usepackage{enumerate}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newtheorem*{claim}{Claim}
\newtheorem{ques}{Question}
\title{CSE 101 Homework 0}
\date{Winter 2021}
\begin{document}
\maketitle
This homework is due on gradescope Friday January 8th at 11:59pm pacific time. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in \LaTeX is recommend though not required.
\begin{ques}[Program Runtimes, 20 points]
Consider the following programs:
\begin{verbatim}
Alg1(n):
For i = 1 to n
j = 1
while j < n
j = j+1
\end{verbatim}
\begin{verbatim}
Alg2(n):
For i = 1 to n
j = 1
while j < n
j = j+i
\end{verbatim}
For each of these algorithms, compute the asymptotic runtime in the form $\Theta(-)$.
\end{ques}
\begin{ques}[Big-$O$ Computations, 20 points]
Sort the functions below in terms of their asymptotic growth rates. Which of these functions have polynomial growth rates? Remember to justify your answers.
\begin{itemize}
\item $a(n) = n+n^{1/2}+n^{1/3}+\ldots+ n^{1/n}$
\item $b(n) = 3^{\lceil log_2(n) \rceil}$
\item $c(n) = n^2(2+\cos(n))$
\item $d(n) = n^{100} 2^{n/2}$
\item $e(n) = 2^n$
\end{itemize}
\end{ques}
\begin{ques}[Walks and Paths, 30 points]
In a graph $G$ we say that there is a \emph{walk} from vertex $u$ to another vertex $w$ if there is a sequence of vertices $u=v_0,v_1,\ldots,v_n=w$ so that $(v_i,v_{i+1})$ is an edge of $G$ for each $0\leq i < n$. Prove that if there is a walk from $u$ to $w$ there is a walk where all of the vertices $v_i$ are distinct. Hint: if two are the same show how you can use this to construct a shorter walk.
\end{ques}
\begin{ques}[Recurrence Relations, 30 points]
Consider the recurrence relation
$$
T(1) = 1, \ \ \ T(n) = 2T(\lfloor n/2\rfloor) + n.
$$
\begin{enumerate}[(a)]
\item What is the exact value of $T(2^n)$? [10 points]
\item Give a $\Theta$ expression for $T(n)$. Hint: compare its value to that at nearby powers of $2$. [10 points]
\item Consider the following purported proof that $T(n)=O(n)$ by induction:
\noindent If $n=1$, then $T(1)=1=O(1)$.
\noindent If $T(m)=O(m)$ for $m < n$, then
$$
T(n) =2T(\lfloor n/2\rfloor) + n = O(n) + O(n) = O(n).
$$
\noindent Thus, $T(n)=O(n)$.
\smallskip \noindent What is wrong with this proof? Hint: consider the implied constants in the big-$O$s. [10 points]
\end{enumerate}
\end{ques}
\begin{ques}[Extra credit, 1 point]
Approximately how much time did you spend working on this homework?
\end{ques}
\end{document}