| Download

Project: Proj Q

Path: 3-LogicAndAlgorithms.ipynb

Views: ⁵²

Kernel: Python 3 (Anaconda)

Mathematics and Computing
Logic And Algorithms

Spring 2018

Comparisons and Decisions

Algorithms are problem-solving techniques via a sequence of steps of the following form:

Each step changes inputs to outputs (statements)
A subsequence of steps may be repeated (loops)
A decision point may lead to one of two different subsequences of steps (branches)

We introduced statements and loops in the previous notebook, so in this notebook we focus on branches (i.e., decisions), which means we need to explore how logic is implemented in Python.

To begin with, a BooleanStatement is a statement which evaluates as either True or False. Typically, a BooleanStatement is produced by a logical comparison.

For example, let's look at some examples of logical comparisons.

In [1]:

2 > 1

True

In [10]:

x = 5 

0 < x <= 7

True

In [11]:

x != 5

False

In [4]:

3 in range(0,7)

True

In [5]:

10 in range(0,7)

False

Equality is also an important concept, but one which is NOT defined clearly enough in mathematics. Indeed, in Python, there are 3 ways that equality occurs, only 2 of which are logical.

Assignment: Python uses a single equals to bind a name to an object. ASSIGNMENT (single equals) IS NOT LOGICAL.
Equal Value: Python uses == to logically test if two objects have the same value.
Identical Objects: Python uses the word is to test if two objects are identical.

Giving an object a name (mathematically, assigning a value to a variable) does not produce True or False, so it cannot be used to make decisions.

Let's look at examples of all 3.

In [9]:

x = 2.0  # error because numbers cannot be used as variable names

In [7]:

2 == 2.0  # These numbers have the same value

True

In [10]:

2 is 2.0  # 2 is an integer, while 2.0 is a decimal (i.e., float)

False

For example, suppose we want to determine if an integer is either even or odd. A even number has a remainder of 0 if divided by 2, so that

n % 2 is zero if n is even

This is easily implemented as a BooleanStatement.

In [11]:

n = 7 

n % 2 == 0

False

In [12]:

n = 12 

n % 2 == 0

True

All logical comparisons are __BooleanStatement__s, but __BooleanStatement__s can be produced in many, many, many other ways.

We can't possible explore all possible ways, so instead, let's focus on the numpy library for arrays and on the logic associated with mathematical structures like matrices.

First, we execute the usual import/plot configuration structures:

In [13]:

%matplotlib inline
from matplotlib import pyplot as plt

import numpy as np

The names np and plt are conventional and are used because they are short and easy to remember.

Moreover, both numpy and matplotlib have commands that are BooleanStatements.

In [14]:

np.iscomplex(1+1j)

True

In [15]:

np.iscomplex(3)

False

In [16]:

np.iterable([1,2,3])

True

In [17]:

np.iterable( 5 )

False

In [18]:

np.isreal(5)

True

In [19]:

np.isreal(5+1j)

False

In [20]:

plt.is_numlike( 1 )

True

In [21]:

plt.is_numlike("Hi Mom!")

False

In [22]:

plt.fignum_exists(12)

False

Indeed, almost every module includes BooleanStatement commands needed in that module.

__BooleanStatement__s can be used to form compound comparisons using and, not, and or. A compound condition is a logical combination of one or more __BooleanStatement__s A and B according to the following:

A and B evalues to True only if A and B both evaluate to True. Otherwise, evaluates False.
not A evaluates to True if A evaluates to False, and vice versa.
A or B evaluates to True if either of A or B are True, but is False if both A and B evaluate False.

Let's look at some examples.

In [23]:

x = 5 

x > 7 and np.isreal(x)

False

In [24]:

x > 7 or np.isreal(x)

True

In [25]:

not x > 7

True

Indeed, compound statements are potentially quite long and complicated.

In [26]:

a, b, c, d = 3, 7, 9, 11

(a > b ) or ( not ( b == c + d and  np.isreal( b*c ) ) or ( a+d <= b + c) )

True

In [27]:

( ( b in range(a,c) ) or ( a+d <= b*c <= a*d  ) ) and ( not (a + d < b + c) or (a*c > b*d ))

False

Decision Making in Algorithms

In Python, the simplest form for a branching structure (i.e., a decision structure) is

if BooleanStatement : 
    Statement1_if_True
    Statement2_if_True
    ...
Statement1_not_inBranchingStructure
...

The statements in the if structure are executed only if the BooleanStatement evaluates to True.

In [28]:

n = 8 

if( n % 2 == 0 ):
    print('n is even')

n is even

Decision structures (if statements) allow us to implement algorithms in which the sequence of steps depends on the initial input.

For example, the algorithm for Making Change is straightforward. A customer pays at least the price of a product to a cashier, who subsequently __return__s the difference in the form of dollars, quarters, dimes, nickels, and pennies.

The logic for this algorithm is implemented as a series of if statements in the next cell. Try changing the price and the amount paid to see how the logic varies according to the initial inputs.

In [29]:

Price = 1.36
AmountPaid = 5.00 

assert AmountPaid >= Price, "Must pay at least the price"

Return = AmountPaid - Price

print("Change is ")
if( Return / 1 >= 1 ): 
    NumDollars = int( Return/1 )
    print("{0} dollars and ".format(NumDollars))
    Return = Return - NumDollars*1
if( Return / 0.25 >= 1 ):
    NumQuarters = int(Return/0.25)
    print("{0} quarters and ".format(NumQuarters))
    Return = Return - NumQuarters*0.25
if( Return / 0.10 >= 1 ):
    NumDimes = int(Return/0.10)
    print("{0} dimes and ".format(NumDimes))
    Return = Return - NumDimes*0.10
if( Return / 0.05 >= 1 ):
    NumNickels = int(Return/0.25)
    print("{0} nickels and ".format(NumNickels))
    Return = Return - NumNickels*0.05
print("{0} pennies".format( round(100*Return) ) )

Change is 
dollars and 
quarters and 
dimes and 
pennies

An else structure can be added for the case where a BooleanStatement is False:

if BooleanStatement : 
    Statement1_if_True
    Statement2_if_True
    ...
else:
    Statement1_if_False
    Statement2_if_False
    ...
Statement1_not_inBranchingStructure
...

Let's look at an example.

In [30]:

n = 7 

if( n % 2 == 0 ):
    print('n is even')
else:
    print('n is odd')

n is odd

We can also include an unlimited number of elif structures, which test a new BooleanStatement1 for the case where the original BooleanStatement is False:

if BooleanStatement : 
    Statement1_if_True
    Statement2_if_True
    ...
elif BooleanStatement1:
    Statement1_if_BS1_True
    Statement2_if_BS1_True
    ...
else:
    Statement1_if_BS_and_BS1_both_False
    Statement2_if_BS_and_BS1_both_False
    ...
Statement1_not_inBranchingStructure
...

Let's look at an example.

In [31]:

x = 15 

if( x % 2 == 0 ):
    print( '2 is a factor of {0}'.format(x) )
elif( x % 3 == 0 ):
    print( '3 is a factor of {0}'.format(x) )
elif( x % 4 == 0 ):
    print( '4 is a factor of {0}'.format(x) )
else:
    print( '{0} is not divisible by 2, 3, or 4.'.format(x) )

3 is a factor of 15

Typically, these decision structures are combined with loops and other structures in implementing algorithms.

For example, the loop below tests if a given integer x is prime.

In [32]:

x = 817

message = "{0} is prime".format(x) 
for p in range(2,x): # actually only need to go to x//2  
    if( x % p == 0 ):
        message = "{0} is divisible by {1}".format(x,p)
        break # ends the loop
message

'817 is divisible by 19'

Moreover, we can loop over any list or tuple or any other iterable -- such as a numpy array.

In this case, we can use logic and decisions to count or otherwise analyze what is in a list or numpy array.

For example, if create a long numpy array of random integers -- using the randint command -- then we can loop over that array and use a decision statement to count the number of occurences of a given pattern.

In [33]:

from numpy.random import randint

RollsOfADie = randint(1,7,10000)  # 10,000 simulated rolls of a fair die
RollsOfADie

array([2, 2, 2, ..., 3, 4, 1])

In [34]:

cnt = 0  # count starts at 0

for roll in RollsOfADie:
    if( roll % 2 == 0 ): # if roll is even
        cnt += 1
cnt  ## should be about 1/2 of the 10,000 rolls

4967

Of course, this is a simple example. But how about the question like "how many times is the current roll equal to the previous roll"?

In [35]:

cnt = 0  # count starts at 0

prevRoll = 0 # to guarantee we don't count the first roll 
for roll in RollsOfADie:
    if( roll == prevRoll ): # if roll is even
        cnt += 1
    prevRoll = roll
cnt

1572

Indeed, many interesting mathematical questions can be answered in much the same way.

Logic with Lists and Dictionaries

Python allows the use of logic and decisions in many useful ways and in many useful contexts. For example, list comprehension is the creation of a list using the structure

    [ FunctionOfValue for Value in Iterable if BooleanStatement ]

Let's look at an example.

In [36]:

## First 10 squared positive integers  
[n**2 for n in range(1,11) ]

[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Indeed, suppose we wanted to create a numpy array of numbers between 1 and 100 that do not have a factor of 7. This turns out to be quite easy using list comprehension inside of the array command in numpy.

In [37]:

np.array( [n for n in range(1,101) if n % 7 != 0 ] )

array([  1,   2,   3,   4,   5,   6,   8,   9,  10,  11,  12,  13,  15,
        16,  17,  18,  19,  20,  22,  23,  24,  25,  26,  27,  29,  30,
        31,  32,  33,  34,  36,  37,  38,  39,  40,  41,  43,  44,  45,
        46,  47,  48,  50,  51,  52,  53,  54,  55,  57,  58,  59,  60,
        61,  62,  64,  65,  66,  67,  68,  69,  71,  72,  73,  74,  75,
        76,  78,  79,  80,  81,  82,  83,  85,  86,  87,  88,  89,  90,
        92,  93,  94,  95,  96,  97,  99, 100])

Finally, there is a very useful structure for writing algorithms called a dictionary, where a dictionary is a set of key, value pairs.

We can create dictionaries in many ways in Python, but the method we use most often is as a set of key-value pairs:

# the following is a dictionary in Python
ADictionary = { 'key1':value1, 'key2':value2, ..., 'keyn':valuen }

The dict command can also be used to create dictionaries.

In [38]:

SpecialHours = { 'noon': 12, 'midnight': 0, 'firstlight': 7, 'sundown':19 }
SpecialHours

{'firstlight': 7, 'midnight': 0, 'noon': 12, 'sundown': 19}

Because a dictionary is a set of key-value pairs, the order in which they are stored is not preserved (i.e., Python decides).

However, we can access values using keys.

In [39]:

SpecialHours['midnight']

0

In [40]:

SpecialHours['noon']

12

In [41]:

SpecialHours['workStarts'] = 8
SpecialHours

{'firstlight': 7, 'midnight': 0, 'noon': 12, 'sundown': 19, 'workStarts': 8}

Once a dictionary is created, we can access its keys with the keys command; and we can get its values using the values command.

In [43]:

SpecialHours.keys()

dict_keys(['firstlight', 'midnight', 'noon', 'workStarts', 'sundown'])

In [44]:

SpecialHours.values()

dict_values([7, 0, 12, 8, 19])

If we loop over a dictionary, then we are getting the keys one at a time:

In [45]:

for key in SpecialHours:
    print(key, SpecialHours[key] )

firstlight 7
midnight 0
noon 12
workStarts 8
sundown 19

Dictionaries can be very useful when logic is involved when designing algorithms.

For example, let's consider how a dictionary can greatly "clean up" the code for the Making Change example, which we repeat below:

In [46]:

Price = 1.36
AmountPaid = 5.00 

assert AmountPaid >= Price, "Must pay at least the price"

Return = AmountPaid - Price

print("Change is ")
if( Return / 1 >= 1 ): 
    NumDollars = int( Return/1 )
    print("{0} dollars and ".format(NumDollars))
    Return = Return - NumDollars*1
if( Return / 0.25 >= 1 ):
    NumQuarters = int(Return/0.25)
    print("{0} quarters and ".format(NumQuarters))
    Return = Return - NumQuarters*0.25
if( Return / 0.10 >= 1 ):
    NumDimes = int(Return/0.10)
    print("{0} dimes and ".format(NumDimes))
    Return = Return - NumDimes*0.10
if( Return / 0.05 >= 1 ):
    NumNickels = int(Return/0.25)
    print("{0} nickels and ".format(NumNickels))
    Return = Return - NumNickels*0.05
print("{0} pennies".format( round(100*Return) ) )

Change is 
dollars and 
quarters and 
dimes and 
pennies

Notice that we are repeating the same "if" statement several times, each time for a different type of coin (assuming dollar coins!). So first off, let's create a coin dictionary whose keys are the coin names and whose values are the coin values.

In [48]:

CoinDictionary = { 'dollar':1, 'quarter':0.25, 'dime':0.10, 'nickel':0.05 }
CoinDictionary

{'dime': 0.1, 'dollar': 1, 'nickel': 0.05, 'quarter': 0.25}

Once we need to make change, we can simply loop over a list of coin names in the order they need to be considered.

In [49]:

Price = 1.36
AmountPaid = 5.00 

assert AmountPaid >= Price, "Must pay at least the price"

Return = AmountPaid - Price

print("Change is ")
for coinName in ['dollar','quarter','dime','nickel']:
    coinValue = CoinDictionary[coinName]
    if( Return / coinValue >= 1 ): 
        NumCoins = int( Return/coinValue )
        print("{0} {1}s and ".format(NumCoins, coinName) )
        Return = Return - NumCoins*coinValue
print("{0} pennies".format( round(100*Return) ) )

Change is 
dollars and 
quarters and 
dimes and 
pennies

Assignment 3

In the exercises below, $a,b,c,d$ are the last 4 __ nonzero __ digits of your student number in nondescending order ( $a \le b \le c \le d$ ). Also, EnumberLast3NonzeroDigits is the last 3 nonzero digits of your Enumber. For example, if your enumber was E12375609, then $a = 5, \quad b = 6, \quad c = 7, \quad \mathrm{and} \quad d = 9$ and EnumberLast3NonzeroDigits is 569.

1. (0.25 points) Execute the following and describe in the Raw NBconvert cell what list it produced.

list(range(c+d, a, -1) )

In [7]:

a,b,c,d=5,6,7,9
list (range(c+d, a,  -1))

[16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6]

The output does describes a list of eleven positive integers all in order with a range between [6 and 16] starting at 16 and ending at 6.

2. (0.25 points) Execute the following and describe in the Raw NBconvert cell what list it produced.

[n**2 for n in range(b+c, a, -1) if n % 2 == 1 ]

In [8]:

a,b,c,d=5,6,7,9
[n**2 for n in range (b+c, a, -1) if n % 2 ==1 ]

[169, 121, 81, 49]

A list of four positive integers which represent the squared product of four odd numbers [13,11,9,7]

3. (0.5 points) Determine if the following BooleanStatement is True or False for your values of a,b,c,d. Embedded Image

In [8]:

Integers={"a=5", "b=6", "c=7", "d=9"}
Integers

{'a=5', 'b=6', 'c=7', 'd=9'}

In [15]:

a,b,c,d=5,6,7,9
import numpy as np
( (a + d < b + c ) or (a*d - b*c > 0 ) ) and not  np.iscomplex((a*d - b*c)**(0.5))

True

In [0]:

In [0]:

In [0]:

In [11]:

4. (0.5 point) Use list comprehension to create the list of numbers between a and c*d which are not divisible by b.

In [1]:

Integers={"a=5", "b=6", "c=7", "d=9"}
Integers

{'a=5', 'b=6', 'c=7', 'd=9'}

In [4]:

a,b,c,d=5,6,7,9
import numpy as np
np.array( [n for n in range(a,c*d) if n % b != 0 ] )

array([ 5,  7,  8,  9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 25,
       26, 27, 28, 29, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 43, 44, 45,
       46, 47, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62])

In [0]:

5. (0.5 points) Create a dictionary in which the keys are the first names of 5 people you know and the values are their ages, respectively.

In [63]:

Adictionary={'Jack':34, 'Tom':36, 'Chloe':18, 'Charlie':26, 'Megan':23}
Adictionary

{'Charlie': 26, 'Chloe': 18, 'Jack': 34, 'Megan': 23, 'Tom': 36}

In [65]:

Adictionary.keys()

dict_keys(['Chloe', 'Tom', 'Megan', 'Charlie', 'Jack'])

In [66]:

Adictionary.values()

dict_values([18, 36, 23, 26, 34])

6. (1 point) The next cell generates 10,000 digits (numbers = 0,1,2,3,4,5,6,7,8,9). Count the number of times that a digit is between a and b+1 (including a and excluding b+1).

In [1]:

from numpy.random import randint

ArrayOfDigits = randint(0,10,10000)
ArrayOfDigits

array([3, 8, 5, ..., 1, 1, 6])

In [1]:

a,b,c,d=5,6,7,9
from numpy.random import randint
ArrayOfDigits=randint(0,10,10000)
count=0
for num in ArrayOfDigits:
    if num>=a and num<b+1:
        count+=1
print (count)

2041

In [0]:

In [0]:

7. (1 point) Write an algorithm in Python which determines the largest factor of a number x and apply it to EnumberLast3NonzeroDigits

(Hint: suggest you go backwards -- i.e., loop over a descending list such as in #1 and #2; n is a factor of x if x divided by n has a remainder of 0 -- and if n is not equal to x )

In [1]:

import math
def maxPrimeFactor(n):
    maxPrime=-1
    while n%2==0:
        maxPrime = 2
        n = n/2
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n%i == 0:
            maxPrime = i
            n=n/i
    if n>2:
        maxPrime = n
        return int(maxPrime)
print (maxPrimeFactor(394))

197

In [1]:

In [0]:

Mathematics and Computing Logic And Algorithms

Spring 2018

Comparisons and Decisions

Decision Making in Algorithms

Logic with Lists and Dictionaries

Assignment 3

Mathematics and Computing
Logic And Algorithms