What does it mean to add up O-terms with different variables? Is this true? O(n) + O(k) =O(n+k).I have searched for it ,the  answers were quite ambiguous and I couldn't find a good explanation.

Yes, this is true.

The LHS means that for some $N$, $M$ and some constants $c_n,c_k$,

$$n\ge N,k\ge M\implies f(n,k)\le c_nn+c_kk.$$

The RHS means that for some $N'$, $M'$ and some constant $c$,

$$n\ge N',k\ge M'\implies f(n,k)\le c(n+k).$$

These two statements are equivalent if you take $c\leftarrow\max(c_n,c_k),N'\leftarrow N,M'\leftarrow M$ one way and $c_n=c_k\leftarrow c,N\leftarrow N',M \leftarrow M'$ the other.


Number of literals in the given boolean expression Count the number of literals in the following expression :

F = AB' + BC' + CD' + DE'

According to me, the answer should be 8. But my solution suggests that the answer should be 6. Can anyone help me out. What am I doing wrong?

Thanks in advance!

Does your material use the (strange) convention of notating $\neg A$ as $A'$?

If so, there are 6 literals (5 without the LHS). If $A'$ is distinct from $A$, there are 9 (8 without LHS) and the solution book is wrong.


Is there any bitwise multiplication algorithm that is sub O(n^2)? The following program implements a simple algorithm for binary multiplication:

-- Numbers as infinite streams of bits, least significant bits first
data Bits
  = O Bits
  | I Bits

-- Increments a number
suc :: Bits -> Bits
suc (O xs) = I xs
suc (I xs) = O (suc xs)

-- Adds two numbers
add :: Bits -> Bits -> Bits
add (O xs) (O ys) =      (O (add xs ys))
add (O xs) (I ys) =      (I (add xs ys))
add (I xs) (O ys) =      (I (add xs ys))
add (I xs) (I ys) = (suc (I (add xs ys)))

-- Multiplies two numbers
mul :: Bits -> Bits -> Bits
mul (O xs) ys =        (O (mul xs ys))
mul (I xs) ys = add ys (O (mul xs ys))

(The complete program can be seen here.)

This algorithm, although simple, has O(N^2) complexity. Are there similarly simple algorithms with lower complexities?

Is Karatsuba algorithm simple enough? It's complexity is $O(n^{1.59})$.


Solving T(n)=T(n−1)+2T(n−2) using substitution I am trying to solve the following Recurrence relation using substitution method and I am stuck almost half way.
I know the answer is 2^n but I can't reach it.

At first, my question is:
Who decicdes the base cases? when do we take T(n)=1 for n=1 or T(n)=1 for n=0?

The work I have done till now is as follows:

T(n) = T(n−1) + 2T(n−2)

T(n-1) = T(n-2) + 2T(n-3)

T(n-2) = T(n-3) + 2T(n-4)

Thus, using these, we can subsitute and we get

T(n) = T(n-2) + 2T(n-3) + 2T(n-2)

T(n) = 3T(n-2) + 2T(n-3) (add and then substitue again)

T(n) = 5T(n-3) + + 6T(n-4)

Now assume we go till k, but I am not able to generalize the usage of k and find a correct assumption that will lead to a result of time complexity of Big O of 2^n

The secret of effective substitution is to find the magic numbers -1 and 2. Look and behold.

$$ T(n)+T(n-1)=2T(n-1)+2T(n-2)=2(T(n-1)+T(n-2))$$
Let $S(n)=T(n)-(-1)T(n-1)$. Then
$$S(n)=2S(n-1)=2^2S(n-2)=\cdots=2^{n-2}S(2)\tag{I}$$

$$ T(n)-2T(n-1)=-T(n-1)+2T(n-2)=-(T(n-1)-2T(n-2))$$
Let $R(n)=T(n)-2T(n-1)$. Then
$$R(n)=-R(n-1)=R(n-2)=\cdots=(-1)^nR(2)\tag{II}$$

Eliminating $T(n-1)$ from formula ($\text{I}$) and ($\text{II}$), we obtain $$T(n)= \frac{2S(n) + R(n)}3=\frac{2^{n-1}S(2) + (-1)^nR(2)}3=\frac{S(2)}62^n + O(1)$$

So, $T(n) = O(2^n)$.

It is assumed in the above that S(2) and R(2) are defined or, what is equivalent, T(2) and T(1) are defined. Their actual values do not affect the conclusion.

In fact, we can be more precise. If $T(2)+T(n-1)>0$, i.e., $S(2) > 0$, we will have $T(n)=\Theta(2^n)$. If $T(2)+T(n-1)=0$, we will have $T(n)=O(1)$. If $T(2)+T(n-1)<0$, we will have $-T(n)=\Theta(2^n)$.

How to find those two magic numbers?

Consider T(n) as $x^2$, T(n-1) as $x$ and T(n-2) as 1. Then you get $x^2 = x + 2$. Solving that equation, you get $x=-1$ or $x=2$.

(Exercise.) Let $F(n)=F(n-1)+F(n-2)$ for $n\in\Bbb N$, $n\ge2$. Show $F(n)= O(\alpha^n)$, where $\alpha = \frac{1+\sqrt 5}2$.


probablistic procedure to permutate array input : $array[1...n]$
output: permutated array
Our algorithm should be probablistic and complexity should be $O(n)$.

Could you give me hint ? My weakness is probability theory and it is why I have a problem.

I'm not exactly certain what you mean by probabilistic procedure as pertains to array permutation, and I'm going to assume you're looking for a random permutation of the array. I'm basing this off the formulation of the problem being very similar to an algorithm for that purpose.

So lets say as a person I'd like to do this task: Well, I'd probably just write down all the possible numbers, and then pick a random one. Then I'd cross of the one I'd picked and continue until I'd crossed them all off.

Spoiler as to the name of the algorithm which I mentioned:

   See Fisher-Yates Shuffle algorithm or Knuth Shuffle.


How does Command Z work through computer commands? How does Command Z work through computer commands? What is the step by step computer commands that complete the process?

You should really try to implement this yourself, and then it will become quite obvious.
You define a stack where you put all the operations that the user performs.  Here are some examples:

Close window
Move file from one directory to another
Create file
Move icon on Desktop from $(x_1,y_1)$ to $(x_2, y_2)$
Type a character
Delete a character
Copy to clipboard

All of these operations have reasonable "inverse" operations.:

Close window → Reopen window
Move file from A to B → Move it back to A
Create file X → Delete file X
Move icon from pos1 to pos2 → Move it back to pos1
Type a character → Delete the previous typed character, etc.

When the stack contains "reversable" operations, the undo command simply pops the last operation off the stack and performs its inverse operation.
Some operations are not reversable, though, such as posting on the Internet, and permanently deleting a file.


Adaptive Radix Tree - Question regarding child indexing i have to write an exam in a course given by one of the contributing professors of this paper: http://www-db.in.tum.de/~leis/papers/ART.pdf

Of course this could also be a possible topic in the exam. Now i understand the basic advantages and structure of this tree, but i just cannot fathom some details. Maybe someone here can help me with that:

So Node4 store up to 4 partial keys (of 1 byte each) and up to 4
child pointers. The child pointer used is determined by the position
of the partial key, right?
Starting at Node48 the child pointer is indexed by using the partial key itself as index into the "key"-array and using that value as index into the child-pointer array, right? But why do we have a 256-element array for the key-bytes although there are only 48 child pointers?
Node256 is just an 256-element array indexed through the key byte.

And at last what are those red numbers depicted in this image?

Thanks a lot!

The red values in the image shows key values associated with a location.

Node4 works by performing a linear search for the key byte in the 4-element key array. If we were looking for key value 255 in the image you posted, we'd find at array index 3. We then find the corresponding child by looking at index 3 in the child pointer array.

Node256 is just an 256-element array of child pointers indexed by key byte, yes.

The problem with Node256 is that it wastes a lot of space if most of the array is empty. Node48 uses much less space by exploiting the fact that a pointer is much larger than a byte (typically 8 bytes). We have an 256-element array of bytes (the child index array), one for each key value. When we index into this array, we get a byte that is an index into the 48-element child pointer array. So the lookup is something like this (the actual implementation is slightly different):

Node *find(Node *node, byte key) {
    idx = node->child_indexes[key];
    // Index == 255 is element missing
    if idx == 255 { return null; }
    return node->children[idx];
}

Since the child index array has 256 elements we can just index it with the key byte, no need to search like in Node4 and Node16. But as you say, we only have 48 child pointers, so at most 48 positions in the child index array will be in use at any one time. The elements are small though, so it is not much of a waste.


How to speed up process of finding duplicates/similar items in a large amount of strings? Our software receives documents (in the order of tens of thousands) from various providers, each document flows through a number of steps, one of those steps finds duplicates and similar documents (within 80% threshold) to this document.

We implemented Levenshtein distance algorithm and we limit amount of documents current document has to look over (via a set of hash codes), but this solution is still horribly slow (since it's M*N problem) even after we launch it on multiple cores.

Are there any suggestions/techniques we can use to speed up the processing? The requirement for it is to work in near real-time (I guess we can accept up to 10-20 minutes gap). The only idea I have is to split exact duplicates and similar docs processing in two steps and use something like HyperLogLog for duplicates.

The texts are from social media (tweets, blog posts, etc.) so it's reasonable to assume that duplicates share are far greater than that of a similar docs.

I apologize if my usage of terminology isn't very accurate.

Edit distance is definitely not the way to proceed. The standard approach toward near-identical document deduplication is to compute hashes of shingles. Here's one way to do it:

Compute a set of k-shingles (say 30 char shingles) for each document
Compute min-hashes for the documents
Use locally-sensitive hashing to look-up similar documents when inserting into the database

Here's a great article that explains how this can be done: http://deduplication.tumblr.com/

And you can pick up an existing tool do this, for example Solr: https://wiki.apache.org/solr/Deduplication


Why does PCP theorem imply that NP problems are hard to approximate? 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?

Take as an example SAT. The PCP theorem (in one formulation) shows that there is a PCP for SAT which uses $O(\log n)$ bits of randomness, queries $O(1)$ places, always accepts on YES instances, and rejects on NO instances with probability at least $\alpha > 0$. The PCP queries at most $2^{O(\log n)} = n^{O(1)}$ different locations in the proof, so the entire proof can be encoded in polynomial size. For each of the $2^{O(\log n)}$ possible queries, we can write a formula of constant size that is true if and only if the verifier accepts. Taking all these formulas together in CNF form, we get a CNF $\psi$ (which depends on the instance of SAT) on polynomially many variables (representing the bits of the proof) with polynomially many clauses (each possible query gives rise to $O(1)$ many clauses).

By the definition of PCP, for each $\phi \in \mathrm{SAT}$, there is a proof that satisfies the verifier on all possible queries. In other words, $\psi$ is satisfiable. On the other hand, for each $\phi \notin \mathrm{SAT}$, every proof is rejected with probability at least $\alpha$. This means that any assignment satisfies at most $1-\alpha/O(1)$ of the clauses of $\psi$, the $O(1)$ factor coming from the fact that the result of each query is encoded using $O(1)$ different clauses, one of which must be falsified if the query leads to rejection by the verifier.


In the Curry-Howard isomorphism as applied to Hindley-Milner types, what proposition corresponds to a -> [a]? (Using Haskell syntax, since the question is inspired by Haskell, but it applies to general Hindley-Milner polymorphic type systems, such as SML or Elm).

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

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

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

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

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

One way to interpret types as logic is as the existence conditions for values of the return type. So f :: a -> [a] us the theorem that, if there exists a value of type a, there exists a value of type [a]. The implementation of the function is the proof of the proposition.

Here's a more detailed explanation:

Basically, data constructors let us build similar things to sums and products (OR and AND), but we can have multiple variants, and we can specially "tag" the type with a name to distinguish it (like the name List).

They also let us build them recursively: for a proposition $a$, the proposition $[a]$ can be viewed as a solution to the equation
$x(a) \iff \top \vee (a \wedge x(a) ) $

Things become a bit clearer when you write the definition of List using GADT-style, pseudocode similar to what you'd see in Agda:

data List : Type -> Type where
    Nil : ∀ a . List a
    Cons : ∀ a . a -> List a -> List a

This gives us two things: the constructors (or functions), which act as axioms for the propositions of List, and axioms for pattern-matching or deconstructing them.

Roughly speaking, it introduces the following axioms into the logic:

For any proposition $a$, $[a]$ holds.
If $a$ holds, and $[a]$ holds, then $[a]$ holds
If $[a]$ holds, then either $\top$ holds, or $a \wedge [a]$ holds.

These are pretty useless when interpreted as logic, since we always know $\top$ holds, deconstructing there doesn't give us much useful information

Without quantifiers or more powerful type extensions (GADTs, Type Families, dependent types, etc.), you can see that we can't really prove interesting things, which is why you often don't see much about interpreting standard Haskell types as logic.


Regex for strings with even number of 1's and number of 0's divisible by 5 I was trying to build up this regex but I am having huge expressions but nothing generates the given regex. I tried to break up the regex as

$0$ multiple of five times and odd $1$'s
$0$ multiple of five times and even $1$'s

Bu this doesn't help me.
The regex  I Found was  $(00)^*1(00)^*1(00)^*1(00)^*1(00)^*$. But in this way two $1$'s and five $0$'s cannot be generated.
Again $(11)^*0(11)^*0(11)^*0(11)^*0(11)^*$ does not generate $5n$ times $0$'s for $n\ge 2$.
There are other possibilities and that too do not meet the regex.
Any help would be appreciated.
P.s: I am at the very beginning in regex. So I am currently trying to avoid the method of conversion from finite automata to regular expressions.

Your last idea is good, but insufficient. Also there is not the right number of zeros. Now let's try to decompose the problem:
Let's consider $L_0=\{1^i01^j01^k01^l01^m01^n,i+j+k+l+m+n \text{ is even}\}$.
Your (corrected) idea was $e_1 = (11)^*0(11)^*0(11)^*0(11)^*0(11)^*0(11)^*$, but this only generate words of $L_0$ where $i, j, k, l, m, n$ are all even. You need now to consider other possibilities. For example, if $j$ and $m$ are odd and the rest are even, we get the regular expression:
$$(11)^*0(11)^*10(11)^*0(11)^*0(11)^*10(11)^*$$
There are a total of $\binom{6}{0} + \binom{6}{2}+\binom{6}{4}+\binom{6}{6} = 32$ expressions to consider all possibilities (choice of an even number of indices that are odd among the 6).
The final regular expression will then be $\left(e_1+e_2+…+e_{32}\right)$.
Now you need to do the same thing with a language $L_1$ containg an odd number of $1$'s, and construct the regular expression for your language with both $L_0$ and $L_1$.
This sure is ugly as hell, but hey, it works! There may be a simpler way to write it, but I'm not so sure.


ILP and number of variables in constraints This question is about the time impact of the length (i.e. number of variables) of the constraints in an Integer Linear Programming formulation.
Most people try to reach the minimum number of constraints/variables, but I couldn't find anything that considers the size of the constraints.

In more concrete terms, I have some maximization problem for which I can make two different formulations $A$ and $B$.  Both have $O(n^2)$ variables, $n$ being the size of the input.

Formulation $A$ has $O(n^3)$ constraints, each having a constant number of variables (say each constraint is a summation over four variables).

Formulation $B$ has $O(n^2)$ constraints, but many constraints are of linear size - i.e. they include summations over $O(n)$ variables.

In terms of performance, does $B$ have an advantage over $A$ ?

There are no hard rules for which formulation would be better especially for mixed-integer problems, however

The time to solve an lp relaxation usually increases with the number of nonzeros in the constraint matrix, but
Tighter lp relaxations usually reduce the number of lp relaxations that need to be solved.

To take your example, suppose you have a variable $y$ that is 1 only if all variables $x_0, x_2, \ldots, x_{n-1}$ have value 1, and all values are binary.  You could write a single constraint
$$ny \le \sum_{i=0}^n x_i$$

or $n$ constraints
$$y \le x_i, \forall i \in \{0, \ldots n-1\}$$

Both sets of constraints will have the same integer-feasible set, but the $n$ constraints have a much smaller continuous-feasible set, so it is probably be much faster to solve.


How can you prove 3^n is not O(n^2)? I can obviously tell by inspection that it is not true but I cannot figure out how to prove it with witnesses (C and k). Thanks!

Let's assume that $3^n = O(n^2)$.

This would by definition mean that there are real positive numbers $a$ and $b$ such that for any sufficiently large $n$ (or to say as $lim_{n \to +\infty}$):

$ an^2 \leq 3^n \leq bn^2 $

Dividing everything by $3^n$ we get:

$ a\frac{n^2}{3^n} \leq 1 \leq b\frac{n^2}{3^n}$

And since if we let $lim_{n \to +\infty}$ we get a contradiction:

$ 0 \leq 1 \leq 0 $

Hence inital statement is false and $ 3^n \neq O(n^2) $


Counting approximate solutions Many of us are familiar with the $P$ class. Counting solutions is believed to be a difficult task and that is why we usually end up approximating the number of solutions (we relax the accuracy of the counting). I want to ask, if relaxing the quality of the solutions counted has been addressed as a problem. Is there for example, any algorithms able to answer the question: How many vertex covers there are, with 3 times the cardinality of the minimum vertex cover? Is the problem $P-$ complete?

Let $(G,k)$ be an instance of vertex cover, where $G$ is a graph on $n$ vertices, and $k$ is the threshold. Suppose furthermore that the minimum vertex cover of $G$ has size either at most $k$ or at least $ck$ for some $c > 1$; this version is already NP-hard.

Consider $n$ copies of $G$, with the addition of a clique of size $n^D$. If $G$ has a minimum vertex cover of size $\ell \leq k$ then the new graph has a vertex cover of size $n\ell+1$, and at most $\binom{n^2}{3nk+3} \binom{n^D}{2nk+3} \leq n^{(6+2D)nk + 6+3D}$ vertex covers of size $3(n\ell+1)$. If the minimum vertex cover of $G$ is $\ell \geq ck$ then the new graph has a minimum vertex cover of $n\ell+1$, and at least $\binom{n^D}{2n(ck)+3} \approx n^{2Dcnk+3D}$ vertex covers of size $3(n\ell+1)$. We can choose $D$ so that $2Dc > 6+2D$, and then the gap between the two cases is roughly $n^{(2Dc-2D-6)nk-6} = e^{\Omega(n\log n)}$.

This reduction shows that it is NP-hard to approximate the number of vertex covers of thrice the minimum size within $e^{O(n\log n)}$. The interested reader can get even better results by slightly tweaking the construction.


Time complexity of the fast exponentiation method I am trying to analyse the time complexity of the fast exponentiation method,
which is given as

$$x^n=
\begin{cases}
 x^\frac{n}{2}.x^\frac{n}{2}       &\text{if n is even}\newline
x.x^{n-1}   &\text{if n is odd} \newline
1 &\text{if n=0}
\end{cases}
$$

I tried to write it as,
$$
T(n)=\begin{cases}
T(\frac{n}{2}).T(\frac{n}{2}) &\text{if n is even}\newline
T(n-1) &\text{if n is odd}\newline
1 &\text{if n=0}
\end{cases}
$$

I think I am lacking somewhere and so not able write correct recurrence relation here.

Need help to do so.

Instead of time complexity, it is much simpler here to count multiplications; I'll leave you to figure out the relation between multiplications and time complexity (the exact relation depends on the computation model).

Denote the number of multiplications when computing $x^n$ using your algorithm by $S(n)$.
Let's consider your cases from bottom to top:

Calculating $x^n$ for $n = 0$. The answer is $1$, so no multiplications are needed: $S(1) = 0$.
Calculating $x^n$ for $n$ odd. In this case we first calculate $x^{n-1}$ using the same method, which takes $S(n-1)$ multiplications by definition. Then we multiply the result by $x$, which uses up one multiplication. This gives $S(n) = S(n-1) + 1$ in this case.
Calculating $x^n$ for $n>0$ even. In this case we first calculate $x^{n/2}$ using the same method, which takes $S(n/2)$ multiplications by definition. Then we multiply the result by itself, which uses up one multiplication. This gives $S(n) = S(n/2) + 1$ in this case.

In total, we get the following recurrence for the number of multiplications:
$$
S(n) = \begin{cases}
0 & n = 0 \\
S(n-1) + 1 & n \text{ odd} \\
S(n/2) + 1 & n>0 \text{ even}
\end{cases}
$$
We can improve on the algorithm slightly using the identity $x^1 = x$. This gives the following alternate recurrence:
$$
S'(n) = \begin{cases}
0 & n \leq 1 \\
S'(n-1) + 1 & n>1 \text{ odd} \\
S'(n/2) + 1 & n>0 \text{ even}
\end{cases}
$$


Item lookaheads versus dot lookaheads for $LR(k)$ with $k \gt 1$? I was reading "Parsing Techniques: A Practical Guide, Second Edition" by Grune and Jacobs, which details a bunch of different parsing algorithms. In the section on $LR(2)$ parsing, they mention that unlike $LR(1)$ items, which just have an item lookahead (the token that should appear after the completed $LR(1)$ item), the items in an $LR(2)$ parser also need a dot lookahead (the tokens that should appear after the dot in the $LR(2)$ item).

I'm having trouble understanding what this means, how this lookahead is computed, and why this isn't needed in $LR(0)$ or $LR(1)$ items. Can anyone explain what this means?

I think you are mistaken, they are needed but the dot look-ahead there is so obvious that you have not paid attention to the fact it is used.

First, let's remark that there are three kinds of items:

those in which the dot is just before a non-terminal. They never participate in an ambiguous situation: when a non-terminal has been produced, it is shifted.
those in which the dot is at the end. They have the item look-ahead and the dot look-ahead which are equal (what may follow the dot is what may follow the produced non-terminal when the production is reduced as the dot is at the end of the item).
those in which the dot is just before a terminal.  They have the item look-ahead and the dot look-ahead which are different.  The item look-ahead is what may follow the non-terminal when the production is reduced, the dot look-ahead start by the terminal which follow the dot and continue with what can be generated after that terminal.

Now, with a look-ahead of 1 or less, the dot look-ahead is trivial: either it is the item look-ahead or the terminal which is just after the dot and that's what you are using to solve a conflict (or decide that there is no way with the limited look-ahead you have).  With a look-ahead of 2 or more, you have to compute the dot look-head or you may not know if you have to shift or to reduce as in the example provided by Grune and Jacobs:

$$\begin{array}{l}
S \rightarrow Aa \; | \; Bb \;| \;Cec \;|\; Ded \\
A \rightarrow qE \\
B \rightarrow qE \\
C \rightarrow q \\
D \rightarrow q \\
E \rightarrow e \\
\end{array}$$

which has the state:
$$\begin{array}{lcc}
&\textrm{item look-ahead}&\textrm{dot look-ahead}\\
A \rightarrow q \cdot E & a\#  & ea\\
B \rightarrow q \cdot E & b \# & eb\\
C \rightarrow q \cdot   & ec   & ec\\
D \rightarrow q \cdot   & ed   & ed\\
E \rightarrow \cdot e   & a \# & ea\\
E \rightarrow \cdot e   & b \# & eb\\
\end{array}$$


How is segmentation different from multiprogramming with fixed partition? As seen here:
It works same like multiprogramming with fixed partition and also the memory is contiguous as well. How is it different and especially non-contiguous? What's happening here?

Segmentation partitions the address space into logically distinct parts
usually with the high-order bits representing the segment number, within which the low order bits are a normal linear address space.

A segment is the unit of access control to memory: one process may be able to read it while another is allowed to write it.

A process will generally have access to many segments.
Several processes may access the same segment. This is a possible way
for processes to communicate.

In Multiprogramming with fixed partitions, each process occupies a contiguous linear address space. It may or may not be aware of the position of the address space in the computer's memory. The process has complete access to its own address space and no access to any other process's. Any process, however, may make system calls.

You can put paging (virtual memory) underneath segmented or partitioned memory.


Why is this sequence of recurrence relevant? I am learning how to solve the time complexity for the recurrence relation

$$
    T(n) = 2T(n - 1) + n^2\text{, where }T(1) = 1
$$

The solution notes that I should begin by considering the following sequence:

$$
    \text{Define }T^k(n) = T^{k - 1}(n + 1) - T^{k - 1}(n) \\
    \text{and let }T^{(0)}(n) = T(n)
$$

How is the sequence $T^k(n)$ relevant to solving my original recurrence relation? This just seems to be complicating the problem by defining an entirely new sequence.

Calculus of differences

We make Kaya's nice observations slightly more formal. The sequence $T^k$ is the $k$th difference sequence of the original sequence $T$. You can think of it as a discrete $k$th derivative. For example, if $T$ is a $k$th degree polynomial then $T^k$ is constant. We will see below what happens when $T$ is exponential.

For a sequence $T$ (all sequences range over the positive integers), let $\Delta(T)$ be defined by $$ \Delta(T)(n) = T(n+1)-T(n). $$
So $T^k = \Delta^{(k)}(T)$, that is $T^k$ is obtained by applying $k$ times the operator $\Delta$. The operator $\Delta$ has an inverse, which corresponds to indefinite integration:
$$ T(n) = T(1) + \sum_{k=1}^{n-1} \Delta(T)(k). $$
If we are only given the sequence $\Delta(T)$ then we don't know $T(1)$, and we can think of it as a constant of integration. For concreteness, define another operator $\Sigma$ given by
$$ \Sigma(T)(n) = \sum_{k=1}^{n-1} T(k). $$
The "fundamental theorem of calculus" then states that
$$ \Delta(\Sigma(T)) = T $$
and
$$ \Sigma(\Delta(T)) = T - T(1). $$
Another useful property of the operators $\Delta$ and $\Sigma$ is their linearity.

Furthermore, we have the nice formula $$\Delta^{(k)}(n^k) = k!,$$ which can be proved by induction on $k$. This formula also implies that $$\Delta^{(k+1)}(n^k) = 0.$$ In fact, this is true for any polynomial of degree at most $k$. Conversely, $\Sigma(n^k)$ is some polynomial of degree $k$.

We can do the same for exponentials:
$$ \Delta(c^n) = (c-1)c^n, \quad \Sigma(c^n) = \frac{c^n-1}{c-1}.$$

Finally, it will be useful to use the shift operator $S$ given by $$S(T)(n) = T(n+1).$$
This operator commutes with $\Delta$: $S(\Delta(T)) = \Delta(S(T))$.

Solving the recurrence

Now to the problem at hand. The sequence $T$ satisfies $$S(T) = 2T + (n+1)^2. $$
Taking the third difference, we get $$S(\Delta^{(3)}(T)) = 2\Delta^{(3)}(T).$$
Here we used the linearity of $\Delta$, the commutativity of $\Delta,S$, and the fact that the third derivative of $(n+1)^2$ vanishes. We can conclude that
$$ \Delta^{(3)}(T) = C 2^n, \quad C = \Delta^{(3)}(T)(1)/2. $$
We now want to repeatedly apply the operator $\Sigma$. Each time we apply $\Sigma$, we get some constant of integration. After the first time, we get
$$ \Delta^{(2)}(T) = C 2^n + C_1 $$
for some $C_1$, using $\Sigma(2^n) = 2^n-1$. While we can express $C_1$ in terms of $T$, it is better not to. The next time we apply $\Sigma$, $C_1$ turns into a linear terms, and so
$$ \Delta^{(1)}(T) = C 2^n + C_1 n + C_2 $$
for some $C_2$. The next time we apply $\Sigma$, $C_1 n$ turns into a quadratic term, and so
$$ T = C 2^n + P_2 $$
for some quadratic polynomial $P_2$.

It remains to find $C$ and $P_2$. Recall that $C = \Delta^{(3)}(T)(1)/2$. Kaya calculated $\Delta^{(3)}(T)(1) = 12$ and so $C = 6$. Therefore
$$ T = 6 \cdot 2^n + P_2. $$
The first few values in $T$ are $1,6,21$, and so $P_2(1) = -11$, $P_2(2) = -18$, $P_2(3) = -27$. Write $P_2 = B_2 n^2 + B_1 n + B_0$, and so $\Delta^{(2)}(P_2) = 2B_2$. On the other hand, $\Delta(-11,-18,-27,\ldots) = (-7,-9,\ldots)$ and so $\Delta^{(2)}(-11,-18,-27,\ldots) = (-2,\ldots)$, and we conclude that $B_2 = -1$. We can now calculate $B_1 n + B_0 = (-10,-14,\ldots)$, and so $B_1 = -4$ and $B_0 = -6$. We can conclude that $P_2 = -n^2 - 4n - 6$, and we get Kaya's formula.

Generalities

More generally, if $T$ is a sequence satisfying $T(n+1) = c T(n) + P_k(n)$ for some polynomial $P_k$ of degree $k$, then the very same method shows that
$$ T(n) = C c^n + P_{k+1}(n) $$
for some constant $C$ and polynomial $P_{k+1}$ of degree $k+1$. In order to find $C$ and $P_{k+1}$, we can either follow the route used above - express $C$ in terms of $c$, $k$ and $\Delta^{(k+1)}(T)(1)$ - or calculate $T(1),\ldots,T(k+2)$ and solve linear equations in the unknowns $C$ and the coefficients of $P_{k+1}$.

Even more generally, we can handle recurrences of the form $T(n) = c_1 T(n-1) + \cdots + c_l T(n-l) + P_k(n)$. As before, after applying $\Delta^{(k+1)}$, the inhomogeneous terms $P_k$ disappears, and we can solve the resulting recurrence relation. Applying $\Sigma^{(k+1)}$, we will get an "error term" of the form $P_{k+1}$ as before.

General recurrence relations have solutions which are sums of expressions of the form $n^r c^n$ for integer $r \geq 0$, so we also need to calculate the (iterated) discrete integrals of these functions; the result of applying $\Sigma$ once is $P_{r+1}(n) c^n$ for some polynomial $P_{r+1}$ of degree $r+1$, and so applying it $k+1$ time we obtain $P_{r+k+1}(n) c^n$ for some polynomial $P_{r+k+1}$ of degree $r+k+1$. As before, we can find the coefficients of all polynomials by solving linear equations, given enough values of the sequence $T$.


Solve parity game in polynomial time? Is it possible to solve a parity game in polynomial time? If yes, how? If no, why not?

The state of the art for solving parity games is now quasipolynomial time. Here are references:

  Deciding Parity Games in Quasipolynomial Time (PDF), by Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan.

  A short proof of correctness of the quasi-polynomial time algorithm for parity games, by Hugo Gimbert and Rasmus Ibsen-Jensen.

  Succinct progress measures for solving parity games, by Marcin Jurdziński and Ranko Lazić, LICS 2017.

An implementation and comparison with previous approaches is available (classic strategy improvement "wins" on random instances, but gets "slow" on Friedmann’s trap examples):

An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space, by John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, Dominik Wojtczak


Understanding characterizations of Matching on Graphs I am studying Matching Theory on Graphs and I am wondering if I understand the characterization of the problems right.

Definition:
Let $G = (V, E)$ a graph. A set $M \subseteq E$ is called a matching in $G$ if and only if each vertex $v$ in $V$ is incident to at most one edge in $M$, that is,  $\forall v \in V ( \forall w \in V ( \forall x \in V (( vw \in M \wedge vx \in M) \rightarrow w = x)))$ holds.
Edges may be weighted.
For any matching $M$ and weight function $w: E \rightarrow \mathbb Q$ we define $w(M) := \Sigma_{e \in M} w(e)$.

In the following are the definitions of the two computational problems I am currently working with.
For simplicity sometimes I use bipartite graphs only.

Problem Name: $\text{MAXIMUM-CARDINALITY MATCHING}$

Input: A graph $G = (V, E)$.

Task: Find a matching $M$ such that $|M|$ is maximum.

Problem Name: $\text{MAXIMUM-WEIGHT BIPARTITE MATCHING}$

Input: A bipartite graph $G = (V, E)$ with weights $w: E \rightarrow \mathbb Q$ on the edges.

Task: Find a matching $M$ such that $w(M)$ is maximum.

Definition:
A path $P$ in $G$ is called $M$-alternating if and only if the edges in $P$ are alternatingly out of and in $M$.

Definition:
A path $P$ in $G$ is called $M$-augmenting if and only if $P$ is $M$-alternating and both its end vertices are not covered by $M$.

Thoerem (I think it is due to Peterson):
Let $G = (V, E)$ be a graph and let $M$ be a matching in $G$.
Then either $M$ is a solution to $\text{MAXIMUM-CARDINALITY}$ $\text{MATCHING}$ or there exists an $M$-augmenting path.

Theorem (Egervary):
Let $G = (V, E)$ be a bipartite graph and let $w: E \rightarrow \mathbb Q$ be a weight function.
Then the maximum weight of a matching in $G$ (that is, the weight of a solution to the $\text{MAXIMUM-WEIGHT}$ $\text{BIPARTITE MATCHING}$ problem) is equal to the minimum value of $y(V)$, where $y : V \rightarrow \mathbb Q$ is such that $y_u + y_v \geq w_e$ for each edge $e = uv$.
If $w$ is integer, we can take $y$ integer.

My question is: Does there exist a simpler characterization of the $\text{MAXIMUM-WEIGHT}$ $\text{BIPARTITE MATCHING}$ problem similar to Peterson's Theorem?
What is wrong with the following characterization?

First, let $A \; \Delta \; B$ denote the symmetric difference of two sets $A$ and $B$.
Further, if $P$ is a path, then let $E(P)$ denote the set of edges in $P$.

Hypothesis:
Let $G = (V, E)$ be a bipartite graph, $w: E \rightarrow \mathbb Q$ a weight function, and $M$ a matching in $G$.
Then either $w(M)$ is maximum or there exists an $M$-alternating (note: not necessarily $M$-augmenting) path $P$ such that $M' := M \; \Delta \; E(P)$ is a matching in $G$ and $w(M') > w(M)$.

Is the hypothesis correct? If not, why is it wrong? What about the hypothesis with respect to non-bipartite graphs? If the hypothesis is correct, why is always Egervary's Theorem used?

It is nice for OP to extract the essence of the proof for Berge's Lemma, which is described as the  "Theorem (I think it is due to Peterson)" to create the hypothesis.

"Is the hypothesis correct? If not, why is it wrong?" Yes, it is correct.

"What about the hypothesis with respect to non-bipartite graphs?" Yes, it is still correct with respect to non-bipartite graphs.

"If the hypothesis is correct, why is always Egervary's Theorem used?" Well, I cannot avow Egervary's Theorem is always used (when? and where?).
It is true, however, that in the case of bipartite graph, Egervary's Theorem is instrumental in creating a fast and easily-implementable algorithm to find the maximum weight matching. In comparison, I cannot find  a similarly good algorithm for which the hypothesis can be equally helpful. So it is no wonder that Egervary's Theorem is usually mentioned when we come to the maximum weight matching for bipartite graph.


How can lazy learning systems simultaneously solve multiple problems? On the english Wikipedia it says about lazy learning systems:

  Because the target function is approximated locally for each query to the system, lazy learning systems can simultaneously solve multiple problems […]

What does this mean? I can only guess what "approximated locally" is supposed to say but even then I have no idea how one is supposed to follow from the other.

Let's see:

  Because the target function is approximated locally for each query to
  the system,

If i am going to predict the class (for example) of a brand new instance i compare it with the most similar in the train dataset. Imagine a 2D graphic with lots of points and i put the new point, so i compare with the other points locally, and the class of the nearest to it will help me say what is its class.

  lazy learning systems can simultaneously solve multiple problems
  and deal successfully with changes in the problem domain.

Maybe, these problems are the ones created by the eager methods that try to simulate the hyperplanes (boudaries) in a function, in logic predicates, etc between the classes and these hyperplanes make lots of mistakes. And simple local comparisons with the similarity with the train dataset could do a better work.


Hardcore Bit proof for discrete log I am studying Crypto and am trying to understand why discrete log creates is useful for creating a PRG. More specifically, I want to prove via reduction that  $B(x)=(x<p/2)$ is a hardcore bit for the one-way function $f_{p,g}(x)=g^x \bmod p$. So far, I have shown that if there is a polynomial-time algorithm $D$ that computes this bit perfectly, then
there is another polynomial-time algorithm $I$ that inverts the one-way function perfectly.
I want to extend the proof to the case
when $D$ is imperfect, but successful with probability $\frac12 +\epsilon$ for some nonnegligible $\epsilon$
(in this case, the probability is taken over a random choice of $x$ between 0 and $p-1$). I want to show that for this case,
it is possible to invert $f$ with nonnegligible probability in polynomial time.

Any help is appreciated.

The usual approach is to identify a randomized self-reduction.  In other words, given a problem instance $x$, you generate a randomized version of $x$, say $x'$, and show how the solution to $x'$ gives you the solution to $x$.

How does this help?  Given a problem instance $x$, you can generate many randomized versions, say $x'_1,x'_2,\dots,x'_m$ (each one using independent randomness).  Now, try to solve each of the $x'_1,x'_2,\dots,x'_m$.  By the conditions of your problem, you know that you'll have a way to solve them, so that a $1/2 + \epsilon$ fraction of the answers are correct: i.e., so that $m/2 + \epsilon m$ of the $m$ answers are correct.

Now, you take it from here.  How could you use that to form a reasonable guess at the solution to $x$?


Properties of Gomory-Hu trees Given an undirected graph $G=(V,E)$ a Gomory-Hu tree $T$ for $G$ has the following properties:

$T$ has a node for each vertex in the graph G and each edge in the tree corresponds to a minimum cut separating the corresponding pair of vertices of G.
$T$ has the property that the minimum cut between vertices $s$ and $t$ in $G$ is the cut corresponding to the minimum weight edge along the path from $s$ to $t$ in the Gomory-Hu tree.

In $[1]$, the author states the following lemma:

Let $S$ be the union of cuts in $G$ associated with $n$ edges of $T$. Then removal of $S$
from $G$ leaves a graph with at least $n+1$ components.

Consider a complete graph $K_4$ with all the edges having weight $1$.
A (possible) Gomory-Hu Tree $T$ for $K_4$ is the following:

If we remove the cuts associated with all the $n=3$ edges of $T$ we might proceed as follows:

$(3,0) \in T$ $\rightarrow$ remove $\{(3,0),(3,1),(3,2)\} \in G$
$(3,1) \in T$ $\rightarrow$ remove $\{(3,0),(3,1),(3,2)\} \in G$
$(3,2) \in T$ $\rightarrow$ remove $\{(3,0),(3,1),(3,2)\} \in G$

A potential result (among the different ones) is a graph with $2 \neq (n+1=4)$ connected components, i.e., $\{3\}$ and $\{1,2,4\}$.
So, my question is, am I missing something in the definition or properties of the Gomory-Hu trees?
Does the author mean that for each $(u,v)$ in $T$, all the minimum weight cuts between $u$ and $v$ in $G$ should be removed in order for the lemma to hold?

[1] Vazirani, Vijay V. Approximation algorithms. Springer Science & Business Media, 2013

The book states the following definition of a cut:

a cut is defined by a partition of $V$ into two sets say $V^{l}$  and $V \setminus V^{l}$ and consists of all edges that have one endpoint in each partition.

Therefore, removing a cut from the graph should mean that we are removing the edges that go across the cut.
Also, consider the following definition of the "cut associated with an edge $(u,v) \in T$ in $G$".

Each edge $(u,v)$ in $T$ denotes a partition of $V$ given by the two connected components obtained by removing $(u,v)$ from $T$. Consider the cut defined in $G$ by this partition. We will say that this is the cut associated with $(u,v)$ in $G$.

Now, let us consider your example of Gomory-Hu tree for $K_{4}$. We want to find the cut associated with the edge $(3,0) \in T$. If we remove $(3,0)$ from $T$, we obtain the partitioning $\{1,2,3\}$ and $\{0\}$. This defines the cut in $G$.
Therefore, you should be removing the edges of $G$ that goes across this cut i.e., $(0,1)$ $(0,2)$ and $(0,3)$.
Similarly for the edge $(3,1) \in T$, you should be removing the edges: $(1,0)$, $(1,2)$, and $(1,3)$.
And, for the edge $(3,2) \in T$, you should be removing the edges: $(2,0)$, $(2,1)$, and $(2,3)$.
It means we are removing all edges from the graph. Therefore, the number of connected components in the remaning graph would be $4 = (n + 1)$, for $n = 3$.


What usage is the delta defined in the polynomial hierarchy? At the Wikipedia page, the polynomial hierarchy also defines the following:

$\Delta_0^\text{P} = P$, $\Delta_i^\text{P} = \text{P}^{\Sigma_{i-1}^\text{P}}$

However, the only usage of this anywhere else on the page is the following set of inclusions:

$\Pi_i^P \subseteq \Delta_{i+1}^P \subseteq \Pi_{i+1}^P$.

What usage does this $\Delta_i^P$ class have?

The polynomial hierarchy is an analog of the arithmetical hierarchy in recursion theory, which also has $\Sigma,\Pi,\Delta$, and several other hierarchies also have $\Delta$ terms.

The usage is exactly the same as the usage of $\Sigma_i^P$ and $\Pi_i^P$. For a given problem, you try to find its exact location in the polynomial hierarchy. If a problem is in $\Delta_i^P$ then it can't be $\Sigma_{i+1}^P$-hard (unless the polynomial hierarchy collapses), but perhaps it is $\Delta_i^P$-hard. So you might need these classes for some problems.


Difference between methods of converting from finite state machine to regular expression I have a question about method that I saw on internet and method that my professor showed me. I have this finite state machine:

q1(a)=q1
q1(b)=q2
q2(a)=q2
q2(b)=q3
qf3(a)=qf3
qf3(b)=qf3

My professor using a method

r(p,q,k+1)=r(p,q,k)|r(p,k+1,k)r(k+1,k+1,k)*r(k+1,q,k)

and he start from (1,3,3). He get r(1,3,3)=a*ba*b|(a|b)*, I understand that method but if a finite state machine is more complicated then it takes to much time, so I saw on internet and I saw here a method where I start like this

q1=epsilon+q1a, q1=a*
q2=q1b+q2a, q2=a*ba*
q3=q2b+q3a+q3b, q3=a*ba*b(a+b)*,q3=a*ba*b(a|b)*

Both regular expression look similar but I do not know is that the same? Can you tell me where is difference if difference exist?

There is a reference question on methods to convert a finite automaton into a regular expression. Personally I am very fond of the "State removal method" which is equivalent to the "Transitive closure method" you seem to be using. The reason is that the administration you do in the state removal seems to be less, and is more easily kept as labels to edges, rather than keeping track of many $R[i,j,k]$ sets.

Nevertheless, basically all methods use the same recursion, and one gets equivalent results. I say equivalent here, because there is no way to uniquely denote regular languages. Even when using the same method, when applying the reductions in a different order one gets a different result. But again, this is always the same language, only written in a different way.


What is loop invariant for this loop? As far as i understand all loops have a loop invariants. My understanding is that loop invariant is an argument that is true at the beginning of the loop block as well as at the end of the loop.
For example:
while(P) {
  //predicate is true here
  body of the loop
  //predicate still true here
}

But let`s say i have the following loop (the code is in Java):
while(stack.size() > 0 && stack.peek() < 0) {
   stack.pop();
}

What i am trying to do here is to pop all negative numbers from the top of the stack - so at the end of the loop at the beginning of the stack will be a positive number or we have an empty stack.
It is not clear from this loop what its invariant?
What technic we can use to get loop invariant. In general, i would like to use loop invariants for validation of program correctness.

"
    Pre: stack is empty or contains only integers
    Post: Stack top is non-negative Integer
    P:  Stack top is an Integer   ( P is the invariant )
    BB: Stack top is negative
    T:  Stack size
"

" Establish P "
stack size > 0 or: [stack push: 0].
[ stack top negative
] whileTrue:
    [ " reduce T "
      stack pop.
      " restore P "
      stack size > 0 or: [stack push: 0]
    ]
" P && non BB => Post "


What determines the "speed" of a programming language? Suppose a program was written in two distinct languages, let them be language X and language Y, if their compilers generate the same byte code, why I should use language X instead of the language Y? What defines that one language is faster than other?

I ask this because often you see people say things like: "C is the fastest language, ATS is a language fast as C". I was seeking to understand the definition of "fast" for programming languages.

There are many reasons that may be considered for choosing a language
X over a language Y. Program readability, ease of programming,
portability to many platforms, existence of good programming
environments can be such reasons. However, I shall consider only the
speed of execution as requested in the question. The question does not
seem to consider, for example, the speed of development.

Two languages can compile to the same bytecode, but it does not mean
that the same code will be produced,

Actually bytecode is only code for a specific virtual machine. It does
have engineering advantages, but does not introduce fundamental
differences with compiling directly for a specific harware. So you
might as well consider comparing two languages compiled for direct
execution on the same machine.

This said, the issue of relative speed of languages is an old one,
dating back to the first compilers.

For many years, in those early times, professional considered that
hand written code was faster than compiled code. In other words,
machine language was considered faster than high level languages such
as Cobol or Fortran. And it was, both faster and usually smaller. High
level languages still developed because they were much easier to use
for many people who were not computer scientists. The cost of using
high level languages even had a name: the expansion ratio, which could
concern the size of the generated code (a very important issue in
those times) or the number of instructions actually executed.  The
concept was mainly experimental, but the ratio was greater than 1 at
first, as compilers did a fairly simple minded job by today standards.

Thus machine language was faster than say, Fortran.

Of course, that changed over the years, as compilers became more
sophisticated, to the point that programming in assembly language is
now very rare. For most applications, assembly language programs
compete poorly with code generated by optimizing compilers.

This shows that one major issue is the quality of the compilers
available for the language considered, their ability to analyse the source
code, and to optimize it accordingly.

This ability may depend to some extend on the features of the language
to emphasize the structural and mathematical properties of the source
in order to make the work easier for the compiler. For example, a
language could allow the inclusion of statements about the algebraic
properties of user defined functions, so as to allows the compiler to
use these properties for optimization purposes.

The compiling process may be easier, hence producing better code, when
the programming paradigm of the language is closer to the features of
the machines that will intepret the code, whether real or virtual
machine.

Another point is whether the paradigms implemented in the language are
closed to the type of problem being programmed. It is to be expected
that a programming language specialized for specific programming
paradigms will compile very efficiently features related to that
paradigm. Hence the choice of a programming language may depend, for
clarity and for speed, of the choice of a programming language
adapted to the kind of problem being programmed.

The popularity of C for system programming is probably due to the fact
that C is close to the machine architecture, and that system
programming is directly related to that architecture too.

Some other problem will be more easily programmed, with faster
execution using logic programming and constraint resolution languages.

Complex reactive systems can be very efficiently programmed with specialized synchronous programming languages like Esterel which embodies very specialized knowledge about such systems and generate very fast code.

Or to take an extreme example, some languages are highly specialized,
such as syntax description languages used to program parsers. A parser
generator is nothing but a compiler for such languages. Of course, it
is not Turing complete, but these compilers are extremely good for
their specialty: producing efficient parsing programs. The domain of
knowledge being restricted, the optimization techniques can be very
specialized and tuned very finely. These parser generators are usually
much better than what could be obtained by writing code in another
language. There are many highly specialized languages with compilers that produce excellent and fast code for a restricted class of problems.

Hence, when writing a large system, it may be advisable not to rely on
a single language, but to choose the best language for different
components of the system.  This, of course, raises problems of
compatibility.

Another point that matters often is simply the existence of efficient libraries for the topics being programmed.

Finally, speed is not the only criterion and may be in conflict with
other criteria such as code safety (for exemple with respect to bad
input, or resilience to system errors), memory use, ease of
programming (though paradigm compatibility may actually help that),
object code size, program maintainability, etc.

Speed is not always the most important parameter. Also it may take different guises, like complexity which may be average complexity or worse case complexity. Also, in a large system as in a smaller program, there are parts where speed is critical, and others where it matters little. And it s not always easy to determine that in advance.


Confluence of beta expansion Let $\to_\beta$ be $\beta$-reduction in the $\lambda$-calculus. Define $\beta$-expansion $\leftarrow_\beta$ by $t'\leftarrow_\beta t \iff t\to_\beta t'$.

Is $\leftarrow_\beta$ confluent? In other words, do we have that for any $l,d,r$, if $l \to_\beta^* d\leftarrow_\beta^* r$, then there exists $u$ such that $l\leftarrow_\beta^* u \to_\beta^* r$?

Keywords: Upward confluence, upside down CR property

I started by looking at the weaker property: local confluence (i.e. if $l \to_\beta d\leftarrow_\beta r$, then $l\leftarrow_\beta^* u \to_\beta^* r$). Even if this were true, it would not imply confluence since $\beta$-expansion is non-terminating, but I thought that it would help me understand the obstacles.

(Top) In the case where both reductions are at top-level, the hypothesis becomes $(\lambda x_1.b_1)a_1\rightarrow b_1[a_1/x_1]=b_2[a_2/x_2]\leftarrow (\lambda x_2.b_2)a_2$. Up to $\alpha$-renaming, we can assume that $x_1\not =x_2$, and that neither $x_1$ nor $x_2$ is free in those terms.

(Throw) If $x_1$ is not free in $b_1$, we have $b_1=b_2[a_2/x_2]$ and therefore have $(\lambda x_1.b_1)a_1=(\lambda x_1.b_2[a_2/x_2])a_1\leftarrow(\lambda x_1.(\lambda x_2.b_2)a_2)a_1\rightarrow (\lambda x_2.b_2)a_2$.

A naive proof by induction (on $b_1$ and $b_2$) for the case (Top) would be as follows:

If $b_1$ is a variable $y_1$,

If $y_1=x_1$, the hypothesis becomes $(\lambda x_1.x_1)a_1\rightarrow a_1=b_2[a_2/x_2]\leftarrow (\lambda x_2.b_2)a_2$, and we indeed have $(\lambda x_1.x_1)a_1=(\lambda x_1.x_1)(b_2[a_2/x_2])\leftarrow (\lambda x_1.x_1)((\lambda x_2.b_2)a_2)\rightarrow (\lambda x_2.b_2)a_2$.
If $y_1\not=x_1$, then we can simply use (Throw).

The same proofs apply is $b_2$ is a variable.
For $b_1=\lambda y.c_1$ and $b_2=\lambda y.c_2$, the hypothesis becomes $(\lambda x_1.\lambda y. c_1)a_1\rightarrow \lambda y.c_1[a_1/x_1]=\lambda y.c_2[a_2/x_2]\leftarrow (\lambda x_2.\lambda y.c_2)a_2$ and the induction hypothesis gives $d$ such that $(\lambda x_1.c_1)a_1\leftarrow d\rightarrow (\lambda x_2.c_2)a_2$ which implies that $\lambda y.(\lambda x_1.c_1)a_1\leftarrow \lambda y.d\rightarrow \lambda y.(\lambda x_2.c_2)a_2$. Unfortunately, we do not have $\lambda y.(\lambda x_2.c_2)a_2\rightarrow (\lambda x_2.\lambda y.c_2)a_2$. (This makes me think of $\sigma$-reduction.)
A similar problem arises for applications: the $\lambda$s are not where they should be.

Two counterexamples are:

$(\lambda x. b x (b c)) c$ and $(\lambda x. x x) (b c)$ (Plotkin).
$(\lambda x. a (b x)) (c d)$ and $a ((\lambda y. b (c y)) d)$ (Van Oostrom).

The counterexample detailed below is given in The Lambda Calculus: Its Syntax and Semantics by H.P. Barenredgt, revised edition (1984), exercise 3.5.11 (vii). It is attributed to Plotkin (no precise reference). I give an incomplete proof which is adapted from a proof by Vincent van Oostrom of a different counterexample, in Take Five: an Easy Expansion Exercise (1996) [PDF].

The basis of the proof is the standardization theorem, which allows us to consider only beta expansions of a certain form. Intuitively speaking, a standard reduction is a reduction that makes all of its contractions from left to right. More precisely, a reduction is non-standard iff there is a step $M_i$ whose redex is a residual of a redex to the left of the redex of a previous step $M_j$; “left” and “right” for a redex are defined by the position of the $\lambda$ that is eliminated when the redex is contracted.
The standardization theorem states that there if $M \rightarrow_\beta^* N$ then there is a standard reduction from $M$ to $N$.

Let $L = (\lambda x. b x (b c)) c$ and $R = (\lambda x. x x) (b c)$. Both terms beta-reduce to $b c (b c)$ in one step.

Suppose that there is a common ancestor $A$ such that $L \leftarrow_\beta^* A \rightarrow_\beta^* R$. Thanks to the standardization theorem, we can assume that both reductions are standard. Without loss of generality, suppose that $A$ is the first step where these reductions differ. Of these two reductions, let $\sigma$ be the one where the redex of the first step is to the left of the other, and write $A = C_1[(\lambda z. M) N]$ where $C_1$ is the context of this contraction and $(\lambda z. M) N$ is the redex. Let $\tau$ be the other reduction.

Since $\tau$ is standard and its first step is to the right of the hole in $C_1$, it cannot contract at $C_1$ nor to the left of it. Therefore the final term of $\tau$ is of the form $C_2[(\lambda z. M') N']$ where the parts of $C_1$ and $C_2$ to the left of their holes are identical, $M \rightarrow_\beta^* M'$ and $N \rightarrow_\beta^* N'$. Since $\sigma$ starts by reducing at $C_1$ and never reduces further left, its final term must be of the form $C_3[S]$ where the part of $C_3$ to the left of its hole is identical to the left part of $C_1$ and $C_2$, and $M[z \leftarrow N] \rightarrow_\beta^* S$.

Observe that each of $L$ and $R$ contains a single lambda which is to the left of the application operator at the top level. Since $\tau$ preserves the lambda of $\lambda z. M$, this lambda is the one in whichever of $L$ or $R$ is the final term of $\tau$, and in that term the argument of the application is obtained by reducing $N$. The redex is at the toplevel, meaning that $C_1 = C_2 = C_3 = []$.

If $\tau$ ends in $R$, then $M \rightarrow_\beta^* z z$, $N \rightarrow_\beta^* b c$ and $M[z \leftarrow N] \rightarrow_\beta^* (\lambda x. b x (b c)) c$. If $N$ has a descendant in $L$ then this descendant must also reduce to $b c$ which is the normal form of $N$. In particular, no descendant of $N$ can be a lambda, so $\sigma$ cannot contract a subterm of the form $\check{N} P$ where $\check{N}$ is a descendant of $N$. Since the only subterm of $L$ that reduces to $b c$ is $b c$, the sole possible descendant of $N$ in $L$ is the sole occurrence of $b c$ itself.
If $\tau$ ends in $L$, then $M \rightarrow_\beta^* b z (b c)$, $N \rightarrow_\beta^* c$, and $M[z \leftarrow N] \rightarrow_\beta^* (\lambda x. x x) (b c)$. If $N$ has a descendant in $R$ then this descendant must also reduce to $c$ by confluence.

At this point, the conclusion should follow easily according to van Oostrom, but I'm missing something: I don't see how tracing the descendants of $N$ gives any information about $M$. Apologies for the incomplete post, I'll think about it overnight.


Show this language is non-regular using pumping lemma: B = {ww | w ∈ {a,b,c,...,z)*} The question I'm working from is:

Prove whether or not a finite automation exists that recognises the following language:

B = {ww | w ∈ {a,b,c,...,z)*}

EDIT

So I believe this is a non-regular language. My understanding of pumping lemma is not great but this was my solution:

S = apbapb

Where S is a valid string in the language and p is the pumping length.

S = aaaabaaaab for example when p = 4

S = xyz // s can be split into xyz components

| x y | <= p

SO y must be all a's before the first b e.g. a | aaa | baaaab

xy2z = aaaaaaabaaaab

xy2z is not in B

Therefore B is not regular

Apparently though this is wrong, please could someone explain why / how to obtain the right answer?

Your proof using the pumping lemma is wrong. You choose a pumping lemma constant $p=4$ but what happens if $p=5$ works? The pumping lemma tell us that there exists a constant $p$. Now you have to try all the remaining possible values of $p$.

I recommend you to study carefully the pumping lemma first. It is a bad idea to try using it without understanding it. After that if you want to assimilate it more you can check this answer: https://cs.stackexchange.com/a/50618/31129 where I explain some common mistakes.


Is this language in $PSPACE^{L'}$? Let's assume we have an arbitrary language $L'$ and let's define the language $L = \{1^n | \text{The number of strings in } L' \text{ of length } n \text{ is odd }\}$.

Is $L\in PSPACE^{L'}$?

I tried saying that I can define a determinstic machine that holds a counter and that goes over all possible strings of length $n$, which is $2^n$, and for each such string it asks the oracle whether it is in $L'$. If yes it increases the counter, and if not, it does not. Then, at the end, checks if the counter is odd, and accepts if so. Else, it rejects.

The problem is that even in $PSPACE$ I can not go over all strings since that would not be a polynomial amount of space, except if I am allowed to override the previous string I checked and that would count only as $n$ space, but I am not sure..

Another part of the question asks if $L \in NP^{L'}$, but that clearly is not the case.

Yes it is, by exactly the argument you give. Looping over all possible strings of length $n$ requires only $n$ tape cells – you can do it by treating the length-$n$ strings as numbers in base $|\Sigma|$, so looping through those is essentially a counter, too. You can reuse the space since you don't care about strings that you've already tested. Testing if the string you just made is in $L'$ takes space $n$ on your oracle tape. Implementing the counter requires only $O(n)$ bits, since you only need to store a number in the range $0, \dots, |\Sigma|^n$. So the total amount of space required is linear in $n$.

In fact, you can do slightly better, though the total will still be $O(n)$ because of the need to loop through the length-$n$ strings.  You don't need to count how many strings in $L'$ you've seen so far; you just need to know if that number is odd or even.


Is the validity of some instance of an equational problem decidable? Is the following FOL-problem (equality is a logical symbol)
effectively decidable?

Given.  A finite equation system $E$ and an equation $s = t$.

Question.  Is there a substitution $\sigma$, such that $\sigma(E)
\models \sigma(s = t)$?

Some useful information.

Obviously one can restrict $\sigma$ to be a ground substitution.
This problem is decidable:  Given a finite system $E$ of
ground equations and a ground equation $s = t$, does $E \models s = t$
hold? (c.f. [1: Corollary 4.3.6])

References

[1] Franz Baader, Tobias Nipkow: Term Rewriting and All That,
© 1998 Cambridge University Press.

This problem is known as rigid E-unification. This problem is NP-complete. The first proof was given by Gallier, Narendran, Plaisted and Snyder [1].

However a related problem, the Simultaneous rigid E-unification that is to find a substitution that simultaneously satisfies several instances of rigid E-unification is undecidable. This result was proved by Degtyarev and Voronkov [2].

References

Jean H. Gallier, Paliath Narendran, David A. Plaisted, Wayne Snyder: Rigid E-Unification: NP-Completeness and Applications to Equational Matings Inf. Comput. 87(1/2): 129-195 (1990)
Anatoli Degtyarev, Andrei Voronkov: The Undecidability of Simultaneous Rigid E-Unification. Theor. Comput. Sci. 166(1&2): 291-300 (1996)


Does a coin tossing algorithm terminate? Suppose we have an algorithm like:

n = 0
REPEAT
  c = randomInt(0,1)
  n = n + 1
UNTIL (c == 0)
RETURN n

(Assumuing the random number generator produces "good" random numbers in the mathematical sense.)

I understand that there is no number $n \in \mathbb{N}$ such that the algorithm is guaranteed to terminate after fewer than $n$ steps. However, the probability of terminating after some finite number of steps is 1.

Is there a convention among computer scientists to call an algorithm like this either "terminating" or "non-terminating"?

The formal, unambiguous way to state this is “terminates with probability 1” or “terminates almost surely”. In probability theory, “almost” means “with probability 1”.

For a probabilistic Turing machine, termination is defined as “terminates always” (i.e. whatever the random sequence is), not as “terminates with probability 1”. This definition makes decidability by a probabilistic Turing machine equivalent to decidability by a deterministic Turing machine supplied with an infinite tape of random bits — PTM are mostly interesting in complexity theory. In applied CS, though, computations that always give the correct result but terminate only with probability 1 are a lot more useful than computations that may return an incorrect result.


CPU and GPU differences What is the difference between a single processing unit of CPU and single processing unit of GPU?
Most places I've come along on the internet cover the high level differences between the two. I want to know what instructions can each perform and how fast are they and how are these processing units integrated in the compete architecture?
It seems like a question with a long answer. So lots of links are fine.

In the CPU, the FPU runs real number operations. How fast are the same operations being done in each GPU core? If fast then why is it fast?
I know my question is very generic but my goal is to have such questions answered.

This are not Real numbers as $\mathbb{R}$, but at this point - CPU has double precision floating point numbers, GPU very low number of units processing them, floats on GPU are halfs.
This is due to graphics (this was the main goal before parallel processing), where results are rounded to display, so speed vs accuracy tradeof went that way.
GPU core frequencies are smaller than CPUs, number of operations is very limited on GPU (boosted by video decoder), and there is a huge difference in branch prediction - CPU has very long and complex prediction, while GPU just recently got it added.

Single core on GPU: it is Streaming Multiprocessor (there are about 4 - 16 per card), it includes cuda cores (which is about 32-64), and they work in lock-step, so it differs from CPU threads (not locked).

It is hard to compare like this, but in short - single core on GPU is still parallel unit working slower than CPU core, less memory, registers and instructions than CPU, with very short branching prediction and preferable half floats, nowadays normal floats but having about one-two processing units for double precision, some time ago integer operations were slower on GPU (not onlu by frequency) - but this changed recently.

The same operation on floats - they are slower on GPU than CPU due to frequency.

You might be interested in AMD architecture, Nvidia architecture and Intel architecture to compare instructions set and hardware differences further.


Can all optimizations be expressed in source code? If someone compiled a program with all optimization settings enabled, would it be possible to create source code that, if it was compiled with all optimizations disabled, produced an identical binary? We'll assume that inline assembly and similar features are not used. If this is not always possible, (and I suspect it probably isn't) what language features or particular types of compiler optimizations make "fully pre-optimized" source code impossible?

The key to remember is that, at its core, a compiler is just a translator between two languages. One is often machine code, and there may be some intermediate steps, but translation is the key.

With that in mind, an optimization is one of three things:

A transformation from source programs to source programs, that is (hopefully) observationally equivalent to the original program, that is (hopefully) faster
A transformation from source programs to target that takes advantage of some property of the source program to generate code that is equivalent to, but faster than, the "vanilla" compiled version of the code.
A transformation from target programs to target programs that produces equivalent but faster code.

(3) could happen after compilation, since it doesn't rely on source input at all, and (1) could happen in an interpreted language as much as a compiled one.

Naturally, (2) can encompass programs that can't necessarily be expressed in the source language. It all depends the properties of your transformation. Is it a surjection between your source and target languages?

If it's not surjective, and both languages are Turing Complete, then:

There must be some programs in the target language which are never the result of compilation
Each "unreached" target program is equivalent to some source program (since both languages are Turing Complete)

Some of these will likely be optimizations.

For some practical examples:

Tail-call elimination is not expressible as a source-to-source transformation in any language with higher-order functions lacking GOTO
Any optimization using a "special" CPU instruction can't be expressed as a source-to-source transformation, since there's no way to access that instruction from the source language.

There are likely many more. (Community: feel free to add examples as you see fit!)


Computational Complexity and P vs. NP, A New Insight There is a preprint on arXiv that states (in my own words).

If there are three numbers (digits) and task is to add all three numbers. First we well take two number to add, set aside third number.  Then we will add third number in previous sum of two numbers. So, addition of three number requires two steps, because we cannot interact and manipulate more than two numbers in single instant. Our limitation to interact with only two number in single step has played very important role. This is one of reasons why Math axioms involve only two number e.g a.0=0, b.1=b etc…Similarly we cannot sort more than two numbers in single step.  If there is a system that can sort three objects in single step it will be 200% more time efficient.  The kind of sorting that involves three numbers in single step is not possible by humans or man-made machines (not even Turing machines ). But one such system is explained in the paper along with consequences.

The paper concludes

“It can be stated explicitly that computational complexity appears because of Mathematical Axioms that are constrained by and based on human cognitive limits as human cannot interact with more than two numbers at an instant”

Is above statement right?

Preprint Link
https://arxiv.org/abs/1711.10874

No.  The paper appears to be total baloney.   I noticed multiple unjustified statements in my first 60 seconds reading the paper.  Don't waste your time with it.

arxiv is not peer-reviewed.  Some papers on arxiv are great; some papers are arxiv are terrible and a waste of time.  Its presence on arxiv says very little about its quality.  It's like finding a paper on someone's personal website.


Validity of predicate logic formulas 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.

Not a counter model, for as you say, the antecedent is not true when $x = 0$.
A counter model:  Every number has a number less than it in $\mathbb{R}$, however there are no least number.
A counter model:  For $x$, let $y = 1/x$, so the antecedent holds, there is no $y$ such that for all $x$, we have that $x \cdot y = 2$.
Not a counter model:  The consequent is always true, let $y = \epsilon$, then for all $x$, it holds that $yxy = x$.


Minimum spanning tree such that one edge can be minimised During a computer coding exam, I have encountered such a problem.

Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the vertexes such that the sum of the lengths of the edges is minimal, provided that you may subtract any one edge of your choice in the tree by the positive number D and reduce the weight of that edge to max(0, weight-D)?

I know that Kruskal's and Prim's algorithm can all be used to solve the first part of the problem, the minimum spanning tree, and I can do it. However, I have been struggling hard for the second part, as I don't know how to minimise the weight of the tree given the number D.

In the following, I assume the set of all feasible solutions is the set $\{(T,uv):T$ is a not necessarily minimum spanning tree of $G$ and $uv$ is a distinguished edge in $T\}$, with the cost of a particular solution $(T,uv)$ being the sum of the edges in $T$ minus $\min(D,w(uv))$.

Let $(T, uv)$ be an optimal solution to the problem you describe, having weight $\sum_{xy \in E(T)} w(xy) - s$, where $s = \min(D, w(uv))$.  There are two possibilities:

Every MST of $G$ contains at least one edge of weight $\ge s$.
At least one MST of $G$ contains no edge of weight $\ge s$.

Case 1

For case 1, we can take any MST $T'$, find an edge in it with weight at least $s$ (since we know by assumption that this exists), and produce a solution having weight at most $\sum_{xy \in E(T')} w(xy) - s$.  This is at most the weight $\sum_{xy \in E(T)} w(xy) - s$ of the optimal solution $(T, uv)$, since $\sum_{xy \in E(T')} w(xy) \le \sum_{ab \in E(T)} w(ab)$ for any tree $T$ by definition of the MST.  That means that for case 1, we can never miss an optimal solution by considering only MSTs.

Case 2

For case 2, consider the edge $uv$ in $T$, which has weight at least $s$.  Let the vertices on one side of this edge be $A$, and the vertices on the other side $B$.  By assumption, there exists an MST in which every edge has weight strictly less than $s$.  In particular, this MST must contain an edge $u'v'$ between the vertex sets $A$ and $B$ having weight strictly less than $s$, since otherwise the MST would be disconnected -- a contradiction.

Suppose $w(uv) > D$.  Then the original solution $(T, uv)$ has weight $X - D$, with $X$ being the weight of the entire tree $T$, while the solution formed by replacing $uv$ with $u'v'$ has weight $X - w(uv) < X - D$.  This contradicts optimality of $(T, uv)$, so it must be that in fact $w(uv) \le D$, in which case both the original and new solutions have weight $X - w(uv)$.  Thus the new solution has weight equal to the old solution, but now falls into case 1 above.

Wrapping up

Since there are only two possible cases for an optimal solution, and in both cases an MST can always be found that leads to a solution that is just as good, it always suffices to find an MST.

The final step is to choose an edge in the MST to minimise.  Clearly it is always optimal to choose the heaviest edge in the MST.


What is the fastest algorithm to check whether input table is a group? Given an input table with binary operation $\circ$. I want to check whether given input table represents a group or not.

I need to verify the four axioms of a group.

The identity I can find it by just scanning the first row of the given table. -----$\mathcal{O}(|G|)$ running time.
Find the closure operation ie.e for any $x,y \in G$, I need to show that $x \circ y \in G $.------$\mathcal{O}(|G|^2)$
An inverse of an element.----$\mathcal{O}(|G|^2)$ Running time.
Associativity operation. -----$\mathcal{O}(|G|^3)$

Which gives me a $\mathcal{O}(|G|^3)$ running time algorithm to check whether the input table corresponds to some group.

Question : What is the fastest algorithm to check whether the input table is a group?

Model of computation is RAM, which computing $x \circ y$ takes constant time.

There is a non-trivial randomized algorithm that can solve this in $O(n^2 \log (1/\delta))$ time, where $\delta>0$ is the desired error probability.  See

Verification of Identities.  Sridhar Rajagopalan and Leonard J. Schulman.  SIAM Journal on Computing, 29(4), pp.1155-1163.


Construct a PDA for at least one $w_i$ $\neq$ $w_{i + 1}^r$? My assignment asks
Let $S =
\{
w_1\#w_2\# \dots \#w_k | k ≥ 2; (∀i ≤ k)w_i ∈ \{0, 1\}^\star
; (∃i < k) w_i\neq w_{i + 1}^r$
, i.e., not every string $w_i$ is equal to the reversal of $w_{i+1}$. Note $S ⊆ \{0, 1, \#\}^\star$.

Show that S is a CFL by a PDA, P, that accepts it.

I have been stuck on this question for approximately 20+ hours. I tried to sketch the PDA about 20 pages but still fail some cases. My friend's suggestion as store the word $w_i$ then the next state is to compare $w_{i + 1}$ to $w_i$, however, what I'm struggling is how do we compare $w_{i + 2}$ to $w_{i + 1}$ after comparing $w_{i + 1}$ to $w_{i}$. This seems impossible since the stack has to be pop out an element in order to compare the previous word. Once it's empty, we can never fill up the stack with the same elements that already popped.

Another way that I found is referring to this link:
https://cseweb.ucsd.edu/classes/su99/cse105/hw2sol.pdf.

On question 3, it has a construction for non-palindrome over $\{0,1\}^\star$. Which is similar to our case but we have a $\#$ sign between words. I.e., we have many different strings instead of this construction only need to handle one string and compare it's left and right. I have been stuck for a long time, I think I'm missing something here. Any suggestions?

Use nondeterminism to guess an index $i$ for which $w_i \neq w_{i+1}$. The machine reads its input until it nondeterministically chooses a $w_i$ and places it on the stack. Afterwards, it compares $w_{i+1}$ to the content on the stack symbol by symbol. If the comparison fails, the machine accepts.


Difference in scale between mean page loading times and exponentially distributed page loading times? Apologies if this is the wrong place to ask.

For my experiment, I have a single-page application and a multi-page application. I am testing them with an exponential distributed delay throttling. The idea is that individual chunks are delayed by a random number sampled from an exponential distribution. So, when a HTTP/GET request comes in, it gets split into 200 byte chunks and each chunk is delayed. Basically each request for a resource e.g. HTML/CSS/JS is a sum of exponential distributed delays.

Now, when I did a test of a 100 page loads and got the mean.

My question is why is the SPA vs MPA without delay, SPA is around 4 times faster but then SPA vs MPA with delay is only 2 times faster?

No delay:

With delay:

Edit: The mean exponential parameter is 1 (second). The multi-page app total size transferred is significantly smaller (58KB), than single-page app (267KB) which due to the JavaScript framework, so it is expected to load faster. SPA also has more files to download, therefore more round-trips.

To do a simulation:

User visits a website from his browser, he makes a HTTP request for the root HTML first, which makes subsequent requests for style sheets and scripts to load the page.
Taking the first request for the root HTML, (for specific details) this TCP stream is fed into a SOCKS server before going out to the web server. The stream takes 200 byte chunks at a time and delays it, (and without blocking) keeps taking another chunk and delays it. It also checks if any previous chunk will overlap, if so it will send it out the same time.
The web server gets the delayed request and sends a reply back (in this case the HTML file) to the SOCKS server, where it will delay it again.

At step 2, say we have a 1000 byte stream, it will take 200 byte and delay it in the background, take another 200 byte and delay that in the background too, and keep doing it. Meanwhile it will check overlaps, so if the first chunk has a delay (plus current time) that is greater than the delay (plus current time) of the second, meaning the second will get sent first. We want to delay the second chunk the same time, so it gets sent in order.

I hope that makes sense. Please let me know if it doesn't.

The time to load a web application is a sum of multiple factors, including at least:

The round-trip latency to initiate a TCP connection to the server (or maybe multiple connections, depending on your application and your browser) -- also called RTT time.
The time to download all of the page and content that it causes to be downloaded.

The second factor depends on the amount of delay you're adding; the first doesn't.  Also, the multi-page application might cause more TCP connections, causing more of the first type of delay; but it downloads less data, so less of the second delay.

So there's no reason to expect things to scale as simply as you are expecting.  Instead, the resulting performance will be a more complicated function of page size, RTT time, and delay.

Heuristically, we can expect a RTT time of a few hundred milliseconds per TCP connection, though that will depend on how far the client is from the server.  You say there's an average delay of 1 second per 200 bytes downloaded, so for the single-page application, you expect 267KB / 200bytes = 1367 seconds of delay added, on average, due to your artificial delays; for the multi-page application, you expect 58KB / 200bytes = 297 seconds of delay added, on average.  Without the artificial delays, the time to download that much data might depend on the speed of your network.


Minimum cost of wood for woodworking project problem This is a fun one, I really can't wrap my head around it. It's like an n-sum problem combined w/ a knapsack problem and I cant seem to find a solution.
I'm currently building a cabinet, and had just enough wood that if I calculated my cuts right, I would've had enough, if I had even cut one certain length from one board instead of another, Id have needed an extra length of wood and would have to go back to the store. And it made me start thinking about if there is a non brute force solution for calculating the minimum amount of wood lengths I needed.
Then started to think about it further, given a bin of infinite lengths of wood in various lengths. Ie: infinite 96", infinite 72", etc, and a cost for each. What would be the minimum cost of wood I'd need to buy.
So the problem would be like, given lengths of wood that have a certain price:
{ cost: 3, length: 96 },
{ cost: 2, length: 72 },
{ cost: 4, length: 144}

And a list of cuts (lengths) needed,
[ 24, 24, 24, 24, 48, 48, 48, 48, 36, 36, 36, 36 ]

What would be the cheapest combination of wood pieces I could buy and still have enough wood.
(Lets assume that we do not have to take into account the amount of wood lost during a cut due to the width of the blade)

As D.W. rightly pointed out, it is a generalisation of the knapsack problem. Its closest relative is probably the cutting stock problem, where the goal is to minimise waste.
The cutting stock problem is typically solved using a (quite natural!) translation to integer linear programming. That seems like the best bet for your problem, too.


Can a DPDA decide if two letters appear the same number of times mod 5? $ L = \{ w  ∈\{0,1\}^* \mid      |w|_0 = |w|_1 \mod 5 \}$

So i tried figuring out why this is CFL and whether its DCFL or not but i couldn't come up with any PDA!

I'm studying for my exam and this was on the book, the book says its CFL but doesn't say whether its DCFL or not and does not draw any PDA for it!

i tried making 5 states and go to the next state everytime i see a 0 {because 0 will always be between 0 and 4} but didn't work

also $|w|_0$ means number of 0's

What does $|w|_0 = |w|_1 \mod 5$ means ?
It could either mean (depending on your book's notations) :

$\exists k\in\mathbb Z, |w|_0 + 5k = |w|_1$
The remainder from the Euclidean Division of $|w|_1$ by 5 is $|w|_0$

Let's first resolve the first case. You should accept if and only if  5 divides $|w|_1 - |w|_0$. This can be done with a finite automaton with 5 states, to keep track of $|w|_1 - |w|_0\mod 5$ and only accepting when it is in state 0 (I'll let you find the transitions).

In the second case, you need to also ensure that the value of $|w|_0$ never goes beyond 4. That can be done by copying the same finite automaton as above 4 times, fixing the transitions accordingly (I would recommend to try doing that) and adding a "trash state" to go to if you have read more than four 0.

So we have deterministic finite state automata for both those languages. Finite state automata are just specific cases of PDA where you never use the stack. So there you have a DPDA for each of those languages.

Another way to do this, which is probably what the author was looking for, is to try to build a grammar. Hint : such a grammar has 5 non-terminal symbols, 2 terminals symbols, and 11 rules (this is for the first case).
Those two constructions are equivalent though.


Does a multi-agent system have to have a synchronous component in order for the agents to cooperate? During my programming assignments in multi-agent systems, I noticed that it feels impossible to get distributed agents to cooperate without a synchronous component. Let me explain what I mean by these terms:

Cooperation: I would loosely define this as any process which a single agent cannot solve without receiving non-static information from one or more other agents.

Example: Consider a system where two identical agents are needed to change a lightbulb. One agent needs to change the lightbulb itself, and one needs to hold the ladder.

Naturally, the problem is how to decide which agent is going to be the lightbulb changer and which the ladder holder. I have somehow arrived at the conclusion that this is impossible without the presence of a synchronous component in the system.

Without such a component, the agents could always get into an inconsistent state - for example, both would consider themself the holder, no matter how you decided how to assign those roles - if you were to choose, for example, a message sending system, where an agent would send to another "I will change the bulb, you hold the ladder", they could still send such a message at the same time. Similarly, if there was to be a "Leader" of those agents who would assign those roles, how would you decide which one was to be the leader? You just move the problem up a level.

Therefore, such problems are normally solved by methods such as assigning an unique integer identifier to each agent, and deciding based on this value (agents with higher value will become the leader, etc). Similarly, I have seen people use things like the time of the agent's entry into the system, the position of the agent in the environment, and so on.

However! All of those things are what I consider to be a synchronous component. Some entity has had to synchronously decide them - there is only a single time, a single person who assigns the identifiers, a single universe by which the agents' locations are defined, and so on.

I am pretty sure this statement holds. My question is: does there exist a theorem which states this or something similar (one that has been formally proven)?

You're asking about a problem known as leader election.  There are various computational models one can consider, based on what we assume about how the network works and what agents are allowed to do.

The Wikipedia article claims there are no deterministic algorithms for leader election in a setting where all agents start from the same state (have no identity) and are situation in a ring (so connectivity is symmetrical); see https://en.wikipedia.org/wiki/Leader_election#Anonymous_rings.

At the same time, there are randomized algorithms for leader election that work if we make some assumptions about network delay (e.g., that messages won't be delayed forever), and if you're willing to accept algorithms with a finite expected running time.  For instance, a very simple starting point is for each node to pick a random number and broadcast it, and then select the agent with the lowest number as the leader.  In case of ties, repeat the entire procedure.  There are additional details one must work out, depending on the model of computation and the assumptions about communication.

There's lots of research on this topic in the distributed systems literature.  You might want to spend some time reviewing the papers that have been published in that field, to see what you can find.


Binary search in log time on a Turing Machine I was thinking about TM (Turing Machine) as a computation model, and I came up with the following question :

Is it possible to make a TM that answers binary search (tell wether $x$ belong to a sorted array $A$) in $\log$ time ? That is, is it possible to simulate random access on a TM ?

My thoughts so far are that it is not possible, because the memory of a TM has to be accessed sequentially, e.g. in binary search, reading the element at $n/2$ in the array (first comparison for binary search) takes at least $n/2$ steps.

If it is indeed impossible, does the same hold for structures like binary trees ?

Can't be done.

Assuming the TM receives its input as $\langle x, A \rangle$ (i.e., $x$ followed by $A$) and that $x$ as well as the array contents are binary encoded, then the asymptotic log-time bound ensures almost all inputs are such that the TM is not even able to read past $x$, let alone search the array. Even if you bound the contents of the array (i.e., a constant number of values, one value per cell), the TM can only read up to the first $\log n$ entries for a list of size $n$; searching for an $x$ strictly larger than those entries will fail.

I am not sure how you intend to represent binary trees (with pointers?). I am sure it is the same case as above.

That being said, there are models which add random access capabilities to TMs, in particular random-access TMs. You might want to look into those.


How does malloc(sizeof(char)) work AFAIK, malloc(sizeof(char)) is intended to allocate a 1-byte block of VM and strcpy requires that

  the destination string dest must be large enough to receive the copy

That means theorically that if the length of src is strictly upper to 1, the strcpy operation fails, and it's impossible to copy more than one character to src.

However, the following code shows a counterexample, where 27 characters gets copied to s (including the '\0') as the program displays:

  s length = 26

int
main()
{
  const char *msg = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
  char *s = malloc(sizeof(char));

  strcpy(s, msg);

  printf("%s\n", s);
  printf("s length = %i\n", strlen(s));
  printf("msg length = %i\n", strlen(msg));
}

So, why malloc(sizeof(char)) allocates 27 characters contrarily to what it is intended to allocate theorically? How does this allocation work?

Quick note, sizeof(char) is defined to be 1. So you can just simplify to malloc(1).

The real answer however is quite boring. Your program has what's so called undefined behavior. In C (and C++), if you make an error like this the result is undefined. This could mean that your program will crash right as you trigger the bug. But it doesn't necessarily crash. It might do what you expect. It might format your hard drive and kill your cat. Whatever happens is fair game according to the C standard. Because you triggered undefined behavior.


Proving $(a+b)^* = b^*(ab^*)^*$ equationally I am new to automata theory and have a problem in understanding equivalence of regular expressions, though I can go for the construction procedure of minimized DFAs to prove that both are equal.

I need to prove the following property using different Kleene star properties:

$$(a+b)^* = b^*(ab^*)^*$$

A report by Aceto contains an axiomatization of the equational theory of regular expressions, called "classical" by Conway (Table 1 on page 5). One of the axioms is very similar to what you're after: $(a+b)^* = (a^*b)^*a^*$. Using these axioms, we can derive your identity as follows (using associativity (C3, C10) for free):
$$
\begin{align*}
(a+b)^* &= (b+a)^* && C2 \\
&= (b^*a)^*b^* && C11 \\
&= (\epsilon+b^*(ab^*)^*a)b^* && C12 \\
&= b^* + b^*(ab^*)^*ab^* && C9 \\
&= b^*(\epsilon + (ab^*)^*ab^*) && C8 \\
&= b^*(\epsilon + \epsilon(ab^*\epsilon)^*ab^*) && C6,C7 \\
&= b^*(\epsilon ab^*)^* && C12 \\
&= b^* (ab^*)^* && C7
\end{align*}
$$


Min weighted edge cover - is the greedy algorithm sub-optimal? The post here: Solving the min edge cover using the maximum matching algorithm provides a way to obtain the min edge cover from a maximum matching by greedily adding edges on top of the maximum matching until all vertices are covered. Now, thinking about the min-weighted edge cover problem, it would seem this approach can be extended. First, find the minimum weighted matching with maximum edges, and then add edges of the smallest weight greedily, smallest weight ones first.
However, reading section 19.3 of the book "Combinatorial optimization: polyhedra and efficiency" by Schrijver, a more complicated algorithm is presented. This makes it seem like my approach above is sub-optimal. Is it possible to find a counter-example, preferably on a bi-partite graph where my greedy algorithm would fail to provide an optimal solution? I haven't been able to find one with some toy graphs.

Here is a counterexample to your proposed algorithm:

The optimal solution consists of 3 edges and costs 3+1+1=5, but the min-cost maximum-cardinality matching, which consists of 2 edges and costs 3+3=6, will be chosen by the first step of your algorithm and immediately returned, as it is already a solution. (The only other maximum-cardinality matching costs 1+6=7.)


Which Peterson’s Solution is right? I have seen two different Peterson’s Solution to mutual exclusion, one is from Modern Operating Systems:

#define FALSE 0
#define TRUE 1
#define N 2

int turn;
int interested[N];

void enter_region(int process)
{
    int other;
    other = 1 - process;
    intersted[process] = TRUE;
    turn = process;
    while(turn == process && interested[other] == TRUE);
}

void leave_region(int process)
{
    interested[process] = FALSE;
}

The other is from Operating System Concepts:

while (true) {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j)
        ;
        /* critical section */
    flag[i] = false;
        /*remainder section */
}

But they are different. The first one set turn to itself, while the second one set turn to the other. The following while condition also has the same difference. After googling around, I think the second one is right, but not sure.

Both versions of Peterson's algorithm are correct.

The version at Operating System Concepts (OSC) is slightly better if you would believe the natural meaning of turn as whose turn it is to enter the critical section or who has the priority to enter the critical section. The version at Modern Operating Systems (MOS) is slightly better for its better variable name interested.

Let us verify that the two versions are equivalent to each other. Let us rename the variable turn in the version at MOS to wait, (which should be a better name for that variable), meaning who should be waiting or who should yield to the other process regarding entering the critical section. Now you can see two versions are similar. The version at MOS say that the current process intends to wait behind the other process when it sets the wait to be itself and checks its value later. The version at OSC says the other process should have the turn to enter the critical section when it sets the turn variable to the other process and checks its value later. Now you can feel that those two versions seems doing the same thing.

To go a step further, after we have renamed turn to wait in the version at MOS, let us further imagine that the way the computer for MOS implements wait=0 is actually set some memory location to 1 and will name that location as turn'. It will implements wait=1 as setting that location turn' to 0.  Also when it checks wait == 0 it actually checks turn' == 1. When it checks wait == 1, it actually checks turn' == 0. Other than this particular implementation for the wait variable, this computer is completely the same as another computer that runs the version at OSC. Now if you skip the intermediate syntactic step that set or check wait and view turn' at the computer for MOS as equivalent to turn at the computer for OSC, (and rename several other variables), you can see they are actually executing the same code.

(In short, if you imagine that, only for the original wait variable at MOS version, 1 means 0 and 1 means 0, then you can see both version are executing same kind of code.)

Another way to see the equivalence of the two versions is to notice, as the questioner has noted, each version sets some variable to some value and then checks whether that variable is still that value. This variable is only used in these two places. There are only two values for that variable. It does not matter what is name of the variable or what are those two values. As long as the code sets some variable to some value and then checks whether that variable is still that value, that part of code has same behavior. Of course, this reasoning here is somewhat shady. It can certainly to help your understanding, though.

Every time we refer to Peterson's algorithm, it is obligatory to praise what a simple and great distributed algorithm it is. How deceptively simple it is and how smart it deals with the intricacy of concurrency!

For a much more complete understanding of the Peterson's algorithm and why it is indeed correct, please check The assertional versus Tarskian methods.


Length of mid part of the string in Pumping Lemma This statement of the pumping lemma from Wikipedia.

  Let $L$ be a regular language. Then there exists an integer $p \ge  1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = x y z$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:

  $\lvert y \rvert \ge 1$
  $\lvert x y \rvert \le p$ and
  for all $i \ge 0$, $x y^i z \in L$.
  $y$ is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in $L$).

What confuses me about the definition of pumping lemma are two requirements: $\lvert y \rvert \ge 1$  and $i \ge 0$, $x y^i z$. The way I read it, that we are required to have $y$ length be equal to one or greater, and at the same time, we can completely skip it, since $i \ge 0$, i.e. effectively  $\lvert y \rvert = 0 $.
Intuitively, it makes sense that we should be able to skip $y$ and still have string be in $L$.

Any finite state automaton that accepts an infinite number of words will necessarily have a loop in it. One such loop may go from state $q$ to state $q$ consuming word $y$ – that is, $y$ is the word based on the symbols on the transitions going from $q$ back to $q$.

The pumping lemma says, more or less, that you can get to such a state $q$ from the initial state by consuming the word $x$ and that you can get to the final state from state $q$ by consuming the word $z$. In the middle you can go through the loop as many times as you like. Thus making the complete word $xy^iz$, where $i$ is the number of times you chose to go through the loop.