Math 455

Introduction to Discrete Structures

Spring 2013

** Course News:**

Monitor this space weekly for important course news, such as:

The First Midterm will be administered on Tuesday February 12, in class. Please arrive on time. A sample exam is now posted.

The Second Midterm will be administered on Thursday April 11, in class. Please arrive on time. A sample exam is now posted.

I will hold extra office hours on Wednesday April 10, from 9:30-11:30 as well at 1:00, as usual. Alden will be in 1623C 1:30-3:30 for extra office hours as well.

**Meeting times: ** Tuesday and Thursday, 9:30-10:45, in Hasbrouck Lab
Addition 113.

**Instructor: **
Dr. Farshid Hajir

**Office: **Lederle 1623C

**Phone: **545-6025

**Email: ** hajir atsymbol math.umass.edu

**Office Hours**:
Current office hours are Tuesday 11-12 , and Wednesday 1-2, subject to change.
You are always welcome to set up an appointment by sending me an
e-mail or calling me on the phone.

**Teaching Assistant:** This class has a TA, Alden Gassert, whose office hours are Monday and Friday 8:30 am to 10:00 am, in Lederle 1423D. His email address is gassert atsymbol math.umass.edu.

**Prerequisites:** Calculus (MATH 131, 132, 233), Linear Algebra
(MATH 235), and Math 300 or COMPSCI 250. For students who have not
taken Math 300 or COMPSCI 250, the instructor may permit students
with su cient experience in reading and writing mathematical arguments
to enroll.

**Course Description:** This is a rigorous introduction to some topics
in mathematics that underlie areas in computer science and computer
engineering, including: graphs and trees, spanning trees, colorings
and matchings; the pigeonhole principle, induction and recursion,
generating functions, and (if time permits) combinatorial
geometry. The course integrates learning mathematical theories with
applications to concrete problems from other disciplines using
discrete modeling techniques. Student groups will be formed to
investigate a modeling problem and each group will report
its findings to the class in a final presentation.

**Course objectives:** 1. To learn and understand how to manipulate the
basic objects of discrete mathematics, as well as how to prove basic
facts and deduce new ones from axioms and standard theorems, using
calculus and linear algebra techniques. 2. To learn a number of
situations in real world applications where discrete methods provide a
powerful tool to derive answers to complex problems quickly and e
ciently. 3. To model the real world problems of (2) using discrete
systems and then apply methods of (1) to solve those problems. 4. To
learn to use critical thinking, collaborative work, and knowledge
accrued in previous General Education and mathematics/statistics
classes to learn about discrete systems and their applications in an
integrated experience.

** Integrative Experience Designation:** This course satises the
Integrative Experience General Education Requirement for Mathematics
and Statistics majors. For information about this requirement, please
read all information contained in
http://www.umass.edu/gened/teachingAdvising/integrativeExperience/ie.html
There are three purposes for IE courses. We describe each in turn.

*1st IE Criterion* Students [will] reflect on and integrate their
learning and experience from the broad exposure in their General
Education courses and the focus in their major." In this course we
develop mathematical tools to solve concrete problems coming from com-
puter engineering, computer science, economics and social
sciences. Many of these problems, such as the four-coloring problem,
have a long and distinguished history and many students have
encountered them in previous courses. Other problems, such as graph
matching and the construction of minimal spanning trees, have
applications to diverse elds ranging from computer networks and the
assignment of medical students for residencies at hospitals. Thus,
students will need to draw not only on their mathematics coursework,
but also on the knowl- edge they have accrued from other GenEd
curriculum they have experienced in their rst two years of
college. After seeing how a common set of mathematical tools can be
used to solve concrete problems from across dierent elds, students can
better appreciate the beauty as well as the power of advanced
mathematics.

*2nd IE Criterion* "Students will practice General Education
learning objectives at a more advanced level." Real-world
applications from social sciences to engineering often lead to very
large data sets, and it is a major challenge to organize these data,
to discover hidden patterns, and to sieve out duplicate
information. Relations between dierent data points can often be
represented in terms of graphs, and graph theory in turn provides a
large set of well-tested algorithms for extracting additional
information about the original data sets. Enumerative combinatorics
provides a powerful set of tools for explicitly counting of data
sets. By ap- plying these tools to solve concrete problems from
diverse elds, students get to know the algorithmic aspects of these
abstract mathematical concepts and gain practical experience about the
strength and limitations of dierent approaches. As with their previous
math classes leading up to upper division classes, students will
engage in critical thinking (de- ductive as well as inductive
reasoning, using logic as well as experiments) and quantitative
reasoning throughout the course. But they will also need to draw on
experiences from other GenEd courses in applying the mathematics they
learn in this class to solving real-world problems described in item
4. The general theme of the course is that of discrete models, as
opposed to continuous ones. Formulation, analysis and interpretation
of a mathematical model are challenging tasks, which invariably
require innovative and critical thinking, both quantitative and
qualitative. Modeling is the key concept that connects mathematics to
other disciplines. The course also aims to provide training for
students in working together in small groups and eectively
communicating their ndings to their peers. Thus, Math 455
is ideally suited to meeting all four goals of
content, critical thinking, communication and connections of the
General Education program.

*3rd IE Criterion* "A shared learning experience for applying
students' prior learning to new situations, challenging questions, and
real-world problems." While much of the course consists of lectures
and homework assignments, a substantial fraction of the course grade
is based on a modeling project carried out in groups; this is a
substantial change from standard upper division math/stat
requirements. Each group, which typically consists of three students,
explores a discrete modeling topic of the groups choice, with input
from the faculty instructor. Each project is an interdisciplinary
investigation that combines mathematical techniques with some scientic
subject matter in which the students in the group have some
background. This type of work goes well beyond the usual procedure in
mathematics classes, where problems are already abstracted from their
scientic context and the emphasis is mainly on developing methods of
solution to those traditional abstractions. The group investigation
involves collaboration between group members as well as presentation
of the nal results to the class as a whole at the end of the
semester. In addition, a written version of the group report is
required from each student individually, and these must be done by
each student independently. A graduate student will attend all
lectures and have extensive o ce hours for helping all groups with the
nal project, both in carrying out the work, and in creating a
presentation which clearly communicates the problems that were
investigated, what methodology was used, etc. The final projects will
be presented either in class or in the form of a poster session at the
end of the semester (or both), at the discretion of the instructor.

**Text: **
*Combinatorics and Graph Theory*, Author: Harris, Hirst, &
Mossinghof, Publisher: Springer, Edition: 2nd, Year Published: 2008,
Price: 43.99 USD

**Moodle Bulletin Board:** A virtual M455 discussion *may* be set up
via the Campus Moodle resource. Stay tuned for details. Please use
this service responsibly. (Assuming I actually set it up, I will
monitor it semi-regularly, but if you want to direct a question
specifically at me, the best way to reach me is during office hours or
by e-mail.

**Homework:** Homework will be posted on The
Homework Page and collected every Thursday at the beginning of
lecture. Late homework will not be accepted and the lowest homework
grade will be dropped. **Be sure to read and follow the homework
rules.**

**Attendance: ** Attendance is required during lectures.
I consider
attendance AND participation important ingredients for your success in
the course. Frequent absences will be reflected in your
grade.

**Final Project:** Two weeks into the course, you will receive a list
of projects. You can ask the instructor and TA questions for more
details about these projects and should sign up for one of the three
slots for a project of your choice; these are
rst-come-rst-serve. There is a small amount of exibility, in that some
groups can have size two or size four, but no student may work on a
project by himself or herself. Part of the point of the project is to
communicate and collaborate with others. However, each student will
turn in an individual document and take part in presenting the
work. Before the course reaches the midterm point, you will be
assigned a project if you have not already decided on one. The TA will
have extensive office hours for meeting with students and getting you
started on investigating your project. All of the projects require
discrete modeling of one kind or another. Possible topics will be
drawn from:

-Social network analysis, which examines the structure of relationships between social entities: diffusion of rumors, spread of diseases, social mechanisms for setting prices.

- Combinatorial optimization and queuing theory/scheduling theory: how to organize interdependent tasks for maximizing prot or minimizing time to completion.

- Network optimization: for instance, setup of telecommunications networks to maintain quality of service during outages Routing, such as determining the routes of buses so that as few buses are needed as possible.

- Coding theory is the science of error-free and efficient transmission of data. It is used in compact discs, cellular phones, satellite transmissions etc.

**Quizzes:** I might give an occasional 10-15 minute quiz in class.
Each of these will count as one homework assignment. ** There will be
no make-up quizzes**.

**Exams:** There will be two midterms and one final project.
The midterms will take place during regular class time on
**Tuesday February 12 and Thursday April 11.**.
** Make-up Exam Policy:** If you have a legitimate (e.g. multiple
exams at the same exact time, medical problems, emergency absences,
religious observances) scheduling conflict with any of the exams, it
is your responsibility to notify me of the conflict as soon as you
become aware of it. The final decision regarding allowing a make-up
exam is mine, subject to University regulations, of course. Please
note that previously arranged travel plans are **not** a valid
reason to be given a make-up exam.

** Computers:** Discrete mathematics is an inherently computational
subject and we will undoubtedly have some use for machine calculations
over the course of the semester, though this will not be a required
aspect of th course necessarily. When the time comes, you will
probably be able to get away with Maple or Mathematica if you're used
to those packages. In fact, however, for many purposes there is a far
better option out there: Pari/GP. Pari/GP has two main advantages: 1)
It does fast arithmetic to arbitrary precision, and 2) it is available
at a very reasonable price: free. We'll deal with this when the time
comes, but if you're curious, everything you ever wanted to know about
Pari/GP can be learned at
The PARI homepage.

**Extra Credit:** Some extra credit problems will occasionally be
included in the homework assignments, or given during class. The number of points for each
problem will vary, as will the difficulty of the problem. The student
with the most points at the end of the semester wins a fabulous prize.
You may hand in Extra Credit solutions at any time throughout the
term, until the last class meeting.

**Grading:**

homework, quizzes, participation - 30%

2 midterms - 20% each

Group Project - 30%

A |
≥ 93% |

A- |
≥ 90% and < 93% |

B+ |
≥ 86% and < 90% |

B |
≥ 82% and < 86% |

B- |
≥ 78% and < 82% |

C+ |
≥74% and < 78% |

C |
≥ 70% and < 74% |

C- |
≥65% and < 70% |

D |
≥ 60% and < 65% |

F |
< 60% |