Math 232: Elementary Discrete Mathematics II, Syllabus, Fall
2023
Instructor: Prof. Boris
Botvinnik :
e-mail
botvinn[at]uoregon.edu
Lectures:
154 Straub Hall: Monday, Tuesday, Wednesday, and Friday at 1:00--1:50 pm,
Office hours: Tuesday, Wednesday 4--5 pm, or by
appointment
Textbook:
Discrete Mathematics and Applications. Kenneth H. Rosen, Either the
7th or 8th edition.
You are expected to read the textbook carefully, and
will be responsible for all the material in those sections that are
covered in class. The text contains solutions or hints for odd
numbered problems. The homework assignments will consist mostly of
even numbered problems, although I strongly recommend that you try
some of the odd numbered problems on your own. The accompanying study
guide contains a great deal of additional information that you should
find helpful.
Prerequisites:
Math 231, or instructor's consent.
Course Content:
This course continues the study of discrete mathematics where Math 231
left off. The course has a few main topics, mathematical induction
(revisited) Recurrence relations and generating functions, graphs and
trees, partial orderes and equivalence relations.
- Week 1-2: MATHEMATICAL
INDUCTION (revisited). Sections 5.1, 5.2. The basic template for an
induction proof, lots of examples proving identities seen in Math 231
such as summation formulae, inequalities and more involving the idea
of divisibilty. The binomial theorem revisited, and proved now by
inducion using the recursive definition of the binomial
coefficients. Proof of the Fundamental Theorem of Arithmetic from
Section 4.3.
- Week 2-3: RECURRENCE RELATIONS
AND GENERATING FUNCTIONS. Sections 8.1, 8.2, 8.4. Solving
homogeneous linear recurrence relations. This could be introduced
quickly with examples, and then done again using generating functions
and partial fractions techniques (although this is challenging since
it relies on algebra skills). Lots of examples and proofs by induction
along the way.
- Weeks 4/5/6: GRAPH
THEORY. Parts of sections 10.1, 10.2, 10.3, 10.5 and 10.7. The
definitions of a graph, multigraph, digraph, relevant examples of
graphs. Neighbors, degrees, special graphs including Kn
and Km,n$. The idea of graph isomorphism. Euler and
Hamilton circuits. Euler's theorem. Brief discussion of the famous
Four Color Theorem.
- Weeks 6/7: TREES.
Parts of sections 11.1, 11.2, 11.3.
Basic terminology of trees and forests,
formulae for their number of edges.
Then ordered rooted trees and some of their applications, ending with
the connection between binary rooted trees and Catalan numbers.
- Weeks 8/9: ALGORITHMS INVOLVING
GRAPHS. Dijkstra's shortest path algorithm from section
10.7. Discussion of the traveling salesman problem. One of Prim's or
Kruskal's algorithm for finding minimal spanning trees from section
11.5.
- Week 10: REVIEW.
Homework
Homework is due in class on Wednesdays, beginning October 3.
Late homework will not be accepted. There will be 9
homework assignments, the last of which will not be
graded. Your lowest homework score will be dropped. You may
collaborate with other class members on your homework, although
you must each write up your solutions independently and in your
own words. To avoid falling behind, you should do the reading
and homework as the material is presented in class, rather than
leaving it all until the last minute.
The homework should be
uploaded to Canvas by the deadline.
Graded homework will be returned electronically, using
Canvas.
Exams
here will be two in-class midterm exams and a final
exam. No cell phones and computersm are alloowed. You may have
one 3x5 index card with everything you wish written there.
First Midterm Exam: 1:00-1:50 pm, Friday October 20, 2023
Second Midterm Exam: 1:00-1:50 pm, Friday November 17, 2023
Final Exam: 2:45-4:45 pm, Monday, December 4, 2023
Important: There will be no makeup for these exams, except
for documented medical Emergencies.
Grading:
| Homework: | 20% |
| First Midterm Exam: | 20% |
| Second Midterm Exam: | 20% |
| Final Exam: | 40% |
Classroom behavior
Students are expected to behave
respectfully toward each other and toward the instructor during class
time. This includes refraining from using cell phones during
lectures.
Academic conduct
The code of student conduct and community
standards is
here. In this course, it is appropriate to give and obtain
help on homeworks so long as the work you are submitting is your own
and you understand it. It is not appropriate to obtain help on exams
or to give help to other students with their exams. Cheating hurts the
cheater and all the other honest students in the system, basically:
PLEASE DO NOT CHEAT!
Learning environment and AEC accommodations
The University of
Oregon strives for inclusive learning environments. Please notify me
if the instruction or design of this course results in
disability-related barriers to your participation. You are also
encouraged to contact the Accessible Education Center at
her.
Accommodations for religious observances
The university makes
reasonable accommodations, upon request, for students who are unable
to attend a class for religious obligations or observance reasons, in
accordance with the university discrimination policy which says ``Any
student who, because of religious beliefs, is unable to attend classes
on a particular day shall be excused from attendance requirements and
from any examination or other assignment on that day. The student
shall make up the examination or other assignment missed because of
the absence." To request accommodations for this course for religious
observance, visit the Office of
the Registrar's website
and complete and submit to the instructor the ``Student Religious
Accommodation Request" form prior to the end of the second week of the
term.
Basic needs
Any student who has difficulty affording
groceries or accessing sufficient food to eat every day, or who lacks
a safe and stable place to live and believes this may affect their
performance in the course is urged to contact the Dean of Students
Office (346-3216, 164 Oregon Hall) for
support. This UO
webpage includes resources for food, housing, healthcare,
childcare, transportation, technology, finances, and legal support.
Inclement weather
It is generally expected that class will
meet unless the University is officially closed for inclement
weather. If it becomes necessary to cancel class while the University
remains open, this will be announced on Canvas and by email.
Mental health and wellness
Life at college can be very
complicated. Students often feel overwhelmed or stressed, experience
anxiety or depression, struggle with relationships, or just need help
navigating challenges in their life. If you're facing such challenges,
you don't need to handle them on your own--there's help and support on
campus. Getting help is a courageous thing to do-for yourself and
those you care about. University Health Services help students cope
with difficult emotions and life stressors. If you need general
resources on coping with stress or want to talk with another student
who has been in the same place as you, visit the Duck Nest (located in
the EMU on the ground floor) and get help from one of the specially
trained Peer Wellness Advocates. Find out more
here.
Last modified September 12, 2023 by
Boris Botvinnik.