Proof that Turing machines and computers have same power How do we prove that any logical circuit can be simulated by a Turing machine?

For example, we take a logical circuit $L$ that is made of gates and, or, and not. This circuit determines a problem, for example, whether the input is an even number. How can we prove that if a problem is decided  by a logical circuit, there is a Turing machine that can decide the problem?

In other words, how do we prove that a CPU is equal in power to a Turing machine? We should not forget that a Turing machine has infinitely many cells.

Turing machines and Boolean circuits cannot really be compared, since Turing machines handle inputs of arbitrary length, whereas Boolean circuits only handle inputs of fixed length.

Furthermore, Turing machines and CPUs corresponds to two different computation models. Turing machines access their memory by moving a head across a tape. In contrast, a CPU accesses its memory via random access. The abstraction corresponding to CPUs is the random-access machine.

If we want to compare the power of Turing machines and circuits, we need to put them into equal footing. One way to do this is to consider a sequence of circuits $C_0,C_1,C_2,\ldots$, one per input length. Such a sequence computes a language in the natural way: an input $x$ belongs to the language if $C_{|x|}$ returns True when given $x$ as input. This circuit model is much more powerful than Turing machines – indeed, it can compute any language, whereas Turing machines can only compute decidable languages.

What went wrong? Let us consider your example, of circuits for parity. The circuits computing parity for different lengths of input are very similar to one another; they seem to be made from a "mold", a set of instructions which can be translated to a circuit of arbitrary length. In contrast, the circuit model considered in the preceding paragraph specifies no such relation between the different circuits. When we add this constraint – that the different circuits follow a "blueprint" – we do get a model equivalent to Turing machines. What exactly constitutes a blueprint is a bit technical (one option is to have the circuits generated by a Turing machine), but the intuitive idea should be clear.

Circuits also come up when trying to understand resource-bounded computation, such as the complexity class $\mathsf{P}$ of languages which can be decided in polynomial time. It is known that any such language can be translated to a "uniform" family of circuits of polynomial size. In this way, the fact that the language can be decided efficiently is reflected by the size of circuits that compute it.


Data structure for partition of a set A partition of a set S is a separation of the set into an arbitrary number of non-empty, pairwise disjoint subsets whose union is exactly S. What manner of a data structure should be used to represent a partition of a set if the following methods need to be optimized:

moving an element from one part to another, possibly an entirely new one, and
iterating over the parts of the partition.

A naive way of prioritizing 1 would be a hash/tree/whatever mapping from set elements to "part labels", but iterating over the parts would require O(N) for first constructing the actual parts from the labels. 2 is naively prioritized as a hash/tree/whatever set of hash/tree/whatever sets, but then moving elements around, especially to new subsets, incurs that memory management overhead.

Is there a way to get the best of both worlds? The implementation I need is Python but I imagine this is a cross-language question.

I'm not familiar with the topic, so all I can do is give a few pointers.
Manipulating partitions of finite sets is known by several names:

union-find when you start with singletons and progressively merge sets;
partition refinement when you start with a single set and progressively split it;
union-split-find when sets can be both merged and split as in your case.

Katherine J. Lai's discusses the union-split-find problem and proposes an algorithm using B-trees that double as finger trees to represent each set. Each element is represented by a distinct integer; using consecutive values for elements that are likely to remain together is more efficient. To merge two sets, split them into non-overlapping intervals that are entirely contained in one of the sets, and join the pieces together. See her thesis for details.


Complement of context free language If a language X regular, then is the complement of X also a regular language? If yes, then thank you, else can you please explain why

Yes, the complement of a regular language is regular.
If $L$ is regular then there is a DFA accepting that language. In particular, its states can be classified as ACCEPTING states and non-ACCEPTING states. Just turn non-ACCEPTING states into ACCEPTING, and ACCEPTING states into non-ACCEPTING states and you will have a DFA accepting $\overline{L}$.


Difference between $O(n^2)$ and $O(m)$ for algorithms on graphs Given a graph $G$ directed with n nodes and m edges, if an algorithm solves a problem  $X$ on $G$ with a complexity $O(n^2)$, while an other algorithm solves same problem $X$ on $G$ but with complexity $O(m)$, what is the most efficient ?

Since $m \in \Theta(n^2)$ in the worst case, $O$-bounds don't tell you much. That is to say, just from these bounds alone, you can't say that $O(m)$ is better than $O(n^2)$ (and the reverse never holds for simple graphs).

However, if you have $\Theta$-bounds then $\Theta(m)$ is properly better than $\Theta(n^2)$ if $m \in o(n^2)$, i.e. you have sparse graphs.

Also, the usual limitations of $O$-worst-case analysis apply: you may actually be interested in typical-case behaviour, constant factors may matter to you, and you need efficiency for finite (small?) $n$.


Examples of undecidable problems whose intersection is decidable I know that given two problems are undecidable it does not follow that their intersection must be undecidable. For example, take a property of languages $P$ such that it is undecidable whether the language accepted by a given pushdown automaton $M$ has that property. Clearly $P$ and $\lnot P$ are undecidable (for a given $M$) but $P \cap \lnot P$ is trivially decidable (it is always false).

I wonder if there are any "real life" examples which do not make use of the "trick" above? When I say "real life" I do not necessarily mean problems which people come across in their day to day life, I mean examples where we do not take a problem and it's complement. It would be interesting (to me) if there are examples where the intersection is not trivially decidable.

So here is a example, which is probably not as nice as you wanted it to be, but less trivial than the one you have mentioned.

Let $L_1,L_2\subset \{a,b,c\}^*$ be two undecidable languages, and $L_3\subseteq \{a,b,c\}^*$ a decidable language. We define

\begin{align}
L_A&:=\{a\,w \mid w\in L_1\} \cup \{c\,w \mid w\in L_3\}, \\
L_B&:=\{b\,w \mid w\in L_2\} \cup \{c\,w \mid w\in L_3\} .\\
  \end{align}

Clearly, both $L_A$ and $L_B$ are not decidable, however their nonempty intersection
$$ L_A\cap L_B =\{c\,w \mid w\in L_3\}$$
is decidable.


Knapsack with a fixed number of weights Consider a special case of the knapsack problem in which all weights are integers, and the number of different weights is fixed. For example, the weight of every item is either 1k or 2k or 4k. There is one unit of each item.

The problem can be solved using dynamic programming. Suppose the knapsack capacity is $C$, and the most valuable item of weight $w$ has a value of $v_w$. Then, the maximum value of KNAPSACK($C$) is the maximum of the following three values:

KNAPSACK($v_1$,$C-1$), KNAPSACK($v_2$,$C-2$), KNAPSACK($v_4$,$C-4$).

Is there a more efficient algorithm? Particularly, is there a greedy algorithm for this problem?

I tried two greedy algorithms, but they fail already for weights 1 and 2. For example, suppose there are 3 items, with values 100, 99, 51 and weights 2, 1, 1:

If the capacity is 2, then the greedy algorithm that selects items by their value fails (it selects the 100 while the maximum is 99+51).
If the capacity is 3, then the greedy algorithm that selects items by their value/weight ratio fails (it selects the 99+51 while the maximum is 100+99).

However, this does not rule out the possibility that another greedy algorithm (sorting by some other criterion) can work. Is there a greedy algorithm for this problem? Alternatively, is there a proof that such an algorithm does not exist?

In your case that the sizes are only 1, 2 or 4, the answer is quite easy:

If the knapsack has an odd size, then you pick the most valuable item of size 1 and add it to the last slot.

If the remaining knapsack has a size that is an odd multiple of two, then you pick the most valuable item of size 2, or the two most valuable items of size 1, whichever is more valuable, and put them to the last slot of size 2.

Now the remaining knapsack has a size that is a multiple of 4. You pick the most valuable item of size 4, or the two most valuable items of size 2, or the four most valuable items of size 1, or the most valuable item of size 2 plus the two most valuable items of size 1.

With other sizes, say sizes 2, 3 and 5, things will be more difficult. However, you can sort the items of each size in descending order, and can solve this using dynamic programming.

I suppose the time will be polynomial for every fixed size of weights, with the polynomial depending on the weights. But you can sort the items of each weight in descending order in O (n log n), and if there are m different weights and the size of the knapsack is K, you find the best solution easily in mW steps.

If the weights and K are large, the number of possible sums of weights may be a lot smaller than K. For example if K = 1 billion and three weights >= 100 million, there will be less than 167 possible sums of weights < K.


Convert propositional logic formulas to mathematical constraints Brief introduction

In all boolean (or more generally mixed-integer) linear programs, constraints are represented as a matrix $A$, a support vector $b$  and is computed by $A^T x \leq b$, where $x$ is a boolean vector one wants to optimize in some way. Another way of formulating the problem is to say that one wants to select a set of items such that a bunch of logic formulas are satisfied while optimizing some function. In my setting, I have all the soon-to-be-constraints in a list of propositional logic formulas. So, to be able to compute and solve using some kind of ILP-solver, I need to convert all logic formulas into mathematical constraints.

Straight-forward conversion from logic formula constraints

The most straight-forward way to convert from a propositional logic formula into mathematical constraints is to first convert the formula into Conjunctive normal form (CNF for short) and then from the CNF create one constraint for each and-clause. For example, let $q$ be formulated as the logical formula $$q = (a \lor b) \rightarrow c$$, then $q$ is converted to CNF $$q_{cnf} = (c \lor \neg a) \wedge (c \lor \neg b)$$ Now, for each conjunction clause we will have one constraint and for each variable in each disjunction we'll set $(1-x)$ if a variable $x$ is negated and just $x$ otherwise:

$$
  (1-a)+c > 0 \wedge (1-b)+c > 0 \Rightarrow \\
  c-a > -1 \wedge c-b > -1 \Rightarrow \\
  c-a \geq 0 \wedge c-b \geq 0 \Rightarrow \\
  a-c \leq 0 \wedge b-c \leq 0
$$

which we'll represent by a matrix $A$ and a vector $b$

$$
A=
\begin{bmatrix}
    1 & 0 & -1 \\
    0 & 1 & -1
  \end{bmatrix}
$$
$$
b=
\begin{bmatrix}
    0 & 0
\end{bmatrix}
$$
where each column index in $A$ represents each variable of $a, b, c$, and we can now easily compute and solve for some optimization problem using all kinds of solvers.

Question

In the general case, a propositional logic formula is converted into many mathematical constraints. For some cases, the formula could be converted into just one constraint. For example, $a \wedge (b \lor c)$ can be represented in one line as $-2a - b - c \leq -3$ whereas $(a \wedge b) \lor c$ cannot be represented by one constraint.

Is there a method for determine if a formula can be represented as one constraint or not? And in the best case, is there even a method for converting into that one constraint if it exists or many otherwise?

Functions which can be described using a single constraint are known as halfspaces or linear threshold functions. They are also the functions computable using a single threshold gate.

Checking whether a function of this form exists is a linear programming problem: you look for a set of weights $w_1,\ldots,w_n,C$ such that if $f(x_1,\ldots,x_n) = 1$ then
$$ \sum_i w_i x_i \geq C + 1, $$
and if $f(x_1,\ldots,x_n) = -1$ then
$$ \sum_i w_i x_i \leq C - 1. $$

More efficient algorithms exist. For example, Maass and Turán gave a famous such algorithm in their paper "How fast can a threshold gate learn?".


Intuitive explanation of neutral / normal form in lambda calculus It is possible to distinguish Normal terms which don't contain beta redex as a sub-expression, from others like so

data WithBound a = Var | Other a

data Normal a
  = Neutral (Neutral a)
  | Abstract (Normal (WithBound a))

data Neutral a
  = Variable a
  | Apply (Neutral a) (Normal a)

Is there any intuitive explanation as to why this property would hold ?
It might be entirely self-evident somehow after you look at it long enough but it does not prompt straight out to me as of now.

I can reassure you that this property is not immediately self-evident. In trying to describe/enumerate the set of normal forms, the main observation required is the following:

Abstraction preserves normal forms: if $t$ is normal, than so is $\lambda x.t$.
Application does not preserve normal forms: if $t$ and $u$ are normal, $t\ u$ may contain a redex!

We want to characterize the normal forms for which we can not create redexes when performing applications. Obviously, this occurs iff $t$ is a $\lambda$-abstraction. In particular, we can take $u$ to be anything we want, so long as it is in normal form.

For $t$, we need either a variable or an application, itself already in normal form. This allows a convenient recursive definition for $t$, which we will call neutral:
$$t=x$$
or
$$t=t_1\ t_2$$
with $t_2$ any normal form, and $t_1\ t_2$ also in normal form, i.e. $t_1$ also a neutral term.

But this is exactly your definition of Neutral!

One can carry out this process further to characterize exactly the normalizing (resp. strongly normalizing) terms, if we furthermore allow weak head expansions.


What is the Certificate for Set Cover? Consider the set cover problem: given a collection of sets ${\cal U}$ whose elements come from $\{1, \ldots, m\}$ find the smallest number of sets in ${\cal U}$ whose union is all of $\{1, \ldots, m\}$. My question is: what would be a certificate for this problem? That is, if I wanted to convince someone that it is not possible to do this with fewer than $k$ sets, what information could I provide that would allow someone to verify that this is the case in polynomial time?

The set cover is not a decision problem, so it doesn't necessarily have a certificate.  Rather, it is an optimization problem.

To make it a problem in NP (a decision problem, with a certificate), you need to apply the standard trick to convert an optimization problem to a decision problem: introduce a budget.  Thus, the decision budget is: given a collection of sets and an integer $k$, determine whether there exists a subset of $\le k$ sets whose union is all of $\{1,\dots,m\}$.  That is a decision procedure, and does have a certificate: the subset of size $k$ is the certificate.

See also Optimization version of decision problems and standard textbooks.


Portfolio allocation with a few twists A similar question has been asked here, but this one is more complicated and has more constraints.

I'm trying to find an algorithm to solve the following (real-life) problem:

A customer has $M$ amount of money each month that he wants to invest according to her preferred asset allocation.
Example

60% stocks
20% bonds
20% REITs

She has a list of "favourite" financial instruments and a preferred allocation in each of the asset classes, e.g.:

Stocks: C (60%) and AAPL (40%)
Bonds: AGG (70%) and LQD (30%)
REITs: VNQI (100%)

Now, the algorithm would provide an investment advice (how many units and what financial instruments to buy) according to the following constraints:

Total sum of purchases with fees cannot exceed $M$ (amount of money).
Units are integer and indivisible, you can buy either one or two stocks but not 1.5. Since the customer ivests small(-ish) sums, this constraint becomes important. Example: $M$ is \$500 and AAPL is \$173 per unit!
Main goal is fee minimisation (again, since the sum invested is not large, fees become relatively large). Instruments have different fees that not flat-rate. E.g.: fees for buying C are "\$1 if transaction sum is <\$100, 0.30% otherwise", but for VNQI they're "\$10 if sum < \$2000, 0.40% otherwise".
Second goal is allocation that is approximately close to the "model allocation" above. Note that the model is concerned with asset classes, not individual instruments. That means the customer can buy only C or only AAPLto attain the desired 60% in Stocks. However, remember that there's also a preferred allocation within an asset class; if we decide not to buy C this month, then we'll need buy more of it next time to keep the stocks in balance.
Fee minimisation can be attained by limiting the number of transactions. That means we can decide to buy, e.g., C, AGG and VNQI only, and think about buying AAPL and LQD next month. We can go even further and decide not to buy a whole asset class at all if the first solution has fees that are too high (above some pre-determined limit). In that case we'll remember that decision and buy more of it next month.

Now, I've been thinking about this for some time; I had my CS lessons over fifteen years ago, so had to rack my brain :)
My first thought was of Bin packing problem. Nah. Doesn't really fit.
Then I remembered about Multi-dimensional unbounded knapsack. Again, not what I was looking for.
Considered Quadratic programming and Dantzig's simplex algorithm for linear programming. Not exactly fitting...

Maybe there is a special algorithm / special case for this kind of problem? Or shall I invent a new one? :)

I'd suggest using integer linear programming (ILP).  You need to buy an integer number of stocks, so you can use integer variables to represent the amount of each stock you buy.  ILP can express constraints (requirements that must be true).  The main limitation is that the objective function you are trying to minimize must be a linear function of the variables, but that can often be accomodated with auxiliary variables.  For instance, your rules about the fees for buying different stocks can be expressed with ILP.

You'll have to figure out how you want to quantify and formalize "allocation that is approximately close to the model", as currently that is rather vague.  Also note that anytime you say you have two goals, you aren't ready to formulate this as an optimization problem, because that leaves open how you plan to trade off the goals.  You need to identify a single objective function you want to minimize, which means you'll need to think how you want to combine fee minimization with approximate model allocation.  We can't tell you how to do that as that is a matter of what you want to achieve.  One way would be to sum up the absolute value of the deviations from the model, and require this to be no more than a certain maximum.  Another way would be to sum up the absolute value of the deviations, and add that to the objective function as an extra penalty.


How approximate sine using Taylor series I need to approximate the sine function without internal libraries. I used Taylor series in 0 to solve this, but my program works for some values, but for others awful results.
The program gets x value, unit (degrees or radians) and how many words we want use for the approximation.
For values like

1 rad, 5 words results are ok:
sin(1 pi) = 0.833333 Difference: 0.00813765;

sin(0.5 pi) = 0.479167 Difference: 0.000258872

But for values like 125.6 rad it returns 2.60145e+008 and C++ sin() function gives -0.0636631, so the result is completely unreal.

Also it doesn't work for values in degrees although I convert degrees on radians. E.g. sin(4.71239 pi) = 6.63667 and real result should be -1.
I completely don't have any idea why it doesn't work properly, could anyone tell me what could cause these problems?

#include <iostream>
#include <math.h>

#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif

using namespace std;

double degConverter(double);
void approximate(double, int, int);
int derivative(int);
double compareWithNorm(double, double);
double inline reductionFormula(double);

double inline degConverter(double x)
{
    return x / 180.0; //x * M_PI / 180.0    <-- the expression in comment gives wrong results in all situations?
}

void approximate(double x, int unit, int words)
{
    double result = 0;
    double xVal = 0;
    int factorial = 1;

    if (unit == 1)
    {
        xVal = x;
    }
    else if (unit == 0)
    {
        xVal = degConverter(x);
        x = xVal;
    }

    if (words > 1)
    {
        for (int i = 1; i < words; i++)
        {
            switch (i % 4)
            {
                case 1:
                    result += xVal / (double)factorial;
                break;

                case 3:
                    result -= xVal / (double)factorial;
                break;

            }
            xVal *= x;
            silnia *= i + 1;
        }
    }

    //Comparing with sin() function from math.h lib
    cout << "Difference between sin C++ and Taylor: " << compareWithNorm(x, result) << endl;
}

double compareWithNorm(double x, double result)
{
    double diff = 0;
    double pattern = sin(x);
    diff = pattern - result;
    if (diff < 0)
        diff *= -1;

    return diff;

}

double inline reductionFormula(double x)
{

    if (x > 2)
    {
        x = fmod(x, 2.0);
    }
    return x;
}

int main()
{
    double x;
    int unit = 1;
    int words = 1;

    cout << "Type x [degrees / rad]: ";
    cin >> x;
    cout << "\nType unit [deg = 0 / rad = 1]: ";
    cin >> unit;
    cout << "\nHow many words?: ";
    cin >> words;
    cout << endl;

    approximate(x, unit, words);

    return 0;
}

You use argument reduction. You know that sin (2kπ + x) = sin (x), so given an argument y, you calculate k = round (y / 2π), y' = y - 2kπ, and sin (y) = sin (y'), with y between -π and π.

You can also use sin (π + x) = - sin (x), sin (π/2 + x) = cos (x) to reduce the argument to sin (y') or cos (y') with -π/4 ≤ x ≤ π/4.

The reason why your Taylor series gives absurd results for large x is that you are adding and subtracting huge terms. Mathematically the series converges just fine, but if you have terms > $10^{20}$, these terms will have rounding errors so large that you cannot expect a good result. Reducing the argument to -π/4 ≤ x ≤ π/4 means you have much smaller terms. (Also see Pseudonym's answer how to get the argument reduction as precise as possible).

You are adding the terms of the Taylor series from the largest. Each addition has a rounding error, proportional in size to the result of the addition. So adding in this order each addition gives a large error. It is better to start with the smallest term. The two smallest terms are tiny, adding them gives a tiny rounding error.

And usually we don't actually use the Taylor series. The Taylor series has its largest error at the end of the range. You would use Chebyshev polynomials, which minimise the largest error over the whole interval. And since you don't want any errors at x = 0, you can write sin(x) = x - x * g(x) and minimise the relative error of g(x).


Sorting an array of length $n$ with $k$ distinct elements There is an integer array that contain $n$ numbers, in the array there are $k$ distinct elements up to $k = 50$.
Is it possible to sort this array in linear time, by using only comparisons?

I know that comparison sorts cannot perform better than $\mathcal O(n\log n)$, so maybe I have to show a sort function that sort this array in less than $\mathcal O(n\log n)$, and it will be a contradiction.

Consider quicksort with $w$ unique values, where the pivot is taken arbitrarily from the list. In the worst case the pivot will be an extrema (either the minimum or maximum of the list), and so the algorithm will recurse for $w-1$ and 1, and a list of 1 unique value is already sorted.

As the time complexity is linear, $O(n)$, for each pass, and the number of passes is in worst case the number of unique values, $O(w)$, then the time complexity is $O(nw)$, which for constant $w=50$, is $O(n)$


Is it possible to generate a better random number generator algorithm from an algorithm that use N computers with one that uses N+1 computers? Is it possible to generate a better random number generator algorithm from an algorithm that use N number of computers with an algorithm that uses N+1 number of computers? I use the word computer here, but I believe you can use the word processor instead as not all computers are single-processor computers although I am not sure if it makes any difference as the answer would be similar I think. The algorithm can be any algorithm, but for the sake of simplicity let's say the fastest one we know, and if you can't generalize for N, let's say N = 1.

The fastest random number algorithm that we know is
0

It is not very random, but it is very fast and therefore the best according to your definition. Maybe you need to rethink your definition. Maybe you should rethink the idea that there might be a “best” algorithm.


Relationship between Kleene Star of a subset of regular language and the regular language If $L(R_1) \subseteq L(R_2) \subseteq L(R_3)$ then $L(R_1)^* \subseteq L(R_2)^* \subseteq L(R_3)^*$. Does this also imply that $L(R_1)^* \subseteq L(R_3)$?

Of course not: Consider R1='a', R2='a|b', R3='a|b|c', for instance.


2-dimensional ranking of multiple arrays Given a fixed dimension $d$, say $d=2$ we want the following:
Input: $A_1\ldots A_m$: $m$ arrays of length $n$ of integers
Each input array $A_i$ must be a permutation of the numbers $1..n$, so in each array each number from $1$ to $n$ appears exactly once.
Output: For each tuple (pairs in the case $d=2$; triplets in the case of $d=3$ etc. In this example we'll use pairs) of numbers $(1,1),(1,2)\dots(n,n)$, we want a count for in how many input arrays the first number of the tuple is also the first to appear in the array (among the numbers of that tuple). The order in which the other numbers of the tuple appear in an array doesn't matter, as long as they come later than the first number of the tuple.

Question: Can this be done quicker than $O(mn^d)$ in the worst case?

Upper and lower bounds
The output is represented as a $d$-dimensional array of length $n$. Therefore a lower bound for the runtime complexity is $O(n^d)$.
The naive approach is to create $m$ mappings from each number to its index for each input array. Then for all $n^d$ tuples, walk through the $m$ mappings, yielding a runtime complexity upper bound of $O(dmn^d)$ and since $d$ is a constant this is $O(mn^d)$.
Examples
A = (1,2,3,4),        Output =  1 2 3 4
    (1,2,3,4),                  -------
    (1,2,3,4),     =>       1 | 4 4 4 4
    (1,2,3,4)               2 | 0 4 4 4
                            3 | 0 0 4 4
    d=2, m=4, n=4           4 | 0 0 0 4

=======================================

A = (4,3,2,1),         Output = 1 2 3 4
    (1,2,3,4),                  -------
    (1,2,3,4)      =>       1 | 3 2 2 2
                            2 | 1 3 2 2
    d=2, m=3, n=4           3 | 1 1 3 2
                            4 | 1 1 1 3

Application
While writing poker analysis software, I'm particularly interested in the case $d=3, m\approx 1250, n\approx 1250$. I estimate that the naive $O(mn^d)$ solution takes multiple hours but less than a day when using native Java arrays (no hashmaps etc) on a single thread.
$d$ stands for the number of players that are still active during a poker hand. Normal poker software handles the case $d=2$. Some high-end software handles the case $d=3$.
I'm interested in the case $d=2$, but then the naive approach is already quick enough in most situations. I'm mainly interested in the case $d=3$. I'm less (but still) interested in the case $d=4$ which is probably unfeasible and even less interested in greater values. I'm not interested in $d>10$. A poker table has 10 players max. The values of $m$ and $n$ do not increase/decrease with $d$.

Here is a solution quite simple to implement, that only improves the $d$ factor.
For the increasing series $[1, 2, .., n]$, get the tuple list of the coordinates to increase in your output array. For $d = 2$ and $n = 4$, this is $H=[(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)]$. Asymptotically (not exactly due to $(a, a)$ being always valid), there are $O(\frac{n^d}{d})$ terms in this list.
Initialize an output array $B$ of size $n^d$ to zeros.
Then, for each of the $m$ arrays $A$ and for each tuple $(a_0, a_1, ..., a_d)\in H$, increase $B[A[a_0], A[a_1], ..., A[a_d]]]$ by 1.
It achieves $O(\frac{m n^d}{d})$.
EDIT
For $d=3$, basically, both tuples $(0, 1, 2)$ and $(0, 2, 1)$ are in the coordinates list to increase. But if you want to use the knowledge that $B[a, b, c] = B[a, c, b]$, you have to keep only tuples non-decreasing after the 2nd integer. So here you leave $(0, 2, 1)$. Be careful to still keep $(a, b, b)$ tuples like $(0, 2, 2)$.
Then you will divide the number of terms in the list by about a factor $2(d-1)!$ for the general case).
At the very end, you have to add a $O(n^d)$ step to gather counts on $B[a, b, c]$ and $B[a, c, b]$. For every tuple $(a, b, c)$ with $b < c$,

$S = B[a, b, c] + B[a, c, b]$
$B[a, b, c] = S$
$B[a, c, b] = S$

This runs in $O(\frac{m n^d}{d!})$.


2D random walk. Should both dimensions be independent? My assignment is to compare several probability distributions in random walk algorithm. I'd like to analyse it in 2D linear space to make the concept more intuitive.

What is the correct approach in selecting consecutive positions of the particle? Do I choose both coordinates independently or the step length?

The usual 2D random walk goes one step in one of the cardinal directions (up, down, left, or right). If you rotate the plane by 45 degrees, you get a random walk which moves up or down and left or right on each step. So both these distributions are the same (up to scaling), at least for a fixed step size.


Estimating the bit operations using big O notation Using big- O  notation estimate in terms  of a simple function of $ n $ the number of  bit  operations required to compute $3^n$  in binary.
I need some help with the above question. The number of bit operations required to multiply two k- bit numbers is $O(k^2)$.
In the first step I am multiplying two 2-bit numbers, in the 2nd step a 4-bit and a 2-bit number and so on.
So the total bit operations will be I feel
$O(k^2) + O(k^2 * k) +.... + O(k^{n-1} * k)
\,\,with \,\, k \,= 2 $
How will the above sum be estimated as a function of n?

There are several problems. First, the time complexity of multiplying two k-bit numbers is much less than O(k^2). More like O(k log k). Since this is an important open research problem, you usually assume it is O(M(k)) for some function M and use that further.
Second, you are not multiplying two k bit numbers. You are multiplying one k-bit number by 3, which is done easily in O(k). This would get you a total of O(n^2).
Third, that’s not a clever method to calculate $3^n$. Much better is repeated squaring/multiplying. For example to calculate $3^{100}$: Start with 3, square, multiply by 3, square, square, square, multiply by 3, square, square. Since the number of bits starts small and doubles every time, this works in O(M(n)).


Combining multiple HMM models Is there any way to combine multiple Hidden Markov Models trained from different sets of data? For example, I want to detect the phases of a sequential activity. I collect two sets of data by using two types of sensors: accelerometer, and video stream. I create two HMM models from the accelerometer and video stream, respectively. To increate accuracy, can I combine the two models?

Yes.  Construct the product automaton.

The "product construction" is a standard construction from automata theory class (e.g., typically taught in the context of finite-state automata).  It can be applied to HMM's as well, and it will do exactly what you want.

For your example, the resulting HMM will have 9 states.  Each state in the resulting HMM will a pair $(s,t)$, where $s$ is a state of the accelerometer HMM and $t$ is a state of the video stream HMM.  Transitions between them and probabilities are derived in the obvious way.  For instance, if there is a possible transition $s \to s'$ in the accelerometer HMM and a possible transition $t \to t'$ in the video stream HMM, then the product HMM will have a transition $(s,t) \to (s',t')$ (and its probability will be the product of the probabilities of the underlying transitions).  The output distribution is obtained by multiplying probabilities: if $p(x|s)$ denotes the probability of outputting $x$ when in state $s$ in the accelerometer HMM, and $p(x|t)$ the probability of outputting $x$ when in state $t$ in the video stream HMM, then we use $p(x|(s,t)) = p(x|s) p(x|t)$ as the probability of outputting $x$ when in state $(s,t)$ in the product HMM.

This assumes that the internal states of the two HMM processes are independent.  That's something you'll need to verify yourself, to see whether the independence assumption seems reasonable in your particular application domain.


Prove that the language of unary not-prime numbers satisfies the Pumping Lemma Here is a question from Daniel I. A. Cohen's book Introduction to Computer Theory:

  Consider the language:

  $\quad \mathrm{PRIME}' = \{ a^n \mid n \text{ is not a prime} \} = \{ \varepsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots \}$

  Prove that $\mathrm{PRIME}'$ is non-regular.
  Prove, however, that $\mathrm{PRIME}'$ does satisfy the pumping lemma.

Part 1. is really easy to prove. I start my proof of part 2. like this:

We pick $m$ s.t. $m \geq 4$.
The opponent picks $w = a^{n^2}$, where $n$ is any prime number greater than m.

Now I don't know how to decompose $w$ into $xyz$. Any help would be appreciated.

Update: According to the answers below, $\mathrm{PRIME}'$ doesn't satisfy the Pumping Lemma we commonly talk about (requiring $|xy| \leq m$). I have checked the book at the library and found there are two versions of the Pumping Lemma in it. The weaker one, which clearly this question refers to, doesn't require a fixed pumping length.

Let $w \in \mathrm{PRIME}'$ with $|w| \geq 5$. Distinguish two cases.

$|w|$ is even -- in that case, choose $x = \varepsilon$, $y = aa$ and $z = a^{|w|-2}$. Then, for all $i\geq 0$, we have $|xy^iz|$ is even and greater than two, as $|z| \geq 3$, and therefore not prime; $xy^iz \in \mathrm{PRIME}'$.
$|w|$ is odd -- in this case, we can not verify the pumping property. This can be seen as follows.

We have

$\quad \forall m \geq 1.\, \exists n \geq m.\, \forall 1 < k \leq m.\, \gcd(k, n-k) = 1 \qquad (\star)$

that is for every assumed pumping length $m$, there is a longer word $a^n$ which you can not separate into $a^k$ and $a^{n-k}$ with $k \leq m$ (note that $k=1$ trivially violates the pumping property) so that $k$ and $n-k$ share a divisor. Therefore, we can invoke Dirichlet's theorem for every possible separation, which yields that there are (infinitely many) primes you get by $(n-k) + ik$. So we can't find a pumpable split of $a^n$, and thus the pumping property is violated for $a^n$, which is enough to "contradict" the lemma.

$(\star)$ can be shown by contradiction. Pick $n>m$ non-prime so that $n$ has no prime factor $\leq m$, e.g. $n = p^2$ for $p\geq m$ prime. Assume there was a $1<k\leq m$ so that some $1<d\leq k$ divided both $k$ and $n-k$, i.e. $k = id$ and $n-k = jd$ for some natural $i,j$. But then, $n = (i+j)d$, i.e. $d \leq m$ divides $n$, which contradicts the choice of $n$.


Showing that $n\log n - n$ is $\Omega(n)$ Prove that $n\log{n} − n$ is $\Omega(n)$.

I do know the answer:

$\log{n} ≥ 2, \forall n \ge 4$.

Thus, $n\log{n}−n\ge n ,\forall n\ge 4 \implies n \log n − n ∈ Ω(n)$.

But can someone please explain how  its done. where did $2$, $\forall n$ and $4$ came from.
Then how was $n, \forall n \ge 4$ added.

According to the definition of big Omega, in order to show that $n\log n - n = \Omega(n)$, we need to come up with $n_0$ and $c$ such that all $n \geq n_0$ satisfy $n\log n - n \ge cn$.

Let us assume that the logarithm is to base 2. When $n \geq 4$, we have $\log n \geq \log 4 = 2$, and so $n\log n - n \geq 2n - n = n$. Therefore we can take $n_0 = 4$ and $c = 1$ and satisfy the requirements for $n\log n - n = \Omega(n)$.

The choice of $4$ is arbitrary — any $n_0 > 2$ would work (for an appropriate value of $c$).


Finding row wise sum of transpose of hv-convex binary matrix I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m).

e.g. I get {4,3,2,2,1} in the input. It's the row wise sum of the following matrix:

    1 1 1 1
    1 1 1 0
    1 1 0 0
    1 1 0 0
    1 0 0 0

To solve the problem, I have to find the row-wise sum of it's transpose.

i.e. I need to calculate {5,4,2,1}

1 1 1 1 1
1 1 1 1 0
1 1 0 0 0
1 0 0 0 0

Can it be achieved in less than O(n*m)?

A non-increasing sequence of integers is known as a partition. The operation you are describing is known as conjugation. Given a partition $\lambda_1,\ldots,\lambda_n$, you can compute its conjugate $\lambda'_1,\ldots,\lambda'_m$ as follows:

Initialize a pointer $i$ at $n$.
Set $\lambda'_1 = i$.
Advance $i$ backwards until $\lambda_i \geq 2$.
Set $\lambda'_2 = i$.
Advance $i$ backwards until $\lambda_i \geq 3$.
Set $\lambda'_3 = i$.
...
Stop once $i = 1$.

As an example, here is how you apply this algorithm on $4,3,2,2,1$.
$$
\begin{align*}
&\begin{array}{ccccc}
4 & 3 & 2 & 2 & 1 \\
&&&& \uparrow \\
&&&& 5
\end{array} \\\hline
&\begin{array}{ccccc}
4 & 3 & 2 & 2 & 1 \\
&&& \uparrow \\
&&& 4
\end{array} \\\hline
&\begin{array}{ccccc}
4 & 3 & 2 & 2 & 1 \\
& \uparrow \\
& 2
\end{array} \\\hline
&\begin{array}{ccccc}
4 & 3 & 2 & 2 & 1 \\
\uparrow \\
1
\end{array}
\end{align*}
$$
It might happen that at some point $i$ doesn't advance at all. This is what happens if we apply this algorithm on $5,4,2,1$:
$$
\begin{align*}
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
&&& \uparrow \\
&&& 4
\end{array} \\\hline
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
&& \uparrow \\
&& 3
\end{array} \\\hline
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
& \uparrow \\
& 2
\end{array} \\\hline
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
& \uparrow \\
& 2
\end{array} \\\hline
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
\uparrow \\
1
\end{array}
\end{align*}
$$


Mathematical expression for the quantity that we are maximising in the stock buying and selling problem Problem Statement:
Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Here's the link to the problem.

I know the solution to this problem but what I'd like to know is how do I write the total profit, (i.e. the thing that we are trying to maximize,) as a mathematical expression? I tried the following (where $n$ is the length of the list):
$$\sum_{ \substack{1 \leq i,j \leq n \\ i\lt j}} (x_j - x_i)[i,j \text{ unique}] $$
But this would be wrong since it could include both $i = 1, j = 2$ and $i = 2, j = 3$, and we can't both buy and sell a stock on day 2. Also I had to resort to the Iversonian notation for this, and if possible, I'd like to avoid it.
I don't know if I should be needing two variables for the summation, since we only iterate through the list once for calculating the profit, but I couldn't do it in one variable.
PS: This is my first time posting here and I couldn't really decide on the tags for this problem. Pardon me if they are wrong, and let me know which ones to use and I'll update the question. :)

To write the profit as a mathematical expression, you need to set up a little more notation for the buys and sells. Let $x[1], \ldots, x[n]$ be the stock prices on days $1, \ldots, n$. For each buy and sell, let $b$ denote the day on which the stock is bought, and $s$ the day on which it is sold. The problem says that we must have $1 \leq b < s \leq n$. The profit from this single transaction is $P = x[s] - x[b]$.
However, the problem allows many buys and sells, say $(b_1, s_1), \ldots, (b_k, s_k)$ for some numbers which must satisfy $$1 \leq b_1 < s_1 < b_2 < s_2 < \cdots < b_k < s_k \leq n.$$
The total profit from these $k$ transactions is
$$ P = \sum_{i = 1}^k \left(x[b_i] - x[s_i]\right). $$
Of course the tricky part is that you don't know ahead of time what $k$ should be, so you're not only trying to optimise over the $b_i$ and $s_i$ variables, but also $k$.


Need help with recurrence relation and postcondition of a function I just wanted to make sure I'm on the right track regarding this.
Here's the function that I'm dealing with:
import math

def Mystery2(A, f, l):
    if f == l:
        return A[f]
    m = math.floor((f+l)/2)
    x = Mystery2(A, f, m)
    c = 0
    i = f
    while i <= l:
        if A[i] == x:
            c = c + 1
        i = i + 1
    if c > (l-f+1)/2:
        return x
    return Mystery2(A, m+1, l)

The precondition is given as: A is an array of integers, and $f$ and $l$ are integers $0 \leq f \leq l < len(A)$.
From what I can see by running the function, the postcondition appears to be that it outputs the element within f and l indices that occurs more than $ \frac{l-f+1}{2}$ times or A[l].
I'm not sure how to find a closed form for the recurrence relation representing the worst case runtime.
So far I figured that with $T(n)$ being the worst runtime of the function and $n = l-f$, $T(n)$ will be constant if $n = 0$ and $T(\left \lfloor \frac{n}{2} \rfloor \right) + T(\left \lceil \frac{n}{2} \right \rceil - 1) + n*c_1 + c$, if $n > 0$. I'm not sure how to convert this into a closed form.
Is it okay to simplify this into $T(\left \lfloor \frac{n}{2} \rfloor \right) + T(\left \lceil \frac{n}{2} \right \rceil) + n*c_1 + c$ for the purpose of comparing it to the master theorem?
Thanks in advance for any help

Without having checked if $T(n)$ is correct, you can find the closed form by:
$$T(n) = T(\lfloor\dfrac{n}{2}\rfloor) + T(\lceil\dfrac{n}{2}\rceil - 1) + n*c_1 + c$$
If n is odd, you can rewrite $T(n)$ as:
$$T(n) = T(\lfloor\dfrac{n}{2}\rfloor) + T(\lfloor\dfrac{n}{2}\rfloor) + n*c_1 + c = $$
$$T(n) = 2T(\lfloor\dfrac{n}{2}\rfloor) + n*c_1 + c $$
If you substitute $T(\lfloor\dfrac{n}{2}\rfloor)$ you get
$$T(n) = 2( 2T(\lfloor\dfrac{n}{4}\rfloor) + \dfrac{n}{2}*c_1 + c  ) + n*c_1 + c =$$
$$T(n) = 4T(\lfloor\dfrac{n}{4}\rfloor) + 2n*c_1 + 3c $$
If you substitute $T(\lfloor\dfrac{n}{4}\rfloor)$ you get
$$ T(n) = 4 (2T(\lfloor\dfrac{n}{8}\rfloor) + \dfrac{n}{4}*c_1 + c) + 2n*c_1 + 3c = $$
$$ T(n) = 8T(\lfloor\dfrac{n}{8}\rfloor) + 3n*c_1 + 7c$$
Now you can observe the pattern and see that after substituting $\dfrac{n}{2^{k-1}}$
$$ T(n) = 2^kT(\lfloor\dfrac{n}{2^k}\rfloor) + k*n*c_1 + (2^0 + 2^1 +...+ 2^k)c$$
Let $n = 2^k$
$$ T(n) = nT(1) + n*log_2n*c_1 + (2^0 + 2^1 +...+ n)c = $$
$$ T(n) = n + n*log_2n*c_1 + (2^n - 1)c = $$
$$ T(n) = n + n*log_2n*c_1 + 2^n*c - c = $$
So you have $O(2^n)$
Now if n is even, you have
$$T(n) = T(\dfrac{n}{2}) + T(\dfrac{n}{2} - 1) + n*c_1 + c $$
And you follow the same method as before (i.e., start by substituting n/2 and find the pattern after a few iterations).


Does $P/O(1)$ equal to $P$ if solver needs to consider smaller inputs? Suppose that $F$ is a problem such that for every $n$, there is a program of length $O(1)$, running in polynomial time to $n$, that solves $F$ correctly on all instances of size less than $n$. Can $F$ be solved in polynomial time? That is, does there exist a single polynomial time algorithm that solves $F$ on all instances?

Suppose that $F$ is a problem such that for every $n$, there is a program of length at most $C$, running in polynomial time, that solves $F$ correctly on all instances of size less than $n$.

Let $P_n$ be a program of length at most $C$, running in polynomial time, that solves $F$ correctly on all instances of size less than $n$. Since there are only finitely many programs of length at most $C$, there must be a single program $P$ that occurs infinitely often as $P_n$. This program solves $F$ in polynomial time for all instances.

If we change $O(1)$ to any bound $f(n) = \omega(1)$ computable in $\mathit{poly}(n)$ time, then we can easily construct undecidable problems which are computable in this model. We can assume that $f$ is monotone and has no jumps (otherwise take $g(n) = \min(\max(f(0),\ldots,f(n)),g(n-1)+1)$). For an undecidable $S \subseteq \mathbb{N}$, consider the following language:
$$
L = \{ x \in \{0,1\}^* : f(|x|) \in S \}.
$$
Since $f$ is monotone, if $|x| \leq n$ then $f(|x|) \leq f(n)$. Hence there is a program of length $f(n) + O(1)$ that solves $L$ correctly on inputs of length at most $n$. Conversely, since $f$ has no jumps, for each $m$ we can find a value $n$ such that $f(n) = m$, and this gives a computable reduction from $S$ to $L$, showing that $L$ is uncomputable.


boolean circuit to decide if there's a path of at most $k$ edges from $u$ to $v$ in graph $G$ Let an undirected graph and $k\in\mathbb{N}$. Prove that there's a circuit of depth $2$, size of $n^{O(k)}$ and unlimited fan-in, which gets $\langle G,v,u\rangle$ as an input and checks if there's a path from $u$ to $v$ of at most $k$ edges.

So I'm familiar with Warshall's algorithm and I think I should utilize it here. The problem is that it seems impossible to do that with a depth-$2$ circuit.

I'd be glad if you could direct me what to do.

Thanks

Since you are allowed an $n^{O(k)}$ size circuit, you could go over all possible $k$-length paths originating at $u$. The first level will contain $n^{O(k)}$ AND gates, one for every possible sequence of vertices $v_1=u,v_2,...,v_l=v$, for $l\le k$, and in the second level you input the results of the previous level to an OR gate.


What is an estimation of the Kolmogorov Complexity for the first N integers? I'm aware some ints have higher or lower Kolmogorov Complexities. For example, the number 5.41126806512 has a very low complexity as it can be expressed by 17/pi. I'm also aware that, though the KC varies depending on the expression language, it is always the same up to a given constant. So, I ask: is there a way to calculate an approximation of the KC for the first N ints?

No, there is no general algorithm to compute a close approximation to the Kolmogorov complexity of the sequence $1,2,\dots,n$.  Any candidate algorithm you come up with will have some inputs where it gives a bad answer (a poor approximation to the correct answer).

Denote by $[n]$ the binary encoding of the natural number $n$, and let $[[n]] = [1],[2],\ldots,[n]$ denote a comma-separated encoding of the sequence $1,\ldots,n$. It is not hard to check that $|K([n]) - K([[n]])| = O(1)$.  Since computing $K([n])$ is undecidable, it follows that computing a good approximation to $K([[n]])$ is also undecidable.

Furthermore, it is known that for "most" integers $n$, $K([n]) = \Theta(\log n)$. So for "most" integers $n$, $K([[n]]) = \Theta(\log n)$.


Choose $n$ out of $2n-1$ boxes containing at least half of all white balls and half of all black balls We are given $2n - 1$ boxes with a total of $B$ black and $W$ white balls. In the $i$-th, box there are $w_i$ white and $b_i$ black balls. It is required to choose $n$ boxes so that, the sum of the white balls is at least $W/2$, and the sum of black balls is at least $B/2$.
  Solve for $O(n\log{n})$.

What I am currently thinking is this:

Generate some hashtable to be able to track the boxes that we chose.
Sort the boxes by the quantity of the white (in increasing order) balls and chose the last $n$ balls every time keeping them in our hashtable.
Sort by the quantity of the black balls and do the same. Check every time to see if we already chose the box or not. Here comes the problem: Suppose we didn't. Then we can face a situation where we already have $n$ boxes that have in total at least $W/2$ white balls but at the same time, they have in total less than $B/2$ black balls. How can we overcome this problem?

We can't just switch the chosen boxes that have the least number of white balls with the one that have the maximum available number of black balls since the box with white balls can contain significant amount of black balls on its own.

Let $B^*, B_1, B_2, \dots, B_{2n-2}$ be the the bins sorted by the number of white balls, in non-increasing order (break ties arbitrarily). Notice that the first bin is called $B^*$.

Consider the two groups $G_E = \{ B^* \} \cup \{B_i \mid i \text{ is even} \}$ and $G_O = \{ B^* \} \cup \{B_i \mid i \text{ is odd} \}$.
Clearly $|G_E| = |G_O| = 1 + \frac{2n-2}{2} = n$.

Moreover, each of $G_E$ and $G_O$ contains at least $W/2$ white balls.
This is true since since for each bin not in $G_E$ (resp. $G_O$) the previous bin in the sorted order must be in $G_E$ (resp. $G_O$). That is, the total number of white balls in $G_E$ (resp. $G_O$) is at least as large as the number of white balls not in $G_E$ (resp. $G_O$).

Now, total the number of black balls in at least one group $G^* \in \{G_E, G_O\}$  must be at least $B/2$. This is easy to see since $\{G_E, G_O \setminus \{B^*\}\}$
is a partition of the set of bins, and hence the bins in at least one set of the partition (which is either $G_E$ or a subset of $G_O$) must contain at least half the black balls.


Programming languages and Model of computations I am learning about model of computation and I found this wikipedia entry that categorises and outlines various model of computation.
Now I want to know the programming languages that builds on these models.
I am aware that functional programming languages are built upon lambda calculus, and that imperative programming is more or less as a result of Turing machine model. But I do not know about the other models and if any programming language have been designed based on them.
Anyone knows if there are languages that builds on model of computation listed on the wikipedia entry?

Functional programming languages can often be thought of as built on the lambda calculus.
Imperative programming languages can often be thought of as built on the RAM (Random Access Machine) model of computation.
Some hardware description languages can be thought of as being built on the finite-state machine model, or on digital circuits.
Some declarative languages can be thought of as built on Datalog.
Some concurrent languages can be thought of as built on the actor model or on process calculi (e.g., CSP, the $\pi$-calculus, etc.).


Floor or Ceiling when getting results for N after doing Big O and Big Theta? I'm working on my data structures homework and proving Big O and Big Theta for a couple questions.  After choosing my values for C and getting to the end I'm left with the fraction 1/300 for $N_0$ for both Big O and Big Theta.  I understood from lecture that we actually take the ceiling of the fraction for Big O, making it 1.  My question is, do I also take the ceiling of Big Theta, or would it be the floor?  Since Big Theta is a lower-bound.

The reason we take floor or ceiling at all in this context is that the definition asks for an integer $N_0$. Now the definitions of big $O$ and big $\Theta$ are both of the form

  There exists a real constant $C > 0$ and an integer constant $N_0$ such that for all $n \geq N_0$, the following holds: ...

Let us denote what should hold by $P(n)$. If you have shown that $P(n)$ holds for all $n \geq N_0$, then it follows that it holds for all $n \geq \lceil N_0 \rceil$ as well, since if $n \geq \lceil N_0 \rceil$ then also $n \geq N_0$. It doesn't necessarily follow that $P(n)$ holds for all $n \geq \lfloor N_0 \rfloor$, since if $N_0$ is not an integer, $\lfloor N_0 \rfloor \not \geq N_0$.


Origins of misconception about using equality signs with Landau notation From "Misconception 1" from Søren S. Pedersen's blog, and as many have seen before, a major misconception in Big-O (and others) notation is to say a function is "equal" to Big-O of some other function:

$f(n) = O(g(n))$

where what we actually mean is this:

$f(n) \in O(g(n))$

What is the origin of this misconception? And why is this misconception perpetuated, even today?

$O$ is not only used in simple statements like $f(n)=O(g(n))$. It is also used to give error terms as in $f(n) = 14\, n\log n + O(n)$. The interpretation is still the same as @usul has described in his answer: There is a function $h \in O(n)$ so that $f(n) = 14\, n\log n + h(n)$.

Here, writing $f(n) \in 14\, n\log n + O(n)$ would emphasize the fact that there is a set involved in the equation, while the important point is that the leading term(s) are exactly as stated, while the $O$-term simply bounds the error. So in this context using $=$ is a sensible choice and I'd assume that it has been carried over to the case with zero leading terms in order to keep notation consistent.


Boolean function and real degree Let $f$ be a boolean function with minimum degree real polynomial representing it be of degree $d$.

Is there a relation between number of zeros $f$ or $1-f$ and degree $d$?

Exercise 12 (online version) in §1 of Ryan O'Donnell's Analysis of Boolean functions shows that all Fourier coefficients of a degree $d$ function are integer multiples of $2^{-d}$. In particular, the number of zeroes of $f$ is an integer multiple of $2^{n-d}$.

Moreover, for every integer $k \in \{0,\ldots,2^d\}$ there is a degree $d$ Boolean function having exactly $k2^{n-d}$ zeroes. This easily follows from the fact that a function on $d$ variables has degree at most $d$.


Does there exist any unrelativized separation between a quantum complexity class and a classical one? I'm familiar with results of relativized separation for BPP-BQP, BQP-PH and NPC-BQP. I'm also aware that while e.g. Factoring is not believed to be in BPP, it hasn't been proven and so we're not quite near proving BQP!=BPP.

My question is, do we have any certain, theoretical, unrelativized proof that quantum computers are "superior" to classical one on any specific problem - Where here, I define superior to include any sort of runtime complexity superiority, so e.g. a quadratic improvement would qualify in this regard.

I'd expect Grover's algorithm to qualify for this criterion - But despite being supposedly "obvious", I'm not sure if it's been proven that classical computers can't solve it in sqrt(n) time as well, in a non-black-box model (i.e. unrelativized).

Separations are known for constant-depth circuits. One recent result in this area is due to Bravyi, Gosset, and Koenig (see also the journal version in Science). Recent independent works by Bene Watts, Kothari, Schaeffer, and Tal, Coudron, Stark and Vidick, and Le Gall strengthened the hardness result for classical circuits from worst-case hardness to average-case hardness.


What techniques exist for energy-efficient computing and networking? I am currently reviewing the potentials of cloud computing regarding energy efficiency and green IT. In connection with this review I am having a look on techniques for increasing energy-efficiency in data centers (computing), hardware, networking and storage devices.

Specificially for computing/servers I have found already a few:

energy-aware scheduling techniques utilizing frequency and voltage scaling
virtualization to consolidate server resources
energy-saving hardware, e.g. ACPI, several processor techniques, especially for mobile devices etc.

However, for networking devices it is rather hard to get information about energy-saving technologies. I have read that people are thinking about new protocols and alternative routing methods to be able to switch off hardware if the network is under low load. Does anyone know of such examples?

Which other points should be added, either for networking or computing

I only know very little about this topic. But from the algorithmic point of view there is a very nice review article from Susanne Albers, which is probably a good starting point.


Show that term cons works by showing all beta reductions I'm new to functional programming.
So the terms cons appends an element to the front of the list. Where cons ≜ λx:λl:λc:λn: c x (l c n).
How should I go about proving that cons works correctly using beta reduction for a sample function. For example reducing cons 3[2,1] to [3,2,1]? Is there a formula like for the artihmetic operations in lambda? I'm a bit confused on how to approach this comapred to a arithmetic operation (i.e. addtion or multiplication).
Thanks.

$[3,2,1]$ is just syntactic sugar for $\mathsf{cons} \, 3 \, (\mathsf{cons} \, 2 \, (\mathsf{cons} \, 1 \, \mathsf{nil}))$. $[3,2,1]$ is $\mathsf{cons} \, 3 \, [2,1]$ by definition of the $[\ldots]$ notation.
Because $\mathsf{cons}$ is part of the definition of lists, it isn't meaningful to ask whether $\mathsf{cons}$ is correct on its own. The meaningful question is whether the definition of lists is correct as a whole. (More precisely, that's the definition of an encoding of lists in the lambda calculus.) Another way to look at it is that the goal isn't to prove that the definition of cons is correct, but that it's consistent with the rest of the definition of lists.
There are several, equivalent ways to define lists as an abstract type. Lists are an abstract type, defined by a number of functions and properties involving these functions. Lists are an abstract data type, so the functions can be classified into three groups: constructors (which build “bigger” lists from smaller lists and other stuff), destructors (which “break down” lists into smaller lists and other stuff) and other functions which can be built out of constructors and destructors. Any simple definition of lists uses two constructors: $\mathsf{nil}$ which is the empty list, and $\mathsf{cons}$ which takes two arguments, an element and a list, and returns a new list. The “most fundamental” (and easiest to reason with, but not easiest to understand) definition uses one destructor $\mathsf{case}$, and satisfies the following equations for any terms $f$, $g$, $h$, $t$ such that $t$ is a list:
$$
\begin{align}
\mathsf{case}\,\mathsf{nil}\,f\,g &= f \\
\mathsf{case}\,(\mathsf{cons}\,h\,t)\,f\,g &= g \, h \, t \\
\end{align}
$$
An encoding of this abstract type in the lambda calculus is the definition of three lambda terms $\mathsf{nil}$, $\mathsf{cons}$ and $\mathsf{case}$. Proving the correctness of this encoding means proving that the equation above holds.
Another, equivalent, definition of lists uses three destructors $\mathsf{empty}$, $\mathsf{head}$ and $\mathsf{tail}$ with the following equations (which presuppose the existence of booleans) for any terms $h$, $t$ such that $t$ is a list:
$$
\begin{align}
\mathsf{empty}\,\mathsf{nil} &= \mathsf{true} \\
\mathsf{empty}\,(\mathsf{cons}\,h\,t) &= \mathsf{false} \\
\mathsf{head}\,(\mathsf{cons}\,h\,t) &= h \\
\mathsf{tail}\,(\mathsf{cons}\,h\,t) &= t \\
\end{align}
$$
An encoding of this abstract type in the lambda calculus is the definition of five lambda terms $\mathsf{nil}$, $\mathsf{cons}$, $\mathsf{empty}$, $\mathsf{head}$ and $\mathsf{tail}$. Proving the correctness of this encoding means proving that the equation above holds.


If L is a non-regular language over {a}, are all Myhill-Nerode classes singletons? Is there a non-regular language over unary alphabet $\{a\}$ which has a Myhill-Nerode equivalence class that is not a singleton?

I'm guessing you are talking about Myhill-Nerode classes.

We can view $L$ as a subset of $\mathbb N$, since only the length of the word is important on $\{a\}$. Moreover two numbers $i,j$ are equivalent iff for any $n$, $i+n\in L$ iff $j+n\in L$.
Assume there are $i<j$ equivalent, and let $k=j-i$. Then for any $n$, we have $n\in L$ iff $n \bmod k\in L$, since you can replace $j$ by $i$ as many times as you want. This means $L$ is regular, because it depends only of the congruence classes modulo $k$.

So the answer to your question is Yes: if $L$ is nonregular, all classes are singletons.


Why is solving of diagonal quadratic equations over $\mathbb R$ and $\mathbb C$ in $P$? Let $\mathbb F\in\{\mathbb R, \mathbb C\}$ the field of real or complex numbers. Then [1, page 22 in the middle] claims that the following equation can easily be solved in deterministic polynomial time:
$$ \sum_{i=1}^n a_ix_i^2=b$$
with $a_i, b\in\mathbb F$. Some discussion suggests, that the algorithmical model assumed in the paper is that of a machine that can perform field operations in one step.

My question is: What is the algorithm? Is it multidimensional Newton? That would be weird because this algorithm only converges (in some cases) and does not give an exact solution. I'm quite unused to computational models over fields like the reals or complex numbers and maybe for someone who is more experienced this is cristal-clear?

[1] Agrawal & Saxena, On the complexity of cubic forms, 2006.

We assume that we are allowed to take square roots in $\mathbb{F}$.

$\mathbb{F} = \mathbb{C}$: If $b = 0$ then $x_1 = \cdots = x_n = 0$ is a solution. If $b \neq 0$ and $a_1 = \cdots = a_n = 0$ then there is no solution. Otherwise, let $a_i \neq 0$, and then a solution is $x_i = \sqrt{b/a_i}$ and $x_j = 0$ for $j \neq i$.

$\mathbb{F} = \mathbb{R}$: If $b = 0$ then $x_1 = \cdots = x_n = 0$ is a solution. Otherwise, without loss of generality assume that $b > 0$ (otherwise, multiply all of $b,a_1,\ldots,a_n$ by $-1$). If $a_i \leq 0$ for all $i$ there is no solution. Otherwise, let $a_i > 0$, and then a solution is $x_i = \sqrt{b/a_i}$ and $x_j = 0$ for $j \neq i$.


how is data in a tree stored in memory? I am not so familiar with trees.

How is a tree stored in memory? what is the data structure type used for storing it?

As a string?linked list? stack (!)?

Or is there some kind of data storage model for trees?

Usually it's stored as an adjacency list. Which is basically a linked list for every single node. So the linked list of a node u contains every node v such that (u,v) is a valid edge of the tree.

The adjacency list of this tree would be:

 1 ->
 3 -> 1, 4
 4 ->
 5 -> 3, 8
 7 ->
 8 -> 7, 10
10 ->

It can also be stored using an adjacency matrix. But that's used when the nodes of the tree are less (since it requires more memory). Adjacency list is better for sparse graphs.


Does "$\forall x\in L, \sigma(\neg x)=\neg \sigma(x)$" hold given that $\sigma(F)\equiv F$ for a CNF formula $F$ built on a set $L$ of literals? Suppose we have a CNF formula $F$ built on the set of literals $L=\{x_1,\neg x_1,\cdots,x_n,\neg x_n\}$ where each variable is used in at least one clause of $F$. Consider a permutation $\sigma$ of $L$ such that $\sigma(F)$ is logically equivalent to $F$ i.e. $\sigma(F)\equiv F$.

Does it hold that $\forall x\in L, \sigma(\neg x)=\neg \sigma(x)$ ?

I tried to find a counter example without success.

No.  Suppose $F$ is the formula

$$(x_1 \lor x_2) \land (\neg x_1 \lor x_2) \land (x_1 \lor \neg x_2) \land (\neg x_1 \lor \neg x_2) \land (x_1 \lor \neg x_1) \land (x_2 \lor \neg x_2),$$

and consider the permutation $\sigma$ such that $\sigma(x_1)=x_2$, $\sigma(x_2)=\neg x_1$, $\sigma(\neg x_1)=x_1$, and $\sigma(\neg x_2)=\neg x_2$.

Then $\sigma(F) \equiv F$, but $\sigma(\neg x_1) \ne \neg \sigma(x_1)$.


Is the type inference here really complicated? There's a question on SO asking why in Java the right type doesn't get picked in a concrete case. I know that Java can't do it in such "complicated" cases, but I'm asking myself WHY?

The (for simplicity slightly modified) line failing to compile is

Map<String, Number> m = ImmutableMap.builder().build();

and the methods are defined as1

class ImmutableMap {
    public static <K1, V1> Builder<K1, V1> builder() {...}
    ...
}

class Builder<K2, V2> {
    public ImmutableMap<K2, V2> build() {...}
    ...
}

The solution K1=K2=String and V1=V2=Number is obvious to everyone but the compiler. There are 4 variables here and I can see 4 trivial equations, so what's the problem with type inference here?

1I simplified the code piece from Guava for this example and numbered the type variables to make it (hopefully) clearer.

This is a common limitation of type inferencing and it has to do with the distinction between parameters and results of a function. Generally type inferencing is done strictly with the parameters passed to a function. Consider just the expression:

ImmutableMap.builder().build();

This has to be a valid expression due to how the language works. This means the type inferencing has to work from this expression alone. There is of course nothing in this expression which reveals what type you are expecting, thus it cannot compile (the type of the expression is not known).

It really isn't a question of how complicated the inferencing is, but rather a question of the fundamental structure of the language. It is possible to design a language where the return type becomes an implicit parameter to a function. However, this starts to create a loop in the typing logic in languages where variables can be auto-type (like C++).

The reason this happens is because of how the syntax trees for such languages are built (this may be only in theory as the compiler may not match exactly). When you have an expression like the above you have a tree that might look kind something like this:

- Assignment
    - LValue: Map<String, Number> m
    - RValue: FunctionCall(
          FunctionCall( ImmutableMap, builder ),
          build
      )

In such languages the "RValue" is essentially an expression -- where expressons are something that resolves to a value. These are processed on their own, and thus limited to the variables and sub-expressions which occur in them. Type inferencing doesn't usually go up tree, thus the FunctionCall has no knowledge it is part of the Assignment tree and thus no knowledge of the "LValue" (what it is being assigned to).

This is the traditional way to process languages (it even applies to formal languages like lambda calculus). Languages don't have to work this way, but there it is the most commonly understood way parsing works. You can certainly make a syntax tree which forwards type information in an assignment, but that leads to the pitfall I mentioned if the "LValue" is auto-typed. If you attempt to allow both sides to infere their type you start entering a constraint based typed system (which again, is possible and I have worked on one before).

One practical way of doing this in some languages is to pass the return variables by reference (which isn't really possible in Java). In C++ I often do this where the function requires its return type. Instead of doing:

var = someFunc(...);

I'll do:

someFunc( var, ... );

And this allows the type of "var" to be known by the function (in this case for template resolution).


Manipulating Adjacency matrix I have created an adjacency matrix which looks something like  this

    A   B   C   D   E   F   G   H   I
A   0   0   0   0   0   0   0   0   0
B   1   0   0   0   0   0   0   0   0
C   1   0   0   0   0   0   0   0   0
D   0   0   0   0   0   0   0   0   0
E   1   1   0   1   0   0   0   0   0
F   1   1   1   1   1   0   0   0   0
G   0   0   1   1   0   0   0   0   0
H   0   1   0   0   0   0   1   0   0
I   1   1   0   0   0   1   0   0   0

I am trying to manipulate this matrix such that an indirect link between two alphabet will replace the direct link. e.g. In the graph, C is connected to A and F is connected to both A and C (among others) and I is connected to both A and F. How do I go about removing the direct connections such as A and F, A and I since there are indirect connection between (C to A and F to C, C to A and F to C and I to F).

I tried using loop but it seems like more the indirect connection, the number of loop required increases as well. What type of algorithm should I use for this type of problem? Would adjacency list be a better alternative?

If I understand you correctly, one solution to your problem would be to compute a spanning forest. A spanning forest of a graph is a smallest possible (in terms of number of edges) graph such that there's a path between two vertices in the forest if, and only if, there's a path between them in the original graph.


How do learn the most important nodes in a tree? I have a list of 20000 words and how often they appeared in a set of 500 newspaper articles.  I am trying to build a stemmer which chops off suffuxes from each words, so walked, walking, walks are the same word.

In English, the Porter Stemmer is a rule-based system where you repeatedly chop off suffixes:

    CONNECTIONS
    CONNECTION
    CONNECT

I am concerned if I do this for my collection of Spanish words and articles, I may not have a complete list of rules or it may be prone to other forms of error.  So I had proposed to learn the suffixes.

Right now, I just count the appearances of each suffixed up to 4 letters.  Here is the result the most common last letter in my vocabulary list:

 u'a': 58189
 u'd': 3183
 u'e': 62971
 u'i': 1725
 u'l': 26374
 u'n': 37823
 u'o': 46786
 u'r': 16833
 u's': 57396
 u'u': 2639
 u'y': 2212
 u'z': 1968
 u'\xe1': 1813
 u'\xf3': 6722

The last letters a and o are obvious things to stem since they indicate masculine and feminine.  However o could also be the 1st person singular of a verb.  a could be the 3rd person singular.

e and s are also obvious choices to stem.  Let's look at the last 4 letters:

 u'ados': 1826,
 u'ales': 1633,
 u'ando': 1291,
 u'ante': 1062,
 u'aron': 1027,
 u'ci\xf3n': 5355,
 u'ente': 3084,
 u'ento': 1690,
 u'erto': 1061,
 u'idad': 1749,
 u'ncia': 1362,
 u'ntes': 1511,
 u'ones': 2845,
 u'ores': 1050,
 u'si\xf3n': 1127

These are very common Spanish suffixes, appearing more than 1000 times in my corpus.  Should I stem them?

How do I choose a data set which handles the suffixes of different sizes and decides which ones are the most "significant" ?

The first thing you need to consider is that stemming rules are language-specific - a stemmer for the English language will not work for Spanish.

That being said, there is already an implementation which you can use, it's called Snowball and it already has a Spanish stemmer you can use.

The only thing you need to figure out is how you want to install and use it - how you feed it the raw data and what you want to do with the output (store it somewhere, run post-processing on it etc.). There's no point in trying to reinvent the wheel. I've used Snowball and successfully written a Romanian stemmer back in the day (about seven years ago) and I must warn you it's not easy to do it from scratch even when you have all the tools (I had Snowball and the stemmer Dana Cojocaru wrote back then, but I wanted to do it on my own).

Best of luck in your endeavors!


Which one is the correct way to change functional notation while solving recurrence relation? In CLRS 3rd edition P. No 86, the relation

  $T(2^{n}) = 2T(2^{n/2}) + n$

is changed to

  $S(n) = 2S(n/2) + n$

My first question is, why we can change any recurrence relation like this? And,  how will the following relation

  $T(2^{n}) = T(2^{n-1}) + 1$

be changed? Which change is correct?

  $S(n) = S(n/2) + 1$

or

  $S(n) = S(n-1) + 1$

"Why we can change any recurrence relation like this?"

Answer: by the definition of function. This is about pure algebra.

Let me explain slowly and clearly. (To someone who just learned the definition of function, I should probably explain much slower with more explanation regarding the definition of domain, range, correspondence, change of dumb variables etc. To someone with a master degree in math, there is really nothing needed to explain. The speed of explanation below is somewhat arbitrarily in-between, since I do not know your level. If you think some stuff is too obvious to you, just skip it. Otherwise, comment below to tell me which part is still puzzling to you.)

Suppose we have a function, $T:\Bbb N\to\Bbb N$ defined by $T(2^{n}) = 2T(2^{n/2}) + n$. Let us define a new function, $S: \Bbb N\to\Bbb N$ by $s(m) = T(2^m)$, that is, $s(1) = T(2)$, $s(2) = T(4)$, $s(3) = T(8)$, etc. Since $m$ is an independent variable, we can also substitute $m/2$ for $m$ to obtain $s(m/2)=T(2^{m/2})$. So we will have,
$$s(m) = T(2^m) = 2T(2^{m/2}) + m = 2s(m/2) + m $$

  how will the following relation $T(2^{n}) = T(2^{n-1}) + 1$ be changed? Which change is correct?  $S(n) = S(n/2) + 1$ or $S(n) = S(n-1) + 1$?

If we define function $S: \Bbb Z\to\Bbb Z$ by $S(m) = T(m)$, i.e., $S$ is the same function as $T$, then we have, for any $n\in\Bbb Z$ that is a power of 2, i.e., $n=2^m$ for some $m$,
$$S(n) = S(2^m) = T(2^m) = T(2^{m-1}) + 1 = S(2^{m-1}) + 1 = S(2^m/2)+1 =S(n/2)+1. $$

On the other hand, if we define function $S: \Bbb Z\to\Bbb Z$ by $S(m) = T(2^m)$, then substituting $m-1$ for $m$, we have $S(m-1)=T(2^{m-1})$. So,
$$S(m) = T(2^m) = T(2^{m-1}) + 1 = S(m-1) + 1$$

In summary, either one of $S(n) = S(n/2) + 1$ and $S(n) = S(n-1) + 1$ can be correct. Which one is correct depends on how you define $S$. Once you have write down the definition of $S$, it will be clear which one is correct and which one is wrong. In other words, you have to specify what is $S$ first.


What is co-something? What does the notation co- mean when prefixing co-NP, co-RE (recursively enumerable), or co-CE (computably enumerable) ?

Often, in mathematical terminology, the prefix co- refers to a dual in some sense. For complexity and computability classes, the prefix co- has a fixed meaning: if X is a class of decision problems, then co-X is the class of problems whose complement is in X. That is, if the problem “does this object have the property $P$” is in X, then the problem “does this object have the property $\neg P$?” is in co-X.

For example, RE is the class of semi-decidable problems, that is, problems for which there is a Turing machine that can verify a positive answer. Co-RE is the class of problems for which there is a Turing machine that can verify a negative answer. A well-known problem that is in RE but not in co-RE is the halting problem (intuitively, you can verify that a Turing machine halts by running it to completion, but if the machine runs forever, you'll never be sure).

NP is the class of problems for which a solution can be verified in polynomial time; equivalently, NP is the class of problems that can be solved by a non-deterministic Turing machine in polynomial time. Co-NP is the class of problems for which the absence of a solution can be proved in polynomial time. It is not known whether $\text{NP} = \text{co-NP}$.


How is memory address applied to address pins in RAM chips I'm reading this book about assembly however I got stuck on one part, I can't seem to comprehend how memory address is 'applied' to the address pins

This is the image from the book

What I know here is the data pin applies voltage on the memory cell's input or output pin. And for the select pin the book explained that a binary code address is applied to the address pins, I imagined this part where there is only 1 address pin and 'something' is encoding the address to it, however looking at the diagram there are a lot of address pins for a few memory locations and they are connected to each other.

So my question here is how is the address "applied" to the address pins?
Which part of the chip applies the address to the address pings because the book only said "You apply this address to the address pins"

btw, the book is titled "Assembly Language Step-by-Step - Programming with Linux 3rd edition" in case somebody who might've read it before can explain it to me.. Thanks in advance!

Actually those 4 dots mean repeat. This means there are $2^{20} = 0x0FFFFF = 1,048,576$ memory cells, each with a line from the decoder. A few too many to draw them all.

Each of the lines from the decoder to a cell is an enable line. If not enabled the memory cell will do nothing (and have any output lines set to the data bus high impedance). If enabled the memory cell will read and write as you would expect.


Linear Bounded Automaton that accepts all strings I'm currently reading Sipser's Introduction to the Theory of Computation, and I'm reading up about linear bounded automata, now we know from Rice's Theorem that whether a TM can accept all strings in a given alphabet is undecidable, I was wondering if the same could apply to linear bounded automata, if not, how would one go about proving the undecidability of such a problem (or its decidabilty?). Thanks in advance.

For Turing machines another problem is also undecidable: whether it accepts any string at all. This is already undecidable for LBA. Basically the proof is by oberving that we can replace a TM accepting string $w$ by a LBA accepting the `trace of the computation' by the TM on $w$. The verification of the trace of the computation does not need more space than the computation itself, and thus can be verified by a LBA.

The question whether a device accepts all strings is already undecidable on a lower level of the Chomsky hierarchy, the context-free languages (CF grammars,or pushdown automata).


Is the fastest solution for one NP-Complete problem the fastest solution for all NP-complete problems? This answer seems incorrect to me:
Which NP-Complete problem has the fastest known algorithm?
The fastest solution for one NP-Complete problem should be the fastest solution for all NP-Complete problems.
Why?
Can any NP-complete problem be reduced to any other NP-Complete problem in polynomial time?
So, finding some super-optimal exponential time solution, $O(1.27k + nk)$, should be able to be applied to all NP-Complete problems. In other words, the most optimal solution is the same for all NP-Complete problems.

A polynomial-time reduction only needs to preserve the size of the problem up to a polynomial upper bound (which is implied by the time constraint).
As an example, suppose you have two NP-complete problems and $A \le_p B$, the reduction blows up the instance size from $n$ to $n^2$, and $B$ admits an algorithm with running time $ 2^\sqrt{n}$. This only induces an algorithm for $A$ with a running time of $2^{\sqrt{n^2}}=2^n$.


What is the name of the tree data structure where node weight equals the sum of all descendant nodes' weights? What is the name of the tree data structure where node weight equals the sum of all descendant nodes' weights?

Example:

      15
    /    \
   10     5
  /  \   / \
 2    8 1   4

It is called a SumTree. A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left subtree and right subtree. An empty tree is SumTree and sum of an empty tree can be considered as 0. A leaf node is also considered as SumTree.


Why there is no FPTAS for multiple knapsack problem for two knapsacks unless P=NP? The multiple knapsack problem (MKP) is defined in "A PTAS for the Multiple Knapsack Problem" as:

Instance: A pair $(B, S)$ where $B$ is a set of $m$ knapsacks and $S$ is a set of $n$ items. Each bin $j\in B$ has a capacity $c(j)$, and each item has a size $s(i)$ and a profit $p(i)$.
Objective: Find a subset $U\subseteq S$ of maximum profit such that $U$ has a feasible packing in $B$.

To prove that there is no FPTAS for MKP, the authors reduce partition problem (PP) to MKP with $m=2$ as follows:

  Given an instance of PP, $a_{1},\ldots,a_{2n}$. We set $c(1)=c(2)=\frac{1}{2}\sum_{i=1}^{2n}a_i$. We have $2n$ items, one for each number in the PP: the size of item $i$ is $s(i)=a_i$ and the profit is $p(i)=1$. If the PP has a solution, the profit of an optimum solution to the corresponding MKP is $2n$; otherwise it is at most $2n-1$.

However, I do not understand why the created instance of MKP is hard. I mean we have a set of $2n$ items where each item $i$ has size $s(i)=a_i$ and a profit $p(i)=1$. Also, we have $2$ knapsacks with identical capacity $c(1)=c(2)=\frac{1}{2}\sum_{i=1}^{2n}a_i$. We would like to maximize the number of assigned items to the two knapsacks such that the capacity of each knapsack is respected. Why we could not do the following?

Sort the items in increasing order of their sizes;
Pick an arbitrary knapsack, say $1$;
Fill it with items until its capacity is attained; and
Repeat 2. and 3. for knapsack $2$.

Sure I am missing something here but I do not know where.

There is no guarantee that the packing algorithm you suggested will lead to an optimal packing. Say you have two knapsacks of capacity 5, and objects of size 1, 2, 3 and 4. An optimal packing would be putting 1 and 4 into knapsack 1, and 2 and 3 into the other knapsack (switching the indexes on the knapsacks would also be another alternative solution and this is a further complication). The greedy algorithm you have given would not result in this packing.


How does one change the probability bounds in probabilistic complexity classes without changing the class? I see this theorem whose proof is not clear to me :

"Let $L \subseteq \{0,1\}^*$ be a language and suppose that there exists a polynomial time PTM M such that for every $x \in \{0,1\}^*$ and $Pr[ M(x) = L(x) ] \geq 1/2 + \vert x \vert ^{-c}$ Then for every constant $d >0$ there exists a polynomial-time PTM M' such that for every $x \in \{0,1\}^*$, $Pr[M(x)=L(x)] \geq 1 - 2^{-\vert x \vert ^d}$"

Even if I assume this above theorem how does this help convert the $2/3$ probability guarantee in the definition of BPP , RP and coRP into $1-2^{-\vert x \vert ^d }$ without changing the class?
I understand that the above theorem is proven by doing a $8\vert x \vert ^{2c +d}$ iterations of the PTM's run and then taking the majority vote and somehow Chernoff bound helps get the exact numbers. But I can't understand the intermediate argument. It would be helpful if someone can help fill in!

Suppose that $\Pr[M(x) = L(x)] \geq 1/2 + \epsilon$. Run $M$ repeatedly $m$ times (for $m$ odd), and take the majority vote. Let $x_i$ be the indicator for the event that the $i$th run of $M$ gives the correct solution. The success probability of the majority vote algorithm is
$$
\Pr[x_1+\cdots+x_m > m/2] \geq \Pr[\operatorname{Bin}(m,1/2+\epsilon)>m/2].
$$
At this point you apply the Chernoff–Hoeffding bound. You take it from here.


Optimal partitioning of n-tuples Motivation

Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into solving the problem but I'm still unsatisfied with my solution.

Problem formulation

You are given a list of unique sets $X_1,\dots,X_n$, each containing four integers.  You are also given an integer $k$.  The goal is to partition the sets into $k$ groups, so that every group has between $0.8n/k$ and $1.2n/k$ sets, in a way that minimizes the number of different integers in each group.  Formally, the goal is to find a function $f:\{1,\dots,n\} \to \{1,\dots,k\}$ that minimizes

$$\Phi(f) = \sum_j \left|\bigcup_{i \in f^{-1}(j)} X_i\right|.$$

Example

If instead of sets of four integers we considered sets of two integers, we could give the following example: for the sets

{1, 2}, {2, 3}, {1, 3}, {3, 4}, {4, 5}, {3, 5}

the optimal partitioning for $k=2$ would be {1, 2}, {2, 3}, {1, 3} and {3, 4}, {4, 5}, {3, 5} with unique elements $|\{1, 2, 3\}|=3$, $|\{3, 4, 5\}|=3$ and $\Phi = 6$.

My attempts so far

So far I've attempted to solve this problem by modeling it as a graph partitioning problem and using KaHIP library to do the computation. I thought of two methods of how to model this problem as a graph.

Each set is a vertex, and we have an edge between two vertices if they share an integer. The number of shared integers determines the weight of the edge. The graph partitioning tool then directly yields some solution to our problem.
Each unique integer that occurs in any set is a vertex, and we put an edge between two integers if they are both contained in the same set. The number of such cases determines the weight of the edge. Having the integers partitioned like this we can assign each set a partition of some of its integers. Resulting partitions can be too large, but that can be resolved by applying the first approach to these now relatively small partitions.

The first model in my case turned out to be very space-consuming. I have approximately 2 millions of these sets and the first model produced over 74M edges. The second approach helps a great deal and yields results of similar quality.

The problem is that neither of these models is the exact model of my original problem. Notably, the number of cut edges will not correspond with the number of duplicated integers across partitions. Can you think of a better graph model or an altogether different approach to this problem that would yield better results?

You might start from an initial solution computed using one of your two models, and then apply local search: consider any movement of one set from a group to another, and apply it if it does not violate the group constraints and it improves $\Phi$.

Local search is a common approach in graph partitioning, thus it is probably already a part of what KaHIP is doing, but even if it is, you would now do it with the correct measure, $\Phi$, not its surrogate, so the outcome is likely to be improved.


Relation between Hamming distances of columns and rows You're given a $0-1$ $n\times n$ matrix such that for every distinct columns $C_i$ and $C_j$, $d_H(C_i,C_j)\gt 2t$ for some $t$. What could be said about the Hamming distances of the rows? It it true for instance that there are two distinct rows $R_k$ and $R_l$ that satisfy $d_H(R_k,R_l)\lt n-t$?

The condition on the columns implies that $2t < n$. Suppose that the condition on the rows is not satisfied. The rows therefore form a code of minimal distance at least $n-t > n/2$ of size $n$. The Plotkin bound implies that unless $n-t$ is extremely close to $n/2$, such a code cannot exist. If $t$ is very close to $n/2$, however, the columns form a code of minimal distance close to $n$, which is again ruled out by the Plotkin bound (except perhaps for very small $n$).

I'll let you fill up the details and check for which $n$ this argument works.


Paths between tuples, MSV, decision trees I'm reading about Multiset Size Verification Problem and in the following paper - http://www.skynet.ie/~sos/mapviewer/docs/Voronoi_Diagram_Notes_2.pdf - I got stuck just on the first lemma. However, since my concrete problem is rather specific, I'll describe it as self-contained, so that no background in terms of what MSV really is will be needed (but I encourage you to check it :)).

Fix natural $k, n$ such that $k \le n$.
Let $$ Y = \{ (z_1, z_2, \ldots, z_n) \in \mathbb{R}^n :  |\{ z_1, z_2, \ldots, z_n \}| = k \} $$
Next, let $$ T = \{ (z_1, z_2, \ldots, z_n) \in \mathbb{R}^n : \{z_1, z_2, \ldots, z_k \} = \{1, 2, \ldots, k \} \  \text{and} \ z_i \in \{1, 2, \ldots, k \} \ for \ i \in \{ k+1, \ldots, n \} \} $$
In the paper that I linked to, they claim that for any distinct $a, b \in T$, on any continuous path from $a$ to $b$ we must encounter a point $p$ that is outside $Y$, i.e. $p \in \mathbb{R}^n - Y$. Apparently, it is not hard to see that, but I have a big difficulty proving it formally.

I wasn't sure whether to ask this question on Math community, or here, since the problem itself is purely mathematical. It's closely related to CS, though.

Consider any path from $a \in T$ to $b \in T$ inside $Y$. Let $t$ be the first time in which the first $k$ coordinates are not distinct. Prior to time $t$, for each $1 \leq i \leq k$, all coordinates in $j \in \{k+1,\ldots,n\}$ such that $a_j = a_i$ must keep satisfying this relation along the path, since otherwise there will be more than $k$ distinct values. Therefore at the point $t$, there will be fewer than $k$ distinct values. We conclude that the first $k$ coordinates always remain distinct, and that they determine the rest of the vector. In particular, the values in the first $k$ coordinates can't cross each other: if $a_i < b_i$ and $a_j > b_j$ then the intermediate value theorem shows that at some point $x$ along the path, $x_i = x_j$. We conclude that $a_1,\ldots,a_k = b_1,\ldots,b_k$. Since the first $k$ coordinates determine the rest, in fact $a = b$.


How to explain/understand brackets of applicative functor [[f u1... un]]? I am reading article about Applicative Abstract Categorial Grammars http://okmij.org/ftp/gengo/applicative-symantics/AACG.pdf and this article uses brackets [[...]] for action on terms inside applicative functors. These brackets are introduced and somehow explained in "Functional Pearl: Applicative programming with effects" http://strictlypositive.org/IdiomLite.pdf. I understand what applicative functor is and what what is functor generally (both in category theory and Haskell) but I still can not understand the meaning and value of these brackets. I understand the sentence idiomatic expression [[f x y]] means ηf * ηx * y, or, alternatively, map (f x) y - that means that [[F(tau)]] is sitting inside brackets, but I can not understand the difference between F(tau) and [[F(tau)]] in brackets (see page 4 of AACG article about context and notation). Also - brackets are not always used with 3 arguments, sometimes there are even on or none arguments!

Do those brackets have meaning, explanation and use in Haskell world? Any explanation - rigorous or not, associative and free-style of not is really appreciated.

http://learnyouahaskell.com/functors-applicative-functors-and-monoids contains example:

pure (+) <*> Just 3 <*> Just 5

Its fine, but what benefit can we get by applying brackets [[]] around this expression, what additional meaning such application created?

In it's simplest, original form, $[\![f\ x \ y]\!]$ just means $\eta(f)\circledast x \circledast y$ where $\circledast$ is what Haskell calls <*> and $\eta$ is what Haskell calls pure. Of course, this is only type correct if $x$, and $y$ have types like $\mathcal{F}(\dots)$ where $\mathcal{F}$ is an applicative functor. If they don't, we can be a bit smarter and automatically use $\eta$/pure to "lift" them to that type. From there, the translation can simply be $[\![f\ x_1\dots x_n]\!]\leadsto [\![f]\!]_1\circledast [\![x_1]\!]_1\circledast\cdots\circledast [\![x_n]\!]_1$ where $[\![e]\!]_1$ is either $e$ or $\eta(e)$ depending on the type of $e$. More systematically, $[\![e\ x]\!]\leadsto [\![e]\!]\circledast [\![x]\!]_1$ where $[\![e]\!] = [\![e]\!]_1$ when $e$ is not an application. You can easily imagine a variation that recursively applies the transformation.

The idiom brackets are just for convenience. The example you show of an applicative expression would become [[3 + 5]] using idiom brackets which is quite a bit shorter and more readable than pure (+) <*> pure 3 <*> pure 5 (which is in this case just pure (3 + 5) and thus is a fairly trivial case).

I have no idea what you mean by [[F(tau)]]. Idiom brackets don't apply to types.

There's a quasi-quoter that implements a notation similar to idiom brackets. Idiom brackets are also implemented by the Strathclyde Haskell Enhancement (SHE) which is made by the person who originally introduced the notation and author of that Functional Pearl, Conor McBride.


Grammar for square numbers in unary I have to write a grammar for the following language:
$$\{1^{n^2} \mid n\geq 1 \}$$
I am having trouble figuring out the production rules. I was thinking of using the fact that $n^2$ can be written as the sum of first $n$ odd numbers but couldn't proceed any further.

Let $B$ stand for the beginning marker, $A$ stands for a single 1 to be added later, $D$'s are copier markers and $E$ be the end marker. $F$, $G$, $I$, $H$ markers are used to properly generate all $A$'s. The following is not the most efficient grammar, but it will do.

Context free grammar rules:

$S \rightarrow BAFUE\ |\ \epsilon$
$U \rightarrow UD \ | \ D$

Non-contracting grammar rules:

$FD \rightarrow DG$
$AD \rightarrow D1A$
$1D \rightarrow D1$
$A1 \rightarrow 1A$
$BD \rightarrow BH$
$H1 \rightarrow 1H$
$HA\rightarrow AI$
$IA\rightarrow AI$
$IG \rightarrow AAF$

Now some non non-contracting rules:

$FE \rightarrow E$
$B \rightarrow \epsilon$
$AE \rightarrow E$
$E \rightarrow \epsilon$

Though this grammar has four non non-contracting rules, I have left them as it is, to help understanding. With a little effort we can convert it into a non-contracting grammar and then to a context-sensitive-grammar.

$IG \rightarrow AAF$ is the important rule, every time it adds two extra $AA$'s to be later substituted by 1's.


Confusion in Reducibility In Sipser's Theory of Computation book, it is stated while reducing ATM to REGULARTM

  We let R be a TM that decides REGULARTM and construct TM S to
  decide ATM. Then S works in the following manner.

S = “On input , where M is a TM and w is a string:

Construct the following TM M2.

M2 = “On input x:

If x has the form 0n1n, accept .
If x does not have this form, run M on input w and
accept if M accepts w.”

Run R on input < M2>
If R accepts, accept ; if R rejects, reject .”`

My question is, shouldn't M2 reject x of the form 0n1n?

Here, M2 hasn't been designed to accept Regular Languages. It has been designed to be used as argument of R. As per assumption that R can decide REGULARTM, R is free to reject M2 if the case arises. Remember, decidability includes both acceptance and rejection.

Update:
As per definition, R will accept only if argument TM accepts regular language. And, it will reject if argument TM accepts non-regular language. The setup of M2 harnesses this rejection property of R. If R hasn't rejected (as it can decide, it'll accept), it means point 2 of M2 was in action (which makes M accept w creating contradiction).


Traveling Salesman: how to use a lower bound? Let me preface this question by giving some helpful background material.

I'm trying to solve the traveling salesman problem using branch and bound. Concretely, for a partial solution, I'm using the solution the algorithm would attain by making greedy choices as an upper bound, and comparing this bound to the current best solution. If the bound attained using this heuristic is better than the cost of the best known solution, we continue exploring the partial solution. Otherwise, we prune and discard. Note that the greedy solution attained is always valid.

The above link mentions a method for finding a global lower bound. This is fairly intuitive: for each node, we add to the bound the sum of the two minimum cost edges to other nodes (representing the cheapest in/out edges, if you will) and divide by two to avoid double counting. The solution implied by this global bound is almost never a valid solution but instead gives a hard limit on the lowest cost we could ever hope to attain.

Here's how I'm currently trying to calculate a local lower bound (a lower bound for a partial solution) with cost $C(S)$.

Set bound to the current accumulated cost, $C(S)$
For each unvisited node, add to bound the sum of the two least cost edges, making sure that the edges selected don't lead to a node already visited
return bound/2

Here's my question: How is the above solution different from the greedy bound? Maybe a better lower bound would be to add to bound the sum of the two least cost edges, paying no attention to whether these edges lead to nodes already visited. Also, how do I actually use this bound to prune the search space? Do I compare the local lower bound computed for a partial solution with the global lower bound, pruning if $L(S) < GL$ or if $L(S) > C(B)$, or if $L(S) > L(B)$? (here $GL$ corresponds to the global lower bound; $L(S)$ computes the local lower bound on a partial solution; $C(B)$ represents the trip cost on the best known solution; $L(B)$ is the lower bound on the best solution). Also, how will $L(S)$ ever be less than the global lower bound (i.e. an infeasible solution) if we only ever use (valid) edges to cities we haven't yet visited?

Comments and suggestions on using this lower bound as well as its efficacy would be very much appreciated. Thank you.

You want a bound that depends upon the partial choices made so far.  So, I suggest you compute a bound that is based upon (1) the sum of the edges in the part you've chosen already, plus (2) a greedy bound for the remaining unvisited nodes (for each node, sum of the two least cost edges, divided by two); or something like this.  This will be different from the greedy bound applied to the entire graph, because of part (1).


Maximum one-to-many matching Let $G = (X+Y,E)$ be a bipartite graph and $k\geq 1$ an integer. A maximum $k$-matching is a subset of $E$ in which each vertex of $X$ is adjacent to at most $k$ edges and each vertex of $Y$ is adjacent to at most $1$ edge.
A maximum-cardinality $k$-matching can be found by the following algorithm:

Create $k$ copies of each vertex $x\in X$, such that each copy is adjacent to all neighbors of $x$ in $Y$.
Find a maximum matching in the resulting graph.

Its run-time complexity for a graph with $n$ vertices and $m$ edges, using the Hopcroft-Karp algorithm, is $O(k m\sqrt{k n}) =O(k^{3/2}\cdot m\sqrt{n})$.
I am interested in the following alternative algorithm:

Repeat $k$ times:

Find a maximum matching in $G$.
Remove the matched vertices of $Y$ from the graph.

Its run-time complexity is $O(k \cdot m\sqrt{n})$.
But does this algorithm always find a maximum $k$-matching?

No. Here is a counterexample: $X=\{a,b\}, Y=\{c,d,e,f\}, E=\{ac, ad, ae, be, bf\}, k=2$. The first iteration of your algorithm could choose $\{ae,bf\}$ (in particular, the edge $ae$), preventing a solution from being found even though one does exist: $\{ac, ad, be, bf\}$.