texts: Provide a polynomial time algorithm that decides whether or not the language recognized by some input DFA consists entirely of palindromes

texts: Everything needed to know is in the question statement. I believe that the DFA has to be acyclic (meaning its language is finite), which can be checked in polynomial time. However, finding all paths from the start state to an accept state can run in exponential time in worst-case.


texts:
INOI 2017, Problem 2, Training
Ash and his Pokemon Pikachu are going on a journey. Ash has planned his route for the journey so that it
passes through N cities, numbered 1, 2, …, N, and in this order.

When they set out, Pikachu has an initial strength of Sin as well as an experience value (XV) of 0. As they
travel they may increase his strength and experience value in a manner to be described below.
In each city, Ash can choose either to train Pikachu or let Pikachu battle the Gym-leader (but not both). The
Gym-leader in ith city has experience E[i]. If Pikachu enters a city i with strength S and decides to train, then
this increases his strength by the cube of the sum of the digits in his current strength.

For example, if he
entered a city with a strength of 12, then training will increase his strength to 12 + (1+2)3 = 39. On the other
hand, if he enters city i with strength S and battles the Gym-leader, then this increases his experience value
XV by S*E[i].
Ash wants your help to find out the maximum XV that Pikachu can attain at the end of his journey.

Input
The first line contains two space separated integers, N and Sin, which are the number of cities, and the
initial strength, respectively.
The second line contains N space separated integers, which correspond to E[1], E[2],..., E[N].

Output
A single integer which is the maximum XV that Pikachu can attain.
Constraints

For all test cases you may assume that:
1 ≤ N ≤ 5000
0 ≤ Sin ≤ 109
0 ≤ E[i] ≤ 104

Subtask 1: For 10% of the score,
N ≤ 20 and Sin = 1
Subtask 2: For further 40% of the score,
E[i] = k for all i
i.e. E[i] is some constant k, for all i
Subtask 3: For further 50% of the score,
No further constraints.

============================================================================

I managed to solve the first subtask by employing a brute force solution (O(2^n)). But for the second and third subtasks I don't think that a brute force solution will be optimal.
Also, for the second subtask I have a vague idea. Taking X to be the number of trainings, then N-X is the number of battles. By maximizing experience gained  from N-X battles, we might get the answer, but I'm not sure if it's the right way.
I do not have any idea of how to solve the 3rd Subtask without using a brute force algorithm. Help would be appreciated.
Edit: Link to the above question in the IARCS website : https://www.iarcs.org.in/inoi/2017/


texts: Arithmetic expressions grammar transformation

texts:
In the article Parsing Expressions by Recursive Descent by Theodore Norvell (1999) the author starts with the following grammar for arithmetic expressions:

E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v

which is quite bad, because it's ambiguous and left-recursive. So he starts from removing the left recursion from it, and his result is as such:

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^"
U --> "-"

But I can't figure out how did he get to this result. When I try to remove the left recursion myself, I'm doing it the following way:

Firs, I group together the productions which doesn't have left recursion in one group, and other (left-recursive) in another group:

E --> E "+" E | E "-" E | E "*" E | E "/" E | E "^" E     // L-recursive
E --> v | "(" E ")" | "-" E
Next, I name them and factor for easier manipulations:

E --> E B E  // L-recursive; B stands for "Binary operator"
E --> P  // not L-recursive; P stands for "Primary Expression"
P --> v | "(" E ")" | U E   // U stands for "Unary operator"
B --> "+" | "-" | "*" | "/" | "^"
P --> "-"

Now I need to deal only with the first two productions, which are now easier to deal with.
I rewrite those first two productions by starting from the non-L-recursive production (which is simply P, the Primary expression) and following it by the optional Tail T, which I define as the rest of the original production less the first left-recursive nonterminal (that is, just B E) followed by the Tail T, or which could be empty:

E --> P T
T --> B E T |

(note the empty alternative for the tail).
These two productions I can now rewrite in EBNF like this:

E --> P {B E}

which is nearly what the author get, but I have E instead of P there inside the zero-or-more repetition pattern (the Tail). The other productions I get quite the same as he have got:

P --> v | "(" E ")" | U E
B -> "+" | "-" | "*" | "/" | "^"
U -> "-"

but here too I have E instead of P in the first production for P.

So, my question is: What am I missing? What algebraic transformation on the syntax I need to proceed now to get the same exact form as the autor gets? I tried substitutions for E, but it only leads me into loops. I suspect that I need somehow to substitute P for E, but I don't know any legal transformation to justify it. Maybe you know what's the last missing step?


texts: Why is $L := \{b^2a^nb^ma^3|m,n \geq 0\}$ a regular language?

texts:
(Pre-note: I'm learning Theory of Computation on my own, so bear with me if I'm saying something wrong/stupid.)

  Why is $L := \{b^2a^nb^ma^3\mid m,n \geq 0\}$ a regular language?

This question appeared in a problem set, whose answer is the following:

  The language is regular. Indeed, it can be expressed by the regular expression $\mathcal{R} := b^2a^*b^*a^3$.

However, I (think I) can find a contradiction using the pumping lemma.

Consider $s = xyz = b^2 a^{p-3}b^1a^3$. (I assume one can take a specific string from the language.)

Clearly, $\forall p>3, s \in L$, and $|s|\geq p$, the pumping length.

Take $x = b^2$, $y=a^{p-3}b^1$, $z = a^3$. (I assume one can take specific values for $x, y, z$).

The pumping lemma says that if $L$ is regular, there is a number $p$ (pumping length) where, if $s \in L \wedge |s| \geq p$, $s$ may be split into three pieces, $s = xyz$, satisfying the conditions:

$|y| > 0$,
$|xy| \leq p$,
$\forall i \geq 0, xy^iz \in L$.

Conditions (1) and (2) are fulfilled.
As for condition (3) ...

$xy^iz = b^2(a^{p-3}b^1)^ia^3$

For $i=0$, $xy^0z = b^2a^3 \in L$.

However, for $i = 2$, $xy^2z = b^2(a^{p-3}b)(a^{p-3}b)a^3$, and taking $p=4$, it is clear that $xy^2z = b^2ababa^3 \notin L$.

Thus, we find a contradiction (because $xy^2z \notin L$) and $L$ is not regular.

(Could you help understand where is the fallacy here?)


texts: Forward edges in undirected graph using BFS

texts:
Introduction to Algorithms books claims BFS only classifies an edge for an undirected graph to be either tree or cross edge. But how about this simple example below where forward edges are naturally appearing?

Given graph with just 2 vertices A and B and 3 edges from A to B!

 exploring A adjacent vertices

(1) A->B (tree edge, A is now marked as an ancestor for B and B is A's descendant)

(2) A->B (forward edge? B is not yet processed (gray) and we found an edge to it from its ancestor(A))

(3) A->B forward edge using the same reasoning as in (2)!

What am I missing here?


texts:
(pseudocode)

f(x,y,z)
{
    if (x < y)
    {
        return 1 + f(x + 1, y, z)
    }
    else if (y < z)
    {
        return 2 + f(x, y + 1, z)
    }
    else
    {
        return z
    }
}

The function call f(12,14,20) returns $40$. Why is this the case? As the final statement is return z, should it not simply return $20$, which would be the value of $z$ at which the recursion stops - $(20,20,20)$?

How does one go about analysing such a function?


texts: Why does $A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon$?

texts:
I have a book that proves the halting problem with this simple statement:

$$
A_\text{TM} \le_m  \text{HALTING} \le_m \text{HALTING}^\varepsilon
$$

It states that halting problem reduces to the language consisting of $\langle M, \omega \rangle$ for which a Turing machine $M$ accepts $\omega$ is undecidable.

What does this mean? What does the notation $\le_m$ indicate?


texts: Is switching quantifiers allowed in this instance?

texts:
In Logic In Computer Science (2nd Edition - Michael Huth and Mark Ryan), exercise 2.4.12.k is the following:

  For each of the formulas of predicate logic below, either find a model which
  does not satisfy it, or prove it is valid.

This one is difficult:

  (∀x ∃y (P(x) → Q(y))) → (∃y ∀x (P(x) → Q(y)))

Not only am I not sure how to prove this, I'm not sure whether it is valid or not. I came across this question when revising for an exam and always hit a dead end with it.

Any suggestions or insight is appreciated.


texts: How to get to the efficient solution of a problem on buying with exchange policy

texts:
I was working through some coding challenges at hackerrank.com and got to this one.

I understand the problem and how to solve it, but after solving it I searched for more solutions to improve mine. So I found this.

After explaining the naive method, which is the one that I used, then there is the efficient solution. But I can not understand the explanation that goes from the naive method to the efficient solution.

Can someone help me understand how is the logic to get to the efficient solution:

  In above naive implementation, we noticed that after finding initial number of chocolates, we recursively divide the number of chocolates with the number of wrappers required. until we left with 1 chocolate or wrapper.
  We are recomputing the values i.e. ((choc/wrap + choc%wrap)/wrap until we get 1.
  It is observed that, we can get the result by just reducing the values of chocolates and wrappers by 1 and then divide them to get the result (choc-1)/(wrap-1)


texts: Scott-continuous functions: an alternative definition

texts:
I'm really struggling with this property:

Let $X,Y$ be coherence spaces and $f: Cl(X) \rightarrow Cl(Y)$ be a monotone function. $f$ is continuous if and only if $f(\bigcup_{x\in D} x)=\bigcup_{x \in D}f(x)$, for all $D \subseteq Cl(X)$ such that $D$ is a directed set.
Directed set is defined thus: $D \subseteq $ POSET$ $ is a directed set iff $ \forall x, x' \in D$ $  \exists z \in D $ such $ x \subseteq z$ and $x' \subseteq z$.
$Cl(X) $stands for cliques of X: $\{x \subseteq |X| \mid a,b \in x \Rightarrow a$ coherent $b \}$.

Many books give that as a definition of Scott-continuous functions, but unluckly not my teacher. He gave us this definition of continuous:

$f : Cl(X) \rightarrow Cl(Y)$ is continuous iff it is monotone and $\forall x \in Cl(X), \forall b \in f(x), \exists x_0 \subseteq_{fin} x, b \in f(x_0)$,
where monotone is defined as:
$f$ is monotone iff $a \subseteq b \Rightarrow f(a) \subseteq f(b)$

This is the proposed proof I have, but I can't understand the last equation.
Proof of $f$ continuous implies $f(\bigcup D)=\bigcup f(D)$:
Let $b \in f(\bigcup D)$. By the definition of continuity, $\exists x_0 \subset_{fin} x \mid b \in f(x_0)$. Note that $x_0$ is the union of  $\{ x_i \mid x_i \in D\}$.
If $D$ is direct then: $\exists z \in D \mid x_i \subseteq z$ then $x_0 \subseteq z$. By the definition of monotony, $f(x_0)\subseteq f(z)$ so $b \in f(z)$ (???) $\subseteq \bigcup f(D)$. And  even that is true we should show that $\bigcup f(D) = f(\bigcup D)$, not just $\subseteq$.
The proof of the other implication is even worse so I can't write it here... Can you explain to me how the proof can work?


texts: Asymptotic analysis for machine learning algorithms

texts:
I wanted to know if it would practical and useful to analyse machine learning algorithms in terms of asymptotic computational complexity.

I have noticed this is very uncommon. However, I believe it would help us compare these algorithms and decide which one to use for a given scenario.

I am also aware that the running time of most machine learning algorithms is highly dependent on the data. For example, gradient descent algorithm can iterate significantly more times on certain data sets than others.

Considering this, what would be a nice complexity measure for comparing machine learning algorithms?


texts:
Consider these matrices:

$A=\begin{bmatrix}1 & 2\\3 & 4\end{bmatrix}$

$B=\begin{bmatrix}-1 & -2\\-3 & -4\end{bmatrix}$

Using standard algorithm:

$C=\begin{bmatrix}1*-1+2*-3 & 1*-2+2*-4\\3*-1+4*-3 & 3*-2+4*-4\end{bmatrix}=\begin{bmatrix}-7 & -10\\-15 & -22\end{bmatrix}$

Transpose B and do dot product row wise for A and B

$B^T=\begin{bmatrix}-1 & -3\\-2 & -4\end{bmatrix}$

$C=\begin{bmatrix}1*-1+2*-3 & 1*-2+2*-4\\3*-1+4*-3 & 3*-2+4*-4\end{bmatrix}=\begin{bmatrix}-7 & -10\\-15 & -22\end{bmatrix}$

I'd like to know whether the second version is correct in general?

And whether the second version is more cache efficient than the standard algorithm?

Why has matrix multiplication been defined as row with column?

NOTE: I do know real world implementations such as BLAS use different techniques than the naive implementation.


texts: looking for general advice on the field of computer science

texts:
I don't have any knowledge at all in the field, i don't know if i am in the correct community. Is there any book you would suggest for a starter to gain an idea about computer science? I have a good background on mathematics and engineering. I want a book to understand get a general idea about the field in order to be able to decide where i should focus.

Thanks


texts: Find all increasing/decreasing sub array

texts:
I have a question that I still struggle with.
It would be really appreciated if you guys could give me some hints.

Here is the problem :
Assume that $a[1\dots n]$ is an array of $n$ positive real numbers.
Let $\alpha >0$ and $\beta >0$

a subarray $a_1$ with $m$ elements of $a[1 \dots n]$ is called increasing if $\frac{a_1[i]}{a_1[j]}\geq \alpha$, for all $i>j$ and $1 \leq i, j \leq m$.
a subarray $a_2$ with $k$ elements of $a[1 \dots n]$ is called decreasing if $\frac{a_2[i]}{a_2[j]}\leq \beta$, for all $i>j$ and $1 \leq i, j \leq k$.

Question : write a program to find all increasing/decreasing subarrays of $a[1 \dots n]$ ?
thanks so much for your help.


texts: Are there any efficient algorithems to find packets similarities in a list?

texts:
I would like to make a program which finds similar packets (there might be more then one class of similarity) in packet list (which is updated all the time). Are there any efficient algorithems to find these similarities?

By similarities I mean that they have the same size, type and payload.

I thought about using tree(with conditions on the branches just like  decision tree) or vector support machine with k classes (k>2), but it means that it should have a lot of classes/nodes. Say there are 10 different packets and 2 kinds of similar packets (3 packets in each group). Then there will be 10 classes with single packet, 2 classes with 3 packets - So its size depends on the amount of packets which can be really big.

thank you


texts: Whether the 2 minimum spanning tree of same graph contains the lowest edges in common?

texts:
If two minimum spanning trees on the same graph only have 2 edges in common, then those two edges must be the lowest costs edges in the graph.

True/false? and why?

Because according to me if there is a only edge which connects 2 subgraphs then that will be included in the MST whatever might be the value. So according to me the answer is False but the solution says the answer to be true. Please explain.


texts: Weighted Set Cover Problem Minimizing Average Weight

texts: In the traditional weighted set cover problem, we aim at minimizing the sum of the weight of the selected sets. Is there any problem/literature that aim at minimizing the average weight of the selected sets (i.e., sum of the weight / number of sets selected)?


texts: Term for array of identical type and different types

texts: What is proper terminology to distinguish between an array (ordered list) data structure in which each element is of identical type/class, and an array in which each element can be different?


texts: Why is the lower bound $m \log n$ for this make-set, union and find-set sequence?

texts:
Look at this solution:

Is the lower bound $m\log n$ because we are only looking at the lower bound for union by rank only? If we make $n$ MAKE-SET operations, then there would be $\log n$ UNION operations, and then $m - 2n + 1$ FIND-SET operations. The lower bound seems larger to me but what am I missing?


texts: I came across this symbol $2^{\mathcal{O} (n)}$ and I can't figure out what is means. What complexity class is this?


texts:
I'm interested in building an AI algorithm to play a board game.  This is a sequential two-player game, where they alternate taking turns, so minimax or alpha-beta algorithms sound natural.

However, the twist here is that the game is randomized.  There is a deck of cards that is shuffled randomly; each turn involves drawing the next card from the deck, then making a move.

What algorithms are appropriate for selecting a move, in a game with randomness?

I understand that one approach is to think of this as a three-player game: in addition to the two players, there is a third player (the dealer) who makes a random move.  For instance, if the two players are Minnie and Maxwell, we might alternate moves in the following order: Dealer (chooses a random card for Minnie), Minnie (selects a move), Dealer (chooses a random card for Maxwell), Maxwell (selects a move), and so on.  I think I've read that alpha-beta search can be adapted to this setting.  However, this doesn't sound too promising to me.  There are perhaps 52 possible outcomes of the moves by Dealer, so the tree will be very bushy (with a large branching factor), causing exponential blowup.  Also, this sort of modified alpha-beta search feels a bit inefficient to me.  Each move likely affects a player's score by only a little bit at a time, so we'd expect that the effects of the randomness to average out over many moves, and there is no need to explore all combinations of possible random outcomes.  To put it another way: the game is more about positional elements and random luck than about tactical/combinatorial elements.

Is there a better algorithm framework for randomized games, that takes into account the stochastic element?  (Bonus points if you can suggest something that takes advantage of the fact the strength of a position changes only slowly over many moves.)


texts:
What is meant by lazily computing online? For example, in context of synthesis, that uses model checking.

http://www.cs.colostate.edu/~france/CS614/Readings/Readings2011/Model-checking-Survey-a21-jhala.pdf

The above paper also mentions the concept in page 21:29.

Thanks in advance


texts: MSO (Monadic second-order logic) Logic On Words

texts:
Let L be a language over $\Sigma = \{a,b,c\}$ that contains all words, where the length $|w|_b$ (number of all b's) has remainder 1 if divided by 3.

MSO logic over words are definded as follow:

I want to express this language using MSO logic. But my problem is how can I count the b's to calculate the reminder? So it would be easiert if I just look on $|w|$, cause I could use max.


texts: How do you find a hash function that respects a custom equality function?

texts:
I've been tasked with hashing arbitrary types in C++, with the caveat that A == B implies hash(A) == hash(B) even if equality of A and B is determined by a custom equality function ==.

For simplicity we can assume that == is an equivalence relation.

For example, the expected behavior of the hash function on std::vectors is as follows:

Given

using namespace std;
vector A = vector();
vector B = vector();

A == B will be true because == is overloaded for std::vector to mean equality of the underlying data. Correspondingly, hash(A) == hash(B) should also be true.

I can't simply hash the addresses of A,Bas integers because A == B but hash(&A) != hash(&B) in general.

I've thought of one solution, but I wonder if its optimal. It seems terribly inefficient. The solution is to build the hash function as new values are hashed:

using namespace std;

<template class Key>
class Hasher{

    public:

       unordered_map<pair<Key,Integer>> hashedKeys;
       int max_hash

       Hasher(int max_hash){
          this->max_hash = max_hash;
       }

       int hash(Key key){

          // If key has already been hashed, used that hash_value
          if ( hashedKeys.count(key) == 1){
               return hashedKeys[key];
          }

          // For pairs of saved (Key key, int hash_value)
          for(unordered_map<Key,Integer>::iterator it=hashedKeys.begin(); it!=hashedKeys.end(); it++;){

             // If an equal key has been inserted, just use its hash_value
             if(key == *it){
                hashedKeys.insert(key, *it.second);
                return *it.second; //use hash value of equal Key
             }
          }

          // If no other Keys equal this one, randomly hash it, and save
          int hash_value = rand() % max_hash;
          hashedKeys.insert(key, hash_value);
          return hash_value;

       }
}

I could do some extra bookkeeping to ensure that inequivalent Keys are less likely to be mapped to the same hash by the random assignment, but that's largely besides the point.

Ignoring collision resolution, hashing a new value is O(hashedKeys.size()),  while hashing a previous hashed value is O(1)
We also require O(n) additional space to store the computed hash values, where most hash functions require O(1).

In a situation where a cache is large and new keys are constantly being inserted, the O(n) search is incredibly inefficient, so I'd prefer another approach if possible, or a proof that improvement is impossible.

Take the class ParityInteger:

class ParityInteger{
   public:
      int number;

      ParityInteger(int n){
         number = n;
      }

      bool operator==(const ParityInteger& other){
         return (number % 2) == (other.number % 2);
      }
}

The ideal hash for such a class is:

int hash(ParityInteger n){
   return n%2;
}

which basically assigns a ParityInteger to a representative of its equivalence class.

Besides my method in the class Hasher, is there any better way to automatically find a function which assigns equivalent members of an arbitrary type to the same integer, without being trivial?

Given a computable equivalence relation == for some type, is there an algorithm to compute a nontrivial function hash such that == is a congruence relation wrt hash.

EDIT:
It seems that the naive Hasher algorithm I put forward is essentially optimal assuming you treat == as a blackbox:
https://cstheory.stackexchange.com/questions/33223/on-partitioning-a-collection-into-equivalence-classes


texts: Inverse VR-Vision, theoretical possibilities and the additional requirements

texts: When using VR-Vision for looking around and the vision is from some point of interest, the look-around is a rotation from inside that point and it reqires a record of a 360° photo or a 360° camera video. What would be necessary if instead the look-around should be outside of the point of interest but around the complete point of interest. Is it possible to calculate this from 3 video cameras, installed evenly around the point of interest? Theoretically it shouldn't be a problem, but what really interests me, is it also possible to use this version of camera installation, 3 cameras around some point of interest and computationally inverse the Vision in real time to a look-around from inside the point of interest? Theoretically this shouldn't be of any problem, or should it? Those 360° video cameras are costing a fortune and are absolutely wasted, or am I not considering something of importance for VR-Vision?


texts: What is the simplest algorithm to compress a string?

texts:
I need to compress a string in my application but I am very limited in the operations I can perform. In particular, I cannot store data in any file and I cannot query any database. Also, I cannot call any library so I have to code my own data compression algorithm. What would be the simplest algorithm to achieve this goal?
I could code the smaz algorithm myself but it does not seem to work very well with long strings.


texts: How to find the number of Binary Search Trees with given number of nodes and leaves?

texts:
With 7 nodes of distinct values (unique), how many Binary search trees (BST) can be formed such that:

Exactly $1$ leaf node(s) present?
Exactly $2$ leaf nodes present?

I was able to solve the first one(and the actual problem was also that, but then I though what if the process can be extended)

  Here's my take on the 1st one

Here the elements are  $1,2,3,4,5,6,7$ (let's assume that for simplicity) and we need only $1$ leaf

So let us fix a root node: To fix the root node we have $2$choice either $1$ or $7$ from  $1,2,3,4,5,6,7$
(if we select any non-extreme elements then only $1$ leaf is not possible)
Let us say we select $1$ as root node
In each and every level we have $2$ different option that is to select i,e; either of extreme elements
So in 2nd level we can select $2,3,4,5,6,7$
Let us say we select $7$ in 2nd level
We still have 2 option to select in $2,3,4,5,6$
So this is true in all levels except last level since only $1$ element is left.
Therefore, total possibilities are : $2 * 2 * 2 * 2 * 2$ = $2^5$

The same condition is true for $7$ as a root

Hence, $2^5* 2$ (1 as root or 7 as root)  =  $2^6$.

(Which comes out as $2^{number of nodes -1}$)

But how can we now approach the second subpart or it can be generalized for let's say (2,3,4) leaf nodes?

Exactly 2 leaf nodes present?


texts: Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test?

texts:
In the paper "PRIMES is in P" the following is said (page 1):

  Let PRIMES denote the set of all prime numbers. The definition of prime numbers already gives a way of determining if a number $n$ is in PRIMES: try dividing $n$ by every number $m \leq \sqrt{n}$ — if any m divides $n$ then it is composite, otherwise it is prime. This test was known since the time of the ancient Greeks — it is a specialization of the Sieve of Eratosthenes (ca. 240 BC) that generates all primes less then $n$. The test, however, is inefficient: it takes $\Omega (\sqrt{n})$ steps to determine if $n$ is prime. An efficient test should need only a polynomial (in the size of the input = $\lceil \log n \rceil$) number of steps.

Firstly, isn't complexity $\sqrt{n}$ already polynomial?

Secondly, why would complexity $\lceil \log n \rceil$ represent an efficient algorithm? This seems somewhat arbitrary to me.


texts: Unrestricted grammar is closed under intersection

texts:
I want to show that unrestricted grammar is closed under intersection and I don't want to use Turing machine or etc. So I think that we have two grammar $G_1$ and $G_2$ that are restricted for example simple grammars
$$
S \rightarrow XY \\
X \rightarrow aXb | ab \\
Y \rightarrow Ya | a$$
and also $G_2$ is
$$
S \rightarrow YX \\
X \rightarrow bXa | ba \\
Y \rightarrow Ya | a$$
(I know these are CF grammars but intersection of them is not CF so I was trying to create unrestricted grammar for $G_1 \cap G_2$) so I change these grammars like below to generate $G'$ that is an unrestricted grammar for $G_1 \cap G_2$.
 $$
S \rightarrow X'Y' \\
X' \rightarrow AX'B | AB \\
Y' \rightarrow Y'A | A \\
BXA \rightarrow X \\
BA \rightarrow X \\
A \rightarrow Y \\
YA \rightarrow Y\\
YX \rightarrow S'$$
but there is two problem that I will forget string that will be accepted because finally the only thing will remain is $S'$ and another problem is that if I have $\lambda$ in the right side of grammar I can't move it to the left side for unrestricted grammar. is my approach true for solving this problem? and what is the idea of solving this?

Edit (complete some part it)

I think after accepting by grammar $G_1$ we can create copy of accepted string by following steps, imagine $aabba$ is accepted by $G_1$ it means that I have $AABBA$ now I can add following rules for every $t \in Terminals$
$$
T \rightarrow T'T''
$$
so $AABBA$ will be $A'A''A'A''B'B''B'B''A'A''$
and now I can define following rules for every $t,r \in Terminals$
$$
T''R' \rightarrow  R'T''
$$
now every variable that is the mirror of a terminal with single quotation will jump over variables with double quotation and the result will be $A'A'B'B'A'A''A''B''B''A''$ now I can work with variables with single quotation and after they disappear add rules to convert double quotation variables to terminals, for every $t \in Terminals$
$$
T'' \rightarrow t
$$
now just needed to proof that this will not accept string that is not in $L(G_1) \cap L(G_2)$ that I thinks its not complicated and the other thing is that I still don't know what should I do with $\lambda$ in right side of grammar rules.


texts: Using Nerode theorem to prove that the following languages are non-regular

texts:
I've been trying to understand the idea behind proving a language is not regular by using Nerode's theorem, but I just couldn't apply the idea on what I've been asked.

The problem is to prove the following languages are non-regular:

$L_1 = \{waw^R  \mid w∈{a,b}^* \}$, the language of all odd-length palindromes over $\{a,b\}$  such that in the middle of the palindrome there is an $a$.
$L_2=\{a^i b^j c^{i+j}  \mid  i,j∈\mathbb N\}$
$L_3=\{a^{2n} b^n  \mid  n∈\mathbb N\}$
$L_4=\{w^2  \mid  w∈\{a,b\}^*, \text{$w$ is a palindrome}\}$

Any help will be appreciated.


texts: Finding "entrance" points in a set of d-dimensional points. Can I do better than O(N^2)?

texts:
I am given a set of d-dimensional points, and need to find the set of entrance points in them.
Definitions:

A point p1 captures p2 if 1) All dimensions of p1 is smaller or equal to p2; and 2) At least one dimension of p1 is strictly less than its corresponding dimension of p2. (e.g. p1 = <1.0, 2.0, 3.0>, p2 = <1.0, 3.0, 3.0>, since 1.0 == 1.0, 2.0 < 3.0, 3.0 == 3.0, we say p1 captures p2.
An entrance point is a point which it is not captured by any other points in the dataset.

For example, in the following dataset:
n = 4, d = 2
=============
p1 = <0.3, 1.5>
p2 = <0.2, 1.4>
p3 = <0.1, 1.7>
p4 = <0.8, 0.9>

The entrance points are {p2, p3, p4} because:

p1 is captured by p2 because all dimensions of p2 is less than p1.
p2, p3, p4 cannot capture each other.

Assuming d is a constant. Now I can only think of a naive O(N^2) solution, that is, take every possible pair of the points and compare the dimensions one by one. If a point is captured by the other, eliminate it from the final set.
I also thought of a divide-and-conquer solution. That is, recursively break the points down into two partitions, perform the previous O(N^2) algorithm to eliminate some candidates from the final set, then recursively merge each pair of the partitions, say part1 and part2, back by comparing each possible pair of points one from part1 and one from part2. However, even though the running time is a little faster with the aid of multi-threading, I found that it is still an O(N^2) algorithm because T(N)=2T(N/2)+O(N^2) ==> O(T(N)) = O(N^2).
I wonder if there exists an algorithm with lower time-complexity for this problem.
Also, is there any well-known name for this problem? Or are there any well-known problems similar to this one so I can look into?


texts: how do we demonstrate using Boolean algebra that these NAND and NOR gate combinations are XOR gates

texts: How do we demonstrate using Boolean algebra that these NAND and NOR gate combinations are XOR gates?


texts: Approximation algorithm for weighted set cover, using multiplicative weights

texts:
It is known that the problem of fractional set cover
 can be rephrased as a linear programming problem and be approximated using the multiplicative weights method, for instance this lecture note shows how to do so.
The running time depends on the "width" of the problem, which equals to the number of sets in the unweighted case. However, in the weighted case, the width of the problem depends on the weight function, hence the running time is exponential with respect to the representation of the problem. Is there a way to overcome this issue? Either a way to reduce it to polynomial running time or proof that it's impossible (under plausible complexity assumptions)?


texts: What does it mean to say that there doesn't exist an algorithm from a TM point of view?

texts:
A TM for a recursive language corresponds to our informal notion of an algorithm.

as per Automata Theory, Languages and Computation by Ullman et al. Then there are languages called RE and $L_d$, where there exist TM that halts for accepting strings in the case of RE languages.

This means that we cannot construct a algorithm for RE languages that are not recursive? Then what is the significance of these RE languages from an algorithm point of view.

What confuses me is that for RE language you can construct a TM. So you can construct an algorithm?


texts: Average case of simple algorithm like binary search

texts:
These questions is about one of my research. As I am not a computer scientist, formal answering is difficult  to me.

I have a special search algorithm which the explanation here will take a lot of time. However I can explain it shortly by some notations.

Assume that we have an array of somethings (in my real research they are some cities which they form a path graph) with length $n$. First, we should select one element by some rules( I ignore the rules here) with $O(1)$ time. indeed, according to the rules this element is nearer element to my solution. However, as this rule does not follow a particular order, we can assume that the selection is random.

This element may take tree label, say $L$, $R$ and $M$. The label can be found in $O(1)$ time. If the label is $M$, then we found the solution. Else, if the label is $l$, then we found that this element is not solution and also all elements before it can not be a solution. similarly, this scenario is also correct when the label is $R$, i.e. this element is not solution and also all elements after it can not be a solution. This leads a binary like search algorithm with the difference  that the first element is not the median of array.
we can summarize the above statements as the following algorithm.

Input: An array $A$ with length $n$.
while length(A) > 1 do
 1.  choose an element $k$  (for example, randomly with uniform
     distribution) with $O(1)$. Find its label with $O(1)$.
 2.If the label is $M$, then stop
 3. else if the label is $l$ then  delete $k$ and all elements before $k$.
 4. else if the label is $r$ then  delete $k$ and all elements after $k$.
end while

I know that the worst case complexity is  $O(n^2)$ and the best complexity is $O(1)$. What is the average complexity?


texts:
I have a very large unsorted file, 1000GB, of ID pairs

ID:ABC123 ID:ABC124
ID:ABC123 ID:ABC124
ID:ABC123 ID:ABA122
ID:ABC124 ID:ABC123
ID:ABC124 ID:ABC126

I would like to filter the file for

1) duplicates

example
ABC123 ABC124
ABC123 ABC124

2) reverse pairs (discard the second occurrence)

example
ABC123 ABC124
ABC124 ABC123

After filtering, the example file above would look like

ID:ABC123 ID:ABC124
ID:ABC123 ID:ABA122
ID:ABC124 ID:ABC126

Currently, my solution is this

var hash;

foreach line in file
      get ID1
      get ID2

      if exists in hash ID1ID2 or exists in hash ID2ID1
        //next line, as we have already have this in our collection
      else
         add to hash ID1 ID2
         print the line

which gives me the desired results for smaller lists, but takes up too much memory for larger lists, as I am storing the hash in memory.

I am looking for a solution that will take less memory to implement.
Some thoughts I have are

1) save the hash to a file, instead of memory

2) multiple passes over the file

3) sorting and uniquing the file with unix sort -u -k1,2 , but that takes many hours and it also doesn't reduce the file that much.
So even if I run that sort,  Most of the filesize is retained.
 when the hash is searched for ID2ID1 , I still have to load a huge file into memory


texts: Distinct elements count of huge multiset

texts:
I know that HyperLogLog can approximate the distinct elements count of a huge multiset but I was wondering if it was possible, using a method I saw mentioned on an IRC channel, to get an exact answer while still using significantly less space than a traditional approach.

Would the following work to compute the exact (not approximate) distinct elements count of a huge multiset?

The idea is to use a Bloom filter twice, first processing the data one way, and then in reverse and additionally using a map (whose size is much smaller than the huge multiset -- this property is provided by the Bloom filter).

1st pass
create an empty bloom filter
create an empty map
for each element from the multiset
    if already in the bloom add to the map with key element / value 0
    else add to the bloom

Second pass is nearly identical but elements from the huge multiset are processed in reverse (multiset doesn't need to be an ordered set: it simply needs to have its elements iterated from the end to its beginning).

2nd pass
    empty the bloom filter (but not the set)
    for each element from the multiset (but processed this time in reverse order)
        if already in the bloom add to the map with key element / value 0
        else add to the bloom

At this point the map contains a list of potentially, but not necessarily, clashing entries in the multiset. So the entries are all set to zero.

3rd pass
   cnt = 0
   for each element in the multiset
       if present in the map, increment value in that map for that key
       else increment cnt

Exact cardinality is now equal to "cnt + nb entries in the map whose value is 1 or greater".

This requires three passes but uses space identical to a Bloom filter plus a map to count the x% of entries the Bloom filter couldn't answer if they were present or not.

I hacked a quick proof of concept and did some generative testing and it seemed to give the correct answer but I'm really not sure.

Is it possible to compute the exact distinct element count of a huge multiset this way?


texts: How many different trees can we form from given graph?

texts:
I'm trying to practice some combinatorics and I faced this problem, let's say we have given graph with N nodes and M edges. $$N\leq500, M \leq N\cdot(N - 1)/2$$

In this graph I want to count the sub-sets of edges such that each subset will have exactly $N-1$ edges and the edges forming the subset will form connected graph.

Example

Let's say we have the following graph

We can count a total of 3 subsets: {1,2,3,5}, {1,2,3,4}, {1,2,4,5}. Please note the the numbers from 1 to 5 are marking the edges, not the nodes.

What I think

Let's say our graph is complete graph, it is the worse case. If we have 500 nodes and 499 nodes going out from each node, I think that there could be $500^{500}$ possible combinations which is huge number.


texts: Converting Decimal Numbers between 0 and 1 to Binary

texts:
I've been playing around with a program I wrote that converts decimal numbers to binary numbers and i've noticed that eventually, after applying the algorithm (multiply by 2, subtract 1 if greater than or equal to 1), to convert a decimal to binary, the results turn strange likely due to floating point imprecision.
For example, the following is a result you might find when applying the algorithm:

The number 0.531904 multiplied by 2 and then subtracted by 1 should result in 0.063708 instead of what is highlighted. Successive instances of this cause the error to eventually propagate to a much greater margin after more iterations.
Thus, I have made 3 observations:

For a decimal between 0 and 1 with "N" places after the point, multiplying it by 2 should never make it more than "N" places. (e.g. multiplying 0.022, where N=3, by any power of 2 should never give it a fourth place etc.)

For a decimal number between 0 and 1 with "N" decimal places beyond the dot. (e.g. 0.022 has N=3 and 0.0101 has N=4) if the binary representation is repeating, then the repeating portion should be no longer than 10^N digits.

For a decimal number between 0 and 1 with the last (rightmost) digit being {1,2,3,4,  ,6,7,8,9} it will always have a repeating representation in binary. It will only not have a repeating representation if the last digit is 5.

My Questions are as follows:

Are these observations true?

If so, is rounding the number to "N" decimal places at every iteration step an appropriate way to fix the problem of precision?

Can someone confirm the result I obtained that 0.002992 has a repeating portion that is 12500 digits long?


texts: Why unsafe state not always cause deadlock?

texts:
I was reading Operating Systems by Galvin and came across the below line,

  Not all unsafe states are deadlock, however. An unsafe state may lead
  to deadlock

Can someone please explain how deadlock != unsafe state ?
I also caught the same line here

  If a safe sequence does not exist, then the system is in an unsafe
  state, which MAY lead to deadlock. ( All safe states are deadlock
  free, but not all unsafe states lead to deadlocks. )


texts: How to prove that one problem belongs to class P?

texts:
Is there any typical proving method when proving that one problem belongs to class P?
For example, when proving that
The problem of finding n to the kth power is the P problem. (Each multiplication can be done in unit time)
If you present an algorithm that can solve this problem with $O (\log n)$, can it be a proof?


texts: How to represent software code for code generation / automatic programming? How to integrate procedural and declarative knowledge?

texts:
I am learning about deontic logics and there I can make the following inferences: If A then there is **duty to create an entity of class C**, If B then there is **duty to assign value 5 to the attribute c.a**, if A and B then **the computation D should be executed**. I. e. those deontic logic statements contain the usual propositional variables A, B, C, but they also contain actions - pieces of procedural knowledge, like create an entity of class C and so on. The questions are:

How do I represent those actions in such manner that they can be used for the code generation/automatic programming? The simple approach can be to represent them by their content - e.g. by the code in the industrial programming language.
The goal of such reasoning is to create the syntactical tree of the program from which the source code in the industrial programming language can be read as source file. How do I represent actions that they can form the syntactical tree?

I feel that the deontic logic (formalized norms) are enough for generating software code (at least business layer - classes and their behavior), but I am struggling with the consequent end of the inference - how to represent actions/source code?

This may be seen as the more general question as well: formalized norms can be seen as the declarative knowledge and we should create reactive, procedural programs / procedural knowledge from the declarative knowledge - how to represent procedural knowledge and how to create procedural knowledge from the declarative knowledge? Are there research efforts to do this and what are keywords for this type of reasearch (so - I can find the already achieved results in Google or journal databases).


texts:
I'm studying a simple max flow problem:

Each type of object $a_1, a_2...$ can be stored in some of several stores $b_1,b_2...$. This is described by this graph:

There are $|a_i|$ objects of the type $a_i$. Store $b_j$ can contain at most $|b_j|$ objects. This shows as capacity constraints on the graph. The other edges have no capacity constraint and just mean "this type of object can be stored in this store". We want to maximize the total number $N$ of objects being stored. Max flow on this graph answers to this question.

Now we add a priority idea. Each type of object $a_i$ has an integer priority $p(a_i)$ say from $1$ to $2$ for simplicity. Instead of maximizing the total number of objects, we want to maximize $(N_1,N_2)$ in lexicographical order where $N_p$ stands for the number of objects with priority $p$ being stored.

Do you see a way to formalize this problem as a flow problem (possibly with a broader meaning than just simple max flow)? Or a way to use max flow algorithms to solve it?


texts:
So I have been given the task of creating an PDA that recognises the language

$\{a^{2n} b^{3n} \mid n = 0,1,2,\dots\}$.

Am I right in thinking that it needs to have at least 3 times number of $b$'s than $a$'s?

So for example:
$aabbb$ would be accepted
$aaabb$ would NOT be accepted
However, how do I show that using JFlap because I am unfamiliar with the software?


texts: P-time reduction A < B where B has no no-instance

texts:
I had a question to prove whether a reduction can exist $A < B$, if B has no no instances and one yes instance. I am not sure if this is too trivial.

Let $A \in P$ and $Y$ be the only yes-instance for $B$.
I build a TM, $M$ that solves $A$ in $P$-time. I build $T_y1$ and $T_y2$ which erase the input and writes the code of Y. I mark the first as an accept state and the latter as a reject. I build a machine M that gets the output of $T$, if $T$ accepts, it goes to $T_y$, if it rejects it goes to $T_y1$, otherwise $T_y2$.

Is this approach correct or too simplistic? or even, can such reduction happen?


texts:
What algorithm should be used here to solve this problem efficiently?

One file stores 5 year log of user IDs & their website visit dates in random order. There were around 1,000,000 users on the website and 1/4 of them were active. Active users visited the website 100 times a day on average.

You need to create a new file in which user IDs would be sorted in ascending order. For the same user IDs records should be sorted by their visit date in ascending order.

Input example:

1234567890 2013-03-08 12:26:09
0987654321 2013-03-09 09:23:17
1234567890 2014-01-01 00:00:34
0087645544 2015-02-03 17:45:01
0087645544 2015-01-03 11:05:06

Output should be:

0087645544 2015-01-03 11:05:06
0087645544 2015-01-03 17:45:01
0987654321 2013-03-09 09:23:17
1234567890 2013-03-08 12:26:09
1234567890 2014-01-01 00:00:34

What I've tried so far:

From what I've yet found out, the External Sort algorithm should be used here. But how exactly, there are different types of it (2-way, k-way etc)? And how do I apply it to the second column (which is visit date)?


texts: In the Curry-Howard isomorphism as applied to Hindley-Milner types, what proposition corresponds to a -> [a]?

texts:
(Using Haskell syntax, since the question is inspired by Haskell, but it applies to general Hindley-Milner polymorphic type systems, such as SML or Elm).

If I have a type signature f :: a -> [a], what is the logical proposition encoded by that type signature?

I know that type constructors like ->, (,) correspond to "operations" in your logic: -> corresponds to the "implies" symbol $\rightarrow$.

I assume [] is a type constructor as well, and have a feeling that the answer may have something to do with its recursive definition, which I know could be implemented as something like:

data List a = Cons a (List a) | Nil

but I'm not sure what this means in logic-verse.


texts: Why do we have to trade abstraction for speed?

texts:
Why can high-level languages seemingly never reach lower-level languages in terms of speed? Examples of high-level languages would be Python, Haskell, and Java. Low-level languages would be trickier to define, but let's say C. Comparisons can be found all around the Internet$^1$ and they all agree that C is a lot faster, sometimes by a factor of 10 or more.

What is it that causes such big difference in performance and why can't high-level languages catch up?

Initially I believed that this is all the compilers' fault and that things will improve in the future, but some of the most popular higher-level languages have been around for decades and they still lag behind when it comes to speed. Can't they simply compile to a similar to C syntax tree and then follow the same procedures that generate the machine code? Or perhaps it's something to do with the syntax itself?

$^1$ Examples:

The Computer Language Benchmarks Game
Julia's benchmark page


texts: Embedding trees of diameter four is NP-hard

texts: Suppose that $T$ is a tree of diameter four and $G$ is a graph. Deciding, whether $T$ can be injectively mapped to $G$ is NP-hard (there is a simple reduction from the problem of finding an independent set). I want to use this result as a side remark in my Bachelor's thesis. I believe that this should be a well-known problem, though I was not able to google it. Do you know some relevant literature to this?


texts: Is traversing an unconnected graph possible?

texts:
I have been assigned a fun project: design and implement a program that maintains the data of a simple social network. Each person in the network should have a profile that contains his name, current status, and a friends list.

I think it is clear that the project calls for the use of the ADT graph. Each vertex represents a person in the network and an edge between vertices a friendship. Now, the graph may not be connected because some members do not have any friends in the network. With that in mind, consider this feature that must be implemented:

•The network must have a feature that computes the “emergency phone chain," make sure that each member in the network is contacted, and only by one person. Any of the people in the network may initiate the first call. Utilize a depth-first graph traversal algorithm.

Now, what I think my professor is suggesting is merely a full traversal of the graph. How is that possible for an unconnected graph? Any suggestions?

(btw, the wording above is somewhat unclear - does the professor mean that everyone in the network is contact by the same one person? Thoughts? I would ask her, but she is unavailable until next week.)


texts:
I just started learning context free grammar and Pushdown Automata, I tried implementing this particular language via a PDA, despite being told this language is context sensitive.
How I attempted it is by popping every 2 'a' for 1 'b' and then popping 1 'b' for 2 'c'. I don't understand why is this wrong.
I feel I am be overlooking something really minuscule.


texts: Strongly connected orientations of undirected graphs

texts:
I'm trying to prove the following.

  There exists a strongly connected orientation of a connected, undirected graph $G$ if, and only if, $G$ has no bridge.

(An orientation of an undirected graph is a directed graph made by replacing each edge $uv$ with exactly one of the directed edges $(u,v)$ and $(v,u)$; a directed graph is strongly connected if it contains a directed path from $u$ to $v$ for every pair of distinct vertices $u$ and $v$; a bridge is an edge whose deletion disconnects the graph.)

I can prove just one side.
Assume that there is no bridge in the graph. So, for vertices $u$ and $v$, we can remove the edge which is between them and still there are(is) some paths(path) in the graph which we can reach $v$ from $u$ (so still the graph is connected). Because there is no bridge in the graph and every pair of vertices are reachable from the other without the edge of between them, we can convert the undirected graph to directed graph.

how about the other side? how can I prove that?

Can I say that, because the graph is undirected and it can be converted to a digraph, for each arbitrary pair of vertices $u$ and $v$ there is a path (or maybe some paths) which we can reach $v$ from $u$ and vice versa except the directed path of between them (the edge between them). So we can remove the directed path of between them. So there is no bridge edge in the graph.


texts:
I've been given an exercise to solve which goes as follows:
generate an NFA from the given CFG,

$$\begin{align*}S &\to AB \mid c\\
A &\to aAb \mid c\\
B &\to bBa \mid c\ .
\end{align*}$$

Now correct me if I'm wrong, but if this language has an NFA it means it is regular.
But looking at this grammar the language described is
$L=\{a^n cb^{n+k}ca^k\mid n,k\geq 0\}$.
If so, I can use the pumping lemma by taking the promised number $n$, choose the word $a^ncb^{n+k}ca^k$, for $xyz$ we get $x=a^s$, $y=a^t$ ($t\ge1$), then I can pump for $i=2$ and get $a^{n+t}cb^{n+k}ca^k$ which is not in the language. Hence the language is not regular and that means there can't be an NFA for it.

I might have done something wrong but I cant see it. Any suggestions?


texts: Turing machine accepts two different strings

texts:
I am having hard time to proving this problem

$C=\{\langle M \rangle \mid M \text{ is a Turing Machine , } L(M) \text { only contains two different strings}\}$

some ideas that i have tried are :

i have to prove if $C$ is not recursively enumerable. I know if $A$ is recursively enumerable, and $co\text{-}A$ is recursively enumerable, then $A$ is recursive. so the first idea is proving if $co\text{-}C$ is recursively enumerable, but i stuck in how to find $u$ and $v$ so that $co\text{-}C$ will not accept.
as co-halting problem is not recursively enumerable, i think $C$ can be reducible from co-halting problem. then if TM $M$ that recognizes $C$ can be use to solve co-halting problem that it proves the problem, but i don't really understand how exactly to prove it.
the idea is the same with #2, but using $A_{TM}$.

Can anyone give me some explanation this problem, or what the best way to prove the problem.

thank you a lot.
EDIT : the problem is how to prove $C$ is not recursively enumerable


texts: Combining Production Rules using Reinforcement Learning

texts:
Production systems have been used to solve puzzles such as the Tower of Hanoi for years with hard-coded production rules. However, has there been any research in using reinforcement learning to combine basic production rules into more complex ones with the goal of solving a puzzle?

Note that I've asked a similar question on Cogsci.SE, but with a greater cognitive perspective. In my opinion, the two perspectives are different enough to merit semi-cross-posting.


texts: Min spanning tree that preserves total weight of original graph

texts:
I have a directed, weighted graph with no double edges. Each node represents a person, and each edge represents a debt. I want to reduce the total number of transactions required to settle all debt, i.e. have the smallest number of edges while maintaining fairness.

I've noticed that you can eliminate edges when you owe person A who owes person B, but you also owe person B. Therefore, you can take on the debt of A directly, reducing the size of the graph to two edges instead of 3:

   ME                   ME
  /  \                 /  \
 /    \               /    \
B <--- A     ====>   B      A

(ME points to A and B)

I'm having trouble coming up with a general approach for this, and I'm not sure what to google since this is an unusual use of spanning tree.

I've thought about building up the graph one edge at a time, then analyzing what simplifications can be made, but the build order seems to matter and often does not produce the most optimal graph.

Edit: formalized constraints

There is a set of individuals $p$ that may owe each other money. For any pair $(p_i, p_j)$, if they owe each other money, it is one directional, i.e. $p_i$ cannot owe money to $p_j$ if $p_j$ owes money to $p_i$.

You are given a list with entries $p_x \to p_y, n$ where $n \in R$. This means that $p_x$ owes $p_y$ $n$ amount of dollars.

Your goal is to return a list of identical form with the following constraints:

It is fair in the sense that each individual in $p$ incurs a wealth difference as if the transactions in the original list were performed.
It is the shortest such list possible


texts: Someone explain the venn diagram for the logic equation A*(B+C)

texts:
So, I am studying logic circuits and how to prove them with Venn diagrams. When drawing a Venn diagram for the equation A*(B+C) I figured it would look something like this:

But according to the answer key, and wolfram alpha, it looks something like this:

Can someone explain why this is? Because doesn't A*(B+C) simplify to AB + AC, which would only be the two shaded regions?


texts: If A is mapping-reducible to B and is not mapping-reducible to co-B, is A Turing-reducible to co-B?

texts:
If $A \leq_m B$ and $A$ is not mapping reducible to $co\text{-}B$, then $A \leq_T co\text{-}B$.

Is this true?

My intuition is false even if we can find some special case to make it true such as $A=B=co\text{-}A_{TM}$. However, I still can't find a counterexample.

Could anyone give me a little hint?


texts: How to calculate average waiting time for round robin cpu scheduling?

texts:
I have tried to calculate average waiting time for the below details there are two answers I'm getting using two methods I'm not understanding which one is correct?

The time quantum is 2
This is the first method:

Process Id         Arrival Time        Burst Time
P0                      0                   5
P1                      1                   3
P2                      2                   1
P3                      3                   2
P4                      4                   3

This is the first gantt chart:

P0      P1      P2      P0      P2      P4      P1          P0          P4
0-2     2-4     4-5     5-7     7-9     9-11    11-12       12-13       13-14

Process Id         Waiting Time
P0                     8
P1                     8
P2                     2
P3                     4
P4                     7

  Average waiting time1: 29/5=5.8

And this is the second method:

This is the second gantt chart:

P0      P1      P2      P3      P4      P0      P1          P4          P0
0-2     2-4     4-5     5-7     7-9     9-11    11-12       12-13       13-14

Process Id         Waiting Time
P0                     9
P1                     8
P2                     2
P3                     2
P4                     6

  Average waiting time2: 27/5=5.4


texts: How to calculate whether a parenthesis string is valid using a 2-tape Turing machine?

texts:
If I have a language over alphabet $\Sigma=\{(,[,],)\}$. How can I find out if a tape has a valid (matching) parentheses structure in linear time?

So far, my attempt is as follows:

state 0: accept ( or [ i.e. no open parentheses
state 1: accept ), ( or [ i.e. a ( has occurred previously
state 2: accept ], ( or [ i.e. a [ has occurred previously

The problem with this setup is that I won't know how many ( or [ has occurred previously. One idea was to store how many occurrences of open parentheses of each kind on the second tape, but this would potentially require an infinite tape alphabet. So it seems as if I'm approaching the problem the wrong way.

How can I create a Turing machine that wouldn't need to store the amount of open parentheses while still being able to accomplish this in linear time?

I looked at this question already, but couldn't figure out how this would be applicable to multiple types of parentheses and still be done in linear time.

Any input would be much appreciated!


texts: Given the definition of a regular language is one that can be expressed with finite memory, how is $\{1^n \mid n \geq 1\}$  regular? The $n$ is unbounded. I know a DFA can be drawn, which means the language is regular. But I thought another condition is that $n$ must be bounded, so it's as if the 2 tests contradict each other?


texts:
Reading Fundamentals of Database Systems 7th Edition, on Page 603, it says,

  Indexes can also be characterized as dense or sparse. A dense index has an index entry for every search key value (and hence every record) in the data file. A sparse (or nondense) index, on the other hand, has index entries for only some of the search values. A sparse index has fewer entries than the number of records in the file. Thus, a primary index is a nondense (sparse) index, since it includes an entry for each disk block of the data file and the keys of its anchor record rather
  than for every search value (or every record).

Is that true though? As far as a database is concerned, if there are no sparse-indexes provided, is it said that all data-files have no "primary index"? I get that a specific designation for a sparse unique index on a block may be required, but is that what primary means? What does this mean for a database, like PostgreSQL, that implements Primary Keys on a dense btrees, and stores its rows in an unordered heap? Does it, technically, not have a "Primary Index"?


texts: This doesn't seem like a valid regular grammar; my instructor says it is

texts:
The following is a screenshot of a lecture slide from my programming language concepts course:

According to Wikipedia and other sources, a regular grammar is one that is either left linear or right linear, meaning it has at most:

one nonterminal symbol on the left end of its right hand side

e.g., A -> Ba

one nonterminal symbol on the right end of its right hand side

e.g., A -> aB
But if we follow this definition, then the "regular grammar" in the screenshot above isn't really a regular grammar because it has two nonterminal symbols on its right hand sides.
My teacher argues it "technically" is because:

Identifier -> Identifier Letter

is "essentially" the same as writing multiple things like:

Identifier -> Identifier 'a'
Identifier -> Identifier 'b'
...

More generally, my instructor says that if a grammar's production rules can be reduced to a form where they have at most one nonterminal symbol, then that grammar is regular. To me, this doesn't seem correct—because then essentially, just by substitution, we can reduce any grammar we want to a regular form. And it seems to destroy the definition/restriction imposed on regular grammars, which is that they may have at most one nonterminal.
Could someone please clarify whether this is in fact a valid regular grammar?


texts: Assuming $\mbox{BPP}\subseteq \Pi_2$ -What conclusions can we make?

texts:
I'd like your help with the following question:

Assume we proved that $\mbox{BPP}\subseteq \Pi_2$ -What conclusions can you make?

BPP  is  the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most 1/3 for all instances,

$\Pi_2$ is the class of all languages $L$ such that there's a polynomial algorithm $M$ and a polynom $p$ so that $\forall x.x\in L\Leftrightarrow \forall u\in \{ 0,1 \}^*.\exists v \in \{ 0,1 \}^*.M(x,u,v)=1$.

We already know that   $\mbox{BPP}\subseteq \Sigma_2$, so $\mbox{BPP}\subseteq \Pi_2\cap \Sigma_2$.


texts: Solving recurrence relation with square root

texts:
I am trying to solve the following recurrence relation :-

$T(n) = T(\sqrt{n}) + n$ using masters theorem.

We can substitute $n = 2 ^ m$

$T(2^m) = T(2 ^ {\frac{m}{2}}) + 2^m$

Now we can rewrite it as

$S(m) = S(\frac{m}{2}) + m$

The big $O$-notation for $S(m)$ will be $O(m)$.

Hence, $T(n) = T(2^m) = S(m) = O(m)$.

So we can say that $T(n) =O(\log n)$ as $n=2^m$.

But the answer is $O(\log\log n)$ . What is wrong with my approach ?


texts: Find all pairs of strings in a set with Levenshtein distance < d

texts:
I have a set of $n = $ 100 million strings of length $l = 20$, and for each string in the set, I would like to find all the other strings in the set with Levenshtein distance $\le d = 4$ from that string.  The Levenshtein distance (also called the edit distance) between two strings is the number of insertions, deletions and/or replacements required to convert one string into the another.

This should be possible in $O((d + 1)^{2d + 1} \cdot l \cdot n)$ time with a Levenshtein transducer, which takes a single query string at a time and find all the matches in a set with Levenshtein distance $\le d$.  However, using the implementation at that link, it appears to take more like $O(n \log n)$ time rather than $O(n)$, and uses more than 200 GB of memory.

Is there an alternate $O(n)$ approach that might be faster in practice?  The Levenshtein transducer is more general than it needs to be for this application, since it finds matches for each string independently and doesn't exploit the fact that you're comparing every string against every other string.


texts: Difference between edges in Depth First Trees

texts:
I have a directed graph, where each node has an alphabetical value. The graph is to be traversed with topological DFS by descending alphabetical values (Z-A).

The result is $M,N,P,O,Q,S,R,T$ (after reversing). Several DFS trees are created during this traversal, and it's the edges between the trees that confuse me. I understand how tree, back, forward and cross edges work in simpler graphs - but this one's harder.

For the example, with the graph

We have the next depth-first trees:

$T$
$S\rightarrow R$
$Q$
$P\rightarrow O$
$M$
$N$

And my question is regarding the edges that connect the trees.

Which are cross edges (like $O,R$), which are back edges and which are forward edges? And giving an example of when they are assigned as back edges / cross edges would be awesome.


texts: Definition of extensional and propositional equality in Martin-Lof extensional type theory

texts:
Martin Hofmann states in Extensional Concepts in Intensional Type Theory (§1.1 p.[4-5]) that:

  A similar situation occurs in extensional Martin-Lof type theory where propositional and definitional equality are forcefully identified by the equality reflection rule $\frac{\Gamma \vdash P:Id_\sigma(M,N)}{\Gamma \vdash M=N: \sigma}\text{(Id-DefEq)}$

Does the above mean that we purposefully drop the proof that M and N are equal and just consider them to be equal definitionally (like a presumption)?

Then it goes on and says:

  This rule makes definitional equality extensional and undecidable.

How does it become extensional and what does it mean by becoming extensional in the first place?

And then it states:

  Moreover, type checking becomes undecidable because $Refl(M):Id_\sigma (M,N)$ holds iff $M$ and $N$ are definitionally equal.

Why would $Refl(M)$ hold only if $M$ and $N$ are definitionally equal? And why would it make it undecidable?


texts:
The problem is this,
say you have a set $E$ of elements $e$, and you have a list of elements you want to remove from this set. But for an element to be removed, one of its dependencies must stay in the set. The list of elements to remove is as follows:

$e_1$  : $a, b, c, d$ ...
$e_2$  : $e, f, g, h$ ...
...

So in order to remove $e$, one of the elements "$a$, $b$, $c$, $d$...." must remain.
The question is how to remove the maximum number of elements while keeping one of its dependencies.

Note that all elements are in the same set, so a dependency of one element can be in the list of elements to remove.
Also if it helps, there is an upper bound on the number of dependencies for an element.


texts: Show that maximum disjoint set problem is NP Complete

texts:
I have been thinking on this problem but couldn't come up with a good reduction yet. First part of the proof, i.e L is being in NP, is okay. However, I cannot find a proper reduction from 3-CNF-SAT to MAXIMUM-DISJOINT-SET problem.

Edit 1: MDS definition
MAXIMUM-DISJOINT-SET problem: We are given a collection S of
sets. We would like to find the maximum number of disjoint sets in S. K sets are said to be disjoint sets if they have no element in common(Wikipedia description).

I have tried the following ideas so far:

Let each clause in 3-CNF form be a set with each literal being its element. Our decision problem is "is it possible to find at least k-many disjoint sets?
If we put each literal of a clause to a set and distinguish between a literal and its negation, it does not work since phi = $(x_1 \lor x_1 \lor x_1)$ and $(\neg x_1 \lor \neg x_1 \lor \neg x_1)$ is not satisfiable but it is considered as disjoint set.
If we negate back all negated literals, then the set phi = ($x_1$ $\lor$ $x_2$ $\lor$ $x_3$)
and $(\neg x_1 \lor \neg x_2 \lor \neg x_3)$ is considered as non-disjoint although this function is satisfiable.

Any help is appreciated.


texts: In this book ‘Theory of computation’ By Dexter Kozen on page 313,exercise 127 he says "A set of total recursive functions is recursively enumerable (r.e.) if there exists an r.e. set of indices representing all and only functions in the set. For example, the complexity class P is r.e., because we can represent it by an r.e. list of TMs with polynomial-time clocks." How do you do what he is talking about for any collection of languages that is r.e.? How do you represent an r.e. complexity class with a list of TMs? What is an example of an enumerator that does this for any r.e. class C?


texts: Is an expression in normal form if terminates on normal order but not applicative?

texts:
Just wondering if something like this...

(λx. y)((λx. (x x))(λx. (x x)))

Would be considered to be in normal form since it terminates with y if done by normal order but does not terminate if done by applicative order


texts: Number of non deterministic finite automata that can be constructed for $n$ states and alphabet with $m$ symbols

texts:
I came across the fact that

  The number of DFAs that can be constructed for $n$ number of states and alphabet containing $m$ symbols is $n\times (\color{red}{n}^m)^n \times 2^n$

So I was wondering whats about NFA? I mean how many NFA can be constructed for for $n$ number of states and alphabet containing $m$ symbols. Surprisingly quick google reveals that this is not discussed anywhere online except at this post, which is somewhat unanswered. So I tried to answer it myself as follows:

  (Same as for DFA) Number of possible start states $=n$ (assuming NFA can have only one start state)
  (Same as for DFA) Number of final states $=2^n$, since any subset of states can be set of final states
  (Same as for DFA, except that $n$ is replaced with $2^n$) For each of $m$ symbols, transition can happen to any number states. That is, number of subsets of $n$ states is $2^n$. So, for $m$ symbols, it will be $(2^n)^m$. This happens for each of $n$ states, that is their are $n$ source states. So total number of transitions will be $((\color{red}{2^n})^m)^n$.

  So the final count turns out to be $n\times ((\color{red}{2^n})^m)^n \times 2^n$.

Am I correct with this?


texts: Build-Max-Heap: Why Start i at floor(A.length/2) rather than A.length?

texts:
Taken from CLRS third edition, a procedure is given for Build-Max-Heap

function a = build_MaxHeap(a)
for i = floor(length(a)/2): -1 : 1        // i = n downto 1
     a = max_heapify(a,i);
end

My question is why use floor(length(a)/2)? How is it different than using length(a)? Is this the same thing?

function a = build_MaxHeap(a)
for i = length(a): -1 : 1        // i = n downto 1
     a = max_heapify(a,i);
end


texts:
A perfect natural number is that which is equal to the sum of it's divisors.
For example 6 is perfect: 1+2+3=6 also 28 is perfect.

Prove the following language is NP hard:

L={< n> | n is a perfect natural number}.

You can use the fact that if

$$n=p_{1}^{m_{1}}p_{2}^{m_{2}} \cdot \cdot \cdot p_{k}^{m_{k}}$$

where $p_{i}$ are n's prime divisors, then the sum of n's divisors including n would be:

$$(1+p_{1}+p_{1}^2+...+p_{1}^{m_{1}})(1+p_{2}+p_{2}^2+...+p_{2}^{m_{2}})\cdot \cdot \cdot (1+p_{k}+p_{k}^2+...+p_{k}^{m_{k}})$$
Now I know the proof should contain a polynomial time reduction from some NP problem to this language L, most likely from SAT, I only can't figure out how to go about it, any guidance would be appreciated.


texts: What is the complexity of this prime trial division algorithms?

texts:
I have two algorithms. What are their time complexities?
The first algorithm checks the modulo of all odd integers from $3,5,...\sqrt{n}$.
The second algorithm generates a list of prime from $2,3...,\sqrt{n}$ and divides the input, $Num$ by these primes.

Algorithm 1 needs $\sqrt{Num}/2$ modulo divisions in the worst case, and Algorithm 2 needs just $\sqrt{Num}/\log{n}$ modulo divisions.
Algorithm 1:

        bool IsPrime(BigInteger Num)
        {
            if (Num < 2) return false;
            else if (Num < 4) return true;
            else if (Num % 2 == 0) return false;
            else for (BigInteger u = 3; u * u <= Num; u += 2)
                    if (Num % u == 0) return false;
            return true;
        }

Algorithm 2:

        bool IsPrimeBetter(BigInteger Num)
        {
            ulong arrayLe = (ulong)Isqrt((long)Num);//Sqrt of Num
            if (Num < 2) return false;
            else if (Num < 4) return true;
            else foreach (var prime in new Atkin(arrayLe))//Atkin sieve which generate list of primes from 2 to √Num
                    if (Num % prime == 0) return false;
            return true;
        }

I don't really know how to check complexity of them.


texts: Is the language $a^i b^j c^k$ with $i+j > k$ context-free?

texts:
I am learning about Context Free Grammars and currently stuck on the following question.

  Is the following language context-free? If not, then how can we prove it using Pumping Lemma?

  $\qquad L = \{a^i b^j c^k \mid i,j,k \geq 0 \land i+j > k\}$.

After spending some time I have been able to generate the production rules for the following language, but unable to understand and conclude the above.

Important Condition ($i+j = k$)

  $\qquad M = \{a^i b^j c^k \mid i,j,k \geq 0 \land i+j = k\}$.

$\qquad\begin{align*}
  S &\to aSc \mid X \\
  X &\to bXc \mid ε
\end{align*}$

Any assistance in solving the condition ($i+j > k$) would be a great help.


texts: What is the possible number of states in the DFA of intersection of two given FA?

texts:
Consider a DFA over $a,b$  accepting all strings having number of $a$ 's divible by 6 and number of $b$ 's divisble by 8. What is the minimum number of states in the resultant DFA ?

This problem can be solved by assuming 2 DFAs. One accepting the number of $a$ 's divible by 6 and the other accepting with number of $b$ 's divisble by 8. And then taking intersection of them. So what will be the number of states in the resultant DFA?

I tried drawing the DFA accepting all strings having number of $a$ 's divible by 3 and number of $b$ 's divisble by 3, and found it to have 3x3 (9) states. Can I asssume the reuslt to be 48 states for this case? Can it be inferred that the for string accepting number of $a$ 's divible by $m$  and number of $b$ 's divisble by $n$ , there will be $mn$  states? Or I need to draw it by hand? Or anything other? Any subtle hint will be very helpful.


texts: What is µ A below ~ x in the Fuzzy Logic

texts:
I am reading the book "Fuzzy Logic with Engineering" written by Timothy J. Ross and there is a phrase in the book at page 90, he mentions about the "Features of the Membership Function". He says:

  The support of a membership function for some fuzzy set A under ~ is
  defined as that region of the universe that is characterized by
  nonzero membership in the set A under ~. That is, the support
  comprises  those elements x of the universe such that μ A under ~
  (x)>0.

He denotes it as a graphical representation:

what is μ A under ~ (x) in this context?  Thanks in advance.

Edit Post
The μ A under ~ (x) in this context is membership function. https://www.tutorialspoint.com/fuzzy_logic/fuzzy_logic_membership_function.htm


texts: Given $n=pq=a^2+b^2$, can we factor $n$?

texts:
Just to be clear, $a$ and $b$ are known, while $p$ and $q$ are unknown prime numbers, both congruent to $1$ modulo $4$. Can we design an efficient algorithm to retrieve $p$ and $q$?

It is a known result that $p$ and $q$ can be written as a sum of two squares in exactly one way, and $n$ can be written in exactly two ways.
If $p=x^2+y^2$, $q=z^2 +t^2$ then
$a^2+b^2=(x^2+y^2)(z^2+t^2)=(xz+yt)^2 + (xt-yz)^2=(xt+yz)^2+(xz-ty)^2$

So we get two possible systems of equations involving $a,b,x,y,z,t$, but it's not obvious how to solve the systems in general.


texts:
In an image processing project (using opencv with python), I am trying to detect as precisely as possible the location of a rectangular object in a photograph. My final goal is to output the 4 corners of the object.

For example, an image could look like this:

In the first stage I am able to detect an approximate boundary for the image, like so:

Now, I have the above red convex polygon.

Next, I would like to compute the Minimum Area Bounding Quadrilateral, and this is where I'm stuck.

My question is, given a convex polygon, what is an efficient algorithm to find a minimum area bounding quadrilateral?

Thanks!


texts: what interpolation method can I use for reliefs

texts: I need to know which interpolation method is the best for working with reliefs, that is, to know the elevations or depths of a given terrain a set of points.


texts: Longest path of a DAG containing a single node?

texts:
I'm interested in implementing an algorithm detailed on this Wiki page for finding the longest path of a DAG.

The second part of the algorithm says the length of the longest path of a node with no outgoing edges should be zero, but my programming professor says this node should return 1 as its longest path length. (Perhaps he says this assuming each node's length is set to 0 and a recursive function that visits each node will add 1 to whichever child has the longest path.)

I think that if someone can answer the question: what is the length of the longest path of a DAG containing a single node, then I will have an answer to my question. Though, I'm not sure if a single-node graph constitutes a DAG.

As you can probably tell, I'm new to graphs, so any guidance is appreciated.


texts: Can 2-philosophers problem be analogous to dining philosophers problem?

texts:
Two philosophers A and B, two forks numbered "1", "2"; A needs both "1" and "2" for eating, so does B.

Is this theoretical a dining philosopher problem? I'm questioning about the forks philosopher A needs all come from B. However, the DP problem usually gives an example of 5 philosophers, in which case, for example, philosophers A requests 2 forks from two different neighbors.


texts: Decide if Turing machine's language contains either a or b string

texts:
during school exercises we worked on decidability problems and there was one I don't really understand. We were provided with solution and explanation regarding this exercise but still I need more guidance.

The problem is:

Proof that
$L = \{ <M> | M$ is Turing machine, $ |L(M) \cap \{a,b\}|= 1\} \notin REC$

Idea of proof:

reduction from Halting problem
machine $M_x$ (output of reduction function) checks if on its input is $a$, saves this information
if $<M_h,W_h>$ (instance of HP) does not have required structure, $M_x$ rejects
$M_x$ simulates $M_h$ on $W_h$, if $M_h$ accepts, $M_x$ accepts if on its input it had $a$, otherwise rejects... if $M_h$ is in loop $M_x$ is in loop also

then

$L(M) = \emptyset$ if $<M_h,W_h>$ has structure corrupted or $M_h$ is in loop on word $W_h$
$L(M) = \{a\}$ if $<M_h,W_h>$ has correct structure and $M_h$ halts

How I see it:

$M_x$ saves information of its input

if $M_h$ halts, $M_x$ checks saved information regarding input, if it contains $a$ or $b$ accepts, otherwise rejects

then

$L(M) = \emptyset$ if $<M_h,W_h>$ has corrupted structure or $M_h$ is in loop on word $W_h$
$L(M) = \{a\}$ if $<M_h,W_h>$ has correct structure and $M_h$ halts with input $a$
$L(M) = \{b\}$ if $<M_h,W_h>$ has correct structure and $M_h$ halts with input $b$

I do not understand what happened with $b$.


texts:
Consider the following problem statement:

  Given an initial number, you and your friend take turns to subtract a perfect square from it. The first one to get to zero wins.
  For example:

  Initial State: 37

  Player1 subtracts 16. State: 21

  Player2 subtracts 8. State: 13

  Player1 subtracts 4. State: 9

  Player2 subtracts 9. State: 0

  Player2 wins!

  Write a program that given an initial state, returns an optimal move, i.e. one that is guaranteed to lead to winning the game. If no possible move can lead you to a winning state, return -1.

This problem can be solved in pseudo-polynomial time using dynamic programming. The idea is just filling an array of length n (where n is the initial state) bottom up with the optimal moves, or -1 if no move leads to winning. This would take O(n * sqrt(n)) since for every number we need to consider subtracting each possible perfect square smaller than it (there are ~sqrt(n) of them). However, this is a pseudo-polynomial runtime complexity since the runtime actually scales exponentially with relation to the size of the input in binary (# of bits used to represent number).

Can anyone think of a polynomial algorithm for solving this problem? If not, could it be NP-Complete? Why?


texts: Proving a DFA recognizes a language using induction

texts:
The following DFA recognizes the language containing either the substring $101$ or $010$. I need to prove this by using induction.

So far, I have managed to split each state up was follows:

q0: Nothing has been input yet.

q1: The last letter was a $1$ and the last two characters were not $01$.

q2: The last letter was a $0$ with the letter before that a $1$.

q3: The last letter was a $0$ and the last two characters were not $10$.

q4: The last letter was a $1$ with the letter before that a $0$.

q5: At least one of the two substrings has been seen.

Induction basis: The empty string does not have either of the substrings, so is correctly rejected.

But I am not too sure on how to proceed after this. I do not know how I should split the string up to prove that the $DFA$ is accurate.

If anyone knows how I should proceed with this, I would love some help!


texts: Are there any decision complexity classes which have no "complete" subclass?

texts: Are there any decision complexity classes, where the "-Hard" version of the class does not intersect with the original class?


texts: What would be a natural generalization of a byte parity check?

texts:
Suppose that we have a group of N bytes. One can add a very basic (and not particularly reliable) check of the consistency of this data by storing an additional (N+1)th byte containing exclusive XOR of all N original bytes. It will be enough to detect a single byte error during the transmission.

In the practical problem that I am trying to solve, if an error occurs during transmission, I actually will know when error occurred and which byte contains the error. Then knowledge of the (N+1)th byte is sufficient to recover the incorrect byte by simply XORing all correct bytes with the (N+1)th byte.

The errors that can occur in my application actually occur in bursts of 1 or several bytes, I will denote this number as M. There can be no more than a single burst per group of N bytes. In fact, when error occurs my transmission channel returns N-M bytes, along with the marker of the position where bytes were lost.

My question is: what would be (is there?) a natural way to generalize the simple (M=1) error correction scheme using a single XOR byte to the case where the error burst can contain up to M skipped bytes? Is it possible to do this specific kind of error correction using only M bytes?


texts: Implementing an interval tree using arrays?

texts:
Is it possible to create an interval tree using an array instead of the traditional pointer method? I know that for segment trees this is commonly done where the children of any element with index i are stored in 2i and 2i + 1 and the range is halved. For interval trees however, because the ranges added are not guaranteed to be halved each time, it seems like it might not be possible.

Could anyone prove or disprove whether interval trees can be implemented in this manner?


texts:
Is the optimization of a linear classifier convex?
Is there any local optima or saddle points for a linear classifier?


texts: PDA - Sum of Two Characters = Sum of Two Other Characters

texts:
For one problem I have to solve, I'm given a Language:

L = {a^r b^s c^t d^u | r+s = t+u}

And from it told to construct a PDA that accepts it. I can construct a PDA for

L1 = {a^r b^s | r,s >= 0}

And for

L2 = {c^t d^u | t,u >= 0}

As they are, essentially, the same language. However, I'm confused as to how I can make sure that the sum of characters in L1 equal those in L2


texts: Assume P != NP. Then there are many examples of problems in NP that are known not to be NP-complete, like 2-SAT, and many that are conjectured not to be NP-complete, like factorization. However, are there any problems that are widely conjectured but not known to be NP-complete?


texts: Need of reducing problems if we already know that a problem is undecidable

texts:
In the Reducibility chapter of Sipser's Theory of Computation book, an example is:

We reduce A(TM) to HALT(TM). And then we claim that if H decides HALT(TM), then A decides A(TM), but since A(TM) is undecidable, so is HALT(TM)

My question is, if we already know that A(TM) is undecidable, what is the need for deciding HALT(TM). It's a basic question though.

Hope you got it.


texts:
I was reviewing the post  If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?

I completely understand why $L/R$ is context free.

I just tried a different approach, which is not that rigorous according to the answers given. It is just based on the basic understanding.

How I tried :

Let $L = a^N b^N a^M b^M$ and $R = \left (a + b \right )^*$.

Then $wx$ belongs to $L$. Suppose I assume $wx = aaabbbab$.

So, now $x = ab$ which belongs to $R$.

So $L/R$ contains $aaabbb$.

Like this, I will get all strings in $L/R = \left \{ a^N b^N | N \geq 1 \right \}$.

This language is nothing but context free.

This approach is not as rigorous as what I saw in the answers.

I just want to confirm: is this approach right?


texts:
If I have the following array: pieces = {35,15,20,25,30,10}  and the time slot is 80 minutes.
How do I do the following:
1. Fill the time slot with any pieces for the perfect fit. (In our case: 30,35,15 or 15,25,30,10 etc.)
2. Fill the time slot with the best fit possible with deviation: (Let's say our time slot is 103 minutes and the deviation is +/-20 minutes. So, we are looking for the best fit anywhere in the 83-123 minute range.
3. Is there any optimizations that can be done if pieces array is sorted?

I'm looking for basic CS algorithms and strategies for optimizing runtime or space. I'm not looking for a specific solution to my problem. Instead, I'm interested in the CS topics I need to look into.

I'm able to solve the simplest version of this problem:
Find out if 2 pieces for the time slot and return true.
Solution:
Loop through the array. Create hashtable and check if hashtable contains  timeslot-pieces[i] if yes, then return true, if no, then add to hashtable.


texts:
Let's say we have a string s , a code size limit of b bytes and a time limit t, the question is then whether or not it is possible to construct an algorithm that prints the string within the time limit when a program is given no input.
In other words - is this problem decidable or undecidable?
I was thinking of reducing the Halt problem when it is given no input, but I'm a bit unsure of whether I should concider the byte size and time limit as input as well, or how I should conquer this problem.
Thank you.


texts: Range Minimum Query with Updating values

texts:
I was wondering if the following problem can be solved in asymptotically better time than$ \ O(n \log n)$.

Suppose you have an array of integers $a_1,a_2,a_3,\ldots,a_i,\ldots,a_n$ where initially for all $i$,$ \ a_i = \mathrm{INF}$.

Now, we will iterate over every element starting from $i = 1$ to $i = n$ and perform two operations.

Update the element at index $i$, $a_i = v$.
Answer a query of the form $\min$ in range $[l, i]$. This should return the minimum value in the range from $l$ to $i$ inclusive.

Of course, we can solve this problem using a Segment Tree where each node stores the minimum in the respective range.
This data structure allows us to carry out point updates in $O(\log n)$ time, and answer range queries in $O(\log n)$ time as well.
This leads to a total complexity of $O(n\log n)$ for this problem.

I know that RMQ has been studied deeply and can be done in constant time for immutable data with some preprocessing. However, in this case we are doing updates.

Is this the best we can do? Is $O(n\log n)$ a lower bound on the problem?


texts:
An NFA $M$ contains a cycle if there is a state $q$ and a string $x$ such that if $M$ is in state $q$ and reads string $x$, $M$ can return to state $q$. Prove:

If $M$ recognizes an infinite language, then $M$ has a cycle.


texts: What is a non-contrived example of static type-checking being too conservative?

texts:
In Concepts in Programming Languages, John Mitchell writes that static type checking is necessarily conservative (overly strict) because of the Halting Problem.  He gives as an example:

if (complicated-expression-that-could-run-forever)
   then (expression-with-type-error)
   else (expression-with-type-error)

Can someone provide a non-contrived answer that would really be a practical concern?

I understand that Java allows dynamically-checked casts for cases like this:

if (foo instanceof Person) {
    Person p = (Person) foo;
    :
}

but I consider the necessity of that more a Java language/compiler deficiency than a cross-language issue.


texts:
I came across generalized nondeterministic finite automata (GNFAs) in Sipser's Introduction to the Theory of Computation. These are automata where transitions are labelled with regular expressions, rather than single symbols from the alphabet. I thought he would explain why GNFAs are allowed. I mean, an appropriate explanation would be that GNFAs are equivalent to NFAs, or GNFAs are equivalent to DFAs or some such argument. But I couldn't find any such explanation in the book.

Online, I read in this article that you can convert a GNFA to an NFA as follows:

  For each transition arrow in the GNFA, we insert the complete
  automaton accepting the language generated by the transition arrow’s
  label as a “subautomaton;” this way, we can replace each regular
  expression by a set of states and character transitions

How is the automaton inserted?

Let's say we have a GNFA with an arrow going from state A to state B labelled with a regular expression R. To convert this GNFA to an NFA, do we get rid of that arrow, instead, take NFA N that recognizes L(R), and create an arrow from A to the start state of N labelled with the epsilon symbol, then create arrows from the accept states of N to B, each also labelled with the epsilon symbol?

Of course the accept states of N would no longer be accept states in the new machine, would they?

I know that GNFAs are equivalent to NFAs but I need a convincing proof, not just a short paragraph mentioning their equivalence.


texts: Compare each array $i$ member to all array $j$ member where $(i > j)$ , in time less than $O(n^2)$

texts:
I am new to algorithms so sorry to ask simple question

I am working on a problem which is about array of integers, my solution is right but not good enough, because I have time exceeded exception on codeforces. I think solution where solution's time < O(n^2) would be right.

My solution:

int n;
cin >> n;

int currentScore = n;
int credits[n];
int grades[n];
for (int i = 0; i < n; i++) {
    cin >> credits[i];
    for (int j = 0; j < i; j++) {
        if (credits[i] <= credits[j]) {
            currentScore--;
        }
    }
    grades[i] = currentScore;
    currentScore = n;
}

for (int i = 0; i < n; i++) {
    cout << grades[i] << endl;
}

return 0;


texts: I am confused about clustered index is dense or sparse. I searched for that, sources saying it is sparse, but can be dense also. What is it exactly?


texts: Finding vertices for which there either exists a path to all other vertices or other vertices have a path to them

texts:
Or in other words, find all $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ or $w \rightarrow  v$. This is for a directed acyclic graph. I need to find an $O(|E| + |V|)$ algorithm for this.

I can see how to identify if a given vertex meets these traits (perform a BFS starting at that vertex, then do another BFS on the reverse of that graph and see if every vertex was visited in those BFSes). The obvious solution would be to run this on every vertex of the graph, but that will end up being $O(|E||V| + |V|^{2})$.

I've considered identifying strongly connected components, but that doesn't seem like the right approach, since a SCC requires that $v$ and $w$ are mutually reachable, whereas this homework question requires that $v$ and $w$ are only reachable one way.

Advice?


texts: 3D gift wrapping algorithm: how to find the first face in the convex hull?

texts:
I am implementing the gift wrapping algorithm to find the convex hull of a set of points in the 3D space.

However, all the articles I have read seem to omit the description of the first step of the algorithm; namely, finding a face (that is, a triangle) in the set that will definitely be in the convex hull (and doing so in $O(n^2)$).

Example of such an article: https://www.sciencedirect.com/science/article/pii/S002200000580056X

I do understand how to find a vertex that definitely be in the convex hull: just take one with extreme coordinates.
However, I don’t know how to approach the problem for edges or faces.


texts:
The bin packing problem is an NP-hard optimization problem that has many constant-factor approximation algorithms. I am looking for an additive approximation. I.e., given a set $I$ of items and bin capacity $B$, find a packing in which the number of bins is at most $OPT(I,B)+d$, where $OPT(I,B)$ is the optimal number of bins and $d$ is some small constant (ideally $d=1$).
Here I found an algorithm that finds a packing in at most $OPT(I,B)+O(\log{OPT(I,B)})$ bins, but not $OPT(I,B)+$constant. This leads me to suspect that it may be impossible unless P=NP. But I did not find a proof of impossibility either.
Is such an additive approximation possible in polynomial time?


texts: How is there a CPU read misses on exclusive caches?

texts:
If the lower level cache contains blocks that are not present in the higher level cache or other caches then it is said to be exclusive.

It is exclusive because it is only there. How can there be cache miss when CPU is looking for it?

See img:


texts:
Min-ones SAT is apparently NP-complete. I get that it is NP-hard (because SAT is trivially reduced in polynomial time to it), but I don't actually see how minimality can be verified in polynomial time.

Thus, my question: why is Min-Ones SAT in NP?


texts: Select the n closest nodes from a starting node in a weighted directed graph

texts:
I need to select a given number of nodes from a weighted directed graph such that the nodes selected are the closest to a given starting node.  This seems like a common problem to need to solve, but I haven't found much material on it.  Does anyone know if this particular problem has a name, or any published material (formal or informal) related to it?

Note, I am not asking for a solution to the problem itself.  I am interested in finding material related to the problem.  For very large graphs, the canonical Dijkstra algorithm will not work because you must enqueue every node first.  I believe a modified version of the Uniform Cost Search will do what I want, since it does not enqueue all the nodes first.  Things get more interesting in this case, because you don't have full knowledge of all shortest paths.  I'm interested in things like how do you know when you've found all the shortest paths for the closest nodes, without traversing the entire graph in the process.  I think this is possible using an admissible heuristic as in the A* search.  These are the kinds of details I want to be able to read up on.


texts: Language of Turing machines that loop on all inputs, recognizable?

texts:
Prove that the language Loop Turning Machine =  {  < M > | M is a TM that loops on all inputs}  is recognizable.

I feel like $M$ would never halt.  To make $M$ recognizable it needs to accept or reject.  Do I need to establish a decider?

EDIT:

Can I say that a halting Turing Machine $M$ is a machine for which  exists a word $w$ such that $M$ halts on $w$?
This makes the language recognizable but the machine may go on forever if executed.


texts: Bottom-Up Parser With Leftmost Derivation

texts:
I'm reading the book Parsing Techniques by Dick Grune et al. and in section 3.1.3 "Linearization of the Parse Tree" they introduce the notion of linearization:

  [...] a parser can produce a list of rule numbers instead, which means that it linearizes the parse tree. There are three main ways to linearize a tree, prefix, postfix and infix.

Those are explained using the following grammar:

and this particular production tree (the grammar is spuriously ambiguous):

(The numbers at the nodes are semantic attributes.)

Prefix notation is explained first:

  In prefix notation, each node is listed by listing its number followed by prefix listings of the subnodes in left-to-right order; this gives us the leftmost derivation [...]:

  leftmost: 2 2 1 3c 1 3e 1 3a

Postfix notation follows:

  In postfix notation, each node is listed by listing in postfix notation all the subnodes in left-to-right order, followed by the number of the rule in the node itself; this gives us the rightmost derivation [...]:

  rightmost: 3c 1 3e 1 2 3a 1 2

Before the linearizations, there is a "leftmost" and "rightmost," respectively. Does that mean prefix notation only works with top-down and postfix notation with bottom-up parsing? But then why? If we start from the rightmost non-terminal and build the parsing tree from the top down, wouldn't the linearization with the "leftmost" in front be the result? Aren't the notations semantically independent?

Furthermore, I've read about LL and LR parsers, which yield a leftmost or rightmost derivation and use a top-down or bottom-up algorithm, respectively. Does that mean a bottom-up parser can only work with a rightmost derivation? Why not with a leftmost one? I don't see the problem with that, similarly to how prefix notation seems to imply a leftmost derivation.