Product of the entries of the product of two matrices Let $A=(a_{ij})$ and $B=(b_{ij})$ be $n \times n$ integer matrices. Then $AB=(\Sigma_{k=1}^n a_{ik}b_{kj})_{ij}$. I am interested in finding the most efficient algorithm for computing the product of the entries of $AB$,

$\Pi_{i,j=1}^n (\Sigma_{k=1 }^n a_{ik}b_{kj}$).

Certainly, the most straightforward way of doing this (by using the above formula) is not the most efficient way of doing this, since there are algorithms like Strassen's algorithm which calculate all of the entries of the matrix $AB$ faster than simply applying the definition $AB=(\Sigma_k a_{ik}b_{kj})_{ij}$ to each entry.

Are there other efficient ways to compute the above product besides using algorithms like Strassen's algorithm?

Extra: What about computing the sum of the entries of $AB$,

$\Sigma_{i,j,k=1}^n a_{ik}b_{kj}$?

You are asking two questions. I will only answer the second one. Let $1$ be the all ones column vector of dimension $n$. The sum of all entries of $AB$ is $1^TAB1 = (1^TA)(B1)$, which gives an $O(n^2)$ algorithm: compute the vectors $1^TA$ and $B1$, each in $O(n^2)$, and then compute their inner product in $O(n)$. This corresponds to the identity
$$
\sum_{i,j,k=1}^n a_{ik} b_{kj} = \sum_{k=1}^n \left(\sum_{i=1}^n a_{ik}\right) \left(\sum_{j=1}^n b_{kj}\right).
$$

As for the product of all entries, I suspect you can't do better than the trivial algorithm which first computes the entire product matrix, and runs in time $O(n^\omega)$.


Are there any hash functions/stateless RNGs that do not use XOR, but produce good quality visual randomness? I'm looking for a small function from integers to integers - in a language that only has floats - that can act as a visual RNG. Normally I would use a function such as the one described here:

int cash(int x, int y){
    int h = seed + x*374761393 + y*668265263; //all constants are prime
    h = (h^(h >> 13))*1274126177;
    return h^(h >> 16);
}

However, for the thing I'm working on, I have the added restriction of only using arithmetic operations. the operations I have available are: +, *, -, /, %, sign(), abs(), pow(base, exponent), ln(), floor(), as well as basic trig functions. I'm having difficulty finding anything that doesn't rely on having bitwise operations available. Does anyone know of a hash function that doesn't use xor, that produces reasonable visual randomness when fed a linear sequence of integers?

Found a solution here, as glsl, which at one time had near exactly the same restrictions I wanted:

float rand(vec2 co){
    return fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * 43758.5453);
}

or as I implemented it: $\operatorname{mod}\left(\sin \left(a\cdot 12.9898+b\cdot 78.233\right)\cdot 43758.5453,\ 1\right)$


Is this set semi-decidable? A set of all  that M is a TM halts on all input strings w such that w <= q(M) where q(M) is the number of states in M $A$ is a set of all $\langle M \rangle$ that $M$ is a TM halting on all input strings $w$ such that $\lvert w \rvert \le q(M)$ where $q(M)$ is the number of states in $M$.

Is $A$ semi-decidable? Is a complement of $A$ semidecidable?

I think $A$ is semi-decidable. We can construct $M1$.

$M1$ = "On input $\langle M \rangle$ where $M$ is a TM

Simulate $M$ on input with all of the string whose length is less than $q(M)$. If it halts for all, accept"

The complement of $A$ is not semi-decidable. But I'm not sure how to prove it.

To show that $\overline{A}\notin RE$ you want to show that another language $B\notin RE$ is reducible to it.

First, the complement of $A$ is the set of all $\left< M \right>$, where $M$ is a Turing machine, and $\exists w$, $|w|<q(M)$ s.t. $M$ doesn't halt on $w$.

Remember that you can add unreachable states to a Turing machine, therefore increasing $q(M)$. The next step would be picking a language who is known to be not decidable (e.g. the complementary of the halting language $\overline{H}$), and think of a reduction to $\overline{A}$.


Difference between IO threads and worker threads I have read that NodeJs is able to support hundreds and thousand of concurrent calls because the worker threads do not wait on the IO calls to complete. They use event driven IO.  Similarly in .NET we have Async keyword which allows the worker thread to be returned to perform other tasks while the "IO" call is executing. How does that all work.  There has to be some thread monitoring for the IO to complete and notify when its ready?

I don't know NodeJs or .NET, and they would be off-topic here anyway, but the underlying concepts are common among programming frameworks and programming models, so I'll answer in general terms.

The word thread can mean several things.

There is the conceptual meaning: one thing happening after another.
There is the way this conceptual meaning is represented in a programming language. In almost all programming languages, most ways to combine program fragments lead to those fragments being executed one after the other, thus in a single thread, e.g. a; b is a very common syntax for “execute a then b”. A few keywords, operators or library functions allow code to be executed in a way other than in sequence, e.g. fork in Unix or Async in .NET. These create conceptual threads.
There are ways to implement this concept at the operating system level. These fall mainly in two categories (refinements are possible but I won't get into those):

Kernel threads are managed by the OS kernel. The threads live independently. If one thread in a program is blocked on an IO call, that doesn't affect the other threads.
User threads (also called green threads) are managed by the program. From the perspective of the kernel, there is a single thread, so if the program blocks on an IO call, none of its threads can run. To allow non-blocked threads to keep running, the programming library must ensure that it makes only non-blocking system calls (it may expose blocking functions in the programming interface, however).

There isn't always a direct match between programming language threads and operating system threads. There are several potential reasons for such a mismatch:

The language was designed with a certain model in mind, but it's implemented on an operating system which doesn't have primitives that map directly to that model.
The language induces programmers to use threads a lot, but kernel threads are somewhat expensive. So many programming language threads are executed in the same kernel thread. Instead of using blocking IO, the library functions uses non-blocking IO exclusively, and calls a function such as select or poll which returns as soon as one pending I/O is unblocked.
I don't know NodeJS, but “able to support hundreds and thousand of concurrent calls because the worker threads do not wait on the IO calls to complete” sounds to me like this is what's happening.
The language discourages programmers from explicitly using threads, possibly because threads with shared memory is extremely hard to get right (the potential for race conditions is huge). Instead, it favors higher-level abstractions where parallel threads are mostly independent. Under the hood, those abstractions may be implemented with operating system threads.
I don't know .NET, but async/await sounds to me like it's implementing a rendezvous abstraction. The async keyword creates a thread which lives its own life until await joins it with its parent.


Find K-subset that includes the most W-subsets I have a set $S$ of $N$ elements, and a set $\Sigma$ of $N$ subsets of $S$: $\sigma_0, \ldots, \sigma_{N - 1} \subset S$, each with $W \ll N$ elements.
Subsets can overlap partially or totally.

For a given $K < N$ (but $K \gg W$), I want to determine the subset $X_K \subset N$ so that:

$X_K$ has $K$ elements.
$X_K$ includes the largest possible amount of subsets among $\sigma_0, \ldots, \sigma_{N -1}$.

Example:

$S = \{A, B, C, D, E\}$, $W = 3$

$\{\sigma_0, \ldots, \sigma_4\}= \{\{A, B, C\}, \{A, B, C\}, \{B, C, D\}, \{A, B, E\}, \{A, B, D\}\}$

$X_4 = \{A, B, C, D\}$ (as it includes $\sigma_0, \sigma_1, \sigma_2$ and $\sigma_4$)

What is the best algorithm to find $X_K$?

I had the same problem a few days ago and I used the following heuristic to do it. According to my first impression it seems to work.

My specific use case was to determine a strategy in which sequence I should convert function implementations from one programming language into another so that we can execute as many test runs with as little effort as possible (in this case the set of functions is $S$ and the test runs are $\Sigma$ and our goal is to cover as many $\sigma \in \Sigma$ as possible with as few elements from $S$ as possible).

Example Data

So let's setup some example data. We have five sets $\sigma$ with different elements inside.

$$
\sigma_1 = \{s_1, s_3, s_4\} \\
\sigma_2 = \{s_1, s_5, s_6\} \\
\sigma_3 = \{s_1, s_3 \} \\
\sigma_4 = \{s_1, s_3, s_4, s_5, s_6\} \\
\sigma_5 = \{s_1, s_2, s_3, s_6\}
$$

My Current Approach

I give each $s_j$ a rating based on the total number of time it exists. Then I check how many elements each $\sigma$ contains. I will then calculate the division between these two numbers and select the $\sigma$ with the highest rating as first winner.

In my opinion this should give me the quick win sets first. I will get at least one set covered and I try to trade-off between trying to get the smallest set first, and trying to select the $s$ that are used the most (i.e. with which I could probably cover the most $\sigma$).

Let me explain this approach on the example above. If we count the number of occurrences for each $s$, we get:

$$
\text{Usages}(s_1) = 5 \\
\text{Usages}(s_2) = 1 \\
\text{Usages}(s_3) = 4 \\
\text{Usages}(s_4) = 2 \\
\text{Usages}(s_5) = 2 \\
\text{Usages}(s_6) = 3
$$

If we use these and the number of elements in each $\sigma$ we get the following ratings:

$$
\text{Rating}(\sigma_1) = \frac{\text{Usages}(s_1) + \text{Usages}(s_3) + \text{Usages}(s_4)}{3} = \frac{5 + 4 + 2}{3} = \frac{11}{3} = 3.67 \\
\text{Rating}(\sigma_2) = \frac{5 + 2 + 3}{3} = \frac{10}{3} = 3.33 \\
\text{Rating}(\sigma_3) = \frac{5 + 4}{2} = \frac{9}{2} = 4.5 \\
\text{Rating}(\sigma_4) = \frac{5 + 4 + 2 + 2 + 3}{5} = \frac{16}{5} = 3.2 \\
\text{Rating}(\sigma_5) = \frac{5 + 1 + 4 + 3}{4} = \frac{13}{4} = 3.25
$$

In this case, I would add the elements $\{s_1, s_3\}$ to my set $X_k$ first.

For the next iteration I would delete $\sigma_3$ from the candidates and repeat the process.

Related Problems

I think that is problem is closely related to the set cover problem. However, it is different and I did not find a way to convert my problem into a set coverage problem. It also was different to any other algorithm I found in the area of set cover problem (e.g. set packing, dominating set, maximum coverage problem). Maximum coverage problem seems to come very close, but it is again a bit different.


Are instructions defined as expressions with side-effects? Can we define instructions as expressions with side-effects?

The answer is no. But this is hardly enough.

I think you put your finger on a slightly sore but important point of
computer science and programming. We can pretty well define what is an
expression because that is well formalized in mathematics. But we
somehow wave our hands on what constitutes the essence of instructions, or
side-effects.  "Side-effect" is itself a strange word, with an almost
negative connotation, which says a lot about mixed feelings on the
issue. I do not mean that instructions have not been well formalized with
precise semantics (they have), but they often seem perceived more as a necessary
evil than as a desirable tool. And this is not easily explained. Maybe it is that, unlike expressions, they do not have an obvious counterpart in mathematics. There may be other issues.

But let's try to see the difference.

Mathematically, expression are precisely defined syntactic structures,
often called well formed formulae. From a computational point of view,
these expression are operateur operand structures, that are
interpreted in some domain of value (for operands) and of functions
(for operators). And an expression is just supposed to apply the
functions to the values in the order specified by the structure and
come back with the result (this is pretty close to the abstract
mathematical notion). As in mathematics, a function is supposed to be
just a mapping, giving a result in a given range.

I would define an instruction as a syntactic writing meant to specify
a modification in an environment. What then is an environment? An
environment is something that can be modified, and that can thus
memorize information (I should add transmit information, but let's
stay simple). A typical and very simple environment is the state of the finite
control of a Finite Automaton (FA). It can be changed, and the change
is memorized and can be used later on. A transition of a FA is an
instruction, since it changes the environment. In the case of a Turing
Machine the environment is constituted of the state of the finite control, the tape
content, and the position of the head on the tape. The content of the environment is precisely what is often called an instantaneous description of an automaton.

Since a side-effect is a modification of an environment, one
could say that an instruction is a syntactic structure meant to specify
a side-effect.

Note that the concept of environment (thus of side-effect) is itself
relative. It may be internalized so that we do not even have to know
it exists. For example, the evaluation of an expression may be done by
a device operating with a succession of instructions modifying a small
environment, until the end result is obtained. The modifications and the environment itself can
then be forgotten, and only the result is kept. There may have been
temporary "local" side-effects, but they are irrelevant outside the
evaluation of the expression. That is actually what happens in the
computer. But we still say that the evaluation of the expression has
no side-effect (none remains).

An environment can include places to store values (what is usually
called a variable). An instruction may be an assignment of a value in
some variable, and the value itself may be specified with an
expression. Conversely, the expression can include variables, and is
evaluated by replacing the variables by their current value in the
environment. So the two concepts interact, and are really two faces of
a computational coin.

Note in passing that we have considered that some environments are
more transient than others (for evaluating an expression). That means
that we may actually consider many environments. Managing environments
is actually a major issue in programming language design, and in
programming, particularly to make side-effects as transient as
possible to make program analysis and maintenance easier.

Coming back to our computational coin, the two faces appear in
various guises:

denotational semantics vs operational semantics;
lambda-calculus,
combinatory logic or recursive funtion theory vs Turing Machines, automata and rewriting systems;
evaluation of expressions vs execution of instructions;
functional programming vs imperative programming;
regular expressions vs finite automata.

Sometimes, the same text can allows both readings. A context-free
grammar can be seen as a set equations between expression valued in
sets of strings (denotational view) or as a string rewriting system
(operational view).

Of course, in programming languages, things are made more complicated
by the mixing of expressions and instructions. Instructions use values
that are obtained by evaluation expressions. That is not too bad.
What is worse is that the evaluation of some expressions may cause
side-effects. This is because programming languages often allow
implementing functions with instructions as described above, but
without restricting the side-effects to a local environment that
disappear when the function terminate.

It may also happen that a function will not always return the same
result when called with the same arguments, because it uses internally
values provided by an outer environment that may be subjected to
side-effects. Though it is sometimes put to good use by programmers,
this may be a reason for the distrust of side-effects, as it seems to depart from our mathematical understanding of functions.


What kind of logarithm does $\log$ mean in Wikipedia articles? Sorry if this seems like a dumb question, but what what type of logarithm is $\log$ in Wikipedia articles? Cheers.

It depends entirely on context. In mathematics as a whole, $\log$ usually denotes the natural logarithm (base $\mathrm{e}$). In computer science, the situation isn't as clean because we often want to talk about things like a number of bits or the height of a binary tree and, in those cases, the most natural (*baddum-tsh*) logarithm to use is base-$2$.  Some authors use $\ln$ and $\lg$ to explicitly denote base-$\mathrm{e}$ and base-$2$ logs, respectively; many authors just write $\log$ to mean whatever base is most appropriate for the situation.

Of course, Wikipedia is written by a huge number of unconnected authors, so you can't assume any consistent convention is used. Indeed, a careful Wikipedia editor would make sure that $\log$ is used consistently within an article, but you can't rely on everyone being careful.

It usually doens't matter. Changing the base of a logarithm just multiplies the answer by a constant factor because, for all $a,b>1$ and all $x>0$,
$$\log_a x = \frac{\log_b x}{\log_b a}\,.$$
In many situations, this multiplicative factor of $1/\log_b a$ isnt at all important. In the context of a big-$O$, big-$\Theta$, big-$\Omega$ etc bound, $O(\log n)$ means the same thing regardless of the base, since big-$O$ disregards constant factors. (But note that, e.g., $2^{\log_2 x}=x$, whereas $2^{\log_3 x}=x^{1/\log_2 3}\approx x^{1.58}$ so there are situations in which the base makes a big difference.)

Your specific example. In a comment, you say you're specifically interested in the page about tf-idf. I know nothing about document retrieval but my understanding from skim-reading that article is as follows. We're interested in ranking documents according to their relevance, and the relevance of a document is given by a score of the form $x\log y$, where $x$ and $y$ are statistics of the document. Since changing the base of the logarithm just multiplies all the scores by a constant, it doesn't change the ranking order. Therefore, it doesn't matter what base you use for the logarithm in this situation.


Separate all leaves of a weighted tree with minimum weight cuts This is part of a larger problem, which I believe I have reduced to this. Given a tree $T$ having positive edge weights, and $k$ leaves (nodes which have exactly one connected node), I need to delete some edges in the tree so that no two leaves in the original tree are connected (by a path) in the newly formed forest (of trees). The total sum of the weights of the deleted edges needs to be minimized.

My understanding is that atleast $k-1$ edges need to be deleted to separate out all the $k$ leaves. Any more deletions will unnecessarily increase the total cost. Thus, we need to perform exactly $k-1$ deletions.

My hypothesis:
For every pair of leaf nodes $l_i$ and $l_j$, find the edge with the minimum weight in the (unique) path from $l_i$ to $l_j$. The $k-1$ least weight edges from this set of edges need to be deleted. This will minimize the sum of weights of the edges to be deleted in order to disconnect all leaves from each other.

I am unable to prove or disprove this hypothesis. Can someone please prove the correctness of this hypothesis, or give a counter-example along with the correct algorithm to solve this problem? If this is indeed correct, is there a faster way (asymptotic complexity wise) to solve this problem? This approach will take $\Theta({k^2})$ time. Thanks in advance!

For each node $v$ with height 1 (all its children are leaves): If $v$ has degree $d$ and $d - 1$ children, then the $d-2$ smallest edges are added to the cut. These cuts are required to separate the children of $v$ from each other. Now, all but one child (leaf) of $v$ has been separated from the rest of the tree.

Now consider all the nodes $v$ with height 2.  Each of these nodes with degree $d$ has a single parent edge (assuming that $v$ is not the root), and $d - 1$ paths of length at most two connecting it to the leaves in its subtree. We must remove the minimum edge from exactly $d - 2$ of these paths in order to disconnect these leaves from each other. Add these edges to the cut. Now all but one leaf in $v$'s subtree has been separated from the rest of the tree.  This leaf is connected to the parent of $v$ and the rest of the tree by a path of length at most $3$. Later on, we will be required to remove at most one edge on this path, so we don't need to track all edges, just the one of minimum weight.

Now consider all nodes $v$ with height $h$. Each of these nodes with $d - 1$ children has exactly $d - 1$ leaves connected in its subtree. Each of these leaves are connected to $v$ by a path of length at most $h$, but have also stored the minimum weight edge on this path. We must cut the smallest $d - 2$ edges in order to separate these leaves from each other. The remaining leaf is connected to the rest of the tree via a path of length at most $h + 1$, and in constant time we store its new minimum weight edge by comparing the old minimum with the weight of the edge (v, v.parent).

By working through the nodes in height order, we maintain the invariants that:

In each subtree, we have selected the minimum cut to separate the leaves in that subtree.
Each subtree has exactly 1 leaf connected to the root of the subtree.
Each subtree maintains the minimum weight edge on the path to that leaf.
Each subtree with $k$ leaves has selected exactly $k-1$ edges for its cut.
Each subtree is processed in $O(d)$ time, where $d$ is the degree of the root of the subtree.

Correctness and a running time of $O(n)$ follow from these invariants.


General algorithm to find a minimal branching program Given a general branching program, is there an algorithm which can find an equivalent branching program $P$ of minimal length. That is $|P| \leq |P'|$ for all equivalent branching program $P'$.

If not, are their some specific cases where this algorithm exists?

I'm assuming you mean branching programs in the sense of generalized binary decision diagrams (see here).

Now the question is whether by "length", you mean "size" or "depth". I will answer the "size" version here, as you will most likely mean that (and the depth version has some intricacies).

We can represent a smaller solution in space not larger than the input size. Furthermore, checking two branching programs to be equivalent is a problem contained in the complexity class co-NP.

Hence, we can define an algorithm in $\Sigma^P_2$ (see here) for finding if there exists a smaller equivalent branching program by letting it first guess a smaller solution, and then verify it to be correct using the co-NP equivalence checking oracle.

Note that this may not be an algorithm that is complexity-theoretically optimal. However, the existence of this algorithm answers your question with a "yes".


Alternative way of proving a language is $NP$ I would like to show a language $A$ is in $NP$.

I can find a TM for $A$, but I wanted to try a different approach and see if it is correct.

Let $B$ be a known problem in $NP$. If I show a polynomial time reduction $A \leq B$, will this imply $A\in NP$?

I believe it will, but I am not 100% sure.

It depends on exactly what kind of reduction you're using.  Assuming that you mean a polynomial-time many-one reduction (also called "mapping reductions") then, yes, if $A$ reduces to $B$ and $B\in\mathrm{NP}$, then $A\in\mathrm{NP}$, also.  This was probably proven to you when you started to study reductions between $\mathrm{NP}$ problems.

If you mean polynomial-time Turing reduction, it's an open problem whether $A\in\mathrm{NP}$.  This corresponds to the question of whether $\mathrm{NP} = \mathrm{P^{NP}}$.

If you don't know what kind of reduction you mean, you should check with your teacher, but it's probably many-one reductions.  Those are the ones that are most commonly used with respect to problems in $\mathrm{NP}$.


Examples of Regular, Context-free and Context-sensitive languages Assume the languages:

$$
a) \, L_1 = \{ w \in \{b,c \}^* | \, w \, \text{contains 'bbc' as substring} \}
$$
$$
b)\,  L_2 = \{ 1^k 0^m 1^m | k,m \in \mathbb{N} \}
$$
$$
c)\,L_3 = \{ w \in {0,1}^* | \, w \, \text{is a multiple of 5 (binary system) }\}
$$
$$
d)\,L_4 = \{ d^k e^m f^k | k,m \in \mathbb{N}, \, k < m\}
$$

$L_1$: Since we could build an NFA which accepts its strings, it's regular.

$L_2$: Using a single stack or PDA, by pushing $0$ to the stack for every $0$ in the string and then poping from the stack for every $1$ (after the $0$s) in the string, we can determine whether the string is in the language if the stack ends up empty. Thus, $L_2$ is context-free.

$L_4$: Same as above, but this time we need $2$ stacks (LBA). Push $0$s in the first stack for every $d$, push $1$s in the second stack for every $e$ and then pop from the two stacks for every $f$. If the first stack ends up empty and second ends up non-empty, then the string belongs to the language. Thus, $L_4$ is context-sensitive.

Are the above conclusions correct? If so, please provide me with a hint for the classification of $L_3$.

$L_1$, $L_2$ and $L_4$ are correct (notice that you are not showing that $L_2$ is not regular and $L_4$ is not context-free, which can be done using the appropriate version of the pumping lemma).

As far as $L_3$ is concerned, let  $x$ be the number that is encoded in binary and call $x_i$ its $i$-th least significant bit, indexed from $0$. Then, counting modulo 5, we have:

$\displaystyle x = \sum_{i=0}^\infty x_i 2^i = \sum_{i=0,4,8..} x_i + 2 \sum_{i=1,5,9..} x_i + 4 \sum_{i=2,6,10..} x_i + 3 \sum_{i=3,7,11..} x_i$.

I.e., the least significant binary digit contributes $1$ to $x \bmod 5$, the next one contributes 2, then 4, 3, 1, 2, 4, 3, ... and this pattern repeats.

This means that you can create a DFA that recognizes $L_3^R$ (and hence $L_3$) using at most 20 states, namely $\langle i,j \rangle$ where $i \in \{0,1,2,3\}$ is the index, modulo 4, of the next character in the string, and $j \in \{0,1,2,3,4\}$ is the partial sum, modulo $5$, of the contributions of binary digits seen so far.

If the next bit is $0$ then:
$\langle i,j \rangle \to \langle i+1 \pmod 5, j \rangle$.

If the next bit is $1$ then $\langle i,j \rangle \to \langle  i+1 \pmod 5, j+ 2^i  \pmod 5\rangle$. Writing this down explicitly:

$\langle 0,j \rangle \to \langle 1, j+1  \pmod 5\rangle$;
$\langle 1,j \rangle \to \langle 2, j+2  \pmod 5\rangle$;
$\langle 2,j \rangle \to \langle 3, j+4  \pmod 5\rangle$;
$\langle 3,j \rangle \to \langle 0, j+3  \pmod 5\rangle$.

The initial state is $\langle 0, 0 \rangle$ and the final states are all the ones of the form $\langle i, 0 \rangle$.


Effects of parity bit on odd code length regarding its size after alternation I am trying to understand code distance, but I am not sure regarding the following scenario:

Assume that you have an information word M with m bits, that You code into a coding word using the following procedure:

You take M and code it using a code you know nothing about. But you do know that its distance(code's distance) is k, and that k>2.
You add to the word obtained in the last step a parity bit.

If you know that k is odd, does it necessarily mean that the distance of the code constructed by those two steps is necessarily k+1?

Well, I am not sure here. Code distance is basically the number of different bits, and the meaning of the second step in the procedure(adding a parity bit) is, according to my understanding, allowing the detection of any odd number of errors. Does it necessarily mean that the code constructed by those two steps is necessarily k+1?

Normally a code's hamming distance is limited to some maximum message length. For example in the case of a 32 bit CRC, for Hamming distance = 3 (2 bit error detection), the maximum length for a message is 2^32-1 bits (including the 32 bits of CRC), depending on the CRC used. With a larger message, a  2 bit error can fail. For a parity check or Hamming distance = 2 (1 bit error detection), there is no maximum length limit.

If the message length is <= maximum message length for that Hamming distance, and k is odd (maximum # of error bits detected is even), then adding a parity check in addition to the CRC should increase Hamming distance to k+1.

For example, CRC16 based on polynomial x^16 + x^12 + x^5 + 1 (0x11021) is the product of 2 irreducible polynomials : (x^15 + x^14 + x^13 + x^12 + x^4 + x^3 + x^2 + x + 1) (0xf01f) and (x + 1) (0x3). For message length (including CRC bits) CRC poly (x^15 + x^14 + x^13 + x^12 + x^4 + x^3 + x^2 + x + 1) Hamming distance is 3 for message length up to 32767 (2^15-1) bits, and the (x + 1) term increases this to Hamming distance 4. As mentioned above, it can detect any odd number of bit errors for any length message.


Exhaustive search algorithms for np-complete problems Somewhere in the forum (a question about p vs np) I read that no exhaustive search algorithm exists for np-complete problems with better time complexity than $2^N$, however the subset sum problem has an algorithm with worst case complexity $O(2^{N/2}$), this looks much better than $2^N$, what is wrong with this?

$O(2^{n/2})$ is still $\mathcal{EXP}$.

The claim you report is known as the exponential-time hypothesis and is a stronger statement than $\mathcal{P} \neq \mathcal{NP}$. We don't actually know if it's true or not.


What did Turing mean when saying that "machines cannot give rise to surprises" is due to a fallacy? I encountered below statement by Alan M. Turing here:

  "The view that machines cannot give rise to surprises is due, I
  believe, to a fallacy to which philosophers and mathematicians are
  particularly subject. This is the assumption that as soon as a fact is
  presented to a mind all consequences of that fact spring into the mind
  simultaneously with it. It is a very useful assumption under many
  circumstances, but one too easily forgets that it is false."

I am not a native English speaker. Could anyone explain it in plain English?

Mathematicians and philosophers often assume that machines (and here, he probably means "computers") cannot surprise us. This is because they assume that once we learn some fact, we immediately understand every consequence of this fact. This is often a useful assumption, but it's easy to forget that it's false.

He's saying that systems with simple, finite descriptions (e.g., Turing machines) can exhibit very complicated behaviour and that this surprises some people. We can easily understand the concept of Turing machines but then we realise that they have complicated consequences, such as the undecidability of the halting problem and so on. The technical term here is that "knowledge is not closed under deduction". That is, we can know some fact $A$, but not know $B$, even though $A$ implies $B$.

Honestly, though, I'm not sure that Turing's argument is very good. Perhaps I have the benefit of writing nearly 70 years after Turing, and my understanding is that the typical mathematician knows much more about mathematical logic than they did in Turing's time. But it seems to me that mathematicians are mostly quite familiar with the idea of simple systems having complex behaviour. For example, every mathematician knows the definition of a group, which consists of just four simple axioms. But nobody – today or then – would think, "Aha. I know the four axioms, therefore I know every fact about groups." Similarly, Peano's axioms give a very short description of the natural numbers but nobody who reads them thinks "Right, I know every theorem about the natural numbers, now. Let's move on to something else."


Lambda Calculus - Call-by-name AND call-by-value reduction I have been tasked with reducing the following lambda expression:

  (λpq.pqp)(λab.a)(λab.b)

using call-by-name and call-by-value reduction strategies.

Call-by-name

strategy: Left-most, outermost redex first but no reduction under lambda.

Step 1) alpha-equivalence

  (λpq.pqp)(λab.a)(λcd.d)

Step 2) Reduction - using the redex (λpq.pqp)(λab.a)

  (λq.(λab.a)q(λab.a)(λcd.d)

Step 3) - substitute (λcd.d) for q

  (λab.a)(λcd.d)(λab.a)

Step 4) - substitute (λcd.d) for a

  (λb.(λcd.d))(λab.a)

Step 5) - substitute (λab.a) for b

  (λcd.d) -> (λab.b)

Which gives the same result if you were to use normal order instead.

Call-by-value

strategy: Right-most, innermost redex first but no reduction under lambda

Step 1) alpha-equivalence

  (λpq.pqp)(λab.a)(λcd.d)

Step 2) substitute (λab.a) for c

  (λpq.pqp)(λd.d)

Step 3) substitute (λpq.pqp) for d

  (λpq.pqp)

You misunderstood call-by-value and are doing it backwards, i.e., you are substituting functions into arguments, instead of the other way around. Call-by-value and call-by-name both use the same rules of reduction, but in different places and in a different order.

In your case the call-by-value and call-by-name do not differ, because the arguments are already reduced.

Here is an example, where the difference matters. Reduce

(λpq.pqp)((λab.a)(λcd.d))

Note that this is different from your examples bacause of the extra parantheses that I put in.

Call-by-name:

(λpq.pqp)((λab.a)(λcd.d)) ➝
λq.((λab.a)(λcd.d))q((λab.a)(λcd.d)) ➝
λq.((λab.a)(λcd.d))q((λab.a)(λcd.d)) ➝
λq.(λb.(λcd.d))q((λab.a)(λcd.d)) ➝
λq.(λcd.d)((λab.a)(λcd.d)) ➝
λq.(λd.d)

Call-by-value:

(λpq.pqp)((λab.a)(λcd.d)) ➝
(λpq.pqp)(λb.(λcd.d)) ➝
(λpq.pqp)(λb.(λcd.d)) ➝
λq.(λbcd.d)q(λbcd.d) ➝
λq.(λcd.d)(λbcd.d) ➝
λq.(λd.d)

The difference is that in call-by-value you normalize the argument before you substitute it for the bound variable.


What is the running time of generating all $k$ combinations of $n$ items $\binom{n}{k}$? I was solving the following problem, just for reference (441 - Lotto). It basically requires the generation all $k$-combinations of $n$ items

void backtrack(std::vector<int>& a,
               int index,
               std::vector<bool>& sel,
               int selections) {
    if (selections == 6) { // k is always 6 for 441 - lotto
        //print combination
        return;
    }
    if (index >= a.size()) { return; } // no more elements to choose from
    // two choices
    // (1) select a[index]
    sel[index] = true;
    backtrack(a, index+1, sel, selections+1);

    // (2) don't select a[index]
    sel[index] = false;
    backtrack(a, index+1, sel, selections);

}

I wanted to analyze my own code. I know at the top level (level = 0), I'm making one call. At the next level (level=1) of recursion, I have two calls to backtrack. At the following level, I have $2^2$ calls. The last level would have $2^n$ subproblems. For each call, we make $O(1)$ work of selecting or not selecting the element. So the total time would be $1+2+2^2+2^3+...+2^n = 2^{n+1} - 1 = O(2^{n})$

I was thinking since we're generating $\binom{n}{k}$ combinations that there might be a better algorithm with a better running time since $\binom{n}{k}=O(n^2)$ or maybe my algorithm is wasteful and there is a better way? or my analysis in fact is not correct? Which one is it?

If you want to generate all items, the runtime is obviously at least O(n over k). To avoid exceeding O(n over k) your algorithm must be quite carefully designed.


Difference between ⫾ (U+2AFE) and ⫿ (U+2AFF) in the context of Dijkstra's Guarded Command Language? Continuing https://tex.stackexchange.com/questions/435986/how-to-draw-the-box-of-dijkstras-guarded-command-language, what is the difference in the intended usage of ⫾ (Dijkstra choice, U+2AFE) and ⫿ (n-ary Dijkstra choice, U+2AFF) in the context of the Guarded Command Language (GCL) of Dijkstra? In other words, when do you use ⫾ and when ⫿ for typesetting GCL programs?

Related:

http://latex.org/forum/viewtopic.php?t=32939
Barbara's take on GCL

Non-deterministic guarded choice is an associative-commutative binary operator. My guess is that the character ⫾ U+2AFE is intended to be used as an infix binary operator and the character ⫿ U+2AFF, which is larger and described as “n-ary”, is intended to be used as a prefix operator which is typeset larger, in prefix position, and typically with a subscript and sometimes a superscript to indicate the range over which the operation is carried out.

$$⫿_{i=1}^n c_i \rightarrow a_i \qquad = \qquad  \mathsf{if}\; c_1 \rightarrow a_1 ⫾ \cdots ⫾ c_n \rightarrow a_n \;\mathsf{fi}$$

Typeset with inline math: $⫿_{i=1}^n c_i \rightarrow a_i = \mathsf{if}\; c_1 \rightarrow a_1 ⫾ \cdots ⫾ c_n \rightarrow a_n \;\mathsf{fi}$

It's the same relationship as between $+$ (binary) and $\sum$ (n-ary), or between $\times$ (binary) and $\prod$ (n-ary) ($\prod$ is sometimes a different product such as $\cdot$). For binary operators other than the two classics addition and multiplication, the n-ary version is the same glyph, just bigger.


How does a program execute with respect to the operating system? I am reading Operating Systems by William Stallings 6th edition and I came across this text,

Program execution:

A number of steps need to be performed to execute a
program. Instructions and data must be loaded into main memory, I/O devices
and files must be initialized, and other resources.

Now I am unable to understand how I/O devices and files are initialized on program execution? I assume it meant to start the I/O resources but what about the files? Please guide. Thanks

A initialized file means that you have comprobe that exist, or open it in some mode (write, read, r&w, etc) and create it if is not already.


Data structure choice for a query-update-delete problem Given is an initial set of n keys. Each key k is of the form (p, q). Note that both p and q are positive.

At any given point, there are two possible actions:

1) Query-Delete: Given a value s as query, find all such keys in the set that have have the (globally) minimum p and satisfy (q >= s), and delete these keys.

2) Insert: Add a new key k' = (u, v) to the set.

I was wondering what would be the best data structure to represent the above.

My first approach is to simply sort the original set in a linked list (or array) and return the appropriate tuples when queried, and if inserted, use linear search to find the position, but the worst-case insertion then becomes O(n), while query-deletion involves checking the first element, and has the complexity O(number of distinct q values).

A second approach is to use a red-black tree with the p values as its key, storing (p, q, r) in each node, where r is the biggest q value found at that level or below in the tree.

For example, given a set (10, 4), (20, 2), (30, 2), (40, 3) the tree looks like:

        (20, 2, 4)
       /          \
 (10, 4, 4)        (30, 2, 3)
                     \
                      (40, 3, 3)

where each node is of the form (p, q, r).

This approach has the benefit of being able to early exit during the query search if (r < s) in the node. Insertion remains O(log n) like in red-black trees, but may face problems with sets of the form {(p, q1), (p, q2), ...}.

Could anyone please suggest modifications or propose a better approach? Thanks.

Store your data structure in a red-black tree where the first component of a key (i.e. p in (p,q)) is the key and the values are red-black trees of the second parts of keys with identical first part.

So, for the set $\{(a,b), (a,d), (d,b), (e,f), (e,g)\}$, you would store a tree with three keys (a, d, and e). The value for the key a would be a red-black tree with b and d, the for the key d would be a red-black tree with b, and the value for the key e would be a red-black tree with f and g.

A red-black tree can be split in $O(\lg n)$ time, so query-delete would take $O(\lg n) + O(\lg n) = O(\lg n)$ time - $O(\lg n)$ for the tree lookup and $O(\lg n)$ for the split of the tree. This doesn't include the cost of deleting, deconstructing, finalizing, or disposing of the deleted elements.

insert would also be $O(\lg n)$.

Query-delete can be made $O(1 + \lg k)$, where $k$ is the size of the deleted set, by keeping a pointer to the smallest key in the big tree and searching from the ends of the little tree, rather than from the root.

Amortized, query-delete is $O(1)$: using the banker's method, simply put a single on each item in the little trees. Since returning $k$ items takes $O(1 + \lg k)$ time and returns $k$ coins, its amortized cost is now $O(1)$, while insert's is $O(1 + \lg n) = O(\lg n)$.


Finding exact corner solutions to linear programming using interior point methods The simplex algorithm walks greedily on the corners of a polytope to find the optimal solution to the linear programming problem. As a result, the answer is always a corner of the polytope. Interior point methods walk the inside of the polytope. As a result, when a whole plane of the polytope is optimal (if the objective function is exactly parallel to the plane), we can get a solution in the middle of this plane.

Suppose that we want to find a corner of the polytope instead. For example if we want to do maximum matching by reducing it to linear programming, we don't want to get an answer consisting of "the matching contains 0.34% of the edge XY and 0.89% of the edge AB and ...". We want to get an answer with 0's and 1's (which simplex would give us since all corners consist of 0's and 1's). Is there a way to do this with an interior point method that guarantees to find exact corner solutions in polynomial time? (for example perhaps we can modify the objective function to favor corners)

You might want to read the paper:

  Sanjay Mehrotra, On finding a vertex solution using interior point methods, Linear Algebra and its Applications, Volume 152, 1 July 1991, Pages 233-253, ISSN 0024-3795, 10.1016/0024-3795(91)90277-4. sciencedirect article link


Why not do these checks on the number of clauses in 3-SAT? I've been writing a 3-SAT solver for fun and comparing its performance against the solver pycosat. My solver vastly outperforms pycosat in two special cases, where I solve by doing simple, obvious checks, which pycosat doesn't seem to do (based on the time it takes to solve these cases).

I presumed that these checks would be known and commonly incorporated into solvers. Is that the case? Why would a solver not bother doing them?

The checks are based on the following:

Let $\phi$ be a CNF with $n$ variables and $m$ disjunctions, where each disjunction has exactly 3 distinct variables and no two disjunctions have the same literals.

1) If $m < 8$, then $\phi$ is satisfiable.

2) If $m > 7* \binom{n}{3}$, then $\phi$ is unsatisfiable. ($\binom{n}{k}$ is the binomial coefficient.)

The proof is simple but tedious. I can provide it if needed.

There's no real reason not to do your checks given that they are computationally tractable, but there's very little point in doing them either.  Your checks make determining the satisfiability of easy random 3-SAT instances easier.  SAT solver authors are interested in algorithms that make hard SAT instances easier.

For random 3-SAT, the hardest instances are known to be near the phase transition point where instances on one side are almost always satisfiable and instances on the other are almost always unsatisfiable.  That transition point has been observed empirically to be when the ratio of the number of clauses and the number of variables is around 4.26.  Your checks would never be helpful with such instances.


Finding the two largest of five small integers as quickly as possible I use a variation of a 5-cross median filter on image data
on a small embedded system, i.e.

    x
  x x x
    x

The algorithm is really simple: read 5 unsigned integer values, get the highest 2, do some calculations on those and write back the unsigned integer result.

What is nice is that the 5 integer input values are all in the range of 0-20. The calculated integer value are also in the 0-20 range!

Through profiling, I have figured out that getting the largest two numbers is the bottleneck so I want to speed this part up. What is the fastest way to perform this selection?

The current algorithm uses a 32 bit mask with 1 in the position given by the 5 numbers and a HW-supported CLZ function.
I should say that the CPU is a proprietary one, not available outside of my company. My compiler is GCC but tailor made for this CPU.

I have tried to figure out if I can use a lookup-table but I have failed to generate a key that I can use.

I have $21^5$ combinations for the input but order isn't important, i.e. [5,0,0,0,5] is the same as [5,5,0,0,0].

It happens that the hash-function below produces a perfect hash without collisions!

def hash(x):
    h = 0
    for i in x:
        h = 33*h+i
    return h

But the hash is huge and there is simply not enough memory to use that.

Is there a better algorithm that I can use?
Is it possible to solve my problem using a lookup-table and generating a key?

In my other answer I suggest that
conditional jumps might be the main impediment to efficiency. As a consequence,
sorting networks come to mind:
they are data agnostic, that is the same sequence of comparisons is executed no
matter the input, with only the swaps being conditional.

Of course, sorting may be too much work; we only need the biggest two numbers.
Lucky for us, selection networks have also been studied. Knuth tells us
that finding the two smallest numbers out of five² can be done with
$\hat{U}_2(5) = 6$ comparisons [1, 5.3.4 ex 19] (and at most as many swaps).

The network he gives in the solutions (rewritten to zero-based arrays) is

$\qquad\displaystyle [0:4]\,[1:4]\,[0:3]\,[1:3]\,[0:2]\,[1:2]$

which implements -- after adjusting the direction of the comparisons -- in
pseudocode as

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Now, naive implementations still have conditional jumps (across the swap code).
Depending on your machine you can cirumvent them with conditional instructions,
though. x86 seems to be its usual mudpit self; ARM looks more promising since
apparently most operations are conditional
in themselves. If I understand the instructions
correctly, the first swap translates to this, assuming our array values have been
loaded to registers R0 through R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

Yes, yes, of course you can use XOR swapping
     with EOR.

I just hope your processor has this, or something similar. Of course, if you build the thing for this purpose, maybe you can get the network hard-wired on there?

This is probably (provably?) the best you can do in the classical realm, i.e.
without making use of the limited domain and performing wicked intra-word magicks.

Sorting and Searching
by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)
Note that this leaves the two selected elements unordered. Ordering them requires an extra comparison, that is $\hat{W}_2(5) = 7$ many in total [1, p234 Table 1].


How many bits needed to describe completely random function? I read this sentence on mit.ocw and don't understand why this completely random function would need $|U|\log n$ bits to be described?

  Unfortunately, if we choose a hash function h that happens to be a
  completely random function from U to [n], we would actually need $|U|\log n$ bits to describe it.

The word random is misplaced here, the question is how many bits are required to describe a function from $U$ to $\{1,...,n\}$. The connection to randomness here is simply the fact that you need to deal with an arbitrary function (since you pick one uniformly at random). Thus, you cannot rely on any structure of the function, which could allow a more compact description (e.g. a constant function would require only $\log n$ bits to describe).

One way to look at it, is saying that you need to specify the output for every possible input. Since there are $|U|$ possible inputs, and specifying an element in the range requires $\log n$ bits, this results in a $|U|\log n$ length description. You can also use the fact that there are $n^{|U|}$ different functions from $U$ to $[n]$, so you need $\log n^{|U|}=|U|\log n$ bits to index an element in this set.


How to identify named points by coordinates? The problem:
This is a reduced version of a problem I currently have. I have a list of edges as input. This list contains the names of 2 nodes (the edge connects these 2 nodes) and 2 x 2D coordinates (which is the start and the end of the edge). The nodes can be in an arbitrary order, and the whole list can contain duplicates. The wanted output is a list of each node (identified by name) and it's coordinates.

It can be assumed that the input uniquely identifies each point correctly, otherwise the algorithm can cancel with an error.

here is an example:

The input could be (AA,BB,CC are names of nodes)

AA,BB = (1,1),(2,2)
BB,AA = (2,2),(1,1)
BB,AA = (1,1),(2,2)
AA,CC = (1,1),(3,3)

The output would be :

AA = (1,1)
BB = (2,2)
CC = (3,3)

So essentially form a list of undirected edges, I want to fetch the list of named nodes.

My current solution:
is a naive implementation, where I'm simple iterating (or recursing) through the input, I note 2 possible coordinates for each named node. If a coordinate verifies with another line of input I mark it as 'confirmed' and add it to the final result (and remove it from the set of 'possible' coordinates).

What I want:
is a better solution, because this feels like a standard problem of graph theory. Can this be reduced to an existing problem, with an existing algorithm? I guess I'm overthinking this, and I all I need to do is putting the input in some kind of mathematical struct and the the solution is trivial or automatically there. Any ideas? Can this be reduced to a standard-problem? Is it possibly NP hard (so my naive implementation is the best I will find)? I'm also struggling to find a unique identifier, for a better solution. Is a name of a point uniquely identifying the 2D coordinate, or is the 2D coordinate uniquely identifying the named node? I have a bit of a blockage in my thinking and can't find a better way than my current one. I'm implementing it in Python, but if anyone has an idea (or hints) in plain words or pseudocode I'm happy to read them.

Thanks

I will assume the graph is connected (otherwise, break it down into connected components and recurse on each connected component).

Pick a single vertex.  Find an edge that uses that vertex.  That gives you two possibilities for the coordinates of that vertex.  Try one of them, propagate its implications, and see if it leads to a contradiction or a consistent assignment of coordinates to vertices. If it leads to a contradiction, try the other possibility.  If either leads to a consistent assignment, output that assignment.  If both lead to a contradiction, abort with an error.

So all that remains is to describe how to propagate the implications.  Suppose we have picked node AA and we assign it to location (2,2).  Then we find all edges between node AA and some other unassigned node.  This will let us assign a location to other other nodes, or abort with a cancellation.  For instance, once we assign AA to location (2,2), the edge AA,BB = (1,1),(2,2) causes us to assign BB to location (1,1) (which might trigger more implications) and the edge AA,CC = (1,1),(3,3) causes a contradiction (since AA can't be in location (2,2)).  Once this process completes, we check whether the resulting assignment is consistent with all of the edges; if not, we've found a contradiction.  Propagation can be done with any standard graph traversal algorithm, like DFS or BFS.

The running time to propagate the implications is linear in the size of the graph.  We only have to do that twice (once for each assumption about the location of the starting vertex), so the total running time is linear, i.e., $O(|V|+|E|)$.


How to get the calculate the binary logarithm of a fixed-point number with 18 decimals? Suppose that:

You're using a programming language that doesn't support fixed-point or floating-point numbers.
The said programming language rounds down divisions, e.g. 12 / 5 = 2.
You're adding 18 trailing decimals to represent fixed-point numbers in your algorithm. for instance, you'd represent 0.5 as 500000000000000000, equivalent to 5e17 in scientific notation.

Now, say you want to calculate the integer part of the binary logarithm of a number x that adheres to the format above.
If x is greater than or equal to 1e18, then the calculation is easy: you just divide x by 1e18, and calculate the most significant bit of the rounded down result. For example, 4e18 / 1e18 is 4, of which the msb is 2. The integer part is thus 2.
But what if x is between 0 and 1e18 (both exclusive)? For example, 1e17? The binary logarithm of a number between 0 and 1 is negative ..

I figured it out, eventually, by making the following observations:

$\log_2{(x)} = -log_2{(\frac{1}{x})}$
To accurately calculate $\frac{1}{x}$, multiply $1e18$ by itself then divide by $x$.

My implementation looks something like this (written in Solidity):
pragma solidity ^0.8.0;

function log2(uint256 x) internal pure returns (int256 result) {
    require(x > 0);
    unchecked {
        // This works because log2(x) = -log2(1/x).
        int256 sign;
        if (x >= 1e18) {
            sign = 1;
        } else {
            sign = -1;
            unchecked {
                x = 1e36 / x;
            }
        }

        // Calculate the integer part of the logarithm and add it to the result and finally calculate y = x * 2^(-n).
        uint256 n = mostSignificantBit(uint256(x / 1e18));

        // The integer part of the logarithm as a signed 59.18-decimal fixed-point number. The operation can't overflow
        // beacuse n is maximum 255, SCALE is 1e18 and sign is either 1 or -1.
        result = int256(n) * 1e18;

        // This is y = x * 2^(-n).
        int256 y = int256(x) >> n;

        // If y = 1, the fractional part is zero.
        if (y == 1e18) {
            return result * sign;
        }

        // Calculate the fractional part via the iterative approximation.
        // The "delta >>= 1" part is equivalent to "delta /= 2", but shifting bits is faster.
        for (int256 delta = 5e17; delta > 0; delta >>= 1) {
            y = (y * y) / 1e18;

            // Is y^2 > 2 and so in the range [2,4)?
            if (y >= 2 * 1e18) {
                // Add the 2^(-m) factor to the logarithm.
                result += delta;

                // Corresponds to z/2 on Wikipedia.
                y >>= 1;
            }
        }
        result *= sign;
    }
}

Where mostSignificantBit is a function that calculates the most significant bit of a number that can go as high as $2^{256} -1 $.


Find a quarrel-free seating order with a greedy algorithm I'm revising for an Algorithms exam and looking at a sample question it says :

A group of n teenagers $t_1, \dots, t_n$ are to sit in a single row of n chairs watching a particulary boring comedy movie. Some teenagers quarrel with each other all the time. The Problem is to devise a seating arrangement for the group in such a way that teenagers sat next to each other do not quarrel.
Propose a solution to this problem using the Greedy approach. Estimate the complexity of the resulting algorithm.

In lectures for greedy problems we've only covered Knapsack Problems so Next Fit/Best Fit for Bin Packing. I can't seem to understand how these methods have any relevance to coming up with a solution for the question.
Obviously I don't expect anyone to answer this, since I've not even made an attempt. But in honesty I don't know where to start. If you guys could give me some sort of hints or just general advice because I'm pretty stranded at the minute.

I don't know if i understood your exercise. But pick a arrangement with n students in n positions is a permutation, so there are n! possible arrangements. So, it's look like a Hamiltonian path problem, where each student is a graph's vertex and there's an edge i,j if the student i can sit next to student j, with no quarrel. If you can find some Hamiltonian path, you have a arrangement. For greedy algorithm you can   propose a heuristic that visit first the vertex with low degree (number of edges incident to the vertex), meaning that the most annoying student will be chosen to sit on the first place of the row.


What is the goal of studying all those NP-complete problems? So i'm currently reading a lot of things about graph NP-complete problems, and it seems that the goal of a lot of researchers is to find new results about their complexity, results like "independent set is 1.593 approximable for graphs which doesn't contains K4 K5 P3 as a minor" (this is probably a wrong result i just invented something which looks like a result we could find in a paper), approximation algorithms, parameterized complexity etc ...
But i'm wondering : what really is the goal to study independent set, vertex cover, hamiltonian circuit etc ... ? Do they have real case application ? Is there any software that uses independent set algorithms ?
Or is it only for the theory ? To discover something new in the P vs NP problems ?
To sum up : are NP-complete problems (and i'm particularly interested in NP-complete graph problems) useful in the reality ?
PS : sorry if the title may seem offensive, it is not, i know a lot of searchers study things which does not have much applications in reality, i want to know if it is the case for np-complete problems

No one are offended by that question, and it's an important question to
ask.
When working in graph theory, we don't believe that proving hardness
results for independent set on $\{K_4, K_5, P_3\}$-minor-free graphs are
"important".  However, it is interesting to see why a certain
forbidden minor puts a problem from being, e.g. polynomial time
solvable, to NP-complete.  It is then important that that is the
focus.
Here is an interesting problem:

Does edge deletion to claw-free graphs admit a polynomial kernel?

Why is it interesting?  Because we know almost everything else about
kernels and edge deletion to $H$-free graphs.  This one is interesting
because it is notoriously hard.  And hopefully, once this is solved, we
will understand more about the interplay between $H$-free graphs, edge
deletion, and polynomial kernels.
But I want to also mention that, yes, there are indeed applications that use algorithms for independent set, vertex cover, travelling salesman, etc.   See for example Dependency hell is NP-complete.

Fast forward to industry.  After quitting academia and joining
industry as a developer, I have more than once been able to tell people
that what they are working on is NP-complete, and to provide insight
into a problem that I got from studying these problems in a theoretic
setting.
I have written and published my share of "unusable" algorithms, but it's
not expected that people can take algorithms and plug-and-play them into
their system.  What they can take is the insight we provide in
structures, heuristics, as well as hardness.  Sometimes a problem is
only hard on graphs that have large grids as minors, and if you suddenly
see that your data is "tree-like", then you might have some tricks to
share with your future industry-colleagues.


$A, B$ --- enumerable sets, is $A \times B$ enumerable? $A, B$ – enumerable sets, is $A \times B$ enumerable?
I have some thoughts, that maybe it can be done using something like the proof of countability of $\mathbb{N} \times \mathbb{N}$, but I don't know how to prove this more proper.

There are many ways you could solve this, so here's a hint. $A$ and $B$ are enumerable, which means that injections

$$ f : A \rightarrow \mathbb{N} \quad \text{and} \quad g : B \rightarrow \mathbb{N}$$

exist. Now, given a tuple $t \in A \times B$, how can you map it to a unique element in $\mathbb{N} \times \mathbb{N}$ using $f$ and $g$?

   Since $f$ and $g$ are injections, their product must also be an injection (prove this). So the function $h : A \times B \rightarrow \mathbb{N} \times \mathbb{N}$, defined as $(a, b) \mapsto (f(a), g(b))$. Is an bijection on a subset of $\mathbb{N} \times \mathbb{N}$ (because it is an injection on $\mathbb{N} \times \mathbb{N}$).

A subset of an enumerable set is always countable, so this concludes the proof.


Recursion call inside a for loop time I'm analyzing a piece of code that has a recursive call inside a for loop such as:

def fun(n):
    for i in range(0, 256):
         if ( n > 0):
             fun(n-8)

(I only included a general piece of code not the actual version)

It is my understanding that a recursive call gets assigned T(n) = T(n-8) but what happens when it is nested inside a for loop?

As there is a loop over $F(n-8)$, so we will have 256 times $F(n-8)$. Hence, time complexity would be:
$$T(n) = 256\times T(n-8) = 256\times(256\times T(n-16)) = \Theta(256^\frac{n}{8})$$.

As mentioned in comment $256 = 2^8$, we will have $T(n) = \Theta(2^n)$.


Is it possible to create a NFA that accepts only n*"a" or n*"b" inputs? I'd like to create a NFA that accepts only inputs like "aaaaa";"a";"bb";"bbb", but not like "aab";"aabaa".
Is the even possible? As far as I understand NFA is processing a superspositon of all sub-inputs. So then, if given automaton accepts "a" or "b", it would always accept "ab" just like it accepts "b". Is there a way around, am I missing something?

Would it work? After reading n*'a' and then 'b' the automaton leaves accepting state but in the same time it is entering another accepting state.

Yes it is.
Considering regular expression and NFA have the same power (source here), your question amounts to asking if there is such a regular expression.
So the regular expression would be /a*|b*/.
As for a NFA doing such a thing, here is an article describing how to go from regex to NFA.
In the article about regex to NFA, there is a section at the end explaining about metacharacter \$ for end of string. An actual regex for your problem would then be /^(a*|b*)$/ .


Is the system of measuring length in the US Turing complete? The author here writes:

  Little known fact, the system of measuring length in the US is Turing complete

My question is: Is the system of measuring length in the US Turing complete?

The post you're referring to is a joke: the US (and similar British Imperial) measurement systems are not Turing complete and the claim is an example of hyperbole.

A key feature that's necessary for a system to be Turing complete is that the system must include computations that do not terminate ("infinite loops").  Although it's not clear exactly what computations can be modeled by unit conversions (or what that even means!), any unit conversion within the diagram takes a finite number of steps.


Have block edit distances been computed on large code bases? There is an enormous mass of source code in this world, and I think it's safe to say that most of this source code was once copied from elsewhere, then modified. There is a decent chance of the (small, incremental) modifications having been made traceable in some kind of version control repository, but the (larger-scale) copying of source code usually isn't traceable in this way.

It would be nice to make it easy to detect it anyway.

As far as I can see, the reason it isn't is ultimately that our paradigm for looking at changes is modelled after diff: we compute changes as a collection of per-character insertions and deletions, disregarding the possibility of using block edit operations such as copy, cut, and paste.
This doesn't match actual code development practices, in which blockwise copies, cuts and pastes are all too common.  Allowing these, we can take two arbitrary code bases and 'reconstruct' an 'ideal' minimal distance between them, measured in terms of change operations that developers are actually likely to use, which includes cut, copy, and paste.  This would allow us to reconstruct an 'ideal' change history in code bases in circumstances where the actual change history is missing (e.g. when no version control system has been used, or when code has been copied verbatim from one code base into another).

There seems to be a sound computational reason that this isn't routinely provided already: it seems too expensive. Even with just per-character insertions and deletions, computing the minimal difference between two arbitrary strings already takes quadratic time in the size of the difference found; diff doesn't evcen attempt to do this perfectly.  If we also allow blockwise copies and/or moves at a constant cost, the problem of determining the minimal edit distance between two arbitrary strings becomes NP-complete. However, it has been argued that realistic constraints can be imposed that make the problem quadratic again. (I am linking to this paper, but I haven't actually read it yet.)

My question to you: have you ever seen an application of block edit distance computations (that is, including substring moves and/or deletions and/or copies) in a piece of software built to compare the similarity of two pieces of software? Does there exist a common, widely available tool that supports this? (A diff on steroids.) Or has there been a project to use such a technique to detect copy-and-paste operations within a large base of source code?

(The reason I'm asking is that source code does not at all consist of arbitrary strings. These problems are NP-hard for arbitrary strings, but they may well turn out be in P for source code found in practice.)

I do not know about publicly available tools to do it, but I did fair amount of diff related algorithms and one tool to check similarities between codes.

There are some basics to start with:

0) diff operates well on similar changed texts and falls into worst case when they are different.

1) Tools to check similarities on codes that I have seen, used and written were all operating on AST trees, disregarding formatting, variable and function names. Even though when codes exhibited packaging into functions it gave really hard time. So after that technique like SSA and strip code of functions was applied.

2) Languages that allow same thing to be done in several ways are to be treated as same expressions.

3) Sometimes code is translated into another language. So perfectly working transpilers should exist in first place. Every transpiler I have used was not fully functional, maybe I am not aware of new achievements, but as I checked there is no tool "write in any language you want and get source in any other".

4) There are situations like using well known algorithms, or copying from one book. Also there is probability that two codes are the same, or almost the same (same AST, same language), and are not copied.

5) There might be a lot of false positives, and even if we overcome above problems, what would be the outcome of such search?

There is no tool to produce comparable and working solution to JS. And nowadays many projects are getting JS spin off. Also with tools like emscripten (to operate on LLVM code) makes it virtually impossible to keep track of code.

If you take Levenshtein distance as a measure, you should probably consider above points. This seems convincing to me that it is really not sufficient to start tracking such changes in open source code, as there are tons of them.


Isn't an improper subset of edges of a cyclic graph, cyclic and thus not a minimum spanning tree? This is the formal definition of a minimum spanning tree taken from Algorithms by Dasgupta, Papadimitrious and U. Vazirani.

Input: An undirected graph $G = (V,E)$; edge weights $w_e$.
Output: A tree $T = (V,E')$, with $E' \subseteq E$, that minimizes
$$ \operatorname{weight}(T) =  \sum_{e \in E'} w_e. $$

My confusion arises from the fact that the edges in the minimum spanning tree are an improper subset of the edges in the original graph. If the graph were cyclic, then we would have removed the cycles in the minimum spanning tree and would have had fewer edges. How is it that we have an improper subset (containing all the edges of the original graph)?
This is the example given right before the definition and the graph clearly contains cycle edges.

It looks like you misread or misunderstand the standard set notation "$E'\subseteq E$".
That notation just means $E'$ is a subset of $E$, i.e. every element of $E'$ is also an element of $E$.

We do not speak of "an improper subset", most of the time if not ever.
Why?
Suppose $A$ and $B$ are two sets. $A$ is a subset of $B$ iff every element of $A$ is also an element of $B$. If, furthermore, $A$ is not $B$, then we say $A$ is a proper (or strict) subset of $B$.
If we want to mention "an improper subset" of $B$, what would it mean?

It should mean $B$ itself. That is how I would understand that phrase upon first reading. Then, why do we want to say "an improper subset of $B$", a pretty long phrase, when we can just say "$B$", which is concise? The phrase "an improper subset" seems implying there are more-than-one such subsets for a given set, which is simply wrong.

It could just means "subset" when it is used in distinction to "proper subset" (which sounds unnatural to me, but maybe that is only me). Again, why not just use "subset", which is concise?


What simple arguments and insights can I observe that running both BFS and DFS can be achieved in O(|V| + |E|)? BFS and DFS can be achieved in O(|V| + |E|). I understand the proof but it seems a bit lengthy.

Can I argue O(|V| + |E|) in a very simply way? e.g. checking each edge at most once?
Also what does O(|V| + |E|) imply?

I know Dijstrka algorithm and many other algorithm is somewhat like BFS. Does it imply automatically they can be run in |V| + |E| is the lower bound?

Intuitively, what a time upper bound of $O(|V| + |E|)$ means is that you spend $O(1)$ time per each vertex and each edge. Taking as an example DFS, there is one recursive call per edge, and the procedure itself runs once per vertex. You can turn this into a full-fledged argument that proves the upper bound.

An upper bound of $O(|V| + |E|)$ is optimal for most graph problems – those that potentially require examining all vertices and all edges. What such an upper bound tells you is that your problem can be solved in the minimal possible time; an $O(|V| + |E|)$ algorithm is an asymptotically optimal algorithm.


Using AI / Machine learning to find the most time and space efficient solutions to an algorithm As programmers, we are always trying to find the most efficient space and time complexity solutions to algorithms.

Is it forseeable in the future that we have languages or techniques such as AI/machine learning to automatically find such optimum solutions to any generic algorithm?

No.

With all the hype about AI/Machine learning, sometimes people forget that there are known limitations to computers, which can be proven, so it doesn't matter how fast your computer is, how sophisticated is your neural net, you just cant do it.

I'll try to address your specific question. First, you have to define exactly what is the task that you expect your AI algorithm to solve. Suppose your input is a description of the problem, given in the form of an encoding of a Turing machine $\langle M\rangle$ which solves it, or as a valid code in your favorite programming language. Now, say we want to output an equivalent program, with optimal (asymptotic) time complexity.

The decision version corresponding to your problem is, given a program in your language, decide if there exists an equivalent program with better (asymptotic) time complexity.

This is not possible for any computer, or in more technical terms, this language is undecidable. We can reduce the halting problem to the above in the following way:

Given a pair $(\langle M \rangle,w)$, Let $M_w$ be the machine which, given input $x$, runs $M$ on $w$ for $|x|$ steps. If $M$ halted then $M_w$ accepts iff $x$ is a palindrome. If $M$ didn't halt within $|x|$ steps, $M_w$ rejects. We can build $M_w$ such that $M_w$ runs in $O(n^2)$ time.

If $M$ halts on $w$ after $n$ steps, then $L(M_w)=\left\{x \big| |x|\ge n \land \text{x is a palindrome}\right\}$, otherwise $L(M_w)=\emptyset$. Since we know that checking whether a string is a palindrome requires $\Omega(n^2)$ time on a single tape Turing machine, then if $M$ halts on $w$, $M_w$ decides $L(M_w)$ with optimal time complexity. Otherwise it doesn't (the empty language can be decided in constant time, just output "no" without even reading the input). This means that $M$ halts on $w$ iff $M_w$ has optimal time complexity.

This shows that for general programs, this task is hopeless. Perhaps, for a specific subset of programs, you can decide optimality, and this doesn't necessarily mean using some fancy AI algorithm,  see Program optimization.


Minimal DFA accepting strings whose length is divisible by $x$ or $y$ Consider the language of all strings whose length is divisible by either $x$ or $y$, where $x,y \geq 1$.
After trying various values of $x$ and $y$, I noticed made the following observation:

If one of $x,y$ is a multiple of the other, then the minimal DFA contains $\min(x,y)$ states, and otherwise it contains $\operatorname{lcm}(x,y)$ states.

Is this true for all values of $x$ and $y$?
Also, what happens if we replace the condition "divisible by either $x$ or $y$" with the condition "divisible by both $x$ and $y$"?

Let $\operatorname{gcd}(x,y) = g$, and suppose that $x,y > g$. If there is a minimal DFA for the language with $n$ states, then according to the pumping lemma, there is $1 \leq m \leq n$ such that the following holds: $\ell \geq n$ is a length of words in the language iff $\ell + m$ is a length of words in the language, that is:

For all $\ell \geq n$: $(x \mid \ell \text{ or } y \mid \ell)$ iff $(x \mid \ell+m \text{ or } y \mid \ell+m)$.

Let $\ell \geq n$ be some multiple of $x$. Then $x \mid \ell$, hence either $x \mid \ell+m$ or $y \mid \ell+m$, which implies that $g \mid \ell$ and $g \mid \ell+m$, and so $g \mid m$.
Suppose that $x \nmid m$. Let $\ell \geq n$ be such that $\ell \equiv -m \pmod{x}$ and $\ell \equiv g \pmod{y}$; there exists such $\ell$ since $g \mid m$. Then $x\nmid \ell$, $y\nmid\ell$ (since $y > g$), but $x\mid \ell+m$, and we reach a contradiction. Therefore $x \mid m$. Similarly, $y \mid m$. Therefore $\operatorname{lcm}(x,y) \mid m$, implying that $n \geq m \geq \operatorname{lcm}(x,y)$ (since $m > 0$).
Conversely, it is easy to construct a DFA for the language with $\operatorname{lcm}(x,y)$ states, showing that this is the number of states in a minimal DFA, assuming that $x,y > g$.
If $x = g$ or $y = g$, then the language consists of all words whose lengths are a multiple of $g = \min(x,y)$, and so the minimal DFA contains $\min(x,y)$ states.
Finally, if we replace or with and in the definition, then we get the language of all words whose lengths are a multiple of $\operatorname{lcm}(x,y)$, whose minimal DFA contains $\operatorname{lcm}(x,y)$ states.


Convex Hull algorithm - why it can't be computed using only comparisons Say I want to compute a covnex hull of given points on the plane. I would like to write an algorithm, that only compares the points and doesn't do any arithmetic operations. Wikipedia states, that:

  The standard $\Omega(n \log n)$ lower bound for sorting is proven in the decision tree model of computing, in which only numerical comparisons but not arithmetic operations can be performed; however, in this model, convex hulls cannot be computed at all.

Why is it so? I can't find any justification for it anywhere, I know it to be intuitively true, but how come it's a necessity?

For a slightly more general way of looking at this, what you want to do is equivalent to saying you can reconstruct the convex hull from the orderings induced by projections onto the coordinate axes.

To see you can't do this, just observe that for three points $a$, $b$, and $c$, knowing that $a < c < b$ in both projections doesn't let you figure out whether $c$ is above, below, or on the segment $ab$.  (Start with $c$ on the segment and then perturb it up or down by a small amount.)

This indicates that you'll need the "left turn" and "right turn" predicates.


A model of computation vs an abstract machine Wikipedia says

  A model of computation is a formal description of a particular type of computational process. The description often takes the form
  of an abstract machine that is meant to perform the task at
  hand.

What other forms can a model of computation take than an abstract
machine?
What are the difference and relation between a model of computation
and an abstract machine? I thought that they were the same, until I saw the the quote above.

An abstract machine typically defines instructions with opcodes and operands. A Warren abstract machine, a java virtual machine, a Turing machine.  A programming model defines operations at a higher level, and could be independently supported by a number of different machines.  For example the actor programming  model says that an actor can send a message, create a new actor, and define internal state for its next message to be handled.  This is said without defining specific opcodes and operands, though one could envision an abstract machine that supported that.


Extending the implementation of a Queue using a circular array I'm doing some exam (Java-based algorithmics) revision and have been given the question:

  Describe how you might extend your implementation [of a queue using a circular array] to support the expansion of the Queue to allow it to store more data items.

The Queue started off implemented as an array with a fixed maximum size. I've got two current answers to this, but I'm not sure either are correct:

Implement the Queue using the Java Vector class as the underlying array structure. The Vector class is similar to arrays, but a Vector can be resized at any time whereas an array's size is fixed when the array is created.
Copy all entries into a larger array.

Is there anything obvious I'm missing?

Using the Vector class is certainly a possibility, as a practical matter. Other solutions will amount to implementing functionality that is similar to what the Vector class provides (possibly in a way that is more efficient given that the data structure stores a queue).

Some languages offer inherently resizable arrays. For example, in C, to allocate an array, you allocate a block of memory of the required size with the malloc function, and you can later resize this block without affecting the data in the remaining part (when shrinking) or the initial part (when extending). Under the hood, realloc may allocate a new region (at a different address in memory) then copy the data, but it'll try to extend or shrink the region in place for efficiency, in which case no copying is necessary.

Most high-level languages do not support resizing existing memory regions. This is because resizing might change the address of the object, which requires modifying all references to that object — C gets away with it by shifting the burden of updating references to the programmer. If you want a resizable array, you can achieve that manually: access the array through an indirect reference, and when you want to resize the array, allocate a new array, copy the data and assign the indirect reference to the new array.

As a simple optimization, if the array size shrinks by a small amount (say, because you take an element from the queue), do not shrink the array: you'll waste a bit of space, but avoid incessantly reallocating the array and moving the data around if successive elements are removed. And if the array size increases by a small amount (say, because you push an element onto the queue), increase the array size by a margin over the requested amount, so that the array will still be good for the next few increases. The Vector class in Java does this: it maintains an elementCount for the array that contains the data; array elements beyond this position are not used.

Asymptotically, you get good behavior by varying the array size exponentially, for example sticking to powers of 2: if you add an element to a 128-element queue, resize the array to 256; if you remove an element from a 65-element queue (in a 128-element array), resize the array down to 64. With array sizes of the form $a^n$, the wasted space is at most $(a-1)$ times the array size. The cost of reallocations, dominated by moving elements when crossing a size boundary is $\Theta(a^n)$. Amortized over a sequence of additions from an empty array or a sequence of removals until the array is empty, the cost of reallocations is $\Theta(a^n/a^n) = \Theta(1)$. In general the amortized cost of reallocations is $O(1)$.

There are other implementations of resizable arrays that avoid reallocation altogether, at the cost of having slower access time to elements. Avoiding reallocations is especially good to avoid long pauses when a reallocation happens and a lot of data needs to be moved around. A simple one is to maintain a list or array of arrays of exponentially increasing size. The element number $2^i + j$ with $j < 2^i$ is stored at position $j$ in array number $i$. No data ever needs to be copied when the array grows or shrinks (except for the bookkeeping data to maintain the collection of array, which grows logarithmically over the total size).


PDA for this context-free grammar I have the following CFG $G$:
$$ \begin{align}
S &\rightarrow aAbb \mid aaBb \\
A &\rightarrow aAbb \mid \epsilon \\
B &\rightarrow aaBb \mid \epsilon \\
\end{align} $$

I have to create a PDA (pushdown automaton) to recognize this language however I am unsure on how to do it. So far I have this(revised based on feedback from user Hendrik Jan) :

I understand that it should accept the last one ($aaaabb$) however it does not for the current version.

From CFG to PDA is a simple construction. Set axiom $S$ as initial pushdown symbol. If the topmost symbol of the stack is nonterminal replace it according to a production of the grammar. If the topmost symbol is a terminal we are forced to read the same symbol from input tape (and pop the symbol). That is called expand-match. See wikipedia. The resulting PDA is single state, acceptance by empty stack.

(added) Your problem is on a special type of grammar, linear context-free. That means in every step of the derivation there is exactly one nonterminal. You can mimic this using a different construction. Basically the nonterminal is the state. All terminal symbols to the left are read, those to the right are pushed, to be read later. For $S\to aaBb$ the PDA goes from state $S$ to state $B$ while reading $aa$ (in usual models that takes two steps) and pushing $b$.

On your construction (it seems of the latter type). Concretely: the grammar generates $a$'s and $b$'s in a two-to-one / one-to-two ratio. In general: in order (for yourself) to see why it doesn't work you have to try to formulate the meaning of the states. How do they relate to things happening in the grammar?


Balance factor changes after local rotations in AVL tree I try to understand balance factors change after local rotations in AVL trees.
Given the rotate_left operation:

  x            y'
 / \          / \
a   y   =>   x'  c
   / \      / \
  b   c    a   b

and $b(x)$, $b(y)$ - balance factors for $x$ and $y$ nodes - I want to find $b(x')$ and $b(y')$.

In my reasoning I will use the Iverson bracket notation, that denotes a number that is 1 if the condition in square brackets is satisfied, and 0 otherwise:
$$
[P]=\begin{cases} 1, \text{ if } P \text{ is true}; \\
              0, \text{ otherwise}.\end{cases} $$

Balance factor for the node $x'$ can be calculated like this:
$$b(x') = h(b) - h(a)$$

where $h(b)$ and $h(a)$ - the heights of sub-trees $a$ and $b$.

Let's substitute $h(b) = h(y) - b(y)[b(y) > 0] - 1$ and $h(a) = h(x) - b(x)[b(x) > 0] - 1$:

$$b(x') = (h(y) - b(y)[b(y) > 0] - 1) - (h(x) - b(x)[b(x) > 0] - 1)$$

Some simplification:

$$b(x') = h(y) - b(y)[b(y) > 0] - h(x) + b(x)[b(x) > 0]$$

Now substitute $h(y) = h(x) + b(x)[b(x) \le 0] - 1 $:

$$b(x') = h(x) + b(x)[b(x) \le 0] - 1 - b(y)[b(y) > 0] - h(x) + b(x)[b(x) > 0]$$

Obviously, $[b(x) \le 0] + [b(x) > 0] = 1$:

$$b(x') = h(x) + b(x) - 1 - b(y)[b(y) > 0] - h(x)$$

Simplify again:

$$b(x') = b(x) - b(y)[b(y) > 0] - 1$$

In the same way I can find balance factor for $y'$. Skipping intermediate steps I get:
$$ b(y') = h(c) - h(x') =\\
     ...\\
     = b(x) + b(y)[b(y) \le 0] - b(x')[b(x') > 0] - 2$$

Somehow I have feeling that this is not the simplest formula for balance factors.

Is there any simpler approach to calculate balance factors, which would always work even if the tree becomes unbalanced?

EDIT:

The simplest formulas I managed to get look like this (see my own answer for details):
$$b(y′)=b(y)+b(x')[b(x')\le0]−1$$
$$b(x′)=b(x)−b(y)[b(y)>0]−1$$

I found the answer myself.
We know that
$$b(x)=b(x')+b(y)[b(y)>0]+1$$
$$b(y′)=b(x)+b(y)[b(y)\le0]−b(x′)[b(x′)>0]−2$$
thus
$$b(y′)=b(x')+b(y)[b(y)>0]+1+b(y)[b(y)\le0]−b(x′)[b(x′)>0]−2$$
where
$$b(x')−b(x′)[b(x′)>0]=b(x')[b(x')\le0].$$
So, the new balance factors will look like this:
$$b(y′)=b(y)+b(x')[b(x')\le0]−1$$
$$b(x′)=b(x)−b(y)[b(y)>0]−1$$


Resolution in First Order Logic i have problem with resolution in first order logic

i have :

C1  :
¬ Loves(x,F(x) ) or Loves ( G(x) , x )

and

C2 :

¬ Animal ( X) or Loves ( jack , x )

can some one help me why the answer ( after Resolve C1,C2 ) is :

¬ Animal(F(jack) ) or Loves ( G(jack) , jack )

because my answer is :

x/ jack

then i will have :

C1 :
¬ Loves ( jack , F(jack ) ) or Loves ( G(jack),jack )

C2 :

¬ Animal ( jack ) or Loves ( jack,jack )

and i cant use resolution with Loves (jack,jack) and ¬ Loves (jack,F(jack))

thank you all !!

If you want to resolve C1 with C2, then the only option is for Loves(jack, x) (in C2) to match ¬Loves(x, F(x)) (in C1), and so as you state, you should substitute x=jack in C1 and x=F(jack) in C2. Upon making these substitutions, C1 and C2 become:

C1[x/jack] = ¬Loves(jack, F(jack)) or Loves(G(jack), jack)
C2[x/F(jack)] = ¬Animal(F(jack)) or Loves(jack, F(jack))

Resolving the two, we get:

¬Animal(F(jack)) or Loves(G(jack), jack)


Closure properties of linear context-free languages Under what operations are linear context-free languages closed? Suppose $L_1, L_2$ are two linear context free languages.  Are there any guarantees about $L_1 \cup L_2$, $L_1 \cap L_2$, $\overline{L_1}$, $L_1 . L_2$, etc.?

For our readers. Linear grammars are close to regular grammars, a single nonterminal at the time, but they may generate letters at both sides $A \to aBb$ with $A,B$ nonterminal, and $a,b$ terminal (or empty). $REG \subset LIN \subset CF$, strict.
Some closure proofs may benefit from another way to define linear languages: as single turn pushdown languages.

Linear languages are closed under union, construction as for context-free grammars $S\to S_1, S\to S_2$. Likewise they are closed under intersection with regular languages.

They are not closed under intersection: $\{ a^n b^n c^m \mid m,n \ge 0 \} \cap \{ a^n b^m c^m \mid m,n \ge 0 \}$.

Hence they cannot be closed under complement, but I would be nice to have a concrete example.

Neither are they closed under concatenation, intuitively because $S\to S_1S_2$ is not a linear structure. Same for Kleene star.

Linear languages have a pumping property which is similar to that of the context-free languages, except that the composition $z = uvwxy$ may additionally be required to have $|uvxy|\le m$, where $m$ is the pumping constant. This is similar to the requirement for regular languages, where pumping may be assumed to be at the beginning. Linear languages also have a linear structure (like finite state computations) but the symbols that are generated first are at both ends of the string. WIth this property it can be easily shown that $K =\{a^nb^n \mid n\ge 1\}^2$ is not linear.

Both regular and context-free are closed under rotation, but linear languages are not: $K$ is the rotation of linear $\{  b^m a^n b^n a^m \mid m,n\ge 1 \}$ (and a suitable regular intersection).

Regular languages are closed under quotient, but linear (and context-free) languages are not. In fact the operation is very powerful: the RE languages are quotients of two linear languages.

On the other hand, they are closed under quotient with regular languages. That follows as they form a full trio (i.e., they are closed under homomorphisms, and inverse morphisms and intersection with regular languages). Consequently/equivalently they are closed under finite state transductions.

Of course, they are closed under reversal.


Is it correct to say L is RE if I can map reduction from LH to L? I seem to be not understanding correctly what reductions means for Languages.

for example, Lets say there is a Language called LM.

I want to see if LM is recursive or not, to do that lets say I find a reduction from L-Halting problem to LM.

and I assume that LM is recursive, so I show that then L-Halting problem is also recursive, which of course is false therefore LM is not recursive.

but can I say that LM is RE because I found a way to reduce LH to LM?
if not how can I show that LM is RE?

Let's clear things a bit, since there are many equivalent/similar definitions that could lead to misunderstandings.

You can show that a language $L$ is recursive by constructing a recursive function $\chi_L$ (or a Turing machine or any other equivalent computation model) that decides it, i.e.
$$\chi_L (x) = \begin{cases} 1 & \quad ; x \in L \\ 0 & \quad ; \text{otw}. \end{cases}$$
notice that $\chi_L$ must be defined for all inputs.
You can show a that language $L$ is not recursive, by finding a "Turing reduction" from a non-recursive language to it. This is probably what what you mean by reduction, and it is defined as follows:

  We say that a language $A$ is Turing-reducible to a language $B$, written $A \le_T B$, if we can construct a recursive function (or Turing machine) that decides $A$ by assumption that there is such function for $B$.

As you see by definition, Turing reduction somehow "transfers recursiveness" from $B$ to $A$.

  For any $A$ and $B$ such that $A \leq_T B$, if $B$ is recursive, then so is $A$.

Hence if we already know that some $A$ is not recursive, then finding a reduction $A \leq_T B$ for any $B$ makes it non-recursive too.
You can show that a language $L$ is RE, by constructiong a recursive function $\varphi_L$ (or Turing machine) that $Dom(\varphi_L) = L$ (or halts on/accepts it), for example
$$\varphi_L(x) = \begin{cases} 1 & \quad ; x \in L \\ \uparrow & \quad ; \text{otw.} \end{cases}$$

where $\uparrow$ means "not defined" (or "does not halt"). There are other definitions of RE-ness, like its namesake "enumerability", which you can easily observe that are equivalent to this one.
But in showing a language $L$ is not RE, Turing reduction does not help, since it does not necessarily transfer RE-ness. For example observe that $\overline{L_{HALT}} \leq_T L_{HALT}$ (indeed any language is Turing-reducible to it's complement and vice versa), but we know that $L_{HALT}$ is RE, while $\overline{L_{HALT}}$ is not.

But there are other kinds of stronger reduction that do transfer RE-ness. One such reduction is called "many-one redicibility":

  We say that a language $A$ is many-one-reducible to a language $B$, written $A \leq_m B$, if there is a total recursive function $f$ such that for any input $x$
  $$x \in A \iff f(x) \in B$$

This is a stronger reduction in the sense that $A \leq_m B$ implies $A \leq_T B$ (and not necessarily vice versa). So, like Turing reduction, it transfers recursiveness. We also have

  For any $A$ and $B$ such that $A \leq_m B$, if $B$ is RE, then so is $A$.

To see how this is true, just take $\varphi_A(x) = \varphi_B(f(x))$.

Hence the correct method to show a language $B$ is not RE, is to find a many-one reduction $A \leq_m B$ for some non-RE language $A$. Notice that the above example does not work here, because $\overline{L_{HALT}} \nleq_m L_{HALT}$.

For further reading, see Computability Theory by S. Barry Cooper Pt. I, Ch. 7.


Data Analysis: Have 70 data parameters, how many different classes of 3 are possible? The order of the classes of three does not matter. Example: 1,2,3 and 3,2,1 would be considered one class. I am trying to do fisher discriminant analysis on a set of data and want to begin reducing the parameters to better help with classification. As of now I cannot tell which parameters are the most pertinent, so looping every combination through and then having MATLAB take out the LDA analysis with the MisIDs on the lower end in my algorithm will help to isolate the parameters. Can someone refresh me on the math behind this/suggest a way to code this in MATLAB?

That probably isn't the most effective way to figure out which parameters (features) are most informative.  Instead, I suggest looking at methods for feature selection or feature ranking.  There are many methods out there; it's a well-studied topic.


Computing the k shortest edge-disjoint paths on a weighted graph Looking for k shortest paths that do not share edges. i.e if the paths were represented as sets of edges, their intersection has to be empty.

We could use Dijkstra to find the 1st "disjoint" (edge unique) shortest path from the origin to all vertices. However, to naively find the 2nd disjoint path, one would need to create $|V|$ versions of the graph, each one with a specific set of set of edges missing, corresponding to a path that was discovered with the original Dijkstra results.

Is there a more computationally efficient method to find the $k$ shortest, edge disjoint paths? Even a heuristic would help me.

Edit:

I think this article posted by Raphael is exactly what I need to $k=2$ but I would like to support a great k if possible, up to 4. One more thing, I don't understand the following instruction:

  Replace each edge of the shortest path (equivalent to two oppositely directed arcs) by a single arc directed towards the source vertex

What does "equivalent to two oppositely directed arcs" mean? What does replacing an edge with a single arc directed towards the source vertex mean?

https://en.wikipedia.org/wiki/Edge_disjoint_shortest_pair_algorithm

Wait, the problem with the above algorithm is that it doesn't lessen the complexity. It is just as efficient as running Dijkstra twice for each pair of vertices. I'm looking for a better way to get the k disjoint shortest paths between each $v_i$ and $v_j$

A comment by D.W. makes a lot of sense (it would do in general but it does in this specific case since there are many different variants of the same problem). Hence, in my response I just refer to a few variants of the same problem (which contain descriptions of various algorithms):

Usually, the term $k$ shortest edge-disjoint paths is plainly interpreted as follows:

  Given a graph $G$ and $k$ pairs of distinct vertices $(s_i, t_i)$, $1 \leq i \leq k$, find whether there exist $k$ pairwise disjoint shortest paths $P_i$, between $s_i$ and $t_i$ for all $1 \leq i \leq k$.

And this is taken from the paper you pointed to: Tali Eilam-Tzoreff. The disjoint shortest paths problem. Discrete Applied Mathematics. Volume 85, Issue 2, pp 113--138. 1998.

This problem is known to be NP-hard for arbitrary values of $k$ but the authors actually provide a polynomial algorithm for the case of $k=2$ with positive edge-costs.

In this variant, there is no interest in minimizing any particular metric. The best result, to the best of my knowledge, refers to Directed Acyclic Graphs (DAGs) and $k=2$:

Torsten Tholey. Linear time algorithms for two disjoint paths problems on directed acyclic graphs. Theoretical Computer Science, 465:35–48, 2012

However, the oldest formulation I know of this problem actually considers the minimization of a specific metric:

  Given a directed graph G containing $n$ vertices, one of which is a distinguished source $s$, and $m$ edges, each with a non-negative cost, find a pair of edge-disjoint paths from $s$ to $v$ of minimum total cost.

This problem is known to be a special case of minimum-cost network flow, and there is a brilliant, splendid, beautiful and amazing algorithm for solving it with $k=2$: Suurballe's algorithm.

Another variant that has received some attention imposes a limit on the number of edges (and these are known as Length Constraints):

  Given a graph $G$ compute a pair of disjoint paths between nodes $s$ and $t$ of an undirected graph, each having at most $K$ edges.

Again, this problem is known to be NP-complete: Spyros Tragoudas and Yaakov L.Varol. Graph-Theoretic Concepts in Computer Science, volume 1197 of Lecture Notes in Computer Science, chapter Computing disjoint paths with length constraints, pages 357–389. Springer Verlag Heidelberg, 1997.

Approximation algorithms have been developed also for this particular variant. See: Longkun Guo. Frontiers in Algorithmics, volume 8497 of Lecture Notes in Computer Science, chapter Improved LP-rounding Ap- proximations for the k-Disjoint Restricted Shortest Paths Problem, pages 94–104. Springer International Publishing, 2014.

In all these works (but the first two ones), the authors refer to shortest paths but watch out what D.W. is asking in his comment: this is not to find the minimum number $m$ of shortest paths from which a set of $k$ shortest paths could be extracted such that they do not share any edge. In general, the computation of these $k$ shortest paths refer to an additional metric. For example, Tragoudas and Varol consider the minimization of the maximum length and Guo introduces the minimization of an additional parameter, $delay$.

Summarizing, there are many variants of the same problem, Suurballe's minimizes the sum of the cost of the pair of paths, others consider the minimization of the longest path (Tragoudas and Varol), and this is known as a min-max version but also max-min versions exist and this is just in case a metric is used. If not, it depends whether you impose limits or not on the length of the paths and other cases. All of them, however, are known to be exponentially hard.

I would like to end just by pointing out that I am not aware of any generalization of A$^*$-like search algorithms that deal with this problem. I think that can be definitely an interesting line of research.

Hope this helps,


How to generate a grammer from this language? I'm trying to generate a grammar from this language:

L={a^i b^j c^k d^l :  i+j=k+l}

to be clear its a in the power of i and b in the power of j... and so on, so that i+j will equal k+l,
I would love an explanation how to get to the solution as well, thank you!

Start with $i+j=k+\ell$. If $i\ge \ell$, say $=\ell+m$, then also $k=j+m$ and we can write strings in the form $a^\ell a^m b^j c^j c^m d^\ell$. Those can be generated by a grammar, you can use the basic toolbox.

Similarly when $i\le \ell$.