Programming logic and design chapter 3 answers

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 cherbert@ccp.edu

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

http://www.gutenberg.org/ebooks/36884

https://archive.org/details/formallogicorca00morggoog

http://hdl.handle.net/2027/mdp.39015004166164

http://books.google.com/books?id=qsY-AAAAYAAJ&pg=PA666&source=gbs_toc_r&cad=3#v=onepage&q&f=false

http://books.google.com/books?id=qsY-AAAAYAAJ&pg=PA666&source=gbs_toc_r&cad=3#v=onepage&q&f=false

http://georgeboole.ucc.ie/index.php?page=11#S01BIx

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