\documentclass[10pt,letterpaper]{article}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{multirow}
\usepackage{listings}
\title{
        CS240 HW \#4
}
\author{}
\date{}

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

\begin{document}
\begin{center}
\Large{ CS240 HW \#4 }
\end{center}

Answers to the following exercises should be prepared in a text editor
and submitted through Canvas as a .pdf file. Equations should be
properly formatted using equation editing software.  Don't forget to
include your name and an honor code statement.

\begin{enumerate}


\item Write the value of the following recurrences for $n$ = 0 to 4. (3pts)
\begin{itemize}
\item  
  $T(0) = 1$\\
  $T(n) = 5  T(n - 1)$ \\
  
\item
  $T(0) = 2$\\
  $T(1) = 2$ \\
  $T(n) = 4 T(n - 2) + 2$\\
  
\item
  $T(0) = 0$ \\
  $T(n) = T(n - 1) + n^2 + n$ \\
  
\end{itemize}


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

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

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


\pagebreak

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

\begin{lstlisting}[style=basic,language=Python,frame=single]
def fun1(n):
    if n == 0:
        print(n)
    else:
        for i in range(3):
            print(i, n)
        fun1(n - 1)

def fun2(n):
    if n == 0:
        print(n)
    else:
        print(n)
        for i in range(4):
            fun2(n - 1)
\end{lstlisting}


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

Hints: 

\begin{itemize}
\item For the second recurrence, it may be useful to recall the
  general formula for a geometric sum:

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

It follows from this that:

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

\item Since we are counting print statements, you should be able to
  double check your solution by executing the code and counting the
  number of lines printed.

\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}


\end{enumerate}

\end{document}
