# Discrete Math

## Fall 2018

CRN 17850
TuTh 1:30-2:50, LART 103; 3 credit hours

### Other resources

• This syllabus in pdf
• Tower of Hanoi
• Planarity the game where you drag vertices around to draw an isomorphic graph that has no crossings (representing the graph as a planar graph).
• map of the United States (for graph coloring)
• Rush Hour game (example of depth-first search maze)
• Collection of blog articles by Keith Devlin about why multiplication is not repeated addition: (The second and third articles get more technical, and the fourth one includes references to several other blog threads discussing the ideas.)
• blog post I wrote about equivalence relations: "One Reason Fractions (and Many Other Topics) Are Hard: Equivalence Relations Up and Down the Mathematics Curriculum".
• blog post about the right way to think about inverse functions.

## Syllabus

### Instructor: Dr. Art Duval

Please feel free to come by my office any time during scheduled office hours. You are welcome to visit at other times, but in that case you might want to make an appointment, just to make sure that I will be there then. You can make an appointment simply by talking to me before or after class, by calling me at my office or at home, or by sending e-mail.

You may also ask any questions directly via phone or e-mail. If I'm not in when you call, please leave a message on the voice-mail or answering machine with your name, number, and a good time for me to call you back. I will try to respond to your phone or e-mail message as soon as possible.

### Prerequisites:

Calculus I (Math 1411). This is entirely a mathematical maturity requirement, as we will use no calculus in this course.

### Course Objectives:

Upon successful completion of the course, you will know and be able to use the basic algebra of sets and of logic. You will be able to identify and use common classes of relations. You will know basic properties of arbitrary functions. You will be able to solve counting problems involving combinations and permutations, including counting problems with restrictions. You will know the basic definitions and theorems of graph theory, and be able to apply them to specific graphs. You will know the basic algorithms for traversing trees, and be able to apply them to specific trees.

Note that this class will probably be quite different from other math classes you have taken, in at least two important ways. First, in contrast to calculus and related courses, the objects under consideration are (as the course title suggests) discrete, not continuous. This has the advantage that you can often explicitly list all the pieces (try listing all the function values of a continuous function!), but the disadvantage of not having continuity to "tie" things together nicely. Second, although there is still a lot of problem-solving, the problems and their answers have a very different flavor: the problems are not equations to be solved, and the answers often aren't even numbers. We also may spend more time explaining why a particular solution works than in finding the solution.

### Textbook:

Discrete Mathematics, 5th ed., Dossey, et. al., Chs. 2, 4, 5, 8, Appendix A. We will skip some sections, as announced in class. The textbook is required at all class meetings.

Required Reading: Read each section that we cover in class, both before and after class. Skim the section before class, even if you don't understand it fully, to have some idea of what we'll be doing in class. Read it more carefully after class to clarify and fill in details you missed in class.

Warning: Sometimes, we will not "cover" all the material from a section, but instead focus on a particular aspect of the section. In such cases, I will point out in class (and at this website) which other parts of the section I expect you to read on your own.

#### Quizzes (15%):

Suggested homework problems will be assigned most class days and will generally be discussed at the next class. There will be approximately weekly quizzes, with problems taken from the homework. Quizzes are closed-book, closed-notes. Missed quizzes cannot be made up, but your two lowest quiz scores will be dropped.

It is very important that you do your homework before it is discussed in class. You will only learn the material by doing it yourself, not by watching others do it for you.

#### Projects (10%):

There will be 3-4 projects throughout the semester, where you consider slightly more in-depth problems, and write up their solutions more carefully. As part of a pilot project, all the projects will be drawn from real applications in biology (though you will not need to know any biology in order to complete them), where math and computer science are playing an increasing role.

#### Exams (15% each):

There will be three in-class exams on the following days:
• Ch. 2: Thu. 4 Oct.
• Ch. 8: Thu. 25 Oct.
• Chs. 4,5: Tue. 20 Nov.

#### Final (30%)

comprehensive (including Appendix A)
The final will be on
Thu. 13 Dec., 1:00-3:45 p.m.
Makeup exams can be given only in extraordinary and unavoidable circumstances, and with advance notice.

Once you begin an exam, you will not be allowed to leave the classroom until you have finished the exam. There will be no bathroom breaks. If you have a medical reason for needing more frequent bathroom breaks, please provide documentation in advance.

### POLICIES:

It is UTEP's policy, and mine, for all suspected cases or acts of alleged scholastic dishonesty to be referred to the Office of Student Conduct and Conflict Resolution for investigation and appropriate disposition. See Section II.1.2.2.1 of the Handbook of Operating Procedures.

#### Attendance:

I strongly encourage you to attend every class, though there is no particular grade penalty for absences. You are responsible to find out any assignment that must be made up if you are absent. My goal is for class meetings and activities to complement, rather than echo, the textbook, and thus for every class to be worth attending.

#### Drop date:

The deadline for student-initiated drops with a W is Friday, November 2. After this date, you will not be able to drop the class (as per the Dean's office). Furthermore, a grade of incomplete is only for extraordinary circumstances, such as a missed exam.

I hope everyone will complete the course successfully, but if you are having doubts about your progress, I will be happy to discuss your standing in the course to help you decide whether or not to drop. You are only allowed three enrollments in this course, and students enrolled after Fall 2007 are only allowed six withdrawals in their entire academic career, so please exercise the drop option judiciously.

#### Courtesy:

We all have to show courtesy to each other, and the class as a whole, during class time. Please arrive to class on time (or let me know when you have to be late, and why); do not engage in side conversations when one person (me, or another student) is talking to the whole class; turn off your cell phone (or, for emergencies, at least set it to not ring out loud), and do not engage in phone, email, or text conversations during class.

#### Disabilities:

If you have, or suspect you have, a disability and need an accommodation, you should contact the Center for Accommodations and Support Services (CASS) at 747-5148, cass@utep.edu, or Union East room 106. You are responsible for presenting to me any CASS accommodation letters and instructions.

#### Exceptional circumstances:

If you anticipate the possibility of missing large portions of class time, due to exceptional circumstances such as military service and/or training, or childbirth, please let me know as soon as possible.