texts: What is Big O of a loop with square root inside?

texts:
Knowing that O(n^2) > O(nlogn) > O(n) > O(sqrt(n)) > O(logn) > O(1) and having below python code:
import math

def f1(n=9):
    return math.sqrt(n)

def f2(n=10):
    return [math.sqrt(i) for i in range(n)]

Am I correct to infer that O(f1(n)) = O(1)
Am I correct to infer that O(f1(n)) = O(n)


texts: Understanding the one-writer, many-readers problem?

texts:
I need some help understanding the implementation of the one-writer many-readers problem shown below as I am new to this concept:

I have a rough idea that there will be starvation/deadlock among the readers as there is one writer that multiple readers are trying to access at once. Can anyone please provide some further insight regarding the problems with the implementation of this situation?

I am not looking for any coding, that was just the sample code (pseudocode) I am working with. I am looking for the problem of the implementation. Upon further research I have assumed the following (based on the line: if readcount == 1 then semWait(wrt); :

There is one writer and many readers
The readers have priority over the writers
The possible problem: The writers cannot write until the reader has finished reading therefore starvation occurs

However upon re-evaluation of the code I have also assumed the following based on the lines:

semWait(mutex);
readcount := readcount - 1;
if readcount == 0 then up
semSignal(mutex);

Could I not also say that only one reader may read at a time therefore the other readers will be starved?

Therefore would either of these be the correct way of interpreting the coding to the problem is of the implementation or would I be wrong?


texts: The "CPS" approach has done great harm to performance in SML/NJ; reasoning desired

texts:
In a comment to Learning F#: What books using other programming languages can be translated to F# to learn functional concepts? Makarius stated:

  Note that the "CPS" approach has done great harm to performance in
  SML/NJ. Its physical evaluation model violates too many assumptions
  that are built into the hardware. If you take big symbolic
  applications of SML like Isabelle/HOL, SML/NJ with CPS comes out
  approx. 100 times slower than Poly/ML with its conventional stack.

Can someone explain the reasons for this? (Preferably with some examples) Is there an impedance mismatch here?


texts:
I need to give a talk about expander codes at university (I'm a student of computer science). Since they have been introduced to show a family of codes looking good when thinking of the Shannon theorem, I wonder what real world application for expander codes exist.

As far as I know one has a real hard time when encoding but decoding is quite fast. Why aren't they used to encode write only media or similar? What is their big disadvantage?


texts: Proving $\{ a^n b^m \mid n \leq m^2 \}$ is not context-free using pumping lemma

texts:
I am working on a pumping lemma question and trying to prove that the following is not context-free, but I can't finish the proof.
The language is
$$L =  \{ a^n b^m \mid n \leq m^2 \}$$
Assume Demon picks $p$ and I choose $s = a^{p^2}b^p$ and $s = uvwxy$ such that $p \geq |vwx|$.
The first case is $vwx = b^j$. If we choose $i = 0$ everything is ok and the relationship isn't right.
The second case is $vwx = a^j$. If we choose $i = 2$ every thing is ok.
I get stuck when  $vwx = a^j b^k$. How can I finish the proof in this case?
Did I choose the right string? I repeated them for $s =  a^{p}b^p$ but it didn't work.


texts: Why does a Turing machine recognise exactly one language?

texts: I am trying to understand the existence of non-recognisable languages. To get this, I need to know why a Turing machine recognises only one language, not multiple. Why is this?


texts: Work-stealing: where and how many to steal

texts: If one ignores the conflicts when accessing the dequeue in Work-Stealing algorithms, does it matter (and in what ways) if one steals from the top or bottom (or anywhere randomly) of the dequeue? Does it matter (and in what ways) if one steals one or more items ?


texts:
Currently I have to learn Coq and don't know how to deal with an or :

As an example, as simple as it is, I don't see how to prove:

Theorem T0: x \/ ~x.

I would really appreciate it, if someone could help me.

For reference I use this cheat sheet.

Also an example of a proof I have in mind: Here for double negation:

Require Import Classical_Prop.

Parameters x: Prop.

Theorem T7: (~~x) -> x.
intro H.
apply NNPP.
exact H.
Qed.


texts:
I'm doing a self-study of Game Theory Evolving by Gintis, and am stuck on problem 4.16 "Poker with Bluffing".

The first question asks "Show that Ollie has 64 pure strategies and Stan has 8 pure strategies.". But no matter how I try to approach this, I can't get more then 4 strategies for Stan!

Here is the game tree for the game in question:

The question marks (?) in the figure mean that the payoff depends on who has the higher card.

Here is the game description:

Two players, each with a deck of three cards: H (high), M(medium) or L (low).
Each puts \$1 in the pot, chooses random card
Ollie (P1) either stays or raises
Stan (P2) simultaneously also stays or raises
If both raise/stay - highest card wins the pot (tie - they take their money back)
If Ollie raises, Stan stays  Ollie gets the \$3 pot.
If Stan raises and Ollie stays - Ollie gets another chance:
-> Drop - Stand wins the \$3 pot
-> Call - add \$1 to the pot.

Why does Stand have 8 pure strategies?


texts:
I am just learning backpropagation algorithm for NN and currently I am stuck with the right derivative of Binary Cross Entropy as loss function.
Here it is:
def binary_crossentropy(y, y_out):
    return -1 * (y * np.log(y_out) + (1-y)*np.log(1-y_out))

def binary_crossentropy_dev(y, y_out):
    return binary_crossentropy(y, y_out) * (1 - binary_crossentropy(y, y_out))

def binary_crossentropy_dev2(y, y_out):
    return (y_out - y)/ (y_out * (1-y_out))

But when comparing both derivative above with real numbers, their results are differenct altough they should be the same.
What am I doing wrong with the above equations?
Thank you!


texts: What is the index of the leftest child of node in a k-nery heap?

texts:
Suppose the root node‘s index is 1, what is the index of the leftest child of a node e in a k-nery heap? What is the parent‘s index of a node in k-nery heap?

All questions regarding my problem I found talk about binary heaps, I just can’t think of a simple solution.


texts: Why $o(\log n)$ bits instead of $O(\log n)$ bits needed for succinct data structure?

texts:
Succinct data structure = succinct representation of data + bits for indexing. Link

Let $S$ be  subset of  of $\{1,2,\ldots,n\}$ then $\lceil \log (2^n) \rceil + o(\log n )$ bits are needed in succinct representation. The $o(\log n)$ bits needed for the indexing of the succinct data structure. I have a doubt, why $o(\log n)$ not $O(\log n)$ bits? Where $O(\log n)$ do not play any role when talking about conventional representation of data.


texts: What different lines of reasoning and traditions lead to the conclusion that Software Engineering is or isn't part of Computer Science?

texts:
Background: Some people consider Software Engineering as a branch of Computer Science, while others consider that they are, or should be, separate. The former stance seems to be well presented in written works. On Wikipedia, Software Engineering is classified as Applied Computer Science, along with, e.g., Artificial Intelligence and Cryptography. The ACM Computing Classification system places SE under Software, along with, e.g., Programming Languages and Operating Systems. CSAB has also considered SE as part of Computer Science, and considered that

  [...] it includes theoretical studies, experimental methods, and engineering design all in one discipline. [...] It is this close interaction of the theoretical and design aspects of the field that binds them together into a single discipline.
  [...]
  Clearly, the computer scientist must not only have sufficient training in the computer science areas to be able to accomplish such tasks, but must also have a firm understanding in areas of mathematics and science, as well as a broad education in liberal studies to provide a basis for understanding the societal implications of the work being performed.

While the above seems to reflect my own view, there is also the stance that the term Computer Science should be reserved for what is sometimes called Theoretical Computer Science, such as Computability Theory, Computational Complexity Theory, Algorithms and Data Structures, and that other areas should be split off into their own disciplines. In the introductory courses I took for my CS degree, the core of CS was defined via the questions "what can be automated?" (Computability Theory) and "what can be automated efficiently?" (Computational Complexity Theory). The "how" was then explored at length in the remaining courses, but one could well consider SE being so far from these core questions that it shouldn't be considered part of CS.

Even here on CS.SE, there has been debate about whether SE questions are on-topic, reflecting the problematic relationship between CS and SE.

Question: I'm wondering what lines of reasoning and traditions within Computer Science might lead to one conclusion or the other: that SE is, or should be, part of CS or that it is not. (This implies that answers should present both sides.)


texts: Need help with previous "Automata / Theory Of Computation" exam question

texts:
I passed by this question in a previous exam while studying for the "Automata / Theory Of Computation" and I am struggling to find answer. I would appreciate it if someone can help me with it:

This is the question:

a)On the basis of what was covered in class, draw the Venn diagram representing the following sets:

1.REXP: the set of the language given by all regular expressions

2.DFSA: the set of all languages recognized by deterministic FSAs

3.NFSA: the set of all languages recognized by non-deterministic FSAs

4.CFG: the set of all languages generated by context free grammars

5.PDA: the set of all languages recognized by PDAs


texts: Shortest subsequence containing all elements

texts:
Given a sequence $a_1,\ldots,a_n$, find the shortest subsequence $a_i,\ldots,a_j$ such that $\{a_1,\ldots,a_n\} = \{a_i,\ldots,a_j\}$.

I came up with three solutions:
The most straightforward brute-force solution is $O(n^3)$.
We can optimizing brute-force solution, performing a binary search on subsequence length in the outermost loop in $O(n^2 \log n)$.
We can re-use idea from longest common subsequence problem by putting tree-based sets in the table (let's say, elements are comparable with $<$) with copy-on-write implementation. This would be $O(n^2 \log m)$, where $m$ is the number of different elements.
Could it be done better? Maybe, something like Z-functions for all different values in $O(nm)$?


texts:
If I have to check a Left Recursive grammer for LL(1)  then should I check it after removing left recursion?

For example:-
S-> (L)|a
L->L.S|S

If I check after removing Left Recursion then the above grammer is LL(1).
But if I do not remove left recursion then above grammer is not LL(1).
which one is the right answer?


texts:
I read that the 4 conditions for deadlock prevention are necessary conditions and not sufficient.

The four necessary conditions are :-

Mutual exclusion.
Hold and wait.
No preemption.
Circular wait.

Here it is clearly mentioned that these conditions are only necessary but not sufficient.
https://cs.nyu.edu/courses/spring03/V22.0202-002/lecture-06.html

Can someone please tell me why are they not sufficient? I am not able to come up with an example where all the conditions satisfy but deadlock doesn't occur.


texts: Is there an optimization problem on planar graphs which is APX-hard ?

texts:
I'm looking for a optimization problem on planar graphs which is APX-hard, which means that it doesn't admit a PTAS (approximation scheme). It would be even better is the difficulty of the problem does not depend on some weight value but only on the structure of the graph (because in this case it's probably possible to find such an inapproximability result).

For instance, the following problems all admits a PTAS on planar graphs :
- Maximum independent set
- Steiner Tree
- (Connected) dominating set
- Vertex cover
- Travelling salesman
- k-center/ k-medians
- ...

By the way, there are a lot of technique to find PTAS on planar graphs, such as Baker's technique and Arora's technique.


texts: How to show that cross entropy is minimized?

texts:
This Question is taken from the book Neural Networks and DeepLearning by Michael Nielsen

The Question:
In a single-neuron ,It is argued that the cross-entropy is small if σ(z)≈y for all training inputs. The argument relied on y being equal to either 0 or 1. This is usually true in classification problems, but for other problems (e.g., regression problems) y can sometimes take values intermediate between 0 and 1. Show that the cross-entropy is still minimized when σ(z)=y for all training inputs. When this is the case the cross-entropy has the value:

C is the cost function

σ is the sigmoid function

y is the expected output of the network

I am not sure if I understand the question correctly.If σ(z)=y wouldn't the partial derivative of C with respect to the weights(or Bias) be equal to zero?This will imply that the weight is already at the correct value and the cost function cannot be reduced any further by changing the weight.

z is the weighted input to the neuron.(z=wx+b)

Where b is the bias and x is the activation of a neuron in the previous layer.(In this case it is the input to the network itself)

w is the weight value


texts:
If $\mathcal C=\mathcal D$ then does $\mathcal A^\mathcal C=\mathcal A^\mathcal D$ hold ($\mathcal C^A=\mathcal D^A$ need not hold)? The class $\mathcal A$ could query same for $\mathcal C$ and $\mathcal D$ since $\mathcal C=\mathcal D$ as languages. Correct? Is there a counterexample?
If $\mathcal C\subseteq\mathcal D$ then does $\mathcal A^\mathcal C\subseteq\mathcal A^\mathcal D$ hold ($\mathcal C^A\subseteq\mathcal D^A$ need not hold)? The class $\mathcal A$ could query same for $\mathcal C$ and $\mathcal D$ since $\mathcal C$ is in $\mathcal D$ and simulate $\mathcal A^\mathcal C$ with $\mathcal A^\mathcal D$. Correct?


texts: Number of final states in minimal DFA for $a^*b^*+b^*a^*$

texts: How many final states exist in the minimal DFA that accepts the language $a^*b^* + b^*a^*$?


texts: Find all edges of G contained in some MSP

texts:
I have the following question in a homework:

Let $G = (V,E)$ be an undirected graph, and let
$$A = \{ e \in E \mid \text{ s.t. exists an MSP $T$ containing } e\}.$$

We were asked to find $A$ in $O(m \log n)$ time.

Any suggestions?


texts: Reduction from 3 SAT to Monotone Exact 1 in 3 SAT

texts: Can someone please help with a clear reduction from a 3SAT to a Monotone Exact 1 in 3 SAT. I tried searching by didn't find much.


texts: Non-Deterministic Turing machine vs Probabilistic Turing Machine vs Deterministic Turing Machine

texts: What is the difference between a Non-Deterministic Turing machine, Probabilistic Turing Machine and a Deterministic Turing Machine ?


texts: Standard constructive definitions of integers, rationals, and reals?

texts:
Natural numbers are defined inductively as (using Coq syntax as an example)

Inductive nat: Set :=
| O: nat
| S: nat -> nat.

Is there a standard way to define integers (and maybe other sets like rationals and reals) constructively?


texts: String matching for wildcard-based records

texts:
Let's say that we have a string "1.2.3" and want to find a match for it in the following records:

1.2.9
1.4.5
1.*.3

For each record:

The . is a separator that divides the string into segments.
Each segment can have a static value or * that matches any segment value.
There are no duplicated records. If there are multiple matches for a given string, only one is returned, following an exact match and left to right rule. So, for the following hypothetical matches for 1.2.3, the previous has priority over the latter: 1.2.3 > 1.2.* > 1.*.3 > *.2.3.

In the initial example, the matching record will be "1.*.3".

Note: here, the numbers used to represent a record are a simplification of a more complex, unpredictable, variable-sized value, such as abc.wxyz.fghijklm. So it is not possible to build tables for possible wildcard values.

I'm looking for the (theoretically) fastest lookup algorithm to find a matching record in memory given these non-requirements:

Longest prefix matches are not a requirement;
Only lookup speed matters: record insertion or deletion are not required to be fast;
Memory space efficiency is not a requirement.

I experimented a range of trie variants and I am guessing (sorry if this sounds naive) that tries, or any datastructure, can't find a match for the proposed problem without backtracking. I'd appreciate some comments on this.

So, which datastructure would best fit my (non-)criteria?


texts: How do we adjust a model to fit our own dataset?

texts:
Often, I see people using networks like AlexNet, GoogLeNet, etc to train it on their dataset. These networks are trained or pretrained with a specific dataset, and people fine-tune it to their dataset.

However, is this really suitable? What if the custom dataset had a lot more images than the original or is detecting completely different classes?

In which ways could we modify the networks so they would fit our dataset better?

*one example is faster-rcnn, where lots of people have done this


texts: Data Compression :Compress a Compressed File

texts:
Suppose we have file A that has been compressed by the the method B and the output-file is C, now if I am not wrong We can not compress C more by method B, but there might another method=algorithm D that  might compress C more and produce compressed file E.

Is this kind method of using more than one compression-method in each iteration of compression   standard? if there is a paper/survey paper on performance of such kind of compression,  please, comment or post an answer.

I mean, is there any study where 2 or 3 methods were apply to same file,   if there is a paper/survey paper on performance of such kind of compression, please, comment or post an answer.


texts: "For small values of n, O(n) can be treated as if it's O(1)"

texts:
I've heard several times that for sufficiently small values of n, O(n) can be thought about/treated as if it's O(1).
Example:

The motivation for doing so is based on the incorrect idea that O(1)
is always better than O(lg n), is always better than O(n). The
asymptotic order of an operation is only relevant if under realistic
conditions the size of the problem actually becomes large. If n stays
small then every problem is O(1)!

What is sufficiently small? 10? 100? 1,000? At what point do you say "we can't treat this like a free operation anymore"? Is there a rule of thumb?
This seems like it could be domain- or case-specific, but are there any general rules of thumb about how to think about this?


texts: Finding language family of given language

texts:
I came across following problem:

  Let $L_1$ and $L_2$ are two languages and both of them are accepted by DPDA. If $L=L_1-L_2$ is any language, then what is the smallest language family $L'$ belongs to?

I know DCFLs are not closed under set difference operation. Neither do CFL are closed. However CSLs are closed under set difference operation. So $L$ must be CSL. CSLs are also closed under complementations. Thus, $L'$ must be CSL. But when checked the solution, it gave $L'$ must be recursive. The reason given was:

  If CFL $\cap$ CFL is accepted in time complexity $\leq O(2^n)$,then $L'$ will be CSL. If it is accepted in time complexity $>O(2^n)$, then it will be recursive.

However I dont really get what does this means. I have never used time complexity logic to decide which language family given language belongs to. Can someone explain? Also if that does means something, isnt it wrong to say CSLs are closed under intersection and complementation? Why we have to disregard CSL bound can call them recursive?


texts: Question is about a paper "A Block-sorting Lossless Data Compression Algorithm" by M. Burrows and D.J. Wheeler

texts:
In the paper A Block-sorting Lossless Data Compression Algorithm by M. Burrows and D.J. Wheeler Link.
On page number 5. please describe this line

  If the original string $S$ is of the form $Z^p$ for some substring $Z$ and some $p > 1$, then the sequence $T^i[I]$ for $i = 0,...., N - 1$ will also be of the form $Z'^p$ for some subsequence $Z'$.


texts: Simplifying a logic function using Boolean algebra

texts: Consider this Logic function : D = A B C + A B’ C + A’ B’ C + A B C’ + A’ B C’ + A B’ C’ I am trying to simplify it using Boolean algebra , I am stuck in this step : D= AB +B'C+ A’ B C’ + A B’ C’ So how do I continue simplifying it ?


texts: Update and find-smallest-absolute-value operations on a tree

texts:
I have a balanced binary tree that stores a number in each node, initially zero.  I want to build a data structure that will support the following two operations:

Given a vertex $v$ in the tree and a real value $w$, add $w$ to all nodes in the subtree under $v$.
Given a vertex $v$ in the tree, find the smallest absolute value associated with any node in the subtree of $v$.

The shape of the tree is static and remains unchanged. No new vertices can be added.  We don't need to support any other operations (e.g., insert a node, delete a node, lookup the value in a node).

I want the running time of both operations to be $O(\lg n)$, where $n$ is the number of nodes in the tree.  How can I do that?  Recursively visiting all nodes in the subtree would be too slow, as it would take $O(n)$ time.


texts: Why does the Java grammar have a StatementExpression that resolves to just Expression? Why have this and other redundant rules in the grammar?

texts:
I'm looking at the following grammar rules for the Java language described on the Oracle docs:
Statement:
    ...
    if ParExpression Statement [else Statement]
    StatementExpression ;
    ...

StatementExpression:
    Expression

ParExpression:
    ( Expression )

I don't understand why the StatementExpression rule is present at all. I also don't understand why ParExpression had to be written as a separate rule.
Why couldn't the grammar just look like the following?
Statement:
    ...
    if ( Expression ) Statement [else Statement]
    Expression ;
    ...


texts: Proper TSP implementation by brute force

texts:
I need to implement TSP algorithm by brute force for learning purposes.

I've understood there's a set of cities, let's call it V and it's possible to get a matrix representation for the costs for going from a v1 city to a v2 city. I'll assume there are not cycles, so  it's no possible to going from v1 back to v1

Then, I should generate a matrix after these sum series:

However, I really can't see in a practice way how a matrix would be outputed from restrictions.

Let's say we got 3 cities:

  Madrid, Berlin and Malmo

So the path costs are (and they're not forced to be the same for ways back):

From Madrid to:

Berlin: 12
Malmo:  20

From Berlin to

Madrid: 32
Malmo:  12

From Malmo to:

Madrid: 14
Berlin: 17

So my input is:

$$\begin{bmatrix} 0 & 12 & 20 \\ 32 & 0 & 12 \\ 14 & 17 & 0\end{bmatrix}$$

How should the matrix be outputed according to the sum series?

  I assume the algorithm would need to generate a matrix from this exampple:

There are 3 cities x1, x2 and x3 and got the costs matrix shown below:

$$\begin{bmatrix} 10 & 2 & 1 \\ 3 & 10 & 2 \\ 11 & 2 & 10\end{bmatrix}$$

Following, example shows the next matrix:

$$\begin{bmatrix} x_{11}+x_{12}+x_{13} &  &  \\  & x_{21}+x_{22}+x_{23} &  \\  &  & x_{31}+x_{32}+x_{33}\\x_{11} & x_{21} & x_{31} \\ x_{12} & x_{22} & x_{32} \\  x_{13}& x_{23} & x_{33} \end{bmatrix}$$

Which would be the same as:

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

Then, considering the power ser of the three cities, matrix got the following rows added:

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

Finally, the whole generated matrix is:

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


texts: Can we always reduce the weights of a weighted graph to rationals and preserve equality relationships?

texts:
Let $G = (Q, \Delta, W)$ be a finite weighted graph with $\Delta: Q \times Q$ and $W: Q \times Q \to \mathbb{R}^{+}$. Is it the case that there always exist a function $W': Q \times Q \to \mathbb{Q}^{+}$ such that $\forall S, S' \subseteq Q, \forall s, s' \in S$:

$$
\sum_{s'' \in S'}{W(s, s'')} = \sum_{s'' \in S'}{W(s', s'')} \Leftrightarrow \sum_{s'' \in S'}{W'(s, s'')} = \sum_{s'' \in S'}{W'(s', s'')}
$$

?

I believe, at least for the finite case, this should be possible and I'm trying to prove this "constructively" by finding $W'$.

So let $\epsilon \in \mathbb{Q}^{+}$ be a rational such that $\forall s_0,s_1,s_2,s_3 \in Q, \epsilon < |W(s_0, s_1) - W(s_2, s_3)|$ whenever that difference isn't $0$.

Obviously if we just round every non-rational weight in a grid with spacing $\epsilon$ we will not preserve equalities and I believe it'll be quite difficult to restore the exact relations.

So my idea is to round one weight at a time, and then fix the equalities that get broken by modifying only non-rational weights and repeating the process until there are only rational weights.

So start by taking two subsets $S, S' \subseteq Q$ and take $s \in S$ and $s'' \in S'$ such that $W(s, s'') \notin \mathbb{Q}$.
Now we can round this number to the nearest rational of the form $k\cdot \epsilon$.

Let $e = W(s, s'') - W'(s, s'')$ is the error we introduced.
Now if there was an $s' \in S$ and an $s'''$ such that $W(s', s''') = W(s, s'')$ then we modify that weight in the same manner, and thus the iff condition still holds for $s$ and $s'$.

Otherwise for $s' \in S$ we must have that some (more than one) weight $W(s', s''') \notin \mathbb{Q}$ and we can subtract $e$ from it and preserve the condition for $s$ and $s'$ with respect to $S$ and $S'$.

However we have now changed some other weight, and thus while we may have preserved the equality between $S$ and $S'$, we may have broken it for other subsets. So we have to consider every subset that is either a subset or superset of $S$ and $S'$, verify if we have broken that iff condition, and if so we must find an other weight and change it, and repeat the process until it we find an equilibrium. But does this actually happen?

My question is:

Does there exist such $W'$ or am I trying to build a non-existent function?
If $W'$ exists, is the above approach feasible in some way, or should I completely change strategy in order to find $W'$? Do you know any particular trick that can help in devising $W'$?


texts:
I have a background in computer architecture and only cursory understanding of process networks. For a paper I am writing I need to understand prefix monotonicity properly.

For now I have "a stream transformer is prefix monotonic if its output for a given input record r is dependent only on the input stream up to and including r, and independent from whether r is the last record in the stream". But this was gathered by word-of-mouth and I am not sure it is the proper approach.

I would welcome suggestions for:

proper formal background and definitions;
useful analogies to explain the concept to a newcomer (the audience of the paper needs to understand prefix monotonicity but may not be knowledgeable with TCS).


texts: How to compare two approximation algorithms

texts:
We say that "An algorithm is a $\beta$-approximation to problem $X$, if for any instance of problem $X$, the solution returned by this algorithm is within a factor $\beta$ of the optimal solution".

Now assume that we have a $\log(N)$-approximation algorithm (called it Alg 1) for problem $X$ where $N$ is the size of problem $X$. Further assume there is one other algorithm (called it Alg 2) for problem $X$, but for that algorithm we could find an instance of problem $X$ with size $N$ such that the solution returned by Alg 2 is $N/2$ times of the optimal solution.

What is a correct way of saying this statement that clearly shows that Alg 1 is much more better than Alg 2? I was thinking about the following one:

"Alg 2 provides a $\beta$-approximation to problem $X$ where $\beta \geq N/2$."

Is this correct? Any better suggestion?


texts: Can the subset sum problem work with an undefined set?

texts:
To give a brief outline of my actual problem, I'm attempting to identify possible impurities in proteins. I have a theoretical mass and an experimental mass, and the difference between the two would in theory be caused by any impurities present in the proteins. Impurities could take the form of an amino acid insertion, an amino acid deletion, an amino acid substitution, or an amino acid modification (modifications can both add and subtract mass).

Every impurity can be associated to a known change in mass, so I want to use the subset sum problem to get all subsets of impurities that add up to the delta mass. My issue is that I'm working with an undefined set. I know what impurities I can have, but I don't know how many of each I can have.

Is it possible to get the subset sum problem to work with an undefined set such as this? Is there a better algorithm I could implement to solve the issue?


texts: Using hash tables instead of lists for buckets in hash tables

texts:
Say instead of using a linked list as buckets for a hash table of size $m$, we use another hash table of size $p$ as buckets this time. What would be the average case for this problem?

I looked up perfect hashing and I got a very close algorithm, and it is $O(1)$. Can someone please clarify?


texts:
I'm looking for a way to find out whether a specific rule in a BNF grammar can be converted to a regular expression.
(With "regular expression" (RE), I mean the simple mathematical kind. I'm not interested in BNF rules that can only be done with the use of backreferences, lookarounds, or other advanced features.)
I'm only interested in cases where it is possible.
I know that this problem is generally undecidable, so I'm basically looking for tricks to do it anyway. Something semi-decidable would be nice.

My current approach is based on the idea that all non-recursive rules (rules that don't refer to themselves and don't contain rules that refer to themselves) can be easily converted to REs. So "all I have to do" is to rewrite the recursive rules. Simple examples:
S = a | b S
  = b* a

T = a | T b T | T c T
  = a | T (b|c) T
  = a ( (b|c) a )*

However, this approach is limited by my ability to recognize patterns in a BNF AST and to simply said AST. It's a very limited approach so I'm looking for better ways.

Here's an example of what the solution has to be able to handle:
S = a | c | S (b S)* c | S d S | S e S ( e S )*

The language of the above rule is regular. However, showing this is not easy and takes time.
Proof sketch:
S = a | c | S (b S)* c | S d S | S e S ( e S )*
  = a | c | S (b S)* c | S d S | S e S
  = a | c | S (b S)* c | S (d|e) S
  = a | c | S c | S b S (b S)* c | S (d|e) S

For now, let's ignore the S b S (b S)* c alternative:
S' = a|c | S' c | S' (d|e) S'
   = (a|c)c* ( (d|e) (a|c)c* )*

Back to the S b S (b S)* c alternative: It basically says that if the input contains a b, then somewhere after the b, there must a (a|c)c. This is hard to express in RE but is easy to do with an NFA.
Construct 2 NFAs x and y such that x = S' and y = S' (b S')* c. Whenever we are at a final state in x, transition via b to the initial state of y. Whenever we at a final state in y, transition via epsilon to all final states of x. The final NFA will have both the initial and final states of x. The RE of the final NFA is: (a|c) ( c | (d|e)(a|c) | b(a|c) ( (b|d|e)(a|c) )* c )*

Original StackOverflow question.


texts: f(n) = n/100 = Ω(n) . I am new at proving asymptotic notations , especially at big-Ω. That's why I even didnt start the beginning myself.  I tried to prove myself as looking at other proofs and searched on the internet to find same question but I couldnt find. I dont think so this question is a duplicate of another which was asked here. Thanks for helps.


texts: Convert scientific notation decimal number to binary

texts:
I'm given the number:
$$8.881784197001252 \cdot 10^{-16}$$
I know it is $2^{-50}$ but suppose I didn't know. I need to convert it to binary.

One way is to apply the school taught algorithm on the fractional part. That'd be:

$.881784197001252\cdot2=1.763568394 \to 1$

$.763568394 \cdot 2=1.527136788 \to 1$

$.527136788 \cdot 2=1.054273576 \to 1$

$.054273576 \cdot 2= 0.108547152 \to 0$

$.108547152 \cdot 2=0.217094304 \to 0$

$...$

It may go on forever so I'd need to determine when to stop.

I then thought I could write the number as:
$$8881784197001252 \cdot 10^{-31}$$
Now the number is an integer and I can precisely convert it. It's:
$$11111100011011110111110001000000010001011000000100100$$
The problem is that I don't know how to convert the base and its exponent from base 10 to base 2. I can approximate it after some attempts. It should be between $2^{-100}$ and $2^{-99}$.

So what I'm asking is: what is the correct approach to convert that number? And, if different from the former, what method does the computer use?


texts:
I am learning the basics of data classification using competitive learning, and am somewhat confused regarding the way this is implemented.

I understand at the start an amount N of prototypes is randomly positioned in the input space. (Ie: weights of output neurons are randomly generated). Subsequently training the data over unlabeled sample input data and changing weight connections shifts each prototype towards the center of a cluster, such data data is more and more accurately labelled.

My question is: How do I know how many classes I want my data to be clustered in? Wouldn't this mean knowing the number of clusters/classes in advance? Are there any techniques to estimate this?

I looked at the leader-follower algorithm, which adds neurons whenever the closest neuron is still more distant than a threshold X. Would this solve the problem?


texts: Knowing the frequencies of each symbol, is it possible to determine the maximum height of the tree without applying the Huffman algorithm? Is there a formula that gives this tree height?


texts:
Given $n$ boolean variables $x_1,\ldots,x_n$ each of which is assigned a positive cost $c_1,\ldots,c_n\in\mathbb{Z}_{>0}$ and a boolean function $f$ on these variables given in the form
$$f(x_1,\ldots,x_n)=\bigwedge_{i=1}^k\bigoplus_{j=1}^{l_i}x_{r_{ij}}$$
($\oplus$ denoting XOR) with $k\in\mathbb{Z}_{>0}$, integers $1\leq l_i\leq n$ and $1\leq r_{i1}<\cdots<r_{il_i}\leq n$ for all $i=1,\ldots,k$, $j=1,\ldots,l_i$, the problem is to find an assignment of minimum cost for $x_1,\ldots,x_n$ that satisfies $f$, if such an assignment exists. The cost of an assignment is simply given by
$$\sum_{\substack{i\in\{1,\ldots,n\}\\x_i\,\text{true}}}c_i.$$
Is this problem NP-hard, that is to say, is the accompanying decision problem "Is there a satisfying assignment of cost at most some value $K$" NP-hard?

Now, the standard XOR-SAT problem is in P, for it maps directly to the question of solvability of a system of linear equations over $\mathbb{F}_2$ (see, e. g., https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#XOR-satisfiability). The result of this solution (if it exists) is an affine subspace of $\mathbb{F}_2^n$. The problem is thus reduced to pick the element corresponding with minimal cost from that subspace. Alas, that subspace may be quite large, and indeed, rewriting $f$ in binary $k\times n$-matrix form, with a $1$ for each $x_{r_{ij}}$ at the $i$-th row and the $r_{ij}$-th column, and zero otherwise, we get a cost minimization problem subject to
$$Ax=1,$$
where $A$ is said matrix, $x$ is the column vector consisting of the $x_1,\ldots,x_n$ and $1$ is the all-1-vector. This is an instance of a binary linear programming problem, which are known to be NP-hard in general. So the question is, is it NP-hard in this particular instance as well?


texts: Approximate the order of summation of two vectors

texts:
Assume we are given two vectors $A,B$ that each contains $c$ numbers: $A=[a_i>0]_{1 \times c}$. We want to see the weighted summation of which one is larger. In other words, given two vectors $A$ and $B$:

$$ws(A) = \sum_{1 \leq i \leq c}{i.a_i}, ~~~~ws(B) = \sum_{1 \leq i \leq c}{i.b_i}$$

we want to know $ws(A)>ws(B)?$

For making the problem simpler, I add another condition to the problem:

$$\sum_{1 \leq i \leq c}{a_i} = \sum_{1 \leq i \leq c}{b_i}$$

Now, is there any way to approximately claim which one of these vectors is larger without running the summation (We may consider the summation of a small number of elements and decide based on that)?


texts: How to prove these two distributions are statistically/computationally indistinguishable

texts:
First we generate a key,
$$k \leftarrow \{\, 0,1 \,\}^{n}$$
And we construct two PPT algorithms $A$ and $B$ as follow:

$$A_{k}\left( \cdot \right) \colon y_{A} \leftarrow k, \text{ return } y_{A}$$
and
$$B_{k}\left( \cdot \right): y_{B} \leftarrow \{\, 0,1 \,\}^{n}, \text{ return } y_{B}$$

For fixed $k$, let $D_{A}$ be the distribution of $A$, and $D_{B}$ be the distribution of $B$. I want to know whether $D_{A}$ and $D_{B}$ are statistically indistinguishable or computationally indistinguishable.

In my opinion, $D_{A}$ is a one-point distribution and $D_{B}$ is a uniform distribution. Thus they are not statistically indistinguishable.

Let
$$A^{\prime}\left( \cdot \right) \colon k \leftarrow \{\, 0,1 \,\}^{n}, y_{A^{\prime}} \leftarrow A_{k}\left( \cdot \right), \text{ return }  y_{A^{\prime}}$$
and
$$B^{\prime}\left( \cdot \right) \colon  k \leftarrow \{\, 0,1 \,\}^{n}, y_{B^{\prime}}, \leftarrow B_{k}\left( \cdot \right), \text{ return } y_{B^{\prime}}$$
then $D_{A^{\prime}}$ and $D_{B^{\prime}}$ are statistically indistinguishable, thus they are also computationally indistinguishable.

Is my method correct? It looks strange and it seems that $k$ is not fixed when I show that they are computationally indistinguishable. Is there a better method from a clear view about the computationally indistinguishable and statistically indistinguishable?

Thanks for @D.W.♦'s answer, if $k$ is fixed, then $k$ is not a random variable anymore. Thus, there are 4 kinds of distributions.

Type (1)

  For $k \leftarrow \{\, 0,1 \,\}^{n}$, $A_{k}$ and $B_{k}$ (given the knowledge of $k$) are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that
  $$\left\vert \Pr \left[  k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left(k, A_{k} \left( \cdot \right) \right) = 1 \right] - \Pr \left[ k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left(k, B_{k} \left( \cdot \right) \right) = 1 \right] \right\vert < \varepsilon(n) $$

Type (2)

  For $k \leftarrow \{\, 0,1 \,\}^{n}$, $A_{k}$ and $B_{k}$ are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that
  $$\left\vert \Pr \left[  k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left( A_{k} \left( \cdot \right) \right) = 1 \right] - \Pr \left[ k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left( B_{k} \left( \cdot \right) \right) = 1 \right] \right\vert < \varepsilon (n) $$

Type (3)

  For $k \in \{\, 0,1 \,\}^{n}$, $A_{k}$ and $B_{k}$ (given the knowledge of $k$) are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that
  $$\left\vert \Pr \left[ \mathcal{A} \left(k, A_{k} \left( \cdot \right) \right) = 1 \right] - \Pr \left[ \mathcal{A} \left(k, B_{k} \left( \cdot \right) \right) = 1 \right] \right\vert < \varepsilon(n) $$

Type (4)

  For $k \in \{\, 0,1 \,\}^{n}$, $A_{k}$ and $B_{k}$ are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that
  $$\left\vert \Pr \left[ \mathcal{A} \left( A_{k} \left( \cdot \right) \right) = 1 \right] - \Pr \left[ \mathcal{A} \left( B_{k} \left( \cdot \right) \right) = 1 \right] \right\vert < \varepsilon (n) $$

To make it clear, I just want to know (4) holds true or not. And my original method confuses the definition between (2) and (4).

I think it may be helpful after we analyse the relation among these 4 types.

Obviously, "(1) holds true" $\Leftrightarrow$ "(3) holds true", since for all the PPT $\mathcal{A}$,
$$\Pr \left[ \mathcal{A} \left(k, A_{k} \left( \cdot \right) \right) = 1 \right] = \Pr \left[  k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left(k, A_{k} \left( \cdot \right) \right) = 1 \right]$$

And "(1) holds true" $\Rightarrow$ "(2) holds true" is also easy to prove.

However I still cannot find a clear proof about the relation between (3) and (4).


texts: Computational Complexity of Not All Equal SAT variant

texts:
Not All Equal SAT is an NP Complete problem. Let us now consider another variant of the problem.

Given a Not All Equal SAT (NAESAT) problem (arbitrary number of literals allowed per clause) with an additional constraint that each pair of clauses share at least 1 literal (not variables but literals).

Is this problem still NP-hard? It seems so, but I am unsure about the reduction.


texts: Justification for neglecting constant factors in Big O

texts: Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing is varying 3 times more rapidly than other! Why do we neglect this fact?


texts:
Unfortunately my background in computational complexity is still weak, but I am working on it.

As I understand, the question of existence of one-way functions is very important in the field.

Assume there are one way-functions, how it can be shown that there exist one-way functions which are length preserving?


texts: Difference between row-polymorpism and bounded polymorpishm?

texts:
I recently came across this blog post by Brian McKenna explaining row polymorphism. This seemed like a wonderful idea to me, but then I realized it smells an awful lot like bounded parametric polymorphism:

With row-polymorphism:

sum: {x: int, y: int | rho} -> int
function sum r = r.x + r.y

With bounded parametric polymorphism:

sum: forall a <: {x: int, y: int}. a -> int
function sum r = r.x + r.y

Can someone clarify the differences to polymorphism between these two approaches?


texts: How fast can we identifiy almost-duplicates in a list of strings?

texts:
I'm having trouble figuring out the upper bound running time for this scenario:

Input:

$N$ number of strings
$M$ upper bound of string length
$T$ threshold for edit distance (2 strings with a Damerau-Levenshtein edit distance lower than $T$ are considered "duplicate")

Expected values

$N \approx 1,000,000$

$M \approx 200$

$T \leq 2$

The algorithm should do the following:

For each string in the list, find any other items in that list that have an edit distance smaller than some threshold, and mark them as "duplicate" (e.g. add them to some other list that tracks duplicates)

I'm having trouble calculating the upper bound for the optimal solution

What is the most optimal upper bound for such an algorithm?

I guess first I need to understand what is the best algorithm for the edit distance itself (is it $O(M \cdot N)$?) then it's simply $N^2$ times that, right? so it is surely "slower" than $N^2$ but my question is how slower?


texts: Shortest Non-Subsequence String With Constant-Size Alphabet

texts:
Let $S[1..n] \in \Sigma^*$ be a string of $n$ symbols over the alphabet $\Sigma$ where $|\Sigma| \in \mathcal{O}(1)$. Determine a shortest string which cannot be obtained from $S$ by deleting some (possibly no) symbols.

For instance, we are given $\Sigma = \{ A, C, G, T \}$ and $S = ACGTACGT$. In this case, one valid answer is $CCA$, because it does not occur as a subsequence in $S$ (i.e. cannot be obtained by removing some of the symbols from $S$) and there is no such string of length $2$.

I am looking for an algorithm which takes $\mathcal{O}(n)$ or $\mathcal{O}(n \log n)$ time. It is not sufficient to compute the length of the answer, an example should also be constructed.

Observations and Approaches. The length of the answer does not exceed $\displaystyle \frac{n}{|\Sigma|} + 1$ by pigeonhole principle. This upper bound is attained for $S = ACGTACGT...ACGT$ in the above example. If we are only interested in the length of the answer, the following approach should work. Let $f(i)$ denote the largest $k \in \mathbb{N}$ such that every string of length $k$ is a subsequence of the prefix $S[1..i]$. Our final answer is $f(n) + 1$ and $f$ can be computed by dynamic programming in $\mathcal{O}(n)$ time for $1 \le i \le n$ simply by recurrence

$\displaystyle f(i) = 1 + f\left(\min{(\ell(i, \sigma_1), \ell(i, \sigma_2), \dots, \ell(i, \sigma_{|\Sigma|})) - 1}\right)$

where $\ell(i, \sigma)$ denotes the last occurrence of $\sigma \in \Sigma$ in the prefix $S[1..i]$. Obviously, the function $f$ is increasing, i.e. $f(i + 1) \ge f(i)$ for $1 \le i \le n - 1$. It seems more difficult to construct an example from this information, that is where I am stuck.

Finally note that the problem is a lot easier, if we require the subsequence do be contigous. Since there are only $\mathcal{O}(n^2)$ substrings, but $\mathcal{O}(|\Sigma|^k)$ strings of length $k$ over $\Sigma$, $k$ turns out to be very small and even brute-force will succeed.

Any kind of help is appreciated, thanks in advance.

Original Source: CSES Problem Set (https://cses.fi/problemset/task/1087/).


texts: general question amortized cost and worst case

texts:
lets say a data structure has operations called insert and delete both of which take O(log(n)) worst case. Suppose the amortized cost of insert is O(log(n)) and the amortized cost of delete is O(1).

Now if a sequence that has n delete operations performed on this data structure  that has n elements currently, then what is the worst case? If delete takes O(1) amortized cost does this mean the worst case (not amortized) is O(n) for n delete's ?

I think no because it doesn't seem right but I'm not sure how to explain it


texts: How to implement simulation on two LTSs?

texts:
Does any one know how to implement the simulation relation on two labelled transition systems (LTS)?

I know how to do it for branching bi-simulation. The signature refinement theorem is used for that purpose which has the time complexity of $O(n^3)$ on cyclic LTSs. Is the signature refinement technique useful for simulation also?

Is there any binary relation called branching simulation? Any idea how to implement it?

What I would like to do is to write a program such that:

Input: Given two labelled transition systems with silent steps
Output1: Does one simulates the other one?
Output2: Are they bisimilar?
Output3: Are they branching bisimilar?
Output4: Does one branching simulate the other one?

The following illustrates the definitions of the above relations:

simulate: An LTS ($L_1$) simulates another LTS ($L_2$) if there exists a binary relation $R$ over the states of the two transition systems such that every transition of $L_2$ can be matched by a transition of $L_1$. Note that simulation is not an equivalence relation.
bisimilar: An LTS ($L_1$) and an LTS ($L_2$) are said to be bisimular if there exists a relation $R$ between the states of these transition systems such that both $R$ and $R^{-1}$ are simulations. Note that bisimularity is an equivalence relation.
branching bisimilarity: is same as bisimilarity but transition systems may have silent steps. Those silent steps ($\tau$ actions) that do not change the behavior of the process are eliminated. Note that branching bisimilarity is an equivalence relation.
branching similarity: I actually have never seen the definition of branching similarity in any context, but it should be the same as similarity. However, the transition systems may have the silent steps.

The paper Distributed Branching Bisimulation Reduction of State Spaces by S. Blom and S. Orzan explains an algorithm to reduce the size of an LTS with respect to branching bisimilarity. The signature refinement theorem is used for that purpose. How it works is roughly as follows:

the algorithm starts by constructing a partition (a set of blocks) of states and terminates once the partition is stable. In a stable partition, two states are branching bisimilar if they belong to the same block.

The above algorithm can also be used to verify whether two LTSs are branching bisimilar or bisimilar. How it works is as follows:

Let LTS, $L_3 = L_1 \cup L_2$, then if after branching reduction, using the above algorithm, the initial states of $L_1$ and $L_2$ both belong to the same block then they are branching bisimular. The above algorithm has time complexity $O(n^3)$ and space complexity $O(n^2)$.

Question: How can I do the same with branching simulate and simulate relations?


texts: Longest common sequence matrix giving wrong answer

texts:
I am trying to find longest common sequence for these two strings

SHINCHAN
NOHARAAA

The common sequence is NHA of length 3

But when I am trying to find out this through LCS matrix which I learnt from this link
https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Based on the explanation and this example given there

I built this matrix for my case

But my matrix is reaching to the length 6 while it should reach to length 3 only because that is the longest comment sequence of the two strings I am using.

Could anybody please point out the mistake I am doing?
I can see the problem is happening because of the extra 3 A's at the end of one of the string.


texts: How to simplify sum of products boolean expression?

texts:
I started with this sum of products:

abc’d’ + abc’d + ab’cd’ + a’b’cd’ + a’bc’d + a’bcd + ab’c’d + a’b’c’d

I have been able to simplify to this:

b'c'd + abc' + a'bc + b'cd'

I can't seem to find a way to simplify it anymore. I have tried reading and watching a ton of tutorials but nothing is clicking.

Some things I have tried is finding the common values among the or expressions such c' or b'.

combining c'

c'(b'd + ab) + b'cd' + a'bc

combining b'

b'(c'd + cd') + abc' + a'bc

I get stuck with the simplification of combining b' or c'.

Can anyone provide any guidance as to what I am doing wrong or missing?


texts: Is there a better way to represent an AND of $n$ variables together other than creating $O(n)$ new variables and constraints?


texts: Time complexity of finding subsequences of a string segmented into parts

texts:
Let $S$ be a string of length $N$, consisting of digits 0 to 9.
For convenience, we assume $N$ to be a multiple of 3.

Then, we split $S$ into $N/3$ equal parts, each of length 3.

For each equal part, we count/enumerate all subsequences of all lengths up to 3.

Finally, we total up how many such subsequences are there altogether.

What is the time complexity of the above algorithm? Thanks.

I give a more concrete example in case the above is not clear. Suppose $S=`111211'$, of length 6.

We first split it into 2 parts $`111'$ and $`211'$. For the first part $`111'$, we  count that there are 3 subsequences of $`11'$ (note that subsequences do not have to be consecutive unlike substrings), for the $`211'$, there is 1 subsequence of $`11'$, so in total there are 4 subsequences of $`11'$. We do this for all possible subsequences up to length 3, even for subsequences that do not appear such as $'000'$, we count that it occurs zero times.

I am new to time complexity, but I did try to calculate it myself. For each part of length 3, the time complexity of enumerating the subsequences is $O(1)$? Hence, in total, we have to repeat it $N/3$ times, so the overall time complexity is $O(N)$?
Is that correct? Thanks a lot.


texts: When working on Linux what happens when a thread is created? It is a separate execution flow. Does each thread have their own code section? Personally I don't think threads would be able to share code section even if it's the same section. Say if the number of threads being created is dynamic. How is the memory allocated for each thread? Will the memory foot print, especially code section, increase as threads are created?


texts: Number of complete traversals of the circle in generalised Josephus problem?

texts:
In the generalised Josephus problem, n people stand in a circle and every kth person is eliminated until only one person is left. The last person left standing can be found using dynamic programming (like here).
I want to find out the number of times the circle will be traversed completely (ie the number of times the you will have to go through the entire array).
Note that k can be larger than the size of the circle (if not at the starting, at least after the circle  is sufficiently reduced); in the circle maybe traversed completely before the next elimination.


texts: Check if given vertices form a connected subtree in a graph

texts:
The approach described in this question is wrong. It'll find false positives for disconnected components with multiple vertices. See D.W.'s answer for a reliable alternative.

This might be a simple question, but I can't seem to find a clear cut algorithm for this. I'm given a set of vertices from a graph and I need to determine whether they form a connected subtree in this original graph. I also have the neighbors of each of the vertices and an edge list to work with.

My approach would be to loop over the vertices and check if each one has at least one of the other given vertices as a direct neighbor. If one of them hasn't, it must be disconnected from the rest of the vertices, so the set can't form a connected subtree and we can return false early. So like this:

foreach (vertex in input)
{
   connectedToAny = false;

   foreach(other in input)
   {
          if (vertex.neighbors.contains(other))
          {
                 connectedToAny = true;
                 break;
          }
   }

   if (!connectedToAny)
   {
          return false;
   }
}

return true;

I'm aware this doesn't preclude the existence of cycles, but I'm happy to ignore this for now.

My main question is if this approach is in fact correct, or whether I'm missing cases where this could lead to false positives or negatives.

I'd also be happy to hear if there's a more efficient approach. I have also considered using a more conventional depth first search from any of the input vertices to see if they're connected, but I think I'd have to compute $neighbors \cap input$ at each recursion to specialize from simply connected (possibly via other vertices) to directly connected subtree, right?


texts:
I have a collection of objects, and a feasibility property for sets of objects which is slow to compute. If a set is feasible then so is any subset. For example, it could be whether the set of things will fit into a certain-sized packing crate.

I want to compute all feasible sets (equivalently - all maximal feasible sets), minimizing the number of evaluations of the feasibility property (worst-case or average). Does anyone know of any theoretical work on this?

Bonus question - what if the cost to compute the property is linear (or superlinear) in the size of the set being evaluated?


texts: How do non-deterministic algorithms work on current machines?

texts:
I have some questions regarding the exact nature of non-deterministic algorithms. Is it right that non-deterministic algorithms do not rely on any randomness whatsoever? In which case, this Wikipedia article which mentions Fermat's little theorem includes generating random numbers. I had thought that non-determinism was more of a concept than one that could be put into practice at this given moment - so what exactly are the 'non-deterministic algorithms' on the Internet, such as on the Wiki page above?

Furthermore, D. Harel's book Algorithmics introduces non-determinism in that whenever the machine must make a choice between two or more branches to next states, it ALWAYS picks the one which will lead to an accepting state, if there are any accepting states. In this way, how can non-deterministic algorithms exist on current machines, as they don't have 'insight' as to what will happen further down the line?

Finally, does converting from a non-deterministic FSM to a deterministic FSM take an exponential amount of time? If not, what bearing would this have on the P=NP problem?


texts: Speaker independent voice command recognition

texts:
I am looking for a software, a library or an algorithm that can be trained to recognize about a dozen speaker independent voice commands. The commands will be very distinct phrases of 4-5 words each. They can be chosen to sound very different from each other. Additionally, the commands will be in more than two different languages. The user will be guided to say only the exact phrases and talk slowly, loud and clear in front of the microphone.

I am currently looking for an algorithm that can compare speech spectrograms and give me a matching percentage, but no luck so far. Any ideas?

If it helps, the code can be written for the specific phrases only, and, in worst case, the phrases can be reduced to 3 or 4.


texts: Are there variations of the regular runtimes of the Big-O-Notation?

texts:
There are multiple $O$-Notations, like $O(n)$ or $O(n^2)$ and so on. I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log n^2)$, or if those are mathematically incorrect.

Or would it be a right thing to say that it is possible to improve a $O(5n^2)$ to a $O(3n^2)$? I can't and don't need to figure out runtimes yet and I do not need to improve anything, but I'd need to know if this how you describe your functions in reality.


texts: If $V$, $E$ and $F$ is respectively the number of vertices, edges and faces in a maximally triangulated graph, then why do we have $3F = 2E$?

texts:
Suppose we have a maximally triangulated graph $G$, where $V$, $E$ and $F$ is respectively the number of vertices, edges and faces. The following graph should be a maximally triangulated graph.

Apparently, the equation $3F = 2E$ holds for $G$. Why (intuitively) is this the case?


texts: Is the complement of $ww^R$ context-free?

texts:
Identify the language given by $L = \{ x \in (0,1)^* : x \neq ww^R, w \in (0,1)^*\}$. Note: $w^R$ is the reverse of the string $w$.

Closure property can/should be applied only in the cases when the actual language is not specified. Otherwise, you may arrive at wrong conclusions. The language in question is fully specified, so I doubt whether one can directly apply closure property on $ww^R$, which you say, is its complement or vice versa. The given answer is CFL. But I don't seem to have arrived at it satisfactorily.


texts: FPT: Dominating Set on Planar Graphs (average degree is known)

texts:
I'm given an instance of a planar graph and should construct a FPT algorithm for dominating set. The task looks like this:

Dominating Set on Planar Graphs

Instance: A planar graph G and an
integer k.
Parameter: k.
Question: Does there exist a dominating set
of size at most k in G?
Fact: Every planar graph has average degree at most 6.

Reading through some papers I found this simple algorithm [FEL]. It runs in O( (dmax+1)^k * n) where dmax is the maximum degree.

global bool exists=false

function domSet(B, E, k):
    if |B|<k
        exists=true
    else if k>0
        choose some u from B
        foreach v in (u+N(u)): # N ... neighbour
            domSet(B -(v+N(v)), E-I(v), k-1) # I ... incident edges

function main():
    given G=(V,E) and k
    domSet(V, E, k)

Now to my problem: I have the running time for this algorithm if I know the max. degree, but I'm not succeeding when using the average degree. All in all, the algorithm branches for each neighbour of an inspected vertex. The depth of this tree is at most k. When the degree is upper bounded by dmax, then its easy to calculate the number of vertices of this search tree and therefore the running time. But what about the average degree? How can I find an upper bound for the running time when I just know this average degree?

What I'm trying to express is something like "the search tree might have a high number of branches for some nodes, but there are many others with a low number and we can give an upper bound as f(k)*poly(n)". But I can't find a formal argument for this.

[FEL] http://www.mrfellows.net/papers/C51.pdf (algorithm on page 2)


texts: What makes data flow analysis higher level than control flow analysis?

texts:
I feel understanding why data flow is higher level than control flow is key to writing good code (and convincing others during code reviews). I find this repeatedly when arguing why my functional style programming with immutability is superior to their mutable state code which is more common and expected.

But I don't understand why one is higher level than the other. The closest I can come up with, informally, is that ultimately end users don't care about what movement of control occurred. But they DO care what movement of data took place.

Other examples

applications which just do processing last only a couple of years, whereas files which store data can last decades)
a CPU just transforms volatile data, whereas disks store data persistently

In other words, control flow is a means of achieving data flow.

Is there a more rigorous way to explain this?

(source: slideplayer.com)


texts: $NTime(2^n) \subseteq NSpace(n^k)$ implies $EXP = PSPACE$?

texts:
Assume $NTime(2^n) \subseteq  NSpace(n^k)$, for some fixed $k$. Is it possible to imply that $EXP = PSPACE$? and what about $NEXP = PSPACE$? It seems the answer might be YES, because this question seems to be equivalent to the open question $EXP=PSPACE$?
Can it be shown using some padding argument?


texts:
I read that "Memory Mapping Segment"/"memory mapped file" is a segment of the virtual memory of a process, where a file or file-like Ressource is loaded into. It is for high performance file I/O.

I wonder..

(1) Is this normally done automatically by the OS?

(2) What are reasons to do this other than loading shared libraries? I can imagine that bigger files quickly blast the address space..

(3) if this isn't done, then where is the file read from. Does the process have to contact the hard drive to get the information from the library if it is not a "memory mapped file"


texts:
L = { a^n b^2n a^(n+2) : n>=1 }

So I'm trying to construct the grammar and I'm getting stuck.Some example strings would be these (spaced out to help demonstrate the patterns):

a bb aaa

aa bbbb aaaa

aaa bbbbbb aaaaa

This is what I have so far....

S -> aXbbXaaa

XbbX -> bXbbXb

The first rule says that there will always be an a on the left side, 3 a's on the right, and 2 b's in the middle.

The second rule adds 2 b's to the middle for b^2n.

But I can't figure out a way to get the a's....

Any suggestions? I don't want the exact answer, but rather hints to lead me to a solution. Thanks in advance!


texts: What is the big-O and big-$\Omega$ of this function?

texts:
The function is given below.

$\displaystyle \frac{1}{\sqrt{n!}} \left( m_t \left(N_t!\right)^{m_t} \right)^t . 2^{\frac{5n + 2t}{2}} \left( \sqrt{n}\right)^{\frac{n}{2}}$

Here, $n$, $m_t$, $N_t$ are integers, and $t$ is an integer constant.

I would like to know the asymptotic bound on this function.

My effort:

In the function, the complexity of computing Ni! is O((Ni)(log (Ni) log log (Ni))2).
I do not know how to proceed from here.


texts: Practical applications of disjoint set datastructure

texts: I know that the disjoint set datastructure is used   to keep track of the connected components of an undirected graph when the edges are added to the graph dynamically . I also know that is is used in Kruskal's  algorithm for minimum spanning trees . What are the other possible applications of this datastructure ?


texts: Longest Common Subsequence Via Dynamic Programming

texts:
I read the wikipedia page on the Longest Common Subsequence problem to understand the LCS Table approach, but it seems to result in different solutions given different orders of the original sequences. For example, the traceback table generated here is correct, since the longest common subsequence of AGCAT and GAC has a length of 2:

   |A  G  C  A  T
---+-------------
  G|0  1  1  1  1
  A|1  1  1  2  2
  C|1  1  2  2  2

From what I understand of how it's supposed to work, the length of the LCS should appear in the bottom right cell.

But using the same method for generating the table, which you can find here, if you rearrange the letters you get an incorrect solution.

   |A  A  G  C  T
---+-------------
  C|0  0  0  1  1
  G|0  0  1  1  1
  A|1  1  1  1  1

Length of the LCS shouldn't have changed, the bottom right value is no longer 2.

Is my question clear enough? Am I simply following the method incorrectly? From what I understand, the order of the original sequences shouldn't matter.


texts: Are there any neural NLG systems which don't generate in left-to-right order?

texts:
For a while, all classification tasks in natural language processing were based on simple RNN's, which operate in a very word-by-word order.  Adding gating mechanisms increased ability to "look back", and the newer addition of context vectors which can train attention to different words during the task have made classification of text less about "left-to-right" reading and more about selective focusing.

However, I have never seen a seq2seq or any other natural language generation system (machine translation, image2seq, etc) which generates the desired sequential output not in sequential order.  It seems this would be very powerful.  Are there any examples of using attention not only in encoders, but also in decoders?


texts: two ways of calculating the entropy in attribute selection (decision tree)

texts:
The definition of the entropy is

$$H(Y) = -\sum p(y_j)\log_2 p(y_j)\,.$$

Now my text book says to compute the entropy for each attribute we consider the grouping of the data by that attribute now in each group we calculate the entropy (with respect to classes in each subgroup) and do a weighted sum. In this way the attribute we choose has the most purity of data in each of their subgroups.

Then I thought why cannot we use the entropy in this way:

We consider each class and calculate the entropy of each class (with respect to the groups they belong to) and do a weighted average.

For example, let's say by putting attribute $t_1$ in the root, the data are split in to sets
and our class labels are $+$ and $-$.

  group 1         group2

{30 +   1 -}       {30 +   1 -}

(the numbers show the frequency of each class)

Method 1:

\begin{align*}
H(\text{group 1}) &= -(\tfrac1{31} \log\tfrac1{31}+\tfrac{30}{31}\log\tfrac{30}{31})\\
H(\text{group 2}) &= -(\tfrac{1}{31} \log\tfrac1{31}+\tfrac{30}{31}\log\tfrac{30}{31}\qquad \text{(just the same)}\\
H(f1) &= \tfrac{31}{62} H(\text{group 1}) + \tfrac{31}{62} H(\text{group 2})\,.
\end{align*}

Method 2:

\begin{align*}
H(\text{label }+) &= -(\tfrac{30}{60}\log\frac{30}{60} + \tfrac{30}{60}\log\tfrac{30}{60})\\
H(\text{label }-) &= -(\tfrac12\log\frac12 + \tfrac12\log\tfrac12)\\
H(f1) &= \tfrac{60}{62} H(\text{label }+) + \frac{2}{62} H(\text{label }-)\,.
\end{align*}

Now I know that the second method does not measure the purity of each subgroup but it can help us.  For example,

f1                               f2

group 1        group 2           group 1      gropu2

{30+  1-}    {30+  1-}           {30+  1-}    {30-  1+}

In this case the method one thinks both of the attributes do a good job of making pure subgroups but we also need the ability to make good decisions
meaning differentiating between different class labels with the help of our attribute. f2 does this much better and I think method2 can help us with that.

Here method 1 gives equal entropy while method 2 gives much lower entropy for f2.

But again method2 is not enough by itself since it cannot measure purity.

My question: am I right? If yes then how can we combine the use of both these measures to choose the best attribute for each node?


texts:
Let L={F| F is a finite language over Σ}
which of the following operation is not closed for L?

a. intersection

b. union

c. complement

d. none of the above

I thought the ans as d as all finite languages are regular and since regular languages are closed under all hence d seemed apt to me. But ans given is C
which is correct C or D? and Why?


texts: In a computer, the processor executes different threads and changes between them, the operating system is a program at the end that it´s being executed by the processor, there exists the posibility that the processor is not executing the code of the operating system, if there is, shouldn´t this cause problems with the programs being executed on the computer?


texts: Functional Abbreviation for Inst Expression in Turing's 1936 Paper

texts:
In Turing's 1936 paper On Computable Numbers Page 30-31, and its Correction Page 1-2 :
For a Turing Machine $M$, $Inst(q_i  S_j  S_k  L  q_l ) $ means that if $M$ scans symbol $S_j $ under $m-configuration$ $q_i$, then the symbol on the  square under scanner (with symbol $S_j $ ) is to be replaced by symbol $S_k$, and the scanner/header moves one unit $Left$, and its new $m-configuration$ becomes $q_l$.

At any stage of the motion of the machine, the number of the scanned
square, the complete sequence of all symbols on the tape, and the
m-configuration will be said to describe the complete configuration at
that stage. The changes of the machine and tape between successive
complete configurations will be called the moves of the machine.

The interpretations of the propositional functions involved are as follows :
${R_S}_j(x,y)$ is to be interpreted as "In the complete configuration
$x$ (of $M$) the symbol on the square $y$ is $S_j$.
$I(x,y)$ is to be interpreted as "In the complete configuration $x$
(of $M$) the square $y$ is scanned".
${K_q}_m(x)$ is to be interpreted as "In the complete configuration
$x$ (of $M$) the m-configuration is $q_m$".
$F(x,y)$ is to be interpreted as "$y$ is the immediate successor of
$x$".

Then, for establishing equivalence between Turing Machine and restricted
Hilbert functional calculus, it is written:

$Inst(q_i  S_j  S_k  L  q_l ) $ is to be an abbreviation for:
$(x,y,x',y')$ {
($ {R_S}_j(x,y) \,\&\, I(x,y)\,\&\, {K_q}_i(x) \,\&\,  F(x,x') \,\&\, F(y',y)) \to   $ $( I(x',y') \,\&\, {R_S}_k(x',y) \,\&\, {K_q}_l(x') \,\&\, F(y',z)  ∨  [(
 {R_S}_0(x,z) \to {R_S}_0(x',z))  \,\&\, ({R_S}_1(x,z) \to {R_S}_1(x',z))  \,\&\, ... \,\&\, ({R_S}_M(x,z) \to {R_S}_M(x',z))])$
}  $ S_0, S_1, ..., S_M $ being the symbols $M$ can print.

I am unable to convince myself of the exact correctness of the above formula w.r.t. to the meaning of $Inst(q_i  S_j  S_k  L  q_l ) $. More specifically, why do we have the following expression included? What is he trying to "cover" by including it?

$ ... \,\&\, F(y',z) ∨ [({R_S}_0(x,z) \to {R_S}_0(x',z))  \,\&\, ({R_S}_1(x,z) \to {R_S}_1(x',z))  \,\&\, ... \,\&\, ({R_S}_M(x,z) \to {R_S}_M(x',z))] $


texts:
I have two 2D arrays: $P[n][s]$ and $C[n][s]$, $s \leq n$.
P contains sets of nodes and $C$ the cost of a set in $P$, e.g. the cost of $P[2][2]$ is $C[2][2]$ and a set $p \in P = \{ s_0, s_1, ..., s_{n-1} \}^q, q \leq n$, e.g. $p=\{s_0, s_3\}$.
For every row I can pick at most one set but in the end the union of the picked sets needs to contain all nodes $\{s_0, s_1, ..., s_{n-1} \}$.
How do I find the least expensive picks in linear time?


texts: An approach to determine whether language is regular or not?

texts:
I have the following problem. I need to determine whether this language is regular or not:

$L:= \{ w \in \Sigma^*: \forall \alpha ∈ \Sigma, |w|_\alpha \text{ is even or divisible by 3}\}$

$|w|_\alpha$ => $|w|$ is the length of the word $w$ and $|w|_\alpha$ is the number of $\alpha$ characters in that word.

For example: $w$ = 100111 => $|w|$=6, $|w|_0$ = 2, $|w|_1$ = 4.

I know that I need to use deterministic/non-deterministic finite automata, regular expression/grammar to prove that it is regular or to use pumping lemma to prove that it is not.

But I'm not sure how to approach this problem to start proving something. Is this trial and error method or is there some way to know from the start?

I appreciate your help!


texts: Does this "set intersection" problem have a different name?

texts:
I've been back and forth about this one. I have the following theoretical homework problem, which describes the SET-INTERSECTION problem. In my homework, it's presented as being NP-complete.

Does this problem have a more common name in general Computer Science nomenclature? I'm trying to wrap my head around the definition itself -- and I can't find any resources that refer to the "set intersection problem" with similar parameters to this except in this pdf. It seems similar to the unit intersection problem described in a math stackexchange post. I also (naively?) think that it might be the set cover problem.

My actual intent is to understand what the problem describes -- so I'm looking for alternate names and resources that lead in the right direction. I'm not asking for any specific help in proving properties of it -- just understanding what it describes.


texts: Proof by Reduction: From Empty Language to Halting Problem on Empty Input

texts:
Question:
Let language $E$ = {$\langle M \rangle$ | $M$ accepts no inputs whatsoever}
Let language $H$ = { $\langle M \rangle$ | $M$ halts on an empty string input}.

Is it possible to show that $H$ is undecidable by reducing $E$ to it? (You can take it as a given that we know $E$ to be undecidable.) If so, show the work. If not, explain why not.

My attempt:

Assume that $H$ is decidable (that there exists a Turing Machine that decides $H$) and write a subroutine that maps the input, a machine description $\langle M \rangle$, to some other machine description $\langle N \rangle$, as follows:

def $R(\langle M \rangle)$:
  def $N(x)$:
    Check whether $M$ accepts no input whatsoever.
    If so:
      accept and halt on all inputs $x$ (including when $x$ == '')
    else, if $M$ accepts some input:
     loop forever on all inputs $x$ (including when $x$ == '')
     return $\langle N \rangle$

Does the above mapping work?

The subroutine $N(x)$ completely ignores the input $x$, and first checks whether $M$ accepts nothing. IFF so, $N$ will halt on every input $x$. Otherwise, IFF $M$ accepts something, then N will loop forever on all inputs $x$.

So, IFF $\langle N\rangle$ is accepted by a decider Turing Machine as belonging to $H$ (meaning $N$ halts on all inputs, including the empty string), we know $\langle M \rangle$ is accepted as belonging to $E$ (meaning $M$ accepts nothing).

Vice versa: IFF $\langle N \rangle$ is not accepted as belonging to $H$ ($N$ loops forever on all inputs, including the empty string), we know $\langle M \rangle$ is not accepted as belonging to $E$ ($M$ accepts something).

So we have a mapping where $\langle M \rangle$ is an element of $E$ IFF $\langle N \rangle$ is an element of $H$, Thus the mapping works. A decider Turing Machine for $H$ would be able to tell the difference, thereby leading us to be able to decide $E$. But since we know a priori that $E$ is undecidable, $H$ is also undecidable.

I'm just getting my feet wet on mapping-reducibility and am unsure whether the above is correct. Any help would be greatly appreciated.


texts: Same computation order using postfix notation?

texts:
I'm trying to understand arithmetic using stacks. Specifically converting infix notation to postfix notation. My question is how you convert an expression like: 1 + (2 + 3) + (4 + 5)
that computes in the exact order that the order of operations says.

Meaning: 1 + (2 + 3) + (4 + 5) becomes
1 + 5 + (4 + 5) then
1 + 5 + 9 then
6 + 9

If you do:

Push 1, Push 2, Push 3, Add, Push 4, Push 5, Add

Where Add pops the top two operands off the stack, adds them, and then pushes the sum back on the stack.

Alternative notation: 1 2 3 + 4 5 +

How do you add 1 + (sum of 2 and 3) next? If you do another Add then the sum of 2 and 3 will be added to sum of 4 and 5, because these are the top two on the stack. Is it impossible to do it in the exact same order? Doing each parentheses group first left to right then doing the rest of the computation left to right.


texts: I have created a new algorithm relating to finding all palindromes in a string. How to get it peer reviewed?

texts:
I have created an algorithm to find all palindromes in a string, and studied the related theory (Manacher, Suffix trees) and prior work and don't think my algorithm relates to any of the existing ones, and the implementation of my algorithm is 3 times faster than a Manacher implementation.

Now I want to get it peer-reviewed and have people of the related field of study bear on it to see if it indeed holds any merit.

How should I proceed? I am not a student or affiliated to any educational institution currently.

In case this is not the right forum for this question, do let me know where I can take this to.


texts:
Reflection is a common mechanism for accessing and changing the structure of a program at run-time, found in many dynamic programming languages such as Smalltalk, Ruby and Python, and in impoverished form in Java and (hence) Scala. Functional languages such as LISP and Scheme also support a good reflect framework.

Modern languages support concurrency, either by adding threads on top of the existing language constructs, or by designing from the ground up with concurrency in mind.

My question is:

  What models of reflection for the concurrency aspects in concurrent languages (multi-threaded, actor-based, active-object-based) exist?


texts: How to calculate the basic steps in Fibonacci sequences to get nFn and n^2

texts:
I am reading Algorithms by Sanjoy Dasgupta, Umesh Vazirani, Christos Papadimitriou and I am trying to understand how the number of steps $nF_n$ and $n^2$ were calculated. Here's the part of the book in Chapter 0 that mentions them. Functions fib1 and fib2 are written below the excerpt.

fib1, which performs about $F_n$ additions, actually uses a number of basic steps roughly proportional to $nF_n$. Likewise, the number of steps taken by fib2 is proportional to $n^2$, still polynomial in $n$ and therefore exponentially superior to fib1.

function fib1(n)
if n = 0: return 0
if n = 1: return 1
return fib1(n - 1) + fib1(n - 2)

function fib2(n)
if n = 0 return 0
create an array f[0 ... n]
f[0] = 0, f[1] = 1
for i = 2 ... n:
   f[i] = f[i - 1] + f[i - 2]
return f[n]


texts:
Why some books state that Primes is a NP problem if, as a decidibility problem, it can be solved in polynomial time?

A simple example:

A number can has its primality tested by dividing it by all numbers from 2 to \sqrt(n). It then takes at most \sqrt(n) operations to find if its prime.

After talking to colleagues, some stated that \sqrt() method is (was) in NP, but after reading about it it seems to take constant time for a certain precision (precision does not matter for this kind of problem).

Why then?

P.S.: Just to state, I know that P is within NP. The thing is not about it being contained, but it beign in NP and not in P (no polynomial solution).


texts: Kolmogorov Complexity of String Concatenation

texts: For all bit strings $x$, $y$ and Kolmogorov complexity $K$, is $K(xy) > K(x)$?


texts: DFA complexity of reverse of language recognized by "maximal" DFA

texts:
Let's assume that DFA $A$ over the alphabet $\Sigma$ and with states $Q$ is maximal if for every function $f\colon Q\rightarrow Q$ there exists such word $w \in \Sigma^{*}$, that $q \cdot w = f(q)$ for every state $q \in Q$. Let $L \subseteq \{a, b, c\}^{*}$ be a non-empty language recognized by a maximal automaton with $n$ states.

Prove that all DFAs recognizing language $L^R$ have got at least $2^n$ states.


texts: Could you show the intractibility of SAT by showing that the number of variables contributing to an arbitrary unsatisfied clause is not constant?

texts:
Preface: This is not an attempted proof at P vs NP

Starting with some CNF Boolean expression ϕ, by the rules of logical disjunction, a clause is only unsatisfied if each of the literals in it are themselves forced into being unsatisfied. A trivial example is (x OR y) with the interpretation XY=00. Non-trivially, we can find a contradiction, ϕ ↔ x ∧ -x. Since a Boolean variable can only be true or false, some clause in ϕ will remain unsatisfied depending on which interpretation of X we choose.

ϕ is satisfied by an interpretation I, iff I doesn't leave any of the clauses in ϕ unsatisfied, following the rules of logical conjunction. If each I contains some unsatisfied clause, then ϕ is unsatisfiable.

ϕ = (a OR c) AND (b OR d) AND (-c OR -d)
ϕ[00CD] = (0 OR c) AND (0 OR d) AND (-c OR -d)

Due to the clausal structure of ϕ above, any I containing A=0 and B=0 will always force the expression into being unsatisfied. Even if we add more clauses or more variables, the existence of these clauses in ϕ means that any such I will always be an unsatisfying interpretation.

Following from this, if ϕ also contained clauses which acted analogously on interpretations containing AB=01, AB=10, or AB=11, then there'd be no satisfying assignment containing A and B. Since all maximal interpretations will contain some assignment for A and B, ϕ is made unsatisfiable based off of these 2, out of a potential n, variables.

ϕ' = (a OR b) AND (a OR c) AND (-b OR -c)
ϕ'' = (-a OR d) AND (-a OR e) AND (-d OR -e)

We could create an example with 1 variable as well. ϕ' has no satisfying I which contains A=0 and ϕ'' has no satisfying I which contains A=1, as the respective assignment to A allows us to generate a contradiction in that expression. If we have the expression Φ = ϕ' AND ϕ'', then we'd automatically have an unsatisfiable expression caused by the complete inability to assign A.

So could we tie up 3, 4, 5 or m $\le$ n variables such that each of the 2m ways of assigning them forces some unsatisfied clause? If m is the maximum number of variables which we could tie up to force some arbitrary clause of size k into being unsatisfied, then if you take each of the (n choose m) possible groups of variables and you try all 2m ways of assigning them, as long as each variable group has at least one I which doesn't leave some clause unsatisfied, then your expression is satisfiable.

I conjecture that when k = 2, m = 2, no matter the problem instance. This would mean that no group of 3 or more variables is both necessary and sufficient to leave a clause with only 2 literals unsatisfied. However, once k $\ge$ 3, then m $\le$ n. We could force a clause of 3 literals to be unsatisfied with 3, 4, or 5 variables, only bounded by n or the total number of variables in ϕ.

I have not given any proof that 2SAT and 3SAT have the value of m that I think they do, but what I want to know is if the conjecture is true, would that mean that the classes are different? Would such a structural difference, if proven to be true, be able to separate the two classes of problems?

Edited to create a more technical question to clarify the information I'm looking for

Edited Major edit to address comments


texts: Is there a term for "delegate" function in CS?

texts:
This question is all about terminology (names).

When you consider "list", this term is well defined in CS -- despite the fact programming languages use and misuse this term (for example C# List is not a list).

I am looking for term in Computer Science domain that C++ defines as pointer to a function, C# as delegate, Swift as closure. Consider a function A that takes another function B as a parameter -- is there established term for B? Functor?


texts: In Lbest PSO, how is the local best position in a neighbourhood defined?

texts:
I am implementing a couple of PSO (particle swarm optimization) algorithms, and I got stuck on a bit of detail which I could not clearly determine from the papers I have read. In lbest PSO, for each particle, the velocity update step takes the best particle's position in that particle's neighbourhood into account. What I am not 100% clear on is how that "best particle" is defined. To my understanding, it could be

(a) the best current position of each particle in the neighbourhood,

(b) the best pbest position (in memory) of each particle in the neighbourhood, or

(c) the best lbest psoition of each such particle, which could be initially determined from (a) or (b) as above, but over time allow information about other neighbourhoods' best positions to distribute across the swarm.

I realize that each of the above may be a valid and published version of PSO. I just want to know which version is usually referred to as "lbest PSO".


texts: Probability of selecting a particular set, by sampling without replacement from a categorical distribution

texts:
Suppose I have a categorical distribution on items $1,\dots,n$, that assigns probability $p_i$ to item $i$.  I now repeatedly sample from this distribution, until I have obtained $k$ unique objects.  I'd like to compute the probability that the set of objects obtained is exactly $\{1,\dots,k\}$.

Is there an efficient way to compute this probability, given $p_1,\dots,p_n$ and $k$?

I can see that the probability has the form

$$p = \sum_\sigma \prod_{i=1}^k {p_{\sigma(i)} \over (1-p_{\sigma(1)}) \cdots (1-p_{\sigma(1)}-\dots-p_{\sigma(i-1)})},$$
where the sum is over all permutations $\sigma \in S_k$ on $\{1,\dots,k\}$.  (Here $\sigma$ represents the order in which the items $1,\dots,k$ are selected.)  However, this formula for the probability involves $k!$ terms, so computing the probability in this way would take time exponential in $k$.  Is there a more efficient way to compute it?

Of course, without loss of generality we can assume $n=k+1$.


texts: Connection between NAND gates and Turing completeness

texts: I know that NAND gates can be used to create circuits that implement every truth table, and modern computers are built up of NAND gates. What is the theoretical link between NAND gates and Turing completeness? It seems to me that NAND gate circuits are closer to finite automata than Turing machines. My intuition is that I can build flip-flops, and therefore registers and memory, out of NAND gates, and unbounded memory is a crucial property of Turing complete systems. I'm looking for a more theoretical or mathematical explanation, or pointers on what to read.


texts: Why do caches fetch data to the right if the offset bit is 0 and to the left if it is 1 in a 2-word block

texts:
Here is an example of table with 32 bit addresses and their respective indexes and tags. The cache has a total of 8 blocks and 2-word blocks.

So since we have 2 word blocks, that means that the offset is 1 and we use the least most significant bit as the offset. So in the first row, it not only brings 3 but it also brings 2 into the cache because the offset bit is 1(why not 4 if the offset bit is 1). Now I understand that the importance of this is to reinforce the idea of spatial locality, I just want to understand more about the procedure and what kinds of conflict it would cause if it was the other way around. If you can show it with an example that would be great.


texts: Understanding $\epsilon$ transitions on NFA

texts:
I can't understand why $\epsilon$ is accepted. I thought if $\epsilon$ is inputed then it would go from $q_1$ to $q_3$. $a$ is also accepted, but I though if $a$ is inputed then then the NFA would die, because in $q_1$ there's no where to go.

I read on another post about $\epsilon$ being at two states at the same time, but couldn't get it. What exactly is happening when $\epsilon$ is entered and when $a$ is entered (two different strings)?

              q1
epsilon---------------------
           q1    q3

I think the above is the correct tree when $\epsilon$ is inputed, but makes no sense to me.


texts: How can I efficiently find the largest positive interval in an unsorted array?

texts:
Given a set of values like [4, 8, 1, 5, 2, 6, 9, 2, 3, 5, 11, 9], how can I find the largest positive interval between any two of them? For example in the one I just listed, index 0 to index 1 has an interval of 4 because 8 - 4 = 4. But the largest positive interval is between index 2 and index 10, because 11 - 1 = 10.

I can see that there's a way to do this in linear time, but I can't figure out what it is. The n^2 brute force solution is straightforward, but I want to understand the better way.

To be clear, the largest positive interval in [20, 1, 4] would be 3, not 19, because 20 -> 1 is an interval of -19.

The solution I would put forward is to translate the array in linear time to an array of differences, e.g. [20, 1, 7, 4, 2] becomes [0, -19, 6, -3, -2], and then use Kadane's algorithm for finding the maximum contiguous subsequence. The largest subsequence would be 6 on its own, implying indices 1 and 2 provided the answer.


texts: Is "Solving two-variable quadratic polynomials over the Integers" is an NP-Complete Problem?

texts:
On this Wikipedia article, they claim that given $A, B, C \geq 0, \; \in \mathbb{Z}$, deciding whether there exist $x, \,y \geq 0, \, \in \mathbb{Z}$ such that $Ax^2+By-C=0$ is NP-complete?
Given by how easy I can solve some (with nothing but Wolfram), it doesn't seem right. I'm sure it's either written incorrectly or I'm just misunderstanding something.


texts: How many times can you divide a list of n elements in 1/2

texts: I am trying to wrap my head around recursion and divide and conquer algorithms. Can someone provide a proof and explanation of how many times a list of n elements can be divided in 1/2 on both sides.. In other words the total number of half divisions in a recursive divide procedure on a list of size n.


texts: Showing a problem on a specific class of graphs is NP-hard

texts:
We know that a set of problems like minimum clique cover problem, coloring problem, vertex cover, ... are NP-hard for general graphs, but may be polynomial-time solvable for some classes of specific graphs, such as perfect graphs.

In my case, I have a specific class of graphs defined as follows.  Define $f : \mathbb{N} \to \mathbb{N}$ by $f(k) = k(2^{k-1}-1)$.  There is a function $g$ from natural numbers to graphs, so that $f(k)$ defines an undirected graph structure on $f(k)$ vertices (i.e., $g(k)$ defines the vertex set and edge set of the graph) for each natural number $k$.  Now I want to consider the class of all vertex-weighted graphs that are consistent with $g(k)$ for some $k$, i.e., where the vertex and edge set is defined by $g(k)$ but the weights on the vertices can be arbitrary.  (The full description of a class of graphs can be found here.)

Finally, I want to solve a problem such as minimum clique cover for this class of graphs. Is it NP-hard or can we always find a polynomial-time algorithm (polynomial in the size of the input, rather than polynomial in $k$) that finds the solution?


texts: Correctness of splitting an undirected tree into a forest of trees with even number of children

texts:
Given an undirected tree (i.e. a tree without any designated root) of even number of nodes.
The task is to remove as many edges from the tree as possible to obtain a forest of trees,
where each such tree contains even number of nodes.
And return/output number of removed edges as an output/answer.

Counting maximum number of removed edges is relatively simple:

Choose any node as a root node;
Recursively traverse a tree using depth-first approach;
Count number of children of each sub-tree (from bottom to up),
and cut sub-tree from the tree if this sub-tree has even number of children (i.e. simply increment counter of removed edges);

This solution is correct but I don't understand why.

I would like to see proof of correctness of such algorithm.

In particular, I have the following doubts (when I'm thinking on this solution):

Why starting DFS from any chosen root gives correct maximum number of removed edges?
Why cutting sub-trees with even number of children from bottom to up gives correct result?

I wrote on paper all possible configurations 1, 2, 3, 4, 5, 6-nodes of undirected trees.

For example, there are two possible configurations of undirected tree with 4 nodes:

(a)

x-x-x-x

(b)

x-x-x
  |
  x

In (a), you can split a tree into 2 sub-trees with 2 nodes each.

In (b), you can not do it since it will be two sub-trees of odd number of nodes (with 1 node and with 3 nodes respectively).

So my doubts based on suggestions:

What if it depends where you start cutting sub-trees?
What if greedy cutting sub-trees with even number of children from bottom to up doesn't give correct maximum number of removed edges? (continue of first question)

This puzzle is described on HackerRank as "Even Tree".
Their editorial and discussion just declared algorithm but they don't say why it works.
Also, I found discussion on stackoverflow but they also don't give explanation why such approach works.


texts: Difference between a lambda term and a lambda expression

texts:
Is there any difference between a $\lambda$-term and a $\lambda$-expression?

Looking at the recursive definitions on Wikipedia of
$\lambda$-term and $\lambda$-expression, they are equivalent. But I am confused as they are slightly different and refer to what they define by a different name.


texts: Complexity of Longest Palindromic Subsequence Algorithm

texts:
I'm trying to find the longest palindromic subsequence for any string and I've tried two approaches:

Recursive Algoritm
Dynamic Programming

Dynamic programming should be the better option in this case because of the time complexity but the time complexity of both algorithms is $O(n^2)$. My question is if the time complexity is the same for both algorithms, why is the dynamic programming approach considered better than recursive solution? I'm following the algoritms in this post. It says that the time complexity of dynamic programming algorithm is much better than the worst case time complexity of naive recursive implementation. What could be the worst case?


texts: Recursively edit 2-D array using backtracking

texts:
I have a 2-D array which contain 3 types of elements:

C (Contaminant)
R (Rock)
W (Water)

The rule is that:

  contaminant can seep through water but not through rocks.

Let's say I have the following input array:

WWWRW
CRRRR
RWWRW
WWWRR
WRRWC

So the cells which have 'C' as their value in the above array can contaminate in the same row and same column if water is present.

So the output would like something like this:

CCCRW
CRRRR
RWWRW
WWWRR
WRRCC

I know I have to solve this using via backtracking and recursion, but I am not able to come up with an apt algorithm to do so.

Any help will be hugely appreciated.


texts: What us difference between distributed computing and workgroup computing?

texts: According to the definition, distributed computing means to distributed a problem among different users while workgroup computing means to work on a problem by different users. So what's the difference between these two? Plz explain it with an example


texts: Dekker's Algorithm spin on intent instead of turn

texts:
For Dekker's algorithm given below (from Wikipedia), why is it that we wait for the turn to change, instead of waiting for p1 to set it's flag to false? It seems to me that it would be safer (or more efficient?) to wait for p1 to complete its exit routine before p0 sets its intent again. It seems like a livelock isn't an issue since we still check for turn on line 3, so when both processes declare their intent, then there is a tie breaker.
p0:
0  while(true) {
1    wants_to_enter[0] ← true
2    while (wants_to_enter[1]) {
3       if (turn ≠ 0) {
4          wants_to_enter[0] ← false
5          while (turn ≠ 0) {} // change this to while (wants_to_enter[1])
6          wants_to_enter[0] ← true
7       }
8    }
9    ...
10   // critical section
11   ...
12   turn ← 1
13   wants_to_enter[0] ← false
14 }


texts: If L is context-free, must FH(L) be context-free?

texts:
Define $FH(L) = \{x \in \Sigma^* : \exists y \in \Sigma^* \text{ with } |x| = |y| \text{ such that  } xy \in L\}$.  In other words, $FH(L)$ is the set of first halves of even length strings in $L$.  Given this, if $L$ is context-free, must $FH(L)$ be context-free?

Here's my attempt at a proof:
Since $L$ is a CFL, there exists a non-deterministic PDA recognizing $L$, $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$, where $\Sigma$ is the input alphabet, $\Gamma$ is the stack alphabet, and $Z_0$ is the symbol representing the initial stack contents.  Construct PDA $M'$ from $M$, with $M' = (Q', \Sigma, \Gamma, \delta', q_0', Z_0, F')$, defined as follows:

$Q' = {q_0'} \cup (Q \times \Gamma_{\varepsilon}) \times (Q \times \Gamma_{\varepsilon}) \times (Q \times \Gamma_{\varepsilon})$.
$F' = \{[(q,X),(q,X),(p,Y)] : X,Y \in \Gamma_\varepsilon \text{ and } p \in F\}$
$\delta'(q'_0, \varepsilon, \varepsilon) = \{([(q,X), (q_0,Y), (q,X)], \varepsilon) : q \in Q \text{ and } X,Y \in \Gamma_\varepsilon \} $
$\delta'([(q,X),(p,Y),(r,Z)], a, \varepsilon) = \{([(q,X),\delta(p,a,Y), \delta(r,b,Z)], \varepsilon): X,Y,Z \in \Gamma_\varepsilon\ \text{ and } b \in \Sigma\} $

The first component of a state in $Q'$ records the guessed state $q$ and does not change once it is initially recorded.  The second element records what state we are in after having processed some prefix of the input x, starting from state $q_0$, and the third element records what state we are in  after having processed some prefix of the guessed $y$, starting from $q$.
I am not sure if this proof works, because I am a bit confused as to what to do with the stack for $M'$.


texts: How the operating system allocated to dual-channels memory?

texts:
I learned that the boot loader transmit the operating system from Hard Disk to Main Memory during the booting process.

I wonder, today's computers are equipped with multiple slice of memory of dual-channels.

How the Operating System is allocated to each channel?

I guess it should not clone twice.