For this assignment, you will submit a single Python source file a2.py
.
Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts.
forall
, exists
,
and/or list comprehensions. Solutions that are more than 2-5 lines in length will receive no credit.
commutative(op,S)
that takes two arguments and returns True
only if the
first argument op
, an operator that takes two arguments, is commutative on the finite set S
.
def commutative(op,S) : return forall(S, lambda x: forall(S, lambda y: op(x,y) == op(y,x)))
associative(op,S)
that takes two arguments and returns True
only if the
first argument op
, an operator that takes two arguments, is associative on the finite set S
.
def associative(op,S) : return\ forall(S, lambda x: forall(S, lambda y: forall(S, lambda z:\ op(op(x,y),z) == op(x,op(y,z)))))
identity(op,S)
that takes two arguments and returns True
only if the
first argument op
(which is itself a function that takes two arguments) has an identity element in S
.
Note that the identity must be both a left and right identity.
# It is important to have the right order for the quantifiers. # There must exist at least one identity element that behaves # like the identity for /all/ the elements of S: # # exists i in S s.t. for all x in S, op(x,i) == op(i,x) == x # # Notice that this is different from a statement such as the one # below: # # for all x in S, exists i in S s.t. op(x,i) == op(i,x) == x # Incorrect. # def identity(op,S) : return exists(S, lambda i: forall(S, lambda x: op(x,i) == op(i,x) == x))
inverses(op,S)
that takes two arguments and returns True
only if for
every element in S
, there is an inverse element with respect to op
.
Note that this is only possible if there is an identity with respect to op
. You may want to write a few
helper functions in order to avoid deeply-nested quantifiers.
# The following is the correct formula: # # there exists i in S s.t. # i is an identity for S # and # for all x in S, exists y in S s.t. op(x,y) == i # # However, equivalents of the following will also be # accepted: # # for all x in S, exists y in S s.t. # op(x,y) == i and i is an identity for S # # For either of the above, "i is an identity for S" should # be a formula equivalent to: # # for all x in S, op(x,i) == op(i,x) == x # # Since we did not explicitly specify whether the identity # must be left- or right-, "op(x,i) == x" or "x == op(x,i)" # alone would be sufficient. def inverses(op,S) : return\ exists(S, lambda i:\ #i is an identity forall(S, lambda x: op(i,x) == op(x,i) == x)\ and\ forall(S, lambda x: exists(S, lambda y: op(x,y) == i)))
randFromPrime()
that takes a single input p
, a prime number,
and generates a set of p
distinct
lists, each of length p
, and each being a "random" reording of the list [ i for i in range(0,p) ]
.
p
distinct integers from the set { i for i in range(0,p) }
.{ i for i in range(0,p) }
.rand()
that takes a single input n
(which might not be prime)
and generates a set of n
distinct
lists, each of length n
, and each being a "random" reording of the list [ i for i in range(0,n) ]
.
n
distinct integers from the set { i for i in range(0,n) }
.{ i for i in range(0,n) }
.floor()
. To use it, add from math
import floor
to the top of your file.
randExtra()
that takes a single input n
(which might not be prime)
and generates a set of n*n
distinct
lists, each of length n
, and each being a "random" reording of the list [ i for i in range(0,n) ]
.
n
distinct integers from the set { i for i in range(0,n) }
.{ i for i in range(0,n) }
.
randByIndex()
that takes two inputs n
and i
. It should return
the i
th element in a "random" sequence of length n
that contains every number in the set
{ k for k in range(0,n) }
. You should not generate the whole list of length n
in memory.
generatePrime()
that takes a single input d
and generates a d-digit (in base 10)
probable prime. Your algorithm should be efficient enough to fairly quickly generate a 1000-digit probable prime, and should not run out
of memory (although it may take quite some time) when generating a 10000-digit probable prime.
probablePrime()
that checks if its input is a probable prime.pow(a,b,m)
that efficiently computes a^{b} mod m.