*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.

- » [comp_complex] Solutions
- » [comp_complex] Solutions
- » [comp_complex] Solutions
- » [comp_complex] Solutions
- » [comp_complex] Solutions
- » [comp_complex] Solutions
- » [comp_complex] Solutions
- » [comp_complex] Re: Solutions
- » [comp_complex] Solutions