\documentclass[12pt]{book}

\newcommand{\thetitle}{Think Java: How to Think Like a Computer Scientist}

\title{\thetitle}

\newcommand{\theauthors}{Allen Downey and Chris Mayfield}

\author{\theauthors}

\newcommand{\theversion}{Version 6.0 Draft -- \today}

\date{\theversion}

\usepackage{geometry}

\geometry{

width=5.5in,

height=8.5in,

hmarginratio=3:2,

vmarginratio=1:1,

includehead=true,

headheight=15pt

}

% paragraph spacing

\setlength{\parindent}{0pt} % 17.62482pt

\setlength{\parskip}{12pt plus 4pt minus 4pt} % 0.0pt plus 1.0pt

\linespread{1.05}

\def\arraystretch{1.5}

% list spacing

\setlength{\topsep}{5pt plus 2pt minus 3pt} % 10.0pt plus 4.0pt minus 6.0pt

\setlength{\partopsep}{-6pt plus 2pt minus 2pt} % 3.0pt plus 2.0pt minus 2.0pt

\setlength{\itemsep}{0pt} % 5.0pt plus 2.5pt minus 1.0pt

% these are copied from tex/latex/base/book.cls

% all I changed is afterskip

\makeatletter

\renewcommand{\section}{\@startsection {section}{1}{\z@}%

{-3.5ex \@plus -1ex \@minus -.2ex}%

{0.7ex \@plus.2ex}%

{\normalfont\Large\bfseries}}

\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%

{-3.25ex\@plus -1ex \@minus -.2ex}%

{0.3ex \@plus .2ex}%

{\normalfont\large\bfseries}}

\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%

{-3.25ex\@plus -1ex \@minus -.2ex}%

{0.3ex \@plus .2ex}%

{\normalfont\normalsize\bfseries}}

\makeatother

% table of contents vertical spacing

\usepackage{tocloft}

\setlength\cftparskip{8pt plus 4pt minus 4pt}

% The following line adds a little extra space to the column

% in which the Section numbers appear in the table of contents

\makeatletter

\renewcommand{\l@section}{\@dottedtocline{1}{1.5em}{3.0em}}

\makeatother

% customize page headers

\usepackage{fancyhdr}

\pagestyle{fancyplain}

\renewcommand{\chaptermark}[1]{\markboth{Chapter \thechapter ~~ #1}{}}

\renewcommand{\sectionmark}[1]{\markright{\thesection ~~ #1}}

\lhead[\fancyplain{}{\bfseries\thepage}]%

{\fancyplain{}{\bfseries\rightmark}}

\rhead[\fancyplain{}{\bfseries\leftmark}]%

{\fancyplain{}{\bfseries\thepage}}

\cfoot{}

%\rfoot{\textcolor{gray}{\tiny ThinkJava Draft \today}}

% balanced index with TOC entry

\usepackage{makeidx}

\makeindex

%\usepackage[totoc]{idxlayout}

% automatically index glossary terms

\newcommand{\term}[1]{%

\index{#1}

\item[#1:]}

% TODO: doesn't work with plastex

%\newcommand{\term}[1]{\item[#1:]}

% where to find graphics

\usepackage{graphicx}

%\graphicspath{{figs/}}

%% tweak spacing of figures and captions

%\usepackage{floatrow}

%\usepackage{caption}

%\captionsetup{

% font=small,

% labelformat=empty,

% justification=centering,

% skip=4pt

%}

% format end of chapter excercises

\usepackage{amsmath}

\usepackage{amsthm}

\newtheoremstyle{exercise}

{12pt} % space above

{12pt} % space below

{} % body font

{} % indent amount

{\bfseries} % head font

{} % punctuation

{12pt} % head space

{} % custom head

\theoremstyle{exercise}

\newtheorem{exercise}{Exercise}[chapter]

% colors for code listings and output

\usepackage{xcolor}

\definecolor{bgcolor}{HTML}{FAFAFA}

\definecolor{comment}{HTML}{007C00}

\definecolor{keyword}{HTML}{0000FF}

\definecolor{strings}{HTML}{B20000}

% syntax highlighting in code listings

\usepackage{textcomp}

\usepackage{listings}

\lstset{

language=java,

basicstyle=\ttfamily,

backgroundcolor=\color{bgcolor},

commentstyle=\color{comment},

keywordstyle=\color{keyword},

stringstyle=\color{strings},

columns=fullflexible,

keepspaces=true,

showstringspaces=false,

upquote=true,

aboveskip=\parskip,

belowskip=\parskip

}

% code listing environments

\lstnewenvironment{code}

{\minipage{\linewidth}}

{\endminipage}

\lstnewenvironment{stdout}

{\lstset{commentstyle=,keywordstyle=,stringstyle=}\minipage{\linewidth}}

{\endminipage}

% pdf hyperlinks, table of contents, and document properties

\usepackage[pdftex]{hyperref}

\hypersetup{%

pdftitle={\thetitle},

pdfauthor={\theauthors},

pdfsubject={\theversion},

pdfkeywords={},

bookmarksopen=false,

colorlinks=true,

citecolor=black,

filecolor=black,

linkcolor=black,

urlcolor=blue

}

% inline syntax formatting

\newcommand{\java}[1]{\lstinline{#1}} %\end{

%\newcommand{\java}[1]{\verb"#1"}

%\newcommand{\java}[1]{{\tt #1}}

\begin{document}

\setcounter{chapter}{4}

\chapter{Decisions and logic}

TODO

\section{Boolean expressions}

TODO

\subsection{Relational operators}

\index{boolean}

\index{expression!boolean}

Most of the operations we have seen produce results that are the same type as their operands.

For example, the \java{+} operator takes two \java{int}s and produces an \java{int}, or two \java{double}s and produces a \java{double}, etc.

\index{operator!relational}

\index{relational operator}

The exceptions we have seen are the {\bf relational operators}, which compare {\tt int}s and {\tt float}s and return either {\tt true} or {\tt false}.

{\tt true} and {\tt false} are special values in Java, and together they make up a type called {\bf boolean}.

You might recall that when I defined a type, I said it was a set of values.

In the case of {\tt int}s, {\tt double}s and {\tt String}s, those sets are pretty big.

For {\tt boolean}s, there are only two values.

Boolean expressions and variables work just like other types of expressions and variables:

\begin{code}

boolean flag;

flag = true;

boolean testResult = false;

\end{code}

The first example is a simple variable declaration, the second example is an assignment, and the third example is an initialization.

The values {\tt true} and {\tt false} are keywords in Java, so they may appear in a different color, depending on your development environment.

\index{initialization}

\index{statement!initialization}

The result of a conditional operator is a boolean, so you can store the result of a comparison in a variable:

\begin{code}

boolean evenFlag = (n % 2 == 0); // true if n is even

boolean positiveFlag = (x > 0); // true if x is positive

\end{code}

The parentheses are unnecessary, but they make the code easier to read.

You can then use these variables as part of a conditional statement later:

\begin{code}

if (evenFlag) {

System.out.println("n was even when I checked it");

}

\end{code}

A variable used in this way is called a {\bf flag} because it flags the presence or absence of some condition.

Notice you don't need to say \java{if (evenFlag == true)}.

Since \java{evenFlag} is a \java{boolean}, it's already a condition.

\subsection{Conditional operators}

\index{logical operator}

\index{operator!logical}

There are three {\bf logical operators} in Java: AND, OR and NOT, which are denoted by the symbols {\tt \&\&}, {\tt ||} and {\tt !}.

The semantics of these operators is similar to their meaning in English.

For example {\tt x > 0 \&\& x < 10} is true only if {\tt x} is greater than zero AND less than 10.

\index{semantics}

{\tt evenFlag || n\%3 == 0} is true if {\em either} of the conditions is true, that is, if {\tt evenFlag} is true OR the number is divisible by 3.

Finally, the NOT operator inverts a boolean expression, so {\tt !evenFlag} is true if {\tt evenFlag} is false---if the number is odd.

\index{nested structure}

Logical operators can simplify nested conditional statements.

For example, can you re-write this code using a single conditional?

\begin{code}

if (x > 0) {

if (x < 10) {

System.out.println("x is a positive single digit.");

}

}

\end{code}

\section{The if-else statement}

TODO

\subsection{Conditional execution}

\index{conditional}

\index{statement!conditional}

To write useful programs, we almost always need to check conditions and change the behavior of the program accordingly.

{\bf Conditional statements} give us this ability.

The simplest form is the {\tt if} statement:

\begin{code}

if (x > 0) {

System.out.println("x is positive");

}

\end{code}

The expression in parentheses is called the condition.

If it is true, then the statements in brackets get executed.

If the condition is not true, nothing happens.

\index{operator!comparison}

\index{operator!relational}

\index{comparison!operator}

\index{relational operator}

The condition can contain any of the comparison operators, sometimes called {\bf relational operators}:

\begin{code}

x == y // x equals y

x != y // x is not equal to y

x > y // x is greater than y

x < y // x is less than y

x >= y // x is greater than or equal to y

x <= y // x is less than or equal to y

\end{code}

Although these operations are probably familiar to you, the syntax Java uses is a little different from mathematical symbols like $=$, $\neq$ and $\le$.

A common error is to use a single {\tt =} instead of a double {\tt ==}.

Remember that {\tt =} is the assignment operator, and {\tt ==} is a comparison operator.

Also, there is no such thing as {\tt =<} or {\tt =>}.

The two sides of a condition operator have to be the same type.

You can only compare {\tt ints} to {\tt ints} and {\tt doubles} to {\tt doubles}.

The operators {\tt ==} and {\tt !=} work with Strings, but they don't do what you expect.

And the other relational operators don't do anything at all.

To compare two strings, you should use the \java{String.equals} method.

%We will see how to compare strings Section~\ref{incomparable}.

\subsection{Alternative execution}

\label{alternative}

\index{conditional!alternative}

A second form of conditional execution is alternative execution, in which there are two possibilities, and the condition determines which one gets executed.

The syntax looks like:

\begin{code}

if (x % 2 == 0) {

System.out.println("x is even");

} else {

System.out.println("x is odd");

}

\end{code}

If the remainder when {\tt x} is divided by 2 is zero, then we know that {\tt x} is even, and this code prints a message to that effect.

If the condition is false, the second print statement is executed.

Since the condition must be true or false, exactly one of the alternatives will be executed.

As an aside, if you need to check the {\em parity} (evenness or oddness) of numbers often, you might want to ``wrap'' this code up in a method, as follows:

\begin{code}

public static void printParity(int x) {

if (x % 2 == 0) {

System.out.println("x is even");

} else {

System.out.println("x is odd");

}

}

\end{code}

Now you have a method named {\tt printParity} that will print an appropriate message for any integer you care to provide.

In {\tt main} you would invoke this method like this:

\begin{code}

printParity(17);

\end{code}

Always remember that when you {\em invoke} a method, you do not have to declare the types of the arguments you provide.

Java can figure out what type they are.

You should resist the temptation to write things like:

\begin{code}

int number = 17;

printParity(int number); // WRONG!!!

\end{code}

\section{Programming logic}

TODO

\subsection{De Morgan's law}

TODO

\subsection{Short circuit evaluation}

TODO

\subsection{DrJava interactions}

TODO

\section{Decision structures}

TODO

\subsection{Chained conditionals}

\index{conditional!chained}

Sometimes you want to check for a number of related conditions and choose one of several actions.

One way to do this is by {\bf chaining} a series of {\tt if}s and {\tt else}s:

\begin{code}

if (x > 0) {

System.out.println("x is positive");

} else if (x < 0) {

System.out.println("x is negative");

} else {

System.out.println("x is zero");

}

\end{code}

These chains can be as long as you want, although they can be difficult to read if they get out of hand.

One way to make them easier to read is to use standard indentation, as demonstrated in these examples.

If you keep all the statements and squiggly-brackets lined up, you are less likely to make syntax errors and more likely to find them if you do.

\subsection{Nested conditionals}

\index{conditional!nested}

In addition to chaining, you can also nest one conditional within another.

We could have written the previous example as:

\begin{code}

if (x == 0) {

System.out.println("x is zero");

} else {

if (x > 0) {

System.out.println("x is positive");

} else {

System.out.println("x is negative");

}

}

\end{code}

There is now an outer conditional that contains two branches.

The first branch contains a simple {\tt print} statement, but the second branch contains another conditional statement, which has two branches of its own.

Those two branches are both {\tt print} statements, but they could have been conditional statements as well.

Indentation helps make the structure apparent, but nevertheless, nested conditionals get difficult to read very quickly.

Avoid them when you can.

\index{nested structure}

On the other hand, this kind of {\bf nested structure} is common, and we will see it again, so you better get used to it.

\subsection{The return statement}

\index{return}

\index{statement!return}

The {\tt return} statement allows you to terminate the execution of a method before you reach the end.

One reason to use it is if you detect an error condition:

\begin{code}

public static void printLogarithm(double x) {

if (x <= 0.0) {

System.err.println("Positive numbers only, please.");

return;

}

double result = Math.log(x);

System.out.println("The log of x is " + result);

}

\end{code}

This defines a method named {\tt printLogarithm} that takes a {\tt double} named {\tt x} as a parameter.

It checks whether {\tt x} is less than or equal to zero, in which case it prints an error message and then uses {\tt return} to exit the method.

The flow of execution immediately returns to the caller and the remaining lines of the method are not executed.

I used a floating-point value on the right side of the condition because there is a floating-point variable on the left.

\section{Recursive methods}

\label{recursion}

\index{recursion}

I mentioned in the last chapter that it is legal for one method to invoke another, and we have seen several examples.

I neglected to mention that it is also legal for a method to invoke itself.

It may not be obvious why that is a good thing, but it turns out to be one of the most magical and interesting things a program can do.

For example, look at the following method:

\begin{code}

public static void countdown(int n) {

if (n == 0) {

System.out.println("Blastoff!");

} else {

System.out.println(n);

countdown(n-1);

}

}

\end{code}

The name of the method is {\tt countdown} and it takes a single integer as a parameter.

If the parameter is zero, it prints the word ``Blastoff.''

Otherwise, it prints the number and then invokes a method named {\tt countdown}---itself---passing {\tt n-1} as an argument.

What happens if we invoke this method, in {\tt main}, like this:

\begin{code}

countdown(3);

\end{code}

The execution of {\tt countdown} begins with {\tt n=3}, and since {\tt n} is not zero, it prints the value 3, and then invokes itself...

\begin{quote}

The execution of {\tt countdown} begins with {\tt n=2}, and since {\tt n} is not zero, it prints the value 2, and then invokes itself...

\begin{quote}

The execution of {\tt countdown} begins with {\tt n=1}, and since {\tt n} is not zero, it prints the value 1, and then invokes itself...

\begin{quote}

The execution of {\tt countdown} begins with {\tt n=0}, and since {\tt n} is zero, it prints the word ``Blastoff!'' and then returns.

\end{quote}

The {\tt countdown} that got {\tt n=1} returns.

\end{quote}

The {\tt countdown} that got {\tt n=2} returns.

\end{quote}

The {\tt countdown} that got {\tt n=3} returns.

\noindent And then you're back in {\tt main}.

So the total output looks like:

\begin{stdout}

3

2

1

Blastoff!

\end{stdout}

As a second example, let's look again at the methods {\tt newLine} and {\tt threeLine}.

\begin{code}

public static void newLine() {

System.out.println();

}

public static void threeLine() {

newLine();

newLine();

newLine();

}

\end{code}

Although these work, they would not be much help if we wanted to print 2 newlines, or 106.

A better alternative would be:

\begin{code}

public static void nLines(int n) {

if (n > 0) {

System.out.println();

nLines(n-1);

}

}

\end{code}

This program similar to {\tt countdown}; as long as {\tt n} is greater than zero, it prints a newline and then invokes itself to print {\tt n-1} additional newlines.

The total number of newlines that get printed is {\tt 1 +(n-1)}, which usually comes out to roughly {\tt n}.

\index{recursive}

\index{newline}

When a method invokes itself, that's called {\bf recursion}, and such methods are {\bf recursive}.

\subsection{Recursive stack diagrams}

\index{stack}

\index{diagram!stack}

In the previous chapter we used a stack diagram to represent the state of a program during a method invocation.

The same kind of diagram can make it easier to interpret a recursive method.

Remember that every time a method gets called it creates a new frame that contains a new version of the method's parameters and variables.

The following figure is a stack diagram for countdown, called with {\tt n = 3}:

\begin{center}

\includegraphics{stack2.pdf}

\end{center}

There is one frame for {\tt main} and four frames for {\tt countdown}, each with a different value for the parameter {\tt n}.

The bottom of the stack, {\tt countdown} with {\tt n=0} is called the {\bf base case}.

It does not make a recursive call, so there are no more frames for {\tt countdown}.

The frame for {\tt main} is empty because {\tt main} does not have any parameters or variables.

\section{Vocabulary}

\begin{description}

\term{boolean}

A type of variable that can contain only the two values \java{true} and \java{false}.

\term{flag}

A variable (usually \java{boolean}) that records a condition or status information.

\index{operator!relational}

\term{relational operator}

An operator that compares two values and produces a boolean that indicates the relationship between the operands.

\index{operator!logical}

\term{logical operator}

An operator that combines boolean values and produces boolean values.

\term{conditional}

A block of statements that may or may not be executed depending on some condition.

\term{chaining}

A way of joining several conditional statements in sequence.

\term{nesting}

Putting a conditional statement inside one or both branches of another conditional statement.

\term{recursion}

The process of invoking the same method you are currently executing.

\term{base case}

A condition that causes a recursive method {\em not} to make a recursive call.

\end{description}

\section{Exercises}

\begin{exercise}

Draw a stack diagram that shows the state of the program in Section~\ref{recursion} after {\tt main} invokes {\tt nLines} with the parameter {\tt n=4}, just before the last invocation of {\tt nLines} returns.

\end{exercise}

\begin{exercise}

This exercise reviews the flow of execution through a program with multiple methods.

Read the following code and answer the questions below.

\begin{code}

public class Buzz {

public static void baffle(String blimp) {

System.out.println(blimp);

zippo("ping", -5);

}

public static void zippo(String quince, int flag) {

if (flag < 0) {

System.out.println(quince + " zoop");

} else {

System.out.println("ik");

baffle(quince);

System.out.println("boo-wa-ha-ha");

}

}

public static void main(String[] args) {

zippo("rattle", 13);

}

}

\end{code}

\begin{enumerate}

\item Write the number {\tt 1} next to the first {\em statement} of this program that will be executed.

Be careful to distinguish things that are statements from things that are not.

\item Write the number {\tt 2} next to the second statement, and so on until the end of the program.

If a statement is executed more than once, it might end up with more than one number next to it.

\item What is the value of the parameter {\tt blimp} when {\tt baffle} gets invoked?

\item What is the output of this program?

\end{enumerate}

\end{exercise}

\begin{exercise}

The first verse of the song ``99 Bottles of Pop'' is:

\begin{quote}

99 bottles of pop on the wall,

99 bottles of pop,

If one of those bottles should happen to fall,

98 bottles of pop on the wall.

\end{quote}

Subsequent verses are identical except that the number of bottles gets smaller by one in each verse, until the last verse:

\begin{quote}

1 bottle of pop on the wall,

1 bottle of pop,

If that last bottle should happen to fall,

No more bottles of pop on the wall.

\end{quote}

And then the song(finally) ends.

Write a program that prints the entire lyrics of ``99 Bottles of Pop.''

Your program should include a {\em recursive} method that does the hard part, but you might want to write additional methods to separate the major functions of the program.

As you develop your code, test it with a small number of verses, like ``3 Bottles of Pop.''

The purpose of this exercise is to take a problem and break it into smaller problems, and to solve the smaller problems by writing simple methods.

\end{exercise}

\begin{exercise}

What is the output of the following program?

\begin{code}

public class Narf {

public static void zoop(String fred, int bob) {

System.out.println(fred);

if (bob == 5) {

ping("not ");

} else {

System.out.println("!");

}

}

public static void main(String[] args) {

int bizz = 5;

int buzz = 2;

zoop("just for", bizz);

clink(2 * buzz);

}

public static void clink(int fork) {

System.out.print("It's ");

zoop("breakfast ", fork) ;

}

public static void ping(String strangStrung) {

System.out.println("any " + strangStrung + "more ");

}

}

\end{code}

\end{exercise}

\begin{exercise}

Fermat's Last Theorem says that there are no integers $a$, $b$, and $c$ such that

\[ a^n + b^n = c^n \]

except in the case when $n \leq 2$ (e.g., the Pythagorean Theorem).

Write a method named {\tt checkFermat} that takes four integers as parameters---{\tt a}, {\tt b}, {\tt c} and {\tt n}---and that checks to see if Fermat's theorem holds.

If $n$ is greater than 2 and it turns out to be true that $a^n + b^n = c^n$, the program should print ``Holy smokes, Fermat was wrong!''

Otherwise the program should print ``No, that doesn't work.''

HINT: You may want to use \java{Math.pow} in your method.

\end{exercise}

\end{document}