\documentclass[12pt]{article}

\usepackage{fullpage,amsmath,amsfonts,hyperref}

\begin{document}

\title{Algorithms and Data Structures}
\author{Summer Semester 2025}
\date{For discussion on Wednesday, May 21}
\maketitle

\begin{enumerate}

\item (GTG Exercise R-4.8) Isabel has an interesting way of summing up
the values in a sequence $A$ of $n$ integers, where $n$ is a power of
two. She creates a new sequence $B$ of half the size of $A$ and sets
$B[i] = A[2i] + A[2i + 1]$, for $i = 0, 1, \dots, (n/2) - 1$. If $B$
has size $1$, then she outputs $B[0]$. Otherwise, she replaces $A$
with $B$, and repeats the process. What is the running time of her
algorithm?

\item (GTG Exercise C-4.12) Give a recursive algorithm to compute the
product of two positive integers, $m$ and $n$, using only addition and
subtraction.



\item Write a recursive function which solves the ``Tower of
Hanoi''-Puzzle.

\emph{Hint:} The input should be in the form of three lists, one for
the source peg, one for the helper peg, and one for the destination
peg, e.g.
\begin{verbatim}
  s = [4, 3, 2, 1]
  h = []
  d = []
\end{verbatim}
At the end of the puzzle, all the ``disks'', i.e., the numbers in the
list, should have moved from the source peg to the destination peg.

The move of a single ``disk'' from source to destination can be done
via the following line of Python code:
\begin{verbatim}
  d.append(s.pop())
\end{verbatim}






\end{enumerate}
\end{document}
