Northern Illinois University

**DISCRETE MATHEMATICS (4 semester hours)**

**PREREQUISITE:**
Math 110 or Satisfactory performance on the Placement Exam

- Section 1, 1:00-1:50 MWHF, DU 300, Richard Blecksmith/a>
- Section 2, 3:00-3:50 MWF and 3:30-4:20 Thursday, DU 302, Richard Blecksmith

- Office: Watson Hall 344 (later Watson Hall 355)
- Email: richard@math.niu.edu
- Phone: 753-1835
- Office Hours: Mon and Wed 2-3, Wed 4-5, Thurs 2:30-3:30

- To understand and connect concepts of discrete mathematics with real world problems and other scientific disciplines, especially computer science.
- To value mathematics and develop an ability to communicate mathematics, both in writing and orally.
- To develop mathematical reasoning and to understand the basic tools of elementary combinatorics, number theory, and graph thoery.
- To attain computational facility and an ability to analyze and develop efficient algorithms.

**SYLLABUS:**
The course will cover most of Chapters 1-5 of the text.

- 1.4 Algorithms and their Efficiency
- 2. Sets, Equivalence Relations
- 3. Coding Theory:

Congruence, Euclidean Algorithm, Encryption, Decryption, Error Correction - 4. Graphs:

Paths, Circuits, Shortest Path, Coloring Problems, Directed Graphs, Multigraphs - 5. Trees:

Spanning Trees, Depth-first search, Breadth-first search, Rooted Trees, Binary Trees

**WITHDRAWAL:**
The last day for undergraduates to withdraw from a full-session course
is Friday, March 11

**GRADING:**
Grades will be assigned on the basis of 500 points, as follows:

- 2 hour exams worth 100 points each
- Quizzes 100 points total
- Homework 100 points total
- Final exam 100 points (

- A: 85%
- B: 75%
- C: 60%
- D: 50%

- HomeWork I Due 1/28
- 1.4 page 33: 1 - 21 odd
- 2.1 page 45: 1 - 27 odd

- HomeWork II Due 2/11
- 2.2 page 52: 2, 6, 10, 12, 18, 20, 24, 25, 26, 31
- POW Handout: Section 1, Binary Numbers, page 7: 1 - 8
- POW Handout: Section 2, Tic-Tac-Toe Code, page 10: 1 - 3

- HomeWork III Due 2/18
- POW Handout: Section 3, Pails of Water Problem, page 14: 1 - 6
- POW Handout: Section 4, Clock Arithmetic, page 17: 1 - 5

- HomeWork IV Due 2/25 (not collected)
- POW Handout: Section 5, Secret Codes, page 21: 1 - 5

- HomeWork V Due 3/4 (not collected)
- 1.1 PERT, page 8-9: 5, 8, 9, 12, 17, 18

- HomeWork VI Due 3/11
- 4.1 pages 161-4: 1, 4, 6, 9, 13, 15, 18, 19, 21, 22, 23, 28, 30, 42, 44

- HomeWork VII Due 3/25
- 4.2 pages 176-181: 10, 18, 20, 22, 24, 26, 28, 30, 31, 32, 33, 34, 41

- HomeWork VIII Due 4/1
- 4.3 pages 190-193: 2, 4, 6, 12, 16, 17

- HomeWork IX Due 4/8
- 4.4 pages 199-202: 2, 4, 6, 11, 12, 17, 23, 24, 25, 28, 33
- Show that the 7 triples of the Fano Plane cannot be bi-colored

- HomeWork X Due 4/15 (not collected)
- 4.5 pages 212-217: 8, 12, 17, 18, 23, 24, 26, 40, 42, 48, 68
- Venn Diagram Handout

- HomeWork XI Due 4/22
- 5.1 pages 234-237: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16, 17, 18, 26

- HomeWork XII Due 4/29
- 5.2 pages 248-253: 3, 4, 8, 9, 10, 12, 16, 18, 20, 22, 24, 34, 39, 41
- 5.3 pages 263-266: 2, 12, 20, 22, 24, 25, 26, 27, 28

- HomeWork XIII Due 5/5 (not collected)
- 5.4 pages 271-274: 2, 3, 4, 6, 8, 12, 17, 18, 20, 21, 24, 25, 28, 30, 32
- 5.5 pages 284-287: 2, 4, 6, 16, 22, 28, 36, 42, 46, 50, 52, 54, 58, 64
- 12 Pennies Problem: Find the bad penny in 3 weighings

- Test 1 Friday Feb 25
- 1.4 Alorithms
- 2.1 Sets
- 2.2 Equivalence Relations
- POW Handout, Section 1, Binary Numbers
- POW Handout, Section 2, Tic-Tac-Toe Error Correcting Code
- POW Handout, Section 3, Pails of Water Problem and the Euclidean Algorithm
- POW Handout, Section 4, Clock Arithmetic and Congruences
- POW Handout, Section 5, Secret Codes

**SAMPLE EXAMS:**
[WORK IN PROGRESS]
You may wish to look at some first exams from previous semesters to see the
level of analysis we expect students to be able to carry out.

NOTE: If you are looking for the sample exam, it is in PDF format, so
you will need
Adobe's Acrobat Reader which is a free and useful download. Click on
the above link to get the latest version of the Acrobat Reader.

Exam 1

Exam 2 (NOT READY)

Exam 3 (NOT READY)
Please note that different instructors assign different exams,
so that a certain raw score on one test might be comparable to
a very different score on another.

** Caution: ** These exams are from a different semester. The subject
matter was comparable, but the text, the audience, the instructor, and the
testing environment may have been different from what you will face.
The testing points in the syllabus also vary from semester to semester.
Please remember in addition that tests cannot be comprehensive; therefore,
there are topics ** not ** on this test for which the students were -
** and you will be ** - responsible for studying in prepartion for the
your own test.

**SPRING BREAK:**
Spring Break is from Saturday March 12 through Sunday March 20.
All classes are cancelled during this week.

**FINAL EXAM:**
The Final Exam is scheduled for the last day of classes, Thursday, May 5, 2011.
Class will meet during the final exam period to review the results of
this exam. These periods depend on your section:

- Section 1: Wed, May 11, noon - 1:50
- Section 2: Mon, May 9, 4 - 5:50

Note: The course changes and the exams change. Our goal is to help you learn the material in Calculus, not specifically to prepare you for the final exam. We may choose to assess your command of these ideas rather differently this semester, should the opportunity arise.

**CALCULATORS:**
Students are asked to have a graphing calculator with roughly the
capabilities of the TI-83. You will find this useful for investigating
the concepts of the class, so you can experiment with additional
examples. You may also want to verify parts of your homework calculations.

Graphing calculators will be allowed on all exams and quizzes, although
most, if not all, of the questions can be answered without it.
Calculators on cell phones or other devices which can communicate to
external devices are **not** allowed on tests or quizzes.

**TEXT:**
**Discrete Mathematics (5th. ed.)**,
by Dossey, Otto, Spence, Vanden Eynden (publ. by Pearson Addison-Wesley)

Some additional references:

- Discrete Mathematics: An Introduction to Mathematical Reasoning,
Brief Edition, by Susanna S. Epp, Brooks/Cole

- Discrete Mathematics with Applications,
Fourth Edition, by Susanna S. Epp, Brooks/Cole

- Discrete Mathematics,
Second Edition, by Richard Johnsonbaugh, Pearson/Prentice Hall

- Discrete Mathematical Structures,
Sixth Edition, by Kolman, Busby, Ross, Pearson/Prentice Hall

- Discrete Mathematics with Graph Theory,
Third Edition, by Goodaire and Parmenter, Pearson/Prentice Hall

- Computers, Codes, and Pails of Water
- Vocabulary List for Graphs
- Hamiltonian Cycles and the Proof of Ore's Theorem
- Dijkstra's Shortest Path Algorithm
- Fano Plane Problem
- Binary Numbers and Venn Diagrams

- Understanding Mathematics: a study guide,
from the University of Utah

- "Symbolic calculators" on-line which will compute derivatives and integrals.

**ACADEMIC CONDUCT:**
Academic honesty and mutual respect (student with student
and instructor with student) are expected in this course.
Mutual respect means being on time for class and not leaving early,
being prepared to give full attention to class work, not reading
newspapers or other material in class, not using cell phones
or pagers during class time, and not looking at another student's
work during exams. Academic misconduct, as defined by the Student
Judicial Code, will not be treated lightly.

**CAAR STATEMENT: **
If you have specific physical, psychiatirc, or learning disabilities and
require accomodations, please let your instructor know early in the semester
so thatyour learning needs may be appropriately met. You will need to
provide documentation of your disability to the CAAR (Center for Access
Ability Resources) Office located in the Health Services Building, 4th floor.

**ADVICE:**
Perhaps the single most important factor in your success
in this course is your ** study habits **.
Think of learning math as "working out" in the gym.
Study at least 3 times per week; do not wait until the day before the exam.
Learn mathematics like you would learn a language.
Work on the concepts until they make sense.
Don't just memorize facts and then forget them a few weeks later.
You will need to know this stuff for Calc III and other courses.
Master each homework problem - beyond just getting a correct answer.
Be on the lookout for mistakes in algebra and trig.
** Always come to class! **
While you're there, listen, think, and ask questions.

Last update: Feb 18, 2011