\documentclass[12pt]{article}

\usepackage{fullpage,amsmath,amsfonts,hyperref}
\usepackage{pythonhighlight}

\begin{document}

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

\begin{enumerate}

\item (GTG Exercise C-9.27) Show how to implement the FIFO queue ADT
using only a priority queue and one additional integer instance
variable.

\item (GTG Exercise C-9.28) Professor Idle suggests the following
solution to the previous problem.  Whenever an item is inserted into
the queue, it is assigned a key that is equal to the current size of
the queue. Does such a strategy result in FIFO semantics? Prove that
it is so or provide a counterexample.

\item (GTG Exercise R-10.21) The following implementation of binary
search is used by GTG in their implementation of the
\texttt{SortedTableMap} class:
\begin{python}
def _find_index(self, k, low, high):
  """Return index of the leftmost item with key greater than or equal to k.

  Return high + 1 if no such item qualifies.

  That is, j will be returned such that:
     all items of slice table[low:j] have key < k
     all items of slice table[j:high+1] have key >= k
  """
  if high < low:
    return high + 1                               # no element qualifies
  else:
    mid = (low + high) // 2 
    if k == self._table[mid]._key:
      return mid                                  # found exact match
    elif k < self._table[mid]._key:
      return self._find_index(k, low, mid - 1)    # Note: may return mid
    else:
      return self._find_index(k, mid + 1, high)   # answer is right of mid
\end{python}
Consider the following variant of the find index method:
\begin{python}
def _find_index(self, k, low, high):
  if high < low:
    return high + 1
  else:
    mid = (low + high) // 2
    if self._table[mid].key < k:
      return self._find_index(k, mid + 1, high)
    else:
      return self._find_index(k, low, mid - 1)
\end{python}
Does this always produce the same result as the original version? Justify
your answer.

\item (GTG Exercise R-10.6) Which of the hash table collision-handling
schemes could tolerate a load factor above $1$ and which could not?

\item (GTG Exercise R-10.18) Explain why a hash table is not suited to
implement a sorted map.


\item (GTG Exercise C-10.45) Describe how to modify a skip-list representation so that index-based
operations, such as retrieving the item at index $j$, can be performed in
$O(\log n)$ expected time.

\end{enumerate}
\end{document}
