DISCRETE ANALYSIS - HONORS – MATH 226H FALL 2003

Credits: 4.

Text: Discrete Mathematics and Its Applications (5-th edition).

By Kenneth Rosen, McGraw - Hill Inc. ISBN 0-07- 242434-6.

Prerequisites: Calculus II.

Examinations: Three common examinations will be given. The dates of the common exams are:

October 01

October 29

November 19

A comprehensive final examination will be given at the end of the semester. The date for this final examination will be announced at the end of the semester.

Quizzes: There will be a 15 minutes quiz most weeks; the quiz schedule is given in the next page, along with a list of problems from the textbook students should be able to solve. The quiz problems will be similar to those problems.

Final grade: The scores received on the three common exams, and the final examination will determine the final grade. The weighting factors will be: common examinations 30%, quizzes 20%, two projects 20%, and the final examination 30%.

Examination time conflicts: If a student is scheduled for more than one common Mathematics Department examination, then the examination in the course with a lower numerical designation will be taken at the regularly scheduled time and the other examination with the evening section.

Missed common examinations or quizzes: It is DMS policy that there are to be no make-up tests. If you miss one test, the grade for the missed test shall be determined by your grade on the final exam for the pertinent material. If you miss two common exams, you shall receive a grade of 0 (zero) for each missed exam. Attendance will be taken before each common exam to be checked against the exam booklets returned at the end of the exam.

Tardiness and absences: Students should try to come to class a few minutes before the scheduled time. On occasion, instructors will discuss the subject matter in a manner that differs from the presentation given in the book - absences make it very difficult to obtain the necessary material. Attendance is required. After more than three absences the Dean will be notified and may remove the student from the course. See Policy at http://math.njit.edu/Undergraduate/

Course_policies/exam_policy.html..

Homework assignments: Very many homework problems are given. They are an integral part of the course. Homework problems will not be graded. The instructors will answer questions pertaining to the homework problems in sessions held during the regularly scheduled class times. Additional information may be obtained from the Learning Center or from the instructors during office hours.

COURSE OUTLINE FOR MATH 226

Week 1 Introduction to logic, propositional equivalences, methods of proof.

Section 1.1 - probs: 2,3,4,6,7,13,18,20,25,26,29-30,33,34.

Section 1.2 - probs: 1,2,3-6,8ab,10ab,11,13,15,16,18,25,26.

Section1.5 - probs: 1,4,7,10,20,24,38-41.

Week 2 Sets, set operations, functions.

Quiz 1

Section 1.6 - probs: 1,2,3,5,6,8,13,15-17,19,22,24,25.

Section 1.7 - probs: 1,2,4,5,6,7,8,11,12,14,16,17,19,20,22,24,25-26,30,38.

Section 1.8- probs: 1-4,6,8-12,14,16-17,22,24,34,35,55,58,60.

Week 3 Integers and division, integers and algorithms, applications to number theory.

Quiz 2

Section 2.4- probs: 1,3,5,6,9,10,11,16,18,21,22,28,36,37,38,39,42,53,55,56.

Section 2.5 - probs: 2-5,8,10,19-21,23,27,28.

Section 2.6 - probs: 2,4,6,12,15,18,20,27,28.

Week 4 Mathematical induction, recursive definitions,

Quiz 3

Section 3.3 - probs: 1,4,6,7,9,11,12,15,17,18,21,23,29,36,47,60.

Section 3.4- probs: 2,4,5,7,8,12,24,26.

Review for exam 1.

Week 5 Basics of counting, the pigeonhole principle.

EXAM 1

Section 4.1 - probs: 1,3,4,8,9,17-19,21,24,27,29,30-33,36,38,39,41-43,48-51

Section 4.2 - probs: 1-4,10,14,16,18-20,22,24.

Week 6 Permutations and combinations, binomial coefficients, generalized permutations and combinations.

Quiz 4

Section 4.3 - probs: 1-3,6,7,8,10,15-17,19-21,25,26,27,31,33,39.

Section 4.4 – probs: 2,4,8,11,14,20,23,26,33.

Section 4.5 - probs: 2,4,6,8,10-12,14-17,19,20-22,24,26,30-35,38,41,46.

Week 7 Generating permutations and combinations, recurrence relations, solving recurrence relations.

Quiz 5

Section 4.6 - probs: 1,2,4,7,11 +additional problems given by instructor

Section 6.1 - probs: 2,4,5,6,7,11,18,19,23-31,36,38.

Section 6.2 - probs: 1,2,3,12,14,19,24,25,27,28,30,32

Project 1

Week 8 Inclusion-exclusion principle,applications of inclusion-exclusion, relations and their properties.

Quiz 6

Section 6.5 - probs: 1,2,4-6,8,10,11,14,15,18.

Section 6.6 - probs: 2,3,4,8,10,11,12,13,15,17,25,26.

Section 7.1 - probs: 1,3,4,6,7,8,24,25,27,28,32-34,39,40,46,54.

Week 9 Representing relations,closures of relations, equivalence relations

EXAM 2

Section 7.3 - probs: 1,2,4,7,8,13,14,15,18-20,24,27,32.

Section 7.4 - probs: 2,3,9,10,11,16,17,19,20,26

Section 7.5 - probs: 1-3,5,7,10,12,16,18,20,22-24,26,30,32,35.

Week 10 Partial order relations, graphs, graph terminology and representation.

Quiz 7

Section 7.6 - probs: 1,2,4,5,8,9,11,14,15,16ac,18,19,20,26-28,35,37,38.

Section 8.1 - probs: 1,4,6,8,11,15,17

Section 8.2 - probs: 1,3,4,5,6,8-10,15,18-21,24,25,26-30,33,38-43.

Week 11 Isomorphism, connectivity.

Quiz 8

Section 8.3 - probs: 2,4,6,8,10,12,14,16,18,20,22,24,26,29,30,35,37-39,41,43,46,54,55,57ab,58,62,63.

Section 8.4 - probs: 2,4,5,10,15,16,17,18,39,42.

Review for Exam 3.

Week 12 Euler and Hamilton paths, shortest path problems.

EXAM 3

Section 8.5 - probs: 1,2,4,5,7,10,14,15,22,26-29,31- 33,36,37,40,41,44,45.

Section 8.6 - probs: 2,3,6,11,17

Week 13 Planar graphs, graph coloring.

Quiz 9

Section 8.7 - probs: 1,3,4,6,9,10,14,18,20,22-24.

Section 8.8 - probs: 1,2,4,6,8,10,13,15,17,27.

Week 14 Introduction to trees, spanning trees, review.

Quiz 10

Section 9.1 - probs: 1,2,4,6,9,10,12,14,16-20,22,24-26.

Section 9.4 - probs: 1,3,6,7,9,11,13,14,17,28,30.

Project 2

Week 15 Review.

Prepared by Jey Ratnaswamy on August 11, 2003.