What is the name for polynomially solvable optimisation problems? An optimisation problem that allows to solve a NPC decision problem through a polynomial reduction is called NP-hard. For these optimisation problems no polynomial algorithm is known.

Symmetrically, is there a standard name for all those optimisation problems for which a polynomial algorithm is known?

An optimization problem is an example of a function problem: i.e., one where the task is to map some input to some output.  The class of function problems solvable in polynomial time is FP. See, for example, the Complexity Zoo.

(Note that there is a class OptP but that's not the polynomial-time optimization problems. Perhaps confusingly, it's the optimization analogue of NP: it's the class of functions that can be defined by taking the maximum out the outputs given by accepting paths of a nondeterministic polynomial-time Turing machine.)


Minimal shift operations to sort an array I have been stuck on this sorting problem for a while now:

Given an array of length N find the minimum number of shift operations in order to sort the array. A shift operation is defined as shifting a value in an array to another position. For this problem however, you can only perform this shift operation on the first element in the array.

For example, let's say N = 4 and our array was [1,2,4,3].To sort this array we could perform the following shift operations:

[1,2,4,3] -> [2,4,1,3] -> [4,1,2,3] -> [1,2,3,4]

Thus, we would have to perform a minimum of 3 shift operations.

Any clues on how to approach this problem?

The problem is actually quite simple. When shifting the element at the front, find the last element that is greater than it, and put it after that element.

The number of shifts this takes is $n -k$ where $k$ is the length of the longest increasing suffix of the input.


$25_r = 23_{10}$ solve for the base r first of all this is a homework question and I don't want the solution. I just want a reference to how to solve similar questions like this. I believe it's explained my course textbook, "Computer Organization & Architecture: Themes and Variations" but I currently cannot afford the textbook.

Here's the question:

For each of the following numbers, state the base in use; that is, what are the values of r, s, and t?

a. $25_r = 23_{10}$

b. $1001_s = 19684_{10}$

c. $1011_t = 4931_{10}$

I recognize it's similar to solving an equation. I'm guessing I have to find r, s and t and they will be a specific base that matches the base ten number. I tried searching online for similar questions but I'm not sure what to search for so I have no clue where to start for solving these equations.

Any help would be appreciated.

Hint:

Consider $25_{10}$. The number can be written as $5 \cdot 10^0 + 2 \cdot 10^1$.

How can $25_{r}$ be written?


Computing order statistics $1,2,4,8,\ldots,n$ On an array of $n = 2^k$ numbers, where $k$ is a non-negative integer, the $k = \log n$ order statistics $1, 2, 4, 8,\ldots, 2^k$ can all be determined in a total of $Θ(n)$ time in the worst case.

I think that this statement is wrong because the loop will take $k$ iterations. So, the time should be $Θ(\log(n))$. But, I'm not sure my guess is correct. Could you tell me whether or not my guess is correct?

You can find all of these order statistics in $O(n)$. First, find the maximum (order statistic $2^k$) in time $O(n)$. Then, find the median (order statistic $2^{k-1}$) in time $O(n)$, and remove all larger elements. Find order statistic $2^{k-2}$ in time $O(n/2)$, and remove all larger elements. And so on. The total running time is $$O(n + n/2 + n/4 + \cdots) = O(n).$$


If $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ is $L_1=L_2$ If the same $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ does it imply that $L_1=L_2$?
My intuition says no, but I couldn't find a counterexample.

Using the definition of reduction,
$x\in L_1\iff f(x)\in L \iff x\in L_2$
And thus $L_1=L_2$.


Mathematical function vs Computer program In mathematics , an $n$-ary relation is subset of cross product on $n$ sets took under consideration.

Let us take $A_1,A_2,A_3 \cdots A_n$ be the n sets.

Then relation $R \subseteq A_1\times A_2\times A_3 \times A_n$ .

Here $X$ represents cross product betwen two sets.

If we consider first $k$ sets as input domain and next $n-k$ sets as output range.

Then $R$ is an $k$-ary function that returns $n-k$ multiple outputs. $0 \le k \le n$

As we know function is a well-behaved relation. i.e.., A relation can assign same input to any number of outputs.

In the case of functions (well-beahaved relations)  one input at most maps to one output.

My doubt is whether

Any program written in any program language ultimately a mathematical relation.
Any program written in any program language ultimately a mathematical function.
Some programs written in programming languages cannot be a mathematical relation.
Some programs written in programming languages cannot be a mathematical function.

We know that 2. $\implies$ 1. and 3. $\implies$ 4.

Which of the four arguments above are true for all set of programs in all programming languages?

I am arguing with my colleague that 1.,2. are true independent of programming language and program.

But his argument is that procedural languages like c, c++, pascal etc.., doesn't obey 2. but in case of functional programming languages like Haskell it's true.

So, is  functional programming is syntactical extension of mathematical functions or conceptual extension?

So, the notion of mathematical function is broader than that of a computable function i.e. one you can write in a programming language. There are some mathematical functions which can't be written as programs, such as the function from binary encodings of Turing Machines to booleans representing whether that machine halts on every input.

A Turing machine can be thought of as a function in one of two ways. In case 1, it's a function from its alphabet $\Sigma^*$ to the set ${\top, \bot}$ of boolean values, where the value for an input string is either true if the machine accepts, or false if it does not. This is also what corresponds to a decision problem in formal language theory. The second, more complex way, is where we see a Turing machine as a function from $\Sigma^*$ to $\Sigma^*$, where the value for an input string is whatever value is on the tape at the time of termination.

Note that all other types of Turing machines, such as non-deterministic, multi-tape, etc. can be converted into a deterministic one. (Unless you get something really weird that can do infinite computation in finite time). Also, you can encode most mathematical data in strings, but things get complicated for things such as real numbers or certain infinite sets.

The lambda calculus interpretation is more straight-forward. The lambda calculus is a term rewriting system, where everything is a function. A lambda calculus expression can usually be taken to a normal (irreducible) form through some sequence of $\beta$ and $\eta$ reductions. (Beta-reduction is basically just substituting values for arguments, eta is just writing $\lambda x . f x$ as $f$).

So, every lambda-calculus expression $f$ can be viewed as a function from lambda-calculus expressions to lambda-calculus normal forms, where the value of $f$ with argument $a$ (some other expression) is the normal form of $f a$. Again, most things, like integers, strings, etc, can be encoded in the lambda-calculus, but some things, such as real numbers, are more tricky.

Now's where things get fun. This is all assuming a lambda-calculus or Turing-machine model. What these are very bad at modelling is IO, or some interaction with the outside world.

The Haskell approach to this is to view these as pure functions with some "world" argument, which gets destroyed every time it's updated (a new world state is created).

Likewise, for something like interactive programs, you can stretch our definitions and model the pixels shown on the screen, the files written to disk, the audio waves played, etc. as bits which are part of the program's output.

For example, consider a Python program which prints the current date and time $n$ times for some argument $n$. At first glance, this isn't a function, since you can give it the same $n$ and get a different result. However, if you view the state of the world, namely the current date and time, as an argument to the program, then it always does give the same result for the same input, it's just that input is physically impossible to reproduce because we don't control the passage of time. (You could fudge the computer clock if you wanted, but you can apply the same principal to physical sensors and such).

So, let's look at your four specific questions.

Yes (see 2 below).
Yes, by expressing that program either as a Turing Machine or $\lambda$-calculus expression.
No, see 4.
No, assuming that you model programs with IO as taking the entire state of the world as input and outputting a new state of the world as output. Otherwise, yes.

You have to be careful, because some languages, such as Prolog, let you write something that's closer to a relation than a function. But at the end of the day, if you massage the notation enough you get something that is a function.


Big O notation of max? I'm coding a few set comparisons and noting their big O's using different algorithms and set implementations. I got to one particular function and I decided that it is $O(max(n,m))$ runtime. Is that the proper way to express this?

The expression $O(\max(n,m))$ is meaningful, and we even have $O(n) + O(m) = O(n+m) = O(\max(n,m))$.


Dataflow framework for global analysis: Why meet, then apply? In Chapter 9 of the Dragon Book, the authors describe the dataflow framework for global analysis (described also in these slides).  In this framework, an analysis is defined by a set of transfer functions, along with a meet semilattice.

At each step of the iteration, the algorithm works by maintaining two values for each basic block: an IN set representing information known to be true on input to the basic block, and an OUT set representing information known to be true on output from the basic block.  The algorithm works as follows:

Compute the meet of the OUT sets for all predecessors of the current basic block, and set that value as the IN set to the current basic block.
Compute $f(IN)$ for the current basic block, where $f$ is a transfer function representing the effects of the basic block.  Then set OUT for this block equal to this value.

I am confused about why this algorithm works by taking the meet of all the input blocks before applying the transfer function.  In some cases (non-distributive analyses), this causes a loss of precision.  Wouldn't it make more sense to apply the transfer function to each of the OUT values of the predecessors of the given block, then to meet all of those values together?  Or is this not sound?

Thanks!

It's the classic precision/efficiency tradeoff. You can, in fact, move the meet outside, since $f(x \sqcap y) \sqsubseteq f(x) \sqcap f(y)$. A canonical example of where this makes a difference is in the following constraint-propagation problem:

IF b
  x = 1
ELSE
  x = -1

y = x*x

The Dragon Book's suggestion will compute $(x=1) \sqcap (x=-1)=\top$ before evaluating $x*x$, and will thus not capture that $y$ is a constant. By computing the meet after (twice) evaluating the multiplication, yours will. What you have effectively done is added a small amount of path-sensitivity, for a small price in efficiency. You can continue down this path arbitrarily. Two steps of this analysis may compute $f(f(w\sqcap x) \sqcap f(y\sqcap z))$. Your suggestion would instead compute $f(f(w)\sqcap f(x))  \sqcap f(f(y) \sqcap f(z))$, but you can take this farther and increase the path-sensitivity by computing $f(f(w))\sqcap f(f(x))\sqcap f(f(y)) \sqcap f(f(z))$. The fully path-sensitive MOP (meet-over-paths) solution is undecidable. The Dragon Book's algorithm gives an MFP (maximal fixed point) solution, which safely approximates the MOP. You've simply refined the approximation a bit.


an appropriate data-structure to represent a family of sets (Which supports exactly MAKE-SET(x), UNION(S1,S2), REPORT(S)) I need to represent a family F of sets with some appropriate datastructure. The datastructure needs to support the procedures MAKE-SET(x), DISJOINT-UNION(A,B) and REPORT(A). I dont have a problem with implementing the procedures themselves. Its pretty straightforward if you follow the idea introduced in the chapter on disjoint-set data-structures in Introductions to Algorithms (CLRS for short). My problem is, in this book there is an added procedure Find(x), that, given any member of F, finds the set it belongs to by returning a representative of its set. But i am not meant to implement this procedure. So how exactly am i supposed to represent the family F? I figure we need some way of representing this collection seeing as otherwise what we have is just loose and unassociated sets. What do i do?

if it serves any interest here is the original problem statement:

  We are interested in maintaining a family of sets of  integers F = S1, …, Sk under the following operations:

  •  MAKE-SET(x ): add the set {x} til F

  •   REPORT(Si ): report (ex. print) all elements in Si.

  •   UNION(Si , Sj ): add the set Si ∪ Sj to F . delete Si og Sj from F.

  •  DISJOINT-UNION(S1, S2): Like UNION except it is assumed Si and Sj are
      disjoint, meaning., Si and Sj do no share any elements. If Si and Sj are not
      disjoint the result of the operation is not defined.

  4.1. Come up with a datastructure, which supports MAKE-SET and DISJOINT-UNION in
       O(1) time and REPORT(Si ) in  Θ(|Si|) time.
       Hint: use an appropriate list datastructure

What they mean is: find data structures and algorithms to implement the MAKE-SET, DISJOINT-UNION, and REPORT operations.  That's all that they mean by "represent the family of sets".  The representation is the data structure where the data is stored.


Represent an octree as a binary tree of thrice the depth? In an octree, each node has up to eight child nodes. This can be implemented with eight pointers per node that are set to null pointers if the child is not used. Another implementation uses a byte as bit-mask that stores which children are used and a pointer to the first child. The children are stored consecutively then.

I'm interested in ray-tracing of sparse voxel octrees, so finding the first intersecting leaf with a ray is the main operation on the tree.

To simplify current implementations, I wonder whether it would make sense to represent an octree as binary tree that at each node bisects the space exactly in the middle. The depth layers would alternate between the three possible orientations of the cutting plane. So three levels of the binary tree correspond to one level in an conventional octree.

YZ-plane (root)
XZ-plane
XY-plane
YZ-plane
...

This is similar to the idea of k-d trees, which are binary trees for space partitioning as well. However, they store cutting planes with the nodes to allow for uneven partitioning.

Is there a difference between the octree and a binary tree of three times the depth, or are they equivalent? If there is, why is the octree used more commonly? I haven't found any reference of someone using the explained binary tree for space partitioning. Maybe I'm just missing the correct term for it though.

They're very similar, as you say.  Their asymptotic running time is equivalent; the difference in running time and space usage is at most a small constant.

However, in practice, constants can matter.  In practice, the octree might perform better, due to its better memory locality.  If the depth of the octree is $d$, the depth of your corresponding binary tree will be $3d$.  That means looking up an element requires three times as many pointer indirections in your binary tree.  Pointer indirections are expensive because they typically cause a miss in the cache (they cause random access to memory, which is the worst case for memory hierarchies).  Consequently, in practice, it's possible that the binary tree implementation might be up to three times slower than the octree, due to the increase in cache misses and the poorer memory locality.

Of course, the only way to know for sure is to implement and measure on some benchmarks.  But this is one plausible reason why octrees might be preferable in practice.


Checking whether a number divides any of a set of other numbers Consider a static set $S$ of positive numbers from range $[1..10^9]$. Is there an efficient algorithm to answer queries of the form: "Given a number $d$ is there an element $x \in S$ such that $d | x$".

Simple straightforward check takes $O(|S|)$ time per query and uses $O(|S|)$ memory.
Storing all the divisors for every element of $S$ makes query time $O(1)$ but uses too much memory and precomputation time $O(|S| \times \sqrt{|\max(S)|})$.

I'm interested in an algorithm that uses less memory than second solution (because $|S| \sim 10^6$) and still somewhat faster queries than first solution (number of queries is also $\sim 10^6$).

A silly answer:

Precompute the union of the sets of the factors of all elements in the set.

Then checking if the number is a divisor of any elements in the set is just a single set lookup ($O(1)$). This, however, requires an absurd amount of precomputation (and space to store the resulting set).

The precomputation time can probably be improved - sort the input set, then for each number from 1 to the square root of the largest number in the set, check if any of the numbers from the number squared to the largest number in the set are divisible by the number (add it to the cache if so). It's still absurd, however.


How to test implementation details when there are multiple ways of implementing the algorithm, without reading the code? I want to make sure that the code that the written code is precisely doing what it is expected to do.

For example, if I want to search in an array particularly using linear search, I don't want binary search to pass the test.
Unit test to test the method "search" would pass irrespective of the implementation which is not what I want.
(I understand that binary search won't work if the data is unsorted, but lets say the data is sorted and I still want to make sure that it is a linear search and not the binary. In this case, I know that for sufficiently large input, BS would be way quicker than LS, but I want a generic answer where there might not be considerable difference in performance.)

Is there a way to achieve this?

An idea comes to my mind -
Divide the method in extremely small submethods and make sure that all the submethods are implemented correctly and are used in main method. However this is not desirable, this might not be feasible always.

To find out if it is e.g. doing binary search (or using hashing, or whatever) inside, you have to look at what it is doing. No way around it.

Why would you insist on a particular algorithm? The whole point of modularity (and thus of much of modern programming languages and techniques) is to be able to hide such irrelevant details, and have users depend only on observable behaviour (so you can go back tomorrow and replace a simple, inefficient algorithm by a complex, efficient one, and noone is the wiser).


How can you shuffle in $O(n)$ time if you need $\Omega(n \log n)$ random bits? A shuffling algorithm is supposed to generate a random permutation of a given finite set. So, for a set of size $n$, a shuffling algorithm should return any of the $n!$ permutations of the set uniformly at random.

Also, conceptually, a randomized algorithm can be viewed as a deterministic algorithm of the input and some random seed. Let $S$ be any shuffling algorithm. On input $X$ of size $n$, its output is a function of the randomness it has read. To produce $n!$ different outputs, $S$ must have read at least $\log(n!) = \Omega(n \log n)$ bits of randomness. Hence, any shuffling algorithm must take $\Omega(n \log n)$ time.

On the other hand, the Fisher-Yates shuffle is widely believed to run in $O(n)$ time. Is there something wrong with my argument? If not, why is this belief so widespread?

Your argument appears to be perfectly valid (Fisher-Yates does indeed require $\log (n!)$ bits of randomness), the discrepancy comes in by making different assumptions about the complexity of the random number generation.

You're assuming generating a random number between $0$ and $n$ takes $O(\log n)$.

But, when saying that the Fisher-Yates shuffle is $O(n)$, one assumes generating a random number takes $O(1)$.

An integer index (which is used in the Fisher-Yates shuffle) is generally considered $O(1)$ space (even though it's technically $O(\log n)$) because you can index way more data with a simple 64-bit integer than can currently reasonably fit into the memory of any computer most of us have access to $^{1}$. And the space complexity per number is same as the complexity for the number of random bits that must be generated for that number.

1: To go beyond the number of elements a 64-bit integer can index, we would require $2^{64}$ = $18446744073709551616$ elements, and, assuming 1 bit (which is obviously very small) per element, this requires 2 exabytes.


Proving $f = \Omega (h)$ I need to prove that $n^4+2n = \Omega (n^2)$

Which means I need to point two constants $c_1,c_2$ that from $n_0$:
$$ c_1 \leq \frac{\log(n^4+2n)}{\log(n^2)} \leq c_2$$

Now I know that:
$\lim_{n \to \infty } \frac{\log(n^4+2n)}{\log(n^2)} = 2$ so I can choose $c_1 = 0.5$ and $c_2 = 3$ but how do I do I calculate the $n_0$ that this sentence become true to?

You are working harder than you have to. There are lots of ways to prove this but in general the idea is that you should just find some constants that work, not worry about finding precise small constants.

In this case we don't even need constants! Assuming $n \geq 1$, we have
$$n^4 + 2n \geq n^4$$
always. And
$$n^4 \geq n^2$$
always.

So $n^4 + 2n \geq n^2$, which means $n^4 = \Omega(n^2)$.

...

An easier definition of $\Omega$ is that you need to find a positive constant $C$ so that
$$C(n^4 + 2n) \geq n^2$$.
As mentioned above, $C = 1$ works!

...

Finally, for your example, as in the comment on cstheory, if you want to do it your way, you can always just pick a really high $n_0$ and check that it does indeed work. In general, you can try to solve the equation $C(n^4 + 2n) = n^2$ for $n$, once you have picked a constant $C$ using your limit approach.


Efficiently generating a uniformly random list of unique integers in a range The problem:

To generate a list of size $n$,
Containing unique integers,
Sampled uniformly in the range $\left[0,m\right)$,
In $O(n)$ time, except that:

Assuming $m$ is bounded by some word-size, $\left|m\right|$, the specific time should be $O(n\cdot\left|m\right|)$, as one cannot do better than this.

Apologies if this is a duplicate, if you find one, feel free to point it out.

EDIT: to clarify, the question implies that we are concerned the complixity in terms of bit-operations. (See logarithmic cost model).

Here is a solution in $O(n\log n)$ (with high probability). We consider two cases: $n\log n \geq m$ and $n\log n \leq m$. In the first case, we choose a random permutation of $[0,m)$ and take only the first $n$ elements. This takes time $O(m) = O(n\log n)$. In the second case, we maintain a balanced binary search tree (or equivalent), adding to it random elements from $[0,m)$ one by one, checking for duplicates each time. In expectation we need to try at most $1/\log n = o(1)$ extra times for each element, so the expected running time of this algorithm is $O(n\log n)$. In fact, the running time is $O(n\log n)$ also with high probability.

We can obtain an expected $O(n)$ solution by replacing the balanced binary search tree with a hash table, and changing the cutoff to $n \geq m/2$ versus $n \leq m/2$.


Solve the recurrence $\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $ $$\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $$
I've found so many similar questions but I couldn't understand any of the answers explanations. When I try to draw a recurrence tree, I see that each 'level' has as many operations as nodes (because of only $\ 1 $ operation in each node) so in the first level it has $\ 1 $ node then $\ \sqrt{n} $ nodes then $\ \sqrt{\sqrt{n}} $ nodes and so forth to $\ n^{\frac{1}{2^k}} $ on the lowest level on the tree.
I get the same answer when unrolling it:
$\ T(n) = n^\frac{1}{2} T(n^{\frac{1}{2}}) + 1 = n^{\frac{1}{2}}(n^{\frac{1}{4}} T(n^{\frac{1}{4}}) + 1) + 1= n^{\frac{1}{2}} ( n^{\frac{1}{4}}(n^{\frac{1}{8}} T(n^{\frac{1}{8}}) + 1 ) + 1) + 1 = ...  $
But it is really inconvenient working with this form.
Also tried using substitution as mentioned here and then applying master theorem but with I can't understand how to make the transition back. Also a similar question here but no further explanations in the answers. I would rather use tree recurrence to solve it but substitution and master theorem also good.


How do I describe a DFA? Consider the alphabet E = ${[abc] : a, b, c \in 0,1,...,9)} $  Example [234], [567],
[897] are symbols of the alphabet. For a string $w \in  $  let n(w) denote the number represented by $ w $:  Example for symbol [345], n([345]) = 345.

1) Describe a DFA for the language of strings of the form $[x_0y_0z_0][x_1y_1z_1]    [x_ny_nz_n]$ such that

$n(x_n...  x_1x_0) + n(y_n...  y_1y_0) = n(z_n...  z_1z_0)$

This language corresponds of reading the numbers from right to left and position
by position; this is how we add numbers by hand.Example $[819][606][213]$ is in the language because 268 + 101 =369.

How can we describe something like this? $M = (Q, E, d, q_0, F)$

where Q : ?

E = ${[abc] : a, b, c \in 0,1,...,9)} $

d: ?

$q_0 =  $

F: ?

Notice that it's not unreasonable to slightly extend this problem to an arbitrary number of triples. For example, the single triplet [123] is a reasonable candidate to be in your language, since $1+2=3$. Similarly, [280][135] is another reasonable candidate, since $12+38=50$. With that in mind, I'll extend the language to all strings of an arbitrary number (including zero) of triples that satisfy the summation requirement. I'll also decide that we'll accept a sequence of triplets only if they represent a sum without a final carry, so we wouldn't accept the string [000][000][190] since $100+900=1000$ and there's a final carry out (though [000][000][190][001] would be accepted).

The fundamental idea is a very common one: "remember" the current state of the problem by using one state in the DFA for each possible configuration. Here's what we might do:

Label the start state $start$. We haven't read any input yet. This will also be the unique final state.
Let state $t$ remember that we've seen the first [, so we have the move $\delta(start, [)=t$.
Next, construct ten states $p_0, p_1, \dotsc,p_9$ to remember the first digit. We'll have the moves $\delta(t,i)=p_i$, i.e., from $t$ we'll be in state $p_i$ after having seen input $i$.
Now make twenty more states, $q_0, \dotsc,q_9$ and $c_0,\dotsc,c_9$. The $q$'s will record the sum of the first two inputs if there's no carry and the $c$'s will record the sum if there is a carry. In other words
$$
\delta(p_i,j) =\begin{cases}
                  q_{i+j} &\text{if } i+j\le 9\\
                  c_{(i+j)\bmod{10}} &\text{if } i+j\ge 10
               \end{cases}
$$
Then make two states, $a,b$ to note whether the third input is the sum of the first two and wehther or not we've generated a carry. From state $q_k$ (sum is $k$ with no carry) we'll pass to state $a$ if the third input is the digit $k$. Similarly, we'll have $\delta(c_k,k)=b$ meaning that we've just seen the appropriate third digit and we had a carry.
Now we've read the first triplet and we're expecting to see a ]. In state $a$ we know we've completed the first triplet and don't have to adjust any subsequent triplet, so $\delta(a,]) = start$, i.e., we loop back to the start and accept if there's no further input. On the other hand, if we're in state $b$ then we have a correct digit sum, but we also have a carry, so we can't yet accept when we see a ], instead we need to read another triplet. We'll process the ], read a [ and duplicate the whole process again, this time adjusting for the carry. We'll then have $\delta(b, ])=u$ and $\delta(u,[)=v$.
Starting anew from state $v$, we construct 34 new states exactly as we did in steps (1) - (6). The only difference is that the transitions from the new states corresponding to the original $p$ states (call them $p'_i$) in step (4) we'll compensate for the previous carry in and have
$$
\delta(p_i,j) =\begin{cases}
                  q_{i+j+1} &\text{if } i+j+1\le 9\\
                  c_{(i+j+1)\bmod{10}} &\text{if } i+j+1\ge 10
               \end{cases}
$$
The final difference with these new states is that if we get to the new state, $b'$ corresponding to the original $b$, then on seeing ], we go back to state $start'$ and start again.

In high-level terms, we have two nearly-identical functions to check whether a triplet $t$ is valid:

$N(t)$ which checks whether $t$ is valid, assuming no carry in. This will return 0 or 1, depending on whether or not $t$ generated a carry.
$C(t)$ which checks whether $t$ is valid, assuming a carry in. This will return 0 or 1, depending on whether or not $t$ generated a carry.

Then, we would have the following pseudocode

c = 0
while there's a triplet t to process
   get t
   if c = 0
      c = N(t)
   else
      c = C(t)
end loop
if c = 0
   accept
else
   reject


Why do we have different algorithm for MST when graphs are directed? What was the reason to come up with Chu–Liu/Edmonds' algorithm when the input graph is directed instead of using the Prim's or Krushkal's method for finding Minimum spanning tree ?
What cases are not covered in using Prim's algo for finding MST for directed input?

Your question was already asked before it seems, but got no explicit examples. I try to give these here.

First note the question only makes sense if we consider a node $u$, and there exist spanning trees starting with $u$. The algorithms of Prim and Kruskal make choices in a greedy way. Once the choice is made, it will not be reconsidered. We show how this choice will go wrong for certain example.

The left picture has two spanning trees, with weight $6+2$ and weight $6+4$. Starting with node $u$ Prim will consider the two edges $4$ and $6$ and choose the lightest one. Now, only one spanning tree remains, not the best one.

The right picture has three spanning trees, with weight $4+2$, weight $6+1$, and weight $6+4$. Kruskal will choose the lightest edge $1$. Now, only one spanning tree remains, not the best one.


Proof that the regular languages are closed under string homomorphism Where can I find a proof of this? Thanks!

First of all, homomorphism is a special case of substitution. Now define the homomorphism as a substitution $h$ that replaces each symbol $a$ in an alphabet $\Sigma$ for a string $h(a) \in \Gamma^*$, where $\Gamma$ can be another alphabet (they can perfectly be the same). Formally the homomorphism $h(\epsilon) = \epsilon$ and for all strings in $ \Sigma^*$, $$h(a_1a_2\ldots a_n) = h(a_1)h(a_2)\ldots h(a_n)$$

Then you are near to proving the closure. Try induction over the number of operands (unions, concatenations, stars) in the regular expression that represents the language $L$. Base step: $h(\epsilon)=\epsilon$ for all $a \in \Sigma^*$, $h(a)$ is a string over $\Gamma^*$ and $h(\emptyset) = \emptyset$. The induction hyphotesis says that if $L$ is regular, then $h(L)$ is regular. The inductive step has three cases: $L$ as a union of $A$ and $B$ ($A \cup B$), $L$ as the concatenation of $A$ and $B$ ($L=AB$) or $L = A^*$. Then you should be able to finish the proof.


What constitutes one unit of time in runtime analysis? When calculating runtime dependence on the input, what calculations are considered? For instance, I think I learned that array indexing as well as assignment statements don't get counted, why is that?

When doing complexity calculations we generally use RAM model. In this model we assume that array indexing is O(1). Assignment statement is just like assigning some value to some variable ins array of variables. This is just for convenience. It simplifies analysis of the algorithm.  In real world array indexing takes $\approx$ O(log I) where I is number of things indexed.

We generally consider things that depend on size of input e.g. loops. Even if there is O(1) operation in the loop and it is executed n times then algorithm runs for O(n) time.

But O(1) operation outside of loop take only constant time and O(n) + O(1) = O(n).

Read about radix sort algorithm from CLRS.


Is there a more up-to-date / wider-scope version of the 'Compendium of NP Optimization Problems' When I was studying Comp Sci, we had Garey & Johnson as a course textbook, with a large collection of NP-Complete problems. But by that time you could also have a look at the Compendium of NP Optimization Problems, online.

However, it seems the 'Compendium' site has not seen any updates in several years. Is that indeed the case? Is there a more up-to-date compendium (perhaps in print) which accounts for further research and contains more problems in more domains?

I know of no compendium that is completely satisfactory in any regard. It seems to be too much of a thankless task maintaining these things, thus I suspect that broad answer to your question is, unfortunately, no.

However, there are several resources which, together, are at least a good start for any search.

In this case, Wikipedia is a fairly decent resource (I guess the contribution model helps overcome some of the problems with a single-curator approach, but you lose the consistency).

If you're interested in Parameterized Complexity, Marco Cesati began a compendium of problems, but like Kann, has (understandably) not kept up with the updates. There's also an online compendium, but it is less comprehensive.

A similar question was also asked on cstheory, attracting a couple of answers, one that caught my eye was the Encyclopedia of Algorithms. I cannot personally vouch for it, but it at least looks useful, or at least useful enough to convince a university library to buy.


How to split a context-free language into three sub-languages? I try to split the language
$$
L = \{a^ib^j \mid i \neq 2j, i \neq 3j\}
$$
into three languages
\begin{align}
L_1 &= \{a^ib^j \mid i < 2j\} \\
L_2 &= \{a^ib^j \mid 2j < i < 3j\} \\
L_3 &= \{a^ib^j \mid i > 3j\}
\end{align}
and then use one more production $S = S_1|S_2|S_3$,
but I have no idea how to find the CFG for $L_2$.

The idea is to start with a grammar for the related language $L'_2 = \{a^ib^j \mid 2j \leq i \leq 3j\}$:
$$ S \to a^2Sb \mid a^3Sb \mid \epsilon. $$
We want to force at least one production of the form $a^2Sb$ and at least one of the form $a^3Sb$. There are many ways of doing that. The simplest, probably, is to force one of these productions to be the first, and the other one to be the last:
$$ \begin{align*} &S \to a^2 T b \\ & T \to a^2 T b \mid a^3 T b \mid a^3 b \end{align*} $$
Alternatively, let us notice that the condition $2j < i < 3j$ can be written as $2j+1 \leq i \leq 3j-1$, and also as $2(j-2) \leq i-5 \leq 3(j-2)$. This implies the even simpler grammar
$$ S \to a^2Sb \mid a^3Sb \mid a^5 b^2 $$


Doubt in understanding the time complexities of algorithms to recognize regular expressions I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al first edition where I came across the following table.

The authors justify the table as follows:

Given a regular expression $r$ and an input string $x$, we now have two methods for determining whether $x$ is in $L(r)$. One approach is to use Thompson's Construction to construct an $NFA$  $N$ from $r$. This construction can be done in $O(|r|)$ time, where $|r|$ is the length of $r$. $N$ has at most twice as many states as $|r|$, and at most two transitions from each state, so a transition table for $N$ can be stored in $O(|r|)$ space. We can then use Algorithm 3.4 to determine whether $N$ accepts $x$ in $O(|r| \times |x|)$ time. Thus, using this approach, we can determine whether $x$ is in $L(r)$ in total time proportional to the length of $r$ times the length of $x$.

(a) A second approach is to construct a $DFA$ from the regular expression $r$ by applying Thompson's construction to $r$ and then the subset construction, Algorithm 3.2, to the resulting $NFA$.
(b) Implementing the transition function with a transition table, we can use Algorithm 3.1 to simulate the $DFA$ on input x in time proportional to the length of $x$, independent of the number of states in the $DFA$.

Dependencies:

Algorithm 3.4

Algorithm 3.2

Algorithm 3.1

Doubt: The point where I am having the doubt is that why are the authors only considering the time complexity of just the algorithm 3.1 and not the time of rest of the work done in the $2(a)$ and $2(b)$. Since the worse case space complexity of the DFA is exponential won't creation of the same involve exponential time as well?

The authors are describing the time complexity to determine whether the input string $x$ is in $L(r)$ in the table and not including construction time, that is they list the per-string cost of using the DFA or NFA, and not the one-time construction cost to build it. In many cases the construction will be done once, and used to recognize strings many times, so it may be worthwhile to sacrifice some time upfront to gain more efficient string recognition afterwards.
You are right to consider the construction cost though. If the automaton will be constructed and used only once, or a small number of times, then the savings in string recognition efficiency may not justify the higher construction time costs.


Is there any standard for comparing runtimes experimentally? My situation

I am writing a paper presenting a software module I developed and I want to compare its runtime to other modules for the same task.
I am aware of the drawbacks of runtime experiments, but please assume as given that there is no way around it in my case.
(I can and do deduce some properties theoretically, but it doesn’t suffice for everything.)

The specific scenarios I want to use for benchmarking have two parameters: the complexity $n$ of the problem and a random seed $r$ which determines the detailed problem. Mainly I want to show the dependence on $n$. Going by preliminary investigations and theory, the influence of $r$ on the runtime is minor or negligible. A single task takes at most ten minutes to complete.

Actual question

I am looking for some commonly accepted or published procedure on performing such experiments or at least a list of common pitfalls (ideally published).

What I found so far

Nothing. Internet searches turn up all sorts of unrelated results, but then I may not be using the right terminology. Including the keyword minimum, which I know to be a good standard (see below), didn’t help either.

How I would do it

Run all experiments on the same machine with potentially interfering software such as a GUI disabled as far as possible.
Subject all modules to the same selection of scenarios, i.e., the same $n$ and $r$.
For each scenario, test the different modules directly after each other in random order. With other words, the loop over the different modules is the innermost one. This should avoid bias on the different modules due to slow fluctuations of the machine’s performance (e.g., due to temperature changes). The random order should avoid bias through such effects as caching or one module always being tested after the same one.
For each $n$, take the minimum runtime over several scenarios with different seeds as the benchmark. This should avoid bias on the different modules due to short-time fluctuations of the machine’s performance that make individual runs exceptionally bad.

In addition to elapsed time for each run, report seconds of user & system mode, and total IP packets, and total disk I/Os, if only to verify that some numbers are consistently "low" and have negligible impact on elapsed time.

On https://wiki.freebsd.org/BenchmarkAdvice PHK and others offer good advice, including

  Use ministat to see if your numbers are significant. Consider buying "Cartoon guide to statistics"


Local search: Problem with neighborhood definition I have question on understanding the following neighborhood relation within a local-search approximation scheme.
Let $M$ be a legal matching on any bipartite graph.
Let $U_k$ be the neighborhood defined as follows:
$$U_k := \{M' : |(M' \backslash M) \cup (M \backslash M')| \leq k\}$$

Can somebody give me an example or explain this to me?

If i choose a small k-value, the cardinality of $M'$ will be small as well, but how does an algorithm decide which matching pair of nodes to take?

If we define node-values and make it a weighted matching,let say we define a weight function $w_e \in \mathbb{R}$ for any edge e in our graph, now the algorithm may use greedy method and take the best possible pair of nodes (with greatest weight).

But I still don't understand the exact set definition of our neighborhood.

I would be grateful for an example, because I'm stumped on this one.

The metric used for the definition of the neighborhood is the size of the symmetric difference. The symmetric difference $A\triangle B$ of two sets $A,B$ is the number of elements which are in exactly one of the sets $A,B$. So $A\triangle B = (A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A)$. A matching is considered a set of edges, so $M\triangle M'$ is the set of edges that are found in exactly one of the matchings. The metric is $d(M,M') = |M \triangle M'|$, and the $k$th neighborhood of a matching $M$ is the set of matchings $M'$ at distance at most $k$ from $M$.

As an example, if $M'$ results from adding an edge to $M$ or from removing an edge from $M$ then $d(M,M') = 1$, and if $M'$ results from replacing one edge of $M$ with another then $d(M,M') = 2$.


Let G be k-reguler bipartite graph of degree at least 2. show that K(G) not equal 1? Let G be k-reguler bipartite graph of degree at least 2, for all v belong to V(G) prove that k(G-v) is connected?

The statement is false. Here is a counterexample. Let $E$ be the even numbers and $O$ be the odd numbers, and Let $N=\{(n,n+1)|n\in\mathbb{N}\}$. Then $G=(E\cup O, N)$ is a $2$-regular, bipartite graphs, every vertex of which is a cut-vertex.

I won't do your homework for you until you can show where you get stuck, but I'll give you a hint: the conjecture is true for finite graphs, and the proof hinges on this fact. You say, well the resulting components have some number of vertices, and these vertices of one component are distributed between the partitions, so I can count the number of edge ends on either side of the partitions and then you double check if it comes out to the same. It also hinges on the fact that the two partitions are equally big: for a $k$-regular graph $G=(U\cup V, E)$, $|U|=|V|$, a fact which you will have to prove first. The proof for that hinges on the fact that the graph is regular.


Categorisation of type systems (strong/weak, dynamic/static) In short: how are type systems categorised in academic contexts; particularly, where can I find reputable sources that make the distinctions between different sorts of type system clear?

In a sense the difficulty with this question is not that I can't find an answer, but rather that I can find too many, and none stand out as correct. The background is I am attempting to improve an article on the Haskell wiki about typing, which currently claims the following distinctions:

No typing: The language has no notion of types, or from a typed perspective: There is exactly one type in the language. Assembly language has only the type 'bit pattern', Rexx and Tk have only the type 'text', core MatLab has only the type 'complex-valued matrix'.
Weak typing: There are only few distinguished types and maybe type synonyms for several types. E.g. C uses integer numbers for booleans, integers, characters, bit sets and enumerations.
Strong typing: Fine grained set of types like in Ada, Wirthian languages (Pascal, Modula-2), Eiffel

This is entirely contrary to my personal perception, which was more along the lines of:

Weak typing: Objects have types, but are implicitly converted to other types when the context demands it. For example, Perl, PHP and JavaScript are all languages in which "1" can be used in more or less any context that 1 can.
Strong typing: Objects have types, and there are no implicit conversions (although overloading may be used to simulate them), so using an object in the wrong context is an error. In Python, indexing an array with a string or float throws a TypeError exception; in Haskell it will fail at compile time.

I asked for opinions on this from other people more experienced in the field than I am, and one gave this characterisation:

Weak typing: Performing invalid operations on data is not controlled or rejected, but merely produces invalid/arbitrary results.
Strong typing: Operations on data are only permitted if the data is compatible with the operation.

As I understand it, the first and last characterisations would call C weakly-typed, the second would call it strongly-typed. The first and second would call Perl and PHP weakly-typed, the third would call them strongly-typed. All three would describe Python as strongly-typed.

I think most people would tell me "well, there is no consensus, there is no accepted meaning of the terms". If those people are wrong, I'd be happy to hear about it, but if they are right, then how do CS researchers describe and compare type systems? What terminology can I use that is less problematic?

As a related question, I feel the dynamic/static distinction is often given in terms of "compile time" and "run time", which I find unsatisfactory given that whether or not a language is compiled is not so much a property of that language as its implementations. I feel there should be a purely-semantic description of dynamic versus static typing; something along the lines of "a static language is one in which every subexpression can be typed". I would appreciate any thoughts, particularly references, that bring clarity to this notion.

Historically, the term "strongly typed programming language" came into use in the 70's in reaction to the existing widely used programming languages, most of which had type holes.  Some examples:

In Fortran, there were things called "COMMON" storage areas, which could be shared across modules, but there were no checks to see if each module was declaring the contents of the COMMON storage with the same types.  So, one module could declare that a particular COMMON storage block had an integer and another a floating point number, and the data would get corrupted as a result.  Fortran also had "EQUIVALENCE" statements, whereby the same storage could be declared to contain two different objects of different types.
In Algol 60, the type of procedure parameters was declared as just "procedure", without specifying the types of the parameters of the procedure.  So, one could assume that a procedure parameter was an integer-accepting procedure, but pass in a real-accepting procedure as the argument.  This would result in the same kind of corruption as the COMMON and EQUIVALENCE statements.  (However, Algol 60 did eliminate the older problems.)
In Pascal, "variant records" were added which were almost exactly like the old EQUIVALENCE statements.
In C, "type casts" were added whereby any type of data could be reinterpreted as data of a different type.  This was a rather deliberate type hole meant for programmers who supposedly know what they are doing.

The strongly typed languages designed in the 70's were meant to eliminate all such type holes.  If you drill down into what this means, it means essentially that data representations are protected.  It is not possible to view data object of one type as an object of another type which happens to have the same bit pattern as its internal representation.  Theoreticians began to use the term "representation independence" to characterize this property instead of the vague idea of "strong typing".

Note that dynamically typed languages like Lisp which perform complete run-time type checking are "strongly typed" in the sense of protecting representations.  At the same time, statically typed languages would lose representation independence unless they did array bounds checking.  So, they are not "strongly typed" in the strict sense of the term.  Due to these anomalous consequences, the term "strongly typed" fell into disuse after the 70's.
When the US Department of Defence developed rigorous requirements for the design of Ada, they included the requirement that the language should be "strongly typed".  (It seems to have been believed at that time that the idea of "strongly typed" was self-evident.  No definition was offered.)  All the language proposals submitted in response claimed to be "strongly typed".  When Dijkstra analysed all the language proposals, he found that none of them were strongly typed and, in fact, it wasn't even clear what the term meant.  See the report EWD663.  However, I see that the term is coming back into use now, through a younger generation of researchers who don't know the checkered history of the term.

The term "statically typed" means that all type-checking is done statically and no type errors will arise at run-time.  If the language is also strongly typed, that means that there are really no type errors during execution.  If, on the other hand, there are type holes in the type system, the absence of run-time type errors means nothing.  The results could be completely corrupt.

The new debate about "strong vs weak typing" seems to be about whether certain type conversions should be allowed.  Allowing a string where an integer is required is "weak typing" according to these folks.  There is some sense to that because attempting to convert a string to an integer may fail, if the string doesn't happen to represent an integer.  However, converting an integer to a string doesn't have that problem.  Would that be an instance of "weak typing" according to these folks?  I have no idea.  I notice that the Wikipedia discussions on "weak typing" don't cite any refereed publications.  I don't believe that it is a coherent idea.

Note added: The basic point is that the term "strong typing" did not come into use as a technical term with a rigorous definition.  It was more like some language designers felt: "our type system is strong; it catches all type errors; it doesn't have type holes" and, so, when they published their language design, they claimed that it was "strongly typed".  It was a buzz word that sounded good and people started using it.  The Cardelli-Wegner paper was the first one that I have seen where some analysis was provided into what it means.  My post here should be thought of as an elaboration of their position.


A criterion for the planar graph to have unique dual I get stuck with the following two criteria both about the uniqueness of plane embeddings of a given planar graph. The first one says that a planar graph admits unique plane embedding iff it is a subdivision of 3-connected planar graph (e.g. from the book "Planar Graphs: Theory and Algorithms"). The second one (is from paper "The uniquely embeddable planar graphs") tells that uniqueness holds iff it is 3-connected planar plus some exclusions. I suppose they are based on two different definitions of equivalence. As for me I consider plane embeddings equivalence as an equivalence of the respective complexes. Indeed, each plane graph is in fact a triple $(V,E,F)$ where $F$ denotes set of faces. So the equivalence means that there is a map that translates the first complex to another one that keeps incidence between vetices and edges, edges and faces, vertices and faces.

My question is particularly under what definition the first criterion holds ? The proof that the book gives is a bit untransparent for me in that matter because the definition of uniqueness that it gives is not that strict.

First let me mention that the definition of being uniquely embeddable requires ANY graph isomorphism (e.g. just renaming symmetric vertices or any other automorphism permutation) to be (not necessary uniquely) extendable to topological (or combinatorial) one (see Diestel Graph Theory chapter about planar graphs for these definitions) in contrast to usual understanding of this definition that for any two planar embeddings there EXISTS some topological (or combinatorial) isomorphism. Difference between the topological and combinatorial isomorphism definitions is negligible for 2-connected planar graphs (see Diestel book). This particularly means that if we reflect or twist some symmetric graph (as done in the proof of necessity of the aforementioned criterion "subdivision of 3-connected planar graph if and only if condition to be embeddable" in the book "Planar Graphs: Theory and Algorithms") we get topologically non-isomorphic graph in general. Though $K_{2,3}$ graph witnesses that the necessity proof here is wrong but the sufficiency is hold.

What I mean by complex-based isomorphism is just combinatorial one from Diestel book.

If we allow my unusual definition of uniqueness that any two embeddings are topologically isomorphic then there is an example of 2-connected non-subdivisions that are uniquely embeddable.

As for aforementioned paper "Uniquely embeddable planar graphs" the special definition which is given there is tougher (not robust to transposition of symmetric vertices) (but close to as Yuval assumed) than topological isomorphism according to its Theorem 3.5.


Converting context-free grammar to Chomsky/Greibach Normal Form Is it necessary to remove all lambda productions, unit productions and useless productions from a context free grammar(CFG) before converting to Chomsky Normal Form(CNF) or Greibach normal form (GNF). If so why is it required?

Also my Professor said that we should convert a CFG into CNF before converting it to GNF. Is that required or can we straight away convert a CFG into a GNF?

You can convert a context-free grammar into Chomsky normal form or Greibach normal form in whatever way you wish (converting a grammar to a normal form means finding a grammar in the normal form which generates the same language as the original grammar). A given algorithm might require you first to remove lambda productions, or first to convert to Chomsky normal form. If using a specific algorithm, you have to follow whatever the algorithm prescribes.


Constructing a directed graph for O(1) queries This question appeared in an undergrad data structures final. The details are sound.

I need help to design a data structure for a directed graph with the following properties:

Initialization should be done in O(1) time.
AddVertex(id1,id2,...idK) - Add a new vertex to the graph. The new vertex is added with id=N+1 where N is the number of existing vertices.
id1...idK are the neighbors of the new vertex, such that there is an outgoing edge from the new added vertex to each of the vertices id1 .. idK.
This should be done in O(K) time.
GetNumberOfNeighbors(id) - Return the number of outgoing edges for a vertex with a given id (id is in 1..N). This should be done in O(1) time.

All O(1) times are for worse case.

I know that the idea is to allocate a new array of K*constant length during the AddVertex method, and to copy K vertices to it in O(K) total, but I don't know how to do this exactly.

Thanks a lot

Make a Node class whose objects hold and an array of references to the other nodes they connects to. Make a Graph class whose objects store a dictionary mapping node IDs to nodes, and implement your 3 methods.


Word Problem over Finite Groupoids I'm struggling with an interesting problem from a chapter about Dynamic Programming in Skienas' famous "The Algorithm Design Manual".
It's listed on the following web-page under number 8-22: http://www.algorist.com/algowiki/index.php/Divide-TADM2E#8-22

The problem asks you to write a polynomial-time algorithm using DP which solves a special case of the Word Problem over finite groupoids:

Given a finite groupoid $G$, a word $s$ on $G$ and an $x \in G$, find out whether it is possible to parenthesize $s$, such that its evaluation will yield $x$. Example from the book:

\begin{array}{c|ccc}
&       a       &       b       &       c      \\
\hline
a       &       a      &       c      &       c  \\
b       &       a      &       a      &       b  \\
c       &       c      &       c      &       c  \\
\end{array}

For instance, consider the above multiplication table and the string
$bbbba$.
Parenthesizing it $(b(bb))(ba)$ gives $a$, but $((((bb)b)b)a$ gives $c$.

So far I managed to write a naive $O(n!)$ recursive algorithm in Python:

def i(x):
    return ord(x) - ord('a')

def mul(x, y):
    return groupoid[i(x)][i(y)]

# rewrite('abc', 1) = 'ac'
# rewrite('abc', 0) = 'cc'
def rewrite(word, i):
    return word[:i] + mul(word[i], word[i+1]) + word[i+2:]

def search(word, x):
    exists = (word == x)
    for i in range(0, len(word) - 1):
        if exists:
            break
        exists |= search(rewrite(word, i), x)
    return exists

word = sys.argv[1]
x = sys.argv[2]
exists = search(word, x)
print('Solution exists' if exists else 'Unsolvable')

Although we can memoize search, it won't give us polynomial time, since memoization space is of a factorial order. This is where I'm stuck.

The problem here is to somehow reduce the factorial search-space of all possible reductions from $s$ on $G$ to a polynomial search-space, which will depend only on $|s|$ and $|G|$. Can you please help me with that? Any other hints?

This word problem over groupoid is a nice example to show the essence of dynamic programming, the recognition of the subproblems. In other words, how can we define the table or the multi-dimensional array that we should fill?
In general, the subproblems should represent the computations that will be repeated many times in a brute-force algorithm. The subproblems should be refined enough so that we can solve the larger subproblems from the solutions of the smaller subproblems. Please take a moment to appreciate how the subproblems are defined below.
Compute $dp[i][j]$, the set of all possible values of $x_{i}x_{i+1}\cdots x_j$, where $1\le i\le j\le n$.
The goal element $a$ is a possible value of $x$ if and only if $dp[0][n]$ contains $a$.
How to compute $dp[i][j]$?
The base case, $dp[i][i]$ is the set of a single element, $x_i$.
How about the case when $j\ge i+1$? Note a parenthesization of $x_ix_{i+1}\cdots x_j$ means to parenthesize it into two parts, $(x_i\cdots x_t)(x_{t+1}\cdots x_j)$ for some $i\le t\lt j$, followed by a parenthesization of the front part $x_i\cdots x_t$ and a parenthesization of the behind part, $x_{t+1}\cdots x_j$. So $dp[i][j]$ contains all products of the form $f\cdot b$, where $f$ is a possible value of the front part and $b$ is a possible of the behind part. Note both the front part and behind part are shorter than the whole, $x_ix_{i+1}\cdots x_j$.
In other word, in order to compute $dp[i][j]$, we can iterate $f$ through all elements in $dp[i][t]$ and $b$ through all elements in $dp[t+1][j]$, adding the product $f\cdot b$ to $dp[i][j]$.
There are $n(n-1)/2$ choices for $i$ and $j$. There are at most $n$ choices for $t$. There are at most $k$ choices for $f$. There are at most $k$ choices for $b$. Depending on the implementation, it takes $O(k\cdot k\cdot k)$ or much less time to compute product $f\cdot b$ and add it to a set of at most $k$ elements. Hence the time-complexity of the algorithm is polynomial in $n$ and $k$.


Time spent on requirement and its effect on project success and development time Is there any evidence suggesting that time spent on writing up, or thinking about the requirements will have any effect on the development time? Study done by Standish (1995) suggests that incomplete requirements partially (13.1%) contributed to the failure of the projects. Are there any studies done which show that time spent on requirement analysis will have any effect on development time of a project, or how successful the project will be.

See Code Complete, By Steve McConnell, Table 3-1.
He compares the average cost of fixing defects based on when they're introduced and detected.
Detection at construction time costs 5-10 times more than detection at requirements time, and 10-100 times more post-release.

The table is based on the following sources:

"Design and Code Inspections to Reduce Errors in ProgramnDevelopment" (Fagan 1976)
Software Defect Removal (Dunn 1984)
"Software Process Improvement at Hughes Aircraft" (Humphrey, Snyder,
and WIllis 1991)

and several more


Why is deep learning hyped despite bad VC dimension? The Vapnik–Chervonenkis (VC)-dimension formula for neural networks ranges from $O(E)$ to $O(E^2)$, with $O(E^2V^2)$ in the worst case, where $E$ is the number of edges and $V$ is the number of nodes. The number of training samples needed to have a strong guarantee of generalization is linear with the VC-dimension.

This means that for a network with billions of edges, as in the case of successful deep learning models, the training dataset needs billions of training samples in the best case, to quadrillions in the worst case. The largest training sets currently have about a hundred billion samples.  Since there is not enough training data, it is unlikely deep learning models are generalizing. Instead, they are overfitting the training data.  This means the models will not perform well on data that is dissimilar to the training data, which is an undesirable property for machine learning.

Given the inability of deep learning to generalize, according to VC dimensional analysis, why are deep learning results so hyped? Merely having a high accuracy on some dataset does not mean much in itself. Is there something special about deep learning architectures that reduces the VC-dimension significantly?

If you do not think the VC-dimension analysis is relevant, please provide evidence/explanation that deep learning is generalizing and is not overfitting. I.e. does it have good recall AND precision, or just good recall? 100% recall is trivial to achieve, as is 100% precision. Getting both close to 100% is very difficult.

As a contrary example, here is evidence that deep learning is overfitting. An overfit model is easy to fool since it has incorporated deterministic/stochastic noise. See the following image for an example of overfitting.

Also, see lower ranked answers to this question to understand the problems with an overfit model despite good accuracy on test data.

Some have responded that regularization solves the problem of a large VC dimension.  See this question for further discussion.

"If the map and the terrain disagree, trust the terrain."
It's not really understood why deep learning works as well as it does, but certainly old concepts from learning theory such as VC dimensions appear not to be very helpful.
The matter is hotly debated, see e.g.:

H. W. Lin, M. Tegmark, D. Rolnick, Why does deep and cheap learning work so well?
C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals, Understanding Deep Learning Requires Rethinking Generalization.
D. Krueger, B. Ballas, S. Jastrzebski, D. Arpit, M. S. Kanwal, T. Maharaj, E. Bengio, A. Fischer, A. Courville, Deep Nets Dont Learn Via Memorization.

Regarding the issue of adversarial examples, the problem was discovered in:

C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, A. Rabinovich, Going deeper with convolutions.

It is further developed in:

I. Goodfellow, J. Shlens, C. Szegedy, Explaining And Harnessing Adversarial Examples.

There is a lot of follow-on work.
Update March 2020. A new hypothesis that appears to explain some of the mismatch between clear over-parameterisation of modern (feed-forward) NNs and good recognition performance is Frankle and Carbin's Lottery Ticket Hypothesis from 2018:

J. Frankle, M. Carbin, The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks.

The claim is that a "randomly-initialised, dense [feed-forward] neural
network contains a subnetwork that is initialised such that when
trained in isolation it can match the test accuracy of the original
network after training for at most the same number of iterations." Regarding the original question, the Lottery Ticket Hypothesis might be understood as saying that:

Training by stochastic gradient descent searches for small subnetworks that work well and deemphasises the rest of the overparameterised network's learning capacity.

The bigger the original network, the more likely it is to contain a small subnetwork with good performance on the task at hand.

This has found empirical support, e.g. in

H. Zhou, J. Lan, R. Liu, J. Yosinski, Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask.

and theoretical support in:

E. Malach, G. Yehudai, S. Shalev-Shwartz, O. Shamir, Proving the Lottery Ticket Hypothesis: Pruning is All You Need.

As far as I'm aware, it has not yet been possible to generalise the Lottery Ticket Hypothesis to recurrent NNs.
Update March 2021. The original 2016 paper Understanding Deep Learning Requires Rethinking Generalization has been updated. Here is the new version:
C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals, Understanding Deep Learning (Still) Requires Rethinking Generalization.


Proving that a certain language is regular using pumping lemma Let $\Sigma = \{a,b,c,\ldots,x,y,z\}$ be the Latin alphabet, consisting of 26 letters. Consider the language $L$ of all words $\alpha$ over $\Sigma$ satisfying the following constraints:

If $\alpha$ contains $a$ then it contains exactly $4$ many $a$s.
If $\alpha$ contains $b$ then it contains exactly $8$ many $b$s.
...
If $\alpha$ contains $`$ then it contains exactly $2^{27}$ many $z$s.

How do I prove that $L$ is regular?
Note: I did research and I have found that we can use the pumping lemma.

You cannot use the pumping lemma to show that a language is regular. The pumping lemma gives a property of regular languages: if $L$ is regular then $L$ can be "pumped". You can use this to show that $L$ is not regular: if $L$ cannot be pumped, then it is not regular. But you cannot use it to show that $L$ is regular: if $L$ can be pumped, it doesn't follow that $L$ is regular; moreover, there are examples of pumpable languages which are not regular. There are extensions of the pumping lemma which can be used to show that a language is regular, but they are not so useful in practice.
In your case, every word in $L$ contain $0$ or $4$ many $a$s, $0$ or $8$ many $b$s, and so on. In particular, it contains at most $4$ many $a$s, at most $8$ many $b$s, and so on. Therefore every word in $L$ has length at most $4+8+\cdots+2^{27}$. Consequently, $L$ is finite. Every finite language is regular.


Worst case runtime for binary search The run time of binary search is O(log(n)).
log(8) = 3
It takes 3 comparisons to decide if an array of 8 elements contains a given element.
It takes 4 comparisons in the example below.

python2.7

def binary_search(a_list, item, comparisons_inner=0):
    low = 0
    high = len(a_list) - 1

    while low <= high:
        mid = (low + high) / 2
        guess = a_list[mid]
        comparisons_inner += 1
        if guess == item:
            return mid, comparisons_inner
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None, comparisons_inner

my_list = [5, 8, 11, 15, 21, 23, 100, 223]
index, comparisons = binary_search(my_list, 223)
print(index, comparisons)

log(8) < 4
Why is the run time of binary search O(log(n)) despite the 4 comparisons it takes in the example above?

Your algorithm makes $\lfloor \log n  \rfloor+ 1$ comparisons for an array of length $n$, which is at most $2 \log n$, which is $O(\log n)$.  Hence, $\lfloor \log n  \rfloor+ 1 = O(\log n)$.

In more detail, recall that the big-O notation subsumes constant factors. A function $f(n)$ is said to be $O(\log n)$ if there exist positive constants $c$ and $n_0$ such that $f(n) \le c \log n$ for all $n \ge n_0$.  In our case, we want to prove $\lfloor \log n \rfloor +1 = O(\log n)$.  To prove the existence of positive constants $c$ and $n_0$ satisfying the desired condition, observe that $\lfloor \log n  \rfloor+ 1 \le \log n + \log n = 2 \log n$, for all $n \ge 2$.  So we can take $c = 2$ and $n_0 = 2$.


Feature detector that doesn't use corners I'm trying to use computer vision to identify objects an image. I am currently using the SURF algorithm, but Harris and SURF both find virtually no points on our objects (a paper ball and a deodorant can) due to their simple features. If it does find points it finds one or two that aren't the same points it find in the new frame. SURF also finds a large amount of points on our floor due to the contrast of the black dots on the carpet.  Here's a sample image:

Is there a feature detector that doesn't use corner detection/curvature?

If you have prior knowledge of the objects expected size you should ignore interest points of too small scale. I think these objects (thanks to round shape and contrast with the background) it should be an easy task for blob detection algorithms, you'd get one detected blob / item. Note that for SIFT or SURF the major orientation isn't well defined for blobs with rotational symmetry but it might be sufficient to assume fixed orientation (like on U-SURF).


How to deal with $n\sqrt n$ in master theorem? In classifying the following formula's asymptotic complexity using master theorem, I have $a = 8$, $b = 4$, and $d = ?$

$T(n) = 8T(n/4) + n\sqrt n$

How do I handle $n\sqrt n$ in this case to get $d$ ?

You have to remember that $\sqrt[x]{y} = y^{\frac{1}{x}}$.

Then the rest should follow easily.

Don't look at the following unless you're genuinely stuck.

   $n\sqrt{n} = n^{1}\cdot n^{\frac{1}{2}} = n ^{\frac{3}{2}}$, hence $d = \frac{3}{2}$. We also have $a = 8$ and $b = 4$, so $\log_{b}(a) = \log_{4}(8) = \frac{3}{2}$. Hence we have the second case of the Master Theorem where $f(n) \in \Theta(n^{d}\log^{0}n) = \Theta(n^{d})$ with $d = \log_{b}(a)$. Therefore $T(n) \in \Theta(n^{d}\log n) = \Theta(n^{\frac{3}{2}}\log n)$.


Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$ I'm having a small issue with wikipedia's proof that $RP \subseteq NP$:

An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic Turing machines where the machine accepts if and only if at least some constant fraction of the computation paths, independent of the input size, accept. NP on the other hand, needs only one accepting path, which could constitute an exponentially small fraction of the paths. This characterization makes the fact that RP is a subset of NP obvious.

My problem lies in the following statement: "...accepts if and only if at least some constant fraction of the computation paths, independent of the input size, accept"
My question is: for a language $L \in NP$, wouldn't it only need one computation path for the non-deterministic TM to accept? Since, if $x \in L$, $P[T(x) accepts] >= 1/2$ with $T$ being the Turing machine that decides $L$.

Fix some $L\subseteq RP$. Then:

if $x\in L$ then $P_y[T(x,y)\text{ accepts}]\ge {1\over2}$, therefore exists some $y$ where $T(x,y)$ accepts.
if $x\notin L$ then $P_y[T(x,y)\text{ accepts}]=0$, therefore for every $y$ we have $T(x,y)$ rejects.

Thus, by definition of $NP$, $L\in NP$.
As you can see from this proof, you are correct: $NP$ requires one path while $RP$ requires at least half of the paths


Algorithm for computing $Pr[s \vDash C \bigcup^{\geq n} B]$ for probabilistic verification I'm having some difficulty trying to come up with an algorithm for computing $Pr[s \vDash C ~\bigcup^{\geq n} B]$ given a finite Markov chain where $S$ is the set of states, $s \in S$, $B,C \subseteq S$, and $n \in \mathbb{N}$ where $n \geq 1$.

I have algorithms for computing $Pr[s \vDash C~\bigcup~B]$, $Pr[s \vDash C~\bigcup^{\leq n}~B]$, and $Pr[s \vDash C~\bigcup^{=n}~B]$. Instead of going down to the Markov chain itself I was thinking of using a combination of these algorithms to calculate $Pr[s \vDash C ~\bigcup^{\geq n} B]$, however, I'm worried about overcounting as it is not necessarily true that $B$ and $C$ are disjoint.

I am using the Principles of Model Checking book by Baier and Katoen.

To compute the probability for $\geq n$, you first compute the probability for an unbounded until and subtract from it the probability for $\leq n-1$. If you compare the sets of paths these formulas represent then you will that they are indeed the same. You start off with a set of all paths satisfying "reach B via C", let's call it $T$. From this set, you remove any paths where B is reached in $\leq n-1$, let's call it $U$. So the set of paths where B via C is reached in $\geq n$ steps is represented by $T \setminus U$. Using properties of probability measures, you can write $Pr(T\setminus U) = Pr(T) - Pr(U)$.

You can safely assume that $B$ and $C$ are disjoint without loss on generality. If  they are not, then reaching a state from $B \cap C$ satisfies the "until", so you can just consider $(C\setminus B) \bigcup B$.


Is $L=\{ xyx^Ry^R \mid x,y \text{ is an element of }\{0,1\}^*\}$ context-free? Is the language $L=\{ xyx^Ry^R \mid x,y \text{ is an element of }\{0,1\}^*\}$ context-free?

Note: $x^R$ is the reverse of $x$.

My Work: I think this is a context free language. Since a pushdown automaton (PDA) accepts context-free languages, I am trying to draw a PDA for this language. When I draw a PDA, how does the PDA tell $x$ and $y$ apart?
Or is this not a context-free language? (then I can use pumping length to prove this)

No, it is not a context-free language. From my original SO answer: consider the string $0^n1^n0^n1^n \in L$, where $n$ is the pumping length from the pumping lemma for context-free languages. This fails the pumping lemma for context-free languages; in particular, we have seven cases for $vxy$:

$vxy$ consists entirely of 0s from the first part of the string. Pumping this up or down will cause the numbers of 0s in the first and third parts of the strings to be different, so we're no longer in $L$.
$vxy$ consists entirely of 1s from the second part of the string. Same problem between the second and fourth parts as between the first and third parts mentioned in case 1.
$vxy$ consists entirely of 0s from the third part of the string. Same but opposite problem as in case 1.
$vxy$ consists entirely of 0s from the fourth part of the string. Same but opposite problem as in case 2.
$vxy$ straddles the first and second parts of the string, beginning with 0s and ending with 1s. Pumping will change the the numbers of 0s and 1s in the first and second parts of the string, and they won't match the third and fourth parts of the string anymore, so we're not in $L$ anymore.
$vxy$ straddles the second and third parts of the string, beginning with 1s and ending with 0s. We have the same problem as in case 5.
$vxy$ straddles the third and fourth parts of the string, beginning with 0s and ending with 1s. We have the same but opposite problem as in case 5.


What is the most efficient constant-space sorting algorithm? I'm looking for a sorting algorithm for int arrays that doesn't allocate any byte other than the size of the array, and is limited to two instructions:

SWAP: swap the next index with the current one;
MOVE: moves the cursor to +1 or -1 index;

That is, you can't swap non neighboring indexes, nor swap the index 100, after you just swapped index 10. What is the most efficient algorithm - i.e., the one that uses the less amount of total moves?

Consider cocktail shaker sort, which is a bidirectional version of bubble sort.  You bubblesort from low to high, and then (this is the added part) you bubblesort from high to low, repeat until done.  This is still $O(n^2)$, but it makes significantly fewer passes on average, because small elements near the high end of the array will be moved to their final position in a single pass rather than N passes.  Also, you can keep track of the lowest and highest positions where a swap occurred; subsequent passes need not scan beyond those points.


Size of maximum clique given a fixed amount of edges? Given an undirected graph $G = (V,E)$, what is the clique number $\omega(G)$ given $|E|$, i.e., the size of the largest clique in a graph with $|E|$ edges.

I think this is doable after realizing that the number of edges in a clique is equal to the triangular number:
$$|E(K_k)| = \frac{1}{2}k(k-1).$$

I am looking for a closed formula.

The graph can have clique number 1 (if we allow the graph to be disconnected), or 2 (consider a long path).  The graph can have a clique of size at most
$$\frac{1}{2} (\sqrt{8m + 1} + 1),$$
where $m = |E|$, provided of course that $|V|$ is large enough.


Can one increment an $n$ bit integer using fewer than $2 - 2^{1-n}$ bit inspections on average? Given an $n$-bit integer, I am interested in performing an increment operation using as few bit reads as possible. The standard binary code (standard binary representation of numbers), requires $n$ bit reads and writes in the worst case, though only $2 - 2^{1-n}$ bit reads on average (i.e $2$ bit reads on average asymptotically). On the other hand, there are codes like the Binary Reflected Gray Code that only require $1$ bit write in the worst case (since all integers in the sequence have hamming distance one). However, the BRGC requires $n$ bit reads in the worst and average case. In addition, there are other codes, such as the Recursive Partition Gray Code, which improve the average number of reads down to $O(\log n)$.

I would like the know if there is a code that can outperform the standard binary code with regards to the average number of reads. I have, however, no restrictions on the number of bit writes or the number of reads in the worst case. I feel like there should be a lower bound that says you cannot do better on average than $2 - 2^{1-n}$, but haven't been able to find a reference.

Edit: I know there is a lower bound of $\log n + 1$ reads in the worst case due to Fredman in 1978, but I am not aware of a lower bound for average case.

We can prove a tight lower bound of $2 - 2^{1-n}$ as follows. Informally speaking, we will argue inductively that whenever a bit is read during the increment procedure, that one of the two possible outcomes (a $0$ or a $1$ can be read) will cause the algorithm to stop reading additional bits. This will show that if we require the average number of reads to be strictly smaller than $2$, then we required a code isomorphic to the standard binary code.

Suppose that the first bit read by the increment algorithm is bit $i_1 \in [n]$. Now we have three cases to consider. In the first case (A), the algorithm will stop reading additional bits regardless of the value of $i_1$. This means that after reading $i_1$, the algorithm must decide which bits must be flipped right away, and clearly this will not yield a valid increment algorithm for $n > 1$. In the second case (B), the algorithm will adaptively read another bit, regardless of the value of $i_1$. We note that the algorithm may choose to read a different bit depending on the value of $i_1$. In this case, however, we are already reading at least $2$ bits no matter what, so the average number of bits read will exceed $2-2^{1-n}$. Finally, in the third case (C), the algorithm will only read another bit for a single value of $i_1$ (say $1$ for convenience). That is, when $i_1$ is $0$, the algorithm will determine which bits need to be flipped, and when $i_1$ is $1$, the algorithm will probe a second bit. In such a case, the expected number of bit reads is at least $1/2 \cdot 1 + 1/2 \cdot 2 = 3/2$. This is the only case where we can hope to beat the standard binary code.

Now we can apply this argument inductively. Suppose now that the algorithm is adaptively reading bit $i_k$, with $k \leq n-1$. Then in case (A), at most $n-1$ of the bits are ever read by the algorithm. This means that there is a bit that is never read and thus never written to, so the increment algorithm cannot be correct. Here we assume that the only bits that can be flipped are the ones read during that particular increment operation. In case (B), we can verify that the expected number of reads is at least $$\sum_{j=1}^{k-1} j/2^j + 2^{1-k}\cdot(k+1) = 2$$ which is again too many. In case (C), however, the expected number of reads can be verified to be at least $$\sum_{j=1}^{k-1} j/2^j + 2^{-k}\cdot k + 2^{-k} \cdot (k+1) = 2 - 2^{-k}\cdot(2k+3)$$ which is again the only case which might lead us to a better performance than the standard binary code.

When performing the $n$-th bit read, there are no other bits that the algorithm can read (since the other $n-1$ bits have already been read), so only case (A) becomes valid. Computing the expected number of reads then gives exactly $2 - 2^{1-n}$, as required.

I find that it helps to view this as a binary decision tree, where the internal nodes are labelled by the bit read, and the leaves are labelled by the bits that are flipped. So you begin by reading the bit labelled at the root of the tree (in our case $i_1$), then you go left if you've read a $0$ and right if you've read a $1$. With this picture in mind, it becomes clear that there are only three cases to consider at each step of the proof.


Reversing an application of `sym` to `ua` and `isoToEquiv` in cubical type theory I am proving a kind of structure invariance principle for magmas in Cubical Type Theory with the Agda/Cubical library. This is done by constructing a path between two simple magmas and then transporting proofs of simple properties about this path. I have already obtained most of the proof (see my code repository) but did not manage yet to complete the following lemma.

At some point in the proof I have the following given:

A bijection between types: f : ℕ → ℕ₀
The isomorphism constructed with f: fIso : Iso ℕ ℕ₀
A function that gives the inverse isomorphism of an isomorphism: invIso : Iso A B → Iso B A

Now, I would like to prove that:

sym (ua (isoToEquiv fIso)) ≡ ua (isoToEquiv (invIso fIso))

There are two parts to my question:

Is this a valid theorem in HoTT? Although this statement seems valid, maybe I have produced a false statement?
Are there built-in functions in the Agda/Cubical that may help in the proof?

The original  statement in my question
sym (ua (isoToEquiv fIso)) ≡ ua (isoToEquiv (invIso fIso))
is a valid statement in Homotopy Type Theory but because (homotopy-) isomorphisms are a special case of equivalences, the statement can be generalized to

sym (ua fEquiv) ≡ (ua (invEquiv fEquiv)) (*)

It is one of the properties of ua that are informally proven in the Univalent Foundations book in section 2.10.

Solution

The results from 1 have been implemented and proven in the lemmas in the Agda Cubical library. The function uaInvEquiv of those lemmas in particular solves my problem (*). For future applications it is better to use 4 because they are more general than my own approach below.

Historical solution

Using the hint to use EquivJ, I gave a proof for the theorem that may not be the most efficient one but it worked (typechecked) for my specific case:

baseIndLemma : (A : Type ℓ-zero) → (λ i → ua (idEquiv A) (~ i)) ≡ ua (invEquiv (idEquiv A))
baseIndLemma A =
  sym ( ua (idEquiv A) ) ≡⟨ uaIdEquiv ⟩
  sym refl ≡⟨ refl ⟩
  refl ≡⟨ sym uaIdEquiv ⟩
  ua (idEquiv A) ≡⟨ cong ua (equivEq (idEquiv A) (invEquiv (idEquiv A)) refl) ⟩
  ua (invEquiv (idEquiv A)) ∎

myUaInvEquiv : sym (ua fEquiv) ≡ (ua (invEquiv fEquiv))
myUaInvEquiv = EquivJ
  (λ _ _ e → sym (ua e) ≡ ua (invEquiv e)) (λ A → baseIndLemma A) ℕ₀ ℕ fEquiv


Is it a tautology or not? According to my truth table its not If $\bigr((q\leftrightarrow p)\leftrightarrow s\bigl)$ is a tautology and $p\rightarrow s$ is contingent, does it follow that $q\rightarrow s$ is contingent?

Since I can't show $\bigr((q\leftrightarrow p)\leftrightarrow s\bigl)$ is a tautology, I'm unsure how to proceed.

The question is not phrased clearly.  Perhaps the question can be rephrased as follows: Let $p,q$ and $s$ be propositions whose truth values belong to some subset $A \subseteq \{T,F\}^3$.  Suppose $A$ is such that $(q \leftrightarrow p) \leftrightarrow s$ evaluates to true for each assignment from $A$ and $p \rightarrow s$ can take both possible truth values over assignments from $A$. Can $q \rightarrow s$ take both possible truth values over assignments from $A$?

But there are many $A$'s which satisfy the given two conditions, and different $A$'s will give different answers- it can be a contingency, or it can be tautology.


Clarifications on polynomial reducibility for problems in P and NP-complete Can I always increase the complexity of a problem via polynomial reduction? (in which case 'reduction' is really a misnomer) For example, if I have a classic P problem (say, finding the smallest element in an array, by iterating through and making comparisons with the smallest value found thus far), what would be a corresponding problem in NP-complete (obtained via polynomial reduction)? Or, would it be possible to polynomially reduce a constant time (worst case) algorithm into a polynomial time algorithm (basically performing unnecessary executions for all n of the input for nothing)?

As a side request, I'm looking for a basic reference that deals with how one problem (in P or NP-complete) can be reduced (in polynomial time) to a problem in (P or NP-complete). Most of the things I found online are beyond scope or vague. I'm looking for an easy way to figure out whether a certain Problem A (in P or NP-complete) can be polynomially reduced to a Problem B (in P or NP-complete).

As pointed out by @Vor the point of polynomial-time reductions is to show that if have a reduction from A to B and an algorithm to solve a problem B then you can use it to efficiently (i.e. in polynomial time) solve the problem A. Note that efficiently does not mean optimally, when you reductions, your solutions will not be better than the class your use for reductions (i.e. if you use a polytime reduction to reduce to a constant time language, you still have just a polytime algorithm).

I think what you are getting confused about is that reductions can be used to show that a problem is easy or that it is hard. In this case, they are used in two different ways. Suppose you have some problem X, and

you think it is easy (i.e. doable in polynomial time). In that case you find your favorite polynomial time problem B (say linear programming) and reduce X to B. Now you have an efficient algorithm for X: run the reduction and then run a polytime LP-solver. On the other hand,
you think X is hard (i.e. probably not doable in polynomial time). In that case you find your favorite NP-complete problem A (say 3-SAT) and reduce A to X. Now if you had an efficient algorithm for X, you would be able to solve A in polynomial time (reduction, then X). Since we suspect that A cannot be solved in polynomial time, this means we have a contradiction, so you cannot have an efficient algorithm for X.

There is no general rule for deciding if a given problem is in P or NP-complete, but we have a list of rules of thumb to help you.


Making groups out of a list of things based on some similarity Let's say I have a list of n items - i1, i2, ..., in.

These items are similar to one another based on some similarity function, say similar_func(item_x,item_y) where item_x,item_y belong to list i1, i2, ... in. This function returns a number that ranges from 0 to 1, where 0 means not similar at all and 1 means exactly similar.

Now I would like a create a number of groups, each of which may contain items from the above list. Each group having items that are similar to each other items of the group by let's say 0.5.

I could run a double loop on the list, comparing each item to one another and creating a group whenever I find two items with similarity more than 0.5. Of course I would need to check if the item already exists in a group already created and with all the other items in that group.

This brute force method is possible and will give the right answer.

But I would like to do this more efficiently. Is there a efficient method for solving this problem?

Edit:
There can be any number of groups and an item can be in multiple groups.

If similarity(x,y) = 0.6 and similarity(x,z) = 0.6, but similarity(y,z) = 0.4, then there will be two groups -> [x,y] and [x,z]

Also if x is similar to y AND x is similar to z, then it doesnt mean that y is similar to z. The similarity between two items solely depends on the the return value of similarity function when those items are passed as arguments to it.

Suppose you represent your items as vertices in a graph and two vertices are connected by an edge if they have a similarity greater than $0.5$.
Then, a possible group corresponds to a clique in this graph (i.e all vertices in the group are connected). You probably only care about the "largest" groups (for example, if $\{x,y,z\}$ is a group then you don't care about the group $\{x,y\}$), which correspond to maximal cliques in the graph.

Thus, your problem amounts to listing all maximal cliques in this graph. Unfortunately, there can be exponentially many such maximal cliques so you won't be able to do this in polynomial time. The Wikipedia article I link to mentions a few sources and ways to do this either in asymptotically optimal time for the worst case or in time polynomial per maximal clique, which might be of interest if the graph happens to have relatively few maximal cliques.


Is there a difference between total-ordering consistency and linearizability? By total-ordering I mean the following definition[0]:

  Total Event Ordering: Controller replicas should process events in the
  same order and subsequently all controller application instances
  should reach the same internal state.

If my understanding is correct, there isn't any difference and the two words can be used interchangeably. However, I would like to make sure I am not mistaken.

In the case both concepts are different, could you stress their differences and perhaps provide an example? That would be very much appreciated!

Thank you,

[0] - https://www.cs.princeton.edu/~jrex/papers/ravana15.pdf

Total, FIFO and causal are all different sequential approaches for ordering the events. Now, consistency applies to all these types ordering and at different levels: local and global.

Sequential consistency requires that all of the operations appear to have executed atomically in some sequential order that is consistent with the order seen at a local level (individual process). This is similar to serializability used in database theory.
Linearizability is another type of consistency, which applies when this order must also preserve the global ordering of non overlapping operations.


Laws to simplify a boolean formula $$ (\neg A \wedge \neg C) \vee (\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C) $$
can simplify down to
$$ (\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C) $$
I've computed the truth tables for the two expressions, and they're the same. But I'm supposed to prove it without using truth tables. What law(s) am I supposed to use?

You have $(\neg A \wedge \neg C) \vee \text{some_big_expression} $ and you want to show that it's equivalent to $\text{some_big_expression} $.

Simplification rules won't necessarily lead you from the first expression to the second expression. There are systematic ways to test whether two expressions are equivalent, by applying De Morgan's laws in a certain way and other simplification rules (such as $\neg (\neg P) \longrightarrow P$) to transform a formula into equivalent formulas until you reach a disjunctive normal form (or other normal forms, if you apply the laws in a different way). But this doesn't directly get you from one expression to the other.

Another way to prove that two formulas are equivalent is to show that the first implies the second and the second implies the first. Here, it's obvious that
$\text{some_big_expression}$ implies $(\neg A \wedge \neg C) \vee \text{some_big_expression}$, so the difficulty is to prove the opposite implication: $(\neg A \wedge \neg C) \vee \text{some_big_expression}$ implies $\text{some_big_expression}$. Think about what this means: you want to prove that if $P$ or $Q$ holds then $Q$ holds — in other words, if you already know $Q$, then you don't need to prove $P$, it's already implied by $Q$. This is a consequence of two properties of disjunction, idempotency and monotonicity: if $Q \Rightarrow P$ then $(P \vee Q) \Rightarrow (P \vee P) \Rightarrow P$.

So what's left is to prove that $\neg A \wedge \neg C$ implies $(\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C)$. I'll let you finish. Hint: the right-hand side has both $B$ and $\neg B$, what can you say about these?

Second exercise: use De Morgan's laws to grind the first formula into the second one.


Application Ambiguity in Untyped Lambda Calculus So, untyped lambda calculus has the following formal grammar for its terms:

$$e::= x \mid \lambda x . e \mid e_1 e_2$$

Usually this is presented in some ML-esque language as (using de Bruijn indices)

data term = variable Nat | lambda term | apply term term

My question is: apply (variable Nat) term is syntactically valid, but the rator is just a free variable, isn't this an invalid expression? If not, what does it evaluate to?

You can't evaluate (x t), where x is free, since evaluation ($\beta$-reduction) is usually defined in terms of substitution, but here you have neither a bound variable nor a function body for $t$ to be substituted into.

A term that cannot take a further step is called a normal form.


Find height of deepest FULL level in binary tree Suppose I have a binary tree that is guaranteed to have at least one level that holds the maximum amount of nodes possible. I want to find the height of the deepest level that is full/holds the maximum amount of nodes possible. I have a function highestFull() that calls it's recursive version highestFull(Node* t) which is initially given the root. I cannot use any of the standard library functions.

How do I approach this problem? I am looking for the most intuitive solution, not the most clever. I found an answer here, but I cannot understand why it works. I really want to understand the thought process behind the solution.

How would you determine the answer if you were looking at a graphical representation of the tree? You would scan all the levels from the root downwards until you found one that isn't full.

Formally, that is a breadth-first search of the tree that stops whenever a node with less than two children is found. Since you are working on a tree rather than a generic graph, you may rewrite it as follows:

Let $Q$ be a new queue of nodes, initially containing only the root.
While $v$, the first element of $Q$, has two children $v_l$ and $v_r$, remove $v$ and enqueue both $v_l$ and $v_r$.


Expressing the condition as a set of linear constraints Express the condition "$x = 0$ if and only if $y = 0$" as a set of linear constraints, where $x,y$ are integers such that $ - 5 \le x \le 8$ and $0 \le y \le 1$

Let us instead translate $x=0 \leftrightarrow y=0$ into disjunctive normal form. We would get

$$ (x=0 \wedge y=0 ) \vee (x>0 \wedge y=1) \vee (x<0 \wedge y=1) $$

Each conjunction is a linear constraint.

In your solution you assumed that the constraint $y=1 \vee x=0$ is always true. In fact $y=1 \vee y=0$ is always true, since this is the domain of $y$.

If you kept this constraint, you would have eliminated solutions where $y=0$ and $x \not= 0$.

Another issue is with your interpretation of the constraints. The pair
$$
\begin{array}{c}
-M < x < 0\\
y=0
\end{array}
$$
is a set of two constraints not a single constraint, therefore it is satisfied by the following 19 pairs
$(-5,0),...,(8,0),(-5,1),...,(-1,1)$. The first 14 pairs clearly violate the condition $x=0 \leftrightarrow y=0$.


Deterministic processing on probabilistic input I've designed an algorithm, is which responsible to process some samples from normal distribution under aegis of some deterministic steps. In other words, the algorithm generate unique response to a unique set of the random set of input.

Now I am prone to plan a title for the corresponding paper and there is a noticeable ambiguity regarding the manner by which the algorithm could be addressed...

It is neither non-deterministic nor randomized and probabilistic. What is this algorithm type? Should I name that as typical deterministic?!...

Edit: This algorithm is supposed to be fed by a number of agent coordinates (are which random normal-driven integer numbers). It should colonize the agents into groups in a specialized manner. Thus, the input is probabilistic but both the algorithm process and the output are considerably deterministic.

The current idea regarding the title is:

Optimal Communication of Agents by the Probabilistic Colonization of the Robot Swarm

But that Probabilistic word does not sound so deserving...

How about ...

Optimal Communication of Agents under Randomized Spatial Distribution


Relationship between Independent Set and Vertex Cover Directly from Wikipedia, a set of vertices $X \subseteq V(G)$ of a graph $G$ is independent if and only if its complement $V(G) \setminus X$ is a vertex cover.

Does this imply that the complement of the independent set problem is the vertex cover problem?

Well, strictly speaking it's not the complement; co-VC is co-NP-complete whereas Independent Set is NP-complete.  If they were the same, we would know that co-NP was equal to NP, which we do not, and indeed most people believe they are not.

But an easy way of seeing that they are not the same if to consider $(K_4, 2)$, the complete graph on four vertices) which is neither a yes-instance of Vertex Cover nor of Independent Set.  Similarly, the instance $(K_2,1)$ is a yes-instance for both.

However, they are related in the following way.
A set of vertices $C \subseteq V(G)$ of a graph $G$ is a vertex cover if and only if $V(G) \setminus C$ is an independent set.  This is easy to see; for every endpoint of an edge, at least one vertex must be in $C$ for $C$ to be a vertex cover, hence not both endpoints of an edge are in $V(G) \setminus C$, so $V(G) \setminus C$ is an independent set.  This holds both directions.

So $(G,k)$ is a yes instance for Vertex Cover (a minimization problem) if and only if $(G,n-k)$ is a yes instance for Independent Set (a maximization problem).