Discrete Mathematics

 Instructor - Robert Hochberg Text - Discrete Mathematical Structures by Kolman, Busby and Ross Grading Policy: Homework: There will be 9 12-point homeworks, worth a total of 100 points, plus 8 bonus points. Exams: There will be 300 points worth of in-class exams Final: There will be a 200 point final Therefore there are 600 points total available, and your grade will be: At least an A if you get more than 519 points At least an B if you get more than 459 points At least an C if you get more than 399 points At least an D if you get more than 339 points Open Problem: The "tile" above is made up of 8 equilateral triangles.  It is not known whether it is possible to put some number of tiles of this shape together to form a larger equilateral triangle without gaps or overlaps. If you figure out a way to do this, or prove that it can't be done, I'll be very grateful.

 Homework Column Homework 1 Prove all parts of Theorem 1 on pages 8-9 1.1 #5 1.2 #8 Test 4 - The Take-Home  Due at the Final (see below).  This test is worth 100 points.  You may work/study together, but may not write answers together.  Any pair of tests which have any identical answers will receive "0," and academic discipline according to section S.1 of the Code of Conduct. Homework 2 (Due Thursday 2/8) 1.3 #4, 6, 20, 26, 28, 30 4.2 #12 (Find the domain, range, matrix and digraph.  For each element not in the domain, give the reason; and for each element not in the range, give the reason) 4.2 #22 (Find the digraph for the relation R given by the matrix, and also the digraph of R2.  You do not need to give the relation itself.) Homework 3 (Due Thursday 2/15) Only the underlined ones need to be handed in 2.1 #2, 6, 8, 10, 18 2.2 #7, 12, 14, 18, 19 4.3 #10a (explain how you know you have all paths of length 2) 4.3 #12 1.5 #6 parts b and c (show work) 1.5 #10, 12 (show work) 8.1 #26 (we sort of did this in class...but I want to see how precisely you can write it up.) 8.2 #6, 10 (explain your answer) 8.3 #17 (give your best explanation) 8.3 #18 8.3 #19 (A different example from that in the back of the book) Homework 4 (Due Tuesday 2/27) Only the underlined ones need to be handed in 2.3 #3, 4, 10, 11, 26 2.4 #3, 5, 8, 15(see note), 17, 18 (Note that for problem 15, the expression "P(A)" means the set of all subsets of A.  So what problem 15 is really asking you to prove is that an n-element set has 2n subsets.  For example, the 3-element set {1, 2,3} has 8 subsets:  {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}) The Final Exam Thursday, May 3 8-10am In our usual room The study guide for this cumulative exam is, as usual, the set of assigned homework problems, including ones that weren't handed it. Homework 5 (Due Thursday, 3/22) 3.1 #2, 4, 6, 8, 10, 14, 16 Office Hours Week of 4/30-5/4 Monday: 2:30 - 5:30 Tuesday: 9-12 Wednesday: 1-4 Thursday:  10-12 Friday:  2-4 Homework 6 (Due Tuesday, 3/27) 3.2 #2, 4, 6 (omit the phrase for a seven story building), 8, 10, 12, 16, 24 Office Hours Week of 5/7 - 5/11 Monday:  2-4 Tuesday:  2-4 Wednesday:  10:30 - 12:30 Homework 7 (Due Thursday 4/5) 3.3 #2, 4, 6, 7, 10, 16 And what is wrong with problem 12? 4.1 #2, 4, 6, 8, 10 Homework 8 (Due Thursday 4/12) 4.2 #2, 4, 6, 14, 20 (note, there is some material here that we need to cover on Tuesday, such as digraphs and matrices) Homework 9 (Due Thursday 4/19) 4.3 #2, 4, 6 1.5 #5 (actually, ignore parts a, b, c and d of this problem, and just compute the following matrix products:  AB, CE, EC 1.5 #24, 25.  (again, ignore the directions to the problem, and just compute the matrix products of the indicated matrices.) Homework the last (Due Thursday 4/26) 8.1 #14, 24 ("regular" means that all vertices have the same degree) 8.2 #2, 4 , 6, 8, 14, 15 8.3 #2, 4, 6, 8, 10 (for 8 and 10, ignore the weights on the edges) This can be handed in until Friday, 4/27 Extra Credit (5 points) Draw a graph which has exactly one odd vertex, or prove that no such graph exists. This can be handed in anytime until Tuesday, 5/1