Why an ARM processor with 32 bits address bus can address 4 billion different bytes? Why an ARM processor with 32 bits address bus can address 4 billion different bytes?
I know that $2^{32}$ is equal to about 4 billions, but shouldn't it be 4 billion bits and not bytes?

Hence if I want to find how many different words it can address it should be $\frac{2^{32}}{8}$ so I will have the number of bytes, and if I want to find the number of words I divide it again by 4 (because a word in ARM is 32 bits = 4 bytes).

While there have been computers built that use bit addressing, notably the Burroughs 1700, 1800, and 1900 mainframes and the Intel iAPX-432, the vast majority of machines use byte addressing.

This means that each possible address corresponds to a potential byte in memory.
Thus a 32 bit address would have a span of $2^{32}$ or $4,294,967,296$ bytes.

For completeness, the other category of machines use word addressing, where each address value corresponds to a word of memory. Examples here include the PDP-10 and CDC-6600 as well as many specialized DSP and embedded processors still in use.


Is using a more informed heuristic guaranteed to expand fewer nodes of the search space? I'm reading through the RMIT course notes on state space search.
Consider a state space $S$, a set of nodes in which we look for an element having a certain property.
A heuristic function $h:S\to\mathbb{R}$ measures how promising a node is.

$h_2$ is said to dominate (or to be more informed than) $h_1$ if $h_2(n) \ge h_1(n)$ for every node $n$. How does this definition imply that using $h_2$ will lead to expanding fewer nodes? - not only fewer but subset of the others.

In Luger '02 I found the explanation:

  This can be verified by assuming the opposite (that there is at least one state expanded by $h_2$ and not by $h_1$). But since $h_2$ is more informed than $h_1$, for all $n$, $h_2(n) \le h_1(n)$, and both are bounded above by $h^*$, our assumption is contradictory.

But I didn't quite get it.

So it seems you are intrigued about the relationship between the informedness of a heuristic function and its pruning power.

This is a well-known relationship established in the literature from the 80s (see for example Pearl, Judea. Heuristics, Addison-Wesley, 1984 who, by the way, has been awarded this year with the Alan Turing award).

As you already mentioned, $h_1$ is said to be more informed than $h_2$ if and only if $h_1(n)\geq h_2(n), \forall n$ in the state space. Now, provided that the heuristic function is also admissible (i.e., $h_1(n)\leq h^*(n)$ so that it never overestimates the effort to reach the goal, where $h^*(n)$ is the optimal cost to reach the goal state from node $n$), $h_2(n)$ is admissible as well since $h^* (n) \geq h_1 (n)$ by definition and $h_1(n)\geq h_2(n)$ by hipothesis, so that $h^* (n) \geq h_2 (n)$.

When considering that both heuristics are admissible, the following result applies to all $A^*$-like search algorithms: $f (n)<h^*(n)$ is a sufficient condition for expansion so that they expand all nodes meeting this property ---other algorithms expanding them as well include IDA$^*$ and RBFS. Since $f (n) = g(n) + h (n)$ where $g(n)$ is the (known) cost from the start state $s$ to node $n$ and $h(n)$ is your heuristic function (either $h_1$ or $h_2$) so that $f(n)$ is the estimated cost of the path $s-t$ when going through $n$, it immediately follows that there are, at least, as many nodes meeting this propertiy when $h_2$ is used instead of $h_1$.

The property mentioned above was already demonstrated in the original paper of the A$^*$ search algorithm and it is quite simple. In response to your comment, I posted a proof at the end of this message.

Hope this helps, this is my first post in this site,

Theorem: $f(n) < h^*(n)$ is a sufficient condition for expansion of node $n$ in A$^*$-like search algorithms provided that $h(n)$ is an admissible heuristic function.

Proof: I will proof this by induction on the number of steps of the A$^*$ search algorithm. Since the proof relies on the monotonicity of $f(n)$ I will first prove it.

$f(n) = g(n) + h(n)$ is a monotonically increasing function (when solving minimization problems). Recall the definitions of $g(n)$ and $h(n)$ provided above.

If $h(n)$ is a consistent heuristic function (i.e., a heuristic function is said to be consistent if it satisfies the triangular inequality $|h(n) - h(m)| \leq c(n,m)$ where $c(n,m)$ is the cost of the operator from $n$ to $m$), then the $f$-value of a node $m$ which is a descendant of node $n$ lies in the interval $[g(n)+c(n,m)+h(n)-c(n,m), g(n)+c(n,m)+h(n)+c(n,m)]=[g(n)+h(n), g(n)+h(n)+2c(n,m)]\geq g(n)+h(n) = f(n)$.

Incidentally, the wikipedia says: "If $h(n)$ is consistent then the value of $h(n)$ for each node along a path to goal node are non decreasing" but this is not strictly speaking true, this is just a result of the original definition provided above.

If $h(n)$ is an $inconsistent$ heuristic function (so that it that does not satisfy the aforementioned property) then $f(m)$ can be arbitrarily smaller than $f(n)$. However, since $h(n)$ is an admissible heuristic function, $max\{h(n)-c(n,m), h(m)\}$ is an admissible heuristic function for node $m$ and using it the same interval results.

Now, bearing in mind that $f(n)$ increases along a path to the goal and that $h(n)$ never overestimates the effort to reach the goal state, it is straightforward to prove the theorem by induction

Base case: the start node $s$ is introduced in the OPEN list and it is selected for expansion. Since $f(s)=g(s)+h(s)=h(s) \leq h^*(s)$ (by hypothesis of the admissibility of $h(\cdotp)$) the theorem has been proved for the base case.

Induction step: at each iteration of the A$^*$ search algorithm the first node $n$ in OPEN is selected for expansion. By induction, it is assumed that $f(n) \leq h^*(n)$. If $n = t$ (the target state), the search immediately terminates and $f(n)=g(n)+h(n)=g(n)$ is the optimal cost of the path $s-t$. Otherwise, the descendants of node $n: n_1, n_2, ... n_k$ are inserted into the OPEN list in increasing order of $f(\cdotp)$. I will now proof that the expansion of $n$ leaves the OPEN list in such a state that the first node $m$ has $f(m) \leq h^*(m)$, because it will be expanded in the next iteration this would proof the theorem by induction. Two cases might arise:

Case 1: one of the descendants of node $n, n_i$ has an $f$-value $f(n_i) = f(n)$ (recall that $f(n)$ is a monotonically increasing function). In this case, it would be ranked first (maybe along with other nodes in case of a tie), since it has the same $f$-value of its ancestor which was already first in the OPEN list.

Case 2: all the descendants of node $n, n_i, \forall i=1, \ldots k$ have $f(n_i) > f(n)$. In this case, these nodes would be arranged in OPEN after the second state in OPEN when $n$ was selected for expansion. Since $f(n_i)\leq h^* (n_i)$, but they are larger than the second best node in OPEN, node $m$ has to verify that $f(m) \leq h^*(m)$ and this concludes the proof.


Game on the graph with matchings The game on the graph $G$ is defined as follows. Initially, the chip is located at one of the vertices (let's call it the starting one). The players take turns, on each move it is necessary to move the piece along any outgoing edge to the vertex, where the piece has never been.
The one who cannot make a move loses. How to Prove that the former wins if and only if
the starting vertex lies in all maximal matchings?

First of all, let me correct maximal matchings (that is, matchings which cannot be extended) to maximum matchings (that is, matchings of maximal size).
Suppose first that the starting vertex $v$ doesn't lie on all maximum matchings. Pick a maximum matching $M$ which doesn't contain $v$. The second player will always play an edge from $M$ – we will show that this is always possible. Suppose that the game play so far has been $v,a_1,b_1,\ldots,a_t$. We know that $M$ doesn't touch $v$. If it also doesn't touch $a_t$, then this is an augmenting path (check!), which contradicts the maximality of $M$. Hence $M$ must contain an edge $(a_t,b_t)$, which the second player can play.
Suppose next that the starting vertex $v$ does lie on all maximum matchings. Pick some maximum matching $M$ which contains $v$. The first player will always play an edge from $M$. Suppose that the game play so far has been $v,a_1,\ldots,b_t$. If $M$ doesn't touch $b_t$ then we could switch edges according to this "almost-augmenting" path to obtain another maximum matching which doesn't contain $v$. Hence $M$ must contain an edge $(b_t,a_{t+1})$, which the first player can play.


Sorting in computing longest increasing subsequence I am currently reading the paper On computing the length of longest increasing subsequences by Michael L. Fredman.
I'm struggling to understand parts of the proof of Theorem 3.5,
especially this bit:

Now consider the following enhancement $A^*$ of $A$. Whenever $A$ concludes that $L < k$, $A^*$ continues to completely sort $S$ [...]

This is used to show a bound for $L \ge k$, but why are they sorting the sequence?

Here is a sketch of the proof of Theorem 3.5:

If there is a comparison-based algorithm for LIS using $m$ comparisons in the worst case, then we can convert it to an algorithm which answers the question "is $L \geq k$" (for some fixed $k$) using $m$ comparisons.
Given an algorithm which answers the question "is $L \geq k$" using $m$ comparisons, we can convert it into an algorithm using $m + n \log k + O(n)$ comparisons which sorts the input whenever $L < k$.
Any comparison-based algorithm which sorts the input whenever $L < k$ must perform at least $\log S(n,k)$ comparisons (since it has at $S(n,k)$ possible outputs).
Consequently, every comparison-based algorithm for LIS must use at least $\log S(n,k) - n \log k - O(n)$ comparisons.
The theorem follows by choosing $k = \lfloor 3\sqrt{n} \rfloor$ and using the asymptotics of $S(n,k)$.

We sort the input in order to use a lower bound on sorting.


Complexity of "Fast Poisson Disk Sampling in Arbitrary Dimensions" I came across the paper Fast Poisson Disk Sampling in Arbitrary Dimensions which gives an algorithm for generating Poisson disk points in $\mathbb{R}^n$.
It's claimed that the algorithm is linear time. However, I wonder if this assumes the dimension n is constant.

My understanding of the analysis is that to generate $N$ points requires $2N-1$ iterations, and each iteration is constant time.
I agree with the $2N-1$ iterations, but I'm not sure about each iteration being constant time.

In each iteration, they sample a small constant $k$ points, and then check whether or not these points are near to any of the previously generated points using a background grid to assist. However, isn't the number of neighboring cells to check exponential in $n$?
It seems like the runtime of the given algorithm using the background grid should be something like $k N \exp(n)$, (or $kN^2$ if you just check the other points directly).

Have I misinterpreted the algorithm or the analysis? I get that for a fixed $N$ it will be constant (assuming $k$ is constant). Is that the standard assumption when saying an algorithm is "linear time"? To me this seems a bit misleading because they mention dimension in the title.
If you go to high enough dimension and use the "constant time" algorithm, the constant will be exponential in $n$ which means the algorithm is not "fast" in "arbitrary dimensions".

As an afterthought, does it even make sense for $k$ to be constant. If you don't increase $k$ exponentially with $n$ then the "density" (number of points per volume) of the points will go to zero (although this is more of a "modeling" choice than an analysis choice).

I have just implemented this algorithm, generalized for an arbitrary number of dimensions. You are absolutely correct in your suspicions about the exponential growth with $n$, as far as I see.
Each of these $2 N - 1$ iterations require a lookup in the neighbourhood for each candidate, and the neighbourhood scales up exponentially with the dimension: from a line to a square to a cube, etc. A more accurate implementation can slow this growth by excluding the corners of the hypercube in higher dimensions, since they don't fulfil the distance criteria, but it won't stop the exponential growth.
Increasing the $k$ for the higher dimensions, on the other hand, does not make much sense to me. $k$ are the candidate points to be tested for acceptance, so if you find at least one valid point among them, the algorithm will continue until the entire space is filled. If anything, I think it's easier to find a valid point for a higher-dimensional case, since there are more degrees of freedom.
Also, here's a link to my implementation: https://github.com/diregoblin/poisson_disc_sampling


Proving that there exists a distance $d$-dominating set of size $O(n/\delta)$ Let $d > 1$, and consider a graph $G = (V,E)$ on $n$ vertices. A distance $d$-dominating set of $G$ is a set $D \subseteq V$ with the property that for any $v \in V$, either $v \in D$ or $v$ is at most distance $d$ from some vertex in $D$. Prove that if $\delta$, the minimum degree of $G$, satisfies $\delta > 50$, then $G$ has a distance $d$-dominating set of size $O(n/\delta)$.

I am considering a greedy algorithm to construct $D$. In each step, pick a vertex that covers the maximum number of "uncovered" vertices (i.e., vertices that are of distance $> d$ from any element in $D$). For each vertex $v$, let $C(v)$ be the set consisting of $v$ together with all of that vertices that are at most distance $d$ from $v$. Suppose that during the process of picking vertices the number of vertices $u$ that do not lie in the union of the sets $C(v)$ of the vertices chosen so far is $r$. Then by assumption, the sum of the cardinalities of the sets $C(u)$ over all uncovered vertices $u$ is at least $r x$....

The drawback of this approach is that I don't see how $x$, a lower bound on the number of vertices within distance $d$ of a vertex in $G$, can be more than $\delta + 1$ (i.e., the order of the complete graph $K_{\delta + 1}$). Unfortunately, if we use this lower bound for $x$ in general, we won't get a dominating set of size $O(n/\delta)$.

Let $S$ be a maximal set of vertices in which any two vertices are at distance at least 3. (Note maximal just means that $S$ cannot be enlarged by adding new vertices.) By design, any other vertex is at distance at most 2 from some vertex in $S$, and therefore $S$ is a 2-dominating set. On the other hand, if we define the $B_1(v)$ to consist of all vertices at distance at most 1 from $v$, then the sets $B_1(v)$ for $v \in S$ are disjoint. Since the minimum degree is  $\delta$, the size of each set $B_1(v)$ is at least $\delta+1$, hence $|S| \leq n/(\delta+1)$.


Minimum no. of coin flips (switch) needed so that all coins face the same side (Heads or Tails) Consider this, I have n coins and I have placed them in a random order (1st coin is Head, 2nd is Tails etc.). You do not know the order. You can flip one coin at a time and then I tell you if all the coins face the same side or not. You continue flipping until all coins are facing the same side.
I tried breaking it down to smaller base cases:
(1) when there is 1 coin: no need to flip
(2) when there are 2 coins: the only odd cases you can have are {H,T} or {T,H}, so flipping the first coin will do the trick
(3) when there are 3 coins: there are 6 odd cases you can end up, but 3 of them are similar to one another, hence only 3 cases to consider with {H,T,T}, {T,H,T} and {T,T,H} (same with one T and 2 heads).
The strategy for this could be flipping the 1st coin, if the order is still not made then flip the second coin, if the order is still not made then flip the 1st coin again.

I am having a hard time coming up with a general algorithm for n coins. Any ideas?

Here is a general algorithm. The maximum number of flips needed is $2^{n-1}-1$.

Input: coin 0, coin 1, coin 2, ..., coin $n-1$

Procedure:
$\quad$  If all coins face the same side, return.

$\quad$  For $i$ from 1 to $2^{n-1}-1$ inclusive:
$\quad\quad$  If $i$ is divisible by $2^k$ but not $2^{k+1}$:
$\quad\quad\quad$  Flip coin $k$
$\quad\quad\quad$  If all coins face the same side, return.

For example, if there are no more than 8 coins, then just flip the coins at the following places successively as long as all faces do not face the same side.

0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0


Linear time algorithm for finding $k$ shortest paths in unweighted graphs Definition. Given an unweighted graph $G=(V,E)$ and two vertices $s$ and $t$,
  the $k$-shortest-paths problem is finding the $k$ shortest simple paths
  between $s$ and $t$ in $G$.

Note that the length of these paths is not necessarily equal, and vertices $s$ and $t$ are necessarily $k$-connected. I was wondering if there is a linear time (in terms of $n$ and $m$) algorithm for this problem (assuming that $k$ is fixed).

I have looked at a few papers in the literature, such as "A New Implementation Of Yen's Ranking Loopless Paths Algorithm" but the time complexity is really high $O(Kn(m+nlogn))$. Also, the other paper by Epstein "Finding the k shortest paths" presents an algorithm that finds the $k$ shortest paths that are not necessarily simple paths with running time $O(n+m+k)$.

Is there a linear-time algorithm for the $k$-simple-shortest-paths problem (in terms of $n$ and $m$) on unweighted graphs, where $k$ is fixed?

No. The best times known can be found in the survey "Implementations and empirical comparison of k shortest loopless path algorithms".

As a note, it is impossible to get linear times in the weighted case. There are lower bounds for the shortest path (i.e., k=1), which are not linear.

In the directed acyclic case you might have linear times for the k-SP, but I think is an open problem.

Cheers


Complexity of Verification for Clique with Adjacency Matrix I am having trouble getting my head around what the complexity of the verification step for the CLIQUE problem would be -- specifically if an adjacency matrix is used. I know in general the complexity for this problem would be O(k^2) * edges in G.

This is the specific question I am attempting to solve:
Select the correct complexity of the verification step for CLIQUE problem. Assume that the candidate solution is size k, and that the Graph with n vertices is represented by an adjacency matrix (i.e., constant time edge lookups).

My thoughts:
If there are k vertices in the candidate solution, I will need to iterate k times. For each of those vertices I will need to check that corresponding row in the adjacency matrix to see if the sum of that row is k - 1. in other words checking to see if the deg(k) for each k is k-1.

Should I consider that k^2? Or would it be (k^2 * n) since I would need to add 1 for each of the n vertices on that row to find out if the row sum is k-1?

Here is an algorithm for verifying that the clique $C[1],\ldots,C[k]$ is contained in the graph whose adjacency matrix is $A$:

for i from 1 to k:
   for j from 1 to i-1:
      if A[i,j] = "no edge", then return "No"
return "Yes"

What is the running time of this algorithm?


Do static and dynamic scoping matter to the closure of a function? If I am correct,

The closure of a function is the non-local environment of the function.
the non-local environment of a function is different depending on static or dynamic scoping.

So is the closure of a function also different depending on static or dynamic scoping?

Thanks.

I'd view it this way:

In dynamic scoping, functions only ever access the local environment
In lexical scoping, functions access the environment in which they are created. Because this is non-local to their calling environment, it must be stored in a closure.

Closures really aren't a thing in dynamic scoping: instead of looking for variables in the closure, you look for variables in the environment in which the function was called.

The process of closing over (storing) the environment is what makes static scoping static scoping.


Proving that a language is not Recursive I have the following language:

T = {M | there exists w such that M accepts w within |w| steps}

I am trying to prove that this language is not recursive and that it is recursive-enumerable. To prove that it is NOT recursive I considered the following steps:

1) Assume that it was recursive
2) Conside input w of infinite length
3) Meaning, we get infinite steps that M can perform before halting. So we get the halting problem when considering this infinite input, and we are saying that we can decide it
4) halting problem is not decidable. contradiction

What do you think about this proof? I'm not sure that I can consider an infinite length input, and I'm not sure wither turing machines in general should deal with infinite inputs lengths.

I tried to search for answers with no luck so far. Any help would be much appreciated. Thanks.

Proving that the language is in RE is quite easy: simulate the machine on every input $w\in \Sigma^*$, in minlex order, for $|w|$ steps. If an input is accepted - accept.

Proving that the language is undecidable can be done by reduction from
$$A_{TM}=\{<M,w>: M\text{ accepts }w\}.$$
A possible reduction:

Given input $<M,w>$, construct a new TM $M'$ that works as follows: given input $x$, simulate $M$ on $w$. If $M$ accepts, accept. If $M$ rejects, reject, and of course if $M$ does not halt then so will $M'$.

Now, if $<M,w>\in A_{TM}$, then $M$ accepts $w$ within $t$ steps, for some $t\in \mathbb{N}$. Thus, for a word $x$ with $|x|>>t$ (the size of $|x|$ needed depends on the manner of simulation, but can be done with $O(t\log t)$), the simulation of $M$ on $w$ will terminate within $|x|$ steps, and $M$ will accept $w$, so $M'$ will accept $x$, and $<M'>\in L$.

Conversely, if $<M,w>\notin A_{TM}$, then $M'$ will not accept any input, so $<M'>\notin L$, and you are done.


Problems for which algorithms based on partition refinement run faster than in loglinear time Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement quite efficiently. I don't know of any other problems that are usually solved using partition refinement other than the ones listed on the Wikipedia page. Out of all these problems, the Wikipedia page mentions two for which algorithms based on partition refinement run in linear time. There's the lexicographically ordered topological sort [1] and an algorithm for lexicographic breadth-first search [2].

  Are there any other examples or references to problems that can be solved using partition refinement very efficiently, meaning something better than loglinear in terms of time?

[1] Sethi, Ravi, "Scheduling graphs on two processors", SIAM Journal on Computing 5 (1): 73–82, 1976.

[2] Rose, D. J., Tarjan, R. E., Lueker, G. S., "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing 5 (2): 266–283, 1976.

Some linear time modular decomposition algorithms use (some type of) partition refinement, see e.g. these algorithms for directed and undirected graphs.


How do O and Ω relate to worst and best case? Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic complexity for an array of $n$ elements.

My idea was, that it is obvisously $O(\log n)$, or $O(\log_2 n)$ to be more specific because $\log_2 n$ is the number of operations in the worst case. But I can do better, for example if I hit the searched element the first time - then the lower bound is $\Omega(1)$.

The lecturer presented the solution as $\Theta(\log n)$ since we usually consider only worst case inputs for algorithms.

But when considering only worst cases, whats the point of having $O$ and $\Omega$-notation when all worst cases of the given problem have the same complexity ($\Theta$ would be all we need, right?).

What am I missing here?

Landau notation denotes asymptotic bounds on functions. See here for an explanation of the differences among $O$, $\Omega$ and $\Theta$.

Worst-, best-, average or you-name-it-case time describe distinct runtime functions: one for the sequence of highest runtime of any given $n$, one for that of lowest, and so on..

Per se, the two have nothing to do with each other. The definitions are independent. Now we can go ahead and formulate asymptotic bounds on runtime functions: upper ($O$), lower ($\Omega$) or both ($\Theta$). We can do either for worst-, best- or any other case.

For instance, in binary search we get a best-case runtime asymptotic of $\Theta(1)$ and a worst-case asymptotic of $\Theta(\log n)$.


Relational Algebra: existential quantifiers So i have the following question and template answer:
Question: List the names of managers who have at least one dependant.
Answer: {e.Fname, e.Lname | EMPLOYEE(e) AND (∃d)(∃t)(DEPARTMENT(d) AND DEPENDANT(t) AND e.Ssn = d.Mgrssn AND t.Essn = e.Ssn) }
My answer was exactly the same except that instead of the (∃d)(∃t)(...) section I said (∃d)(DEPARTMENT(d) AND e.Ssn = d.Mgrssn) AND (∃t)(DEPENDANT(t) AND t.Essn = e.Ssn).
My question is basically are these equivalent?

Let me concentrate, as you asked, on section $(\exists d)(\exists t)(\cdots)$.
In case when one part of conjuction is "not depend" on letter under existence quantifier, holds
$$(\exists d)(A \text{ and } B)\Leftrightarrow  (\exists d)(A) \text{ and } B$$
Where we assume $B$ does not containt letter $d$.
$$$$
In your case, for simplicity, let make following designations:
$$\begin{array}{l}
A(d) = \text{ DEPARTMENT(d) }\\
B(t) = \text{ DEPENDANT(t) } \\
C(d) = (\text{e.Ssn = d.Mgrssn})\\
E(t) = (\text{t.Essn = e.Ssn})
\end{array}$$
and assume, that $A,C$ doesn't depend on $t$ and $B,E$ doesn't depend on $d$. Then we have
$$(\exists d)(\exists t)\big(A(d) \text{ and } B(t)\text{ and } C(d) \text{ and } E(t)\big) \Leftrightarrow \\
\Leftrightarrow (\exists d)\big(A(d) \text{ and } C(d)\big) \text{ and } (\exists t) \big(B(t)\text{ and } E(t)\big)$$
So, you are right, they are equivalent in reviewed case.
Generally we cannot distribute existence quantifier  with respect to $\text{AND}$(conjunction) operation as shows example: take $A=$"$d$ is even" and $B=$"$d$ is odd". Then, of course, sentence "$(\exists d)(A) \text{ and } (\exists d)(B)$" is true, but sentence "$(\exists d)(A \text{ and } B)$" is false.


Meaning of "pushing x down" and "pulling x up" in database query handling In this book there is a lot of mention of "pushing x down". For example:

  Pushing NOT operations down and eliminating them

  NOT operations need to be pushed downwards for correctness reasons. Attention has to be paid to the IS NOT NULL and IS NULL predicates. XXX complete set of rules go into some table

  ...

  Typical steps during this rewrite phase are unnesting nested
  queries, pushing selections down, and introducing index structures.

  ...

  When pushing down projections, we only apply them just before a pipeline breaker

  ...

  Logical query optimization turned out to be a little difficult: pushing selections down and reordering joins are mutually interdependent.

  ...

  In this section, we consider pushing down (pulling up) unary operators into (from) the arguments of binary operators. Thus, we are interested in equivalences of the form $f(e_1 ◦ e_2) ≡ f(e_1) ◦ e_2$ and $f(e_1 ◦ e_2) ≡ e_1 ◦ f(e_2)$.

From that last example I can vaguely see that e.g. $f(e_1 ◦ e_2) ≡ f(e_1) ◦ e_2$ there is a "moving out" of $e_2$ from the equation, but I'm not sure what direction up/down and not sure what the meaning/purpose is in doing this. Wondering what exactly this means.

I would normally say "pushing inward"/"pulling outward", but "down"/"up" make sense if you are thinking in terms of syntax trees and, being a computer scientist, your trees grow downward.

In (classical) logic there are rules like De Morgan's rule which says $\neg(P\land Q)\equiv(\neg P)\lor(\neg Q)$ and many others that allow you to move negation either outward/upward toward the outermost connective (reading the equivalence from right to left), or inward/downward towards the leaves of the syntax tree (reading the equivalence left to right). If we actually draw out the syntax tree it will look like

    ¬             ∨
    |            / \
    ∧      ≡    ¬   ¬
   / \          |   |
  P   Q         P   Q

which illustrates the down/up movement. In general, we can use any available equivalences for any sort of expression to move operations around. In the case of negation, since we have $\neg\neg P\equiv P$ it is often desirable to try to move them toward each other. Systematically moving them towards the leaves, i.e. inward/downward, is one way to accomplish this. Often these types of cancellations are one of the goals of applying these equivalences. There are other concerns too. For example, if it is possible to remove duplicates before a join rather than after, that could be extremely advantageous.

  Logical query optimization turned out to be a little difficult: pushing selections down and reordering joins are mutually interdependent.

This just states that sometimes the available equivalences are not so simple, and an equivalence might simplify a selection at the cost of making a join more complicated or vice versa and so the equivalences can't just be blindly applied in a fixed direction (at least not if you want a good result).


Question about Complete partially Directed Acyclic Graph I am reading CPDAG, can anyone please explain why G1 and G3 are not equivalence classes as in the picture below?
Thank you very much!
according to https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume18/acid03a-html/node2.html .

"Theorem 1 [59]   Two DAGs are equivalent if and only if they have the
same skeleton and the same v-structures.
The skeleton of a DAG is the undirected graph that results from ignoring the directionality of every edge.
A v-structure in a DAG $H$ is an ordered triplet of nodes,
$(x,y,z)$, such that (1) $H$ contains the arcs  $x\rightarrow y$ and
$y \leftarrow z$, and (2) the nodes $x$ and $z$ are not adjacent in
$H$. A head-to-head pattern (shortened h-h) in a DAG $H$ is an ordered
triplet of nodes, $(x,y,z)$, such that $H$ contains the arcs
$x\rightarrow y$ and  $y \leftarrow z$. Note that in an h-h pattern
$(x,y,z)$ the nodes $x$ and $z$ can be adjacent."
The concept of equivalence of DAGs partitions the space of DAGs into a set of equivalence classes.

They have different v-structures: $G_1$ has the v-structures $(x_3,y,x_4),(x_4,y,x_3)$, whereas $G_3$ has the v-structures $(x_1,x_4,y),(y,x_4,x_1)$.


Identification and the definition of data type A frequently cited definition of data type is that it is a set of values and a set of operations of those values.

I've never read any mention along the lines of a type must be capable of being identified, although the programming languages I've encountered use names to distinguish different types.

Is the use of identifiers then just a convenience for the programmer? In principle, couldn't you just replace the identifier with the type definition each time it was needed?
Are there any programming languages that don't use named types?
And, if so, what implications, if any, are there of this? (One possibility I can think of is that it means there is no nominal typing.)

Is the use of identifiers then just a convenience for the programmer? In principle, couldn't you just replace the identifier with the type definition each time it was needed?

Yes. You can have a strongly typed language that completely infers types, where the program at no point refers to the types, at all, ever.

For example, you could write programs in Hindley Milner (without the gamut of extensions you see in something like Haskell) without ever referring to a type. You shouldn't, but you could.

Types and values are usually separate in non-dependently typed programs, and if your system allows for full type reconstruction, you don't need to refer to them in your code.

  Are there any programming languages that don't use named types?

Doubtful. When you use an integer but the program expects a boolean, the compiler has to tell you something. So it's going to want to give a name to those types.

Without primitive types, you can't do much useful in a programming language, so you're going to want to at least give your primitive types names.

Also, having all sum-types be anonymous would be extremely tedious. You could refer to the List type as T . T = Nil + Cons T, and occasionally you will see something like this on paper, but this is going to get hard to use very fast. As you can see, recursive types are particularly awkward in this scheme, and you usually end up needing the type-level equivalent of the $Y$-combinator.

Now, if you use things like Church encoding, you can get away without having primitive types, where everything is probably going to be higher-rank polymorphic types. For example, you can encode natural numbers as  forall a . (a -> a) -> a -> a. But again, this is something more useful on paper than in the hands of a programmer.

  And, if so, what implications, if any, are there of this?

None that I can think of, other than the lack of nominal typing, and you could even fake nominal typing by attaching some singleton type to your values.

For example, ((), forall a . (a -> a) -> a -> a) is isomorphic to forall a . (a -> a) -> a -> a, but now you have two isomorphic types the system considers distinct.


Two definitions of the Reed-Muller code I found two definitions Reed-Muller codes being used in literature. More specifically for any $n \in \mathbb{Z}^+$ and $1 \leq d \leq n$ we define the set $RM(d,n)$ in two possible ways,

1.
$RM(d,n) = \{ f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2 \vert $f$ \text{ is a polynomial of degree at most } $d$\} $

2.
$RM(d,n) = \{ f: \mathbb{F}_2^n \rightarrow \mathbb{F}_2 \text{ s.t} f(x) = (-1)^{P(x)} \vert $P$ \text{ is a polynomial of degree at most } $d$ \text{and  with integer coefficients of magnitude at most }d \}$

Are these the same?
In the first definition how is "degree" defined? Is $f$ assumed to be a sum over monomials where each literal occurs with power $1$ and then the final answer of the polynomial is evaluated $mod$ $2$ or is $f$ to be thought of as a generic degree $d$ polynomial such that when its input is restricted to $\mathbb{F}_2^n$ its output gets restricted to $\mathbb{F}_2$?

They are the same.

In the first definition, we identify $\mathbb{F}_2$ with elements $\{0,1\}$, with $+$ defined to be addition modulo 2 and $\times$ defined to be multiplication modulo 2.
In the second definition, we identify $\mathbb{F}_2$ with elements $\{1,-1\}$ and $+$ defined to be multiplication modulo 2 and $\times$ defined as $x \times y = \max(x,y)$.

Both representations of $\mathbb{F}_2$ are isomorphic.

Degree is defined as usual for the polynomial ring $\mathbb{F}_2[x_1,\dots,x_n]$; see your favorite math textbook for the formal definition.  Do note that $f$ is a multivariate polynomials, not a univariate polynomial.

The "integer coefficients of magnitude at most $d$" is weird and doesn't belong.  The definition would make more sense with that phrase omitted.  Pedantically speaking, that phrase makes no sense, as a polynomial over $\mathbb{F}_2$ by definition has coefficients in $\mathbb{F}_2$, so it makes no sense to speak of them as "integers", and they don't have a magnitude.  (Alternatively, if we interpret it loosely/informally, that phrase becomes redundant and dead and ultimately has no effect.)


Algorithm to generate the number of tuples that satisfy the sum equals product problem. Problem Statement:
Let $n\geq 2$ be a natural number. We are interested in sequences $(x_1,x_2,...,x_n)$ of natural numbers such that
$$x_1+x_2+...+x_n = x_1x_2...x_n\text{ and }x_1\leq x_2\leq...\leq x_n.$$
Let $A(n)$ denote the set of all such sequences. Moreover, we denote by $a(n)$ the cardinality of the set $A(n).$  The goal is to generate $a(n)$ for $n\geq 2.$

Attempt: Naive attempt in Python 3.5

from itertools import product

def prod(tup):
    """
    Computes the product of all elements in the tuple.
    """
    p = 1
    for i in tup:
        p = p*i
    return p

def a(n):
    """
    Check Sum Equals Product Property.
    """
    list_of_tuples = list(product(range(1,2*n+1), repeat = n))
    count = 0
    for tup in list_of_tuples:
        if sum(tup) == prod(tup):
            count = count + 1
    return count

It can be proved that for all $n\geq 3$ that
$$x_1+x_2+...+x_n\leq 2n.$$
So I just used the bound $1\leq x_i\leq 2n$ for all $i=1,2,...,n.$ I know this is really bad because it is $O((2n)^n)$ and I not generating non-decreasing sequences. I guess one would want to reduce the number of tuples to check, but I am not sure how to do this. Perhaps someone has an idea?

One simple optimization you can use is as follows: since $x_1 + \cdots + x_n \leq 2n$, it follows that at most $\log_3 (2n)$ values are at least 3. You can go over all possible values for these $O(\log n)$ elements, and for each of them it should be easy to determine whether they can be completed (by adding only 1s and 2s) to a solution.

Taking this one step further, you can start adding elements to the sequence, from $x_n$ down, keeping track of the current product. If it exceeds $2n$, you can immediately halt.

You can probably optimize this much further, but this is already a good start.

Alternatively, OEIS has your sequence as A033178, and a table for $n \leq 10000$.


one for loop wraps 2 indexof method, what is the time efficiency? I'm confused about how to know the time / space efficiency.

If there is an array whose size is n, do a for loop on this array, so that time efficiency should be O(n) = n, where n is array size. then if I have two indexof methods in the loop, indexOf and lastIndexOf, should the O(n) become n*(2n)? because each of the indexof methods has the time efficiency of n as well just like a for loop?
how to know the space efficiency of this method?

char firstNotRepeatingCharacter(String s) {

    char[] str = s.toCharArray();
    // n
    for (int i = 0; i < str.length; i++) {

        char item = str[i];
        // 2n
        if(s.indexOf(item) == s.lastIndexOf(item)) return item;

    }
    // 2n2

    return '_';
}

Yes, you are correct. But time complexity we measure only in big-O notation.

So the code above has time complexity $\mathcal O(n^2)$

The space complexity depends on indexof's space complexity. Assuming it was done with a for loop and a simple comparison, the space complexity would be $\mathcal O(log(n))$ - as the  storing the array length $n$ required $log(n)$ bits, and therefore keeping in memory the index i will take at most that much space.


Howto formally go about proving that two LTL formulas are equivalent? Do they need to "unwind" exactly to the same set of paths or does it suffice when one set is contained in the other ?

Or is it sufficient to argue that M,s satisfies both LTL formulas for any starting s and a model M, that is, reaching with both at "true" ?

Generally.

Let $M$ be any model. Further, let $s$ be any state $M$ might be in.

Let $\phi$ and $\psi$ be two LTL formulas.

If $\forall$ paths $\pi$ in $M$ starting at $s$ it holds that $\pi \models \phi \leftrightarrow \pi \models \psi $ then we say  $\phi$ and $\psi$ are equivalent ($\phi \equiv \psi$).

More succinct

$(\pi \models \phi \leftrightarrow \pi \models \psi) \rightarrow (\phi \equiv \psi)$.

Example. Prove that $\neg G \chi \equiv F \neg \chi$.

If we can show that $(\pi \models \neg G \chi \leftrightarrow \pi \models F \neg \chi)$ we would have proven that $(\neg G \chi \equiv F \neg \chi)$. So we reduce to the former.

Step 1. We show that $(\pi \models \neg G \chi \rightarrow \pi \models F \neg \chi)$:

$\{(\pi \models \neg G \chi) \leftrightarrow (\pi \not\models G \chi) \leftrightarrow (\forall i \geq 1, i \in \mathbb{N}. \pi^i \not\models \chi)\} \rightarrow \{(\exists i \geq 1, i \in \mathbb{N}. \pi^i \not\models \chi) \leftrightarrow (\exists i \geq 1, i \in \mathbb{N}. \pi^i \models \neg\chi) \leftrightarrow (\pi \models F \neg \chi)\}.$

Step 2. We show that $(\pi \models F \neg \chi  \rightarrow \pi \models \neg G \chi)$:

$\{(\pi \models F \neg \chi) \leftrightarrow (\exists i \geq 1, i \in \mathbb{N}. \pi^i \models \neg\chi) \leftrightarrow (\exists i \geq 1, i \in \mathbb{N}. \pi^i \not\models \chi)\} \rightarrow \{?\}.$ How do I get back?

Ok. I can semantically understand that if for every model and any path in it, it is true eventually that $\neg \chi$ holds, it cannot be the case that generally for every model and any path in it $\chi$ will hold. How can I write this down formally?

Would for $\{?\}$: $\{\neg (\forall i \geq 1, i \in \mathbb{N}. \pi^i \models \chi) \leftrightarrow (\neg (\pi \models G \chi)) \leftrightarrow (\pi \not\models G \chi) \leftrightarrow (\pi \models \neg G \chi)\}$ be a valid argumentation ? It looks different than Step 1. and anyway is there a rule to pull $\neg$ "out" from $\not\models$ this way ?

The semantics of LTL is (initially) defined with respect to infinite computations. So in that sense, two formulas $\psi_1,\psi_2$ are equivalent if for every computation $\pi$ it holds that $\pi\models \psi_1$ iff $\pi\models \psi_2$.

So in this sense - yes, you need the formulas to unwind the same set of computations.

The semantics is then extended to Kripke structures in the $ALTL$ model, meaning that a formula is satisfied in a structure if all its computations satisfy the formula. However, testing for equivalence should be done with respect to paths.

As for proving formally the equivalence of formulas: if this is an exercise, it will probably be easiest to analyze the formulas and prove that a path satisfies the first iff it satisfies the second. However, if you are handling complex formulas, then the best approach will probably be via nondeterministic Buchi automata, by testing the equivalence of the automata that correspond to the formulas. In practice, there are tools to do just that, but doing it manually may prove quite time-consuming (as the problem is PSPACE complete).


How to estimate maximum n given complexity and amount of time? Say you've implemented a program that completes it's work with O(2n) time complexity, and you measure the actual running time of the program as:

n1: 0.006s
n100,000: 16.057s

Since time will grow exponentially as n increases, what is the typical way to estimate the maximum n given a time t? For example, if time t is 1 minute or 1 hour, how do you "correctly" estimate n?

You can't.  Mathematically, you can't conclude anything about the running time for all $n$, given just two points (given the running time at just two values of $n$).  There are many possible curves that might go through those two curves; two points aren't enough to determine a curve.  The running time might be something like

$$\frac{1}{2^{100}} 2^n + n^2.$$

Or, it might be something like

$$\frac{1}{2^{95}} 2^n + \frac{1}{10000} n.$$

Or, the running time might be

$$\frac{1}{100000000} n^2.$$

Or any number of other possibilities.

That said, in practice it seems very unlikely that you have an algorithm whose running time on all instances of size $n$ is $\Theta(2^n)$... and yet for $n=100,000$ it completes in 16 seconds.  That's a bit silly.  In practice, it could happen if the algorithm is sufficiently weird, but not bloody likely in practice.


Number of cliques in a graph I think the number of cliques in a graph is generally exponential in the of vertices of that graph. Does anyone know any reference for that?

I am assuming you mean the number of maximal cliques, as the number of cliques of a complete graph is trivially $2^n$ (any subset of the vertices forms a clique).

For the number of maximal cliques, take the complement of a disjoint union of triangles.  Since the number of maximal independent sets is exactly the same (in the complement), you can count the number of maximal independent set in a graph that is a disjoint union of triangles.  This number is $3^{n/3}$ (Moon and Moser, 1965).

See also: The number of cliques in a graph: the Moon and Moser 1965 result.


Are joins/pullbacks of bloom filters possible? An interesting advantage of bloom filters over hash tables, that they share with bitarrays, is that they support taking unions & intersections of sets by simply doing bitwise or & bitwise and respectively. The union of two bloom filters is the same as the bloom filter generated by the union of the sets, while the intersection will at least always be greater than or equal to the bloom filter generated by the intersection of the sets.
This got me thinking, if I use bloom filters to represent tuples, is there a way to do it that allows for efficient projections, cartesian products, and joins, so that it could be used as a heuristic for constraint propagation?

Ok, so the short answer to this question seems to be a "yes, but it grows quickly in size". You can view the bloom filters for each tuple element as vectors of bits. In that case, their tensor product will be a "bloom filter" for the cartesian product, where projection can be done by taking partial traces.
The downside of this is that the number of bits grows exponentially with the size of the tuple. You can mitigate this by maintaining a list of bloom filters for all pairs of tuple elements instead, which is still useful for constraint propagation, and gives projection as the intersection of the projection of each pair filter.


How can we reduce variables when converting from 3-SAT to 4-SAT? If we suppose that we'd like to convert an instance of 3-SAT to an instance of 4-SAT, by how much can we reduce the amount of variables?

CONVERSION METHODS FOR PRODUCTS OF SUMS

If we are given a 3-SAT clause $(A \lor B \lor C)$, we can readily convert this to 4-SAT by rewriting it as $(A \lor B \lor C \lor x) \land (A \lor B \lor C \lor \overline{x})$, where $x$ is a free variable.  In other words, $x$ can be any one of the existing variables, or a completely new variable.  This entails that we can gaurantee that 3-SAT can be converted to 4-SAT without adding any new variables.

Additionally, we can convert 3-SAT into 4-SAT and eliminate one variable, given a special set of clauses.  The 3-SAT clauses

$$(x \lor B \lor D) \land (\overline{A} \lor \overline{C} \lor x) \land (A \lor C \lor \overline{x}) \land (A \lor \overline{C} \lor x) \land (\overline{A} \lor C \lor x)$$

readily "reduce" to $(A \lor B \lor C \lor D)$.  This eliminates the free variable $x$, assuming it only appears in these clauses, and also greatly reduces the number of clauses.  The significance of this is that we may be able to eliminate some variables using this technique.

THE MAIN QUESTION

What are some other techniques for reducing the number of variables when converting from 3-SAT to 4-SAT?

Note that converting from product-of-sums to sum-of-products form may also be useful.

The paper Effective Preprocessing in SAT through Variable and Clause Elimination covers the variable elimination techniques used in Minisat.  Broadly, variables can be eliminated by

Substitution, in which a variable to be removed is defined in terms of other variables in the formula and the definition is substituted everywhere in place of the variable.  Automatic Extraction of Functional Dependencies describes how to efficiently find (some of) these variable definitions.
Distribution, in which all clauses containing a negated literal of $x$ are resolved against all clauses containing a positive literal of $x$.  The produced resolvents are kept (minus any tautological clauses) and the original clauses containing $x$ are discarded.  The resulting formula is satisfiable iff the original formula was satisfiable.

The overall goal of the techniques described in the Minisat paper is to optimize the formula for exploration by a CDCL solver by reducing the total number of clauses and strengthening (decreasing the length of) the clauses that remain.
 You could of course (with exponential effort) eliminate all the variables, eliminating all the clauses as well if the formula was satifiable or leaving one or more empty clauses if formula was unsatisfiable.


Run time of product of polynomially bounded numbers Let $M$ denote a set of $n$ positive integers, each less than $n^c$.

What is the runtime of computing $\prod_{m \in M} m$ with a deterministic Turing machine?

Computing the product sequentially, we need to perform $n-1$ multiplications of numbers of size $O(C^n n^{cn})$, for some constant $C$ corresponding to the constant in $O(n^c)$. Using algorithms for fast integer multiplication, each of these requires $\tilde{O}(C\log n + cn \log n) = \tilde{O}_c(n)$, so in total the time is $\tilde{O}_c(n^2)$ (the $\tilde{O}$ hides logarithmic factors).


Time cost of thread creation While creating an algorithm, the following question came up:

  In uniform cost, what is the time cost of a process that creates a thread?

Is there a difference between creating a thread in a thread pool vs creating a thread in runtime?

I know these questions should be self-explanatory, but I cannot seem to find an answer.

Every model of computation has a supported list of instructions, each associated with its time complexity. Thread handling is not a basic instruction in any model I'm aware of, but probably for practitioners of parallel computation, it is. The time complexity really depends on your viewpoint. If you're interested in optimizing the inner working of the operating system, then thread creation is not a basic operation at all, and its cost is associated with the algorithms implementing it. If you're interested in parallel computation, then probably thread creation is a primitive operation of unit cost. It all depends on the context.


Incremental strongly connected components For a changing directed graph, I would like to maintain information about strongly connected components. The graph operations are incremental: only vertex addition and edge addition. What data structures achieve the best known amortized complexity for these operations?

If the graph was undirected, the answer would be the union-find structure. And as undirected graphs can be seen as special cases of directed graphs, the (ever so slightly) superconstant lower bound carries over.

For a linear upper bound, the strongly connected components can be computed from scratch after each edge addition, without recycling any data at all. I wonder if there is any way to do better.

In the setting where I need this, I somehow expect non-trivial SCCs to be the exception rather than the rule. And in the absense of cycles I can achieve linear time in total (that is amortized constant time per operation). [EDIT:] Let me clarify what I mean. Of course, in the absense of cycles I do not need to keep track of SCCs at all. The amortized constant time is for what I do in my setting besides worrying abouts SCCs.

So I would also be interested in data structures that are, in general, not better than the above upper bound but use amortized constant time per operation as long as the graph remains a DAG.

To the best of my knowledge, the best algorithm for decremental strongly connected components is presented in [1] with $O(m \sqrt{n} \log n)$ total expected update time.

  [1] Decremental Single-Source Reachability and Strongly Connected
  Components in Õ(m√n) Total Update Time - Shiri Chechik, Thomas Dueholm  Hansen, Giuseppe F. Italiano, Jakub Łącki, Nikos Parotsidis -  https://ieeexplore.ieee.org/document/7782945 - FOCS 2016

Update: The new best Algorithm for decremental SCCs is $O(m (\log n)^4)$ presented in [5]

  [5] Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time
   - Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen -https://arxiv.org/abs/1901.03615 - accepted at STOC 2019

The best algorithm for incremental strongly connected components is presented in [2] with $O(m^{1/2})$ update time per edge.

  [2] Incremental Cycle Detection, Topological Ordering, and Strong
  Component Maintenance - Bernhard Haeupler, Telikepalli Kavitha, Rogers
  Mathew, Siddhartha Sen, Robert Endre Tarjan -https://arxiv.org/abs/1105.2397 - 2012 ACM Trans. Algorithms

It is an open question if those two problems can be solved faster.

For fully dynamic strongly connected components conditional lower bounds are known. Worst-case lower bounds are also known for decremental/incremental strongly connected component maintenance. For details look in [3] and [4].

  [3] Unifying and Strengthening Hardness for Dynamic Problems via the
  Online Matrix-Vector Multiplication Conjecture - Monika Henzinger,
  Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak -  https://arxiv.org/pdf/1511.06773.pdf - STOC 2015

  [4] Popular conjectures imply strong lower bounds for dynamic problems
  - Amir Abboud, Virginia Vassilevska Williams - https://arxiv.org/pdf/1402.0054.pdf - FOCS 2014

All of these results hold for general graphs. Better results are known for planar graphs.

The result you mention about DAGs is well known:

  Amortized efficiency of a path retrieval data structure - G. F. Italiano - https://www.sciencedirect.com/science/article/pii/0304397586900988 - TCS 1986


Find maximum distance between elements given constraints on some I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements:

The element 1 is in position 1, and element N must be at a position >= the position of element N-1. (i.e. element 2 could be at position 1, element 3 at position 7, and element 4 at position 8 (but not position 5))
Some elements must be within a certain distance from each other on the line.
Some elements must be at least a certain distance from other on the line.

My objective is to return an integer that represents the maximum span between element 1 and element N. If no lineup is possible, return -1, and if the elements can be any distance apart, return -2.

I am given:

The number of elements
A withinArray[][] where withinArray[x][y] = the distance elements x and y must be within on the line. Any zero values represent no constraints.
An atLeastArray[][] where atLeastArray[x][y] = the distance elements x and y must be apart on the line. Any zero values represent no constraints.

An example input would be: 4 elements, withinArray1[3] = 10, withinArray[2][4] = 20, and atLeastArray[2][3] = 3. (all other array values are zero).

The return value for this input would be 27. (element 1 at position 1, element 2 at position 8, element 3 at position 11, and element 4 at position 28)

The problem was first posted here by someone else. I'd like to figure out an elegant solution to it programmatically. Though I've been working on it for a whole day, I still have no luck coming up with a good solution. I feel that I need to use dynamic programming techniques, but have a hard time finding a good substructure.

I am not able to locate the same example on the web. Any pointer to such materials online would be appreciated. It's even better if you are an expert for such kind of question and can outline the solution in detail. Executable code is a plus.

What you describe is a linear program. You can use the following formulation:

Let $x_i$ be the $i$th element. The variables are $d_1,\ldots, d_{n-1}$, where $d_i$ denotes difference between $x_{i+1}$ and $x_i$. You require $d_i\ge 0$.

If two elements $x_i,x_j$ should be at least within some distance $\ell^-_{ij}$, then you set
$$ d_i+d_{i+1}+\cdots +d_{j-1} \le \ell^-_{ij}.$$
If they should be at least $\ell^+_{ij}$ away from each other you set
$$ d_i+d_{i+1}+\cdots +d_{j-1}  \ge \ell^+_{ij}.$$
Then maximize the objective function $\sum_{i=1}^{n-1} d_i$. An LP solver can also tell you if the problem is infeasible or unbounded. Of course you could look for a faster solution for this special class of LPs.


Does the Kolmogorov complexity of a program $p$ generating a string $x$ equal the complexity of $x$ up to constant? If $U$ is a universal prefix Turing machine, $U(p)=x$ for some program $p$ and string $x$, is it true that $K(x)=K(p)+O(1)$, with $K$ being the prefix Kolmogorov complexity?

I guess, I have found the answer myself: no.

Let $q$ be a shortest program that generates $x$: $K(x)=l(q)$. It is enough to concatenate any incompressible string $s$ not sharing information with $q$ and setting $p=\bar{q}s$. Let $m$ be the number of a Turing machine $T_m$ in the standard enumeration, that takes $p$, executes $q$ and discards $s$. Then, $U(\langle m,p\rangle)=T_m(p)=x$.
However, $K(p)\ge l(q)+l(s)+O(1)>l(q)=K(x)$. We thus have constructed a $p$ that contradicts the claim.


"Functorial" reductions? If I understand correctly, $\mathsf{NC}^0$ reductions are taken as the formalization of the concept of "local" reduction, i.e., a reduction that acts locally on substructures of the instances of the problem to be reduced: they map fixed-size "gadgets" of the source problem to fixed-size structures of the target problem.  It is my (hopefully correct) understanding that this kind of reductions occur ubiquitously in structural complexity theory.

An example: to reduce CIRCUIT VALUE to MONOTONE CIRCUIT VALUE (or MCV), one applies the following local transformations, which "double" every gate and every input (see e.g. Cook and Nguyen's Logical Foundations of Proof Complexity, proof of Theorem VIII.1.7, or slide 6 of this):
$$
\begin{align*}
a &\mapsto (a_+,a_-) \\
0 &\mapsto (0,1) \\
1 &\mapsto (1,0) \\
\lor(a,b) &\mapsto (\lor(a_+,b_+),\land(a_-,b_-)) \\
\land(a,b) &\mapsto (\land(a_+,b_+),\lor(a_-,b_-)) \\
\lnot(a) &\mapsto (\land(a_-,a_-),\land(a_+,a_+))
\end{align*}
$$
After applying this transformation, we obtain a monotone circuit with $2$ outputs, call them $o_+$ and $o_-$, such that the value of the output $o_+$ is exactly the value of the original circuit ($o_-$ is its negation). To obtain an instance of MCV (a circuit with only one output), one simply projects on $o_+$, which means plugging a constant (i.e., independent of the original circuit) $2$-input, $1$-output circuit to the outputs of the circuit obtained above.

The whole operation is obviously in $\mathsf{NC}^0$, because bounded-depth circuits can not only implement the local transformation above (taking gadgets to substructures) but can also add arbitrary "constant" substructures (in this case, circuits), where "constant" means depending only on the size of the source instance.

I am interested in reductions which are, so to speak, "purely functorial", in the sense that they map gadgets to substructures but are not allowed to add any "constant".  In the above example, the first part of the reduction would be functorial, whereas projecting on the $o_+$ output breaks functoriality.  My question is:

  Have "functorial" reductions ever been considered and, if so, under what name and for what purpose?

(The term "functorial" comes from the identity $F(f\circ g)=F(f)\circ F(g)$ which is at the basis of the definition of functor. If one sees problem instances as freely built out of basic gadgets, then functoriality means exactly "gadget to substructure". One could also say "homomorphic". Another analogy may be made with linear algebra: functorial reductions would be linear maps wheras $\mathsf{NC}^0$ reductions are affine maps).

I am pretty sure that "functorial" reductions are too restrictive to be of general interest.  For instance, I do not see how CIRCUIT VALUE could be $\mathsf P$-complete under such reductions. However, the variant of CIRCUIT VALUE in which one asks for the value of a specified output out of possibly many, would still be $\mathsf P$-complete (this "multi-output" variant is of course equivalent to CIRCUIT VALUE under $\mathsf{NC}^0$-reductions), as well as the similar variant of MCV.  So the notion is not completely void of significance.  Also note that "functorial" reductions are incomparable w.r.t. projections: they are more general in one sense (the local dependence is not necessarily "bitwise") but more restrictive in another (projections are still allowed to add arbitrary substructures, i.e., break functoriality).

You might be interested in the Universal Algebra point of view of Constraint Satisfaction Problems; see for example this survey by Libor Barto. One classical result in this area is Schaefer's dichotomy theorem.


Reccurence $T(n) = \sqrt{n}T(\sqrt{n})+n$ Note: this is from JeffE's Algorithms notes on Recurrences, page 5.

(1). So we define the recurrence $T(n) = \sqrt{n}T(\sqrt{n})+n$ without any base case. Now I understand that for most recurrences, since we're looking for asymptotic bounds, the base case wouldn't matter. But in this case, I don't even see where we could define the base case. Is there any number we are guaranteed to hit as we keep taking square roots starting from any integer Do we just define $T(n) = a$ for $n<b$, for some reals $a$, $b$?

(2). On page 7, Erickson gets that the number of layers in the recursion tree L will satisfy $n^{{2}^{-L}} = 2$. Where is this coming from? I have no idea. I see that the number of leaves in the tree should sum to $\sqrt(n)\sqrt(n) = n$, but I have no idea where to go from there.

Any help is appreciated!

Notes I'm looking at: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

You should really be asking a third question: what happens if $n$ isn't a perfect square. The answer to this question is that the actual recurrence should have $T(\lfloor \sqrt{n} \rfloor)$ or $T(\lceil \sqrt{n} \rceil)$ instead of $T(\sqrt{n})$, though in the analysis we will only consider inputs which are "recursive" squares.

Regarding your first question, there can be more than one base case. For example, perhaps $T(n) = 1$ for all $n \leq 100$. You are guaranteed to eventually hit this base case. In this case, as in most cases, the exact form of the base case doesn't affect the big Theta asymptotics (but it does affect the hidden constant).

Finally, regarding your second question, suppose that your base case specifies $T(n)$ for $n \leq C$. The recursion tree (which is a particular interpretation of some features of the recurrence) has the following form:

The root is one instance of size $n$.
The root has $\sqrt{n}$ children which are instances of size $\sqrt{n}$.
Each node at depth 1 has $\sqrt{\sqrt{n}} = n^{1/4}$ children which are instances of size $\sqrt{\sqrt{n}} = n^{1/8}$.
More generally, a node at depth $d$ is an instance of size $n^{1/2^d}$. You can prove this by induction by checking the case $d = 0$ (where $n^{1/2^d} = n$) and calculating $\sqrt{n^{1/2^d}} = n^{1/2^{d+1}}$.

The recursion terminates when the instance has size at most $C$, and this happens when $n^{1/2^d} \leq C$. At the point that this happens, we have $n^{1/2^{d-1}} > C$ (assuming $n > C$), and so $\sqrt{C} < n^{1/2^d} \leq C$. Taking the logarithm, $\frac{1}{2} \log C < \frac{\log n}{2^d} < \log C$ and so $\frac{\log n}{2^d} = \Theta(1)$, implying $2^d = \Theta(\log n)$. We can conclude that $d \approx \log\log n$. This is the number of layers in the tree. Jeff uses $C = 2$, which is how he gets his particular formula.


Is the following figure DAG? I have been through multiple definitions of DAG and all of them say that it is a directed graph without cycles. Also, it is said that it has topological ordering.

Now the following figure is directed graph and does not have cycles.

But looking at the ordering of edges (look at edge (2,1)), it is not topologically ordered.

Is this still a DAG or every edge must be topologically ordered for this graph to be a DAG??

The acronym DAG stands for directed acyclic graph. In other words, a DAG is a (finite) digraph without directed cycles. A digraph is a DAG if and only if it has a topological ordering.

In your example you have a labeled DAG. The labels do not constitute a topological ordering of the DAG, but the underlying digraph is still a DAG.


How do real numbers like Pi, golden ratio, etc fit into type theory In type theory, all computable functions must terminate, however, numbers like Pi are non-terminating real numbers, hence a non-terminating function is required to compute this number, even though one would never compute the full sequence.
How does type theory view/deal with such non-terminating numbers/object?

If by "non-terminating real number" you mean to say that the digit expansion of the number is an infinite sequence, then that is not saying much, because every real number is "non-terminating" in this sense, even the real number 42, for its digit expansion is
$$41.999999999999999999999999999999....$$
In any case, nobody suggests that the digits must somehow be computed all at once, although that is a common misconception that arises in the study of computability of reals. We just need a method which computes any digit we desire – but we never desire all the digits at once.
A sequence of digits is a function $f : \mathbb{N} \to \mathbb{N}$, and such functions can be perfectly managed by type theory. In fact, the correct way to represent a real number by a sequence is to use positive and negative digits, or else you can't compute certain operations (such as $+$). So in reality, in type theory or in any other setting a real number may be represented by a sequence of digits $f : \mathbb{N} \to \{-9, -8, \ldots, 8, 9\}$. Even better but equivalent is the representation by which a real number is represented by a map $g : \mathbb{N} \to \mathbb{Q}$ satisfying the condition $\forall m, n \in \mathbb{N} \,.\, |g(m) - g(n)| < 2^{-\min(m,n)-1}$. Such a map represents the number $\lim_n g(n)$.
All of the above can be stated in type theory:
$$
\Sigma (g : \mathbb{N} \to \mathbb{Q}) \,
\Pi (m, n : \mathbb{N}) \;
\mathrm{Id}_\mathbb{Q}(1, \max(|g(m) - g(n)| \cdot 2^{1 + \min(m, n)}, 1))
$$
The inner $\mathrm{Id}$-type says
$$\max(|g(m) - g(n)| \cdot 2^{1 + \min(m, n)}, 1) = 1$$
which is just a fancy way of stating
$$|g(m) - g(n)| \cdot 2^{1 + \min(m, n)} \leq 1.$$


Go from source to destination in 2d matrix with min steps collecting all candies. How to do it? If we have a 2d matrix of max dimension, 95x95 and we have at max 12 candies placed in some cells. We always start from top left corner(0,0) and we need to reach some given destination (x,y) after having collected ALL the candies. There are some cells which are blocked and hence cannot be visited.
Let 10 represent empty cell, 11 represent blocked cell and 12 represent candy. So, for the given 3x3 matrix:

10 10 11
11 12 10
11 12 11

with destination: (1, 2) (0-indexed), the min. no. of moves required to go from (0,0) to (1,2) is 5. i.e (0,0)->(0,1)->(1,1)->(2,1)->(1,1)->(1,2).

How to solve this question? Since BFS, DFS, etc all avoid re-visiting visited nodes, I am unable to use them. Same goes with backtracking.

The fact that the total number of candies is at maximum 12 is an important constraint.

Let the candies and start and end points (total <=14 points) be key points in the grid. Now use BFS from each of the key points to find the distances between the key points, and form a new graph with only the key points. Since the number of nodes in the new graph is so small, we can use Travelling Salesman on this new graph to solve the problem.

(Note: You will need to slightly modify Travelling Salesman to work for this specific problem.)


Time complexity of base conversion Why can't arbitrary base conversion be  as fast as converting from base $b$ to base $b^k$ ?

Seems to be a big time complexity difference! I am also interested in reading material about it.

Old. Original detailed question

Conversion between power-2-radix can be done faster than between non-power-of-2 radix, they can be even done in parallel, as every digit (or some groups of them) can be decoded independently of the rest.

For example the binary number 00101001 can be converted to hexadecimal 0x29 nibble by nibble (0010 and 1001), and vice versa (i.e. every hex-digit can be parsed to 4 bits independently of the rest), but doing that conversion from decimal (or any other non-power-of-2 radix) to binary, it's not so easy because digits affects each other!.

I've seen time complexity of maths operations in wikipedia, and there is also a related question in stackoverflow saying time complexity of conversions of arbitrary digit length to be $\mathcal{O}(M(n) log(n))$

I'm not interested in a "general time complexity bounds for any base conversion" but I would like to know more about these big differences in time complexity between "power-of-2 conversions" vs "any other base conversions".

I think there is a general fact about conversions that can be done faster if they are done between numbers where its bases are power among themselves, not only for 2, but the same to a base 10 to base 100.

Is there any known proof or materials around this ?

Conversion from base $b^k$ to base $b^l$ can be done by reading the original number in chunks of length $\mathrm{lcm}(k,l)/k$, and converting each such chunk into $\mathrm{lcm}(l,k)/l$ digits in the new base. For fixed $b,k,l$, this is linear time.

There is a non-trivial algorithm for base conversion in time $O(M(n)\log n)$, where $M(n)$ is the time it takes to multiply two $n$-bit numbers, $n$ is the length of the number (in digits), and the two bases are fixed. See for example page 14 of these notes by Brent.

The question you are asking is, for fixed $b_1,b_2$ which cannot be written in the form $b^k,b^l$, whether there exists a linear time algorithm for converting from base $b_1$ to base $b_2$. One possible approach to show that this is impossible might be by reducing multiplication (or any other equivalent operation, such as division) to base conversion for some fixed constant bases -- but it's not clear if it is in fact possible to build such a reduction or not. I don't believe the question has been asked in the literature.


Unambiguous grammars with different right and left hand derivations I read recently that for an unambiguous grammar the left hand derivation need not necessarily be equal to the right hand derivation. Can someone give an example of this?

Consider the following simple grammar:
$$
S\to AB \\
A\to a \\
B\to b
$$
Here is a leftmost derivation of $ab$:
$$
S\to AB \to aB \to ab
$$
Here is a rightmost derivation of $ab$:
$$
S \to AB \to Ab \to ab
$$
You can see that they look different. However, they correspond to the same parse tree:

More generally, each leftmost derivation corresponds to a parse tree, and this correspondence is a bijection; and the same holds for rightmost derivations. Therefore each leftmost derivation has a corresponding rightmost derivation, sharing the same parse tree.


Why can't CPU access secondary memory I have read in my subject "Operating Systems" that CPU can't access secondary memory. Any program that is stored on secondary memory is executed once its retrieved from secondary memory to primary memory. Is this true?  If the CPU can't execute code directly out of secondary memory, why not?

There are CPUs that can execute programs directly from secondary memory. (I'm kind of surprised at you not being able to simply search this: e.g.http://www.analog.com/media/en/technical-documentation/application-notes/EE363v01.pdf)

That being said, many CPUs cannot. It generally boils down to access speeds and/or I/O type. Secondary storage (flash, etc) can be slower and/or have more latency than RAM, and for a simple CPU (i.e. embedded system or similar, generally) the CPU may not be able to wait the length of time necessary to do an instruction fetch. (Or rather, it may assume that an instruction fetch will complete in  cycles as opposed to having a mechanism to wait until the instruction is actually fetched)

Also, unless you have memory-mapped I/O or a proper MMU you'll need explicit support by the CPU to issue the I/O instructions required, which increases the complexity of the CPU and may increase the critical path, limiting the speed of the CPU. (If you have a MMU you can just have a page fault handler that fetches the appropriate page from secondary memory on first access)

An elaboration:

Ultimately, a CPU has to be able to read the data for its next instruction. This is generally only a few bytes at most. However, many devices only support block-level access (e.g. 512 bytes, etc) of larger block sizes than the instruction size. Note that this includes many forms of RAM! (For instance, if you have DDR ram (64 bits transferred at a time) and an instruction set that isn't always 64 bits wide) There are a couple of ways to deal with this mismatch: you can fetch the block and toss away the data you don't need for that instruction, you can fetch the block into a small sliding window of the next few instructions (throwing away the rest of the block) so you only need to do a fetch every few instructions, or you can fetch the entire block into a buffer. Fetching every instruction is slow, and in particular is latency-sensitive. It also wastes memory bandwidth that could be otherwise used for DMA, for instance. Fetching into a sliding window can faster, but substantially more complex. It also introduces latency variations (if you have unpredictable branches you may not be able to keep the window filled, for instance) And fetching the entire thing limits you and requires a lot of die space for the buffer (you need to have a buffer at least as large as the block size), and is prone to problems (e.g. what happens when an instruction overlaps two blocks? There are a lot of edge cases.)


Decidability of the language that accepts a universal turing machine Is the language $L_{universal} = \{ \left \langle M \right \rangle | M \textrm{is a universal turing machine} \}$ decidable?

I'm guessing it is decidable according to the definition of a UTM, that a UTM must be able to calculate every recursive function. Since the set of recursive languages and the set of all input words are both enumerable, we are theoretically able to determine if the given $\left \langle M \right \rangle$ is a UTM. Is my logic somewhat correct?

If $L_{u}$ would be decidable,  $L_u^\complement$ would be decidable too (the complement of a recursive language is recursive too) , but if you can build a TM that accepts $L_u^\complement$ you can build a TM that accepts $L_d=\{w \mid w_i \notin L(M_i)\} $ that is not RE.

In fact if $w \in L_d  \implies (w,w)\notin L_u \implies (w,w) \in L_u^\complement$.

So with a reduction from $L_d$ to $L_u$ it can be shown that $L_u$ is not decidable.


Asymptotic relationship of logarithms in different bases I'm reading through the Khan Academy course on algorithms. I'm taking a quiz and finally got the right answer (all 3 of the options are true).

  For the functions $\lg n$ and $\log_8 n$, what is the asymptotic relationship between these functions.  Select all that apply.

  [  ] $\lg n$ is $O(\log_8 n)$
  [  ] $\lg n$ is $\Omega(\log_8 n)$
  [  ] $\lg n$ is $\Theta(\log_8 n)$

Why is this the case? I thought that the answer would be only the first one:  $\log_2 n$ would be the upper bound of $\log_8 n$. Can someone explain this to a noob?

We'll show two results. The first is that for any positive constant $k$, we'll have
$$
k\cdot f(n) = O(f(n))
$$
To see this, recall what it means for $g(n)=O(f(n))$: this is true when we can find two constants $c>0, N\ge 0$ such that $g(n)\le c\cdot f(n)$ for all $n\ge N$. If we choose $g(n)$ to be $k\cdot f(n)$ then we have just what we need: we'll just use $k$ for our constant $c$ and select any $N$ we want. It's trivial to adapt this argument to big-$\Omega$, and so it also holds for big-$\Theta$ as well.

In simple terms: Asymptotic notation ignores constant multiples.

The second result we need is that logs to different bases are always going to be constant multiples of each other, namely
$$
\log_ax=(\log_ab)\log_bx
$$
This is easy to see: just raise $a$ to each side power and you'll wind up with equal results.

In the problem stated, assuming that $\lg n$ is $\log_2n$, we'll have
$$
\lg n=(\log_2 8)\log_8n=3\log_8n
$$
and the two logs will differ only by a multiple of 3, which as we showed above, means that $\lg n$ and $\log_8n$ are the same function, as far as big-whatever notation is concerned.


How to design an algorithm to generate balanced teams? I am trying to design an algorithm that allows to create balanced teams for a summer camp. There are about a 100 campers of different ages. Gender ratio isn't necessarily 50/50. Also there are a different number of campers for each age group.
The idea is to create fair and well-balanced teams while having approximately the same amount of boys and girls in each team as well as the same number of kids in each age group per team.
The usual approach is to make a list and manually make the teams (prior to the camp), but this is stupid and has a lot of balancing issues.

My idea is to create an algorithm based on some kind of score (eg. time to run an obstacle course) simple enough to be programmed in excel or some other tool everybody knows how to use. My first idea of how it could look like is:

Separating boys and girls into different categories
Ordering them from fast to slow (this should still make it so that the oldest kids are roughly at the top of the list and the slowest at the bottom)
Design algorithm that creates teams with the same averages while taking kids from all over the list. This is the part I'm having trouble with because I don't want to use iterative methods.
Once I have the boys teams and girl teams ready mix them together so that

4.1 Each group has the same amount of kids (number of boys + number of girls)

4.2 The average time of each team should be as close as possible (here are iterative methods ok because there are less combinations)

If anyone has experience, ideas or has seen something similar I'd gladly read it.

There's probably a tradeoff between ease of implementation and the quality of the solution.  I'll list a few possible approaches.  The first step is to pick a way to measure the quality (imbalance/unfairness) of a proposed solution.  One possibility would be the variance of the team averages; another would be the gap between the largest team average and the smallest team average.  Then, pick one of the following methods to choose an assignment that is as good as possible, under this quality measure:

Random. The simplest to implement method is random assignment.  Randomly assign each kid to a team (subject to the requirement that each team has the same number of boys and same number of girls).  Measure the quality of each assignment.  Do this for 1000 random assignments.  Pick the best one.  That's very easy to implement.
Here is a simple way to do the random assignment: randomly re-order the list of kids, and put the first $k$ into the first team, the next $k$ into the second team, and so on, where $k$ is the desired team size.  To also ensure gender equality, do this separately for the boys and girls.

A greedy heuristic. A different approach is to assign the kids to teams in a heuristic way.  Sort the kids from slowest to fasteast.  Now iterate over the kids in this order and, for each kid, assign that kid to a team.  Assign the kid to the fastest team (measured by their average speed given the current assignment).  If some teams currently have fewer members than others, only choose among the teams with the fewest members.  To ensure gender equality, when a boy picks a team, have them only pick among the teams with the fewest number of boys; and symmetrically for girls.  There are other heuristics you could consider, but this seems like it might yield good results.

Random + heuristic. You can combine the first two ideas.  First, randomly pick a fraction of the kids, and then randomly assign them to teams.  Second, assign the rest of the kids via the above heuristic.  You can repeat 1000 times and take the best assignment seen so far.
It will probably help to ensure that the initial random assignment assigns the same number of boys and girls to each team.

Simulated annealing. A more sophisticated method is to start with a random assignment and use simulated annealing to improve it.  In each step, you randomly pick a pair of kids of the same gender but from different teams, and you consider what would happen if you swapped them.  Depending on how this affects the quality of the solution, you decide whether to make the swap or not, in a particular way.  Simulated annealing might improve on the other methods, but it is also a little fiddly, as there are parameters you have to tune to get it to work to best effect.

Integer linear programming. If you're willing to measure quality by the difference between the largest team average and the smallest team average, a more sophisticated method still is to use integer linear programming.  You have a zero-or-one integer variable $x_{i,j}$ indicating that the $i$th kid is assigned to the $j$th team, and then you can write down linear inequalities that capture the requirements on a solution to be valid.  This can potentially give you the optimal solution.

I suspect the latter two approaches are more complicated than is really necessary and just trying a bunch of random assignments might be good enough.
In general, your problem is NP-hard; it is as hard as bin-packing.  If you cared enough you could investigate the heuristics and approximations for bin-packing and try seeing if you can adapt them to your problem.  I don't know that that will be worth the effort.


Recusively Enumerable or Recursive dependent on whether P=NP If a language is defined such that
$L = (0+1)^{\ast}$   if $\mathsf{P} = \mathsf{NP}$ and $\emptyset$   otherwise

Then $L$ is a regular language if $\mathsf{P} = \mathsf{NP}$, otherwise it is the empty langauge.
Therefore $\mathsf{P} = \mathsf{NP}$ , $L$ is recursive (being regular), but is $L$ still recursive if $\mathsf{P} \neq \mathsf{NP}$?

The language $L = \emptyset$  is indeed a recursive set.


What category does questions like "Given n points on 2D plane find ..." belong to Not after a specific answer, do following questions belong to same set of problem types?

Given n points in on 2D plane, find 4 or 5 , or m subset of points with less total distant to each other than all other points.

Or

Given n points in on 2D plane, count the number of triangles, squares etc. that they form.

Or

Given n points in on 2D plane, find a point that is closeses to most number of points as possible.

are these optimisation questions? or is there another name for above type of questions, or there can be no category for all the questions of type

Given n points in on 2D plane, find $\cdots$

This question did not seem to be fit for SO or Software engineering, so I am asking it here, if there is better SE to ask this question I'll delete this question and ask it there ( in reverse order ).

Combinatorial geometry.

http://mathworld.wolfram.com/CombinatorialGeometry.html

Computational geometry.

https://en.m.wikipedia.org/wiki/Computational_geometry


Is impredicative Set consistent with the excluded middle? While studying Coq, I found a few references that impredicative Set might not work well with classical axioms, in particular the axiom of choice.

I'm working on a dependent type system based on the calculus of constructions (with Prop and Set), on which I intend to add Peirce's law on sets, as in the computability side it represents call/cc (capturing/resuming the whole computation).

My question is: is the calculus of constructions* with an impredicative Set, with the excluded middle working on sets (precisely, forall P: Set, ((P -> False) -> P) -> P being of type Set), without the axiom of choice, consistent? I didn't manage to find a reference for that.

(* Would inductive types make any difference, from CoC to CIC?)

I'm not an expert, but my understating was not that it it was inconsistent, but that it implies proof irrelevance. That is, if $s,t:T$ then $s=t$.

This gives many undesirable properties, like having $1=2$, but I'm not sure it actually implies bottom.
This answer had similar details.


Monotonic queues recurrence relation I'm looking at the following explanation of monotonic queues and their applications in problem solving.

Monotonic Queue Summary

I have a reasonable understanding of this data structure and the problems described in the post. However, i'm struggling with the following "recurrence relation"

Any DP problem where A[i] = min(A[j:k]) + C where j < k <= i

I don't completely understand this formula. It looks like a recurrence relation but seems to to be in reference to the underlying array.
I can't seem to see if the previous array range
(j to k) is referring to a portion of the array or a portion of previously solved sub-problems.

I'm not sure what the base case is and it seems like the answer is the minimum value in this array range plus some constant. I don't see how this solves the problems above.

Am I looking for too much precision in this statement or am I missing something?

The following seems more intuitive

Any DP problem where DP[i] = smallest(prefix_sums[j:k]) where j < k <= i and prefix_sums[k] - prefix_sums[j] >= K

It is no wonder that you are confused.

One characteristic of DP problem is the recurrence relation that combines solutions to subproblems to a solution to larger subproblems. That article presents the following general "recurrence relation".

Any DP problem where A[i] = min(A[j:k]) + C where j < k <= i

However, because the same A appears on both sides of the equation, that "recurrence relation" cannot be specialized/instantiated as the recurrence relation of any problem listed in that article.

Instead of "DP problem", this kind of problem should better called "sliding window problem", or "SW problem".  Basically, a first-in-first-out queue sliding over the given array are used to track the useful entries. We could argue that "SW problem" is a special kind of "DP problem", where the overlapping subproblems are to fill those sliding windows.  Each sliding window will lead easily to a solution for the original problem at one end of a window. Or, if you prefer a visual identification  of the "DP problem" as "table-driven bottom-up memoization", an "SW problem" is supposed to be solved by tracking useful data in a table moving across the given array.

An "SW problem" does not have the usual form of recurrence relation,  as can be checked against all problems listed in that article. Instead of Any DP problem where A[i] = min(A[j:k]) + C where j < k <= i, it should have been something like Any problem to find M[i] where M[i] is defined as something like min(A[j:k]) where j < k <= i given array A.

This technique, "sliding window" is indeed very powerful and easy to use. Except the glaring lapses mentioned above, that article is pretty nice. I encourage you to read the full article, ignoring that summary statement or using my replacement above.


Algorithm to turn gray-scale text into legible binary black and white text I have an image with gray-scale anti-aliased text produced by Chromium and need to convert this into pure binary black and white text. Applying a simple binary threshold pass over the image causes artifacts, either missing edges or weird protrusions and text being too bold depending on the chosen threshold.

Below an example of the input, the perfect outcome (as this is how the text would be rendered without AA) and the current outcome based on binary threshold (I think this is a 0.6 threshold). Sadly, it's not possible to instruct Chromium to render the text without anti-aliasing, so a conversion is the only option.

I was wondering if there was an established algorithm for this kind of problem or in what direction I would have to look to find something that could be adapted to work here. Any algorithm would need to be able to run in semi-realtime, no offline solutions.

It is possible that the literature on image vectorization might be useful.  That basically tries to reconstruct the strokes that produced the image.  However, I think this is going to be challenging when the width of the strokes is narrower than two pixels or so, and it is possible that standard techniques might work poorly in that domain.  I would recommend that you try increasing the font size or the resolution, and then try standard methods.

For your example image, I get somewhat more reasonable results by using a better threshold (0.8), but I think you'll do a lot better if you can increase the resolution.

If you know in advance what font and font size will be used, it might be feasible to render each possible character and capture an image of the anti-aliased rendered result for each possible character, in a few random locations, and then use simple pattern matching.


Viewing images that compressed using lossless algorithms I am just trying to understand a few minor details regarding images that are compressed with lossless algorithms such as RLE.

If a bmp image is compressed using RLE, when does the decompression occur when viewing the image? does the image viewer have a built-in library to decompress the image and then view it? or is it using a system library? Is the decompressed image file stored in the RAM temporarily?

Do you any references for this process?

Image is decompressed before viewing for the most time.
It is not necessary to decompress it fully if this is very big image and you have preview of the top left cropped area - only needed rows could be decompressed up to visible part.
This is highly implementation dependent, some programs use system built-ins (Windows format BMP) some disregard this and use own (on other systems Windows BMP is not generally built-in).
It may be stored in RAM, on disk, translated to internal format. There is no reason to stick with one scheme.

There are no references as this is implementation specific.
But I can share with my own scheme: I always unpack compressed data, never depend on external libraries, store it on internal format and since I use it in image editor - I store in RAM last three operations used on images.
They can be huge (800k x 600k) so if that is the case I put only visible part to RAM.
Since BMP can come in up side down format and other compress techniques prevent me from mapping coordinates to file, I explicitly store them as small sized decompressed grid (something like Google Maps do).


Is the union of computable enumerable sets computably enumerable Let $\{A_n : n \in \mathbb{N}\}$ be a collection of c.e. (computably enumerable) sets. Is $\bigcup_n A_n$ c.e.?
That is, is the union of c.e. sets c.e.? Otherwise, under what conditions will this be true?

Every language can be written as a countable union of singletons $\{x\}$.
On the other hand, the union of finitely many c.e. languages is c.e.


Time complexity of Rabin-Karp algorithm $n$ : length of text T

  $m$ : length of pattern P

When I study Rabin-Karp algorithm, I learned the best case of this algorithm is $\theta(n-m+1)$. Because if a hashed number is too small to modulo by some other number.

But when I'm talking with my friends about this best complexity, I was very curios that does above theta notation can be represented by $\theta(n)$ if $n$ is asymptotic to infinity?

First time, it was reasonable to me that $\theta(n)=\theta(n-m+1)$ is correct because it is asymptotic notation. But if $m$ is always $n-1$, can we use $\theta(n)$ in this situation? I'm confusing about notation concept and what I'm curious is below question.

  What is the right time complexity notation of Rabin-Karp algorithm?

  $\theta(n)$ or $\theta(n-m+1)$?

The running time you quote isn't correct. If $n = m$ then it takes $\Omega(n)$ to verify that $T = P$. The best case running time of any string matching algorithm is $\Omega(m)$, since this is how long it takes to verify a match. Perhaps you are disregarding the time it takes to compute the hashes.

Ignoring all of this, let us suppose that we are considering an algorithm whose running time is $\Theta(n-m+1)$, where $m \leq n$ are two parameters. As your example makes clear, this is not the same as $\Theta(n)$, since if $m$ is close to $n$ then $n-m+1$ is much smaller than $n$. Generally speaking, an asymptotic expression depending on two parameters cannot be reduced to an asymptotic expression depending on only one of them.

In practice, often $m$ is itself a known function of $n$, and this can be used to reduce $\Theta(n-m+1)$ to an asymptotic expression depending on a single parameter. For example, if $m = n/2$ then $\Theta(n-m+1) = \Theta(n)$, whereas if $m = n$, then $\Theta(n-m+1) = \Theta(1)$.


Is there a logspace version of the reduction used in Cook-Levin? The proof (one of the standard ones, anyway) for Cook-Levin uses snapshots.
E.g., see Cook-Levin proof (end of page 2, early page 3)

Now, $z_i$ ( where $z_i$ describes a snapshot of the machine ) depends on $z_{i-1}$ and $z_{prev_{m}(i)}$, but to calculate $z_i$ we cannot erase index $i$, or we will forget what we are currently calculating. What happens if we are restricted to logspace? If we keep the recursive procedure, the stack may well take more than logspace since the variable i might become very large.

And a follow up is, if such log space reduction really exists, wouldn't that imply $P$ is in $L$?

To address your "follow-up", no.  The ability to use logspace reductions instead of polynomial time reductions to prove NP-completeness doesn't prove that P is contained in L.  It just proves that you don't need the full power of polynomial time reductions to define NP-completeness.  The situation is similar to saying, "Hey, there are lots of polynomial-time algorithms for graph reachability but I just found out that the problem is in logspace.  Does that mean that P$\,=\,$L?" except that now we're talking about a whole class of computations (the reductions) rather than just one problem.

In fact, if you check out books on descriptive complexity,1 you'll see that we can use even weaker notions of reduction (reductions definable by first-order formulas) and still define a meaningful and, as far as we know, equivalent notion of NP-completeness.  This is reassuring: it tells us that NP-completeness is a robust concept that doesn't seem to depend exactly on how you define it.

I say "doesn't seem to depend" because, as far as I'm aware, it is not known that defining NP-completeness in terms of polynomial time, logspace and first-order reductions makes exactly the same class of problems NP-complete.  But there are no problems known to be NP-complete under one of these kinds of reductions but not under one of the others.  (Stand by for this paragraph to be edited after people comment!)

1 E.g., Immerman, Descriptive Complexity (Springer, 1999) or Libkin Elements of Finite Model Theory (Springer, 2004).


Do all recursive problems have optimal substructure? I am reading about dynamic programming and I understand the overlapping subproblem requirement but not sure why optimal substructure is explicitly stated. Are there problems that can be solved recursively that do not have an optimal substructure?

I think there is some confusion in terminology here. Part of the problem is what we mean by problem and algorithm. But there is more to it:

Textbooks like CLRS introduce the notion of optimal substructure as a property of problems (and not algorithms directly). That's because an algorithm often transforms a problem statement into other problem/s and, as a result, an algorithm may establish a link between problem solutions with subproblem solutions. Indeed, CLRS defines optimal substructure as follows: "A problem exhibits optimal substructure if a solution to the problem contains solutions to its sub-problems". While it doesn't say this directly, the term "contains" implies through an algorithm.
Just because a problem (and actually all problems) may accept a recursive formulation or algorithm, it doesn't of course mean of course that every algorithm to solve it is indeed recursive (this is in relation to Yuval Filmus's answer). For a particular algorithm to be recursive, it must call itself recursively.
Similarly, just because an algorithm may involve some form of iteration or even recursion (e.g. in some of its subroutines), it doesn't mean that the algorithm is actually solving the original problem recursively.
Last but not least, just because an algorithm is recursive, it does not mean it solves a problem with optimal substructure where solutions to the original problem are the result of combining solutions to sub-problems of the same type. For example, if you write an algorithm to sort numbers, and this algorithm sorts the input and then once it's done sorting, it e.g. calls itself recursively with a NOP in each call for some depth of recursion, that does not mean that the algorithm is actually building the sorted sequence (the solution to the stated problem) from solutions to subproblems, and thus exploiting the optimal substructure of the problem.


How to modify semantic actions when removing left-recursion from a grammer Is there any algorithm that tells us how to modify semantic actions associated with a left-recursive grammar? For example, we have the following grammar, and its associated semantic actions:

$ S \rightarrow id = expr $  { S.s = expr.size }

S $\rightarrow$ if expr then $S_1$ else $S_2$ { $S_1.t = S.t + 2; $
$S_2.t = S.t + 2;$ $S.s = expr.size + S_1.size + S_2.size + 2;$ }

S $\rightarrow$ while expr do $S_1$ { $S_1.t = S.t + 4;$ $S.s = expr.size + S_1.s + 1;$ }

S $\rightarrow$ $S_1$ ; $S_2$  {$S_1.t = S_2.t = S.t;$ $S.s = S_1.s + S_2.s; $ }

Clearly the non-recursive version of the grammer is:

S $\rightarrow$ id = expr T

S $\rightarrow$ if expr then $S_1$ else $S_2$ T

S $\rightarrow$ while expr do $S_1$ T

T $\rightarrow$ ; $S_2$ T

T $\rightarrow$ $\epsilon$

But we also need to change the semantic actions accordingly. Any ideas how this can be done?

From what I have discovered, there is no general technique to modify the semantic actions while removing left-recursion. Instead, the best method is to take a representative example, draw its parse tree, and then checking which semantic actions give us the same result as the previous grammar.