Description - Programming Logic in Java

The Java Learning Kit: Chapter 3 – Programming Logic

Copyright 2015 by C. Herbert, all rights reserved.

Last edited January, 2015 by C. Herbert

This document is a chapter from a draft of the Java Learning Kit, written by Charles Herbert, with editorial assistance from

Daphne Herbert, Craig Nelson, Christopher Quinones, and Matthew Staley. It is available free of charge for students in

Computer Science courses at Community College of Philadelphia during the Spring 2015 semester.

This material is protected by United States and international copyright law and may not be reproduced, distributed,

transmitted, displayed, published or broadcast without the prior written permission of the copyright holder. You may not alter

or remove any trademark, copyright or other notice from copies of the material.

The Java Learning Kit: Chapter 3 – Programming Logic

Lesson 3.1 – Boolean Logic in Branching and Looping

Lesson 3.2 – The Nature of Algorithms

Lesson 3.3 – Conditional Execution (Branching)

Lesson 3.4 – Enumerated Data Types in Java

Lesson 3.5 – Lab Reports and Collaborative Editing

Lab 3A – Program Design: Body Mass Index

Lab 3B – Multiple Branching

Lab 3C – Quadratic Equations

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 2

Contents Chapter 3 – Programming Logic .................................................................................................................. 4

Boolean Logic in Branching and Looping ......................................................................... 5

Boolean Relational Operations ........................................................................................................... 6

Boolean Relational Operators in Java ................................................................................................. 6

Boolean Logical Operations ................................................................................................................ 8

Boolean Logical Operators in Java .................................................................................................... 11

Boolean Expressions Using boolean Variables .................................................................................. 11

CheckPoint 3.1 .................................................................................................................................. 12

The Nature of Algorithms .............................................................................................. 13

Turing Machines and the Church-Turing Thesis ................................................................................ 14

Elements of Logical Structure in Algorithms ..................................................................................... 17

Tools for Describing Algorithms ........................................................................................................ 20

Linear Sequences .............................................................................................................................. 24

CheckPoint 3.2 .................................................................................................................................. 25

Conditional Execution in Algorithms - Branching .......................................................... 25

Binary Branching – Bypass vs. Choice ............................................................................................... 25

Binary Branching in Java ................................................................................................................... 26

Multiple Branching ............................................................................................................................ 27

Nested if…else Statements in Java .................................................................................................... 30

The switch Structure in Java .............................................................................................................. 33

Choosing between Nested if…else and switch .................................................................................. 34

CheckPoint 3.3 .................................................................................................................................. 35

Enumerated Data Types in Java..................................................................................... 36

CheckPoint 3.4 .................................................................................................................................. 38

Lab Reports and Collaborative Editing .......................................................................... 39

Computer Science 111 Lab Report .................................................................................................... 39

Collaborative Editing of Word Documents ........................................................................................ 40

Tracking Changes .............................................................................................................................. 40

Document Comments ....................................................................................................................... 41

Programming Design Example – Body Mass Index ........................................................ 41

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 3

Programming Exercise – Looking at Multiple Branching NetBeans Projects ................. 44

Programming Design Exercise – Quadratic Equations ................................................... 47

Key Terms in Chapter 3 ......................................................................................................................... 50

Chapter 3 – Questions .......................................................................................................................... 51

Chapter 3 – Exercises ............................................................................................................................ 52

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 4

Chapter 3 – Programming Logic This chapter is about branching – conditional execution of code segments that depends on the

result of Boolean logic in a computer program.

The chapter begins with a look at relational operations that compare values to yield true or false

results, such as less than or greater than, and logical operations that combine and modify such

values in boolean expressions, such as if (hours > 40.0 and rate > 12.50).

The nature of algorithms and their structure are briefly examined, including the concept of a

Turing machine and its importance in the history of computer science and math. The bulk of the

chapter is about branching in Java. Repetition of a code segment in an algorithm, also known as

looping, will be covered in the next chapter.

Learning Outcomes

Upon completion of this chapter students should be able to:

 list and describe the six comparison operators and the three primary logical operators used in

Boolean logic;

 describe the use of comparison and relational operators in forming Java boolean expressions;

 describe the concept of a Turing machine and the nature and importance of the Church-Turing

Thesis;

 list and describe the three elements of logical structure in algorithms;

 describe the difference between a binary bypass and a binary choice in the logic of an algorithm;

 describe the concept of multiple branching and how it relates to binary branching;

 describe the use of the if statement for establishing conditional execution in Java;

 describe the use of the if…else statement for establishing multiple branching in Java, and how to

establish nested if…else structures in Java;

 describe the proper use of the switch statement for establishing multiple branching in Java, and

the use of the break statement in a switch structure in Java;

 create Java code that demonstrates correct use of each of the following: conditional execution,

multiple branching with an if…else structure, and multiple branching with a switch structure;

 describe the nature and use of enumerated data types in Java;

 describe the requirements of a properly organized programming lab report for Computer

Science 111, and how to use Microsoft Word’s track changes and commenting features to

collaboratively edit lab reports.

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 5

Boolean Logic in Branching and Looping

In chapter one we saw Java’s boolean data type, whose variables have the values true and false. The

data type is named for George Boole, a brilliant self-taught mathematician with little formal training who

became the first Professor of Mathematics at Queen’s College in Cork, Ireland. Boole wrote two books

that laid a foundation for what are today known as Boolean logic and Boolean algebra: The

Mathematical Analysis of Logic (1847) and An investigation into the Laws of Thought, on which are

founded the Mathematical Theories of Logic and Probabilities (1854).²

The digital logic that is today the basis of both computer hardware and computer software evolved over

a period of about 90 years following Boole’s first publications on the subject. Many people contributed

to perfecting Boole’s ideas, in particular Augustus De Morgan at London University, London economist

and mathematician William Stanley Jevons, and Claude Shannon, a Bell Labs mathematician and

electrical engineer who developed digital circuit logic.

Boolean logic is a system of logic dealing with operations on the values 1 and 0, in which 1 can represent

true and 0 can represent false. We will use the values true and false in discussing Boolean operations.

Boolean algebra is a formal language for describing operations on true and false values based on

Boolean logic. Boolean algebra is covered in Math 121, Math 163 and several other courses at

Community College of Philadelphia.

Computers derive Boolean true and false values primarily by comparing things. For example, a condition

in a payroll program might compare the number of hours a person worked to the value 40 to see if the

person should receive overtime pay:

if (hours are greater than 40)

calculate overtime pay;

The condition (hours are greater than 40) will be true or false. If it is true, then the computer will

be directed to calculate overtime pay, if it is false, the computer will ignore this directive.

Simple conditions such as these can be combined or modified using logical operations to form

compound conditions, such as:

if ( (burglar alarm is on) AND (door is open) )

sound alarm;

There are two simple conditions in this case that both need to be true for the alarm to sound.

In this section we will look at the comparisons that yield true and false results and the formal language

for specifying them in Java. We then look at logical operations like the AND operation that form

compound conditions in the next section, then see how boolean logic forms branching and looping

sequences in the structures of algorithms.

In Chapter 2 we saw that the term Boolean, referring to Boolean logic and Boolean algebra, is

capitalized, while the term boolean, referring to a Java a data type, is not capitalized.

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 6

Boolean Relational Operations

In Java programming, a boolean variable assigned a true or false value by using the boolean literals true

or false, or by using an assignment statement with boolean expressions:

A boolean variable can be set to true or false, such as in the following:

boolean citizen;

citizen = true;

The terms true and false are known as boolean literals. Boolean literals are tokens that represent the

values true and false in Java code. They are not Strings. There are only two boolean literals – true and

false.

We can also obtain a true or false value by using relational operations in Boolean expressions. A

relation operation is a comparison of two values to see if they are equal, or if one is greater or lesser

than the other. A relational operation forms a boolean expression that may be true or false. The

relational operations are indicated by relational operators for equality and inequality. A boolean

expression is an expression that evaluates to a true or false value.

For example, the expression (x < 3) can be evaluated for a specific value of x. When x is 2, the

expression evaluates to true; when x is 4, the expression evaluates to false.

Boolean Relational Operators in Java

In general, there are six relational operations in Boolean logic. The table below describes each of the six,

along with the operators used for them in math and in Java programming.

Boolean Relational Operations

Condition math Java Examples A equals B A = B (A == B) zipcode == "19130"

A is not equal to B A ≠ B (A!= B) root != 0.0

A is less than B A < B (A < B) name < "Miller"

A is greater than B A > B (A > B) temperature > 98.6

A is less than or equal to B A ≤ B (A <= B) rate <= 12.50

A is greater than or equal to B A ≥ B (A >= B) bedrooms >= 3

Note that the logical operator for equals uses two equal signs together, as opposed to the operator in

Java assignment statements that uses a single equal sign. The equals and not equals operators are

sometimes referred to as equality operators.

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 7

The six common Boolean operators in Java are used primarily with primitive values, but not with objects.

However, the equality operator (==) will return true if two Strings are the same. We will learn how to

compare objects and how to perform other comparison operations on Strings later in the semester.

Simple boolean conditions for branching in Java each have a single conditional operation in parentheses

following the keyword if, as in the following example:

if (hours > 40) {

overtimeHours = hours - 40.0;

overTimepay = overtimeHours * rate * 0.5;

} // end if (hours > 40)

In this case, the condition is immediately followed by a brace, starting a new block of code. If the

condition is true, then the entire block of code will be executed. If the condition is false, the computer

will skip the block of code and move on to whatever comes next in the code. This is an example of

conditional execution.

If we compare numbers, then it is obvious what the less than and greater than operations mean, but

what about the char data type in Java?

A collating sequence is used for comparison of text data. A collating sequence is a defined order of

characters for a particular alphabet or set of symbols. The version of the Latin alphabet used for the

English language is an example of a collating sequence – {A, B, C, … Z}. It seems simple, but almost

immediately complications can arise. What is the order of the characters if we have both uppercase and

lowercase characters? Here are three different collating sequences based on the English version of the

Latin alphabet with both uppercase and lowercase characters:

Three Collating Sequences for the English Alphabet

1. {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}

2. {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z}

3. {A,a,B,b,C,c,D,d,E,e,F,f,G,g,H,h,I,i,J,j,K,k,L,l,M,m,N,n,O,o,P,p,Q,q,R,r,S,s,T,t,U,u,V,v,W,w,X,x,Y,y,Z,z}

All three sequences use the traditional A-Z order learned by children, but differ as to how they handle

upper and lower case letters. In the first sequence, uppercase letters come before lowercase letters. In

the second sequence lowercase letters are first, or less than the upper case letters. The third sequence

is more traditional, with the uppercase and then the lowercase version of each character coming before

the uppercase and lowercase version of the next character in the A-Z sequence. (Can you see what a

fourth sequence might be?)

Consider the order of four characters a, A, b, and B according to the three sequences above.

 Using the first sequence, B comes before a because uppercase B comes before lower case a; B is

less than a. The four characters in order would be A, B, a, and b.

 Based on the second sequence, b comes before A because lowercase b comes before uppercase

A. The four characters in order would be a, b, A, and B.

Figure 1 –

Block of code in an if statement

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 8

 The third sequence, which is more commonly used in everyday language, indicates that the

order of the four characters should be A, a, B, and b.

We also need to consider non-alphabetic symbols in a collating sequence for text data. Do the symbols

for numeric digits come before or after letters of the alphabet? What about special symbols, such as the

question mark, the dollar sign, and the ampersand? What about symbols from other alphabets?

As we saw in the previous chapter, most modern computer programming languages, including Java, use

the defined order of the Unicode UTF-16 character set as the collating sequence for text data. So do

most modern operating systems, including all current versions of Microsoft Windows, Apple OS X, and

most newer Linux and Android operating systems.

Each Unicode character has a code number. The order of the code numbers is the order of the

characters when Unicode is used as a collating sequence. Here is a chart showing part of the UTF-16

code1 in order. The entire UTF-16 code has over 64,000 characters (216 = 65,536) characters:

A Portion of the UTF-16 Version of Unicode ! " # $ % & ' ( ) * + - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ?

@ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _

` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~

Each line in the chart is a continuation of the previous line. The chart shows us that the numeric digits

come before uppercase letters, which come before lowercase letters. Symbols other than alphanumeric

characters are in different parts of the code; some before alphanumeric characters, some after.

A String value is a sequence of characters. When we learn more about Strings, we will see that the

Unicode sequence is also used to compare String values, character by character.

Boolean Logical Operations

Simple boolean conditions based on comparing values can be combined using Boolean logical

operations to form compound conditions, such as the burglar alarm condition mentioned earlier:

(burglar alarm is on) AND (door is open)

There are three primary logical operations in Boolean logic:

 conjunction, represented by the word AND

 disjunction, represented by the word OR

 negation, represented by the word NOT

The AND operator takes two Boolean operands and yields a Boolean result. If both operands are true,

then the result is true, otherwise the result is false. If either operand is false, the result is false.

1 For detailed information on Unicode, see the Unicode Consortium Website, online at: http://www.unicode.org/

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 9

The OR operator takes two Boolean operands and yields a Boolean result. If both operands are false,

then the result is false, otherwise the result is true. If either operand is true, the result is true.

The NOT operator is a unary operation; it takes one Boolean operand and yields a Boolean result. If the

operand is true, the result is false. If the operand is false, the result is true. This is known as inverting a

Boolean value. The NOT operation inverts the true or false value of the operand.

The table below defines the three primary Boolean logical operations:

AND OR NOT

false AND false -> false

false AND true -> false

true AND false -> false

true AND true -> true

false OR false -> false

false OR true -> true

true OR false -> true

true OR true -> true

not(false) -> true

not(true) -> false

The AND and OR operations are both commutative and associative:

commutative (a AND b) = (b AND a) (a OR b) = ( b OR a) associative (a AND b) AND c = a AND (b AND c) (a OR b) OR c = a OR (b OR c)

AND and OR operations are not distributive with regard to the NOT operation. You may recall from

elementary algebra that the distributive law involves two different operations. For example,

multiplication is distributive over addition, as in these two examples:

a*(b+c) = (a*b) + (a*c) 3(x+y) = 3x + 3y

We often use this in reverse to simplify expressions:

17x + 11x = 28x;

We might be tempted to say that NOT(a AND b) = NOT(a) AND NOT(b), but this is incorrect; the NOT

operation is not distributive with respect to AND, nor with respect to OR. Instead De Morgan’s laws

apply.

De Morgan’s Laws

NOT (a AND b) = NOT(a) OR NOT (b) NOT(a OR b) = NOT(a) AND NOT (b)

Like the distributive law in elementary algebra, De Morgan’s laws are often used in reverse in computing

and logic to simplify Boolean expressions.

De Morgan’s laws were developed by George Boole’s contemporary, Augustus De Morgan, who, at age

22 became the first professor of Mathematics at the University of London, shortly after it was founded.

In addition to the primary Boolean operations, there are derived Boolean operations, so named

because they can be derived from the three primary operations. The most common of these are NAND,

NOR, and XOR. These derived Boolean operations are important in the design of modern computer

chips because they are easy to mass-produce in electronic logic circuits (called gates) at a microscopic

level. Some chips are composed entirely of NAND gates or of NOR gates.

NAND NOR XOR

a NAND b = NOT(a AND b) a NOR b = NOT(a OR b) a XOR b = (a OR b) AND NOT(a AND b)

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 10

Toward That Grand Prodigy: A Thinking Machine

In 1984, Oxford University Press published The Boole-De Morgan Correspondence, 1842-1864, containing a collection of more than 90 letters between the two friends. George Boole in Cork and Augustus De Morgan in London laid the foundation for modern digital logic. In the Spring of 1847 Boole published Mathematical Analysis of Logic. Later that year De Morgan published Formal Logic or The Calculus of Inference. Much of modern digital electronics and computer programming is based on their work. Boole died from pneumonia in 1864 at age 49. De Morgan went on to found the field of Relational Algebra, the basis for most modern database management systems.

Boole and De Morgan were part of a British circle of acquaintances important in the history of computing, including Charles Babbage and Ada Augusta Lovelace. Most of their writing is available freely online, including their books, papers, and letters.

One interesting artifact is a letter of condolence to Boole’s wife from Joseph Hill describing a meeting of Boole and Babbage at the Crystal Palace Exhibition of 1851. In it Hill wrote:

… Mr. Babbage arrived and entered into a long conversation with Boole. Oh, the scene would have formed a good subject for a painter. As Boole had discovered that means of reasoning might be conducted by a mathematical process, and Babbage had invented a machine for the performance of mathematical work, the two great men together seemed to have taken steps towards the construction of that grand prodigy – a Thinking Machine.”

A copy of Boole’s The Mathematical Analysis of Logic is available online at Project Guttenberg (along with his other works): http://www.gutenberg.org/ebooks/36884

De Morgan’s Formal Logic or The Calculus of Inference is at the Internet Library: https://archive.org/details/formallogicorca00morggoog

A copy of Babbage’s On the Application of Machinery to the Purpose of Calculating and Printing Mathematical Tables is available online from the Hathi Trust Digital Library: http://hdl.handle.net/2027/mdp.39015004166164

Lovelace’s translation and notes from Menabrea’s Sketch of the Analytical Engine is available in its 1843 published form at Google Books: http://books.google.com/books?id=qsY- AAAAYAAJ&pg=PA666&source=gbs_toc_r&cad=3#v=onepage&q&f=false

Text from and images of Hill’s letter to MaryAnn Boole can be found online in the University of Cork’s Boole Papers Collection: http://georgeboole.ucc.ie/index.php?page=11#S01BIx

George Boole 1815-1864

Augustus De Morgan 1806-1871

Charles Babbage 1791-1871

Ada Augusta Lovelace 1815-1852

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 11

Boolean Logical Operators in Java

Compound Boolean conditions in Java are formed by using Boolean logical operations AND, OR and NOT

to combine and modify simple conditions. The Java symbols used for the Boolean logical operators are:

Operation Operator Notes

AND && two ampersands with no space in between

OR || two vertical lines with no space in between*

NOT ! a single exclamation point

* Although there is no standard location on the keyboard for the vertical line character, it’s

often on a key above the Enter key,. It is a straight vertical line, sometimes with a break in

the middle. It goes by other names, including the pipe or pipeline character, but the official

Unicode name for the character is the vertical line. It is Unicode 007c.

Logical operations have an order of precedence just as numeric operations do. Parentheses may be used

to group logical operations to specify an order, just as with numeric expressions. In the absence of

parentheses, AND has precedence over OR.

NOT modifies whatever immediately follows it. If a parenthesis follows NOT, then everything in the

parentheses is resolved to a boolean value, which is then reversed by the NOT operation.

Here are examples of boolean expressions using AND, OR, and NOT:

// hours > 40 and status == “hourly” // score > 99 and score < 1,000 ( (hours > 40) && (status == “hourly”) ) ( (score > 99) && (score < 1000) )

// (wordCount > 1000) or (pageCount > 5) // month < 1 or month > 12 ( (wordCount >1000) || (pageCount > 5) ) ( (month < 1) || (month > 12) )

// not(x < 3) or not (y < 4) // not ( ( X < 3) and (Y < 4) ) ( !(x < 3) || (!(y < 4) ) !( ( x < 3 ) && ( y < 4) )

Can you see how the bottom expressions in the examples above are related to De Morgan’s laws?

Boolean Expressions Using boolean Variables

Recall that a boolean variable has a true or false value, so a boolean condition testing for true only needs

the name of the variable, not a comparison, to be true. The statement to test if innerDoorClosed is true

would be

if(innerDoorClosed),

rather than

if (innerDoorClosed == true).

Conversely, to test for false, the condition would be

if ( !(innerDoorClosed) ).

Figure 2 –

compound

Boolean expressions

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 12

CheckPoint 3.1

1. How do computers derive Boolean values?

2. What are the six boolean comparison operators in Java that can be used with primitive values?

Which of these operators works with String values?

3. What do each of the three primary Boolean operations (conjunction, disjunction, and negation)

do, and what word is associated with each one?

4. What are the symbols in Java for the three primary boolean operations?

5. Describe two forms of De Morgan’s Laws, and how De Morgan’s laws are related to the

distributive properties of AND and OR.

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 13

The Nature of Algorithms

We saw in chapter one that an algorithm is a step-by-step process and that computer programs are

algorithms. In Java, as in all object-oriented programming, algorithms are implemented as methods

within objects. Here we will begin to focus on the nature of algorithms. What can we do and what can’t

we do with algorithms? How are algorithms structured?

Algorithms contain the steps necessary to complete a task or solve a particular problem. Algorithms are

a part of everyday life. A recipe for baking a cake will have a list of all the ingredients needed for the

cake and instructions for what to do with those ingredients. The recipe provides an algorithm for baking

a cake. A child who learns to perform long division is learning an algorithm. A doctor can follow an

algorithm to diagnose a patient’s illness. Professionals, such as engineers, architects, and accountants,

use many different algorithms in the course of their work. Some algorithms are simple; some can be

quite long and complex. The Holtrop and Mennen Algorithm used to design the optimum propeller for

an ocean going vessel uses techniques of matrix algebra with thousands of steps and must be run on a

computer.

Even though algorithms are an important part of life all around us, they are not the kind of thing that

most people spend time thinking about. So, how much do we really know about the nature of

algorithms? How much do we need to know? Mathematicians, engineers, and computer scientists need

to know quite a bit about them, beginning with the question: What can and can’t be done by following

an algorithm?

Figure 3 –

applied algorithms

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 14

Turing Machines and the Church-Turing Thesis

in the 1930s a young mathematician at Cambridge University named Alan Turing was considering the

question: Is there an algorithm to determine if any given problem can be solved with an algorithm? To

answer his question, he came up with the concept of a simple theoretical machine that could follow any

algorithm. Today we call his machine a Turing machine.

One of the burning questions in mathematics In the late 1800s and early 1900s, was the decidability

question: Is there a method we can use to look at any math problem and decide if the problem can be

solved? To answer this question, we need a Boolean test – one with a clear yes or no answer – yes, this

problem can be solved, or no, this problem can’t be solved. We need one test that works for all

problems. Some of the best mathematicians of the time – people such as David Hilbert, Kurt Gödel, and

Alonzo Church – worked on what Hilbert called the Entscheidungsproblem (German for decision-making

problem). It turns out that Turing’s question is equivalent to the Entscheidungsproblem.

The truth of mathematics and logic for all real numbers is based on first and second order predicate

logic and a set of axioms, called Peano’s Axioms, after the 19th Century Italian mathematician who

described them. Hilbert and company were trying to prove that math is complete, consistent and

decidable. They had trouble with the decidability part – the Entscheidungsproblem: Is there a method

we can use to look at any math problem and decide if the problem can be solved? 2

Turing realized that this question was the same as what he called the Halting Problem: For all computer

programs, is there a way to tell if any particular program that is running will halt, or continue to run

indefinitely? He thought of his Turing machine as one of the simplest of computing machines, which can

calculate what people can calculate. He thought of it as a tool to examine computation and algorithms.

The work of Alan Turing, along with the work of Alonzo Church from Princeton University, surprised the

world of mathematics by illuminating two important concepts in modern computer science:

1. All mechanical systems of algorithmic computation with real numbers are functionally

equivalent. That is, given an infinite amount of time and an infinite amount of memory, they

can compute exactly the same things. Today this is known as the Church-Turing Thesis. Church3

and Turing4, working independently of each other, released their results in the spring of 1936. At

the time, Church was a Princeton University math professor; Turing was a 23 year old student

who had finished his bachelor’s degree in 1934.

2. The answer to the halting problem, and hence the answer to the Entscheidungsproblem, was no,

math is not decidable. (Gödel suggested the same thing a few years earlier with his

Incompleteness Theorems, but his theorems proved to be incomplete.)

2 More specifically, Hilbert asked if there is an algorithm that can be used to decide if any given theorem is true.

3 Church, Alonzo, An Unsolvable Problem of Elementary Number Theory, Amer. Journal of Math., Vol. 58, No. 2. (1936)

4 Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc. (1937) s2-42

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 15

Church was working on a system to describe functional math called lambda calculus. Turing quickly

realized and showed in an appendix to his paper that Church’s theorems based on lambda calculus were

equivalent to his ideas based on the Turing machine; that whatever could be determined in Lambda

Calculus, or any other system of logic based on functional algorithms and Peano’s Axioms, could be

determined with a Turing machine. Church’s former student, Stephen Kleene, showed the same thing.

A Turing machine is a theoretical model for a very simple mechanical computer. A Turing machine has:

1. a tape broken up into separate squares, in each of which we can write a symbol. There is no

limit to the length of the tape, it is infinitely long. (Turing mentions that he chose a tape as it is

one-dimensional, as opposed to two dimensional sheets of paper.)

2. a read/write head for the tape. The square under the read/write head is called the current

square. The symbol the machine just read from the current square is called the scanned symbol.

3. a state register, which is a memory that can store the current state of the machine. There are a

finite number of possible states for the machine, listed in a state table.

4. a state table with entries for each possible configuration of state and scanned symbol. A state

table tells the machine what to do for each possible configuration (state, scanned symbol).

There is a special initial state we can call the start state.

The Turing machine has a machine execution cycle that works like this:

 read the symbol in the current square;

 lookup the configuration in the state table;

 perform an operation based on the lookup;

 set the new state of the machine.

The process is repeated indefinitely, or until the machine reaches a final state and halts.

In each operation, the machine can do one of three things - write a new symbol in the current square,

erase the current square, or leave the current square alone; it then moves the tape to the left one

square or to the right one square.

Figure 4 –

model Turing machine

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 16

Here is an example of a state table for a Turing machine:

state scanned symbol

operation* new state

S1 0 R S1 S1 1 P0, R S2 S2 0 R S2 S2 1 P0,R S3

*Pn means print n; L move left, R move right.

This example is only a small part of what could be a much longer state table. We program the machine

by establishing a state table then giving the machine a tape with symbols on it.

Turing was a pioneer in what has come to be known as automata theory. Automata theory is the study

of theoretical computing machines to explore the nature and scope of computation. It involves the

languages of such machines as well as how they operate and what they are able to do. The primary

focus of automata theory is not really the machines, but on learning more about computation, language,

and algorithms.

State diagrams are used in automata theory. A state

diagram shows the possible states of a system, and how the

system moves from one state to another. The state diagram

shown here is based on the turns players take in a game of

chess.

Each state is represented by a circle, and the events or

activities that cause a change in state are represented by

lines connecting the states. The initial state is represented

by a dark circle. The terminal states, or halting states, are

represented by dark circles with lines around them. The

example on this page shows a very simple view of the

moves in a game of chess. Turing’s state diagrams dealt

with combinations of elementary processes, in which it

takes time to understand the big picture. We shall skip

them for now.

The algorithm for players taking turns in a game of chess is

shown in pseudocode on the next page. In the pseudocode we can see some items that are also part of

Java, such as braces to indicate the beginning and end of a block of instructions. We can also see some

structured language that we have not yet learned about, such as the if and while instructions.

The if statement sets up conditional execution – part of the algorithm is only executed if a certain

condition is true. The while statement sets up repetition, part of the algorithm forms a loop that is

Figure 5 –

state diagram

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 17

repeated if a certain condition is true. The conditions are enclosed in parentheses. If you look back at

the state diagram, you can find branches and loops there as well. For example, white’s turn, then black’s

turn, then white’s turn, then black’s turn, and so on, is repeated until a checkmate or stalemate occurs.

We are looking at this from a higher-level, so we don’t see the details about board position that

determine if there is a checkmate or stalemate, nor do we see how a player decides what move to

make. Those algorithms would be far more detailed and require massive state tables and long

pseudocode, or more likely, be broken down into many smaller parts that would each be described in

separate units. Our purpose here is simply to see how tools such as state diagrams and pseudocode

illustrate algorithms with the simple example of the flow of moves in a game of chess.

// initialize variables

set checkmate to false;

set stalemate to false;

set result to “draw”;

// when the board is placed in a new position, checkmate and stalemate are set, if applicable

Start the game;

while (checkmate and stalemate are both false) {

white moves; // white puts the board in a new position

if (checkmate is now true)

result = “White wins”;

if (checkmate and stalemate are both false) {

black moves; // black puts the board in a new position

if (checkmate is now true)

result = “Black wins”;

} // end if (checkmate and stalemate are both false)

} // end while (checkmate and stalemate are both false)

print result;

Stop the game;

Elements of Logical Structure in Algorithms

Conditional execution and repetition form patterns in the sequential logic of algorithms. These patterns

fall into categories that can be understood as elements of logical structure, which can be combined in a

myriad of ways to form the algorithms we see in modern software. Programmers who are familiar with

elements of logical structure can more easily create and edit computer programs. They can use

elements of logical structure like building blocks as they design and build software.

Think about how this compares to a plumber or an electrician. A person who wishes to design a

plumbing system for a building, such as a residential home, has a selection of existing parts from which

to choose. We can see these parts in a hardware store – elbow joints, T- joints, certain kinds of valves,

Figure 6 –

chess pseudocode

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 18

and so on. Despite the differences from one home to another, the plumbing systems will mostly be

composed of the same parts, which we might think of as the elements of a plumbing system. The

architects and plumbers who will design and build the system need to know how to work with each of

the elements and how they fit together.

The same thing is true for an electrical system. The electrical engineers and electricians who design and

build such systems need to be familiar with the electrical parts that are available, how they work, and

how they fit together. Switches, wires, outlets, junction boxes, circuit breakers, and so on, can be

thought of as the building blocks or elements of electrical systems.

So it is with the logical structure of algorithms. The elements of logical structure are the building blocks

we can put together to design and create algorithms. But, just what are these elements of logical

structure? How many of them do we need to learn about? The answer is: surprisingly few.

We don’t need hundreds or even dozens of different kinds of parts such as plumbers and electricians

would need to build their systems. In 1966 two Italian computer scientists, Corrado Böhm and Giuseppe

Jacopini, published a paper in the Communications of the ACM showing that all algorithms are

composed of three basic elements of logical structure, each one a sequence of instructions: 5

 linear sequences

 selection sequences (conditional execution)

 repetition sequences

A more abstract equivalent of Böhm and Jacopini’s work

was contained in the work of Stephen Kleene in the

1930s, but Böhm and Jacopini’s 1966 paper captures the

move toward structured programming that was

happening in the 1960s and 1970s. Most modern

programming languages, including Java, have branching

and looping instructions based on what was happening

then with languages like ALGOL, C and Pascal, whose

underlying basis in sequential logic was described by

Böhm and Jacopini.

5Corrado Böhm, Giuseppe Jacopini Flow diagrams, Turing machines and languages with only two formation rules, Communications of the ACM, Volume 9 Issue 5, May 1966 available online at: http://dl.acm.org/citation.cfm?id=365646

Figure 7 –

Böhm and Jacopini flow diagrams

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 19

(People) != (Turing Machines)

Programmers must bridge the logical divide between the way computers work and the way

people think. Computers are algorithmic and precise. They follow instructions step-by-step

doing exactly what each instruction says to do, whereas, people are generally not

algorithmic.

People think heuristically. They are constantly looking for shortcuts and trying new ways

to do things. They are creative and intelligent, interpreting language to see what it really

means. But because of this, they often don’t follow directions very well, and are often

imprecise in their use of language. People are not Turing machines.

This can cause problems for programmers who must turn the heuristic logic of what people

say into the algorithmic logic of a computer program. Here is an example:

A boss says to a computer programmer: “Give me a list of all the people who live in

Pennsylvania and New Jersey.” What should the Boolean expression in our code look like,

assuming each person can only live in one state? The expression will be part of a loop,

looking at the data for each person, one at a time.

If we write (state == “PA” && state == “NJ”) our list will be empty. The variable state

cannot be equal to both PA and NJ at the same time. We need to write:

(state == “PA” || state == “NJ”) to get one list with each person who lives in Pennsylvania

or who lives in New Jersey. If state = “PA”, the condition will be true, and the person will

be included in the list. If state = “NJ”, the condition will be true and the person will be

included in the list. We will end up with one list with all of the people who live in

Pennsylvania and all of the people who live in New Jersey.

The boss is not using proper Boolean language. Yet, a programmer who understands

Boolean logic will most likely understand the boss and translate the request properly. This

example illustrates the difference between how people think and how computers work. It

also shows that programmers are often called upon to help bridge that gap.

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 20

Tools for Describing Algorithms

Böhm and Jacopini used a system they called flow diagrams to describe their work. Figure 7 on page 18

is an image from their manuscript showing basic flow diagrams. They weren’t the first to use such

diagrams, which had been around in business and industry since the 1920s. The diagrams later became

known as flowcharts. A flow chart is a diagram showing the logical flow and structure of an algorithm.

In CSCI 111, 112, and 211 we will see many other tools for describing software systems in general and

algorithms in particular, such as state tables and pseudocode like we saw above, and various UML

diagrams. For now, we will use two simple tools to illustrate the elements of logical structure in

algorithms: simple flowcharts, similar to Böhm and Jacopini’s, and pseudocode.

Today pseudocode is the most common tool used to describe and discuss algorithms. We saw in

chapter 2 that pseudocode is somewhere between a human language like English and a formal coding

language like Java. It might be thought of as structured English, which is easy to read, but which has

language structures such as [if…then…else…] and [for count = 1 to n] to describe branching and looping

in algorithms.

The following example describes an algorithm using both pseudocode and a flowchart.

* * * * * * * * * * * * * * * Guessing Game Example * * * * * * * * * * * * * * * * * * * * * * * * * * * *

We wish to create a computer program for a guessing game. The computer will pick a random integer

between 1 and 100, and then ask the user to guess the number.

If the user’s guess is not correct, then the program should tell the user that the guess is either too low or

too high and allow the user to guess again. This process should continue until the user enters the

correct guess. Once the user enters the correct guess, the computer should tell the user that the guess

is correct, along with the number of guesses it took to get the correct number.

Here is a sample run of the program:

I am thinking of a number between 1 and 100.

Try to guess what it is.

Your guess?

50

Too low. Try again.

Your guess?

75

Too High. Try Again.

Your guess?

63

Too Low. Try Again.

Your guess?

69

Too High. Try Again.

Your guess?

66

Too High. Try Again.

Your guess?

65

Too High. Try Again.

Your guess?

64

Correct! The number is 64

It took you 7 guesses

The psuedocode for the algorithm is shown on the next page:

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 21

start

int pick // the number the computer picks

int guess = 0 // the user’s guess, initialized to zero

int count = 0 // the number of guesses

pick = a random number between 1 and 100

print “I am thinking of a number between 1 and 100.”

print ”Try to guess what it is.”

print” Your guess?”

user inputs guess // get value of guess from the keyboard input

while (guess ≠ pick) // set up a loop to repeat until the user guesses the number

{

increment count // keep track of how many guesses

if (guess < pick) // in the loop guess cannot equal pick: it will be low or high

print “Too low. Try again.”

else

print “too high. Try again.”

print ”Your guess?”

user inputs guess // get value of guess from the keyboard input

} //end while (guess ≠ pick), the loop ends when guess = pick

print “Correct. The number is ” + pick

print “It took you ” + count + “ guesses”

stop

We can see in the above example that pseudocode is somewhere between English and a programming

language. Quoting from the book Introduction to Algorithms by Cormen, Lierson and Rivest: 6

“What separates pseudocode from ‘real’ code is that in pseudocode, we employ whatever

expressive method is most clear and concise to specify a given algorithm. Sometimes the clearest

method is English, so don’t be surprised if you come across an English expression or phrase

embedded within a section of ‘real’ code. Another difference between pseudocode and real code

is that pseudocode is not typically concerned with issues of software engineering. Issues of data

abstraction, modularity, and error handling are often ignored in order to convey the essence of

the algorithm more concisely.”

6 Cormen, Thomas; Lierson, Charles; and Rivest, Ronald; An Introduction to Algorithms; MIT Press; 1990 pg. 2 This text is an important work on algorithms, used in many advanced courses in algorithms.

Figure 8 –

guessing game pseudocode

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 22

Pseudocode often uses mixed terminology – language from both the problem domain and the

implementation domain. The problem domain is the environment in which the need for software arises,

such as a specific business or engineering environment. It is the world of the user of an application. The

implementation domain for software is the programming environment. Pseudocode is developed as we

move from specifications in the problem domain to code in the implementation domain. We need to

watch for terms from the problem domain that have specialized meaning, perhaps working with an

expert on the problem domain or a specially trained systems analyst to clarify language.

Pseudocode uses programming terms from the implementation domain, such as if…else and while, that

have a specific meaning for people with knowledge of structured programming languages, such as C,

C++, Java, and Python. Terms such as if, while, and for, generally are used the same way in pseudocode

as in these languages. We will use such terms as they are defined in Java, but with less formal syntax. As

we learn about conditional execution and repetition in Java, we will be learning terminology needed to

understand pseudocode.

The flowchart for the same algorithm as the pseudocode in Figure 8 is shown here:

A flowchart may appear to be more formal and precise than pseudocode, but looks can be deceiving.

Details about such things as initializing variables, how variables are used in conditions, how messages

Figure 9 –

guessing game flowchart

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 23

are displayed, and so on, often are not shown in a flowchart. A flowchart is a good map of the logical

flow in an algorithm, illustrating branching and looping very well, but often lacking other critical details.

In an attempt to rectify this, companies like IBM in the mid-to-late 20th Century introduced many

additional flowchart symbols and rules. IBM actually had a 40-page manual for flowcharting with

several dozen different symbols and a series of templates to draw flowcharts by hand, like the one

shown here:7.

However, drawing complicated flowcharts can make programming more cumbersome, not easier.

Today the use of complicated flowcharts in software development has fallen out of favor, in part

because of better use of structured language and the emergence of UML. They are still used to define

business processes, in accordance with ISO standards for business process management and information

systems, but used far less often by programmers to describe the details of an algorithm. We will use a

simple version of flowcharting to illustrate the elements of logical structure found in our algorithms.

Böhm and Jacopini’s flow diagrams were very simple. They had only two symbols: rectangles to show

each step in an algorithm, and diamond-shaped boxes to show what they called a logical predicative.

More commonly, a logical predicative is called a predicate or a conditional. To say that one thing is

predicated on another means that one thing is determined by another. In other words, there is some

condition that will determine what happens next.

We will use only four symbols: rectangles and diamonds as Böhm and Jacopini did, along with a black

circle marking the beginning of an algorithm and black circles with another circle around them to

represent the end of an algorithm. These symbols are the same as those used in UML activity diagrams.

Effectively, we are using UML activity diagrams to illustrate the logical structures found in all algorithms

– linear sequences, selections sequences (branching) and repetition sequences (loops).

7 IBM flowcharting template courtesy of Walt Johnson, retired CCP professor of Computer Information Systems and former IBM Systems Engineer.

Figure 10 –

IBM flow chart template

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 24

individual steps in an algorithm are shown on a flowchart using rectangles. There is one line entering

each rectangle and one line exiting each rectangle to show the flow of a sequence of instructions. A

diamond is used when branching occurs, with the condition for branching clearly stated in the diamond

and multiple exits from the diamond, each with labels showing which values will cause the branching

routine to select that branch of the algorithm. One-way connecting lines should be vertical or horizontal

only, with directional arrows (but not too many arrows). In general, since a flowchart is used to help us

see the logical structure of an algorithm, we should keep it clear and concise, doing what we can to

make it easy to understand.

In the rest of this chapter we will briefly look at linear sequences, then focus on conditional execution –

also known as branching. We will explore repetition in the next chapter.

Linear Sequences

The simplest element of logical structure in an algorithm is a linear sequence, in which one instruction

follows another as if in a straight line. The most notable characteristic of a linear sequence is that it has

no branching or looping routines – there is only one path of logic through the sequence. It does not

divide into separate paths, and nothing is repeated.

On a flowchart or activity diagram, this appears just as the name suggests, as a single path of logic,

which would always be executed one step after another, as shown here.

Linear sequences seem simple, but programmers need to make sure that linear sequences meet the

following criteria:

 They should have a clear starting and ending point.

 Entry and exit conditions need to be clearly stated. What conditions need

to exist before the sequence starts? What can we expect the situation (the

state of the system) to be when the sequence is finished?

 The sequence of instructions needs to be complete. Programmers need to

be sure not to leave out any necessary steps. (This can be harder than you

might expect.)

 The sequence of instructions needs to be in the proper order.

 Each instruction in the sequence needs to be correct. If one step in an

algorithm is incorrect, then the whole algorithm could be incorrect.

In short, linear sequences must be complete, correct, and in the proper order, with clear entry and exit

conditions.

Linear sequences can be identified in pseudocode by the absence of branching and looping instructions

– one instruction after another with no language indicating branching or looping. The same is true in

most computer programming languages.

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 25

CheckPoint 3.2

1. What does the Church-Turing Thesis tell us?

2. What is a Turing machine and how is it related to Automata Theory?

3. List and briefly describe the three elements of logical structure in algorithms, as shown by Böhm

and Jacopini.

4. What are pseudocode and flowcharts and how are they used to describe algorithms?

5. Summarize the criteria that should be met by linear sequences in algorithms.

Conditional Execution (Branching )

A selection sequence, or conditional execution, occurs whenever the path or flow of sequential logic in

an algorithm splits into two or more paths. As an example of a selection sequence, consider this

example of a student who has chemistry lab at 2:00 p.m. on Fridays only:

start

if (Today is Friday)

(Get to chemistry lab by 2:00 p.m.)

stop

Each path is called a branch, so selection sequences are also

known as branching routines. They establish conditional

execution of part of an algorithm.

Binary Branching – Bypass vs. Choice

Whenever conditional execution divides an algorithm into two, and only two, possible paths we have

binary branching. If there are more than two paths, then it is called multiple branching. “Would you

like vanilla ice cream?” is a binary question – it has two possible answers, yes and no. “What flavor ice

cream would you like?” is a question with multiple possible answers, not just yes or no. Binary branching

is similar to the first question above; multiple branching is similar to the second.

There are two forms of binary branching: a binary bypass and a binary choice.

binary bypass

binary choice

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 26

In a binary bypass, part of an algorithm is either executed or bypassed. In a binary choice, one of two

parts of an algorithm is chosen. The difference between a bypass and a choice is subtle but significant.

In a binary bypass, it is possible that nothing happens, whereas in a binary choice, one of the two

instructions will be executed, but not both.

In pseudocode, a bypass is equivalent to: IF (condition) THEN (instruction) structure. (Note that in all of

these examples a single instruction could be replaced by block of instructions.) If the condition is true,

then the instruction is executed; if the instruction is not true, then the instruction is ignored, and

nothing happens. The chemistry lab example above shows a binary bypass.

A binary choice is equivalent to an IF (condition) THEN (instruction A) ELSE (instruction B) structure. If the

condition is true, then instruction A is executed; if the instruction is not true, then instruction B is

executed. Either instruction A or instruction B will be executed, but not both. One of the two is always

executed, as seen in the example below.

A student has Math class on Monday, Wednesday, and Friday, and History class on Tuesday and

Thursday. We will assume the student only needs to consider weekdays and not weekends:

start

if (today is Monday, or today is Wednesday, or today is Friday)

(go to math class)

else

(go to history class)

stop

The student will always go to either Math class or History class, but not both at the same time.

Binary Branching in Java

The if and if … else statements set up binary branching in Java. The if statement sets up simple

conditional execution, sometimes also called a binary bypass as we saw above. If the condition is true,

the instruction or block of instructions following the if statement is executed; if the condition is false,

the instruction or block of instructions is bypassed. The terms if and else in Java are both lowercase. The

boolean condition following if should be in parentheses. Figure 12 on the next page has several

examples.

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 27

// example 1 - if statement - simple conditional execution – binary bypass

if (temp > 98.6)

System.out.println("The patient has a fever");

// example 2 – if statement – binary bypass – a block of code

if (temp > 98.6) {

System.out.println("The patient has a fever.");

System.out.println("Please have blood work done to check for an

infection.");

} // end if (temp > 98.6)

// example 3 – if else statement – binary choice

if (temp > 98.6)

System.out.println("The patient has a fever");

else

System.out.println("The patient’s temperature is normal");

//example 4 – if statement – binary bypass – checking a range of values

if (temp > 97.0) AND (temp < 99.0)

System.out.println("The patient’s temperature is in the normal range.”);

//example 5 – if else statement – binary choice – two blocks of code

if (temp > 98.6) {

System.out.println("The patient has a fever.");

System.out.println("Please have blood work done to check for an infection.");

} // end if (temp > 98.6)

else {

System.out.println("The patient’s temperature is normal.");

System.out.println("Please check blood pressure and pulse.");

} // end else (temp > 98.6)

Multiple Branching

As we saw above, multiple branching occurs when the path of logic in an algorithm divides into many

different paths based on a single condition, such as “What flavor ice cream would you like?” It is not a

true or false question, but one with many different possible answers.

A flowchart showing this might look something like a pitch fork, as shown in Figure 13, on the next page:

Figure 12 –

examples of

binary branching

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 28

A multiple branching routine is equivalent to a series of binary branching routines. Consider the ice

cream question. Instead of asking the multiple branching question, “What flavor ice cream would you

like?”, a series of binary questions could be asked – “Would you like vanilla ice cream?”, “Would you like

chocolate ice cream?”, “Would you like strawberry ice cream?”, and so on.

There are two ways to do this: as a collection of independent binary branching routines or as a collection

of nested binary branching routines.

Independent binary branching could be an inefficient solution. Consider the following psuedocode:

if (flavor = vanilla)

get vanilla

if (flavor = chocolate)

get chocolate

if (flavor = strwaberry)

get strawberry

…and so on.

If the flavor does equal vanilla, the if routines that follow for chocolate, strawberry, and so on, are still

executed, even though we know that they will be false.

A better solution is to implement a series of nested binary branching routines. If the answer to any one

of these questions is yes, then the branching is complete, if not, then the algorithm moves on to the

next binary selection.

Figure 13 –

multiple branching

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 29

The flowchart and pseudocode in Figure 14 on this page shows the same ice cream question as above,

but as a series as a series of nested if… else… statements, with the second if… else… enclosed in the else

portion of the first if… else… , the third nested in the else portion of the second if… else…, and so on.

start

if (flavor = vanilla)

get vanilla

else

if (flavor = chocolate)

get chocolate

else

if (flavor = strawberry)

get strawberry

else

if (flavor = pistachio)

get pistachio

else

get chocolate chip

deliver

stop

We can see in the pseudocode that if any one of the if conditions is true, the remaining if routines are

bypassed. This is a result of the nesting.

The flowchart matches the pseudocode logically and shows that as soon as there is a true condition we

break out of the chain of if… else… statements. However, its arrangement doesn’t give the same clear

impression of the nested if.. else… structure that the pseudocode does.

The flowchart in Figure15 on the next page is logically the same, but it shows the if… else... nesting more

clearly.

Figure 14 –

nested if...else statements

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 30

Nested if…else… statements are preferable to a series of independent if statements, but they can

become messy and prone to errors if there are too many choices. What happens if the ice cream shop

has 28 flavors? The preferred way to handle many choices is by table lookup or through associative

arrays, which are covered in CSCI 211 – Data Structures. We could also use a switch block, as discussed

later in this chapter.

Nested if…else Statements in Java

A nested if…else structure is really just a specialized use of a set of if…else statements, but it is unique

enough to be discussed as a separate category. Two different styles are used for this in Java, as shown in

examples 6 and 7 below in Figures 16 and 17. The way in which we organize nested binary branching

Can affect the readability of our code.

Figure 15 –

nested if...else statements

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 31

// example 6 - nested if else structure – three possibilities

if (temp > 99.0)

System.out.println("The patient has a fever");

else

if (temp < 97.0)

System.out.println("The patient’s temperature seems too low.")

else

System.out.println("The patient’s temperature is normal");

In example 6, if the first condition is true, a message is printed and we’re done. If the first condition is

false, then a second condition is checked. A nested if…else is inside the else part of the first if…else.

This isn’t too hard to follow, but it is starting to spread across the page.

Some programmers move the nested if following an else up to the same line as the else to condense

things a bit, as in example 7. This may make it seem like else if is an instruction, but it is not; it is simply

a new if statement starting immediately after the else from the previous if…else statement.

// example 7 - nested if else structure – three possibilities

if (temp > 99.0)

System.out.println("The patient has a fever");

else if (temp < 97.0)

System.out.println("The patient’s temperature seems too low.");

else

System.out.println("The patient’s temperature is normal");

The examples in Figures 18 and 19 on the following page shows a series of if…else statements for a

situation with eight possibilities. There is one possibility for each day of the week, plus an eighth default

item in case the weekday was somehow wrong – such as spelled wrong or left as a null value. This

example uses a String to hold the day of the week. Example 8 shows the traditional way indenting

if…else statements. Example 9 shows the same code, with the indenting changed.

Keep in mind there is no else…if statement in Java. Each else in Example 8 and Example 9 is matched

with the previous if in a sequence of nested if...else statements whose alignment makes it look like there

is an else…if statement.

Figure 16 –

nested if...else code

traditional indenting

Figure 17 –

nested if...else code

modified indenting

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 32

// example 8 - nested if else structure – eight possibilities

System.out.print("The soup of the day is ");

if (day == “Monday”)

System.out.println("McGinley’s Jersey Tomato Soup.");

else if (day == “Tuesday”)

System.out.println("McGorry’s Chesapeake Crab Chowder.");

else if (day == “Wednesday”)

System.out.println("Melamed’s Vegetable Rhythm Roundup");

else if (day == “Thursday”)

System.out.println("Horwitz’s Florida Matzah Ball

Bisque.");

else if (day == “Friday”)

System.out.println("Sylvia’s Seafood Special");

else if (day == “Saturday”)

System.out.println("Daphne’s Potato Leek

Potpourri");

else if (day == “Sunday”)

System.out.println("Craig Nelson’s

Jazz Joint Jumbalaya");

else

System.out.println("day error”);

We can see from example 8 that indenting nested if statements can start to become a little ridiculous

with many choices, so a common style is to modify the indenting as in example 9:

// example 9 - nested if else structure – eight possibilities – modified indent

System.out.print("The soup of the day is ");

if (day == “Monday”)

System.out.println("McGinley’s Jersey Tomato and Basil.");

else if (day == “Tuesday”)

System.out.println("McGorry’s Chesapeake Crab Chowder.");

else if (day == “Wednesday”)

System.out.println("Melamed’s Vegetable Rhythm Roundup");

else if (day == “Thursday”)

System.out.println("Horwitz’s Florida Matzah Ball Bisque.");

else if (day == “Friday”)

System.out.println("Sylvia’s Seafood Special");

else if (day == “Saturday”)

System.out.println("Daphne’s Potato Leek Potpourri");

else if (day == “Sunday”)

System.out.println("Craig Nelson’s Jazz Joint Jumbalaya");

else

System.out.println("day error”);

Figure 18 –

nested if...else code

traditional indenting

Figure 19 –

nested if...else code

modified indenting

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 33

The switch Structure in Java

As an alternative to nested if…else statements, Java provides the switch statement. The switch

statement uses the value of a single variable to determine which branch to take in a selection sequence.

It can have as many different branches as there are values for the variable. The following example

shows this with soup of the day.

// example 10 - switch with eight possibilities

String day; // the code to set the value of day is not shown here

System.out.print("The soup of the day is ");

switch (day)

{

case “Monday” : System.out.println("McGinley’s Jersey Tomato and Basil.");

break;

case “Tuesday” : System.out.println("McGorry’s Chesapeake Crab Chowder.");

break;

case “Wednesday” : System.out.println("Melamed’s Vegetable Rhythm Roundup");

break;

case “Thursday” : System.out.println("Horwitz’s Florida Matzah Ball Bisque.");

break;

case “Friday” : System.out.println("Sylvia’s Seafood Special");

break;

case “Saturday” : System.out.println("Daphne’s Potato Leek Potpourri");

break;

case “Sunday” : System.out.println("Craig Nelson’s Jazz Joint Jumbalaya");

break;

default : System.out.println("day error”);

} //end switch(day)

A switch statement has a single control variable. Each case in the switch statement is equivalent to an if

statement checking the value of the switch control variable. The data type for each case value must

match the data type of the switch control variable. The switch statement works with byte, short, and int

integer variables; with char and String text variables; and with enumerated data types, which are

described in the next section. It does not work with floating point numbers nor with long integers.

Notice that the cases in a switch statement are enclosed by braces {...} forming a switch block. The

default statement is the last item in a switch block. It tells the computer what to do if the switch control

variable does not equal any of the values in the case statements.

A break statement terminates a block of code and tells the computer to move on to whatever follows

the block. A break statement may be used in any block of code, but is most often used in switch blocks.

Break statements are usually necessary in a switch block. Without the break statements in the example

above, the computer would print the soup of the day and all of the soups for the following days. We use

the break statement to tell the computer to print the name of only one soup, then leave the block.

Figure 20 –

multiple branching

with a switch block

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 34

Choosing between Nested if…else and switch

When should we use a nested if…else structure and when should we use a switch structure when our

algorithm calls for multiple branching? If we have a short well-defined set of values for a single control

variable, then we can use the switch statement.

There are four situations in which it is better to use nested if…else than to use switch:

1. if the control variable does not have a data type that switch accepts, such as float.

If the control variable is not one of the data types a switch structure can use, than we either cast

the data type or use a nested if…else structure. The nested if…else structure is preferable to

unnecessary type casting. This is what happens if the control variable is a floating point data

type or a long integer.

2. if we need to make a selection based on an inequality relational operation.

The switch statement only works if the control variable equals a set value, not with inequality

relational operations, such as in the case of (hours > 40). We could manipulate things to

make this work, but why introduce unnecessary processing, which adds to the software’s run

time and complicates the code?

3. if we need to make a selection based on a range of values. The switch statement only works if

the control variable equals a set value, not with a range of values. In example 7 in Figure 17 on

page 31 we are not checking to see if a person’s temperature is equal to 99 or equal to 97, but

checking to see if it is in one of three ranges:

 less than 97

 greater than or equal to 97 but less than or equal to 99

 greater than 99

This situation is better suited to an if…else structure than a switch structure, because of the

unnecessary complications we would need to make it work with a switch structure.

4. If there is more than one control variable. A Nested if…else structure is also a better to handle

situations with more than one control variable than a switch structure, although we could

include if statements within the code for a switch structure.

To illustrate a situation with more than one control variable, consider an airlock on a submarine. The

airlock has two airtight and watertight doors, an inner door and an outer door. We have a boolean

variable for each door, true if the is door closed and false if it is open. There are four possible conditions:

 If both doors are closed, the airlock is sealed.

 If the inner door is closed and the outer door is open, then the airlock is open to the outside.

 If the inner door is open and the outer door is closed, then the airlock is open to the inside.

 If both doors are open, then an emergency alarm should sound.

We can implement this as a nested if…else structure in which each if statement tests one of the four

possible conditions. Two different ways to do this are shown in the examples in the next page.

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 35

// Example 11 -- airlock doors – nested…if – two boolean variables

boolean innerDoorClosed; // true if closed and sealed, otherwise false

boolean outerDoorClosed; // true if closed and sealed, otherwise false

// the code to set the values is not shown

if (innerDoorClosed && outerDoorClosed) // both doors are closed

System.out.println("Airlock sealed");

else if (innerDoorClosed) && !(outerDoorClosed) ) // inner door closed, outer door open

System.out.println("Open to othside");

else if ( !(innerDoorClosed) && (outerDoorClosed)) // inner door open, outer door closed

System.out.println("Open to inside");

else // inner door open, outer door open

System.out.println("Danger – Airlock doors not sealed");

// Example 12 -- airlock doors – nested…if with two boolean variables

boolean innerDoorClosed; // true if closed and sealed, otherwise false

boolean outerDoorClosed; // true if closed and sealed, otherwise false

// the code to set the values is not shown

if (innerDoorClosed)

if (outerDoorClosed) // both doors are closed

System.out.println("Airlock sealed");

else // inner door closed, outer door open

System.out.println("Open to outside");

else

if (outerDoorClosed)) // inner door open, outer door closed

System.out.println("Open to inside");

else // inner door open, outer door open

System.out.println("Danger – Airlock doors not sealed");

When you have learned more about programming, you will be able to implement what is known as an

associative array, or a table lookup. Both of these methods are preferable to a long sequence of nested

if…else statements. We could also use hashing or other advanced techniques not covered in this course.

For conditions that are not too complicated, nested if…else statements and switch structures work very

well. CSCI 112 and 211 cover more advanced techniques.

CheckPoint 3.3

1. What is the difference between a binary bypass and a binary choice in an algorithm?

2. Show how to establish a binary bypass in Java.

3. Show how to establish a binary choice in Java.

4. Show how to use nested if…else statements to establish multiple branching in Java.

5. Show how to use the switch statement for multiple branching in Java.

Figure 21 –

branching with

two boolean variables

Figure 22 –

alternative branching with

two boolean variables

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 36

Enumerated Data Types in Java

Java has a special mechanism to set up enumerated data types. An enumerated data type is a data type

with a set of defined values established as an object in Java code. Variables of that type can only have a

value equal to one of the defined values. The enum keyword is used to declare a new enumerated data

type as an Object in Java. Here is an example of how this works for days of the week, using three letter

abbreviations for the day.

// example 12 new enumerated data type - Day

public enum Day

{

SUN, MON, TUE, WED, THU, FRI, SAT

} // end enum Day

Then we can use the new data type in our software:

Day today; //declares today as a Day variable just as int x declares x as an int variable today = Day.MON; // today is set to the constant value MONDAY from the class Day

This can be a little tricky to use, so read the next few paragraphs carefully.

The keyword enum sets up a special kind of class called an enumerated class, which is why the name of

the data type is capitalized and preceded by public in the declaration. You can see in the example above

that Day is capitalized. These are not primitive variables like int or float. Day is the name of a class,

which is the data type.

The possible values for an enumerated data type are all caps because they are static constants in the

class. (In Chapter 2 we saw that that the names of constants in Java are usually capitalized.) Static

means that they are associated with the class itself, not an instance of the class. When we use

enumerated constants in an assignment statement we should include the name of the class in a

qualified name, as in Day.MON in the assignment statement today = Day.MON;

The declaration of any class, including an enumerated data type, cannot be local, which means it cannot

be inside a method or block of code. It can be inside another class, creating an inner class. An inner

class is a class defined inside another class. It can be used anywhere in the outer class in which it is

defined. Inner classes are often used to define enumerated data types if the enumerated data type will

only be used within methods in the outer class.

Once an enum declaration appears as an inner class, a variable of that type may be declared and used

anywhere in the outer class that contains the inner class. It can have any one of the constant values

specified in the declaration.

Enumerated data types works very well with switch statements. In the example in Figure 24 on the next

page, the outer class is our project class, SoupSwitch. The enumerated data type Day is declared inside

the SoupSwitch class as an inner class. This allows us to use the static constants from the enumerated

class -- the values MON, TUE, etc. , in our main method.

Figure 23 –

declaring an

enumerated data type

with a switch block

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 37

Keep in mind that the data type is not enum, it is whatever we name the new enumerated data type. In

this example, Day is the data type and today is a variable of type Day.

Here is the soup-of-the-day example with an enumerated data type for days of the week. The zipped

NetBeans project file SoupSwitch.zip in the files for week 3 in Canvas contains this code as a NetBeans

project. Some comments in the original code have been removed so that the listing fits on the page.

package soupSwitch;

public class SoupSwitch {

public enum Day // enum inner class declaration

{ SUN, MON, TUE, WED, THU, FRI, SAT } // fits well on one line

public static void main(String[] args) { // main method demonstrates switch

Day today; // declare today as a variable of type Day

today = Day.MON; // for this example, today can be set to any Day

System.out.print("The soup of the day is ");

switch (today) {

case MON: System.out.println("Charlie McGinley’s Jersey Tomato and Basil.");

break;

case TUE: System.out.println("Marian McGorry’s Chesapeake Crab Chowder.");

break;

case WED: System.out.println("Dan Melamed’s Vegetable Rhythm Roundup");

break;

case THU: System.out.println("Steve Horwitz’s Florida Matzah Ball Bisque.");

break;

case FRI: System.out.println("Sylvia Gaines-Henderson’s Seafood Special");

break;

case SAT: System.out.println("Daphne Herbert’s Potato Leek Potpourri");

break;

case SUN: System.out.println("Craig Nelson’s Jazz Joint Jumbalaya");

break;

default : System.out.println("day error");

} //end switch(day)

} // end main()

} // end class SoupSwitch

We can make up almost any enumerated data type, but typically enum is used for well-known,

predefined sets of data, such as the days of the week, the months of the year, the names of the Three

Stooges, and so on. An enumerated data type can be used instead of a String variable for well-defined

sets, such as the set of two letter abbreviations for US states.

Here is an enumerated data type for the Three Stooges (all six of them):

Figure 24 –

SoupSwitch code

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 38

public enum Stooge { LARRY, MOE, CURLY, SHEMP, JOE, CURLY_JOE }

Note that the declaration is on a single line because the list is short.

Unlike Strings, an enumerated data type prevents the value of the variable from being something other

than what has been declared, such as a Stooge named CURTIS. Enum works very well in a menu

program where there are a set number of choices a person can pick from, or in event-driven

programming where a user presses a button on the screen. We will see examples of this later in the

semester.

Note that In the switch structure above, the default option isn’t really needed, because there is a case

for every possible values of today. However it is good practice to include it anyway, in case the software

is modified and all of the possible cases are not covered.

CheckPoint 3.4

1. What is an enumerated data type in Java?

2. How are enumerated data types implemented in Java?

3. What is an inner class and why is it often used to define an enumerated data type?

4. What are the values of enumerated data types in all caps?

5. Describe how an enumerated data type can be used with a switch statement in Java.

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 39

Lab Reports and Collaborative Editing

Lab reports are an important part of computer programming courses. They are similar to project

documentation and help you to prepare for writing project documentation, which is an important part

of professional programming.

Computer Science 111 Lab Report

A template for programming lab reports for Computer Science 111 is included in the files for Week 3 in

Canvas. Unless directed to do something different by the assignment, a programming lab report

should include the following five sections:

a. Heading

Include your name, course and section number, semester, and identification of the assignment.

b. Assignment Analysis and Design

In your own words, describe the problem including input and output. Briefly describe how you

developed your code. Briefly describe what your code does and how it works – including anything

different or unique or special that you did in your software. If the software is long or complicated,

describe how it is organized. Include a copy of any pseudocode or other design documents you used.

If you worked with anyone else, asked anyone for help, or looked anything up, then mention it here.

Include proper references to source material.

c. Assignment Code

Include the code for your assignment as directed by the assignment or by your instructor. In most

cases, this will be a zipped copy of the folder for your NetBeans project attached to the report. You

can put the report and the NetBeans project all in one zipped folder. In the report, either tell the

reader that the code is in an attached file or include the code.

A zipped folder may contain another zipped folder. You can copy the zipped folder for your

NetBeans project and your lab report into a folder for your assignment, then zip the assignment

folder. Alternatively, you could copy the report into your NetBeans project’s folder before zipping it.

Your instructor may have specific requirements for this.

d. Assignment Testing

Describe how you tested this program to verify that it runs correctly.

e. Assignment Evaluation

Briefly describe what you learned from this project. What things did you struggle with? What was

easy? Give your opinions of the process, including what you liked about the project and any

suggestions you have for improving the project.

The report does not need to be long, but it should be complete.

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 40

Collaborative Editing of Word Documents

From time to time it will be necessary to work on programming projects with other people. This

happens more often than not in a professional environment. You should know how to use Document

Markup and Review features in Word to markup and comment on what other people have written, and

to edit your own documents that have been marked by others.

The notes below are for Office 2010. There are similar features in other versions of Word.

There are two things you can do to mark and edit an existing document:

1. make changes to the document with Track Changes turned on;

2. add document comments to the document.

The Track Changes feature and the comment feature are both found on the Review Ribbon in Word

2010, as shown below:

These features are easy to use, as described below. Several short tutorials for tracking changes and

commenting in Word 2010 are available on the Web. See the following:

 from Microsoft: http://office.microsoft.com/en-us/support/results.aspx?ctags=CH010372680

 from Office consultant Shauna Kelly,: http://shaunakelly.com/word/sharing/howtrackchangesworks.html

 a YouTube video from a graduate student: http://www.youtube.com/watch?v=AUf-IxzXyVk

Tracking Changes

To use track changes, click the Track Changes button to turn the feature on. The button works like a

toggle switch – each time you click the button it changes the track changes setting to either on if it is off,

or off if it is on. When it is on, any changes you make in the document will show up as editor’s marks in

the document.

The settings to the right of the Track Changes button allows you to see the final document with the

markup, to see what the original document looked like without the markup, or to see what the final

New Comment

Button

Track Changes

switch

Track Changes

navigation Comment

navigation

Figure 25 –

Track Changes

in Word 2013

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 41

document looks like without the markup. You should experiment with Track Changes in Word to get a

feeling for how it works. Open an old document and experiment with the settings while making changes

to the document.

If someone sends you a document with changes that were made while Track Changes was on, you can

change the Track Changes settings to see the document showing the markup, to see it as it originally

was, or to see what the final document looks like without the markup.

Starting from the beginning of your document, you can use the Track Changes navigation buttons to

move through the document from one change to another, accepting or rejecting the changes.

Document Comments

To place comments in a document without changing the document, select the location where you want

to comment or click the item you wish to comment on, then click the New Comment button on the

Review pane.

If someone sends you a document with comments, you can move from one comment to another or

delete comments using the comment navigation buttons to the right of the New Comment button.

Just as with track changes, it is best to open an existing document and experiment with document

comments.

Lab 3A – Body Mass Index

Here is a program that will make you popular with your friends and family. According to the Centers for

Disease Control, 8 “Body Mass Index (BMI) is a number calculated from a person's weight and height.

BMI is an inexpensive and easy-to-perform method of screening for weight categories that may lead to

health problems.” The formula for BMI using weight in pounds and height in inches and a table showing

the standard weight status categories associated with BMI ranges for adults are given here:

BMI = 𝑾

𝑯𝟐 ∗ 703

𝑾 is weight in pounds

𝑯 is height in inches

BMI Weight Status

BMI < 18.5 underweight

18.5 ≤ BMI < 25 normal

25 ≤ BMI < 30 overweight

BMI ≥ 30 obese

We wish to design a program that will ask the user for height and weight and then calculate and display

the person’s BMI.

STEP 1.

We will start by writing the BMI formula as a valid Java assignment statement:

bmi = wt / (ht * ht) * 703

8 The CDC Body Mass Index Web page can be found at: http://www.cdc.gov/healthyweight/assessing/bmi

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 42

STEP 2.

Next, we need to write the categories in the table as boolean expressions in Java. The first and last

conditions are okay as they appear in the table, but the two middle conditions need to be rewritten.

They are ranges of values. All four would look like this as Java boolean conditions:

underweight ( bmi < 18.5 )

normal ( (18.5 <= bmi) AND (bmi < 25.0) )

overweight ( (25.0 <= bmi) AND (bmi < 30) )

obese ( bmi >= 30 )

STEP 3.

Now we can write a series of if statements to display the BMI category. We will use a string variable

named category, and set category = to the BMI category using the boolean conditions we just wrote:

if ( bmi < 18.5 )

category = “underweight”;

if ( ( 18.5 <= bmi ) AND ( bmi < 25.0 ) )

category = “normal”;

if ( ( 25.0 <= bmi ) AND ( bmi < 30.0) )

category = “overweight”;

if ( 30.0 >= bmi )

category = “obese”;

We could also write this as a series of nested if…else statements as follows, which would be more

efficient:

if ( bmi < 18.5 )

category = “underweight”;

else if ( bmi < 25.0 )

category = “normal”;

else if ( ( bmi < 30.0 ) )

category = “overweight”;

else

category = “obese”;

The nested if…else statements are more efficient because as soon as one condition is true, the

computer ignores the rest of the conditions and moves on to whatever comes next in the program.

With the series of simple if statement above, the computer checks every if statement, even though only

one of them can be true at a time.

STEP 4.

If we look at what we have so far, we can see that there are four variables:

height, weight, and bmi are numeric values that could have decimal points; category, is a String. (Note

that category could also be an enumerated data type, but we will keep it simple with a String variable.)

Figure 26 –

BMI if…statements

Figure 27 –

nested BMI if statements

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 43

double height; // person’s height in inches

double weight; // person’s weight in pounds

double bmi; // person’s calculated body mass index

String category; // the BMI category

STEP 5.

Now we are ready to design our algorithm and describe it using pseudocode.

// Body Mass Index calculator

double height; // person’s height in inches

double weight; // person’s weight in pounds

double bmi; // person’s calculated body mass index

String category; // the BMI category

set up scanner for input from the keyboard

print opening message

get person’s height

get person’s weight

bmi = wt / (ht * ht) * 703 // calculate BMI using CDC formula

// determine BMI category

if ( bmi < 18.5 )

category = “underweight”;

else if ( bmi < 25.0 )

category = “normal”;

else if (( bmi < 30.0 )

category = “overweight”;

else

category = “obese”;

print result -- “your BMI category based on your height and weight is” + [category].

END

STEP 6.

It is left for you to complete the exercise by converting this to Java code and getting the program to run

as a NetBeans project name bmiCalculator.

Figure 28 –

BMI Algorithm

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 44

Lab 3B – Airlock

Two NetBeans project folders, airlock.zip and soupSwitch.zip are in the files for Chapter 3 in Canvas.

Your task is to run each as a NetBeans project and experiment with the multiple branching statements

to see how they work.

The instructions for doing this with the airlock project are included below. It has nested if..else

statements. When you finish with airlock, you should be able to do the same with the soupSwitch

project, which has the soup-of-the-day code from the example in this chapter. It includes the code for

the enumerated data type Day implemented as an inner class.

STEP 1.

Locate the NetBeansProjects folder on the computer system you are using. If you installed NetBeans

following the directions in Appendix A, and did not change the default settings, it should be within the

My Documents folder on a Windows-based PC. Our goal here is to first make sure we know where the

folder is located on the system we are using.

STEP 2.

Log into Canvas. Go to the module for Week 3 and find the file airlock.zip.

STEP 3.

Click on the name of the file to access it. A new window will open in Canvas as seen here. Near the top

of the window there will be a link to download the file.

Figure 29

Figure 30

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 45

STEP 4.

A dialog window should appear asking you if you want to open the file or save it. On many systems the

window will appear near the bottom of the screen, as shown here. The exact configuration depends on

your operating system and browser.

You should click the arrow next to save and select Save as from the menu that appears so you can

control where the file will be saved.

STEP 5.

Save the file in the NetBeans Projects folder that you located in step 1. Be sure to save it within the

actual NetBeansProjects folder and not in the folder that contains the NetBeansProjects folder.

Once the file is saved in the right location you can exit Canvas.

STEP 6.

Link to download the file Figure 31 –

download link

in Canvas

Figure 32 –

download link

in Chrome

Figure 33 –

NetBeans IDE

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 46

Run the NetBeans IDE software. When NetBeans is open, first close any projects that are open. You

should now have a blank NetBeans IDE.

STEP 7.

Select the File menu in the IDE, then Open Project. Open the airlock project from the list of files that

appears. It may take a few moments for your project files to load. The IDE windows should fill with

information from the project, including the source code in the source code editor window

STEP 8.

Look through the source code to become more familiar with what it does. You can run the program to

see the result. Lines 24 and 25 set the variables innerDoorClosed and outerDoorClosed both to true. In a

program like this from an actual airlock, the data would be read in from hardware sensors. You can

change the values and run the code again to see what happens. There are four possible combinations of

the two variables. The code checks for all four.

STEP 9.

When you are finished experimenting with the code, you can close the project. You should now be

able to download and open the SoupSwitch project in the same way that you did with airlock. The

SoupSwitch.zip file is in the Canvas Week 3 module.

SoupSwitch demonstrates a switch structure which uses the control variable today, a variable of the

enumerated data type Day, which is defined in the project as an inner class. The value of the variable is

set to Day.MON. Try changing it to different values to see how it works. Together the airlock and

SoupSwitch projects show the two different approaches to multi-branching discussed in this chapter.

Figure 34 –

Project in

NetBeans IDE

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 47

Lab 3C – Quadratic Equations

A second degree polynomial, such as 𝑥2 + 2𝑥 − 8 = 0 has the standard form 𝑎𝑥2 + 𝑏𝑥 + 𝑐 = 0.

a, b and c are the coefficients of the equation. The values for x, called the roots of the equation, can be

found using the quadratic formula x = −𝑏±√𝑏2−4𝑎𝑐

2𝑎 .

The term (𝑏2 − 4𝑎𝑐) in the quadratic formula is called the discriminant. It could be negative, zero, or

positive. This will tell us how many roots a quadratic has:

 If (𝑏2 − 4𝑎𝑐) is negative, the equation has no real roots, since a negative number has no square

root.

 If (𝑏2 − 4𝑎𝑐) is zero, then its square root is zero, and since (–b + 0) = (–b – 0), the equation has

one real root: –𝑏

2𝑎 .

 If (𝑏2 − 4𝑎𝑐) is positive, the equation has two real roots: x1 = −𝑏−√𝑏2−4𝑎𝑐

2𝑎 and

x2 = −𝑏+√𝑏2−4𝑎𝑐

2𝑎 . A positive number has two square roots. For example, both 4 and -4 are √16.

Quadratic equations could represent ballistics, such as a thrown baseball. If we ask the question “When

will the baseball be exactly 50 ft. above the ground?”, the answer could be twice if it is thrown high

enough and hard enough, once on the way up and once on the way down; once if it just reaches 50 ft. at

its peak; or never if it isn’t thrown hard enough to reach 50 ft. The roots of a quadratic equation

representing ballistics could answer the question. We could have two roots, one root, or no roots.

We wish to design a program to solve quadratic equations. in standard form. The software should:

 ask for the three coefficients, then calculate the discriminant.

 If the discriminant is negative, the software should tell the user there are no real roots.

 If the discriminant is zero, it should tell the user there is one real root and calculate and display

the root.

 If the discriminant is positive, it should tell the user there are two real roots and calculate and

display the roots. We start by defining the algorithm with pseudocode and a flowchart:

Figure 35 –

Quadratic Roots

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 48

Finding the Roots of a Quadratic Equation

start

double a; // coefficient of x2

double b; // coefficient of x

double c; // constant term

double disc; // the discriminant

double root1; // the first root or only root if there is a single root

double root2; // the second root

setup console input and

get values of the coefficients a, b, and c from the user

calculate the discriminant disc = 𝑏2 − 4𝑎𝑐

if (disc < 0)

no real roots

else if (disc = 0)

{

one real root

root1 = –𝑏

2𝑎

display root1

)

else

{

two real roots

root1 = −𝑏−√𝑏2−4𝑎𝑐

2𝑎

root2 = −𝑏+√𝑏2−4𝑎𝑐

2𝑎

display both roots

}

stop

Once we have pseudocode that seems to be correct, we can start to turn the pseudocode into

comments and begin building our program, as shown on the next page.

Figure 36 –

Quadratic Roots Algorithm

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 49

double a; // coefficient of x2

double b; // coefficient of x

double c; // constant term

double disc; // the discriminant

double root1; // the first or only root if there is a single root

double root2; // the second root

// set up input stream from the keyboard (see chapter 2)

// get coefficient a from the user

// get coefficient b from the user

// get coefficient c from the user

// calculate the discriminant

disc = b*b – (4 * a * c);

if (disc < 0)

// print no real roots

else if (disc == 0) {

// print one real root

root1 = ( -b ) / ( 2*a );

// display root1

}

else {

// print two real roots

root1 = ( -b - Math.sqrt(disc) ) / ( 2*a );

root2 = ( -b + Math.sqrt(disc) ) / ( 2*a );

// display both roots.

}

The code shown here is in the text file quadratic.txt in the Week 3 module in Canvas. Your task is to

open the file with a text editor such as NotePad, start a NetBeans project named quadratic, copy the

code into the main method in the project, then turn it into a working program.

There are things that will need to be refined, such as including the necessary import statement for

console input, and turning the math expression for the discriminant into proper code.

Figure 37 – developing comments and code

for a quadratic roots algorithm

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 50

Here is some data to test your software.

A B C result

1 1 12 no real roots

1 - 6 9 one root 3

1 2 -8 two roots -4, 2

A solution is in the NetBeans project file quadraticSolution.zip in Canvas. You should compare your

solution to the one provided to see how they differ.

Key Terms in Chapter 3

After completing this chapter, You should be able to define each of the following key terms:

AND, 8

Automata theory, 16

binary branching, 25

binary bypass, 25

binary choice, 25

Boolean algebra, 5

Boolean expression, 6

boolean literal, 6

Boolean logic, 5

break, 33

Church-Turing Thesis, 14

collating sequence, 7

conditional execution, 16

conjunction, 8

De Morgan’s laws, 9

derived Boolean operations, 9

disjunction, 8

enum, 36

enumerated data type, 36

flowchart, 20

implementation domain, 22

inner class, 36

invert (Boolean), 9

linear sequence, 24

multiple branching, 25

negation, 8

NOT, 9

OR, 9

problem domain, 22

relation operation, 6

repetition, 16

state diagram, 16

switch, 33

Turing machine, 15

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 51

Chapter 3 – Questions

1. What values can be used in Boolean logic? How is Boolean logic different from Boolean algebra? How

do computers derive Boolean values? How else can a boolean variable obtain a true or false value?

2. What are the six Boolean relational operations? What operators are used for these operations in Java?

What is the seventh boolean operator in Java? How is an equality operator different from a relational

operator?

3. What does Java use as a collating sequence for text data? What are some other programming languages

that use the same collating sequence? Which of these operating systems use the same collating

sequence: Microsoft Windows, Apple OS X, most versions of Unix, and most newer Android operating

systems? What is the order of the following characters using Java’s collating sequence: a, B, A, and b?

4. What are the names of the three primary logical operations in Boolean logic, and what words are used

to represent each of them? Which of these is a unary operation and what does that mean? Which

operation yields a true value, given a true value and a false value? Which operation yields a false value,

given a true value and a false value?

5. Which of the Boolean logical operations are commutative and what does that mean? Which are

associative and what does that mean? Which are distributive? What are the two versions of

De Morgan’s laws? What statement using the OR operation would be equivalent to saying NOT (A and

B)?

6. What are three common derived Boolean operations? What operators exist in Java for derived Boolean

operations? How are primary and derived Booelan operations important in the design and manufacture

of computer chips?

7. What operators are used in Java for the three primary Boolean operations? In the absence of

parentheses, which of these operations takes precedence over another?

8. Who was Alan Turing? What is a Turing machine? How is his Halting Problem related to Hilbert’s

Entscheidungsproblem?

9. What is Lambda Calculus? Who developed Lambda Calculus? What does the Church-Turing Thesis tell us

about the relationship between what can be calculated with a Turing machine and what can be

calculated with Lambda Calculus?

10. What is the focus of automata theory? What two things does a state diagram show us about a system?

11. Why are the elements of logical structure important in designing and creating algorithms? What are the

three elements of logical structure described by Bohm and Jacopini? What tool is most commonly used

today to describe and discuss algorithms?

12. What is the difference between a problem domain and an implementation domain? Language from

which of these domains is used in Pseudocode? How is pseudocode related to these two domains?

13. What are the four symbols used in flowcharts in this chapter that are the same as in UML activity

diagrams? What does each of them represent?

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 52

14. What criteria do programmers need to make sure linear sequences meet? How can we identify linear

sequences in pseudocode and computer software?

15. What is the difference between a binary bypass and a binary choice? What statements are used in Java

for each of these?

16. How can multiple branching be implemented in Java using if…else statements? Is there an else…if

statement in Java? If not, then why does it look as if there is an else…if statement in the code in Figures

18 and 19 on page 32?

17. What does the switch structure do in Java? How many branches can it have? How many variables does

it use? Which data types can be used in a switch statement?

18. What does a break statement do? Why is a break statement necessary in a switch block?

19. What does the default statement do in a switch block?

20. What are four situations in which it is better to use a nested if…else structure than a control block? In

what courses are more advanced techniques learned that are preferable to a long sequence of nested

if...else statements?

21. What values can a variable of an enumerated data type have? Why is the name of the data type

capitalized when an enumerated data type is established in Java? Why are the values for an enumerated

class in all caps? How must we use the values from an enumerated class in an assignment statement?

22. What is an inner class and where is an inner class declared? Where can we use a variable from an

enumerated data type that has been declared as an inner class?

23. What is an enumerated data type typically used for? What advantage does an enumerated data type

have over using String values?

24. What type of software documentation are lab reports related to? What are the five sections that should

be included in a lab report for Computer Science 111? How can we package our lab report and

NetBeans project for submission to an instructor?

25. What features of MS Word can we use to mark and edit existing documents? Where can we find these

features in Word? How can we accept or reject changes made in a document when Track Changes has

been turned on? How can we see and remove document comments from a Word document?

Chapter 3 – Exercises

1. Write each of the following as valid Java boolean expressions: (Pay attention to data types.)

A. length of a fish greater than or equal to 22 inches

B. joint income greater than $17,400 and less than or equal to $70,700

C. name less than “Smith”

D. water level greater than 5 feet and less than 14 feet

E. number of students less than 36

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 53

2. Write each of each of the three derived logical operations described on page 6 – NAND, NOR, and XOR –

as Java boolean expressions.

3. We have three variables: age, weight and height. An airbag warning sign on the sun visor in the front of

a car says “Passenger must be at least 12 years old, with a weight of at least 75 pounds or a height of at

least 57 inches” to sit in the front seat. Write this rule as a boolean expression.

4. In most states in the US, a vehicle must stop at an intersection with a traffic light when the traffic light is

red, except when making a right turn, in which case the driver must pause and can then make a right

turn on red if the way is clear, unless otherwise posted. At a particular intersection there is a sign that

says, “No right turn on red, 6 am to 6 pm, except Saturdays and Sundays.” Write the set of rules and

conditions for this intersection as an if…else statement with a single boolean expression of the form:

if (boolean condition)

right turn on red

else

no right turn on red

5. Which of the following does not contain a valid Boolean expression, and why?

a. If (romeDistance < veniceDistance OR naplesDistance)

b. If (count > 10 AND count < 20)

c. While (count < 5 AND > 1)

d. While (height < count OR height < 12.5)

e. If (message = “Hello, World.” OR “Hello, World!”)

6. We can test for divisibility by performing a remaindering operation (the % operator in Java) on a

numeric value. If A % B is 0, then A is divisible by B. For example, (15 % 3) = 0, so 15 is divisible by 3. The

rule for determining if a year is a leap year can be found at the U.S. Naval Observatory’s Website online

at http://aa.usno.navy.mil/faq/docs/leap_years.php

Create a Java application in NetBeans that asks the user for the year, determines if the year is a leap

year, then gives the user the result.

7. CCP Airways has a frequent flyer program that rewards people with frequent flyer miles in different

categories, as follows:

 up to 10,000 miles CCP Flyer

 10,000 to 24,999 miles CCP Silver Flyer

 25,000 to 50,000 miles CCP Gold Flyer

 more than 50,000 miles CCP Platinum Flyer

Create a Java application in NetBeans that asks for the user’s number of CCP Airways frequent flyer

miles, them determines and displays the user’s frequent flyer status.

JLK Chapter 3 – Programming Logic DRAFT January 2015 Edition pg. 54

8. A company determines an employee’s pay based on hours times rate, with “time and a half for

overtime”. Overtime is more than 40 hours in one week. If an employee works more than 40 hours, the

gross pay is equal to the regular pay for 40 hours, plus 1.5 times the rate for overtime hours.

Create a Java payroll application in NetBeans that prompts the user to enter the employee’s name,

hours, and rate; calculate gross pay, then print a report with the employee’s data – name, hours, rate

and gross pay.

9. A university recognizes graduates with high GPA’s in different honors categories using the following

cutoffs:

 summa cum laude 3.8 or higher

 magna cum laude 3.6 or higher, up to summa cum laude

 cum laude 3.2 or higher, up to magna cum laude

A 2.0 GPA is needed to graduate. Students with less than a 2.0 are not eligible for graduation.

Create a Java application in NetBeans that asks the user to enter a student’s GPA then determines and

displays the student’s graduation status.

10. The Java Math class has a function to determine the hypotenuse of a right triangle, given the two other

sides of the triangle: Math.hypot(double a, double b) returns as a double the square root of ( a2+ b2).

(See the table of math Functions on page 21 in Chapter 2.) Remember, a2+ b2 = c2, where a and b are the

lengths of the shorter sides in a right triangle and c is the hypotenuse. So, c = √𝑎2 + 𝑏2.

The distance from any point (x,y) in a Cartesian Coordinate system to the origin (0,0) is the hypotenuse

of a right triangle with the two short sides of the triangle equal to the x and y coordinates. In the

example below, the distance from the point (3,4) to origin is √32 + 42, which equals 5.

The example on the right also shows us that the quadrants of a Cartesian plane are numbered I through IV, with the following properties:

 If both x and y are non-negative, the point is in Quadrant I.

 If x is negative and y is non-negative, the point is in Quadrant II

 If x and y are both negative, the point is in Quadrant III.

 If x is non-negative and y is negative, the point is in Quadrant IV.

Y axis

X axis

(3,4)

4

3(0,0)

Quadrant IQuadrant II

Quadrant III Quadrant IV

Your task is to create a Java application in NetBeans that asks the user for the x and y coordinates of a

point, then returns the distance to the origin and which quadrant the point is in.

— End of Chapter 3 —