Divide-and-Conquer Solution for Bitonic Array Indexing

BitonicArrays.pdf

source_BitonicArrays.tex

% Copyright 2018 Alexander L. Hayes

\documentclass[usenames,dvipsnames,letterpaper]{article}
\usepackage[left=2cm, right=2cm, top=2cm]{geometry}

\usepackage{helvet}
\usepackage{courier}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{MnSymbol}
\usepackage{wasysym}

\usepackage{hyperref}

% https://en.wikibooks.org/wiki/LaTeX/Algorithms
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}

% https://www.overleaf.com/learn/latex/Code_listing
\usepackage{listings}
\usepackage{color}

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}

\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},
    commentstyle=\color{codegreen},
    keywordstyle=\color{magenta},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codepurple},
    basicstyle=\footnotesize\ttfamily,
    breakatwhitespace=false,
    breaklines=true,
    captionpos=b,
    keepspaces=true,
    numbers=left,
    numbersep=5pt,
    showspaces=false,
    showstringspaces=false,
    showtabs=false,
    tabsize=2
}

\lstset{style=mystyle}

\setlength{\pdfpagewidth}{8.5in}
\setlength{\pdfpageheight}{11in}

\newcommand*\Let[2]{\State #1 $\gets$ #2}
\algrenewcommand\algorithmicrequire{\textbf{Precondition:}}
\algrenewcommand\algorithmicensure{\textbf{Postcondition:}}


\begin{document}

\title{Divide and Conquer Method for Bitonic Array Indexing}

\author{Alexander L. Hayes\\
The University of Texas at Dallas\\
alexander@batflyer.net}

\maketitle

\textbf{\underline{Given}}: A bitonic array A[1, ..., n] of numbers strictly increasing up to an index \texttt{p}, and strictly decreasing after.

\textbf{\underline{Find}}: The index \texttt{p} using a divide and conquer algorithm. Set up the recurrence relation and solve it.

\textbf{\underline{Allowed}}: Comparison operations.

\section*{Pseudocode}

\begin{algorithm}[ht]
  \caption{Divide-and-conquer method that returns the index where a bitonic array switches from strictly increasing to strictly decreasing.}
  \begin{algorithmic}[1]

    \Function{FindP}{Array \textbf{A}, int \textbf{start}, int \textbf{end}}
      \Let{$i$}{$\lfloor($\textbf{start} + \textbf{end}$)\ /\ 2 \rfloor$}
      \Comment{Recurr over half the indexes (rounded down)}
      \If{$(\textbf{end} - \textbf{start}) \leq 3$}
        \Comment{Small case in the recurrence when three or fewer remain}
        \State \Return{small\_case(\textbf{A}, i)}
      \EndIf
      \If{$\textbf{A}[i - 1] < \textbf{A}[i + 1]$}
        \State \Return{FindP(\textbf{A}, i, \textbf{end})}
        \Comment{Recurr on the right half of \textbf{A}}
      \ElsIf{$\textbf{A}[i - 1] > \textbf{A}[i + 1]$}
        \State \Return{FindP(\textbf{A}, \textbf{start}, i)}
        \Comment{Recurr on the left half of \textbf{A}}
      \Else
        \State \Return i
      \EndIf
    \EndFunction

    \Statex

    \Function{small\_case}{Array \textbf{A}, int \textbf{i}}
      \Comment{Three or fewer comparisons}
      \If{\textbf{A}$[i - 1] <$ \textbf{A}$[i] <$ \textbf{A}$[i + 1]$}
        \State \Return{i + 1}
      \ElsIf{\textbf{A}$[i - 1] >$ \textbf{A}$[i] >$ \textbf{A}$[i + 1]$}
        \State \Return{i - 1}
      \Else
        \State \Return i
      \EndIf
    \EndFunction

  \end{algorithmic}
  \label{Alg1}
\end{algorithm}

\clearpage
\section*{Recurrence Relation and Proof by Substitution Method}

The recurrence relation for the \textbf{FindP} function may be defined as follows:

$$t(n) = t\Big(\Big\lfloor \frac{n}{2} \Big\rfloor\Big) + 1$$

The overall cost is $t(n)$. At each step, the length of the array is being divided in half (line two of Algorithm \ref{Alg1}) until the total length being reasoned about is three or fewer. The ``$+ 1$" represents all constant-time operations, such as the \textbf{small\_case} function which performs comparisons on exactly three indexes. All other comparisons and math operations are also assumed to take constant time.

\begin{enumerate}
  \item \textbf{\underline{Guess}}: $t(n) = \mathcal{O}(\log{}n)$

    \begin{align*}
      \begin{aligned}
        t(n) &= c \cdot \log{}n\\
        t\Big(\Big\lfloor \frac{n}{2} \Big\rfloor \Big) &= c \cdot \log{\Big( \Big\lfloor \frac{n}{2} \Big\rfloor \Big)}\\
      \end{aligned}
    \end{align*}

  \item \textbf{\underline{Substitution}}:

    \begin{align*}
      \begin{aligned}
        t(n) &= c \cdot \log{\Big( \Big\lfloor \frac{n}{2} \Big\rfloor \Big)} + 1\\
        &\leq c \cdot \Big( \log{n} - \log{2} \Big) + 1 && \text{Floor terms are dropped}\\
        &\leq c \cdot \log{n} - c \cdot \log{2} + 1\\
        &\leq c \cdot \log{n} - c + 1 && \log{2} \text{ is also constant}\\
        &\leq c \cdot \log{n}\ && \text{True for}\ c > 1\\
      \end{aligned}
    \end{align*}

  \item Since our substitution differs from our guess by a constant factor, we have a sufficiently tight bound to accept our hypothesis.

    $$\blacksquare\ t(n) = \mathcal{O}(\log{}n)$$

\end{enumerate}

\section*{Acknowledgements}

This problem was provided by \href{https://www.utdallas.edu/~chandra/}{Professor R. Chandrasekaran} as a bonus problem for his CS 6363 Computer Algorithms course in the Fall 2018 semester.

\clearpage
\section*{Appendix}

\subsection*{Python Implementation}

\begin{lstlisting}[language=Python]
def find_p(array):
  """
  Find the element ``p`` in a bitonic array where the entries
  switch from strictly increasing to strictly decreasing.
  """

  def small_case(_array, _i):
    """Small condition when a few elements are compared."""
    if _array[_i - 1] < _array[_i] < _array[_i + 1]:
      return i + 1
    elif _array[_i - 1] > _array[_i] > _array[_i + 1]:
      return _i - 1
    return _i

  def find_p_helper(array, start, end):
    """Helper function with explicit start and end positions."""
    i = (start + end) // 2

    if (end - start) <= 3:
      return small_case(array, i)

    if array[i - 1] < array[i + 1]:
      return find_p_helper(array, i, end)
    elif array[i - 1] > array[i + 1]:
      return find_p_helper(array, start, i)
    return i

  return find_p_helper(array, 0, len(array))
\end{lstlisting}

\end{document}