\documentclass[11pt]{article}

\newcommand{\yourname}{}
\newcommand{\yourcollaborators}{}

\def\comments{0}

%format and packages

%\usepackage{algorithm, algorithmic}
\usepackage{algpseudocode}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{enumerate}
\usepackage{enumitem}
\usepackage{framed}
\usepackage{verbatim}
\usepackage[margin=1.0in]{geometry}
\usepackage{microtype}
\usepackage{kpfonts}
\usepackage{palatino}
	\DeclareMathAlphabet{\mathtt}{OT1}{cmtt}{m}{n}
	\SetMathAlphabet{\mathtt}{bold}{OT1}{cmtt}{bx}{n}
	\DeclareMathAlphabet{\mathsf}{OT1}{cmss}{m}{n}
	\SetMathAlphabet{\mathsf}{bold}{OT1}{cmss}{bx}{n}
	\renewcommand*\ttdefault{cmtt}
	\renewcommand*\sfdefault{cmss}
	\renewcommand{\baselinestretch}{1.06}
\usepackage[usenames,dvipsnames]{xcolor}
\definecolor{DarkGreen}{rgb}{0.15,0.5,0.15}
\definecolor{DarkRed}{rgb}{0.6,0.2,0.2}
\definecolor{DarkBlue}{rgb}{0.2,0.2,0.6}
\definecolor{DarkPurple}{rgb}{0.4,0.2,0.4}
\usepackage[pdftex]{hyperref}
\hypersetup{
	linktocpage=true,
	colorlinks=true,				% false: boxed links; true: colored links
	linkcolor=DarkBlue,		% color of internal links
	citecolor=DarkBlue,	% color of links to bibliography
	urlcolor=DarkBlue,		% color of external links
}

\usepackage[boxruled,vlined,nofillcomment]{algorithm2e}
	\SetKwProg{Fn}{Function}{\string:}{}
	\SetKwFor{While}{While}{}{}
	\SetKwFor{For}{For}{}{}
	\SetKwIF{If}{ElseIf}{Else}{If}{:}{ElseIf}{Else}{:}
	\SetKw{Return}{Return}
	

%enclosure macros
\newcommand{\paren}[1]{\ensuremath{\left( {#1} \right)}}
\newcommand{\bracket}[1]{\ensuremath{\left\{ {#1} \right\}}}
\renewcommand{\sb}[1]{\ensuremath{\left[ {#1} \right\]}}
\newcommand{\ab}[1]{\ensuremath{\left\langle {#1} \right\rangle}}

%probability macros
\newcommand{\ex}[2]{{\ifx&#1& \mathbb{E} \else \underset{#1}{\mathbb{E}} \fi \left[#2\right]}}
\newcommand{\pr}[2]{{\ifx&#1& \mathbb{P} \else \underset{#1}{\mathbb{P}} \fi \left[#2\right]}}
\newcommand{\var}[2]{{\ifx&#1& \mathrm{Var} \else \underset{#1}{\mathrm{Var}} \fi \left[#2\right]}}

%useful CS macros
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\zo}{\{0,1\}}
\newcommand{\pmo}{\{\pm1\}}
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\card}[1]{\left| #1 \right|}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\negl}{\mathrm{negl}}
\newcommand{\eps}{\varepsilon}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\newcommand{\eqand}{\qquad \textrm{and} \qquad}
\newcommand{\ind}[1]{\mathbb{I}\{#1\}}
\newcommand{\sslash}{\ensuremath{\mathbin{/\mkern-3mu/}}}

%mathbb
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
%mathcal
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}

%theorem macros
\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{fact}[thm]{Fact}
\newtheorem{clm}[thm]{Claim}
\newtheorem{rem}[thm]{Remark}
\newtheorem{coro}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}[thm]{Conjecture}

\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}


\newcommand{\instructor}{Virgil Pavlu}
\newcommand{\hwnum}{1}
%\newcommand{\hwdue}{Wednesday, January 27 at 11:59pm via \href{https://gradescope.com/courses/229309}{Gradescope}}

\newtheorem{prob}{}
\newtheorem{sol}{Solution}

\definecolor{cit}{rgb}{0.05,0.2,0.45} 
\newcommand{\solution}{\medskip\noindent{\color{DarkBlue}\textbf{Solution:}}}


\begin{document}
{\Large 
\begin{center}{CS5800: Algorithms} ---  \instructor \end{center}}
{\large
\vspace{10pt}
\noindent Homework~\hwnum \vspace{2pt}%\\
%Due :~\hwdue
}

\bigskip
{\large \noindent Name: \yourname }

{\large \noindent Collaborators: \yourcollaborators}

\vspace{15pt}

{\large \noindent Instructions:}

\begin{itemize}

\item Make sure to put your name on the first page.  If you are using the \LaTeX~template we provided, then you can make sure it appears by filling in the \texttt{yourname} command.

\item Please review the grading policy outlined in the course information page.

\item You must also write down with whom you worked on the assignment.  If this changes from problem to problem, then you should write down this information separately with each problem.

\item Problem numbers (like Exercise 3.2-1) are corresponding to CLRS $4^{th}$ edition.  While the  $3^{th}$ edition  has  similar  problems  with  similar  numbers,  the  actual  exercises  and their solutions are different, so make sure you are using the $4^{th}$ edition.

\end{itemize}

\newpage

\begin{prob} \textbf{(20 points)}
\end{prob}

Two linked lists (simple link, not double link) heads are given: headA, and head B;it is also given that the two lists intersect,  thus after the intersection they have the same elements to the end.  Find the first common element, without modifying the lists elements or using additional datastructures.

\begin{enumerate}[label=(\alph*)]

\item  A  linear  algorithm  is  discussed  in  the  lecture:  count  the  lists  first,  then  use  the count  difference  as  an  offset  in  the  longer  list,  before  traversing  the  lists  together. Write a formal pseudocode (the pseudocode in the lecture is vague), using “next” as a method/pointer to advance to the next element in a list.

\solution

\item Write the actual code in a programming language (C/C++, Java, Python etc) of your  choice  and  run  it  on  a  made-up  test  pair  of  two  lists.   A  good  idea  is  to  use pointers to represent the list linkage.

\solution
\end{enumerate}

\begin{prob} \textbf{(10 points)}
\end{prob}

Let $f(n)$ and $g(n)$ be asymptotically nonnegative functions. Using the basic definition of $\theta$-notation, prove that max($f(n), g(n))=\theta(f(n)+g(n))$.

\solution

\begin{prob} \textbf{(5 points)}
\end{prob}

Is $2^{n+1}=O(2^n)$? Is $2^{2n}=O(2^n)$?

\solution

\begin{prob} \textbf{(15 points)}
\end{prob}

Rank  the  following  functions  in  terms  of  asymptotic  growth.   In  other  words, find an arrangement of the functions $f_1, f_2, . . .$ such that for all i, $f_i = \Omega(f_{i+1})$.
\begin{center}
\begin{tabular}{ccccccc}
$\sqrt{n}\ln n$ & $\ln \ln n^2$ & $2^{\ln^2 n}$ & $n!$ & $n^{0.001}$ & $2^{2\ln n}$  & $(\ln n)!$ \\
\end{tabular}
\end{center}
\solution

\begin{prob} \textbf{(40 points)} Problem 4-1
\end{prob}

Give asymptotic upper and lower bounds for $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for $n \leq 2$. Make your bounds as tight as possible, and justify your answers.

\begin{enumerate}[label=(\alph*)]

\item $T(n) = 2T(n/2) + n^3$

\solution

\item $T(n) = T(8n/11) + n$

\solution

\item $T(n) = 16T(n/4) + n^2$

\solution

\item $T(n) = 4T(n/2) + n^2\lg n$

\solution

\item $T(n) = 8T(n/3) + n^2$

\solution

\item $T(n) = 7T(n/2) + n^2\lg n$

\solution

\item $T(n) = 2T(n/4) + \sqrt{n}$

\solution

\item $T(n) = T(n-2) + n^2$

\solution
\end{enumerate}

\begin{prob} \textbf{(5 points)} Problem 4-3 from (a) to (c) 
\end{prob}

\begin{enumerate}[label=(\alph*)]
  \item Deﬁne $m = \lg n$ and $S(m) = T(2^m)$. Rewrite recurrence $T(n) = 2T(\sqrt{n}) + \theta(\lg n)$ in terms of $m$ and $S(m)$. 

  \solution

\item Solve your recurrence for $S(m)$. 

  \solution

\item Use your solution for $S(m)$ to conclude that $T(n) = \theta(\lg n \lg \lg n)$.

  \solution

\end{enumerate}
\begin{prob} \textbf{(30 points)} Problem 4-4 from (a) to (f) 
\end{prob}

Give asymptotic upper and lower bounds for $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for sufficiently small $n$. Make your bounds as tight as possible, and justify your answers.

\begin{enumerate}[label=(\alph*)]

\item $T(n) = 5T(n/3) + n\lg n$

\solution

\item $T(n) = 3T(n/3) + n / \lg n$

\solution

\item $T(n) = 8T(n/2) + n^3 \sqrt{n}$

\solution

\item $T(n) = 2T(n/2 - 2) + n/2$

\solution

\item $T(n) = 2T(n/2) + n / \lg n$

\solution

\item $T(n) = T(n/2) + T(n/4) + T(n/8) + n$

\solution
\end{enumerate}
\end{document}
