texts: Why do we have to forbid non-conforming lower and upper type bounds?

texts:
(it's a repost of my unanswered question from scala-user@googlegroups.com about Scala)

In the Scala Language Specification, §4.4 Type Parameters, there is a requirement:

  The most general form of a first-order type parameter is @a1 ... @an ± t >: L <: U. Here, L and U are lower and upper bounds that constrain possible type arguments for the parameter. It is a compile-time error if L does not conform to U.

I'm interested in a particular case of this rule, when it applies to type parameters of a generic class definition.

IIRC, in early versions of Scala this rule did not exist. One might think this was benign and in worst case could only result in an uninstantiable and uninhabited type (and even could be useful in some cases, when L and U depend on some type parameters and can be simultaneously satisfied with certain substitutions, although statically L does not conform to U).

But, as I recall, it was demonstrated that without this rule it was possible to compile certain non-typesafe program, exploiting transitivity of subtyping, that resulted in a ClassCastException at runtime, although no explicit casts were involved. I tried to find or reconstruct such an example, but so far without success.

Could you please help me to find such an example, or point me to other reasons why this rule must be required for the language to be typesafe? Thanks!


texts: how can this function be computed in polynomial time in regards to its input?

texts:
i am struggling for quite a while with this. trying to understand why the following function can be calculated in polynomial time(in regards to the input length)

defining a function from assignments of truth values to a set of booleans to 3CNF propositions:

the function gets an assignment of truth values to a set of n boolean variables $x_1,x_2,...,x_n$ (n ≥ 3) (meaning each boolean variables gets either 0 or 1).

the function returns a 3CNF proposition that upholds(maintains) the following:

1)each clause of the proposition contains exactly three literals

2)the proposition consists of only the variables $x_1,x_2,..,x_n$

3)the three literals in each clause are of different variables(there are no double literals in the clause, and none of the clauses consists of complimentary literals)

4)the proposition is satisfiable and the only assignment that satisfies the proposition is the assignment the function obtained as an input.

prove that the given function can be calculated in a polynomial time in regards to the input size

i don't understand how can it be computed in a polynomial time in regards to the input size. tried to look everywhere, this site, online, sipser's book and nothing. similar problems are usually from the NP family.

could someone please explain to me how this one can be polynomially computed? i just can't understand that

EDIT: this is how the final 3CNF should look in my opinion: $(l_1 \lor l_2 \lor x_1) \land  (\lnot x_1 \lor l_3 \lor x_2) \land (\lnot x_2 \lor l4 \lor x_3)\land ... \land(\lnot x_{n-3} \lor l_{n-1} \lor l_n)$ (from $(l_1 \lor l_2\lor...\lor l_n)$).

but what i don't understand is why is it polynomial, could someone please explain to me why can it be computed polynomially in regards to input size?


texts: What is the time complexity of this randomized algorithm?

texts:
Let's start with a problem statement:

  given an array of length $n$ with numbers $1$ through $n$ (inclusive), consider the following steps:

  Select a random number $k$ in range $[1, n]$.
  Set $a[k] = q$.
  If there exists element $p$ in $a$ such that $p \ne q$, go to step 1, otherwise end.

So, basically we are going to randomly pick elements in the array and set them to some predefined value until every element in the array is set to this value. What is the time complexity of such algorithm? please explain your answer.


texts:
Let $G$ be a graph whose edges have integer weights between 1 and 255.

What is an efficient algorithm for finding a path between two vertices $s,t$, such that the product of weights on the path is minimized?

The first approach that comes to mind is to replace each weight with its logarithm, and use e.g. Dijkstra's algorithm for finding a path that minimizes the sum of weights. The run-time complexity is $O(|E|+|V|\log|V|)$. For practical purposes this is a good solution, but theoretically it does not solve the problem, since the logarithm (when represented as a floating-point number) is not accurate.

A second approach is to use Dijkstra's algorithm directly, replacing each "+" operation with "*" and each "0" with "1" (equivalently, replace each weight with its logarithm but represent the logarithm of $x$ as "$\log{x}$" and sum the weights using the rule $\log{x}+\log{y}=\log{xy}$).
The problem is that, with integer multiplication, the weights might grow very fast: even though each weight is represented by $O(1)$ bits, the product of a path might require $O(n)$ bits to represent,  and this affects the runtime complexity of multiplication.

Is there a more efficient algorithm?


texts: How to find sets of polynomially bounded numbers whose subset sums are different?

texts: Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ such that we always have $\pi(S) \ne \pi(S')$. For example, we can define $a_i = 2^i$. This function satisfies the property because for each $A \subseteq N$, $\pi(A)$ uniquely represents an integer written in base 2. However, in this function $a_i$ is bounded above by $\mathcal{O}(2^n)$. I am looking for a function such that $|a_i|$ and $\frac{1}{|a_i|}$ are bounded above by a polynomial. As an example that does not satisfy this last condition we can consider $a_i = 2^{i-n}$. It would be great to know different functions that satisfy this property. I will try to proof the uniqueness myself (if it is not so difficult!), so please let me know if you are aware of such functions.


texts:
I am trying to reduce NOT-ALL-EQUAL SAT to MAX-CUT with weighted edges.

I know that if there are weights to the edges, then I can reduce NOT-ALL-EQUAL SAT to MAX CUT by have a $G$ with $2n$ nodes ($x_i$ and $\bar{x}_i$) and edges between the nodes based on each clause. And, adding edges between $x_i$ and $\bar{x}_i$, so on.
But, I am not sure how to assign weights if I have to reduce a NOT-ALL-EQUAL SAT to weighted MAX CUT.

How should I go about this problem?


texts: Regular expression for even/odd string on alphabet

texts:
Given the alphabet $\{ a,b \}$, if I want to build the regular expression for even/odd lenght strings, I can think that an even lenght string is given by some combination of $a$'s and $b$'s, and the letters can be paired, so there are four possibilities: $aa,ab,ba,bb$, the regular expression(for even lenght strings) so is:
$(aa+ab+ba+bb)^* $
But can I write this in this other (more compact) way?
(Using, e.g., the notation of Hopcroft-Motwani-Ullman) given a language $L$,
we write $L^i:=\{ w_1w_2...w_i \ \ \ s.t. w_1,w_2,...,w_i \in L  \}$
Then given that $(a+b)$ is (as a regular expression) the notation for the strings formed by one symbol, $a$ or $b$, then $(a+b)^2$ as in the notation above is
$\{w_1w_2  \ \ \ s.t. w_1,w_2 \in (a+b)\}=\{aa,ab,ba,bb\}$
So i can rewrite the notation for the regular expression for even lenght words as:
$((a+b)^2)^*$
But this holds in general, so if I want the strings of lenght a multiple on $n \in \mathbb{N}$, I can consider:
$((a+b)^n)^*$
As the regular expression.
I feel like this is somehow cheating and that this argument is not valid, but to me it seems correct: because it is true that exponentiation is not an operation in the language of regular expressions, but it is also true that in reality here exponentiation is only the concatenation $n-$times of the regular expression $(a+b)$, so $(a+b)^2=(a+b)(a+b)$, $(a+b)^3=(a+b)(a+b)(a+b)$, which is always a valid operation for regular expressions.

So my question is: Is the first way in which I have expressed the
regular expressions for even-lenght words the most concise way to
write it? And if the second way in which I have expressed it is
correct, can this be generalised for $n$ generic (as I proposed)?


texts: Existence of interval arrangement satisfying constraints

texts:
Problem statement:

Input:
(a) A natural number $n$.
(b) $m$ requirements on $I_1,\ldots,I_n$ of the form:

Segment $I_i$ is entirely to the right of segment $I_j$.
Segments $I_i$ and $I_j$ intersect.

Output:
Is it possible to find $n$ non-empty segments (on the real number line) which fulfill the $m$ requirements?

Here is my solution attempt.
I started by considering what happens when I have only requirements of type 1 (no particular reason, just easier to visualize).
I created a directed graph with $V=\{v_1,v_2,\ldots,v_n\}$ nodes, where each node represents a segment. I added an edge $e=(u,v)$ iff the segment $u$ is to the right of segment $v$ ($e$ represents a requirement of type 1). A solution exists if the graph is a DAG, which can be checked in linear time using DFS.
My problem is with edges of type 2. I understand that a solution exists iff there is no edge of type 2 between two nodes which have a path with edges of type 1 between them.
I believe I found an $O((m+n)m)=O(mn+m^2)$ algorithm using BFS from every node $u$ for which an $e=(u,v)$ of type 2 exists. I run the BFS from the node $u$ and check if $v$ is discovered. If it is, no solution exists.
Is there a linear time algorithm for this?


texts: Counting elements in an array greater than a value and after the value

texts:
I have an array composed of integers from 1 through n. For each integer, I want to count the integers which are greater than that integer and occur after the integer's placement in the array in O(n*log(n)) time complexity
Ex:
array : {2, 1, 4, 3}
For 1,  4 and 3 are after 1 and greater than 1 so 3 and 4 are chosen
For 2, (1,4,3) are after 2, but only 4 and 3 are greater than 2, so only 4 and 3 are chosen
For 3, There are no elements after 3
For 4, There are no elements greater than 4
So I get something, maybe a map, that looks like: (I don't care about order)
1 - 3,4
2 - 4,3
3 -
4 -
I tried using the index placements of each integer, but the only thing I got was the number of occurrences. What I got:
1 - 2
2 - 2
3 - 0
4 - 0


texts: Count number of the ways to fill a N-lengthed binary string

texts:
From the problem, count the number of ways to fill a binary string of length $N$ with at least one $1$'s consecutive sequence of length $K$ and other $1$'s consecutive sequences have length no more than $K$.

For $N \le 2\times 10^6$, my approach is to using DP. dp[N][K][2] is the number of ways to fill string of length $N$ with the current $1$'s consecutive sequence length is $K$ and last parameter is to tell whether the current string contains the $1$'s consective sequence of length $K$.

This would work if N is small enough but the constraints of this problem is : $1 \le N \le 10^{10}, 0 \le K \le 50$.

The approach I need is obviously Matrix Exponentiation so I can solve it in $O(\log N \times ?)$. Storing every possible binary strings of length K is not possible ($2^M$). Can anyone provide the solution of the problem? Or at least some hints


texts: Computational equivalences between a calculus and an automaton model

texts:
This Wikipedia table (template for "Formal languages and grammars") maps grammar to language to abstract machine for more than a dozen languages.

http://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars

But I miss another relation: Lambda calculus (that can be described syntactically as a certain context free grammar) has the same computational strength as a Turing machine. I somehow see this as functional programming (LC) vs imperative programming; but as I don't trust my intuition here, I want to explore the correspondence between abstract programming languages and automata further by asking this question.

Are there any similar equivalences between a calculus and an automaton, for finite state machines, and pushdown automata, to start with? (Other examples welcome.)


texts: NP-hardness given some reducible language

texts:
While reading a passage in an older textbook I came upon this problem which I am having difficulty in justifying whether its true or false. Is this possible?

If some problem $A$ is NP-hard, and if that problem $A$ can be reduced to problem $B$, and there exists some polynomial-time algorithm which solves $B$, then P=NP?

While I understand that the view is $P≠NP$, if the above case were true would $P=NP$?


texts: Looking for a simple example of Transition Semantics

texts:
I want to define a semantics of a DSL through transition semantics. For my DSL I defined the syntax and implemented a code generator. Although I can provide a demo by giving examples, I want to write the semantics of my DSL to provide a formal specification of it.

However I don't know how to do it!. Can someone provide me with an example?


texts: Can P=PSPACE and PSPACE problems be formulated as $\Pi_1$ formula?

texts:
To say simply, can PSPACE problems be written as $\Pi_1$ formula? Or how can these problems be written in terms of (first-order) arithmetic hierarchy?

edit:also currently, by what arithmetic hierarchy formula can P=PSPACE be written?

and what would be the consequence of being able to write P=PSPACE as $\Pi_1$ formula?


texts: Why do we assume that a nondeterministic Turing machine decides a language in NP in $n^k-3$ in Sipser's proof

texts:
At page 277 of Sipser's Introduction to the Theory of Computation, a proof of the NP-completeness of SAT is given.

The following comment is made on the trace of some machine $N$ which can decide a language $A\in\mathrm{NP}$:

"Next, we take any language $A$ in NP and show that $A$ is polynomial time reducible to SAT. Let $N$ be a nondeterministic Turing machine that decides $A$ in $n^k$ time for some constant $k$. (For convenience, we actually assume that $N$ runs in time $n^k-3$, but only those readers interested in details should worry about this minor point.)"
(p. 277)

Interestingly, Levin's paper, Universal Search Problems, which discusses the search version of computation (in contrast to the decision version) states:

"Two function $f (n)$ and $g (n)$ will be said to be equal if there exists some $k$ such that:
\begin{equation}
f (n) \leq (g (n) +2)^k\  \textrm{and} \ g (n) \leq (f (n) +2) ^k.
\end{equation}
The term less than or equal is defined similarly."
(p.1 of the paper)

Levin is sometimes co-cited with Cook for the proof of the NP-completeness of SAT (Cook-Levin theorem).

So what are those $2$ and $3$ constants? Are they even related or was it just an intuition? In conventional big-O notation, we would have said $\pm O(1)$. But here, both authors take the time to specify an exact constant, and both are discussing the notion of polynomial-time reduction.


texts:
I know that Big $O$ notation is used to describe the upper bound of running time of an algorithm, if we consider time complexity of that algorithm. However, I'm not sure why the following is not stated everytime anyone attempts to explain time complexity or Big $O$ - the fact we're looking for the least upper bound of the running time.

Correct me if I'm wrong, but $O(n!)$ is known to be the highest complexity - much worse than exponential. If I have an algorithm whose running time is $O(n)$, then it is also $O(n^2)$, $O(n^3)$, $O(2^n)$, and $O(n!)$, because they are all upper bounds of its running time (I know that, because it's $O(n)$).

So is it possible to find the least upper bound of the running time? If I read an algorithm has complexity $O(2^n)$, does it mean it has been proven this is the least upper bound? Or is it just the smallest upper bound that has been found so far?


texts: Update SSSPP solution on complete digraph on weight changes

texts:
I have a directed graph with $N$ vertices. Every pair of vertices is connected by two edges (one in each direction), and each of these edges has a weight which may be negative.

On various occasions 'edge update' operations occur, where the weight of an edge is modified (although the edge is never deleted, and no new edges or vertices are added). After each of these operations I wish to know the length of the shortest path between one 'root' vertex and every other vertex in the graph. I don't care what the path is, and I already know it must exist. I don't mind how negative weight cycles are handled.

I care about optimizing the running time of the single update operation and the $N$ queries that follow.

The obvious approach would be Bellman-Ford, which would take $O(|V||E|)$ which is $O(n^3)$.

Is there a faster way to do it?


texts: Shortest path in a dynamic tree with vertex updates

texts:
There is a tree with $n$ nodes. All edges are of equal weights. The vertices of the tree can be of two types: 0 or 1. There are two types of queries:

Set(X): change the given vertex X from type 0 to type 1,
Dist(X): find the shortest path from X to a node of type 1 and return the length of this path.  This will return zero if X is of type 1.

The naive method would be to just maintain a tree and on every update change the type of vertex; to answer queries of second type, run a bfs starting at X and stop as soon as a vertex with type 1 is found.  With this simple scheme, Set(X) would run in $O(1)$ time, but Dist(X) would take $O(n)$ time.

However, in my application the number of queries and number of nodes are both of the order of $10^5$, so the naive method is too slow.  In particular, $O(n)$ time is too slow.

Can somebody suggest a better algorithm for doing this?


texts: Why do you need to fill the first element of array when implementing heap?

texts:
I'm looking at Heap data structure implementation from different sources. What I found is that sometimes it's implemented with the first element of array set to magic (default, unused?) value.

For example here the first element is added in constructor.

And visualization here shows that it's also set to something magic.

However, I've seen many examples without the first element. What's the trick and why sometimes it's there and sometimes it's not?


texts: Can an intersection of two context-free languages be an undecidable language?

texts:
I'm trying to prove that

$\exists L_1, L_2 : L_1$ and $L_2$ are context-free languages $\land\;L_1 \cap L_2 = L_3$ is an undecidable language.

I know that context-free languages are not closed under intersection.

This means that I can produce an $L_3$, which is undecidable.

An example would be $L_1 = \{a^n | n \in \mathbb{N}\} \cap L_2 = \{0\} = \emptyset$.

Is this a correct proof?
If not, how can I prove this theorem?
Is the empty language decidable?


texts: Skienna's recursive algorithm for edit distance

texts:
I'm having some trouble understanding part of Skienna's algorithm for edit distance presented in his Algorithm Design Manual. I'm posting the recursive version, prior to when he applies dynamic programming to the problem, but my question still stands in that version too I think.

He provides the following code:

#define MATCH       0
#define INSERT      1
#define DELETE      2

int match(char c, char d)
{
    if (c == d) return(0);
    else return(1);
}

int indel(char c)
{
    return(1);
}

int string_compare(char *s, char *t, int i, int j)
{
        int k;                  /* counter */
        int opt[3];             /* cost of the three options */
        int lowest_cost;        /* lowest cost */

        if (i == 0) return(j * indel(' '));
        if (j == 0) return(i * indel(' '));

        opt[MATCH] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]);
        opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]);
        opt[DELETE] = string_compare(s,t,i-1,j) + indel(s[i]);

        lowest_cost = opt[MATCH];
        for (k=INSERT; k<=DELETE; k++)
                if (opt[k] < lowest_cost) lowest_cost = opt[k];

        return( lowest_cost );
}

I am having trouble understanding the logic behind how the indices are decremented when arriving at opt[INSERT] and opt[DELETE]. They seem backwards to me.

How can I prove to myself that they are correct?


texts: Proving that collision is less likely if the table size is prime in case modulo arithmetic is used

texts:
If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets,

  where m = table_length/GreatestCommonFactor(table_length, x)

Can someone help me to prove the above equation.

 Example for the above question would be:
 x = 3, table_length = 24
 m = 24/gcd(3,24) = 24/3 = 8

So 3%24 = 3  ->1
   6%24 = 6  ->2
   9%24 = 9   ->3
   12%24 = 12 ->4
   15%24 = 15 ->5
   18%24 = 18 ->6
   21%24 = 21 ->7
   24%24 = 0  ->8
   27 %24 = 3 ->1

From the above equation inference can be drawn that when

   table_length/GreatestCommonFactor(table_length, x) is 1,

i.e when x and table_length are co-prime, the distribution would be proper and will cover all the buckets.

Based on observation

exactly 8 distinct multiples of 3 modulo 8.
exactly 2 distinct multiples of 4 modulo 8
exactly 1 distinct multiple of 8 modulo 8
exactly 4 distinct multiples of 6 modulo 8
exactly 8 distinct multiples of 6 modulo 8

There are exactly LCM(n,c)/c = n/GCD(c,n)distinct multiples of c modulo n

Is a better way of proving possible?


texts:
Given an undirected graph with non-negative edge weights, and two vertices $s,t$ in the graph. I would like to find the minimal cut such that $s$ and $t$ are on different sides of the cut.
For example I have a graph describing the network of roads connecting Berlin and Munich and I want to find the minimal cut such that Berlin and Munich fall on different sides of the cut.
I know of an algorithm for global minimal cut (Karger), which wouldn't guarantee that $s$ and $t$ are not on the same side of the cut. The best thing I managed to find was this article for finding the s-t min-cut of a directed graph (flow network).
I think I can use the flow network algorithm to solve the problem by doing the following:

Make my undirected graph directed by replacing each edge with two directed edges.
Apply the "minimum s-t cut in a flow network" algorithm on step one's graph to find all edges of the directed s-t min-cut.
For the undirected case the s-t min-cut consists off all edges where at least of its directed was in step two's min-cut.

Is there a more efficient algorithm for this problem specifically for undirected graphs?
Thanks!


texts:
I'm curious on how to type a dependent pattern matching in a functional language. What should the rule for typing

match e with
| C_1 a_1_1 a_1_2 ... a_1_n1 -> e_1
| C_2 a_2_1 a_2_2 ... a_2_n1 -> e_2
| ...
| C_m a_m_1 a_m_2 ... a_m_nm -> e_m
end

be, where e is of type T, which has constructors C_i for each i.

I think that to prove that the pattern match has a type T', we need to prove
that each e_i has type T' under specific assumptions, but I can't quite pinpoint those assumption to add into the context.


texts: Concurrency: Is it order-independability or interruptibility of tasks?

texts:
After researching concurrency I am unable to discern if it is either of these specifically or it encapsulates both?

I was also wondering if someone could provide some programming applications/real world examples I am struggling to grasp the concepts entirely and it feels like every where I look people have different understandings.

Just two re-define the two concepts I believe it to be:

Order independent: There is 3 Tasks A, B and C they need to be completed for the application to finalize, and are able to be completed in any order.
Interruptible: Tasks are able to be halted mid processing in order to complete part of one of the other tasks.

Point 2 I am most uncertain about how is this advantageous for a serial application? I am guessing it would be to do with user input/bypassing locks or waits caused by requiring further information so other tasks can be completed.

NOTE: I am trying to apply these in a context outside of parallelism.


texts: What is the Big-Ω of the following function?

texts:
For the following function:

$$
\sum_{n=1}^{2n}x+x^2
$$

It is easy to see the (tightest) Big-Oh is $O(n^3)$, but I am not so sure about the Big-Omega. Here is my attempt:

$$
\sum_{n=1}^{2n}x+x^2
$$
$$
\geq \sum_{n=1}^{2n}x^2
$$

But not sure how to continue. Also, does tightest Big-Ω always equal tightest Big-Oh?

EDIT: The way I worked out the Big-Oh is shown below:

$$
\sum_{n=1}^{2n}x+x^2
$$
$$
\leq \sum_{n=1}^{2n}x^2+x^2
$$
$$
= \sum_{n=1}^{2n}2x^2
$$
$$
\leq 2n ( 2(2n)^2)
$$
$$
= 8n^3
$$

Therefore the Big-Oh is $O(n^3)$.


texts: Travelling Salesman Problem Easy Algorithms

texts:
I'm looking for a easier algorithm to implement to solve the travelling salesman problem (in javascript).
Unluckily all of the ones i found are really hard to understand/ to implement.

The ones i already have are the nearest/farthest-neighbour-algorithms. Do you guys have any other suggestions?


texts: Can I say is lossy compression to discard data having a way to recover it?

texts:
I'm working on a compression algorithm for a specific kind of data. I have found a way to discard (important) parts of the data during compression as I have also found a way to recover the missing parts during decompression.

The decompression algorithm most of the times will infer the data equal to the discarded one. However, in punctual cases, it will infer similar data that works just as well as the original.

So my question is: Can I claim that my algorithm is lossy?


texts: Functorial type constructors in System F

texts:
I have come across the claim that all basic data types in System F, such as Bool, Nat, and List(U), can be expressed in the form $\forall \alpha (((T\alpha \rightarrow \alpha) \rightarrow \alpha)$, where $T(\alpha)$ is a definable functorial type constructor.

Can someone explain why this is true or refer me to a proof? Because I have not found a proof for this claim yet.


texts: Is there an application area that sensors are on planes and we know the local positions of the sensors, but not the global positions?

texts:
I am currently writing the motivation of my thesis. And the answer to this question is very crucial for me:

I am working on wireless sensor networks.
Say that, there are a number of planes, for instance rooms inside a building.
There are sensors on these planes.
Is there any application area or sceniaro that gives me the local positions (positions on the planes) of the sensor but not the global positions?

In other words, can you tell me a scenario that we don't know where the sensors are (or which plane they are on) in 3D but we know where they are on their own plane?


texts: Balanced $\epsilon$-separated partitioning by a hyperplane

texts: Suppose we have $m$ points in $R^n$ and $\epsilon>0$ is a given constant. How can we find a hyperplane that the number of points that are $\epsilon$-close to it is minimum, with the constraint that it partitions the points to two sets of equal size. More formally, if the hyperplane is parametrized by $u^\top x = b$, in which $||u||_2=1$ is the unit vector orthogonal to the hyperplane. The constraint is that the number of points that is in the halfspace $u^\top x<b$ is equal to the number of points in $u^\top x<b$. Among all the hyperplanes that satisfy this constraint, we want to minimize over points that are in the space $|u^\top x - b|\le \epsilon$. Is there a relatively fast algorithm (quadratic or cubic at most) algorithm that solves this efficiently?


texts: Listing integers as the sum of three squares $m = x^2 + y^2 + z^2$

texts:
I would like to write an algorithm that lists all the ways a natural number $m \in \mathbb{N}$ can be written as the sum of three squares $m = x^2 + y^2 + z^2$ with integers $x,y,z \in \mathbb{Z}$.

Legendre's theorem says $m$ has such a representation if $m \neq 4^a(8b+7)$ with $a,b \in \mathbb{N}$.  See on MathOverflow:

Legendre and sums of three squares
Efficient computation of integer representation as sum of three squares

If I just wanted to count  the number of representations as the sum of squares, we could find formulas in the Online Encyclopedia of Integer Sequences:

A005875 - Theta series of simple cubic lattice; also number of ways of writing a nonnegative integer n as a sum of 3 squares (zero being allowed).
A074590 - Number of primitive solutions to $n = x^2 + y^2 + z^2$ (i.e. with $\gcd(x,y,z) = 1$).

How do I list the sum of squares representations for each $m$?  I would take a slower algorithm if it were easy to implement.

I considered just writing: $\boxed{m -x^2 -y^2 = z^2 }$ and looping over $0 < x < y < \sqrt{m} $ and checking it is perfect square.

Another possibility is keeping an array square writing square[x*x+y*y*z*z] += [[x,y,z]] storing triples in the appropriate place as I find them.  That is something like $m^3$ time since I loop over $0 < x,y,z < m$.

Do any solutions jump out at you?

10/12/17 Here I take a naive approach:

N = int(M**0.5)

z = [ (a,b,c) for a in range(N) for b in range(N) for c in range(N)
      if a**2 + b**2 + c**2 == M]

This rather slow, but I could get solutions in the range N=10000 in about 20 seconds.  Here I run it 100 times within a half-hour.

Sometimes, there is no solution.  How can I improve this to work quickly at $N \approx 10^6$ ?


texts: Is there any knapsack-based cryptosystem that hasn't been broken?

texts:
I took part in the development of a knapsack-based asymmetric cryptosystem, and am currently planing to launch a campaign to promote it.
Before we actually do, it occurred to me to research...
what were all the attempts of knapsack-based cryptosystem, ever devised and which of them have been broken?
Thanks in advance.


texts: How would you prove/disprove that $e^n = O(2n^2)$? It's unclear to me which function grows faster.


texts: Pseudo-Proof of Constrained Sudoku is co-np

texts:
The definition of CO-NP

  A decision problem X is a member of co-NP if and only if its
  complement X is in the complexity class NP. In other words,
  co-NP is the class of problems for which there is a polynomial-time algorithm that can verify "no" instances - wikipedia

Sparse-Language

  Where all strings have the form 1k, where "1" can be any fixed symbol.
  For example, the language {1, 111, 1111} is unary, as is the language
  {1k | k is prime}

  For a string s over an alphabet Σ, let shift(s) denote the set of circular shifts of s, and for a set L of strings, let shift(L) denote the set of all circular shifts of strings in L. If L is a cyclic code, then shift(L) ⊆ L; this is a necessary condition for L being a cyclic language.

  My algorithm follows a 3x3 shift language allowing valid Sudoku Grids. Valid grids up to 50x50 and seemingly 100x100 so far have been generated.

  Wikipedia,
  Cyclic language,
  Sparse Language

The language used by this algorithm is a 3x3 circular shift. A cyclic code of permutes allowing valid grid.

Constrained Sudoku Pseudo Proof

What I'm trying to do/Decision Problem

I'm trying to compare two grids. One non-constrained and the other constrained. Both grids are technically valid but within their own "class"

Determine if a valid Sudoku grid is of the conventional class or the constrained class following the shift(L) circular language.

As mentioned in the co-NP definition a decision problem "X" is a member of co-np if and only if its complement X is in the complexity class "NP." As said before, co-np is the class of problems for which a poly verifier can say no instances. The algorithm verifies no instances for grids. If it does not follow the circular language. It says, "not a constrained puzzle."  Therefore, Constrained Sudoku is co-np.

Assuming, that the cyclic language is maintained indefinitely.

  Cyclic Permutation

  let n = input

  let k = shift(L)

  Pn = (n-k)!

  (n-3)! == lim_(n->∞) 3 = 3

  In reduced form

  (n - 3)! = n->∞-k

Pseudo-Code

if indexes/elements match in grid and follows  shift(L) language:

                                   print "yes"
else:

                                   print "no"

Overall, is this sufficient proof that Constrained Sudoku is co-np?

Constrained Sudoku Algorithm


texts:
I am interested in all know classes of Computatinal problems. The Wikipedia article on computational problems types is incomplete. Some of the known classes are:

1- Decision problem such as 3SAT

2- Search problem such Factoring search problem

3- Function problem such as finding a second Hamiltonian cycle on a cubic graph (given some Hamiltonian cycle) which in TFNP

4- Optimization problem such as maximum independent set problem

5- Uniqueness problem such as Unique SAT problem

6- Another solution problem such as finding a second Hamiltonian cycle on a general graph (given some Hamiltonian cycle) which is in NP

7- Counting problem such as counting perfect matchings in bipartite graphs

8- Promise problem such as finding solution of SAT under the promise that it has a unique solution

9- Inverse problem such as Inverse 3SAT

10- Extendibility problem such as edge precoloring extension problem on bipartite graphs

11- Parity problem such as Parity-SAT

  What other types of computational problems should be added to the above list?

P.S. Some of the above can be cast as decision problem such as optimization problems.


texts: Multiple-Choice Questions about decidability

texts:
I'm working on old MC-Questions about decidability und don't have the answers to the following ones:

1.) $L_1$ and $L_2$ are not decidable $\Rightarrow$ No superset of $L_1 \cup L_2$ is decidable

2.) For Turing-acceptable languages L is "L = $\emptyset$" a non-trivial property.

3.) There are context-free languages $L_1$ and $L_2$ so that $L_1 \cap L_2$ is not decidable.

4.) $L$ is decidable $\Leftrightarrow$ $L \le \{0\}^* \cdot \{1\}^*$

I think 1.) is false, because $\Sigma^*$ as a superset of many undecidable languages for example is decidable and 2.) is true, because there are Turing-acceptable languages with (exactly one) and without the property. I have no idea at 3.) and 4.).


texts: Prove that determining whether a Turing machine ends in polynomial time on any input is undecidable

texts:
I'd like to prove by reduction that given a Turing machine $M$, there exists no Turing machine that decides whether $M$ ends in polynomial time on any input.

Any idea as to what problem to reduce, as a first hint?


texts: Number of rounds in interactive proofs - Arora & Barak

texts: In the web draft of Arora and Barak, "Computational Complexity: A Modern Approach", the way I understand their definition of a round of interaction is that it consists of either the verifier or the prover sending a message. In other sources on the matter, it seems to me that a round consists of both the verifier and the prover sending a message. Could someone clarify which of the definitions is the one that is usually used?


texts: Single Input Single Output Sequential Circuit Explanation Required

texts: I'm a student of Formal Methods in Software Engineering, I'm trying to study this question for two days but still haven't figured it out, I couldn't even find a similar solution or explanation, so please if anyone can explain in detail the question and it's solution I've provided in the image, it'll be a real help. One last thing, my guess is that the solution provided in the image is not correct, or maybe its my logic that isn't, so please help me with this. Thank You.


texts: TM for Language With a Specific Cardinality

texts:
I'm curious about how to build TM that decide and recognize languages defined by cardinality. For example, with the language $L_1$ = $\{w \in \{0,1\}^* | |w| = 1\}$ this is the language with a single string. It is finite so we know that is it decidable and we can build a decider $A$ that determines whether there is a DFA with at least 1 state for 1 string.

However, how to we build TMs to describe a language that isn't finite but countable infinite like $\{w \in \{0,1\}^* | |w| > 100\}$? Wouldn't this be like $\{0,1\}^*$? Even though we can represent this as a DFA with a single accept state and self loop the computation has no end in that it goes through strings forever, therefore, this would be undecidable, right? How then would we build a TM that ensures that we have at least 100 strings in this language?


texts: Permuting integer vectors $x$ and $y$ which add to integer vector $z$

texts:
I posted this on mathoverflow but haven't recieved any comments. I wonder if there might be some insight from this community. Thanks!
The problem
Suppose you have nonnegative integer vectors of length d,  $x$, $y$, $z \in \mathbb{Z^+}^d$. We know that $\sum_{i=1}^d x_i + y_i = \sum_{i=1}^d z_i$. I wish to find permutation matrices $\Pi_1$ and $\Pi_2$ such that
\begin{align}
\Pi_1 x + \Pi_2 y = z
\end{align}
without enumerating all possible permutations. If there is a solution, I'd like to know in as few steps as possible. If the solution is not unique, I'd like to know all permutation pairs which satisfy the above (or have an efficient means of enumerating them)
More context:
$x$ and $y$ actually represent integer partitions, and I actually have many $x$'s and many $y$'s for any given $z$, and will have to check all possible $x, y$ pairs for the given $z$.
Things I've tried:

We can immediately rule out some $x, y$ pairs using majorization. Let $\tilde{x}$ and $\tilde{y}$ be the sorted versions of $x$ and $y$. I can show that $\tilde{x} + \tilde{y}$ majorizes all other permuted sums of $x$ and $y$. If $z$ majorizes $\tilde{x} + \tilde{y}$ (and is not equal to it, modulo permutation), then it majorizes all permuted sums of $x$ and $y$, so there is no solution. Similarly, $\tilde{x} + \text{reverse}(\tilde{y})$ is majorized by all other permuted sums. If $z$ is majorized by $\tilde{x} + \text{reverse}(\tilde{y})$, then it is majorized by all permuted sums and there is no solution. By partially ordering all the $x$'s using majorization and doing the same for $y$, this method potentially knocks out many pairs without having to check them all.
We can avoid checking all pairs of permutations by using sorting.
Let $\tilde{x}$ be the sorted version of $x$ and let $\widetilde{\Pi}_x$ be a permutation which sorts $x$, i.e.  $\widetilde{\Pi}_x x = \tilde{x}$.
Enumerate all unique permutations of $y$, and subtract them from $z$.
Sort each difference vector, and compare it against $\tilde{x}$.
Given a match, $\Pi_1$ and $\Pi_2$ can be determined by the permutation of $y$ and the permutation which ``unsorts'' $\tilde{s}$.
Formally, suppose for some permutation $\Pi^*$, $s = z - \Pi^* y$ with $\tilde{s} = \tilde{x}$.
Then $\Pi_1 = {\widetilde{\Pi}_s}^{-1} \widetilde{\Pi}_x$ and $\Pi_2 = \Pi^*$.
I've found a reduction of the problem to filling in count matrices with specified row, column, and diagonal margins, but haven't found efficient ways of solving that problem. Please chime in if you have thoughts on this. I can say more about this if relevant.

I realize this question is somewhat algorithmic in nature, but I'm hoping there is some relevant area of mathematics that could help. I've tried to think about this from the perspective of symmetric groups, the elementary basis for symmetric functions, general equivalence classes, but I'm not getting very far. Any help or suggested directions would be appreciated!


texts: Undecidability of REGULAR_TM (Detail within Proof)

texts:
I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book.

The example shows how $REGULAR_{TM}$, defined as the problem of determining if a Turing machine recognizes a regular language, is undecidable. The way they do it is by showing a reduction from $A_{TM}$, which is the acceptance problem for Turing Machines (the acceptance problem for some computational model is the task of determining whether or not it accepts a given input string).

From what I understand, all that needs to be done is show that if $REGULAR_{TM}$ was decidable by some TM $R$, then another TM could use $R$ to decide $A_{TM}$, which would be a contradiction, since $A_{TM}$ is undecidable.

They construct a TM $S$ that can be used to decide $A_{TM}$. Where I'm lost is through their use of an intermediate TM, $M_2$. Here is the full description:

$S$ = "On input $\langle M, w\rangle$, where $M$ is a TM and $w$ is a string:

Construct the following TM $M_2$.

$M_2$ = "On input $x$:

If $x$ has the form $0^{n}1^{n}$, accept.
If $x$ does not have this form, run $M$ on input $w$ and accept if $M$ accepts $w$."

Run $R$ on input $\langle M_2 \rangle$.
If $R$ accepts, accept; if $R$ rejects, reject."

My two main questions are:

Why are we allowed to do step 2 in the construction of $M_2$? If we could just say "run $M$ on $w$ and accept if $M$ accepts", then wouldn't that be a way to show that $A_{TM}$ is decidable?
What exactly is the role of step 1 in the construction of $M_2$? The book says that the purpose of this TM is not to be run, but just to feed its description into $R$. The TM recognizes $\{0^n1^n\mid n \ge 0\}$ if $M$ does not accept $w$, and $\Sigma^*$ if it does, but I don't see how it does that from the description. Also, I don't see how $A_{TM}$ can be decided by using this (I'm thinking it's that the TM $M_2$ only outputs a regular language if the TM $M$ accepts $w$, but I don't understand how it can do that).

Any help is greatly appreciated, thanks!


texts: Extracting Boolean Function using Machine Learning

texts:
How can machine learning help extract a Boolean relationship in a given binary input-output data set?

Let us assume that the given data set is exhaustive - ie. it cover all possible input combinations, can we derive the boolean relationship between inputs and outputs? (Say we assume x inputs and 1 output)

Further, if the dataset is not exhaustive, can we predict the output for "(n+1)"th input vector if we know outputs for the previous "n" input vectors? (in other words, can we "learn" how the function behaves?)

I'd greatly appreciate if you can share what approach should I devise to work on this problem, and if possible, about any on-going research on this topic?

UPDATE: As rightly pointed out by @D.W.
Several heuristics exist to tackle such NP-hard problems in logic synthesis and minimization.

The essence of my question is to find out if any Machine Learning algorithm can be adopted and developed, which potentially performs better than the currently known heuristics when deployed at scale.

And importantly, if any "recent" advances in ML can be of help in developing tools for Electronic Design Automation?


texts:
Construct a context-sensitive grammar that generates L:

L = {a^n b^m c^k|k>n, k>m}

I believe my productions should go along this lines:

S-> ABCC
A-> a|aBC|BC
B-> b|bBC
C-> c|Cc
CB->BC

The idea is to start with 2 c and keep always one more c, and then with C->c|Cc ad as much c as i want.
How can my production for C remember the numbers of m and n.


texts: Efficient algorithm to compare arrays problem

texts:
I was submitted an interesting problem, but I wasn't able to find a solution.

Define a function p(x, y) that takes int x and y, with y > x and returns an int.

p(x, y) = x & (x+1) & (x+2) & ... & (y-1) & y

There are then two arrays X of length N and Y of length M representing x and y, in binary with M >= N > 0. X and Y are consistently indexed, so that X[0] and Y[0] represent the least significant digit of x and y.

The final goal is to write an efficient algorithm that computer p(x, y). The ideal solution would be to have a time complexity of O(M) and a space complexity of O(M).
We can assume that the bitwise AND operator is already implemented with a complexity of O(M) in both time and space. There's also no need to work on the binary representation of the numbers. Pseudocode is fine.


texts: Why the given lexical specification will not process the following strings?

texts:
I'm taking a Compiler MOOC on my own time. The class is self paced. An answer was given to a question but I can't understand the answer. In fact I'm not even sure how to interpret the question.
Here is the question:

Given the following lexical specification:
$(00)^*$
$01^+$
$10^+$
Which strings are NOT successfully processed by this
specification?

$0111110$
$01100110$
$0001101$
$01100100$

The correct answers are 1 and 2. But I can't figure out why. How do I interpret this lexical specification? Can someone help me out with this.


texts: Are genetic algorithms special instances of random search done in an unexpectedly short run-time?

texts:
I was wondering since randomness is embedded in genetic algorithms at almost every level, is there a really fine line between genetic algorithms and pure random search?

Ever since I finished my implementation of a GA , since randomness is present in the mutation function,the initialization part (as well as the reinitialization part) and crossbreeding part as well... other than a encoder which tries to sense of the chromsomes (encoder tailored to make sense of the chromosome in context of the problem) and a fitness function , it feels like genetic algorithms are just random search functions in disguise .

So my question is : are GA implementations just plain old random searches with a shot of memory to make it look like there is some sort of meaningful feedback?


texts: Uncapacitated facility location problem using local search

texts:
I'm studying about UFLP using the book The Design of Approximation Algorithms Ch 9 starting page 233 (there is an electronic free edition), I ran into some unclear steps in the book and need some help with it.
In few words the UFLF deals with finding a subset of facilities from a given set of potential facility locations to meet the demands of all the customers such that the sum of the opening cost for each of the opened facilities and the service cost (or connection cost) is minimized
We can do the following local steps on current solution:

We can open one additional facility an “add” move.
We can close one facility that is currently open a “delete” move.
We can do both of these simultaneously a “swap” move.

Let's assume we have optimal solution and let $S^*$ be its open  facilities, and let $\sigma^*$ denote the corresponding optimal assignment of clients to open facilities. To compare the cost of this optimal solution to the current, locally optimal solution of the algorithm, we let $F$ and $F^*$ denote, respectively, the total facility cost of the current solution and the optimal one, and similarly let $C$ and $C^*$ denote their respective total assignment costs. The optimal value OPT is clearly $F^*+C^*$. Note that now $F$ stands for both the set of facilities and the cafility cost of the current solution, but the meaning at any given point should be clear from the context.

What I need help with:

Lemma 9.1: Let $S$ and $\sigma$ be a locally optimal solution. Then $$ C \leq F^* + C^* = \mathrm{OPT}. $$

Proof from the book page 235:

Consider some facility $i^* \in S^* - S$, and suppose that we open the additional facility $i^*$, and reassign to that facility all of the clients that were assigned to $i^*$ in the optimal solution: that is, we reassign all clients $j$ such that $\sigma^*(j) = i^*$. Since our current solution $S$ and $\sigma$ is locally optimal, we know that the additional facility cost of $i^*$ is at least as much as the improvement in cost that would result from reassigning each client optimally to its nearest open facility; hence, $f_{i^*}$ must also be more than the improvement resulting from our specific reassignments; that is, $$ f_{i^*} \geq \sigma_{j\colon \sigma^*(j) = i^*} (c_{\sigma(j)j} - c_{\sigma^*(j)j}). $$

Not clear what is "open the additional facility $i^*$".
Isn't $i^* \in S^*$ already open? Where does this facility open? in $S$? If so, why is it marked with a star? Doesn't that stand for the optimal solution?
I also need help with:
Proof from page 237:

Let $\phi(i^*)$ denote the facility in $S$ closest to $i^*$.
Lemma 9.3: Let $S$ and $\sigma$ be a locally optimal solution. Then $$F \leq F^* + 2C^*.$$
Consider a facility $i$ that is not safe (or, in other words, is unsafe), and let $R \subseteq S^*$ be the (non-empty) set of facilities $i^* \in S^*$ such that $\phi(i^*) = i$; among those facilities in $R$, let $i’$ be the one closest to $i$. We will derive one inequality for each member of $R$, based on an add move for each member of $R - \{i’\}$, plus one swap move closing the facility at $i$, while opening a facility at $i’$.
First let us derive an inequality for each add move corresponding to $i^* \in R - \{i’\}$. As in the proof of Lemma 9.3, we open a facility at $i^*$, and for each client $j$ that is assigned to $i$ in the locally optimal solution and is assigned to $i^*$ in the optimal solution, we reassign client $j$ to $i^*$. The change in cost caused by this move must also be non-negative, and we derive the inequality $$ f_{i^*} + \sum_{j\colon \sigma(j) = i \text{ & } \sigma^*(j)=i^*} (c_{\sigma^*(j)j}-c_{\sigma(j)j}) \geq 0. $$

If the function returns the nearest facility in $S$, what is the meaning of choosing $i'$? Isn't it just one facility that is the closest in $S$? I mean isn't $R$ of size 1? (line 2)
There is a typo and it's not Lemma 9.3 but Lemma 9.1 in the second paragraph, my second question here is also similar to the first question: what is $i^*$ here?
Any clarification will be happily welcome.


texts: Choosing a shortest representative number from interval in arithmetic coding

texts:
In arithmetic coding a word is coded as the binary encoding of a number in a certain interval. The interval is determined from a sequence of nested intervals according to the probability distribution on the letters of the word.

This encoding and decoding process is totally clear to me, but what wonders me is how an encoder chooses the optimal number (i.e. the one with shortest length if written in binary)?

For example, in the above linked wikipedia article in the paragraph Sources of Inefficiency in the example they choose 0.538 as the message, which is not optimal as it has quite a long (way longer than 8 bits) binary expansion when written in binary, as also noted choosing 0.5390625 would be much better.

Also, if we change the probability model with a uniform distribution we get $(5/27, 6/27)$ as an interval, as shown in the paragraph the binary codings of the boundaries are quite long, much longer then the $~5$ bits, but if we choose $0.1875$ then this could be coded with $0.0011$ which requires five bits if we submit $00110$ (the final $0$ seems to be necessary for the decoder as discussed in the paragraph).

So choosing the right number in the interval is in my understand the key of the compression algorithm (also backed up with the intuitive understanding that if we have a larger interval; which is given by higher probabilites from individual tokens, then we have more possibilites to choose numbers from to find one with a short binary expansion), but every textbook or notes I find just concentrates on describing the interval nesting procedure, but not how to choose a shortest representative?

So, if my understanding is correct this seems to be an essential part? So how to achieve this?


texts: Why do ¬, ∀ and ∃ have the same precedence?

texts: I thought the order of precedence of operators and quantifiers was arbitrary, but I don't really understand why those three have the same "strength" in relation to other operators (e.g., ¬ will have precedence over ∧, but not over ∀). This leads to the rule being that ¬, ∀ and ∃ will bind to the closest predicate on their right (if I understood correctly). Why is this?


texts: Write a regex to match string that does NOT contain a certain pattern

texts:
Let's say our alphabet is 0 and 1.

How would you approach writing a regex to generate a language of words that do NOT contain 101.

The only regex operators allowed are concatenation , star * and OR |.

I am stuck now and I want to know if anybody has an idea.


texts: Searching for multiple partial phrases so that one original phrase can not match multiple search phrases

texts:
Given a predefined set of phrases, I'd like to perform a search based on user's query. For example, consider the following set of phrases:

index      phrase
-----------------------------------------
0          Stack Overflow
1          Math Overflow
2          Super User
3          Webmasters
4          Electrical Engineering
5          Programming Jokes
6          Programming Puzzles
7          Geographic Information Systems

The expected behaviour is:

query         result
------------------------------------------------------------------------
s             Stack Overflow, Super User, Geographic Information Systems
web           Webmasters
over          Stack Overflow, Math Overflow
super u       Super User
user s        Super User
e e           Electrical Engineering
p             Programming Jokes, Programming Puzzles
p p           Programming Puzzles

To implement this behaviour I used a trie. Every node in the trie has an array of indices (empty initially).

To insert a phrase to the trie, I first break it to words. For example, Programming Puzzles has index = 6. Therefore, I add 6 to all the following nodes:

p
pr
pro
prog
progr
progra
program
programm
programmi
programmin
programming
pu
puz
puzz
puzzl
puzzle
puzzles

The problem is, when I search for the query prog p, I first get a list of indices for prog which is [5, 6]. Then, I get a list of indices for p which is [5, 6] as well. Finally, I calculate the intersection between the two, and return the result [5, 6], which is obviously wrong (should be [6]).

How would you fix this?


texts: Find an algorithm that sorts the nodes of a given graph acc. to distance from source node + value of the node's key

texts:
an unweighted connected graph $G=(V,E)$ all nodes of the graph contain a "serial number" between 1 to V. (V is an integer).

I am trying to come up with an algorithm that sorts all nodes firstly by distance (number of eadges) from source node 's' , secondly- if two nodes have same distance value sort them by value of thier serial number.

complexity required is $O (V+E)$

I tried to solve this via using bfs and then recieve a "bucket" array of distances - for each distance $1,2...$ all nodes within it are in its "bucket".
the problem is, that in order to sort two nodes with same distance according to
their serial number takes at least $O( nlogn)$ of sorting.
 I tried to come up with a use $v-1$ empty arrays and tried to send each "bucket" nodes acc. to their index in the graph and print it - that takes )$V^2$.

This is NOT homework, I really did try my best.
Your comments are appreciated.


texts: If the Halting Problem was solvable, and we solved it, what would be its implications?

texts:
Perhaps a way to better understand the Halting Problem's importance is to know what would happen or what could be possible if this was solved.
What would be the Halting Problem's implications in today's technology, mathematics and its practical applications, if it was somehow solved?


texts: Is the empty problem (or its complement) Karp reducible to any problem in NP?

texts:
I'm currently following a course on Complexity Theory, and whilst studying, I came across a rather counterintuitive statement:

If $\textbf{P}=\textbf{NP}$, the following holds:

For every $A \in \textbf{NP}$, there is a $B \in \textbf{NP}$ such that $A \leq B$ (where $\leq$ means Karp reducible).

However, I do not understand how this applies to the empty problem $\emptyset$, and it's complement $\Sigma^*$, as these only have no-instances and yes-instances, respectively.

Are there other problems in NP such that these two are reducible to them?


texts: How machine learning libraries are created?

texts:
I would like to know how machine learning libraries (or in general libraries at large scale) are created. I mean Python doesn't have inbuilt array system but c has. So how they are supported for Python and how do they start the thing and develop it as we know today as a final product (like NumPy) ?

P.S.- Let me know if this is not the right community for asking general computing questions because there is significant overlap among CS stack exchange forums and if it's not right place then recommend the appropriate stack exchange platform for asking general computing questions.

Also, I couldn't find relevant tags so had to tag it with machine learning.


texts: Complexity of Two problems graphs with cycle

texts:
I want to determine the complexity of these two problems (with a given k):

1) Determine if the graph G has a cycle of length less or equal than k;

2) Determine if the graph G has a cycle of length equal or more than k.

For the first problem, I think it is NP-complete because it is NP (but why?) and because we can reduce the HAM-CYCLE problem to it (but how?)

I don't know what to say about the second problem. Can you help me solving this and can you help me telling me what is a good method to solve these kind of problems?


texts: Rice's theorem application on a language that resembles ETM

texts:
I'm working on an exercise that involves checking if the Rice's theorem can be applied on a two languages.

The first language is $E_{TM} = \{ \langle M \rangle \text{ | M is a Turing Machine and } L(M) = \emptyset \} $.

I already know it's undecidable, thus Rice's theorem should apply without any problem and in fact it checks the three theorem's requisite just fine.

The second language is $X = \{\langle M \rangle \text{ | M is a Turing Machine that does not halts on any input string \}}$.

To me, the fact that the TM does not halts on any string means that the language is empty, which means that X is similar if not equal to $E_{TM}$.

But the property stated in X is not on the language of the TM, but rather describes what it does on all possible strings.

Is this reasoning correct?

Thanks for your help.


texts:
Let $(P)$ an Integer Linear Program, where we aim to find $x\in \{0,1\}^n$ maximizing a linear function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ under some linear constraints $Ax\le b$

Let $(P^*)$ be its relaxation, which means that the constraint $x\in \{0,1\}^n$ is replaced by $x\in [0,1]^n$.

Then, suppose that we know that
$$
\max_{x\in \{0,1\}^n} \left\{f(x), Ax\le b\right\} = \max_{x\in [0,1]^n} \left\{f(x), Ax\le b\right\}
$$

Is it possible, given an optimal solution $y^*\in[0,1]^n$ of $(P^*)$ (that we have found with simplex algorithm for instance), to find an optimal solution $y\in\{0,1\}^n$ of $(P)$ (i.e. such that $f(y)=f(y^*)$ and $Ay\le b$),  say in polynomial time ? Or is there any concrete conter-example ?


texts: How can I formalize key value stores with set theory?

texts: I'm currently developing a simple key-value NoSQL store and want to build its formal model. I found article about key value formalisation with category theory, but I'm interested are there some works about formalisation of key-value stores except category theory (I know we can use it for all, but...)? I want to use some more simple and lightweight mathematics for mathematical description of key-value stores. And I feel that set theory will be enough for this, but couldn't find any helpful articles.


texts:
A theorem says if $f$ is a computable function and we can prove $x \in A \Leftrightarrow f(x) \in B$, then we can use reduction so $A \leq_m B$.
But i'm confused if should I prove if :

$(x \in A \Rightarrow f(x) \in B )\land (f(x) \in B \Rightarrow x \in A)$

Or

$(x \in A \Rightarrow f(x) \in B ) \land(x \notin A \Rightarrow f(x) \notin B)$

in which circunstances because I've seen both in demonstration. Or maybe are they equivalent ?
For example, here is a solution to the empty string problem. But with $f$ such as, $f: \text{M accepts w} \to \text{M accepts } \epsilon \\ f(\langle M, \epsilon \rangle) = \langle M \rangle$, we can proove 1. Is it valid ?


texts: A question about domains in Karp reductions

texts:
A basic question or request for clarification regarding Karp reducibility:
Let $\Sigma^*$ be the set of all finite strings of 0's and 1's.  Call a subset of $\Sigma^*$ a language.  Let $\Pi$ denote the set of all functions from $\Sigma^*$ into $\Sigma^*$ that are computable in polynomial time.  According to Karp, a language $L$ is reducible to a language $M$, also denoted $L \leq_K M$, if there is a function $f \in \Pi$ such that $f(x) \in M \Leftrightarrow x \in L$.
For many problems, however, we are interested in the difficulty of determining membership in subsets of domains other than $\Sigma^*$.  To address this, Karp briefly discusses encodings:  Given a domain $D$, there is often a natural "one-one" encoding, $e: D \rightarrow \Sigma^*$.  He then says that given a set $T \subset D$, $T$ is recognizable in polynomial time if $e(T) \in \mathcal{P}$.  But don't we, in practice, typically consider $T$ to be recognizable in polynomial time if, for any $x \in D$, we can determine whether $x \in T$ in polynomial time?  On the face of it, this doesn't seem to be the same as Karp's definition, since there is no guarantee that $e(D) = \Sigma^*$.
Similarly, according to Karp, $T \leq_K U$ where $T \subset D$ and $U \subset D'$ if $e(T) \leq_K e'(U)$ where $e: D \rightarrow \Sigma^*$ and $e': D' \rightarrow \Sigma^*$.  However, when we are actually proving $T \leq_K U$ for some real $T$, $U$, $D$, and $D'$, don't we frequently just define an $f: D \rightarrow D'$ computable in polynomial time, confirm that $f(x) \in D'$ for any $x \in D$, and show that $f(x) \in U \Leftrightarrow x \in T$ for any $x \in D$?  Again, this doesn't seem to be the same thing as Karp's definition if $e(D) \neq \Sigma^*$.
What am I missing?


texts: What is the psuedo-code for Tremaux's Algorithm as a Depth First Search to solve a maze?

texts:
I was interested in the Tremaux Algorithm as a Depth First Search to solve a Maze.
Unfortunately I was not able to understand what Data Structures are and how they could be used.

For example, I saw a YouTube video which shows the process of solving a Maze using the Tremaux Algorithm but I did not understand what data structures are and how they could be implemented to mark the shortest path to reach the final destination.

Thank you for your time and help in advance.


texts:
I have a question regarding performance of 2-opt and 3-opt algorithms.

I tried implementing the 3-opt and 2-opt algorithms and most of the time 3-opt outperforms the 2-opt algorithm around 5%.

Surprisingly, in few cases my 2-opt algorithm outperforms the 3-opt algorithm. I am wondering, is it some kind of error or it may happen that the 2-opt algorithms sometimes end in the better local optimum?

(I know that if solution is 3-opt, then it is also 2-opt. But we can find multiple 2-opt or 3-opt solutions in the same route, don't we?)


texts: Figuring out the language of a non-linear CFG

texts:
I have the CFG G with the following production rules:
$$
S \to aSaS \mid b
$$
Is it possible to find $L(G)$? I have no idea how describe it by any pattern. I use grammophone to check example words, but it's not very helpful tho.


texts: Syntax Directed Translation Scheme for Postfix to Infix Notation

texts:
I'm reading Compilers Principles, Techniques and Tools textbook and I encountered a problem from exercise 2.3

We have to construct a syntax-directed translation scheme that translates arithmetic expression from postfix notation into infix notation. I constructed a scheme the following way.

expr -> expr expr + | expr expr - | expr expr * | expr expr / | digit

into

expr -> expr {print('+')} expr +
      | expr {print('-')} expr -
      | {print('(')} expr {print(') * (')} expr {print(')')} *
      | {print('(')} expr {print(') / (')} expr {print(')')} /
      | digit {print(digit)}

The translation seems pretty valid, but I can't figure out how to construct parse tree using that translation.

Can anyone explain me how to construct parse tree for 2 3 + 3 5 3 * - * and 9 5 2 * -? Thanks in advance!


texts: Power of Multi Tape and Multi Track Turing Machine

texts: How can we prove that the computational power of Multi Track and Multi Tape Turing Machine is same as the Normal or Standard ( One Tape- One Track- One Head) Turing Machine?


texts: Proving that a property is k-inductive with an SMT solver (parametric resettable counter)

texts:
I'm following the slides at https://homepage.cs.uiowa.edu/~tinelli/talks/FT-11.pdf where Tinelli explains how k-induction works in the context of SMT based model checking.

A parametric and resettable counter is given as a Kripke structure by the following formulas:

Variables:

$x := (c, n, r, n_0)$, where:

$n_0$ is a positive integer (input)
$r$ is a boolean (input)
$c$, $n$ are integers (internal variables)

Initialization:

$I[x] := (c = 1) \wedge (n = n_0)$

Transitions:

$\begin{align*}
 T[x,x'] := (n' = n) & \wedge (& (r' \vee (c=n)) & \to (c' = 1)) \\
                     & \wedge (& \neg(r' \vee (c=n)) & \to (c' = c + 1)) \\
\end{align*}$

Property to prove invariant:

$P[x] := c \le n + 1$

Tinelli uses the following notation:

$I^i:=I[x^{(i)}],P^i:=P[x^{(i)}],T^i:=T[x^{(i−1)},x^{(i)}]$.

He then claims on page 52/90 that the formula $P := c \le n+1$ is an invariant of this system because $P$ is 1-inductive (while incidentally not being 0-inductive). If I'm following correctly, this means that $I^0 \models P^0$ and $I^0 \wedge T^1 \models P^1$ (base case) and $P^0 \wedge P^1 \wedge T^1 \wedge T^2 \models P^2$ (inductive step). In particular it means that the formula $P^0 \wedge P^1 \wedge T^1 \wedge T^2 \wedge \neg (P^2)$ is UNSAT. However, after playing a little with Z3Py I was able to find the following model for this formula and a corresponding representation of a state transition trace with $(c,n,r)$:

$c^0 = -1, n^0 = 0, c^1 = 1, n^1 = 0, r^1 = \text{True},c^2 = 2, n^2 = 0, r^2 = \text{False}$
$(-1, 0, *) \to (1, 0, \text{True}) \to (2, 0, \text{False})$

Intuitively this makes sense. The constraint on $n_0$ being a positive integer affects the base case formula $I^0$ but not the inductive step, and therefore the above model is a valid model of the induction formula for $i=1$ which means the implication fails.

Of course $P$ is an invariant of this system, but it would seem to me that we cannot show it with k-induction for k = 1.

What is the gap in my understanding of this material?


texts: Can You List the Names of Some Algorithms For Determining the Intersection of Two Context Free Grammars?

texts:
Suppose we have two sets of strings XS and YS such that set XS is described by grammar GX and YS is described by grammar GY.

We want an algorithm which accepts GX and Gy as inputs. The algorithm will return true if the intersection of sets XS and YS is non-empty and will return false otherwise. We do not need to know exactly what the intersection is. It is possible that the intersection set is massive, so returning a container of all elements is unreasonable. Describing the intersection as a grammar is okay as long as it's apparent whether the grammar actually describes a non-empty set of string or not.

Just the name of the algorithm is fine if a Google search using that name will bring up the result. If the algorithm is obscure, additional information would be helpful.


texts: Fast algorithms that work on some large percentage of possible inputs

texts:
I've been wondering if research of these algorithms exists. An example, let's say I'm fine with $p$% of possible inputs of size $n$ to be unsorted. Is there an algorithm that would allow me to sort $n$ integers in sublinear time with a guarantee that $(100-p)$% of all possible inputs will be sorted.

Algorithms don't have to be linked the sorting, let's say it's optimization, is there an algorithm that will find the optimal tour for 1% of all TSP inputs of size $n$ really fast and what that algorithm is?

Is there a fundamental reason why these algorithms shouldn't exist or are hard to analyze?


texts: Why say that breadth-first search runs in time $O(|V|+|E|)$?

texts:
It's often stated (e.g., in Wikipedia) that the running time of breadth-first search (BFS) on a graph $G=(V,E)$ is $O(|V|+|E|)$.  However, any connected graph has $|V|\leq |E|+1$ and, even in a non-connected graph, BFS will never look at a vertex outside the component that contains the start vertex.  That component contains at most $|E|$ edges, so it contains at most $|E|+1$ vertices, and those are the only ones that the algorithm will visit.

This means that $|V|+|E|\leq 2|E|+1$, so why don't we say that the running time is just $O(|E|)$?

This came up in comments on a question about the running time of Disjkstra's algorithm.


texts: How to count number of 1s of the first k positions in a bitset (bitmap)?

texts:
Input: Given a bitset $b$, which is is an array of 0s and 1s, of length $L$, and a positive integer $k$.

Output: the total number of 1s in the first $k$ position of $b$.

Obviously it can be done in $O(k)$, is there any more efficient way in C++ such as $O(\frac{k}{W})$, where $W$ is the word size of the machine? Note that the popcount instruction only works when $k=L$, but $k$ is varying.


texts: Why default TCP Maximum Segment Size is 536? If found this line in TCP/IP by behrouz forouzan


texts:
I was reading 'Category Theory for Programmers' by Bartosz Milewski and got really confused by the implementation of bimap in Bifunctor typeclass.

class Bifunctor f where
    bimap :: (a -> c) -> (b -> d) -> f a b -> f c d
    bimap g h = first g . second h
    first :: (a -> c) -> f a b -> f c b
    first g = bimap g id
    second :: (b -> d) -> f a b -> f a d
    second = bimap id

This is the definition of the Bifunctor typeclass taken directly from the library Control. If bimap evaluates to first and second, which in turn evaluates to bimap itself, how is this supposed to end? Could you please explain how the evaluation of bimap works? Thank you!


texts: Does domination rule apply for inadmissible heuristics?

texts:
Let's say $h_1(n) \geq h_2(n)$ so that dominance is established even if $h_1$ and $h_2$ are both inadmissible/non-optimal heuristics -in whichever given search space.

Is $h_1$ still faster/better than $h_2$ or does the dominance rule only apply to admissible heuristics?

Also, if I could ask for a bit of extra help, can you provide a link/reference to an academic material that establish this relationship between dominanation and inadmissibility? Thank you!


texts:
This are two sections from a task I got.

  The Young tableau is defined as a matrix of m rows on n columns so that
  the bars in each row are sorted in ascending order Left to right and
  the elements in each column are sorted in ascending order from top to
  bottom. Some of the elements in the Young tableau may be $\infty$ we
  will refer to these elements as non-existent elements . Therefore, the
  Young tableau can be used to hold finite numbers.

  Write an algorithm for EXTRACT-MIN on a non-empty Young tableau of m at n in time running  $O(n+m)$
  Show how to insert a new element into a non-complete Young tableau v at the size of m at n in time running  $O(m+n)$

That's what I tried:

When I remove the element at the $(1,1)$ I need to move every element in the table 1 step left (and if the col is 1 so move one row up and put it on the last col) so I can solve it on $O(n*m)$. I think that $O(m+n)$ actually measn $O(max(m,n))$

Regarding the second clause I was thinking to compare the element to insert with the element in the first col in every row until until we get to bigger one and then and then check on this row where to insert it. But again let's say that I want to insert element which will be the min on the new table, so I need to push all the elements one stop left and it takes $O(m*n)$


texts: For complexity classes A and B, what does $A^B$ mean?

texts:
What does $A^B$ mean where A and B are complexity classes?

The "Polynomial Hierarchy" page says:

$A^B$ is the set of decision problems solvable by a Turing machine in class A augmented by an oracle for some complete problem in class B

In that case what is a Turing machine in class A?

(besides just a machine of some sort that can solve problems in A, because that doesn't give any insight as to what it means to augment such a machine with an oracle)

The motivation for this question was: What is a Turing Machine in class coNP.


texts: Scheduling / Queuing jobs with multiple different workers

texts:
I have a stream of jobs (so I don't know upfront how many jobs). And I have N workers in the system.

Now I want to schedule / queue a job to one worker (a worker can have multiple jobs in his queue).

However, it's not the case that the workers can equally well do all jobs (think delivery -- delivery people who are closer to the pickup can do the job better than those that are further away). So there are two costs. First the cost to assign job X to worker Y (which varies with each worker -- for example time from worker's location to pickup point) and second the cost of doing the job (for eg. time from pickup to customer location).

It's perfectly alright to re assign jobs from one worker to another as long as they have not started processing the job (so only the jobs that are queued up can be "shuffled" amongst the workers).

What's a good away to do assignment of jobs to workers so as to reduce the cost (or in our example, time for delivery) across all the jobs? It doesn't have to perfectly optimal.

One simple solution would be as soon as a job comes in to find the worker that can finish the job fastest (it could be worker who is working on another, but his initial cost could be very little -- for eg. somebody who is delivering an item to a customer and the pickup for the next item is very close by). This would obviously not be very optimal.

Then periodically, try and re assign the queued up orders by swapping jobs between pairs of workers that would result in faster delivery (or rather least waiting time) for all of the jobs. But how good is this?


texts: Path in digraph passing through given set of vertices

texts:
Suppose we have digraph G, set of its vertices W and two (possibly equal) vertices s and f. I'm looking for an algorithm which will solve the following problem: whether there is path from s to f passing through all vertices from W; if yes, return any of such paths. By "path" i mean path in the most general sense: repetitions of edges and vertices are allowed.

Unfortunately no information about graph is known: it needn't be connected in any sense, it might have oriented cycles, etc.

My idea was to modificate DFS somehow but i didn't manage to proceed. Any ideas and hints will be highly appreciated. Thanks in advance.


texts: Why are palindrome and not-palindrome both context-free?

texts: Both palindrome and its complement are context-free. This is very interesting. Both are non-deterministic context-free, which in general are not closed under complement. What is it about these two NCFLs that makes complement work?


texts: Graph Closeness - Different result with gephi and NodeXL

texts:
I'm writing a JavaScript library for calculating graph measurements such as degree centrality, eccentrality, closeness and betweenness.

In order to validate my library I use two exist applications Gephi and NodeXL to run calculation with them.
The problem is I got what looks like different results.

I build simple graph:

  (A) ----- (B)
   |         |
   |         |
  (C) ----- (D)

Gephi gave those results:

A ecc=2 close=1.333 bet=0.5
B ecc=2 close=1.333 bet=0.5
C ecc=2 close=1.333 bet=0.5
D ecc=2 close=1.333 bet=0.5

NodeXL gave those results:

A close=0.25 bet=0.5
B close=0.25 bet=0.5
C close=0.25 bet=0.5
D close=0.25 bet=0.5

Note that NodeXL does not calculate eccentrality.

Which one is right?
Are the results really different?

I didn't normalize (or at least not intend to normalize) any results.


texts:
This is a question from the Dragon Book. This is the grammar:

  $S \to  AaAb \mid BbBa $
  $A \to \varepsilon$
  $B \to \varepsilon$

The question asks how to show that it is LL(1) but not SLR(1).

To prove that it is LL(1), I tried constructing its parsing table, but I am getting multiple productions in a cell, which is contradiction.

Please tell how is this LL(1), and how to prove it?


texts: Machine Learning to predict the Halting Problem

texts:
I seem to recall an academic paper from some years ago which used machine learning (possibly genetic or evolutionary programming) to predict whether a Turing Machine would halt.

By predict, I mean the standard notion in ML: minimize the error on some validation set. For simplicity, let's assume that the ML is a binary classifier,  (although AFAIK the actual paper may have framed it as a regression problem).

The notion is then not 'solving' the Halting Problem (which we know is impossible), but rather using ML to agree with an Oracle that knows the answer on the training (and validation) set.

However, I haven't been able to find anything so far.

Does anyone know of a reference?


texts: What would be acceptable size of list for O(n!) algorithm

texts:
I was wondering what the limitations to an algorithm that runs in O(n!). For example lets take an algorithm that generates all permutations of a list. Now what i am wondering is what the upper bound would roughly be for size of list. I understand that this can vary based on ram/memory. Let's say that this would be ran client side and be expected to work on basically any machine a user would have at his/her home.

Thanks in advance for any insight.


texts: Fixed size set to contain the maximum number of given sets

texts:
I asked this question in SO here

I have about 1000 sets of size <=5 containing numbers 1 to 100.

{1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ...

Is it possible to find a set of size 20 that contains the maximum number of given sets?

In other words, let $U = \{1, 2, ..., 100\}$ and $S \subseteq \{Z \in 2^U \mid |Z| \leq 5\}$. How can I find $X \subseteq U$ with $|X| = 20$ such that $|\{Y \in S \mid Y \subseteq X\}|$ is maximized?

Checking each of 100!/(80!*20!) sets  or bulding all set combinations with size <=20 is inefficient.

Is there any (semi)efficient solution or is it np-complete?

The set {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20} contains 5 sets.


texts: What happens to quantum algorithms such as BB84 if P=NP

texts:
Under the hypothesis that P=NP, many cryptographic protocols are no longer secure (i.e. attacks are feasible).

The BB84 algorithm is based on the idea that by observing a quantum state, one has to (in quantum theory) disturb that state. This makes them efficient against eavesdropping.

Are quantum algorithms based on BB84 also subject to the hypothesis that P=NP? Or do they remain unaffected by the hypothesis?


texts:
I wondering how the browser's JS runtime implements these methods.  I looked on the web and could not find any documentation.

How does something like the V8 runtime actually work to implement these methods into machine code?
 At runtime what does the call stack look like?

Function

function multiply(a, b) {
    return a * b;
}
multiply(2, 3);

Function nested in an associative array at creation time

var MyMath = {
    multiply: function (a, b) {
        return a * b;
    }
};
MyMath.multiply(2, 3);

Function nested in an associative array, but added after initial construction

var MyMath = {};
MyMath.multiply = function (a, b) {
    return a * b;
};
MyMath.multiply(a, b);

Function added to an object prototype

var MyMath = function(a) {
    this.a = a;
};
MyMath.prototype.multiply = function(b) {
    return this.a * b;
};
var math = new MyMath(2);
math.multiply(3);

Function added statically to the Object

var MyMath = function(a) {
    this.a = a;
};
MyMath.multiply = function(a, b) {
    return a * b;
};
var math = new MyMath(2);
math.multiply(math.2, 3);

Function added dynamically in the Object constructor

var MyMath = function(a) {
    this.multiply = function(b) {
        return a * b;
    };
};
var math = new MyMath(2);
math.multiply(3);

Function dynamically added to an instance of the Object

var MyMath = function(a) {
    this.a = a;
};
var math = new MyMath(2);
math.multiply = function(a, b) {
    return a * b;
};
math.multiply(math.a, 3);

Function added via prototype but references regular function

function multiply(a, b) {
    return a * b;
};

var MyMath = function(a) {
    this.a = a;
};
MyMath.prototype.multiply = function(b) {
    return multiply(a, b);
};
var math = new MyMath(2);
math.multiply(3);


texts:
Suppose I have a compressed file and it is not possible to compress it more without loss of information. We say that this file is random or pseudorandom.

So, if the randomness means not comprehensible and not compressible, I don't understand why ths file is, at the same time, information that my computer and I can understand.

This file could be a book that my computer can show to me and read, and I can read and sum it ...so, it is really randomness?

Note: I understand that if I can make a summary of a text or define it with less words, that not means that it could be possible to get all the information of this book again, of course but this book is not random for me.

Note II: I undesrtand ramdoness as something that is not possible to reproduce with an smaller algorithm. I mean a string is random when I can't find an other smaller string that is an algorithm that can reproduce the first one.

Note III: I want to thank you all for your help.


texts: How to prove that if $L, G$ are regular languages then $\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?

texts:
Prove that if $L, G$ are regular languages over $\{a,b,c\}$ then $H=\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?

I think this could be a good exercise and the conditions are very simple.

Because $L,G$ are regular  they have corresponding DFA's:
$$
L=\bigg(\sum,Q_1, q_{01,\delta_1, F_1}\bigg)\\
G=\bigg(\sum,Q_2, q_{02,\delta_2, F_2}\bigg)
$$

Then we can build a pushdown automaton $M$ for $H$:

$$
M=\bigg(Q_1\times Q_2\times \{0,1,2\}\cup \{q_f\}, \sum,\{A, S\},\delta, (q_i,q_j,0),S,F_1\times F_2\times\{2\}\bigg),\quad q_i\in Q_1, q_j\in Q_2, q_f\in F_1\times F_2\times\{2\}, S \text{ is the starting symbol on the stack}
$$

$\delta$ can be defined as follows:
first we read $w\in L$ and add two stack symbols for each letter read. Also we put the special symbol $B$ which we will need later:
$$
\delta((q_i,q_j,0),\sigma, S)=((\delta_1(q_i, \sigma), q_j, 0), AABS)\\
\delta((q_i,q_j,0),\sigma, A)=((\delta_1(q_i, \sigma), q_j, 0), AAA)
$$
Then we guess the start of $x\in G$:
$$
((q_i,q_j,0),\epsilon, A)=(q_i, q_j, 1), A)
$$
Then we delete symbols off the stack one by one:
$$
\delta((q_i,q_j,1),\sigma, A)=(q_i,(\delta_2(q_j, \sigma), 1), \epsilon)
$$
If there're no more characters to read from $x\in G$ then we should see a $B$ on the stack, which means that $|x|=2\cdot |w|$ and we're in accepting state:
$$
((q_i,q_j,1),\epsilon, B)=(q_i, q_j, 2), \epsilon)
$$
Because a PDA exists for $H$ then $H$ is context-free.

Is my proof good, especially the $\delta$ function?


texts: Trouble Convincing Myself Algorithm Correctness

texts:
I'm having a tough time convincing myself right when coming up for some solutions to medium/hard leetcode.com problems. Take the following question for example.

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result.  If not possible, return the empty string.

Example 1:

Input: S = "aab"
Output: "aba"
Example 2:

Input: S = "aaab"
Output: ""
Note:

S will consist of lowercase letters and have length in range [1, 500].

On a question like this I usually work up to a solution and then try to look for counter examples. Looking for counter-examples often helps me identify where there might be holes in my approach, but it's still challenging to not fool myself.

For example I may initially have the idea to sort the string by characters, then create a new string by inserting different characters between similar characters through a process of interleaving.

e.g. `abacc`
1. Sort: `aaccb`
2. Interleave: `acacb`

Hmm.. OK seems like a decent algorithm. But then I might find a counter-example.

e.g. `ababcc`
1. Sort: `aaccbb`
2. Interleave: `acacbb`

OK, this is good as my algorithm can improve. It seems like I need to sort the strings I am interleaving by frequency possibly, but that doesn't quite work as already shown by this counter example. So maybe I can insert them by round-robin order, yes that seems to be much better.

e.g. `ababcc`
1. Sort: `aaccbb`
2. Interleave: `acabcb`

Now at this point I am fairly confident that my algorithm is correct after trying to come up with more counter-examples, unsuccessfully. However, I am still not sure that I am correct (e.g. what if sorting by some other random order produces a result that I did not cover with this approach? How can I convince myself this is not the case?)

I could perhaps say something like "ok, well since I am sorting and getting maximum variability by doing a round robin interleaving this should be correct" but there is still a part of me that is unsure that this is correct and that there isn't a counter example.

With simpler examples it's easier to convince myself correctly with a little mini-proof, or by covering the entire sample space, or by proving by contradiction or something similar, but as the questions get tougher I find myself hard-pressed to convince myself short of writing an entire proof out.

Do I just need to get better at proofing stuff like this with in a hand-wavy way like I would be able to with easier problems?

Extra Information:

I've already taken DS&A and all the formal algorithms courses at university.


texts: Subtree with minimum sum of nodes' costs

texts:
Let's consider a tree with root $r$ ( not necessary binary) and to each node $i$ we associate a cost $\sigma(i)$ that can be negative, positive or zero. We want to select the set of nodes that minimize $\sum_i \sigma(i)$. Of course, the problem until now is easy :

If there are only non-negative costs the solution is the empty set.
If there are some non-positive costs, we select them all.

But, there is an additional constraint that states: "if a node $\sigma(i)$ is selected, its predecessor to the root is also selected.  Thus we are looking for the set of nodes that grow upward to the root and that minimize that sum, or equivalently, we are looking at a subtree of root $r$ that minimize that sum.

My question is how to design an algorithm that solves this problem and how to prove its correctness and compute its complexity?

(I have a hint that states that we could do some bottom-up traversal, of the tree but I don't know how to use this information)

Any help will be appreciated.
Thanks


texts: In Agda's GADT, are "parameterized" and "indexed" different semantically?

texts:
I know they have different scoping:
data a (n : Set) : Set where
    introA : a n

data b : Set -> Set where
    introB : {n : Set} -> b n

That's not what I'm caring about. Are they different semantically?


texts: Bucket computation, cutting array with lines

texts:
Given an NxN array, drawing a line from the edge's midpoint to the opposite field how can the N buckets be found covering the majority of the line's path?

A visual aid:

Is there a better way to this than computing the linear equation and iteratively advancing in tiny steps to check which bucket we fall on? If not what is the lower limit step size to choose?


texts: Line smoothing algorithm that perserve data uniformity

texts:
Intro:

I'm working with huge data set that i need to plot in browser, and since there may be up to 1M points my idea was to create different representations for different zoom levels

lets say i have 100k points, i would average two-by-two until i get 50k, then i would repeat that until i get below 500 points (my arbitrary threshold)

so on the most zoomed-out level i would draw all 500 points, or part of it, depending of the chart size, and as i zoom in, i would switch to next zoom level (and stream data if user drags selection l/r), and ultimately if user wants to see fine grain details he can zoom to 0 zoom level and see all the fine details.

I actually created this prototype, and its working quite well, except for one thing: side-effect of this is, as you can imagine, that peaks are lost in those iterations of averaging.

I did some research and find about Douglas-Peucker algorithm, and how it can perserve peaks, i did some tests, and it works quite well, but the problem with that is that if it encounters a series of data (y values) [1,1,1,1,5,6,1,1,1,1,1,1] it will smooth that to something like [1,6,1,1] which doesn't work for me since i need to keep ratio of zoom levels like this

n (length of original data) > n/2 > n/4 > n/8 > .....

I read quite few papers on line smoothing, but all algorithms that i found are accepting distance threshold, that they use for smoothing as a parameter, and none of those can accept number of desired output elements, and also, since their goal is to smooth the line, they will transform sequence like this (y values) [1,1,1,1,1,1,1,1,1,1,1] into [1,1]

So, finally, my question:

Is there an algoritm that:

instead of usual distance threshold accepts the desired number of output elements
tries to perserve peaks (as Douglas-Peucker does)
will smooth data uniformly, so even if it gets (y values) [1,1,1,1,1,1] and i say i want 3 outputs, event if it IS in theory correct to smooth as [1,1] i would need to get [1,1,1] instead

Also, please don't be confused by lack of X axis information because it is irrelevant since all data are measured from 1 to n in steps of 1, so there are no N/A values, or blank spots, or values like [1.3,1.4,3]

x is always [1,2,3....n]


texts: Throughput of slotted ALOHA when one node goes out of sync

texts:
What would be the throughput of slotted ALOHA when one node goes out of sync? Closer to ALOHA or slotted ALOHA?
According to my calculations:
For ALOHA we have probability of success = $N \cdot p \cdot (1 - p)^{N - 1}$
For slotted ALOHA we have probability of success = $N \cdot p \cdot (1 - p)^{2(N - 1)}$
For one node going out of sync probability of success = $N \cdot p \cdot (1 - p)^{N}$
According to my intuition it should be almost equal to slotted ALOHA as for large N, $lim (N - 1) \rightarrow N$ and these two probabilities should become equal.
I have had a look at this derivation but didn't completely understand the formal proof for the efficiency of slotted ALOHA.


texts: Polynomial-time Compute the Number of States resulting from the NFA to DFA (greedy) conversion?

texts:
The canonical NFA to DFA conversion, starting with an NFA with $n$ states, can result in a DFA with $2^n$ states. However, in many cases, there are states that are "unnecessary," such as when minimizing the resulting DFA. The most common case is when states are "unreachable" from the corresponding start state.

I am interested in the following question: if we have an NFA with $n$ states and $q$ symbols, is there a $\mathrm{poly}(n, q)$-time algorithm to output the number of states that the standard conversion (and minimizing, if possible) to a DFA would produce? Note that producing the DFA itself can take exponential time.


texts: Cross platform apps and programing languages...how is it done?

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

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

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


texts: What is the complexity of recurrence $T(n) = T(n-1) + 1/n$

texts:
What is the complexity of the follwoing recurrence? $$T(n) = T(n-1) + 1/n$$

I highly suspect the answer to be $O(1)$, because your work reduces by $1$ each time, so by the $n$th time it would be $T(n-n) = T(0)$ and your initial task reduces to 0.


texts: Difference between time complexity and computational complexity

texts:
For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them?

I used to calculate the maximum (worst) count of basic (most costing) operation in the algorithm.


texts: Proving that shortest path distance of adjacent nodes can't differ by more than one

texts:
Could someone explain this proof to the following question?

Lemma 22.1 from intro to algorithms
Let $G=(V,E)$ be a directed or undirected graph, and let $s\in V$ be any vertex. Then, for any edge $(u,v)\in E$,
$$\mathrm{dist}(s,v)\leq \mathrm{dist}(s,u)+1\,.$$
Proof.
If $u$ is reachable from $s$, then so is $v$. In this case, the shortest path from $s$ to $v$ cannot be longer than the shortest path from $s$ to $u$ followed by the edge $(u,v)$ and thus the inequality holds.

I drew this to visualize the problem but I don't see how what I drew is wrong and how the proof is correct.

If going from $s$ to $u$ has less vertices along that path than going from $s$ to $v$, than the shortest distance of $s$ to $v$ should be greater than going from $s$ to $u$ and $s$ to $u$ to $v$.


texts: What is an example of complex random string, in the Kolmogorov-Chatin sense?

texts:
Any string generated from a PRNG clearly has a very short description.  You need the code for the random number generator, the seed, and then the number of times to iterate.  So, it seems that all such strings have low KC complexity.

If the above it true, then what is an example of a "complex" string, in the Kolmogorov-Chatin sense?


texts: How to get the best factor for abstract algorithm that has expected cost?!

texts:
1.10 Let A be an algorithm for minimization NP-optimization problem such that the expected cost of the solution produced by A is at most $\alpha OPT$, for a constant $\alpha>1$. What is the best approximation guarantee you can establish for this problem using algorithm A?

Hint: A guarantee of $2\alpha-1$ follows easily.
to be honest, I don't really understand the question good. So usually when we want an approximation factor we take the ratio between solution of algorithm A and OPT of problem. could you explain the problem in other way! and how we get factor of $2\alpha-1$. Suppose I want to use Markov's bound, since the information we know is expected value. Thus, I would get $\alpha OPT/a$ for $a>0$. I don't see any logic here! I would like any help in terms of explanation!

Thank you!


texts: If we are given only one NOT gate and any number of OR and AND gates, then, can we simulate more NOT gates?


texts: Color coding to get an FPT algoirthm for k disjoint triangles

texts:
The k-disjoint triangles problem is as follows:

Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$
Output: Are there $k$ vertex-disjoint triangles in $G$?

An FPT algorithm is presented here
(starting from slide 60). The algorithm uses color-coding and relies on dynamic programming to determine if a solution is highlighted (each vertex in the solution group is colored with a distinct color). The running time of the algorithm is $O^∗((2e)^{3k})$.
I`m trying to understand the running time of this algorithm using dynamic programming (method 2). why is it   $O^∗((2e)^{3k})$?


texts: Hardness of approximation of the 3 colorability problem

texts:
If we have polynomial algorithm that $c$-approximation, $c<\frac{4}{3}$ for graphs that their chromatic number $\geq k$ then $NP=P$, how to prove such statements?

I also have some sort of explanation of this statement: It's NP-hard to separate between graphs that have chromatic number $k$ and chromatic number $c \cdot k$ when $c<\frac{4}{3} \quad \forall k\geq 3$


texts: Floyd–Warshall algorithm on an undirected graph contains negative weight edges

texts: According to this answer, the Bellman-Ford algorithm doesn't work when an undirected graph contains negative weight edges since any edge with negative weight forms a negative cycle, and the distances to all vertices in a negative cycle, as well as the distances to the vertices reachable from this cycle,  are not defined. So in the all-pairs shortest path problem, can we say the Floyd–Warshall algorithm also doesn't work on an undirected graph contains negative weight edges for the same reason?


texts: Effects of parity bit on odd code length regarding its size after alternation

texts:
I am trying to understand code distance, but I am not sure regarding the following scenario:

Assume that you have an information word M with m bits, that You code into a coding word using the following procedure:

You take M and code it using a code you know nothing about. But you do know that its distance(code's distance) is k, and that k>2.
You add to the word obtained in the last step a parity bit.

If you know that k is odd, does it necessarily mean that the distance of the code constructed by those two steps is necessarily k+1?

Well, I am not sure here. Code distance is basically the number of different bits, and the meaning of the second step in the procedure(adding a parity bit) is, according to my understanding, allowing the detection of any odd number of errors. Does it necessarily mean that the code constructed by those two steps is necessarily k+1?