[go: up one dir, main page]
Scribd
Upload
11 views1 page

ECE 606, Fall 2019, Assignment 9: Zhijie Wang, Student ID Number: 20856733 Zhijie - Wang@uwaterloo - Ca November 12, 2019

Uploaded by

hstrybest
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views1 page

ECE 606, Fall 2019, Assignment 9: Zhijie Wang, Student ID Number: 20856733 Zhijie - Wang@uwaterloo - Ca November 12, 2019

Uploaded by

hstrybest
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

ECE 606, Fall 2019, Assignment 9

Zhijie Wang, Student ID number: 20856733

zhijie.wang@uwaterloo.ca
November 12, 2019

1. Proof. Suppose each state remember the past 4 bits in order to make decision on where the fourth from
last bit is ‘0’. If there is a DFA which has states fewer than 16, then, there must be some state, said state
q, where both a1 a2 a3 a4 and b1 b2 b3 b4 lead to this state. (ai , bi ∈ {0, 1})
Since a1 a2 a3 a4 6= b1 b2 b3 b4 , then they must differ in at least one bit, say ai 6= bi , here we assume ai =
1, bi = 0.
If i = 1, then, since 1a2 a3 a4 has the fourth from last bit equals to 0, then state q must be acceptable,
which makes contradiction because 0b2 b3 b4 is unacceptable.
If i = 2, then, we have a1 1a3 a4 and b1 0b2 b3 b4 at state q. Suppose we have input 0 to pass state q to state
p, then, 1a3 a4 0 is acceptable, which makes contradiction again because 0b3 b4 0 is unacceptable.
If i = 3, 4, suppose we input 00 and 000, then, it will make the same contradiction as before.
Therefore, no DFA of fewer than 16 states exists for the following language: bit-strings of length at least
4, whose fourth from last bit is ‘0’.

2. Suppose we have a solution consists of an n2 × n2 matrix, therefore, for each row, column and square,
it takes Θ(n2 ) times to check if every element is distinct. We have n2 rows, n2 columns and n2 squares,
and also k slots which have been filled before, so, it takes 3n2 Θ(n2 ) + Θ(1) = Θ(n4 ) times. If n is
binary-encoding, suppose n = 2s , then it takes Θ(24s ) times to check a solution.
Therefore, this problem is ∈
/ NP, but ∈ NEXP.

3. Suppose G =< V 0 , E 0 >, H =< V, E >.


1: S ← {}
2: for each i from 1 to |V 0 | do
3: Non-deterministically pick a vertex vi in V \S
4: f (vi0 ) = vi
5: S ∪ {vi }
6: for each i from 1 to |E 0 | do
7: e0i = (a0 , b0 )
8: if ei (f (a0 ), f (b0 )) is not exist then
9: return False
10: return True

Here we have a brief discussion. For the first for-loop, we build a 1-1 f from vertexes in G to some vertexes
in H, which is done with non-deterministically pick vertexes from H. Therefore, we check for each edge
e0 = (a0 , b0 ) in G, whether H also has a edge e = (f (a0 ), f (b0 )). If all the edges exist, then there is a
subgraph of H which is isomorphic to G.
The first for-loop runs Θ(|V 0 |) times, and computing V \S takes Θ(|V |) times. The second for-loop runs
Θ(|E 0 |) times for the worst case. Therefore, the algorithm runs Θ(|V 0 ||V | + |E 0 |) for the worst case.
4. a9p4.py

You might also like