M426 Homeworks

Week 1

1. Primitive shift register Read section 1 and do problems 1,2,3.

2. Redraw map on handout sheet so that face f is the outside face.

3. There are n people at a party where each person knows four other people except the host who knows everyone.  What can you say about the number of people at the party?

4. Create circuit diagrams and truth tables for logic functions given in class using "the form".

5. Count edges, vertices,and faces for a picture frame and check the formula F+V-E (Note: edges cross only at vertices and faces must be deformable to disks, i.e., the annulus interior to two concentric circles is not considered to be a face.)

6. Find F,V, and E for the polyhedra given by 4.6.8 and 5.4.3.4.  Note: 4.6.8 means that incident to each vertex is a square (4), hexagon (6), and octagon (8).

Week 2

1. By considering the dual polyhedra as I did in class find how many squares, hexagons and octagons make up the 26 faces of 4.6.8.

2. Show  ((p->q)and((q->r))->(p->r) is a tautology by using the new logic system.

3. Read section 2 of Primitive Shift Register and do problems 6-10.

4. Do Symmetry Worksheet-2

5. There are six people at a part where every pair of people is either a friend or an enemy.  The claim is that their are three people who are either mutual friends or mutual enemies.  Show that this is true by trying to color the edges of  the complete graph K6 using two colors (i.e., blue for friend and red for enemy).  Show that there will always be at least one red triangle or one blue triangle. Also prove that for K3, K4, and K5 there are some colorings that do not have a red or blue triangle.  Since K6 is the minimal complete graph with this property the Ramsey number of (3,3) is said to equal 6 or as we say R(3,3)=6. If you made sense of this try to prove that R(2,7)=7.

6. Draw a map in the plane that needs four colors to color it.

Week 3

1. Do three logic problems given in class.

2. Fish tank problem (from handout)

3. Draw K5 as a planar graph on a period torus (a torus cut open to a rectangle).

4. Draw K5 and K3,3 with only 1 crossing edge.

4. Do three graph isomorphism problems from handout.

5. Draw sprouts map.  Draw the dual map.  What are the fewest colors needed to color either the faces of the original map or the vertices of the dual map.  Remeber a dual map has a vertex within each face of the original and paired edges.

6. Do these problems from Rosen 5th edition:  555/19-23, 26,27.  Do not hand these problems in.

7. Symmetry Workshop - 3 is due next Monday.

8. Use the equation in Excercise 7 of the Primitive Shiift Register module (PSR) to modify Figure 3 by adding the clock.  Also read Primitive Shift Register through Section 2 and ask questions if you are not clear about something. 

2/5/04

1. Do logic circuit problem stated in class. Show that (0,1,0) is a balanced state. Show that if a=1 then the circuit changes a back to 0, i.e., if a is tuned on then it turns off.

2. I had a problem in class proving that the mark followed by p equals the mark.  Can you prove this?  (When I returned to my office I figured it out.).

3. Symmetry Worksheet 3

4. Use the recursion relations in Theorem 1 and 2 stated in class to prove that R(3,4)=9.  Please note that Theorem 2 was incorrectly stated.  It should be:  If i ≤  3 and j ≤ 3 and R(i-1,j) and Ri,j-1) are even then R(i,j) ≤ R(i-1,j) + R(i,j-1) -1  [I stated incorrectly that i,j are even].   Use this theorem to prove that R(3,4)≤9 and then show that there is a two coloring of the edges of K8 that violates the Ramsey condition.

5. Read Section 3.1 of the Primitive Shift Register (PSR) and do problems 11-16.  I just noticed that these problems are a good review and should be doable in about 3 minutes if you have been following what I have been saying about this topic.  The solutions require no calculations.

6. Note: The edges of a tesseract correspond to the two element reductions of of the K-maps for four simple statements p,q,r,s; the faces are the 4 step reductions, the 3-D cubes are the 8-step reductions and if all 16 vertices are colored you have a tautology.  Use this information to color the vertices of a cube corresponding to the logic function :  q + pq' + p' qr  where + means "or" multiplication means "and" and ' means "not".  Remember, a single statement (e.g., p) corresponds to a face, a pair of  statements (e.g., pq') correspond to an edge while a three statements (e.g., p'qr) correspond to a vertex of the cube.

Week 4

1. For the automaton that I discussed today show that if we begin with z=1 in state A and then change to z=0, the state transforms to B if we wait long enough.  Compute the sequence of transitions from A to B.

2. Symmetry Worksheet-4  Due Feb. 16.

3. Primitive Shift Registers - Read Section 3.2   Do Problems: 17, 18.

4. Challenge:  Prove that R(3,5)≤14 and that there is not graph K13 with red K3 and blue K5 so that R(3,5)=14.  Extra credit.

5. Review Dijkstra's algorithm.  Make sure that you understand how the handout that I began discussing in class works.  I also gave out a handout on Critical path analysis on the first day of class.  Please bring it to class and if you have chance begin looking at it.

2/12

1. Read Section 3.3 - 19-22  You will have to review how to divide a polynomial by a polynomial.

2. Find F,E,V for 4.6.6.  Also use duality to find the number of squares and hexagons for this polyhedron (a truncated octoahedron)

3. Examine the logic function F = <<F>F>   (note: I am using <  >  to represent the "form". Draw the circuit.  Does it have any balanced states.  Why is this function odd?  What do you observe about it?

4. Do the assigned Dijksta's algorithm problem on bottom of the the handout.

5. Do 601/3 from Rosen.  Also apply Kruskal's algorithm to this graph to find the tree with the smallest weight.  How does it compare to the tree you get from Dijkstra's algorithm?

6. Read the critical path algorithm in the weighted graph handout.

Week 5

1. For the directed graph in Figure 1 on page 9 of the Minimum distance through a weighted graph handout find a) the critical path, b0 the least time through the network (length of the maximum pat through the network) using the algorithm we discussed in class;  c) find the earliest and latest times to accomplish the tasks not on the critical path.

2. Read pages 1 and 2 for an alternative way to solve minimum paths through a network pertaining to Figure 1 on page 9.  Notice that you must solve this problem by iterations.  This is unavoidable.  Why?

3. From primitive shift register paper, read Section 4.1 and do problems 23-25 - Due Feb. 23

2/19

1. Find the final Hedetenmi matrix (see Shortest Path handout)  for the weighted graph in 601/2 of rosen (5th Edition) or pg498/2 (4th Edition).  Use the matrix to find the shortest path from v_a to

2. Do Symmetry Worksheet - 5 .  Add the following problem 3: For each pattern find the subgroup of the transformation group that keeps the pattern invariant.

3. Read the Chinese Postman Chapter. 

Week 6

1. Read the Chinese Postman Chapter and do exercises: 2,3,4,7

2. How many distinct colorings of a 2x2 square using two colors are there if two patterns are considered identical if they are transformations of each by rotations only not reflections, i.e., the rotational symmetry group of a square {e,a,a2,a3}.

3. If a rectangle is tiled by four congruent rectangles, how many distinct two-colorings are there. Two patterns are considered identical one is a transformation of the other under the symmetry group of a rectangle, i.e., G = {e,a,b,c}.

4. (Due next Monday) There are 23 distinct standard tic-tac-toe patterns if two patterns are considered distinct if one is a transformation of the other under an element of the symmetry group of the square including rotations and reflections?  In other words there are 23 different trajectories or orbits. Verify this by a computations.  Also find the order of the orbits of the following two patterns?:

                  x  x  o                   and           x  x  o

                  0 x x                                     o x o

                  o o x                                     x o x

2/26

1. Problem above was misstated.  There are 23 tic-tac-toe patterns with 5 x's and 4 o's as the Burnside - Polya Chapter shows.  I would lie you the total number of tic-tac-toe patterns possible with any number of crosses.  Then use the method that I showed in class to find the number of distinct patterns that have 3 x's and 6 o's.

2. Use the template that I handed out in class to construct a dodecahedron.  then determine the cycle symbol for the 60 rotation transformations of the rotation group of the dodecahedron.  for example I showed in class that a typical symbol for each of the 24 5-fold rotation transformations is t₅²t₁.  If you are able to do this then use it to determine the number of colorings of a dodecahedron with 1,2, or 3 colors ( a big number).  For extra credit try to find the number of colorings that have exactly 2 blues, 4 reds and 6 greens using the method that I showed in class (answer is 262).

3. Read Section 4.2 and 4.3 of the Primitive Shift Register and do problem 23.

4. Read pages 650-652 of Rosen 5th edition about Huffman trees and do 656/19, 20, 22, 23

 Week 7

1. Use Huffman coding to encode these symbols with given frequencies:  A:0.10, B: 0.25, C: 0.05, D: 0.15, E:0.30, F:0.07, G:0.08.  What is the average number of its bits required to encode a symbol?

2. Do 4th Edition 561/9,20,28,32   546/2,4,5     For 5th Edition: 656/2,4,5  673/9,18,24

3. In subgraph Enumeration chapter do: Problems: 4,9,14

Note:  The number of colorings of the dodecahedron with 2 reds, 4 blues, and 6 greens is actually 246 rather than 262 as I misstated above.  My apologies.  Congratulations to Daniel Rodrigues who computed the correct result.

3/4

1. Due Monday March 9:  Primitive Shift Register - Read Section 4.4 up to Exercise 31 on page 21 and do problems: 27-33.

2. Read the chapter on Network flows and try to do:  Exercise 1 (good luck!)

3. Verify that there are 246 distinct ways to color a dodecahedron with 2 reds, 4 blues, and 6 greens faces.

Week 8

1. Network flow handout: problem: 5, 8

2. Complete the Primitive shift register module and do problems:  34-37  Due March 25

Take home exam is due on Monday March 22.  The computer program is due on March 25.  If you have any questions you should send them to my home e-mail at: kappraff@aol.com  Have a spring break.

Week 9

Exercise from the Stirling Number handout:

1-4,6,7,8,9*,12,13,14*,16,17,18**  Due next Thursday

Note * means hard problem, ** means very hard problem.  Definitely look at problem number 18 since it is quite interesting.

Read the chapter on Stirling numbers and start looking at the chapter on Catalan numbers in the handout.  This will be our next topic.

Week 10

For slant diagonals of 1, 11, 111, 1111, 11111 dtermine the series generated by these diagonals and the polynomials that generate these series. 

4/1

1. Show that the relation :  g1 R g2  iff  g1 = h g2 for h a member of subgroup H, partitions the group G where G is the group of transformation of a square and H is the subgroup, D1 = {e, rho 1).  Since D1 has two elements the partition has 4 subsets.  Color each of the 8 sectors of the square one of four colors depending on the transformation in each of the four subsets of the partition (cosets).  Do the same if        H = { e, sigma2).

2. Find an approximation of the function e^x by using the method of divided differences for five values spaced between 0 and 1 as I stated today in class.  Compare your approximation with the actual values of e^x and the approximation from the first four terms of Taylor's series (for extra credit).

3. Stirling number handout problems 10 and 11.

Week 11

Compute a cubic polynomial approximation to sin x that goes through the points x = 0, pi/3, 2pi/3 and pi. Use the polynomial to compute the value of sin pi/4 and compare your results with the actual value and the value obtained from the cubic approximation of Taylor's theorem, i.e., sin x = x - x^3/3!

Please submit your redone computer program by Monday April 12.

Read the handout on Catalan number and also look at Sections 1 and 2 of the new handout on Finite state machines ass recognizers.

April 8

Do problems at end of Catalan numbers:  problems: 1, 2a,b, 4a,b, 5

Week 12

Do: 136/2c, 3, 4c

Extra credit: The Cayley diagram for the symmetry group of a square, D4 is a complete octagon, K8, in which each of the 7 transformations (not including the identity) corresponds to one of the 28 edges, i.e., each of the 7 transformation is represented by 4 edges.  Draw this diagram and color code the edges so that each operation has a different color.  The operations that have distinct inverses should be direced, the other edges are undirected. 

Do Exercises 1-8 from the Finite State Machine handout.

Complete the problems in the Finite State machine handout.

Do the problems on the take home exam.

Week 13

Hand in only the starred problems: Note that pages fro the 4th edition are in parentheses.

Rosen:  750 (639) /4a,b,c,10*,13,18*       764 (653) /1,9,13,14*,16*    774 (665)/2*,3,8,10*,11

4th edition: 

Extra credit if you can find the four missing Frieze symmetry groups.  Show what they do to a pattern of p's .   Try to draw the Cayley diagrams for them.

4/22

pages for the 4th edition are in parenthses.

756 (645) /1, 3a, 7, 10, 12,13

The new approach to Boolean algebra uses:

p' = 1-p

p and q = pq

p^2 = p

p or q = p + q -pq

Use this to prove the following tautologies:  hypothetical syllogism, disjunctive syllogism (see page 58  (168) Rosen.  Also prove the distributive law of addition  : r or (p and q) = (r or  q) and (r or q)

Week 13

782(673)/1,3,5,7,11,12

Use the new logic algebra to show that modus ponens is a tautology see Rosen page 58(168).

Find the stable states for the circuit with two not gates, i.e., x = <y>, y = <x> and find the stable state for :x=<x<x>>.

Read the new chapter on Petrie nets and try to do:  Problem:  1, 3, 5, 9

Use the new logic algebra to prove the distributive law for addition of logic functions, i.e.,

           prove De Morgan's laws with the new logic algebra

We will have a review session on Wednesday at 1PM in room 108 T