[PDF] Homework 11 Solutions

View - Download Homework 11 Solutions

Previous PDF

Next PDF

CS 341: Foundations of Computer Science II

Prof. Marvin Nakayama

Homework 11 Solutions

1.

Answ ereac hpart TR UEor F ALSE.

(a)2n=O(n). TRUE. We can see this by lettingc= 2, and noting that2n cn= 2nfor alln1. Thus, the denition of big-O holds forc= 2and n 0= 1. (b)n2=O(n). FALSE. For it to be true, we would need that there exist positive constantscandn0such thatn2cnfor allnn0. By dividing both sides byn, we see that \n2cnfor allnn0" is true if and only if \ncfor all nn0" is true, but clearly there cannot exist constantscandn0for which the last statement is true. (c)n2=O(nlog2n). FALSE. To see why, note thatn2=O(nlog2n)if and only if there exist positive constantscandn0such thatn2cnlog2nfor all nn0, which holds if and only if n

2nlog2ncfor allnn0:(1)

By cancelling out annfrom the numerator and denominator, we can rewrite equation (1) asn=(log2n)cfor allnn0. Writingn=n1=2n1=2, we see that the last statement is true if and only if[n1=2=(logn)]2cfor allnn0. But because we know thatlogn=o(n1=2), we have thatn1=2=(logn)! 1as n! 1, so[n1=2=(logn)]2ccannot be true for allnn0for any constant c. (d)nlogn=O(n2). TRUE. Becauselogn=O(n), there exist positive constants candn0such thatlogncnfor allnn0. Multiplying both sides byngives nlogncn2for allnn0for the same positive constantscandn0, so nlogn=O(n2). (e)3n=O(2n). FALSE. Suppose that it were true. Then there exists constantsc andn0such that3nc2nfor allnn0. The last requirement is equivalent to (3=2)ncfor allnn0. However,(3=2)n! 1asn! 1, so(3=2)nc cannot be true for allnn0for any constantc. (f)3n= 2O(n). TRUE because3n= 2nlog23= 2O(n). (g)22n=O(22n). TRUE. Any functionf(n)isO(f(n)). 1

2.Let b >1be a constant. Show thatO(t(n))O(bt(n)) = 2O(t(n)).

Answer:Letf1(n) =O(t(n))andf2(n) =O(bt(n)), so we want to show that f

1(n)f2(n) = 2O(t(n)). Becausef1(n) =O(t(n)), there exist constantsc1andn1

such thatf1(n)c1t(n)for allnn1. Becausef2(n) =O(bt(n)), there exist constantsc2andn2such thatf2(n)c2bt(n)for allnn2. Consequently, letting c

0=c1c2, we get

f

1(n)f2(n)c0t(n)bt(n)

for allnn0max(n1;n2). Now recall thatx= 2log2(x)for anyx, so c

0t(n)bt(n)= 2log2(c0t(n)bt(n))

= 2 log2(c0)+log2(t(n))+t(n)log2(b) = 2

O(t(n))

becauselog2(t(n)) =O(t(n)). 3. (a)

Sho wtha tP is closed under union.

Answer:Suppose that languageL12P and languageL22P. Thus, there are polynomial-time TMsM1andM2that decideL1andL2, respectively. Speci- cally, suppose thatM1has running timeO(nk1), and thatM2has running time O(nk2), wherenis the length of the inputw, andk1andk2are constants. A Turing machineM3that decidesL1[L2is the following: M

3=\On inputw:

1.RunM1with inputw. IfM1accepts,accept.

2.RunM2with inputw. IfM2accepts,accept.

Otherwise,reject."

Thus,M3acceptswif and only if eitherM1orM2(or both) acceptsw. The running time ofM3isO(nk1)+O(nk2) =O(nmax(k1;k2)), which is still polyno- mial inn; i.e., the sum of two polynomials is also polynomial. Thus, the overall running time ofM3is also polynomial. (b)

S howthat P is closed under concatenation.

Answer:Suppose that languageL12P and languageL22P. Thus, there are polynomial-time TMsM1andM2that decideL1andL2, respectively. Speci- cally, suppose thatM1has running timeO(nk1), and thatM2has running time O(nk2), wherenis the length of the input, andk1andk2are constants. A Turing machineM3that decides the concatenationL1L2is the following: M

3=\On inputw=a1a2an, with eachai2a symbol:

1.Fori= 0;1;2;:::;n, do

2.RunM1with inputw1=a1a2ai, and

runM2with inputw2=ai+1ai+1an.

If bothM1andM2accept,accept.

3.If none of the iterations in Stage 2 accept,reject."

2 The TMM3checks every possible way of splitting the inputwinto two partsw1 andw2, and checks if the rst partw1is accepted byM1(i.e.,w12L1) and the second partw2is accepted byM2(i.e.,w22L2), so thatw1w22L1L2. Suppose that the inputwtoM3has lengthjwj=n. Stage 2 is executed at most n+ 1times. Each time Stage 2 is executed,M1andM2are run on stringsw1 andw2withjw1j jwj=nandjw2j jwj=n. Thus, runningM1onw1 takesO(nk1)time, and runningM2onw2takesO(nk2)time, so Stage 2 runs in timeO(nk1) +O(nk2) =O(nmax(k1;k2)), which is polynomial inn. Because Stage 2 is executed at mostn+1times, we get that the time complexity ofM3is O(n+ 1)O(nmax(k1;k2)) =O(n1+max(k1;k2)), which is polynomial inn. Hence, the overall running time ofM3is polynomial inn. (c)

Sho wthat P is closed under complemen tation.

Answer:Suppose that languageL12P, so there is a polynomial-time TMM1 that decidesL1. A Turing machineM2that decidesL

1is the following:

M

2=\On inputw:

1.RunM1with inputw.

IfM1accepts,reject; otherwise,accept."

The TMM2just outputs the opposite of whatM1does, soM2decidesL 1.

BecauseM1is a polynomial-time TM, so isM2.

4. A trianglein an undirected graph is a 3-clique. Show thatTRIANGLE2P, where

TRIANGLE=fhGijGcontains a triangleg.

Answer:LetG= (V;E)be a graph with a setVof vertices and a setEof edges. We enumerate all triples(u;v;w)with verticesu;v;w2Vandu < v < w, and then check whether or not all three edges(u;v),(v;w)and(u;w)exist inE. Enumeration of all triples requiresO(jVj3)time. Checking whether or not all three edges belong toEtakesO(jEj)time. Thus, the overall time isO(jVj3jEj), which is polynomial in the length of the inputhGi. Therefore,TRIANGLE2P. Remark:Note that forTRIANGLE, we are looking for a clique of xed size3, so even though the3is in the exponent of the time bound, the exponent is a constant, so the time bound is polynomial. We could modify the above algorithm forTRIANGLE to work forCLIQUE=fhG;kijGis an undirected graph with ak-cliquegby enu- merating all collections ofkvertices, wherekis the size of the clique desired. But the number of such collections isjVj k =jVj!k!(jVj k)!=O(jVjk); so the time bound isO(jVjkkjEj), which is exponential ink. Becausekis part of the inputhG;ki, the time bound is no longer polynomial. Hence, we cannot use this algorithm to show thatCLIQUE2P. Nor does it show thatCLIQUE62P since we've only shown that one algorithm doesn't have polynomial runtime, but there might be 3 another algorithm forCLIQUEthat does run in polynomial time. However at this time, it is currently unknown ifCLIQUE2P orCLIQUE62P. BecauseCLIQUEis NP-complete, this question will be answered if anyone solves the P vs. NP problem, which is still unresolved. 5. Using the p olynomial-timealgorithm f orcon text-freelanguage recog nition(i.e., t he CYK algorithm or dynamic programming), ll out the table for stringw=abbaand CFGG: S!RT

R!TRja

T!TRjb

Answer:We start the CYK algorithm by writing an emptynntable, wheren= 4 is the length of the stringw=abbathat we want to determine if the CFGG(in

Chomsky normal form) can generate.

1 2 3 41

2 3 4 stringa b b a Note that we numbered the rows and columns, and we wrote the stringabbaalong the bottom of the table. We will ll in the table a diagonal at a time, starting with the main diagonal. Once one diagonal is lled in, we move to the diagonal directly above it. The entrytable(i;j)corresponds to the substring starting in positioniand ending in positionj, and we put intotable(i;j)those variables that we can start with to generate that substring. We start by lling in the main diagonal, which consists of the entriestable(1;1), table(2;2),table(3;3), andtable(4;4). Entrytable(1;1)corresponds to the sub- string starting in position1and ending in position1, which is the substringa. Because the given CFG is in Chomsky normal form, the only way a variable can generate this substring is if there is a rule that has this variable go directly toa. Because there is a ruleR!a, we add the variableRintotable(1;1). There are no other rules withaon the right side, so we don't add any other variables totable(1;1); hence, table(1;1) =fTg.

1 2 3 41R

2 3 4 stringa b b a 4 We now move to the main diagonal's next entry,table(2;2). This corresponds to the substring starting in position2and ending in position2, which is the substringb. The only way to generate this substring is through the ruleT!b, sotable(2;2) =fTg.

1 2 3 41R

2T 3 4 stringa b b a Similarly, for entriestable(3;3)andtable(4;4), which correspond to substringsband a, respectively, we havetable(3;3) =fTgandtable(4;4) =fRg.

1 2 3 41R

2T 3T 4R stringa b b a Now that the main diagonal is complete, we next ll in the diagonal just above it. Entrytable(1;2)corresponds to the substring starting in position1and ending in position2, which is the substringab. We can divide this substring into two shorter parts,aandb, and we see how we can generate these two shorter parts. ?For the rst parta, which starts in position1and ends in position1, we look in entrytable(1;1)to see thatRcan generate this parta. ?For the second partb, which starts in position2and ends in position2, we look in entrytable(2;2)to see thatTcan generate this partb. Now if we have a rule in which the right side pairs a variable fromtable(1;1)with a variable fromtable(2;2), then the variable on the left side of the rule can generate the current substringab. Specically, we are looking for rules whose right sides are from table(1;1)table(2;2). Sincetable(1;1) =fRgandtable(2;2) =fTg, we have thattable(1;1)table(2;2) =fRTg, so we look for rules withRTon the right side. ?For example, there is a ruleS!RT, so the variableScan generate the current substringab. To see why, consider the right sideRTof the ruleS!RT. Entrytable(1;1)tells us that theRon the right side can generatea, and entry table(2;2)tells us that theTon the right side can generateb. Thus,S)RT) ab, soScan generateab. We have now determined thatScan generate the current substringab, which starts in position1and ends in position2, so we addSintotable(1;2); hence,table(1;2) = fSg. 5

1 2 3 4

1RS 2T 3T 4R stringa b b a Now we consider the next entry in the current diagonal. This istable(2;3), which corresponds to the substring starting in position2and ending in position3, which is the substringbb. We divide this substring into two smaller parts,bandb, and we determine how we can generate these two parts. ?For the rst partb, which starts in position2and ends in position2, the entry table(2;2)tells us thatTcan generate this partb. ?For the second partb, which starts in position3and ends in position3, the entry table(3;3)tells us thatTcan generate this partb. Now if we have a rule in which the right side is fromtable(2;2)table(3;3)(i.e., the right side pairs a variable fromtable(2;2)with a variable fromtable(3;3)), then the variable on the left side of the rule can generate the current substringbb. Since table(2;2) =fTgandtable(3;3) =fTg, we havetable(2;2)table(3;3) = fTTg, so we are looking for rules that haveTTon the right side. But there are no rules withTTon the right side, so it is impossible to generate the current substring bbusing the rules of the CFG; thus, we put a dash \|" in entry(2;3)to denote that table(2;3) =;.

1 2 3 41RS

2T| 3T 4R stringa b b a Using similar reasoning for entrytable(3;4), we look for rules that have right sides fromtable(3;3)table(4;4) =fTg fRg=fTRg. Thus, we look for rules with TRon the right side, which leads us to putRandTintable(3;4), sotable(3;4) = fR;Tg.

1 2 3 41RS

2T| 3TR;T 4R stringa b b a 6 Now that the second diagonal is complete, we next ll in the diagonal just above it. Entrytable(1;3)corresponds to the substring starting in position1and ending in position3, which is the substringabb. We can divide this substring into two nonempty parts in two dierent ways:aconcatenated withbb, andabconcatenated withb.

First consider splittingabbinto partsaandbb.

?For the rst parta, which starts in position1and ends in position1, entry table(1;1) =fRgtells us thatRcan generate this parta. ?For the second partbb, which starts in position2and ends in position3, entry table(2;3) =;tells us that nothing can generate this partbb. Note thattable(1;1)table(2;3) =fRg;=;, so it is impossible to generate the current substringabbby using the splitaconcatenated withbb. Now consider the other way of splitting the current substringabbinto two parts, by concatenatingabwithb. ?For the rst partab, which starts in position1and ends in position2, entry table(1;2) =fSgtells us thatScan generate this partab. ?For the second partb, which starts in position3and ends in position3, entry table(3;3) =fTgtells us thatTcan generate this partb. Thus, if we have a rule with right side fromtable(1;2)table(3;3) =fSg fTg= fSTg, then the variable on the left side of the rule can generate the current substring abb. We are thus looking for rules with right sideST, and we add the variables on the left sides of these rules totable(1;3). In this case, there are no rules withSTon the right side, so it is impossible to generate the current substringabbusing the split that concatenatesabwithb. (Actually, we don't have to even look at the rules to determine that no rule hasSTon the right side since the start variableScannot appear on the right side of any rule because the CFG is in Chomsky normal form.) Since the other way of splittingabbasaconcatenated withbbalso was impossible, we then see it is not possible to generateabbusing the CFG, sotable(1;3) =;, which we denote with a dash.

1 2 3 41RS|

2T| 3TR;T 4R stringa b b a Let us now review how we lled in entrytable(1;3). We looked for rules that had on the right side either ?a variable fromtable(1;1)paired with a variable fromtable(2;3), i.e., a right side fromtable(1;1)table(2;3), or 7 ?a variable fromtable(1;2)paired with a variable fromtable(3;3), i.e., a right side fromtable(1;2)table(3;3). Thus, to ll in entrytable(1;3), we pair entries by going across row1and down column

3. In general, to ll in entrytable(i;j), we pair entries by going across rowiand down

columnj, i.e., we look for rules with right sides fromtable(i;i)table(i+ 1;j), or table(i;i+ 1)table(i+ 2;j), or ..., ortable(i;j1)table(n;j). Next we ll in entrytable(2;4), which corresponds to the substring starting in position

2and ending in position4, which is the substringbba. Using the observation from the

previous paragraph, we thus want to pair entries going across row2and down column

4. In particular, we look for rules with right sides from

?table(2;2)table(3;4), i.e., we pair a variable fromtable(2;2)with a variable fromtable(3;4), or ?table(2;3)table(4;4), i.e., we pair a variable fromtable(2;3)with a variable fromtable(4;4). In the rst case, sincetable(2;2) =fTgandtable(3;4) =fR;Tg, we have table(2;2)table(3;4) =fTg fR;Tg=fTR;TTg, so we look for rules with TRorTTon the right side. We nd the rulesR!TRandT!TR, so we add the variablesRandTto entrytable(2;4). There are no rules withTTon the right side, so we don't any more variables totable(2;4)at this point. In the second case,table(2;3)table(4;4) =; fRg=;, so there is no way to generate the substringbbaby the split that concatenatesbbwitha. Thus, we add no other variables to entrytable(2;4), sotable(2;4) =fR;Tgfrom theRandTin the rst case.

1 2 3 41RS|

2T|R;T

3TR;T 4R stringa b b a This completes the third diagonal, so now we move to the next diagonal. The entry table(1;4)corresponds to the substring starting in position1and ending in position

4, which is the substringabba. To determine how we can generate this substring, we

pair entries in the table by going across row1and down column4. In particular, we pair ?a variable fromtable(1;1)with a variable fromtable(2;4), or ?a variable fromtable(1;2)with a variable fromtable(3;4), or ?a variable fromtable(1;3)with a variable fromtable(4;4).

Thus, we look for rules with right sides from

8 ?table(1;1)table(2;4) =fRg fR;Tg=fRR;RTg, or ?table(1;2)table(3;4) =fSg fR;Tg=fSR;STg, or ?table(1;3)table(4;4) =; fRg=;. For any rule that has any of these right sides, we add the variable on the left of the rule to entrytable(1;4). The only rule with these possible right sides areS!RT, so we addSto entrytable(1;4).

1 2 3 41RS|S

2T|R;T

3TR;T 4R stringa b b a The table is now complete since we have lled in the upper triangle. To determine if the CFG can generate original stringabba, which is the substring starting in position

1and ending in position4, we check if the starting variableS2table(1;4). Since it

is, CFGGgenerates the stringabba. IfSwere not in the upper right corner, then the

CFG would not generate the string.

9quotesdbs_dbs17.pdfusesText_23

[PDF] p ? q is logically equivalent to

[PDF] p ? q ? p ? q

[PDF] p(anb) formule

[PDF] p (q p) is equivalent to

[PDF] p toluene diazonium chloride

[PDF] p value excel

[PDF] p.c. sharma machine design pdf

[PDF] p.o. box 188004 chattanooga

[PDF] p.o. box 5008 brentwood

[PDF] p100 mask

[PDF] p2p car sharing business model

[PDF] p65warnings

[PDF] p7 design and implement a security policy for an organisation

[PDF] p7zip command line

[PDF] pa 1040 form 2019 pdf