texts: Approximate Nearest Neighbour Problem in Spherical Setting

texts:
There has been significant literature in solving the (Approximate) Nearest Neighbour Problem in the spherical setting in the $\mathbb{R}^n$ using Angular and Spherical LSH and other lattice sieving techniques. A proper definition of the problem is found in the image below.  (The problem definition is borrowed from Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing by Laarhoven and Weger 2015. Here is the IACR page for the paper. )

(Refer to Sieving for shortest vectors in lattices using angular locality-sensitive hashing
by Laarhoven 2015. The link is in the comments.)

I was curious if there is a way to have a similar spherical setting for the approximate NN problem for the finite field $\mathbb{Z}_2^n$. Particularly, I was wondering if there was a sphere definition relevant to $\mathbb{Z}_2^n$ that could be analogical or atleast very similar to the one in Definition 4. The one in definition 4 allows entire lattices to be embedded on the sphere i.e. $P$ is a lattice.  The proposed distance measure could either be the $l_2$ norm or the hamming distance.
It does not seem that it can be simply translated into finite fields.

I apologize if this is a naive question or does not make sense because I am a first time undergraduate researcher who is not very familiar with this forum and the level of questions asked here.


texts:
I was converting a DFA to regular expression with the help of state equations and came up with this regular expression. How do I further reduce this regular expression?
$$b+aaa^*b+abb^*+a$$
I can feel it's same as $$a^*b+ab^*$$ but how do I proceed to simplify the first one to the second mathematically?


texts: Derive a while loop runs in $\Theta( \sqrt{n} )$

texts:
I know for a fact that algorithm A runs in $\Theta(\sqrt{n})$, but how does one derive that fact?

Algorithm A

i = 0
s = 0
while s <= n:
    s += i
    i += 1

Here is what I am thinking. We know that A is upper-bounded by O(n), as we increment $s$ by more than 1 in each iteration. We also know that it must be lower-bounded by $\log n$, as we increment $s$ with by something less than $2^i$ in each iteration. (Correct me if I am wrong, these are just my thoughts ...).

Now, what else can we say about A? How do we derive that its time complexity is $\Theta(\sqrt{n})$?


texts: Why isn't Busy Beaver Infinite for n < trivial k?

texts:
I am clearly not understanding the Busy Beaver function. Why wouldn't it be infinite for n > k,
while(true)
{
  print("1");
}


texts: The unicode characters under the "Basic Latin" unicode block from U+0020 to U+007F are the characters that characters we use in English. However, the "Latin-1 Supplement" block from U+00A0 to U+00FF is an extension of the "Basic Latin" block and includes characters that are used in some languages. For example, the Spanish language use all the characters from U+00A0 to U+00BF as well as the letter "Ñ/ñ" (U+00D1 and U+00F1), which is pronounced like the "ny" in "canyón". So, how did some languages get the characters under the Latin-1 supplement block?


texts:
I think you can create the complementary language that is an element of DSPACE($f(n)$), where $f(n) \geq \log(n)$ by adding a step to the algorithm that reverses the answer. By that the function $f(n)$ does not change, therefore DSPACE($f(n)$) is closed under complement.

I know that most likely my answer is wrong. Can someone explain why?


texts: If P = NP, do these NP-complete problems reduce to these specific easier versions?

texts:
I am trying to understand reductions and NP-completeness from Algorithms by Dasgupta et al.
Chapter 8 has the table below and I am wondering:

if  $P = NP$ does each of the problems on the left reduce to the easy problem (in $P$)in its immediate right?

The book mentions that

the problems on the left are all difficult for the same reason! At their
core, they are all the same problem, just in different disguises! They are all equivalent:

does this imply that the problems on the right are also the same problem but in different guises? Can they be solved the same way like solving SAT for NP-complete problems? If so, what's the equivalent of SAT for problems in $P$ ?  I understand that SAT reduces to all problems in $NP$  but is there a problem in $P$ that sort of holds the same position as SAT in $NP$?

Does the Rudrata/Hamiltonian path reduce to minimum spanning tree if $P=NP$? This was asked in a true-false question and couldn't get it right. The options were: true, false, true if $P=NP$, true $P \neq NP$. In my opinion, the Rudrata/Hamiltonian path could be reduced to a spanning tree and not necessarily the minimum spanning tree as the Rudrata/Hamiltonian path only needs to find a path that connects all the nodes without the constraint of minimizing total of edge weights. Is this reasoning correct?


texts:
How to answer on many requests by type:

  Count amount simple paths passing through chosen edge in an acyclic undirected graph using dynamic programming?


texts: Is the difference of two context-free languages still context-free?

texts:
i am asking myself the following question:

Assuming: A and B are context-free languages, then A - B (difference) must also be context-free language, right?
but I do not know how to prove it.


texts: Can such a Turing-recognizable language exist?

texts:
Suppose $\Sigma = \{a,b\}$. Is the following claim correct?

  There exists a Turing-recognizable language $L \subseteq \Sigma^*$ such as its complement is not Turing-recognizable, and for all $n \in \mathbb{N}$ it contains exactly $n$ strings of length $n$.

I'm kind of lost here. Any help would be appreciated.


texts: An Exact Method for Solving Small Instances of XORSAT

texts:
I have a couple of small instances for XORSAT for which I am to design and implement an exact method. However, there are a few catches. It is guaranteed that there always exists and answer but I need to find the one solution with the minimal (non-zero) number of TRUE variables.

As I understand, XORSAT can apparently be solved in polynomial time through the Gaussian Elimination method but I simply cannot apply the special conditions of this problem (the minimal number of TRUE variables) and I'm wondering if I could potentially get some help on that.

The instances of XORSAT that I have are not completely random, they all consist of a number of variables that if XOR'd together will always yield FALSE. I.e., all of the clauses are in the form of $x_1 \oplus x_2 \oplus ... \oplus x_i = 0$ which would translate into the equation $x_1 + x_2 + ... + x_i = 0\space(mod 2)$.

At first, I tried to apply a greedy method, taking the two most repeated variables in all of the clauses and forcing the value TRUE on them, then propagating their values through all of the clauses and repeating the same method on the remaining unsatisfied clauses but that was fundamentally flawed.

Any help is tremendously appreciated.


texts:
Others have studied the following question: given a set of words $w_1,w_2,\dots \in \Sigma^*$, find a regular grammar (or a context-free grammar) that generates all of those words, is "natural" in some sense, and is as small as possible.  In the special case where we have a single word $w \in \Sigma^*$, if the grammar generates exactly the word $w$, we can think of this as a compression algorithm that compresses the word $w$ to the grammar produced by this inference algorithm.  Of course, each word is a one-dimensional sequence of symbols.

Now consider a two-dimensional array of symbols, say an array $A[1\ldots m, 1\ldots n]$ where each $A[i,j] \in \Sigma$.  Is there any corresponding algorithm that could be used to find a grammar of some sort that generates $A$?  Could this be used as a compression algorithm for compressing images, i.e., one that compresses a two-dimensional image to its corresponding grammar?

I'm not even sure what kind of grammar would be suitable.  Is there an analog of regular or context-free grammars that generates a two-dimensional output instead of a one-dimensional output?  I've done some searching, and haven't found anything obvious.

Of course we could linearize the image, by concatenating the rows of the array, to get a one-dimensional sequence, and then apply any of the above techniques -- but this does not preserve locality.  In other words, elements that are vertically adjacent will no longer be near each other after this transformation.  So this transformation does not seem useful.
Perhaps we could build a quad-tree over the array and then consider tree automata over that quad-tree?  Is there a grammar inference algorithm for such tree automata over quad-trees?
Alternatively, it seems like there might be a natural extension of context-free grammars to two-dimensional output: just make the right-hand side of each rule be a two-dimensional array of terminals and non-terminals of arbitrary size, and then apply the obvious generation algorithm.  Do such grammars have a standard name?  Is there a grammar inference algorithm for such grammars?


texts: Ehrenfeucht-Fraïssé games, possible mistake in example

texts:
I was reading up on Ehrenfeucht-Fraïssé and came by this example at http://www.math.cornell.edu/~mec/Summer2009/Raluca/lesson3.html

Shouldn't there be a line between b4 and b2 (or b3 and b1), otherwise I don't see how the duplicator has a winning strategy in 3 rounds. Is this a mistake or ami I missing something?

thank you.


texts: Worst-case recursion depth for guessing numbers in a Sudoku puzzle when certain polynomial-time deduction rules are used

texts:
So for an arbitrary $n^2 \times n^2$ Sudoku puzzle, there are rules for inferring values and auxillary information in cells that run in polynomial time, e.g. using the filled in values to check to see if only one number is possible for a cell, using the filled in values to check if only one cell in a given row/column/square can contain a particular number, eliminating a number as a possibility for a row/column outside of a square if the number must lie in the row/column within the square, (and vice-versa for eliminating possibilities within a square), and taking advantage of the fact that if there are $k$ cells in a row/column/square that can only contain a particular subset of $k$ numbers, then no other cells in the row/column/square can contain those numbers. Presumably there are other polynomial time rules too.

The rule/strategy I want to exclude from this list is guessing a fixed number of cells' values, and checking to see if a contradiction is found or a complete valid puzzle is obtained. So, if we consider a certain reasonably rich set of polynomial time rules except for that one, what is the worst-case known recursion depth for how many cells' values need to be guessed simultaneously in order to make progress in a puzzle? Is this known for classical $n = 3$ for a reasonably rich certain set of polynomial time rules (e.g. the rules I listed above), and more interestingly for general $n$?


texts: Is the certificate for primality testing polynomial in the length of the input?

texts:
If we were to assume that primality testing was in NP.

What would the certificate be, so that a polynomial time verifier can check the number X is indeed prime?


texts: Algorithm to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$

texts:
We have An array of $3n$ elements. we want to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$. We can solve this problem of $M(n)$ space and $T(n)$ time complexity. We want to find $M(n)$ and $T(n)$ as functions of $n$.
Note that $x$ and $y$ are not in array. for example if the array is $1 , 2 , 3, 4 , 5 ,6$ we can have $x=2.5$ and $y=4.5$. Also $x$ and $y$ are obviously not unique and we just want one number for each of them that satisfy the conditions. The array is not necessarily sorted.

For this problem, I was thinking of using order statistic and find $n$ and $n+1$ and $2n$ and $2n+1$ elements. But the problem seems odd to me. I know Selection algorithm is $O(n)$ but this problems seem more complex than just saying that.

It is the problem of a quiz of DS course (Of an Iranian University) but it seems like it is from a reference book. I want to know the answer of this question or reference to know what the question really wants and maybe finding the answer this way.


texts: Closure Properties between different Language Classes

texts: I am trying to understand closure properties between different language classes. For example, if L1 is regular and L2 is recognisable, then is L1 intersection L2 decidable? My answer is that L1 is also recognisable and therefore L1 intersection L2 is recognisable. However, this cannot guarantee that it is decidable. Is this a correct solution?


texts: if (dis)proving a conjecture on graph theory can be done just by a counter example then can every (dis)proof be mapped actually to a counter-example?

texts:
Suppose we have a conjecture on graph theory that can be (dis)proved by means of a counter example, then, is it true that every alternative (dis)proof of the conjecture can be mapped to a counter example?

This is in the general case, but for instance, can any proof that the hadwiger's conjecture is false be mapped to a counter example, i.e., a particular graph?

Or,

Can any proof about a purported property $P(L)$ of a language $L$, susceptible of being (dis)proved by a counter example, be mapped to a particular word, say $w$ meaning $w$ a counter example, i.e., $P(L):=FALSE\;$  since $w$ exists?


texts:
I am a Front-End Developer with several years of experience as well as I have my B.S. in Computer Science. I am doing research and pursuing my MS in Computer Science. However, I am somewhat struggling to word my career objective correctly and in a fashion in which I could be considered for admittance into Grad School. How could this snippet be modified to accomplish the goal while remaining under 150 characters:

  I have always been fascinated with disassembling and reassembling objects to figure out how they work. When I was ten, my mother brought home several desktop computers. I figured out how to remove all of the components and combine or reinstall them, all while keeping the computers in an operable state. This was the beginning of a constantly growing interest with computers and how they operate. My interests range from hardware to operating systems, and current employment in software engineering.


texts: Has category theory had an impact on computer science?

texts:
I've only learned bit of category theory, but so far its relation to type systems seems mostly descriptive. For example, you really don't need to know about coproducts to come up with the idea of union types.
I'm looking for references to ideas in computer science that were arrived at due to results in category theory. I'd be especially interested in results in areas other than PL such as machine learning.


texts: Does Herbrand's theorem mean any first-order logic formula can be expressed in CNF?

texts:
Herbrand's theorem shows that any formula of first-order logic can be expressed as a disjunction of quantifier-free formulas of first-order logic.

Is this equivalent to saying that Herbrand's theorem shows that any first-order logic formula can be expressed in Conjunctive Normal Form (CNF)?


texts:
Assume I have a list of $N$ surfaces $\{S_i\}, i \in [1,N]$ which may or may not overlap.

I also have a boolean function $F(S_{i_1},\dots,S_{i_k})$ (with $1 \le k \le N$) which tests whether all surfaces $S_{i_k}$ overlap (or if they were discrete sets, then $F$ would test whether they contain a common element). In other terms: $F(\{S_{i_k}\})=\;\; (\;\cap_{j=1}^{k} S_{i_j} \;\;!=\;\;\emptyset \;)$.

I now consider the "set of maximum overlaps", $L_\rm{max}=\{O_1,\dots,O_m\}$, where each $O_j$ is a set with $n(j)$ elements being surfaces that all share a common intersection. More specifically: $O_j=\{S_{j_1},...S_{j_{n(j)}}\}$ with $\cap_{i=1}^{n(j)} S_{j_i} \ne \emptyset$ (or equivalently $F(O_j)=\rm{True}$).

$L_\rm{max}$ is unique once defined through the following two constraints that it must satisfy:

a) Each surface must appear in at least one overlapping set $O_i$ of $L_\rm{max}$.

b) Each overlapping set $O_i$ in $L_\rm{max}$ must be "maximal" in the sense that there cannot exist a surface $S_j$ not part of $O_i$ and for which its intersection with the intersection of all surfaces in $O_i$ is not empty.

One may write this definition of $L_\rm{max}$ more formally as follows:

$L_\rm{max} := \; \{ O_j \}\;\rm{with}\; O_j=\{S_{j_1}\dots S_{j_{n(j)}} \} \;|\;$

$\;\;\; \forall j \; \cap_{i=1}^{n(j)} S_{j_i} \ne \emptyset \;,$

$\;\;\; \forall i \; \exists\; j\; \rm{s.t.}\; S_i \in O_j\;,$

$\;\;\; \forall j \; \not\exists\; r\; \rm{s.t}\; (\; S_r \notin O_j \; \rm{and}\;S_r \cap (\cap_{i=1}^{n(j)} S_{j_i}) \ne \emptyset\;) $

Now, the problem is to identify the algorithm building $L_\rm{max}$ and requiring the least expected number of calls to the function $F$, assuming that any legal solution set $L$ is equally likely before the problem is investigated by successive calls to the function $F$.

The above sounds complicated but it is visually very simple to illustrate. I therefore include below a graphical representation of the problem for 5 surfaces (but please answer the abstract problem, not the particular realisation below):

In that example, the solution set $L_\rm{max}$ is:

$\{ \{S_1, S_2, S_3\},\; \{S_3, S_4\},\; \{S_5\} \}$

And here are some examples of the output of the function $F$:

$F(S_1, S_2)=\rm{True}$

$F(S_3, S_4)=\rm{True}$

$F(S_3, S_5)=\rm{False}$

$F(S_1, S_2, S_3)=\rm{True}$

$F(S_1, S_2, S_3, S_4)=\rm{False}$

$F(S_2, S_4)=\rm{False}$

$F(S_i)=\rm{True}, \forall i$

etc...

Note that I am curious as to what is the exact answer to this set-theoretic puzzle with no reference to the particularity of the example above (e.g. the surface $S_i$ could very well be discrete sets too).
My hope is that someone may recognise this problem to be isomorphic to some other known mathematical problem with an established solution.

In practice however, my academic research would actually benefit from a solution tailored to the case of convex volumes (but with parametric equations of higher degree than quadratic and in an arbitrary number of dimension).
In particular, I would be very interested if someone knows how to cast the derivation of the set $L_\rm{max}$ into a single convex-constrained optimisation problem.

Also, an algorithm proven optimal is of course not required, rather just an algorithm featuring a less disastrous complexity than the one of the naive implementation I came up with so far (which saturates around N=10 and I would need around N=100).
Maybe this problem really is NP hard after all, but the question remains as to what is the algorithm of minimal expected complexity...


texts:
i know that resources duplicate is solution to Structure Hazard but what about code scheduling ....
Can code scheduling considered as a solution to Structure Hazard ?
with Example please .


texts: Learning rule of multilayer neural networks

texts:
Suppose we have a 2-layer neural network completely connected with $d^{(0)}$ input units, $d^{(1)}$ hidden units and $d^{(2)}$ output units. We consider the error function given by $J(w) = \frac{1}{2}\sum_{k=1}^{d^{(2)}}(t_k-c_k)^2$, where the vector $t = (t_1,\dots,t_{d^{(2)}})$ represents the labels and $z = (z_1,\dots,z_{d^{(2)}})$ represents the values obtained by the network. Suppose that the inputs to the second layer are calculated as $z_k = \sum_{j=0}^{d^{(2)}}y_j w_{kj}$, where $y$ represents the hidden layer output.

I want to know which are the learning rules between hidden and output layer, and between input and hidden layer, for a given activation function $\theta$.

Based on SGD, the learning rule consists in adding to the weights the gradient ot the error function.

For the first one I have tried this. I need to compute the gradient, so I derive $J(w)$ respect to the weight $w_{kj}$ and apply the chain rule:

$$\frac{\partial}{\partial w_{kj}}J(w) = \frac{\partial(\frac{1}{2}(t_k-z_k)^2)}{\partial w_{kj}}=\frac{\partial(\frac{1}{2}(t_k-z_k)^2)}{\partial z_k}\frac{\partial z_k}{\partial w_{kj}} = -(t_k-z_k) \frac{\partial (y_jw_{kj})}{\partial w_{kj}} $$

But I'm not sure about how to continue. If $y_j$ is not dependent of the weight $w_{kj}$, then the derivative turns into $-(t_k-z_k)y_j$, but is this right? Would this be the learning rule for the weights between hidden and output layer?

And for the learning rule between input and hidden layer I don't know how should I start. Any idea would be appreciated. Thanks.


texts: Can independence numbers of box products of cycles increase after stabilizing?

texts:
Is there an evidence or a proof that the independence of strong products of graphs can increase after stabilizing?

I am interested in odd cycles only.

Let $C_n$ be an odd cycle and $\alpha(G)$ represent independence number of a graph $G$.

Let $C_n^m$ be $m$-times strong product of $C_n$.

Now say $$\alpha(C_n^{m_1m_2})=\alpha(C_n^{m_1})^{m_2}.$$
That is $m_1m_2$-times strong product of $C_n$ has same independence number as $m_1$-times strong product of $C_n$ raised to $m_2$. For example,  $\alpha(C_5^{4})=\alpha(C_5^{2})^{2}=25$.

Then is it possible $$\alpha(C_n^{m_1m_2m_3})>\alpha(C_n^{m_1})^{m_2m_3}\mbox{ or }\alpha(C_n^{m_1m_2m_3})>\alpha(C_n^{m_1m_2})^{m_3}?$$

In the example above, we have violation of strict inequality since we have:$$\alpha(C_5^{8})=\alpha(C_5^{2})^{4}=625\mbox{ or }\alpha(C_5^{8})=\alpha(C_5^{4})^{2}=625.$$


texts: Unambiguous context-free grammar for strings with at least as many a's as b's

texts:
I have designed this Grammar but it is ambiguous:

$$S\to aSbS \mid bSaS \mid aS \mid\epsilon$$

Would anyone help me make it unambiguous? Assume the alphabet is $\{a,b\}$.


texts:
Let $A$ be an array of $n$ integers containing the numbers $\{1, 2, \dots , n\}$ in
some arbitrary order. For integers $i$ and $j$ such that $1 ≤ i < j ≤ n$, let
$\mathrm{Reverse}(A, i, j)$ be a procedure that reverses the subarray $A[i], A[i +
1], \dots , A[j]$ of the array $A$ while leaving the remaining elements of the
array unaffected.
Prove that the following algorithm sorts the array $A$
and also terminates.
for i := 1 to n − 1
  while A[i] ≠ i do
    Reverse(A, i, A[i])

I am able to prove this if the elements are in descending order. Why does this algorithm work for an arbitrary order?


texts: Choosing potential function in amortized analysis of the dynamic array

texts:
Suppose we have a dynamic array with some initial capacity $c_{initial}$ (i.e., the dynamic array with zero elements will have this capacity). The $add$ operation is modified the following way:

  New array capacity $c^{'} = c*scale$, where the $scale$ is some constant if the number of elements in the array is $s = scale^{k}$ (i.e., the array is full, and the capacity must be increased $scale$ times).

I am trying to show that the $add$ operation has constant complexity using the following potential function:  $\Phi=scale*s-c+c_{initial}$ - $\Phi(0)=-c_{initial}+c_{initial}=0$.

where $s$ is the array size (number of elements) and $c$ - array capacity ('generalized' version of the popular case when the array capacity doubles - $\Phi=2*s-c$ and initial capacity $c_{initial}=0$).

However, I stuck with the case when the scale factor is bigger than 2, for example, for $scale=4$ case (and initial size = 0) the cost of $add$ then the array is full is $c_{i}^{'} = c_i + \Phi_i - \Phi_{i-1} = (s+1)+(4*(s+1) - 4*c)-(4*s-c)=5+s-3*c=5-2*c$, which is not a constant.

Is there some way besides the guess-and-check, 'brute-force' way to come up with an appropriate potential function?

Another possible modification of an $add$ operation is to increase the capacity on some constant, and I don't see any pattern to the potential function in this case.


texts: On the termination of mutually recursive functions

texts:
In Finding Lexicographic Orders for Termination Proofs in Isabelle/Holl the authors construct a method for proving termination of functions based on constructing a matrix that registers for each row the recursive calls in the body and for each column a measure. The matrix itself contains the information about the decrease of the measure on that specific call.

As an example of mutually recursive functions (page 46) they give:

even 0 = True
even Suc n = odd n
odd 0 = False
odd Suc n = even n

they state that they convert these functions into a single function over the sum type nat+nat. Apparently this transformation is explained in this thesis (page 117).

How would the transformed function look like?

They go on stating that this transformation give the following proof obligations:

  wf ?R

  $\land$n.(Inr n,Inl Suc n) $\in$?R

  $\land$n.(Inl n,Inr Suc n) $\in$?R

where Inl,Inr are the injection functions for sum types. Similarly,

Do you understand why these proof obligations are derived? What are their meaning?

Finally, the step in which I am most interested. They introduce measure functions in this sum types in order to proof termination. The set of measures for $t_1 + t_2$ is:

$M(t_1+t_2) =\{case_+ m_1 m_2 | m_1 \in M(t_1),m_2 \in M(t_2)\}$

and they explain that this means that the measures are built taking all combinations for measures of $t_1$,$t_2$ and combining them with a case combinator for sum types which has signature $case_+ :: (\alpha \Rightarrow \gamma) \Rightarrow (\beta \Rightarrow \gamma) \Rightarrow (\alpha + \beta \Rightarrow \gamma)$.

Could you explain what the case combinator does?

So summarizing, I need a clarification on the construction idea, assuming no knowledge on sum types.


texts: Efficient insertion of deterministic acyclic finite state automaton (DAFSA) into a full-text search index?

texts:
I have a problem where I can easily construct a set of deterministic acyclic finite state automata (DAFSA) and I need a full-text search index, e.g. a suffix tree/array, over all the words encoded by these automata.
Is there an efficient algorithm for this? By efficient I mean that the complexity must not depend on the on the total number of words encoded in the DAFSA which may get very large. Consider the following example:
(all edges are directed from left to right)

  a1 --- a2 ... a{n-1} --- an
 /   \ /               \ /   \
S     X                 X     T
 \   / \               / \   /
  b1 --- b2 ... b{n-1} --- bn

In this example there are $2^n$ distinct paths from S to T, e.i. if the nodes were labelled with characters it would be an DAFSA encoding $2^n$ words. Still, the number of vertices is just $2(n+1)$ and the number of edges $4n$.


texts: Is this reduction from 3D-MATCHING to PATH SELECTION invalid?

texts:
I'm a bit confused about some proof that PATH-SELECTION-PROBLEM  is NP-complete (Problem 9, chapter 8 in "Algorithm Design" by Tardos and Kleinberg) that I found in some solution manual here:

https://github.com/weimin/CS-180/blob/master/Algorithm%20Design%20(Kleinberg%20Tardos%202005)%20-%20Solutions/Algorithm%20Design%20-%20Kleinberg%20%26%20Tardos%20-%20Solutions/chapter_08/problem%20(8).pdf.

The PATH-SELECTION PROBLEM is defined as follows: for a given directed graph and a set of paths we ask if it is possible to select at least $k$ paths so that no pair of paths share any node.

The solution uses polynomial reduction from 3D-MATCHING problem defined as: for distinct $n$-sets $X, Y, Z$ and a set of triples $T$ $\subset$$X \times Y \times Z$ we ask if there is an $n$-subset of $T$ that covers $X \cup Y \cup Z$.

For a given arbitrary instance of 3D-MATCHING, the proposed reduction constructs a directed graph $G=(V, E)$ such that $ V := X \cup Y \cup Z$ and for each triple $\langle x, y, z \rangle $ from $T$ it adds edges $\langle x, y \rangle, \langle y, z \rangle $ to $E$ which define set of paths $\mathcal{P}$. It then claims that there are $n$ legal paths in $G$ iff there exists $n$-subset of distinct triples from $T$ (which is equivalent to saying that it covers sum of $X, Y, Z$).

My confusion is that adding edges as above produces too much paths that yield a solution to PATH-SELECTION having no correspondence in 3D-MATCHING. Let's consider $n=2$, $T= \{ \langle x_{1}, y_{1}, z_{2},  \rangle, \langle x_{2}, y_{1}, z_{1},  \rangle, \langle x_{2}, y_{2}, z_{2},  \rangle \}$. There is no solution for 3D-MATCHING here but in reduction described above we have paths $\langle x_{1}, y_{1}, z_{1},\rangle $ and $\langle x_{2}, y_{2}, z_{2},\rangle $.

EDIT:
I think I missed one point: over all paths $\mathcal{P}$ the solution defines a subset $\mathcal{P'} \subset \mathcal{P}$ of the paths that strictly correspond to the triples and then we are only allowed to search for a solution in $\mathcal{P'}$. But this is still odd as it reformulates the PATH-PROBLEM adding up additional constraint ...


texts: Looking for clarity on step in fractional knapsack problem proof

texts:
I'm reading through the proof for the fractional knapsack problem presented here: https://www.cs.rice.edu/~nakhleh/COMP182/Knapsack.pdf
I follow the proof until the definition of the new set $Q = \langle q_1, q_2, ..., q_n \rangle$

for every $1 \leq i<j: q_{i}=o_{i} ($also $q_{i}=y_{i})$ which is constructed as follows:
$q_j=y_j$
For $i=j+1$ to $n$

\begin{array}{l}
- d^{\prime} \leftarrow \min \left(q_{i}, d\right) \\
- q_{i} \leftarrow q_{i}-d^{\prime} \\
- d \leftarrow d-d^{\prime}
\end{array}
I don't understand where the $q_{j+1...n}$ elements come from. We only fill $Q$ up to $q_j$, but to fill $q_{j+1}$ we reference $q_i$ which is undefined — should it be 0? What am I missing?


texts:
Being a programmer I appreciate the errors given by a compiler for a programming language and come to rely on the compiler's error as a safety net.

In learning category theory I would like to have some tool that also acted as a safety net letting me experiment with diagrams and pointing out my mistakes when I make one. Does such a tool/app exist?

I know this is more of a math question, but I am asking here because I am looking for an answer from those with and understanding for computer science.


texts: Proof that the Blank Tape Halting Problem is undecideable

texts:
I have seen a few proofs that the Blank Tape Halting Problem is undecideable, however I'd like to check if the following is a valid proof (and if it isn't why not)

Proof: Suppose that the Blank Tape Halting problem is decideable, then there exists a universal turing machine $M$ that decides it. So given any turing machine $T$, $M$ decides if $T$ halts after being started on a blank tape.

Now let any turing machine $T$ and input $w$ be given. Construct a new turing machine $R$ (with start state blank) such that $R$ halts on a blank tape if and only if $T$ halts on $w$.

Then if $M$ takes $R$ as input, $M$ decides if $R$ halts on a blank tape and thus decides if $T$ halts on $w$. Since $T$ and $w$ were chosen arbitratily $M$ decides the Halting problem, a contradiction, so the Blank Tape Halting Problem is undecideable. $\square$.

Is there anything wrong with my reasoning above? I assume that there must be some key detail that I'm overlooking, or that my proof isn't completely rigorous

I guess the problematic argument may be the following

  Construct a new turing machine $R$ (with start state blank) such that $R$ halts on a blank tape if and only if $T$ halts on $w$.

Since I haven't explicitly constructed such a turing machine $R$ in my proof above.


texts: What is the reasoning behind magic constancs in hash code calculations found in programming practice?

texts:
In real-world programming, we frequently need to compute hash codes for complicated objects. The main desired properties are that the values should

be deterministic and
have few collisions.

Let's assume we have access to robust hashing for basic data types such as integers, strings, etc. How do we combine multiple such hash codes to a single one, say for an array or a struct with several properties?

I immediately went for XOR-ing all "child" codes, figuring that the "spread" of the original hash function should be maintained, roughly.
Apparently, I'm not alone.

However, if you google around, you find other approaches.

Here an answerer proposes adding hash codes after perturbing them by some multiplication.
This asker uses XOR but multiplies the individual codes with some numbers, apparently consciously choosing "large" primes.
Here, the author states that "[things] have low values (favour the lower bits), so they should be combined with a multiplication to spread them across a wider bit range of the hash code".

The reasons given, if any, seem vacuous to me. Does multiplying already "random" values with a (small) constant really serve any purpose? Does it matter if the factor is a prime (which everybody seems to assume)?


texts:
Let's assume we have an arbitrary language $L'$ and let's define the language $L = \{1^n | \text{The number of strings in } L' \text{ of length } n \text{ is odd }\}$.

Is $L\in PSPACE^{L'}$?

I tried saying that I can define a determinstic machine that holds a counter and that goes over all possible strings of length $n$, which is $2^n$, and for each such string it asks the oracle whether it is in $L'$. If yes it increases the counter, and if not, it does not. Then, at the end, checks if the counter is odd, and accepts if so. Else, it rejects.

The problem is that even in $PSPACE$ I can not go over all strings since that would not be a polynomial amount of space, except if I am allowed to override the previous string I checked and that would count only as $n$ space, but I am not sure..

Another part of the question asks if $L \in NP^{L'}$, but that clearly is not the case.


texts:
I've been recently dealing with the classical problem of finding the minimum vertex cover in a bipartite graph. The common approach is to set direction to all edges and run DFS from all vertices of the left part outside of the matching. However, this solution seems too clever for me.

I read this in this link. Can any body explain it to me with simple example.
https://codeforces.com/blog/entry/63164

" The minimum vertex cover should contain exactly one vertex for every edge in the maximum matching M. So let's assign a boolean variable for every edge in M, say, xi = 0 if the i-th edge adds its left end to the vertex cover. One can build all the dependencies over these variables. For example, if there exist edges  and , while w is not saturated by M, we have to set xi equal to 0, because there is no other way to cover the edge (u, w). All the other cases are handled trivially.

As a result, we obtain a full system of restrictions for the set of variables. Finding an arbitrary valid assignment is a classical 2-SAT problem. So we have basically reduced the minimum vertex cover problem to 2-SAT without thinking too much. "

what I dont understand is this

I don't understand the variables. I have an edge from maximum matching then I might have both the endpoints of that edge in the vertex cover. But this scheme does not allow this.

This is the graph I have two edges in the maximum matching.

For the first edge I took left vertex in the cover

x1=0(according to the blog in the link)

for the second edge I took right vertex in the cover x2=1

How final 2-sat will be true?

Can anyone explain what will be the relation between x1 and x2 ?


texts: Proving that the scramble of a regular language is context-free

texts:
For strings $w$ and $t$, if they have the same length and comprise the same characters (namely, they are two permutations of these characters), then $w\sim t$. For a string $w$, define an operator $\operatorname {SCRAMBLE}$ such that
  $$\operatorname {SCRAMBLE}(w):=\{t\mid t\sim w\}, $$
  and for a language $A$,
  $$\operatorname {SCRAMBLE}(A):=\{t\mid t\sim w, \exists w\in A\}.$$
  Prove that: given an alphabet $\Sigma:=\{0,1\}$, for any regular language $L$, $\operatorname {SCRAMBLE}(L)$ is a context-free language.

I have tried to use the pumping lemma of regular language to show that it satisfies the pumping lemma of context-free language after the $\operatorname {SCRAMBLE}$ operation, but I failed to find the pumping substring of $\operatorname {SCRAMBLE}(L)$.
I have also tried PDA construction but to no avail. Can anyone help me with it? Any answer or hint will be appreciated. Thanks in advance.


texts: Is the langauge of (descriptions of) DFAs that accept $\Sigma^*$ decidable?

texts:
Is $L = \{\langle A\rangle\mid A\text{ is a DFA and }L(A) = \Sigma^*\}$ decidable?

I know that $L'=\{\langle A,w\rangle \mid A\text{ is a DFA and }w\in L(A)\}$ is decidable, but I'm not sure if this is related.


texts: Is a stack overflow detected by hardware or software?

texts: Is it the task of the software (operating system) to detect stack overflows or is a stack overflow detected in hardware, causing an exception in the CPU?


texts:
Let $A$ be a set of integers: $A=\left \{ x_1, x_2...x_n \mid 10<x_i<100\right \}$

A valid permutation $x_{i_1}x_{i_2}...x_{i_n}$ is a permutation that holds the following property:

For every adjacent numbers $x_{i_j}x_{i_{j+1}}$, the unit's digit of $x_{i_j}$ is equal to the ten's digit of $x_{i_{j+1}}$.

For example, if $A=\left\{ 24,87,48,12 \right \}$ then $12-24-48-87$ is a valid permutation, whereas if $A=\left\{ 46,83,58 \right \}$, there is no valid permutation of $A$.

Now, given such a set $A$, I need to find an algorithm that prints a valid permutation if such exist, otherwise, it returns that there is no valid permutation of $A$.

I need to solve it using a graph, with a reasonable complexity, and I've been instructed to use some of the Eulerian path's properties, so it might play some role in getting the solution to that problem.

This is what I have in mind so far:

Setting a directed graph $G=(V,E)$ with: $V=\left\{ x_1, x_2...x_n\right \}$, and $E$ will contain all the arcs $(x_{i_j}, x_{i_{j+1}})$ s.t. $x_{i_j} x_{i_{j+1}}$ is valid (i.e the unit's digit of $x_{i_j}$ is equal to the ten's digit of $x_{i_{j+1}}$).

Now, if a valid permutation of $A$ exist, there is a path in $G$ that travel through every vertex only once.

There are two things that troubles me with this thought. First of all, it has nothing to do with Eulerian path, or Eulerian graph, or Eulerian anything, which makes me believe I'm way off target here. Second, the complexity of such algorithm is a nightmare: creating $G$ alone is $O(|V|^2)$, but that's nothing compared to finding some path in $G$ that traverse through all vertices only once, considering that I can't determine at which vertex to start the search.

Does anyone have an idea on how to approach this problem? Are there any observations I fail to see? Maybe searching the graph differently, or maybe even setting the graph in some other configuration?


texts:
I'm trying to understand Section 3: L1 Cache Missing in the paper Cache Missing for Fun and Profit. I'm stuck on trying to figure out how the covert channel is being constructed.

Specifically, I don't understand the following construction (the especially confusing parts are highlighted):

  A covert channel can therefore be constructed as follows: The Trojan
  process allocates an array of 2048 bytes, and for each 32-bit word it
  wishes to transmit, it accesses byte 64i of the array iff bit i of the word is set. The Spy process allocates an array of 8192 bytes, and repeatedly
  measures the amount of time needed to read bytes 64i, 64i + 2048,
  64i + 4096, and 64i + 6144 for each 0 ≤ i < 32. Each memory access
  performed by the Trojan will evict a cache line owned by the Spy, resulting in lines being reloaded from the L2 cache, which adds an
  additional latency of approximately 30 cycles if the memory accesses
  are dependent.

I don't understand why the byte 64i needs to be accessed, or what the relevance of bit i being set is in this context. And I don't understand why the Spy process would have the pattern of reading bytes 64i, 64i + 2048, 64i + 4096, and 64i + 6144.

EDIT (to incorporate D.W.'s suggestion): I get the general gist of how a covert channel is created, but not exactly. There are two processes that agree to send and receive messages from each other. They agree upon some set in a cache which they would use to contend for data.
The first process then floods the cache set with its data, and so does the second process. But the second process tries to measure the time it takes for it to access the resource (the set in the cache that is being contended for). If the access is fast, then it reads that as a certain bit, and if its slow, as the opposite bit.


texts: How many prefix code we can find for a given distribution of probability?

texts: A source emits 5 signals s1, s2, s3, s4 and s5 whose probabilities are as follows: 1/3, 1/3, 1/9, 1/9, 1/9, 1/9. How many prefix codes we can construct on A={a, b, c}? And how many are there with the same performance (efficiency)?


texts: Applying the context-free pumping lemma to a language with crossed nestings

texts:
For proving language $\{a^nb^mc^nd^m \mid n,m > 0\}$ is not context free.
Do I have to use $z = a^pb^pc^pd^p$ as pumping lemma string where $p$ is pumping length?

Or do I have to use a string that would reflect than $n$ and $m$ does not have to be the same length?


texts:
Parallel computing is not new but it is becoming common now a days. This is essentially driven by the need of the users (they need to process more data now) and also because of physical limitations on chip designing e.g power dissipation limits forcing to manufacturers to move to multicore CPUs.

My question is how is the parallel computing different now from what they used to do 30 years back?


texts: graph theory analogue of rectangular matrix

texts:
Graphs are usually defined as a set of vertices $V$ together with a set of edges $E$ consisting of elements $V \times V$. I'm interested in a slight generalization of this, where instead one has two sets $V$, $W$ and the edges are taken from $V \times W$. The adjacency matrix of such an object would be rectangular, as opposed to the adjacency matrix of a regular old graph, which is square. Is there a name for this?

I'm interested in this because I'm writing a data structure to represent a graph in terms of its partitioning into sub-graphs for the purposes of parallel computation. For example, given a graph $G$ on a vertex set $V$, we can partition $V$ into disjoint subsets $V_1$ and $V_2$; $G$ is then naturally divided into two subgraphs $G_1$ and $G_2$ describing connections among $V_1$ and $V_2$ respectively, and a "rectangular graph" $H$ describing connections between $V_1$ and $V_2$. I'd like to give the class a name that makes sense.


texts: Admissibility of heuristic in the $A^*$ algorithm

texts:
The CS188 course from Berkeley goes to great length in explaining why the optimality of $A^*$ algorithm is conditioned by the admissibility of heuristic.

Note: admissibility of heuristic means that:

$$\forall n, 0 \leq h(n) \leq h^*(n) $$

With $h^*(n)$ being the true optimal distance of $n$ to the goal.

The course's proof reasoning is sound and makes perfect sense.

However, this example uses a heuristic that is not admissible. For instance, the distance between the start state and the goal state is only $h^* = 2$ while the heuristic of the start state is $h = 17$ (see the example with the 8-puzzle, using Nilsson heuristic). Obviously, $17 \gt 2$ and therefore the heuristic is not admissible.

However, after having implemented the algorithm and tested it, it seems that it is able to find the optimal solution each time. Trying to alter the heuristic function only makes it worse than optimal.

So, if the admissibility of the heuristic a necessary condition for the guaranteed optimality of $A^*$, how comes that this example seems to refute this?

Did I miss something? Or perhaps, does the condition on the admissibility means that sometimes, the algorithm will be optimal even with an unadmissible heuristic, but only an admissible one guarantees the optimality?

I'd be curious to hear any thought about that.


texts:
Given a $n\times m$ matrix $A$ of integers, find a sub-matrix whose sum is maximal. If there is one row only or one column only, then this is equivalent to finding a maximum sub-array.

The 1D version can be solved in linear time by dynamic programming. The 2D version can be solved in $\cal O(n^3)$ by looping over all pairs of columns and using the 1D algorithm on the array whose length is the number of rows in the matrix where each position $r$ holds the sum of the elements at row $r$ between the two columns.

If the matrix is given by:

\begin{pmatrix}
  1 & -2 & 0 & -1 \\
  5 & 43 & 31 & 78 \\
  -45 & -12 & 19 & 9
 \end{pmatrix}

Then for the pair of columns $(0,2)$, the max sub-matrix sum can be found by using the 1D algorithm on the array (top to bottom):

\begin{pmatrix}
  1-2+0 & = & -1 \\
  5+43+31 & = & 79\\
  -45-12+19 & = & -38
 \end{pmatrix}
Does anybody know of a $\cal O(n^2)$ algorithm for solving this problem?


texts: Ford-Fulkerson Algorithm not "pushing back" flow

texts: I am told that with every flow network, the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges (i.e. never “pushes back” the flow on any of the edges). I am wondering how that can be possible. Can we choose augmenting paths that allow us to never "push back"?


texts: Still not understanding why the Knapsack Problem does NOT have a polynomial-time solution

texts:
All the explanations for why the $O(nW)$ DP algorithm that solves the Knapsack Problem is NOT polynomial repeat the same thing: it is the length (in bits) of the input that matters, not its value/magnitude. The solution has the following structure:

# some preprocessing
for i in range(n):
    for w in range(W):
        # compute stuff

They repeat the same example: $W=10_2=2$, but $W=100_2=4$, i.e. every extra bit doubles the length of $W$. Here's my confusion

Why can't I apply the same logic for $n$?


texts: Clique number of a graph given its order and average degree

texts:
Let $G$ be simple graph of order $N$, and let $\bar{d}$ be its average degree.

  Find the maximum value of $\omega(G)$ (the clique number of $G$) as a function of $N$ and $\bar{d}$.
  Find the minimum value of $\omega(G)$ as a function of $n$ and $\bar{d}$.
  What are the minimum and maximum values of $\omega(G)$ when $G$ is $d$-regular?


texts: Expressing functions using the arithmetic dictionary

texts:
i have seen in the "logic to cs" class i take - a theorem that states: "every recursive (computable) function $f$ can be expressed using the arithmetic dictionary {$C_0, C_1, f_+(,), f_x(,), R_\le(,)$} with the structure {$D=\mathbb{N} ,C_0=0,C_1=1, f_+(a,b) =a+b, f_x(a,b)=ab, R_\le(a,b) = a\le b $}"

But we didnt prove this theorem because a part of the students didnt take the "computational models" course (i did take it though)

Where can i find a proof for this theorem? Thanks in advance!


texts:
we are given an Array

Array size <= 10^4 .

0 <= A[i] <= 15

We need to partition the array into 4 subsets (each subset can have zero or more elements ). Take xor of each subset and sum those xors.

for example,  one subset could have indices 0, 3, and 7, and another subset could have indices 1, 2, and 4
find the max sum.

4^n approach is very expensive.

there are only 16 different values of xor so for each value of xor=X we can search in array if is it possible to partition the array such that we get xor=X.


texts: How to adapt proof of the ND time hierarchy theorem for alternate definition of NDTM?

texts:
For reference, the version of the nondeterministic time hierarchy theorem in question is this one:

The relevant portion of the proof in question (also from Arora-Barak) is here:

Arora-Barak define a NDTM as identical to a deterministic TM except that NDTMs have two transition functions such that either may chosen nondeterministically and used at each time step. However, the definition of a a NDTM with which I am more familiar is more in the flavor of Goldreich's text, which instead defines a transition relation, allowing more than two nondeterministic choices to be made at each time step.

My question is: how can the above proof be modified to work for Goldreich's definition of a NDTM? All of the proofs I have found that rely on the Goldreich definition (including Goldreich's own proof) only prove the coarser, logarithmic version of the nondeterministic time hierarchy theorem. Despite the equivalence of these two definitions, I can't find a way to work around the reliance of the proof on claim that $M_i$ has $2^{(f(i) + 1)^{1.1}}$ branches of computation, which holds assuming that only two nondeterministic choices are possible at each time step.

At first I figured the proof could be modified to suit the Goldreich definition simply by changing the base 2 in $f(i+1) = 2^{(f(i) + 1)^{1.1}}$ to whatever the size of the state space of $M_i$ is (since this is an upper bound on how many branches of nondeterministic computation you can obtain at each time step). However, since $i$ can be arbitrarily large and each binary string represents some Turing machine (one of the assumptions made by Arora-Barak), it seems that state spaces can be arbitrarily large as well and bounding them isn't quite as simple as picking a constant base other than 2.


texts: Connections between circuit complexity and Unique Games Conjecture?

texts:
Circuit complexity has connections to many questions in complexity theory.
For a couple examples, Ryan Williams shared some in a recent talk and Section 3 of these notes gives simple relations to $\mathbf{P}$ vs. $\mathbf{NP}$ and $\mathbf{P}$ vs. $\mathbf{BPP}$.
More can be found in the textbook Boolean Function Complexity.
On the other hand, the Unique Games Conjecture has been linked to a wide range of computational problems and areas of applied mathematics; see e.g. this talk or this survey of Khot.

What I'm wondering is, are there strong connections known between circuit complexity and hardness of approximation, specifically the Unique Games Conjecture?
If so, what are they?


texts: Time complexity of generating the first n primes and their product

texts: Suppose that I have a turing machine that receives as input the string $1^{n\times n}$ (unary input), what is the time complexity of writing $p_1,...,p_n$ on the output tape, where $p_i$ is the i-th prime number (written in binary)? And writing the first $n$ primes  followed by their product (all written in binary)?


texts: Are there any problems in $P$ which we do not know any $P$ algorithms?

texts:
A problem in $P$ is one that can be solved in polynomial time (or faster) on a deterministic Turing machine. Now if I am correct, there is nothing here referring to the algorithms - which can themselves can be given a complexity class (necessarily greater or equal to that or the problem).

My question is: Are there any problems in $P$ for which we do not know the existence of any algorithm in $P$.

I am physicist by training so please let me know if anything doesn't make sense.


texts:
As far as I'm aware, EXPSPACE is the most inclusive computational complexity class. I was wondering if/how people conceptualize supersets of EXPSPACE.

Thinking about this question, I came up with a couple thoughts of my own:

Maybe EXPSPACE = the set of all Recursively Enumerable problems, i.e. $\Delta_1$ in the arithmetical hierarchy. In this case, the rest of the arithmetical hierarchy would come after EXPSPACE.
Maybe there are problems with space requirements that need to be described by non-computatable functions. For example, take the Busy Beaver function, $BB(n)$, which returns the maximum number of steps an $n$-state Turing Machine could take before halting. $BB$ grows faster than any computable function -- so if a problem required $BB(n)$ space to solve, maybe that would put it in a complexity class after EXPSPACE? In other words, maybe after EXPSPACE there is one or more sets of problems that require a non-computable amount of space to solve.


texts: Stable matching of producers, consumers and objects

texts:
Has the following version of the stable matching problem been studied?

There are $k$ types of objects.
There are $n$ producers, each of whom can produce a single object of any type, and has a personal preference relation over the objects (e.g. Bob prefers to produce shoes, then socks, then cars, etc.).
There are $n$ consumers, each of whom has a personal preference relation over the objects (e.g. Alice prefers to buy cars, then shoes, then socks, etc.).
A matching is a function mapping each producer to a unique consumer and to a single object-type. I.e., each producer produces exactly one object for a single consumer.
A matching is stable if there is no pair of producer P and consumer C such that:

P would prefer to produce a certain object X rather than the object currently produced;
C would prefer to consume X rather than the object currently consumed.

Does there always exist a stable matching in this setting?


texts: I don't understand formula meaning of computer vision Paper

texts:
I am master degree student at Computer Science Department.
I started master degree at this year.
Now I'm reading two papers about computer vision.
Actually before time I didn't have experience about computer vision. so I am not familiar with the concepts used in this field.

OK. I want start question.
I am reading these paper.
1) Template Matching using Fast Normalized Cross Correlation
by "Kai Briechle and Uwe D. Hanebeck
2) Fast Template Matching
by J.P. Lewis

Question 1. In the above  "2) paper" we can see formula like bottom, f(x,y) is source Image, t(x,y) is
template Image.

I wonder why two red box term to be constant and remove. I thank that just mathematically.
Who can explain to me? by using some picture or easily. I don't understand by image processing field.

Question 2. In the above "1) paper" I don't understand red box term (average value) to be that.
because, In usually We can calculate average value like this (value1 + value2 / 2)


texts: Proof of RAP-derivation sequence for a set of functional dependencies in relational databases

texts: I'm reading David Maier's outstanding but out-of-print book on relational databases (the book,"The Theory of Relational Databases", is available online from the author's website http://web.cecs.pdx.edu/~maier/TheoryBook/TRD.html). I have a question regarding the proof of Theorem 4.2 of Chapter 4. On page 55 of the book (see pdf for Chapter 4 if you don't have the book), it was said that the FDs of step 13 and 14 can be replaced by new steps 13.1 ... 13.k and 14 that follows. It seems to me that only step 13.k is needed and steps 13.1 - 13.(k-1) are unnecessary. I'm pretty sure I'm missing something here, but the author didn't explain. In fact, the example in the proof shows that only step 13.k is used.


texts: Filter bubble algorithms for presenting related video lists

texts: In a filter bubble, what are some of the techniques and best ways to determine the relationship between a video that is watched or liked, and the list of related videos to be presented to the browsing user? Thanks.


texts: Retrieving data from website - Parser vs AI

texts:
I'm currently working on a personal software project (as a hobby) and would like to know which kind of approach I should follow according to you.

My application scans some websites (like Amazon or eBay) to check items of a specific category and show them all together ordered, for instance, by price.

Currently I use Python with LXML to extract strings and numbers from specific positions on the page (searching by HTML element tag or CSS class).

This approach works smoothly, but I'm a little bit concerned about scalability: what if I want to add more web sources? What if Amazon and eBay change the structure of the HTML page?

So far I managed these issues by manually changing the functions I use to retrieve data from each website, but was wondering if there is a better approach, for example using AI/Machine Learning.

Finally the question: is it better to rely on "old-style" and "hard-coded" algorithms for such a scenario or Machine Learning and AI could be more helpful according to you?

Thanks a lot!


texts: Could following be a counter example to Church-Rosser (Confluence) theorem?

texts:
According to the "Type Theory and Formal Proof" book, Church-Rosser theorem (confluence) is as follow:

  Suppose that for a given term $M$, we have $M \twoheadrightarrow_\beta N_1$ and $M\twoheadrightarrow_\beta N_2$. Then there is a $\lambda-term$ $N_3$ such that $N_1\twoheadrightarrow_\beta N_3$ and $N_2\twoheadrightarrow_\beta N_3$.

But if we take $(\lambda u.v)((\lambda x.xx)(\lambda x.xx))$ expression as $M$, then it will reduce to $v$ if we start with the left sub term and reduces to $(\lambda u.v)((\lambda x.xx)(\lambda x.xx))$ if we start with the right sub term. And they would never reduce to equal terms if we keep reducing the sound one using the right sub term since it would keep converting to itself for ever.Isn't the above example a refutation of the CR theorem, or I have missed a point somewhere?!


texts: Conversion of ambiguous left recursive grammar to LL(1)

texts:
I have been strugling with this LL(1) transformation for far longer than expected and am getting quite desperate. We are given a grammar $ G = \left\{V_N, V_T, S, \Phi \right\}$, with the non-terminal set $V_N = \left\{S\right\}$, terminal set $V_T = \left\{\underline{o}, \underline{l}, \underline{r}, \underline{i}\right\}$, start symbol $ S $ and the production rules in $\Phi$:

$$ \begin{equation}\begin{split} S \rightarrow & \ S \underline{o} S \\ S \rightarrow & \ S \underline{l} S \underline{r} \\ S \rightarrow & \ \underline{i}\end{split}\end{equation}$$

I have tried the standard tricks like left factoring, left recursion removing, which lead to an infinite transformation loop. Trying to fix first and follow set clashes also did not help. Here are some results after applying the transformations:

$$ \begin{equation}\begin{split} S \rightarrow & \ \underline{i} A & \ \ \ \ \ \ \ \ \ \ \ S \rightarrow & \ S A \\ A \rightarrow & \ \underline{o} S A & \ \ \ \ \ \ \ \ \ \ \ S \rightarrow & \ \underline{i} \\ A \rightarrow & \ \underline{l} S \underline{r} A & \ \ \ \ \ \ \ \ \ \ \ A \rightarrow & \ \underline{o} S \\ A \rightarrow & \ \epsilon & \ \ \ \ \ \ \ \ \ \ \ A \rightarrow & \ \underline{l} S \underline{r} \end{split}\end{equation} $$

However I go about the problem, I cannot seem to get even close to eliminating the double entries in my LL(1) table.


texts: Why is the intersection of these two Languages Recursively Enumerable, not Recursive?

texts:
I am only several days exposed to computational theory, so my understanding is quite slim: in a question, it says that for a regular language L1 and a recursively enumerable but not recursive language L3, L3 ∩ L1 is recursively enumerable. But I thought it would be recursive?

Now, the text and I came to the same first conclusion - that it is important to deduce that L1 is a recursive language, since it is regular, and go from there - but my understanding is that if a recursive language had an undecideable intersected, you'll either get the empty set (which is recursive) or you'll get a set of elements common to both. Since all elements in a recursive must lead to halting, then the elements of the intersection all must lead to halting.

Hence '(recursive) ∩ (rec enu but not recursive)' and so 'L1 ∩ L3' should be recursive?

I must have gone wrong somewhere because the text, without explanation, just says it's recursively enumerable - where have I gone wrong? Thanks for your insight.


texts: Understanding Dynamic Frequency Warping (not Dynamic Time Warping)

texts:
I am implementing a paper which need Dynamic Frequency Warping as a component. They have written very briefly about this algorithm and cite to
this paper: Voice transformation using PSOLA technique (page 9/13 of the PDF, section 3.3). I have read it but can't understand its mechanic. I've also made some search on Google but almost have no improvement. As I understand, DFW take an input of 2 spectra (A and B) and then calculate a warping matrix that convert A->B. Can someone give me some clearer intuition?

Thanks in advance.


texts:
I have a bit of experience with loop invariants but I'm not really clear on them. I'm trying to learn them through an Algorithm I have.
Reverse(X,Y)
   n = X.length
   for(i = 1 to n)
      Y[n - i + 1] = X[i]
   return Y

This copies values in array X into array Y in reverse order, and returns array Y. If X and Y both have length n (i.e., n = X.length = Y.length) and both arrays are indexed from 1 to the length of the array, what would be some loop invariants for the for loop which would prove its correctness?


texts:
Two-part question:

Is there any more specific name than "unbalanced binary tree" to describe the tree below? The distinguishing characteristics are:

i. The root node and left children must have either 0 or 2 children.

ii. Right children must have 0 children.

iii. All nodes must be positive non-zero integers.

iv. Any node with children must equal the sum of its children.

Given the value of the root node (in this case, 77), is there a standard algorithm to efficiently calculate all possible trees of this type?

i.e. (77, 76, 1), ..., (77, 1, 76), (77, (76, 75, 1), 1), etc.

         77
        /  \
       68   9
      /  \
     48   20
    /   \
   47    1
  /  \
 42   5


texts: Marriage Problem: Is both sided stable matching strongly pareto optimal?

texts:
According to this problem: Unique Stable Solution in Stable Marriage Problem: Is it Pareto-efficient and a Nash Equilibrium?

Is the both sided stable matching strongly pareto optimal for both sides? And is there a rule that in a m- and w-optimal stable matching at least one person gets his first choice like in the example?


texts: A question about decidable and undecidable problems

texts:
Maybe this question is not very smart but I really wanna learn this thing. also, I need someone who is familiar with printing 42 problem and zero program problem.

This is the context:

  Consider the problem of determining whether a number belongs to a set. This
  problem is easy for the following sets:

  The set of odd numbers
  The set of even numbers
  The set of prime numbers
  The set of numbers that can be written as a sum of five square numbers

  For every one of these sets, a program can be written that accepts a whole number as input and—depending on whether the input is in that set—outputs a yes or no answer.

  However, there are other types of sets. This chapter has shown that there are
  certain sets of whole numbers for which no computer program can be written that can decide if they are in the set or not. For example,

  The set of numbers of programs that will output 42 for some input
  The set of numbers of programs that always output a 0"

  The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us by Noson S. Yanofsky

First of all, I should say that I am a self-learning in this area, so I don't have very good knowledge about this stuff. so, in this context, I don't get two parts. If anyone could help me, I would very appreciate it.

the first part is: "there are other types of sets. This chapter has shown that there are certain sets of whole numbers for which no computer program can be written that can decide if they are in the set or not." what are they. is the writer talking about inputs/ arbitrary whole numbers or certain sets of whole numbers?

second, I don't get this part at all and somewhat, this part is making me confused about the former question:

  The set of numbers of programs that will output 42 for some input
  The set of numbers of programs that always output a 0"

if you rewrite this part in another form, I think I would comprehend it because I think this is a grammatical confusion. thank you in advance


texts: How can I optimise a 8b10b encoding for maximum alignment?

texts:
Imagine you encode an 8 bit symbol as a 10 bit symbol that is sent sequentially over a wire. The goal at the receiver is to detect the byte boundary.

Since there are 4 times more encoded symbols than source symbols, 3/4 encoded symbols are invalid. So the idea is that if you look at a buffer of received bits, if they are misaligned there will be encoded symbols that are invalid.

An aligned buffer has zero invalid symbols, but the reverse is not true. A misaligned buffer could accidentally be valid. So it's desirable to pick an encoding that is unlikely to be valid when shifted.

So I'm trying to figure out the probability that a given sequence of a given encoding is valid when shifted. And trying to optimize such an encoding.

As an example, 8b10b encoding is usually optimised for maximum transitions. So the best symbols are for example barrel rolled versions of '0101010101', and '0101011010'. But it's easy to see that '...01010101010101010101...' is valid at every possible index. So this is not at all useful for alignment.

It seems slightly better to have the fewest transitions, so '0000000000', '1111111111' and variations of '1111100000'. In this case '...00000000001111111111..." is only valid at 2/10 positions.

But maybe there is a better way? Barker code seems relevant, except it's not the autocorrelation that matters, but the correlation between all possible permutations of symbols sequences.


texts:
How do top news portals detect similar news? For example https://www.bbc.com/news/world-asia-china-51431087, if you go to this webpage, you can see the "More on this story" section at the bottom of the page. This news was published today, but it has detected similar news from days ago.

Is there any known algorithm or any library?


texts:
I read in this article that the amount of bits that can be emulated by a certain number of qubits is 2^(number of qubits). This is because each qubit can be in one of 2 states after it collapses, and so before all the quantum... whatevers collapse, that is the function that gets that result. At least, that was generally what it was saying, but I probably mangled the explanation myself; sorry.

Anyway, this relation (2^n) happens to be the same as the relation between memory registers and RAM in classical computers (i.e. if the computer has n bits in the register, it can have up to 2^n bytes in RAM). Is this important? Does it mean qubits will become like the memory registers and their states like the RAM when we switch to quantum computers? Or is it just something that seems important but is actually meaningless in practice?

By the way, there don't seem to be any tags for some things I referenced, like RAM & memory registers. Is that because the site is so new, or am I just not looking hard enough?


texts: How to reduce C′A′B + CAB′ to C′B + CB′?

texts:
I faced this Boolean expression:

$C'(A'B+A)+C(A'+AB')$

It was solved as follows:

$C'(A'B+A)+C(A'+AB')$
$=C'(A+B)+C(A'+B') $       ...by applying absorption laws $(I)$
$=C'A+C'B+CA'+CB'$
$=(C\oplus A)+(C\oplus B)$

However somehow it did not clicked to me to apply absorption laws. So I did following:

$C'(A'B+A)+C(A'+AB')$
$=C'A'B+C'A+CA'+CAB'$    $...(II)$

Here, I can have $C'A+CA'=C\oplus A$, but I have following doubt:

What Boolean law / identity I can use to reduce $C'A'B+CAB'$ to $C'B+CB'$ (which then can be reduced to  $C\oplus B$) ? Is it even possible? or I have to somehow remember to apply absorption law as shown above and their is not other way to arrive at $(C\oplus A)+(C\oplus B)$ by expanding as in step $(II)$?


texts: Counter example to graph coloring heuristic using BFS

texts:
I am considering the following heuristic for the graph coloring problem (i.e. to color a graph $G$ using a minimal number of colors so that no two adjacent vertices have the same color):

  Explore the vertices of $G$ in the order that they would be explored by a BFS search (with arbitrary starting vertex) and assign each vertex the lowest numbered color not yet used for one of its neighbors.

Since I don't think this algorithm is correct, I am trying to find a counterexample where coloring a graph in this way does not yield a coloring with the minimal number of colors. Does anyone know of such an example?


texts:
There are a couple of function pairs which give the identity when composed, e.g.,

decrypt(encrypt(value)) == value
deserialize(serialize(data, filepath)) == data

What is this property called? Suppose one function undoes the property of the other, and it is guaranteed that this is possible for all values (within the domain of interest).


texts: If an NP complete problem 'A' is polynomial time reducible to another problem 'B' does that imply 'B' is also NP complete?

texts:
The following question was asked on a quiz:

  Let S be an NP-complete problem, and Q and R be two other problems (that we don't know much about). If we now know that Q is polynomial time reducible (i.e., can be reduced in polynomial time) to S, and S is polynomial-time reducible to R, which one of the following statements can be deduced from the above information?

It was asked to choose a correct option out of these four options:

  R is NP-complete
  R is NP-hard
  Q is NP-complete
  Q is NP-hard


texts: Learning material on information visualization

texts:
If somebody with a computer science background wants to learn about information visualization, again from a computer science perspective, which will be the best learning material for him?

A textbook will be preferred but any other tutorial or something similar is also welcome.


texts: Algorithm to convert decimal number to binary

texts:
I am reading this material to understand the basics of number system.
I am stuck at a point in that material where it writes the algorithm to convert a decimal number to binary number.
The heading of that part where I am stuck is Decimal to Base
The algorithm (may be presented less than faithfully, please refer the link) it mentions there is:

  Let $p = \lfloor \sqrt{V} \rfloor$
  Let $v = \lfloor \dfrac V {B^p} \rfloor$
  (v is the next digit to the right)
  Make $V = V − v * B^p$
  Repeat steps 1 through 3 until $p = 0$

It is explaining by taking an example of converting decimal number 236 to binary.

I am not getting how it is calculating the 1st step, i.e. to get the value of p.

It writes that p = int(square root of V)

Now, square root of 236 = 15.36229149573721635154

As per point number 1, p = integer part of 15.36229149573721635154
So, I remove the decimal part and p then becomes 15. But the material there says it is 7.

I can't get what is happening here. I am stuck.


texts: For any language $A$, there is $B$ such that $A \le _T B$ but $B \nleq _T A$

texts:
I am trying to come up with a proof for the following:

  For any language $A$, there exists a language $B$ such that $A \le_{\mathrm{T}} B$ but B $\nleq_{\mathrm{T}} A$.

I was thinking of letting $B$ be $A_{\mathrm{TM}}$, but I realize that not all languages are Turing reducible to $A_{\mathrm{TM}}$, so $A \le _T B$ would not hold.
What other choice of $B$ do I have that would allow me to write a TM which uses an oracle for $B$ to decide $A$?

Thanks!


texts: Data structure/aglorithm for strings to see if there exists two strings you can concatenate to get a target?

texts: I want to come up with an arbitrary string, and feed it into my program to see if there exists two strings that I can concatenate to get the target string. What kind of data structure and algorithm would be good for this? I'm thinking a sorted array would be good, and then walk down the list, binary searching for the suffix/prefix needed. That would be O of NlogN I think.


texts: What happens when time slices are too short or too long?

texts: What bad things can occur when the lengths of the time slices in a multitasking system are too small? What can happen when they are too big?  How should the length of the time slice be chosen?


texts: $ADD = {x=y+z}$ with $x, y, z$ binary integers, and $x$ is the sum of $y$ and $z$. Pumping lemma to show that $ADD$ is not regular

texts:
Consider the alphabet $\Sigma = \{0, 1, +, =\}$ and the language $ADD = \{x=y+z|x,y$ are binary integers $x$ is the sum of $y$ and $z$ $\}$.

This is the (informal) solution I came up with (not sure about its correctness).
Using the pumping lemma:

Take $s= 1^p=0+1^p$, $s \in ADD$. $s$ can be divided into three parts so that $s=xyz.$
The pumping lemma says that $|xy| \leq p$ and $|y| > 0$ so $y$ must be in the first $p$  $1's$. Choose $i=0$. Then the equation is false, so the languge $ADD$ is not regular. $\square$

Even though I think this is correct, in the answers they use the string $1^p=10^{p-1}+1^{p-1}$ which is also a correct pick, is mine just another correct pick?


texts: How to check if a string is accepted by a context-sensitive grammar?

texts: Is there an algorithm to determine membership in context-sensitive grammars?


texts: Time complexity of an enumeration of SUBSET SUM instances

texts:
An instance of the SUBSET SUM problem (given $y$ and $A = \{x_1,...,x_n\}$ is there a non-empty subset of $A$ whose sum is $y$) can be represented on a one-tape Turing Machine with a list of comma separated numbers in binary format.
If $\Sigma = \{0,1,\#\}$ a reasonable format could be:

$( 1 \; (0|1)^* \; \#)^* \#$

Where the first required argument is the value $y$ and $\#\#$ encodes the end of the input. For example:

 1  0  0  #  1  0  #  1  #  #
^^^^^^^^     ^^^^     ^
   y          x1     x2
Instance: y=4, A={2,1}

I would like to enumerate the SUBSET SUM instances.

Question: What is the (best) time complexity that can be achieved by a Turing Machine $TM_{Enum}$ that on input $m$ (which can be represented on the tape with a string of size $\log m + 1$) - outputs the $m$-th SUBSET SUM instance in the above format?

EDIT:

Yuval's answer is fine, this is only a longer explanation.

Without loss of  generality we set that $y > 0$ and $0 < x_1 \leq x_2 \leq ...  \leq x_n$, $n \geq 0$

And we can represent an instance of subset sum using this encoding:

$y \# x_1\# d_2\# ...\# d_{n} \#\#$ where $d_i \geq 1, x_i = x_{i-1} + d_i - 1 \; , i \geq 2$

Using a binary representation for $y,x_1, d_2, d_3, ...$ we have the following representation:

$1 \; ((0|1)^* \# 1)^* \; \#\#$

Equivalent to $1 \; (0|1|\#1)^* \; \#\#$. There is always a leading 1 and a trailing ## so we can consider only the $(0|1|\#1)^*$ part.

So the decoder TM on input $m$ in binary format should:

output the leading 1
convert $m$ to base 3 mapping digit 2 to $\#1$
when outputing the i-th intermediate $\#$ calculate $x_i = d_i + x_{i-1}-1$
output the trailing $\#\#$

No duplicate instances are generated.


texts:
Can someone give me a hand here, I am new to backtracking, and preparing for an interview. I couldn't even attempt this question, please help.

Describe a back tracking algorithm for efficiently listing all k-element subsets of n items.

For n = 5 the 3 element subsets are (1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5), (2,3,4), (2,3,5), (2,4,5), (3,4,5)

In particular, I am interesting in first describing the solution vector representation to use, and then how I would partition the work among construct-candidates, is-a-solution and process-solution functions.


texts: Explanation of pilot jobs in distributed/grid computing

texts:
I'm reading into grid systems/distributed systems and came across pilot jobs that I can't find a decent explanation for. The wikipedia page is not understandable to me.

I know multi-level schemes from distributed graph algorithms, and I guess in this context it means first the resources are scheduled to the applications and then the application does internal scheduling? But some more explanation would be appreciated. In my application the pilot jobs are empty jobs that are sent to resources, acquire them and then demand jobs from a (central?) job queue in a pulling strategy (as far as I understood it).

I think it would be very helpful if somebody could point out an alternative scheduling strategy and compare its pros and cons to those of the pilot job variant.


texts: Understanding the time-complexity of Insertion Sort

texts:
From my textbook, I am studying the time-complexity of the insertion sort algorithm (shown below).

INSERTION-SORT(A)                         cost     times
1  for j <- 2 to length[A]                c1       n
2      DO key <- A[j]                     c2       n - 1
3         ▷ Insert A[j] into the sorted
          ▷          sequence A[i..j-1]   0        n - 1
4         i <- j-1                        c4       n - 1
5         while i > 0 and A[i] > key      c5       sum_{j=2}^2 t_j
6            do a[i+1]<-A[i]              c6       sum_{j=2}^2 (t_j-1)
7                i <- i-1                 c7       sum_{j=2}^2 (t_j-1)
8         A[i+1] <- key                   c8       n - 1

The algorithm above shows the times that each statement is executed. But wait, why is line 1 executed n times?

Shouldn't line 1 be executed n-1 times since insertion sort starts making comparisons at the second element at the list.

Thanks in advance.


texts: I know that this problem is a known NP-Complete problem, but I'm curious as to why a particular algorithm won't work. Given a graph $G = (V,E)$, and edge weights $w(e)$, why can we not create a new graph $G' = (V,E')$, and flip the sign of each edge weight, i.e set the weight of each edge $e' \in E'$ to $w(e') = 0-w(e)$ and use an algorithm such as Bellman-Ford to find the minimum weight path on this new graph. I understand that flipping the sign of the edges could create negative cycles, implying there is no shortest path in $G'$, but won't this imply that there is a positive cycle in $G$, meaning there is no longest path? Can someone give a counter-example of when this algorithm would fail?


texts: Why in Flow network, there is no reversed edges?

texts:
I have read that Flow network is a directed graph, with no self loops and there is no reverse edges and non negative capacity.
However in Residual network, we allow the reverse edges so we can cancel(subtract) some units from the flow.

My question is why there is no reversed edges in flow networks?

I understand that it is directed since we need to go from source to sink, non negative capacity since there is no a negative flow but i don't understand why no reversed edges.


texts: Proving number of calls made in cut-rod algorithm

texts:
I was reading dynamic programming chapter from famous book Introduction To Algorithm

In rod cutting problem it gives simple algorithm as follows:

    cutRod(p,n)
    {
       if (n == 0)
       {
          return 0
       }
       q = -∞
       for (i=1 to n)
       {
          q = max(q,p[i]+cutRod(p,n-i))
       }
       return q
    }

It then says:

  T(n) be the total number of calls made to cutRod() when called with its second parameter equal to n. T(n) equals the number of nodes in a subtree whose root is labeled n in the recursion tree. The count includes the initial call at its root. Thus,

T(0) = 1          and

T(n) = ${\sum\limits_{j=0}^{n-1} T(j)}$

Exercise at the end of this chapters asks to prove from above two that in fact

T(n) = 2$^n$

How can we go about proving this?


texts: Interval scheduling scheduling problem with minimal workers

texts:
I am writing a greedy algorithm for a variation of the interval scheduling problem that I haven't seen before.

I have a set of jobs, each with start and finish time. All jobs in set must be assigned to a worker, workers cannot have overlapping jobs. My greedy algorithm should minimise workers - use the least number of workers possible to complete all jobs.

Does this algorithm accomplish this? It seems too simple to me and I have probably neglected to think of something.

sort(jobs) //earliest starting time first

w = 0 //number of allocated workers

for i = 1 to n {
    if (worker w has no job with finish time later than starting time of job i)
        schedule(worker w, job i)
    else
        schedule(worker w+1, job i)
        w++


texts: I have this [kind of funny] question in mind. Why is the non-deterministic finite automaton called non-deterministic while we define the transitions for inputs. Well, even though there are multiple and epsilon transitions, they are defined which means that the machine is deterministic for those transitions. Which means it's deterministic.


texts: What is the Big O time complexity of this algorithm?

texts: We are given $m$ arrays of $n$ elements each. For 90% of these arrays we run an $\mathcal O(n)$ algorithm and for the other 10% an $\mathcal O(n\log n)$ algorithm. What is the total time complexity? I think it is $\mathcal O(m n \log n)$ but I am not sure.


texts: Activity scheduling with activities that can move around

texts:
In this problem. I have a set of "activities" which can happen. Each "activity" is associated with several values:

Duration: The length of time the activity takes
Earliest time to start: The earilest time at which the activity can begin
Latest time to start: The latest time at which the activity can begin
Weight/Value: The "value"/"benefit" gained if the activity happens.

I have a set of activities $A = \left\{ a_{1},a_{2},\dots,a_{n}\right\}
 $.
I want to find a subset of activities $\alpha \subset A$ which maximises the total value, subject to the constraint that two activities cannot overlap in time (so the subset of activities should be such that we can schedule these activities without any overlap, and such that each activity starts within its earliest and latest start times). Activities must be performed contiguously. i.e we can't just break apart an activity in two and do half of it now and half of it later.

If activities all had a fixed starting time, this would be equivalent to the "Maximum Weight Independent Set of Intervals" problem, but in this case an activitiy does not have a fixed starting time and it can move around.

If activities could be positioned anywhere, this would be equivalent to a knapsack problem.

I will use this with a time span of one day and activities will usually last between 1 and 4 hours.

I had one idea which I write below but thought maybe someone would have a better idea. Heuristics and approximations would be helpful as well.

I need something that will run in less than a second with ~$1000$ activities.

So far what I thought of doing is duplicating activities that can move around. So if I have an activity $a$ which can start between 14:00 and 16:00, then to create three activities: at 14:00, at 15:00 and at 16:00. That way I don't need to worry anymore about activities moving around and I have a "Maximum Weight Independent Set of Intervals" problem which seems researched at least. Also "Maximum Weight Independent Set" problems are quite researched.

Thank you!


texts: What is the Necessary math to understand books?

texts:
I have many problems understanding algorithms described in the books.

Well, I'm talking about the mathematical description of a problem.

For example: I don't understand how the math of Unscented Kalman Filter works.
I have spent many days studying good books but for me just code make sense.

I have the basic math from the college but something is missing and I don't know what is.
I need understand math because I should translate math to code.

Can you help me saying what is missing?

Thank you, and sorry for any english mistakes.


texts: Difficulty in proving the existence of one-way functions

texts:
By definition:

A polynomial-time computable function $f:$ $\{$0,1$\}$$^*$→ $\{$0,1$\}$$^*$ is a one-way function if for every probabilistic polynomial time Turing Machine $PTM$ there is a neglegibible function $E$ $:$$\mathbb{N}  → \mathbb{N} $
  $ \ s.t. \ $ $Pr$ $x$ $∈$ $\{$0,1$\}$$^n$ $[PTM \ \ inverts \ \ f(x)] ≤ E(n)$.

Now, reading the definition above, the existence of one-way functions seems like an easy bet, however it is considered a stronger assumption than $P \neq NP$.
Apparently proving the existence of these functions would be more difficult than proving $P = NP ?$   And I'd like to know the technical reasons for this, does it have something to do with the "for every" in the definition?

What steps would a mathematician or computer scientist take to prove that one-way functions exist? I believe that since proving its existence would also prove $P \neq NP$, this means that we cannot use the techniques that we know for sure does not work: Relativization, diagonalization, Natural Proof.

So,  what form could such a proof take? Maybe something in  second(+)-order logic?


texts:
I am a bit confused on how to reduce a problem. I'll give an example:
Let's say there is a problem called HALTEMPTY and we know it is undecidable.

$HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ is a Turing Machine that halts on input } \varepsilon\}$

The problem we are reducing to is

$HALT_{TM} = \{\langle M,w\rangle \mid M \text{ is a Turing Machine that halts on input } w\}$

So from what I think, we reduce $HALTEMPTY_{TM}$to $HALT_{TM}$ by creating a turing machine similar to $HALT_{TM}$ but it would delete the tape then run normally like $HALT_{TM}$. Am I thinking this right? Is there a systematic way of solving these type of problems?


texts: How to prove that a constrained version of 3SAT in which no literal can occur more than once, is solvable in polynomial time?

texts:
I'm trying to work out an assignment (taken from the book Algorithms - by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Chap 8, problem 8.6a), and I'm paraphrasing what it states:

  Given that 3SAT remains NP-complete even when restricted to formulas in which
  each literal appears at most twice, show that if each literal appears at most once, then the problem is solvable in polynomial time.

I attempted to solve this by separating the clauses into multiple groups:

Clauses which did not have any variable in common with the rest of the clauses
Clauses which had only 1 variable in common
Clauses which had 2 variables in common
Clauses which had all 3 variables in common

My reasoning was attempted along the lines that the # of such groups is finite (due to the imposed restriction of no literal being present more than once), and we could try to satisfy the most restricted group first (group 4) and then substitute the result in the lesser restricted groups (3, 2 and then 1), but I realized that this wasn't quite getting me anywhere, as this doesn't differ much from the case for the constrained version of 3SAT in which each literal can appear at most twice, which has been proven to be NP-complete.

I tried searching online for any hints/solutions, but all I could get was this link, in which the stated hint didn't make sufficient sense to me, which I'm reproducing verbatim here:

  Hint: Since each literal appears at most once, convert this problem to 2SAT problem - hence polynomial time, if a literal $x_i$ appears in clause $C_j$ and complement of $x_i$ (i.e., $\overline{x_i}$) in clause $C_k$, construct a new clause clause $C_j \lor \overline{C_k}$.

Both $C_j$ and $C_k$ have three literals each - I didn't get how I should go about converting it into 2SAT by doing $C_j \lor \overline{C_k}$ (or $\overline{C_j \lor C_k}$ if I read it incorrectly).

Any help in either decrypting the hint, or providing a path I can explore would be really appreciated.


texts: Is the halting problem decidable for pure programs on an ideal computer?

texts:
It's fairly simple to understand why the halting problem is undecidable for impure programs (i.e., ones that have I/O and/or states dependent on the machine-global state); but intuitively, it seems that a pure program's halting on an ideal computer would be decidable through e.g. static analysis.

Is this in fact the case? If not, what are some counterexamples or papers disproving this claim?


texts: Can I get the lambda calculus for free from Cartesian closed categories?

texts:
I have heard the simply typed lambda calculus is the internal language of closed Cartesian categories.
I have a written a compiler from the STLC to CCCs but this involves a lot of ugly tuple shuffling.
Is it possible to get the STLC for free from the definition of a closed Cartesian category?


texts: (Co)-monads and terminating implementations

texts:
The bounty above should read 'I would like to know whether the example I discuss is a com-monad and why (why not).'
Suppose we set $\mathbb{M} \alpha := r \to \alpha$, where $r$ is some fixed type, and $\alpha$ an arbitrary type, of the STLC (Simply-Typed Lambda Calculus)
Suppose we want to define a co-monad, which contains Co-unit and Co-join, with the following types (where $\mathbb{M}$ binds more tightly than $\to$ and $\mathbb{M}$ is as stated above):

Co-unit $\;\;\;\; \mathbb{M} \alpha \to \alpha$
Co-join  $\;\;\;\;\mathbb{M}\mathbb{M} \alpha \to \mathbb{M} \alpha$

I have been told that this will not work and that we could not create a co-monad in this way, since there is no terminating implementation for the type $(e \to a) \to a$.
But in the pure STLC all terms are "terminating"(i.e, reductions always lead to a (unique) normal form). So I don't understand how this comment can be relevant in the case of the STLC.
Is there some link between (co)-monads and terminating implementations? Or is this just about creating a co-monad in Haskell?
Why would we not be able to construct a co-monad in the way described above?


texts:
I’m trying to make a photo mosaic web application. I split the main picture in to a number of squares. I split this square up in to 9 squares.

Then I calculate the mean color (RGB) of the entire square and the mean color of the 9 little squares. So I will get the following vector.

Vector: Mean R; mean G; mean B; cell 1 R; cell 1 G; cell 1 B; cell 2 R; cell 2 G; cell 2 B; cell 3 R; cell 3 G; cell 3 B; cell 4 R; cell 4 G; cell 4 B; cell 5 R; cell 5 G; cell 5 B; cell 6 R; cell 6 G; cell 6 B; cell 7 R; cell 7 G; cell 7 B; cell 8 R; cell 8 G; cell 8 B; cell 9 R; cell 9 G; cell 9 B

This will all be number between 0 and 255. And the mean RGB is more important than the other elements.

I make the same vector for all pictures in my DB. So now I want to compare a square of the original too my DB and want to find the 10 closest pictures.

My question is how do I compare these vectors??


texts: Number of strings at given edit distance

texts:
I would like to know the number of strings at edit distance $n$ of a string $s$.

I guess this is textbook knowledge... but I cannot find the textbook in question.

More formally, I have an alphabet $\Sigma$ (in my case, $|\Sigma| = 4$), and I consider all the words in $\Sigma^*$.
I use the edit distance $d$.
I am looking for the number of words at distance $n$ of a word $w \in \Sigma^*$.
Namely,

  $ f_1(w, n) = \lvert \{ w' \in \Sigma^*: d(w, w') = n \} \rvert $

I need the maximum size, considering all the words of a given length.
Namely:

  $ f_2(s, n) = \max_{w,\ |w| = s}(f_1(w, n)) $

In practice, I have to compute a table of $f_2$ with $s \in [0, 100]$, and $n \in [0, 5]$, so I can compute $f_2$ recursively.

I tried to read the original Levenshtein paper, but it seems to deal with binary alphabets only.

What I had in mind, is that $f_2(s, n)$ can be computed with $f_2(s, n-1)$, and adding an error: insertion, deletion, substitution.

  $ f_2(s, n) = (s+1) |\Sigma| f_2(s, n-1) + s f_2(s, n-1) + s (|\Sigma|-1) f_2(s, n-1)$

I know it is not strict bound, because deleting a (previous inserted) insertion should not count.
But am I far from true?

With the previous recursion (and knowing that $f_2(s, 0) = 1$), I would have:

  $ f_2(s, n) = (|\Sigma| (2s + 1))^n $

Is there a better bound?


texts: A regular expression for a given formal language

texts:
I wanted to ask if someone can help me to construct a regular expression over the alphabet $\{a,b,x\}$ for the language $L$ which is constituted by all strings containing an odd number of $a$'s, and in which between each pair of consecutive $a$'s there is an even number of $b$'s (and an arbirtary number of $x$'s).

For example, $babbxbbxabbxaabxxbax \in L$, $bab \in L$, while $abba \notin L$ and $abbbaa \notin L$.

What is the approach?


texts: recursively enumerable sets closed under concatenation

texts:
I'm trying to show the set of all recursively enumerable sets is closed under concatenation. I'm trying to use the definition of recursively enumerable sets to construct the argument. I believe that I must  consider the Cartesian product $S_1\times S_2$ of two recursively enumerable sets $S_1$ and $S_2$. Then I construct the function $f':S_1\times S_2\rightarrow \lbrace 1\rbrace\cup\lbrace\perp \rbrace$ (where $\perp$ is undefined) such that: $$f'(x,y)=\begin{cases}
 1 &\text{  if } x\in S_1 \text{ and } y\in S_2\\
 \perp&\text{ otherwise}
\end{cases}$$
Does the mere existence of this function $f'$ show that $S_1S_2$ is recursively enumerable?
I'm still new to these proofs, so any help would be appreciated.


texts: Is this combinatorial seach problem NP-complete?

texts:
The context: Consider the following optimization problem. Let $f_1,\dots,f_L:\mathbb{R}\to\mathbb{R}$ arbitrary (continous) functions for $L>1$ and $x_k\in\mathbb{R}$  evolve according to
$$
x_{k+1} = f_{\sigma(k)}(x_k),
$$
given $x_0$, where $\sigma_k \in\{1,\dots,L\}$. We want to find $\sigma(0),\dots,\sigma(N-1)$ to minimize
$$
\sum_{k=0}^{N-1} x_k^2
$$
for some $N>0$. As far as I can tell, if the functions $f_1,\dots,f_L$ are arbitrary, then $x_k$ may lie virtually in any place in $\mathbb{R}$ and there won't be any aparent structure on the number of states that $x_k$ can have. Thus, it seems that there is no better solution but to try all combinations of $\sigma(0),\dots,\sigma(N-1)$, which grow as $L^N$, exponentially in $N$. This may be done, e.g., by building a tree where each level is a step $k$ and the posible choices $1,\dots,L$ are explored at each node. This "try all combinations" can be improved by some heuristics, but still I suspect that the combinatorial explosion problem is hard to be avoided if an exact solution is desired. This makes me think that we can show this problem to be NP-complete (in terms of the variable $N$).
As far as I know, to show that this problem is NP complete we need to reduce this problem to another problem in a "list" of NP complete problems. Unfortunately, I have just started reading on complexity theory and combinatoric optimization (mosty due to my need to solve a problem like this one) and I haven't managed to see if these problems are related to mine, particularly since I don't understand most of them (yet).
Question: If you are more familiar to the NP-complete problems list, do you see which one may be a good candidate to reduce my problem to?
EDIT: As noted in the comments, this problem isn't NP-complete since verifying the correctness of a solution is as hard as finding one. However, my goal was to show that this problem is indeed "hard" is some sense, by framing it under some of these complexity categories. If NP-completeness is not the right category, which one is it?


texts: Value flow (and economics) in stacked reinforcement learning systems: agent as reinforcement environment for other agents?

texts:
There is evolving notion of stacked reinforcement learning systems, e.g. https://www.ijcai.org/proceedings/2018/0103.pdf - where one RL systems executes actions of the second RL system and it itself executes action of the thrid and the reward and value flows back.

So, one can consider the RL system RLn with:

S - space of states;
A={Ai, Ainner, Ao} - space of actions which can be divided into 3 subspaces:

Ai - actions that RLn exposes to other RL systems (like RLn-1, RLn-2, etc.) and for whome the RLn provides reward to those other systems;
Ainner - actions that RLn executes internally under its own will and life;
Ao - actions that RLn imports from other RL systems (like RLn+1, RLn+2, etc.) and that RLn executes on the other systems and form which RLn gets some rewards, that can be used for providing rewards for Ai actions.

So, one can consider the network (possibly hierarchical) of RL systems . My questions are:

is there some literature that consider such stacks/networks of reinforcement learning systems/environments?
is there economic research about value flow, about accumulation of wealth, about starvation and survival proceses and evolution in such stacks/networks of RL systems/environments

Essentially - my question is about RL environments that can function in the role of agents for some other environments and about agents that can function in the role of environemnts for some other agents. How computer science/machine learning/artificial intelligence name such systems, what methods are used for research and how the concepts of economics/governance/preference/utility are used in the research of evolution of such systems?


texts: Programming Symbols : Instance/Instantiation

texts:
Is there a generally accepted symbol for indicating instantiation. That is indicating an object is an instance of a class.

My first guess is to use a left arrow with a double or triple line but this seems more like a functional programming symbol, based upon what I've seen of Haskell.

Wikipedia has no examples and a quick google for psuedocode mostly turns up simple functional or procedural algorithms. Object Orientated examples don't seem to feature or do not use any specific symbol.