Presenting Pleasant Provisions of the Python Programming Platform for the Pedagogy of Discrete Mathematics

“And now, for something completely different…”
monty_pythons_flying_circus

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:

  1. 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³. 
    pi_is_still_wrong

    ● 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! :-)

  2. 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).

  3. 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'
    >>> 
    
  4. 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! ;-)

  5. 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 "&empty;") 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'}
    >>> 
    

    monty_python_spam

    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 frozensets in Python. Can you guess what Disney movie I reference in my class when this comes up? ;-) .

  6. 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.)

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

  8. 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
mcGuire_hugh

 

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






This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>