“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 general programming language, Python provides utilities for showing the numbers that correspond to characters and vice-versa:
ord(x)andchr(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’sInteger.toBinaryString(n)may appear better than Python’sbin(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 + trueistrue, etc., and thatboolvalues 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 forN). 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
asA ∪ ~(B ∩ C), and exercises to write a functionpowerset(S)and a functionis_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 befrozensets 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), andc*g(n). And I think demonstrations like this makeO(),Ω(), 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)) )
