TOPICS IN DISCRETE MATHEMATICS

MATH 149B, course information

Meetings: MTWF 3:10-4:00 PM, meeting at 235 Wellman. A couple of sessions will take place in Kerr Hall 451 (computer lab) and this will be announced in class.

Instructor: Jesús A. De Loera.

email: deloera@math.ucdavis.edu

URL: http://www.math.ucdavis.edu/~deloera/

Phone: (530)-754 70 29

Office hours: Wednesday 11am-12pm and Friday 1-2pm or by appointment. My office is 580 Kerr Hall.

Text: Biggs N. Discrete Mathematics, Oxford Univ Press, Oxford, second revised edition, 1999.

Description: This course is an introduction to Discrete Mathematics via the study of classical algebraic techniques (groups, rings, fields). In 149B we will study rings and fields and then look at applications to design theory, finite geometry, and coding theory. Applications of algebraic techniques to concrete combinatorial-computational examples will be emphasized. Here is an overview of the topics we will study:

Material up to first Midterm (4 weeks): Modular arithmetic, latin squares, t-designs. Basics of rings and field theory. Polynomial factorization and Polynomial GCD algorithms.

Material for second part (6 weeks): Finite fields, finite geometries and projective planes, Error-correcting codes, linear codes, cyclic codes and generalizations.

Grading policy: The course grade will be based on 4 homeworks (approximately 12-15 problems each) that may include some programming assignment (40 points), one midterm exam set for April 30th (30 pts) and the final exam (30 points). The exams will be closed-book and closed-note. The final exam will be comprehensive. I will assign grades based on an statistical curve of points obtained by all students. Please note that NO late homeworks will be accepted. Feel free to call me or send me email if you are stuck!

Prerequisites: MAT 149A or 150A or equivalent and a willingness to solve many exercises and learn some mathematical software.

FIRST HOMEWORK SET: Due April 16th. 4.6 (2,3,4), 4.7 (all), 4.8 (8,11,12), 6.4 (1,3), 6.5 (2,3),6.6 (19,20).

SECOND HOMEWORK SET: April 30th 15.8 (1,2,3), 15.9 (2,5,11), 16.1 (1-4), 16.3 (1,3,4).

THIRD HOMEWORK SET: May 23th 16.4 (2,4) 16.6 (2,3) 16.8(1,3,4), 16.10 (5,14,17), 17.1 (1,3,4)
Computer exercises: a) Using maple find all the monic irreducible primitive polynomials of degree 2 over Z_7[x].
b) Write a simple maple program that computes pairs of orthogonal latin squares of order 11.

HINT You can download here the maple example we did in class for dealing with finite fields. REMEMBER, to download the file, while pressing the shift key click on the marked text. To use the files, open xmaple then from the file menu open the mws file.

Another set of useful Maple commands, dealing with LINEAR CODES and examples, can be found here . They will be most useful for the next homework

FOURTH HOMEWORK SET: June 6th. 17.2 (1,4), 17.3 (1,2,3), 17.4 (1,2,3). 17.5(3), 17.6(1,2).

The practice final (in pdf format) can be downloaded here

FINAL EXAM INFORMATION: The final exam will be Monday June 11 from 1:30-3:30 pm at 235 Wellman.

2001-03-13