Can the House Robber problem be solved with a Sliding Window solution? I was reading an article on how to solve sliding window problems and it said:

Fast/Lagging
This one is a little different, but essentially the slow pointer is simply referencing one or two indices behind the fast pointer and it’s keeping track of some choice you’ve made.
In the House Robber problem you are trying to see what the maximum amount of gold you can steal from houses that are not next door to each other. Here the choice is whether or not you should steal from the current house, given that you could instead have stolen from the previous house.

So, I tried to solve the House Robber problem using a Sliding Window (fast/lagging) solution.  It worked for a lot of test cases, but there were some that it just would not solve.
I came to the conclusion that it wasn't possible as the problem is recursive (you don't know whether to rob this house and next-door-but-one unless you know whether to rob next-door-but-one and next-door-but-one, unless you know whether... etc. etc.)
So, I clicked the Solution button on leetcode and the solutions presented were recursion and tabulation.
Is it possible to solve this problem using a 'sliding window'?

Yes you can! It's called dynamic programming, though.
Usually, the sliding window technique stores only information local to the window, but to make this work, you should store also the global solution up until the current window position.
What you store in a window (size 2?) is what the optimal solution is if you pick the last house of the window, and what is the optimal solution when you skip the last house of the window.
We call this technique dynamic programming, and not sliding window, although they have much in common.
P.S. this problem is also known as Independent Set in Path Graphs.

I don't know if you call this sliding window, but here is one way of solving it:
def window(data):
    if not data:
        return 0
    pick, skip = data[0], 0
    for window_idx in range(1, len(data)):
        pick, skip = data[window_idx] + skip, max(skip, pick)
    return max(pick, skip)

data = [14, 7, 11, 8, 13, 9, 10, 12]
print(window(data))  # 14 + 11 + 13 + 12 = 50


how does Kleene-Post show two languages that are not Turing reducible to each other? I'm having difficulty understanding the proof of the Kleene-Post result. It purports to construct two languages that are not Turing reducible to each other, using a diagonalization argument.
I've seen it in many places: for example a very brief summary here (where it is used to answer a different question about mapping reducibility), and also in page 2 here and also page 40 of here. There's also a prior thread on Kleene-Post, but that asks something very specific about one component of Kleene-Post, not how the entire proof works.
Very roughly speaking, it seems to be something about constructing a pair of sequences of languages (or sequence of sets of languages, I'm not too sure) such that for each "step" in the sequence, there's at least one oracle TM (i.e. a TM that is able to query some oracle) for which an oracle for one "side" cannot be used to decide the other "side". Once these sequences are done, we take the intersection of every element in the sequence, and by construction all the languages in this intersection will fail to be mutually Turing reducible by every single possible oracle TM.
While I believe the general argument follows the above, I don't understand the details at all, since the proofs I've linked to use terminology (e.g. recursive, characteristic function, etc.) that differs significantly from those used by Sipser, the textbook I'm following (e.g. Turing recognizable, Turing decidable). There's also a few other proofs I've seen which I have not linked, and in those proofs I found the notation and exposition still difficult to understand.
My question is: how does the Kleene-Post proof work? What are the details of the construction, presented carefully in a way that is unambiguous and easily understood, preferably using terminology from Sipser as opposed to equivalent but different terminology?

Unfortunately, I don't possess a copy of Sipser, so I will just define all my notation. Let $T_0,T_1,\ldots$ an enumeration of all oracle Turing machines whose input is a word over some alphabet $\Sigma$. I will denote by $T_i^O(x)$ the output of the execution of $T_i$ on input $x$ with oracle $O$, or $\bot$ if the machine doesn't halt. We say that $T_i$ (Turing-)reduces $A$ to $B$ if $T_i^B(x)$ halts for all $x$, and returns the truth value of "$x \in A$". We assume for simplicity that the output of $T_i^B(x)$ can always be interpreted as a truth value.
We will construct two sequences $A_0,A_1,\ldots$ and $B_0,B_1,\ldots$ of "partial sets", that is, mappings from $\Sigma^*$ to $\{0,1,\bot\}$. Initially, $A_0$ and $B_0$ map all strings in $\Sigma^*$ to $\bot$. Moreover, $A_{i+1}$ is an extension of $A_i$, that is, if $A_i(x)\neq \bot$ then $A_{i+1}(x) = A_i(x)$. Furthermore, each $A_i$ or $B_i$ is defined (not equal to $\bot$) for only finitely many words in $\Sigma^*$.
We will eventually take $A$ to be a set extending all $A_i$, that is, if $A_i(x) = 0$ for some $i$ then $i \notin A$; if $A_i(x) = 1$ for some $i$ then $i \in A$; and otherwise the status of $i$ doesn't matter (for definiteness, let $i \notin A$). The extension property guarantees that $A$ is well-defined. We define $B$ similarly.
We construct $A_{2i+1},B_{2i+1}$ from $A_{2i},B_{2i}$ in a way which rules out $T_i$ being a reduction from $A$ to $B$. By assumption, there exists $x \in \Sigma^*$ such that $A_{2i}(x) = \bot$. Consider what happens when we try to run $T_i$ on input $x$ with oracle $B_{2i}$. If $T_i$ tries to apply the oracle on a word $y$ on which $B_{2i}$ is defined, then it gets $B_{2i}(y)$. If $B_{2i}(y) = \bot$, then we simulate both branches in parallel (each of them could further split down the road). One of the following must happen:

There is a branch on which computation halts.
All branches result in non-halting computations.

The second case is easy – $T_i$ cannot be a reduction from $A$ to $B$, since it doesn't halt on input $x$, whatever happens in later stages of the construction. So we take $A_{2i+1} = A_{2i}$ and $B_{2i+1} = B_{2i}$.
In the first case, we actually have to do something. Pick a halting branch. The branch corresponds to a choice of definite values for some strings in $\Sigma^*$ on which $B_{2i}$ is undefined. We form $B_{2i+1}$ from $B_{2i}$ by keeping all values already defined in $B_{2i}$, and defining the additional strings occurring in the halting branch according to the branch. We form $A_{2i+1}$ from $A_{2i}$ by keeping all values already defined in $A_{2i}$, and defining $A_{2i+1}$ on $x$ in the opposite way to what $T_i$ answers in the halting branch: if $T_i$ outputs Yes then $A_{2i+1}(x) = 0$, and if $T_i$ outputs No then $A_{2i+1}(x) = 1$. This ensures that $T_i$ does not reduce $A$ to $B$, since it outputs the wrong value on $x$.
We construct $A_{2i+2},B_{2i+2}$ from $A_{2i+1},B_{2i+1}$ in a similar way, switching the roles of $A$ and $B$, ruling out $T_i$ being a reduction from $B$ to $A$.
Since the final $A$ and $B$ "encompass" all $A_i,B_i$, by construction no $T_i$ reduces $A$ to $B$ or $B$ to $A$, and so there is no Turing reduction from $A$ to $B$ or from $B$ to $A$.

The dichotomy above (some branch halts / all branches never halt) is not computable, in the sense that given $A_{2i},B_{2i},T_i$ we cannot determine which of the two options occurs. But it is possible using an oracle to the halting problem, since we can construct a Turing machine which tries out all branches in parallel, and immediately halts if one of them halts. Furthermore, by "going down the tree" we can find a halting branch if such exists. This shows that we can compute the sequences $A_i,B_i$ using an oracle to the halting problem.
Now suppose that when choosing a string $x$, then we always choose the first such string on which $A_{2i}$ (or $B_{2i+1}$) is undefined, according to some fixed ordering. This guarantees that any string will be eventually defined by some $A_i$ and by some $B_j$. Since the sequences $A_i,B_j$ are computable using an oracle to the halting problem, this shows that the sets $A,B$ are computable using an oracle to the halting problem.

Here is an alternative proof. Let $\mu$ be an arbitrary measure on languages such that $\mu(L) = 0$ for any specific language $L$ (we say that $\mu$ has no atoms). For example, $\mu$ could correspond to the experiment in which each word is put in the language with probability $1/2$ independently.
Let $\mathbf{A},\mathbf{B} \sim \mu$. The probability that $T_i$ reduces $\mathbf{A}$ to $\mathbf{B}$ is 0, since fixing the outcome of $\mathbf{B}$ to be $B$, there is at most one language $L$ which $T_i$ reduces to $B$, and by assumption $\mu(L) = 0$. Since there are only countably many machines $T_i$, it follows that the probability that $\mathbf{A}$ reduces to $\mathbf{B}$ is zero. Similarly, the probability that $\mathbf{B}$ reduces to $\mathbf{A}$ is 0. We conclude that almost surely (that is, with probability 1), $\mathbf{A}$ doesn't reduce to $\mathbf{B}$ and $\mathbf{B}$ doesn't reduce to $\mathbf{A}$. In particular, there exist realizations $A,B$ such that $A$ doesn't reduce to $B$ and $B$ doesn't reduce to $A$.


What does Bellantoni-Cook say about Cook-Reckov? In implicit complexity theory they construct natural programming languages that are complete for various complexity classes.

An example, while there are many others, is Bellantoni-Cook where they show that FP can be characterized by such a language (called system B).

What I'm wondering is what do successes such as Bellantoni-Cook in implicit complexity say about Cook-Reckov?

Cook-Reckov: There exists a polynomially bounded propositional proof system iff NP = coNP.

Are these languages not proof systems? Where the outputs are the propositional tautologies (or something like this).

Why does the successful construction of these languages not prove, by the Cook-Reckov theorem, that NP = coNP?

PS you could ask the same thing of descriptive complexity... why don't constructions like FO(LFP) (first-order logic with a least fixed point operator added to it, on ordered structures), by, again, the Cook-Reckov theorem, prove P=coNP? As P can be described as the problems expressible in FO(LFP) and it is a propositional proof system--how is this not the same thing as FO(LFP) is a polynomially bounded propositional proof system?

Thank you!

A polynomially bounded proof system is a function $M$ computable by an FP machine with the following properties:

For any $x$, the output $M(x)$ is a propositional tautology.
There exists a polynomial $p(n)$ such that for any propositional tautology $y$ there exists $x$ of size at most $p(|y|)$ such that $M(x) = y$.

Now suppose that you found a sophisticated way to describe all functions in FP, call it System R. This lets you come up with the following equivalent definition.

A polynomially bounded proof system is a function $M$ expressible in System R with the following properties:

For any $x$, the output $M(x)$ is a propositional tautology.
There exists a polynomial $p(n)$ such that for any propositional tautology $y$ there exists $x$ of size at most $p(|y|)$ such that $M(x) = y$.

As you can see, nothing has really been gained. We only changed "computable by an FP machine" with "expressible in System R".


DFA that accepts two more $1$'s than $0$'s What is the state diagram of a DFA that follows

$L = \{w \in \{0,1\}^*\mid w\text{ has at least two or more 1's than of 0's}\}$.

Examples: $110$ doesn't work, $1110$ works.

As mentioned this is not a regular language.

To prove this, recall that a language, $L$, is regular iff some DFA recognizes it.

We will show that no DFA recognizes $L$.
Consider the infinite set of strings $S=\{0^n : n \ge 0\}$.
Then any two strings in $S$ are of the form $\alpha=0^x$ and $\beta=0^y$, $x,y\ge0$, we may assume wlog that $x>y$.

Let $\lambda=1^{y+2}$.

Then $\alpha\lambda=0^x1^{y+2} \notin L$ (since $x>y \implies y+2 -x < 2$), but $\beta\lambda=0^y1^{y+2} \in L$.

Thus we have an infinite set of strings (prefixes), $S$, such that for every pair of distinct strings $\alpha,\beta \in S$ there exists another string (suffix) $\lambda$ where exactly one of $\alpha\lambda$ or $\beta\lambda$ is in $L$. Thinking about this, this means that if a DFA, $D$, recognizes $L$, then every string in $S$ must take $D$ to a different state (if $\alpha,\beta \in S$ both took $D$ to the same state then so would $\alpha\lambda$ and $\beta\lambda$ for any $\lambda$, but we know that only one of these strings is in $L$). So $D$ must have at least $|S|$ states, but $|S|=\infty$, thus $D$ cannot exist.


What defines a tool as a "compiler" I've been trying to figure out what technically makes a tool or program a compiler.

For example, I know that gcc will compile source code to object files or assembly, hence transforming a programming language to a different form by breaking it down into "words" with some lexer and reading the "grammar" of the words with some parser, and finally compiling it.

But is the term compiler limited to transforming specifically programming languages?

For example, there's a tool called doxygen that will read all of the documentation from source code files, break them down, and generate output based on the documentation. Is this considered to be a compiler?

A compiler translates code written in one programming language into code in another language -- normally, with the semantics of the output code being the same as the input code (or with a strong relationship).

Personally, if you asked me to use the word strictly, I wouldn't call Doxygen a compiler.  The output isn't executable code, and doesn't have anything like the same semantics as the input source code.

See also Wikipedia's definition/explanation.

That said, there are many situations where we use a word loosely, when from context it will be understood what we're referring to -- so I'm not sure how useful it will be to look for a super-precise definition of the word.  If the specific definition is important in your writing, then it might be best to define how you plan to use the term.


Recursive Bubble Sort Complexity I have this code for a recursive bubble sort:

def bubble_sort_recursive(list_):
    global counter
    for i in range(len(list_)):
        counter += 1
        try:
            if list_[i + 1] < list_[i]:
                list_[i], list_[i + 1] = list_[i + 1], list_[i]
                bubble_sort_recursive(list_)
        except IndexError:
            continue
    return list_

The counter is initialized with zero outside the function, so I can count the number of times the elements were iterated.

I was told that the complexity of bubble sort is O(N^2). But when I run with a reversed list (worst case) with size 3, the counter finishes with the value 12, shouldn't it be 9?

The same happens for other sizes:
4 -> 28
5 -> 55

What is happening?

The meaning of $O(n^2)$

  I was told that the complexity of bubble sort is $O(n^2)$. But when I run with a reversed list (worst case) with size 3, the counter finishes with the value 12, shouldn't it be 9?

Had $O(n^2)$ meant $n^2$, we should have written it as $n^2$ instead of that funny looking $O(n^2)$. Instead, $O(n^2)$ means no more than $n^2$ roughly. By "roughly", we mean we do not care about a constant multiplier, be it 0.01 or 2019 or a million. That is, $O(n^2)$ represents a function of $n$ that is $0.01n$ or less. Or a function that is $2019n$ or less. Or a function that is $1000000000n$ or less.

Because of that constant multiplier, even if that counter for a list of size 3 ends up with 9999, it does not contradict the bound $O(n^2)$, although it could be considered a warning sign that the right bound might be bigger such as $O(n^3)$ instead.

The counter and the time-complexity

What is the meaning of the counter in the algorithm? It counts how many times the algorithm has entered into the loop body.

For each call of the algorithm, if we exclude the subcall of the algorithm cause by an inversion, list_[i + 1] < list_[i], the counter will be increased len(list_) times, namely, $n$ times.

Assume the input list was reversely sorted, the worst case for time-complexity. There are $n(n-1)/2$ inversions, which lead to calling the algorithm $n(n-1)/2$ times. There is also the initial call of the algorithm. In total, the algorithm is called $1+n(n-1)/2$ times. So, in the end, the value of the counter is $n\cdot(1+n(n-1)/2)$. For example, if $n=3$, counter ends up with $3(1+3(3-1)/2)=12$, as mentioned in the question.

Note that $n\cdot(1+n(n-1)/2)=\Theta(n^3)$. Since the time-complexity of the algorithm is about a constant multiple of that counter, we conclude that the time-complexity of the algorithm is $O(n^3)$.

An improved version of the algorithm

Here are a few places where the algorithm can be improved.

Instead of for i in range(len(list_)), it could have been for i in range(len(list_)-1). The try ... except can be spared.
The return value of bubble_sort_recursive is never used.
When we have swapped two elements, list_[i + 1] and list_[i] as they  found to be the first unsorted pair of elements, the first $i$ elements remain sorted. So, we can avoid checking the adjacent pairs in those $i$ elements then.
Consider the $n-1$ comparisons made in one call of the algorithm but not in the possible recursive call inside that call. When an inversion is found by one of the comparisons, a recursive call, which will try to find an inversion from scratch, will be made. That means all later comparisons will not succeed and, hence, will not change the list in any way. So, we can break the loop after the recursive call.

Here is the improved version.

def bubble_sort_recursive_improved(list_, begin):
    global counter
    for i in range(begin, len(list_) - 1):
        counter += 1
        if list_[i + 1] < list_[i]:
            list_[i], list_[i + 1] = list_[i + 1], list_[i]
            bubble_sort_recursive_improved(list_, 0 if i == 0 else i - 1)
            break

# import sys
# sys.setrecursionlimit(max(1000, n * n // 2))
numbers = [5, 4, 3, 2, 1]
counter = 0
bubble_sort_recursive_improved(numbers, 0)
print(numbers, counter)

Exercise 1. Explain how the improved algorithm works correctly.

Exercise 2. Show that the improved algorithm runs in $O(n^2)$ time. In particular, counter is at most $n(n-1)$.


Confusion regarding regular language A regular language is a language that can be represented by a regular expression(or for which there exists a DFA), then why is language represented by  0$^{+}$   not regular?

I am asking this because for the following question the correct answer is option 2

Let L denote the languages generated by the grammar S→0S0∣00.
Which of the following is TRUE?

L=0$^{+}$
L is regular but not 0$^{+}$
L is context free but not regular
L is not context free

The statement (2) is ambiguous. It could mean either
$$
L \text{ is regular but } L \text{ is not equal to } 0^+ \tag{1}
$$
Or it could mean,
$$
L \text{ is regular but } 0^+ \text{ is not regular} \tag{2}
$$
(1) is true and (2) is false.
The authors of the question intended it to mean (1).
But you thought that the meaning was (2), so you were confused.


What is the precise definition of pseudo-polynomial time (feat. Counting Sort) From wikipedia

  In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required to represent it) and the numeric value of the input (the largest integer present in the input). In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length.

From this SO post

  An algorithm runs in pseudo-polynomial time if the runtime is some polynomial in the numeric value of the input, rather than in the number of bits required to represent it.

I have some questions about the wiki definition. To my knowledge, the definition provided by the SO post makes more sense. Shouldn't the wiki say pseudo-polynomial time is if the running time is
1) exponential (or something greater than polynomial) in the length of the input, and
2) polynomial in the numeric value of the input (largest number of input)
??

Assuming you have answered the question of definition above,

I am having trouble analyzing the running time of Counting Sort which is $O(N + K)$ with respect to $N, K$, the numeric values of the input.

Assuming we do not have the $k = \Theta(N)$ simplifying condition, the length of the input is $x = \Theta(N\log(k))$ bits.

The Wiki says "In general, the numeric value of the input is exponential in the input length". But $k = 2^{\Theta(\frac{x}{N})}$. With N potentially bringing down the magnitude of the exponent, I don't really see how $k$ is exponential in $x$.

In addition, the SO post I referenced claims counting sort runtime is exponential with respect to the length of the input, $x = \Theta(N\log(k))$ bits. How can $O(N + k)$ be transformed into an expression exponential in $n$ to demonstrate the claim? I got it down to $O(\frac{x}{\log(x)} + k)$ but got stuck there.

If I just think the length of the input is $\Theta(\log k)$ then I can see why the run-time is exponential but this doesn't seem to be consistent with how $x$ should be defined.

Let us denote the input's length by $n$, and lets remember that $n=\Theta\left(N\log K\right)$. You won't be able to write the exact running time of counting sort as an expression of the form $2^{\Omega(n)}$, as this would mean that for large enough inputs, the running time is always exponential. However, in this case, if $K$ is not too large compared to $N$, then the running time is actually linear, this means that there exists an infinite series of inputs with increasing size on which the running time is not exponential.

With this is mind, recall that what you seek is the worst case complexity of your algorithm, i.e. you want to find a certain time bound that holds for all inputs of large enough size. This means that to lower bound the complexity, it suffices to find one series of inputs with increasing size on which the running time is exponential. This allows you to focus on inputs where $K=2^N$, in this case the input size is $n=\Theta\left(\log^2 K\right)$, and the running time is $O(K)=O\left(2^{\sqrt{n}}\right)$, which is definitely exponential.

In general, a pseudopolynomial time algorithm is an algorithm which runs in polynomial time in the numeric value of the input (which means it is not necessarily polynomial in the input's length). Wiki's definition is no different, except it adds the restriction that the running time is polynomial in both the numeric value and the input size, i.e. if the input size is $n$, and its associated numeric value is $v$, we want a time bound of the form $p(n,v)$ for some polynomial $p$. This excludes for example a $2^N+K$ time algorithm for sorting $N$ numbers in the range $[1,K]$, although this is polynomial in $K$.


Computing all possible partial sum-function of a given set of numbers Let there be $N$ positive numbers given as $\lambda_1\geq\dots\geq\lambda_N$. Now I am interested in the following numbers given as $$\alpha_i=\exp(\frac{\lambda_i}{\lambda})$$ for some positive constant $\lambda$. Define the function $\mathcal{S}(..)$ which takes a subset of these numbers (let me call me them as a sequence) and calculate their products. For example$$\mathcal{S}(\alpha_1,\alpha_2)=\alpha_1\alpha_2$$Also note that $$S(\alpha_1,\alpha_2,\alpha_3)=S(\alpha_1,\alpha_2)S(\alpha_3)$$Also $$\mathcal{S}(\alpha_1,\alpha_3,\alpha_4)={\mathcal{S}(\alpha_1,\alpha_2,\alpha_3,\alpha_4) \over \mathcal{S}(\alpha_2)}$$ and so on. For given $K$ and $N$, we have $NC_K$ possible subsequences of $\alpha_i$'s. Is there a really efficient way of computing $\mathcal{S}(.)$ for all such sequences.

There are ${N \choose K}$ subsequences of length $K$, so outputting $\mathcal{S}(\cdot)$ for all of them will certainly require an output of length at least ${N \choose K}$.  Thus, the running time has to be at least ${N \choose K}$.  Beware that this is potentially exponential in $N$, depending on the value of $K$, so for some choices of $N,K$ there is no hope for an efficient algorithm to compute all those values.

You can list all those values in approximately ${N \choose K}$ time.  Take any algorithm for enumerating all $K$-size subsets of $\{1,2,\dots,N\}$; then it is easy to turn it into an algorithm to do what you want, by keeping track of the product associated with each subset.  Note that when you add an element to a subset, with a single multiplication you can update the product (compute the product of the new subset, based on the product of the old subset multiplied by the new element that was added).


Number of MUX required for Cache Mapping I have read that the number of multiplexers required is equal to the number of bits in the TAG field. Is it true? If yes then why?

I know that the size of each multiplexer has to be S to 1, where S is the number of sets in a k-way associative cache (For Direct Mapped, no. of sets = no. of lines). That's because we have to select one of the sets using the set offset (or index) bits.

I'm not being able to reason with the number of multiplexers required though.

A multiplexer can output only a single bit on output line.
So, to output one complete tag to the comparator ,

Number of multiplexers required = Number of bits in the tag. (say T)

If there are k lines in one set, then number of tags to output = K,

thus ,

number of multiplexers required = Number of lines in one set (K) x Number of bits in the tag(T).

TOTAL MUX REQUIRED = K*T


Hamming distance and parity For an Hamming code of $n$ bit there are $k$ bit reserved for the data and $p$ bit for the parity where $p$ is the minimum integer for which the following inequation is satisfied: $$2^p \geqslant p + k + 1$$
This because at least $p$ bit are required to code $n$ error on a single bit $+ 1$ for the "no error" word.

For an Hamming code with distance $d$ you can detect $d-1$ bit of errors and correct $\lfloor d-1/2 \rfloor$ bit of errors.

However you can have SEC (7,4) and SEC (12,8) with the same Hamming distance $d = 3$ but the the first has $p = 3$ bit for the parity while the second has $p = 4$ bit for the parity.

The first question is what does it mean for an Hamming code H having an Hamming distance = 3 ? Does it mean that all $k$ or $n$ bit of data are required to have $d=3$ with each other ?

What is the relationship between the parity and the distance in an Hamming code ?

A (binary) code $C$ is a collection of binary strings of some length $n$, known as codewords. The minimal distance of $C$ is the minimum Hamming distance between (different) codewords. Hamming codes have minimum distance 3, which means that (1) every two codewords differ in at least 3 places, (2) there exist two codewords which differ in exactly 3 places.

Hamming codes are examples of an important class of codes known as linear codes. You can think of linear codes in many ways:

A linear code of length $n$ is a linear subspace of $\{0,1\}^n$. The dimension of the code is known as the rate $k$.
A linear code is a code which is closed under XOR, that is, the XOR of any two codewords is again a codeword. It turns out that the number of codewords is always a power of 2, say $2^k$. The parameter $k$ is known as the rate.
A linear code is a way of encoding $k$-bit messages using $n$ bits. The original bits of the message are put in fixed places, and every other bit is an XOR of a certain fixed subset of the message bits. For example, the SEC(7,4) code encodes a 4-bit message $x,y,z,w$ using 7 bits:
$$
x \oplus y \oplus w, x \oplus z \oplus w, x, y \oplus z \oplus w, y, z, w
$$

The minimal distance of a linear code is also the minimal Hamming weight of a non-zero codeword. So the fact that Hamming codes have minimum distance 3 means that (1) every non-zero codeword has at least 3 ones, (2) there exists a codeword having exactly 3 ones.

We have mentioned three parameters: the length of the code $n$, the rate of the code $k$, and the minimal distance $d$. There is no exact relation between these three parameters, though there are various  bounds relating the three quantities. One of these bounds is the Hamming bound:
$$
\sum_{\ell=0}^{\lfloor \frac{d-1}{2}\rfloor} \binom{n}{\ell}\leq 2^{n-k}.
$$
For example, for the SEC(7,4) code this gives
$$
\binom{7}{0} + \binom{7}{1} \leq 2^{7-4}.
$$
You can check that equality holds, and indeed this is the case for all Hamming codes. Codes for which equality holds are called perfect codes. Apart from a few trivial and exceptional cases, Hamming codes are (essentially) the only perfect codes.


NFA accepting the empty string Suppose I have an NFA with accepting state q1(which is also an accept state) and non-accept state q2, with ε-transition from q1 to q2.

Also, suppose that empty string is inside the language. Then I want to know if the empty string is accepted by the above NFA following the standard definition:

Here, $\mathcal{P}(Q)$ denotes the power set of Q. Let $w = a_1 a_2 \ldots a_m$ be a word over the alphabet $\Sigma_\epsilon$. The automaton $M$ accepts the word $w$ if a sequence of states, $r_0,r_1, \ldots, r_n$ exists in $Q$ with the following conditions with $m >= n$ and $m>=0$:

$r_0 = q_0$

$r_i+1 \in \Delta(r_i, a_i+1)$, for $i = 0, \ldots, n−1$

$r_n \in F$

I know it would be much easier to figure out whether the given string is accepted by NFA by visualizing what's going on in the NFA, but I find the formal definition above rather confusing because it's only checking the existence of one particular branch of computation that satisfies the above three conditions. I know that an empty string is w =  ε or [blank]. By blank, I mean it has no symbols (where m = 0). But if I take w = ε, it would move from q1 to q2 via following ε-transition.But if I take w = [blank], then the sequence of state would be just q0, then it would be accepted. Is this the right way of thinking about it?

Is this the right way of thinking about it?

No.

An NFA (with or without $\varepsilon$-transitions) accepts if there is any sequence of transitions that leads to an accepting state, regardless of whether there are other sequences that lead to non-accepting states.  If the start state is accepting, then the empty string is accepted because the null sequence of transitions (no transitions at all) leads to an accepting state. It doesn't matter that there are other sequences that lead to non-accepting states.

$\varepsilon$-transitions are annoying to define formally. Informally (but completely accurately), they just allow the automaton to change state without reading an input character.


BNF syntax for a recursive function? I'm to write a syntax that will allow for a recursive function, i.e.
f(x) = if x == 0 then x else f(x+1)

Here's one attempt at creating the grammar:

But I don't think this is right since there's no such thing as parameterized syntax.

Are you aiming to simply allow recursive functions or specify only recursive functions. The following grammar allows recursive functions:
function      := id '(' parameter ')' '=' function_body ;
function_body := conditional
               | expression
               ;
expression    := function_call
               | <other expression types>
               ;
function_call := id '(' parameter ')' ;

Specifying only recursive functions would require a context-aware grammar (BNF is context-free). You can approach the problem outside of the grammar specification though and check for recursive functions later in your parser / compiler pipeline.
Checking for recursion outside of the grammar allows you to more easily identify cyclic recursion (not just f calling f but something like f -> a -> b -> c -> f).


Why is Big O not defined here for a hash table? In this cheat sheet, average time complexity for access to a hash table is listed as N/A.

I'm curious as to why.  Since a hash table is mostly mathematical, I would assume it would be O(1) like the other operations ... Search, Insertion, Delete.

http://bigocheatsheet.com/

The chart is underspecified. I assume they mean by "Access" to "retrieve the $i$-th element¹.

In hashtables, there is no notion of order. While you could pick the $i$-th element in the underlying array, that would have no meaning at all. Hence, this operation does not make sense on hashtables -- n/a.

Which is of course underspecified or unfair, depending on how you look at it: in a BST, "Access" gives you also the $i$-th smallest element, whereas in a plain array you get just some element.


Will a Greedy algorithm give a correct result for minimum partition? Will a greedy method of picking the item that causes the largest difference each time lead to the optimal result in the minimum partition problem?

Let's say I have a set $\{a_1,a_2,a_3,...a_n\}$, now I have to divide it into two subsets so that the difference between the sums of the two subsets is the minimum possible.

Greedy Method:

I have the given set of numbers and an empty set. On each iteration, I select the number from the first set and check which causes the minimum difference and put that into the second set and repeat the process again.

For example: let us say I have to partition $\{1,2,3,4\}$ into two subsets so that their respective sums are minimum.

So using the above method I would do the following steps:

Select the number that causes the min diff so far ie.

$\{2,3,4\}$ and $\{1\}$ diff = $9$

$\{1,3,4\}$ and $\{2\}$ diff = $6$

$\{1,2,4\}$ and $\{3\}$ diff = $4$

$\{1,2,3\}$ and $\{4\}$ diff = $2$

so the minimum is $\{1,2,3\}$ and $\{4\}$

I use the above configuration and repeat the same process, and I land up with the partition $\{2,3\}$ and $\{4,1\}$ which has a difference of $0$ and is the correct answer.

So, assuming the numbers given are all positive integers, will the greedy method work for all inputs or will it fail for some. Is dynamic programming the only way to get the optimal solution?

This does not always lead to the optimal solution. For example for input $\{1,11,16,19,20,30,36,40,41\}$ it gives $\{1,11,16,19,20,36\}$ and $\{30,40,41\}$ with a difference of 8, while a difference of 0 is possible: $\{1,40,36,30\}$ and $\{41,20,16,11,19\}$


Assignment to make formula unsatisfiable Lets imagine we have a satisfiable formula $F(A_0, A_1,...A_k,S_0,...,S_n)$ The problem to solve is "Is there an assignment for variables $(S_0,...,S_n)$ which will make F unsatisfiable?". One way of solving is to find all solutions for F in terms of variables $S_0,...,S_n$ and if the count is < $2^n$, the missing solution will be the answer, but the complexity of this algorithm is huge, if the number of such assignments is small.

My questions are:

Is there a way to solve the problem with less SAT solver calls?
Is it a well-known problem in theory (What I should google to read about it)?

Your problem is the canonical $\Sigma_2^P$-complete problem:
$$
\exists \vec{S} \forall \vec{A} \lnot F(\vec{A},\vec{S}).
$$
As such, it is thought to be more difficult than SAT (which is $\Sigma_1^P$). Solving it with a few SAT-oracle calls is akin to solving SAT itself efficiently (the P vs. NP question), though it could be that $\Sigma_2^P = \Sigma_1^P$ while $P \neq NP$, so in some sense there is more hope for your problem than for SAT itself.


Minimum-area enclosing equilateral triangle for a point set We have $n$ points $P$ in $2D$ space. We want to find an enclosing  equilateral triangle $\Delta$ with minimum area in $O(n\log n)$. Suppose  We know that at least on side of $\Delta$ covers at least two points of $P$.
My first attempt: I try to compute convex hull of points, then I select three points of the hull and construct a triangle with minimum area, touching these points. The running time becomes $O(n^3)$ because we need to check each combination of three points from $O(n)$ points - so it's inefficient.
Second try: I think this problem have is related with lover envelope, but I can't formulate it in dual manner. Any help to solve this problem in $O(n\log n)$ will be appreciated.

Let’s consider the following problem at first – given a convex polygon $H = (v_1,v_2,...,v_m)$ and a direction (unit vector) $\vec a$, find a farthest vertex $v \in H$ along this direction (it will be a vertex with maximum value of the dot product $\vec a \cdot \vec v$). Obviously, this problem can be solved by brute force in $O(m)$ time.
If the polygon is static and the query direction varies, then it makes sense to preprocess the polygon to answer this query faster. For each vertex $v \in H$ we can calculate a range of directions (a wedge), for which this vertex will be the farthest one - please see the picture below.

It’s easy to see, that wedges for two vertices, connected by an edge, have a common side – and this side is exactly the outward-pointing normal for this edge. These wedges together with corresponding vertices can be stored in a tree-like data structure. So, for any given direction we’ll be able to use this structure to find a wedge, containing this direction, and also the farthest vertex, corresponding to this wedge, in $O(\log m)$ time.
Returning to the main problem – we need at first to compute the convex hull $H$ for the set $P$, and then to preprocess the polygon $H$ as described above. After that we can scan edges of the polygon one by one, constructing the minimal enclosing equilateral triangle for each edge and recording its minimum area. For each edge the line, collinear with this edge, defines the direction of the first side of the triangle – and this side will contain two polygon vertices. As soon as the direction of the first side is known we can find directions (normal vectors) for other two sides by rotating it by $120^o$ and $240^o$. Then we use the tree, described above, to find farthest vertices for the second and third side of the triangle.
The convex hull computation plus the polygon preprocessing takes $O(n \log n)$ time. The loop over polygon edges takes $m \le n$ steps, and on each step we need to do two binary searches with depth $O(\log m)$, so the overall time will be $O(n \log n)$.


Questions about Randomized Median algorithm? In textbook by Mitzenmacher and Upfal here, they write in page 62, the following:

  By repeating Algorithm 3.1 until it succeeds in finding the median, we can obtain an iterative algorithm that never fails but has a random running time.

Note that that the algorithm has linear running time. Now, if we repeat this algorithm for k times, then the running time would be O(kn). Now, how they say that "By repeating algorithm until it succeeds in finding the median, we can obtain an iterative algorithm"?
I do not understand how they get an iterative algorithm. In order to get an iterative algorithm, then the algorithm must call itself and must have a logarithmic running time.

Another question: What does they mean by "it has a random running time"?

About iterated algorithm, please look here.
To see the algorithm, look at the book in page 59.

Let's start with your second question. A random running time is a running time which is a random variables. As a simple example, consider an algorithm which tosses a fair coin until it come up heads. The running time is a random variable whose distribution is, roughly speaking, geometric. This is not so different from the randomized median algorithm: every run of the median algorithm is like a coin toss, and you iterate running it until it comes up "heads" (succeeds).

Now, for the name iterative algorithm. Here is the algorithm you describe:

repeat
  run Algorithm 3.1
until the algorithm succeeds

This is the epitome of iteration – the algorithm consists of a single loop.

You write

  In order to get an iterative algorithm, then the algorithm must call itself and must have a logarithmic running time.

I'm not really sure why you think that an iterative algorithm should call itself. Indeed, algorithms calling themselves are usually known as recursive algorithms. (As an aside, an iteration of the form considered here is a special case of recursion known as tail recursion.)

Also, I'm not really sure why the algorithm should have a logarithmic running time. The standard algorithm for summing an array is iterative and runs in linear time.


(DROP) Data Reduction Algorithm - How it works? I am studing a PHD framework which the propose is to reduce the dataset with the most representative samples for training a classifier. Maybe I am loosing something, but I could not undestand a specific part.

Basic this is the algoritm 1 proposed:

Question 1: line 7 says it will union 'edge (s,t)'. What it means? It means that Z'2 (output) will be a set of edges with s and t from different cluster-id's?

And I am asking it because the second algorithm in thesis is the following:

I am not sure if I understood how it L list is generated because some edgs did not make sense by the figure below:

Question 2 Why 6 and 7 has the same element (triangles)? It not should be different, once the edges (from algorithm 1) are from different cluster-ids?

This is the link for thesis: http://repositorio.unicamp.br/handle/REPOSIP/275528?locale=en (page 21-22)

Algorithm 1 takes non-annotated data as input, so it is agnostic to the labels (shapes). In line 1, algorithm 1 computes clusters on the non-annotated data. The cluster assignments do not necessarily correspond exactly to the labels. The output of algorithm 1 will be a set of edges between data in different clusters, but the data need not have different labels. So the reason edges 6 and 7 can connect between triangles is because the triangles have been assigned to different clusters.


Similarities and differences in major process algebras To my knowledge, there are three major process algebras that have inspired a vast range of research into formal models of concurrency. These are:

CCS and $\pi$-calculus both by Robin Milner
CSP by Tony Hoare and
ACP by Jan Bergstra and Jan Willem Klop

All three seem to have to this day a quite active following and vast amounts of research has been done on them.

  What are the key similarities and differences of these approaches?
  Why has research in process algebra diverged instead of converged, in the sense that there is no one universal model to unify the field?

I only know CSP and CCS/pi-calculus (not ACP).

CSP was motivated by imperative programming processes communicating via messages.  Hoare then tried to abstract away a simple calculus out of it.  CCS, on the other hand, was an effort to create a foundational calculus like lambda calculus.  Given their original starting points, and given their final form, I would say that they have converged rather than diverged.

What I find common between CSP and CCS is that both of them are based on the notion of "process" (and, by that, I mean an abstract notion of events arranged in time).  The main difference between them is that CSP has two forms of choice (internal/external or nondeterministic/deterministic).  In CCS the two ideas are fused into one.  I think that is an irreconcilable difference.

The distinction between internal and external choice allows CSP to have a semantics in terms of linear traces.  The CCS semantics, on the other hand, has to be based on trees.

I think Hoare's current plan for "Unifying theories" is to put both of them into a single framework.  We have to wait and see what he comes up with!


Is the language L = {(a,b)* | #a * #b is an odd number} regular? Is the following language regular? $$\{ w \in \{a, b\}^* |\ \text{the product of the number of $a$'s and the number of $b$'s is an odd number}\} $$

If i'm not mistaken the condition is the same as having an odd number of $a$'s and an odd number of $b$'s. I have tried using the Pumping Lemma without success. So I'm suspecting it's regular. But I can't think of a regular expression or an automaton that accepts it.

It is.

Since only the product of two odd numbers is an odd number, you can construct a DFA that only accepts when #$a$ and #$b$ are (both) odd.

The followings states would be:

$Q_1$ : #$a$ even, #$b$ even
$Q_2$ : #$a$ even, #$b$ odd
$Q_3$ : #$a$ odd, #$b$ even
$Q_4$ : #$a$ odd, #$b$ odd (an accepting state)

The transitions are fairly simply, and I'll leave them to you.


Error lower-bound for an algorithm for vertex cover I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set:

Fix some order $e_1, e_2, . . . , e_m$ over all edges in the edge set E of G, and set $B_0 = \emptyset$.
Add to $B_0$ all isolated vertices, i.e. the ones without any incident edges.
For every edge $e$ in $e_1, e_2, . . . , e_m$

if both endpoints of $e$ not contained in $B_0$, then
flip a fair coin deciding which of the endpoints to choose, and add this endpoint to $B_0$.

How can I prove that, for every constant $c \geq 1$, the algorithm might produce a $B_0$ with $|B_0
| \ge c|OPT|$?

Fix a star graph of $c + 1$ vertices. A star graph is a vertex connected to all other vertices in the graph (a universal vertex called the center), and all other vertices are pairwise not adjacent. Here is a visual example. $c$ is the center of the star.

Now an optimal solution is to pack the center of the star. The size of this solution is equal to 1. For each edge, suppose our algorithm packs the other end of the edge (the non-universal vertex), then we need to pack all vertices of the graph except for the center and hence, we need to pack $c$ different vertices. In total we get $|B_0| = C |OPT|$ for any arbitrary but fixed value of $c$.

Note
A simple modification of the algorithm yields a derandomized approximation algorithm with answer size at most twice as large as the optimum. It goes as follows: if both endpoints of the edge are not in $B_0$, then add both endpoints to $B_0$ and iterate.

The reason why this works is simple. The edges, who get their endpoints added for a maximal matching and hence, we add twice the number of vertices in a maximal matching to the cover. Note that the size of a matching in a graph is a lower-bound on the size of a minimum vertex cover and hence, we add at most twice many vertices as the size of the minimum vertex cover.


Image selection for Object detection I'm relatively new and am still learning the basics. I've used NVIDIA DIGITS in the past, and am now looking at Tensorflow. While I've been able to fumble my way around creating some models for a few projects I'm working on, I really want to start diving deeper into what I'm doing, how I'm doing it, and ultimately a better understanding of why.

One area that I would like to start with is the Images that I'm using for training and testing. Can anyone point me to a blog, an article, a paper, or give me some insight in what I need to consider when selecting images to train a new model on. Up until recently, I've been using datasets that have already been selected and that are available for download. Lets say I'm going to start working on a project that involves object detection of ships from a variety of distances and angles.

So my thoughts would be

1) I need a large quantity of images. 2) The images need to contain ships of the different types I would like to detect. (lets just say one class, ships, don't care what type of ships) 3) I also need to have images that have a great variety of distance perspective for the different types of ships.

Ultimately, my thoughts are that the images need to reflect the distance, perspective, and types of ships I would ideally want to identify from the video. Seems simple enough.

However, there are a number of questions

Does the images need to be the same/similar resolution as the camera I'll be using, for best results? Does the images all need to be the same resolution? Can I use a single image and just digitally zoom out on the image to give the illusion of different distances?

I'm sure there are a number of other questions that I'm not asking, or should be asking. Are there any guide lines available for creating a solid collection of images to use when creating the collection of images for training and validation?

Do the images need to be the same/similar resolution as the camera I'll be using, for best results?
Technically yes, for best results, you should use as close as possible images that you train them on to predict, for example, HD camera and webcam images are quite different, but in real life, it is not usually possible, as it is costly. You don't need the same resolution images, but if you resize from 30 x 30 x 3 to 256 x 256 x 3  or 1024 x 768 x 3 it to 256 x 256 x 3 makes a difference in how the image looks after transformation, but  You can use different resolution images, but you need to resize them, using letterbox (padded image while preserving aspect ratio), or crop, or even in some cases just resizing without preserving aspect ratio gives good results.
It depends on a case by case.
Does the images all need to be the same resolution? Can I use a single image and just digitally zoom out on the image to give the illusion of different distances?
No, you don't have to have them in the same resolution. You can always resize images.
If the object is small in the image it could be possible, but remember it's better to have more unique data for generalization of the network. But for augmentation usually one of the augmentation techniques is zooming in (center crop and resize), and you could use zoom out as well.  There are other various techniques rotation, HSV transformations, shear, and many more you can use for augmentation.


Algorithm for computing the sum of symmetric sums (better than $\mathcal{O}(2^N)$ ) Let denote $\mathbf{x} = \{x_1,x_2,...,x_N  \}$ with $x_i \in \Bbb R$ for $i=1,...,N$ and $f(\mathbf{x},n)$ be the $n$-th symmetric sum of the set $\mathbf{x}$
$$
f(\mathbf{x},n) = \sum_{\sigma_1,...,\sigma_n} \left(\prod_{i=1}^n x_{\sigma_i}\right)
$$
with $\sigma_1,...\sigma_n \in \{1,2,...,N \}$ and $\sigma_i \ne \sigma_j$ for $i\ne j$
(the definition of the $n$-th symmetric sum can also be found here)
Let define $g(\mathbf{x},a)$  be the sum of symmetric sum
$$
g(\mathbf{x},a)= \sum_{n=0}^N a^{\mathbb{mod}(n,2)} f(\mathbf{x},n)
$$
with $a \in \Bbb R$ and
$\mathbb{mod}(n,2) = \begin{cases}
1 \quad \text{ if } n \text{ odd} \\
0 \quad \text{ if } n \text{ even}
\end{cases}$
Example 1: N = 2:
$$
g(\mathbf{x},a)= 1 - a(x_1 +x_2) + (x_1 x_2)
$$
Example 2: N = 3:
$$
g(\mathbf{x},a)= 1 - a(x_1 +x_2+x_3) + (x_1 x_2+x_2 x_3+x_3 x_1) - a x_1 x_2 x_3
$$
The complexity of $g(\mathbf{x},a)$ is $\mathcal{O}(2^n)$ with a naive algorithm. Indeed, the sum $g(\mathbf{x},a)$ has exactly $2^N$ terms and we sum up the terms sequentially
$$
g(\mathbf{x},a)= \sum_{n=1}^N\left( a^{\mathbb{mod}(N,2)} \sum_{\sigma_1,...,\sigma_n} \left(\prod_{i=1}^n x_{\sigma_i}\right)\right)
$$
My question: does there exist a better algorithm for computing $g(\mathbf{x},a)$ which is less complex than $\mathcal{O}(2^N)$?
My attempt: There exists special cases where $a=\pm 1$ that can factorize the sum $g(\mathbf{x},a)$ as follows
$$
g(\mathbf{x},a)= \prod_{n=1}^N(x_i+a)
$$
and then the sum can be computed in $\mathcal{O}(N)$. I try to find a mathematical method like this for $a \ne \pm 1$ without success. In fact, all difficulties lie on the modulo function $\mathbb{mod}(n,2)$.

But $g(x,a)$ is linear in $a$ so if you can compute it efficiently for two different values of $a$ then you can compute it efficiently for all $a$?


Inventory Routing - Subtour Elimination I'm trying to implement a Inventory Routing Problem with Branch-and-Cut. But I'm facing with an issue regarding subtour elimination. (http://www.danflash.com/files/irp.pdf)

The paper describes the constraint like this:
$$\sum_{i \in S} \sum_{j \in S, j<i} y^t_{ij} \le \sum_{i \in S} z_{it} -z_{kt} \quad S \subseteq M \quad t \in T \quad \text{for some} \ k \in S$$
And some page further I've found this: $k=arg max_j\{z_{jt}\}$ but no idea how to interpret this.

Where $y^t_{ij}$ is $1$ when the edge is used from $i$ to $j$ at time $t$. And $z_{it}$ is $1$ when vertex $i$ is visited at time $t$.

What is the exact definition of $S$? The set of all subtours or one specific subtour? Let say $M = \{1, 2, ...,7\}$ and $M' = \{0, 1, ..., 7\}$ ($M'$ with supplier/depot).

And the solution I get contains the following subtours: $0,1,3,0$ and $2,4,5,2$ and $6,7,6$

Know how would a pseudo code look like to implement this? And what is $k$?

My current solution look like this (implemented in C# with Gurobi solver). But I'm not sure if this should be implemented as a lazy constraint in the callback or adding the constraint after model.Optimize() if a subtour exists and call model.Optimize() again.

I did an implementation but I guess it's not worth to post it before I really understand the equation.

$S$ contains every subtour except the tour with the depot. And for each subtour a constraint has to be added.

The meaning of $k=argmax_j\{z_{jt}\}$ has been answered in https://math.stackexchange.com/questions/1290142/explanation-of-textrmargmax-jz-jt-and-how-to-implement-it/1290178#1290178

I solved this with a callback as soon as a subtour is found.


Binomial coefficient to approach multi-way choices DP problem? I'm trying to understand this dynamic programming related problem, adapted from Kleinberg's Algorithm Design book. Not homework: i've already a solution, just considering if i'm ok with the theory.

  Suppose we want to replicate a file over a collection of $n$ servers $S_1, S_2
, \ldots , S_n$. Each server $S_i$ has a placement cost $c_i$ to place a copy of the file at $S_i$. If a user requests the file from $S_i$ and no copy is present, then servers $S_{i+1}, S_{i+2}, S_{i+3}, \ldots$ are searched in order until a copy is found, say at $S_j$ (where $j > i$). This results in an access cost $a_i$, where
  $$
a_i=
\begin{cases}
j-i \qquad \hbox{if $S_i$ does not contain a copy the file} \\
0 \qquad \hbox{ if $S_i$ contains a copy of the file}
\end{cases}
$$
  We require that $S_n$ contains the file, so that all searches will terminate.
  Given $I \subset \left\{1,\ldots, n − 1\right\}$, a subset of servers to place the file on, we define the total cost

  $$
c(I) = c_n + \sum_{i \in I} c_i + \sum_{i=1}^{n} a_i
$$

  To be the sum of the placement costs for each server that contains the file (recall that $S_n$ must contain the file), plus the sum of the access costs associated with all $n$ servers. Design a polynomial-time algorithm to compute a subset I of servers to contain the file that minimizes total cost.

My approach is to consider every possible choice, like for other problems e.g. segmented least squares, ending up with a $O(n^4)$ running time algorithm.

Anyway it looks like there is a better solution, given by the following recurrence:

$$
OPT(j) = c_j + \displaystyle\min_{0 \leq i < j}(OPT(i)+\binom{j-i}{2})
$$

With the initialitazions $OPT(0)= 0$ and $\binom{1}{2}=0$. The answer is given as usual by $OPT(n)$. This is to me very counterintuitive: why the binomial coefficient, and why the number $2$?.

Is it a standard way to approach similar problems?

The binomial coefficient here appears through the formula
$$
\sum_{i=1}^{n-1} i = \binom{n}{2}.
$$
In the formula, $OPT(j)$ is the minimal cost of a solution for the first $j$ servers. Another way of looking it that it's the minimal cost up to $j$ of a solution which puts the file in $S_j$.

Where does the recurrence come form? Take an optimal solution for the first $i$ servers. We know that the file appears in $S_j$. Let $S_i$ be the next largest server it appears on (or $i=0$ if it only appears in $S_j$). Without loss of generality, we can assume that the solution restricted to $S_1,\ldots,S_i$ is optimal, and so of cost $OPT(i)$. Putting the file in $S_j$ costs $c_j$. Accessing the file at positions $i+1,\ldots,j-1$ costs $(j-(i+1)) + \cdots + (j-(j-1)) = \binom{j-i}{2}$. This gives the recurrence formula. (We also have to verify the case $i=0$ separately, which I leave to you.)


Why is there no "traditional"-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm? Why is there no algebraic definition of algorithm besides recursive functions?
If I'm wrong, what is the matheist definition of algorithm that you've ever seen in a paper and can you provide a link?
For example, modern machines do overflowed arithmetic by the rules of modulo $2^{32}, 2^{64}$, etc arithmetic.
So why is there rarely a discussion of a theoretical machine that works on finite groups or just integer quotient groups brought to some power which is the memory length (number of "words").
I think a lot can be done with math to solve algorithmic questions, but when one first approaches the subject, there is very little workable mathematics.
Recursive functions are nice, but mathematically they can be very hard to deal with.  Since every recursive algorithm has an iterative counter-part, I wish there were a paper that had operators like $\sum_{i=1}^{g(n)} f(i)$ which mimic a for-loop with bound dependent upon $n$ and that essentially evaluates $f(n)$ every loop.
Why can't we have this type of more traditional mathematics describe algorithms, or can we?  Do you have a definition you're working on?
If so, please share it in an answer to this question.

If you're looking for algebraic structure, then you should look at the field of denotational semantics. This is exactly what you describe: using algebra, and often Category Theory, to model computation mathematically.
Some examples:

Domain theory provides a mathematical model of the untyped lambda calculus, which is powerful enough to capture all computable functions. The trick is that, to model computation, we need to represent functions, but for any set $S$, the function space $S \to S$ is always larger than $S$. So there's no simple set that captures all computations involving computations. Instead, Dana Scott introduced domains, which impose additional structure on sets to avoid countability problems.

SKI Combinators provide a "point-free" description of computation. Every computation can be expressed by composing and applying three base combinators $S$, $K$, and $I$. The equations for the combinators are:

$ S\ x\ y\ z = (x\ z)(y\ z)$
$ (K\ x) y = x$
$ I x = x$

So these equations, in some sense, give an algebraic account of all of computation.

Cartesian closed categories provide models for typed programming languages. They don't capture all of computation, but they do provide an abstract model of it.

Topos theory provides a generalization of logic using category theory. And logic corresponds to computation via the Curry-Howard correspondence

As for recursion, it turns out that you can eliminate it by instead using fixed-point combinators like the Y combinator. So recursion can always be eliminated from (untyped) languages, even without using iteration.


Automata with minimal number of states using reverse So, by the Bzozowski theorem, if A is DFA  det(rev(det(rev(A))) would have minimal number of states. And for the most of them work. But for this example, I can't figure out why it doesn't. I have an DFA which is NOT minimal (the min. automata have 2 states ) but det(rev(A)) is the same automata (obviously  det(rev(det(rev(A))) is also the same). Can you tell me what am I doing wrong ? Tnx.

Your initial automaton has two final states. Its reverse should have two initial states. You wanted to avoid that, and added a new initial state.

The proper construction just uses the two initial states. The determinization algorithm can handle that.


Is the halting problem decidable by an "infinite Turing machine"? It has been shown of course that the halting problem is undecidable. That is, we cannot formulate a Turing machine that will decide for any arbitrary turing machine whether it will halt or not.

However, I'm wondering, if we want to decide for the set of Turing machines $T$, whether a turing machine $t$ halts, and we somehow have access to "infinite Turing machines" $I$, which have the property $P$: "They can calculate an infinite amount of steps in finite time", would it then be possible to grab a $i$ from $I$ that decides the halting problem for all $t\in T$?

The proof of the undecidability of the halting problem no longer applies here, because it would require one of the $t\in T$ to contain $i$, but then we might possibly have that $t\in I$ (since $t$ now simulates $i$, which is in $I$).

So my question is, can we prove that in this case, the halting problem is decidable? If not, are there other constructions of $I$ than the one I came up with that would make it possible?

(is there a name for what I've called "infinite turing machines"?)

It is true that infinite Turing Machines as you have defined them can solve the halting problem for regular Turing Machines. That is, there exists an infinite TM, $I(t,x)$, that returns $1$ iff $t(x)$ halts. To see this, just have your first step be “run t(x) for infinitely many steps” and the rest is easy after that. Yes, there are some issues formalizing this idea, but it can be done. This is called a “Hyper Turing machine”

There’s an interesting question lurking here though... is there an infinite TM that solves the halting problem for infinite Turing Machines? The answer to that is no, and if you know the diagonalization proof of the incomputability of the halting problem that applies here too.


does order matter when two different derivations are to be made for ambiguous grammar E ->  E + E | E * E | (E) | a

Derivation for ( (a+a) * a)

Question : Show that the grammar is ambiguous by sparse tree method

Now, I have derived two derivation using left most derivation

but it results in like this
1st : ((a+a) * a)
2nd : (a * (a+a))

is this correct or the order should also be same?

You are deriving different strings. The definition of ambiguity asks for the very same string.

In this case, that they "mean the same thing" in algebra, due to the commutative law for multiplication, is completely off topic.


Finding longest subset arithmetic progression with given difference Given a list of distinct positive integers, I am trying to find the largest subset that forms an arithmetic sequence with a given difference D.

For example, given D = 5, with the set of numbers 1, 5, 10, 6, 7, 8, 15, 11 the longest sequence would be 5, 10, 15

I have tried using sets to solve this but I can't find a solution faster than $O(n^2)$. For example, I have tried adding all items in the array to a TreeSet. This automatically orders the elements, after which I brute force check all the possible sequences. Am I on the right lines or is there a better approach?

Using a hashtable, you can solve this in $O(n)$ expected time, as follows:

Fill a hashtable $H$ with the given numbers.
Go over all numbers in the list. For each number $x$, if $x-D \notin H$:

Go over the numbers $x + D, x + 2D, x + 3D, \ldots$ until you find a number not in $H$.

The running time of the first step is $O(n)$. As for the second step, the potentially expensive step is the sub-step. However, in this sub-step we go over each element in the list at most once (we check $y$ only for $x = y-aD$, where $a$ is the maximal integer such that $y-aD \in H$), and so the second step takes $O(n)$ time.

Without using a hashtable but assuming that the list is sorted, we can solve this in $O(n)$ time as follows:

Go over all numbers in the list. For each number $x$, add an edge to $x+D$ if $x+D$ is in the list.
Go over all numbers again. For each number $x$, if there is no edge pointing at $x$, follows the path starting at $x$ and calculate its length.

Using two pointers, we can implement the first step in $O(n)$. (The first pointer points at $x$, the other one is looking for $x+D$.) The second step takes $O(n)$ time for the same reason as in the hashtable algorithm.

Since it takes $O(n\log n)$ time to sort the list, this solution runs in time $O(n\log n)$. Using the fast $O(n\log\log n)$ integer sorting algorithm, we obtain a solution running in time $O(n\log\log n)$.


Undecidability of the PCP problem with bounded width Given two ordered sets of words $a_1, a_2, ..., a_k$, $b_1, b_2, ..., b_k$ taking values in some discrete alphabet $A$, a solution to the PCP problem is a sequence $i_1, ..., i_n$ taking values in $1, 2,..., k$ such that $a_{i_1}|a_{i_2}|...|a_{i_n}=b_{i_1}|b_{i_2}|...|b_{i_n}$ where $|$ means concatenation. $k$ can be called the length of the problem, $n$ the length of the solution and if we let $w$ be the length of the largest word in $a_1, a_2, ..., a_k, b_1, b_2, ..., b_k$, $w$ is called the width of the problem.

I know that the PCP problem becomes decidable in several scenarios, for instance: for bounded $n$, or if $A$ is unary, etc. On the other hand for $k\geq7$ PCP is still undecidable. My question is, is there any result known for bounded values of $w$?

If $w$ is bounded, and the alphabet size is bounded, then the number of possible words is bounded. Thus, there is only a finite number of possible instances, so the problem becomes a finite languages, and hence decidable.

If you don't bound the alphabet, then you can encode any width of $w$ by adding more letters, so the problem is the same as standard PCP, and hence undecidable.


How to find sets of polynomially bounded numbers whose subset sums are different? Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ such that we always have $\pi(S) \ne \pi(S')$. For example, we can define $a_i = 2^i$. This function satisfies the property because for each $A \subseteq N$, $\pi(A)$ uniquely represents an integer written in base 2. However, in this function $a_i$ is bounded above by $\mathcal{O}(2^n)$. I am looking for a function such that $|a_i|$ and $\frac{1}{|a_i|}$ are bounded above by a polynomial. As an example that does not satisfy this last condition we can consider $a_i = 2^{i-n}$. It would be great to know different functions that satisfy this property. I will try to proof the uniqueness myself (if it is not so difficult!), so please let me know if you are aware of such functions.

There are many functions that satisfy your condition. Here are a few.

$a_i=1+c^{-i}$, for some constant $c\ge 2$.
$a_i= 1+b_i/p_i$, where $p_i$ is the $i^{th}$ prime number and $b_i$ is any integer between 1 and $p_i-1$.
$a_i =1+\alpha^i/\lceil\alpha^i\rceil$, for any positive transdental number $\alpha$. For example, you can take $\alpha = \pi$ or $\alpha=e$ or $\alpha=0.110001000000000000000001\cdots$, an Liouville number. (Yuval's method)
$a_i=c_1b_i+c_0$, where $b_i>0$ is such a function and $c_1, c_0$ are positive constant.
One can choose random numbers between a positive constant $c_0$ and 1, which should satisfy the requirement with probability one. The issue then is how to select/implement a random number generator and detect the outliers, which may or may not be trivial. (Yuval's method)

For the first three methods, the constant 1 can be replaced by some kind of polynomial of $n$. For example, a nonzero polynomial of $n$ with nonnegative integer coefficients.

These functions should get you going. If you find more ways, you can update this answer.


How does Instruction Set Architecture (ISA) affect performance? If 2 CPUs have the same Instruction Set Architecture, which of the following properties will be the same?

Clock Rate
CPI
Execution time
No. of instructions
MIPS

Same ISA means they understand the same instructions in binary. They can certainly be very different in speed. Look at e.g. the x86 family (disregard the instructions added over time). The very latest Pentium is certainly much faster than the first 386, and even within each "number" there are variations.
Even crasser, remember ye goode olden days of i486 and overclocking? Even the same chip can (sometimes) run at different clock rates. BTW, that is something current laptops do: To conserve battery power, the CPU runs at a lower clock rate when possible.


Why is DPLL better than brute force? I understand that by being clever about the way we navigate the search space of the SAT problem we're going to get better performance than by randomly choosing and testing solutions, though of course both methods have $O(2^n)$ time complexity. What are the specific reasons that DPLL gives better performance than brute-force (sequentially testing solutions from FALSE-FALSE-FALSE.... to TRUE-TRUE-TRUE....)?

Local (stochastic) search is all about clever navigation of the search space.  DPLL's advantage is pruning the search space of large swaths of assignments that provably cannot satisfy the formula.  DPLL does this by incrementally building partial assignments (some variables assigned values, some left unassigned), applying the unit propagation and pure literal rules and then checking if the resulting formula is trivially unsatisfiable.  If the simplified formula implied by the partial assignment contains an empty clause, DPLL need not try assigning values to the remaining unassigned variables since the empty clause represents a clause that can never be satisfied under the partial assignment.  The time saved is exponential to the number of unassigned variables, and those skipped assignments are where DPLL improves on brute force sequential search.


Linear ordering of all subsets of size k I was wondering if there is an obvious way to 'name' the ${n \choose k}$ subsets of size $k$ of the integers from $1$ to $n$. So I am looking for a bijection from the subsets of $\{1,\ldots, n\}$ into $\{1, \ldots, {n \choose k}\}$ that can be computed in $O(1)$ at best.

The most trivial way for this would be to use a tree where each leaf node corresponds to such a subset but then I have to save the entire tree and each lookup will cost more than $O(1)$. We could also totally order those subsets such that $\{1, 2, 3\}$ would be the smallest subset for $k=3$ and $\{n, n-1, n-2\}$ the largest one and then use the number of smaller/equal subsets in this ordering as our index. I tried to come up with a closed form solution and it ended in some gnarly sums of binomial coefficients.

So maybe there is a well known solution to this problem and somebody could give me a reference?

The bijection you are looking for is known as a combinatorial number system. A great further resource is Knuth's TAOCP.


Aggregate text data of some particular column I have a dataset as follows

Biodata
last_name  first_name  age   Description     Hobby
Smith       John       20    In high school  Music
Johnson     Robert     45  Software Developer Gardening
Williams    David      15     Junior school  Baseball
Davis       Michael    65     Traveler       Skydiving
Miller      Molly      25     Scientist      Cycling

Now I got a question from a assignment that Aggregate text data under “Description” and “Hobby”

I cannot understand what is the meaning of Aggregate text data?

If any one understand the question please share their view point. I want to know it theoretically how could any one aggregate text data depend upon description and Hobby column.

This is a coding assignment of python. But currently I don't bother about coding. I want to know the theoretical meaning of this question and want to solve it manually.

Thank you in advance

My assumption is that they want you to normalize the text data in those columns.  In other words, you may create a collection of the text, and the two columns would refer back to that collection.  Does that make sense?


Data interchange in two registers This picture is from Computer System Architecture 3rd Edition by Morris Mano. Is it possible to interchange the data of any two registers in a single clock pulse? I know that the data of DR (data register) and AC (accumulator register) can be interchanged in a single clock pulse. But other than this I don't understand how data replacement between two registers can be accomplished.
Thank you.

Just count the busses.  Most of the registers in this design only have an input from the single common bus.  The only exception is the ACcumulator, which also has an input from the DR.


Shortening the number of reductions to prove NP-Completeness This question is based on the slides from this pdf:

Slide 54, they define the Subset Sum Problem.
Slide 65, they define the Partition problem.
Slide 74, they talk about the Job Scheduling problem.

My question is, is it possible to cut the middle man of the partition problem and reduce Subset Sum to Job Scheduling directly?

To prove scheduling is NP, we can use what is already stated since it's not related to partition.

I'm not sure how to combine the reduction from both onto one though.

Yes, that's possible.

The reduction from Subset Sum to Partition is a mapping $f$ from Subset-Sum-instances to Partition-instances.  The reduction from Partition to Job Scheduling is a mapping $g$ from Partition-instances to Job-Scheduling-instances.  So, the function $g \circ f$ is a mapping from Subset-Sum-instances to Partition instances.

This gives you a direct reduction in one step; the reduction is given by the function $g \circ f$.  If you work through the details of the construction of $f$ and $g$, you should be able to figure out what $g \circ f$ is doing.  If you wanted, you could write down the definition of the function $g \circ f$ without telling anyone that it came from composing $f$ and $g$.  Whether that would be useful in any way is a different question...


What is a good design for expanding opcodes? Are there any tutorials on YouTube or good text tutorials on designing expanding opcodes? I always make mistakes on switching from one line to another and "counting" in binary. I pretty much know how to design them, but I don't really understand it and I make so many mistakes. I also don't have any examples to go by and check my answer.
Here's one example of what kind of designing and exercises I need:
Design 1 three-address instruction, 10 two-address instr, 7 one-address instr and 4 zero-address instr. The addresses are 8 bits each and 2 bits for an instruction (style: 00 xx yy zz)

So I went about doing designing it like this:

00 xx yy zz

00 00 yy zz
00 01 yy zz
00 10 yy zz
00 11 yy zz
10 00 yy zz
10 01 yy zz
10 10 yy zz
10 11 yy zz
11 00 yy zz
11 01 yy zz

11 10 00 zz
11 10 01 zz
11 10 10 zz
11 10 11 zz
11 11 00 zz
11 11 01 zz
11 11 10 zz

11 11 11 00
11 11 11 01
11 11 11 10
11 11 11 11

and the last one is all 1s so I guess it's correct. Maybe if there are no tutorials on YouTube, someone can simplify it or explain it here in text?

It looks like this is simply the problem of mapping a set of possible values (i.e., possible instructions) to some bit encoding.

You haven't specified whether all instruction encodings need to have the same length.

If they can have different lengths, usually you'll want them to form a prefix-free encoding (no encoded value is a prefix of any other).
If all instruction encodings must have the same length,any mapping that gives different instructions different encodings is acceptable.

Your solution doesn't look OK to me.  00 00 yy zz is a prefix of 00 xx yy zz if xx, yy, and zz are the addresses 00000000.

Editorial comment: the exercise is a bit boring and trivial, and doesn't involve much in the way of deep concepts.  It's just a matter of "bit-packing".


Avoiding underflow when identifying neighbours of a cell in a grid by using modulo I'm going through a tutorial that is using the Game of Life as example code. It has a function in it that finds the neighbor of a given cell. It is explained quickly that "When applying a delta of -1, we add self.height - 1 and let the modulo do its thing, rather than attempting to subtract 1" which would require a bunch of conditional logic to check for edge cases (when the cell we are checking is on the edge and simply adding or subtracting from its position would put it out of bounds)... This is the algorithm:

for a given 0-indexed row and col in a 2d space with area width * height:

for delta_row in [height - 1, 0, 1]
    for delta_col in [width -1, 0, 1]
        if delta_row == 0 && delta_col == 0
            continue // this is the cell we are checking

        neighbour_row = (row + delta_row) % height
        neighbour_col = (col + delta_col) % width

Anyways, I'm just wondering, how does someone figure this out from the naive case, where you just add and subtract and check for bounds? I'm not great with math but I'm assuming there might be a way to explain this algebraically? I worked through this with actual numbers for a while to verify it and just want to get a better understanding of how this works so maybe I can use this concept again later.

Using modular arithmetic here is equivalent to playing the game of life on a torus. Suppose you start with a $100\times 100$ grid with rows and columns numbered $0, \dots, 99$. The modular arithmetic says that $0-1\equiv 99$, which means that row $99$ is above row $0$ as well as below row $98$ and, similarly, column $99$ is to the left of column $0$ as well as to the right of column $98$.

This isn't equivalent to saying that there is nothing above row $0$ and nothing below row $99$.


Pointwise mutual information vs. Mutual information? I am learning about information theory and mutual information. However, I am quite confused with MI(Mutual information) vs. PMI(Pointwise mutual information) especially signs of MI and PMI values. Here are my questions.

Is MI values a non-negative value or it can be either positive or negative? If it is always a non-negative value, why is it ?
As I search online, the PMI can be positive or negative values and the MI is the expected value of all possible PMI. However, expected value can be positive or negative. If MI is really the expected value of PMI, why is it always positive ?

Did I misunderstand anything of MI and PMI here ? Thank you very much,

PMI can clearly be negative, since if $p(x,y)<p(x)p(y)$, then taking $\log \frac{p(x,y)}{p(x)p(y)}$ gives a negative number.

But MI is always non-negative, as it can be written as $d_{KL}(p(x,y)||p(x),p(y))$, where $d_{KL}$ is the Kullback–Leibler divergence which is non-negative (the proof of the latter is not completely trivial).

Intuitively, this happens because if there is a point such that $p(x,y)<p(x)p(y)$, then the probability must "compensate" for this later, with a pair $p(x',y')>p(x')p(y')$.


Prove longest path shares two points If there are two longest paths in a connected graph with path lengths of 79 (going through 80 vertices each). How can I prove that they share more than 1 vertex.

If they only cross at a single vertex $v$, consider the distance from that $v$ to the four path ends. Since the lengths are odd, $v$ can not be in the exact middle of the paths. But then, are the paths really the longest ones?


help understanding formal grammar for subtraction example I am going through the following document trying to understand a simple grammar for a basic subtraction example (page 4).

The example states that

  Simple arithmetic expressions of arbitrary length built from the subtraction operator '-' and the numerals 0 and 1 can be described by the following grammar:

E = T "-" E | T
T = "0" | "1"

I understand T is the terminal symbols, but I am having a hard time understanding E.  What confuses me even more is when it is stated:

  Choosing the other alternative for E we might get the derivation...

E ==> "0" "-" E

How and why is an alternative to E include E?  Likewise, I am having a hard time understanding how ET derives "0" or how EET derives 1.

Could someone better explain this to me?  I would greatly appreciate it to move forward in the document.  Maybe with a few examples would be extremely helpful.

T = "0" | "1" means that if you want a T string, 0 or 1 will
do.

E = T "-" E | T means that if you want an E string, a T string
followed by - followed by an E string will do, or a lone T
string will do.

Thus, for example, 1 is a T string, and is thus also an E
string. Hence, 1-1 is an E string since it follows the T "-" E
pattern.

Note that the double quote is just a notational device to distinguish
terminal symbols from non-terminal ones.

Can you go on from here?


How to solve this recurrence using recursion tree method How to solve this using the recursive tree method? I'm stuck with the $\max$.

$$T(n) = T\left(\left\lceil \frac{n}{\max\,\{\sqrt{n},2\}}\right\rceil\right) + n\,.$$

Break it up into parts you can handle.

$\max\,\{\sqrt{n},2\} = \sqrt{n}$ if, and only if, $n>3$, so rewrite the recurrence as

$$\begin{align*}
T(n) &= T(\lceil\sqrt{n}\,\rceil) + n && \text{for } n>3\\
T(n) &= T(\lceil n/2\rceil) + n &&\text{for } n\leq 3\,.
\end{align*}$$

At that point, I think it's reasonable to solve the $n\leq 3$ part by direct substitution and then use required method for the $n>3$ case.

By the way, you also need a case for $T(1)$, since the general equation gives $T(1) = T(\lceil\tfrac12\rceil)+1 = T(1)+1$, which is impossible.


Backpropagation for 'Classification' Neural Network Question: How does one formulate a back propagation algorithm (either batch, gradient, anything that works) for a neural net, playing a game of Tic Tac Toe?

(Java is being utilized)

Scenario: There are 9 input neurons, one for each square. A value of -1 represents X, 1 represents O, and 0 represents an empty space. These values are stored in 1x10 array (the tenth input being bias). These lead to a single hidden layer, with n nodes (n selected on boot). The weights between the input and hidden layer are stored in a 10 x n array. A typical sigmoid activation function is used on the hidden layer. The hidden layer then leads to 9 output neurons, with weights stored in a n x 9 array. A separate function is used to normalize the output, dividing every point by the largest output, and whichever neuron is storing "1", the next move is made there. I've gotten this portion to work.

The cost function is as follows- Every board has an "advantage", which is equal to 10(turns till lose) - 8(turns till win) - 100(boolean invalid[i.e. placing a piece over another piece]). A negative advantage is bad for the AI, positive is good. Cost therefore, is cost = 1/2(best possible delta(advantage), - the delta(advantage) that the AI comes up with)^2. Squared in order to make the function convex, multiplied by .5 for the power rule to make it cleaner.

Here lies the problem: I need to calculate the derivative, so I know what way is down hill. How do I calculate the derivative for the advantage function, if it uses if statements, loops, etc.? It really is more of an operator, than a function- is there a way to re-write a cost function for tic-tac-toe which would be more conducive to machine learning? Or is there a way to derive around this?

I hope I explained that correctly- P.S. This is not for a class, rather my own blatant curiosity.

As D.W. points out, please consult a textbook on neural networks, or Wikipedia. The answer to your question lies in the insight that neural networks do not inspect the cost function or algorithm used to compute it, but it is an empirical method. That is, you will have to play many games of Tic Tac Toe (or generate configurations at random, whichever), compute the cost function yourself, and then feed the configuration with its cost function to your neural network, which then does backpropagation, and repeat. Alternatively, you may collect a large batch of data and feed the batch to the neural network. Either way, the gradient of the network at a particular configuration is a value computed only from available data.

That said, and while most numerical algorithms have no well-defined derivatives, there are edge cases, for example the identity function $f(x) = x$, but most have no practical use. Then there are algorithms that estimate the derivative of a function such as the one you supplied form a large batch of data that a neural net can use to aid its search by improving its gradient estimate, but that will get you into some very deep waters. Deep waters, but fun waters, so consult a textbook if you want to know about that.


Is a universal assembly language for all computers possible? I would like to ask a few questions about Assembly language. My understanding is that it's very close to machine language, making it faster and more efficient.

Since we have different computer architectures that exist, does that mean I have to write different code in Assembly for different architectures? If so, why isn't Assembly, write once - run everywhere type of language? Wouldn't be easier to simply make it universal, so that you write it only once and can run it on virtually any machine with different configurations? (I think that it would be impossible, but I would like to have some concrete, in-depth answers)

Some people might say C is the language I'm looking for. I haven't used C before but I think it's still a high-level language, although probably faster than Java, for example. I might be wrong here.

Assembly language is a way to write instructions for the computer's instruction set, in a way that's slightly more understandable to human programmers.

Different architectures have different instruction sets: the set of allowed instructions is different on each architecture.  Therefore, you can't hope to have a write-once-run-everywhere assembly program.  For instance, the set of instructions supported by x86 processors looks very different from the set of instructions supported by ARM processors.  If you wrote an assembly program for an x86 processor, it'd have lots of instructions that are not supported on the ARM processor, and vice versa.

The core reason to use assembly language is that it allows very low-level control over your program, and to take advantage of all of the instructions of the processor: by customizing the program to take advantage of features that are unique to the particular processor it will run on, sometimes you can speed up the program.  The write-once-run-everywhere philosophy is fundamentally at odds with that.


Help me understand the logic behind x - y in binary by boolean? x and y are 4 bit signed numbers (2s complement..)

x - y can be obtained by:

!(!x + y)

I know that in 2s complement

-y = (!y + 1)

So I can pretty much understand how this works:

x - y = x + (!y + 1)

But, what sort of magic is going on in here, how does this work:

!(!x + y)

I mean, when I do the math with pen and paper all is fine, but I do not know why it is working..


Hyperexponentiation modulo a prime Let $a\uparrow^{n} b $ denote the indexed version of Knuth's up-arrow notation ($a \uparrow\uparrow \dots \uparrow b$ with $n$ arrows), with $a, b, n$ positive integers.

Is there a generalized algorithm to compute $a\uparrow^{n} b$ modulo a prime efficiently? How does the complexity of such an algorithm depend on $n$? What if we restrict $a$ and $b$ to also be prime, or if we remove the requirement for $p$ to be prime?

Maybe.

Consider the problem of calculating $a^{a^b} \bmod p$. What we do here is calculate $x = a^b \bmod (p-1)$, which is the exponent we need to do $a^x \bmod p$, which is our answer. This is due to Fermat's Little Theorem, which states that for prime $p$:

$a^{p-1} \equiv 1 \bmod p$

You may notice that this intermediate exponential is smaller. Also, given a composite modulus, we can break it into factors, calculate for each of the those factors separately and combine with the Chinese Remainder Theorem. So the modulus can shrink pretty fast.

This means that a power tower can only grow to a certain size, beyond which the modulus used to calculate the upper parts of the tower is zero, so the part of the tower above that threshold has no effect on the result.

So tetration at least may be easier than it would at first appear. That said, there is also the requirement that you can swiftly factorize p, which makes large p difficult to work with.


"Reshaping" vs Polymorphism In Data Wrangling A lot of the work in data science -- machine learning in particular --involves "reshaping" arrays, tables, and other data structures.  These data transformations are not really lossy transformations (except for subsets/selective views), but rather simply getting existing data into a different form acceptable to existing algorithms.
This seems to be a big step backward in computer science, away from data abstraction.  In particular, it seems polymorphism has somehow been forgotten in all the work geared toward morphing the data into the proper form.
Am I missing something about this problem that renders it particularly immune to the application of mature technologies to hide data representation from the abstract functions?

Am I missing something about this problem that renders it particularly immune to the application of mature technologies to hide data representation from the abstract functions?

I would say so. And that is empirical experience of what works.
In theory data is data. A general artificial intelligence agent should be able to classify a picture as a cat or a dog regardless of whether it's a photo, a drawing, in color or black/white, altered through an Instagram filter to have a human face, a PNG, JPEG or MP4, compressed with zip, or infinite other possibilities.
But that's purely theory. In practice data representation matters, a lot. The very same task your machine learning method gets state of the art on might not learn at all if you change the data representation. In practice feature engineering is a huge part of any machine learning project. And the existence and importance of this task should indicate that with current techniques it's not feasible to even begin to think of hiding the data representation.

As an example, take the recent success of GPT-3 and transformers. The entire novelty of this technique comes from the way data is represented and learned from inside the neural network.
Another example, AlexNet. It popularized the now standard deep convolutional neural network. A convolutional neural network only really 'works' on (multiple slices of) 2D data. Any other representation and the convolution stops making any sense at all.
In state of the art machine learning, data representation is everything.


What is the upper bound on the number of nodes in a tree with n leaves where each internal node has at least two children? The pieces of information available to us are the number of leaves in a tree and that each internal node must have at least two children. Is there a way to find the upper bound on the total number of nodes in the tree?

Is there a way to find the upper bound on the total number of nodes in the tree?

Yes. There is actually a formula for the exact number: see e.g. these notes:

A full $m$-ary tree with $l$ leaves has $n = \frac{ml - 1}{m - 1}$ vertices and $i = \frac{l-1}{m-1}$ internal vertices.

Here, $m$-ary means that every internal node has between $1$ and $m$ children, and full means that every internal node has exactly $m$ children (the maximum). So in your case, for a full binary tree, just plug in $m = 2$ to these formulas.

By the way, to derive such formulas, you can count the number of vertices in the tree in two ways. First, they are either internal or leaves, so
$$
n = i + l
$$
Second, we can obtain the total number of vertices by adding up the number of children over all nodes, plus the root, so
$$
n = 1 + \sum_{v \in V} \text{children}(v) = 1 + mi,
$$
because each internal node has $m$ children and leaves have no children.
Now set the two equal and we have
$$
i + l = 1 + mi,
$$
from which we can derive the above results.


Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$ is not regular by use of Pumping Lemma I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it.

Question

Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$ is not regular by use of Pumping Lemma. I know the correct way of prove with factorial or using closure. However today someone explain a way to me and I couldn't find what is wrong with it. I think it is wrong but if it is true, is it possible to explain why?

Proof (Maybe correct):

we suppose that that $L$ is regular and there is a machine with $u$ state that accept it. If it is a NFA, we can convert any NFA to DFA with for example $k$ state.
We have a group of strings like $a^kb^{k + t}$ for every $1 \le t \le k$ which accepted with machine.
There is only one way for read $a^k$ because our machine is DFA so we can write $a^k = a^sa^ta^p$ that $|a^sa^t| \le k$ and $|a^t| \ge 1$ and $a^t$ is cycle, so with pumping lemma we can say that $a^{k + t}b^{k + t}$ (with one more time of cycle) belongs to $L$ and it is contradiction. (one of our strings in our first group will fail) so our language is not regular.

My Problem

Because we we get a group of strings (instead just one strings which is normal in proves) and use same $t$ when break $a^k$ to $a^sa^ta^p$, is it true anymore? If no or yes, please explain.

My explanation

I think we can construct a NFA that accept each of $a^kb^{k + t}$ (for each $t$) with different size of cycle (cycle that is used in pumping lemma) however when convert it to a DFA, I can't understand how to prove it.

This is a trick question. Your proof doesn't quite work, but can be turned into a proof, as follows.

Let $p$ be the constant in the pumping lemma, and consider the word $a^pb^{p+p!} \in L$. According to the pumping lemma, it can be decomposes as $xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. Since $|xy| \leq p$, we must have $y = a^q$ for some $q \leq p$; since $y \neq \epsilon$, we must have $q \geq 1$. Let $i = p!/q + 1$. Then you can check that $xy^iz = a^{p+p!} b^{p+p!} \notin L$, contradicting the pumping lemma.

Here are two more proofs. The first uses closure properties. If $L$ were regular then so would the following language be: $a^*b^* \setminus L = \{ a^nb^m : n = m \}$. However, this language is known to be non-regular.

Another proof uses Myhill–Nerode theory. Let us say that two words $x,y$ are incomparable if there exists a word $z$ such that $xz \in L$ but $yz \notin L$, or vice versa. In any DFA for $L$, we must have $\delta(q_0,x) \neq \delta(q_0,y)$ (why?). Therefore, if we can find an infinite collection of pairwise incomparable words, then the language is not regular (why?). In the case of $L$, such a collection consists of the words $a^i$ for all $i \geq 0$. Indeed, if $i \neq j$ then $a^ib^j \in L$ whereas $a^jb^j \notin L$, showing that $a^i,a^j$ are incomparable.


Easiest improvement on first-fit for bin packing algorithm See the interactive example here. First-fit on the left, optimal on the right.

I know that in general, optimal bin-packing is NP-hard, so I'm not looking for a perfect solution. I'm looking for the lowest cost improvement over the current solution.

The problem is the one most of the web pages on the internet have: How to best pack a set of rectangles into an enclosing rectangle, preserving order, with no overlaps. Actually the enclosing rectangle is only a fixed width, it expands to arbitrary height needed to fit all the rectangles, but we still want everything aligned along the top.

Real web browsers do it by relying on a rather restrictive set of rules, one of the most significant of which is that the items are presented in a given order and that order must be maintained when laying out the items in the same way text is laid out, which for English is left-to-right, top-to-bottom.

For some cases, though, such as a set of images, the order could be changed somewhat in order to achieve better packing. We do want to limit the reordering, so that an item ends up no more than n places out of position, but we don't need n to be zero.

A web library called Packery implements this with a basic first-fit algorithm. With "gravity" pulling the rectangles to the top-left, it places the first item where it will fit, which of course is the top-left of the enclosing rectangle. It then places the next item where it will fit, and so on, until all the items are placed.

This works very well when the rectangles are all related by small integers, e.g. 1x1, 1x2, 1x3, 2x1, 2x2, 2x3, 3x1, 3x2, 3x3, with the enclosing rectangle being some integer width, and there are enough small rectangles. In our example the outer rectangle is 3 units wide. Our inefficient packing algorithm on the left becomes optimal on the right with the addition of just 2 more rectangles that match the voids.

So the question is: is there a low-cost way to detect the inefficient packing and backtrack or make some other alteration to get to the efficient packing in the middle? Keep in mind that we want to preserve order as much as possible, so the optimization of pre-sorting the list so that the largest rectangles are first is not acceptable.

One "easy" option is to, after the first-fit algorithm has run, do a local search, i.e. checking if there are any k swaps / moves that you can do to improve the packing (i.e. removing a row or column) (for a relatively small value of k).

I also suspect, although this isn't rigorous by any stretch of the imagination, that you could, to a specified maximum depth, do a search-and-backtrack with the current element and next element every time you hit an element that is larger than the next element. In this case, for instance, you have the elements [1x1, 2x1, 1x1, 1x2, 1x3]. You specify a maximum depth, say 1. Then you start packing elements. In this case just packing [1x1] so far. When you hit the 2x1, you try packing [2x1, 1x1, 1x2, 1x3], , but you also branch and try packing [1x1, 2x1, 1x2, 1x3]. Ideally with an alpha-beta search, but you can also just try going to a specified lookahead and then seeing which is better.

Also, note that that particular packing library has... issues. In particular, when you tell it to pack [1x1, 1x1, 2x1, 1x2, 1x3] it does this: