Minimal positive difference of a mulitset of real numbers Motivated by Max-Flow: Detect if a given edge is found in some Min-Cut,  I'd like to ask the following questions:

Given a multiset of real numbers $B$, how hard is it to compute the minimal positive difference $\delta_\min$
$$\delta(B_1,B_2)=\left|\sum_{b\in B_1}b-\sum_{b\in B_2}b\right|$$
taken over all partitions $B_1\cup B_2=B$ of $B$ such that  $\bf\delta(B_1,B_2)>0$?
How hard is it to find a lower bound $\delta_- >0$ for $\delta_\min$?

Observe that (2) is easy for rational numbers, as you can compute the least common denominator $d$ and every positive difference is a multiple of $\frac{1}{d}$.

Assume that all $b\in B$ are from some subset (closed under addition and symmetric difference) of $\mathbb{R}$ for which we do have a representation by finite strings and all basic operations are performable in at most polynomial time.

Original formulation

(Originally, the OP was interested in the minimum absolute difference rather than the minimum non-zero absolute difference.)

You are asking two different questions. For the first, consider the restricted version in which all numbers are rational, and the decision variant in which the problem is to decide whether your expression is at most some $\delta$. This problem is NP-complete by reduction from PARTITION. (Wlog all numbers are integers, and you can ask whether the difference is at most $1/2$.)

Your other question concerns the decision variant in which the problem is to decide whether your expression is at least some $\delta$. This problem is coNP-complete, and so unless NP=coNP, no nice lower bounds exist (that is, there are no polysize witnesses that the minimal difference is at least $\delta$ which can verified in polytime).

Revision 1

(The question has been changed, and now we are looking for the minimum non-zero absolute difference.)

The problem is NP-complete by reduction from PARTITION. This time assume all numbers are integers, and add to them the additional number $1/3$. Deciding whether the minimal non-zero absolute difference is at most $1/3$ is tantamount to solving PARTITION, and so is NP-complete.


Minimise given size using dynamic programming Given numbers $0<x_1<x_2< \dots<x_{n^2}<1,$ for every subset of $n$ of them $x_{i_1}<x_{i_2}< \dots<x_{i_n},$ let us consider the size: $$\max\{x_{i_1}, x_{i_2}-x_{i_1}, x_{i_3}-x_{i_2},\dots,x_{i_n}-x_{i_{n-1}},1-x_{i_n}\}$$
Give an algorithm to find the minimal size that subset of $n$ numbers can achieve.

My thoughts:
I would like to use dynamic programming.
I started by defining the following:
$$d(1) = x_{i_1}, d(j)=\max\{d(j-1), x_{i_j}-x_{i_{j-1}}\}$$
The solution to the problem will have to minimise the following:
$$\max\{d(n),1-x_{i_n}\}$$

I got stuck here, and my question is how can I continue to finish the solution.
Any help is appreciated.

A dynamic programming approach would be:
$f (p, k)$ is the minimum size when we considered prefix $\{x_1, x_2, \ldots, x_p\}$, and selected exactly $k$ items from it, the last one being $x_p$.
We add sentinels $x_0 = 0$ and $x_{n^2 + 1} = 1$ for our comfort.

Base: $f (0, 0) = 0$.

Transitions: $f (p, k) = \min\limits_{q = 1, 2, \ldots, p - 1} \max \left\{f (q, k - 1), x_p - x_q\right\}$.

Answer: $f (n^2 + 1, n + 1)$, the point number $n + 1$ being the added value $x_{n^2 + 1} = 1$.

In total, this takes $O(n^2)$ to calculate a single $f (p, k)$, and there are $O (n^3)$ such values, so the approach will take $O(n^5)$ time and $O(n^3)$ memory.

The memory could be reduced to $O(n^2)$ by calculating iteratively, like:

for k = 1, 2, ..., n+1:
    for p = 1, 2, ..., n^2 + 1:
        calculate f (p, k)

And storing $f (p, k)$ only for the current and the previous values of $k$ at every moment: the storage strategy can be to store $f (p, k)$ in f[p][k mod 2].

The time could be perhaps reduced to $O(n^3)$ by altering the function to optimize the $O (n^2)$ transition cost to something like $O (1)$ amortized.
But instead, let us consider another approach.

Say we want the answer to be at most $s$.
We can then greedily construct a subset.
First, let $x_{i_1}$ be the greatest possible: $i_1 = \max i : x_i \le s$.
Next, let $x_{i_2}$ be the greatest possible: $i_2 = \max i: x_i - x_{i_1} \le s$.
Then define $i_3 = \max i: x_i - x_{i_2} \le s$, and so on.
If this leads to $x_{i_n}$ such that $1 - x_{i_n} > s$, the answer can't be $s$.
Otherwise, we just constructed a subset of $\le n$ elements with the answer at most $s$.
As the value $i$ is always increasing, for a given fixed value $s$, the check whether $s$ can be the answer takes $O (n^2)$ time and $O (1)$ additional memory.

What's left is to run a binary search over the value $s$, and for each candidate $s$, execute the greedy algorithm above.
The number of binary search iterations can be $\log n$ (there are $O (n^4)$ possible candidates for $s$), or $\log C$ where $C$ is the required precision.
For example, if all $x_i$ are integers from $0$ to $L$, we have a binary search over integers from $0$ to $L \cdot n^2$, so it will complete in $O (\log (L \cdot n^2))$.

In total, this approach takes $O (n^2 \log n)$ or $O (n^2 \log C)$, which is better than an optimized dynamic programming approach would achieve.


Writing programs with a block programming environment vs. Writing programs using high level prgramming language I'm a GCSE Computing student and I've been asked to compare writing programs in a block programming environment (I think this means using programs such as Scratch or App Inventor but I'm not entirely sure) compared to writing programs using high level programming languages such as Python, Java etc.
I'm honestly not trying to ask you to do my work for me, I just desperately need some help on the advantages and disadvantages of both ways of writing programs because we haven't really been taught it by my teacher and I haven't found much on the Internet about it.

Scratch is a Turing-complete language, so any problem that can be solved with computers can be solved using Scratch (just like Python or Java).  However, you would have to reduce the problem to one that can be solved with Scratch.

In application, Scratch can't do anything that you may be interested in as an engineer, such as hardware interfacing.


Which one of these two sets is computably enumerable? M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language.

{M : |L(M)| <= 330}
{M : |L(M)| >= 330}

I don't quite understand what this question is asking. Does the first question mean  M accepts at most 330 inputs?

My thoughts:

co-CE
CE (Construct a M to check the input, if >= 330 inputs are accepted, halt)

I am not sure if I am correct, and can I prove the first question is not CE by decribing TM may never halt?

As Rick commented, the first question is asking whether the set of Turing machines that recognize no more 330 strings is computably enumerable. Similarly, the second question is asking whether the set of Turing machines that recognize no less 330 strings is computably enumerable.

Let us show that second set is computably enumerable using dovetailing. Let $M_1, M_2, \cdots$ list all Turing machines. Let $w_1, w_2,\cdots$ list all words over the alphabet. We can build a Turing machine using the universal Turing machine to run the following procedure.

for i from 1 to infinity:

for j from 1 to i:

let string_count be 0
for k from 1 to i:

run $M_j$ with input $w_k$ up to $i$ steps. If it is found $M_j$ accepts $w_k$, add 1 to the string_count. If string_count is no less than 330, append $M_j$ to the output tape.

It is clear that every Turing machine that accepts no less than 330 strings will be added to the list at some point of time. Although each of them may be listed many times, that does not matter. Also only that kind of machines will be included in the list. So we have shown that the second set is computably enumerable.

Rice's theorem tells us the second set, which is $$\{\langle M\rangle : M\text{ is a TM and }L(M)\text{ has property that its size is no less than } 330 \}$$ is undecidable. Since it is computably enumerable, its complement (relative to the decidable problem whether a string encodes a Turing machine) $$\{\langle M\rangle : M\text{ is a TM and }L(M)\text{ has property that its size is less than } 330 \}$$ cannot be computably enumerable.
Well, the size of that number 330 does not affect our argument here. If we change it to 331, we see that the first set is not computably enumerable.


Counting Inversions with merge-sort I'm doing this course: Engineering: Algorithms1 - SELF PACED Algorithms: Design and Analysis, on Stanford's website. And the first assignment asked us to count the inversions in an array.

The idea that they used was:

Break the original array in half.
Count the inversions in each half
Pass the original array through mergeSort to get the split inversions

If this is so, then I do not understand how can the mergeSort not recount the inversions from each half.

From what I thought, every time I pick the element from the right array over the element from the left array that would be an inversion. And since we work recursively into basic single elements of the array, this would also go through each of the halves when merging, therefore recounting.

Am I missing something?

An inversion is a pair of indices $(i, j)$, with $i < j$ and $a_i > a_j$.
If you separated the array into two halves, then the inversions fall into three categories:

both indices of an inversion appear in the left half -> we count those in the first recursive call
both indices of an inversion appear in the right half -> we count those in the second recursive call
$i$ is in the left half, and $j$ is in the right half.

So in the merge step, we need to make sure that we only count those inversions of the third type.

By taking the definition of inversion, this translates as follows:
For each element in the left half ($a_i$), count how many elements in the right side are smaller ($a_j$). It should be obvious, that this really counts all inversions of the third category, and that it only counts these.
This translation also gives a very native $O(n^2)$ implementation of this step.

To make this more efficient, we can use the fact that both halves are sorted after the recursive calls, and we can use two pointers so that we can accomplish this step in $O(n)$. The pointers point to the first unprocessed element in each half. Then we take the smaller one of the two unprocessed elements, and put it in our merged array. If this one is of the first half, then we can count in constant time how many were smaller than it in the second half (by looking at the index of the second pointer).


Prove that palindromes are not regular language without using pumping lemma I came across this question. Palindromes are not regular: It is easy to prove it using pumping lemma. The problem is I want an explicit proof without pumping lemma. I came up with a solution. It goes like this.
Let us assume a language L which is palindrome so L can be expressed as x.xR where xR is reverse of x. If x is a regular language then xR will be too and hence the palindrome will be regular. What if x is not a regular language. Lets say x is 1^n0^n. It is not possible to draw a DFA for this as this string needs memory to keep the count of 1s so that it can add exact number of 0s. Since DFA doesn't have memory so it wont be possible to make a DFA for this, but xR = 0^n1^n and L=x.xR that is 1^n0^n.0^n1^n is still palindrome but not a regular language. So we can say palindromes are not regular.
I remember from my undergrad class to prove some language is not regular it is sufficient to give one negative example.
Will this approach work?

You can use the Myhill–Nerode criterion.

Suppose that $A$ is a DFA accepting your language. Let $q_n$ be the state which the DFA reaches upon reading the word $0^n1$. As the DFA has finitely many states, we must have $q_n = q_m$ for some $n \neq m$. On the one hand, when at state $q_n$, upon reading $0^n$ the DFA must reach an accepting state, since $0^n 1 0^n$ is a palindrome. On the other hand, when at state $q_m$, upon reading $0^n$ the DFA must reach a non-accepting state, since $0^m 1 0^n$ is not a palindrome. We have reached a contradiction since $q_n = q_m$.


Are SAT problems with at most one false clause NP-complete? Is the problem of deciding whether a SAT instance, where at most one clause is false (that is, any given variable assignment will either lead to all clauses being true, or all but one), is satisfiable solvable in polynomial time?

Given a CNF with $n$ variables and $m$ clauses, we denote by $A_i$ the set of truth assignments that do not satisfy clause $i$. Then the number of satisfiable assignments is
$$2^n-\left|\bigcup_{i=1}^m A_i\right|.$$
Since each assignment makes at most one clause false, $A_i$ and $A_j$ are disjoint for $i\neq j$. Also note $|A_i|=2^{n-n_i}$ where $n_i$ is the number of variables in clause $i$. Hence, the number of satisfiable assignments is exactly $2^n-\sum_{i=1}^m 2^{n-n_i}$ (this result is also given as lemma 2 in [1]).

So we can decide whether the CNF is satisfiable by checking whether $2^n-\sum_{i=1}^m 2^{n-n_i}>0$, which can be done in polynomial time.

[1] Nishimura, N., Ragde, P., & Szeider, S. (2007). Solving #SAT using vertex covers. Acta Informatica, 44(7-8), 509-523.


If two vertices point to one another in a directed graph, is the graph then considered cyclic? Suppose you have a directed graph. Vertices a and b are part of the graph. There is an arrow pointing from a to b and an arrow pointing from b to a. Does this make the directed graph cyclic?

Yes the graph is cyclic. It does not matter how many vertices are there. If a cycle can be formed then the graph is cyclic. You can even form a cyclic graph with one node. This cycle would be called a self loop.


Runtime analysis of sorting an array with known number of inversions I'm having difficulties with analyzing the worst-case runtime of this following case:

I'm given an array that has $n$ natural numbers. Out of all $\binom{n}{2} = \frac{n(n-1)}{2}$ possible pairs there are $\frac{n(n-1)}{2} - 5n$ inversions. Inversion is defined like this: $a[i] < a[j],\ i>j$.

So of course you can sort the array in $O(n \log n)$ time but can you do any better than this? I've looked online and saw that inversion sort time is in $\Theta(n+I)$ where $I= \text{# inversions}$ but then I get that $I=\Theta(n^2)$ so it doesn't really help me.

Hint: Make use of the following facts:

Each pair $i,j$ that forms an inversion for sorting in ascending order, does not form an inversion when sorting in descending order (and vice versa).
Reversing the complete list can be done in $\Theta(n)$.


Min path cover for a three-layer graph with all paths traversing all layers Best to start with an example. I want to design fictional fruits. The fruits have three attributes: color, taste and smell. There are $c$ possible colors, $t$ possible tastes and $s$ possible smells. Further, there is a feasibility matrix between colors and tastes and also one between tastes and smells. Hence, this can be thought of as a tri-partite graph; but there are edge constraints only between successive layers and not between every combination of layers; so it is a special case of a tri-partite graph (in a general tri-partite graph, there would also be edges between colors and smells). My objective is to cover all possible colors, tastes and smells with a minimal number of fruits.
Included below is a toy example. Here, we have three colors, two tastes and three smells. The connectivity is as shown on the left. The optimal solution is shown on the right. We can see that there are three paths that can cover all possible colors, tastes and smells. Hence, three fictional fruits will suffice and are the minimal required (since there are three colors and smells, we couldn't have done it with less than three).

Note: Cross-posted here: https://math.stackexchange.com/questions/3878929/minimum-edges-required-to-cover-all-vertices-of-three-way-graph. See great answer there as well.

My attempt:
One algorithm that comes to mind is the minimal path cover for a DAG. However, the well known formulation of that problem requires the paths to not share any vertices. We can see in the solution above that this constraint only gets in our way for this problem. The optimal solution does indeed have two paths that share a common taste vertex ($t_1$). Hence, it doesn't immediately apply.
Another approach involves finding the min-edge cover for the bi-partite graph between colors and tastes and another min-edge cover between tastes and smells. Then, we can go to each taste and greedily assign colors and smells from the respective min-edge covers until everything is covered. This approach has a danger: the two min-edge covers are not aware of each other. In the figure below, the situation on the left shows one possible set of min-edge covers which leads to the optimal solution. But, we could also end up with the situation on the right. In that case, we'll end up needing four fruits to cover everything which is sub-optimal.

So, how do we fix the algorithm above? We want to encourage the behavior on the left from the min-edge cover and discourage the behavior on the right. We observe that $t_1$ is a "super-vertex" with more colors and smells attached to it. So, we can assign the edges emanating from it lower costs. Then, we can modify the min-edge cover algorithm to prefer the edges with low costs. One approach would be to take the minimum of the number of colors and smells attached to each taste and divide $1$ by this. Then all edges emanating from that taste get this as the cost.
This algorithm will work for our toy example. However, how do we prove its optimality in general? And if it isn't optimal, how do we devise an optimal algorithm?

I think this can be solved by reduction to a circulation problem.
Introduce a graph with source $a$ and sink $z$.  The edges are as follows:

All edges will have infinite capacity, lower bound 0, and cost 0 unless mentioned otherwise.
Add an edge $z \to a$ with cost 1.
Add edges $a \to c_i$ for each color $c_i$ and $s'_k \to z$ for each smell $s_k$.
For each allowable combination $c_i,t_j$, add an edge $c'_i \to t_j$, and each allowable combination $t_j,s_k$, add an edge $t'_j \to s_k$.
Add edges $c_i \to c'_i$, $t_j \to t'_j$, $s_k \to s'_k$ with lower bound 1.

Find the minimum cost solution to this circulation problem.  I think there exists an integral solution, and it can found in polynomial-time.
The solution corresponds to a collection of fruits, and the cost of the solution is the number of fruits required.  Each unit of flow corresponds to a fruit.  The structure of the graph ensures that each attribute is covered by at least one fruit.


Prove that any directed cycle in the graph of a partial order must only involve one node So I have the question:

Prove that any directed cycle in the graph of a partial order must only involve one node.

So I know that a partial order must be transitive, antisymmetric, and reflective, but from there I am pretty lost. I also know that any path of one or more edges from a node to itself is a directed cycle, but from there I am having trouble connecting everything.

I kind of need help as to where to start thinking, and the first step as to how to answer this question.

I'm assuming your partial orders are of the type "$a \leq b$" rather than of the type "$a < b$", though the proof is very similar to both cases. Each edge $a \to b$ in the graph corresponds to an inequality $a \leq b$. Now suppose you had a triangle $a \to b \to c \to a$. Such a triangle would imply
$$a \leq b \leq c \leq a, $$
which has some implications since $\leq$ is a partial order. The case of longer (or shorter) cycles is similar.


On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it.

Besides, it's easy to see that the KP problem is a special case of the QKP.

How should one proceed to prove the NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem?

CCQKP:

$$max\ \sum_{i=1}^{n} \sum_{j=1}^{n} x_i x_j c_{ij}$$
$s.t$
$$\sum_{j=1}^{n} a_j x_j \leq C$$
$$\sum_{j=1}^{n}x_j = 1$$
$$0 \leq x_j \leq 1,\ j = 1,...,n$$
$$\sum_{j=1}^{n}z_j = k$$
$$z_j \in \{0,1\},\ j = 1,...,n$$

I'm aware that we usually talk about the hardness of Decision Problems even tough I'm formalizing the Optimization version of it.

The quadratic knapsack problem is NP-hard.  Therefore, the cardinality-constrained quadratic knapsack problem is NP-hard, too (as Yuval says, just don't use any cardinality constraints).

If problem X is a special case of problem Y, and problem X is NP-hard, then so is problem Y.  Now let X = CCQKP and Y = QKP.


Is there a solution for this maze problem in polynomial time? Suppose you have a maze represented by a graph where each vertex represents a room and edges represent paths between rooms and each edge has a weight denoting the time it takes to go that way. Now here comes the tricky part: suppose each room needs a set of keys for you to enter, and inside each room you can find another set of keys. Keys can be repeated and one key may be needed to enter on more than one room. You can only enter the room if you have all keys required.

You have an arbitrarily large number of chests with gold inside and each chest needs one key which can be found in the maze. You already have a set of keys that you can use. You can use a key more than once. The question is: how do you collect the keys you need as fast as possible?

If the number of keys is unlimited, the problem is NP-hard, by a straightforward reduction from the traveling salesman problem: simply put a different key in each vertex,  and have a single chest that requires all the keys.


Is the given language DCFL? $a^ib^jc^k | (i = j)$ then k is even?

I can write it as
$a^ib^ic^k$ where k is even

OR

$a^ib^jc^k where (i != j)$

Both are DCFL and union of DCFL may be DCFL, but I think because of OR operator it gives a sense of parallelism and hence NCFL.

I haven't tried to make a DPDA for it, because in exam I might not be have much time to draw.

I don't think it is DCFL.

Theoretically, is this approach right ?

You can construct a DPDA for your language as follows. When reading $a$s, the machine pushes $A$s onto the stack. When reading $b$s, the machine pops them, noting to itself if there are more $b$s than $a$s. When it reads the first $c$, it can use the top-of-stack to tell if the number of $a$ was equal to the number of $b$s; if so, it transfers control to a DFA for $(cc)^*$, and otherwise it transfers control to a DFA for $c^*$.


Should one learn proofs for the correctness of algorithms? Why? I'm reading Introduction to Algorithms and would like to know if learning the proofs is worthwhile.

That's up to you. Reading correctness proofs for algorithms is useful since:

The proofs explain why the algorithms work. If you need to modify these algorithms, you'd better know how they work. Such an understanding is very useful even just for coding algorithms, and certainly for debugging them.
The proofs are good examples of mathematical proofs. The mathematical notion of proof is one of the most important contributions of mathematics to the world, and is a way of knowing which you could find useful in life, even without using it yourself.
If you continue in academia, say get a graduate degree, you might have to write such proofs in the future.

However, it is my understanding that most programmers don't come up with new algorithms, or even code classical ones. If this is your case, you can probably skip the proofs, indeed the entire course, if it were not made compulsory by your university (if any).


Dividing a weighted planar graph into $k$ subgraphs with balanced weight I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge weights. After cutting, each subgraph must be connected (i.e. there must be a path between any two vertices of the subgraph which is only composed of vertices in that subgraph).

However, unlike most existing work on graph partitioning out there, I don't intend to obtain subgraphs that contain the same approximate number of vertices. Instead, I would like these subgraphs to have similar sum of edge weights. In other words, I would like to minimize the sum of edge weights of the subgraph with maximal weight and ideally cut long (weighted) edges.

Is there a name for this problem? I wasn't able to find anything about this on the web. Also, how can I approach this problem?

If the graph is sparse, may be it's also bounded tree width. Then we can find the optimum cut by using dynamic programming for graphs of bounded treewidth1. To check whether it's a bounded tree-width or not there are some tools and you can use them. On the other hand, one (may be good) heuristic approach is finding maximum spanning tree. This can be done by negating edge weights and running Kruskal algorithm to find MST. Because the graph is sparse then heaviest cuts along this tree are not bad, also good cut for tree can be found by bottom up dynamic programming approach. (I think it's in factor of at most 5 with high probability in most cases).

1: I didn't think about it, but seems to be as usual.


Does every procedure have a structural equivalent? Suppose I have a basic mathematical function like:

$ f(x) = x^2 + 2$

implemented in typed pseudo-code as:

int f(x) {
  return x*x + 2;
}

If we were to break out this procedure into a step-by-step sequence of actions, we have the following:

f: procedure(int x) returns int:
  set int(temp)         as multiply(x, x);
  set int(temp2)        as add(x, int(2));
  set int(return-value) as temp2;
  return;

However, say we have an equivalent "function" that is not a procedure but is equivalent in functionality (as in, it describes the same mutations, just differently--by structure):

f: function(int x) returns int:
  define(return-value
    add(
      2
      multiply(
        x
        x
      )
    )
  )

This is essentially a mathematical expression written as a tree of operators and  operands, Lisp-style.

It is very clear that the two are equivalent and describe the same mathematical expression: one by procedure, and the other, by structure/definition.

But why is it possible to know the two are equivalent? This mapping between procedure and functional is not always very clear. For even this pair of constructs, they are not equivalent simple "because they are." There must exist some sort of algorithm or procedure to describe how to map a procedure to a function (and, hopefully, not simply enumerating all of the possible values of output from a procedure and comparing it to a function).

Now, suppose we have a procedure as such:

g: procedure(Vector<{int red, int blue, int green}> screen,
             Vector<{int red, int blue, int green}> buffer) returns void:
  for-each {int, int, int} pixel, screen-pixel in buffer, screen:
    copy screen-pixel into pixel;
  return;

Is there a system in which a structural/functional equivalent for $g$ can exist?

Generally; for a set of procedures, does there exist a system in which each procedure has a functional/structural equivalent?

Semantics-wise, we usually know what a string of actions/instructions coupled with a set of data will do. For example, for-each will usually loop over a set of data performing some sort of sequences of instructions for each element in a set. However, the actual implementation of for-each can often differ, which means that proving that several implementations are equivalent in functionality can be non-trivial unless there is a universal way of mapping several procedures to their functional/structural form that all exist in a common system.

Generalized, if every procedure has a structural equivalent that share a common system for description, it may be possible to compare each procedure by value and then prove each are equivalent to a single function or not. This is the justification for why I am asking this question.

Every procedure has a functional equivalent, but not a structural equivalent, going by contextual definitions of functional and structural equivalent based on your question.

That every procedure has a functional equivalent is part of the general result that all “reasonable” methods of defining computation result in the same definition of what is computable. This is the Turing thesis.

A model that is close to your definition of procedures is the RAM machine. It's also possible to define a model based more closely on imperative programming with variable names. Two models based on function calls are µ-recursive functions and the lambda calculus. Both of these models require more than the ability to call a function.

With µ-recursive functions, there is a way to iterate calls to a function (the primitive recursion operator) and a way to call functions recursively until a condition is reached (the minimisation operator). Think of the primitive recursion operator as for loops and of the minimisation operator as while loops (building a general while loop requires more than the minimisation operator because that operator extracts only a specific part of the functionality).

With the lambda calculus, functions can be defined and applied to other functions. This unbridled functionality allows building recursive functions and thus arbitrary computations.

All of these models of computation can be proved to be equivalent. I'll refer you to a textbook for a formal proof; I'll just give the intuition here. Given an imperative program, put all of its variables in a single structure. Where functions use local variables, make a chained list of structures. This way you end up with a single variable in your program. In functional programming, this is known as the world state. Now you can pass this single variable as an argument to all function calls and have the functions returned the modified world state. Express all loops and conditional statements using while, and change while (condition) do_stuff() to a recursive call to do_stuff that minimizes the number of iterations (that's where the primitive recursion and minimisation operators get combined). You no longer need any assignment operator! You've converted your imperative program to a recursive functional program.

This transformation lets you convert an imperative program into a functional one. However, it doesn't really help if what you wanted was to know whether your programs are equivalent, because there are many different ways to implement a particular mathematical function in any framework. It's a general result that functional equivalence (determining whether two programs compute the same result) is undecidable: there is no algorithms that given two programs always says (correctly) “yes, they're equivalent” or “no, they aren't equivalent”. This is a special case of Rice's theorem, which informally speaking says that any decidable property of algorithms that depends only on what the algorithm computes (i.e. the mathematical function that it implements) and not on how it computes it is either the property “true for all algorithms” or “false for all algorithms”. This theorem holds for any Turing-equivalent model of computation (because if there was a way to decide a property for programs written in one model, it could be transposed to any model simply by translating the programs).


Computational problem - definition How should I understand the definition of computational problem?

  A computational problem is a mathematical object representing a
  collection of questions that computers might be able to solve. For
  example, the problem of factoring

  "Given a positive integer n, find a nontrivial prime factor of n."

What is the mathematical object in the example above? Quoting Wikipedia again:

  Commonly encountered mathematical objects include numbers,
  permutations, partitions, matrices, sets, functions, and relations.

So how can you 'represent' a collection of questions with numbers or permutations, matrices etc.? What is meant here is probably the following collection of sentences:

'find a nontrivial prime factor of 1', 'find a nontrivial prime factor of 2' and so on...

But the thing is - these sentences are not mathematical objects.

A little further in the article it reads:

  A computational problem can be viewed as an infinite collection of
  instances together with a solution for every instance.

which makes perfect sense, but I don't quite see the relationship with the first definition.

But the thing is - these sentences are not mathematical objects.

Yes, they are. A set of sentences can be a mathematical object. Just about anything can be a mathematical object.

A computational problem can be viewed as an infinite collection of instances together with a solution for every instance.

[...] but I don't quite see the relationship with the first definition

Well, "an infinite collection of instances together with a solution for every instance" is a mathematical object (representing a collection of questions that computers might be able to solve).


A vector-like data structure with allocation table; O(1) indexing time required I am a beginner in data structures and recently came across a vector implemented on an array, which is extended on demand. Of course the table cannot be extended "in place", we must allocate a new array, then copy elements from the previous one which is a linear operation itself (invoked log(n) times, where n is the number of insertion operations). Are there better implementations of such data structure while preserving constant item access time? For example, how about implementing a concept known from disk file systems - an allocation table; whenever we need to extend our array, an allocation table entry is created for newly reserved memory, without touching previously inserted items. Indexing time could still be constant, if only the allocation table would be implemented wisely (for example with using constant "page" size)
What I've written could be complete nonsense; it's just an idea.

The indexing time is always O(1) for an array whether you reallocate or not! Reallocating is not a bad idea if the table size doubles each time the array overflows, insertion takes constant time amortized.

Your idea is no different from a linked list of arrays of fixed size (correct if I'm wrong). If the list gets really large, looking for an element will take a lot of time.


Good reference for average-case runtime analysis of QuickSort I'm a beginner in programming with little knowledge about the technicalities. I'm assigned to do a "reading project" on the average case analysis of quicksort. I mean I have to present it in class. Now, I need a good source from which I can read it and find the materials which I can include in my presentation. As for my existing knowledge on algorithms, one can assume that I almost know nothing except for "just codes" and nothing at all about their analysis. Any book or materials having rigorous proofs will also do. Any help will be greatly appreciated!

Given your stats background, you will find the "indicator variable" analysis easier than the solution via recurrence equations.
It is based on computing the probability that two elements of given ranks are compared to each other.

The idea is described on the wikipedia page
and in more detail in Section 7.4 of Cormen et al. Introduction to Algorithms 3rd edition.


Can two minimum spanning trees for a same graph has different number edges? (1) Let's say $T_1$ has $r$ number of edges and $T_2$ has $s$ number of edges; where $r \ne s$ but two trees has same weight since they both are MST.

I kind feel this kind not be true because to span $n$ vertices with minimum number of edges, we need $n-1$ edges. so MST must have at least $n-1$ edges; if some MST has more than $n-1$ edges, then there must exists a cycle which leads to non-MST.

However, I don't know how to show that if the number of edges is greater or equal to the number of vertices of an an undirected, connected graph $G$, then $G$ has a cycle.

What if the graph is directed? Is this hold as well?

Any hint?

The answer is no. When running an algorithm for finding MST, It is first of all a tree, it has |v| - 1 edges $exactly$.

If there are more than |v| - 1 edges, than there're two vertices that their path isn't simple, which is simply shown with induction. Meaning if there's a path from s to t with more than |v| - 1 edges, one of the vertices will be repeated.


Can the lambda functions in Church numbers be swapped? I've learned that one can represent natural numbers with lambda calculus like this:

\begin{align*}
c_0 &= \lambda s. \lambda z. z\\
c_1 &= \lambda s. \lambda z. s~z\\
c_2 &= \lambda s. \lambda z. s~(s~z)\\
c_3 &= \lambda s. \lambda z. s~(s~(s~z))\\
\end{align*}

But could one also write

\begin{align*}
c'_0 &= \lambda z. \lambda s. z\\
c'_1 &= \lambda z. \lambda s. s~z\\
c'_2 &= \lambda z. \lambda s. s~(s~z)\\
c'_3 &= \lambda z. \lambda s. s~(s~(s~z))\\
\end{align*}

?

Why / why not?

Sure, except it's going to be more painful to use the numbers with the swapped arguments because in many cases you want to apply a Church numeral only to the argument $s$ and leave $z$ specified. Thus, instead of writing $c_n \, e$ you will have to write $\lambda z . c'_n \, z \, e$ whenever that happens.


Turing Machine that computes maximum steps of halting machines Suppose that $TM_{halting}$ is the set of machines that halt.

Given a number of states $m$ and a length $n$ of the input, let $f(m,n)$ be the maximum number of steps a machine with $m$ states in $TM_{halting}$ can take on an input of length $n$.

Is the function $f(m,n)$ computable?

Hint: If you could compute $f(m,n)$, then given a Turing machine $M$ with $m$ states and an input $x$ of length $n$, the Turing machine will either stop within $f(m,n)$ steps or never halt.

This argument actually shows that it is impossible to compute any upper bound on $f(m,n)$. In other words, $f(m,n)$ grows faster than any computable function.


What's the worst case complexity of Robert W. Floyd's cycle detection algorithm? Givens. I understand Floyd's algorithm can determine the length $\lambda$ of the loop and the length $m$ of the tail.  The hare will not necessarily catch the tortoise on the first cycle, but it is guaranteed to catch it after a number $k$ of cycles, where $k$ is a natural number.

Question. Given I know these facts, how can I deduce the worst case complexity of the algorithm?

An answer that seems fallacious.  For the tortoise and the hare to meet, they both need to be in the cycle.  This will occur certainly after $\mu + \lambda$ iterations.  Once the tortoise is in the cycle, the distance between the tortoise and the hare diminishes by one at each iteration.  Yuval Filmus' answer shows that they meet in the cycle in an index that's a multiple of $\lambda$.  Therefore, after they're both in the cycle, after $\lambda$ iterations (in the worst case) they must have reduced their distance to zero --- because the largest distance between them in the cycle is $\lambda$.  But how do I know the hare didn't jump the tortoise?  This argument doesn't seem very good.

In this answer, I show that $x_i = x_{2i}$ iff $i \geq \mu$ and $i$ is a multiple of $\lambda$. In particular, this will happen for some index $i$ in the range $\{\mu,\ldots,\mu+\lambda-1\}$. This shows that the algorithm runs in time $O(\mu + \lambda)$.


Given a set of sets, what is the largest common intersection between them? Given a set of sets: $S = \{~\{1, 2, 3\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$, I would like to find the largest common subset of $S$. If $S$ does not have a subset across all elements of $S$, I would like to find the largest common subset across the largest subset of $S$.

For example:

$S = \{~\{1, 5, 4\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$ has $\{4\}$ in common across all subsets.

$T = \{~\{1, 2, 6\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$ has $\{3, 4\}$ in common across the subset $\{T_1, T_2\}$

I understand the problem to be the following:

  Given sets $A_1,\dots,A_n$, find the largest $k$ such that there exist $k$ distinct indices $i_1,\dots,i_k$ that make $A_{i_1} \cap \cdots \cap A_{i_k}$ have a non-empty intersection.

This can be solved in $O(nm)$ time, where $m$ denotes the maximum size of any of the $A_i$. It suffices to find $x$ in $A_1 \cup \cdots \cup A_n$ that maximizes $|\{i : x \in A_i\}|$ (i.e., the number of sets $A_1,\dots,A_n$ that contain $x$).  When you've found this $x$, you can output the corresponding set $\{i : x \in A_i\}$ of indices.  You can output the intersection $\cap_{i : x \in A_i} A_i$ too if you want.

Naively, this might appear to take $O(n^2m)$ time.  However, the algorithm can be implemented in $O(nm)$ time, by scanning through the elements of the sets, maintaining a hashtable with a counter for each element $x$ that counts the number of sets it is contained in, and incrementing the right counter as you encounter each element.

The correctness follows from the fact that if $A_{i_1} \cap \cdots \cap A_{i_k}$ has a non-empty intersection, there must be some $x \in A_1 \cup \cdots \cup A_n$ that is contained in $A_{i_1} \cap \cdots \cap A_{i_k}$, and thus the algorithm above will find that combination of indices.


Any reason why Turing Machine would prevail on recursion theory? Nowadays, most introduction books, videos, and comments about theoretical computer science talk about Turing machines but don't discuss recursion theory anymore. These approaches are known to be equivalent.
What is the reason behind this? Has recursion theory simply gone out of fashion or is there a fundamental/mathematical reason explaining this?

With Turing machines you can talk about computer concepts such as running time and space usage. This is harder with $\mu$-recursive functions.


Changing from Kernel mode to User mode (and vice versa) I am reading Operating Systems book by Galvin. Galvin explains, what are kernel & user modes, instruction privileges given for both modes & also about mode-bit. But I am interested to know how mode changes from one to another. Basically I want to solve following question :

  A CPU has 2 modes, privileged and non-privileged. In order to change
  the mode from previledged to non-previledged

  a) A hardware interrupt is needed

  b) A software interrupt is needed.

  c) A privileged instruction is needed.

  d) A non-privileged instruction is need.

From what I understand,

from user mode to kernel mode - Hardware Interrupt is needed [like in Disk I/O]. Now, in case user program tires to access an memory which is beyond its permissible range, a trap occurs, which is basically a software interrupt which will be handled by OS. Now, in user mode we cannot execute any privileged instructions. So, a non-privileged instruction such as I/O request can change user to kernel mode. So I think, to change

  from non-privileged(user) to privileged(kernel) - H/W Interrupt, S/W
  Interrupt & non-Privileged instruction will do.

Now coming to, kernel to user mode. The OS can change kernel to user mode. So, it will simply run a privileged instruction to change from kernel to user mode. It does not need to generate either H/w or S/w interrupt. So I conclude, to change

  from previledged to non-previledged - a privileged instruction will
  do.

Am I right ?

Also when executing in kernel mode, all interrupts will be disabled right ? So answer cannot be (a) or (b). Also, since OS is basically a software, it cannot generate H/W interrupts.

Also, since OS itself handles interrupts, it does not make sense to me why has to generate a interrupt (& service it) to change from kernel to user mode.

Please let me know if I am wrong anywhere. Any help regarding this is appreciated.

Usermode to kernelmode: Wrong! ;-) Yes, interrupts are processed in kernel mode, and originally the way to enter kernel mode was by an interrupt forced somehow by software. On the DEC 2020 there was a set of UIOs (Unimplemented Instruction Opcodes), calling any of those caused a trap to the operating system. They included floating point instructions (if not in hardware) and other exotic instructions, but also the means to do operating system calls. The i?86 family has the int (interrupt) instruction, traditionally used as you say. Newer members of the family have SYSTENT to do supervisor calls more efficiently. The means of going to supervisor mode can't be privileged, but must somehow be tightly controlled by the kernel (where you enter the kernel, what arguments you pass, ...).

Kernelmode to usermode: No need for the "drop privileges" operation to be privileged. If you don't have privileges, dropping them is a no-op. But the exact mechanism is architecture dependent in extreme.

Interrupts disabled in kernel: Interrupts indicate some condition that has to be handled as soon as possible (for example, if the data arrived over the net isn't saved from the card before the next arrives, it will get overwritten). Thus interrupts are very rarely disabled. In original Unix systems (and contemporaries), there was one CPU, and the simplest way to get a critical region ("nobody mess with my data while I modify it") was just to disable interrupts. Pains were taken to keep the "interrupt disabled" stretches as short as possible because of the above. On current multi-CPU machines, disabling interrupts on one CPU does nothing much in this direction; disabling interrupts globally is extremeñy costly in inter-CPU coordination, so it is not done (or extremely rarely).


Numbers of ways of expressing the sum of a number between [a,b] I need an algorithm to calculate the number of ways of expressing a number N as sum of numbers inside the interval [a, b]

What you want is the number of integer partitions restricted to the interval $[a,b]$. I suggest you take a look at the approaches to count all partitions (check references and external links of the article) and adapt it to your needs.


Efficiently convert an NFA with multiple $\varepsilon$ edges and accepting states into a regular expression Given an NFA with alphabet $\Sigma = \{a, b, c\}$ defined in the diagram, is there a way to efficiently convert it into a regular expression?

The way I solved this problem is to first convert the NFA into a DFA using equivalent classes, and then proceed with the method described here. I feel in this case, that method is very inconvenient, as there are many loops and multiple accepting states. I wrote down all the partial regexps regarding to each accepting state alone, then unioned them together, then eliminated the redundant parts. My answer is $a(a^+ \cup b^*a \cup c^*)^+$.

I also tried to eliminate the $\varepsilon$ edges first then start from the "sanitized" NFA, but there were way too many edges in this case, and was very confusing during the process.

Edit: as @DavidRicherby has commented below, converting the NFA to DFA first is not necessary and makes the problem more complex.

State elimination method is a good technique, if used properly.

Solving $f_2$ can be done directly from the given automaton.
$$ f_2 = ( s \rightarrow q_1 \rightarrow f_2 + s \rightarrow q_2 \rightarrow f_2 + s \rightarrow f_1 \rightarrow f_2)^+ $$
( Overall Kleene + due to $(f_2,\epsilon) \rightarrow s$)
$$ f_2 = (a\cdot a^*\cdot a + a\cdot b^*\cdot a + (a\cdot c^*)^+\cdot c)^+ $$
This can be rearranged as
$$ f_2 = (a\cdot a^+ + a\cdot b^*\cdot a + (a\cdot c^*)\cdot (a\cdot c^*)^*\cdot c )^+$$
$$ = ( a \cdot ( a^+ + b^*\cdot a + c^*\cdot (a\cdot c^*)^*\cdot c) )^+ $$

Similarly, $f_1$ can be solved directly from the given automaton as follows
$$ f_1 = ( s \rightarrow q_1 \rightarrow f_2 \rightarrow s  + s \rightarrow q_2 \rightarrow f_2 \rightarrow s)^* \cdot s \rightarrow f_1 \cdot (\epsilon + c \cdot \epsilon \cdot f_1) $$
$$ = ( a \cdot a^+ + a\cdot b^* \cdot a )^* \cdot (a\cdot c^*)^+ \cdot ( \epsilon + c \cdot \epsilon \cdot f_1) $$

$( \epsilon + c \cdot \epsilon \cdot f_1)$ represent the two possible transitions from $f_1$. If the input has been completed scanned, stop at $f_1$. If not, move to $f_2$ using $c$, then move to $s$ using $\epsilon$. Then start scanning for $f_1$ again.

This recursive relationship can be solved by taking
$$ r = ( a \cdot a^+ + a\cdot b^* \cdot a )^* \cdot (a\cdot c^*)^+$$
Then $f_1$ becomes,

$$ f_1 = r \cdot ( \epsilon + c \cdot f_1)$$
$$ = r \cdot ( \epsilon + c \cdot ( r \cdot ( \epsilon + c \cdot f_1) ) )$$
Unravelling this recursion gives us,
$$ f_1 = r + r \cdot c \cdot r + r \cdot c \cdot r \cdot c \cdot r + \space... $$
$$ = r \cdot ( c \cdot r )^*$$


Neural network to detect connected parameters I have a list of configurations. Each configuration contains a number of parameters. The parameters have the same name but sometimes different values.
I now want a neural network, that can detect, which Parameters always have the same value when Parameter 1 has value 'A'.
I want to find out which Parameters are "related", so which parameters always change together and have always the same pair of values.

That's easy.  Find all configurations where parameter 1 has value A; throw away all the rest.  Now you can easily test whether all the remaining parameters have the same value for parameter 2 (just scan through them and see if they all have the same value as the first); you can do that for parameter 3; and so on.  No fancy algorithm is needed -- it's straightforward to program with a simple linear scan.


What is the result of multiplying O(n) and Ω(n)? If $f(x) = \Omega(n)$ and  $g(x)= O(n)$, what would be the order of growth of $f(x) \cdot g(x)$ ?

First I figured it should $\Theta(n)$ , as two extremes would cancel each other and the order of growth will be same as $n$

But, where I came across this question, the answer given was $\Omega(n)$, and no proof was mentioned. Well, I didn't understand why, but intuitively I convinced myself as "you can't know for sure the upper limit of growth for $f(x) \cdot g(x)$ so you can't say it's $O(n)$, but you can be sure that it won't be lower than $\Omega(n)$"

Can someone help me in understanding this, in a more believable way?

Basically, without further information you know nothing about the asymptotic growth of $f \cdot g$.

Let's unfold the definitions:

$\qquad f \in \Omega(n) \implies f(n) \leq cn$ and

$\qquad g \in O(n)      \implies g(n) \geq dn$

for some $c,d \in \mathbb{N}$ and $n$ greater than some constant.

Now it's clear that you get no bound on $g \cdot f$; you have no upper bound for one factor and no lower for the other. In fact, you can get arbitrarily slowly and fast growing results:

For $f : n \mapsto n$ and $g_k : n \mapsto n^{-k}$, we get $f \cdot g_k : n \mapsto n^{-k+1}$. Note that the induced sequence of functions is properly decreasing in terms of asymptotic growth.
For $f_k : n \mapsto n^k$ and $g : n \mapsto n$, we get $f_k \cdot g : n \mapsto n^{k+1}$. Note that the induced sequence of functions is properly increasing in terms of asymptotic growth.

If you restrict yourself to (eventually) non-decreasing functions -- that is $f,g \in \Omega(1)$ -- you get one of the missing bounds and thus $f \cdot g \in \Omega(n)$.


NP-complete proof from Dasgupta problem on Kite I am trying to understand this problem from Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, chapter8, Pg281. Problem 8.19

A kite is a graph on an even number of vertices, say $2n$, in which $n$ of the vertices form a clique
and the remaining $n$ vertices are connected in a “tail” that consists of a path joined to one of the
vertices of the clique. Given a graph $G$ and a goal $g$, the KITE problem asks for a subgraph which
is a kite and which contains $2g$ nodes. Prove that KITE is NP-complete.

Any pointers to start with this problem? I am completely lost with it.

You can reduce CLIQUE ($G$ has a clique of size $k$) to KITE: given $G=(V,E)$ and $k$, just build in polynomial time a new graph $G'$ in this way: for each node $v_i$ add a tail of $k$ new nodes.

If $G'$ has a kite of size $2k$ then the $G$ has a clique of size $k$ (the kite without the tail). Added nodes cannot introduce new cliques on G′, so $G$ contains exactly the same cliques of $G'$.


What is the space complexity of quicksort? What is the space complexity of quicksort?
I was doing some research and found some saying it is $O(1)$, some saying it's $O(\log n)$, and some saying $O(n)$. Not sure what to believe, even though $O(\log n)$ seems to make the most sense for me. Does it all depend on the pivot point that is chosen?

Since worst case space complexity of $\Theta(n)$ could be a problem, you can make a slight modification to the Qicksort algorithm: Partition the array, then sort the smaller half recursively, and sort the larger half iteratively. Roughly:
Sort (range r)
    While r contains two or more elements
        Partition range r
        Sort (smaller sub partition)
        r = larger sub partition

This reduces the worst case space required to $\Theta(\log n))$. It does not help with the worst case execution time.


Lower bound for matrix determinant algorithm I have the an algorithm for computing a matrix determinant:
$$\ det(A) = \sum_{i=1}^n (-1)^{i-1} \cdot A_{i1} \cdot det(A_{-i,-1})$$
Where $\ A_{-i,-1} $ is the matrix $\ A $ without the row $\ 1 $ and column $\ i $
Drawing the recurrence tree, I see each level $\ k $ has $\ \frac{(n-1)!}{(n-k)!} $ nodes. So I think the upper bound for this algorithm to be $\ O(n!) $ because the height of the tree is $\ n $ and the row sum of each level is the same as number of nodes. How can I set lower bound using recurrence tree? I've found this answer where the lower bound of such arithmetic operation in a matrix is set to be $\ \Omega(n^3) $ though , can not understand why?

The complexity of your algorithm on $n \times n$ matrices satisfies the recurrence
$$
T(n)=nT(n-1) + O(n^3),
$$
with a base case of $T(1) = O(1)$. In particular, $T(n) \geq n! T(1)$.
In the other direction, let $S(n) = T(n)/n!$. Then
$$
S(n) = S(n-1) + O(n^3/n!),
$$
with a base case of $S(1) = O(1)$. Since $\sum_{n=0}^\infty n^3/n!$ converges, we get $S(n) = O(1)$, and so $T(n) = O(n!)$. (The same argument also proves the lower bound.)


It is possible to implement a *greater than* function using only addition, substractions and multiplications? All values are from a finite field $Z_t$.
I want to write a function greater than like this

$GT(x,y) = \begin{cases}
  1, & \text{if } x > y, \\
  0, & \text{otherwise}.
\end{cases}$

using only additions, multiplications, subtractions and preferably not divisions.

The equality function

$EQU(x,y) = \begin{cases}
  1, & \text{if } x == y, \\
  0, & \text{otherwise}.
\end{cases}$

can be computed like this

$EQU(x,y) = 1 - (x-y)^p$, where p is the Euler totient function $p=phi(t)=t-1$ because $t$ is prime.

Can a greater than function be written in a similar way ?

The greater than function would be used for a homomorphic encryption application to find the maximum integer value from a vector of encrypted integers.

Every function on a finite field $GF(q)$ can be represented unique as a polynomial of individual degree at most $q-1$.

Indeed, as you mention, $1-x^{q-1} = [\![x=0]\!]$ is a polynomial that equals $1$ if and only if $x=0$. Therefore we can represent any function $f\colon GF(q)^n \to GF(q)$ in the variables $x_1,\ldots,x_n$ in the following form:
$$
\sum_{t_1,\ldots,t_n \in GF(q)} f(t_1,\ldots,t_n) \prod_{i=1}^n \left(1-(x_i-t_i)^{q-1}\right).
$$
Since the dimension of the space of $n$-variate functions is $q^n$ and the number of monomials of individual degree at most $q-1$ is also $q^n$, we conclude that this representation is unique.


Is there any sort of formal definition of terms like 'data type', 'abstract data type', etc? If not (because I assume not) is there some kind of reference or book that provides some theoretical foundation to these concepts? I've been learning about data structures and abstract data types for a while now but all these concepts seem very hazy and I would like some sort of rigorous grounding to stand on.

I hear type theory is used to found a lot of theoretical computer science (or all of it). So where could I read about type theory and how it is used to formalize CS?

I good starting point is Benjamin Pierce's Types and programming languages (popularly referred to as "TAPL").


How create DFA with multiple finished states for lexers? Is possible to create DFA directly from regular expression. But for lexical analyse is needed "joined" DFA with many finish states, for example one state for string, one for integers, one for floats etc. How do such DFA? Maybe convert many DFA's to one or join DFA's to one NFA and next convert it to DFA?

As Rick Decker rightly noted, real-world lexical analysers produce a DFA with multiple final states.

Lexical analysers created via Lex-like generators differ from theoretical DFAs in several respects, and this is only one of them. Another obvious difference is that they don't stop at the end of the input string.

Instead, lexical analyser generators generally work as if they ran all DFAs corresponding to the lexer rules in parallel (in practice using a DFA with multiple end states), and applying the following rules:

The DFA that "wins" is the one that proceeded the furthest (often called the "maximal munch" rule).
If more than one DFA would accept that maximal-length input, the one that occurred first in the specification file "wins" (the disambiguation rule).

The disambiguation rule is used, for example, to distinguish keywords (e.g. if, else, while) from identifiers. Ignoring underscores for the moment, an identifier is (typically) any lexeme that starts with an alphabetic character followed zero or more alphanumeric characters, but isn't a keyword. You could create a regular expression which matches this, but it's much easier to specify keywords before identifiers and let the lexical analyser generator do the disambiguation for you.


Are there any computer science encyclopedias? Consider the volume "The Princeton Companion to Mathematics" which has the broadest range of topics attempted by any book in the field.

Does a Computer Science counterpart exist?

There are two that I've seen:

Encyclopedia of Computer Science and Technology by Allen Kent (Over 40 volumes)
Encyclopedia of Computer Science and Technology by Harry Henderson

Also, Wikipedia could be considered containing a CS encyclopedia.


What does "non-pathological data" mean? I took an algorithms class on Coursera. The professor in the video about hash tables said that

  What's true is that for non-pathological data, you will get constant time operations in a properly implemented hash table.

What does "non-pathological data" mean? Can you give some examples?

Pathological data is supposed to be data that makes things go wrong in
some way for your intended computation. It can be called
pathological when it is rare enough in actual uses, so that things
work OK most of the time. This can sometimes be made mathematically
more precise (for example with probabilities), but the use of the
word pathological in often informal.

For example, tomato salad and ketchup are excellent food, except for
pathological people, meaning those people who are allergic to
tomatoes. It can actually kill in some cases.  But people allergic to
tomatoes are very rare so that tomato dishes are considered excellent,
except in pathological cases.

There are many algorithms that, while having a worst case complexity
above the optimal one, are on the average as good or better than worst
case optimal algorithm. If you compare quicksort and merge sort,
quicksort is time $O(n^2)$ while merge sort is $O(n \lg n)$ in the worst
case. But people will often use quicksort, because they both are time
$O(n \lg n)$ on average, and the space complexity is $O(\lg n)$ for
quicksort and $O(n)$ for merge sort.

The fact that quicksort is as good on average may be attributed to the
fact that the $O(n^2)$ time complexity actually occurs only on
pathological (implying bad but rare) cases.


Why do caches fetch data to the right if the offset bit is 0 and to the left if it is 1 in a 2-word block Here is an example of table with 32 bit addresses and their respective indexes and tags. The cache has a total of 8 blocks and 2-word blocks.

So since we have 2 word blocks, that means that the offset is 1 and we use the least most significant bit as the offset. So in the first row, it not only brings 3 but it also brings 2 into the cache because the offset bit is 1(why not 4 if the offset bit is 1). Now I understand that the importance of this is to reinforce the idea of spatial locality, I just want to understand more about the procedure and what kinds of conflict it would cause if it was the other way around. If you can show it with an example that would be great.

The two-word blocks are always aligned, and you can find where they start by zeroing the LSB. So the two blocks are always of the form $x0,x1$. So if you fetch $x1$ you also fetch $x0$, and vice versa. This makes indexing the block easy, since to find what block a word belongs to, you just need to drop the LSB.


Solve T(n) = T(n-1)*n with repeated substitution I'm trying to solve T(n) = T(n-1)*n using repeated substitution.

I can expand it, but I'm having trouble with geometric sequences for any problem. I find I'm just memorizing solutions to typical problems. It's sometimes hard for me to go from the expanded equation to a general equation that I can simplify.

T(n) = T(n-1)(n)

T(n) = T(n-2)(n-1)(n)

T(n) = T(n- 3)(n-2)(n-1)(n)

I'm not sure how to generalize this to ultimately find the big O. Any tips are appreciated!

This is the rucursive formula for $n$ factorial.

Define the formula $T(n)$ for $n \geq 0$ as $T(n) = nT(n-1)$. By repeated substitutions observe that
$$ T(0) = 1$$
$$ T(1) = 1\times T(0)=1 \times 1$$
$$ T(2) = 2 \times T(1)=2\times 1\times 1$$
$$ T(3) = 3\times T(2)=3\times 2\times 1\times 1$$
$$\dots$$
$$T(n) = nT(n-1)=n\times (n-1)(n-2)\dots 1\times 1 $$
Thus by simple observation you can easily guess the pattern of product of the first $n$ positive integers.

For a complete proof you need to prove that $T(n) = n!$. This is easily done by induction. For $n=0$, $T(n)=1 = 0!$. Assume that formula is true for $n-1$. Then $T(n)=nT(n-1)=n(n-1)!=n!$ which completes the proof. So $T(n)$ is $\Theta(n!)$.

There is no a standard method to solve such kind of recurrence relations, but you usually guess the explicit form of the formula and proof it, for example, using induction or other technique or method.

As an exercise try to guess and prove explicit formulas for

$T(0) = 1, T(n)=2T(n-1)$
$T(0) = 1, T(n) = nT(n-2)$, for only even $n$s.


How to argue about semi-decidability of a problem? I have the following problem, and I try to prove that it is semi-decidable, but I have a hard time arguing about it.

I know that if a problem $\mathcal{P}$ is semi-decidable, then we can build a program $\Pi$, such that $\Pi$ takes as input instance $I$ of $\mathcal{P}$, and if we have a positive instance, then $\Pi$ returns true, and on negative instance, $\Pi$ either returns false, or does not terminate.

Now, I tried to write a simple procedure like this:

Then, I tried to argue like this:

We can write a procedure $\Pi'$ that takes as input $(S,n)$, and simulates a run of $\Pi_1$ on $S$, and a run of $\Pi_2$ on $n$. We can show that such procedure $\Pi'$ is a semi-decision procedure, and we can distinguish the following cases:

Case 1. Suppose that $(S,n)$ is a positive instance, meaning $\Pi_1$ outputs $I$ on input $S$, and $\Pi_2$ outputs $I$ on input $n$. Then the simulation $\Pi'$ will encounter that $OUT1 = OUT2$, and output return true by its construction.
Case 2.1. Suppose that $(S,n)$ is a negative instance and it halts. Then, we have that $\Pi_1$ outputs $I_1$ on input $S$, and $\Pi_2$ outputs $I_2$ on input $n$, such that $I_1 \neq I_2$. Thus, $\Pi'$ does not halt due to its construction.

My problem is that, I cover just two cases, I believe I need one more case, where we have as output false, and terminate. Also, from the definition of semi-decidable program, I believe instead of using the pair $(S,n)$, I need to use the pair $(\Pi_1, \Pi_2)$, which is the actual instance of the problem. But, then how will I choose $S$ and $n$? If someone can help me with those questions, I would be glad.

We know that $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ have the same cardinality, so there exists a bijection $f:\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}$. Let $s_n$ be the $n$-th string in some enumeration, like $s_1=\epsilon, s_2=0, s_3=1, s_4=00, s_5=01,\dotsc$ then consider the following semi-decider, where I leave it to you to fill in the missing parts:
$$\begin{align}
&\Pi'(\Pi_1, \Pi_2)=\\
&\quad\text{for }n=1,2,3,\dotsc\\
&\quad\quad\text{compute }f(n)=(i,j)\\
&\quad\quad\text{run }\Pi_1(s_i)\\
&\quad\quad\text{run }\Pi_2(j)\\
&\quad\quad\text{... }\\
&\quad\quad\text{... }\\
&\quad\quad\quad\text{return accept}
\end{align}$$

There are lots of bijections between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$, here are a few to get you started.


Data structure for adjacent rectangles I have a file with a list of non-overlapping rectangles covering the entire space (they are adjacent). I would like to plot efficiently the graph edges that connect each rectangle center point with the adjacents rectangle center points. Which is the best data structure to use to load the rectangle list? Which is the best algorithm to find all the adjacent rectangles in x and y directions?

Thank you.

More details:
In the picture below a visual example with 12 axis-aligned rectangles. The red paths are the desired output.

The numbering is from the random order in the input file:

rect1   (19,0)  (23,19)
rect2   (0,3)   (4,16)
rect3   (8,17)  (11,19)
rect4   (8,6)   (19,17)
rect5   (0,0)   (11,3)
rect6   (4,3)   (15,6)
rect7   (4,6)   (8,8)
rect8   (15,3)  (19,6)
rect9   (11,0)  (19,3)
rect10  (0,16)  (4,19)
rect11  (4,8)   (8,19)
rect12  (11,17) (19,19)

The desired output is the adjacent combinations of rectangles and their length:

(1,4) (1,12) (1,8) (1,9) (2,5) (2,10) (2,11) (2,7)
(2,6) (3,4) (3,12) (3,11) (4,6) (4,7) (4,8) (4,11)
(4,12) (5,6) (5,9) (6,7) (6,8) (6,9) (7,11) (8,9) (10,11)

The sweeping algorithm, suggested by @adrianN, can be elaborated this way.

Step 1. Put all your rectangles in a map of sets in such way, that:

the map key is left boundary of rectangle
the map value is ordered by lower boundary set of rectangles, having this left boundary

For your example, this map will be:

0 => (2, 5, 10)
4 => (6, 7, 11)
8 => (3, 4)
11 => (9, 12)
15 => (8)
19 => (1)

Step 2. Create a similar map of rectangle sets, having the same right boundary.

Step 3. Define active rectangle set, which will "sweep" the data structure above, from left to right, generating pairs of adjacent rectangles.

At first assign to the active set the rectangle set with minimal left boundary $x_0$. You can immediately generate a number of pairs of adjacent rectangles from the active set (because it's ordered and there are no "holes" in it).

Then move the active set to the next position of the left boundary, let's say $x_1$. You will need to update the active set, removing rectangles with right boundary $x_1$, and adding rectangles with left boundary $x_1$. You already have these rectangle sets in data structures, created earlier. The active set will be ordered after this update - generate pairs from it.

And so on...

For your example - active sets A0, A1 etc. will be:

A0 = (2, 5, 10)
A1 = (5, 6, 7, 11)
A2 = (5, 6, 4, 3)
A3 = (9, 6, 4, 12)
A4 = (9, 8, 4, 12)
A5 = (1)

This algorithm will generate all pairs of rectangles, adjacent in vertical direction only. Some of pairs will be generated more than once - you'll need to filter repetitions out.

In order to get all pairs of rectangles, adjacent in horizontal direction, you'll need to "rotate the picture" by 90 grades and repeat the algorithm. Another option - much more complex processing of rectangles during the active set update.

Time complexity of this algorithm depends on complexity of set operations union and minus.


Cardinality of the set of algorithms Someone in a discussion brought up that (he reckons) there can be at least continuum number of strategies to approach a specific problem. The specific problem was trading strategies (not algorithms but strategies) but I think thats beside the point for my question.

This got me thinking about the cardinality of the set of algorithms. I have been searching around a bit but have come up with nothing. I've been thinking that, since turing machines operate with a finite set of alphabet and the tape has to be indexable thus countable, it's impossible to have uncountable number of algorithms. My set theory is admittedly rusty so I am not certain at all my reasoning is valid and I probably wouldn't be able to prove it, but it's an interesting thought.

What is the cardinality of the set of algorithms?

An algorithm is informally described as a finite sequence of written instructions for accomplishing some task. More formally, they're identified as Turing machines, though you could equally well describe them as computer programs.

The precise formalism you use doesn't much matter but the fundamental point is that each algorithm can be written down as a finite sequence of characters, where the characters are chosen from some finite set, e.g., roman letters, ASCII or zeroes and ones. For simplicity, let's assume zeroes and ones. Any sequence of zeroes and ones is just a natural number written in binary. That means there are at most a countable infinity of algorithms, since every algorithm can be represented as a natural number.

For full credit, you should be worried that some natural numbers might not code valid programs, so there might be fewer algorithms than natural numbers. (For bonus credit, you might also be wondering if it's possible that two different natural numbers represent the same algorithm.) However, print 1, print 2, print 3 and so on are all algorithms and all different, so there are at least countably infinitely many algorithms.

So we conclude that the set of algorithms is countably infinite.


Language to Generate Powers of 2 Using a Language Containing Decimal Numbers For this question, I have the alphabet $\Sigma=\{0,1,2,3,4,5,6,7,8,9\}$. I also have the language $L$ over $\Sigma$ described as the language such that the strings $w$ contained in $L$ are powers of 2 and $w$ is treated as a decimal number. I then need to:

Design a grammar to generate $L$
Classify the grammar (Regular, Context-free, etc.)
Show that $L$ is not regular
Determine if $L$ is a context-free language (answering only yes or no)

The original question is in the image below, for reference.

I'm not entirely sure how to start on this question in particular. Most of the examples I had in my automata class consisted of much smaller alphabets and more precise languages. Any help with an explanation would be much appreciated.

Thank you in advance!

L is not context-free
Periodicity for context-free languages of bounded growth: Let $w_n$ be the number of words of length $n$ in a given regular language. If the sequence $w_1, w_2, \cdots$ is bounded (bounded growth), then it is eventually periodic.
Proof: This follows from the fact that every context-free language of bounded growth is a union of paired loops, which is the theorem 2.1 in the paper On a conjecture about slender
context-free languages by Lucian Ilie, 1994.

Let $w_n$ be the number of words of length $n$ in $L$. $w_n=\#\{k\in\Bbb N\mid n-1\le k\log_{10}2 \lt n\}$. Since $\log_{10}2$ is irrational, the sequence $w_1, w_2, \cdots$ cannot be eventually periodic. So $L$ is not context-free. Hence, it is not regular, either.
As rici pointed out, it is not difficult to prove that $L$ is not context free by applying the pumping lemma to any word in $L$ that is long enough. The above more conceptual proof is presented in the hope that it might raise more interest and more questions.
$L$ is context-sensitive
According to rici's comment, we can write a context-sensitive grammar which multiplies a decimal number by two. Use marker tokens which move right to left over the number; you'll need two of them because of the possibility of carry. As with many other cases of context-sensitive grammars, the actual construction might be apt to get lengthy and tricky, sometimes even debatable.
Another conceptual way to see $L$ is context-sensitive is using linear bounded automaton (LBA) that accepts a context-sensitive language. It is easy to see that we can divide by 2 repeatedly using a linear bounded automaton. More specifically, we can design a LBA such that given an input of $S m E$, where $m$ is a sequence of decimal digits and where $S$ and $E$ are start marker and end marker respectively, it will output $S1\square\square\cdots\square E$, where $\square$ stands for the special blank symbol if and only if $m$ is the decimal representation of some power of 2.
An exercise
Let language $L_U$ over $\Sigma=\{0,1,2,3,4,5,6,7,8,9\}$ be the language of words which are positive integers whose prime factors belong to a finite set $U$ of prime numbers when they are treated as decimal numbers. Show that $L_U$ is context-sensitive but not context-free.


How to prove quantum circuit identity in Qiskit? I am working on a simple quantum circuit identity. I proved it on paper with the tensor product, but i'm having trouble showing that with qiskit. I know I need to measure them somehow but i don't know how.
Can someone help? :)

You can check whether the unitary matrices are equivalent.

def circuits_equivalent(a, b):
    au = Operator(a)
    bu = Operator(b)
    return au.dim == bu.dim and np.allclose(au.data, bu.data)


On complete problems for $P/poly$ and $BPP$ Is there a complete problem for $P/poly$?

Decision version of permanent more or less acts as a complete problem for $PP$ while its weaker sibling has no known complete language. Why? I saw wiki reason but it is not clear to me. In https://en.wikipedia.org/wiki/PP_(complexity)#Complete_problems_and_other_properties it is stated 'Unlike BPP, PP is a syntactic, rather than semantic class. Any polynomial-time probabilistic machine recognizes some language in PP. In contrast, given a description of a polynomial-time probabilistic machine, it is undecidable in general to determine if it recognizes a language in BPP'.

There are no $P/Poly$ complete languages (relative to polynomial time or even computable reductions).

Suppose for the purpose of contradiction that there exists some language $L$ which is complete for $P/Poly$. In that case the mapping $f:P/Poly\rightarrow \mathbb{N}$, which maps any language in $P/Poly$ to its corresponding reduction to $L$ (we refer to the encoding of this reduction as a natural number), is an injection from $P/Poly$ to the natural numbers. This of course leads to a contradiction, since $P/Poly$ is of cardinality $2^{\aleph_0}$.

In light of Ricky Demer's comment, we should note that since computable reductions are of no use to $P/Poly$, one needs to introduce the notion of non-uniform reductions. One example is projection reductions.

A family of boolean functions $f_n(x_1,...,x_n)$ is said to be projection reducible to the family $g_n(y_1,...,y_n)$ if for all $n\in\mathbb{N}$ there exists some $m\le p(n)$ with polynomial $p$, and a rewiring of $g$'s inputs, $\sigma:\left\{y_1,...,y_m\right\}\rightarrow\left\{0,1,x_1,\overline{x_1},...,x_n,{\overline{x_n}}\right\}$, such that $f_n(x_1,...,x_n)=g_m\left(\sigma(y_1),...,\sigma(y_m)\right)$. Intuitively, this means that given a circuit for $g$ (perhaps with polynomialy more inputs), we can compute $f$ just be rewiring the inputs accordingly. We denote this by $f\le_{proj} g$.

Note that if $g\in P/Poly$ and $f\le_{proj} g$ then $f\in P/Poly$, the advice for input $x$ would be the rewiring $\sigma$, together with the $m(|x|)$ inputs circuit for $g$.

The following is a (very) short sketch of the proof that the circuit value problem, $CVP$, which takes as input a circuit $\mathcal{C}$ and input $x$, and asks whether $\mathcal{C}(x)=1$ is $P/Poly$ hard under such reductions. Given $L\in P/Poly$, let $\mathcal{C}_n$ be the polynomial circuit family for $L$. For any string $x$, You can hardwire $\mathcal{C}_{|x|}$ as input to $CVP$ (using the constants $0/1$), and use the rest of the variables to input $x$.


Cartesian construction of PDA and DFA How would I go about using Cartesian construction to find the intersection between a PDA and a DFA?

Is there another term for Cartesian construction? Would it be similar to the procedure for finding the intersection/union of 2 DFAs?

The more common term is the "product construction".

The product of a PDA and a DFA is a PDA whose state space is the Cartesian product of the states of the two automata (just like in two DFAs), the transition function is similar to the product construction in DFAs, only the PDA component can act on the stack.


How many bits would be needed for the byte? The Problem: A high speed workstation has 64 bit words and 64 bit addresses with address resolution at the byte level.  Assuming a direct mapped cache with 8192 64 byte lines, how many bits are in each of the following address fields for the cache?  1) byte 2) Index 3) Tag?

I know that an address for specifying data within a cache is 64 bits.
I know that an address  for a cache has to have the byte, index, and tag field so byte + index + tag = 64
The index field should take up 13 bits to account for the 8192 byte lines

How many bits would be in the byte field though? I know that a processor processes one word at a time and each word consists of 8 bytes. A 64 byte cache line would contain 8 words. Would this byte field need to identify each word or each byte itself. If it was byte itself, it be 6 bits but if it was word it be 3 bits.

If I had to take a stab, I would say the byte field needs to be 3 bits to identify each word because it doesn't make sense for the processor to just process one byte. Can anyone confirm my suspicisions?

In a processor architecture of 64 bits the smallest single 'word' is 64 bits. that is each cyclic transfer from buffer to buffer occurs on a 64 bit buss. to identify a single byte of this native word in fact would only take 3 bits, but the actual register might in fact be 8-16 bits... if it was designed that way. the compiler that was designed to handle this would take all this into account and when you incremented a pointer it would do the conversion for you. as well as if the 'byte ' was actually an Unicode 16 bit character'. you need to look at the cpu programmers guide or manual for actual specifics and also the compilers manual, specifically with regards to data types and to addressing them.


Multi object image segmentation methods I want to survey the state-of-the-art in image segmentation. Is there a paper on how to segment multiple objects in an image? The segmentation papers I read, normally identify one of the many objects in the image. This object is typically in the center of the frame, or most-foreground compared to other objects in the image. I'm looking for a way to identify all different objects in an image simultaneously. Is there any recent work on this?

I think that you are interested in MFC - Multiple Foreground Cosegmentation.
MFC article

Awesome material:
Articulated Motion and Deformable Objects : 5th International Conference, AMDO 2008, Port d'Andratx, Mallorca, Spain, July 9-11, 2008, Proceedings

In advance I warn you, these are not all out of the box working solutions, but with small changes all can do segmentation so if first link is what you have expected treat these below as starting point to work your own way.

Every "one object only in the foreground" can start iterative scheme: find first, cut, colour it with backgroundish color (presumably gray darker then mean luminance of the image), cut next.

When some classifiers are used, or patterns are known it is easier, but when background is complex and you want just regions there are oldschool ways: use Otsu, or modified K-Means clustering, try region growing, edge detection, make decision from colour or shadows.
In the end you will find yourself in situation that there are some components, now it is time to decide which is background (darker; connected with all edges of the image; bigger? Every of those could fail).

Image segmentation is based on some kind of connecting self similar regions, cuts them by edges even follows perspective lines if possible.

Foreground - Background separation is the most of the time asuming that foreground is smaller, better exposed. Very rarely there is perspective reconstruction and from one image it is virtually impossible (for street views we can detect lines and follow to horizon, but other types fail).

Below are additional links. If nothing helped write me a comment and describe more details.

Examples are connected in this paper but it works for separate objects: automatic foreground extraction

Foreground prediction

Must read:
Otsu image segmentation
Region-based
Graph based

When you expect some objects:
Blobs

Sequence of images:
Kalman filter
Background/Foreground


Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random? The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers.

  An algorithmically random number is a number (in some encoding,
  usually binary) for which the shortest program (e.g using a Turing
  Machine) to generate the number, has the same length (number of
  bits) as the number itself.

In this sense numbers like $\sqrt{e}$ or $\pi$ are not random since well known (mathematical) relations exist which in effect function as algorithms for these numbers.

However, especially for $e$ and $\pi$ (which are transcendental numbers) it is known that they are defined by infinite power series.

For example $e = \sum_{n=0}^\infty \frac{1}{n!}$

So even though a number, which is the binary representation of  $\sqrt{e}$, is not alg. random, a program would (still?) need the description of the (infinite) bits of the (transcendental) number $e$ itself.

Can transcendental numbers (really) be compressed?

Where is this argument wrong?

UPDATE:

Also note the fact that for almost all transcendental numbers, and irrational numbers in general, the frequency of digits is uniform (much like a random sequence). So its Shannon entropy should be equal to a random string, however the Kolmogorov Complexity, which is related to Shannon Entropy, would be different (as not alg. random)

Thank you

The problem is in your poor definition of "algorithmically random number" as applied to irrational numbers. In particular:

has the same length (number of bits) as the number itself.

has no meaning if the number is of unbounded length.
Your Wikipedia link gives better definitions, which don't have this problem. For example (and paraphrasing formatting):

Kolmogorov complexity [...] can be thought of as a lower bound on the algorithmic compressibility of a finite sequence (of characters or binary digits). It assigns to each such sequence $w$ a natural number $K(w)$ that, intuitively, measures the minimum length of a computer program (written in some fixed programming language) that takes no input and will output $w$ when run. Given a natural number $c$ and a sequence $w$, we say that $w$ is $c$-incompressible if $K(w) \geq |w| - c$.
An infinite sequence $S$ is Martin-Löf random if and only if there is a constant $c$ such that all of $S$'s finite prefixes are $c$-incompressible.

This is a test passed by $\sqrt{e}$ by setting $c$ a bit larger than the program to generate $\sqrt{e}$ and including in it the length to generate.


Is Acceptance by Empty stack and Final state possible in the same PDA? $L$ is the language accepted by the above PDA :
$L = \{a^n\mid n\geq 0\}\cup\{a^n b^n\mid n\geq 0\}$ and is deterministic context-free is the language accepted by the PDA how can we accept $a^n$? As it doesn't contain an epsilon transition at the end right ? Is acceptance by both the final state and empty stack possible in the same PDA?

The PDA can accept $a^n$ because :

Till we don't read a $b$, we stay in start state.
The start state is a final state.

By acceptance by final state, the PDA accepts strings of the form $a^n$.

For strings $a^nb^n$, we have the following :

$X^n$ is pushed on the stack, by reading $a^n$ and looping over the start state.
For the first $b$, pop the stack, and continue to pop till we get only $Z$ in the stack.
When only $Z$ remainded, we have only one choice to do, and even if it's an epsilon transition, because it's the only possible transition at this point, the automaton is still deterministic.

We have also here an acceptance by final state.

In addition, we can define both acceptance by final state and by empty stack on the same PDA, but generally, the two don't lead to the same language. For your language, acceptance by empty stack lead to an empty language, because the stack can never be empty.


Getting parallel items in dependency resolution I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent paths?

I assume that an edge $(u,v)$ means that $u$ has to be executed before $v$. If this is not the case, turn around all edges. I furthermore assume that you are less interested in paths (those are already given by the DAG) than in a good execution strategy given the dependencies.

You can easily adapt the topological sort procedure: instead of appending, merge all items of the same "depth" to one set. You get a list of sets, each of which contains items you can execute/install in parallel. Formally, the sets $S_i$ are defined thus for the graph $G = (V,E)$:

$\qquad \displaystyle \begin{align}
  S_0 &= \{ v \in V \mid \forall u \in V. (u,v) \notin E \} \\
  S_{i+1} &= \{v \in V \mid \forall u \in V. (u,v) \in E \to u \in \bigcup_{k=0}^i S_k \}
\end{align}$

You can then execute your tasks like this (let's assume there are $k$ sets):

for i=0 to k
  parallel foreach T in S_k
    execute T

Of course, this does not yield maximum throughput if tasks take different amounts of time: two parallel, independent linear chains sync after each element. To circumvent this, I suggest you work directly on the DAG with a parallel traversal starting in the source nodes -- those in $S_0$ -- and syncing/forking in nodes with several incoming/outgoing edges:

parallel foreach T in S_0
  recursive_execute T

where

recursive_execute T {
  atomic { if T.count++ < T.indeg then return }
  execute T
  parallel foreach T' in T.succ
    recursive_execute T'
}

and T.count is a simple counter holding the number of predecessors of T which have been executed already, T.indeg the number of predeccessors and T.succ the set of successors.


What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to the standard definition of linearity? I was reading notes on computability theory when I came across the term "Linearity" which I was not familiar with, in the context of boolean functions. I am quite comfortable what linear maps mean in Vector Spaces (say in the context of linear algebra and functional analysis) but I had never seen this term being used in the context of boolean functions. In those other contexts it roughly means the following equation is true:

$$ f(x+y) = f(x) + f(y) $$

however, when I went to wikipedia to find out what linearity means for boolean functions I came across a weird paragraph that seem to define it but didn't seem to have a clear succinct way to define linear functions or its relations to the more standard way of defining linearity.

Can someone explain to me how the definition from wikipedia relates to the more traditional way of defining linearity over Vector Spaces? In other words, why is the detailed definition on wikipedia the way it is?

For ease, here is wikipedia's definition:

  In Boolean algebra, a linear function is a function ${\displaystyle f}$ for which there exist $ {\displaystyle a_{0},a_{1},\ldots ,a_{n}\in\{0,1\}} a_0, a_1, \ldots, a_n \in \{0,1\} $ such that:

  $$ f(b_1, \ldots, b_n) = a_0 \oplus (a_1 \land b_1) \oplus \cdots \oplus (a_n \land b_n), \text{ where } {\displaystyle b_{1},\ldots ,b_{n}\in \{0,1\}.} b_1, \ldots, b_n \in \{0,1\}. $$

  A Boolean function is linear if one of the following holds for the
  function's truth table:

  -> In every row in which the truth value of the function is 'T', there
  are an odd number of 'T's assigned to the arguments and in every row
  in which the function is 'F' there is an even number of 'T's assigned
  to arguments. Specifically, f('F', 'F', ..., 'F') = 'F', and these
  functions correspond to linear maps over the Boolean vector space.

  -> In every row in which the value of the function is 'T', there is an even
  number of 'T's assigned to the arguments of the function; and in every
  row in which the truth value of the function is 'F', there are an odd
  number of 'T's assigned to arguments. In this case, f('F', 'F', ...,
  'F') = 'T'. Another way to express this is that each variable always
  makes a difference in the truth-value of the operation or it never
  makes a difference.

Linearity for boolean functions means exactly linearity over a vector space.

Consider the field $\mathbb{F}_2$, i.e., the field with two elements $\{0,1\}$.  Here the "addition" is addition modulo 2, i.e., exclusive xor (xor).

A vector space $V$ over this field is basically a vector of $n$ elements of $\mathbb{F}_2$.  The "sum" of two vectors $v+w$ is obtained by taking the component-wise "sum", i.e., the xor of these two vectors.  In this way you can think of the space $\{0,1\}^n$ as a vector space over $\mathbb{F}_2$: just identify $\{0,1\}^n$ as the set of $n$-vectors over $\mathbb{F}_2$, so it becomes a $n$-dimensional vector space.

Now a boolean function $f:\{0,1\}^n\to \{0,1\}$ is considered linear iff it is a linear function from the vector space $\{0,1\}^n$ to the vector space $\{0,1\}$.  This amounts to saying that

$$f(x_1,\dots,x_n) = c_1 x_1 \oplus c_2 x_2 \oplus \cdots \oplus c_n x_n.$$

Here $\oplus$ represents the xor operation.

Why is this equivalent to the usual definition over vector spaces?  Recall from linear algebra that if $f:V \to W$ from vector space $V$ to vector space $W$, then it can be represented as multiplication by a $k \times \ell$ matrix, where $k = \dim V$ and $\ell = \dim W$.  Here we have a map $f: \{0,1\}^n \to \{0,1\}$, and $\dim \{0,1\}^n = n$, so $f$ can be represented as multiplication by a $n \times 1$ matrix.  Here everything is over the field $\mathbb{F}_2$, so you have to replace the usual addition and multiplication with addition and multiplication modulo 2.  Multiplication by the matrix $[c_1 c_2 \cdots c_n]$ is equivalent to the definition above, so we obtain the equivalence.

Caveat: linear vs affine. If we have $f:V \to W$, a linear function is one that can be represented as

$$f(x) = Mx$$

where $M$ is some matrix.  An affine function is one that can be represented as

$$f(x) = Mx+c$$

where $M$ is some matrix and $c$ is some vector.  A linear function has the property that $f(x)+f(y)=f(x+y)$.  An affine function does not; but it does satisfy the property that $f(x-y+z)=f(x)-f(y)+f(z)$.

Wikipedia's definition claims to be a definition of a linear function, but it's really a definition of an affine function.  Sometimes people don't distinguish between linear vs affine (they consider both of them to be linear functions).  That can be a bit confusing, especially if you're just learning these concepts. Unfortunately, Wikipedia seems to be one of those places that has lumped both concepts under the name "affine".

In your context, a boolean function $f:\{0,1\}^n\to \{0,1\}$ is affine iff it is a linear function from the vector space $\{0,1\}^n$ to the vector space $\{0,1\}$.  This amounts to saying that

$$f(x_1,\dots,x_n) = c_1 x_1 \oplus c_2 x_2 \oplus \cdots \oplus c_n x_n \oplus c_0.$$

The difference between linear vs affine is the extra constant term ($\oplus c_0$) that can appear in an affine function.  When Wikipedia provides its definition of a linear function, it is really providing a definition of an affine function.  I guess that implicitly Wikipedia is using the word "linear" to include both concepts.  Anyway, as long as you understand this little detail, all of the standard machinery of linear algebra applies.

See also https://en.wikipedia.org/wiki/Affine_transformation#Over_a_finite_field.


Arbitrary precision integer square root algorithm? Are there any known subquadratic algorithms for calculating the floor of the square root of an n bit integer?

The naive algorithm would be something like

def sqrt(x):
    r = 0
    i = x.bit_length() // 2
    while i >= 0:
        inc = (r << (i+1)) + (1 << (i*2))
        if inc <= x:
            x -= inc
            r += 1 << i
        i -= 1
    return r

This takes O(n) iterations, each one involving additions that are O(n) time, so it's O(n^2) time overall. Is there anything faster? I know that for the case of multiplication there are special algorithms that do better than quadratic time, but I can't find anything for square roots.

One of the problems with Newton's method is that it requires a division operation in each iteration, which is the slowest basic integer operation.

Newton's method for the reciprocal square root, however, doesn't. If $x$ is the number for which you want to find $\frac{1}{\sqrt x}$, iterate:

$$r_{i+1} = \frac{1}{2} r_i (3 - x r_i^2)$$

This is often expressed as:

$$w_i = r_i^2$$
$$d_i = 1 - w_i x$$
$$r_{i+1} = r_i + \frac{r_i d_i}{2}$$

That's three multiplication operations. The division by two can be implemented as a shift-right.

Now the problem is that $r$ is not an integer. However, you can manipulate it as such by implementing floating-point manually, and doing a bunch of shift operations to compensate when appropriate.

First, let's rescale $x$:

$$x' = 2^{-2e} x$$

where we would like $x'$ to be greater than, but close to, $1$. If we run the above algorithm on $x'$ instead of $x$, we find $r = \frac{1}{\sqrt x'}$. Then, $\sqrt{x} = 2^e r x'$.

Now let's split $r$ into a mantissa and exponent:

$$r_i = 2^{-e_i} r'_i$$

where $r'_i$ is an integer. Intuitively, $e_i$ represent the precision of the answer.

We know that Newton's method roughly doubles the number of accurate significant digits. So we can choose:

$$e_{i+1} = 2e_i$$

With a little manipulation, we find:

$$e_{i+1} = 2e_i$$
$$w_i = {r'_i}^2$$
$$x'_i = \frac{x}{2^{2e - e_{i+1}}}$$
$$d_i = 2^{e_{i+1}} - \frac{w_i' x'_i}{2^{e_{i+1}}}$$
$$r'_{i+1} = 2^{e_i} r'_i - \frac{r'_i d_i}{2^{e_i + 1}}$$

At every iteration:

$$\sqrt{x} \approx \frac{r'_i x}{2^{e + e_i}}$$

As an example, let's try calculating the square root of $x = 2^{63}$. We happen to know that the answer is $2^{31}\sqrt{2}$. The reciprocal square root is $\frac{1}{\sqrt{2}} 2^{-31}$, so we'll set $e = 31$ (this is the scale of the problem) and for our initial guess we'll pick $r'_0 = 3$ and $e_0 = 2$. (That is, we pick $\frac{3}{4}$ for our initial estimate to $\frac{1}{\sqrt{2}}$.)

Then:

$$e_1 = 4, r'_1 = 11$$
$$e_2 = 8, r'_2 = 180$$
$$e_3 = 16, r'_3 = 46338$$
$$e_4 = 32, r'_4 = 3037000481$$

We can work out when to stop iterating by comparing $e_i$ to $e$; if I've calculated correctly, $e_i > 2e$ should be good enough. We'll stop here, though, and find:

$$\sqrt{2^{63}} \approx \frac{3037000481 \times 2^{63}}{2^{31+32}} = 3037000481$$

The correct integer square root is $3037000499$, so we're pretty close. We could do another iteration, or do an optimised final iteration which doesn't double $e_i$. The details are left as an exercise.

To analyse the complexity of this method, note that multiplying two $b$-bit integers takes $O(b \log b)$ operations. However, we have arranged things so that $r'_i < 2^{e_i}$. So the multiplication to calculate $w_i$ multiplies two $e_i$-bit numbers to produce a $e_{i+1}$-bit number, and the other two multiplications multiply two $e_{i+1}$-bit numbers to produce a $2e_{i+1}$-bit number.

In each case, the number of operations per iteration is $O(e_i \log e_i)$, and there are $O(\log e)$ iterations required. The final multiplication is on the order of $O(2e \log 2e)$ operations. So the overall complexity is $O(e \log^2 e)$ operations, which is sub-quadratic in the number of bits in $x$. That ticks all the boxes.

However, this analysis hides an important principle which everyone working with large integers should keep in mind: because multiplication is superlinear in the number of bits, any multiplication operations should only be performed on integers which have the roughly the magnitude of the current precision (and, I might add, you should try to multiply numbers together which have a similar order of magnitude). Using integers larger than that is a waste of effort. Constant factors matter, and for large integers, they matter a lot.

As a final observation, two of the multiplications are of the form $\frac{ab}{2^c}$. Clearly it's wasteful to compute the all the bits of $ab$ only to throw $c$ of them away with a right-shift. Implementing a smart multiplication method which takes this into account is also left as an exercise.


Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems? Most of today's encryption, such as the RSA, relies on the integer factorization, which is not believed to be a NP-hard problem, but it belongs to BQP, which makes it vulnerable to quantum computers. I wonder, why has there not been an encryption algorithm which is based on an known NP-hard problem. It sounds (at least in theory) like it would make a better encryption algorithm than a one which is not proven to be NP-hard.

Worst-case Hardness of NP-complete problems is not sufficient for cryptography.  Even if NP-complete problems are hard in the worst-case ($P \ne NP$), they still could be efficiently solvable in the average-case. Cryptography assumes the existence of average-case intractable problems in NP. Also, proving the existence of hard-on-average problems in NP using the $P \ne NP$ assumption is a major open problem.

An excellent read is the classic by Russell Impagliazzo, A Personal View of Average-Case Complexity, 1995.

An excellent survey is Average-Case Complexity by Bogdanov and Trevisan, Foundations and Trends in Theoretical Computer Science Vol. 2, No 1 (2006) 1–106