| Instructor: |
Gábor Hetyei
Office: Fretwell 335F, Phone: 867-2543, E-mail: ghetyei@uncc.edu
|
Office hours:
|
MWF 9:30-10:30 am or by appointment.
|
|
| Text: |
Introductory Combinatorics by Kenneth P. Bogarth, third Ed.,
Academic Press.
|
| Prerequisite: |
MATH
2164 or consent of the department.
|
|
Topics:
|
- Sets: Counting Principles. Relations, Functions. Binomial
and Multinomial Theorems. Mathematical Induction. Equivalence
Relations. Partitions. Algebraic counting techniques. The Principle of
Inclusion and Exclusion. Generating Functions. (Chapters 1-2, Chapter
3/Sections 1-2.)
- Graphs and Algorithms: Basic Notions. Eulerian
Walks. Trees. Spanning Trees. Search Trees. Algorithms and their
Interpretation. Isomorphism and
Planarity. Digraphs. Orientation. (Chapter 4/Sections 1-5.)
- Matching and Optimization: Coloring. Graphs and
Matrices. Matching. Bipartite Graphs. Greedy Algorithm. Stable
Marriages. Network Flow. Max-Flow Min-Cut Theorem. (Chapter 5/Sections
1-3, Chapter 6/Section 1.)
|
|
Test Dates:
|
|
Test 1
|
Thursday February 13 2003 7:30-8:50 pm.
|
|
Test 2
|
Thursday March 27 2003 7:30-8:50 pm.
|
| Final Exam |
Thursday May 8 2003, 7:00-10:00 pm
(Double-check in the UNCC Exam
schedule !)
The final exam will be cumulative, consisting of two parts of equal
weight. The first
part will be mandatory, covering only material taught after Test 2. The
second half will contain questions reviewing the material taught before
Test 2. This part will be optional, if left unanswered, I will substitute the
average of your test scores.
|
|
| Homework: |
Homework will be assigned nearly every day, and will be usually collected on
Tuesday. I will make an effort to regularly post the homework on the webpage
http://www.math.uncc.edu/~ghetyei/courses/3166/hw.html
.
In case of discrepancy, what I said in class is "official".
A random selection of the assigned exercises will be graded. Some homework
exercises will be discussed in next class and not graded. Specially
designed assigments will be given and collected every 3 or 4
weeks.
|
| Evaluation: |
Grades will be based on: 20% for the homework, 20% for each of the
tests, and 40% for the final.
|
|
Class meeting: |
TR 7:30-8:50 pm in Denny 217.
|
|
Homepage: |
http://www.math.uncc.edu/~ghetyei/courses/3166/index.html
|