texts: Showing a problem on a specific graph is NP-hard

texts:
Maybe there is a trivial answer to my question or maybe there is not any. But I ask it here and appreciate if anyone can give me a clear answer.

We know that a set of problems like minimum clique cover problem, coloring problem, vertex cover, ... are NP-hard for general graphs, but maybe polynomial-time solvable for specific graphs.

My question is that, if we are given a graph $G=(V,E)$ (I am asking this generally but you can specifically assume the graph described here), and want to find for example minimum clique cover for this graph, how can we show that it is NP-hard (if it is)? Is there any method for that?


texts: Finding $d$ in RSA Encryption mathematically and by hand

texts:
I'm working on this RSA encryption problem and the catch is that it must be done by hand and mathematically.

Let's say $p=11$, $q=13$
$$N=p \cdot q=11 \cdot 13=143$$
I chose $e$ to be relatively prime to $(p-1)(q-1)$, $e=23$
So the public key is $(23,143)$

Now I want to find out $d$ and for that I've come across $2$ different methods. First is using this formula
$$23 \cdot d \equiv1 \mod120$$ where I can't seem to work out what $d$ is. I tried to solve it like a quadratic equation $$23x=1 \mod 120$$
$$x=\frac {1}{23}$$ which doesn't make sense. Then I came across this other method to find the value of $d$.

$$∃k : e \cdot d +k(p-1)(q-1) \equiv1$$
$$23 \cdot (47) + (-9)\cdot120=1$$ So the private key would be $(47,143)$ but there is no mention of how they figured out the value of $d$ and $k$. That's why I need some help to work out the value of $d$ in a way so that I can find it given any problem.


texts: How do I construct reductions between problems to prove a problem is NP-complete?

texts: I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How should I approach a problem that asks me to prove a problem is NPC?


texts: Is safety-critical software a subset of real-time software?

texts:
I would like to refute my hypothesis that all safety-critical software (that is, software where errors can have catastrophical consequences, either in terms of human lives or high material costs) is a real-time software (where tasks have timing constraints) by finding interesting counterexamples: systems without timing constraints which are safety-critical.

I tried thinking of several examples, but they always seem somehow related to some physical system (e.g. flight control, radiation therapy, nuclear power) and therefore have some implicit timing constraints/deadlines. Even somewhat contrived "safety-critical" systems such as high-frequency trading are still real-time.

Note: I am not interested in a very specific subset of the code which is timing independent, but on something more complete, consisting of a substantial part of a complete application.


texts: What would the truth table for a finite state machine showing transitions of flags in a nascar race look like?

texts:
I'm trying to construct a truth table from a finite state machine of flags in a NASCAR race.

Flag meanings: green=start yellow=caution red=stop black=get off white=one lap left checkered=finish line

In an example with a stoplight in class, the variable that makes the current state go to the next state on the stoplight is a timer. So the truth table looked like this:

Timer    current state    next state
0            red              red
1            red              green
0            green            green
1            green            yellow
etc...

For a NASCAR Flag FSM would the variable be whatever is causing it to go to next state, since there isn't a timer involved(?)?

For example, would this be correct?

variable      current state            next state
crash             green                     yellow
stop race         green                     red
get off track     green                     black
1 lap left        green                     white
race over         white                     checkered


texts: Exponential nested Loop Big O complexity calculation

texts:
Can I get a bit of help over here, I can't seem to get to a finish point with this code complexity. I have trouble with making notations, exponential ones in particular..... I spent hours with this particular piece of code to get BIG O but i can't mathematically..... I'm a newbie.

I tried to logarithmate the whole thing like:
j= n, n^(1/2), n^(1/4), ........, 2
then:

j= log (2,n), log(2, n^(1/2)), ..... log (2, (n^(1/2))^K) need to find out K from this notation

If i try to sum them up: log(2,n) + 1/2*log(2,n) + 1/4*log(2,n) + ..... + (1/2)^K * log(2,n)

then:

log(2,n) * [1/2 + 1/4 + ....... + (1/2)^K]
The number of terms this sum has should give me the number of steps for j
I can't proceed to i without it but i get stuck right there at that sum at this point and i get lost from here.....

I also made a piece of code to count the steps and have a better view here are the results for

n = 1000

for j: 1000   i: 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1,   steps: 10

for j: 31   i: 31, 15, 7, 3, 1,   steps: 5

for j: 5   i: 5, 2, 1,   steps: 3

for j: 2   i: 2, 1,   steps: 2

n = 65

for j: 65   i: 65, 32, 16, 8, 4, 2, 1,   steps: 7

for j: 8   i: 8, 4, 2, 1,   steps: 4

for j: 2   i: 2, 1,   steps: 2

for (int j=n; j>1; j=sqrt(j))
       for (int i=j; i>0; i/=2)
             k++; // O(1)


texts: Distribute objects in a cube so that they have maximum distance between each other

texts:
I'm trying to use a color camera to track multiple objects in space. Each object will have a different color and in order to be able to distinguish well between each objects I'm trying to make sure that each color assigned to an object is as different from any color on any other object as possible.

In RGB space, we have three planes, all with values between 0 and 255. In this cube $(0,0,0) / (255,255,255)$, I would like to distribute the $n$ colors so that there is as much distance between themselves and others as possible. An additional restriction is that $(0, 0, 0)$ and $(255, 255, 255)$ (or as close to them as possible) should be included in the $n$ colors, because I want to make sure that none of my $(n-2)$ objects takes either color because the background will probably be one of these colors.

Probably, $n$ (including black and while) will not be more than around 14.

Thanks in advance for any pointers on how to get these colors.


texts: Why is there only a polynomial number of provers in multi-prover interactive protocols?

texts:
The paper On The Power of Multi-prover Interactive Protocols by Fortnow, Rompel, Sipser states the following:

There are provers $P_1, P_2, \dots, P_k$ in a multi-prover interactive proof system such that $k$ is polynomial in the size of the input. The value of $k$ cannot exceed a polynomial because this would prevent the verifier in the system from accessing all the provers.
In one round a verifier can interact with more than one prover.

Since a verifier can interact with more than one prover in one round, is the real reason that the number of provers must be polynomial due to the fact that the total length of the messages to all the provers in one round must be polynomial in the length of the input?


texts:
The Monster M is the largest of the finite sporadic groups that arises in the classification of finite, simple groups in mathematics.

M can be realized as a (very large!) set of 196882 X 196882 matrices with nothing more than entries of 1's and 0's, so long as we compute arithmetic as follows:

1+1=0
1+0=1+0=1
1*1=1
0*0=0
1*0=0*1=0

I have two simple questions for the reader. What is the minimum amount of bytes needed to store a single matrix? What is the computational cost (i.e., in FLOPS) of a single matrix multiplication in the most efficient implementation (i.e., taking into account that the entries are binary, not taking into account mathematical properties about the Monster)?

This is a question purely at the computational side of the problem. In other words, treat the matrices as general 196882 x 196882 matrices with binary entries. This is not a question about the Monster. That was just added as motivation.


texts: Converting Mathematical Statements to SAT Formulas

texts: Is it possible to write a mathematical statement (like Goldbach's conjecture, for example) as a nontrivial 3-SAT formula that is satisfiable iff that statement is true? iff it is false? iff it is independent of the axioms of ZFC? So, for any statement, you would have (at most) 3 formulas, for which only one can be satisfiable. Is there any work in this field (you can use the Pythagorean Theorem as a more simpler example)?


texts: Genetic algorithm: What is the expected number of strings that are explored?

texts:
My question concerns genetic algorithm searching along bit strings.

Given:

$N$ = population size
$l$ = length of bit strings
$p_c$ = probability that a single crossover occur (double crossover never occur)
$p_m$ = probability for a given bit that a mutation occur

$w(x)$, the fitness function is equal to the number of 1 in the strings. Therefore, the fitness can take any integer value between 0 and $l$ (the length of the strings).

My question is (three ways of formulating the same question):

What is the expected total number of possibilities explored in $G$ generations?

or

What is the expected proportion of the total possibility space (which equals $2^l$) that is explored in $G$ generations?

or

What is the expected size of the subset of strings that have ever existed in the population during a simulation that last $G$ generations?

Secondary questions:

How does the frequency distribution - of the total number of possibilities explored in $G$ generation - looks like?

is it a normal (Gauss) distribution?
Is it skewed?
...

I don't quite know how complex is my question. Here are two assumptions that one would like to consider in order to ease the problem.

one might want to assume that the population at start is not randomly drawn from the possibility space. He could assume that the whole population is made of identical strings (only one instance). For example, the string 000000000 (which length equals $l$).
one might want to assume that $p_c = 0$


texts: I am wondering if deciding the decidability of problem is a decidable problem. I am guessing not, but after initial searches I cannot find any literature on this problem.


texts: Why do we proof the halting problem with turing machines?

texts:
It can be shown that Turing machines, μ-recursive functions and reasonable programming languages can compute/decide the same problems. I wonder why we then still proof the halting problem with Turing machines.
Isn't it much easier to argue that the function halts below cannot exist in e.g. python since then I would be able to write the following program which is a contradiction.
def halts(source):
  ...

if __name__ == "__main__":
  this_file = open(__file__)
  if halts(this_file.read()):
    while True:
      pass
  else:
    return 1

Why is this proof not as good as the TM diagonal argument?
Edit: I read https://cs.stackexchange.com/a/94235/119946

OK, fine. This proves that the halting problem can't be solved for
code written in any programming language that has a
get_source_code_of_current_function() API. However, my favorite
programming language doesn't have such an API. So, this proof doesn't
prove anything about my favorite programming language -- perhaps the
halting problem is solvable for my language, who knows? Similarly,
Turing machines don't have such an API, so this doesn't prove that the
halting problem for Turing machines is undecidable.

I mean by that argument I can say the TM proofs only shows that the halting problem cannot be decided by Turing machines, but does not show anything about python. Isn't the crucial part, that (as I wrote) TM and modern programming languages can compute/decide the same problems? If one can decide the halting problem, then all other can do so as well and vice versa.


texts: Learning the weights in a directed acyclic graph

texts:
I have a directed acyclic graph $G=(V,E)$ where each vertex $v$ is associated with a weight $w_v$ such that  $$w_v=1+\sum\limits_{(v,v')\in E} w_{v'}$$ and $w_v=1$ in case $v$ is a leaf.

I am trying to construct $G$ and the weights or at least the weights. The information that is available to the system can be anything useful for starting the construction. Though one interesting information is of type $v$ is a possible ancestor of $v'$. I am interested in similar problems exists in the literature for further reading and understanding. Appreciate any pointers.


texts: Isn't the given characterisation of recursively enumerable subsets of the class of all recursively enumerable languages?

texts:
$S$ is a subset of the class of all recursively enumerable languages over some finite symbols then $S$ is recursively enumerable iff

If $L$ is in $S$ and $L'$ is a language such that $L ⊆ L'$ and $L'$ is recursively enumerable, then $L'$ is in $S$
If $L$ is an infinite language in $S$, then there exists at least one finite subset of $L$ that is in $S$
The set of all finite languages in $S$ is enumerable, i.e. a Turing machine can list all the finite languages in $S$

Source of the statement: https://cs.stackexchange.com/q/2322 and some online notes

Isn't the 3rd one contradictory to the 1st one?


texts: Set containment of MinimumBadPrefix and BadPrefix of a Safety Property

texts:
This question is related to formal model checking theory, but I cannot find a tag for it.

Let $P_{safe}$ be a safety property.

$BadPref(P_{safe})$ is the set of bad prefixes for $P_{safe}$

A Safety property $P_{safe}$ over Atomic Proposition $AP$ is regular
if its set of bad prefixes is a regular language over $2^{AP}$

Is the following true?

If $L$ is a regular language with $MinBadPref(P_{safe}) \subset L \subset BadPref(P_{safe})$,
then $P_{safe}$ is regular.
If $P_{safe}$ is regular, then any L for which
$MinBadPref(P_{safe}) \subset L \subset BadPref(P_{safe})$ is regular.

My attempt to 2. is that it's true

$P_{safe}$ is regular then $MinBadPref(P_{safe})$ is regular and so is $BadPref(P_{safe})$. A NFA $N$ recognizing $BadPref(P_{safe})$ can be obtained by adding self loops on the final states of the NFA $M$ recognizing $MinBadPref(P_{safe})$. And $L$ is recognized by some NFA containing a subset of the self loops added to $M$. Therefore $L$ is regular.

And what about 1.?


texts: Solving Recurrence relation with master method?

texts:
I have to solve the following recurrence equation and I thought to solve it with case #3 of the master theorem. Can I do that?

$$T(1) = c>0 $$
$$T(n) = 9T(n/3) + f(n)$$
$$f(n) = n^2\cdot lg^3 (n) + n^3 \cdot lg(n)$$

I think that $f(n) = \Omega(n^{log_ba})$ where $a=9, b=3$ so $n^{log_ba}=n^2$.

Since  $f(n) = n^3 lg(n)$, we can prove that $$a\cdot f(n/b) \leq c\cdot f(n)$$.

Is it a correct solution?

The only piece I am afraid could be tricky is proving $a\cdot f(n/b) \leq c\cdot f(n)$.

Thank you,
Alan


texts: How to show that this decision problem is in co-NP?

texts:
Given a set of strictly positive numbers $a_1, ..., a_n$, the problem is to determine if $\lfloor n/2 \rfloor$ different indexes $i_1, ..., i_{\lfloor n/2 \rfloor}$ exist so that $$\frac{a_{i_j}}{a_{i_{j-1}}} = \frac{a_{i_{j+1}}}{a_{i_j}}$$ for $2 \leq j \leq \lfloor n/2 \rfloor$.

How to show that this problem is in co-NP ?


texts:
Suppose we are given a matrix $A$ over real numbers and we want to computer the inverse of matrix $A$. There are various algorithms to do so and it also turn out that we can use matrix multiplication problem to solve matrix inversion problem.

My question:  How to prove that matrix inversion is at least as hard as matrix multiplication?


texts: Help coming up with a solution to a combinatorial problem

texts:
So here is the problem:

Say I want to find the only possible combinations to find the sum of a specific number using only the numbers 1, 2, & 3 with a specific number of additions.

I know this sounds confusing, but let me give an example:

Say we were trying to find the number of possible combinations to add up to the number 6 using, as stated above, only the numbers 1, 2, & 3 with exactly 2 additions.

The solution is easy:

Since we are trying to add up to 6 using exactly 2 additions with the only three numbers we are allowed to use (1, 2, & 3), we only get: {3 + 3}.

Similarly, If we were trying to find the number of possible combinations to add up to the number 4 with exactly 2 additions we get: {1 + 3} & {2 + 2}.

So, I am asking is there an algorithm out there that I can use to solve this when the numbers get bigger? Is there a clever way to solve this with code? I've been thinking about this for a while and can't seem to solve it.

Thanks!


texts:
hi i know that the question 5 is true because by definition  w ∈ L if and only if δ*(q0,w)∩F ≠ ∅. Consequently, if δ∗ (q0,w)∩F = ∅, then w ∈ L1. "L1 is the complement of L"

but iam really confused about the question 6 our teacher told us that it's false but i think it's true  because i don't see any difference between the 2 questions

i get this picture from peter linz book : An-Introduction-to-Formal-Languages-and-Automata


texts: reinforcement learning in gridworld with subgoals

texts:
Andrew Ng, Daishi Harada, Stuart Russell published a conference paper entitled Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping.

There is a specific example there that I am extremely curious/interested about. It is in Figure 2(a) of the paper:

It is about a 5x5 gridworld with start and goal states in opposite corners. The catch is, the agent must learn to go from start to end BY VISITING specific subgoals 1,2,3,4 IN ORDER.

Has anyone seen/understood the code for this? I want to know how the reward function/shaping is given in this kind of problem.

I am interested to know how the flow of this modification to the grid world is written.


texts:
In the wiki article about closures one can read:

  closure ... is a function or reference to a function together with a
  referencing environment

At the same time in the wiki article about class methods:

  Accessor methods are used to read data values of an object. Mutator
  methods are used to modify the data of an object.

So, can I say that data is environment and class methods (accessors and mutators) are closures?


texts:
May be this question is really silly and obvious but I am missing something subtle. I am reading on Sensitivity and Block sensitivity.

Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function.

Let $[n]=\{1,2,\dots,n\}$.

If $i\in[n]$, let $\Bbb 1_i$ be length $n$ vector with all $0$s except $1$ at $i$th position.

If $B\subseteq [n]$, then $\Bbb 1_B$ be the length $n$ vector with $1$s only in positions marked by $B$.

If  $i\in[n]$ and $x\in\{0,1\}^n$, let $x^i=x\oplus\Bbb 1_i$ where $\oplus$ is $XOR$ operation.

If  $B\subseteq [n]$ and $x\in\{0,1\}^n$, let $x^{B}=x\oplus\Bbb 1_B$ where $\oplus$ is $XOR$ operation.

Sensitivity of $f$ at input $x$ is $$S_x(f) = |\{i:f(x)\neq f(x^i)\}|$$

Sensitivity of $f$ is $$S(f)=\max_xS_x(f)$$

Block Sensitivity of $f$ at input $x$, $BS_x(f)$ is maximum $r$ such that there is a set of disjoint subsets $\{B_i\}_{i=1}^r$($\forall i\neq j$, $B_i\cap B_j=\emptyset$) such that  $$\forall j\mbox{, }f(x)\neq f(x^{B_j})$$

Block Sensitivity of $f$ is $$BS(f)=\max_xBS_x(f)$$

It is clear that $S(f)\leq BS(f)$ since we can take size $1$ blocks at coordinates of input $x$ that are modified to achieves $S(f)$.

So why can't I say $BS(f)\leq S(f)$? That is, suppose we found a maximum set of blocks $B_i$ that are disjoint, then cant I say:

There is no other bit position outside of $\cup_{i=1}^rB_i$ where we can change an input in order to change the input (Or else there is a size $1$ block that is disjoint and we can add to list $B_i$ incrasing $r$).
It is clear $S(f) = |\cup_{i=1}^rB_i|$ since if we change all bit positions in $B_i$ we change inputs and there is no other extra bit position by $1$.
Split the $B_i$ in to size $1$ blocks to get $S(f)=BS(f)$?

Am I wrong in the definition that $2$ DOES NOT HOLD since we can only consider $1$ block at a time and hence we can only say $S(f)\geq max_i|B_i|$? Anything else I am missing?

Is there any example for which $BS(f)\leq S(f)^{1+\epsilon}$?


texts: Characterization about Kleene Closure, when is a language $L=L^*$?

texts:
I'm trying to find a characterization of when $L=L^*$.
I think I have one, but maybe is trivial, but I don't know if the proof is correct.
Claim: $L=L^* \Leftrightarrow L=LL$.
Proof:
If $L=L^*$ then is easy to see $LL \subseteq  L$ so $L=LL$.
The other implication is in which I have doubts, I used a simple chain of equalities
$$L=LL=\cdots=L^n=\cdots= \bigcup_{i\geq 0}L^i=L^*.$$
I would like to know if there is something wrong and specially if there's another characterization which is less trivial.


texts:
What are the significant applications of minimum spanning trees?

After doing some research online and in several textbooks, I have found three real-world applications:

Building a connected network.  There are scenarios where we have a limited set of possible routes, and we want to select a subset that will make our network (e.g., electrical grid, computer network) fully connected at the lowest cost.
Clustering.  If you want to cluster a bunch of points into $k$ clusters, then one approach is to compute a minimum spanning tree and then drop the $k-1$ most expensive edges of the MST.  This separates the MST into a forest with $k$ connected components; each component is a cluster.  (I confess I'm not very clear on whether anyone uses this clustering method in practice, and if so, what domains it is useful in.)
Traveling salesman problem.  There's a straightforward way to use the MST to get a $2$-approximation to the optimal solution to the traveling salesman problem, and the Christofides' heuristic uses MSTs to get a $1.5$-approximation.  (One could reasonably question how real-world this is, though, as there are other approximation algorithms for the traveling salesman problem that will typically do even better in practice.)

I have found vague references to other applications, but I have not found details.  Are there other significant real-world applications of minimum spanning trees, and if so, how do they work?


texts: Measuring the hardness of SAT instances Lemma

texts:
I am reading the paper Measuring the hardness of SAT instances by Ansótegui, Bonet, Levy and Manyà (Proc. 23rd AAAI Conf. on AI, pp. 222–228, 2008) (PDF).I have two questions the first one is I would like to undersatnd the demonstration for the last claim. Specifically I need an example of the proof tree of $[x\rightarrow b](\Gamma)\vdash \{\Box\}$. And the second one is I would like an example of the last part of the Lemma 3, that is an example of the definition $s(\Gamma)$.

  Lemma 3 The space satisfies the following three properties:

  $s(\Gamma \cup \{\Box\})$ = 0
  For any unsatisfiable formula $\Gamma$, and any partial truth assignment $\phi$, we have $s(\phi(\Gamma))\leq s(\Gamma)$.
  For any unsatisfiable formula $\Gamma$, if $\Box\notin\Gamma$, then there exists a variable $x$ and an assignment $\phi\colon\{x\}\to\{0,1\}$, such that $s(\phi(\Gamma))\leq s(\Gamma)-1$.

  The space of a formula is the minimum measure on formulas that satisfy (1), (2) and (3). In other words, we could define the space as:3

  $$s(\Gamma) = \min_{x, \overline{x}\in\Gamma, b\in\{0,1\}} \big\{
\max\{s([x\mapsto b](\Gamma))+1, s([x\mapsto\overline{b}](\Gamma))\}\;\big\}$$
  when $\Box\notin\Gamma$, and $s(\Gamma\cup\{\Box\}) = 0$.

  3 Note that, since $\Gamma$ is unsatisfiable, it either contains $\Box$ or it contains a variable with both signs.

I trying to understand the proof of that Lemma using this UNSAT formula: $\Gamma = (a+b)(a+b')(a'+c)(a'+c')$. Specifically, in this point:  "From the proof tree of
$[x \rightarrow b](\Gamma) \vdash\{\Box\}$ , adding the literal $x'$ in the clauses where
$[x \rightarrow b]$ has removed it, but preserving the structure of the
proof tree, we get a proof of $\Gamma \vdash x'$". I consider $x=a=1$ then replacing $a'$ in the formula $[a\rightarrow 1](\Gamma)$ I get $(a'+b)(a'+b')(a+c)(a+c')$ that also by resolution is $\{\Box\}$. What is wrong in my example How Do I get $\Gamma \vdash x'$?

*$\{\Box\}$ means the empty clause


texts: How would you identify the size of a circular turing tape?

texts:
Came across this interesting problem in one of my interviews. Suppose you have a circular turing tape, i.e. simply a circular array. You do not know the size i.e. the number of cells available in that circular array.

The array consists only of binary digits. Lets say you are currently at one of the cells. You can read and write on the current cell you are on. You can rotate the array towards the left or right, and you have a counter with you which tells you how far away are you from the original cell that you started off with. So if you go right by x units, the counter will read x units and -x if you go x units to the left. However, you cannot store the value of previous cells you encountered. You may have at max only one unit of external memory at your disposal. For example, if you are at +x, you could compare the value at that +x with the one value you have stored in the external memory. Given that currently all the cells have been randomly assigned either a 0 or a 1.

How would you identify the size of this circular array?


texts:
I'm interested in such problem. I have a set of $n$ tasks ${T_i}$ and directed acyclic graph, which nodes correspond to tasks and edges correspond to order of execution two tasks. In other words if I have edge $T_i \rightarrow T_j$ it means that task $T_i$ should be executed in day which strictly before day of execution $T_j$. All tasks should be executed within $m$ days, every task should be executed exactly once. Execution of task $T_i$ in day $j$ costs $C_{ij}$ dollars. There is no restriction on number of tasks executed in one day. I should minimize total cost of execution all tasks.

Can one solve this problem in polynomial time?

My idea is only to bruteforce topological sorting and dynamic programming then, but it is too slow.

ADD: I can solve problem, when given DAG is forest. It can be done by simple dynamic programming, where states are $(T_i, j)$, which means that $T_i$ is executed in day $j$ and subtree tasks are executed within constraints.

ADD: I've read this paper, 13.3 Layer Assignment, p. 417.
Also this problem can be formulated in terms of weighted CSP, we need to minimize such value $\sum\limits_{v \in V}C_{v \sigma(v)} + \sum\limits_{(u,v) \in E} D_{\sigma(u)\sigma(v)}$, where $\sigma(v)$ is day when task $T_v$ is executed, $D_{ij} = \begin{cases} 0 &\mbox{if } i < j \\
\infty & \mbox{if } i \ge j \end{cases}$.


texts: Is it possible to get Nth Fibonacci number in sublinear time?

texts:
I was researching the topic of Fibonacci numbers and asymptotic complexity of generating them. Coming across a seemingly paradoxical conclusion, I've decided to check out if you agree with my explanation.

The naive algorithms runs in $O(n)$, if we ignore the cost of addition.
The Binet's formula or matrix exponentiation method should both theoretically run in $O(\lg(n))$ (since exponentiation of both matrices and real numbers takes $O(\lg(n))$ steps)

The problem arises when you analyze the size of Nth Fibonacci number by assuming that after first few members of the sequence, the ratio between two numbers is at least 1.5 (picked randomly, I assume it can be easily proved by induction).

We can then bound the number to be at least as big as: $c_1*(1.5)^n$.
Its logarithm gives us the number of digits the Nth Fibonacci number has ($c_2*n$).
Am I right to assume that you can't print out (or calculate) linear number of digits in sublinear time?

My explanation of this "paradox" is that I forgot to add multiplication costs in 2nd algorithm (Binet/matrix), making its complexity $n*\lg(n)$.
I've found out that naive algorithm (1st) runs better for very small inputs, and 2nd algorithm runs better for bigger ones (python3).

Is my explanation of complexity correct, and should the naive algorithm get better running time at even larger inputs ($n>10^9$ or such)?

I do not consider this to be a duplicate question, since it adresses the problem of arbitary values and arbitary integer aritmetic.


texts:
There is a square table composed of N*N Cells. Initially all cell is filled with a number 0.
Two types of Operations can be performed on the table.

R i k: All the numbers in the cells on ith row has been changed to k.

C i k: All the numbers in the cells on ith column has been changed to k.

Please Note : k ∈ {0, 1} (ie k = 0 or 1).

At any time ,Alice is interested to know  the total number of 0's on some row or total number of 0's on some column.

Our task is to answer Alice Query.

Input

First line contains a single integer N as described above.Next line contains a single integer Q representing the total operations and queries from Alice.
Then Followed Q lines , containing operations or queries in following format:

R i k: All the numbers in the cells ith row has been changed to k.

C i k: All the numbers in the cells ith column has been changed to k.

qc i :How many 0's are there in ith row?

qr i:How many cols are there in ith col?

Examples:
Input:

3

6

qr 1

C 1 1

qr 1

qc 1

R 1 0

qc 1

Output:

3

2

0

1

I tried a Naive solution.But it got time out. The constraint is quite large and the time limit is just 0.55 Seconds.

**1 ≤ N, Q ≤ 500000 (6 * 10^5)

How can i solve this problem within the given time-limit?

P.S: This is not a homework.


texts:
In order to prove that SAT is in NP, I need to come up with a polynomial time verfier (an algorithm). The Cooks Levin Theorem uses a non-deterministic Turing machine but that's not what I am looking for.
The idea of the algorithm could be that we put in the values and calculate the answer. Then, we check whether the answer is 1 or not. However, I am unable to understand how I could write a psuedocode for the 'putting in values' part and then show that it's polynomial for sure.
if x = 1:
 accept
else:
 reject

This could be in O(1). But what about the remaining part?


texts: Change the structure from 3SAT to 1in3 3SAT

texts:
There is a variable set V = {x1,x2,x3} and clause set C1={x1,x2,-x3} C2={x1,-x1,-x2} C3={-x1,-x2,x3} C4={x2,x3,-x3}. For this structure, no matter each variable is positive or negative, the clause can always be TRUE by at least one literal is TRUE within each clause, just like 3SAT.
How can I change the variable gadgets and clause gadgets to make it no matter each variable is positive or negative, the clause can always be TRUE by only one literal is TRUE within each clause, just like 1 in3 3SAT?


texts: Can a language be Turing Complete if its only provision for unlimited code/memory is through recursion?

texts: We've developed an esoteric language. In this language, a program contains a static amount of code, and a static amount of storage space. However, parts of the program can recurse, so the interpreter will spawn another copy of a subset of the code and additional storage space to match. Can this language be Turing Complete?


texts: Busy Beaver problem - Proof by contradiction

texts:
I am trying to understand a proof regarding the Busy Beaver problem that uses a proof by contradiction approach to show $\sum(n)$ is Turing-uncomputable:

  Find $\sum(n) = max \{\sum(M) | M \in M(n) \}$

Where

  $n$ : Number of states

  $M(n)$: Set of Turing Machines with $n$ states and binary alphabet (0s and 1s)

  $[k]$: Configuration of having a block of $k$ consecutive 1s on an otherwise blank (All 0) tape, and with the head at the leftmost 1.

  $e$: Empty tape (All 0s)

  $\sum(M): \sum(M) = k$ if machine $M$ when started on $e$ halts with $[k]$. Otherwise $\sum(M) = 0$

The proof:

  Suppose there is some Turing machine $\sum$ that computes $\sum(n)$. Then  consider the following Turing machine $Q$ where $k$ is the number of states of the last 3 components:

I cannot understand from here, what exactly is the contradiction here?


texts: Is this solution is bad for the coin change problem?

texts:
was doing coin change problem as an assignment(didnt know before), after came with this solution i checked the solutions available couldnt find a similar one like this, just curious.
removing the element from the list is O(N) so seems this also O(N^2) right?

def rec_coin(target,coins):
    if target == 0 or coins == []:
        return 0

    max_coin = max(coins)
    mod = target % max_coin
    coin_count = (target-mod)/ max_coin
    coins.remove(max_coin)

    return int(coin_count) + rec_coin(mod, coins)

rec_coin(23,[1,5,10,25])


texts: Consequences of the Time Hierarchy Theorem

texts:
The form of the Time Hierarchy Theorem that I have is this:

  If $f$ is time constructible then $\text{DTIME}(f(n)) \subsetneq \text{DTIME}(f(2n+1)^3)$.

We want the consequences of this to be that $\text{P} \neq \text{EXP}$ and $\text{EXP} \neq \text{2-EXP}$ etc. But I can't see how this follows.

I have $\text{P}$ defined as $\text{P} := \bigcup_{c=0}^\infty \text{DTIME}(n^c) $ and $\text{EXP}$ as $\text{EXP} := \bigcup_{c=0}^\infty \text{DTIME}(2^{n^c}) $.

I know that $\text{DTIME}(n^c) \subsetneq \text{DTIME}((2n+1)^c)=\text{DTIME}(2^c(n+0.5)^c)$. But $c$ is a constant, so surely the RHS is just another polynomial class.

Additionally, even if I had, say, $\text{DTIME}(n^c) \subsetneq \text{DTIME}(2^{n^c})$, how would I know that the limit of infinitely many of these classes still preserves the "not equal to" relation? (For instance, $\{n\} \subsetneq \{n, n+1\}$ but $\bigcup_n \{n\} = \bigcup_n \{n, n+1\} = \mathbb{N}$.)


texts: What is inapproximability of NP-hard problems?

texts:
Recently I have come across a paper which talks of "(1+ε)-inapproximability" and of "logarithmic approximation".

While I have a basic knowledge of computational complexity (I more or less know what it means to be in P, NP, NP-hard and so on), I tried to study some basic texts on approximability but I'm not sure I really get what this inapproximability is. Could you enlighten me on what the above expressions mean?

If you want to know the paper I was referring to, it was DasGupta & Desai. «On the complexity of Newmanʼs community finding approach for biological and social networks». Journal of Computer and System Sciences 79, n. 1 (2013): 50–67. The found inapproximability is a property of the modularity measure (the so-called Q) related to the Newman-Girvan algorithm for finding community structure in networks, a measure whose maximization has been proved NP-complete by Brandes, Delling, Gaertler, Gorke, Hoefer, Nikoloski, and Wagner in 2008. Thank you in advance.


texts: Communication complexity: fooling set bound for inner product function

texts:
I am trying to prove that the fooling set method does not give a good lower bound for the communication complexity of the inner product function. Specifically, I am trying to show that the best bound we get using the fooling set method is $$D(IP) \geq \Omega(\log n) $$

$D(IP)$ is the deterministic communication complexity of the inner product function. This implies that any fooling set for the inner product cannot have more than $n^2$ elements. How do I show this? I can verify the statement for specific instances, but I have no intuition for the proof.


texts: How this proof of fractional knapsack works?

texts:
I don't understand a step in my book proving the fractional knapsack problem:

Let value of items $v_1\ge v_2\ge \dots\ge v_n$, and assume $X=\langle x_1, \dots,x_n\rangle$ are the solution by greedy, where $0\le x_i\le 1$ is the fraction packed into the knapsack.
Assume $j$ is the first index s.t. $x_j<1$. Let $Y=\langle y_1,\dots, y_n\rangle$ be any solution not $X$.
Consider $$\dfrac{v_i}{w_i}(x_i-y_i)\ge\dfrac{v_j}{w_j}(x_i-y_i),\tag{????}$$
So $\displaystyle\sum_{i=1}^n v_i(x_i-y_i)=\sum\color{blue}v_i\dfrac{w_i}{\color{blue}w_i}(x_i-y_i)\ge\color{blue}{\dfrac{v_j}{w_j}}\sum w_i(x_i-y_i)\ge0.$

I can understand the blue part I highlighted, but can anyone help me understand the (????) part? Why it must hold?


texts:
I was experimenting with a WAVL Tree code I wrote.
One thing I noticed is that on average, there was much less rebalancing actions after delete than after insert. In fact, average rebalances after insert were about 2.5 per insert, and 1.8 per delete.
This results were consistent, even when we inserted and deleted in completely random order.
What possible explanation could there be?
Thanks!


texts:
This is a question about recurrence relation that contains sum inside the recursion.I am totally stuck. Can anyone help?

The problem asks to solve the following recursion $T(n)=\frac{1}{n} \sum_{i=1}^{n-1}(T(i)+T(n-i))+cn$. The problem also warns that unwrapping is going to be the wrong approach and the right strategy would be to guess the solution and prove it by induction. As the first step it suggests to start with $nT(n) -(n - 1)T(n -1)$.


texts: How to define the languages of the implicit set system problems?

texts:
There are implicit versions of some set system problems or matroid problems.
A set system is a pair $(U, \mathcal{F})$, where $U$ is a universe of size $n$ and $\mathcal{F}$ is a collection of susbets of $U$. $\mathcal{F}$ may satisfy some properties (e.g. Matroid).
We define $\Phi$ is a polynomial-time oralce which determines whether $S \subseteq \mathcal{F}$ given the universe $U$ and a subset $S \subseteq U$.
We formally define the implicit set system problems: Given a universe $U$, the goal is to determine whether there exists a set $X$ satisfying the property $P$.
For example of the property $P$.

The size of $X \in \mathcal{F}$ at least $k$.
$X$ hits all the elements $S \in \mathcal{F}$.

So the size of the instance is $|U| = n$.
What is the language of the implicit problem? It seems that the input contains an oracle.
How can I know the complexity of this kind of problems.
I think the size of this problem can be smaller (that is $O(\log n)$), because the input can just be a natural number, right?


texts: Reducing the halting problem for a language with strings that include at least one 1

texts:
$L_1$ = A sequence of $0$ or $1$'s such that at least one $1$ is in the sequence

$L_2$ = Turing machines that decide $L_1$

I think the first language is decideable, as the input string is of finite length and you can check every character in the string.

However, my intuition says the second language is undecideable. This would be like checking if a TM is equal to a TM that decides $L_1$.

Am I correct? And if so, how should I proceed to reduce the halting problem to $L_2$?


texts: Finding the longest overlapping interval pair

texts:
Say I have a list of $n$ integral intervals $[a,b]$ where each represents a set $S = \{a, a+1, \ldots, b\}$. An overlap is defined as $|S_1 \cap S_2|$. Example: $[3,6]$ and $[5,9]$ overlap on $[5,6]$ so the length of that is 2. The task is to find two intervals with the longest overlap in $o(n^2)$ using just recursion and not dynamic programming.

Naive approach is obviously brute force, which does not hold with time complexity condition. I was also unsuccessful trying sweep line algo and/or Longest common subsequence algorithm.

I just cannot find a way of dividing it into subproblems. Any ideas would be appreciated.


texts: Backward data-flow: post-order or RPO on reverse CFG?

texts:
When solving backward data-flow problems, many resources (Wikipedia and many presentations found online) recommend traversing the control-flow graph (CFG) in post-order for fastest convergence, which makes sense.

Other resources (such as the "Engineering a Compiler" book) suggest to use reverse post-order (RPO) on the reversed CFG instead.

... and PO(graph) != RPO(rev(graph)) in some cases involving cycles.

My question is: which resource is right? Post-order makes sense, so why not just use that and save the CFG inversion? Why would I use RPO on reversed CFG instead?


texts: Modifying the code for reading .ogg datasets and apply LSTM

texts:
Deep learning/LSTM/Matlab
There is a Matlab code that is doing the following steps for deep learning and applying LSTM, I need to change first three steps to use our dataset to train this model and you don't need to change other.
I need to apply that for .ogg audio files so Create and Use some audio files with .ogg format as sample data and give me the code.
The following steps is for your information:
Three classes of audio signals are generated and labeled as 'white', 'brown', and 'pink'. Each class has 1000 samples.
800 samples from each class are used as the training samples to train the deep neural network, so total 800*3=2400 samples in the training dataset. Their labels are their class names 'white', 'brown', and 'pink'. (Lines 29 and 30)
200 samples from each class are used as the validation samples to test the performance of deep neural network, so total 600 samples in the validation dataset. Their labels are their class names 'white', 'brown', and 'pink' (Lines 32 and 33)
Extract features from the training dataset and validation dataset.

define the structure of the neural network model (LSTM)
set training options
train the model iteratively using the training dataset and test the model using the validation dataset every iteration.
finish training and get the trained model.
generate test dataset and use the trained model to classify the test dataset into three classes, 'white', 'brown', and 'pink'

Code:
fs = 44.1e3;
duration = 0.5;
N = duration*fs;
wNoise = 2*rand([N,1000]) - 1;
wLabels = repelem(categorical("white"),1000,1);
bNoise = filter(1,[1,-0.999],wNoise);
bNoise = bNoise./max(abs(bNoise),[],'all');
bLabels = repelem(categorical("brown"),1000,1);
pNoise = pinknoise([N,1000]);
pLabels = repelem(categorical("pink"),1000,1)
sound(wNoise(:,1),fs)
melSpectrogram(wNoise(:,1),fs)
title('White Noise')
sound(bNoise(:,1),fs)
melSpectrogram(bNoise(:,1),fs)
title('Brown Noise')
sound(pNoise(:,1),fs)
melSpectrogram(pNoise(:,1),fs)
title('Pink Noise')
featuresTrain = extract(aFE,audioTrain);
[numHopsPerSequence,numFeatures,numSignals] = size(featuresTrain)
audioTrain = [wNoise(:,1:800),bNoise(:,1:800),pNoise(:,1:800)];
labelsTrain = [wLabels(1:800);bLabels(1:800);pLabels(1:800)];
audioValidation = [wNoise(:,801:end),bNoise(:,801:end),pNoise(:,801:end)];
labelsValidation = [wLabels(801:end);bLabels(801:end);pLabels(801:end)];
aFE = audioFeatureExtractor("SampleRate",fs, ...
"SpectralDescriptorInput","melSpectrum", ...
"spectralCentroid",true, ...
"spectralSlope",true);
featuresTrain = permute(featuresTrain,[2,1,3]);
featuresTrain = squeeze(num2cell(featuresTrain,[1,2]));
numSignals = numel(featuresTrain)
[numFeatures,numHopsPerSequence] = size(featuresTrain{1})
featuresValidation = extract(aFE,audioValidation);
featuresValidation = permute(featuresValidation,[2,1,3]);
featuresValidation = squeeze(num2cell(featuresValidation,[1,2]));
layers = [ ...
sequenceInputLayer(numFeatures)
lstmLayer(50,"OutputMode","last")
fullyConnectedLayer(numel(unique(labelsTrain)))
softmaxLayer
classificationLayer];
options = trainingOptions("adam", ...
"Shuffle","every-epoch", ...
"ValidationData",{featuresValidation,labelsValidation}, ...
"Plots","training-progress", ...
"Verbose",false);
net = trainNetwork(featuresTrain,labelsTrain,layers,options);
wNoiseTest = 2*rand([N,1]) - 1;
classify(net,extract(aFE,wNoiseTest)')
bNoiseTest = filter(1,[1,-0.999],wNoiseTest);
bNoiseTest= bNoiseTest./max(abs(bNoiseTest),[],'all');
classify(net,extract(aFE,bNoiseTest)')
pNoiseTest = pinknoise(N);
classify(net,extract(aFE,pNoiseTest)')


texts: Arden's Rule, DFA & NFA to regular expressions

texts:
I have been trying to figure out the Arden's Rule and the equational method to transform DFA's & NFA's to RE. I know what the rule state:

if   x = s + xr
then x = sr*, with $s,r\in$ Regular Expressions

With that said, when I'm trying to transform one DFA in a RE this questions pop:

For example regarding this DFA

The $\epsilon$ is added in the entry stage A or in the final stage D and A ?
The equations should be written regarding the transitions in or out of a given state

2.1 For example A = $\epsilon$ + 0B + 1C  or A = $\epsilon$ + 0C
Can the equational method and Arden's Rule be applied to a NFA with multiple initial states ?

Final thoughts, I have been trying out and it seems that when we count the transitions out of a state the $\epsilon$ should be added to the final state. When we count the transitions into a state the $\epsilon$ should be added to the initial state.

Keep in mind that I SERIOUSLY doubt my conclusions and I really need some help.


texts: Simplest argument that language decidable in constant time cannot be $\mathsf{NP}$-hard?

texts:
My question is specifically about $\emptyset$, but more generally about any language that can be decided in (deterministic or nondeterministic doesn't really make a difference here) constant time. Obviously, $\emptyset$ cannot be $\mathsf{NP}$-hard since there is nothing to map "yes"-instances to, but I'd prefer a one line argument using a time hierarchy theorem, ideally. Currently I'm arguing (very informally speaking) that since constant time is $\subsetneq \mathbb{o}(n \log n)$, constant time is strictly "less powerful" than any deterministic polynomial time due to the deterministic time hierarchy theorem and thus - since $$\mathsf{Polytime}(f(n)) \subseteq \mathsf{NPolytime}(f(n))$$ - also strictly less powerful than nondeterministic polynomial time. So, constant time languages can't be $\mathsf{NP}$-hard.

This doesn't sound elegant to me at all (although it should be correct I hope, even if not phrased as formally as I'd write it down for something to hand in). What's the most elegant argument you can come up with, preferably using not-too-advanced complexity theory?


texts: Independence of order of insertion hashtable with open addressing

texts:
I'm taking a data-structure class, and the lecturer made the following assertion:

  the number of attempts needed to insert n keys in a hash table with linear probing is independent of their order.

No proof was given, so I tried to get one myself. However, I'm stuck.

My approach at the moment: I try to show that if I swap two adjacent keys the number of attempts doesn't change. I get the idea behind it, and I think it's going in the right direction, but I can't manage to make it into a rigorous proof.

Aside, does this fact also hold for other probing techniques such as quadratic or double hashing?


texts: Recursive type encoding on System F (and other pure type systems)

texts:
I am studying pure type systems, particularly the calculus of constructions, and trying to use an encoding for recursive types on it, which, according to Philip Wadler, is possible. As an example, I'm using the Morte Haskell library to encode Scott numerals as given by Cardelli.
A summary of the encoding is as such: given a (positive) recursive type...
$$\mu X.F\ X$$
...we may encode it as a type on System F as...
$$Lfix\ X.F\ X\ =\ \Lambda X.(F\ X\rightarrow X)\rightarrow X$$
...or, using pure type systems' notation (with an explicit $F$)...
$$Lfix\ =\ \Pi F: *\rightarrow*.\Pi X: *.(F\ X\rightarrow X)\rightarrow X$$
...since $F$ is a type constructor ($*$ is the type of types).
In order to encode such, we need to declare three functions, $fold$, $in$ and $out$, according to Wadler, and used by Cardelli on the encoding for Scott numerals.

fold  :  All X. (F X -> X) -> T -> X
fold  =  \X. \k: F X -> X. \t:T. t X k
in    :  F T -> T
in    =  \s: F T. \X. \k: F X -> X. k (F (fold X k) s).

(Where $T$ is $Lfix\ X. F\ X$.)
It's trivial to write the $fold$ function as given. But when trying to write the $in$ function, it doesn't seem to typecheck. The expression $(fold\ X\ k)$ has type $T\rightarrow X$, and $(F\ (fold\ X\ k)\ s)$ should be of type $F\ X$. Then we infer that $F$ should be of type $(T\rightarrow X)\rightarrow F\ T\rightarrow F\ X$ (looks like a fmap). This doesn't typecheck, because F is a type constructor (of type $*\rightarrow*$).
This doesn't look like a typo... am I missing something?


texts: Is the language L = {(a,b)* | #a * #b is an odd number} regular?

texts:
Is the following language regular? $$\{ w \in \{a, b\}^* |\ \text{the product of the number of $a$'s and the number of $b$'s is an odd number}\} $$

If i'm not mistaken the condition is the same as having an odd number of $a$'s and an odd number of $b$'s. I have tried using the Pumping Lemma without success. So I'm suspecting it's regular. But I can't think of a regular expression or an automaton that accepts it.


texts: Higher order rewriting theory and critical pairs with the beta rule

texts:
In a higher-order pattern rewrite system, one specifies rewrites on beta
normal forms of terms.  Is it possible to have a rewrite like:

$\gamma := \lambda x . F(m) \to F(\lambda x . m)$

for some function symbol $F$ and $m$ in $\beta$-normal form?  If so, then there is a "critical pair" between $\gamma$ and $\beta$

$F(m) [t/x] \leftarrow (\lambda x . F(m)) t \rightarrow (F(\lambda x .m )) t $

On the other hand, is there any reason to require $\gamma$ go the other direction?:

$F(\lambda x . m) \to \lambda x . F(m)$

This would avoid critical pairs with $\beta$, but may in practice be less natural.

If the former is possible, can one still conclude confluence if all critical pairs are development closed?


texts: Find all neighbors at a certain distance, in 3 dimensions

texts:
I have two algorithms which I would like to implement:

First, given a (very long) list $\{\mathbf{r}_{i}\}_{i=1}^{n}\subset \mathbb{R}^{3}$, a point $p \in \mathbb{R}^{3}$, and a distance $d>0$, find all $i$ such that $|\mathbf{r}_{i} - \mathbf{p}| < d$.

Currently, I sort the list over the $x$-coordinate, so that if $x_{i}$ is the $x$-coordinate of $\mathbf{r}_{i}$, then $x_{1} \le x_{2} \le \cdots \le x_{n}$. Then I use the condition $(x_{i}-\mathbf{p}_{x})^{2} > d^2 \implies |\mathbf{r}_{i} - \mathbf{p}|^2 > d^{2}$. This allows me to filter the list by binary search. This leaves me with a subset $\{\mathbf{r}_{i}\}_{i=j_{1}}^{i=j_{2}}$ of the original list where for all $i \in [j_{1}, j_{2}]$, $(x_{i}-\mathbf{p}_{x})^{2} <= d^2$. Then I have to bite the bullet and do an explicit test on each one of these to see if $|\mathbf{r}_{i} - \mathbf{p}| < d$.

This algorithm strikes me as weird and not optimal; is there a better way?

Next: A related problem: Given a list $\{\mathbf{r}_{i}\}_{i=1}^{n}\subset \mathbb{R}^{3}$ and a point $\mathbf{p} \in \mathbf{R}^{3}$, find $j \in [1,n]$ such that $d_{j}:=|\mathbf{r}_{j} - \mathbf{p}| = \min_{i} |\mathbf{r}_{i} - \mathbf{p}|$.  Is there an efficient algorithm to find $j$?

Finally, I should note that any one-time ``sorting'' expense is tolerable, since this operation is repeated many times.


texts: If there is no global clock in Distributed systems  , then what is the solution for synchronization in DS ? Also , no global clock in DS is a direct consequence of the fact that the only communication is by sending messages through a network. Can someone please explain how the communication via message passing has resulted in no global clock ?


texts: Turing-completeness of Goto language with limited constants

texts:
This is taken from an old exam of my university that I am using to prepare myself for the coming exam:
Given is a language $\text{Goto}_{17} \subseteq \text{Goto}$. This language includes exactly those $\text{Goto}$ programs in which no constant is ever greater than $17$. Show that every $\text{Goto}$ program can be simulated by a $\text{Goto}_{17}$ program.
$Goto$ here describes the set of all programs written in the $Goto$ language made up of the following elements:
With variables $v_i \in \mathbb{N}$ and constants $c \in \mathbb{N}$
Assignment: $x_i := c, x_i := x_i \pm c$
Conditional Jump: if(Comparison) goto $L_i$
Haltcommand: halt
It seems obvious to me that this would not limit the power of a program, as there are easy ways to just repeat operations to achieve the same thing with limited constants. To add or subtract arbitrary values we can just add or subtract repeatedly. To compare, we can put our value to compare with into a dummy variable and compare, reduce, repeat until we know the value. These dummy variables are guaranteed to be unused and free for this use if we simply map the variables from our Goto program so that any variable $v_i$ from the Goto language maps onto $v_{2i}$ in our new language.
How can the equivalence in power between these to languages be shown? Is a compiler from one to the other the best solution, or are there more elegant ways? Specifically showing how comparisons work seems like it would be rather complicated and this is a question that originally appeared in a written exam with only a few minutes to answer this question if you average it out. If there is no better way, how would an approach to converting the following Goto program into a limited Goto program of this kind look?
v = 99
repeat: v = v + 1
if(v = 100)goto repeat
halt


texts: Maximum flow with maximum flow on specific edge

texts:
I am trying to solve the following problem:

We're given a network flow $(V,E,c,s,t)$ and an edge $(u,v)$. We have to provide an algorithm that computes the maximum flow which has maximum flow on $(u,v)$ also.

The idea that I had was, computing max flow and on the residual graph trying to compute a cycle that starts from $s$ and passes through the edge $(u,v)$ and trying to increase $(u,v)$'s flow while decreasing the flow from other edges. In other words, trying to maximize the flow of $(u,v)$ while preserving the maximum flow value. But I feel like there's a simpler way.

Can someone point me in the right direction? Is my thinking correct? If not how should I approach the problem?

Any help is appreciated! Thanks!


texts: When did "regular" start referring to Type 3 languages/grammars?

texts:
In his 1959 paper, On Certain Formal Properties of Grammars, Chomsky defined a "regular" grammar as a specific form of a type 2 (context-free) grammar. (See Definition 8 of that paper.) He then goes on (in Section 6) to demonstrate that regular (type 2, context-free) grammars can generate more languages than type 3 (finite state) grammars.

However, in every other computer-science reference I've read, type 3 languages (those recognizable by a finite state machine) are called "regular". (For example, see the Wikipedia entry for Chomsky Hierarchy.)

My question is, when did "regular" shift from referring to type 2 languages to type 3 languages? And why? (Was it intentional, or did someone mis-quote Chomsky at some point and that stuck?)


texts:
I am preparing to graduate high school. Although I do not intend to study computer science in college, I feel like it might be useful to familiarize myself with the theoretical CS concepts taught in academia (eg. algorithms, structures, compilers). Can you recommend books that are either frequently used in current CS curricula or equate what one would learn in a CS curriculum?

Right now, I am planning on buying The C Programming Language, The Algorithm Design Manual, Algorithms + Data Structures = Programs, and Compilers: Principles, Techniques, and Tools.


texts: DFS timestamps, how important are they in pathfinding?

texts:
I am writing a work on pathfinding algorithms and DFS is a part of it. And the book Introduction to Algorithms and many another websites mention timestamps. And they say timestamps could be used for others algorithms using DFS, topological sorting and etc.

So for pathfinding these timestamps dont really matter?

Thank you for helping.

Here is the section from the book mentioning timestamps:
Besides creating a depth-first forest, depth-first search also timestamps each vertex. Each vertex has two timestamps: the first timestamp :d records when is first discovered (and grayed), and the second timestamp :f records when the search finishes examining ’s adjacency list (and blackens )


texts: approximation algorithm of k-set packing

texts:
For my application problem, I am looking for an easy to implement or source code for approximation algorithm for maximum k-Set Packing problem.

Given a universe $U$   and a family $ \mathcal{S} $ of subsets of $ {\mathcal{U}}$. Assume that all subsets in $\mathcal{S}$ have size $k$.
A $k$-set packing is a subfamily ${\mathcal {C}} \subseteq {\mathcal {S}}  $ of sets such that all sets in  ${\mathcal{C}}$ are pairwise disjoint, and the size of the packing is  $|{\mathcal  {C}}|$. We are looking for the maximum size of k-Set Packing.

I have found a few math papers claiming
the integrality gap is exactly $k - 1 + \frac{1}{k}$, via standard linear programming; $k - 2$, by local constraints;  at most $\frac{k+1}{2}$ via a result in extremal combinatorics. However, there is no clear algorithm for implementation. Please help me if you have any suggestions. Thank you!


texts: Prove that finding largest subset of undirected graph that is almost independent is NP-hard

texts:
A subset $S$ of vertices in an undirected graph $G$ is called almost independent if at most 100 edges in $G$ have both endpoints in $S$. Prove that finding the size of the largest almost-independent set of vertices in a given undirected graph is NP-hard.

For these types of problems, I know that I should try to find a polynomial time reduction of an algorithm that is already known to be NP-hard.  I tried my hand at trying to manipulate the k-coloring problem, but without any luck.

How would I go about proving this function is NP-hard?


texts: Informal definition of a safety property

texts:
Could someone kindly explain why safety properties are commonly informally described as "something bad never happens"? This doesn't seem accurate at all. Rather, it seems that one should say "if something bad happens, you can always guarantee it will have happened in a finite amount of time" where "something bad happens" means the property is necessarily violated.
The corresponding definition for liveness properties that "something good should eventually happen" makes sense, though arguably the word "good" should be taken out.


texts: How can I make a pipeline with undefined/unlimited stages?

texts: I've been told that if you understand a pipeline then you should be able to make it with any depth, but I can only do 4 stages and maybe 5 if the memory is not too slow. How can I learn how to make infinite pipelines?


texts: How many $(x, y)$-paths of length $20$ are there, where $x$, $y$ adjacent vertices in cycle $C_5$?

texts: As the title of the question suggests, let $x$ and $y$ be two adjacent vertices in the cycle $C_5$. How many $(x, y)$-paths of length $20$ are there?


texts: Example of binary trees with maximum rotation distance

texts:
In the 1988 paper Rotation Distance, Triangulations, and Hyperbolic Geometry, Sleator, Tarjan and Thurston show that for any pair of $n$-node binary trees, the maximum rotation distance between them is $2n-6$ for all $n \ge 11$.

They also claim that this bound is tight for sufficiently large $n$. I see how they achieved the upper bound of $2n-6$ rotations but I am now trying to understand their proof of the lower bound. To the best of my understanding, their argument relies on triangulating a polyhedron and looking at volumes in hyperbolic space.

I'm having trouble connecting these fairly technical mathematical claims back to actual binary trees. In particular, what would be a concrete example of two binary trees (or families of binary trees) which meet this lower bound and actually require $2n-6$ rotations to transform one tree into the other?


texts: Monad in Haskell programming vs. Monad in category theory

texts:
I have a question about concept of monad used in Haskell programming
and category theory in math.
Recall in Haskell a monad consists of following components:

A type constructor that defines for each underlying type how the
corresponding monad type is to be obtained. The name of this type
constructor is often used synonymously with the whole monad. If $M$
is the name of the monad and $t$ is arbitrary fixed data type,
then $M t$ is the corresponding monadic type

A unit function that maps a value of the underlying type to the value of
the corresponding monad type. The result is the "simplest" value in the
corresponding type that can be obtained from the original value.
In Haskell this function is called return. The unit function has
the polymorphic type $t → M t$

At least one further operation, which describes the combination of
monadic operations.

On the other hand in category theory a monad is a triple $(T, \eta, \mu)$
of a category $C$ where

$T: C \to C$ is a functor

$\eta: 1_K \to T$ a natural transformation in sense of category theory

$\mu: T^2 \to T$ a natural transformation

and these objects should
satisfy following diagrams:
https://en.wikipedia.org/wiki/Monad_(category_theory)
Question: How are these monads from Haskell and abstract category theory
related? Does the monad structure in Haskell have natural
"monad structure" in sense of category theory, ie we can canonically associate to $M$ a canonical triple as described above?


texts: How can I use prefix sum of an array to solve this problem?

texts:
I attempted this question on hackerrank. It seemed simple enough, and my program ran on small inputs. But my approach was "naive". And failed for more computationally intensive inputs. Here is the question:

Problem Statement

You are given a list of size , initialized with zeroes. You have to perform  operations on the list and output the maximum of final values of all the  elements in the list. For every operation, you are given three integers ,  and  and you have to add value  to all the elements ranging from index  to (both inclusive).

Input Format

First line will contain two integers  and  separated by a single space.
Next  lines will contain three integers ,  and  separated by a single space.
Numbers in list are numbered from  to .

Constraints

2 ≤ N ≤ 10^7
1 ≤ M ≤ 2 * 10^5
1 ≤ a ≤ b ≤ N
0 ≤ k ≤ 10^9

Output Format

A single line containing maximum value in the updated list.

Here is the editorial describing how to solve the problem

  You are given a list of size N, initialized with zeroes. You have to
  perform M queries on the list and output the maximum of final values
  of all the N elements in the list. For every query, you are given
  three integers a, b and k and you have to add value k to all the
  elements ranging from index a to b(both inclusive).

First thought which comes into mind after reading this problem will be segment tree with lazy propogation but that will not pass here as N <= 10^7 :)

So, We have to use some different kind of approach. We can do a O(1) update, i.e. given a b k add k to index a and add -k to index (b+1). By doing this kind of update ith number in array will be prefix sum of array from index 1 to i.

So, We can do all M updates in O(M) time. Now we have to check the largest number in the original array. i.e. the index i such that prefix sum attains maximum value.

We can calculate the all prefix sums as well as maximum prefix sum in O(N) time which will get Accepted. Another approach is we can do it in O(MlogM) time because we have to check the value of prefix sum at only 2*M indices. i.e. a and b values of all the updates. See setter's code.

I don't understand how adding k to index a and adding -k to index (b+1) gives us an array in which the the ith number in the array is the prefix sum of the array from index 1 to i.


texts: Simple path in a graph, within a given range of lengths

texts:
Given an undirected graph $G(V,E)$ and two nodes $s$ and $t$, $s,t\in V$, find a path whose length $L$ is bounded by a lower bound $N$ and an upper bound $M$, $N\leq L\leq M$.

So, for example, $N=4, M=7$, I want to confirm that there is at least one simple path of 4,5,6 and 7 between two nodes in a graph? Nodes of the graph may appear in more than one path.

Typical problem size:

10,000 nodes
Mean of 20 edges per node
Cycles in graph
Unweighted edges


texts: Easy infinite subclass of cubic graphs for Hamiltonian cycle problem

texts:
I know that Hamiltonian cycle problem is $NP$-complete for 2-connected planar bipartite cubic graphs.

I'm interested in non-trivial infinite subclass of cubic graphs where the Hamiltonian cycle (path) problem is efficiently solvable. I tried the graph class database but could not find any such class graph.

  Is there any easy infinite subclass of 2-connected cubic graphs for Hamiltonian cycle problem?

Motivation: Barnette's conjecture states that every 3-connected planar bipartite cubic graphs is Hamiltonian which implies that HC is in $P$ (if it is true). However, Feder and Subi proved if there is any non-Hamiltonian 3-connected planar bipartite cubic graph then HC is $NP$-complete for this graph class.


texts:
I was wondering, since $a^*$ is itself a star-free language, is there a regular language that is not a star-free language? Could you give an example?

(from wikipdia) Lawson defines star-free languages as:

  A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star.

Here is the proof of $a^*$ being star-free:

  $\emptyset$ is star-free $\Longrightarrow$
  $\Sigma^*=\bar{\emptyset}$ is star-free $\Longrightarrow$
  If $A\subseteq\Sigma$ then $\Sigma^*A\Sigma^*$ is star-free $\Longrightarrow$
  If $A\subseteq\Sigma$ then $A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$ is star-free

In the last line we have $A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$, because any word that is not of form $A^*$ contains a letter in $\Sigma \setminus A$ and vice versa.


texts: error computation in multi layered perceptron

texts:
I was reading about Multi Layered Perceptron(MLP) and how can we learn pattern using it. Algorithm was stated as

Initiate all weight to small values. Compute activation of each
neuron
using sigmoid function. Compute the error at the output layer using
$\delta_{ok} = (t_{k} - y_{k})y_{k}(1-y_{k})$
compute error in hidden layer(s) using
$\delta_{hj} = a_{j}(1 -a_{j})\sum_{k}w_{jk}\delta_{ok}$
update output layer using using
$w_{jk} := w_{jk} + \eta\delta_{ok}a_{j} ^{hidden}$
and hidden layer weight using
$v_{ij} := v_{ij} + \eta\delta_{hj}x_{i}$

Where $a_{j}$ is activation function, $t_{k}$ is target function,$y_{k}$ is output function and $w_{jk}$ is weight of neuron between $j$ and $k$

My question is that how do we get that $\delta_{ok}$? and from where do we get $\delta_{hj}$? How do we know this is error? where does chain rule from differential calculus plays a role here?


texts: Highest possible value of combinations of 5

texts:
According to https://www.heroescounters.com/teampicker a Hero has a synergy value with another hero, Heroes of the Storm have 60+ heroes each one with a synergy value for example:

HeroID  Synergy.With.HeroID      Synergy.Points
1               2                       97
1               3                       95
1               4                       94
45              1                       2
45              2                       11

A Team in heroes of the storm have 5 heroes, and the full synergy of a team is calculated by the formula:

Team_total_synergy = Synergy_Points(Hero1 with Hero2) +
mean(Synergy_Points(Hero3 + Hero1) + Synergy_Points(Hero3 + Hero2)) +

mean(Synergy_Points(Hero4 + Hero1) + Synergy_Points(Hero4 + Hero2) + Synergy_Points(Hero4 + Hero3)

[And so on... till Hero5]

Explaining the formula: Each Synergy Value after the synergy of Hero 1 and Hero 2 is calculated by the Mean of that Hero with the rest of the team, When Hero5 is added up i got the synergy of the team summing all the values.

My Answer is, How can I find the Team with the greatest possible synergy given that formula, and how can I write the code to find it given the possibility there are 64 Heroes(approximately) without brute-forcing all all 64^5 combinations of heroes.


texts: Is radix sort really O(n) for sorting 32 bit integers?

texts:
I was trying to analyze radix sort in terms of time and space. Assume that we are given $n$ 32-bit integers which we would want to sort by looking at the least significant digits first.

$k$ is the total amount of bits that you will be working with at every step. So at first you look at the first $k$ bits, and sort the elements with counting sort. Then you look at the next $k$ bits etc.

In total we would have to run counting sort $\frac{32}{k}$ times. In the counting sort phase we will both have to scan the input array and also the bucket array, where the input array is of size $n$ and the bucket array is of size $2^k$. In other words the running time is going to be $ \Theta (\frac{32}{k}(n+2^k))$. As for space, we will need an extra temporary array of size $n$ during the counting sort phase, and also an array for the bucket, so in total the space will be $\Theta (2n + 2^k)$

So we have:

Time: $ \Theta (\frac{32}{k}(n+2^k))$

Space: $\Theta (2n + 2^k)$

Am I the only one who can't see why this is $O(n)$?


texts:
I was fooling around the other day on this website: http://regexcrossword.com/ and it got me wondering what the best way to solve it was.

Can you solve the following problem in polynomial time or is it NP-hard?

  Given an NxM grid with N regular expressions for the columns and M for the rows, find any solution to the grid such that all the regular expressions are satisfied, or say that no solution exists.


texts: How to transform robot motor steps into X/Y coordinates?

texts:
I have a robot with two motors A and B connected to wheels 21.6mm in diameter. The motors move in steps, and there are twenty steps for each complete revolution of the wheel. To make the robot move forwards, I turn on A and B in the forward direction and have it rotate a number of steps. To make it move backwards, I turn on A and B in the reverse direction. To get it to turn left, I turn on A and turn off B. Similarly to get it to turn right, I turn off A and turn on B. Using this scheme, I can get the robot to move in any direction.
My question is this: is it possible to transform the steps of motor A and motor B into the X/Y coordinates for the robot? For example, if I move the robot forward 10 steps, turn right 10 steps and move forwards again 10 steps can I calculate the X/Y coordinates of the robot? Assume that the robot starts at point 0,0.


texts: Construct a lambda term from a Böhm tree

texts:
Given an acyclic graph, how can I build a lambda calculus term such that this graph is the term's Böhm tree?

If the Böhm tree is a finite tree (so the result is a strongly normalizing term).
If the Böhm tree is an acyclic graph, but not necessarily a tree (so the result may not be normalizing).
If the Böhm tree is not finite — is there a language of inifinite trees on which the process is decidable and which allows reaching every lambda term?


texts: New to the world of software verification and synthesis. It was suggested to me that the book "Principles of Model Checking" is a good reference for verification, but I am clueless about synthesis. Could someone refer a good book?


texts: Reference request: Leaf-heavy master theorem algorithms

texts:
I know many algorithms that can be analyzed using master theorem, but the only algorithm I know where the time is dominated by the leaves is fast matrix multiplication.

Are there other recursive algorithms (not necessarily master-theorem-style -- can be akra bazzi/something similar) where the time is dominated by the leaves? Would be grateful for any references.


texts: How can I improve my algorithmic ingenuity?

texts:
During undergrad I felt my education was mostly comprised of applying existing theory to real world problems (ie. algorithm design/analysis). I've seen derivations of many algorithms and proofs of their complexity, but I'm often left bothered by the question of how one comes to discover an algorithm. It seems daunting to imagine developing a novel algorithm given the ingenuity involved in crafting an effective approach. I'm wondering if there are ways to train that ingenuity.

My question is, how I can cultivate the skills necessary to develop original approaches to quantitative problems? Are there any resources that focus on these skills?


texts:
Given that the Hamiltonian cycle problem is NP-complete, I want to prove that the following problem is NP-complete:

  Given an undirected graph $G(V,E)$ and vertices $s,t\in V$, does there
  exist a path from $s$ to $t$ with at least $k$ edges such that all vertices
  in the path are distinct?

I thought of assigning a weight of $1$ to every edge and on similar grounds, but I am not able to compensate for the "at least $k$" edges part.

It would be appreciated if somebody could help me with  the approach.


texts: Best algorithm for correlation between time series?

texts:
I have some biological data (ECG), which are quite chaotic in nature, and and some other data; that are not chaotic but related in some way, like fatigue. I want to find out how the time series, chaotic, data are related to each of these other time series.

My undergrad thesis was on string "emotion" classification and time series is a whole other animal. My goal is to understand how the "other data" trend and at what percentage in correlation the biological data, not just classes [A, B, C].

I want to be able to distinct what is happening throughout the biological's phases in retrospect to the other time series. Like in this phase of the ECG there was 20% increase in fatigue, 7% in attention etc. I have all those data I just don't know how to make the connection.

I tried to find on time series ML but all of them jump from pretty basic algorithms and vague narratives to hardcore mathematical implementations.

If you know of a site, blog, docs, anything that ease into such examples and, very important, have code (python would be nice).

Would Random Forest work for such a task or should I be looking more into KNN (K-Means Nearest Neighbour), DTW (Dynamic Time Wrapping), STMF (Shape-based Template Matching Framework)?

Thank you very match for your time. Would be happy to provide and clarification I can, if anything doesn't make sense.


texts: Why did Alan Turing have to define computation before demonstrating undecidability?

texts:
It seems to me that Turing could've just presented the following argument:

Theorem: Given a computational model $\mathcal{M}$ capable of conditional branching and indeterminate repetition the halting problem of $\mathcal{M}$ is undecidable from within $\mathcal{M}$.

Proof: Suppose $H$ solves the halting problem in $\mathcal{M}$. Namely $H\in\mathcal{M}$ and
$$
H(A) =
\begin{cases}
1 & \text{if $A(A)$ halts}\\
0 & \text{if $A(A)$ doesn't halt}
\end{cases}\qquad\forall A\in\mathcal{M}
$$

Then construct
$$
\begin{split}
\overline{H}(A)
& =
\begin{cases}
\infty & \text{if $H(A) = 1$}\\
0 & \text{if $H(A) = 0$}
\end{cases}\\
& =
\begin{cases}
\infty & \text{if $A(A)$ halts}\\
0 & \text{if $A(A)$ doesn't halt}
\end{cases}
\end{split}
$$
($\infty$ indicates an infinite loop. The $0$ could've just as well been a $1$ without affecting the argument.)

Because $H\in\mathcal{M}$ so is $\overline{H}$. After all, it only adds conditional branching and an infinite loop. So we can ask whether $\overline{H}(\overline{H})$ halts - yielding a contradiction in either case. $$\tag*{$\Box$}$$

It seems to me that with this argument Turing could've just said "I don't care how you define computation. Try coming up with the most powerful notion you can conceive of, then run through this argument, and voila, there's still undecidable problems."


texts: Is subtype polymorphism a kind of ad hoc polymorphism?

texts:
"Ad-hoc polymorphism is obtained when a function works, or appears to work, on several different types (which may not exhibit a common structure) and may behave in unrelated ways for each type." – Strachey 1967

Subtype polymorphism seems to fit this description, albeit usually with late binding on the type that dictates the function's behavior. In Java, for example, the toString function works on any object at all, but has many wholly distinct implementations which are distinguished from one another based on the runtime type of the object; i.e., any class can override it and create a new ad hoc definition.

But when I poke around online, I usually find people making a sharp distinction between subtype polymorphism and ad hoc polymorphism; they are treated as wholly different beasts. Would it be correct to say that subtype polymorphism is a kind of ad hoc polymorphism? If not, why not?


texts: Why is sequential search of ordered list slower than search of unordered one

texts:
I have got assignment to implement set class with linked list, so I first made it with unordered list and time needed to insert million integers is bit less than hour. Then I thought I can get it to work faster by making list ordered (since in average it should take less time to check  is element already in set) but it went running for 1.5h after I stopped it.

In both algorithm there are 2 functions: 1. searches through linked list and returns pointer to predecessor of given element (null if element is not found). In first algorithm before searching for element, element itself is inserted at end of list and after search it is removed (this way there is no need to check if current element is last in search loop). If element is not found second function adds it on beginning of list.

In second algorithm search function does same except it stops after it finds element larger than searched element and returns it address.Then it is inserted in right place.

Integers are randomly generated using built in rand() function.

Update:
I measured average time it takes to find element in both ordered and unordered list and results looks strange to me.

Average times in unordered list
(left is number of elements in list, right is average time spent in search loop in microseconds).

10000 :29.4015
20000 :58.7789
30000 :88.0507
40000 :117.39
50000 :146.82
60000 :176.307
70000 :206.139
80000 :236.085
90000 :265.948
100000 :296.426
110000 :326.888
120000 :357.238

In ordered list

10000 :30.2287
20000 :87.0195
30000 :154.494
40000 :221.932
50000 :292.55
60000 :364.127
70000 :442.623
80000 :527.407
90000 :624.626
100000 :739.803
110000 :869.816
120000 :1008.33

Measured pieces of code:

Search in unordered list

while(k != current->k){
    old = current;
    current = current->next;
}

Search in ordered list

while(current->k < k){
    old = current;
    current = current->next;
}

In both cases there is guard at and of list, in first case equal to k, and in second larger than k.


texts: Space complexity for accepting word decision problem of DFAs

texts:
It is well known that the the decision problem $w \in \mathcal{L}(M)$ for a DFA $M=(Q,\Sigma, \delta, q_0,F)$ is in $\mathcal{O}(|w|)$. To proof this we assume that the successor state computation can be done in $\mathcal{O}(1)$, for example with an array of size $Q \times \Sigma$.

My question is: Is there a better way to store the transition function while maintaining the same runtime complexity? When $\Sigma$ is very large the table gets very memory inefficient. It is even worse for NFAs which have a list of states in each cell of the array.


texts: Heuristics for maximizing the performance for a given complexity

texts:
I often have to balance the computational requirement of each qualitatively different module of my algorithm. So, I'm using this heuristics for maximizing the performance for a given complexity, but I couldn't find this heuristics anywhere online. Could anyone give me some reference?

Let $F(x):=\sum_{i=1}^N O(f_i(x))$ be the complexity of my algorithm, where $x=(x_1,\ldots x_k)$, and each $O(f_i(x))$ is the complexity of $i$-th module of algorithm. Note that the algorithm performs better each time we increase the computes for any of the module, i.e., $f_i$, but we don't know how the form of the performance scaling function $G(f_1, f_2,\ldots f_N)$ looks like. I usually set $O(x_i)$ for each $i$ such that $O(f_i(x))=O(f_j(x))$ for any $i,j$. In other words, I usually want each module to spend asymptotically the same computes, so that none of them will become the bottleneck. You can assume each $f_i(x)$ is a polynomial of positive coefficients for simplicity. I think this is kinda common sense. Is there any formal jusitification?


texts:
$Q=\left\{q_{0}, q_{1}\right\} \times\{0,1, \cup\} \times\{0,1, \cup\}$

What does this mean ? Is it just for saving values in a state?


texts: Sqrt(x) function implementation; what is $(i^2 \leq x) \land ((i + 1)^2 > x)$ checking?

texts:
Recently I was working on a LeetCode question

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only
the integer part of the result is returned.

Example 1:

Input: 4
Output: 2
Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
             the decimal part is truncated, 2 is returned.

Here is a solution that I really like and understand, except for one line. It is using binary search to get to the solution:

int mySqrt(int x) {
    if (x == 0) return x;
    int left = 1, right = INT_MAX, mid;
    while(left < right) {
        mid = left + (right - left)/2;
        if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {
            return mid;
        }
        if (mid < x/mid) {
            left = mid + 1;
        } else { // mid > x/mid
            right = mid;
        }
    }
    return right;
}

The conceptual question is: why is it true that given a particular number, say $i$, $$(i^2 \leq x) \land ((i + 1)^2 > x)$$ returns whether or not $i$ is the truncated integer representation of the square root of $x$? (The code block above returns on the identical condition, but inequality is rearranged to avoid integer overflow)


texts: Finding Closest Transformation Between 2 Input Images

texts:
Is there an algorithm (or model/approach) that manages to find the "closest" possible transformation between two input images? As the set of information preserving transformations (e.g. diffeomorphisms) can be rather large, I will be happy with an approach for affine transformations only, i.e. scalings + rotations + translations + reflections + shears. I know that such a discipline exists – I believe it is called image registration? Wiki link – and is most probably used in medical applications for aligning scans and such.
Below is an example of such a possible setting: Two images are similar in such a way that there exists a rotation up to which the images have a large amount of overlap (here: about 35 degrees counterclockwise) The images are assumed to be centered and scaled but this is not necessary in the general case, of course. Some similarity metric is chosen and the angle of rotation that yields this optimal value should be returned somehow. In other words, with the two images given on the left, the expected output should be approximately 35 degrees CCW.

Another example might be two images of a cat which are extremely similar up to a translation. The algorithm takes the two images as inputs and should have as output the correct translation, whether as a vector (x and y translations) or a matrix (shift matrix).


texts: In TensorFlow tutorials, why do they use only the first term of cross-entropy as the cost function?

texts:
The cross-entropy cost function is usually defined as

$$C = -\frac{1}{n} \sum_x \left[y \ln \hat{y} + (1-y ) \ln (1-\hat{y}) \right]$$

where $y$ is the expected output and $\hat{y}$ is the predicted output, for training example $x$.

But, in TensorFlow MNIST tutorial, they use

cross_entropy = tf.reduce_mean(-tf.reduce_sum(y_ * tf.log(y_conv), reduction_indices=[1]))

which, I suppose, is equivalent to

$$C = -\frac{1}{n} \sum_x y\ln\hat{y}$$

That means only the first term of the cross-entropy expression, $y\ln\hat{y}$, is being used. Why? Why isn't the second term, $(1 - y)\ln(1 - \hat{y})$, being used too?


texts: Constraint-based Type Inference with Algebraic Data

texts:
I am working on an expression based language of ML genealogy, so it naturally needs type inference >:)

Now, I am trying to extend a constraint-based solution to the problem of inferring types, based on a simple implementation in EOPL (Friedman and Wand), but they elegantly side-step algebraic datatypes.

What I have so far works smoothly; if an expression e is a + b, e : Int, a : Int and b : Int. If e is a match,

match n with
  | 0 -> 1
  | n' -> n' * fac(n - 1)`,

I can rightly infer that the t(e) = t(the whole match expression), t(n) = t(0) = t(n'), t(match) = t(1) = t(n' * fac(n - 1) and so on...

But I am very unsure when it comes to algebraic datatypes. Suppose a function like filter:

let filter pred list =
  match list with
    | Empty -> Empty
    | Cons(e, ls') when pred e -> Cons (e, filter ls')
    | Cons(_, ls') -> filter

For the list type to remain polymorphic, Cons needs to be of type a * a list -> a list. So, in establishing these constraints, I obviously need to look up these types of my algebraic constructors - the problem I now have is the 'context-sensitivity' of multiple uses of algebraic constructors - how do I express in my constraint equations that the a in each case needs to be the same?

I am having trouble finding a general solution to this, and I am unable to find much literature on this. Whenever I find something similar - expression based language with constraint-based type inference - they stop just short of algebraic datatypes and polymorphism.

Any input is much appreciated!


texts:
If you designed a greedy algorithm to obtain an optimal solution and the algorithm can produce different combinations of values but still, any of theses combination is an optimal solution. How you prove it is optimality?

For example you have a set of numbers $\mathcal{M}=\{1,2,3,4\}$ and you want to design an algorithm to obtain the minimum number of integers required to obtain a sum 5. In this case, $1,4$ or $2,3$ can produce 5 and both are optimal solutions as the minimum number required is two.

How to prove the optimality of the algorithm ?

I tried by contradiction an assume that there is an optimal solution $P^*$ and my algorithm doesnot produce an optimal solution $P$ so $P \neq P^*$. but I donot know how to continue the argument.


texts: Algorithm for generating all unlabeled trees with n nodes?

texts:
How can one generate all unlabeled trees with $\le n$ nodes?

That is, generate and store the adjacency matrices of those graphs? (not just count them)

Visualization of all unlabeled trees with $\le6$ nodes:


texts: Time Complexity of Basic Primality Test Algorithm

texts: The algorithm I'm referring to is one of the most fundamental primality checks: For a number, $n$, check if it is divisible by some odd number, $k$, less than or equal to $\sqrt{n}$. Assume $n$ is a fixed size and that all basic arithmetic operations (add, subtract, multiply, divide, remainder) run in $O(1)$. I don't see why this algorithm will not be $O(\sqrt{n})$, but apparently it's not since PRIMES was considered an NP problem up until the AKS primality check.


texts: how to understand the occurrences of free variables?

texts:
I am thinking that many example only takes free variable with one occurrence, such as  $(\lambda x.x )y$ where $y$ is free.

can we say $y y $ is a $\lambda$-term and two $y$ are same free variable?
I did not see such examples so far, just wondering.


texts: Does each assembly language correspond to one instruction-set-architecture?

texts:
This is a quote from wikipedia:

  Each computer architecture has its own machine language. Computers differ in the number and type of operations they support, in the different sizes and numbers of registers, and in the representations of data in storage. While most general-purpose computers are able to carry out essentially the same functionality, the ways they do so differ; the corresponding assembly languages reflect these differences.

However, “computer architecture” is often meant to denote “instruction set architecture”. If that is what is meant here then I understand the quote. Or do we need multiple assembly languages for different architectural implementations of the same instruction set?


texts: Complexity of solving fractional constrained set multicover

texts:
Recently, I've encountered the following problem:
Given a collection of sets $S_1 \dots S_n$ of elements $e_1 \dots e_k$ with element $e_k$ denoted privileged, and a $k-1$-vector $r$, choose at most $m$ of the $n$ sets to maximize the number of times the privileged element $e_k$ occurs in the multiset union of the chosen sets, subject to that each other element $e_i$ must occur at least $r_i$ times in that union. Each set in the collection can be chosen at most once, but the collection may contain duplicate sets.
This can be reduced to solving a constrained set multicover problem (CSMP) with various values of $r_k$ to determine the maximum possible value that keeps the minimal number of sets at or below $m$.
In my context, taking a fractional amount of a set is allowed (e.g. taking 0.1 of $S_1$ counts as contributing 0.1 towards the capacity constraint of every element that's in $S_1$, and towards the maximum $m$ constraint). The fractional version of either the privileged cover problem or the CSMP can be cast as a linear programming problem and thus solved in polynomial time.
Now here's my problem: in my context, $n$ can be on the order of millions, while $m$ is on the order of hundreds. So while linear programming works and is polytime, it would be very slow in practice. I've been trying to find out how either my problem or the CSMP can be solved more quickly, but I've not had any luck. All I can find is information about how to use duality to approximate the integral version of the CSMP, which doesn't seem to be applicable here.
What is known about the complexity of solving the fractional CSMP or set covering problems in general? Are any faster algorithms than LP known to exist for either the fractional CSMP or my privileged cover problem? And if not, what kind of theory is applicable to determining whether such algorithms exist?


texts: How does the cache / memory know where to return results of read requests to?

texts:
The pipeline of a modern processor has many stages that may issue read
requests to main memory, e.g. in fetching the next command or loading
some memory location into a register. How is the result of a read
request returned to the right pipeline stage, given that there are more than one possible recipients?
Since most CPUs access main memory via a cache hierarchy, the question
becomes: how does the L1 cache know which part of the pipeline to
return a result to?
I imagine that access to the L1 cache is queued, but each access
presumably needs a 'return address'. How is this typically handled?
Processors tend to have a LSU (= load-store unit), see [1, 2] for example, but those descriptions tend not to mention how  read data finds its recipient.

RISC-V Boom, The Load/Store Unit (LSU).

Arm, Load Store Unit (LSU).


texts:
Okay I am trying to understand the Heap's Algorithm from the original research paper published by B.R Heap.

The most confusing aspect I found that while Heap says that the example described on the first page takes N=12 ie. example with 12 objects to provide a permutations for them.

But yet he says that the 12 objects are the letters A to Q. Now unless I have forgotten my counting totally, A to Q is 17 objects not 12. So am I missing something obvious ?

Secondly, can someone please explain the Table 1 given in the bottom of the first page ?

Thanks.


texts: What are the characteristics of a $\Theta(n \log n)$ time complexity algorithm?

texts:
Sometimes it's easy to identify the time complexity of an algorithm my examining it carefully. Algorithms with two nested loops of $N$ are obviously $N^2$. Algorithms that explore all the possible combinations of $N$ groups of two values are obviously $2^N$.

However I don't know how to "spot" an algorithm with $\Theta(N \log N)$ complexity. A recursive mergesort implementation, for example, is one. What are the common characteristics of mergesort or other $\Theta(N \log N)$ algorithms that would give me a clue if I was analyzing one?

I'm sure there is more than one way an algorithm can be of $\Theta(N \log N)$ complexity, so any and all answers are appreciated. BTW I'm seeking general characteristics and tips, not rigorous proofs.


texts: Situations where Kleene star of A is context-free, but A is not

texts:
This question appeared on my Theory of Computer Science final:

True | False: $A^*$ is context-free $\implies$ $A$ is context-free.

My professor says the answer is false, and I believe him, but am having trouble constructing a counterexample or even just convincing myself why. It seems to me that if a grammar can describe repeated concatenation, there must be some nonterminal that is concatenated.

Does anyone have a counterexample?


texts:
Show that: $\Theta(n\log n)\cup o(n\log n)\neq O(n\log n)$

I tried to start this in many ways but I don't really know how... intuitively isn't $\Theta \cup o = o$? So that would mean that I would have to just show that $o(n \log n) \neq O(n \log n) $  Which would be easier I think. But I don't know how to go about this formally..


texts: In the linear time selection algorithm which finds the ith smallest element in O(n) time our first step is to divide our unordered set into subsets of 5. Why is the size of the subsets chosen to be 5 and how would the algorithm be affected if I chose a different number. Nothing online describes why this number is the chosen subset size..


texts: If an instruction contains an address, how is it copied to the MAR?

texts: Since the Memory address bus is unidirectional, how is an address copied to the MAR if a previous instruction such as "STO 150" contains an address?  STO would store the contents of the accumulator in the address location 150.


texts: Non-regular language whose prefix language is regular

texts:
I understand that prefix of a regular language is regular, but I am unable to get my head around this:

  Give an example of a non-regular language $A ⊆ \{0, 1\}^*$ for which $\operatorname{Prefix}(A)$ is regular.


texts: CTL - model checking for formula $A [a \cup b]$

texts:
I'm trying to verify if the following model satisfy $A [a \cup b]$:

The algorithm I'm using is taken from "Concepts, Algorithms, and Tools for Model Checking", Joost-Pieter Katoen. In particular I applied the SatAU part (previous calculation of the states in which a and b are valid):

Intuitively the formula is verified in state $\{s_1, s_2, s_3, s_4\}$ (so the model does not satisfy the property because the set doesn't contain the other initial state $s_0$).
But if I apply the algorithm above the only state that I get are $\{s_2, s_3, s_4\}$, because the condition to generate the new $Q$ set (row 7) says to take a state s only if it has a connection with EACH element of the old $Q$ set.
Is it correct my interpretation of the algorithm? How can I get also $s_1$ from the algorithm?


texts: How to prove "The power set of a countable set must be uncountable"?

texts:
I'm not sure if this statement is correct, but my friend said so.

The problem arose from this T/F question:
Let $F=\{f: f$ be a primitive recursive function from $\mathbb{N}$ to $\mathbb{N}\}$, then $2^F$ (Power set of $F$) is uncountable.

And its answer is True. The set of primitive recursive functions is countable, and I would like to know the proof to the statement above...I believe I've seen it somewhere in the book but can't find it now.

Thank you for your time.


texts: Is there a way to state Blum's speedup theorem in terms of Big-O (Landau) notation?


texts: How does a cache handle overwriting between 2 addresses in the same block?

texts:
Consider a byte-addressable cache with block size 16 bytes, bytes 0-15 form one block.
First I write an int(let's say 7) to address 0, so now bytes 0-3 contain the int 7. Now if I try to write another int(9) to address 2, then how does the cache handle this? Also if i try to read from byte 1, what effect does that have?

The lectures I'm watching suggest treating a block as the atomic unit in a cache, because keeping track of all the unwritten and written bytes will be a resource heavy task. So how will the above situation pan out? Will every block contain only 1 instance of data, with every write beginning from byte 0? because that is the only possible solution i can think of.


texts: Prove that this solution to the Closest 3-Sum problem always works

texts:
I was working on a Leetcode problem, 3Sum Closest. I came up with a solution but struck it down because I didn't think it could be correct. But, turns out it was. I want to know why.
Here's the problem, transcribed:

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

The top solution was basically this:

Sort the list.
Loop over each number using index i.
Pick j to be i+1, in other words, the leftmost number of the segment after i.
Pick k to be n-1, in other words, the rightmost number of the segment after i.
If the sum of the numbers at (i, j, k) are less than the target, then j++. Otherwise, k--.

But isn't it possible that we might prematurely increment j (or decrement k), dismissing it forever, when in fact it may have been the optimal pairing had we tried a different k (or j)?
It seems we'll never backtrack to check other combinations.
Can someone provide a minimal, intuitive proof of why such a case never occurs? I'm unable to come up with a counterexample, and I trust the experienced members of Leetcode, so I know I must be wrong, but I can't seem to prove it. I can prove it for the Exact 3-Sum problem, but I don't know how to work with inequalities.