\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 31, 2022}
\maketitle

\begin{enumerate}
\item (GTG R-5.6) Our implementation of insert for the
\texttt{DynamicArray} class, as given in the code
\verb+ch05/dynamic_array.py+ of the book's repository, has the
following inefficiency. In the case when a resize occurs, the resize
operation takes time to copy all the elements from an old array to a
new array, and then the subsequent loop in the body of insert shifts
many of those elements. Give an improved implementation of the insert
method, so that, in the case of a resize, the elements are shifted
into their final position during that operation, thereby avoiding the
subsequent shifting.


\item (GTG R-5.7) Let $A$ be an array of size $n \geq 2$ containing
integers from $1$ to $n - 1$, inclusive, with exactly one
repeated. Describe a fast algorithm for finding the integer in $A$
that is repeated.


\item (GTG C-5.16) Implement a pop method for the
\texttt{DynamicArray} class that removes the last element of the
array, and that shrinks the capacity, $N$, of the array by half any
time the number of elements in the array goes below $N/4$.


\end{enumerate}
\end{document}
