8

So I'm not completely sure, but I think you're asking to count the number of strings of size $n$ (over the alphabet $\{a, b\}$) where the factor/substring $aa$ does not appear right? In this case, there are a few combinatorial approaches that you can take. Both Yuval and ADG have given simpler and more intuitive arguments, so I definitely suggest checking ...


7

Lee Gao's answer is excellent. Here is a different account. Consider the following automaton: This is an unambiguous finite automaton (UFA) without $\epsilon$ transitions: an NFA such that each word has exactly one accepting path. The number of words of length $n$ is thus the number of paths of length $n$ from the starting state to an accepting state (since ...


4

@Lee Gao's is too complex (I haven't even read the whole thing), here is a simplistic approach: Let f(n) be all desired strings out of which let a(n) be strings that end at a and b(n) be strings that end at b. Now for every string that ends at b we can directly add a to get ba in ending and a valid string: $$a(n)=b(n-1)\tag{1}$$ Note than we cannot add a ...


3

Your problem is known variously as the lost cow problem or the cow-path problem, and is a standard example in online algorithms. The algorithm you describe is 9-competitive, which is optimal for deterministic algorithms. For randomized algorithms the competitive ratio is roughly 4.6. See for example a writeup apparently by Rudolf Fleischer.


3

There are many functions that satisfy your condition. Here are a few. $a_i=1+c^{-i}$, for some constant $c\ge 2$. $a_i= 1+b_i/p_i$, where $p_i$ is the $i^{th}$ prime number and $b_i$ is any integer between 1 and $p_i-1$. $a_i =1+\alpha^i/\lceil\alpha^i\rceil$, for any positive transdental number $\alpha$. For example, you can take $\alpha = \pi$ or $\alpha=...


3

Finding a good analytic characterization of $n(N)$ is tricky. Let's first consider the relaxation where $N = \frac{n}{\log n}$ without the flooring restriction. Here's a somewhat nonintuitive approximation: let $m(z) = 1 + \frac{1}{z}$, let's see how $\frac{m(z)}{\log m(z)}$ behaves as a function of $z$: $$ \begin{array}{ccc} z = 1 & 10 & 100 & ...


3

You say that $N=\lfloor\tfrac{n}{logn}\rfloor$. But since you have a linear recurrence in N, not n, you really want n as a function of N. We have $n ≈ N \log n$. You substitute this for n and get $n ≈ N \log (N \log n) = N \log N + N \log \log n$. $\log \log n$ is small compared to $\log N$, so we ignore it and get $T(N)=T(N-1)+\mathcal{O}(N \log N)$ ...


3

Let us start by giving an alternative formula for $\sum_{u,d} |L(u,d)|$. For a node $x$, let $\pi^{(d)}(x)$ be its $d$'th parent, and let $h(x)$ be its height. Then $$ \sum_{u,d} |L(u,d)| = \sum_x |\{ L(\pi^{(d)}(x),d) : 0 \leq d \leq h(x)\}|. $$ It suffices to show that $|\{ L(\pi^{(d)}(x),d) : 0 \leq d \leq h(x)\}| = O(\sqrt{n})$ for all nodes $x$. Let $...


3

The Risch algorithm is undecidable by Richardson Theorem if absolute value is allowed or semi-undecidable with $\log_2, \pi, e^x, \sin x$. Akitoshi Kawamura in his dissertation Computational Complexity in Analysis and Geometry has proved that integration is $\#P{-}complete$ operation. There are multiple modifications of the Risch algorithm, but still nobody ...


2

Hint: Use a union bound. Note that for $m \geq 2^k$ you cannot provide any non-trivial bound, since there are formulas with $2^k$ clauses of width $k$ that are unsatisfiable. The same example shows that the bounded hinted above is tight (for all $m \leq 2^k$).


2

Let me write the definition in a little bit more detail. Suppose that $f(n),g(n)$ are two functions from $\mathbb{N}$ to $\mathbb{R}_+$, that is, they accept as input a natural number, and return as output a positive real number. We say that $f(n) = O(g(n))$ if there exist $n_0 \in \mathbb{N}$ and $C \in \mathbb{R}_+$ such that for all $n \geq n_0$, $$ f(n) ...


2

That guess is obviously wrong. If all items have weight 666 and value 1, then you can fit 3 items into a bin of size 2000, and only one into a bin of size 1000. If all weights are W < $w_i$ ≤ 2W, then O = 0 and O' = highest value of a single item. There is very little that you can say except the obvious O ≤ O'. You might have "valuable" items with a ...


2

This kind of thing just doesn't work. For example, one of your intermediate terms is $O(1)/O(\log n)$. However any function $f$ can be written as $g/h$ where $g=O(1)$ and $h=O(\log n)$. If $f=O(1)$, then let $g=f$ and $h=1$. If $f=\Omega(1)$, then let $g=1$ and $h=1/f$. For a more formal treatment, try to rewrite each of your statements that involve ...


2

I will suggest a similar strategy. Note that your strategy yields a constant factor better than the one presented here but the proof is more technical. Let us divide the strategy in rounds $1, 2, \dots$, where in round $i$ we go $2^{i-1}$ steps to the right, then we go back to the center and we repeat the exact same to the left. This means we go one step to ...


2

It seems that you have overlooked the fact that $f(n) \in \Theta(n^4)$ already implies both an upper bound of $f(n)\in O(n^4)$ and a lower bound of $f(n)\in \Omega(n^4)$. Intuitively, $\Theta$- notation says that a function grows "as fast as" another function, which means both "at most as fast" and "at least as fast".


2

Let us notice the following: $$ |\sin(\pi \cdot n/2)| = \begin{cases} 1 & \text{if $n$ is odd}, \\ 0 & \text{if $n$ is even}. \end{cases} $$ This implies that your function $f(n)$ alternates between $n^2$ (for odd $n$) and $0$ (for even $n$). This means, for example, that $f(n) = O(n^2)$ (since $f(n) \leq n^2$ for all $n$) but $f(n) \neq \Omega(n^2)$ ...


2

After posting the above I realized there was a possible solution with a different model. By viewing sets as nodes in a directed graph and edges as constraints, where $x \subseteq y$ would be translated to x -> y, the final checker would simply look for a path between $a$ and $b$ in this graph. (Using DFS or BFS per this SO question).


2

That section is not talking about parsing. The algorithms referred to are algorithms for converting between CFGs and PDAs of different types. The question is, as usual, "what is the computational complexity of the algorithm", and the response is, as usual, expresseded in terms of the size of the input -- to the algorithm. The input to an algorithm which ...


2

The trivial bounds are that $|c| \le |X|=n$ and $|c| \le |S|=p$. Knowing bounds on the sizes of the sets $s_i$ doesn't help much. For instance, consider the family of sets $s_1,\dots,s_{n-k+1}$ given by $s_i=\{i,n-k+2,\dots,n-1,n\}$. These sets are all of size $k$, and yet the largest inclusion-minimal cover has size $n-k+1$, i.e., exactly equal to the ...


2

Set disjointness is easier for product distributions since the hard distribution for set disjointness is very far from being a product distribution. What do we require from a hard distribution $(X,Y)$ for inner product? We want each of $X,Y$ separately to be quite random, and we want $X\cdot Y$ to be mostly zero, say $X \cdot Y$ contains at most a single $1$....


1

You can identify each set $A$ with a unary predicate $A(x)$. For example, the constraints $A \subseteq B$ and $B \subseteq C$ correspond to the constraints $$ \forall x \, A(x) \to B(x) \\ \forall x \, B(x) \to C(x) $$ Suppose we want to understand whether these constraints imply $A \subseteq C$, that is $$\forall x \, A(x) \to C(x)$$ This holds if for every ...


1

Let $S$ be a maximal set of vertices in which any two vertices are at distance at least 3. (Note maximal just means that $S$ cannot be enlarged by adding new vertices.) By design, any other vertex is at distance at most 2 from some vertex in $S$, and therefore $S$ is a 2-dominating set. On the other hand, if we define the $B_1(v)$ to consist of all vertices ...


1

Here's what my search has come up with: There's a straightforward dynamic programming solution of the problem in this case, which requires $\mathop{\Omega}\left( k \cdot n^3 \right)$ time; and with some thought one can avoid redundant computation of sums-of-squares by this algorithm, reducing the complexity to $\mathop{\Omega}\left( k \cdot n^2 \right)$. ...


1

If you want to compute X (whatever X is), then you just need to compute X, and whatever intermediate results are required by your method for computing X. If your method doesn't need upper and lower bounds, there's no need to compute them. The point of upper and lower bounds is that they're usually easier to compute than the actual answer, and ...


1

There are lots of NP-complete problem where no algorithm will find an optimal solution - during your lifetime. Given the choice between a greedy algorithm that finds a solution quickly which is often good, and an algorithm that will find a guaranteed optimal solution, but not while you are waiting for it, what are you going to use?


1

The recurrence relation $T(n) = T(n-1) + T(n-2)$, with initial conditions $T(2) = T(1) = 1$, has as solution the Fibonacci numbers, whose asymptotic growth is known to be $\Theta(\phi^n)$, where $\phi = \frac{1+\sqrt{5}}{2} < 2$. The same bound holds for arbitrary positive initial conditions.


1

Tricky. As an approximation, assume that the number n is in the set with a probability p (n), and the sum of p (n) over all integers n is finite, so we may guess that the set is finite. You'd have to check enough values n to make some reasonable assumptions about p (n), and then based on those assumptions make a reasonable guess about the upper bound. ...


1

Place $T$ triangles next to each other such that the line $l$ intersects them all. Observe how the number of intersections is $T+1$. Now substitute $T$ with the upper bound on the number of triangles for any triangulation that you mentioned, and we obtain $2n-5+1=2n-4$ as an upper bound on the number of intersections. The example provided in the question ...


1

Since $n \geq 1$ (since $n$ is the input length), we have $$ 20n^2 \leq 20n^2 + 11n + 1 \leq (20+11+1)n^2 = 32n^2. $$ Put differently, for all $n \geq 1$, the function $f(n) = 20n^2 + 11n + 1$ is bounded from below by $20n^2$ and from above by $32n^2$. This shows that $f(n) = \Theta(n^2)$. Note also that when $n$ is large, $f(n)$ gets very close to $20n^2$. ...


1

Remember that: We can view a nondeterministic computation as a directed acyclic graph of configurations indexed by time. I have a guess that in your eyes: $2^n$ for both, one directs itself and one directs others and at most every has the $\Sigma$ chance to go next state, maybe to itself, maybe the other state, so from $1$ to $n$ state, an NFA produces at ...


Only top voted, non community-wiki answers of a minimum length are eligible