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

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

\begin{document}
\newcommand{\bq}{\item \begin{samepage} }
  \newcommand{\eq}{\end{samepage}}
%\maketitle
\begin{center}
\Large{ CS240 HW \#6 }
\end{center}

Answers to the following exercises should be prepared in a text editor and submitted through blackboard 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}
\bq Complete the Midterm Survey on the course Blackboard page. (10pts)
\eq



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

  
\end{itemize}
\eq


\bq Write the value of the following recurrences for $n$ = 1, 2, 4 and 8. (6pts)
\begin{itemize}
\item
    $T(1) = 4$ \\
    $T(n) = 3 \times T(n/2)$ \\
\item
    $T(1) = 2$ \\
    $T(n) = 4 + T(n/2)$ \\

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


\end{itemize}
\eq

\pagebreak

\bq Write recurrence relations that describe the number of times that \verb+basicOp+ is called by each of the following recursive functions. (10pts)
\begin{lstlisting}[style=basic,language=Python,frame=single]
def fun1(n):
    if n == 0:
        return 0
    else:
        sum = 0
        for i in range(n):
            sum += basicOp() + basicOp()
        return fun1(n - 1) + sum

def fun2(n):
    if n == 0:
        return basicOp()
    else:
        return fun2(n - 1) + fun2(n - 1) + basicOp()
\end{lstlisting}

\eq

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

For the second recurrence, it will be useful to know that:

 $ \displaystyle \sum_{j = 0}^n 2^j = 2^{n+1} - 1$.

  \eq


\end{enumerate}

\end{document}
