Homework 10 (due Tuesday, November 9th) This homework is to
be presented in class by the students of the
class.
1. 7B in Van Lint. (See the hint.)
2. 7C in Van Lint. (See the hint.)
3. 7D in Van Lint. (See the hint.)
4. 7E in Van Lint. (See the hint.)
5. 7F in Van Lint. (See the hint.)
6. Suppose that a manufacturer makes n different (positive) sizes of
steel beams, a1, ..., an, but only k < n sizes can
be stocked. Suppose further that the demand for each of the n sizes
in uniform. When a particular size for a steel beam is demanded by
a customer, it is necessary to go to the next larger size and cut it to the
smaller size with the cost to the manufacturer being the difference in sizes.
Find an algorithm to determine the sizes to stock that minimizes the
cost to the manufacturer.
7. Let A be an n-by-m matrix of 0's and 1's. Suppose that you
add 1's as follows: Every time that three out of four of the entries
in a 2-by-2 minor of A are 1's you fill in the fourth to be 1. For
example, if a11=a13=a61=1 and a63=0,
you change a63 to 1. Show how to determine quickly when
you fill in all entries of A to be 1. Hint: A certain bipartite graph
has to be connected.