“And now, for something completely different…”

By the way, the language is named after the BBC show “Monty Python’s Flying Circus” and has nothing to do with reptiles. Making references to Monty Python skits in documentation is not only allowed, it is encouraged!

: The Python Tutorial, Section 1: “Whetting Your Appetite”

Robert Talbert, one of my colleagues here at GVSU, has been using Python in teaching Discrete Mathematics for Computer Science for years; but I kept playing around with other systems (Haskell or Java) without ever really ‘tasting’ Python. Then, midway through last semester (i.e. just a few months ago), when I was about to tell my students what system they should use to do some work in this introductory course on Discrete Mathematics, I went through the Python tutorial — and I was hooked. Python provided pretty much precisely what I wanted!

I went down the hallway to Robert’s office, and I said:

“Why didn’t you tell me how wonderful Python is?”

He replied:

“I wanted you to find out for yourself.”

(Incidentally, can you tell from this reply of his that Robert is a mathematician? ` `

Here’s what I’m doing with Python this semester:

- Of course it’s necessary to start with teaching students the basics of Python since our CS curriculum here at GVSU does not yet
`(;-)`use Python in our beginning Computer Science course. I start presenting Python during the second week of the course (after covering translation between decimal, binary, and hexadecimal numbers etc. during the first week). And teaching Python is simple, considering how easy it is to start using it: you can just start its interpreter and type expressions which get evaluated. How easy is that?! (The contrast between interpreted and compiled languages is classic.) None of my students have any trouble starting to use it. For an initial homework exercise, I ask them to try some of the actions specified in the Python tutorial, after I show them such actions myself during lecture. And actually what I show them first in lecture is how Python can do this course's entire first week's assignment, translating between decimal and binary and hexadecimal etc., by typing just a few lines of text in Python:Python 3.4.3 (v3.4.3:9b73f1c3e601, Feb 24 2015, 22:43:06) [...] Type "copyright", "credits" or "license()" for more information. >>> >>> # Python uses ">>>" to prompt you for input. >>> # You can enter a comment by starting material with # . >>> >>> # Here's how all of Assignment 1 could have been accomplished: >>> >>> for n in [0, 10, 34, 197, 2015, 40000, 0b0010, 0b1001, 0b00100000, 0b01011010, 0b011111111111, 0x10, 0x5FC, 0xBEAD, 0o10, 0o752643]: print(n, hex(n), oct(n), bin(n), sep='\t') 0 0x0 0o0 0b0 10 0xa 0o12 0b1010 34 0x22 0o42 0b100010 197 0xc5 0o305 0b11000101 2015 0x7df 0o3737 0b11111011111 40000 0x9c40 0o116100 0b1001110001000000 2 0x2 0o2 0b10 9 0x9 0o11 0b1001 32 0x20 0o40 0b100000 90 0x5a 0o132 0b1011010 2047 0x7ff 0o3777 0b11111111111 16 0x10 0o20 0b10000 1532 0x5fc 0o2774 0b10111111100 48813 0xbead 0o137255 0b1011111010101101 8 0x8 0o10 0b1000 251299 0x3d5a3 0o752643 0b111101010110100011 >>> >>> # That's worth 24 points! >>> >>> # But that was relatively advanced material to show how cool >>> # Python is. More fundamental material starts as follows: >>> >>> # You can use Python as a calculator. For example: >>> >>> 33 * 5 165 >>> >>> 2 + 2 4 >>> >>> (50 - 5.0*6) / 4 5.0 >>> >>> 17 / 3 5.666666666666667 >>> >>> # There are applications such as security which use whole- >>> # number quotients and remainders instead of exact division; >>> # Python provides these operations e.g. as follows: >>> >>> 17 // 3 5 >>> >>> 17 % 3 2 >>> >>> # And in Python you can raise a number to a power (more >>> # conveniently than via Java's Math.pow(x,y) ), e.g. as >>> # follows: >>> >>> 5 ** 2 25 >>> >>> 2 ** 7 128 >>> >>> # You can set variables in Python, e.g. together as follows: >>> >>> width,height = 20,59 >>> >>> width * height 1180 >>> >>> # And Python provides strings and lists with which you can >>> # use [] (again, more conveniently than Java's .charAt(i) ) . . . >>> # Programming instructions include if , while , etc. . . . >>> # You can use for as follows, for example: >>> >>> for n in range(5): print(n*n, end=' ') 0 1 4 9 16 >>> >>> for x in 'HELLO everybody out there in the WORLD!': print(x.upper() if x in 'aeiou' else x.lower(), end='') hEllO EvErybOdy OUt thErE In thE wOrld! >>> >>> >>> # You can define a function and invoke it as follows, e.g.: >>> >>> def f(x): return x % 3 == 0 or x % 5 == 0 >>> f(18); f(19); f(20) True False True >>> >>> # Here's another example: >>> >>> from math import sqrt >>> def isprime(n): if n <= 1: return False for d in range(2, int(sqrt(n)) + 1): if n % d == 0: return False return True >>> for n in range(9): print('isprime(' + str(n) + '):', isprime(n)) isprime(0): False isprime(1): False isprime(2): True isprime(3): True isprime(4): False isprime(5): True isprime(6): False isprime(7): True isprime(8): False >>>

After presenting that initial material, I give students exercises including the following:

● Assign the value 6.283185307179586 to the symbol

`tau`

, which some people think is more appropriate than`pi`

. Then, define the function`volume_sphere(r)`

, using the formula (2/3)·`tau`

·r³.

● An integer number is said to be a

*perfect number*if its factors, including 1 (but not the number itself), sum to the number. For example, 6 is a perfect number, because 6 = 1 + 2 + 3, and 8 is not a perfect number, because 8 ≠ 1 + 2 + 4. Write a function`perfect(n)`

that determines whether parameter`n`

is a perfect number.

[Acknowledgement: this exercise is derived from Deitel & Deitel.]*(While I don't present*`map()`

or`lambda`

with the initial material here, I do ask the students to try, for example,`list(filter(perfect, range(9999))`

.)The total number of points for this Homework Assignment #2 is 24, and my students' median score is 24 and their mean is 22.89. Looks like Python is easy to learn!

- Next, like any general programming language, Python provides utilities for showing the numbers that correspond to characters and vice-versa:
`ord(x)`

and`chr(n)`

. I ask students to use these utilities to do Caesar ciphering and deciphering. Continuing to use the interpreter (since this course's purpose is Discrete Math, not really programming per se), managing input is a non-issue, so students can do this work much more easily than they could in Java (which I had students use in the past).

- Above, I showed
`bin(n)`

. Students can use it when I ask them to learn operations on binary numbers: addition, multiplication, shift left, bitwise AND, etc. Of course Python provides all the standard bitwise operators. And whereas Java's`Integer.toBinaryString(n)`

may appear better than Python's`bin(n)`

for negative integers (by the way it's because Python's integers aren't limited in size), well, we're Computer Science professors and Python is a programming language:>>> def bin_ex(n): bitlist = [] while n != 0 and n != -1: bitlist.append(chr((n & 0b1) + ord('0'))) n >>= 1 return ('0b...' + ('11111' if n == -1 else '00000') + ''.join(reversed(bitlist))) >>> bin_ex(89) '0b...000001011001' >>> >>> bin_ex(-89) '0b...111110100111' >>>

- I don't use Python for this course's next topics: boolean algebra, propositional calculus, predicate logic, and introduction to writing proofs — these topics appear to me to require skills that are orthogonal to mere computation. (Actually I do use the C programming language to show students that
`true + true`

is`true`

, etc., and that`bool`

values are output as`0`and`1`.) A few years ago I was actually the instructor of record for an undergraduate Honors College student's Senior Project which was a Python program that performed theorem proving. But I don't have my students use that Python program: to learn theorem proving for the Computer Science curriculum, I think students need to 'get their hands dirty' more, by trying to construct proofs themselves. For reference, consider learning outcomes specified in "Computer Science Curricula 2013":

- Convert logical statements from informal language to propositional and predicate logic expressions.
- Apply formal methods of symbolic propositional and predicate logic, such as calculating validity of formulae and computing normal forms.
- Use the rules of inference to construct proofs in propositional and predicate logic.
- Apply each of the proof techniques (direct proof, proof by contradiction, and induction) correctly in the construction of a sound argument.

I haven't found these outcomes achievable via students computing or programming. (But if such was possible, I bet it would be possible in Python!

- Next, Python provides utilities for sets — even using braces and set comprehension a.k.a. set-builder notation; e.g. from the Python Tutorial etc.:
>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'} >>> print(basket) # show that duplicates have been removed {'orange', 'banana', 'pear', 'apple'} >>> sorted(basket) ['apple', 'banana', 'orange', 'pear'] >>> >>> len(basket) # |basket| 4 >>> 'orange' in basket # fast membership testing True >>> 'crabgrass' in basket False >>> >>> { 1, 3, 3, 3, 5, 5, 5, 5, 5 } == { 5, 3, 1 } True >>> >>> {2,6} < {2,4,6} # test {2,6} ⊂ {2,4,6} True >>> {2,8} <= {2,4,6} # test {2,8} ⊆ {2,4,6} False >>> >>> { n**2 for n in range(9) } # { n² | 0 ≤ n < 9 } {0, 1, 64, 4, 36, 9, 16, 49, 25} >>> sorted(_) [0, 1, 4, 9, 16, 25, 36, 49, 64] >>> >>> A = {1,4,7,10} >>> B = {1,2,3,4,5} >>> C = {2,4,6,8} >>> empty = set() # While Python doesn't use {} for the empty >>> # set, we normally use some special symbol such >>> # as ∅ ("\empty" or "∅") anyway, right? >>> >>> # Python uses | for union and & for intersection, etc.: >>> >>> A | empty {1, 10, 4, 7} >>> sorted(_) [1, 4, 7, 10] >>> >>> B & C {2, 4} >>> >>> A - B {10, 7} >>> sorted(_) [7, 10] >>> >>> # If you specify a universe U, you can perform complement >>> # of a set S via U - S -- as in textbooks such as Rosen. . . . >>> # Beyond binary union and intersection shown above, Python >>> # can do a ‘big’ union or intersection of a bunch of sets, >>> # e.g. as follows: >>> >>> S1 = set('whisper') >>> S2 = set('this') >>> S3 = set('quickly') >>> S4 = set('here') >>> S5 = set('please') >>> >>> def union(X,Y): return X|Y # to be able to use ...reduce() >>> import functools >>> functools.reduce(union, [S1,S2,S3,S4,S5]) {'i', 'l', 'r', 'h', 'e', 'u', 'y', 'a', 'p', 't', 'c', 'q', 'w', 'k', 's'} >>>

By the way, I actually show my students the following:

>>> {'spam', 'spam', 'spam', 'spam', 'spam', 'spam', 'eggs', 'spam'} {'spam', 'eggs'} >>>

To challenge me, you might ask:

`What about infinite sets? Python can't represent them like Haskell, can it? Huh? Huh? Can Python do that? Can it?`Well, observe:>>> import itertools >>> >>> N = itertools.count() >>> >>> 0 in N True >>> next(N) 1 >>> next(N) 2 >>> next(N) 3 >>> next(N) 4 >>> next(N) 5 >>> 8 in N True >>> 2**2**2**2 in N True >>> 7654321 in N True >>> >>> Z = map(lambda n: -n//2 if n%2==1 else n//2, itertools.count()) >>> >>> list(itertools.islice(Z, 20)) [0, -1, 1, -2, 2, -3, 3, -4, 4, -5, 5, -6, 6, -7, 7, -8, 8, -9, 9, -10] >>>

Of course, it’s necessary to handle infinite sets carefully as in Haskell (with e.g.

`[0..]`

), avoiding for example any attempt to display such entirely or check a value which has already been ‘passed’ (such as a negative one for`N`

). Nonetheless, I think this is cool.Now, when a 'calculator' appears to be available to do students' math homework for them, a teacher might react negatively. But I think a 'calculator' actually provides opportunities for pedagogy to quickly get through relatively mundane details and reach more thorough or deeper understanding of concepts, e.g. set identities. (How good are your students’ proofs using set identities if they haven’t been able to clearly see the results of some of the operations such as union and complement?) And of course it's also possible to use a 'calculator' to verify or clarify points that students have doubts about such as what is the cardinality of

`{∅, {∅}}`

, and whether`{1,2,3}`

may be a subset of itself.Exercises that I assign to students on this material include simple 'calculator' exercises to figure out how to get Python to calculate a range of set expressions such

as`A ∪ ~(B ∩ C)`

, and exercises to write a function`powerset(S)`

and a function`is_partition(𝒞)`

, where`𝒞`

is a collection or set of sets. (By the way, the sets that are inside a collection or set of sets actually need to be`frozenset`

s in Python. Can you guess what Disney movie I reference in my class when this comes up?`;-) .` - Following sets, the next topic in this course is Tuples and Relations. Well, guess what Python provides — even using traditional notation, if you want?
>>> # {1,2,3} X {'a','b','c'} : >>> R1 = { (n,x) for n in {1,2,3} for x in 'abc' } >>> R1 {(2, 'b'), (2, 'a'), (1, 'c'), (3, 'a'), (1, 'a'), (1, 'b'), (3, 'b'), (2, 'c'), (3, 'c')} >>> sorted(_) [(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b'), (2, 'c'), (3, 'a'), (3, 'b'), (3, 'c')] >>> >>> R2 = {('a','abacus'), ('b','book')} >>> >>> # join: >>> R_join = { (n,x1,w) for (n,x1) in R1 for (x2,w) in R2 if x1 == x2 } >>> R_join {(2, 'b', 'book'), (3, 'b', 'book'), (1, 'b', 'book'), (3, 'a', 'abacus'), (2, 'a', 'abacus'), (1, 'a', 'abacus')} >>> sorted(_) [(1, 'a', 'abacus'), (1, 'b', 'book'), (2, 'a', 'abacus'), (2, 'b', 'book'), (3, 'a', 'abacus'), (3, 'b', 'book')] >>> >>> # projection: >>> R_proj = { (n,w) for (n,x,w) in R_join } >>> R_proj {(2, 'abacus'), (1, 'book'), (1, 'abacus'), (3, 'abacus'), (2, 'book'), (3, 'book')} >>> sorted(R_proj) [(1, 'abacus'), (1, 'book'), (2, 'abacus'), (2, 'book'), (3, 'abacus'), (3, 'book')] >>> >>> # Would you prefer using column indexes? >>> >>> R_proj = { (tuple[0],tuple[2]) for tuple in R_join } >>> sorted(R_proj) [(1, 'abacus'), (1, 'book'), (2, 'abacus'), (2, 'book'), (3, 'abacus'), (3, 'book')] >>> . . .

(The video clip I show to my students regarding relations may be a little risqué; sorry.)

- The next topic in this course is an introduction to mathematical induction. See above regarding whether students’ learning to construct proofs may be very susceptible to processing by a programming environment.

- The next topic is performance: O() etc. And look what you can do in Python:
>>> def f_3p7(n): return 3*n + 7 >>> def f_1(n): return n >>> def test_O(f, g, c, n0): print(list(map(lambda n: f(n) <= c*g(n), range(n0, n0 + 12)))) # range(n0, n0 + 12) fits nicely on screen; # of course you can extend further, e.g. n0 plus # powers of 2... >>> test_O(f_3p7, f_1, 4, 7) [True, True, True, True, True, True, True, True, True, True, True, True] >>> >>> def f_5nlgn(n): return 5*n*lg(n) >>> def f_sq(n): return n**2 >>> test_O(f_5nlgn, f_sq, 2, 8) [True, True, True, True, True, True, True, True, True, True, True, True] >>>

I actually show students the values of

`f(n)`

,`g(n)`

, and`c*g(n)`

. And I think demonstrations like this make`O()`

,`Ω()`

, etc. come more alive for students. Seeing actual values appears to clarify relative growths more than considering 'abstract' aspects of functions such as derivatives (and how memorable are the positions of different curved lines in graphs?).

What computing systems do you like to use in your introductory course on Discrete Mathematics for Computer Science? What are the strengths (and/or weaknesses) that you perceive with them?

Regards,

Hugh McGuire

P.S. A few days after I originally made this posting, I gave a midterm examination to this class; and here's what I asked about Python. (Did I say above that Python might not be good for boolean algebra and logic? ` `

[8 points] What are Python's outputs if material is entered as follows?

(Write the outputs in the spaces for them below.)>>> 5 ** 3 >>> >>> 2 ** 6 >>> >>> for n in range(26): print(chr(n + ord('A')), end = ' ') >>> print('A B C bar(C) (B and bar(C)) (A or (B and bar(C)))') >>> # Show the output from this print() in the big space below. >>> >>> # Python uses or and and for boolean-algebra + and * >>> # -- the outputs really are 0s and 1s. >>> >>> def bar(v): return 1 - v # boolean-algebra 'bar' (:-) >>> for A in [0,1]: for B in [0,1]: for C in [0,1]: print(A, B, C, ' ', bar(C), ' ', B and bar(C), ' ', A or (B and bar(C)) )