Homework Seven Quick Answers 1. 2 (263 103) 5.1.18 2. You can choose 21 21 integer pairs. In the given range 11 are even, 10 are odd. So: (11 11 10 10)/21 21...
Computer Science 575 / Math 513 Fall 2014 December 10 Office hours this week for 575/513: Wednesday 1 2:30 (no office hours monday or tuesday, except by appointment...
Homework Six quick answers 1. 27 cells, 14 black, 13 blue. Center cell is blue. HAM path must be 27 long, must start and end with black (the 14 count color). But...
Homework Nine Quick Answers 1. C(12,6) 2. Generator is (1 x x2)50 seek coefficient of x40 This begins C(89,40) C(50,1) C(86,37) C(50,2) C(83,34)... 3. Just pick...
Homework Assignment Nine You may collaborate on numbers 4,5, 8. Notation in brackets are references to problems in Tucker, 5th edition. 1 Find the coefficient of...
Homework 12 Quick Answers 1. For example,pi2 is (a b c d) 2. pi2 and pi3 3. 1/4 2 64 2 2 16 2 32 4. n even: 1/2(3 2n 1); n odd 1/2(3 2n 1 3 2(n 1)/2))...
Homework Assignment Ten You may collaborate on numbers 1,3,5,7. 1 Find a recurrence for the number of n letter sequences using letters A, B, and C, such that any...
Homework Assignment 11 You may collaborate on problem numbers 3,5,6 1 How many ways are there to roll 9 distinct dice so that all 6 faces appear? 8.2.2 1 What...
Homework Assignment Eight You may collaborate on 3, 6, 12. Citations in indicate problem numbers in Tucker, 6th edition. 1 Show the correctness of this binomial...
Homework Assignment Seven 1 How many different license plates involving 3 letters and 3 digits are there if the three letters appear at the beginning or at the...
Homework Assignment Six 1. Consider 27 cubes arranged in a 3x3x3 array. Form an associated graph with each cube viewed as a vertex, and with two vertices adjacent...
Quick Answers Homework Assignment 5 1. Suppose a connected graph G has 20 edges. What is the maximum number of vertices possible in G? Answer: 21 this is the tree...
CS 575 / Math 513Homework Three Quick Answers 1. Choose a max length path in G with endpoints a, b. Take a. Its links must go back into path, else path could...
Homework Five CS 575 / Math 513 You may collaborate on #2 and #6. 1. Suppose a connected graph G has 20 edges. What is the maximum number of vertices possible in...
Computer Science 575 / Math 513 Homework Assignment Four Collaboration permitted on: 6, 8,9,10 Due: Tuesday, September 30, in class RobbieMoll 17 Feb 2009
Computer Science 575 Math 513 Fall 2014 Homework 3 You may collaborate on #2,8,9 1. Suppose d 1, and for graph G every vertex has degree d. Show that G must...
Computer Science 575 Homework Assignment #2 Assignment is attached at the bottom of this page (pdf format). You may collaborate on problems 3 and 7. Due date: Tuesday...
Computer Science 575 Fall 2014 Homework Assignment 1 All problems are from the textbook, fifth edition. I`ve also attached an image of the problems if you are using...
Course Resources CS 575 / Math 513 Textbook: Alan Tucker, Applied Combinatorics (Wiley) 6th edition. On sale at textbook annex Other useful texts: Roberts...
575/513 Final Fall 2006 Answers 1. How many distinct four digit numbers have the property that their digits sum to 31? Answer: Via generating functions look for...
Homework 8 Quick Answers 1. Rewrite the generic term as C(m,m k) C(n,r k). In this form the target, C(m r,m n) accounts for all paths to location m r at depth m n...
CS 575 / Math 513 Homework 4 Quick Answers 1. a) Kn for odd n; b) K2; c) r,s both even. 2. No this would be an Euler cycle on the graph of board cells, with...
CS 575/ Math 513 Homework 2 Answers Homework Two Answers 1. vertices are labeled 0 16. Each vertex has arcs to next 3 (e.g. 8 9, 10, 11). Second player...
Course Grading 575/513 Grading: 50% homework problems; 15% midterm; 35% final. Also: you must pass the final to get a C in the class. Collaborative solutions...
Homework Ten Quick Answers 1. 7.1.8 Use identity C(n,k) C(n 1,k) C(n 1,k 1) 2. 7.1.18 a. An 2An 1 An 2; b. An An 2 2An 1 4An 4 3. 7.1.22 An 2An 1 2 (n 1) 4. 7....
Computer Science 575/ Mathematics 513 Combinatorics and Graph Theory Final Exam May 14, 2005 Show all you work! 1. Given two copies each of the letters a,b,c,d,e...
Homework Assignment Twelve Due: in class on Tuesday, December 12 last day of class (all work due at that time!) 1. 9.1.2 2. 9.1.12 3. 9.2.4 4. 9.2.10 5. 9.3.4...
Homework Assignment Nine Due in class on Tuesday, November 14 1. 6.2.4 2. 6.2.18 3. 6.2.24 4. 6.2.30 5. 6.3.14 6. 6.3.22 7. 6.4.10 8. 6.5.2e 9. 7.1.2 RobbieMoll...
Lecture Eleven: Matching The fundamental theorem about unweighted bipartite matching is Hall` theorem: a bipartite graph (X,Y,E) has a complete match(i.e. a match...
Telegraphic Answers to Homework Assignment Five 1. 3.1.2 21 2. 3.1.18 use the fact that if c1 and c2 are centers, and b1 and b2 are leaves that witness for the...
Lecture Ten: Network Flows Lecture today follows the text fairly closely A network is a loop free directed connected graph with a unique source (a), sink...
Homework Assignment Six 1. 4.4.2 2. 4.4.8 3. 4.2.13 4. 4.2.6 5. 4.3.2 a,b 6. Two spanning trees on a Graph N, say T1 and T2, are `neighbors` if T2 can be obtained...
Computer Science 575 / Mathematics 513 Combinatorics and Graph Theory Midterm Exam March 10, 2005 1. (15) Characterize trees that have Euler trails. 2. (15) An...
Lecture Nine: Trees, part 2 Recall a tree is connected graph without circuits If G is a connected, undirected graph, then it has a spanning tree T a...
Lecture Eight: Trees, part 1 Def a tree is connected graph without circuits Textbook quickly switched to rooted trees: trees with distinguished `root`...
Homework Three Quick Answers 1. 1 supp 4 (p. 49) 11 vertices is minimum. K11 has 55 edges, K10 has 45 2. 1 supp 10 Consider (a) shortest path from a to b, where a...
Lecture Six Notes Lecture six covers the basics of Euler cycles and Hamiltonian circuits and their variants. The fundamental theorem about Euler cycles, due to Euler...
Lecture Five: Wagner`s Theorem Every planar graph has a planar drawing constructed using just straight lines. Def a max planar graph (mpg) is a planar graph...
Homework Assignment Twelve Due: in class on Thursday, May 12 last day of class (all work due at that time!) 1. 9.1.2 2. 9.1.12 3. 9.2.4 4. 9.2.10 5. 9.3.4 6. 9....
Homework Assignment Nine Due in class on Tuesday, April 12 1. 6.2.4 2. 6.2.18 3. 6.2.24 4. 6.2.30 5. 6.3.14 6. 6.3.22 7. 6.4.10 8. 6.5.2e 9. 7.1.2 RobbieMoll...
Homework Assignment Six 1. 3.3.6 2. 3.3.10 b 3. 4.2.13 4. 4.2.6 5. 4.3.2 a,b 6. Two spanning trees on a network N, say T1 and T2, are `neighbors` if T2 can be obtained...
All numbered homeworks are from the Tucker text 1. 1.1.4 2. 1.1.20 3. Prove that no graph with two or more vertices has the property that all its vertices have different...
Computer Science 575 / Mathematics 513 Combinatorics and Graph Theory old midterm answers 1. A graph is regular if all of its vertices are of the same degree. Suppose...
UMass CS EdLab.Moll575 Web Preferences The following settings are web preferences of the UMass CS EdLab.Moll575 web. These preferences overwrite the site level...
This is a subscription service to be automatically notified by e mail when topics change in this Moll575 web. This is a convenient service, so you do not have to...