# Math 232: Discrete Mathematics

## Spring 2009

 Instructor: Martha Wallace Find me in SC 256 Phone me at x3408 Email me Text: Goodaire and Parmenter, Discrete Mathematics with Graph Theory (3rd Edition) Tools: A willingness to tackle nonroutine problems

What is Discrete Mathematics?

Discrete mathematics is a branch of mathematics that models the world of information processing and social decision-making. Discrete (non-continuous) mathematics has become increasingly important as more situations are investigated, represented, and solved using computers. Examples of questions that can be studied via discrete mathematics are:
• What is the quickest way to sort a list of names alphabetically?
• Which way of connecting a number of sites into a telephone network requires the least amount of cable?
• Which version of a lottery gives the best odds?
• What is the best way for a robot to pick up items stored in an automated warehouse?
• How does a CD player interpret the codes on a CD correctly even if the CD is scratched?
• How can ice cream stands be placed at various street corners in a town so that at any corner there is a stand which is at most one block away?
• How can representatives be apportioned fairly among the states using current census information?
Discrete mathematics typically explores three central questions in solving problems:
1. Existence: Is there a solution?
2. Algorithmic solutions: Can we construct an efficient algorithm to solve the problem?
3. Optimization: Which solution is best?

We will use problems, both realistic and silly, and games we will learn about mathematical topics such as:
1. Graph theory: using vertex-edge diagrams to model and investigate relationships among a finite number of elements;
2. Combinatorics: systematic counting procedures;
3. Recursion: describing and investigating sequential change;
4. Algorithm development and analysis;
5. Logic and proof

Through problemse emphasis will be on modeling, problem solving, and learning to read and write mathematical proofs. Future teachers will look at the role of discrete mathematics in high school mathematics.

Class Requirements

Homework Policy:

With few exceptions, you will have two assignments due each day:

A reading covering the material to be discussed during that class period. For each reading assignment, you are to read the section carefully, identifying the main concepts and questions you may have. Your reading assignment is a very important part of your work in this class, and you will have Moodle quizzes over many of the reading assignments. They do count toward your grade.

A writing assignment based on the material discussed in the previous class as well as often some preview problems from the next sections and possibly some review problems from previous sections. This assignment should be done in draft form by the next class day to allow for a small amount of explication in class. The final form of each assignment is due on the second class day after it is assigned. You are encouraged to work with other class members to do your homework assignments. The writing assignments will count toward your final grade in the course.

No late homework will be accepted, but 3 writing homework scores and 3 Moodle quiz scores will be dropped.

Computer Work:

During the semester, we will have a few computer labs and computer components in other assignments. You will use the computer algebra system Maple 12 for these assignements. This program is available on the computers in SC 175. Some of the tests may have a take-home portion on which you will be expected to use Maple.

Presentations:

You will work in pairs for this part of the class.  Each pair of students is responsible for making a 30 minute presentation to the class during the last half of the class.  Your presentation should not be at the ``theorem-proof'' level of mathematics.  Instead, it should show some application of discrete mathematics, to another discipline or to some interesting problems.  Your presentation should involve some hands-on engagement
by the rest of the class.  Here are some possibilities.  Other ideas will be provided after we get into the class material.

• Matching using graphs
• You could design a roommate match procedure, a dating service or some other situation  matching one person with another.
• Network Flows
• This topic leads to solutions to problems involving getting traffic out of a city during rush hours, or getting a large group of people from the ground floor to a penthouse with a limited number of elevators.
• Voting theory
• An important topic, especially since we just finished a presidential election year.
• Codes and cryptography
• Create and decipher secret codes.  Include public key codes, which are becoming even more important with increasing computer security issues.
• Games or magic tricks using discrete mathematical structures or topics.
• Collection of problems around a topic of your choosing.  Examples  include:
• Application of graph theory to management decision making.
• Application of graph theory or combinatorics to taking a trip, visiting
a museum, or other situation.
• Creative story using discrete mathematics topics.
• Discrete mathematics in middle or high school.
• Most appropriate for students considering high school teaching.
• Other?  Talk to me!

 How does your work contribute to your final grade? What grade will you get in this class? Components: Points Possible: Total Points Earned as % of Possible Minimum Grade You Will Earn Homework, Labs and Moodle Quizzes 100-150 points 90% A- Presentation 50 points 80% B- 2 Tests 200 points 65% C- Final 150 points Total Possible 500-550 points

Hints for Success:

Reading the material carefully before it is covered in class is a big step toward success in any math course. Successful students typically outline or otherwise summarize the material briefly in their notebook and highlight questions to bring to class. A great way to become familiar with concepts and techniques is to work each of the examples. (This means work on paper -- don't just read and nod.)

Be sure to work lots of problems -- they are fun!

Make sure that you begin the assigned homework as soon as possible after it is assigned and bring a nearly complete homework paper to the following class so that you can get the most out of any homework discussion in class. Be sure to make connections in your mind between discrete concepts and the other mathematics that you have studied.

Disability Policy:

If you have a documented disability that will impact your work in this class, please contact me to discuss your needs. Additionally, you will need to register with Student Disability Services located at the Academic Support Center. All such discussions will be confident

Disclaimer