\documentclass[12pt]{article}
\usepackage{palatino}
\usepackage{epsfig}
\usepackage{epstopdf} % for \psfig{.eps}
\usepackage{color}
\usepackage{tabularx}
\usepackage{hyperref}
\usepackage{url}
\usepackage{listings} % for embedded code
\lstset{basicstyle=\ttfamily, numbers=left, numberstyle=\tiny, numbersep=5pt,
   extendedchars=true, language=C, morekeywords={bool}, mathescape=true,
	tabsize=3,
	}
\setlength{\topmargin}{-0.1in}
\setlength{\leftmargin}{-0.1in}
\setlength{\textheight}{8.0in}
% \newcommand\note[1]{{\color{red} #1}}
\pagestyle{myheadings}
\markboth{CS315 Spring 2021}{CS315 Spring 2021}
\newcommand\note[1]{\fbox{#1}}
\newcommand\codebold[1]{\texttt{\textbf{#1}}}
\newcommand\order[1]{$\mathcal O(#1)$}
\newenvironment{notelist}{\begin{list}
   {$\bullet$}
   {\setlength{\itemsep}{0in}}}
   {\end{list}}
\author{Raphael Finkel}
\title{CS315 Class Notes}
\begin{document}
\maketitle

\section{Intro}
% \note{Lecture 1, 1/16/2020}
\note{Class 1, 1/26/2021}
\begin{notelist}
\item Handout 1 --- My names
\item TA:
\item Plagiarism --- read aloud
\item Assignments on web.  Use C, C++, or Java.
\item E-mail list:
\item accounts in MultiLab
\item text --- we will skip around
\end{notelist}

\section{Basic building blocks: Linked lists (Chapter 3) and trees (Chapter 4)}

Linked lists and trees are examples of {\bf data structures}: 
\begin{notelist} 
\item way to represent information
\item so it can be manipulated
\item packaged with routines that do the manipulations
\end{notelist}
Leads to an {\bf Abstract Data Type (ADT)}: has an API (specification) and
hides its internals.

\section{Tools}
\hspace*{1in}\psfig{figure=softwareTool.eps,height=0.6in}

\section{Singly-linked list}
\begin{notelist} 
\item used as a part of several ADTs.
\item Can be considered an ADT itself.
\item Collection of {\bf nodes}, each with optional arbitrary {\bf data} and
a {\bf pointer} to the next element on the list.
\end{notelist} 
\hspace*{1in}\psfig{figure=linkedList.eps,height=1.0in}

\begin{tabular}{l l}
{\bf operation} & {\bf cost} \\
create empty list   & \order{1} \\
insert new node at front of list & \order{1} \\
delete first node, returning data & \order{1} \\
count length & \order{n} \\
search by data  & \order{n} \\
sort & \order{n \log~ n} to \order{n^2}
\end{tabular}

\section{Sample code (in C)}
\begin{minipage}{4in} \begin{lstlisting}
#define NULL 0
#include <stdlib.h>

typedef struct node_s {
   int data;
   struct node_s *next;
} node;

node *makeNode(int data, node* next) {
   node *answer = (node *) malloc(sizeof(node));
   answer->data = data;
   answer->next = next;
   return(answer);
} // makeNode

node *insertAtFront(node* handle, int data) {
   node *answer = makeNode(data, handle->next);
	handle->next = answer;
	return(answer);
} // insertAtFront

node *searchDataIterative(node *handle, int data) {
   // iterative method
   node *current = handle->next;
   while (current != NULL) {
      if (current->data == data) break;
      current = current->next;
   }
   return current;
} // searchDataIterative

node *searchDataRecursive(node *handle, int data) {
   // recursive method
   node *current = handle->next;
   if (current == NULL) return NULL;
   else if (current->data == data) return current;
   else return searchDataRecursive(current, data);
} // searchDataRecursive
\end{lstlisting} \end{minipage}

\section{Improving the efficiency of some operations}
\begin{notelist}
% \item \note{Lecture 2, 1/21/2020}
\item To make count() fast: maintain the count in a separate variable.  If we
need the count more often than we insert and delete, it is worthwhile.
\item
To make insert at rear fast: maintain two handles, one to the front, the
other to the rear of the list.
\item Combine these new items in a header node: \\
\begin{minipage}{4in} \begin{lstlisting}
typedef struct {
   node *front;
   node *rear;
   int count;
} nodeHeader;
\end{lstlisting} \end{minipage} \\
\item \note{Class 2, 1/28/2021}
\item To make search faster: remove the special case that we reach the end of
the list by placing a {\bf pseudo-data node} at the end.  Keep track of the
pseudo-data node in the header. \\
\begin{minipage}{4in} \begin{lstlisting}
typedef struct {
   node *front;
   node *rear;
   node *pseudo;
   int count;
} nodeHeader;

node *searchDataIterative(nodeHeader *header, int data) {
   // iterative method
   header->pseudo->data = data;    
   node *current = header->front;
   while (current->data != data) {
      current = current->next;
   }
   return (current == header->pseudo ? NULL : current);
} // searchDataIterative
\end{lstlisting} \end{minipage}
\item Exercise: If we want both pseudo-data and a {\tt rear} pointer, how does
an empty list look?
\item Exercise: If we want pseudo-data, how does {\tt searchDataRecursive()} change?
\item Exercise: Is it easy to add a new node {\em after} a given node?
\item Exercise: Is it easy to add a new node {\em before} a given node?
\end{notelist}

\section{Aside: Unix pipes}
\begin{notelist}
% \item \note{Lecture 3, 1/23/2020}
\item Unix programs automatically have three ``files'' open: standard input,
which is by default the keyboard, standard output, which is by default the
screen, and standard error, which is by default the screen.  
\item In C and C++, they are defined in {\tt stdio.h} by the names {\tt stdin},
{\tt stdout}, and {\tt stderr}.
\item The command interpreter (in Unix, it's called the ``shell'') lets you
invoke programs redirecting any or all of these three.  For instance,
{\tt ls | wc} redirects {\tt stdout} of the {\tt ls} program to {\tt stdin} of
the {\tt wc} program.
\item If you run your {\tt trains} program without redirection, you can type in
arbitrary numbers.
\item If you run {\tt randGen.pl} without redirection, it generates an unbounded
list of pseudo-random numbers to {\tt stdout}.
\item If you run {\tt randGen.pl | trains}, the list of numbers from {\tt
randGen.pl} is redirected as input to {\tt trains}.
\end{notelist}

\section{Stacks, queues, dequeues: built out of either linked lists or arrays}
\begin{notelist}
\item We'll see each of these.
\end{notelist}

\section{Stack of integer}
\begin{notelist}
\item Abstract definition: either {\bf empty} or the result of pushing an
integer onto the stack.
\item operations
   \begin{notelist}
   \item stack makeEmptyStack()
   \item \codebold{boolean} isEmptyStack(stack S)
   \item \codebold{int} popStack(stack *S) // modifies S
   \item \codebold{void} pushStack(stack *S, \codebold{int} I) // modifies S
   \end{notelist}
\end{notelist}
\section{Implementation 1 of Stack: Linked list}
   \begin{notelist}
   \item {\tt makeEmptyStack} implemented by {\tt makeEmptyList()}
   \item {\tt isEmptyStack} implemented by {\tt isEmptyList()}
   \item {\tt pushStack} inserts at the front of the list
   \item {\tt popStack} deletes from the front of the list
   \end{notelist}

\section{Implementation 2 of Stack: Array}
\begin{notelist}
\item \note{Class 3, 2/2/2021}
\item {\bf Warning:} it's easy to make off-by-one errors. \\
\begin{minipage}{5in} \begin{lstlisting}
#define MAXSTACKSIZE 10
#include <stdlib.h>

typedef struct {
   int contents[MAXSTACKSIZE];
   int count; // index of first free space in contents
} stack;

stack *makeEmptyStack() {
   stack *answer = (stack *) malloc(sizeof(stack));
   answer->count = 0;
   return answer;
} // makeEmptyStack

void pushOntoStack(stack *theStack, int data) {
   if (theStack->count == MAXSTACKSIZE) {
      (void) error("stack overflow");
   } else {
      theStack->contents[theStack->count] = data;
      theStack->count += 1;
   }
} // pushOntoStack

int popFromStack(stack *theStack) {
   if (theStack->count == 0) {
      return error("stack underflow");
   } else {
      theStack->count -= 1;
      return theStack->contents[theStack->count];
   }
} // popFromStack
\end{lstlisting} \end{minipage}

\item The array implementation limits the size.  Does the linked-list
implementation also limit the size?
\item The array implementation needs one cell per (potential) element, and one
for the count.  How much space does the linked-list implementation need?
\item We can position two opposite-sense stacks in one array so long as their
combined size never exceeds MAXSTACKSIZE.
\end{notelist}

\section{Queue of integer}
\begin{notelist}
\item Abstract definition: either {\bf empty} or the result of inserting
an integer at the rear of a queue or deleting an integer from the front of a
queue.
\item operations
   \begin{notelist}
   \item queue makeEmptyQueue()
   \item \codebold{boolean} isEmptyQueue(queue Q)
   \item \codebold{void} insertInQueue(queue Q, \codebold{int} I) // modifies Q
   \item \codebold{int} deleteFromQueue(queue Q) // modifies Q
   \end{notelist}
\end{notelist}

\section{Implementation 1 of Queue: Linked list}

We use a header to represent the front and the rear, and we put a dummy node
at the front to make the code work equally well for an empty queue.
\medskip
\hspace*{1in}\psfig{figure=listQueue.eps,height=1.6in}

\begin{minipage}{4in} \begin{lstlisting}
#include <stdlib.h>

typedef struct node_s {
   int data;
   struct node_s *next;
} node;

typedef struct {
   node *front;
   node *rear;
} queue;

queue *makeEmptyQueue() {
   queue *answer = (queue *) malloc(sizeof(queue));
   answer->front = answer->rear = makeNode(0, NULL);
   return answer;
} // makeEmptyQueue

bool isEmptyQueue(queue *theQueue) {
   return (theQueue->front == theQueue->rear);
} // isEmptyQueue

void insertInQueue(queue *theQueue, int data) {
   node *newNode = makeNode(data, NULL);
   theQueue->rear->next = newNode;
   theQueue->rear = newNode;
} // insertInQueue

int deleteFromQueue(queue *theQueue) {
   if (isEmptyQueue(theQueue)) return error("queue underflow");
   node *oldNode = theQueue->front->next;
   theQueue->front->next = oldNode->next;
   if (theQueue->front->next == NULL) {
      theQueue->rear = theQueue->front;
   }
   return oldNode->data;
} // deleteFromQueue
\end{lstlisting} \end{minipage}

\section{Implementation 2 of Queue: Array}
{\bf Warning:} it's easy to make off-by-one errors.
%\note{Lecture 3, 1/17/2019}
\\
\vspace*{1in} \\
\psfig{figure=arrayQueues.eps,height=4.5in} \\
\begin{minipage}{4in} \begin{lstlisting}
#define MAXQUEUESIZE 30

typedef struct {
   int contents[MAXQUEUESIZE];
   int front; // index of element at the front
   int rear; // index of first free space after the queue
} queue;

bool isEmptyQueue(queue *theQueue) {
   return (theQueue->front == theQueue->rear);
} // isEmptyQueue

int nextSlot(int index) { // circular
   return (index + 1) % MAXQUEUESIZE;
} // nextSlot

void insertInQueue(queue *theQueue, int data) {
   if (nextSlot(theQueue->rear) == theQueue->front)
      error("queue overflow");
   else {
      theQueue->contents[theQueue->rear] = data;
      theQueue->rear = nextSlot(theQueue->rear);
   }
} // insertInQueue

int deleteFromQueue(queue *theQueue) {
	if (isEmptyQueue(theQueue)) {
      return error("queue underflow");
	} else {
		int answer = theQueue->contents[theQueue->front];
      theQueue->front = nextSlot(theQueue->front);
      return answer;
   }
} // deleteFromQueue
\end{lstlisting} \end{minipage}

\section{Dequeue of integer}
\begin{notelist}
\item Abstract definition: either {\bf empty} or the result of inserting
an integer at the front or rear of a dequeue or deleting an integer from the
front or rear of a queue.
\item operations
   \begin{notelist}
   \item dequeue makeEmptyDequeue()
   \item \codebold{boolean} isEmptyDequeue(dequeue D)
   \item \codebold{void} insertFrontDequeue(dequeue D, \codebold{int} I) // modifies D
   \item \codebold{void} insertRearDequeue(dequeue D, \codebold{int} I) // modifies D
   \item \codebold{int} deleteFrontDequeue(dequeue D) // modifies D
   \item \codebold{int} deleteRearDequeue(dequeue D) // modifies D
   \end{notelist}
\item Exercise: code the insertFrontDequeue() and deleteRearDequeue() routines
using an array.
\item All operations for a singly-linked list implementation are
\order{1} except for deleteRearDequeue(), which is
\order{n}.
\item The best list structure is a {\bf doubly-linked list} with a single
dummy node.

\hspace*{1in}\psfig{figure=doublyLinked.eps,height=3.0in}

\item Exercise: Code all the routines.
\item Exercise: Is it easy to add a new node {\em after} a given node?
\item Exercise: Is it easy to add a new node {\em before} a given node?
\end{notelist}

\section{Searching}
\begin{notelist}
\item \note{Class 4, 2/4/2021}
%\item \note{Lecture 4, 1/22/2019}
\item Given $n$ data elements (we will use integer data), arrange them in a
data structure D so that these operations are fast:
   \begin{notelist}
   \item \codebold{void} insert(\codebold{int} data, *D)
   \item \codebold{boolean} search(\codebold{int} data, D) (can also return entire data record)
   \end{notelist}
\item We don't care about the speed of deletion (for now).
\item Much of this material is in Chapter 4 of the book (trees)
\item Representation 1: Linked list
	\begin{notelist}
	\item insert(i) is \order{1}: Place new element at the front.
	\item search(i) is \order{n}: We may need to look at whole list;
	we use pseudo-data $i$ to make search as fast as possible
	\end{notelist}
\item Representation 2: Sorted linked list
	\begin{notelist}
	\item insert(i) is \order{n}: On average, $n/2$ steps.
	Use pseudo-data (value $\infty$) at end to make insertion as fast as
	possible.
	\item search(i) is \order{n}: We may need to look at whole list; on
	average, we look at $n/2$ elements if the search succeeds; all $n$ elements
	if it fails. Use pseudo-data (value $\infty$) to make search as fast
	as possible.
	\end{notelist}
% \item \note{Lecture 4, 1/28/2020}
\item Representation 3: Array
	\begin{notelist}
	\item insert(i) is \order{1}: We place new element at the rear.
	\item search(i) is \order{n}: We may need to look at whole list; use
	pseudo-data $i$ at rear.
	\end{notelist}
\item  Representation 4: Sorted array
	\begin{notelist}
	\item insert(i) is \order{n}: We need to search and then shove cells
	over.
	\item search(i) is \order{\log  n}: We use {\bf binary search}.

	\hspace*{-.7in}\begin{minipage}{4in} \begin{lstlisting}
// warning: it's easy to make off-by-one errors.
bool binarySearch(int target, int *array,
		int lowIndex, int highIndex) {
   // look for target in array[lowIndex..highIndex]
   while (lowIndex < highIndex) { // at least 2 elements
      int mid = (lowIndex + highIndex) / 2; // round down
      if (array[mid] < target) lowIndex = mid + 1;
      else highIndex = mid;
   } // while at least 2 elements
   return (array[lowIndex] == target);
} // binarySearch
	\end{lstlisting} \end{minipage}
	\end{notelist}
\end{notelist}

\newpage
\section{Quadratic search: set mid based on discrepancy}

Also called {\bf interpolation search}, {\bf extrapolation search}, {\bf
dictionary search}.

\begin{minipage}{5in} \begin{lstlisting}
bool quadraticSearch(int target, int *array,
		int lowIndex, int highIndex) {
   // look for target in array[lowIndex..highIndex]
   while (lowIndex < highIndex) { // at least 2 elements
      if (array[highIndex] == array[lowIndex]) {
         highIndex = lowIndex;
         break;
      }
      float percent = (0.0 + target - array[lowIndex])
         / (array[highIndex] - array[lowIndex]);
      int mid = int(percent * (highIndex-lowIndex)) + lowIndex;
      if (mid == highIndex) {
			mid -= 1;
		}
      if (array[mid] < target) {
         lowIndex = mid + 1;
      } else {
         highIndex = mid;
      }
   } // while at least 2 elements
   return(array[lowIndex] == target);
} // quadraticSearch
\end{lstlisting} \end{minipage}

Experimental results
\begin{notelist}
\item It is hard to program correctly.
\item For $10^6 ~ \approx ~ 2^{20}$ elements, binary search always makes 20
probes.
\item This result is consistent with \order{\log~n}.
\item Quadratic search: 20 tests with uniform data.
The range of probes was 3 -- 17; the average about 9 probes.
\item Analysis shows that if the data are uniformly distributed, quadratic
search should be \order{\log~\log~n}.
\end{notelist}

\section{Analyzing binary search}
\begin{notelist}
\item Binary search: $c_n = 1 + c_{n/2}$ where $c_n$ is the number
of steps to search for an element in an array of length $n$.
\item We will use the {\bf Recursion Theorem}:
\label{recursionTheorem}
if $c_n = f(n) + a c_{n/b}$, where $f(n) = \Theta(n^k)$, then \\
\begin{center}\begin{tabular}{l | l}
when & $c_n$ \\
\hline
$a < b^{k}$ & $\Theta(n^k)$ \\
$a = b^{k}$ & $\Theta(n^k ~ \log~n)$ \\
$a > b^{k}$ & $\Theta(n^{log_b a})$
\end{tabular} \end{center}

\item In our case, $a=1$, $b=2$, $k=0$, so $b^k = 1$, so $a = b^k$, so
$c_n = \Theta(n^k~\log~n) = \Theta(\log~n)$.
\item Bad news: any comparison-based searching algorithm is $\Omega(\log~n)$,
that is, needs at least on the order of $\log~n$ steps.
\item Notation, slightly more formally defined.  All these ignore multiplicative
constants.
	\begin{notelist}
 	\item $\mathcal O(f(n))$: no worse than $f(n)$; at most $f(n)$.	
 	\item $\Omega(f(n))$: no better than $f(n)$; at least $f(n)$.
 	\item $\Theta(f(n))$: no better or worse than $f(n)$; exactly $f(n)$.
	\end{notelist}
\end{notelist}

\section{Representation 5: Binary tree}
\begin{notelist}
% \item \note{Lecture 5, 1/30/2020}
\item \note{Class 5, 2/9/2021}
\item Example with elicited values
\item Pseudo-data: in the universal ``null'' node.
\item insert(i) and search(i) are both \order{\log~n} if we are
lucky or data are random. \\
\hspace*{-.5in}\begin{minipage}{4in} \begin{lstlisting}
#define NULL 0
#include <stdlib.h>

typedef struct treeNode_s {
   int data;
   treeNode_s *left, *right;
} treeNode;

treeNode *makeNode(int data) {
   treeNode *answer = (treeNode *) malloc(sizeof(treeNode));
   answer->data = data;
   answer->left = answer->right = NULL;
   return answer;
} // makeNode

treeNode *searchTree(treeNode *tree, int key) {
   if (tree == NULL) return(NULL);
   else if (tree->data == key) return(tree);
   else if (key <= tree->data)
      return(searchTree(tree->left, key));
   else 
      return(searchTree(tree->right, key));
} // searchTree

void insertTree(treeNode *tree, int key) {
   // assumes empty tree is a pseudo-node with infinite data
   treeNode *parent = NULL;
   treeNode *newNode = makeNode(key);
   while (tree != NULL) { // dive down tree
      parent = tree;
      tree = (key <= tree->data) ? tree->left : tree->right;
   } // dive down tree
   if (key <= parent->data) 
      parent->left = newNode;
   else
      parent->right = newNode;
} // insertTree
\end{lstlisting} \end{minipage}
\item We will deal with balancing trees later.
\end{notelist}

\section{Traversals}
\begin{notelist}
\item A {\bf traversal} walks through the tree, visiting every node.
\item {\bf Symmetric traversal} (also called {\bf inorder}) \\
\begin{minipage}{4in} \begin{lstlisting}
void symmetric(treeNode *tree) {
	if (tree == NULL) { // do nothing
	} else {
		symmetric(tree->left);
		visit(tree);
		symmetric(tree->right);
	}
} // symmetric()
\end{lstlisting} \end{minipage}
\item {\bf Pre-order traversal} \\
\begin{minipage}{4in} \begin{lstlisting}
void preorder(treeNode *tree) {
	if (tree == NULL) { // do nothing
	} else {
		visit(tree);
		preorder(tree->left);
		preorder(tree->right);
	}
} // preorder()
\end{lstlisting} \end{minipage}
\item {\bf Post-order traversal} \\
\begin{minipage}{4in} \begin{lstlisting}
void postorder(treeNode *tree) {
	if (tree == NULL) { // do nothing
	} else {
		postorder(tree->left);
		postorder(tree->right);
		visit(tree);
	}
} // postorder()
\end{lstlisting} \end{minipage}
\item Does pseudo-data make sense?
\end{notelist}

\section{Representation 6: Hashing (scatter storage)}
\begin{notelist}
\item Hashing is often the best method for searching (but not for sorting).
\item insert(data) and search(data) are \order{\log~n}, but 
we can generally treat them as \order{1}.
\item We will discuss hashing later.
\end{notelist}

\section{Finding the $j$th largest element in a set}
\begin{notelist}
% \item \note{Lecture 6, 2/4/2020}
\item If $j=1$, a single pass works in \order{n} time: \\
\begin{minipage}{4in} \begin{lstlisting}[mathescape=true, morekeywords={foreach,in}]
largest = -$\infty$; // priming
foreach (value in set) {
   if (value > largest) largest = value;
}
return(largest);
\end{lstlisting} \end{minipage}
\item If $j=2$, a single pass still works in \order{n} time, but it is
about twice as costly: \\
\begin{minipage}{4in} \begin{lstlisting}[mathescape=true, morekeywords={foreach,in}]
largest = nextLargest = -$\infty$; // priming
foreach (value in set) {
   if (value > largest) {
      nextLargest = largest;
      largest = value;
   } else if (value > nextLargest) {
      nextLargest = value;
   }
} // foreach value
return(nextLargest);
\end{lstlisting} \end{minipage}
\item It appears that for arbitrary $j$ we need \order{j n} time, because
each iteration needs $t$ tests, where $1 \le t \le j$, followed by modifying
$j+1-t$ values, for a total cost of $j+1$.
\item \note{Class 6, 2/11/2021}
\item Clever algorithm using an array: {\bf QuickSelect} (Tony Hoare)
   \begin{notelist}
   \item Partition the array into ``small'' and ``large'' elements with a
   pivot between them (details soon).
   \item Recurse in either the small or large subarray, depending where the
   $j$th element falls.  Stop if the $j$th element is the pivot.
   \end{notelist}
\item Cost: $n + n/2 + n/4 + \dots ~=~ 2n = \mathcal{O}(n)$
\item We can also compute the cost using the recursion theorem (page
\pageref{recursionTheorem}):
   \begin{notelist}
   \item $c_n = n + c_{n/2}$ (if we are lucky)
   \item $c_n = n + c_{2n/3}$ (fairly average case)
   \item $f(n) = n = \mathcal{O}(n^1)$
   \item $k=1$, $a=1$, $b=2$ (or $b=3/2$)
   \item $a < b^k$
   \item so $c_n = \Theta(n^k) = \Theta(n)$
   \end{notelist}
\end{notelist}

\section{Partitioning an array}
\begin{notelist}
\item Nico Lomuto's method
\item Online demonstration.
\item The method partitions {\tt array[lowIndex .. highIndex]} into three
pieces:
   \begin{notelist}
   \item {\tt array[lowIndex~..~divideIndex -1]}
   \item {\tt array[divideIndex]}
   \item {\tt array[divideIndex + 1 .. highIndex]}
   \end{notelist}
   The elements of each piece are in order with respect to adjacent pieces.
\\
\hspace*{-.7in}\begin{minipage}{4in} \begin{lstlisting}
int partition(int array[], int lowIndex, int highIndex) {
   // modifies array, returns pivot index.
   int pivotValue = array[lowIndex];
   int divideIndex = lowIndex;
   for (int combIndex = lowIndex+1; combIndex <= highIndex;
         combIndex += 1) {
      // array[lowIndex] is the partitioning (pivot) value.
      // array[lowIndex+1 .. divideIndex] are < pivot
      // array[divideIndex+1 .. combIndex-1] are $\geq$ pivot
      // array[combIndex .. highIndex] are unseen
      if (array[combIndex] < pivotValue) { // see a small value
         divideIndex += 1;
         swap(array, divideIndex, combIndex);
      }
   } // each combIndex
   // swap pivotValue into its place
	swap(array, divideIndex, lowIndex);
   return(divideIndex);
} // partition
\end{lstlisting} \end{minipage}
\item Example \\
\begin{tabularx}{4in}{|X|X|X|X|X|X|X|X|X|X|X}
\hline
5 & 2 & 1 & 7 & 9 & 0 & 3 & 6 & 4 & 8 \\
d & c &   &   &   &   &   &   &   &   \\
\hline
  & d,c &   &   &   &   &   &   & & \\
5 & 2 & 1 & 7 & 9 & 0 & 3 & 6 & 4 & 8 \\
  & d & c &   &   &   &   &   &   & \\
\hline
  &   & d,c &   &   &   &   &   &   & \\
5 & 2 & 1 & 7 & 9 & 0 & 3 & 6 & 4 & 8 \\
  &   & d & c &   &   &   &   &   &   \\
\hline
  &   & d & c &   &   &   &   &   &   \\
  &   & d &   & c &   &   &   &   &   \\
\hline
  &   & d &   & c &   &   &   &   &   \\
  &   & d &   &   & c &   &   &   &   \\
\hline
  &   &   & d &   & c &   &   &   &   \\
5 & 2 & 1 & 0 & 9 & 7 & 3 & 6 & 4 & 8 \\
  &   &   & d &   &   & c &   &   &   \\
\hline
  &   &   &   & d &   & c &   &   &   \\
5 & 2 & 1 & 0 & 3 & 7 & 9 & 6 & 4 & 8 \\
  &   &   &   & d &   &   & c &   &   \\
\hline
  &   &   &   & d &   &   & c &   &   \\
  &   &   &   & d &   &   &   & c &   \\
\hline
  &   &   &   &   & d &   &   & c &   \\
5 & 2 & 1 & 0 & 3 & 4 & 9 & 6 & 7 & 8 \\
  &   &   &   &   & d &   &   &   & c \\
\hline
  &   &   &   &   & d &   &   &   & c \\
  &   &   &   &   & d &   &   &   &   & c \\
\hline
\hline
4 & 2 & 1 & 0 & 3 & 5 & 9 & 6 & 7 & 8 \\
\end{tabularx}
\end{notelist}

\section{Using partitioning to select $j$th smallest}
% \note{Lecture 7, 2/6/2020} \\
\begin{minipage}{4in} \begin{lstlisting}
int selectJthSmallest (int array[], int size, int targetIndex) {
   // rearrange the values in array[0..size-1] so that 
	// array[targetIndex] has the value it would have if the array 
	// were sorted. 
	int lowIndex = 0;
	int highIndex = size-1;
	while (lowIndex < highIndex) {
		int midIndex = partition(array, lowIndex, highIndex);
		if (midIndex == targetIndex) {
			return array[targetIndex];
		} else if (midIndex < targetIndex) { // look to right
			lowIndex = midIndex + 1;
		} else { // look to left
			highIndex = midIndex - 1;
		}
	} // while lowIndex < highIndex
	return array[targetIndex];
} // selectJthSmallest
\end{lstlisting} \end{minipage}

\section{Sorting}
\begin{notelist}
\item \note{Class 7, 2/16/2021}
\item  We usually are interested in sorting an array {\bf in place}.
\item Sorting is $\Omega(n~\log~n)$.
\item Good methods are \order{n~\log~n}.
\item Bad methods are \order{n^2}.
\end{notelist}

\section{Sorting out sorting}
\begin{notelist}
%\item \note{Lecture 7, 1/31/2019}
\item \url{https://www.youtube.com/watch?v=HnQMDkUFzh4}
Original film.
\item \url{https://www.youtube.com/watch?v=kPRA0W1kECg}
15 methods in 6 minutes.
\end{notelist}

\section{Insertion sort}
\begin{notelist}
% \item \note{Lecture 8, 2/11/2020} \\
\item Comb method:\\
\hspace{0.5in}\psfig{figure=insertionSort.eps,height=2.0in}
\item $n$ iterations.
\item  Iteration $i$ may need to shift the probe value $i$ places.
\item $\Rightarrow ~ \mathcal{O}(n^2)$.
\item Experimental results for Insertion Sort:\\
compares + moves $\approx n $. \\
\begin{tabular}{r r r r}
$n$ & compares & moves & $n^2/2$ \\
\hline
100 & 2644  & 2545  &  5000 \\
200 & 9733  & 9534  &  20000 \\
400 & 41157 & 40758 &  80000 \\
\end{tabular} \\
\begin{minipage}{4in} \begin{lstlisting}
void insertionSort(int array[], int length) {
   // array goes from 1..length.
	// location 0 is available for pseudo-data.
   int combIndex, combValue, sortedIndex;
   for (combIndex = 2; combIndex <= length; combIndex += 1) {
      // array[1 .. combIndex-1] is sorted.
      // Place array[combIndex] in order.
      combValue = array[combIndex];
      sortedIndex = combIndex - 1;
      array[0] = combValue - 1; // pseudo-data
      while (combValue < array[sortedIndex]) {
         array[sortedIndex+1] = array[sortedIndex];
         sortedIndex -= 1;
      }
      array[sortedIndex+1] = combValue;
   } // for combIndex
} // insertionSort
\end{lstlisting} \end{minipage}
\item {\em Stable}: multiple copies of the same key stay in order.
\end{notelist}

\section{Selection sort}
\begin{notelist}
\item Comb method:\\
\hspace{0.5in}\psfig{figure=selectionSort.eps,height=2.0in}
\item $n$ iterations.
\item  Iteration $i$ may need to search through $n-i$ places.
\item $\Rightarrow ~ \mathcal{O}(n^2)$.
\item Experimental results for Selection Sort:\\
compares + moves $\approx n $. \\
\begin{tabular}{r r r r}
$n$ & compares & moves & $n^2/2$ \\
\hline
100 & 4950  & 198 & 5000  \\
200 & 19900 & 398 & 20000 \\
400 & 79800 & 798 & 80000 \\
\end{tabular} \\
\begin{minipage}{4in} \begin{lstlisting}
void selectionSort(int array[], int length) {
   // array goes from 0..length-1
   int combIndex, smallestValue, bestIndex, probeIndex;
   for (combIndex = 0; combIndex < length; combIndex += 1) {
      // array[0 .. combIndex-1] has lowest elements, sorted.
      // Find smallest other element to place at combIndex.
      smallestValue = array[combIndex];
      bestIndex = combIndex;
      for (probeIndex = combIndex+1; probeIndex < length;
            probeIndex += 1) {
         if (array[probeIndex] < smallestValue) {
            smallestValue = array[probeIndex];
            bestIndex = probeIndex;
         }
      }
      swap(array, combIndex, bestIndex);
   } // for combIndex
} // selectionSort
\end{lstlisting} \end{minipage}
\item Not {\em stable}, because the swap moves an arbitrary value into the
unsorted area.
\end{notelist}

\section{Quicksort (C. A. R. Hoare)}
\begin{notelist}
\item \note{Class 8, 2/18/2021}
\item  Recursive based on partitioning:\\
\hspace{0.5in}\psfig{figure=quickSort.eps,height=3.0in}
\item about $\log~n$ depth.
\item each depth takes about \order{n} work.
\item $\Rightarrow ~ \mathcal{O}(n~\log~n)$.
\item Can be unlucky: \order{n^2}.
\item To prevent worst-case behavior, partition based on median of 3 or 5.
\item Don't Quicksort small regions; use a final
insertionSort pass instead.  Experiments how that the optimal break point
depends on the implementation, but somewhere between 10 and 100 is usually good.
\item Experimental results for QuickSort:\\
compares + moves $\approx 2.4 ~ n \log n$. \\
\begin{tabular}{r r r r r}
$n$ & compares & moves & $n \log n$ & $n^2/2$ \\
\hline
100  & 643   & 824   & 664   & 5000    \\
200  & 1444  & 1668  & 1528  & 20000   \\
400  & 3885  & 4228  & 3457  & 80000   \\
800  & 8066  & 8966  & 7715  & 320000  \\
1600 & 17583 & 18958 & 17030 & 1280000 \\
\end{tabular} \\
\item Analysis if lucky: $C_n = n + 2 C_{n/2}$, so 
$k = 1, a = 2, b = 2$, so $a = b^k$, so
$C_n = \Theta(n^k \log n) = \Theta(n \log n)$.
\item Analysis if unlucky:
$C_n = n + C_{n/3} + C_{2n/3} < n + 2 C_{2n/3}$, so
$k = 1, a = 2, b = 3/2$, so $a > b^k$, so
$C_n < \Theta(n^{log_b a}) =
\Theta(n^{log_{3/2} 2}) \approx \Theta(n ^ {1.70951})$,
which is still better than quadratic.
\end{notelist}
\begin{minipage}{4in} \begin{lstlisting}
void quickSort(int array[], int lowIndex, int highIndex){
   if (highIndex - lowIndex <= 0) return;
      // could stop if <= 6 and finish by using insertion sort.
   int midIndex = partition(array, lowIndex, highIndex);
   quickSort(array, lowIndex, midIndex-1);
   quickSort(array, midIndex+1, highIndex);
} // quickSort
\end{lstlisting} \end{minipage}

\section{Shell Sort (Donald Shell, 1959)}
\begin{notelist}
\item Each pass has a {\bf span} $s$. \\
\begin{minipage}{4in} \begin{lstlisting}[morekeywords={in}]
for (int span in reverse(spanSequence)) {
   for (int offset = 0; offset < span; offset += 1) {
      insertionSort(a[offset], a[offset+span], ... )
   } // each offset
} // each span
\end{lstlisting} \end{minipage}
\item The last element in spanSequence must be 1.
\item Tokuda's sequence: $s_0 = 1$; $s_k = 2.25 s_{k-1} + 1$;
	$span_k = \lceil s_k \rceil$
	=  1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, ...
\item Experimental results for Shell Sort:
compares + moves $\approx 2.2 n \log n$. \\
\begin{tabular}{r r r r r}
$n$ & compares & moves & $n \log n$ & $n^2/2$ \\
\hline
100  & 355   & 855   & 664   & 5000    \\
200  & 932   & 1932  & 1528  & 20000   \\
400  & 2266  & 4666  & 3457  & 80000   \\
800  & 5216  & 10816 & 7715  & 320000  \\
1600 & 11942 & 24742 & 17030 & 1280000 \\
\end{tabular} \\
\end{notelist}

\section{Heaps: a kind of tree}
\begin{notelist}
% \item \note{Lecture 9, 2/13/2020} \\
\item \note{Class 9, 2/25/2021}
\item Heap property: the value at a node is $\le$ the value of each child (for a
{\bf top-light heap}) or $\ge$ the value of each child (for a {\bf top-heavy heap}).
\item The smallest (largest) value is therefore at the root.
\item All leaves are at the same level $\pm1$.
\item To insert
	\begin{notelist}
	\item Place new value at ``end'' of tree.
	\item Let the new value sift up to its proper level.
	\end{notelist}
\item To delete: always delete the least (root) element
	\begin{notelist}
	\item Save value at root to return it later.
	\item Move the last value to the root.
	\item Let the new value sift down to its proper level.
	\end{notelist}
\item Storage
	\begin{notelist}
	\item Store the tree in an array [1 $\dots$ ]
	\item {\tt leftChild[index] = 2*index}
	\item {\tt rightChild[index] = 2*index+1}
	\item the last occupied place in the array is at index {\tt heapSize}.
	\end{notelist}
\item Applications
	\begin{notelist}
	\item Sorting
	\item Priority queue
	\end{notelist}
\end{notelist}
\begin{minipage}{4in} \begin{lstlisting}
// basic algorithms (top-light heap)
  
void siftUp (int heap[], int subjectIndex) {
   // the element in subjectIndex needs to be sifted up.
   heap[0] = heap[subjectIndex]; // pseudo-data
   while (1) { // compare with parentValue. 
      int parentIndex = subjectIndex / 2;
      if (heap[parentIndex] <= heap[subjectIndex]) return;
      swap(heap, subjectIndex, parentIndex);
      subjectIndex = parentIndex;
   }
} // siftUp
  
int betterChild (int heap[], int subjectIndex, int heapSize) {
   int answerIndex = subjectIndex * 2; // assume better child
   if (answerIndex+1 <= heapSize &&
         heap[answerIndex+1] < heap[answerIndex]) {
      answerIndex += 1;
	}
   return(answerIndex);
} // betterChild
  
void siftDown (int heap[], int subjectIndex, int heapSize) {
   // the element in subjectIndex needs to be sifted down.
   while (2*subjectIndex <= heapSize) {
      int childIndex = betterChild(heap, subjectIndex, heapSize);
      if (heap[childIndex] >= heap[subjectIndex]) return;
      swap(heap, subjectIndex, childIndex);
      subjectIndex = childIndex;
   }
} // siftUp
\end{lstlisting} \end{minipage}
 
\begin{minipage}{4in} \begin{lstlisting}
// intermediate algorithms
 
void insertInHeap (int heap[], int *heapSize, int value) {
   *heapSize += 1; // should check for overflow
   heap[*heapSize] = value;
   siftUp(heap, *heapSize);
} // insertInHeap
   
int deleteFromHeap (int heap[], int *heapSize) {
   int answer = heap[1];
   heap[1] = heap[*heapSize];
   *heapSize -= 1;
   siftDown(heap, 1, *heapSize);
   return(answer);
} // deleteFromHeap
\end{lstlisting} \end{minipage}
 
\begin{minipage}{4in} \begin{lstlisting}
// advanced algorithm
 
void heapSort(int array[], int arraySize){
	// sorts array[1..arraySize] by first making it a
	// top-heavy heap, then by successive deletion. 
	// Deleted elements go to the end.
   int index, size;
   array[0] = $-\infty$; // pseudo-data
   // The second half of array[] satisfies the heap property.
   for (index = (arraySize+1)/2; index > 0; index -= 1) {
      siftDown(array, index, arraySize);
   }
   for (index = arraySize; index > 0; index -= 1) {
      array[index] = deleteFromHeap(array, &arraySize);
   }
} // heapSort
\end{lstlisting} \end{minipage}
 
\begin{notelist}
\item This method of heapifying is \order{n}:
	\begin{notelist}
	% \item \note{Lecture 10, 2/18/2020} 
	\item 1/2 the elements require no motion.
	\item 1/4 the elements may sift down 1 level.
	\item 1/8 the elements may sift down 2 levels.
	\item Total motion = $(n/2) \cdot \sum_{1 \le j} j/2^j$
	\item That formula approaches $n$ as $j \rightarrow \infty$
	\end{notelist}
\item Total complexity is therefore $\mathcal{O}(n + n \log n) =
\mathcal{O}(n \log n)$.
\item This sorting method is not {\em stable}, because sifting does not preserve
order.
\end{notelist}
\medskip \noindent
Experimental results for Heap Sort:
compares + moves $\approx 3.1 n \log n$. \\
\begin{tabular}{r r r r r}
$n$ & compares & moves & $n \log n$ & $n^2/2$ \\
\hline
100  & 755   & 1190  & 664   & 5000    \\
200  & 1799  & 2756  & 1528  & 20000   \\
400  & 4180  & 6196  & 3457  & 80000   \\
800  & 9621  & 14050 & 7715  & 320000  \\
1600 & 21569 & 31214 & 17030 & 1280000 \\
\end{tabular} \\

\section{Bin sort}
\begin{notelist}
\item Assumptions: values lie in a small range; there are no duplicates.
\item Storage: build an array of bins, one for each possible value.  Each is 1
bit long.
\item Space: \order{r}, where $r$ is the size of the range.
\item Place each value to sort as a 1 in its bin.  Time: \order{n}.
\item Read off bins in order, reporting index if it is 1. Time:
\order{r}.
\item Total time: \order{n+r}.
\item Total memory: \order{r}, which can be expensive.
\item Can handle duplicates by storing a count in each bin, at a further expense
of memory.
\item This sorting method does not work for arbitrary data having numeric keys;
it only sorts the keys, not the data.
\end{notelist}

\section{Radix sort}
\begin{notelist}
\item Example: use base 10, with values integers 0 -- 9999, with 10 bins, each
holding a list of values, initially empty.
\item Pass 1: insert each value in a bin (at rear of its list) based on the last
digit of the value.
\item Pass 2: examine values in bin order, and in list order within bins,
placing them in a new copy of bins based on the second-to-last digit.
\item Pass 3, 4: similar.
\item The number of digits is \order{\log~n}, so there are
\order{\log n} passes, each of which takes \order{n} time, so the
algorithm is \order{n~\log~n}.
\item This sorting method is {\it stable}.
\end{notelist}

\section{Merge sort}
\begin{minipage}{4in} \begin{lstlisting}
void mergeSort(int array[], int lowIndex, int highIndex){
	// sort array[lowIndex] .. array[highIndex]
   if (highIndex - lowIndex < 1) return; // width 0 or 1
	int mid = (lowIndex+highIndex)/2;
   mergeSort(array, lowIndex, mid);
   mergeSort(array, mid+1, highIndex);
   merge(array, lowIndex, highIndex);
} // mergeSort
  
void merge(int array[], int lowIndex, int highIndex) {
	int mid = (lowIndex+highIndex)/2;
	// copy the relevant parts of array to two temporaries
	// walk through the temporaries in tandem,
	// placing smaller in array, ties honor left version.
} // merge
\end{lstlisting} \end{minipage} \\
\begin{notelist}
\item $c_n = n + 2 c_{n/2}$
\item $a=2$, $b=2$, $k=1$ $\Rightarrow$ \order{n \log n}.
\item This time complexity is {\bf guaranteed}.
\item Space needed: $2n$, because merge in place is awkward (and expensive).
\item The sort is also {\it stable}: it preserves the order of identical keys.
\item Insertion, radix, and merge sort are stable, but not selection, Quicksort or
Heapsort.
\end{notelist}

\noindent
Experimental results for Merge Sort:
compares + moves $\approx 2.9 n \log n$. \\
\begin{tabular}{r r r r r}
$n$ & compares & moves & $n \log n$ & $n^2/2$ \\
\hline
100  & 546   & 1344  & 664   & 5000    \\
200  & 1286  & 3088  & 1528  & 20000   \\
400  & 2959  & 6976  & 3457  & 80000   \\
800  & 6741  & 15552 & 7715  & 320000  \\
1600 & 15017 & 34304 & 17030 & 1280000 \\
\end{tabular} \\

\section{Red-black trees (Guibas and Sedgewick 1978)} 
\begin{notelist}
\item \note{Class 10, 3/2/2021}
% \item \note{Lecture 11, 2/20/2020} 
\item Red-black trees balance themselves during online insertion.
\item Their representation requires pointers both to children and to the parent.
\item Each node is {\bf red} or {\bf black}.
\item The pseudo-nodes (or null nodes) at bottom are black.
\item The root node is black.
\item Red nodes have only black children.  So no path has two red nodes in a
row.
\item All paths from the root to a leaf have the same number of black nodes.
\item For a node x, define black-height(x) = number of black nodes on a path
down from x, not counting x.
\item The algorithm manages to keep height of the tree $\le 2 \log(n+1)$.
\item To keep the tree acceptable, we sometimes {\bf rotate}, which reorganizes
the tree locally without changing the symmetric traversal. \\
\hspace*{1in}\psfig{figure=rotations.eps,height=1.0in}
\item To insert
	\begin{notelist}
	\item place new node \fbox{n} in the tree and color it red.
	\order{\log~n}.
	\item walk up the tree from \fbox{n}, rotating as needed to restore color rules.
	\order{\log~n}.
	\item color the root black.
	\end{notelist}
\psfig{figure=redblack.eps,height=5.0in}
\item try with values 1..6:
\end{notelist}
\psfig{figure=redblack1-6.eps,height=3.5in}
\begin{notelist}
\item try with these values: 5, 2, 7, 4 (case 1), 3 (case 2), 1 (case 1) 
\end{notelist}

\section{Review of binary trees}
\begin{notelist}
%\item \note{Lecture 10, 2/12/2019}
\item Binary trees have expected \order{\log~n} depth, but they
can have \order{n} depth.
\item insertion
\item traversal: preorder, postorder, inorder=symmetric order.
\item deletion of node D
	\begin{notelist}
	\item If D is a leaf, remove it.
	\item If D has one child C, move C in place of D.
	\item If D has two children, find its successor: S = $R L^*$.
	Move S in place of D.  S has no left child, but if it has a right child
	C, move C in place of S.
	\end{notelist}
\end{notelist}

\section{Ternary trees}
\begin{notelist}
\item \note{Class 11, 3/4/2021}
%\item \note{Lecture 8, 2/5/2019}
\item By example.
% \item \note{Lecture 12, 2/25/2020} 
\item The depth of a balanced ternary tree is $\log_3 n$, which is only 63\% the depth
of a balanced binary tree.
\item The number of comparisons needed to traverse an internal node during a search 
is either 1 or 2; average 5/3.
\item So the number of comparisons to reach a leaf is ${5 \over 3} \log_3 n$ instead of
(for a binary tree) $\log_2 n$, a ratio of 1.05, indicating a 5\% degradation.
\item The situation gets only worse for larger arity.  For quaternary trees, the
degradation (in comparison to binary trees) is about 12.5\%.
\item And, of course, an online construction is not balanced.
\item Moral: binary is best; higher arity is not helpful.
\end{notelist}

\section{Quad trees (Finkel 1973)}
\begin{notelist}
\item Extension of sorted binary trees to two dimensions.
\item Internal nodes contain a {\bf discriminant}, which is a two-dimensional
(x,y) value.
\item Internal nodes have four children, corresponding to the four quadrants
from the discriminant.
\item Leaf nodes contain a {\bf bucket} of $b$ values.
\item Insertion
	\begin{notelist}
	\item Dive down the tree, put new value in its bucket.
	\item If the bucket overflows, pick a good discriminant and subdivide.
	\item Good discriminant: one that separates the values as evenly as
	possible.  Suggestion: median (x, y) values.
	\end{notelist}
\item Offline algorithm to build a balanced tree
	\begin{notelist}
	\item Put all elements in a single bucket, then recursively subdivide as
	above.
	\end{notelist}
\item Generalization: for $d$-dimensional data, let each discriminant have $d$
values.  A node can have up to $2^d$ children.  This number becomes cumbersome
when $d$ grows above about 3.
\item Heavily used in 3-d modeling for graphics, often with discriminant chosen
as midpoint, not median.
\end{notelist}

\section{k-d trees (Bentley and Finkel 1973)}
\begin{notelist}
\item Extension of sorted binary trees to $d$ dimensions.
\item Especially good when $d$ is high.
\item Internal nodes contain a {\bf dimension} number ($0 ~..~ d-1$) and a {\bf
discriminant} value (real).
\item Internal nodes have two children, corresponding to values $\le$ and $>$
the discriminant in the given dimension.
\item Leaf nodes contain a {\bf bucket} of $b$ values.
\item Offline construction and online insertion are similar to quad trees.
	\begin{notelist}
	\item To split a bucket of values, pick the dimension number with the largest
	range across those values.
	\item Given the dimension, pick the median of the values in that dimension
	as the discriminant.
	\item That choice of dimension number tends to make the domain of each
	bucket roughly cubical; that choice of discriminant balances the
	tree.
	\end{notelist}
\item Nearest-neighbor search:  Given a $d$-dimensional probe value $p$, to
find the nearest neighbor to $p$ that is in the tree.
	\begin{notelist}
	\item Dive into the tree until you find $p$'s bucket.
	\item Find the closest value in the bucket to $p$.  Cost: $b$ distance
	measures.  Result: a {\bf ball} around $p$.
	\item Walking back up to the root, starting at the bucket:
		\begin{notelist}
		\item If the domain of the other child of the node overlaps the ball,
		dive into that child.
		\item If the ball is entirely contained within the node's domain, done.
		\item Otherwise walk one step up toward the root and continue.
		\end{notelist}
	\item complexity: Initial dive is \order{n}, but the expected number
	of buckets examined is \order{1}.
	\end{notelist}
\item Used for cluster analysis, categorizing (as in optical character
recognition).
\end{notelist}

\section{2-3 trees (John Hopcroft, 1970)}
\begin{notelist}
\item \note{Class 12, 3/9/2021}
\item By example.
\item Like a ternary tree, but different rule of insertion
\item Always completely balanced
\item A node may hold 1, 2, or 3 (temporarily) values.
\item A node may have 0 (only leaves), 2, 3, or 4 (temporarily) children.
\item A node that has 3 values splits and promotes its middle value to its
parent (recursively up the tree).
\item If the root splits, it promotes a new root.
\item Complexity: \order{n \log n} for insertion and search, guaranteed.
\item Deletion: unpleasant.  
\end{notelist}

\section{Stooge Sort}
\begin{notelist}
\item A terrible method, but fun to analyze.
\item 
\begin{minipage}{4in} \begin{lstlisting}
#include <math.h>

void stoogeSort(int array[], int lowIndex, int highIndex){
	// highIndex is one past the end
	int size = highIndex - lowIndex;
	if (size <= 1) { // nothing to do
	} else if (size == 2) { // direct sort
		if (array[lowIndex] > array[lowIndex+1]) {
			swap(array, lowIndex, lowIndex+1);
		}
	} else { // general case
		float third = ((float) size) / 3.0;
		stoogeSort(array, lowIndex, ceil(highIndex - third));
		stoogeSort(array, floor(lowIndex + third), highIndex);
		stoogeSort(array, lowIndex, ceil(highIndex - third));
	}
} // stoogeSort
\end{lstlisting} \end{minipage}
% \item \note{Lecture 13, 2/27/2020} 
\item $c_n = 1 + 3 c_{2 n / 3}$
\item $a = 3$, $b = 3/2$, $k = 0$, so $b ^ k = 1$.  By the recursion theorem 
(page \ref{recursionTheorem}), since 
$a > b^{k}$, we have complexity
$\Theta(n^{log_b a})$ =
$\Theta(n^{log_{3/2} 3}) \approx \Theta(n ^ {2.71})$, so Stooge Sort is worse than
quadratic.
\item However, the recursion often encounters already-sorted sub-arrays.  If we
add a check for that situation, Stooge Sort becomes roughly quadratic.
\end{notelist}

\section{B trees (Ed McCreight 1972)}
\begin{notelist}
%\item  \note{Lecture 12, 2/19/2019}
\item A generalization of 2-3 trees when McCreight was at Boeing,
hence the name.
\item Choose a number $m$ (the {\bf bucket size}) such that $m$ values plus $m$
disk indices fit in a single disk block.  For instance, if a block is 4KB, a
value takes 4B, and an index takes 4B, then $m = 4 {\rm KB}/8 {\rm B} = 512$.
\item $m=3 \Rightarrow$ 2-3 tree.
\item \note{Class 13, 3/11/2021}
\item Each node has $1 ~..~ m-1$ values and $0 ~..~ m$ children.
(We have room for $m$ values; the extra can be used for pseudo-data.)
\item Shorthand: $g = \lceil m/2 \rceil$ (the {\bf half size})
\item Internal nodes (other than the root) have $g ~..~ m$ children.
\item Insertion
	\begin{notelist}
	\item Insert in appropriate leaf.
	\item If current node overflows (has $m$ values) split it into two
	nodes of $g$ values each; hoist the middle value up one level.
	\item When a node splits, its parent's pointer to it becomes two pointers
	to the new nodes.
	\item When a value is hoisted, iterate up the tree checking for overflow.
	\end{notelist}
\item B+ tree variant: link leaf nodes together for quicker inorder traversal.
This link also allows us to avoid splitting a leaf if its neighbor is not at
capacity.
\item  A densely filled tree with $n$ keys (values), height $h$:
	\begin{notelist}
	\item Number of nodes $a = 1 + m + m^2 + \cdots + m^h =
		\frac {m^{h+1}-1} {m-1}$.
	\item Number of keys $n = (m-1)a = {m^{h+1}-1} \Rightarrow
		\log_m(n+1) = h+1 \Rightarrow h$ is \order{\log~n}.
	\end{notelist}
\item A sparsely filled tree with $n$ keys (values), height $h$:
	\begin{notelist}
	\item The root has two subtrees; the others have $g = \lceil m/2 \rceil$
	subtrees, so:
	\item Number of nodes $a = 1 + 2(1+g+g^2 + \cdots + g^{h-1}) =
		1 + \frac {2(g^h-1)} {g-1}$.
	\item The root has 1 key, the others have $g-1$ keys, so:
	\item Number of keys $n = 1 + 2(g^h-1) = 2g^h-1
		\Rightarrow h = \log_g (n+1)/2 = \mathcal{O}(\log~n)$.
	\end{notelist}
\end{notelist}

\section{Deletion from a B tree}
\begin{notelist}
\item Deletion from an internal node: replace value with successor (taken from a
leaf), and then proceed to deletion from a leaf.
\item Deletion from a leaf: the bad case is that it can cause {\bf underflow}:
the leaf now has fewer than $g$ keys.
\item In case of underflow, borrow a value from a neighbor if possible,
adjusting the appropriate key in the parent.
\item If all neighbors (there are 1 or 2) are already minimal, grab a key from
the parent and also {\bf merge} with a neighbor.
\item In general, deletion is quite difficult.
\end{notelist}

\section{Hashing}
\begin{notelist}
\item Very popular data structure for searching.
\item Cost of insertion and of search is \order{\log~n}, but only because
$n$ distinct values must be $\log~n$ bits long, and we need to look at the
entire key.  If we consider looking at a key to be \order{1}, then
hashing is expected (but not guaranteed) to be \order{1}.
\item Idea: find the value associated with key $k$ at {\tt A[$h(k)$]}, where
	\begin{notelist}
	\item $h()$ maps keys to integers in $0 .. s-1$, where $s$ is the size of
	A[\,].
	\item $h()$ is ``fast''.  (It generally needs to look at all of $k$,
	though.)
	\end{notelist}
\item Example
	\begin{notelist}
	\item $k$ = student in class.
	\item $h(k)$ = $k$'s birthday (a value from 0 .. 365).
	\end{notelist}
\item Difficulty: collisions
	\begin{notelist}
	\item Birthday paradox: Prob(no collisions with $j$ people) =
		$\frac {365!} {(365-j)! 365^j}$
	\item This probability goes below 1/2 at $j=23$.
	\item At $j=50$, the probability is 0.029.
	\end{notelist}
\item Moral: One cannot in general avoid collisions.  One has to deal with them.
\end{notelist}

\section{Hashing: Dealing with collisions: open addressing}
\begin{notelist}
\item Overview
	\begin{notelist}
	\item The following methods store all items in A[\,] and use a probe sequence.
	If the desired position is occupied, use some other position to consider
	instead.
	\item These methods suffer from clustering.
	\item Deletion is hard, because removing an element can damage unrelated
	searches.  Deletion by {\bf marking} is the only reasonable approach.
	\end{notelist}
\item Perfect hashing: if you know all $n$ values in advance, you can look
for a non-colliding hash function {\tt h}.  Finding such a function is in
general quite difficult, but compiler writers do sometimes use perfect hashing to
detect keywords in the language (like \codebold{if} and \codebold{for}).
\item Linear probing.  Probe $p$ is at index $h(k) + p$ (mod $s$), for
$p=0,~1,~\dots$.
	\begin{notelist}
	\item Terrible behavior when A[\,] is almost full, because chains coalesce.
	This problem is called ``primary clustering''.
	\end{notelist}
\item Additional hash functions.  Use a family of hash functions, $h_1(),~
h_2(), \dots$.
	\begin{notelist}
	\item insertion: key probing with different functions until an empty
	slot is found.
	\item searching: probe with different functions until you find the key 
	(success) or an empty slot (failure).
	\item You need a {\bf family} of independent hash functions.
	\item The method is very expensive when A[\,] is almost full.
	\end{notelist}
\end{notelist}

\section{Review for midterm}
\note{Class 14, 3/16/2021} \\
Insert the following items:
$3_1~1_1~4~1_2~5_1~9~2~6~5_2~3_2$
into:
\begin{notelist}
\item binary tree.  Preorder result:
	$3_1 ~ 1_1 ~ 1~2 ~ 2 ~ 3_2 ~ 5_1 ~ 5_2 ~ 9 ~ 6$
\item top-light heap.  Breadth-order result:
$1_1~1_2~2~3_1~3_2~9~4~6~5_2~5_1$
%\item  \note{Lecture 11, 2/14/2019}
\item array, then heapify.  Breadth-order result:
$1_1~1_2~2~3_1~3_2~9~4~6~5_2~5_1$
\item ternary tree. Preorder result:
$(1_1,3)~1_2~(2,3_2)~(4,5_1)~5_2~(6,9)$
\item array, then 5 steps of selection sort.  Result:
$1_1~1_2~2~3_1~3_2~|~9~4~6~5_2~5_1$
Note: not stable.
\item array, then 5 steps of insertion sort.  Result:
$1_1~1_2~3_1~4~5_1~|~9~2~6~5_2~3_2$
Note: stable.  Can force anti-stable.
\item array, then first step of Quicksort, using Lomuto's partitioning.
final insertionSort.
\item 2-3 tree.  Preorder result: $3~1~1~(2,3)~5~(4,5)~(6,9)$
% \item \note{Lecture 14, 3/3/2020} 
\item red-black tree.  Preorder result:
$3_b ~ 1 ~ 1_b ~ 2_b ~ 3 ~ 5 ~ 4_b ~ 5 ~ 9_b ~ 6$
\end{notelist}

\section{Midterm exam}
\note{Class 15, 3/18/2021}

\section{Midterm exam follow-up}
\note{Class 16, 3/23/2021}

\section{Hashing: more open-addressing methods}
\begin{notelist}
\item \note{Class 17, 3/25/2021}
\item Quadratic probing.  Probe $p$ is at index $h(k)+p^2$ (mod $s$), for
$p=0,~1,~\dots$.
	\begin{notelist}
	\item When does this sequence hit all of A[\,]?  Certainly it does if
	$s$ is prime.
	\item We still suffer ``secondary clustering'': if two keys have the
	same hash value, then the sequence of probes is the same for both.
	\end{notelist}
\item Add-the-hash rehash.  Probe $p$ is at index $(p+1)\cdot h(k)$ (mod $s$).
	\begin{notelist}
	\item This method avoids clustering.
	\item Warning: $h(k)$ must never be 0.
	\end{notelist}
% \item \note{Lecture 15, 3/5/2020} Midterm
% \item \note{Lecture 16, 3/10/2020} Review after midterm
% \item \note{Lecture 17, 3/12/2020}
\item Double hashing.  Use two has functions, $h_1()$ and $h_2()$.  Probe
$p$ is at index $h_1(k) + p \cdot h_2(k)$.
	\begin{notelist}
	\item This method avoids clustering.
	\item Warning: $h_2(k)$ must never be 0.
	\end{notelist}
\end{notelist}

\section{Hashing: Dealing with collisions: external chaining}
\begin{notelist}
\item Each element in A is a pointer, initially null, to a {\bf bucket}, which
is a linked list of nodes that hash to that element; each node contains $k$ and
any other associated data.
\item insert: place $k$ at the front of A[$h(k)$].
\item search: look through the list at A[$h(k)$].
	\begin{notelist}
	\item optimization:  When you find, promote the node to the start of its
	list.
	\end{notelist}
\item average list length is $s/n$.  So if we set $s \cong n$ we expect about 1
element per list, although some may be longer, some empty.
\item Instead of lists, we can use something fancier (such as 2-3 trees), but it
is generally better to use a larger $s$.
\end{notelist}

\section{Hashing: What is a good hash function?}
\begin{notelist}
\item Want it to be
	\begin{notelist}
	\item Uniform: Equally likely to give any value in $0 .. s-1$.
	\item Fast.
	\item Spreading: similar inputs $\rightarrow$ dissimilar outputs, to prevent
	clustering. (Only important for open addressing, as described below.)
	\end{notelist}
%\item  \note{Lecture 13, 2/21/2019}
\item Several suggestions, assuming that $k$ is a multi-word data structure,
such as a string.
	\begin{notelist}
	\item Add (or multiply) all (or some of) the words
	of $k$, discarding overflow, then mod by $s$.
	It helps if $s = 2^j$, because mod is then masking with $2^j-1$.
	\item {\tt XOR} the words of $k$, shifting left by 1 after each, followed by
	mod $s$.
	\end{notelist}
\item Wisdom: The hash function doesn't make much difference.  It is not
necessary to look at all of $k$.  Just make sure that $h(k)$ is
not constant (except for testing collision resolution). 
\end{notelist}

\section{Hashing: How big should the array be?}
\begin{notelist}
\item Some open-addressing methods prefer that $s = ||Array||$ be prime.
\item Computing $h()$ is faster if $s = 2^j$ for some $j$.
\item Open addressing gets very bad if $s < 2n$, depending on method.  Linear
probing is the worst; I would make sure $s \ge 3n$.
\item External chaining works fine even when $s \cong n$, but it gets steadily worse.
\end{notelist}

\section{Hashing: What should we do if we discover that $s$ is too small?}
\begin{notelist}
\item We can rebuild with a bigger $s$, rehashing every element.  But that
operation causes a temporary ``outage'', so it is not acceptable for online
work.
\item Extendible hashing
	\begin{notelist}
	\item Start with one bucket.  If it gets too full (list longer than 10,
	say), split it on the {\em last bit} of $h(k)$ into two buckets.
	\item Whenever a bucket based on the last $j$ bits is too full, split it
	based on bit $j+1$ from the end.
	\item To find the bucket
		\begin{notelist}
		\item compute $v = h(k)$.
		\item follow a tree that discriminates on the last bits of $v$.
		This tree is called a {\bf trie}.  
		\item it takes at most $\log~v$ steps to find the right bucket.
		\item Searching within the bucket now is guaranteed to take constant time
		(ignoring the $\log~n$ cost of comparing keys)
		\end{notelist}
	\end{notelist}
\end{notelist}

\section{Hash tables (associative arrays) in scripting languages}
\begin{notelist}
\item \note{Class 18, 3/30/2021}
\item Like an array, but the indices are strings.
\item Resizing the array is automatic, although one might specify the expected size
in advance to avoid resizing during early growth.
\item Perl has a built-in datatype called a {\bf hash}. \\
\begin{lstlisting}[language=Perl,literate={\$}{{\$}}1]
	my %foo;
	foo{"this"} = "that".
\end{lstlisting}
\item Python has {\bf dictionaries}. \\
\begin{lstlisting}[language=Python]
	Foo = dict()
	Foo['this'] = 'that';
\end{lstlisting}
\item JavaScript arrays are all associative. \\
\begin{lstlisting}[morekeywords={const}]
	const foo = [];
	foo['this'] = 'that';
	foo.this = 'that';
\end{lstlisting}
\end{notelist}

\section{Cryptographic hashes: {\bf digests}}
\begin{notelist}
%\item \note{Lecture 14, 2/26/2019}
\item purpose: uniquely identify text of any length.
\item these hashes are {\em not} used for searching.
\item goals
	\begin{notelist}
	\item fast computation
	\item uninvertable: given $h(k)$, it should be infeasible to compute $k$.
	\item it should be infeasible to find collisions $k_1$ and $k_2$ such that $h(k_1) =
	h(k_2)$.
	\end{notelist}
\item examples
	\begin{notelist}
	\item MD5: 128 bits.  Practical attack in 2008.
	\item SHA-1: 160 bits, but (2005) one can find collisions in
	$2^{69}$ hash operations (brute force would use $2^{80}$)
	\item SHA-2: usual variant is SHA256; also SHA-512.
	\end{notelist}
\item uses
	\begin{notelist}
	\item storing passwords (used as a trap-door function)
	\item catching plagiarism
	\item for authentication ($h(m+s)$ authenticates $m$ to someone who
	shares the secret $s$, for example)
	\item tripwire: intrusion detection
	\end{notelist}
\end{notelist}

\section{Graphs}
\begin{notelist}
% \item \note{Lecture 18, 3/24/2020}
\item Our standard graph: \\
\hspace*{1in}\psfig{figure=graph1.eps,height=1.2in}
\label{standard-graph}
%\item \note{Lecture 16, 3/7/2019}
\item Nomenclature
	\begin{notelist}
	\item {\bf vertices}: V is the name of the set, $v$ is the size of the set.
	In our example, V = \{1, 2, 3, 4, 5, 6, 7\}.
	\item {\bf edges}: E is the name of the set, $e$ is the size of the set.
	In our example, E = \{e1, e2, e3, e4, e5, e6, e7\}.
	\item {\bf directed graph}: edges have direction (represented by arrows).
	\item {\bf undirected graph}: edges have no direction.
	\item {\bf multigraph}: more than one edge between two vertices.  We
	generally do not deal with multigraphs, and the word {\bf graph} generally
	disallows them.
	\item {\bf weighted graph}: each edge has numeric label called its {\bf
	weight}.
	\end{notelist}
\item Graphs represent situations
	\begin{notelist}
	\item streets in a city.  We might be interested in computing {\bf paths}.
	\item airline routes, where the weight is the price of a flight.  We might
	be interested in minimal-cost cycles.
		\begin{notelist}
		\item Hamiltonian cycle: no duplicated vertices (cities).
		\item Eulerian cycle: no duplicated edges (flights).
		\end{notelist}
	\item Islands and bridges, as in the bridges of K\"onigsburg, later called
	Kaliningrad (Euler 1707-1783).  This is a multigraph, not strictly a graph.
	\\ \psfig{figure=koenigsburg.eps,height=2.0in} \\
	Can you find an Eulerian cycle?
	\bigskip
	\item Family trees.  These graphs are {\bf bipartite}: Family nodes and
	person nodes.  We might want to find the shortest path between two people.
	\item Cities and roadways, with weights indicating distance.  We might want
	a minimal-cost spanning tree.
	\end{notelist}
\end{notelist}

\section{Data structures representing a graph}
\begin{notelist}
\item Adjacency matrix
	\begin{notelist}
	\item an array $n \times n$ of Boolean.
	\item A[$i,j$] = true $\Rightarrow$ there is an edge from vertex $i$ to
	vertex $j$. \\
		\begin{tabular}{l | c c c c c c c}
		& 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
		\hline
		1 &   & x &   &   &   & x &   \\
		2 & x &   & x &   &   &   & x \\
		3 &   & x &   &   &   &   & x \\
		4 &   &   &   &   & x &   &   \\
		5 &   &   &   & x &   &   &   \\
		6 & x &   &   &   &   &   & x \\
		7 &   & x & x &   &   & x &   \\
		\end{tabular}
	\item The array is symmetric if the graph is undirected
		\begin{notelist}
		\item in this case, we can store only one half of it, typically in a 1-dimensional array
		\item A[$i(i-1)/2 ~+~j$] holds information about edge $i,j$.
		\end{notelist}
	\item Instead of Boolean, we can use integer values to store edge weights.
	\end{notelist}
\item Adjacency list
	\begin{notelist}
	\item an array $n$ of singly-linked lists.
	\item $j$ is in linked list A[$i$] if there is an edge from vertex $i$ to
	vertex $j$.

	\begin{tabular}{l | l}
		1 & $2 \rightarrow 6$ \\
		2 & $1 \rightarrow 3 \rightarrow 7$ \\
		3 & $2 \rightarrow 7$ \\
		4 & $5$ \\
		5 & $4$ \\
		6 & $1 \rightarrow 7$ \\
		7 & $2 \rightarrow 3 \rightarrow 6$
		\end{tabular}	\end{notelist}
\end{notelist}

\section{Computing the degree of all vertices}
\begin{notelist}
\item Adjacency matrix: \order{v^2}. \\
\begin{minipage}{4in} \begin{lstlisting}[morekeywords={foreach}]
foreach vertex (0 .. v-1) {
    degree[vertex] = 0;
    foreach neighbor in 0 .. v-1 {
        if (A[vertex, neighbor]) degree[vertex] += 1;
    }
}
\end{lstlisting} \end{minipage}
\item Adjacency list: \order{v+e}. \\
\begin{minipage}{4in} \begin{lstlisting}[morekeywords={foreach,null}]
foreach vertex (0 .. v-1) {
    degree[vertex] = 0;
    for (neighbor = A[vertex]; neighbor != null;
            neighbor = neighbor->next) {
        degree[vertex] += 1;
    }
}
\end{lstlisting} \end{minipage}
\end{notelist}

\section{Computing the connected component containing vertex $i$ in an undirected
graph}
\begin{notelist}
%\item \note{Lecture 17, 3/19/2019}
\item why: to segment an image.
\item \note{Class 19, 4/1/2021}
\item method: {\bf depth-first search} ({\bf DFS}). \\
\begin{minipage}{4in} \begin{lstlisting}[morekeywords={foreach,true}]
void DFS(vertex here) {
	// assume visited[*] == false at start
	visited[here] = true;
	foreach next (successors(here)) {
		if (! visited[next]) DFS(next);
	}
} // DFS
\end{lstlisting} \end{minipage}
\item DFS is faster with adjacency list: \order{e'+v'}, where $e'$, $v'$
only count to the number of edges and vertices in the connected component.
\item DFS is slower with adjacency matrix: \order{v+v'}.
\item For our standard graph (page \pageref{standard-graph}), assuming that the
adjacency lists are all sorted
by vertex number (or that we use the adjacency matrix), starting at vertex 1, we
invoke DFS on these vertices: 1, 2, 3, 7, 6.
% \item \note{Lecture 19, 3/26/2020}
\item DFS can be coded iteratively with an explicit stack \\
\begin{minipage}{4in} \begin{lstlisting}[morekeywords={foreach,true}]
void DFS(vertex start) {
   // assume visited[*] == false at start
   workStack = makeEmptyStack();
   pushStack(workStack, start)
   while (! isEmptyStack(workStack)) {
      place = popStack(workStack);
      if (visited[place]) continue;
      visited[place] = true;
      foreach neighbor (successors(place)) {
         if (! visited[neighbor]) {
            pushStack(workStack, neighbor);
            // could record "place" as parent
			} // "neighbor" is not yet visited
      } // foreach neighbor
   } // while workStack not empty
\end{lstlisting} \end{minipage}
\end{notelist}

\section{To see if a graph is connected}
\begin{notelist}
\item 
See if DFS hits every vertex. \\
\begin{minipage}{4in} \begin{lstlisting}[morekeywords={foreach,true,false}]
bool isConnected() {
	foreach vertex (vertices)
		visited[vertex] = false;
	DFS(0); // or any vertex
	foreach vertex (vertices)
		if (! visited[vertex]) return false;
	return true;
} // isConnected
\end{lstlisting} \end{minipage}
\end{notelist}

\section{Breadth-first search}
\begin{notelist}
\item applications
	\begin{notelist}
	\item find shortest path in a family tree connecting two people
	\item find shortest route through city streets
	\item find fastest itinerary by plane between two cities
	\end{notelist}
\item method: place unfinished vertices in a queue.  These are the ones we still
need to visit, in order closest to furthest. \\
\begin{minipage}{4in} \begin{lstlisting}[morekeywords={foreach,true,false}]
void BFS(vertex start) {
   // assume visited[*] == false at start
   workQueue = makeQueue();
   visited[start] = true;
   insertInQueue(workQueue, start)
   while (! emptyQueue(workQueue)) {
		place = deleteFromQueue(workQueue); // from front
		foreach neighbor (successors(place)) {
			if (! visited[neighbor]) {
				visited[neighbor] = true;
				insertInQueue(workQueue, neighbor); // to rear
				// or: insert (place, neighbor)
				// to remember path to start
			} // not visited
		} // foreach neighbor
   } // while queue not empty
} // BFS
\end{lstlisting} \end{minipage}
\item For our standard graph (page \pageref{standard-graph}), assuming that the
adjacency lists are all sorted
by vertex number (or that we use the adjacency matrix), starting at vertex 1,
BFS visits these vertices: 1, 2, 6, 3, 7.
\item using adjacency lists, BFS is \order{v'+e'}.
\end{notelist}

\section{Shortest path between vertices $i$ and $j$}
\begin{notelist}
\item Compute BFS($i$), but stop when you visit $j$.
	\begin{notelist}
	\item Actually, you can stop when you place $j$ in the queue.
	\item Construct the path by building a back chain when you insert a vertex in
	the queue.  That is, you insert a pair: {\tt (place, neighbor)}.
	\end{notelist}
\item If edges are weighted:
	\begin{notelist}
	\item Use a heap (top-light) instead of a queue.  That's why heaps are
	sometimes called {\bf priority queues}.
	\item stop when you visit $j$, not when you place $j$ in the queue. \\
	\end{notelist}
\item \note{Class 20, 4/6/2021}
\end{notelist}
\begin{minipage}{4in} \begin{lstlisting}[morekeywords={foreach,in,true,false}]
void weightedBFS(vertex start, vertex goal) {
   // assume visited[*] == () at start
   workHeap = makeHeap(); // top-light
   insertInHeap(workHeap, (0, start, start));
		// distance, vertex, from where
   while (! emptyHeap(workHeap)) {
		(distance, place, from) = deleteFromHeap(workHeap);
		if (visited[place] != ()) continue; // already seen 
		visited(place) = (from, distance);
		if (place == goal) return; // could print path
		foreach (neighbor, weight) in (successors(place)) {
			insertInHeap(workHeap, (distance+weight, neighbor, place));
		} // foreach neighbor
	} // while queue not empty
} // BFS
\end{lstlisting} \end{minipage}

\section{Dijkstra's algorithm: Finding all shortest paths from a given vertex in a
weighted graph}
The weights must be positive.
\fbox{Weiss \S9.3.2}
\begin{notelist}
\item Rule: among all vertices that can extend a shortest path already
found, choose the one that results in a shortest path.  If there is a tie
ending at the same vertex, choose either.  If there is a tie going to different
vertices, choose both.
\item This is an example of a {\bf greedy algorithm}: at each step, improve the
solution in the way that looks best at the moment.
\item Starting position: one path, length 0, from start vertex $j$ to $j$.
\\
\psfig{figure=dijkstra.eps,height=2.0in}
\begin{tabular}{l r l}
path & length \\
\hline
5 & $\rightarrow$ 0 \\
\hline
5 6 & $\rightarrow$ 40 \\
5 3 & 120 \\
5 1 & 60 \\
\hline
5 1 & $\rightarrow$ 60 \\
5 6 3 & 100 & better way to add vertex 3\\
5 6 4 & 160 \\
\hline
5 1 2 & 140 \\
5 6 3 & $\rightarrow$ 100 \\
5 6 4 & 160 \\
\hline
5 1 2 & 140 \\
5 6 3 4 & $\rightarrow$ 120 & better way to add vertex 4\\
\end{tabular}
\item Another example:\\ \psfig{figure=dijkstra-1.eps,height=1.4in}
Start at 1.
\begin{tabular}{l r l}
path & length \\
\hline
1 & $\rightarrow$ 0 \\
\hline
1 2 & $\rightarrow$ 3 \\
1 4 & $\rightarrow$ 3 \\
\hline
1 2 3 & $\rightarrow$ 4 \\
1 2 5 & 7 \\
1 4 3 & 5 \\
1 4 5 & 6 \\
\hline
1 2 5 & 7 \\
1 4 5 & 6 \\
1 2 3 5 & $\rightarrow$ 5 \\
\end{tabular}
\end{notelist}

\section{Topological sort}
\begin{notelist}
%\item \note{Lecture 18, 3/21/2019}
% \item \note{Lecture 20, 3/31/2020}
\item Sample application: course prerequisites place some pairs of courses in
order, leading to a {\bf directed, acyclic graph (DAG)}.  We want to find a
{\bf total order}; there may be many acceptable answers.
\item \fbox{Weiss \S9.2} \\
\hspace*{1in}\psfig{figure=dag.eps,height=1.5in}
\hspace*{0.4in}\psfig{figure=topSort.eps,height=2.0in}
\\ Possible results: \\
\begin{minipage}{4in} \begin{lstlisting}
    4 10 1 2 6 5 7 8 3 9
    10 4 7 1 2 5 8 6 3 9
\end{lstlisting} \end{minipage}
\item method: DFS looking for sinks (degrees with fanout 0), which are then
placed at the front of the growing result. \\
\begin{minipage}{4in} \begin{lstlisting}[morekeywords={foreach,true,false}]
list answerList; // global
 
void topologicalSort () { // computes answerList
   foreach j (vertices) visited[j] = false;
   answerList = makeEmptyList();
   foreach j (vertices)
      if (! visited[j]) tsRecurse(j);
} // topologicalSort
 
void tsRecurse(vertex here) { // adds to answerList
   visited[here] = true;
   foreach next (successors(here)) 
      if (! visited[next]) tsRecurse(next);
   insertAtFront(answerList, here);
} // tsRecurse
\end{lstlisting} \end{minipage}
\end{notelist}

\section{Spanning trees}
\begin{notelist}
% \item \note{Lecture 21, 4/2/2020}
%\item \note{Lecture 19, 3/26/2019}
\item \note{Class 21, 4/8/2021}
\item \fbox{Weiss \S9.5}
\item {\bf Spanning tree}: Given a connected undirected graph, a cycle-free
connected subgraph containing all the original vertices. \\
\hspace*{0.4in}\psfig{figure=span.eps,height=2.0in}
\item {\bf Minimum-weight panning tree}: Given a connected undirected
weighted graph, a spanning tree with least total weight.
\item Example: minimum-cost set of roads (edges) connecting a set of cities
(vertices).
\end{notelist}

\section{Prim's algorithm}
\begin{minipage}{4in} \begin{lstlisting}[morekeywords={times}]
Start with any vertex as the current tree.
do $v-1$ times
   connect the current tree to the closest external vertex 
\end{lstlisting} \end{minipage}
\begin{notelist}
\item This is a {\bf greedy algorithm}: at each step, improve the
solution in the way that looks best at the moment.
\item Example: start with 5.  We add:
    (5,6), (5,1), (1,3), (3, 4), (1, 2)
\item Implementation
    \begin{notelist}
	 \item Keep a top-light heap of all external vertices based on their distance
	 to the current tree (and store to which tree vertex they connect at that
	 distance).
    \item Initially, all distances are $\infty$ except for the neighbors of the
	 starting vertex.
    \item Repeatedly take the closest vertex $f$ and add its edge to the current
    tree.
    \item For all external neighbors $b$ of $f$, perhaps $f$ is a better way to
    connect $b$ to the tree; if so, update $b$'s information in the heap.
	 (Remove $b$ and reinsert it with the better distance.)
    \end{notelist}
\item Complexity: \order{v \cdot \log v + e}, because for we add each vertex once,
removing it from a heap that can have $v$ elements; we need to consider each
edge twice (once from each end).
\end{notelist}

\section{Kruskal's algorithm}
\begin{minipage}{4in} \begin{lstlisting}[morekeywords={times}]
Start with all vertices, no edges.
do $v-1$ times
   add the lowest-cost missing edge that does not form a cycle
\end{lstlisting} \end{minipage}
\begin{notelist}
\item This is a {\bf greedy algorithm}: at each step, improve the
solution in the way that looks best at the moment.
\item We can stop when we have added $v-1$ edges; all the rest will certainly
introduce cycles.
\item Data representation: List of edges, sorted by weight
\item Complexity: assuming that keeping track of the component of each vertex is
\order{\log^* v}, the complexity is
\order{e \log e ~ + v \log^* v}, because we must sort the edges and then
add $v-1$ edges.
\end{notelist}

\section{Cycle detection: Union-find}
\begin{notelist}
\item general idea
	\begin{notelist}
	\item As edges are added, keep track of which connected componenent every
	vertex belongs to.
	\item Any new edge connecting vertices already in the same component would
	form a cycle; avoid adding such edges.
	\end{notelist}
\item operations
	\begin{notelist}
	\item Each vertex starts as a separate component.
	\item union(b,c): assign b and c to the same component (for instance, when
	an edge is introduced between them).
	\item find(b): tell which component b is in (if b and c are in the same
	component, don't add an edge connecting them).
	\end{notelist}
\item method for union(b,c)
    \begin{notelist}
    \item Every vertex has at most one {\bf parent}, initially nil.
	 \item Find the {\bf representative} b' of b by following parent links until
	 the end.
	 \item Find the representative c' of c.
	 \item If b' = c', they are already in the same component.  Done.
	 \item Point either b' to c' or c' to b' by introducing a parent link
	 between them.
    \item We want trees to be as shallow as possible. So record the height of
    each tree in its root.  Point the shallower one at the deeper one.
	 \item We can compress paths while searching for the representative.  In
	 this case, the height recorded in the root is just an estimate.
    \end{notelist}
%\item \note{Lecture 20, 3/28/2019}
\item We use this data structure in Kruskal's algorithm to avoid cycles: \\
\begin{minipage}{4in} \begin{lstlisting}
typedef struct vertex_s {
   int name; // need not be int
   struct vertex_s *representative; // NULL => me
   int depth; // only if I represent my group; 0 initially
} vertex_t;
\end{lstlisting} \end{minipage}
\item \note{Class 22, 4/13/2021}
\item More examples of Union-Find
\end{notelist}

\section{Numerical algorithms}
\begin{notelist}
% \item \note{Lecture 22, 4/7/2020}
\item We will not look at algorithms for approximation to problems using real
numbers; that is the subject of CS321.
\item We will study integer algorithms.
\end{notelist}

\section{Euclidean algorithm: greatest common divisor (GCD)}
\begin{notelist}
\item Examples: gcd(12,60)=12, gcd(15,66)=3, gcd(15,67)=1. \\
\begin{minipage}{4in} \begin{lstlisting}
int gcd(a, b) {
   while (b != 0) {
      (a,b) = (b, a % b);
	}
   return(a);
} // gcd
\end{lstlisting} \end{minipage}
\item Example:
\begin{tabular}{c | r r r}
a & 12 & 60 & 12 \\
b & 60 & 12 & 0
\end{tabular}
\item Example:
\begin{tabular}{c | r r r r r }
a & 15 & 66 & 15 & 6 & 3 \\
b & 66 & 15 & 6 & 3 & 0
\end{tabular}
\item Example:
\begin{tabular}{c | r r r r r }
a & 15 & 67 & 15 & 7 & 1 \\
b & 67 & 15 & 7 & 1 & 0
\end{tabular}
\end{notelist}

\section{Fast exponentiation}
\begin{notelist}
\item Many cryptographic algorithms require raising large integers (thousands
of digits) to very large powers (hundreds of digits), modulo a large number
(about 2K bits).
\item to get $a^{64}$ we only need six multiplications:
$(((((a^2)^2)^2)^2)^2)^2$
\item to get $a^5$ we need three multiplications:
$a^4 \cdot a ~=~ (a^2)^2 \cdot a$.
\item General rule to compute $a^e$: look at the binary representation of $e$,
read it from left to right.  The initial accumulator has value 1.
    \begin{notelist}
    \item 0: square the accumulator
    \item 1: square the accumulator and multiply by $a$.
    \end{notelist}
\item Example: $a^{11}$.  In binary, $11_{10}$ is expressed as $1011_2$.  So we get \\
$((((1^2)a)^2)^2 \cdot a)^2 \cdot a$, a total of 4 squares and 3
multiplications, or 7 operations.  The first square is always $1^2$ and the
first multiplication is $1 \cdot a$; we can avoid those trivial operations.
\item In cryptography, we often need to compute $a^e ~ (\bmod~p)$.  Calculate this
quantity by performing $\bmod~p$ after each multiplication.
\item As we read the binary representation of $e$ from left to right, we could
start with the leading 0's without any harm. 
\item Example (run with the {\em bc} calculator program): $243^{745} \bmod 452$.
$745_{10} = 1011101001_{2}$.\\
\begin{minipage}{4in} \begin{lstlisting}
a = 243
m = 452
r = 1
r = r^2*a % m
r = r^2 % m
r = r^2*a % m
r = r^2*a % m
r = r^2*a % m
r = r^2 % m
r = r^2*a % m
r = r^2 % m
r = r^2 % m
r = r^2*a % m
r
\end{lstlisting} \end{minipage}
\end{notelist}

\section{Integer multiplication}
\begin{notelist}
\item \note{Class 23, 4/15/2021}
%\item \note{Lecture 21, 4/2/2019}
\item The BigNum representation: linked list of pieces, each with, say, 2 bytes
of unsigned integer, with least-significant piece first.
(It makes no difference whether we store those 2 bytes in little-endian or
big-endian.)
\item Ordinary multiplication of two $n$-digit numbers $x$ and $y$ costs
$n^2$.
% \item \note{Lecture 23, 4/14/2020}
\item Anatoly Karatsuba (1962) showed a {\bf divide-and-conquer} method that is
better.
	\begin{notelist}
	\item Split each number into two chunks, each with $n/2$ digits:
		\begin{notelist}
		\item $x = a \cdot 10^{n/2} + b$
		\item $y = c \cdot 10^{n/2} + d$
		\end{notelist}
	The base $10$ is arbitrary; the same idea works in any base, such as $2$.
	\item Now we can calculate
	$x y = a c 10^n + (bc + ad)10^{n/2} + bd$.
	This calculation uses four multiplications, each costing $(n/2)^2$, so it
	still costs $n^2$.
	All the additions and shifts (multiplying by powers of 10) cost just
	\order{n}, which we ignore.
	\item We can use the Recursion Theorem (page \pageref{recursionTheorem}~):
	$c_n = n + 4 c_{n/2}$.  Then $a=4$, $b=2$, $k=1$, so $a > b^k$, so 
	$c_n = \Theta(n^{log_b(a)}) = \Theta(n^{log_2(4)}) = \Theta(n^2)$.
	\item But we can introduce $u = ac$, $v = bd$, and $w = (a+b)(c+d)$ at a cost
	of $(3/4)n^2$.
	\item Now $xy = u 10^n + (w - u - v)10^{n/2} + v$, which costs no further
	multiplications. 
	\item Example
		\begin{notelist}
		\item $x=3962$, $y=4481$
		\item $a=39$, $b=62$, $c=44$, $d=81$
		\item $u=ac=1716$, $v=bd = 5022$, $w = (a+b)(c+d) = 12625$
		\item $w-u-v = 5887$
		\item $xy = 17753722$.
		\end{notelist}
	\item In {\em bc}: \\
\begin{minipage}{4in} \begin{lstlisting}
x = 3962
y = 4481
a = 39
b = 62
c = 44
d = 81
u = a*c
v = b*d
w = (a+b)*(c+d)
x * y
u*10^4 + (w-u-v)*10^2 + v
\end{lstlisting} \end{minipage}
	\item We can apply this construction recursively.
	$c_n = n + 3 c_{n/2}$.  We can again apply the Recursion Theorem (page
	\pageref{recursionTheorem}~):
		$a = 3$, $b = 2$, $k = 1$, so
		$a > b^k$, so $c_n = \Theta(n^{\log_b a}) = \Theta(n^{\log_2 3}) 
			\approx \Theta(n^{1.585})$.
\item For small $n$, this improvement is small.  But for $n=100$, we reduce the
	cost from $10,000$ to about $1480$.  Running {\tt bc -l}:
	\begin{lstlisting}
	power=l(3)/l(2)
	a=100
	e(power*l(a))
	\end{lstlisting}
    \end{notelist}
\begin{minipage}{4in} \begin{lstlisting}
bigInt bigMult(bigInt x, y; int n) {
	// n-chunk multiply of x and y
   bigInt a, b, c, d, u, v, w;
   if (n == 1) return(toBigInt(toInt(x)*toInt(y)));
   a = extractPart(x, 0, n/2 - 1); // high part of x
   b = extractPart(x, n/2, n-1); // low part of x
   c = extractPart(y, 0, n/2 - 1); // high part of y
   d = extractPart(y, n/2, n-1); // low part of y
   u = bigMult(a, c, n/2); // recursive
   v = bigMult(b, d, n/2); // recursive
   w = bigMult(bigAdd(a,b), bigAdd(c,d), n/2); // recursive
   return(
      bigAdd(
         bigShift(u, n),
         bigAdd(
            bigShift(bigSubtract(w, bigAdd(u,v)), n/2),
            v
         ) // add
      ) // add
   );
}
\end{lstlisting} \end{minipage}
\end{notelist}

\section{Strings and pattern matching --- Text search problem}
\begin{notelist}
\item \note{Class 24, 4/20/2021}
%\item \note{Lecture 22, 4/4/2019}
\item The problem: Find a match for pattern $p$ within a text $t$, where $|p|=m$
and $|t| = n$.
\item Application: $t$ is a long string of bytes (a ``message''), and $p$
is a short string of bytes (a ``word'').
\item We will look at several algorithms; there are others.
    \begin{notelist}
    \item Brute force: \order{m n}.  Typical: $1.1 n$ (operations).
    \item Rabin-Karp: \order{n}.  Typical: $7 n$.
    \item Knuth-Morris-Pratt: \order{n} Typical: $1.1 n$.
	 \item Boyer-Moore: worst \order{m n}. Typical: $n/m$.
    \end{notelist}
\item Non-classical version: approximate match, regular expressions, more
complicated patterns.
\end{notelist}

\section{Text search --- brute force algorithm}
\begin{notelist}
\item Return the smallest index $j$ such that $t[j ~..~ j + m - 1] = p$, or $-1$
if there is no match. \\
\hspace*{-.7in}\begin{minipage}{4in} \begin{lstlisting}
int bruteSearch(char *t, char *p) {
	// returns index in t where p is found, or -1
   const int n = strlen(t);
   const int m = strlen(p);
   int tIndex = 0;
   p[m] = 0xFF; // impossible character; pseudo-data
   while (tIndex+m <= n) { // there is still room to find p
      int pIndex = 0;
      while (t[tIndex+pIndex] == p[pIndex]) // enlarge match
         pIndex += 1;
      if (pIndex == m) return(tIndex); // hit pseudo-data
      tIndex += 1;
   } // there is still room to find p
   return(-1); // failure
} // bruteSearch
\end{lstlisting} \end{minipage}
\item Example: p = "001", t = "010001".
\item Worst case: \order{(n-m)m} = \order{nm}
\item If the patterns are fairly random, we observe complexity
\order{n-m} = \order{n}; in practice, complexity is about $1.1 n$.
\end{notelist}

\section{Text search --- Rabin-Karp}
\begin{notelist}
\item Michael Rabin, Richard Karp (1987)
\item The idea is to do a preliminary hash-based
check each time we increment {\tt tIndex}
and skip this value of {\em tIndex} if there is no chance that this position works.
% \item \note{Lecture 24, 4/21/2020}
\item Problem: how can we avoid $m$ accesses to compute the hash of the next
piece of $t$?
\item We will start with {\bf fingerprinting}, a weak version of the final
method, just looking at
parity, and assuming the strings are composed of 0 and 1 characters.
\item The parity of a string of 0 and 1 characters is 0 if the number of 1
characters is even; otherwise the parity is 1.
\item Formula: parity $= \sum_j p[j] \pmod{2}$.
\item We can compute the parities of windows of $m(=6)$ bits in $t$.  For
example, \\
% \fbox{Johnsonbaugh and Schaefer p. 372}
\hspace*{-.5in}
{\small \begin{tabular}{c | r r r r r r r r r r r r r r r r r r r}
$j$           & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 &  14 & 15 & 16 & 17 & 18 \\
$t$           & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0  & 0  & 1  & 0  &  1  & 0  & 0  & 1  & 1  \\
{\tt tParity} & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0  & 0  & 1  & 1  &
\end{tabular} }
\item Say that $p = 010111$, which has {\tt pParity} $ =  0$.  We only need to consider
matches starting at positions 2, 4, 6, 8, 10, and 11.
\item We have saved half the work.
\item We can calculate {\tt tParity} quickly as we move $p$ by looking at
	 only 2, not $p$, characters of $t$:
    \begin{notelist}
    \item Initially, ${\tt tParity}_0 = \sum_{0 \le j < m} t[j] \pmod{2}$.
    \item Then, ${\tt tParity}_{j+1} = {\tt tParity}_j + t[j] + t[j+m] \pmod{2}$
    \end{notelist}
\hspace*{-.7in}\begin{minipage}{4in} \begin{lstlisting}[morekeywords={bit}]
bit computeParity(bit *string, int length) {
	bit answer = 0;
	for (int index = 0; index < length; index += 1) {
		answer += string[index];
	}
	return (answer & 01);
} // computeParity

int fingerprintSearch(bit *t, bit *p) {
   const int n = strlen(t);
   const int m = strlen(p);
   const int pParity = computeParity(p, m); 
   int tParity = computeParity(t, m); // initial substring
   int tIndex = 0;
   while (tIndex+m <= n) { // there is still room to find p
      if (tParity == pParity) { // parity check ok
         int pIndex = 0;
         while (t[tIndex+pIndex] == p[pIndex]) { // enlarge match
            pIndex += 1;
            if (pIndex >= m) return(tIndex);
         } // enlarge match
      } // parity check ok
      tParity = (tParity + t[tIndex] + t[tIndex+m]) & 01;
      tIndex += 1;
   } // there is still room to find p
   return(-1); // failure
} // fingerprintSearch
\end{lstlisting} \end{minipage}
\item Instead of bits, we can deal with character arrays.
    \begin{notelist}
    \item We generalize parity to the exclusive OR of characters, which are just
    8-bit quantities.
    \item The C operator for exclusive OR is {\tt \^{}}.
    \item The update rule for tParity is
    {\small \begin{verbatim}
    tParity = tParity ^ t[tIndex] ^ t[tIndex+m];
    \end{verbatim} }
    \item We now have reduced the work to 1/128 (for 7-bit ASCII), not 1/2,
	 for the random case, because only that small fraction of starting positions
	 are worth pursuing.
    \end{notelist}
%\item \note{Lecture 23, 4/9/2019}
\item The full algorithm extends fingerprinting.
    \begin{notelist}
	 \item Instead of reducing the work to 1/2 or 1/128, we want to reduce it to
	 $1/q$ for some large $q$.
    \item Use this hash function for $m$ bytes $t[j] \dots t[j+m-1]$:\\
    $\sum_{0 \le i < m} 2^{m-1-i} t[j+i] \pmod{q}$.
	 Experience suggests that $q$ should be a prime $> m$.
	 \item We can still update {\tt tParity} quickly as we move $p$ by looking at
	 only 2, not $p$, characters of $t$: \\
        ${\tt tParity}_{j+1} = (t[j+m] + 2({\tt tParity}_j-2^{m-1}t[j])) \pmod q$.
    \item We can use shifting to compute {\tt tParity} without multiplication:
        ${\tt tParity}_{j+1} = (t[j+m] + ({\tt tParity}_j-(t[j] << (m-1)) << 1)
        \pmod q$.
		  We still need to compute mod $q$, however.
    \end{notelist}
\item \note{Class 25, 4/22/2021}
\item Monte-Carlo substring search
    \begin{notelist}
    \item Choose $q$, a prime $q$ close to but not exceeding $m n^2$.
    For instance, if $m=10$ and $n=1000$, choose a prime $q$ near $10^7$,
	 such as 9,999,991.
    \item The probability $1/q$ that we will make a mistake is very low, so just
    omit the inner loop.  We will sometimes have a false positive, with
    probability, it turns out, less than $2.53/n$.
    \item I don't think we save enough computation to warrant using Monte Carlo
    search.  If false positives are very rare, it doesn't hurt to employ even a
    very expensive algorithm to remove them.  Checking anyway is called the
	 ``Las-Vegas version''.
    \end{notelist}
	\item The idea is good, but in practice Rabin-Karp takes about $7 n$ work.
\end{notelist}

\section{Text search --- Knuth--Morris--Pratt}
\begin{notelist}
\item Donald Knuth, James Morris, Vaughan Pratt, 1970-1977.
\item Consider $t$ = {\tt Tweedledee and Tweedledum}, $p$ = {\tt Tweedledum}.
\item After running the inner loop of brute-force search to the {\tt u} in $p$,
we have learned much about $t$, enough to realize that none of the letters up to
that point in $t$ (except the first) are {\tt T}.  So the next place to start a
match in $t$ is not position 1, but position 8.
\item Consider $t$ = {\tt pappappappar}, $p$ = {\tt pappar}.
\item After running the inner loop of brute-force search to the {\tt r} in $p$,
we have learned much about $t$, enough to realize that the first place in $t$
that can match $p$ starts not at position 1, but rather in position 3 (the third
{\tt p}).  Moving $p$ to that position lets us continue in the middle of $p$,
never retreating in $t$ at all.
\item How much to shift $p$ depends on how much of it matches when we encounter
a mismatch in the inner loop.  This {\bf shift table} describes the first
example. \\
\begin{tabular}{c | r r r r r r r r r r r}
p &  & T & w & e & e & d & l & e & d & u & m \\
k & -1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
shift & 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10
\end{tabular}
\item If our match fails at p[8], use shift[7]=8 to reposition the pattern.
\item Here is the shift table for the second example. \\
\begin{tabular}{c | r r r r r r r r r r r}
p &  & p & a & p & p & a & r \\
k & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\
shift & 1 & 1 & 2 & 2 & 3 & 3 & 6
\end{tabular}
\item Try matching that $p$ against $t$ = {\tt pappappapparrassanuaragh}. \\
\hspace*{-.7in}\begin{minipage}{4in} \begin{lstlisting}
int KMPSearch(char *t, char *p) {
   const int n = strlen(t);
   const int m = strlen(p);
   int tIndex = 0;
   int pIndex = 0;
	char shiftTable[m];
   computeShiftTable(p, shiftTable);
   while (tIndex+m <= n) { // there is still room to find p
      while (t[tIndex+pIndex] == p[pIndex]) { // enlarge match
         pIndex += 1;
         if (pIndex >= m) return(tIndex);
      } // enlarge match
		const int shiftAmount = shiftTable[pIndex - 1];
      tIndex += shiftAmount;
      pIndex = max(0, pIndex-shiftAmount);
   } // there is still room to find p
   return(-1); // failure
} // KMPSearch
\end{lstlisting} \end{minipage}
\item Unfortunately, computing the shift table, although \order{m}, is not
straightforward, so we omit it.
\item The overall cost is guaranteed \order{n + m}, but $m < n$, so 
\order{n}.  In practice, it makes about $1.1 n$ comparisons.
\end{notelist}

\section{Text search --- Boyer -- Moore simple}
\begin{notelist}
% \item \note{Lecture 25, 4/23/2020}
\item Robert S. Boyer, J. Strother Moore (1977)
\item We start by modifying {\tt bruteSearch} to search from the end of $p$ backwards.
\\
\hspace*{-.7in}\begin{minipage}{4in} \begin{lstlisting}
int backwardSearch(char *t, char *p) {
   const int n = strlen(t);
   const int m = strlen(p);
   int tIndex = 0;
   while (tIndex+m <= n) { // there is still room to find p
      int pIndex = m-1;
      while (t[tIndex+pIndex] == p[pIndex]) { // enlarge match
         pIndex -= 1;
         if (pIndex < 0) return(tIndex);
      } // enlarge match
      tIndex += 1;
   } // there is still room to find p
   return(-1); // failure
} // backwardSearch
\end{lstlisting} \end{minipage}
\item {\bf Occurrence heuristic}: At a mismatch, say at letter $\alpha$ in $t$,
shift $p$ to align the rightmost occurrence of $\alpha$ in $p$ with that
$\alpha$ in the text.  But don't move $p$ to the left.  If $\alpha$ does not
occur at all in $p$, move $p$ to one position after $\alpha$.
\item Method: Initialize {\tt location} array for $p$: \\
\hspace*{-.7in}\begin{minipage}{4in} \begin{lstlisting}
int location[256];
// location[c] is the last position in p holding char c

void initLocation(char *p) {
	const int m = strlen(p);
	for (int charVal = 0; charVal < 256; charVal += 1) {
		location[charVal] = -1;
	}
	for (int pIndex = 0; pIndex < m; pIndex += 1) {
		location[p[pIndex]] = pIndex;
	}
} // initLocation
\end{lstlisting} \end{minipage}
\item Let $\alpha$ be the failure character, which is found at a particular
{\tt pIndex} and {\tt tIndex}.
\item Slide $p$:  {\tt tIndex += max(1, pIndex - location[$\alpha$])}
\item This formula works in all cases.
	\begin{notelist}
	\item $\alpha$ not in $p$ and {\tt pIndex = m-1} $\Rightarrow$ a full shift:
	{\tt tIndex += m}
	\item $\alpha$ not in $p$ and {\tt pIndex = j} $\Rightarrow$ a partial shift,
	larger if we haven't travelled far along $p$:
	{\tt tIndex += pIndex + 1}
	\item $\alpha$ is in $p$.  We shift enough to align the rightmost $\alpha$
	of $p$ with the one we failed on, or at least shift right by 1.
	\end{notelist}
\item Examples % \fbox{Johnsonbaugh and Schaefer p. 392}
\begin{notelist}
\item $p$ = {\tt rum}, $t$ = {\tt conundrum}.
We shift $p$ by 3, another 3, and find the match.
\item $p$ = {\tt drum}, $t$ = {\tt conundrum}.
We shift $p$ by 1, by 4, and find the match.
\item $p$ = {\tt natu}, $t$ = {\tt conundrum}.
We shift $p$ by 2, then fail.
\item $p$ = {\tt date}, $t$ = {\tt detective}.
We would shift $p$ left, so we just shift right 1, then 4, then fail.
\end{notelist}
\item \note{Class 26, 4/27/2021}
\item {\bf Match heuristic}: Use a shift table (organized for right-to-left
search) as with the Knuth--Morris--Pratt algorithm.
\item Use both the occurrence and the match heuristics, and shift by the larger
of the two suggestions.
\item {\bf Horspool's version} (Nigel Horspool, 1980):
on a mismatch, look at $\beta$, which is the
element in $t$ where we started matching, that is, $\beta = t_{i+m-1}$.
Shift so that $\beta$ in $t$ aligns with the rightmost
occurrence of $\beta$ in $p$ (not counting $p_{m-1}$).
\begin{notelist}
\item This method always shifts $p$ to the right.
\item We need to precompute for each letter of the alphabet where its
rightmost occurrence in $p$ is, not counting $p_{m-1}$.
In particular:
\item shift[$\beta$] = if $\beta$ in $p_{0..m-2}$ then $m - 1 - max\{j | j < m - 1,
p_j = \beta\}$ else $m$.
\end{notelist}
\end{notelist}

\section{Advanced pattern matching, as in Perl}
\begin{notelist}
%\item \note{Lecture 24, 4/11/2019}
\item Based on regular expressions; can be compiled into finite-state automata.
	\begin{notelist}
	\item exact: {\tt conundrum}
	\item don't-care symbols: {\tt con.ndr..}
	\item character classes: {\tt c[ou1-5]nundrum}
	\item alternation: {\tt c(o|u)nund(rum|ite)}
	\item repetition:
		\begin{notelist}
		\item {\tt c(on)*und}
		\item {\tt c(on)+und}
		\item {\tt c(on)\{4,5\}und}
		\end{notelist}
	\item predefined character classes: {\tt \verb+c\wnundrum\d\W+}
	\item Unicode character classes: \\
	{\tt \verb+c\p{ASCII}nundrum\p{digit}\p{Final_Punctuation}+}
	\item pseudo-characters: {\tt \verb+^conundrum$+}
	\end{notelist}
\item Beyond regular expressions in Perl
	\begin{notelist}
	\item Reference to "capture groups": {\tt con(un|an)dr\textbackslash 1m}
	\item Zero-width assertions: {\tt (?=conundrum)}
	\end{notelist}
\end{notelist}

\section{Edit distance}
\begin{notelist}
%\item \note{Lecture 25, 4/16/2019}
% \item \note{Lecture 26, 4/28/2020}
\item How much do we need to change $s$ (source) to make it look like $d$
(destination) ?
\item Charge 1 for each replacement (R), deletion (D), insertion (I).
\item Example: ghost $\stackrel{D}{\rightarrow}$ host 
    $\stackrel{I}{\rightarrow}$
    houst
    $\stackrel{R}{\rightarrow}$
    house
\item The {\bf edit distance} (s,d) is the smallest number of operations to
transform $s$ to $d$.
\item We can build an edit-distance table $d$ by this rule: \\
$d_{i,j} = \min (d_{i-1,j}+1, d_{i,j-1}+1, d_{i-1,j-1} +$ if s[i] = d[j] then 0
else 1$)$.
\item Example: peseta $\rightarrow$ presto (should get distance 3).
\\ \begin{tabular}{r r | r | r r r r r r }
 & & -1 & 0 & 1 & 2 & 3 & 4 & 5  \\
 & &    & p & e & s & e & t & a  \\
\hline
-1 && 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
0&p& 1 & 0 & 1 & 2 & 3 & 4 & 5  \\
1&r& 2 & 1 & 1 & 2 & 3 & 4 & 5  \\
2&e& 3 & 2 & 1 & 2 & 2 & 3 & 4  \\
3&s& 4 & 3 & 2 & 1 & 2 & 3 & 4  \\
4&t& 5 & 4 & 3 & 2 & 2 & 2 & 3  \\
5&o& 6 & 5 & 4 & 3 & 3 & 3 & 3  \\
\end{tabular}
\item We can trace back from the last cell to see exactly how to navigate to the
start cell: pick any smallest neighbor to left/above.
    \begin{notelist}
    \item $\downarrow$: delete a character from source (left string)
    \item $\rightarrow$: insert a character from destination (top string)
    \item $\searrow$: keep the same character (if number the same) or replace
	 a character in the source (left string) with one from the destination (top
	 string).
    \end{notelist}
\item complexity: \order{n m} to calculate the array; the preprocessing
is just to start up the array, of cost \order{n+m}.
\item Another example: convert {\tt banana} to {\tt antenna}.  It should take
only 4 edits.
\item \note{Class 27, 4/29/2021}
\item This algorithm is in the {\bf dynamic programming} category.
Pascal's triangle is another, as is finding the rectangle in an array with the
largest sum of values (some negative).
\end{notelist}

\section{Categories of algorithms}
\begin{notelist}
\item Divide and conquer
\item Greedy
\item Dynamic programming
\item Search
\end{notelist}

\section{Divide and conquer algorithms}
\begin{notelist}
\item steps
    \begin{notelist}
    \item if the problem size $n$ is trivial, do it.
    \item divide the problem into $a$ easier problems of size $n/b$.
    \item do the $a$ easier problems
    \item combine the answers.
    \end{notelist}
\item We can usually compute the complexity by the Recursion Theorem
(page \pageref{recursionTheorem}).
\item cost: $n^k$ for splitting, recomputing, so
$C_n = n^k + a C_{n/b}$.
\item Select $j$th smallest element of an array.
$a=1$, $b=2$, $k=1$ $\Rightarrow$ \order{n}.
\item Quicksort.
$a=2$, $b=2$, $k=1$ $\Rightarrow$ \order{n \log n}.
\item Binary search, search in a binary tree.
$a=1$, $b=2$, $k=0$ $\Rightarrow$ \order{\log n}.
\item Multiplication (Karatsuba)
$a=3$, $b=2$, $k=1$ $\Rightarrow$ \order{n^{\log_2 3}}.
\item Tile an $n \times n$ board that is missing a single cell by a trimino: 
$a=4$, $b=4$, $k=0$ $\Rightarrow$ \order{n}.
\\ \psfig{figure=trimino.eps,height=0.4in}
%\item \note{Lecture 26, 4/18/2019}
\item Mergesort: \\
\begin{minipage}{4in} \begin{lstlisting}
void mergeSort(int array[], int lowIndex, int highIndex){
	// sort array[lowIndex] .. array[highIndex]
   if (highIndex - lowIndex < 1) return; // width 0 or 1
	int mid = (lowIndex+highIndex)/2;
   mergeSort(array, lowIndex, mid);
   mergeSort(array, mid+1, highIndex);
   merge(array, lowIndex, highIndex);
} // mergeSort
\end{lstlisting} \end{minipage} \\
$a=2$, $b=2$, $k=1$ $\Rightarrow$ \order{n \log n}.
\end{notelist}

\section{Greedy algorithms}
General rule: Enlarge the current solution by selecting (usually in a simple
way) the best single-step improvement.
\begin{notelist}
\item Computing the coins for change: greedily apply the biggest available coin
first.
    \begin{notelist}
    \item not always optimal: consider denominations 1, 6, 10, and we wish to
    construct 12.
    \item Denominations 1, 5, 10 guarantee optimality.
	 \item Power-of-two coins would be very nice: no more than 1 of each needed
	 for change.  British measures follow this rule:
	 fluid ounce : tablespoon : quarter-gill : half-gill : gill : cup : pint :
	 quart : half gallon : gallon 
	 \item Similar problem: putting weights on barbells.
    \end{notelist}
\item Kruskal's algorithm for computing a minimum-cost spanning tree: 
greedily add edges of increasing weight, avoiding cycles.
\item Prim's algorithm for computing a minimum-cost spanning tree:
greedily enlarge the current spanning tree with the shortest edge leading out.
\item Dijkstra's algorithm for all shortest paths from a source:
greedily pick the cheapest extension of all paths so far.
\item Hoffman codes for data compression
% \fbox{Johnsonbaugh and Schaefer p. 302}
    \begin{notelist}
    \item Start with a table of frequencies, like this one: \\
    {\tt \begin{tabular}{l r}
    space & 60 \\
    A & 22 \\
    O & 16 \\
    R & 13 \\
    S & 6 \\
    T & 4
    \end{tabular} }
    \\
    A text containing all these characters in the given frequencies would take
    $60+22+16+13+6+4 = 121$ 7-bit units or $847$ bits.
    \item Build a table of codes, like this one: \\
    {\tt \begin{tabular}{l r}
    space & 0 \\
    A & 111 \\
    O & 110 \\
    R & 101 \\
    S & 1001 \\
    T & 1000
    \end{tabular} }
    \end{notelist}
    The same text now uses $60 \cdot 1 + 22 \cdot 3 + \dots + 4 \cdot 4 = 253$
    bits.
    \item To decode: follow a tree: \\
    \hspace*{0.4in}\psfig{figure=huffman.eps,height=2.0in}
    \item To build the tree
        \begin{notelist}
        \item Each character is a node.
        \item Greedily take the two least common nodes, combine them as children
        of a new parent, and label that parent with the combined frequency of the
        two children.
        \end{notelist}
\item Adding a million real numbers, all in the range $0 \dots 1$, losing
minimal precision
    \begin{notelist}
    \item Remove the two smallest numbers from the set.  (This step is greedy:
    take the numbers whose sum can be computed with the least precision loss.)
    \item Insert their sum in the set.
    \item Use a heap to represent the set.
    \end{notelist}
\item Continuous knapsack problem
    \begin{notelist}
    \item Given a set of $n$ objects $x_i$, each with a weight $w_i$ and
    profit $p_i$, and a total weight capacity $C$, select objects (to put
    in a knapsack) that together weigh $\le C$ and maximize profit.
    We are allowed to take fractions of an object.
%	\item \note{Lecture 27, 4/23/2019}
    \item Greedy method
        \begin{notelist}
        \item Start with an empty knapsack.
        \item Sort the objects in decreasing order of $p_i/w_i$.
        \item Greedy step: Take all of each object in the list, if it fits.
            If it fits partially, take a fraction of the object, then done.  
        \item Stop when the knapsack is full.
        \end{notelist}
    \item Example. \\ % \fbox{Johnsonbaugh and Schaefer p. 313}\\
    \begin{tabular}{c c c r}
    chapter & pages (weight) & importance (profit) & ratio \\
    \hline
    1 & 120 & 5 & .0417 \\
    2 & 150 & 5 & .0333 \\
    3 & 200 & 4 & .0200 \\
    4 & 150 & 8 & .0533 \\
    5 & 140 & 3 & .0214
    \end{tabular} \\
    sorted: 4, 1, 2, 5, 3.
    If capacity $C = 600$, take all of 4, 1, 2, 5, and 40/200 of 3.
    \item This greedy algorithm happens to be optimal.
    \end{notelist}
\item 0/1 knapsack problem: Same as before, but no fractions are allowed.
The greedy algorithm is still fast, but it is not guaranteed optimal.
\end{notelist}

\section{Dynamic programming}
General rule: Solve all smaller problems and use their solutions to compute
the solution to the next problem.
\begin{notelist}
\item Compute Fibonacci numbers: $f_i = f_{i-1} + f_{i-2}$.
\item Compute binomial coefficients: $C(n,i) = C(n-1,i-1) + C(n-1, i)$.
\item Compute minimal edit distance.
\end{notelist}

\section{Summary of algorithms covered}
\begin{notelist}
% \item \note{Lecture 26, 4/28/2020}
\item \note{Class 28, 5/4/2021}
\item Graphs
    \begin{notelist}
    \item Computing the degree of all vertices: Loop over representation
    \item Computing the connected component containing node $i$ in an undirected
	 graph: Depth-first search, recursive, avoiding vertices already visited
    \item Breadth-first search: use a queue, iterative, avoiding vertices
	 already visited, perhaps with back-pointers
    \item Shortest path between nodes $i$ and $j$: use a priority queue (heap)
	 sorted by distance from $i$.
    \item Topological sort: recursive; build list as the last step.
    \item Dijkstra's algorithm: Finding all shortest paths from given node
    Greedy: extend currently shortest path
	 \item Prim's algorithm for spanning trees: Greedy, repeatedly add shortest
	 outgoing edge
    \item Kruskal's algorithm for spanning trees: Greedy, repeatedly add
	 shortest edge that does not build a cycle.
    \item Cycle detection: Union-find: All vertices in a component point
	 (possibly indirectly) to a representative; union joins representatives.
    \end{notelist}
\item Numerical algorithms
    \begin{notelist}
    \item Euclidean algorithm for greatest common divisor (GCD): Repeatedly take
	 modulus.
    \item Fast exponentiation: represent the exponent in binary to guide the
	 steps
    \item Integer multiplication (Karatsuba): Subdivide a problem of size $n
	 \times n$ into three problems of size $n/2 \times n/2$.
    \end{notelist}
\item Strings and pattern matching --- Text search problem
    \begin{notelist}
    \item Text search --- Brute-force algorithm: Try each position for
	 the pattern $p$.
	 \item Text search --- Rabin-Karp: Hash-based pre-check each time $p$ moves
	 over.
    \item Text search --- Knuth--Morris--Pratt: Precomputed shift table tells
	 how far to move $p$ on a mismatch.
    \item Text search --- Boyer -- Moore simple: Match starting at the end of
	 $p$; can jump great distances.
	 \item Edit distance --- Dynamic programming, finding edit distance of
	 several subproblems to guide the next subproblem.
    \end{notelist}
\item Miscellaneous
    \begin{notelist}
    \item Tiling (divide and conquer)
    \item Mergesort (divide and conquer)
    \item Computing Fibonacci numbers (dynamic programming)
    \item Computing binomial coefficients (dynamic programming)
    \item Continuous knapsack problem (greedy)
    \item Coin changing (greedy)
    \item Hoffman codes (greedy)
    \end{notelist}
\end{notelist}

\section{Tractability}
\begin{notelist}
\item Formal definition of $\mathcal{O}$: $f(n) = \mathcal{O}(g(n))$ iff for
adequately large $n$, and some constant $c$, we have $f(n) \le c \cdot g(n)$.
That is, $f$ is bounded above by some multiple of $g$.  We can say that $f$
grows no faster than $g$.
\item Formal definition of $\Theta$: $f(n) = \Theta(g(n))$ iff for
adequately large $n$, and some constants $c_1, c_2$,
we have $c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$.  We say that $f$ grows as
fast as $g$.
\item Formal definition of $\Omega$ is similar; $f(n) = \Omega(g(n))$ means that
$f$ grows at least as fast as $g$.
\item We usually say that a problem is {\bf tractable} if we can solve it
in polynomial time (with respect to the problem size $n$).
We also say the program is {\bf efficient}.
    \begin{notelist}
    \item constant time: \order{1}
    \item logarithmic time: \order{\log n}
    \item linear time: \order{n}
    \item sub-quadratic: \order{n \log n} (for instance)
    \item quadratic time: \order{n^2}
    \item cubic time: \order{n^3}
    \item These are all bounded by \order{n^k} for some fixed $k$.
    \item However, if $k$ is large, even tractable problems can be
    infeasible to solve.  In practice, algorithms seldom have $k > 3$.
    \end{notelist}
%\item \note{Lecture 28, 4/25/2019}
\item There are many algorithms that take more than polynomial time.
    \begin{notelist}
    \item exponential: \order{2^n}.
    \item super-exponential: \order{n!} (for example)
    \item \order{n^n}
    \item \order{2^{2^n}}
    \end{notelist}
\end{notelist}

\section{Decision problems, function problems, P, NP}
\begin{notelist}
\item Decision problems: The answer is just ``yes'' or ``no''.
    \begin{notelist}
    \item Primality: is $n$ prime?  (There are very fast probabilistic
    algorithms, and recently a polynomial algorithm).
    \item Is there a path from $a$ to $b$ shorter than 10?
    \item Are two graphs $G$ and $F$ isomorphic? (Apparently very hard)
    \item Can graph $G$ be colored with 3 colors? (Apparently very hard)
    \end{notelist}
\item Function problems: the answer is a number.
    \begin{notelist}
    \item What is the smallest prime divisor of $n$?
    \item What is the weight of a minimum-weight spanning tree of $G$?
    \end{notelist}
\item We use $P$ to refer to the set of decision problems that can be
decided in polynomial time.  That is, 
for all problems $p \in P$, there must be an algorithm and a positive number
$k$ such that the time of the algorithm for $p$ is
\order{|x|^k} where $|x|$ means the size of $x$.
\item We use {\em NP} to refer to the set of decision problems that can be
decided in polynomial time if we are allowed to guess a witness to a
``yes'' answer and only need to check it.
	\begin{notelist}
	\item Is there a path from $a$ to $b$ shorter than 10?  Guess the path,
	find its length.  \order{1}.
	\item Are two graphs $G$ and $F$ isomorphic? Guess the isomorphism, then
	check, requiring \order{v+e}.
	\item Can graph $G$ be colored with 3 colors? Guess the coloring, then
	demonstrate that it is right; \order{v+e}.
	\item Is there a set of Boolean values for variables $x_1, ..., x_n$ that
	satisfies a given Boolean formula (using "and", "or", and "not")?
	Guess the values, check in linear time (in the length of the formula).	
	\end{notelist}
\item Properties of {\em P} and {\em NP} (and {\em EXP}, decision problems that
can be solved in \order{k^n}).
    \begin{notelist}
    \item $P \subseteq NP \subseteq EXP$
    \item $P \subset EXP$
    \item if a problem in {\em NP} has $g$ possible witnesses, then it has an
    algorithm in \order{g^n}.
    \item Some problems can be proved to be ``hardest'' in $NP$.  The are
    called $NP$-complete problems.  All other problems in $NP$ can be
    reduced to such $NP$-complete problems.
    \item Nobody knows, but people suspect that $P \subset NP \subset EXP$.
    \end{notelist}
\end{notelist}

\end{document}
\end{notelist} \end{document}

% vim:ts=3 sw=3:
