MATHS 415: Mathematics of Coding and Communication (3)

Syllabus

1.  Prerequisite:  MATHS 311 or permission of the department chairperson. 

2.  Course Description:  Exploration of applications of number theory, group theory and linear algebra to areas such as cryptography and error-correcting codes; applications of graph theory to resource allocation and route planning; other possible topics selected by the instructor.

3. Course Objectives:  This course concentrates on parts of modern applied mathematics which do not require extensive background in analysis or differential equations.  The specific topics and applications are chosen so that students may become acquainted with the applications and questions on the cutting edge of current research, with a minimum of preparation.  The course may also serve as preparation for in-depth study in these areas.

4.  Course Rationale:  Digital communications have pervaded our lives and permanently altered the structure of our society.  With this revolution has come the need for accurate and secure transmission of information, and the need to solve complex problems in planning and resource allocation.  These needs have driven the development of new and exciting mathematics, large parts of which are accessible to mathematically mature undergraduates.  It is highly appropriate that we take the opportunity to show students how mathematics is used in these (and other) aspects of the modern world. 

5.  Course Content:  It is suggested that the instructor divide the course into units according to topic area. Three possible units include:

a. Error-correcting codes:  binary vectors and matrices, Hamming distance, error detection, error correction, Hamming codes, connections with lattices and sphere packing. (Suggested resources:  Berlekamp, Algebraic Coding Theory; Conway and Sloane, Sphere Packings, Lattices and Groups).

b. Cryptography:  prime numbers, divisibility, Euclidean algorithm, Fermat’s little theorem, RSA encryption, primality tests, attacks on RSA, discrete logarithm, ElGamal encryption, digital signature schemes, smart cards, other encryption schemes as time permits.  (Suggested resources include:  Koblitz, A Course in Number Theory and Cryptography;  Menezes, Van Oorschot and Vanstone, Handbook of Applied Cryptography; Salomaa, Public-key Cryptography)

c. Graph theory:  graphs, Hamiltonian paths, traveling salesman and postman problems, digraphs, scheduling problems, critical paths, minimal spanning trees (Suggested resources include:  Goodaire and Parmenter, Discrete Mathematics with Graph Theory)

6.  Course Format:  lecture/discussion.

7.  Methods of Evaluating Student Performance:  Typical components are homework assignments, projects, papers, and take-home exams (possibly involving group work); in-class exams; class participation and student presentations.  The evaluation and weight of these components are at the discretion of the instructor.  Students may be evaluated on their understanding of the content material of the course, their ability to solve problems related to the course material, and on their ability to communicate mathematically to others orally and/or in writing.  

8.  Evaluation of the Course:  The instruction of the course is evaluated by departmental student evaluations and peer evaluation.  The course is reviewed and revised periodically by the Departmental Undergraduate Programs Committee.  

T. Ivey, rev. R. Bremigan, Spring 2002, rev. M. Karls 2/2005 and Fall 2006