texts: Is there a theory of exception hierarchies?

texts:
I'm familiar with a dozen of programming languages which have exceptions in some way, yet I came to witness two "pathological" tendencies.

There doesn't seem to be a common pattern or hierarchy of exceptions. Every language basically rolls its own version, and if the exceptions make it into the standard, then the kinds of exceptions that one finds in the standard would be rather arbitrary (mostly those which were implemented while creating language tools, such as reading source code from string or an exception to invoke debugger, or the one which happens when the file cannot be found etc.)

Exceptions defined by the language are very rarely reused by user programs. There would be usually one or two popular exceptions ("not implement" for example). Though most times programmers will create their own exceptions. (Compare this to, for example, creating new numeric types or new collection types).

This looks like a terrible omission to me. How comes no one knows what kinds of errors will be needed in user programs? I was hoping for there to be a kind of nice hierarchy, similar to numeric types, collections, object system etc.
Worse yet, Goolge and Wikipedia provide very little help on the subject. So far I've only found a paper on functional exception which opens in a passage:

This paper argues that lazy functional programming not only makes
built-in exception handling mechanism unnecessary, but provides a
powerful tool for developing and transforming programs that use
exceptions

(A Functional Theory of Exceptions, Mike Spivey, 1988)
But I think that exceptions are good. I don't want to transform programs that use exceptions, on the contrary, I want to make the use of exceptions less chaotic.
The question:
Is there a theory of exceptions? If so, what is it called? What are, if any, the cornerstone works outlining the basis of it?


texts: Are Agda's inductive-inductive types safe?

texts:
An inductive-inductive definition is a kind of simultaneous inductive definition of a type $A : \mathcal U$ and a type $B : A \to \mathcal U$. I think Agda also lets you extend this idea in all of these ways:

add another type $C : A \to B \to \mathcal U$ to be simultaneously defined.
have $B : F(A) \to \mathcal U$ for an arbitrary function $F:\mathcal U \to \mathcal U$.
combine the above two, so that you have $C : G(A, B) \to \mathcal U$ for an arbitrary function $G : \mathcal (A: \mathcal U) \to \mathcal (B: F(A) \to \mathcal U) \to \mathcal U$.
have each type being defined live at different universe levels.

Is it known that these are safe things to do?
Edit: I skimmed Inductive-Inductive Definitions and it suggests that the first one is always good, and the second one is at least okay when $F$ is a "pullback-preserving functor". It doesn't seem to say anything about the other two.


texts: why does ${a^nb^n}$ fit the pumping lemma for context-free languages?

texts:
I am writing somthing about Ppumping Lemma. I know that the language $L = \{ a^nb^n| n ≥ 0 \}$ is context-free. But I don't understand how this language satisfies the conditions of pumping lemma (for context-free languages) ?

if we pick the string $s = a^pb^p, |s| > p , |vxy| < p \land |vy| > 0$.

it seems it will be out of the language when we pump it (pump up or down) or there is something I'm missing.

Any explanation would help.

Edit: I am applying pumping lemma to a^nb^n and it fails to stay in the language for all cases. So, why is it Context free?


texts: Mahalanobis distance of point to plane algorithm

texts:
I am trying to understand the Mahalanobis distance of a point from the plane given by this paper. The algorithm is given below:

Calculate covariance of point $S_{uu}$
Apply a whitening transform to the covariance matrix using SVD where $S_{uu} = RVR^T$. $R$ is the rotation matrix and $V$ is the scale $V = diag(a^2, b^2, c^2)$
The output is transformed into 3 homogenous 4x4 matrices

$Rh = \begin{bmatrix} R & 0 \\ 0^T & 1 \end{bmatrix}, Th = \begin{bmatrix} I & 0 \\ -u^T & 1 \end{bmatrix}, Ah = diag(a,b,c,1)$
where $u$ is the point under consideration.

The transformed plane is given by $q = Ah*Rh*Th*p$ where p is the planar parameters

5 . The transformed plane distance to the center of the unit sphere is given as:
$d_M = \frac{q_4}{\sqrt{q_1^2 + q_2^2 + q_3^2}}$
My first question is regarding the whitening transform. I am not sure how it is being derived (its not given in the paper). If anyone can provide an intuitive explanation, that would be great.
My second question is - I simulated a plane with planar parameters [0, 0, 1] and points on the plane with std error of 0.02.  We can recover the planar parameters using svd. Now, when I run the algorithm to get the transformed plane using the following code:
# whitening transform of point covariance
cov_pts = np.cov(pts.transpose())
r, v, rt = np.linalg.svd(cov_pts)
abc = np.sqrt(v)
ah = np.diag(v=np.concatenate((abc, np.array([1]))))
rh = np.zeros((4, 4))
rh[0:3, 0:3] = r
rh[3, 3] = 1
th = np.eye(4)
th[3, 0:3] = -center
transformed_plane_fit = np.dot(np.matmul(np.matmul(ah, rh), th),
                                       np.concatenate((plane_fit, np.array([1]))))

the values I get for transformed planar fit is $-0.029929, -0.000731, -0.019731, -0.911577$, which don't seem to correspond to the planar parameters. What can be the reason for the discrepancy?


texts: Show that a language with union is not regular by using pumping lemma

texts:
Given the language $L:= { \{ c^{2k} w \ \vert \ k \ge 1, \ w \in \{a,b,c\}^* \ and \  \vert w\vert_a \ = \ \vert w\vert_b \} \  \cup \ \{ a,b \}^* }$
I'm really unsure how to even start because of the union.
I tried it with $w=a^nb^n$ but my correction said that it's
pumpable because it is in $\{ a,b \}^*$ which makes sense.
What would be a good word to start with?
I guess there are several cases i need to show?


texts: Finding no. of leaf nodes for each node in a BST

texts:
A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is

$\qquad \min(\#\text{leaves in } L(x), \#\text{leaves in } R(x))$

for $L(x), R(x)$ the left resp. right subtree of $x$, then the worst-case time complexity of the program is

$\Theta(n)$
$\Theta(n \log n)$
$\Theta(n^2)$
$\Theta(n^2 \log n)$

I am actually looking for a subtle hint.


texts: Conversion of nfa with self-loop to one without self-loop

texts: For every nondeterministic finite state automata that has self-loop(s), there exists an equivalent nfa that does not have any self-loop. How can we prove this statement in a general basis without the use of examples?


texts: Changing probabilities to 0/1 in definition of class IP

texts:
A language $L$ belongs to $\mathbf{IP}$ if there exists $V,P$ such that for all $Q$, $w$,
$$w\in L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3$$
$$w\notin L\Rightarrow Pr[V\leftrightarrow Q\text{ accepts }w]\leq1/3$$

I am trying to understand the claim that changing the $1/3$ to $0$ for the $w \notin L$ case is equivalent to having a deterministic verifier, thus reducing the class to $\mathbf{NP}$. Is this because, in this case, we could rig all of the $V$'s interactions with $P$ so that whenever $Pr[V\leftrightarrow P\text{ accepts }w]>0$, it now determinstically accepts?

If this is correct, then why can't we do a similar thing for the hypothetical situation where the $2/3$ is replaced by a $1$ (apparently doing this does not change $\mathbf{IP}$)? My intuition is that we can't make a similar modification because it would require modifying $V$'s behaviour for all $Q$. But my thoughts are bit fuzzy here...

Can someone please help clarify?


texts: Examples of processes / problems that cannot be tackled by Turing Machines

texts:
I know that there are problems that cannot be solved by any algorithm, such as the Halting problem.
I also know that some processes cannot be even adequately approximated by any Turing Machine (equivalently, any digital computer), meaning that some property of the process cannot be simulated due to its intrinsic nature. An example of this would be Chaos, and its non-periodicity.

My question is: are there any other interesting processes in nature that really are outside the realm of what Turing Machines / digital computers can tackle? Any other interesting problems (outside from the well-known textbook ones) that Turing Machines cannot solve?

The reason why I ask for this is that I'm teaching to computer science students, and I want to make sure they understand that computers are not all-powerful machines, but there are problems and phenomena that lie fundamentally outside the realm of possibilities of any digital computer.
What powerful examples could I use, other than Chaos and the Halting problem, to support my argument?

Thank you!


texts: Language of CFG: $S \to aS | aSbS | \varepsilon$

texts:
I'm trying to prove that the language L generated by the CFG $S \to aS | aSbS | \varepsilon$ is the language $L=\{ w \in \{a,b\}^*: \text{every prefix of $w$ has at least as many $a$'s as $b$'s} \}$.I proved the first inclusion $w \in L(G) \implies w \in L$. I can't prove the vice versa. By induction on the lenght of $w \in L$, I could say:

BASE: $|w|=0$, i.e. $w=\varepsilon$ and it's clear.

IND: suppose the thesis is true whenever $|w|<n+1$ and prove for a word of lenght $n+1$. Given $w \in L$, $w=a_1\dots a_{n+1}$ one has $a_1=a$ since $a_1$ is a prefix of $w$. Thus I can first apply the rule $S \to aS$ or $S \to aSbS$. But what now?

Any suggestion would be helpful. Thanks.


texts:
Consider the following problem.

  Given a set $S$ of integers, a function $f : \mathbb{Z} \to \mathbb{Z}$ and $k \in  \mathbb{Z}$, decide wether there is $X \subseteq S$ such that $f\left(\sum_{x\in X}x\right)=k$.

Is this still considered a subset-sum problem?

For instance, given

$\qquad \displaystyle S=\{ −7, −3, −2, 5, 8\}$

and $k=0$, find a subset $X$ such that $f\left(\sum_{x\in X}x\right)=0$ for $f(y)=-3+y$. In this case, a solution is $X=\{ -3,-2,8 \}$.


texts: why does the pumping lemma want us to only consider the first repitition of states?

texts:
In Sipser's Intro to Theory and computation, He writes:

I don't understand the constraint on x. Shouldn't it be just y <=p? (Equal bc in the case when machine M runs through all states p) Making xy <=p, the theorem only wants us to consider the first p elements and the first repetiton. Why can't any repetition be considered for the pumping lemma? We can simply pick an arbitrary substring of length p and the looping structure works just fine?
Is this constraint on x just to generalize since some inputs may not have more than one looping structure?


texts: Why does making a seemingly insignificant edit to an executable's machine code return errors?

texts:
First of all, I would like to apologize if this question is in the wrong section. For all I know, it could be placed in Super User, Reverse Engineering, or Stack Overflow.

Now lets get back the experiment I tried:

What I did was took an executable file and changed its file type to a text document type. Then I opened this file in a text editor and changed a single character. This character was just part of some descriptive copyright information. After this I changed the file type back to an executable file type and tried running it. Why does the Windows operating system return the error, "The version of this file is not compatible with the version of Windows you're running...", when attempting to run the executable?

What is happening underneath the hood when an executable runs?


texts: Difference between Sequential ,Direct and Random acess with their acess time

texts:
I'm stuck on a point while reading about these different accessing methods. As per author.

Sequential access

  Memory is organized into units of data, called records.Access must be made in a specific linear sequence.

I understand that it will take variable time to access due to sequential ordering.

Direct Access

  individual blocks or records have a unique address based on physical location.Access is accomplished by direct access to reach a general vicinity plus sequential searching,counting,or waiting to reach the final location. Again, access time is variable.

Here I'm Stuck that if we have unique address why it is taking variable time and why we can't directly access data.

Random Access

  Each addressable location in memory has a unique,physically wired-in addressing mechanism. The time to access a given location is independent of the sequence of prior accesses and is constant.

What is the difference between this and direct access method.


texts: What does 'computable in the limit from above' mean?

texts:
$H(x)$ is the program size complexity of $x$ for some universal Turing machine $U$. $H$ is not computable, however $H$ is "computable in the limit from above".

From my notes:

  i.e the set $\{(x,n) \mid x \in B^*,n \geq 0, H(x) \leq n\}$ is computably enumerable.

Can someone tell me what this means? I understand the incomputability of $H$ but the term "limit from above" is confusing me.


texts: Comparison between Aho-Corasick algorithm and Rabin-Karp algorithm

texts:
I am working on string searching algorithms that support multiple pattern search.  I found two algorithms that seem like the strongest candidates  in terms of running time, namely Aho-Corasick and Rabin-Karp. However, I could not find any comprehensive comparison between the two algorithms. Which algorithm is more efficient? Also, which one is more suitable for parallel computing and multiple patterns search? Finally, which one requires less hardware resources?

For AC algorithm, the searching phase takes $O(n+m)$ time, while it is $O(nm)$ for RK. However, the running time for RK is $O(n+m)$ which makes it similar to AC. My tentative conclusion is that RK seems practically better as it does not need as much memory as AC. Is that correct?


texts: NP-hardness proof, what is wrong with it?

texts:
My question is the following: If we have a problem divided into two versions, weighted and unweighted. Can we prove that the unweighted problem is NP-hard from the fact that the weighted problem is NP-hard ?

For example let say I have the knapsack problem (the weighted version):

$$\max \sum_{i}^n w_i x_i$$
$$\text{s.t.} \sum_{i=1}^n p_i x_i\leqslant W,\quad(WP)$$
$$x_i\in\{0,1\}.$$

This problem is know to be NP-hard problem. However, the unweighted version of this problem is given by:
$$\max \sum_{i}^nx_i$$
$$\text{s.t.} \sum_{i=1}^n p_i x_i\leqslant W,\quad(P)$$
$$x_i\in\{0,1\}.$$
is not NP-hard since the optimal solution is to sort the items in the ascending order with respect to $p_i$ and start filling the bag until the capacity $W$ is reached.

The problem is the following: I used the unweighted version of this problem as a special case of the weighted version and I showed that unweighted is an NP-hard problem. What is my mistake?
Here is my steps: I will reduce $(WP)$ to $(P)$ in polynomial time. So, an instance of $(P)$ is constructed easily by taking $w_i=1$. And I am done and hence $(P)$ is NP-hard which is obviously wrong.

Thank you to correct me and give me if possible some good references that deal with such weighted and unweighted problems?


texts: Regular expression $(a^{*}b^{*})^{*} = \left( a+b \right)^{*}$ proof

texts: Im having a lot of trouble proving that for the Regular expression $R_{1} = \left( a^{*} b^{*} \right)^{*}$ and $R_{2} = \left( a+b \right)^{*}$ that $L \left( R_{1} \right) = L \left( R_{2} \right)$. I was wondering if anyone could help me with this? thanks


texts: If P is equal to NP, then what happens to the problems those can be solved in polynomial time?

texts:
Suppose that an algorithm $A$ is able to solve a problem in NP in polynomial time.
Does this effect the good old sorting, searching, shortest path, minimum spanning tree etc. algorithms?
Can this improvement pave the way for a $O(n)$ sort or $O(log^*n)$ search?

Edit: P vs. NP problem can also be interpreted as "can we find something without searching?" that's why I wonder if that effects the other problems as well.


texts: Algorithm to enumerate all complete schedulings of finals tests?

texts:
I'm creating an app that receives some map between finals and the respective periods during which they are held and a student's required finals. I was wondering if there was an algorithm to enumerate all complete schedulings of these finals. Concretely, I have a list of finals for a specific student and each $F_i$ has a list of periods $P_i$ that they are held. In my specific use case, there are $8$ periods.

$$
\begin{align}
F_1 &\rightarrow \{P_1, P_2, P_8\} \\
F_2 &\rightarrow \{P_4, P_7\} \\
F_3 &\rightarrow \{P_4\}
\end{align}
$$

And I want to find all assignments of periods to finals that are non-overlapping and complete, i.e. the student can attend all finals. One such assignment could be:

$$
\begin{align}
P_1 &\rightarrow F_1 \\
P_4 &\rightarrow F_3 \\
P_7 &\rightarrow F_2
\end{align}
$$

This is complete because all finals are associated to a period and the periods are non-overlapping. Another assignment could be $P_4 \rightarrow F_3, P_7 \rightarrow F_2, P_8 \rightarrow F_1$. My question is then, how could I enumerate all these assignments? I was thinking of a greedy approach whereby I choose a period starting with the finals with the fewest amount of available periods, the choosing for the next-most restricted final. But that only gives me one particular working schedule, not all  valid schedulings.


texts:
I've been reading about the differences between serializability and linearizability, which are both consistency criteria for replicated systems such as replicated databases. However, I don't know in which cases linearizability would be needed, even though it's stronger than serializability.

Could you come up with scenarios where such strong property would actually be necessary?


texts: Is asymptotic ordering preserved when taking log of both functions?

texts:
In one of my exercise sheets I have the following question;

Let $f,g\colon \mathbb{N}\longrightarrow\mathbb{R}$ be positive functions with $f(n) \in O(g(n))$. Prove or disprove;  $\ln(f(n)) \in O(\ln(g(n))$.

I first thought this would be the case since $\ln$ is a monotonically increasing function (derivative is positive), and so the asymptotic ordering of these functions wouldn't be affected. But then there was an example stuck in my mind and which I have later on seen on the internet as well.

Let $f(n) = 2^n,g(n)=3^n$. Since $f(n) \in O(g(n))$ given $\lim_{n\to \infty} \frac{3^n}{2^n}=\infty$. Then $\ln(f(n))=n\ln 2$ and $\ln(g(n))=n\ln 3$ which leads to $ 0< \lim_{n\to \infty} \frac{n\ln 3}{n\ln 2} < \infty$ which implies $\ln (f(n)) \in \Theta(\ln(g(n)))$. The growth rates have changed, yes, but since $\Theta(f) = O(f) \cap\Omega(f)$ isn't, technically speaking, $\ln(f(n)) \in O(\ln(g(n)))$? I am a bit confused as going by my own steps the initial assumption seems right but I am not entirely convinced for either possibility. Because if this is correct I feel like I can extend the same idea for exponentiation as well maybe.

Anything to prove or disprove the statement with an explanation would be really welcome as I am a bit lost at the moment.


texts: Is using Fibonacci Heaps in Huffman Code, better than a regular Min-heap?

texts:
When using Huffman Code, to generate prefix-code trees for a sequence of letters, CLRS choose to use a normal Min-heap data structure.

Using Fibonacci-heaps instead, are we not able to achieve a better bound on the running time, knowing that especially the INSERT operation of Fibonacci-heaps are constant time amortized, compared to worst-case $\theta(\log n)$ in a regular Min-heap?

I have tried to search online, without finding a solid reference, of the use of Fibonacci-heaps in Huffman code?

Can anyone explain to me if this is a practice, or in the case it is not, why Fibonacci-heaps is not a better pick than a regular Min-heap structure, when we use a sequence of Extract-min and Insert-operations?


texts:
In computation theory, when talking about the computability and complexity of a
problem, what is the definition of a problem?

How specific should a problem be? For example, can the followings
all be function evaluation problems?

evaluate $f$, where $f(x)=x^2, x \in \mathbb R$
evaluate any function in $\mathbb R^{\mathbb R}$.
evaluate any function in $Y^X$, where $X$ and $Y$ are any two sets.

Without restriction to the computability and complexity of a problem (or
even without restriction to computation theory), how is a problem defined?

Can the above examples in 1 all  be  function evaluation problems?

Thanks.


texts:
In RAID 6, there is a parity scheme that allows 2 concurrent disk failures. This requires 2 ‘syndromes’, one of which is simply XOR, as used for RAID 5's only parity. In trying to find out whether RAID 6 can support 3 or more parities, it has been disputed that there even exist any other parity syndromes.
    I don't understand the maths for computing RAID 6 parity or ‘syndrome decoding’ but I sort of make out that the 2 syndromes used in RAID 6 are just 2 of a very large group and that XOR is simply a special-case. Presumably the number of syndromes is something along the lines of an exponential function of the number of bits in a chunk (or other rapidly increasing combinatorial function such as factorial). I see something there about the bits being coëfficients of a polynomial, but this is somewhat over my head at the moment.
    If I'm correct that there are more than 2 parity syndromes, I'd like to know how to calculate the number of different syndromes for a given chunk size (or whatever parameters are required).


texts: Help figuring out how to write the English description of a turing machine?

texts:
So I generally understand how to follow a flow-diagram of a Turing Machine, but I'm going over how to write the "steps" in English and am having a bit of trouble. The problem is as follows: "Give the English description of a Turing machine that decides this language: {$1^{n}$$2^{n}$, $n > 0$}"

I understand that the string is basically: "there must be the same number of 1's and 2's in the string, and there are more than 0 1's and 2's (the string cannot be empty), but how would I write the English steps for this language? Could someone explain the process on how to break it down and write it?


texts: What is the difference between symbol recognition, classification and identification?

texts:
I've just wondered if there is a difference between symbol recognition, classification and identification.

What would you use when you have a hand-written symbol and you want to get the LaTeX code for it? Is that symbol classification, because you have about 1200 classes of LaTeX symbols? Or identification? Are some of those words synonyms? Which words are used more often?


texts: Sorting array containing elements from $\{1,\ldots,k\}$ in place in $O(n\log k)$

texts:
An array $a[1,\ldots,n] \subseteq \{1,\ldots, k\}$ is given, where $k < \sqrt{n}$.
Our goal is a project algorithm which sorts it in place and in time $O(n\log k)$.
We assume that $k < \sqrt{n}$ - otherwise $O(n\log k) = O(n\log n)$ - then we may use HeapSort.

We may assume that we know $k$.  I try to do it. The only thing that I can do is finding all $k$ distinct elements and bring them on beginning of array in $O(n\log k)$  - I use binary search.

However I have no idea how to solve it. Any ideas?


texts: Maximum Independent Set of special Directed Graph

texts:
I was given this special type of Directed Graph and was asked to find it's Maximum Independent Set.
Graph Properties :

Graph has $N$ vertices and $N$ edges
There can be no edge from a vertex $v$ to itself
Each vertex $v$ has only 1 outgoing edge and 0 or more incoming edges

I framed this problem as a linked list with potentially some cycles. So far I've tried a DFS approach, two Greedy ones and right now I am thinking of a DP one trying to convert the linked list to a Binary Tree by removing the cycles somehow.
All of the approaches below respect the fact that there can be no edges between vertices of the under construction independent set.So when a vertex is under consideration to be a member of it I check if it points to a vertex of the under construction independent set.
First Greedy approach :
Sort the vertices based on the number of incoming edges and keep taking the ones with the least incoming edges let's call them $v_1,v_2...$ as well as the ones who point where $v_1,v_2...$ do as they are basically free and so on.
Second Greedy approach :
Take the ones with no incoming edges let's call them $z_1,z_2...$ as well as the ones who point where $z_1,z_2...$ do as they are basically free as well and from there see which vertices have the most incoming edges and take the ones who point at them.
Both approaches seem to fail by 1 in some test cases.
As for the DFS one it was something like take 2 a time where in $v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4 \rightarrow v_5$ I would take $v_1,v_3,v_5..$ and so on.
I also tried prioritizing the ones with 0 incoming edges in the DFS approach but no luck and I think I am in the right direction but I am missing a small detail.
Any thoughts or insight would be really helpful.


texts: Multiple Variables in Asymptotic Notation

texts:
I am trying to understand the multiple variable definition of an asymptotic notation. Particularly the definition in Wikipedia. It's also discussed in Asymptotic Analysis for two variables? but I think the answer is wrong. At least it is just corrected in the comments and and referenced to a lengthy answer. What I look for is just the answer for my confusion of the example given here. Wikipedia says,

Big $O$ (and little $o$, $\Omega$, etc.) can also be used with multiple
variables. To define big $O$ formally for multiple variables, suppose
$f$ and $g$ are two functions defined on some subset of
$\mathbb{R}^{n}$.
We say $f(\vec{x})$ is $O(g(\vec{x}))$ as
$\vec{x} \rightarrow \infty$ if and only if $\exists M \exists C>0$ such that for all $\vec{x}$ with $x_{i} \geq M$ $\textbf{for some $i$}$ $|f(\vec{x})| \leq C|g(\vec{x})|$.
... For example, if $f(n, m)=1$ and $g(n, m)=n$,
then $f(n, m)=O(g(n, m))$ if we restrict $f$ and $g$ to $[1,
\infty)^{2}$, but not if they are defined on $[0, \infty)^{2}$, This
is not the only generalization of big o to multivariate functions, and
in practice, there is some inconsistency in the choice of definition.

What I don't understand is, if we only look for some $i$, why can't we use the domain $[0, \infty)^{2} $? For example, if I only take the $n$ variable to infinity ($i$ is 0 in this case), then shouldn't it be fine and $f(n,m) \in O(g(n,m))$? Shouldn't the definition be not for some $i$ bur rather for all $i$? Do I understand the notion of for some in the wrong way?


texts: Converting a recursive algorithm to a runtime function

texts:
void Sort(int A[], int left, int right)
{
    int p;

    if (left < right)
    {
        p = (right + left + 2)/3;

        Sort(A, left, left+p-1);
        Sort(A, left+p, left+2*p-1);

        MergeSort(A, left+2*p, right);

        Merge3(A, left, left+p, left+2*p, right);
    }
}

I need to convert this function into a mathematical expression in order to solve it's run-time complexity.

I know  that MergeSort()'s complexity is of $\Theta(n \log n)$ and that Merge3()'s complexity is of $\Theta(n)$.

I can't figure how to transform this into a recursive mathematical expression.


texts: Context free grammer for $L = \{a^i b^j a^n b^m \mid i + j = n + m\}$

texts:
Find a CFG for the following language:

$$L = \{a^i b^j a^n b^m \mid i + j = n + m\}$$

I'm not sure how I can do that context free. I know that I have to borrow one char from the left group for each char from the right group. but not sure how.


texts:
I'm reading "Sets for Mathematics" by Lawvere, and he uses the following metaphor at the end of section 1.3: "we will see...how any abstract set F of the right size can act as mappings between given abstract sets. (For example, in computers variable programs are just a particular kind of variable data.)"

The internet seems silent on these so called "variable programs". Has anyone heard of them/has an accessible introduction (at an introductory graduate level)? Extra bonus points if you can explain how this relates to sets and functions.


texts: Why are computable functions also called recursive functions?

texts:
In computability theory, computable functions are also called recursive functions. At least at first sight, they do not have anything in common with what you call "recursive" in day-to-day programming (i.e., functions that call themselfes).

What is the actual meaning of recursive in the context of computability? Why are those functions called "recursive"?

To put it in other words: What is the connection between the two meanings of "recursiveness"?


texts: What are some of the practical applications of functions that extract the exponent and mantissa of a floating point number?

texts:
I'm talking about functions such as Python's math.frexp() :

  math.frexp(x)

  Return the mantissa and exponent of x as the pair (m, e). m is a float
  and e is an integer such that x == m * 2**e exactly. If x is zero,
  returns (0.0, 0), otherwise 0.5 <= abs(m) < 1. This is used to “pick
  apart” the internal representation of a float in a portable way.

  https://docs.python.org/3.4/library/math.html

And:

  In some applications it is useful it obtain the mantissa and exponent
  of floating point numbers.
  http://www.technicalc.org/tiplist/en/files/pdf/tips/tip6_58.pdf

That said, what would be the usefulness of functions such as math.frexp() in real-world applications? What can I use it for?


texts: Merge sort: sorting and merging complexity $\Theta(n)$

texts:
So this is the Master theorem for Merge Sort:

$$ T(n) = 2T(n/2) + \Theta(n). $$

I am not able to understand why is the time complexity for sorting and merging $\Theta(n)$.

Is sorting $O(1)$ and merging $O(n)$?


texts: How to determine approximability of a problem when we don't know how good a solution is?

texts:
As far as I have learned, an approximation algorithm for an optimization problem

Runs in polynomial time, and
Whose cost can be bounded by a function of input in terms of distance from the optimal cost.

If we consider the optimization version of subset-sum problem, it says

  Given a set $A$ of integers, what is the maximum value of $sum(B) \le t$
  where $B \subset A$, $sum(B) = \sum{b\in B}$ and $t \in Z^+$

In this problem, we know that we search for a maximum value that is smaller than or equal to $t$. So, a solution $B_1$ is better than another solution $B_2$ if $\dfrac{sum(B_1)}{sum(OPT)} > \dfrac{sum(B_2)}{sum(OPT)}$, $OPT$ being the optimal subset.

Now, let us consider the WSN localization problem, which is defined as:

We have a set $A = \{1,2,\dots,n\}$ of $n$ points in $d$-dimensions. We only know the coordinates of some points, let us denote them with $B = \{b_1, b_2, \dots, b_m\}$ where $B \subset P$. By using the positions of the nodes in $B$, we aim to assign positions to the nodes in $A$. While doing this, we use the Euclidean distance graph $G = <V,E,W>$ that is given as input. In this graph, each node $i \in V$ corresponds to a point $i \in P$ and each edge $\{i,j\} \in E$ means that there is a distance measurement between the point $i$ and point $j$. The weights of an edge corresponds to the Euclidean distance between two points.

We use a unit disk graph (UDG) model. In a UDG, an edge $\{i,j\}$ exists if and only if the Euclidean distance $\delta_{ij}$ between $i$ and $j$ is smaller than or equal to a specific value $R$. That indicates if there does not exist an edge $\{i,j\}$, then $\delta_{ij} > R$.

We aim to assign coordinates to each node $v \in V$ considering their Euclidean distances. This process is called localization.

As the motivation is wireless sensor nodes, we assume that we cannot measure distances with 100% accuracy. Therefore, each distance $\delta_{ij}$ is altered by adding a value $\epsilon$ to model the environmental noise.
For any two points $i,j$ whose pairwise distance is $\hat{\delta}_{ij} < R$, the given distance is $\delta_{ij} = \hat{\delta}_{ij} + \epsilon$.

$\epsilon$ is up to $\pm P\%$ of the wireless range $R$ selected from a uniform random distribution.
Let us assume that we always can localize %100 of the nodes i.e. the input graph is localizable.
Our objective is to minimize the average localization error.
This is computed by $\dfrac{\sum\limits_{v \in V}||v_{est} - v_{act}||}{|V|}$, where $v_{est}$ is the estimated position of node $v$, $v_{act}$ is the actual position of node $v$ and $||v_{est} - v_{act}||$ denotes the Euclidean distance between two.

The optimal solution for any instance is clearly $\forall v \in V, v_{est} = v_{act}$ and the cost is $cost(OPT) = 0$.

In subset sum, we know how close we are to the value $t$ and can compare two solutions. In traveling salesman problem, we can compare the solutions by their costs. However, in localization problem, we cannot compare two solutions without knowing the actual positions, which is impossible by the definition of the problem.

My question is: Can we anyhow prove if WSN localization problem is approximable or not by not being able to know how good a solution is? Or is it completely irrelevant?

For further reading, here is the NP-hardness proof of the localization problem with noisy distances. This paper defines the formal theory of the same problem.


texts: Algorithm for finding connected components checking as few edges as possible

texts: Is there a good algorithm to find connected components in undirected graphs with at the lowest possible costs given as the total weight of the edges being checked?


texts: Is this sorting algorithm valid and able to run in O(range of input set) time?

texts:
I imagined a sorting algorithm that sorts an array in O(r) time, where r is the range. Is this already an algorithm (if so, which?), or have I made a mistake calculating the running time (probably).

Create an array going consecutively from the smallest element to the largest element.
Loop over the unsorted array and for each element mark the same element in the generated array. Since the list is sorted, we can jump to each element in O(1) time [number three is the third element in the generated array].
Remove all elements that are unmarked from the generated array.

If this can really run in O(r), then since for most datasets the range is not larger than the number of elements, this would be faster than merge sort or any other sorting algorithm.


texts:
I have a couple of questions based on how SAT solvers work. I understand that SAT solvers may employ any/all of the following techniques:

Randomness
Heuristics
Backtracking

SAT is just one example of an NP-complete problem. Is it common to use such techniques in conjunction to solve intractable problems? I normally see approaches to solving difficult problems in sections, like probabilistic algorithms or parallelism, but what stops them from being employed simultaneously?

Further to this, how is randomness achieved on a Turing machine? I mean by this pseudo-randomness, so is this possible on a Turing machine?

This is a slightly more specific question, but heuristic algorithms will have different meanings based on the problem. So if someone were to make a polynomial-time solver for another NP-complete problem like clique, based on heuristics, how would this also make SAT in P? Basically, certain methods of solving certain NP-complete problems will undoubtedly differ. How can this all at the end of the day reduce to the same problem? Can methods of solving an NP-complete problem be reduced to others?


texts:
In Khan Academy's RSA Encryption 2 video, I can't understand how they have got from

$$m^e\bmod N\equiv c$$
to
$$c^d\bmod N\equiv m\,.$$

The transcript says,

  01:39 some piece of information that makes it
  01:41 easy to reverse the encryption
  01:44 we need to raise $c$ to some other exponent, say $d$,
  01:48 which will undo the original operation applied to $m$
  01:51 and return the original message $m$.
  01:54 So both operations together, is the same as
  01:57 $m^e$ all raised to the power of $d$,
  02:01 which is the same as $m^{e\times d}$.

The person says if we want to reverse the function to give us $m$ (the encrypted message), we simply have to  raise $d$ to another exponent, $d$, and this reverses it.

Although I know this video isn't supposed to fully explain everything I don't understand how this is done. How can you just raise $c$ to some power and get the original message $m$. Is there some sort of proof or can someone explain it in more detail perhaps? By the way, I pretty much know nothing about encryption/ cryptography. I study CS at college (UK) AND was just watching due to curiousity.


texts: Infinite recognizable not decidable subsets

texts:
If L is an infinite ($|L|=|\mathbb{N}| $) decidable language, prove that it contains:
a) An infinite subset that is not recognizable
B) An infinite subset that is recognizable and not decidable
For the (a) I considered all the subsets of L, i.e., $\mathbb{P}$(L)
So $|\mathbb{P} (L)| = |\mathbb{R}|$ so that means that it exists $A \subset L$ that is not recognizable
(for there are not enough Turing machines to recognize them all)
If A were finite, then it would be decidable so it would be recognizable which would be a contradiction.
Therefore A is infinite and not recognizable.
For (b) I thought about B=L\A.
Then B is recognizable because A is not?
But I'm not really sure


texts: Counting subarrays where each number either doesn't occur or occurs odd number of times

texts:
We have given array $V$ of $N$ integers, we want to count the number of subarrays of the array such that each elements in the subarray either doesn't occur at all, or it occurs odd number of times.

Subarray is subset of array that is contiguous part of the array.

For example $N = 4, V = \{1, 1, 1, 2\}$. The result is $7$, and the subarrays we want to count are as follow: $[1, 1], [2,2], [3,3], [4,4], [1, 3], [1, 4], [3,4]$. Note that the intervals I wrote mean the part of the array starting at index $i$ finishing at $j$.

I coded the $O(N^2)$ algorithm but I know that there is faster way to do it. So, I tried to do some observations and to use XOR to count them, but I couldn't find anything that will work stable.


texts: Difference between multi-agent systems and distributed systems

texts: What is the difference between multi-agent systems (MAS) and distributed systems, in the context of control with agents?


texts: ANN with communication between nodes of same layer

texts:
I starting to learn about artificial neural network.

I already did some simple things for classification, with different hidden layer.

I would like to know :

Is there a way to create "communication" (synapse) between neurons of the same layer ?
If yes how will work the back-propagation ?

Thanks a lot


texts: What is the relation between differential-privacy mechanism and entropy?

texts:
Why do differential-privacy people care whether or not the noise function saturates the lower bound of Shannon entropy?

For example :
Laplace distribution that is used to model the noise function happens to saturate the lower bound of Shannon entropy under epsilon differential privacy constraints. See Theorem 8 in Yu Wang, Zhenqi Huang, Sayan Mitra and Geir E. Dullerud, Entropy-minimizing Mechanism for Differential Privacy of
Discrete-time Linear Feedback Systems for an example.

But what is the significance of this saturation?


texts: Efficient algorithms for identifying the diamond fork&join vertices and the diamond pairs in directed acyclic graph?

texts:
Given a DAG (directed acyclic graph) $G=(V,E)$ without multiple edges, i.e., edges with the same source and target vertices, we define:

A vertex $v_j \in V$ is a diamond-join ($\Diamond_J$) vertex if there exists some other vertex $v_f \in V$ such that there are at least two vertex-disjoint paths (except $v_f$ and $v_j$) from $v_f$ to $v_j$.

Furthermore, we call such a corresponding vertex $v_f$ above a diamond-fork ($\Diamond_F$) vertex. And, we call such a pair $(v_f, v_j)$ above a diamond ($\Diamond$) pair.

An Example:
In the figure below,

$E$ and $F$ are $\Diamond_J$ vertices.
$A$ and $C$ are $\Diamond_F$ vertices.
$(A,E), (A,F)$ and $(C,F)$ are $\Diamond$ pairs.

The problems are:

  How to identify all the $\Diamond_J$ vertices?
  How to identify all the $\Diamond_F$ vertices?
  How to identify all the $\Diamond$ pairs?

The algorithms should be as efficient as possible. For example, are there linear algorithms, i.e., in $\Theta(n + m)$, for them, where $|V| = n, |E| = m$?

My Thoughts:

The first problem is easy: Run DFS on $G$ and the vertices pointed to by cross edges are the $\Diamond_J$ vertices.

I do not know how to solve 2&3 efficiently.

Edit (2016-05-11): I accept the answer by @Chao Xu which solves the third problem in $O(nm)$ (I think it is correct; please peer review it). I am still open to possibly more efficient algorithm for the third problem, like $O(n+m)$.


texts: Is there any neutral element for the cryptographic hash function SHA256? (or its variants)

texts:
My question is
Is is possible to compute a string given that after applying a SHA256 function the result is the same string?


texts: closure property violated by palindrome language

texts:
It is well established that palindrome language is non-regular. The one way to prove it is by means of pumping lemma. The other way is violating the closure properties of regular language. The strategy seems that pick a regular language and intersect with language L under consideration. If the result is a non-regular language, then L is non-regular. Can I argue that a closure properties of a non-regular language like palindrome do not form a Boolean algebra? Is it this violation that make palindrome a non-regular
(context-free) language?
Moreover, please suggest some pointers where I can study palindrome language in greater detail.


texts: Impossible recurrence relation help with masters theorem, plus evaluation of complexity

texts:
I had an exercise to solve a recurrence relation in my exam, I think it was a tricky question but I am not 100% sure.

The recurrence was $ T(n) = 2*T(n) + \sqrt{n} +42 $, it was specifically asked to be solved using the master theorem, and I wrote it cannot be solved using master theorem because it requires for b>1.
Do you think is correct?

After that I had a small piece of code to evaluate, after a look at it I decided it was $ O(n^3) $

    for i in range(1,n):
      j = i+1
      while(j/n<=n):
        k=1
        while(k<=n):
            constantFunction(4) # a function that executes in constant time
            k=k+3
        j=j+1

In my opinion the function going from 1 to n, makes the while(j/n<=n) always be <=n as $ n-> infinity $, which makes the other while inside execute until k<=n, k will grow fast and soon that while loop makes me wonder, will it stop ? I mean let's assume n goes to infinity, then k will grow, but not as much as n, so it'll be $O(n^3)$. Am I right?

Thank you


texts: Dividing 2 integers with some constraints

texts:
This a problem i came across while practicing binary search. Here is the problem:

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.

Note:

Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store
      integers within the 32-bit signed integer range: [−2^31,  2^31 − 1]. For
      the purpose of this problem, assume that your function returns 2^31 − 1
      when the division result overflows.

A Brute force Solution is that subtract the dividend with the divisor till it is greater and the number of subtractions is the result. But it is giving Time Limit Exceeding error.

How to solve the problem efficiently or using Binary Search ??

Also provide the time complexity as well.


texts: How to prove a given sequence of x86 instructions is shortest possible?

texts:
Say we want to find a shortest possible sequence of x86 instructions to move the $9^{th} - 16^{th}$ bit of the $eax$ register to the $24^{th} - 31^{th}$ bit of the $ebx$ register without changing the other bits of the $ebx$ register, where the least significant bit is defined to be the $0^{th}$ bit.

An obvious solution is:

ror eax, 1
rol ebx, 8
mov bl, ah
ror ebx, 8

But how do I prove this is the shortest possible? Is there a nice way to do it? If not, is there a nice piece of FOSS software to brute force it?


texts: Can you write an algorithm that can generalize another algorithm?

texts:
Can you write an algorithm which can take in a given function/algorithm, and produce a distribution of generalizations of the function at hand? One such simple example of generalization might mean the generalization from the factorial function to the gamma function, or the generalization of the irrationals to the reals.
Is such an algorithm ultimately incomputable, and thus reducible to the Halting problem?


texts: Why is there so little literature on partial order production?

texts:
Please excuse or improve the poor title of this question.
My question is rather undirected, but I guess I am trying to find out if I might be missing a keyword for my problem.
So there is plenty of work on sorting algorithms.
Sorting is usually understood as creating a / the one correct total order given a set of elements X and their pairwise relationship x >= x' for all x in X. Or  actually >= is the total order and the task is to create a sequence or directed graph s.t. x comes after x' iff x>=x'.
Now you want to do the exact same thing, only >= does not define a total order over X, but only a partial order.
This seems like a very straightforward generalization that I can only imagine is required quite often. Still, under the term partial order production, I find only very little literature on the topic / task.
Am I missing something?
EDIT: Alternative Formulation
Given a set of elements X and a function f that returns the relationship between any two elements x,x' in X. Create a DAG with an edge x->x' if the relationship is >= and x'->x if the relationship f((x,x')) is <. Then create the transitive reduction of the DAG.

f(x,x') is either >= or <. This is normal sorting.

f(x,x') is either >=, < or ? (not comparable). This is partial order production.

I would say both are clearly ordering problems, given the relationship function f (the order) and the elements X to order.
Still you find so much on case (1) and hardly anything on case (2).


texts: Converting this DFA to RE using the Brzozowski Algebraic Method

texts:
Hello people, I'm trying to convert this DFA to RE using the Brzozowski Algebraic Method.
(DFA created with JFlap)

My Attempt
Write down equations

R1 = bR1 + aR2 + ɛ

R2 = bR2 + aR3

R3 = bR2 + aR1

Eliminate equal Rx's from RHS

R1 = b*aR2 + b*

R2 = b*aR3

New equations

R1 = b*aR2 + b*

R2 = b*aR3

R3 = bR2 + aR1

Substitute R2 into R3 and eliminate R3 from RHS

R3 = bb*aR3 + aR1

R3 = (bb*a)*aR1

Substitute R3 into R2

R2 = b*a(bb*a)*aR1

New equations

R1 = b*aR2 + b*

R2 = b*a(bb*a)*aR1

R3 = (bb*a)*aR1

Substitute R2 into R1 and eliminate R1 from RHS

R1 = b*ab*a(bb*a)*aR1 + b*

R1 = (b*ab*a(bb*a)*a)*b*

Answer

RE = (b*ab*a(bb*a)*a)*b*

Issue(?)

The past exam paper answer is: b*(ab*a(bb*a)*ab*)*

My calculated answer is: (b*ab*a(bb*a)*a)*b*

Are these 2 answers equal or have I done something wrong?

EDIT: The answer is correct even in the form I have provided; the textbook answer has gone a step forward having used the shifting rule to achieve its format.

Here are some useful rules for simplifying RE's:

Shifting Rule: E(FE)* = (EF)*E
Denesting Rule: (E*F)*E* = (E+F)*


texts: Is there any mechanism where the kernel portion of an OS in memory may also be swapped?

texts:
I'm recently learning the part of I/O buffering of operating system and according to the book I use,

  When a user process issues an I/O request, the OS assigns a buffer in the system portion of main memory to the operation.

I understand how this method is able to avoid the swapping problem in non-buffering situation. But is it assumed that the OS buffering created for the process will never be swapped out?

To extend my question, I was wondering if there is any mechanism where  the kernel portion of an OS in memory may also be swapped?


texts:
I am reading the lecture notes and have a question. I am trying to understand the beginning of Section 3 on page 2.

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

Naive solution: $O(\log m)$ bits, exact solution.

I don't understand why it is not $O(m)$ bits but $O(\log m)$ bits. Any help would be greatly appreciated.


texts: Sufficient condition for a complexity class's closure under NP-reductions?

texts:
Let us say that there exists a $\mathsf{NP}$-reduction from a problem $A$ to another problem $B$ when there exists a non-deterministic, polynomial-time Turing machine $T$ such that for each $a \in A$, one of the possible outputs of $T(a)$ is in $B$ (and conversely, if one output $T(a) \in B$, then $a \in A$). $\mathsf{NP}$ reductions are discussed with relevant citations in the opening pages of this article.
A complexity class $\mathcal{C}$ is closed under $\mathsf{NP}$-reductions, if whenever a problem $A$ can be $\mathsf{NP}$-reduced to some $B \in \mathcal{C}$, we have $A \in \mathcal{C}$. (I think) equivalently, the class $\mathcal{C}$ is closed under $\mathsf{NP}$-reductions if whenever $B$ is $\mathcal{C}$-complete and there exists a $\mathsf{NP}$ reduction from $A$ to $B$, there also exists a polynomial-time (deterministic) many-one reduction from $A$ to $B$.
Of course, any class $\mathcal{C}$ that is closed under $\mathsf{NP}$-reductions must include $\mathsf{NP}$, but it isn't obvious to me that any class containing $\mathsf{NP}$ is closed under $\mathsf{NP}$-reductions. Indeed, on p. 545 of this article it is claimed that closure under $\mathsf{NP}$-reductions is nontrivial and that every class in the series $\mathsf{NP} \subseteq \exists\mathbf{R} \subseteq \mathsf{PSPACE}$ is closed under $\mathsf{NP}$-reductions.
Here is my question: What is a non-trivial condition on a complexity class $\mathcal{C}$, such that when $\mathcal{C}$ satisfies that condition, it is closed under $\mathsf{NP}$ reductions?


texts: Matrix chain multiplication: Greedy approach

texts:
some suggested a thread in which the algorithm multiplies the 2 matrices with lowest values first. Mine is different: it divides by parenthesis the 2 matrices. And continues to the next section.

The problem is: finding the most efficient way to multiply a series of matrices together, using an algorithm of some sort, and comparing these algorithms to find the most efficient one.

The dynamic algorithm approach works at a time complexity of theta of N^3.

My question is, what is the runtime of this algorithm:

A= 5x2
B= 2x7
C= 7x3

1) First, find the matrix with the lowest dimension ( a matrix which has the lower number from the rows or columns of all the matrices).

*If the lowest number is in the last dimension, it is the same like putting the entire sequence in parentheses.

*There is no guidance as to what to do if the lowest number appears twice in the sequence, so I suggest the algorithm just takes 1 randomly.

2) Then divide the sequence to 2: (A)(B•C).
The parentheses will close on the matrix from the right and open on the next matrix. This way they will divide the series to 2 parts.

Then repeat the process for the 2 parts. Stop when you have 1 (or 2) matrices in the sequence.

Is this algorithm optimal?
It has to be better than N^3 (the usual algorithm)


texts: How to read this inductive language definition?

texts:
A language $L$ is defined recursively according to the following rules:

$λ ∈ L$
If $w ∈ L$, then $bw ∈ L$ and $waa ∈ L$

I am not sure if strings from this language should mix from this definition. Would strings only consist of $bbbb$ and $aaaa$, or can it also consist of $bbaa$, $aabb$, and so on?


texts: What is the intuition behind the way of reading off a dual optimal solution from simplex primal tabular in CLRS?

texts:
Section 29.4 "Duality" of CLRS (3rd Edition) describes the way of reading off an optimal dual solution from the last slack form of the primal as follows:

  Suppose that the last slack form of the primal is
  $$
\begin{align}
z &= v' + \sum_{j \in N} c'_j x_j \\
x_i &= b'_i - \sum_{j \in N} a'_{ij} x_j, \; i \in B.
\end{align}
$$
  Then, to produce an optimal dual solution, we set
  $$
\overline{y_i} = \begin{cases}
  - c'_{n+i} & \text{if } (n + i) \in N, \\
  0          & \text{otherwise}.
\end{cases}
$$

I am able to follow the proof of a later Theorem (Theorem 29.10: LP Duality) to convince myself that this $\overline{y_i}$ is indeed an optimal dual solution.

However, what is the intuition behind the way the optimal dual solution is constructed? I notice that each non-zero $\overline{y_i}$ corresponds to a tight constraint in the optimal primal solution. Is this fact helpful to understand the optimal dual solution?


texts: Find shortest path that visits all nodes in a given set of nodes

texts:
Suppose I have a graph $G$ and a set of target nodes $S = \{A_1, ..., A_n\}$. I'm attempting to find the shortest path that visits each target node, in order, without visiting the same node twice.

For example, consider the following:

I have attempted to solve this by first performing a breadth-first search to find the shortest path from A to B, then from B to C, and so on, taking care to exclude any paths already found at each iteration.

This greedy solution works for most inputs, but in some case it will fail to find a solution, as the shortest path between two target nodes may end up blocking the complete path.

Aside from a brute-force approach, is it possible to find the shortest path that visits all of the target nodes, and is guaranteed to find such a path if one exists? Any suggestions on how to proceed?


texts:
The worst case height of AVL tree is $1.44 \log n$. How do we prove that?
I read somewhere about Fibonacci quicks but did not understand it.


texts: Efficiently partition tree into clusters of similar diameter

texts: I am looking for a way to split a tree into $k$ clusters so that the cluster with largest diameter is as small as possible. All edges have the same length.  I'm hoping for an algorithm that can handle arbitrary trees (with arbitrary branching factor), not just binary trees.


texts:
Im trying to make an invariant for this Z schema about routes.

1) The invariant should express that each route should contain at least 20 different places. First of all i thought of doing a universal quantification such as:

∀x : ran routes • ( #x>20 ∧ x ≠ x')

However i'm really not sure if thats correct that implying 20 different places.


texts: Can I simplify successive XOR operations?

texts:
I'm doing an online programming challenge where successive XOR operations are used (from codewars.com, if you don't want to create an account, here are the instructions).

We have a rectangle of known dimensions where every value of column and row (zero-indexed) are XOR-ed in order to create a value. Then, we must compute the sum of every value of that rectangle.
(i.e. for a rectange of 8 columns & 5 rows, the first value would be 0 ^ 0 = 0, then 0 ^ 1 = 1, etc. until 7 ^ 4 = 3, then the sum of every value would give 105, which is the result)

I've tried different approach to this problem, but every one of them end up being too slow and not enough efficient. The naive solution is of time complexity $O(N^2)$, which becomes too slow when we're working with a lot of values.

Here would be the function to compute the value of 1 row.
(x is the number of columns & y is the number of the current row)
$$
f(x,y) = (0 \oplus y) + (1 \oplus y) + (2 \oplus y) + (3 \oplus y) + .. + ((x - 1) \oplus y)
$$
So the whole rectangle would be that function from 0 to y - 1 for the y value.

So my question is: Is there a way where I can simplify a function like that to gain efficiency ?


texts: Does a Hadamard Gate have uses outside of pure and evenly mixed states?

texts:
The standard usage cases for the Hadamard gate seem to be passing a pure $|0\rangle$ or $|1\rangle$ state in to get an even amplitude (probability) mixed state which has either matching or mismatching phase.

The other use of course, is to take such an even amplitude mixed state, pass it through the Hadamard gate, and get back a pure $|0\rangle$ or $|1\rangle$ state.

This of course scales up to multiple qubits.

Are there any other usage cases for the Hadamard Gate?  I'm wondering if say you had an uneven amplitude qubit, would passing it through a Hadamard Gate do anything useful?  Or the same question with multiple qubits, that had varying amplitudes of states.

Thanks!


texts: interference graph: assigning variable to itself

texts:
I'm studying the theory behind compiler design, and was assigned with building an Interference graph for a certain code 3-address code.
We were taught to first divide the code into blocks (according to GOTOs), and draw lines that represent a variables lifeline.
I am not sure on a = a op c (that is, same variable is both read and assigned in same command).
I am following this examples, which sadly, has a typo that makes it hard to understand this very end-case. Here, a=a+b+c, so a is both used and assigned.
I have initially treated that with no special care (logic being "i know some interpreters can read RHS before LHS"), but now I am not quite sure. My question really:I think perhaps the example should have mark a's line starting from the read() command, end it in the a=a+b+c but also re-draw the line. This way an extra register will temporarily hold a's value before assigning it back to a. Is that correct?


texts: Question regarding terminology used to describe Benes networks

texts:
I'm studying a routing problem on a cyclic butterfly network. The paper I am reading states that two properties of the cyclic butterfly network make it efficient for the routing algorithm it describes. I'm new to this subject, and I'm struggling to understand the first property, which is:

"(1) It embeds a Benes network - meaning that if we traverse the columns and back any permutation of the row labels can take place without collisions"

It adds that this is trivially true for a square grid. In this context do collisions mean collision of packets of information? Why is this trivially true for a square grid, but not the cyclic butterfly network?

Kind regards

S


texts: Are there algorithms for which we cannot determine if they ever halt?

texts:
My understanding of the halting problem in layman's terms is that there is no algorithm which will accept an arbitrary program as input and return true if it halts and false if it does not.

For a Turing machine does the question, "Does this Turing machine halt for all inputs?" always have an answer in the first place?

E.g. the algorithm "If this machine halts, then loop. Otherwise halt." seems to suggest that the answer is no. Is there something wrong with this example? Is there a canonical example?


texts: Empirical studies about benefits of Q&A sites for programming

texts:
I'm looking for empirical papers which investigate if a user can benefit from Q&A sites like Stack Overflow. I welcome any papers related to this topic, e.g:

an experiment, investigating if a specific task can be executed faster,
an analysis, investigating if a user understands the solutions on Q&A sites or if he just does copy&paste without thinking about it,
a comparative analysis of the code quality of users with access to Q&A sites in contrast to users without internet access (but just offline documentation of APIs).


texts:
I am reading "Neural Networks and Learning Machines" and in Chapter 11 the book covers Boltzman machines and it is stated "the network [Boltzmann machine] can perform pattern completion", but does not show how this would be done in practice, or how a Boltzmann machine could be used at all.

As I am more the "hands-on" person, and the book is more on the theoretical side of science. I am currently looking for an practical example/paper/article on an Boltzmann machine, maybe even a simple (therefore small) educational implementation.

I'd appreciate any link/paper/article covering the (non-restricted) Boltzmann machine in an understandable ("hands-on") way.


texts:
Wikipedia's article Cyclic redundancy check states that for the same n (bits) there are multiple CRCs possible with different polynomial. Then it lists this Best CRC Polynomials article that gives some variations with different polynomials. I am looking to implement a simple CRC-8. What should be my criteria for picking one polynomial over another?

I assume that it boils down to selecting the Hamming distance, but how is that related to my problem at hand? How do I pick the correct/best Hamming distance for best detecting possible errors in my case (and in what terms should I describe my case)? For example, will the choice depend on the media for storing/transmitting data or other physical factors or something else?


texts: Is it correct to say that an algorithm ALG is an O(1)-approximation algorithm?

texts:
I read it in not only one place. People write theorems of the form:

  Theorem: ALG is an O(1)-approximation algorithm

It means that ALG is a constant factor approximation algorithm but is it safe to say that? I mean it misleads. Why am I asking?

Because, many problems I know of do not have an $\alpha$-approximation algorithm where $\alpha<\gamma$, unless P=NP. For example, the k-center problem does not have an $\alpha$-approximation algorithm where $\alpha<2$, unless P=NP. Well, there is a simple greedy algorithm that is 2-approximation algorithm for the k-center problem. Can we say that this greedy is O(1)-approximation algorithm for the k-center problem? I mean, if it is an O(1)-approximation algorithm for the k-center problem, it is, for example, an 1.9-approximation algorithm, no?


texts: Is there a direct way to obtain the RE for the handle-finding DFA of a grammar?

texts:
LR parser for a (CFG) grammar uses a handle-find automaton (which is a DFA) to find the handles. Such automata can be constructed by computing the canonical collection of sets of LR(0)/LR(1) items.
Is there a way to obtain the RE of the handle-find automaton, directly from the given grammar?

Example: Below are the grammar for balanced parentheses and its handle-finding DFA (from the book: Engineering a Compiler).


texts: Particular function communication complexity computation

texts: Consider a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$. If $f$ satisfies $f(\bar{0})=0$ where $\bar{0}$ is vector of $0$, $f(x)=1$ with every $0/1$ vector of hamming weight $1$, then communication complexity of function is $\Omega(n)$. This is claim $4.23$ in Jukna's book. If $f$ satisfies $f(\bar{0})=0$ where $\bar{0}$ is vector of $0$, $f(x)=1$ with atleast $r$ number of $n$ of $0/1$ vectors $x$ each of Hamming weight $1$, then is communication complexity of function $\Omega(r)$? Could this possibly have truth?


texts: How center the eyes of human face at specific pixels?

texts:
I am facing a problem with processing some frontal facial images.

I need to adjust the centers of the eyes (irises) to be at certain specific pixels in the image. In other words, i need to transform the image until the centers of the eyes are at specific pixels.

Can anyone help me with this problem, an algorithm, technique, ...etc. that might solve this problem ?

Thanks,


texts: I need to present a regular expression for the following languages:

texts:
1.
L2 = E{0,1)

All the words in L2 with equal number of 0's and 1's and every prex of w has at most two more of either
0's or 1's.

2.
All words that does not contain “bbb” as substring.

i think this is :( e + b + bb)(a + ab + abb)*

Thanks in advance!


texts:
I found a question.

  Least number of temporary variables required to create three address code in static single assignment form for the expression $p+q*r-s/(q*r)$

My attempt:

  $t_1 = q*r$
    $t_2 = s/t_1$
    $t_3 = p + t_1$
    $t_4 = t_3 - t_2$

So, I got $4$ variables but their answer is $5$. Am I missing something? Where I am being wrong?


texts: Smallest real root of a polynomial in a range

texts:
I'm trying to numerically find the smallest real root of a polynomial in a given range. My initial plan was to shift the polynomial so that the bottom of the range was 0, expand the resulting expressions to find the new coefficients, then use the Jenkins-Traub algorithm until it finds the first (smallest) root or increases out of the range. However, the Wiki page says that it only generally finds the roots in increasing order, so it sounds like that's not guaranteed. Is there a way to guarantee finding the first root? If not, what is the most efficient way to solve the problem?

Finding all the roots then sorting is possible, but is inefficient as the degree of the polynomial gets larger, and, I hope, unnecessary. The bisection method is another common algorithm, but consider the polynomial:
$-5x^2+5x-1$
with a range of (0,2), which would cause the angle bisection to fail. The best answer is one that guarantees success with the fastest time for a reasonable degree polynomial (less than say 10).


texts: I want to ask what is the cardinality of a weak relationship like the loan payment relationship shown below, will be ? I am guessing it should be many to many.


texts:
Suppose that you have a large dictionary with spellings and pronounciations of foreign words, and you want to find a set of pronunciation rules. They should have the simplest form: a sequence of letters to a sequence of sounds.

For example, in French, c [k], i [i] and ci [si].

The rules may be long: tion [sjɔ̃] (instead of [tjɔ̃]).
They may be rare: à [a] is used only in a dozen of words.
They may be both: aill [aj] (as a-ill, instead of ai-ll [ɛl]).

Fortunately, such rules are rare enough: for the most part, the letters are pronounced by itself, even most of them in complicated rules. For examples, cercle [sɛʀkl] instead of [kɛʀklɛ]: the algorithm should notice the corresponding sounds in the middle of the word.

Maybe, there is a standard algorithm to extract candidates for such rules? I would like to have an explicit list of rules, rather than a method predicting  pronunciation.


texts: NP-complete problem 3-SAT, is there a difference in complexity between just providing yes/no without exact solution

texts:
The 3-SAT problem is NP-complete, meaning that no known algorithm can provide an exact solution in polynomial time, while a solution can be tested very quickly in polynomial time.

My question is, if asking for an algorithm that only provides yes/no, or solvable/not solvable, without providing an exact solution of the 3-SAT formula, will this result in another complexity class?

The reason I have in mind of asking this, is a similar situation when looking for prime numbers and factorizations. Where it is known that it's much easier to test if a number is a prime number yes/no, than to find an exact prime factorization of a number.


texts: Examples of algorithms with low spacetime complexity

texts:
When running a data center, one of the cost metrics you might care about is "ram seconds". For example, an algorithm that holds 1 MB of memory for five minutes consumes 300 million ram seconds. A datacenter only has so many ram seconds in a day.

The spacetime complexity of most algorithms, i.e. their cost in ram-seconds, is just their time cost multiplied by their space cost. But suppose an algorithm had an $\Theta(n)$ time startup phase that required $\Theta(n)$ space to compute a couple required details, followed by an $\Theta(n^2)$ time serial computation that only needed $\Theta(\log^2 n)$ space. This algorithm's spacetime complexity would be $\Theta(n^2 \log^2 n)$ instead of the $O(n^3)$ you'd get by multiplying its time complexity by its space complexity.

Are any real life, practical examples of algorithms with spacetime complexity lower than their time complexity times their space complexity?


texts: Is Wikipedia's formal definition of NP correct?

texts:
Wikipedia's formal definition of NP based on deterministic verifiers states:

  A language L is in NP if and only if there exist polynomials p and q,
  and a deterministic Turing machine M, such that

  For all x and y, the machine M runs in time p(|x|) on input (x,y)
  For all x in L, there exists a string y of length q(|x|) such that M(x,y) = 1
  For all x not in L and all strings y of length q(|x|), M(x,y) = 0

I'm not an expert in the field but the first bullet point leads me to think that M must run in time p(|x|) regardless of the size of y, which doesn't seem to be true, at least if M gets to read y completely. What if |y| > p(|x|)?

Is the first bullet point of the definition correct? Shouldn't it be

  For all x and y, the machine M runs in time p(|x|+|y|) on input (x,y)

Can you point me to an authoritative source with the original definition of NP based on deterministic verifiers?


texts: How can I optimize 3 variables in order to maximize the end product?

texts:
I am in the process of making a cryptocurrency trading bot. Currently, I am doing backtesting over a period of 7 months in which I provide a portion of historical data as if it were in real-life.

By modulating 3 variables: decision threshold, maximum % gain per trade, and stop loss, I want to find the best input values in order to maximize the amount of ending money I have at the end of the backtest.

What would be a good way to go about this? Currently, I'm running each backtest, and changing only 1 variable, but it seems like a slow process and I feel like there has to be a better way to do it. I've heard about neural networks, but I'm not 100% sure this would be a good scenario to apply that here.


texts: Algorithm to find exactly two sets of numbers that have the same sum

texts:
I am searching for the most efficent implementation of a specific algorithm:

Assume you have a set of positive integers, for example:

X = [1,1,2,3,3,6,8]

The aim is to find exactly two sets (containing together all elements of X), so that the sum of all elements of the one is equal to the sum of the other.

So for example a solution would be (there can be more than one solution of course, or no solution):
A = [1,2,3,6]
B = [1,3,8]

(Sorry if my wording is wrong, just a curious developer and no computer scientist)


texts: How to modify the following Dijkstra/ Uniform-cost search to return the result for all end points?

texts:
I know there is a lot of code out there that does this, but in particular, I'm trying to modify the following code to not just return the goal node/ one end point, but all endpoints. How do I go about it? I tried thinking of keeping a seen/visited set, but that seems redundant and kills the whole point of the reached map.
def best_first_search(problem, f):
    "Search nodes with minimum f(node) value first."
    node = Node(problem.initial)
    frontier = PriorityQueue([node], key=f)
    reached = {problem.initial: node}
    while frontier:
        node = frontier.pop()
        if problem.is_goal(node.state):
            return node
        for child in expand(problem, node):
            s = child.state
            if s not in reached or child.path_cost < reached[s].path_cost:
                reached[s] = child
                frontier.add(child)
    return failure


texts: Is computer science really a branch or sub-branch of physics?

texts: Given that a computer is basically an electronic machine, is computer science really a branch of electronics, which is in turn a branch of physics?


texts:
$$C \to A B C \mid A$$

Obviously has the same FIRST(C) for the both productions.

But how can this be left-factorised?

Tried:

$$C \to A B C'$$
$$C' \to A C \mid \varepsilon$$

The FIRST sets are disjoint, but is this correct?

Should $B \to \varepsilon$ (or $C \to \varepsilon$) be added as well, so that it handles $A B A$?


texts: Find all Eulerian cycles in a directed graph

texts:
I am trying to create an algorithm that can find all Eulerian cycles in a directed graph. I was able to make an algorithm that can find one cycle in the graph, but I don't know how to find all the cycles. Searching around I found that I had to use BEST theorem somehow.

def eulerian_cycle_from(graph: Dict[str, List[str]], path: List[str]) -> List[str]:
    """Generate a new cycle from the tip of the path.

    This function will add all possible circles still in the graph it can find
    from nodes in the path to the path and return the path.
    Calling itself with smaller an increasingly smaller graph
    """

    node = path.pop()
    edges = graph[node]

    backtrack = []

    # Follow path
    while edges:
        path.append(node)
        node = edges.pop()
        edges = graph[node]

    # Backtrack to see if there is still a node with edges in current path.
    while True:
        graph.pop(node, None)
        backtrack.append(node)

        if not path:  # We completed cycle, could not find more free edges.
            return backtrack[::-1]

        node = path.pop()

        if graph.get(node):  # This node still has edges.
            # Augment path with a cycle from that node and add the backtrack
            path = eulerian_cycle_from(graph, path + [node])
            return path + backtrack[::-1]


texts: What's the possibility of random guessing a youtube's video ID

texts: Let's say i make a program that produces an eleven character long ID like youtube does and tries to find a valid video in youtube. What's the actual possibility that it's going to produce a valid ID corresponding to a real video and also an unlisted one??


texts: If the virtual address space can be larger than the physical address space, how are the address mappings stored in memory?

texts:
Let's say we are working with a system that has 40 physical address bits. The total physical address space (assuming byte-addressable memory) is $2^{40}$ bytes, or 1 TiB. And if virtual addresses are 48 bits in length, that means there are more addresses available to virtual memory than there are locations in physical memory.

This makes sense to me, because the "excess" addresses could refer to hard disk locations as well. However, what I don't understand is how the translation between virtual and physical addresses occurs. I assume there is a mapping stored somewhere which links VAS locations to the physical locations. If there are more virtual address locations than physical locations, how can all of these mappings possibly be stored in memory? At minimum you would need 48 bits to store each virtual address, and then another 40 to store the physical location it maps to. So obviously you cannot just store a 1:1 mapping of each virtual address to its physical counterpart, as mapping every location would take more memory than physical memory itself.

What exactly am I missing here?


texts: For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time?

texts:
For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time or is there a computable function $f$ such that every problem that can be solved in $O(f(n))$ can also be solved in $o(f(n))$ time?

This question popped into my head yesterday. I've been thinking about it for a bit now, but can't figure it out. I don't really know how I'd google for this, so I'm asking here. Here's what I've come up with:

My first thought was that the answer is yes: For every computable function $f$ the problem "Output $f(n)$ dots" (or create a string with $f(n)$ dots or whatever) can obviously not be solved in $o(f(n))$ time. So we only need to show that it can be solved in $O(f(n))$ time. No problem, just take the following pseudo code:

x = f(n)
for i from 1 to x:
    output(".")

Clearly that algorithm solves the stated problem. And it's runtime is obviously in $\Theta(f(n))$, so problem solved. That was easy, right? Except no, it isn't because you have to consider the cost of the first line. The above algorithm's runtime is only in $\Theta(f(n))$ if the time needed to calculate $f(n)$ is in $O(f(n))$. Clearly that's not true for all functions1.

So this approach didn't get me anywhere. I'd be grateful for anyone pointing me in the right direction to figure this out properly.

1 Consider for example the function $p(n) = \cases{1 & \text{if $n$ is prime} \\ 2 & \text{otherwise}}$. Clearly $O(p(n)) = O(1)$, but there is no algorithm that calculates $p$ in $O(1)$ time.


texts: Min weighted edge cover: don't follow proof in Schrijver

texts:
I'm reading section 19.3 of Combinatorial Optimization by Schrijver where he details an algorithm for finding the min-weight edge cover. His method works for general graphs, but I'm particularly interested in bi-partite graphs. To find the min-weighted edge cover of a graph $G=(V,E)$ with a weight function $w: E \to R$, he first defines a clone graph, $\tilde{G} = (\tilde{V},\tilde{E})$. He then defines a larger graph, $G'=(V',E')$ whose set of vertices, $V'$ is the union of $V$ and $\tilde{V}$. The edges, $E'$ and weight function $w'(E')$ are as follows:

$w'(e)=w'(\tilde{e})=w(e)$ for $e \in E$
$w'(v,\tilde{v})=2\mu(v)$ for each $v \in V$ where $\mu(v)$ is the minimum weight edge of $G$ incident on $v$.

Now, we construct a minimum weight perfect matching, $M$ for $G'$ and this yields a minimum weight edge cover $F$ for $G$ once we replace any edge $v\tilde{v}$ in $M$ by an edge $e_v$ of minimum weight of $G$ incident on $v$.
Now, for the proof that this works, the author notes that $w(F)=\frac{1}{2}w'(M)$. So far so good.
Then, he states that any edge cover $F'$ for $G$ gives by reverse construction a perfect matching $M'$ in $G'$ with $w'(M')\leq 2w(F')$.
This is the part I don't understand. How does one go about constructing this new perfect matching, $M'$ and further prove the inequality?


texts: Which algorithm is used for generating random permutations in shuf command in linux


texts:
I was reading through this paper, "Priority Queues and Dijkstra's Algorithm" by Mo Chen et al., which suggests using Dijkstra's without edge relaxation, but to rather to just insert new nodes. Please see the pseudo code listed on the right-hand side below, which is taken from page 16 of that paper.

But to me the code looks wrong. I think the comparison should be
k <= d[u]

and also the update of the d[u] in the next line seems redundant to me. I think the delete-min operation can never return a vertex with distance label k which is strictly less than d[u] since whenever a vertex distance pair is inserted into the priority queue the distance array d is updated. Am I correct in assuming that this is a mistake in the paper?


texts: Weighted Matching with multiple assignments and min assignments

texts:
I need to do a weighted matching between two sets (say students and professors). The set of students is much larger than set of professors. So multiple students can be matched to professors. However, each professor also has a minimum number of students he needs. So even though all students maybe matched best with one professor, some need to distributed amongst the rest, as long as they can be matched of course -- since not all professors and students will have edges between them.

Standard Bipartite matching won't work since they match one to one. Max Flow won't work since they don't consider weights.


texts: BFGS vs L-BFGS -- how different are they really?

texts:
I am trying to implement an optimization procedure in Python using BFGS and L-BFGS in Python, and I am getting surprisingly different results in the two cases. L-BFGS converges to the proper minimum super fast, whereas BFGS converges very slowly, and that too to a nonsensical minimum.

QUESTION: From my readings, it seems to me that BFGS and L-BFGS are basically the algorithm (quasi-Newton methods), except that the latter uses less memory, and hence is faster. Is that true? Otherwise, if they are more different, then how so?

Ultimately, I want to figure out if the difference in performance is due to some differences in the actual algorithms, or due to their implementation in the python SciPy modules.

EDIT: I am adding some data to support my claims of divergent behaviour from the two algorithms.

 RUNNING THE L-BFGS-B CODE

       * * *

Machine precision = 2.220D-16
N =          147     M =           10
This problem is unconstrained.

At X0         0 variables are exactly at the bounds
At iterate    0    f=  2.56421D+04    |proj g|=  1.19078D+03
At iterate    1    f=  2.12904D+04    |proj g|=  1.04402D+03
At iterate    2    f=  1.49651D+03    |proj g|=  2.13394D+02
At iterate    3    f=  6.08288D+02    |proj g|=  9.85720D+01
At iterate    4    f=  2.91810D+02    |proj g|=  6.23062D+01
...
At iterate  142    f=  3.27609D+00    |proj g|=  8.80170D-04
Time taken for minimisation: 36.3749790192

*** BFGS code ***

At iterate    1,  f= 21249.561722
At iterate    2,  f= 15710.435098
At iterate    3,  f= 15443.836262
At iterate    4,  f= 15386.035398
At iterate    5,  f= 15311.242917
At iterate    6,  f= 15211.986938
At iterate    7,  f= 15022.632266
...
At iterate  524,  f= 67.898495
...
Warning: Desired error not necessarily achieved due to precision loss.
Iterations: 1239
Time taken: 340.728140116


texts:
I have a structure. that consist of the following:

Athlete A         Athlete  B     Athlete C
speed=10          speed=12       speed=6
endurance=60      endurance=59   endurance=64

I would like to rank the strength of those three Athletes based on their speed and endurance. I would like to give a slightly greater weight (0.6) to the endurance. Is there any algorithm that have a good complexity to solve this problem?


texts: Given a connected graph with edges >= vertices, find an algorithm in O(n + m) that orients the edges such that every vertex has indegree of at least 1

texts: I'm not exactly sure how to approach this problem. I was thinking we would need to detect a vertex in a cycle, then run DFS on it while also orienting the edges along each vertex u in the cycle, to be directed from u to some vertex v incident to it. But I am not sure what edges cases I might be overlooking, or whether the idea is sufficient. Below is one such example.


texts: Choosing a production with $\lambda$ in Context-Free Grammars

texts:
Given the context-free grammar

\begin{align*}
& S \rightarrow AA \\
& A \rightarrow xA \\
& A \rightarrow B \\
& B \rightarrow yB \\
& B \rightarrow \lambda
\end{align*}
What is the meaning of $\lambda$? $\lambda$ itself means the empty string and will match anything without consuming it, but in terms of the productions, how do you know which one to use? Do you use the last $B$ production only if $B \mapsto yB$ cannot be used? Or can both be used interchangably?

For example, parsing the string $xyy$ could give two different results:

Is there a formal way to prefer one of the two possible options? Which one is the "default"?


texts:
The government wants to create a team with one alchemist, one builder, and one computer-scientist.

In order to have good cooperation, it is important that the 3 team-members like each other.

Therefore, the government gathers $k$ candidates of each profession, and creates their "liking" graph. This is a tri-partite graph, where there is an edge between $a$ and $b$ iff $a$ likes $b$.

(Note that the "like" relation is symmetric but not transitive, i.e.: if $a$ likes $b$ then $b$ likes $a$, but if $a$ likes $b$ and $b$ likes $c$, then not necessarily $a$ likes $c$).

Is this always possible to create a team? Of course not. For example, it is possible that no alchemist likes any builder.

However, suppose the "liking" graph has the following property: in each group of 3 alchemists and 3 builders, there is at least a single alchemist-builder pair that like each other; ditto for alchemists-computerists and builders-computerists.

Given this property, is this always possible to create a team where all 3 members like each other? If so, what is the minimum number of candidates of each type ($k$) that the government will have to gather?

I would like to both find k and prove that it is the minimum.

A possibly related sub-question is: in a group of $k$ alchemists and $k$ builders, what is the minimum number of pairs that like each other? For $k=3$, by the assumption of the question, that number is 1. What about $k>3$?

A third question is: what is the name of this kind of problems?


texts: How can I see which language type will result from the union or intersection of different language types?

texts:
I have to decide which language type will result from the union of a type-2 (context-free) and a type-3 (regular) language.

Is there a way or rule to decide this for all language types?


texts: How to use the Pumping Lemma to prove that a restricted subset of 0*1*2*3*, where there are as many 3's as 0's and 1's, is not a CFL?

texts:
Use the pumping lemma for context-free languages to show that the following
  language is not context-free: $ L = \{0^i 1^j 2^i 3^k \mid k=i+j \} $

So I have started like this:

Let us assume that $ L = \{0^i 1^j 2^i 3^k \mid k=i+j \} $ is a context-free language. Then $ ∃ p∈N $ such that $∀ w∈L$, $|w|≥p$, then $∃ u,v,x,y,z∈Σ^*$ such that we can write $w=xuyvz$ which is subject to the following conditions:

$
 |uyv|≤p\\
 |uv|>0\\
 ∀ k≥0,xu^k yv^k z∈L
$

Now, let $p$ be the constant in the Pumping lemma and let $w=0^q 1^p 2^q 3^{p+q}$.

Here I have gotten stuck. I am not sure about my choice of $w$ and very unsure about what I can actually say about $w$ since I know nothing about $q$ compared to $p$ except that the number of $3$'s is $p+q$. I am even doubting that it is possible to show that $L$ is not context-free. At the moment there is always the possibility that $uyv$ is in both the $1$'s and $3$'s or the $0$'s and $2$'s (if I swap $p$ and $q$), and then I could possibly pump them just fine.

What am I missing here? Been starring myself blind trying to find it.


texts: Pumping-Lemma regular languages: Consider multiple cases?

texts:
The language $ L = \{ a^nb^mc^m : n,m \in \mathbb{N} \} $ is non regular. Suppose this needs to be proven using the pumping lemma for regular languages:
Be $ z = ab^nc^n $ such that $ z=uvw, |v| \geq 1, |uv| \leq n $.
Obviously $uv^2w \notin L $ with $ v=b^{k}$ and $ 1 \leq k \leq n-1$.
Is this proof finished now? Or do I need to consider $ v=ab^{n-1} $ as well?
More general: Using the pumping lemma for regular languages, do i need to consider all possible combinations for $uv$?


texts: Algorithm to maximize function of subsets

texts:
Let's say I have a finite set S with, say, 1000 elements, and a function f on some subset of S. Suppose that f has no useful mathematical properties.

What algorithm is most relevant in finding the subset of S that maximizes f?


texts: What is complexity theoretic implication of following possibilities - $NP=coNP=BPP=RP$ or $coNP\neq NP=BPP=RP$ (consensus is these seem impossible)?


texts: How to tell if a minimax search tree is computationally feasible using parallel computing

texts:
I am trying to apply the minimax algorithm to a game of Pokemon. This is a problem where the search tree is usually around 20 levels deep (number of turns) and each level has 9 or less branches (number of choices per turn).
What I am wondering is if this is a computationally feasible problem using parallel computing? My idea for how to tackle it is to fork a new thread for the first n number of levels to break up the work.
If my math is correct this means that there will be 9^20 operations that need to be split up (technically it will be less since the number of choices per turn decrease as the game gets closer to the end). I was wondering if there is some sort of constant or general rule of thumb I can use to quickly estimate if this problem is computationally possible and worth pursuing or not?
The most ideal outcome would be if the computation can run in 2 minutes or less, but it isn't a requirement.


texts: Generate all combinations of a set/array with specific conditions

texts:
Apologies if this isn't posted in the right stack exchange, but I'm trying to come up with an algorithm that generates a set of sets ('set' as synonymous with 'array') with the following conditions:

Element values range between 0-11
Set length is between 1-12
All sets must begin with 0 ([ 0 ])
Value of element n must be greater than value of element n-1

I want to generate every possible combination of sets with those conditions. So here's a few examples:

[ 0 ],
[ 0, 1 ],
[ 0, 2 ],
[ 0, 3, 5 ],
[ 0, 8, 9, 11 ]

All the way to:

[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]

The main language I'm using is Javascript, but if you're use to dealing with C/C++/Python examples in those languages work too. Just no ASM or Perl please. :)


texts: How to generate uniformly random binary trees?

texts: Could someone please provide a reference giving an algorithm to generate uniformly random binary trees?


texts: Regular Languages and Separating Suffixes

texts:
Preparing for the next semester, I wanted to give the following as a homework question, yet after a few attempts, I failed to solve it.
Given a language $L\subseteq \Sigma^*$ and two words $x,y\in \Sigma^*$, define the language $L_{x,y}$ consisting of all the separating suffixes of the words $x,y$ relative to the Myhill-Nerode relation of $L$. That is, $$L_{x,y} = \{ z\in \Sigma^*:  (xz\in L \wedge yz\notin L) \lor (xz\notin L \wedge yz\in L) \}$$
Is it true that if $L_{x,y}$ is regular for every $x,y \in \Sigma^*$ then $L$ is regular?
Thoughts:

The solution I had in mind works only for languages that have bad prefixes. A word $y$ is a bad prefix for $L$ if you cannot extend $y$ to a word in $L$. That is, $y\cdot z \notin L$ for every $z \in \Sigma^*$.
If $y$ is a bad prefix for $L$, then $L = L_{\epsilon,y}$, and so if $L_{\epsilon,y}$ is regular, we're done.
But clearly, some languages don't have bad prefixes.

The opposite claim is correct: if $L$ is regular, then $L_{x, y}$ is regular. This can be easily solved as follows. If $A = \langle Q, \Sigma, q_0 , \delta, F \rangle$ is a DFA for $L$, then one can define a DFA $B$ for $L_{x, y}$ over the product of $A$ with itself: $B = \langle Q^2, \Sigma, \langle \delta(q_0, x), \delta(q_0, y) \rangle, \delta', ((Q\setminus F) \times F) \cup (F \times (Q\setminus F))\rangle$. I omit the details.


texts:
We'll say $P$ is a symmetric property if $\forall x\in \{0,1\}^n:x\in P\iff \forall \pi \in S(n): f_{\pi }(x)\in P$ where $\forall i\in [n]:f_\pi (x)_i=x_{\pi(i)}$.

Given a symmetric property $P$ we want to find an algorithm which tests $P$, meaning given a vector $x\in \{0,1\}^n$ we want to say if $x\in P$ in sublinear time.

I know how to calculate an $\epsilon-$approximation of hamming weight in probability $\frac{2}{3}$ (can make it higher if I want to but can't get to probability $1$, just choose more indexes) in $O(\log \frac{1}{\epsilon^2})$ but can't find any way to use it.

Thought of trying to calculate the hamming weight with small enough $\epsilon$ such that I'll know if $x\in P$ or not, but can't find small enough $\epsilon$ which doesn't depend on $n$.

Any ideas?


texts: point of view of each pixel with regard to the whole image

texts: I am looking for a technique or an algorithm that outputs a unique number/vector for each pixel of the image. I want to give the pixel a perspective so the neighboring pixels have more visibility and the farther away pixel have less visibility. Imagine if someone walks on the pixels, he sees different patterns, and I want to get such pattern for each pixel. I tried to think of the 2D image as a 3D image stretched on a sphere, but then I would miss the neighboring pixels, and I also thought of planar convolution, but I had no luck, or very intuitive method. I hope that I could explain what I am looking for. Please ask your questions so I could make it more clear.


texts: Complexity of computing the first bits of a minimal permuted adjacency matrix

texts:
Given any graph $G$ on $V(G)=\{1,\dots,n\}$ and its adjacency matrix
$$A(G)=\left(\matrix{
A_{1,1} & A_{1,2} & \dots & A_{1,n}\\
A_{2,1} & A_{2,2} & \dots & A_{2,n}\\
&&\dots&\\
A_{n,1} & A_{n,2} & \dots & A_{n,n}
}\right)$$ any permutation on  $\{1,\dots,n\}$ defines a new isomorphic graph $G'$. A common approach to canonization is to take the lexicographically  minimal string $A'_{1,2}A'_{1,3}\dots A'_{n-1,n}$ (i.e. the upper/lower triangular matrix) such that $G$ is isomorphic to $G'$ with $A'=A(G')$.

If you now consider a permutation on $I=\{(i,j)\mid 1\leq i<j\leq n\}$ or equivalently  a bijective function $\pi : \{1,\dots,{n \choose 2}\} \rightarrow I$, we can try to minimize $A'_{\pi(1)},\dots,A'_{\pi({n\choose 2})}$ instead, or at least to compute the first $k$ bits of the minimal string.

Observe that the complexity of this task heavily depends on the choice of $\pi$:

If you stick with default permutation (upper triangular matrix) you can easily compute the first $2n-1$ bits in polynomial time (adjacent vertices with maximal degrees).
If you choose $\pi(i)=(i,i+1)$ for the first $\sqrt[c]{n}$ positions, you can reduce HamiltonPath to this in polynomial time.

Now my questions:

Given a fixed function $k$ and input $(G,\pi)$ how hard is it to compute the first bits $k(|V(G)|)$ of the minimal string $A'_{\pi(1)},\dots,A'_{\pi({n\choose 2})}$? Is there any (not necessarily strictly) monotonically increasing $k$ for which this is feasible?
Is there a $\pi$ s.t. even $\omega(n)$ bits can be computed in polynomial time?
Do you know any other reductions to a problem of this kind where $\pi$ is "fixed" (i.e. only depends on $|V(G)|$) and the input has the form $(G,k)$ or $G$ (i.e. $k$ is "fixed" too)?

Note: Answering (1) is enough to get accepted.

Edit: In the meanwhile there appeared a somewhat connected question: Is induced subgraph isomorphism easy on an infinite subclass?


texts: How to prove that a string is made up of subsequences occurring some arbitrary number of times using concatenation?

texts:
How to prove that a string, s is made up of n > 1 subsequences occurring some arbitrary number of times using concatenation and stripping first and last character?
 E.g s = xyzxyz, subsequence is xyz and it occurs 2 times. The solution is to concatenate the same string e.g. xyzxyzxyzxyz and then strip the first and last character to get yzxyzxyzxy, then you find s (xyzxyz) inside that.

Other examples:

The word Table does not have a subsequence so the above method will give:
Table||Table -> TableTable -> ableTabl -> which does not contain
Table so Table does not contain a subsequence
The word mmebmmebmmeb -> has to return true with the above method because it contains mmeb repeated 3 times. So, mmebmmebmmeb || mmebmmebmmeb -> mmebmmebmmebmmebmmebmmeb -> (strip first and last) mebmmebmmebmmebmmebmme which contains mmebmmebmmeb (meb**mmebmmebmmeb**mmebmme)

My thought was to assume that there is at least one character in s that will invalidate the occurrence of a subsequence. E.g. instead of xyzxyzxyz (xyz occurring three times) we have xyzxyzxya where a is the wrong char. Now we assume that in   yzxyzxyaxyzxyzxy (after concatenation and stripping first and last) that the string s does exist which should be a contradiction - but I am stuck.

Could someone give me a formal mathematical proof?

Looked at this for ideas:
How to prove that the reversal of the concatenation of two strings is the concatenation of the reversals?


texts: Pick elements that don't exhaust any set

texts:
The following is an NP-Complete problem:

Suppose you have a collection $\mathcal{C}$ of sets, so that $A_i\in \mathcal{C}$ and $A_i$ is some set--we can suppose the elements of $A_i$ are integers.  We want some $k$ integers, say $X \subseteq \bigcup_{A_i\in \mathcal{C}}A_i$ where $X$ has $k$ elements, and subject to the constraint that $A_i \not\subseteq X$ for any $A_i \in \mathcal{C}$.

I primarily am curious whether this is a named problem and if so, what is it's name?  I've already figured out how to show that it's NP-Complete by reduction to the Independent Set problem.  However I am curious to get some more context to this problem, so I wanted to research it a bit.  But I can't find it referenced anywhere.


texts:
I am looking for a sorting algorithm to help me in my work. My objective is the following: after receiving an input of this kind:

5 4
1 2
2 3
3 4
4 5

The first line tells me how many ids I have, and the second number tells me how many connections. The following lines tell me the connections, and tell me that the first Id comes before the second one, for example: 1 comes before 2, 2 comes before 3, and so on. And if an impossible situation occurs:

3 2
1 2
2 3
3 1

or

2 2
1 2
2 1

I want to be able to send an error message.

Or even when there is not enough information to have a conclusive sorting:

4 4
1 2
3 1
3 4
4 2

Is there an algorithm that already does this? or can u give me some guide lines to how to start my work? The sorting part is not hard, but the impossible/insuficient info cases is what I am struggling to implement.

Thanks in advance for your time.


texts: Derive a Context Free Grammar from a language

texts:
I am having challenges (in two phases) with creating a CFG.

Derive the CFG for the following language
Show parse trees for the strings cacab and aacabbb obtained from the grammar designed above.

I am getting a bit mixed up by the exercise especially because my CFG appears not to produce a parse tree.

Here is the language:

$$
    L = \{a^n (ca)^m b^{n+1} \mid m \ge 0 , n \ge 0 \}
$$

So far my grammar looks as follows:

$$ \begin{align}
    S &\to Ab \mid Bb \mid Cb \mid b \\
    A &\to aA \mid \epsilon \\
    B &\to caB \mid \epsilon \\
    C &\to bC \mid \epsilon \\
\end{align} $$


texts: Why is constant always dropped from big O analysis?

texts:
Suppose I have an algorithm that has a performance of $O(n + 2)$. Here if n gets really large the 2 becomes insignificant. In this case it's perfectly clear the real performance is $O(n)$.

However, say another algorithm has a performance of $O(n^2/2)$. Here if n gets really large then $n^2/2$ is exactly half of $n^2$, which is not significantly smaller than $n^2$. So why we drop 1/2 from $O(n^2/2)$ and it becomes $O(n^2)$?