latest handbook commit

gistfile1.txt

commit 9c25ff27baf0c0b4727051ca6727a60f234dff87
Author: Godmar Back <godmar@gmail.com>
Date:   Wed May 25 22:20:59 2016 -0400

    fixes to BFS and various other notes
    
    - streamlined BFS implementation
    - pointers for BFS and TSP practice
    - note on integer arithmetic
    - note on dyadic rationals

diff --git a/book/code/bfsloop.java b/book/code/bfsloop.java
index e51f609..0b0320f 100644
--- a/book/code/bfsloop.java
+++ b/book/code/bfsloop.java
@@ -2,14 +2,21 @@
  * Assumes that 'State' implements equals() and hashCode()
  * according to contract.
  * State must also provide 'isfinal', and 'successors' methods
+ * boolean isfinal() { } 
+ * List<State> successors() { ... }
+ *
+ * @return distance from start state, or -1 if state space 
+ *         was exhausted before final state was reached.
  */
-void solve(State start) {
-    Set<State> visited = new HashSet<State>();                  
-    // has this state been visited?
-    Map<State, State> pred = new HashMap<State, State>();       
+int solve(State start) {
     // predecessor on the shortest path to the start state
+    // only needed if path must be reconstructed.
+    Map<State, State> pred = new HashMap<State, State>();       
+
+    // shortest distance to start state, doubles to keep track
+    // if state was encountered 
+    //
     Map<State, Integer> dist = new HashMap<State, Integer>();   
-    // shortest distance to start state
     Deque<State> bfs = new ArrayDeque<State>();  // BFS queue
     bfs.offer(start);
     dist.put(start, 0);
@@ -17,17 +24,13 @@ void solve(State start) {
     while (bfs.size() > 0) {
         State s = bfs.poll();
         int n = dist.get(s);
-        visited.add(s);
 
         if (s.isfinal()) {
             output(n, s, pred);
-            return;
+            return n;
         }
 
         for (State succ : s.successors()) {
-            if (visited.contains(succ))
-                continue;
-
             if (!pred.containsKey(succ))
                 pred.put(succ, s);
 
@@ -37,6 +40,7 @@ void solve(State start) {
             }
         }
     }
+    return -1;
 }
 
 /* Compute and output path */
@@ -55,4 +59,3 @@ void output(int distToSolution, State finalState, Map<State, State> pred) {
         System.out.printf("%3d %s%n", i, revPath.get(revPath.size() - 1 - i));
     }
 }
-
diff --git a/book/nphard.tex b/book/nphard.tex
index b9ef86d..946702f 100644
--- a/book/nphard.tex
+++ b/book/nphard.tex
@@ -146,3 +146,8 @@ Additional notes:
     \caption{EBay sellers vs. traditional traveling sales men. Source: \href{https://xkcd.com/399/}{https://xkcd.com/399/}}
     \label{fig:xkcdtsp}
 \end{figure}
+
+Practice it:
+\href{https://open.kattis.com/problems/supermario169}{2014/NAIPC/SuperMario 169},
+\href{https://open.kattis.com/problems/bustour}{WF/2012/Bustour}
+
diff --git a/book/searching.tex b/book/searching.tex
index 310fb6b..035e33c 100644
--- a/book/searching.tex
+++ b/book/searching.tex
@@ -26,8 +26,11 @@ See also \astar{} in Section~\ref{sec:astar}.
 
 \subsection{Breadth-First Search (BFS)}
 \label{sec:bfs}
+\index{Breadth-First Search}
+\index{Search!Breadth-First}
+
 BFS is a common and simple way of exploring a state space that is asked for 
-in numerous programming competition problems. 
+in numerous programming competition problems.
 There are numerous ways of writing a BFS loop.  There are even more ways of
 getting it wrong.  Here is one way that is correct:
 
@@ -56,6 +59,14 @@ Section~\ref{sec:objequivalence}.
     Note that both 'pred' and 'dist' have the invariant when encountering a state 
     multiple times, only the first encountered state is kept in the map.
 
+\item Note that the use of a \code{HashMap} can be expensive; for instance, our code times out
+    for \href{http://codeforces.com/contest/676/problem/D}{CF/354/D}.  If each state can be mapped
+    to a number within a contiguous, dense range, a simple \code{int [] dist} array can be used
+    instead.  For CF/354/D, doing so brought the solution from timing out ($>3s$) down to
+    $1s$ of runtime and passing.
+
+Practice It: 
+\href{http://codeforces.com/contest/676/problem/D}{CF/354/D Theseus and Labyrinth}.
 \end{itemize}
 
 \paragraph{Flood-Filling.}
diff --git a/book/stdlibs.tex b/book/stdlibs.tex
index 1c60574..d2ae702 100644
--- a/book/stdlibs.tex
+++ b/book/stdlibs.tex
@@ -606,6 +606,7 @@ This argument is optional because you can list your arguments to the
 format string in the order that they are referenced.
 
 \subsection{Rounding}
+\label{sec:rounding}
 \index{Rounding}
 
 The \texttt{\%f} conversion character rounds floating point numbers to
@@ -619,7 +620,11 @@ rounded to $.54$.
 The big problem with rounding when using the \code{double} type is that you
 usually do not know the exact magnitude of a fractional part of a \code{double}.
 Recall that doubles use a binary representation, which means that any fraction
-that doesn't have a denominator that is a power of 2 cannot be exactly represented.
+that doesn't have a denominator that is a power of 2 cannot be exactly represented.\footnote{
+    As a side note, if the problem uses only \href{https://en.wikipedia.org/wiki/Dyadic_rational}{dyadic rationals} 
+    (i.e., the only division is by 2 or by numbers that are already dyadic rationals), then the use of
+    doubles is perfectly safe.  Example: \href{http://codeforces.com/contest/676/problem/B}{CF/354/B}
+}
 So for instance, $1.53125$ can be exactly represented (it's $\frac{49}{32}$), but
 $1.53126$ cannot.  The latter is $\frac{38289}{25000}$, whose denominator is not 
 a power of 2.  When you write \code{1.53126} in your program, you are creating
@@ -684,6 +689,25 @@ instead of \texttt{10000}. To turn it off, do:
     ((DecimalFormat)nf).setDecimalSeparatorAlwaysShown(false);  
 \end{minted}
 
+\subsection{Integer Arithmetic}
+\label{sec:intarithmetic}
+\index{Integer Arithmetic}
+
+As should be clear from Section~\ref{sec:rounding}, the use of floating point arithmetic 
+should be avoided wherever possible. Below we give some formula for how to implement common
+operations using integers.
+
+\begin{enumerate}
+    \item Checking for overflow.  If \code{a} and \code{b} are two long integers, 
+        \code{a * b} overflows long iff \texttt{a > Long.MAX\_VALUE / b}. Ditto for \code{int}.
+
+    \item Computing floor and ceiling.  For two integers with equal sign $x$ and $y$, computing 
+        $\left \lfloor \frac{x}{y} \right \rfloor$ is just \code{x/y}.  (Note that when $x$ and $y$
+        have opposite signs, Java rounds to zero, so the result is $\left \lfloor \frac{x}{y} \right \rfloor + 1$).
+        Similarly, $\left \lceil \frac{x}{y} \right \rceil$ can be computed as \code{1 + ((x - 1) / y)}
+        but only iff $x, y > 0$.
+\end{enumerate}
+
 \subsection{Fast Output}
 \label{sec:fastoutput}