texts: Solving a recurrence of uneven subproblems without Akra-Bazzi

texts:
I encountered the following recurrence relation in homework, for which we need to find its asymptotics: $$T\left(n\right)=T\left( \frac{n}{3} \right) + T\left( \frac{n}{6} \right) + 1$$
I observed it is possible to approach this relation with the method of Akra-Bazzi, however this method was not taught in class. Akra-Bazzi gives the result of  $\theta(n^p)$ where $p$ is the unique solution to $$\frac{1}{3^p}+\frac{1}{6^p}=1$$
However, since this was not taught, I would like to ask if there's a different method to tackle this exercise, or a way to find its asymptotics more constructively.


texts: If a comparison-based algorithm finds the ith smallest element, it also classifies all the elements as ≥a[i] or ≤a[i]

texts:
Suppose that an algorithm uses only comparisons to find the $i$-th smallest element in a set of $n$ elements. Show that it can also find the $i−1$ smaller elements and the $n−i$ larger elements without performing any additional comparisons.

I would like to show my solution. I ask you for checking it :)

Let $k$ will be $i$-th element.
Let's suppose that we don't know if element $x$ is larger or smaller than $k$
Then it is impossible to know if $k$ is the $i$-th element. Contradiction.

It is very short proof. I can't see reason that it is not correct.


texts: Recursive definition of sum of two numbers in terms of the successor function

texts:
This is a question from the book Data structures using C and C++ by Tenenbaum. Not a homework problem but self-study.

  Recursive definition of a+b, where a and b are non-negative integers, in terms of successor function succ defined as

  succ(int x)
      {
          return(x++);
      }

I have been thinking how is it possible? Can I change the function? I am not sure from the problem definition in the book. So how can this be done?


texts: P2P and C/S, is it possible to determine which one is more bandwidth consuming?

texts:
In peer-to-peer (P2P) networks nodes are interconnected with each other. In client/server (C/S) networks clients talks to the server. If in a C/S network clients also want to talk with each other (such as in a multiplayer online game), then clients would have to communicate through the server.

Given these, is it possible determine which architecture is more bandwidth consuming?


texts: Understanding the simulate of an IF loop program through a LOOP program

texts:
We have the following operation $\text{IF} \ x_i =0 \ \text{THEN} \ P \ \text{END}$. I want to simulate this using a $\text{LOOP}$ program. Here is what I have:
$$\text{IF} \ x_i = 0 \ \text{THEN} \ P \ \text{END} \  ≙
\begin{cases}
      x_j := 1; \\
      \text{LOOP} \ x_i \ \text{DO} \ x_j := 0 \ \text{END}; \\
      \text{LOOP} \ x_j \ \text{DO} \ P \ \text{END}
   \end{cases}
$$
The $\text{IF}$ program executes $P$ only when $x_i =0$, otherwise terminating. The $\text{LOOP}$ program takes $x_j$ and assigns it the value $1$. Then loops $x_i$ many times executing the program $x_j := 0$. Since no value has been assigned to $x_i$, this line is looped over $0$ many times. In the final line we loop once and execute the program $P$. Therefore, both the programs are equivalent.
So if we have $x_i = 3$, then we loop $3$ times, and each time we assign $x_j$ the value of $0$. After the third loop, the program terminates and never executes the program $P$. This is the same as the $\text{IF}$ program, which doesn't execute $P$ since $x_i \neq 0$. Is my understanding correct?


texts: Are partial recursive functions analogous to recursive languages or r.e. languages?

texts:
From Ullman and Hopcroft's Introduction to Automata Theory, Language, and Computation 1ed 1979:

  The assumption that the intuitive notion of "computable function"
  can be identified with the class of partial recursive functions is
  known as Church's hypothesis or the Church-Turing thesis.

  A problem whose language is recursive is said to be decidable.
  Otherwise, the problem is undecidable. That is, a problem is
  undecidable if there is no algorithm that takes as input an
  instance of the problem and determines whether the answer to that
  instance is "yes" or "no."

  Note that one TM may compute a function of one argument, a different
  function of two arguments, and so on. Also note that if TM M computes
  function f of k arguments, then f need not have a value for all
  different k-tuples of integers. ...

  In a sense,

  the partial recursive functions are analogous to the r.e. languages, since they are computed by Turing machines that may or
  may not halt on a given input.
  The total recursive functions correspond to the recursive languages, since they are computed by TM's that always halt. ...

How do these go together?

From the following first two quotes

The first quote says that computability can be identified with the class of partial recursive functions,
the second quote seems to say that computability can be identified with recursive languages.

Note that the second quote says about decidability while here I uses computability, so I assume that computability and decidability are the same or consistent concepts, but is it true?

Do they imply that partial recursive functions and recursive
languages are analogous to each other, as far as computability/decidability is concerned?
The third quote says that "in a sense",

the partial recursive functions are analogous to the r.e. languages
The total recursive functions correspond to the recursive languages.

Does the third quote contradict the implication from the first
two quotes as pointed out above in part 1?

In what "sense", does the third quote mean?

For my related confusion about the third quote, see
Do the Turing machines involved in Chruch-Turing thesis have to halt on all the inputs?


texts: Intuitive meaning of modal $\mu$-calculus formula

texts:
I am solving one of the past exams and I am not certain with my solution to one of the exercises. The exercise is asking to give intuitive meaning to modal $\mu$-calculus formula:

$$ \phi = \mu Z. \langle - \rangle tt \wedge [-a]Z $$

According to an article Modal logics and mu-calculi: an introduction by Bradfield and Stirling[1] the intuition behind $\mu$ operator is "finite looping". So my reasoning is following: on every path through states in $Z$ there must be only a finite number of transitions with labels different from $a$ and then we must reach a state which is both non-terminal (from the first condition) and all transitions from it are labelled $a$ (from finiteness).

Hence on every path through states in $Z$ there must eventually be a transition labelled $a$. (similar to CTL formula $\forall F(a)$).

Is my reasoning correct? I am unable to find any formal reason for my solution to be right, can you give me a little hint?

[1] http://homepages.inf.ed.ac.uk/jcb/Research/bradfield-stirling-HPA-mu-intro.ps.gz


texts: Why in simulated annealing, thermal equilibrium need to be meet for each temperature throughout the iterations?

texts:
I have read in this book, simulated annealing, on page 40-41, if temperature $t$ tend to $0$, then the stationary distribution will be distributed among optimal solutions. What i can not understand here is that, if with temperature $0$, the stationary distribution will be distributed among optimal solutions, so why we need to have initially large temperature and reduce it slowly, so that at each temperature, the algorithm reaches the thermal equilibrium? Why do not we set the temperature to $0$ at the start of the algorithm and iterating until reaching thermal equilibrium for temperature $0$.

Form physical point of view, i know that, if in the annealing process, the temperature reduced quickly, the meta-stable amorphous structures will be reached rather than the low energy crystalline lattice structure. But from theoretical point of view, i can not understand the depth of the subject.


texts: How to simulate backreferences, lookaheads, and lookbehinds in finite state automata?

texts:
I created a simple regular expression lexer and parser to take a regular expression and generate its parse tree. Creating a non-deterministic finite state automaton from this parse tree is relatively simple for basic regular expressions. However I can't seem to wrap my head around how to simulate backreferences, lookaheads, and lookbehinds.

From what I read in the purple dragon book I understood that to simulate a lookahead $r/s$ where the regular expression $r$ is matched if and only if the match is followed by a match of the regular expression $s$, you create a non-deterministic finite state automaton in which $/$ is replaced by $\varepsilon$. Is it possible to create a deterministic finite state automaton that does the same?

What about simulating negative lookaheads and lookbehinds? I would really appreciate it if you would link me to a resource which describes how to do this in detail.


texts: Minimize Contrast Votes Where People Have Two Choices

texts: Imagine that in a community people either vote to A or B and each of them have an initial vote, they may  change their vote in order to the majority of their friends vote. If we have the initial vote of each person and we have the friends of each person what would be the minimum of (number of friend pairs disagree each other + number of persons who vote different from their initial vote)


texts:
In Chapter 23 of CLRS, the following quote appears:

  We also assume a limit on the size of each word of data.
  For example, when working with inputs of size $n$, we typically assume that integers are represented by $c \lg n$ bits, for some constant $c ≥ 1$.

Here is how I understand the text:
I searched on the Internet about what does a word of data means. Turns out that a word of data is a data unit used by processors. Different processors have different definitions on a word of data. For example, processor A takes 16 bit as a word of data while processor B takes 24. I think of a word of data as a box, placed in the RAM. We assume a limit of the size of whatever inside the box.

I am so worried about if my understanding is wrong, as I have a strong feeling that it is. The problem is I can't seem to find a better explanation of the text than this one.


texts: Are weakly polynomial time algorithms truly polynomial?

texts:
I've been looking through a ton of sources to try and understand the definitions of strongly and weakly polynomial time algorithms. Wikipedia
states an algorithm runs in strongly polynomial time if

  the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
  the space used by the algorithm is bounded by a polynomial in the size of the input.

A weakly polynomial time algorithm is then just an "algorithm that runs in polynomial time but that is not strongly polynomial."

What I'm confused about is how weakly polynomial time algorithms can actually be said to be polynomial. As stated in this post in reference to weakly polynomial time algorithms,

  The algorithm is already polynomial time in the arithmetic model, so as long as its space is bounded in the TM model then the rest of the algorithm is still polynomial time in the TM model.
  Think of it like this, when converting from the arithmetic model to the TM model, the only thing that can go wrong is the space. The numbers you produce need to be representable in a number of bits that is polynomial in the number of bits in the input. So long as that holds, the rest of the algorithm is still polynomial time in the TM model.

I understand the difference between the arithmetic model and the TM model. But this quote and the wikipedia definition itself seem to imply that a weakly polynomial time algorithm will not run in polynomial time on a TM. This being because (to my understanding) if the space being used isn't bound by a polynomial in the size of the input, just the time spent allocating the space necessary to run the algorithm on a TM eliminates any hope of polynomial time. The classic example is in the post I linked above and the Wikipedia article and involves calculating $2^{2^n}$ given $2^n$.

So how can we say weakly polynomial algorithms are still polynomial? There seems to be a consensus that weakly polynomial is better than pseudo-polynomial, but aren't they both not polynomial on a TM?

Edit: I would also like to add that confusingly this post states that

  Consider running either one on a Turing Machine. Both will run in a number of steps polynomial in the length of binary-encoded input.

This seems to contradict the previous post I linked which states

  Any strongly-polynomial time algorithm can be converted into a polynomial time algorithm on a TM by replacing the arithmetic operations with equivalent algorithms in the TM model.

suggesting that the difference is weakly polynomial time algorithms don't run in polynomial time on a TM. Either I'm missing something fundamental or multiple definitions seem to be floating around.


texts: Maximum value reached in extended binary GCD

texts:
Given positive integer inputs $x$ and $y$ , with $0<x<y$ and $y$ an odd prime (or $\gcd(x,y)=1$ and $y$ odd), the following algorithm computes $x^{-1}\bmod y$ per the (half-)extended binary GCD. All quantities are non-negative.

What's an upper bound of the value internally reached by integers $a$ and $d$ , as a function of input $y$ ? I'm content with a number of bits: the objective is deciding a number of words for $a$ and $d$ when dealing with $y$ in the order of 256 bits.

If $x$ is odd then $u\gets x$ ; else $u\gets x+y$ ;
$v\gets y$ ; $a\gets0$ ; $d\gets p-1$ ;
While $v\ne1$
[invariant here and at start of the next while loop: $u$ and $v$ are odd and distinct]

While $v<u$

$u\gets u-v$ ; $d\gets d+a$ ;
While $u$ is even (that's at least once)

If $d$ is odd then $d\gets d+y$ ;
$u\gets u/2$ ; $d\gets d/2$ ;

$v\gets v-u$ ; $a\gets a+d$ ;
While $v$ is even (that's at least once)

If $a$ is odd then $a\gets a+y$ ;
$v\gets v/2$ ; $a\gets a/2$ ;

$a\gets a\bmod y$ ; that's the desired inverse.

Note: I'm aware that by changing $a\gets a+y$ to:
   if $a<y$ then $a\gets a+y$ ; else $a\gets a-y$ ;
and same for $d\gets d+y$ , we keep $a$ and $d$ below $4y$ ; I'm asking what if we do not.

There's a similar upper-bound issue in the classical extended binary GCD algorithm using signed variables, as in the Handbook of Applied Cryptography's algorithm 14.61. This question's $d$ (resp. $a$) is similar in role to $-D$ (resp. $C$ and $a$) in that algorithm.

Update: I'm leaning towards $\max(a,d)<4y\log_2(y)$ or something on that tune, but fail to make a proof.


texts: PDA with N-Stacks comparison with Turing Machines

texts:
Is it possible to compare PDA having N-Stacks with Turning Machines. Are they equally powerful in this situation?

It's been told that PDA with 2-Stacks is equally powerful to Turning Machine. But what if we add more stacks i.e. 3, 4, 5...N to PDA; will it become more powerful or it can serve same purpose.


texts: Why do we simulate the universal TM to simulate another TM M instead of simulating M directly?

texts:
In the proof of the time hierarchy theorem given on page 69 of Arora-Barak, we define a TM D as follows:

"On input $x$, run for $|x|^{1.4}$ steps the Universal TM $\ \mathcal{U}$ of Theorem 1.9 to simulate the execution of $M_x$ on $x$." Here $M_x$ is the machine encoded by string $x$.

Since we are simulating another TM on $D$, this would implicitly make $D$ a universal TM, right? If this is the case, then why is it necessary to state that $D$ will simulate $\mathcal{U}$ in order to simulate $M_x$ when $D$ is already capable of simulating $M_x$ directly?

On the other hand, if it is not the case that $D$ is a UTM, then why can't we "run" (whatever that means) $M_x$ directly on $x$ instead of running $M_x$ through $\mathcal{U}$ (in the same way that we "run" $\mathcal{U}$)? Why do we need to simulate a machine capable of simulating an arbitrary TM if we only need to simulate exactly one TM?


texts: Are there automatic transformation of grammar algorithms?

texts:
From time to time you can write a grammar that creates shift/reduce conflict (for example) but after reading the grammar you notice that if you rewrite the productions the conflict will go away, despite the fact that the rewritten grammar is obviously equivalent and accepts exactly the same language.

Are there some automatic transformations of the grammar to avoid conflict? Something (just an analogy) as left recursion elimination in LL parsers?

For example, here is a trivial example of two grammars:

...
deco_symbol -> anon_symbol | named_symbol;
...

and

...
symbol -> anon_symbol | named_symbol;
deco_symbol -> symbol;
...

For LR(1) parser such indirection can be crucial and second form can introduce conflicts (it did in real life).

Since I asked this question I wrote automatic removal of identity production and it helped, so this would be the first type of transformation I know it is helpful. Now I am testing wrapper production removal and empty productions as well.


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

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

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

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

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

Q) Deriving the expected number of steps that is taken to perform the k'th operation

This would be the average of all possible events so number of search and prepends to the expected length. Expected length is given to be p (k-1). Derived from below

expected length of linked list

search takes i steps (probability 1-p). Prepend takes 1 step (probability is p ).

$E(X) = search(1) + search(2) + \cdots + search((p(k-1)))$

Not sure how to get an exact value for it


texts: How to build a system for configuring a large variety of data sources?

texts:
I'm working on a project where my application has to ingest data from a huge number of different data sources. Each of these data sources has their own mechanism for auth (usually OAuth2, but not always), some send metadata and require a callback, some have "resources updated_since" type endpoints that need to be polled periodically, some required waiting on a data export to finish, and then collecting that data. There are a bunch of different ways in which we might be sent data, and there are many more coming.
Note: The data sources themselves are partners, so it's possible to push some of the work onto their side, as long as the mechanism for having them send data doesn't seriously affect the way their systems work.
Possible solutions
Build an integration for each data source
This seems overkill, and would introduce a lot of redundancy. Trying to avoid this.
Build a configuration abstraction API(s)/UI
Token management
For example, I could imagine a simple endpoint for configuring auth for a data source. Eg: here's the token refresh endpoint, here's the client_id and secret, here's the token lifespan etc. And then our system would just manage all those tokens automatically.
Data source config
Things get more complex on the actual data source side. It seems like creating a configuration system with a bunch of different modular steps might make sense, eg: step for receiving a list of IDs, step for querying a specific ID, step for polling a data generation status endpoint, step for collecting updated_since data on a particular interval etc.
Final Thoughts
Are you aware of any companies/systems similar to this? Are there certain design patterns that make sense here? Any gotchas to be aware of?


texts: Find total count of all paths starting from a fixed vertex to all other vertexes of the graph

texts:
Given an directed graph (may contain cycles) we have to find total number of simple paths from a fixed source vertex to all other vertices of the graph, i.e.

$$
\text{#(paths from 1 to 2)}+\text{#(paths from 1 to 3)}+\cdots+\text{#(paths from 1 to $n$)}.
$$

We have to find this in linear time, as number of vertexes can be as large as 100000. I tried using DFS in this question to generate all the paths and keeping up count of these but this is not fast enough.

Is there any mathematical formula for this?

P.S. I am only interested in total number of paths, not generating all the paths. Each vertex has up to 4 or 5 edges.

For example, if the adjacency matrix of a 4 nodes graph is like this:

  A B C D
A 0 1 0 0
B 1 0 1 1
C 0 1 0 1
D 0 0 1 0

Then the number of paths are

from A to B: 1
from A to C: 2
from A to D: 2
therefore 5 paths

So I want the answer to be 5.

The edges may be unidirectional or bidirectional and I want to find only simple paths.


texts: Counting the number of words accepted by an acyclic NFA

texts:
Let $M$ be an acyclic NFA.

Since $M$ is acyclic, $L(M)$ is finite.

Can we compute $|L(M)|$ in polynomial time?

If not, can we approximate it?

Note that the number of words is not the same as the number of accepting paths in $M$, which is easily computable.

Let me mention one obvious approach that doesn't work: convert the NFA to a DFA (which will also be acyclic), then count the number of accepting paths in the DFA.  This doesn't result in a polynomial-time algorithm, since the conversion can cause an exponential blowup in the size of the DFA.


texts:
There seems to be a classification of processes in IT. For example, "business process" refers to the collection of tasks done by organization members / software systems to achieve a goal.

If a process is completely automated and carried out by software (no people involved) what is the process called? Say we have a Web service A and service B online and we have a process that automatically uses both in achieving a goal.

I googled for "Software process" but the results are not what I am looking for (e.g waterfall)

My apologies if this is not the correct forum to ask this question.
Thanks in advance


texts: Is it possible to solve the Mountain Car reinforcement learning task with linear Q-Learning using the state as direct input?

texts:
I'm trying to solve the Mountain Car task on OpenAI Gym (reach the top in 110 steps or less, having a maximum of 200 steps per episode) using linear Q-learning (the algorithm in figure 11.16, except using maxQ at s' instead of the actual a', as required by Q-learning; I've solved it with other methods easily, the question is about linear Q-learning). Also, I'm using 1 output for each action, so I can select an action in a single forward pass. Important: my input features are the identity function of the state, i.e., the state variables themselves. I know it can be solved with other features, I want to know about this one specifically.

Here is a description of the algorithm I'm using: https://youtu.be/vVDKzIxzkzQ

Unfortunately, this method never solves the task. Actually, it rarely reaches the top. I'm aware that vanilla Q-learning has no convergence guarantees, so I tried some variants which reduce or even solve this issue: I've tried experience replay, double q-learning, GTD and advantage learning. Nothing helped.

I know that this task can be solved linearly on the state inputs directly, since I've done it by manually tuning the weights so the car always apply the force in the same direction as its velocity, so the representation is not an issue. But it seems that the learning algorithm is.

So the question is: is linear Q-learning able to learn the mountain car task directly from the state variables? A paper where the author solves this task with Q-learning in a single-layer network (and shows the algorithm or code) with features = state variables would be enough.


texts: Why does a suffix tree have a linear number of nodes (relative to input string size)?

texts: Aren't there $n^2$ unique substrings of a string (irrespective of the alphabet size)? Perhaps the number of unique suffix substrings is less than the number of unique substrings of a string.


texts: Minimum sum of squared Euclidean distance between two arrays

texts:
Question:
Given two sorted sequences in increasing order, $X$ and $Y$. $Y$ is of size $k$ and $X$ is of size $m$.
I would like to find a subset of $X$, $i.e$, $X'$ of size $k$, and considering the following optimization problem:$$d(Y,X') = \sum_{j=1}^{k}(y_{j}-x'_{j})^{2}$$ And $X'$ is a subset of $X$ of size $k$, $y_{j} \text{ and } x'_{j}$ is element in $Y$ and $X'$. I would like to find the subset of $X$, to reach the minimum of $d(Y,X')$.
Note that $X'$ could have $k!$ numbers of arrangements, so its order is totally unknown.

What I have came up with so far:
I would like to approach it using Dynamic Programming, and I think I would first compute the squared distance between each element in $Y$ and $X$, but I'm having trouble in determining what is the subproblem and how to solve ths using DP. Thank you!
Update: The $X'$ could be sorted, which means we could aim at finding a sorted subset of $X$.


texts: Find distinct groups with no common parents

texts: Given an array $arr$, element $arr[i]$ indicates its parent. If the element has no parent then $arr[i]=-1$. What is the optimal algorithm for finding the minimum number of groups such that no element in each group is a child node (whether directly or indirectly) of any other node in the same group.


texts: Finding upper bound on number of I/Os needed to generate all permutations of some input in external memory

texts:
The general approach outlined in this paper in its proof of the lower bound on the average number of I/Os needed to obtain a given permutation of some input in external memory is as follows. Note that $N$ is the number of items to be permuted and $t$ has no prior definition in the paper.

Why are they trying to find the value of $t$ for which the bound on the number of possible permutations generated after $t$ I/Os is only $\frac{N!}{2}$ instead of $N!$? I realize that $\frac{N!}{2}$ gives the number of orderings of $n$ elements, but just because you can obtain one permutation after $t$ I/Os does not necessarily mean that you can obtain its reverse permutation after $t$ I/Os.


texts: Row polymorphism, union and intersection types

texts:
It seems that row polymorphism with union types can be used in dynamic languages to approximate overloading, e.g. given the following python function:

def f(foo, o):
    if foo:
        return o.x
    return o.y

Depending on the value of foo, the type of o could be $\forall \alpha, \left. \rho_1 \middle/ x \right.. \{x: \left. \alpha \mathrel{}\middle|\mathrel{} \rho_1 \right.\}$ or $\forall \beta, \left. \rho_2 \middle/ y \right.. \{y: \left. \beta \mathrel{}\middle|\mathrel{} \rho_2 \right.\}$, where $\alpha$ and $\beta$ are regular type variables, and $\rho_1$ and $\rho_2$ are row variables, lacking an $x$, respectively $y$ label. It would seem natural to extend this system to give f the type $\forall \alpha, \beta, \left. \rho_1 \middle/ x \right., \left. \rho_2 \middle/ y \right.. \{x: \left. \alpha \mathrel{}\middle|\mathrel{} \rho_1 \right.\} \cup \{y: \left. \beta \mathrel{}\middle|\mathrel{} \rho_2 \right.\} \rightarrow ()$, where $\cup$ stands for the union of the two types.

On the other hand I have seen intersection types used for the same purpose, e.g. f could be typed as $\forall \alpha, \left. \rho_1 \middle/ x \right.. \{x: \left. \alpha \mathrel{}\middle|\mathrel{} \rho_1 \right.\} \rightarrow () \wedge \forall \beta, \left. \rho_2 \middle/ y \right.. \{y: \left. \beta \mathrel{}\middle|\mathrel{} \rho_2 \right.\} \rightarrow ()$ where $\wedge$ stands for the intersection of the two types.

What is the difference between the two approaches? Which would be better for a type inferred system?  What I'm interested in is if the two approaches are equivalent, i.e., they allow the same set of programs to be typed correctly, and which one is more amiable to type inference, if any.


texts: Self-balancing BST supporting in-order-sequential multi-insertions / multi-deletions in logn+klogk time?

texts:
Given a self-balancing binary search tree of size $n$, I want to perform the following operations:

InsertInOrderSequentialBatch an ordered sequence of $k$ values (specialized $k \in \{2, 3, 4\}$ or generalized $k \in N $) which are guaranteed to be sequential in an in-order tree traversal immediately after insertion.

For example, insert $[310, 320, 330, 340]$ into a balanced tree containing $[100, 200, 500]$.

Future insertions might still be between the inserted nodes' values.

DeleteRange all of $k$ nodes (likewise specialized or generalized) between 2 values in the BST.

For both operations, I want the tree to remain balanced.
With a Red-Black or AVL tree, I can achieve both operations through a sequence of $k$ insertions/deletions in $\mathcal{O}(k \log n)$, but wonder if a data structure (e.g. AVL/RB tree variant) could achieve $\mathcal{O}(\log n + k \log k)$ time for a real-world performance gain (e.g. traverse tree for insertion point, insert balanced tree into insertion point, perform one auto-balance pass)?
My needs are less theoretical and more in terms of wall-time & memory pressure for an implementation of Fortune's Algorithm - an algorithm with high constant-time multipliers is unfortunately not useful. My insertion sequence is biased & frequently multimodal (modes not known prior) with long streaks of insertions/deletions within modes. My tree size is anywhere from 100 to 3000 nodes.


texts: Is there a closed-form formula for this recursive sequence?

texts:
Let $k > 0$ be an integer.

Define $A_n$ as follows:

$$ A_n = \begin{cases} n & \text{if } n < k, \\ \sum_{i=0}^{k-1} i & \text{if } n = k \\ \sum_{i=1}^k A_{n-i} & \text{if } n > k. \end{cases} $$

This looks much like Fibonacci, except it's linear up until the k-th term (so the G formula does not work). I am 99% sure there is a closed formula for this one, but can't seem to figure it out at the moment.

Any pointers will be appreciated!


texts: Reducing a Knapsack-type problem to a known problem

texts:
The Quadratic Knapsack problem, introduced by Gallo, is an optimization problem in the following form:

$max \sum_{i=1}^n{\sum_{j=1}^n{q_{ij}x_ix_j}}$

$s.t \sum_{i=1}^n{w_ix_i} \leq c$

$x \in \{0, 1\}^n$

Where $n$ is the number of items, $c$ is the capacity (positive and integral) of the knapsack, $w_i$ are the positive and integral weights of the items and the $q_{ij}$ are the non-negative and integral profits.

I am trying to solve a problem whose closest cousin might be the quadratic knapsack problem or some other sort, but it has been difficult for me to reduce this problem to some known problem.

Modifications I need

Consider a directed acyclic graph that will describe relationships between nodes.  Whenever node $i$ appears by itself, the profit will be $q_{ii}$. But if for some reason an ancestor $j$ of $i$ (as defined by the directed acyclic graph) appears in the solution together with $i$, then I have $q_{ij}=-q{jj}$.  Also, if more than one ancestor of $i$ appears in the solution together with $i$, I want to only apply the discount of the ancestor of $i$ closest to $i$.

Do you have any pointers to a known problem to which I could reduce my problem? Any help would be greatly appreciated.  And please, if you can put better tags to this question than the ones I placed, feel free to edit them.

EDIT to the question
The matrix $Q$ is given, as well as the values of $w$.  The values that I am looking for are the values of $x$ that maximize the total profit.  This total profit is defined in the section Modifications I need


texts: What would be an efficient method to find the kth smallest element in an array with worst case time complexity being $ O(n) $?


texts:
Given a matrix $A$ and a vector $v$, I'm aware there are efficient algorithms for computing $e^Av$, where efficient means significantly faster than computing $e^A$ and multiplying by $v$. For a diagonal matrix $D$, is there a similarly efficient algorithm to compute $$ e^A \cdot D = \sum_i (e^A)_{ii} D_{ii}?$$
In particular, is there an efficient way to compute the trace of the exponential?


texts: Who first introduced the pushdown automaton?

texts: I'm interested in learning more about the history of automata theory and have tracked down many of the original papers on Turing machines, finite automata, and the like. However, I'm having trouble finding a source that first introduces pushdown automata. Who first developed them, and what was the context?


texts:
My understanding of the Y-combinator is that it never terminates (Yg = g(Yg)). Its termination is only decided externally to the $\lambda$ specification when it has reached a fixed point (g(x)=x) because based on its $\lambda$ expression there is no exit from the infinite loop even when the fixed point is reached.
Am I wrong?


texts: RAM can be accessed hundreds of times faster than a hard drive. Explain How?

texts:
I have been reading this for quiet a long time that "RAM can be
accessed hundreds of times faster than a hard drive".
But, no one has been able to explain it properly.
I searched on Internet and found that "Access time of RAM is faster because they have less addresses(~4GB RAM) than Hard Drive(~1TB), and therefore address-resolution is faster".

Please guide me on this topic.


texts: What are some of the best circuit separations that we know of and that we suspect?

texts:
We know that $\mathsf{non-uniformAC^0\subsetneq PSPACE}$, $\mathsf{non-uniformACC^0\subsetneq NEXP}$. We know that $\mathsf{uniformACC^0=PH}$ is a possibility.

What are some of circuit separations that we know of?

What are some circuit separations that seem farthest apart but cannot be separated? By this question I mean that even though $\mathsf{uniformTC^0\subsetneq PH}$ is a possibility, an answer with  $\mathsf{uniformACC^0\subsetneq PH}$ suffices since $\mathsf{uniformACC^0\subsetneq uniformTC^0}$ is hypothesized.


texts: Is this solution to the dining philosopher's problem entirely valid?

texts:
In a question on Stack Overflow, the answer by Patrick Trentin lists the following solution to the dining philosopher's problem:

  A possible approach for avoiding deadlock without incurring
  starvation is to introduce the concept of altruistic philosopher, that
  is a philosopher which drops the fork that it holds when it realises
  that he can not eat because the other fork is already used.

  Having just one altruistic philosopher is sufficient in order to avoid
  deadlock, and thus all other philosophers can continue being greedy
  and attempt to grab as many forks as possible.

  However, if you never change who is the altruistic philosopher during
  your execution, then you might end up with that guy starving himself
  to death. Thus, the solution is to change the altruistic philosopher
  infinitely often. A fair strategy is to change it in a round robin
  fashion each time that one philosopher acts altruistically. In that
  way, no philosopher is penalised and you can actually verify that no
  philosopher starves under the fairness condition that the scheduler
  gives a chance to every philosopher to execute infinitely often.

I was intrigued by this solution because I hadn't heard it before. However, I can find no references to it anywhere in the existing literature.

I did a quick check, and saw that it isn't listed on Wikipedia as a standard solution.
Googling 'altruistic philosopher dining' yields only one result from Google Books that does not discuss the round robin strategy and only vaguely alludes to the altruistic philosopher to talk about the perils of starvation.
I tried looking up altruistic philosopher on ArXiv, only to return no results.
Trentin cites a book about nuXmv, a symbolic model checker, as his source but only provides a link to his own lab slides.

So my question: does this naive yet seemingly remarkable solution actually work? Or are there pitfalls that have been overlooked? I find it hard to believe that, if it works, it wouldn't have at least some mention somewhere - but at the same time I can't see why it wouldn't work, as it's a fairly naive solution.

If it does work, can I either a) have a reference to a proof, or b) an actual proof that this solves the dining philosopher's problem? If it doesn't, same standards apply, except for the negation of a proof. :)


texts: DFA: Can the set of States Q be empty by definition?

texts:
Can the set of states Q be empty by definition?

I was wondering about this question when doing exercises in the pumping lemma for finite automaton.


texts: What advantage do quadratic basis functions have over gaussian basis functions in RBF implementations?

texts:
I've been reading up recently on radial basis functions, and I've recently moved from Gaussian basis functions of the form $\phi(x)=\exp(-\alpha||x-x_i||)$ to multiquadratic basis functions. My source is this paper, which is referenced in an algorithm that I'm looking at.

The basis function for the multiquadratic RBF is given as $\phi(x)=\sqrt{||x-x_i||^2+R^2}$, where $R$ is a shape parameter. While it's certainly possible to solve the set of linear equations in a basis function and get a valid result for any equation, this choice of basis functions seems odd. Compared to a Gaussian basis function, where the effect of a basis function with a large value of $||x-x_i||$ approaches zero, multiquadratics grow increasingly rapidly as the radius increases.

Intuitively, this seems like a strange choice for a basis function, since distant points in a training data set would seemingly influence the results of a local solution more than nearby points. Why is this function used as a basis function, and what advantages does it have over something like a Gaussian basis function?


texts: O(1) algorithm to get approximate number that is larger as a binomial coefficient

texts: Ideally I need a to calculate the binomial coefficient ${p \choose n}$. But since the fastest algorithm to do this is an $\mathcal{O}(n)$ algorithm I would look to do something different. I don't really care for the exact number as long as it is reasonably close and is at least equal or larger then the actual number. My number should be within a factor of 2 of actual binomial coefficient. Is there an $\mathcal{O}(1)$ way to compute such a number?


texts: Bayes theorem probaility doesn't make sense

texts:
I try to use Bayes Theorem to calculate the probability of $P(A|B)$. I have $P(A)$ in column1, $P(B|A)$ in colmn2, $P(B)$ in column 3. I get the following:

my calculations were:

$$P(B/A) = 0.8\times A$$
$$P(B) = (Bx*0,55)+((1-Bx)*(0,55))$$
$$P(A/B) = (Ax*Bx)/Cx$$

The probability gets above 1. What am I doing wrong?


texts: DFA for a strings whose every subsequence of length five has at least two zeroes

texts:
I have a regular language consisting of such {0,1}^k sequences, in which every subsequence of length 5 has at least two 0's in it (which also means every sequence of length <5 is 'good'). I need to find a DFA which generates this language.

I can't say I tried everything, but each time I encountered the same problem, that is it always generated a subsequence of the form 11111... (I tried incorporating each subsequence of length 5 with two 0's in my DFA so that the last element returned to the beginning of the automaton, but this resulted in accepting 'bad' subsequences - for instance 00111 and 11100 were 'good', but 0011111100 wasn't).

Is there any way to do it?


texts:
Consider the following desicion problem:
3-Hitting Set - This problem is indentical to the classic Hitting Set problem with the following constraint: Each set has to be exactly 3 items long. Similarly to 3-SAT and SAT, It seems almost obvious that 3-Hitting Set is also NP-complete like the original Hitting Set problem. Is it possible to reduce the original Hitting Set problem to the 3-Hitting Set problem directly, or we must go through a third NP-complete problem?


texts: Generate string with large Kolmogrov complexity

texts:
Given $c$, can you generate a string $s$ with $K(s) \ge c$, along with a proof of that fact?

I think the answer is no except for small $c$, but I'm not sure.


texts: Verification condition in case of array theory

texts:
As far as i can understand the problem of checking safety property, can be reduce to solving for inductive invariants in VC's and there is following parts to it:

Generate VC's from the program.
Solve it: If user provide inductive invariants just check the Validity of the whole VC formula.
Inferring problem : simultaneously solve the VC's taking these predicates as uninterpreted function that make all the VC's valid.

How hard the problem of checking 2. (User provide the inductive invariant) in the case of array theory? For example: Array sorting.


texts: Find all pairs of nodes whose deletion disconnects graph

texts:
Given undirected, connected graph, find all pairs of nodes (connected by an edge) whose deletion disconnects the graph. There can't be an edge connecting a node to itself.

The problem seems similar to finding articulation points of a connected, undirected graph - yet with a twist, that we have to remove a pair of vertices connected by an edge (and all other edges connected to that pair).

This is a homework question. I might not be a smart student, but neither a lazy one. I will try to answer it below, and I would love for someone to verify my understanding of the issue.

I will be basing my solution of finding Articulation Pairs (AP) based on finding articulation points by this analysis: https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ and the DFS with additional bookkeaping of 'lowpoint' value for each node, where
lowpoint(v) is a minimal depth of non-parent adjecent node at the time of traversal
found here: https://en.wikipedia.org/wiki/Biconnected_component#Algorithms

Analysis:
1) u is root of DFS tree with at least three children. Then every pair (u, child(u)) is AP.
2) u is root with at least two children, one of which (v) has at least one child. Then every pair (u, v) is AP.
3) u is not a root of DFS tree and it has a child v1 such that v1 has child v2, such that no vertex in subtree rooted with v2 has a back edge to one of the ancestors of u

Rephrasing 3):
(u,v) is AP iff:
- v is a child of u
- there exist child(v) such that lowpoint(child(v)) >= depth(u)

My questions are:
Did I miss any case? Is my reformulation of the issue sufficient for this problem?

@EDIT:
This solution/analysis completely doesn't work and at this point I have no idea how to approach this issue.


texts: How do I prove that entropy is maximal for $P(A_2) = \cdots = P(A_n) = (1-a) /(n-1)$ while $P(A_1) = a$ (a fixed number) and $A_1,…, A_n$ is a partition of the sample space?


texts: Does closure against countable union survive union of classes?

texts:
A class of languages $\mathcal{C}$ is closed under countable union (cucu) if for all series of languages in $\mathcal{C}$ ($(L_i)_{i\in\mathbb{N}} \in \mathcal{C}^\mathbb{N}$) the language $\bigcup_{i\in\mathbb{N}}L_i = \{x\mid \exists i\in\mathbb{N}: x \in L_i\}$ is an element of $\mathcal{C}$.

As we know most (if not all but $\mathsf{ALL} = \wp(\Sigma^*)$) interesting complexity classes are not closed under countable union as every Language $L$ is the countable union of some singleton Laguages $\{w_i\}$.

However there are some classes of decidable languages which are cucu like:

$\{\{w\in\Sigma^*\mid |w| \leq i\}\mid i\in\mathbb{N}\}$
$\{n\text{-}\mathrm{SAT}\mid n\in\mathbb{N}\}$
every $\mathcal{C}$ s.t. every $L \in \mathcal{C}$ is cofinite

My questions:

Let $\mathcal{C},\mathcal{C'} \subset \mathsf{REC}$ be two classes of decidable languages s.t. both are cucu. Is $\mathcal{C} \cup \mathcal{C'}$ cucu?
Is there some "real" complexity class (i.e. defined by some machine model, grammar type, $\lambda$-calculus restriction etc.) that is cucu? (You may restrict it artificially (e.g. NFA, where each final state has a path to another final state), if it fits otherwise.)
Edit (after Yuval Filmus' answer): Given $\mathcal{C},\mathcal{C'}$, as in (1), does the closure of  $\mathcal{C} \cup \mathcal{C'}$ under countable union only contain decidable languages?

(1) is the main question, (2+3) only addenda.


texts: Is the identity functor a kind of free object?

texts:
My understanding of free objects is: Free functors, free applicatives, free monads, free monoids, &c, give you more structure "for free", i.e. in general, or for all some thing with less structure, you can have more for free. For example, the free monad give you a monad instance for any type with a functor instance, even without its own native monad instance.

The Identity functor gives you a functor (and applicative, and monad) instance for any type. Therefore it seems to me to be a sort of free structure. Am I write about this, or am I confusing myself by my vague definition of free objects?


texts: Universal approximation bounds of the form $\|f(x)-\hat{f}(x;w)\|\leq \varepsilon \|f(x)\|$

texts:
It is known that for every $\varepsilon>0$ there is an appropriate neural network architecture, such that one can approximate any continuous function $f:[0,1]^n\to[0,1]^m$ by the neural network output $\hat{f}(\bullet;w):[0,1]^n\to[0,1]^m$ as:
$$
\|f(x)-\hat{f}(x;w)\|\leq \varepsilon, \forall x\in[0,1]^n \quad \quad \quad \quad \quad (1)
$$
My question is if its possible to derive a similar result, but with a conclusion of the following form: that for every $\varepsilon'>0$ there exists a suitable architecture such that the estimation $\hat{f}(x;w)$ (different from the one in (1)) complies
$$
\|f(x)-\hat{f}(x;w)\|\leq \varepsilon' \|f(x)\|, \forall x\in[0,1]^n\ \  \quad \quad(2)
$$
This is, the approximation $\hat{f}(x;w)$ gets better if the true output $f(x)$ is small.
I am not trying to show that (1) implies (2), but that there is $\hat{f}$ complying (2) by itself. This is a stronger result, since (2) can imply (1) for appropriate $\varepsilon,\varepsilon'$.
I'm not looking for complete proofs, but just some discussion and suggestions:
-Do you think a result of this form should be able to be proved?
-If (2) is too strong to be proved, what other condition could be feasible to prove, which correctly synthetize the statement "the approximation $\hat{f}(x;w)$ gets better if the true output $f(x)$ is small."?
-Do you have any suggestion on what to look for in order to proceed in the proof?
And one more. Do you think this question fits here, or should be posted at stats.stackexchange.com or math.stackexchange.com instead?


texts: Why use logic gates in this situation? (XOR gates)

texts:
I came across this circuit that swaps logical signals:

However I don't understand why would you need to use logic gates. Would it be possible to just connect the A on the left to the B on the right and the same with the B on the left (maybe add a diode to prevent current from going back?).

And one last question; would an "Enable" signal make this circuit more useful (only swaping when Enable is high)?

Maybe I'm missing something. Thank you.


texts: Sum of all distances in connected DAG in $O(n\log n)$

texts:
I have a DAG with $n$ nodes and $n-1$ edges. The edges in DAG (fixed) are defined as follows:  For every  node $i$, $1 \le i \le n-1$ is connected to node $i+1$. The lengths of the $n-1$ edges are given as input.

I need to compute the sum of all of the distances between all pairs of different vertices, i.e., to compute $\sum_{u<v} d(u,v)$, which is the sum of the distances for each pair $u,v$ such that $u<v$.

For example, suppose $n=4$, and the edge lengths are $1,1,1,1$.
Then the pairs along with their distance would be $(1,2):1,(1,3):2,(1,4):3,(2,3):1,(2,4):2,(3,4):1$, so the total sum of distances would be  $1+2+3+1+2+1=10$.

I tried Dijkstra's Algorithm (time complexity $O(n\log n)$) on every node  but the time complexity is $O(n^2 \log n)$ which is inefficient. Is there a way to reduce it to $O(n \log n)$ or less?


texts: Search for maximal value smaller than V in an array composed of K linear functions

texts:
Sorry for the lack of clarity in the question description.

I have an array composed of length $N$ composed of $K$ linear subarrays. We define a linear subarray as a contiguous subarray of the array $[l,r]$ where $A[i]-A[i-1] = C$, a constant, for all $l<i<=r$. (Note: $C$ may be different for different subarrays; the elements of the array are integers.) Please note that the linear subarrays are not disjoint (there is one element intersection between any pair of adjacent linear subarrays). For example, [1,3,5,4,3,2] has two linear subarrays: [1,3,5] and [5,4,3,2]. [1,3,5,1,2,3] would have three: [1,3,5], [5,1], [1,2,3].

I wish to find multiple queries for the maximal value that is less than a queried value $V$, in $o(K)$ and $o(N)$ time per query, with $o(K^2)$ and $o(N)$ preprocessing. (Assume that the array has already been stored in terms of the K linear subarrays, perhaps in terms of the constant C and length of each subarray, with the subarrays ordered. Therefore, you are given the array with the starting and ending points of all the linear subarrays, as well as the linear constant C, as described before. So, one does not need to derive the linear subarrays in the first place.) Otherwise, a proof (formal or not) that it is not possible to do so would be appreciated.

Of course, a balanced binary search tree (BBST) or simply sorting achieves the purpose, but it requires $O(NlogN)$ preprocessing, which is too much. Checking the largest valid value within each subarray takes $O(K)$ per query, which is again too much. Would it be possible for something to combine both of these, perhaps?

Randomised algorithms are okay as long as they always achieve the correct answer and work fast enough in the average case, though deterministic algorithms are preferred.

Thanks for any and all responses. I was wondering if there was any research in the question, maybe? It does not seem like too obscure a topic, but unfortunately my searching has not been competent enough.

EDIT: A method that seems useful.

Here was my line of thinking after I asked the question; I wonder if this would help somehow. It uses the idea of modulo as well.
Initialise V=0, and allow each linear subarray to be stored as L,R; where L is the minimal value of the subarray and R is the maximal value. When we are given a query for V, we somehow disinclude elements where L>V and R<V (perhaps by using multiple dimensions?) A supplementary data structure stores the minimal theoretical difference of the element in the array, which is something like L - V mod c[i]. So essentially, we now need to be able to run a range add on this data structure, but if the value of any element becomes <0 or >=c[i] it needs to be reset (eg. if an element becomes equal to -1 with c[i]=5 it would be reset to 4; if an element becoming equal to 6 with the same c[i] would be reset to 1); and also run range minimum queries.

If such a data structure can be made, the problem is solved. The trouble is the modulo, as range add and range minimum query can be easily done with a segment tree and lazy propagation; as well as the disinclusion of certain elements.


texts: Language of a Turing Machine that runs its input on two other Turing Machines

texts:
Given two Turing Machines M1 and M2, we build a new machine M that does the following on input x:

Run M1 on x. If M1 accepts x, then go to an accept state.
Run M2 on x. If m2 accepts x, then go to an accept state.

What would be the language of such a Turing Machine? My first intuition was that $L(M)=L(M1) \cup L(M2)$ , but this can't be the case since if $x \notin L(M1)$ and $x \in L(M2)$, then there is the possibility that M1 runs forever, so M2 will never get the chance to recognize x and go to an accept state.

Unless we assume that M1 never runs forever, how is it possible to express $L(M)$? Thanks!


texts: Are there criteria that will make: $A \subseteq B$, $A$ unrecognizable imply $B$ unrecognizable?

texts:
Let $A \subseteq B$, and A is unrecognizable. I know in general that doesn't mean B is unrecognizable. However, are there some limitations we could put on A and B that would make it true? The only thing I could come up with was A=B. Plus, we could say B is unrecognizable as part of our assumptions, but that's not really helpful.

(recognizable means recursively enumerable, in case you use different terminology)


texts:
I have $n$ elements out of $n-1$ are distinct. The repeated element is either minimum or maximum element. I need to figure out how many distinct max heaps can be made from it.

My analysis : I started with $n$ distinct elements. Since root is fixed( maximum element) we can choose $l$(found using deducting total elements from elements in penultimate level) from remaining $n-1$ elements and recursively choose for Left Sub-tree and Right Sub-tree.

Recurrence Relation :

  $T(n)={n-1 \choose l} * T(l) * T(r)$

Now for $n-1$ distinct elements(given), for root we have $2$ options i.e. maximum elements and we can recurse as above for left and right sub-tree. But since the repeated element is also there I am not able to figure out exact way to do so.

Eg: $A=[2,6,6] =>$
There are 2 distinct max heaps $ => [6,2,6] , [6,6,2]$

I am unable to think of the way to find out the number of max heaps in this case. Can someone think of algorithm/recurrence relation to find so ?


texts: What is the difference in SMO algorithm for SVM and SMO for one class?

texts:
Please let know if this is not the correct forum to ask this question. If not can anyone please tell where can I ask this question?

I am trying to understand the difference between the paper :
https://pdfs.semanticscholar.org/59ee/e096b49d66f39891eb88a6c84cc89acba12d.pdf

and the paper http://users.cecs.anu.edu.au/~williams/papers/P132.pdf

The first paper is about SMO for SVM and the second paper is about SMO for one class. The question is what are the difference between this two algorithms? Also what are the common factors in both the paper?

The second paper has not shown any details of the algorithm so not sure what minimal change to be done on the first to get the second algorithm?

Given the code for the SMO for SVM, what minimum change would require to make the code suitable for one class SMO?


texts: How can I make the following grammar unambiguous

texts:
Given the below ambiguous grammar how can I make it inambiguous and how can I prove the new modified unambiguous grammar is unambiguous? S -> S + S | S − S | S ∗ S | S / S | (S) | x | y
My attempt: The ambiguity can be corrected by
S -> S + T | T , T ->T - M| M, M * N|N , N / Q | Q , Q-> (I) | x| y|
But I'm unsure how to provide a proof for this and I do not know if the |x|y| will have an affect on making this grammar ambiguous. I was thinking I could do an induction proof but I'm unsure how I would begin.


texts: Using Headpose Vector and 2D Points to Compute Distances

texts:
I have a frame taken from a video. The frame contains a face and I have the (x, y) locations of the features (corners of lips, edge of eyebrows, etc.) and the headpose vector (pitch, yaw, roll), which shows the direction that the face is looking in degrees ((0, 0, 0) would be at the camera).

I need to calculate distances between specific points in real (3D) space. How can I map the feature locations to 3D space?


texts: Average codeword length in a Huffman tree is $\Omega(\log n)$

texts:
Prove that the average codeword length in a Huffman tree is $\Omega(\log n)$, where $n$ is the number of characters.

My try:

I think that the worst case is when the tree is full and all the characters are in the highest level.

Therefore: $n=2^h \to h=\log n$, and the average codeword length is $\Omega(\log n)$.

Am I missing something?


texts: Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?

texts:
I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this thought:

If I had a language A that is recursive for some Turing Machine, TM(A), would it be possible to design another TM, TM(A2), where you add in a feature that instead makes TM(A2) loop for one or more words in A?

Now, A is no longer recursive.

This seems to be intuitively obvious for at least some examples (though my example is with a very simple language). Say A = {1}, and TM(A) is a program that just says:

'if (x=1)
{return true}'

For TM(A), A is accepted.

Now, let TM(A2) be a program that says 'while (x>_1) {x+=1}', and so now A causes TM(A2) to loop forever.

Granted that this example may unbenkownst to me be too simple to prove a real point, but if the above holds, then yes, languages can be of 'different types' depending on their context.

However, in none of the literature I've seen has this been written to be the case? If a language is recursively enumerable in one given example, it's recursively enumerable altogether - that seems to be the description of how it works.

To combat this confusion then, and given also that a language type in the Chomsky hierarchy is a subset of the types above it in the hierarchy, would this be a correct definition of the 'type of a language': if there exists at least one machine  (a DFA, a PDA, TM, etc) of a given language type, type X, that can be found to accept on a language, and it can be proven that no machine from the type below in the Chomsky hierarchy can accept on that language, then that language is of 'type X', and all the types above it?

If I'm correct in that rather long definition, then, it means that when a textbook says for example that a language is context free, then it means yes there are an infinite number of PDAs or TM's the can be thought of for which the CF language doest not accept, or loops even. But, there exists at least one PDA for which the language accepts on, and there can be no DFA that can accept on the language?

Further, when a textbook says a language is not even recursively enumerable i.e. unsolveable, it means that this language is above recursively enumerable in the Chomsky hierarchy, and that truly it is impossible to solve - that no TM can be designed to accept/reject on it?

If I've missed the point entirely or have been unclear, please do let me know.


texts:
We will consider a set whose elements I call "precedences". Precedences are related by two relations: "is subclass of" and "higher than", which are specified by some pairs (given on algorithm input) of precedences conforming to these relations and by the below rules. All sets in consideration are finite.

Let "is subclass of" be the finite partial order on the set of precedences, generated as the smallest partial order containing specified pairs of precedences, these pairs are specified in algorithm input.

Let "higher than" be the smallest partial order conforming to the following rules:

We have (as an algorithm input) a set of pairs of precedences, the first element of which is higher than the second one.
If A is strictly higher than B then A1 is strictly higher than B1 for every their respective subclasses (that is objects related by "is subclass of" relation) A1 and B1. [Added strictly.]

I need:

check if the partial orders (conforming to the above) "is subclass of" and "higher than" exist;
calculate (based on algorithm input) the relations, especially the relation of being "higher than".

The sets of pairs of both "is subclass of" and "higher than" are added to the algorithm input in chunks (several pairs of them are specified and added to the current sets of pairs). I want the algorithm to be reasonably fast and so not to recalculate everything when new data is added.

Please help me to conceive a reasonably efficient algorithm. I am writing in Java.

Remark: I am afraid that finding a reasonably fast algorithm may take me several years. I am going to work on this problem nevertheless until I find a solution. Your help is appreciated. (Well, I also consider that I need to think how to change the question if it does not always have a solution (minimum $>_U$).)


texts:
Is $\{ WxW^{\mathrm{R}} \mid W,x\in\{0,1\}^+\}$ a regular language? If so, why?

The notation $W^{\mathrm{R}}$ means the reverse string of $W$?

If we consider the best answer in this solution, if the language is regular, then its FA should reject all strings not in the language. However, a string such as 0110100 would also be accepted by the FA, since it compares only the starting and end characters! Please explain.


texts: Traveling salesman problem with disconnected cities / infinite length edge

texts:
I am looking to solve a variant of the traveling salesman problem with a certain set of constraints:

the graph is not complete, i.e. some nodes are not connected to each other
the weight of an edge between any pair of connected nodes is always 1

What is the best way to model and solve this problem?

AFAIK the Concorde TSP solver, for example, requires real numbers for edge weights. And it seems like because all the edges have the same weight, there could be more than one valid solution.


texts: Do Field separators delimit only fields or also data units inside fields?

texts:
At least intuitively, I understand the following terms to be rigorously associated:

Field Separator (FS) as a delimiter which delimits text segments such as words, sentences or lines/fields and an example would be an Input Field Separator / Internal Field Separator (IFS)
Indentation character:

Whitespace character
Tabulation character
Other, less standard, indentation characters

Line break character:

(non-carriage-return) Line Feed (LF)
Carriage Return Line Feed (CRLF)
Other, less standard, line break characters

If a field separator delimits text segments (one ore more byte/s before it, in one or more field/s) I would personally name it a text segment separator and not a field separator.
Do Field separators delimit only fields or also data units (sub-fields / "words and sentences") inside fields?


texts: Counterexample to big-O claim looks wrong

texts:
Let $T_1(n) = O(f(n))$ and $T_2(n) = O(f(n))$.
Then $T_1(n) / T_2(n) = O(1)$ is a false statement. A counterexample is $T_1(n) = n^2$, $T_2(n) = n$, and $f(n) = n^2$.

I don't get this counterexample, if $T_2(n) = n$, then $T_2$ is $O(n)$ and not $O(n^2)$. (As indicated by $T_2 = O(f(n))$ and $f(n) = n^2)$. Therefore, this doesn't look like a valid counterexample to me. Am I wrong?


texts: Finding the union, subtraction, and intersection of two DFAs

texts:
I recently solved problem of finding union of two DFAs and came up with some observations. I need confirmation about them along with some other facts:

I can prepare the union, subtraction and intersection DFA of two DFAs by preparing their product automaton and then suitably choosing final state. If $A_1$ and $A_2$ are non final states of DFA1 and DFA2 respectively and $F_1$ and $F_2$ are final states of DFA1 and DFA2 respectively, then,

For union of the DFAs, any state having any final state will be final:$A_1F_2, F_1A_2$ and $F_1F_2$.
For intersection of the DFAs, any state having both final states will be final:$F_1F_2$
For subtraction DFA1-DFA2, state having DFA1's final state but non final state of DFA2 will be final: $F_1A_2$

While preparing product automata for union and subtraction of DFAs, I may have to mark state $F_1D_2$ as final, where $D_2$ is dead state in $DFA_2$ and $F_1$ is final state in $DFA_1$. State $F_1D_2$ need not be dead state in the union, subtraction and intersection DFA. Is that right?
I can also prepare union DFA by introducing new start state with $\epsilon$-transitions to start states of both $DFA_1$ and $DFA_2$. Then I can reduce the $\epsilon$-NFA if required. I will have to mark final state as explained in 1st bullet point in point 1. I found this approach is similar to product automaton approach, its just that it avoids unreachable states while product automaton approach forces to consider all, even unreachable states. Is that right?
If point 3 is correct, can I prepare intersection and subtraction DFAs by following approach stated in point 3 but marking final states as stated in point 1?


texts: Match dictionary to misspelled word, corner cases

texts:
I'm trying to think of corner-cases where I can skip having to linear-search through my dictionary in my problem; For a given word w1, find all matches with the least editing distance from it in the dictionary D (Levenshtein distance).

The dictionary can contain 500.000 words so a linear search through it can tend to be quite costly. The tricks I've come up with so far includes;

Check if D contains wi (distance = 0) before beginning search
Since a lower bound for the Levenshtein distance is abs(w1.length-w2.length) I don't calculate the Levenshtein distance for two words if their length-difference is greater than the smallest Levenshtein distance I've found so far
I re-use parts of my Wagner-Fischer-matrices if two words I've searched for after one another have letters in common
I calculate all the words you can get using one operation on wi and check if any of those are in the dictionary data structure (of the 'physical' dictionary) -> if so I return them and stop the search (since I've already checked that the word isn't in the dictionary).

Are there any more cases in where I can manage to skip searching through the whole thing? I've thought about calculating all words that you can get with a distance of two from a word, but it feels like it's too costly combinatorically..


texts: Randomized agorithm for selecting a $m$-subset out of a $n$-set

texts:
The question has been discussed here but unfortunately is closed.

Reference : m-element random sample being equally likely ...(CLRS 5.3-7)?

My question is as follows.

Suppose $n = 5, m = 3$. This implies that we need to randomly select a $3$-subset out of $5$ elements. The algorithm makes $3$ recursive calls. The probability of obtaining the set $S_1 = \{1,2,3\}$ is more than that of $S_2 = \{3,4,5\}$ since we can obtain $S_2$ in only one way as follows.

$$ 3 = RANDOM(1,3) \\4 = RANDOM(1,4)\\ 5 = RANDOM(1,5) $$

But in case of $S_1$ we have $3! = 6$ ways of obtaining it, two of them being as follows.

$$ 3 = RANDOM(1,3) \\2 = RANDOM(1,4)\\ 1 = RANDOM(1,5) $$
$$ 2 = RANDOM(1,3) \\3 = RANDOM(1,4)\\ 1 = RANDOM(1,5) $$

Now, how can the output of each $3$-subset is equally likely as claimed in the question?


texts:
I am so confused between concurrency vs parallelism in multi-core processor.
If a concurrent process has many threads and if the processor is multi-core then can each thread run on multiple core? If the answer is YES then multiple thread are running in parallel but the process is concurrent. How is it possible and where is the concept of concurrency applied?
but if your answer is no then why do we even need concurrency concept. Why cant all process be based on parallelism concept?
If I assume that multiple threads of conncurrent proceess run in parallel.
Then which is better performance-wise concurrency in multi-core vs parallelism in multi-core and why?


texts: Single-tape Turing Machines with write-protected input recognize only Regular Languages

texts:
Here is the problem:

Prove that single-tape Turing Machines that cannot write on the portion of the tape containing the input string recognize only regular languages.

My idea is to prove that this particular TM is equivalent to a DFA.

Using this TM to simulate DFA is very straightforward.

However, when I want to use this DFA to simulate TM, I encounter the problem. For the TM transition $\delta(q,a)=(q',a,R)$, DFA can simulate definitely by reading tape to the right and doing the same state transition.

For $\delta(q,a)=(q',a,L)$, I cannot figure out how to use this DFA or NFA to simulate the left move because the DFA only reads to left and has no stack or something to store.

Should I consider another way? Could anyone give me some hints? Thanks.


texts: Why is the run time with a loop of this structure considered O(log n)

texts:
I used the search function and a good amount of google searches, but wasn't able to get a straight answer on how a loop of the form below, is translated to a proper summation where the function derived from the summation is:  $O(\log n)$.

Example of the for loop:

int j = 0;
for (int i = 2; i <= n; i *= 2) {
    j = j + n * 2;
}

So I understand within the loop we have 3 operations (multiplication, addition, then assignment).

I understand that the index $i$ ranges from $[1, 2, 4, 8, 16, 32, 64, 128, 256]$... ($i$ is only equal to powers of 2, up to $n$).

So essentially the range of $i$ seems to be from $[2^m, n]$ and $m \in [0, \log_2n]$ right?

Also, $i^m < n$ so the loop executes $\log_2n - 0 + 1 = \log_2n + 1$ times right? How do we go about expressing this in summation notation?

Is it this (just taking a guess, not sure if it's right):

$$\sum\limits_{i = 0}^{log_2n + 1} 3$$ since we have 3 operations? If this is the answer, why do we keep the upper bound of the summation to $\log_2n$ instead of $n$? Also, I know typically we'd use $\log n$ but just put in the base 2 to help clear things up in my own head.

Could someone please show how the summation of the for loop is properly written?


texts: How to simulate a bidirectional TM on a regular one with time factor four?

texts:
In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM $\tilde{M}$. How to work out the constant $4$?

In my opinion, in addition to "go over the edge" operation, one transition in $M$ corresponds to one transition in $\tilde{M}$, so where does constant $4$ come from?


texts: Find candidate keys - What are the steps

texts:
I have these following functional dependencies I figured out:
DM -> RA
RDT -> AM
AD -> RM

I got with a software to calculate what the candidate keys were to this:
{R, D, T}
{A, D, T}
{M, D, T}

But I don't know HOW i should do this manually to figure out this. Not to use the actual software. What the steps are to solving this. First I thought I should do something like this to figure out the candidate keys:
DM+ = DMRA
RDT+ = RDTAM
AD+ = ADRM

But from what I understand is that only the RDT+ is giving all the attributes for it to be a candidate key? I am so confused by this. How should I think to pick it out from these functional depedencies?


texts: Finding a line shape objects (bars) in video images using neural networks (instead of Hough transform)

texts:
I'm currently trying to learn about computer vision stuff and I want to try it on a simple project of real time tracking of figures of players in a foosball game while the camera can be moving a little bit above the table. The first goal I want to achieve is detecting (and tracking) the bars on which the figures are attached (so then I can easily find the figures on them).

My idea was to use Hough transform to find the lines that fit to the bars, but I'm wondering whether it couldn't be done using a neural network. Would it have better performance? If so, how could it be done, what approach can be used here? So I could give images of the table from different angles as inputs to the NN and it'd give me 8 lines that fit to the bars. Using the usual objects detection algorithms probably isn't the right way as this seems to be a simpler problem (finding just bars/lines). If you could just point me to some direction or show me some papers or tutorials that solve a similar problem, I'd be grateful.

Note:
To train the NN a was thinking about the mentioned Hough transform to find the lines in the training examples.


texts: What is the type signature of a Turing Machine?

texts:
Maybe my question is a bad question, but if it is, I want to know eactly how it is a bad question.

Suppose we have some Turing machien $M$ that takes as input a natural number $n$ in the form of a binary string, writes $n^2$ in binary on its output tape, and then halts.

What is the type signature of this machine? Here is why I am confused:

We can treat $M$ as a function: $M(\cdot)$ denotes the function that maps $n\mapsto n^2$, which suggests that it has type $\{0,1\}^*\to\{0,1 \}^*$
But $M$, intuitively speaking, is not a function, but a "device". This means that we can extract more information from it. e.g. potentially we could define $M_{235}(\cdot)$ to be the function that takes an input and outputs: "what is the string on the output tape after 235 steps, given this input?".
In the formal definition, a turing machine is a tuple $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$ (with some properties on these elements). But I am confused about how this tuple relates to type theory. Is this the "type signature" of $M$? If so, what kind of type theory captures this kind of type?


texts: Can every program be parallelized infinitely and automatically?

texts:
In my previous question ( Can Turing machines be converted into equivalent Lambda Calculus expressions with a systematic approach? ), I got the answer that it is indeed possible.

And as I have read before, every program written in all programming languages is convertible to a Turing Machine. And of course, since there are no side effects and no order in calculating a lambda expression, parallelization is infinitely possible, and it can break down to computing one lambda function on a separate machine.

So with having these three facts in mind, An interesting question comes to mind. Since every program written in every programming language has an equivalent Turing machine, Turing machines are convertible to Lambda Calculus expression through an algorithm, and Lambda expressions are infinitely parallelizable, can every program be parallelized automatically and infinitely?

EDIT : I think I have to clear out one thing. By infinitely parallelizing, I mean to parallelize till the point where it benefits us, so the arguments about the size of parallelizations are not valid. For example, by having five cores of cpu, one can utilize all of his\her cores by these approach.


texts: What are good resources for self teaching parallel/concurrent/multithreaded programming techniques?

texts: I’m having a hard time finding anything thorough. I have found some courses with titles like "parallel and concurrent programming in Java", but I'm looking to learn general techniques, not their use in {insert specific technology}.


texts: Context-free with single terminal symbol -- regular language

texts:
I have the following problem to solve:

Show that if G is a context-free grammar and Σ consists of just one terminal symbol, then L(G) is regular.

It is problem 4.26 from the book "Formal models of computation" by Arthur Fleck.

Do you have any ideas or solutions?


texts: What factors of the integer dataset being sorted can I change, in order to compare two sorting algorithms?

texts: I am comparing two comparison and binary data structure based sorting algorithms, the Tree Sort, and the Heap Sort. I am measuring the time taken for both algorithms to sort an increasing size of an integer dataset. However, I am wondering if there are any other variables which I can modify, for example standard deviation, in the integer dataset itself that would be of any benefit to my comparison.


texts: What is the difference between variables and pointers?

texts:
Whist reading an article outlining differences in OO and Functional programming I came across function pointers. It has been a while since I completed my Computer Science degree (2003) and so I looked up pointers to refresh my memory.

Pointers are variables that contain a reference to a memory address. They can be considered to point to the data that is contained in that memory address if such data exists. Or, as in the case in the article, they might indicate the entry point to a section of code and can be used to call that code.

Why is this different from a variable? Variables are symbolic names for memory addresses and compilers will replace the name with the actual address. This means that variables contain references to memory locations and can be considered to point to the data at that address if such data exists.

If the difference is in behaviour (maybe a pointer cannot be reassigned at runtime, or can only be assigned a symbolic variable name, not any other value) doesn't that mean it is just a variable of a particular type, the pointer type? In just the same way a variable declared to be of type integer is restricted by the compile in what it can be used for.

What am I missing here?


texts: A simple Query regarding Modulus Notation?

texts:
Aren't these two Modulus equations exactly the same (seems obvious):

$ X = 0 \ (mod\ B) $
$ X = B \ (mod\ B) $

The reason for the query is the following NP Complete Problem from Garey and Jhonson:

AN2, Simultaneous incongruences.

Given a collection $ [(a_1,b_1),…,(a_n,b_n)]$ of ordered pairs of positive integers with $a_i≤b_i$ for $1≤i≤n$, is there an integer $x$ such that for all $i$, $x≢a_i(mod \ b_i)$?

If both are equivalent why do we require $a_i≤b_i$ in the problem definition as its equivalent to $a_i<b_i$ ?


texts: Capsule networks for classification with limited data

texts:
Capsule networks seem to match performance of convolutional neural networks on image classification tasks (more specifically on classification of handwritten digits in the MNIST dataset) 1.

I have also read in various articles that capsule networks require less training data than convolutional neural networks. Does this mean that a capsule network could reach the same accuracy as convolutional neural networks with less data? Eg. could a capsule network achieve the same accuracy as convolutional neural networks on the MNIST while only training on a fraction of the dataset?


texts: Can one count the number of n points in m triangles in less than O(nm)?

texts:
We have n points given as $(x,y)$ coordinates and m triangles given as triples of $(x,y)$ coordinates, and want to count the number of times that one of the points is inside one of the triangles. The triangles may overlap so each point may be counted  multiple times.

The naive way is to check each pair of a point and a triangle and count +1 if the point is inside the triangle. Is it possible to do it more efficiently than $O(nm)$?


texts: how to formally arrive at a correct EBNF grammar of a language

texts:
I am trying to write a mini parser for a simple language whose specification is as follows:

A search term is represented by. Both searchkey and searchvalue is a word formed by using alphanumeric characters.

<searchkey> <searchoperator> <search value>

: represents the exact match(similar to "=").
ex :

response:success

multiple search terms can be combined with AND & OR operator.
ex.

response:sucess AND extension:php

By default AND has higher precedence than OR but this can be changed by grouping the search terms in a round bracket.
ex:

response:sucess AND (extension:php OR extension:css)

along with : other valid operators search operators are >, >=, <, <= .
ex.

time >= 2020-01-09 AND response:success OR os:windows

A search term could be preceded with NOT keyword to do the negation.
ex.

response:success AND NOT os:windows

I have written this grammar in ebnf notation :

<exp> ::= <exp> " OR " <exp> | <logical_and>
<logical_and> ::= <exp> " AND " <exp> | <logical_not>
<logical_not> ::= " NOT " <logical_not> | <term>
<term> ::= "(" <exp> ")" | <atom>
<atom> ::= <word> <op> <word>
<op> ::= ">" | ">=" | ":" | "<" | "<="
<word> ::= ("a" | "b" | "c" | "d" | "e" | "f" | "g"
                      | "h" | "i" | "j" | "k" | "l" | "m" | "n"
                      | "o" | "p" | "q" | "r" | "s" | "t" | "u"
                      | "v" | "w" | "x" | "y" | "z")+

But originally I had come up with this grammar.

<expr> ::= <or>
<or> ::= <and> (" OR " <and>)*
<and> ::= <unary> ((" AND ") <unary>)*
<unary> ::= " NOT " <unary> | <equality>
<equality> ::=  (<word> ":" <word>) | <comparison>
<comparison> ::= "(" <expr> ")" | (<word> (" > " | " >= " | " < " | " <= ") <word>)+
<word> ::= ("a" | "b" | "c" | "d" | "e" | "f" | "g"
                      | "h" | "i" | "j" | "k" | "l" | "m" | "n"
                      | "o" | "p" | "q" | "r" | "s" | "t" | "u"
                      | "v" | "w" | "x" | "y" | "z")+

is there any difference if I choose one over another? Can there exist multiple grammars for a language?
Is there any formal way to generate grammar for a language? this is a small language so its easy to get the grammar intuitively by tweaking it but what if the langue specification is huge?


texts: Can $ \{A^nB^nA^nB^n \mid n \geq 0 \}$ be pumped using the pumping lemma?

texts:
In order to show that $ \{A^nB^nA^nB^n \mid n \geq 0 \}$ isn't CFL, I was trying to use a pumping lemma this way: At first we assign $w= A^jB^jA^jB^j ,$ $(w^i=uv^ixy^iz), p<|vxy|, p<j.$

if $vy$ contains just $a$s we choose i=0 for $w^i$, so in this case the number of $a$s isn't equal to the $b$s.
if $vy$ contains just $b$s we choose i=0 for $w^i$, so in this case the number of $b$s isn't equal to $a$s.
if $vy$ contains both $a$s and $b$s then for any i there will be a difference in there quantity compare to the $n$ $a$s and $b$s that aren't in $vy$. Also $vy$ can't contain the whole world since the number of $a$s larger than $p$.
Isn't it CFL? Can pumping lemma help here?

I was told in class that it isn't correct to use pumping lemma here, why?


texts: Smallest set of features that would make relational algebra Turing complete

texts:
I'm thinking this should be just one or two things, since lambda calculus is so tiny and still Turing complete.

Probably just recursion (something like "MY_QUERY(param) = select * from param UNION MY_QUERY(DO_SOMETHING_WITH(param))"). But I don't see how I could define aggregate functions with this.

Any idea?


texts: Conversion from automaton to left linear grammar

texts:
I stumble across this problem:

  Give right linear grammar.

The solution given was simple:

$S\rightarrow bA$
$S\rightarrow aS$
$A\rightarrow \lambda$
$B\rightarrow bA$
$A\rightarrow aB$

Earlier I came across problems specified in this post, which involves applying Arden's theorem to left linear and right linear equations to find regular expressions. So I thought whether I can come up with left linear grammar for this. I tried and come up with this grammar:

$S\rightarrow \epsilon | Sa$
$A\rightarrow Sb|Bb$
$B\rightarrow Aa$

I was doubting if it is correct. So I tried operating both grammars on string "ab".

For right linear grammar, instantaneous description will be:

  $S\Rightarrow aS \Rightarrow abA\Rightarrow ab$

For left linear grammar, I felt it should be:

  $A\Rightarrow Sb\Rightarrow Sab\Rightarrow ab$

Book by Peter Linz explains how we can convert between right linear grammar and automaton on page 94,95. So I was thinking if its possible to convert between automaton and left linear grammar.

As you can see, above derivation in left linear grammar doesnt start with $S$ but ends with $S$ (i.e. uses production $S\rightarrow \epsilon$ in the end). So is it correct to think as valid derivation and legit left linear grammar? Also can we interpret it as something like bottom up derivation? I know I have not read anything like this in reference books, but was just giving free thoughts.


texts:
How likely is for a pseudorandom number generator to generate a long sequence of similar numbers? "Similar numbers" could be same numbers, or numbers from a given range.

For example, if we consider PRNG algorithm being a simple counter counting from 0 tom MAX, the distribution is uniform and there's a guarantee of not repeating numbers in a sequence. So, not repeating numbers does not break uniformness. But probably it breaks randomness, does it? To what extent? If so, does it mean, that the better the algorithm, the less guarantee we have to not generate similar numbers in sequence?

I'm particularly interested in the answers regarding Mersenne Twister as a most popular PRNG in programming languages implementations. It'd also be great to know how things are in operating systems' crypto-secure PRNGs – Yarrow (macOS), Fortuna (FreeBSD) or ChaCha20 (Linux).


texts: LTL Logic Finally, Globally and Until to irreflexive Version

texts:
my professor said that we can transform the reflexive Finally, Globally and Until into irreflexive Finally, Globally, Until.

Can someone explain me this?

For irreflexive Finally we have $w \models F^+ \varphi$ if $\exists i >= 1: w^{(i)} \models \varphi$
For irreflexive Globally we have $w \models G^+ \varphi$ if $\forall i >= 1: w^{(i)} \models \varphi$
For irreflexive Finally we have $w \models \varphi_1 U^+ \varphi_2$ if $\exists i >= 1: w^{(i)} \models \varphi_2$ and $\forall j, 1 \leq j < i w^{(i)} \models \varphi_1$


texts: The number of executions of the count statement; how many?

texts:
How many times does the statement count in line 5 executes in terms of $n$?

1.  count=0;
2.  for (i=1; i<=n; i++) {
3.  for (j=1; j<=n; j*=2) {
4.  for (k=1; k<=j; k++) {
5.        count = count + 1;
6.      }
7.    }
8.  }

For the loop in line 3, we can list the numbers for $j$ as, $2^0,2^1,...,2^{\log n}$
Therefore, we can refer to the iterations of the exponents as $r$. Doing so would lead to the summations below for counting the number of executions.

$\sum_{i=1}^{n}\sum_{r=0}^{\log n}\sum_{k=1}^{j}1 =\sum_{i=1}^{n}\sum_{r=0}^{\log n}j $

I am stuck here, because $\sum_{r=0}^{\log n}$ depends on $j$ but I am not sure how to incorporate them.

Thanks in advance.


texts: Converting an approximate algorithm for the minimization to the maximization form

texts:
I have a $\rho$-approximate algorithm for a minimization algorithm, where the objective is to minimize $O$ ($\rho \geq 1$ is some constant), such that the algorithm's solution is always within $\rho$ times the optimal. Is it possible to use this to get an approximate algorithm to maximize $-O$? What is the approximation ratio of this algorithm?

Thanks!


texts: Acceptance problem for CFGs is not regular

texts:
Let $ACFG$ be the language of all encodings $(C,x)$ where $C$ is a context free grammar that generates a language containing $x$, i.e. $ACFG$ is the acceptance problem for context free grammars.

It is easy to show that $ACFG$ is decidable. Parsing algorithms like CKY are proofs of this fact.

Is $ACFG$ also regular? Is it also context-free? I would guess nay to both, but how would one formally show these facts?


texts: Is cubical type theory still consistent with univalent excluded middle and univalent choice?

texts: I want to formalize some undergraduate maths in cubical agda, and learning cubical type theory in the proccess. The problem is that I will need univalent excluded middle and univalent choice (and maybe propositional resizing). I know these are consistent with homotopy type theory (although computation is lost when axiom are used), but cubical that type theory is stronger (in the sense that univalence is a theorem). Are this axiom still consistent in the cubical setting? Is there a better way of doing classical theorems in cubical type theory?


texts: I have an input array and I have to select an indefinite number of intervals from it so that the "profit" is maximal and I have exactly T elements selected in total, where T is given. Profit means the sum of all the elements of an interval, except for the first element. An interval can consist of a single element, meaning that the profit for such an interval is 0. The array may contain negative numbers. Apparently dynamic programming is the answer to this problem, but I cannot think of an efficient algorithm to solve it. This is homework, so I would appreciate any help.


texts:
Robot in a grid: Imagine a robot sitting on the upper left corner of a grid with $r$ rows and $c$ columns. The robot can only move in two directions, right or down, but certain cells are off limits and the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.

ArrayList<point> isThereAPath (boolean[][] matrix) {
if (matrix == null) {return null;}
ArrayList<point> arrayList = new Arraylist<point>();
if(isThereAPath (boolean[][] matrix, 0, 0, arrayList)){ return arrayList ;}}
// returns boolean, if there is a path, we return the modified arrayList

boolean isThereAPath (boolean[][] matrix, int row, int column, Arraylist<point> arrayList) {
if (row > matrix.length - 1 || column > matrix[0].length -1) {return false;}
boolean destination = (row == matrix.length - 1) && (column == matrix[].length - 1)
    if (destination || isThereAPath(matrix, row + 1, column, arrayList) || isThereAPath(matrix, row, column + 1,     arrayList)) {
    Point newPoint = new Point(row, column);
    arrayList.add(newPoint);
    return true;}
return false;
}

I have been trying to find out the time complexity of this algorithm. I have asked a few people, and they say the time complexity is 2^r+c where r = row, and c = column. Even the book says that.

But I don't think that is true. Because the or operator (||) supports Short-circuit evaluation. So the algorithm will keep going downwards (if there aren't any obstacles) and then keep going left. (again if there aren't any obstacles).

My point being even though it is a recursive algorithm, there might not be two branches for each recursion. It really depends on the distribution of the obstacles. So where did $2^{r+c}$ come from?

Please give me some hint as to how the book got $2^{r+c}$ for the answer.


texts: Proving that language, with $|\Sigma|=1$, is irregular by Myhill–Nerode theorem

texts:
We have $\Sigma =\{0\}$ and $$L=\{0^{2^n} \mid n\ge 0\}$$
How to prove that $L$ is irregular by using Myhill–Nerode theorem?

At other languages with $\Sigma >1$ we can usually separate the word or something like this with combination and this how we can show that two words are not at the same equivalent class....
But what we can do at this case?

Here what I tried:
Assuming that $i\ne j$, then $0^{2^i+1}$ is not at the same equivalent  class with $0^{2^j+1}$, why?
Let mark: $p$ - the amount of $0$'s that we need to add to $0^{2^i+1}$ to be $0^{2^{i+1}}$, $q$ - same thing but with $j$ instead of $i$.
Of course $p\ne q$, hence:
$0^p\in 0^{2^i+1}$ but $0^p\notin 0^{2^j+1}$.

I'd like to know if I'm right at my and I should continue or try a different way...

Thank you!


texts: Physical significance of pumping length in pumping lemma

texts:
Would it be possible to explain the physical significance of pumping length $p$ in pumping lemma for regular languages?

Somehow, the physical significance of
pumping length $p$ in pumping lemma for regular languages escapes me.

I have explored a number of tutorials and presentations on this topic. The nearest I came to is, at some point, $p$ was assumed to be the number of states in the DFA recognizing the language. But the same presentation at some later point cautioned that $p$ is a property of the language, and not of the DFA.

When we prove a language to be not-regular, first of all, we assume it to be regular and thus having a pumping length $p$. We also assume the language to satisfy the conditions of pumping lemma. Later on, we find that the language fails to satisfy the conditions of pumping lemma and hence not a regular one.

So, such languages will not have any pumping length.

But what about regular languages? If I am given a regular language, there are many, just pick any one from this list, $10^*$, $1\Sigma^*$, $\Sigma^* 001$, would it be possible for us to point out the pumping length for that language?


texts: Is deep learning appropriate to approximate dynamic programming problems?

texts:
I have a problem which can be completely solved using dynamic programming, but in a very intractable way (On^4, where n is around 1000).  I won't get into the details of the problem since it's a bit complicated, but it involves comparing properties of subsequences of a single string, where the property of subsequence (xi... xj) is related in a complex way to the property of subsequence (xi... xj + 1). I am fine with getting an approximation of the correct answer, but obviously would like to maximize correctness and minimize compute.

I have a well-defined metric for how good an answer is, but I have no idea what approach I should be using to solve it.  I was thinking about turning it into a reinforcement learning problem for a deep neural network, as a way of avoiding having to find the best algorithm myself.  I realized that I have no intuition for the kind of "algorithmic" problems for which deep reinforcement learning fits well.  For instance, playing Go well was considered an "algorithmic" problem and has been advanced by using deep reinforcement learning, but the fact that it is nontrivial to teach multiply makes me think that certain seemingly simple problems might be out of reach.  Is there a good way to think about what problems are well suited for deep reinforcement learning?


texts: Queue FIFO search speed up through the change of visited array?

texts:
As I was preparing for the CCC this year, I am quite confused as to why a certain code modification was able to speed up my code for CCC Seniors Problem 2.
Here was the C++ source code for my first attempt, which scored 13/15 in the cccgrader website as well as the DMOJ online judging website.
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vint;
typedef pair<int,int> pii;
vector<pii> vpairs[1000001];
vector<vector<bool>> vis;
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int A,B;
    cin>>A>>B;
    for(int i=0;i<A;i++)
    {
        vector<bool> newvecbool;
        for(int j=0;j<B;j++)
        {
            newvecbool.push_back(false);
            int k;
            cin>>k;
            vpairs[k].push_back(pii(i,j));
        }
        vis.push_back(newvecbool);
    }
    queue<pii> queue;
    queue.push(pii(A,B));
    while(!queue.empty())
    {
        pii curpair = queue.front();
        queue.pop();
        if(curpair.first==1 && curpair.second==1){
            cout<<"yes";
            return 0;
        }
        vis[curpair.first-1][curpair.second-1] = true;
        int value = curpair.first*curpair.second;
       // cout<<curpair.first<<' '<<curpair.second<<endl;
        for(int i=0; i<vpairs[value].size();i++)
        {
            pii pair = vpairs[value][i];
            if(!vis[pair.first][pair.second]){
                //vis[pair.first][pair.second] = true;
                queue.push(pii(pair.first+1,pair.second+1));
            }
        }
    }
    cout<<"no";
}

Here, on the other hand, was my second attempt, being much faster in time and scoring 15/15 on both the cccgrader and the DMOJ judging website.
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vint;
typedef pair<int,int> pii;
vector<pii> vpairs[1000001];
vector<vector<bool>> vis;
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int A,B;
    cin>>A>>B;
    for(int i=0;i<A;i++)
    {
        vector<bool> newvecbool;
        for(int j=0;j<B;j++)
        {
            newvecbool.push_back(false);
            int k;
            cin>>k;
            vpairs[k].push_back(pii(i,j));
        }
        vis.push_back(newvecbool);
    }
    queue<pii> queue;
    queue.push(pii(A,B));
    while(!queue.empty())
    {
        pii curpair = queue.front();
        queue.pop();
        if(curpair.first==1 && curpair.second==1){
            cout<<"yes";
            return 0;
        }
        //vis[curpair.first-1][curpair.second-1] = true;
        int value = curpair.first*curpair.second;
       // cout<<curpair.first<<' '<<curpair.second<<endl;
        for(int i=0; i<vpairs[value].size();i++)
        {
            pii pair = vpairs[value][i];
            if(!vis[pair.first][pair.second]){
                vis[pair.first][pair.second] = true;
                queue.push(pii(pair.first+1,pair.second+1));
            }
        }
    }
    cout<<"no";
}

As you may have noticed, the only difference between the two source codes is the position in which the vis vector, a vector used to store the pairs of integers of visited coordinates,  is set to true. after visit of a coordinate point. One is right after the if statement, whilst one is in the while loop. I'm not quite sure what led to the speed increase.
Any help will be greatly appreciated.


texts: How to justify the role of blossom in Edmond's blossom algorithm for maximum matching? odd cycles also can be covered in augmenting path.


texts: Mathematical expression for the quantity that we are maximising in the stock buying and selling problem

texts:
Problem Statement:
Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Here's the link to the problem.

I know the solution to this problem but what I'd like to know is how do I write the total profit, (i.e. the thing that we are trying to maximize,) as a mathematical expression? I tried the following (where $n$ is the length of the list):
$$\sum_{ \substack{1 \leq i,j \leq n \\ i\lt j}} (x_j - x_i)[i,j \text{ unique}] $$
But this would be wrong since it could include both $i = 1, j = 2$ and $i = 2, j = 3$, and we can't both buy and sell a stock on day 2. Also I had to resort to the Iversonian notation for this, and if possible, I'd like to avoid it.
I don't know if I should be needing two variables for the summation, since we only iterate through the list once for calculating the profit, but I couldn't do it in one variable.
PS: This is my first time posting here and I couldn't really decide on the tags for this problem. Pardon me if they are wrong, and let me know which ones to use and I'll update the question. :)


texts:
If $L^2$ is regular. Does that imply L is regular.

I think L need not be regular. But I can't find any example where L is not regular but $L^2$ is regular.

My teacher told me an example where L={$0^k$ | k is composite} clearly L is not regular. But he claims that $L^2$ is regular. I don't know why it is regular? Please help.


texts: Maximizing the sum from m stacks using k pop's

texts:
Assume you have m stacks each some elements within it. If you are allowed to do k pops , the objective is to maximize the sum(sum increases by the value of the popped element). What is the best algorithm which would be able to solve this problem.
Can the complexity be improved if the details of the elements in each stack is known beforehand.