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%