\documentclass[12pt]{article}

\usepackage[T1]{fontenc} 
\usepackage{fullpage,amsmath,amsfonts}

\begin{document}

\title{Algorithms and Data Structures}
\author{Summer Semester 2022}
\date{For discussion on Tuesday, May 24, 2022}
\maketitle

\begin{enumerate}
\item Consider the \verb+binary_sum+ implementation from GTG
Section~4.4.2 discussed in class.  Prove the claim that when $n=2^k$
for some positive integer $k$, then  \verb+binary_sum(n)+ invokes
exactly $2n-1$ function calls.

\item Type the following into your Python console:
\begin{verbatim}
  a=[1,2]
  b=a
  a[1]=3
  b
\end{verbatim}
What output do you expect?  What output do you get?  Explain!

\item Type the following in your Python console:
\begin{verbatim}
  a=1
  b=a
  a=3
  b
\end{verbatim}
What output do you expect?  What output do you get?  Explain!

\item Write an piece of code which demonstrates experimentally that
Python's \texttt{append}-method for lists is an $O(1)$ operation on
average.  I.e., show that $n$ appends execute in $O(n)$-time when $n$
is large.

For time keeping and plotting, you can reuse much of the solution code
to Exercise~1 on the first exercise sheet.


\end{enumerate}
\end{document}
