Syllabus 149A: Discrete Mathematics
Winter 2003

Lectures: MWF 3:10-4:00pm, Wellman 212
Instructor: Anne Schilling, Kerr Hall 578, phone: 754-9371, anne@math.ucdavis.edu
Office hours: Monday 2:00-3:00, Friday 1:30-3:00
Discussion section: T 3:10-4:00pm, Wellman 212
T.A.: Lipika Deka, Kerr 577, deka@math.ucdavis.edu
Office hours: Tuesday 11:00-12:00, Wednesday 12:00-1:00pm
Text: N.L. Biggs, Discrete Mathematics, Oxford University Press, revised edition, 1999, ISBN 0-19-853427-2
Pre-requisite: MAT 108, 22A, 21 or equivalent
Problem Sets: There will be weekly homework assignments, handed out on Wednesday, due the following Wednesday.
You are encouraged to discuss the homework problems with other students. However, the homeworks that you hand in should reflect your own understanding of the material. You are NOT allowed to copy solutions from other students or other sources. No late homeworks will be accepted. Solutions to the problems will be discussed in the discussion section. This is also a good forum to get help with problems and to ask questions!
Exams: Midterm February 12, Final exam March 18 at 10:30 am
There will be no make-up exams!
Grading: The final grade will be based on: Problem sets 20%, Midterm 30%, Final 50%
Web: http://www.math.ucdavis.edu/~anne/WQ2003/149A.html

Course description

This course is an introduction to Discrete Mathematics via the study of classical algebraic techniques (groups, rings and fields). The first part (149A) focuses on finite groups. We will explore the applications of groups to combinatorics, cryptography, number theory, and symmetries in geometry. The goal is that the students develop a good understanding of the key properties of a group and how they relate to finite objects such as permutations, graphs, partitions, codes, polyhedra, etc.. The class is primarily based on Chapters 3-6 and 13-20 of Biggs' book.

1. Permutations and the symmetric group
permutations, counting derangements, cycle decompositions and conjugacy classes, the symmetric group, the 15-puzzle and parity of permutations, A_n and other classical subgroups and S_n

2. Basic group theory and applications
cosets, Lagrange's theorem, the RSA public encryption system

3. Group actions
group actions, Frobenius-Burnside lemma, orbits, graphs and groups, groups of automorphisms of a graph

4. Groups in symmetries
finite groups of rigid motions, the Platonic solids, coloring problems, Polya's counting theorem

Problem sets

Homework 0: Send me an e-mail at anne@math.ucdavis.edu and tell me something about yourself, what kind of math you like, what you expect of the class or anything else, so that I can get to know you all a little bit!

Homework 1: due January 15, 2003 in class; ps or pdf
Solutions: ps or pdf

Homework 2: due January 22, 2003 in class; ps or pdf
Solutions: ps or pdf

Homework 3: due January 29, 2003 in class; ps or pdf
Solutions: ps or pdf

Homework 4: due February 5, 2003 in class; ps or pdf
Solutions: ps or pdf

Homework 5: due February 12, 2003 in class; ps or pdf
Solutions: ps or pdf

Homework 6: due February 19, 2003 in class; ps or pdf
Solutions: ps or pdf

Homework 7: due February 26, 2003 in class; ps or pdf
Solutions: ps or pdf

Homework 8: due March 5, 2003 in class; ps or pdf
Solutions: ps or pdf

Homework 9: due March 12, 2003 in class; ps or pdf
Solutions: ps or pdf

Here is the Maple program we worked on in class on February 21: ps or pdf

Here is a Maple program using Polya's theorem: ps or pdf

Practice Midterm ps or pdf
Practice Final ps or pdf
Solution: ps or pdf
anne@math.ucdavis.edu