Parsing a string with LR parsing table Me and my friends are studying for an upcoming test and this exercise is one of the harder ones for us.

We have been trying to solve it and we have been looking at similar exercises, the problem is that the explanations are too complicated for us to understand. Keep in mind we just started with this.

So, my question is: Can anyone explain this as simple as possible, I have included the exercise.

The mechanics of shift-reduce parsing is pretty simple -- the hard part is understanding why it works or how to construct the tables.  But since you already have the table, that is not relevent.

To do shift/reduce parsing, you need an action table and a goto table (which you have) and a stack of states.  You start with just state 0 on the stack.  At each step you look up in the action table with the top state on the stack and the next token of input and perform the corrsponding action.

for a SHIFT action you consume the token of input and push the state on the stack
for a REDUCE action, you find the SIZE of the right-hand-side of the rule to be reduced (number of symbols -- ε is zero size) and the SYMBOL on the left-hand-size.  You pop SIZE states from the stack and then use the state now on top of the stack and the SYMBOL to lookup in the GOTO table and push the corresponding state.

That's it.  You repeat the above until you either reach an ACCEPT action (the string matches) or a REJECT action (any blank in the action table -- the string is not matched).  The reduce action is a bit complicated as it chains immediately to a goto action, so you can think of the reduce+goto as a single action or as two distinct actions as you prefer.

If you want your parser to construct the parse tree while you're at it, its a bit more complicated.  You need to have your stack hold state × subtree pairs -- when you shift a token you include that token (as a single node subtree) along with the state, and when you reduce, you create a new subtree from the subtrees popped (as children to the LHS symbol) which you push along with the GOTO state.  When you get to the ACCEPT state you do a 'reduce 1' action to build the complete parse tree.


Projecting points on a Pareto-front onto a (hyper)plane? I'm trying to implement the Biased Crowding Distance in NSGA-II as described in the paper Integrating User Preferences into Evolutionary Multi-Objective Optimization by Branke and Deb.

Basically, from what I understand, given a set of points on a Pareto-front, we need to project the points onto a hyperplane with a direction vector $\eta$. Doing this will give the new crowding distance $d'$ based on the locations of the individualson the hyperplane with direction $\eta$.

To illustrate, see the figure below.

My question is simple: how do we obtain the hyperplane given a user-specified direction vector $\nu$? Is it simply by getting the perpendicular of the direction vector?

And a follow up question would be: how would I project the points onto the hyperplane? If $p$ is the point and $v$ is the vector representing the hyperplane, is it correct that the new location of $p$, call it $p'$ is $\frac{v.x(p.x) + v.y(p.y)}{||v||^2} (v.x, v.y)$ based on this?

Thanks and any information would be very helpful.

I'm not sure if this should be considered a computer science question or not, it seems more an algebra question than anything else.

A vector is a direction vector of a hyperplane if it is parallel to that hyperplane (source).

For any vector $\vec{v} = (v_1, . . . , v_n)^T$ you can find a plane parallel to it by taking the dot product of $v$ and your variable vector $\vec{x} = (x_1, . . . , x_n)^T$ and setting the result equal to some constant $c$.

Consider $\eta$ as described in the paper, then the hyperplane he is referring to will be $$\eta_1 f_1 + . . . + \eta_n f_n = c $$ for a constant $c$. Because you are only interested in the distance between the points after projection, and not the location of the projected points, you can select $c = 0$, as shifting around the hyperplane won't affect the distances between the projected points.

Since the origin is contained in this hyperplane, the hyperplane is a subspace, call it $H$. We can then represent each $p_i$ as a vector $\vec{p_i}$ and project the vector onto the subspace.

To project a vector onto $H$ we need to find a basis for $H$. This can be done by making $n - 1$ similar vectors to $\eta$, where the difference is a single value is set to $0$ (distinct from previous selections). E.g., the plane $3x_1 + 4x_2 + 5x_3 = 0$ has a basis of $$\Bigg\{\begin{bmatrix}3 \\ 4 \\ 0\end{bmatrix}, \begin{bmatrix}3 \\ 0 \\ 5\end{bmatrix}\Bigg\},\Bigg\{\begin{bmatrix}3 \\ 4 \\ 0\end{bmatrix}, \begin{bmatrix}0 \\ 4 \\ 5\end{bmatrix}\Bigg\}, \text{ or } \Bigg\{\begin{bmatrix}0 \\ 4 \\ 5\end{bmatrix}, \begin{bmatrix}3 \\ 0 \\ 5\end{bmatrix}\Bigg\}$$

Once you have a basis of $H$ you can use this guide guide to perform the projection. Note, since you have to do this multiple times, coming up with $Q$ as described in the guide and saving it will allow you to perform the process on many points.


Big O Asymptotic complexity I am trying to rank $\log n $, $\log_{10} n $, $n \log n $, $n \log n^2 $, $n^{0.8}$, $\sqrt{n}$ in increasing asymptotic complexity. $\log n $ has base 2 unless specified otherwise.

The answer I have is $\log_{10} n $, $\log n $, $\sqrt{n}$, $n^{0.8}$, $n \log n$, $n \log n^2$,

Is this right? And possibly explain the reason behind it? thank you!

The answer is correct. Let's verify it

$\log_{10}n $ and $\log{n}$ belong to the complexity class $O(\log{n})$, because they differ by a constant factor, hence $\log_{10}n \asymp \log{n}$.

$n^{0.8} \succ \sqrt{n}$, because $0.8 > \frac{1}{2}$. The last pair $n\log{n}$ and $n\log{n}^2$ belong to the complexity class $O(n\log{n})$ because they also differ by a constant factor ($n\log{n^2} = 2n\log{n}$), hence  $n\log{n} \asymp n\log{n^2}$. Finally we'll show that $\sqrt{n} \succ \log{n}$ and $n\log{n} \succ n^{0.8}$. The last one is obvious and I'll leave to you to prove that $\sqrt{n} \succ \log{n}$ (I claim that is true, if you face problems with it I'll expand the answer with proof).


Heuristic algorithms for the dense assignment problem Given a dense assignment problem ($n$ tasks assigned to $n$ workers, where each worker can do any one of the tasks), I understand the best complexity is $O(n^3)$, using the Hungarian Algorithm or variants.

However, if $n$ is large, $O(n^3)$ may not be feasible from a timing perspective. Moreover, storing the complete $n^2$ cost matrix may require a prohibitive amount of memory.

Are there heuristic algorithms that give "good enough" solutions, with are significantly faster? I have seen some algorithms that claim to be faster, but they assume the number of edges is smaller than $O(n^2)$, which is not true in the dense case.

This paper has a painfully detailed table on what you can achieve using (currently known) deterministic, randomized and $\epsilon$-approximation algorithms. To summarize, for the bipartite case (all assuming integer weights bounded by $N$):

Deterministic time $O(n^2 \sqrt n \log N)$.
Randomized $O(n^{2.373} N)$.
$(1 - \epsilon)$-approximation in $O(n^2 \epsilon^{-1} \log N)$.

These algorithms are mostly very complex and go through $LP$ formulations. It is unlikely that any of them are truly what you're looking for. Also, regarding their use of space, I am not sure, but you can follow the papers for the different algorithms and see for yourself, if you can make them work in less space. (By the way, isn't your cost function already using quadratic space?)

If you want a heuristic with no provable guarantees, then I recommend the simple local search. You basically start with some random permutation (this is a feasible assignment, since your bipartite graph is complete) and make random swaps that improve the cost. If you do many such searches, you get a good solution more often then not. You can make the whole thing run in $O(t (n + s))$ time and linear space, if you do $t$ searches (from random permutations), each for $s$ steps. Choose $t, s$ to trade-off quality of the solution with complexity.


Why guess $\Theta(n^2)$ for the substitution method of worst-case partitioning In the book

  Introduction to Algorithms (3th edition) chapter 7

the recurrence of the running time of quicksorts partitioning is given by $$T(n) = T(n-1) + \Theta(n)$$
as the worst-case happens when the partitioning has one subproblem with $n-1$ elements and one with $0$ elements.

Now, they they guess $T(n)=\Theta(n^2)$ for the substitution method. I don't  understand this, why choose $\Theta(n^2)$? I personally would have chosen $\Theta(n)$, which is wrong.

With the help from a fellow friend I came to the following conclusion:

We know that we have to make $$n-1,n-2, \dots, 2,1 \text{ comparisons}$$

So when looking at the arithmetic series $$\sum_{i=1}^n k = \Theta(n^2)$$

We can conclude that $T(n) = \Theta(n^2)$.

Please comment if I can improve my answer in any way.


Efficient algorithm for this optimization problem? Dynamic programming? I've created a diagram that depicts what I'm trying to accomplish.

Full-size Image

In the input sequence, the nodes are as close together as possible. But I want the white nodes to be as close to their respective black nodes as possible. The edges between nodes can be lengthened to try to minimize this error. They cannot be shortened. So, 1 -> 2 can be no less than 4, for example.

I've included a possible solution. The edges that have been lengthened are labeled. Note that lengthening an edge shifts all the nodes to its right.

This axis is continuous, but I could possibly discretize it if that helps.

I'm thinking a dynamic programming approach could work here but I'm not sure - I was never very good with DP.

What's the fastest running algorithm that can solve this? Can this be categorized / re-framed as a well-known problem?

This is just an extension to @Sébastien Loisel's answer.

Notice minimize $(x_i-y_i)^2$ subject to $x_i-x_{i-1}\ge c_i$ is equivalent to minimize $(x_i-(y_i-c_i))^2$ subject to $x_i\geq x_{i-1}$. Let $a_i=y_i-c_i$, then this is precisely the isotonic regression problem. There exist a $O(n)$ time algorithm.


Numbering of unlabelled trees For labelled trees there are the Pruefer numbers that uniquely identify them. Is there a similar numbering system for unlabelled trees?

According to Wikipedia, a closed-form formula for the number of unlabelled trees is not known, so a numbering in the form of a bijection between the set of unlabelled trees on $n$ vertices and $\{1,\ldots,T_n\}$ (for an appropriate $T_n$) is probably hopeless. Tree isomorphism is in P, so if you want an "effectively unique" identifier for trees, you can get it by using the Prüfer numbering and applying the algorithm to test equality. It is also possible that you can canonicalize trees (using the same ideas as in the algorithm), thereby creating a coding scheme in which two isomorphic trees get the same (Prüfer) number.


Why there aren't any famous programming languages that implement what Alan Kay considers to be "real OOP"? Why there aren't any famous programming languages that implement what Alan Kay considers to be "real OOP"?

Is it because the "modern OOP" that exists in programming languages like C++ and C# and Java are "better" than "real OOP", or are there other reasons?

"OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things. It can be done in Smalltalk and in LISP. There are possibly other systems in which this is possible, but I'm not aware of them." - Alan Kay.
I would like to point that there is no single evidence of term OOP being coined by Alan Kay (if you find one, please share).

About C++ Alan gave statement: "I invented the term object-oriented, and I can tell you that C++ wasn't what I had in mind".

Other languages that may fall into "real OOP" is self programming language and probably Squeak and Objective-C.

When languages switched from messages to params passing, becoming bidirectional, it broke initial assumptions. Alan have pointed flaws in Simula design, so this one also do not count.

It is impossible to say that some languages are "better" than others, but being "real OOP" according to definition is some road taken by one influential author. Term OOP and class based programming was introduced in Simula, long before "real OOP" was supposedly coined.

All modern languages took other road and "modern OOP" is more down-to-earth, no asynchronous agents passing messages, microservices with own memory, everything being object by default.

Since there are performance hits in every step and there is no single reference gathering what it should do beside notes like actor-based programming is a way to go, because programmers should consider interactions of objects and interactions with users, we can safely assume "real OOP" by Alan Kay is only about road taken by him and not really implementable by others, so only smalltalk and squeak may be truly covered and other languages followed more pragmatic, expressive and performant way.


Is there such a notion as "effectively computable reductions" or would this be not useful Most reductions for NP-hardness proofs I encountered are effective in the sense that  given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by using reductions. All reductions in the 21 classic problems considered by R. Karp work this way. A very simple example might be reduction from INDEPENDENT_SET to CLIQUE, just built the complement graph of your input.

But when considering the proof of the famous Cook-Levin Theorem that SAT is NP-complete, the reduction starts from a non-deterministic TM and some polynomial, that exists by definition. But to me it is not clear how to get this polynomial effectively, meaning given an non-deterministic TM from which I know it runs in polynomial time, it is not clear how to compute this polynomial, and I highly suspect it is not computable at all.

So soley from the encoding of NP-complete problems by the class of non-deterministic polynomial time TMs (the polynomial itself is not encoded as far as I know) I see no way how to give a reduction in an effective way, the aforementioned proof just shows that there exists some, but not how to get it.

Maybe I have understood something wrong, but I have the impression that usually the reductions given are stronger in the sense that they are indeed computable, i.e. given a problem we can compute our reduction, and not merely know its existence.

Has this ever been noted? And if so, is there such a notion as "effectively computable reduction", or would it be impractical to restrict reductions to be itself computable? For me, from a more practical perspective, and also the way I sometimes see reductions introduced ("like we have an algorithm to convert one instance to another") it would be highly desirable to know how to get this algorithm/reduction, so actually  it seems more natural to demand it, but why is it not done?

Nice question! I think that your notion of an "effectively computable reduction" is interesting and worth studying, but not as fundamental as standard reductions. Let me provide some observations about this notion that may be illuminating:

Observation 1: it does not make sense to talk about effectively computable reductions from one language to another; only from a family of languages to another.

In particular, you seem to be mixed up when you write this:

  Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by using reductions. All reductions in the 21 classic problems considered by R. Karp work this way.

A reduction from, say, VertexCover to 3SAT is a Turing machine $f$ that transforms instances of VertexCover into instances of 3SAT. Since it is a Turing machine, it is effectively computable by definition. So it is not surprising that all reductions you have seen of this form are effectively computable.

In other words, if we just look at reductions from one language to another, then every reduction is effectively computable!

This is different from the case of the Cook-Levin theorem, where we have to show a reduction $f$ from an arbitrary NP language to SAT. Then it might make sense to consider whether this reduction -- parameterized by the language in NP -- is effective or not. But that brings us to my second point:

Observation 2: What counts as an effectively computable reduction depends on the representation of languages.

This is important because standard reductions (either many-to-one reductions or Turing reductions) do not depend on the way the language is represented. For a reduction from $L$ to $L'$, I consider $L$ and $L'$ to be subsets of $\{0, 1\}^*$. But for your notion of effectively computable to make sense, we need to have access to a representation of $L$ (we probably don't need a representation of $L'$).

To make this point clearer, consider the reduction in the proof of the Cook-Levin theorem, which you brought up. The proof considers a language $L$, represented by a polynomial-time nondeterministic Turing machine $N$. Then it shows that $L$ is reducible to SAT. You say that this reduction is not effectively computable, but that depends on how $N$ is represented, i.e., the definition of a polynomial-time nondeterminstic Turing machine $N$:

Definition 1: A polynomial-time NTM is a nondeterministic Turing machine such that there exists a polynomial $p(n)$, such that the TM always halts in time at most $p(n)$.
Definition 2: A polynomial-time NTM consists of a nondeterministic Turing machine, together with a polynomial $p(n)$. The way it runs is that, on any branch, it is only executed for $p(n)$ steps; if it does not halt in this time, then that branch is ignored.

It may seem that I am making Definition 2 up and that the definition is not natural, but actually both of these are perfectly valid definitions of a polynomial-time NTM that both have their merits. And for the classical theory of P, NP, and NP-completeness, both of these definitions are equivalent. The nice thing about Definition 2 is that an NTM is allowed to diverge on certain branches; you don't worry about that because the execution semantics says that we just forget about it once the running time goes above $p(n)$.

However, the definitions become inequivalent when it comes to effectively computable reductions. Note that, according to Definition 1, when we are given a language defined by an NTM $N$, we have no idea what its running time is, so we may not be able to reduce it to SAT (more on this below). But according to Definition 2, part of the NTM $N$ is that it comes with a polynomial, and so we know its running time. Therefore, we can effectively reduce all NP languages to SAT if we are using Definition 2.

Also, we have only considered nondeterministic Turing machines; we could equivalently define NP using verifier Turing machines. Then the definition of an effectively computable reduction could be something else!

TL;DR: Depending on how a language in NP is represented, and in particular depending on the definition of a polynomial-time NTM, it may be either true or false that every language in NP is effectively reducible to SAT. In other words, The set of effectively computable reductions changes depending on the model of computation used to represent languages in NP.

Now at this point, given points (1) and (2), a question still remains: can the reduction in the Cook-Levin theorem be made to be effective? In particular, suppose we fix the following definitions:

Languages in NP are represented by nondeterministic Turing machines whose runtime is bounded by an unknown polynomial $p$ (i.e. Definition 1).
Given a language $L$, we say that the class of languages NP is effectively poly-time reducible to $L$ if the following holds: there is a TM $f$ that takes as input $\langle N, w \rangle$, where $N$ is a polynomial-time NTM and $w$ is any input to $N$, such that $w \in L(N)$ if and only if $f(\langle N, w \rangle) \in L$. Also, $f$ must run in polynomial time (in its input $\langle N, w \rangle$).

In other words, to address point (1), we are assuming that languages in NP are represented by nondeterministic Turing machines without an explicit polynomial bound. And to address point (2), in our definition of effectively reducible, we are talking about a reduction from a class of languages, in this case NP, to a single language.
Now we have the following observation:

Observation 3: (Cook-Levin is not effective) The class NP is NOT effectively reducible to SAT.

Let us see why this is true. Assume towards a contradiction that an effective reduction $f$ exists. The idea is that we will try to solve a difficult (say, doubly-exponential-time) problem by taking its instance, turning it into a polynomial-time NTM, and asking $f$ to reduce it to SAT. So, let $L_{hard}$ be some problem that requires doubly-exponential time to solve (this exists by the Time Hierarchy theorem), and let $M_{hard}$ be a (deterministic) TM that solves it. Given any instance $w$ of the problem, define the following NTM $N_w$:
\begin{align*}
N_w :=
&\text{"On any input $a$, first run } M_{hard} \\
&\text{on input } w \text{. When it halts, accept if} \\
&\text{it accepts and reject if it rejects."}
\end{align*}

Now we can use this to solve $L_{hard}$ in exponential time (not double exponential), as follows. On input $w$, we first construct $N_w$, which has size only a constant more than $w$. Then we pass $\langle N_w, \epsilon \rangle$ (the second argument, $\epsilon$, is just a placeholder here) to $f$ to reduce it to SAT. $f$ gives us back an instance of SAT that is at most polynomial size in $N_w$, and $f$ takes only polynomial time to run. So we end up with an instance of SAT of polynomial size in $w$; now we solve it in exponential time in $w$ using brute-force search.

This point (3) seems to suggest that most of the time, no interesting class of languages will be reducible in this effectively computable sense to a single language. It will just be too hard, because you can exploit this computability to then solve hard problems by encoding them as part of a TM input to the effective reduction. However, something is a bit fishy here, because if we feed the TMs $N_w$ into the Cook-Levin theorem reduction, we would end up with very large SAT formulas, exponential in $w$. So perhaps our definition needs to be tweaked so that $f$ runs in time polynomial in the running time of $N_w$, not just polynomial in the input $\langle N_w, \epsilon \rangle$.

Observation 4: If we allow Turing (many to many) reductions, then Cook-Levin can be made effective.

As D.W. says in a comment:

  I think one can construct an effective Cook reduction, by iterative doubling. Does that help?

I also believe this is true. In particular, we can change our definition of an "effective reduction" from NP to a language $L$ by saying that the reduction does not just return an instance of $L$, but returns many instances of $L$ in sequence, and uses an oracle for $L$ to solve the original problem. Then to solve a general problem in NP, you could try larger and larger polynomials $p$ until you get the right one which bounds the running time. You can detect whether a particular polynomial bounds the running time on all branches of the NTM by a separate reduction to SAT.

Disclaimer

I am not an expert in this topic. These are just some preliminary notes on the idea, and I am not sure if someone has studied this in the literature.

P.S. Although it may not be directly related, your question about considering effective reductions reminds me of an idea I had, about considering not just whether languages are in P or in NP, but whether they are provably so. This is related to the idea of developing a complexity theory that is effective or constructive. I asked and later answered question about defining provably P and provably NP languages here.


Recognize end of Input in a Turing Machine If I have a turing machime TM, can I recognize end of input on the tape?
I know that the "end of input" in a turing machine is signaled with a special character, $\sqcup$.
Can I do this -

Let $TM$ be a turing machine.
Until we reach the first $\sqcup$, continue. If we reached $\sqcup$, replace it with a special character - #.

Is it "legal" to that this?

There are many possible input conventions for Turing machines. The one I know has the tape initialized by the input word (in case of a single input) surrounded by blanks, where a blank is a symbol of the tape alphabet that isn't in the input alphabet. The Turing machine treats all tape symbols in the same way, so you can do with them whatever you want.

Other conventions are also possible. For example, we might want to forbid writing blank for some reason. Only you know which convention is used in your class. The various input conventions are mostly equivalent, so in practice it usually doesn't matter which one is used.


Lower Bounds for the Set Disjointness Problem Consider the set disjointness problem. Alice and Bob hold n-bit strings $a$ and $b$ respectively.
They would like to compute the function
$$
\text{Dis}(a,b) =
     \begin{cases}
       0 &\text{if } \exists i : a_i = b_i = 1 \\
       1 & \text{Otherwise}\\
     \end{cases}
$$

It is well known that this problem has communication complexity exactly $\Theta(n)$ (see here for example).
This means that it cannot be solved with communication overhead sublinear in $n$.

Many times this result is informally stated as "Computing disjointness has communication overhead linear in the size of the inputs"

Question:
How do I go from the formal definition and result for set disjointness to the informal statement above.
My issue is the following:
Assume Alice and Bob hold sets of 64-bit integers.
In this case writing them as characteristic bit vectors would require them to send around 2^64 bits.
However, clearly I can trivially solve the problem by sending my total set, which would have a communication overhead of $\text{set-size} \cdot 64$.
How is this communication overhead related to the bit-strings of the set disjointness problem?

That's simply a different problem.  The set disjointness problem is defined, by common agreement, to be the problem where the universe has size $n$ and the inputs (sets) are represented as a bitvector of length $n$.  In other words, when you hear the phrase "set disjointness problem", you can know that's what they're referring to, and not the problem you care about.

It's fair to ask about the communication complexity of your problem.  I don't know what its communication complexity is.  There is no reason to assume your problem will necessarily have the same complexity as the set disjointness problem.

(There's a natural randomized protocol for your problem: if Alice and Bob each have a set of $n$ 64-bit integers randomly pick a universal hash function $f$ from the space of 64-bit integers to the set $\{1,2,\dots,2n\}$, transmit a description of $f$, hash the elements, and check disjointness of the hashed elements.  If there is a common element among the hashes, use binary search to find all common elements and check if the unhashed elements match as well.  The expected communication cost is $\Theta(n)$.  It's also clear that any algorithm must have communication complexity $\Omega(n)$.  This still leaves open what is the communication complexity for deterministic protocols, or the worst-case communication complexity for randomized protocols.)


All words containing at least twice as many zeroes as ones Consider the language
$$
\{ w \in \{0,1\}^* : \#_0(w) \ge \#_1(w) \}
$$
consisting of all words over $\{0,1\}$ in which the number of zeroes is at least twice the number of ones.
Is this regular, context-free, Turing decidable?
My Idea
It's not regular, because we need to track the number of zeros and so it cannot be done with
a finite number of states.
I am not sure if this argument is a formal one.
Turing Decidable - Yes
Take a machine which reads 1 from the end, writes an X there and then traverses the tape and X's two 0's.
If after all ones are gone the tape is empty of there are still zeroes left then it's accepted. Otherwise, if there are ones left
on tape after this operation, it's rejected.
Context-Free
I am unable to find any context free grammar for it. Neither can I prove that it's not context-free.

The language is context-free. As you read the string, you'll need a counter comparing two values: $\#_0 \cdot 2$ and $\#_1$. Such counter can be implemented using the stack of the PDA.
When a $0$ is read:

if there is a $1$ on top of the stack, pop it. If the stack is now empty, add a $0$, otherwise pop again.
else add $0$ to the stack twice

When a $1$ is read:

if there's a $0$ on top of the stack, pop it.
else add $1$ to the stack

It is easy to see* that the stack contains now the difference between $\#_0 \cdot 2$ and $\#_1$, encoded as the number of symbols on stack and the symbol used. After the entire string has been scanned, the top symbol of the stack tells which of the numbers is greater: if the top symbol is $0$ or the empty stack symbol, accept. Otherwise reject.
*If you need a more formal proof of this construction's correctness, it is fairly easy proven by induction: first establish that the symbols of the stack represent the correct counts after reading the first symbol, then perform an induction step with the assumption that the first $n$ symbols resulted a correct count on the stack and showing that the $n+1$th symbol read doesn't violate this correctness.


Using amplification lemma to decrease error probability gives 0 as divisor I am attempting to work through an example of how to select an error bound, and then determine the number of simulations necessary by the amplification lemma to obtain the desired error bound. I have probabilistic Turing machine $M$ with an error probability of $.5$. I'd like an error bound of $.25$, so I will bound the error probability by $2^{-t}$, where $t=2$. According to my textbook, I need to choose a $k$ such that $k \ge t/f$, where $f=-log_2(4e(1-e))$, where $e$ is the error probability. As $M$ has an error probability of $.5$, $e=.5$. Substituting into the equation gives: $-log_2 (2(.5))=-log_2(1)=0$. The problem is when I go to select a $k$ such that $k \ge t/f$, I get $0$ as a divisor. Are there other restrictions on the calculation? Or, am I just doing something wrong?

If the Turing machine has an error probability of $1/2$, the Turing machine is useless and you cannot amplify to reduce the error bound.

Consider: if you just ignore the input and flip a coin and use that to decide whether to accept or reject, you get an error probability of $1/2$ -- yet that is an obviously useless procedure.  A Turing machine with an error probability of $1/2$ is no better than that.

Here's another way to see why it's hopeless.  One standard method of amplification is to run the Turing machine multiple times and take a majority vote.  Suppose we run the Turing machine 3 times, and take a majority vote.  What is the probability that the outcome of the majority vote is correct?  It's not hard to see that this probability is $1/2$ -- no better than running the machine once.  (Why?  Each time you run the Turing machine, it is either correct or incorrect.  Since you run it 8 times, there are 8 cases: CCC, CCI, CIC, CII, ICC, ICI, IIC, III, where C = correct and I = incorrect.  If the Turing machine's error probability is $1/2$, all 8 of those cases are equally likely.  The majority vote after 3 runs will be correct in the cases CCC, CCI, CIC, and ICC; thus, the majority vote is correct with probability $4/8 = 1/2$.)  The same thing happens no matter how many times you run the Turing machine.

To get amplification, you need the error probability to be strictly less than $1/2$.


Given a list of strings, find every pair $(x,y)$ where $x$ is a substring of $y$. Possible to do better than $O(n^2)$? Consider the following algorithmic problem: Given a list of strings $L = [s_1, s_2, \dots, s_n]$, we want to know  all pairs $(x,y)$ where $x$ is a substring of $y$. We can assume all strings are of length at maximum $m$, where $m << n$ and are all over a finite alphabet $\Sigma$ with $|\Sigma| << n$. We may also assume that the number of pairs $(x,y)$ where $x$ is a sub-string of $y$ is much smaller than $n$.

A trivial algorithm would be this:

1. foreach x in L:
2.   foreach y in L:
3.      if x is substring of y:
4.         OUTPUT x,y

However, this has complexity $O(n^2 \cdot m)$ - I am curious to know whether there is a faster algorithm?

Edit:
As pointed out in the comments, there can be at most $n^2$ such pairs, so I don't see how there can be an algorithm faster than $O(n^2)$. However, I was wondering if there is something like a $P-FPT$ algorithm where the squared complexity is dependent on the number of output pairs, rather than $n$? Or at least an algorithm that reduces the complexity to something better than $O(n^2 \cdot m)$.

This can be solved with Aho-Corasick algorithm in $O(nm + Mm)$ time, where $M$ is the number of pairs outputted.

First build the Aho-Corasick automaton for the set of strings in $O(nm)$ time. Then run each string through the automaton - this takes $O(nm)$ time for running the strings through the automaton and $O(Mm)$ time for outputting the matches because the same string can match $m$ times in the worst case. (For example ab matches ababab 3 times.)

This can be improved to true linear $O(L + M)$ time, where $L$ is the total length of the strings and $M$ is the number of matches:

When running the strings through the automaton, store for each node of the automaton the index of the previous string for which this node was visited. When outputting the matches, stop following the dictionary links if the link leads to a node that has already been visited for this string - you have already outputted all matches that are upwards from that node. Now each match gets outputted exactly once, and we traverse dictionary links only when new matches are outputted.


Difference between multitasking, multithreading and multiprogramming I was a little confused between these three terms Multitasking, Multithreading and Multiprogramming

Although every one means executing different lines of codes, and for every one we need something like Task State Segment or context to store data for that particular thread/task.

I am missing something, can anyone give me the basic difference between them and how they are actually executed in a processor

Edit: Actually I was a guy from Electronics background and I was poor at OS related issues. The main thing I understood between multiprogramming and multithreading is that in multiprogramming we execute two separate programs where as in multithreading the scheduler produces two different threads which can be executed independently. I think these are a form of multitasking implementation. Am I correct. I was really confused

The Wikipedia article Computer multitasking covers this well. In summary:

Multitasking: there is more than one process and the operating system somehow decides which to run next.
Multithreading: threads are essentially subprocesses, which share memory (separate processes cannot normally access each other's memory) but which are independently scheduled.
Multiprogramming: a form of multitasking in which a process keeps running until it tries to access an I/O device, at which point another process is chosen to run so the CPU doesn't idle waiting for a punched card reader or something.


Implementing Do keyword in a compiler I'm writting a compiler implementation for a language that you can see defined here. I having problems designing how the do keyword should be handled. You can find the code I'm referring to in here.

Let me delve a little bit into the problem. According to the documentation:

  The do keyword is used to call an expression (normally, a method call)
  just for its side-effect, and discards the result.

Now according to the list of possible expressions in the file I referred to before:

IntLit(value)
StringLit(value)
True()
False()
And(lhs, rhs)
Or(lhs, rhs)
Plus(lhs, rhs)
Minus(lhs, rhs)
Times(lhs, rhs)
Div(lhs, rhs)
LessThan(lhs, rhs)
Not(expr)
Equals(lhs, rhs)
ArrayRead(arr, index)
ArrayLength(arr)
MethodCall(obj, meth, args)
Variable(Identifier(name))
New(tpe)
This()
NewIntArray(size)

I want to figure out first in which cases should do act. Clearly, it should act with MethodCall as it provides a result but also with expressions that contain operators (And,Or,Plus,Minus,Times,Div,LessThan,Not,Equals,...). What would be the complete list of cases I should consider?

My second question is how can I implement Do behaviour for MethodCall, that is, not getting the result but getting the side effects.

The general idea is that do ( expression ) is a statement that evaluates any expression and throws away the result.

A first attempt could be

  def evalExpr(e: ExprTree)(implicit ectx: EvaluationContext): Value =
    // ...

  def evalStatement(stmt: StatTree)(implicit ectx: EvaluationContext): Unit =
    stmt match {
      // ...
      case DoExpr(expr) =>
        evalExpr(expr)
    }
  }

but in this way, we return a Value and not a Unit, so the compiler raises a type error. We can fix that by using

      case DoExpr(expr) =>
        evalExpr(expr)
        ()  // the Unit value


Huffman Coding vs LZW Algorithm I'm trying to understand comparisons between the two. Is there ever a case where is it better to use Huffman Coding over LZW? Could the compression ratio for Huffman ever surpass that of LZW?

Thanks!

In a gist LZW is about frequency of repetitions and Huffman is about frequency of single byte occurrence.

Take the string 123123123.

(The following is an oversimplification but will make the point) LZW will identify that 123 is repeated three times and essentially create a dictionary of codes for sequences. It will esentially say when I say A I mean 123 here is AAA (or three bytes).

Huffman will detect the frequency of bytes (let's assume the text above is ASCII or UTF-8 (which will make ABC all single byte code points), so A=3, B=3, C=3 and there are no other items, so I can use 1.5 bits (well a 1 and 2 bit combo) to represent all characters. So let's say A=0, B=10, C=11. Huffman will encode the text ABCABCABC as (in bits) 010110101101011 (or 15 bits) or since we are usually limited to bytes 2 bytes.

What if we used Huffman on the LZW result?

Well AAA can be represented with a single bit (Let's choose 0) so 000 (3 bits or 1 byte rounding up).

The unfortunate part here is that Huffman and LZW require some info to decode so it won't quite be as awesome as sending a 0 and saying go decode with Huffman, then LZW, but in essence this combination results in very good compression results with real-world payloads that aren't already compressed (A JPG or ZIP file is unlikely to be compressible with this, but a .docx, xml doc, txt file, etc (the longer and more verbose and repetitive the better) will do. awesome!

If you look at the characteristics of the algorithms and have awareness of the data you will see that order of algorithms and repetition may well make a difference. Think of a doc 1TB in size of all "A"s and apply the above and think what would do better. Frankly a naive SingleByteUsageEncoder would do best as the minimal info here is what char how many times. Huffman would max out at approximately 1/8 (1 byte to one bit) LZW would do muuuuuuuch better. However if you had a doc with ever possible permutation of a sequence of letters then generally Huffman would do better. I think if you think carefully about this you will recognize that LZW is generally more helpful, but combos often achieve best results (assuming your goal is smallest size, not best performance).


Results on the difficulty of specific random 3-SAT problems? This is a companion question to Results on number of solutions to random 3-SAT?

Let $A$ and $B$ be two problems drawn from random 3-SAT, both with the same number of variables and clauses.  If $A$ has fewer satisfying assignments than $B$, do SAT solvers perform worse when trying to solve $A$ vs. $B$?    Are there any results on this?  (I'm a physicist by training, so a follow-up would be: is this even an interesting CS problem?)

EDIT:
I wrote a quick little DPLL-based program to calculate the number of satisfying assignments for $\alpha = 4$ and $N = 80$.  Here are the # of solutions and time to complete for a few random runs to illustrate the phenomenon that I'm looking for insight into:

368 solutions, 2.2 s
192 solutions, 8.4 s
UNSAT, 3.2 s
50492 solutions, 2.6 s
1212 solutions, 13.9 s

As illustrated above, both the number of solutions and the time to run can fluctuate significantly; is there any relationship between the two?

Research has concentrated not on the number of satisfying assignments, but on the clause density $\alpha$. It is (more or less) known that:

Below a certain threshold, the problem is easy. Moreover, the solution set is "continuous" (with high probability), in that all solutions are (more or less) connected.
After a certain threshold, there are no satisfying assignments (with high probability).
Between the two thresholds, the instance is satisfiable (with high probability), but a satisfying assignment is conjectured to be hard to find. Moreover, the solutions belong to exponentially many small clusters that are "far away" from each other: any path connecting them goes through an assignment that satisfies a relatively small fraction of clauses.

These thresholds have been calculated by physicists, but their work is not mathematically rigorous. Rigorously much is known, especially for random $k$-SAT and similar problems for large $k$, but the actual behavior for 3SAT hasn't been rigorously proven.

The literature on the area is enormous, but unfortunately I can't find a recent survey, though these probably do exist. You can start by reading a very short, relatively recent survey by Coja-Oghlan. A recent important rigorous result is Ding, Sly and Sun, who prove rigorously that the unsatisfiability threshold for $k$-SAT exists for large enough $k$.


What is wrong with my LP exercise (longest path cost for a graph) I have to do a linear programming exercise  but i have some problems regarding the result. I have a graph with N nodes and E edges, that is not acyclic, and each edge is associated to a cost. I have also two nodes (marked as B and E), and I have to find the maximum path cost from B to E. Also, each edge can be used at most k times and the total cost of the path must be at most C.

I have inserted also the constraint regarding the balance of each node as follow (where E are the edges and x[i,j] tells me how many times an edges is been used, and the two nodes B and E):

$\sum\nolimits_{j |(j,i) \in Edges} x(j,i) -\sum\nolimits_{j | (i,j) \in Edges} x(i,j) =0$

$\sum\nolimits_{j | (j,B) \in Edges} x(j,B) -\sum\nolimits_{j | (B,j) \in Edges} x(B,j) =-1$

$\sum\nolimits_{j | (j,E) \in Edges} x(j,E) -\sum\nolimits_{j | (E,j) \in Edges} x(E,j) =1$

The objective function is:
$max \sum\nolimits_{(i,j) \in Edges} x(i,j)*cost(i,j)$

Other constraints:

$x(i,j) <= K \forall (i,j) \in Edges$

$\sum\nolimits_{(i,j) \in Edges} x(i,j)*cost(i,j) <= C$

When i run the LP solver the solution that it gives me, of course it includes a path from B to E, but also an other cyclic path that not includes nodes B and E.

Any suggestion?

You are on a fool's errand: Longest Path is NP-hard, thus there is no LP for solving it.


What easy algorithms are there for calculating products of cycle decompositions? Here is the easy algorithm we are taught for adding two numbers in base-10 notation. We are taught this algorithm in first or second grade.

  sub infix:<+>(@x, @y) {
   #x, y are lists of digits
   #returns a list of digits
   my @greater = (@y.elems > @x.elems) ?? @y !! @x;
   my @lesser_ = (@y.elems > @x.elems) ?? @x !! @y;
   my @gPopped = @greater;
   my @lPopped = @lesser_;
   my $carry = 0;
   my @sum;
   loop (my $i = 0; $i < @greater.elems; $i++) {
     if (@lPopped.elems >= 1) {
       my $gDigit = @gPopped.tail;
       my $lDigit = @lPopped.tail;
       @sum.append: (($gDigit + $lDigit) % 10) + $carry;
       $carry = (($gDigit + $lDigit) / 10).floor;
       @lPopped = @lPopped.head(@lPopped.elems - 1);
       @gPopped = @gPopped.head(@gPopped.elems - 1);
     } else {
        my $gDigit = @gPopped.tail;
        @sum.append: $gDigit + $carry;
        $carry = 0;
        @gPopped = @gPopped.head(@gPopped.elems - 1);
     }
   }
   return @sum.reverse;
  }

The algorithm is very easy and a child can do it by hand. Meanwhile, I am unaware of any algorithm for multiplying two permutations decomposed into cycle form (e.g. $(123)\times(12)(34)$). What is an easy algorithm for multiplying two cycles?

Here is how I would do it manually, taking the example of $(123) \cdot (12)(34)$.

Start with a number appearing on the right permutation, say 1. The right permutation sends it to 2, and the left to 3.

Doing the same with 3, we get 4 and then 4.

Doing the same with 4, we get 3 then 1. We have closed a cycle $(134)$.

Now take another number on the right (or left) permutation not already covered – has to be 2. It gets sent to 1 then 2. We have closed a cycle – 2 is a fixed point.

In total, the result is $(134)$.

Now let's compute $(12)(34) \cdot (123)$.

Let's start with 1. It goes to 2 then 1. So it's a fixed point.

Let's try 2 next. It goes to 3 then 4, which goes to itself then 3, which goes to 1 then 2. We have closed a cycle $(243)$. That's the answer.


A special case for the subset sum problem: selecting from powers of two Given a multiset $X=\{x_1,\dots,x_n\}$ where every element $w_i$ is a power of two, and given an integer $M$, I'd like to determine if there is any subset of $X$ that sums to $M$.

(This question is based on a previous question about the subset problem where every number in the set is a multiple of two, but this time $X$ consists only of powers of two.)

Can we find an efficient algorithm for this problem? Could we make it any better than standard algorithms for subset sum or knapsack?

First, look at the bits that are set in $M$ and write it as $M = m_1+m_2+\dots$ where each $m_i$ is a power of two and such that $m_1$ is the smallest power of two, and so on.

If the numbers $x_i \in X$ are distinct powers of two and you can use each one zero or one times, the problem is trivial: If all $m_i$ are found in $X$, then $M$ can be formed by them, otherwise it can't. This is because missing powers of two can't be formed by a) any combination of larger powers of two or b) distinct smaller powers of two.

If the numbers $x_i$ aren't guaranteed to be distinct, it's a bit more complex. Missing powers of two still can't be formed by larger powers of two, but they can be formed by non-distinct smaller powers of two.

Let's look at how smaller powers of two can form larger powers of two. If you have powers of two $A = [a_1, \dots, a_n]$ that are smaller than a power of two $N$, and $S=\sum_{i=0}^n a_i$, then $N$ can be formed by them iff $S \ge N$. Let $b$ be the smallest power of two in $A$ and $c$ its number of occurences in $A$. If $c$ is odd, one $a_i=b$ can't combine with anything to form a higher power of two and the corresponding bit will be set in $S$. The others can be replaced with $\lfloor \frac{c}{2} \rfloor$ copies of the number $2b$ in $A$. If we continue this with higher powers of two until we get to $N$, we find that we can form $\lfloor \frac{S}{N} \rfloor$ copies of $N$ with $A$.

So, start with $m_1$. If it's found in $X$, we remove it and move to the next power of two. If it's not, we calculate the sum $S$ of all $x_i$ smaller than $m_1$ and remove them from $X$. If $S \lt N$, then $M$ can't be formed by $X$. Otherwise, we add $\lfloor \frac{S}{m_1} \rfloor - 1$ copies of $m_1$ to $X$ and continue in the same manner with the next smallest power of two in $M$.


Is there a repository for the hierarchy of proofs? I am self-learning proof assistants and decided to start on some basic proofs and work my way up. Since proofs are based on other proofs and so form a hierarchy, is there a repository of the hierarchy of proofs?

I know I can pick a particular proof-assistant and analyze its library to extract its hierarchy, however if I want to find the next proof in a chain to prove, I can't when it is not in the library.

In my mind I picture a graph, probably a DAG, of all of the known mathematical proofs that can be expressed using English statements, not proofs using pictures. This would be the master map (a map in the sense of starting at one point and traveling to another point via intermediate points), and for a particular proof assistant, one would have a subgraph of the master map. Then if one wanted to create a proof using a proof assistant found on the master not on the subgraph, by comparing the two graphs one could get an idea of the work needed to create the missing proof(s) for the proof assistant.

I am aware that mathematical proofs are not necessarily easily convertable for use with a proof assistant, however having a general idea of what to do is much better than none at all.

Also by having the master map, I can see if there are mulitple paths from one point to antoher and choose a path that is more amenable for the particualr proof assistant.

EDIT

In searching I found something similar for mathematical functions. I did not find one for proofs at the NIST

The Mizar system is a huge repository of math proofs. See the wikipedia page and the official website.

  of all of the known mathematical proofs that can be expressed using English statements

From wikipedia/Mizar_system#Mizar_language:

  The distinctive feature of the Mizar language is its readability

Proofs are written as articles, of which there are more than a thousand articles, and more than 50,000 proven theorems. The wikipedia page mentions some interesting ideas of the "QED manifesto", and how Mizar might be on its way to accomplishing this.

A huge graph of the Mizar library.

This paper might also be helpful: Combining Mizar and TPTP Semantic Presentation Tools


optimal placement of fixed length items on a given length I have got some equipment of standard lengths, say:

  equipment_lengths = {60, 48, 36, 29}

that I have to place on a given length of, say 100. I have to place this equipment so as to minimize material waste while covering the given length. I am allowed to exceed the given length of 100 but keep the excess minimized.  I am not allowed to drop short of the given length. Also I have an unlimited number of each equipment.

So, one solution to the above example would be:

  {60, 48} (excess = 60 + 48 - 100 = 8)

Another could be

  {60, 60} (excess = 60 + 60 - 100 = 20)

The first solution is preferable to the second one as it minimizes the excess.

My first approach has been to implement a greedy algorithm that takes the longest equipment and keeps placing those till I exceed the given length. Once that happens I remove the last equipment I placed and place the next smaller ones till I exceed again. In the end I select the combination with the least amount of excess. For example the algorithm will successively do the following:

60, 60 (excess = 20)
60, 48 (excess = 8)
60, 36, 36 (excess = 32)
60, 36, 29 (excess = 25)

So, now it will select {60, 48} as the optimal solution when you remove last one equipment on excess. The algorithm then repeats the exercise by removing the last two equipments and finds another optimal solution. Finally it chooses the best one among the two optimal solutions it found.

Now, I have been studying bin packing and knapsack problem variations and while these problems look similar, I haven't been able to apply them to my problem. Does my problem have a well known solution? If not, how should I go about it to efficiently find the globally optimum solution?

Additional information: I think giving preference to longer equipments should be a good idea as the equipments need to be joined with screws or bolts so joining two longer equipments would be less work than three shorter ones, but I don't think it's more important than material wastage.

Your problem is NP-hard.  The decision problem version of your problem is to ask whether there exists a selection of equipment achieving an excess of $e$ or less (given $e$ as input, and all the lengths).  The special case of $e=0$ is exactly the subset sum problem, which is NP-complete.  Therefore, the decision version of your problem is NP-complete, so finding an optimal set of equipment is NP-hard.  In other words, you cannot hope for a fully polynomial-time algorithm to solve this problem.

If the lengths are not too large, you can adapt the standard dynamic programming algorithm for subset sum to solve your problem as well.  It applies almost directly: the dynamic programming algorithm tells you, for each integer $\ell$, whether there is a way to choose equipment whose lengths sum to exactly $\ell$.  Now you can check whether there is a solution for $\ell=100$, $\ell=99$, $\ell=101$, $\ell=98$, $\ell=102$, etc. (in that order) and take the first solution you find.  The running time will be tolerable if the desired length (e.g., 100) is not too large.


Program counter format LC-2 Not really sure if this is an exact CS question. I'm reading the Patt/Patel Introduction to computing systems Powerpoint presentation and I don't understand about the program counter and instruction register format in LC-2.

On the memory pages section in chapter 5, it writes there:
"Direct mode addressing gets page number from PC[15:9] and page offset from IR[8:0]."
My question is, I don't understand why the format of PC and IR is in [x:y], can anyone explain it to me? I read on Wikipedia and it says that it should be base + offset, but why does the base and offset both have 2 separate values?

Thanks.

The notation is as follows: FROM[left bit : right bit], so in your example PC[15:9] means take bitfield (number) from PC from fifteenth bit to ninth bit, inclusive, so 15 - 9 + 1 = 7 bits.
The same applies for IR[8:0] meaning take bitfield from IR from eight to zeroth bit inclusive.
For example PC[14:14] would be exactly one bit long and in such case by convention one would write PC[14].


L = { , M is a DFA accepting all strings except finitely many Is the $L$ = { $<M>$, $M$ is a DFA accepting all strings except finitely many. }
decidable ? I am sort of confused about the question - what exactly does $M$ accept. How are those finitely many strings look like for a particular $DFA$? It is known that $DFA$ accepts infinite number of strings if it accepts at least one string with length $>=k$, where $k$ is the number of states. Does it mean that M doesn't accept any strings of size less then $|k|$ - since this number would be finite ?
I came up with the
 decider for $L$ call it $I$, which basically checks $M$ on accepting any strings of size less than $k$.
I = “On input $<M>$, where $M$ is a $DFA$:
1. Let $k$ be the number of states of $M$
2. Construct $k$ $DFA's$ denote them $D_i$, where $i$ goes from $0$ to $k-1$, $D_i$ accepts all strings of length exactly $i$
3. Construct a $DFA$ call it $T_i$ such that $L_i(T) = L(M) ∩ L(D_i)$.
4. Test $L_i(T) = ∅$ using the $E_{DFA}$ decider
5. if $E_{DFA} $ accepts for every $T_i$ and $E_{DFA}$ reject on $M$  => accept , otherwise reject.

Is there a simpler way of answering the question ?

It is indeed decidable, but your solution is not quite correct.

To restate the problem, we're given an encoding $\langle M\rangle$ of a DFA $M$, and we want to decide whether accepts every possible string except a very small (finite) number of them. So for each DFA encoding in this language $L$, there's an associated $x_{M} \in \mathbb{N}$ (which we don't know) and $M$ only rejects $x_{M}$ strings.

So for example, a DFA $A$ that accepts everything (i.e. $\Sigma^{\ast}$) would be in $L$, because $x_{A} = 0$, which is definitely a finite number. Similarly if we have a DFA $B$ which rejects the string $a$, but accepts everything else, this would be in $L$ as $x_{B} = 1$, which is also finite.

Right, now to showing that this decidable for every DFA $M$. To do this we need to make a key observation, similar to what you were proposing, but sort of reversed; if a DFA rejects only finitely many strings, they must all have length smaller than $k-1$, where $k$ is the number of states. Why is this true? Suppose that it rejects a string with length greater than $k-1$, then to process this string the DFA must go around a cycle (either a loop or a longer path, or some combination thereof), but if it can go around the cycle once, it can do it twice, or three times, or any number of times. So if there's at least one long rejected string, there must be an infinite number of rejected strings.

Using this, we can see that if it rejects a string of length somewhere between $k$ and $2k$ (a single go around the cycle can use each state at most twice), then it must reject an infinite number of strings.

Finally we can get to our decider:

On input $\langle M \rangle$ where $M$ is a DFA:

One by one, enumerate all strings of length $k$ to $2k$.

Simulate $M$ on each string.
If $M$ rejects any tested string, reject.

If $M$ rejects no strings of length between $k$ and $2k$, accept.


How could a formal system ever be non-obviously unsound? When reading discussions of Gödel's theorems one is always heeded that just because formal system $F$ proves a theorem $T$ that doesn't necessarily mean that when one applies the intended interpretation the theorem is actually true. After all, even if one assumes that $F$ is consistent, it might still be unsound.

But this puzzles me. When setting up $F$ one always makes sure that all the axioms are true under the intended interpretation. Presumably, one would also make sure that all the rules of inference are valid. That is, if all the theorems proven so far are true, then the rules of inference only produce further true theorems. Is that too much to ask?
However, this straightforward construction immediately implies that I can't prove falsehoods under the intended interpretation. Further, I'd be hesitant to even call something for which the rules of inference aren't truth preserving an "interpretation".
But then it seems that unsound formal systems couldn't even exist. So where's the problem with this view?

You jumped to a conclusion when you said that "when setting up $F$ one always makes sure that all the axioms are true under the intended interpretation". This is not the case at all. Using theories and formal systems as devices with which we reliably discover thruths is only one possible application.

Insisting that a formal system must be sound with respect to an "intended interpretation" can have the unfortunate effect of holding back development. For example, in order to discover non-Euclidean geometry someone had to contradict the dogma that Euclid's geometry was obviously true, and suggesting a theory which was non-Euclidean (which was considered obviously unsound) amounted to taking a professional career risk.

Sometimes there is no intended interpretation because we are exploring a new mathematical theory with which we have very little experience. In such a situation we will attempt to identify possible axioms and hope that their consequences will inform us about what is going on.

Sometimes we simply do not know what the intended interpretation is, and so we have to make a choice about accepting or rejecting an axiom based on other criteria than truth. Or better, we do not make a choice and study several options, without obsessing about "intended model". The most famous example of this is the axiom of choice in set theory. We know that set theory with choice is consistent if, and only if, set theory without choice is consistent. Which one is sound? On what grounds do we decide whether the axiom of choice is "true in the intended interpretation"?

So what is wrong with your view? I don't think much is wrong, except that it can hinder mathematical development. I advocate the position that the so called "intended interpretation" is in general an unknowable and uncommunicable entity whose existence is grounded in history and collective social norms. Of course, this does not imply that the "intended interpretation" is completely useless. On the contrary, it binds mathematicians together and allows them to share intuitions, and give coherence to mathematical development. But let us not confound an informal mathematical idea of "intended interpetation" with its mathematical ideal of a model.


Extension of Time Hierarchy Theorem to LBAs I am trying to prove:

  Let there be a constructible function $t: ~\mathcal{N} \to \mathcal{N}$. Then there exists a language $L$ where $L$ is decidable by an LBA in $O(t(n))$ time, but not $o\left(\frac{t(n)}{\log t(n)}\right)$ time. You may assume that LBAs have a fixed tape alphabet and have unique symbols marking the start and end of the input.

I've read through Sipser's version of the proof (Theorem 9.10) several times, but am not sure how to apply it to LBAs. Hints only please.

It may help you to remember that LBA's are simply non-deterministic TM's with a limited tape (instead of infinite).


Number of words in $\{pi,po\}^*$ of length at most 9 I have a language $L^*$ for $L = \{pi,po\}$ (I think pi counts as one letter and po also as one letter otherwise a max length of 9 is not possible).

The question is how many words I can make with $L^*$ where the maximum length is 9.

The answer is 31, but I do not know how it got calculated. How is this calculated?

Here are all words in $L^*$ of length at most 9:
$$
\epsilon, \\
pi, po, \\
pipi, pipo, popi, popo, \\
pipipi, pipipo, pipopi, pipopo, popipi, popipo, popopi, popopo, \\
pipipipi, pipipipo, pipipopi, pipipopo, pipopipi, pipopipo, pipopopi, pipopopo, popipipi, popipipo, popipopi, popipopo, popopipi, popopipo, popopopi, popopopo.
$$
In total, there are 31 words.

More generally, suppose that we have $m$ distinct words of length $\ell$. Then the total number of words of length at most $n$ is
$$
\sum_{r=0}^{\lfloor n/\ell \rfloor} m^r =
\frac{m^{\lfloor n/\ell \rfloor+1}-1}{m-1}.
$$
In our case, we get $\frac{2^{\lfloor 9/2 \rfloor + 1}-1}{2-1} = 2^{4+1}-1 = 31$.


How is the Delta Rule derived in neural networks and what is the explanation for the algebra? I am currently trying to learn how the Delta Rule works in a neural network. So far I completely understand the concept of the Delta Rule, but the derivation doesn't make sense. My question is how is the Delta Rule derived and what is the explanation for the algebra.
Currently I am writing equations to try to understand, they are as follows:
Desired = (Input * WeightD)
Actual = (Input * WeightA)
Error = (Input * WeightD) - (Input * WeightA)
Error = Input (WeightD - WeightA)
However, as stated Here, the ΔWeight is understood to be Error * Input, where as I derive it to be Error / Input. I fully understand the concept of correcting the weights in a neural network, however, I do not understand how the algebra and derivation of the Dela Rule work to re-adjust the weights to correctly represent the output. I will explain my current understanding to help you understand why I may be confused. Because the Input is constant whilst you attempt to find a correct weight, you can factor it out. This leads me to the equation that the Error is equal to the Input times the difference between the correct and incorrect weights. This is also very clear. However I do not understand where they go from here to get the equation to correct the weights. How is the required net change derived from this? How does the algebra behind simply Input * Error work? Thank you.

Your equations are wrong on several counts. First of all, the weights and the inputs are both vectors. Second, the value of actual is given by $\operatorname{sgn}(\langle \mathit{Input}, \mathit{Weights} \rangle)$, in words, the sign of the inner product of the input and the current weights. Similarly, the desired output is either $+1$ or $-1$. Therefore the error is either $+2$ (if the desired was $+1$ but the actual was $-1$) or $-2$ (in the opposite case). Third, we don't want to "solve" for the weights, since this would erase everything that we have learned so far.

The idea of the learning process is to give negative feedback. Suppose that we got $-1$ but we expected $+1$. We want to change the weights so that on the same input, $\langle \mathit{Input}, \mathit{Weights} \rangle$ will be larger. The most economical way (in some sense) is to update the weights with a new vector proportional to the input, since the input is the vector most correlated with itself (that is, the unit vector $w$ maximizing $\langle \mathit{Input},w \rangle$ is proportional to $\mathit{Input}$). Thus we increase the weights with some multiple of the input. If the error were in the other direction, we would decrease instead of increase — which is why we multiply the input by the error.


Till which layer does the loopback packet goes? I want to know exactly till which layer in the OSI model the 127.0.0.1 (loopback) packet goes till it is returned to the upper layer. I read some where it goes till data link layer. but as i was told data link layer cannot see the ip address then how data link layer decide that the packet has to be send "up" instead of "down".

When you say "layer", you are probably thinking of the OSI model, also known as the seven-layer model.

However, real TCP/IP implementations don't actually fit the OSI model very well.  The OSI model was designed by a standards committee 30 or 40 years ago, based on how the committee members thought network stacks ought to be designed -- but that was before the Internet and without the advantage of the experience we have today.

127.0.0.1 is an IP address, and the loopback functionality of 127.0.0.1 is associated with the IP protocol.  The IP protocol can be thought of as most closely associated with the "network layer" (in the OSI model).  So, you could say that the answer is "the network layer".

But, it's important to realize that this is a bit of a lie.  In real operating systems, there's not necessarily a clean separation between the TCP stack and the IP stack; the two are closely hooked together.  So, it's doesn't make sense to ask "the code that does loopback processing -- what layer is it at?".  The code that does loopback processing could plausibly be considered part of the TCP/IP stack, and the TCP/IP stack combines elements of the network layer, the transport layer, and the session layer.  Loopback processing might also be performed in a separate device driver that, from the operating system's perspective, looks like another device (just like another Ethernet card, but different), so one could even make an argument that the code is really part of the data link layer or physical layer.  See how the seven-layer OSI model isn't really adding much insight here?  The code is what the code is; trying to attach a label based on one of those seven layers is a human construct, one that in this case isn't a very good match to reality.

It's probably better to think of the OSI model as a plausible vocabulary for talking about network protocols, but it's less helpful when talking about the structure of networking code: the structure of the code doesn't necessarily correlate well to the seven layers of the OSI model.

TL;DR: the OSI model is a lie.


Find the Pumping Length for Language L of (2+3k) a's or (10+12k) b's The following question on the theory of computation is GATE 2019 CS question 24:

For $Σ = \{a, b\}$, let us consider the regular language: $$L = \{x \mid
 x = a^{2+3k} \text{ or } x = b^{10+12k}, k \geq 0\}$$  Which one of the
following can be a pumping length (the constant guaranteed by the
pumping lemma) for $L$?
(A) 3$\quad$(B) 5$\quad$(C) 9$\quad$(D) 24

My Attempt
I tired to solve like this. I divide the minimum string possible into $x(y^i)z$ that is $a^2$ so getting i value $2$ but option not available.
Then I take second minimum $a^5$ i.e., taking $x=\epsilon$ and $y=a^5$ and $z=\epsilon$.
I am getting $i=5$. So is it correct answer??

I am getting i=5. So is it correct answer?

I am afraid I could not understand your argument and conclusion clearly.

Anyway, can you check if you are able to pump $a^2, a^5, b^{10}, b^{22}$ using the pumping length of your choice?

Here are a few results stated in the form of exercises that you can prove and use to solve the problem in the question and beyond.

Assume $L$ is an arbitrary regular language.
Exercise 1. Show that there exists $p_0=p_0(L)\in \Bbb N^+$ such that $p\in\Bbb N$ is a pumping length for $L$ iff $p\ge p_0$.
We call $p_0$ the minimum pumping length of $L$.

Exercise 2. Let $L_{m,n}=\{a^m, a^{m+n}, a^{m+2n}, \cdots\}$ for $m,n\in\Bbb N$, $0<n$. Show that $p_0(L_{m,n})=m+1$.

Exercise 3. Let $L_1, L_2$ are two regular languages. Show that $p_0(L_1\cup L_2)\le\max(p_0(L_1), p_0(L_2))$

Exercise 4. Let $L_1, L_2$ are two regular languages over disjoint alphabets that do not contain the empty word. Show that $p_0(L_1\cup L_2)=\max(p_0(L_1), p_0(L_2))$

Exercise 5. Show that 11 is the minimum pumping length of $\{x\mid x=a^{2+3k} \text{ or } x=b^{10+12k},\ k\ge0\}$.


Is shuffling a set of items after popping an item meaningfully more random than doing it once, before starting? I'm working on a thing to randomly assign people into a shift. There's mostly 2 sets of people, "free" and "assigned".

Is shuffling the "free" set after assigning an employee meaningfully more random than just doing it before I start putting people into the "assigned" set? How can I come up with proof of this?

Say we have $n$ people. After shuffling the whole list (once), every person occupies every position with probability $1/n$.

Shuffling before each draw means every choice is uniformly random; that is, because the choices are now stochastically independent, being drawn as $i$th person has probability

$\qquad\displaystyle \frac{1}{n-i+1} \cdot \prod_{k=1}^{i-1} \Bigl(1-\frac{1}{n-k+1}\Bigr) \quad=\quad \frac{1}{n}$.

So no, shuffling repeatedly does not "add" any randomness -- whatever that would mean. It's uniform, i.e. "fair", to begin with, so what would "more random" mean?

The correct statement is: repeated shuffling does not change the distribution. Which means it is unnecessary, but also not harmful if it eases the mind of laymen participants.


Finding the nearest neighbour of an existing 2d point in a set of points within $\mathcal{O}(\log{}n)$ time Question

Is it possible to find an existing point's nearest neighbour within a logarithmic upper bound?

What I've tried

I have:

the set of points $P$,
a point $p$, where $p\in P$,
a point $q$, where $q\notin P$,
a Voronoi diagram, $V(P)$, of the points in $P$.

I know it's possible to query for a new point $q$'s nearest neighbour in $\mathcal{O}(\log{}n)$ time using $V(P)$ but is it possible to find the nearest neighbour of an existing point, such as $p$?

I've thought that if it wasn't possible, then I could delete the point $p$ in $V(P)$, assuming I could somehow create a dynamized Voronoi structure that allows for timely deletions (this paper notes that there is a way to insert points in constant time, so hopefully there's a Voronoi structure that allows deletions in logarithmic or less time), then search for the now non-existing point in logarithmic time. This would also solve my problem. Is there a dynamized Voronoi structure that allows deletions in $\mathcal{O}(\log n)$ time?

If you have a voronoi diagram you have neighbour information of each $p$. You can use that to path search (using A* or even greedy depth first) to the 3 points that surround $q$. Then you can extract the closest from that.

If the voronoi is stored as a binary tree where each line divides the space into half-planes then it's just a dive into the search tree.


Hyperplane through origin which goes through most number of points Given $M$ points in $\mathbb{R}^{N}$ (where $M$ is larger than $N$), I was wondering if there is an algorithm to find a $N-1$-dimensional hyperplane which goes through the origin and also intersects as many points as possible.

Specifically, does there exist an algorithm which runs faster than $O(M^{N})$ time? This is achieved by looking at all subspaces defined by each subset of $N-1$ points.

Furthermore, if there is no faster exact algorithm, I was wondering if there are any constant factor approximations which run faster than $O(M^{N})$. It would be greatly appreciated if someone can point me to the correct papers or references for these.

I suspect your problem might be hard, for the following reason:  The corresponding problem when working over a finite field is NP-hard.

Your problem is equivalent to the following:

Inputs: a $M \times N$ matrix $A$, with real-valued entries
Goal: Find $x \in \mathbb{R}^N$ that maximizes the number of 0 entries in $Ax$

The corresponding problem for a finite field (e.g., working with integers modulo a prime $p$, rather than real numbers) is known as the minimum-weight codeword problem for linear codes, and it is known to be NP-hard.  See, e.g.,
https://cs.stackexchange.com/a/59922/755,
Solving/Optimizing a linear system in a finite field (Z/2Z),
https://cstheory.stackexchange.com/q/27460/5038,
https://cstheory.stackexchange.com/q/21678/5038.
It's always possible that the problem is dramatically easier for real numbers than over a finite field, but that seems like it might be a lot to hope for.

Anyway, I don't know if there are algorithms with running time better than $O(M^N)$, but I suspect it's hard (not likely to have a polynomial-time solution).

See also https://cstheory.stackexchange.com/q/3719/5038 for a related but different problem.


Monte Carlo algorithm: Element in array Design a Monte Carlo algorithm that checks in constant time if a given element $x$ is in a $n$-dimensional vector $V$. Calculate the probability for a correct answer. Then suppose $n=10$, how many times the algorithm must be executed so the probability for a correct answer is greater than $0.9$?

Thats what I tried. Lets pick an arbitrary index $i$ which make sense in $V$, then check if $x=V[i]$ and return true or false as the equality holds or not.

My doubt comes at the time of calculating the probability of a correct answer as the statement gives no more details. Is it even numerically doable without additional asumptions?

I guess the probability of $x\in V$ once $x\not=V[i]$ is $$p=p_1+p_2+\dots+p_{n-1}$$ (following law of total probability) being $p_j$ the probability of $V$ having $j$ times the element $x$. But this probabilities are unknown. Or $$p=1-p'$$ being $p'$ the probability of $V$ not having $x$ as an element (also unknown).

Am I forced to suppose $V$ is a vector of elements of a certain finite set $X$ of $m$ elements or something similar?

It doesn't matter what other elements are. We can assume that $k$ elements in $V$ are equal to $x$. Then the probability for a correct answer would be $k/n$ and $1-k/n$ for an incorrect answer. Then after $m$ tries, the probability of failure would be $(1-\frac{k}{n})^m$.
And the probability of success in $m$ tries is the probability of not to be failed in every try, which is $1-(1-\frac{k}{n})^m$.


Asymptotic growth of a series How we can prove that:
$$
\sum_{k=1}^{c \log n-1}\:k\cdot \left(\frac{1}{2}\right)^{\frac{k}{3}}\in O\left(1\right) \quad \mbox{?}
$$


Big-O Notation and Calculus? I was wondering if there are any calculus relationships implicit in Big-O notation.

For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount at each step, and also involves looking at each part of the input a constant number of times. The derivative of a linear expression is a constant expression, so there is some hint of a pattern. However, I haven't been able to figure out how to generalize these facts to other Big-O classes of algorithms.

Do derivatives/antiderivatives help in matching an algorithm's Big-O description with its behavior?

an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount at each step

I don't think that's really true. It seems to me that all you're doing here is observing that a discrete linear function changes by a constant amount at each step and wondering if that's connected to the fact that the derivative of a continuous linear function is constant. That doesn't have much to do with what linear-time algorithms necessarily do.

Since algorithms are intrinsically discrete and calculus is intrinsically about continuous properties, I'm not aware of any real relationships between them. One might occasionally use calculus, e.g., to bound a sum by an integral or in tricks like
$$
\begin{align*}
\sum_{i=1}^k in^i &= \sum_{i=1}^k (i+1)n^i - \sum_{i=1}^k n^i\\
 &= \sum_{i=1}^k \frac{\mathrm{d}}{\mathrm{d}n}n^{i+1} - \sum_{i=1}^k n^i\\
 &= \frac{\mathrm{d}}{\mathrm{d}n}\sum_{i=1}^k n^{i+1} - \sum_{i=1}^k n^i\,,
\end{align*}$$
but I doubt that's the sort of application you had in mind.


Is there a decision algorithm with time complexity of Ө(n²)? Is there a decision problem with a time complexity of Ө(n²)?

In other words, I'm looking for a decision problem for which the best known solution has been proven to have a lower bound of N².

I thought about searching for the biggest number in matrix but the problem is that matrix is an input of O(n²) so the solution is linear.

It doesn't need to be known problem, a hypothetical one would suffice as well.

EDIT
I looking for a regular programing problem - not a Turing Machine.

It's could be an arrays, strings, graph etc.

Yes: Checking that a string is a palindrome takes $\Omega(n^2)$ on a single tape Turing machine.

In general the time hierachy theorem implies that there are such problems for most reasonable functions.

For RAM, edit distance can't be solved in $O(n^{2-\epsilon})$ for $\epsilon > 0$ unless the strong exponential time hypothesis is false.


Kolmogorov Complexity: Why would you need more bytes than the string itself? I was reading Wikipedia's entry on Kolmogorov Complexity (thanks to this question), which states:

  It can be shown that the Kolmogorov complexity of any string cannot be more than a few bytes larger than the length of the string itself.

Why would you ever need anything more than the string itself to describe it?

The exact value of the Kolmogorov complexity depends on the language chosen to represent strings. This language has to be Turing complete, so representing all strings as themselves isn't an option.

By the pigeonhole principle, if there is at least one string of length at most $n$ whose representation is shorter than itself, then there is also at least one string of length at most $n$ whose representation is longer than itself. (The representation is a compression algorithm.)

You can have a description language where each string has a representation that's at most one bit longer than itself: start each representation with a bit that indicates either “print literally” or “interpret”. Not all description languages are that simple though.

A more formal statement is given further down in the Wikipedia article, in the invariance theorem section. There are optimal description languages, such that for any given language, there is a constant $C$ such that the description of any string in the optimal language (no matter what its length is) is at most $C$ bits longer than in that other language. Intuitively, write an interpreter for the other language in the optimal language.


Does this problem map to the Set Packing problem? Let $G(m,n)$ be A bipartite graph $G$ with paritions $m$ and $n$ with the property that partition $\mathit n$ has two types of nodes (type1 or type2).

Given $G(m,n)$ and $k \in \mathbb Z+$:

Does $\mathit S\subset \mathit m$ where |$\mathit S$| $=$ $\mathit k$ exist so that none of $\mathit S$'s nodes are adjacent to nodes of type1, but all type2 nodes in $n$ are adjacent to nodes in $S$? ($S$ is a subset of the $m$ partition).

I can see a solution is easily verified by checking that each type2 in $n$ has a neighbor in $S$ and that |$S$| $=$ $k$. This means the problem is in NP.

To reduce the problem of Set Packing to the above, I am thinking to consider the of all of $m$ nodes's neighborhoods as subsets. But from here I am not sure how to proceed with the problem mapping.

You cannot reduce set-packing to your problem, unless P=NP.

There is a linear-time algorithm for your problem.

Remove all vertices of type 1 and all their neighbors. Let $m'$  (resp. $n'$) be the set of remaining vertices in $m$ (resp. $n$).
If $|m'| \ge k$ and the neighborhood of $m$ contains all the vertices in $n'$, the answer is yes.

If any of the above two conditions is not satisfied then the answer is no:

If $|m'| < k$ then any set $S \subseteq m$ with $|S| \ge k$ contains a vertex that is adjacent to some vertex of type 1 in $n$.
If there is a vertex $v \in n$ of type 2 that is not in the neighborhood of $m'$, then every vertex $u \in m$ that is adjacent to $v$ is also adjacent to a vertex of type 1 in $n$.


How to calculate the average of x numbers? I just started a college course and I'm being asked for a flowchart where I explain how to calculate the average of x quantity of numbers. For this assignment I'm asked to follow the problem solving steps, which are:

Identify the problem.
Comprehend the problem. (As in, "is it mathematical?")
Identify different alternatives to solve the problem.
Selecting the best alternative to solve the problem and why.
Construct a list of instructions that allows to solve the problem.
Evaluate the solution.

After this I need the make a flow chart of the steps of pseudo-code. All of this is for a course called Structured Programming where we are supposed to learn Java.

I want to make clear that I don't want you to do my assignment I just want an explanation on how to do it, what should be the function I use and how to structure the flowchart.

Instead of giving an answer, I will try to paraphrase the steps, I hope this will help you solve your homework.

Identify the problem: What is the input? What is the output?
Comprehend the problem: Can you write a formula for the problem, that relates input to the output? What is the formula for the average of x numbers?
Identify different alternatives to solve the problem: How can you implement that formula? As a closed-form function? With an iterator? Solving recursively?
Selecting the best alternative to solve the problem and why: Which one did you select in step 3, and why?
Construct a list of instructions that allows to solve the problem: Write the pseudo-code about how you can actually implement the solution you selected on step 3.
Evaluate the solution: Is it working? How well is it working? Are there any conditions that it is not working? What are they? How long does it take to produce an answer?

I hope that you are actually stuck and these explanations can guide you. Else I will regret my decision to help someone that actually looks for a ready-to-jump-on solution for his homework.


About Big O properties Suppose I have something like the following:

$f(x) = g(x) + O(x^n)$

And I apply a power $m$ to both sides

$f(x)^m = g(x)^m + \cdots + O(x^n)^m$

My question is whether the following is well formulated:

$O(x^n)^m = O(x^{nm})$

Thank you!

If $f(x) = O(x^n)$ then $f(x)^m = O(x^{nm})$. Indeed, $f(x) = O(x^n)$ means that $f(x) \leq Cx^n$ for some $C>0$. Therefore $f(x)^m \leq C^mx^{nm}$, and so $f(x)^m = O(x^{nm})$.

On the other hand, it is not true that $(g(x) + h(x))^m = g(x)^m + O(h(x)^m)$. For example, suppose that $g(x) = 2$ and $h(x) = 1$. Then it is not the case that $3^m = 2^m + O(1)$.

What is true is that $(g(x) + h(x))^m = O(g(x)^m + h(x)^m)$. Indeed, if $g(x) \leq h(x)$ then $$(g(x) + h(x))^m \leq (2h(x))^m = 2^m h(x)^m = O(h(x)^m) = O(g(x)^m + h(x)^m), $$
and similarly in the other case.

(Throughout this answer, $m \geq 1$ is a constant. The first part holds for any constant $m \geq 0$.)


Using transitive closure to determine acyclic property on directed graph Is it possible to use Warshall's algorithm (calculating the transitive closure) to determine if a directed graph is acyclic or not?

I'm trying to achieve this but getting stuck on the reflexive property of the transitive closure!

It is possible to use Warshall's algorithm for that also. If there is is a negative entry on the diagonal, then the graph contains a negative cycle. If both the shortest path from i to j and the shortest path from j to i is not infinite, then the graph contains a cycle. If there are no i and j with this property, then the graph is acyclic. (This takes only $O(|V|^2)$ steps to check, while Warshall's algorithm itself takes $O(|V|^3)$ steps.)

However, it's faster to use depth first search and check that there are no backward edges in the depth first search tree. Also note that there exists an algorithm for computing the transitive closure (including the transitive reduction) in $O(|V|\cdot|E|)$ steps. (I think it uses a topological order as a starting point.)


Does this regular expression equal this automata? I just came across an exercise which is to find a regular expression for the following automata, such that the regular expression and the automata generate the same language.

One solution presents the following expression:

$\qquad \displaystyle r_A = a^+b^+(c\mid ca^*b^+)^*$

However, can this be true? I think not, because the all words created from the regular expression will have at least one $b$ in it, whereas the automata accepts words without $b$, such as $aaa$.

What is your opinion?

In general, you can decide equivalence of regular expression and finite automaton using standard algorithms:

Construct an NFA from the regular expression,
Determinise and minimise both automata,
Check for equality (up to isomorphism).

These algorithms and proof that the minimal DFA of any regular language is unique (up to isomorphism) can be found in introductory textbooks.

If the underlying task is to "read off" a regular expression from an automaton, don't guess & proof but rather build the expression algorithmically to save time.


Efficient algorithm to find the nth number in a base-k numeral system with only different digits I am looking for an efficient algorithm for the following problem.

There is a base-k numeral system, and we want to have some k-length numbers, but all of the digits must be different ones.

It would be useful, if all of the possible feasible numbers would be unequivocal sortable (so the given nth number is always the same one).

An example to be clear:

k=5

possible digits: 0 ... (k-1) -> 0, 1, 2, 3, 4

we have a base-5 numeral system

we need numbers with length 5

possible feasible numbers:

01234

10234

02134

...

43210

The goal is, to find a way, that if I say, I need the 8th number, it will give me for example 34210 (and it will give me always this number, if I ask for the 8th one).

It is also important, that this algorithm should be efficient, if it is possible in O(1), or in P.

It would be also great, if the algorithm would not generate and store all of the possible feasible solutions, but somehow it could generate only that one appropriate number, which is the answer for the input.

I guess, there is no known P solution for this.

The brute-force and probably not the most efficient way would be, to generate and store all of the possible feasible solutions in a given order, and then we could answer any input, and the same input would generate always the same output. This solution satisfies all of the above criteria, but maybe there is a much more efficient algorithm to do this.

Your problem is known as unranking permutations in lexicographic order.  Bonet, Efficient Algorithms to Rank and Unrank Permutations
in Lexicographic Order describes efficient algorithms, and contains some pointers to the literature.

As described in the paper, more efficient algorithms are possible if you don't insist on lexicographic order.


How fundamental are matroids and greedoids in algorithm design? Initially, matroids were introduced to generalize the notions of linear independence of a collection of subsets $E$ over some ground set $I$. Certain problems that contain this structure permit greedy algorithms to find optimal solutions. The concept of greedoids was later introduced to generalize this structure to capture more problems that allow for optimal solutions to be found by greedy methods.

How often do these structures arise in algorithm design?

Furthermore, more often than not a greedy algorithm will not be able to fully capture what is necessary to find optimal solutions, but may still find very good approximate solutions (Bin Packing, for example). Given that, is there a way to measure how "close" a problem is to a greedoid or matroid?

It's difficult to answer the question "how often". But as with all "underlying structures" the benefit comes from recognizing that the underlying problem one is trying to solve has a matroid (or greedoid) structure. It's not just matroid problems. The matroid intersection problem has a specific model (bipartite matching).

Nick Harvey did his Ph.D thesis fairly recently on algorithms for matroid problems and also looked at submodular function optimization (which generalizes matroid problems). Reading the introduction and background to the thesis might be helpful.


Which classifier is more accurate for a SVM classification? I am learning the SVM classification and encounter a problem. I am not sure if this dilemma has a terminology for it.

Assume we would like to classify patient by SVM given the samples of healthy people ( of both gender) and people with liver cancer ( of both gender). If we label healthy people sample as class 1 and the people with cancer as class 2, we can train a binary SVM and obtain a classifier 1 to predict any new patient. Now, image another scenario. Assume that we first divide all samples by gender before SVM classification. For each gender, we still label healthy patients vs cancerous patients into 2 classes and train a binary SVM to obtain classifier 2 and classifier 3 for female and male samples respectively. The question is if there is a new female patient, which classifier, 1 or 2, should be used to obtain more accurate prediction ? Here is the dilemma for the arguments I have

(1) When the number of samples is large, the prediction should be more accurate. Based on this argument, the classifier 1 seems a good choice.

(2) However, if we divide samples into female and male groups first, the classifier 2 seems a better choice since the new patient (unknown test sample) is female.

Does this kind of dilemma have a terminology or does anyone know any further information or how to solve problem like this ? I am not even sure if this is a legit question and sorry for the naive question in advance. Thanks

You should take a look at Feature selection and algorithms that automate this process. It's okay if you are new to ML and don't understand the entire feature selection process, just get the proper intuition and then you can use a library to automate the process.

The key idea of having a Learning algorithm is so that it can find the patterns ... the most you can do, is help him out by providing lots of (non-redundant) data and having a good preprocessing step, that usually involves stuff like feature selection, and normalization.

On a friendly note, when implementing learning algorithms, you should not try to modify your dataset just by 'looking' at it, unless you have concrete metrics that testifies it needs modifications, many a  times, it has been the case, that the learning algorithm put high bias towards features that did not appear to be even remotely 'related' to the classification process. Always try to do a feature selection step before trying any modifications on your data.


Is this language semi-decidable? Let $M_w$ be the DTM encoded by the binary string $w$ and let
$$L=\{w\#x\,|\,\text{all states are reached when running }M_w\text{ on }x\}.$$
I've already proved that this language is undecidable (the halting problem can be reduced to this), but is this language semi-decidable? I.e., is there an enumeration of $L$ or a reduction of $L $ to a semi-decidable language?

You can start by considering this related problem:

$$L'=\{w\#x\#n\,|\,\text{all states are reached when running }M_w\text{ on }x\text{ within $|n|$ steps}\}.$$

Argue that $L'$ is decidable. Then, noting that

$$L=\{w\#x\,|\,\exists n.\ w\#x\#n \in L'\}.$$

should give you an idea about how to proceed.


processes response time confusion An OS contains 10 identical processes that were initiated at the same time.Each process contains 15 identical requests. Each request consume 20 msec of CPU time.A request is followed by an I/O operation which consumes 10 msec.The CPU scheduling overhead is 2 msec. The system uses Round Robin scheduling with the time quantum of 10 msec.

Q1) What is the response time of 1st request of last process ?
  A) 210 msec  B) 140 msec  c) 230 msec  D) 240 msec

Q2) The subsequent request of the processes receives a response times of
 A) 110 msec  B) 220 msec  C) 230 msec  D) 240 msec

Ans: Q1) D

 Q2) C

What I thought :

For 1 process, there are 15 request so
15 * ( 20 + 10) = 450 msec  But all answers are so small than this approach. So no need to think about further i.e. CPU overhead then 2nd...3rd...processes.

Here my problem is I didn't get the concept behind this question properly. CPU overhead ( i.e context switching ) will take place between 10 processes or each process's 15 request.
So please tell how this scenario will work.

I didn't get the meaning of 2nd question.

Hint : Try to understand more about context switching. Context switching takes place between 10 processes. (And you can forget about those 15 requests, instead consider each process needs 15 * 20 msec of CPU time)


Satisfiability Toward A Sequential Circuit Define a sequential circuit model be a directed graph with each vertices being a boolean gate. The difference is that we allow cycles in the boolean circuit. Each cycle will determine a boolean equation.

For example, constructing a loop by connecting the input and output of a negation gate will yield the equation $x=\lnot x$, which is not satisfiable. Given such circuit, the "satisfiability" in the sense naturally occur. My question is:

  Is determining whether this circuit can be satisfied known to be hard or easy? Furthermore, is finding or enumerating these configuration known to be hard or easy?

OK so now I figured this out. The problem is $NP$-complete. We could simply verify an assignment by checking each gate as an equation. For solving SAT of boolean function A(x), simply construct a equation, $y=y\otimes\lnot A(x)$ would suffice.


How to determine seed collision probability in a PRNG? I want to use a PRNG to generate random patterns. I would provide the PRNG with a hash value as a seed. Ideally, the seed size would be 64-bit or 128-bit and I would expect no collisions if the seeds are unique.

Do PRNGs encounter 'collisions', where two different seeds produce the exact same sequence of random numbers?

For example, if one initializes a PRNG with all possible 32-bit, 64-bit or 128-bit numbers, one would expect zero collisions since all seeds would be different.

When considering a Linear congruential generator, the seed gets divided into a multiplier. Since a Lehmer LCG uses a multiplier of 231-1, supplying a random 32-bit hash would cause collisions, since it is dividing all possible 32-bit numbers into 231-1 numbers. Thus, a seed of 1, 232-1 and 231 are equivalent and produce the same sequence of numbers. This is a problem since I am expecting the collision resistance of 64 or 128-bit hashes in the PRNG.

For more complicated algorithms, it's not as simple to determine these cases. My language of choice is JavaScript, which has no built-in seeded PRNG. There are of course many options to remedy this in the sense of libraries or standalone functions.

The best/fastest available PRNG for JavaScript seems to be Alea. It has a JS and C implementation and is based on Marsaglia's MWC algorithm. The JS implementation takes a variable string seed, so it is not clear how many unique seeds are possible. Alea is described as having a period length of 2116, which if I understand correctly, would mean it utilizes up to 116 bits of a supplied seed (e.g. a 128-bit hash).

Basically what I am asking is, how would I determine if seeds collide in a PRNG? Is it based on the described period length?

A good illustration of the issue is to compare Jenkin's small PRNG (2007) with xoshiro128+ (2018). They are quite similar. They both use 32-bit arithmetic, store the state in a 128-bit array composed of four uint32's and return one uint32 as the result. The main difference is that Jenkins only uses a 32-bit seed that is repeated in b,c,d. While in xoshiro128+ the entire initial state is the seed. Thus I can supply a 128-bit hash to the latter as the seed and still benefit from the quality of the generator (without modifying the algorithm). That is essentially what I mean - being able to provide a very large seed.

As a workaround to this potential issue, I thought about simply using the hash function itself, and running further iterations of the mixing function to obtain new pseudo-random bits (in the same way as obtaining a new number in a PRNG). It is deterministic and appears random enough, but it seems unlikely that hash function outputs pass "statistical randomness tests" such as Diehard or BigCrush since it was not designed as a PRNG.

Also, there are no cryptographic requirements here. The hash function I would use would be MurmurHash3 or similar--anything good enough to pass SMHasher suite of tests and produces 64-bit or 128-bit hashes.

It depends on the PRNG.  But it doesn't matter in practice.  As long as the probability of collisions is low enough, who cares?  These are pseudorandom numbers, so no one ever claimed they are perfect (exactly uniformly distributed); at best they are indistinguishable from random by any procedure that uses a limited amount of computing power.