texts: How often should I read out information from an echo state recurrent neural network?

texts:
Recurrent neural networks makes it possible to implement some kind of memory, which can be very useful for a lot of tasks, incl. (but not limited to) robot control, which I am interested in. For example, echo state networks are known to display some kind of dynamical short-term memory, and display a very small search space wrt alternatives.

Of course, recurrent neural networks are not so simple to use in practical: the search space can grow really fast (e.g. with fully connected networks), forgetting can be catastrophic, etc.

One particular question is: how often should one "read out" the information from a recurrent neural network?

On the one hand, it is very likely that any new input values' influence will be limited when reading out (ie. using) output values at every time steps (ie. no time for operations requiring several iterations to deal with the new inputs).

On the other hand, one can choose to read out outputs values once every N iterations of the neural networks, but there is a risk of forgetting the relevant information if N is too big. Of course, there may exist better guess for N. For example, setting N to be sure that any new input values can travel throughout the shortest path from input to output neurons, but then you may loose partly the benefit of recurrence for this particular input values (e.g. integrate).

In practical, and to the extent of my knowledge, setting N is mostly done by lucky guessing or empirically, through multiple trials.

So my question is: is there an automated way to choose N more wisely, whether there is a magical formula (I'm skeptic) or a methodology to estimate the value of N from data or from observing the reservoir? (e.g. computing some kind of derivative from the reservoir to guess if it is too large or to little).


texts: Is this problem $\mathsf{NEXP}$-complete?

texts:
I have found this challenge and now I'm interested how hard it is being generalized.

It can be reformulated like this:

Given numbers $N,k$ find a if there exists string of directions (W,E,N,S) that will reach every reachable cell on every $N\times N$ grid from any position of length at most $k$.

We only need to find a string that will pass all $N^2$ cells from any position on following grids:

Number of walls is $(N-1)^2$.
Every cell is reachable.

It appears that number of such grids is exponential on $N$. So, the solution can be checked in 2-exponential time. Hm, for $2\times 2$ there only are 4 such grids,for $3\times 3$ there are 189 such grids. Perhaps, this problem is even harder.

But is this problem $\mathsf{NEXP}$-complete? If so, this would be one of the most natural $\mathsf{NEXP}$-complete problems.

Of course it is possible that shortest string can be expressed using some formula. Since I suspect that this string depends at most exponentially on $N$, it would be in $\mathsf{EXP}$.


texts: Runtime of various versions of binary search

texts:
I was given the following code and was told to find the best and worst case running times in big theta notation. (Below is in python)

def find(a, target):
    x = 0
    y = len(a)
    while x < y:
        m = (x+y)/2
        if a[m] < target:
            x = m+1
        elif a[m] > target:
            y = m
        else:
            return m
    return -1

I know that the running time of this code in the worst case is $O(\lg n)$. But the question I was given if the fifth line was changed from $m = \frac{x+y}{2}$ to $m=\frac{2x+y}{3}$, would the running time change?

My intuition is that the running time gets a little larger as it is no longer cutting the list in half like binary search should do which is less efficient, but I am not sure how to calculate what the asymptotic runtime would be at this point.


texts: Is this correct in term of big-oh notation: given $g = O(f)$ and $h = O(f)$ can we say $g = O(h)$?

texts:
We have two equations $g = O(f)$ and $h = O(f)$ , then can we derive that $g = O(h)$.
I came up with following proof but i dont know it's correct or not.
$$g = O(f)$$
$$g \le c_1*f $$
$$h \le c_2*f $$

Now we have to prove,
$$g = O(h)$$
$$g \le c_3*h$$
$$g \le c_3*c_2*f  $$
$$ c1 \le c3*c2 $$
We can find $c_3$ such that last equation $ c1 \le c3*c2 $ will be true.

  Is this correct or not? If not what will be correct proof for this?


texts: DFA that accepts strings with last character being repeated at least 1 time before

texts:
I'm trying to design a DFA in a 4 digit language, for example L(a,b,c,d) or L(1,2,3,4) that accepts strings with the last character being already repeated before.

Everyway im trying, i get so many transitions im literally lost in them...

So, for example, abbdb is accepted (because b is showed again at least 1 time) but abc is rejected since c (last char) never shows up more than 1 time.

I managed to make it work for a language with 2 DIGIT:
For example:

Which accepts for example aa or ababa but can't do for 4 DIGIT language.


texts: Permutation of words that have matched parentheses

texts:
Let $L$ denote the (context-free) language of matched parentheses over the alphabet $\Sigma$.  Consider the following problem:

Input: words $x_1,\dots,x_n \in \Sigma^*$
Question: does there exist a permutation $\sigma$ of $\{1,\dots,n\}$ such that $x_{\sigma(1)} x_{\sigma(2)} \cdots x_{\sigma(n)} \in L$?

What is the complexity of this problem?  Can it be solved in polynomial time?  Is it NP-hard?

It "smells" like something that might be NP-hard.  But perhaps there is a way to reduce this to the route inspection problem (which has a polynomial-time algorithm),  perhaps by treating each $x_i$ as an edge in some graph, or something?

Motivation: This is inspired by a question about permutations of lines of code, but my main interest is just curiousity.

Related:

Time complexity of a problem inspired by palindromes claims to show that the problem is NP-hard when $L$ is the language of palindromes, a different context-free language (though I don't understand the proof).
Word tiling, where you must use each tile exactly once considers the problem where $L=\{y\}$ where $y \in \Sigma^*$ is a single word specified as part of the input, and the answers show this is NP-hard too.


texts:
How many satisfying assignments does the following formula have?

(x1 ∨ x¯2 ∨ x¯3)(x1 ∨ x2)(x¯1 ∨ x¯2)


texts: Pathfinding when the graph varies over time

texts:
Let's say I want to simulate a very large number of travelers booking flights. For example, a traveler might want to fly from New York to New Delhi. There's no direct flight from New York to New Delhi, but there's a flight from New York to London, and from London to New Delhi, so our traveler books those two flights. Each traveler is looking for the route with the lowest cost (where cost is some function of travel time, total fares, and various other factors; this function may vary depending on the traveler). A simple pathfinding problem so far.

But the actual problem is a little messier than that. There might be a flight from London to New Delhi on Friday, but not on Saturday. So it won't do any good to arrive in London after the last plane for New Delhi for the week has already left. It's as if the graph changes with every step, because time passes with each step and the available flights change with time. (However, we're planning out the whole trip in advance; no time is actually passing during the pathfinding process.)

I can think of ways to compensate for this. For example, I could use A* with a graph where, rather than each node being a city, it could be a city and a time, so that London on Friday and London on Saturday are considered separate nodes. However, I'm not sure this is the best way. Since I'm simulating a very large number of travelers, I need this algorithm to be as fast as it can possibly be, so long as memory usage is reasonable. What literature exists on this subject?


texts: Does $E_{TM}$ accpets the empty word $\varepsilon$?

texts:
Let $L = E_{TM} = \left\{  \left<M \right> | M \text{ is a TM and L(M)} = \emptyset   \right\}$.

Does $L$ accepts the empty word $\varepsilon$?

In other words, is $$\varepsilon \in L$$

I'm a little bit confused by this.

My intuition says it doesn't since the empty set rejects every input.


texts: How to characterize equivalence classes induced by Myhill-Nerode theorem?

texts:
Given $L=\lbrace w\in \lbrace 0,1 \rbrace^\ast : N_0(w)=N_1(w) \rbrace$,  where $N_0(\cdot)$ and $N_1(\cdot)$ mean the number of zeroes and ones respectively, I need to characterize the classes induced by the relation on $\{0,1\}^\ast$ $$x \thicksim_{L} y \iff \forall z\in \{0,1\}^\ast \left(xz \in L \iff yz \in L\right)$$
The reference I have already shows that the (obviously, infinitely many) classes are of the form $C_k=\lbrace w\in \lbrace 0,1 \rbrace ^{\ast} : N_0(w)-N_1(w)=k  \rbrace $ and clearly $\bigcup_{k\in\Bbb Z } C_k = \{0,1\}^\ast $, but I have no idea how could I have deduced this correct characterization myself.

When given a regular language, I find it easier to construct a suitable minimal DFA and then "back engineer" each state to a useful characterization of its class. But for a non-regular language, I'm having a really hard time working with the relation definition. In this particular example, I don't understand how it applies to the classes $C_k$ above.

So for me there are two underlying questions here:

If given the equivalence classes, how can one prove that they are indeed induced from the relation?
However, if they are not given, is there a systematic\algorithmic approach to characterize all of these classes for a given language? mainly, a non-regular one.


texts: how to solve NFA acceptance problem in polynomial time

texts:
I need to show that the language Anfa = {(A,w)| A is an nondeterministic finite automata that accepts w} can be decided in polynomial time. My problem is every solution that I think of requires exponential time.

I would appreciate any help, Thanks in advance..


texts: Is there an algorithm that provides the highest possible "sum of satisfaction" for a priority based distribution problem?

texts:
Let's say we have n (e.g. 6) children and a box of candy. The box has k (e.g. 8) different flavours, and m (e.g. 4) piece of candy in each flavour. This question is specifically about the cases where k > n and n > m.

We can assume a maximum of a 1 piece of a flavour per person.

We ask them to make a list of the flavours from most liked to least liked, so we know the preferences of each child.

We of course want the "sum of satisfaction" to be the highest possible.

Is there an algorithm that is able to give the perfect distribution, or one that's quite close?


texts:
I'm trying to get a better understanding for the relationship between decidability and a few other things so that I can get a better grasp of the topic. Any info helps!

Is every decidable language a deterministic context free language?
Are there any decidable languages that are not recognizable?
Is the question "Does a given PDA accept a given input?" decidable?
Under what operations are decidable languages not closed?


texts:
Given 2 polygons in a plane:

$A : ( (xa_1,ya_1), (xa_2,ya_2), ... (xa_n,ya_n) )$

$B : ( (xb_1,yb_1), (xb_2,yb_2), ... (xb_m,yb_m) )$

Is there a polynomial algorithm to compute a matching $M$ between the points in A and B, such that:

If $(xa_i,ya_i)$ is matched to $(xb_p,yb_p)$ and $(xa_k,ya_k)$ is matched to $(xb_r,yb_r)$, then for $i<j<k$ and $p<q<r$, $(xa_j,ya_j)$ is matched to $(xb_q,yb_q)$.
For $M:\{(i_1,j_1),(i_2,j_2)...\}$ and $|M|=min(n,m)$, $\Sigma_{k=1}^{|M|} distance((xa_{i_k},ya_{i_k}),(xb_{j_k},yb_{j_k}))$ is minimized.


texts:
I'm trying to change below context free grammar such that it becomes unambiguous, but I don't know what steps I should take. Is there any specific way of doing that?

Here is my CFG:
\begin{align}
&S \to SS \mid T \\
&T \to aTb \mid ab
\end{align}


texts: A plane-sweep algorithm for a points in triangles inclusion problem

texts:
I was given the following homework assignment:

Consider a set of $p$ points and $t$ triangles in the plane. The triangles are pairwise disjoint, that is, their edges do not intersect, no triangle lies in the interior of another, and no edge/vertex is part of more than one triangle. The points are in general position with respect to the triangles, that is,
no point lies on a vertex or an edge of a triangle. The triangles are given by the coordinates of their vertices, and also the points are given by their coordinates. All points and vertices have pairwise different coordinates. (See below for an example.)

The task is to determine for each of the $p$ points whether it lies inside a triangle, and if yes in which. Design an efficient algorithm for solving this task. Explain your solution in detail, show its correctness, and analyze its runtime and memory requirements.

I've coem up with the following algorithm, that closely resembles the Bentley–Ottmann algorithm for the intersection of line segments. The idea is to sweep the plane from left to right analogousely to it. The main point is the observation that a point p lies in a triangle iff $p$ lies $x$-wise between the triangle starting - and triangle endpoint as well as $y$-wise between the intersection points of the sweep line with the triangle sides. (For an illustration see below.)

SET-UP: Let $X$ be a priority in which we store the $x$-coordinates of the points of $P$ and $T$. Let further $Y$ be a Red-Black-Tree in which we store the $y$-coordinate-wise sorted list of triangle edges. At last let $T$ be the set of triangle points and $P$ be the set of the remaining points.

ALGORITHM:

1) $X := 0, Y := 0$

2) Insert the $x$-coordinates of all points of $P$ and $T$.

3) while $x \neq \emptyset$ do

Find the minimum $m$ of $X$ and delete it from $X$.
If $m$ is a triangle starting point then insert the incident edges into $Y$.
If $m$ is a triangle middle point then delete the incident edge to the left
of $m$ and insert the incident edge to the right of $m$ into $Y$.
If $m$ is a triangle end point then delete both incident edges from $Y$.
If $m$ is a point out of $P$ then do for all pairs of adjacent edges in $Y$:

Calculate the intersection points of the sweep line L with the
current pair of adjacent edges.
Check wether the $y$-coordinate of $m$ lies between the $y$-
coordinates of said intersection points. If it does the point
$m$ is in the respective triangle. Report $m$ and said
triangle.

I think that this algorithm should have $\mathcal{O}((p+t)*log(p+t))$ running time, but I don't know how to argue that in a more formal manner with the characteristic of Red-Black-Trees and so on. Could you help me with that?

Illustration 1
Illustration 2
Illustration 3

SOURCES:

http://www.ist.tugraz.at/_attach/Publish/Eaa17/assignment_06.pdf


texts:
I came across this question about NFA-e and thought to convert it into DFA:

This is what I did.

$\begin{array}{|c|c|}
\hline
& a \\ \hline
 q_1&q_2 \\ \hline
 q_2&\phi \\ \hline
 q_3&\phi  \\ \hline
\end{array}$

Found epsilon closure of states:

$\varepsilon(q_1) = q_1$

$\varepsilon(q_2) = [q_2, q_3, q_1] = P$ (let)

$\varepsilon(q_3) = [q_3, q_1] = Q$ (let)

Defined new transition rule for the states:

$\delta'(q_1, a) = \varepsilon\{\delta(q_1, a)\} = \varepsilon(q_2) = P$

$\delta'(P, a) = \varepsilon\{\delta(q_2, a) \cup\delta(q_3, a) \cup \delta(q_1,a)\}=\varepsilon\{\phi\ \cup\ \phi\ \cup q_2\}=P$

$\delta'(Q,a)=\varepsilon\{\delta(q_3,a) \cup \delta(q_1,a)\}=\varepsilon\{\phi \cup q_2\}=P$

$\begin{array}{|r|r|}
\hline
&a\\\hline
q_1&P\\\hline
*P&P\\\hline
Q&P\\\hline
\end{array}$

Now I'm stuck on how to make the FSM. There is no transition to $Q$ from $q_1$ or $P$. What did I do wrong?


texts: How is reachability reduced to order maintenance?

texts:
After reading Dimitris Andreou's blog post on reachability, it seems that reachability can be reduced to order-maintenance. A solution to the order-maintenance problem has the following interface:

Insert (X, Y ): Insert a new element Y immediately after element X in the
total order.
Delete (X): Remove an element X from the total order.
Order (X, Y ): Determine whether X precedes Y in the total order.

The reachability problem is easily solved by just calling Order(X, Y) to check if Y is reachable from X, but I'm not sure how this works with non-tree DAGs. For example, what if you have a graph like this (from the Multiple inheritance diamond problem):

and you'd like to answer queries like: "Does D inherit from A?" (is A reachable from D). You'd have to call Insert(D, B), Insert(D, C), Insert(B, A), Insert(C, A), and then Order(D, A). However, AFAIK, the Insert(X, Y) method can only be called if Y does not already exist, so this wouldn't work with vertex A.

How can you solve reachability for non-tree DAGs using order-maintenance?


texts: Are the No Free Lunch theorems useful for anything?

texts:
I have been thinking about the No Free Lunch (NFL) theorems lately, and I have a question which probably every one who has ever thought of the NFL theorems has also had. I am asking this question here, because I have not found a good discussion of it anywhere else.

The NFL theorems are very interesting theoretical results which do not hold in most practical circumstances, because a key assumption of the NFL theorems is rather strong. This assumption is, roughly speaking, that the performance of an algorithm is averaged over all problem instances drawn from a uniform probability distribution. In realistic applications the problems an algorithm typically encounters are NOT drawn from a uniform distribution, and are instead drawn from what is likely a very interesting and complicated distribution specific to the general problem setting.

So, while the NFL theorems are quite interesting results, do they have any practical implications? Or are they merely theoretical results?

EDIT: By practical implications, I mean novel or improvements over existing algorithms, improved hyper-parameter selection, and things of that nature. I would even be interested to learn of NFL-inspired theorems that do apply to realistic search/optimization/learning problems.


texts:
I know how to prove that CFL are closed under kleene star operation using CFG.
I can't find online or in class notes a proof using PDA.
I would appreciate description of the basic idea (not formal).


texts:
I'm looking for an existing algorithm that would ensure that the first k elements after sorting are the top k elements but not necessarily in the right order.
To put it differently, I would like an algorithm that acts like C++ std::partial_sort but takes advantage of the fact that I don't need the first elements ordered.
If there's no such thing yet, I'm planning on studying again existing algorithms and try to find out which one would be the best candidate to tweak. Any lead would be welcome.


texts: Can we simulate any dependent datatype with `Eq`?

texts:
Consider the canonical homogeneous equality type: Eq : (A : Set) -> A -> A -> Set, with constructor refl : (A : Set) -> (z : A) -> Eq A z z.

I could swear I remember reading somewhere that the equality type was essential in some sense: all other datatypes could be built using it. This would be very useful for dealing with simple dependent type languages, where we don't want to have arbitrary datatypes in our metatheory.

Can someone who knows the field confirm/deny this, or possibly provide a reference?


texts: Can PDA model Turing Complete objects if the objects' state are finite?

texts:
I am currently reading the extended Version of the Paper Online Detection of Effectively Callback Free Objects with Applications of Smart Contract.

I am trying to understand the proofs of Chapter 6.
In particular, I cannot understand the premise of proofs 6.2. Indeed, the authors use a variant of SMAC, an Object-oriented and Turing Complete (SMAC) and they claim that (I underlined the suspicious claim with bold)

  Thus, we focus on verifying $sECF$, namely, statically verifying whether all executions of an object are $dECF_{FS}$ or $ECF_{C}$, where the domains of the object variables are restricted to finite sets. Hence, such objects can be modeled with a pushdown-automaton (PDA). Such a PDA for an object o is
  able to simulate any modular well-formed execution $\kappa \in \pi$
  where the active object of all states in $\pi$ is o.

In my understanding, this premise should be wrong, because although the state of this SMAC program is final, it is not computable by Push-Down-Automata (which compute total functions).

Foo:
     int x = 0 // field of the object
     enter // enter the single method of the object/contract
         while true do
             x = 1
     return


texts: It is pretty obvious that $DTime(n^3) \subseteq PSpace$, since $DTime(n^3) \subseteq DSpace(n^3) \subseteq PSpace$, but I fail to see how to find such a language $L$ so that $L\in PSpace\,\,\,$  yet $\,\,L\notin DTime(n^3) $. Can someone assist with an idea of how to find such $L$?


texts:
def f(n):
 i = 2
 while i < n:
  print(i)
  i = i * i

I evaluated an expression that becomes something like 2^n or 2^2^n and set that equal to when the loop breaks or (2^2^n ) (>=)n    but can't figure out how to get a runtime. Can someone show how to do complete this analysis and get a runtime?


texts: Computing FOLLOW sets for LL(1) grammar. Stuck on question

texts:
Calculate the FOLLOW sets for all the non terminals:

  $S \rightarrow bEx \mid Db \mid b \mid F$

  $D \rightarrow EDc \mid Y$

  $E \rightarrow dED \mid dDY$

  $Y \rightarrow ab \mid aDx \mid \varepsilon$

So I know that:

FOLLOW($S$) = $\{\$\}$ since it doesn't appear anywhere

FOLLOW($D$) = $\{b, a, x, c\}$, since it is followed by terminal $b$ in $S$, $c$ in $D$, FIRST($Y$) in $E$ which is $\{a\}$ ($\varepsilon$ not included), and $x$ in $Y$

FOLLOW($E$) = $\{x, c, a, d\}$, since it is followed by terminal $x$ in $S$, FIRST($D$) in $D$ which is $\{a, d, c\}$

but how do I calculate FOLLOW($Y$)? It isn't followed by anything. I'm guessing since it's at the end of $D$ and $E$ its the union of their follow sets including $\$$ since there's an $\varepsilon$?

Have been stuck on this for a while, any help is HIGHLY appreciated. Thanks in advance for any input


texts: Good AI model for learning to write code, specifically generate css from any given html?

texts:
Currently I am working on getting lots of html code and its related css, via id or class name. Once I have enough data to work with I am unsure how it would be easiest for any model to learn what css should be generated for each element.

My idea is to make a script to extract all html elements from a given file and then map it onto the css code as a possible good output for the model to learn.

For example : script extracts element h1 with class name "title" and then it maps onto its css code, something simple such as

title{
 color:blue;
 text-align: center;
 font-size: 40px;
}

The catch is that the model should also consider the rest of the elements found on that page, likely given in an array of detected elements and then output an array of css as above for each element. My hope here is that it would learn to style entire pages rather than single elements on their own.

Another issue is what to do with the css code itself, wether to try and make the model choose between pre-set options for each element or let it learn the language and its format from scratch.

I am not sure what model would be best to deal with this kind of input and output. Currently my strongest consideration is LSTM.


texts: If algorithm runs $\theta(n)$ in time T, doubling input size has what effect on time T?

texts: In other words, is there a relationship between the step size and the actual running time? Suppose that the algorithm is run on identical machine.


texts: Does Automatic Differentiation handle conditional branches, if yes how?

texts:
I'm trying to understand how Automatic Differentiation (AD) works.
For simple algebraic operation, I get the chain rule thing.
But, when the code contains conditional statement like

1: test_sign = x*y < 0
2: if test_sign :
3:     biggest = max(x,y)
4: else
5:     smallest = min(x,y)

Does AD work?
If it works, can you explain why?

When the code executes line 1, how does AD interpret the inequality <?
Let's say, my AD is in foward mode, what is the differential for the if then else branch?

My understanding is that the above code use non differentiable function, in the sense that left and right derivatives are not the same. So, how does AD pick the good derivative?

Also, if I'm in forward mode, it is possible that line 5 is never visited. But when AD bumps x to x+h, line 5 should be evaluated. So the AD tape will incorrectly always differentiate line 3, instead of differentiation line 5.


texts: Can such an algorithm be written using recursion

texts:
I'm writing an algorithm that, given a limit N, and given a list of elements of value V, find all the possible combinations so that the sum of the elements is equal to N. Note that several elements can have the same value.

A simple example to demonstrate this, if N=16, and that we have 3 elements, a, with a value of 3, b with a value of 3 and c with a value of 4, we have:

a+a+a+a+c = 12
a+b+a+b+c = 12
c+c+c+c = 12
b+b+a+b+c = 12
etc...

The algorithm I wrote is pretty straightforward, yet I have a huge trouble making it generic. Indeed, my algorithm depends on the numbers of elements given as input. Here is what I came up with, in pseudo-code:

Input: a list of element (input)
Output: A list of elements so that the sum of their value == N (output)

FOR element_1 IN input
    sum := element_1.value

    IF sum EQUALS N
        output.push([element_1])

    FOR element_2 IN input
        sum := element_2.value

        IF sum EQUALS N
            output.push([element_1, element_2])

        FOR element_3 IN input
            // etc, there will be as much inner for loops are there are elements in input

RETURN output

Note that the algorithm is working, and the results are correct.

The problem here is that my algorithm depends on how many numbers there are in the input list. To be precise, the algorithm will work if there are less elements in the input list than there are inner for loops, and fail otherwise. Thus, I wondered, is this possible to write this algorithm using recursion ? So that I can write a generic code, that will adapt to the length of the input list.

I tried, yet didn't succeed, I don't know much about algorithmic, and I wondered if there are cases where recursion cannot be applied, and if this case is one of them.


texts: Difficulty in understanding an approach to SPOJ $d$-query problem

texts:
I was trying to solve this problem on SPOJ:

  Given a sequence of $n$ numbers $a_1, a_2, \ldots, a_n$ and a number of $d$-queries. A $d$-query is a pair $(i, j)$, $(1 \leq i \leq j \leq n)$. For each $d$-query $(i, j)$, you have to return the number of distinct elements in the subsequence $a_i, a_{i+1}, \ldots, a_j$.

Specifically, the input to the problem is as follows.

Line 1: $n$, where $1 \leq n \leq 30000$
Line 2: $n$ numbers $a_1, a_2, \ldots, a_n$, where $1 \leq a_i \leq 10^6$
Line 3: $q$, the number of $d$-queries, where $1 \leq q \leq 200000$
Finally, $q$ lines, where each line contains 2 numbers $i, j$ representing a $d$-query, where $1 \leq i \leq j \leq n$.

But after a few hours of trying to solve it, I googled for a possible hint. I found one approach described here by user irancoldfusion:

  First I thought a good O(n ^ 2 + q log q) would pass, but it didn't run in time. Then, I thought of the idea below which I haven't implemented yet:

  The result of a query [a, b] is number of integers whose last occurrence in [1, b] is >= a.

  Let's have two kinds of events: QueryEvent and NumberEvent. First we read whole input and sort all events, the key for QueryEvents are their end (i.e. b for query [a, b]), and for NumberEvents the key is their position in array.

  We also have a segment tree which answers the queries of kind: how many elements are at position range [x, y]. Initially the tree is empty.

  Then we process events in order:
    + When we meet a NumberEvent:
      1. If number has occurred before at position p, we remove p from segment tree.
      2. We add position of number to the segment tree.
    + When we meet a QueryEvent:
      - Query the segment tree, and find the answer.

  The overall time complexity of algorithm is O( (n + q) log n + (n + q) log (n + q) )

But I am not able to understand it properly. Can anybody help me in understanding the approach. I want to understand how are the positions inserted and deleted from the tree. That is, what does the segment tree hold, say for an interval.


texts: What type of an algorithm is being used for directory structure scanning?

texts:
So after learning about DFS and BFS yesterday in my class I was curious as to how is scanning on various file system being done. I spent quite a bit of time trying to look for some references on the web, but so far I have failed in doing so. I'm assuming that either DFS or BFS are behind the core "scanning" in some file systems.

There's also Dijkstra's algorithm but as I'm not even sure if file system is a weighted or unweighted tree (ie. number of files being the weight or file size) it's hard to say if it's useful or not because I believe that BFS would be better than Dijkstra if it's unweighted tree.

I hope that someone could clear this up as there just isn't anything specific about it on the web.


texts: Largest set of 10-digit numbers where none have Hamming Distance = 1 with any other

texts:
I'm working on a system that will require manual data entry of 10-digit numbers (Σ = 0123456789). To help prevent data errors, I want to avoid generating any two strings that have a hamming distance of 1.
For example, if I generate the string 0123456789 then I never want to generate any of these strings: {1123456789, 2123456789, 3123456789, ...}
What is the largest set of unique strings in the universe of possible strings that satisfy the constraint where no two strings have a hamming distance of 1? If this set can be identified, is there any reasonable way to enumerate it?


texts: Ordered set cover problem: is it NP-hard?

texts:
Given a set of elements $U=\{1,2,\ldots,n\}$ and a collection of $m$ sets $\{S_1,S_2,\ldots,S_m\}$ whose union equals $U$. Each element $e$ of a set $S_i$ has a weight $w_i(e)$. The weight $w(S_i)$ of the set $S_i$ is defined as $w(S_i):=\max_{e\in S_i}w_i(e)$.

The problem is to choose an ordered collection of sets $O$ from $\{S_1,S_2,\ldots,S_m\}$ whose union is $U$ and its total weight is minimum.  Here, if $O=\{S_1,S_2,\ldots,S_p\}$, then we choose $S_1$, then we choose $S_2$, etc. We define the total weight $W(O)$ as the sum of the weight of the sets covering new elements, i.e. $$W(O)=w(S_1)+w(S_2\backslash S_1)+\ldots+w(S_p\backslash\bigcup_{i=1}^{p-1} S_i),$$ since we choose $S_1$ first, then all elements of $S_1$ are new. At the time we choose, $S_2$, the newly covered elements are $S_2\backslash S_1$, etc.


texts:
One of the steps in Binary Index Tree algorithm is to find a node's parent which is done by un-setting the rightmost SET bit. For example: if a node has index 1010 than it's parent is 1000.
To apply such transformation the following method is applied:

1) Find 2's complement of the index.
2) AND the result of 1 with index.
3) Subtract the result from 2 with index.

If the following method is applied to 1010 then we get 1000 as the answer. Now I want to understand how to create such formulas?  In Algebra we solve such type of problems by solving linear equations. How do we do it with Binary numbers to achieve such answers?


texts: How to find the big O notation of $\log^b x$

texts:
How would you determine big O notation for $\log^b x$? I don't think you can simply say $O(\log^b x)$, can you?

If you can, then here is a better question: $x^3 + \log^b x$. How would you know if it's $O(x^3)$ or something else depending on the $b$ value?


texts:
I was reading Knuth's paper "On The Translation of Languages from Left to Right", my particular interest being on RL($k$) languages (not a typo). By the end of the paper, he puts the grammar:

$$
S \rightarrow Ac
\\
S \rightarrow B
\\
A \rightarrow aAbb
\\
A  \rightarrow abb
\\
B \rightarrow aBb
\\
B \rightarrow ab
$$

Which generates the language $\{a^nb^n\}\cup\{a^nb^{2n}c\}$. He states that this language is clearly RL($k$), which is easy to see, and he proves that it cannot be LR($k$). But, in his proof, he states:

  The problem is, of course, the appearance of "c" at the extreme right.

So, my doubt is: if it wasn't for the extra "c", could the language be LR($k$)? He remarks that, of course, the problem is the "c", but I don't see how I could write an LR($k$) grammar for $\{a^nb^n\}\cup\{a^nb^{2n}\}$.


texts:
At work I’ve been tasked with inferring some type information about a dynamic language. I rewrite sequences of statements into nested let expressions, like so:

return x; Z            =>  x
var x; Z               =>  let x = undefined in Z
x = y; Z               =>  let x = y in Z
if x then T else F; Z  =>  if x then { T; Z } else { F; Z }

Since I’m starting from general type information and trying to deduce more specific types, the natural choice is refinement types. For example, the conditional operator returns a union of the types of its true and false branches. In simple cases, it works very well.

I ran into a snag, however, when trying to infer the type of the following:

function g(f) {
  var x;
  x = f(3);
  return f(x);
}

Which is rewritten to:

\f.
  let x = undefined in
    let x = f 3 in
      f x

HM would infer $\mathtt{f} : \mathtt{Int} \to \mathtt{Int}$ and consequently $\mathtt{g} : (\mathtt{Int} \to \mathtt{Int}) \to \mathtt{Int}$. The actual type I want to be able to infer is:

$$\mathtt{g} : \forall \tau_1 \tau_2. \:(\mathtt{Int} \to \tau_1 \land \tau_1 \to \tau_2) \to \tau_2$$

I’m already using functional dependencies to resolve the type of an overloaded + operator, so I figured it was a natural choice to use them to resolve the type of f within g. That is, the types of f in all its applications together uniquely determine the type of g. However, as it turns out, fundeps don’t lend themselves terribly well to variable numbers of source types.

Anyway, the interplay of polymorphism and refinement typing is problematic. So is there a better approach I’m missing? I’m currently digesting “Refinement Types for ML” and would appreciate more literature or other pointers.


texts: Are there search problems that cannot be written as decision problems?

texts:
I'm not sure whether the distinction between decision and search problems has a deeper significance or if it is just concerns the immediate answer to the problem.
Of course, if you have a finite solution space then you can easily turn a search problem into a decision problem by assigning a 'yes' to whichever output satisfies your conditions. Even if you are searching for the object which maximises some function on the solution space, you can pairwise compare the evaluations of the function to assign 'no' values and be left with the 'yes' solutions.
Perhaps there are search problems cannot be turned into decision problems if we are unable to enumerate the solution space and assign a 'yes' or 'no' to every value?


texts:
Describe construction of finite automata that accepts the language
Double-Letter(L), where Double-Letter(L) is in the language of words
from L, except each letter in the word appears twice. So $abc\in L$
$\iff aabbcc \in $ Double-Letter($L$).
For example if L={a,aa,ab,ba} then Double-Letter(L) = {aa,aaaa,aabb,bbaa}

My idea:
Create states Q that are named s and ss where $s\in \Sigma$. Make states named ss accepting if $ss \in L$
FA illustrated for the example above
What next? is this a good approach? I can't think of the next step on how to construct this doubled DFA for ALL languages.


texts: Bin packing variant for maximizing value in a bin

texts:
I'm creating a tool where, given a list of N items that have a volume (v) and a price (p), it should produce a list L that optimally fits as much value as possible into a single bin with a fixed size V. L does not need to contain all N.
My current solution is a heuristic that simply sorts all the items by price-per-volume and iterates over all items, inserting it into the bin if it can. This produces mixed results, so I'm looking to a bin-packing variant to solve this. All of the examples of bin-packing I've seen only seem to optimize for reducing the number of bins.
Is there a specific name for the variant I've described here?


texts: Kolmogorov complexity of string concatenation

texts:
If $K(s)$ is the Kolmogorov complexity of the string $s \in \{0,1\}^*$,

Can we prove (or disprove) the following statement:

"Every string $s$ is a prefix of an incompressible string; i.e. for every string $s$ there exists a string $r$ such that $K(sr) \geq |sr|$" ?

In a very informal (and perhaps not too meaningful) way: we know that $K(r) \leq |r| + O(1)$; if we pick a large enough incompressible string $r$, can we "use" the $O(1)$ to "mask" the compressibility of the given string $s$ ?

A similar (but different) result is that for any $c$, we can find $s$ and $r$ such that: $K(sr) > K(s) + K(r) + c$


texts:
I want to prove that $E \subsetneq EXP$ and i would like to do so using the Time Hierarchy Theorem

I need to choose $f(n)$, i think $2^{cn}$ is a good choice, so here is my Proof:

$E\subseteq TIME(2^{cn})$
$TIME(2^{cn}) \subsetneq TIME(n^2 \cdot (2^{cn})^2)$ Time Hierarchy Theorem
$E \subsetneq EXP$

Is this correct ?

I have done something similar with $P\subsetneq EXP$:  PROOF IDEA:

$P\subseteq TIME(2^n)$
$TIME(2^n)\subsetneq TIME(n^2\cdot (2^n)^2) \ \text{Time Hierarchy Theorem}$
$TIME(n^2\cdot (2^n)^2)\subseteq EXP$
$P\subsetneq EXP$

  Complexity class E: $E=\bigcup_{c\ge 0}TIME(2^{cn})$
  Complexity Class EXPTIME: $EXP=\bigcup_{c\ge 0}TIME(2^{n^c})$
  Time Hierarchy Theorem: $TIME(f(n)) \subsetneq TIME(n²\cdot (fn)²)$

The Time Hierarchy Theorem shows that allowing Turing Machines more computation time strictly increases the class of languages that they can decide. Recall that a function $f : N → N$ is a time-constructible function if there is a Turing machine that, given the input $1^n$ , writes down $1^{f(n)}$ on its
tape in $O(f (n))$ time.


texts: What data structure is best suited for nested values and count of values?

texts:
I have incoming stream of data which has following values.
Country, City, State

Along with maximum number of unique values to store (e.g. 50,22,12).
I need to design a system which will keep count of occurrences of above values and its sub-values. If there are more than maximum number of values then instead of storing actual value store ETC.

Country and count of occurrences
States and count of occurrences
Cities and count of occurrences

At defined time interval requirement is to calculate all counts along with subtype counts. e.g.

Country A 435, States B 264, City C 300
Country B 123, States B 825, City C 321
Country A 153, States B 122, City C 534

My system enforces following restrictions.
1. Can't use any database system to store and retrieve values.
2. For speed and use of simplicity this needs to be in memory (hence limit on maximum values stored)
3. Values are cleared at particular interval.
4. These values are nested, I can't use separate tables to keep track of 3 fields separately.

I have thought about using custom data structure which stores nested values and its count. What other ways I can achieve following design. Which data structures can be used? Are there any existing examples which does similar things?

Note : This is not a homework assignment, I am developing my own application and I am stuck at designing elegant solution for this requirement. If you think this question is too general or inappropriate for StackOverflow, before closing or voting it down leave remark which forum should be used to ask this question. Any positive feedback appreciated.


texts: Finding the max XOR of two numbers in an interval: can we do better than quadratic?

texts:
Suppose we're given two numbers $l$ and $r$ and that we want to find $\max{(i\oplus j)}$ for $l\le i,\,j\le r$.

The naïve algorithm simply checks all possible pairs; for instance in ruby we'd have:

def max_xor(l, r)
  max = 0

  (l..r).each do |i|
    (i..r).each do |j|
      if (i ^ j > max)
        max = i ^ j
      end
    end
  end

  max
end

I sense that we can do better than quadratic. Is there a better algorithm for this problem?


texts: What is the time complexity of FC_MRV algorithm?

texts: I am studying CSP and read the papers on it.I wanted to know the time complexity of Forward checking with Minium Remaining Value algorithm.


texts: How to derive dependently typed eliminators?

texts:
In dependently-typed programming, there are two main ways of decomposing data and performing recursion:

Dependent pattern matching: function definitions are given as multiple clauses. Unification ensures that all omitted cases are impossible, and an external solver ensures that recursion is well-founded.
Eliminators: Each inductive datatype $D$ has an associated constant $E_D$, which acts as an induction principle, and as recursive function that decomposes values of type $D$. These are more verbose, but have the advantage of being total (all cases are covered by $E_D$) and terminating by construction.

I've seen eliminators for common datatypes, like $Nat$, where the eliminator is basically mathematical induction, or $List$, where the eliminator is basically a fold.

I've been reading several papers on dependent pattern matching, and many refer to type theories in which datatypes can be defined, and eliminators are provided by the theory. For example, Eliminating Dependent Pattern Matching describes how UTT is based on eliminators, and how pattern matching can be converted to elimination in the presence of axiom $K$. My understanding is that, once a datatype is defined, the theory provides the eliminator.

What I haven't found (or at least, haven't recognized if I've seen it) is a good description of how one can derive the eliminators, both their types and their semantics.

Can someone point me to a reference that describes how one can obtain an eliminator from the definition of a datatype?


texts:
$L=\{a^ib^i|i\geq0\}$, cfg for $L^2$

can you write cfg for $L^2$ where $L=\{a^ib^i|i\geq0\}$?

the professor's answer sheet says it's $S\to AA\\ A\to aAb|\lambda$

but I think it is wrong because two $L$ have to be identical with each other.

can you help me figure out if there is cfg describing $L^2$?


texts: What is the formal analysis with Simple Uniform Hashing that the load factor is $\alpha = \frac{n}{m}$

texts:
Recall the definition of the load factor is the average number of elements in a chain for hashing for a table $T$ of size $m$ (with $n$ elements in consideration). Let $n_j = T[j]$ be the size of the chain for entry $j$. In this case the definition of the load factor should be:

$$ \mathbb{E}[n_j] = \mathbb{E}[T[j]] = \alpha = \frac{n}{m}$$

I was wondering, why is the above statement correct under the Simple Uniform Hashing (i.e. the probability that any given element is equally likely to hash into any of the $m$ slots or in equations $Pr[h(k_i) = h(k_j)] = \frac{1}{m}$)? In particular, I find it difficult to understand what exactly distribution (or what random variables to define) in order to compute the expectation. What distribution is the expectation taken over with respect to?

CLRS talks about this on page 259 but they never quite explain in detail why it is $\frac{n}{m}$ or ignore (leave out) the probabilistic analysis.

After some thinking I realized that $n_j$ is a random variable and it depends on how the hash function $h$ distributes keys (and I guess also in the keys one might get). So a realization of $n_j$ will be in the set $\{ 0, ..., m-1 \}$, since the table can only have a $0$ elements up to $m$ elements. Hence to calculate the expected length of $n_j$ we compute:

$$\mathbb{E}[n_j] = \sum^{m-1}_{x=0} x \Pr[n_j = x]$$

but my question is, how does one determine the distribution for $x$?


texts: Finding the Best Fitting Plane Given a Set of 3D Points

texts:
Suppose that we have $n$ points in 3D.

I want to find a plane $ax + by + cz + d$ such that sum of all the orthogonal distances to the plane is minimum.

I read this article. However, I need an algorithmic solution.

So far, this answer from SO was the simplest one. However, this solution projects the points onto $z=0$ plane all the time.

Could you help me to write the algorithm? I'll code it in Java.


texts: Bit operations; Treating a number like an array

texts:
Are there features in programming languages that allow you to directly access the $k^{th}$ bit of a number. Treating it like an integer.

I'm not talking of using bit shifting to retrieve a number. But directly access the bit at index $i$ of a number as if it were an array.

I'm looking at this feature to replace shifting to write an algorithm I was working on. If it isn't faster than shifting, then such a feature would be pointless.

I didn't ask this on stack overflow as this isn't about a specific programming language, but about whether programming languages in general have this feature.

Also are there language features for inverting the bits(a specific bit or as many as needed) of a number?


texts: Can I say the two cases of Recursion Tree are always either $\theta{(n)}$ or $\theta({n\log{n}})$

texts:
Given positive constants: $c_1, c_2, ..., c_k, c^\prime$, assume that
$T(n) = T(c_1n) + T(c_2n) + ...+ T(c_kn) + c^\prime n$

There are two cases:

$c_1 + c_2 + ...+ c_k < 1$
$c_1 + c_2 + ...+ c_k = 1$

As I observed (from some problems), in case 1 $T(n) = \theta{(n)}$, in case 2 $T(n) = \theta{(n\log{n})}$
But I didn't find the theory says this always true,
so I'm wondering, generally is this true or a theorem or is there any counterexample?

For example,
of Case 1 : $T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + T(\frac{n}{8}) + n = \theta{(n)}$  and
of Case 2 : $T(n) = T(\frac{n}{3}) + T(\frac{2n}{3}) + n = \theta{(n\log{n})}$


texts:
I have two questions:

I consider the following language
$$L_1= \{ w\in \{0,1\}^* \mid \not \exists u\in \{0,1\}^* \colon w= uu^R\}.$$
In other words $w$ is not palindrome with even length. I proved that this language is NOT regular by proving that its complement is not regular. My question is how to prove it using the pumping lemma without using going over the complement.
Let
$$L_2=\{w\in\{0,1\}^* \mid \text{$w$ has same number of 101 substrings and 010 substrings}\}. $$  I proved that this language is not regular by using equivalence classes. How I can prove it using the pumping lemma?

Thanks alot for edit:)


texts: Is there a meaningful difference between O(1) and O(log n)?

texts:
A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ elements to process, even an $O(1)$ operation such as an index lookup will start to take longer as the index has to be calculated in multiple operations. I think it will take at least $O(\log n)$.

Similarly even if an algorithm has $O(\log n)$ complexity, $\log n$ cannot possibly grow larger than about a hundred, so could be ignored as no larger than a small constant.

So, is it really meaningful to treat $O(1)$ and $O(\log n)$ as different?

The same applies of any difference of $\log n$, like between $O(n)$, $O(n\log n)$ and $O(n/\log n)$.


texts: Normalized measure from dynamic time warping

texts:
I am trying to find the similarity between two time series, but not in terms of distance, in something more sensible such as percentage of similarity. In other words I need something that shows the similarity, not dis-similarity.

The dynamic time warping gives a very good response, when trying to compare the time-series. But the distance computed by dynamic time warping depends on the duration of the time series and the magnitude of the template and the query. Moreover, it shows the distance, which demonstrates the dis-similarity.

Is there a way to convert the distance from DTW into some form of normalized similarity measure?


texts: Counting Number of Points Satisfying given Equation

texts:
I am given set of points S. I need to find the count of four vertices (A, B, C, D) satsfying the equation AB + CD = BC + AD, morever, the vertices should be pairwise distinct.

Here, A, B, C, D denotes the vertices choosen from set S.
AB, BC, CD, AD denotes the distance between A and B, B and C, C and D, and A and D respectively.

I could come up with an algorithm of O(N^4). Is there any more optimal solution?

Example :
S = {(3, 0), (0, 4), (7, 3), (4, 7)}
Ans = 8
These are the indexed of S which satisfies the given equation

1 2 4 3
1 3 4 2
2 1 3 4
2 4 3 1
3 1 2 4
3 4 2 1
4 2 1 3
4 3 1 2


texts: What is the best way to compare two images for similarity if the brightness of the second image was changed?

texts: I calculate similarity percent between two images. Another image is the same with changed brightness. I've already tried comparing by pixel (euclidean distance for grayscale and 0/1 values), comparing by HSV. I've tried also normalisation (pixel brightness-mean brightness). The results were quite good (80-90%), but the similarity rate with changed image was lower than similarity between images with compeletely different tables, for example. Is there any simple approach to solve this problem? Or should I use neural networks?


texts: What are the main ideas used in a Fenwick tree?

texts:
While I was solving a programming competition question, I came across a technique advertised as suitable for the solution. A so called Fenwick tree (a.k.a binary indexed tree) was at the heart of this technique. So in an effort to understand Fenwick trees, I researched all online sources in vain because reading them in details is a pain!

No one seems to be able to explain the main concepts behind this data structure in a concise and clear way. Can anyone please give a high level exposition of the main ideas related to Fenwick trees without going into unnecessary details?


texts:
To be precise I am here for RAW hazard.
Consider a 5 stage pipeline .

In case of $I_4-I_1$ dependency , I am not sure if it is an $RAW$  hazard as $I_4$ does not depends on value of
$R_1$ that $I_1$ gives. and even if it fetches it ,it still be a wrong value as per the instruction sequence as $I_2$ is modifying it.

So , is $I_4-I_1$ a $RAW$ hazard ?
and if yes, then please give suitable explanation why so and related information about $RAW$  hazard as it happened even if $I_2$ modified the Value in between .


texts: Two-Sum - Pre-sort Optimization Algorithm Design

texts:
Is it possible to optimize the runtime of a two-sum solution by receiving a pre-sorted input either in ascending or descending order?
 Original Two-Sum
Determine whether there are two items whose individual capacity will perfectly equal the total capacity while ensuring the same item cannot be selected twice.

Input: An Int representing the total capacity and an Array of Int's representing items' individual capacities.
Output: A Boolean representing whether it is possible for two of the items to equal the total capacity.
Time complexity: Linear growth, $O(n)$
Space complexity: Linear growth, $O(n)$

Samples
Input: [4, 5, 2, 6]

Total capacity: 10
Expect: true

Input: [4, 5, 2, 5]

Total capacity: 10
Expect: true

Input: [4, 5, 2, 7]

Total capacity: 10
Expect: false

Pseudocode

Create a Set searchSet to store the item's that have already been examined.

Iterate through the input Array of item capacities.
2a. Find the targetCapacity for the current item: totalCapacity - itemCapacity
2b. If searchSet contains the targetCapacity, return true.
2c. Else, add the itemCapacity to the searchSet.

Return false if the entire input is iterated through without finding a match.

 Pre-Sort

Save a new var lastTargetCapacity
If the current itemCapacity < lastTargetCapacity, there are no possible two-sums and return false.

i.e.
Input: [6,2,1,0]

Total capacity: 9

Iterations

targetCapacity = 9 - 6, lastTargetCapacity = 3
Return false because the itemCapacity of 2 < lastTargetCapacity of 3.


texts: Languages that are not subset, but are union

texts: Are there examples of regular languages $L_1$ and $L_2$, where $L_1$ and $L_2$ is not a subset of each other but  that $(L_1 \cup L_2)^* = L_1^* \cup L_2^*$ ?


texts: Prove by Induction that $r_n$ is $O(\log_2(\log_2n))$

texts:
Let the sequence $r$ be defined by:

$$\begin{align*}r_{1} &= 1\\
r_n&= 1 + r_{\lfloor\sqrt{n}\rfloor}\,,\quad n\geq 2\,.\end{align*}$$

Prove by induction that $r_n$ is $O(\log_2(\log_2n))$.

My idea is to find the closed form function of r and then use the big O definition on the closed form function but I'm having a hard time even finding the function in the first place. Any help? Also is this even the right way to approach this proof?

Thanks.


texts: NFA-style representation of regexps which includes AND

texts:
I'm looking for a regexp matching strategy that supports conjunction and which is based on an NFA-style machine.  I know how to handle conjunctions using a DFA, or using Brzozowski's approach, but for various reasons, I can't use Brzozowski's technique and bump into state explosion when using a DFA.

I know about the cross-product construction to compute the intersection of two NFAs, but there as well: while the state explosion is not as severe as when going through a DFA, it is sometimes still too severe for my needs, so I'd like an NFA-like representation that lets me build the cross-product "on the fly", kind of like "Thompson's NFA" matching constructs the DFA states on the fly.


texts: How can one flip a stream using corecursion

texts:
Following is the definition of codata stream:

codata Stream where
    hd : Stream −> A
    tl : Stream −> Stream

For simplicity I assume I have just a binary stream. Now I would like to define a function flip : Stream -> Stream , that reverses the order of the stream elements.

Defining: hd(flip S) = head (S) is pretty simple.

However I don't see how one can define tl(flip S)) properly. Does anyone have an idea, if this is possible and if yes, how?


texts: After the training phase, is it better to run neural networks on a GPU or CPU?

texts:
Sorry if this is the wrong forum for this question. My understanding was GPUs were more efficient for running neural nets, but someone recently suggested GPUs are only needed for the training phase. Once trained, it's actually more efficient to run them on CPUs.

Is this true?


texts: Balance factor changes after local rotations in AVL tree

texts:
I try to understand balance factors change after local rotations in AVL trees.
Given the rotate_left operation:

  x            y'
 / \          / \
a   y   =>   x'  c
   / \      / \
  b   c    a   b

and $b(x)$, $b(y)$ - balance factors for $x$ and $y$ nodes - I want to find $b(x')$ and $b(y')$.

In my reasoning I will use the Iverson bracket notation, that denotes a number that is 1 if the condition in square brackets is satisfied, and 0 otherwise:
$$
[P]=\begin{cases} 1, \text{ if } P \text{ is true}; \\
              0, \text{ otherwise}.\end{cases} $$

Balance factor for the node $x'$ can be calculated like this:
$$b(x') = h(b) - h(a)$$

where $h(b)$ and $h(a)$ - the heights of sub-trees $a$ and $b$.

Let's substitute $h(b) = h(y) - b(y)[b(y) > 0] - 1$ and $h(a) = h(x) - b(x)[b(x) > 0] - 1$:

$$b(x') = (h(y) - b(y)[b(y) > 0] - 1) - (h(x) - b(x)[b(x) > 0] - 1)$$

Some simplification:

$$b(x') = h(y) - b(y)[b(y) > 0] - h(x) + b(x)[b(x) > 0]$$

Now substitute $h(y) = h(x) + b(x)[b(x) \le 0] - 1 $:

$$b(x') = h(x) + b(x)[b(x) \le 0] - 1 - b(y)[b(y) > 0] - h(x) + b(x)[b(x) > 0]$$

Obviously, $[b(x) \le 0] + [b(x) > 0] = 1$:

$$b(x') = h(x) + b(x) - 1 - b(y)[b(y) > 0] - h(x)$$

Simplify again:

$$b(x') = b(x) - b(y)[b(y) > 0] - 1$$

In the same way I can find balance factor for $y'$. Skipping intermediate steps I get:
$$ b(y') = h(c) - h(x') =\\
     ...\\
     = b(x) + b(y)[b(y) \le 0] - b(x')[b(x') > 0] - 2$$

Somehow I have feeling that this is not the simplest formula for balance factors.

Is there any simpler approach to calculate balance factors, which would always work even if the tree becomes unbalanced?

EDIT:

The simplest formulas I managed to get look like this (see my own answer for details):
$$b(y′)=b(y)+b(x')[b(x')\le0]−1$$
$$b(x′)=b(x)−b(y)[b(y)>0]−1$$


texts: What's a minimum-window alpha beta search algorithm?

texts: I was skimming the Deep Blue overview paper and on page 242 it says: "The search control does not really implement the regular αβ search algorithm. Rather it implements a minimum-window αβ search algorithm. This eliminates the need for value stack." I know the basics of alpha beta pruning/search, but couldn't find any reference to minimum-window αβ search algorithm online. Does the algorithm go by a different name nowadays that I might be able to look up somewhere ?


texts:
Can someone help me giving a pseudo code to this problem : There are two groups of processes , A and B. Maximum 3 Processes from group A or group B(only from one group) can use the given resource . How can this be implemented using semaphores ?

I'm thinking of something like this :

Semaphore work = 1
semaphore nProcesses = 3
Process A:

P(work);
P(nProcesses);

access(resource);

V(nProcesses);
….
V(work);

Process B:

P(work);
P(nProcesses);

access(resource);

V(nProcesses);
….
V(work);

..but I don't know when to free the work semaphore .


texts: Defining decision-problem complexity classes by counting branches of a polynomial-time NTM

texts:
This answer on another SE community discusses the concept of a "counting complexity class". As far as I can tell, the author is using that term in a slightly nonstandard way: most sources (PS format) use that term to refer to complexity class like #P of counting problems that count the accepting branches of a polynomial-time nondeterministic Turing machine (NTM). The author of the linked answer seems to be using the term to mean a complexity class C for decision problems such that C can be defined in terms of this count. Am I understanding this correctly?

If so, then I believe that all of the following counting complexity classes (in the latter sense of the term) can be defined in the form "C is the set of decision problems for which there exists a polynomial-time NTM such that ...". Am I completing the sentences correctly for each counting complexity class?

P: if the answer is yes then every branch accepts, and if the answer is no then every branch rejects. (My answer below explains why this definition is equivalent to the usual one.)
RP: if the answer is yes then a fraction $p$ of the branches accept, where $p$ is a positive number that does not depend on the input size. If the answer is no then every branch rejects.
co-RP: if the answer is yes then every branch accepts. If the answer is no then a fraction $p$ of the branches reject, where $p$ is a positive number that does not depend on the input size.
BPP: if the answer is yes then a fraction p of the branches accept, where $p > 1/2$ does not depend on the input size. If the answer is no then a fraction q of the branches reject, where $q > 1/2$ does not depend on the input size.
NP: if the answer is yes then at least one branch accepts. If the answer is no then every branch rejects.
co-NP: if the answer is yes then every branch accepts. If the answer is no then at least one branch rejects.
C$ _=$P: if the answer is yes then exactly half the branches accept. If the answer is no then the fraction of accepting branches does not equal $1/2$.
PP: if the answer is yes then most branch accept, and if the answer is no then at least half the branches reject.

One advantage of this formulation is that it makes obvious the class inclusions P $\subset$ (co-)RP $\subset$ BPP (using this trick) $\subset$ PP and (co-)RP $\subset$ (co-)NP $\subset$ PP (using Buchfuhrer's trick here).

Note: In order to make this question clearer and more useful for future viewers, I have edited it to make every definition correct. The definitions in the original version of my question (available in the question history) had a few errors, which Ariel pointed out in their answer.


texts: $L_n = \{x \in \Sigma^{*} | \exists w, y, z \in \Sigma^*, x = ywz, w^r = w, |w| = n \}$ Informally x is palindrome of length n. Find regex for n = 1

texts:
$L_n = \{x \in \Sigma^{*} | \exists w, y, z \in \Sigma^*, x = ywz, w^R = w, |w| = n \}$

Informally x is palindrome of length n

where $\Sigma = \{0,1\}$

I'm having a hard time understanding this could someone please explain.

For $n = 1$

$L_1 = (0+1)^*(0+1)^*$ (Why? What does this mean?)

$L_1^c = ?$ (What would the compliment mean)

For $n = 2$

$L_2 = (0+1)^*(00+11)(0+1)^*$

$L_2^c = (10)^*(\epsilon + 1) + (01)^*(\epsilon + 0)$

I get how regexes work I just don't understand how $L_1$ is the regex for palindrome of length one. Not sure what the compliment means. Same for $L_2$


texts: Why doesn't subset sum problem contradict the Exponential time hypothesis?

texts: Subset sum can be solved with dynamic programming in pseudopolynomial time O(mn) which is subexponential. And, of course, subset sum problem is NP-complete. Why doesn't that contradict the Exponential time hypothesis?


texts: Is there a name for the technique used in the "merge" part of MergeSort?

texts:
MergeSort has two parts, "divide" and "merge" (arguably three if you include "recurse" as its own part in the middle). I'm interested in the "merge" part, which tends to look like this:

consider two priority queues list1, list2
initialize an empty sorted list
while neither list1 nor list2 is empty:
    find lowest element between peek(list1) and peek(list2)
    pop that element from its list and add it to the sorted list
add the rest of the non-empty list to the sorted list
return the sorted list

This paradigm of "split into multiple priority queues and continuously handle the first elements" is also useful for problems that decidedly do not involve merging, such as performing operations on one list depending on the highest-priority element of another list that's less than it. For example,

consider two priority queues list1, list2
initialize an empty destination list
while neither list1 nor list2 is empty:
    while peek(list1) < peek(list2):
        add f(peek(list1), peek(list2)) to destination list
        pop element from list1
    pop element from list2
return destination list

In both of these examples, the same idea of "iterate through multiple priority queues simultaneously, doing something with the top elements of each, but only pop one of them at a time" is used. This is different than matching two lists and enumerating through corresponding elements.

Is there a specific name for this technique/paradigm? The Wikipedia page for MergeSort does not, at time of writing, answer the question, and in the context of MergeSort I've never seen it described as anything other than "merge" (which is inaccurate in my second example) or "conquer" (which is too vague).


texts:
I'm trying to come up with a context-free grammar for the following language:

$$L = \{a^mb^nc^{m+n}\mid 0 \le n \le m\}$$

My thinking is that i can rewrite this to

$$L = \{a^mb^nc^nc^m\mid 0 \le n \le m\}$$

and then create the grammar

$$
\begin{align*}
S &\rightarrow aSc \mid B\\
B &\rightarrow bBc \mid \epsilon
\end{align*}
$$

The problem is that this grammar doesn't capture $0 \le n \le m$ and I can't figure out how to do this. Any help would be greatly appreciated.


texts: Prove that in an optimal code, if the letter frequencies are increasing, the encoding lengths are monotonically decreasing

texts:
I am trying to prove that, in an optimal encoding (possibly Huffman?), if letter frequencies are increasing, their encoding lengths are monotonically decreasing. It is intuitive that this makes sense, but I'm not sure how to write it formally.

Here is what I have:

Let $x_1$ and $x_2$ be two letters in the encoding where $x_1$ is before $x_2$.

It is given that $\text{freq}(x_1) < \text{freq}(x_2)$.

Suppose the contradiction, $\text{code_length}(x_1) < \text{code_length}(x_2)$.

The cost would be $$B(A) = \text{freq}(x_1)\times\text{code_length}(x_1) + \text{freq}(x_2)\times\text{code_length}(x_2)+r$$ where $r$ is the remaining cost of the other letters in the code.

If we were to swap the code lengths of $x_1$ and $x_2$, the cost would become $$B(A) = \text{freq}(x_1)\times\text{code_length}(x_2) + \text{freq}(x_2)\times\text{code_length}(x_1)+r$$

The cost would decrease, meaning the code where they are not swapped is not an optimal encoding.

The problem is I'm not sure how to prove that the cost would decrease. Is that provable? Also, is there a better approach?


texts: Planar cover of a rigid and non-planar graph

texts:
Let $G$ be a graph which is rigid and non-planar (e.g. $K_{3,3}$). Is it possible that $G$ has a planar cover?

Are there any studies on this topic?


texts: Is there a Zero-Knowledge proof for SAT?

texts:
I know that SAT can be reduced to (3 vertex) Graph colouring, and there is a Zero-knowlegde protocol (ZKP) for graph colouring. However, I am interested in a ZKP that can be performed directly on a SAT instance, without graph colouring.
Is there a known ZKP for SAT, and if not how would you suggest coming up with one?


texts: Can Edge Belong to a cycle if it is part of multiple BFS products

texts:
Given a simple connected undirected graph. with V vertices and E edges.
Let e be some edge from E.
If I perform |V| different BFS runs - meaning started each time from a different vertex - and in every run e is part of the Spanning tree produced from the run.
Can it be belonging to some cycle?
The multiple answers I have to choose from are:

it does not belong to any cycle
e might belong to a cycle but if it belongs to an odd-length cycle, then it must belong to an even-length cycle.
e might belong to a cycle but if it belongs to an even-length cycle, then it must belong to an odd-length cycle.
None of the above.

My claim is, because BFS is deterministic and because we performed |V| BFS on the graph, each time from a different vertex. if e was on some cycle, and it doesn't matter even-length or odd length, one of the vertices on the cycle would have caught up with it and remove it.
The only way that it belongs to every Spanning tree, is if it's un replaceable, meaning it's the only thing connecting two vertices.
Am I right? is there any formal proof th


texts:
In both B-trees and B+trees, a node (a.k.a page) contains K keys and K+1 pointers:

node = [ ptr_1, key_1,  ... , ptr_K , key_K , ptr_(K+1) ]

Now suppose that I want a B/B+ tree (whichever possible), where each node contains exactly K keys and K pointers, in form of {key,ptr} pairs:

node = [{key_1,ptr_1} , ... , {key_K,ptr_K}]

By aligning key-values as an array of paired structs, it will be more efficient to process key-value pairs in CPUs and use SIMD operations, etc.

It is easy to statically construct an n-ary search tree with this node layout, simply by building the tree from bottom to top. However, the insert/delete procedure of B-tree and B+-tree is specifically designed for a node with K keys and K+1 pointers.

I don't know how to do insert/updates in a consistent manner when there is no left-most pointer in the nodes; in a way that the theoretical O(log_n) guarantee is still preserved.

Any suggestions? I specifically wonder if such a data structure is known or discussed somewhere.


texts:
Consider a datatype whose objects will be sequences of elements that has the following two methods

prepend($x, T$) which will insert an element to x to the beginning of the sequence T

search($T, i$) which returns the ith element in the given sequence

T is a linked list. prepend takes $1$ step. Search takes $i$ steps

Suppose T has exactly one element and a sequence of n operations are performed. You are given that prepend has probability $p$ and search has probability $1-p$ for each operation. The value of $i$ is chosen uniformly from $[1, \dots, T]$

Q) Derive the expected length for the linked list just before the k'th operation is performed

so we need the weighted average of all possible values of some random variable. for each $X_i$ let it be the number of steps for given events. If theres a prepend we add a node whereas if theres an access we do nothing to the length. How do we come up with an equation for expectd length?

$E(X) = something \cdot (k-1)$ since just before $k$ but not sure how to derive the probability yet

Any help appreciated


texts: Minimizing sum of $w_i(y_i - y_c)$ over $y_c$

texts:
A person wants to connect $n$ circuit points to the clock signal. Now, the clock signal is going to pass parallel to the x-axis and all those circuit points are going to be connected by vertical to the clock line. Suppose the widths of the vertical wires in the given diagram also vary varying.

If the coordinates $(x_i,y_i)$ for each circuit point $c_i$ to be connected  are given, find $y=y_c$, through which the clock line should pass to minimize the expression
$$L = \sum_{i=1}^n w_i(y_i - y_c)$$
Also prove that your solution is optimal.


texts: What is the meaning of in place and out place in sorting? What are the difference of two of them? Couldn't find any good explanation in the internet.


texts: Minimum square side length to enclose n circles of radius r

texts:
I thought of a problem but have no idea how to solve it. The problem is as follows:

Given 2 numbers, n and r, find the side length (S) of the smallest square that encloses n circles each of radius r without any overlap among any of the circles.

I though about a greedy approach that would find the optimal position for each circle locally and placing it before moving onto the next one, but realized that it would be difficult without being given definitive positions of each of the circles. Is there a solution to this problem?


texts: Memory Hierarchy and storing data in caches

texts:
Question: How many 32 bit integers can be stored in a 16 bit cache line.
Answer: 4

can somebody please explain for me why the answer is 4 i did not understand the reason and i think they should give us more given like the number of blocks in the cache..


texts:
I never used a debugger that can run a program backwards but I would like to. Now I wonder if there is much evidence and theory about backwards runnable programming, when and why a program can be run backwards or when and why not?

Intuitively I find that the computer should be able to run the program backwards, if it once has run the program forward knowing that the program will run backwards hence saving states of the program that otherwise might get lost and deallocated.

Debugging is just a practical example. I'm also interested in it for the sake of the theory of reversibility, if the program can be run backwards, then what the program does is reversible, isn't it?


texts: What is the process of bringing equal elements together in an array?

texts:
I have a large array of mostly random numbers, with a few elements equal to each other. I need to change the array so that any elements that are equal are next to each other. Of course, sorting solves this problem but since I do not require the entire array to be in order I am assuming there are faster algorithms for this.

I am mainly asking what is this process called so I can read up on it further. I need to understand the different approaches that exist and so am not looking for a specific algorithm, but any suggestions for such would be appreciated as well.

Many thanks.


texts: Interpretation of this regular expression: (1*0*)*

texts:
Do the values of the two * inside the ( ) need to remain unchanged for every repetition of ( )?

For example, 110011001100 is part of this language set, but 1100100010 isn't?

Or can the values of the two * change for every repetition of the ( )?


texts: Would it be possible for a new technology to make RAM obsolete?

texts:
If a new technology is invented for storage devices, which is the same as or speeder than RAM (bandwidth&lanecy), is it possible to make RAM obsolete and consider the storage device as the main memory?

if that happened data and program would run directly from the storage device, or the RAM or its concept (especially as temporary space) must be part of the storage device such as at the beginning addresses.


texts: Traveling Salesman -- number of qubits required?

texts:
I'm trying (in vain) to get a beginner's grasp of quantum computing, so doing a lot of reading. I've started looking at IBM's QISkit Jupyter Notebooks, and came across the one on MaxCut problems. In there, they give an example of how you could use quantum computers to solve the Traveling Salesman problem, for 4 cities. I may have missed the explanation somewhere in the notebook, but they use 9 qubits to address the problem -- can someone explain why 9? It is a hardcoded value in the actual code, which indicates to me that you could use different numbers...so what would be the tradeoffs with using more or fewer qubits, and how would that scale with the number of cities?

I understand that I can run the notebook and change the value to see how the results change, but I'd like to get a better theoretical grasp of why.

Thanks!


texts: Is it efficient to use large scale data algorithms on disk?

texts: Is it efficient to use algorithms like locality sensitive hashing and bloom filters  on disk instead of memory for very large datasets where even these structures cannot be saved in memory?


texts: Determine smallest possible parameter set for FPT

texts:
I am reading a book about complexity analysis and cannot find a way to solve a problem in that book.
The problem is, that I do not understand how to determine the smallest possible parameters, given the runtime of an algorithm. Do I just need to insert some numbers and see if the parameters exceed n at some point? Perhaps someone can explain that to me.

Consider the following exercise:

  The following O(.) expressions represent worst-case runtimes of different algorithms, where n is a measure of the input size and p, q and r are parameters (where p, q, r <= n). Which of the following running times are FPT running times?
  Give the smallest possible parameter set for which the running times are FPT (if one exists) and explain.

  a) $O(p^q * n^2)$

Now I know that by the definition of FPT, this runtime is FPT (because we have a function of the parameters times n^constant). However, what are the smallest $p$ and $q$ in that case?

There are some more, but I just want to understand how to solve it and then I'll try the rest myself again.

Taken from:

  Rooij, I. V., Blokpoel, M., Kwisthout, J., & Wareham, T. (2019). Fixed-Parameter Tractable Time. In Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis (p. 125). Cambridge, England: Cambridge University Press.


texts: Labeled points in $\{0,1\}^n$ such that every linear separator requires exponential weights

texts:
I want to find labeled samples in $\{0,1\}^n$ such that the Perceptron algorithm takes $2^{\Omega(n)}$ steps to converge. One way to do this would be to find a sequence of labeled examples that are linearly separable, but require every linear separator to have at least one exponentially large weight. To show that the samples are linearly separable, it is enough to show that they are consistent with a decision list, which should be apparent from the list of samples. So, my question is

  Does there exist a set of labeled samples $S$ in $\{0,1\}^n$ that are consistent with a decision list and such that any linear threshold function that correctly labels $S$ has at least one exponentially large weight $w_i = 2^{\Omega(n)}$?

Here are the definitions that I'm working with: A linear threshold function $f \colon \{0,1\}^n \to \{0,1\}$ with associated weights $w_0, \dots, w_n \in \mathbb{R}$ gives $f(x) = 1$ if and only if $w_1x_1 + w_2x_2 + \dots + w_nx_n \geq w_0$. Given a set $S$ of points in $\{0,1\}^n$ labeled $0$ or $1$, we say that a linear threshold function $f$ correctly labels $S$ if $f(x) = 1$ whenever $x$ is labeled $1$ and $f(x) = 0$ whenever $x$ is labeled $0$ for all $x \in S$.

Note: I had asked the same question on math.stackexchange since it seemed relevant to both fields. Here is the link for that.


texts:
I've found the following algorithm for selection sort on the internet.

program SelectionSort(input,output);
var
  A : Array[1..80] of Integer;
  n, i, j, k, m, loc, temp : Integer;
begin
  writeln('size of the array?');
  read(n);

  for i := 1 to n do
   read(A[i]);

  for k := 1 to n - 1 do
   begin
    m := A[k];
    loc := k;
     for j := k + 1 to n do
      begin
       if m > A[j] then
        begin
         m := A[j];
         loc := A[j];
         loc := j;
        end;
      end;
     temp := A[k];
     A[k] := A[loc];
     A[loc] := temp;
   end;

  for i := 1 to n do
   begin
    writeln(A[i] : 3);
   end;

  readln();
  readln();
end.

I'd like to gain a better understanding of how it actually does the sorting. Could someone please help me with this?


texts:
Is there anything known about mixing time of Markov chains for three particle systems?

It is proved here
http://www.ams.org/journals/tran/2005-357-08/S0002-9947-05-03610-X/S0002-9947-05-03610-X.pdf
that the mixing time of an exclusion process is O(n). We can think if a exclusion process, a Markov chain on permutations of two particles (0,1). I wonder if there is any result such as that for three particles.


texts:
I am making database on Disaster Management. There are four tables.

DisasterEvent (eventid, name, glideID, status, description, date_occurred,  date_ended, disaster_type)
People(eventid, num_deaths, num_injuries, num_affected)
Homes (eventid, num_homes_destroyed, num_homes_damaged, total_insured_loss, total_uninsured_loss)
Place (place_id, city, state, country, postal_code)

In my design, I have one to one relationship between People and DisasterEvent , and one to one relationship between Home and DisasterEvent because for a particular disaster there is only one People table that we are concerned and same for Home table.
Now, Place has many to many relationship with DisasterEvent because at particular place there can be many disasters over time and same disaster could occur many place at once.

What am I trying to achieve is able to map number of affected people by the particular disaster event at certain place. For this I think there needs to be three way relationship among DisasterEvent, Place and People. How do I achieve this?


texts: Is star closure of reverse of language equivalent to reverse of closure of that language

texts:
is the following true
$ (L^R)^* = (L^*)^R $

I tried the following to prove it true.
let u,v belong to L then $ L^* = \{ u,v, uu, vv, uv, vu ... \} $
and $ (L^*)^R = \{ u^R, v^R, u^Ru^R, v^Rv^R, v^Ru^R, u^Rv^R ... \} $

now $ L^R = \{ u^R, v^R \} $ so
$(L^R)^* = \{ u^R, v^R, u^Ru^R, v^Rv^R, u^Rv^R, v^Ru^R ... \} $


texts:
What are the non-trivial graph families that have a known chromatic number, or an easy way (polynomial-time algorithm) to compute the latter.

Examples would be:

Kneser graphs
Chordal graphs

Do you know any other families?

Motivation:

We are looking for interesting classes on which we can test a proper coloring heuristic. This is why we wanted some graphs that are not so easy to color but in the same time have a known chromatic number so we can evaluate the quality of the heuristic.


texts: Is there a limit to data compression without mentioning Kolmogorov complexity?

texts:
I want to develop a previous answer to Is there a known maximum for how much a string of 0's and 1's can be compressed?.

I've looked at the Hutter Prize and various compression benchmarks.  The compression records are graphed below over a 12 year period.  The red curve is an exponential fit, which seems to be asymptotic to something much greater than zero (10MB?). The test file (enwik8) is a bulk extract from Wikipedia, and I don't think that Mr Kolmogorov can help us here.

I'm not overtly asking what the limit is. I'm just asking is there (or could there possibly be) a limit to data compression without Mr. Kolmogorov, whilst using contemporary science? Intuitively and as the fitted curve suggests, there must be some limit as the data can't be compressed to 1 bit.  Can anyone expand on any research regarding how close we might be to a minimum value for losslessly compressing enwik8? Is another 25% improvement possible? Is there any active research in this field or is the Hutter team leading the world?


texts: Scheduling algorithm for a student's study times given assignments, expected time, due dates, and class times

texts:
I would like to create an algorithm that advises a student when they should work on certain assignments given the expected time each assignment will take, and the due date of each assignment.
Say that for a students' weekly schedule, there are class times and events that must be attended. With the remaining time slots in the week, how can I assign times to work on each assignment so that the recommended assignment time is fulfilled before the due date.
This is very similar to single-machine scheduling problems, and usually a greedy algorithm of closest-due-date-first would work, but I want to implement constraints based on human factors. For example: don't work on one assignment for more than 2 hours in a row, don't schedule a study time right after a class, etc.
How would I go about including these human factor constraints within my algorithm?


texts: How would I design an NFA that recognises the language of all strings that don't end in a certain sequence?

texts:
How would I design an NFA that accepts all strings don't end in a certain sequence over the alphabet {0,1}.
Designing a DFA that does the job is fairly straight forward, but I can't find out how to make my Automata Non-Deterministic.


texts: Polynomial size Boolean circuit for counting number of bits

texts:
Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x_1, y_1, \dots, x_n, y_n)$, such that the output is true if and only if the assignment that makes it true verifies

$$\sum_{i = 1}^{i = n} (x_i + y_i) \not\equiv n \bmod 3$$

I should specify that this I am looking for a Boolean circuit, not necessarily a Boolean formula as it is usually written in Conjunctive Normal Form (CNF). This is because when written in CNF, a formula like the one before has a trivial representation where the number of clauses is approximately $\frac{4^n}{3}$, as it contains a clause for every assignment $(x_1, y_1, \dots, x_n, y_n)$ whose bits sum to a value which is congruent with $n \bmod 3$. Constructing such a formula would therefore take exponential time.

I have been told that a Boolean circuit can be found for this formula that accepts a representation of size polynomial in $n$. However, so far I have been unable to find it. I would use some help; thanks.


texts: What is the explicit definition about the computablity of non-deterministic Turing machine?

texts:
Given a finite alphabet $\Sigma$. We define the set of all words of finite length to be $\Sigma^{*}$.

A partial function can become a total function with trivial modifications, thus we just consider about the total function.

Is the following definition correct?

We say a function $f \colon \Sigma^{*} \rightarrow \Sigma^{*}$ is computable by a NDTM $M$, if $M$ halts on every input $x \in \Sigma^{*}$ and The run of $M$ on $x$ halts with $f(x)$ written on its tape.

My questions:

1-What is the usefulness of $q_{accept}$ and $q_{reject}$ here？What kind of inputs dose the $M$ accept (reject)?

2-Is the output of the $M$ are the same on input $x$? (the NDTM may choose different transition functions)

3-Do we need require that all branches halt for $M(x)=1$?

Finally, how can we use this definition to solve a function problem or a search problem?


texts:
Given N finite subsets of the finite universe set E, it is necessary to find the intersection which contains maxumum number of subsets. Let call this problem MSI (Maximum Subset Intersetion).

Firstly I had thought that it is variation of well-known Maximum Clique Problem where vertices are subsets and edges are relations of intersection, so the classic Bron-Kerbosch algorithm or Tomita et al. algorithm can be easily used. But the k-size clique is certainly not the same that the mutual intesection of k subsets (cause subset A can intersect B, B can intersect C, A can intersect C, but at the same time A, B and C may not have common points of intersection).

Actually the multiple intersections form edges in hypergraph, so the main task is to find edge of maximal cardinality.

I found an article by Eduardo C. Xavier A Note on a Maximum k-Subset Intersection Problem
 where he proves that the MSI-problem is a variation of Maximum Edge Biclique (MEB) problem which is in turn NP-hard.

My naive solution is to implement branch and bound greedy algorithm (in other words, to adopt Bron-Kerbosch algorithm to this domain).

May be there are already any implementations or acadimic paper on that problem?

EDIT:

Actually the exact problem I met in my work is the following:

Suppose that I can run some function which returns the cardinality of one subset or N subsets intersection. The function is time-consuming. I am interested in finding optimal or approximately optimal argorithm to find the intersection of maximum number of subsets (next thing is to find the whole set of such intersections in cardinality decreasing order).
Working on element-level is even more costly from the time consumption point of view.

I thought firstly to take cardinalities of all subsets (N operations) and then run Bron-Kerbosh kind of search for subsets sorted by cardinality decreasing order. So I will start with the largest subset, check if it intersects with the 2nd largest subset and so on.


texts: Load and Store Data hazard problem in 5-stages pipeline

texts:
Hi everyone and first of all thank you for been reading.
I'm a little confused about data hazard dependences when a "Store" instruction is followed by a "Load" instruction.
(Assume that we're working with a 5 stages pipeline processor withouth data forwading paths)

So if I have the following code now:

Store R3,R8,off-1
Load R3, off-2

If we've had ADD and Subsract instructions instead of "store" and "load" we'll have data hazard dependences, so we would have to "wait" for the result using No-Op, but in this case; can I start "fetchig" the second instruction while the first one is on "Decode" stage?

I think I'm missing some concepts here, as to where the operand is fetched from and where it gets stored to.

Thank you.


texts: Why aren't primality tests easily linear in time complexity?

texts:
Why don't we consider them as linear? I don't understand. You just have to check for factorization up to sqrt of n.  So it's even faster than linear.
I assume it's not linear only if we compare the number of operations relative to the input in terms of binary representation.  But why would we do so?
It seems to me wrong.  The growth in calculation should be calculated compared to the number itself.  Why do we compare it to the binary representation?


texts: Big O of rational function using the definition

texts:
I want to prove that $\dfrac{3x^3+2x^2+x+1}{4x^2+1}$ is $O(x)$.

I am having problem in finding $c$ and $k$ and proving that it is big O, since the function involves a fraction.

How would I go about doing this?


texts: What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)

texts:
I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as
$(0+0001)((1111)^*+(00)^*)$

What is the length of the longest string that cannot be pumped?
What is the length of the shortest string that can be pumped, I think this will come naturally when we find the $p$ (the pumping length).

The pumping length of a regular language $L$ is the minimal $p$ such that every word $w \in L$ of length at least $p$ can be split as $w = xyz$ such that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (iii) $xy^iz \in L$ for every $i \geq 0$.
As per the answer https://cs.stackexchange.com/a/83727/33673, can we chose $y$ (the middle term in $xy^iz$ to be $1111$ in this case?


texts:
Doing exam papers now and I came across two questions which I cannot get my head around sadly. Both are regarding Amdahl's law and Parallel Computing but they seem rather simple and frustratingly enough I cannot really find a definitive answer to any of those questions.
The questions are:

Why must Amdahl's law always apply to a computation?
Why is the existence of superlinear speedup not in contradiction with Amdahl?

The best description of Amdahl's law I found is this one:

At the most basic level, Amdahl's Law is a way of showing that unless a program (or part of a program) is 100% efficient at using multiple CPU cores, you will receive less and less of a benefit by adding more cores. At a certain point - which can be mathematically calculated once you know the parallelization efficiency - you will receive better performance by using fewer cores that run at a higher frequency than using more cores that run at a lower frequency.

I just cannot find a suitable answer on why the law must be always applied to a computation. And superlinear speedup is just when a parallelised speedup can reach far beyond the speedup of a sequential processor. How would it actually contradict Amdahl's law I do not really know apart from it looking a bit like a glitch in the matrix.


texts:
This is a puzzle about measuring network latency that I created. I believe the solution is that it's impossible, but friends disagree. I'm looking for convincing explanations either way. (Though it is posed as a puzzle I think it fits on this web site because of its applicability to the design and experience of communication protocols such as in online games, not to mention NTP.)

Suppose two robots are in two rooms, connected by a network with differing one-way latencies as shown in the graphic below. When robot A sends a message to robot B it takes 3 seconds for it to arrive, but when robot B sends a message to robot A it takes 1 second to arrive. The latencies never vary.

The robots are identical and do not have a shared clock, though they can measure the passage of time (e.g. they have stop watches). They do not know which of them is robot A (whose messages are delayed 3s) and which is robot B (whose messages are delayed by 1s).

A protocol to discover the round trip time is:

whenReceive(TICK).then(send TOCK)

// Wait for other other robot to wake up
send READY
await READY
send READY

// Measure RTT
t0 = startStopWatch()
send TICK
await TOCK
t1 = stopStopWatch()
rtt = t1 - t0  //ends up equalling 4 seconds

Is there a protocol to determine the one way trip delays? Can the robots discover which of them has the longer message sending delay?


texts: How do I prove that the Perceptron bound for mistakes is tight? I need to prove that for any amount of given data points, the total amount of updates (mistakes) that the algorithm will make is $\frac{1}{\gamma ^2}$, where $\gamma$ is the margin. I know that I'll have to make it such that for a given $m$ number of data points, I'll make it such that $\gamma = \frac{1}{\sqrt{m}}$, but I'm not really sure how to continue and would appreciate a hint in the right direction.


texts: Do forward chaining (Rete) business rules (Drools, ILOG) / production rules support higher order rules and compositionality?

texts:
There is this talk http://andrewcropper.com/pubs/jelia19-typed.pdf about higher order Prolog, about use of higher-order predicates (that takes other predicates as arguments) and compositionality of predicates. All that is about Prolog and backward chaining inference.

My question is: do business rules (Drools, ILOG), production rules and Rete algorithm support higher order business rules. Simple business rule is:

if x=5, then y=6

Higher order business rule may be (as I understand, please, correct me, if I am wrong)

if rule P fired then rule R comes into force

This seems to be quite applied question (more appropriate for stackoverflow), but I am asking this about the possibility of higher order expressivity for production rules and about possibility of Rete algorithm for handling such extensions? Maybe other algorithm is necessary?

I also remember that there was extensive PhdThesis about formal semantics (especially about Hoare logic) for IBM ILOG JRules - that would be great reference here - but I can not find to add it here. If I could gind, I would have added it here to show that business rules/production rules are quite interesting from the computer science (not only programming) point of view as well. And that there are challening issues.


texts: Finding the language of a context-free grammar?

texts:
Given following question:

Let $G$ be a context-free grammar, $G=(V, \Sigma, R, S)$, that has start
variable $S$, set of variables $V = \{S\}$, set of terminals $\Sigma = \{0, 1\}$, and set of rules $R = \{S \rightarrow \epsilon , S \rightarrow 0 , S \rightarrow 1 , S → 0S0 , S \rightarrow 1S1\}$. Describe $L(G)$,
the language of the grammar $G$.

I know that $\epsilon, 0, 1, 00, 11, 010, 101, 01010, 10101, 10001, 01110$ all fit the grammar, but I can't find a formal way to express what I want to say. Perhaps I don't know the symbols or something, but I would express it as

$L(G) = \{(0\ or\ 1)^n(0\ or\ 1)^{(0\ or\ 1)}(0\ or\ 1)^n,\ n \ge 0\}$

Is this right? Is there a more formal way to express this?


texts:
I have been trying to implement a Van Emde Boas tree in python, but I'm having trouble understanding how exactly it works. In the notes here, It states that the summary of a VEB structure is another VEB structure, and the individual clusters are also VEB structures. Does that mean that the individual clusters than also contain smaller individual clusters that are VEB structures and so on as well? This is my code to implement the clusters.

class VanEmdeBoas():
def __init__(self, size):
    if size <= 0:
        raise ValueError('Invalid size of universe!')
    self.size = 4
    while size > self.size:
        self.size = self.size * self.size
    self.min = None
    self.max = None
    self.clusters = [VanEmdeBoas(math.sqrt(self.size)) for i in range (int(math.sqrt(self.size)))]

Doing this results in the error "maximum recursion depth exceeded". Intuitively this fails because the recursion never stops, so does this mean my understanding is flawed?


texts: Big O Proof , f(n) = 2n + 1 and I have to prove f(n) is O n^2

texts: If I have $f(n) = 2n + 1$ and I  have to prove $f(n) \in O(n^2)$, by proving there exists positive constants $c$ and $n_0$ such that $f(n)<cn^2, \forall n\ge n_0$, can I do this all in one step by putting in values of $c$ and $n_0$ at once or do I have to put in values of c first and then get n on one side and put in values for $n_0$, the for all $n \ge n_0$ confuses me.


texts: A real-world example for a kind of real-time applications

texts:
I submitted a paper regarding hard real-time systems to an engineering journal. But the referees generally agreed my task model is too limited. My task model is a frame-based real-time application where all the tasks in the application have a common deadline D and are independent from each other. In the following Figure you can see a model of this application.

The tasks T1 to T5 are independent from each other and have common deadline D.

  "Independent" means that order of the tasks execution is flexible (is
  not important) or the tasks can be executed concurrently.

There are related works that have considered this type of real-time application, but none of these works include any real-world examples.  The referees said that to convince the readers I must provide some real-world examples of this kind of application.

Does anybody know a real-world example for this kind of real-time application?


texts: Complexity of STRIPS planning for finding optimal solution: PSPACE-complete or NP-complete?

texts:
I am reading the two articles below to try to figure out whether STRIPS are NP-complete or PSPACE-complete. Specifically, I am trying to figure out the complexity of finding optimal solutions using STRIPS.

Also, Bylander (1994) defines PLANMIN to find the shortest plan. This is tied to length directly where minimizing plan length is the objective. I'm not sure if I can apply his reasoning to my situation. I use a objective function other than length, for which I need to find the entire plan before calculating its utility, then find a plan that minimizes that utility. So I can't simply stop my search and backtrack if I find a plan longer than the shortest one I have found so far. Does this condition make this search NP-complete?

Thank you in advance.

Bylander, T. (1994). The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1–2), 165–204. https://doi.org/10.1016/0004-3702(94)90081-7

Erol, K., Nau, D. S., & Subrahmanian, V. S. (1991). Complexity, Decidability and Undecidability Results for Domain-Independent Planning: A Detailed Analysis, 76(CS-TR-2797), 75–88.


texts: What is the language feature which allows a variable to be associated with values of different types?

texts:
In Python,  I can change the types of values associated with a variable:

>>> x=1
>>> x="abc"

In C, I can't do the same.

What is the name of the feature that allows Python to behave so, while not C?

I was wondering if the following language features have to do with  the observation in Python:

no explicit type annotations,instead of explicit type annotations
dynamic typing, instead of static typing
or reference model of variable, instead of value model of variables?

Thanks.


texts:
I am looking for the name (definition?) of X in:

A regular expression is X iff it has exactly one possible match.

Examples: <empty regex>, abc, \., [.], a|a, a{8,8}, \Q.*?\E
Counterexamples: ., a*, a|b, \d, a?
I would call such a regex constant. Can I use this name? Is there a similar concept?

Additionally, I would say a regex is literal iff it is constant and the single match is equal to the regex itself (f.e. a but not [a]).
NB: I would greatly appreciate some references, because I would like to cite them.
Research done:
Check if a regex is ambiguous uses "ambiguous" but in another way ("a string can be matched by more that one ways from 1 regex")
I have asked it on math SE but was redirected here.