Spring 2017 Math 405 Discrete Math Grilli

SPRING 2017 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 Applied Combinatorics, sixth edition. Alan Tucker, John Wiley & Sons, Inc., 2012.

Syllabus Chapter1: Elements of Graph Theory 1.1–1.4

Chapter 2: Covering Circuits and Graph Coloring 2.1 – 2.4

Chapter 3: Trees and Searching 3.1–3.4

Chapter 4: Network Algorithms 4.1–4.2

Chapter 5: General Counting Methods 5.1–5.4

Chapter 6: Generating Functions 6.1 – 6.2

Chapter 7: Recurrence Relations 7.1 – 7.3

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 three tests. Tentative dates are: 2/7, 3/16, 4/20. Make-up tests will only be given in extreme circumstances.

Course grade: homework, quizzes 20%

tests 60%

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 (http://www.cbu.edu/math-center ) in CW 321, is available for your assistance.

Proposed Schedule-Math 405 Spring 2015

Week 1 1.1, 1.2 Graph models & Isomorphisms

Week 2 (2 days) 1.3, 1.4 Edge Counting & Planarity

Week 3 1.4, Supp. Also Supplementary Problems

Week 4 2.1, Test 1 Euler Graphs, Test 1

Week 5 2.2, 2.3 Hamilton Graphs, Graph Coloring

Week 6 2.4, 3.1, 3.2 Graph Coloring, Trees, Search, Spanning

Week 7 3.3, 4.1 Traveling Salesperson, Shortest Path in Networks

Week 8 4.2 Test 2, Minimal Spanning Trees

Spring Break

Week 9 4.2, 4.3 Minimal Spanning Trees, Network Flows

Week 10 5.1, 5.2 Counting 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 13 6.2, 6.3 Generating Functions

Week 14 7.1 – 7.3 Recurrence Relations

Week 15 8.1, 8.2 Venn Diagrams, Inclusion/Exclusion, Test 4

Week 16 Wrap Up