2018-04-25
Apr 25 In-Class Exercise Thread .
Posts your solutions to the Apr 25 In-Class Exercise to this thread.
Best,
Chris
Posts your solutions to the Apr 25 In-Class Exercise to this thread.
Best,
Chris
Instance of Subset-Sum
1000 100 = v1
1000 010 = v1'
0100 100 = v2
0100 011 = v2'
0010 001 = v3
0010 010 = v3'
0001 001 = v4
0001 100 = v4'
0000 100 = s1
0000 200 = s1'
0000 010 = s2
0000 020 = s2'
0000 001 = s3
0000 002 = s3'
1111 444
v1+v2'+v3'+v4'+s1'+s2'+s3+s3' = 1111 444
corresponds to x1 true, x2 false, x3 false, x4 false
(Edited: 2018-04-25) Instance of Subset-Sum
1000 100 = v1
1000 010 = v1'
0100 100 = v2
0100 011 = v2'
0010 001 = v3
0010 010 = v3'
0001 001 = v4
0001 100 = v4'
0000 100 = s1
0000 200 = s1'
0000 010 = s2
0000 020 = s2'
0000 001 = s3
0000 002 = s3'
1111 444
v1+v2'+v3'+v4'+s1'+s2'+s3+s3' = 1111 444
corresponds to x1 true, x2 false, x3 false, x4 false
| ! - | x1 | x2 | x3 | x4 | C1 | C2 | C_3 |
|---|---|---|---|---|---|---|---|
| v_1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| v_1' | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| v_2 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| v_2' | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| v_3 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| v_3' | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| v_4 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| v_4' | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| s_1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| s_1' | 0 | 0 | 0 | 0 | 2 | 0 | 0 |
| s_2 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| s_2' | 0 | 0 | 0 | 0 | 0 | 2 | 0 |
| s_3 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| s_3' | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| - | 1 | 1 | 1 | 1 | 4 | 4 | 4 |
let x1 = false, x2 = true, x3 = false, x4 = true
Then we pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' which will give 1111 444
(Edited: 2018-04-25) {|
|-
!! - !! x_1 !! x_2 !! x_3 !! x_4 !! C_1 !! C_2 !! C_3
|-
| v_1|| 1 || 0 || 0 || 0 || 1 || 0 || 0
|-
| v_1'|| 1 || 0 || 0 || 0 || 0 || 1 || 0
|-
| v_2|| 0 || 1 || 0 || 0 || 1 || 0 || 0
|-
| v_2'|| 0 || 1 || 0 || 0 || 0 || 1 || 1
|-
| v_3|| 0 || 0 || 1 || 0 || 0 || 0 || 1
|-
| v_3'|| 0 || 0 || 1 || 0 || 0 || 1 || 0
|-
| v_4 || 0 || 0 || 0 || 1 || 0|| 0 || 1
|-
| v_4' || 0 || 0 || 0 || 1 || 1|| 0 || 0
|-
| s_1 || 0 || 0|| 0|| 0|| 1|| 0|| 0
|-
| s_1'|| 0|| 0|| 0|| 0|| 2|| 0|| 0
|-
| s_2 || 0|| 0|| 0|| 0|| 0|| 1|| 0
|-
| s_2' || 0|| 0|| 0|| 0|| 0|| 2||0
|-
| s_3 || 0|| 0|| 0|| 0|| 0|| 0|| 1
|-
| s_3' || 0|| 0|| 0|| 0|| 0|| 0||2
|-
| - || 1|| 1|| 1|| 1|| 4|| 4 || 4
|}
let x1 = false, x2 = true, x3 = false, x4 = true
Then we pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' which will give 1111 444
x1 x2 x3 x4 C1 C2 C3
v1 = 1 0 0 0 1 0 0
v1'= 1 0 0 0 0 1 0
v2 = 0 1 0 0 1 0 0
v2'= 0 1 0 0 0 1 1
v3 = 0 0 1 0 0 0 1
v3'= 0 0 1 0 0 1 0
v4 = 0 0 0 1 0 0 1
v4'= 0 0 0 1 1 0 0
s1 = 0 0 0 0 1 0 0
s1'= 0 0 0 0 2 0 0
s2 = 0 0 0 0 0 1 0
s2'= 0 0 0 0 0 2 0
s3 = 0 0 0 0 0 0 1
s3'= 0 0 0 0 0 0 2
1 1 1 1 4 4 4
x1 = false; x2 = false; x3 = false; x4 = false
variables = v1', v2', v3', v4', s1, s1', s2, s3, s3'
(Edited: 2018-04-25)
x1 x2 x3 x4 C1 C2 C3
v1 = 1 0 0 0 1 0 0
v1'= 1 0 0 0 0 1 0
v2 = 0 1 0 0 1 0 0
v2'= 0 1 0 0 0 1 1
v3 = 0 0 1 0 0 0 1
v3'= 0 0 1 0 0 1 0
v4 = 0 0 0 1 0 0 1
v4'= 0 0 0 1 1 0 0
s1 = 0 0 0 0 1 0 0
s1'= 0 0 0 0 2 0 0
s2 = 0 0 0 0 0 1 0
s2'= 0 0 0 0 0 2 0
s3 = 0 0 0 0 0 0 1
s3'= 0 0 0 0 0 0 2
1 1 1 1 4 4 4
x1 = false; x2 = false; x3 = false; x4 = false
variables = v1', v2', v3', v4', s1, s1', s2, s3, s3'
<nowiki>
φ=C1∧C2∧C3 where,
C1=(x1∨x2∨¬x4), C2=(¬x1∨¬x2∨¬x3), and C3=(¬x2∨x3∨x4).
v_1 1 0 0 0 1 0 0
v_1' 1 0 0 0 0 1 0
v_2 0 1 0 0 1 0 0
v_2' 0 1 0 0 0 1 1
v_3 0 0 1 0 0 0 1
v_3' 0 0 1 0 0 1 0
v_4 0 0 0 1 0 0 1
v_4' 0 0 0 1 1 0 0
s_1 0 0 0 0 1 0 0
s_1' 0 0 0 0 2 0 0
s_2 0 0 0 0 0 1 0
s_2' 0 0 0 0 0 2 0
s_3 0 0 0 0 0 0 1
s_3' 0 0 0 0 0 0 2
If x1 = false, x2 = true, x3 = false, x4 = true Then we pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' which will give 1111 444
</nowiki>
<nowiki>
φ=C1∧C2∧C3 where,
C1=(x1∨x2∨¬x4), C2=(¬x1∨¬x2∨¬x3), and C3=(¬x2∨x3∨x4).
v_1 1 0 0 0 1 0 0
v_1' 1 0 0 0 0 1 0
v_2 0 1 0 0 1 0 0
v_2' 0 1 0 0 0 1 1
v_3 0 0 1 0 0 0 1
v_3' 0 0 1 0 0 1 0
v_4 0 0 0 1 0 0 1
v_4' 0 0 0 1 1 0 0
s_1 0 0 0 0 1 0 0
s_1' 0 0 0 0 2 0 0
s_2 0 0 0 0 0 1 0
s_2' 0 0 0 0 0 2 0
s_3 0 0 0 0 0 0 1
s_3' 0 0 0 0 0 0 2
If x1 = false, x2 = true, x3 = false, x4 = true Then we pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' which will give 1111 444
</nowiki>
<nowiki>
x1 x2 x3 x4 c1 c2 c3
v1 1 0 0 0 1 0 0
v1' 1 0 0 0 0 1 0
v2 0 1 0 0 1 0 0
v2' 0 1 0 0 0 1 1
v3 0 0 1 0 0 0 1
v3' 0 0 1 0 0 1 0
v4 0 0 0 1 0 0 1
v4' 0 0 0 1 1 0 0
s1 0 0 0 0 1 0 0
s1' 0 0 0 0 2 0 0
s2 0 0 0 0 0 1 0
s2' 0 0 0 0 0 2 0
s3 0 0 0 0 0 0 1
s3' 0 0 0 0 0 0 2
t 1 1 1 1 4 4 4
let x1 = false, x2 = true, x3 = false, x4 = true
and pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' = gives 1111 444
</nowiki>
(Edited: 2018-04-25) <nowiki>
x1 x2 x3 x4 c1 c2 c3
v1 1 0 0 0 1 0 0
v1' 1 0 0 0 0 1 0
v2 0 1 0 0 1 0 0
v2' 0 1 0 0 0 1 1
v3 0 0 1 0 0 0 1
v3' 0 0 1 0 0 1 0
v4 0 0 0 1 0 0 1
v4' 0 0 0 1 1 0 0
s1 0 0 0 0 1 0 0
s1' 0 0 0 0 2 0 0
s2 0 0 0 0 0 1 0
s2' 0 0 0 0 0 2 0
s3 0 0 0 0 0 0 1
s3' 0 0 0 0 0 0 2
t 1 1 1 1 4 4 4
let x1 = false, x2 = true, x3 = false, x4 = true
and pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' = gives 1111 444
</nowiki>
2018-04-28
Given :
φ=C1∧C2∧C3 where C1=(x1 ∨ x2 ∨ ¬x4), C2=(¬x1 ∨ ¬x2 ∨ ¬x3), and C3=(¬x2 ∨ x3 ∨ x4)
x1 x2 x3 x4 C1 C2 C3
v1 = 1 0 0 0 1 0 0
v1'= 1 0 0 0 0 1 0
v2 = 0 1 0 0 1 0 0
v2'= 0 1 0 0 0 1 1
v3 = 0 0 1 0 0 0 1
v3'= 0 0 1 0 0 1 0
v4 = 0 0 0 1 0 0 1
v4'= 0 0 0 1 1 0 0
s1 = 0 0 0 0 1 0 0
s1'= 0 0 0 0 2 0 0
s2 = 0 0 0 0 0 1 0
s2'= 0 0 0 0 0 2 0
s3 = 0 0 0 0 0 0 1
s3'= 0 0 0 0 0 0 2
1 1 1 1 4 4 4
Solution : v1+v2'+v3'+v4'+s1'+s2'+s3+s3'
x1 = true
x2 = false
x3 = false
x4 = false
Given :
φ=C1∧C2∧C3 where C1=(x1 ∨ x2 ∨ ¬x4), C2=(¬x1 ∨ ¬x2 ∨ ¬x3), and C3=(¬x2 ∨ x3 ∨ x4)
x1 x2 x3 x4 C1 C2 C3
v1 = 1 0 0 0 1 0 0
v1'= 1 0 0 0 0 1 0
v2 = 0 1 0 0 1 0 0
v2'= 0 1 0 0 0 1 1
v3 = 0 0 1 0 0 0 1
v3'= 0 0 1 0 0 1 0
v4 = 0 0 0 1 0 0 1
v4'= 0 0 0 1 1 0 0
s1 = 0 0 0 0 1 0 0
s1'= 0 0 0 0 2 0 0
s2 = 0 0 0 0 0 1 0
s2'= 0 0 0 0 0 2 0
s3 = 0 0 0 0 0 0 1
s3'= 0 0 0 0 0 0 2
1 1 1 1 4 4 4
Solution : v1+v2'+v3'+v4'+s1'+s2'+s3+s3'
x1 = true
x2 = false
x3 = false
x4 = false
2018-04-29
x1 x2 x3 x4 C1 C2 C3
v1 1 0 0 0 1 0 0
v1' 1 0 0 0 0 1 0
v2 0 1 0 0 1 0 0
v2' 0 1 0 0 0 1 1
v3 0 0 1 0 0 0 1
v3' 0 0 1 0 0 1 0
v4 0 0 0 1 0 0 1
v4' 0 0 0 1 1 0 0
s1 0 0 0 0 1 0 0
s1' 0 0 0 0 2 0 0
s2 0 0 0 0 0 1 0
s2' 0 0 0 0 0 2 0
s3 0 0 0 0 0 0 1
s3' 0 0 0 0 0 0 2
1 1 1 1 4 4 4
Let x1 = T x2 = F x3 = T x4 = T
Pick v1 + v2' + v3 + v4 + s1' + s2'+ s3 + s3' = 1111 444
x1 x2 x3 x4 C1 C2 C3
v1 1 0 0 0 1 0 0
v1' 1 0 0 0 0 1 0
v2 0 1 0 0 1 0 0
v2' 0 1 0 0 0 1 1
v3 0 0 1 0 0 0 1
v3' 0 0 1 0 0 1 0
v4 0 0 0 1 0 0 1
v4' 0 0 0 1 1 0 0
s1 0 0 0 0 1 0 0
s1' 0 0 0 0 2 0 0
s2 0 0 0 0 0 1 0
s2' 0 0 0 0 0 2 0
s3 0 0 0 0 0 0 1
s3' 0 0 0 0 0 0 2
1 1 1 1 4 4 4
Let x1 = T x2 = F x3 = T x4 = T
Pick v1 + v2' + v3 + v4 + s1' + s2'+ s3 + s3' = 1111 444
Given : φ=C1∧C2∧C3
where C1=(x1 ∨ x2 ∨ ¬x4), C2=(¬x1 ∨ ¬x2 ∨ ¬x3), C3=(¬x2 ∨ x3 ∨ x4)
x1 x2 x3 x4 C1 C2 C3
v1 1 0 0 0 1 0 0
v1' 1 0 0 0 0 1 0
v2 0 1 0 0 1 0 0
v2' 0 1 0 0 0 1 1
v3 0 0 1 0 0 0 1
v3' 0 0 1 0 0 1 0
v4 0 0 0 1 0 0 1
v4' 0 0 0 1 1 0 0
s1 0 0 0 0 1 0 0
s1' 0 0 0 0 2 0 0
s2 0 0 0 0 0 1 0
s2' 0 0 0 0 0 2 0
s3 0 0 0 0 0 0 1
s3' 0 0 0 0 0 0 2
1 1 1 1 4 4 4
Solution : v1+v2'+v3'+v4'+s1'+s2'+s3+s3'
Hence x1 = true x2 = false x3 = false x4 = false
(Edited: 2018-04-29) Given : φ=C1∧C2∧C3
where C1=(x1 ∨ x2 ∨ ¬x4), C2=(¬x1 ∨ ¬x2 ∨ ¬x3), C3=(¬x2 ∨ x3 ∨ x4)
x1 x2 x3 x4 C1 C2 C3
v1 1 0 0 0 1 0 0
v1' 1 0 0 0 0 1 0
v2 0 1 0 0 1 0 0
v2' 0 1 0 0 0 1 1
v3 0 0 1 0 0 0 1
v3' 0 0 1 0 0 1 0
v4 0 0 0 1 0 0 1
v4' 0 0 0 1 1 0 0
s1 0 0 0 0 1 0 0
s1' 0 0 0 0 2 0 0
s2 0 0 0 0 0 1 0
s2' 0 0 0 0 0 2 0
s3 0 0 0 0 0 0 1
s3' 0 0 0 0 0 0 2
1 1 1 1 4 4 4
Solution : v1+v2'+v3'+v4'+s1'+s2'+s3+s3'
Hence x1 = true x2 = false x3 = false x4 = false
x1 x2 x3 x4 C1 C2 C3
v1 = 1 0 0 0 1 0 0
v1'= 1 0 0 0 0 1 0
v2 = 0 1 0 0 1 0 0
v2'= 0 1 0 0 0 1 1
v3 = 0 0 1 0 0 0 1
v3'= 0 0 1 0 0 1 0
v4 = 0 0 0 1 0 0 1
v4'= 0 0 0 1 1 0 0
s1 = 0 0 0 0 1 0 0
s1'= 0 0 0 0 2 0 0
s2 = 0 0 0 0 0 1 0
s2'= 0 0 0 0 0 2 0
s3 = 0 0 0 0 0 0 1
s3'= 0 0 0 0 0 0 2
1 1 1 1 4 4 4
Let x1 = false, x2 = true, x3 = false, x4 = true .
Then we pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' = 1111 444
x1 x2 x3 x4 C1 C2 C3
v1 = 1 0 0 0 1 0 0
v1'= 1 0 0 0 0 1 0
v2 = 0 1 0 0 1 0 0
v2'= 0 1 0 0 0 1 1
v3 = 0 0 1 0 0 0 1
v3'= 0 0 1 0 0 1 0
v4 = 0 0 0 1 0 0 1
v4'= 0 0 0 1 1 0 0
s1 = 0 0 0 0 1 0 0
s1'= 0 0 0 0 2 0 0
s2 = 0 0 0 0 0 1 0
s2'= 0 0 0 0 0 2 0
s3 = 0 0 0 0 0 0 1
s3'= 0 0 0 0 0 0 2
1 1 1 1 4 4 4
Let x1 = false, x2 = true, x3 = false, x4 = true .
Then we pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' = 1111 444
(c) 2026 Yioop - PHP Search Engine