Programming Logic

An Introduction to Computer Science with Java, Python and C++ Community College of Philadelphia edition Copyright 2018 by C.W. Herbert, all rights reserved.

Last edited September 24, 2018 by C. W. Herbert

This document is a draft of a chapter from An Introduction to Computer Science with Java, Python and C++, written by Charles

Herbert. It is available free of charge for students in Computer Science courses at Community College of Philadelphia during the

Fall 2018 semester. It may not be reproduced or distributed for any other purposes without proper prior permission.

Please report any typos, other errors, or suggestions for improving the text to [email protected]

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

Boolean Logic in Branching and Looping .......................................................................... 4

Boolean Relational Operations ............................................................................................................. 5

Boolean Relational Operators in Python .............................................................................................. 5

Boolean Logical Operations .................................................................................................................. 7

Boolean Logical Operators in Python .................................................................................................. 10

Boolean Expressions Using Boolean Variables .................................................................................... 10

CheckPoint 3.1 ..................................................................................................................................... 11

The Nature of Algorithms................................................................................................ 12

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

Elements of Logical Structure in Algorithms ....................................................................................... 16

Tools for Describing Algorithms .......................................................................................................... 19

Linear Sequences ................................................................................................................................ 23

CheckPoint 3.2 ..................................................................................................................................... 24

Conditional Execution (Branching ) ................................................................................. 24

Binary Branching – Bypass vs. Choice ................................................................................................. 24

Binary Branching in Python ................................................................................................................. 25

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

Pythons elif statement ........................................................................................................................ 30

CheckPoint 3.3 ..................................................................................................................................... 31

Chapter 3 – Programming Logic DRAFT September 2018 pg. 2

Lab Reports and Collaborative Editing ............................................................................ 32

Computer Science 111 Lab Report ...................................................................................................... 32

Collaborative Editing of Word Documents ......................................................................................... 33

Tracking Changes ................................................................................................................................ 33

Document Comments ......................................................................................................................... 34

Lab 3A – Body Mass Index ...................................................................................................................... 34

Lab 3B – Quadratic Equations ................................................................................................................ 36

Key Terms in Chapter 3 ........................................................................................................................... 39

Chapter 3 – Questions ............................................................................................................................ 39

Chapter 3 – Exercises .............................................................................................................................. 40

Chapter 3 – Programming Logic DRAFT September 2018 pg. 3

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 Python. 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 Python 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 Python;

• describe the use of the if…else statement for establishing multiple branching in Python, and how

to establish nested if…else structures in Python;

• describe the proper use of the elif statement for establishing multiple branching in Python.

• create Python code that demonstrates correct use of each of the following: conditional

execution, multiple branching with an if…else structure, and multiple branching with an elif

structure;

• 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.

Chapter 3 – Programming Logic DRAFT September 2018 pg. 4

Boolean Logic in Branching and Looping

In chapter one we saw Python’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 language for

specifying them in Python. In the next section, we will look at logical operations like the AND operation

that form compound conditions, then see how Boolean logic forms branching and looping sequences in

the structures of algorithms.

Chapter 3 – Programming Logic DRAFT September 2018 pg. 5

Boolean Relational Operations

In Python programming, a Boolean variable is assigned a true or false value by using the Boolean

constants 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:

licensed = False

citizen = True

The terms True and False are known as Boolean constants or Boolean literals. Boolean literals are

tokens that represent the values true and false in Python 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 Python

There are six common relational operations in Boolean logic. The table below describes each of the six,

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

Boolean Relational Operations

Condition math Python 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

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

sometimes referred to as equality operators.

The symbols for the six logical operators in Python are the same in many programming languages,

including Java and C++.

Simple Boolean conditions for branching in Python each have a single conditional operation in following

the keyword if, as in the following example:

Chapter 3 – Programming Logic DRAFT September 2018 pg. 6

if hours > 40

overtimeHours = hours - 40.0

overTimepay = overtimeHours * rate * 0.5

In this case, the condition is immediately followed by a new block of code indicated by indenting the

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. We will see more about if statements in Python later in this

chapter.

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

what about text data, such as strings in Python?

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 formal name for this is lexicographic order or

lexicographical order A lexicon is a dictionary -- a set of words in a particular order. In mathematics,

lexicographic order means that a set of word is ordered according to the defined order of their

component letters. In other words, alphabetic order, according to some defined alphabet.

The version of the Latin alphabet used for the English language is an example: {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 the words "apple" and "Ball" according to the three sequences above.

• Using the first sequence, B comes before a because uppercase B comes before lowercase a; B is

less than a. In this case, Ball comes before apple.

• With the second sequence, lowercase letters come before uppercase letters, so a comes before

B. Here apple comes before Ball.

Figure 1 –

Block of code in an if statement

Chapter 3 – Programming Logic DRAFT September 2018 pg. 7

• The third sequence, which is more commonly used in everyday language, indicates that both

uppercase and lowercase versions of a letter come before the next letter in the sequence. In this

case, apple comes before Ball.

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 Python,

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 Unicode also includes characters from other languages, such as the Cyrillic, Arabic and Hebrew alphabets. For detailed information on Unicode, see the Unicode Consortium Website, online at: http://www.unicode.org/

Chapter 3 – Programming Logic DRAFT September 2018 pg. 8

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 with a single operand. 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, that 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)

Chapter 3 – Programming Logic DRAFT September 2018 pg. 9

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

Chapter 3 – Programming Logic DRAFT September 2018 pg. 10

Boolean Logical Operators in Python

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

NOT to combine and modify simple conditions. Python simply uses the lowercase versions of the words

and, or and not as the Boolean logical operators:

Operation Python Notes

AND op1 and op2 both operands must be True to yield True

OR op1 or op2 if any operand is True the result is True

NOT not(op1) the Boolean value of the operand is reversed

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:

# more than 40 hours AND status is “hourly” # a score between 90 and 100, including 90 hours > 40 and status == “hourly” score >= 90 and score < 100

# 1,00 words or 5 pages # month not in the range 1 to 12 wordCount >1000 or pageCount > 5 month < 1 or month > 12

# not (x < 3) or not (y < 4) # not ( ( x < 3) and (y < 4) ) not(x < 3) or not(y < 4) not( x < 3 and y < 4 )

Can you see how the bottom two 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 a Boolean variable, not a comparison. 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 not(innerDoorClosed)

The parentheses around innerDoorClosed optional. not applies to whatever immediately follows it.

Parentheses are often used, even when not needed, for clarity.

Figure 2 –

compound

Boolean expressions

Chapter 3 – Programming Logic DRAFT September 2018 pg. 11

CheckPoint 3.1

1. How do computers derive Boolean values?

2. What are the six Boolean comparison operators that can be used in Python? 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 Python 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.

Chapter 3 – Programming Logic DRAFT September 2018 pg. 12

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 this section we will begin to focus on the nature of algorithms. What problems can and

cannot be solved by following an algorithm? 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. An algorithm to design the optimum propeller for an ocean-going vessel using

The Holtrop and Mennen Method to determine a vessel's resistance to water 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?

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

Figure 3 –

applied algorithms

Chapter 3 – Programming Logic DRAFT September 2018 pg. 13

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 themselves proved to be incomplete.)

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

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

Chapter 3 – Programming Logic DRAFT September 2018 pg. 14

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) of he

system. 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.

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

Figure 4 –

model Turing machine

Chapter 3 – Programming Logic DRAFT September 2018 pg. 15

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 not needed in Python, 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

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

Figure 5 –

chess state digram

Chapter 3 – Programming Logic DRAFT September 2018 pg. 16

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,

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

Figure 6 –

chess pseudocode

Chapter 3 – Programming Logic DRAFT September 2018 pg. 17

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 be familiar 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 an Italian computer scientist, Corrado Böhm and his student,

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 Python, 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

Chapter 3 – Programming Logic DRAFT September 2018 pg. 18

(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” and 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” or 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.

Chapter 3 – Programming Logic DRAFT September 2018 pg. 19

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 Python or 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:

Chapter 3 – Programming Logic DRAFT September 2018 pg. 20

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

Chapter 3 – Programming Logic DRAFT September 2018 pg. 21

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 Python, but with less formal syntax.

As we learn about conditional execution and repetition in Python, 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

Chapter 3 – Programming Logic DRAFT September 2018 pg. 22

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

Chapter 3 – Programming Logic DRAFT September 2018 pg. 23

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.

Chapter 3 – Programming Logic DRAFT September 2018 pg. 24

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

Chapter 3 – Programming Logic DRAFT September 2018 pg. 25

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 Python

The if and if … else statements set up binary branching in Python. 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 Python are both lowercase.

The Boolean condition following if could be in parentheses, but they are not required.

In Python, A colon is used after the condition in an if statement and the instruction or block of

instructions to be executed are indented:

if hours > 40:

grossPay = regular pay + (hours-40) * rate * .5

Chapter 3 – Programming Logic DRAFT September 2018 pg. 26

Indentation is used in python to mark a block of code. all of the statement indented in an if statement

will be executed an one block of code if the condition is true. In the example below, the three

statements indented become a block of code to be executed if the condition (hours > 40) is true.

if hours > 40:

regular pay = hours * rate

overtime pay = (hours-40) * rate * 1.5

grosspay = regular pay + overtime pay

A colon and Indentation are also used following else and in an if…else… statement.

Here are some additional examples of Python if statements:

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

if (temp > 98.6):

print("The patient has a fever")

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

if (temp > 98.6):

print("The patient has a fever.")

print("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):

print("The patient has a fever")

else:

print("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):

print("The patient’s temperature is in the normal range.”)

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

if (temp > 98.6):

print("The patient has a fever.")

print("Please have blood work done to check for an infection.")

# end if (temp > 98.6)

else:

print("The patient’s temperature is normal.")

print("Please check blood pressure and pulse.")

# end else (temp > 98.6)

Figure 12 –

examples of

binary branching

Chapter 3 – Programming Logic DRAFT September 2018 pg. 27

Multiple Branching

As we saw earlier, 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:

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 independent binary branching routines or as a set 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.

Figure 13 –

multiple branching

Chapter 3 – Programming Logic DRAFT September 2018 pg. 28

If the flavor does equal vanilla, and there can be only one flavor, 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 set 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.

The flowchart and pseudocode in Figure 14 shows the same ice cream question as above, but as a series

as a set 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 from the flowchart and pseudocode that if any one of the if conditions is true, the remaining

if routines are bypassed. This is a result of the nesting.

Figure 14 –

nested if...else statements

Chapter 3 – Programming Logic DRAFT September 2018 pg. 29

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 is logically the same, but it shows the if… else... nesting more clearly.

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

become messy if there are too many choices. What would this look like if we have 28 flavors of ice

cream to choose from?

Here is code similar to situation above with four choices in above in Python:

Figure 15 –

nested if...else statements

Chapter 3 – Programming Logic DRAFT September 2018 pg. 30

if flavor = "vanilla":

print("vanilla")

else:

if flavor = "chocolate":

print("chocolate ")

else:

if flavor = "pistachio":

print("pistachio")

else:

print("chocolate chip")

Notice that in the above example chocolate chip becomes a default choice. If none of the if conditions

are true, chocolate chip is printed. It is often better to have a default that indicates none of the

available options were chosen, as in the following:

if flavor = "vanilla":

print("vanilla")

else:

if flavor = "chocolate":

print("chocolate ")

else:

if flavor = "pistachio":

print("pistachio")

else:

if flavor = "chocolate chip":

print("chocolate chip")

else:

print("Your choice was not on the menu.")

Pythons elif statement

Python has a an elif statement that can be used to simplify such nested branching. An elif statement

takes the place of an else clause that is immediately followed by another if statement in nested

branching. Like else, elif only needs to be indented to the same level as the corresponding if statement.

Here is the example from above using elif:

if flavor = "vanilla":

print("vanilla")

elif flavor = "chocolate" :

print("chocolate ")

elif flavor = "pistachio":

print("pistachio")

elif flavor = "chocolate chip":

print("chocolate chip")

else:

print("Your choice was not on the menu.")

Chapter 3 – Programming Logic DRAFT September 2018 pg. 31

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 Python.

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

4. Show how to use nested else clauses to establish multiple branching in Python.

5. Show how to use elif for multiple branching in Python.

Chapter 3 – Programming Logic DRAFT September 2018 pg. 32

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 source code file for your program attached to the report. You

can put the report and the program 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. In Java, You could copy the zipped folder for a

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.

Chapter 3 – Programming Logic DRAFT September 2018 pg. 33

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 2013. 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

2013, as shown below:

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

commenting in Word 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

Chapter 3 – Programming Logic DRAFT September 2018 pg. 34

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 Category

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 and BMI category.

STEP 1.

We will start by writing the BMI formula as a valid Python assignment statement:

bmi = wt / (ht * ht) * 703

STEP 2.

8 The CDC Body Mass Index Web page can be found at: http://www.cdc.gov/healthyweight/assessing/bmi

Chapter 3 – Programming Logic DRAFT September 2018 pg. 35

Next, we need to write the categories in the table as Boolean expressions in Python. 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 Python Boolean conditions:

underweight bmi < 18.5

normal 18.5 <= bmi AND bmi < 25.0

overweight 25.0 <= bmi AND bmi < 30.0

obese bmi >= 30.0

STEP 3.

What variables will we need?

height; # person’s height in inches

weight; # person’s weight in pounds

bmi; # person’s calculated body mass index

category; # the BMI category

STEP 4.

Now we are ready to design our algorithm and describe it using pseudocode.

# Body Mass Index calculator

height # person’s height in inches

weight # person’s weight in pounds

bmi # person’s calculated body mass index

category # the BMI category

print opening message

get person’s height

get person’s weight

# calculate BMI using CDC formula

bmi = wt / (ht * ht) * 703

# 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 results – BMI and BMI category message

END

Figure 28 –

BMI Algorithm

STEP 5 It is left for you to complete the exercise by converting this to Python code and

getting the program to run as a program named bmiCalculator.

Chapter 3 – Programming Logic DRAFT September 2018 pg. 36

Lab 3B – 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

Chapter 3 – Programming Logic DRAFT September 2018 pg. 37

Finding the Roots of a Quadratic Equation

start

a # coefficient of x2

b # coefficient of x

c # constant term

disc # the discriminant

root1 # the first root or only root if there is a single root

root2 # the second root

get values of the coefficients a, b, and c from the user

calculate the discriminant disc = 𝑏2 − 4𝑎𝑐

if (disc < 0)

# no real roots

print appropriate message

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

Chapter 3 – Programming Logic DRAFT September 2018 pg. 38

a = 0.0 # coefficient of x2

b = 0.0 # coefficient of x

c = 0.0 # constant term

disc = 0.0 # the discriminant

root1 = 0.0 # the first root or only root if there is a single root

root2 = 0.0 # the second root

# get coefficient a from the user

a = float( input("Enter the value of A: ")

# get coefficient b from the user

b = float( input("Enter the value of B: ")

# get coefficient c from the user

b = float( input("Enter the value of C: ")

# calculate the discriminant

disc = b*b – (4.0 * a * c)

if (disc < 0.0):

# print no real roots

print("No real roots")

elif (disc == 0.0):

# calculate and print one real root

root1 = ( -b ) / ( 2.0*a )

print("One real root:\n\t", root1)

else

# calculate print two real roots

root1 = ( -b - math.sqrt(disc) ) / ( 2.0*a )

root2 = ( -b + math.sqrt(disc) ) / ( 2*a )

print("Two real roots:\n\t", root1, "\n\t", root2)

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

Figure 37 – developing comments and code

for a quadratic roots algorithm

Chapter 3 – Programming Logic DRAFT September 2018 pg. 39

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, 15

binary branching, 24

binary bypass, 25

binary choice, 25

Boolean algebra, 4

Boolean expression, 5

Boolean literals, 5

Boolean logic, 4

Church-Turing Thesis, 13

collating sequence, 6

conditional execution, 15

conjunction, 7

De Morgan’s laws, 8

decidability question, 13

derived Boolean operations, 8

disjunction, 7

elif, 25

else, 25

flow chart, 19

Halting Problem, 13

if, 25

implementation domain, 21

inverting , 8

lexicographic order, 6

linear sequence, 23

multiple branching, 24

NAND, 8

negation, 7

NOR, 8

NOT, 8

OR, 8

problem domain, 21

relation operation, 5

repetition, 15

state diagram, 15

state table, 14

Turing machine, 13

XOR, 8

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

Python? How is an equality operator different from a relational operator?

3. What does Python 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 Python’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?

Chapter 3 – Programming Logic DRAFT September 2018 pg. 40

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? How are primary and derived Booelan operations

important in the design and manufacture of computer chips?

7. What operators are used in Python 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?

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

Python for each of these?

Chapter 3 – Exercises

1. Write each of the following as valid Python 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

2. Write each of each of the three derived logical operations described on page 6 – NAND, NOR, and XOR –

as Python Boolean expressions using only and, or, and not.

Chapter 3 – Programming Logic DRAFT September 2018 pg. 41

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 Python) 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 Python program 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 Python application that asks for the user’s number of CCP Airways frequent flyer miles, then

determines and displays the user’s frequent flyer status.

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.

Chapter 3 – Programming Logic DRAFT September 2018 pg. 42

Create a Python payroll program that prompts the user to enter the employee’s name, hours, and rate;

calculate gross pay; then prints 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 Python program that asks the user to enter a student’s GPA then determines and displays the

student’s graduation status.

10. The Python math library has a function to determine the hypotenuse of a right triangle, given the two

other sides of the triangle: math.hypot(a, b) returns the square root of ( a2+ b2). (See the table of math

Functions 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 Python application 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 —