Math 232: Discrete Mathematics

Spring 2006





Instructor:
Martha Wallace


Find me in OMH 103
Phone me at x3408
Email me

Text:

Dossey, Otto, Spence, Vanden Eyden, Discrete Mathematics, Fourth Edition
Tools:
 TI-89 or similar calculator, Maple, and a willingness to tackle nonroutine problems



What is Discrete Mathematics?

Discrete mathematics is a branch of mathematics that models the world of information processing and social decision-making. Discrete (non-continuous) mathematics has become increasingly important as more situations are investigated, represented, and solved using computers. Discrete mathematics explores three central questions in solving problems:
  1. Existence: Is there a solution?
  2. Algorithmic solutions: Can we construct an efficient algorithm to solve the problem?
  3. Optimization: Which solution is best?
Topics we will study include:
  1. graph theory: using vertex-edge diagrams to model and investigate relationships among a finite number of elements;
  2. combinatorics: systematic counting procedures;
  3. recursion: describing and investigating sequential change;
  4. algorithms;
  5. logic and proof

The emphasis will be on modeling and problem solving. Future teachers will look at the role of discrete mathematics in high school mathematics.


Class Policies:

Homework Policy:

With few exceptions, you will have two assignments due each day:

A reading covering the material to be discussed during that class period. For each reading assignment, you are to read the section carefully, identifying the main concepts and questions you may have. Your reading assignment is a very important part of your work in this class, and you should be prepared for the possibility of random card quizzes covering the basics of the reading. Card quizzes are 2-3 question quizzes administered in the first 3 minutes of class testing the major points of the assigned reading. They do count toward your grade.


A writing assignment based on the material discussed in the previous class as well as often some preview problems from the next sections and possibly some review problems from previous sections. This assignment should be done in draft form by the next class day to allow for a small amount of explication in class. The final form of each assignment is due on the second class day after it is assigned. You are encouraged to work with other class members to do your homework assignments, and may if you wish, submit one paper for two people. (If you do this, be sure to put the names of both contributors on the paper and take turns writing the final draft so that you both get your writing critiqued.) The writing assignments will be corrected and the grades will count toward your final grade in the course.

No late homework will be accepted, but 3 writing homework scores and 3 card quiz scores will be dropped.

Computer Work:

During the semester, we will have a few computer labs and computer components of many other assignments. You will use the computer algebra system Maple 8 for these assignements. This program is available on the computers in SC 175 and OMH 108. Some of the tests may have a take-home portion on which you will be expected to use Maple.

Grading Policy:
How does your work contribute to your final grade?


What grade will you get in this class?
Components: Points Possible:

Total Points Earned as % of Possible Minimum Grade You Will Earn
Homework, Labs and Quizzes 100-150 points

90% A-
2 Tests 200 points

80% B-
Final 150 points

65% C-
Total Possible 450-500 points



Hints for Success:

Reading the material carefully before it is covered in class is a big step toward success in any math course. Successful students typically outline or otherwise summarize the material briefly in their notebook and highlight questions to bring to class. A great way to become familiar with concepts and techniques is to work each of the examples. (This means work on paper -- don't just read and nod.)

Be sure to work lots of problems -- they are fun!

Make sure that you begin the assigned homework as soon as possible after it is assigned and bring a nearly complete homework paper to the following class so that you can get the most out of any homework discussion in class. Be sure to make connections in your mind between discrete concepts and the other mathematics that you have studied.
Disability Policy:

If you have a documented disability that will impact your work in this class, please contact me to discuss your needs. Additionally, you will need to register with Student Disability Services located at the Academic Support Center in Room 1 of the Old Main Annex. All such discussions will be confident


Assignments, Mathematics 232: Spring 2005


  • Math Fun Facts!

    • Date Section(s) Topic(s) Assignments given this date:
    2/07
    		1.1-1.3
    		 Intro to Discrete Mathematics
    		 1.
  • Read for next class: To the Student and Sections 1.1-1.3; Course Information on Moodle (Be ready for a card quiz on course policies)
  • Written Homework: 1.1: 13, 19; 1.2: 5, 7, 11, 19, 27; 1.3: 1-13 odd, 19
  • Written HW Due: 2/11/05
    • 2/09
    		 2.1-2.3
    		 Set and equivalence basics, congruence
    		 2.
  • Read for next class: 2.1-2.3
  • Written Homework: 2.1: 3, 7, 11, 17, 25; 2.2: 5, 7, 13, 19; 2.3: 9, 13, 17, 21, 25, 29, 33
  • Written HW Due: 2/14/05
    • 2/11
    		 2.5
    		 Check digits -- java
    Public Key Code
    Java encoder
    		 3.
  • Read for next class: 2.5-2.7
  • Note: no written hw on 2.5, but you will be expected to know it.
  • Written Homework: 2.3: 37, 39, 41; 2.6: 3, 5, 9-27 odd.
  • Written HW Due: 2/16/05




    • 2/14
    2.6


    Inductive Reasoning

    vs.

    Proof by Induction

    		 4.
  • Read for next class: 3.1
  • Written Homework:
  • p. 34: Make a chart to follow each of the algorithms 28-30. In each case, let n =10 and pick your own values for the other variables. You don't need to answer any questions, just make sure that you have a chart for each tracing the values of each variable through the steps. (See chart on Week 3 for example.)
  • 2.7: 7, 9-12, 21, 25, 27, 29, 37, 40, 43
  • Written HW Due: 2/21/05
    • 2/16
    2.6    		 Proof by Induction again 5.
  • Read for next class: 3.1, 3.2
  • Written Homework: 2.6: 12-28 even
  • Written HW Due: 2/21/05
    • 2/18
    2.7, 3.1
    Intro to Graph Theory    		 6.
  • Read for next class: 3.3
  • Written Homework: 3.1: 16, 17, 21, 22, 23, 24, 28, 30, 38, 41, 42, 45, 46, 48; 3.2: 9, 11, 18, 20, 24, 26, 30
  • Written HW Due: 2/23/05




    • 2/21
    		 3.2, 3.3
    		 Paths and Circuits,
    Shortest Paths, Distance
    		 7.
  • Read for next class: 3.4
  • Written Homework: Finish worksheet handed out in class. 3.2: 10, 31, 32, 52, 53, 54, 56, 60; 3.3: 1, 3, 5, 7, 9, 13
  • Written HW Due:2/25/05
    • 2/23
    		3.3, 3.4
    Why distance procedure?
    Graph coloring
    		8.
  • Read for next class: 3.5
  • Written Homework: 3.3: 2, 6, 8, 16; 3.4: 1, 3, 4, 11, 13, 15; Also, explain why we can tell from M^3 the number of paths of length 3 from A to D in the class example that we used to explain paths of length 2.
  • Written HW Due: 2/28/05

    		•
    2/25
    		 3.5
    		 More graph coloring
    Digraphs
    		 9.
  • Read for next class: no new reading
  • Written Homework: 3.4: 16, 25, 26, 32; 3.5: 5, 10, 11-23 odd, 34, 35
  • Written HW Due: 3/02/05

    		•




    2/28
    		Sprouts again
    Inductive proof again
    		 10.
  • Read for next class: 4.1
  • Written Homework: 3.5: 39,

  • 41, 44, 48, 52, 53, 55, 62, 67; Coloring problems sheet: Work the first of the two scheduling problems (the ones with the charts);
  • Written HW Due: 3/04/05
    		•
    /02
    		 4.1
    		 Trees
    		 11.
  • Read for next class: 4.2
  • Written Homework:
  • p. 105: 73, 77;
  • p. 181: 27;
  • 4.1: 11-17, 27, 28;
  • Sprouts: Find the minimum and maximum number of moves in a game starting with n vertices. (Note that this may be different than the number of vertices, which is how we approached it in class.)
  • Written HW Due: 3/07/05

    		•
    3/04
    		 4.2

    Spanning trees

  • Die Hard 3 Problem
  • Ivars Peterson's Math Trek: Measuring with Jugs


    		• 12.
  • Read for next class: 4.3
  • Written Homework: 4.2: 3, 7, 8, 9, 10, 17, 18, 25, 26, 29, 38, 39; Frogs: Determine the number of moves if there are 3 of each color. Explain how you count. Expand to n of each color.
  • Written HW Due: 3/09

    		•




    3/07
    		 4.3
    		 Depth-first searches
    		 13.
  • Read for next class: 4.4
  • Written Homework:4.2: 30, 37; 4.3: 3, 6, 9, 12, 15, 18, 26, 27, 38, 39
  • Written HW Due: 3/11

    		•
    3/09
    		4.4
    		 Rooted trees
    		 14.
  • Read for next class: None
  • Written Homework: 4.3: 32. 34. 40; 4.4: 16, 29-32; Ch. 4 Supplementary Exercises: 1, 26, 29.
  • Written HW Due: 3/14
    		•
    3/11
    		7.1
    		 Pascal's Triangle and the Binomial Theorem
    		 15.
  • Read for next class: 7.1 and use the binomial theorem and Pascal's triangle to do the homework below.
  • Written Homework: 7.1: 6, 8, 10, 18, 20-25; Find patterns in P.T by 1) sum of the squares of the numbers in each row, 2) sum of the numbers in a tilted rectangle.
  • Written HW Due: 3/18 -- instead due 3/30
    		•




    3/14
    		 7.1
    		 More Pascal's Triangle with patterns
    Test I (through 3/09) Out
    		 16.
  • Read for next class: 7.2, especially Pigeonhole examples
  • Written Homework:Pascal's triangle sheet: 9-10, 11-12 then state and prove general rule, 16 -18; Pigeonhole sheet: 5-7; Text 7.1: 27, 28;
  • Written HW Due: 3/30 -- instead due 4/1
    		•
    3/16

    		No Class


    • 3/18
    		7.2
    TEST I Due


    • 3/19-28
    		Spring Break
    		 Spring Break
    3/30
    		 7.2

    Pigeonhole and Other Principles

    Homework Assignment 15 due

    		 17
  • Read for next class: 7.3 and Proof of Th. 2.12 on pp. 97-98
  • Written Homework: 7.1: 19-23 odd; 7.2: 2-8 even, 11, 12-18 even, 26, 28, 32
  • Written HW Due: 4/04
    		•
    4/01
    		 7.3
    		 Permutations and Combinations
    		 18.
  • Read for next class: 7.4
  • Written Homework: Prove binomial theorem by induction; 7.3: 14-28 even
  • Written HW Due: 4/06
    		•





    4/04
    		 7.4
    		 Arrangements and Selections with Repetitions
    		 19.
  • Read for next class: 7.5
  • Written Homework: 7.4: 2, 4, 6, 10, 14, 16, 18, 23, 24, 31, 34; 7.5: 4, 8, 12, 16, 20, 28, 32; 7.2: 28; Extra credit - 7.5:24
  • Written HW Due: 4/08


    • 4/06
    		 7.5
    		 Probability
    		 20.
  • Read for next class: 7.6
  • Written Homework: 7.5: 2, 6, 10, 14, 18, 22, 26, 29; 7.6: 1-4, 10
  • Written HW Due: 4/11


    • 4/08
    		7.6
    		 Inclusion-Exclusion
    		 21.
  • Read for next class: 7.7
  • Written Homework:7.6: 5, 6, 8, 12, 15, 16, 18, 23,
  • Written HW Due: 4/13







    • 4/11
    		 7.7
    		 More fun with probability
    		 22.
  • Read for next class: Nothing new
  • Written Homework: 7.6:
  • 10(remove from this assignment -- done on assignment 20),
  • 13, 19, 20, 29 (hint: keep n as a constant, and think of situation as finding the number of subsets of an n-element set, but not including empty set or all of the original set),
  • 30, 34(use formula in 33 along with what you found in 29);
  • p. 412: 14, 18, 20
  • Written HW Due: 4/15 -- extended to 4/18


    • 4/13
    		8.1
    		 Recurrence Relations
    		 23.
  • Read for next class: 8.1
  • Written Homework: pp. 412-413: 11, 19, 21, 31, 33, 39, 41, 49, 51, 55, 57, 59, 60
  • Written HW Due: 4/18


    • 4/15
    		8.2
    		 Recurrence Relations, Iteration
    		 24.
  • Read for next class: 8.2
  • Written Homework: 8.1: 13-19 odd, 22, 24, 28, 30; 8.2: 11, 13; Write a recurrence relation and initial conditions for the number of regions in a plane formed by n lines, where each line intesects each other line, but no three lines have a common intersection. Extra credit: 8.1: 35 (the answer is the same as the answer for the stacks example -- for credit, explain why this is true.)
  • Written HW Due: 4/20







    • 4/18
    		8.2
    		 Linear Difference Equations
    		 25.
  • Read for next class: nothing new
  • Written Homework: 8.2: 1-4, 9 (hint -- look at 7), 16, 18, 24, 27, 28, 33 -- (Note that there is a mistake in #3. The second n-1 subscript should be n-2.)
  • Written HW Due: incorporated into next homework

    • 4/20
    		8.3
    		 Linear Difference Equations
    		 26.
  • Read for next class: 8.3
  • Written Homework: p. 414: Use what we started in class to do 56, 57, and 60 part 2; 8.2: 1-10, 17-18, 22, 24, 26, 27, 28, 33
  • Written HW Due: 4/25


    • 4/22
    		8.5
    		Generating Functions
    		27.
  • Read for next class: None
  • Written Homework: 8.3: 6, 10, 14, 18, 22, 25-30 (use the formulas for first and second-order equations for these), develop the formula for a first-order linear difference equation.
  • Written HW Due: 4/27







    • 4/25

    		More fun with iteration
    		 28.
  • Read for next class: none
  • Written Homework: 1) Complete Tiling with Squares and Dominoes sheet (handed out in class and available in Class Materials folder on L-drive), 2) Develop formula for second order linear difference equation where characteristic equation has repeated roots.
  • Written HW Due:


    • 4/26

    		Dominoes
    		 29. Different Assignments for Different People, due on Monday:
    1. For people who have not had Math 244 or 252 or believe they need more work on logic: Not for seniors! Appendix A: Read carefully all of appendix A and work enough of the odd numbered problems in each section that you can test yourself on your understanding and practice what you just learned. (e.g. you probably only have to do a one or two problems of each type in section 1, then do more of each type in sections 2 and 3.)
    2. For people who have had 244 and/or 252: Work through all of the examples in the domino handout and try any three of the proofs in the exercises. The handout will be in a folder outside my door.
    4/28
    		Logic and Proof
    or Dominoes
    		 30.
  • Read for next class: See above for assignment
  • Written Homework: See above
  • Written HW Due:








    • 5/02
    		Problem Solving
    		 31.

  • Read for next class: Block walking sheet (in class folder)
  • Written Homework:
  • 1) Use block walking method to verify the following identity: (C(n,0))^2 + (C (n,1))^2+ ... +(C(n,n))^2 = C(2n,n);
  • 2) Domino sheet --
  • a. people who did Appendix A be able to explain all of the examples and work any one exercise;
  • b. people who did Domino sheet before be able to explain exercises 12, 16, 17, 18.
  • Written HW Due: Bring assignments 29 and 31 to class on 5/4/05


    • 5/04
    		Problem Solving

    		 32.
  • Read for next class: Nothing new
  • Written Homework: Ole and lena sheet.

  • Written HW Due: Finish and bring to class on 5/06
    		•
    5/06

    		33.
  • Read for next class: Nothing new
  • Written Homework: None -- prepare for test
  • Written HW Due: Bring all recent assignments to class on 5/09
    		•





    5/09
    		Problem Solving
    TEST II out
    		 34.
  • Read for next class:
  • Written Homework:
  • Written HW Due:


    • 5/11
    		Problem Solving

    35.

  • Read for next class:
  • Written Homework:
  • Written HW Due:


    • 5/13
    		Problem Solving
    		 36.
  • Read for next class:
  • Written Homework:
  • Written HW Due:







    • 5/16
    		Course Summary

    5/21


    Final Exam, 2:30-4:30 p.m.






    Disclaimer

    Disclaimer