\documentclass[10pt,letterpaper]{article}

\usepackage[letterpaper, left=1.25in, right=1.25in]{geometry}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{multirow}
\usepackage{listings}
\title{
        CS240 HW \#2
}
\author{YOUR NAME HERE}
\date{}

\lstdefinestyle{basic}{
    basicstyle=\small\ttfamily,%
    frame=single,
    showstringspaces=false,%
}

\begin{document}
\maketitle

Answers to the following exercises should be submitted through Canvas
as a .pdf file.  Don't forget to include your name and an honor code
statement. \\

Hints for solving recurrences (these may or may not apply to the
problems below):

\begin{itemize}
\item Two sums often show up in solving these recurrences. One is the geometric sum:

 \[\sum_{j = 0}^n r^j = \frac{1 - r^{n+1}}{1 - r}.\]

From which it follows that:

\[ \sum_{j = 0}^{n-1} r^j = \frac{1 - r^{n}}{1 - r}.\]

A second is the arithmetic sum: 

$$\sum_{j=0}^n j = \frac{n(n+1)}{2}$$

From which it follows that: 

$$\sum_{j=0}^{n-1} = \frac{(n-1)n}{2}.$$

\item Remember that $a^{\log_2 b} = b^{\log_2 a}$. This helps, for instance, with simplifying statements like $4^{\log_2 n} = n^{\log_2 4} = n^2$. 

\item Wolfram alpha (www.wolframalpha.com) is able to solve
  recurrences like these automatically.  Feel free to use this tool to
  check your answers.  Your score will be based on showing the steps
  required to solve the recurrences using backward substitution.
\end{itemize}

\newpage

\begin{enumerate}

\item Write the value of the following recurrences for $n$ = 0 to 4. (3pts)
\begin{enumerate}

\item  
  $T(0) = 1$\\
  $T(n) = 2  T(n - 1)$ \\

\item
  $T(0) = 1$\\
  $T(1) = 2$ \\
  $T(n) = 2n + 2 T(n - 2) + T(n - 1) + 1$\\
  
\item
  $T(0) = 2$ \\
  $T(1) = 2$ \\
  $T(n) = 4n^2 + T(n - 2)$ \\
  
\end{enumerate}


\item Write the value of the following recurrences for $n$ = 1, 2, 4
  and 8. (3pts)

\begin{enumerate}
\item
  $T(1) = 2$ \\
  $T(n) = 4 T(n/2)$ \\
\item
  $T(1) = 8$ \\
  $T(n) = n + T(n/2)$ \\

\item
  $T(1) = 0$ \\
  $T(n) = 3n^2 + n + T(n/2)$ \\
\end{enumerate}

\item Find a closed form solution for each of the following
  recurrences (for b you may assume $n$ is a power of $4$). (4 pts)

\begin{enumerate}
\item 
  $T(0) = 10$ \\
  $T(n) = 1 + 10 T(n - 1)$
\item 
  $T(1) = 3$ \\
  $T(n) = n + 4 T (n / 4)$
\end{enumerate}


\pagebreak

\item Write recurrence relations that describe the number of times
  that \verb+System.out.println+ is called by each of the following recursive
  functions. (4pts)

\begin{lstlisting}[style=basic,language=Java,frame=single]
public static void fun1(int n) {
    if (n == 0) {
        System.out.println("fun1 line");
    } else {
        for (int i = 0; i < 4; i++) {
          System.out.println("fun1 line");
        }
        fun1(n - 1);
    }
}

public static void fun2(int n) {
    if (n == 0) {
        System.out.println("fun2 line");
    } else {
        fun2(n - 1);
        fun2(n - 1);
        for (int i = 0; i < 8; i++) {
            System.out.println("fun2 line");
        }
    }
}

\end{lstlisting}

Another hint: 
\begin{itemize}
\item Since we are counting println statements, you should be able to
  double check your solution by executing the code and counting the
  number of lines printed.
\end{itemize}

\item Use the method of backward substitution (or the tree method) to
  solve the recurrences from the previous exercise. Show your
  work. (4pts)\\



\end{enumerate}

\section*{Helpful {\LaTeX} Hints}

Thanks to Dr. Kirkpatrick...

\begin{itemize}  % itemize is a bullet-point list; use enumerate for numbered
\setlength{\itemsep}{0pt} % this can adjust the spacing between lines in the list
\item Use  $\frac{1}{2}$ instead of $1/2$.
\item Use $\log n$ instead of $log n$ or $log~n$.
\item Compare $n^{123}$ with $n^123$.
\item Compare $\sqrt{n + 3}$ with $\sqrt n + 3$.
\item Use $\Theta(n)$ or $\Omega(n)$ as needed. Note that parentheses don't
      have a special meaning in math mode when used like this.
\item Compare $\lim_{n\to\infty} \frac{n^2}{n^3}$ with
      $\displaystyle\lim_{n\to\infty} \frac{n^2}{n^3}$ .
\item Math mode has a lot of built-in equality symbols, such as $<, >, \le, \ge, \ne,
      \in, \subset, \subseteq, \equiv$. Thes can be negated by adding \textbackslash{}not
      before them, such as $\not\in, \not\subset, \not\equiv$.
\item You can make things \textbf{bold} or {\bf bold}. You can also switch
      to \texttt{monospace} {\tt fonts}. Use \textbackslash{}\{emph\} to
      make things \emph{italic}. You can also switch to {\sc Small Caps}
      \textsc{Font} or \textsf{sans-serif} {\sf font}.
\end{itemize}

\subsection*{Paragraphs}

If you want to create a new paragraph, it's really easy to do. Just put a blank
line between two paragraphs.

The new paragraph will automatically be indented and you can continue writing.
Sometimes, you want more than that, and you want to force an extra blank line.
There are a few ways. One is to add \textbackslash{}\textbackslash{} at the
end, like here: \\

The new paragraph will start with a blank line in between. You can adjust that
spacing with a measurement in brackets, such as using what's at the end of
this paragraph to add a 1-inch space. \\ [1in]

Now we have even more space in between. Another helpful spacing tool is the
tilde character (\~{}). You ~ can ~~ add ~~~~~ spaces ~~~~~~~~~~~ between words
or c~h~a~r~a~c~t~e~r~s. You can also use this in math mode if you want to make
a difference between $3n^2$ and $3~n^2$.

\end{document}
