Modeling a set of probabilistic concurrent processes I'm looking into discrete-time Markov chains (DTMCs) for use in analyzing a probabilistic consensus protocol. One basic thing I haven't been able to figure out is how to model a set of independent processes: consider $N$ processes. These processes will concurrently execute a series of identical instructions labeled $0, 1, 2, 3,$ etc. and all are starting in instruction $0$. When probability is not involved, modeling this is simple: it's a state machine which branches nondeterministically off the start state to $N$ different states, where in each of those $N$ states a different process was the first to execute instruction $0$. What do we do when probability is involved? Do we do the same thing with $N$ states branching from the start state, where the probability of transitioning to each state is $\frac{1}{N}$? As in, it's uniformly random which process was the first one to execute instruction $0$?

Is this like taking the product of the state machines of each process?

I'm using a DTMC here, would I gain anything by moving to a CTMC if I don't care about anything beyond the global order of execution?

Bonus question: assigning probabilities to whichever action is taken first seems like a generalization of the non-probabilistic notion of fairness; if it is, what is the formal definition of this generalized notion of probabilistic fairness?

One approach is to model it as a composition of $N+1$ processes: a scheduler process, plus your $N$ basic processes.  At each time step, the scheduler process selects which basic process will execute next.  Your scheduler could be randomized: for instance, at each time step, it could choose which basic process to execute next uniformly at random, if you wanted.

Now the transitions of the entire system, and their probabilities, should be easy to derive.  A state of the system is of the form $\langle s_0,s_1,\dots,s_N \rangle$ where $s_0$ is the state of the scheduler and $s_i$ is the state of the $i$th basic process.  Each transition might have the form $\langle s_0,\dots,s_N \rangle \to \langle s'_0,s_1,\dots,s_{i-1},s'_i,s_{i+1},\dots,s_N \rangle$ (where $i$ is a deterministic function of $s_0$, and with probability given by the probability of $s_0 \to s'_0$ in the scheduler multiplied by the probability of $s_i \to s'_i$ in the $i$th basic process).

There are probably other ways to model it as well, maybe better ones for all I know.  This is just one possibility that occurs to me.


Big-O Justification Question I am trying to justify the big-O order of a runtime complexity by finding a $c$ and $n_0$ that hold for it. Does the left side of the justification need to be one or higher, or can it be any value so long as it is a real number and less than the right side? For instance, is the following valid:
$$n^2/4 + 1/2 \leq c\cdot n^2\,,$$

when $c= 1$ and $n=1$:
$$3/4  \leq 1\,.$$

"The Big-O notation describes the limiting behavior of a function when
  the argument tends towards a particular value or infinity, usually in
  terms of simpler functions."-Wikipedia

If you see the formal definition, then the only restriction is that the domain of functions must be $\mathbb{R}$. Hence, by definition the range of the functions can at least be any vector space.
In the most common use in CS, the range of the functions is also taken to be $\mathbb{R}^+$.

To answer your question, by definition, the left side can be any real positive value.


Breadth First Search with cost Looking for some tutorials / references that discuss Breadth First Search that takes into consideration the cost of paths, but could not find much information.

Could someone refer a tutorial?

From a general point of view: there are tons, but I do sincerely recommend you the latest volume on Heuristic Search: Heuristic Search: Theory and Applications by Stefan Edelkamp and Stefan Schroedl.

From a specific point of view: in spite of the graph being directed or not, breadth-first search taking costs into account

If no heuristics are available, then it amounts to either Dijkstra or Uniform Cost Search. An excellent discussion between these two algorithms is presented in Felner, Ariel, "Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm", Symposium on Combinatorial Search, Barcelona (Spain), 2011.
If heuristics are available Then there are also a number of interesting alternatives: A$^*$ is the usual one but RBFS also expands the same nodes in the same order with a linear consumption of memory. For these, I do strongly recommend the book by Stefan Edelkamp and Stefan Schroedl.

Hope this helps,


Does a multi cpu system not improve the first come first serve (fcfs) cpu scheduling algorithm? I created a program that simulates the fcfs scheduling algorithm. First I implemented it for a single core, then modified it for four homogenoues cpus.

I compared the results with several datasets, and for the most part they are identical.

I understand fcfs is nonpreemtive, so there are no context switches. Then each cpu holds the process until its current cpu burst is finished, from there it either terminates or does IO (goes to wait queue).

Im guessing a multi core system only improves performance if many processes are in the ready queue at the same time, otherwise only one cpu is being used.

Here is the algorithm that I implemented:

while(TRUE)
{
    for(i = 0; i < NUM_CPUS; i++)
    {
        if(!cpu[i].idle)
        {
            if(cpu[i] is finished executing current burst)
            {
                //either move the process from the cpu to the waitQ, or terminate process if finished all bursts
                if(terminatedPrs == numberOfProcess)
                    break;
            }
        }
        if(waitQ->front != NULL)
        {
            //Check if waitQ->front is finished io
            if(waitQ->front finished IO burst)
            {
                //insert waitQ->front to readyQ, then dequeue waitQ
            }
        }
        if(cpu[i].idle)
        {
            if(readyQ->front != NULL)
            {
                //check if readyQ->front is ready to be executed (that is, arrival time < elapsedTime)
                if(readyQ->front ready to be executed)
                {
                    //move readyQ->front to CPU (begin executing), and dequeue readyQ
                }
            }
        }

    }
    elapsedTime++;
}

Is my algorithm fine? I am getting pretty much the same average waiting time, average turnaround time and average cpu utilization.

Sounds like something's very wrong.  My guess is that you are testing with a load that is too small.  You should be able to increase the number of processes and at some point the 4-processor system should be able to handle about 4 times as many processes.

Let's try a simple asymptotic analysis:

Suppose we have $N$ processes each of which goes through the following cycle repeatedly (forever):

Wait in the ready queue until a CPU is available.
Run on the CPU for average time $S$.
Request an I/O that takes average time $Z$.
Go back to the ready queue.

What's the minimum average response time $R_{\mathrm{min}}$, for going through this cycle once?   $S+Z$.  (That's the average time for service at the CPU plus average time for I/O, and no time waiting in the queue.)  So

$$ R \geq S+Z.  $$

Now Little's Law says that the average response time $R$ is equal to the number of processes in the system, $N$, divided by the system throughput, $X$ (in units of number of times through the entire cycle each second).

$$ R = \frac{N}{X}. $$

What's the maximum throughput this system can achieve.  That would happen in the (unrealistic) case that all the processors were busy all the time.  There are $P$ processors and each CPU burst consumes average time $S$, so the maximum throughput is $P/S$.  That is $X \leq P/S$.  So

$$ R \geq \frac{N}{X} = \frac{NS}{P}. $$

That is, when $\frac{NS}{P} \geq S+Z$ you should start to see the average response time increasing linearly as you increase the number of jobs in the system.  Below that and you won't see much difference.


Error propagation when compiling a compiler Just for curiosity, I recently heard that many compilers are written in its own language. For example, gcc is partially written in C. And old version of compiler is used to compile the new version of compiler.

Then I have a question, if there is a bug in the compiler, and you fix the bug in the source code and use the previous buggy compiler to compile a new compiler, how can you ensure that the bug in the new compiler is fixed?

Theoretically, if you have a very buggy old compiler, and now you have a new, bug-free version of the compiler source code, would the compiler converges to a bug-free compiler if you keep repeating compilation of the compiler starting from the old compiler?

There is no reason why compiling a compiler's source code with a broken compiler would result in a working compiler. The bug in the existing binary could well lead to a binary that is completely broken, or subtly broken, or has the very same bug.

For example, there once was a version of CAML (an ancestor language of Ocaml) where one version of the compiler omitted the code for a case in a match-case construct under certain circumstances. So the developers fixed the bug — a case was missing in a match-case construct in the source code. But the compiler was bootstrapped (the CAML compiler was written in CAML), and compiling the corrected source generated a binary that was still buggy, because the compiler bug caused the new case to not have generated code. The developers had to rewrite the code in a different way, then recompile to get a correct compiler, and after that they could change the source code back to using the desired match-case construct.

There is a rather famous example where such a self-reproducing bug was introduced deliberately: the “Thompson hack”. Ken Thompson was one of the main authors of the Unix operating system and the first C compiler. He introduced a backdoor in the operating system by modifying the source code of the login program to allow him to log in on any Unix system. Then he reverted this change and instead modified the C compiler to insert this backdoor whenever it was compiling login.c. Then he modified the C compiler again to add code to insert the backdoor in login whenever the compiler was compiling itself. He recompiled the compiler and removed all traces of his backdoor. So he had a self-perpetuating bug which happened to be a backdoor. I strongly recommend “Reflections on Trusting Trust”, his Turing award lecture, where he revealed and explained this backdoor.

In practice, there are a few ways to reduce the risk of self-perpetuating compiler bugs. Compiler writers usually try to use a well-known, stable subset of the language, and avoid newer features where the compiler is more likely to have bugs. Some compilers have a bootstrap compiler which depends on a subset $A$ of the language and is capable of compiling a subset $B \supset A$; the full compiler is written in $B$ and is capable of compiling the whole language. If multiple compilers exist for the language the compiler is written in, this makes it unlikely that they'll all be too buggy to compile the compiler.

There are research efforts to reduce the trusted base of compilers, i.e. the amount of software that must be assumed to be correct in order to guarantee that the compiler binaries will work correctly. In particular, certified compilers come with a proof that the compiler binary has the semantics specified by its source code. A correctness statement goes like this: “assuming that the proof checker for the compiler is correct, and assuming that the runtime environment in which the compiler runs conforms to its model, then the compiler always produces binaries that have the semantics specified by their source code”. The trusted base consists in the runtime environment and the proof checker, which is typically orders of magnitude smaller than a compiler.


Does the Bellman-Ford algorithm find all the negative cycles? The Bellman-Ford algorithm "can detect and report the negative cycle", but does it guarantee to find them or it may find some?

The algorithm really focuses on the shortest paths, so I'm unclear if it will find any negative cycle or if it might miss it.

Thanks!

EDIT:
I'm only interested in knowing if there is a negative cycle (not where it is). How does one prove that Bellman-Ford would find the existence of a cycle?

Bellman-Ford simply returns there exists at least one negative-weight cycle, it doesn't actually find all edges part of all such cycles. At best, without extending the algorithm too much, you find at most one edge per negative-weight cycle as cycles may intersect. There are ways to recover a negative weight cycle, see the link you provided, but this is outside the scope of the Bellman-Ford algorithm.

Edit: There is a subtlety that I forgot to mention, Bellman-Ford only returns the existence of a negative-weight cycle if that is cycle is reachable from the source vertex. In a disconnected graph, it may be the case that the negative-weight cycle is unreachable, so it will not be reported. Assume therefore that for every graph with a negative-weight cycle, it is reachable from the source vertex.

The proof is fairly simple. Let $v_1, v_2, \dots, v_k, v_1$ be a reachable negative weight cycle. We assume for contradiction that
$d(v_i) + w(v_i, v_{i+1}) \geq d(v_{i+1}) for all $i = 1, \dots, k$.

If we add all inequalities, we obtain

$$\sum_{i = 1}^{k} d(v_i) + \left(\sum_{i = 1}^{k - 1} w(v_i, v_{i+1}) + w(v_k, v_1)\right) \geq \sum_{i = 1}^{k} d(v_i),$$

and so $\sum_{i = 1}^{k - 1} w(v_i, v_{i+1}) + w(v_k, v_1) \geq 0$. This is a contradiction, thus it must be that there is an edge on the cycle that still can be relaxed. Note that a simple path is of at most length $|V| - 1$, and if an edge can still be relaxed after $|V| - 1$ iterations, it must be an edge of a negative-weight cycle (this is maybe a little too simplified, but the intuition is correct).


Separating two strings without a separating character Say you need to write a function such that you have string a and string b.
The function argument is a concatenation of string a and string b.
The function prints string a and string b separately. I'll explain.

For example one can think of a naive solution such that 'x' will be a separator character and so if we want to print "hello world" for example we create a function that prints everything as string a until it encounters an 'x' char and than it knows that string b is starting.
So our argument will be something like:

void separateString("helloxworld");

But this eliminates the option of using 'x' as a char in our String.

I am sure that there is a simple solution to this that I am not getting.

Not looking for code, just your idea. The code will be easy to implement.

Thanks

Just an extended note for the "quoting" techniques:

You can also pick one character of the alphabet (e.g. $a$) and interpret it as a space and use $aa$ for $a$:

 hello world  -> helloaworld
 amazing spacing -> aamaazingaspaacing

However it is easy to see that this approach can lead to ambiguities:

 a are doubled -> aaaaare doubled
                 --OK_DECODING   -> a are doubled
                 --WRONG_DECODING-> aa re doubled

These ambiguities can be avoided/ignored if we assume that the "special" character $a$ appears only in a well defined format and context.

Indeed this technique is still used for representing quotes or double quotes in well-known formats: e.g it is used for strings in the CSV format: every string is double quoted and the double quotes in a string are "doubled".

 COLUMN 1 | COLUMN 2            | COLUMN 3
 42        | My name is "Nobody" | He said "To be or not to be"
 43        | "Quote me"          | Charater " embedded

Are represented in CVS files as:

 42,"My name is ""Nobody""","He said ""To be or not to be"""
 43,"""Quote me""","Character "" embedded"

It is also used for single quotes in the SQL language:

 SELECT 'This is a quoted string: ''Hello world''!!!'

But more modern languages/formats usually prefer the escape technique (see Yuval's answer)


Regular expression for the strings without a particular substring How can we design a regular expressions without particular substrings.
The goal of this is to create language L which won't contain a particular substring (i.e. 110)

for the case of a regular expression without substring $110$, I Was thinking of: $\require{cancel}\cancel{(101)^*+}(010)^*+(10)^*+(\cancel{1}1)^*+(\cancel{0}0)^*+(01)^*$ but is that over excessive?

Then for example, I crossed out (101)* because obviously if you have two of those 101101, a subset of that will be 110, which we don't want.

Notes:

Question has been edited since it gained attention in the past few days. Also see comment for justification.

I did the following multistep technique.

Step 1: make a DFA that accepts all strings with "110".  I am able to construct a DFA that accepts all strings with substring "110" and has just 4 states.

Step 2: Flip all the accepting states to non-accepting and all the non-accepting states to accepting.  This page at Old Dominion describes the technique quite succinctly.  This creates a DFA that accepts the language you want.

Step 3: Now you need to convert the DFA back to a regular expression.  As @Alejandro Sazo mentioned there is a proof that this is possible.  But you need an algorithm.  This paper by Christoph Neumann describes three different techniques.  The easiest one is the "state removal technique."   You remove a state and replace all the edges between states that were connected to the removed state with edges labeled with regular expressions.  As you reduce in this way you eventually get to a regular expression for the whole DFA.  (Note that Figure 4 in the paper I linked is not quite right.  The self-loop on state $q_j$ should have the regular expression "c e* b", not "c e* d".)

By going through this process it became clear that: the language you are going to need to solve for this particular problem has the property that once you have seen the sub-string "11" then you can never see another "0".


What is the "shortest path heuristic" for the Steiner problem in graphs? I keep encountering citations of the following article:

Takahashi  and  A.  Matsuyama,  “An  approximate  solution  for  the Steiner  problem  in  graphs,” Math. Japonica,  vol.  24,  no.  6,  pp.  573–577, 1980

For example, Yahui Sun refers to it here as "a widely-used Steiner tree approximation algorithm".
But... what is the actual algorithm?
The website of Mathematica Japonica only goes back to 1994, and I can't find the article anywhere else either.
Wikipedia contains this description, but without a citation:

The general graph Steiner tree problem can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of the graph induced by the terminal vertices. The metric closure of a graph G is the complete graph in which each edge is weighted by the shortest path distance between the nodes in G. This algorithm produces a tree whose weight is within a 2 − 2/t factor of the weight of the optimal Steiner tree where t is the number of leaves in the optimal Steiner tree; this can be proven by considering a traveling salesperson tour on the optimal Steiner tree. The approximate solution is computable in polynomial time by first solving the all-pairs shortest paths problem to compute the metric closure, then by solving the minimum spanning tree problem.

Is this the algorithm that Sun and others refer to?

Let G = (V, E) be our graph, and S be the set of vertices that must be in the Steiner tree. Let t be the number of leaves in the optimal Steiner tree.
It seems that Takahashi and Matsuyama's algorithm (1980) is indeed the "shortest path heuristic" since it actually uses shortest-path searches. Starting from a single vertex, it simply grows the tree T by finding the closest vertex v in S \ T that hasn't been added yet, and adding the shortest path from T to v until all vertices have been added, similar to Prim's algorithm for the minimum spanning tree.
The algorithm I cited from Wikipedia, based on the metric closure, is due to Kou, Markowsky and Berman (1981), and boils down to: compute the metric closure, find the minimum spanning tree of the metric closure, turn this back into a subgraph (not necessarily a tree) of the original graph, find the minimum spanning tree of that subgraph, then repeatedly remove leaves that are not in S.
I didn't read Gilbert and Pollak (1968) fully (it's mostly about the geometry of Steiner trees in the plane). I presume they did something similar to Kou et al., but without the final pruning step, which might explain why they only got within a factor 2 from the optimal cost, rather than the 2 - 2/t by Kou et al..
I made some edits to Wikipedia to record all this, and added a summary of an algorithm by Wu, Widmayer and Wong (1986), which is more efficient and also easier to implement than both of the above, while retaining the same optimality bound.


Closure of Turing-recognizable languages under homomorphism I've proven that the  Turing-recognizable languages are closed under concatenation and I need to show that they are closed under homomorphism.

But what's really the difference? Doesn't closure under concatenation imply homomorphism as well? Or perhaps I misunderstand what homomorphism means when talking about Turing-Recognizable languges?

A class of languages $\mathcal{L}$ is closed against concatenation if for every pair of languages $L_1, L_2 \in \mathcal{L}$ we also have $L_1 \cdot L_2 \in \mathcal{L}$.

Here, $A \cdot B = \{ v \cdot w \mid v \in A, w \in B \}$.

A class of languages $\mathcal{L}$ is closed against homomorphism if for every language $L \in \mathcal{L}$ and every (word) homomorphism $f$ we also have that $f(L) \in \mathcal{L}$.

Here, $f : \Sigma \to \Sigma^*$ is lifted to words and sets in the natural way, i.e.

$\qquad\displaystyle f(w) = f(w_1) \dots f(w_n)$ for $w = w_1 \dots w_n$,

and

$\qquad\displaystyle f(A) = \{ f(w) \mid w \in A\}$.

(Note that can make a difference if you require $f : \Sigma \to \Sigma^+$.)

It's easy to see that the two are not the same.

   Let $A = \{ w \in \{a, b\}^* \mid |w|_a \in 2\mathbb{N} \}$. Clearly, $\mathcal{A} = 2^A$ is closed against concatenation but not against homomorphism.

 Let $B = \{ ww \mid w \in \{a,b\}^* \}$. Then, $\mathcal{B} = 2^B$ is closed against homomorphism but not against concatenation.
 (mentioned by chi in a comment)

 For completeness, $2^{\Sigma^*}$ is closed against both, and $\mathcal{A}\cdot\mathcal{B}$ against neither.


Is a set system an independence system, if and only if it is an accessible system, and has the Interval Property without Lower Bounds From Wikipedia,
a finite matroid $M$ is defined to be $(E,F)$, where $E$ is a finite set  and $F$ is a family of subsets of $E$, so that it satisfies

either nonempty, the hereditary property, and the augmentation property:
or an accessible system, the augmentation property, and the interval property without lower bounds.

The two definitions should be equivalent. Do we need the augmentation property, for the following to be true:

  a set system $(E,F)$ is nonempty and has the hereditary property, if and only if it is an accessible system, and has the Interval Property without Lower Bounds?

Without assuming the augmentation property, it is simple to see that the "only if" part is true, but I wonder if the "if"part is also true?
Thanks and regards!

Note:

A set system $(E,F)$ that is nonempty and has the hereditary property is also called an independence system.

The aforementioned properties are defined as follows:

The empty set is in $F$. (nonempty property)
if $X \in F$, then every subset of $X$ is also in $F$. (The hereditary property)
for all $X,Y ∈ F$ with $|X| > |Y|$, there is some $x ∈ X-Y$ such that $Y∪{x} ∈ F$. (The augmentation property)
Every nonempty  $X  \in F$ contains an element $x$ such that $X-\{x\} \in F$. (I.e. $(E,F)$ is an accessible system)
If $B, C ∈ F$ with $B ⊆ C$, then, for all $x ∈ E-C$, $C∪\{x\} ∈ F$ implies $B∪\{x\} ∈ F$. (the Interval Property without Lower Bounds)

Suppose that a set system $F$ is accessible and satisfies the interval property. We show that it is hereditary. Let $C = \{x_1,\ldots,x_n\}$ be any set. Without loss of generality, by accessibility we can assume that for all $t \in \{0,\ldots,n\}$, $\{x_1,\ldots,x_t\} \in F$. We show by induction that all subsets $B$ of $C$ are in $F$. If $|B| = 0$ then $B = \emptyset \in F$ (the case $t = 0$ above). Now suppose $B = \{x_{i_1}, \ldots, x_{i_k}\}$, where $i_1 < i_2 < \cdots < i_k$. By assumption, $A = \{x_{i_1},\ldots,x_{i_{k-1}}\} \in F$. Now $A \subseteq \{x_1,\ldots,x_{i_k-1}\}$ and both $\{x_1,\ldots,x_{i_k-1}\},\{x_1,\ldots,x_{i_k}\} \in F$, and so by the interval property, $B = A \cup \{x_{i_k}\} \in F$.


What is the best hash functions for millions of String keys? I have a situation where there are a million Keys of type String and I want to use the Symbol table to store the key and the value.

The problem that the retrieval process is too slow and I want to improve the retrieval. I wonder if there is a good hash function to help me with this task.

I am using Separate Channing for resolving the collision

the current hash function

hash = 0
for i = 0 : strlen
    hash = hash * 31 + getChar(strlen, i)

So My question: Is there a better hash function to minimize the collision between the keys?

hash = (hash + getChar(strlen, i)) * 123456791


Is there a language that cannot be polynomially reduced to? Is there a language A that cannot be polynomially reduced to by some language B? Or is it always possible to reduce a language B to A?

As stated in the comments, every problem is reducible to itself (under any notion of reduction - polynomial-time many-one reduction, polynomial-time Turing reduction, ...).

It's worth noting that when thinking about many-one reductions there are two important "edge cases" to consider:

No nonempty set is many-one reducible to $\emptyset$.
No set other than $\mathbb{N}$ is many-one reducible to $\mathbb{N}$.

I'll prove the first, since the second is identical. Suppose $A\not=\emptyset$, and pick $a\in A$. Fixing any function $f$ whatsoever, we have $a\in A$ but $f(a)\not\in \emptyset$, so $f$ is not a many-one reduction of $A$ to $\emptyset$. This doesn't impact your main question, but it does illustrate a subtlety of many-one reductions. (Note that this doesn't apply to more complex reductions like Turing or truth-table: with respect to such notions, all computable sets are reducible to each other.)

You also ask in the comments whether there is some $X$ such that every set is reducible to $X$. The answer is no, regardless of what reducibility we use:

One natural example, applicable to all the usual reducibility notions in complexity theory, is provided by the Turing jump: every language $A$ has a "halting problem analogue," $A'$. The usual proof that the halting problem is not computable relativizes to show that $A'$ is not Turing-reducible to $A$, and a very simple argument shows additionally that $A$ is $1$-reducible to $A'$ - even logtime-$1$-reducible, under a mild assumption on the enumeration of oracle Turing machines we use. So in a very strong sense every set is strictly less complicated than its jump.

Incidentally the "complexity interval" between a set and its jump is always quite rich: the jump is very much not a successor operation. So in some sense using the jump here is massive overkill. However, there's no "natural" way so far as we know to build such "intermediate" sets (and this is why the halting problem is the canonical example of a non-computable set!). Indeed it's broadly conjectured that there are no "natural" sets $A,B$ such that $B$ is strictly between $A$ and $A'$ in terms of Turing reducibility, and we know some technical results along these lines. So introducing the Turing jump here is kind of unavoidable if we don't want to do weird stuff.

More coarsely, basically all of the reductions we consider in the context of computability theory have the property that they're indexed by natural numbers: for any $A$, there are only countably many $B$ which are reducible to $A$ according to that notion. Now apply Cantor.

This applies even to very strong reducibilities like hyperarithmetic reducibility (which in particular is so strong that the halting problem and the Turing jump in general is totally irrelevant). To break out of this situation we need to either look at "ambiguous" reducibilities like generic or coarse reductions or set-theoretic reducibilities like relative constructibility which are consistently fairly trivial. But the former are still subject to the "no-top-element" issue in a coarse manner by only slightly messier arguments, and the latter are generally only studied under additional assumptions which make them nontrivial (and in particular, lacking a top element).


Z Notation: sequence of sequences - find sum Let me just say that this is for a university project. I do not expect an answer but more of a "hint".
I have a schema of a Supermarket that holds a sequence of queues:
+-- Supermarket-------
|queues: seq Queue
----------------------

And here is how I've defined a queue:
+-- Queue ----------
|length: ℕ
--------------------

I wish to define a schema that returns the total number of customers, waiting in line. Thus far I have:
+--TotalQueueCustomers----
|Ξsupermarket: Supermarket
|totalCustomers!: ℕ
|-------------------------
|totalCustomers = total θ supermarket
--------------------------

I'm struggling with defining the total function. It needs to "loop" every customer in every queue and sum their lengths. Here is what I have so far: total = q: Queue ⦁ q.length ↦ q.length
Any idea?

I am not aware of the Z notation but here's what you have to do:
step 1: initialize a variable total to 0
step 2: loop through all queues
step 3: add the length of every queue to total


How get the permutation of two lists but the elements of each list remain in the same order? So if I have lst1 = [a, b] and lst2 = [x, y] the result would be:

[x, y, a, b]
[x, a, y, b]
[x, a, b, y]
[a, x, y, b]
[a, x, b, y]
[a, b, x, y]

I'm thinking about doing something recursive where I take the first element of a list, place it at the start, then recursively take the next element of that list and shift it through each position (and on each shift go through all remaining elements of that list).

But I'm wondering if there may be a nicer way to do this?

edit: Some more elaborate info here

Generate a string chi with len(lst1) 0s and len(lst2) 1s, e.g. for lst1 = [x, y] and lst2 = [a, b, c], you generate chi = [0, 0, 1, 1, 1].  Then you shuffle chi to obtain your "characteristic vector".  This new list will dictate the order in which to output elements from lst1 and lst2.

I hope this Python program speaks for itself:

from random import shuffle

def permutation(lst1, lst2, chi):
    idx1 = 0
    idx2 = 0
    for i in range(len(lst1) + len(lst2)):
        if chi[i] == '0':
            yield lst1[idx1]
            idx1 += 1
        else:
            yield lst2[idx2]
            idx2 += 1

lst1 = 'xy'
lst2 = 'abc'

chi = list('0' * len(lst1) + '1' * len(lst2))
shuffle(chi)
print(''.join(chi))
print(''.join(list(permutation(lst1, lst2, chi))))

Outputs:

11001
abxyc

10011
axybc

00111
xyabc


Is the language of words that are unbalanced in the first half context-free? (Practice exam question in computational models)

Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s.

Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and the first half of $w$ is unbalanced$\}$. Determine whether or not $L$ is context-free and prove your answer. You may do so by drawing an NPDA which recognizes $L$, using the closure properties of CFLs, or the relevant pumping lemma.

This question has been bugging me for a while; my gut tells me it isn't context-free since any PDA that recognizes it would have to check the balance of the string read thus far while simultaneously measuring its length and non-deterministically choosing an unbalanced point to validate as the middle of the word. I also haven't been able to express it as a union or concatenation of two CFLs or find a CFG which generates it.

On the other hand, I haven't been able to either find a word in the language that can't be pumped or prove that every word can be pumped.

Does anyone have any ideas on how to proceed?

Perhaps it can be proved using Ogden's Lemma and its generalization by Bader and Moura, this is a rather informal sketch of the proof.
First restrict $L$ to strings of length $4n$ and apply to it the following homomorphism between $\Sigma = \{ 0,1 \}$ and $\Sigma' = \{ a, b, c\}$:
$h(11) \to a$
$h(00) \to b$
$h(01) \to c$
$h(10) \to c$
If $L$ is CF then also the new language $L'$ obtained is CF by closure properties.
Informally $L'$ contains an unbalanced number of $a$ and $b$ in the first half and the number/occurences of $c$ doesn't matter.
Further restrict $L'$ by intersecting it with the regular language $R = \{ a^* (c^* b^*)^*  \}$; let $L'' = R \cap L'$
For example the string
$a a c b | cccc \in L''$ corresponds to $11\;11\;10\;00\; |\; 10\;10\;10\;10 \in L$ ($|$ is used to mark the half of the string for better readability)
$a b c c | cccc \notin L''$ corresponds to $11\;00\;10\;10\;|\;10\;10\;10\;10 \notin L$
Suppose that $L''$ is CF, and $p$ is its pumping length. Build $w \in L''$ concatenating these four parts:

$(\;a^p\;)$ leading $a$'s

$(\;c^j\;)$ a sequence of $c$s, we'll fix $j$ below

$(\;c^{p} \;b\;)$ repeated $p + p!$

If $n$ is the constant of the Bader-Moura's condition, then we pick $j$ large enough to exclude all the symbols in part 1 and 3: $j \geq n^{p+(p+1)(p+p!)+1}$

$(c^k)$ where $k$ is large enough to be pumped exluding all  previous symbols: $k \geq n^{p + j + (p+1)(p+p!)+1}$

$w = a^{p} \; c^j \; (c^{p} \;b )^{p+p!} \; c^{k} $
Now we mark the first $a$ sequence as distinguished, the string $vx$ must contain $0 < q \leq p$ distinguished positions ($\#a_{vx} = q$) by Ogden's lemma; $vx$ can also contain one $b$ (not more than one because the $b$s are spaced with more than $p$ symbols $c$) and $0 \leq r < p$ symbols $c$ ($\#c_{vx} = r$).

if $vx$ is such that $\#a_{vx}=q$, $\#b_{vx}=0$, $\#c_{vx}=r$:

then we can pump $i = p! / q $ times and we obtain the same number of $a$s and $b$s; if after the pump some $b$s fall after the half of the string, we can pump the final $c^k$ independently from the rest of the string and we can "push" all $a$s and $b$s back in the first half (and $\#a_{w'} = \#b_{w'} = p + p!$), so the pumped string $w'$ is not in $L''$

if $vx$ is such that $\#a_{vx}=q$, $\#b_{vx}=1$, $\#c_{vx}=r$:

then each time we pump we increase the number of $a$s and $b$s, but we cannot guarantee that we reach the same number (e.g. in the case $\#a_{vx}=q=1\#b_{vx}$). But in this case the derivation tree "isolate" the $c^j$ part of the string from the final part $c^k$, so we can pump them independently.
We can pump $c^j$ as many time as needed to "push" $p!$ symbols $b$s to the second half of the string. Suppose that the pumping length of $c^j$ is $s$ (that must be even), the half of the string is shifted towards the $b$s by $s/2$. We have $s \leq p$ so after each pump at most one $b$ is "pushed" to the second half, because the "distance" between $b$s is $p$. So also in this case we get a string $w'$ not in $L''$


Where does the base come from in a subsequence count? If sequence X has m symbols, then X has 2m possible subsequences.

Where does the base (2) come from?

The origin of this question is the following paragraph:

  We are given two ordered sequences of symbols, and we wish to find a longest common subsequence of $X$ and $Y$.

  A subsequence of $X$ is just $X$ with some (or possibly all
  or none) of its elements removed. For example, one subsequence of A; B; C; D; E; F; G would be B; C; E; G.

  The length of a longest
  common subsequence of $X$ and $Y$ gives one measure of how similar these
  two sequences are. For example, if the two sequences are base pairs in
  DNA strands, then we might consider them similar if they have a long
  common subsequence.

  If $X$ has $m$ symbols and $Y$ has $n$ symbols, then $X$ and
  $Y$ have $2^m$ and $2^n$ possible subsequences
  respectively.

You can think of a subsequence $Y$ of $X$ as a characteristic vector $\chi_Y$  that has $m$ elements, one per element of $X$. The $i$-th element of $\chi_Y$ is $1$ if the $i$-th element of $X$ is also in $Y$ and $0$ otherwise.

It is easy to see that this is a bijection: every subsequence $Y$ has a distinct characteristic vector $\chi_Y$, and every characteristic vector $\chi_Y$ is associated to a distinct sequence $Y$.

This means that the number of subsequences $Y$ is equal to the number of vectors $\chi_Y$. Since each vector $\chi_Y$ has $m$ elements, each of which can have one of $2$ possible values, this number is $2^m$.

A concrete example of a sequence $X$, a subsequence $Y$, and its characteristic vector $\chi_Y$ is the following:


Why do register machines outperform stack machines? Wikipedia says stack machine “designs have though been routinely outperformed by the traditional register machine systems, and have remained a niche player in the market.” Why is this?

I think the prime reason why register machines are better at performance because registers are within the CPU chip itself, however stack is generally the part of main memory, accessing register is on average 1-3 clock cycles, level 1 cache requires nearly 10-20 cycles on average, and depending on the design it could have level 2 shared cache which takes about 40 cycles on average, finally main memory takes 100s of cycles in comparison per initial word access then once you access it, the further block containing the required word is only incrementally cycle consuming. Hence register based architecture should always out perform stack based.

The data presented is definitely not according to today's state of the art processors take it from more of a conceptual stand point rather than practical one, and that I believe was the intent of the question.


Can one get Turing-completeness without nontermination? As I'm reading the movfuscator paper by Stephen Dolan, I encounter this claim:

  In order to have Turing-completeness, we must allow for nontermination.

This seems like a reasonable statement. But I'm also aware of this work by Wouter Swierstra which aims to prove quite the opposite (as I see it): that one can simulate a Turing-complete machine in a total language such as Agda.

From a purely theoretic point of view: I'm somewhat confused. Total languages permit only total functions, and total functions always terminate. Yet there exists a total interpreter of a Turing-complete language. Can somebody help reconcile this confusion?

Is nontermination necessary for Turing-completeness? Is this a valid question at all?

Many total languages, including Agda and Coq, allow you to define coinductive data types. These model infinite objects, like infinite lists.

Obviously, a function producing an infinite list cannot terminate. However, it must, in a total language, be productive. This means that any finite prefix of the produced infinite list can be computed in finite time. Coq and Agda have productivity checkers to ensure this, like they have termination checkers for functions which consume inductive data types.

Using these coinductive data types, you can model infinite executions. In the example you linked, 'running' a brainfuck program produces a trace, which is a potentially-infinite list of machine states.

Whether this is enough to declare the language 'Turing-complete' is, I guess, a question for philosophers. Agda only ever allows you to inspect a finite prefix of the generated trace, so you can't 'run' a program for an infinite amount of time. Then again, no physical machine can run a program for an infinite amount of time. And in practice, you can just disable Agda's termination checker for the one function that prints out your potentially-infinite trace.


Big O Proof for Logarithmic Function I am an undergraduate student in Computer Engineering and going through one of the textbook examples, I am asked to prove that

$T(n)$ is $O(\log{}n)$

Where $T(n)= 5\log_{2} 2n +7$.
I understand that this means that I must prove that $5\log_{2} 2n +7 \leq\lambda log(n)$

For some in n in a neighborhood of infinity. How exactly would I proceed with this?

$$5\log_2(2n)+7=5\log_2 n+5\log_2 2+7=5\log_2 n +12$$
Since for example $12\le 12\log_2 n$ for $n\ge 2$, it follows that
$$5\log_2 n +12\le 5\log_2 n +12\log_2 n=17\log_2 n $$
for $n\ge 2$. This yields $O(\log n) $.


A Language Belonges to PSPACE Let $A,B$ be two languages, for which we know:

$A \in PSPACE$
$A\le_LB$

Can we conclude from the above that $B \in PSPACE$ ?

I think the answer is no, however I don't know how to prove it. I guess I have to write a reduction that proves otherwise, but how?
Thank you!

No.
Note that given languages $A,B$ and a reduction $A\le_L B$, you get that $B$ is at least as hard as $A$, but that's about it.

You can contradict the above statement with the following extreme:

Take $A = \{0\}$, then $A\in \text{PSPACE}$, and take $B= H_{TM}\cup\{0\}$.

Define $f$ to be the following reduction $A \le_L H_{TM}\cup\{0\}$ (we can assume that $1\notin H_{TM}$):

$$f(0) = 0$$ $$\forall x\in \Sigma^*\setminus\{0\}  . f(x)=1$$.

Clearly $f$ works in logarithmic space, but $B$ is clearly not in $\text{PSPACE}$. In fact, it isn't even in $\text{R}$.


Does the closure of a function include the actual parameter passed to the function? A closure of a function includes the environment when calling the function.

Does the environment included in a closure of a function include the actual parameters for the function?

If I am correct, from mathematical logic point of view, a closure for an expression consists of the free variables of the expression. So I guess the answer to the question is no.

No. A closure is a function, and, as such, its parameters are passed when the function is called. The main difference between closures and plain functions is that closures are associated with an environment. This environment stores the values of the free variables* that were in scope when the function was created.

* The term free variable refers to those variables which are used locally within a function but are defined outside of this function (i.e., in an enclosing scope).


Proving that L is not regular using closure properties I need to show that the following language is not regular.

$$L = \{\ ab^jc^j\ |\ j \geq 0\ \}\ \cup\ \{\ a^ib^jc^k\ |\ i, j, k \geq 0 \ and\ i \neq 1\ \}$$

There is also a hint that it cannot be proven just with using the Pumping Lemma. Closure properties must also be used.

I'm having a hard time with this one. Any help would be appreciated.

Let $ L_1 = \{\ ab^jc^j\ |\ j \geq 0\ \} $ and $ L_2 = \{\ a^ib^jc^k\ |\ i, j, k \geq 0 \ and\ i \neq 1\ \} $. Then

$$
L = L_1 \cup L_2.
$$

If we take
$$ \begin{align}
L\ \cap\ ab^*c^* &= (L_1\cup L_2) \cap ab^*c^* \\
 &= (L_1\cap ab^*c^*)\ \cup\ (L_2 \cap ab^*c^*)\\
\end{align}
$$

Since $L_1\cap ab^*c^* = L_1$ and  $L_2 \cap ab^*c^* = \emptyset$, we have

$$
L\ \cap ab^*c^* = L_1
$$

Now, $ab^*c^*$ is regular, and $L_1$ is not regular (can be shown using the Pumping Lemma). If $L$ was regular, by the closure properties, $L_1$ would be to, which is a contradiction. Hence, $L$ is not regular.


How do we place $8n$ objects in a grid of size $n \times n$? How do we place $8n$ objects on a square of size $n\times n$ in a form of grid such that no 4 of them form a rectangle with sides parallel to those of square? Each object occupies exactly one cell in the grid and two objects cannot occupy the same cell. We are given $n\geq 100$.

Example. The following can be a $7\times7$ portion of some large grid (say $200\times200$), where 0 and 1 denote empty and filled cells respectively):

0000111
0101001
0011100
0110010
1010001
1001010
1100100

What approach one should follow to solve the problem?

Source: codechef.com MAY Long challenge "Ada Rooks 2"

Given a set of objects in a cell grid, if no 4-set of it forms a rectangle with sides parallel to the sides of the grid, we will call those objects rectangle-free.

The more general problem is to determine sequence A072567, whose $n$-th term $M_n$ is the size of maximal set of rectangle-free cells in an $n \times n$ cell grid. Its first 13 entries are

$$1, 3, 6, 9, 12, 16, 21, 24, 29, 34, 39, 45, 52, \cdots$$

It looks like the value of $M_{14}$ is unknown, which does not matter for the current problem, though.

We know that $M_{q^2+q+1}=(q+1)(q^2+q+1)$ when $q$ is a power of a prime number. In particular, letting $q=4,5,9,11,13$, we get $M_{21}=105$, $M_{31}=186$, $M_{91}=910$, $M_{133}=1596$, $M_{183}=2548$.

For a square grid of size $n\ge100$, we will select disjoint smaller square grids along its main diagonal line and fill the maximal set of rectangle-free cells in each of those smaller squares.

If $100\le n\le 113$, select a grid of size 91 since $91<100$ and $M_{91}=910 \gt 8 \times 113.$
If $114\le n\le 125$, select one grid of size 91 and one grid of 21 since $91+21\lt 114$ and $M_{91}+M_{21}=910 + 105\gt 8 \times 125.$
If $126\le n\le 132$, select one grid of size 91 and one grid of 31 since $91+31\lt 126$ and $M_{91}+M_{31}=910 + 186\gt 8 \times 132.$
If $133\le n\le 182$, select one grid of size 133 since $133\le 133$ and $M_{133}=1596\gt 8 \times 182.$
If $183\le n\le 300$, select one grid of size 183 since $183\le 183$ and $M_{183}=2548\gt 8 \times 300.$
if $200+100k\le n\lt200+100(k+1)$ for some $k\ge1$, select one grid of size 183 and $k$ grids of size 91 since $183+91k\lt 200+100k$ and $M_{183}+kM_{91}=2548+910k>800(300+100k)\gt8n$.

Now the problem is shifted to realize $M_{q^2+q+1}=(q+1)(q^2+q+1)$ for $q=4,5,9,11,13$. The realizations comes from finite projective planes that is built on top of finite fields, which is explained in detail here.

There are many packages that helps computation of finite fields.

Here is how to fill $21\times21$ grid with 105 objects. Note that there are exactly 5 objects in each row and each column.

000000000000000011111
010001000100010000001
000100010001000100001
001000100010001000001
000011110000000010000
010010000001001001000
000110000010010000100
001010000100000100010
000000000000111110000
010000010010100000010
000100100100100001000
001001000001100000100
000000001111000010000
010000101000000100100
000101001000001000010
001000011000010001000
100010001000100000001
100001000010000101000
100000100001010000010
100000010100001000100
111100000000000010000

Here is how to fill $31\times31$ grid with 186 objects, where empty cells are left as whitespaces. Note that there are exactly 6 objects in each row and each column.

                         111111
    1    1    1    1    1     1
  1    1    1    1    1       1
   1    1    1    1    1      1
 1    1    1    1    1        1
                    111111
    1   1   1   1   1        1
  1      1 1      1 1       1
   1  1       1  1  1      1
 1     1     1     11     1
          11111          1
    1  1  1       1  1     1
  1   1   1        1   1     1
   1     11     1     1   1
 1      1 1      1      1   1
               11111     1
    1 1      1 1      1     1
  1     1     11     1    1
   1   1   1   1        1    1
 1       1  1  1       1   1
     11111               1
    11     1     1     1  1
  1  1       1  1       1  1
   1 1      1      1 1      1
 1   1        1   1   1      1
1    1    1    1    1         1
1        1   1   1   1       1
1       1  1       1  1    1
1      1      1 1      1    1
1     1     1     1     1 1
11111                    1

Exercise 1. Refine the algorithm so that it uses only $M_{21}=105$, $M_{31}=186$, $M_{91}=910$, $M_{133}=1596$, i.e., without $M_{182}$.

Exercise 2. (Open problem) The smallest $n$ such that we can fill $8n$ rectangle-free objects in an $n\times n$ grid is 57 since $M_{57}=8\times57$ for $q=7$. What is the biggest $n$ such that we cannot fill $8n$ rectangle-free objects?


What is the optimal way to cut B chocolate bars to share equally between N people? What is the optimal way to cut B chocolate bars to share equally between N people?

Here is an example of different cuts for B = 5 chocolate bars and N = 6 people.

Strategy 1: cut each chocolate bar in 6 equal parts and, then, give 5 parts for each person. Number of cuts: 5 x 5 = 25.

Strategy 2: cut 3 bars in 2 equal parts and cut 2 parts in 3 equal parts and, then, give 1/2 bar and 1/3 bar for each person. Number of cuts: 3 x 1 + 2 x 2 = 7.

What is the optimal solution for the general problem?

Thanks, Humberto.

If optimal means having less cuts, can do this:

1. Line the chocolate bar up.
   [bar 0][bar 1][bar 2]

2. Treat that as a big bar.
   [big bar            ]

3. Divide the big bar equally.

Only about N cuts needed (if B < N)

If B > N, just give everyone equal number of bars. Then divide the remaining bars with the above algorithm.

Or 1 cut:

[bar 0]
  [bar 1]
    [bar 2]

cut vertically once.

I am sure there might be easier way to line it up... if optimal means that we don't need to use a ruler to measure the chocolates in real life.


Constructing regular expressions with given substring requirments I'm having trouble with this question about regular expressions:

  Let $L_1$ be the language of passwords containing at least one
  lowercase letter, at least one uppercase letter, and at least one
  number. Write down a regular expression that describes $L_1$.

This is my answer, but I'm not too sure about it. I let $\mathcal{A}$ be the alphabet, and attempted to cover all permutations. I think my answer is correct, but is there a simpler way to go about it?
\begin{equation*}
 (\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*) \cup
 (\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*) \cup
 (\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*) \cup
 (\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*) \cup
 (\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*)\cup
 (\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*)
\end{equation*}

I'm really stuck on this second part:

  Let $L_2$ be the language of "good" password. It is related to L1 by:
  \begin{equation*}  L_2=\{w\in L_1 : w \text{ has length } \geq 8\} \end{equation*} Specify a regular expression that describes $L_2$,
  without writing it down in full. What is the length of this regex?

I'm not sure about how to construct a regular expression using my answer for $L_1$. I thought it might be similar to the first part, where I could specify all the permutations.

Hint: Replace each sub-expression of the form $\Sigma^* A \Sigma^* B \Sigma^* C \Sigma^*$ with a union of expressions of the form $\Sigma^\alpha \Sigma^* A \Sigma^\beta \Sigma^* B \Sigma^\gamma \Sigma^* C \Sigma^d \Sigma^*$ for appropriate $\alpha,\beta,\gamma,\delta$.

Notice also the point of the exercise, namely that (plain) regular expressions aren't a good fit for describing passwords. We would really appreciate being able to intersect regular expressions (do you see how that helps?).


Data structure for finding the sum of edge weights on a path Let $T$ be a tree, and there is a weight function on the edges $w:E\to X$. $(X,\oplus)$ is a monoid structure.

Define $f(u,v) = \bigoplus_{i=1}^k w(e_i)$, where $e_1,\ldots,e_k$ is the unique path from $u$ to $v$.

Can we preprocess the tree, such that we can use linear space (or close to linear space), so we can answer queries $f(u,v)$ in $O(\mathrm{polylog} (n))$ monoid operations? The problem become more interesting if we allow removing edges and add edge between two vertices in distinct trees.

We can also ask the question on a DAG, with weights from a commutative monoid. We want to preprocess in linear time, and query the result of $f(u,v)= \sum_{e} w(e)$, where $e$ is in some path from $u$ to $v$, in $O(\mathrm{polylog} (n))$ time.

If we consider the very special case where the entire graph is just a path, then what we want is a dynamic version of a Fenwick tree. A finger tree can solve the problem in $O(\log n)$ time.

Static case. Suppose the tree is static.  Let $d$ denote the average depth of the nodes of the tree, taken over all nodes.  Then you can solve this problem with $O(nd)$ preprocessing, a data structure of size $O(nd)$, and query time of $O(1)$.  As a consequence, if the tree is balanced or of height $O(\lg n)$, the preprocessing and data structure size are $O(n \lg n)$ and the query time is $O(1)$.

Here's how.  My solution is inspired by Yuval's, but takes into account that we do not have an inverse.  Basically, you just build a map that stores mappings $(u,v) \mapsto f(u,v)$, where $u,v$ range over all pairs of tree nodes such that $u$ is an ancestor of $v$.   This has $O(nd)$ entries and can be computed in $O(nd)$ time during preprocessing.  Also, precompute a data structure to help you solve the least common ancestor problem.  Now, to compute $f(u,v)$ where $u,v$ are an arbitrary pair of nodes (not necessarily an ancestor of the other), find their least common ancestor $p$ and compute $f(u,v) = f(p,u) + f(p,v)$ (with the convention that $f(v,v)=0$ for all $v$).  Thus, queries can be solved in $O(1)$ time, using a sufficiently good algorithm for LCA.

It's also possible to get slightly better efficiency for the above scenario.  Instead of storing all mappings $(u,v) \mapsto f(u,v)$ where $u$ is an ancestor of $v$, we'll store just a subset of them.

Let $r$ denote the root.  Focusing on a single leaf $\ell$, we have a path from $r$ to $\ell$; if the leaf is at depth $d$, this path has length $d$.  So, we can build a balanced binary tree $T_\ell$ (akin to a Fenwick tree) over this path, where each node of $T_\ell$ corresponds to a mapping $(u,v) \mapsto f(u,v)$ (where $u$ is an ancestor of $v$ in the original tree $T$).  The root of $T_\ell$ is the mapping $(r,\ell) \mapsto f(r,\ell)$, corresponding to a path of length $d$.  It has two children, $(r,m) \mapsto f(r,m)$ and $f(m,\ell) \mapsto f(m,\ell)$, corresponding to two paths of length about $d/2$ (here $m$ is a node halfway along the path from $r$ to $\ell$).  Each leaf of $T_\ell$ represents a single edge in  the path from $r$ to $\ell$.  In this way, we get a tree $T_\ell$ of size $O(d)$, where $d$ is the depth of $\ell$ in the original tree $T$.

Now take the union of the $T_\ell$, over all leaves $\ell$ of the original tree $T$ (sharing common nodes in these trees).  This gives us a map that stores mappings $(u,v) \mapsto f(u,v)$, but now with a smaller subset of entries in the mapping than before.  Given any pair of nodes $p,v$ where $p$ is an ancestor of $v$, we can compute $f(p,v)$ in time $O(\lg d)$, where $d$ is the depth of $v$.  Therefore, we can compute $f(u,v)$ for arbitrary $u,v$ in time $O(\lg d)$, where $d$ is the depth of the deeper of $u,v$.

With this "forest of trees" scheme, the time to answer a single query is slightly more, but the size of the data structure is slightly less.  I don't know if this will be a win in practice, but it might be.  This scheme also has the advantage that, if the weight on an edge of $T$ is updated, you can fairly efficiently update the data structure.

There might be a smarter way to choose what subset of entries $(u,v)\mapsto f(u,v)$ to store in your data structure -- I'm not sure.

It's possible to extend these to the case of a static DAG, if you are promised that the length of the longest path  in the DAG is not too large  (if it is short and bushy/wide rather than long and narrow).


how to interpret the coefficients of binary logistic regression? I'm working on a kNN classifier to classify whether a text is written by a man or a woman on the basis of the most frequent words. However, a kNN doesn't show which features were the most important in the classification. I got the suggestion to fit a logistic regression on my training data and labels to see which words were the most important in the classification task.

Now I have a list of the top 20 positive words and coefficients and top 20 words with negative coefficients. I do not know how to interpret these. I can see that the logistic regression has the classes F and M (don't know which one is 0 and which is 1), but is it possible to argue that the positive coefficients belong to the F class and the negative belong to the M class?

I don't have the rep to comment, but the answer to your question is "sort of." It would take me too long to answer this question completely and with the proper care, so i will point you to a good resource
http://www.appstate.edu/~whiteheadjc/service/logit/intro.htm

There is a section midway through on interpreting your regression coefficients. In your specific case (as I imagine all of your independent variables only take on positive values), your interpretation is fine. If $b_1$ is the slope coefficient of an indicator variable for some word, then a 1 unit change in $b_1$ (i.e. if the word corresponding to $b_1$ is seen) corresponds to an $\exp{(b_{1})}$ change in the log odds of your model (e.g. the probability of the person being a boy is $\exp{(b_{1})}$  more likely). Hope this helps


If X is in NP-complete and complement(X) is in NP, show that for all Y in NP, complement(Y) is also in NP If X is in NP-complete and complement(X) is in NP, show that for all Y in NP, complement(Y) is also in NP.

I am struggling with figuring this out. I know this means Y can be reduced to X, so if I could solve X I could solve Y. I can't solve X, but I have a certifier for X and complement(X). I am having trouble combining the reductions and certifiers to find a certifier for complement(Y).

Note that

$$
A \leq B \iff \overline{A} \leq \overline{B}
$$

where $\overline{A}$ denotes the complement of $A$. Indeed, if $f$ is a reduction for either side, it is also a reduction for the other side (exercise: prove this using the definition of $\leq$).

From this, your statement quickly follows.


Which pretrained model will be best for my dataset? I am trying to build a classification algorithm having 28 classes. These classes consists of Logo of companies like adidas , Nike etc. I have very low dataset below than 100 images and greater than 70 images. I have trained CNN model but not got decent results . Accuracy is not good. I want to switch on pretrained model. I don't know which pretrained model should I use either VGG , ResNet etc. because I saw on Internet that you may use Pretrained model on  similar dataset but I have logo of companies , I don't know that any pre trained model is trained on such similar type of objects or not. How should I choose pre trained model that will performs well on my dataset.

There's no general answer.  In this field, you'll just have to try multiple approaches and see how well they work.  We usually won't know what will work best until we try it.
I can suggest three candidate approaches:

Get more data.

Use a pre-trained model and fine-tune it.  You can use any state-of-the-art model, pick a version that was pre-trained on ImageNet, and then fine-tune it (either fixing the first n-1 layers and training only the last layer; or training all layers, but with a smaller step size).

Use few-shot learning.  This will probably require more sophisticated methods and more study.

Aggressive data augmentation might be useful.


What is the state of the art in efficient boolean function operations? How do you most efficiently combine boolean functions with a large number of variables using AND, OR, and NOT?  The most up-to-date work that I can find on this subject is about 20 years old (Efficient data structures for Boolean functions).  Which search terms should I be using to explore this question?

Edit:

I am starting from about 200 simple boolean functions.  These are combined with each other using AND, OR, NOT, and XOR to give other boolean functions, which are then also combined using AND, OR, NOT, and XOR.  The process repeats about 3000 times, until a final combination gives me a single boolean expression.  I'm interested in that final expression.

Representing the functions as DNF or CNF makes certain operations (NOT and XOR) slow.  Representing the functions as ROBDDs is an option - are there any drawbacks here?  I'm not sure whether SMT solvers are useful here, because I am interested in the final equation rather than whether the equation is satisfiable.  What else should I be looking at?

The obvious method is to use BDDs.

Given a BDD for two boolean functions $f,g$, you can form a BDD for $f \land g$, $f \lor g$, $\neg f$, $f \implies g$, $f \oplus g$ (xor), and many other binary operations on them.  Also, given BDDs for $f,g$, you can test whether $f$ and $g$ are the same boolean function.

The worst-case behavior is that their size might grow to be exponential in $n$, the number of boolean variables, but empirically, the size often remains manageable in many real-world applications, e.g., when there is suitable structure in the underlying boolean functions.  In the model-checking world, designs with 50-200 boolean variables are routinely handled using BDDs.

It's also possible to manipulate boolean expressions in symbolic form, and then use SAT solvers or SMT solvers to test for equivalence.  This is another plausible alternative.

My advice is: try BDDs first, then if they don't scale well enough for your needs, you can try SAT-based solutions.  If that still doesn't work, come back to ask for more suggestions (providing more details about your specific setting and what you've tried).


TSP 200-approximation, given $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ for all nodes $x,y,z$ Input: complete, undirected graph $G=(V,E)$ and cost function $c$
Assume for all nodes $x,y,z \in V$:  $c(x,z)\le c(x,y) + 100\cdot c(y,z)$
Find a 200-approximation polynomial time algorithm for the input.
I've seen the regular 2-approximation algorithm for a graph that satisfies the triangle inequality.

Find the MST $T$ for the graph
Find Euler Cycle by doubling the edges in $T$
Find Hamiltonian Cycle by removing each vertex that appears more than once

If $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ , then $c(x,z)\le c(x,y) + c(y,z)$ , so I figure we can use the same approximation algorithm. But I'm not sure how to prove that this gives a 200-approximation.

This is not true.

If $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ , then $c(x,z)\le c(x,y) + c(y,z)$

However it is true that, for $x,z \in V$ with $x \neq z$, you have $c(x,z) \le 100 d(x,z)$.
To see this let $P$ be a shortest path from $x$ to $z$. The proof is by induction on the number of edges $|P|$ of $P$.
If $|P|=1$ then $c(x,z) = d(x,z) \le 100 d(x,z)$.
If $|P| \ge 2$ then, let $y$ be the vertex immediately preceding $z$ in $P$.
By inductive hypothesis $c(x, y) \le 100 d(x,y)$ and you have
$$
c(x,z) \le c(x,y) + 100 c(y,z) \le  100 d(x,y) + 100 c(y,z) =100 d(x,z). \quad \square
$$
Consider a MST $M$ of $G$ and let $T$ be a Euler tour of $M$, starting from an arbitrary vertex.
Let $v_0, v_1, \dots, v_{n-1}$ be the vertices in $V$ in the order they appear for the first time in $T$ and let $v_n = v_0$. Consider the tour $T'$ that visits $v_0, v_1, \dots, v_n$ in this order.
For $i=0, \dots, n-1$ let $T_i$ be the portion of the tour between the first occurrence of $v_i$ in $T$ and the next occurrence of $v_{i+1}$ in $T$.
Given any graph $H$, let $c(H)$ be the sum of costs of the edges in $H$.
Let $T^*$ an optimal tour of $G$.
You have:
$$
\begin{align*}
c(T') &= \sum_{i=0}^{n-1} c(v_i, v_{i+1}) \le 100 \sum_{i=0}^{n-1} d(v_i, v_{i+1}) \le 100 \sum_{i=0}^{n-1} c(T_i) \\
&\le 100 c(T) \le 200 c(M) \le 200 c(T^*).
\end{align*}
$$


Represent string as concatenations If $S_1,S_2$ are set of strings, then $S_1S_2 = \{s_1s_2|s_1\in S_1, s_2\in S_2\}$. $S^0=\{\epsilon\}$, $\epsilon$ is the empty string. $S^n = S^{n-1}S$.

Two related problems about represent string as concatenation of other strings.

Given a finite set $S$ of strings, how to decide if there exist a string can be written as concatenations of elements in $S$ in two different ways?
Given a finite set $S$ of strings and $n$, how can one compute the smallest set of strings $T$, such that $S\subset T^n$?

(Bonus: what about infinite $S$, at least when it's regular? For the second problem when $S$ is infinite, we might ask to find a minimal $T$ under set inclusion.)

I will try (1) and go for infinite (the bonus).

The finite case is called the code problem: finding possible decompositions is like decoding. Its classical algorithm is called Sardinas–Patterson. It is not immediately clear it is a finite search space. The lengths of the decomposition might be long. Still it is not Post Correspondence as that has additional restrictions.

The finite case has a simple regular language solution: for every pair of distinct $s,t \in S$ test whether the regular set $s S^* \cap t S^*$ is empty. (The Sardinas-Patterson tries that "in parallel".) This does not work in the infinite case as there would be infinitely many $s,t$ to test.

In the infinite (but regular) case I would build a new finite state automaton based on an automaton for $S$. It simulates in parallel the two different decompositions by keeping track of a pair of states, one for each decomposition. On a letter both pairs make a step on the same letter. In a final state each component may either restart (it has seen an element in $S$) or proceed (trying to find a longer word in $S$). Now we need one additional boolean addition to the state-pair as we need to check whether the two components made different choices in at least one point. Accept if both simulations end in a final state (and we have seen a point where the two decompositions differed). Now again there are no two different decompositions for the same string iff the language of the automaton is empty.

And indeed, for context-free the problem must be undicidable, but I do not have a reference at hand now.


Two recurrences for the change-making problem with repetition The change-making problem with unbounded repetition is:

  Input: Unlimited quantities of coins with values $x_1, \ldots, x_n$ and an amount $v$.
  Output: Can the given $v$ amount of money be made with these coins?

The first recurrence is based on the subproblems of
$C[w]$: can $w$ be made with these coins?

$$
  C[w] = \bigvee_{i: x_i \le w} C[w-x_i].
$$

The second recurrence is based on the subproblems of $C[i,w]$: can $w$ be made with coins $x_1, \ldots, x_i$?

$$
  C[i,w] = (C[i, w-x_i] \land w \ge x_i) \lor C[i-1, w].
$$
The recurrence consider both cases of whether $x_i$ is used or not.

Problem:
I think both recurrences are correct. Therefore, I want to understand their connections.

Specifically, how are they equivalent (if both are correct, of course) in terms of the subproblems they solve.

Can we transform one to another by, for instance, introducing a second variable to the first one or eliminating one variable from the second one?

First, the number of subproblems and dependencies among these subproblems for the first recurrence are $v$ and $nv$ respectively, while they are $nv$ and $2nv$ respectively for the second one.

Pictorially, the subproblem-dependency graph of the first recurrence is a 1D array and that of the second one is a 2D table.

Informally, the subproblem-dependency graph of the second recurrence can be regarded as a "compacted" version of that of the first one in the sense that the 2D table is compressed into a 1D array through the clause $\lor C[i−1,w]$ in the second recurrence.

Formally, inspired by the comment made by @Raphael, if we expand $C[i−1,w]$ recursively in the second recurrence, we get (ignoring the $w \ge x_i$ details)

$$
\begin{align*}
  C[i,w] &= C[i, w-x_i] \lor C[i-1, w] \\
         &= C[i, w-x_i] \lor (C[i-1, w-x_{i-1}] \lor C[i-2, w]) \\
         &= C[i, w-x_i] \lor C[i-1, w-x_{i-1}] \lor C[i-2, w-x_{i-2}] \lor C[i-3, w] \\
         &= \cdots  \\
         &= \bigvee_{j \leq i: x_j \le w} C[j, w-x_j]
\end{align*}
$$

Therefore, we can conclude that $C[n,w] = C[w]$.


Reference request: Introduction to reinforcement learning with hand calculation examples For me, the most difficulty when it comes to learning about reinforcement learning is that there is not much to learn in the sense that without running some algorithm, it is very difficult to get a sense of how abstract RL framework is done in practice.

This is in contrast to a lot of the stuff you learn in related courses on optimization, game theory or even pure algorithm. In each of these courses, you have a large amount of examples where you can hand compute to obtain the solution (for algorithms, you can solve for shortest path etc by hand). It is also easy to compute the gradient, and calculate the value at each step using gradient descent algorithm for example in an optimization class, or compute the Nash equilibria in simple games. This allows one to better appreciate how the algorithms work.

Even for supervised machine learning, algorithms such as ANN, KNN, SVM etc. can be analyzed by hand, using step by step calculation.  However, this does not seem to be the case for reinforcement learning. Every article I have came across basically runs through the whole "state, action, reward" framework then goes on talking about MDP and Q, TD learning. Then applications that usually follows are not something that are easily programmed on a first try i.e. robotic acrobat, pole cart system etc.

Are there any introduction or tutorial to reinforcement learning where a problem is solved by hand? Meaning, you can actually compute the values at each step following a particular technique and perhaps obtain the optimal solution.

Even if not, are there any mathematical convergence analysis of reinforcement learning algorithms?

Poole and Mackworth's Artificial Intelligence: Foundations of Computational Agents, fully available online, has one such example for Q-learning.

Sutton & Barto's Reinforcement Learning: An Introduction, also online, has a few tiny iterative examples here and there.

Isbell & Littman's udacity course on RL has examples, quizzes, and programming exercises in Java.


How likely is it that a computer miscalculates 1+1? Of course, normally a fully-functional computer will calculate 1+1=2. However, the physics governing the behavior of a chip is quantum mechanical. So in principle there is a certain probability that something goes wrong and we get the result 1+1=x where x≠2. In my opinion this probability should get bigger the smaller the chips are becoming.

So the question is: How likely is this event? Can one give an order of magnitude?

P.S. I'm not talking about quantum computing, just "standard" computers nowadays everyone has on their desk.

The probability of read error is bigger than write error, so there is a chance for bitflip on either of $1$ which might occur anywhere.
I can offer description of JVM attack which is not exactly the answer, but shows how much effort is needed to induce bitflips, tells about softerrors and a very successful attack on JVM, given good heat ;).

The probability of error grows the most related with heat dissipation problems, and making chip smaller include it's higher efficiency (performance per watt).

Anyway there is bad assumption - making chip smaller gives more errors - if this were true over time CPUs would generate noticeable amount of errors today.

Please check also this error rate study. With calculating probability of error there is a problem - this is hardware dependent and the most of hardware actually has errors, but they get corrected at several levels, so they do not occur for user, and with invalid / broken piece machine crashes are to often to perform test.


Fractional vertex cover number may not be feasible? Very confusing! For my project, I try to use minimum fractional vertex cover number (MFVC). (Please find below definition details) MFVC can be formulated as optimal solution of a linear program relaxation.

However I find that every linear program relaxation is either infeasible, unbounded, or has an optimum solution.

Does is mean that MFVC may not exist, or may not be a finite number, but MFVC is less or equal to minimum vertex cover number? Very confusing! :(

Many thanks!

Definitions:

K-uniform hypergraph:

Minimum fractional vertex cover number (MFVC): link (on page 8)

MFVC as linear programming relaxation:

The minimum fractionl vertex cover $\tau^* (G)$ in a k-uniform hypergraph $G=(V,E)$ is
 $\min \sum_{v\in V}w (v)$

such that $0 \le w(v) \le 1$,

and for each $e \in E$, we have $\sum_{v\in e} w(v) \ge 1$.

The linear program defining the minimum fractional vertex cover always has an optimal solution. The fact that some linear programs are infeasible or unbounded doesn’t mean that every linear program is infeasible or unbounded.

To give another example, sometimes you can’t divide by $x$. But if $x$ is a positive integer, then you can always divide by $x$. This in no way contradicts the fact that there exist $x$ that you can’t divide by - it just means that this complication doesn’t occur for positive integers.

To see that the minimum fractional vertex cover always exists, we have to show that the relaxation is feasible and bounded (from below). To see that it is feasible, notice that if you assign $w(v) = 1$ for all $v$, then you get a feasible solution. To see that it is bounded from below, notice that $w(v) \geq 0$ guarantees that the objective functions is always non-negative.


Isn't this Commentz-Walter algorithm buggy? I've been trying to piece together an implementation of the Commentz-Walter string search algorithm. The idea is to construct a state machine from a trie, working backwards from the earliest feasible position.
The paper is available here, though it is a scanned printout from 40 years ago. I have also found a better quality pseudocode for the core search loop (image below). But it seems that neither description of the algorithm provides a way to 'back out' of a dead end: The current trie node v is only ever assigned to its own child. It seems that there is a missing step: once the inner loop has exhausted the possibility of a match, the current node should be changed.
An example of an input that fails my implementation tests is to find the string bb in abb: The search begins on the first b, finds that ab is invalid, and fails
Can anyone put me right?

Pseudocode of search algorithm:

I figured it out, you have to reset v to root at the same time as you reset j to 0 (in fact if you just add depth to your node, you can skip j and just use v.depth)


Equivalence of Turing Machines Consider the following two arguments

  "For every non deterministic TM M1 there exists an equivalent
  deterministic machine M2 recognizing the same language."
  "Equivalence of two Turing Machines is undecidable"

These two arguments seem a bit contradicting to me.
What should I conclude from these two arguments?

These arguments are not really related, on several levels.

The first is that existence and computability are not the same thing. That is, even if there exists some object (e.g. a TM), it does not mean that finding (or computing) such an object can be done using a TM.

However, there is a more basic difference between the two statements. The first says that for every TM $M_1$, there exists some equivalent machine $M_2$. The second statement is that deciding, given $M_1$ and $M_2$, whether these two specific machines are equivalent, is undecidable.

Just to emphasize the difference, consider the following problem: given a TM $M_1$, is there some TM $M_2$, that is different from $M_1$, which is equivalent to $M_1$? This problem is trivial - the answer is always "yes" (e.g. just add a redundant state to $M_1$).


Computational complexity vs Computational cost Is there a difference between the computational complexity and computational cost of an algorithm?

To answer your question as stated: "computational complexity" typically refers to the $\Theta$-class of a certain (often implicit) measure of computational cost.
That said, I prefer to use the terms like this:

Use "complexity" when talking about problems. For instance, you can say "sorting has $\Theta(n \log n)$ worst-case time complexity (in the comparison model)".

Use "costs" when talking about algorithms. You would say, "Mergesort has a worst-case running-time cost in $\Theta(n \log n)$ (under the RAM model)".

This is consistent with common use, that is every expert will understand what you're saying, but avoids using the term "complexity" for different things.
Rationale

Complexity theory and analysis of algorithms (AofA) are distinct fields with different goals and techniques. It's not helpful to use terminology that muddles the two together.
Side note: teaching only the complexity-theory side of things makes large parts of the AofA literature inaccessible to computer science graduate, which I think is a shame. See the work of Flajolet and Sedgewick if you're interested in these things.

"Cost", other than "complexity", is used for precise measures like, say, "the number of comparisons" often analysed in sorting. Such a cost measure is (given an algorithm and a machine model) a well-defined function on the inputs (other than "time") and can be analysed rigorously.

Every algorithm has many cost measures with different asymptotic behavious; in sorting, for instance, number of comparisons, swaps, and many more. Therefore, asking for "the complexity of the algorithm" is an oversimplification, and only meaningful under certain assumptions/conventions.

The analysis of cost measures can yield testable hypotheses, if it's more precise than Landau bounds. "Complexity" results are not testable.

"Complexity" of an algorithm can be rigorously defined in terms of cost measures, if one so desires. The other way around does not work.
For instance, an algorithm's "(time) complexity" is usually taken to mean the $\Theta$-class of dominant, additive cost measure that is defined by a function on basic operations. However, I consider this practice confusing and thus harmful (cf. item 1), and prefer to say "[cost measure] is in $\Theta(\_)$".


Proving that $L = \{ a^{n!} \ | \ n \geq 0 \}$ is not regular Let $L$ a language over $X = \{a\}$ defined as follow :

$$L = \{ a^{n!} \ | \ n \geq 0 \}$$

I want to prove that $L$ isn't regular, I have searched in the forum for an equivalent question, but I found nothing. If it's a duplicate, I apologize and I'll be glad if you provide me the link of the duplicated question.

I'll show here what I have done, using the pumping lemma.

Suppose that $L$ is regular, let $n \in \mathbb{N}^*$ and $\omega = a^{n!}$. We have $\omega \in L$ and $|\omega| \geq n$. Thus, there exist $x, y, z \in X$ so as :

$a^{n!} = xyz$
$y \neq \epsilon$
$|xy| \leq n$
$xy^kz \in L, \quad \forall k \geq 0$

Because of fact 3, $xy = a^k$ and $y = a^j$ with $k \leq n$ and $1 \leq j \leq n$. Thus :

$$a^{n!} = a^{k - j}.a^{j}.a^{n! - k}$$

By fact 4, we must have $a^{k - j}.a^{n! - k} = a^{n! - j} \in L$.

In addition, because $1 \leq j \leq n$, the following is true :

$$n! - n \leq n! - j \lneq n!$$

The final result that I need is that $(n - 1)! \lneq n! - n$. Using this I can deduce :

$$(n - 1)! \lneq n! - j \lneq n!$$

Showing that $n! - j$ can't be the factorial of an integer, giving the contradiction $a^{n! - j} \notin L$. I have tried to prove the final result, but I didn't succeed. It is not true for the first values of $n$, I have tried to consider multiple cases but went for nothing.

So I ask for your advice, maybe I am going wrong and didn't applied the pumping lemma with a word that leads to contradiction.

The easiest way is probably to use the pumping lemma on the complement language $\overline{L} = \{ a^m : m \neq n! \}$. Suppose that $L$ were regular. Than $\overline{L}$ would be regular. According to the pumping lemma, there is a pumping length $p$ such that every word $w$ of length at least $p$ in $\overline{L}$ has a decomposition $w = xyz$ such that $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in \overline{L}$ for all $i \geq 0$. Take $w = a^{p\cdot p!} \in \overline{L}$ (without loss of generality, $p > 1$). Suppose that the decomposition is $w=xyz$, where $y=a^t$. Since $t \leq p$, it follows that $t \mid p!$. But then $xy^{1+p!/t}z = a^{p\cdot p! + p!} = a^{(p+1)!} \notin \overline{L}$.


What's the purpose of the non-deterministic Turing machine? (*) Acronyms

NTDM := non-deterministic Turing machine.
TM := deterministic Turing machine.

(*) Consider the following idea

The NTDM is able to follow, in parallel, all paths of the tree of the universe of solution.  Suppose that in some point in time, for a certain problem, a new theorem is discovered that tells us that we need not worry about certain branches of the universe of solution because those branches yield no solution.  Then in some future point in time, a new theorem appears telling us we need not worry about some other branches of the tree and so on.  New theorems keep on being proved such that eventually there's only a single path to be followed in the tree of the universe of solution.  The problem therefore affords a polynomial solution since at every branch, it tells us where to go.

So the concept of NDTM accounts for all future scientific development.  Therefore, if a problem cannot be solved in polynomial time in the NDTM, then it's not in NP and therefore has no chance of being polynomial, no matter how science might advance.

This seems to be a good reason for the concept.  Is there any flaw in this argument?  In parallel, I'm interested in the question: why was the NDTM invented?

I will try to address why the concepts of NDTM and NP are useful, and possibly what motivated their study.

NDTM is one of many variants of turing mahcine. For example, the classical (deterministic) Turing machine can be equipped with multiple heads and tapes, randomness or quantum states. It can also be constrained by a limited alphabet, limited tape or pre-determined head-movements (see here).

A TM is said to decide a language (a set of words using a pre-defined alphabet), if it can halt on any input written on the tape, and accept precisely inputs belonging to the language. A language is called decidable if any TM decides it. Similarly, a function $f$ on natural numbers is said to be computable if there exists a TM which, given an input $n$, halts with $f(n)$ written on the input tape.

It turns out that all of the mentioned variations of TMs (including NDTM) are equivalent in the set of functions they can compute (similarly, the languages they can decide). This holds for other, much more different models than TMs, and has led to the Church-Turing thesis, which informally hypothesizes that any "reasonable" model of computation is equivalent to the classical Turing machine. In this aspect, NDTMs are useful as an example of fantastical computational models that are nonetheless as strong as a classical TM, supporting the Church-Turing thesis.

As far as I understand (see here and here for history), Turing himself did not focus on complexity classes, and so the previous reason might have been his sole motivation. However, later on it was discovered that different TM variants are not equivalent in the set of problems (languages and functions) they can solve in a certain amount of computation steps (time), bound on working-tape size (memory) and success probability. With this finer resolution, it turns out that the different models are very different, resulting in a zoo of complexity classes for problems.

I hope this is helps show why NDTMs (and the NP complexity class) are not a definite model for the problems science could potentially solve efficiently, but just one of many variations of computational models (less realistic than random and quantum machines, for example). There are, however, some reasons for why the specific class of nondeterministic polynomial time ($NP$) is such a popular attraction of the zoo:

It is relatively easy to explain and reason about. While researchers are working on many other open problems in complexity theory, the question of whether $P\neq NP$ requires only basic knowledge in math to understand, and the concept seems so intuitive that it invites many solution attempts from amateur researchers.
Whether a problem is solvable in polynomial time in a computational model is seen as an approximate measure of practical tractability (this is Cobham's thesis).
Any complexity bound derived by NDTMs can be seen as a bound on verification time by classical TMs (see here for why). Since classical TMs are used as models of practical computation, this has practical implications.
Many real-world important problems just happen to be not just in $NP$, but $NP$-complete. This means that if $NP$ is indeed a different complexity class than $P$, all of these important problems are not solvable in polynomial time with classical TMs.

Note that the fourth reason is unrelated to how realistic NDTMs are as a computational models (compared to classical TMs or other variants), or to any initial motivation for the invention of the concept. NP-complete problems are just surprisingly common in real life, and the scientific interest in them mirrors that.


Applying Akra–Bazzi with an unbounded number of summands The Akra–Bazzi method handles recurrences of the form
$$
f(n) = \sum_{l=1}^k a_l f(n/b_l).
$$
Does it work when then number of $a \cdot f(n/b)$ is not finite, meaning that we have a sum that depends on our input $n$?
What about this:
$$ f(n) = \sum_{l=1}^{n} f(n/3^l) $$
Can I say that we need to find the $p$ so that
$$ \sum_{j=1}^{n} (\frac{1}{3^j})^p  =1,$$
and because $n \rightarrow \infty$ we can say it is an infinite geometric sum?  Or because $n$ is our input we can't say that, and the Akra–Bazzi method fails to deal with this kind of stuff? There is no internet site I found that says $k$ (which in Wikipedia is the number of $f(n/b)$) needs to be finite.

Quoting from Wikipedia, the Akra–Bazzi method applies to recurrences of the form
$$
T(x) = g(x) + \sum_{i=1}^k a_i T(b_i x + h_i(x))
$$
where $a_i,b_i$ are constant, $a_i>0$, $0<b_i<1$, $g$ is polynomially bounded, and $h$ is "sublinear enough".
Your recurrence is not of this form, so you cannot apply the Akra–Bazzi method. It could be that the techniques used to prove the Akra–Bazzi theorem also apply to your case, but you will have to look at the proof.

Notice that
$$
f(n) - f(n/3) = \sum_{i=1}^{\log_3 n} f(n/3^i) - \sum_{i=1}^{\log_3 (n/3)} f(n/3^{i+1}) = f(n/3),
$$
and so $f$ satisfies the recurrence
$$
f(n) = 2f(n/3).
$$
In particular,
$$
f(n) = 2^{\log_3 n} f(1) = n^{\log_3 2} f(1).
$$
(Throughout, we are assuming that $n = 3^k$.)


How to mark things in the input? Sipser theorem 4.4*
$E_{DFA} = \{ \langle A \rangle \mid \text{A is a DFA and } L(A)=\emptyset\}$ is decidable.

I could not quite understand the solution, I'll quote it:

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

Mark the start state of A

Repeat until no new states get marked:

Mark any state that has a transition coming into it from any state that is already marked.

If no accept state is marked, accept; otherwise, reject.

My question is, what does it mean to even 'mark' something in the encoding? how do we do this? The encoding is merely a word from $\{A,c\}$, how would you 'mark' states?

It's just a colloquialism.  It means, you keep a set of states that have been marked.  Initially the set is empty.  When you mark a state, you add it to that set.


How can I detect carry and overflow What is the diffrence between a carry bit and overflow

Carry is generally used for unsigned arithmetic and overflow is used for signed arithmetic.

This unsigned 8-bit operation results in Carry, but no overflow (the sign of the result is correct):

0xC0 + 0xD8 = 0x98

If we're doing unsigned 8-bit arithmetic, that's fine and we're only interested in the carry bit in this case, which tells us that the "correct" answer is actually 0x198.

If we look at the same operation and the same operand values, but consider that the operands are signed, we have the equivalent:

-0x40 + -0x28 = -0x68

In this case, there is also no "overflow" and the result of the arithmetic is correct.

Consider this unsigned operation, however:

0x70 + 0x68 = 0xD8

No overflow here -- and no carry. The unsigned arithmetic is simple. But now look at the operands as signed values:

0x70 + -0x98 = 0x28

The answer is obviously wrong. We have subtracted a larger number from a smaller one and ended up with a positive value. The carry is not set here, so it doesn't offer a clue of the problem. The overflow flag reveals that the "correct" signed answer is -0x28.

source


Complexity of factoring products of distinct prime numbers Problem: Input is an integer number $x$ that we know factors as $p_{i_1}\cdot p_{i_2}\ldots p_{i_n}$, where the $p_{i_j}$'s are distinct prime numbers. Output is the above factorization of $x$.

Do you know any results/references for the time complexity of this factoring problem?

Note: If the $p_{i_j}$'s are not assumed distinct, then the problem is just integer factorization. This is a very special case.

As far as I know, there are no non-trivial lower bounds on factoring, and in particular, no variant is conjectured to be NP-hard. (While factoring is not a decision problem per se, you can make up a corresponding decision problem that gives the $k$bit of the $\ell$th smallest factor.)

As far as algorithms go, there are a great many of them, including the following subexponential ones:

Quadratic sieve: this factors an integer $n$ in time $2^{O(\sqrt{\log n\log\log n})}$. There are many variants of this algorithm resulting in different constants for the big O, and one of them (due to Dixon) provably has the stated running time.
Elliptic curve method: this factors an integer $n$ with smallest prime factor $p$ in time $2^{O(\sqrt{\log p \log\log p})}$ (in general, this is the time it takes to find the factor $p$ rather than the complete factorization). No variant of this algorithm has a provable running time guarantee. The algorithm relies on the fact that random elliptic curves modulo $p$ have a certain order (number of points) distribution, and this empirically verifiable property isn't proven. (What you really need to know is the probability that the order is $\alpha$-smooth, whose conjectured behavior is satisfied for any reasonably smooth probability distribution.)
Number-field sieve: this factors an integer $n$ in time $2^{O(\sqrt[3]{\log n (\log \log n)^2})}$. No variant of this algorithm has a provable running time guarantee. The algorithm relies on the probability that a random element of a number field is smooth (in terms of its norm), a property which can be empirically verified but is unproven.

In practice, one first runs simpler algorithm which are able to find small prime factors more quickly. Some of the algorithms might run into problem if all prime factors are repeated, which is ruled out by your constraints, but I can't think of any concrete example.

There is no consensus on the conjectured complexity of the problem. Recent advances in the related discrete logarithm problem suggest that factoring might be in quasipolynomial time, and some people (Charles Rackoff, for example) wouldn't even rule out a polynomial algorithm for factoring. Others would concede that the number-field sieve algorithm might not be optimal, but that factoring should require time $2^{\Omega((\log n)^c)}$ for some $c > 0$.


Simple examples of Artificial Intelligence I am having trouble understanding the concept of AI.

Is AI just a software that uses Probability, Linear Algebra and some advanced Mathematics to make independent decision ?

Please give me some simple examples of AI.

Artificial Intelligence is a catch-all term for a large collection of everything from philosophical questions down to very specific programming techniques.

At heart, AI comes from the question is it possible to build a machine that displays intelligent behavior to the same level as human beings? This is often clarified with examples like, can we build a machine that plays chess, composes a sonnet, tells a joke or recognizes kittens. Investigating this question has led to the distinctions between strong and weak AI, and thought-experiments like the Turing test and the Chinese room.

On the more practical side, there is a collection of techniques that are being used to (partially) solve some of these problems. For instance, we can build a machine that beats any human at chess or checkers. Computers can recognize objects in images with reasonable accuracy. They can diagnose diseases, sometimes better than doctors, they can parse a sentence into its constituents and make a reasonable mapping to the meaning behind it.

Many of these algorithms and techniques use probability, linear algebra, logic and a variety of other subjects, but that's just a matter of using what works. There are plenty of systems that use linear algebra that have nothing to do with AI. What makes a technique AI is that, in some sense, it attempts to behave intelligently.

A precise definition beyond that is difficult to give. The trouble with defining AI is that it's the study of something that doesn't exist yet, and we don't know that it ever will. But we're pretty sure that we'll know it if we see it.


shortest distance vs shortest path This question might be redundant but I want to verify my understanding further. Suppose I have this linear directed graph:

$$S \overset{2}{\to} A \overset{1}{\to} B \overset{3}{\to} E \overset{1}\to D.$$

Here, $S$ is the source, $D$ is the target, and numbers indicate to edge weight:

When taking about shortest path, do we only count the number of edges? So in this example, shortest paths from $S$ to $D$ is 4.
Thus, when taking about shortest distance, we find the sum of the edges weights. So in this example, shortest distance from $S$ to $D$ is 7.

The reason why I elaborate this question using example is that I've seen plently of answers when I google this question but it seems they treat the work path and distance in similar way which is counting the number of edges (hops).

If it is ambiguous (as in this case), a well-written text should indicate what it means.  If it doesn't, you might have to guess.  Sometimes people are sloppy or imprecise, or rely on you to infer what they mean from context.  There's certainly no guarantee that people will use language the way you describe -- it's not a standard assumption you can make.

In a graph without weights on the edges, the situation is clear, and we will use "shortest path" to mean the path with the fewest edges, and use "distance" to mean the number of edges.  In such a graph, the notion of number of edges and sum of edge weights coincides (since we assume each edge has weight 1), so there's no distinction to draw.  Thus, in that situation, we'd use the two words similarly.

In a graph with weights (lengths) on the edges, the most common situation is probably to use "shortest" path to mean the path with the smallest sum of edge weights, and use "distance" to refer to the length (sum of edge weights) of the shortest path.  In other words, when there are weights (lengths) on the edges, the most common situation is that we never refer to anything involving the number of edges on the path.

But sometimes we have a graph with weights (lengths) on the edges, and we want to talk about two different distance metrics: the number of edges on the path, and the sum of the weights on the edges on the path.  Then it's anyone's guess what terminology people will use; I don't think there's any accepted standard.  In this situation, I think you have to hope that the writer defines their terms, or try to infer their meaning from context.


"Uniform" Set Cover Approximation? The (optimization version of) Set Cover problem is the following: given a "universe" set $S$ and a collection of subsets $S_1, \cdots, S_m \subseteq S$, we want to find the minimum cardinality set of $k$ elements $\{i_1, \cdots, i_k\}$ such that $\bigcup_{i=1}^k S_{i_j} = S$.

It is a well-known result in an introductory approximation algorithms class that this problem has no $O(\log n)$-factor approximation unless $P = NP$.

However, I'm interested in a restricted version of the problem: suppose that $|S_i| = n$ for all $i$ (i.e., all the subsets are exactly the same size). This problem turns out to still be $NP$-complete, but is there a better approximation ratio one can achieve?

I don't know if there is terminology for the problem (I dubbed it "uniform" here), because searching through Google Scholar and the arXiv has not yielded much.

No, one can't achieve a better approximation ratio for your problem.  This follows by a simple padding argument.

Let $S_1^*,\dots,S_m^* \subseteq S^*$ be an instance of ordinary set cover (where the sizes of the sets are not restricted to be the same).  Let $n = |S|$.  Define $S^* = S \cup \{1,2,\dots,n\}$ where it is assumed that $1,2,\dots,n$ represent $n$ new symbols not found in $S$.  Also define $S_i = S^*_i \cup \{1,2,\dots,n-|S^*_i|\}$ and $S_{m+1} = \{1,2,\dots,n\}$.  Then $S_1,\dots,S_m,S_{m+1} \subseteq S$ form an instance of your uniform set cover problem; by construction, the sets $S_1,\dots,S_m$ all have the same size.  Moreover, the minimum cardinality cover for the original problem $S^*$ differs in size from the minimum cardinality cover for the uniform problem $S$ by at most one, since given any solution $\{i_1,\dots,i_k\}$ for the original problem we obtain a valid solution $\{i_1,\dots,i_k,m\}$ for the uniform problem, and vice versa, any valid solution for the uniform problem is also a solution for the original problem.

It follows from this reduction that uniform set cover has the same approximation factor as ordinary set cover.  Thus, all the standard approximability results for set cover carry over to your problem as well.