Home‎ > ‎Lectures‎ > ‎

MTH 263: Discrete Mathematics


Announcements:

Course Contents

Description:  Concepts and methods of discrete mathematics with an emphasis on their application to computer science. Logic and proofs, sets and relations, algorithms, induction and recursion, combinatorics, graphs and trees.

Software: Maple 14

Course Notes, Reviews

Textbook:     Discrete Mathematics, Laszlo Lovasz, Jozsef Pelikan, Katalin L. Vesztergombi    
ISBN: 0-387-95584-4 (hardcover)
ISBN: 0-387-95585-2   (softcover)                                                                                                              



Other books used in the past and recomended:   Discrete Math by Grossman

Grading:

There will be three midterms and the final weighted as follows:

  • Midterm I:      20%
  • Midterm II:     20%
  • MidtermIII:     20%
  • Final              40%
Grades will be computed using the following formula

 grade= (T-35)/15

where T is the total percentage score during the semester.


Course Policies: 

For all the problems and concerns you might have you must talk to me. No  makeups will be given other then in case of documented emergencies. cellular phones or any electronic equipment is allowed during lecture. No calculators of any kind are  allowed. Further, I do not tolerate any kind of academic dishonesty. Appropriate measures according to Oakland University regulations will be take for any case of cheating or breaking other rules.  Class participation is mandatory.


Project

The following is Maple code that implements what we covered in class.  Use the same method to encrypt and then decrypt 
"Your name"
You have to present all computations.  Use the same matrix as matrix A below.  

A program to encrypt using matrices mod n:
Input: 1) string S
2) the matrix A
3) the modul n

Output: The encrypted message E

1) Convert the string S of length 2r to a list L containing ASCCI codes (S --->
L)
2) Compute L mod n
3) Built the data matrix X (the above list becomes a 2 by r )

X:=[ [ L[1], L[3], .... L[r] ]
[ L[2], L[4], ....L[2r]
]

4) Compute the matrix Y=AX (2 by r)
5) Convert the matrix Y to a list LL of length 2r
6) Convert the ASCII characters to integers 0..28
7) Find the encrypted message

_____________________________________________________________

> restart:
> with(LinearAlgebra:-Modular):
> A:=Matrix([[23,2],[2, 6]]); A_1:=Matrix(linalg[inverse](A)) :
                           Matrix(%id = 4307211840)
> L:=convert("Spring is coming", bytes); nops(L);
 [83, 112, 114, 105, 110, 103, 32, 105, 115, 32, 99,  111, 109, 105, 110, 103]
                                      16
> if irem(nops(L),2)=1 then L:=[op(L),32]; fi:
> L;
 [83, 112, 114, 105, 110, 103, 32, 105, 115, 32, 99, 111, 109, 105, 110, 103]
> for i from 1 to nops(L) do
> if L[i]=32 then L[i]:=26: elif L[i]=33 then L[i]:=28 elif L[i]=63 then
> L[i]:=27 elif L[i]>96 then L[i]:=L[i]-97: else L[i]:=L[i]-65 fi; od:
> L;
          [18, 15, 17, 8, 13, 6, 26, 8, 18, 26, 2, 14, 12, 8, 13, 6]
We create a matrix X (2 by r) of all 0's
> X:=Matrix(2, nops(L)/2);
                           Matrix(%id = 4307213760)
> for i from 1 to nops(L) do X[irem(i+1,2)+1,iquo(i+1,2) ]:=L[i] od:
> X;
                           Matrix(%id = 4307213760)
> Y:=Multiply(29, Mod(29,A,integer[]), Mod(29,X,integer[]));
                           Matrix(%id = 4307214120)
> LL:=[]:
> for i to nops(L)/2 do LL:=[op(LL),Y[1,i]]: LL:=[op(LL),Y[2,i]]; od:
> LL;
        [2, 13, 25, 22, 24, 11, 11, 27, 24, 21, 12, 11, 7, 16, 24, 11]
> for i from 1 to nops(LL) do
> if LL[i]=26 then LL[i]:=32: elif LL[i]=28 then LL[i]:=33 elif LL[i]=27 then
> LL[i]:=63 else LL[i]:=LL[i]+65 fi; od:
> LL; 
       [67, 78, 90, 87, 89, 76, 76, 63, 89, 86, 77, 76, 72, 81, 89, 76]
> convert(LL, 'bytes');
                              "CNZWYLL?YVMLHQYL"
Define the above expression as a function:
> restart;
> with(LinearAlgebra:-Modular):
> encrypt:=proc(S, A) local L, i, X, Y, LL;
> L:=convert(S, bytes);
> #
> if irem(nops(L),2)=1 then L:=[op(L),32]; fi:
> L;
> for i from 1 to nops(L) do
 
> if L[i]=32 then L[i]:=26: elif L[i]=33 then L[i]:=28 elif L[i]=63 then
> L[i]:=27 elif L[i]>96 then L[i]:=L[i]-97: else L[i]:=L[i]-65 fi; od:
> L;
> X:=Matrix(2, nops(L)/2);
 
> for i from 1 to nops(L) do X[irem(i+1,2)+1,iquo(i+1,2) ]:=L[i] od:
> Y:=Multiply(p,Mod(29,A,integer[]),Mod(29,X,integer[]));
> LL:=[]:
> for i to nops(L)/2 do LL:=[op(LL),Y[1,i]]:LL:=[op(LL),Y[2,i]]; od:
> LL;
> for i from 1 to nops(LL) do
> if LL[i]=26 then LL[i]:=32: elif LL[i]=28 then LL[i]:=33 elif LL[i]=27 then
> LL[i]:=63 else LL[i]:=LL[i]+65 fi; od:
> LL; 
> convert(LL, 'bytes'); 
> end:

Using the function

> p:=29;
                                      29
> A:=Matrix([[21,5],[12, 6]]); A_1:=Matrix(linalg[inverse](A)) ;
                           Matrix(%id = 4307187384)
                           Matrix(%id = 4307187504)
> enc_mes:=encrypt("Spring is coming", A);
                              "SQUUNSGMPYZVCSNS"
> encrypt(enc_mes, A_1);
                              "SPRING IS COMING"












 






Homework:

1.2:    6,  17, 18;
1.8:    10-13, 17-18, 24, 27, 31
2.1:    12-13
2.5:    1-4
3.1:    1-3
3.2:     1
3.8:     4, 8, 9
4.1:     2, 3
4.2:     1-3, 5,
4.3:     8,9, 12, 13, 16

6.1:   3, 4, 6
6.3:   3
6.6:   1, 2, 3

Handout (version posted below)

Page 35:  22-26, 28-32.
Page 40: 1-6

 


ċ
Handout.pdf
(4k)
Tony Shaska,
Jan 4, 2011, 6:57 PM