Using pumping lemma to show a language is not context free(Complicated) How can i show that the following long language is not context free using the pumping lemma?

$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$

Such that:

$m,n,o \geq 1;$

$m>n>o>0;$

$i_1,i_2,...,i_{2m} \geq 0;$

$j_1,j_2,...,j_{2n} \geq 0;$

$k_1,k_2,...,k_o \geq 0$

And how can I conclude from that $L=\left\{0^i1^j2^k|1\le \:i<j<k\right\}$ is not a context free language?

I have been struggling with it for many hours, would really appreciate an explanation I can follow and learn from. The examples given in class are simpler and not on that level, and I don't know which z to take and how to break it in order to deduct in a proof that L is not context free.

Could you please give a slow explanation so I could learn fast?

My attempt for the first part:

Proving by negation that L is not a context free language: Assuming L is a context free language, then there should exist a pumping length P for which any string S such that $|S| \leq P$ can be divided into 5 pieces(uvxyz) while obeying the pumping lemma rules. Because of the information on the question, I'll focus on the first part of the lemma, i.e: $\forall i: uv^ixy^iz \in L$. The structure of a typical word from L will be:$S=abc^{p_1}bc^{p_2}...bc^{2p_i+2}def^{p_1}ef^{p_2}...ef^{2p_i}ghq^{p_1}...ghq^{2p_i-1}$. vxy cannot contain c,f,q's, We'll divide it into the following cases based on vxy. Don't know how to divide it or how to continue, would really appreciate your assistance with it. Very important to me

My attempt for the second part(I don't understand it well enough to solve the first part, I will ask for your help with it):

Proving by negation that L is not a context free language: Assuming L is a context free language, then there should exist a pumping length P for which any string S such that $|S| \leq P$ can be divided into 5 pieces(uvxyz) while obeying the pumping lemma rules. Because of the information on the question, I'll focus on the first part of the lemma, i.e: $\forall i: uv^ixy^iz \in L$. The structure of a typical word from L will be:$S=0^p1^p2^p$. vxy cannot contain a,b,c's, We'll divide it into the following cases based on vxy:

Doesn't contain 0: pumping S with 0 to obtain $uv^0xy^0z=uxz$. in this case, there are fewer 1 or 2, so not in L.
There's 0 but not 2: pumping S with 2 to obtain $uv^2xy^2z$, meaning more 0's than 2's, so it is not in L.
There are no 2's: pumping S with 2 to obtain $uv^2xy^2z$, meaning more 1's or 0's than 2's, so it is not in L.

Since each option was checked and each one contradicted, It can be safe to assume that $L=\left\{0^i1^j2^k|1\le \:i<j<k\right\}$ is not a context free language since it does not adhere to the pumping lemma.

Thank you very much

Start with a long enough string $w$ in $L$ in which $m=p+2,n=p+1,o=p$ and

$i_1,...,i_{2m}=0$
$j_1,...,j_{2n}=0$
$k_1,...,k_{o}=0$

$w = a\; b^{2(p+2)}\; d\; e^{2(p+1)}\; g\; h^{p} $

Then apply pumping lemma (it should be easier ;-).

If you want to "reduce" $L$ to $L' = \left\{0^i1^j2^k|1\le \:i<j<k\right\}$ then you must use closure properties, in particular CFLs are:

closed under homomorphism
closed under reverse homomorphism
closed under reversal

The homomorphism that you can use is: $H(a) = H(c) = H(d) = H(f) = H(g) = H(q) = \epsilon, H(b) = \bar{2}, H(e) = \bar{1}, H(h) = \bar{0}$

Applying $H$ to the language gives $H(L) = \{ \bar{2}^{2m} \bar{1}^{2n} \bar{0}^{o} \mid m > n > o > 0\}$

Then you can use a reverse homomorphism $\varphi(2)=\bar{2}\bar{2}, \varphi(1)=\bar{1}\bar{1}, \varphi(0) = \bar{0}$ and you get:

$\varphi^{-1}( H(L)) = \{ 2^m 1^n 0^o \mid m>n>o>0 \}$

and finally apply closure under reversal:

$(\varphi^{-1}( H(L)))^R = \{ 0^o 1^n 2^m \mid 0<o<n<m \} = L'$

If $L$ is CF then by closure properties $(\varphi^{-1}( h(L)))^R = L'$ should be CF, which is not the case.


Do multiple transitions over the input give finite state machines more power? In the common model of FSA, the automaton reads the input string once, moving from one state to another after reading each letter in the input string. Epsilon transitions allow moving from one state to another without reading a character. However, the movement over the input string is still unidirectional.

Is there a formal model of a FSA that reads the input string K times, and only then reaches its final state? is this model more powerful than FSA, e.g., can it recognize context-free languages that are not regular?

I think the option of adding an epsilon transition for every transition edge in the FSA means the models are equivalent in power (since we can model K iteration over the input by epsilon transitions from the last state back to the first -- although I am not sure), but if this is so, are there any results regarding the number of states needed in a regular FSA and a FSA with K transitions?

Multiple passes do not add any power.

It's possible to do all the passes in parallel, using a state machine whose states are vectors of states in the original machine. Each vector has one element for each state in the original machine, and represents the result of performing the transitions starting at the state corresponding to the position of the element in the vector. A vector state is an accepting state iff there is a path of length $k$ starting at the original machine's starting state and linking the state at each position to that position.

Specifically, let the original machine be $(Σ, Q, q_1, δ, F)$, where $Q = \{q_1, \ldots, q_n\}$. Define the new machine $(Σ, Q^n, q'_s, δ', F')$ with

$$\begin{align}
q'_s &= \langle q_1, \ldots, q_n\rangle \\
\delta'(\langle q_{i_1},\ldots,q_{i_n}\rangle, s) &= \langle \delta(q_{i_1}, s),\ldots,\delta(q_{i_n}, s)\rangle \\
\langle q_{i_1},\ldots,q_{i_n}\rangle \in F' &\text{ iff } \exists t_1,\ldots,t_k \text{ with } t_1 = 1, q_{t_k} \in F \text{ and } t_j = i_{t_{j-1}} \text{ for } j \in \{2,\ldots,k\}
\end{align}$$
Although that's a lot of states, it's still a finite number, and the set of  accepting states is well-defined and can be enumerated. So the multiple-pass machine is still a finite-state machine.


Algorithm for Filling Regions with Small Gaps I am looking for an algorithm that fills a region with one color, but the edge of the region is not completely closed (i.e. one or more gaps are being left). The result is like the use of the Paint Bucket Tool with Gap Size option in Adobe Flash. We can assume that the input of the algorithm has to specify the largest size (straight line distance) of the gap.

My straightforward idea is (1) to fill the gaps in the edges (as shown in this webpage), and then (2) use the flood fill algorithm to perform the filling on a closed region. I have done (2) by using a recursive algorithm, but how should (1) be done?

Any alternative idea are also welcomed. Thanks!

This is clossing operator implemented as dilate-then-erode filter and then it is FloodFill.
Dilate filter is adding pixels that would became new hull.
Erode filter is cutting out pixels that are at the hull.
Here is try me link: Demo of operators
One thing that could be improved in this technique are gaps after filter.

You can get rid of it by applying dilation on color region.

This is one kind of solving, another would be to go along the edge and find pattern edge-gap-edge with given radius.
There are also caveats - if edge is not in single color, then operators must include that information or get binary representation (with binary data, e.g. 0 means empty, 1 means edge).
Clossing operator is easy to implement but slower than contour tracing.
You could trace edge by FloodFill starting from edge region, using BFS and going into counting mode after boundary is crossed, to check within gap radius.


Split-Find: maintaining dynamic graph connectivity information, under edge deletion Is there a data structure to keep track of the connected components of a dynamic graph, when the graph might by changing by deleting edges of the graph?

Let $G$ be an undirected graph.  I have two operations I'd like to be able to perform:

Delete$(u,v)$: delete the edge $(u,v)$ from the graph.
SameComponent$(u,v)$: returns true or false according to whether $u,v$ are in the same connected component

Is there a data structure that allows me to perform both operations relatively efficiently?

The naive data structure is simply to store the graph in adjacency list representation, and answer SameComponent$(u,v)$ queries by doing a depth-first search from $u$ to see if $v$ is reachable.  However, that makes the SameComponent operation take linear time, and it feels like it is re-doing a lot of work, so maybe there is a more efficient algorithm.  Is there a data structure where both operations can be done in sub-linear running time?

One way to think about it is that I am basically asking for the dual of the Union-Find data structure.  The Union-Find data structure offers two operations:

Union$(u,v)$: add an edge $(u,v)$ to the graph.
Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).

You could think of this question as asking for a Split-Find data structure, which should support two operations:

Split$(u,v)$: delete the edge $(u,v)$ from the graph.
Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).

As we know, there is an efficient Union-Find data structure.  The apparent symmetry between Union-Find and Split-Find makes me wonder whether there is also an efficient Split-Find data structure, too.

Of course, if we had an efficient Split-Find data structure, we could answer the original problem: Delete$(u,v)$ would be implemented by calling Split$(u,v)$, and SameComponent$(u,v)$ would be implemented by testing whether Find$(u) = $ Find$(v)$.

So, is there an efficient Split-Find data structure?

It sounds like you're looking for "decremental connectivity". The fastest result I could find was Wulff-Nilson's "Faster deterministic fully-dynamic graph connectivity", which "supports updates (edge insertions/deletions) in $O(\log^2 n/ \log \log n)$ amortized time and connectivity queries in $O(\log n/ \log \log n)$ worst-case time, where $n$ is the number of vertices of the graph."


How was $T(N)$ derived for this function? I’m struggling to understand how $T(N)=C_1 \times N + C_2$ was derived
Assuming $C_1$ refers to l <- 0, and $C_2$ refers to return l
Shouldn’t it total $T(N)= C_1 + (N + 1) + N + C_2$, which simplifies to $T(N)= C_1 + 2N + 1 + C_2$ ?

Here, $C_1$ and $C_2$ are constants that concern several instructions:

$C_2$ corresponds to instructions executed only once l <- 0, the last executed test of while(A[l]!=NULL) and return l
$C_1$ corresponds to instructions executed several times: each test of while(A[l]!=NULL) but the last, and l<-l+1. Those are executed a total of $N$ times.

We indeed get $T(N) = C_1\times N + C_2$.


Quantified Boolean Formula vs First-order logic Is Quantified Boolean Formula (QBF) the same as First-order logic (FOL)?

Firstly, a quantified Boolean formula is a formula in quantified propositional logic (which consists of Boolean variables and quantifiers). A true quantified Boolean formula is a formula that can be made true (formulas have no free variables so they can be either true or false). Note that this term is also used for the true quantified Boolean formulas (TQBF) language which contains all true Boolean qualified formulas. Therefore, you probably had a comparison of the respective logics in mind, namely quantified propositional logic and first-order logic.

To make a connection of quantified propositional logic and first-order logic, let us consider predicate logic (that is more general, and includes first-order logic). When comparing propositional logic and predicate logic, a basic difference is that the latter includes a richer ontology: objects, functions and predicates on objects. (This allows more flexible and compact representation of knowledge, as expressing a binary predicate on a set of n terms might lead to n*n terms in propositional logic.) Having this in mind, effectively, first-order logic and quantified propositional logic add quantification to propositional and predicate logic, respectively.

Consequently, from the perspective of the comparison of the formal systems represented by these two logics, one might consider their expressiveness. While quantified propositional logic is restricted to Boolean variables (that might hold either true or false), first-order logic does not have such restrictions. It can model different sets of objects (terms), together with predicates and functions on them (it is most widely used to express properties in wide range of mathematical theories). Therefore, strictly speaking, first-order logic is more expressive.

One important distinction between these logics is in terms of decidability. Namely, to check whether a formula in quantified propositional logic is true is decidable (the language TQBF is decidable; more specifically, it is PSPACE-complete). Unlike quantified propositional logic, first-order logic is undecidable if the language has at least one predicate of arity at least 2 (other than equality). This means that there is no decision procedure that determines whether arbitrary formulas are logically valid. (This can be shown by encoding the statement "the Turing machine T halts on empty input", which is known to be undecidable, in first-order logic.)

Note that formulas in quantified propositional logic can be straightforwardly interpreted in first-order logic. (This is explained in more details in this answer.)


Polynomial time counter of solutions of 2SAT expression with pure literals As per the title, is there any polynomial time algorithm to count the number of satisfying arguments for a 2SAT expression with pure literals? An even shallower case: Is there any such counter when the literals in the expression are either all positive, or all negative?

Counting the number of satisfying assignments in a positive 2SAT formula is the same as counting the number of vertex covers in the corresponding graph (after removing singleton clauses). Counting the number of vertex covers is known to be $\mathsf{\#P}$-complete. See also this question on cstheory.


Is a two-opt move guaranteed to produce a non-worse tour? I have a little doubt with respect to the two-opt improvement heuristic for TSP. I understand how it works, from the Wikipedia article on 2-opt and "Heuristics for the Traveling Salesman Problem". However, from my understanding and subsequent experiments, it appears this heuristic does not give any guarantee to at least not lead to a worse tour. If this is so, I don't understand how a two-opt move is any better than a random swap of cities. I would really appreciate if this can be clarified for me. Thanks!

2-Opt is a move that doesn't guarantee to give a better tour.

We use such moves ($k$-Opt, swap, insertion,..) in local searches to look for a better tour in the neighbor of the input (which is a tour).
Local search consists of browsing all (feasible) tours that can be produced with only one move from the input.
If the input tour is not improved, we call it a local optimum which may be the optimal solution.


Why does stable matching without Gale-Shapely takes n! steps There are n men and n women. I am unable to understand how stable matching done by simply searching through all the matchings takes n! steps i.e., I cannot figure out why there are n! matchings possible.

Suppose that the group of men is $m_1,\ldots,m_n$ and the group of women is $w_1,\ldots,w_n$. Suppose that man $m_i$ is matched to woman $w_{c_i}$. Then the matching can be described by the sequence $c_1,\ldots,c_n$. Each $c_i$ is in $\{1,\ldots,n\}$, and $c_i \neq c_j$ for $i \neq j$. So $c_1,\ldots,c_n$ is a permutation of $\{1,\ldots,n\}$, of which there are $n!$.


Running time of this Program def f(n):
 i = 2
 while i < n:
  print(i)
  i = i * i

I evaluated an expression that becomes something like 2^n or 2^2^n and set that equal to when the loop breaks or (2^2^n ) (>=)n    but can't figure out how to get a runtime. Can someone show how to do complete this analysis and get a runtime?

In the loop, $i$ is repeatedly squared so it will take the values
$$
2, 2^2=4, 4^2=16, 16^2=258, \dotsc
$$
In other words, $i$ will be
$$
2^1, 2^2, 2^4, 2^8, \dots,2^{2^k}
$$
so the loop will iterate $k$ times, until $2^{2^k}\ge n$. Taking the log of this inequality twice we'll have $k\ge \log \log n$ for our running time.


Avoiding correlated values and reduced collision resistance in multiple hash states I need to design a hash function that fits this criteria:

Limited to 32-bit integer operations (for compatibility with JavaScript bitwise operations, my target system)
Produces an n-bit hash digest, greater or equal to 64-bit, with the expected collision probability of a hash of that size. Effectively combining multiple uncorrelated 32-bit states.

However, it seems care must be taken with this approach. I cannot verify it myself, but computing two 32-bit hashes using the same message but a different seed may cause more collisions than expected from a 64-bit hash, due to the two values being correlated.

This issue also seems to extends to the output of a single hash function that outputs two 32-bit results to form a 64-bit (which is exactly what I am trying to do).

I found MurmurHash64B (link to C++ code) which seemed almost ideal for my purpose. It produces a 64-bit hash using 32-bit operations at no significant performance cost.

But on the SMHasher wiki, the author mentions this about what I suspect to be the same function:

  MurmurHash2_x86_64 computes two 32-bit results in parallel and mixes
  them at the end, which is fast but means that collision resistance
  is only as good as a 32-bit hash. I suggest avoiding this variant.

Then I saw this exchange on the subject:

  Hacker News comment by martincmartin:
  Computing two 32-bit results in parallel and mixing them at the end does NOT mean collision resistance is only as good as a 32-bit hash. For that, you need to compute ONE 32-bit result, then transform it into a 64-bit result.

  Hacker News comment (reply) by finnw
  Depends whether the two 32-bit hashes are correlated with each other. If there is no correlation then a pair of 32-bit hashes is no more likely to collide than a single 64-bit hash. But this is difficult to achieve, and you should not assume (for example) running the same algorithm twice with different initial states will produce uncorrelated hashes.

So then, is this function really not as good as a 64-bit hash? A naive test: Searching for a collision in state h1 doesn't seem to cause collisions in state h2. Is it simply not sufficiently mixing the states? It only mixes h1 and h2 at the end, not within the input mixing phase.

MD5 for example which also uses 32-bit arithmetic, computes four hash states which I assume must not suffer from this issue. There also exists a MurmurHash3_x86_128 which computes a 128-bit hash using four 32-bit states and appears to mix it more thoroughly (which has no mention of being weaker by the same author).

So I am wondering how can it be shown that MurmurHash64B (or a similar function) has correlated values that could result in reduced collision resistance than expected of the digest size.

MurmurHash2_x86_64 (aka MurmurHash64B) works as follows: it computes a 32-bit value $h_1$ based on bytes 0-3, 8-11, 16-19, 24-27, etc. of the input; it computes a 32-bit value $h_2$ based on bytes 4-7, 12-15, 20-23, etc. of the input; and then it mixes and combines these two values to obtain a 64-bit hashcode, computed as a function of $h_1,h_2$.  (Here by $h_1$ I mean the value of the variable h1 at line 180 in the source code you linked to.)

There is a sense in which this has only 32-bits of collision resistance.  In particular, if we consider two inputs that are the same in bytes 0-3, 8-11, 16-19, etc., and differ only in the other bytes, then there will be a $1/2^{32}$ chance that they collide.  Why?  Because there is a $1/2^{32}$ chance that they end up with the same $h_1$ value just by chance; and they will certainly end up with the same $h_2$ value (since it depends only on bytes that are the same for both outputs); so there is a $1/2^{32}$ chance they collide.  This is the same chance of collision as for a 32-bit hash.  For a 64-bit hash, you might expect a collision probability of $1/2^{64}$.

So this is a sense in which MurmurHash2_x86_64 is less than ideal, i.e., a sense in which one might say it has only 32 bits of collision resistance.  Whether it is relevant in your practical situation is unknown.

The latest version of MurmurHash is MurmurHash3.  MurmurHash3 supports a 128-bit output.  A reasonable approach would be to compute a 128-bit hash using MurmurHash3, then discard all but the first 64 bits.


Find a grammar for this language Assume the language:
$$L=\left\{w\in\{0,1\}^*\,| \text{ w has odd length and 111 right in the middle}\right\}$$

This is my attempt for constructing a grammar $G$ for this language:

$$G: S \rightarrow A111B,\, A \rightarrow 01B |10B|00B|11B,\, B  \rightarrow 01A |10A|00A|11A$$

This process adds random even strings of $\{0,1\}^*$ to both sides of $111$.

However, it must assign $\varepsilon$ to $A$ and $B$ simultaneously, for the even strings to be of equal length and for $111$ to stay in the middle of the resulting string.

How can I achieve the last step?

If you do not want a more complicated (non-context-free) grammar, you cannot coordinate the two steps. The trick is to work the other way around: generate the two "side strings" from one central non-terminal and put the $111$ in the end.

Further problems with your grammar are:

you miss $111$,
since your intention is to generate 2 symbols both at the front and at the end, you would add 4 instead of 2 and thus miss every second odd number.

I propose the grammar
$$[ \{0,1\}, \{S\}, R, S]$$
where $R$ has the rules
$S\rightarrow 0S0\ |\  1S1\  |\  0S1\  |\  1S0\  |\  111$.


How to find First in a left recursive grammar? One of the basic requirements for a grammar to be LL(1) is : For every pai r of productions A -> X | Y, First(X) and First(Y) should be disjointed.
If a grammar is left-recursive, then the set of productions will contain at least one pair of the form A -> AX|B; and hence, First(AX) and First(Y) will not be disjoint sets, because everything in the First(Y) will also be in the First(AX).
Source : Compiler Design by Dr. O.G. Kakde

How can I calculate the First of (AX) because First(A) = First(AX) U First(Y) goes recursively forever ?

Here is how to apply the production rule $ A\to AX$ to compute $\text{first}(A)$.

  When $\epsilon\in\text{first}(A)$, add all (non-$\epsilon$) members of $\text{first}(X)$ to $A$.

More generally, if there is a rule $A\to AX_1X_2\cdots X_n$,

  When $\epsilon\in\text{first}(A)$, add all non-$\epsilon$ members of $\text{first}(X_1)$ to $A$. When $\epsilon\in\text{first}(A)$ and $\epsilon\in\text{first}(X_1)$, add all non-$\epsilon$ members of $\text{first}(X_2)$ to $A$.
  When $\epsilon\in\text{first}(A)$ and $\epsilon\in\text{first}(X_1), \text{first}(X_2)$, add all non-$\epsilon$ members of $\text{first}(X_3)$ to $A$, and so on.

The rules above are just specializations of the general rules. What is particular in this situation is that there is no effect when you add all members of $\text{first}(A)$ to $\text{first}(A)$. There is no concern about infinite recursion.

Here is a left-recursive grammar.
$\quad S \to SX\mid Y$
$\quad X \to x$
$\quad Y \to y$
We compute as the following.

$\text{first}(X)=\{x\}$ by the rule $X\to x$.
$\text{first}(Y)=\{y\}$ by the rule $Y\to y$.
$\text{first}(S)=\{y\}$ by the rule $S\to Y$.
Since $\epsilon\not\in\text{first}(S)$, ignore rule $S\to SX$.

Here is another left-recursive grammar.
$\quad S \to SX\mid Y$
$\quad X \to x \mid \epsilon$
$\quad Y \to y \mid \epsilon$
We compute as the following.

$\text{first}(X)=\{\epsilon, x\}$ by the rules $X\to x \mid \epsilon$.
$\text{first}(Y)=\{\epsilon, y\}$ by the rules $Y\to y\mid\epsilon$.
add $\epsilon, y$ to $\text{first}(S)$ by the rule $S\to Y$.
Since $\epsilon\in\text{first}(S)$, add $x$ to $\text{first}(S)$ by the rule $S\to SX$. So $\text{first}(S)=\{\epsilon, x, y\}$

Exercise. Compute the first set of the following grammar.
$\quad E\to E - T \mid T$
$\quad T\to T * F \mid F$
$\quad F\to (\ E\ ) \mid I$


Is there any K-means analog for regression, not culstering? Good day
Is there any regression Machine learning model, based on k-means?
Example (Zillow's Zestimate):
I have a lot of houses(with features like sq.feet and location) and prices. I want to estimate price for a new house by averaging k neighbors.

You could use $k$-nearest neighbors regression.  It's not based on $k$-means, but it is based on estimating the price of a new house by averaging $k$ neighbors (in particular, the $k$ most "similar" houses in the training set, for some measure of similarity that you define).  $k$-nearest neighbors is supported in many machine learning toolkits.

See https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm.


Determining the complexity of calculating n-th root of an integer, and performing modulo arithmetic? For a while now, I have been struggling to find a source explaining the complexity of the following 2 elementary operations

Calculating the $n^\text{th}$ root of an integer $x$,
$$
\sqrt[\leftroot{-3}\uproot{3}n]{x}
$$
Checking whether
$$
a \equiv b \mod r
$$
for $a,b,r \in \mathbb{N}$

I now think I may have come close to finding an answer to the second of these problems, but I am not certain.

On pages 10-11 of the book Édouard Lucas and Primality Testing (by Hugh C. Williams), the following statement is made:

  For any $m$ and $a,b$ with $0 < |a|, |b| < m$ calculating
  $$
r \equiv ab \mod m
$$
  can be done in $O((\log m)^2)$ operations.

Am I to assume, based on this, that operation 2. has complexity $O((\log m)^2)$?

I also suspect that operation $1$ has complexity $O((\log m)^2)$, but I have no justification for this. Could someone please also tell me whether this is correct?

You can multiply two n-bit numbers trivially in $O(n^2)$, but using FFT (fast fourier transform) you can get the time down to $O (n \log n \log \log n)$. Lets call this time T(n).

For the modulo, you would calculate ab, then z = floor (ab / m), then r = ab - mz. If mz > ab then z was too large, so decrease z by 1 and subtract m from mz.

To find ab / r, you can use Newton iteration. There is a clever way to arrange this without any divisions, just multiplications. This is an iterative method with about log n iterations, but only the last iteration needs the full precision, so the total time is O (T(n)).

Things are even better if you want $z = a^{1/b}$ rounded to an integer, and to check if it is an integer. Again you use Newton iteration, but you only need a result with a bit over n / b bits precision. The result itself is a bit harder to calculate, requiring about log b multiplications, so the time to calculate this is $O (T (n / b) \log b)$. If you can't decide whether z is an integer or not due to precision, you can calculate $round(z)^b$ in T(n).


Maintain statistics over a sliding window (robust & efficient) I am looking for an algorithms to maintain several statistics over a sliding window. The setup is as follows: There is a datastream consisting of (real value,timestamp) tuples. The values for the last x seconds are stored. In each iteration at least one new tuple arrives and between zero and more values are retired.
Now I want to maintain mean and variance without recomputing everything from scratch. There are methods if values are never retired, e.g. Welford's method. But what if values are retired?

The second problem I am facing is, how to compute covariance between two sliding windows in a similar fashion?

Are you aware of a solution or references?

To compute the mean of all the values in your window, separately compute (a) the sum of all the values in the window, and (b) a count of the number of values in the window.

To keep track of the sum of all the values in the sliding window, each time you receive a new value, add it to the sum.  Each time a value leaves the window, subtract it from the sum.  Now you'll always have a sum of the values in the window.

To keep track of the number of values in the window, each time you receive a new value, increment the counter.  Each time a value leaves the window, decrement the counter.

Finally, the mean is the sum divided by the count.

To keep track of the variance, you need the count, the sum of the values, and the sum of the squares of the values.  You can keep track of the sum of the squares of the values in the window in the same way (when a new value arrives, add its square to the running sum; when a value leaves, subtract its square).  These three values are enough to let you compute the variance of the values in the sliding window.

Note that when using the sum of squares method to compute the variance, you will need to compute the three intermediate values to enough digits of precision.  If you don't have enough digits of precision for those intermediate values, then you get a very inaccurate estimate.  This is the robustness problem that is mentioned in the blog post you link to and that is addressed by Welford's method.  However, there is another pragmatic way to address it that will work for most practical settings: just compute those three intermediate values to more digits of precision.

For the covariance between $x_1,\dots,x_n$ and $y_1,\dots,y_n$, you need to know the sum of the values $x_i$, $x_i^2$, $y_i^2$, $x_i y_i$, and the count $n$.  So, it's basically the same principle as above, but now there are five intermediate values you need to maintain, instead of just three.


Why we do isomorphism, automorphism and homomorphism? What are the key differences between these three terms isomorphism, automorphism and homomorphism in simple layman language and  why we do isomorphism, automorphism and homomorphism ?

Isomorphism formalizes the notion of equal graphs. For example on this figure you see three isomorphic graphs

More formally, an isomorphism of graphs $G_1$ and $G_2$ is a bijection $f:V(G_1) \mapsto V(G_2)$ that preserves adjacency. That is to say:

$$u \sim_{G_1} v \iff f(u) \sim_{G_2} f(v)$$

It is not hard to find such a bijection for every pair of graphs on the picture.

Now if $G_1 = G_2$ then the obtained mapping becomes an automorphism - a isomorphism from the graph to itself.

You might ask what is the intuitive notion of graph automorphism  and the answer is that it gives you some kind of information of which vertices are "equivalent" in a graph. In other words if there is an automorphism of $f$ of graph $G$ such that the vertex $v$ is mapped to vertex $u$ then in a way the neighbourhood of $u$ and $v$ "looks" the same.

This in turn leads to the notion of graph symmetries. A graph $G$ is said to be vertex-transitive if for every pair of vertices $u,v \in V(G)$ there is an automorphism $f:V(G) \mapsto V(G)$ such that $f(u) = v.$ An example of a vertex-transitive graph is the Petersen graph

and as you can see the graphs "looks" pretty symmetric. That is precisely because it has "many" automorphisms of the described type.

Graph homomorphisms are usually not studied by layman and are more or less of theoretical purposes. For example they are closely related to the notion of vertex-colourings.  See also Hadwiger Conjecture


An example of a context-sensitive grammar for a given language Consider this language: $L = \{a^nb^ma^nb^m \mid n,m \ge 1\}$. Can we give for this language a context-sensitive grammar?

Your request is easily served!

$$\begin{array}{lcl}
   &S  &\to &abab\\
   &ba &\to &bbBa\\
   &Ba &\to &aB\\
   &Bb &\to &bb\\
   &ba &\to &bAaa\\
   &bA &\to &Ab\\
   &aA &\to &aa\\
\end{array}$$

There is some theory to help you make sense of this solution.

Let us first consider a simpler language that manifests the same difficulty: $L = \{a^nb^ma^n ∣
n,m \ge 1\}$. Imagine it as a sea of $b$ between the shores of $a$, if you please.

We would like to grow the shores so that they are always the same size. One immediate way is to
have a collection of rules like $a + b^m + a \to aa + b^m + aa $. But we see it will not serve our
needs, as, our collection being finite (grammars are required to have a finite set of rules),
there is always some choice of $m$ that is not accomodated. So evidently there is a trick.

The trick is to introduce a non-terminal "ship" that will sail across the sea and deliver the
information from one shore to the other. When the left shore grows, it will send a ship to the
right shore, and when the right shore receives a ship, it will also grow, thus maintaining the
required equilibrium. How can we sail a ship? $Ba \to aB$ is one way to move it one unit of sea
rightwards. What remains to be put in place is a shipyard $ba \to bbBa$ and a port $Bb \to bb$.

Here is what we get:

$$\begin{array}{lcl}
   &S  &\to &bab\\
   &ba &\to &bbBa\\
   &Ba &\to &aB\\
   &Bb &\to &bb\\
\end{array}$$

I am sure you can see how to extend this to your original language: you will need the sea
people to also send some sort of messenger golems $A$ across the land to the sea on the other side of
$b$.

Happy adventures in fantasy grammar land!


How are alphabetic characters programmed into a computer? I'm no cs student, I'm a programmer. I have a couple of questions and a few assumptions that I will make here (correct me if I'm wrong please).

From my understanding is that all the sequences of 1 and 0's that computers execute are just representations of actual data or instructions that tell other hardware on a system what to do like telling a graphic card to change a pixels color on the monitor.

01100001 being the representation of the letter "a" and that this sequence of bits has been chosen by the fathers of computing/ascii or what have you to represent that letter, it could just as well have been some other sequence right?

All computer systems have agreed that those bits mean the letter "a" for all of the computers around the globe to be interoperable, if there were no standards in place for this the internet would be a mess.

What I want to know is: where is the information stored on a computer that tells it that these sequences of bits here mean/represent the character "a"? Is it in the OS or directly on the motherboard or am I just completely wrong?

It isn't stored anywhere. 01100001 could represent anything. It could be the ASCII character "a" or it could be the integer 97 or it could even be something different entirely. It's up to the programmer to tell the computer what to do with 01100001, for instance by supplying a font file that tells it how to map binary sequences to the instructions to draw a character on the screen. Often this is taken care of in libraries but the OS and motherboard have no idea that 01100001 represents "a".


Can we specify the pumping length while applying pumping lemma In all the examples I have seen, the pumping length $p$ is not specified. The string is a pattern that somehow has the $p$. E.g. when proving $L=\{a^n b^n c^n | n \geq 0\}$ is not context free, we assume the string $s \in L$ has the form $a^pb^pc^p$, and continue.

Do we have to select such a general pattern?

E.g. Can I just say, $s=aaabbbccc$, where $p=3$, and reason continuing this?

The pumping lemma states that if $L$ is regular, then $\exists p.\forall w.\exists x,y,z. w=xyz \wedge$ they can be "pumped"

Thus to show that $L$ is not regular, we must show $\neg(\exists p.\forall w.\exists x,y,z. w=xyz \wedge$ they can be "pumped"$)$
which is equivalent to $\forall p. \exists w. \forall x,y,z.w=xyx\wedge($ all other requirements given in the lemma$)\rightarrow\exists.n$ they cannot be "pumped" n times

This shows us its nessecary to never assume what p is.

Furthermore, it explains why we need to find only one word (which depends on p).


Prove that there is a path of lenght k+1 in a graph with minimum degree k I am faced with this question.

  Let $G$ be a graph in which each vertex has degree at least $k$. Show
  that there is a path of length $k$ in $G$ - that is, a sequence of $k+1$ distinct vertices $v_0, v_1, ..., v_k$ such that for $0 ≤ i < k$, $v_i$ is connected to $v_{i+1}$ in $G$.

I started attacking it this way:

If $G$ has a vertex of degree atleast $k$, it has atleast $k+1$ vertices. That is, $G$ can have $|v| \geq k+1$

In the case where $|v| = k+1$, the graph is a fully connected graph of $k+1$ vertices, which trivially has a path of length $k+1$.

I am not able to prove the cases where $|v| \geq k+2$

Hint. Build up the path, using the minimum degree condition to show that you can extend it as much as you need to.


Find the n best choices while maximizing value Given:

A list of slots (A, B, C, ...)
Every slots supports a list of choices (C0, C1, C2, C3...)
Every choice has a value

All slots must be filled with at most n different choices. The sum of the values should be maximized.

Example:

Choice-Values:

C0 = 4
C1 = 3
C2 = 2
C3 = 1

Slots:

A: C1, C3
B: C0, C1, C3
C: C2, C3
D: C0, C1, C2, C3
E: C1, C2, C3

Solution for n = 1: C3, C3, C3, C3, C3

Solution for n = 2: C1, C1, C2, C1, C1

Question

Is this a known problem?

It reminds me of a mix between the knapsack problem and of a scheduling problem, as I want to get the maximum value while filling a certain space using a limited set of items.

Thanks to Yuvals comment i found this site discussing the set cover problem. It's exactly what I needed.


Closed-form Expression of the Expected value of the Cost of D&C Algorithm? Let there is a binary-string, $B$, of length $N$. The probability of occurrence of 0 and 1 in this binary-word is $p$  and $q$ , respectively. Each bit in the string is independent of any other bit.

There is an algorithm (divide and conquer) which finds the location of 1’s in a given binary-string, in Q # of steps (cost).

I am looking for some close-form solution of the expected # of steps,$E[Q]$, with given probabilities $p$ and $q$ for a string of length $N$.

For instance, for $N=4$ the cost ,${{Q}_{i}}$,  for each possible word is:
[\begin{matrix}
   {{B}_{i}} & {{Q}_{i}} & {{P}_{i}}  \\
   0000 & 1 & {{p}^{4}}  \\
   0001 & 5 & {{p}^{3}}q  \\
   0010 & 5 & {{p}^{3}}q  \\
   0011 & 5 & {{p}^{2}}{{q}^{2}}  \\
   0100 & 5 & {{p}^{3}}q  \\
   0101 & 7 & {{p}^{2}}{{q}^{2}}  \\
   0110 & 7 & {{p}^{2}}{{q}^{2}}  \\
   0111 & 7 & p{{q}^{3}}  \\
   1000 & 5 & {{p}^{3}}q  \\
   1001 & 7 & {{p}^{2}}{{q}^{2}}  \\
   1010 & 7 & {{p}^{2}}{{q}^{2}}  \\
   1011 & 7 & p{{q}^{3}}  \\
   1100 & 5 & {{p}^{2}}{{q}^{2}}  \\
   1101 & 7 & p{{q}^{3}}  \\
   1110 & 7 & p{{q}^{3}}  \\
   1111 & 7 & {{q}^{4}}  \\
\end{matrix}]
From the discrete probability theory, we can evaluate the expected cost of the above case ,$N=4$,as follow $\begin{align}
  & \therefore E[Q]=\sum\limits_{i=0}^{{{2}^{N}}-1}{{{Q}_{i}}({{p}^{N-i}}}{{q}^{i}}) \\
 & \Rightarrow E[Q]=\sum\limits_{i=0}^{15}{{{Q}_{i}}({{p}^{N-i}}}{{q}^{i}}) \\
 & \Rightarrow E[Q]={{p}^{4}}+4\times 5\times {{p}^{3}}q+2\times 5\times {{p}^{2}}{{q}^{2}}+4\times 7\times {{p}^{2}}{{q}^{2}}+4\times 7\times p{{q}^{3}}+1\times 7\times {{q}^{4}} \\
 & \Rightarrow E[Q]={{p}^{4}}+20{{p}^{3}}q+10{{p}^{2}}{{q}^{2}}+28{{p}^{2}}{{q}^{2}}+28p{{q}^{3}}+7{{q}^{4}} \\
\end{align}$

However, for very large values of N, say 1024, it is computationally not possible to evaluate the cost of each possible binary string (i-e ${{2}^{1024}}=\text{1}\text{.79}\times \text{1}{{\text{0}}^{308}}$ binary words). So, this is the problem I am stuck in.

Is it possible to deduce some analytical/ close-form expression for evaluating the expected value of the cost of this algorithm for a given length N and probabilities p and q (instead of brute-force method defined above)?

I will be very thankful, if someone could help in this regard.

ADDITIONAL INFORMATION:

Divide & Conquer Algorithm:
    Lets take 0000 0001, for instance:

First question: Is it (i-e 0000 0001) equal to ZERO (i-e 0000 0000) ? The answer is No, for our case.
Then divide the original 8 bit word into two 4 bit segments, and again ask the same question for each of the two 4 bit words. So for our case it would be YES for the first segment (0000) and NO for the other segment (0001)?
Now, this time I will be questioning only the segment where I got NO. In our case it was 0001. Then, I will now again divide this 4-bit segment into two segments and pose the same question. Hence, is 00 equal to ZERO? answer : YES. For the other segment , 01, the answer is NO.
This is the final step. I will again divide the 2-bit word into two 1-bits, i-e 0 and 1. So, my first question: is 0 equal to 0? answer is YES. And for the other remaining bit, is 1 equal to 0? Answer is NO.

So, I asked a total of 7 questions to find the location of 1 in a binary word of 0000 0001. Similarly, we will go through other binary words.

Efficient Way for evaluating the cost of Above algorithm:
(courtesy to Yuval Filmus)

Here is how to calculate the cost of the algorithm. Start with the bit vector $x$, and consider the following operation $O$, which divides $x$ into pairs of bits and computes their ORs. Thus $|O(x)| = |x|/2$. Compute a sequence $O(x),O(O(x)),O(O(O(x))),\ldots$ until you get a vector of width $1$. Count the total number of 1s in the sequence. If you got $N$, then the cost is $2N+1$.

For example, suppose $x=0101$. Then the sequence is
$$ 11,1, $$
and so $N = 3$ and the cost is $7$.

Expectation is additive, so your expectation equals
$$ E := 2E[w(O(x))] + 2E[w(O(O(x)))] + \cdots + 2E[w(O(\cdots(x)\cdots))] + 1, $$
where $w(\cdot)$ is Hamming weight.
Let's calculate $E[w(O(x))]$, again using the fact that expectation is additive. The probability that the $i$th bit of $O(x)$ is $1$ is exactly $1-p^2$, and there are $N/2$ of them, therefore $E[w(O(x))] = (N/2)(1-p^2)$. Similarly, the probability that the $i$th bit of $O(O(x))$ is $1$ is exactly $1-p^4$, and there are $N/4$ of them, and so $E[w(O(O(x))] = (N/4)(1-p^4)$. If $N = 2^n$, then we get
$$ E = 2^n (1-p^2) + 2^{n-1}(1-p^4) + \cdots + 2(1-p^{2^n}) + 1.$$
We can simplify this slightly by summing the geometric series:
$$ E = 2^{n+1}-1 - 2^n p^2 - 2^{n-1} p^4 - \cdots - 2p^{2^n}. $$


Infinite languages and undecidable languages I'm having a problem with proving the following statement:

For every infinite language $L$, does there exists an infinite language $L'  \subseteq L$ such that $L'$ is not decidable?

The set $\{L' : L' \subseteq L\}$ is an uncountable set of languages, and since there is only countably many decidable languages, it has to contain an undecidable language. (You can get a concrete $L'$ by a diagonal argument.)


Regularity of language obtained by interleaving $a,b$ Let $L$ be a regular language on an alphabet $\Sigma$. and let $L^{ab} = \{\sigma_1a\sigma_2b...\sigma_n \mid \sigma_1...\sigma_n \in L\}$ be the language obtained by add between any two letters of any word of $L$ the letters $a$ and $b$, except before the first and after the last. Prove that $L^{ab}$ is regular.

I tried to prove it by induction on the length of $r$, the regular expression that the language corresponds to. There are 3 cases, the case of $r$ is union I understand but in the cases of concatenation and *, the induction doesn't work.

There are several issues here. Let's first see what happens if you need to insert only $a$-s. We will construct an operator $A[r]$ which generates a regular expression for $$\{\sigma_1 a \sigma_2 a \ldots a \sigma_n : \sigma_1 \ldots \sigma_n \in L[r], n \geq 1\}.$$ If $\epsilon \in L[r]$ (which can be determined inductively), then it would need to be added explicitly as an additional final step. The construction is inductive:

$A[\epsilon] = A[\emptyset] = \emptyset$, $A[\sigma] = \sigma$.
$A[r_1 + r_2] = A[r_1] + A[r_2]$.
$A[r_1r_2] = A[r_1] a A[r_2] \stackrel?+ A[r_1] \stackrel?+ A[r_2]$, where the first additional term is present if $\epsilon \in L[r_2]$, and the second if $\epsilon \in L[r_1]$.
$A[r^*] = (A[r]a)^*A[r]$.

When you have both $a$-s and $b$-s the general idea is the same, but you have to keep track of the parity of the generated words. We construct operators $E[r],O[r]$ for extracting only the words of even length and odd length (respectively) in $L[r]$. The construction is inductive:

$E[\epsilon] = \epsilon$, $O[\epsilon] = \emptyset$.
$E[\sigma] = \emptyset$, $O[\sigma] = \sigma$.
$E[\emptyset] = O[\emptyset] = \emptyset$.
$E[r_1 + r_2] = E[r_1] + E[r_2]$, $O[r_1 + r_2] = O[r_1] + O[r_2]$.
$E[r_1r_2] = E[r_1]E[r_2] + O[r_1]O[r_2]$, $O[r_1r_2] = O[r_1]E[r_2] + E[r_1]O[r_2]$.
$E[r^*] = E[r]^*(O[r]E[r]^*O[r])^*E[r]^*$, $O[r^*] = E[r^*] O[r] E[r^*]$.

At this point we have all the ideas required to solve your actual exercise. That's a task for you.


Transitive dependency in 3NF Came across this question : State whether True or False

  A prime attribute can be transitively dependent on a key in 3NF

Answer: True
How could this be true? Because as far as I know, A relation initially in 1NF is said to be in 3NF when partial and transitive dependencies have been eliminated. Correct me if I'm wrong.
Also, would it be correct to say that given a relation which doesn't have any non prime attribute along with no partial dependencies, then the relation is in BCNF ?
(I don't have any knowledge beyond BCNF).

An accepted definition of Third Normal Form is that any non-trivial dependency with a single attribute on the right part must have a superkey as left part, or the right part must be constituted by a prime attribute.

In other words, if you have a dependency with a prime attribute on the right part, that dependency does not violates the 3NF.

For your second question, a relation is in BCNF if any non-trivial dependency has a superkey as left part. If a relation does not have partial dependencies, and all the attributes are prime, this means that no dependency exists with attributes that are not a full key or that are not constituted by non-prime attributes. So, the answer is yes, that relation is in BCNF.


Does the subset sum problem remain $NP$ complete when we increase word size and restrict number of words? Is the problem

  'Given $m=\big\lceil{n^b}\big\rceil$ with $b\in(0,1)$ integers $a_1,\cdots,a_m$ each with $\lceil\log_2 |a_i|\rceil=\big\lceil n^a\big\rceil$ with $a\in[1,\infty)$ is there a subset that sums to zero?'

$NP$ complete?

The reason I ask is this problem can be solved in $2^{O(n^b)}=2^{o(n)}$ time.

Your problem is not really well-defined, since it's not clear what is the parameter $n$. That said, under any reasonable interpretation, your problem is still NP-complete, as can be shown by padding. Given an instance of subset sum, we can create an instance of your restricted subset sum by adding a lot of zeroes to the set.

Subset sum is solvable in polynomial time if the weights are polynomially bounded. More generally, if there are $m$ integers and each one is bounded in magnitude by $B$, then subset sum can be solved in $O(mB)$. In your case the weights are not polynomially bounded.


How does strong NP-completeness agree with encoding complexity? I've recently read about the concepts of weak and strong NP-completeness, but faced a problem in wrapping my head around them. I've understood that problems which have numerical parameters (like discrete knapsack) and can be solved polynomially in the values of those parameters (which implies exponential time in their binary encoding) are said to be weakly NP-complete. There exists no known polynomial-time computable mapping from any NP-complete problem which produces a unary encoded input to another NP problem like the knapsack problem, where the numerical parameters are polynomially bounded in the input length of the original problem. On the other hand, problems which are known to be NP-complete when restricted to the subset of instances where the numerical parameters are polynomially bounded in the input length of the original problem are called strongly NP-complete, but there isn't any known pseudopolynomial algorithm for those. Whether the classes of weakly and strongly NP-complete problems are the same is unknown and depends on the outcome of the P-NP question.
Now, my confusion stems from the chosen encoding. Weakly NP-complete problems are thought not to be NP-complete in their pseudopolynomially solvable instances. Those, however, are only polynomial because their input is provided in unary encoding, which avoids the exponential unfolding of the numerical values from binary format. So, an alternative way of defining weak and strong NP-completeness would simply depend on the existence of a polynomial algorithm when provided the input in unary encoding. But how could any problem being provided unary encoded input be NP-complete, that is, possess a Karp reduction (i.e. computable in polynomial time) from any other NP-complete problem? Since the original problem cannot be assumed to be given in unary encoding, its binary encoding has to be unfolded into unary encoding during the mapping, which would always require exponential time, wouldn't it? This holds even if we only require the numeric parameters of the problem be given in unary encoding, since we must assume the length of numbers to grow with the problem size. But then, this would imply that there cannot be any strongly NP-complete problems, and that any form of NP-completeness must be a weak one. Since the opposite is known, I clearly must've made an error in my reasoning, but I cannot spot it.

I figured it out after looking at this paper. My error in thinking came from generally assuming some direct (i.e. linear) relationship between the numbers in the source problem and those in the target problem to which the reduction is mapping. However, producing unary output in the reduction in polytime requires that such a connection must only exist in those cases where the source problem is a number problem which has its numerical values polynomially bound in its binary input length. If, on the other hand, the source problem is allowed to have exponentially large numbers, the #bits required to encode the numbers in the target problem may only scale logarithmically with the #bits required for the numbers in the source problem, ensuring polynomial boundedness of the maximum value and enabling changing from binary to unary encoding in polytime.


Is the extension of every undecidable theory undecidable? While it is not the case that the extension of every decidable theory is decidable, is it true that:

the extension of every undecidable theory undecidable?

In other words, given an undecidable theory A, is it enough to show

$$A \subseteq B$$

to prove that B is undecidable?

No. A theory is a set of theorems. The set of all formulas is a decidable theory and it is an extension of all theories, including undecidable ones. It is also very inconsistent and thus useless in practice, but it is a counter-example to your claim.


Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded? Does the difficulty of a strongly NP-hard or NP-complete problem (as e.g. defined here) change when its input is unary instead of binary encoded?

What difference does it make if the input of a strongly NP-hard problem is unary encoded? I mean, if I take for instance the weakly NP-complete Knapsack problem, it is NP-complete when binary encoded but can be solved in polynomial time by dynamic programming when unary encoded. Maybe it has some implications for hardness of higher levels of the polynomial time heirarchy?

Does the notion of strongly ...-hard also hold for other complexity classes, e.g. higher classes of the polynomial time hierarchy?

I previously asked this question at stackoverflow.com but it was pointed out that it is more appropriate here.

A problem size of $N$ encoded in unary is size $N$ and $\log N$ if binary. If the time taken is $F(N)$, this is $F(\text{size})$ in the first case and $F(2^{\text{size}})$ in the second case. So an algorithm that is polynomial for the first case will probably be exponential for the second. The encoding of the problem can so change the complexity of an algorithm radically.


Determine time given algorithmic complexity as input grows? Consider the time required to solve a problem, represented by f(n), and for sufficiently large inputs of size k, the time required to solve a problem is t. What is the typical method of determining how long, in terms of t, is necessary to solve a problem, for different kinds of f(n) and k?

For example, when f(n) is Θ(n), and the input is 2k, we know that the time is approximately 2t. But what is the standard method of determining the time, in terms of t, for problems like this? For example:

When f(n) is Θ(n3) and the input is k2 ?
f(n) is Θ(2n) and the input size is k+3 ?
f(n) is Θ(lg n) and the input size is 4k ?
f(n) is Θ(n!) and the input size is k+2 ?

This question is not asking for answers to those scenarios per se, rather, how to go about expressing the time, in terms of t, given the parameters above.

The standard method is to heuristically assume that a bound of the form $\Theta(g(n))$ can be approximated by $Cg(n)$ for some constant $C$, though in some cases this approximation is not justified, and the "constant" $C$ fluctuates (but is bounded on both sides).

Considering your first example, if $f(n) \approx Cn^3$ then $f(k^2) \approx Ck^6 = (Ck^3)^2/C \approx f(k)^2/C$. Unfortunately, the dependence on $C$ cannot be eliminated, but $C$ can be approximated empirically, though you should take such results with a grain of salt.


In-place algorithm for interleaving an array You are given an array of $2n$ elements

$$a_1, a_2, \dots, a_n, b_1, b_2, \dots b_n$$

The task is to interleave the array, using an in-place algorithm such that the resulting array looks like

$$b_1, a_1, b_2, a_2, \dots , b_n, a_n$$

If the in-place requirement wasn't there, we could easily create a new array and copy elements giving an $\mathcal{O}(n)$ time algorithm.

With the in-place requirement, a divide and conquer algorithm bumps up the algorithm to be $\theta(n \log n)$.

So the question is:

  Is there an $\mathcal{O}(n)$ time algorithm, which is also in-place?

(Note: You can assume the uniform cost WORD RAM model, so in-place translates to $\mathcal{O}(1)$ space restriction).

Here is the answer which elaborates upon the algorithm from the paper linked by Joe: http://arxiv.org/abs/0805.1598

First let us consider a $\Theta(n \log n)$ algorithm which uses divide and conquer.

1) Divide and Conquer

We are given

$$a_1, a_2, \dots , b_1, b_2, \dots b_n$$

Now to use divide and conquer, for some $m = \Theta(n)$, we try to get the array

$$ [a_1, a_2, \dots , a_m, b_1, b_2, \dots, b_m], [a_{m+1}, \dots, a_n, b_{m+1}, \dots b_n]$$

and recurse.

Notice that the portion $$ b_1 , b_2, \dots b_m, a_{m+1}, \dots a_n$$ is a cyclic shift of

$$ a_{m+1}, \dots a_n, b_1 , \dots b_m$$

by $m$ places.

This is a classic and can be done in-place by three reversals and in $\mathcal{O}(n)$ time.

Thus the divide and conquer gives you a $\Theta(n \log n)$ algorithm, with a recursion similar to $T(n) = 2T(n/2) + \Theta(n)$.

2) Permutation Cycles

Now, another approach to the problem is the consider the permutation as a set of disjoint cycles.

The permutation is given by (assuming starting at $1$)

$$ j \mapsto 2j \mod 2n+1$$

If we somehow knew exactly what the cycles were, using constant extra space, we could realize the permutation by picking an element $A$, determine where that element goes (using the above formula), put the element in the target location into temporary space, put the element $A$ into that target location and continue along the cycle. Once we are done with one cycle we move onto an element of the next cycle and follow that cycle and so on.

This would give us an $\mathcal{O}(n)$ time algorithm, but it assumes that we "somehow knew what the exact cycles were" and trying to do this book-keeping within the $\mathcal{O}(1)$ space limitation is what makes this problem hard.

This is where the paper uses number theory.

It can be shown that, in the case when $2n + 1 = 3^k$, the elements at positions $1$, $3, 3^2, \dots, 3^{k-1}$ are in different cycles and every cycle contains an element at the position $3^m, m \ge 0$.

This uses the fact that $2$ is a generator of $(\mathbb{Z}/3^k)^*$.

Thus when $2n+1 = 3^k$, the follow the cycle approach gives us an $\mathcal{O}(n)$ time algorithm, as for each cycle, we know exactly where to begin: powers of $3$ (including $1$) (those can be computed in $\mathcal{O}(1)$ space).

3) Final Algorithm

Now we combine the above two: Divide and Conquer + Permutation Cycles.

We do a divide and conquer, but pick $m$ so that $2m+1$ is a power of $3$ and $m = \Theta(n)$.

So instead on recursing on both "halves", we recurse on only one and do $\Theta(n)$ extra work.

This gives us the recurrence $T(n) = T(cn) + \Theta(n)$ (for some $0 \lt c \lt 1$) and thus gives us an $\mathcal{O}(n)$ time, $\mathcal{O}(1)$ space algorithm!


Interval extensionality? For example, in the proof of lemma 6.4.1 in the HoTT book, a function inductively defined over a function is simply applied on paths loop and refl, and then a path between loop and refl is used (presumably by congruence via f) to construct a path between f loop and f refl:

  Suppose that loop = refl base. [...] with x : A
  and p : x = x, there is a function f : S1 → A defined by f(base) :≡ x and f(loop) := p, we have

p = f(loop) = f(refl base) = refl x.

But in a cubical setting, things are not so clear-cut. f(loop) is not well-typed, only f(loop i) is, for some i : I. But then that above proof becomes

p = <i> f (loop i) = <i> f (refl base i) = refl x

but doesn't that need some kind of "interval extensionality" in the middle   step? What exactly is the justification of the middle step in cubical type theory? I can see how to prove ∀ i → f (loop i) = f (refl base i), but how does one "lift" that to <i> f (loop i) = <i> f (refl base i)?

Originally I was going to give an assurance that something like your extensionality principle must hold, but I decided to puzzle out enough cubical Agda to actually demonstrate the proof.

However, I should say that your all : ∀ i → f (loop i) = f (refl base i) is actually a digression. This is equivalent to a square with arbitrary sides, which looks like this:

$$
\require{AMScd}
\begin{CD}
x @>all(0)>> x \\
@VpVV \Rightarrow @VVreflV \\
x @>>all(1)> x
\end{CD}
$$

but something with type p ≡ refl is actually more uniform than that, because if e has that type, then e i : x ≡ x regardless of i, which is more uniform than the above square (where e i : all i0 i ≡ all i1 i), and is equivalent to a square of the form:

$$
\begin{CD}
x @>refl>> x \\
@VpVV \Rightarrow @VVreflV \\
x @>>refl> x
\end{CD}
$$

But, if we have loop ≡ refl, we already have this sort of square, and applying f point-wise produces a new square of this type. So, the following code is accepted:

module Path
    (S1 Z : Set)
    (base : S1)
    (loop : base ≡ base)
    (f : S1 → Z)
    (x : Z)

    (sq : loop ≡ refl)
  where
  rfl : base ≡ base
  rfl = refl

  z : Z
  z = f base

  p : z ≡ z
  p i = f (loop i)

  zrfl : z ≡ z
  zrfl = refl

  hsq : p ≡ zrfl
  hsq j i = f (sq j i)

So, the bit in the HoTT book is just a consequence of the composition of 'functions'.

The more arbitrary square can be expressed using the PathP type, which is also written _[_≡_] in cubical Agda, and the proof of equivalence to the ∀ type is:

module Square
    (A : Set)
    (x y : A)
    (e₁ e₂ : x ≡ y)
    (lines : ∀ i → e₁ i ≡ e₂ i)
  where
  f₀ : x ≡ x
  f₀ = lines i0

  f₁ : y ≡ y
  f₁ = lines i1

  square : (λ i → e₁ i ≡ e₂ i) [ f₀ ≡ f₁ ]
  square i j = lines i j

If you want to fool around with cubical Agda yourself to try this out interactively, I've been using a recent Agda from the development branch with {-# OPTIONS --cubical #-}, along with this library.


Searching a sorted array to find the $k$ closest values to a target value $T$ Let $A$ be a sorted array of $N$ values. I am interested in finding the index $j$ such that the elements $A_j, A_{j + 1}, ..., A_{j + k - 1}$ have the $k$ closest values to the given target value $T$. Assume that $k$ is comparable, in magnitude, to $N$; i.e. we don't have $k \ll N$.

One can naively do this by first (binary) searching for the closest element, and then successively probing the left/right neighbors of that element to arrive at the result. This method has a time complexity of $O(\log N + k)$.

I suspect one can modify the original binary search algorithm to arrive at the result in $O(\log N + \log k)$ time. I tried searching online for such a variant of the binary search algorithm, without success. I'd appreciate any/all pointers to sources I might have missed, and also original attempts at formulating such a variant.

Note: It turns out there is an elegant binary search cousin that computes the result in $O(\log(N - k))$ time. See Ivan Smirnov's answer for a discussion.

You can do it in two binary searches. For simplicity I assume that all numbers are distinct and, even more, absolute differences between $T$ and all other elements are distinct too. The solution is easily adapted if it is not the case.

What means that a selected subrange is optimal? That means that we can't move it neither right ($|A_{j+k} - T| > |A_{j} - T|$) nor left ($|A_{j+k-1} - T| < |A_{j-1}|$). That looks like a binary search as well!

Look at the function $h(j) = \mathbb{1}\{|A_{j+k} - T| > |A_{j} - T|\}$ (that is, $h(j)$ is 1 iff the answer does not become better if we move the subrange to the right). Now you have to find minimum $j$ s.t. $h(j) = 1$. As the function is monotonous, it can be done by a binary search by $j$ in $O(\log n)$ time. (Actually, it is $O(\log (n-k))$ because $j < n - k$).

If there are identical values in the array, we need some case handling. Whenever $|A_{j+k}-T| = |A_j-T|$, there are three cases possible: Either $A_{j} = A_{j+k}$ and the segment is to the left of $T$; in this case we should move right. Or, $A_{j} = A_{j+k}$ and the segment is to the right of $T$, and we should move left. Or the segment contains $T$, in this case we've found the optimal answer.


Which are the cases where the "pumping lemma" doesn't work? Are there some languages not regular and/or not context-free in which the proof by contradiction fails? Why we need a "more specific" version of pumping lemma?

The standard formulations of the regular pumping lemma all force the pumped part to be at a specific place -usually the beginning of the word- and of a very restricted length. Thus you can trick the lemma by contructing a language that allows just about anything in the first part of the string and gets complicated in the second part. Take for example:

$$\{wba^nb^n\mid w\in\{a,b\}^+,\ n>0\}\,.$$
Since the pumping lemma just states the existence of its constants, you can pump anything in the first part of the language without leaving it. However, due to the last component the language is not regular.


How can I efficiently construct a CFG from a language I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}.
So m can be infinitely bigger than n but n can only be up to 3 more bigger than m and they can be the same. I have no idea how to make a CFG for this.
What I came up with was:
S -> AB | _
A -> a | aa | aaa | C | _
C -> aC | a | _
B -> bB | b | _

But I think this is not even close...
Any help/tips/advice would be much appreciated!

The best way is to learn is to look at examples, and see how they work.
One of the simplest "real" context-free languages is $\{\; a^mb^n \mid n = m \;\}$
Its grammar is $S\to aSb\mid \varepsilon$.
Now add in steps, the extra 3, and the more than ...
$\{\; a^mb^n \mid n = m+3 \;\}$
$\{\; a^mb^n \mid n \le m+3 \;\}$


Decidability of CFG that accepts at least one odd length string Let $L$ be the language$\{\langle G \rangle : G\text{ is a CFG and L(G) accepts at least one odd-length strings}\}$.

  Prove that $L$ is decidable or undecidable.

Here is my attempt:

$L$ = On input $\langle G \rangle$, where $\langle G \rangle$ is a CFG:

Construct CFG, such that $L(O)$ contains only odd length strings.
Construct CFG $\langle H \rangle$ such that $L(H) = L(O) \cap L(G)$
Input $\langle H \rangle$ to the decider $E_{\text{cfg}}$
If it accepts, $reject$.
Else, $accept$.

Is my proof correct? In the first step, can I construct a DFA, $O$ such that $L(O)$ consists of only odd length strings instead of a CFG?

You cannot compute the intersection of two context-free grammars, at least not if you expect the answer to be another context-free grammar. The reason is that context-free languages are not closed under intersection (consider $a^nb^nc^m \cap a^mb^nc^n = a^nb^nc^n$).

However, context-free languages are closed under intersection with a regular language, and moreover there is an efficient algorithm that, given a context-free grammar $G$ and an NFA $A$, computes a new context-free grammar for the language $L(G) \cap L(A)$. You should use this algorithm in your second step.

Another problem with your solution is that it's not clear what you mean by "$L(O)$ contains only odd length strings". There are many languages that contain only odd length strings, for example the empty language. You want $L(O)$ to contain only and all odd length strings, that is, you want it to be the language of odd length strings.


LTL to Büchi automaton, deterministic? I know it is possible to convert LTL formulas to Büchi automatons. But is it possible to convert a LTL formula to a deterministic Büchi automaton? Are there formulas that can't be converted to a deterministic Büchi automaton, then why not? Do you have examples for that case?

There are languages that are representable by an LTL formula but by no deterministic Büchi automaton (DBA).
Thus a translation from LTL to DBA cannot exist.
An example is the formula $\mathbf{F}\mathbf{G} a$, which states that from some moment on $a$ has to hold forever.
A nondeterministic Büchi automaton can guess when this moment occurs.

No deterministic Büchi automaton can accept the corresponding language. To see this, assume that there is a DBA for the language and note that when reading only $a$ an accepting state must be visited at some point.
After visiting the accepting state, let the next symbol of the input word be $b$, and then $a$ again until another accepting state is reached.
Such a state must be reached again eventually, as $a^* b a^{\omega}$ is part of the language.
By iterating this idea a word can be constructed that is not in the language but nevertheless is accepted by the automaton, which contradicts the assumption.


Two increasing functions from the set of positive integers to the set of positive integers such that neither f (n) is O(g(n)) nor g(n) is O(f (n)) Here is the question again : Give an example of two increasing functions f (n) and g(n) from the set of positive integers to the set of positive integers such that neither f (n) is O(g(n)) nor g(n) is O(f (n)).
I tried with several functions such as sine and cosine, but they are not increasing functions but Oscillatory. Then I tried x + sinx and x + cosx. However for sufficiently large coefficients c and n0, they also fail two satisfy the criteria. I am starting to doubt if such pairs of functions even exist !?


Limiting memory usage while keeping score For an assignment we are asked the following(simplified) :

A function F(a) has a non-negative integer as a result. This result is reused in the function itself. Like this, and where the first a is given:
new_a = (c1 * (previous_a or first_a) + c2) mod c3
Write, in C#, a sufficiently fast and memory efficient algorithm that tells how many iterations of the function does it take before new_a is within a specified range of any previous ones?

Now I have already made a "naive" solution as follows: I create an array of size c3 and for every new_a I check whether its corresponding index is set to true. If so, the number of iterations is returned. If not, the index and the given range around it is set to true. This goes on until there is a hit.
This solution is very fast but the downsize is that for large enough sizes of c3 there is just not enough memory available.
I have been thinking about a week now on how to solve the memory problem, but I just am stuck figuring out how to do it? The only thing I can think of is that given the function there is some kind of assumption I should/can make about the distribution of its outcomes but I just am stuck.
Any ideas on the direction I should take?

Your idea of an array of size $c_3$ is a good one.
But you can do better. First, since you need only be withing a range $r$,
you can use an array of size $c_3/r$, rounding upward, and just mark the entry
corresponding to the integer segment you fall in (there may be some details to work out).

Then, rather than using an array, if it is still too large, you can
build a binary structure, so that you create only the array entries you
need. Each node of the binary structure corresponds to a range of
consecutive entries.

    Then, you can reduce the memory requirement further by merging contiguous ranges where all entries have been hit, and rebalance the tree.

 Of course, there is a $\log_2 c_3/r$ price in access time. But this cost is limited by the tree shrinking as it gets full.


What would NP-complete solution in O(2^N/B) mean? Suppose we had an algorithm that solved an NP-complete problem (SAT, TSP, etc.) in time $O(2^{N/B})$ where $B>2$ is an input to the algorithm, along with the instance to be solved.

So for $B < N$, we have a reduced exponential growth runtime, but for $B \geq N$ we actually have a constant runtime.

What would this say about P vs NP?  Does this complexity class already exist or would it be a new one?  Would this add anything significant to our current understanding of complexity theory?

It says nothing about the P vs NP question because no such algorithm can exist.  If there is an algorithm that takes as its input a formula $\phi$ and an integer $B$ and determines whether $\phi$ is satisfiable in time $O(2^{N/B})$, where $N$ is the length of $\phi$, then we can decide SAT in constant time by calling the algorithm with $B=N$.

But we know that SAT cannot be solved in constant time because, in $k$ steps of the computation, you can only read the first $k$ characters of the input. That means that you have no way of distinguishing between the formulas $X\land X\land\dots \land X$ and $X\land X\land\dots \land X\land\neg X$, where $X$ is repeated, say, $k$ times. One of these formulas is satisfiable and the other isn't, but an algorithm running in $k$ steps would have to return "satisfiable" or "unsatisfiable" before seeing the $\neg X$ (or lack of it) at the end.


Characteristic path length I am unable to understand that what the characteristic path length (CPL) of a graph is.

In one of its definitions, it is written that

  it is defined as the median of the means
  of the shortest path lengths connecting each vertex to all other vertices.

This is what I understand. Is it right?

Suppose we have 3 nodes A, B and C. A can reach to B and C through different paths. We consider just the two paths, AB and AC. These two are the shortest path lengths from which A can reach to B and C respectively. We will then take the mean of AB and AC. Similarly, we will calculate two more means for B and C like I calculated it for A. In the end, we will take the median of the 3 means.

Am I right?

To get the CPL by this definition you first take the average distance from a certain vertex to any other vertex:
$$d_v = {{\sum_{v \ne w} d(v,w)} \over {|V(G)| - 1}}$$
 After doing so for every vertex $v \in V(G)$, calculate the median of all previously calculated $d_v$.


Solve a recurrence using the master theorem This is the recursive formula for which I'm trying to find an asymptotic closed form by the master theorem:
$$T(n)=9T(n/27)+(n \cdot \lg(n))^{1/2}$$

I started with $a=9,b=27$ and $f(n)=(n\cdot \lg n)^{1/2}$  for using the master theorem by $n^{\log_b(a)}$, and if so $n^{\log_{27}(9)}=n^{2/3}$ but I don't understand how to play with the $(n\cdot \lg n)^{1/2}$.

I think that the $(n\cdot \lg n)^{1/2}$ is bigger than $n^{2/3}$ but I'm sure I skip here on something.

I think it fits to the third case of the master theorem.

$f(n) = (n\cdot \lg n)^{1/2}$ and $n^{\log_b a}=n^{2/3}$, thus
$f(n) = O(n^{\log_b a})$ and even $f(n) = O(n^{\log_b a - \epsilon})$ for $\epsilon < 1/6$.

Why? because
$$\lim_{n\to\infty} \frac{f(n)}{n^{\log_b a - \epsilon}} = \lim_{n\to\infty}\frac{n^{1/2}\lg^{1/2}n}{n^{2/3-\epsilon}} =  \lim_{n\to\infty} \frac{\lg^{1/2}n}{n^{1/6-\epsilon}} =0 \quad\text{for }\epsilon< 1/6$$

Thus case 1 of the Master theorem should apply, and $T(n) = \Theta(n^{2/3})$.


When are log complexities considered equivalent? Would we consider $O(\log_2(n))$ to be the same complexity as $O(\log_2(n-1))$?

Why or why not? I'm specifically wondering about how the number we take the log of affects the time complexity.

$O(\log(n))$ and $O(\log(n-1))$ contain the same set of functions.

The inclusion $O(\log(n-1)) \subseteq O(\log(n))$ is trivial.
As for $O(\log(n-1)) \supseteq O(\log(n))$, let $f(n) \in O(\log(n))$ and let $c \ge 1$ and $n_0 \ge 3$ be such that:
$$
f(n) \le c \log(n) \quad \forall n \ge n_0.
$$

We have:
$$
f(n) \le c \log(n) = c + c \log(n/2) \le c + c \log(n-1) \le 2c \log(n-1).
$$

Showing that $f(n) \in O(\log(n-1))$.


NPDA question about accepting condition Will an NPDA accept a string that reaches a final state but does not have all its input consumed yet?

By “final state” I assume you mean “accepting state”.
The answer is no, as the accepting state should have an empty string $\epsilon$ for it to be meaningful.

You can of course define a transition relation that consumes everything after it has reached an accepting state. It will act as a prefix detector.


How to find middle element of doubly linked list using head and tail? Is there a way possible to find the middle element of a doubly linked list using head and tail. I tried traversing to the next element from the starting node and the previous element from the end node and check if the reference of both is same or not. This works fine if there are odd number of elements in the list. I am not able to find when should I stop in case the number of elements in the list is even.

while(head.next != end.previous) {
    head = head.next;
    end = end.previous;
}

Start with a pointer $x$ at the beginning and a pointer $y$ at the end. Repeatedly execute the following steps:

If $x=y$, stop.
Advance $x$ forward.
If $x=y$, stop.
Advance $y$ backward.

This should work out for both even and odd length.


Monte-Carlo Algorithm for counting 'on' bits in a binary array Given a Monte-Carlo algorithm (called A) that given a binary array with b 'on' bits (one-bits) returns a, where in a probability of 1/2:
$\frac b 3 \leq a \leq 3b$

How can I use A to build an algorithm that does the same, but with probability $poly(\frac 1 n)$ of success (success means $\frac b 3 \leq a \leq 3b$
 ), using A? if A runs in $O(T(n))$ time ($T(n)$ is much smaller than $n$), what's the runtime of the new algorithm?

This is a standard technique. Run the algorithm multiple times and take the median answer. The median will be a success unless there are many failures; use a Chernoff bound to show that this many failures has the low probability you require. Typically, a constant number of runs will give a constant (but better than $1/2$) failure probability, poly-log runs will give polynomially small failure probability and a polynomial number of runs will give exponentially small failure probability.


Question about IO automaton I'm currently reading Nancy Lynch book about distributed systems, chapter about IO automaton. And I have following questions related to book exercise 8.13(c).

We are given some automaton A with sig(A) is empty. Traces(P) is the set of sequences  over {1,2}  in wich every occurance of 1 is immediatly followed by a 2. I need to show that P is neither a safety property nor a liveness property. and show explicitly that P could be expressed as intersections of S and L.

Here is my problem: I can show that P is not safety because it breaks prefix-closed property, e.g. {2,1,2} has no prefix belonging to P (it should be of the  form {...,1} which is impossible for P). But I don't know how to deal with L property -- either it is empty or include trace(P) -- trace(P) $\subset$ trace(L). If it is empty then traces(P) is empty because traces(P)= traces(S) $\cap$ traces(L) which is wrong. So I think that traces(P) is subset of traces(L).

Is my conclusion related to traces(L) is right?

How can I explicitly express traces(P)=traces(S) $\cap$ traces(L) for this problem?

Thanks in advance.

Let S be the set of all traces in which "11" does not appear (a safety property) and L be the liveness property defined such that if 1 appears then eventually 2 will appear after (in temporal logic: $\square( 1 \rightarrow \lozenge 2)$).
Then trace(P)=trace(S)$\cap$trace(L).


Figuring out the language accepted by a DFA? I have been asked to give a formal description of a finite state machine. I have tried for over five hours to minimize it, to understand what gets accepted, and what gets refused, to no avail. I really am in need of help. If solving the problem does not seem reasonable, I would really appreciate any tips to attack this problem. The machine looks as such:

Things I've tried:
 I tried minimizing it, but the minimized version no longer accepts the same language.
 I tried looking at what gets accepted. I looked at how one can reach state q1 (through loops and what not), and how one can reach state q4 (through the same idea). When I tried this, I couldn't find a reasonable answer.
Example:

For q1: 4 ways to get to q1:

a run of a's,

loops of the manner (q1->q2->q3->q1),

loops of the manner (q1->q2->q4->q3->q1),

and loops of the manner (q1->q2->q4->q3->q2->q4->q1).

I would follow a similar thought process for arriving to q4. However, I can't seem to write a language that encompasses all of the possible combinations of these, along with the union of the two. I appreciate any help.
Thank you very much.

EDIT: My attempt at minimizing the state machine :

I look at the state diagram of the state machine, which looks something like the following:

The 0 equivalence looks like this:
[Q2 Q3] [Q1 Q4]

1 equivalence looks the same

This means we only have two states. I'll denote [Q1 Q4] by A, and [Q2 Q3] by B.
Initial and final state is A, and the other is B, which is not final.

A on a goes to A, A on b goes to B.

B on a goes to B, B on b goes to A.

resulting in the following state machine:

In the initial machine, bbb is accepted, but not in the minimized version.
Hence, I don't know where I went wrong.

The DFA is already minimal. In the table below, I give words which separate all pairs of states:
$$
\begin{array}{c|c|c|c|c}
& q_1 & q_2 & q_3 & q_4 \\\hline
q_1 & & \epsilon & \epsilon & b \\\hline
q_2 & \epsilon & & ba & \epsilon \\\hline
q_3 & \epsilon & ba & & \epsilon \\\hline
q_4 & b & \epsilon & \epsilon & \\
\end{array}
$$
As for the language accepted by this DFA, the best I got is
$$
\begin{align*}
&(a^? (a^{even} b)^+ a^{odd} b)^* a^* + \\
&(a^? (a^{even} b)^+ a^{odd} b)^* a^?(a^{even} b)^+a^{even} b,
\end{align*}
$$
where $a^? = a + \epsilon$, $a^{even} = (aa)^*$, $a^{odd}=a(aa)^*$, and $r^+ = rr^*$.

There might be a simpler description.


Maximum independent nodes subset algorithm with strong constraint I've a tree with weighed nodes, the problem is to flag a subset of nodes with the following constraints:

The selected nodes must be the optimal solution (maximal sum of weight).
If one node is flagged no adjacent nodes can be flagged.
If a node is flagged it will be called: "directly controlled", the adjacent nodes instead will be called: "indirectly controlled", all nodes must be directly or indirectly controlled.

I think is a dynamic programming problem (a greedy approach didn't find always a optimal solution), the first two constraints are a typical maximum independent subset problems, but i cannot find a solution with the third constraint included.
Any idea? Thanks

A set satisfying condition (3) is known as a dominating set. The exercise asks for a maximum weight dominating independent set.

If all node weights are positive, then every optimal solution is automatically a dominating set (why?), regardless of whether the graph is a tree or not. In the more general case in which negative weights are allowed, you can use a standard dynamic programming approach. Root the tree at an arbitrary node, and for every subtree rooted at some internal node $v$, compute the maximum weight independent set in the following three cases:

The independent set is dominating and includes $v$.
The independent set is dominating and doesn't include $v$.
The independent set is dominating if $v$ is removed (it is allowed to dominate $v$ as well), and doesn't include $v$.

I'll let you complete the details.


Black box with O(n) calls Let's say a procedure called 'decision(x,q)' is available as a 'black box'
X is the input set and Q is a real number Q.

I need to design an algorithm that reports "yes" if there exists a subset of X whose total sum is = Q
otherwise, it reports "no".

Running time is not an issue, it just needs to have all actual numbers in the subset  and it can't make more than O(n) calls to the procedure.

I believe this can be solved with dynamic programmming.

I believe you have misunderstood the question. You are given a black box that can answer queries of the form "does $X$ have a subset summing to $Q$", and you need to construct an algorithm that given $X$ and $Q$, finds a subset summing to $Q$ if one exists.

Here is a hint:

  Choose an arbitrary $x \in X$. Ask the black box whether there is a subset of $X - x$ summing to $Q - x$.


Algorithm to mimimally pair up points in 3D space Given a set of $n$ points $P$ and a set of $n$ points $Q$ in 3 dimensional space, what's the fastest algorithm to uniquely pair points in $P$ with points in $Q$ so that the sum of the square of the distance between points in $P$ and their corresponding point in $Q$ is minimized? Each point in $P$ must be matched with one and only one point in $Q$, and vice versa.

Another way to look at the problem: if $P$ and $Q$ are matricies with 3 columns and $n$ rows, how can I reorder the rows of $P$ so as to minimize the frobenius norm of $P - Q$?

This problem can be solved in $O(n^3)$ by creating a cost matrix $M$ where $m_{i,j}$ is the distance between point $P_i$ and point $Q_j$, and then by using the hungarian algorithm to find the minimal assignment, however I feel like there's a faster way.

Even if there isn't an exact solution, are there any fast approximations?

Edit: for my specific use-case, the points in $P$ are the points on a $m \times m \times m$ grid and $n=m^3$

As an approximate solution in $O(n^2)$ you can construct the cost matrix $M$ and then solve the stable marriage problem.


Where did the terms memory pool and memory leak come from? I wonder where those terms came from.

Is it computer science related?

Or are they related to civil engineering, or swimming sports?

Is it some analogy with filling water in a pool, or something like that?

Yes, Computer Science.

Back in the days of the NASA/Apollo program (and possibly before), mainframe computers had wads of memory (like as much as 256 Mwords). To support multi-tasking, a program/task running on that mainframe had to specify how much memory was required to do its job, and the system would allocate that much - if possible - out of the "memory pool". This "pool" nomenclature  comes at a time when we had motor pools, secretarial pools, labor pools... nonspecific resources of a certain class; indeed, this working memory on a mainframe was not dedicated to a specific use (there are regions of mainframe memory that are not available to "normal" programs/tasks).

As the tasks run, they are supposed to only use what they ask for, and they are required to signal the system when the memory is no longer needed. Depending on efficiency concerns, they may ask for the memory a little at a time (it's nice for other tasks that you don't grab either everything available, or more than you need). Poorly developed programs have a nasty side-effect of not returning what was allocated to them. From the system's perspective, the available memory pool is getting smaller and smaller, hence the memory "leaks out". It doesn't go anywhere, but the net effect is that a program that needs a certain amount of memory to either load or run will have to wait until a better behaved program/task returns a sufficient part of the allocation - or the memory system is restarted.


Can file snapshots aid in detecting malware? I noticed certain programs have a feature that can have a 'snapshot' of a file from a certaim time and compare it to a more recent snapshot of the file. If one's system has a snapshot of a program when 'first' downloaded and  it can compare  this to the program 'as it is now' and if there are any changes this might indicate the file is corrupt and it could be marked for possible removal. So could this comparison feature be used to determine if a file is corrupt?

This is not likely to be very effective in practice.  Malware might corrupt the file before you were first able to take a snapshot... or, more realistically, it might corrupt the snapshot you have taken, so that the snapshot matches the current version of the file.  It is difficult to defend against that attack.

So, while your idea is not a bad one, it has significant limitations that might render it not terribly useful in practice.

This also assumes that the underlying file is one that should never change.  Of course, in practice, for any given file, there are valid circumstances when the file should be allowed to change.  So this means you'd need some way to recognize valid, legitimate changes to the file.  This starts to get a bit more complex to implement.

You might take a look at Tripwire, which is a system that does something like this -- except it keeps only a cryptographic hash of each monitored file, rather than a full copy of the file.


How can a Turing machine write the description of the n-th Turing machine? I am trying to interpret the following problem:

"Describe an algorithm for a Turing machine which receives the integer n as
input and proceeds to write the description of the n-th Turing machine from
the standard enumeration on its tape."

I am confused about how a Turing machine itself can represent another Turing machine (the n-th Turing machine).

The question is probably assuming that there is some arbitrary but agreed-upon convention that specifies how to write a Turing machine description with the symbols of some alphabet. Since all Turing machines have by definition a finite description, all valid outputs will be finite strings.

The exercise itself is an ordinary combinatorics problem.


How to compare computational complexity of algorithms I have three different algorithms for achieving a target. Algorithm 1 takes $O(Mn)$ - $M$ is constsnt and n is variable,Algorithm 2 takes $O(min(p^3,n^3))$ - both $p$ and $n$ is variable and Algorithm 3 takes $O(nk+nd)$ - $k$ constant, $n$ and $d$ is variable. Is it possible to compare these algorithms? Which algorithm is fast and how much fast than other two algorithms?

Since you have three different variable it is not easy to compare their running times. For example if $d = 1/n$ then $nd = 1$. But if $d = n$ then $nd$ is $n^2$. If $d$ and $n$ are unrelated to each other asymptotically or functionally I think you may not compare them. Analogously for $p$.

Update:
If $M,p,k$ and $d$ are constant then we have Alg1 is $O(n)$, Alg2 is $O(min(p^3, n^3)) = O(p^3) = O(1)$, and Alg3 is $O(n)$.


Interesting Speedup & Amdahl's law problem I have found a problem on my Computer Architecture textbook which I have some issues with:

We have a process which spends its time in the following way:

50% of the time, it executes common arithmetic (non-floating point) instructions
10% of the time, it executes floating point instructions
40% of the time, it executes a function which has 4816896 instructions, which is 60% of the total of instructions

After improving the function's algorithm, we end up with 983040 instructions executed on the function instead.
Assuming that each instruction is executed in one cycle, it asks about the performance improvement after this instruction number reduction.

By calculating the speedUp in CPI before and after in the improved functions (4,9), and then using Amdahl's law, we get an increase of 46,7% in performance.
After this, it asks to calculate the speedUp again, but this time by checking the increase in MFLOPs.
How could this be done if we don't know anything about execution times?

You can calculate the speedup in MFLOPs. Speedup is a dimensionless quantity, so you don't need to know the execution time to calculate it.
You need to know the old execution time only if you need to find out the improved execution time.

In this problem, we can calculate the increase in MFLOPS by dividing the ratio of Floating point instructions to total number of instructions after improvement by the ratio of Floating point instructions to total number of instructions before improvement, since the Cycles Per Instruction is 1 and clock cycle time remains the same.
Increase in MFLOPS = $\dfrac{(Ratio\ of\ Floating\ point\ instructions\ to\ total\ number\ of\ instructions\ after\ improvement)} {(Ratio\ of\ Floating\ point\ instructions\ to\ total\ number\ of\ instructions\ before\ improvement)} $


Can Shortest Job First Scheduling be subject to convoy effect? Look at the below table for example :

Look at the Non-Preemptive SJF table
Suppose if the burst time of process $P_1$ was a very large number compared to $7$, the processes $P_3,P_2$ and $P_4$ have to wait for a large amount of time till $P_1$ frees the CPU. No book or article that I've read mentions of SJF being a subject to convoy effect? Why not?

I think you're not using the same terminology as the books and articles you're reading.  Non-preemptive schedulers suffer from priority inversion, not convoy effects.

Most scheduling disciplines (FIFO, SJF, LJF, Nearest-deadline-first, ...) can be reframed as highest priority first schedulers, where what changes from discipline to discipline is the priorities assigned to the jobs.  So first-in-first-out (FIFO) scheduling assigns priorities according to their order of arrival.  Shortest-job-first (SJF) assigns priorities according to the burst time.  In preemptive shortest-job-first the scheduler is always running the job with the highest priority.  In non-preemptive shortest-job-first scheduling if a short job arrives after a longer job already starts, then the scheduler will be running the lower priority job instead of the high priority job for a while.

A convoy effect is a different problem where jobs that need many different kinds of service get clumped up together because of decisions you have made elsewhere in the system.  It applies to things like schedulers that deal with jobs that have more than one burst (separated by time when those jobs are waiting for i/o, or when jobs are waiting for a lock).  For the lock case there's a wikipedia article: http://en.wikipedia.org/wiki/Lock_convoy.


Are there graphs for which A* cannot be admissible? Wikipedia states that "On infinite graphs with a finite branching factor and edge costs that are bounded away from zero $ (d(x,y)>\varepsilon >0$ for some fixed $\varepsilon$), A* is guaranteed to terminate only if there exists a solution."

Does this mean that, if I have such a graph, then there is no admissible A* which exists for this graph? When one says that A* is not admissible, this means that its heuristic is not admissible, right?

Furthermore, is it correct to say that a heuristic is only admissible with respect to a graph - not generally admissible?

For example, if I have a infinite graph which has a finite branching factor, and the cost of each edge is
half of the cost of the edge preceding it (something like this: $goal\leftarrow_{_{c=2}} start \rightarrow_{_{c=1}}q1 \rightarrow_{_{c=1/2}} q_2 \rightarrow ...$), the heuristic and therefore the A* is necessarily inadmissible as there exists no fixed $\epsilon>0$ that is less than the cost of any edge?

To generalize, the $epsilon$ constraint is to make sure that there is no infinite path who's total cost converges, thereby assuring termination?

Any clarification is appreciated. Thanks!

The heuristic function $h:V \longrightarrow \mathbb{R}_{\geq 0}$ is *an input to the $A^*$ algorithm. If the function is admissible then $A^*$ algorithm gives you the solution; however as you have noted for infinite graphs the edge weights must have a positive lower bound.

The point of the heuristic function is to find the shortest path in the least amount of time, i.e. lower the computational complexity; because you are making informed decisions based on a heuristic (hence the name).

Recall the heuristic function is admissible if $h(v)$ is always less than (or equal to) the true path cost to the goal node.

There is always an admissable $h$ namely $h(v)= 0$ for all $v$. In this extreme case it becomes Dijkstra's algorithm.

Returning to the example you gave if you plug in the input $A^*(G,h)$ where $G$ is a description of $G$ and $h = 0$ then $A^*$ won't halt (geometric series $r = 2 \implies \sum_i r^i = \frac{1-r^{n+1}}{1-r} \leq 2$ for all finite partial sums). But lets see if we can bypass that; lets try: \begin{equation} h(v) = \begin{cases} 3 & \text{if } v = q_1 \\ 0 & \text{else}\end{cases} \end{equation} as you can see $h$ is admissible (because $d(q_1 , \text{goal}) = 3$ on the nose) and $A^*$ will pick "goal" as its first node (because its two choices are $f(q_1) = 4$ or $f(\text{goal}) = 2$).


Parity of number of divisors Im pretty new here.

My question showing me an algorithm:

TRUE_SEQ(A[1...n])

for i <- 1 to n do
 A[i] <- FALSE
for i <- 1 to n do
 k <- i
 while(k <= n) do
  FLIP(A[k])
  k <- k + i

FLIP(x)

if x = TRUE then
 x <- FALSE
else
 x <- TRUE

Now i need to prove that after we finish TRUE_SEQ, the value of $A[i]$ is TRUE if and only if $i \in N$ is a power of a some natural number.

We learned about loop recorded sequence (Im not sure if i say it correctly in english)

Any way i would like a hint (and prefer a hint than a solution - as those are my homeworks)

Thank you for the help.

At the end of the algorithm, the value of $A[n]$ is the parity of the number of divisors of $n$ (TRUE means odd parity). The divisors of $n$ come in pairs $i,n/i$. Most of these pairs consist of two distinct values, but if $n$ is a square, then when $i = \sqrt{n}$, both elements are equal. This shows that $A[n]$ is TRUE if and only if $n$ is a square.


Check Cycles- On adding an edge in DAG Given a DAG N, if an edge $(U \rightarrow V)$ is added between any existing nodes U and V. Then, by performing DFS from the node $U$ and checking whether there is a cycle or a not, should be sufficient to conclude that this addition of edge didn't violate the acyclic property of the given DAG. Is it correct?

Or there is a need to perform DFS from other nodes in the network to verify the cyclic property of DAG?

Trying to find the most efficient way to verify whether addition of an edge to an existing DAG introduces cycles or not?

If you start with a dag then the only thing you need to check is whether adding the edge $U\to V$ will not create a cycle. That is, there should not exist a path from $V$ to $U$ in the original graph.


Evenly Spaced Points On Smooth Surface I want to space points evenly (i.e. maximizing minimal distance between two points) on some smooth surface $S\subseteq\mathbf{R}^n$ (usually $n=3$), where I have a projection operator $p:\mathbf{R}^n\to S$ which approximates the closest point on the surface.  My idea is to place them randomly first and then let some repelling force act between them and reproject back to the surface after each iteration of the action.  This can be rather costly, if there are $10^3$ points, I have to compute the distance between $10^6$ points in one iterations, and I need a few iteration until everything stabilizes.

How can I imporove this process?  My ideas:

Measure the distance between every pair of points but compute the force only when the distance is smaller than some $a$, then do a few iterations (assuming the points don't move too far in one iteration) and recompute the distance after $k$ steps.
Choose some partition of the surface where each part has a set of 'neighbours' (including itself), compute for each point the location in the partition, i.e. the part it lies in, then let only the points in neighbouring parts act on each other, recompute the location after $k$ steps.

I would suggest that you don't calculate the distance between all pairs of points, but only between pairs of points that are nearest neighbors.  You could store the points in some nearest-neighbor data structure, e.g., an octree, or even a fixed partitioning of space.  Some data structures might allow for relatively rapid updates, so you could even update after every iteration.

I'd also suggest looking at the methods used for simulating the n-body problem, as some of those might be applicable to your situation as well.  See https://en.wikipedia.org/wiki/N-body_problem#Many_bodies and https://en.wikipedia.org/wiki/N-body_simulation.

Also, you might consider adapting your objective function.  Rather than having all points repel, maybe you might have only those points whose neighbor are below a certain threshold repel; or you might make the repelling force a smooth function of the distance between the points, where this function is similar to $f(x) \approx x$ when $x \ll \tau$ (where $\tau$ is the threshold) and $f(x) \approx \tau$ when $x \gg \tau$.  You could select your threshold $\tau$ to be approximately equal to the expected final minimal distance that you think is achievable, or you could set it adaptively in each iteration.  This may require many more iterations, but each iteration can be done much faster, and it will avoid moving points that are already far from all their neighbors.