2. Teaching
3. MAT226
4. Syllabus

Prerequisites

(MAT 121 or MAT 136) with a grade of C or better

Catalog Description

Elementary discrete mathematics including topics from graph theory and combinatorics with emphasis on problem solving.

Course Content

1. Counting Theory: brute force counting, multiplication principle, subtraction principle, addition principle, division principle, pigeonhole principle, inclusion-exclusion, permutations, combinations, sets, unions, intersections, combinatorial proof, binomial coefficients, multinomials, the Mississippi problem, stars-and-bars technique, balls-in-bins, equally likely probability computations (but not axiomatic probability, not expectation).
2. Graph Theory: graphs, digraphs, multigraphs, weighted graphs, special graphs (e.g., complete, bipartite), matrix representation, walks, paths, circuits, cycles, connected components, isomorphisms, degree (valence), the handshaking lemma, matching and the marriage theorem, planar graphs, Euler’s formula, colorings of graphs, trees, spanning trees, traversal (Euler and Hamilton paths and circuits); algorithms: Prim, Kruskal, Dijkstra, etc.; applications of graphs to scheduling, efficient use of resources, etc.
3. Induction and Recursion: constructing recurrence relations for counting problems, solving simple recurrence relations, mathematical induction, generalized induction, strong induction.
4. Additional topics as time permits such as generating functions, probability, chromatic polynomial.

The mathematician does not study pure mathematics because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.

Learning Outcomes

Upon successful completion of the course, students will be able to:

1. Analyze a counting problem.
   • Determine which technique or techniques are relevant.
   • Determine how the processes are nested.
   • Apply them in an organized manner to produce a correct result.
   • Express the process and logical reasoning in writing.
   • Calculate basic discrete probabilities using counting methods.
2. Use techniques of graph theory effectively.
   • Define and identify particular kinds of graphs (planar, directed, undirected, complete, bipartite, etc.).
   • Identify and derive properties of graphs.
   • Express a discrete problem (scheduling, planning, relationships, etc.) in graph-theoretic terms. -Use graphs to model and solve problems.
3. Use techniques of induction and recursion.
   • Write proofs using all variations of mathematical induction.
   • Define sequences recursively. -Model appropriate phenomena with recursively defined sequences.
   • Solve some recursions to obtain closed-form solutions.
   • Obtain results involving counting or graph theory using inductive thinking, i.e., informal induction.
4. Demonstrate mathematical communication and reasoning skills.
   • Provide convincing justifications for results in writing.
   • Demonstrate persistence in solving problems.
   • Solve problems that do not fit an exact pattern discussed in class.

The impediment to action advances action. What stands in the way becomes the way.

Rights of the Learner

As a student in this class, you have the right:

1. to be confused,
2. to make a mistake and to revise your thinking,
3. to speak, listen, and be heard, and
4. to enjoy doing mathematics.

You may encounter many defeats, but you must not be defeated.

Commitment to the Learning Community

In our classroom, diversity and individual differences are respected, appreciated, and recognized as a source of strength. Students in this class are encouraged and expected to speak up and participate during class and to carefully and respectfully listen to each other. Every member of this class must show respect for every other member of this class. Any attitudes or actions that are destructive to the sense of community that we strive to create are not welcome and will not be tolerated. In summary: Be good to each other. I would appreciate private responses to the following question: Are there aspects of your identity that you would like me to attend to when forming groups, and if so, how?

Students are also expected to minimize distracting behaviors. In particular, every attempt should be made to arrive to class on time. If you must arrive late or leave early, please do not disrupt class. Please turn off the ringer on your cell phone. I do not have a strict policy on the use of laptops, tablets, and cell phones. You are expected to be paying attention and engaging in class discussions. If your cell phone, etc. is interfering with your ability (or that of another student) to do this, then put it away, or I will ask you to put it away.

An ounce of practice is worth more than tons of preaching.

Textbook

Our textbook for the semester is Introduction to Discrete Mathematics. Early versions of the book were originally written by NAU retired mathematics professor Dr. John Hagood (usuing the title MAT 226 Discrete Mathematics). Dr. Hagood was gracious enough to pass the source of the book along and has granted me permission to modify the content. Current iterations of the book are now my responsibility. The book is available as a freely-assessible PDF. You can find the book on the Course Materials page. Since I will be tweaking the book as we go, chapters will be released incrementally.

I will not be covering every detail of the textbook and the only way to achieve a sufficient understanding of the material is to be digesting the reading in a meaningful way. You should be seeking clarification about the content whenever necessary by asking questions. Here’s one of my favorite quotes about reading mathematics.

Don’t just read it; fight it! Ask your own questions, look for your own examples, discover your own proofs. Is the hypothesis necessary? Is the converse true? What happens in the classical special case? What about the degenerate cases? Where does the proof use the hypothesis?

Rules of the Game

Reviewing material from previous courses and looking up definitions and theorems you may have forgotten is fair game. Since mathematical reasoning, problem solving, and critical thinking skills are part of the learning outcomes of this course, all assignments should be prepared by the student. Developing strong competencies in this area will prepare you to be a lifelong learner and give you an edge in a competitive workplace. When it comes to completing assignments for this course, unless explicitly told otherwise, you should not look to resources outside the context of this course for help. That is, you should not be consulting the web (e.g., Chegg and Course Hero), generative artificial intelligence tools (e.g., ChatGPT), mathematics assistive technologies (e.g., Wolfram Alpha and Photomath), other texts, other faculty, or students outside of our course in an attempt to find solutions to the problems you are assigned. On the other hand, you may use each other, the textbook, me, and your own intuition. You are allowed and encouraged to work together on homework. Yet, each student is expected to turn in their own work.

In this course, we may use generative AI tools (such as ChatGPT) or AI mathematics assistive technologies (such as Wolfram Alpha) to examine the ways in which these kinds of tools may inform our exploration of mathematics content. You will be informed as to when and how these tools will be used, along with guidance for attribution if/as needed. Any use of generative AI tools outside of these parameters constitutes plagiarism and a violation of the University’s Academic Integrity Policy. Please read NAU’s Academic Integrity Policy.

The ultimate goal is for each individual student to learn and to be successful. So, if you feel you need additional resources or support, please come talk to me and we will come up with an appropriate plan of action.

The following are examples (not an exhaustive list) of behaviors that could constitute cheating and/or plagiarism. You should not be doing these things.

• Copying solutions or portions of solutions from another person
• Submitting solutions (in part or whole) by multiple students that identically match, especially in peculiar details
• Having another person complete your homework problems for you
• Using any applications or websites (e.g., Course Hero, Chegg, ChatGPT, WolframAlpha, PhotoMath) to complete problems or portions of problems (even if only used on one step that you are stuck on)
• Anything that takes solutions or portions of solutions and attempts to pass them off as your own ideas and work

The following are examples (not an exhaustive list) of behaviors that do not constitute cheating and/or plagiarism. You should be doing these things. 

• Having a conversation with a classmate about a homework problem to compare methods and discuss strategy
• Collaborating with a classmate on a homework problem (not copying)
• Asking questions about a homework problem on our course forum
• Responding to questions on our course forum in the form of feedback or guidance
• Asking the instructor for assistance or a hint

Tell me and I forget, teach me and I may remember, involve me and I learn.

Homework

You are allowed and encouraged to work together on homework. However, each student is expected to turn in their own work. In general, late homework will not be accepted. However, you are allowed to turn in up to three late homework assignments with no questions asked. Unless you have made arrangements in advance with me, homework turned in after class will be considered late. You can find the list of assignments on the homework page. I reserve the right to modify the homework assignments as I see necessary.

Your homework will always be graded for completion and some subset of the problems will be graded for correctness. Problems that are graded for completeness will be worth 1 point. Problems that are graded for correctness will either be worth 2 points or 4 points depending on the level of difficulty. Generally, quick computational problems will be worth 2 points while more substantial problems will be worth 4 points. Each 4-point problem is subject to the following rubric:

To compute your score on a given homework assignment, I will divide your total points by the total possible points to obtain a percent score. Each homework assignment has the same weight. Your overall homework grade will be worth 40% of your final grade.

I must not fear.
Fear is the mind-killer.
Fear is the little-death that brings total obliteration.
I will face my fear.
I will permit it to pass over me and through me.
And when it has gone past I will turn the inner eye to see its path.
Where the fear has gone there will be nothing.
Only I will remain.

Exams

There will be two midterm exams and a cumulative final exam. Exam 1 and Exam 2 are tentatively scheduled for Friday, October 6 (week 6) and Friday, November 17 (week 12), respectively. Each of Exam 1 and Exam 2 will be worth 20% of your overall grade. The final exam will be on Wednesday, December 13 at 10:00AM-12:00PM and is worth 20% of your overall grade. Make-up exams will only be given under extreme circumstances, as judged by me. In general, it will be best to communicate conflicts ahead of time.

I write one page of masterpiece to ninety-one pages of shit.

Attendance

Regular attendance is expected and is vital to success in this course, but you will not explicitly be graded on attendance. Students can find more information about NAU’s attendance policy on the Academic Policies page.

Extra Credit

The only thing I will award extra credit for is finding typos on course materials (e.g., textbook, exams, syllabus, webpage). This includes broken links on the webpage. However, it does not include the placement of commas and such. If you find a typo, I will add one percentage point to your next exam. You can earn at most two percentage points per exam. Extra credit points are only available to the first person to notify me of the error. They’re is a typo right here.

Basis for Evaluation

In summary, your final grade will be determined by your scores in the following categories.

It is not the critic who counts; not the man who points out how the strong man stumbles, or where the doer of deeds could have done them better. The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood; who strives valiantly; who errs, who comes short again and again, because there is no effort without error and shortcoming; but who does actually strive to do the deeds; who knows great enthusiasms, the great devotions; who spends himself in a worthy cause; who at the best knows in the end the triumph of high achievement, and who at the worst, if he fails, at least fails while daring greatly, so that his place shall never be with those cold and timid souls who neither know victory nor defeat.

Department and University Policies

You are responsible for knowing and following the Department of Mathematics and Statistics Policies (PDF) and other University policies listed here (PDF). More policies can be found in other university documents, especially the NAU Student Handbook (see appendices).

As per Department Policy, cell phones, MP3 players and portable electronic communication devices, including but not limited to smart phones, cameras and recording devices, must be turned off and inaccessible during in-class tests. Any violation of this policy will be treated as academic dishonesty.

Important Dates

Here are some important dates:

• September 4: Labor Day (no classes)
• November 10 Veteran’s Day (no classes)
• November 23-24: Thanksgiving (no classes)
• December 13: Final Exam (10:00AM-12:00PM)

Getting Help

There are many resources available to get help. First, you are allowed and encouraged to work together on homework. However, each student is expected to turn in their own work. You are strongly encouraged to ask questions in our Q&A Discussion board, as I (and hopefully other members of the class) will post comments there for all to benefit from. You are also encouraged to stop by during my office hours and you can always email me. I am always happy to help you. If my office hours don’t work for you, then we can probably find another time to meet. It is your responsibility to be aware of how well you understand the material. Don’t wait until it is too late if you need help. Ask questions!

Changes to the Syllabus

Any changes to this syllabus made during the term will be properly communicated to the class.

If you want to sharpen a sword, you have to remove a little metal.

University Policies

Academic Integrity: NAU expects every student to firmly adhere to a strong ethical code of academic integrity in all their scholarly pursuits. The primary attributes of academic integrity are honesty, trustworthiness, fairness, and responsibility. As a student, you are expected to submit original work while giving proper credit to other people’s ideas or contributions. Acting with academic integrity means completing your assignments independently while truthfully acknowledging all sources of information, or collaboration with others when appropriate. When you submit your work, you are implicitly declaring that the work is your own. Academic integrity is expected not only during formal coursework, but in all your relationships or interactions that are connected to the educational enterprise. All forms of academic deceit such as plagiarism, cheating, collusion, falsification or fabrication of results or records, permitting your work to be submitted by another, or inappropriately recycling your own work from one class to another, constitute academic misconduct that may result in serious disciplinary consequences. All students and faculty members are responsible for reporting suspected instances of academic misconduct. All students are encouraged to complete NAU’s online academic integrity workshop available in the E-Learning Center and should review the full Academic Integrity policy available here.

Copyright Infringement: All lectures and course materials, including but not limited to exams, quizzes, study outlines, and similar materials are protected by copyright. These materials may not be shared, uploaded, distributed, reproduced, or publicly displayed without the express written permission of NAU. Sharing materials on websites such as Course Hero, Chegg, or related websites is considered copyright infringement subject to United States Copyright Law and a violation of NAU Student Code of Conduct. For additional information on ABOR policies relating to course materials, please refer to ABOR Policy 6-908 A(2)(5).

Course Time Commitment: Pursuant to Arizona Board of Regents guidance (ABOR Policy 2-224, Academic Credit), each unit of credit requires a minimum of 45 hours of work by students, including but not limited to, class time, preparation, homework, and studying. For example, for a 3-credit course a student should expect to work at least 8.5 hours each week in a 16-week session and a minimum of 33 hours per week for a 3-credit course in a 4-week session.

Disruptive Behavior: Membership in NAU’s academic community entails a special obligation to maintain class environments that are conductive to learning, whether instruction is taking place in the classroom, a laboratory or clinical setting, during course-related fieldwork, or online. Students have the obligation to engage in the educational process in a manner that does not interfere with normal class activities or violate the rights of others. Instructors have the authority and responsibility to address disruptive behavior that interferes with student learning, which can include the involuntary withdrawal of a student from a course with a grade of “W”. For additional information, see NAU’s Disruptive Behavior in an Instructional Setting policy located here.

Nondiscrimination and Anti-harassment: NAU prohibits discrimination and harassment based on sex, gender, gender identity, race, color, age, national origin, religion, sexual orientation, disability, veteran status and genetic information. Certain consensual amorous or sexual relationships between faculty and students are also prohibited as set forth in the Consensual Romantic and Sexual Relationships policy. The Equity and Access Office (EAO) responds to complaints regarding discrimination and harassment that fall under NAU’s Nondiscrimination and Anti- Harassment policy. EAO also assists with religious accommodations. For additional information about nondiscrimination or anti-harassment or to file a complaint, contact EAO located in Old Main (building 10), Room 113, PO Box 4083, Flagstaff, AZ 86011, or by phone at 928-523-3312 (TTY: 928-523-1006), fax at 928-523-9977, email at equityandaccess@nau.edu, or visit the EAO website located here.

Title IX: Title IX of the Education Amendments of 1972, as amended, protects individuals from discrimination based on sex in any educational program or activity operated by recipients of federal financial assistance. In accordance with Title IX, Northern Arizona University prohibits discrimination based on sex or gender in all its programs or activities. Sex discrimination includes sexual harassment, sexual assault, relationship violence, and stalking. NAU does not discriminate on the basis of sex in the education programs or activities that it operates, including in admission and employment. NAU is committed to providing an environment free from discrimination based on sex or gender and provides a number of supportive measures that assist students, faculty, and staff.

One may direct inquiries concerning the application of Title IX to either or both the Title IX Coordinator or the U.S. Department of Education, Assistant Secretary, Office of Civil Rights. You may contact the Title IX Coordinator in the Office for the Resolution of Sexual Misconduct by phone at 928-523-5434, by fax at 928-523-0640, or by email at titleix@nau.edu. In furtherance of its Title IX obligations, NAU promptly will investigate or equitably resolve all reports of sex or gender-based discrimination, harassment, or sexual misconduct and will eliminate any hostile environment as defined by law. The Office for the Resolution of Sexual Misconduct (ORSM): Title IX Institutional Compliance, Prevention & Response addresses matters that fall under the university’s Sexual Misconduct policy. Additional important information and related resources, including how to request immediate help or confidential support following an act of sexual violence, is available here.

Accessibility: Professional disability specialists are available at Disability Resources to facilitate a range of academic support services and accommodations for students with disabilities. If you have a documented disability, you can request assistance by contacting Disability Resources at 928-523-8773 (voice), ,928-523-8747 (fax), or dr@nau.edu (e-mail). Once eligibility has been determined, students register with Disability Resources every semester to activate their approved accommodations. Although a student may request an accommodation at any time, it is best to initiate the application process at least four weeks before a student wishes to receive an accommodation. Students may begin the accommodation process by submitting a self-identification form online here or by contacting Disability Resources. The Director of Disability Resources, Jamie Axelrod, serves as NAU’s Americans with Disabilities Act Coordinator and Section 504 Compliance Officer. He can be reached at jamie.axelrod@nau.edu.

Responsible Conduct of Research: Students who engage in research at NAU must receive appropriate Responsible Conduct of Research (RCR) training. This instruction is designed to help ensure proper awareness and application of well-established professional norms and ethical principles related to the performance of all scientific research activities. More information regarding RCR training is available here.

Misconduct in Research: As noted, NAU expects every student to firmly adhere to a strong code of academic integrity in all their scholarly pursuits. This includes avoiding fabrication, falsification, or plagiarism when conducting research or reporting research results. Engaging in research misconduct may result in serious disciplinary consequences. Students must also report any suspected or actual instances of research misconduct of which they become aware. Allegations of research misconduct should be reported to your instructor or the University’s Research Integrity Officer, Dr. David Faguy, who can be reached at david.faguy@nau.edu or 928-523-6117. More information about misconduct in research is available here.

Sensitive Course Materials: University education aims to expand student understanding and awareness. Thus, it necessarily involves engagement with a wide range of information, ideas, and creative representations. In their college studies, students can expect to encounter and to critically appraise materials that may differ from and perhaps challenge familiar understandings, ideas, and beliefs. Students are encouraged to discuss these matters with faculty.