State University College at Buffalo

Department of Mathematics

 

Request for Course

 

 

 

I.     Number and title of course

 

MAT 309 ‑ Discrete Mathematics II

 

 

II.     Reasons for addition to the present curriculum

 

A.   To provide an alternative to the more traditional approach to algebra for those students interested in computational mathematics.

 

B.    To provide an elective mathematics course for stu­dents interested in the mathematics of computation.

 

C.   To continue the study of discrete mathematics begun in Mathematics 301‑Introduction to Modern Algebra I.

 

 

III.      Major objectives of the course

 

A.   To introduce the student to discrete mathematical structures.

 

B.    To provide the student with a foundation in algebraic theory relating to the mathematics of computation.

 

C.   To extend the results and techniques begun in Mathematics 301‑Introduction to Modern Algebra I.

 

 

IV.      Behavioral Objectives

 

The following is a partial list of behavioral objectives.

The student will be expected to know how to:

 

A.   recognize and perform basic operations with discrete

mathematical structures, and

B.    apply the principles of discrete mathematics in

designing systems for computation.

 

 

 

V.      Topical Outline

 

A.   Automata

1.    Building Automata with specified behavior.

2.      Direct products and machine decomposition.

 

B.    Linear Machines and Codes

 

1.    Modules

2.    Group codes

3.      Linear machines and shift registers

4.      Building linear machines with specified behavior

 

C.   Algebraic Coding Theory

 

 

1.    Polynomial rings over a field

2.    Introduction to Cyclic codes

3.    Minimum polynomials and maximum length codes

 

D.     Language Theory

 

1.        Context-free grammars

2.        Tree Automata

3.        Polish notation

4.        Pushdown automata

   

 

 

VI.    Bibliography, texts and references

 

1.    Birkoff, 0. and Bartee, T.C., Modern Applied Algebra

McGraw Hill, 1970..

 

2.    Bobrow, L.S. and Arbib, M.A., Discrete Mathematics

W.B. Saunders, 1974.

 

               3.    Stone, L.S., Discrete Mathematical Structures, SRA   

                                1973.

 

 

 

 

VII.     Presentation and Evaluation

 

A.   Presentation will be by lectures and class discussions.

 

B.    Evaluation will be by examinations, homework and c            

    class participation

 

 

 

VIII.     Prerequisites

 

MAT 30l and MAT 207

 

 

  IX.       Credit

 

3 Semester hours

 

 

   X.        Catalog Description

 

MAT 309 ‑ Discrete Mathematics II

 

Automata, modules, group codes, linear machines, polynomial rings, cyclic codes, minimum polynomials, context‑free gram­mers, tree automata, polish notation, pushdown automata. Prerequisites: MAT 301 and MAT 270

 

XI.    Statement of qualifications of faculty who will teach this course

 

A master's degree in mathematics is a minimum formal educa­tion. All members of this Department meet this requirement. Current staff and facilities are adequate for the offering of this course.

 

The following faculty have experience in the area of dis­crete mathematics:

 

M.W. Boyd, Assistant Professor of Mathematics, Ph.D., SUNY at Binghamton

 

A.C. Green, Assistant Professor of Mathematics, Ph.D., Syra­cuse University

 

 

 

XII.    Statement of Approval

 

This course was examined in accordance with recommended procedures and approved by the Department of Mathematics.