FALL 2011 Prof. Linner - Watson 326 e-mail: alinner@math.niu.edu Office hours: M,W 10-10:45; T,F 1-1:45 or by appointment. TEXT: Discrete Mathematics by Dossey, Otto, Spence, and vanden Eynden, 5th ed. GRADING: Exam 1 - 3: 100 points each Quiz 1 - 5: 25 points each Final Exam: 200 points The Final Exam is comprehensive! Quiz problems will be selected from the homework assignment! Attendance is important! The quizzes will not be announced in advance and there will be no make-up quizzes. The purpose of the quizzes is both to assess the quality of your homework and to measure your attendance. For you final total score I will count the two highest of your three midterm exam scores. I will count the four highest of your five quiz scores. Together with the final exam score this amounts to a total of 500 points. Grades are assigned as follows: A: 425 - 500 B: 350 - 424 C: 275 - 349 D: 250 - 274 F: 0 - 249 FINAL EXAM: MONDAY, December 5, Noon - 1:50 P.M. WEEK DATES SECTION TOPIC HOMEWORK 1 Aug. 22 1.1 PERT 4,8,14 Aug. 23 1.2 Matching 8,12,15 1.3 Knapsack 21,24,25,26,29,30 Aug. 24 1.4 Algorithms, Efficiency 11,12,25 Aug. 26 1.4 Algorithms, Efficiency 27,29 2 Aug. 29 2.1 Set operations 9-16,22,25-28,39 Aug. 30 2.2 Equivalence Relations 9,10,23,25,31 Aug. 31 2.3 Partial Ordering 8,26,30 Sep. 02 2.4 Functions 1-4,45-52,60 3 Sep. 05 LABOR DAY - no classes Sep. 06 2.5 Mathematical Induction 3,7-10,11,14,19 Sep. 07 2.6 Applications: Induction 37,47 Sep. 09 3.1 Congruence 1,6,9,14,17,28,33 4 Sep. 12 3.2 The Euclidean Algorithm 3,4,7,8,19,20,24,25 Sep. 13 3.3 RSA 23,24 Sep. 14 3.3 RSA Sep. 16 3.4 Error: Detection/Correction 1-8,23,24, 5 Sep. 19 Review Sep. 20 Exam 1 Sep. 21 4.1 Graphs 21,24,30,31,42,43 Sep. 23 4.2 Paths/Circuits 18-23,41,50,51 6 Sep. 26 4.3 Shortest Paths 3,7,15,16 Sep. 27 4.4 Coloring 1-8,10,12,23,24 Sep. 28 4.5 Directed Graphs 11,19-22,53,54,63 Sep. 30 5.1 Properties of Trees 14,15,25 7 Oct. 03 5.2 Spanning Trees 5,6,37 Oct. 04 5.3 Depth-First Search 3,27 Oct. 05 5.4 Rooted Trees 5.5 Traversals 17,23,29,33,39,48,49 Oct. 07 5.6 Optimal Binary Trees 40-42 8 Oct. 10 Review Oct. 11 Exam 2 Oct. 12 8.1 Pascal's Triangle 5,7,9,18,25 8.2 Fundamental Principles 10,16,23,24,33 Oct. 14 8.3 Permutations/ Combinations 15,21,29 LAST DAY TO WITHDRAW 9 Oct. 17 8.4 Arrangements/Selections 5,19,23 Oct. 18 9.1 Recurrence 7,9,15 Oct. 19 9.2 Iteration 1-4,11-18 Oct. 21 9.3 Linear difference equations 5,13,17,20 10 Oct. 24 9.4 Efficiency Oct. 25 9.5 Generating Functions 1,2,5,6,13,17,20 Oct. 26 9.6 Algebra 1,5,8,11,15,18 Oct. 28 10.1 Logical Gates 3,4,5,9,12,19,22,31,32,37,38 11 Oct. 31 10.2 Combinatorial Circuits 5,6,11-13,25,28 Nov. 01 10.2 Combinatorial Circuits 35,36 Nov. 02 10.3 Karanugh Maps 7-12 Nov. 04 10.3 Karnaugh Maps 25-34 12 Nov. 07 Review Nov. 08 Exam 3 Nov. 09 6.1 Distinct Representatives 1-16,21 Nov. 11 6.2 Matchings in Graphs 1-6,11-16,21 13 Nov. 14 6.3 Matching Algorithm 5,6,11 Nov. 16 6.4 Applications 13 Nov. 18 6.5 The Hungarian Method 1,3,6,13 14 Nov. 21 7.1 Flows and Cuts 3,7,9,12 Nov. 22 7.2 Flow Augmentation 5,7,13,23 Nov. 23 THANKSGIVING BREAK - no classes Nov. 25 THANKSGIVING BREAK - no classes 15 Nov. 28 7.3 Max-Flow Min-Cut 5,9 Nov. 29 7.4 Flows and Matchings 7-10,11,15 Nov. 30 Review Dec. 02 Review

**ACADEMIC MISCONDUCT:** Please read the statement on Academic Integrity which appears in the Undergraduate
Catalog, and which includes this passage: ``Students guilty of, or assisting others in, either cheating
or plagiarism, on any assignments, quizzes, or examinations, will receive a grade of F for the course
involved and may be suspended or dismissed from the University.''

- Cell phones must be silent and not used during class or exams.
- Children are not permitted in class.
- You are expected to arrive and depart class on time.

** Failure to abide by the following will result in a zero score!**

- PDA's and cell phones shall be stowed and not be visible during exams.
- Talking or other communication between students is not permitted during exams.

Please contact your instructor early in the semester so that we can provide or facilitate in providing accommodations you may need.