Math Problems Vault

Problem 7.1

Answer each part TRUE or FALSE.

?

(a)

$2 n=O(n)$ .

(b)

$n^{2}=O(n)$ .

(c)

ᴬ $n^{2}=O\left(n \log^{2} n\right)$ .

(d)

ᴬ $n \log n=O\left(n^{2}\right)$ .

(e)

$3^{n}=2^{O(n)}$ .

(f)

$2^{2^{n}}=O\left(2^{2^{n}}\right)$ .

Problem 7.2

Answer each part TRUE or FALSE.

?

(a)

$n=o(2 n)$ .

(b)

$2 n=o\left(n^{2}\right)$ .

(c)

ᴬ $2^{n}=o\left(3^{n}\right)$ .

(d)

ᴬ $1=o(n)$ .

(e)

$n=o(\log n)$ .

(f)

$1=o(1 / n)$ .

Problem 7.3

(a)(b)

Which of the following pairs of numbers are relatively prime? Show the calculations that led to your conclusions.

?

(a)

1274 and 10505

(b)

7289 and 8029

Problem 7.4

Fill out the table described in the polynomial time algorithm for context-free language recognition from Theorem 7.16 for string $w=$ baba and CFG $G$ :

\begin{aligned} & S \rightarrow R T \\ & R \rightarrow T R \mid \mathrm{a} \\ & T \rightarrow T R \mid \mathrm{b} \end{aligned}

?

Problem 7.5

Is the following formula satisfiable?

(x \vee y) \wedge (x \vee \bar{y}) \wedge (\bar{x} \vee y) \wedge (\bar{x} \vee \bar{y})

?

Problem 7.6

Show that P is closed under union, concatenation, and complement.

?

Problem 7.7

Show that NP is closed under union and concatenation.

?

Problem 7.8

Let $\operatorname {CONNECTED}=\left\{ \langle G\rangle \mid G\text{ is a connected undirected graph }\right\}$ . Analyze the algorithm given on page 185 to show that this language is in P.

?

Problem 7.9

A triangle in an undirected graph is a 3-clique. Show that TRIANGLE $\in \mathrm{P}$ , where TRIANGLE $=\left\{ \langle G\rangle \mid G\text{ contains a triangle }\right\}$ .

?

Problem 7.10

Show that $\operatorname {ALL}_{\text{DFA }}$ is in P.

?

Problem 7.11

(a)(b)

In both parts, provide an analysis of the time complexity of your algorithm.

?

(a)

Show that $\operatorname {EQ}_{\mathrm{DFA}} \in \mathrm{P}$ .

(b)

Say that a language $A$ is star-closed if $A=A^{*}$ . Give a polynomial time algorithm to test whether a DFA recognizes a star-closed language. (Note that $\operatorname {EQ}_{\text{NFA }}$ is not known to be in P.)

Problem 7.12

Call graphs $G$ and $H$ isomorphic if the nodes of $G$ may be reordered so that it is identical to $H$ . Let $\operatorname {ISO}=\left\{ \langle G, H\rangle \mid G\text{ and }H\text{ are isomorphic graphs}\right\}$ . Show that $\operatorname {ISO} \in \mathrm{NP}$ .

?