University of Massachusetts Amherst
Department of Mathematics and Statistics

Math 455.1—Introduction to Discrete Structures (# 15236)—Spring 2009

    Meets MWF 1:25–2:15 p.m. in LGRT 219
    Exceptions: Wed., Feb. 4  & Fri., Feb. 6 and exams meet in ELAB 307

INSTRUCTOR

    Prof. Murray Eisenberg
    Lederle Tower 1335 G
    Office hours: MWF 2:30–3:30 + other times (ask!)
    Phone:  5-2859
    e-mail:   murray@math.umass.edu
    Mailbox: Lederle Tower 1623D (do not leave papers at my office!)

WEB SITE

     http://www.math.umass.edu/~murray/Math_455_Eisenberg
    (use upper-case M, and E as shown; include the underscores _ )

REQUIRED TEXT

  • L. Lovász, J. Pelikán, and Vesztergombi,  Discrete Mathematics: Elementary and Beyond, Springer, 2003, ISBN-10: 0387955852; paperbound, about $33 used, $45 new.

SOFTWARE

  1. Mathematica Version 6.0.3 or later—preferably Version 7. This numerics-symbolics-graphics package is available on the computers at all OIT public labs, including the cluster of OIT-managed computers in the DuBois Library Learning Commons. Mathematica might be installed elsewhere, e.g., in some Engineering labs. You are not required to buy it.

    2. Mathematica includes complete on-line documentation. I will help you learn how to use Mathematica.

    If you wish to run Mathematica on your own computer , you may buy Mathematica for Students directly from the publisher, Wolfram Research. Mathematica for Students is a fully functional version of the professional product. (See the FAQ about Mathematica for Students.) There are three licensing options for Mathematica for Students:

    • Semester Edition, good for 6 months. $44.95.
    • Annual Edition, good for 12 months. $69.95.
    • Standard Edition, good for as long as you remain a student. $139.95. (This may also be available in a CD package at Campus Center Bookstore Bookstore; just be sure it’s version 6.)
       
  2. Course-specific Mathematica notebooks—live electronic documents that you download. Except for minor cosmetic differences in window interface, these notebooks work identically on all operating systems.
     
  3. Adobe Acrobat Reader, to read homework set assignments and some notes.

SUPPLIES

    Access to your UMass UDrive (or other web-based file storage) or a USB flash drive.

PREREQUISITES

  • Mathematical:  Math 132 (end of single-variable calculus); Math 235 (linear algebra) or else CompSci 250 and a rudimentary knowledge of matrices.
  • Computer:  previous experience with Mathematica is not assumed

REQUIREMENTS

  • take the final exam at the officially scheduled time
  • take the two mid-semester exams during regular class meetings
  • hand in the (roughly weekly) homework sets, which will include computer work

COURSE AIMS

  1. Learn computational skills of counting and other areas of discrete mathematics.
  2. Understand fundamental concepts about integers, graphs, and other discrete structures.
  3. Improve ability to read mathematical exposition.
  4. Develop skills of reasoning about discrete structures, and of expressing that reasoning in writing.
  5. Become acquainted with various mathematical ideas that are useful in computer science, computer engineering, further mathematical study, and elsewhere.
  6. Engage in some (guided) mathematical exploration.
  7. Learn enough about Mathematica to use it effectively in dealing with discrete mathematics and to be able to learn more about Mathematica.

Mathematica is used for three purposes: First, as a tool for doing numeric and symbolic calculations and forming graphical representations. Second, as a means for experimenting. Third, as an aid in understanding key ideas and methods.

CONTENT

The principal source for the topics below is the textbook.  Not everything of importance will be covered in lecture: you learn some things by reading textbook assignments, reading on-line notes, working through Mathematica notebooks I provide, doing Mathematica work, and solving homework problems.

  • Counting elements of finite sets (“combinatorics”)
  • Recursive definitions and proof by induction
  • Elementary number theory (about integers) and application to public-key cryptography
  • Graphs (in the sense of networks of relationships)
  • Additional topics as time may allow

GRADING

Scores below are on a 100-point scale.  Let

    F = final exam score
    X = average of mid-semester exam scores
    H = average of best 80% of homework set scores

Then your course score S is the weighted average defined, in Mathematica notation, by:

    S = Apply[Plus,{0.25,0.50,0.25}* {F,X,H}]

Course scores 86–100 earn a course grade of A; 76–85 at least B; 60–75 at least C; 50–59 at least D.  Intermediate scores may earn course grades A–, B+, etc.

THE SECRET TO SUCCEEDING IN MATH 455

  • Read assigned material—before the classes where it is discussed.
  • Keep up with new material every day: many topics build upon preceding ones!
  • On exams and homework sets, the way you express your solutions is important! Except where all you are doing is the very calculation I explicitly asked you to do, indicate clearly what you are doing, and why—you may get reduced or no credit for the right answer obtained for the wrong reason or no reason at all! Write in complete mathematical sentences. Arrange each answer so that the order of its parts is unambiguous. Distinguish “if” clauses from “then” clauses; include necessary “every” and  “some” qualifiers.

EXAMS

These cover both theory and calculation. You need to know definitions and statements of theorems. You will be able to use a calculator and—if, as expected, the exams are given at a lab—Mathematica. In any case, you should show the setup leading to the computations.

Final exam

Covers the entire semester's work, with some emphasis on material since second mid-semester exam. You must take it at the scheduled time. Final exam conflicts are handled in the usual way.

Mid-semester exams

These are given during regular class time. Each is announced about a week in advance. If class on the exam date is canceled for any reason, the exam will be given at the next class.

There are no make-ups for mid-semester exams.  Any excuse for missing an exam due to unavoidable cause such as serious illness must be in writing. By University policy, I will excuse missing an exam due to certain University-sanctioned events or a day of religious observance (about which you appropriately notified me). The normal arrangement in the case of a valid excuse is that your grade will be based upon the rest of your work.

HOMEWORK SETS

Each homework set has a due date that is strictly enforced except for unavoidable cause affecting the whole class.  Normally the due date is a class day, and in that case the set is due at the start of class. If class on the due date is canceled for any reason, the next class meeting becomes the due date.

Some problems you turn in will not be graded at all, while others will merely get a “checkoff” as to whether you made an honest attempt to solve them. Of course, all papers will be treated alike in this regard.

Only the best 80% of homework set scores are counted.  This is to allow for all reasons that problem sets are not handed in on time, including illness, emergencies, officially excused absence from campus, and absence for religious observance.

For each homework set:

  • Use 8.5-by-11" paper and write legibly with a pen or dark pencil.
  • There should be no “frizzies” along an edge due to removing pages from a notebook (but punched holes are OK).
  • Leave at least a 1" right margin on every page, so the grader can write there.
  • Identify each problem from the textbook or notes with its number, e.g., “Exercise 1.5.1 (d”) or “Proof of Theorem 1.1.10”; or, for problems not from the text or notes, with at least a brief version of the problem statement.
  • Do not do different problems side-by-side in two or more columns on a page
  • Arrange your solutions in the order in which they are listed in the assignment.
  • Put your name at the top right of every page.
  • On the top right of the first page, just below your name, write “Math 455” then the set number.
  • If possible, staple the pages together in their upper left corner only; do not use any cover or folder.

For some homework you may be asked to provide me with a Mathematica notebook file containing your work.

Some problems you turn in may not be graded at all, while others may merely get a “checkoff” as to whether you made an honest attempt to solve them.  Of course, all papers will be treated alike in this regard.

COLLABORATION AND PLAGIARISM

You are encouraged to work in a group of two or three. Indeed, for some or all of the homework sets, you will be expected to work collaboratively in a team of 2 or 3.  (Aside from the general benefits of collaborative learning, this is likely to be necessary due to the large class size and limited time available for grading, whether by a grader or by me.) For such team homework sets:

  • a single paper is submitted on behalf of the entire team, and all members of the team receive the same grade;
  • for each set, the teams must be disjoint from one another, and there should be no cross-discussion between different teams; and
  • the teams may change from one homework set to another.

In any non-team homework sets, even though you may still work in a group, you must turn in a separate paper of your own, on which you name any collaborators and acknowledge everybody (except me) from whom you received any significant help. You must be explicit in indicating on which problem(s) you received help of what kind from whom.

In all cases, team or non-team, you must explicitly cite any sources you use other than the textbook, your own Math 455 class notes,  handouts in class, materials available on this web site,  documentation accompanying Mathematica, or help from me. And you may not receive help from students who have taken Math 455 previously, nor search on the web for or otherwise use solutions to homework problems from previous offerings of Math 455.

Representing somebody else’s work as your own is plagiarism, for which there can be severe penalties under University policy.

ATTENDANCE

You are expected to attend regularly and are responsible for anything you miss! In accordance with University regulations, within the first calendar week of classes you should notify me in writing of expected absences for religious observance.

DROPS, WITHDRAWALS, INCOMPLETES

The last day to drop is Monday, February 9; to withdraw with a W, Tuesday, March 24 (Mid-Semester Date).

An Incomplete is possible only if (1) you had a compelling personal reason (e.g., serious illness), (2) your work has clearly been passing, and (3) there's a good chance you'll complete the course with a passing grade within the allotted time. Thus, failing work is no reason in itself for an Incomplete.

COPYRIGHT INFORMATION

Many of the materials created for this course are the intellectual property of the instructor. This includes, but is not limited to, the syllabus, lectures, printed handouts, and pages and files on the course web site whose intellectual ownership is not otherwise indicated. Except to the extent not protected by copyright law, any use, distribution, or sale of such materials  in any format—printed or electronic—requires the permission of the instructor. Please be aware that it is a violation of University policy to reproduce, for distribution or sale, class lectures or class notes, unless copyright has been explicitly waived by the faculty member.

Copyright ©2009 Murray Eisenberg. All Rights Reserved