texts: Can a program language be malleable enough to allow programs to extend language semantics

texts:
With reference to features in languages like ruby (and javascript), which allow a programmer to extend/override classes any time after defining it (including classes like String), is it theoretically feasible to design a language which can allow programs to later on extend its semantics.

ex: Ruby does not allow multiple inheritance, yet can I extend/override the default language behaviour to allow an implementation of multiple inheritance.

Are there any other languages which allow this? Is this actually a subject of concern for language designers? Looking at the choice of using ruby for building rails framework for web application development, such languages may be very powerful to allow designing frameworks(or DSLs) for wide variety of applications.


texts:
We know that counting the number of Hamiltonian paths is in $\#\mathsf{P}$.

So, what complexity (counting version) class would the counting the number of Hamiltonian paths that have two or three particular vertexes in a graph be in?

Also, what would be like if counting the number of hampaths that have two or three particular vertexes in particular place - so, for example, calculating the hampath that has vertex 3 as the second place from starting point and so on?


texts: Is there a generic algorithm to optimally combine elements by some arbitrary scoring method?

texts:
I'm looking for a generic algorithm to optimally combine elements of a list. I'm not sure if it even exists, but I believe some kind of divide-and-conquer algorithm could exist. In my specidifc case, optimally combining the score means minimizing, but that's probably not important

Formally stated:

We have the function SCORE(L) that computes score for a list.
Each adjacent pair of list elements L[i],L[i+1] can be replaced by element produced by the function COMBINE(L[i],L[i+1]). This operation can be repeated recursively, further shortening the list.
COMBINE is associative and commutative, i.e. COMBINE(A, COMBINE(B, C)) == COMBINE(COMBINE(A, B), C) and COMBINE(A, B) == COMBINE(B, A)
Given list L and functions SCORE/COMBINE, we need to find best score that can be reached on L or any its reduction.

So, as an example, if I have the list [A, B, C, D], all of these options are to be considered: (AB denotes the combination of A and B):

[A, B, C, D], [A, B, CD], [A, BCD], [A, BC, D], [AB, C, D], [AB, CD], [ABC, D], [ABCD]

Two obvious options include brute force (thanks, no) and a greedy algorithm, which would go roughly as follows in pseudocode Python:

def greedily_combine( elements, combine, score ):
    i = 0
    combine_success = False
    while i < len( elements ) - 1:
        combine_candidate = [combine( elements[i], elements[i+1] )]
        sublist_to_consider = elements[0:i+1]
        combined_score = score( combine_candidate )
        uncombined_score = score ( sublist_to_consider )

        if ( combined_score < uncombined_score ):
            elements.pop(0)
            elements.pop(0)
            elements.insert(0, combine_candidate)
            combine_success = True
        else:
            i += 1
            if i == len( elements ) - 1:
                i = 0
                combine_success = False

    return elements

However, this is almost certainly not going to be optimal. Is there a known general solution? If not, how could I have seen this myself, and is my greedy search good or easily improvable?


texts: How can an artificial neural net change the sign of a weight?

texts:
My neural net is having trouble switching the sign of a weight. The issue is that the deltas applied to the weight are proportional to that weight, so when it gets closer to zero, the deltas become smaller and are never sufficient to get it past that point. I tried adding a momentum term with 5% of the previous iteration contributing to the current iteration without success.

In my example I have a very simple neural net with one input and one output and no hidden layer. The transfer function in the neural net is a sigmoid, and the function I am trying to learn is also a sigmoid. Specifically: $y = S(10 x - 5)$ where S is the sigmoid function. The neural net gets to a point where its internal weights are essentially generating a function very close to $y = S(2x + 0)$. At this point it gets stuck because the fitted function is sometimes above and sometimes below the desired function, but the weight on $x$ needs to go up and the weight on the constant term needs to go down. I ran it for 1,000 epochs and 100,000 epochs and it stays in the same place. The initial weights were 0.6 and 0.2, so it made improvements over that.

How can a net get over this hump? Should I not be scaling the weight delta by the weight value?

Here's the reference I'm using for computing the weights for back-propagation.  I am using a learning rate of 0.05 and apply the deltas after each training example.  The x-values (input) used in training are 0.00, 0.01, 0.02, ... 0.99, 1.00.  I always play them in order.

Thanks for your help.

Note: I originally posted this on stack overflow and was directed here.


texts:
Let's say I have the following string:

XXXXXAYYYYBYYYYCXXXXXDYYYY

We can see that the substring XXXXX is 5 characters long, and repeated 2 times. So it covers 10 characters. This is the longest repeated substring

However, there's the substring YYYY which is 4 characters long, and repeated 3 times and therefore covers 12 characters.

I want to find the repeated substring of length of at least 2 with the highest coverage, and that don't overlap.

Is there an efficient algorithm that does so?

This is the current algorithm I'm using (written in Java), which is naive and slow :

String highestCoveringRepeatedSubstring(String string) {
  int highestCoverage = 0;
  String highestCoveringRepeatedSubstring = "";
  for (int length = 1; length < string.length(); length++) {
    for (int index = 0; index < string.length() - length; index++) {
      String substring = string.substring(index, index + length);
      int count = 0;
      for (int i = index; i >= 0; i = string.indexOf(substring, i + length)) {
        count++;
      }
      if (count > 1 && length * count >= highestCoverage) {
        highestCoverage = length * count;
        highestCoveringRepeatedSubstring = substring;
      }
    }
  }
  return highestCoveringRepeatedSubstring;
}


texts: GATE CSE 2018, Which of the following languages are context-free?

texts:
A] {ambncpdq | m+p = n+q,
where m, n, p, q >=0}
B] {ambncpdq | m = n and p
= q, where m, n, p, q >=0}
C] {ambncpdq | m = n = p
and p not= q, where m, n, p, q >=0}
D] {ambncpdq | mn = p+q,
where m, n, p, q >=0}

Instead of Formal proofs if any answer can provide telltale signs of a language being CFL or not will be more appreciated, because this question is taken from a competitive exam. Formal proofs are welcome too.
Here is my approach
A] I don't have any idea for constructing PDA for this language, probably not a CFL. Also by pumping lemma splitting the word in 'uvwxy' for any 'vwx' (belonging to 'akbk' and such combinations), the equality won't hold. Thus not a CFL.
B] Is a CFL we can push a's and pop on b's, same for c's and d's.
C] Not a CFL, as we need two stacks, one for keeping count of |a|==|b| and second for |b|==|c|.
D] Not a CFL, cause we can't construct a PDA, such a PDA will require capability to move back and forth on input string (for keeping track of m*n), which is not possible.


texts: Easy to state open problems in computability theory

texts:
I was searching for interesting and easy to state open problems in computability (understandable by undergraduate students taking their first course in computability) to give examples of open problems (and obviously I want the students to be able to understand the problem without needing too much new definitions and also be interesting to them).

I found this list but the problems in it seem too complicated for undergraduates and will need spending considerable time giving definitions before stating the problem. The only problem I have found so far is

  Is Diophantine problem over rational numbers decidable?

Do you know any other interesting and easy to state open problem in computability theory?


texts: Sums of all pairs: possible less than quadratic?

texts:
Is there an algorithm to prepare all sums of pairs of a list ($L$, size $n$, max value $m$) in $< O(n^2)$ such that query "does this sum of pairs exist" takes $< O(n)$?  In other words, can max value $m$ be used to advantage?

E.g. in $L =\{1, 2, 4, 8\}$ and $m = 8$, all (distinct) sums of pairs are $S = \{2, 3, 4, 5, 6, 8, 9, 10, 12, 16\}$ (not given, calculate).

This may be possible using a divide-and-conquer on both $L$ and on the bits of each item.  (N.B. the constraint keeps $S.size$ to $2m$, no need for size $O(n^2)$)


texts: What happens when many interrupt requests happen at the same time?

texts: My initial guess is that you would have to queue the lower priority one, but what happens when for example 5 or many more requests happen at the same time? Are all these requests put in a queue or are they lost forever?


texts: Is there a way a proving a language regular/non-regular that works for every possible language?

texts: In my theory of computing class, we've been talking about how to prove languages regular and non-regular. I've heard of methods like the pumping lemma and Kolmogorov complexity to prove languages non-regular, while proving languages regular revolves around building a DFA, or using the Myhill-Nerode theorem. All of these approaches fail for some language. Is there some approach that will work for all regular/non-regular languages?


texts: Construct a TM for $L = \{ M | M$ is a Turing machine with no useless states}

texts:
I'm trying to construct a recursively enumerable TM for this language. (Useless state: one that is never entered during a computation on any input).

The TM L:
Write out all of M's states, generate input in lexicographical order one at a time, and after one is generated, simulate M on the input and mark down which states M has entered. If M enters all states, halt, if M halts without entering all states, generate the next input in lexicographical order and repeat the process. (Keeping the list of entered states between simulations, since once a state is entered for any input, it is not considered useless).

My question is, what happens if M does not halt on input $w_i$ but will halt and in fact enter all states on $w_{i+1}$?
Then L will get stuck in an infinite loop on $w_i$ and not realize that M's behavior on $w_{i+1}$ means L should actually accept--thus L will not eventually halt and accept.

Is there a way to deal with this problem or is this TM just not the right way to show this language is recursively enumerable?


texts: Reference request: Algorithms on Turing Machines

texts: Is there a good survey or some papers with algorithms in the Turing machine model? I know the paper STRING-MATCHING AND OTHER PRODUCTS contains Turing Machine version of KMP. Are there any other such papers?


texts:
Adleman's theorem gives $$\mathsf{BPP\subseteq P/Poly}.$$
Why is this theorem considered progenitor to derandomization conjecture that $\mathsf{P=BPP}$?

Does it mean Adleman's result could be considered as evidence $$\mathsf{BPP\subseteq P/Log}$$ is a realistic possibility?
Anaalogously, does it mean $$\mathsf{NP\subseteq P/Poly}$$ could be considered as evidence $$\mathsf{NP\subseteq P/Log}$$ is a realistic possibility?

Is there a satifactory answer without considering Impagliazzo-Wigderson's conditional $\mathsf{P=BPP}$ result?


texts: Automatically generate meaningful queries for a data table

texts:
My field of research is not Database or AI. But I have some problems to solve, and would like to know which branch this kind of problems belong to, and what are the results.

The main question is: given a table of data, there are lots of possible queries that can be made. But some queries are meaningful, some are meaningless. Are there some algorithms to automatically generate a ranked set of meaningful queries, from the relationships inside the table?

Here is an example:

ArticleID   Price   Quantity    Sale
A01         10      3           30
A01         10      3           30
A02         20      4           80
A02         20      5           100
A03         15      3           45
A03         15      4           60
A03         15      5           75
A04         20      2           40
A04         20      3           60
A04         20      4           80

There are two relationships in this table, which may be given or inferred (the detection of the relationships is not an issue here): a) one ArticleID maps one Price; b) Sale = Price * Quantity.

Then, the first issue is, how to automatically generate some queries? For instance:

1) Sum of Quantity by ArticleID
2) Sum of Sale by ArticleID
3) Sum of Price by ArticleID

The second issue is, how to rank the meaningful queries? For example,
intuitively, we can say that Query 1 and Query 2 make more sense than Query 3. And this conclusion can be more or less inferred from the two given relationships.

Certainly, the problem becomes more complexe when there are relationships among several tables. The tables and the relationships that I study are not very complicated.

Could anyone tell me which field this problem belongs to? Are there some good results/proposals that are easy to understand?


texts: Is undecidability of TMs' properties a statistical statement?

texts:
We know (by Rice's theorem) that is it not possible to decide a non-trivial property of a given TM. We could say therefore that we cannot be sure at 100 percent that a given TM has a certain non-trivial property.

Therefore we cannot know if it is 100 percent impossible to show that a given TM has a certain non-trivial property. Right?

So my question is this: as (maybe) we could guess a non-trivial property of a Turing machine, is Rice's theorem just a statistical statement on the probability of finding out a given non-trivial property?

BONUS question: is that probability related to Chaitin's constant?


texts: Is there a fast algorithm for computing the rolling mode of an array of integers?

texts:
I was wondering if there exists an efficient algorithm for calculating the "rolling mode of an array of integers.

By rolling mode I mean that we have an array of integers of size $n$ and a sliding window of size $k$ and we we want to compute the mode for each window in the array.
 There is an algorithm to do this in $O(n*k)$, by using a hash table in which we store the frequency of each integer. We can update this structure in $O(1)$ time, but to find the integer with max frequency we need $O(k)$ which gives the total running time.
 I was wondering if there exists a faster algorithm(Perhaps a data structure that can index the values both by frequency and value).


texts: Detecting coplanarity by given erroneous pairwise distances

texts:
This is the question I asked four months ago and took very satisfactory answers. However, I tackle a new problem now.

Here, I summarize the original problem:

We have points in 3D space.
We do not know the coordinates of the points.
We know some of the pairwise Euclidean distances.
Those points are deployed on random planes.
We neither know the number nor the equations of the planes.

Problem is to find an algorithm that extracts the coplanar point groups.

So far, this and this answers helped me to approach the original problem.

Now, I struggle with a slightly changed version of the problem.

Suppose that, distance measurements are not precise. We have a variable, called error rate, which tells us the possible deviation of a distance measurement.

For example: The Euclidean distance between any arbitrary point pair is $d = 10$ and the error rate is $e = 1\%$.
When we give the graph as input, that particulat distance $d$ may range from $9.9$ to $10.1$.
If $e$ is $5%$, then $d \in [9.5, 10.5]$ etc.

Now, we have another challenge, which is, even though 4 points are on the same plane, Cayley-Menger determinant may result a negative number, because of the violation of the triangle inequality.

Can we extract the planes even though the distances are erroneous?
Please notice that, the coordinates of the points are not known. However, if it makes any difference, you may assume that the coordinates of a number of arbitrary points are known.


texts: Count submatrices with only zeros for each element of the matrix

texts:
Let's say we have given matrix of size $N \cdot M$, only with zeros and ones. For each element in the matrix, we want to count subrectangles that are covering this element and are made only of zeros. We actually want only the sum of those value, not separately for each of them.

For example:

010 -> 201
001 -> 320
The sum is: 3 + 2 + 2 + 1 = 8

I have a solution with complexity of $O(N^3)$ which counts all possible rectangles with fixing the lower right corner, but I know that this can be improved somehow to $O(N^2)$


texts: Proving that Rice's theorem does not apply to a property

texts:
This is related to an assignment, but I would still appreciate help in formalising proof either through private message or on this topic.

The question is about if Rice theorem applies to certain property. For example for a structural property such as number of states. I would argue that:

The property is decidable through its definition in encoded form.
The property is irrelevant to the language, because given the same language we can easily find another TM that does not have this property, ie one with empty states, so the property is not a language property, and hence Rice Theorem does not apply, since by definition, Rice theory only applies if it is a non trivial language property.

To me, this seems to be a good argument, but the question is assign a substantial mark of 10, and I feel like this is not enough for 10 marks, am I missing out some rigorous argument that I need to include to make my explanation crystal clear?


texts: Proving NP hardness about graph creation

texts:
I have graph creation problem.

Given a set of nodes of graph, and node constraints such as given every node's number of neighbors and number of neighbors of neighbors and so on. I want to create a graph that can satisfy all these constraints (# of constraints is polynomial in n).

I have formulated the problem as an integer programming wherein I am trying to create possible edges by assigning them random variables $z_{i,j} \in $ $\{0, 1\}$ and then trying to satisfy the constraints of # neighbors, # neighbors of neighbors and so on (k steps). However I am not sure if this is a NP complete problem because the constraints are non-linear.


texts: How does one show $(\lambda x . (\lambda y.x))yx \equiv_{\beta} y$ in lambda calculus?

texts:
I wanted to show:

$$ (\lambda x . (\lambda y.x))yx \equiv_{\beta} y $$

the definition of beta equivalence is on page 17 of these notes.

I did a few attempts but got different things like $x$. I think my main confusion is how to interpret:

$$ yx $$

at the end. Does that mean we are applying $x$ to $y$ or that we are applying $yx$ to the lambda function $(\lambda x . (\lambda y.x))$? I tried both interpretations and didn't get anything that made sense.

I think I understand what $\beta$ conversion means (cuz I could follow the example he gave) but then when I tried doing it myself on this weird example I got non-sense.


texts: Correct term for a priority queue with unique elements

texts:
Is there a standard term for a priority queue which can only hold a single occurrence of any element?  This would be a priority queue for which operations such as "raise the priority of element x to the new value p" would make sense.

In this kind of an abstract container, if you insert some element ("key", but not in the sense of "priority key") with some priority, you cannot insert it again until it is extracted, but you can update its priority.

I would also like to know if there is some established interface for this kind of a priority queues.


texts:
For a given undirected graph G, I want to count all the subgraphs H that satisfies the following conditions:

H.V = G.V (The subgraph will containt all the original graph nodes)
H is connected

(Note: I don't care if two subgraphs are isomorphic)

The graphs which I will be working with will have |G.V| <= 15


texts: Channeling Constraints in Constraint Handling Rules (CHR)

texts:
Suppose we have a constraint satisfaction problem that can be defined as its constraints in two different viewpoints $V_1$ and $V_2$. Moreover, there are two variables $A$ and $B$ from $V_1$ and $V_2$ respectively, such that the value $I$ for the variable $A$ in $V_1$ is equivalent to value $J$ for the variable $B$ in $V_2$. Now the question is how we can define the channeling constraint in CHR if we choose $V_1$ to solve the problem? Is it enough to write $P_1(A,I) ==> P_2(B,J)$? (suppose $P1$ and $P2$ are two predicates related to their viewpoints).

However, this propagation in the context of CHR does not help to solve the problem more efficient as we have no constraints over the variables of $V_2$.

Notice that this question in the matter of programming asked here but not solved yet.


texts: Is there any rich problems that can be solved using several algorithm techniques?

texts: I am wondering if there are some particularly rich problems that have a large intersection with algorithms and data structures. An example could be the travelling salesman problem. Any other suggestions ?


texts: Equivalance of NFAs, understanding the solution

texts:
This solution comes from https://people.eecs.berkeley.edu/~luca/cs172-07/solutions/practicefinal-sol.pdf

  Consider the language

  $$ EQ_{NFA} = \{ \langle N, N^\prime \rangle \mid N, N^\prime \text{ are NFA's with the same alphabet and } L(N) = L(N^\prime) \} $$ show
  that $EQ_{NFA} \in \textbf{PSPACE}$.

  (hint: Can you convert this to a appropriate reachability problem?)

  Solution Outline: Suppose $N$ and $N^\prime$ both have at most $n$ states. We can then convert them into DFAs $D_N$ and
  $D_{N^\prime}$ with at most $m = 2n$ states each using space
  polynomial in $n$. Finally, we can construct a DFA $S$, which is the
  product of $D_N$ and $D_{N^\prime}$ (with at most $m = 2^n$ states)
  and accepts $L(D_N)\Delta L(D_{N^\prime})$ (strings that are in
  exactly one of the languages). Now, $L(N) = L(N^\prime)$ iff $L(S) = \emptyset$ i.e. none of the final states are reachable from the start
  state in $S$.

  Since this is a reachability problem, it can be decided
  nondeterministically using space logarithmic in the size of the graph
  (because $PATH \in NL$). Thus, this problem can be decided in
  $NSPACE(\log{(m^2)}) = NSPACE(n) \subseteq NSPACE(n^2) \subseteq PSPACE)$.

I see that it works and I see that the last paragraph try to convince that it is actually $PSPACE$.  But, I have a doubt:

After all, the solution constructs two exponential automats. How is it possible?

My intuition is that:
We can compute DFA for NFA using $\log n$ memory on working tape. Obviously, we have to use exponential size of memory but on the output (readonly) tape.

Now, when we construct it we can use it in reachability problem which works in $NL$. We know that composition of $LOG$ function is $LOG$. Is my understanding correct? Does the same apply (I mean a composition of functions) when it comes to $NLOG$?


texts: How to find the relation between two models, and sort of inductive bias is that is implemented in those models

texts:
I am pretty new with data science and Machine Learning. I am learning form one textbook and I found this task. I have no Idea from where to start and what relation could be. Any help would be great.

Suppose we want to learn the Boolean functions in instance space
$X=\{0,1\}^3$. We are given two models to examine: $H_1$ is the set of all
logical functions in conjunctive normal form (CNF), $H_2$ is the set of
logical functions which can be displayed in Horn form (disjunction
of literals with at most one positive). I need to explain what is the
relation between $H_1$ and $H_2$, and which sort of inductive bias is
implemented in those models.


texts: Optimal covering of 2D matrix elements given spatial constraints

texts:
I have a particular problem I need to solve, but I'm not sure how to classify the problem or pick the right algorithm to solve it. I'm hoping someone here can lead me in the right direction.

I've generalized and reduced the problem to this:

Given an $M \times N$ matrix with elements in $\{0, 1\}$, cover all the $1$ elements according to the following rules:

"Marking" an element covers that element as well as the elements directly above and below
A maximum of $\frac{N}{2}$ elements can be marked in any row of the matrix

while minimizing the number of $1$ elements that are covered by an adjacent element but not marked itself.

For example,

Let $M = N = 4$ and consider the following matrix:

$$
\begin{bmatrix}
1 & 0 & 1 & 1\\
0 & 1 & 1 & 0\\
1 & 1 & 1 & 1\\
0 & 0 & 0 & 1
\end{bmatrix}
$$

Because $N = 4$, only 2 or less elements may be marked per row.

An optimal solution is as follows, where marked elements are shown in red, and elements that are covered but not marked are shown in blue.

$$
\begin{bmatrix}
\color{red}{1} & 0 & \color{blue}{1} & \color{red}{1}\\
0 & \color{red}{1} & \color{red}{1} & 0\\
\color{red}{1} & \color{red}{1} & \color{blue}{1} & \color{blue}{1}\\
0 & 0 & 0 & \color{red}{1}
\end{bmatrix}
$$

In this solution, there are three $1$ elements that are covered but not marked (in blue).

For this problem, I need an actual assignment of the marks for each row, not just the final minimum cost.

The spatial relationship between neighboring elements initially led me to think about the problem in terms of a graph, so I tried setting it up as a minimum-cost maximum-flow problem, but I couldn't figure out how to model the flow graph.

Then I started looking into set-covering and ILP, but I'm not sure how to specify the rule about the relationship between vertical neighbors as a constraint.


texts: Lowest common ancestor similar algorithm for a graph

texts:
I'm working on a type system and hit upon a problem that seems similar to lowest common ancestor. Given two types, I need to find the smallest sequence of conversions which will result in the same target type. If I had a simple type tree I know how to get the result, but unfortunately I have a slightly more complex graph structure.

That graph has a few key points. It is unidirectional and no loops are ever formed. Due to an unlimited number of types however it cannot be produced statically. The distance of a path is generally quite low. It "feels" more like a tree with a bunch of shortcut edges.

Initially I looked at lowest common ancestor, but it is mainly described as a tree algorithm. I've not yet given up hope that I could adapt it. The other possibility would be a more generic path-finding algorithm.

I'm hoping somebody has seen this problem before, or a similar one, and can give me some references on how to further approach it. It seems familiar enough that I assume something must exist and I'm just searching for the wrong terms/names.

Here's my attempt to describe this more formally.

Let there be a graph $G = \{ V \}$ such that each vertex has a set of outgoing edges $V = \{ E=V_x \}$. Note, as the graph is dynamic, possibly infinite, there is no way to construct the form $G = \{V, E=(V_x,V_y)\}$ for the entire graph.

A path is formed from a vertex by following any of the available edges from that node. $Pnm_x = V_n, ..., V_m$. The length of this path is equal to the number of vertices in the sequence. There is no cycle possible. The set of all paths between two nodes is expressed as $Pnm = \{ V_n, ..., V_m \}$.

Note that $Pnm$ can be determined to be empty in a finite number of steps. Enumerating the entire $Pnm$ set is not practically possible.

The problem is finding the shortest path from two vertices to a third vertex. That is, given $V_a, V_b$, find $V_c$ such that paths $Pac_x$ and $Pbc_y$ exist and $length(Pac_x) + length(Pbc_y)$ is minimal.


texts:
Why operator overloading was included in Python and not in Java?
How does one decide to include or exclude operator overloading in a programming language?

It is said here that operator overloading is excluded from Java
to make the language simpler
(for programmers, language and VM developers, etc.).

I don't understand why the same explanation doesn't work for excluding it in Python?


texts: Same notation/terminology for union of sets and concatenation (Kleene star)?

texts:
For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology and operator?

The following is my understanding of the union of sets versus the concatenation of sets (Kleene star). Please correct me if I'm wrong.

Union of sets

For the two sets $\{a,b\}$ and $\{a,b\}$ we have the union
\begin{align}
\{a,b\}\cup\{a,b\}=\{a,b\} \tag 1
\end{align}
Update: For reference I used Union (set theory) from Wikipedia.

Concatenation of sets (Kleene star)

The concatenation of $\{a,b\}$ and $\{a,b\}$ is also a union (same notation?!) of two sets
\begin{align}
\{a,b\}^*&=\bigcup _{i=0}^{2} \{a,b\} ^2 \tag 2\\
&=\{a,b\} \cup \{a,b\} \tag 3\\
&=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,\dots\} \tag 4
\end{align}

Update: For reference  I used Kleene star from Wikipedia. And here's where my confusion lies because at Wikipedia they also use the notation with the union operator:
$$
V^* = \bigcup_{i\geq 0} V^i = V^0\cup V^1 \cup V^2 \cup V^3 \cup V^4 \cup \cdots \tag 4
$$
Which is the same (?!) notation as in my $(2) - (3)$ but with the upper bound $2$. And the notation does not coincide with $(1)$.


texts: What is an algorithm for minimizing the standard deviation of m sums summed from n summands? [with attempt]

texts:
I have m bins (sums) and n summands. Each summand goes into a bin. In order to minimize the standard deviation, I have a greedy algorithm that appears to accomplish this. I am not sure of the name, but would like to know more. All m bins must have a sum greater than zero at the end of the algorithm.
It seems simple:
sort the summands from highest to lowest.
for each summand in the summands:
find the first available bin with minimum sum and place it in the bin
I haven't proved anything about it, but I've come up with a few test data sets and it appears to work.
EDIT --- Here is my attempt at an analysis:
The algorithm seeks to minimize the standard deviation of m sums summed from n summands.
The mean is always the sum of n summands divided by m, that is given.
To minimize the standard deviation, the algorithm makes the greedy choice to minimize the standard deviation, or variance (either). I want to prove that the greedy choice is always the optimal choice.
Suppose there is a bin m1, not the minimum sum bin, that is a better choice than minimum sum bin m. Adding to this bin will minimize the standard deviation around u.
In other words, placing the next value n into this m will maximally decrease the variance, meaning that we have maximally decreased the sum of (m_i - u)^2. NOTE: m1' = m1 + x, m' = m + x, where x is the next summand.
So:
remaining_sum_var + (m1' - u)^2 + (m - u)^2 < remaining_sum_var + (m' - u)^2 + (m1 - u^2) where m1 is greater than m.
Simplify and factor:
(m1' - u)^2 + (m - u)^2 < (m' - u)^2 + (m1 - u^2)
m1'^2 - 2um1' + 2u^2 + m^2 - 2um < m'^2 - 2um' + 2u^2 + m1^2 - 2um1
m1'^2 - 2um1' + m^2 - 2um < m'^2 - 2um' + m1^2 - 2um1
Ignoring linear terms whose difference will be constant (linearity).
m1'^2 + m^2 < m'^2 + m1^2
If we have added summand x to m1 this expands to:
(m1 + x)^2 + m^2 < (m + x)^2 + m1^2
m1^2 + 2m1x + x^2 + m^2 < m^2 + 2mx + x^2 + m1^2
2m1x < 2mx
m1 < m, this is a contradiction. So it cannot be the case that there is a better choice than minimum sum bin m.


texts: What were the shortcomings of Robinson's resolution procedure?

texts:
Paulson et alii. From LCF to Isabelle/HOL say:

Resolution for first-order logic, complete in principle but frequently disappointing in practice.

I think complete means they can proof any true formula in first-order logic correct. In the Handbook of Automated Reasoning I find:

Resolution is a refutationally complete theorem proving method: a contradiction (i.e., the empty clause) can be deduced from any unsatisfiable set of clauses.

From Wikipedia:

Attempting to prove a satisfiable first-order formula as unsatisfiable may result in a nonterminating computation

Why is that disappointing?


texts: UInt128 - Compute the product of two UInt128's that are each represented by two UInt64's?

texts:
I have a struct like this:

struct UInt128 {
    UInt64 s1;
    UInt64 s2;
}

In this struct, s1 represents the highest 64-bits of my 128 bit integer, and s2 represents the lowest 64-bits of my 128 bit integer.

I'm attempting to implement a method that produces the product of two UInt128's.

My current thought process is that the solution is similar to FOIL, the technique used to expand brackets in algebra e.g. $(a+b)(c+d)$ where we give the result as $ac + ad + bc + ad$, but my issue comes from the fact that I don't understand how to break the result back into two UInt64's.

How can I compute the product of two UInt128's as defined by the struct above?


texts: Is there a database of linear codes with "small" covering radius

texts: Does anyone keep a database of (or including) linear codes with small covering radius? I'm specifically interested in the smallest-dimension codes known  of covering radius R ($2\le R \le 4$ say) for each codimension (up to codimension 10 or 12) over various small fields, especially $\mathbb{F}_3$, $\mathbb{F}_5$ and maybe $\mathbb{F}_7$. There are various papers giving data for specific fields, few very recent, but no integrated dataset that I can find.


texts: Shuffling a list while keeping order relative to related elements

texts:
I'm looking to shuffle a list of the elements $a_1,\dots, a_6, \dots, e_1, \dots, e_6$

while keeping two rules:

if I loop though the list and filter out a specific letter or number it should be in order:

$a_1, a_2, a_3 \dots$ or $a_1, b_1, c_1 \dots$

How can I shuffle the list keeping these rules? I'm using python, so if there's a library that'd be great. Otherwise, just a generic way I could tackle this problem.

Here's an example of a shuffle that would fit the criteria:

$a_1, b_1, a_2, b_2, c_1, a_3, d_1, c_2, d_2, e_1, a_4, b_3,$ $c_3, d_3, b_4, d_4, c_4, a_5, e_2, d_5, e_3, c_5, a_6, b_5, e_4, a_7, $ $b_6, c_6, b_7, d_6, e_5, e_6, c_7, d_7, e_7$


texts: How to the NP hard of a problem that search for a subset of points with maximum scores?

texts:
Suppose in a plane, there is a set of points, whose distance to $(0,0)$ is always 1:

$[(0,1),(1,0),(0.707,0.707),(0.707,-0.707),...]$

Each point is assigned with a weight (possible negative):

$[w(0,1) = 1, w(1,0) = 2,w(0.707,0.707) = -1,w(0.707,-0.707)= -2,...]$

Suppose the standard deviation of the points are defined as the top answer here: https://stats.stackexchange.com/questions/13272/2d-analog-of-standard-deviation

Find a subset of points $S$ such that SUM(w)×STD is maximized.

My gut feeling is that this problem is NP hard. Very similar to knapsack problem. However, knapsack use weight as a threshold. I'm not sure how to transfer the standard deviation here. Any thought on how to prove this would be appreciated!


texts: Showing filling a container with rectangles is hard by reducing from SUBSET-SUM

texts:
Given a set of rectangles, $D = \{ (a_1, b_1), (a_2, b_2) \dots , (a_n, b_n) \}$, where in each pair $(a_i, b_i)$, $a_i$ represents the height of the rectangle and $b_i$ the width, and given another pair $(w, h)$ representing the width and height of a container $C$, does exist a way that taking some of the squares in $D$, the whole container C is perfectly filled? Here, $a_i, b_i, w, h \in \mathbb N$.

I am trying to reduce it from Subset Sum, but can't find the way... Hope you guys can give me a hint over it!


texts: Dynamic all pairs shortest path edge removal

texts:
I have a planar(|E|=O(V)) undirected graph with positive edge weights.

I have already calculated all pairs shortest path with Floyd–Warshall algorithm.

Now I want to recalculate APSP with an edge removed. I'm not interested in the path and just having the distances is enough for me.

I want a highly parallelizable method and I only have one update so there is no need to support multiple edge removals.

Can I do this is something better than O(V^3)?

Edit: I also need to add edges but that could easily be implemented in O(V^2) via simple matrix addition(and thus be highly parallelizable).

Edit: My final goal is to construct |E| new graphs each with only one edge removed from the original graph, and then calculate APSP in a batched mode. In case you are wondering, I want this algorithm to compute a metric, related to APLS(but not APLS itself).


texts: Difference between properties of good hash function: uniformity and randomness

texts:
I did go through Korth's book of DBMS and I got these definitions:

Uniformity:

Each bucket is assigned the same number of search-key values from the set of all possible values.

Randomness:

Each bucket will have the same number of records assigned to it irrespective of the actual distribution of search-key values in the file.

These definitions seem  similar to me. Can anyone please differentiate, I did search on net but can't understand.


texts: How many edges can you add to the petersen graph without changing the crossing number

texts: I am trying to prove what the maximum number of edges that can be added to the petersen graph is without changing the crossing number of 2.


texts: How is a conditional branch instruction implemented in hardware? The instruction checks the sign bit, how does it decide to load pc with the branch address or increment pc to the next sequential address?


texts: Graphs that cause DFS and BFS to process nodes in the exact same order

texts: For some graphs, DFS and BFS search algorithms process nodes in the exact same order provided that they both start at the same node. Two examples are graphs that are paths and graphs that are star-shaped (trees of depth $1$ with an arbitrary number of children). Is there some way for categorizing graphs that satisfy this property?


texts:
Show that the following languages are not regular:

$(1)\ L=\left\{a^nb^mc^k\mid n>k \land n,m,k>0\right\}$

$(2)\ L=\left\{a^nb^mc^k\mid m>k \land n,m,k>0\right\}$

I've difficulties showing that these two languages are not regular by using the Pumping Lemma. Any suggestions?


texts: Modeling tiling problems as SAT problems

texts:
I read that tiling problems can be modeled as satisfiability problems (2-SAT?), but the author did not explain how. Is this true? What would be an example?

By a "tiling problem" I mean you have a matrix and have to fill it up according to some constraint. For example, you might have to fill the matrix with a particular shape, or the values in the matrix have to adhere to some constraint. For example, imagine a partially filled matrix and the rule is that you have to fill it with values that are one more or one less than the adjoining values, or something like that.


texts: Random Access Machines with only addition, multiplication, equality

texts:
The literature is fairly clear that unit-cost RAMs with primitive multiplication are unreasonable, in that they

cannot be simulated by Turing machines in polynomial time
can solve PSPACE-complete problems in polynomial time

However, all of the references I can find on this topic (Simon 1974, Schonhage 1979) also involve boolean operations, integer division, etc.

Do there exist any results for the "reasonableness" of RAMs that only have addition, multiplication, and equality? In other words, which do not have boolean operations, truncated integer division, truncated subtraction, etc?

One would think that such RAMs are still quite "unreasonable." The main red flag is that they enable the generation of exponentially large integers in linear time, and due to the convolution-ish effects of multiplication, this can get particularly complex. However, I cannot actually find any results showing that this allows for any sort of "unreasonable" result (exponential speedup of Turing machine, unreasonable relationship to PSPACE, etc).

Does the literature have any results on this topic?


texts: Regular expression for a palindrome of finite length?

texts:
I have a language $$ L = \{ww^R, w \in \{ab\}^5\}$$

I know this is a regular language because it is finite (since w can only be of length 5). I want to prove it's a regular language, so I'd create a regular expression for it.

Theoretically, my regular expression could be the union of all strings in the language, but is there a concise way to express this rather than writing all possible strings out?


texts: Which algorithm for game matchmaking in tournament

texts:
I organize amateur tournaments every week with random players.
Every week, players sign up, and I get a list with:

Name
Rank (1, 2 or 3)
Role (s) (DPS, TANK and HEALER)

I need to get balanced teams of 6.
Ideally, there are 2 DPS, 2 TANKS and 2 HEALERS but in practice there are not enough healers and I have to make 3 DPS, 2 TANKS and 1 HEALER.

The other problem is that some players register together, up to 3 players grouped.

The process is currently done by hand but I would like to automate it.

I learned about the algorithm Knapsack problem, is this a good track?

Do you have any advice to help me in my research?

Thanks you.


texts: What algorithm to use for substractive machining RT simulation?

texts:
For a CAM (Computer Aided Manufacturing) software, and more specifically, for the simulation of the subtractive manufacturing, I would like to understand how to design the representation.

In subtractive manufacturing (e.g. a Mill), a piece of raw material like a cube or a cylinder is machined. That is, a milling bit (like the bit of a drill) is moved following a path (defined by a GCode program), which slowly remove material from the raw part until the desired piece is formed. Subtractive manufacturing is the reverse process than 3D printers, where material is deposited following a GCode program path.

By representation, I refer to that beige raw piece in the image: how to efficiently represent it in memory, but more important, how to efficiently calculate it new shape, every few milliseconds, based on the path and shape of the tool bit.
Notes: This is not about 3D APIs, I have experience with OpenGL/Vulkan, but about how to calculate the shape modification.
My first understanding of the problem is that each few milliseconds ∆t, I could calculate the parallelepiped produced by the linear motion of the tool/bit from an origin (where the tool/bit is at t) to a destination (where the tool is at t+∆t). And perform a 3D boolean subtract of the raw piece with it.
Note: This is for an end-mill, for a ball-mill (with rounded end of the tool bit) the parallelepiped become a more complex shape.
However, I am not sure that a 3D boolean operation can be performed real-time.
I got suggested to divide the raw piece into small "voxels" where each voxel represent a configurable cubic space (e.g. 1mm^3). This with the intend to simplify the boolean operation.
Is there a common approach to this problem?
Ideas of algorithms would help, but I am more interested in some demonstrated solution: either a solution known to be implemented in some of the major CAM software, or a solution demonstrated to be effective by some research paper.


texts: Bias of first values produced by a family of RNGs

texts:
Suppose I'm doing a large number of pseudo-random but deterministic experiments, where each experiment requires generating several random numbers.

I'm approaching this by having each experiment use a random number generator seeded with a random-looking seed - e.g. hash of the index of the experiment. This is especially convenient for parallelizing my experiments.

I'm wondering if this is a sound way to get good randomness. In particular, this article points out at the end that the first value returned by e.g. Java's random generator (LCG) is highly biased even if you vary the seed.

How can I avoid this bias? Is it sufficient to throw away one or two numbers, as that article suggests? Is there any research on this topic? (I wasn't able to find the right keywords)

Would, e.g., Mersenne Twister behave better?


texts:
I am currently reading Fuss, Futexes and Furwocks: Fast Userland Locking in Linux and came across this quote:

  In a fair locking scheme the lock is granted in the order it was
  requested. This can have negative impact on throughput due to the
  increased number of context switches. At the same time it can lead to
  the so called convoy problem. Since the locks are granted in the order
  of arrival, they all proceed at the speed of the slowest process,
  slowing down all waiting processes. A common solution to the convoy
  problem has been to mark the lock available upon release, wake all
  waiting processes and have them recontend for the lock. This is
  referred to as random fairness. However, this also leads to the
  thundering herd problem. Despite this, it can work well on
  uni-processor systems if the first task to wake releases the lock
  before being preempted or scheduled, allowing the second herd member
  to obtain the lock, etc...

I have a few questions about this quote.

First, does a fair locking scheme result in an increased number of context switches because different tasks put processes into the wait queue at different times and thus by serving processes in the order they were received, we'd be context switching between multiple tasks?

Second, how does granting locks in the order of arrival cause processes to proceed at the speed of the slowest process? Wouldn't this only be the case if the slowest process is granted the lock before the other processes? Similarly, how does having processes contending randomly for the lock solve the convoy problem?

Finally, I don't understand how random fairness is any better on uni-processor systems in comparison to multiprocessor systems. For example, in both cases, all of the waiting processors are woken up, one gets the lock, and the others have to go to sleep again, right? So how does this work well on uni-processor systems?


texts:
Is there already a worst case time complexity proof for the sum of all elements in a power set? I would assume, naively, you have to just add everything, which would run in about 2^n, where n is the size of the set.

For example: A = {1,2,3} Powerset(A) = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3} } Sum(Powerset(A)) = {{} + {1} + {2} + {1 + 2} + {3} + {1 + 3} + {2 + 3} + {1 + 2 + 3} }

I'm defining addition between sets as: A = {1}, B = {2,3}, A + B = {1} + {2 + 3} = 6


texts: Labeling a limited number of points on the screen

texts:
I have a map with up to thousands of points on it.

Now I want to label those points on the screen. But this would only make sense for a limited number of points and the label of points close by should not overlap with others.

What would be a way to go about this to not cover the screen with labels?


texts: Heights series in the DFS traversal of a binary tree

texts:
Assume a binary tree of height N. All nodes have exactly 2 children and all leaves have height N. For example, the following tree has N=3:

             3
           /   \
         /       \
       /           \
      2             2
    /  \          /  \
   /    \        /    \
  1      1      1      1
 / \    / \    / \    / \
0   0  0   0  0   0  0   0

When we do a depth-first traversal  and note the height of each node, we get the following array (for any N>3):

[0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 3, 0, 0, 1, ...]

Note how the head of the array isn't dependent on N and can go infinitely.

I'm looking for a function F that, for any index in that array, would give the corresponding value. For example:

F(2) = 1
F(4) = 0
F(6) = 2

If possible, the function shouldn't be recursive. I do no want to have to iterate through millions of elements to calculate a height at an index far in.


texts: For a logic gate to be universal, must it necessarily be able to perform duplication?

texts:
It is said that a gate that can simulate AND and NOT is universal and able to recreate any classical circuit. I was looking at some of the circuits simulated by NAND, and for some of them, we need to split the output of a gate and direct each of the splits to other NAND gates (see the area circled in red):

If we make the restriction that all gates are reversible (in particular, we require fixed input/output size), does the AND/NOT criterion still hold? Is the ability to "split" outputs (i.e., a gate that can do AND, NOT, and duplicate a $0$ or $1$, e.g. $(0,0,1) \rightarrow (0,1,1)$ ) a necessary/sufficient condition for universality?


texts: Regular languages closed under quotients with arbitrary languages

texts:
When proving that that the quotient of a regular language $R$ and an arbitrary language $B$, I understand you take a DFA $M$ accepting $R$, and then construct a DFA that is the same, but its final states are those from which we can reach a final state of $M$ with a string from $B$. How can we just say it's possible to take such a set?

Does this proof also work for a similar property (I don't know the name) that creates the set
$\{ x \mid \forall y \in B : xy \in R \} $?


texts: Is FACTORIZATION or PRIMES known to be in LOGSPACE

texts:
Are the integer factorization and PRIMES known to be in LOGSPACE?

Recently, it has been shown by researchers that PRIMES is in P. But this does not say anything about LOGSPACE since it is not known if LOGSPACE = P.


texts:
The question is as follows:

I am new to this, and I do not understand how to apply divide and conquer to a matrix, the algorithm that I have come up with is as follows (I am not sure if I am correct)

I thought I can divide the matrix into a matrices of 3 x 3 and 2 x 3 first. Then I will apply sorting of rows over column individually on both the matrices. Finally I will copy the second matrix sorting result over to the first sorted matrix. However, my problem is how do I sort the matrix first in to some order so that my division will yield a correct partition else what happens is, post copy I have to again sort (Which I thought is probably wrong)


texts: Why do we prove X is in NP to prove it is NP-complete?

texts: The steps to show something is NP-complete is to show it is a member of NP, and then show an NP-complete problem reduces to it in polynomial-time. Why is the first step necessary? Is it possible to reduce an NP-hard problem to an NP-complete problem in polynomial time? Because that would be the only instance in which this is important.


texts: Is there a term for mixing deferred and eager evaluation?

texts:
I've written a model which utilises deferred evaluation for many aspects of its feature but in one instance of its use it is mixed with threaded eager evaluation for things that are expected to be used at some point.

Is there a term for mixing lazy and eager evaluation, possibly when mixing with threading?


texts: How to statically type polymorphic lambdas using hindley milner style type inference

texts:
I am playing with a simple implicitly typed functional language and have implemented type checking using a Hindley Milner style system. In order to guide code generation, I want to tag each term with its type during type inference.

Of course my language uses lambda expressions and the implicit typing should enable nice polymorphic use of those lambdas. Unfortunately, this goal clashes with the static type tagging as each lambda can be tagged only once which specializes it for a particular set of argument and closure types. It is also not possible to statically copy lambdas on each use, as this requires dynamic knowledge.

I thought about dynamically copying and tagging lambdas at runtime but this would involve quite some work and possibly overhead. Is there a standard solution for this kind of problem?

Update 1
The following example might help to clarify my point.

add := func (a, b) begin a + b end
a   := add(2, 3)
b   := add('hello', 'world')

The lambda add has polymorphic type (T1, T1) -> T1 and during type checking add is first instantiated to (Int, Int) -> Int and then to (Str, Str) -> Str, everything fine so far. But, during compilation, I want to have the tree representing add to be annotated with conrete types. Unfortunately, add is a single tree and that tree is either tagged with the first or the second type instantiation.

I could create copies of the add tree for each application but it seems to me that this is only possible at runtime, when the actual target of a call is available. On the other hand, maybe I could somehow let bind copies of the lambda for each instantiation and mangle the type variant into the name? That would entail updating references and I'm not sure whether this is actually possible in general? What about lambda return values, conditionals and so forth?

Update 2
I still feel like I did not describe my problem sufficiently. My language is really rather simple and I would like to stick with a simple typing solution. I found an article series that exactly details my problem and even explores the approaches that I envisioned: type spacialization per application and selecting specialized trees using a structured ler naming scheme.


texts: I wanna determine whether an image belongs to warm/neutral/cool tone. I find Kelvin color temperature to calculate the average temperature of an image over all piexls. But the result seems not good. Can anybody point in the right direction to determine the tone of one image?


texts:
Starting from a random node, which of these series can be a BFS traversal (L to R)?
1 MNOPQR
2 NQMPOR
3 QMNPRO
4 QMNPOR
Now, I understand that my answer (1- MNOPQR) is wrong because I got confused with DFS.. and the answer is 3. but why isn't 4 right as well? I mean, it defines BFS... no?   Thanks!


texts: Isn't measuring the results the main bottleneck of quantum computers?

texts:
I have researched a bit about quantum computers, and hopefully understood that the main advantage does lie in the utilisation of superpositions in order to compute (manipulate qubits) in parallel instead of sequential.
While conventional bits can only hold a single information at a time, qubits are capable of holding two states simultaneously - let say i want to add two 4-bit numbers - not only I don't need 8 bits (4 bits for each number) for just a single addition, but with just 4 qubits I am able to "encode" for example 8 additions ((2^4)/2) and compute them all at once.
To visualize my idea:
4 qubits, therfore 2^4 states:
01.) 0000
02.) 0001
03.) 0010
04.) 0011
05.) 0100
06.) 0101
07.) 0110
08.) 0111
09.) 1000
10.) 1001
11.) 1010
12.) 1011
13.) 1100
14.) 1101
15.) 1110
16.) 1111

Let's assume we have circuit that adds two consecutive "lines" (=states) together and stores the value in the latter one, i.e. we add 1.) and 2.) and store the sum in 2.), we add 3.) and 4.) and store the sum in 4.) and so on and so forth.
But
... how am I able now to "read" (measure) two results at the same time? What do I mean by that? What if I not only want to measure the result saved in line 1.), but also line 15.)?
I mean, the moment I measure - let's say line (=state) 1.) - the qubits act like a bit, and only one single information is given while the other informations are loss.
It may be true that quantum computers compute in parallel, but at the end, I am only able to measure a single outcome-scenario, thus losing the advantages of parallel-computation.
I know that I misunderstood something, or even everything with regards to quantum-computers. That's why I am asking.
Tldr: What advantages do we gain from quantum-computer's parallel calculations if we are able to measure only a single outcome while losing every other possible outcome? It feels like sequential computing with extra steps.
_


texts: Minimum number of tree operations to normalize a labeled tree

texts:
Given a binary tree with labels on the leaves, like $(bc)(ad)$ or $((af)e)(c(db))$, which we can interpret as a product of terms with respect to a commutative associative operation, how many applications of commutativity (swapping the two children of a node) and associativity (tree rotations) are needed to bring this tree to a sorted normal form like $a(b(cd))$ or $a(b(c(d(ef))))$? Examples:

$$(bc)(ad)\mapsto((bc)a)d\mapsto(a(bc))d\mapsto a((bc)d)\mapsto a(b(cd))$$

\begin{align}
&\phantom{{}\mapsto{}}((af)e)(c(db))\\
&\mapsto (a(fe))(c(db))\\
&\mapsto (a(fe))((cd)b)\\
&\mapsto (a(fe))(b(cd))\\
&\mapsto (a(ef))(b(cd))\\
&\mapsto a((ef)(b(cd)))\\
&\mapsto a((b(cd))(ef))\\
&\mapsto a(b((cd)(ef)))\\
&\mapsto a(b(c(d(ef))))
\end{align}

There are $C_{n-1}\cdot n!$ possible trees on $n$ elements, and about $2n$ possible operations to apply at each stage, so the information theoretic bound gives $\Omega(\log_{2n}(C_{n-1}\cdot n!))=\Omega(n)$. On the other hand, if we first fully right associate, then we can perform adjacent swaps with $O(1)$ operations, leading to an upper bound of $O(n^2)$ operations.

I suspect that $O(n\log n)$ operations suffice, perhaps even $O(n)$, but I have not been able to improve on the above bounds. I know that $O(n)$ operations work if it is possible to perform exchanges in $O(1)$, but every element has its depth change by at most 1 per operation, so exchanges are rather expensive ($O(n)$) in this model. Probably we want to keep the tree balanced during the sorting, but assuming a balanced tree it's not clear how to sort effectively by block swaps.


texts: What is the most efficient way to test whether a set $X \subset \{0, 1\}^n$ and its complement $\{0, 1\}^n \setminus X$ are linearly separable?

texts: I am interested in algorithms that have optimal running time, and ideally which are also very easy to implement.  If you can also give some tips on how to implement the algorithm(s) you mention in the answer, that would be great.


texts: Is this the correct time complexity of my algorithm?

texts:
I have an algorithm broken down into the pseudish code below. But the gist of it is, we go through every person in a list, we then ask them to talk to all of their friends. Every time we choose a person to eval in the list, it costs $log N$ time. Every time that person talks to a friend it costs $log N$. What is the time complexity? Is my answer right?

My answer: $O(N \cdot log(E \cdot log(N)))$

List[People] // N

forall People in List:  //O(Log N) to get a person in list
   forall friends of Person:    // Person has a set of Friends E that is [0, N)
       Person.talkToFriend(friend)  //Costs O[LogN] to talk to a friend


texts: Maximizing integer sets intersection (with integer delta)

texts:
There are two sets of integers with different numbers of items in them.

X= { x_0, x_1, ... x_n }, x_0 < x_1 < ... < x_n
Y= { y_0, y_1, ... y_m }, y_0 < y_1 < ... < y_m

And there is a function of a single integer defined as

F(delta) = CountOfItems( Intersection( X, { y_0+delta, y_1+delta, ... y_m+delta) ) )

That is - i add delta integer to every element of the Y and then count how many same integers  are in the X and the modified Y.

And then the problem - find delta that maximizes F(delta).

max( F(delta) ), where delta is integer

Is there some "mathematical" name for such task and optimal algorithm for this?
Obviously i can use brute-force here and enumerate all possible combination - but it does not work for big n and m.


texts:
I am reading the lecture notes. I am trying to understand Morris' algorithm on page 2. The Morris' algorithm is as follows.

Problem: Given an input stream $\sigma$, compute (or approximate) its length $m$.

Initial: $X=0$
For each item in the stream, increment $X$ with probability $\frac{1}{2^X}$.
Output: $2^X-1$.

It is said that $\mathbb{E}[2^X-1]=m$, where $X_m$ is the value of $X$ after seeing $m$ items.

How to show that $\mathbb{E}[2^X-1]=m$? Any help would be greatly appreciated.


texts: Does the time complexity of a problem change with encoding of the problem?

texts:
Suppose I have a decision problem $D$ and I encode it to a language $L \subset \{0,1\}^*$. Now, I can also encode it to a different language $L'$.

Is there any theorem relating the time complexity of $L$ and $L'$?

How does the time complexity of a problem change with different encodings of the same problem?


texts: Algorithm: Given a large semiprime number N, find the smallest value of $A$ such that $N + A^2$ is a square

texts:
Given a large (100+ digit) semiprime $N$, I want to find the least positive integer $A$ such that $N + A^2$ is a perfect square. For example, if $N = 299$, then I want $A = 5$, because $299 + 5^2 = 18^2$. (Equivalently, I want to find the least perfect square $s$ where $s - N$ is also a perfect square. In the previous example, $s = 18^2 = 324$.)

Thus far, I've only managed to do this with guess-and-check, which is computationally intensive for larger values of $N$; so I'm looking for an efficient algorithm.

Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.


texts: Does there exist a way, within Lambda Calculus, to discover if two free variables are the same?

texts:
Using Church's $\lambda x.(\lambda y.y))$ as false and $\lambda x.(\lambda y.x))$ as true, and given two free variables $g$ and $h$:

Could there exist a function $eq?$ such that $(eq?\ g\ h)$ is false, and $(eq?\ g\ g)$ is true?

I typically would show my work here, but as of right now, I honestly have nothing except a hunch that it's categorically impossible.


texts: Could the halting problem in theory be solved for any finite set of Turing Machines?

texts:
Suppose there's a program A that decides whether or not every program halts.
Then we could construct program B that invokes A and does the opposite. Do I halt? If so, loop. Do I loop? If so halt.
That shows we cannot construct program B.
HOWEVER, that assumes B can be embedded in A.
Could there exist a program B that decides all programs of length N or less - their halting, such that B is greater in length than N?
In other words, the "halter decider" is necessarily bigger than the programs it's proving.
Trivially, there exists a computer program that decides the halting of all programs of length 100 or less. There's 2^100 programs of length 100 or less (assuming programs are encoded in base-2). Therefore there's a base-2 number with length 2^100 where each bit corresponds to whether or not the program halts.
Thus, you can solve the halting problem for any arbitrary length or less.
In general, given a finite set M of Turing Machines, there exists a Turing Machine that decides the halting problem for M
Anything wrong with this logic?


texts: Number of ways to pass edges of a cycle exactly n times

texts:
Consider an undirected network consisting of a single cycle with 6 nodes according to the below image with a given starting node.

Is there a way to get an expression for the number of paths one may take to pass each edge exactly n times?


texts:
Given a matrix $A$ with entries $a_{ij} \in \{0,1\}$, the matrix $B$ is formed by $b_{ij}=a_{ij} + a_{i+1,j} + a_{i,j+1} + a_{i+1,j+1}$. $B$ has one row and one column less than $A$. The problem is given such a matrix $B$ to find one possible matrix $A$ that produced $B$. This can be done by reducing the problem to 2-SAT, but after many attempts I'm I am not sure how to approach it.

All entries $b_{ij}\in\{0,1,2,3,4\}$, but given for example $a_{ij} + a_{i+1,j} + a_{i,j+1} + a_{i+1,j+1} = 2$ is there a 2 CNF formula that is equivalent to that (and for the other cases when the entry is $1$ or $3$)?


texts: Functions with small support have small circuits

texts:
I have been trying to understand the use of circuit models for boolean functions, and came across this question, that I am trying to struggle to understand:
Show that if a function $f\colon \{0,1\}^n→\{0,1\}$ has a support of size $k$, then it can be decided by a circuit of size $O(nk)$.
I understand that for any binary functions of this sort, the maximal size of the circuit is $O(n2^n)$, and I have a feeling that this could be useful for proving the statement, but I am not exactly sure where to proceed from there. Furthermore, I also understand that the "support" referred to in this question is actually the language defined by the function, but again, this leads me nowhere.
Any help on this would be much appreciated.


texts: Calculate probability in graphical model

texts:
I have the following graphical model, in which I wish to compute $p(Intelligence = 1|Letter = 1, SAT = 1)$

But I'm not sure how to rewrite $p(Intelligence = 1|Letter = 1, SAT = 1)$? I was told to consider the formula $p(D,I,G,L,S)=p(D)p(I)p(G|D,I)p(S|I)p(L|G)$ (which applies to this model), but I don't see how someone can get something with $p(I|L,S)$? Is it correct to assume $p(I|L,S)=\frac{p(I,L,S)}{p(L,S)}$?


texts:
I understand that every modern human made computer is being operated by time sharing operating systems which allow two or more users running two or more processes at once each, from two different terminals.
Take for example playing two songs at once: One from YouTube and one from MP3; they appear "mixed" but the "particles" of each one are being played alone in a tremendous velocity so to the human mind it appears "mixed" but not really is.
Is time sharing an illusion?
Is it true to say that even time sharing operating systems still handle each process alone in tremendous velocity so that the time sharing is just an illusion of "present" but is actually only the past and the future so two or more processes can't really be handled by one single processing unit at the exact same time?


texts: What counts as automatic program analysis?

texts:
I'm trying to understand the definition of program analysis on Wikipedia:

  Program analysis is the process of automatically analyzing the behavior of computer programs regarding a property such as correctness, robustness, safety and liveness.

What is the meaning of "automatic" here?

Are parsers static analysis tools, since they will throw an error if they encounter syntactically invalid code?

Is running a program an example of dynamic analysis, since it will provide me with an output (though I still have to interpret it myself)?

What if I explicitly throw a this can't happen exception when the program reaches an invalid state?

What about using a debugger to pause execution?


texts: Dynamic connectivity in forests with constant query time

texts:
I'm interested in the dynamic connectivity problem for forests. In this problem a forest is subject to updates (edge insertion that do not create cycles and edge deletion)  and queries if two nodes are connected.

Link cut trees and Euler tour trees supports these three operations in $O(\log n)$ (Erik Demaine's notes). The results of Eppstein at. all (Sparsification—a technique for speeding up dynamic graph algorithms, JACM, 1997) for general graphs are $O(\sqrt n)$ for updates and $O(1)$ for queries.

In my use case queries are more common than updates, so I'm looking for an alternative structure (the Eppstein structure is too general and too complicated to implement) that supports updates in sublinear time and queries in constant time. Is there such structure?


texts: Prime checking and factorization with just bit cheking

texts:
I've read about some methods of prime factorization like here and here. However, I'm wondering: what can we do in prime factorization with just some bit manipulation and without other variables/constants?

In base 10, we can get some hints about the factors of an integer just be checking the digits:

digit's place is even --> int is even
digit's place is 0 of 5 --> int is divisible by 5
sum_of_digit % 3 = int % 3
sum_of_digit % 9 = int % 9

Given an integer num as a bit array, how can we check for num's primality and guess or extract its prime factors just by looking at its bits like we do with digits in base 10?

   There are 5 0's --> (num % (2^5)) = 0
            / \
           /   \
           |   |
1010101110100000
      | |      ^
      | |      | last bit is 0 --> num is even
      | |
       v
may be these 3 bits can give some information?

What's allowed:

bit-manipulations which take 1 argument are allow. This includes functions like not but not xor.
ifs and loops are allowed but bits in num will be used for the flag. (no using if num > 2)
num is the only variable/constant allowed to be declared. We can not(num) (flip every bits in num) but not num - 2 (2 is another var/const).
Operating on bits only in num like summing all the bits (bit_sum(20) = bit_sum(b1010) = 2 because there are 2 1s)

Bonus if the operation can quickly be done by hand like the given examples for base 10.


texts: Why does the Toffoli gate output c XOR (a AND b) instead of just a AND b?

texts:
The Toffoli gate takes in three inputs and gives out three outputs, and is often referred to as the quantum AND gate.

It takes in a,b,c and gives out a, b, c XOR (a AND b).

Why does it do that, instead of just giving out a,b,b AND c?  or a,b,(a AND b)?


texts: Confusion about proof of undecidability of REGULAR TM in Sipser's book

texts:
in the book "Introduction to the Theory of Computation" by Michael Sipser there is an example of undecidable languages in which there is a language REGULR_TM which is described as follows :

REGULAR_TM = { <M> | M is a Turing machine and L(M) is regular language }.
 Well, Sipser says that this is an undecidable language since we cannot have a decider to decide this language. Because if we could, we could create a TM that decides ATM which we know previously that is undecidable. so this could cause a contradiction.
Here is the proof from this book :

Proof. We let R be a TM that decides REGULAR_TM and construct TM S to decide ATM. Then S works in the following manner.

S = "On input <M, w>, where M is a TM and w is a string:

Construct the following TM M2.

M2 = "On input x:

  1. If x has the form 0^n 1^n, accept.

  2. If x does not have this form, run M on input w and accept if M accepts w."

Run R on input <M2>.
If R accepts, accept; if R rejects, reject."

Now my question is, is this kind of constrcuting a TM S correct?
the part that is really confusing me is the part that says "run M on input w and accept if M accepts w". this is the whole question for Atm. If we could answer that question why we need a machine M2 to feed it into the R and output the result of R. We just "run M on w".

Also for some languages that [we know] are decidable we can have the same argument and conclude that it is not decidable.

----- EDIT -----

Ok. let me explain my confusion a little bit different. consider language A_DFA :

A_DFA = { <B, w> | B is a DFA that accepts w }

We know it is decidable (Proof in the textbook). so we reduce ATM to A_DFA.

PROOF. let R be Turing machine that decides A_DFA. we construct TM S to decide ATM. then S works in the following manner :

S = "On input <M, w> where M is a TM and w is a string:

Construct the following DFA D:

DFA D has only one state q0 which is also the start state.
all arrows come back to q0 itself. if M accepts w add q0 to F. (F is the set of final states.)
Run R on <D, w>
accept if R accepts; reject if R rejects.

It is interesting that I kind of understood the problem of my own work when I was writing the proof of reduction of ATM to A_DFA. I write it so that if it is true others can learn if it is wrong others will correct it!

I think that because M2 in the first proof is a Turing machine we CAN say that if "M accepts w". (we somehow embedded the work of "if M accepts w" into M2 without actually running M on w). but in my own proof of ATM -> A_DFA the problem is that we cannot construct DFA D without actually running M on w. so we cannot construct D. That's the reason why the first proof is true and my proof is wrong.


texts: Mainstream publication venues for Internet of Things (IoT)

texts: I am interested in reading the research literature on Internet of Things (IoT).  I am especially interested in theoretical research (eg. papers where techniques from graphs or algorithms are utilized).   What are the leading journals and conferences in IoT?


texts: Is the language of palindromes context-free?

texts:
Is the language $\{ w=w^R \mid w \in \{0,1\}^* \}$ a context-free language?

I am confused in deciding whether the language is context-free or not, that is one of my problems, I do a pumping lemma proof and what I get is that it is not a context-free language, but I want to make sure again.


texts: Understanding the Transition points of a BST

texts:
I'm trying to understand the definition of Transition point of a BST, as given in  Demaine, Erik D., et al. "Dynamic optimality-almost." SIAM Journal on Computing 37.1 (2007): 240-251

Define the transition point for [a node]
y at time i to be the minimum-depth node z in the BST Ti such that the path from
z to the root of Ti includes a node from the left region of y and a node from the right region of y.

with

Define the *left region of [a node] y to consist of y itself plus all nodes
in y’s left subtree.
Define the right region of [a node] y to consist of all nodes in y’s right subtree

I'm having trouble understanding how a path from a node to the root can pass through both the left and the right subtrees of a given node.
Since each node forks the tree, a path (towards the root) comes either from the left or right subtree.
Also, in this picture from the notes of a Demaine's course the transition point Z is drawn above the node y (i.e. closer to the root than y):

I understand that the left region of a node includes the node itself but this seems to reduce the definition to "the root of the right region".
Now, the right region may not even exist, an apparently that's a minor technical flaw.
Clearly, I must be missing something with my understanding of the transition point definition.
What's wrong with my interpretation?

Example
For example, given the following tree

For the nodes B, D, G, H, I there is no definition of the transition point (because there is no right region in the first place), assuming  I understood the linked answer correctly.
The left and right regions of the remaining nodes (F, E, C and A) should be these ones

With the left region in blue and the right region in red.
Now, since the path from transition point to the root must include a node from both regions (of a given node y) and since these regions' nodes are, by construction, at least as deep in the tree as y (i.e. at the same distance from the root as y or farther away), the transition point cannot be above y (when drawn in a picture of the tree).
Finally, for a path (to the root) to cross both regions it must originate in the right region and pass through y.
That's the only way I can imagine such a path.
Then, since the transition point must be of minimal depth, the root of the right region seems to be the only candidate.
In the picture below the light-green arrows depict the path from the Transition point to the root. The transition point is the node close to the rounded end of the array.  The dark-green stars mark the node in the left and right regions (of a given node) the path goes through.

So, in this example, the transition points should be C, E, H, J.
But I'm sure something's off, it would be great to have the correct transition point worked out for one node of the tree in the example.


texts:
Is it known whether the implication $\mathsf{NEXP} = \Sigma_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds?

(The question is inspired by well-known $\mathsf{NEXP} \subseteq \mathsf{P/poly} \Leftrightarrow \mathsf{NEXP} = \mathsf{MA}$.)


texts:
Since Earley parser finds all possible application variants for a token, can it parse text in parallel, unlike the usual parser like stack-based, etc.
You just need to modify the start of each parallel chunk of tokens, then while going backwards while constructing a table you combine and validate the found rules like in standart Earley approach. But since vector operations are done there, it is possible to parallel this too. And splitting on tokens also. So its (theoretically, i haven't see project like that)  GPGPU support for Earley parsing.


texts: Complexity of the language of all TMs $M$ such that $L(M)$ is decidable

texts: Let $$R = \{\langle M \rangle \mid L(M) \text{ is decidable}\}.$$ Is $R$ recursively enumerable or co-recursively enumerable?


texts:
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 208:

  The internal state is kept in six memory registers. Each time another bit is input, the values in the registers are shifted to the right. For example, if 111 is input and the initial state is all zeros, then the  internal state, written left to right, will become 100000, 110000, and 111000, after the first, second, and third bits have been input, respectively. The output bits will be 11, followed by 10, and then 01. It takes seven shifts to flush an input completely so that it does not affect the output. The constraint length of this code is thus $k=7$.

  A convolutional code is decoded by finding the sequence of input bits that is most likely to have produced the observed sequence of output bits (which includes any errors). For small values of $k$, this is done with a widely used algorithm developed by Viterbi (Forney, 1973). The algorithm walks the observed sequence, keeping for each step and for each possible internal state the input sequence that would have produced the observed sequence with the fewest errors. The input sequence requiring the fewest errors at the end is the most likely message.

My question is about this part:

  For small values of $k$, this is done with a widely used algorithm developed by Viterbi (Forney, 1973).

My question is how do they determine whether the value of $k$ is considered small or big? What is the threshold value for $k$? For example, length of this code is 7 and they considered it a small value. How about $10$? How about $20$? Are they considered small values or large values? I'm curious about the threshold value of $k$.


texts: Pretend you want to search through a max-heap to find a specific element. I know there is no such option but still... Would it take worse case O(n) or O(logn) time? I am assuming O(n) since the property of a max-heap doesn't really help us unlike a bst. Thanks.


texts: Weight of minimum spanning tree of G and T

texts:
We have undirected weighted connective graph $G=(V,E)$, We also have a minimum spanning tree $T$ of $G$.
Let $v$ be some vertex.
We have new graphs, $G'$ and $T'$.
$G'$ and $T'$ are same $G$ and $T$, except the extra node $v$ witch is connected (with new weighted edges) to the same nodes in both graphs.
I need to prove that $G'$ MSP has the same weight as $T'$ MSP.
I was thinking about using kruskal or prim algorithm to show that Given a MSP of $T'$, We can use kruskal or prim on $G'$ to find it, with no results.

Any idea?


texts: Complexity of computer algebra for systems of trigonometric equations

texts:
As discussed in this question, I drafted a spec algorithm that hinges on finding a specific root of a system of trigonometric equations satisfying the following recurrence:

$\qquad f_{p_0} = 0\\
\qquad p_0 = 2\\
\qquad \displaystyle
  f_{p_n}(x) = f_{p_{n-1}}(x) + \prod_{k=2}^{p_{n-1}} (-\cos(2\pi(x+k-1)/p_{n-1}) + 1)\\
 \qquad \displaystyle
 p_n = \min\left\{ x > p_{n-1} \mid f_{p_n}(x) = 0\right\}$

Playing with this system a bit over on Wolfram|Alpha, it seems I can get specific answers to the recurrence from their computer algebra system. Unfortunately, I can find no specific documentation on the methods they're using to solve my equations.

My question, then:

  What methods (and what time and space complexities) do computer algebra systems use to solve these forms of equations? I suspect the Gröbner basis is commonly used, but I could be very wrong.


texts: Is Morse code without spaces uniquely decipherable?

texts:
Are all Morse code strings uniquely decipherable?  Without the spaces,

......-...-..---.-----.-..-..-..

could be Hello World but perhaps the first letter is a 5 -- in fact it looks very unlikely an arbitrary sequence of dots and dashes should have a unique translation.

One might possibly use the Kraft inequality but that only applies to prefix codes.

Morse code with spaces is prefix code in which messages can always be uniquely decoded.  Once we remove the spaces this is no longer true.

In the case I am right, and all Morse code message can't be uniquely decoded, is there a way to list all the possible messages?  Here are some related exercise I found on codegolf.SE

https://codegolf.stackexchange.com/questions/36735/morse-decode-golf
https://codegolf.stackexchange.com/questions/131/morse-code-translator


texts: Can someone give me an explanation of how dcaches works?

texts:
So, I'm trying to do a computer architecture assignment and there's a question about dcaches. Here's the question:

  Given a 16 word dcache initially filled with word address 0, 1, 2, …15
  memory data (referenced by the datapath in that order). Below is the next
  sequence of data memory address references given as word addresses.
   1, 18, 2, 3, 4, 20, 5, 21, 33, 34, 1, 4

  a) Assuming the dcache is direct-mapped with one-word blocks, list if each
  reference is a hit or a miss. Show the state of the dcache after the last reference. What is the hit rate for this reference string?

I'm not asking for a solution but would just like to know what is considered a miss or hit and how this is calculated? Also, what would be the difference if the dcache had a two-word blocks instead of 1?

Any help is greatly appreciated.


texts: How to implement recursive solution with large number or parameterized possible next steps

texts:
I was looking at a recursive solution for the robot on a grid problem which basically states that there is a robot on the top left corner on a grid and you are supposed to find a path to the bottom right of the grid and the robot can only move down or to the right.  Below is the recursive function for the solution

public static boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path) {
        // If out of bounds or not available, return.
        if (col < 0 || row < 0 || !maze[row][col]) {
            return false;
        }

        boolean isAtOrigin = (row == 0) && (col == 0);

        // If there's a path from the start to my current location, add my location.
        if (isAtOrigin || getPath(maze, row, col - 1, path) || getPath(maze, row - 1, col, path)) {
            Point p = new Point(row, col);
            path.add(p);
            return true;
        }

        return false;
    }

I understand the solution, at every recursive call it checks if it is at the bottom right or if going down one step or going right one step takes it to the bottom right.

However I was thinking that this solution only works because there are only two possible next steps (down or right) that we are easily able to hardcode and connect with the || operator.  But what if there were N different next steps? In that case we would need to call the recursive getPath() function within a for loop from 1 to N.  But then how would we check if any of the 1 to N recursive calls return True? In this case it would not be possible to connect all of them with an || operator.  Would something like the following work?

public static boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path) {
        // If out of bounds or not available, return.
        if (col < 0 || row < 0 || !maze[row][col]) {
            return false;
        }

        boolean isAtOrigin = (row == 0) && (col == 0);

        if(isAtOrigin){
            Point p = new Point(row, col);
            path.add(p);
            return true;
         }

         for(int i:N){
             if(getPath(maze,row,col-i,path)){
                Point p = new Point(row, col);
                path.add(p);
                return true;
             }
         }

        return false;
    }

Is this a valid solution for the change in the problem that I suggested? I think what is throwing me off here is that in the original solution all the recursive calls are made at the same time within the if statement, but here they are called sequentially in the for loop.  Is that still valid?


texts: Can we apply the Master Theorem to the following recurrence?

texts:
Our recurrence is

$$
T(n)=
\begin{cases}
T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if $n>1$} \\
1 & \text{if $n=1.$}
\end{cases}
$$

I have identified $a = 1 > 0$, and $b = 2 > 1$. I am having trouble identifying the $c$ (for $n^{c}$ in $f(n) =(\log(n))^{2}$. The best I could break it down to was $(\log(n))^{2} = \log(n)^{1}*\log(n)^{1}$, which doesn't seem to be the form we are looking for, as $\log(n) \ne n$. Also, how do we take the floor operator into account?

If it follows that we can't apply the Master Theorem (which seems to be the case), what is the culprit?


texts: Algorithm Selection for Classification problem

texts:
I've been working on a developing a product selection network for my workplace. I work with lots of chemicals and the clients don't always know what they want/need so most of the time I have to ask a bunch of question, collect useful/ignore useless information, then make a selection from there. Discussions take place over the phone.

Ideal situation In terms of information collection/flow:
1. I ask a probing question which specifies which feature I am referring to
2. Client answering question and speech recogniser converts voice to text filling in feature input.
3. Text summariser searches the feature and reduces down to specific key words.
- For example: Me: "what kind of application are you looking to perform?"
               Client: "I'm wanting to adhere two pieces of wood together"
               Feature summarised to: adhere, wood
4. Once feature vector has enough information the network recommends the most suitable product.

Problems:
1. Clients tend to waffle and give useless information therefore network will need lots of training data.
2. Once a question is asked - client may not directly answer that question and may incidentally answer another feature question.

I would think the logical place to start would be a speech recognition RNN - I have written a weak tensorflow one however I think I'll just look to tap into Google's cloud speech recognition API here. This is where I get stuck - should I just use a simple forward/back propagation network from here and treat it as a classification problem or is there another way to do it?

Any direction pointers would be greatly appreciated.

Kind Regards, Andy


texts: Why is a deterministic Turing machine a special case of a probabilistic Turing machine?

texts: I have no formal training in computer science as I have not yet taken any such classes, so perhaps this question appears naive.  I was reading about BPP and it was claimed that a deterministic Turing machine is a special case of a probabilistic Turing machine.  I don't understand why this is.


texts: For signed integers, why don't representative the smallest number as all zeros in binary, and the largest as all ones?

texts:
I'm reading up on bitwise operators, complements, and two's complements, and I'm wondering why the lower limit of a range (aka lowest negative number) isn't all zeroes in binary, and the upper limit isn't all ones.

For example, for 8 bit integers, why don't we represent -128 as 0000 0000, -127 as 0000 0001, -1 as 0111 1111, 0 as 1000 0000, and +127 as 1111 1111?


texts: What type of math classes are good to take for computer science majors?

texts: I am an undergraduate computer science student at Cal Poly (SLO) and I have some flexibility in which math courses I can take, but I don't know which math courses would be most beneficial. I have already taken a statistics/probability course and Calculus 3. My options are pretty flexible for a Mathematics/Statistics elective. What type of math is most useful to know for the field of computer science? I still don't know what type of career I would like, so general answers are okay; or some specific classes for specific career paths would be great too. Thanks!


texts: Approximation Algorithms in planar graphs

texts: I have an NP-hard problem which I'm not going to tell you, and I suspect it becomes easier on planar graphs. I tried method Baker but it did not work because we have a restriction on vertices that avoid us to solve the problem in part of the graph then calculate the union of the solution in each part. Also, we try bidimensionality and Klein method but they didn't work because our problem is not contraction closed. Are there any general methodologies for approximation algorithms [or algorithms in general] in planar graphs beyond bidimensionality and Klein's method, for example when a problem is not contraction closed?


texts: When does an extendible 1:1 p.c. function have a 1:1 computable extension?

texts:
A partial computable function $\varphi_e$, defined on a c.e. set $W_e$, is called extendible if there exists some computable function $f$ which extends $\varphi_e$, i.e. $\varphi_e(W_e) = f(W_e)$.
My question is what are the conditions for a p.c. function $\varphi_e$ to have an injective extension.

So far I have found some necessary conditions:

Obviously, $\varphi_e$ itself should be injective.
$|\overline{W_e}| \leq |\overline{\varphi_e(W_e)}|$. Because $f(\overline{W_e})$ should have no intersection with $f(W_e) = \varphi_e(W_e)$, so $f(\overline{W_e}) \subseteq \overline{\varphi_e(W_e)}$.
This rules out $\varphi_e(x) = x/2$, defined on even numbers. And also any other surjective partial function.

I couldn't manage to find a sufficient condition yet.


texts: Global minimum when noisy estimates of function available

texts: I am interested in knowing about algorithms for finding global minimum when noisy estimates of the function are available.


texts: Degree Reduction in Max Cut and Vertex Cover

texts:
I have been reading Alimonti and Kann's paper "Some APX-Completeness results for cubic graphs" and I don't understand why the degree-reduction gadgets for Max Cut and Min Vertex Cover have to be different.

Here are the two gadgets in question. The Min Vertex Cover gadget simply divides a degree $n$ node $v$ into a chain of nodes $v_1,u,v_2$, where $v_1$ and $v_2$ share the edges of $v$, increasing the Min Vertex Cover by 1 in the process. The Max Cut gadget on the other hand is rather more complicated and involves cycles. What I don't understand is why the simple Min Vertex Cover gadget can't be used for Max Cut?

Consider a degree 4 vertex $v$ in Max Cut. If you unfold the vertex as $v_1,u,v_2$ (as in the Min Vertex Cover example) you are adding 2 edges to the graph, both of which can be cut by placing $u$ on the opposite side of the cut to $v_1$ and $v_2$, so wouldn't the Max Cut just increase by 2? I'm probably missing something but I don't know what it is.


texts: Number of substrings possible with even characters

texts:
Consider a string 'ABBAA'
Possible substrings with even number of characters are 4
'ABBA' : Count of 'A' is even and 'B' is even
'AA' : Count of 'A' is even and 'B' is even ($0$)
Similarly 'BB' and 'BBAA'.
So a total of $4$ substrings are possible.
If given string is 'AABCCBBCAA'
substrings possible are "AA" "BB" "AA" "CC" "BCCB" "CCBB" "CBBC" "CBBCAA" "AABCCB"
So total $9$ substrings
Is there any pattern or sequence or algorithm to find this?


texts: Multi agent graph traversal with edge discovery

texts:
Suppose we are given a set of agents (say $P_1 , \dotsc, P_M$), an undirected graph G(V,A) and a set of initial vertices on $G$ where each agent is located. Initially only the edges connected to these initial set of vertices are globally known to all agents.  At each step, the agents can traverse an edge connected to their current vertex. If the agent happens to arrive at a vertex $v$ which was previously unvisited by any player, then all the edges connected to $v$ becomes global knowledge to all agents. The aim of the agents is to reach a vertex $v_G$, it suffices if any one agent reaches $v_G$.

I was wondering if this community can point me to problems that have a similar flavor in literature that has been studied before.

One interesting question would be to find the minimum number of steps required to reach $v_G$. I can think of a simple Dynamic Programming(DP) based algorithm for computing the minimum number of steps. A state in the DP would be, the number of steps elapsed, the  vertices visited by all agents and the current vertex occupied by each agent. It is simple to expand these states and compute the minimum number of steps. However the number of states expanded can be exponential in $|V|, |A|, M$. I am wondering if one can do better than the DP sketch I just described. More formally, what is the complexity in determining the minimum number of steps.


texts: ILP representation of the number of maximal 1 sequences in a row

texts:
I am currently using an ILP to model events which occur on some input sequence from $1...n$. These events modify the input sequence in order to obtain a desired sequence. Each event can happen on some consecutive range $(i,j)$ and no two events can overlap. Therefore, I can represent events by some matrix $a=\{0, 1\}^{n\times n}$ where $a_{i,j} = 1$ iff there is an event that begins at $i$ and ends at $j$ ($i<=j$).

Unfortunately, this results in $O(n^2)$ variables and in some cases $O(n^3)$ or greater number of constraints. It would be ideal if instead I could represent these events as a row $a'=\{0,1\}^n$, where $a'_i = 1 \iff \exists a_{p,q}\quad  \text{s.t.}\quad  p\leq i\leq q \land a_{p,q} = 1$
i.e. a position $a'_i=1$ iff there is an event that modifies position $i$.

Since I am optimizing over the number of events, at the moment I am minimizing $\sum a_{p,q}$, since it represents the number of events. If I ditch $a$ and try to only use $a'$, I am left with some row, for example $a'=[1,1,0,...,1,0,1]$.

Question 1: I want to represent the total number of events given $a'$. Currently, I am thinking $\sum a_i(1-a_{i+1})$ to count the number of "ends" of events. Obviously I can deal with the edge case as well. Unfortunately, this results in a product of binary variables. I know that I can represent this with a helper variable, and just sum over that, but I was wondering if there was any more efficient ways.

Question 2: This question is more important, since my whole model revolves around this. An event will only affect the input elements after the end of the event. Think of events as duplications. If some range $(i,j)$ is duplicated, all elements after $j$ would shift to the right by $j-i+1$ slots. Following this idea of events being duplications, consider the input below:

$a,b,c,d,e$ and the desired sequence $a,b,a,b,c,d,e,d,e$. We can achieve this by duplicating $a,b$ and $d,e$ i.e. $a'=[1,1,0,1,1]$. Notice how positions $0$ and $1$ did not shift at all, positions $2,3,4,5,6$ were originally $0,1,2,3,4$, and positions $7$ and $8$ were originally $3$ and $4$.

Essentially, for every position $i$ in the resulting sequence, I would like to be able to determine which position $j$ it came from in the original sequence. Consider position $6$ in the resulting sequence, we can clearly see it came from position $4$. We notice that this shift of $2$. Similarly, position $5$ came from position $3$. A pattern unfolds such that the shift of position $i$ is always equal to the $\sum_{j<k} a'_j$ where $k$ is the largest index such that $k\leq i \land a_k=0$. This is the same as saying that we are taking the sum of all values of $a'$ up to the most recent $0$ before or at $i$ in $a'$.

How can I model such shifting in an ILP? I.e. given $a’$, how can I create a variable $h$ in the ILP such that $h_{r, l}=1$ iff $\sum_{j<k} a'_j= l$ where $k$ is the largest index such that $k\leq r \land a_k=0$.


texts: How does cpu fetch active program data (using virtual address) from storage when there is a page fault?

texts: I read that cpu generates virtual address and using the same mmu translates to physical address and then fetches the data from RAM. But when there is a page fault, the data is fetched from the HDD(or Secondary Storage) where the program resides. But how does the cpu knows exact location of the program on storage device. Does it maps the virtual address to the address of storage device? If yes, how does it do ?


texts: MST: Is there such an example of a graph with unique mst and not unique light edge?

texts:
The problem is the following:

Give an example of a graph that has a unique minimum spanning tree but for every cut of the graph, there is not a unique light edge crossing the cut.

I am trying to find such a graph, but I have not find any example. Is it possible to have such a graph? If not, why?


texts: regular expression: sum of positive fixed point decimal numbers

texts:
I need help with this exercise.

Indicate the regular expression for the following Languages. Explain your  expression in one sentence and indicate the basis form of the alphabet. Indicate also every assumption you make.

i) Sums of positive fixed-point decimal numbers. The following Strings should exist in the Language:

e.g: 3.14 or also 3 + 4.2 + 7 + 1

I have a couple more exersices that are pretty similar but I guess if I get to understand this exercise I could try to do the others faster.

I appreciate the help in advance.


texts:
TAPL (page 549) proposes the following lemma in order to prove soundness of System F type system:

Substitution lemma for types:

$E, X, \Delta \vdash t: T \implies E, [X \mapsto S] \Delta \vdash [X \mapsto S]t: [X \mapsto S]T$

Proof of the T-TApp case:

$ E,X,\Delta \vdash t[A]: [Y \mapsto A]T $

and by rule T-TApp we have:

$ E,X,\Delta \vdash t: \lambda Y . T $

so by induction hypothesis:

$E, [X \mapsto S] \Delta \vdash [X \mapsto S]t: \lambda Y. [X \mapsto S]T$

so applying the T-TApp rule we have:

$E, [X \mapsto S] \Delta \vdash [X \mapsto S]t[A]: [Y \mapsto A][X \mapsto S]T$

however I should need $[Y \mapsto A][X \mapsto S]T = [X \mapsto S][Y \mapsto A]T$

I think I can assume that $A,S$ cannot contain $Y$.

However, what if $A$ contains $X$? Then these types do not coincide.

Assume $T$ contains $Y$. Then the lhs type leaves $X$'s in the result while the rhs type does not leave any.

Other sources

You can find an sketched proof in the proof of lemma 17, page 86 of the following lecture notes. But this case appears to be immediate.