EECS 3101 Winter 2019-20 – Exam
Instructor: Jeff Edmonds
1) Gray
a) Recursive
i) path friend ii) code
iii) proof
7 7 9
23
b) Iterative
i) LI
ii) Establish iii) Maintain iv) Post
v) code
4 4 9 4 4
25
c) L(s,i,t) d) Bit(i)
i) Proof ii) Code
9 5 4
18
2) Graph Colour
9
9
3) Greedy
a) Optimal b) Why
c) Time
4 9 4
17
4) Dyn Prog
a) Bird Friend b) Subinstances c) Code
d) Time
i) parameters ii) bits
4 3 11 3 3
24
5) NP
a) Sum
b) Satisfying
c) Works
d) Definitions
i) SAT to Knap ii) Knap to Sat
i) NP ii) Hard
5 4 4 4 4 4
25
6) First Order
a) Yes
b) Reduction
i) SAT ii) Knap
3 3 3
9
7) Art
c) Bonus
9 2
Total
150
161
Keep your answers short and clear.
Do not repeat the question.
20% is given to any subquestion left blank (eg 3b).
0 Academic Integrity & Remote/Online/Open Book Assessments
We all share responsibility to ensure conditions for success and upholding academic integrity. As your instructor, I am committed to:
• Communicating clearly the expectations around academic integrit
• Following up on all concerns related to breaches of academic integrity, including application of
the York University Senate Policy on Academic Honesty
(https://secretariat-policies.info.yorku.ca/policies/academic-honesty-senate-policy-on/)
Expectation Statements for Online (Open Book) Exams:
All students will receive the exam on Thurs April 16 at 10:00 am
All students will submit the exam by Friday Thurs April 17 at 10:00 am
(a) I am hoping this will meet the needs of students approved for accommodations, but if you have additional needs you are asked to communicate with me about them prior to the exam date.
(b) Students who encounter health-related or care-related challenges should advise me as soon as possible so that alternatives can be discussed
Rules for this open book exam are:
(a) The exam is to be completed in pairs or individually: Specifically, DO NOT split the questions. You need to do all the questions yourself. But you are allowed to discuss your ideas with your partner and to be supports for each other. You are not to discuss the exam with anyone except this one partner.
(b) Forum: Do not have any chat group about it other than the forum that Jeff is also reading. Jeff will try to keep up with posted question. If you are confident that it is information that Jeff would give, feel free to answer it.
1
(c) The exam is open book but NOT open to GOOGLE searches: You are allowed to read any material provided on the course web page and any material on the internet about the topics in general. Jeff will try to make the questions unique, but in case he fails, DO NOT search the internet for answers to the specific questions on the exam. And really do not ask questions on some Cheat forum.
(d) Do NOT code: My request is that you do NOT code up and run the algorithms. My goal is to teach you how to know and to prove that it works without running it.
(e) Do not Share: Please do not share the questions with anyone during or after the exam. I resent the web pages that feel they can post my tests. They are mine.
(f) Reporting: If you suspect someone is cheating, please reprimand them and insist that they stop. If it is too much or if they refuse to stop then please report them with names and evidence to me.
Academic Integrity Attestations or Pledges
By putting my name to this statement, I attest to the fact that my partner and I acted with integrity, abiding by the Senate Policy on Academic Honesty and any rules the instructor has articulated for this assessment.
Student 1 Name: __________________ Student Number:_________________Date: _____________
Student A Name: __________________ Student Number:_________________Date: _____________
1. Agraycodeisawalkalongtheedgesofann-cube. ItisalistLof n-bit strings that includes each of the 2n strings exactly once each and consecutive strings differ in exactly one bit.
You are to develop four algorithms for producing this list: a re- cursive one, a loop invariant one, a slick one that quickly maps t to L[t], and one which defines Bit(t) to be which bit needs to be flipped next.
Some Notation:
s ∈ {0, 1}n: Let s be an n-bit string.
i ∈ [1..n]: Let be an index into one of s’s bits.
Because we will sometimes be thinking of these bit strings as integers written in binary, we will have the left most bit be indexed by i = n and the right most by i = 1.
s(i): Let s(i) denote the string s with it’s ith-bit flipped. Let s(i, i−1) be s with both bits flipped.
Above is an example, when n = 4. The columns list the indexes (time) t from 0 to 2n− 1 in binary; a gray code L; and a sublist denoted L(1100, 3).
t
L(0000, 4)
L(1100, 3)
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
1100 1101 1111 1110 1010 1011 1001 1000
Eg. If s = 1110 then s(1) = 1111, s(3) = 1010, s(4) = 0110, and s(4, 3) = 0010. The code works better if we define s(0) to still be s. Because i = 0 is not actually a bit of s, this makes sense.
L: Let L be a list of n-bit strings.
t: Let t ∈ [0, .., |L|−1] be an index into the list L. L[t]: Let L[t] be the tth string in the list.
s s(3) 1110 1010
L(s, i) : Let L(s, i) be a list of n-bit strings with the following properties:
• Examples: L(0000, 4) and L(1100, 3) are listed above in the second and third columns.
L(1100,3)
s s(3) 1100 1??? 1000
2
• The list starts with the string s, i.e. L(s, i)[0] = s.
• Consecutive strings differ in exactly one bit.
• It hits each string of the form ⟨snsn−1,…,si+1,?i,?i−1,…,?1⟩ with high n−i order bits of s
unchanged and all 2i combinations of first i bits appearing exactly once.
Eg when s = 1100 and i = 3, then the 23 string can be represented by 1???.
• Hence, the number of strings in the list is |L(s, i)| = 2i.
• The list ends with the string s(i), i.e. L(s,i)[2i−1] is back to a string that is the flip of bit
ith away from the beginning s. As such this path/list could close the cycle and go back to s
if it wanted.
• A full walk along the edges of the n-cube is obtained with L(s, n) for any start string s.
(a) We will first design a simple Recursive Algorithm printing the list L(s, i).
i. Recursive Path: We will use the following diagram to denote the gray code path L(s, i) = L(10000,4) with n = 5. You are to redraw it, deconstructing it into subpaths that your recursive friends handle and edges that you handle. As seen use straight arrows to designate a step between consecutive strings that are 1 bit flip apart and wavy arrows to designate a friend’s sublist. Specify the strings along the path as shown below.
Explain your reasoning.
s 10000
L(s,i), n=5, s=10000, i=4 L(10000,4)
1????
s(i) 11000
(7 Marks. My answer has 13 sentences.)
ii. Recursive code: Write the code for L(s, i) that takes an n-bit string s and an integer i ∈ [1..n]
as input and prints out the stated sequence of 2i strings.
(7 Marks. My answer has 9 sentences.)
iii. Prove that your recursive program L(s, i):
A. Starts with s and ends with s(i).
B. Outputs 2i strings.
C. Prints all strings of the form ⟨snsn−1, . . . , si+1, ?i, ?i−1, . . . , ?1⟩ D. Every consecutive pair of strings differs in only one bit.
E. Has a good base case.
(9 Marks. My answer has 20 sentences.)
(b) The following is a second algorithm for the above problem.
algorithm L(s,i)
⟨pre−cond⟩: s is an n-bit string s and i ∈ [1..n]. ⟨post−cond⟩: Prints out the stated sequence of 2i strings.
begin
loop t = 0…2n−1
Print( L(s, i, t) ) end
end algorithm
Your task now is to write an iterative (loop invariant) program for computing L(s,i,t) which
returns the tth string in L(s, i).
i. State the loop invariant of your algorithm.
Hint: Recall the GCD algorithm on input ⟨X, Y ⟩ had the loop invariant that it has a smaller input ⟨x, y⟩ such that GCD(x, y) = GCD(X, Y ). Your loop invariant here will be the same. (4 Marks. My answer has 1 sentences.)
3
ii. Establish the Loop Invariant.
(4 Marks. My answer has 2 sentences.)
iii. Maintain the Loop Invariant. Hints:
• Each iteration of your algorithm should split the search space in half in a way similar to that of binary search.
• Unlike the bits, the list will be indexed starting from 0, i.e. t ∈ [0, .., 2i −1]. For example, it begins with L(s, i, 0) = s and ends with L(s, i, 2i −1) = s(i).
• Hence, t in binary is an i-bit string, from 000..0 to 111..1.
• Let ti be the ith bit of t, i.e. its left most bit.
If ti = 1, then then t ≥ 2i−1 and L(s,i,t) is in the second half of the list.
Notethatt(i)=t−2i−1 istwiththeith bitzeroed.
• Usethenotations,iandtvss′,i′ andt′.
(9 Marks. My answer has 20 sentences.)
iv. Obtain the postcondition.
(4 Marks. My answer has 2 sentences.)
v. Give the full code with the loop invariant.
algorithm L(S,I,T)
⟨pre−cond⟩: S is an n-bit string,I ∈ [1..n], T ∈ [0..2I −1] ⟨post−cond⟩: Returns the Tth string in L(S,I).
begin
(4 Marks. My answer has 12 sentences.)
(c) We will now develop a third algorithm for producing the list L(s, i)
that quickly maps t to L[t] in a slick way.
• It turns out that the algorithm for L(s, n, t) can be simplified to simply L(s, n, t) = s⊕t⊕⌊ t ⌋.
2
– Here s = s ⊕ t denotes the bit-wise exclusive-or of the bit string s and the bit string of t when written in binary.
– For example, consider any rows in the above table, say t = 1011 in binary. Then ⌊ t ⌋ = 101 is the same string shifted one to the right.
2
Then 1011 ⊕ 101 = 1110 which is in fact the tth string in L(0000, 4).
• Can you wave your hands a bit and see if you can argue that this does the same that your
iterative algorithm does?
• Hint: At least this is what your iterative algorithm is supposed to do.
(9 Marks. My answer has 7 sentences.)
(d) We will now develop a forth and final algorithm for producing the list L(s, i) which defines Bit(t) to be which bit needs to be flipped next.
i. This question is about defining Bit(t).
• Suppose for a minute that s = 0000000000.
• Then the last question “proved” that the tth string in the gray code is t ⊕ ⌊ t ⌋
and that the t+1st string is (t+1)⊕⌊t+1⌋. 2 2
• The means that these two strings must differ in only one bit. Denote this bit by Bit(t).
• For example, consider t = 1011.
– When transitioning from the string t = 1011 to the string t+1 = 1100,
the bits indexed by i′ ∈ [1, 2, 3] flip value.
– When transitioning from string ⌊ t ⌋ = 101 to string ⌊ t+1 ⌋ = 110,
′22 the bits indexed by i ∈ [1, 2] flip value.
4
– Whentransitioningfromstringt⊕⌊t⌋=1110to(t+1)⊕⌊t+1⌋=1010, ′22
only bit indexed by i ∈ [3] flips value. – Hence, in this case Bit(1011) = 3.
Also Bit(00000) = Bit(00010) = 1.
and Bit(00111) = Bit(10111) = 4. • Generalize these ideas to an arbitrary t
and in doing find so a quicker way of determining Bit(t) from the string t. (5 Marks. My answer has 9 sentences.)
ii. Complete the following algorithm for L(s, n). Hint: Use the result from the last question. No proofs are needed.
algorithm L(s,i)
⟨pre−cond⟩: s is an n-bit string s and i ∈ [1..n]. ⟨post−cond⟩: Prints out the stated sequence of 2i strings. begin
loop t = 0 . . . (2n)−1 Print( s )
⟨loop−invariant⟩: The 0th to tth gray code strings have been printed and s currently is the tth one.
???
??? end
end algorithm
(4 Marks. My answer has 2 sentences.)
2. Recall that the algorithm from test 2 found a 6 colouring of a graph that was promised by the precon- dition to be planar. Recall that the test stated: “Minimum Degree: A fact about every planar graph is that there is always a node u whose degree is at most five.” Does the same algorithm work if you change the precondition to promise that the input graph G has a node u whose degree is at most five? Either argue why the same algorithm works or argue why it does not.
Demonstrate with an example graph. As a reminder, here is the code.
algorithm SixColour(G)
⟨pre−cond⟩: G is a planar graph [with degree 5 or less node]. ✘
⟨post−cond⟩: C is a bichromatic six colouring of G. begin
if( G = emptyGraph )
return( emptyColouring )
else
u = NodeMinDeg(G)
G1 = DeleteN ode(G, u)
C1 = SixColour(G1)
Let c be one colour from {1,2,…6} not used in C1 to colour one of u’s
at most five neighbors N eighbors(G, u). Let C colour all the nodes in G except for u
in the same way as C1 colours G1
and let C(u) be c. return( C) )
end if end algorithm
✘ ✘
Deleting u and its adjacent edges from G.
5
(9 Marks. My answer has 4 sentences.)
3. Greedy Algorithms: Discuss (and correct) the following questions.
(a) Every step of every greedy algorithm chooses the next object to consider based on a greedy criteria and then makes an irrevocable decision about it. In what way do we say that this choice optimal? Does this guarantee that the algorithm produces an optimal solution? Use an example in your discussion.
(4 Marks. My answer has 5 sentences.)
(b) Give the details of why St−1 is changed into St?
(9 Marks. My answer has 7 sentences.)
(c) How much time does it take the algorithm to change St−1 into St?
(4 Marks. My answer has 3 sentences.)
4. Dynamic Programming:
Knapsack Problem:
Standard: You must select a subset of the n objects in the store to put in your knapsack. The total volume of the objects taken can’t exceed the volume of the knapsack. Your goal is to maximize the total price of the objects taken.
Aisled: Now the store is laid out into n aisles each with m treasures and for each aisle, you must choose exactly one treasure.
Instances: An instance consists of I = V, v⟨i,j⟩, p⟨i,j⟩ | i ∈ [n], j ∈ [m].
Here V is the total volume of the knapsack.
For i ∈ [n] and j ∈ [m], the jth treasure in the ith aisle has volume v⟨i,j⟩ and price p⟨i,j⟩.
Example:
n = 5 aisles labeled a-e and m = 2 treasures per aisle labeled Left and Right. It is just a coincidence that v⟨i,j⟩ = p⟨i,j⟩.
Solutions: A solution is S = ⟨j1, . . . , jn⟩, where for i ∈ [n], ji ∈ [m] specifies which treasure was taken from aisle i.
Example: S = ⟨1,1,1,2,1⟩ = ⟨L,L,L,R,L⟩
Total volume allowed V = 11111, Total price achieved P = 11111.
Valid: A solution is valid if the taken treasures fit into the knapsack, i.e., i∈[n] v⟨i,ji⟩ ≤ V .
Measure Of Success: The value of a solution is the total price of what is put in the knapsack, i.e. i∈[n] p⟨i,ji⟩.
6
Aisle
Left
Right
a
⟨10000, 10000⟩
⟨01001, 01001⟩
b
⟨00100, 00100⟩
⟨10000, 10000⟩
c
⟨00010, 00010⟩
⟨00101, 00101⟩
d
⟨11010, 11010⟩
⟨00000, 00000⟩
e
⟨01001, 01001⟩
⟨00110, 00110⟩
Total volume allowed V = 11111
Aisle
Treasure
a
L = ⟨10000, 10000⟩
b
L = ⟨00100, 00100⟩
c
L = ⟨00010, 00010⟩
d
R = ⟨00000, 00000⟩
e
L = ⟨01001, 01001⟩
Total
⟨11111, 11111⟩
Example: Total price achieved for this solution P = 11111.
Goal: Given the treasures in the aisles, the goal is fill the knapsack with one treasure from each aisle
with the greatest possible total price.
Example: This solution is clearly optimal P = 11111 = V . Because v⟨i,j⟩ = p⟨i,j⟩, we have that for every solution the sum price = sum volume ≤ V and hence one cannot do better than this.
In general, it would be very hard to know if a given solution is optimal.
Greedy Version: It the volume is not a constraint, then you maximize the total price i∈[n] p⟨i,ji⟩ by simply choosing the highest price object from each aisle.
Here are your questions:
(a) Bird and Friend: Consider a particular instance, V , v⟨i,j ⟩ , p⟨i,j ⟩ | i ∈ [n], j ∈ [m] to the Aisled Knapsack problem. Give an algorithm using trusted bird and friend.
Hint: A solution MUST have exactly one treasure from each aisle.
Hint: In understanding this problem, it is best not to consider each of the nm treasures as an object for which you need to decide whether or not to take it. Instead, think of each of the n aisles as being an ”object” for which you need to decide which treasure to take it.
Hint: If the solution is S = ⟨j1, . . . , jn⟩, what should you ask the bird? Hint: Is there a case in which you simply know the bird was wrong?
(4 Marks. My answer has 9 sentences.)
(b) What is the set of subinstances solved by the recursive backtracking algorithm? How many are there?
Hint: We still want a full m treasures in each aisle.
(3 Marks. My answer has 4 sentences.)
(c) Give the dynamic programming code.
(11 Marks. My answer has ? sentences.)
(d) What is the running time of your dynamic programing code?
i. What is the time in terms of V , n, and m? (3 Marks. My answer has 2 sentences.)
ii. What is the running time of your program expressed as a function of input size? (3 Marks. My answer has 2 sentences.)
5. NP Complete: Aren’t you excited to know why knapsack like problems are NP-Complete!?! See 2001-60-NP Complete.pptx Quick Reduce
The 3-unique-SAT problem is known to be NP-complete. It is defined as follows.
Input: The input consists of the AND of a number of clauses. Clause: Each clause consists of exactly three literals.
Literal: A literal is either a variable or its negation.
Example: (aor¬bord)&(¬aordore)&(bor¬cor¬e)&(cordor¬e)&(¬aor¬core) Potential Solution: A “potential” solution consists of a True/False assignment to each variable.
Example: a=T,b=T,c=T,d=F,e=T.
Valid/Satisfying: A solution is valid/satisfying iff each clause is satisfied exactly once. Example: (aor¬bord)&(¬aordore)&(bor¬cor¬e)&(cordor¬e)&(¬aor¬core)
The satisfied literals are in bold.
Each clause has exactly one such literal.
Hence, this is a valid/satisfied solution.
It witnesses/proves the fact that the given instance is a Yes instance.
Algorithm: The following is an algorithm for solving the 3-unique-SAT problem. 7
Input: Given an instance. (See above for an example.) Matrix: Form a matrix as follows:
Example:
C1 =(aor¬bord),C2 =(¬aordore),C3 =(bor¬cor¬e), C4 =(cordor¬e),&C5 =(¬aor¬core)
Variables: For each n variables have a row.
T/F: Have one column for True and a second for false.
Clauses: Break each column into a sub-column for each variable. Positive Literals: If a variable x appears un-negated in clause C,
then put a 1 in row x, column T.C. Otherwise a 0. Negative Literals: If a variable x appears negated in clause C,
then put a 1 in row x, column F.C. Otherwise a 0.
Binary Strings: Form a binary strings by concatenating the bits in each row for True/False.
Example:
Integers: Consider these strings as decimal integers (i.e. base 10). Example: 11010 + 01001 = 12011.
But we will make sure sums never have carries, eg. 17 + 28 = 45. Instance Map: Form an instance to the Aisled Knapsack Problem as follows.
Example:
Total volume allowed V = 11111,
Total price required P = 11111.
Aisles: There will be one aisle for each of the n variables/rows. Treasures per Aisle: There will be m = 2 treasures in each aisle,
i.e. True ≈ Left and False ≈ Right.
Volume/Price: For each treasure both the volume and the price will be equal to the corre-
sponding integer in our previous table.
Total Volume: Let V = 11111 be the integer formed by concatenating together a 1 for each
clause. This will be the total volume for the knapsack.
Bound on Price: Normally the Aisled Knapsack Problem returns an optimally priced so-
lution, i.e. which treasure to choose from each of the n aisles. However, our oracle is only allowed to answer Yes/No questions.
8
Var
True
False
C1
C2
C3
C4
C5
C1
C2
C3
C4
C5
a
1
0
0
0
0
0
1
0
0
1
b
0
0
1
0
0
1
0
0
0
0
c
0
0
0
1
0
0
0
1
0
1
d
1
1
0
1
0
0
0
0
0
0
e
0
1
0
0
1
0
0
1
1
0
Var
True
False
a
10000
01001
b
00100
10000
c
00010
00101
d
11010
00000
e
01001
00110
Aisle
Left
Right
a
⟨10000, 10000⟩
⟨01001, 01001⟩
b
⟨00100, 00100⟩
⟨10000, 10000⟩
c
⟨00010, 00010⟩
⟨00101, 00101⟩
d
⟨11010, 11010⟩
⟨00000, 00000⟩
e
⟨01001, 01001⟩
⟨00110, 00110⟩
Hence, this instance will be considered a Yes instance iff it has a solution whose price is
at least P = V = 11111.
Solution Map: The following is bijection between potential solutions to your instance to the 3-
unique-SAT problem and potential solutions to the corresponding Aisled Knapsack instance. SAT Solution: The first is a T/F assignment to the variables.
Example: a=T,b=T,c=T,d=F,e=T.
Knapsack Solution: For each aisle x, take the Left treasure iff the corresponding variable
is set to be True.
Example:
Total volume allowed V = 11111,
Total price achieved P = 11111.
Oracle: Ask the Aisled Knapsack Oracle this instance. She answers Yes or No depending on
whether or not there is a valid solution with price at least P = V = 11111.
Example: Note, the given valid/satisfying solution witnesses/proves the fact that the
given instance is a Yes instance.
Same Answer: Our algorithm returns the same Yes/No answer as given by the oracle.
Example:
Instance: (aor¬bord)&(¬aordore)&(bor¬cor¬e)&(cordor¬e)&(¬aor¬core). Oracle: We have seen that the given instance to Aisled Knapsack Problem is an Yes instance so
the oracle says Yes.
Algorithm: So our algorithm also says Yes.
Correct: We have seen that the given instance to 3-unique-SAT Problem is an Yes instance so
this is the correct answer.
——
Here are the questions for you to answer.
For each your answers needs to be for a general input. And you should make reference to the example at hand.
(a) Total Volume/Price: Lets try to understand the sum of the volumes/prices of the treasures taken. Here I am not assuming that either potential solutions are satisfying.
• Let i index some digit in the sum volume/price. It corresponds to clause Ci. Consider some variable/row x.
When does row x contribute 1 to the ith digit of the sum of taken treasures? i.e. what does this say about clause Ci? Explain.
• What is the ith digit of the sum of taken treasures? i.e. what does this say about clause Ci? (5 Marks. My answer has 7 sentences.)
(b) Satisfying to Satisfying:
i. 3-unique-SAT to Aisled Knapsack:
• Suppose your assignment to the variables satisfies the 3-unique-SAT instance. • What is the sum of volume/price of the taken treasures?
9
Aisle
Treasure
a
L = ⟨10000, 10000⟩
b
L = ⟨00100, 00100⟩
c
L = ⟨00010, 00010⟩
d
R = ⟨00000, 00000⟩
e
L = ⟨01001, 01001⟩
Total
⟨11111, 11111⟩
• Prove that this means that the corresponding solution satisfies the Aisled Knapsack in- stance.
(4 Marks. My answer has 5 sentences.) ii. Aisled Knapsack to 3-unique-SAT:
• Suppose the oracle gives you a solution that satisfies the Aisled Knapsack instance.
• What is the sum of volume/price of the taken treasures?
• When summing up the total volume/price (eg 11010+01001 = 12011) prove that no digit
has carries.
• Prove that this means that the corresponding solution satisfies the 3-unique-SAT problem.
(4 Marks. My answer has 8 sentences.)
(c) Algorithm works: Prove that the above algorithm answers Yes iff your instance to the 3-unique- SAT problem has satisfying solution.
(4 Marks. My answer has 5 sentences.)
(d) Definitions:
i. Prove that the Aisled Knapsack problem is in the class NP. (4 Marks. My answer has 1 sentences.)
ii. Prove that the Aisled Knapsack problem is in the class NP-Hard (and hence NP-Complete). (4 Marks. My answer has 4 sentences.)
6. First Order Logic: I believe that a very useful skill is to be able to express math concepts as first order logic statements.
eg. “Integers have negations” is expressed with ∀x ∃y x+y = 0. (a) Yes Instance:
i. Define a first order logic statement Φ3USAT (I) to state that “Instance I is a Yes instance to the 3-unique-SAT problem”.
• Let I denote an instance to 3-unique-SAT problem, namely clauses.
• Let C denote one of the clauses of I.
• Let x denote one of the variables of I.
• Let S denote a potential solution of I, namely as setting of each variables to True/False.
• Let V alid(I, C, x, S) state that when setting the variable according to S, clause C of I is
satisfied by variable x (or its negation).
• Let ∃ ̇ be an quantifier that states that some value exists uniquely.
Give this first order logic statement Φ3USAT (I).
(3 Marks. My answer has 1 sentences.)
ii. Define a first order logic statement ΦAK(I′) to state that
“Instance I′ is a Yes instance to the Aisled Knapsack problem”.
Here I′ = IM(I) is the instant map defined above.
• Let V alid′(I′, i′, x′, S′) state that when considering solution S′ of I′, row x′ contributes
a one to the i′th bit of the sum of volume/price. Give first order logic statement ΦAK(I′).
(3 Marks. My answer has 1 sentences.)
(b) Explain how the above reduction needs to prove the following: Φ=∀I [Φ3USAT(I)iffΦAK(IM(I))].
(3 Marks. My answer has 1 sentences.)
7. Bonus: Again it is 4am and I cant help but add more to this exam. But I don’t want to mark more. So do one or the other of these but not both. (Or none for 20%).
10
(a) We know that Cook proves that 3-SAT is NP-complete but suppose we don’t know that the unique version is. Also we really care about the normal Knapsack problem, not this aisle one.
Make the following changes to the SAT/Knapsack reduction:
• Drop the unique requirement on SAT, i.e. each clause can have 1, 2, or 3 of its clauses satisfied but not 0.
• Drop the aisle requirement on Knapsack, i.e. for each aisle you can take 0, 1, or 2 of its treasures.
• For the same SAT instance
C1 =(aor¬bord),C2 =(¬aordore),C3 =(bor¬cor¬e), C4 =(cordor¬e),&C5 =(¬aor¬core)
The Knapsack instance becomes
• Before the volume/price integer for each treasure had one digit indexed i for each clause Ci. Now it will also have one digit indexed j for each variable/aisle xj. For both the Left and Right treasure in this jth aisle, this jth digit will be 3 and the other j′th digits will be zero.
• For each clause Ci, add two new treasures with a 1 in the ith digit and a zero everywhere else.
• Change the required volume/price to being 3 in each of the clause digits and each of the variable digits, i.e. V = P = 33333 33333.
Now repeat 5bi and 5bii, i.e. prove that
There is a setting of the variables that satisfies each clause
iff
There is subset of the treasures that adds up exactly to V = P = 33333 33333.
(9 Marks. My answer has 14 sentences.)
(b) Don’t try this unless you have time and are amused.
Our goal is to prove Φ stated above.
It is the kind of thing that Jeff would like to teach in Math1090, but is surprised how hard it is. On the other hand, if you unwind the proof we did above, though subtle, Jeff’s proof does follow the same proof.
Believing that George would not approve of his proof technique,
he wonders how George would prove it.
How would you prove it?
Jeff’s technique to prove first order logic statements is to play a particular game.
In it who provides what and the order that they provide it is crucial.
https://www.eecs.yorku.ca/~jeff/courses/3101/ass/steps0.pdf
To make life easier for us,
• Let all our variables be integers (positive or negative).
• Let I′ = IM(I) = 5I be our Instance Map.
• Let V alid(I, C, x, S) be some strange function returning True/False.
• LetValid′(I′,i′,x′,S′)=Valid(I′,7i′,x′,S′),whenallvaluesinvolvedareintegers. 539
• Try to use Jeff’s game to prove the following: Φ = ∀I [Φ3USAT (I) ⇒ ΦAK(IM(I))].
• Hint: Assume that you have access to an oracle giving a winning strategy to play Jeff’s game associated with the statement Φ3USAT(I) and then use that to give a winning strategy to play Jeff’s game associated with the statement ΦAK(IM(I)).
11
Aisle
Left
Right
Extra
Extra
a
⟨10000 30000, 10000 30000⟩
⟨01001 30000, 01001 30000⟩
⟨10000 00000, 10000 00000⟩
⟨10000 00000, 10000 00000⟩
b
⟨00100 03000, 00100 03000⟩
⟨10000 03000, 10000 03000⟩
⟨01000 00000, 01000 00000⟩
⟨01000 00000, 01000 00000⟩
c
⟨00010 00300, 00010 00300⟩
⟨00101 00300, 00101 00300⟩
⟨00100 00000, 00100 00000⟩
⟨00100 00000, 00100 00000⟩
d
⟨11010 00030, 11010 00030⟩
⟨00010 00030, 00000 00030⟩
⟨00010 00000, 00010 00000⟩
⟨00010 00000, 00010 00000⟩
e
⟨01001 00003, 01001 00003⟩
⟨00110 00003, 00110 00003⟩
⟨00001 00000, 00001 00000⟩
⟨00001 00000, 00001 00000⟩
(9 Marks. My answer has 19 sentences.)
8. (2 marks) Art therapy question: When half done the exam, draw a picture of how you are feeling.
12