Why does the category of language types have morphisms, not functors? I am probably not phrasing this question well, so please bear with me as I try to explain what I mean.

I am working on learning category theory, as applied to programming.  So far, I understand that:

Objects in a category are "unbroken"; you're not supposed to peer inside them to see their internal structure.
Any Set is a category
Programming language types can be thought of as sets.  (Bool is the set True, False; Int is the set of all integers; etc.)
Thus, all of the types in a language form a category of sets.
Morphisms are arrows between objects.
If those objects are themselves categories, then the morphisms get called functors.

Taken together, that would imply that a function from Int to Bool is a functor, because it's a map from the the set category Int to the set category Bool.

However, I have also read elsewhere (in particular https://www.johndcook.com/blog/2014/05/10/haskell-category-theory/), that thinking of it that way is wrong and we really shouldn't be talking about language types being a base category with "just" morphisms.  But I don't see how that fits with my previous logic.

I therefore must conclude that my previous logic is faulty, but I'm unclear how or why.  What is the right way to conceptualize this?  Are Sets just extra special exceptions?  Or is it really just an arbitrary matter of preference for how to view the problem space?  Or am I just flat out wrong somewhere?

There are several ideas floating around here. You can look at a programming language through a categorical lens, and then types are objects, and they are indeed opaque. So Bool is not a set of True and False in this picture. It's an object that has two morphisms (injections) going into it, one corresponding to True, and one to False. In Haskell these are the two constructors of Bool. They take no arguments, but that is interpreted as being morphisms from the terminal object (the unit type). It all works out nicely.

Then there is the more traditional picture where types are just sets of values and morphisms are functions between sets. Sets and functions form a category Set. That picture works nicely as long as you don't talk about partial function (ones that loop forever).

Then there is the third idea that every individual set is a category in itself. It's a discrete category, meaning there are no morphisms (other than identity) between elements. In that case, functions between sets would indeed correspond to functors between discrete categories. But a functor between discrete categories is nothing but a function on objects (elements) which is trivial on morphisms, so it's not a very interesting point of view.


Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time? This is a question posted for extra practice (i.e., not for credit):

  Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time? Explain.

I'm not sure how to approach it. I see lots of near-answers online using $O(\cdot)$, but $\Theta(\cdot)$ is a little different because it means there is both an upper and a lower bound of $n^2$ and $n \log(n)$, respectively.

So, at its absolute best case, a $n^2$ algorithm may run in $\frac{1}{a}n^2$ time, which for large $a$ may be very fast compared to most quadratic algorithms. However, since $a$ is constant, as $n \to \infty$, the time for even a $\frac{1}{a}n^2$ algorithm will far surpass a $bn\log(n)$ algorithm, even if $b$ is very large.

This would lead me to believe the answer is no, an algorithm that runs in $\Theta(n^2)$ cannot run faster than a $\Theta(n \log n)$ algorithm when analyzed asymptotically as I have done.

With this said, if the thing that makes the $\Theta(n \log n)$ algorithm $\Theta(n\log n)$ happens very frequently but the thing that makes the $\Theta(n^2)$ algorithm $\Theta(n^2)$ does not happen frequently at all (either due to the nature of the algorithm or optimized design), then the amortized complexity of the $\Theta(n^2)$ algorithm may in fact be less than that of the $\Theta(n \log n)$ algorithm — even if the asymptotic complexity says otherwise — right?

If the two complexities given were $O(\cdot)$ rather than $\Theta(\cdot)$ then I may be inclined to side with the latter argument. The presence of the lower bound that $\Theta(\cdot)$ implies is giving me second thoughts though. Can anyone help point me in the right direction here and clarify if it seems that I am misunderstanding the use of $\Theta(\cdot)$ for asymptotic versus amortized analysis.

Edit: I don't think this is a duplicate of Sorting functions by asymptotic growth. I am familiar with how to use limits, etc. to classify and sort algorithms asymptotically. Speaking strictly in terms of asymptotics, I think the answer to my question is definitely no. The question quoted (as worded) seems more general though; it wants to know if there is any way that a $\Theta(n^2)$ algorithm can out perform a $\Theta(n \log n)$ algorithm. Is such an occurrence possible when considering amortized analysis rather than asymptotic analysis and the algorithms are structured as described above? Or is this irrelevant and the answer is still no?

Asymptotically, you're right: for big-enough inputs, the $\Theta(n\log n)$ algorithm can be faster. However, this is only true for big enough $n$.  It might be that "big enough" means "far bigger than any actual computer can store" or even just "plenty bigger than any input I care about".

For a specific example of this, look at matrix multiplication algorithms.  For $n\times n$ matrices, the standard pencil-and-paper algorithm takes time $\Theta(n^3)$.  Strassen's algorithm essentially considers the matrix to be a matrix of smaller matrices and improves the running time to $O(n^{2.81})$ but the algorithm is more complicated, so the constants hidden by the big-$O$ mean that Strassen is only likely to be faster for about $n>100$.  Coppersmith–Winograd is $O(n^{2.37})$ but is even more complicated and, as far as I'm aware, isn't used in practice, because it only wins on matrices that are too big for people to want to multiply anyway.

Another aspect is that some algorithms might be better or worse than others on real computers.  If an algorithm's data access patterns play nicely with the cache, it can be thousands of times faster than code that sprays memory accesses all over the address space: algorithms based on hash tables are particularly bad at for that.  $n^2 < 1000n\log_2 n$ for all $n$ less than about $14\,000$.  Likewise, an algorithm with a simpler branching structure in the code might run faster because the CPU pipeline is full more of the time.


Why can we ignore the constant factor in Weis's proof of the Master Theorem In the 4th edition of his Data Structures textbook, Weis gives a proof of part of the Master Theorem.  This proof says "Let us ... ignore the constant factor in $\theta(N^k)$ ...  I don't understand why it ignoring that constant is valid.  (I know that the real Master Theorem is broader  than the version presented in the text.  I'm just having trouble understanding the argument presented in the text.)

Specifically, the relevant part of Theorem 10.6 on page 469 is

The solution to the equation $T(N) = aT(N/b) + \Theta(N^k)$ is $T(N) = O(N^{log_b} a)$ if $a > b^k$

The proof includes the phrase "ignore the constant factor in $\theta(N^k)$ ..." and then goes on to use a telescoping sum to get

$T(N) = T(b^m) = a^m \sum_{i=0}^m (\frac{b^k}{a})^i$

At this point, he argues that because $a > b^k$, then the sum is a geometric series with a ratio less than 1.  However, if we don't ignore the constant in the $\Theta$ expression, isn't there a constant inside the summation that would affect whether the geometric series converges?

Suppose that your function is always in the range $cN^k$ to $CN^k$. Consider the three recurrences
$$
s(N) = as(N/b) + cN^k, S(N) = aS(N/b) + CN^k, R(N) = aR(N/b) + N^k.
$$
For appropriate initial conditions, $s(N) \leq T(N) \leq S(N)$ will hold, as a straightforward proof by induction would show. On the other hand, for appropriate initial conditions, $s(N) = cR(N)$ and $S(N) = CR(N)$, as another straightforward induction shows. This explains Weis's remark.

What it happening here? As you unroll the recursion, you add various terms which are $\Theta(N^k)$, for various values of $N$. The contribution of the big Theta to the final sum is at most a constant factor. Instead of $a^m \sum_{i=0}^m (\frac{b^k}{a})^i$, you get $\Theta\bigl(a^m \sum_{i=0}^m (\frac{b^k}{a})^i\bigr)$. Crucially, the additional constant factor is global and doesn't accumulate throughout the recursion.

As an example, consider the generic recurrence $s(N) = 2s(N-1) + f(N)$, with base case $s(0) = 0$. The solution is $$ s(N) = f(N) + 2f(N-1) + 4f(N-2) + \cdots + 2^{N-1} f(1). $$ If we multiply $f(N)$ by a constant factor, the solution of this recurrence will be multiplied by the same constant factor, while the constant $2$ stays the same.


Sequence alignment with one to many characters I'm trying to align a sequence of characters together, I found that sequence alignment algorithms which use dynamic programming like Needleman-Wunsch or Smith–Waterman only align one character with one character beside allowing character substitution, deletion or insertion.

For example, if I have a set of similarly sounding characters, like

monir, monier, muneer, munir, mounir, mouneer

The alignment algorithm will produce the following output

m u n i - r
| | | |   |
m o n e e r

Is there a way to adapt these algorithms (or an alternative algorithm) to consider aligning/substituting character with more than one character in order to output something like

m u n i  r
| | | |  |
m o n ee r

Please note that, I'm using the standard java implementation for these algorithms and I don't have a predefined list of similarly sounding characters, so I'm trying to aligning the similar words together in order to extract these alignments.

If I understood your problem correctly, a trie data structure may help you. The main challenge would be after the first mismatch, match the upcomming characters. I'm not sure how I would hack it, but it may not be that hard.

Hope it helps. Regards


Converting REGEX to BNF grammar Say I have a bunch of regex expressions which are used as filtering rules. (Any special extraction capabilities are unnecessary here, the set of regular expressions I have is only used for filtering down sentences).

Can any pure regex be converted into BNF? (ABNF, EBNF, etc.)

Are there well known algorithms (or existing library implementations) that can perform the conversion?

The language I wish to convert from is actually not the standard language of regular expressions, but one that conditions on word taggings which are provided per word (part-of-speech tags that come along with the text). So it is a variant of regular expressions, which operates at the word level rather than the character level.

Thanks!

Conventional regular expressions as they are commonly found in literature describe exactly the regular languages. Given a regular expression, you can therefore find an equivalent automaton, then find the linear grammar equivalent to such automaton and put it in any form you prefer.

On the other hand, "regular" expressions as they are implemented by most programming languages are not equivalent to the set of regular languages; several implementations allow you to describe languages that aren't even context-free.


Is $G_2(V_2,E_2)$ a subgraph of $G_1(V_1,E_1)$ given number of vertices and adjacency matrix for both? Given $n_1$ and $n_2$ number of verteces and the adjacency matrix for both graphs, one should determine whether $G_2$ is a subgraph of $G_1$.

I am supposed to use C++ for this, and though I could probably come out with a solution including $20$ for functions, it's most likely not the best approach to the exercise.

Do I have to(?):

Assume the graphs have $n_2$ common vertices (because this has to be in order for $G_2$ to be a subgraph of $G_1$, right?)
Check to see if any of the $\begin{pmatrix}n_1\\ n_1-n_2\end{pmatrix}$ possibly resulting graphs after the removal of $n_1-n_2$ vertices from $G_1$ is equal to $G_2$

Althogh not sure how to compute the above.

This must be an easy exercise since it's for beginners in graphs, but I guess there's just something I am missing. Could you give me some hints on how to approach this in a better way? I've looked for this one a while, hopefully it's not a duplicate.

This problem is more general form of the graph isomorphism problem. No polynomial time algorithm is known solving it. The state of the art suggests possible approaches.


Cross platform apps and programing languages...how is it done? I always wondered how various certain languages like Java, HTML5 and browser extensions are made with cross platform(operates and functions the same, regardless of OS, being Linux/Windows/BSD not specifically CPU architecture)  compatibility in mind...

Is there a certain developmental process semantic or otherwise that one would have to follow, in order to create such?

Can some one give me the "nitty gritty" of how it's done , how  it works ... i.e. system calls(if any)

First word: consistent API across platforms - when programming on different platforms, the same API is presented to programmers.

Second word: layered architecture - this hides the low level differences under a consistent layer.


Why do Tarjan's and Kosaraju's algorithms for finding strongly connected components have the same running-time complexity? I followed an explanation of Kosaraju's and Tarjan's strongly-connected components algorithms, and they say that both have O(|V|+|E|) time complexity.

That didn't make sense to me since Kosaraju uses two DFS passes and computes the transposed graph, but Tarjan's use only one DFS.

they say that both have O(|V|+|E|) time complexity.

that didn't make sens for me since Kosaraju use two dfs pass and compute transpose graph, but Tarjan's use only one dfs

If you check the definition of Landau notation you will see that it does not say which function is smaller, that is (here) which algorithm is faster. It ignores constant factors.
Both algorithms have running times in $\Theta(|V| + |E|)$; that does not preclude one of them being $2^{100}$ times faster than the other for all $n \leq 2^{100}$.


Asymptotic analysis of $T(n) = T(n/5) + T(4n/5) + \Theta(n)$ If I have a recurrence relationship like this:
$$T(n) = T(n/5) + T(4n/5) + \Theta(n),$$
how would I analyze its rate of growth?
I believe I can't use the master theorem. I tried to draw a tree but some of the branches terminate earlier. There's a way to calculate the big-O notation by assuming $T(n) \le 2 T(4n/5)$, but does this result in a tight estimate?

Your recurrence can be solved using the Akra–Bazzi theorem, a vast generalization of the master theorem. The result is $\Theta(n\log n)$.
You can also see this using a recursion tree. The root is labeled $n$. An internal vertex $m$ has children labeled $m/5$ and $4m/5$. Vertices are leaves if their labels is at most some arbitrary positive constant $C$, say $C=1$. The running time is proportional to the sum of all labels.
We can partition the vertices in the tree to levels according to their distance from the root. The first $\log_5 n$ levels of so are "complete", that is, their labels sum to $n$, and there are $\log_{5/4} n$ levels in total, so the sum of labels is between $n\log_5 n$ and $n\log_{5/4} n$ levels. In particular, the complexity is $\Theta(n\log n)$.


Matrix chain multiplication and exponentiation If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}B$ and only then evaluate numerically, because $AB$ is of dimension $1000\times1000$ but $BA$ is of dimension $2\times2$.

I want to solve a generalized version of this problem. Is there a reasonably efficient algorithm (not brute force) to optimize an expression containing:

Free matrix variables of known dimensions
Products of arbitrary subexpressions
Arbitrary subexpressions raised to natural power

... so that it takes the least amount of work to evaluate numerically, after substituting the free matrix variables with concrete matrix values?

The matrix chain multiplication problem is a special case of my problem.

Edit:

This is a tentative answer. It seems intuitively right to me, but I have no proof that it's correct. If it turns out to be correct, I'm still interested in the proof. (If it's not correct, of course, please do correct me.)

For every product raised to a power, say, $(A_1 A_2 \ldots A_k)^n$, consider every cyclic permutation of the factors:

$(A_1 A_2 \ldots A_k)^n$
$A_1 (A_2 \ldots A_k A_1)^{n-1} A_2 \ldots A_k$
$A_1 A_2 (A_3 \ldots A_k A_1 A_2)^{n-1} A_3 \ldots A_k$
...
$A_1 A_2 \ldots A_{k-1} (A_k A_1 A_2 \ldots A_{k-1})^{n-1} A_k$

... recursively. Each power is to be calculated using exponentiation by squaring (obviously), and all other products are to be calculated using the optimal order returned by the matrix chain multiplication algorithm.

Edit:

The idea outlined in my previous edit is still somewhat nonoptimal. The exponentiation by squaring algorithm actually evaluates expressions of the form $K A^n$ or $A^n K$, where $K$ isn't necessarily the identity matrix. But my algorithm doesn't consider the possibility of using the exponentiation by squaring algorithm with $K$ not equal to the identity matrix.

Disclaimer: The following method has not been rigorously proven to be optimal. An informal proof is provided.

The problem reduces to finding the most efficient ordering when considering the square of the product.

For example, when looking at e.g. $(ABC)^{50}$, we only need to optimally solve $(ABC)^2$ since this expands to $ABCABC$. No useful ordering information is added by concatenating $ABC$ again. The intuition here is that since the problem of optimal ordering can be solved bottom-up, higher orderings consisting of more elements using the same matrices are irrelevant.

Finding the best ordering of $ABCABC$ reduces to the Matrix Chain Multiplication problem. After finding an optimal ordering, apply exponentiation to the triplet (n-tuple generally) in the ordering.

As an e.g., if the optimal ordering for the square is $A(B(CA))BC$, the solution to the initial problem is $A(B(CA))^{49}BC$.

In summary:
1) The first step in solving $(A_1 A_2 \cdots A_n)^m$ is to solve $(A_1 A_2 \cdots A_n)^2$.
2) Solving $(A_1 A_2 \cdots A_n)^2$ is best approached as an instance of the Matrix Chain Multiplication problem.
3) Using the n-tuple ordering $G$ from the solution in (2) will give us the solution to (1) as some flavor of $A_1 \cdot A_2 \cdot G^{m-1} \cdot A_n$ (note that any other groupings from solving (2) should be applied as well).

Informal proof
Considering the simplest case using two matrices, $(AB)^n$, we note that $A$ and $B$ have dimension $X \times Y$ and $Y \times X$ respectively. Any product using $A$ and $B$ has one of the following dimensions:

$X \times Y$
$Y \times X$
$Y \times Y$
$X \times X$

We have either $X < Y$ or $Y ≤ X$.

Assumption 1a): $X < Y$
$AB$ has dimension $X \times X$, and this ordering is guaranteed to be optimal from a bottom-up approach. Any other configuration of $A$ and $B$ is either equally good, or worse. Thus, the problem is optimally solved as $(AB)^n$.

Assumption 1b): $Y ≤ X$
$BA$ has dimension $Y \times Y$. This is the optimal ordering for all products involving $A$ and $B$. Thus, the solution is optimally found as $A(BA)^{n-1}B$.

This concludes the proof, and we have only looked at the two orderings found in $ABAB$, the square problem.

Using more matrices, the argument is similar. Perhaps an inductive proof is possible? The general idea is that solving the MCM for the square will find the optimal size for the operations with all involved matrices considered.

Case study:

julia> a=rand(1000,2);
julia> b=rand(2,1000);
julia> c=rand(1000,100);
julia> d=rand(100,1000);
julia> e=rand(1000,1000);

julia> @time (a*b*c*d*e)^30;
  0.395549 seconds (26 allocations: 77.058 MB, 1.58% gc time)

# Here I use an MCM solver to find out the optimal ordering for the square problem
julia> Using MatrixChainMultiply
julia> matrixchainmultiply("SOLVE_SQUARED", a,b,c,d,e,a,b,c,d,e)
Operation: SOLVE_SQUARED(A...) = begin  # none, line 1:
    A[1] * (((((A[2] * A[3]) * (A[4] * (A[5] * A[6]))) * (A[7] * A[8])) * A[9]) * A[10])
  end
Cost: 6800800

# Use the ordering found, note that exponentiation is applied to the group of 5 elements
julia> @time a*(((((b*c)*(d*(e*a)))^29*(b*c))*d)*e);
  0.009990 seconds (21 allocations: 7.684 MB)

# I also tried using the MCM for solving the problem directly
julia> @time matrixchainmultiply([30 instances of a,b,c,d,e]);
  0.094490 seconds (4.02 k allocations: 9.073 MB)


{a^n b^n c^n | n>=1} - PDA I just started learning context free grammar and Pushdown Automata, I tried implementing this particular language via a PDA, despite being told this language is context sensitive.
How I attempted it is by popping every 2 'a' for 1 'b' and then popping 1 'b' for 2 'c'. I don't understand why is this wrong.
I feel I am be overlooking something really minuscule.

Yes you missed something ,
Lets review how your PDA works :

we push  a for each a we read
we pop 2as for each b we read , then when stack is empty we push b for each b we read
we pop b for each 2cs we read

Your PDA will accept strings of form a2nbn+mc2m
for ex , a4b5c6 , here n = 2 , m = 3
You push 4 as , then for each 2as you pop b , you pop 2bs , and 3 bs remain which are pushed to stack !!!
Hopefully you can see the problem here , no one told you that you are half way bs when you finished popping as
You continue , for each of the 6 cs you pop a b then you accept
You expect the string in the form a2nbn+mc2m , you compare  a2nbn then  bmc2m , of course if n = m you are correct , but there is no way to ensure this


Best solutions to 6 degrees of separation From purely my knowledge of computer science a simple breadth first search from root A in search of node B, while keeping track of the depth of the tree, would be the most effective way to check whether A and B have 6 degrees of separation. If I simply wanted to check whether B is within 6 degrees I could also limit my depth to 6.

I have heard however that there are better ways of doing this using bidirectional methods which involve some heuristics. I was wondering if someone could explain the most effective way of doing this and compare space and time complexity between the different approaches. Thanks!

And as a followup, what would be a good algorithm for finding the degree of separation between two arbitrary nodes A and B and the path between them?

You could possibly save some space using a "meet in the middle" approach. Make a list of all nodes at distance at most 3 from A, and another list of all nodes at distance at most 3 from B. If the lists intersect, then A and B are at distance at most 6. In the fact, it is enough to construct one of the lists and then generate the other list, testing whether each element belongs to the first list.

To determine whether the lists intersect, you have two options: either sort the first list, or put it into a hash table. The second uses more space but it's faster. (You will need counterparts of these, a balanced binary tree or a hash table, to generate the lists in the first place.)

Practically speaking, you would apply the following optimization: first determine all nodes at distance 1 from A and all nodes at distance 1 from B, and check whether the lists intersect. Then check all nodes at distance 2 from A against all nodes at distance 1 from B. Then check all nodes at distance 2 from A against all nodes at distance 2 from B. And so on. If the distance is less than 6, then you potentially save a lot of time and space.


Check if two items are equal after replacing Let's say that an item is either a natural number or a list of items. Examples of items are:

1
[2]
[4, [3, 1], 3, 4]

A rule states that two items are equal. For example:

1 = 2
3 = [3, 1]
[4, 3] = [1, 5]

When using these example rules, we can transform [4, [3, 2]] into [4, [3, 1]] into [4, 3] into [1, 5] and we can say that  [4, [3, 2]] equals [1, 5].

I want to find an algorithm that, given items $a$ and $b$ and a finite set of rules, determines if $a = b$.

I already thought of an algorithm that works in some cases. But I hope to find an efficient algorithm that works in all cases. It would also be nice if the algorithm can detect $a \not= b$ instead of infinitely searching for ways to let $a = b$. Is this a known problem? Any help is appreciated.

Note: We can simplify the problem by only allowing the number 1 instead of every natural number. This is equivalent, because we can transform 1 into [1], 2 into [1, 1], 3 into [1, 1, 1], etcetera.

I found a solution to my problem. Let's look at the simpler but equivalent problem in which an item is recursively defined as an empty list or a list of items. I'll summarize the algorithm.
Variables:

Int counter starting at 0
Hash map: list of integers $\to$ integer.
The integers represent equivalence classes.

Function find(item) $\to$ int:
Finds the equivalence class of an item. Recursively call find on all the children of item. Now you have a list of ints. If this list of ints is contained in the hash map, return the corresponding value. If not, add the list to the hash map with the counter as value. Increase the counter and return the value.
Function merge(int a, int b):
Merges two equivalence classes a and b. In the hash map, replace all occurences (both in keys and in values) of a by b. Now it can happen that one key is mapped to multiple values. If that happens, again merge those values.  Repeat this until every key maps to a unique value.
Algorithm:
For every rule c = d, call merge(find(c), find(d)). Then to see if a = b, check if find(a) = find(b).


Questions on Topological Sorting Currently learning about topological sorting.
My teacher gave us this problem.

The answer given to us is : B,A,C,E,D,G,F,H in lexicographical order.

Why does the order go from B,A,C THEN go to E and then D IF it is in lexicographical order?
Also, can another topological sort of this graph be: B,A,C,D,E,G,F,H?

The comments are right. In a topological sort, we start with nodes that have no incoming arrows and remove them from the graph, so to speak. In this case, if there are multiple possible nodes to remove, then we want to remove them in lexicographical order. Hence, the order should be $B, A, C, D, E , F, G, H$.

Your suggest topological sort does not work. This is because you propose to put $G$ before $F$.


How were operating systems even made? By that, I don't mean what is needed to make an operating system. I know that OSes are built on top of kernels and whatnot. But what I mean is, it wasn't like anyone could just "program" the OS like any other software, right? Was an assembler first built? and then a C compiler on top of that? It's a chicken-egg problem I can't seem to find the answer to.

There is some great mysticism around Operating Systems. They are sometimes treated like this dark wizardry that only a handful of the initiated are allowed to understand. (Compilers are treated like that as well.)
Here's the truth, though: an Operating System processes inputs and does something in reaction to those inputs. You know what also does that? Every other program.
An OS is just a program. There is nothing special or magical about it.

But what I mean is, it wasn't like anyone could just "program" the OS like any other software, right?

Why not?
Linux was literally written by accident.
Linus Torvalds saved up to buy his dream machine, the pinnacle of computing at the time: a 32 bit 80386 PC clone. And he wanted to learn how to program the 80386 to get the most performance out of it. He spent a lot of time using a terminal program to connect remotely to the university, but all terminal programs that existed where too slow or too clunky.
So, he decided to kill two birds with one stone and teach himself 80386 assembly by writing a better terminal program. After a while, he realized that if he wanted to really dive into how the 80386 works and wanted the most performance, he should get rid of the Operating System and just boot into his terminal program directly. So, he wrote a boot loader that booted directly into the terminal program. Now, without the OS, he also needed a keyboard driver, so he could type commands into the terminal program, he needed a console driver so that the terminal could print answers back, and he needed a driver for the serial port, so he could connect to the university. Unfortunately, when he wanted to transfer files, he still had to boot into the OS, so he added a hard disk driver and a file system driver to the terminal program. And in order to be able to use the terminal program while it was downloading files, he added multithreading and a scheduler.
It was at this point, that he realized, that he had accidentally written an almost complete Operating System. So, he decided to further play around with it, add some missing features, etc.
Then, one day, he mistyped a command, and accidentally overwrote the partition with his Minix installation, thus destroying the existing OS that was installed on the PC.
Now, he had a decision to make: reinstall Minix or finish his OS. And the rest, as they say, is history.
So, writing an OS is really not that different from writing any other kind of program. Linux is the existence proof of that, because it is just a normal program that accidentally became an OS.


compute a gradient with "minimal" colorstops from a ordered set of RGB colors I got a array of colors that are closely related = most of the time there is no sharp transition between color[n] and color[n+1].

Exemple of such an array of colors
[0,.1,.2,.3,.4,.5,.6,.7,.8,.9,1.0,.8,.6,.4,0.2,0]

You'll notice that there are 3 "special" values. The colors
slowly increase from value 0 to 1 (in 10 steps) then
decrease more rapidly from 1 to 0 (in 5 steps).

So our array could also be described this way :

an array of 16 colors where
Color[0]  whose value is  0 evolves linearly until
color[10] whose value is  1 evolves linearly to
color[15] whose value is  0

I don't really care about the length of my initial array. It will be  stretched (interpolated) so instead of using indexes it makes more sense to use percentage values
index 0  /15 = 0%
index 10 /15 = 66%
index 15 /15 = 100%

so the initial array could be rewritten like this
[{0, 0%}, {1, 66%}, {0, 100%} ]

This last notation is close to what is called a gradient in svg or css. The special color are named "colorstops" and gradients are written this way
linear-gradient(black 0%, white 66%, black 100%);

One could notice that some gradients are equivalent

linear-gradient(black 0%, white 100%) =
linear-gradient(black 0%, grey 50%, white 100%) =
linear-gradient(black 0%, lightgrey 25%, grey 50%, darkgrey 75%,  white 100%)

like

interpolation[0, 1] =
interpolation[0, .5, 1] =
interpolation[0, .25, .5, .75, 1]

So my challenge is to go from
[0,.1,.2,.3,.4,.5,.6,.7,.8,.9,1,.8,.6,.4,.2,0]
to
linear-gradient(black 0%, white 66%, black 100%)
and not the naive
linear-gradient(
 black    0%,
 grey++++ 6%,
 grey+++  13%,
 grey++   20%,
 grey+    26%,
 grey     33%,
 grey-    40%,
 grey--   46%,
 grey---  53%,
 grey---- 60%,
 white    66%,
 grey---  83%,
 grey-    80%,
 grey+    86%,
 grey+++  92%,
 black   100%)

The expected size of color array is no more that 2000 RGB colors and the goal for color-stops is no more that 10 and ideally 2.

EDIT
 in fact what i want to do is compute the blue lines like on the following graph

What you want to do is fit a piecewise linear function to your data.

No noise

If the data is perfect and has no noise, this is easy:

Form a line from the first points.  Remember those two points as the endpoints of the line.
If the third point lies on this line, discard the right endpoint and replace it with the third point.  Otherwise, start a new line from the second point and third point.
Repeat.

That can be done with a simple linear scan.

Noisy data

If the data is imperfect and noisy, you want to do a best fit of a piecewise linear function to your data.

There's no universal answer, as there are multiple ways to fit a piecewise linear function.  If you have $n$ points, you can always get a perfect fit by drawing $n-1$ lines (one line between each consecutive pair of points), but the resulting function might be very wiggly and not what you are looking for.  In practice, we probably have the idea that a solution with few pieces (few lines) is probably more likely than one with more pieces, all being equal.  On the other hand, with too few pieces, you might get a very poor fit.

Thus, you need a parameter to balance the number of pieces against the amount of error in your fit, and then you can try to find an optimal solution.  So, the first step will be to define a loss function that quantifies how good/bad each candidate solution is.  Once you have that, there are various algorithms for finding the best fit.  One approach is to use dynamic programming.  See https://en.wikipedia.org/wiki/Segmented_regression, https://dsp.stackexchange.com/q/1227/5874, https://stackoverflow.com/q/22028529/781723, and probably many other sources.

My guess is that if there is any noise/error in  your data, it will be very small, so any reasonable procedure will work well.


Can a computable program have an infinite output? Can a computable program produce an infinite output from its (presumably finite) input?

*I wouldn't think so for similar argument as to why it can't compute over an infinite input.

A follow on (basically the same?) question: Are there non-halting programs that are computable?

Thanks!

Our general rule is one question per post.  I'll answer the first question.

A program can certainly produce infinite output.  It can enter an infinite loop producing output.  Consider everyone's first program in Basic:

10 PRINT "Hello World!"
20 GOTO 10

It makes no sense to talk about a program being computable.  There's no need to you write a program to output a program.  Instead, you can just write the program you want in the first place.  Instead of talking about computable programs, computability is about languages.  We talk about languages being computable.  Check the definition of computability.


Are some real world compression algorithms sometimes producing unexpectedly large files? Lossless compression is not magic. It just gives the common patterns a short notation, compensating by the less common patterns ending up with a longer notation. By that logic, all lossless compression algorithms must sometimes give you a larger file back. A real world example of that is for instance giving a file containing 'a' and a line feed to gzip (2 bytes), it subsequently returns a 30 byte file. In general, compression tools do not break even for very small files.

My question is: Are some compression utilities bloating out larger files by some significant amount? (While "Give this file to 7z and watch you harddrive fail!" is cool, things like "This 4kb file will grow to 6kb." are also good.)

I can see a reason why such behaviour might not exist. If you for instance always put an extra bit to the output telling if the file is actually compressed, or just the original file in the cases where the compression fails, your output can never be worse than the original file plus 1 bit. I am however not sure if any such protection against unexpected large files is used.

If you take vanilla RLE in bitmap which does not have any consecutive runs it will increase file size two times. It is apparently very rarely used fact that BMP, TIFF and PCX allows compression, (not all applications supporting these formats even implement RLE scheme). This is very pathological case and since it mostly increase file size it is abandoned.

Normal compression algorithms include information of failure, so instead of huge increase you can expect several bytes per chunk increase. In those that do not check there are three methods of checking how far we can increase file: take already compressed file, take encrypted file or find pathological cases from algorithm.

I have generated $256 \text{ bytes}$ file with consecutive numbers.
Compressed as 7z LZMA: $349 \text{ bytes}$, LZMA2:$356 \text{ bytes}$, Deflate or Deflate64: $400 \text{ bytes}$, bz2: $388 \text{ bytes}$, PPMd: $421 \text{ bytes}$ so not that cool.


Approximated TSP: weight of minimum spanning tree less than cost of the optimal tour? In the chapter, Approximation Algorithms of Introduction to Algorithm, 3rd Edition, for the approximation problem Travelling Salesman Problem, the author proposes a approximation method that first constructs a minimum spanning tree.

In order to prove this algorithm is a 2-approximation algorithm, the author claims that:

The weight of the minimum spanning tree $T$ is less than the cost of the optimal tour.

I am wondering if the minimum spanning tree(which is acyclic) of $G$ ensures that its weight is necessarily smaller than any tour(which is cyclic) of the same graph $G$

PS:

The original claim is:

If you take any tour and remove any edge, then you get a spanning tree. Hence the weight of a minimum spanning tree is at most the weight of every tour.

I should add that one of the tricks behind this algorithm is that while we can't find a minimum tour efficiently, we can find a minimum spanning tree. Minimum spanning tree is an efficiently computable relaxation of minimum Hamiltonian path.


Approximation algorithm for TSP variant, fixed start and end anywhere but starting point + multiple visits at each vertex ALLOWED NOTE: Due to the fact that the trip does not end at the same place it started and also the fact that every point can be visited more than once as long as I still visit all of them, this is not really a TSP variant, but I put it due to lack of a better definition of the problem.

This problem was originally posted on StackOverflow, but I was told that this would be a better place. I got one pointer, which converted the problem from non-metric to a metric one.

So..

Suppose I am going on a hiking trip with n points of interest. These points are all connected by hiking trails. I have a map showing all trails with their distances, giving me a directed graph.

My problem is how to approximate a tour that starts at a point A and visits all n points of interest, while ending the tour anywhere but the point where I started and I want the tour to be as short as possible.

Due to the nature of hiking, I figured this would sadly not be a symmetric problem (or can I convert my asymmetric graph to a symmetric one?), since going from high to low altitude is obviously easier than the other way around.

Since there are no restrictions regarding how many times I visit each point, as long as I visit all of them, it does not matter if the shortest path from a to d goes through b and c. Is this enough to say that triangle inequality holds and thus I have a metric problem?

I believe my problem is easier than TSP, so those algorithms do not fit this problem. I thought about using a minimum spanning tree, but I have a hard time applying it to this problem, which under the circumstances, should be a metric asymmetric directed graph?

What I really want are some pointers as to how I can come up with an approximation algorithm that will find a near optimal tour through all n points

I don't know how to solve your problem or show its NP-Hardness but you can find all pair shortest path to convert your graph to metric one, just replace $e_{a,b}$ with shortest path from a→b and if there isn't edge between $a,b$ add new edge with shortest path weight, now you can run some approximation for TSP to find approximation for your problem, as I know best approximation for TSP is currently $O({\log n \over \log{ \log n}})$. Base idea is using Held-Karp relaxation and finding special spanning tree then using method like Christofides algorithm. (it has some new definitions like Thin tree, ... which makes it harder than other methods for asymmetric case), you can also use known $O(\log n)$ approximations. Also I thought about your problem to approximate it with a minimum cycle cover, but I couldn't get good result. If I found anything I'll update this answer.


Whats is the meaning of polynomial run-time in input size ? If an algorithm runs in exponential time with exponential input then we say it runs in polynomial time ?
Why ?
Doesn't the algorithm run in exponential time anyway ?
How the input size affects ?
Thanks.

I think I understand the question enough to answer it. Yes polynomial time is the time the algorithm takes relative to the size of the input. So if your input has size $n$, PTIME means the running time is a polynomial in $n$. Sure if you replace $n$ with some exponential $n=e^p$ you get an exponential time relative to $p$ (assuming the algorithm was not running in constant time). But that does not invalidate the concept of polynomial time anymore than saying that $f(x)=2x$ is a linear function but you can substitute $x$ with $y^{y^y}$ on both sides, i.e $f(y^{y^y})=2y^{y^y}$; it is an intrinsic property of $f$ of being linear in its argument.

This is further discussed on an example at https://cstheory.stackexchange.com/questions/18756/whats-the-meaning-of-input-size-for-3-sat

This issue of having to express the input size as a function of another "quantity" does occur (implicitly) in the context of reducing one problem to another in order to feed it to an existing algorithm. In that context, in order to avoid the obvious gotcha that would "prove" an EXPTIME problem is a PTIME one by using an exponential-size encoding, only polynomial-time reductions are allowed. So, if $p$ is the size of a problem, you can encode it in PTIME as another problem of size polynomial in $p$. But you can't encode it (taking only PTIME) as problem of exponential size in $p$.


Every LEFT-RESET Turing machine has an equivalent conventional Turing machine I am working on a proof of the theorem that every LEFT-RESET Turing machine has an equivalent conventional, single tape Turing machine. The transitions for the LEFT-RESET Turing machine are {Right, RESET}, and the transitions for the conventional Turing machine are {Left, Right}. Here is the general outline of my proof:

Given a LEFT-RESET Turing machine $T_1$ and a conventional, I will prove that $T_1$ has an equivalent conventional Turing machine $T_2$. There are two possible transitions for $T_1$: right and reset. The right transition of $T_1$ is identical to the right transition of $T_2$. When $T_1$ performs a reset, $T_1$ moves its read-write head left until it reaches the leftmost cell on the tape. Therefore, a LEFT-RESET Turing machine is equivalent to a conventional Turing machine. Q.E.D.

Do I have to prove that there is a series of transitions on $T_1$ that are equivalent to a single left transition on $T_2$? Other write-ups I have seen include this, but if the LEFT-RESET Turing machine cannot perform a traditional left transition as an operation, I do not understand why it is part of the proof.

The other write-ups you mention show that the two models are equivalent. That is, they also show that a normal Turing machine can be simulated by a left-reset Turing machine.


Heaviest planar subgraph Consider the following problem.

Given: A complete graph with real non-negative weights on the edges.

Task: Find a planar subgraph of maximum weight. ("Maximum" among all possible planar subgraphs.)

Note: The maximum-weight subgraph will be a triangulation; if the complete graph is on $n$ vertices, it will have $m=3n-6$ edges.

Question: What is the best available algorithm for this problem? What is its time-complexity?

This is NP-hard even for weighted complete graphs. For an easy algorithm, you can compute a maximum-weight spanning tree: negate the edge weights and run Kruskal's algorithm. This gives you a performance ratio of 1/3 (a spanning tree has $n-1$ edges, and as you note, a maximum planar subgraph can contain at most $3n-6$ edges). As far as I know, the algorithm in [1] which has a performance ratio at least 25/72 and at most 5/12 has not been considerably improved upon (but see what newer papers reference it).

For complete graphs whose edge weights obey the triangle inequality, the performance ratio of the algorithm in [1] is at least 3/8. The algorithm, I think, is rather involved and can be made to run in $O(m^{3/2}n \log^6 n)$ time on general graphs. There are some simpler variants the authors present as well with different performance ratios, and possibly better runtimes.

[1] Calinescu, G., Fernandes, C. G., Karloff, H., & Zelikovsky, A. (2003). A new approximation algorithm for finding heavy planar subgraphs. Algorithmica, 36(2), 179-205.


Local to global algorithms in gossip based P2P networks Suppose we have a peer to peer network of, say, $n$ peers. Peers communicate by an asynchronous randomized gossip protocol (Push, Pull, Push/Pull doesn't really matter here). The task is for any local peer to get an (approximate) picture of the global communication in all of the network over time.

I mean after some time $t_1$, each local peer $k$ should have a data structure that is the record of every gossip event that took place in all of the network up to a time $t_2$, with $t_2\leq t_1$. This data structure should provide knowledge about the appearance of events globally over space and time.

To make it "simple", we can assume, that communication channels never fail. Every peer can reach every peer. However since peers might crash or disappear, we can not just choose some central peer that records everything and then redistributes its knowledge.

A solution exist in the so called hashgraph algorithm, which goes roughly as follows:

Every peer stores locally a directed acyclic graph, to record the gossip events. Vertices are the gossip event together with an identifier of sender and receiver. Each vertex has two incoming edges, which might be called $sender\_parent$ and $receiver\_parent$. $sender\_parent$ is an edge from the previous gossip event of the sender and $receiver\_parent$ is an edge from the previous gossip event of the receiver. Outgoing edges are of arbitrary number.

Each time a peer connects to another peer it askes for the previous gossip event of the receiver, then creates a new vertex locally to record *this event. Then it transfers all of the graph along to the other peer. (This is a simplification for the push protocol and can be tweaked appropriately for pull or push/pull as well)

The question now is, whether or not this is essentially (up to isomorphism) the only way to do it. The hashgraph algorithm is patented. Therefore it would be good to know if other solutions exist. With such local to global views, network analysis can be quite efficient.

Edit: The system is free to implement any kind of communication contend, which makes the task possible.

Another solution would be to use SWIM gossip (Scalable Weakly-consistent Infection-style Process Group Membership Protocol), or it derivatives like Serf (which includes the vivaldi network and SWIM) or even Consul (which implements raft consensus, key value store, and Serf).


Language Decidability What is the easiest and the most straightforward way to find whether a given language is decidable?

For example, how do we know if the following languages are decidable or not?

`Binary representation of all prime numbers`
`{ empty string(eps) }`

A language $L$ is decidable if there is an algorithm that halts on every input, says Yes if the input belongs to $L$, and says No if the input doesn't belong to $L$.

The language of all binary representations of prime numbers is decidable since there is an algorithm that decides whether an integer is prime. You can probably code such an algorithm yourself in your favorite programming language. There are a few added complications - you need to parse the input, and you need to handle arbitrarily large integers - but intuitively these are not hard to address.

Similarly, the language consisting of only the empty string is decidable, since an algorithm can examine the string and check whether it is empty or not.

The real challenge is proving that some problem ins't decidable. The main techniques are are diagonalization and reduction. Roughly speaking, proofs by diagonalization construct an input that every potential algorithm fails to address, using some kind of self-reference. A good example is the halting problem, much information on which is available online. Proofs by reduction show that if you could decide your problem X then you would be able to decide some other problem Y which is already known to be undecidable.


Why does the Huffman coding algorithm produce a valid tree? I am not asking about the Huffman Code, but the most widely described algorithm for generating one, also described on the english wikipedia: https://en.wikipedia.org/wiki/Huffman_coding#Compression
Now, I am not really concerned with the code being optimal or not, because many proofs for this can be found, but there is one thing that bothers me - why can I be sure, that for any path on the Huffman Code tree, no string constructed from labels is a prefix of another string in the tree?
Considering a simple tree (source: http://homes.sice.indiana.edu/yye/lab/teaching/spring2014-C343/huffman.php):

It has these codes:
E - 0
U - 10
D - 01
L - 110
C - 1110
M - 11111
Z - 11110
K - 11111,
and it is obvious, that none of these codes is a prefix of another. However, I am looking for a general proof that this is true for any Huffman tree, which for some reason I am unable to find. I would be grateful for any sources.

Let $v$ be a vertex of the tree. If $\pi_v$ is the path from the root of the tree to $v$, then the string $s(v)$ constructed from the labels of $\pi_v$ is unique (if you really want, you can prove this by induction on the depth of $v$).
If $s'$ is a proper prefix of $s(v)$  then there is a node $u$ in $\pi_v$ such that $s(u)=s'$ and, by the above observation, this node is unique.  Moreover, $u$ cannot be a leaf (since it precedes $v$ in $\pi_v$).
This means that, for each leaf $v$ there is no prefix of $s(v)$ that matches the code $s(v')$ of another leaf $v'$. Since the symbols only appear as leaves of the tree, this means that the code is not ambiguous.


algorithm for correctly rounded floating point radix conversion Is there any generic algorithm which implements a floating point radix conversion?

Lets say we have a $p$-digit FP number

$A = \sum_{i=0}^{p-1} A_i \beta^{e-i}$

in radix $\beta$ and with $0 \leq A_i < \beta$.

How do we find the $A'_i$, $e'$ values for the $p'$-digit base $\gamma$ FP number

$A' = \sum_{i=0}^{p'-1} A'_i \gamma^{e'-i}$

closest to $A$?

There is one question which explicitly asks about radix 2 to radix 10 conversion, but unfortunately the answers seem to be specific for these radix combination. Here I ask about the general case.

Also is an intermediate arbitrary precision FP calculation really necessary? (as in the function strtod in David Gay's dtoa.c)

In the worst case, you may need very high precision intermediate results. If your problem is limited, for example p ≤ 50 and e ≤ 1,000, it will be possible to prove how much precision is needed at most - with $1000 \cdot 10^{50}$ possible values to convert, 200 bits precision are likely enough.
In practice, some values can be calculated with correct rounding by calculating them with a single floating point operation with exact operands. Many other values can be calculated rounded correctly (including proof) with just a bit of extra precision. So you can do the calculation with relatively few extra bits of precision, check if you have a proven correctly rounded result, and do the same calculation with more bits if needed.
Example: 10.00073 = 1,000,073 / 100,000 Is the quotient of two exact numbers and therefore correctly rounded. 1e30 = 1e15 x 1e15 = product of two exact numbers. 1,000,000,000,000,000,123,456,789,012,345 = FMA (1e15,1e15, 123,456,789,012,344) = fused multiply-add of there exact numbers.


How to build a parser for syntactic analysis of regular expressions? Is it possible to build a parsing algorithm that build a parse tree using a top-down method that simulate a derivation process for regular expressions, like we do for type 2 languages?

My guess

Given a regular expression r, build its FSA, then obtain the grammar that generate r in order to build a parse tree

It is absolutely possible and you are on the right track.  You will need to make sure your grammar is %100 correct and probably LL(1), from there you can choose one of many algorithm examples that are out there or write your own.

See https://en.wikipedia.org/wiki/Top-down_parsing and https://en.wikipedia.org/wiki/LL_parser

Word of warning: The tricky part won't be the implementation but getting your grammar right.


Is the "Bidirectional Dijkstra" algorithm optimal? In some sites they say the bidirectional Dijkstra's algorithm is optimal, e.g.,
this, and this. Also there is some software that uses this algorithm (for example this DBMS).
But some posts express doubts about the optimality of this algorithm, such this, and this. Which one is correct?  Is the bidirectional Dijkstra's algorithm optimal or not?

When we talk about the "bidirectional Dijkstra" algorithm, we actually mean a family of similar algorithms which are implementations of a more abstract idea. All of these algorithms are optimal (produce an optimal solution). Some algorithms may work only under some assumptions on the input, for example only in the unweighted case, which is what the doubtful posts seem to have in mind.

More generally, algorithms usually come with correctness proofs. These proofs show that under certain conditions, the algorithm has certain guarantees. If these conditions don't hold, that the guarantees don't necessarily hold. When using an algorithm, check that the conditions that you know hold indeed imply the guarantees that you are looking for.


If a NAND gate is universal, why you don't have NAND OISCs If a NAND gate can be used to construct all other of the basic logic gates, then I'm wondering why you don't/can't have a purely NAND-based One Instruction Set Computer (OISC). All the OISC single instructions are complicated like "addleq, add and branch if less than or equal to zero", but I don't see why you can't just have an OISC be "nand, perform nand operation". Wondering what I am missing.

With such an instruction set, all you could express are straight-line programs.  Without branches, you can't have loops.  Thus, the program would not be able to handle arbitrary-length inputs: it would be limited to dealing with fixed-size inputs (or inputs with a fixed known upper bound on the size of the input).  So, that wouldn't be very satisfactory.


my new sorting algorithm, what should my upper bound be? I just thought this up while walking after typing up a knapsack with repetition implementation in Python.
I want to teach computer science so I talk to myself a lot pretending to talk to students.
So in my imaginary lecture for merge sort, I used the example of an unshuffled deck of cards.
But then it hit me that, "With cards, I know what high and low are so I can just have a grid that is 4 * 13 with spades as first row, then hearts, then clubs then diamonds".
That would take exactly O(n) where n = 52 to sort the pile if I pick a card and put it in its place since each operation takes O(1) + O(1)
So then I thought, why can't I do this for a sort of any array with the caveat being that all values need to be distinct.
I can find the minimum and maximum in O(n), remember the indices and truncate the input array by 2 by deleting these to make array called rem for remaining.
Then I make an array of size (maximum - minimum) as the grid with minimum at index 0 and maximum at array.length - 1 and initialize all values to some value outside the range of minimum to maximum.
Then I remember what minimum and maximum are for the following operations.
Iterate rem from index 0, and for each element, calculate:
index = element_value - minimum
Then put the element in the grid at position index.
Repeat for the entire rem array.
Calculations are done in constant O(1) time as well as insertions for n times for total O(n).
Now make a new array final that has length of input array.
Now traverse the grid and transfer to array final all valid values that are not equal to the initialized value outside the range.
This could take a super long time if the difference between maximum and minimum far exceeds input size n so when I do maximum - minimum, I have to set some sort of upper bound to this difference before it defaults to an O(nlogn) merge sort or an even faster Tim sort that is built into Python.
But say the initial range is min = 0, max 20 and n = 10.
That final operation would take O(2n) which is still big-O of O(n).
If the range is min = 0, max =100 and n =10, it would take O(10n) which still defaults to O(n)?
Calculating O(nlogn) for the last example, I get:
(10) * log_2(10) = approx. 35?
Which means max-min <= 35 I can match the speed of merge sort?
Edit:
Even if there are repeated values in the input array, I could have have a 2D array for the grid or a list of tuples in the case of Python and keep adding to it.
tup = tup + (repeat_val,)

And for an input array with consecutive values, this would be way faster wouldn't it?

It looks like the algorithm you are describing is called counting sort.
This algorithm works in $O(n+k)$ where $n$ is the number of items in the input, and $k$ would be their range: $k=max - min$.
This algorithm is indeed better in computational time complexity than mergesort when you restrict $k$ to be small enough. For your examples, you "fixed" a value for $n$ and $k$, which makes no sense to compute the big-O notation on. The big-O describes the algorithm in its full behaviour, and is an upper bound for any "fixed" value you would give.
As a side note, this algorithm is not a comparison-based sorting (sorting only by comparing numbers), and can only sort natural numbers. Actual comparison-based sorting algorithms (like mergesort) must take at least $\Omega(n\log(n))$, but are capable of sorting any list, and not just natural numbers.


To calculate how many times a certain year repeats itself in the calendar within a given year range Let's say I have a year $Y$. I wanna know how can I calculate the number of times the calendar configuration of the year $Y$ repeats itself in the year range $[A, B]$.

Is there any method to it without brute force, in a pretty efficient way?

NOTE: I'm talking about the Gregorian Calendar.

Basically, the "configuration" of a year, if I understand well can be described as a state $Y_i = (D_i, L_i)$ with $D_i$ the weekday of January the $1^{st}$ (0 to 6 for monday to sunday) and $L_i$ which is 1 if $Y_i$ is a leap year and 0 else.

So, comparing the state of 2 years, you can decide wether they have the same configuration.

As a year has 365 days (366 for a leap year) and $365 \mod 7 = 1$ (2 for a leap year), there is a simple relation:

$D_{i+1} = D_i+L_i+1 \mod 7$

As there is one leap year every four years (without 100-exception), it is interesting to also notice there is a 5-step on weekday every 4 years:

$D_{i+4} = D_i+5 \mod 7$

Now, how to not loop on all year ?

Let's consider leap years are all years divisible by 4 without exception. Then, from a starting year $Y_0$, we seek the next year with same configuration $Y_s$. Let's consider all possibles values of $M_0 = Y_0 \mod 4$ :

$M_0 = 0$, then $Y_0$ is a leap year, as $GCD(5, 7) = 1$, 7 of the 5 steps (28 years) are necessary to reach the same configuration: $Y_s = Y_0 + 28$ and $M_s = 0$
$M_0 = 1$, then $Y_s = Y_0 + 6$ and $M_s = 3$
$M_0 = 2$, then $Y_s = Y_0 + 11$ and $M_s = 1$
$M_0 = 3$, then $Y_s = Y_0 + 11$ and $M_s = 2$

Thus, if the considered year is a leap year, you have exactly the same configuration every 28 years, else, you have 3 times the same configuration every 28 years. In the latter case, the $B-A \mod 28$ reamaining years may be simply considered with above rule.

To consider the 100-exception, you may do the same work adding an extra variable modulo 100 (quite more laborious).


Phrase generators for use with testing grammars that don't use a seed In helping someone understand phrase generators for use with testing grammars, think compiler test cases, I noted that I have never found a phrase generator that is knowledgeable of the grammar, and is deterministic. The phrase generators I am talking about rely on the grammar of the language as input so that the user does not have to recreate the rules for the grammar into a format acceptable for the tool. The tool must accept a BNF grammar; I don't mind if the grammar has to be factored some for the tool before input. Tools that rely on a seed or generate a random seed are what I want to avoid.

I am aware that one can use PROLOG to generate a parser and then run a query that outputs a set of results that are phrases used for testing. I also know that it is not uncommon for these result sets to have 10**15 answers for basic cases of a grammar like C++.

Does anyone know of such tools? They can be commercial or open-source as I don't plan on using it, I have my own, I just want to verify my knowledge.

EDIT

The tool must encompass sematic knowledge of the compiler. In other words the phrases must be able to be compiled by a compiler, not just pass the syntactic rules.

EDIT

I agree that the comments and answers regarding deterministic are correct and I my use of the word here is not correct.

What I am looking for is a tool that not only takes in a BNF grammar and can use it "as is" which would mean for a grammar like C++ a basic result sets with 10**30 items. That is not an accurate number but a realistic one based on a phrase generator I have that can report the number of results before generating the results. Since that size of a result set is impractical, I have given the tool the ability to enhance the grammar with constraints, thinking tree pruning. This allows one to generate phrases for one particular branch of the grammar, and also prune and limit the sub-braches and number of recursion over those branches. Even with the constraints each result item is a valid C++ file for use as input to a C++ compiler.

I have a proof of concept of this already, but the difference between a proof of concept and useful tool is a lot of work. So while a seed can be reused and create deterministic results, it does not allow the user to determine the conditions.

The tools you refer to are probably already deterministic. Tools that accept a seed probably only employ a pseudorandom generator which is keyed from the seed and nothing else. Therefore, given the seed, everything is completely deterministic. If the seeding process is reasonable, then a seed like $0$ or $1$ should work. For definiteness, I suggest you take your favorite "random" tool and use a fixed seed, say $1$. Now it's completely deterministic.

One reason you'd want a deterministic tool is reproducibility. You want to be able to reproduce phrases on demand. If the tool is random, that's impossible. However, if all the "randomness" is encapsulated in a user-entered seed, the output is reproducible; all you have to do is remember the seed used.

I cannot think of any other reason you'd want your tool to be deterministic, but if there is one, please let us know so that we can understand your question better.


Algorithm to separate circles to reduce collision the maximum between them I'll try to do my best to explain this.

I have X circles (from 2 to 4) which can move around smaller pivot circles. The pivot circles are fixed and cannot be moved once they are in the "field". Pivot circles are never created colliding with other pivot circles. Something like this:

Red are pivot circles (fixed) and orange are the normal circles (displace without exiting the pivot circles).

Now if I put two pivot circles near, the algorithm should do something like this:

This is pretty easy to achieve. Detect colliding circles and displace them the needed amount. Because red circles never collide, the orange circles are never going to break the "do not exit the pivot circle" rule.

The problem comes when 3 or more circles come into play. Because they cannot exit the pivot circle zone, so there should be some vertical/horizontal movement, like this:

I think this is the least colliding I can achieve when 4 pivots are next to the other. I created this manually but I'd like to know if there's already an algorithm to detect this efficiently without making a lot of detections/passes to achieve the least colliding factor, as I don't like everything that I'm thinking on.

The best I can think of is to simply do a loop where I detect all circle collisions, then displace the circles the amount needed for them to avoid the collisions the maximum possible, then repeat the loop, and repeat until I find that the "collision factor" is not reduced anymore for the next X steps. To make the circles go "up" and "down" I can try to create a bit of noise each time, and the algorithm will do the rest to move the circles up and down. Also, instead of noise I can try to detect if they are colliding "horizontally" or "vertically" and add a bit of horizontal/vertical movement when a circle with 2 or more collisions has a perfect horizontal/vertical collision.

I don't like this much actually, so well, here I am hehe.

I can't think of something, but I'm pretty sure that there's something that can be calculated with one step, instead of looping the same step multiple times, but I'm really stuck and nothing comes out of my head.

If you want to brute force it, this is a constrained optimization problem where the quantity you're minimizing is the overlap area, the variables are the x and y coordinates of each circle's center, and the constraints are that each center lies within a red circle.

Depending on how you want to count areas inside three or more circles, the formula for the overlap arra can be reasonably simple or a huge mess that gets worse with the number of circles.


If a language is X-complete, is its complement is X-complete as well? I'm looking for an information about closure of complexity complete classes.

Is it true that any language, if the language is X-complete, then its complement is X-complete? Why?

I was thinking that it has to do with accepting states in Turing Machine. You should just switch them so the complexity should be the same but I'm not sure.

I was thinking that it has to do with accepting states in Touring Machine. You should just switch them so the complexity should be the same but I'm not sure.

That argument does not always work. You are probably thinking of the proofs that REG and R are closed against complement.
Note how the same technique alread breaks down for CFL; it's not that easy for NPDA (or, in fact, for any non-deterministic automaton model). Also, we know that RE ≠ co-RE so the technique does not even work for all deterministic models.

This leads me to this answer: the flip-final-state technique works for membership in some deterministic classes; I'm not sure if completeness then works out as well, but my gut feeling is yes.

The technique is unlikely to work even for membership in nondeterministic classes. As a matter of fact, we do not know if NP = co-NP and, as a consequence, we do not know if NPC = co-NPC.
And, of course, REC ≠ co-REC.

Another thing to keep in mind is that the notion of completeness depends on the type of reduction you consider. For instance, above mentionen open question about co-NPC and NPC applies only to Karp reductions; under Cook reductions, co-NPC = NPC (see e.g. here).


How do I show that whether a PDA accepts some string w is decidable? or undecidable? Currently studying for an Automata Theory final and can't find an answer to this question anywhere.

Can you simply let w = w!w and show that it is undecidable that way? Like this here: How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

Or do I have to show decidability for arbitrary string w.

Thanks

Given a PDA and a string $w$, there are several algorithms that decide whether the PDA accepts $w$. In fact, for a fixed PDA, such algorithms run in time $O(|w|^3)$ or less. The most well-known algorithm is the CYK algorithm. Although CYK expects the language in the form of a context-free grammar rather than in the form of a PDA, there is an algorithm that converts a PDA to a context-free grammar generating the same language.

I expect every decent textbook on automata theory to contain a proof that the acceptance problem for PDAs (given a PDA and a string, determine whether it accepts the string) is decidable, say along the lines above.


Memory address of variable after reassignment When a local variable is reassigned a different value/object, does its position/address change in the stack?

"Local variable" is a concept in the source language. Some target languages have the concept (e.g. virtual machines with dictionary-based scopes), but many do not. Since you're using Java, let's look at the JVM.

A local variable cannot be accessed by other methods (e.g. you can't pass a variable by reference like you can in C++ or Fortran), and cannot be accessed by other threads. This gives a Java compiler (and a JVM implementation, for that matter) a lot of freedom about what to do with it.

JVM code has two "local" areas where it may store data: the operand stack and the local variable array. If you want to read along, this is covered in section 2.6 of the JVM specification. As the names suggest, the operand stack is organised like a stack (mostly push and pop-type operations), and the local variable array is organised like an array (dereference-type operations).

The JVM is designed so that a compiler can emit code where every local variable has one exactly entry in the local variable array. To use the value, the compiler would emit code to transfer a value from the local variable array to the stack (the instruction is called "load"; there are variants for variables of different types, but we'll ignore this complication for now), and to write a value to the variable, there is a corresponding "store" instruction which transfers a value from the stack to the local variable array. Section 3.2 of the specification covers this.

The reason why the JVM is designed with this in mind is that it allows for very simple compilers. However, this is not the only possible way to generate code for the JVM.

A local variable cannot be accessed by another method (e.g. you can't pass it by reference like you can in C++), or on another thread. So the compiler has a lot of freedom about what it can do with one.

If a variable is extremely short-lived, for example, it may not need an entry in the local variable array. Consider, for example:

for (int i = 0; i < 10; ++i) {
    int x = f(i);
    g(x,x);
}

A simple way of compiling the body of this loop might be something like this.

// x = f(i);
iload i    // push i onto the stack
invoke f   // pop the argument, call f, and then push the return value on the stack
istore x   // pop the stack and store the value in local variable x
// g(x,x);
iload x    // This probably doesn't need to be explained, right?
iload x
invoke g

(Note that this isn't actually JVM bytecode. The JVM uses slot numbers in the bytecode stream, not names, and also has different "invoke" instructions depending on what "f" actually is; it might be a static method, or an interface method, or one of a number of other things. Nonetheless, this should give you the basic idea.)

The variable x doesn't really need to be stored in the local variable array. When this method calls the method f(), the return value is pushed onto the operand stack. Invoking the method g() requires two values to be on the top of the operand stack, representing its arguments. The JVM has an instruction (called "dup") which duplicates the value on the top of the operand stack, so the body of this loop could be compiled as:

iload i
invoke f
dup        // Duplicate the top value on the stack
invoke g

In fact, in this simple example, the compiler may not need to allocate local storage for i, either.

There are lots of other possibilities. The compiler might reuse local storage slots for local variables whose lifetimes don't overlap, or it might assign different locations to the same variable for different parts of the code; this is known as live range splitting. In a sense, the distinction between the operand stack and the local variable array when compiling for the JVM is very like the distinction between registers and the stack when compiling for a physical CPU, and many of the same ideas carry across.

Now, there are a few reasons why a compiler might not want to go to all this trouble.

First off, it can be a lot of work. Optimal register allocation is a formally unsolvable problem, although for some reasonable definitions of "optimal" it's NP-complete. Nonetheless, for stack machines like the JVM, very simple techniques work in practice.

Secondly, chances are good that if this is performance-critical code, it will be JIT-compiled anyway, and so many of these optimisations will be done by that part of the JVM implementation.

Thirdly, it complicates debugging. If a variable can be stored in more than one location, then the debugger needs to know where to find the value any point in the program. If the reason why you're optimising local variable storage is to reduce the size of the class file, chances are good that it won't help, because what you gain in the number of instructions you will probably lose in debugger metadata.

This is one reason why software projects often use "debug builds" during development.

One final thing: I've been talking about basic types like integers here, but one additional complication in optimising the storage of local variables is how it interacts with the garbage collector, since the garbage collector needs to know what heap objects are referred to by local variables.

Garbage collection is a more advanced topic, and you didn't ask about it, so I won't go into the details. It doesn't affect how a Java compiler would compile to JVM bytecode, but it may affect the design of the JVM implementation. Once again, a local variable can't be accessed by other methods or other threads, so this gives the JVM implementation a lot of freedom on how it can let the garbage collector know what is live and what isn't.


Why larger input sizes imply harder instances? Below, assume we're working with an infinite-tape Turing machine.

When explaining the notion of time complexity to someone, and why it is measured relative to the input size of an instance, I stumbled across the following claim:

  [..] For example, it's natural that you'd need more steps to multiply two integers with 100000 bits, than, say multiplying two integers with 3 bits.

The claim is convincing, but somehow hand-waving. In all algorithms I came across, the larger the input size, the more steps you need. In more precise words, the time complexity is a monotonically increasing function of the input size.

  Is it the case that time complexity is always an increasing function in the input size? If so, why is it the case? Is there a proof for that beyond hand-waving?

Is it the case that time complexity is always an increasing function
  in the input size? If so, why is it the case?

No.  Consider a Turing machine that halts after $n$ steps when the input size $n$ is even, and halts after $n^2$ steps when $n$ is odd.

If you mean the complexity of a problem, the answer is still no.  The complexity of primality testing is much smaller for even numbers than for odd numbers.


What is different between "Arithmetic Calculation" and "Calculation" in computer science? What is different when you say "Arithmetic Calculation" and "Calculation" in the context of the computer science?

The "arithmetic" in the former seems needless to me since all calculations are arithmetic.

Is there some meaning that is enhanced by adding "arithmetic" in this case?

Thank you in advance.

"Arithmetic calculations" are those involving addition, subtraction, multiplication and division of numbers. eg (2+13)/5

There are also "algebraic calculations"  eg Find y such that y + 2x = 13 and more.


Mathematical conjectures equivalent to the halting of a Turing machine This question is about whether every mathematical theorem can be reduced to the question of whether a single Turing machine halts. In particular, I'm interested in conjectures that are currently unproven.

For example: Wikipedia says that it's currently unknown whether there are any odd perfect numbers. Since it's decidable whether a given number is perfect, one could write a Turing machine that checks each odd number in turn and halts if it finds one that's perfect. (This Turing machine does not take any input.) If we knew whether that Turing machine halts, then we would know whether the conjecture is true, and vice versa.

However, as another example, what about the twin primes conjecture? It's decidable whether a given number is the first prime in a twin pair, but in this case we can't just halt when we find the first one, because the question is about whether there are an infinite number. It's not clear to me whether it's possible to make a Turing machine that halts if and only if the twin primes conjecture is true.

We can surely make a Turing machine that halts if and only if the twin primes conjecture is provable within Peano arithmetic or some other formal system, but that's a different question, since it might be true but not provable in the particular system we choose.

So my questions are

Is it possible to make a Turing machine that halts if and only if the twin primes conjecture is true? (And if so, how?)
Is it possible, in general, to make a Turing machine that halts if and only if some given mathematical statement is true? Can this Turing machine be constructed algorithmically from the formal statement?
If it's not possible in general, is there some way to classify mathematical statements into whether they're equivalent to the halting of a single Turing machine, or a turing machine with an oracle, etc.? If so, is this classification decidable for a given statement?

Your question is answered by the arithmetical hierarchy. The existence of an odd perfect number is a $\Sigma_1$ statement, and so you can test it using a $\Sigma_1$ machine, which halts iff the statement is true. The twin prime conjecture is a $\Pi_2$ statement, and so you can construct a TM with access to the halting oracle which halts iff the statement is false.
In a strict logical sense, you can always make a Turing machine that halts iff statement $\phi$ holds:

If $\phi$ holds, then take a machine which halts.
If $\phi$ doesn't hold, then take a machine which doesn't halt.

To see that this construction is valid, consider the logical form of your statement:
$$ \forall \phi \exists T . \phi \Leftrightarrow T\text{ halts}. $$
You can clear this confusion up by asking a slightly different questions:

What is a set of statements $\Phi$ such that there exists a Turing machine which halts on $\phi \in \Phi$ iff $\phi$ is valid?

Above I have indicated that $\Sigma_1$ statements form such a set.


Using Amdahl's law how do you determine execution time after an improvement? Speeding up a new floating-point unit by 2 slows down data cache accesses by a factor of 2/3 (or a 1.5 slowdown for data caches).  If old FP unit took 20% of program's execution time and data cache accesses took 10% of program's execution time, what is the overall speed up?

I solved this problem using amdahl's law:

FeFP = floating point enhanced fraction = .2

FeDC = data cache access enhanced fraction = .1

SeFP = floating point enhanced speedup = 2

SeDC = data cache access enhanced speedup = 2/3

Speedup overall = 1 / (   (1 - FeFP - FeDC)   +   FeFP/SeFP   +    FeDC * SeDC    )

= 1 /  (   (   1 - .2 - .1  ) + .2/2 + (.1) * (2/3)   )
 = 1.154.

I hope I did this correctly, but I'm confused about the next part asking what percentage of execution time is spent on floating point operations after implementing the new FP unit?

I know that T[improved ] = T[affected] / improvement factor   + T[unaffected]

But I'm unclear how to use it in the context of this problem.  Would appreciate all / any advice.

Since the FP speedup  slows down  the cache by a factor of $2/3$, the cache is "sped up" by $3/2$. Hence the overall speedup is

$ S = \frac{1}{0.7 + 0.2/2 + 0.1 \times \frac {3}{2}} = 1.05 \equiv 5\%$

The execution times now have the ratio: $0.7:0.1:0.15$ for remaining operations:FP:cache. The percentage time spent on FP now is $\frac{0.1}{0.7+0.1+0.15} = 0.105 \equiv 10.5\%$.


Finding the total capacity of two communication channels I have the transition matrices of two communication channels. I am able to find the capacity of each by performing an optimization calculation, however I need the total capacity of the two channels. The channels are not weakly symmetric so I don't think I am able to simply add the two capacities. I think what I need to do is perform the optimization calculation over the combined channels but I'm not sure how to do this. I think I need to construct a transition probability matrix but I'm not sure how to go about this. If anyone can give some advice on this I'd be grateful.

Thanks

If the channels are not coupled (i.e., their effect on the input is independent of each other) then their combined capacity is the sum of their individual capacities. See for example Wyner, Capacity of Product of Channels, who also considers the converse.


Origins of the term "distributed hash table" I am currently researching for my diploma thesis in computer science with a topic in the area of distributed hash tables. Naturally, I came to the question were the term distributed hash table came from. (I know it is not rocket science to just derive it from distributing a hash table, but somebody somewhere must have come up with it).

Most papers I read referred to the original paper on consistent hashing and one of the first algorithms making use of it (e.g Chord). I know that there was a lot of research on distributed databases in the 80s, so I figure that the term, or maybe the idea behind it, should be older than ~15 years.

The motivation behind this question is that knowing an earlier date and maybe another term for a similar idea would possibly widen the range of useful information I could gather for my research. For example, what have others done that is similar to what I want to do and where have they failed. Etc. etc.

I tried to find more on this subject using Structured Overlay Networks as a search keyword, but the resulting definitions/papers are also quite young, which leaves me with the impression that the research topic might not be so old after all.

Does anybody of you know of earlier research (maybe pre-90s?) in the topics of distributed hash tables and/or structured overlay networks? I'd be glad to hear some keywords which could lead me to more historic papers.

The term can at least be traced back to a publication by Carriero, Gelernter and Leichter from 1986: Distributed Datastructures in Linda[Lin86]. The paper attributes the term to Rob Bjornson (which I believe to be this guy), but only cites personal communication as their mean of learning the term. [Lin86] also refers D. Gelernter: Dynamic global name spaces on network computers. (1984), which is said to propose an implementation. I didn't find the paper, so I can not say if this is true. Another report (which I didn't find as well) by Leichter is said to discuss the implementation further: Implementing the Unimplementable -- Algorithms for Linda's Tuple Space.

The source in Linda seems to be a dead end, but was the oldest source of the term that I could find. I think it could be attributed with the term, but I may be confuted. If we assume that Bjornson came up with the term, at least the time frame would be fitting. Bjornson started his work in 1984, so if he is attributed with the term, the term's origin would neatly fit into the time were the Linda papers above were written.


Given a truth table, force a contradiction Suppose I have a formula, and a lying witness is attempting to make it evaluate to False.

  Given a truth table $c(F_1,…, F_n)$, how could you force a lying
   witness to contradict herself?

A contradiction is simply when the witness's statements are logically impossible; i.e. that $x_1,x_2$ are each True, but $x_1 \space AND\space x_2$ is False.

How can I characterize the set of all formula for which I force the witness to contradict herself?
What complexity class does this problem fall in?

It appears the question that you are asking is:

  What is the set of formula for which a witness attempting to prove the formula false will always fail?

That is, you are asking whether a formula is valid: whether it is true for every interpretation. A formula is valid if and only if its negation is unsatisfiable, which according to this resource is Co-NP complete.


Counting the number of words accepted by an acyclic NFA Let $M$ be an acyclic NFA.

Since $M$ is acyclic, $L(M)$ is finite.

Can we compute $|L(M)|$ in polynomial time?

If not, can we approximate it?

Note that the number of words is not the same as the number of accepting paths in $M$, which is easily computable.

Let me mention one obvious approach that doesn't work: convert the NFA to a DFA (which will also be acyclic), then count the number of accepting paths in the DFA.  This doesn't result in a polynomial-time algorithm, since the conversion can cause an exponential blowup in the size of the DFA.

Here's one approach that I expect should give you a multiplicative-factor approximation, with polynomial time running time.
Let $L$ be a regular language that is a subset of $\{0,1\}^n$, e.g., $L=L(M) \cap \{0,1\}^n$.  We will try to compute the approximate size of $L$.
At a high level, our approach to approximate $|L|$ will look something like this:

Pick a fraction $p$, where $0<p<1$.

Choose a regular language $R$ such that, roughly speaking, $R$ is a random subset of $\{0,1\}^n$ of size approximately $p2^n$ (i.e., $|R|\approx p2^n$).

Check whether $L \cap R$ is non-empty.  Note that this check can be done in polynomial time.

Repeatedly perform steps 1-3 for various values of $p$.  This gives you some information that will let you approximate $|L|$.
In particular, if $|L|=m$, then we'd expect
$$\Pr[L \cap R = \emptyset] = (1-p)^m \approx e^{-pm}.$$
So, if you happen to choose $p=1/m$ and repeat steps 1-3 a bunch of times, you should expect to see an empty intersection about 37% of the time.  If you see an empty intersection significantly more often then that, then increase $p$ and try again.  If you see an empty intersection significantly less often then that, you might decrease $p$ and try again.
In this way, using something like binary search, you should be able to approximate $|L|$ to within a multiplicative approximation factor.
You'll still need to pick some way to choose $R$ so that it is regular but also behaves like a random subset.  There are many possibilities, but one might good way might be to choose a random 2-universal hash $h:\{0,1\}^m \to \{0,1,2,\dots,k-1\}$, pick $y \in \{0,1,\dots,k-1\}$ randomly, and let $R=\{x \in \{0,1\}^n : h(x)=y\}$.  Choosing $k=\lceil 1/p \rceil$ gives you a random set $R$ of approximately the right size, and because $h$ is 2-universal, all of the mathematics above should work out properly.
This should solve your problem for the case where all strings in the NFA have the same length, say $n$.  If they have varying lengths, then you can handle each possible length separately.  Since $M$ is acyclic, the maximum lengths of any string in $L(M){}$ is at most the number of states in $M$, so this does not increase the runtime too much.
(This construction might remind you of the Valiant-Vazirani theorem about unambiguous SAT.)


Complexity of All-SAT All-SAT is the problem of enumerating all satisfying assignments of a boolean formula.
All-SAT is different from #SAT, where it suffices to find the number of satisfying assignments without enumerating them.
Is the computational complexity of All-SAT known, or is this an open problem?
In this CS Theory question, some solvers for All-SAT are discussed, but the papers do not seem to give complexity results.

You can naively compute ALL-SAT in $2^npoly(n,m)$ time, where $n$ is the number of variables and $m$ is the number of clauses. You clearly need $\Omega(2^n)$ time in the worst case just to write down the assignments (in the case of a tautology). If the strong exponential time hypothesis (SETH) holds, then this is not much harder than SAT itself, so under SETH the complexity of SAT, ALL-SAT, #SAT is the same (up to polynomial factors).
Moreover, without SETH you can claim that given access to a $\#SAT$ oracle, you can output all satisfying assignments in time $k(\varphi)poly(n,m)$ where $k(\varphi)$ is the number of satisfying assignments for $\varphi$ (just see if the number of satisfying assignments changes when substituting $1$ or $0$ to some variable $x_i$). This also shows that in some sense ALL-SAT is not much harder than $\#SAT$.


Problem with forming a context-free grammar describing a language I've been trying for hours to figure out, how to form a CFG describing this language $L$:
$$L=\{ w\in\{a,b\}^* \mid w\text{ is of the form }a^nxb^{n+2}\text{, where }x\text{ is a string of length }3\text{ in }\{a,b\}^* \}.$$

The problem I'm having is related to the first $n$ of $a$'s. I can't wrap my head around how can this be described properly, since the $x$ can also contain 3 $a$'s.

This is my current solution. It does not work because it doesn't take the $n$ $a$'s to the front.

A -> aB | bB
B -> aC | bC
C -> aD | bD
D -> bE
E -> bF
F -> bF | _

$S \to aSb \mid Abb, A \to aaa \mid aab \mid \ldots \mid bbb.$ That's it.
First create an equal number of $a$s and $b$s with $S$. Eventually go to the $Abb$ rule creating two extra $b$s and then terminate with $A$ to any string of length $3$.


Psedu-polynomial Time : Conflict with the definition of input size From wikipedia

  In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required to represent it) and the numeric value of the input (the largest integer present in the input). In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length.

From this SO post that was very helpful.

  An algorithm runs in pseudo-polynomial time if the runtime is some polynomial in the numeric value of the input, rather than in the number of bits required to represent it.

And this MIT OCW lecture on the knapsack DP running time and definition of pseudo-polynomial time.

They are all talking about the same thing in that a running time is pseudo-polynomial when it is a multivariate polynomial of $(x, k)$ where $x$ denotes the size of the input and $k$ is some integer(numeric value) involved. Since $k$ is often exponential in $x$, pseudo-polynomial time is not necessarily polynomial time in $x$, the number of bits needed to represent the input. Mathematically, $k = \Theta(2^{x})$, 2 is replaceable by a constant.

This works absolutely fine when we have a numeric value $k$ as the input with running time $\Theta(k)$. Then $x = \Theta(\log k)$ and we have running time $\Theta(2^{x})$. Everything is clean.

And then I start to see more complicated issues in other algorithms. For example, in the knapsack case, let $N$ denote the number of things or objects in the input. As described in the MIT video, the input is $x = \Theta(NlogS)$ and the running time is $\Theta(NS)$. The instructor describes that since $S$ is exponential in the input size $\log S$ (the number of bits needed to represent the numeric value), we can see how knapsack running time is not polynomial time. $\log S$ is only a part of $x$, so I don't see how $\Theta(N\cdot 2^{\log S})$ is exponential in $\Theta(N\log S)$. How is running time expressed in the form $O(c^{x})$ where $c$ is a constant?

Something similar happens for counting sort running time. The SO post gives running time $O(N + k)$. It gives the same logic as above to say that the running time is exponential in the input size $\log k$. But to me it seems like $x = \Theta(N\log K)$ since the input is a list of $N$ things with the maximum value $k$. I don't really see how $O(N + k)$ can be exponential in $x$ just because $k$ is exponential in the number of bits needed to represent it, since $\log k$ is definitely not $x$, only a part of it. Same thing: running time doesn't seem exponential in $x$, rather only in $\log S$.

So either I am still not getting what it means to have exponential "length of the input" is or there is some conflict with how people define length of the input. MIT video defines input size similar to how I think of $x$ while many other sources have a different opinion it seems. I see it as the total number of bits needed to represent the whole input, but some analysis just sees it as the number of bits needed to represent a numeric value that is only a part of the whole input. Is running time exponential in the input size if it is exponential in the size of a part of the input or the whole thing?? Please clarify!!

First, the size of the input is the number of bits required to represent the input. When talking about complexity, we often assume that our input is represented as some bit-string.

For the knapsack case, when we have $x= \Theta(N\log S)$ and running time $\Theta(N\cdot2^{\log S})$, we say that the algorithm is exponential in the size of the input, as $\Theta(N\cdot2^{\log S}) = \Theta(N\cdot2^{(N\log S)/N}) = \Theta(N\cdot 2^{x/N})$. For fixed $N$, the latter formula is exponential in $x$. However, when we fix $S$ instead, the formula is linear in $x$ (which then is $\Theta(N)$). Since we often do not assume bounds on $S$ in the general knapsack problem, we can consider the formula exponential.

A similar analysis can be done for the case of counting sort.

So, in summary, although the length of the input is indeed the full encoding of the input (usually as a bit-string), this doesn't change the fact that if you encode a number $N$ in your input $x$ with $\log N$ bits alongside perhaps other things, $\Theta(N)$ will be exponential in $x$.

Finally, let me make some comments on pseudo-polynomial time. Personally, I think that both the definition on Wikipedia and in the SO post lack generality and clarity. I prefer to take the definition alluded to in this answer: An algorithm is pseudo-polynomial if it is polynomial only in a specific encoding, such as unary. This implies the definition given on Wikipedia, as the unary encoding on the number $N$ has size $N$, but the binary encoding has size $\log N$.

I prefer the definition above, as it shows a bit more what is going on: it matters what sort of input encoding we use whether our algorithm is polynomial, which explains the name. The fact that this occurs precisely when we have a number in the input is a nice corollary, but hides a bit too much and is probably a reason for your confusion.


Longest subarray with at most two different values - Runtime complexity for a DP solution Consider the problem of finding, for a given input array, the longest subarray with at most two different values.

For example:

Input: [3,3,3,1,2,1,1,2,3,3,4]
Ans = 5, the longest subarray would be [1,2,1,1,2].

Input: [1,2,3,2,2]
Ans = 4, the longest subarray would be [2,3,2,2].

Below is dynamic programming solution to this problem (in Python, hopefully it's easy to read) using a sliding window that holds a "valid subarray" (the subarray of elements between indices i and j always holds two values at most).

I read on e.g. LeetCode that this solution has a runtime complexity of $O(N)$ where $N$ is the length of the input array, but that's not immediately clear to me since we have two nested loops with $i$ and $j$ and $0\leq i\leq j\leq n$.

Why is the worst-case runtime complexity of this solution $O(N)$ and not $O(N^2)$?

Here's the DP solution in question with those nested loops holding a subarray between $i$ and $j$:

    def longest_subarray_holding_two_diff_values (input_array):
        ans = i = 0
        count = collections.Counter()

        for j, x in enumerate(input_array):
            count[x] += 1

            while len(count) >= 3:
                count[input_array[i]] -= 1
                if count[input_array[i]] == 0:
                    del count[input_array[i]]
                i += 1
            ans = max(ans, j - i + 1)
        return ans

Here is how the sliding window algorithm works (unfortunately, I don't understand your code, so can't say whether this is the same algorithm).

We keep track of two pointers $i,j$, with the following properties: the subarray $A[j],\ldots,A[i]$ contains exactly two values, and it is maximal with respect to $j$ (that is, either $j = 0$ or $A[j-1],\ldots,A[i]$ contains three values). We also keep track of the two values in question $a,b$, and of their last appearance $k_a,k_b$. Finally, we keep track of the longest valid subarray seen so far.

In the initialization phase, we scan the array until we see two different values; if the array is constant, then the answer is the length of the array.

At steady state, we take a peek at $A[i+1]$. If $A[i+1] \in \{a,b\}$, we update $k_a$ or $k_b$, and simply increase $i$. If $A[i+1] \notin \{a,b\}$, then we do two things. First, we update the value of the longest valid subarray seen so far (comparing it to $j-i+1$). Second, suppose that $A[i] = a$; then we set $j = k_b+1$, set $b = A[i+1]$, set $k_b = i+1$, and increment $i$.

Finally, when reaching $i = n$, we update the value of the longest valid subarray (comparing it to $j-i+1$), and output the result.

As you can see, this algorithm performs $O(1)$ operations per iteration, so runs in $O(n)$ time.