texts: Connection between KMP prefix function and string matching automaton

texts:
Let $A_P = (Q,\Sigma,\delta,0,\{m\})$ the string matching automaton for pattern $P \in \Sigma^m$, that is

$Q = \{0,1,\dots,m\}$
$\delta(q,a) = \sigma_P(P_{0,q}\cdot a)$ for all $q\in Q$ and $a\in \Sigma$

with $\sigma_P(w)$ the length of the longest prefix of $P$ that is a Suffix of $w$, that is

$\qquad \displaystyle \sigma_P(w) = \max \left\{k \in \mathbb{N}_0 \mid P_{0,k} \sqsupset w \right\}$.

Now, let $\pi$ the prefix function from the Knuth-Morris-Pratt algorithm, that is

$\qquad \displaystyle \pi_P(q)= \max \{k \mid k < q \wedge P_{0,k} \sqsupset P_{0,q}\}$.

As it turns out, one can use $\pi_P$ to compute $\delta$ quickly; the central observation is:

  Assume above notions and $a \in \Sigma$. For $q \in \{0,\dots,m\}$ with $q = m$ or $P_{q+1} \neq a$, it holds that

  $\qquad \displaystyle \delta(q,a) = \delta(\pi_P(q),a)$

But how can I prove this?

For reference, this is how you compute $\pi_P$:

m ← length[P ]
π[0] ← 0
k ← 0
for q ← 1 to m − 1 do
  while k > 0 and P [k + 1] =6 P [q] do
    k ← π[k]
    if P [k + 1] = P [q] then
       k ← k + 1
    end if
    π[q] ← k
 end while
end for

return π


texts: What is wrong with this proof that proves that 0*1* is not a regular language?

texts:
I know why cases 1 and 2 are wrong because our language can have different numbers of 0's and 1's. But I'm not sure how case 3 can be proved wrong for our language.
Exercise 1.30:
Describe the error in the following “proof” that $0^{∗}1^{∗}$ is not a regular language. (An error must exist because $0^{∗}1^{∗}$ is regular.)

The proof is by contradiction. Assume
that $0^{∗}1^{∗}$ is regular. Let p be the pumping length for $0^{∗}1^{∗}$ given by the pumping
lemma. Choose s to be the string $0^{p}1^{p}$. You know that s is a member of $0^{∗}1^{∗}$, but
Example 1.73 shows that s cannot be pumped. Thus you have a contradiction. So
$0^{∗}1^{∗}$ is not regular.

Example 1.73:

Let B be the language $\{0^{n}1^{n}|n ≥ 0\}$. We use the pumping lemma to prove that
B is not regular. The proof is by contradiction.
Assume to the contrary that B is regular. Let p be the pumping length given
by the pumping lemma. Choose s to be the string $0^{p}1^{p}$. Because s is a member
of B and s has length more than p, the pumping lemma guarantees that s can be
split into three pieces, s = xyz, where for any i ≥ 0 the string $xy^{i}z$ is in B. We
consider three cases to show that this result is impossible.

The string y consists only of 0s. In this case, the string xyyz has more 0s
than 1s and so is not a member of B, violating condition 1 of the pumping
lemma. This case is a contradiction.
The string y consists only of 1s. This case also gives a contradiction.
The string y consists of both 0s and 1s. In this case, the string xyyz may
have the same number of 0s and 1s, but they will be out of order with some
1s before 0s. Hence it is not a member of B, which is a contradiction.

Thus a contradiction is unavoidable if we make the assumption that B is regular,
so B is not regular. Note that we can simplify this argument by applying
condition 3 of the pumping lemma to eliminate cases 2 and 3.
In this example, finding the string s was easy because any string in B of
length p or more would work.

This question is from the book 'Introduction to the Theory of Computations' by Michael Sipser, exercise 1.30


texts: hi I'm having difficulty in Designing a DFA binary string with exactly 2 occurrences of 010?


texts: Use the pumping lemma to show the language is not regular

texts:
I can use the pumping lemma to prove simpler examples, but i'm finding this problem rather complex partly due to the notation.

Can anyone explain how I would do this problem:

  For any string $s$ in $\{a, b\}^*$, let $n_a(s)$ be the number of a’s in s, and let $n_b(s)$ be the number of b’s in s. Let L over {a, b} be given by $L = \{x \in \{a, b\}^* | n_b(x) = n_a(x)^2 \space \text{and} \space x \notin ((a^∗b^∗) ∪ (b^∗a^∗))\} $.
  Prove, using the pumping lemma for regular languages, that the language L is not a regular language

I know we suppose that it is regular then by the pumping lemma it has to satisfy the properties of the pumping lemma for regular languages.

Hence, we need to find a decomposition and break it by pumping this decomposition which is no longer in the language forming a contradiction by hypothesis. However, I fail to see the decomposition or what to pump....


texts: Converting from cfg to cnf (Chomsky normal form)

texts:
I am trying to convert this grammar from context free grammar with kleene star productions into the Chomsky normal form equivalent. I am having a hard time trying to understand how to do this, I need this for use in recursive decent parsers primarily a table driven top down predictive parser.

Grammar

  expr        ::= term {addop term}
  term    ::= factor {mulop factor}
  factor     ::= variable| unsigned-number| ( expr)
   variable ::= identifier
  addop ::= + | -
  mulop ::= * | /


texts: How to Simulate Nested Parallelism on a Sequential Machine

texts:
So I have sets of functions $A$, $B$, $C$, $D$, $E$, and $F$. I want to run them in a nested way. I also want to run some of them in parallel, and some of them in sequence. Here is how that might look:

In Parallel A {
  In Sequence B {
    In Parallel C {
      In Sequence D {
        In Parallel E {
          In Sequence F
        }
      }
    }
  }
}

Now I start getting lost on how this would look. Here is my attempt at explaining it...

Part I

This part I can sort of understand.

Say we have $n$ $A$ processes running in parallel with $\land$.

$$A = a_1 \land a_2 \land \dots \land a_n$$

Within $a_1$, say we have 5 steps running in sequence with $\to$, and $a_2$ is 10 steps, etc. We have:

\begin{align}
  \land\ a_1 &= b_1 \to b_2 \to \dots \to b_5\\
  \land\ a_2 &= b_1 \to b_2 \to \dots \to b_{10}\\
  \land\ a_3 &= b_1 \to b_2\\
  \dots\\
  \land\ a_n &= b_1 \to b_2 \to \dots \to b_n
\end{align}

Now, I would like for "all of $A$ to run at the same time". This means that each $a \in A$ is a whole process. That is, if $a_1$ takes 5 steps and $a_2$ takes 10 steps, the whole process won't start over until 10 steps later.

$$A_{1,s=10} \to A_{2,s=10} \to \dotsc \to A_{n,s=10}$$

That means it will sort of look like this:

\begin{align}
  A_1 &: s\ s\ s\ s\ s\ s\ s\ s\ s\ s\\
  A_2 &: s\ s\ s\ s\ s\ w\ w\ w\ w\ w\\
  A_3 &: s\ s\ w\ w\ w\ w\ w\ w\ w\ w\\
  \dots\\
  A_n &: s_n \dots w_n
\end{align}

Where $s$ is a step and $w$ is waiting.

Part II

This part is where I get lost.

Now I want to be able to just apply this reasoning to the nested parallel and sequential processes. Informally, so $A$ has started, this means $a_1$ has started, which means $b_1$ has started. Now $b_1$ wont complete until all of the $C$ nested within it have completed, but they are running in parallel.

$$b_1 = c_1 \land c_2 \land \dots \land c_n$$

So it's like:

| a1. . . . .           | a1. . . . .
| b1. . b2. .           | b1. . b2. .
| c .   c . .           | c .   c . .
| c . . c . .           | c . . c . .
| c .   c . .           | c .   c . .
| c .   c . .           | c .   c . .
| c .   c .             | c .   c .

| a2. . . . . . . . . . | a2. . . . . . . . . .
| b1. . . . b2. . . . . | b1. . . . b2. . . . .
| c . . .   c . . . . . | c . . .   c . . . . .
| c . .     c .         | c . .     c .
| c . . . . c . . .     | c . . . . c . . .
| c . .     c . . .     | c . .     c . . .
| c .       c . . . .   | c .       c . . . .

Then it goes into further nesting all the way to $F$, which would be hard to draw and is really hard to think about.

Part III

This is where I get quite lost.

Now to model them sequentially.

I have just been wanting to do this:

for a in A:
  for b in B:
    for c in C:
      run c...

But that isn't right. So then I've tried:

for a in A:
  start a
for b in B:
  start b
for c in C:
  start c
for aa in start a
  ... hmm

Now that's not going to work.

So then it's like, if the functions were all flattened somehow, then we could just iterate through them. But I am already really confused by this point.

Question

My question is, how I simulate this on a sequential machine.

Any help would be greatly appreciated.


texts: Classic Problems on Process Synchronization

texts:
I have been studying Process Synchronization and inter-process communication in Operating Systems Engineering and have come across multiple problems like "Sleeping Barbers", "Producer Consumers", "Dining Philosophers" and "Reader Writers" . While working on these problems I found them very interesting and I get a sort of feeling that each problem has its special significance. I can visualize the situations in which "producer consumers problem" and "reader writers problem" can be applied but have been stuck with "Sleeping Barbers Problem" and "Dining Philosophers problem".

  What are the examples of application of Sleeping Barbers problem and Dining Philosophers problem in computer science( primarily Operating Systems Design and Databases)?


texts: Difference between multitasking, multithreading and multiprogramming

texts:
I was a little confused between these three terms Multitasking, Multithreading and Multiprogramming

Although every one means executing different lines of codes, and for every one we need something like Task State Segment or context to store data for that particular thread/task.

I am missing something, can anyone give me the basic difference between them and how they are actually executed in a processor

Edit: Actually I was a guy from Electronics background and I was poor at OS related issues. The main thing I understood between multiprogramming and multithreading is that in multiprogramming we execute two separate programs where as in multithreading the scheduler produces two different threads which can be executed independently. I think these are a form of multitasking implementation. Am I correct. I was really confused


texts:
Okay so I've been going crazy about this problem I was given. It is as follows:

Given a pile of N matches, 2 people take turns removing matches from the pile. When it is your turn you are allowed remove 1, 5 or 6 matches. If it is your turn and you are unable to make a move then the game is over and you have lost.

The idea is to develop a strategy where you can always win. Note that you can always decides who goes first.

Not sure if I'm even on the right track but currently I can guarantee that if it is my go and  then I remove 1, 5 or 6 matches, leaving my opponent with 22 matches I will win. But unsure how to guarantee that this situation will arise.

Any help would be appreciated even if it's just a reassurance that it is possible because I've spent hours within the last 2 days and still can't come up with a winning strategy that works all the time.


texts:
The problem

Given $n$ stacks of $k$ integers each. What is the maximum sum that can be achieved by removing exactly $p$ integers?

The following example illustrates the problem.

$n$ = 3, $k$ = 4, $p$ = 3

stack 1: 2, 5, 12, 5

stack 2: 10, 3, 12, 50

stack 3: 7, 4, 20, 20

Note that the top of a stack is the leftmost element.

Here, the optimal solution is to pick all the first three numbers from stack 3, which gives a sum of 31.

The algorithm

I came up with the following algorithm.

The idea is to calculate the best possible sum for each stack if all $p$ elements were chosen from that particular stack. This sum only considers the integers that can possibly be taken.

Then, greedily take the top element from the stack with the best possible sum. And update the sum for all stacks because now only $p-1$ integers need to be popped.

The question

is this algorithm always going to produce a correct answer? If not, when would this fail?

Disclaimer

I am aware that a dynamic programming solution can solve the problem in $O(npk)$ time.

This is based on the following problem from a previous contest on google coding competitions platform. (https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d40bb)


texts: How to resolve issue of circular definition for an `If` statement

texts:
I am trying to define an If statement, but am stuck because the definition/implementation of If is circular from what I have tried. For example, here is one definition:

class If {
  provide: Condition
  provide: TrueBlock
  body:
    If (Condition) {
      call(TrueBlock)
    }
}

You can then use it like this:

If (true) {
  Something()
}

But the thing is, the definition itself uses If to define it:

class If {
  ...
    If (Condition) {
      call(TrueBlock)
    }
}

The only other way I can think of defining it is by saying that an If statement is an "atomic statement", and so it doesn't have an implementation. (The compiler or whatever would then have special instructions to treat it uniquely).

class If {
  provide: Condition
  provide: TrueBlock
}

That would be the whole definition of If. No implementation required.

Wondering if this is sort of the right approach to this problem. The problem being that you can't really implement an If statement without resorting to using If itself. And so you define it as atomic.


texts:
Is there a direct way to represent Kleene plus(+) using  Thompson's construction algorithm?
When I studied Thompson's construction I learned how to transform concatenation, union and kleene star of regular expresions directly into a NFA.
In wikipedia(and other websites) I found the same thing I learned in college(nothing about Kleene plus):Thompson's construction
In a non-direct method we can always transform $R^+$ in $RR^*$ and then use Thompson construction.
There is a website that transform regular expressions into NFA. They claim to use Thompson-McNaughton-Yamada algorithm. Here they transform $a^+$ into:

Is this some kind of extension of Thompson's construction algorithm?


texts: Why do we need MinHeap for Meeting Rooms 2 Leetcode problem

texts:
I came across this problem online which is a Leetcode premium problem. Most of the people are solving this using Minheap. To me using minHeap for this seems like repetitive way to solve a problem if we can achieve the same thing just by sorting the array based on startTimes & than checking if meeting(i).endTime > meeting(i+1).startTime. Increment if the aforementioned condition is true.
I don't have access to leetcode premium so I can't verify if the following solution would suffice.
Am I missing something here?
Problem Statement:

public int minMeetingRooms(List<Interval> intervals) {
        // Write your code here

        if(intervals == null || intervals.size() == 0)
            return 0;

        Collections.sort(intervals, (meeting1, meeting2) -> meeting1.start-meeting2.start);

        int rooms = 1;

        for(int i=0; i<intervals.size()-1; i++) {
            if(intervals.get(i).end > intervals.get(i+1).start)
                rooms++;
        }

        System.out.println("rooms required: "+ rooms);

        return rooms;
    }


texts:
Denote $D$ a set of finite sequences of integers. In Papadimitriou's "Computational Complexity" in theorem 2.5 it is proved that if a RAM program $\Pi$ computes a function $\phi$ from $D$ to integers in time $f(n)$, then there is a $7$-string Turing machine $M$, which computes $\phi$ in time $O(f(n)^3)$.

Consider the following example: $\phi(S)$ is a sum of first two numbers of a finite sequence $S$, or $0$, if $|S| < 2$. It seems to me that a RAM, defined in Papadimitriou's book computes $\phi$ in time $O(1)$. Thought, any Turing machine, computing $\phi$, should work for at least linear time (we can take an input of length $n$ with only two numbers in sequence). I don't see how to cope with this contradiction.

Could you please describe me, where I am wrong? Thanks a lot.


texts: Do all recursive problems have optimal substructure?

texts: I am reading about dynamic programming and I understand the overlapping subproblem requirement but not sure why optimal substructure is explicitly stated. Are there problems that can be solved recursively that do not have an optimal substructure?


texts: Boolean formula that agrees with most truth assignments

texts:
Let $X_1,\dots,X_n$ be $n$ boolean variables.  I have an unknown predicate $P(X_1,\dots,X_n)$ on these boolean variables.  Of course, I can view the predicate as a function $f_P : \{0,1\}^n \to \{0,1\}$ that maps a vector of $n$ boolean values to the truth value of this predicate on those inputs.

Now I have a truth table of pairs $(x_1,y_1), \dots, (x_m,y_m)$, and I want to find a predicate $P$ that is consistent with these pairs and that is as "simple" as possible.  In particular, I have two variants of the problem:

Problem 1. Given $(x_1,y_1), \dots, (x_m,y_m)$, find a predicate $P$ such that (1) it agrees with the entire truth table (i.e., for all $i$, $f_P(x_i)=y_i$), and (2) out of all such predicates, the complexity of $P$ is minimized.

Problem 2. Given $(x_1,y_1), \dots, (x_m,y_m)$ and a threshold $t$, find a predicate $P$ such that (1) $P$ agrees with at least a $t/m$ fraction of the truth table (i.e., there are at least $t$ values of $i$ such that $f_P(x_i)=y_i$), and (2) out of all such predicates, the complexity of $P$ is minimized.

Are there any algorithms for solving either of these problems, in a way that is more efficient than enumerating all predicates?

Of course, to make the problem well-posed, we must agree on a definition of the complexity of a predicate.  Here I can see any number of realistic complexity metrics.  One metric might be that, when we express $P$ as a formula in boolean logic, the length of that formula.  Another might be the number of operators in that formula, or the nesting depth of the formula.  I am interested in any and all algorithms for any plausible notion of complexity.

This can be viewed as a kind of learning problem, where Occam's razor suggests that low-complexity predicates are a priori more likely than high-complexity predicates.


texts: Numeral systems other than unary used in nature or in animal and human behaviours

texts:
Representing numeric values using positional notation is one of the milestones in the history of arithmetic. Babylons used a base 60 system, Maya a base 20 system; base 10 system became "the standard" used by modern civilizations; digital computers use the Binary numeral system, ....

But if we look at nature, we found that life itself "heavily rely" on an alphabet of 4 symbols: the DNA has four (chemical) bases: adenine, cytosine, guanine and thymine (A, C, G, T) that are used to store the "instructions and information" to generate and drive the parts of a living organism.

But on a higher level, are there "natural algorithms" (algorithms found in natural processes, in animal behaviours or in everyday human behaviours) that take advantages of "numeral systems" other than the unary representation.

To be more precise I would like to know whether or not natural processes or living creatures make use of a finite, discrete alphabet of "symbols" and use them in a manner similar to a positional notation: the symbols are placed together and used as a whole to  represent "something" (an action, an information, an object, ...) among many other possibilites ... a sort of "index" in an exponential number of possibilites.

Another (obvious) non numeric example is the human language where (in general) a combination of finite number of sounds ("alphabet") are combined to form the words.


texts:
Just a basic question to ask

Does the write through cache copies the whole block or just the byte which is updated?

I went through the following question

Array A contains 256 elements of 4 bytes each. Its first element is stored at physical address 4096.
Array B contains 512 elements of 4 bytes each. Its first element is stored at physical address 8192. Assume that only arrays A and B can be cached in an initially empty, physically addressed, physically tagged, direct mapped, 2K-byte cache with an 8 byte block size. The following loop is the executed

for(i=0; i<256; i++)
A[i] = A[i] + B[2*i];

How many bytes will be written to memory if the cache has a write-through policy?

I calculated it as follows:

The cache can store the whole array with 2 elements per block (block size = 8bytes, element size = 4bytes). For every write, the whole block will be copied. For $0^{th}$ element, the block containing $0^{th}$ and $1^{st}$ element would be written. The same would be done for $1^{st}$ element as well.

So, for every iteration the 2 elements would be written. This makes the number of bytes as $256*2* (4bytes / element) = 2048bytes$.

But in the solution, they have just calculated the number of loop iterations ($256$) multiplied by the element size ($4byte$) which makes the answer $1024bytes$.
If this is true, then the cache would update only the updated byte (not the whole block).

Which is correct?


texts: Applying a 1-qubit gate to entangled qubits

texts:
Given two entangled qubits in the state ${|00⟩+|11⟩\over \root \of 2}$, I have trouble getting the way of applying a 1-qubit gate (let's say a Hadamard) to 1 of the entangled qubits (let's say the first one). Actually I have several questions:

Following this link, Ran G. says that "You can apply a quantum gate on any subset of the qubits."
On the other, hand Agent Gotse says here that "You can not compute the Hadamard gate on only one qubit, as the state is entangled and cannot be factored into two independent qubits."
Do the answers contradict themself?
I understand part of the principle of the entangled pair, it a superposition of bipartite system. But given for example an entangled pair $|00⟩+|11⟩ = |0⟩ \otimes |0⟩ + |1⟩ \otimes |1⟩$, and two unitary operators $A\ B$ to appy to the system.
Why can't we juste do $A|0⟩ \otimes B|0⟩ + A|1⟩ \otimes B|1⟩$?
I mean what is the mathematical meaning of that?
Finally, the superdense coding use an entangled pair, and in the procedure given in the link, Alice apply some operator to her qubit without changing Bob's one (because it's probably far far away...). Quantum Computing textbooks say that in the case of an entangled pair, Alice has to apply $U \otimes I$, with $U$ the chosing operator.
But Alice has only 1 qubit, and clearly $U \otimes\ I$ acts on 2 qubits (it's a $4*4$ matrix), how it's works physically?


texts:
Coinduction is a logical principle that is somehow dual to induction. I'm struggling to understand it.

Are there any interesting examples of coinduction in analysis?

A few examples seem like they could be promising:

the $p$-adic numbers can be represented as infinite streams in such a way that the arithmetic operations are well-behaved. Therefore coinduction seems quite promising here.
continued fractions for real numbers. Unfortunately, the arithmetic operations are not well behaved in this representation; so it's unclear if it's of any use.
Real numbers with signed digits. Coinduction here is complicated by the fact that representations of real numbers become non-unique. But the arithmetic operations are well-behaved. Seems promising.
Power series.
Continued powers or "infinite radicals".


texts: How to prove that a grammar is unambiguous?

texts:
My problem is how can I prove that a grammar is unambiguous?
I have the following grammar:
$$S
→ statement
∣ \mbox{if } expression \mbox{ then } S
∣ \mbox{if } expression \mbox{ then } S \mbox{ else } S$$

and make this to an unambiguous grammar, I think its correct:

$ S → S_1 ∣ S_2 $
$S_1
→ \mbox{if } expression \mbox{ then } S
∣ \mbox{if } expression \mbox{ then } S_2 \mbox{ else } S_1$
$S_2
→ \mbox{if } expression \mbox{ then } S_2 \mbox{ else } S_2
∣ statement$

I know that a unambiguous grammar has one parse tree for every term.


texts: explaining $\lambda$-calculus/functional programming to someone used to Turing machines/procedural programming?

texts:
I have the following background:

I have experience with object-oriented programming languages
I find Turing machines and the concept of a "procedure" very intuitive.

Yet I'm interested to understand the idea behind the abstract $\lambda$-calculus, and its application in the form of functional programming.

When I read about either $\lambda$-calculus or functional programming, these explanations tend to either:

make reference to practical benefits that seem generally beneficial to me, but don't give me a fundamental-principled understanding. E.g. that functional programming languages are more modular and less error-prone because there are no state-dependencies.
or assume an already existing intuitive familiarity with either $\lambda$-calculus or the practicalities of functional programming. (Essentially these explanations suffer from the curse of knowledge: the authors cannot place themselves in the shoes of someone who doesn't have their intuition yet).

So I am looking for a general, principled, theoretical understanding of the conceptual and formal difference between (1) $\lambda$-calculus and Turing machines, and between (2) functional programming and procedural programming.


texts: Convert ambiguous grammar to unambiguous and SLR(1)

texts:
I have the following ambiguous operator grammar:

E->E+E*E | E-E*E
E->E+E | E-E | E+E | E*E | E/E
E->(E) | x

I must convert it to an unambiguous one which is also SLR(1).
The following rules regarding precedence and associativity must hold:

Operators * and / have the highest precedence (and precedence between them must be equal)
Operators - and + have the same precedence (lower than * and /)
All operators are left associative.
Reducing with the first 2 rules is preferred if it does not break the precedence and associativity rules.

My problem is the first line of the grammar (E+E*E , E-E*E). I can't find i way to convert it and the new grammar will be SLR(1).

Edit:
The closest i came is this grammar, but it has 2 SLR conflicts:

E->E+F | E-F | T
T->T+F | T-F | F
F-> F*C | F/C | C
C-> (E) | x


texts: Game of Nim (Find winning states in large range)

texts:
If I want to solve a game of nim with 3 piles containing (x, 2x, 3x) respectively

I know that the solution of (winning) iff x^2x^3x != 0

but if x can be in the range from 1 to 2^61 so How many winning states in this range?

I want to solve this problem ... I tried to find a pattern but I think there is no pattern for that


texts: Abusing ElGamal in order to attack a known encrypted text

texts:
I saw a very interesting question regarding Elgamal cryptosystem that I don't know its answer. It is really interesting and I would be very happy if you could elaborate on it and explain the tricky part.

It goes like this: given Elgamal Cryptosystem:

1) Show how it is possible to create a valid new encryption from two different encryptions that we don't know their decryption

2)How can an adversary take advantage of this property in order to attack a known encrypted text?

I don't understand it, and it seems really cryptic and interesting. Tried digging on it but couldn't find the connection or insights.

Seems really fascinating, would appreciate if you could explain it so I can understand this riddle.


texts: Looking for two-way communication/consensus/contract algorithm for use in marriage proposal

texts:
I am looking for some sort of communication or consensus algorithm with the following properties:

Can be used with just two parties (and ideally doesn't collapse to a trivial case with two parties)
Requires each party to initiate some sort of communication to which the other responds (ideally in a binary way)
Non-hierarchical
Bonus points if it's some sort of consensus, decision-making, or contract signing algorithm

Context: my boyfriend and I are planning on getting engaged soon. For various reasons, we would both like to propose to each other. The challenge is that we don't want whichever proposal is second to feel like it was unnecessary. Since we're both computer scientists, we figure there must be an algorithmic solution to this problem! So we are looking for a communication protocol/consensus algorithm/something else in that vein in which it is necessary for both parties to initiate and respond to a communication. We will be implementing the chosen algorithm verbally, not over an actual internet connection. In case you're having a hard time picturing this, it would be kind of like how a lot of textbooks will have conversational English versions of the messages being sent under various communications protocols, e.g.:

Except we would replace "Hey. Can I talk to you?" with something more like "Will you marry me?".

Before anyone asks, yes, this is entirely symbolic/for fun, but we feel that's true of most aspects of getting engaged/married. And yes, we are nerdy enough that we will happily exchange random numbers with each other in public if that's what the protocol (or its associated cryptography) demands.

Possibilities we've considered so far:

TCP: This was our first thought, but it's not a great fit. For connection establishment all the server sends is a SYN-ACK, which isn't really satisfying either as a response to the first proposal or as the question being asked in the second proposal. The connection termination protocol seems like it would be weird to adapt to verbal communication.
Dining cryptographers: Would be great (although we'd have to use 0 to mean yes, which is a little gross), except it falls apart with only two parties. So we'd have to include a third person (and give them veto power over our engagement). It would be perfect for a polyamorous engagement, though!
Some sort of blockchain consensus algorithm: All the ones I'm aware of seem like they'd collapse to a trivial case with two parties (but I could be wrong about this)
Some sort of contract signing algorithm: Probably the best option we've found so far. These are the closest to being designed to solve the actual problem that we have, but all the ones I've seen require some sort of trusted third party (we could make that work but it wouldn't be ideal).

Does anyone know of an algorithm that is a better fit than these? Apologies if this is off-topic (I'm hoping it falls under "we do not hate fun")!


texts:
If a grammar is of the following form (i.e. all its productions are), is its language regular?

$B → a$ - where $B$ is a non-terminal in $N$ and a is a terminal in $Σ$
$B → aC$ - where $B$ and $C$ are in $N$ and $a$ is in $Σ$
$B → ε$ - where $B$ is in $N$ and $ε$ denotes the empty string, i.e. the string of length 0.
$B → A$ - where $A$ and $B$ are non-terminals in $N$

(1. - 3. quoted from wikipedia)

I only added the 4th rule and I assume that the language is regular. However, I cannot find any reference that supports this intuition.


texts:
Let us have a set of N men and N women, and we have two matrices of affinities $M$ and $W$ such that $M(i,j)$ is the affinity of the ith man towards the jth woman and $W(i,j)$ is the affinity of the ith woman towards the jth man.

The problem at hand is to find an optimal stable marriage, which satisfies that:

There is no couple of man and woman not married such that they would prefer to be with each other (have higher affinity towards) rather than their actual partners.
The sum of the affinities of each couple is maximal among the stable marriages.

Does vanilla Gale Shapley solve this problem? If not, is it NP-complete or is there any hope of solving it polynomially?


texts: Intuition behind eigenvalues of an adjacency matrix

texts:
I am currently working to understand the use of the Cheeger bound and of Cheeger's inequality, and their use for spectral partitioning, conductance, expansion, etc, but I still struggle to have a start of an intuition regarding the second eigenvalue of the adjacency matrix.
Usually, in graph theory, most of the concepts we come across of are quite simple to intuit, but in this case, I can't even come up with what kind of graphs would have a second eigenvalue being very low, or very high.
I've been reading similar questions asked here and there on the SE network, but they usually refer to eigenvalues in different fields (multivariate analysis, Euclidian distance matrices, correlation matrices ...).
But nothing about spectral partitioning and graph theory.

Can someone try and share his intuition/experience of this second eigenvalue in the case of graphs and adjacency matrices?


texts: Can non-recursively enumerable languages be solved with dovetailing?

texts: I'm a bit confused about the dovetailing concept. It seems too powerful. Could it solve non-recursively enumerable languages?


texts: Removing duplicates efficiently and with a low memory overhead

texts:
I want to filter efficiently a list of integers for duplicates in a way that only the resulting set needs to be stored.

One way this can be seen:

we have a range of integers $S = \{1, \dots{}, N\}$ with $N$ big (say $2^{40}$)
we have a function $f : S \to S$ with, supposedly, many collisions (the images are uniformly distributed in $S$)
we then need to store $f[S]$, that is $\{f(x) | x \in S\}$

I have a quite accurate (probabilistic) estimation of what $|f[S]|$ is, and can therefore allocate data structures in advance (say $|f[S]| \approx 2^{30}$).

I have had a few ideas, but I am not sure what would be the best approach:

a bitset is out of the question because the input set does not fit into memory.
a hash table, but (1) it requires some memory overhead, say 150% of $|f[S]|$ and (2) the table has to be explored when built which requires additional time because of the memory overhead.
an "on the fly" sort, preferably with $O(N)$ complexity (non-comparison sort). Regarding that, I am not sure what is the major difference between bucket sort and flashsort.
a simple array with a binary search tree, but this requires $O(N \log |f[S]|)$ time.
maybe using Bloom filters or a similar data structure could be useful in a relaxation (with false positives) of the problem.

Some questions on stackoverflow seem to tackle with this sort of things (https://stackoverflow.com/questions/12240997/sorting-array-in-on-run-time, https://stackoverflow.com/questions/3951547/java-array-finding-duplicates), but none seems to match my requirements.


texts: Maximum size of Huffman codes for an alphabet containing 256 letters

texts:
I made a Huffman algorithm for data compression: it takes the content of a file as an input and outputs a compressed string. More important, it generates optimal prefix codes (made of 0 and 1) for every possible character, that is to say for every number between 0 and 255.

While the size of a code cannot exceed 256, it is possible to encode every character with a code of size 8 at most.

However, it is impossible that the algorithm generates a code of size 256 because then the codes wouldn't be optimal. It will give to the most likely chars, codes of size < 8 and it will give codes of size > 8 to the others (intuitively).

My question thus is, how can we get an upper bound of the maximum size a code can have, better than 256? I don't see how to approach the problem.

PS: the upper bound I'm looking for doesn't depend on the probability distribution. It has to be an upper bound for every possible probability distribution. As I said, I doubt that there is a probability distribution for which there is a code of size 256, so there has to be an upper bound.

I think I found the solution: For an alphabet of size $n$, the longest possible code is of size $n-1$, so here the answer is 255. So I was actually wrong in my intuition. You just need to arrange the weights so that each one is at least twice as much as the precedent and you get a Huffman tree which outputs a code of maximal size.


texts: Why is the complete state of a turing machine representable by a finite word?

texts:
At the moment I'm just reading through this article on the word problem for groups (https://projecteuclid.org/euclid.bams/1183548590), and I'm wondering about a certain snippet.
On page 40 the article describes a word that can encode the state of a turing machine, namely $S_{k_{u}}...S_{k_{1}}q_{i}S_{j_{1}}...S_{j_{v}}$ where $S_{k_{u}}...S_{k_{1}}S_{j_{1}}...S_{j_{v}}$ is the tape expression, $q_{i}$ is the current internal state of the turing machine, and $S_{j_{1}}$ is the currently scanned symbol.
I'm just wondering why this word is necessarily finite. Why can't the input of the turing machine have an infinite amount of non-zero characters?


texts: Pumping lemma for an involved non context free language

texts: Hi I'm trying to show $C=\{wzzw^R|w,z\in\{0,1\}^+\}$ is not a context-free language.( I have this believe because $C=\{ww|w\in\{0,1\}^+\}$ is not a context free language.) I'm really struggling to come up with a string that captures the essence of irregularity of this language: I tried strings like $s=1^p0^p1^p0^p1^p1^p$ but there are too many cases to deal with and most of the examples I saw only use 1 or 2 cases, so I believe the direction I'm going is wrong. Can you provide a hint on which string to pick as the 'pumping string'? Thank you.


texts: What is known about the sets enumerated by primitive recursive functions?

texts:
Let's say that a set of natural numbers $S \subseteq \mathbb{N}$ is primitive recursively enumerable if there exists some primitive recursive function $f$ such that $S$ is the range of $f$. That is, we can enumerate $S$ by calculating $\{f(0), f(1) \ldots \}$.

What is known about this class of sets? Where does it stand in terms of computability? I suspect that it contains sets that are not context free, and that it does not contain all recursive sets.

Has this been studied? Does anyone have a reference for this?


texts: Approximating the biggest acyclic subgraph of a given weighted digraph $G= (V,E)$

texts:
The base scenario is this: We're given a weighted, directed graph $G= (V,E)$, and are tasked to find an approximating algorithm which returns a digraph $G' = (V,E')$ (i.e. which only deletes edges) so that $G'$ is acyclic, and so that the sum of the weights of the remaining edges $\sum_{e\in E'} weight(e)$ is as big as possible.

Furthermore, the approximation shall be at worst half as good as the optimal solution (i.e. the sum of weights the approximation algorithm returns is at least half as big as the sum of weights of the optimal solution)

This is a homework problem, and I'm looking for hints how to solve it, as I can't seem to figure out any tactic to somehow compare the approximation algorithm ideas to any bound on the optimum solution.

I've come up with 4 ideas of choosing nodes/edges, from which 2 could go arbitrarily bad, and from which I believe 4) has the best chance of succeeding.

So far I have the following results:

1)
Using an algorithm to identify the strongly connected components, I can partition $G$ into a set of subgraphs (one for every strongly connected component), and solve for each subgraph individually (all edges between these subgraphs never create a cycle, and can always be taken into the solution).

2)
Using the tactic to iteratively identify a cycle and remove the one edge of it which has the lowest weight can go arbitrarily bad .

The optimal subgraph $\hat G = (\hat V, \hat E)$ has a topological sorting.
Therefore, there exists a numbering $v_1,..,v_{|V|}$ of the nodes so that with $T:= [v_1,..,v_{|V|}]$, the sum
$$\sum_{j=1}^n \sum_{ k=2}^j  weight(v_j\to v_k)
$$
is minimal. (The sum represents for each node $v$ in $T$ the weight of all edges $(v,v')$ that is lost because $v'$ appears before $v$ in the list, and thus there mustn't exist an edge $v\to v'$

Therefore, an approximation algorithm might guess the topological sorting of the optimal graph.

3)
Going from left to right, and always picking the node that brings with it the highest weight (as sum of its outgoing edges that are eligible) can go arbitrarily bad.

4)
However, so far I haven't found any counter-example for going from right to left, and always picking the node which loses the least weight.

For the last approach, we can show the following inequality:
Let $T:= [v_1,..,v_{n}]$ be the result of the approximation algorithm, then holds:
$$
 \sum_{k=1}^{j-1} weight(v_j\to v_{k}) \le \sum_{j=2}^n\sum_{k=2}^j weight(v_1\to v_k) = \sum_{j=1}^{n-1} (n-j)weight(v_1\to v_j)
$$


texts:
Does NP ⊆ Co-NP imply NP = Co-NP?

And also, does Co-NP ⊆ NP imply NP = Co-NP?

And does either statement imply P = NP?

Thank you very much in advance.


texts: Scheduling: Existence of specific total order

texts:
A question arising from a scheduling problem:
I have a finite set $X$ with elements $x_i$ and some preorder $\leq$.
I have pairs $p_j$ of $x_i$ (i.e. $p_j$ = $(x_k, x_l)$) with the property that $x_k \leq x_l$.
I say that for two pairs $p, p'$ : $p \leq p'$ when for all $x \in p, x' \in p': x\leq x'$.
I call two pairs $p = (x_1, x_2), p' = (x'_1, x'_2)$ unrelated if for no $x \in p$, $x' \in p'$ holds: $x \leq x'$ or $x' \leq x$.

Question: Does there always exists a total order $\leq'$ of $X$ which is compatible with $\leq$, with the property that $p \leq' p'$ or $p' \leq' p$, for all unrelated pairs $p, p'$?

To give an example:

$X = \{1,2,3,4,5\}$ , $p_1 = (1,2), p_2 = (3,5)$ and a partial order (preorder) $1 \leq 2, 3 \leq 5$. E.g. by topological sorting I can obtain a total order ($ 1 \leq 2 \leq 3 \leq 4 \leq 5$) which satisfies $p_1 \leq p_2$. However, tsort can also give me the total order ($1 \leq 3 \leq 2 \leq 4 \leq 5$), which does not satisfy $p_1 \leq p_2$ or $p2 \leq p1$ (here, $\leq$ refers to the corresponding total orders).

The relation to a specific scheduling problem is that I have undetermined times $x_i$ at which I acquire or release a resource. To avoid deadlocks, the pairs of (acquisition, release) must not overlap.

(In the actual problem, some time $x_i$ can occur in multiple such pairs, but that's another problem not considered here).

UPDATE

I think I found at least some idea, yet not sure if it is correct:
The graph below shows the general structure of such a preorder (which we now treat as a directed acyclic graph): Given two such pairs $(x, x')$ and $(y, y')$, there is a path from $x$ to $x'$ (and from $y$ to $y'$). There may be nodes in-between, and edges connecting to that path. However, by our assumption that the pairs are unrelated, none of the incoming or outgoing edges in the section $x \to x'$ can reach $y$ or $y'$.
We can now start constructing a topological sort. Without loss of generality, we reach $x$ as the first node of all pairs which we consider (which is not necessarily unique, but that does not matter). Because there are no edges between $x$ and $x'$ which connect from/to another point $y$ from another pair, we can continue our topological sort until we reach $x'$. Then, the pair $(x, x')$ is "compact" in our final order, that is, will have a $\leq'$ relation to all other pairs (because no point of any other reservation is between $x$ and $x'$, by construction of the total order $\leq'$). We can repeat this procedure every time we reach the first point of such a pair.

Is there any flaw in this argument?


texts: can we do binary search to solve quadratic equation?

texts:
Suppose i have a quadratic equation like this, 2x^2 - 4x - 5 = 0, the solution here is x1=2.87 and x2=-0.87. I tried this python snippet to find the non-negative solution(2.87) by setting range 0 to 1000 and it worked but how to find the negative one too?. I tried the range -1000 to 0, but no luck!

def solve():
    low, high=0,1000
    while (high-low)>10e-5:
        x = (low+high)/2
        fx = 2*(x**2)-4*x-5
        if fx>0:
            high=x
        else:
            low=x

    return low

print(solve())

Or I am doing this whole thing wrong? What is the strategy to work with negative ranges and floating numbers in binary search?


texts:
I'm trying to figure out the intuition on creating a CFG in my head. I understand the idea of Grammar rules akin to "onions" with various layers throughout. For example, I was working on a problem earlier where I was to construct a CFG of $a^ib^jc^k$ with $i \ne j$ OR $j \ne k$. Obviously I separated the problem into two parts, $i$ not being $j$ and the other part being $j$ not being $k$. Taking the left part into account I wrote out the  following:

$$\begin{align*}
S &\to aSbTc \mid aS \mid bT \\
T &\to bTc \mid bc \\
D &\to cD
\end{align*}$$
Am I correct in this for $i$ not being $j$ or is there something in my head thats wrong in thinking through this?


texts: Why does PCP theorem imply that NP problems are hard to approximate?

texts: What I only got currently from PCP theorem is that it needs at most $O(\log n)$ randomness and $O(1)$ query of proof to approximate. So how does this result relate to the fact that solution to NP problems are hard to approximate?


texts: Fastest algorithm to decide whether a (always halting) TM accepts a general string

texts:
Given a TM $M$ that halts on all inputs, and a general string $w$, consider the most trivial algorithm (Call it $A$) to decide whether $M$ accepts $w$:

$A$ simply simulates $M$ on $w$ and answer what $M$ answers.

The question here is, can this be proven to be the fastest algorithm to do the job?

(I mean, it's quite clear there could not be a faster one. Or could it?)

And more formally and clear:

Is there an algorithm $A'$, that for every input $\langle M,w\rangle$ satisfies:

If $M$ is a TM that halts on all inputs, $A'$ will return what $M$ returns with input $w$.
$A'$ is faster than $A$.


texts: How to find left-hand side of tape on a Turing Machine?

texts:
I am pretty new to Turing Machines and am trying to figure something out. So let's say I have a tape with input

0 0 1 0 0 1

The language is twice as many 0's than 1's. So first time through, I will mark an X on the first 1 I find. Then when I am heading back to the start of the tape, how do I know when to stop? Can you "run" off the left hand side of the tape?


texts: If $L$ is a regular language then so is $L/a =\{w | wa ∈ L\}$, where $L$ is a language over $\Sigma$ and $a \in \Sigma$

texts:
I'm trying to work out a proof by construction that $L/a$ would be regular.

$a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be changed is the set of accepted states ($F$)

I came up with the following definition of $F'$ for the new

$F' = \{q ∈ Q | \delta(q, a) ∈ F\}$

Where $Q$ is the set of states (the same for both machines), and $\delta$ is the transition function (also the same for both machines).
I believe this would make any state that has a transition to an accepting state in the first machine an accepting state in the second machine (including prior accepting states, if they have a self-loop).

Am I missing anything here? It seems suspicious to me that I would only need to modify the set of accepting states and not any other component.


texts: How to handle L-attributed SDDs with LR parsers

texts:
I've read Chapter 5, Syntax Directed Translation, of the Dragon Book but am still unable to understand the following related points:

How to handle L-attributed SDDs in an LR grammar when using a tool such as Bison? I believe, the book says that inherited attributes could be used with an LR parser (via Marker symbols?) provided the grammar is LL, or is (partly?) transformed into LL. Is this true? What if the grammar is LR and/or converting it to LL is not easy -- how do you then use inherited attributes?

If LR grammars are a proper superset of LL grammars and therefore more powerful, then how come LR grammars/parsers won't out-of-the-box allow L-attributed SDDs which, being a superset of S-attributed SDDs, are more powerful?

Avoiding the SDD style - Parsing style mismatch: Is it true that no matter the grammar (LL, LR, ...) or the parsing tool (Antlr, bison, yacc...), I can always first build the AST and then traverse it post-/pre-order any number of times to get whatever SDTs I want? (Ignore the time inefficiency here.)

Is there a text or online resource that covers topics 1 and 2 better or in more detail?


texts: Time Complexity: Why does $n^n$ grow faster than $n!$?

texts:
Seeing the title, you will probably like to give your explanation as

$n!=n\times (n-1)\times (n-2)\times (n-3)\times\cdots\times 1$

where as

$n^n$ = $n\times n \times n\times n \times\cdots\times n$ $\text{($n$-times)}$

but consider one thing: if we do $\log(n!)$ then it comes out to be $O(n\log n)$.

On the other hand, if we do $\log(n^n)$ it also comes out to be $O(n\log n)$. So, aren't they equal asymptotically?


texts: Derivatives involved in Bilinear interpolation

texts:
If we choose a unit square in which the four points where the function $f$ is known are as shown in the diagram the interpolation formula for $f$ is:
\begin{equation}
\begin{split}
f(x+u, y+v)\approx (1-u)(1-v)f(x,y)+u(1-v)f(x+\Delta x,y)\\
&\hspace{-7cm}+(1-u)vf(x,y+\Delta y)+uvf(x+\Delta x,y+\Delta y).
\end{split}
\end{equation}

The above formula is equivalent to the following Taylor expansion series
\begin{equation}
f(x+u, y+v) \approx f(x,y) + u \frac{\partial{f}}{\partial x}(x,y) + v\frac{\partial{f}}{\partial y}(x,y)+uv \frac{\partial^2{f}}{\partial x \partial y}(x,y).
\end{equation}

The derivative of $f$ w.r.t. $x$ is given by:

\begin{equation}
\frac{\partial f}{\partial x}(x+u,y+v)= \frac{\partial{f}}{\partial x}(x,y)+u\frac{\partial^2{f}}{\partial x^2}(x,y) + v\frac{\partial{f}}{\partial x\partial y}(x,y)+uv \frac{\partial^3{f}}{\partial^2 x \partial y}(x,y)
\end{equation}

In a previous post I stated the approximate derivatives as follows:
\begin{equation}
\frac{\partial{f}}{\partial x}(x,y)= \frac{f(x+\Delta x, y)-f(x,y)}{\Delta x}
\end{equation}

\begin{equation}
\frac{\partial^2{f}}{\partial^2 x}(x,y)= \frac{f(x+2\Delta x, y)-2f(x+\Delta x,y)+f(x,y)}{\Delta^2 x}
\end{equation}

\begin{equation}
\frac{\partial^2{f}}{\partial x \partial y}(x,y)= \frac{f(x+\Delta x, y+\Delta y)-f(x, y+\Delta y)-f(x+\Delta x,y)+f(x,y)}{\Delta x\Delta y}
\end{equation}

\begin{equation}
\frac{\partial^3{f}}{\partial^2 x \partial y}(x,y) = \frac{f(x+2\Delta x, y+\Delta y)-2f(x+\Delta x, y+\Delta y)+f(x, y +\Delta y)}{\Delta^2 x\Delta y}\\
\frac{-f(x+2\Delta x,y)+2f(x+\Delta x,y)-f(x,y)}{\Delta^2 x\Delta y}
\end{equation}

Is it true to say that the $\frac{\partial^2{f}}{\partial^2 x}$ and $\frac{\partial^3{f}}{\partial^2 x \partial y}$ are equal to zero?

Because we have to move $2\Delta x$ and bilinear interpolation involves 4 points.


texts:
I haven't done much algorithm writing till now. I have a specific scenario and I am wondering which approach shall I take.

Scenario:

Let us suppose that

we have 4 guys (A,B,C,D)
We want to assign them a certain task whose duration varies from 40 mins - 1 hr 15 mins.
The task duration varies depending on the number of people (1-6) which he needs to serve. (i.e 40 mins for 1 person and 75mins for 6).
Now we want to utilise these 4 guys(A,B,C,D) in particular time slots. let's say:

  06:30 to 11:00 & 16:00 to 22:00

I don't only want the code rather I would love to get some info about good algorithms which are best suited for this scenario following with some code.

All resources have equal efficiency. Efficiency is not much of our concern.
We can have any number of customers who are to be served. I'll try to explain this by one scenario:

  A,B,C,D are cooks(assume) who need to work during the mentioned time slots(6:30 to 11:00 & 16:00 to 22:00). Customers(as an individual or some group who are living together in a flat) can book the cooks to cook food for them. The cooking time (40 mins to 75 mins) is directly proportional to the number of people for whom it is being cooked. The customer should be able to register himself on some website and the website would allocate the resources(A,B,C,D) to the registered users accordingly.

Input:

How many people are enrolling for the service
Desired time slots

output

Available cooks as per the selected time slot

Update 2:

There can any number of cooks.
There can any number of customers with no relation to cooks.
Once a customer books any cook , its not compulsory that the cook has to serve in both(lunch & dinner) time slots. The customer can select opt for the same cook if he's(the cook) available or else the customer will be asked to select another cook who is available during that time


texts: Programming a genetic algorithm with a non-fixed size

texts:
I am trying to write a genetic algorithm for a program. Most examples for genetic algorithms use something like this as the input:

aaaaaaaaaa

and mutate/crossover until they get

helloworld

or similar. This requires however that you start with something of length N, but my search space doesn't have a fixed length. How should I alter the mutation/crossover steps to allow for changes in unit size?


texts: Knowing if I have an optimal ordering for a OBDD

texts:
I'm learning about OBDD and I have learned that the size of a reduced OBDD (ROBDD) is dependent on the ordering of the variables, and that finding an optimal ordering is an NP hard problem.

Say I already have one ROBDD by some ordering, I can, in some cases, determine if it optimal:for example if each variable appear only once (the optimality follows from the fact that a ROBDD does not contain variables that the formula doesn't depend on)

My question is this - Can I always tell if a ROBDD is optimal by some given relation ?

This would be true if a ROBDD must have each variable at most once (this is a claim I haven't managed to prove).


texts:
The following predicate logic formula is invalid (i.e. not a tautology):

$\Bigl[\forall x \,\exists y {\,.\,} P(x,y)\Bigr] \implies \Bigl[\exists y \, \forall x {\,.\,} P(x,y)\Bigr]$

Which of the following are counter-models (i.e. counterexamples) for it?

The predicate $P(x,y) \equiv  \bigl[ y \cdot x = 1 \bigr]$, where the domain of discourse is $\mathbb{Q}$.
The predicate $P(x,y) \equiv \bigl[ y<x \bigr]$, where the domain of discourse is $\mathbb{R}$.
The predicate $P(x,y) \equiv \bigl[ y \cdot x = 2 \bigr]$, where the domain of discourse is $\mathbb{R} \smallsetminus \{ 0 \}$.
The predicate $P(x,y) \equiv \bigl[y \,x \,y = x\bigr]$, where the domain of discourse is $\{0,1\}^\ast$ — that is, the
set of all binary strings, including the empty string).

Is my answer below true  ?

Answer:
I think the first model is not a counter model since 0 is a member of rational numbers there exists no rational y for which $x \cdot y = 1$. So $\forall x \,\exists y {\,.\,} P(x,y)$ is false, thereby validating the conditional for this choice of predicate $P$. Also sentence 4 is not a counter model. The other two are counter-models.


texts: is (infinitely often p) ∨ (infinitely often ¬p) valid?

texts:
i'm trying to prove every trace over PROP = {p} is a model of the formula.
I am very stuck in figuring out a model pi that satisfies this formula, can anyone point me in the right direction?


texts: There are parsimonious reductions between all NP-Complete problems: Well-known conjecture?

texts:
The reduction from SAT to Clique shows a way to construct a graph with cliques from a Boolean formula. A closer look at that reduction even yields a simple algorithm which finds a large clique in the graph from a given satisfying assignment to the variables. That mapping is bijective: each satisfying assignment is mapped to a different large clique, and the number of large cliques is the same as the number of satisfying assignments.

A reduction which preserves the number of solutions is called a parsimonious reduction (technical definition below). It is a stronger notion of reduction than the usual Karp reductions, because not all reductions have that property. NP-Completeness is usually defined in terms of Karp-reductions, but since parsimonious reductions are clearly more beautiful, it is natural to conjecture:

Conjecture: All NP-Complete problems can be reduced to one another via parsimonious reductions.

But I can't find this in the literature.

Question: Does the literature contain the conjecture that all NP-Complete languages can be reduced to eachother via parsimonious reductions?

This is different from the Bertman-Hartmanis conjecture that all NP-Complete problems can be reduced to eachother via polynomial-time invertible bijections. That conjecture is about instances of the language, whereas I talk about certificates to the NP machine. Of course the most beautiful thing would be a parsimonious bijection! References to that are greatly appreciated.

Definition If $L,K\subseteq\{0,1\}^\ast$ are languages and $f\colon\{0,1\}^\ast\to\{0,1\}^\ast$ is a reduction from $L$ to $K$, then we say that $f$ is parsimonious if there are polynomial-time nondeterministic Turing Machines $N, M$ accepting $L$ and $K$, respectively such that for all $x\in\{0,1\}^\ast$, $\#N(x)=\#M(f(x))$, where $\#N(x)$ denotes the number of certificates accepted by a non-deterministic Turing Machine on input $x$.

(The motivation for the question is that, for my thesis, I found that the reduction in the quantum Cook-Levin theorem is parsimonious. Beautiful! I want to conjecture that all quantum NP complete problems have parsimonious reductions, so I am looking for the classical reference)


texts:
I'm trying to count running time of build heap in heap sort algorithm

BUILD-HEAP(A)
heapsize := size(A);
  for i := floor(heapsize/2) downto 1
    do HEAPIFY(A, i);
  end for
END

 image by HostMath

 suppose this is the tree

   4    .. height2
  / \
 2   6  .. height 1
/\   /\
1 3 5 7  .. height 0

what I understand here $O(h)$ means worst case for heapify for each node, so height=ln n if the node is in the root for example to heapify node 2,1,3 it takes $ln_2 3 =1.5$ the height of root node 2 is 1, so the call to HEAPIFY is $ln_2 n=height = O(h)$

im not sure about this $\frac{n}{2^{h+1}}$ , is the number of nodes for any given height , suppose height is 1 and sum of nodes is 3 such as 2,1,3, so $\frac{n}{2^{h+1}}= \frac{3}{2^{0+1}}=1.5=2$ , when height is 0 there is at most two nodes. am i correct?

suppose given height is 0 so it is the last layer, then when sum of nodes is 7 , $\frac{n}{2^{h+1}}$ =$\frac{n}{2^{0+1}}$=$\frac{7}{2}=3.5=4?$ -> {1,3,5,7} if the root is 4

the summation is lg n because it sum the total height when it do heapify?

and last is to count the big-oh, BUILD HEAPIFY will call HEAPIFY $\frac{n}{2}$ times, and each will be $ln_2 n$ = height of the root, so $O(\frac{n}{2} * ln_2 n)$ ?

please correct me if i am wrong thanks!

https://www.growingwiththeweb.com/data-structures/binary-heap/build-heap-proof/
this is the reference i used, and also i read about this in CLRS book


texts: Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$

texts:
Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there is a feasible solution that is $k$-sparse, i.e. there are only $k$-nonzero elements in $x$?

What about if we know an upper bound on the $L_1$-norm of the solution  $|x|_1\le B$. Would it be possible to answer the system has a sparse solution in polynomial time?

P.S. I'm aware of this question, but the answer does not address whether this approach always finds a feasible solution in polynomial time.


texts: In lieu of neural networks and deep learning, what are some approaches to computer vision?

texts:
So much software related to computer vision relies on AI and neural networks, I wonder some of the approaches which don't use those methods. How could some of the mainstays of computer vision (eg. recognition and identification) be achieved without "artificial" means?

I'm reading Vision by David Marr and it talks about the human visual system model and how it could be emulated algorithmically for computer vision. I know of salience mapping and edge detection algorithms which there's significant consensus that the brain processes visual information in a manner not too dissimilar to, but what other methods are there?

Consider something such as facial recognition: I have a headshot of hundreds of individuals, how could a system recognize if a new face was novel or previously recognized without neural networks or deep learning? My interest is in white-box approaches to computer vision rather than these black-box approaches.


texts: Question about proof of Lemma 2.41 - Sipser book

texts:
Doesn't the modification described in paragraph three potentially introduce non-determinism? For example, say neither a, b, x, nor y is the empty string (denoted e). If in the original machine P we have:

f(q, e, x) != null
f(q, a, y) != null
f(q, b, y) != null

wouldn't the modification give us:

f(q, e, $) != null
f(q, a, $) != null
f(q, b, $) != null


texts: A robot arm consisting of a sequence of rigid line segments L1, L2, . . . , Ln hinged together consecutively

texts:
Hi I am a Computer Science student attempting to solve this problem for extra credit. Problem is I am unsure what this algorithm is asking for as the language is a bit hard for me to follow:

  Imagine that you have a robot arm consisting of a sequence of rigid
  line segments $L_{1}, L_{2}, \dots , L_{n}$ hinged together
  consecutively. The lengths of the line segments $l_{1}, l_{2}, \dots ,
> l_{n}$ are positive integers. You may rotate freely around the hinges
  and the line segments are allowed to cross over. Our goal is to pack
  in the line segments into one line segment as compactly as possible.
  More precisely, given positive integers $l_{1}, l_{2}, \dots , l_{n}$
  (and $l_{0} = 0)$ and a sequence of
  $\pm1$’s, $s_{0}, s_{1}, \dots , s_{n}$, where $s_{i} = 1$ or $s_{i} = −1$, $0 ≤ i ≤ n$, define

  $$m_1 = \min_j\left(\sum_{i=0}^j s_il_i\right) $$
  $$m_2 = \max_j\left(\sum_{i=0}^j
s_il_i\right) $$
  where ($0 ≤  j ≤ n$).
  Find $\min_s (m_{2} − m_{1})$, where the minimum is taken over all sequences
  $s = (s_0, s_2, \dots , s_n)$.

The goal is for me to write an algorithm that solves this problem. But I am not entirely sure what the question is asking. My understanding is drawn below:

The arms shall be compacted as much as they can be such the vertical height of the extended arm is minimized. But I don't understand what the $s_0, s_1,\dots, s_n$ sequence is for? And if someone could describe in layman's terms what the sequences $m_1$ and $m_2$ are asking for that would be great.


texts:
filter() in functional programming can be thought of as being analogous to an equation that filters the range of the variable.

map() can be through of as a function mapping domain to codomain.

reduce() is the only one I have a problem with. To me it just seems to be a special instance of map / function, where $R^{n} \rightarrow R^{1}$.

Is there a unique general mathematical concept / object associated with reduce()?


texts:
Consider the following complexity class $IP^\star$, a variant of $IP$.
  A language $L$ is in $IP^\star$ if there's a proof system $(P,V)$ s.t.
  $V$ is a verifier runs for a polynomial time and:

  $$x\in L \implies Pr[(P,V)(x) = 1] \ge 3/4 \\ x\not\in L \implies
> Pr[(P,V)(x) = 1] = 0 \\ $$

  Prove that $NP = IP^\star$.

  Note: in this definition as far as I understand, we have a single $P$
  (for both cases).

Now, one side is easy ($NP\subseteq IP^\star$), since by definition $NP$ language has a perfect polynomial-verifier - so we're satisfying the demands.

The other side is the tricky one. Consider a language $L\in IP^\star$. We want to show that $L\in NP$. Obviously we shall utilize $V$ somehow.
The certificate could be the "conversation" between $V$ and $P$. Then our $NP$ TM could simulate the conversation between $P$ to $V$.

Yet, that's alone isn't good enough - we have a $1/4$ probability to make a mistake if $x\in L$.

Amplifying the probability isn't good enough too. We need perfect soundness.

So maybe we shall use the non-determinism of our machine somehow?


texts: Number of spanning arborescences with a specific root in a directed graph

texts:
I am wondering how to calculate the number of spanning arborescences in a directed graph when a root is specified. For example:

where there are 5 spanning arborescences. Note that there is an edge from b2 to b3 and one from b3 to b2.
Angela Pretorius mentioned a method in Number of Spanning Arborescences, Mathematics, but there is no euclidean circuit in this example. It seems that he/she is referring to BEST theorem.


texts: Predicate Logic Notation: What does a "dot" mean?

texts:
What does a dot (.) mean in predicates?

$\forall a \in A. \exists d \in D. H(a,d)$

Especially, how is the above different to

$ \exists d \in D. \forall a \in A. H(a,d)$

I've never seen this used in German lecture scripts.


texts: How to simulate this randomized "finite" sum?

texts:
Consider the the Geometric Brownian motion

$\qquad dX_t=\mu X_t dt+\sigma X_t dW_t$, with $X_0=1$, $\mu=0.2$, and $\sigma=0.30$.

for each $n=1,2,3,..$ let $h_n=1/n$, and let $X^n_n$ be the final value of the discrete process obtained from Euler scheme wrt $h_n$, i.e.

$\qquad  X^n_{k+1}=X^n_{k} +\mu X^n_k h_n +X^n_k \sigma \sqrt{h_n} \text{randn}(0,1),$

for $k=0,1,2,\ldots n-1$. Here $\text{randn}(0,1)$ means the standard normal random variable with mean 0, standard deviation 1.

That is, after using Euler scheme ,for each $n=1,2,3, \ldots$ you have a sequence  (which depends on $n$)

$\qquad \{1,X_1^2, X_2^n,\ldots, X_n^n \}$.

For simplicity assume that $F_n\equiv X_n^n$.

I do know how to find $F_n$ for $n=1,2,\ldots$.

Assume that $N\sim \text{Geometric}(p)$, i.e, $P(N=k)=(1-p)^{k-1}(p)$ ( let assume $p=0.5$ here for simplicity), for $k=1,2,3,\ldots$.

My question here is:

How to simulate this sum

$\qquad Y=\sum_{k=1}^{N}\frac{(F_{k+1}-F_{k})}{2^k} N^2 $?

Using geornd(p) provided by matlab, I do know how to generate $N$.
How to approximate $E(Y)$?

My confusion comes from here. There are random variables floating around here: $N$ and $F_{k+1}-F_{k}$. Assume that $N$ and $F_k$ are independent, so we have

$\qquad E(Y)=\sum_{k=1}^{\infty}\frac{E[(F_{k+1}-F_{k})]E[N^2 I_{k\leq N}]}{2^k} $.


texts: Regex vs line by line read efficiency - general concept question

texts:
Say, I have a file that is somewhere between 10-20 pages long. I need to extract 10-20 pieces of information from it that I can fairly easily extract using a series of regex-es or by running code that reads things line by line and extract information that way. Is there a way that is necessarily faster than the other?

I know that regex are generally faster for searching things. But the uncertainty I have here is more like, if I use a regex approach, I virtually have to run regex on the text multiple times, whereas if I were reading it line by line, I would basically be only reading everything only once. I wonder if there is a general principal or maybe just some rule of thumb that one way is better than the other. Is there something like that? Or will it be so scenario dependent that I really won't know the answer without doing testing each time I have something like this?


texts: Does an FPTAS imply a problem is FPT for a specific parameter?

texts:
I don't understand the exact relation between between FPT and FPTAS. Specifically, given an optimization problem P with fptas A does that imply that for any parameter (a computable map from the input to the integers) there is an FPT algorithm? It's standard that given an FPTAS, there is an FPT algorithm parameterized by the solution cost. (see: Why are all problems in FPTAS also in FPT?).

Does the existence of an FPTAS have any bearing on the FPT status of a problem with given (i.e. not necessarily solution cost) parameter k? Thanks.


texts: Is the consensus number of SetAgree(3, 2) 2 or 1 (proof needed)?

texts:
SetAgree(n, k)

An object that allows n threads to propose() n values.
It guarantees Each thread will decide() on a (single) value.
The cardinal number of the set of all values decided on is lower or equal to k.
All values decided on were proposed.

It is obviously trivial if n <= k so the first interesting case is SetAgree(3, 2).

Consensus(n) is the same as SetAgree(n, 1).
A consensus number of an object is the highest number of threads that can arrive at a consensus using that object and shared memory access.

Alright, I'll start by saying I think the consensus number of SetAgree(3, 2) is not two.

My line of proof is that I assume there is a protocol that solves a binary consensus(2) using the strongest SetAgree(infinity, 2).

At some point in the algorithm (which has to be deterministic) we arrive at a node where if thread A acts, the consensus will be its proposal (without loss of generality 1) and if thread B acts, it will be its proposal (without loss of generality 0).

Lets say, both of them wish to access the SetAgree object at this node, they could get the values they proposed no matter the order of access they use so the state of the system will be the same (no matter the order). If only one of them accesses the object and the other one reads or writes to a memory register then the order is meaningless for sure simply because memory doesn't affect the SetAgree object and SetAgree doesn't affect any of the shared memory registers. So obviously regardless of the order, the state of the system will be the same after these two operations which means, it is not possible that one leads a consensus on (1) and the other on (0).

The line of proof that suggests consensus number 2 states (the known fact) that setAgree(3, 2) cannot be build with shared memory alone. This is well known but it doesn't suggest setAgree(3, 2) has a stronger consensus number cause that line of proof only applies to data structures, cause it relies on universal construction.

Is there any stronger proof that it's consensus number 1 or 2?


texts: AI Search - State in the toy vacuum problem

texts:
I have been reading about AI search, specifically the toy vacuum cleaner problem and I would like to code an example of this but I am finding the description of the state hard to get my head around.
The problem states that the AI needs to be able to move between squares, either left or right and if there is dirt in the square it can clean it (suck).

Is the state something you are supposed to hard code in advance in AI search? This seems unlikely due to the possible number of potential states for a larger problem, so I am not sure how I can represent the state in a problem like this, or any other really.
In the vacuum problem the states are 'dirt left', 'dirt right' and 'vacuum position' and an action such as 'move left', 'move right' or 'suck' will leave the problem in a new state but how do you represent these changes?
Would state be an object with boolean properties for the dirt and an int value for the vacuum position of either 0 or 1 depending on which array element it is looking at?
In the context of a map program trying to get to somewhere I do understand the state might be In(New York) but I what I am struggling with is how I would represent something like that in code, or perhaps a maze where the current state might be the x, y coordinate of the square the agent is currently in, again would an object be the right thing to use to model state?


texts: Update existing clusters to satisfy distance and volume constraints

texts: I have a massive distance matrix of clusters. The distance matrix is the distance between each cluster. I now need to recluster each entity based on two constraints. Each cluster has an associated volume.  The constraints are a max volume and min distance. I want to scan for the minimum distance and if neighbor cluster falls within this minimum distance AND if the summation of the volume does not exceed max volume, then that forms a new cluster. I want it to do this for all clusters. I’ve been struggling with creating an algorithm for this. Is there any algorithm that can help?


texts: Context-sensitive grammar for the language of words concatenated with themselves

texts:
I'm looking for a context-sensitive grammar that describes the following language:
$L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\}$ .

I've got problems with the fact that no rules such as $X \to \varepsilon$ are allowed and therefore I can't place any nonterminal indicating the "middle" of the word. Is there any trick to the problem?


texts: Show that exist a finite set of clauses F in first-order logic that Res*(F) is infinite

texts:
I'm kind of desperate at this point about this question.

A predicate-logic resolution derivation of a clause $C$ from a set of clauses $F$ is a
sequence of clauses $C_1,\dots,C_m$, with $C_m = C$ such that each $C_i$ is either a clause
of $F$ (possibly with the variables renamed) or follows by a resolution step from two
preceding clauses $C_j ,C_k$, with $j, k < i$. We write $\operatorname{Res}^*(F)$ for the set of clauses $C$
such that there is a derivation of $C$ from $F$.

The question is to give an example of a finite set of clauses $F$ in first-order logic such that $\operatorname{Res}^*(F)$ is infinite.

Any help would be appreciated!


texts:
I have used Rabin Karp Rolling Hash for searching a pattern $P$ in a text $T$. Now I am allowing $k$-mismatches, but not able to do a faster implementation.

I tried modifying RK algorithm by splitting the pattern into few blocks, but that does not improve the speed.

I'm trying to use locality sensitive hashing, but not sure how could I calculate hash with sliding window manner. Any help would be appreciated. For my case, the length of $P$ is 50~75 and $T$ is 100~150.


texts:
While I was learning about time complexity of recursive functions, I came across this code to calculate $x^n$:

power (x, n) {
    if n == 0
        return 1
    if n is even
        return power(x, n/2) * power(x, n/2)
    if n is odd
        return power(x, n/2) * power(x, n/2) * x

According to the book, its complexity is $\Theta(n)$ which seems rather strange to me. In my eyes, this code should have complexity $\Theta( n^2)$.

What am I seeing wrong?


texts: Is it true that if we replace in the Dijkstra algorithm + with max, then the resulting algorithm correctly solves the problem of finding the shortest paths where the length of the path is measured as the maximum of its edge weights?


texts: Deriving the exact number of execution times

texts:
So I'm studying for my data structures midterm and my professor gave out a sample midterm with the answers, but I'm having a hard time understanding one of the questions.

Here's a screen cap:

The answer is n^2(n+1)/2.

I would appreciate a very simple walk through and/or a pointer to some good material.


texts: Sorting an array of strings by length in linear complexity

texts:
I am trying to find an algorithm to sort an array of strings by length in O(n) time complexity, and O(1) space complexity.
The max length of the strings is known.
Because of that, I tried using counting sort, but I failed to do in O(1) space complexity. Because multiple strings might have the same length, I need to store the strings in some kind of 2D array for each possible length, and that is O(n) space in the worst case of all strings having the same length.
How would I go about solving this problem?


texts: Language of all words accepted by a TM by at most $t$ steps is regular

texts:
Let $M$ be a Turing machine, $\Sigma$ an alphabet, $t \in \mathbb{N}$

$L = \{ w \in \Sigma^* : w$ is accepted by $M$ by at most $t$ steps$\}$

I want to show that $L$ is regular.

My attempt:

I'm trying to do this directly by constructing a DFA for $L$.

Let $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$

Define $\Gamma_0 = \Gamma \cup \{\sqcap\}$ where $\sqcap \notin \Gamma$.

Set $Q_0 = Q \times \Gamma_0^{t+1} \times \{i\}_{i=1}^{t+1}$ a finite set.

For $q \in Q$, $(a_1,..,a_{t+1}) \in \Gamma^{t+1}$, $1 \leq i \leq t+1,$ $b \in \Sigma$:

Say that $\delta(q, b) := (q_1, b_0, R $ or $L)$ and that $\delta(q, a_i) := (q_2, a_0, R$ or $L)$. We define $\delta_0: Q_0 \times \Sigma \to Q_0$ by

$\delta_0(q, (a_1,..,a_{t+1}), i) =
  \begin{cases}
    (q_2, (a_1,..,a_0,..,a_{t+1}), i+1)       & \quad \text{if } R \text{ and }a_i \in \Gamma\\
    (q_2, (a_1,..,a_0,..,a_{t+1}), i-1)       & \quad \text{if } L \text{ and }a_i \in \Gamma\\
(q_1, (a_1,..,b_0,..,a_{t+1}), i+1)       & \quad \text{if } R \text{ and }a_i = \sqcap \\
(q_2, (a_1,..,b_0,..,a_{t+1}), i-1)       & \quad \text{if } L \text{ and }a_i = \sqcap\\
  \end{cases}
$

Where the  change of letter in the $t+1$ tuple occured in the $i^{th}$ spot.

**Edit: also make the machine loop upon entering the accept or reject states

Then consider the DFA $A = (Q_0, \Sigma, \delta_0, g_0, F)$ where $g_0 = (q_0, (\sqcap,...,\sqcap), 1)$ and $F = \{(q_{accept}, x, j) : x \in \Gamma_0^{t+1}, 1 \leq j \leq t+1\}$

Now intuitively I think that this machine accepts $L$, but am having a hard time proving it.

So, is it true that $L(A) = L$? If so can you point some directions on how to prove it?


texts: Prove an arithmetic property of a partial recursive function

texts:
I have this program written in haskell :

I have to prove that:
    $(\forall a \in \mathbb{N})[!D_V [h](a) \Rightarrow log_2 (D_V[h](a) )\equiv 2  (mod$ $ 10) ]$.

The predicate $P_2$ for the $g$ function is obvious :
$P_2(f,g) \equiv (\forall x,y \in \mathbb{N})[!g(x,y) \Rightarrow g(x,y)\backsimeq xy]$.

But the predicate for the function $f$ which would give me authomaticaly the one for $h$ I have no idea what it should be.

Any ideas and help in solving this problem is welcomed :)

Notations:

$D_V[h]$: denotational semantics with passing by value of the function $f$.
$!F(x)$ means that $F$ is defined at point $x$.
$F(x) \backsimeq V$ means has the value $V$ at the point $x$ or is undefined.


texts: Why don't people use Fermat's little theorem to check if number is prime?

texts:
There're a lot of examples of code for checking if a number is prime. Why don't people use Fermat's little theorem, i.e. this simple formula

$\qquad a^{p-1} \equiv 1 \pmod p$,

to check if a number is prime?


texts: Find largest subset of vertices in graph so that every pair of vertices have an edge between them

texts:
Let's say you have a graph like this:

The largest subset of nodes so that every pair of vertices have an edge between them is $\{3, 5, 7, 12\}$. The second largest subsets are

$\{4, 7, 21\}$,
$\{3, 5, 7\}$,
$\{3, 5, 12\}$,

etc.

Is there an algorithm to find the largest subset efficiently?

Also, keep in mind that I know virtually nothing about graphs (haven't learned at school, haven't taught myself). The data was originally given as a set of pairs of numbers.


texts: Are there any NP complete problems in SUB EXP TIME?

texts:
Generally most np complete problems seem to have the best strategies operate in time $O(c^n$) for some choice of $c$

Has something like $O(2^\sqrt{n})$ (or any other less than exponential but greater than polynomial running time) ever been encountered in the wild as a run time for an algorithm that solves an NP complete problem?


texts:
I'm a beginner learning about Assembly language and I was doing questions where I have to identify different addressing mode in 8086 processor.
One such instruction is:
mov ah,09h
Here the source operand has immediate address mode and destination operand has Register address mode.
In many tutorials online they have just mentioned that the instruction has only Immediate addressing mode, I don't understand why these tutorials do not mentioned about the destination addressing mode.
Shouldn't the answer be both immediate and register addressing mode for the given instruction.
I know it is a very simple question but every other explanation on the internet is making me more confused. I would really like to know if my reasoning is correct.


texts: In the Data Link Layer, is it better to use large or small frames?

texts:
I understand how the layer works to an extent, but cannot seem to figure out if the data link handles big frames more efficiently due to error detection or small frames better.

I am assuming from my understanding that the data link works better with small frames as it can save time by not having to keep retransmitting larger frames when an error is detected.

Is this reasoning correct?

Havent used stackexchange in a long while so apologies if these type of questions are no longer permitted


texts: Unrecognizability of functional variant of halting problem

texts:
Let $L_0 = \{ \langle M, w, 0 \rangle \mid M \text{ halts on } w\}$ and $L_1 = \{\langle M, w, 1\rangle \mid M \text{ does not halt on } w\}$.
In $\langle M,w,i \rangle$, the $i$ indicates a specific bit such as $0$ for language $L_0$ and $1$ for language $L_1$.
I want to prove that $L = L_0 \cup L_1$ is unrecognizable and so is $\overline{L}$.
I think: the halting problem $\{\langle M,x \rangle \mid M \text{ halts on input } x \}$ is recognizable, that is, given a machine $M$ and a string $w$, I can always get acceptance if $M$ stops on $w$ by simply running it.
Assume that $L_0$ and $L_1$ are recognizable, that is, there are machines $M_0$ and $M_1$ such that $M_0$ accepts $x \in L_0$ and halts, $M_1$ accepts $x \in L_1$ and halts. Then to recognize $x \in L_0 \cup L_1$, we can have a hypothetical $M_\cup$ that can recognize (not decide) $L_0 \cup L_1$:

we can run $\langle M, w, 0 \rangle \in L_0$ on $M_0$
and $ \langle M, w, 1 \rangle \in L_1$ on $M_1$

So:

If $M_0$ stops we know $M$ halts on $w$ and
if $M_1$ stops we know $M$ does not halt on $w$

(Note that any $x \not \in L_0 \cup L_1$ will lead to divergence on these two machines. That’s why $M_\cup$ can only recognize $L_0 \cup L_1$ and cannot decide.)
Thus we have solved the halting problem: for any $M$ and $w$, $M_\cup$ will accept and halt for both

$M$ halts on $w$
$M$ does not halt on $w$

This is a contradiction (halting problem is undecidable) and so both $M_0$ and $M_1$ cannot exist simultaneously. This proves that $L = L_0 \cup L_1$ is not recognizable.
For the $\overline{L}$ case: $\overline{L} = \overline{L_0} \cap \overline{L_1}$. As stated previously, $L_0$ is recognizable and $L_1$ is not recognizable (“no Turing machine can recognize all Turing machines that never halt”: Corollary 2 here).

$\overline{L_0}$ is not recognizable
$\overline{L_1}$ is recognizable
$\implies \overline{L}$ is not recognizable

Is this a valid chain of arguments for this proof?


texts:
Consider the gate used in Simon's Algorithm. It operates on a control register and target register, changing state like: $|\textbf{x}\rangle|\textbf{y}\rangle->|\textbf{x}\rangle|\textbf{y}\oplus f(x)\rangle$.

As I am working on an universal way to simulate operations on qubits, I've been using a matrix representation of gates, which allowed me to transform even pretty complicated states without much concern about transform's correctness. However, I can't really see how would I represent a gate like shown above with a matrix (or how would I build such a matrix knowing x, y and f(x)?)

How can such gates operating on multiple qubits be represented with matrices?

Alternatively, having a vector states representing x and y and knowing f how can I transform y? (If all qubits in x are set in equally-weighted superposition of 0 and 1, I guess I'd need to calculate f for all possible x states, but how should I apply the results to y then?)


texts:
I am having a very difficult time trying to understand what exactly this question is asking.

  How many valid English plaintexts are there for the ciphertext message CJU using a length-3, one-time pad of cyclic shifts, (i, j, k)?

If the encrypted question message is CJU and the one time pad is i, j, k would there not be exactly 1 solution? We are given the one time pad i, j, k so we can derive the plaintext simply by some alagebra

(x + 9) % 26 = 3

(y + 10) % 26 = 10

(z + 11) % 26 = 21

Where x, y, and z are the plaintext letters T, Z, J?

I feel like this is a trick question that I am not understanding


texts:
Given a board of size $n \times 1$ where $n=\infty$ (basically a tape, one way infinite), and a set of colors $C$, some starting color $c_{start} \in C$, a set of templates $T$ in a form $(c_k, i, c_i, j, c_j)$ (meaning if on some position on the board there is a color $c_k$ then $i$ steps to the right of $c_k$ there is a color $c_i$, and $j$ steps to the right of $c_i$ there is a color $c_j$).

Prove that if we put $c_{start}$ on the board in position $(1,1)$ (furthest to the left), the answer to the question below is PSPACE-hard

  Can we fill the board with $c \in C$ in such a way that we use all the elements from $T$?

I attempted to reduce TQBF to this problem, however if I construct a gadget where I say that each variable is a color, I have a trouble encoding $i$ and $j$ with clauses. Also, I'm not sure if it's the right direction (maybe try reducing from GG? but I would have the same problem).

Any help is appreciated.


texts: Are there some popular science videos on computer algorithms to recommend?

texts:
I am seeking for some popular science videos on computer algorithms for my last lecture delivered in this term. The topic of the videos includes but are limited to algorithm design, algorithm analysis, computational complexity, the application of algorithms, the history of algorithms (even computer science), the story about the people working on the field, and so on.

By ``popular science videos'', I am just ruling out the videos which are focusing on some specific theory and targeted at a special interest group. It will be better to meet the following specifications (not mandatory):

produced by known university
produced by known corporation, like BBC
film or record, not just a speech given by one person
lasts for more than half an hour
amusing

Any recommendation will be appreciated.


texts: Measure divergence in Particle Swarm Optimization

texts:
I'd like to monitor divergence/diversity in my swarm during the particle swarm optimization algorithm to measure when the swarm search space is converging.
This would be used as one metric to be recorded during the run and potentially to terminate the PSO process when not much further progress is to be expected.
Is there a common metric for measuring PSO swarm divergence?


texts: Meaning of the constants that appear in the Master Theorem

texts:
The general formula for time complexity is $T(n) = aT(n/c) + bn^k$.

If $a> c^k$, the complexity is $O(n^{\log_c a})$.
If $a = c^k$, it is $O(n^k \log n)$.
If $a < c^k$, it is $O(n^k)$.

$a$ is the amount of times the recursive function is called, but what do $b$, $c$, and $k$ represent?


texts: Can other models of computation equivalent to Turing machines also recognize the same languages?

texts:
There are other models of computation equivalent to Turing machines in terms of computability.

Turing machines also recognize recursively enumerable languages.

My questions are

Do other models of computation equivalent to Turing machines also recognize the same languages?
Are computability and language recognization unrelated to each other, so that other models of computation equivalent to Turing machines don't recognize or accept any language?

Thanks.


texts: Maximum set of equalities, subject to some inequalities

texts:
I have $n$ variables $x_1,\dots,x_n$.  I'm given a set $E$ of equalities (each of the form $x_i=x_j$ for some $i,j$) and a set $I$ of inequalities (each of the form $x_i \ne x_j$ for some $i,j$).  I want to find a maximum-size subset $E' \subseteq E$ such that $E'$ is compatible with $I$, i.e., such that there is an assignment to the $n$ variables that satisfies every inequality in $I$ and every equality in $E'$.

Is there an efficient algorithm for this?

I can see that the greedy algorithm (try adding equalities to $E'$ as long as doesn't imply the negation of some inequality) doesn't yield an optimal solution.  I have no idea what other approaches to try.

Equivalently, the problem can be formulated in graph-theoretic terms.  I'm given an undirected graph $G=(V,E)$ and a set $I \subseteq V \times V$.  I want to find a maximum-cardinality subset $E' \subseteq E$ of edges, such that when I decompose the graph $G'=(V,E')$ into connected components, $v,w$ are in different connected components for all $(v,w) \in I$.


texts: Maximum cut using a 1/2 approximation greedy algorithm

texts:
I have the following greedy algorithm for max cut problem:

Initialization: $A \leftarrow \{v_1\}$ , $B \leftarrow \{v_2\}$
For $v \in V − \{v_1, v_2\}$ do:

if $d(v,A) \geq d(v,B)$ then $B \leftarrow B \cup \{v\}$,

else $A \leftarrow A \cup \{v\}$.
Output $A$ and $B$.

Here, $v_1$ and $v_2$ are arbitrary vertices in $G$ and $d(v,A)$ denotes the number of edges between vertex $v$ and set $A \subset V$.

To show that this is a factor 1/2 approximation algorithm, I used the upper bound that $opt \leq |E|$ and internal_degree(v) and external_degree(v).

But there is a problem, I can not say that when the algorithm terminates, we have external_degree(v) $\geq$ internal_degree(v) for all v (there is a counterexample) , of course since each vertex is check once so time complexity is O(n).

Is there any other way to show this factor?


texts: Resources on Dynamic Programming with Indefinite Recursion

texts:
I am trying to explain the value iteration method that is used in reinforcement learning. The method is used to estimate a solution to a recursive equation like:
$ Return(state_t,action_t) = Reward(state_t,state_{t+1}) + \gamma * \max \begin{bmatrix} Return(state_{t+1}, action_{t+1}=='n')\\ Return(state_{t+1}, action_{t+1}=='e')\\  Return(state_{t+1}, action_{t+1}=='w')\\  Return(state_{t+1}, action_{t+1}=='s') \end{bmatrix}$
Normally, if the sub-problems(RHS) are overlapping, a problem like this can be solved using recursive or iterative dynamic programming. However, in the case of reinforcement learning the recursion is often mutual, and thus the dynamic programming solution has no natural point of termination.
The value iteration method works by filling up the memorization table with arbitrary values and then repeatedly applying the recursive equation to every cell in the table until the values in the cell converge.
A similar approach is used in the HITS algorithm where the hub and authority values have mutual recursion.
Are there any good resources, preferably online, that deal with the application of dynamic programming to problems with mutual, indefinite recursion?


texts: Longest path in DAG or finding DAG diameter

texts:
A directed acyclic graph (DAG), is a directed graph with no directed cycles.

That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way to start at any vertex v and follow a consistently-directed sequence of edges that eventually loops back to v again.

we have several algorithms to finding shortest path from one vertex to another(Dijkstra algorithm and Bellman-ford algorithm)
or such algorithms to find shortest path from every to vertices( floyd-Warshall algorithm and Johnson algorithm)

But which method could help us to find the maximum path between all two vertices and pick the maximum one as graph Diam.

here we have a DAG so there is no cycle with
Positive edge weight to drop in infinite loop for finding longest path. and we could use many other features in DAG.

Is any polynomial time order algorithm for this problem....?

thanks


texts: Ordering the incident edges of each vertex to have a specified pre-order traversal

texts:
Input: You are given a graph $G(V, E)$ undirected, loop-less, no parallel edges, etc. and a label function $L: V \to \mathbb{N}$. Also, a sequence of $|V|$ natural numbers is given.

Output: Is it possible to order the incident edges set of each vertex and choose a starting vertex $s \in V$ so that a pre-order DFS traversal starting from $s$ prints out a sequence of labels of visited vertices which matches the given sequence.

Any idea on this problem? It is solvable on trees by Dynamic Programming. But for general graph, it seems to be much harder.


texts: Deadlock avoidance: How does the system know in advance about the number of resources required by a process?

texts:
While studying about Deadlock Avoidance I came across a paragraph which states as given below:

  When the system needs to issue any resource to any process, then in making this decision the system must consider the resources currently available, the resources currently allocated to each process, and the future requests and releases of each process.

So my question is that how can the system know in advance about the number of resources that a particular process will require/request in future?


texts: Does the order of ripping off the states matter?

texts: Do we get same regular expressions at the end regardless of the order that we take the states step by step? Can somebody prove by exemplification?


texts: When can a deterministic finite-state-automaton (DFSA) along with its input sequence be said to be a part of another DFSA?

texts:
For a Finite State Automaton / Finite State Machine (FSM) $F$, that has an input alphabet, a set of possible states, an initial state, a set of possible final states and a state transition function, let a finite input sequence $S$ is given, such that at the end of this sequence the FSM enters a final state and stays in that state.
Can this FSM $F$ along with the input sequence $S$ be considered a separate FSM $F'$?
Analogous to this, can a Turing machine $T$ along with a finite tape $P$ be considered a separate Turing  machine $T'$?
What are the conditions, if any, for this to be true assuming it is true?
Note: I expect a formal proof, or a reference/outline to a formal proof that proves that either of this can or cannot be done. Some theory related to this is also welcome.
My research:
Closely related topic:
R. T. G. TAN (1979) Hardware and software equivalence, International Journal of Electronics, 47:6, 621-622, DOI: 10.1080/00207217908938690

I am aware of the principle of hardware and software equivalence, which states that a given task can be performed using hardware or software, i.e. digital hardware and software are equivalent models of computation. But I think my question is different from this one.
Motivation:

From this question (
Is there code below microcode? ) I think we can consider an FSM with its input sequence (microcode) to be a part of another FSM (the digital computer), but of course much more circuitry like Arithmetic and Logical Unit (ALU) and datapath is needed to make a computer. Microcode is used only for the control circuit.

This answer claims the data in the RAM of a computer along with the CPU can be considered to be a part of a bigger circuit.

To quote:

The circuit is fixed (it is the gates in the processor) and part of its input is data that depends upon the program you are executing (which is stored in the RAM of the computer). However, you could consider this a larger circuit where part of it is hardcoded (i.e., the program part of the input is hardcoded); then you can view a computer running a program as a big circuit with part that is universal and identical for all programs (the gates of the processor) and part that depends on the program (the hardcoded input), and this immediately gives a mapping from programs to circuits. The mapping is implemented by a compiler.


texts:
I have a problem in understanding how to prove the following question.

Let $Q = \langle\max,f,L\rangle$ be an NPO-Problem, where $f$ only supports integers.
Define $$L_Q^* =\{(x_0,1^k) : \exists x . L(x_0,x) \land f(x_0,x) \geq k\}.$$
The instance of $x_0$ is binary coded, while the numerical parameter $k$ is unary coded. Show that if $L_Q^*$ is NP-complete, then there is no FPTAS for $Q$.
It can be assumed that $P \neq NP$.

Normally I have some ideas, but this time I am really stumped. My only idea was to use the fact that if $L_Q^*$ has an approximation scheme, then $f$ must run in time polynomial in $|x_0|+|x|$.


texts:
I am having hard time solving the following problem.

  Are there any languages for which
  $$
\overline{L^*} = (\overline{L})^*
$$

Assuming $\emptyset^* = \emptyset$, if I consider $\Sigma = \{a\}$ and L = $\Sigma^*$, I get that $L^* = L$ and that $\overline{L^*} = \emptyset$. For the right side I get $\overline{L} = \emptyset$ and $(\overline{L})^* = \emptyset$. Thus, both sides are equal.

Is it true that $\emptyset^* = \emptyset$?


texts: How does one end up with a non-integer exponent in time complexity? (e.g., $O(n^{2.81})$)

texts:
Periodically I come across sentences like

"Winograd's variant [20] of this algorithm, whose asymptotic complexity is
also $O(n^{2.81})$ are considered" (from https://www.cise.ufl.edu/~sahni/papers/strassen.pdf)

I understand intuitively how we end up with complexities like $O(n^2)$ and $O(n \log n)$ because I can see how the loops and trees work.  But I've got no idea of how one ends up deriving a complexity with a decimal. Can someone give me an example how this happens?


texts: Two versions of arithmetic instructions in RISC. One modifies the flags and the other doesn't

texts:
I've read that in RISC architecture most arithmetic instructions have two "versions":

one that modifies the flags after calculations
one that doesn't modify any flags.

My question is: why is it so?


texts:
I am not sure if this is the right place , but:

Is there an algorithm for solving $n\times n \times n$ rubik's cube (non-trivial one)? If so how efficent is it? Now say I have a $n \times \ldots \times n$ ($d$ times) rubic cube , is there an algorithm that works effiecently for this case?(of course now it depends also on $d$ and not just on $n$)

I haven't found anything online/on wikipedia and I was just wondering.


texts: How fundamental are matroids and greedoids in algorithm design?

texts:
Initially, matroids were introduced to generalize the notions of linear independence of a collection of subsets $E$ over some ground set $I$. Certain problems that contain this structure permit greedy algorithms to find optimal solutions. The concept of greedoids was later introduced to generalize this structure to capture more problems that allow for optimal solutions to be found by greedy methods.

How often do these structures arise in algorithm design?

Furthermore, more often than not a greedy algorithm will not be able to fully capture what is necessary to find optimal solutions, but may still find very good approximate solutions (Bin Packing, for example). Given that, is there a way to measure how "close" a problem is to a greedoid or matroid?


texts: How to prove that a language is not recursively enumerable

texts:
How does one prove that some arbitrary language $L$ is not recursively enumerable?

I know I can prove that the language $L$ is recursively enumerable by constructing a Turing machine $M$ that accepts all words in the language (and the language would be even recursive if $M$ halts on all inputs).

But it is not clear to me how to prove that language in not RE. I was thinking about showing the fact, that such TM could not be constructed for a given language, but proving non-existence is always difficult.