texts: Why is backpatching needed during intermediate code generation?

texts:
In compiler design, control-flow statements are translated to sequences of three-address-code (3AC) instructions a lot of which are jump statements. A 3AC instruction of the jumping type  could be an unconditional jump in the form of a goto statement with a target label as its argument, such as

  goto L1

or it may be a conditional jump in the form of an if statement, as in

  if a < b goto L1

Now when the compiler generates a 3AC jump instruction, the target label is available to it in the form of an inherited attribute ( which I assume is a pointer to an object/structure and so we could think of it as a pointer to a variable ).

Now, the labels passed to say, an if-else statement as inherited attributes would also be then attached to certain target instructions after the if-else construct that used those labels has been translated.

Suppose, a label L1 has been used a lot of times before in constructs that have now been  translated. Now suppose that label has to be attached to say a target assignment statement (the next instruction to be emitted) whose index is in the array of instructions is 137 (because there are 137 3AC instructions already stored in the quadruples array). Then at this point of time the variable L1 would get the value 137 and so all the earlier uses of L1 would also now get the value of L1 (because the variable pointed to by them now gets a value).

And so in this way we have translated control-flow statements in one pass and there is no need for backpatching to reduce the number of passes further.

I don’t understand why what I just wrote wouldn’t work and without backpatching two passes would be required to attach labels to their correct instructions.


texts: Look Ahead buffer vs Translation Look aside buffer

texts:
I know that Translation look aside buffer is used for address translation in  paging to achieve better performance.

I came across term called Look Ahead buffer in a document which said it implements Temporal locality.

I tried searching for Look Ahead buffer's but could not get any significant data.

Please help


texts: Maximum number of different substrings in big string

texts:
I'm trying to find the maximum number of different substrings of string consisting only of lowercase letters 'a' - 'z', if the length of string can be up to $5000$

Firstly, I was thinking that the number of substrings is $\frac{n\cdot(n-1)}{2}$ but then I noticed that a lot of the substrings will be the same, and also because of the length of the string of most $5000$ we cannot put all the possible strings with length 3 for example.

What is the maximum number of different substrings we can get in one string of length $5000$


texts:
Is there a difference between the set of quantum gates that are:

"universal" in the sense that you could calculate anything in BQP with a polynomial number of gates,
"universal" in the sense that you could approximate any arbitrary "gate" (unitary transformation) on a set of qubits?

And if so, what is the proper terminology to distinguish between these? (Or maybe it is exclusively used in only one of the above meanings?)

I believe these are at least different (but maybe the second implies the first). For example, it is my understanding that both of these sets:

Toffoli and Hadamard gates
CNOT gates plus all single qubit gates

are universal in the first sense, yet the first set cannot make phase shifts gates from the later. So Toffoli and Hadamard gates cannot be universal in the second sense.

Does any set meeting the second sense of universality automatically satisfy the first as well (or can some sets so inefficiently approximate calculations that they are not useful for modelling BQP)?


texts:
I am confusing on completing one epoch, I am using Single Layer Feed Forward neural Network approach. Lets suppose i have a data of OR Gate:

X1  X2   Target
0   0    0
0   1    1
1   0    1
1   1    1

Now we initialize weights (w1 and w2 with 0) and bias 1, it satisfy our first condition  0   0   0 with delta rule (T-O=0) but when we use same weight and same bias with 0  1  1 this row not satisfy with (w1 = 0 , w2 = 0, b= 1) so we change our weight and bias values, now my question is:

We changed value on 2nd row, now we have new weight values and bias value, do we need to check the third row which is 1  0  1 with new weight and bias value or with old one which is (w1=0, w2=0, b=1) ? and if we check 2nd row 3rd row and 4th row with new values and it satisfy 2nd 3rd and 4th row with new value, does this complete our 1st epoch ? but how because we didn't check the first row with new value.


texts: Run time of recurrence with five uneven calls

texts:
I am trying to figure how to find an upper bound for the running time of a given recurrence relation (without proving the bound) using the Iteration method. The recurrence is:

$$T(n)=2T\left(\frac{n}{5}\right)+3T\left(\frac{n}{10}\right)+n$$

I tried to iterate over it and got:

$$\begin{align}
T(n)& =2T\left(\frac{n}{5}\right)+3T\left(\frac{n}{10}\right)+n\\[0.5em]
& =2\left(2T\left(\frac{n}{25}\right)+3T\left(\frac{n}{50}\right)+\frac{n}{5}\right)+3\left(2T\left(\frac{n}{50}\right)+3T\left(\frac{n}{100}\right) + \frac{n}{10}\right)+n\\[0.5em]
& =10T\left(\frac{n}{25}\right) + 6T\left(\frac{n}{50}\right) +9T\left(\frac{n}{100}\right)+\frac{7n}{10}
\end{align}$$

And couldn't know how to continue from here, any hints?


texts: Log space reduction from STCONN to CYCLE

texts: I read this post: Showing Cycle is NL-complete?, but I am not sure why the reduction is log space, as it requires keeping track of the new graph, which has $n^2$ nodes.


texts:
Lately I've been toying with an automatic solver for the Android/iPhone game Flow.

In this game, you start with several pairs of squares on a grid, and you have to connect each pair, without crossing the paths, and by using every square on the grid. Here's a simple 7x7 example (the hardest boards in the game are 11x13).

Beginning:

Finished:

In most cases, a few simple rules can all but solve the problem. For example, if a node only has one uncovered exit, it must extend that way, and if extending in a direction would make a part of the board unreachable, then that move is forbidden. But is there a more general way? I've been trying to figure out if it is a specific case of a general graph algorithm, perhaps some kind of Path Coloring.

Note that the game presents other variants of the problem, such as a hexagonal grid, and 'warps' that connect squares on opposite sides of the board. Also, as far as I can tell, there is only ever one correct solution. I'd also be interested in how they can generate the starting positions.


texts: find separate pairs of points with minimal total distance

texts:
I am looking for suitable algorithm how to solve the following problem.

For finite set $S \subset \mathbb{R}$ ($|S| = N_{S}$) we need to find its disjunctive separation $S = A \cup B$ ($A \cap B = \emptyset$) on two ordered sets and assignment $\pi$ between elements of these two sets, where the following conditions must be fulfilled:

$|A| = |B| = N$ where $N = \lfloor N_s/2 \rfloor$
$s_k \in S$ where $k = 1,2, ...,N_s$
$a_i \in A$ and $b_j \in B$ where $i,j = 1,2, ..., N$
$\sum_{i=1}^{N}|a_{\pi(i)} - b_i| \to min$

In other words, I am looking for method how to find set of separated pairs $[a_{\pi(i)},b_i]$ assignments.

Example:
$$S = [3.0, 2.1, 0.9, 2.9, 1.1], N_s = 5, N = 2$$
then
$$A = [3.0, 0.9]$$
and
$$B = [2.9, 1.1]$$ which produce following separate pairs:

$$[3.0, 2.9], [0.9, 1.1]$$

Note: I am not sure if my problem description is sufficiently rigorous and clear. But I tried do my best.


texts: sorting with noisy but persistent answers

texts:
Given a set of elements $A$ and a probability of noise $p<0.5$. For any two elements $x,y\in A$ we can ask the oracle $O$ to know where $x$ stands w.r.t $y$ (0 means $x$ is smaller than $y$ and 1 means the other way).

The oracle answers correctly with probability $1-p$. The noise is random and independent but persistent in a sense that if the oracle answers incorrectly for one pair $(x,y)$ it will give the same answer if questioned on the same pair again.

Is there any known strategy to sort $A$ with high probability?


texts: What are the differences between NP-Complete and NP-Hard?

texts:
What are the differences between NP, NP-Complete and NP-Hard?

I am aware of many resources all over the web. I'd like to read your explanations, and the reason is they might be different from what's out there, or there is something that I'm not aware of.


texts:
Could an artificial neural network algorithm be expressed in terms of map-reduce operations? I am also interested more generally in methods of parallelization as applied to ANNs and their application to cloud computing.

I would think one approach would involve running a full ANN on each node and somehow integrating the results in order to treat the grid like a single entity (in terms of input/output and machine learning characteristics.) I would be curious even in this case what such an integrating strategy might look like.


texts:
I was browsing Agda's stdlib source code, since I was trying to get into it seriously and therefore wanted to know more. I was amazed at that Agda is way more developed than I thought and it's significantly much closer to Haskell than Coq.

However, I was quite a bit panicked when I see some code like following:

toList∘fromList : ∀ s → toList (fromList s) ≡ s
toList∘fromList s = trustMe

It seems there is an observable hole in the system, and it means Agda is not entirely built from ground up by axiomization. Then I saw this,

https://github.com/agda/agda-stdlib/blob/master/src/Data/Colist.agda

data Colist {a} (A : Set a) : Set a where
  []  : Colist A
  _∷_ : (x : A) (xs : ∞ (Colist A)) → Colist A

I took Colist is the same as List in Haskell, allowing optionally infinite length, and from Wiki https://agda.readthedocs.io/en/v2.5.3/language/coinduction.html

  The type constructor ∞ can be used to prove absurdity!

Just as I suspected, optional infinity introduces absurdity. To this point, I felt I was more scared than amazed.

I understand that being practical must come with some trade off. However, Agda is more or less considered as a proof system, arguably more than a progarmming language. There are lots of papers these days are based on Agda. However, a quick code scan has shown holes in many disguises. (Sure Coq also has that, but it's considerably easy to discover: just grep axiom, admit will tell a lot, and Coq supports printing axioms for each lemma.)

Since I am trying to enter Agda, I have no idea what I should expect from it. So the title says all my question: are the system and the results based on it, sound?


texts:
I'm trying to get a better grasp of computation theory, and have a few questions that I can't seem to find great answers too.

Given language L, which is non-recognizable, is L* context free?
Is P countably infinite, and why?
Are all recognizable languages NP-complete?


texts: "Low-High" sort divide and conquer with merge... how small to make the subproblems for good efficiency?

texts:
For a mental exercise, I decided to try out my own simple sorting algorithm which processes an array of integers in any order, and as it passes thru them all, records the highest and the lowest.  So imagine an array of size 10 with elements (9, 2, 4, 1, 6, 8, 5, 3, 7, 0) in that order.  We want the algorithm to sort them into (0, 1, 2, 3, 4, 5, 6, 7, 8, 9).  There are many ways to implement this, but the simplest I found is to use a 2nd array (call it B).  After the first pass thru A, B[0] will become 0 and B[9] will become 9.  Those are the smallest and largest elements in A.  I also have an array of flags telling me which numbers from A I already "plucked" so I will skip over those on any subsequent passes.  For simplicity, I rescan the entire array of 10 elements even on the 2nd, 3rd, 4th... passes to find the lowest and highest remaining pairs from A.  This is obviously a slow algorithm since it is O($n^2$).

So I got this working quickly because it is so simple, however, it is very slow as N (the # of elements in the array to be sorted) becomes large.  For example, if N=1000 vs. N=500, the N=1000 takes 4 times as long.  N=2000 takes 4 times as long as N=1000....

So what I am wondering is why not have the program first break up the array into smaller arrays, sorts those, and then just merge the results into 1 big array.  The question is, what is the optimal final (smallest) size array "chunks" we should work on?  Breaking it up has overhead, but an n squared algorithm can go so much faster operating on small chunks, then merging the results which takes O(N) time.

For example, suppose someone wants to sort 1 million random integers and they pass me an array of those.  I cannot just use my simple algorithm on that, it would take forever and a day.  But is there an optimal way to break it up into pieces, or does that depend on too many things such as the compiler/interpreter, cache memory size...?  Should I just try many different subarray sizes such as 1024, 512, 256... and just pick the best for my computer, timing each one?  I would suspect that if breaking the subarrays too small, the overhead of doing that and merging all the tiny little pieces (such as arrays of size 2) might not be optimal, especially on a slow computer and/or in an interpreted environment (like I am using).

Also I am interested in the time complexity as the big initial array gets chopped into pieces.  For example, with N=1000, I would make 1000 passes on 1000 numbers so 1 million "examinations" (array references) which is O($n^2$), however if I "chop" only once, now I would have 2 * (500$^2$) = 1/2 million + 1 merge, 4 sub-blocks would be 4 * (250$^2$) = 1/4 million but with 3 merges.... What I am thinking is eventually there will be a point of diminishing returns, meaning that chopping any smaller is of no advantage (and may actually slow things down).  Question is, is trial and error the only way to find this point?


texts: Is this an example of a type-0 grammar that is not context-sensitive?

texts:
A type-0 grammar generates a recursively enumerable (RE) language.

A RE language is also known as a semi-decidable language.

A semi-decidable language is a particular kind of undecidable language: If a language is semi-decidable, we can write a method that returns true for each string that is an element of the language; for strings that are not an element of the language, the method may return false or it may loop indefinitely.

Problem: Provide an example of a type-0 grammar which generates a language that is not context-sensitive (i.e., not decidable).

Answer (I think): The following grammar generates this language:

(a+b+) union (infinite a's)

Here is the grammar:

S → aA | bE
A → aA | bB
B → bB | ε | aE
bE → aE
E → aE

A method for recognizing strings in the language generated by this grammar would return true for strings that are an element of a+b+ and would run indefinitely for strings that are not an element of a+b+

I think that this is an example of a type-0 grammar which generates a language that is not context-sensitive (i.e., not decidable).

If I am incorrect, would you provide an example please?


texts:
I was wondering what would be a time complexity of shifting a binary or a decimal number?
For example: 0011, when I shift it left I get 0001.

I was thinking that the time complexity is $\Theta(n)$, because we have to shift every number.

I need it to calculate $m*{b^\frac{n}{2}}$, where $m$ is some number
and $b$ might be 2 (in case of binary) or 10 (decimal).
Therefore instead of multiplication, I just shift to multiply, and therefore complexity is $\Theta(n)$.

Am I correct or is my thinking wrong?


texts: dynamic pseudo-code for simplified coin changing algorithm

texts:
As a homework exercise our professor presented to us a simplified version of the coin-changing problem in which we do not need to minimize the number of coins used or track the number of possible combinations.  Instead we need only to determine if a certain subset of coins of same or varying denomination, equal exactly to, some amount M.

My recursion equation of the problem is as follows:

let k = 0

If ∑ (v1 + v2 + … + vn) = M
    return true

If ∑ (v1 + v2 + … + vn) < M
    return false

Else
    Increment k by 1
    make recursive call on coin subset {v1, v2, … v(n-k)}

The next question is to convert this into pseudo-code that represents a dynamic programming solution to this problem.

I'm a bit stuck.  If you were to make a table of every possible sum {v1 + v2},  {v1 + v2 + v3},  {v1 + v2 + v3 + v4}, etc. You could eventually find a solution but wouldn't that be a much less efficient brute force approach?

I assume the solution would include some implementation of memoization or some way to store and retrieve sums already encountered, but being that the problem is not an optimization problem, I'm having a hard time envisioning a dynamic solution.

Much of the dynamic programming examples that I see suggest iteratively subtracting elements, one item at a time, which is similar to the composition of my recursion equation but I don't see a modification that would make this pseudo code dynamic in nature.

If anyone could please enlighten me, I'd be very grateful


texts: Does Peterson's 2-process mutual exclusion algorithm account for dying processes?

texts:
I think that in Peterson's algorithm for mutual exclusion, if the process first to enter the critical section were to die or be cancelled, the other process would loop forever, waiting to enter the critical section.

In the picture, if process 1 is stopped, the rest of the processes behind process 1 will execute up to where of process 1 is but then loop.

What happens if the process that reaches the critical section first dies before leaving it?


texts: Constructing a Turing machine which decides whether a fixed TM will halt on a fixed input or not

texts:
It is known that the halting problem is decidable for every fixed $M_0$ Turing machine and every fixed $w_0$ input.

My related question would be the following: is it true that for every fixed $M_0$ Turing machine and every fixed $w_0$ input, an $M_{M_0,w_0}$ Turing machine can be constructed for which the possible inputs are $(M, w)$ machine-input pairs, and for the $(M_0, w_0)$ pair, the output is "1" if $M_0$ will halt on $w_0$ and "0" if $M_0$ will not halt on $w_0$? ($M_{M_0, w_0}$ can give false answers for other pairs, it is not demanded that it has to run correctly for every $(M, w)$ pair.)


texts: Minimum spanning tree of multi directed graph

texts:
I have problem of inferring a rooted tree out of a connected simple graph.
The inference can be done by finding its minimum spanning tree, but the result is restricted by additional two types of condition:

There is a known root, which is s in the following example.
We know directions of some edges if they are chosen. These edges are not chosen yet, or the problem becomes a Steiner tree problem.

Note that numbers on edges are their weights. So we will get s -> b -> c -> a if a normal min spanning tree is applied, but the direction of edge ac is wrong. On the other hand, we cannot use Chu–Liu/Edmonds' algorithm for spanning arborescence of directed graphs, because we don't know and cannot infer the direction of edge bc.

We can infer some edges' directions according to the position of the root. For example, in the example, we know s -> b and s -> a.
It seems that the problem can be solved by two steps:

turn the simple graph into a multi-graph. For edges (in the original simple graph) whose directions are unknown, we represent them in a multi-graph using two directed edges between two vertices with inverse directions.
We find the minimum oriented spanning tree of this multi-graph.

Oriented Spanning Tree
In the final section of spanning tree, Wikipedia, oriented spanning tree is mentioned and a paper [levine2011sandpile] is referred. The problem fits the setting. It says:

Given a vertex v on a directed multigraph G, an oriented spanning tree T rooted at v is an acyclic subgraph of G in which every vertex other than v has outdegree 1.

Note that the term "outdegree" is a bit confusing, which I think should be "indegree". But it doesn't matter, because it just restricts the simple subgraph to be a directed tree with root being source or sink.
But it is not clear to me how an algorithm can be implemented according to that paper.

Levine, L. (2011). Sandpile groups and spanning trees of directed line graphs. Journal of Combinatorial Theory, Series A, 118(2), 350-364.
https://en.wikipedia.org/wiki/Spanning_tree


texts: Minimum basis for the nullspace of sparse matrices

texts:
Let $A\in\mathbb{F}_2^{m\times n}$ and denote its nullspace as $V=\{x\in\mathbb{F}_2^m:xA=0\}$. The weight of a basis $B=\{b_1,\dots,b_l\}$ for $V$ is the total weight of vectors in the basis, denoted $|B|=\sum_{b\in B}|b|$, where $|b|$ is the Hamming weight of vector $b\in\mathbb{F}_2^m$. Out of all bases for $V$, some bases have the minimum weight. We call these the minimum bases for $V$.

In general, finding a minimum basis is NP-hard, because it would allow one to calculate the distance of the binary, linear code with codespace $V$. However, given some sparsity constraints on $A$, the problem of finding a minimum basis for $V$ can be easy.

For example, if each row of $A$ has exactly two non-zero entries (two 1s), then a minimum basis for $V$ can be produced in $\text{poly}(m,n)$ time. This is because $A$ can then be interpreted as the incidence matrix for a graph $G$ with $m$ edges and $n$ vertices. Then, the minimum basis problem is equivalent to finding a minimum cycle basis for $G$, a task that can be performed by e.g. Horton's algorithm.

This brings me to my main question. Can anything be said about the time complexity of finding a minimum basis for $V$ when each row of $A$ has exactly three non-zero entries?


texts: How many ways to express N as sum of 2, 3 and 5?

texts:
I've learnt about problems about express N as sum of 2, 3, 5. For examples, if N = 7:

N = 5 + 2
N = 2 + 5
N = 2 + 2 + 3
N = 2 + 3 + 2
N = 3 + 2 + 2

But most of I found on the Internet that the different position is different way to express N (as this link for expressing N as sum of 1, 3, 4). Following that link, I try following DP formula:

    f[0] = f[1] = 0 ;
    f[2] = f[3] = f[4] = 1;
    for(int i = 5; i < 100; i++) {
        f[i] = f[i-2] + f[i-3] + f[i-5];
    }

But it isn't correct, as N = 7, F[N] = 4. So what is the correct DP method for this problem?

Hard version: I also concern about don't care order of way to express N, such as N = 2 + 2 + 3 and N = 2 + 3 + 2 and N = 3 + 2 + 2 will be only count as 1 time.

Note that I'm trying to solve above problem in complexity O(N).


texts: Pushdown automation where number of letter `a` is at least as twice as letter `b` in the word

texts:
I have talked to my friend and he said this is the only place somebody could know how to solve it. It is the only exercise(from around 80) from exam revise I just do not know how to do at all.

Create pushdown automation for
{w: #a(w) >= 2#b(w)}; and simulate it for the word ababaaa

# means number

Does any one of you is fluent enought in automation to solve it?


texts: What is a weighted or probabilistic automaton?

texts:
I'm developing a program that has some entities (things) that are "classified" according to "relevancy". Sort of like search engine (think PageRank).

Therefore, I'm looking to implement an automaton, which I think should handle "value hierarchies". What I mean is that each "next possible state" should have a value that determines how "relevant" it is relative to the state from which are to be moved to it.

Is this called a weighted automaton?
Or a probabilistic automaton?

This is what I want:

(From: http://engineering.flipboard.com/2014/10/summarization/)

To be able to have the states that can be "moved to" have different "relevancy values".

My application reminds of this:

(notice the "sub contexts" centered at the blue texts)

(From: http://shadow.cios.org:2222/www/vcceguide/images/full-screen/vcce-menunew-conceptanalysis-1c3b-tripleconceptnetwork-conceptmenusearch.png)

I think it's an automaton that (in my program) would be going through those "sub contexts" (moving from blue text to blue text, based on user input). But what kind of automaton?


texts: Let $t:\mathbb{N}\rightarrow\mathbb{N}$ be a time constructible function with $t(n)\geq n + 100$. Show that there is no TM $T$ that given the gödel number of another TM $M$, decides wether or not M is time bounded by $t$. Can someone help me with this? I have no clue


texts: Some explanations needed about Negation in Gentzen's Natural Deduction rules

texts:
I'm beginning to have an understanding thanks to some videos relating to "Proposition as Types". But, I don't come from a theoretical CS background, so maybe I'm blocked probably a bit by notation...

Given that I have understood, Conjunction, Disjunction, Implication,

I'm stumbling on Negation:

intro:
[A]
 /\
---
¬ A

elim:
A ¬A    /\
----   ---- .
 /\     D

It comes from an extract of the Gentzen paper during a P. Wadler talk Proposition as Types, and I'm stuck by the meaning of the symbol resembling /\. What is this symbol called, and what is the meaning ?

Moreover, I have no clue about that D (which was not introduced) and . in:

 /\
---- .
 D

Is it anything related to _|_ bottom in Haskell, or else the Void empty type?

All those missing pieces makes me unable to grasp the meaning and how to apply these rules.

EDIT: I was also having difficulties with the Universal Introduction rule and this video covers the topic.


texts: Express XOR with multiple inputs in zero-one integer linear programming (ILP)

texts:
In the below post, it is explained how to express xor of two variables as linear inequalities.

Express boolean logic operations in zero-one integer linear programming (ILP)

Naturally, the xor of multiple variables can be expressed using a sequence of multiple 2-input xors but my question whether there is a smarter way to do it?


texts: Using Myhill Nerode to prove that a language is not regular

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


texts: Using integer programming to find a solution without optimizing it

texts:
Oftentimes I find myself wanting to use integer programming to find a solution to a particular problem, without caring about optimizing a certain variable at all.

I've found that most packages that offer integer programming do not provide this feature.

Is it then correct to assume that maximizing/minimizing a solution is no harder than just finding any solution?

If yes, does it matter what variable you choose to optimize for (considering you really do not care either way)?

If not, why do packages almost never offer to only solve rather than optimize?


texts:
Let $(G,+)$ be an abelian group, $X$ a finite set (of "colors"), and $f:G \to X$ a function such that there exists a subgroup $H<G$ for which $f$ separates cosets of $H$, i.e. $\forall a,b\in G:f(a)=f(b)\iff a+H=b+H$.
Using information gained from evaluations of $f$, determine a generating set for $H$.
This is the hidden subgroup problem, that is solved in abelian groups using a quantum polynomial time algorithm.
In many cases $f$ is actually an homomorphism. So, in fact, the subgroup $H$ corresponds to $\text{Ker}(f)$.
For example, this is true in the cases of factoring, i.e. Shor's algorithm and also in the discrete log problem.
More generally, I am interested in the cases where we can construct a mapping $M:X\times X\to X$ such that $\forall a,b\in G:M(f(a),f(b))=f(a+b)$ (e.g. when $f$ is an homomorphism $(x,y)\overset{M}{\mapsto} x\cdot_Xy$ is the mapping). However, $f$ is not necessarily an homomorphism and $X$ is not necessarily associated with a know group operation either.
Clearly such $M$ always exists, by going through group $G$ using representatives from coset in $f^{-1}$. So, what is really interesting, even when restricting to the abelian case, is whether we can always find such $M$ classically and efficiently. Also, is there a known thing that is described somewhere in this direction?


texts:
What is the run time of the following piece of code in Big-Oh notation? The first loop runs n times in the worst case. But I am having difficulty in finding run time of nested loop which runs V / deno[i] times to be exact. So I think the total runtime would be O(n* V/deno[i])? Please correct me if I am wrong.

int deno[] = {1, 2, 5, 10, 20, 50, 100, 500, 1000};

int n = sizeof(deno)/sizeof(deno[0]);

// Driver program
void findMin(int V)
{
    // Initialize result
    vector ans;

// Traverse through all denomination
for (int i=n-1; i>=0; i--)
{
    // Find denominations
    while (V >= deno[i])
    {
       V -= deno[i];
       ans.push_back(deno[i]);
    }
}


texts: Why do some search trees store all the elements in leaves, while others don't?

texts:
Why do some search trees store all elements in the leaves, while other search trees don't?
One difference that makes is whether a successful search may end up in an internal node.

For m-ary search trees, the former case will need more leaves and more heights than the latter. Is this the benefit of not storing all the elements in the leaves?

Is storing all the elements in the leaves only for looking consistent? Does it have some benefits?
Someone said that

  Contrary to what you said, in the three examples you gave, the internal nodes also contain values.

  In a B+ tree for example, all values are located in the leaves, the internal nodes only contains keys

  "This is interesting only when the data is separated in a key and some other value (as in a database). This allows more keys to go in the internal nodes, limiting the tree depth. When the nodes are on a slow medium, this limits the time needed to go to the data." But I don't quite understand that, because

when we choose to store records in the internal nodes, we don't need to store the actual records in the internal nodes, but can always store with each key a pointer to the actual records, so that we can save space to store more keys. So I don't understand why he said that "This allows more keys to go in the internal nodes".
as mentioned above, I guess storing elements in the leaves rather than also in internal nodes will make the search trees higher, so I don't understand why he said that storing all the elements in the leaves can "limit the tree depth".

For B-trees and 2-3 trees, why do some references define them so that all the elements are stored in the leaves, while other references don't? Note that 2-3 trees are special B-trees, according to Aho's book.

I just found that

the definitions of 2-3 trees and B trees in Aho's Data Structures and    Algorithms store all the elements in the leaves, so that a
successful    search always end up in a leaf

But the examples of 2-3 trees and B trees in Wikipedia and also    in wikipedia and in Sedgewick's Algorithms (also
see the    first picture below) and in CLRS (see the second picture
below) store    only some elements in the leaves, so that a
successful search may end    up in an internal node.

For binary search trees, why all the references define them so that not all elements are stored in the leaves?

I haven't seen any reference that define binary search trees with all elements defined in the leaves, or am I missing it?

Can Huffman trees be viewed as binary search trees where all the elements are defined in the leaves?
Is balancing the only or most important aspect where 2-3 trees improves over binary search trees?

From the above questions, I mentioned that some references define 2-3 trees  so that all the elements are stored in the leaves, while others don't, and within my readings, binary search trees are always defined so that not all the elements are stored in the leaves. Is whether search trees store all elements in the leaves  an important aspect to distinguish between 2-3 trees and binary search trees, as important as the balancing aspect?

Thanks.


texts: ANN - Backpropagation with multiple output neurons

texts:
Can I utilize the backpropagation algorithm in a layered, feed-forward ANN in instances where there are multiple output neurons? If so, how? Links to (somewhat) comprehensible resources would be greatly appreciated, if nothing else.

The background is that I'm working on a simple C program that can create, propagate, and train dynamically sized, layered feed-forward ANNs. For the most part, everything's been going swimmingly. However, I'm having a little trouble wrapping my head around backpropogation. My main concern right now is how to use the backpropagation method for training a network that has multiple output neurons. All the examples/explanations I've found only use one output neuron. I'm assuming this is for the sake of simplicity. But, I'm wondering if, perhaps, this is because the backpropagation algorithm is only designed to works with one output neuron at a time. In other words, it can only be applied relative to one output neuron every time an feed-forward ANN is propagated. This would make sense, as it is known to be among the simplest ANN training methods.

Here are links to my aforesaid resources (or at least, the ones I found intuitive):

http://home.agh.edu.pl/~vlsi/AI/backp_t_en/backprop.html
https://www.youtube.com/watch?v=GlcnxUlrtek
https://www.youtube.com/watch?v=IruMm7mPDdM (I'm actually not entirely certain as to whether or not this explanation accounted for multiple output neurons; if it did, it must've went over my head)

Thanks!


texts: What are the conditions for a NFA for its equivalent DFA to be maximal in size?

texts:
We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in worst case gives us $2^S$ states, if our NFA had $S$ states.

My question is: what is determining the worst case scenario?

Here's a transcription of an algorithm in case of ambiguity:

Let $A = (Q,\Sigma,\delta,q_0,F)$ be a NFA. We construct a DFA $A' = (Q',\Sigma,\delta',q'_0,F')$ where

$Q' = \mathcal{P}(Q)$,
$F' = \{S \in Q' | F \cap S \neq \emptyset \}$,
$\delta'(S,a) =\bigcup_{s \in S} (\delta(s,a) \cup \hat \delta(s,\varepsilon))$, and
$q'_0 = \{q_0\} \cup \hat \delta(q_0, \varepsilon)$,

where $\hat\delta$ is the extended transition function of $A$.


texts: Can exactly one of NP and co-NP be equal to P?

texts: Maybe I am missing something obvious, but can it be that P = co-NP $\subsetneq$ NP or vice versa? My feeling is that there must be some theorem that rules out this possibility.


texts: Does such an algorithm exist? What would the complexity for it be?

texts:
Given an $n \times m$ matrix $A$ where

$m-n=1$
The value of any $A$[$i,j$] is either $1$ or $0$
If $A$[$i,j$] $=1$ then $i<j$

Does anyone know of an algorithm which would run as follows and what its complexity might be:

Starting with the last column, column $m-1$, traverse each index $A[i,m-1]$ (where $0 \leq i < m-1$).
Keep track of all $i$ such that $A[i, m-1] = 1$.
Letting $S = \{i :  A[i, m-1] = 1\}$, determine whether $A[j,k] =1$   for all $j,k\in S$ such that $j < k$.
For each $A[j,k]=1$, add 1 to a counter.
Repeat process for remaining columns $m-2, m-3,\ldots,2$
(no need to do this for column 1, as column 0 will be all 0s).
Return count.

So for example if we have the following $5\times6$ array:

$$
\begin{array}{cccccc}
    0&   1& 1& 0& 1& 0 \\
    0&   0& 1& 0& 1& 0 \\
    0&   0& 0& 0& 0& 1 \\
    0&   0& 0& 0& 1& 1 \\
    0&   0& 0& 0& 0& 1
\end{array}
$$

Then we would start with column 5.

There is a value of $1$ at $A$[$2,5$], $A$[$3,5$] , and $A$[$4,5$], and so we would

Check if $A$[$2,3$] has a value of 1. If it does, add 1 to the counter. It doesn't.
Check if $A$[$2,4$] has a value of 1. If it does, add 1 to the counter. It doesn't.
Check if $A$[$3,4$] has a value of 1. If it does, add 1 to the counter. It does, increase counter.

Repeat this process for columns 4, 3, and 2, and then return the count.


texts: Is persistence a property of a database?

texts:
I was having a discussion in another forum on this topic, and I couldn’t get a satisfactory answer. Originally, a statement was made that a redis data store couldn’t be considered a database because it’s not persisted to disk. I queried that, because I didn’t see why persistence is a required property of a database. I understand a database to simply be some structured/organised data.
So: is persistence a required property of a database, and why?


texts: DNA as software and molecular machines as hardware

texts:
Several scientists view DNA as some kind of software. Chaitin suggests that life is an evolving software. Rothemund, Papadakis, and Winfree showed that DNA self-assembly can be used as a Turing-universal biomolecular system.

DNA holds genetic information and holds the key to the evolution of living organisms. Transcription and translation mechanisms enable living cells to process information encoded in DNA. To that end, transcription and translation are fundamental mechanisms needed to enable the evolution of organisms. Molecular machines (enzymes) carry out these mechanisms by reading the information in DNA and using it to construct proteins.

If we consider molecular machines as Hardware and DNA as software;

  What algorithmic processes can independently produce the molecular machines and matching DNA code which will be executed correctly by molecular machines? How is compatibility guaranteed ( between biological software and hardware )?

Motivation: If such processes are known then we can simulate the origin of life using supercomputers.


texts: MAX-2-XOR-SAT: Why does the special case work?

texts:
I'm a new user so I cannot respond directly to this post here.

I'm confused about the answers to the question, namely that MAX-2-XOR-SAT is in $P$ iff each clause is of the form $(x_i \oplus \neg x_j)$ (or is it $(x_i \oplus x_j)$? There were two different answers). Couldn't you make a simple substitution $\neg x_i \rightarrow y_i$ such that this is always the case, so that you can get the special case always? For example, you could convert, $(x_1 \oplus \neg x_2) \wedge (x_1 \oplus x_3)$, to $(x_1 \oplus y_2) \wedge (x_1 \oplus x_3)$.

Forgive me if there is something obvious I am missing...I'm new to this field.

Thank you!

EDIT

To clear up confusion, I'm asking if a substitution is made for all clauses with a matching variable. Take for example,

$$(x_1 \oplus x_2) \land (\neg x_1) \land (x_1 \oplus \neg x_3)$$

By substituting $\neg x_3 \rightarrow y_3$ we get:

$$(x_1 \oplus x_2) \land (\neg x_1) \land (x_1 \oplus y_3)$$

Where each 2-clause is of the form $(x_i \oplus x_j)$. It seems that in this case it still remains in $P$. Which raises a new question, how do single clauses affect the complexity of the solution?


texts: How to Tokenize a String and Save Each Substring Separately (Independent Names for Each Substring)

texts:
I am given two files one with the name of person and the location that they are from
(Evan Lloyd|Brownsville)
and one with the name and salary (Evan Lloyd|58697) (the line number that you find the employee on in the first file is not necessarily the line number that find the employee on in the second).
The user inputs a location (whole or part). For example if they input "ville" or "Ville" it should include all of the employees in Brownsville, Clarksville, Greenville, etc. I am supposed to join the the name and salary and return them if they are in the city searched for i.e. "ville" or "Ville." I am attempting to use a vector for both of the files
vector(name, address) and vector(name, salary) and later return a vector of a string and tuple (address, (name, salary)) as my output. I don't know how to tokenize the string for example "Evan Lloyd|Brownsville" into the substrings "Evan Lloyd" and "Brownsville" separately (without the |) and save them separately so that I can push both strings into my vector(name, address). How would I tokenize the strings that way or should I try something else entirely?


texts: A notion dual to a product type having a given type

texts:
Consider this class:

class Has record part where
  extract :: record -> part
  update :: (part -> part) -> record -> record

It captures the notion of some product type record having a field of the type part which can be extracted from the record, or the functions on which can be used to update the whole record (in a lens-ish manner).

What happens if we turn the arrows? Following the types and noting that a sum type is dual to a product type, and a "factor" in a product type is analogous to an option in a sum type, we get

class CoHas sum option where
  coextract :: option -> sum
  coupdate :: (sum -> sum) -> option -> option

Firstly, is this line of reasoning correct at all?

If it is, what is the meaning of coextract and coupdate? Obviously, coextract produces the sum out of one of its options, so it might as well be called inject or something similar.

coupdate is more interesting. My intuition is that, given a function f that updates a sum type, it gives us a function that can be used to update one of its options. But, obviously, not every f is fit for this! Consider

badF :: Either Int Char -> Either Int Char
badF (Left n) = n
badF (Right _) = Left 0

then coupdate badF does not make sense where coupdate is taken from CoHas (Either Int Char) Char. One requirement seems to be that the function passed to coupdate must not change the tags of the sum type.

So here's the second question: what's the dual of this requirement in the Has/update case?

My intuition is that it's not as straightforward because Has produces a function and CoHas consumes a function. Things get more symmetric if we consider the rules for the type classes, something along the lines of

update f . update g = update (f . g)
update id = id
extract . update f = f . extract

Now we can actually talk about bad instances of Has producing update functions breaking these rules. But even with this additional constraint, I'm not sure I follow what the laws for the functions that coupdate accepts should be and how one could derive them from such duality-based reasoning.


texts:
I need an algorithm which can do the following:

  Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{R}^2$ for the particles to take so they won't collide.

The list of points for a particle specifies the order in which the particle must visit those points.  All particles start moving at the same time.  The time elapsed for a particle to travel from any prescribed point to the next is constant for every particle regardless of distance.  I'd like to find a continuous trajectory for each particle, so they won't collide (the circles won't overlap).  Ideally, I would like to find the solution which minimizes total path length under the constraint that there are no collisions.

Assume that the distance between the n'th prescribed point of different particles are at least the particle's diameter apart so that there are no unfixable collisions.

My best solution is just making splines for every path, and keeping a record of all the collisions.  I have been reading papers about potentially adding more prescribed points to bend the paths, and 'elastic bands', but I'm not sure exactly how to do it.


texts: Time complexity of quicksort for arrays in increasing or descreasing order

texts:
Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order.

Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using quicksort.

I think $c_1 = c_2$ and $c_1=O(n^2)$? Is this correct ?

I am using the last element as a pivot for each partition.


texts: What is the difference between a module in a monolithic kernel and a server in a microkernel?

texts: I´m not exactly sure what kind of impact these two things have on kernel design. Are servers more flexible because of running in user space, for instance, and does adding a module require a new build of a kernel?


texts:
I have the following algorithm:

func()
{
    for(i=1; i<n; i=i*2)
        print("aa");
}

How can I find Big-Oh using summation?


texts: Complexity of recognizing whether two $\omega$-regular expressions represent the same language

texts: If the complexity of recognizing whether two regular expressions represent different languages is EXPSPACE-complete, then what can be said for the complexity of recognizing whether two $\omega$-regular expressions represent different languages?


texts: How to check equality between any two 2-dimensional arrays (dense matrices) with time complexity less than O(n*m)?

texts:
Here, n = no. of rows and m = no. of columns

Suppose, there are three matrices - A[3][2] : {{1,2},{3,4},{5,6}} ;
B[3][2] : {{1,2},{3,4},{5,6}} ;
C[3][2] : {{2,1},{3,4},{5,6}} .
Here A=B , A!=C and B!=C .

So, task is to check equality between all possible combinations of 2-dimensional matrices from a given set of matrices with time complexity less than O(n^m) .Here the possible combinations are (A,B) , (A,C) and (B,C).

( As part of the solution :

Matrix to matrix comparison is costly .So these matrices have to be converted into 'something' which results less comparison time . I think if I can convert/represent the matrix as a value/string/1-dimensional array , then equality comparison will be less costlier . My question is how to convert/represent ? If it can be solved by hashing how to solve this exactly ? )

NOTE : No. of 2-dimensional matrices and their sizes are not fixed. In my problem scenario no. of 2-dimensional matrices are been generated gradually which can be of any size. Cant predict how many matrices of which size will be generated . Here my main task is to identify all possible equal matrices among the set of all generated matrices . Main idea is - whenever a new 2D matrix generates, check if it has been already generated or not. If yes , we can say 'identical matrices found'; If no , continue checking for other matrices .


texts: Edge incident to cut-vertex not in perfect matching of a graph

texts:
Let G = (V,E) be a connected graph and a ∈ V be an articulation point of G. How can be proved that there is an edge e ∈ G incident with a with the property that e doesn't belong to a perfect matching of G?

Let's say that there are two vertices u,v ∈ G so that the only paths between them go through a. Then there is no edge directly connecting u and v. It means that a has at least 2 vertices(which is pretty obvious) and knowing that the property of a perfect matching is that the degree of any vertex is equal to 1, it means that there is at least one edge incident to a that doesn't belong to the perfect matching. But I'm not sure, is it okay?


texts: Is this grammar really LL(1) while not being LR(1)?

texts:
$S \rightarrow S$, $L(G) = \{\}$

LL(1) analysis:

We estabilish $FIRST(S)$ to be empty and $FOLLOW(S)$ to be $\{\$\}$.
$FIRST(S)$ doesn't contain ε, so the parse table looks like this:

+---+---+
|   | $ |
+---+---+
| S |   |
+---+---+

and correctly rejects any input including ε.

LR(1) analysis:

We start with the initial state 0:

$S' \rightarrow \bullet S [\$]$

calculate its closure:

$S' \rightarrow \bullet S [\$]$

$S \rightarrow \bullet S [\$]$

and the only transition, which leads to state 1 on S:

$S' \rightarrow S \bullet [\$]$

$S \rightarrow S \bullet [\$]$

State 1 has a reduce/reduce conflict.

Now, obviously there must be something I'm missing, since LL(k) grammars are a proper subset of LR(k) grammars. Would anyone care to point out the error?


texts: Intuition on what an attribute grammar can achieve

texts:
I have seen attribute grammars for a small handful of tasks:

Parsing simple arithmetical expressions
Type checking
Checking that a variable is initialized
anbncn (seems to be a favorite toy example)...

and that's about it.

What are some practical uses of attribute grammars outside of the field of compilers?  I've seen CFG's being used in program synthesis, computational biology, computational linguistics, and computational music - are attribute grammars anywhere near as useful?

In addition, I'd appreciate some more theoretical intuition about what kinds of context-sensitive languages can be made parseable using attribute grammars, and what are beyond the reach of such grammars.


texts: If a non-deterministic Turing machine runs in f(n) space, then why does it run in 2^O(f(n)) time?

texts:
Assuming that f(n) >= n.

If possible, I'd like a proof in terms of Turing machines. I understand the reason why with machines that run on binary, because each "tape cell" is a bit with either 0 or 1, but in Turing machines a tape cell could hold any number of symbols. I'm having trouble why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape.


texts: Recommender system - Binary rating adding a condition

texts:
I want to implement a recommender system based on collaborative filtering. Each user will have a set of visualized items (0-1's) and based on that similitude the recommendation will be generated.
In order to develop this, I was thinking of using the Jaccard similarity coefficient (if anyone has a better suggestion please let me know).
But, what if I want to add a condition to the result? For example, if the items are premium will appear first. This should be implemented at the end as a condition or there is another way?
To sum up, there are a set of items and some of them are premium and there are a set of user and each one have a set of visualized items. I want that the recommender system not only takes into account the visualizations but also that there are some items more "important" that has to appear firs (the premium ones).
Thanks in advance.


texts: Algorithm for finding fixed cycles in bipartite graphs in sublinear time

texts:
Does there exist an algorithm that will compute in sublinear time whether a bipartite graph contains a cycle of fixed length? For example given a $K_{3,3}$ graph finding if it contains a cycle $C_4$.

I considered the answer to be no. As a DFS could be used and then compare to see if after a certain traversal we were back at a node we've already visited. That would be $O(n)$ time at best. However, as a counter argument to that, a complete graph will always contain a cycle, and if we know the cycle length then search time should be dependant on the cycle length which would be $O(1)$ or big-oh of the cycle length. If we know whether we're in partition A or B all we have to do is return to the first node since both sets connect to all nodes of the other.


texts: Compactly representing integers when allowed a multiplicative error

texts:
Consider the problem of representing in memory numbers in the range $\{1,\ldots,n\}$.

Obviously, exact representation of such number requires $\lceil\log_2(n)\rceil$ bits.

In contrast, assume we are allowed to have compressed representations such that when reading the number we get a 2-approximation for the original number. Now we can encode each number using $O(\log\log n)$ bits. For example, given an integer $x\in\{1,\ldots,n\}$, we can store $z = \text{Round}(\log_2 x)$. When asked to reconstruct an approximation for $x$, we compute $\widetilde{x} = 2^z$. Obviously, $z$ is in the range $\{0,1,\ldots,\log_2 n\}$ and only requires $O(\log\log n)$ bits to represent.

  In general, given a parameter $\epsilon>0$, what is the minimal number of bits required for saving an approximate representation of an integer in the above set, so that we can reconstruct its value up to a multiplicative error of $(1+\epsilon)$?

The above example shows that for $\epsilon=1$, approximately $\log\log n$ bits are enough. This probably holds asymptotically for every constant $\epsilon$. But how does epsilon affect the memory (e.g., does it require $\Theta(\frac{1}{\epsilon^2}\log\log n)$ bits?).


texts: Is Group Theory useful in Computer Science in areas other than cryptography?

texts: I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot find out where and how to apply Group Theory to other areas in CS, such as algorithms, data structres, graphs, complexity and so forth.


texts:
I want use DFA to describe a sequence of movements in a 2D-space (language will be  the path accepted by automaton in a particular case).

That is a typical modeling problem: how can I encode a sequence of 2D movements in a DFA?

Infact, walking through DFA or NFA seems a process analogous to walk through point of a maps.

A naives example could be: State like point in space coordinate (x,y); and  Transitions with an alphabet of "up, down, etc".
That's direct approach is impracticable beacuse "the number of locations is infinite or simply too many". I'm looking for a better and more efficient encoding.

Are there any study about using regular languages for coding path, or movements?


texts: Stable marriage problem preferential to asking side

texts:
Watching this youtube video: https://www.youtube.com/watch?v=w1leqkpDaRw it described the problem with the stable marriage problem, that the asking side get a better deal then the asked site. Meaning that the result may differ if the woman ask the men instead of the men asking the women.
I have test this and found it to be true, but i can not find any scientific papers on this, so i where hoping that some of you guys might know of one or more?


texts: Pumping Lemma. Why is there a word w in L for infinite languages with n≤|w|≤2n

texts:
The following comment on an other question says that if we have an infinite language L that satisfies the pumping lemma for regular languages then we have a word with n≤|w|≤2n which is in L. (n is the constant in the pumping lemma)

https://cs.stackexchange.com/a/55606/99669

Why is this the case? The lower limit can be explained by the constant of the regular pumping lemma, because in infinite languages there exists a word in L which is longer than n.

But how comes there is an upper limit? The pumping lemma does not say anthing about a upper limit for the words we choose.


texts: Prove that language of possible stack content is regular

texts:
So, here's the problem:

Suppose that $A=(Q,\Sigma,\Gamma,\delta,s,\bot, F)$ is a PDA, let
 $$L = \{ \gamma \in \Gamma^* \hspace{5pt}|\hspace{5pt} \exists_{x,y\in \Sigma^*} \exists_{q\in Q}: (s,x,\bot)\vdash_A^*(q,y,\gamma)\}$$

Show that $L$ is regular.

So far solution has been eluding me, any hints are welcome.


texts:
I am currently reading a couple of papers about event processing. In the context of ordering events, "2g-precedence" is frequently mentioned. I don't know what it is, and I cannot find much information about it. In this paper I was able to find a short explanation that is way over my head, though:

[It is assumed] that the maximum time difference between any
two clocks at the same instant of time is bounded by $\delta$. The
granularity condition states that the granularity of the global
time-base $g$ should not be smaller than $\delta$, $g > \delta$, ensuring
that global clocks do not overlap. A global and total
order of events can be determined if event timestamps are
two or more clock ticks apart, a fact known as 2g-precedence.
If this assumption does not hold in all cases, one has
to face partial ordering of events.

What is a "granularity condition"? What is a "global time-base"? How do clocks "overlap"? In other words, what is "2g-precedence"?


texts: why does the poly-time reduction from dominating set to vertex cover require adding a vertex to every edge?

texts:
I'm trying to understand a poly-time reduction proof from dominating set to vertex cover. If I'm understanding correctly, it goes something like this: suppose we have a vertex cover of size $k$ in graph $G$. Then we construct a new graph $G^\prime$ with the same vertices and edges, except for every edge $(u,v)$ we add a new vertex $w_{uv}$, which has an edge to both $u$ and $v$.
Then, here's the oddest part: it says that if there's some dominating set in $G^\prime$ that includes any of the $w_{uv}$, then we can construct another dominating set, that's at least as good, by replacing that $w_{uv}$ with either $u$ or $v$. That is, we end up not including any of the $w_{uv}$ at all, and thus the dominating set in $G^\prime$ is the vertex cover in $G$ plus any remaining isolated vertices not in the cover.
This raises the obvious question: what's the point of $w_{uv}$ if we're gonna include them and then argue that the original $u$ and $v$ can render them obsolete anyway? The proof in the link above conspicuously does not explain this. If the dominating set of $G^\prime$ doesn't even include $w_{uv}$, and the vertex cover dominates just fine (except for the isolated vertices, which are trivial and have nothing to do with $w_{uv}$), why even add the $w_{uv}$? Why does the proof fail if we never introduce the $w_{uv}$ at all?


texts: A variant of job assignment (scheduling) problem with variable time span

texts:
The problem is a scheduling problem with n jobs and k machines. Each job i can be started at any time, but its duration is not exactly known except a time span interval. For example, a job may take anything from 5 mins to 10 mins. The list of jobs and their duration interval is given to the scheduler and the aim is to minimize the time all jobs would be finished.
In interval scheduling, the job start and end time is given and the length is fixed. Here, the job can start and end anytime (should be done in whole though) but its duration (length) is not exactly known.

I searched the literature for this problem but couldn't find it. Is there any keywords I can use or any reference for this problem? Is it well-defined?


texts: How to draw a Turing Machine for Even-Even

texts:
A TM to accept EVEN-EVEN (a collection of all strings with an even number of a's and an even number of b's) can be based on the algorithm:

Move up the string, changing a’s to A’s
Move down the string, changing b’s to B’s

Modified algorithm: To avoid the problem of crashing on the way down the $Tape$, change the letter in the first cell to an $X$ (if it's an $a$) and to a $Y$ (if it's a $b$). This way we can recognize the left end of the tape.

So far I have this but am not sure how to implement the modified algorithm (note: the e's from start to halt mean empty):

Any help is appreciated!


texts:
I have the following problem:

There is a "clean" sequence of sequences, say:

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

And a "noisy" sequence which is not segmented:

segmented = [1, 100, 2, 3, 3, 101, 4, 5]

I would like to partition segmented into exactly len(clean) parts such that the sum of the edit distances of each part and its clean counterpart is minimized.

For this example, one optimal solution would be:

optimal = [
    [1, 100, 2], # edit distance 1
    [3, 3],      # edit distance 1
    [101, 4, 5]  # edit distance 1
]                # total 3

It seems like a typical dynamic programming problem. My first thought was to use a similar algorithm to what TeX uses for line breaking, which brought me to SMAWK.

This is where I am stuck, because I cannot figure out the cost function. For regular line breaking, the function cost(i,j) is the cost of having a line go from index i to index j, like here. But for this problem, we would need a third parameter, namely which line in the clean reference to compare to.

Is this problem not conditioned correctly for SMAWK? Or is there a different cost function definition that I'm missing?
Is there another, similar problem which has a more applicable solution?


texts: How does a computer direct the processing of information

texts:
So I'm reading Introduction to computing systems:From bits and gates to C and beyond, and the author states that a CPU is the mechanism that

...directs the processing of information. Which is figuring out what task should get carried out next

My question is: what exactly does he mean when he says that a processor "figures out" the next task that the computer has to carry out? Do we have a model for this from a software perspective?
The way that I currently understand this statement is that by "figuring out", he's referring to the Control Unit, from the Von Neumann model of a stored program computer, but I know there's different computer architectures out there. The author implying that the a computer is essentially a CPU in the same paragraph just adds to my confusion.

We have used the word computer many times in the preceding paragraphs, and
although we did not say so explicitly, we used it to mean a mechanism that does
two things: It directs the processing of information and it performs the actual
processing of information. It does both of these things in response to a computer program. When we say "directing the processing of information," we mean
figuring out which task should get carried out next. When we say "performing
the actual processing," we mean doing the actual additions, multiplications, and
so forth that are necessary to get the job done. A more precise term for this mechanism is a central processing unit (CPU), or simply a processor.


texts: Is true * true = true in Separation Logic?

texts:
I am trying to show that the following interference is unsound in terms of Separation Logic:

$$
(p_0 \implies p_1) \implies ((p_0 * q) \implies (p_1 * q))
$$

I came up with the following values for a counter example: $p_0 = true$, $p_1 = x \mapsto 1$, $q = true$. The heap contains just one mapping of $x \mapsto 1$.

The idea is that $(p_1 * q)$ cannot be true because $p_1$ already describes the whole heap and there is nothing left for $q$.

I am not sure, however, why $true * true$ would hold if there is only one element in the heap. Shouldn’t it be false as those two $true$s cannot claim that single heap element at the same time?


texts: Need solution for infinite right recursive grammar in Predictive parsing?

texts:
i am new to compiler design, currently studying Ullmans book on this.He says:

Problem with predictive parsing (both recursive and non recursive) is that Left recursive productions can go infinite loop.Thus, to make grammar suitable for predictive parsing we need to eliminate the left recursion by immediately or indirectly.

 E -> E+T|t

My problem is, same can happen with right recursion also.What is the solution for it?

 T -> E+T|t

Please correct me if i am wrong! thanks.


texts: Convex optimization with the help of Multiplicative Weights Update Method

texts:
I've already asked this question over at MathExchange, but since I received no replies or comments there, I hoped it might be more adequately fitting in this category.

I have a convex (concave) objective function with constraints that are all linear, and would like to use the Multiplicative Weights Update method (see MWU) to optimize it. Has anybody done something like this before, or seen a paper on the topic? My searches so far have been rather unsuccessful, so I'd appreciate every hint/idea or even reference.


texts: Reducing 3-coloring problem to trio representatives

texts:
A group of students is divided into trios - groups of 3 members. Each student can be assigned to more than more trio. We want to assign their representatives, by choosing exactly one member of each trio. Is such assignment possible?

My goal is to use polynomial-time reductions to transform 3-coloring of a graph into this problem. However, I'm stuck on the correct representation.

If each vertex is a different student and edges represent being in the same trio, how do I separate trios?
If each node represents a trio, what could be a sensible meaning of the edges?

I suspect that since a 4-clique has no adequate 3-coloring (which could also mean that 4 trios with the same three members have no possible representative assignment), the latter option could be more sensible, but I'm not sure on how to proceed with this reduction proof.


texts: What are some complexity classes for neural networks?

texts:
Turing machines and neural networks are equivalent in their expressive powers, but as models of computation they are different. Turing machines come pre-configured with their transition functions while the neural networks configure weights to build learnable computable functions using input data.

Is the class of problems efficiently solvable by a neural network equivalent to the class P or NP... or some normal complexity class or do they have their own complexity classes that are not equivalent to normal ones.


texts: Application of shortest vertex-disjoint path with time window

texts:
I am working on finding shortest disjoint path problem, When there are distinct origin destination pairs and there is a predefined time window (or length) associated with each object (which we want to move from one origin to its specific destination). This time window will tell us how long it will take for the object to pass a particular point on the network.

These objects should not encounter each other in any ways on the network, so it is a vertex-disjoint path problem with respect to time. For example if I have two objects A and B, and object A will pass node 1 from 10:00 a.m. to 12 p.m., during these time periods object B cannot cross this node, but any time after 12.00 and before 10 (as long as the time window of B allowed) B can pass through node 1.

I want to know if there is any application of this problem in computer science?


texts: Are data storage efficiency and volatility directly correlated?

texts:
It seems intuitive to me that less efficient data storage methods are also less susceptible to degradation over time.
For instance, the string "ABC" can also be represented as "AAABBBCCC." In the first string, if you randomly change one letter into any other letter, the original string can't be constructed. In the second, more redundant representation, if you do the same thing the original string is still constructible. The second string is less volatile.
What I'm looking for is a theorem or paper that explains this effect. Is efficiency really correlated with volatility like this, or am I missing something?


texts: Computational Complexity of 'Generic'/'Relaxed' Horn 3SAT

texts:
Horn 3SAT are described as the 3SAT with at most one positive literal. And its in P. What about the complexity of relaxed case of 2-Horn 3SAT i.e.

Each clause is in CNF, has exactly 3 literals, with at most 2 positive literals.

Can someone please help with the reference.


texts: How can I treat a problem like a search problem in AI?

texts:
I'm a CS student and I'm trying to understand the searching algorithms used in AI.

My problem is that I don't really understand how to treat a problem like a search problem. I don't know which would be the first steps for solving it and how shall I choose the right algorithm for that.

For example, I have a problem like that:

n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of
an n×n n grid. The vehicles must be moved to the top row but in reverse
order; so the vehicle i that starts in (i, 1) must end up in (n−i+ 1, n). On
each time step, every one of the n vehicles can move one square up, down,
left, or right, or stay put; but if a vehicle stays put, one other adjacent
vehicle (but not more than one) can hop over it. Two vehicles cannot
occupy the same square.

I understood that the start state of each car is the bottom row,
each car has at most five possible moves from any position and if each car has
a 3x3 grid of empty space around it, then all five moves are possible.

My idea is that I should treat the car route like a tree where each node is a position of the car at a time, but I don't know how correct is it.

Which would be my first steps regarding this problem to solve it like a search problem?

I would be very thankful for any advice!


texts: Priority queue with ubounded number of elements (i.e., with dynamic storage)

texts:
I'm looking for a data structure that can work as a priority queue with reasonable maintenance complexities (like $O(\log n)$ for insertion and deletion) and that has a theoretical unbounded limit for its number of elements (like a tree structure, that is bounded only by the computer's available memory, and unlike a traditional heap, that uses an static array, which is too costly to augment).

The reason is that I'm implementing a program that makes use of a priority queue and I don't know a priori how many elements I'm going to insert in this queue at once, so sometimes I'm out of space to add another element.

There is no way to estimate this number, and to create a huge array to support a static type of queue is a terrible option, as maybe not even a half of it will be used and I'll be short on memory to allocate other objects.

I've heard of something like a Dynamic Heap (or something in the like) that is some sort of linked list of arrays, whose elements are dynamically allocated when needed, but I'm not sure this is the best strategy to follow, moreover, I would like to know if there were other options.

Just for the record, I'm implementing a Branch-and-Bound algorithm for solving a linear integer optimization problem, with each node stored on the queue being the abstraction of an active node on the algorithm. The number of active nodes cannot be estimated at any time, so a theoretically unbounded queue would help a lot.


texts:
I have a set of leaf-labeled trees. I want to concatenate them into a single leaf labelled tree in such a way that the height of the resulting tree is smallest possible.
Can somebody please help me to generate an algorithm for this task,
with good performance?

Leaf labelled tree is a tree in which all the data is held at leaves.


texts: prove that Integer partition problem is NP complete using Hamiltonian Cycle

texts:
Show that Integer parition problem is NP-complete using the fact that Hamiltonian cycle is NP-Complete
My Thoughts :
Integer paritition problem is about partitioning a given set of integers into two sets with equal
sums. If I could show that Integer partition is polynomially reducible to Hamiltonian cycle
that would prove the given statement. I am not really sure how an instance of solution to IP
could lead to a hamiltonian cycle


texts: What is "potential speedup" in parallel computing?

texts:
There is an example problem from p506 of Computer Organization and Design, Fifth Edition: The Hardware/Software interface by David A. Patterson, John L. Hennessy

I wonder how "potential speedup" is defined? The book doesn't give its definition.

In the example, since speedup with $10$ processors is $55\%$ of the potential speedup, the potential speedup should be $ 5.5 / 55\% = 10$. it is equal to the number of processors.

Since the execution time before improvement has a part $(10t)$ unaffectable by parallel computing on multiple processors, according to Amdahl's law (outlined in blue box), the potential speedup must be smaller than the number of processors.

So I am puzzled.

Google books has an earlier (4th) edition which has a similar example too.


texts: Applying subproblem technique to permutations with grouping

texts:
I am trying to apply overlapping subproblems and dynamic programming to permutations.

Say, we have a set of $n$ elements in a string. Each of these elements could be a $1$ or a $0$.

Given some string, I am trying to count the number of valid permutations- where a valid arrangement is defined as an ordering with no $1$ that stands alone from other 1s.

Example input string: $0101$

Example of valid arrangements: $1100, 0011, 0110$

Not valid: $0101, 1010, 1001$

EXPECTED OUTPUT: $3$

For example:

Say our input string contains four 1s and two 0s.

I suppose my difficulty is coming with defining the sub-problem. I initially thought I could set up a string with only the $0$ elements with slots/bins in between. $[ ] 0 [ ] 0 [] $, and then continue to use combinatorics to compute the number of additional arrangements possible with each 1 added in.

The first 1: 0 possibilities, because it will never have a 1 to accompany it.

Adding the 2nd 1: 3 possibilities, because the pair can go in either of the 3 slots.

Adding the 3rd 1: 0 new possibilities, because it must go with the other 2 ones, wherever they are.

Adding the 4th 1: We have enough to make 2 groups of $1$s now... here is where I start getting unsure. I'd think it would be an additional 3 possibilities. $\binom{3}{1} + \binom{3}{2} = 6$ total

Would anyone have an idea if I'm on the wrong track, or if not, how to proceed? This approach doesn't seem like it works for larger values. Thanks!


texts:
I've been looking into reductions to/from the TQBF language and have managed to get stuck on something that is almost certainly not true (or, if it is true I'm missing a significant computational cost associated with it) with respect to simplifying TQBF instances.
For the sake of simplicity, let's restrict attention to TQBF instances in prenex normal form and CNF with no free variables. My hypothesis (which I strongly suspect is wrong, but have been unable to find a counter-example) is that such a TQBF is satisfiable if and only if the TQBF that results from removing all instances of universally quantified variables from the sentence is satisfiable. For example, take the following instance:
$\exists a \forall b \exists c \forall d$ $\psi(a,b,c,d)$
$\psi(a,b,c,d) = (\neg a \vee b \vee c)\wedge (\neg b \vee \neg c \vee d)\wedge (a \vee c \vee \neg d)$
First, I contend that this instance is not satisfiable (easily verifiable by hand). If we apply the method I describe above, we get the following "core":
$\exists a \exists c$ $\phi(a,c)$,
$\phi (a,c) = (\neg a \vee c)\wedge (\neg c) \wedge (a \vee c)$
which is clearly not satisfiable. If instead of this example we look at this:
$\exists a \forall b \exists c \forall d$ $\psi(a,b,c,d)$
$\psi(a,b,c,d) = (\neg a \vee b \vee \neg c)\wedge (\neg b \vee c \vee d)\wedge (a \vee c \vee \neg d)$
which clearly is satisfiable (set c to true, a to false) and which has a "core" of
$\exists a \exists c$ $\phi(a,c)$,
$\phi (a,c) = (\neg a \vee \neg c)\wedge  (c) \wedge (a \vee c)$
that is also satisfiable with the same variable settings.
If this method always works, that would seem to imply that there is a reduction from TQBF to SAT in time linear in the number of universal quantifiers and the number of occurrences of the universally quantified variables in the formula, showing that TQBF is NP-Complete (it is already known to be PSPACE-Complete and thus NP-Hard, so if it is in NP it is NP-Complete) and furthermore that NP=PSPACE. I would be utterly stunned if this is the case, but I have been unable to find a counterexample (or a missing computational cost in the reduction that makes it not polynomial time). What am I missing?


texts: Feedback Vertex Set with vertex partitions?

texts:
I've encountered this problem in a program analysis project I'm working on, where I've got a bunch of functions defined in terms of each other, and because I'm using SMT which doesn't support recursion, I'd like to define as many functions outright as possible, so that fewer are left to be solved by the SMT solver.

In terms of pure graph theory, my problem is this:

Given:

A directed (possibly cyclic) graph $G=(V,E)$
A partitioning of $V$ into disjoint subsets $V_1, \ldots, V_k$

I want to choose:

$v_i \in V_i$ for each $1 \leq i \leq k$ that minimizes the feedback-vertex number of the subgraph of $G$ induced by $\{v_1,, \ldots v_k \}$

I'm fairly guessing the problem is $NP$-hard, because of its reliance on the Feedback Vertex Set problem. If we assume that our $V_i$ sets are small, say with a maximum size $M$, then there are at most $M^k$ combinations to try.

I'm wondering:

Has this problem (or anything similar) been studied before?
Is this problem $NP$-hard, or does it fall into one of the subsets of feedback-vertex that is tractable (e.g. chordal graphs, convex-bipartite, etc.)
Does anyone know of a way to reduce the Feedback Vertex Set problem to this? It's solvable in $O(1.7548^n)$ time, so if I can translate my problem into this one it's entirely possible it's solvable for small inputs. But for all I know, my problem is harder than Feedback-vertex.
Are there any approximation algorithms that can be adapted to my variant of the problem, that are maybe not optimal, but would give near-optimal results quickly


texts: Big O - Equivalence: "Standard" definition vs Limit definition

texts:
This question is related to: Landau Notation, Definitions: Limits vs. Cormen's.

Consider functions $f, \ g : N \rightarrow R^{\geq0}$.

For small-$o$, the definition:
$$f(n)\in o(g(n)) \iff \forall c>0,\exists n_0>0, \forall n\geq n_0: f(n) < c \ g(n)$$

Can also be expressed as a limit (i guess this assumes the limit exists):
$$f(n)\in o(g(n)) \iff \lim_{n\to\infty}\frac{f(n)}{g(n)}=0 $$

This can be verified introducing the definition for $\lim_{n\to\infty}$ on $N$, and then both definitions are identical.

Now, the "standard" definition for big-O would be something like (near exactly to Cormen's, except the codomain here is $R^{\geq0}$):
$$f(n)\in O(g(n)) \iff \exists c>0,\exists n_0>0, \forall n\geq n_0: f(n) \leq c \ g(n)  \qquad  (1)$$

Im trying to see if the following is true (again, this assumes the limit exists):
$$f(n)\in O(g(n)) \stackrel{?}{\iff} \exists c>0: \lim_{n\to\infty}\frac{f(n)}{g(n)}=c$$

Im not sure both directions of the equivalence are true. More specifically, i am having trouble with the $\Rightarrow$. According to this general answer, both directions should be true for $\Theta(g(n))$, wich is stronger than $O(\_)$. On the contrary, this answer (for roughly the same question, but in math SE) says big-$O$ cant be defined in that way (it was downvoted).

So, the questions are:

How exactly def (1) implies the $\lim$ definition?:

$$\forall \epsilon>0,\exists n_0>0, \forall n\geq n_0: \left| \frac{f(n)}{g(n)}-c\right| < \epsilon$$

Is the above still true considering generic functions $f, \ g : X \rightarrow R^{\geq0}$, where $X$ is some reasonable domain, maybe $Z$, $N^k$ or even $R^k$ (although reals are not turing-computable, im thinking in algorithms in the more general sense possible).


texts:
If a grammar has the same variable multiple times, is it the same as adding a $\mid$ between them? For example, is

$$\begin{align*}S &\to bB  \\
S &\to \varepsilon  \\
B &\to cB  \\
B &\to \varepsilon  \end{align*}$$

equal to the following?

$$\begin{align*}S &\to bB \mid \varepsilon \\
B &\to cB \mid \varepsilon \\
\end{align*}$$


texts: Helping prove this notation for Big-O(n!)

texts: Hello, I was wondering if anyone can help me prove the right part of this double equation. I know the left one is possible due tolog(n!) = Θ(nlogn). Any help is much appreciated.


texts: What are the fundamental differences between predictive and LALR(1) parsers?

texts:
I'm reading the Dragon book.  The beginning describes recursive descent parsers. Then it states that a predictive parser is the table version of a RD parser.

I also read up on LALR(1) parsers.

The differences between predictive and LALR parsers seem superficial to me.  LALR seems to consume terminals quickly, but the predictive parser will do that too if the grammar is properly prepared (for example, by converting it to Greibach Normal Form.)

What am I missing? What is LALR's advantage?


texts: Optimal Algorithm for checking if a number is a multiple of three

texts:
I'm just starting a course on Computational Number Theory and have very little Computer Science background but definitely know enough about the big-O notation.

I currently have an assignment to work on:

  An algorithm reads in the binary digits of a positive integer $N$ and determines whether $N$ is a multiple of 3. Show that the algorithm takes time at least of order $n$, where $n$ is the number of binary digits of $N$.

Basically, I have thought up of an algorithm which I'm pretty sure is correct:
(I don't know what's the best/correct way to write an algorithm but here's my attempt)

Start with a binary number $x=a_na_{n-1}\dots a_1a_0$.
Then compute $x'=\sum^{i=n}_{i=0} (\frac{3}{2}+\frac{1}{2}(-1)^{i+1})a_i$.
Then $x'=0 \mod3 \iff 3|x$

This works because $2^{2k}=1\mod3$ and $2^{2k+1}=2\mod3$

I can guess that my algorithm takes time at least of order $n$ because I need order $n$ steps to compute $x'$.

However, I have my doubts:

How do I know my algorithm is the optimal algorithm?
Am I 'cheating' by saying $x'=0 \mod3 \iff 3|x$?
Am I even answering the question correctly by providing such an algorithm or is there some other sort of analysis to show lower bounds for algorithm time?


texts: Data structure that allows accessing elements by index and delete them in O(logn)

texts:
I need to take an kth index element from array like data structure and delete it (k is any possible index). Array have O(n) for deleting elements, and List have O(n) for searching element. I would like to do both operations in O(logn) time.
Which data structure should I use to meet this requirement?
Clarification:
Deleting element on index(5) will move element from index(6) to index(5)
the element at index 6 change indexes so that it now has index 5
and 7th element changes to 6th so on ..


texts:
I'm currently confused whether a graph should contain strictly one distinct Hamiltonian Cycle. (given that [1,2,3,4,1] and [2,3,4,1,2] are the same).

I was wondering if, by definition, there can be multiple distinct Hamiltonian Cycles in a graph? something like H1 = [1,2,3,1] and H2 = [6,7,8,6]

can someone kindly confirm?

(addt'l sources and references would really be great so I can dive in deeper)

Cheers!


texts: How to measure processing power of a quantum computer?

texts: Is there any way to get an equivalent of computing power of quantum computers in terms of computing power of common computers? I mean, how many teraflops (or so) can a quantum computer compute? How can I calculate that equivalence? I think it depends on the architecture, like a x64 in common computer, and a 512-qubit.


texts: Proving that it's decidable whether a TM ever moves on the blank input

texts:
I'm trying to understand how to prove a language is decidable, semi-decidable, co-semi-decidable, or none of the above.

I've got the problem: $$A_{\mathrm{right}} = \{ \left<  M\right>  | M \text{ never moves on blank input} \}$$

and I have to prove what it is. I know that it is decidable, because if given an input where there is a blank, then it will enter a halt and will loop there forever and not move, thus it is rejected. Everything else can be accepted. I just don't know how to go about proving this with quantifiers.

Any help would be greatly appreciated.


texts: Estimating run time in the absence of knowledge

texts:
I’ve always wondered how to make a best guess in the absence of any knowledge.

Let’s say you have a computation running, and you don’t know when it will complete (just that it will). Can you make any estimate when it will be finished just based on the elapsed time without any further knowledge? For example after 10 minutes I cannot tell how much longer it will take, it might take 10 more minutes, or less, or a lot more. But after 4 hours  I’m quite sure it will not finish in the next 10 minutes (that would be a big coincidence). So a guess might be "probably a few hours more". After 4 days I’d be quite certain that it will take a lot longer.

Can you somehow quantify this certainty / uncertainty?


texts: Algorithm Request: "Shortest non-existing substring over given alphabet"

texts:
I'm looking for an (efficient) algorithm to solve the following problem:

  Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not contained in $S$.

Try as I might, I can't seem to map this problem to any of the standard CS string problems.


texts: Complexity of special instance of Knapsack

texts:
Consider the following algorithmic task:

Given: primes $p_1,\dots,p_k$, and positive integers $e_1,\dots,e_k$, and a positive integer $M$
Find: integers $d_1,\dots,d_k$ that maximize $\prod_i p_i^{d_i}$, subject to the requirements that $0 \le d_i \le e_i$ and $\prod_i p_i^{d_i} \le M$.

What is the complexity of this problem?  Is it NP-hard?

This problem is equivalent to the following:

Given: primes $p_1,\dots,p_k$, and positive integers $e_1,\dots,e_k$, and a positive integer $M$
Find: integers $d_1,\dots,d_k$ that maximize $\sum_i d_i \log p_i$, subject to $0 \le d_i \le e_i$ and $\sum_i d_i \log p_i \le \log M$.

This can be seen to be an instance of bounded knapsack with $k$ items, where the $i$th item has weight $\log p_i$ and value $\log p_i$ and can be used at most $e_i$ times, and where the capacity of the knapsack is $\log M$.  (See the footnote below for a more careful statement.)  Thus, my problem is a special case of bounded knapsack.  It follows that my problem is in NP.

But is my problem NP-hard?

For instance, is there a way to reduce from bounded knapsack to my problem?  It's not clear, because my problem limits the weights and values to be something specific related to the log of primes, rather than arbitrary values.

Footnote: strictly speaking, the bounded knapsack requires item weights and values to be integers, whereas $\log p_i$ isn't an integer.  However, we can fix this up by picking a sufficiently large constant $K$ and using $\lfloor K \log p_i \rfloor$ as the weight and value of the $i$th item, and use $\lfloor K \log M \rfloor$ as the capacity of the knapsack.  With this fix-up, my problem now becomes a special case of bounded knapsack, or reduces to bounded knapsack.


texts: given a binary number b, is there any grammar that generates the languages of $1^x$ where $x$ is $b$ in base $n$ ($n \in \mathbb{N}$) e.g. if $b$ is 1100, the grammar should generates $11,1^{12},1^{36},\cdots$. is there any idea that helps to create the proper grammar?


texts: Find the central point in a metric-space point set, in less than $O(n^2)$?

texts:
I have a set of $n$ points which are defined in a metric space – so I can measure a 'distance' between points but nothing else. I want to find the most central point within this set, which I define as the point with the minimum sum of distances to all other points. The metric computation is slow, so needs to be avoided where possible.

The obvious way to find this point uses $n^2$ metric distance calculations, as it simply (a) calculates for each point the sum of distances to all other points and then (b) takes the minimum point.

Is there a way to do this in less than $O(n^2)$ distance comparisons? (Probably making use of the triangle inequality in some way, which should hold with my metric.)

A good approximation might suffice if an exact method doesn't exist.


texts: Fibonacci Series with Dynamic Programming

texts:
We can compute Fibonacci numbers by means of dynamic programming approach. If we do not store intermediate solutions, we cannot use them for future necessities. In this case, asymptotic complexity reaches exponential time.

             f(5)    -> 2^0
            /    \
           /      \
          f(4)    f(3)   -> 2^1
         /   \    /   \
       f(3) f(2) f(2) f(1) ->2^2
      /   \
     f(2)f(1)............

Each recursive call consumes only O(1) time.

T(n) = 2^0 + 2^1 + 2^2.... (geometri series)

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

T(n) = O(2^n)

In some places, it is written that n is size of the problem, but I think n is number of levels in recursion tree. Is n equal to size of the problem or number of recursion levels ?


texts: Detecting coplanarity by given pairwise distances

texts:
Consider an undirected weighted graph $G = (V,E)$, where $V \subset \mathbb{R}^3$ so the points are 3D, and the weight of an edge equals the (Euclidean) distance between its endpoints.  Note that we're not given the coordinates of the points in V.  We may not even be given all pairwise distances, so the graph need not be complete, and it may even be sparse.

Suppose we're given $k$ and told that there are $k$ planes such that all the vertices belong to at least one of those plane. We want to find $k$ such planes, with an added restriction:

In order to determine whether 4 points are coplanar given only their pairwise distances, the most straightforward method is to use the Cayley-Menger determinant.  For our problem, this would require the graph to be fairly dense, since we'd need to know most of the pairwise distances to apply Cayley-Menger.  The restriction is to find $k$ planes without using the Cayley-Menger determinant.

If this is impossible, can we obtain a proof that states this is impossible?  In other words, can we prove that for any such graph $G$ and given $k$, if we have enough information to find $k$ planes for $G$ by some means, then we have enough information to use Cayley-Menger to find $k$ planes?


texts: How often can a linear speed sort succeed?

texts:
Let's say you have sorting function. It is allowed to exit with failure (but if it does not it must return a correctly sorted sequence). It is also $\mathcal O (n)$.

What kind of bounds can we place on the success rate of such an algorithm? It obviously can't succeed 100% of the time, since then it would just be an ordinary list sorting function and it would have to be $\Omega(n \log n)$. The answer isn't 0% success, since you can check if it sorted in $\mathcal O (n)$, and so you can sometimes succeed.

Of course, the success rate depends on how we are choosing the list. The uniform case would be best, but any kind of bounds would be helpful.


texts: Finding longest balanced parentheses using $n$ smaller strings

texts:
Given $n$ strings consisting only of '$($' and '$)$', how one can compute the length of the longest string that can be built by concatenating a subset of these strings in some order such that the resulting string is a balanced parenthesis?

Example: If we have the strings $\{"(()",")(",")","(("\}$, one can build the string $"(())()"$ which has length 6.  We cannot construct a longer one from the previous set, thus the answer is 6.

In general, the answer is always even, and always $\geq 0$ because we can always take the empty set.

Problem source: North American Invitational Programming Contest (NAPIC) 2017, Problem A.


texts: Which part of Go(lang) is in Crystal(lang)?

texts:
Reading Crystal Programming Language They says it is inspired from many programming language and Go.

I would like too know which part of Golang, since it is not its syntax.


texts:
Sometimes the C# compiler can do some type inference when you have to specify the generic parameters of some methods, like:

list.Select<[type of x.xx]>(x => x.xx)

Can be shorten as

list.Select(x => x.xx)

. This feature is quite unstable and confusing. Consider another example:

public interface ISome
{
  int Method(string arg);
}

public class Mock<T>
{
  public void Setup<TResult>(Func<T, TResult> func) { }
}

public static class It
{
  public static T IsAny<T>() { return default(T); }
}

And we wish we can write this:

var mockSome = new Mock<ISome>();
mockSome.Setup(s => s.Method(It.IsAny()));

But C# compiler will raise error in this case:

  The type arguments for method 'It.IsAny()' cannot be inferred from the usage. Try specifying the type arguments explicitly.

Since the type signature of ISome.Method is consistant, it's known at compile time. But the C# compiler asks you to specify the generic parameter of It.IsAny.
So we have to do this:

mockSome.Setup(s => s.Method(It.IsAny<string>()));

This is quite strange. Is there a way to formally, or, correctly and totally describe the C# compilers' type inference rule? (like, in what circumstances will C# compiler infer the type; in what circumstances won't?


texts:
I am not very familiar with "heuristic", so please correct me if anything said by me is wrong.

Per my understanding, Algorithm is an automatic steps which guarantee to give a correct solution corresponding to a specific problem (and its input domain)

Heuristic is somehow a rule to guess the next step, hoping when repeating this rule a nearly-optimal solution is found.

Algorithm is proof-able, the complexity, the correctness, etc.

But I wonder how can one proof heuristic?

Indeed I wonder is "proof" a correct term / action correlate to heuristic, but how about say, proof the heuristic can give sub-optimal answer (like at most 10% worst than the optimal) for 90% out of all possible input?


texts:
I am looking for an answer regarding the CPU read and write. We know there are two clocks that are working in the computer system, one is the peripheral clock and the other is the CPU own clock on which its control systems are working. I am familiar with the clock domain crossing but I dont understand how the CPU read and write data working on different clocks.
For example the CPU sends the data to be written on the data bus and address on the address bus. Since the rest of the peripherals are working on their own clocks such as PCI or other standards, Now the CPU which is working on its own clock will execute the next instruction send the address again on the address bus and the data on the data bus to the same peripheral but data bits have still not been read by the peripheral so doesnt the data will be lost in this process or is there any mechanism of handling this situation ?


texts: Leo's deterministic reduction for Earley Parsing

texts:
I am trying to build an Earley parser using the Wikipedia pesudocode as a base, with Aycock's fix for epsilon rules as follows:

def predict(self, column, symbol, state):
    # original predict
    for alternative in grammar[symbol]:
        column.add(a new state corresponding to alternative)
    # Aycock fix
    if nullable(symbol):
        column.add(state.advance())

And Leo's optimization for right recursion using the explanation here for further insight.
I am able to understand how to parse Right Recursive grammars with it. However, I am confused when it comes to using it to parse non-right recursive grammars.
For example, here is a grammar that can parse an example string aa

    <start> := <A>
    <A>     := <A> + 'a'
    <A>     := \epsilon

Without the deterministic reduction from Leo, the Earley items constructed (pipe indicates the dot) are as follows:
The parenthesis is in this format (starting column, earley set).

char: _ column[0]
<start>:= | <A>(0,0)     #1) init
<A>:= | <A> a(0,0)       #2) predict from 1
<A>:= |(0,0)             #3) predict from 1
<start>:= <A> |(0,0)     #4) epsilon complete from 3
<A>:= <A> | a(0,0)       #5) epsilon complete from 3

char: a column[1]
<A>:= <A> a |(0,1)       #6) scan a from 5
<start>:= <A> |(0,1)     #7) complete A from 1 (start col of 6)
<A>:= <A> | a(0,1)       #8) complete A from 2 (start col of 6)

char: a column[2]
<A>:= <A> a |(0,2)       #9) scan a from 8
<start>:= <A> |(0,2)     #10) complete A from 1 (start col of 9)
<A>:= <A> | a(0,2)       #11) complete A from 2 (start col of 9)

According to Leo,

  Definition 2.1: An item is said to be on the deterministic reduction path above $ [A \rightarrow  \gamma., i] $ if it is $ [B
> \rightarrow \alpha A ., k] $ with $ [B \rightarrow \alpha . A, k] $
  being the only item in $ I_i $ with the dot in front of A, or if it is
  on the deterministic reduction path above $ [B \rightarrow \alpha A .,
> k] $. An item on such a path is called topmost one if there is no
  item on the deterministic reduction path above it.

(I am assuming that $ [B \rightarrow \alpha A ., k] $ is also in $ I_i $.)

The completer is as follows:

def complete(self, column, state):
    detred = self.deterministic_reduction(state)
    if detred:
        column.add(detred)
    else:
        for st in (matching states in start column of state):
            column.add(st.advance())

column 0

So, when it processes item (3) <A>:= |(0,0) in column[0] for completing, it finds both item (1) which obeys the restriction for a single item with dot before <A> and the corresponding item (4) with dot after. Hence, it considers (4) on the deterministic path. This does not change anything for column[0]. However, things change for column[1].

column 1

When it processes (6) for completing, it again finds (1) and item (4), and hence (4) is considered a parent in the deterministic path. Hence, it saves a copy (4) to the column[1] rather than completing it traditionally in earley. This means that the item (8) <A>:= <A> | a(0,1) from the original Earley parse never gets created, which means no item for accepting the next a in column[2] (which should have been added to column[2] by scanning of this item), and the parsing fails.

So, my understanding of deterministic reduction bye Leo is somehow faulty. Where have I gone wrong?

I have read up on all materials I could get on Leo's optimization, but still unclear what I have missed. I think the item (4) should not be a parent because it is not a previous instance of the recursive rule in item (6). However, nothing in Leo's paper seems to explain how I can exclude such instances from the deterministic path.

If it helps, the complete self contained implementation is here.