Syllabus 149A: Discrete Mathematics
Winter 2006


Important: The final exam will take place March 22 4-6pm in Wellman 6!
Office hours during finals week: James 3/17 11-12, 3/20 12-1, 3/21 11-12
Lectures: MWF 3:10-4:00pm, CRUESS 107
Instructor: Anne Schilling, MSB 3222, phone: 754-9371, anne@math.ucdavis.edu
Office hours: M 2-3pm, Th 11am-12pm
Discussion section: T 3:10-4:00pm, CRUESS 107
T.A.: James Parmenter, MSB 3206, capnjim@math.ucdavis.edu
Office hours: Monday 12-1pm, Tuesday 11am-12pm, Fridays 11am-12pm
Text: N.L. Biggs, Discrete Mathematics, Oxford University Press, second edition, 2002, ISBN 0-19-850717-8
Pre-requisite: MAT 108, 22A 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 15 in class, Final exam March 22 at 4pm
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/WQ2006/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 10-13 and 20-27 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 18, 2006 in class; ps or pdf
Solutions: ps or pdf

Homework 2: due January 25, 2006 in class; ps or pdf
Solutions: ps or pdf

Homework 3: due February 1, 2006 in class; ps or pdf
Solutions: ps or pdf

Homework 4: due February 8, 2006 in class; ps or pdf
Solutions: ps or pdf

Homework 5: due February 15, 2006 in class; ps or pdf
Solutions: ps or pdf

Homework 6: due February 22, 2006 in class; ps or pdf
Solutions: ps or pdf

Homework 7: due March 1, 2006 in class; ps or pdf
Solutions: ps or pdf

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

Homework 9: due March 15, 2006 in class (last one!); ps or pdf
Solutions: ps or pdf

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

Here is a handout from class March 3: ps or pdf

Practice Midterm: ps or pdf
Solutions by James: ps or pdf

Practice Final: ps or pdf
Solutions: ps or pdf