[comp_complex] Solutions

  • From: David Friedman <dkf@xxxxxxxxxx>
  • To: <comp_complex@xxxxxxxxxxxxx>
  • Date: Mon, 12 Apr 2004 15:55:29 -0400 (EDT)

hi everybody,

for the assignment due on Wednesday you are allowed to use a
package such as Mathematica, MatLab, etc. to do the matrix
manipulations.

Also, at the end of the first problem please write all
your answers in approximate numeric form for 1.3-1.6.


 Basic solutions for the last assignment:

 1. The simplification is all seven clauses other than:
 (~pi_1 \/ ~pi_2 \/ ~pi_3)

 anded together.

 1.1. At a minimum 1/2 of the phi_psi,r are false, and for each
 phi_psi_r there are at most 7 clauses of which at a
 minimum only one clause is false, so the minimum
 fraction of clauses that are false is
 1/14. Meaning the machine should accept if more than 13/14
 of the clauses are satisfiable, so epsilon = 1/13.


 2. To prove: w(G) = m ===> w(G^2) >= m^2

 The original clique is v_1 ... v_m   so then
 under the definition (v_1, v_1) .... (v_m, v_m) are
 all connected.

 To prove:  w(G^2) = m^2  ===> w(G) >= m

 Consider the m^2 nodes which form the clique:
              -    -
              | |  | |
  w_1    =   (| |, | |  )
  w_2    =   (| |  | |  )
  ...         | |  | |
  w_m^2  =   (| |  | |  )
               -    -

  There must be at least m distinct nodes in either the
  first column or the second column (otherwise there
  would be duplicates in the list), and all these m
  nodes are connected.

  The two statements combined prove the the theorem, (for if
  when w(G) = m  w(G^2) > m^2 would imply from the second that
  w(G) > m, and similarly the other way)


 3. This problem just asks you to show that the expression accurately
 represents the problem.






Other related posts: