***Do either Unit 1 or Unit 2 ..do not do both ***
due March 11
Unit 1 ------------------------------
1, . (Computational) Find the inverses of the following matrices:
You may use programs. You don't need to do this problem by
hand.
1 0 0
1 0 1 mod 2 system
0 1 1
3 0 1
1 1 2 mod 7 system
0 0 4
1 2 3 4
0 1 2 3 mod 26 system
0 0 1 2
0 0 0 9
1 1 0 1 1 mod 2 . Is this matrix non-singular?
0 0 1 1 0 If so find its inverse.
1 1 0 1 0
1 0 1 1 1
0 0 1 0 1
2. (computational) In a particular language there are 12 letters.
Two of these are
used with relative frequency 3; four are used with relative frequency
2, and the remaining six are used with relative frequency 1. Compute
the index of conincidence for monoalphabetic substitutions in this
language. --- 5 points
3, . a) Construct an addition table for Z/11 (the integers mod 11) and
a multiplication table for Z/11 - {0} (the integers mod 11 with
0 removed).
b) As we have discussed a Group G is a set with a defined binary
operation # which is:
i) closed under #
ii) # is an associative operation
iii) there is an identity element e, a#e = e#a = a, for all a in G
iv) each element a of G has an inverse, a^{-1} where
a#a^{-1} = a^{-1}#a = e
Use your table from part a) to show that Z/11-{0} forms a group under *.
(assume associativity)
----------------------------------------------------------------------
Unit 2
1. Consider an equilateral triangle and operations on this triangle.
The triangles vertices are number 1,2 and 3 (starting at the top).
One operation is a rotation of 120 degrees about the center of the
triangle (call it alpha) and another operation is reflecting the
triangle around a verticle line which bisects the triangle and
runs through the top vertex (call that operation beta). These operations
and various compositions of these operations form a group.
a) enumerate all the elements of the group in terms of alpha and
beta. List them.
b) what is the order of the group? what is the order of each element?
c) what are the subgroups?
2. (Computationsal) Given three arbitrary positive integers a,b and c
what is the
probability that gcd(a,b,c) = 1? (their greatest common divisor is 1).
Do not try
and find the answer theoretically but rather approximate the answer
by simulation. Randomly generate three positive integers between 2 and
N (where N is large) and find their gcd. Do this at least 10000 times.
3. a) Suppose we write text of 100 characters into a 10 by 10 rectangle
by rows
then permute the columns (in some prescribed way) and then write
the rectangle out by columns. (columnar transposition)
What is the key?
What is the size of the key space ?
b) answer the questions of part a for the general case where
there are N characters of text (spaces are written as
asterisks).