2017-04-12

Apr 12 In-Class Exercise .

Hey Everyone,

Post your solutions to the Apr 12 In-Class Exercise here.

Best, Chris

Hey Everyone, Post your solutions to the Apr 12 In-Class Exercise here. Best, Chris

-- Apr 12 In-Class Exercise

We could encode all states of a DFA into a turing machine and move from current state to the other based on the input.

At the end of the input, if the current state we are in is the special final state, then we write 1 to the output tape. This takes 1 tape square which is within log space, L.

For correctly matched parenthesis, to recognise correctly matched pairs of parenthesis, we could count up when we see an opening parenthesis, and count down when we see a closing parenthesis.

This will take at most log space to store the count of half the length of a correctly matched pairs.

Languages recognised by a PDA use a stack which could grow at a rate linear to the input which is not contained in NL. For a language recognised by PDA to be in NL, it would have to be similar to the PATH problem where we were checking for paths of at most 2^i in length.

(Edited: 2017-04-12)

1. We could encode all states of a DFA into a turing machine and move from current state to the other based on the input. At the end of the input, if the current state we are in is the special final state, then we write 1 to the output tape. This takes 1 tape square which is within log space, L. 2. For correctly matched parenthesis, to recognise correctly matched pairs of parenthesis, we could count up when we see an opening parenthesis, and count down when we see a closing parenthesis. This will take at most log space to store the count of half the length of a correctly matched pairs. 3. Languages recognised by a PDA use a stack which could grow at a rate linear to the input which is not contained in NL. For a language recognised by PDA to be in NL, it would have to be similar to the PATH problem where we were checking for paths of at most 2^i in length.

-- Apr 12 In-Class Exercise

A DFA that accepts inputs of size n has at most n many states. We can keep track of which state a DFA is in with only log n many bits.

We can recognize the language of correctly matched parentheses of size n by tracking how many open parentheses we have found so far: incrementing when we encounter an open, and decrementing when we encounter a closed. In a string of size n matching parentheses, there will only be up to n/2 open parentheses, and in the worst case we can track them with log(n/2) bits.

Create a configuration graph for a PDA accepting some language. If this configuration graph can find a path between a start and accept state (using our NL algorithm PATH), the language is in NL.

1. A DFA that accepts inputs of size @BT@n@BT@ has at most @BT@n@BT@ many states. We can keep track of which state a DFA is in with only @BT@log n@BT@ many bits. 2. We can recognize the language of correctly matched parentheses of size @BT@n@BT@ by tracking how many open parentheses we have found so far: incrementing when we encounter an open, and decrementing when we encounter a closed. In a string of size @BT@n@BT@ matching parentheses, there will only be up to @BT@n/2@BT@ open parentheses, and in the worst case we can track them with @BT@log(n/2)@BT@ bits. 3. Create a configuration graph for a PDA accepting some language. If this configuration graph can find a path between a start and accept state (using our NL algorithm PATH), the language is in NL.

-- Apr 12 In-Class Exercise

A DFA has finite number of states, we can design the automata so that on successfully accepting the string it writes 0 to the output tape else it writes 1. This uses constant space so we can say that languages decided by DFA are in logspace

we count the number of parenthesis. incrementing when we see a opening parenthesis and decrement it when we encounter a closing parenthesis

Languages recognised by a PDA grow in linear way as they use a stack, if a CFL would be similar to the PATH problem which we defined in class then we could say that it is in NL.

1. A DFA has finite number of states, we can design the automata so that on successfully accepting the string it writes 0 to the output tape else it writes 1. This uses constant space so we can say that languages decided by DFA are in logspace 2. we count the number of parenthesis. incrementing when we see a opening parenthesis and decrement it when we encounter a closing parenthesis 3. Languages recognised by a PDA grow in linear way as they use a stack, if a CFL would be similar to the PATH problem which we defined in class then we could say that it is in NL.

-- Apr 12 In-Class Exercise

In DFA we are storing information of only current state. If DFA has n input states then each state can be represented by at most log(n) bits. Hence DFA is in logspace L.

In the language of correctly matched parenthesis, maintains a count of unmatched pairs. If opening parenthesis is encountered then increament counter. If closing parenthesis is encountered then decreament the counter. For n parentheses, we need atmost log(n) bits to maintain the count. Hence It is in L.

Since for languages recognized by PDA stacks are updated in linear was. We need to check complete stack to verify whether the language is in NL. Hence it is harder do determine that the language is in NL.

1. In DFA we are storing information of only current state. If DFA has n input states then each state can be represented by at most log(n) bits. Hence DFA is in logspace L. 2. In the language of correctly matched parenthesis, maintains a count of unmatched pairs. If opening parenthesis is encountered then increament counter. If closing parenthesis is encountered then decreament the counter. For n parentheses, we need atmost log(n) bits to maintain the count. Hence It is in L. 3. Since for languages recognized by PDA stacks are updated in linear was. We need to check complete stack to verify whether the language is in NL. Hence it is harder do determine that the language is in NL.

-- Apr 12 In-Class Exercise

• DFA has K states where K is a constant: this requires a fixed amount of memory, which is in O(log(n))

• Parenthesis Language is in LOGSPACE, because all one needs to do is count parenthesis (adding or subtracting one at each symbol), and counting takes O(log(n))

• A stack is required to keep track of arbitrary symbols, and a stack can grow linearly, which is larger than LOGSPACE

• DFA has K states where K is a constant: this requires a fixed amount of memory, which is in O(log(n)) • Parenthesis Language is in LOGSPACE, because all one needs to do is count parenthesis (adding or subtracting one at each symbol), and counting takes O(log(n)) • A stack is required to keep track of arbitrary symbols, and a stack can grow linearly, which is larger than LOGSPACE

-- Apr 12 In-Class Exercise

Since we have finitely many states, we will simulate the input on a TM with the same amount of states, and would only require an additional write space for the output. This can be done in constant space.

First we need to count the number of parenthesis which can be done in n/2 time, and keeping track of left vs right parenthesis which can be done in log space.

Since we have to keep track of the stack, there could be n many symbols to write on the work tape, which would be greater than logspace. Suppose we had a stack with log many symbols, this can be done in NL-space.

(Edited: 2017-04-12)

#Since we have finitely many states, we will simulate the input on a TM with the same amount of states, and would only require an additional write space for the output. This can be done in constant space. #First we need to count the number of parenthesis which can be done in n/2 time, and keeping track of left vs right parenthesis which can be done in log space. #Since we have to keep track of the stack, there could be n many symbols to write on the work tape, which would be greater than logspace. Suppose we had a stack with log many symbols, this can be done in NL-space.

-- Apr 12 In-Class Exercise

Since a DFA has finite states, an automata which when successfu;;y accepts the string writes 0 else writes 1 cane be designed. SInce this uses constant space,

languages decided by DFA are in logspace

Count number of open and close parenthesis and if there is a mismatch, reject it

3 .Since languages recognised by a PDA use stack, they grow in linear time. If a CFL is similar to PATH problem, we can say that it is in NL

1. Since a DFA has finite states, an automata which when successfu;;y accepts the string writes 0 else writes 1 cane be designed. SInce this uses constant space, languages decided by DFA are in logspace 2. Count number of open and close parenthesis and if there is a mismatch, reject it 3 .Since languages recognised by a PDA use stack, they grow in linear time. If a CFL is similar to PATH problem, we can say that it is in NL

-- Apr 12 In-Class Exercise

(i) We could encode all the states of DFA in the input tape of the turing machine. We can output 1 if accept state is reached else 0. So it would take 1 tape square 1 is less than log space. (ii) The parathesis matching can be done as given: for every open paranthesis we increment the count and for closed paranthesis we decrement the count and when we finish parsing the input the count should be 0 if the parathesis match. So it would take atmost log(n/2) space. (iii)To check if a language is recognized by PDA, we use PATH algorithm which uses stack. The inputs put into a stack, the stack would grow linearly which is in NL.

Query Statistics

https://www.yioop.com/thread/7101

Total Elapsed Time for Queries: 0.03484630584716797 seconds.

SELECT LOCALE_NAME, WRITING_MODE FROM LOCALE WHERE LOCALE_TAG ='en-US'

Time: 0.001752138137817383 seconds.

SELECT COALESCE(MAX(UPDATE_TIMESTAMP), 0) AS MOST_RECENT FROM ITEM_IMPRESSION_SUMMARY WHERE USER_ID = 2 AND ITEM_TYPE = 3 AND ITEM_ID IN (SELECT GROUP_ID FROM USER_GROUP WHERE USER_ID = 2 AND STATUS = 1) AND UPDATE_PERIOD = -4

Time: 0.0008800029754638672 seconds.

DELETE FROM ITEM_IMPRESSION_SUMMARY WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -4
Array ( [0] => 2 [1] => 7101 [2] => 1 )

Time: 0.004336118698120117 seconds.

INSERT INTO ITEM_IMPRESSION_SUMMARY VALUES (?, ?, ?, -4, ?, 0, -1, -1) ON CONFLICT DO NOTHING
Array ( [0] => 2 [1] => 7101 [2] => 1 [3] => 1782249773 )

Time: 0.004339218139648438 seconds.

UPDATE ITEM_IMPRESSION_SUMMARY SET NUM_VIEWS = NUM_VIEWS + 1 WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -2 AND UPDATE_TIMESTAMP = 0
Array ( [0] => 2 [1] => 7101 [2] => 1 )

Time: 0.0003099441528320312 seconds.

DELETE FROM ITEM_IMPRESSION_SUMMARY WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -4
Array ( [0] => 2 [1] => 294 [2] => 3 )

Time: 0.004310131072998047 seconds.

INSERT INTO ITEM_IMPRESSION_SUMMARY VALUES (?, ?, ?, -4, ?, 0, -1, -1) ON CONFLICT DO NOTHING
Array ( [0] => 2 [1] => 294 [2] => 3 [3] => 1782249773 )

Time: 0.004802942276000977 seconds.

UPDATE ITEM_IMPRESSION_SUMMARY SET NUM_VIEWS = NUM_VIEWS + 1 WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -2 AND UPDATE_TIMESTAMP = 0
Array ( [0] => 2 [1] => 294 [2] => 3 )

Time: 0.0003490447998046875 seconds.

SELECT STATUS FROM USERS WHERE USER_ID = ?
Array ( [0] => 2 )

Time: 0.0004708766937255859 seconds.

SELECT USER_NAME FROM USERS WHERE USER_ID = ?
Array ( [0] => 2 )

Time: 0.0004038810729980469 seconds.

SELECT COUNT(DISTINCT G.GROUP_ID) AS NUM FROM USER_GROUP UG, SOCIAL_GROUPS G WHERE UG.USER_ID = ? AND UG.GROUP_ID = G.GROUP_ID AND ( UG.STATUS = 1 OR UG.STATUS = 5)
Array ( [0] => 2 )

Time: 0.001451015472412109 seconds.

SELECT COUNT(GI.ID) AS NUM FROM GROUP_ITEM GI WHERE GI.GROUP_ID IN (SELECT GROUP_ID FROM USER_GROUP WHERE USER_ID = ? AND STATUS = 1) AND GI.TITLE NOT LIKE ? AND GI.PUBDATE > ?
Array ( [0] => 2 [1] => %2% [2] => 1782249772 )

Time: 0.0005550384521484375 seconds.

SELECT G.GROUP_ID AS GROUP_ID FROM SOCIAL_GROUPS G WHERE G.GROUP_NAME = ?
Array ( [0] => Personal$2 )

Time: 0.0002489089965820312 seconds.

SELECT USER_ID FROM USER_GROUP WHERE GROUP_ID = ?
Array ( [0] => -1 )

Time: 0.0001480579376220703 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-4 )

Time: 0.0002701282501220703 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-37 )

Time: 9.107589721679688E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-202 )

Time: 7.700920104980469E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-687 )

Time: 6.890296936035156E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1115 )

Time: 6.890296936035156E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1138 )

Time: 0.0001068115234375 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1140 )

Time: 7.104873657226562E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1149 )

Time: 6.794929504394531E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1152 )

Time: 6.794929504394531E-5 seconds.

SELECT * FROM GROUP_ITEM WHERE ID=? LIMIT 1
Array ( [0] => 7101 )

Time: 0.0002009868621826172 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 9.584426879882812E-5 seconds.

SELECT G.GROUP_ID AS GROUP_ID, G.GROUP_NAME AS GROUP_NAME, G.OWNER_ID AS OWNER_ID, O.USER_NAME AS OWNER, REGISTER_TYPE, UG.STATUS AS STATUS, G.MEMBER_ACCESS AS MEMBER_ACCESS, G.VOTE_ACCESS AS VOTE_ACCESS, G.POST_LIFETIME AS POST_LIFETIME, UG.JOIN_DATE AS JOIN_DATE, G.OPTIONS AS OPTIONS, G.RENDER_ENGINE AS RENDER_ENGINE FROM SOCIAL_GROUPS G, USERS O, USER_GROUP UG WHERE (UG.USER_ID = :user_id) AND UG.GROUP_ID= :group_id AND UG.GROUP_ID=G.GROUP_ID AND OWNER_ID = O.USER_ID LIMIT 1
Array ( [:group_id] => 294 [:user_id] => 2 )

Time: 0.0003719329833984375 seconds.

SELECT COUNT(DISTINCT GI.ID) AS NUM FROM GROUP_ITEM GI, SOCIAL_GROUPS G, USER_GROUP UG, USERS O WHERE GI.PARENT_ID='7101' AND NOT LOWER(group_name) LIKE LOWER('Personal$%') AND (UG.USER_ID='2' OR G.REGISTER_TYPE IN ('4','3') ) AND GI.USER_ID=O.USER_ID AND GI.GROUP_ID=G.GROUP_ID AND GI.GROUP_ID=UG.GROUP_ID AND (( G.MEMBER_ACCESS IN ('2','3','4', '5')) OR (G.OWNER_ID = UG.USER_ID OR UG.USER_ID = '1'))

Time: 0.002621173858642578 seconds.

SELECT DISTINCT GI.ID AS ID, GI.PARENT_ID AS PARENT_ID, GI.GROUP_ID AS GROUP_ID, GI.TITLE AS TITLE, GI.DESCRIPTION AS DESCRIPTION, GI.FLAG AS FLAG, GI.PUBDATE AS PUBDATE, GI.EDIT_DATE AS EDIT_DATE, G.OWNER_ID AS OWNER_ID, G.MEMBER_ACCESS AS MEMBER_ACCESS, G.GROUP_NAME AS GROUP_NAME, P.USER_NAME AS USER_NAME, P.USER_ID AS USER_ID, GI.TYPE AS TYPE, GI.UPS AS UPS, GI.DOWNS AS DOWNS, G.VOTE_ACCESS AS VOTE_ACCESS FROM GROUP_ITEM GI, SOCIAL_GROUPS G, USER_GROUP UG, USERS P WHERE GI.PARENT_ID='7101' AND NOT LOWER(group_name) LIKE LOWER('Personal$%') AND (UG.USER_ID='2' OR G.REGISTER_TYPE IN ('4','3') ) AND GI.GROUP_ID=G.GROUP_ID AND GI.GROUP_ID=UG.GROUP_ID AND (( G.MEMBER_ACCESS IN ('2','3','4', '5')) OR (G.OWNER_ID = UG.USER_ID OR UG.USER_ID = '1')) AND P.USER_ID = GI.USER_ID ORDER BY GI.PUBDATE ASC LIMIT 10 OFFSET 0

Time: 0.003975868225097656 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 0.0002341270446777344 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 7.104873657226562E-5 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 6.103515625E-5 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 6.604194641113281E-5 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 5.698204040527344E-5 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 6.413459777832031E-5 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 4.315376281738281E-5 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 4.911422729492188E-5 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 4.482269287109375E-5 seconds.

SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => -2 )

Time: 0.0001788139343261719 seconds.

SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 6.508827209472656E-5 seconds.

SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 6.604194641113281E-5 seconds.

SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 6.29425048828125E-5 seconds.

SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 6.008148193359375E-5 seconds.

SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 5.602836608886719E-5 seconds.

SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 3.886222839355469E-5 seconds.

SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 3.504753112792969E-5 seconds.

SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 3.886222839355469E-5 seconds.

SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 3.910064697265625E-5 seconds.

SELECT * FROM GROUP_ITEM WHERE ID=? LIMIT 1
Array ( [0] => 7101 )

Time: 0.0002028942108154297 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 294 )

Time: 0.0001070499420166016 seconds.

SELECT G.GROUP_ID AS GROUP_ID, G.GROUP_NAME AS GROUP_NAME, G.OWNER_ID AS OWNER_ID, O.USER_NAME AS OWNER, REGISTER_TYPE, UG.STATUS AS STATUS, G.MEMBER_ACCESS AS MEMBER_ACCESS, G.VOTE_ACCESS AS VOTE_ACCESS, G.POST_LIFETIME AS POST_LIFETIME, UG.JOIN_DATE AS JOIN_DATE, G.OPTIONS AS OPTIONS, G.RENDER_ENGINE AS RENDER_ENGINE FROM SOCIAL_GROUPS G, USERS O, USER_GROUP UG WHERE (UG.USER_ID = :user_id OR G.REGISTER_TYPE IN (3,4)) AND UG.GROUP_ID= :group_id AND UG.GROUP_ID=G.GROUP_ID AND OWNER_ID = O.USER_ID LIMIT 1
Array ( [:group_id] => 294 [:user_id] => 2 )

Time: 0.0005249977111816406 seconds.

SELECT STATUS FROM USER_GROUP WHERE USER_ID=? AND GROUP_ID=? LIMIT 1
Array ( [0] => 2 [1] => 294 )

Time: 0.0001671314239501953 seconds.