What defines a subproblem? In algorithm analysis what exactly defines a subproblem?

I know that one of the optimality conditions for greedy algorithms is that all subproblems of the solution are also optimal, but to me this begs the question. Are subproblems defined relative to a data set, a problem on that data set, or a solution to that problem?

As an example, a shortest path algorithm on a connected graph with vertices {a,b,c,d,e} for a path from a to e may return {(a,b),(b,c),(c,d),(d,e)}, and the subproblems here to me are every path from an earlier vertex in the list to a later vertex in the list, implying that you have subproblems relative to a solution.

An example that confuses me, however, is dealing with sequence alignment on strings.
Given an optimal alignment for two sequences, what are the subproblems? Is it the alignment of any partition of the two strings? Because the answer to an alignment problem can actually return different strings.

For example, if we're aligning ["AT","CAT"] we should get ["_AT","CAT"]

But for the 0th index here it doesn't make sense to say that ["_","C"] is a subproblem, or that ["A","C"] is a subproblem, because they're both trivial (alignment of two singletons can never be suboptimal), and ["A","C"] is never actually aligned/compared in the result.

There is no formal definition. A subproblem is just a (usually smaller!) problem that you solve on the way to solving the problem you're really interested in.


How do I know if my algorithm is right (without coding)? For some background :
I think I am quite good at advanced (graduate/research level) mathematics and physics but I have no CS background. Now I am taking a graduate level class on algorithms.

I don't think I have ever written a wrong proof in mathematics - as in either I can prove something or I can't. I have never faced a situation whereby I wrote a wrong proof - its just obvious if I am writing a wrong proof.

BUT with algorithms it seems that its just trivial to write a wrong algorithm. I am simply not getting as to how does one know if what one has written is right or wrong. There seems to be something "mysterious" going on here - like while I write a recursive/dynamic programming solution etc. - I am thinking that I wrote something right but then somebody comes along with an example where my answer doesn't work!

Its quite contrary to my years of experience of writing proofs in mathematics!

This is getting freaking scary! Its better to not be able to do something than to be writing a wrong answer and not knowing it! (...often enough I land up writing a greedy solution trying to optimize something locally but its not the globally correct answer!..how does one see it!?...coming up with a counter-example is also almost always very hard!..)

Can someone help?

I am currently doing a lot of practice with this but I wonder if there is something that I am missing totally!

You prove that the algorithm is correct.  This requires (1) writing out a precise specification of what you mean by correctness, (2) writing a mathematical proof that your algorithm meets this specification.  Algorithms courses and textbooks often include some material on how to prove algorithms correct, as well as many examples of this, so that would be a good starting point to study, if you want to learn more about proofs of correctness for algorithms.  See also formal methods / formal verification, and possibly the following question on this site: How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect


What complexity class is this set of grammars? In between NL and P? Given a grammar where (every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$), (($X \to YZ$) implies ($X \to ZY$)) and (($XY \to Z$) implies ($YX \to Z$)) where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

What complexity class does this correspond to?

It appears to be the problem of finding an "all-in-path" in a "3-digraph" (See: Is there a name for this directed graph and path concept? 3-digraph and all-in-path?).

Related questions:

What complexity class does is this set of grammars? L-complete?

What complexity class does is this set of grammars? NL-complete?

What complexity class is this set of grammars?

What complexity class is this set of grammars? RE?

This appears "almost P-complete".

I think this is existential and P-complete is universal.

This problem corresponds to, "given (1) a SAT problem, (2) a candidate solution, and (3) a variable A, does (A imply (not A))?" This problem shows the existence of a contradiction (for a single variable).

P-complete corresponds to "given (1) a SAT problem, and (2) a candidate solution, does there exist a variable X such that (X implies (not X))?" By showing there exists a solution, you show the non-existence of a contradiction (for all variables).

Sometimes it's easier to find a contradiction than a solution. Consider a Horn-SAT problem containing the clauses A and (not A). You don't need to check the other clauses.

This assumes the original question is equivalent to finding an "all-in-path" in a "3-digraph" (See: Is there a name for this directed graph and path concept? 3-digraph and all-in-path?

Given a 3-SAT instance S, candidate solution Candidate and a target variable, X, does X imply not X?

We will construct a 3-digraph:

For each literal A and its negation nA, in S, create a vertex.

Rewrite each or-clause in S:

(A or B or C)

((A or B) or C)

(not(not((A or B))) or C)

(not(not(A) and not(B))) or C)

(not(A) and not(B)) implies C)

Since there are 6 permutations of A,B,C, there are 6 rewrites. For each rewrite, add 2 directed edges: nA->C and nB->C.

Create a new vertex, Candidate. For each literal A in Candidate, add a directed edge Candidate->A.

Create a new vertex, XContradiction. Add directed edges X->Xcontradiction nX->Xcontradiction.

(After adding edges, ensure this is a trigraph.)

Is there an all-in-path from S to Xcontradiction?

If we show the non-existence of an all-in-path for each literal (and not just X), then we have decided the corresponding P problem (does Candidate satisfy).


Alternative algorithms for calculating x^2? I'm emulating 128-bit arithmetic. At the moment I'm calculating $x^2$ by computing $x\cdot x$. What might be some alternative methods that aren't simply dressing up multiplication?

Base on the fact that:

If n is an even number $(n = 2m) \implies n^2 = 4m^2$

If n is an odd number $(n = 2m + 1) \implies n^2 = 4m^2 + 4m + 1$

And you can calculate $m$ by bitwise shifting right of $n$, calculate $4m$ (or $4m^2$) by bitwise shifting left.

So you can apply the recursion method to this process to establish the result with $O(\log n)$ time complexity.


How to compare the output of a neural network with his target? I am coding a neural network implementation, but a I have problems in the design. I was wondering about how to compare the output with the target, my neural networks has three outputs

 groups = {'Iris-virginica':[0,0,1], 'Iris-setosa':[0,1,0], 'Iris-versicolor':[1,0,0]}

I know I must translate each output to 0 and 1.

I meant if my result is Iris-virginica and my output is more or less: [0.999979082561091, 0.9999918549147135, 0.9998408912106317], the subtraction would yield the following result:

[-0.999979082561091, -0.9999918549147135, 0.000159]

Is that correct, or I need to follow a different approach. Is possible train my net with 0, 1 and 2 values. Do I need to know any more?

The easy answer: Take the predicted class to be the argmax of your output vector.

The longer answer: Since you're doing multiclass classification you should probably be using softmax output units (if I had to guess, I would guess you're using sigmoid output units). If $\mathbf{x} \in \mathbb{R}^n$ is the input to your output units then the softmax for the $i$th output unit is

$$ y_i = \frac{\exp(x_i)}{\sum_{j}\exp(x_j)} $$

This output function is nice for a number of reasons.

since your output vector sums to 1, you can interpret it probabilistically.
the derivative is particularly nice in combination with a log loss function.

Note: the further information I've provided may seen redundant since clearly

$$ \text{argmax}\{\mathbf{x}\} = \text{argmax}\{\mathbf{\sigma(x)}\} = \text{argmax}\{\mathbf{\text{softmax}(x)}\}, $$

where $\sigma$ is the elementwise logistic sigmoid function. The problem with just taking the argmax of what you have is you will likely not be optimizing the function you are actually interested in internally.

On the other hand the choice of loss function for classification isn't as cut and dry as I've made it sound.


Another version of the 3-coloring decision problem? Given a graph $G$, is there a 3-coloring with colors $c1$, $c2$ and $c3$ such that at most $k$ nodes are given the color $c1$ and that no two adjacent nodes are given the same color?
Is there a decently fast algorithm to solve this? My only solution is to go through every subsets of size $1$ to $k$ and remove those nodes and check if the graph is bipartite. I am also not sure if this runs in polynomial time.

Note that when $k$ is a fixed constant (that is, $k$ is not part of the input, for example $k = 17$ ), then the problem is easy. Indeed, in this case, your suggestion works because $n \choose l$ is polynomial in $n$, for every $l\leq k$. Also, checking whether a graph is bipartite can be done in polynomial time.
If $k$ is part of the input, then your problem is harder than the NP-complete vertex-deletion graph bipartization problem. The later problem is defined as follows. Given a graph $G$ and an integer $k\geq 0$, find a subset of at most $k$ vertices such that removing these vertices results in a bipartite graph.
To see why your problem is harder, assume that you have indeed succeeded in coloring a graph with $c_1, c_2$ and $c_3$, where at most $k$ vertices are colored with $c_1$. Then, removing the vertices that are colored with $c_1$ leaves us with a subgraph colored with $c_2$ and $c_3$, and thus the remaining subgraph has to be bipartite as two vertices with same color cannot be neighbors.
The vertex-deletion graph bipartization problem is known to be NP-complete even when restricted to planar graphs. See here.


Relation between CLR Grammar and Ambiguity I am studying CLR Parser and have a query about Grammar. If a Grammar can't be parsed using CLR(1) Parser ( i.e LR(1)) parser is it necessarily ambiguous?

Is it possible that a grammar which is unambiguous can't be parsed using CLR Parser?

A grammar may be may unambiguous, but not parsable by a LR(k) parser.
It is actually possible that a language has an unambiguous grammar,
but cannot be parsed deterministically by any PDA, hence has no LR(k)
parser.

For example the language $\{a^nb^n\mid n>0\}\cup\{a^nb^{2n}\mid n>0\}$.
It is clearly unambiguous (it is easy to write an unambiguous grammar for it). But, informally, there is just no way you
can decide which way you want to parse before you have read all the
$a$ and as many $b$.

An ambiguous grammar may define a language that has another grammar
that is not ambiguous, and may even be CLR(1) or LR(0). Actually, you
can just take an LR(0) grammar and add a few useless rule to make it
ambiguous without changing the language.

However, there are context-free languages that are inherently
ambiguous, i.e. that can only be defined by an ambiguous grammar.
And of course, there is no way an inherently ambiguous language can be
parsed deterministically.


If we spoke in TM-computable English, what would it look like? We know that any "effectively computable" process is computable by a Turing machine (Turing-Church thesis).

Although it seems that "effectively computable" is still open to discussion, the intuitive interpretation is that any process that is "mechanical enough" can be computed by a Turing machine.

Turing's initial objective was to axiomatise how humans do reasoning. Now what do you need to reason? Non-ambiguous definitions (axioms) and non-ambiguous rules. Then you are good to go. So in effect if TM successfully modelise how humans think, that's all they should need and hence natural languages should be quite a close candidate to become regular languages as long as we impose that words have just one meaning.

My question is then, intuitively, is it enough for a language to be "non-ambiguous" to be computed by a Turing machine? Or is there more intuitive properties that the language need to respect?

(I am currently trying to figure out if the laws voted in a parliament, although written in mundane English, have enough of these characteristics to be computed by an automaton).

Under reasonable assumptions, there is a TM which can decide whether something is a valid piece of English legalese. We can safely assume that the length of a law is bounded by some finite number $k$, say the number of characters the fastest human reader can read in less than two hundred years. There is then only a finite number of possible strings that might or might not be valid laws. Hence there is a lookup table of finite size that contains for every string of length at most $k$ the correct answer.

It is not settled whether humans can in fact recognize languages that TM can't recognize, so it's unclear whether the length restriction is truly necessary. See for example this question, or this question.

This is of course a boring answer, because this TM is completely impractical to construct. In actual practice you probably want to restrict yourself to a subset of English that can be parsed by an LL(k) parser (real English is not context-free), or go for a language specifically designed to be easy to understand to both humans and computers. @LukasBarth mentioned Lojban in the comments, but there are a number of such languages (programming languages are another example).


How to solve this mapping reduction problem by proving the computability of this function? I am working on a mapping reduction problem. Define the union of two languages $L_1,L_2\subseteq\{0,1\}^*$ to be $L_1 \cup L_2 = \{x0\mid x \in L_1\} \cup \{y1\mid y \in L_2\}$. I want to prove that $L_1 \le_m L_1 \cup L_2$.

I was reading about the mapping reduction. According to mapping reductions, for any $w \in \Sigma^*$, $w \in L_1$ iff $f(w) \in L_1 \cup L_2$.

I am thinking of making my computable function $f=\{x \mid x\text{ ends with }0\}$. If I can prove that this function is computable, then I can complete my reduction. I just have two following questions:

Am I thinking correctly about this problem?
How to correctly prove that this $f$ is computable? I am thinking to create a TM $M$ that enumerates $w \in L_1 \cup L_2$. If the string ends with a 0, then I halt the machine and accept the result. I am not sure how to formally prove the computability of $f$.

The reduction function is simply

$$
f(x)=x0
$$

which is computable, since a TM can move to the end of $x$, append a $0$, and halt. It is also total, by definition.

Note that to prove that $f$ is computable we do NOT have to consider the decidability / enumerability of any sets. I think your confusion is caused by thinking about c.e. sets when crafting $f$, but defining a reduction function does not involve enumerability. You only have to ensure that $f$ is total computable, and that $x\in A \iff f(x)\in B$ for all $x$.


Given an non-deterministic finite automaton, will its determinization always have unreachable states? Given an NFA that accepts the regular language L, will its equivalent DFA which accepts the same language L always have unreachable states.
If it does, why?

No, there aren't always unreachable states.  Consider the NFA with one state, $q$, and no transitions.  (It accepts the language $\{\epsilon\}$ if $q$ is accepting, and accepts $\emptyset$, otherwise.)

If you determinize this automaton, you end up with a two-state DFA with a transition from the start state $\{q\}$ to the other state, $\emptyset$, so both states are reachable.


Creating a list of minimum-distance pairs from two lists Let's say there are two lists of objects, list1 and list2, and that there is a function that can generate the "distance" between an object in list1 and an object in list2. What I would like to do is create a list of pairs of objects from each list such that the sum of all the distances of each of the pairs is minimal.

The only method that has occurred to me so far is just a brute force solution of creating a matrix of all the distances between list1 and list2 and then examining the sums of the distances of all possible combinations. Obviously, that approach is rather unappealing. I'm sure that many people have come across a similar problem before but I've been having a hard time phrasing my question in such a way that Google can help me out. Anybody have any ideas?

This seems to be a classical example of bipartite weighted maximum matching, for which there are efficient algorithms (you'll have to convert your minimization objective to a maximization one).


How 2-QCNF algorithm works? Suppose we have following 2-QCNF problem:

$$\forall x_1...\forall x_m\exists y_1...\exists y_k:\varphi(x_1,...,y_k)$$

where $\varphi$ is 2-CNF.

When the formula is false?

Rules that I found:

$\exists y_i:(y_i\rightarrow \overline{y_i})\land(\overline{y_i}\rightarrow y_i).$ Existentially quantified variable and it's negation are strongly connected.
$\exists\{x_i,x_j\}:(x_i\rightarrow x_j)\lor(\overline{x_i}\rightarrow x_j)\lor(x_i\rightarrow \overline{x_j})\lor(\overline{x_i}\rightarrow \overline{x_j}).$ Two (or one and it's negation) totally quantified variables are connected.
$\exists\{x_i,y_j\}:((y_j\rightarrow x_i)\land(\overline{y_j}\rightarrow x_i))\lor((y_j\rightarrow \overline{x_i})\land(\overline{y_j}\rightarrow \overline{x_i})).$ Totally quantified variable is reachable from existentially quantified variable and it's negation.

Is there any other rule to solve 2-QCNF or, maybe, there is better way to solve it?

Aspvall, Plass and Tarjan describe a linear time algorithm determining the truth value of quantified 2CNFs in their paper A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Their algorithm is an extension of the well-known algorithm for solving 2SAT using directed reachability; their initial step is computing the strongly connected components of the implication graph.


Are Lie theoretic codes impractical? I have been recently studying Lie theory. I discovered that there is a family of Lie theoretic error correcting codes. I did not find any information except this paper:

“Representations of Lie Algebras and Coding Theory“ by Xiaoping Xu

So, my question is: why isn't there a further development of this research? Are these codes considered inefficient or impractical?

There are zillions of papers in coding theory, proposing zillions of codes. Most of them are not used, due to several reasons:

Some of the codes are non-constructive.
Some of the codes don't have efficient decoding procedures.
Some of the codes have bad parameters.

The main reason, however, is that practitioners don't spend their time reading the coding theory literature and thinking up applications of the various codes. Rather, given a concrete problem, they first look up the "standard" solutions they know of. I'm putting "standard" in quotes since different people probably use different types of codes — whatever they are used to. There are many reasons for this:

Known codes are the easier to find out about — they are already familiar.
Code (and sometimes hardware) is already available.
Bosses prefer using known and proven tools.
Practitioners are often interested in properties which are either hard to prove or are simply not completely formal, but could be tested experimentally (for example, recovery from burst errors). These are found in their own literature rather than the theoretical coding theory literature.

If none of the standard codes seem to work, then they are in trouble and probably ask an expert. The expert probably knows some other standard codes which do work.

For a new code or type of code to reach the mainstream requires a lot of publicity to make the community aware of it. Mathematicians working in coding theory don't usually care about the practical side, and indeed, often their constructions have theoretical aims which are not important in practice (this is especially common for researchers in theoretical computer science). Even if a particular code is practical, the researcher is usually not interested enough in promoting it for it to become widely known among the practitioners.

Engineers, on the other hand, might publish new practical codes, and rarely one of them does change the mainstream paradigm. Most papers are, however, small variations on known techniques, and are important mostly for people's resumes, or for the particular project they were developed for.

In your particular case, the paper you are linking to is theoretical, and ignores one of the main questions in coding theory, namely how to efficiently decode. This shows that it's a theoretical paper. The motivation behind the paper is to construct orthogonal codes with good parameters. It mentions that orthogonal codes have applications in mathematics, but not necessarily in "real life". Furthermore, as you mention, the construction seems novel, which makes it more interesting mathematically. Practically speaking, the novelty is not as important as the "usability" of the code in terms of parameters and ease of encoding and decoding, an issue not mentioned at all.


Result of ANDing & ORing functions expressed as CDNF & CCNF I came across following fact:

  If we AND two functions expressed as CDNF (Canonical Disjunctive Normal Form), then the result contains sum of commont minterms.

For example consider two functions $f_1$ and $f_2$ on three variables $A,B$  and $C$ expressed in CDNF. Then they will have eight minterms: $m_0$ to $m_7$.

If

$f_1 = \sum ({m_1,m_2,m_3}) = m_1+m_2+m_3$  and

$f_1 = \sum ({m_2,m_3,m_4})=m_2+m_3+m_4$

then,

$f_1.f_2=m_2+m_3$ as $m_2$ and $m_3$ are common in both $f_1$ and $f_2$.

However now I am thinking about what will be the result of

$f_1+f_2$

If we consider $F_1$ and $F_2$ on three variables $A,B$  and $C$ expressed in CCNF (Canonical Conjuctive Normal Form) as follows:

$F_1 = \prod ({M_1,M_2,M_3}) = M_1.M_2.M_3$  and

$F_1 = \prod ({M_2,M_3,M_4}) = M_2.M_3.M_4$

then what will be the result of
$F_1.F_2$
$F_1+F_2$

After some thinking, I came up with following:

$f_1+f_2$ will be

  union of minterms in both functions, that is sum of all minterms with the common minterm appearing only once.

Thus, $f_1+f_2 = m_1+m_2+m_3+m_4$
$F_1.F_2$ will also be

  union of the maxterms in both functions. That is the product of all maxterms with the common maxterms appearing only once.

Thus, $F_1.F_2=M_1.M_2.M_3.M_4$
I found it very tricky to think about $F_1+F_2$. In the end I felt it should be

  AND of OR of two different maxterms with no OR of same and common maxterms.

$\therefore F_1+F_2= (M_1+M_2)(M_1+M_3)(M_1+M_4)(M_2+M_3)(M_2+M_4)(M_3+M_4)$
So $(M_2+M_2)$ and $(M_3+M_3)$ will not be there.

as $f_1.f_2$ was

  OR of AND of two same and common minterms with no AND of different minterms.

So above $f_1.f_2$ was actually $m_2.m_2+m_3.m_3$. This because AND of different terms will be $0 (false)$ and $0+a=a$

However, if I am correct with $(M_2+M_2)$ and $(M_3+M_3)$ being not part of $F_1+F_2$, I don't understand why that would be. If I think as dual of "AND of different terms will be $0 (false)$ and $0+a=a$", it would be "OR of same terms will be $1 (true)$ and $1.a=a$". But I dont get how OR of same terms will be 1?

I am just trying to find some pattern here and didnt found this explained anywhere.

Q. Am I correct with these three guessings?

Q. If yes then I will like to know about above bold-faced question: how OR of same terms will be 1?

There is no need to guess. Try to prove your guesses. If $f$ is the disjunction of minterms $\{m_i : i \in I\}$ and $g$ is the disjunction of minterms $\{m_j : j \in J\}$ then it is definitely the case that $f + g$ is the disjunction of $\{m_k : k \in I \cup J\}$, but not all $m_k$ are necessarily minterms. For example, $x + xy = x$.

Regarding $F+G$, try to use de Morgan's rules twice to reduce it to the case of $fg$, which is identical other than the operators involved. In Boolean algebra addition and multiplication are dual (via de Morgan's rules), so anything you can with CNFs you can also do with DNFs.


Using Myhill Nerode to prove that a language is not regular Prove that the language $A$ on $\{0,1\}$ containing all words for which the number of $0$s is equal to the number of $1$s is not regular.
I know one way to do it would be to show that the cardinality of $A / \mathbin \equiv$ is infinite. But how would I find the different equivalence classes and then show it has an infinite number of equivalence classes?

Let $L$ be your language and let $\equiv$ be the equivalence relation defined by $x \equiv y$ iff $x \in \Sigma^*$ and $y \in \Sigma^*$ have no distinguishing extension (a distinguishing extension is a word $z \in \Sigma^*$ such that exactly one of $xz$ and $yz$ belongs to $L$).
Given $i,j \in \mathbb{N}$ with $i < j$, $0^i$ and $0^j$ cannot belong the same equivalence class since $1^i$ is a distinguishing extension for them: $0^i 1^i \in L$ but $0^j 1^i \not\in L$.
This shows that $L/\mathbin\equiv$ is not finite, and hence $L$ is not regular.


Are randomized algorithms constructive? From , the proofs by the probabilistic method are often said to be non-constructive.

However,  a proof by probabilistic method indeed designs a randomized algorithm and uses it for proving existence. Quoted from p103 of Randomized Algorithms
 By Rajeev Motwani, Prabhakar Raghavan:

  We could view the proof  by the probabilistic method as a randomized
  algorithm. This would then require a further analysis bounding the
  probability that the algorithm fails to find a good partition on a
  given execution. The main difference between a thought experiment in
  the probabilistic method and a randomized algorithm is the end that
  each yields. When we use the probabilistic method, we are only
  concerned with showing that a combinatorial object exists; thus, we
  are content with showing that a favorable event occurs with non-zero
  probability. With a randomized algorithm, on the other hand,
  efficiency is an important consideration - we cannot tolerate a
  miniscule success probability.

So I wonder if randomized algorithms are viewed as not constructive, although they do output a solution at the end of each run, which may or may not be an ideal solution.

How is an algorithm or proof being "constructive" defined?

Thanks!

The probabilistic method is typically used to show that the probability of some random object having a certain property is non-zero, but doesn't exhibit any examples. It does guarantee that a "repeat-until-success" algorithm will eventually terminate, but does not give an upper bound on the runtime. So unless the probability of a property holding is substantial, an existence proof by the probabilistic method makes a very poor algorithm.

In point of fact, probabilistic algorithms aren't actually constructive existence proofs, so much as they are algorithms to produce constructive existence proofs. The output is an object of the sort which it was meant to prove the existence of; but the fact that it will eventually yield one ("there will exist an iteration in which it yields an example — except with probability zero...") is not enough to be constructive; it will only be satisfactory to someone who already accepts that non-zero-probability-without-construction suffices for existence. Conversely, if you do have a good bound on the run-time, then there's in principle no excuse not to run it in order to actually produce an example. A good probabilistic algorithm still isn't a constructive proof, but a good plan to obtain a constructive proof.

Note that this idea, that a randomized algorithm is a proof strategy (as opposed to a proof in itself) to demonstrate an existential quantification, is not unlike the idea that induction is a good proof strategy to show a universal quantification (over the natural numbers). This analogy may seem compelling, as induction is essentially the heart of recursion as a computational technique. (For any positive integer $n$, if you want to decide whether $n^2$ is a sum of the consecutive odd numbers preceding $2n+1$, you can reduce this to investigating whether $(n-1)^2$ is a sum of the consecutive odd numbers preceding $2n-1$, and so forth.) Induction is essentially an algorithmic proof-strategy which we have elevated to a theorem, allowing us to have the knowledge without explicitly computing it each time. However, induction is accepted constructively because it is already an axiom(-scheme) of Peano arithmetic, and one which is independent of the other axioms. By contrast, there is no rule of inference or axiom which allows the probabilistic method to prove existence constructively, or to constructively prove that probabilistic algorithms produce existence proofs, or anything along these lines. You simply cannot prove that there are examples of a class of object from the fact that there is a probabilistic algorithm to construct it, unless you already accept that proposition, either as an axiom, or from other premises.

Of course, one might adopt a philosophical position intermediate to constructivism and the classical approach to existence, and say that what one wants is not constructions per se but construction-schema which are allowed to fail with any probability less than one; that would make any probabilistic construction "schematic", if not completely constructive. Where one wishes to draw the line, to say that they find an existence proof "satisfactory", ultimately depends on how much intuition (in a non-philosophical sense) they wish to gain from proofs.


Is it possible to make data structure that will find MEX and support modification queries Let's say we have given array of $n$ elements, now we want to create data structure that will allow us to get the MEX of its elements, MEX (Minimum EXcluded) meaning the smallest positive integer that is not present in the set. More info from wikipedia. The data structure should also support insert and remove elements from itself.
In other words, we have given a multiset with $n$ elements, we want to find its MEX, but we should support removing and adding elements.
What I was thinking was that we should first process the elements on some way, and then when adding new element in the set we should check if it is equal to the MEX, but there are many cases to worry about, so I couldn't come to complete solution.
The data structure should support both the queries/updates in $O(\log N)$ or similar time-complexity classes.

Method 1
You can also use a bit trie — this is a trie made of bits of your numbers, thus it is represented as a binary tree (since there are only two types of bits — 0 and 1), and its depth is $\mathcal{O}{(log(n))}$.
When you add a number, you mark the vertex that representing this particular number as a full binary tree, and then you recursively go over its parents marking them as full binary trees if their left and right children are both full binary trees as well.
When you remove a number, you unset the "full binary tree" mark and do so for all its parents.
When you want to get MEX, you should do the DFS towards $x$, avoiding visiting subtrees which are marked as full (because there are no free values in such subtrees) and attempt to visit a left subtree first if you are allowed to by the x restriction.
class MEX {
  struct MEXNode {
    MEXNode *children[2];
    bool is_full = false;
    int cnt = 0;

  public:
    MEXNode() {
      children[0] = nullptr;
      children[1] = nullptr;
    }
  };
private:

  inline MEXNode *nonnull(MEXNode *& n) {
    if (!n) n = new MEXNode();
    return n;
  }

  void insert(int val, int level, MEXNode *n) {
    if (level == -1) {
      n->cnt++;
      n->is_full = true;
      return;
    }

    int cur_bit = (val & (1 << level)) >> level;
    insert(val, level - 1, nonnull(n->children[cur_bit]));

    n->is_full = nonnull(n->children[0])->is_full && nonnull(n->children[1])->is_full;
    n->cnt = nonnull(n->children[0])->cnt + nonnull(n->children[1])->cnt;
  }

  // Remove an integer from the set
  void remove(int val, int level, MEXNode *n) {
    if (level == -1) {
      n->cnt--;
      n->is_full = n->cnt > 0;
      return;
    }

    int cur_bit = (val & (1 << level)) >> level;
    remove(val, level - 1, nonnull(n->children[cur_bit]));

    n->is_full = nonnull(n->children[0])->is_full && nonnull(n->children[1])->is_full;
    n->cnt = nonnull(n->children[0])->cnt + nonnull(n->children[1])->cnt;
  }

  // Find the minimum element >=x that isn't present in the set
  int get(int val, int level, MEXNode *n) {
    if (n->is_full) {
      return -1;
    } else if (n->cnt == 0) {
      return val;
    }

    int cur_bit = (val & (1 << level)) >> level;
    int ans = get(val, level - 1, nonnull(n->children[cur_bit]));
    if (cur_bit == 0 && ans == -1) {
      ans = get((val >> level << level) | (1 << level), level - 1, nonnull(n->children[1]));
    }

    return ans;
  }

  MEXNode root_node;
public:

  void insert(int x) {
    insert(x, 31, &root_node);
  }
  void remove(int x) {
    remove(x, 31, &root_node);
  }
  int get(int x) {
    return get(x, 31, &root_node);
  }
};

Method 2
Create a set of intervals $S$. If the interval $[l, r]$ is present in $S$, that means that the elements $l, l + 1, l + 2, \dots , r$ are in $S$.
Adding an element $x$ is handled like this:
If $[whatever, x - 1]$ is present in the set, remove it and add $[whatever, x]$. Likewise, if $[x + 1, whatever]$ is in the set, remove it and add $[x, whatever]$.
Removals are handled in this way:
Find the interval containing x. Split it into two intervals $[start, x - 1]$, and $[x + 1, end]$.
MEX queries are handled similarly:
Find the interval containing $x$ and output $end + 1$. This can be implemented using 2 std::set<std::pair<int, int>> in C++.
The first set indexes pairs by the first element (i.e. left end), and the second one by their second element (i.e. right end)
class MEX {
  typedef std::pair<int, int> interval;
  std::set<interval> s[2];
  std::multiset<int> values;
  void insert_pair(interval p) {
    auto[x, y] = p;
    if (x > y) std::swap(x, y);
    s[0].insert({x, y});
    s[1].insert({y, x});
  }
  void remove_pair(interval p) {
    auto[x, y] = p;
    if (x > y) std::swap(x, y);
    s[0].erase({x, y});
    s[1].erase({y, x});
  }

  std::optional<interval> is_end(int x, bool left) {
    int idx = left;
    auto it = s[idx].lower_bound({x, 0});
    if (it != s[idx].end() && it->first == x)
      return *it;
    else
      return std::nullopt;
  }

 public:
  void insert(int x) {
    bool ok = values.find(x) == values.end();
    values.insert(x);
    if (!ok) return;
    auto p1 = is_end(x - 1, true);
    auto p2 = is_end(x + 1, false);
    if (p1 && p2) {
      interval i = {p1->second, p2->second};
      remove_pair(*p1);
      remove_pair(*p2);
      insert_pair(i);
    } else if (p1 && !p2) {
      interval i = {p1->second, x};
      remove_pair(*p1);
      insert_pair(i);
    } else if (!p1 && p2) {
      interval i = {x, p2->second};
      remove_pair(*p2);
      insert_pair(i);
    } else if (!p1 && !p2) {
      interval i = {x, x};
      insert_pair(i);
    }
  }
  void remove(int x) {
    values.erase(values.find(x));
    if (values.find(x) != values.end()) return;
    auto it = s[1].lower_bound({x, 0});
    if (it->first != x && it->second != x) {
      interval p1 = {it->second, x - 1};
      interval p2 = {x + 1, it->first};
      remove_pair(*it);
      insert_pair(p1);
      insert_pair(p2);
    } else if (it->first != x && it->second == x) {
      interval p = {x + 1, it->first};
      remove_pair(*it);
      insert_pair(p);
    } else if (it->first == x && it->second == x) {
      remove_pair(*it);
    } else if (it->first == x && it->second != x) {
      interval p = {it->second, x - 1};
      remove_pair(*it);
      insert_pair(p);
    }
  }
  int get(int x) {
    if (values.find(x) == values.end()) return x;
    auto it = s[1].lower_bound({x, 0});
    return it->first + 1;
  }
};

Usage

MEX mex;
mex.insert(int);
mex.remove(int);
mex.get(int); // Find the minimum element >=x that isn't present in the set

Reference
Sample Problem
Solution using Method-1
Solution using Method-2


Formalism for unambiguous context-sensitive languages? I know that there are some languages that are unambiguous but not context-free (this is a good fact). Is there any kind of formalism for describing unambiguous context-sensitive languages? Even better yet, is there a parsing algorithm for unambiguous context-sensitive languages?

Actually, I found something close enough to what I want. They're unambiguous boolean grammars and they're both unambiguous and strictly more powerful than context-free grammars. Other people may find this useful, so I decided to share it.


Network Flow - Minimum flow in a network I have a directed graph G=(V,E) with a source s$\in V$ and a sink t$\in V$. There is a minimum capacity (lower bound) l $_{e}$ for each edge in G. There are no upper bounds on the edges.

In a course that I took, the professor told that to find a minimum flow -

1) We need to assign a large capacity to all edges and find flow f
2) Construct G $_{1}$ where all edges are reversed and each edge has capacity f$_{e}$ - l$_{e}$
3) We need to then find the max flow from t to s in G$_{1}$ that is f$_{1}$
4) Then, the  minimum flow in G is  f-f$_{1}$

  My question is-  Why can't we find a s to t path in G with the least
  value of  l$_{e}$. The least value of l$_{e}$ would be the minimum
  flow that could be pushed through the network?

Imagine you have the following graph (in red are the minimum capacities):

The $(s,t)$-path with the lowest flow demand needs $1$ unit of flow, but the minimum flow is $4$. And the $(s,t)$-path with minimum sums of capacities has a sum of $2$, so this also doesn't work.


Moore's law and Clock Speed This figure says according to moore's law number of transistors doubles about two years. but clock speed, power flattening after given stage. can anyone describe the reasons this flattening in clock-speed. Why can't we increase the clock speed more and more?

There are two different "laws" being graphed here, Moore's law, and Dennard scaling.  Moore's law is an economic observation, made by Gordon Moore in 1965, that predicts that the number of transistors on a die will tend to double about every two years.  It does not seem to be slowing down (yet).  While there are reasons to believe that transistors will stop scaling down soon (14nm is 140 Angstroms (about the width of 140 hydrogen atoms)) it may be possible to continue Moore's law scaling for some time, either by making bigger chips (what Moore originally predicted) or by stacking multiple layers of transistors in the 3rd dimension.

Dennard Scaling, on the other hand, is an observation, made by Robert Dennard in 1974 that every time you scale down the width of a CMOS gate by a factor of 2, you can reduce both supply voltage and the threshold voltage by a factor of 2, the clock frequency can improve by a factor of 2, and the power density will stay constant.  (Or you can scale down the voltage by less than 2, and you'll get a better than 2x clock frequency boost, but an increase in power.)  When Dennard's observation was made a CMOS transistor was about 5 micron = 5000 nm wide.  (So we've scaled transistor widths by a factor of about 360 in about 40 years.)

The limit that showed up in the early 2000s has to do with threshold voltage.  Clock frequency (at a particular transistor size) is at best proportional to
$V_{dd} - V_{th}$ (supply voltage minus threshold voltage), but as you scale $V_{th}$ down leakage current (and power) increases exponentially.  That was fine from 1974 to about 2000 because $V_{dd}$ was much larger than $V_{th}$.  (In 1974 $V_{dd}$ was usually about 12V.)  So we could hold $V_{th}$ at around a volt or so, and just change $V_{dd}$.  But now with $V_{dd}$ around 1.3V and $V_{th}$ around .5V, we can't scale voltage much anymore (without dramatically increasing leakage power.)


Trading Auction - Need help with calculating price / quantity of restricted underlying securities for matching I'm having some difficulty with implementing a non-brute force algorithm for solving the following Problem. If I can get something even close to O(N^3) i'd be happy at this point.

Auction: https://www.investopedia.com/terms/a/auctionmarket.asp

I have an algorithm in place that can do a generic Auction (accumulating bids and offers over a fixed period of time, leading up to an event whereby bids and offers are matched to determine a reference price (the price securities are sold at in the auction)however we've just implemented a level of complexity that is throwing me for a loop.

We have a security with underlying shares that contain restrictions on who can own them. During an auction, we need to ensure that buyers can only buy shares they're allowed based on the underlying restriction.

Example:

Security: Foo
-Class A Shares
-Class B Shares
-Class C Shares

Buy Orders

John can only buy Class A and Class B (Wants to buy 500 at $1.50)
Sally can only buy Class B, and Class C (Wants to buy 300 at $1.52)
Joel can buy any class. ((Wants to buy 200 @ 1.49)

Sell Orders

Xavier owns 500 (200 Class A, 300 class B) and is selling 400 at $1.42
Jennifer owns 1000 shares (800 Class B, 200 class C) and is selling 650 at $1.50
Martha owns 1500 shares (300 Class A, 1200 class C) and is selling 400 at $1.52

When a user puts in  Buy / Sell auction order, they don't care what class of shares they're buying or selling, we can determine what they are buying or selling.

The goal is trying to find the price point where the most shares can be sold, while making sure that we're filling all orders that can be filled.

I've ran through multiple scenarios on calculating it from a price perspective, and the underlying class perspective, calculating the # of shares that can be sold at each price point, but I'm at a blank as each way I do it, i find I'm missing shares that could be traded.

Example: The following illustrates (when we have a correct price) that we also need to match buyer & seller  using the most restricted / least tradable security so we match those who can't trade with much first, then go for those that are less restricted.

The above isn't hard to solve, it's getting to that point, to figure out the best price and tradeable amount.

Any thoughts or ideas on this?

I would do this iteratively going through buyers ready to pay the highest price. I assume you can have partial fills if buyer and seller quantity don't match?

Step 1. Sort the buyers with MAX price at the top.
Step 2. Sort the sellers with LEAST price at the top.
Step 3. Take the topmost buyer from step 1 and try to fill its order, taking into consideration any restrictions, with a matching seller from the top. This will be your reference price. To match the seller you would need to traverse from top, comparing one by one to see which seller matches.
Step 4. Update the seller and buyer quantities based on the match in step 3.
Step 5. Repeat from step 1.

Hope that helps. Have a wonderful day!


Which architecture do modern computers use? Is it one of:

Harvard
Modified Harvard
von Neumann

Or are they antiquated models that modern computers are only loosely based on?

If you asked Intel or AMD what would they say?

Modern general-purpose high-performance processors use separate instruction and data caches, and so could be classified as modified Harvard even though they use a unified address space. (Some microcontrollers—usually to provide extra memory or protection without a memory protection unit—use a Harvard architecture in which data and code use separate address spaces.)

x86 might be considered a little more nearly "pure" von Neumann than some other ISAs in that self-modified code is guaranteed to be handled properly if a jump is used. Many other ISAs require an instruction synchronization instruction and may require explicit invalidation of any modified memory from the instruction cache (i.e., the instruction cache is not necessarily coherent).

Cross-modified code is somewhat more complex; even x86 requires a synchronizing instruction.


Is an inﬁnite union of context-free languages always context-free? Let $L_1$, $L_2$, $L_3$, $\dots$ be an inﬁnite sequence of context-free languages, each of
which is deﬁned over a common alphabet $Σ$. Let $L$ be the inﬁnite union of $L_1$, $L_2$, $L_3$, $\dots $;
i.e., $L = L_1 \cup L_2 \cup L_3 \cup \dots $.

Is it always the case that $L$ is a context-free language?

The union of infinitely many context-free languages may not be context free. In fact, the union of infinitely many languages can be just about anything: let $L$ be a language, and define for every $l \in L$ the (finite) language $L_l = \{ l \}$. The union over all these languages is $L$. Finite languages are regular, but $L$ may not even be decidable (and thereby definitely not context-free).

The closure properties of context-free languages can be found on Wikipedia.


Why do compute time complexity for algorithms? I read about Big-O notation with modular arithmetic. So, Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform. Thus the amount of time taken and the number of elementary operations performed by the algorithm differ by at most a constant factor. Some algorithms have a worst-case time of $O(n)$ or $O(n^2)$ or $O(n^3)$.

What I want to know is what is the best time complexity of an algorithm? And why?

The problem you are describing is indeed a shortcoming of asymptotic notation. Asymptotic notation has several advantages:

It doesn't depend as much on the underlying computation model. For example, the microprocessor executing the compiled code shouldn't affect the running time by more than a constant.
It avoids cumbersome exact results, for example instead of $n^2 + 3.5n\log n + 700\log n\lfloor \log\log n \rfloor$ we can write simply $O(n^2)$ (or even $\Theta(n^2)$).
In many cases it is hard to analyze exactly the running time (even ignoring the first issue), but easy to come up with asymptotics. Standard examples are recursive algorithms. In those case, however, it is often possible to come up with first-order estimates, that is, perhaps we can say that the running time satisfies $T(n) \sim 2n^2$, which is more accurate than $T(n) = \Theta(n^2)$.
Practically speaking, in many cases the constants hidden by the big O notation are "small" or at least "reasonable", and therefore for $n$ which is not too small, a $\Theta(n)$ algorithm will usually be faster than a $\Theta(n^2)$ algorithm.
Big O estimates function as ball park heuristics, which allow us to guess which algorithm is better or which part of an algorithm needs optimization the most. If in doubt, however, it is better to use profiling.

On the other hand, in some cases the problem you're indicating is serious. A classical case is fast matrix multiplication, where the trivial $O(n^3)$ algorithm often beats Strassen's $O(n^{\log_2 7})$, and always beats all other algorithms (which have better asymptotic running time).

Summarizing, there is no easy answer. Asymptotic notation is a good model of reality in many cases, but not always. Still, it is useful since it is concise and allows quick comparison between different algorithms.


Method for Creating Any Unambiguous Grammar? I'm in an undergraduate class where we're studying formal grammars right now. I asked my teacher if there was any known set of rules for creating context free grammars that

Was guaranteed to produce an unambiguous grammar.
Allows for the creation of any possible unambiguous grammar.

I am well aware that determining whether a grammar is ambiguous is undecidable. I'm not sure if the above stated idea is reducible to that, but after fiddling around with it a bit, I couldn't think of a method for making such a reduction. That said I'm really no expert at reductions or grammars. I tried googling for a while, but I only found pages about undecidability. Does anyone know?

No, and there is indeed a reduction to the undecidability of ambiguity.

First, note that ambiguity is (for context-free grammars) semi-decidable: just keep generating words by different left-derivations and say "ambiguous!" when you first find a word you've seen before.

Now, the method you are proposing allows to semi-decide unambiguity. You effectively look for a computable enumeration of all unambiguous grammars. You just generate grammars until you find your given grammar and answer "unambiguous!".

Since semi-decidability and co-semi-decidability imply decidability, this contradicts what you already know. Hence, there can be no "set of rules" as you propose.


What are the strongest known type systems for which inference is decidable? It's well known that Hindley–Milner type inference (the simply-typed $\lambda$-calculus with polymorphism) has decidable type inference: you can reconstruct principle types for any programs without any annotations.
Adding Haskell-style typeclasses seem to preserve this decidability, but further additions makes inference without annotations undecidable (type families, GADTs, dependent-types, Rank-N types, System $\omega$, etc.)
I'm wondering: what is the strongest known type system with completely decidable inference? It's going to lie somewhere between Hindley–Milner (completely decidable) and dependent-types (completely undecidable). Are there aspects of DTs which can be added which preserve inference decidability? What research has been done to see how far this can be pushed?
I realize that there is not a single strongest system: that there are likely infinite small, incremental changes that can be added to HM keeping inference. But there are likely a few practical candidates of systems that have been discovered.
Edit: given that there is no "strongest" system, I will accept an answer that outlines the notable systems that extend Hindley–Milner with decidable inference. Examples could be Liquid Types, Rank-2, etc.

[EDIT: Voilà a few words on each]

There are several ways of extending HM type inference. My answer is based on many, more or less successful, attempts at implementing some of them.
The first one I stumbled upon is parametric polymorphism. Type systems trying to extend HM in this direction tend toward System F and so require type annotations. Two notable extensions in this direction I came across are :

HMF, it allows type inference for all System-F types, which means that you can have universal quantification "in the middle" of a type, their appearance is not implicitly situated at the highest scope like for HM polymorphic types. The paper clearly states that no clear rule exists as to how many and where type annotations may be needed. Also the types being those of System F, terms usually don't have a principal type.
MLF is not only an extension of HM, it's also an extension of System F that regain the principal type property of HM by introducing a kind of bounded quantification over types. A comparison has been made by the authors, MLF is strictly more powerful than HMF and annotations are only required for parameters used polymorphically.

Another way of extending HM is through variation of the constraint domain.

HM(X) is Hindley-Milner parameterised over a constraint domain X. In this approach, HM algorithm generates the constraints that are sent to a domain solver for X. For the usual HM, the domain solver is the unification procedure and the domain consists of the set of terms build from the types and the type variables.
Another example for X could be constraints expressed in the language of Presburger arithmetic ( in which case type inference / checking is decidable ) or in the language of Peano arithmetic ( no longer decidable ). X varies along a spectrum of theories, each with its own requirements regarding the amount and localisation of type annotations needed and ranging from not at all to all of them.
Haskell's type classes are also a kind of extension of the constraint domain by adding type predicates of the form MyClass(MyType) ( meaning that there exists an instance of MyClass for the type MyType ).
Type classes preserve type inference because they are basically an (almost) orthogonal concepts they implements adhoc polymorphism.
As an example, take a symbol val of type val :: MyClass a => a for which you can have instances MyClass A, MyClass B etc. When you refer to that symbol in your code, it's actually because type inference is already performed that the compiler can infer which instance of the class to use. This means that the type of val depends on the context in which it is used. That's also why running a single val statements leads to an ambiguous type error : the compiler can't infer any type based on the context.

For more advanced type systems like GADTs, type families, Dependent types, System (F)ω, etc., type are not anymore "types" they become complex computational objects. For example it means that two types not looking the same are not necessarily different. So type equality becomes not trivial ( at all ).

To give you an example of the actual complexity let's consider the dependent type of list : NList a n where a is the type of objects in the list and n is its length.
The append function would have type append :: NList a n -> NList a m -> NList a (n + m) and the zip function would be zip :: NList a n -> NList b n -> NList (a, b) n.
Imagine now we have the lambda \a: NList t n, b: NList t m -> zip (append a b) (append b a). Here the first argument of zip is of type NList t (n + m) and the second of type NList t (m + n).
Almost the same, but unless the type checker knows that "+" commutes on natural numbers, it must reject the function because (n + m) is not literally (m + n). It's no longer about type inference / type checking, it's about theorem proving.

Liquid types seem to be doing some dependent type inference. But as I understand it, it's not really dependent type, more something like usual HM types on which additional inference is made to compute static bounds.

I hope this helps.


Help with recursive algorithm analysis Given this algorithm:

int foo(int num) {
    if (num == 0){
        return 0;
    } else {
        return 1 + foo(num/10);
    }
}

Me and my friend are debating how you should treat "N" as the size of the input.

If I'm considering N to be the number of digits: then my analysis will say O(n)

However, if I'm considering N to be the actual value of the input to the function I will get a different runtime representation and different analysis with the conclusion of O(log n) (base 10)

Me and my friend cannot understand why the second approach is wrong, so far we got explanations like : "The algorithm is cutting the number digit by digit so your N is the number of decimal digits of the number"

However, log (base 10) of the actual value will give me pretty much the same result.

Why is the second approach is wrong ?

There is nothing inherently wrong about either approach, however the first one is overwhelmingly more common. The reason is that complexity analysis takes place in an asymptotic setting with respect to the size of input.

Computers are machines that perform meaningless operations on meaningless symbols, it is your job to find meaning in the computation. Therefore,
determining what the size is depends on some agreed upon definition of what constitutes a reasonable symbolic representation of the input. Formally, you would have to define how the machine that executes your algorithm works in order to be able to talk about complexity at all, but in this context it is sufficient to assume that any representation that uses a finite set of symbols is acceptable.

There are many ways - all in principle equally valid - to represent the natural numbers. For instance, you might say that $0$ is represented by the string x, $1$ by xx, $2$ by xxx and so on. In this case the size of input would be proportional to the numerical value.

However most of us would agree that representing numbers in some base $b$ - which is certainly acceptable as it requires at most $b$ symbols - is more reasonable; in this case the size of the input is proportional to the number of digits required to write the representation of the number, which is itself proportional to the logarithm of the numerical value.

Taking numbers to have size proportional to their logarithm is also more consistent with the way we treat other objects. If the input of an algorithm is an array, the size of the array is the number of cells (and not the number of different arrays of that length), similarly for graphs, matrices and other mathematical objects.


The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements about a pushdown automata (PDA) which accepts by empty stack, as:

1. $n$, the total length of the input, is surely an upper bound on the number of states and stack symbols.

2. One rule could place almost n symbols on the stack.

The following statements were made while the authors were about to make some notes about the decision properties of CFLs(Context Free Languages)

Now here are some points by which I am possibly able to contradict the claim rather than proving it correct.

Suppose $n$, is the total length of the input, but as per the design of the PDA it might so happen that to accept the input string all the states of the PDA is not involved, so by this we can't say that $n$ is an upper bound on the number of states the PDA has.
Though the PDA accepts by empty stack, it might so happen that a transition function adds more than $n$ elements on the top of the stack, but at the end on consuming the $n$ input symbols we can stay on the particular state and use epsilon transitions to just remain in the same state and pop the elements from the stack till it becomes empty. So how can we say that $n$ is an upper bound on the number elements on the stack? We arrive at a contradiction...

I don't understand where I am making the mistake, because the same statements are written in the 3rd edition of the book without any changes being made from the second edition which makes it probable that the statement is correct.

I have attached the corresponding portion of the text below:

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

The input to an algorithm which converts a PDA to a CFG is the PDA, and the size of the input -- the metric stick for the algorithm's complexity -- is the size of the *PDA". That's what the authors intend n to be.

How does one measure the size of a PDA? Simple: you write the PDA out as a string in some PDA definition language, and count symbols in the description. That's a completely fair procedure, because in order to call the conversion algorithm on the PDA, it's necessary to give the converter an input which represents the PDA.

Given that definition, the claims are not at all surprising. Every state and every alphabet symbol must be present at least once in the PDA description, so the size if that description is an upper bound. Similarly, it is possible that most of the description of the PDA is the description of a single rule, which could push almost n symbols.


Why use joint trees in Graphical Models? I am wondering why some methods transform the underlying graphical model (Bayesian Network for example) to a junction tree¹? What are the advantages?  Also what are the limitations?

I believe it's for computational purposes. If that's the case under what circumstances it is not recommended to transform the underlying DAG to joint-trees?

Edit: speaking about graphical models in general (whether they are probabilistic or not), is there some guidelines when to transform them i.e. decompose them?

1 Junction trees are also known as tree decomposition.

I view junction trees as basically an implementation/analysis tool for doing exact MAP and marginal inference in graphical models.  They are needed so that you can safely localize the effects of of maxing or summing (in the case of MAP and marginal inference) out a variable.

When wouldn't you use a junction tee?  Well, that's the same case as when you wouldn't do exact inference in your model.  Why wouldn't you do exact inference?  In general, because it can be expensive; it's exponential in the treewidth of your junction tree.


Simple discrete math problem: A and B in 3CNF I need to write (A and B) in 3CNF, and for whatever reason, I can only come up with (A or B) in 3CNF (A OR B OR X) AND (NOT(X) OR A OR B). Any help is greatly appreciated!

How about $(A \lor A \lor A) \land (B \lor B \lor B)$?

If you need three different variables in each clause, you can use

$$
(A \lor x_1 \lor x_2) \land (B \lor x_1 \lor x_2) \land \\
(\lnot x_1 \lor y_1 \lor z_1) \land (\lnot x_1 \lor y_1 \lor \lnot z_1) \land
(\lnot x_1 \lor \lnot y_1 \lor z_1) \land (\lnot x_1 \lor \lnot y_1 \lor \lnot z_1) \land \\
(\lnot x_2 \lor y_2 \lor z_2) \land (\lnot x_2 \lor y_2 \lor \lnot z_2) \land
(\lnot x_2 \lor \lnot y_2 \lor z_2) \land (\lnot x_2 \lor \lnot y_2 \lor \lnot z_2).
$$


Identifying a starting point for maximum coverage I have 10,000 sequentially numbered items I wish to characterize. For each item, I created a list of the other items I think might have a similar characteristic.

i.e.

Item 1: [2,4,7,8,9,...,9489] (list contains 250 items)
Item 2: [1,4,13,23,...,9424] (list contains 12 items)
Item 3: [1,2,4,7,...,9489] (list contains 140 items)
Item 4: [1,3,7,9,...,9211] (list contains 250 items)
Item 5: [1,3,7,9,...,9221] (list contains 250 items)
Item 6: [1,2,7,25,...,9248] (list contains 241 items)
Item 7: [4,5,6] (list contains 3 items)

If I only have time to test 50 items, How might I choose which items to test so that the maximum number of items is represented? The identified similarity is not necessarily bi-directional - notice item 7's list contains 4,5,6 but not 1 and 3(which both have 7 in their list).

Some lists may be very similar or even identical, as seen in items 4 and 5. Testing both 4 and 5 would not achieve the maximum coverage.

It sounds like you want to select a set of 50 lists whose union contains as many elements as possible.  This is the maximum coverage problem, which is NP-complete, but there are standard techniques that can be used to get decent-quality solutions (there is an approximation algorithm using a greedy algorithm, and a formulation as ILP).


No. of subsets whose element multiply to give a square number I have been given an array whose elements lie between [1,70] and the size of array [1,10^5].

I have to find the total number of subsets whose all elements multiply to give a perfect square number.

Since, count of subsets can be very large, I have to give the
 ans mod (10^9 + 7).

How should go on to solve this problem ?

One hint given to me is to utilise the range of value that every array element hold which is [1,70] and total no. of prime numbers between these [1,70] are 19.

Factor each element $x_i$ to produce a vector $v_i$ of the powers of all primes which are at most 70. The product $\prod_{i \in S} x_i$ is a perfect square if every prime appears in an even power, that is, if $\sum_{i \in S} v_i = \mathbf0 \pmod{2}$. This suggests considering $v_i$ as a vector over $\mathbb{Z}_2$ (the integers mod 2). You are now given a matrix, and wish to know how many subsets of rows sum to the zero vector. This is a problem in linear algebra, and the answer depends on the rank of the matrix: if the matrix has $n$ rows, $m$ columns, and rank $r$, then the answer is $2^{n-r}$.

Here is a worked out example for $1,2,4,5,8$. In this case there are two relevant primes: $2,5$. The full matrix (before reducing modulo 2) is
$$
\begin{bmatrix}
0 & 0 \\ 1 & 0 \\ 2 & 0 \\ 0 & 1 \\ 3 & 0
\end{bmatrix}
$$
After reducing modulo 2, the matrix becomes
$$
\begin{bmatrix}
0 & 0 \\ 1 & 0 \\ 0 & 0 \\ 0 & 1 \\ 1 & 0
\end{bmatrix}
$$
This matrix has full rank (rank 2), and so the answer is $2^{5-2} = 8$.

Here are the 8 subsets:
$$
\emptyset \\
\{1\} \\
\{4\} \\
\{1,4\} \\
\{2,8\} \\
\{1,2,8\} \\
\{2,4,8\} \\
\{1,2,4,8\}
$$

As noted in the comments, you might want to disallow the empty set (which multiplies to 1). In this case, the formula becomes $2^{n-r}-1$.


Why are four context sensitive grammar (CSG) rules needed to represent AB -> CD? In Wikipedia of Kuroda normal form, it says

  A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB → CD is replaced by four context-sensitive rules AB → AZ, AZ → WZ, WZ → WD and WD → CD.

Why are four rules needed here? Aren't three rules: AB → AZ, AZ → CZ, CZ → CD enough?

With three steps we are not forced to complete all the steps before continuing interacting with other context around the two initial letters.

In fact, Révész himself answers this question, in his Introduction to Formal Languages at archive.org, with the following example.

  Note that three rules like AB → A'B, A'B → A'D, and A'D → CD are
  not enough to replace the rules AB → CD. For example, if we have the
  rules S → AB, B → DE, AB → CD in the original grammar, then this
  replacement makes the derivation

  S ⇒ AB ⇒ A'B ⇒ A'DE ⇒ CDE

  possible, though CDE is not derivable in the original grammar. Such
  parasitical derivations are often quite difficult to avoid when we are trying
  to transform a grammar into an equivalent one.


Poker with Bluffing (game theory) I'm doing a self-study of Game Theory Evolving by Gintis, and am stuck on problem 4.16 "Poker with Bluffing".

The first question asks "Show that Ollie has 64 pure strategies and Stan has 8 pure strategies.". But no matter how I try to approach this, I can't get more then 4 strategies for Stan!

Here is the game tree for the game in question:

The question marks (?) in the figure mean that the payoff depends on who has the higher card.

Here is the game description:

Two players, each with a deck of three cards: H (high), M(medium) or L (low).
Each puts \$1 in the pot, chooses random card
Ollie (P1) either stays or raises
Stan (P2) simultaneously also stays or raises
If both raise/stay - highest card wins the pot (tie - they take their money back)
If Ollie raises, Stan stays  Ollie gets the \$3 pot.
If Stan raises and Ollie stays - Ollie gets another chance:
-> Drop - Stand wins the \$3 pot
-> Call - add \$1 to the pot.

Why does Stand have 8 pure strategies?

Stan has two pure strategies for each type of card. Since there are three types of cards (H, M, L), in total he has $2\times 2\times 2 = 8$ strategies. Here is a list of them:

Always stay.
Always raise.
Stay only if H.
Stay only if M.
Stay only if L.
Raise only if H.
Raise only if M.
Raise only if L.


Maximum degree of concurrency in task dependency graphs I've been researching ways of modeling and executing tasks which are dependent on each other (but in an acyclic way) and came up with task graphs. But the question that's bugging me is how can I find out the maximum degree of concurrency in a given task graph.

In my case, I'm talking of a relatively small graph, around 100 nodes, but nodes, representing tasks, are long running tasks. So the occuracy, more then complexity of such an algorithm would matter.

Assuming I came up of such a degree, the second problem, is how should I distrubute tasks? I've read about topological sort, and transforming the result in a list of sets, with each set being run in parallel. But again, I suspect if this is the best approach.

If you turn an activity-on-node task graph into a partial order (by taking the transitive closure), then the largest independent set of tasks is what you are looking for.

(Taking a topological sort, as suggested in another answer, does not work in general.  Consider the series-parallel task graph $((a|b)c)|(d(e|f))$, where $\alpha|\beta$ means parallel composition of task graphs and $\alpha\beta$ means every task in task graph $\alpha$ precedes every task in task graph $\beta$.  Here $\{a,b,e,f\}$ is the largest independent set, yet the topological sort will produce $\{a,b,d\}$.)

Although finding largest independent sets is NP-complete in general, it can be done quickly for partial orders.  This starts by noting the equivalence of an independent set in a poset with a set of witnesses that realise the width of the poset, and applying König's theorem to compute the witnesses by a perfect matching.

Some of these basic algorithms are already part of software toolkits, like the Graph CPAN module for Perl, and the Boost Graph Library for C++.


Soundness and completeness w.r.t. programming languages I'm studying programming languages (more specifically type systems) and came across a concept I couldn't quite wrap my head around: soundness and completeness.

I'm taking a class, and according to my instructor:

  Soundness is an analyzer's ability to prove the absence of errors. If a program is accepted by an analyzer, then the program is guaranteed to be safe.

  On the other hand, completeness is an analyzer's ability to prove the presence of errors. If a program is rejected, then that program has errors.

An example that I thought of is: If an analyzer is designed to accept all programs, does this mean the analyzer's system is sound but incomplete? I'm not quite sure if my reasoning is correct.

I've taken a look at other answers on this community:

Is there a relationship between “sound and complete” in logic and “type safety” in PLs? and

Example of Soundness & Completeness of Inference

but still am not quite sure how the logical concepts apply to type systems of programming languages.

Would anyone be kind enough to explain the differences?

Thank you.

I'll focus on your question:

  An example that I thought of is: If an analyzer is designed to accept all programs, does this mean the analyzer's system is sound but incomplete? I'm not quite sure if my reasoning is correct.

No, your reasoning is not correct. Let's take the definition your instructor gave you:

  Soundness: [...] If a program is accepted by an analyzer, then the program is guaranteed to be safe.

If a sound analyzer accepts every program, by definition every program must be safe. This is not the case -- so a sound analyzer must not accept everything.

  Completeness: [...] If a program is rejected, then that program has errors.

By definition, the always-accepting analyzer is complete: since it accepts everything, it rejects nothing, so all programs it rejects (i.e., none) have errors. This follows because from a false hypothesis ("a program is rejected") we can logically infer anything at all (including "the program has errors").

So, the always-accepting analyzer is complete, but not sound.

By contrast, an always-rejecting analyzer would be sound but not complete.

My preferred way to describe soundness and completeness is pretending we have an analyzer which, given an input program, returns "SAFE" (technically, accepts) or "NOT SAFE" (technically, rejects). A sound analyzer is one that can be trusted when it says "SAFE". A complete analyzer is one that can be trusted when it says "NOT SAFE".

A sound & complete analyzer can always be trusted, so (if it always halts) it is a decider for program safety. (Actually, by Rice's theorem, such a perfect analyzer can not exist.)

A sound but not complete analyzer, can be trusted only on "SAFE" answers. So, we can pretend it reliably answers "SAFE" or "DO NOT KNOW". (Indeed, "NOT SAFE" answers can not be trusted, so they actually mean "DO NOT KNOW")

A complete but not sound analyzer, can be trusted only on "NOT SAFE" answers. So, we can pretend it reliably answers "NOT SAFE" or "DO NOT KNOW". (Indeed, "SAFE" answers can not be trusted, so they actually mean "DO NOT KNOW")


Interactive example of Dynamic scoping and evaluation order of expressions Given the following (arbitrary language, although I think it is close to Algol 60) program:

program main;                               // A main parent level
  var i : integer;                          // A 'global' variable

  (* Note that all parameters are passed by value here *)

  function f1 (j : integer) : integer;      // A Child function
  begin { f1 }
    i := i + 3;
    f1 := 2 * j - i;
  end; { f1 }

  function f2 (k : integer) : integer;      // Another Child function, same level as f1
    var i : integer;                        // Here, there is a variable that is declared
  begin { f2 }                                 // but no value assigned
    i := k / 2;
    f2 := f1(i) + f1(k);
  end; { f2 }

begin { main }                              // Running/Calling/Executing the code
  i := 8;
  i := i + f2(i);
  writeln(i);
end. { main }

How would you trace the values of variables throughout the program when it is interpreted using Dynamic scoping of free variables, when the arguments appearing in expressions  are evaluated left to right, and when they are evaluated right to left, so that the user can watch what happens

I have created a JS plnkr for Static Scoping with Left to Right evaluation
and another for Static Scoping with Right to Left evaluation.
Feel free to adapt these answers (if possible) for Dynamic Scoping, with L->R and R->L evaluation.

I chose plnkrs because I knew I could get the Static/lexical side using JS, but am unsure of how to make it happen dynamically or in another interactive environment (preferably not one I have to install).

I learn a bit slower on some problems like this where the values are asked of the output, but don't show the value states throughout the program, and trying to get a better understanding, especially in an example I can play around with interactively, as the book examples are really bad.  In the code above, it also gets challenging, because it appears that the variable i in line 2 is allocated, but would be undefined.   But that may be my imperative/functional brain making it more complicated than it is...

I do not know other environments in existing languages, whether
statically or dynamically scoped. Also, that would be language
specific, hence off topic here.

Without a system environment, the way I would do this would be to
insert print statement in my program, either by hand if I am poor, or
with a some programmable program transformation system. I actually did
it often a very long time ago for debugging purposes, applying program
transformations I had developed in such a program transformation
system.

Your example is rather simple as the formal parameters j and k are
never modified, so that everything can be assumed to be call by value.
But things can get very hairy when formal parameters get modified in
the function, depending on the parameter passing mode.

I am also a bit surprised that your system gives you the post value
of i in f2 at the beginning rather than at the end of the trace.

You may try to trace the values of variable that are not visible in
the function currently executed, for example by printing them with a
function defined at the right place. But that can only work when the
function uses static scoping.

My basic philosophy is that dynamic scoping is an endless source of
problems because you cannot know what a free variable stands for, as
it may vary from call to call. I know that some people like it and say
it is useful. I will not comment.

Dynamic scoping was invented as a bug in the first Lisp interpreter, in the late fifties.
When they realized what they had done, the beast was out. Scheme
corrected that, but much later.

I am not sure I answered you. But I now realize this question is borderline on this site.


Proving some subsets of a regular languages to be regular languages I have to prove that if a language $L$ is regular then:
a) $NONPREFIX(L)=\{u \in L / $none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \} $ is regular
On this one I think I can divide the words of L in two parts and get it, since regular languages are closed under concatenation, I dont know if this is correct.
And the other one:
b) $NONEXTENSION(L)=\{u \in L / $ $u$ is not a prefix (not $\epsilon$ or $u$) of any element of $L \} $ is regular
In this one I've no idea how to begin.
Any help would be pretty apreciated. Thanks!

a) Proving NOPREFIX(L) is regular :
The idea is simple , for a string w ∈ NOPREFIX(L) , w must be in L , and no proper prefix of w is in L
So , if we have a DFA M for L , we run string w on M , changing M a bit ,  if M enters the accept state before the end of the input , then a proper prefix of w is accepted by L and so we reject , if not and we reach an accept state just by the end input we accept , of course if by the end of w we don't enter an accept state we reject since w is not in L an so not in NOPREFIX(L)
Now you may want to try constructing M' based on the above explanation , then check your answer
Proof :
Let M = (Q,Σ,δ,q0,F) recognising some regular language L ,construct M' = (Q',Σ,δ',q0',F') to recognise NOPREFIX(L) as follows :
Q' = Q
for r ∈ Q' , a ∈ Σ
δ'(r,a) = δ(r,a) , if r is not in F
δ'(r,a) = ∅  , if r  ∈ F
q0' = q0'
F' = F
Hopefully you can see how changes in δ' achieve our purpose , M' simulates M , till it reaches an accept state , if the input ends we accept ( note that w is not a proper prefix of w) since w ∈ L , and we did not encounter any accepted proper prefixes , but if we enter an accept state and the input is not yet finished we reject since this means that we encountered an accepted proper prefix
b) Proving  NOEXTEND(L) is regular
This is an easier one , for a string w ∈ NOEXTEND(L) , we need to make sure that no string wx ∈ L , x ∈ Σ^+ , so for w not to be a proper prefix of a string in L ,we need to make sure that no symbols could be added to w to form a string in L ,
Once again you may want to try M' that recognises NOEXTEND(L)
Proof :
Let M = (Q,Σ,δ,q0,F) recognising some regular language L ,construct M' = (Q',Σ,δ',q0',F') to recognise NOEXTEND(L) as follows :
Q' = Q
δ' = δ
q0' = q0'
F' = { q| there is no path from q to an accept state in F)
M' works exactly as M , when the string end we consider the  final state we reached q , if there is a path from q to any accept state in F ( the accept states of M) , then we reject since this means we can extend w by x to reach a string wx ∈ L , with x being the string of symbols on the path from q to accept state   , and thus w is a proper prefix of some string wx ∈ L , if there is no path from q to an accept state so w cannot be extended to form a string in L and thus we accept


Subset Sum Requirements Consider the following problem.

  Given a set $S$ of integers, a function $f : \mathbb{Z} \to \mathbb{Z}$ and $k \in  \mathbb{Z}$, decide wether there is $X \subseteq S$ such that $f\left(\sum_{x\in X}x\right)=k$.

Is this still considered a subset-sum problem?

For instance, given

$\qquad \displaystyle S=\{ −7, −3, −2, 5, 8\}$

and $k=0$, find a subset $X$ such that $f\left(\sum_{x\in X}x\right)=0$ for $f(y)=-3+y$. In this case, a solution is $X=\{ -3,-2,8 \}$.

It depends on the form of $f$. If $f(x) = x$, then it is identical to subset-sum. If $f(x) = 0$, then it is a trivial problem with an $O(1)$ solution: return $true$. You can possibly define $f$ in other ways to make the question more or less difficult, as well.

See below a mini-complexity zoo corresponding to different choices of $f$:

for $f(x) = c$, the problem is $O(1)$ (return true iff $c = 0$).
for $f(x) = 0$ for $x \geq 0$ and $f(x) = 1$ otherwise, the problem is $O(n)$ (linear search for any number greater than 0)
for $f(x) = 0$ for $x \geq c$, $c > 0$, $f(x) = 1$ otherwise, the problem is no more than $O(n \log n$) (sort the items in the set in descending order, and see if any prefix sums to a working solution)
for $f(x) = ax + b$, the problem is as hard as subset-sum (in an informal sense, and I don't provide a construction to demonstrate the reduction from subset-sum to this... if I'm wrong about this one, please let me know!)
for $f(x) = 0$ if the Turing machine encoded by $x$'s binary representation halts when given the binary representation of $x$ as input (alternatively, when given the empty tape as input, and similar kinds of halting problems), and $f(x) = 1$ otherwise, the problem is undecidable (a solution to the problem for this $f$ could solve the halting problem)

Anybody see anything else fun?


What is a 'Key' in computer science? I'm a bit confused on what exactly the meaning of a 'key' is in computer science. I understand key-value pairs, primary keys, etc... But I can't find a definition of what the term 'key' means by itself.

As far as I can tell it just means a piece of data. In CLRS, data associated with tree nodes are referred to as 'keys'. Data to search a hash table is called a 'key'. Is this what a 'key' is?

In the most general sense, a key is a piece of information required to retrieve some data. However, this meaning plays out differently depending on exactly what situation you're dealing with.

In the contexts you mention, a key is a unique identifier for the complete data used to retrieve it from some location in the structure. Each key is associated with only one item, so it can be used to find a particular set of data. The data structure will usually be organized in such a way that finding the key is much more efficient than a linear search through all of the data. Sometimes the key is actually part of the data and stored along with it (like primary keys in the database); other times, it is segregated from the data itself (like in a hash map). The data structure will also often perform extra processing on the key (and only the key) to support its efficient searching algorithm (such as in a hash map, the key is converted into a hash code, or a database will index the primary keys using a B-tree).

In cryptography, a key is used in a sense more akin to physical keys used on locks. They're pieces of data required to obtain the original from the encrypted data (to "unlock" the data, so to speak).


I am a little bit confused about how to calculate the memory capacity I am a little bit confused about how to calculate the memory capacity.

word=data lines size
byte=8 bit
n=adresse lines size

  Most of the people use this formula to calculate the capacity of the
  memory: C=(2^n*word)/8 octet

Is this formula correct when speaking about byte-addressable? Because if we have byte-addressable memory, I think the capacity will be 2^n octet.

If this is correct why people use the formula in all cases? If not can you please explain why to me?

Thanks you.

This formula assumes that memory is word-addressable rather than byte-addressable. The number of words that can be addressed is $2^n$. If you want to convert this from words to bytes, you can use the formula (in which word stands for the word size in bits). If you want to convert it to kilobytes, for example, you need to multiply by the word size in bits, and divide by $8192$. And so on. Come up with your own formulas!


Is it or is it not correct to say that the expected runtime of an algorithm is its runtime on the expected problem size? Why? Say we have an algorithm that takes time $T$ to process a problem of size $n$.

Is $\langle T(n)\rangle $ = $T(\langle n\rangle)$?

In general, it does not hold that $\DeclareMathOperator{\EE}{\mathbb{E}}\EE[f(X)] = f(\EE[X])$. For example, suppose that $X=0$ with probability $1/2$ and $X=1$ with probability $1/2$, and that $f(x) = x^2$. Then $\EE[f(X)] = 1/2$ whereas $f(\EE[X]) = 1/4$.


Difference between approximation scheme and approximation algorithm? What is the difference between approximation schemes and approximation algorithms?
Why do we study approximation schemes?

In theoretical computer science, an approximation algorithm is an algorithm that guarantees a certain approximation ratio $\rho$, and an approximation scheme is a (uniform) collection of algorithms that guarantees several different approximation ratios. Since the collection is uniform (all the algorithms look the same but with different parameters), you can also think of an approximation scheme as an algorithm with an auxiliary parameter $\rho$ which then guarantees an approximation ratio of $\rho$; the close $\rho$ is to $1$, the harder the algorithm would have to work, and not all $\rho$ are valid inputs. For example, usually you need $\rho \neq 1$. If the scheme works for $\rho$ arbitrarily close to $1$, and furthermore the scheme is polynomial time (for each $\rho$ separately), then it is a polynomial time approximation scheme (PTAS).


Should we assume both processes are getting same CPU clock while we solve SYNCHRONIZATION problems in uniprocessor system? In synchronization, when one process is in a critical section & another is busy waiting,  both are using CPU. But in a uni processor system, in the same clock both cant get the CPU. So there must be a scheduling algorithm for them. Should we consider these while solving synchronization problem or should we think both are doing their work on the same clock while we solve problems in synchronization?

It is very common to run processes on an operating system with a preemptive scheduler. The scheduler can switch between processes at any time: it is unpredictable when the operating system will switch from one process to another.

Unless otherwise specified, this is the model we use when discussing synchronization problems: there may be a switch between processes at any time. This means that in many cases there is no difference between the uniprocessor case and the multiprocessor case: the same execution sequences are possible in both. The operating system effectively pretends that there's one CPU per process.

The switches can even happen in the middle of a high-level instruction. For example, if you write a simple assignment in a high-level language

x := y;

this could translate to multiple machine instructions such as

copy top half from x to y
[possible switch]
copy bottom half from x to y

or

load x to register r1
[possible switch]
store y from register r1

This is why it's important to know which operations are atomic even in the uniprocessor case.

When you consider synchronization between kernel threads, and you get down to the level of machine instructions, there are things that are not possible in a uniprocessor case, because the kernel decides when a context switch is possible. But to exclude these impossible sequences, you need to know both how the machine instructions work and how the kernel works. If you don't know that then you can't exclude any interleaving of the execution.


Relation between space and time complexity for machines with write once read many (WORM) memory While thinking about different calculi for predicate logic (like natural deduction and sequent calculus), I noticed that these calculi are (often) presented in a form suitable for "human computers". A "human computer" is limited to use write once read many (WORM) memory when processing large amounts of data. Pure functional programming also seems to favor a WORM memory model. In fact, it seems to me that the WORM memory model is so natural that classifying it as unconventional computing might underestimate its importance. (Understanding the strengths and limitations of the computing resources available to humans is important.)

What is known about the relation between space and time complexity for machines with WORM memory? What are the keywords to google for available material related to these questions? Do we known whether the time complexity will remain the same, if a small (for example C*log(WORM memory)^n) amount of normal memory is added?

What are the keywords to google for available material related to these questions?

The Wang B-machine is a very simple Turing machine with only WORM memory. A Turing machine with only WORM memory is commonly referred to as a "non-erasing Turing machine".

  What is known about the relation between space and time complexity for machines with WORM memory?

Let's assume a Turing machine with $q$ internal states and a binary tape alphabet.
If the machine halts after $t$ steps, having written $m$ marks on the tape and "visited" $p$ positions of tape, then $t \leq (m+1) \cdot pq$. The reasoning behind this bound is simple. As long as the machine doesn't write a new mark, there are only $pq$ distinct configurations. As the machine didn't cycle, it can have taken at most $pq$ steps between two write events, and there were only $m$ such write events.

  Do we known whether the time complexity will remain the same, if a small (for example C*log(WORM memory)^n) amount of normal memory is added?

Already Wang himself showed that a non-erasing Turing machine can simulate a normal Turing machine with only a polynomial slowdown. It was shown recently that the same is also true for the Wang B-machine. Hence it's not really interesting to investigate the change of time complexity when adding a small amount of normal memory to the machine. It would be more interesting to investigate (for different algorithms) how much the normal space complexity can be reduced by allowing for a separate non-erasable space complexity. Not sure how to apply this to pure functional programming.


What is the name for this ... (alerting when threshold is exceeded, but only if dropped enough below threshold first) Imagine:
you are monitoring a system, and want an alert when certain measured value goes over a threshold value X.

But perhaps the measured value is constantly fluctuating close to X, and you get a lot of alerts.

There's an solution to that, where you only get new alerts when the measured value has dropped to below Y (e.g. X-10%). So that you only get alerted when the value had dropped meaningfully below X.

What is the name for that?

I remember this from CS uni years, but can't remember which class it came with (queueing theory?), or what the name for it was.

I've googled with various keywords (monitoring, maximum, alerts, skewed, ...) but no useful results.

Hysteresis is a general concept in control systems that seems relevant.

Debouncing is another specific technique used for post-processing data from switches/buttons that has a similar flavor.  The term has sometimes been used elsewhere in software systems to deal with similar issues.

Finally, take a look at rate limiting for a related technique.


Can an interrupt handler be preempted? Can a running interrupt handler be pre-empted by another interrupt handler?
If this is possible, in which scenarios is this safe, and in which scenarios is it not?
If this is not possible, why?

This depends on both the processor architecture and the kernel architecture.

Generally speaking, interrupt handlers start with interrupts disabled. This is necessary so that the interrupt handler has room for storage — at a minimum, the interrupt handler needs the exclusive use of a few registers, including the program counter, which the processor must save somewhere (in a set of banked registers).

On some processors, it's possible for an interrupt to be interrupted by another higher-priority interrupt. To give one example that I'm familiar with, on ARM processors, there are two interrupt levels: IRQ (normal interrupts) and FIQ (fast interrupts). Each has their own register bank for the program counter and stack pointer, and their own interrupt vector. An IRQ handler starts with IRQ disabled but FIQ enabled; an FIQ handler starts with both IRQ and FIQ disabled. Thus an FIQ can be triggered in the middle of handling an IRQ.

It's up to the operating system to decide when an interrupt handler will reenable interrupts of the same priority, or interrupts of a different type with the same priority. The longer interrupts are blocked, the longer the latency to handle an interrupt that comes soon after another. In particular, a real-time OS typically needs to reenable interrupts very fast. To give a couple of examples:

FreeBSD's interrupt handlers can be preempted when they are performing a blocking operation (waiting for a lock).
Linux encourages splitting the task of an interrupt handler into two parts: the top half is the actual interrupt handler, and runs with interrupts disabled; the bottom half runs with normal preemption for as long as it needs. Typically the top half exchanges data between hardware peripherals and a preallocated memory buffer, then the bottom half handles all the rest such as communicating with other kernel and userland threads, initiating new hardware I/O, etc.

At the point where an interrupt handler unmasks interrupts, it must be ready to cope: it must not be using any resource that another interrupt handler would thrash. Furthermore, since the interrupt handler hasn't finished its job, there must be some mechanism for the program counter to be saved somewhere; the mechanics of this depends a lot on both the processor and the kernel architecture.


Sorting strings using Counting Sort in O(n), where n is the total number of characters in all the strings Suppose, you are given an array of strings of different lengths, but the total number of characters over all the strings is n. Describe an algorithm using Counting Sort to sort the strings in alphabetic order (eg. algorithm < cs < hello) in O(n) time.

Here is the general idea:

Sort all the strings according to their first character (refer to each string using an index to save time).
Partition the strings according to their first character, and run recursively on each part (deleting in your mind the first character).

I'll let you work out the details.


Dataset of Hard Instances of SUBSET-SUM I know for factoring we have the RSA Numbers, in which factoring one of them quickly (usually) indicates a breakthrough in the field. However, I want to know if there's something similar for SUBSET-SUM, in which there are hard instances that if solved, would be a "big deal"? I found this, but they don't seem to be unsolved.
One way would to take the RSA numbers, convert them to 3-SAT, then convert to SUBSET-SUM, but the weights generated are very large. Maybe there's a way to convert FACTOR (the special case of two prime factors, to be specific) directly to SUBSET-SUM without having to go through 3SAT (not the main question; just a thought)?
For the RSA numbers in particular, we know how long each non-trivial factor is: $\frac k2$, where $k$ is the number of bits of the number $n$. Maybe we can use that to shrink the number of variables to only $n$, without having to make extra variables and unnecessarily fill the problem with "junk".

Note that FACTOR isn't known to be NP-complete.


Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$ I would like your help with the following question:

  Let $L$ be a language, and operator $A(L)=\{\,ww^Rw \mid w \in L\ \wedge\ |w| \lt 2007\,\}$ where $x^R$ is the  reversed string of $x$. Which of the
  following statements are correct?

  If $L$ is regular so $A(L)$ is regular.
  If $L$ is a CFL which is not regular then $A(L)$ is CFL which is not regular.
  If $L$ is a CFL which is not regular, then $A(L)$ is a CFL which may or may not be regular.
  If $L$ is not a CFL then $A(L)$ is not CFL.

What does the fact that $|w|< 2007$ help me with the decision?
For (2) I can choose $O^n1^n$ and I get that $0^n1^{2n}0^{2n}1^n$, which is not regular, but for (3),(4) I can't find an examples to refute it. The answer is 3, but I can't understand why, since $A(L)= ww^R \circ  w$  but $ww^R$ is not regular.

Since $|w| < 2007$, the number of strings like $ww^Rw$ is finite. So $A(L)$ is finite for all $L$ and is hence regular.