texts: Clarification of the definition of a POMDP

texts:
From what I understand, a $MDP=(G, A, P, R)$ (markov decision process) is represented as:

A complete directed graph $G=(V, E)$
A set of actions $A_u$ for each vertex $u \in V$
A reward function $R$ that maps any vertex to some reward, i.e., $R \colon V \mapsto \mathbb{R}$.
A probability function $P$ that gives the probability $P_a(u, v)\in [0, 1]$ of taking edge $(u, v)$ after performing action $a \in A_u$ at node $u$

The behavior of any MDP is talked about in terms of some policy $F$, where $F_0$ is the initial state that the policy starts in, and $F(u)\in A_u$ is the action $F$ takes when at node $u$, which is defined for all $u \in V$.

We then say that the MDP starts in $u=F_0$, performs some action $a=F(u)$, then moves to some other vertex $v \in V$ with probability $P_a(u, v)$. It repeats this process, where on turn $t$ it performs an action $b=F(w)$ some node $w \in V$, then moves to some other node $z\in V$ according to probability $P_b(w, z)$.

Now, a POMDP (partially observable markov decision process) is defined in a similar manner, except at each state $u \in V$ instead of knowing it's current state, $F$ is given some observation data $O(u) \in S$, where $S$ is any set. $F$ then constructs a "belief state" $b \in [0, 1]^{\vert V \vert }$ based on that information, which is a set of probabilities associated with each node of how much it "believes" it is in that node.

Now we define $F$ in terms of what action it performs in a given belief state, where the belief state can change with time.

This all makes sense, my question it just that since there are a different set of actions for each node, how does $F$ know what actions $A_u$ it has available without knowing what node $u\in V$ it is in?


texts: Constructing a minimal pushdown automaton for counting characters in substrings

texts:
I have to construct a pushdown automaton for the following language over alphabet {a,b,c}:

L={ ucv | |u|!=|v|; u,v={a,b}* }

(note: u,v are substrings over alphabet {a,b}, |u| is length of substring u)

My tutor has constructed a PDA using 4 states, however - I believe it's possible to construct this with only 3. Here's what I came up with:

Legend: QO = initial state, QF = final/accepting state. Directed edges are named after transitions in the following form

input_character, highest_element_in_stack | new_highest_element(s)_in_stack

The basic idea behind it is:

QO counts the number of characters in substring u by pushing x's.

Q1 counts the number of characters in substring v by popping x's.

Is my PDA correct or is it missing something crucial that I haven't noticed?

Thank you in advance.


texts:
I'm new to Haskell and have some general questions.

Question 1:
The Haskell expression (\x -> \x -> x) is the same as the λ-term λx.λx.x
The type of this expression is p1 -> p2 -> p2. What does this mean?

Question 2:
λyx.x is shorthand for λy.λx.x. In Haskell (\y x -> x) is shorthand for (\y -> \x -> x). Do (\x x -> x) and (\x -> \x -> x) have the same type in Haskell and why?


texts: In a set associative cache (in this case 4-way) what happens when you try to read an entry with e.g. the tag 0x3B and this tag appears two times within the same set. Given the first is invalid, would you search on for the second (which is valid) or simply get a miss? And why do would there be a duplicate line at all?


texts: Use pumping lemma to show L is not context free

texts:
Show that L = $\{0^{2^n}| n\geq 0\}$ is not a context free language.

Let string $s = 0^{2^p}$. Then we know we can write $s$ as $s = uvxyz$. I know that |vy| > 0 and $|vxy| \leq p$.

So how do I show that $uv^2xy^2z$ is not in $L$.


texts: Why is $L = \{ \langle M \rangle : L(M) = \{ \langle M \rangle \} \}$ not Turing-recognizable?

texts:
In other words, $L$ is the language of Turing machines that recognize the language consisting of only themselves.

Why is $L$ not Turing-recognizable? $L$ is clearly not decidable by Rice's Theorem, but how do I go one step further and also prove that no machine can enumerate $L$?


texts: In his "Types and Programming Languages", Pierce, at the very end, presents the most powerful system in the book: $F^{\omega}_{<:}$. He, however, does not explain how bounded existential polymorphism would work. I could not find a reference to this online anywhere. Is this just not possible or just not very interesting or what? If this is possible could someone point me to a reference?


texts: I'm working on my school homework,even though i found all three of these. It says use limit to compare. I confused , what should i do, i mean its obvious C A B


texts: Does the normal form theorem imply that every partially computabe function is primitive recursive?

texts:
This is Normal Form Theorem (Second Edition of Computability, Complexity, and Languages written by Martin Davis page 75):

Let $f(x_1,...,x_n)$ be a partially computable function. Then there is a primitive recursive predicate $R(x_1,...,x_n,y)$ such that:
$f(x_1,...,x_n) = L(min R(x_1,...,x_n,z)_z)$ (minimization is on z)

So I think an immediate result of this theorem is that every partially computable function is primitive recursive and every primitive recursive function is partially computable. is it true?


texts:
I need to find the shortest path in a Directed Unweighted Cyclic graph. And it has to be optimal (find a path if exists one) and also optimal in terms of space and time complexity, being time complexity the most important.
I think BFS is the solution. But am not sure.

What I am doing is mapping database tables into a graph data structure. And I need the shortest path for querying the tables with joins. Am storing information in the edges related to the nature of the relationship between the tables, like foreign key field and type of relation (one2many, one2one, etc).


texts: Sorted-greedy for Load Balancing Problem

texts:
In load balancing problem we have $m$ machines and $n$ jobs, each taking processing time $t_j$. Total processing time on the machine $i$ is $T_i =\sum_{j\in A(i)}{t_j}$, where $A(i)$ is the set of jobs assigned to machine $i$. Goal is to provide an assignment of jobs, such that $\max T_i$ is minimized.

It is known that sorted greedy algorithm is only approximation solution for load balancing problem. But I can't find an instance of problem, when it actually doesn't find an optimum solution. Can someone provide an example when this algorithm gives a wrong answer?


texts: How can I compute the most general unifier for these two expressions?

texts:
I have the following first order logic expressions:

$f(g(a, h(b)), g(x, y)),~f(g(z,y), g(y, y))$

and I want to compute the most general unifier for them. If I follow the algorithm found on these slides then I get the following.

\begin{align*}
S_0 &= \{f(g(a, h(b)), g(x, y)), f(g(z,y), g(y, y))\}\\
D_0 &= \{g(a, h(b)),g(z,y)\}                    &[\text{first disagreement set}]\\
&\text{(need to unify these two functions)}\\
D_0'&= \{a,z\}                                  &[\text{first sub-disagreement set}]\\
\sigma &= \{z=a\}\\
D_0''&=\{h(b),y\}                               &[\text{second sub-disagreement set}]\\
\sigma &= \{z=a, y=h(b)\}\\
S_1 &= \{f(g(a, h(b)), g(x, h(b))), f(g(a,h(b)), g(h(b), h(b)))\}\\
D_0 &= \{x,h(b)\}                    &[\text{second disagreement set}]\\
\sigma &= \{z=a,y=h(b),x=h(b)\}\\
S_2 &= \{f(g(a, h(b)), g(h(b), h(b))), f(g(a,h(b)), g(h(b), h(b)))\}
\end{align*}
No disagreement, unifier found! $\sigma = \{z=a,y=h(b),x=h(b)\}$.

However, this is not the most general unifier as we have $\{y=h(b),x=h(b)\}\in \sigma$, so i think the MGU should actually be $\sigma' = \{z=a,y=h(b),x=y\}$.

Is this correct? When I use Prolog to unify them, it gives $\sigma'$. What did I do wrong in my following of the algorithm, so that it gave me a unifier that wasn't the most general?


texts: Confused about 3rd rule of CFG pumping lemma

texts:
Let $L = \{\space ww \space | \space w \in \{0,1\}^*$} (need to prove that $L$ is not CFL)

Assuming $L$ is CFL we can use the PL and split $s=uvxyz$ and we choose $s = 0^p1^p0^p1^p$ where $p$ is the pumping length.

Using the 3$^{rd}$ rule, namely $|vxy| \le p$, can I say that $vxy$ can consist only of $0's$ and either pumping up(e.g. $uv^2xy^2z)$ or down ($uxz$) will throw us out of $L$ ?


texts: A problem similar to the Bin packing problem?

texts:
I'm working on a problem that is very similar to the bin packing problem, but for me, the objective is to minimize the maximum weight given m bins. The problem statement is:

Given n items, each with a certain weight less than some maximum weight (w_max), how do you pack them into m bins so that you minimize the maximum weight (over all bins)?

I'm looking at a possible approach that would simply iterate by grouping the two smallest weight items until the number of groups equals the number of bins.

Has anyone heard of a similar problem and know of an approach to solve this with some guarantees?


texts: What are the recent research directions in the topic of circuit lower bounds from derandomization?

texts:
I am thinking of the classical paper, https://www.cs.sfu.ca/~kabanets/Research/poly.html

Can someome link to some papers/reviews that give a sampling of what are the recent thoughts in this direction?

I am equally happy to know of what are the recent directions in the topic of pseudorandomness and derandomization.


texts:
My friends and I are taking a formal languages class and for one of our homework questions we have to prove if these languages are regular:

1) L = {apaqi : p and q are fixed integer values, i >= 0}

2) L = {apbq : p and q are fixed integer values}

For (1), we know it is regular because we can make a DFA out of it, but what we are not sure how exactly the DFA should look like. Should it not be consist only of one state, say q0, and it acts as both the initial and final state, with a loop of "a" moves going through it? Our line of thought is because p and q could be any integers, so whatever p and q would be, we would always end up with a certain number of a's, but we are not sure we are 100% correct.

For number (2), we say it is not regular because p and q could be infinite, thus making the language automatically irregular.

We are still quite confused on which concepts are correct. This is still a very abstract concept for all of us and any guidance would be appreciated. Thank you!


texts: How can you check if a 2SAT problem has a bad loop

texts:
im trying to figure out why this is true

The clauses {a,b}, {b,~c}, {c,~a} constitute a 2SAT problem with an implication graph without bad loops.

Can someone show me how to illustrate this and indicate how i can find wether any 2SAT problem has a bad loop or not, Thank you so much :)


texts:
Can  a distributed algorithm be serial?
For example if I have 3 distinct agents in a network would an algorithm that looks like this be considered a distributed algorithm?

    Process ABC
       If (you are agentA) then
           Do stuff
       Else if (you are agent B) then
           Wait until agent A has finished doing stuff
           Do other stuff
       Else if (you are agentC) then
           Wait until agent B has finished doing stuff
           Do your own thing
       EndIf
    EndProcess

To my understanding it should be considered as distributed as long as the agents don't share memory. Wouldn't being serial defeat the purpose of having a distributed algorithm though?


texts: Selection in expected linear time: Why am I getting $O(n)$ bound instead of $\Omega(n \lg n)$?

texts:
The problem is from CLRS 9.3-1:

  In the algorithm SELECT, the input elements are divided into groups of
  $5$. Argue that SELECT does not run in linear time if groups of $3$ are used.

If we do the "divide by $3$" technique, we will come up with this recurrence --

$$T(n) = \begin{cases}
\Theta(1) & \text{if $n \le K$} \\
T(\lceil n/3 \rceil)+T(2n/3+4) + O(n) & \text{if $n \ge K$}
\end{cases}$$

I have solved by substituting $T(n) \le cn$ and  $O(n) = an$ --

$$\begin{aligned}
T(n) & \le \lceil n/3 \rceil + c(2n/3 + 4) + an \\
     & \le cn/3 + c + 2cn/3 + 4c + an \\
     & = cn + 5c + an \\
     & = (c+a)n + 5c \\
     & = c_1n + c_2 \le c_1n \approx O(n)
\end{aligned}$$

But the solution says it should be $\Omega(n \lg n)$. I understand that substitution like $cn \lg n$ could give $\Omega(n \lg n)$ bound, but what is wrong with $O(n)$ formulation above?


texts:
I've reading up on Kosaraju's algorithm to compute the strongly connected components of a directed graph and I found that

using an adjacency list representation gives a time complexity of $\Theta(V+E)$.
using an adjacency matrix representation gives a time complexity of $O(V^{2})$.

Why $\Theta$ in the first case and $O$ in the second case?


texts: No subset of RE captures the set of TMs halting on themselves as input

texts:
For a property $P$ of languages, which we identify with the set of languages satisfying it, let $L_P = \{ \langle M \rangle \mid L(M) \in P \}$ be the set of descriptions of Turing machines whose languages satisfy $P$.

  How can we prove that there's no property $\displaystyle P\subseteq RE $ for which $ L_{P}=K $, where $K=\{\langle M \rangle \mid M(\langle M \rangle)\!\downarrow\} $?


texts:
I have recently written code for detecting path colors in a 2D grid and printing the corresponding path costs and it works fine for me.
Here's my code; I am currently new to OpenCV and know only C++ (no python).

The image that I had for the project was:

Now I may get an image like this for the same task:

I need an algorithm to detect the square in the middle of the arena, rotate it to the angle by which it becomes like the image above, and then crop the rest of the image off.

I am currently at a fix about doing this.


texts: Variable Capturing With Repetition of Variable Name

texts:
I am very confused as to which variables are captured by which λ in the example below:

(λa.λb.(λa.a)aba)(ab)

I am new to lambda calculus and the repetition of variables makes this example hard for me to understand and reduce. Any help would be appreciated!


texts: How do I show that the matching polytope of $K_{2n}$ is a linear projection of the perfect matching polytope of $K_n$?

texts: Of course a matching polytope is the convex hull of edges in a matching and similarly for a perfect matching polytope.


texts: Message protocol to probabilistically infer missing object from Union of two subsets of a larger set

texts:
This was a challenge problem I read some time ago and just remembered it:

  Say you have two people, $A$ and $B$, collect objects distinctly labeled $1,...,n$. They will each separately collect sets $S_A$ and $S_B$ such that $|S_A \cup S_B| = n-k$ where $k\leq \sqrt n$. There is no guarantee in what order any of these will be collected in by each person. The goal is for $A$ to send $B$ a short message of bits so that $B$ can infer (at least) ONE of the $k$ objects missing from the union of their sets, i.e., $$k \in \{1,\ldots,n\} \setminus (S_A \cup S_B).$$
  The protocol or composition of the message is agreed upon before hand, but since neither of them know the value of $k$ a priori the message can't be based on that. Before entering the maze, both parties have access to shared randomness or a set of random bits they know and can be used to communicate later (i.e., an adversarial maze generator does not have access to this randomness). (I am not sure if this detail changes the problem.)

We know $k \geq 1$ and the sets $S_A$ and $S_B$ are disjoint.

$A$ can of course base his answer on $S_A$ but can't transmit all of $S_A$. For example I came up with: if $A$ sends the sum of the elements of $S_A$ and the size of $S_A$, then $B$ can always infer if only one element is missing ($k=1$) but will fail otherwise. This takes $O(\log n)$ bits.

But how can we design a protocol to achieve the following:

  $A$ sends a message with $O(\log^3 n)$ bits such that $B$ with probability $1-\frac{1}{n^c}$ can infer (at least) ONE missing object for any $1 \leq k \leq \sqrt n$ (and with remaining probability fails), where $c$ is some number given ahead of time (i.e., it is not under the control of or chosen by $A$ but the constant factor of $O(\log^3 n)$ can depend on it).

To clarify, the goal is to design a message protocol that will achieve the desired result for any values of $n$ and $c$. So the program itself can't pick the value of $c$.


texts: How does prefix summing the count histogram in counting sort result in an array of output indices?

texts:
My implementation of counting sort is based on the description I found here. I've also included my code in this REPL, but here it is:

def counting_sort(input_list, max_int):

  # Make a histogram array for occurences of each integer
  count = [0] * (max_int + 1)
  for i in range(len(input_list)):
    value = input_list[i]
    count[value] += 1

  # count -> [0, 2, 2, 0, 0, 1, 1, 1]

  # Prefix sum the count histogram array
  modified_count = [i for i in count]
  for i in range(1, len(count)):
    modified_count[i] = modified_count[i-1] + modified_count[i]

  # modified_count -> [0, 2, 4, 4, 4, 5, 6, 7]

  # Output elements from input_list according to modified_count
  output = [0] * len(input_list)
  for i in range(len(input_list)):
    output_value = input_list[i]
    output_index = modified_count[output_value] - 1
    output[output_index] = output_value
    modified_count[input_list[i]] -= 1

  print("Output", output)

counting_sort([1,5,7,6,2,1,2], 7)

Most of this algorithm makes sense to me:

The algorithm makes a histogram of occurrences where count[i] is the number of occurrences.
Then we prefix sum this count histogram which gives us modified_count—an array that stores the number of items with a key less than i.
We then use that array to determine the index of the integer in the output array.

The Wikipedia article states, that the modified_count array, which stores the number of items with a key less than i, is the same as an array where each item is the "the first index at which an item with key i should be stored in the output array."

That quote from Wikipedia is what I don't understand.

In a nutshell, my question is: Why is the number of items with a key less than i the same as the first output array index for an item with key i. It seems so clever, but very mystifying (currently).


texts:
I have heard a colleague of mine giving the following statements to a student, but I am not quite sure if he is right. The statements were about Multi Layer Perceptron and the Backpropagation algorithm, he said that:

It would be reasonable to check it up if the data to be input to a MLP should be checked first its degree of data normality. It is the first time I heard that and I am not sure about it. I have seen this article:
https://www.researchgate.net/publication/256980936_Assumptions_of_Multiple_Regression_Correcting_Two_Misconceptions

that talks about multiple regression (and I know that a MLP NN can be used for this case) and it says that:

  In this article, we clarify that multiple regression models estimated using ordinary least squares require the assumption of normally distributed errors in order for trustworthy inferences, at least in small samples, but not the assumption of normally distributed response or predictor variables

So a MLP with BP algorithm does it only work when the input data if it has a normal distribution?

Another point that he mentions is that a MLP NN could not work in n-dimensions, but I am pretty sure that is not a limitation, because I have seen in the Andrew Ng course that he talks about data that is in Rn dimensions, and uses MLP and backpropagation to classify it.
So both limitations could exist? in which cases a MLP could fail, regarding the data input.

Thanks


texts: Context free grammar for $bin(n)bin(n+1)^R$

texts:
It is pretty hard for me to understand, how binary representation of number may be context free. This language $L=\{bin(n)bin(n+1)^R : n \geq 0\}$ is context free.

Here, at 1.b, is a PDA which describes this language, so it is context free. I've tried to construct a context free grammar for this one, but I have no idea when to even start. How can I express a CFG binary representation of a number? I would be very glad for any suggestions.


texts: Arrange in increasing order of asymptotic complexity

texts:
I have the following functions that I need to rank in increasing order of Big-O complexity:
$$(\log n)^3, 10\sqrt n, n\log n, n\sqrt n, n^4 + n^3, (2.1)^n \cdot n^2, 3^n, 2^n \cdot n^3, n! + n, n^n. $$
My current ranking is as follows:
$$(\log n)^3 < 10\sqrt n < n\log n < n\sqrt n < n^4 + n^3 < (2.1)^n \cdot n^2 < 2^n \cdot n^3 < 3^n < n! + n < n^n. $$
Is my ranking of the functions in increasing order of complexity correct?


texts: Amortized analysis - adding operations to a data structure

texts:
One of the finer points of amortized analysis about which I have been able to find relatively little information is the broad question of what happens to the amortized cost of a structure's existing operations if we add a new one. I'll use two popular examples to illustrate my confusion:
In a binary counter which only supports the increment operation, choosing the potential function $\Phi=\#$ of $1$'s in the present configuration gives us constant amortized cost for the operation. In every example I can see in the literature, adding the decrement operation to the counter creates a situation where both it and the increment operation have linear amortized costs. The argument given is that we can toggle $m$ times between values of $2^n$ and $2^n-1$ with a series of alternating decrement and increment operations, giving us a time of $\Theta(mn)$.
In a binomial heap, using the number of binomial trees in the structure as a potential function gives us constant amortized time for insertion. Popping the minimum takes logarithmic time both amortized and in actuality.
Perhaps I'm mistaken, but I see a certain contradiction here. In a binomial heap we could reach a point where we have one large binomial tree with $2^n$ elements and repeatedly perform pop and push operations, which will cost $\Theta(m\log n)$ time. Even if each vertex keeps its children in a linked list which would give the deletions constant time, the insertions will all take logarithmic time.
Having said that, the insertion operations for both structures still function the same way: for any sufficiently large $m$, any series of $m$ insertions to either structure still takes $O(m)$ time - the inclusion of the deletion (decrement in the counter) operation doesn't affect the way the insertion operation works.
So why do we say that adding decrementation to a binary counter increases the amortized cost for incrementation and then ignore the same argument when analyzing binomial heaps?


texts: Bounds on update time in the RMQ problem subject to $O(1)$ query time?

texts:
In the static RMQ problem, one has to answer queries about the minimum in a range of a fixed array. A classic variation allows updates of the form $A_i \leftarrow x $.

My question is : How fast can we update if we must answer queries in $O(1)$?

I can think of a solution which works in $O(\sqrt{n})$ per update :

We can answer queries in $O(1)$ using a sparse table. Since each element is a part of $O(n)$ ranges in the sparse table, we can clearly update a sparse table of an array of size $n$ in $O(n)$. Now, divide into $\sqrt{n}$ blocks. For each block, maintain the prefix and suffix minimums and also a sparse table. Clearly, a block can be updated in $O(\sqrt{n})$. On the upper level, maintain another sparse table which can answer minimum over a range of blocks. Clearly this can also be done in $O(\sqrt{n})$  and the query time is still $O(1)$. The memory used and precomputation done are both $O(n \log{n})$.

Can we do better, say $\text{polylog}(n)$, perhaps using more memory and/or precomputation? Is there a known lower bound?


texts: How can I prove that a cryptography algorithm is a pseudo-random number generator?

texts:
I have read about cryptography prgs.
If I have a generator G(x1,x2...,xn)= x1,x2,...,xn, x1&x2...&xn , how can I prove that it is a prg or prove it is not?

Is there some principles I have to be based on while proving prgs?


texts: Approximation factor preserving reduction

texts:
The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365:

Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving
reduction from $\Pi_1$ to $\Pi_2$ consists of two polynomial-time algorithms, $f$ and
$g$, such that:

for any instance $I_1$ of $\Pi_1$, $I_2 = f(I_1)$ is an instance of $\Pi_2$ such that $OPT_{\Pi_2}(I_2) \leq OPT_{\Pi_1}(I_1)$.
for any solution $t$ of $I_2$ (constructed above), $s = g(I_1, t)$ is a solution of $I_1$ such that: $obj_{\Pi_1}(I_1, s) \leq obj_{\Pi_2}(I_2, t)$.

It is clear that this reduction preserves the approximation factor.
QUESTION: Since any solution of $I_2$ shall have an objective value no less than that the objective value of the corresponding solution of $I_1$, if the solution $t$ to $I_2$ is optimal, that is, $obj_{\Pi_2}(I_2, t) = OPT_{\Pi_2}(I_2)$, doesn't this imply that equality should always be satisfied on the first condition? In other words, $OPT_{\Pi_2}(I_2)$ can never be less than $OPT_{\Pi_1}(I_1)$, or else, some solution of $I_1$ will have an objective value less than its optimal (which yields a contradiction for a minimization problem).
I understand that we are mainly interested in optimization problems that are NP-hard, however, in this reduction, we did not specify that the solution of $I_2$ should not be optimal.
In this book, the author gives several such reductions between different problems, however, none of those reductions were built upon the strict equality of the first condition.


texts: Weaknesses arising from using same key in both channel directions

texts:
I came across the following question:
Which of the following risk may arise, when same key is used to encrypt both directions of a communication channel, that are not present if using different keys in both direction?
The answer to the question was reflection attack. The other options provided were denial of service, eavesdropping and none of the above.
I presume it could be eavesdropping. Eg: When a Diffie-Hellman key exchange is performed, a man-in-the-middle attack (type of eavesdropping attack) could occur.
So is the answer reflection attack or eavesdropping or something else entirely and why ? I tried looking up resources to justify and figure out the right answer but this is what I could conclude with.


texts: Convergence of recursive formula in TextRank

texts:
I am reading a paper about the TextRank algorithm in keyword extraction and they mention the recursive formula:
$$ \displaystyle S(V_{i}) = (1 - d) + d \ast \sum_{j \in In(V_{i})} \frac{1}{|Out(V_{j})|} \; S(V_{j})  $$

where $ In(V_{i}) $ are the vertices that point to $ V_{i} $ and $ Out(V_{i}) $ are the vertices that $ V_{i} $ points to.

The paper claimed that this algorithm will converge for any arbitrarily small positive threshold and any arbitrary initial values by testing with experiments. However, I am attempting to prove it mathematically that this algorithm will always converge regardless of the choice of the threshold as well as the initial values, but haven't succeeded at this point. My approach is to prove that if $ E_{ij} $ is the error at vertex $ i $ at the $ j $ iteration, then the sequence $ E_{i1}, E_{i2}, \dots, E_{in} $ is a decreasing sequence. Intuitively, it means that the error rate approaches $ 0. $

Any hint or suggestion is appreciated.


texts: What is an asymptotically tight upper bound?

texts:
From what I have learned asymptotically tight bound means that it is bound from above and below as in theta notation.
But what does asymptotically tight upper bound mean for Big-O notation?


texts: Does "aimed application" mean something specific?

texts:
I was reading about an uninstall tool that was especially useful for removing "aimed applications."  When I tried to find out what that meant (beyond the obvious, "targeted at a specific group") I found it used quite a bit, but I have been unable to find an actual definition of the term.  Since I'm asking here, I'm obviously interested in the term as used for the programs the uninstall tool can target and not the term from the medical, advertising or any other domains.

If there's a better place to ask about a computer term, please direct me there and accept my apologies for wasting your time.

EDIT:  Here are a few links to pages that use the term without defining it (at least not in any way I recognize as "defining"):

https://techdows.com/2010/08/uses-of-hunter-mode-in-revo-uninstaller.html

https://ieeexplore.ieee.org/document/7367021

https://books.google.com/books?id=vdCeBQAAQBAJ&pg=PA92&lpg=PA92&dq=what+is+an+%22aimed+application%22&source=bl&ots=CYk_PlUnF5&sig=ACfU3U0wLGAjj7P5wFC09Sun310ap3rA5A&hl=en&sa=X&ved=2ahUKEwid9rO9x-vjAhXsYt8KHdNkChg4ChDoATAAegQIBBAB#v=onepage&q=what%20is%20an%20%22aimed%20application%22&f=false

https://forum.latenightsw.com/t/how-to-activate-the-aimed-application-when-displaying-a-cocoa-alert/185


texts: Weakly NP-complete problems and strongly NP-complete problems

texts:
I'm still confused with the terms Weakly NP-complete and strongly NP-complete.
Many people states that weakly NP-complete problems are the problems with time complexity growing as a polynomial in the magnitude of the input, while strongly NP-complete problems are the problems with time complexity growing as a polynomial in the size of the input.
Does this make checking whether a number is prime or not (which is always considered as polynomial-time problem) a weakly NP-complete problem since its time complexity is growing as a polynomial in the magnitude of the input but as an exponential in the size of the input?


texts: Regex NFA construction: Why use Glushkov over Thompson? Pros/Cons

texts:
In what circumstances should we prefer Glushkov's algorithm or Thompson's construction for the building of regular expression NFAs?

I understand the difference between them, and can follow the argument for each approach.

I understand that the result is an NFA in each case, but with a lack of $\epsilon$-transitions in Glushkov's approach, and that this presumably results in a minor[?] match-time implementation-complexity benefit and a reduction in the total number of states for a given expression?

Are these the primary criteria to recommend Glushkov?

It appears that the Glushkov construction process may be more complex than Thompson. Is this the case? Does this argue for Thompson for projects where that is a factor?

Are there other important factors affecting the implementation choice which I am unaware of?


texts: Is there way to prove a problem is in NP without a verifier?

texts:
There is a theorem that states that if A is polynomially reducible to B and B is in P, then A will be in P.

Now, would that hold for NP problems?

Simply, since coming out with verifiers all the time might be a longer/trickier task if there is a actually an easier way to to prove something is in NP.


texts: How to prove polynomial time equivalence?

texts:
Define the problem $W$:

  Input: A multi-set of numbers $S$, and a number $t$.

  Question: What is the smallest subset $s \subseteq S$ so that $\sum_{k \in s} k = t$, if there is one? (If not, return none.)

I am trying to find some polytime equivalent decision problem $D$ and provide a polytime algorithm for the non-decision problem $W$ assuming the existence of a polytime algorithm for $D$.

Here is my attempt at a related decision problem:

  $\mathrm{MIN\text{-}W}$:

  Input: A multi-set of numbers $S$, two numbers $t$ and $k$.

  Question: Is there a subset $s \subseteq S$ so that $\sum_{k \in s} k = t$ and $|s| \leq k$?

Proof of polytime equivalence:

Assume $W \in \mathsf{P}$.

solveMIN-W(S, t, k):
1. S = sort(S)
2. Q = {}
3. for i=1 to k:
4.     Q.add(S_i)
5.     res = solveW(Q, t)
6.     if res != none and res = t: return Yes
7. return No

I'm not sure about this algorithm though. Can anyone help please?


texts:
In a typical read operation from a dram chip, all the banks are equipped with sense amplifiers which select one bit from each bank using column multiplexer.
But how does write operation takes place? How does only one column in a bank is written in a particular row?


texts: Schaefer's dichotomy theorem and reformulating 3-literal clauses

texts: Does Schaefer's dichotomy theorem establish that a general 3-sat clause cannot be transformed into an equivalent set of 2-sat/Hornsat/affine clauses (using auxiliary variables) or just that this would be very unlikely in that it would imply P = NP?  I ask because I know that there are some types of problems involving 3-literal-clauses which can be transformed into equivalent 2-sat/Hornsat clauses.  I'm thinking specifically of 2-or-3 SAT which can be solved by 2-sat/anti-Hornsat clauses or 1-or-3 SAT which can be solved using affine clauses.


texts: Circuit complexity of hardest monotone function

texts:
Show there exists a monotone function $f\colon \{0,1\}^n \mapsto \{0,1\}$, such
that the minimal size of a monotone circuit that computes $f$ is
$\Omega(2^n / n^2)$. Use the fact that the number of monotone
functions is at least $2^{\frac{2^n}{2 \sqrt{n}}}$.

Every monotone $f\colon \{0,1\}^n \to \{0,1\}$ has a minimal size monotone circuit $C_f$ that computes $f$. Since there are at least $2^{\frac{2^n}{2 \sqrt{n}}}$ functions such as $f$, there are at least $2^{\frac{2^n}{2 \sqrt{n}}}$ circuits such as $C_f$.
Assume the minimal size of a monotone circuit that implements a monotone function $f\colon \{0,1\}^n \to \{0,1\}$ is $o(2^n / n^2)$. Fix some $c\in \mathbb{R}^+$. There exists some $N$, such that for every $n>N$ it holds that $\mathrm{Size}(C_f) \leq c\cdot \frac{2^n}{n^2}$.
I am trying to show that the number of possible monotone circuits $C_f$ on $n>N$ inputs - whose size is minimal and bounded by $c\cdot \frac{2^n}{n^2}$ - is less than the number of monotone functions $f$. This would mean the assumption I made leads to a contradiction, and thus the opposite is true.
Can you help me solve this problem?

$f\colon \{0,1\}^n \to \{0,1\}$ is monotone if for every $x,y\in \{0,1\}^n$ such that $x_i \leq y_i $ for all $i$, it holds that $f(x) \leq f(y)$.
A circuit $C(x_1,\ldots,x_n)$ is monotone if it only has AND gates and OR gates.


texts: Is there a name for "yield first result parallel map"?

texts:
Context

In randomized algorithms two schemes of computation are common:

Las Vegas algorithms with random running time
Randomized algorithms that have a probability of success, and have to be executed multiple times before getting the answer

You can also transform the latter in the former with a loop but they really don't have the same properties (like an optimal restart sequence for Las Vegas algorithms), so I want to distinguish the two.
It is also possible to have randomized algorithms that can fail AND that take a random amount of time.

Parallelization with map

When parallelizing, it is common to use a map primitive: just execute those algorithms in parallel.

However, while waiting the answers from each of the nodes at each "batch", one loses tremendous amounts of time, for example if one instance of the algorithm takes much more time than the others: most processes will be idle. Of course, it is possible to group batches to avoid this situation, but then one will have to wait for the end of the batch which will take more time.

"Yield first result parallel map"

The good solution would to be able to return the result in the parent node immediately when one node finds it, hence the name "yield first result parallel map". Then there should be a way to either stop directly the children (I don't know any clean way) or be able to use the free nodes while the busy ones finish their now useless computation. Maybe one should also be able to get those calculations back in a queue if they have a result.

Another way to express it would be "getting the results of a parallel map in an asynchronous queue".

Is this concept known? Does it have another name? Is it implemented somewhere (I implemented it in MPI but was wondering whether there are other implementations)?


texts: In Breadth-first search and depth-first search what is the purpose of visited flag

texts:
In Breadth-first search and depth-first search, in this source code https://gist.github.com/gennad/791932

public void bfs()
    {
        // BFS uses Queue data structure
        Queue queue = new LinkedList();
        queue.add(this.rootNode);
        printNode(this.rootNode);
        rootNode.visited = true;
        while(!queue.isEmpty()) {
            Node node = (Node)queue.remove();
            Node child=null;
            while((child=getUnvisitedChildNode(node))!=null) {
                child.visited=true;
                printNode(child);
                queue.add(child);
            }
        }
        // Clear visited property of nodes
        clearNodes();
    }

    public void dfs() {
        // DFS uses Stack data structure
        Stack stack = new Stack();
        stack.push(this.rootNode);
        rootNode.visited=true;
        printNode(rootNode);
        while(!stack.isEmpty()) {
            Node node = (Node)s.peek();
            Node child = getUnvisitedChildNode(n);
            if(child != null) {
                child.visited = true;
                printNode(child);
                s.push(child);
            }
            else {
                s.pop();
            }
        }
        // Clear visited property of nodes
        clearNodes();
    }

what is the purpose of visited flag? as I can see it is not used especially if we will use Queue and\or Stack


texts:
It can be shown that every graph G has at most $\binom{n}{2}$ min-cuts.
It follows from Karger’s algorithm Analysis.

Is there a different combinatorial proof of this fact? Was this known before Karger’s paper?


texts: What is the difference between a Top type and a Unit type

texts:
Wikipedia defines a Top type: (edited for readability)

  The Top type [...] is the universal supertype, as all other types in any given type system are subtypes of Top

However, the article goes on to say:

  In C++: The pointer to void type can accept any non-function pointer, even though the void type itself is not the universal type but the unit type.

I don't understand this. In particular, given these two functions:

void foo(T1, T2, T3);
SomeType bar(T1, T2, T3);

I'd expect bar to be accepted wherever foo is accepted (in function pointers, as virtual methods, etc); which makes me think void is being treated as a supertype of SomeType.

Leaving C++ aside, I'd expect the same semantics from any language: any logic that expects a void could logically accept any other type.

So, given its properties, why is void usually called a Unit type, and how is it different from a Top type?


texts: how can i proof $3^n$ has a greater growth than $n2^n$?

texts: i want to prove that $3^n$ has a greater growth than $n2^n$ or $3^n = O(n2^n)$. but how can i do it mathematically? by induction or contradiction or other ways of proof.


texts: Is membership of x in an infinite set decidable?

texts:
In order to prove a certain function to be partially computable, I need to show an $\mathbb S$-program that computes it. I could really use the predicate $X \in B$ in my program to draw my conclusion. To give you the idea of what I am dealing with here it is one of my problems:

Give an infinite set $B$ such that $\Phi(x,x)\uparrow$ for all $b \in
B$ and such that $$H(x) = \begin{cases}1 \text{ if }
\Phi(x,x)\downarrow \\ 0 \text{ if } x \in B \\ \uparrow \text{
otherwise}\end{cases}$$ show that $H(x)$ is partially computable.

I am wondering if membership for infinite set is decidable and therefore can be used to write $\text{IF } X \in B$ such program. Am I allowed?

Edit: the notation $\Phi(x,x)\uparrow$ means the function is undefined.


texts: Minimum pumping length of regular language

texts:
I know the method to the find the minimum pumping length of regular language by constructing minimal DFA and finding the number of states but I am not able to quite understand why is it working.

For example, $L = (10)^*$.
Here minimum pumping length is 1 by constructing DFA.
But by pumping lemma, how can there be a string of length 1 belonging to $L$? As pumping lemma says the string $S$ should be such that $|S| \le p$ and $S$ should belong to $L$, where $p$ is the pumping length, and here there is no string of length 1 belonging to $L$.


texts: Data structure to query intersection of a line and a set of line segments

texts:
We want to pre-process a set $S$ of $n$ line segments into a data structure, such that we can answer some queries:
Given a query line $l$, report how many line segments in $S$ does it intersect.

It is required that the query should be done in $O(\log{n})$ time. The data structure itself should take up to $O(n^{2})$ storage and be built in $O(n^{2}\log{n})$ time. It is suggested that it should be done in dual plane.

I understand that the question may require me to look for the number of double wedge that the a query point is in, but I can't think of any efficient data structure to report such information. Any suggestions?

This question is basically a homework question from the textbook Computational Geometry by de Berg et al (Question 8.15). I would like to apologize that this question may not be exciting to you.

Edit:
Yes it is in $\mathbb{R}^{2}$. By query point I mean the query line dualised into a point on dual plane.


texts: How does one guarantee that the commutative, associative and distributive properties hold for a type?

texts:
While most main stream programming languages allow for user defined types that can have the following properties:

associative
commutative
distributive

the only way I know of that this can be shown to be correct is to use models to prove it correct for each user defined type.

As an example the language F* (FStar) includes the model rules in the programming language. Here is an example rule for association for one type:

assume ConcatAssocR: forall a b c.{:pattern (Concat (Concat a b) c)}
  Concat (Concat a b) c = Concat a (Concat b c)

Note: I don't use F* but am considering learning it.

Since most programming is done without using models, to prove the program correct are there other ways that proving these rules hold for user defined type can be done for a program?

Further expanding the idea, are there any attacks that exploit the lack of proving these properties?
(I know this is a security question, but some of those people hang out here.)


texts: How is the difficulty of any problem (not just decition problems) classified?

texts:
I have been studying Integer Programming and I find out that some optimization problems are referred to as P or NP-Hard, however, as I started to read about it, it turns out that those classes are just for decision problem. Thus:

What does it mean that an optimization problem ($\max\{f(c)\mid x\in X\}$) is NP or NP-Hard if they are not (necessarily) decision problems?
If an optimization problem ($\max\{f(c)\mid x\in X\}$) is not a decision problem, then, how is its difficulty classified?


texts:
I'm trying to teach myself about quantum computing, and I have a decent-ish understanding of linear algebra.

I got through the NOT gate, which wasn't too bad, but then I got to the Hadamard gate. And I got stuck. Mainly because while I "understand" the manipulations, I don't understand what they really do or why you'd want to do them, if that makes sense.

For example, when the Hadamard gate takes in $|0\rangle$ it gives $\frac{|0\rangle + |1\rangle}{\sqrt{2}}$. What does this mean? For the NOT gate, it takes in $|0\rangle$ and gives $|1\rangle$. Nothing unclear about that; it gives the "opposite" of the bit (for the superposition, it takes in $\alpha|0\rangle+\beta|1\rangle$ and gives $\beta|0\rangle + \alpha|1\rangle$) and I understand why that is useful; for the same reasons (basically) that it is useful in a classical computer. But what (for example) is the Hadamard gate doing geometrically to a vector $\begin{bmatrix}\alpha \\ \beta \end{bmatrix}$? And why is this useful?


texts: Graphs with bounded degree and small max independent set

texts:
Graphs with degree $\Delta$ have a maximum independent set of size $\alpha \geqslant \frac{n}{\Delta}$ where $n$ is the number of vertices.
But, are there graphs such that $\alpha \approx \frac{n}{\Delta}$, or even $\alpha = c \frac{n}{\Delta}$ for some constant $c \leqslant 1$?


texts: Proof that the length of the largest ascending subsequence is the number of decreasing subsequences

texts:
Given a sequence of numbers, I have to prove that the number of decreasing subsequences (non-strictly), so that every number is included in one subsequence and the number of subsequences is minimum is actually the length of one of the longest increasing subsequences. I need to this because I have to prove the greedy algorithm for finding all the decreasing subsequences having as few subsequences as possible. I have no idea of where to start, any help is much appreciated.

Edit:
The big, greedy problem sounds like this: decompose the sequence in a minimum number of decreasing subsequences (non-strictly). Those are the subsequences I am talking about.

Thank you.


texts: Proving the equivalence of two definitions of NFA acceptance

texts:
Recall that an NFA $N = (Q,\Sigma,\delta,S,F)$ accepts $w=w_1w_2\ldots w_n$, where $w_i \in \Sigma$, if one of the following holds:

  (a) $\hat\delta(S,w) \cap F \neq \emptyset$, where $\hat\delta\colon P(Q) \times \Sigma^* \to P(Q)$ is given by
  $$
\hat\delta(Q',w) =
\begin{cases}
Q' & w = \epsilon \\
\bigcup_{q \in \hat\delta(q',w_1\ldots w_{n-1})} \delta(q,w_n) & |w| = n > 0
\end{cases}
$$

  (b) $\exists r_0,\ldots,r_n$, where $r_i \in Q$, such that:

  $r_0 = q_0$
  $r_n \in F$
  $r_{i+1} \in \delta(r_i,w_{i+1})$

  Show that (a) $\leftrightarrow$ (b)

I think I have proven from (b) to (a) but I'm not sure, and I seem to have no idea where to start the other way around. This is part of the first exercise in the computational models course I'm taking and I would really appreciate the help.


texts:
Confused about a question regarding flow networks.

Question is: Given the network below, what is the current value of flow in this network?

Does the current flow of a network refer to the maximum flow or something else?


texts: How to calculate the minimum number of groups, by grouping groups with capacity together?

texts:
I need to group cars (and their passengers) with other cars, and I don't know how to approach this problem.

If I have, for example, 3 cars. Car A with 7 seats and 2 passengers (3/7 because of the driver). Car B, 2/2. Car C, 1/3.
The most wasteful clustering would be [A, B, C]. But car C has room to pick up the driver and passenger of B, but no room for A, leaving us with [A, C]. Obviously, the best cluster would be one with only A because it has room to pick-up the other 2 cars. Now, this is a simple and small example, but how can I search for the minimum number of cars in samples with an arbitrary number of cars and passengers?

I tried to approach this problem in 3 different ways, but all fell short.

I thought about a maximum flow problem (image 1). But the maximum flow problem deals with capacities in edges of a graph. This specific problem has limitations on capacities of nodes/cars (not in its edges).

Maybe there's an adaptation of this method that I can use, but I couldn't think of any that would give me the list of groups that minimize the number of cars.

I also thought about the longest path problem (image 2). Every edge of my graph would be weighted by the number of people (driver + passenger) that would be picked-up if traversing to that node. And I could adapt the algorithm to decreased the capacity of the origin node accordingly with each node visited and stop that iteration if the max capacity was reached.

But to my understanding, I need to calculate the longest simple path (and not repeat any nodes) and that requires an acyclic graph. Given the context of my problem, most of the times there would be no way to turn my graph acyclic given that all the nodes would be strongly connected.

Lastly, I considered creating a list of trees (image 3). Where each root would be the origin car, and each child node would be a car that the root could pick-up. For each level of depth the available seats of the root would decrease until no more combinations existed. Then I would group trees' levels together and try to achieve the best combination and minimum of cars.

But at what level do I start. Does starting at the tree with the greatest depth and then grouping with other trees guarantee the minimum number of cars? Or is there a counterexample where grouping trees in their respective mid levels achieve better clustering? Do I just need to try every possible combination? That seems like an exhausting comparison and awfully inefficient.

I may be overlooking some characteristics of my problem, or maybe I'm just not comprehending the solutions I described. Is there a known solution to my problem, or maybe an adaptation I could implement? Any help or guidance is appreciated.

Thank you.

Edit:

u/gnasher729 mentioned the Bin packing problem in the answers which is indeed very similar to my problem.

Bin packing is calculated with bins of the same size. Given the context of my problem, my bins (cars) have different capacities.

With u/gnasher729 suggestions, the adaptation I came up with was:

Sort cars by remaining capacity first. Items weights are the size of the different groups of passengers.
Run the bin packing algorithm with bins of capacity equal to that of the car with more available seats.
Of the bin allocations produced by the algorithm, choose the bin with more items in it (meaning more groups of passengers were able to fit inside).
Remove the grouped cars (the bin + the items) from the sorted list and from the unplaced items.
Re-run the bin packing algorithm with the next emptiest car and with the remaining passenger groups.
Repeat until no more packing is possible.

It seems like it'll be an intense computation when given a large enough number of cars. If I have 20 cars with unknown passengers and unknown seats, and if I group 2/3 of those cars together with each iteration of the bin packing algorithm, then it'll be costly.

Is my adaptation wrong? Can i optimize it further?


texts: Efficient computation of Kronecker product

texts:
Given matrices $A \in \mathbb{C}^{n_1,m_1}, B \in \mathbb{C}^{n_2,m_2}$ a naive way to computer the Kronecker product would be as such:

$M = \operatorname{zeros}(n_1n_2,m_1m_2)$ (initialize an empty array)
    For $p = 1,2,\ldots n_1n_2:$
        For $q = 1,2,\ldots m_1m_2:$
            $M_{p,q} = A_{{\lfloor {{p}{n_1}} \rfloor},{\lfloor {{q}{m_1}} \rfloor}} B_{p \bmod n_2,\  q\bmod m_2}$

Which will have running time $O(n_1n_2m_1m_2)$.

I was wondering if there is a more efficient way to computer $M$?

Thanks!


texts: Find close pairs of real points in a set

texts:
Given an array $S$ with $n$ real numbers. Design a linear time algorithm that finds $x,y \in S$ such that that $|x-y| \leq \frac{max(S)-min(S)}{n-1}$.
I was thinking that it is similar to the closest point problem but that can only be solved in O(nlogn).
Please help


texts:
Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting the maze?  I'm looking for a single sequence of commands that will work no matter where in the maze you start from.

Assume that if our partner is given the "move right" command when there's a wall on the right, he will simply stay where he is.

In other words, we're given a maze, and we must choose a sequence of commands.  Then, our partner will be placed somewhere in the maze and will follow the sequence of commands we've chosen in advance.  We want this sequence to ensure our partner will escape, no matter where our partner was initially placed.  Note that the allowable commands do not have any conditional statements, so they cannot follow a different sequence depending on your partner is.

Is there a polynomial-time algorithm to construct such a sequence, given a description of the maze?

Yuval Filmus mentions this is a special case of a synchronizing word problem, and might be related to universal traversal sequences.  I also found a paper that seems relevant:

The Simultaneous Maze Solving Problem.  Stefan Funke, André Nusser, Sabine Storandt.  AAAI 2017.

Unfortunately for general graphs this appears to be a unsolved problem, but I'm wondering if there might be a good algorithm for this specific case.   I came up with a candidate approach: Label every position with the number of minimum steps it requires to exit, and keep track of every agent in the maze. It might be possible to do a A* search this way.


texts: How memory controller reads from RAM with O(1) time complexity?

texts: I am trying to understand how a RAM memory controller gets data with instant access while reading through the memory. Let's say initially, ram gets the data at address 0 and then to get the data at some random location like 1234, does it not have to loop through the first 1233 addresses before reaching 1234? Please explain. Thank you!


texts: Minimal complexity for pairing two comparable sets with comparability restrictions

texts:
A project at university (whose deadline has passed by now) presented the following problem:

  Consider two finite sequences of (not necessarily distinct) real
  numbers $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$ such that the $b_k$'s
  are a permutation of the $a_k$'s. The aim is to create an algorithm
  which returns a permutation which maps the sequence $(a_k)$ onto
  $(b_k)$. In order to find such permutation it is necessary to compare
  some numbers during the algorithm. The restriction is that one cannot
  compare any $a_x$ with an $a_y$ or a $b_x$ with a $b_y$: all that is
  allowed is to compare a number of the first sequence with one of the
  second sequence.

I am wondering what would be the minimal (worst-case) complexity of the number of comparisons. It's not hard to get $O(n^2)$: for every $a_x$, search brute-force for a corresponding $b_y$, which costs $O(n)$ comparisons giving a total of $O(n^2)$.
A bit smarter would be to adapt the familiar QuickSort algorithm, in the recursions step taking as a pivot a couple $(a_x,b_y=a_x)$ (which can be found in $O(n)$ comparisons) and partitioning both sequences using this 'pivot'. This gives $\Theta(n\log n)$ comparisons in average, but still $\Theta(n^2)$ worst-case (as usual with QuickSort).

It's not hard to see that $\Omega(n\log n)$ is a minimum: represent a given algorithm as a binary decision tree with a comparison at each node. Since the total number of leaves can reach $\Theta(n!)$ (the number of permutations in case all the $a_k$ are different) the height of the tree is at least $\Omega(\log_2(n!))=\Omega(n\log n)$.

It seems likely that a $O(n\log n)$ algorithm exist, but I have not been able to find one. I have tried adapting MergeSort, but a problem during the merging arises giving a worst-case of $\Theta(n^2)$ nonetheless.

Is this a known problem? Does a $O(n\log n)$ algorithm exist? Do you have suggestions for other known sorting algorithms which might be adapted without increasing their complexity?


texts: I am trying to generate a $n$-bit gray code where I can specify two strings $s$ and $t$ that must be consecutive in that gray code. I know that there are ways to generate specific codes (such has the Binary Reflected Gray Code and the Recursive Partition Gray Code), but I need to be able to construct one given any two strings as described above. Is there a way to do this? Or a result that guarantees that this is possible? I am almost certain it is, but haven't been able to find anything.


texts: I'm noodling around with making a hardware SAT solver on an FPGA, and I'm wondering if there are any interesting SAT problems smaller than, say, 50 variables both to stay within the limits of the FPGA board (namely the number of LEDs) and so I can brute-force if needed to get all possible solutions.  I looked into factorizing small integers, but it seems that even relatively small numbers quickly get in to the hundreds of variables.  Is there anything else I can look at besides random-SAT?


texts: Finding subset of integer summing up above threshold

texts:
Given an array $|A|=n$ of integers, and $m,k \in \mathbb{N}$, I want to find $m$ elements $a_{i_1},...,a_{i_m}$ of $A$ such that $\sum a_{ij} \geq k$ (repitions allowd), or determine that no such solution exists.

Clearly, a trivial solution is to take the maximal element $a_{max} = \max_{i} A_i$, multiply it by $m$, and if $ma_{max} \geq k$ return it.

Is there a polynomial time algorithm $X$ such that: $X$ is a randomized algorithm, and at every run, it outputs such $m$ elements where every $m$ elements have a positive probability to be generated by $X$? (for example, the above method does not satisfy it because on a given $A,m,k$ it will output one answer with probability 1, and many possible other solutions with probability 0). Is there an algorithm where every $m$ elements have an equal probability to be generated (i.e. the algorithm is uniform)?


texts: What is a dominator node and a dominator tree?

texts:
I tried reading the wikipedia about Dominator (graph theory), which gives the following definition of a dominator node:

a node d dominates a node n if every path from the entry node to n
must go through d.

I need to understand the concept of a dominator node but I do not need to go deep into graphs, so I'm trying to make sense of these definitions. I'm trying to look in the images on the article:
This is a graph:

This should be a dominator tree for the graph above:

Based on the definition above, I think
node 2 dominates node 3 because every path from 3 must go through 2. Why? To go from 3 to itself I must pass to 2. That's why 2 goes to 3 in the dominator tree.
Am I thinking right?
Can I know also why this is useful in compilers?


texts: Given a Turing Machine M and a string $x$ how do we tell whether a the Turing Machine M loops on the string $x$

texts:
Let us say there is a Turing Machine $M$ and a string $x$.  So now I want to know if $M$ accepts or rejects the string or loops on it. So, I feed the string to $M$. So, if $M$ is accept or reject the string it would halt after a finite time and I would get my answer.  But how do I know if the machine loops on the string or not.

One possible way is to see if a configuration repeats itself. However, the machine has no way of knowing  if the configuration has occurred before because it cannot store them . So, we would never get an answer. So, how will I be able to tell whether or not $x$ is accpted or rejected or looped upon by $M$.


texts: Describing the Bool-And monoid in terms of categories

texts:
Normally I put the question before the context, but in this case I want to admit
the possibility that the context and my understanding nullify the question.
Plus it helps me think through my question.

I recently started reading Category Theory for Programmers (Bartosz
Milewski), and this is my
understanding of categories: they are "algebraic structures" which consist of
objects and arrows/morphisms between those objects. The morphisms have to obey
the laws of associativity, so

$$ a \rightarrow ( b \rightarrow c ) = ( a \rightarrow b ) \rightarrow c $$

And there must be an identity morphism for each object.

Now, Milewski goes on to explain that monoids (which I'm pretty comfortable with
in the set-theoretic sense) are also viewable as categories. This is the part I
am having trouble with. One of the exercises in the book is to consider the
Boolean-and monoid (booleans with the and operator) as a category:

  Represent the Bool monoid with the AND operator as a category: List the
  morphisms and their rules of composition.

I want to give some examples, which I'll do in a SML (though I'll borrow Haskell names).

The monoid could be described set-theoretically with the following signature:

signature MONOID = sig
  type m
  val mempty : m
  val mappend : m -> m -> m
end

Further, the monoid for booleans with the and operator would be given as

structure BoolAnd : MONOID = struct
  type m = bool
  val mempty = true
  fun mappend x y = x andalso y
end

So, here is my understanding of this monoid as a category and its morphisms: is
it correct?

The objects in the category are booleans (true and false) and functions from
booleans to booleans
BoolAnd.mappend is a morphism from the former to the latter
mappend true is an identity morphism for the function objects in the
category (I say "an" because isn't the actual identity function fun id x = x
also an identity morphism for the functions, thanks to polymorphic types? Or
does that not count in category-land? I know that mappend true is equivalent
to the identity function under composition of functions with type bool -> bool.)
the identity morphism for boolean objects appears to be just fun id (b:bool) = b
the given identity morphisms should be associative:

(* example, not proof *)
- open BoolAnd;
- (id o (mappend true)) o not;
val it = fn : bool -> bool
- it false;
val it = true
- id o ((mappend true) o not);
val it = fn : bool -> bool
- it false;
val it = true

The rules of composition seem to be that mappend true is the identity, while
mappend false is a "sink" of sorts, causing the resulting function to always
return false. But id and mappend don't directly compose, because the types
do not align (when id is specialized to booleans, as in the bullets above).

Am I missing something? Is something wrong? Did I give too much detail (there
seems to be an emphasis on avoiding digging in to the objects too much)?

I ask this both to confirm my understanding so that I have a good foundation for
the remainder of the book and also because it took me a long time to identify
the objects and morphisms at work; some of them I am still shaky about.


texts: Cartesian product of regular expressions?

texts:
My textbook has a problem to find the regular expression that describes the set of all strings of 0's and 1's whose number of 0's is divisible by 5 and whose number of 1's is even.

I can write a regular expression for each condition

a. $0^*(10^*1)^*$

b. $1^*(01^*01^*01^*01^*01^*)^*$

I am having trouble understanding how to combine these two regular expressions. If they were DFAs, I could combine them by taking their cartesian product. Is is possible to take the cartesian product of two regular expressions (without translating each to a DFA first)?


texts: Is there a way to connect a deep language model output to input?

texts: In models like GPT-2, TXL and Grover, is there a good way to know which input weights (tokens) resulted in each token of the output?


texts: In a DBMS what are the implementation details that make set operations faster than cursors?

texts:
What are the low level implementation details that make set based operations exponentially faster than iterative processes, like cursors?

At a memory level how does a set operation "touch" the data less than a cursor?


texts: Finding one of 2/3 of all array elements in constant expected time

texts:
How do I go about designing a constant time algorithm which satisfies the following I/O requirements:

Input: an array $A$ of length $3n$, containing $2n$ values of the symbol $X$ and $n$ of the symbol $Y$
Output: a number $i$, such that $A[i]=X$

It is clear that the naive linear scan approach is $O(n)$. Is there any good algorithm, potentially randomized, that has a constant number of expected operations $O(1)$?


texts: Number of double wedges containing a point

texts:
We have a set of $n$ double wedges on a plane. (By double wedge, I mean two lines intersecting at a point, with opposite sides of the point considered as "inside" the double wedge.) Now these $n$ double wedges can intersect each other.
Our query is as follows: given a point, we want to find how many double wedges it's contained in. We want to be able to make this query in $O(\log n)$ time, using a data structure that can be constructed (preprocessed) in $O(n^2\log n)$ time and $O(n^2)$ space.
This exercise is from the de Berg's computational geometry book in the chapter about arrangement of lines, so I was thinking we can do some kind of incremental construction by adding the double wedges one by one, but I can't seem to think of the data structure.


texts: Explaining TM notation in Lewis/Papadimitriou

texts:
I was working on some questions in the book "Elements Of The Theory Of Computation", by Lewis and Papadimitriou, and I need help with one question - question 4.1.8 (chapter 4):

  Give the full details of the turing machines illustrated:

  >LL.

I managed to solve everything but this, and that is because I don't know what the dot is used for. Couldn't find any explanation in the book.
There are two more machines in this question (without dots), but I solved them.


texts: Scheduling jobs online on 3 identical machines - a lower bound of 5/3

texts:
Consider the Online Scheduling Problem with $3$ identical machines. Jobs, with arbitrary size arrive online one after another and need to be scheduled immediately on one of the $3$ machines without ever moving them again.
How can I show, that there can't be any deterministic Online-Algorithm which achieves a competitive ratio of $c<\frac{5}{3}$.
This should be solved by just giving some instance $\sigma$ and arguing that no det. algorithm can do better.
Same can easily be done for $2$ machines and $c<\frac{3}{2}$. Sadly I can't find any solution to this (more or less) textbook question.


texts: Is s-grammar powerful enough to generate all possible DCFL?

texts:
In s-grammar all productions are in form of A →  , A∈V , a∈T , ∈V*

  "... and any pair (A, a) occurs at most once in P." [P. Linz, 6th ed. , p. 144]

s-grammar is Unambiguous and i think (not sure) we can describe all Unambiguous-CFL by s-grammar. I want to know can s-grammar describe all possible DCFL or not ? according to this sentence, I think we can't do it but i'm not sure about that:

  Unfortunately, not all features of a typical programming language can be expressed by an s-grammar. [P. Linz, 6th ed. , p. 152]

but all languages which described by an s-grammar is Deterministic.

I say this, because we can made 2-state DPDA for any simple-grammar with this definition:

R ≝ Production Rules of CFG
(x,y,"LBL") is a labeled-edge between x and y with “LBL” as a label
∀r∊R: r= (A,aⱰ) ( A∊V ⋀ a∊T ∧ Ɒ∊V*) add (q,q,"a,A/Ɒ") to E
Add (q,q,"ε,z/Sz′") to E
Add (q,f,"ε,z′/z′") to E

if there is any DCFL that we can not provide an s-grammar for it , show me that please and correct me if i'm wrong.

Thanks.


texts: How to determine the polynomial runtime of an NP reduction?

texts: To show that a NP problem is NP-complete, we also have to show that $L \leq_{p} L'$  , where $L$ is proven NP-complete and you have to prove $L'$ also is. The thing I am confused is how in all NP-complete problems in CLRS they just state the reduction algorithm for $L$ to convert to $L'$ is polynomial. How can one prove it's polynomial time, provided an example such a clique or ham cycle kind of problem?


texts: Are the permutation or weakening lemmas needed for term substitution?

texts:
In TAPL book, page 453, Pierce discusses the following lemma:

  $\Gamma , x:S , \Delta \vdash t:T \land \Gamma \vdash s:S \implies \Gamma, \Delta \vdash [x \mapsto s]t:T$

He claims that when $t$ is a variable, we need to use the permutation lemma:

  $\Gamma \vdash t:T \implies \Delta \vdash t:T$ where $\Delta$ is a permutation of an extension of $\Gamma$.

I don't think this should be the case since in this context the (inductive) type rule for variables says:

  $x:T \in \Gamma \implies \Gamma \vdash x:T$

So if I try to prove the original lemma by induction on the typing derivation, I end up with the following subgoals:

$y \neq x \implies \Gamma,x:S,\Delta \vdash y:T  \land \Gamma \vdash s:S\implies \Gamma,\Delta \vdash y:T$

$y = x \implies \Gamma,x:S,\Delta \vdash x:T \land \Gamma \vdash s:S \implies \Gamma,\Delta \vdash s:T$

Here weakening is not applicable since the conclusion context is smaller than the premise's context. Also permutation is not applicable.

I strongly think this is a typo in the solutions and it should say $\lambda$-case...


texts:
All I could find is an example of sparse language.

I understand that I need to design a language whose all strings generation should not be bounded by a polynomial function, but I feel all the languages string generation is bound to at least one polynomial, so I am unable to design a language L whose strings are not bounded to a polynomial function.


texts: Partition points on a 2d plane with arbitrary line segment

texts:
Let's say I have a 11x11 grid with a few points (around 8) marked in the grid. One of the points is in the center cell. Call it point P.

I choose a point other than P and connect it with a line segment to P. Call that point C1

I choose another point that is not C1 and connect it with a line segment to P. Call that point C2.

Now, if we extend the line segments out from P to the edges of the grid, then the grid will be split into two regions A and B.

How can I determine which of the remaining points are in A and B efficiently?


texts:
How do people measure performance overhead? Whenever someone is bragging about how their program or application performs better than another, they talk about particular measurements, eg time, performance etc.

Whilst I understand how time to perform a task can be calculated, I cannot understand how performance is measured, and I can't find out thought Google.

Are there multiple ways? Are they all accepted or do people have issues with certain methods?


texts: CLRS Question 8-6 Lower bound on merging sorted lists

texts:
I'm doing the CLRS Problems and there's a part I'm having trouble following.
The question is:
Part a) Given 2n numbers, compute the number of possible ways to divide them into two sorted lists, each with n numbers.
Part b) Using a decision tree and your answer to part (a), show that any algorithm that correctly merges two sorted lists must perform 2n−o(n) comparisons.
Part a) makes senses to me.
The first line to the solutions of part b) states any decision tree to merge two sorted lists must have at least $2n$ choose $n$ leaf nodes.
I don't follow why this is. In particular, what is each branch comparing to get to this result? And what does each leaf node represent?


texts: What is the origin of λ for empty string?

texts:
I usually use the symbol $\varepsilon$ for empty string (empty word or null string). But I know some people use $\lambda$ instead of $\varepsilon$.

I think $\varepsilon$ is derived from the word "Empty". However I don't know what's the origin of $\lambda$.

In automata theory, there is the epsilon transition of automata, and it's also said to be the lambda transition. For example, JFLAP software uses $\lambda$ for the label of epsilon transitions by default.

I googled on the origin and searched cs.stackexchange, but I couldn't find. Does anyone know a reference that describes this?


texts:
The problem is taken out of Theory of Computational Complexity:

Now, I think I've successfully proven that $ALL_{NFA} = \{(A) :  A$ is an NFA and $ L(A) = \Sigma^*\} \leq_p MIN_{NFA}$. Which implies that $MIN_{NFA}$ is PSPACE hard, as the latter is itself.

However I'm stuck proving this problem is in PSPACE - I've thought of defining a nondeterministic Turing Machine, that takes an NFA and a natural number $n$ as input, and on each branch of the computation creates a NFA with number of states less than or equal to $n$. This machine will go on to compare the resulting NFA (in each branch) to the given one (this problem is itself in PSPACE, but I've yet to prove it myself).

However it seems to me the above idea may use more than poly. time, as we may have to keep track of the transition function of each NFA; whose image is in the power set of its states.

Any assistance?


texts: How to convert this DFA with multiple final states to a regular expression? (State elimination method)

texts:
So I have a DFA which I would like to convert to a regular expression. As you can see it has multiple accepting states and the start state has incoming input 'a' from q2 and 'b' from q4.

I want to convert this into a regular expression using State elimination, and I know that I need to first create a new state call it 's' which replaces q0 as the start state, and then create another new state (call it 'f') which will be the new final state, and make q1, q2, q3, and q4 non-accepting states, and make epsilon transitions from the former accepting states to the new final state.

My question is, when I eliminate say q1, I don't know what the regular expression will be as a result. Now since q1 has 2 outgoing transitions 'a' to a2 and epsilon to f, what would be that regular expression? I know that for q2 it would be a(ba)a(ba) ... then q0 to f will be a(ba)*.. so far it doesn't make sense to me how this will end up becoming the correct regular expression. Am I on the right track?


texts: If A many-one reduces to B, does the complement of A many-one reduce to the complement of B? My gut says no but I am having a hard time finding a counterexample.


texts: Auction website with Paxos consensus algorithm

texts:
As a project, I'm trying to construct a P2P auction web application with paxos in a high latency environment. The idea is that each user visiting the website will keep a small log file with the interested item and current price/bid. Each submitted bid will use a client-sided paxos algorithm to contact nodes all nodes to reach a consensus of the bid value. The idea is quite simple, user wishing to buy/sell an item, either add a new entry to the log or update an existing one. However, since its an auction, time is an issue, especially with high-lantecy.

I have a couple of problems with this idea, which I hope it is achievable. How would the final bid be finalized? E.g. how would ALL the user know that bid has ended and this user is the winner? Client-side validation can be circumvented with JavaScript and timestamping can be forged. What other options do I have?


texts: Complexity of closest set of points in plane problem

texts:
Given a set of points on a plane find the set of $n$ points that are closest to the origin.  (Points are pairs of integers.)

  Input: list of points.
  Initialize a priority queue $Q$, where priority is measured according to the distance from origin (larger distance is higher priority).
  For each point $p$:

  Add $p$ to $Q$.
  If $Q$ contains $n+1$ points, remove the point with highest priority.

  Return $Q$.

The priority queue is implemented using a heap.

I'm thinking the runtime is $O(n + k \log n)$, and space is $O(n + m)$.  Where $n$ is the number of points examined, $m$ is the number of points being returned and $k$ is $\max(0, n - m)$.  Space is both the priority queue and the output.

My understanding is that a heap can be constructed in $O(n)$ hence the $O(n)$ in the runtime complexity.  I find it hard to reason why heap construction, which has an upper bound $O(n \log n)$ can be reduced to $O(n)$, but $k$ deletions should be $O(k \log n)$.

I might be overthinking this, but thought I would ask.


texts: What makes a program flow different from a program path?

texts: Program flow and path are discriminated in the literature of program analysis. However, I have failed to find a formal definition of program flow and path. Can anyone please point me to some authentic literature, e.g. research paper or popular books? Also, an example will be highly appreciated.


texts: What's the most time efficient way to find the number of nodes reachable from each root and no other root?

texts:
Suppose there are n nodes.
These nodes are connected by m unique directed edges. Sets of these edges may form cycles.
Each node has an associated quantity.
r of these nodes are selected as root nodes.

A node a can be said to reach node b if

a is b or
there exists a directed path from a to b.

The goal: For each root node, find the sum of the quantities of all nodes which it can reach and no other root can reach.

This includes the root itself. For example, if root 2 can reach root 1, then root 1's associated quantity will be counted to neither root 1 nor root 2's sum. On the other hand, if no root other than root 1 can reach root 1, then root 1's associated quantity will be counted toward root 1's sum.

I'm trying to puzzle out how to do this with the minimum number of calculations, but I think I need to brush up on my graph theory. This problem is quite a lot easier on a tree, but I've found dealing with cycles makes things much more complicated. I'm having a tough time finding a solution which doesn't incessantly re-traverse the graph.


texts: Describing time complexity when internally using a function of unknown complexity

texts:
Assume that I have some functions $f$ and $g$, both implemented perfectly, where

$$
f(x, g(z)) = \sum_{k=0}^{k=\lfloor{x}\rfloor}g(k)\quad (x > 1)\,.
$$

Function $g$ is of unknown definition. I would like to express the time complexity of $f$ in big-O notation. My initial thought was to do something similar to:

$$
O(\sum_{k=0}^{k=\lfloor{x}\rfloor}T_g(k))\,.
$$

Assume $T_g$ represents the time function of function g. However, this representation feels inadequate and irreducible for asymptotic time complexity; there should be a better way to express $T_f$.

How do I describe, in big-O notation, the time complexity of $f$?


texts: clarification about Algorithm of page replacement LRU with reference bits

texts:
Studying LRU approximation Algorithms I think to have not understand how it works, for example:

consider a process with 3 logical pages and 2 frames allocated , an approximation of the
Algorithm Last Recently Used based of reference bits where every four references there is
a shift and where are considered just the first 2 bits, and the follow reference string:

  1 2 1 1 1 1 0 1 0 0

I'd solve it in this way:

  1 2 1 1 (m1) 1 1 (m2) 0 1 0 0

(m1)

4 references so I'd pass from

 frame                     frame
 -----+---+---     to       -----+---+---
    1 | 1 | 0                  1 | 0 | 1
    2 | 1 | 0                  2 | 0 | 1

(m2)

page fault so I'd pass from

 frame                     frame
 -----+---+---     to       -----+---+---
    1 | 1 | 1                  1 | 0 | 0
    2 | 0 | 1                  0 | 0 | 0

So the questions are:

Is my doing correct?
At m2 there is a page fault, is there a "reset" and all bits puts at 0?
the shift frequency (4 in the example) restart counting every page fault?


texts: What's the context-free grammar for { w | 2*(number of a's in w) != 3*(number of b's in w) +2 }?

texts:
So I have this language:
$$
A= \{ w \in \{a,b\}^* \mid 2*\#_a(w) \ne 3*\#b(w) + 2\}
$$
I know it's context free, I know how to make a PDA for it, I just can't, for the life of me, figure out how to design a grammar for it.
I know that for this language:
$$
A= \{ w \in \{a,b\}^* \mid 2*\#_a(w) = 3*\#b(w)\}
$$
I can design a grammar that looks like this (and it's hopefully correct):
\begin{align}
             S \rightarrow aSaSaSb | aSaSbSaSb | bSaSaSaSb | aSbSaSaSb | bSbSaSaSa|aSbSbSaSa|bSaSbSaSa|aSbaSbSa|bSaSaSbSa|aSaSbSbSa|SS|\lambda
    \end{align}
And although I know that usually when the condition of the language has $x \ne y$ I should use the union of $x<y$ and $x>y$ I just can't figure out how to do this for this specific example.
I would really appreciate your help on this!


texts: Does Gödel's first incompleteness theorem apply to quantifier-free arithmetics?

texts:
Gödel's first incompleteness theorem states roughly that "for any axiomatization of arithmetic, there are statements that can neither be proven to be false nor true."

Does this still hold when it comes to quantifier-free statements?

I.e. if we have the structure of arithmetic: $(\mathbb N, +,\cdot, 0,1)$, and we restrict to sentences $\Phi^{QF}$ about this structure that don't contain $\exists, \forall$, can we then for all $\phi\in \Phi^{QF}$ either prove or disprove $\phi$?


texts: How to use a CFG to restrict a subset of a*b*c*d* so that there are at most as many a's and b's as d's?

texts:
Give Context-free Grammar for the language $\{a^i b^j c^k d^h \mid i,j,h \ge 0, k>0, i+j \le h\}$

This is a training exercise, for which we don't get any answers, in a course I'm taking. I have found similar examples, but nothing that touches on the i+j≤h part of this. My biggest trouble is that it is ordered, so I have no idea how to add d's to the end when I add a's or b's to the front. I haven't gotten very far because of this, but my thinking looks like this at the moment:

S→ABcCD
A→aA | ϵ
B→bB | ϵ
C→cC | ϵ
D→dD | ϵ

I can't put things like A→aAd or A→aBCD because that would result in c's and d's before b's in the end word/string. My conclusion is that I am probably on the wrong track, but all examples I find use some sort of partitioning like this.

So could anyone point me in the right direction?


texts: Using the appropriate machine learning algorithm

texts:
I am not sure if this is the right forum to ask this.

I have some data of the houses, like their size(in square meters), if they use aircondition, how many residents live in, I have their electricity consumption as well.
I want to train any Machine Learning Algorithm to the dataset above, in order to create a model that estimates the houses consumption.

I tried many different algorithms (using weka), but I did not have good results.
I was said that SVMs could solve this problem, with the right preprocessing. However, i did not have good results either.

Can anyone help me, in the way i should approach this problem?

Thanks in advance


texts: Assign n people to m rooms of different sizes, such that noone is alone

texts:
I'm looking for an efficient way to assign n people to m rooms in a very specific way.

INPUT:

The program receives two sets of people (set of males and set of females), as well as a set of available rooms (rooms can have different sizes, ranging from 2 to 6).

ASSIGNMENT CONDITIONS:

The algorithm must assign people to the rooms in a way, that:

A room can be only occupied either by all males, or by all females
Noone can be alone
The algorithm must minimize the number of occupied rooms

We can assume that there are at least 2 representatives of each gender.

OUTPUT:

The algorithm must return the assignment.

I've tried to do it, but all of the sollutions I come up with are at least O(n^3). Does anyone know an efficient way to do this?


texts: FPTAS algorithm to find flow at each link for multi commodity flow problem?

texts:
Given a graph $G$ and $K$ commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodities and the relevant paths. I understand the problem in general falls under NPC, hence I am looking for FPTAS algorithms.

I am struggling with the problem, so any intuitive idea to tackle the problem is also most welcome.


texts: What approaches are most useful when proving uncomputability of a given function?

texts:
I'd like to understand what approaches should one adopt when deciding/proving that a given function F is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows:

Reduction, from a known uncomputable function (such as $UC(\alpha)$, the uncomputable function as proved by Cantor's diagonalization argument in Chapter 1 of the book "Computational Complexity" by Sanjeev Arora and Boaz Barak, or $HALT(\alpha, x)$, which is nothing but the function in the Halting problem), to F. If such a reduction is possible, it can be argued that F is uncomputable as otherwise, the problems that are proved to be uncomputable would become be computable as well.
Proof by contradiction, in which one shows that if there is a TM M that computes F, it would lead to some sort of inconsistency in either the M's output, or the functions evaluated value.

I've applied (or rather, tried to apply) both the above techniques to some reductions, two of which I now state here (for illustrating the limitations of my approach):

If whenever a TM M accepts a string w $\in$ ${\{0,1\}}^*$, it also accepts $w^R$, the TM M is said to possess property R. ($w^R$ is the string obtained by reversing $w$ i.e. $(110)^R$ is $011$). Let $R: {\{0,1\}}^* \rightarrow \{0,1\}$ be defined as follows: $R(\alpha) = 1$ if $M_\alpha$ possesses property $R$, and $R(\alpha) = 0$ otherwise. Prove that $R$ is uncomputable.

Let $B: {\{0,1\}}^*$ x $ {\{0,1\}}^* \rightarrow \{0,1\}$ be defined as follows:
$B(\alpha,x) = 1$ if $M_\alpha$ writes a non-blank symbol on its output tape while computing input $x$, $B(\alpha,x) = 0$ otherwise. Prove that function $B$ is uncomputable.

For problem 1, I tried reducing the uncomputable function $UC$ to $R$, but the reason I couldn't quite complete the reduction is because $R$ is a property of the Turing Machine, not dependent on any input instance, where $UC$ depends on the output of a specific instance $M_\alpha(\alpha)$. Also, for both $R(\alpha)$ = 0 and $R(\alpha)$ = 1, it is possible that $M_\alpha$ can go on indefinitely for some inputs!
For problem 2, I tried reducing the function $HALT$ to $B$ (thus attempting to make a TM that computes $HALT(\alpha,x)$ by using the output of a TM $M_\beta$ that computes $B$). But here as in problem 1, it is possible that for both outputs of $M_\beta(\alpha,x)$, the TM $M_\alpha$ may not halt at all on input $x$!
So, I'm stumped here - I understand intuitively why these functions should be uncomputable (No TM should be able to predict whether another TM would halt/output anything on any possible input), I'm not quite able to derive a concrete proof! So, I really want to understand what approaches am I missing here, or are there holes in the current approaches that I've tried so far!
Note: For self-containment, I'm stating what are the functions UC and HALT here as well:
$UC: {\{0,1\}}^* \rightarrow \{0,1\}$:
$UC(\alpha) = 0$, when the Turing Machine represented by $\alpha$, $M_\alpha(\alpha)$ = 1
$UC(\alpha) = 1$, otherwise.
$HALT: {\{0,1\}}^*$ x $ {\{0,1\}}^* \rightarrow \{0,1\}$:
$HALT(\alpha, x) = 1$, when the Turing Machine represented by $\alpha$, $M_\alpha(\alpha)$ halts on input $x$.
$HALT(\alpha, x) = 0$, otherwise.


texts:
A bit of context

I was writing a parser for a grammar, and for testing purposes I come up with idea to generate some random inputs. The grammar I was dealing with was much more complicated, in this question I presented "minimal working example" for simplicity. And of course, I am able to avoid the issue I faced using a bunch of trivial heuristics, but the question really makes me wonder.

The problem

Suppose we have a typical context-free grammar for arithmetic expressions of $+,*$, brackets, and integer literals:

$$E \longrightarrow F(“+”F)^*$$
$$F \longrightarrow T(“*”T)^*$$
$$T \longrightarrow int|“(”E“)”$$

It is easy to implement a staighforward algorithm for generating random words by this grammar: we implement a separate procedure for each nonterminal. If a nonterminal has multiple production rules (as $T$ does), we choose a production rule by tossing a coin. If rule contains kleene star (e.g. $(“+”F)^*$), we also toss a coin and generate zero or one repetition (sure we could pick any random integer $k\geq0$ and generate $k$ repetitions, but for simplicity we will focus on the simplest version of this procedure). Here is what we get:

generate_E():
    if coin_toss():
        return generate_F() + "+" + generate_F()
    else:
        return generate_F()

generate_F():
    if coin_toss():
        return generate_T() + "*" + generate_T()
    else:
        return generate_F()

def generate_T():
    if coin_toss():
        return "(" + generate_E() + ")"
    else:
        return random_integer()

An invocation of generate_E() yields a random expression.

What could go wrong? It turns out that execution of this procedure on the real machine terminates with stack overflow quite often. Of course, technically here we have a possibility of endless recursion, but my intuition was telling me that probability of reaching recursion depth $k$ decays exponentially with increasing $k$, therefore getting deep levels (let's say, 1000) is almost impossible. Apparently, a few consecutive runs reveals that procedure can easily reach depth of many thousands (by depth I mean maximum number of procedure calls the stack contains simultaneously).

I am curios how to formalize this empirical fact. I want either a formula for $P(depth = k)$, or an asymptotic approximation of it, or an inequality bounding right tail of CDF below (something like $P(depth > 1000) > 0.05$)

My attempt

I tried to come up with a formula for $P(depth = k)$:

Let's denote $P(depth = k)$ as $P_E(k)$. Also, we define similar values for generate_F() and generate_T() - $P_F(k)$ and $P_T(k)$ respectivetely.

Clearly (else branch of generate_T), $$P_T(1) = \frac{1}{2}$$ and for $k > 1$ (then branch)$$P_T(k) = \frac{1}{2}P_E(k - 1)$$

Regarding $P_F(k)$, we can either execute else branch, and it gives term $$\frac{1}{2}P_T(k - 1)$$, or then branch, what gives a bit more complicated one $$\frac{1}{2}\sum_{(x, y) | max(x, y) = k - 1}{P_T(x)P_T(y)}$$ i.e. $$P_F(k)= \frac{1}{2}(P_F(k - 1) + \sum_{(x, y) | max(x, y) = k - 1}{P_T(x)P_T(y)})$$

Finally, the formula for $P_E(k)$ is almost the same as for $P_F(f)$, we only have to replace $P_T(x)$ with $P_F(x)$.

Now, we can calculate some values of $P_e(k)$

\begin{array} {|r|r|}\hline k & P_E(k) & P_E(k)\text{ in decimal}& P_E(k)\text{ by Monte-Carlo} \\ \hline 3 & \frac{33}{128} & \approx0.257812 & \approx0.2527 \\ \hline 6 & \frac{4448787585}{34359738368} & \approx0.129477 & \approx0.1282 \\ \hline 9 & \frac{14080391757747154038821618051813151497122305}{178405961588244985132285746181186892047843328} & \approx0.078923 & \approx0.0761 \\ \hline 12 & \text{ the fraction is too long} & \approx0.053213 & \approx0.0530 \\ \hline  \end{array}

As we can see, the recurrent formulas seem to be true, but neither they give me an insight on asymptotical behaviour of $P_E(k)$, nor the first values give a clue on formula in closed form.

Any help would be appreciated.


texts:
If an attacker has an unlimited physical access to CPU, but does not have access to memory, including RAM, can he attack and gain access to the user's data?

I heard the opinion that this is impossible according to the laws of physics, even with an electron microscope. It's true?


texts: Practical exponential time algorithms for polynomial-time solvable problems

texts:
Inspired by this quote attributed to Alan Perlis:

  For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run.

How I interpret this statement is that some exponential running times should be preferred over polynomial ones for realistic problem sizes. I have never actually seen such a case though.

I wonder if there are any problems for which exponential algorithms are known that are preferable to the best polynomial ones up to a nontrivial problem sizes?


texts: What are the gates used to implement Shor's algorithm?

texts: I understand theoretically how Shor's algorithm works, but I don't know what specific gates are used (or would be used) to implement it. What would the quantum circuit look like?


texts: Why is $DSPACE(\log(n)) = NSPACE(\log(n))$ not known?

texts:
Here $DSPACE(\log(n))$ is the family of algorithms for which there exists a deterministic Turing machine using $O(\log(n))$ space.

On the other hand $NSPACE(\log(n))$ is the family of algorithms for which there exists a non-deterministic machine using $O(\log(n))$ on all the possible path it could explore.

I understand that $DSPACE(\log(n)) \subset NSPACE(\log(n))$ because a Turing machine is just a special case of a non-deterministic one. Although, it seems to be that the fact $NSPACE$ considers all the possible path of a non-deterministic machine makes it a way stronger condition which would lead to $NSPACE(\log(n)) \subset DSPACE(\log(n))$.

Although, to the best of my knowledge $L = NL$ is an open problem which I surely did not crack just there.

Why is my reasonning wrong and what would be a good counterexample?


texts: Compress 32 bit integer into a normalized float

texts:
and sorry if this is a duplicate of some sort, my poor technical vocabulary doesn't get me very far with google.

I am trying to implement some well-known PRNG algorithms. For the time, the algorithm in themselves do their job very well (generating 16/32/64/128 random bits). I am now trying to create a uniform distribution function, that, taking as input a 16/32/64/128 bit integer spits a IEEE compliant binary2, binary4 or binary8 (the function doesn't have to handle all of them at once, but by able to somewhat template for the other floating point types.

As quoted in the title of the question, the output shall be between -1.0 and 1.0 . A naive implementaion would be to take a byte of the integers, and affect it to the exponent, while leaving the rest to the mantissa (padding with 0s if there's not enough bits), but how to handle denormals (the code is performance critical, and the target is reluctant with un-uniform data-based condition). How to handle these then ?.

And while that may be asking two questions at once, how to do the same for a normal distribution ?

Any help or guidance is appreciated. Thanks in advance


texts: The image of a recursive language under a computable function

texts:
Let $f:\Sigma^{*}\to\Sigma^{*}$ be a computable function and let $L$ be a recursive language. Is $f(L):=\left \{{f(w)|w\in L} \right\}$ recursive?

Here, I see clearly, that $f^{-1}(L)$ is recursive (simply by applying $f$ on an input $w$, and then see if $f(w)$ belongs to $L$).

My intuition tells me that $f(L)$ should also be recursive. For an input $w$, we should verify if there exists $x\in \Sigma^{*}$ such that $f(x)=w$. We can apply $f$ on every word lexicographically. Surely, if $w\in f(L)$, the machine accepts. But otherwise, the machine does not halt. So maybe my intuition is wrong?


texts: Is there a designation for this not-quite-exponential time?

texts:
I've been working and experimenting with an algorithm that may take time $O^*(2^\sqrt{n})$.  Here $O^*(f(n))$ simply neglects all polynomial terms.  I've seen a comment on Scott Aaronson's blog that mentions graph isomorphism algorithms run in this time, too.  Actually, $O(2^\sqrt{n})$.  Is there a designation for this time?

I thought perhaps quasi-exponential may describe it, but I'm wondering if there is already a name/designation for it.


texts:
Distributed Systems 5ed by Coulouris says on p68

  2.4.2 Failure Models

  Omission Failures ...

  Arbitrary Failures
  The term arbitrary or Byzantine failure is used to describe the worst
  possible failure semantics, in which any type of error may occur. For example, a process
  may set wrong values in its data items, or it may return a wrong value in response to an
  invocation.

  Timing Failures ...

Are arbitrary/Byzantine failures arbitrary? (Sounds yes to me.)

Do arbitrary/Byzantine failures include omission failures and timing failures? (I guess not. Otherwise, why does it describe omission failures and timing failures separately?)

The book on p660 says

  15.5.1 System model and problem definitions

  Our system model includes a collection of processes communicating by
  message passing. An important requirement that applies in many
  practical situa- tions is for consensus to be reached even in the
  presence of faults. We assume, as before,  that communication is
  reliable but that processes may fail. In this section we consider
  Byzantine (arbitrary) process failures, as well as crash failures.

Does the above quote imply that crash failures (a kind of process omission failures, as the book said in Section 2.4.2) are not Byzantine (arbitrary) process failures?

Thanks.


texts: Why is the second while loop in KMP not a conditional statement?

texts:
When building the partial match table for KMP:

void buildBackTable() {
    int i = 0, j = -1; b[0] = -1;
    while (i < m) {
        while (j >= 0 && P[i] != P[j]) j = b[j]; //Why is this a while loop!?
        i++; j++;
        b[i] = j;
    }
}

How come that second while loop is not a conditional instead? Such as:

void buildBackTable() {
    int i = 0, j = -1; b[0] = -1;
    while (i < m) {
        if (j >= 0 && P[i] != P[j]) j = b[j]; //Why not?
        i++; j++;
        b[i] = j;
    }
}

In most of the examples I've tried, this statement is used to reset j to -1 when there is no match, so when the next iteration comes, we compare the first character of the string (P[j]) with the character at position i (P[i]). Is there an example where the while loop would be needed? I would love to see one. I've tried several samples of my own and changing the statement to a conditional would not make a difference (hence my question).


texts: Proving $\{xx^R \mid x\in L_1, x^R\in L_2\}$ is context-free

texts:
I have this problem:

  Let $L_1$ and $L_2$ be two regular languages.  Show that $L_3 = \{xx^r : x \in L_1, x^r \in L_2 \}$ is a context-free language.

I am unsure how to prove that some language is context-free. Could someone please provide the steps?


texts:
What is $S2-EXP•P^{NP}$?
I saw in on the complexity zoo site without any explanation of what it is.
Coul someone please explain it?


texts: Complexity of divide and conquer algorithm with a quadratic merge function

texts:
Consider the following pseudocode:

int divide(int l , int r){
    if r - l > 3 then
        mid = (l + r) / 2
        divide(l , mid)
        divide(mid + 1, r)
        return merge(l, mid, r)
    else
        return bruteforce_solution(l, r)
}

If merge function takes $O(n^2)$ time, then total complexity can be found as a solution of the reccurence: $T(n)=2T(n/2)+n^2$
The solution of a the reccurence is $T(n)=2n^2-n$
So $O(log(n))$ calls of an $O(n^2)$ function takes $O(n^2)$ time?