texts: How to prevent overflow and underflow in the Euclidean distance and Mahalanobis distance

texts:
I was working in my project when I was struck by the question of whether it would be necessary, or at least cautious, prevent overflow and underflow in the calculation of these two distances.

I remembered that there is an implementation of the calculation of the hypotenuse to prevent this. Most languages implementers, and is known for Hypot

The calculation of the Euclidean distance remains the same "pattern" and I thought that if Hypot() controls the overflow and underflow should also beware of the Euclidean distance.  I've disappointed to note that the language we use, and others, do not control the overflow and underflow for calculating distance. Will not worth spend this "additional effort"?

I did a searchs and came to a question in Math.StackExchange

There is no definitive answer to this issue and is somewhat old. The first thing I wondered is: Will okay? I think that yes, seeing that is a generalization of the same procedure that performs Hypot().

I decided to extrapolate this concept to the Mahalanobis distance. The original is as follows:

$$D_M(X,Y,L) = \sqrt{\sum_{i=1}^{n}\left(\frac{X_i-Y_i}{L_i}\right)^2}$$

Since $L$ is the vector of eigenvalues.

And my proposal is this:

$$D_M(X,Y,L) = C\sqrt{\sum_{i=1}^{n}\left(\frac{X_i-Y_i}{L_i }\frac{1}{C}\right)^2}$$

That is the same to:

$$D_M(X,Y,L) = C\sqrt{\sum_{i=1}^{n}\left(\frac{X_i-Y_i}{L_i C}\right)^2}$$

And $C$ is the max value from the $|(X_i-Y_i)/L_i|$:

$$C = \max_{i}\left(|\frac{X_i-Y_i}{L_i}|\right)$$

Is it okay?


texts: Restrictions on Computational Methods (Art of Computer Programming)

texts:
In the Art of Computer Programming, Knuth describes a computational method as a quadruple $(Q, I, \Omega, f)$ where $I, \Omega \subseteq Q$, $\Omega$ is pointwise fixed, and each $x \in I$ defines a sequence $x_0, x_1, x_2, \ldots$ such that $x_0 = x$ and $x_{k+1} = f(x_k)$ for $k \geq 0$. He notes that the sequence terminates in $k$ steps if $k$ is the smallest integer for which $x_k \in Q$.
Later he mentions that we can place restrictions $Q, I, \Omega, f$ in the following way.
Let $A$ be a finite set of letters, and let $A^*$ be the set of all strings on $A$. The idea is to encode the states of the computation so that they are represented by the strings of $A^*$.  Now let $N$ be a nonnegative integer and let $Q$ be the set of all $(\sigma, j)$, where $\sigma \in A^*$ and $j \in [0, N] \cap \mathbb{Z}$; let $I$ be the subset of $Q$ with $j = 0$ and let $\Omega$ be the subset with $j = N$. If $\theta$ and $\sigma$ are strings $A^*$,  we say that $\theta$ occurs in $\sigma$ if $\sigma$ has the form $\alpha \theta \omega$ for strings $\alpha$ and $\omega$. To complete our definition, let $f$ be a function of the following type, defined by the strings $\theta_j, \phi_j$ and the integers $a_j, b_j$ for $0 \leq j < N$:
$f(\sigma, j) = (\sigma, a_j)$ if $\theta_j$ does not occur in $\sigma$
$f(\sigma, j) = (\alpha \phi_j \omega, b_j)$ if $\alpha$ is the shortest string for which $\sigma = \alpha \theta_j \omega$
$f(\sigma, N) = (\sigma, N)$

I understand everything until the "To complete our definition..." What primarily confuses me is the function definition. I suppose that the fixed points (i.e. $\Omega$) are given by $(\sigma, N)$. However, I don't understand what $a_j, b_j, \theta_j, \phi_j$ stand for, and that is making it difficult for me to understand what this function is trying to convey. I would appreciate if someone could please break down exactly what $f$ does and relate it to the unrestricted definition.


texts: Show that,with the array representation for sorting an n-element heap, the leaves are the nodes indexed by n⌊n/2⌋+1,⌊n/2⌋+2,…,n

texts:
The Question of the CLRS $6.1-7$ exercise reads as:

    Show that, with the array representation for sorting an n-element heap, the leaves are the nodes indexed by $\lfloor n / 2 \rfloor + 1, \lfloor n / 2 \rfloor + 2, \ldots, n⌊n/2⌋+1,⌊n/2⌋+2,…,n$.

I looked for the solution here:
https://walkccc.github.io/CLRS/Chap06/6.1/

The solution was provided like this:

Let's take the left child of the node indexed by $\lfloor n / 2 \rfloor + 1.$

\begin{aligned} \text{LEFT}(\lfloor n / 2 \rfloor + 1) & = 2(\lfloor n / 2 \rfloor + 1) \\ & > 2(n / 2 - 1) + 2 \\ & = n - 2 + 2 \\ & = n. \end{aligned}

I can't understand this statement:
$LEFT(⌊/2⌋+1) > 2(/2−1)+2$

Please help me out.
Thank you.


texts: What Good Is Kolmogorov Complexity Since It Is Relative?

texts:
Kolmogorov complexity is relative to a choice of Universal Turing Machine. Because of the Invariance Theorem, the difference in complexity assigned by two Universal Turing Machines is bounded by a constant that depends on the choice of that pair. They can't disagree too much because one can always switch over to emulating the other. However, this amount of maximum disagreement can be arbitrarily large.

Given that, of what use is Kolmogorov complexity? I suppose if you have a sequence of bitstrings, then you can talk about the asymptotic growth of the complexity of these bitstrings, and you will know that this is independent of choice of UTM.

But I thought that Kolmogorov was supposed to be meaningful for individual finite strings. But every bitstring can be produced by an arbitrarily small program: imagine a language that functions just like Java but where an empty file produces the bitstring under consideration.

Doesn't this relativity make Kolmogorov complexity basically pointless? I must be mistaken, right?


texts:
We know that the Burrows-Wheeler Transform is reversible, in the sense that, given
s=BWT(w) and an index I, it is possible to recover w by an algorithm. But how to prove that w is unique? In other way how to prove that Burrows-Wheeler is injective?


texts: Prove or disprove, If A ≤p B and B is NP-hard, then A is in NP-hard

texts:
Intuitively if A can reduce to B, and B is NP-Hard, A might be NP Hard but maybe not. If there is a way to solve A that does not involve reducing to B, it might be faster.

How do I formally disprove this statement using a counter example or some well known algorithms, or using some other technique?


texts: How to pick a good structural induction hypothesis

texts:
(Full disclosure: homework question)

Let $M = (Q, \Sigma, q_0, A, \delta)$ be a finite automaton. The extended transition function $\delta^*$ is defined as follows:

$\forall q \in Q$

$\delta^*(q, \Lambda) = q$
$\forall q \in Q, y \in \Sigma^*, \sigma \in \Sigma$

$\delta^*(q, y \sigma) = \delta(\delta^*(q, y), \sigma)$

I am attempting to prove the following statement $\forall x,y \in \Sigma^*$:

$\delta^*(q, xy) = \delta^*(\delta^*(q, x), y)$

It seems pretty obvious from an intuitive standpoint. Since the definition of $\delta^*$ states that for all $y \in \Sigma^*, \sigma \in \Sigma$

$\delta^*(q, y\sigma) = \delta(\delta^*(q, y), \sigma)$

And since the base case of $\delta^*$ is (using $\Lambda$ as the empty string)

$\delta^*(q, \Lambda) = q$

That means $\delta^*(q, y)$ is just a bunch of nested $\delta^*$ applications with the first symbol of $y$ on the innermost application, and the last symbol of $y$ on the outermost application. E.g. if $y = y_1y_2y_3$, then

$\delta^*(q, y) = \delta^*(\delta^*(\delta^*(y_1), y_2), y_3)$

I'm not very experienced at writing proofs, so I'm not sure how to go about setting up the basis case, induction hypothesis, etc. I can prove the first equation for $xy = \Lambda$ as the basis, but I don't know what to do beyond that.


texts:
How do I fill a truth table from the following expression? I can't decide whether it is SOP or POS.

Y=(A+B)C+AB`+(A+C)C`+(`AB)


texts: How to prove that these two languages are regular, or not regular?

texts:
I have these two languages

$L_1={\{a^n b^m,n≥m+5,m>0}\}$ Where $∑=(a,b)$

$L_2={\{a^n b^m,n≥m+5,m≤5}\}$ Where $∑=(a,b)$

As you can see that there is only one difference, the condition of m is different.

My question is to determine whether these two languages are regular or not, and to prove it.

If one or both these languages are non-regular. then how can we prove that using pumping lemma?

These two languages have so many conditions, I am just confused that how to solve these kind of Languages.


texts:
Say I have $k$ sorted lists of the same size $n/k$, and I want to combine them into one sorted array in $O(n\log k)$ time.

The solution I came up with is to recursively halve the lists until you have sections of two lists. Then you combine them by setting a pointer at the start of each one, and placing the smaller element into a new array and incrementing its pointer until you've gone through every element, then return that sorted array.

The combine part does at most $2n$ comparisons, so it's $O(n)$. The recursion depth is $\log_2 k$, since you're halving the remaining lists at each combination. This would give a total of $n\log_2 k$.

Is this a correct implementation and time analysis?


texts:
given:
$$m_1+m_2+...+m_k=m$$
How can I find $\Theta(log(m_1)+...+log(m_k))$ as related to $m$?

I know that i can doing that: $O(log(m_1)+...log(m_k))=O(log(m)+...+log(m))=O(k \cdot log(m))$ , but can I find something without $k$ ?


texts:
By definition:

  For a given function $g(n)$ we denote by $\Theta(g(n))$ the set functions

  $\Theta(g(n))$ = $\{f(n):$ there exists positive constants $c_1, c_2$ and $n_0$ such that $0 \leq c_1g(n) \leq f(n) \leq c_2g(n)$ for all $n \geq n_0$ .$\}$

We say $6n^3 \neq \Theta(n^2)$ becuase if it was, then there would be:

\begin{equation}
6n^3 \leq c_2n^2 \Rightarrow n \leq c_2/6  \hspace{100px} (1)
\end{equation}

which is not true because $n$ (size of the input) is not limited to any constant.

But to prove $\dfrac{1}{2}n^2-3n = \Theta(n^2)$ we can write

\begin{align*}
    c_1n^2 &\leq \dfrac{1}{2}n^2-3n \leq c_2n^2\\
    c_1 &\leq \dfrac{1}{2}-\dfrac{3}{n} \leq c_2
\end{align*}

by setting $c_1=1/14, c_2=1/2, n_0=7$ it becomes true.

Here is the problem,

$$\dfrac{1}{2}-\dfrac{3}{n} \leq  c_2$$

implies

$$
n \leq \dfrac{1/2-c_2}{3} \hspace{100px} (2)
$$

why in $(1)$ bounding $n$ is a contradiction, but in $(2)$ it is not?

Thanks


texts: Online algorithm to find shortest subarray containing all k-elements

texts:
We have given array of $n$ integers in the range $[1, k]$. We want to design algorithm that can modify the array and also find the length of the shortest subarray containing at least one of each integers in the range $[1,k]$. $k$ can go up to 50, but $n$ can be large number, up to 100000.

I know that the offline version with fixed array can be solved in $O(NK)$ with sliding window across the array, but I don't know how to extend this or another algorithm to make it work online.

Please give me some hints where to start.


texts: Area of Union Of Rectangles using Segment Trees

texts:
I'm trying to understand the algorithm that can be used to calculate the area of the union of a set of axis aligned rectangles.

The solution that I'm following is here : http://tryalgo.org/en/geometry/2016/06/25/union-of-rectangles/

The part I don't understand is :

  The segment tree is the right choice for this data structure. It has complexity O(logn)
   for the update operations and O(1)
   for the query. We need to augment the segment tree with a score per node, with the following properties.

  every node corresponds to a y-interval being the union of the elementary y-intervals over all the indices in the span of the node.
  if the node value is zero, the score is the sum of the scores of the descendants (or 0 if the node is a leaf).
  if the node value is positive, the score is the length of the y-interval corresponding to the node.

How do we achieve this in O(n log n) ?

My idea was to create a segment tree, and update each range's value as and when we encounter the range(y range as the height of the rectangle) while line sweeping. And then for for each interval(two consecutive elements in the sorted x array, multiple Δx by the total length of the y range active in this interval, by looking at the sum of all elements in the segment tree)

This would still leads us to having max(y) - min(y) elements in the segment tree's base.

Hence, I'm not sure how this is O(n log n) - where n is the number of rectangles.

Would greatly appreciate any help here.

I got an answer here : https://stackoverflow.com/questions/55702005/area-of-union-of-rectangles-using-segment-trees

But I'm not sure I understand @Photon's solution. What I don't understand is, what does each value inside each node of the segment tree mean ? And if we talk about the case where after meeting first rectangle on x=0, why does the segment tree get updated to the second figure ?

Per my understanding, the interval we're trying to update is [3, 6]. But that doesn't seem to be the case.

Thanks!


texts: It is clear, that NP ⊆ PSPACE holds and that it is unknown if the strict inclusion holds. How is it if one looks at the corresponding functional complexity classes? Does FNP ⊂ FPSPACE hold?


texts: Is there any undecidable language that is countable?

texts: All we know is that if a language is countable than it must be recognizable. However, a recognizable language may or may not be decidable.


texts:
One way to prove that a problem $X$ is NP-Complete is to pick two NP-Complete problems $Z$ and $W$ and show that ($\leq_p$ is polynomial reduction):
$$\begin{array}{rr}X \leq_p Z & (1)\\W \leq_p X&(2)\end{array}$$
The usual way to prove NP-Completeness however, is to follow Karp’s strategy which consists in proving that
$$\begin{array}{rr}X\in \textsf{NP} & (3)\\W \leq_p X&(4)\end{array}$$
I am trying to show that $(1)$ and $(3)$ are equivalents, but but I'm not sure where I can start. Can someone help me with how to do this?


texts: How can ws with |w| = |s| and w ≠ s be context-free while w#s is not?

texts:
Why does (if so) the seperator $\#$ is making a difference between the two languages  ?

Let say:

$L=\{ws : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \}$

$L_{\#}=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \}$

Here is a proof and a grammer representing $L$ as a $CFL$

And below Im adding a proof for $L_{\#} \notin CFL$ :

Does the $\#$ sign truly make a difference? if so, why is that ? and if not, which one of the proofs is wrong and where?

Proof that $L_{\#} \notin CFL$ :

Assume by way of contradiction that $L ∈ CFL$. Let $p > 0$ be the pumping constant for $L$
guaranteed by the pumping lemma for context-free languages. We consider the word
$s = 0^{m}1^{p}\#0^{p}1^{m}$ where $m=p!+p$ so $s ∈ L$.
Since $|s| > p$, according to the pumping lemma there exists a representation $s = uvxyz$, such that
$|vy| > 0$, $|vxy| ≤ p$ , and $uv^{j}xy^{j}
z ∈ L$ for each $j ≥ 0$.

We get a contradiction by cases:

If $v$ or $y$ contain $\#$: Then for $i = 0$, we get that $uxz$ does
not contain $\#$, so $uxz \notin L$ in contradiction.
If both $v$ and $y$ are left to $\#$: Then for $i = 0$, we get that
$uxz$ is of the form $w\#x$, where $|w| < |x|$, so $uxz \notin L$.
If both $v$ and $y$ are right to $\#$: Similar to the last case.
If $v$ is left to $\#$, $y$ is right to it, and $|v| < |y|$: Then
for $i = 0$, we get that $uxz$ is of the form $w\#x$, where $|w| >
   |x|$, so $uxz \notin L$.
If $v$ is left to $\#$, $y$ is right to it, and $|v| > |y|$: Similar
to the last case.
If $v$ is left to $\#$, $y$ is right to it, and $|v| = |y|$: This is
the most interesting case. Since $|vxy| ≤ p$, $v$ must be contained
in the $1^{p}$ part of $s$, and $y$ in the $0^{p}$ part. So it holds
that $v = 1^{k}$ and $y = 0^{k}$ for the same $1 ≤ k ≤ p$  (in fact,
it must be that $k < p/2$). For each $j ≥ 0$, it holds that
$uv^{j+1}xy^{j+1}z = 0^{m}1^{p+j·k}\#0^{p+j·k}1^{m}$, so if it
happens that $m = p + j · k$, then it holds that $uv^{j+1}xy^{j+1}z
   \notin L$ in contradiction. To achieve this, we must take $j =
   (m-p)/k$, which is valid only if $m − p$ is divisible by $k$. Recall
that we chose $m = p + p!$, so $m − p = p!$, and $p!$ is divisible by
any $1 ≤ k ≤ p$ as wanted.


texts: Finding path with best distance/cost ratio from a node in a graph

texts:
We have a weighted graph, where each node is a city. And the edges between the nodes are a pair of floating-point values (distance and cost of travel).
Given a node/city, describe an algorithm that can find the path with the largest distance/cost ratio from said node/city. Note that the path can traverse multiple nodes.
I need help with this (for both directed and undirected graphs). I stumbled across this question in a lecture note from my university (I graduated but am self-studying), and have no idea how to solve this.
There is no limitation on how to store the graphs, though I only know of adjacency matrix and adjacency list.


texts:
How can I convert a XOR statement into linear constraints for integer programming ?
The expression is $(x_1 \geq 1)$ XOR $(x_2 \geq 1)$ where $x_1$ and $x_2$ are integer. It means that if $x_1 \geq 1$ then $x_2 = 0$ and vice versa.
I started to linearize the statement by :
$(x_1 \geq 1)$ XOR $(x_2 \geq 1) = (x_1 \geq 1 \quad and \quad x_2 \leq 0) or (x_1 \leq 0 \quad and \quad x_2 \geq 1)$ but I don't know how to continue, I would like to follow the Big M mothod but I'm going around in circles...
I need it to resolve this kind of linear program where if $x_1\geq 0$ then $x_2=0$ and vice versa :
\begin{equation}
\begin{aligned}
\min \quad & a_1x_1 + a_2x_2 + a_3x_3\\
\textrm{s.t.} \quad & x_1 + x_2 + x_3 = 200\\
  &x_1 \leq 100\\
  &x_2 \leq 100\\
  &x_3 \leq 100\\
  &x_1 \geq 1 \quad xor \quad x_2 \geq 1 \\
  &x_i \in N, \quad i \in \{1, 2, 3 \}   \\
  &a_i \in R, \quad i \in \{1, 2, 3 \}   \\
\end{aligned}
\end{equation}
Thanks a lot ! :)


texts: Algorithm to split an array into minimal number of subarrays where sum of their elements is less than or equal a given one

texts:
Title of the question pretty much summarises the question. Here is a concrete example of what I'm trying to achieve with no success.
Let's say we have a sorted list (but sorted is not a requirement) L = [1,3,20,100,150,200,260] and K = 260. I need a function f(L,K) which given this list and K will return a list B = [[1,3,20,200],[100,150],[260]]. As you see if we just group elements in their sorting order with their sum <= K like this: [[1,3,20,100], [150], [200], [260]] we will have 4 subarrays but it's possible to have 3.
This algorithm may be useful for instance to make a compact linear stack layout of some UI elements of different lengths with min number of lines of those elements.

UPD. I decided to remove a word "efficient" from the question because this looks like an NP-hard problem. To be clear I need more or less optimal but correct solution. Numbers will not be large because I'm talking about this problem in the context of practical task (efficient UI layout) that's why K and list elements will be a small numbers in the range [0, ..., ~1000].
I put a label "dynamic programming" because I think that this problem may be solved with dynamic programming approach and as was mentioned in the first comment is related to bin packing problem.


texts: Game Theory: Using a convex hull algorithm to map out Pareto outcomes

texts:
I have started studying the Pareto efficiency notion in Game theory. The definition I am familiar with is this:

Strategy profile $\mathbf{s}$ Pareto dominates strategy $\mathbf{s}'$ if for all $i\in\mathcal{N}$, $u_i(\mathbf{s})\geq u_i(\mathbf{s}')$, and there exists some $j\in\mathcal{N}$ for which $u_j(\mathbf{s})>u_j(\mathbf{s}')$. Strategy profile $\mathbf{s}$ is Pareto optimal, or strictly Pareto efficient, if there does not exist another strategy profile $\mathbf{s}'\in S$ that Pareto dominates $\mathbf{s}$.

I am interested in finite normal form games, for example, the $n$-player Prisoner's dilemma. Clearly, for $n=2$ we have three Pareto outcomes and it's not too difficult to derive them.

But my concern is with a large number of players and non-constant utilities. How do can we find the Pareto efficiency outcomes? If you are aware of a paper that does this, please share it with me.

Is there a better, more efficient way to compute the efficiency of different outcomes of a game? Maybe the price of anarchy?

I'd appreciate any help or hint. Thank you.


texts: Can the average case of an algorithm be $O(n \log n)$ if the best case running time of an algorithm is $\Theta(n \log n)$?

texts: Let us suppose the best case running time of an algorithm is $\Theta(n \log n)$. Can the average case run time of the algorithm be $O(n \log n)$? Since $O(n\log n)$ would imply the value going even below $n \log n$ hence would be lower than the best case bound of $\Theta(n \log n)$. Is this possible?


texts: Disabeling interrupts to solve critical section issue on multiprocessor system

texts:
Assume I have a multicore system and a critical section.

I understand how disableling interrupts on a single core systems solves the critical section problem.

So assume I could disable interrupts on all cores atomically (Why is that not possible?).
Why would that solve the problem?

As I understand, there would still be n processes running at the same time that may interfere with each other. They just wont be stopped until interrupts are enabled again.

Can somebody explain why that would (according to my professor) work?


texts:
I'm trying to determine the big O time complexity of the following
data set where the first column is the input size, and the second column is the execution time in seconds. Where possible, I should determine the exponent of the dominant term and provide an estimate for the coefficient on the dominant term.

I made the following
graph of the data and a log/log graph to try and figure it out. At first I thought it might have been 1/n or something along those lines but as n gets quite large, the execution time increases again instead of asymptotically approaching a value.
The log graph having such a distinct pattern leads me to believe that the answer will lie there but I'm stuck as to where to go from here. Any help would be great.


texts:
Could you proof it to me that A(A+B) = A?

AA + BA [AA = A]

A + AB

Then what?


texts: How does Gradient Descent treat multiple features?

texts:
As far as I know, when you reach the step, in a gradient descent algorithm, to calculate step_size, you calculate learning_rate * slope
Now, slope is obtained by calculating the derivative of the cost_function with respect to the feature you want to find the optimal coefficient for.
Let's say that the cost function for the purposes of this question is the sum of squared residuals.
My question is, how are coefficients of other features treated in the differentiation of the equation? For instance, if I have the equation $y = b_0 + x_1 + x_2$, then by calculating the derivative of the cost function with respect to $x_1$, one gets:
$\frac{d}{d\left(x_1\right)}\left(\left(\hat{y}\:-\:\left(b_0\:+\:x_1+x_2\right)\right)^2\right) =$
$2\times\:\left(\hat{y}\:-\:b_{0\:}-x_1-x_2\right)\left(\frac{d}{d\left(x_1\right)}(x_2)\:+\:1\right)$
In this case, how is a value obtained by substituting a value for $x_1$ while $\frac{d}{d(x_1)}(x_2)$ is still in the formula?
I watched a YouTube video (it starts at the right point) that says that  $x_2$ is a constant (while it's a different feature) and, therefore, when differentiating, $\frac{d}{d(x_1)}(x_2)$ is omitted and we are left with $2\times \:\left(\hat{y}\:-\:b_{0\:}-x_1-x_2\right)(1)$. Is this the case or am I missing something?


texts: Keeping a String Secret in (Open) Source Code

texts:
I have finished developing an app for Android and intend to publish it with GPL -- I want it to be open source.
However, the nature of the application (a game) is that it asks riddles and has the answers coded into the string resource. I can't publish the answers!
I was told to look into storing passwords securely -- but I haven't found anything appropriate.

Is it possible to publish my source code with a string array hidden, encrypted, or otherwise obscured? Maybe by reading the answers from an online database?

Update

Yuval Filmus's solution below worked. When I first read it I was still not sure how to do it. I found some solutions, for the second option: storing the hashed solution in the source and calculating the hash everytime the user guesses. To do this in javascript there is the crypto-js library at http://code.google.com/p/crypto-js/.
For Android, use the MessageDigest function. There is an application (on fdroid/github) called HashPass which does this.


texts: Algorithm to search substring in a circular string?

texts:
I need an algorithm to search for substrings. I checked different resources, and it seems that the most known algorithms are the Boyer–Moore and the Knuth–Morris–Pratt.

However, as far as I understand, these operate on "regular" strings, but what I need is a substring search on a circular string.

A circular string as a string characterized only by its size and the order of the elements, i.e. ABCD is the same as BCDA, CDAB and DABC

An source/query example that should succeed:

Source string: EFxxxABCxxxxxD
Query string:  DEF

Do you know of any references on substring search on circular strings? Any advice on how to do this?

(Possibly) related:

CS: Automaton for substring matching
SO: main differences between the KMP and BM algorithms?
http://en.wikipedia.org/wiki/String_searching_algorithm


texts: Big-O when iterations do not correlate with input

texts:
Sorry for the perhaps basic question, but my time at university is long ago and I need to brush up on Big-O stuff for interviews.
My question is, what would the time complexity be when an algorithm does depend on the input but not on the size of the input? For example, assume I have this function:
func doSomething(numbers []int) int {
    // find maximum number
    maxNumber := max(numbers)
    for i := 0; i < maxNumber; i++ {
      // magic happens here
    }
}

func maxNumber(numbers []int) (max int) {
     for _,num := range numbers {
           if num > max {
              max = num
            }
     }
     return max
}

How would you define the Time-Complexity of doSomething? The amount of iterations happens to be the maximum number in the input, so if the input is [1000000] we  get 1000000 iterations with input size 1. Yet if the input would be [1,1,1,1,1,....] the iteration would still only be 1 even though our input size would be much greater.
Of course the maxNumber would be O(n) but my understanding is that you would ignore  this in the calculation of doSomething.
I could say O(1) because it's not dependent of the input size, but that seems wrong to me because different input could have different iterations.


texts: Terminology Questions: Data-structure consisting of lists without repetitions

texts:
I've google around and have been unsuccessful in finding a name for a data-structure consisting of a list whose elements are unique.

I've seen "unique sorted lists", but I'm looking into the more general, not necessarily sorted, case.

Does anyone know a name and a source for such things? --e.g., a one word name for them.

Moreover, lists may be construed as initial algebras or the solutions to a family of recursive equations involving constructors, say, nil and cons. What possible equational algebra gives rise to lists without repetitions? That is, do they pop-out as a solution to some family or are they an algebraic data type that has certain equational constraints, if so which ones?


texts: Suboptimal Solution for a combinatorial problem

texts:
I have a cost function $f(X)=\|\hat{X}-X\|_2$ to minimize which depends on a $s\times s$ matrix $X$ where $\hat{X}$ is given and $\|X\|_2=\big(\sum_{i,j}x_{ij}^2\big)^{1/2} $. This matrix $X$ is generated by selecting only $s$ different rows from a matrix $B$ of dimension $n\times s$. At the end, we are going to choose one matrix $X$ that generates the least cost $f(X)$ within all possible $n\choose s$ submatrices of B. And so, this is a combinatorial problem that becomes complicated mostly when $n$ is big.

So my question is can we find a suboptimal solution without going through all possible $n\choose s$ submatrices and what kind of algorithm that I can apply to find such solution.

My second question is can we apply a feature selection algorithm to find a suboptimal solution for a combinatorial problem.


texts: How can I multiply a binary representation by ten using logic gates?

texts:
So I’m currently working on something and I have converted all decimal digits 0-9 into binary.
But now I want to take say 6 in binary and increase its order of magnitude by base 10 (turning 6 into 60) without converting back to base 10.
Is this possible and if so is there a way to do it with any number, X --> X0 ?

EDIT 1: sorry the first part of the question was super vague and I forgot to mention I’m trying to do this with logic gates.


texts: How many possibilities of merging two queues?

texts:
Say there're two queues of numbered items of different kinds (e.g. color), now we need to merge them into one queue so that each item maintains its order in the original queue, regardless of its kind.

For example,

queue of blacks balls: b1, b2, b3

queue of red balls: r1, r2

one possible merging result: b1, b2, r1, b3, r2

given size of two queues being m and n, derive an expression of total possibilities of merging? I feel like it can be solved with dynamic programming but still have no clue...


texts:
I'm looking for someone who can tell me which algorithm this is and help me to clearify what the variable mean.

$g_j$ : the shortest path length from $1$ to $j$
$t_{i,j}$: the length from $i$ to $j$
$\mathrm{SCS}$: successive set
$S$: Start node, $G$: Goal node

\begin{align}
   &f_G = 0 \\
   &f_i = \infty, \forall i ≠ G \\
   &t_{i,j} = \infty, \forall (i, j) \notin T \\
   &t_{i,j} > 0 , \forall (i, j) \in T\\
   &T = \{1, 2, . . . , N − 1, N\}, \quad Ť = \{\emptyset\} \\
   &\text{Do while $T$ is not empty} \\
   &\qquad j^* = \arg\min_{j\in T} f_j \\
   &\qquad \text{for }i \in \mathrm{SCS}(j^*)\\
   &\qquad\qquad f_i  = \min \{f_i , t_{i,j}^* + f_j^*\}\\
   &\qquad \text{Remove $ j^*$ from T, add $j^* $ to Ť} \\
   &\text{Stop while }j^*= S
\end{align}


texts: Is it possible to implement 64-bit cmpxchg from 32-bit cmpxchg?

texts:
Question

Given a 32-bit cmpxchg operation as a primitive:

u32 cmpxchg32(u32* mem, u32 key, u32 old, u32 neo) {
    // this function runs atomically
    u32 found = mem[key];
    if (found == old) {
        mem[key] = neo;
    }
    return found;
}

Is it possible to implement the same function, for 64-bits?

What I've tried

So far, the only progress I've had is this paper, which describes a method for implementing multi-word cmpxchg based on single-word primitives. It works for arbitrary lengths, though, and uses linked lists, insertion sort and additional heavy-weight structures to accomplish that. It, thus, looks overkill for my case, so I wonder if there is a more straightforward approach for the 32-bit -> 64-bit case.


texts: How do modern Operating Systems detect process starvation?

texts:
So first off do the modern operating systems like windows and linux have a method for detecting starvation? if not, why? and if they do, then how are they going to detect starvation of a process? (this was a question in our exam)

my take was this so correct me if this is not good or not possible:

i said we should implement a linked list of waiting processes (that are waiting for a resource or etc) then we periodically run a function(using interrupts) which checks this list and we have a variable for each process and we increase that everytime, when it reaches certain point then we would know its starving(but i still dont know how to know this "certain point")

so is this correct? if so then how can we know this "certain point"? ( I suppose one way is just look at the statistic of average waiting time of processes and do a little math?)

if not, what is your solution?


texts:
Is infinite union of non-regular languages $L_i$ that form a chain such that $L_i\subseteq L_{i+1}$  always non-regular?

Or is there a possibility that it be ever regular?

Is there an easy way to see this?


texts: Does left factoring CFG make it unambiguous?

texts:
I came across following problem:

  If the CFG is left factored then it must be Unambiguous and Not left Recursive.
  TRUE/FALSE?

I have many thoughts about this. But I feel they are somewhat contradicting and hence form a bigger doubt. May be I lack some understanding.

Thought 1

Ambiguity has nothing to do with determinism (even if grammar does not have productions with same prefix of their right side, they still can have a string with two parse trees). So CFG is still ambiguous after left refactoring. Hence, the sentence should be false.

Thought 2

Left factoring is used to eliminate common prefixes of right hand side of productions in the grammar. Doesnt that make grammar deterministic? Deterministic grammar derive deterministic context free languages. So isnt turning grammar deterministic makes it unambiguous? If yes, given statement should be true.

Thought 3

I have completely ignored left recursion in thought 1 and 2. Is it ok?

Doubt: I feel thought 1 and  thought 2 are contradicting. And I am not able to figure it out which one is correct. Which of the above thoughts are incorrect and why? Am I missing any more subtleties?


texts: Polynomial generator required to detect single bit error in Cyclic Redundancy Check codes

texts:
I was reading about CRC coding from two books:

Data Communication and Networking by Forouzan Page 294
Computer Network by Tanenbaum Page 188

They use following notations:

$d(x)$: dataword to be sent (as a polynomial)
$c(x)$: codeword sent (as a polynomial)
$e(x)$: error (as a polynomial)
$c(x)+e(x)$: codeword sent with error introduced (if any)
$g(x)$: generator polynomial to be used at CRC encoder (for creating c(x)) and decoder (for checking if error is introduced or not during transmission)

Forouzan then states following:

  A single-bit error is $e(x)=x^i$, where i is the position of the bit. If a single-bit error is caught, then $e(x)=x^i$ is not divisible by $g(x)$. (Note that when we say not divisible, we mean that there is a remainder.) If $g(x)$ has at least two terms and the coefficient of $x^0$ is not zero (the rightmost bit is 1), then $e(x)$ cannot be divided by $g(x)$ and all single bits errors can be caught.

He then gives example of generator:

$g(x)=x+1$ saying that it can catch all single bit error (with which I have some doubts)
$g(x)=x^3$ saying that all single-bit errors in positions 1 to 3 are caught rest are left uncaught (with which I dont have any confusion).

For example, consider the below example for generator $g(x)=x+1$:

Tanenbaum says:

  If $g(x)$ contains two or more terms, $e(x)$ will never divide into $g(x)$, so all
  single-bit errors will be detected.

My doubts:

Q1. Forouzan states additional requirement to Tanenbaum that "the coefficient of $x^0$ is not zero (the rightmost bit is 1)". Whats correct? and why? Will generator $g(x)=x^3+x^2$ (which satisfies Tanenbaum's statement) capture all single bit errors? Do we always need "$+1$" in $g(x)$ for capturing any single bit error?

Q2. I feel I dont understand the reason/logic behind statements made by both authors, thats why I am not able to decide on myself whether "$+1$" should be there in $g(x)$ or not. Whats the logic then behind both of statements (whichever is correct)? More precisely: why $e(x)$ with single bit error will not be dividable by $g(x)$ if

  $g(x)$ has at least two terms and the coefficient of $x^0$ is not zero

as Forouzan says or if

  $g(x)$ contains two or more terms

as Tanenbaum says (whichever is correct).

I must be missing something very very basic stuff here.


texts: For every undirected unweighted graph is every MST also a SPT

texts: I have a feeling this might be wrong an I'm looking for a counter example, however, I couldn't find one yet.. can anyone guide me in the right direction?


texts:
Say you have a loop that iterates over an array,

for i in someArray:
    //some code

This basic example would have a running time of $O(n)$. Say that you added a nested loop with equal number of operations, this then would be $O(n^2)$. My question is, is it safe to do this kind of simplication in general? For example,

Say your outer loop had worst case complexity of $O(n^2)$ and your inner loop has worst case complexity of $O(\log n)$. Can the total time complexity be said as $O(n^2\log n)$?


texts: When do you know whether an exponent represents a movement of the decimal point to the left?

texts:
I'm learning about floating point numbers and I don't quite understand when one should interpret an exponent as moving the decimal point to the left.

By book shows  an example of converting -10.5 into binary in normalised form (using 8 bits):

First we convert it into binary without normalisation and use a fixed floating point representation, giving 10101.100
We know to normalise it, the decimal point must move four places to the left (so when we get the normalised number, the decimal point would having to move four places right)
So in normalised form, we get a mantissa of 1.0101100 and an exponent of 4

Now, my book represents four at 100, but it also says to use two's complement. Therefore, can't I interpret 100 as -4? When would I know to interpret an exponent as negative or positive? I.e., when would I know to move a decimal point to the left when given a mantissa?


texts: Is the relation between the input and output of an arbitrary algorithm describable by a mathematical function?

texts:
I hope that this question is clear, and not off-topic:

I have been reading about neural networks (in the AI sense), and the textbook said that an artificial neural network can always be described by a single mathematical function (rather than by an "algorithm" in a register-machine, which is the standard way I intuitively look at an AI neural network).

So this made me think: is it possible for any arbitrary algorithm, meaning an arbitrary Turing machine, to be simulated by a mathematical function? (I do not mean a function as used in programming languages).

By simulated in this case I mean that given any arbitrary input in the algorithm, that function produces the same output as the algorithm.


texts: A 1 is an "on" signal, and a 0 is an "off" signal. How does a computer know 01110 is different from 010? Does the computer wait between signals?


texts: Does pre-emption of a process occur when that process is busy waiting?

texts:
I was reading about Peterson's Solution for Synchronisation. Let's assume the two shared variables to be int bool flag[2] and turn. Lets also consider the two processes as P0 and P1.

Initially, P0 executes causing - flag[0] = true and turn = 1. Now lets assume P0 is pre-empted by P1 causing - flag[1] = true and turn = 0

Now, busy waiting condition of P1

while(flag[0] == true && turn == 0);

puts P1 on an indefinite wait until P0 resumes its execution, completes it and turns flag[0] = false. But wouldn't this again require P1 to be pre-empted, and bring back P0 from 'Ready' to 'Running' and get it executed ? So does a process pre-empt if it's busy waiting?


texts: Give a computation of the expression to normal form (Lambda calculus)

texts:
Past exam question:

What my understanding of B-reduction is : Find all occurrences of the parameter in the output, and replace them with the input and that is what it reduces to

(λ param . output)input => output [param := input] => result

Example:

(λx.xy)z

= (xy)[x:=z]

= (zy)

= zy

But I do not know how to use B-reduction on the expression above. What is the input, output and the parameter.


texts: Is checking if regular languages are equivalent decidable?

texts:
Is this problem algorithmically decidable?
L1 and L2 are both regular languages with alphabet $\Sigma$. Does L1 = L2?
I think that it is decidable because you can write regular expressions for each language and see if they are the same. But I'm not sure how to prove it since I see that you prove something is decidable by showing a Turing Machine


texts: Algorithm for finding best match between two database rows

texts:
Let's say we have a database with a given table named food. The food table has many columns but we are interested in only 3 of them:

buyorsell, which specifies if the food is for selling or buying.
amount, which is the amount of food to be bought or sold.
isVegan, which is set true if the food is vegan.

The goal is to find the best match between 2 rows. The best match should satisfy the following rules:

Both rows have the same value for 'isVegan'
One row should be buy/sell and the other row must be the opposite
Both amounts must be equal

The table will have millions of rows and the table is changing rapidly.

What is the right algorithm in matters of speed and resource usage for this matching problem?


texts: Formal semantics of a mutable/imperative stack

texts:
When introducing formal semantics for data structures, immutable stacks are a nice simple example :

$\mathit{is\_empty}(\mathit{create()})=\mathrm{True}$
$\mathit{is\_empty}(\mathit{push}(e, s))=\mathrm{False}$
$\mathit{top}(\mathit{push}(e, s)) = e$
$\mathit{pop}(\mathit{push}(e, s)) = s$

I am trying to do the same for a mutable stack structure, where the $\mathit{push}$ and $\mathit{pop}$ operations will modify a stack instead of returning one.

The way I am trying to do it is with Hoare triples. I can define the simplest ones (omitting that $s$ is a stack and $e$ an element) :

$[]\  s\gets create() \ [\mathit{is\_empty}(s) \text{ yields True}]$
$[]\ \mathit{push}(e, s) \ [\mathit{is\_empty}(s) \text{ yields False}]$

However I am not finding satisfactory axioms for $\mathit{pop}$. I could do $$[\mathit{is\_empty}(s) \text{ yields some value } b]\ \mathit{push}(e, s)\mathord{;} \mathit{pop}(s)\ [\mathit{is\_empty}(s) \text{ yields the same value } b]$$.

But this is formally only applicable when one would push and immediately pop, which is too restrictive.

With the immutable version, the same axiom (mutatis mutandis : sequence vs. composition) is acceptable because in any actual $\mathit{pop}(s)$ where $s$ is an expression that correctly denotes a non-empty stack, this expression $s$ can be reduced (in the sense of rewriting) to a normal form $\mathit{push}(\cdot, \cdot)$ and the axiom will then apply, allowing for further reduction.

This does not seem to work in the mutable/imperative case. Or does it ?

A solution would be to use properties that express the length of a stack~: pushing adds one, poping subtracts one, and expressing emptiness becomes easy. But this would not be sufficient for tracking the values of the elements ; applying the same idea would amount to having a whole immutable stack in the Hoare properties to track the mutable stack in the imperative program.

Is there a neater approach to this ?


texts: How can Chomsky hierarchy be applied to languages with alternated letters?

texts:
I have the following grammar, which I know it is regular because it can be represented by a finite state automata:
\begin{array}{l}
\mathrm{S} \rightarrow \mathrm{X} \mid \mathrm{Y} \\
\mathrm{X} \rightarrow \mathrm{a} \mathrm{Y} \mathrm{b} \mid \mathrm{ab} \\
\mathrm{Y} \rightarrow \mathrm{b} \mathrm{X} \mathrm{a} \mid \mathrm{ba}
\end{array}
According to Chomsky hierarchy:

Type-3 grammars generate the regular languages. Such a grammar
restricts its rules to a single nonterminal on the left-hand side and
a right-hand side consisting of a single terminal, possibly followed
by a single nonterminal (right regular). Alternatively, the right-hand
side of the grammar can consist of a single terminal, possibly
preceded by a single nonterminal (left regular).

However, I do not find the hierarchy applied to the grammar. Am I missing something?


texts: Modified Linear Bounded Automata Language

texts:
We know that linear bounded automatons accept context-sensitive grammars.

  Now suppose that we modify the LBA such that any location of the tape except the
  input part can be changed.What language does this automaton accept?

I think it is as strong as the standard Turing machine because we can copy the input part somewhere else and work with it like a semi-infinite Turing machine so that its tape is limited from the first symbol of the input that we copied.So it accepts recursively enumerable languages.Is this correct?


texts: How many queries does it take to find the best flight?

texts:
I often find flights through a search engine like Google Flights. On input some refined subset of the space of all flights (e.g., non-stop only, departing in the morning, from one of two airports, and on a certain date) the search engine returns the cheapest flight in this subset. My goal using the search engine, however, is not so simple as restricting to a subset and finding the cheapest flight. Rather, I mentally place a certain dollar value on how much I am willing to pay extra for various options: e.g., willing to pay \$20 extra for nonstop, willing to pay \$50 extra for closer airport. I want to find the cheapest flight after these dollar values are taken into account.

This raises an algorithmic question: how many queries to the search engine does it take to find the best flight? We can formulate this as the following search problem:

$X$ is a search space (set of flights);
$f: X \to \mathbb{R}^+$ is an unknown price function, where $f(x)$ is the price of $x$;
$g: X \to \mathbb{R}^+$ is a known additional cost to us, which we assume is a weighted sum of $k$ known indicator functions:
$$
g(x) = \alpha_1 [x \in A_1]
+ \alpha_2 [x \in A_2] + \cdots + \alpha_k [x \in A_k],
$$
where $\alpha_i \ge 0$ are weights and $[x \in A] = \begin{cases} 1 &\text{if } x \in A \\ 0 &\text{otherwise} \end{cases}$ is the Iverson bracket.

The problem: Determine $\min_{x \in X} (f(x) + g(x))$, using queries to an oracle which, on input any subset $X' \subseteq X$, returns $\min_{x \in X'} f(x)$ and $\arg\min_{x \in X'} f(x)$.

Question 1: As a function of $k$, how many queries to the oracle are needed in the worst case?

It can easily be done in $2^k$ queries: the sets $A_1, A_2, \ldots, A_k$ collectively partition $X$ into $2^k$ regions, so we can query on each subset. Is there a better algorithm in general?

Question 2: Assume that the actual minimum of $f(x) + g(x)$ falls into at most $k' \ll k$ of the indicator sets $A_i$ (so I'm not going to pay too much extra). As a function of $k$ and $k'$, how many queries to the oracle are now needed?


texts:
A Verifier for a language $A$ is an algorithm $V$ such that $$A=\left\{ w \space | V  \space \text{accepts} \space \langle w,c\rangle \space\text{for}\space \text{some} \space \text{string} \space c\right\}.$$

My question about this definition is what is this string $c$ stands for?

Let's say I have a graph and I want to verify if it has a clique. What would be my $c$?


texts: Unique triangulation duals of simple polygons

texts:
Given a triangulation (without Steiner points) of a simple polygon $P$, one can consider the dual of this triangulation, which is defined as follows. We create a vertex for every triangle in our triangulation, and we connect two vertices if the corresponding triangles share an edge. The dual graph is known to be a tree with maximum degree three.

For my application, I am interested in the following. Given a tree $T$ with maximum degree three, is there always a simple polygon $P$ such that the dual of every triangulation (without Steiner points) of $P$ is equal to $T$. Here, the triangulation of $P$ may not be unique, but I require that the dual graph be unique.

This is certainly true when $T$ is a path, but becomes unclear when you have vertices of degree three.


texts: Intersection between regular language and context-free language

texts:
In general, context-free algorithm are not closed under intersection but the intersection between a regular language and a CF language is known to be context-free.

My question is: does exist an algorithm to compute intersection in these special cases?

Thanks.


texts:
I once did normalization for my Computer Science project, and I had to turn 0NF to 1NF, 2NF and 3NF.

What must we actually do to convert 0NF to 1NF, 2NF and 3NF? Must we rearrange the information and then compress the info into just a few categories?


texts: how does $PATH$ being $NL$-complete help to prove $NL = coNL$

texts:
There is a proof in Sipser showing that $NL = coNL$ (theorem 8.27 in the 3rd edition).

In the proof idea, the first sentence is: "We show that $\overline{PATH}$ is in $NL$, and thereby establish that every problem in $coNL$ is also in $NL$, because $PATH$ is $NL$-complete." I'm having trouble understanding this.

Sipser did not elaborate on this, but it sounds like the logic behind this sentence is:

$PATH$ is $NL$-complete
so $\overline{PATH}$ is $coNL$-hard
and $\overline{PATH}$ is in $NL$
so $coNL \subseteq NL$

If so, why can we get 2 from 1?

More generally, since $PATH$ can be decided in $NL$ (Sipser example 8.19), why can't we just flip the result to decide $\overline{PATH}$ directly?


texts: In ontology development, where do axioms come from?

texts:
I am developing an ontology. I've got the classes, relationships and I guess I could come up with instances at this point too.

But what I'm really focused on is the axioms. I've learnt that the axioms restrict the knowledge so that reasoning can be done which then reveals the consistency or satisfiability of the ontology as well as subsumption and some other things.

I want to know: where do the axioms come from?
Is there a formal method to coming with the axioms? Do I just dream them up and kind of decide, based on my knowledge of the domain, that these things are true and ought to be represented as such? If I had to substantiate my axioms and say where I came up with them, what would I say??


texts: Why are SIFT features significantly different after simply re-sizing image?

texts:
I'm new to SIFT and was surprised by how much the features changed after resizing an image. Here's the images I used for testing:

Original:

Resized:

Cropped:

After running SIFT on those 3 images, I was surprised to find out that the original image was more "similar" to the cropped one than the resized one (I tested with both bag of words + cosine distance and the distance algorithm described in the SIFT paper).

Is that normal and expected? What would be good approach if I wanted the original and resized images to score as more similar than the cropped one? Would normalizing image size before applying SIFT help?

Edit: After drawing the SIFT keypoints on each image, I'm now seeing that the resized image seems to have less keypoints in a common than the original and cropped ones.

I am guessing I should probably normalize image dimensions before doing SIFT to avoid this issue.


texts: Overlap between theory and systems fields in CS

texts:
I have finally had some serious graduate-level exposure to CS Theory and loved it. I really enjoyed complexity theory (time and space complexity, the different classes, reductions to prove NP-Completeness), and algorithm analysis. I am still very interested in Operating Systems, software engineering, and network/information security.

My question is: What would some starting places to look into if I want to find direct overlaps between CS Theory (algorithm design and analysis, complexity theory, information theory, etc) and, OS, or software engineering? I guess I am looking for areas that might have project possibilities that will test and expand my knowledge in both theory and either OS or SE.

For Security the best one I could think of is theory of cryptography, but I am kind of at a loss when it comes to the other two.


texts: The amount of ROM needed to implement a 4-bit multiplier?

texts:
For a 4-bit multiplier there are $2^4 \cdot 2^4 = 2^8$ combinations.

The output of 4-bit multiplication is 8 bits, so the amount of ROM needed is $2^8 \cdot 8 = 2048$ bits.

Why is that?  Why does the ROM need all the combinations embedded into it?

What will be the case with RAM?


texts:
I have followed two famous book on "Automata and Formal Language Theory":

Micheal Sipser's book
Jeffrey Ullman and John Hopcroft's book

in both books, tuple level definition of Turing machine differs with each other. Although abstract level working are same but details are different. Why there is not any standard definition? Even some other books have explained the Turing machine in different way.

When we try to measure time complexity of same algorithm on these machines, exact time also differs. Why the authors/scientist have not agreed upon one standard definition?


texts:
The following is an excerpt from OS concepts by galvin.Here is the book.

Multithreading Models
Our discussion so far has treated threads in a generic sense. However,
support for threads may be provided either at the user level, for user
threads, or by the kernel, for kernel threads. User threads are
supported above the kernel and are managed without kernel support,
whereas kernel threads are supported and managed directly by the
operating system. Virtually all contemporary operating
systems—including Windows, Linux, Mac OS X , and Solaris— support
kernel threads.
Ultimately, a relationship must exist between user threads and kernel threads.

It then goes on to discuss Many-To-One Model,One-To-One Model and Many-To-Many Model.
Question :
Why there must be a relationship between user threads and kernel threads?
Does kernel thread here means a thread of the kernel(i.e OS)? I don't think so since it clearly specifies that it relates to support for threads.


texts: Neural Network | What is the purpose of hidden layers and how many should I use?

texts:
I am pretty new to Neural Networks and I have two questions about hidden layers:

1.
What is the purpose of hidden layers? I was wondering this because obviously you can get every result you want with just one weight per input, as you're performing a multiplication.

2.
How should I choose the number of hidden layers and how many cells should they have?


texts:
You are given a tree of $N$ nodes with colors assigned to each node. You need to find for each node $X$, a value $AR[X]$.

$AR[X]$ = The sum of values of $CALC(X , i)$ for each $i$ from $1$ to $N$.

$CALC(A,B)$ = Count the number of non-repeating colors in the path from $A$ to $B$.

Can somebody suggest an efficient solution to this problem?


texts: Is thread in operating system = thread function in programming languages?

texts:
I'm new to Operating System, just learnt about process and now is about to learn about threads. From what I understand,

a program is an executable file, program code
a process is a program in execution
a thread is part of a process
in a process, there might be multiple threads. e.g. MS Word
in a programming code, there is the main function and there're might be other functions also
because there is only one main function, usually the program would just run from top of the main function to down.

My question are:

Q1. Is thread in operating system = function in programming language?

Q2. Is function in programming language = thread function in
programming language?

Q3. Is thread in operating system = thread function in programming language?

Q4. Thread function allows multiple functions to be performed simultaneously, like having multiple main functions. Is this correct?

Q5. Where is thread written in operating system/ programming language?

I appreciate it greatly if somebody can explain these in simple terms, and examples from analogy or simple programming languages (C/C++/java).

EDIT:
What I mean by thread function (I'm not sure if this is a correct term) is like,

pthread.h in POSIX thread programming
thr_create, thr_join etc in Thread Functions in Solaris and Windows 9x/NT
CreateThread (included in windows.h?) in Create Threads using C in Windows.

I guess that "thread function" = "thread".

If so, then, from David's answer,

  Q2. Is function in programming language = thread function in programming language?

no.

And from a Q&A in Quora here, it says that

  Q: What is the difference between a thread in a programming language, like Java or Python, and a Linux thread?

  A: There is no difference; it is the same word with the same meaning (as opposed to one word that's overloaded to mean multiple things). The operating system will execute threads in parallel as requested by the software that creates the threads.

So, I guess that the answer for my third question,

  Q3. Is thread in operating system = thread function in programming language?

yes.

And, from POSIX Thread

  Initially, your main() program comprises a single, default thread. All other threads must be explicitly created by the programmer

so I guess the answer for

  Q4. Thread function allows multiple functions to be performed simultaneously, like having multiple main functions. Is this correct?

I think yes.

Q6. Will the program not be able to do multithreading if it doesn't include these thread functions?

I think yes.

Although I'm not sure how it is included/written in programming code that doesn't explicitly use thread functions directly like CreateThread etc., which is my fifth question.

For example, in Tetris code in C, I didn't see any "thread" word inside the code. Instead, it uses conio.h, which is from wikipedia

  conio.h is a C header file used mostly by MS-DOS compilers to provide console input/output. It is not part of the C standard library or ISO C, nor is it defined by POSIX.

Q7. So does this mean this particular programming code in Tetris code in C is single-threaded only?

Q8. Is it by including windows.h, a programming code can perform multithreading?

Please correct me if I'm mistaken.

The remaining questions are Q5, Q7, Q8.


texts: Optimal permutation of matrix rows and columns

texts: Let $M$ be a square matrix and $S(M) = \sum_{i<j} m_{i,j}$ the sum of the elements in the upper triangular part of $M$. Is there an efficient algorithm to find a permutation matrix $A$ that minimizes $S(A M A^{\top})$


texts: EM-algorithm for categorical hidden variables

texts:
I have the following model: Let's say two indepentent weighted six-sided dice $X$ and $Y$ with unknown probabilities (i.e. probability of 1 is unkown etc) and they have not necessarily the same probability distribution.

However, these are hidden variables and we only observed the outcome $S = X + Y$. I now want to use the EM-algorithm to estimate these probabilities, so we gather some outcomes $D = s_{\{1:N \}}$.

The likelihood for one outcome $n$ is given by (here $\theta = \{p_{1,x},\dots,p_{6,x},p_{1,y},\dots,p_{6,y} \})$:

\begin{align*}
p(s_n, X_n, Y_n | \theta) &= [\text{Use conditional properties}]\\
&= p(s_n \mid X_n, Y_n, \theta)\,p(X_n\mid\theta) p(Y_n \mid \theta)\\
&= \prod_{\ell=1}^6 \prod_{m=1}^6 [p(X_n = \ell\mid\theta) p(Y_n = m\mid \theta)]^{1(X_n = \ell, Y_n = m) + 1(s_n = \ell + m \mid X_n = \ell, Y_n = m)}\end{align*}

Here $1$ is the indicator function and the log likelihood is:

\begin{align*}
L &= \log(p(s_n, X_n, Y_n | \theta)) \\
&= \sum_{\ell=1}^6 \sum_{m=1}^6 \left[
    \begin{array}{l}\big[1(X_n = \ell, Y_n = m) + 1(s_n = \ell + m \mid X_n = \ell, Y_n = m)\big]\\
\qquad\times\big[\log(p(X_n = \ell \mid \theta)) + \log(p(Y_n = m\mid\theta))\big]
\end{array}\right]\,.\end{align*}

However, now I'm not sure how to proceed, i.e. doing the E and M step. We want to estimate $p(X_n = \ell)$, for $\ell=1,\dots,6$ and $p(Y_n = m)$ for $m=1,\dots,6$.

In the E step, we want to compute

$$Q(\theta, \theta_t) = \sum_{n=1}^N E_{X_n, Y_n \mid s_n, \theta_t} [L] = ?$$

And in the M step we want to compute

$$\theta_{t+1} = \arg\max Q(\theta, \theta_t)\,.$$

Any ideas?


texts: How would the ALU in a microprocessor differentiate between a signed number, -7 that is denoted by 1111 and an unsigned number 15, also denoted by 1111?


texts:
Say I have two arrays, { energy and score }, and they could have elements like this:

E: 1  3  4 7
S: 16 10 5 1

What I want is the best score with the best energy. What data structure can support inserting items in a way that I don't have have an item with less energy and less score than another item i.e. for any i,j where i!=j => score[i] > score[j] || energy[i] > energy[j]

When inserting, I do three steps:
1- if any item has more or equal score and energy, return;
2- if any item has less or equal score and energy, remove this item;
3- insert the required item.

Here are some examples:
1- insert e=8, s=1. The arrays become:

E: 1  3  4 8
S: 16 10 5 1
           ^

2- insert e=5, s=6. The arrays becomes:

E: 1  3  5 8
S: 16 10 6 1
         ^

3- insert e=5, s=11. The arrays becomes :

E: 1  5  8
S: 16 11 1
      ^    (3,10) is removed because (5,11) has more energy and more score than it.

What data structure can support this in (hopefully) O(logn) time?


texts: Subarray containing all integers from 1 to $m$

texts:
I have faced the following problem in an entrance examination, and need to verify a few results plus a question part that did not manage to get in time.
Given an array $A$ of length $n$ which contains all integers $1,\ldots,m$, the goal is to find a consecutive subarray of $A$ containing the integers $1,\ldots,m$ which is closest to the end of $A$. For example, if the array is $2,2,1,2$, then we need to return the final two elements $1,2$. We may use a procedure HAS-INTEGERS that given the first and last index of a subarray, checks whether the subarray contains all integers $1,\ldots,m$. We assume that HAS-INTEGERS can be implemented in $O(1)$.
The task, known as FIND-SNIPPET, can be solved in $O(n^2)$ by simply trying all subarrays. The problem has two parts:

Come up with an $O(n)$ algorithm for FIND-SNIPPET.
Show how to implement HAS-INTEGERS in $O(1)$.

I thought about a dynamic programming solution using the fact that the function can be expressed recursively on $m$:
FIND-SNIPPET($n,m,A$) equals FIND-SNIPPET($n,m-1,A$) extended to contain the closest $m$ (if $m$ is not already inside),
and respecting the priority to the right side in case of equal distance.
I am not sure how to get this to a pseudocode using dynamic programing, Also, I'm not sure how to implement HAS-INTEGERS in $O(1)$.


texts: An obvious approach to explaining NP != coNP, how far has it been pushed?

texts:
A recent question made me think about an obvious approach for circumventing the "algorithm is allowed to do anything" problem, when proving lower bounds. Instead of starting with a simple looking NP-complete problem, start with a powerful looking logical deduction system.

Then try to find a reasonable general term expression problem, such that equality of the terms can be decided by the logical deduction system, and inequality of the term expressions is NP-complete. (For example, Boolean algebra term expressions would work.) Then start to prove that the logical deduction system cannot efficiently prove equality of specific term instances, unless it has access to specific higher order features, like the cut-rule.

And then the goal would be to push up the required higher orders features as far as possible, i.e. beyond the cut-rule towards fully impredicative higher order logic. But already proving that you need the cut-rule would seem like a nice achievement. How far has such an approach to explaining NP!=coNP actually been pushed in the past?


texts: Consensus anomaly about read-write registers and test&set

texts:
I read this answer below and got into another question.

Why is the consensus number for test-and-set, 2?

I also read that read/write registers have consensus number 1.

But I see that in test&set (also in compare&swap) by using read write registers alone, we still arrive at consensus.

I think I am missing something very fundamental here. Need help.

The protocol in the accepted answer of the link is as mentioned below

  Suppose that we have two threads 0 and 1 that need to reach consensus.
  We could do this by letting each thread follow the consensus protocol
  below:

  Write your proposed value to A[t], where t is the thread id and A is an array of size 2
  Perform the test-and-set instruction on some register R, with R initialised to 0.
  If the return value is 0, you were first: return A[t]. Otherwise, you were second: return A[|t−1|].


texts: k-basis representation of natural numbers

texts:
(This is the problem 1.56 from Michael Sipser' Introduction to the theory of computation )

Let
$A_k(S)= \{ w |w \text{ is the k-basis representation}$
$\text{ without leading 0 of some natural number in the set S}\} $

Example : $A_2 (\{3,5\}) = \{11,101\} $

Let the statement $ P = \exists S \text{, a set of natural number where} A_2(S) \text{ is regular and }A_3(S) \text{ isn't.}   $

Is $P$ true ?

I think that $P$ is false.

Let's consider two case :

$S$ is finite :

Write a (possibly very long) regular expression which is the union of all of the k-basis representation strings of the numbers in $S$ no matter what $k$ is.

$S$ is infinite :

Construct a NFA $N$ that recognize $A_k(S)$ with :
$\text{For each symbol }e\in\Sigma\smallsetminus 0, \space$
$\delta(q_{initial},e) = q_{begin},\space q_{begin} \in F $
$\text{For each symbol }e\in\Sigma,\space \delta(q_{begin},e) = q_e ,\space \delta(q_e,\varepsilon) = q_{begin},\space q_e \in F  $

Am i correct ? (I think I'm not but I'm stuck with this, maybe I don't get the definition of $A$ correctly ).


texts:
I have a balanced $k$-ary B-tree with $N$ leaves (where N is a power of $k$ for simplicity) and I need to simultaneously locate $\ell$ leaves in it. What is the expected number of nodes I will need to traverse? Obviously for $\ell=1$ we need to traverse $\log_k N$ nodes, but the question becomes less trivial (for me) for larger $\ell$. Here is my attempt at $\ell=2$ and $k=2$.
Without loss of generality, the first query is in the leftmost leaf. First, we traverse the root. Then, out of all the possible places where the other query one can be, there's a $2^{N-1}/2^N$ chance that we will need to follow different paths for each of the nodes, and that would mean the total nodes to be traversed is $2 \log N - 1$. In the rest of the cases we have the same problem only we are down to $\frac{N}{2}$ leaves, only we have already traversed the root. So the expected number of leaves would be
$$
\begin{align}
f(2) &:= 2 \\
f(N) &:= \frac{1}{2}(2 \log N - 1) + \frac{1}{2}(f(\tfrac{N}{2}) + 1) = \log N+\frac{f(\frac{N}{2})}{2}
\end{align}
$$
So that would become
$$
f(N) = \sum_{i}\frac{\log N-i}{2^i}
$$
I might be wrong on my result. Is there a general formula for this?


texts: How to find a rectangle of maximum value in a $n \times m$ binary grid

texts:
Given a $n \times m$ grid $G$, with each grid square having a value 0 or 1, find a rectangle $R$ in $G$ that maximizes $R_1 - R_0$, where $R_0,R_1$ are defined as follows:

$R_0$ = the total number of 0's in $R$
$R_1$ = the total number of 1's in $R$

The brute force solution is to compute the value $(R_1 - R_0)$ for all possible rectangles, then select the one with maximum value. There can be $1/4 \lbrace nm(n+1)(m+1) \rbrace$ possible rectangles in a $n \times m$ grid. [Source]

Is there a smarter way to do this? Can we relate this problem to the Maximal Rectangle Problem?

This problem turns out to be similar to this one. We just have to replace 0s with -1s, then find the rectangle with largest sum.  Using the techniques shown there, the problem can be solved in $O(nm \cdot \min(n,m))$ time.  Can we do better?


texts: MST with degree constraints on some node

texts:
While preparing for an algorithms exam I came across the following problem in a practice test:

Let $G = (V,E)$ be a connected, undirected graph with weighted edges (all weights are rational numbers but not necessarily all unique) and let $v$ be some node in $G$.

Design an algorithm that finds a minimum spanning tree of $G$ where $\deg(v)=2$ if one exists or indicates if there is no such tree.

Full credit will be given for solutions with the same time complexity as Prim's algorithm ($O(|E| + |V|\log |V|)$). Partial credit will be given for solutions whose time complexity is $|V|\cdot$Prim, and minimal credit will be given for solutions with greater time complexity.

The first step in any solution must be to use Prim or Kruskal's algorithm to find the target weight for such an MST. From there, though, I've tried a number of different methods of approaching this problem but all the successful ones require halting an existing MST algorithm before it's done, i.e. prioritizing all $v$'s edges, running Kruskal until $v$''s degree is two, then deprioritizing them and continuing the algorithm, etc.

The problem is that my professor flat-out refuses to accept answers that involve stopping an algorithm in the middle, insisting that this would require one to re-prove the correctness of the entire algorithm.

Does anyone have a solution? The problem has been eating at me for a few weeks now and I haven't been able to find an answer on the internet anywhere. The professor said she won't tell us the answer and I suspect she intends to put this question on this or future exams.

Thanks very much in advance for your time.


texts:
Computer science is a science and as a science each thesis can be refutable. So, why there is no "major" counter-thesis?
After all, Einstein was a well known "genius" and has lived a long life and he has got many opponents. Why isn't it the same case for Turing?


texts: Closed (visited) list in state-space search - How do I make it efficient?

texts:
As part of an assignment for an AI class that I'm taking, I'm need to solve a puzzle on a 4x4 grid using breadth-first search (each element can take on 12 different values). There is a maximum of 4 moves for each state. Needless to say, after 30-or-so moves, the number of nodes (each representing a state) in the queue gets too large for most (any?) computer to handle, since many nodes are duplicates.

The solution, as far as I know, is to add all visited nodes to a "visited list." This makes it possible to compute without running out of memory, but it takes forever. Why? Because for each node that I add, I have to make sure that it's not in the list of visited nodes. For a somewhat complex puzzle, this list can get really long. Let's say the list gets to 500000 nodes, which is feasible. That means that for every new node I add to the queue, it needs to be compared to 500000 nodes to make sure that it isn't identical to any node in that list. This takes a really long time to compute. It solves the problem, but I'm pretty sure I have the wrong idea about how to approach this to actually make it efficient.

I know BFS usually isn't a very good approach to these kinds of problems, but it's part of the assignment. It's only about actually solving the puzzle, but I'm interested in knowing if there is a way to make it more efficient. In general, I mean. I'm sure that I could tailor the program to make it solve this specific puzzle much faster, but what I want to know if there's some idea that could be applied to all problems.

Any help is greatly appreciated!


texts: Algorithm for computing a sum with multiples of specific values

texts:
I am attempting to compute a known sum or closest value to that sum using the multiples of a subset of numbers. In this approach I want to minimize the multiples or coefficient.

For instance if I have the number 120 and I have a set of 50s and 20s, I would get

120 = 2*50 + 1*20.

The set of numbers can be limited however, so if I only have 1x50 and 6x20s, I will get

120 = 6*20.

Furthermore if I have only 5x20s, since I want to minimize the coefficient, I would have

110 = 1*50 + 3*20.

Note that in this case, the value is the closest value to the sum. If the sum can be achieved, that takes precedence over having the closest value to the sum with less number of multiples.

Is there a known algorithm to achieve this result?


texts: what is the 'x :=' part mean in a hoare triple?

texts:
In Hoare logic, there's a thing called a Hoare triple, e.g.$$
\begin{array}{ccccc}
\{x = 2\} & & x := x+1 & & \{x = 3\}
\end{array}.
$$
What does '$x :=$' mean?


texts:
per this post

  $t = x^2$ means the problem is solvable in "Polynomial" time.

per this post

  in the form

  $$a_{n}x^{n}+a_{n-1}x^{n-1}+\dotsb +a_{2}x^{2}+a_{1}x+a_{0} {
> \boldsymbol{=0}}$$

  plug in $n=100000000000$ with $a_n=1$ and $a_k=0$ for all $k \neq n$

  then we see that $x^{100000000000}$ is a polynomial

  it doesn't matter if its 2, 3, or a billion, as long as the n is a finite number

in this context, does $t = x^{100000000000}$ still mean the problem is solvable in "Polynomial" time?


texts: P=NP giving a deterministic algorithm for SAT

texts:
I'm trying to prove the following problem:

Prove that if $P=NP$ then there is a polynomial time algorithm for the following problem:
INPUT: A boolean formula $\phi$.
OUTPUT: A satisfying assignment of $\phi$ if $\phi$ is satisfiable. If $\phi$ is unsatisfiable, return $false$.

My proof:
If $P=NP$ then $SAT$ can be decided in polynomial time. Run $SAT$ on $\phi$. If it returns $false$, reject. Else, nondeterministically select a boolean assignment. If it satisfies $\phi$, return it.
The algorithm is in $NP$, but because $P=NP$, it is also in $P$.
Is my proof correct? I'm asking because the textbook gave a different answer, and I want to know if my proof is correct, and if not, where does it fall?


texts: I am working with grammars that need to be in Greibach Normal Form. I want to check whether a grammar recognises a string. In order to perform CYK the grammar would have to be converted into CNF. Is there an established way of carrying out such conversion?


texts:
What does it mean to multiply or divide polynomials?

I have used them so many times, in error correcting codes, cryptography, etc. but it was never clear to me what would be a graphical representation/ interpretation.

I have always pondered what did it mean when someone multiplies a line with a curve to get another hyperplane of a bigger dimension.

I know the formulae and properties of polynomial multiplication & division, I am specifically looking for a graphical/algebraic interpretation of it.


texts: Finding a cycle in a graph with the biggest value (the sum of all edges)

texts:
I am trying to solve this problem: we have an oriented, weighted graph and we have to find a cycle with the biggest weight. Weight of a cycle is the sum of all edges forming the weight. The preferred solution is via backtracking.

My idea was to :

backtrack all combinations of vertexes (0s and 1s representing whether vertex is in a subgraph)
then verify if the subgraph is connected
then verify if a source vertex of any edge is in the subgraph is used only once
and then connecting the first vertex with the last one, thus forming a cycle.
If the sum of all weights is > then max, max = sum.

However, this solution doesn't work correctly on any almost any vertex. It finds a cycle, but it never finds the biggest one. Could you help me fix my algorithm? Thanks!


texts: How to define an approximation algorithm when it fails?

texts:
I have an NP-hard problem P where we are trying to minimize some objective function subject to some constraints. Problem P is very hard in the sense that even finding a feasible solution is NP-hard! (i.e., finding a solution that satisfies the constraints is NP-hard).

Let OPT denotes the optimal algorithm for P. That is, OPT will return, given an instance of P, the best possible solution, or will report none exist. Now, suppose I designed an approximation algorithm, denoted ALG, that solves P (of course not to optimality).

Given an instance I1 of P, ALG may fail to find a feasible solution when actually one exists and of course OPT finds it. So, if I would like to measure the performance of ALG in terms of its approximation ratio, how would I do that? Should I ignore the instance I1? As far as I know, an approximation algorithm, by definition, must return, for any instance of the problem, a solution that has a bounded value compared to the optimal value. But in this case, given an instance of P, ALG may not be able to find any value and hence reports none.

For short, if an algorithm fails to find a solution to a problem, how do we measure its performance ratio? Is it even considered an approximation algorithm? Is there something related to this in the literature?


texts: Why does the insertion-sort algorithm have a quadratic instead of a quasi-linear time complexity?

texts:
Can someone explain how the insertion sort have quadratic time complexity and not quasi-linear time complexity in the worst-case?

Even in the case of a reversely sorted list, it's not like it'll have to compare each element with all the other elements. For example in [4, 3, 2, 1], 4 won't be compared with anything. 3 will only be compared with 4. 2 will be compared with 4 and 3 but not 1. And only 1 will be compared with all the other 3 items.

How is this O(n^2) and not O(nlogn)? What am I missing here?

My implementation of Insertion Sort:

const insertionSort = (arr) => {
  for (let i of arr) {
    for (let x = arr.indexOf(i) - 1; x >= 0 && arr[x] > i; x--) {
      arr[x + 1] = arr[x];
      arr[x] = i;
    }
  }


texts: Help with a difficult expected runtime recurrence

texts:
I developed an algorithm and have a recurrence for its runtime; I want to show the expected runtime is $O(\sqrt{n})$.
At each iteration $i$, I have a random variable $k_i$ that is equal to the number of heads after flipping $\frac{n}{2^i}$ coins minus $\frac{n}{2^{i+1}}$ (i.e. a binomial distribution centered at 0 with width $\frac{n}{2^i}$). The runtime of my algorithm is then given by the following recurrence:
$$B(0) = 0$$
$$B(i) = \max\{B(i-1)+k_i, 0\}$$
When $B(i)$ is large, the negative and positive $k_i$ can cancel each other out, so intuitively one should be able to come up with a pretty good bound on $\mathbb{E}[B(n)]$, but I have no idea where to start.


texts: Can all $O(n)$ problems be solved without nested loops?

texts: There are examples of algorithm implementations that contain nested loops but are of complexity O(n), and some of them have corresponding implementations that contain no nested loops. So here comes a question, can all such implementations be simplified or converted to an implementation with only top layer loops? Namely, can all problems that have an $O(n)$ algorithm be solved with an algorithm without nested loops?


texts: Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?

texts: Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number of nodes or vertices. The Dijkstra's algorithm has a complexity of O((|V| + |E|) * log(|V|)) where E is the number of edges. Compared to A star, the Dijkstra's does not rely on properties of any heuristic which makes them popular. But I am trying to understand the advantage of Dijkstra's over Grassfire. Are there practical reasons why this is the case? Or am I simply seeing more cases of Dijkstra's compared to Grassfire due to the application areas such as navigation that I am working on?


texts:
I tried watching http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-4-heaps-and-heap-sort/ to understand heaps and heapsort but did not find this clear.

I do not understand the function of max-heapify. It seems like a recursive function, but then somehow it's said to run in logarithmic time because of the height of the tree.

To me this makes no sense, because what if you run max-heapify on a min-heap? It'll have to reverse every single node, which I don't see how this can be done without it touching every single node.


texts: TSP heuristics for limited distance information

texts:
this is my first question on ComputerScience beta. :)

I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site.

Problem:

  I'm looking for TSP heuristics in the case of limited information about the edges, for example: I have $n$ nodes but can only ask for $~\sim4n$ distances. My graphs are metrically and I can make an estimate in advance with the euclidean distance, but those estimates might be very bad.

Question:

  So what are the TSP-Heuristika for those distance-matrices?

Thanks in advance.


texts: How do you correctly write this sentence as a CTL formula?

texts:
Sentence: From every reachable state it is possible to reach a state where $p$ is true.

How do you write this sentence as a CTL formula? So far I only dealt with CTL syntax and trees but maybe it will also be asked in a test how you convert a sentence to a CTL formula..

So I've read that $AX$ means all next.

Then $AXp$ should mean in all next states $p$ is true.

Now I only need the first part of the sentence: From every reachable state it is possible to reach

But how would this be expressed and how do you connect it with the $AXp$ I got?

I hope you can help me because on the internet I couldn't find some example like that? : /


texts: Prove if $\{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$ is regular or not

texts:
$$L = \{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$$

To Prove: If given language is regular or not.

I know that it is not a regular language but I am not able to come up with the string which I can use in the pumping lemma to prove that it is not regular.

We can also divide $L$ into two parts:
$$\begin{align*}
L_1 &= \{x^iy^jz^k \mid i \le 2j\}\\
L_2 &= \{x^iy^jz^k \mid j \le 3k\}\,,
\end{align*}$$

so I just need the strings to be used in the pumping lemma for $L_1$ and $L_2$.


texts: Algorithm to reconstruct sentence from shuffled string

texts:
Given a dictionary of words, and given a string which is an anagram of concatenation of group of words from the dictionary, is there an efficient algorithm to find valid set of  words that can form this string ?

eg1: dict = [ 'dog', 'cat', 'cow' ]
s = 'ocdgatcta'
ans = [ 'cat', 'cat', 'dog' ]

If we join the words in the answer to form the string, we can see that it is an anagram of the input string s

eg2: dict = [ 'dog', 'act', 'cat', 'cow' ]
s = 'ocdgatcta'
ans = [ 'cat', 'cat', 'dog' ] or [ 'act', 'cat', 'dog' ] or [ 'act', 'act', 'dog' ]

In the above case any of the above list is valid as the string formed by them is an anagram of the input string s

We can brute force but there seems to be overlapping sub problems. Can this be solved in polynomial time ?


texts:
Kindly suggest what would be the loop invariant in the following algorithm ( I need it for the purpose of proving the partial correctness of the algorithm).

MinDistance(A[0...n-1])
dmin <- ∞
for i = 0 to n-1 do
   for j= 0 to n-1 do
     if i ≠ j and |A[i] - A[j]| < dmin
       dmin <-|A[i] - A[j]|
return dmin

another algorithm for which the loop invariant is to be discovered is

MinDistance2(A[0...n-1])
dmin <- ∞
for i = 0 to n-2 do
    for j= i+1 to n-1 do
       temp <-|A[i] - A[j]|
       if temp < dmin
          dmin <- temp
return dmin


texts: Definition of "properly partial" versus "total" value types

texts:
In the Foundations chapter of Elements of Programming (Stepanov and McJones, 2009), this paragraph appears:

  A value type is properly partial if its values represent a proper subset of the abstract entities in the corresponding species; otherwise it is total. For example, the type int is properly partial, while the type bool is total.

I have a hard time understanding what this means and have been unable to find any good explanations of these terms on the Internet. What are properly partial and total value types?


texts: can network layers communicate between each other?

texts: in a network architecture can two layers in different machines communicate between each other using some protocols, without having to go through the layers below, if yes how briefly ?


texts: Is the following language context-free? $L= \{a^nb^m| m\geq2^n\}$

texts: Is $L=\{a^nb^m|m\geq2^n\}$ a context-free language?


texts:
Introduction

Step One

I wrote a standard backpropegating neural network, and to test it, I decided to have it map XOR.

It is a 2-2-1 network (with tanh activation function)

X1  M1
        O1
X2  M2

B1  B2

For testing purposes, I manually set up the top middle neuron (M1) to be an AND gate and the lower neuron (M2) to be an OR gate (both output 1 if true and -1 if false).

Now, I also manually set up the connection M1-O1 to be -.5, M2-O1 to be 1, and
B2 to be -.75

So if M1 = 1 and M2 = 1, the sum is (-0.5 +1 -0.75 = -.25) tanh(0.25) = -0.24

if M1 = -1 and M2 = 1, the sum is ((-0.5)*(-1) +1 -0.75 = .75) tanh(0.75) = 0.63

if M1 = -1 and M2 = -1, the sum is ((-0.5)*(-1) -1 -0.75 = -1.25) tanh(1.25) = -0.8

This is a relatively good result for a "first iteration".

Step Two

I then proceeded to modify these weights a bit, and then train them using error propagation algorithm (based on gradient descent). In this stage, I leave the weights between the input and middle neurons intact, and just modify the weights between the middle (and bias) and output.

For testing, I set the weights to be and .5 .4 .3 (respectively for M1, M2 and bias)

Here, however, I start having issues.

My Question

I set my learning rate to .2 and let the program iterate through training data (A B A^B) for 10000 iterations or more.

Most of the time, the weights converge to a good result. However, at times, those weights converge to (say) 1.5, 5.7, and .9 which results in a +1 output (even) to an input of {1, 1} (when the result should be a -1).

Is it possible for a relatively simple ANN which has a solution to not converge at all or is there a bug in my implementation?


texts: Constructing a list of functions/formulas which describes a set of grid points in a 3D matrix

texts:
Given a 3D matrix of size $N \times N \times N$, let $\mathcal{S}$ be a set of points in the Matrix and $\mathcal{S}'$ be the complement of $\mathcal{S}$. Can we find a set of equations of the form:

$F: (f_1 \land f_2 \land \ldots \land fn)$

where $f_x$ is of the form

$f_x \implies ai + bj + ck + dN + e \text{ } \{<,>,=,\neq\} \text{ } 0$

$f_x$ is true if a point satisfies the aforementioned function and false otherwise

where $i,j,k$ are the indices of the grid points in the Matrix (which vary from 1 to $N$) and $a,b,c,d,e$ are integers such that

$F(\text{all points in }\mathcal{S}) = True$
$F(\text{all points in }\mathcal{S}') = False$

For example:
If $N = 4$, and $S = \{(1,1,1),(2,2,2),(3,3,3),(4,4,4)\}$, we can say that the functions $f_1 \implies i-k=0$ and $f_2 \implies j-k=0$ are one solution for this set.

Ideally we are interested in a solution with the minimum number of equations, but this is not necessary.


texts:
I'm stuck on this semaphore exercise (it's a exam question of a previous exam and I'm studying for that exam):

There are three processes: A, B and C. Process A wants to execute method a(); Process B wants to execute b(); and Process C c();. The Processes are each started once.

The execution of a(); must not overlap with the execution of b(); or c();. However b(); and c(); must always be able to run concurrently. The order of execution must not be forced.

I can use as many semaphores as I want. With every solution I tried so far I always get the case that when e.g. b(); is executing and a(); is waiting, that I will also block c();. The solution is probably simple but I'm too blind to see it.


texts: Prove or disprove that a any language L and its complement have the same amount of equivalence classes

texts:
The question is:

Given a language $L$ (not necessarily regular), prove or disprove that $Eq(L) = Eq(\overline{L})$.
Where $Eq(L)$ is the amount of equivalence classes the language L has, and $\overline{L}$ is the complement of $L$.

My intuition says the statement is true, but I don't know how to prove it.


texts: Blockchain cipher suitable for preschoolers

texts:
Is there a cipher that well suited for preschool-aged children to work out on pencil and paper, to learn concepts of block chains?

It must have the following requirements:

Able to be easily verified
a. For example, Joe submitted red, but Suzy submitted blue. Everyone knows Suzy is right...somehow. (Color-specific results are not required but used to illustrate that the cipher need not be number-based, although that is fine too)
Able to be easily ciphered with pencil and paper, or drawings, or in a child's head
Able to use a previous result (minus the genesis of course), to create a 'blockchain' of sorts

The cipher may be low-complexity. It does not matter if it is easily broken.

Most ciphers are geared towards being easy to verify, but difficult to decipher. This situation is a bit different in that it does not have to be difficult to decipher. Out of the box ideas are quite welcome.


texts: How to check if a list of XY coordinate meet the safety distance to each others?

texts:
My background is not CS so sorry for using improper term. But basically I want to check if a point on XY plane is "too close" to any other points, and do so with every points. In another words, if I draw a circle with radius R at every points, would any circle cross other circles on the plane.

I want to code this in Python, if that matters.


texts: Computing number of block reads given relational algebra statement

texts:
So I'm just starting to learn about query processing and such in databases and I'm having some trouble.  I don't really understand how to compute the minimum number of block reads given a relation and a query I guess you could say.  If anyone could help me out, it'd be much appreciated.  Here is an example that I'm working on:

R1(A,B,C) A is a primary key and C is a foreign key to R2.C
R2(C,D,E) C is a primary key
R1 has 20,000 records, with 200 records per block. There is a primary B+-tree index on
A with height h = 3
R2 has 45,000 records, with 4,500 records per block. There is a primary B+-tree index
on C with height hC = 3 and a secondary B+-tree index on D with height hD = 2.

Find the minimum number of block reads for each statement.  I can only hold one block of memory for each relation at a time.

Where B=1(R1)
Where C=1(R2)

I'm not looking for answers.  I'm looking for explanation of how to actually do it and guide me along the way.  Aka equations, etc. It's kind of difficult to find anything beneficial online at all.


texts: Find the computational complexity of the given program

texts:
int seq(int n)
{
   if(n == 0 || n == 1)
       return n;
   return(seq(floor(n/2)) + seq(ceil(n/2));
}

Find the computational complexity of the above program.

I have tried doing it in the following way:
$$\begin{align*}
T(0) &= 1 \\
T(1) &= 1 \\
T(2) &= 2T(1) = 2 \\
T(3) &= T(1) + T(2) = 3 \\
T(4) &= 2T(2) = 4 \\
T(5) &= T(3) + T(2) = 5 \\
&\vdots
\end{align*}$$

So the thing I have observed here was:

$$T(n) = n$$

However I am not sure if this result/approach is even somehow correct, is it? If not can someone show me the way how to approach problems like this one? Thanks


texts: How to prove that the lower bound of the Huffman coding problem is $\Omega(n \log n)$?

texts:
how to prove that the lower bound of the Huffman coding problem is $\Omega(n \log n)$?
Here Huffman coding problem is Huffman encoding.
For example,
Input:
A string with different characters, say “ACCEBFFFFAAXXBLKE”
Output:
Code for different characters:
Data: K, Frequency: 1, Code: 0000
Data: L, Frequency: 1, Code: 0001
Data: E, Frequency: 2, Code: 001
Data: F, Frequency: 4, Code: 01
Data: B, Frequency: 2, Code: 100
Data: C, Frequency: 2, Code: 101
Data: X, Frequency: 2, Code: 110
Data: A, Frequency: 3, Code: 111

I already saw that we can know that the bound of the sorting problem is $\Omega(n \log n)$ by using decision tree.
the number of leaves: $n!$
(the number of leaves in a half tree with a height of $h) \leq 2^h$
$\Rightarrow n! \leq 2^h \Rightarrow h \geq \log n!$
$\Rightarrow \log n! \fallingdotseq n \log n - n = \Omega(n \log n)$
So I thought I could also use the decision tree to get the lower bound of the Huffman coding problem but I am not sure how to construct the decision tree for Huffman coding problem, like how many leaves are needed,...
Please tell me how to construct the decision tree or is my attempt to tackle this proof wrong?


texts: Why is the set for which a decision problem is true called a "language"?

texts:
When we have a decision problem, " does $f(x)=1$ hold?", we call the set of strings $x$ for which the answer is yes a "language".

Why this strange terminology?


texts: Algorithm to compute the difference between two geometric paths

texts:
I want to compute the difference/intersection between two paths. By path I mean a list of points that can be created by the following actions on a graphics context:

move to x, y
line to x, y
Bézier to x, y

How could I do that? What's the best algorithm to compute the difference/intersection between two paths, A - B? What if there's a simplification where B is guaranteed to be a rectangle?


texts:
I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the following claim:

L-attributed definitions include all syntax-directed definitions based on LL(1) grammars.

What is the intuition or logic behind this statement?
In the later sections they show that L attributed grammars can be easily implemented by a DFS search algorithm of the parse tree (and hence easily by a predictive parser [recursive/non recursive]). $^\dagger$
Is it so that since LL(1) grammars can also be parsed by predictive parser and by the logic of $\dagger$, the authors make the claim?


texts:
Show that a language is decidable iff some enumerator enumerates the language in decreasing order.
I know a language is decidable iff some enumerator enumerates the language in the standard string order (increasing order), but I am not sure if this makes sense in decreasing order. Can anyone prove it?


texts: Software for proving tautology with steps

texts:
I'm looking for a software which can prove a tautology using logical equivalences.
It should be able to show each step. So you can follow the chain of reasoning.
Here is an example:
\begin{align}
(p\to q)\to(\neg q\to\neg p)&\equiv\neg(\neg p\lor q)\lor(q\lor\neg p)\tag{material implication}\\[1em]
&\equiv\neg(\neg p\lor q)\lor(\neg p\lor q)\tag{commutativity}\\[1em]
&\equiv \neg M\lor M\tag{$M:\neg p\lor q$}\\[1em]
&\equiv \mathbf{T}.\tag{negation law}
\end{align}


texts: Complexity of an instance of a NP-complete problem

texts:
I am trying to prove the NP-Completeness of problem [A].

I know there is a well-known NP-Complete problem called problem [B].

I can model [A] into an instance of [B] ([B] is a very general problem and when I assign some edges a weight value then it becomes [A]).

Is this sufficient to say [A] is NP-Complete?


texts:
new to automata theory and this is quite difficult for me so I'd appreciate a hint in the right direction if possible.

We want to find a regular expression for the language $L$ over $\Sigma = {a,b,c}$ where $L$ is the language of all strings of even length, contain $a$ at least once, and after the final $a$ letter there are no $b$s.

for example - $bcbabaca$ is a valid word.

Best thing I could come up with is somewhat akin to $R = ((a+b+c)(a+b+c))^*a((a+b+c)(a+b+c))^*$ and it has to be something like that since we need to control the length of the word to make it even, but still its no good and im having difficulties.


texts: Perceptron - Generalization Bounds & Compression Bounds

texts:
A distribution $P$ over $\mathbb{R}^{d} \times\{-1,+1\}$ being $(\gamma, R)$ -separable. We now let $\mathcal{P}_{\gamma}$ denote the set of all $(\gamma, 1)$ separable distributions. For a distribution $P \in \mathcal{P}_{\gamma},$ we let $\mathbf{w}_{P}$ denote the unit length (ie. $\left.\left\|\mathbf{w}_{P}\right\|=1\right)$ vector that satisfies
$$
\underset{(\mathbf{x}, y) \sim P}{\mathbb{P}}\left[y\left\langle\mathbf{w}_{P}, \mathbf{x}\right\rangle \geq 1\right]=1
$$
Let $\mathcal{A}_{\text {perc }}$ denote the perceptron algorithm. For a distribution $P \in \mathcal{P}_{\gamma},$ we now define $H_{P}$ to be set of hypotheses that the perceptron algorithm may output given a sample from $P .$ Clearly, we have:
$H_{P} \subseteq\left\{h_{\mathbf{w}} \in H_{\operatorname{lin}} \mid \mathbf{w}=\mathcal{A}_{\text {perc }}(S)\right.$ for some $S$ with $y\left\langle\mathbf{w}_{P}, \mathbf{x}\right\rangle \geq 1$ for all $\left.(\mathbf{x}, y) \in S\right\}$
Prove that
$$
\mathrm{C}\left(H_{P}\right) \leq \frac{1}{\gamma^{2}}
$$
Combine the results from the previous steps to prove the following statement: Let $\epsilon, \delta \geq 0 .$ There exists a constant $c,$ such that, for all distribution $P \in \mathcal{P}_{\gamma},$ for all samples sizes
$$
n \geq c \cdot \frac{\left(1 / \gamma^{2}\right) \log (\epsilon)+\log (\delta)}{\epsilon}
$$
we have
$$
\underset{S \sim P^{n}}{\mathbb{P}}\left[\mathcal{L}_{P}\left(\mathcal{A}_{\mathrm{perc}}(S)\right) \leq \epsilon\right] \geq 1-\delta
$$
Also state the corresponding generalization bound for the perceptron algorithm that the fundamental theorem implies and compare the two bounds.
Stuck at : I have proved that perceptron algorithm stops after $
\mathrm\  \frac{1}{\gamma^{2}}
$
I don't know how to go further. Any help is appreciated.


texts: What is the simplest/smallest subset an OOP language like C#/JavaScript that is Turing-complete?

texts:
This question is not meant to be too theoretical or nitpicky. I have experience programming, so I'm trying to get a better understanding of what it takes to get Turing-completeness by using my intuition about practical programming languages.

Basically: What minimal elements of a language like Javascript do we need to have Turing completeness, and why? (I'm pretty sure we don't need interfaces or subclasses, etc).

Extra question: Is there a simple, natural polynomial-time reduction from a language like Javascript/C++/C# to a Turing machine?


texts: Can Von Neumann bit extraction be made more efficient?

texts:
I want to develop a previous question regarding Von Neumann debiasing /randomness extraction.

The typical solution (as posted) is to take pairs of throws and output a bit based on a comparison of the two throws.  This is the most simple solution.

My problem is that it's very wasteful of input entropy.  The biased die can have values 1 - 6, but only a single bit is output.  So 2 x log2(6) bits in, produce 1 bit out.  It's actually less as the throws may be discarded if identical.  What happens if the die is a D & D D120 (Disdyakis triacontahedron - 120 sides)?  You'd be inputting 13.8 bits of entropy, and getting (practically) less than 1.  That's incredibly wasteful of precious entropy.  Is there a clever variant of Von Neumann that can output more than a single bit at a time?

My particular interest is actually not a bigger die, but more of them.  For example you simultaneously throw 6 biased regular dice.  Can you get better than 1 purely random bit out per pair of throwing rounds?