How to construct the found path in bidirectional search I am trying to implement bidirectional search in a graph. I am using two breadth first searches from the start node and the goal node. The states that have been checked are stored in two hash tables (closed lists).
How can I get the solution (path from the start to the goal), when I find that a state that is checked by one of the searches is in the closed list of the other?

EDIT

Here are the explanations from the book:
"Bidirectional search is implemented by having one or both of the searches check each
node before it is expanded to see if it is in the fringe of the other search tree; if so, a solution has been found... Checking a node for membership in the other search tree can be done in constant time with a hash table..."

Some pages before:
"A node is a boolkkeeping data structure used to represent the search tree. A state corresponds to a configuration of the world... two different nodes can contain the same world state, if that state is generated via two different search paths." So from that I conclude that if nodes are kept in the hash tables than a node from the BFS started from the start node would not match a node constructed from the other BFS started from the goal node.

And later in general Graph search algorithm the states are stored in the closed list, not the nodes, but it seems to me that even that the states are saved in the hash tables after that the nodes are retrieved from there.

Let me give this question a try. I am not sure I do fully understand it so I was considering to post a comment but in the end, I preferred to try an explanation. Hope it helps!

Raphael already suggested a solution (so I voted up his comment) which works even if you only store states instead of nodes. To make it clear:

states: those in the original problem. These are unique
nodes: those enumerated by your search algorithm (bidirectional breadth-first search in your case). As stated in your book "two different nodes can contain the same world state, if that state is generated via two different search paths" so that it is very likely to have more nodes than states (since the former distinguish states by the different paths ---which can be exponentially large--- that lead to the same state).

Obviously, the path from the start state $s$ to the target $t$ is computed by concatenating the paths from $s$ to $n$ and from $n$ to $t$ where $n$ is the node that was found in the hash table of the opposite search.

Now, assuming you are using a consistent-heuristic function (a heuristic function $h (n)$ is said to be consistent if and only if it satisfies the triangular inequality $h(n) \leq c(n,m) + h(m)$ where $c(n,m)$ is the cost of the operator from node $n$ to one of its offsprings $m$) or no heuristic function at all (so that your BFS is a blind search) let me suggest the following procedure:

Let me assume wlg that $n$ was generated by the forward search (i.e., from the start state $s$) and that it was found in the hash table of the backward search (i.e., the one issued from the goal node). In this case it suffices to expand the node $n$ and to select any descendant that appears also in the hash table of the backward search. You can do this since you are storing all states (instead of nodes) in both hash tables. No matter of the difference between nodes and states, if you generated $n$ in the backward search (which results from the fact that it is stored in the hash table) it had to be done via one of its parents which can be recovered now as one of its descendants (assuming you are traversing undirected graphs, otherwise just apply the inverse operators to recover the parents). Acting like this you will eventually get to the target node.

The same mechanism applies to the forward search ---i.e., no need to store with each node its path to the start node, just use the closed list implemented as a hash table. Reverse the path obtained in the previous paragraph, concatenate them and there you are a solution path.

If you are not using a consistent heuristic function, then you should store along each node in the hash table its value $g(n)$ ---i.e., the cost of the path from its corresponding root node, either $s$ or $t$. Doing so, the previous procedure is just slightly modified by selecting the parent (now generated as a successor) whose $g$ value is $g(n)-1$. However, this is not even necessary in case you are seeking (as it seems) any path from $s$ to $t$.

Bidirectional search is one of the most intriguing "paradigms" in heuristic search. Noone has already found a simple way that makes it as efficient as in the case of blind search (where it is clearly a winner).

Hope this helps,


Does there exist a priority queue with $O(1)$ extracts? There are a great many data structures that implement the priority-queue interface:

Insert: insert an element into the structure
Get-Min: return the smallest element in the structure
Extract-Min: remove the smallest element in the structure

Common data structures implementing this interface are (min)heaps.

Usually, the (amortized) running times of these operations are:

Insert: $\mathcal{O}(1)$ (sometimes $\mathcal{O}(\log n)$)
Get-Min: $\mathcal{O}(1)$
Extract-Min: $\mathcal{O}(\log n)$

The Fibonacci heap achieves these running times for example. Now, my question is the following:

  Is there a data structure with the following (amortized) running times?

Insert: $\mathcal{O}(\log n)$
Get-Min: $\mathcal{O}(1)$
Extract-Min: $\mathcal{O}(1)$

If we can construct such a structure in $\mathcal{O}(n)$ time given sorted input, then we can for instance find line intersections on pre-sorted inputs with $o\left(\frac{n}{\log n}\right)$ intersections strictly faster than if we use the 'usual' priority queues.

Our idea is to use threaded splay trees. Other than the Wikipedia article we will thread the trees so that every node has a pointer next to its successor in the in-order traversal; we also hold a pointer start to the smallest element in the tree.

It is easy to see that extracting the smallest element is possible in (worst case) time $\mathcal{O}(1)$: just follow the start pointer, remove the minimum and change the pointer to the minimum's next. The minimum can never have a left child; if it has a right child, we put it in the minimum's place in the tree. We do not perform the splay operation splay trees usually would do.
The result is a search tree that is still reasonably balanced: because we only remove nodes on the left flank, we know that when the number of nodes (in an affected subtree) drops to about half the original number because of deletions, the (sub)tree's height is reduced by one.

Insertions are possible in $\mathcal{O}(\log n)$ amortised time; the zig-zag (and what not) operations will here also rebalance the tree nicely.

This is a rough sketch at best. Credits go to F. Weinberg who puzzled over the question with me and our advisor M. Nebel who mentioned splay trees, about the only tree variant we had not tried.


What can you do with lambda calculus if you aren't allowed parentheses? Is there a concise/existing way to denote the expressive power of "lambda calc without using parentheses/tree-of-expressions/application-order-restructuring anywhere"?

Can you do without them/reinvent them? Does it break completely (i.e, even with a naive no-more-parentheses, you're using them implicitly, like when naming things)? Does it become completely trivial/boring?

I haven't tried very hard, but I feel like I couldn't express something like

$\lambda x y z . x y (x z)$

without using parentheses somewhere.

Answer 1

The best answer to this question is: This is the wrong question to ask! Let me explain.

The fact that we write down expressions (in $\lambda$-calculus or anywhere else) as sequences of symbols is a convenience and tradition established by humans. From a theoretical point of view the strings of symbols are not the optimal way of representing expressions. Instead, abstract syntax trees are.

Abstract syntax trees do not require any parentheses. Parentheses are there only because we use a particular way of writing things. There is nothing deep in having or not having parenthesis. Your question then boils down to the following: "Suppose we use a notation which requires parentheses, but then we remove parenthesis, what happens?" This is not a mathematically interesting question. It can be answered, but it's irrelevant for $\lambda$-calculus. The answer might be interesting, but it will not reveal anything about parentheses. Instead, it will reveal something about abstract syntax trees of a certain shape.

Were you born in a slightly different universe, where everyone used reverse Polish notation then you would not have known that there is such a thing as parentheses.

Let me put it another way. It is a convention that in $\lambda$-calculus we write $a\,b\,c$ to mean $(a\,b)\,c$. Without such a convention we would always have to write parentheses everywhere, all the time. The first person to establish the convention could have picked the other one, so that $a\,b\,c$ would mean $a\,(b\,c)$. Then your question would have a different answer because of some person who picked a convention a long time ago.

Answer 2

It is not entirely clear where you think parentheses are needed, but let's suppose that

application is left-associative, so that $x y z = (x y) z$, and
$\lambda$-abstraction has lower precedence than application, and it binds as much as it can, so that $\lambda x . x y z$ and $(\lambda x . x y) z$ are different expressions.
You think that $x \lambda y . y$ is not a valid expression because it should be written as $x (\lambda y . y)$. That is, a $\lambda$-abstraction in an aplication must always be parenthesized.

Under these conditions, we cannot ever write any $\beta$-redeces (because we would have to apply a $\lambda$-abstraction). So any expression must be of the form $\lambda x_1 . \lambda x_2 . \ldots \lambda x_n . M$, possibly with $n = 0$, where $M$ is of the form $y_1 y_2 \ldots y_m$ for some variables $y_1, \ldots, y_m$ (which may be equal to the $x_i$'s).

If anyone can say anything interesting about this fragment of $\lambda$-calculus, I'd be interested to hear.


What are the best ways to find errors in a sequence of messages (strings)? I am currently working on a thesis, where the main goal is to find errors (like a missing message, wrong sequence) in message sequences. The messages are distinguishable by their name, have further information in the message body, and are available in a database. Each message can just be thought of as string-representation of its name.

The thesis should compare different concepts for finding errors in these real-life message sequences. A big amount of these messages are being collected and the goal is to check for errors in the sequence or any missing messages. The default sequence (so the standard-case) can be defined.

Now I am just lacking any ideas on how to approach this problem.
So, my questions are as follows: Which approaches can be used to solve this problem? Are there any algorithms, that could be used in this context?

Further example to make it clearer:

Message sequence A, B, C, D, E is defined for one standard-case.
Now, the real message sequence that is observed is A, B, C, E, D (or one message is missing entirely).

I hope the problem is comprehensible. Thanks to all who take the time to read.

Not sure if I get your question right, as you didn't specify whether this is a theoretical problem or a practical.

Assuming it is practical problem, there are quite some algorithms (e.g. TCP) depending on which layer your messages are being send (if they are being send at all).

Assuming it is more of a theorectial problem you can use stuff like the Hamming distance.

Maybe check: Computer Networks by Andrew S. Tanenbaum


Lower bounds of calculating a function of a set Having a set $A$ of $n$ elements, let's say I want to calculate a function $f(A)$ that is sensitive to all parts of the input, i.e. depends on very member of $A$ (i.e. it is possible to change any member of $A$ to something else to obtain a new input $A'$ s.t. value of $f$ on $A$ and $A'$ are different).

For example, $f$ could be the sum or the average.

Is there a result that proves that, under some conditions, the time necessary to a deterministic Turing machine to compute $f$ will be $\Omega(n)$?

You have to be specify the model of computation and properties of $f$. In the following argument I will state the assumptions that I need. It can be generalized a little bit further but I think it should be sufficient to give you the idea.

Assume that the machine $M$ never reads the value of one of the members of $A$ (a fixed set, and $A$ is given as a list). Assume further that $A$ is an input such that changing the value of its $i$th member does not change $M$'s answer. Assume further that $f$ is sensitive to all parts of the input, i.e. depends on very member of $A$ (i.e. it is possible to change any member of $A$ to something else to obtain a new input $A'$ s.t. value of $f$ on $A$ and $A'$ are different).

We can use an adversary argument to show that the machine cannot compute the right answer by changing the value of that member of $A$ to obtain $A'$ else s.t. the value of $f$ is different. The value of $M$ on these two sets is the same, so one of them must be false and therefore $M$ cannot compute $f$ correctly.

Therefore any machine $M$ that computes $f$ will need to read all of the input which takes $\Omega(n)$ steps.

(On the other hand, assume that we have a nondeterministic random access machine, and we want to compute OR of the bits in the input. We can nondeterministicly guess a bit and check if that is 1, if it is 1, we output 1. This machine reads only a single bit of the input in $O(\lg n)$ steps and correctly answers the problem. So without assumptions on $M$ and $f$ the result does not hold.)


How do I find the roots of the disconnected subgraphs of a directed graph? If I have a directed acyclic graph $G(V,E)$, which may consist of several disconnected subgraphs $G_i(V_i,E_i) \subset G(V,E)$, how do I find the root of every subgraph $G_i(V_i,E_i)$?

You can apply the following algorithm:

Identify the weakly connected components (i.e., the disconnected subgraphs). To do this, you can turn all edges into undirected edges and, then, use a graph traversal algorithm.
For each  component, select the node that has no incoming edges (i.e., the source node) as the root. If there is more than one source node, then there is no root in this component.

Note that this solution assumes the root of a directed acyclic graph $G=(V,E)$ to be a node $r$ such that $\forall v \in V-\{r\} \Rightarrow \exists P=[(r, v_1),(v_1,v_2), ...,(v_{n-1},v)]$, where $P$ represents a directed path from $r$ to $v$.


Regular Expression from Context Free Grammar The purpose of this exercise is to write a program that recognize all the words derived from this grammar.
The time complexity of this program must be O(n) hence i must be able to derive a regular expression from the grammar

  $S\rightarrow ASA\mid A$
  $A\rightarrow aAa\mid aAab\mid bA\mid\epsilon$

By intuition I guessed that this grammar generates words in the form of
$\left \{ a^ia^jb^*a^jb^ja^i \right \}^*$ and, correct me if I'm wrong, this doesn't seems like a regular language.

My problem with this type of exercise (I've tried a lot like this) is that there is no automatic way to find the regular expression from the grammar even if it generates indeed a regular language. Any advice on how to proceed on exercises like this?

Denote your grammar by $G$ and let
$$
M=\{w\in\{a,b\}^*\mid |w|_a\equiv 0\pmod 2\}
$$
where $|w|_a$ is the number of $a$s in $w$. In other words, $M$ is the set of all strings of $a$s and $b$s with an even number of $a$s. We claim $L(G)=M$.

First, it is clear that any word in $L(G)$ must have an even number of $a$s, so $L(G)\subseteq M$. All we now have to do is show $M\subseteq L(G)$, in other words, that every string in $M$ can be generated by $G$. We'll show this by induction on the number, $n$, of $a$s in a word.

If $n=0$, we can generate strings consisting only of $i\ge 0\ b$s by one of two derivations:
$$\begin{align}
S &\Rightarrow A\Rightarrow \epsilon \\
S &\Rightarrow A\Rightarrow bA\stackrel{*}{\Rightarrow} b^i
\end{align}$$
So we can generate all strings with no $a$s.

If $n=2$, any string in $M$ with exactly two $a$s must have the form $b^iab^jab^k$ with $i, j, k\ge 0$. Write such a string as $(b^i)(ab^ja)(b^k)$. We've seen that we can generate the $b^i$ and $b^k$ portions from $A$. We can also generate the $ab^ja$ part from $A$:
$$
A\Rightarrow aAa\stackrel{*}{\Rightarrow} ab^ja
$$
so we can generate $b^iab^jab^k$ by
$$
S\Rightarrow ASA\Rightarrow AAA\stackrel{*}{\Rightarrow} b^iAA\stackrel{*}{\Rightarrow}b^iab^jaA\stackrel{*}{\Rightarrow}b^iab^jab^k
$$
and it's clear that we can continue this process for even $n>2$, simply by starting with the requisite number of $A$s. In short, we've shown that any word in $M$ can be generated by the grammar $G$, and this, combined with the first part, shows that $L(G)=M$.

Of course, $M$ is regular, if for no other reason than it is denoted by the regular expression $(ab^*a+b)^*$. Also, it would also be easy to construct a finite automaton for $L$ as well.


Median-of-medians in O(log n) memory Is there a way to use median-of-medians to find a median in,

simultaneously,  O(log n)  memory and O(n) comparisons?

The user orlp on this site seems to claim that there is.

Getting  O(log n)  auxiliary memory seems to be straightforward,

but I have no clue how that can be improved to O(log n) memory.

There is no such way.

This paper shows

  that any comparison-based randomized algorithm for finding the

  median requires $\Omega(n \log \log_{\hspace{.02 in}S} n)$ expected time in the RAM model

  (or more generally in the comparison branching program model),

  if we have S bits of extra space besides the read-only input array.

  This bound is tight for all $S\gg \log n$, and remains

  true even if the array is given in a random order.

$n^{1/\left((\hspace{.02 in}\log(n))^{\hspace{.02 in}\Omega(1)\hspace{-0.03 in}}\right)} \; = \; 2^{\left((\hspace{.02 in}\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}$
and
$\operatorname{polylog}(n) = 2^{\log(\hspace{.02 in}\operatorname{polylog}(n))} = 2^{O(\hspace{.02 in}\log(\hspace{.02 in}\log(n)))} \subseteq 2^{\left((\hspace{.02 in}\log(n))^{\hspace{.02 in}o(1)}\hspace{-0.03 in}\right)} \subseteq 2^{\left((\hspace{.02 in}\log(n))^{1/2}\hspace{-0.03 in}\right)}$

so since

$2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)} \: \cdot \: \operatorname{polylog}(n) \;\;\; \subseteq \;\;\; 2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)} \: \cdot \: 2^{\left((\hspace{.02 in}\log(n))^{1/2}\hspace{-0.03 in}\right)}$

$= \;\;\; 2^{\left((\hspace{.02 in}\log(n))^{1-\Omega(1)}+\hspace{.02 in}(\hspace{.02 in}\log(n))^{1/2}\hspace{-0.03 in}\right)} \;\;\; = \;\;\; 2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}$

and

$\Omega \hspace{-0.04 in}\left(n\log \log_{2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}} n\right) \;\;\; = \;\;\; \Omega \hspace{-0.04 in}\left(n\cdot \left(\log(\hspace{.02 in}\log(n))-\log \left(\log \left(2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}\right)\right)\right)\right)$

$= \;\;\; \Omega(n\cdot ((1\cdot \log(\hspace{.02 in}\log(n)))-((1-\Omega(1)) \cdot \log(\hspace{.02 in}\log(n)))))$

$= \;\;\; \Omega(n\cdot (1-(1-\Omega(1))) \cdot \log(\hspace{.02 in}\log(n))) \;\;\; =$

$\Omega(n\cdot \Omega(1) \cdot \log(\hspace{.02 in}\log(n))) \;\;\; = \;\;\; \Omega(n \log \log n)$

and

pointers can be represented with  O(log(n))  bits

,
even when one measures with polylog(n)-bit machine words and assumes that

input-elements fit into such words, comparison-based selection algorithms

that use at most    $2^{\left((\hspace{.02 in}\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}$  $\Big($equivalently,  $n^{1/\left((\hspace{.02 in}\log(n))^{\hspace{.02 in}\Omega(1)\hspace{-0.03 in}}\right)}\Big)$    space

require  $\Omega(n \log \log n)$  comparisons on average,

even if the array is given in a random order.


Why do AI researchers seem to think that consciousness is a computation? Disclaimer: I am just an undergraduate student so my exposure to a lot of things is certainly limited.
I am not sure about the actual popularity of the idea that consciousness is a computation but my impression is that it is very widespread. I lost count to how many times I saw, sometimes very serious scientists, claim that we are just decades away from an actually intelligent AI (or AGI).
I also noticed a similar underlying premise with Machine Learning's "Neural Network" which is more or less exactly an implementation of the computational model of consciousness (which as far as I understand it [the model in the next sentence], assumes the Hodgkin-Huxley model to be true even though we don't actually really know that).
Am I wrong? Is it actually not as widely accepted and popular as I think it is?
If not, then why is it this widely accepted as fact?

Consciousness as a computation is not by any means a scientific fact.  Firstly because there's no universally accepted definition of consciousness.
General AI does not have either a widely accepted definition.  There are two hypothesis in relation to consciousness: Weak AI states that you can achieve AGI with the computational models that we know e.g. without "consciousness." Strong AI, on the other hand states that there's something beyond our known computational models that is needed to achieve AGI.
Neural networks as used in machine learning are modeled in biological nervous systems but I don't think anyone has claimed that consciousness or even AGI can be expected from their implementation.
Some proposed consciousness theories worth mentioning are:
Daniel Benett's: Consciousness is nothing special. It's an illusion that you have control of your own decisions.  He backs it up with some experiments that have been done where subjects think they have reached a given decision.  In the experimental setup, however, it's demonstrated that before the subjects confirm that they've taken their decision an external observer can already determine the decision that the subject will take.
Douglas Hofstadter's theory of consciousness is based on the idea that consciousness is an effect achieved through computational deep recursion.
However, as I mentioned in my first point, consciousness is not scientifically defined to be even possible to set up a proper experiment that could determine wether consciousness can be achieved through computation or not.


How to find the angle of an arc to draw graphic I would like to draw an arc from a specific point to a goal point, during the process of drawing a larger path. I would like to do it using bezier curves, which aren't adequate for modeling circular arcs, but these equations found here seem to potentially estimate the arc pretty well (I can't tell if these equations correctly implement the circular arc using cubic Bezier curves (yet), but it seems like a good start). Here is the equations from that link.

start coordinate = {
  x: R,
  y: 0
}

control point 1 = {
  x: R,
  y: R * 4/3 * tan( phi / 4)
}

control point 2 = {
  x: R * ( cos(phi) + 4/3 * tan( phi/4 ) * sin(phi) ),
  y: R * ( sin(phi) - 4/3 * tan( phi/4 ) * cos(phi) ),
}

end coordinate = {
  x: R * cos(phi),
  y: R * sin(phi)
}

So let's say I start with a drawing of a path composed of some stuff, in this case just a few connected line segments (doesn't matter what they are):

Then what we want to do next, from the current point we left off at, is draw an arc. This is what that arc might look like:

You can see that there is a center where we can draw a radius, and a goal point where the arc ends (so it doesn't complete a whole circle).

My question is, how to determine the angle phi (in the equation above). That way I can use the equation. I am not sure what my current orientation is, if it is all relative to a global coordinate space or what. This is for traditional graphics. So need to figure that part out. Let's say it is a global coordinate space and not relative to the direction I moved along the path. Then this would be the angle:

I don't know, I'm already confused. So somehow I need to figure out some angle, which I'm not sure what to do. From there I think I could figure out the rest. Any help would be appreciated.

After the radius is found, then these equations above would take my simple circular arc, and turn it into a cubic Bezier equation so hopefully it could be drawn in an environment that only supports that and not arcs.

I think you have to determine the center C of your circle first. From your drawing, I suppose you want the last black segment to be tangeantial to the circle. Let say this last segment coordinates are P0 (x0, y0) and P1 (x1, y1).

Then the vector is:

vy = y1-y0
vx = x1-x0
with norm vr = sqrt(vy²+vx²)

And the vector vc from P1 to C is (2 choices depending on orientation):

vcy = +R*vx/vr or -R*vx/vr
vcx = -R*vy/vr or +R*vy/vr

then you obtain C coordinates (cx, cy) applying vc to P1. Now, your rotation angle phi must be expressed in the Cxy frame whatever the curve equation you use. The translation from (X, Y) in Cxy to (x, y) in Oxy is:

y = Y+cy
x = X+cx

Now about Bezier cubic curves, the equations you give assume you are starting at theta0=0 which is not the case on your figure. You can compute the starting angle with arctan2 (implemented on most of languages):

theta0 = arctan(-vcy, -vcx)

Then to plot a large angle arc with Bezier you actually have to cut it in small angle curves (let's say 30° max). So cut the (theta0, theta0+phi) angle into several (a, b) angles. NB: phi is negative on your figure (clockwise).

For every (a, b) angle, your Bezier cubic curve equation in Oxy frame is then:

K= 4/3 * tan( (b-a)/ 4)

start : y = cy+R*sin(a)
        x = cx+R*cos(a)

cp1 : y = cy+R*(sin(a)+K*cos(a))
      x = cx+R*(cos(a)-K*sin(a))

cp2 : y = cy+R*sin(b)- K*cos(b))
      x = cx+R*cos(b)+ K*sin(b))

end : y = cy+R*sin(b)
      x = cx+R*cos(b)

I did not not check these equations, I hope there is no mistake in.


How to prove this language is context free? There's lots of ways to prove a language is not context free. Going through some exercises, I'm stuck at a question that asks me to prove that a language is indeed context free.

$L = \{a^{(n+1)} b^{(m+2)}c^{(n+4)}\ |\ m, n ≥ 0 \}$

I see that the langauge is equivalent to $L = \{aa^nbbb^mccccc^n\}$, but I'm not sure if that helps at all.

Maybe breaking the language apart into a concatenation of three languages like $\{a^{n+1} | n>= 0\}.\{b^{m+2} | m >= 0\}.\{c^{n+4} | n>=0\}$ might be helpful, because we can do a rule separately for each? The n has to be equal for the left and right side though, which I'm having difficulty with.

Any help would be much appreciated!

I see that the language is equivalent to $L = \{aa^nbbb^mccccc^n\}$,

Indeed

  but I'm not sure if that helps at all.

Well, maybe not. How about if we write the equivalent language ever-so-slightly differently:

$$L = \{a^nabbb^mccccc^n\}$$

That's the same as

$$\begin{align}L &= \{a^nMc^n\}\\
M &= \{abbb^mcccc\}\\
\end{align}$$
And then
$$\begin{align}L &= \{a^nMc^n\}\\
M &= \{abbNcccc\}\\
N &= \{b^m\}\\
\end{align}$$
Which seems pretty straight-forward.

Or, to put it another way: Look for symmetries. Or try to create them.


Prove that regular languages are closed under the cycle operator I've got in a few days an exam and have problems to solve this task.

Let $L$ be a regular language over the alphabet $\Sigma$. We have the operation
$\operatorname{cycle}(L) = \{ xy \mid x,y\in \Sigma^* \text{ and } yx\in L\}$
And now we should show that $\operatorname{cycle}(L)$ is also regular.

The reference is that we could construct out of a DFA $D=(Q,\Sigma,\delta, q_0, F)$ with $L(D) = L$ a $\epsilon$-NFA $N$ with $L(N) = \operatorname{cycle}(L)$ and  $2 · |Q|^2 + 1$ states.

The idea is to decide nondeterministically at the beginning how much the word is cycled, and have a copy of the automaton for every case. In terms of the automaton, that means that we guess in which state $D$ would have been after consuming a word's prefix (which is a suffix of our input), and start in that state.

Now the construction. For every state $q \in Q$, separate $D$ into two parts $A_1$ and $A_2$. $A_1$ contains the states from which $q$ is reachable and $A_2$ the states that are reachable from $q$:

[source]

Note that any given node may be contained in both $A_1$ and $A_2$. Therefore,  the number of states can double if we make this step explicit.

Now we rewire this automaton so it accepts all words for which $q$ marks the "cycle point":

[source]

We get $|Q|$ automata of this form; create a new initial state which has $\varepsilon$-transitions to all their starting states. The resulting automaton accepts $\operatorname{cycle}(L)$. Altogether, we get at most $|Q|\cdot(2|Q|+1) + 1$ states, only $|Q|$ more states than the reference claims are possible.

You can achieve $2|Q|^2 + 1$ states by modifying the component automata a little bit; eliminate all $q_0$ by replacing the incoming $\varepsilon$-transitions with copies of its outgoing transitions. That is, for every pair of transitions $(q_1,\varepsilon,q_0), (q_0,a,q_2)$, introduce a transition $(q_1,a,q_2)$.

Rigorous construction and correctness proof remain as exercise.


Primitive recursive functions and unbounded quantifiers From what I know If the predicate $P(t,x_1,...,x_n)$ belongs to some PRC class $\zeta$ then so do the predicates

$(\forall t)_{\le y}$  $P(t,x_1,...,x_n)$

$(\exists t)_{\le y}$  $P(t,x_1,...,x_n)$

But what about the unbounded quantifier? what difference does it make if I replace $(\forall t)_\le$ with $(\forall t)$ and also $(\exists t)_\le$ with $(\exists t)$ ?

Davis in his book page 43 says:

  Theorem 3.3: A function is primitive recursive if and only if it belongs to every PRC class

I saw a problem related to what I said that I couldn't solve, here it is :

  If $P(x)$ and $Q(x)$ are primitive recursive predicates which one of the following may not be primitive recursive:

$P(x) \rightarrow Q(x)$
$Q(z) \wedge P([\sqrt{x}])$
$\forall x(x \le y \rightarrow P(x))$
$\exists x(P(x) \wedge Q(x)) $

Since only one of the above choices is right, so I don't know 3 is the answer or 4!

If $P(t,x_1,\dots,x_n) \in \zeta$, then clearly $(\forall t)_{\le 0}P(t,x_1,\dots,x_n) = P(0,x_1,\dots,x_n) \in \zeta$.

Moreover, if for some $y$, we have $(\forall t)_{\le y}P(t,x_1,\dots,x_n) \in \zeta$, then it can easily be shown that $(\forall t)_{\le y+1}P(t,x_1,\dots,x_n) = P(y+1,x_1,\dots,x_n) \land (\forall t)_{\le y}P(t,x_1,\dots,x_n) \in \zeta$, noting that taking the logical and is a primitive recursive operation.

By induction, we have that for any $y$,  $(\forall t)_{\le y}P(t,x_1,\dots,x_n) \in \zeta$. Things work similarly for $(\exists t)_{\le y}$. However, this reasoning doesn't extend to unbounded quantifiers, and in the general case, $\forall t P(t,x_1,\dots,x_n) \notin \zeta$.

If you think of PRC predicates as things that can be checked by a computer in finite time, the underlying meaning is that

if it takes finite time to check whether a given proposition is true for any given value, then it also takes finite time to check whether it's true for any/all values in a finite set (at most the sum of the finite times taken to check for each element in the set)
on the other hand, it's not necessarily possible to check that it's true for any/all values in an infinite set. Naively checking for $0$, then $1$, then $2$, etc..., could take forever.

The answer to your second question is proposition 4. Indeed, in proposition 3, the universal quantifier over $x$ is bounded by the free variable $y$, which is a finite value. In other words, proposition 3 could be rewritten as $(\forall x)_{\le y}P(x)$.


Return 3 smallest elements in a list How would we find the three smallest elements in a list and return it as a tuple (a,b,c) using divide and conquer?
So far I've considered the following:
def sm(L):
    # base
    if len(L) == 3:
        return L sorted
    else:
        # divide

How would I divide the list so that we guarantee the list to be of size 3 and be in the base case?

In the divide and conquer approach, we break the problem into subproblems and we try to solve these subproblems.
So, you can divide your problem into two subproblems till you reach one element. Now you can combine these subproblems but in each step, you know the 3 smallest elements of these subproblems.
Fortunately, Merge Sort uses the divide and conquer idea to sort an array. Please note that in each step of combining subproblems, it is sufficient to hold only three elements of each sub-lists. So, it is not necessary to sort all elements. (Just the 3 smallest elements)
Check Merge sort here:
https://www.geeksforgeeks.org/merge-sort/


asymptotic tight bounds for quadratic functions In Introduction to Algorithms by CLRS, it's said

For any quadratic function $f(n)=an^2+bn+c$, where $a$, $b$ and $c$ are constants and $a>0$, $f(n)=\Theta (n^2).$ Formally, to show the same thing, we take constants $c_1=a/4, c_2=7a/4$ and $n_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a}).$ You may verify that $0\leq c_1n^2\leq an^2+bn+c \leq c_2n^2$ for all $n\geq n_0.$

They didn't specify how values of these constants came? I tried to prove it but couldn't.

I think I can suggest more easy way. Having $a>0$ in $f(n)=an^2+bn+c$ we can take any $a_1<a$ and then show that $a_1n^2 < an^2+bn+c$ for some $N_1,n>N_1$ , because it is same as $a_1 < a + \frac{bn+c}{n^2}$.
Same we can make for any $a<a_2 \Rightarrow an^2+bn+c < a_2n^2$ for some $N_2,n>N_2$ because it is same as $a + \frac{bn+c}{n^2}< a_2$.
At last we will have $a_1n^2 <an^2+bn+c < a_2n^2$.


How to schedule n jobs that come at different times on 1 machine (each taking a different time to complete the task)? Let's say I have to do n jobs, and each job can be done at or after a time T(i) (1<=i<=n). And we have 1 machine and the machine takes a time M to do any job whatsoever. The machine once started can be used again only after it's job is done. What's the optimal way to schedule these jobs on the machines?

This problem lends itself to Mixed Integer Programming. The trick is to consider that there are multiple versions of each job for each machine, and you have to cover each job once.

So you can have $c_{j,m}$ as the indicator variables that say if a job is assigned to a machine. You have to introduce a constraint that says $$\sum_m  c_{j,m} \geq 1.$$


Remapping values to bias a uniform set towards a certain curvature I'm trying to generate random numbers that would be distributed according to a sample curve that I provide in the shape of vertices.

I came up with this:

function curve_map(curve) {
    //  convert to sorted points
    var points = [];
    for (var x in curve) { var y = Number(curve[x]);
        points.push( {'x' : Number(x), 'y' : y} );
    }
    points.sort(function(a,b) {return a.x - b.x});

    //  create segments
    this.segments = [];
    var posy = 0;
    for (var i = 1; i < points.length; i++) {
        var n = points[i].y + points[i - 1].y;
        var seg = {
            'x0' : points[i - 1].x,     'x1' : points[i].x,
            'y0' : points[i - 1].y,     'y1' : points[i].y,
            'n0' : posy,                'n1' : posy + n
        };
        posy = seg.n1;
        this.segments.push(seg);
    }

    //  normalize n
    for (var i = 0; i < this.segments.length; i++) {
        this.segments[i].n0 /= posy;
        this.segments[i].n1 /= posy;
        this.segments[i].nr = this.segments[i].n1 - this.segments[i].n0;
    }

    //  func
    this.apply = function(x) {
        for (var i = 0; i < this.segments.length; i++) {
            var seg = this.segments[i];
            if (x >= seg.n0 && x <= seg.n1) {
                var along = (x - seg.n0) / seg.nr;
                //along = seg.y0 / (seg.y1 - seg.y0);

                var val = seg.x0 + (seg.x1 - seg.x0) * along;
                return val;
            }
        }
    }.bind(this);
}

What this does is

take 2 points and make a segment, preserving the original coordinates
each segment's length is equal to the sum of Y of both points
after creating a segment between all the points, normalize so the chain of segments reaches from 0 to 1

So now I have a chain of segments. If I feed it a value, it looks up which segment it belongs to, checks how far along in the segment it is and remaps the location to the original interpolated x coordinates of the segment.

In theory I expected this to shave off the corners of the original curve since I don't know how to account for the difference in Y values in each segment.

Anyways, the result is quite different:

The red curve is what I fed the "curve_map" and what it should mimic

The black one is ~10k uniformly distributed random values put through the algorithm.

At least it sorta follows the line... but this is nowhere near good enough. Also I'm out of ideas on how to fix it.

Does anybody know if what I'm trying to do actually has a name? So I could read up on it or maybe find a neat algorithm to port..

For continuous distributions, you can use the inverse transform sampling method.  See also https://stats.stackexchange.com/q/176955/2921 and https://en.wikipedia.org/wiki/Ziggurat_algorithm.

For discrete distributions, you just generate a random floating point number in the range [0,1], and then figure out which of the buckets $[0,p_1)$, $[p_1,p_1+p_2)$, $[p_1+p_2,p_1+p_2+p_3)$, ..., $[..,1]$ it falls into, where $p_1,p_2,p_3,\ldots$ are the desired probabilities of the possible values.  See also https://stats.stackexchange.com/q/26858/2921 and http://www.keithschwarz.com/darts-dice-coins/.


What is the role of mathematics in programming? I am almost totally uneducated in programming and computer science in general, though I am really fascinated by these topics. I read that mathematics is important in programming and that nowadays many mathematicians specialise in applied mathematics in this field. So, I wonder how these two branches are linked with each other. What are the fields of mathematics that are useful (maybe unavoidable?) in writing a computer program?

You don't need any math to write a Hello World or a very simple website.

You will need to know some discrete mathematics and algorithm analysis to write a program that finds a route between two cities.

You will need to know matrix transformations and quaternions to write a game engine.

You will need to know a lot about all kinds of mathematical fields to write the next Wolfram Mathematica.

What I'm trying to say, what fields of mathematics you will need to know and to what degree will depend a lot on what kind of programs do you want to write. But the ones that tend to be most widely useful are data structures, algorithms and their analysis.


Regular expression that have the same number of 0 and 1 I'm doing some Automata Theory exercises through a book and I'm trying to solve the exercise below but I cant figure out how to solve it.

Could I get a hint on how to construct a regular expression that describe the following language given the alphabet $\Sigma = \{0, 1\}$:

$A = \{w \in \Sigma^ * : |w|_0 = |w|_1 \cup \Sigma^*\{00,11\}\Sigma^*\}$

Some examples that I think might be right:

00011 belongs to the language

0does not belong to the language

1does not belong to the language

0011 belongs to the language

01010101 belongs to the language

$\lambda$ belongs to the language because $w_0=0$ and $w_1=0$

One solution that I found so far is that the regular expression $\alpha$ would be:

$\alpha = ((0 \cup 1) \Sigma^*)^*$

However, to be honest, I really does not have sure if this one is correct.

Could please someone clarify this one?

Thanks !

Your $\alpha$ matches all strings, and is certainly incorrect.

The language is a union of two sets, so you can consider the two parts respectively and construct the regular expression with the form $R_1\mid R_2$.

The $\Sigma^*\{00,11\}\Sigma^*$ part is easy.

The $|w|_0=|w|_1$ part is somewhat tricky. You cannot construct a regular expression for $|w|_0=|w|_1$ because this language is not regular. However, You can only care about the set $S=\{w\mid |w|_0=|w|_1\text{but }w\notin\Sigma^*\{00,11\}\Sigma^*\}$ instead of the set $\{w\mid |w|_0=|w|_1\}$. Now try to figure out what $S$ looks like and write a regular expression for it. This is not hard.


Time complexity of a compiler I am interested in the time complexity of a compiler. Clearly this is a very complicated question as there are many compilers, compiler options and variables to consider. Specifically, I am interested in LLVM but would be interested in any thoughts people had or places to start research. A quite google seems to bring little to light.

My guess would be that there are some optimisation steps which are exponential, but which have little impact on the actual time. Eg, exponential based on the number are arguments of a function.

From the top of my head, I would say that generating the AST tree would be linear. IR generation would require stepping through the tree while looking up values in ever growing tables, so $O(n^2)$ or $O(n\log n)$. Code generation and linking would be a similar type of operation. Therefore, my guess would be $O(n^2)$, if we removed exponentials of variables which do not realistically grow.

I could be completely wrong though. Does anyone have any thoughts on it?

The best book to answer your question would probably be: Cooper and Torczon, "Engineering a Compiler," 2003.  If you have access to a university library you should be able to borrow a copy.

In a production compiler like llvm or gcc the designers make every effort to keep all the algorithms below $O(n^2)$ where $n$ is the size of the input.  For some of the analysis for the "optimization" phases this means that you need to use heuristics rather than producing truly optimal code.

The lexer is a finite state machine, so $O(n)$ in the size of the input (in characters) and produces a stream of $O(n)$ tokens that is passed to the parser.

For many compilers for many languages the parser is LALR(1) and thus processes the token stream in time $O(n)$ in the number of input tokens.  During parsing you typically have to keep track of a symbol table, but, for many languages, that can be handled with a stack of hash tables ("dictionaries").  Each dictionary access is $O(1)$, but you may occasionally have to walk the stack to look up a symbol.  The depth of the stack is $O(s)$ where $s$ is the nesting depth of the scopes.  (So in C-like languages, how many layers of curly braces you are inside.)

Then the parse tree is typically "flattened" into a control flow graph.  The nodes of the control flow graph might be 3-address instructions (similar to a RISC assembly language), and the size of the control flow graph will typically be linear in the size of the parse tree.

Then a series of redundancy elimination steps are typically applied (common subexpression elimination, loop invariant code motion, constant propagation, ...).  (This is often called "optimization" although there is rarely anything optimal about the result, the real goal is to improve the code as much as is possible within the time and space constraints we have placed on the compiler.)  Each redundancy elimination step will typically require proofs of some facts about the control flow graph.  These proofs are typically done using data flow analysis.  Most data-flow analyses are designed so that they will converge in $O(d)$ passes over the flow graph where $d$ is (roughly speaking) the loop nesting depth and a pass over the flow graph takes time $O(n)$ where $n$ is the number of 3-address instructions.

For more sophisticated optimizations you might want to do more sophisticated analyses.  At this point you start running into tradeoffs.  You want your analysis algorithms to take much less than $O(n^2)$ time in the size of the whole-program's flow graph, but this means you need to do without information (and program improving transformations) that might be expensive to prove.  A classic example of this is alias analysis, where for some pair of memory writes you would like to prove that the two writes can never target the same memory location.  (You might want to do an alias analysis to see if you could move one instruction above the other.)  But to get accurate information about aliases you might need to analyze every possible control path through the program, which is exponential in the number of branches in the program (and thus exponential in the number of nodes in the control flow graph.)

Next you get into register allocation.  Register allocation can be phrased as a graph-coloring problem, and coloring a graph with a minimal number of colors is known to be NP-Hard.  So most compilers use some kind of greedy heuristic combined with register spilling with the goal of reducing the number of register spills as best as possible within reasonable time bounds.

Finally you get into code generation.  Code generation is typically done a maximal basic-block at a time where a basic block is a set of linearly connected control flow graph nodes with a single entry and single exit.  This can be reformulated as a graph covering problem where the graph you are trying to cover is the dependence graph of the set of 3-address instructions in the basic block, and you are trying to cover with a set of graphs that represent the available machine instructions.  This problem is exponential in the size of the largest basic block (which could, in principle, be the same order as the size of the entire program), so this is again typically done with heuristics where only a small subset of the possible coverings are examined.


Turing machine to output enumeration of a language I am trying to write a Turing machine enumerator that enumerates the language where $w = 0^n1^n$ and $n ≥ 0$.

So for example it should output the following to the first tape:
e,#,0,1,#,0,0,1,1,#,0,0,0,1,1,1 etc.

Here e means empty, i.e., to leave that index blank.

I can't figure out how to display this as a Turing machine with states and transitions.

Here is one way to approach this problem. Program a machine that acts as follows:

Initialize the tape with $\#01$ (or $\epsilon\#01$).
At each step, write $\#$, then go back to the previous $\#$ and copy the string written there, say $0^n1^n$.
Change the first $1$ to a $0$, add two $1$s at the end, and go to the next step.


If P != NP, then 3-SAT is not in P I hope I'm in the right section:

I know that if P = NP, then 3-SAT can be solved in P (Cook), but is the opposite valid, too? If P != NP, then 3-SAT is not in P?

Thanks!

The opposite is valid.

$3SAT$ is an $NP$-complete problem, so every problem in $NP$ can be reduced to $3SAT$.

If $P \neq NP$ and $3SAT \in P$, every problem in $NP$ would be in $P$, contradicting $P \neq NP$. So if $P \neq NP$ then $3SAT \notin P$.


Operating System: Performance of Demand Paging I am reading Operating systems from the book "Operating System Concepts" by Peter Baer Galvin, 7th edition.

  Performance of Demand Paging:

  Let p be the probability of a page fault (0 $\leqslant$ p $\leqslant$1). We would expect p to
  be close to zero—that is, we would expect to have only a few page faults. The
  effective access time is then
  effective access time = (1 - p) x ma + p x page fault time.

  To compute the effective access time, we must know how much time is
  needed to service a page fault.

  Example If we take an average page-fault service time of 8 milliseconds and a
  memory-access time of 200 nanoseconds, then the effective access time in
  nanoseconds is

  effective access time = (1 - p) x (200) + p (8 milliseconds)

  = (1 - p) x 200 + p x 8.00(1000

  = 200 + 7,999,800 x p.

My doubt when there is a page table hit it we should multiply p by (ma + ma) because, we need one memory access to access page table from memory and one more memory access to access the actual page from memory.
In my opinion formula should be
effective access time = (1 - p)x(ma+ma) + p x page fault time.

Where ma is memory access time

Please let me  where am I wrong?

CPUs keep in special purpose caches recently addressed page table entries. Entries are usually named "TLB = Translation Lookaside Buffer"

We have 3 cases :

The page is in TLBs and the access is allowed (no write in read-only areas, no user access in supervisor pages, etc...). The delay to access the TLBs is usually hidden through pipelining. The access time depends on whether data is in caches or not. Can be less than 1ns on current high performance CPUs.
The page is not in TLBs. The CPU must find a way to update the TLBs. Some do it with simple hardware mechanisms, others use exceptions and let software do the work. In both cases, one or more memory accesses to pages tables is needed. 8ms is far too much for such operations which have a huge impact on CPU performance. This is not really "page faults"
The page may be in the TLBs, or not, but there is a real "page fault", for example the memory accessed has been swapped to disk, or not yet initialized, or the applications has a bug... The operating system will need to do complex thing to correct that, loading memory and updating page tables, or killing the applications... 8ms seems a reasonable delay for some of these operations.


What is time complexity in this case? I have the recurrence of the form

  T(n) = T(n/2) + O(n)

This can be solved using master's theorem and if i use the results of the theorem, the recurrence evaluates to a time complexity of O(n). But if i think of it in terms of its tree, the input is reducing by half each time so we have a tree of logn height. Cost of each level is O(n). So we might have a complexity of O(nlogn). Now i am confused that is it O(nlogn) or O(n). Please help me.

In this problem, the input size at each level of recursion is reduced by a factor of 2. At our topmost level, we have $cn$ for some constant $c$, but in the second level? In picturing a tree, our top most level (our leaf node) has one child, $cn/2$. This child has a single child of its own: $cn/4$, and so on.

To get the time complexity for our recurrence relation, we have to sum up the work done in each layer of the tree. You state that each layer does $O(n)$ work, but this is where your mistake is. Each layer does half the work of the previous layer. Therefore we end up with the summation $\sum_{i=0}^{n}\frac{n}{2^i}$. This sum is asymptotically equivalent to $O(n)$. Therefore, the result you reached using the Master Theorem is correct.


What is the time complexity Big-O of this algorithm? What is the time complexity Big-O of this algorithm?

, The first assumption it's O(N * lg N) but it is not correct, why?

        count = 0
        for i = N : 1 {
            for j = 0 : i {
                count = count + 1
                j =  j + 1
            }
            i = i/2
        }
        print(count)

The second for-loop while be executed N + N/2 + N/4 +....+ N/N

, the first for-loop decides how much the second for-loop will be executed.

When i = 0, j loops until N

, i = N/2, j loops until N/2

, And so on

, The Big O notation of N + N/2 + N/4 +....+ N/N will be O(N)


Help with understanding why we need an expectation in the loss I am reading the paper SV2P - Stochastic Varaiational Video Prediction (https://arxiv.org/abs/1710.11252). In it the authors use the loss shown in the image:

Why do we need expectation in the reconstruction loss?
I think that the loss is similar to the one used in the VAE paper.

It's because $z$ is a random variable, and the term is a function of $z$.  So, without the expectation, the $\log$ term would be a random variable, and you can't use that as a loss; the loss needs to be a number.  You can use its mean (its expectation).


Algorithm to determine if recursion was breadth first or depth first Given a tree $T$ and a sequence of nodes $S$, with the only constraint on $S$ being that it's done through some type of recursion - that is, a node can only appear in $S$ if all of its ancestors have already appeared, what's a good algorithm to determine if $S$ is a breadth first visit, a depth first visit, or neither?

A brute force approach is to compute every breadth first and depth first sequences and see if any is identical to $S$.  Is there a better approach?

What if we don't want a yes or no answer, but a measure of distance.  E.g. $breadth < S < R < U < depth$; what's a good algorithm to determine distance? (A brute force approach for this is just $max(length(longest{\_}common{\_}subsequence(S, breadth))/length(breadth))$ over every BFS - again, is there a better way to do this?)

Recall that both BFS and DFS are worklist algorithms.  This means they maintain a "worklist" of vertices that need to be visited, but haven't been yet.  You can think of the worklist as a list or set  of "stuff that needs to be done", where here the kind of tasks that need to be done are of the form "visit vertex $v$".  When DFS or BFS visits a vertex $v$, we find all its neighbors, and add each one that has not yet been visited to the worklist (if it is not already present in the worklist).

The only difference between DFS and BFS is in how they implement the worklist.  DFS implements the worklist as a stack.  BFS implements the worklist as a queue.

So, here is how you can test whether your sequence was obtained by DFS, by BFS, or by something else.  Replay the sequence of visited nodes.  Keep a worklist, just like DFS/BFS would, but use a set data structure, and add a timestamp to each item in the worklist recording when it first entered the worklist.  At each step, when you visit a node $v$, check that $v$ is in the worklist, and check its timestamp.  If its timestamp is the earliest of all items in the worklist, this is consistent with removal from a queue (i.e., BFS); if it is the latest of all items in the worklist, it is consistent with a stack (i.e., DFS); otherwise, it is neither.  Then, add to the worklist each neighbor of $v$ that has not yet been visited and that isn't already in the worklist, using the same timestamp for all of them (since they all entered the worklist on the same step of the sequence).

Iterate through the entire sequence like this.  If every step is consistent with DFS (i.e., consistently stack-like), then this sequence could have been generated by some DFS traversal.  If every step is consistent with BFS (i.e., consistently queue-like), then this sequence could have been generated by some BFS traversal.  If neither of these are true, then you know that this was generated by neither DFS nor BFS.

You can make this algorithm very efficient: at most a logarithmic slowdown compared to a DFS/BFS itself (and maybe even faster is possible).


Turing machine - infinite tape in one or two directions I have seen turing machines beeing represented with tapes infinite in one, and in two directions. Is there any difference in the power of such turing machines, or are they basically equivalent? In my head I think they are equivalent, since I guess that there must be some way to represent the two-way infinite tape as a one-way infinite tape, but I can't seem to find a proof or example.

They are equivalent in computational power.  Anything computable by one of these two kinds of Turing machines, is computable by the other kind.  Let's look at how to simulate a Turing machine with a doubly infinite tape, on a Turing machine with a singly infinite tape.

The idea is to cut your doubly infinite tape in two, so that you have
two singly infinite tapes, a left one and a right one, which you will ultimately merge. You may mark
the ends with a tape location containing a special EOF symbol. You
also duplicate your finite control, so that you have two identical
finite state controls. You assume that you have a control passing
device (see below), so that, when the left machine tries to go beyond the right
end of its tape, it passes the control to the right machine, on its
leftmost tape position (just before the left end of the right
tape). And conversely, when attempting to pass the left end of the
right tape.

Now, in order to distinguish the left and the right machines, we
change the names of the states and the tape symbols, by indexing them
with $R$ and $L$ respectively for the left and the right machine. And
we change accordingly the transitions of the two machines so that they
work as before.

Now we are ready to merge the two half-tapes, for example by folding
the right one onto the left one. For that you flip over the right half
tape, and you are careful to modify accordingly the transitions,
exchanging right for left and left for right. Then you fuse the two
half tapes into a single tape containing pairs of symbols, a left one
and a right one, each component being possibly blank.

You modify again the transitions of both machines, so that the left
(resp. right) transitions use and modify only the left (resp. right)
parts of the pairs on the tape. Then you merge the control of the two machines by
simple set union respectively for states, and for transitions.

You add a set of transitions for each existing state, so that when the
tape symbol is EOF, it goes back to the previous tape location (the
first non-EOF location) and the state changes to its chiral
counterpart: if it is a left (resp. right) state, it changes to its
right (resp. left) counterpart.  That is the control passing device.

I may have forgotten a detail, but this is the general idea of the
construction. The proof is left as an execise.

Of course, the initial tape (input) must be modified accordingly.
But that can be made simple by placing the input (if finite) fully on
the left side (the one that is not flipped over) of the tape cut.

Then you put away the screw driver as it may be dangerous for the kids.

PS I only showed that the doubly infinite tape can be simulated with a singly infinite tape. The converse seems too obvious.


A survey on ranking keyword search results To rank the keyword search results, I'm trying to crack the way the Airbnb algorithm or similar ones work. I'm not asking which features they are using since those are different depending on the business needs. What I'm asking is where can I find a paper/survey/book to see what are the various relevancy metrics in addition to TF-IDF and PageRank? and how can I merge various metrics/algorithms into a single algorithm to sort the search results?

Input: a couple of keywords
Output: a ranked list of options relevant to the input keywords

Anything from links to surveys/books/algorithms/open-source software would work.

Best

There is a research literature on this subject that uses machine learning for ranking; it is often known under the term learning to rank.  I recommend reading the papers on that subject.


Finite loop on a NFA I understand that in a non-deterministic automaton, an input can lead to one, more than one, or no transition for a given state.
Given this information, I would assume that if the input lead to a loop, this loop would be infinite until a determined input happened (being one || more || ε).
However I would like to know if there's a way to represent a "finite" loop with an NFA. For example, an ATM where a person only has a determined amount of chances to get the password right. If not, the operation is cancelled.
The input is always the same (0-9 digits), so how can the outcome be different after 3 tries?
Thank you for any hints on this!

Let's assume the user needs to enter a password and then press OK. Let's assume the password is 42:

But let's say the user makes a mistake, how can we allow three tries? By adding failure states, waiting for OK, and if we're in a failure state when OK gets pressed we get another try. Let $*$ notate 'anything else' - any character that wasn't handled by another arrow.


Approximation for vector bin packing I came across the following question. Given a 2-approximation for minimum bin packing problem, find a 2d-approximation for d-dimensional bin backing.

To clarify, inputs to the bin packing problem are real numbers $x_1,...,x_n\in [0,1]$, which should be divided into $k$ bins $S_1,...,S_k$ such that for all $i$: $\sum\limits_{x\in S_i}x\le 1$.

Inputs to the vector bin packing problem are vectors $x_1,...,x_n\in [0,1]^d$, which should be divided into $k$ bins $S_1,...,S_k$ such that for all $1\le i \le k$ and $1\le j\le d$: $\sum\limits_{x\in S_i} x^j\le 1$, where $x^j$ is the $j'th$ coordinate of $x$.

It seems intuitive to use the 2-approximation on each coordinate of the given vectors $x_1,...,x_n\in [0,1]^d$ and obtain $d$ partitions into at most $2k$ bins (where $k$ is the minimal number of bins for the vectors partition). However, i cant seem to combine those bins into a partition of size at most $2d\cdot k$. For any vector $x_i\in [0,1]^d$, let $b_i\in \left\{1,...,2k\right\}^d$ be the vector whose $j'th$ entry is the bin in which $x_i^j$ was placed (after running the approximation on all the $j'th$ components). Since i cant allow two vectors $x_i,x_j$, whose corresponding vectors $b_i,b_j$ differ in at least one component, go into the same bin, it seems i need at least $(2k)^d$ bins. What am i missing?

Create an instance $y_1,\ldots,y_n$ of bin packing by taking $y_i = \max(x_i^1,\ldots,x_i^d)$, and solve it using the given approximation algorithm. The solution is feasible for the vector bin packing problem. On the other hand, given a solution for the vector bin packing problem, you can construct a solution for the "max" bin packing problem using at most a factor $d$ more bins by splitting each bin into $d$ bins according to the largest coordinate.


How to represent whitespace in a context-free grammar? Say we want to support: xx

The following grammar does accept it:

S -> xAx
A -> ε.

because S => xAx => xx.

But what about supporting: x x

I realize this might be a stupid question but I'm really unable to find a definite answer. Especially as

S -> xAx
S -> x A x

appear to be equivalent representations in most references.

This is a classical confusion between language and metalanguage.

More generally, you have the same problem when you want to include in
your symbols, expecially terminal symbols, characters that have
syntactic meaning in the syntax of grammars, for example the symbol
"|" which is often used to give on the same line all possible
right-hand-sides for a given non-terminal.

In such a case, you do what I just did: use some mechanism for
quotation, such as "|", or " " in the case of a space. Some form of quoting is the usual technique to avoid confusion between language and metalanguage.
And as you remarked, the language of grammars already uses the space for its own (lack of) purposes.

So you write:

S -> xAx
A -> " "

Of course, the spaces outside the quotes still play the same role as before, wherever allowed. So the grammar could be written as well:

S ->  x A  x
A  ->   " "

Whatever is within quote must be written exactly as expected.

However, in many contexts (such as programming language syntax), it is implicit that you can add spaces wherever you want between terminal. So you have to be clear whather you just want one compulsory space where you have the terminal " ", or whether you forbid spaces, unless specified by the syntax as done here.

The quotation marks are metasyntax, i.e. part of the language used to write the grammar, like the arrow. The analyser (whether LR(1) or any other) will ignore the quotes, as it ignores the arrow ->. It would work as well with a grammar written as [(S,xAx)(A," ")]. Some metalanguages for writing grammars, such as BNF, simplify the issue by making the quotes compulsory around terminals ... though there is still a problem when terminals include the quoting symbols ... but this has solutions.

Another question you may want to look at is: What are the meanings of metalanguage and metasyntax and EBNF?


The difference between a sequence and a set I am new to discrete mathematics and the theory of computation I am trying to learn and understand the terminology.

I am having a difficult time understanding the difference between a set and a sequence. I understand that unlike a set, in a sequence order and repetition does matter and sequences contain objects rather than elements or members. However, I don't see how sequences can be logically applied to the real world.

Can someone please give a clear and simple example of when a sequence would be used as opposed to a set and explain how is a sequence is different that a set?

I appreciate any clarification.

Your question uses a number of words, such as "logic" that might require clarification. In order to answer I should start with some preliminary definitions.

Consider a universe of objects. The objects have different properties. We do not know yet if each object can be identified. We say that all objects that share a certain property form a set (this statement is related to the notion of specification in Set Theory).

For instance in order to have a set of all sand particles you do not need to be able to identify each particle of sand. You just need to be able to distinguish them from objects that are not sand particles.

So a set is either an empty set or a set of all objects in our universe that share some common property. Two sets $A$ and $B$ are considered equal if an element $x$ belongs to $A$ if and only if $x$ belongs to $B$. (this statement is known as extensionality). It follows that removal of duplicates does not change a set.

In order to define a sequence we need to introduce natural numbers into our universe. Now a sequence is a mapping from the set of natural numbers into a set of objects. That is each number is associated with a unique object.
(You need to be able to identify individual objects in order to define a sequence).

A sequence can also be considered as a set where each element has a special form. For example a sequence A, B, C, B, ... can be represented as a set

   { {1,{A}}, {2,{B}}, {3,{C}}, {4,{B}}, ... }

Example

Now here is an example where a sequence can be used as opposed to a set. Suppose our universe consists of colored grains of sand. Assume each grain is either green or red. Then we could have only four different sets in our universe:

  {}, {G}, {R}, {G, R}

and many higher order sets, such as

  {{G}}, {G,{R}}, ... etc.

However we could form many infinite sequences without using higher-order sets:

  R, G, G, R, G, R, R, G, ....

Programming

In programming languages some basic data structures, such as arrays or lists are sequences, that is you can refer to an element by its sequence number. Using such structures to model sets requires additional processing: identifying duplicates and keeping them in a sorted state.

A natural data structure to model sets is a hash table. This model handles duplicates efficiently, however computing a hash table that represents a union of two hash tables may have complexity proportional to the size of the hash tables.

Hope this clarifies the difference between sequences and sets.


Resolution complexity versus a constrained SAT algorithm EDIT: ad hoc speed-ups are excluded.

We have the result that propositional resolution requires exponential time. The resolution result uses the proof of the pigeonhole principle as an example of a proof that takes exponential time.

Let's also say we have a hypothetical algorithm M for SAT that runs in polynomial time.
EDIT : M is correct, complete, sound, and general-purpose; it contains no ad hoc speed-up rules for the pigeonhole principle or any other theorem that requires exponential length in resolution. M takes its input in clausal form; we'll set up the input like a resolution proof where the consequent is negated to lead to unsatisfiability if the theorem is true. Now let's consider how the proof of the pigeonhole principle works in algorithm M with a strong condition C added:

C. We are given that M simply transforms one clause (or set of clauses) to another clause (or set of clauses). Every such transformation is logically sound.

Some questions; please point out the most fatal flaws:

Given condition C above, and since M's rule system must be finite, correct, and complete, can we conclude that there is a translation from M's rule system to an equivalent set of expansions based on resolution?
Are we now in a place where we can conclude that M would produce a computation that could be mapped by the translation in point 1 above into an impossible polynomial-time resolution proof of the pigeonhole principle?

While the deductions made by $M$ can have equivalent (possibly exponentially bigger) resolution proofs, I'm not sure what you mean by translating the rule system of $M$ into resolution form. If $M$ has a rule saying that if the problem is a PHP (pigeonhole principle) problem then output unsat if number of pigeons > number of holes, how would you translate that rule into resolution form?
Edit: To elaborate on the last point, we know that Extended Resolution (ER) which in a nutshell, allows one to add new variables, has polynomial-size PHP proofs. Now suppose, $M$ uses ER to prove PHP. Such reasoning cannot be "directly" translated into a resolution proof as that would require adding new variables to the formula which is not allowed in pure resolution proofs.
As I mentioned in point 1, you can translate the deductions by $M$ into resolution proofs of those deductions but the resolution proof might be exponentially larger.


Context free grammar for this language Is this language Context Free?

$L=\{a^{n+3} b^{2m} \mid n \neq m \}$

I think that I could split the languages into $L_1$ and $L_2$ with the conditions $n<m$ and $n>m$, provide 2 CF grammars and then to make the union. But I don't know how to put the condition $n<m$ to the grammar or how to think about the conditions. Thank you!

Idea: Construct a Grammar fragment for $a^nb^(2n)$. Complement it with rules that break the symmetry.

1: L -> aaaX

2: X -> aXbb   // So far, the subsequence of terminals does not belong to L.
               // The next two rules break the symmetry.
3: X -> aP
4: X -> Qbb

5: P -> aP  | epsilon
6: Q -> Qbb | epsilon

Proof sketch

The grammar is clearly context-free.

The correctness can be proven eg. by induction over possible derivations. The intuition is simple:

Each derivation starts with applying rule 1 followed by an arbitrary number of. applications of rule 2. At each step of this derivation, the current item matches a^3a^nXb^(2n); n >= 0. In particular, n=min the nomenclature of the problem statement.
After application of any one of the rules 3 and 4, non-terminals will only ever expand into sequences of either a or b.
At least on application of rule 3 or 4 is necessary to complete a derivation.

The very first application of 3/4 introduces the imbalance between a and bb in the terminal string. After passing that 'trapdoor', this imbalance will never be offset, since only the 'right' terminals will be produced henceforth.


LK-$\phi$ proof of $\exists y Pby$ I am having difficulty with the concept of $LK-\Phi$ proofs, here is a question I have been working on:

  Let $\Phi = \{Pafa\}$, where $P$ is a binary predicate symbol and $f$ is a unary function symbol. Give an $LK-\Phi$ proof of $\exists y Pby$. You do not need to show exchanges and weakenings.

My intution for these questions is very little unless it is blatantly obvious over what to do, but I do know that in the system $LK$ we have a $LK-\Phi$ proof if we have $A\to A$ or $\to A$ where $A\in\Phi$. So in this situation I think I set this up as the following:

$$\to \exists y Pby$$and then I would have a sequent above it where I would apply the $\exists R$ rule, which would create the sequent above as: $$\to Pba$$ but from here I am not sure at all what to do whether I need to rely on some sort of trick or anything? Any help would be greatly greatly appreciated, this is for an exam I am studying.

First of all, let me recommend then you use parentheses. So $\Phi = \{P(a,f(a))\}$, and you're trying to derive $\exists y P(b,y)$ from this.

If it were $\exists y P(a,y)$ instead, the proof would be very simple. You start by using the $\Phi$-rule to deduce $\vdash P(a,f(a))$, and then using the $\exists R$ rule you deduce $\vdash \exists y P(a,y)$.

As it stands, you cannot deduce $\exists y P(b,y)$ from $\Phi$ since $\exists y P(b,y)$ is not logically entailed from $\Phi$. For example, consider the interpretation in which $f$ is the identity and $P(x,y)$ is true only if $x=y=a$. Then $\Phi$ holds but $\exists y P(b,y)$ is false. Since LK-$\Phi$ is sound, you cannot deduce $\exists y P(b,y)$ from $\Phi$.


How do we know to what community a vertex belongs to in the Girvan-Newman algorithm? So I've been doing some reading on community detection in graphs as I'm planning on working on my thesis for it. I've been reviewing papers regarding the same and came across the Girvan-Newman algorithm. I've read the paper and have a doubt which I couldn't really figure out.

The algorithm works by removing the edge which has the highest value of "edge betweenness" in every iteration. Suppose I have a graph $G(V, E)$ such that $V = \{ v_{1}, v_2, \cdots , v_n\}$. Now suppose this graph is such that it has 2 distinct communities (something we already know but that's what the algorithm should detect). After the first iteration, it would remove the edge which has the highest value of edge betweenness. Now my question is, after this is done (or even after a few iterations), say I have any vertex $v_i$, how do we know which community this vertex belong to? Am I missing something here?

This is hierarchical clustering method. As you remove edges, at some point the graph will become disconnected: the connected components are your top-level communities. As you keep removing edges, the top-level communities become disconnected too, and you can think of the new smaller connected components as sub-communities. So you can think of the algorithm as building a tree of finer and finer communities, where the leaves are individual vertices.


Choice of machine learning algorithms frequency of parts of speech I'm new to machine learning. I have text, and I tag the text according to their parts of speech tag ie walk is tagged as verb, etc. I tag entire sentences, and then convert them into a vector based on their frequency like so:

Dan, walk the dog - > noun,verb, definite-article, noun -><2,1,1> (2x nouns, 1 verb, 1x DA).

The sentences each belong to one of two classes. I've performed a Kolmogorov–Smirnov test on each tag and picked the ones with the lowest P-value to use. I've used a couple of the models provided by scikit but each time I'm only getting around 55-56% accuracy. The models I've tried are: Gaussian Naive Bayes, K-Nearest Neighbours, SVM, Decision Tree, Random Forest Classifier, Quadratic Discriminant Analysis...

I'm asking if anyone has any comments or pointers about these methods? Should I be using different machine learning methods? Am I going about this problem completely wrong? I would really appreciate any input.

You're trying to classify the sentences' sources, right? I would suggest grouping your training data by their sources (but only up to some fixed size, in which case you would have a duplicate entry for that source). E.g., if you are trying to classify the source of a tweet, you would make each tweet (not sentence, and that means each vector would represent a string of up to 140 characters) a vector and calculate its corresponding features, which should span the contents that the feature vector would relate to. Further if you could get each of the fixed bodies of text into  ARFF format, where the last value in the vector would represent the source of the fixed body of text and the feature vectors would each have the same number of features (the features of which you would pick, more on this in a bit) then you wouldn't be too far from being able to use the Weka suite of classifiers. As for which classifier you should use, I suggest skimming through the following paper:

Antti Puurula, Sung-Hyon Myaeng.  Integrated Instance- and Class-based Generative Modeling for Text Classification.  ADCS 2013.

It comes from the same machine learning group that produced the Weka suite of classifiers and should give you some pretty good insight.

For your choice of what features you would like to vectorize the fixed bodies into, it would be good to count classes of tags. For example, you could count the number of adverbs as a feature, and/or count the number of first-person/second-person/third-person pronouns as a feature, and/or count the number of verbs in a certain tense as a feature, etc. The features you choose are more so based on your understanding of the bodies. If your fixed bodies could include multiple sentences then some other features could also be the average length of sentences (with respect to number of tokens), the average length of tokens (omitting punctuation, for example, from this group), and/or even just the number of sentences in the fixed body.

Make sure to pick enough features, and make sure to pick features you think would be better at differentiating your classes of sources. For example, if any two of your sources are likely to differ in the formality of their tones, then a useful feature would be the number of slang tokens per fixed body.


Find unambiguous grammar for an ambiguous grammar Hi I want to find an unambiguous grammar for a known ambiguous one, and the production is like this:

S->bA|aB
A->a|aS|bAA
B->b|bS|aBB

I have found the string to prove this grammar is ambiguous: bbaaba. I wonder whether it is doable to convert the grammar into unambiguous. I have approached it from this perspective: in the above counter-example, the difference shows up when we have AA in the list, then whether we are changing the first A to contain S or the second will make the next step different. So I think maybe I can restrict A to go only via the first or the second A and hence eliminate the ambiguity, like this:

S->bA|aB
A->a|aS|baA|baSA
B->b|bS|abB|abSB

I'm not sure whether my approach or answer is correct or not. I understand there is no algo for this kind of conversion, but are there any kind of 'common steps' for getting the unambiguous grammar?

I'm not sure whether my approach or answer is correct or not.

It is not correct. Your modified grammar can produce at most three consecutive 'a's or 'b's, while the original grammar can produce an unbounded number of consecutive 'a's or 'b's.

Your approach starts fine by looking for counterexamples, but then runs into a trap by staying too close to the given grammar. This is a trap, because the problem asks for extensional equality of languages. After you isolated the critical part of the grammar which generates the problem, you should first try to understand the generated language (that interacts with that part), before starting to modify the grammar.

  I understand there is no algo for this kind of conversion, but are there any kind of 'common steps' for getting the unambiguous grammar?

Your first step to look for a counterexample and isolate the part of the grammar which generates the problem makes sense.
My next step would be trying to understand the generated language. Let me try your example:

From S, I can generate any number of 'a's, followed by the same number of 'b's, and end up in S again. Can I ever generate more 'a's than 'b's? No, the number of 'a' or 'A' on the left side is identical to the number of 'a' or 'A' minus 'b' or 'B' on the right side for all rules. Can I generate any string with the same number of 'a's and 'b's? Yes, because ...

Ah, so the generated language is simply the language where the number of 'a's equals the number of 'b's.

After you understood the generated language, you can try to determine whether it can be generated by an unambiguous grammar, and write down such a grammar if desired. Let me try for your example:

The generated language is so simple, I would have heard if this language were ambiguous. It should even be deterministic, I can just push 'a's on the stack when there are more 'a's than 'b's, and push 'b's on the stack when there are more 'b's than 'a's. Of course, when the symbol on top of the stack differs from the current symbol, then I will just pop it. I know it is possible to convert this sort of deterministic PDA into a deterministic grammar, so I'm done without even trying to write down any specific deterministic grammar.


Are accepting states and unaccepting states distinguishable? Is it true that for all DFA that if $A$ is an accepting state and $B$ is not, that $B$ is always distinguishable from $A$.

I don't think it's true, just because I think I can create a DFA.

$B$ reads b -> $A$

$A$ reads b -> $A$

If you start at $B$ while reading a b and at $A$ you read a b you end up in the accepting state $A$. Now is there an algorithm to see if my construction is valid?

This depends on your definition on distinguishable. Let's assume the following definition: $A,B$ are distinguishable if for some word $x$, if the automaton starts at $A$ and reads $x$ then it accepts, while if it starts at $B$ and reads $x$ then it rejects; or vice versa.

Under than definition, any accepting state is distinguishable from any non-accepting state: just take $x$ to be the empty string.


Finding often repeating substrings in multiple strings I'm currently looking for an algorithm to find often repeating substrings in one or multiple strings. However, my search until now was not really successful. I try to illustrate the problem on the following example strings:

S1: ABCCCDxxxxxxABCCCDxxxxABCCCD
S2: xxxxxABCCCDxxxxABCCCDxxxxxxx
...
S10: xxABCCCDxxxxxxxxABCCCDxxxxxx

In the given example strings S1, S2 up to S10, the substring ABCCCD occurs multiple times, making it an often repeating substring, and thus interesting for me. However, when trying to find an algorithm that helps with finding such substrings, I often end up at the longest common substring problem, which would help me find the longest common substring between S1 and S2, however, it would ignore the repetition of the substring.

Does an algorithm exist, that can help me with this problem? Additionally, it would be quite interesting to set additional constraints, such "substring must occur at least n times" or "substring must be at least n characters" long.

Let's say you are looking for substrings that occur at least $c$ times in each string and have length at least $k$. Furthermore, lets say we're looking for maximally repeated substrings i.e. if $R$ is our solution set of substrings, there exists no pair $r_i, r_j\in R$ such that $r_i$ is a substring of $r_j$.

Offline option

Construct a generalized suffix tree from all input strings. Any node at depth at least $k$ that has at least $c$ leaves from each input string (i.e. at least $c$ $\$_1$ leaves, at least $c$ $\$_2$ leaves and so on) is $blue$ and each $blue$ node with no $blue$ children is also $red$. The set of substrings represented by $red$ nodes is the set of maximally repeated substrings. This runs in time $O(mn)$ where you have $n$ input strings of length at most $m$.


Advantages (from a mathematical perspective) of representing data as symmetric matrices From Wikipedia, a symmetric matrix is a square matrix that is equal to its transpose. An example of this (I think) is an adjacency matrix with undirected edges, which is a square matrix representing links between elements (undirected in this case).

The thing is, the data is duplicated in this case (looking at it from a computer science perspective). The two halves of the diagonal carry the same information, so you can just use one half of it.

I am new to matrices, so I apologize if this is a basic question. The question is if there is any advantage mathematically or from a computer science perspective to representing data (such as graphs, but more generically any data such as key/value pairs or pointers, etc.) using symmetric matrices like this. Wondering if it (for example) makes lookup O(1) in certain cases, or it provides some other significant hidden benefit because of the symmetry.

The main advantages of matrices are in solving linear equations. In fact judging whether there even exists solutions to a system of equations becomes very easy when you represent equations in form of matrices. Matrices form the core of Linear Algebra.

Systems of linear equations pop up everywhere in the real world. Linear Algebra is integral to Machine Learning, Image processing, Computer Graphics, Operations Research.....( the list is inexhaustible).

Using matrices as representation of graphs is in fact one of the less useful facets of Linear Algebra (due to the more space efficient Adjacency List data structures). If we talk about using matrices as datastructures you can look into Bottom Up approach of solving dynamic programming problems.

Importance of Symmetric Matrices

If we have a symmetric matrix, then we immediately know a few things about the concerned system of linear equations:

If each vector is linearly independent, then we have as many pivots as we have rows or columns.
This is a special case where we say that the matrix has a full rank. Hence the matrix is invertible, and there exists a particular unique solution to this system of linear equations.
Eigen Values are defined for square matrices.
This allows us to investigate whether a given matrix is diagonalizable. If the matrix is diagonalizable, then it allows us to perform efficient computations of the powers of A, leading into matrix exponentials.
Diagonalization is a very common mathematical operation in quantum mechanics. The time-independent Schrödinger equation is broadly speaking, an eigenvalue equation.

Since matrices are nothing but representations of linear equations, we cannot force ourselves to represent data symmetrically (actually we can, and often do). If a particular dataset that we are investigating has the same number of vectors as its attributes (which is definitely coincidental) then we can perform an extended analysis on the dataset owing to the properties of the square matrix.


How to interpret $BPP^{NP}$ I have taken one basic class in complexity and understand the fundamentals. E.g. P, NP, NP-hardness. But I can't understand how to interpret $BPP^{NP}$.  I believe it means "BPP with an NP oracle" but how should I interpret that?

Does this mean that members of this class are problems for which there exist randomized algorithms that run in polynomial time but which can call another algorithm that can solve any problem in NP in constant time?  If so, how is this different from just having an algorithm that can solve any problem in NP in constant time?

You should think of this as the class of problems who lie in $BPP$, but in a new (relativised) world where the model of computation is slightly different. Turing machines now have an additional query tape and three new special states, $q_{\text{query}},q_{\text{yes}},q_{\text{no}}$. Upon entering the state $q_\text{query}$, if the contents of the query tape is $s\in\Sigma^*$, then the machine goes to either the yes or no state depending on whether or not $s\in SAT$.

The key point is that nothing changes in the BPP part, the only thing different is the computational model. This actually changes everything, but luckily we can integrate the oracle to the standatd Turing machine without changing basic notions such as time/space complexity. This allows us to talk about classes such as $P, NP, BPP$ in the new model (we can define them in exactly the same way).

Note that we don't have a general definition of $A^B$ for two complexity classes $A, B$. We use this notation when $A$ has a natrual extension to the relativised (oracle) world.

Additionally, to define our model of computation precisely we need to specify exactly what is the oracle (we need to define the transition function from $q_{\text{query}})$. Thus, we can't have an algorithm solve every NP problem in a single step, we need to choose a problem in order to specify a well defined behavior for the machine. It is not hard to show that for every two NP complete languages $L,L'$ it holds that $\mathsf{BPP^L=BPP^{L'}}$. So when we write $BPP^{NP}$ we mean languages having a BPP machine with access to a SAT oracle (or any other NP complete language of your choosing). In cases where the definition of $A^B$ might depend on the exact choosing of the oracle, statements involving $A^B$ usually hide a universal quantifier on the oracle, and should be read as "for all $o\in B$ ...".


Why merge into the larger tree in union by rank When we do union by rank we merge the smaller tree into the larger tree. I dont understand why we do this exactly?

Imagine merging the larger tree into the smaller one. By doing this, you are guarantying that the new tree will have depth one more than the larger tree's depth. But, if you were to merge the smaller tree into the larger one - the increase in depth would occur only in the branches of the small tree, and since it is small it wont impact the depth (unless the smaller tree is the same size as the larger tree).
So to summarize - by doing this you ensure to create the lowest possible depth you can.

Try to run on some examples both cases (merging largest to smallest and merging smallest to largest) and see the differences for yourself


Find number of nodes that seperate graph to two or more subgrahps when removed individually - Find articulation points on a non-directed graph Suppose that we have an undirected graph, and that for any two nodes there is a path from one to another. In such a graph, there might be some nodes that, if removed from the graph individually, leave behind the starting graph as two or more subgraphs - that is, removing one of the said nodes no longer makes possible to find a path between any two nodes.

What I want is a good algorithm to find how many these nodes are - nodes that if removed individually tear the graph connectivity apart.

What I have thought so far involves removing a node at the time and trying to reach all nodes from a starting node - failing to reach every node would mean the node removed is of the kind I am looking for. Some optimizations may apply, but that's the main idea.

Can you propose any better algorithm for this, e.g. taking advantage of say the degree of the nodes?

EDIT: After having found the answer, my question is equal to asking to find the number of articulation points in an undirected graph, so the title has changed accordingly.

After some searching, I came across exactly what I wanted - seems like knowledge of terms is important. Source from Wikipedia - Biconnected components.

  Linear time depth first search

  The classic sequential algorithm for computing biconnected components in a connected undirected graph is due to John Hopcroft and Robert Tarjan (1973).[1] It runs in linear time, and is based on depth-first search. This algorithm is also outlined as Problem 22-2 of Introduction to Algorithms (both 2nd and 3rd editions).

  The idea is to run a depth-first search while maintaining the following information:

  the depth of each vertex in the depth-first-search tree (once it gets visited), and
      for each vertex v, the lowest depth of neighbors of all descendants of v in the depth-first-search tree, called the lowpoint.

  The depth is standard to maintain during a depth-first search. The lowpoint of v can be computed after visiting all descendants of v (i.e., just before v gets popped off the depth-first-search stack) as the minimum of the depth of v, the depth of all neighbors of v (other than the parent of v in the depth-first-search tree) and the lowpoint of all children of v in the depth-first-search tree.

  The key fact is that a nonroot vertex v is a cut vertex (or articulation point) separating two biconnected components if and only if there is a child y of v such that lowpoint(y) ≥ depth(v). This property can be tested once the depth-first search returned from every child of v (i.e., just before v gets popped off the depth-first-search stack), and if true, v separates the graph into different biconnected components. This can be represented by computing one biconnected component out of every such y (a component which contains y will contain the subtree of y, plus v), and then erasing the subtree of y from the tree.

  The root vertex must be handled separately: it is a cut vertex if and only if it has at least two INDEPENDENT (non-connectible) children. However, since we hold the child count of each visited node, and the count only increments if the adjacent node being checked is not already visited, the root having >=2 children count would surely mean that at least two of the root's children are independent. If there were no 2 independent children of the root, all of the children of the root apart from the first checked would be marked as visited BEFORE the DFS search returned to root and continued the search to the second child, therefore the root's children count would be stuck at 1.

The code below prints the said articulation points, but with minimal changes it can also just print out the count of the said points.

Pseudocode

GetArticulationPoints(i, d)
      visited[i] = true
      depth[i] = d
      low[i] = d
      childCount = 0
      isArticulation = false
      for each ni in adj[i]
          if not visited[ni]
              parent[ni] = i
              GetArticulationPoints(ni, d + 1)
              childCount = childCount + 1
              if low[ni] >= depth[i]
                  isArticulation = true
              low[i] = Min(low[i], low[ni])
          else if ni <> parent[i]
              low[i] = Min(low[i], depth[ni])
      if (parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1)
          Output i as articulation point


Linear Programming Problem - what is feasible size for solution on a PC I need to get feeling for the feasible size of a LPP, that can be solved on a PC.
Say, its a good one (8 cores @ 3+GHz,  64GB RAM).
We also assume that number of variables is close to the number of additional conditions.
I know it depends on the solver, but what size is feasible for solution in several hours/few days?
1000 of variables? A million?
Order of magnitude would be enough.
Update. Let's consider a general form:
matrix is not sparce/diagonal/blotchy or whatever.
Let's say matrix's rows are filled with many hundreds of values (@ thousands of variables).

I would assume a few times n^3 operations for n variables. How many operations per second can you perform? Using vector operations is not too difficult. Using 8 cores for one problem is hard. Depending on your programming effort you will be able to do between 1 and 100 billion operations per second, or 100 to 10,000 trillion operations per day, or very roughly n = 20,000 to 100,000. Buy a lot of RAM as well.


State machine with knowledge of prior states? I'm attepting to model a process flow where the transition to the next state is occasionally based on not only the input to the current state, but a prior state as well.

Below is an example graph descibring the process. The essence is: If both State Q1 and State Q3 recieve an input of one, after State 3, transition to State Q4, otherwise transition to State Q5.

I understand that it would be possible to model this using a finite-state machine where we duplicate any states between those that we are interested in. The example below demonstrates this with States Q2a and Q2b corresponding to the differences in input at state Q1

However, as the number of conditions and the gaps between them grows (both of which are possible in the process I'm looking at), the number of states grows exponentially.

The question is, what other computational models could be used to describe a process where an arbitrary number of inputs could be used to control transition between states?

In digital design we would call the thing you are looking for an algorithmic state machine.  In compiler design we would call it a control flow graph.  The idea in either case is that you divide the state problem into two parts, one part represents the control state, the other part represents the data path.  You label the states with how you want the data path to be modified, and the data path has some boolean outputs that you use to determine which way the control state should change.

Formally, you are describing a Moore machine where each state describes a set of control signals that will be sent to tell the data path how to modify itself, and the data-path in turn has a small set of boolean outputs that are used as the input language to the control state machine.

Your original problem would then have a control state, Q, and two variables, v1 and v2 and the graph would look something like:

       q1: v1 <- some_function(...)
                |
                v
       q2: something else happens
                |
                v
    q3: v3 <- some_other_function(...)
        test (v1==1 && v3==1)?
       /                 \
       | true             | false
       v                  v
q4: something    q5: something else
       \                  /
        \                /
         v              v
           q6: whatever


Time complexity of Dynamic Array via repeated doubling When we implement dynamic array via repeated doubling (if the current array is full) we simply create a new array that is double the current array size and copy the previous elements and then add the new one? Correct?

So to compute the complexity we have 1 + 2 + 4 + 8 + .... number of steps? Correct?

But

 1 + 2^1 + 2^2 + .... + 2^n  =  (2^(n-1) - 1)  ~  O(2^n).

However it is given that

 1 + 2 + 4 + ... + n/4 + n/2 + n  ~  O(n).

Which one is correct? And why? Thanks

Both are correct but you're using $n$ to mean two different things:

when you say that $1 + 2^1 + 2^2 + \dots + 2^n  =  (2^{(n-1)} - 1)  \sim  O(2^n)$, you're using $n$ to mean the number of times you had to increase the size of the array;
when you say that $1 + 2 + 4 + \dots + n/4 + n/2 + n  \sim  O(n)$, you're using $n$ to mean the total size of the array after you've extended it some number of times.

So, you should never just say "$n$", without saying what it means. Normally, $n$ refers to the size of the input to a problem. In this case, that would probably be the number of things you want to insert into the array. This is closest in meaning to the second case above since, when you've inserted $n$ elements, the total size of the array will be somewhere between $n$ and $2(n-1)$ (i.e., it will be $O(n)$).