texts: Let $h$ be a homomorphism and let $L$ be a language.  Writing ${}^*$ for Kleene star, I want to show that $(h^{-1}(L))^* \neq h^{-1}(L^*)$.  Can I prove this just by showing that we can have  $h^{-1}(L)$ to be empty (because no strings are mapping into $L$) and therefore the right side is the empty set? Doing the same to the left side gives $\emptyset^* = \{\epsilon\}\neq\emptyset$.


texts:
I want to prove that the following program is correct. The code takes an array i of length N and a number x. At the end, the value of found should be true if the array contains x and false otherwise.

found := false;
i := 0 ;
while i < N do {
    found := found || (a[i]=x);
    i:=i+1
}

The given preconditions are that N >= 0 and that the array is sorted in ascending order (however, I don't know how the fact that it is sorted can help).

As postcondition, I think the following would suffice: the value of found equals the value of the predicate “there exists an i in the range [0, N) such that a[i] == x”

However, I am stuck at this point and don't know how to continue. I cannot think of any loop invariant that has any relation to the postcondition. What would you suggest as a loop invariant?


texts: When is a variable bound or free in a lambda application?

texts:
I am currently reading the book "An Introduction to Functional Programming through Lambda Calculus" (the 2011 edition) and am a bit puzzled by the definitions of free and bound variables with regards to function application.
The book states, in section 2.10, that a variable is bound in an expression if

the expression is an application $(\langle function \rangle \langle argument \rangle)$ and the variable is bound in $ \langle function \rangle$ OR $\langle argument \rangle$, or
the expression is a function $\lambda \langle name \rangle. \langle body \rangle $ and the variable is named $\langle name \rangle$ or bound in $\langle body \rangle$.

Next, it states that a variable is free in an expression if

The expression is a single name and the variable has that name, or
the expression is an application $(\langle function \rangle \langle argument \rangle)$ and the variable is free in $\langle function \rangle$ OR $\langle argument \rangle$, or
the expression is a function $\lambda \langle name \rangle.\langle body \rangle$ and the variable is not named $\langle name \rangle$ and is free in $\langle body \rangle$.

What confuses me is the use of "or" in the definitions of both bound and free variables in applications. I figured that if a variable is not bound, it must be free, and if a variable is not free, it must be bound. So I would expect that if a variable is free, the point 1 in the definition of bound above is inverted, so with boolean logic $\neg(A \lor B)$ should become $\neg A \land \neg B$.
However, the book doesn't state that a variable is free if it is free in $\langle function \rangle$ AND $\langle argument \rangle$.
I checked Wikipedia for another reference and it states:

The set of free variables of a lambda expression, M, is denoted as FV(M) and is defined by recursion on the structure of the terms, as follows:

$FV(x) = \{x\}$, where $x$ is a variable

$FV(\lambda x.M) = FV(M) \setminus \{x\}$

$FV(M N) = FV(M) \cup FV(N)$

So the set of bound variables in (M N) should be the complement of $FV(M) \cup FV(N)$ which I believe would be $FV(M)' \cap FV(N)'$ where ' denotes the complement.
The book repeats this definition later in a summary of the chapter, so I'm hesitant to think it would be a typo. I'm thinking that either I'm

wrong in assuming that bound and free are full complements or
wrong in thinking that a variable with the same name in the function and argument expressions of an application is the same variable.

What is the correct interpretation here? As an example, in the application expression $(\lambda x.x\ \ \lambda y.x)$, is $x$ bound or free, or is it senseless to speak of "x" outside of the scope of either the function or argument expressions?


texts: Difference between $\mathsf{SIZE}(n^k)$ vs $\mathsf{P/poly}$ and $\mathsf{SIZE}(n)$ vs linear size circuit?

texts:
In the Wikipedia page on the Karp–Lipton theorem it is mentioned that $$\Sigma_2\not\subseteq\mathsf{SIZE}(n^k)$$ (which is known) is not same as $$\Sigma_2\not\subseteq\mathsf{P/Poly}$$ (which is open). I was of the opinion $\mathsf{P/Poly}$ referred to polynomial size circuits which seems same as $\mathsf{SIZE}(n^k)$. Why are these circuit complexity classes different? Could someone provide an illuminating example?

Does this mean that $\mathsf{NP}\subseteq\mathsf{P/Poly}$ is possible but $\mathsf{3}$-$\mathsf{SAT}\in\mathsf{SIZE}(n)$ is impossible?

For example in this paper it is shown $\mathsf{PP}$ has linear sized circuits with respect to an oracle but not even a quantum circuit of size $\mathsf{SIZE}(n^k)$. But at $k=1$ linear circuits coincide with $\mathsf{SIZE}(n)$. Correct?


texts:
Just a quick question here, is there a known description of a graph family where for every graph $G=(V,E)$ it holds that for every $(u,v) \in E$ you have $|N(u) \cap N(v)| \geq k$? There was a definition for such graph as $k$-community. Even non-trivial examples (e.g., cliques) might be interesting.

Also, how to construct a graph which is a $k$-community, but does not have a $k+2$ clique? Is it possible at all?

Note that non-trivial cases also exclude not connected graphs and 1-vertex graphs.


texts: Drawing Annotated Parse Tree for Syntax Directed Definition

texts:
Im trying to draw an annotated parse tree for 3*5+4n, the text book shows the following:

[Compilers - Principles, techniques and tools (Dragon Book) by Aho, p308]

I have a few questions regarding this

Why is 3*5+4 considered as a single string? Can't I draw a parse tree something like
for the same string ie:with operator at the node
What is the need for giving T.VAL=3 and then giving another child F.VAL=3. (I understand that the integer attribute for digit needs to be supplied by the lexical analyzer)


texts:
Nodes A and B are accessing a shared medium using CSMA/CD, with propagation delay
of 245 bit times between them (i.e., propagation delay equals to the amount of time to transmit 245 bits). Minimum frame size is 64 bytes. Suppose node  begins transmitting a frame at  = 0 bit time. Before A finishes, node B begins transmitting a frame. Assume no other nodes are active.

What is the latest time by which B can begin its transmission?

Attempt:
Considering that t=512 bit times is the time at which A finishes transmission, shouldn't the latest time by which B begins its transmission be at t=245 bit time? (At t=1, 1st bit is pushed on the link, and at t=245 bit time, this is the last "timing" that B can start transmitting before it senses that A is transmitting). However, the answer given is 244 bit time and I do not understand why.


texts: Understanding B tree key deletion step from CLRS algorithm

texts:
CLRS explains B tree key deletion as follows:

  If the key $k$ is in node $x$ and $x$ is a leaf, delete the key $k$ from $x$.
  If the key $k$ is in node $x$ and $x$ is an internal node, do the following:

  a. If the child $y$ that precedes $k$ in node $x$ has at least $t$ keys, then find the predecessor $k'$ of $k$ in the subtree rooted at $y$. Recursively delete $k'$, and replace $k$ by $k'$ in x. (We can find $k'$ and delete it in a single downward pass.)

  b. If $y$ has fewer than $t$ keys, then, symmetrically, examine the child $z$ that follows $k$ in node $x$. If $z$ has at least $t$ keys, then find the successor $k'$ of $k$ in the subtree rooted at $z$. Recursively delete $k'$, and replace $k$ by $k'$in $x$. (We can find $k'$ and delete it in a single downward pass.)

  c. Otherwise, if both $y$ and $z$ have only $t-1$ keys, merge $k$ and all of $z$ into $y$, so that $x$ loses both $k$ and the pointer to $z$, and $y$ now contains $2t-1$ keys. Then free $z$ and recursively delete $k$ from $y$.
  If the key $k$ is not present in internal node $x$, determine the root $x.c_i$ of the appropriate subtree that must contain $k$, if $k$ is in the tree at all. If $x.c_i$ has only $t-1$ keys, execute step 3a or 3b as necessary to guarantee that we descend to a node containing at least $t$ keys. Then finish by recursing on the appropriate child of $x$.

  a. If $x.c_i$ has only $t - 1$ keys but has an immediate sibling with at least $t$ keys, give $x.c_i$ an extra key by moving a key from $x$ down into $x.c_i$ , moving a key from $x.c_i$’s immediate left or right sibling up into x, and moving the appropriate child pointer from the sibling into $x.c_i$.

  b. If $x.c_i$ and both of $x.c_i$ ’s immediate siblings have $t - 1$ keys, merge $x.c_i$ with one sibling, which involves moving a key from $x$ down into the new merged node to become the median key for that node.

I have a doubt in step 2c. In this step, $y$ is a node containing the predecessor of the key and $z$ is a node containing the successor of the key, both of which has minimum number of keys ($t-1$) and hence authors say we need to merge both of nodes. The authors give following example:

  First tree is before deleting $G$, second is after deleting $G$, which utilized step 2c.

  Here, $y=[D,E]$ is a predecessor node of $G$, with predecessor $E$ and $z=[J,K]$ is a successor node of $G$, with successor $J$. So we merge both $[D,E]$ and $[J,K]$ forming $[D,E,J,K]$.

My doubt is do we always end up successor and predecessor node if they contain minimum number of nodes ($t-1$)? This is what authors must mean to say when they say "merge $k$ and all of $z$ into $y$" in step 2c. But I feel they might not be the predecessor and successor nodes, they are just immediate next children of key $k$, as can be seen in this example I tried out:

Here we have not merged nodes of predecessor (node $[N,O]$) and successor (node $[R,S]$), but have merged immediate children of $Q$, i.e. node $[C,G,L]$ and node $[T,X]$.

So am I right with "we need to merge immediate next children of key $k$ but not predecessor and successor node"? If yes, is book have mistake? Or book does indeed tries to say the same and I am misinterpreting? Or I got it all wrong? Or am unnecessarily overthinking?


texts: Number of contiguous subsequences summing to a given target

texts:
I could not figure out an efficient way (better than $O(n^2)$) to count the number of contiguous subsequences of an array of both positive and negative integers summing up to a given number $k$.

For example, if $A = \{2,5,6,-1\}$ and $k = 5$ then the answer is $2$, since both $5$ and $6,-1$ sum to $5$.


texts: For every non-trivial language $A$ and every finite strict subset $B \subsetneq A$, it's holds that $A \le_m A \setminus B$

texts:
It's claim 1 from Bader Abu Radi's solution to this question.
My solution (have no idea how wrong it is):
$B$ finite $\Rightarrow$ $B\in R \Rightarrow$ exists TM $\langle M_B\rangle$ that halts $B$.
*Wrong from here
Let's define reduction $f$ from $A$ to $A \setminus B$, in the following way $f(\langle M_B\rangle , x)=\langle M_A\rangle$
When $M_A$ implemented on input $w$ like this:

Run $M_B$ on $w$ and answer on the same way

$x\in B \Rightarrow M_B$ accept $x\Rightarrow M_A$ accept $x\Rightarrow x\in M_A$
$x\notin B \Rightarrow M_B$ reject $x\Rightarrow M_A$ reject $x\Rightarrow x\notin M_A$
till here
So the reduction $A \le_m A \setminus B$ true.
As I wrote early not sure how wrong is it, additionaly what're the changes that should be done to proof the second claim ($A \setminus B \le_m A$) from the same answer.
Edit
$f(x)=x'=x\setminus x_B$ (when $x_B$ is all the $x$ that accepted by $M_B$), because $M_B$ halts on $B$ the reduction is applicable and work for any $x$.
It's implemented in the following way:

run $M_B$ on $x$ (halts), if $M_B$ accept, $x'$ reject
otherwise return $x$

If $x\notin A \Rightarrow x'\notin A \setminus B$
If $x\in A$:
$x\in B \Rightarrow M_B$ accept $x \Rightarrow x'$ reject $\Rightarrow x'\notin A\setminus B$
$x\notin B \Rightarrow M_B$ reject $x \Rightarrow x'=x\Rightarrow x'\in A\setminus B$
Is this one correct? Should something be added to it?


texts: Dynamic Programming, Binary Tree: How to factor in depth to recursion?

texts:
I have the following problem.

I have a set of elements $x_0,\ldots,x_n$ which must retain their order inside the binary tree: if, given $x_i, x_j, i < j$, $x_i$ must be to the left of $x_j$ if $x_j$ is the root and $x_i$ is part of $x_j$'s subtree.

I also have a set of frequencies $f_0,\ldots,f_n$.  I need to build a binary tree such that the cost of accessing the elements, defined as $depth$*$f$ is minimized.

I figured this was just like chain matrix multiply, so I wrote that the dynamic table was:

T(i,j) = minimum cost tree between i and j

And I wrote the following recurrence:

$$
T(i,j) = min \lbrace T(i,k) + T(k,j)\rbrace, i \le k < j
$$

However, I can't figure out if depth is being factored in here--it appears (to me) that it isn't.

How do I construct this recurrence??


texts: Computing order statistics $1,2,4,8,\ldots,n$

texts:
On an array of $n = 2^k$ numbers, where $k$ is a non-negative integer, the $k = \log n$ order statistics $1, 2, 4, 8,\ldots, 2^k$ can all be determined in a total of $Θ(n)$ time in the worst case.

I think that this statement is wrong because the loop will take $k$ iterations. So, the time should be $Θ(\log(n))$. But, I'm not sure my guess is correct. Could you tell me whether or not my guess is correct?


texts: Find optimal redistribution in flow graph

texts:
I have directed graph (maybe with cycles), and some resources in vertices (let's say gold). I can transfer gold between vertices only in direction of edges. The task is to minimize maximum value of resources in vertices (e.g. make optimal redistribution of gold).

For example,

Optimal distribution for this graph is following:

6 => 5 => 5 => 5

So the answer is 6.

Or another example:

The answer is 9.

I think that solution should be based on finding max flow in graph and binary search for answer, but I can't connect these approaches and build proper solution. Could you please help?


texts: Find the number of strings in the language $(∅∅^∗ + ∅)$

texts:
Consider the language $L = \emptyset\emptyset^∗ + \emptyset$.

How many words does $L$ contain? Zero or one?

Note: $\emptyset^∗ =\{\epsilon\}$.


texts: Describe a Turing machine that accepts a word iff there are twice as many 0's as 1's

texts: Can anyone help me describe a Turing machine the language of which is the set of the words that have twice as many 0's as 1's? Assume the alphabet is $\{0,1\}$.


texts: Problem with derivative of sigmoid activation function

texts:
I'm following Jeff heatons book 'Introduction to Neural Networks with Java'.
To get node deltas, we need to calculate $f'(sum)$. In the very first row for Training Element #1, we need to compute $f'(1.13) \cdot 0.25$ which Heaton evaluates to $0.045$.

Using my calculator, I get $f'(1.13)=-0.13$ (derivative of sigmoid activation function), then I multiply by $0.25$ to get $-0.0325$. I've been trying to figure out for days how heaton does his calculation but no success yet. Kindly assist.


texts:
I'm reading on wikipedia about P vs NP and I have a question.
Consider the zero sum problem: given a set of integer A, determine if there is a non empty subset such that the sum of all its elements is zero. The problem needs exponential time to be solved because (1) nobody found a polynomial algorithm and because (2) the size of the input is |A| and there are 2^|A| subsets to check.
Is it right to feed the Turing machine with just the input A and pretending to find a polynomial time algorithm? The input needs to be decompressed/unzipped, no?
In other words suppose we have two Turing machine Te and Ti for the zero sum problem: Ti is the implicit/standard version, it reads a set of integer as input and accepts it if there is a non empty subset such that the sum of its elements is zero, Te is the explicit version and it reads a sequence of sets and accepts the input if there is a set in the sequence such that the sum of its elements is zero. Te runs in polynomial time and Ti in exponential time but they solve a similar problem.
Is the problem of P vs NP just a problem of implicit vs explicit input, like Te and Ti?


texts: Is this language is Context-free language or not?

texts:
Is anybody can help me please to determine is this language is Context-free language or not?

L={wvw | w,v∈{a,b,c}+}

for example:

part of the language: acbac, abcab, bbcbb

not part of the language: abab, aa, abcc

I tried to prove using pumping lemma for context-free languages like that:

I take this word from language w=aacbbaa.
I split the word to 5 parts uvxyz and if I can pump u and y and the word stays inside  language the language is context-free:

u-aa, v-cc, x-b, y=bb, z=aa
after I pump v and y the word is still in language->
u-aa, v-cccc, x-b, y=bbbb, z=aa ->
aaccccbbbbbaa

But the answer inside answers section is that the language is not context-free.

What wrong with my prof?


texts:
I need to apply the unification function to unify the following expression:

foo(X,X,Y) and foo(Z,p(Z),w)

So far, I've determined that I must substitute 'w's for occurances of 'Y', making

foo(X,X,w) and foo(Z,p(Z),w)

Then, I can saw X/Z (replaces 'Z' with 'X'), making:

foo(X,X,w) and foo(X,p(X),w)

Now all that's left is making p(X) equivalent to X

My question here is, is it allowed to replace this P(X) with X using the substitution X/p(X)? Or am I going about the question in the wrong pattern?

Thank you!


texts: One-way function is not injective when it is in NP

texts:
Let us $\Sigma = \{0,1\}$ and $f: \Sigma^* \rightarrow \Sigma^* \in FP$ for which is valid that $\exists k: \forall x \in \Sigma^* : \lvert x \rvert ^ {1/k} \leq \lvert f(x) \rvert \leq \lvert x \rvert ^ k$. Thus, we can say that the function $f$ is one-way function.

We have language $L = \{ w \; | \; \exists z \in \Sigma^*, w = f(z)\}$. The question is, how to prove that $f$ is not injective if $L \in NP \setminus UP$, where $UP$ is the class of unambiguous TM.

It is clear, that if $L \in NP \setminus UP$ then exists NTM which decides this language and may exist at least one acceptable path for $w \in L$.


texts: Find the minimum cost of adding the elements of a set (greedy algorithm)

texts:
I'm VERY stuck with this problem:
Given a set (with possible repeated elements), the cost of adding two elements $x, y$ is $x + y$.
For example, the possible costs of the next set $\{1,2,5 \}$ are:

The cost of adding $1 + 2$ (with cost $3$), plus the cost of $3 + 5$ (with cost $8$). The overall cost is $11$.
The cost of adding $1 + 5$ (with cost $6$), plus the cost of $6 + 2$ (with cost $8$). The overall cost is $14$.
The cost of adding $2 + 5$ (with cost $7$), plus the cost of $7 + 1$ (with cost $8$). The overall cost is $15$.

We want to find the minimum overall cost (implementing a greedy-algorithm).
I've implemented two approaches:
const minCost = (l = []) => {
    sort(l);
    let cost = 0;
    let currentSum = 0;
    for(let i = 0; i < l.length - 1; i++){
        if(i === 0){
            currentSum = l[i] + l[i + 1];
            cost += currentSum;
        }
        else{
            currentSum += l[i + 1];
            cost += currentSum;
        }
    }
    return cost;
}

What im doing here is sorting in ascending order, and then simply computing the costs (like the first option in the example).
The issue I found is with the following instance: [2,2,2,2] will compute a cost of 18. But, I've realized that you can group the elements and compute the cost of the in this way: ((2+2) + (2+2)), with overall cost of 16.
So I also came out with this approach:
const cost = (l = []) => {
    if(l.length <= 1) return 0
    else return l.reduce((acc, val) => acc + val, 0)
}

const minCostRecursive = (l = []) => {
    if(l.length <= 2) return cost(l)
    let left = minCostRecursive([...l.slice(0, Math.ceil(l.length/2) )])
    let right = minCostRecursive([...l.slice(Math.ceil(l.length/2), l.length)])
    let newList = []
    left > 0 ? newList.push(left) : newList.push(...l.slice(0, Math.ceil(l.length/2)))
    right > 0 ? newList.push(right) : newList.push(...l.slice(Math.ceil(l.length/2), l.length))
    return left + right + minCostRecursive(newList)
}

The main idea is to partition the cost of the halves. If you have two items, the cost is the sum of the items. If you have one or fewer items, the cost is 0 (there is nothing to add). If not, I make a recursive call to the function with the halves, and with if its result is greater than zero, then I add it to a new list. If not, I add the element that was there before, and call the function again.
But also, I found a counterexample [1,5,7,9] (in the first implementation it gives 41, but in the second returns 44). Moreover, I think this isn't a greedy solution.


texts:
I'm currently learning computer science, and there is a slide of notes brief described the parallel radix sort under data parallelism.

number 101 110 011 001 111 (1st bit)
order    2   1   3   4   5 (new order)
number 110 101 011 001 111 (2nd bit)
order    3   1   4   2   5 (new order)
number 101 001 110 011 111 (3rd bit)
order    3   1   4   2   5 (new order)
number 001 011 101 110 111

I roughly know how to sort it from lecturer's explanation, but how is it related to parallel computing to increase the performance?


texts: Aggregate Rate and Poisson Process in Aloha

texts:
I'm having a hard time understanding what is mean't by the aggregrate rate $\lambda$ and what it means for throughput in unslotted and slotted Aloha protocols. The more I seem to read about poission process the more confused I get.

I understand that the probability a packet is transmitted in a time interval $\delta t$ is $\lambda \times \delta t$ where you have $N$ senders and $Y$ is the aggregate rate from all $N$ senders.

However I don't understand what is mean't by aggregate rate. It's quite a perculiar phrase. Does it mean the probability that any of the $N$ senders will try to transmit, or is the number of packets to be sent by $N$ senders over the time?

Next we're then told that the individual rate for a sender is $\lambda / N$. Because I'm so confused by what is mean't by rate it's hard to begin to think about what this even means.


texts: How to connect line segments to form the least number of paths

texts:
I have a list of unordered line segments, some of whose endpoints lie on the same point. How do I connect these segments efficiently to form a minimal amount of paths?

For example, if I have the following lines $(x_1, y_1, x_2, y_2)$: [[0, 0, 2, 2], [4, 0, 2, 1], [2, 2, 4, 0]] the algorithm should be able to join these three segments into one path $(x, y)$: [[0, 0], [4, 0], [2, 1]].


texts: van Emde Boas tree: why store max recursively?

texts:
In both CLRS (third edition) and Erik Demaine's lecture, the van Emde Boas tree is defined to store max but not min recursively.  Why store max recursively?

If it is not stored recursively, insert(V, x) can take advantage of the special case where a cluster or summary contains one element (min = max), although I think the advantage gained from this is insignificant.  Keith Schwarz implements it this way in his Archive of Interesting Code.  So why do CLRS and Erik not make use of this optimization in the algorithm?  Is it actually a mistake?


texts: Are there conditions under which given text $T$ that huffman code and arithmetic code will produce the exact encoding of $T$?


texts:
I just discovered Context-sensitive grammars.
The problem is most of the examples are weird non-interesting toy languages !
Second the descriptions are math oriented, rather than programmer oriented.
I'm interested in the following points :
1. How do you start to build CSG. What is the process ?
2. CSG examples building Natural and programming languages ?
3. Algorithm for sequence generation given a CSG.

You can skip 3 if the question become too broad.
Context : I'm experimenting with Sequitur algorithm, which generates context-free grammar from presented sequences. I want to understand CSG, so that I can eventually do similar thing.
Then finally I want to use the Grammar to generate prediction/s given start-sub-sequence, but that's for later.
PS> Is there ready made parsers ?


texts:
In NLP, does the lexer have to tag the tokens before the parser?

I.e. does the lexer have to classify the tokens to morphological categories before the parser?

I'm thinking yes, but is this also the only way to do the parsing?


texts:
I have 1D data for binary classification. Data includes about 10000 samples and each sample has the length of 120. Data is only partially labeled (for about 20% of samples, I am sure about the label) and I cannot label samples manually for thoes not labeled. Every ~60 samples come from same recording and therefore belong to the same class. I have tried k-mean clustering and in most cases results matches the labels. What semi-supervised learning algorithm is suitable for this problem?

There are 142 different recordings, each repeated ~60 times. About 20% (28 recording) are labeled. Samples are noisy so I need to average every 5-10 of them. I extracted 10 features based on amplitude of signal for clustering. I expect 60-80% of recordings belong to class I.


texts: Training a neural net without labels in Reinforcement Learning

texts:
I am trying to dig further into machine learning and I am making a program to play a game as a start. I have created a game that is based on the mobile game Flappy Bird and can be generalized to the following:

Actions $A = \{\text{no action}, \text{tap}\}$
States $S \subset \mathbb{R}^3$ such that $s \in S$,

$s_1$ is the horizontal distance to the center of the nearest forward gap
$s_2$ is the vertical distance to the center of the nearest forward gap
$s_3$ is the vertical velocity ($\text{unit}/\text{sec}$)

As a starting point, I have implemented a naive Q-Learning algorithm with positive rewards whenever it passes through a gap successfully. Everything went well and the q-table ($f(s): S \to A$) was adjusted accordingly to the rewards.

Now I would like to train a neural net to do the same. One problem that existed with the Q-Learning approach is that the algorithm does not take locality into account. I had to also discretize the feature space into very huge chunks which is not optimal. I am hoping that a neural net can solve these issues.

I am familiar with performing basic classifications with neural nets, and so I am trying to approach this problem similarly. I would just take a state (a vector of three real numbers) as input and an action as output (one neuron per action and take the one with the highest probability). The problem is, I do not have labels for training! The only thing that I get from the game is reward.

Is a neural net a good choice for this type of problem? How should I train or design such network?


texts: Connected Graph: Select the minimum number of nodes such that the node and neighbor covers everything

texts:
The problem is to select the minimum number of nodes from a graph such that, the selected nodes and their neighbors consists of all the nodes of the graph.

Any straight forward algorithm for this?
Repeatedly selecting the node with highest degree centrality doesn't work.

Thank you.


texts: Lower upper bound on # variables in k-SAT with m clauses

texts:
If I have an instance of $k$-SAT with $m$ clauses, then a trivial upper bound on the number of variables $n$ is given by $n \leq mk$. But we can only have $n = mk$ when no variable is repeated and that would be a trivial yes-case of k-SAT. I am making some running time analysis based on number of clauses, and therefore need to eliminate $n$ from my formula.

So my question is, can I make a lower upper bound on the number of variables, above which the instances will always be trivial?

I have a feeling that $\frac{1}{2}mk$ should be possible (I even think I had the argument for this in my head at some point), because $mk$ is actually an upper bound on the number of literals, not variables, but I can't be sure that all literals are present in both negated and unnegated form, and therefore can't seem to find an argument for this.


texts:
I would like to write a function that returns a 2D array of floating point numbers representing pixels in an image. I have tried implementing perlin noise 3 times and have followed this (https://www.youtube.com/watch?v=MJ3bvCkHJtE&t=1008s) video. So far, I've been getting numbers larger than 1 as my final result. I've tried reading the wikipedia page on perlin noise, but they aren't written in English a normal person could understand. Could someone guide me through the perlin noise algorithm and provide an example, preferably in C (I also know C++, Python, Java and javascript). Thanks. (If you prefer simply fixing my existing code, I'd be happy to provide it, just let me know)
UPDATE:
I read the Wikipedia page on perlin noise (as Yuval Filmus recommended in the comments) and I have several questions:
What does randomGradient do and how does it work? Why aren't the numbers it returns truly random?
How are the grid cell coordinates calculated (why is there x0 and x1 + y0 and y1)?
What does (the) permutation (array) do? I have no clue what permutation is.


texts: Is a finite Solomonoff learner worse than human learning?

texts:
An elegant program for a bitstring is the shortest program on a universal Turing machine that outputs this bitstring.  According to Kolmogorov complexity, the length of the elegant program is independent of the Turing machine implementation.

Solomonoff induction uses the elegant program for a bitstring to predict the next digit.
This is a universal prior given the minimal assumption the output is generated by a Turing machine.

We can use this insight to build a machine learning algorithm called a finite Solmonoff learner.
The difference between a finite Solomonoff learner and the original Solmonoff induction algorithm is the finite learner does not have access to all elegant programs.
There is no algorithm that can generate all the elegant programs, so the elegant programs the finite learner can use must be stored in memory.
With a finite amount of memory, there is a limit to the elegant programs that can be stored and consequently used by the finite learner for prediction.

The limit exists because there are a finite number of elegant programs of a certain length L.  When the bitstring of 1s becomes long enough, it is not possible for there to be an elegant program representing the bitstring to be of length L or shorter.
If L is the amount of memory available, then eventually the elegant programs will all be longer than L, and none will fit in memory.

Now let's assume we have a very long string of 1s, and we remove one digit to make a prediction problem.

As a concrete example, our bitstring is:

11111111111111111111

We remove a 1 at random:

111111111111111_1111

The learner must figure out the most likely digit to go in the empty spot.

For a given amount of memory we can make the bitstring of 1s long enough that its elegant program cannot fit in memory.
In this case, the finite Solomonoff learner will not be able to access the elegant program for the bitstring, and will thus be incapable of predicting the digit that goes in the empty slot.

To continue the example, assume the elegant program that generates the 1s is:

10001011

Furthermore, the amount of memory available is 7 bits.  Consequently, the 8 bit elegant program cannot be stored in memory, and the finite learner cannot figure out what goes in the empty slot.

On the other hand, regardless of how long the bitstring of 1s becomes, a human will have no problem identifying the missing digit.  A human has finite memory and cannot access all elegant programs to make predictions.  Despite having the same handicap as a finite learner, the human can outperform the finite learner infinitely often.

Does this demonstrate Solomonoff learning is less powerful than human learning?


texts: Finite State Machine with limited operations

texts:
I have to implement a state machine in some special hardware which has a lot of limitations. This hardware can be understood as a box that gets events as inputs and could output events.

The state machine is very small 3-4 states that are al connected as a ring 0->1->2->3->0 plus some states have loops with themselves. Thus the new state will always be either the same or current + 1 mod N.

A state change can be triggered by two things:

A given event can trigger a state change.
There is a global counter that increases every time an event arrives. If the counter reaches certain value (depending on the current state) that can trigger a state change.

The biggest problem is that every time an event arrives at the box I can only do the following:

Read the counter value, increase it by one and save it in memory again.
Read the current state and I have to compute instantaneously the next state and save it. Variables can not be accesses twice. Meaning that I can not read it, do a complex operation and then write the new state down. The only thing I am allowed to do is: I can define 2 simple boolean expressions of the form (+- current_state +/- variable (==, !=, >, >=,...) Constant. The output of those 2 bolean expressions can be used to decide how the state is updated. However the only thing you can do is: update the state in way A (i.e state+1), update state in way B (i.e state -1) and not modify it.

For example:

if expression1:
    state= state+1
if expresion2 and not expresion1:
    state= state-1

if not expresion1 and not expresion2:
   state = state.

Basically the hardware circuit that is executed is comprised of the following:

2 comparison units that can produce 2 bolean outputs (as explained above).
2 ALUS that can perform fixed operations if enabled using the result of the comparisons.
The result of the ALU can be written back to memory, (this is our state).
The updated state can be outputted from the box.

I know it might be a bit confusing, but I did not find a better way to explain the hardware using a small text. I can clarify things.

Question:

Do you think there is a way to implement a small state machine given those constrains?


texts: What we lack to do automatic programming?

texts: From time to time I am trying to implement automatic programming system. We already have the formalization of norms (laws/legislation, business policies and rules) as some kind of deontic logic (there have been endeavours to convert deontic logic formulae into executable rules). We have ontology of GUI elements. So - we have specification. But how to convert this specification into executable code? What we lack to do automatic programming at least in the domain of business software (that is specified by legislation and enterprise rules)?


texts: Coming up with loop invariants involving k?

texts:
void min(arr[], n){
for(i = 0;i < n; ++i)
{
   // Change < to > if you want to find the smallest element
   if(arr[i] > arr[i+1])
       arr[i] = arr[i+1];
}

To avoid wording about a "just check my work" question. I will try to explain what I do not understand about this topic of loop invaraints. I have been having the hardest time coming up with the beginning loop variant with respect to the variables and the what they mean in relation to the arrays. So, my question about this code loop invariant is that this program finds the smallest element in the array. My loop invaraiant is At the start of the iteration when i = k, the item at index k is the smallest item in the range from zero to k. Can you tell me both if I have the correct loop invariant and also am I understanding the concept correctly. I believe that I need to relate such variables such as i, and j in loops with the varaible k in relation to what the program is doing. Thank you.


texts:
Let $P$ be a problem that you need to study its difficulty, i.e., NP-hard, Polynomial-time solvable, etc.

  My question is: If I reduce a known polynomial time problem (say,
  maximum matching in bipartite graph) to $P$, why I can say that $P$ is an
  easy problem?

  My guess is: No, we cannot say that.

  Why? Because from an instance of maximum matching problem, $I_{ MM }$,
  I create an instance of $P$, $I_{ P }$, and then I show that maximum
  matching is solved with $I_{ MM }\iff P$ is solved with $I_{ P }$.

  But what if from another instance of maximum matching problem, $I_{ MM }'$
  , I create another instance of $P$, $I_{ P }'$, which is hard to
  solve?

I have read that the reduction is correct and works, for example from sorting to convex hull, but I do not why.

I do not know what I am missing here.


texts: Choosing nonzero entries from an array so no pair in same row or column

texts:
Suppose we have an $n\times n$ array $A$ of non-negative real numbers in which the sum of each row and each column is $1$.  We want to find $n$ entries of the array $(x_1,y_1), \dots, (x_n,y_n)$ such that

each $A[x_i,y_i]>0$ and
no pair $(x_i,y_i),(x_j,y_j)$ are in the same row or column (i.e., $i\neq j$ implies that $x_i\neq x_j$ or $y_i\neq y_j$ or both).

How can we prove that such a set of entries always exists?

Here is an example solution with a $3\times3$ table.


texts:
My friend and I were studying NP-hard problems and NP-completeness. I don't think we have understood the concept very well so I thought I would come here to solve our doubt.

To show that a given problem is in NP, we have to verify a solution to a given instance of the problem can be solved in polynomial time. We get this. What we wanted to know is that is by default then every existing problem is in NP until a solution for the problem is derived in polynomial time? Or is it that we have completely missed the concept?


texts: If a connected graph has a bridge then it has a cut vertex

texts:
Is it true that if a connected graph has a bridge then it has a cut vertex?

In my point of view, I don't think it is true to consider that a graph having a cut edge will definitely have cut vertex.

Consider a graph with a single edge $uv$; if we remove this edge, the graph will get disconnected but if we remove $u$, the graph will be connected as a graph with the single vertex is still consider connected.


texts: What is the difference between Strict 2Phase Locking and 2Phase Locking?

texts:
I have read some notes about the two but yet still confused about why there is a need for the strict 2phase locking. Based on some slides,

Two Phase Locking  and  Strict Two Phase Locking

They have a single difference which is :

If transaction T releases any lock, it can acquire no new locks. <-
2PL
Hold all locks until end of transaction. <- S2PL

I will like a practical example of a Transaction in both strict and normal.Highlighting the differences.


texts: What is the best solving algorithm for a game with stacks?

texts:
Game Explanation: Suppose there is a game with cards that have numbers from 1 to n. Each card has a different number so there are not two cards with the same number. The deck is scrambled. We chose one card from the deck and we create a stack. Then when we chose the next if the card is a number lower than the top of the stack we add it to the stack. If the card is greater than the top of the stack we create a new stack with this card as the top. As we progress each card we draw from the deck should go either in one of the stacks (if it is less than the top of at least one of them) or create a new stack (if it is greater than the tops of all the stacks). If the card we drew can go to more than one stack it is our choice as to which stack it should go.

Game rule: If there is at least one stack were a card can go, we cannot create
a new stack with this card as the top.

Game Objective: Finish the game (draw all n cards) with the minimum number of stacks.

My solution: Except the first time we draw were we have to create a stack, the next rounds, when we draw a card, we examine the top of each stack and find the minimum top call it M1 . Then if the card can go there (less than M1) we place it there. If it is greater than M1, we place it in the next minimum top we can. That way, we leave the tops that have greater numbers open for new numbers that could be greater than the one we drew this round, thus we minimize the possibility of creating a new stack.

My question: Is my solution correct? If it is, is there any solution better than mine? I think my solution is O(n*m), where n is the number of cards and m the number of stacks. Is there a solution with better complexity?

First Attempt at proving that the algorithm is optimal (based on links provided) :
Let f be the number of stacks and A our algorithm and O an optimal algorithm.
For i=1 card deck: then f(A) <= f(O), they will actually be equal f(A)=f(O), because each algorithm must create a stack with the first card (by rule). If f(A)<=f(O) for i=n then for i=n+1 (I don't know how to prove that f(A)<=f(O) here).

Second Attempt:

My proof: At the base the number of stacks will be equal as I mention above. Then suppose that the state $A^{i-1} \preceq O^{i-1} $ .

This means that the vectors will be the following

$(t_1,\dots,t_k) \prec (u_1,\dots,u_\ell)$ if $k \prec \ell$
$(t_1,\dots,t_k) \prec (t_1, \dots, t_j, u_{j+1}, \dots, u_k)$ if $t_{j+1} \prec u_{j+1}$.

In case number 1 the number of stacks in A is less than or equal to the one of O.
I think it is obvious that if another element (card) was to be added to both of those vectors, the resulting vectors would be either equal in number of stacks (if only the left vector stack number increases) or again $(t_1,\dots,t_{k+1}) \prec (u_1,\dots,u_{\ell+1} )$ where $k+1 \prec \ell +1$. I have two problems here. The first is that I can't prove this for case number 2 and also this proof is if we supposed $A^{i-1} \prec O^{i-1} $.


texts: Proving Space Requirements for van Emde Boas Tree Recurrence Relation

texts:
I know the space requirements for a van Emde Boas tree is $Θ(u)$, and that the recurrence relation for this looks like:

$$S(u) = (\sqrt u + 1) S(\sqrt u) + Θ(\sqrt u)$$

I'm curious and can't seem to find it anywhere but, how would one go about proving this recurrence relation is true? I.e., how do you prove $S(u) = Θ(u)$ ?


texts: If I have sources and sinks of a DAG can I find the minimum number of edges to be added to make it Strongly Connected?

texts:
I am trying to create an algorithm in linear time where if given a directed acyclic graph I can add edges to make it strongly connected components.

I believe I have an algorithm to identify sources and sinks in the input list of edges in form

1 2
2 5
3 1
etc

And I know that the minimum number of edges to be added in order to create connected components is equal to MAX(sources,sinks).

My question is, is there a way to come up with where I should add edges so that I can have the minimum number and still be linear complexity?

Here is an example of what I'm after.

Given this input edges:

1 3
1 4
2 3
2 4
5 7
5 8
6 8
6 9

Output these edges to be added:

3 1
4 5
7 6
8 1
9 2


texts:
Some hypervisors optimize memory usage using a method that is called ballooning (at least that's what KVM calls it), this method deduplicates memory between VMs and sets common pages to read-only with copy on write.
This is sort of the opposite of a fork call.

Is it feasible to implement on an OS level for processes (I was mainly thinking of for the duplication of memory when browsing with Chromium with multiple tabs on the same site), has it been implemented already?


texts: Algorithm: ordering non-overlapping intervals

texts:
Assume we have a (multi)set of nontrivial intervals $\mathcal{I} = \{I_1,...,I_n\}$ and for any two $I_i, I_j \in \mathcal{I}$, we have that $I_i \cap I_j$ is trivial (that is: contains at most one point), or one of them contains the other. Just to clarify, an example would be $\mathcal{I} = \{[0,10], [2,6],[6,8], [2,4],[2,3],[5,6],[6,7]\}$. For the sake of simplicity, assume there is a longest interval that contains all other intervals, call that the root.

We can arrange such (multi)sets as a tree where $I_i$ is a descendant of $I_j$ iff $I_i \subseteq I_j$ (if an interval has multiplicity $> 1$, then its multiple occurrences can form a path in the tree). What I want to do is find such a tree. It's clearly possible in $\mathcal{O}(n^2)$ time: sort the intervals by length in descending order and process them in that order. Whenever we insert the next interval $I_i$ into the tree, find the shortest interval already in the tree $I_j$ such that $I_i \subseteq I_j$; such an $I_j$ must exist since the root contains all other intervals.

I would like to do this in $\mathcal{O}(n \log n)$ time and it seems to me that should be possible. Rough ideas include using interval trees and trying to construct the tree from the bottom up starting from its leaves, or figuring out how to annotate search trees to do something like this for me, but nothing successful so far.


texts: Is the longest path in a (weighted) DAG always from a source to a sink? This seems correct to me by intuition, but I'm not 100% confident. Like, for example, if I had an array in which each index represented a node in topological order, and stored the length of the longest path with that node as its endpoint in the graph at that index, would the longest path in the graph always be stored in the last index?


texts: Optimization of Thompson Construction of an NFA

texts: I would like to ask under which circumstances can these optimizations be used,supposed that they are part of a bigger NFA and when can they lead to an error ??


texts: Is correctness implied by an optimality proof?

texts:
New to proofs (in the context of analysis of algorithms).
I'm wondering, if I were to prove a greedy algorithm is the optimal solution, does this imply its correctness as well? (partial correctness + termination).
I'm trying to understand how The Job Sequencing Problem is correct but can only find proofs for its optimality. How can we be sure this algorithm is correct?
EDIT: I have found an excellent resource that uses a proof of optimality to show (I think) partial correctness as well. It is here but for the life of me I cannot understand it. A layman's explanation would be amazing!


texts: Find points that lie outside of a series of triangles

texts:
Suppose there are $n$ triangles on a 2D plane, which don't cross each other and have no common vertex. Suggest an algorithm that gets $n$ points and in $O(n \log n)$ determines the points that don't lie in any triangle. What if the triangles could overlap.

I found some algorithms to determine if a point is inside a triangle or not, but checking this process for all points and triangles is at least $O(n^2)$

Do you have any suggestion?


texts: Why does little endian apply to numbers and not to text strings?

texts:
The Portable Executable file format is the format that Windows EXE files use.

It is a binary format.

Numbers are in little endian form. Thus, the following hex represents the decimal number 256, not 1.

00 01

Some fields in the file format represent text strings. For example, the "Name" field contains a null-terminated string that has up to 8 characters. Here are the hex bytes for a name and in parentheses the corresponding string:

2E 64 61 74 61 00 00 00 (.data)

My question is this: The file's byte order is little endian and therefore the bytes in a number are interpreted from right-to-left. Why aren't the bytes in a string interpreted right-to-left? Why aren't the bytes for the above string this:

00 00 00 63 74 61 64 2E

Notice that I reversed the order of the bytes. That's not how it is in EXE files, but why not? Why does "little endian" apply only to numbers and not to text strings?


texts: Help understanding an audio processing algorithm

texts:
I'm reading “Speech segmentation without speech recognition” by Dong Wang, Lie Lu and Hong-Jiang Zhang.
The algorithm I'm looking at is a V/C/P (Vowel/Consonant/Pause) classification algorithm on a digital speech signal. It is described as such:

Audio data is segmented into 20ms-long non-overlapping frames,
where features, including ZCR, Energy and Pitch, are extracted.
Energy and pitch curve is smoothed.
The  Mean_En and  Std_En of energy curve are calculated to
coarsely estimate the background noise energy level, as:

NoiseLevel = Mean_En - 0.75 Std_En.

Similarly the threshold of ZCR (ZCR_dyna) is defined as:

ZCR_dyna = Mean_ZCR + 0.5 Std_ZCR

Frames are classified as V/C/P coarsely by using the following
rules, where FrameType is used to denote the type of each frame.

If ZCR > ZCR_dyna then FrameType = Consonant
Else if Energy < NoiseLevel, then  FrameType = Pause
Else FrameType = Vowel

Update the NoiseLevel as the weighted average energy of the
frames at each vowel boundary and the background segments.
Re-classify the frames using algorithm in step 4 with the updated
NoiseLevel. Pauses are merged by removing isolated short
consonants. Vowel will be split at its energy valley if its duration is
too long

I do not understand step #5. Like I don't know how to interpret the wording - is there another way to describe what they are doing? I get that we want to update the NoiseLevel variable and re-run step #4 for every frame, I just don't understand how exactly.


texts: Designing a 2 place function that is not Turing computable

texts:
I'm just refreshing my memory on Turing machines and computability, and I was wondering how to design a function of 2 arguments that is guaranteed not to be computable. I've seen the proof (by diagonalization) for one argument functions, and I'd like to make sure I have the right idea. For functions with 2 arguments, a sketch of my proof is as follows:

Let f_{1},f_{2}... be a listing of all 2 argument Turing computable functions

Let d be a 2 place function (and assume that it is Turing computable) such that d(x,y)=1 if the xth function in the list of Turing computable functions returns 0, and return 1 otherwise. Then d is not in our list of functions, but it was assumed that it was. Therefore, d is not a computable function of 2 arguments. Sorry for the lack of latex, hopefully this is understandable without it for now.


texts: How do I measure the reliability of a confidence value in a predictive algorithm?

texts:
Supposing I have some algorithm that is able to provide me with a confidence value for some event occurring. Let's say on day 1 it tells me that there is a 80% chance it will rain, on day 2 it tells me there is a 20% chance that the mail will be late, and on day 3 it tells me that there's a 90% chance my milk will go off.

3 days later, I measure what actually happened and come up with this result:

Confidence  Occurrence
80.000%         false
20.000%         false
90.000%         true

In other words, it did not rain on day 1, the mail was not late on day 2, and my milk did go off on day 3.

Supposing that the data set is large, but that the confidence values remain distributed and not confined to any particular range, how do I go about measuring the "reliability" of my algorithm, and what metrics could I use?

Note that the floating-point precision of the confidence value is high (say a 8-byte double). I know I could simply divide each confidence up and measure the samples in "buckets", but this would reduce the reliability of the result as it would require me to trade off between reducing the sample set for each range or accepting a larger error in the form of a broader test range. I want to use all of the information to get an accurate a result as possible.


texts:
P is RE, but is the complement of the class of languages decidable in polynomial time also recursively enumerable?

If both are RE then this makes P recursive?


texts:
Give two functions that is in O(n^2) but not in o(n^2).

The answer is nlogn and n,But I think a lot but can't understand why answer are them.I doubt answers is wrong.

And this question,Give two functions that is in big-omega(n^2) not in
little-omega(n^2)?

The answer is n^2logn and n^3.But I think a lot but can't understand why answer are them.


texts: Most popular path in weighted cylic directed graph

texts:
Context
I have a graph $G=(V,E)$ with weighted edges, all weights are positive integers $w(e)\in\mathbb{N}\setminus\{0\}$. The weights represent the popularity/count of each edge, for example $w(e) = 22$ means that amongst all edges the edge $e$ was visited $22$ times.
Approach
Given two vertices $v,v'$ in $G$, how can I find the "most popular path" ? Knowing the fact finding the max weight path in cyclic directed graph is NP-hard, I changed my approach in the following way:

Normalize the weights to have probabilities $p(e) = \dfrac{w(e)}{Z_w}$ with $Z_w = \sum_{e\in E} w(e)$
Set the cost of a path $P = (e_1,e_2,\dots, e_n)$ as a decreasing function of the product of probabilities $\prod_{i=1}^n p(e_i)$,
for example use the Negative Log Likelihood $\ell(P) = -\sum_{i=1}^n\log p(e_i)$
Use a shortest path algorithm which minimizes the NLL of a path between $v,v'$ to approximate the most popular path. This can be done via setting new weights $\tilde{w}(e) = -\log w(e) + \log Z_w$

Question
Is this approach at least partially correct? Can I trust its results? I will conduct a statistical experiment (on random graphs) later today and post results. Any contribution is appreciated!


texts: Do system calls always means a context switch?

texts:
When a system call takes place some kernel code must be executed. If some kernel code is being executed it means it can alter register values. So before this code gets executed the old process state must be saved. This is called context switch.
Now Wikipedia says that not all system calls need context switch. How is this possible?


texts: Maximizing number of selected squares in a grid

texts:
We have an $n\times n$ grid of squares, each square has a non-negative integer. Two distinct squares are neighbours if they share a row or column. A selection of squares is good if every selected square has a number of selected neighbours less than or equal to its number.

Is there a known way to find the maximum number of elements in a good selection? Clearly there is a $\mathcal O(2^{n^2}n^2)$ brute force algorithm (we can test for goodness of a selection in time $\mathcal O (n^2)$ by precomputing number of selected squares in each row and column).


texts:
I understood what amortized analysis does, but can anyone tell me what is the main purpose of this kind of analysis?

What I understood:

Let say we have 3 three operations a,b,c used 1,2 and 3 times to achieve d. Based on aggregate analysis a,b and c are used 2 times each. Is this correct?

I am trying to understand the advantages of this in CLRS but I am completely lost. For example in dynamic programming we save the answers to sub problems in tables which helps us reduce the running time(lets say from exponential to polynomial). But I am unable to get a complete picture of amortized analysis.


texts: Topological Sort without modifying the graph or marking edges

texts:
I have a DAG which I want to traverse in a topological order. Wikipedia describes two algorithms for topological sorting, which both work in theory but seem impractical to me from a design point of view: Kahn's algorithm modifies the graph (by removing edges) and the DFS-based one marks nodes, which would require me to modify my node classes (by adding a boolean field) and is furthermore not thread safe.

Are there more practical approaches, that preserve the asymptotic runtime but do not interfere with my business logic so much?


texts: Finding the rows/columns of an m-by-m symmetric similarity matrix M which minimizes the sum of the elements in an n-by-n submatrix N, where n < m

texts:
I have a machine learning problem where I need to find the most dissimilar subset of rows/columns of an $m$-by-$m$ symmetric similarity matrix $M$ which minimizes the sum of the elements in an $n$-by-$n$ submatrix $N$, where $n < m$. In other words, by minimizing this sum, we find the most dissimilar rows/columns in $M$ that makes up $N$.
The values of $M$ are real, positive values between zero (dissimilar) and ones (similar). The diagonal consists of ones as the diagonal compares the same object with itself, meaning they definitely are identical. Furthermore, as the matrices are symmetrical, selecting row $i$ from $M$ also includes selecting column $i$ from $M$ (for $N$).
Take a 3-by-3 matrix as an example (i.e. $M$ with $m=3$):
\begin{pmatrix}
1 & 0.8 & 0.2 \\
0.8 & 1 & 0   \\
0.2 & 0 & 1
\end{pmatrix}
In this case, the first and second element are relatively similar (0.8), first and third are relatively dissimilar (0.2), and second and third are completely dissimilar (0). Assuming $n=2$, there are three possible ways to construct the submatrix $N$:

Select first & second row/column:

\begin{pmatrix}
1 & 0.8 \\
0.8 & 1
\end{pmatrix}

Select first and third row/column:

\begin{pmatrix}
1 & 0.2 \\
0.2 & 1
\end{pmatrix}

Select second and third row/column:

\begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix}
For this particular case, we know that the third alternative minimizes the sum. However, scaling this problem to $m=5000$ and $n=400$ makes the problem impossible to compute as the number of possible submatrices gets insanely large.
I was initially considering using the Monte Carlo method, but I'm thinking that there might be a more elegant way to do this. Do you have any pointers?


texts: Feasibility of linear inequalities with binary variables

texts:
I have a system of linear inequalities of the form $A^t x \leq b$, where each of the $x_i$'s is a binary variable in $\{0, 1\}$. Are there any known fast and practical algorithms that can find a feasible solution or prove that the system has no solutions?

I need this to generate an initial solution to the heterogenuous fleet VRP where the number of unknowns is ~ 10s of millions in each instance.


texts: Myhill–Nerode equivalence classes of $\{0^n1^n \mid n \in \mathbb{N}\}$

texts: I am told to find the equivalence classes of the Myhill–Nerode relation of the language $\{0^n1^n \mid n \in \mathbb{N}\}$. For one, I know it has an infinite number of equivalence classes given that it's a non-regular language. Im not sure how to find all the equivalence classes and show how I got those equivalence classes.


texts:
Let $E$ be an equivalence relation defined over a set $S$. The access to $E$ is only via queries of the form $M(s_1,s_2) = 1$ if $s_1$ and $s_2$ are in the same class and $0$ otherwise. Computing $M$ is expensive (say, $O(n^2)$).

I am looking for an efficient data structure $D$ that supports queries of the form "given $s$, does $D$ contain an element $s'$ in the same equivalence class as $s$"?
A naive approach is to search element by element in $D$ and test, but is there other solution?


texts: Name for data structure that keeps track of minimal/maximal element through unit step updates

texts:
There's a data structure that has the following operations:

$\text{init}(n)$ - Initializes $n$ integer elements set to zero, $O(n)$.
$\text{inc}(i)/\text{dec}(i)$ - Increments/decrements the element at index $i$ by one, $O(1)$.
$\text{get}(i)$ - Returns the element at index $i$, $O(1)$.
$\text{min}()/\text{max}()$ - Returns an index containing a minimal/maximal value, $O(1)$.

One possible implementation of the above is a linked list of buckets, each bucket storing the elements of value $k$, combined with a vector storing which bucket an element $i$ is in, and a vector directly to the node inside the bucket.
Does this have a name?


texts: What kind of scheduling problem is this?

texts:
I'm working on a problem and would like to do some research on similar problems to help refine my approach.  Can anyone help me identify what kind of problem this is or, at least, what kind of problems it relates to?

The basic model is a set of different job types, handled by a set of machines.  There is also a dispatcher that carries parts between machines.  I have estimates for the travel times involved when using a dispatcher to perform transfers and I also have estimates for the amount of time required that each job type takes to execute.  The exact process flow between job types is dynamic (i.e. if there are $A$, $B$ and $C$ jobs, the result of $A$ can determine whether it gets routed to either $B$ or $C$.)  New parts can arrive in the system and parts will eventually be routed out of the system after a job completes.

So, in summary:

Setup: Finite set of job types ($J_1, J_2, J_3, ..., J_n$) and machines to execute them ($M_1, M_2, M_3, ..., M_m$); a given job type might have multiple machines that support it.  We can designate $M_{INPUT}$ as a special 'input machine' which can hold multiple parts that are available to be brought in to the system.

Inputs: A set of parts arrive over time at $M_{INPUT}$, where the arrival time can be denoted as $T_i$ and they are each assigned a sequence of jobs to perform $S_i$, though the algorithm cannot know the exact sequence in advance.

Process:

The dispatcher can take one of two actions at any given time:

Decide to move between two machines, where the time to transfer is a known $\tau(M_{i_1},M_{i_2})$.
Decide to exchange the part it currently holds with the part in the machine it is at.  This exchange takes a fixed time $\tau_E$.

Every job type takes a known time $D_k$.  After a given job at a particular machine completes, it assigns the next job in its sequence $S_i$.  If the sequence is exhausted, it is routed to a special machine $M_{OUT}$ for routing out of the system.

Problem: Scheduler algorithm has to produce a series of dispatch orders (either move or exchange operations) to push parts through their job sequences and ultimately out of the system.  The optimization criterion is to be capable of handling aggressive input sequences (more parts, more often), and maximize the number of parts finally moved through $M_{OUT}$ over the execution time of the system.

I believe this is a type of scheduling problem (sounds somewhat similar to Job Shop Scheduling?)  I'm currently approaching this by considering different orderings of upcoming transfers in a branching fashion, generating an estimated timeline up to a certain limit forward in time, then preferring the schedules that move the most parts in the least amount of time.  I'm pretty sure this kind of problem has been studied more rigorously, however and would like to learn more about the theory behind it.


texts: Does selecting the same arm has the same reward?

texts:
In multi-armed bandit problem, we have a set of $K$ arms. In each round $t$, a bandit selects an arm $k$ and receives a reward $r_{kt}$. The objective is to maximize the rewards after $T$ rounds.

My question: Does selecting the same arm in two different rounds leads to the same reward? Or the rewards are completely different?

It is surprising to me if one could select the same arm but receives a different reward and still has a sublinear regret.


texts: Partitioning vertices of colored acyclic digraph

texts:
I have a dag $G=(V,E)$ and a coloring $c:V \to C$ that assigns a color to each vertex.  I want to partition the vertices into groups, in a way that minimizes the number of groups, such that the following conditions are satisfied:

(a) All vertices in the same group must have the same color.

(b) If there is a path $v \leadsto w$ between two different vertices $v,w$, then $v,w$ cannot be placed in the same group.

Is there an efficient algorithm for this problem?

Here is another way to think about this problem.  I have two or more disjoint acyclic directed subgraphs and I want to merge the disjoint subgraphs by joining the nodes into groups, i.e. not creating an edge but by grouping set $V_i$ from subgraph $G_n$ with set $V_j$ from subgraph $G_m$. Edges may only go from one node to another if they are not in the same set. Nodes within the same set do not form edges, they are just grouped together as a graph component.  The goal is to minimize the number of sets of nodes (single nodes will count as a set), subject to the following conditions:

$i)$ Since we are dealing with directed graphs, it is important that the topological order of the node sets is maintained, even after merging.

$ii)$ Only vertices with the same color are allowed to be in the same group.

$iii)$ We may only group two nodes $v,w$ if there's no path from $v \rightarrow w$ or $w \rightarrow v$ .

Here is a simple example to illustrate the problem:

Can this be solved efficiently?


texts: Normalizing the Central Difference Method

texts:
How could I normalize the 2nd order central difference method?
The original function is F(A,B,C,D) and only one variable is varied at a time. ie

$F'' = \frac{F(A+\Delta A,B,C,D) - 2\times F(A,B,C,D) + F(A-\Delta A,B,C,D)}{\Delta A^2}$

I want to compare the sensitivity of each variable. But I would like to do it with normalizing the second derivatives.


texts:
I am currently reading SmartCheck: Static Analysis of Ethereum Smart Contracts (Tikhomirov et al., WETSEB'18; PDF). In section 3.1 it talks briefly about synonym propagation.

What is synonym propagation?

I searched in the Dragon Book, but I did not manage to find it.


texts: How does having separate instruction and data memories help in implementing a single cycle datapath for a MIPS instruction set? I want to know why we can only use a datapath element once in a cycle for making the datapath capable of executing any instruction in a single cycle.


texts: Time complexity for calculating the $LPS$ array (failure function) in KMP algorithm preprocessing

texts:
I'm studying the Knuth Morris Pratt pattern searching algorithm from here. I want to know the order of computing the $lps$ array in this algorithm - that is the array of longest proper prefixes that are also suffix. I studied the Wikipedia page for this algorithm and it says this part is of $O(m)$ - $m$ is the length of the pattern being searched. I just don't understand why.

Can anyone help?


texts: Which algorithms provide high compression ratios for bit matrices?

texts: I have an x*y bit matrix where the total number of bits fluctuates between ~1,000,000 and ~20,000,000 bits. The rows are much smaller than the columns. An example matrix might be of size 1,000,000 x 20. The percentage of 1's in this matrix is around 15% and these 1's can occur anywhere within the matrix, with the remaining bits being 0. Which algorithm(s) would provide high compression ratios for such a matrix, if possible? This matrix is generated on a node and has to be sent to another node, with any decompression information, to allow the receiving node to fully decompress the original matrix.


texts: Is $nHALT$ undecidable even if $M$ halts on input $w$ in finite steps

texts:
If we have the language

$nHALT=\{<M,w,n>;$ $M$ halts on input $w$ in less than $n$ steps$\}$

Is this language also undecidable in the same way that $HALT$ is undecidable? And if so, $nHALT\notin P$, right?


texts: Is a relational database just a $ \geq 2$-dimensional array?

texts:
In terms of comparing data structures, is a relational database just a >1 dimensional array?  I'm just asking because I don't know much about databases, but I know a bit about data structures.

I am trying to make this clear in my mind.


texts:
I stumbled upon these two defintions of a turing machine:

http://www.cs.um.edu.mt/gordon.pace/Teaching/Complexity/CoursePage/Notes/chapter5.pdf

http://scholar.harvard.edu/files/harrylewis/files/s6_sols.pdf

The difference which bothers me is that the second one allows only left and right movements whereas the first allows left, right and not moving the head at all.

First definition:  $\delta_1: Q_1 \times \Gamma_1 \mapsto Q_1 \times \Gamma_1 \times \{L,R,S\}$

Second definition:  $\delta_2: Q_2 \times \Gamma_2 \mapsto Q_2 \times \Gamma_2 \times \{L,R\}$

Are they equivalent? If they are equivalent it should be possible to transform a TM that can do $\{L,R,S\}$ into a TM which always has to move left or right (does only $\{L,R\}$)?

How is this possible?


texts: Scheduling algorithm to minimize maximum deadline overshoot in pre-emptive scheduler

texts:
Suppose there are $n$ tasks, which need to be scheduled by a pre-emptive scheduler. Each task $T_i$ has a deadline $d_i$ and a total processing time $t_i$ associated with it. Now, all $n$ tasks are given a priory to the scheduler. The scheduler can run a task for 1 unit of time in one go. After each unit of time, it can schedule any process (including the current one) for the next 1 unit of time.

The goal of the scheduler is to minimize the maximum overshoot of its deadline by any process. For example, for tasks $T_1: (2, 2)$, $T_2: (1, 1)$ and $T_3: (4, 3)$ are the 3 tasks with their respective $(d_i, t_i)$, then a schedule of $T_2, T_1, T_3, T_1, T_3, T_3$ gives a maximum overshoot of 2. No other schedule can reduce the maximum overshoot.

My solution is to use "Earliest Deadline First Scheduling", with tie-breaks based on most time/work remaining. Further ties are broken arbitrarily. Basically, after each unit of time, the task with the earliest deadline is scheduled first. Any ties are decided on which task has the most work remaining. Further ties are broken arbitrarily. This seems to work on a few small hand-constructed cases. But I could not prove or disprove it.

To make the question more than a yes/no question, I would really appreciate it if someone could prove if this is correct, or provide a correct and efficient (sub-quadratic time) algorithm for this. This is not homework. It was presented to me by someone, and I suspect it might be a popular interview question or a question on a programming forum.


texts:
I am trying to learn how to construct an NFA state diagram.

$$M = \{q0, q1, q2\}, \{a,b\}, \delta, q0 , \{q2\}$$

$δ(q0,a) = q0; \delta(q0,b) = {q0,q1}; \delta(q1,a)= {q0, q2}; \delta(q1,b) = {q1}; \delta(q2,b) = {q1}$

From the above notation, I drew the state diagram below. Is this diagram correct?

In state $q1$ I don't understand how $a$ can transition to state $q0$ OR to state $q2$. How can the string $ba$ be accepted but also not accepted, depending on which path the NFA takes? Can you help me understand.


texts: Regular expression for a finite automaton appears to be wrong

texts:
For the following finite state machine:

The language recognized by it is given to be: $0+(10+11)(0+1)^*$ in my samples book, which I think is clearly wrong, since there's no return path to the final state.

I think the language recognized should be just an epsilon or nothing. I wanted to confirm if I am right or wrong with the answer.


texts: Is the set of Gödel numbers of computable constant functions recursively enumerable?

texts:
I've been working on the following exercise:

  $S = \{ x | f_x  \text{ is constant} \}$. Is $S$ recursively enumerable?

Here, $fx$ is the function computed by the $\text{x-th TM}$. So it is a computable function.

Intuitively, I think that to check if $S$ is constant, I would have to check if $f_x$ stops for every input. That procedure would run forever.

Important: Same thing about $\overline{S}$, if some $f_x$ is undefined for every input $y$ (it would not be constant, as far as I understand, it is constant if it has the same image for all input values) then I would not be able to list $f_x$ in an enumeration of $\overline{S}$.

In fact, suppose $\forall x,fx$ is undefined. This $f_x$ is computable - a TM can be constructed that loops forever. How can you determine that $f_x$ is not constant? There will be no input for which $f_x$ halts. Therefore, we cannot check for equality of $x_1$ and $x_2$ to determine that is not constant. Then, we can't list this $TM_x$ in the enumeration.

A solution in which this $f_x$ was put at the beginning of the enumeration was suggested. But there are infinitely many $TMs$ that are undefined for all inputs. Consequently, I can't put them at the beginning of the enumeration as other $TMs$ won't be enumerated.

I tried to reduce the Halting Problem to this problem without success. I believe that both $S$ and $\overline{S}$ are not r.e. (see my intuitive thoughts above).

How would you solve this problem?


texts: Halting Problem and Turing Degree and Reduction?

texts:
This is a Local Olympiad question on computation and computer science on 2013. How can explain it and says some hint for understanding such an example question.

  for $ A \subseteq \mathbb{N}$ we have $a=deg_T(A)=\{B | B \equiv_T A \} $ and $D=\{deg_T(A)|  A \subseteq \mathbb{N} \}$. For $(D, \leq)$
  that has $A \leq_T B$ iff $ a \leq b$. which of the following is
  false:

  1) $(D, \leq)$ is a distributive lattice

  2) $(D, \leq)$  is bounded (has minimum and maximum)

  3) $(D, \leq)$ is a half disjunctive lattice. (may be I worded this
  statement poorly, sorry)

  4) he maximum elements of $(D, \leq)$ is a degree of Halting Problem .

I think $deg_T$ means Turing Degree and $\leq_T$ means Turing Reduciblity.

Edit 1:


texts: How to convert a dependency graph to series-parallel representation?

texts:
I'm given a finite partial order, in the form of a dependency graph between items, and I'd like to have it in series-parallel form (Wikipedia).

So formally, given a finite partial order $\le$ on a set $V$, I'd like to construct it using only the following rules:

For every item $P$ in $V$, we have the partial order on $\{P\}$.
Series. If we have orders $X$ and $Y$, then we also have $X;Y$, which adds both orders such that additionally for any $x,y \in X,Y$ we have $x \le y$.
Parallel. If we have orders $X$ and $Y$, then we also have $X + Y$, which adds both orders such that any $x,y \in X,Y$ are incomparable ($x \not\le y \land y \not\le x$).

What kind of algorithm could I use to construct this SP-form?

(I'm aware that the graph is required to be "N-free" for an SP-form to exist.)

For a larger graph which is regularly updated, it would be helpful if the algorithm were incremental, but I have no idea whether that would be possible.

Examples.  Writing $P$ for the partial order on the single-element set $\{P\}$, a linear order would look like $A;B;C;...$ (all in sequence).  The "unorder", where different items are incomparable, would look like $A+B+C+...$ (all in parallel).  A binary tree could look like $A;((B;(C+D))+(E;(F+G)))$.

Background.  In a task list or issue tracking application which allows you to specify dependencies between tasks or issues, it seems helpful to present them in a series-parallel form, instead of the usual flat list which at most is topologically sorted.


texts: How is Pratt's gap sequence better than the gap sequences suggested by Shell, Hibbard, and etc.?

texts: Pratt's paper suggests that the average time complexity for his gaps are $0.315 n(\log_2 n)^2$ (gaps generated from the ascending sequence of numbers in the form $2^p3^q$). Pratt's paper claims that $\Theta(n (\log_2 n)^2$ is better than all other shell gaps, suggesting the assertion, $n^{\frac{3}{2}}=o(n (\log_{2} n)^2)$. I doubt this assertion is correct since according the their graphs, $n (\log_{2} n)^2$ upper bounds $n^{\frac{3}{2}}$. The confusion might come from the  fact that the assertion, $n^{\frac{3}{2}}=o(n (\log_{10})^2)$ is indeed true but on logarithmic base 2 it is not.


texts:
I want to show that the following problems are in NP (NP-completeness is irrelevant) by textually describing a non-deterministic Turing machine which runs in polynomial time. The assumptions are that addition, multiplication, tests for divisibility can be done in polynomial time and natural numbers are represented in binary.

a) $\{n \in \mathrm{N} \ | \ n \ $is not a prime number$\}$

b) $\{x_1, ..., x_n, y \in \mathrm{N} \ | \exists M \subseteq \{1, ..., n\} : \sum_{m \in M}x_m = y \ \}$

For a) it's clear that there must be a non-trivial divisor if $n$ isn't a prime, but how does it exactly work? How can I reject invalid and verify valid inputs?


texts:
I read this paper obout simCLR and I didn't understand a few things:

What is the goal of the temperature parameter τ? How does it affect the loss?
What will be the value of the loss for a batch with 2N identical samples? Is there a mathematical formulation?
In that case (question 2), will different temperature values change the loss?
How does the batch size affect the contrastive loss? Is large batch size better than small batch size when training a model with contrastive loss?

Thanks!


texts:
The book "Cracking the Coding Interview , 6th ed." describes the following method to sum the values of all nodes in a balanced binary search tree, and also claims that this method runs in O(n) time.

int sum(Node node) {
    if (node == null) {
        return 0;
    }
    return sum(node.left) + node.value + sum(node.right);
}

It seems to me that this method iterates through every node in the tree exactly once, plus one null reference for each leaf in the tree. I would say that n is the number of nodes in the tree, and we visit O(n+b) nodes (where b is the number of leaf nodes, is the number of null nodes traversed) and do constant work there.

How can n be an upper bound if we visit (or attempt to visit) more than n nodes? You might argue that b is constant and so we drop it, but b grows proportionally to n.

Please don't mark this as a duplicate just to get your internet points. Specific questions have specific answers.


texts: Amdahl's Law when the speedup of new component = ∞

texts:
I was doing a problem about Amdahl's Law when I noticed that $s,(local$ $ speed-up)$ was incalculable. The wording:

A computer takes 100 seconds to execute a program. The multiplication operations
take the 80% of the time. By how much we have to improve the speed of the multiplier
in such a way that the program runs 5 times faster?

So I applied the law:

$5 = \frac{1}{\frac{0.8}{Sm}+0.2}$

$\frac{0.8}{Sm}=0$

What does this mean? Am I doing something wrong?


texts: Notations for dealing with generators in algorithms

texts:
This question is about generators, which are functions that return an item from a (usually very large or infinite) set on demand, an example from Python is:
def all_natural_evens():
    n = 0

    while True:
        yield n
        n += 2

As can be seen, the above function yields the even number n in an infinite loop, in other words, it yields all positive even numbers, but since they are infinite and computer memory is finite, they generate the numbers one by one, on demand (using next(gen) to get the next number of the generator gen, where gen = all_natural_evens()).
I am using generators to build an algorithm and when writing it in Latex, I didn't know how to express this in the algorithm, for ordinary return values there is return, but with generators in Python there is yield and yield from (yield from works like an intermediary generator, it generates from a generator...clearly). Is there any notation anywhere for dealing with this kind of generators?
At the moment I'm using keywords $\text{yield}$ and $\text{yield from}$ in the algorithm's pseudocode and explaining what they do.


texts: The maximum number of nodes in a heap tree of degree d and depth k

texts:
The maximum number of nodes in a binary tree of depth k is defined by $2^{(k+1)}-1$, but the same rule doesn't appear to work for heap trees of different degrees.
Let's say I have the following tree of degree 3
   1
 / | \
2  3  4

Here the depth of the tree is 1. So according to the formula, it will be $3^{(1+1)}-1=8$. But we have 4 nodes here. I am really struggling to adapt the binary tree formula to trees of other degrees.
Any thoughts?


texts:
The hash value of a string $s$ is given by

$$
h(s) = \sum^{|s|}_{i = 1} s_i  \cdot p^{|s| - i} \mod m;  \text{ $m$  is prime, $m < 10^{12}$}.
$$

The string $s$, $p$, $m$ is given,
 $|s| \le 14$, alphabet size $= 62$ (letters and digits).

I need to
find a string $s^{\prime}$:

$s^{\prime} \neq s$, but $h(s^{\prime}) = h(s)$

$s^{\prime}$ must meet the same requirements as $s$. The answer is always exist.

I know about Birthday-attack, but $m$ is too large and
if I generate random strings, probability of collision is too small.
Simple brute-force is also not suitable, because the string may be too long (14 characters).


texts: Partitioning bag of sets such that each set in a group has a unique element

texts:
Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one element not found in any other set in that group. Formally, the criterion for a group $G = \{g_1, g_2, \dots \} \subseteq S$ is:

$$\forall i: \left(g_i \setminus \bigcup_{j\neq i} g_j\;\neq\;\emptyset\right) $$

The partition $P = \{\{s_1\}, \{s_2\}, \dots\}$ always satisfies this requirement, so there is always a valid solution. But what is the smallest number of groups needed? Is this problem feasible or NP-complete?

Another formulation of this problem is to partition a multiset of integers into groups such that each integer has a bit set in its binary expansion that no other integer in its group has set.


texts: What is the Big O estimate of a nested for loop?

texts:
I am trying to figure out what the big o estimate of the following for loop is.

for(int i = 10; i to 100; i++){
for(int j = 1; j to i; j++){
for(int k = 1; k to j; k++){
s=s+i+j;
}
}
}

I was thinking that the two inner loops run n times but I am unsure about the first loop.

What would the Big O estimate be for this code?


texts: Booth's algorithm Question : Binary Number Arithmetic (Multiplication)

texts:
It's being said booth's algorithm produces the output exactly as normal binary multiplication while reducing the number of operations performed and can be used for both positive and negative numbers !
I tried multiplying two 4-bit numbers while I don't get the same result...Please guide what am doing wrong.
Multiplicand : 1101 ,
Multiplier : 1110,
Recorded Multiplier(Applying skipping over 1's) : 00-10

The Result's are different Please Help !


texts:
Motivation

Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into solving the problem but I'm still unsatisfied with my solution.

Problem formulation

You are given a list of unique sets $X_1,\dots,X_n$, each containing four integers.  You are also given an integer $k$.  The goal is to partition the sets into $k$ groups, so that every group has between $0.8n/k$ and $1.2n/k$ sets, in a way that minimizes the number of different integers in each group.  Formally, the goal is to find a function $f:\{1,\dots,n\} \to \{1,\dots,k\}$ that minimizes

$$\Phi(f) = \sum_j \left|\bigcup_{i \in f^{-1}(j)} X_i\right|.$$

Example

If instead of sets of four integers we considered sets of two integers, we could give the following example: for the sets

{1, 2}, {2, 3}, {1, 3}, {3, 4}, {4, 5}, {3, 5}

the optimal partitioning for $k=2$ would be {1, 2}, {2, 3}, {1, 3} and {3, 4}, {4, 5}, {3, 5} with unique elements $|\{1, 2, 3\}|=3$, $|\{3, 4, 5\}|=3$ and $\Phi = 6$.

My attempts so far

So far I've attempted to solve this problem by modeling it as a graph partitioning problem and using KaHIP library to do the computation. I thought of two methods of how to model this problem as a graph.

Each set is a vertex, and we have an edge between two vertices if they share an integer. The number of shared integers determines the weight of the edge. The graph partitioning tool then directly yields some solution to our problem.
Each unique integer that occurs in any set is a vertex, and we put an edge between two integers if they are both contained in the same set. The number of such cases determines the weight of the edge. Having the integers partitioned like this we can assign each set a partition of some of its integers. Resulting partitions can be too large, but that can be resolved by applying the first approach to these now relatively small partitions.

The first model in my case turned out to be very space-consuming. I have approximately 2 millions of these sets and the first model produced over 74M edges. The second approach helps a great deal and yields results of similar quality.

The problem is that neither of these models is the exact model of my original problem. Notably, the number of cut edges will not correspond with the number of duplicated integers across partitions. Can you think of a better graph model or an altogether different approach to this problem that would yield better results?


texts: Gas Station problem : Fixed path variation

texts: Given a set of cities where you need a certain amount of fuel to travel from one city to another, each city has a different fuel price and you can only load K amount of fuel to the vehicle. The path is fixed (ie) you have to go from C1 to Cn through C2, C3,.. and so on. The objective is to fill fuel in these cities in such a way the spendings on fuel is minimized. I thought about storing the minimum prices within a window whose requirements add up to K and then find the minimum cost required to traverse. I'm not sure how it holds up or is it even right in the first place. What if being greedy and filling up fuel to reach the city empty till you reach the closest city with cheaper fuel, not the optimal solution? How do i prove that it is?


texts: Proving that $A=\{w_{2i}|w_{2i}\not\in L(M_i)\}$ is not Turing-recognizable

texts:
In this problem, $w_{2i}$ is the $2i$th string in the lexicographic order of binary strings and $M_i$ is the TM whose binary code is $w_i$.
We are given the diagonalization language $A_D=\{w_i \mid w_i \notin L(M_i)\}$. We know $A_D$ is not Turing Recognizable.

Basically, $w_i$ is the $i$th string in the following lexicographic ordering:
$\epsilon, 0, 1, 00, 01, 10, 11, ...$

The proof for $A_D$ is the following: Suppose by contradiction, there is a TM $M$ such that $A_D = L(M)$. Then $M=M_i$ with code $w_i$ for some $i$. $w_i \in A_D$ iff $w_i \notin L(M_i)$ by definition of $A_D$. $w_i \in A_D$ iff $w_i \in L(M_i)$ by $A_D = L(M_i)$. A contradiction.

The problem is I don't understand the proof above. Therefore, I have no idea how to approach the topic question. It would be very helpful if someone can give a brief explanation of how $A_D$ proof works and what approach I can take to prove $A$ is not Turing recognizable. For instance, is it possible to reduce $A_D$ to $A$? Or is it better to follow the same proof format as $A_D$?


texts: What type of operations are seen the most at the physical disk level — reads or writes? Why?

texts:
This question came up in my operating systems class in a section about file system cache and RAID.

I'm speculating that the answer is that writes are seen more at the physical disk level because an efficient cache reduces the need to read from the disk.

Can someone confirm or correct this?


texts: Why can't we search lexicographicaly ordered programs to compute Kolmogrov complexity?

texts: Kolmogrov complexity is known to be uncomputable.  Why can't we enumerate all programs of size i = 0 in lexicographical order - if any produce string s, that is the Kolmogrov complexity; if not, increment i and iterate? Won't that prove that no program of length < i generates string s?


texts:
For any language $A$, define a language $L_{A}$ as:

$L_{A} = \{0^{n}: \text{Number of strings in $A$ of length $n$ is more than $2^{n-1}$} \}$

I am trying to construct an $A$ such that $L_{A} \notin P^{A}$. It should intuitively be true, as a polynomial time machine cannot query an exponential number of strings and check whether a majority of them belongs to a language.

The proof boils down to a diagonalization argument. But I am unsure on how to construct the sets.


texts: Problems understanding proof of smn theorem using Church-Turing thesis

texts:
I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem:

Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a computable function $g(x)$ such that $f(x,y) = \Phi_{g(x)}(y)$ for all $x,y \in \mathbb{N}$. Here, $\Phi_n$ refers to the $n$th recursive function.

The proof goes like this:

For a fixed $x_0$, the function $h_{x_0}(y) = f(x,y)$ is computable (this I agree with) and so we there exists an index $e_{x_0}$ so that $h_{x_0} = \Phi_{e_{x_0}}$ (this I also agree with).

So, the function $g$ that to each natural $x$ assigns such index $e_x$ (so that $h_x = \Phi_{g(x)}$) is computable (this is the part I don't understand).

When saying that $g$ is computable it means that we can describe an algorithm that takes $x$ as an input and will output the desired $g(x)$. I don't see how such algorithm can be described. (I guess my confusion has to do with the "there exists an" that I placed in bold letters.)

If it helps, we are using Godel numberings of Turing Machines to index the recursive functions.


texts: Is there an O(logN) optimal weight balanced binary search tree where weights/sizes of left and right subtree differ at most by 1?

texts:
I am wondering if there is a log time WBT (weight balanced binary search tree) data structure in which for any node, the sizes of its left and right subtrees diff at most by 1.

PS: I have read through Balancing weight-balanced trees but the weights of subtrees can differ up to a factor of $\Delta$.


texts: On graph isomorphism over exponential word sizes

texts:
Is it known Graph isomorphism can be done in poly time if we allow exponential word sizes?

(Shamir's poly time Integer Factoring algorithm is over exponential word sizes).


texts: Simplification of a multi-index Boolean expression towards computation in fewer steps

texts:
Let $x_{ij} \in \{0,1\}$, $1 \leq i \leq M$ (typically, $M = 2000$), $1 \leq j \leq  N$ (typically, $N = 10$), be Boolean variables. If possible at all, I would like to simplify the following expression
$$
\bigvee_{i_1,\dots,i_N} \left(\bigwedge_{k=1}^N x_{i_k k} \right),
$$
where the join operation is taken over all indices $(i_1,\dots,i_N) \in \{1,\dots,M \}^N$, so that it can be computed faster instead of looping through all multi-indices.

Apologies if this is a well-known problem (with or without solution). This is very much outside of my field of expertise, so I am hoping someone around here could give some feedback on it. Feel free to edit the tags as you see more appropriate.

Thanks!


texts:
A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children.
I have been trying to prove that its height is O(logn) unsuccessfully.
Here is my work so far:

I am considering the worst case of a full binary tree in which each right node has a subtree, and each left node is a leaf.
In this case:
$N = 2x - 1$
$H = x - 1$
I am going nowhere trying to prove that $H = O(\log(N))$

Furthermore, we know that leaves l is bounded by $h+1 <l<2^h$.
Internal nodes is bounded by $h<i<2^{h-1}$.
All this proves is that number of nodes $n=i+e$ is $<= 2^{h+1} - 1$ i.e. $\log(n) <= h$. But this does not take me anywhere closer to prove that $H = O(\log(n))$


texts: In compiler design, why should left recursion be eliminated in grammars? I am reading that it is because it can cause an infinite recursion, but is it not true for a right recursive grammar as well?


texts: How internet speed is manipulated at the physical level

texts:
Although I am a computer science major, I am having a hard time understanding how internet providers have control over internet speed (example: offer different speeds to different customers, one with a higher price, etc.).

And I mean how is it that they do it at the physical level or bit level if I may. I think that they might have some tool that let more bits flow through a certain pipe or something like that. I would appreciate if someone could answer my question or ask me any clarification about my inquiry if it's not clear.


texts: What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$?

texts: If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(n)\subseteq DTIME(O(f(n)))$?


texts:
everyone! I don't know a whole lot about the fields of encryption or quantum computing, but I've read a lot of articles on the subjects and that is prescisley what caused this question. I've been a little scared about the whole NSA quantum computer that is build for the sole purpose of cracking encryption codes. I am fairly certain that they wouldn't use that power to get into random civilians' information, but if they did how hard would it be to block them out?

According to the numbers I've seen this computer could crack a typical encryption code within a little more than a week. And I recall seeing that a typical encryption key used in a consumer application is either 64 or 128 bits (or bytes?) long. I'm sorry if I'm getting these numbers wrong. Now, a week is an awful long time to to wait to crack a code (but wickedly better than with conventional computers), so they wouldn't waste their time on the password hash for your Facebook account. But say they did, wouldn't it be easy to overwhelm that system? According to mathematics the total number of time it would take to break the code would double with every bit longer the code is, and multiply by 256 with every byte. So, assuming a computer that could crack a 64bit code in up to a week, it would take 3.54^17 years to crack a 128 bit one.

Is this true? And if it is, then wouldn't this make the NSA computer useless? Because anyone that the angency would want to hack into could simply just increase the length of their encryption keys.

Thanks for any insight on the matter, and sorry if I have my facts wrong.


texts: Why the pointer in linked list is of structure type?

texts: Since any node points to a memory location is there any specific need in using it's pointer as structure type.Why couldn't we use integer as the pointer type in linked list rather than structure?


texts: Standard training and test corpuses for POS tagging

texts: I'm wondering if there is a standard corpus that people use to evaluate their part-of-speech taggers.  I am implementing my own tagger, and would like a meaningful way to measure its performance, which would ideally be against the same corpuses that other people are using.


texts: Easy instances of the coloring problem on graphs with degree at most 4

texts:
Given a graph with some set of colors, the goal of the coloring problem is to color the input graph with as few number of colors as possible, such that no adjacent vertices have the same color.

In general, the problem is hard. For trees and cycles, the problem is solvable in polynomial time. I am interested in bounded degree instances or more precisely graphs of degree at most 4. Is there any non-trivial subclass of graphs of degree at most 4 for which the coloring problem is solvable in polynomial time?


texts: Where did Don Knuth say that suffix trees were the "Algorithm of the Year 1973?"

texts:
If you do a quick search for suffix trees on Google, you'll find a bunch of sources saying that Don Knuth called them the "Algorithm of the Year 1973." However, I can't seem to find a source on this.

Is there a reference to a paper, communication, etc. where Knuth specifically says this about suffix trees?


texts:
Possible Duplicate:
  Is this language Context-Free?

The language is defined by
$$(a+b)^*-\{(a^nb^n)^n\mid n \geq1 \}$$

is Context-Free Language? I believe that the answer is that it is not a CFL's, but I can't prove it by Ogden lemma or pumping lemma.

chazisop, (a+b)* means {a,b}*. That's all strings that you can form with the symbols a or b or both.


texts: What does actually reasonable mean when we say "reasonable model of computation"?

texts: I have seen in many text when the author says "reasonable model of computation". What does it really mean?


texts: Is there a mapping reduction of E(tm) to OVERLAP(tm)?

texts:
$E_{TM}=$ { < $M$> $|$ $M$ is a TM; $L(M)$=$\varnothing$}

Where $L(M)$ is the language accepted(recognized) by $M$.

$OVERLAP_{TM}=$ {< $M_{1}$,$M_{2}$> $|$ $M_{1}$,$M_{2}$ are TMs;  $L(M_{1})\cap L(M_{2}) \ne \varnothing$}

Is there a mapping reduction of $E_{TM}$ to $OVERLAP_{TM}$ ?


texts: Problem with solving the recurrence $T(n) = 2T(\sqrt n) + \log n$

texts:
This question has already been asked before in this site, but the details of none of them is my question and none of them answer my question.
The following is an example recurrence given in introduction to algorithms book by CLRS .

$$T(n) = 2T(\sqrt n) + \log n$$

It is solved by changing the variables. It renames the $m = \log n$ and it yields

$$T(2^m) = 2T(2^{m/2}) + m$$

and it renames $S(m) = T(2^m)$, so it produces new recurrence

$$
S(m) = 2S(m/2) + m
$$

which is easy to solve.

I have two problems with this solution:

1- renaming $S(m) = T(2^m)$ must yield  $S(m) = S(m/2) + \log m$, since we can't change the argument of the $T$ and leave the $m$ as it was. We can use $S(m) = S(m/2) + m$ only if the original recurrence was $T(2^m) = 2T(2^{m/2}) + 2^m$

2- The second problem is, even if the above renaming is true, $2T(\dfrac{2^m}{2})$ would be $S(m/2)$ not the $2T(2^{m/2})$

thanks in advance.


texts: Would it be possible that the intersection of two non-context-free languages is context-free?

texts:
Assume two languages $L_1$ and $L_2$, both of which are non-context-free.

Let $L = L_1 \cap L_2$. Could $L$ be context-free?


texts: Need introductory guide to cellular automata for geographic automata systems

texts:
I would like to work on urbanisation and I've read that cellular automata has potential use on model urban sprawl. However I need some kind of introductory to cellular automata in order to tackle an academic paper I have found.

I have a fair background in Computer Science. Moreover I am looking for any tools from CS applied to cities.


texts: Obtaining a graph with no cycles after removing k edges

texts:
I am looking for an algorithm that upon an input of a directed graph G and a natural number k,outputs a set of k edges, that upon removing them, the graph will have no cycles. If there are no such k edges, it outputs "not found"

The algorithm cannot use any algorithms for NP-Complete problems - except for the one deciding if it belongs to acyclic. Its running time must be polynomial in regards to its input.

My attempt: to decide if a directed graph is acyclic, we can look for a vertex that has no incoming edges - if no such vertex to be found, it contains cycles. Upon finding such vertex, using a stack, traverse using dfs and add edges, if one vertex is found twice - than the graph contains cycles, otherwise - the graph contains no cycles.

I don't know how to design an algorithm that upon getting a directed graph G and a natural number k, outputs the set of k edges, that without them the graph will have no cycles.

It would help me a lot if you could write the algorithm in "turing machine notion"(computation/complexity) as I am trying to learn to use it properly and seeing how to do so correctly would help a lot.

Acyclic language is the language that contains all acyclic directed graphs

Thank you very much for helping me.