SPRING 2015 MATH 405 – DISCRETE MATH GRILLI
Catalog Description. The course is an introduction to graph theory and combinatorics. The topics will be chosen from the following: the basic properties of graphs and digraphs, graphs as models, Eulerian and Hamiltonian circuits, graph coloring, trees, network algorithms, generating functions, and recurrence relations. Prerequisite. Math 231. One semester; three credits
Textbook AppliedCombinatorics, sixth edition. Alan Tucker, John Wiley & Sons, Inc., 2012.
SyllabusChapter1: Elements of Graph Theory 1.1–1.4
Chapter 2: Covering Circuits and Graph Coloring2.1 – 2.4
Chapter 3: Trees and Searching3.1–3.4
Chapter 4: Network Algorithms 4.1–4.4
Chapter 5: General Counting Methods5.1–5.5
Chapter 6: Generating Functions6.1 – 6.3
Chapter 7: Recurrence Relations7.1 – 7.3
Chapter 8: Inclusion-Exclusion8.1 – 8.2*
*covered as time permits
Evaluation
Homework - You are expected to read the text and complete homework assignments daily. Specified problems will be collected and graded.
Homework problems, in general, must include verbal explanation using complete English sentences. Graphs and diagrams are often helpful. Be sure to label appropriately. Papers must be neat and legible. As problem-solving and creative thinking involve multiple approaches, first drafts of homework are not usually the best submissions. Be sure to include your name on all papers. List the assignment and the date submitted. If the assignment involves multiple pages either staple the sheets or fold them lengthwise. Use pencil on homework submissions and tests.
Ordinarily homework is due at the beginning of the class period and should be turned before the start of class. Homework that is turned in on time will usually be graded with a maximum of ten points. There may be a reduction in total points possible for late homework. Short quizzes may monitor progress.
Tests - I anticipate four 50-minute tests. Tentative dates are:2/6, 3/4, 4/10, 4/29. Make-up tests will only be given in extreme circumstances.
Course grade: homework, quizzes 24%
tests 56%
final exam 20%
Grading scale: A 90-100%, B 80-89%, C 70-79%, D 60-69%, F below 60%
Attendance
If a student has no more than three absences, then the final exam score may replace a test score in determining the student’s final grade. An absence is any time that you are not present for a class. Arriving habitually late for class or leaving early may count as an absence.
Class attendance is expected. CBU.'s policy states that a student who misses eight hours of class may be given a failing grade for the course. If an absence is unavoidable, you are responsible for the material covered in class including assignments.
Time
A rule of thumb for college courses is to spend 2-3 hours studying outside of class for every hour in class. Of course this is an average. If math is difficult for you, you can expect to spend more time in order to succeed. Some for whom math comes easily can learn the concepts with less time. It is extremely difficult to have a full-time job and be a full-time student. Being realistic about your time commitments can save frustration later.
Study time should be fairly evenly distributed. I am unimpressed when people tell me that they spent x hours studying the night before a test (where x is a big number). Studies indicate that the part of the brain that we use to do mathematics suffers when someone hasn't had enough sleep.
Math Center
The Math Center ( ) in CW 321, is available for your assistance.
Proposed Schedule-Math 405Spring 2015
Week 11.1, 1.2 Graph models & Isomorphisms
Week 2 (2 days) 1.3, 1.4Edge Counting & Planarity
Week 31.4, Supp.Also Supplementary Problems
Week 42.1, Test 1Euler Graphs, Test 1
Week 52.2, 2.3Hamilton Graphs, Graph Coloring
Week 62.4, 3.1, 3.2Graph Coloring, Trees, Search, Spanning
Week 73.3, 4.1Traveling Salesperson, Shortest Path in Networks
Week 84.2 Test 2, Minimal Spanning Trees
Spring Break
Week 94.2, 4.3Minimal Spanning Trees, Network Flows
Week 105.1, 5.2Counting Techniques & Principles
Week 11 (2 days)5.3, 5.4 Repetitions, Distributions,
Week 12 (2 days)6.1 Intro Generating Functions, Problem day, Test 3
Week 136.2, 6.3Generating Functions
Week 147.1 – 7.3Recurrence Relations
Week 158.1, 8.2 Venn Diagrams, Inclusion/Exclusion, Test 4
Week 16Wrap Up