Why isn't a binary counter used for generating $k$-combinations? I have been looking at algorithms that allow you to generate $k$-combinations of a given string.

My question is that why isn't the algorithm used to generate power sets used to generate the combinations of a given string? That is, we can just use a binary counter of length $n$ with $k$ ones set to select $k$ elements from a length $n$ string. The method is very simple.

I mean, the power set can represent all $k$-combinations of the input. So why use complex algorithms like the ones described here (e.g., Gray codes)?

For concreteness, suppose you have a string $S$ of length $n = 10$. You want to generate all $k$-combinations of $S$ for some $k$, say $k = 3$. When you use a binary counter (using $n$ bits), you go through $2^n = 2^{10} = 1024$ values, corresponding to all possible subsets. On the other hand, there are only ${10 \choose 3} = 120$ possible 3-combinations choosable from $S$. So wouldn't it be nice if you could only perform 120 steps instead of 1024? I encourage you to play around with larger numbers, and consider how quickly these numbers actually grow.

There might also be other reasons to consider e.g., Gray codes. Some algorithms have particular properties that might be crucial for certain applications. For instance, we might want that there's exactly one change between two adjacent combinations, or so on.


Binary string satisfying several constraints I'm trying to solve this problem, but without success.

Problem: You're given a binary string where some of the bits are replaced by ?. You're also given several intervals [$l_i$, $r_i$] ($l_i < r_i$). Find a binary string S with ? replaced by 0 or 1, such that in each interval [$l$, $r$], s[$l..r$] includes both 0 and 1.
Example:
Given the string 00?11 and the interval [2, 3], the string 00111 satisfies the requirements, as S[2..3]=01 include both 0 and 1.
However, the string 00?11 and the intervals [2, 3] and [3, 4] cannot be solved, as the ? would have to be both 0 and 1.
The bounds are |S|,Q<=1e5

I tried using greedy, but it's giving wrong answer for this case: 0??0, [1, 3], [2, 3] and [3, 4], as the greedy algorithm would try 0??0 -> 01?0 -> 0100 -> fail, yet there exists a solution (0010).
I tried removing completely overlapping intervals (such as [1, 3] and [2, 3]), but there're other cases I found that fails. What would be a correct solution?
Thanks.

There are 4 types of intervals:

Intervals containing both $0$ and $1$ (e.g. 00?11?). Such intervals are already satisfied, and we simply ignore them.

Intervals which can't be satisfied: either of length 1 (e.g. 0, ?), or contain only 0's or 1's (e.g. 000, 111). If such an interval exists, report "no solutions".

Intervals which consist only of 0's or only of 1's and have a single ? (e.g. 00?0, 1?). For such intervals, we know what ? must be - so we just set ?, satisfying the interval, and ignore the interval from now on.

Intervals which have more than one ?. We'll talk about them later.

The first phase of the algorithm is to get rid of Types 1, 2, 3. Note that when we satisfy an interval of Type 3, other intervals can change their Type.
while (true) {
    Remove all intervals of Type 1
    Check that there are no intervals of Type 2
    if (there exists an interval of Type 3) {
        Satisfy and remove this interval
    } else {
        break
    }
}

As a result, only intervals of Type 4 remain. Each such interval has two ?. In particular, it covers two consecutive remaining ?'s. Therefore, it suffices to assign to the remaining ?'s values 0, 1, 0, 1, 0, 1, ..., from left to right.

Now, the efficient algorithm for the first phase. We process all intervals in increasing order of their right ends.
We maintain a set of intervals $T_4$ (initially empty) of currently encountered Type 4 intervals, sorted by their left ends.
For each new interval, depending on their type, we do the following:

Type 1: Ignore it

Type 2: Return "no solutions"

Type 4: Add an interval into $T_4$.

Type 3: Satisfy it. Now we look into the rightmost interval $I$ in $T_4$ (i.e. with the largest left end). If it changed its type, remove it from $T_4$ and process it again (i.e. check its type and apply the corresponding action from this list). Otherwise do nothing: since $I$ didn't change its type, other intervals in $T_4$ also won't change their type.
Indeed, let $I'$ be another interval from $T_4$. If $I \subseteq I'$, we are fine (if $I$ has two ?, then $I'$, which contains $I$, also has them). Let $i$ be the position of the fixed ?. If $i > right(I')$, then we are fine. Otherwise, we have $i \le right(I') < right(I)$. But note that there are no ? between $right(I')$ and $right(I)$: otherwise, the currently processed interval wouldn't be Type 3, since it has at least two ?'s. Therefore, $I \cap I'$ has at least two ?'s, and therefore, $I'$ too.

While processing Type 3, we find the rightmost interval $I$ in $T_4$ until $T_4$ is empty or $I$ didn't change its type. Simply put, we remove intervals from $S$ while there are intervals which change their type.


In how many steps Euclidean Algorithm will find the GCD for two integers I'm trying to solve this problem for big numbers (up to $10^9$). Namely, let's define $$GCD(a,b) = GCD(a-b, b)$$

We define GCD as function that returns greates common divisor of two numbers.

In case if $b > a$ we swap the values of $b$ and $a$. Now I want to count the number of steps when either $a$ or $b$ will be equal to $0$.

Example

$$a = 4, b = 17\\GCD(17, 4) = GCD(4,13)\\GCD(13,4) = GCD(4, 9)\\GCD(9,4)=GCD(5,4)\\GCD(5,4) = GCD(4, 1)\\GCD(4,1) = GCD(1,3)\\GCD(3,1) = GCD(1,2)\\GCD(2,1) = GCD(1,1)\\GCD(1,1) == GCD(0,1)$$

We have total of 8 steps, however for big values those numbers are growing super fast.

What I tried

I know that this is solvable with Euclidean algorithm for finding GCD, but the faster variant of Euclidean variant is $GCD(a,b) = GCD(b, a \text{ mod } b)$, and for this variant the number of steps is less that $\log_{10}max(a,b)$. But for this variant the number of steps is big numbers, so I think that it can be only calculated with math steps.

It can be observed that the product $ab$ drops by a factor of at least two for each iteration.

Prior to each iteration, we have the pair $(a, b)$ such that $a < b$, which is replaced by the pair $(r, a)$ at the end of each iteration in preperation for the next, where $r = b \bmod a$. We then have $r < a$ and $a + r ≤ b$. Hence, $b ≥ a + r > 2r$. So, $ar < \frac{1}{2}ab$.

Supposing it takes N steps to compute $gcd(a, b)$ using the Euclidean algorithm, we then have $ar ≤ \frac{ab}{2^N}$ after N steps. It follows that $ab ≥ 2^N$.

Hence, $N ≤ \log_2 ab = \log_2 a + \log_2 b$.

Therefore, the number of steps it takes to compute $gcd(a, b)$ using the Euclidean algorithm is at most $\log_2 a + \log_2 b$.

Furthermore, on Wikipedia, you can observe that the worst case is $N ≤ 5 \log_{10} a$, i.e. five times the number of (base-10) digits of $min(a, b) = a$, where $(a, b)$ is a pair of consecutive Fibonacci numbers. This relationship is useful because $gcd(F_{n+1}, F_{n+2}) = 1$ (i.e. all consecutive Fibonacci numbers are coprime).

Given these upper-bounds, the asymptotic computational complexity of the Euclidean algorithm can be expressed using Big-O notation as $\mathcal{O}(\log b)$.

Since,

$$\mathcal{O}(\log b) = \mathcal{O}(\log_2 a + \log_2 b) = \mathcal{O}(5\log_{10} a)$$

where $b ≥ a$.


How to construct a random error-correcting code (its generator matrix) according to the code parameters? I need to construct a random code which corrects T errors, has R check bits and has N maximum bits in the transmitting word.

I have researched the topic and found a few theorems about the bounds (The Varshamov-Gilbert bound, for instance). Neither of them suggests an algorithm of how to construct the code.

How do I build the random code with the specified parameters? I assume the algorithm should be probabilistic, but I'm not certain.

Look at Reed–Solomon codes. They are MDS codes, and AFAIK, MDS codes are most efficient codes that operates on independent blocks of bits.

If you need to support only erasures, there is simple to describe algorithm - consider input words as values of some polynomial at points 0..n-1, and compute (using a Galois Field) values of the same polynomial at points n..n+m-1 - it will be possible to restore polynomial coefficients from any n survived values.

If you can read Russian, I wrote more about erasure-only codes at ReedSolomonFFT-ru.md.


Coalescing by register allocation I have a rough idea of what coalescing in terms of memory access by threads is, but now, when learning about compilers, the term coalescing also appears when talking about register allocation.

In my book, it is just briefly mentioned, that coalescing for register allocation is just merging nodes from the graph (I assume the nodes of the graph show the variables that can be stored in a register).

Can someone explain a bit more thoroughly what coalescing in this sphere means?

In this context, "coalescing" means eliminating variable-to-variable move operations in the register allocator by allocating those two variables to the same location, typically the same register.

It may not be obvious why you'd do this in the register allocator, as opposed to in an earlier optimisation like constant folding. The reason is that code generation might introduce loads and stores for convenience or optimisation purposes.

The way that register allocation is often presented, you generate an assignment of "variables" to "locations", where a location could be a register or spilled. That's a good mathematical model of the problem, but it's a bit more complicated than this in practice.

Look at live range splitting as one example. This is an optimisation where a variable is not held in the same place for its lifetime ("spilling" can be thought of as a special case). As a concrete example, consider the case of two nested loops with a variable that is used a lot in the inner loop:

x <- something();
for (outer loop) {
    some_computation();
    for (inner loop) {
        some_other_computation_involving(x);
    }
}
use(x);

It seems like we probably want to store x in a register in the inner loop, but we may not want to store it in a register in the outer loop, because that would tie up a register during some_computation. On the other hand, there may be enough registers to keep x in a register, depending on how allocation for some_computation works out.

One solution is to split the range of variable x into two:

x1 <- something();
for (outer loop) {
    some_computation();
    x2 <- x1;
    for (inner loop) {
        some_other_computation_involving(x2);
    }
    x1 <- x2;
}
use(x1);

That introduces two variable-to-variable moves. If we allocate x1 and x2 to different locations, we are essentially spilling x for some of its lifetime. But using a coalescing-aware allocator, we have the chance that the spill may never happen if the moves are coalesced.

Another interesting case is that of special-purpose registers and calling conventions. Suppose, for example, you are calling a function:

x <- f(p(), q());

We will also suppose that the calling convention for this architecture requires the first argument for the call to f to be in register r1 and the second argument to be in register r2. One way to do this is to generate code like this:

t1 <- p()
r2 <- q()
r1 <- t1
call f

Again we have introduced a variable-to-variable move. A coalescing-aware register allocator can then decide whether to "spill" t1 or to generate it directly in r1:

r1 <- p()
r2 <- q()
call f

I use the word "spill" advisedly here because it might also be appropriate it to "spill" it to another register:

r3 <- p()
r2 <- q()
r1 <- r3
call f

Since r1 plays an important role in the calling convention, it may be needed for computing q().

Callee-save/caller-save registers can also be implemented using this mechanism.


Perturbing a Markov chain to be closer to a target stationary distribution Suppose we are a given a Markov chain $A_0 \in \mathbb{R}^{n \times n}$ and a desired stationary probability vector $\pi_0 \in \mathbb{R}^n$. I would like to find a Markov chain that is as close as possible to $A_0$ and whose stationary probability is as close as possible to $\pi_0$. For example, I would like to solve

$$ \min_{{\rm stochastic}~ A} ||A-A_0||_F + ||\pi(A)-\pi_0||_2$$

Is this doable in polynomial time? For example, for any fixed $\epsilon > 0$, can I find something $\epsilon$-close to the optimal solution in time polynomial in $n$? If not, what sort of approximation guarantees can we obtain for this?

I am pretty flexible on the problem statement; ultimately, the solution will be validated based on performance on a particular application. So if the problem is solvable by replacing the $2$- and Frobenius norms with something else, or via formalizing the problem in some other way, that would also be perfect.

You could use gradient descent.  It is possible to compute the gradient of the objective function $\varphi(A)$ in terms of $A$, i.e., the derivative of the objective function with respect to each entry of the matrix $A$. Then you could apply gradient descent.

In particular, let $\varphi(A) = \|A-A_0\|_F + \|\pi(A) - \pi_0\|_2$ denote your objective function.  Applying gradient descent to this objective function requires us to be able to compute $\nabla \varphi(A)$, i.e., the derivative ${\partial \over \partial A_{ij}} \varphi(A)$ of the objective function with respect to each individual entry $A_{ij}$ of the matrix $A$.  Let me explain how to do that.

One approach is to approximate the gradient numerically, i.e., to compute the gradient $\nabla \varphi(A)$, perturb each element of $A$ by a small amount of measure how much $\varphi(A)$ changes.  This might be fast enough if the matrix dimensions are sufficiently small, and it has the benefit of being easy to code.  However, it will scale poorly in practice for large matrices, as we need to compute $n^2$ perturbations for each gradient, and each perturbation requires computing the stationary distribution of a perturbed matrix, which naively takes $O(n^3)$ time, for a total of $O(n^5)$ time per gradient.  Thus each iteration of gradient descent will take $O(n^5)$ time, and you need to do many iterations of gradient descent, so this might take a while.  (You can speed this up by computing the stationary distribution of the perturbed matrix  using a few iterations of the power method, initialized with the stationary distribution of $A$; this takes $O(n^2)$ time; but it's still $O(n^4)$ time per iteration of gradient descent.)

A better way is to find an explicit, symbolic formula for the gradient $\nabla \varphi(A)$, and then use that with gradient descent.  That is possible but it gets messy, so I'll explain the details below.

It remains to handle the constraint that $A$ must be stochastic.  There are multiple ways to do that:

One way is to use projected gradient descent: in each iteration you update $A$ in the direction indicated by the gradient, then project the resulting matrix to the nearest stochastic matrix ($A' = A - \gamma \nabla \varphi(A)$, then let $A''$ be the stochastic matrix nearest to $A'$ and replace $A$ with $A''$).
Another way is to adjust the objective function, letting $\varphi'(A) = \varphi(A) + c \cdot p(A)$ where $p(A)$ is a penalty term that measures how badly $A$ fails to be stochastic (a simple choice might be $p(A) = \sum_i |(\sum_j A_{ij}) - 1|^2 + \sum_{i,j} \min(a,0)^2$), then choose $c$ sufficiently large and apply gradient descent to minimize $\varphi'(A)$.  For instance, you could perform several rounds of gradient descent, where the solution from the previous round is the initial value for next round, and where you double $c$ after each round.

There may be other ways as well.

OK.   That's an overview of the approach that I am proposing.  On to explaining how to compute the gradient symbolically, as promised.

An explicit formula for the gradient

We can write the objective function in the form $\varphi(A) = \varphi_1(A) + \varphi_2(A)$ where $\varphi_1(A) = \|A-A_0\|_F$ and $\varphi_2(A) = \|\pi(A) - \pi_0\|_2$.  It's easy to compute $\nabla \varphi_1(A)$; it is simply

$$\nabla \varphi_1(A) = {1 \over \|A-A_0\|_F} (A - A_0).$$

Computing $\nabla \varphi_2(A)$ is more difficult, as this requires us to compute the gradient of the stationary distribution $\pi(A)$ as a function of $A$.  Since the stationary distribution $\pi(A)$ is the principal eigenvector of $A$ (when it is unique), this reduces to computing the gradient of the principal eigenvector of $A$ as a function of $A$, for which there are techniques available.  In particular, we have

$$\nabla \varphi_2(A) = {1 \over \|\pi(A) - \pi_0|_2} \sum_k (\pi_k(A) - {\pi_0}_k) \; \nabla \pi_k(A),$$

and we need to find an expression for $\nabla \pi_k(A)$, where $\pi_k(A) = \pi(A)_k$ is the $k$th element of $\pi(A)$, and $\nabla \pi_k(A)$ is the gradient of that with respect to the entries of $A$.

Fortunately, there are nice formulas for how to compute the gradient of the eigenvector of a matrix.  In particular,

$$\nabla \pi_k(A) = (\text{Id} - A^\top)^\dagger b_k \pi(A)^\top,$$

where $b_k$ is the $k$th basis vector (1 in the $k$th entry and 0 elsewhere), and $\dagger$ indicates the Moore-Penrose pseudo inverse.  (Here I have used that the stationary distribution $\pi(A)$ is the eigenvector that corresponds to eigenvalue 1.)  Plugging in, we find that

$$\nabla \varphi_2(A) = {1 \over \|\pi(A) - \pi_0|_2} (\pi(A) - \pi_0)^\top (\text{Id} - A^\top)^\dagger \pi(A)^\top.$$

This then gives a symbolic expression for $\nabla \varphi(A) = \nabla \varphi_1(A) + \nabla \varphi_2(A)$.


PCA and Eigenvectors I am trying to understand how PCA works, and think I got most of it except...

By calculating eigenvalues/vectors of the covariance matrix of the original dataset allows to find those dimensions where data is least correlated (lowest covariance). Sorting them based on eigenvalues is the method which allows the sorting of dimensions.

Hence, multiplying the original dataset by the 'feature matrix' allows to discard those dimensions which are least significant.

What I don't understand is the relation between the covariance matrix and eigenvectors. Why is it that eigenvectors of the covariance matrix automatically allow us to find the directions where data is least correlated?

Hope this makes sense :)

Each eigenvector of the covariance corresponds to a new feature (which is a combination of the original features).

The principal eigenvector of the covariance matrix corresponds to the direction of maximum variance (not least as mentioned in the question).
Subsequent eigenvectors can be computed one by one under the constraint that they are orthogonal to the ones already computed. The fact that they are orthogonal makes the new features uncorrelated with each other.
In other words, a set of $k$ eigenvectors of the covariance corresponds to a set of $k$ new features that are uncorrelated with each other.

There are many different viewpoints on what exactly principal components are. In general, these seemingly different viewpoints have strong connections with each other. For example, the first $k$ eigenvectors (i.e., the eigenvectors corresponding to the $k$ largest eigenvalues of the covariance matrix) capture the maximum cumulative variance of the data. At the same time they form a basis for a $k$-dimensional subspace (the space of new features) such that if you project your original data (each datapoint individually) on that subspace (i.e., if you optimally approximate each datapoint using the new features), then the total euclidean distance between the original datapoints and their projections is the minimum possible; by minimum we mean in comparison to any other $k$-dimensional subspace.

This short article takes a look at what PCA is from a few different viewpoints.


is reducing to normal form simply applying beta-reduction? See example below:

reduce to normal form:

(λ c . (λ a . (λ d . (λ h . (h (d (a (a (λ z y . y))) (d (a (a (λ f x . x))) (a (a (a (λ z x . x)))))) (h (a (a (λ z y . y))) (a (a (a (λ z x . x))))))) (λ n m . n (d m) (λ z y . y))) (λ n m . n a m)) (λ n z . c (n z) z)) (λ z g x . z (g x))

Wikipedia says that to be in normal form: all reductions that can be applied have been).

I used these two calcualtors to try and get the correct reduction:
http://lambda.jimpryor.net/code/lambda_evaluator/
http://lambda.jimpryor.net/code/lambda_evaluator/

both return:
λz x.z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z x)))))))))))))))))))))))))))))))))))))))))

Can I get to this answer by only using beta-reduction? This is the only reduction I am currently trying to understand but from this example there are two more:
https://stackoverflow.com/questions/34140819/lambda-calculus-reduction-steps

Using only $\beta$-reductions is sufficient to get to a normal form if variables are named “correctly”.

What do we mean by that?

Let’s take as an example the term $\lambda x y. x\ y$.
Informally, it is a function that takes two arguments - variables $x,y$ and gives us the application of first argument to the second - $x\ y$. Now we want to apply something to this term, say $$(\lambda x y. x\ y)\ a$$

After we perform the $\beta$-reduction, substituting $a$ for $x$ in our term, we get $\lambda y. a\ y$ and we realize that whatever we substitute for $x$, we should be left with a function that applies it to the input variable $y$.

What if we want to substitute a variable named $y$ for $x$? We would be left with $\lambda y. y\ y$ which is a function that takes a variable and applies it to itself! Not at all the function we thought we would have for any $a$.

This example demonstrates that sometimes $\alpha$-conversion is necessary as a helper tool, and I emphasize the word “conversion” because it is not per se reduction.

You could also check my answer on this question that has computation similar in nature to yours and maybe try pLam interpreter to see all the reduction steps with colored terms that go into reductions.


Dynamic list for frame pointers and static list of nested activation frames I am going through the book Compiler Construction by Niklaus Wirth.  The following is what I feel to be stated summarily by his lesson on procedure calls:

The compilation of a procedure call is the allocation of a block of stack memory. It starts with the base address which is stored in the frame pointer and the local variables are allocated addresses with respect to it with negative offsets.
For every procedure the block of stack memory is termed as its stack frame or the activation frame and a DYNAMIC LIST is maintained of the base pointers of the  stack frame

Then an illustration of an situation is made where nested procedure calls are made with the following code snippet:

PROCEDURE P; P 0
  VAR x: INTEGER; x 1
  PROCEDURE Q; Q 1
  VAR y: INTEGER; y 2
    PROCEDURE R; R 2
    VAR z: INTEGER; z 3
    BEGIN x := y + z
    END R;
  BEGIN R
  END Q ;
  PROCEDURE S; S 1
  BEGIN Q
  END S;
BEGIN Q; S
END P;

Now it is said that  assuming that access of the local variables of R by traversing the dynamic list, it is possible that call to R can be made through the sequence  P → S → Q → R. As such a second list of activation records is necessary, denoting the nestedness of the procedures.

Why is it necessary to have a static list of the activation frames of the procedures and the procedures nested in them?

At the end of a procedure, we can restore the value of the frame pointer by taking the previous value in the dynamic list and the return address would be restored from the register where it was saved. I don't see why a static list linking the activation frames of the nested procedure is required.

It has been suggested that the following question :

Static scope and dynamic scope

might be having the answer to my question and the questions are co-duplicate to each other but I would beg to differ as :

The suggested question is more about evaluation strategy of a function , more focused on the implementation of argument passing to functions , however my question can be said to be  about "returning the control to the calling procedure" or "linking of nested procedures ".
My question basically asks the reasons for which Wirth considers maintaining of one static list as a necessity  . The following is the link to With's book  and my question is centered around the topic "addressing of variables" in pages 72 and 73 .

ON WHY I SAID THAT MY QUESTION IS MORE ABOUT "returning the control to the calling procedure"

I know Wirth starts up the topic with the problem of accessing the variables of an internal procedure or nested procedure but since the dynamic list of frame pointers is maintained to restore the registers from activation frames on return of control to the calling procedure that is why I said that my question is more about the "returning the control to the calling procedure".

The two links can point to different frame.  Consider this variation:

PROCEDURE P;
  VAR x: INTEGER;
  PROCEDURE S;
  BEGIN X := 42
  END S;
  PROCEDURE Q;
  VAR y: INTEGER;
    PROCEDURE R;
    VAR z: INTEGER;
    BEGIN S
    END R;
  BEGIN R
  END Q ;
BEGIN Q
END P;

when calling S in R, it will set the static link pointing to R so that S can return to R and the dynamic link pointing to P so that S can access the correct X.


Divide-and-Conquer Exercise I need help on this question:
Given a sorted array of distinct integers A[1, . . . , n], you want to find out whether there is an index i for which A[i] = i. Give a divide-and-conquer algorithm that runs in time O(log n).

How I can proceed?
Thanks a lot!

Hint: Define $B[i] = A[i] - i$. What can you say about the array $B$? Use the fact that $A$ contains distinct integers.


Why don't integer multiplication algorithms use lookup tables? It seems to me that we can use lookup tables for multiplication of two integers of size $\log(n)/2$, and that the number of entries for each table of these numbers should be $O(n)$.

Now, multiplying two $n$-bit naturals together can be assisted by using an FFT of size $O(n / \log(n))$.  It seems to me that we can then perform the multiplications and additions for the FFT using the lookup tables.

I'm wondering why this method doesn't or hasn't seemed to get any attention.  Is it because of memory bandwidth problems?

It just seems to me that using tables would be quicker, so I'm hoping that someone can provide me with a better intuition.

If you want to use lookup tables, and you have 4GB of memory, you'll only be able to use a lookup table with about $2^{32}$ entries or fewer, so you'll only be able to handle multiplication of numbers that are at most 16 bits long.  If you want to multiply larger numbers, you won't be able to use lookup tables for multiplication.  Typically we want to multiply numbers that are larger than that.  And when we do want to multiply small numbers, using the CPU's built-in multiply instruction is usually faster than using a lookup table.

So there is no size (that I'm aware of) where a lookup table is a good solution for multiplying two numbers.

Now you're thinking that maybe the numbers that are generated by FFT should be multiplied with lookup tables.  But those are just numbers, and as I said above, there is pretty much no situation where the fastest way to multiply two numbers is with a lookup table.  It doesn't matter how those numbers were generated -- whether by FFT or by any other process.

So I'd say the reason it doesn't have more attention is because it doesn't deserve attention; it seems unlikely to be faster or better than existing schemes.

Lookup tables are occasionally used in cryptographic code, where constant-time access is needed.  This is not because they are faster -- they're not; they're slower -- but because they have other properties that are beneficial.  I don't know of any specific examples, but it wouldn't surprise me to discover that someone had used a lookup table for multiplication in some constant-time cryptographic code.


Equivalent Straight Line Embedding of a Planar Graph Drawing on a Grid An embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:

the endpoints of the arc associated to an edge e are the points
associated to the end vertices of e,
no arcs include points associated with other vertices,
two arcs never intersect at a point which is interior to either of the arcs.

Two embeddings of a planar graph in the plane are called equivalent for every vertex of the graph the cyclic order of the incident edges is the same in both embeddings.

I am looking for a reference which shows that any Jordan arc embedding of a planar graph can be equivalently embedded as a straight line drawing with the $n$ vertices of the graph lying on the vertices of an  $O(n) \times O(n)$ grid. (Certainly any planar graph can be embedded with its vertices on the vertices of such a grid but I'm looking for an embedding that's equivalent to the originally given one.) Schnyder's algorithm seems to produce an embedding equivalent to the topological embedding given as its input but I've not managed to find a proof of this.

Does anybody know of such a theorem?

"Schnyder's algorithm" computes an embedding on an $O(n)\times O(n)$ grid. See here for a reference, and see here for a more general treatment that is not behind a paywall. Note that if your initial (topological) embedding is not unique, you can just add edges (while preserving planarity) until the graph becomes 3-connected (or even a triangulation) and then apply some drawing algorithm. Once the layout is computed you simply remove the augmentation.

I want to point out that there is also a different drawing algorithm for the $O(n)\times O(n)$ grid by De Fraysseix, Pach and Pollack. It is based on the canonical order of the planar graph. See here for the reference if the graph is a triangulation, and here for 3-connected planar graphs.enter link description here. These articles are behind paywalls, but the algorithms are standard and you will find lecture notes if you google the keywords. You might also try to check out the handbook of graph drawing for more information.


Restrictions to counter machines capturing LBA As you know in computation theory, there is a simple programming language equivalent in power to Turing machines. It is described as follows:

Values: natural numbers only, but of unlimited precision.

• Variables:

– Input variables X1, X2, X3, . . .

– An output variable Y

-Local variables Z1, Z2, Z3, . . .

• Instructions:

1 ) $V ← V + 1$ Increase by 1 the value of the variable V .

2 ) $V ← V − 1$ If the value of V is 0, leave it unchanged; otherwise decrease by 1 the value of V.

3 ) $ IF \;V \neq 0\; GOTO \;L$ , If the value of V is nonzero, perform the instruction with label L next; otherwise proceed to the next instruction in the list.

• Labels: A1, B1, C1, D1, E1, A2, B2, C2, D2, E2, A3, . . .

• Exit label: E.

• All variables and labels are in the global scope .

for example the following program computes f(x) such that if x = 0 , f(x) = 1 otherwise f(x) = x
\begin{align}
[A] \quad &X ← X − 1 \\
    &Y ← Y + 1 \\
    &IF\; X \neq 0\; GOTO \;A \\
\end{align}
this language can use infinite number of variables.

  What restrictions should be added to this language so its power will be the same as Linear Bounded Automata? One of them is clear about the variables but I will appreciate if anybody helps me about any others, if they exist. I have searched a lot but I couldn't find any source that describes both topics. I would appreciate any relevant pointers.

Programs with natural numbers as data and as instructions increment, decrement and zero test are know as register machines or counter automata. (Wikipedia cites several sources, usually I refer to Minsky).

Their power is that of the Turing machine, that is, they accept recursively enumerable sets (strings or numbers).

Thus they are more general than the LBA, which is more a complexity class (as mentioned in the comments). The length of the space used for computations is linear, otherwise the LBA are Turing Machines.

To translate that restriction to counter automata I would suggest to restrict the variables to at most exponential in the size (length) of the input. First, you can code such variable by markers on the tape. That would prove one inclusion. I expect that every LBA can be simulated by an exponentially bounded counter automaton, after all, the tape is just a number an writing on the tape is changing a digit. There is a standard construction that translates the two sides of the tape (right and left from the reading position) as two numbers, and moving the head is just a multiplication/division, deciding the element under the reading head is modulo counting. You need extra counters (variables) for these operations and in particular you need the zero test.


Connected components of the graph on $[n]$ in which $i,j$ are connected if $\mathrm{gcd}(i,j) > g$ I recently got asked the following question:

A set of $n$ cities are numbered from 1 to $n$. Given a positive integer $g$, two cities are connected if their greatest common divisor is greater than $g$. The number $n$ may be as large as $10^5$.
Alice has a list of $q$ cities that she'd like to visit. Given Alice's list of $q$ origin cities and $q$ destination cities, return a boolean vector with a 1 in the $i$th position indicating that it's possible to reach the $i$th destination city from the $i$th origin city, and 0 if not. The length of the list $q$ may be as large as $10^5$ as well.

I solved this problem with a quadratic time solution. However, the large upper bound for $n$ and $q$ clearly implies there is a better runtime. I haven't yet seen a way to speed up the creation of the graph, however.
My solution builds the graph in quadratic time, using a union find data structure to handle the component merging, and Euclid's algorithm for computing gcd's.
The fundamental question is whether there exists a faster than $O(n^2)$ algorithm to construct and query an undirected graph, when edges are defined by a pairwise rule, and it appears that every pair $(i, j)$ for $1 \leq i,j \leq n$ needs to be looked at.

Given parameters $n$ and $g$, you want to find the connected components of the graph on $[n] := \{1,\ldots,n\}$ whose edges are $\{(i,j) \in [n] : (i,j) > g\}$. Let us write these edges in a different way:
$$
\bigcup_{d=g+1}^n \{(i,j) \in [n]: d \mid (i,j) \} =
\bigcup_{d=g+1}^n \{(dI,dJ) : 1 \leq I,J \leq n/d \}.
$$
For each $d$, we have a clique on $\lfloor n/d \rfloor$ vertices. We can preserve the same connectivity properties by replacing it with a path:
$$
\bigcup_{d=g+1}^n \{(dI,d(I+1)) : 1 \leq I < \lfloor n/d \rfloor \}.
$$
The number of edges in the new graph is
$$
\sum_{d=g+1}^n \lfloor n/d \rfloor \leq n \sum_{d=g+1}^n \frac{1}{d} = O(n\log n).
$$
You can find the connected components using BFS/DFS in time $O(n\log n)$, a large improvement over your quadratic time algorithm.


Simple Task-Assignment Problem I have this simple 'assignment' problem:

We have a set of agents $A = \{a_1, a_2, \dotso, a_n\}$ and set of tasks $T= \{t_1, t_2, \dotso, t_m\}$. Note that $m$ is not necessarily equal to $n$. Unlike the general assignment formulation in Wikipedia, a task $t_c$ can only be assigned to an agent based on the task's preferred agents $ta_c \subseteq A$. For example, if we have $ta_1= \{a_1, a_3\}$, that means that task $t_1$ can only be assigned to either agents $a_1$ or $a_3$. Now, each agent $t_d$ has a quota $q_d$ where $q_d$ is positive integer. This means that $a_d$ must be assigned with $q_d$ number of tasks.

The Problem

Given above and a set of quota $\{q_1, q_2, \dotso, q_n\}$, is there an assignment of tasks to agents such that all agents meet their respective quota $q$. Note that it is not necessarily that all tasks be assigned to an agent.

Possible Solution

I have tried reformulating this problem in terms of a bipartite graph $G(A, T, E = \cup ta_c)$ and expressed as a form of matching problem where given a matching $M$, a vertex agent $a_d\in A$ is matched up to $q_d$ times or is incident to $q_d$ edges in $M$ but the vertices in $T$ is incident to only one edge in $M$. Not really like the usual matching problem which requires that the edges in $M$ are pairwise non-adjacent.

However, it was suggested by someone (from cstheory, he knows who he is) that I could actually work this out as a maximum matching problem, by replicating an agent $a_d$ into $q_d$ vertices and 'conceptually' treat them as different vertices as input to the matching algorithm. The set of edges $E$ is also modified accordingly. Call the modified graph as $G'$

It is possible to have more than 1 maximum matchings from graph $G'$. Now, if I understand this correctly, I still have to check each of the resulting maximum matchings and see that at least one of them satisfies the $qouta$ constraint of each $agent$ to actually provide the solution to the problem.

Now, I want to prove that not finding one maximum matching $M$ $\in$ set of all maximum matchings of the graph $G'$ that satisfies the $qouta$ constraint of the problem guarantees that there really exists no solution to the problem instance, otherwise a solution exist which is $M$.

I want to show that this algorithm always give correct result.

Question

Can you share to me some intuition on how I might go to show this?

As I stated on the CSTheory post, this is solved via maximum matching. The following should give enough intuition to show that each agent $a_i$ has a $q_i$-matching iff a transformed graph $G'$ has a matching. First, construct the graph $G$. Now, for each agent $a_i$ and quota $q_i$, make a new graph $G'$ that has $q_i$ copies of $a_i$. That is to say, if agent $a_i$ has quota $q_i = 3$, make 2 new nodes $a_i', a_i''$ that have the same tasks as $a_0$.

Here is an illustration to help. Supposed we have the complete bipartite graph $K_{2,3}$ where agent $q_1 = 2, q_2 = 1$.

Original graph $G$, and modified graph $G'$:

We see that agent $a_1$ has two copies in the new graph $G'$, while agent $a_2$ maintains just his lone copy. Solving for the maximum matching in $G'$ and then merging all copies of an agent to the original and you will have your best possible assignment. Since the edges are unweighted, one possible solution is (and merged solution):


How to prove that this language is not regular? Given a language $L$ over the alphabet { 0, 1, [, ,, ] } where if $x \in L$ then $x$ is of the form $[x_0, \dots, x_n]$, in which each of the $x_i$ represents unique binary strings (so $x_i = x_j$ only when $i=j$). Prove that this is not a regular language.

Here is what I have. I have used the pumping lemma.

Suppose $L$ is a regular language. Let $M$ be the DFA that accepts $L$. Let $p$ be the pumping length of $L$. Given $x = [x_0,\dots,x_p] \in L$ we see that $|x| > p$ so pumping lemma applies, so $x = UVW$ where $|UV| < p$, $|v| > 0$, and $UV^iW \in L$.

Now if we have $UVVW$ that means $V$ is repeating some of the characters in $x$ and therefore it must repeat some $x_i$. Therefore we have reached a contradiction, which shows that $L$ is not a regular language.

Is this a correct proof? If not, what can I do to improve it?

Now if we have $UVVW$ that means $V$ is repeating some of the characters in $x$ and therefore it must repeat some $x_i$. Therefore we have reached a contradiction, which shows that $L$ is not a regular language.

This is not necessarily true. Suppose $x=[0^p, 0^{p-1}, \dots, 00, 0]$. If $V$ is of length $k<p$ and entirely in $0^p$, we get $UVVW = [0^{p+k}, 0^{p-1}, \dots, 00, 0]$ which is still in $L$.

Normally when doing a proof using pumping lemma, we try to use a more specific $x$ such that the pumping lemma fails. Like this:

Suppose $L$ is regular and let $p$ be its pumping length. We choose $x=[0^p, 0^{p-1}, \dots, 00, 0]\in L$. By the pumping lemma, we can split it into 3 parts $UVW$. Noticed that $V$ cannot include the symbol [ otherwise $UVVW$ contains two [ which is not in $L$. Then, the choices for $V$ is either $0, 00, \dots, 0^{p-1}$. Note that it cannot be $0^p$ because it is subject to the constraint $|UV|\leq p$. No matter what we choose for $V=0^k$, the string $UW=[0^{p-k}, 0^{p-1}, \dots, 0]$ is not in $L$ because $0^{p-k}$ must be one of $0, 00, \dots, 0^{p-1}$. Hence $L$ is not regular.


Finding set of disjoint sets with additional value optimization I've got a set $Q$ of pairs $[S, v]$ where $S$ is a nonempty set and $v$ is a value ($v \in \mathbb{N}_{+}$). I need to find a subset $R$ of $Q$ with following properties:

Sum of all $v$'s is maximum
$S$ from all pairs construct a disjoint set

Example. For given set $Q$:

$Q = \{[\{1, 2\}, 5], [\{2, 3\}, 8], [\{3, 4\}, 2], [\{5\}, 1]\}$

Result $R$ should be:

$R = \{[\{2, 3\}, 8], [\{5\}, 1]\}$

I came up with an obvious algorithm which constructs every possible set of pairs whose $S$ constructs disjoint set:

T = {}
foreach (q in Q)
  foreach (t in T)
    if (union of all S from t and S from q constructs a disjoint set)
      add copy of t to T
      add q to t
  add {q} to T

Then I would find t with highest sum of all it's v's.

This is worst case $O(2^n)$.
Can I do better than this? I will appreciate any additional information regarding this problem.

Your problem is polynomially equivalent to the maximum-weight independent set problem problem, and the standard results for that problem apply directly to your problem as well.

If all the values were the same (say, $v=1$ for all pairs), then your problem would equivalent to the independent set problem.  In particular, treat each pair as its own vertex, and build an undirected graph $G$ where you have an edge between two pairs if they are disjoint.  Then the solution to your problem is exactly the largest independent set in $G$.    One can also construct a reduction the other way as well: given any undirected graph $G$, we can form an instance of your problem by construct a set corresponding to each vertex of $G$ (namely, the set of edges incident on that vertex), each of value 1; then the solution to your problem is the maximum independent set of $G$.

The independent set problem is NP-complete, so it follows that your problem is NP-complete as well.  Therefore, you should not expect any polynomial-time solution to your problem.

Because you allow arbitrary values to be associated with each set, your problem is basically equivalent to a slight generalization of the independent set problem, namely, the maximum-weight independent set problem.  Each vertex has a weight associated with it, and the weight of an independent set is the sum of the weights of the vertices in the independent set, and the problem is to find the heaviest independent set in the graph.  This is obviously at least as hard as the standard independent set problem, so also NP-complete.

Fortunately, there are standard algorithms for the independent set problem, and they can be extended to the maximum-weight independent set problem as well.  For instance, you can formulate the problem as an integer linear programming (ILP) instance and then try to solve it using an off-the-shelf ILP solver.  There are also exponential-time algorithms for independent set whose running time is asymptotically faster than $\Theta(2^n)$; I don't know whether they extend to the maximum-weight independent set problem as well, but you could check the literature to see, if this is of interest.  You could try applying them to your problem.

Unfortunately, the independent set problem is known to be hard to approximate to within a constant factor (unless P = NP), so you should not expect efficient approximation algorithms for your problem, either.


minimum spanning tree and minimum heavyweight spanning tree a minimum heavyweight spanning tree is a spanning tree in which the heaviest edge is as light as possible.
Formally,
input : given connected undirected weighted graph, $G$.
output : a spanning tree $T$ for $G$ with property that every spanning tree $T'$ for $G$ has some edge $e'$ such that $w(e')\ge w(e)$  for every edge $e$ in $T$.

provide a greedy algorithm to solved the problem.
is every minimum heavyweight spanning tree a minimum spanning tree ?

first thing comes into my mind was using Kruskal's algorithm with $O(|E| \log |V|)$ running time. If I use kruskal's algorithm for 1, the output will guarantee to be a MST, thus 2 will be true? Can someone verify this for me, thanks in advance

Hints:

Scaling.
Almost every graph would answer this.


Position in the Linked-list I am reading Data Structures and Algorithms by Alfred Aho, Jeffrey Ullman, et al. In the section about lists it's said:

We should note that a position in a linked-list implementation of a list behaves
differently from a position in an array implementation. Suppose we have a list with
three elements a, b, c and a variable p, of type position, which currently has position
3 as its value; i.e., it points to the cell holding b, and thus represents the position of c.
If we execute a command to insert x at position 2, the list becomes a, x, b, c, and
element b now occupies position 3. If we use the array implementation of lists
described earlier, b and c would be moved down the array, so b would indeed occupy
the third position.
However, if the linked-list implementation is used, the value of p, which is a pointer
to the cell containing b, does not change because of the insertion, so afterward, the
value of p is "position 4," not 3. This position variable must be updated, if it is to be
used subsequently as the position of b.†

I don't understand how do position works? It's said that position works differently in pointer implementation that that of array but, the result seems to be the same on both. In both implementation position (pointer) moves forward. Then, what's the difference? I appreciate your answers.

First of all, let me strongly recommend avoiding outdated textbooks such as Aho, Hopcroft and Ullman.
Let me also replace Aho, Hopcroft and Ullman's use of "position" with the more common notion of pointer. In a linked list, each cell consists of a value and pointer to the following cell (if any). The linked list itself is represented as a pointer to its first cell (if any). Therefore, if we consider the list $a,b,c$, then a pointer which is pointing at the third element will be pointing at the cell containing $c$.
(This is also a good place to mention that unless you're programming in Fortran or in Excel, then your arrays are zero-based; that is, the first element is element number 0.)
Now suppose that $p$ is a pointer which currently points at the cell containing $c$. If you insert $x$ between $a$ and $b$, then $p$ will still be pointing at $c$. However, $c$ is now the fourth element rather than the third element.
In contrast, if the list were implemented as an array, then $p$ will be a pointer to the third element of the array. Therefore, after inserting $x$ between $a$ and $b$, the pointer $p$ will be pointing at $b$.


Solving recurrence relation with minimum and factorial I need to solve the following recurrence relation, where $T(n,m)$ is defined over $\Bbb N_+\times\Bbb N_+$.

$T(n,m)=\begin{cases}
1, & n=1\text{ or }m\leq 2(n-1)!\\
\min\limits_{a,b,c\geq 1,\ c\le n-1\\a\leq c!,\ b\leq(n-c)!}{T(c,a)+T(n-c,b)+T(n,m-ab)}, & \text{else.}
\end{cases}$

Note: This question is highly related to my previous question here, since $ab\leq\max\limits_{1\leq c\leq n-1}{c!(n-c)!}=(n-1)!$

I guess that the minimum is obtained at $c=\lceil n/2\rceil,a=c!,b=(n-c)!$, but I don't know how to prove it.

The first 10 values of the first n's are:

$T(1,*)=1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\dots\\
 T(2,*)=1, 1, 3, 5, 7, 9, 11, 13, 15, 17,\dots\\
 T(3,*)=1, 1, 1, 1, 3, 3, 5, 5, 7, 7,\dots\\
 T(4,*)=1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\dots$

Experiments show that

$$T(n,m)=\begin{cases}1 & n=1
\text{ or }f(n,m)\leq 0,\\ 3+2\Big\lfloor\frac {f(n,m)-1}{g(n)}\Big\rfloor & \text{otherwise},\end{cases}$$

for $f(n,m)=m-2(n-1)!$, and for some $g$ whose first values are: 1, 1, 2, 4, 12, 48, 240. I guess that $$g(n)=\begin{cases}1 & \text{if }n<3,\\ 2(n-2)! & \text{otherwise.}\end{cases}$$

Summary

It is not true that the minimum can always be obtained at $c=\lceil n/2\rceil,a=c!,b=(n-c)!$. Here is the smallest counterexample, $$T(5,49) = T(1,1) + T(4,1) + T(5,48) = 3 \not=5=T(3,6)+T(2,2)+T(5,12).$$ Instead, the minimum can always be obtained at $c=1$, $a=1$,  $b=2(n-2)!.$

The following neat formula conjectured in the question is correct.
$$T(n,m)=\begin{cases}
1 & n=1 \text{ or }f(n,m)\leq 0,\\
3+2\Big\lfloor\dfrac {f(n,m)-1}{g(n)}\Big\rfloor &\text{otherwise},
\end{cases}$$
where $f(n,m)=m-2(n-1)!$ and $g(n)=\begin{cases}1 &\text{if }n<3,\\ 2(n-2)! &\text{otherwise.}\end{cases}$

Observations

$T(n,m)=1,$ if $n=1$ or $m\le 2(n-1)!$.
$T(n,m)$ is nondecreasing with respect to $m$.
$T(n,m)\ge3$ if $m\gt 2(n-1)!$.
$T(2,m)=\begin{cases}
1 & m\le2,\\
2m-3 & \text{otherwise}.\end{cases}$
If $n=3,4,5$, then the conjectured formula is correct.
The following proposition $p(n,j)$ is true for all $n\ge3$ and $j\ge0$.
$$\text{If $n\ge3$ and $j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor$ for some $j\ge0$ and $m$, then $T(n,m)=3+2j.$}$$

The conjectured formula is the same as the combination of observations 1, 4, and 6.

All observations above except observation 6 can be proved easily, although observation 5 might take a while to sort out case by case.

Let $S(n,m,a,b,c)=T(c,a)+T(n-c,b)+T(n, m-ab)$. Then for $m\gt 2(n-1)!$,
$T(n,m)=
\min\limits_{a,b,c\geq 1,\ c\le\frac n2\\a\leq c!,\ b\leq(n-c)!}S(n,m,a,b,c).$ The reason why we can replace the condition $c\le n-1$ by $c\le \frac n2$ is that $(n,m,a,b,c)=(n,m,b, a, n-c)$.

Proof of observation 6 by well-founded induction

Here are the steps. Steps 1 and 2 are the induction bases while step 3 is the induction step.

Suppose $j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor=0$, i.e., $2(n-1)!\lt m\le2(n-1)!+2(n-2)!$. Since $m\gt 2(n-1)$, $$T(n,m)\ge3.$$ On the other hand, $$T(n,m)\le S(n,m,1,2(n-2)!,1)=1+1+1=3.$$ So $T(n,m)=3$, i.e., $p(n,j)$ is true when $j=0$.
Observation 5 says that $p(n,j)$ is true for $n=3,4,5$.
Let $n\ge6$ and $j\ge1$. As induction hypothesis, suppose $p(x,y)$ is true for all $x\le n$ or $x=n$ and $y\lt j$, i.e.,
$T(x,y)=3+2\lfloor\frac{f(x,y)-1}{2(x-2)!}\rfloor$, which implies, by the definition of $\lfloor\cdot\rfloor$, $$(x-2)!(T(x,y)+2x-5)<y\le (x-2)!(T(x,y)+2x-3).$$

We will prove that $p(n,j)$ is true, i.e., $T(n,j)\le 3+2j$.

Let $j=\lfloor\frac{f(n,m)-1}{2(n-1)!}\rfloor$ for some $m$.

Proof for $T(n,m)\le 3+2j$

By induction hypothesis, we know that $T(n, m-2(n-2)!)=3+2(j-1)$. Hence,
$$T(n,m)\le S(n,m,1,2(n-2)!,1)=1 + 1 + T(n, m-2(n-2)!)=3+2j.$$

Proof for $T(n,m)\ge 3+2j$

Because $T(n,m)$ is nondecreasing with respect to $m$ (observation 2), we will assume $m=2(n-1)!+2(n-2)!j+1$, the smallest value possible such that $j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor.$

We will prove that $S(n,m,a,b,c)\ge 3+2j$ for all valid choices of $(a,b,c)$.
The case when $c=1$ or $c=2$ is relatively easy. From now on assume $3\le c\le \frac n2$.

Let $A=T(c,a)$ and $B=T(n-c,b)$. The case when $A=1$ or $B=1$ is much easier to prove. Now assume $A,B\ge2$.

Since $c<n$, we have $a\le(c-2)!(A+2c-3)$.
Since $n-c<n$, we have $b\le(n-c-2)!(B+2n-2c-3)$.
Since $ab\ge1$, we have $\lfloor\frac{f(n,m-ab)-1}{2(n-2)!}\rfloor<j$, so we can apply induction hypothesis to yield the first equality below.

Since $T(n,m)$ is nondecreasing w.r.t $m$,
$$\begin{aligned}
&S(n,m,a,b,c)\\
&\ge A+B+T(n,m-(c-2)!(A+2c-3)\,(n-c-2)!(B+2n-2c-3))\\
&= A+B+3+ 2\lfloor\frac{f(n,m-(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3))-1}{2(n-2)!}\rfloor\\
&= 3+2j+ A+B +2\lfloor\frac{-(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3))}{2(n-2)!}\rfloor\\
&\gt 3+2j+ \frac{(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3)}{(n-2)!}(h(c,A,B)-1) \\
\end{aligned}$$

where
$$h(n,A,B,c)=\frac{(A+B-2)(n-2)!} {(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3)}.$$
Since $n-c<n$, induction hypothesis yields the second equality below.
$$\begin{aligned}
B&=T(n-c,b)\le T(n-c, (n-c)!)\\
&=3+2(\frac{(n-c)(n-c-1)}2-(n-c-1)-1)\\
&=(n-c)(n-c-3)+3.
\end{aligned}$$
Since $n\ge6$ and $c\ge3$, $(n-2)!\ge (n-2)(n-3)(n-4)(c-2)!(n-c-2)!.$
Since $n\ge6$, $c\le \frac n2$ and $A,B\ge2$, $(n-2)(A+B-2)\gt A+2c-3.$

$$\begin{aligned}h(n,A,B,c)
&\ge\frac{(A+B-2)(n-2)(n-3)(n-4)}{(A+2c-3)(B+2n-2c-3)}\\
&\ge\frac{(n-3)(n-4)}{B+2n-2c-3}\frac{(n-2)(A+B-2)}{A+2c-3}\\
&\ge\frac{(n-3)(n-4)}{(n-c)(n-c-1)}\frac{(n-2)(A+B-2)}{A+2c-3}\\
&\gt1
\end{aligned}$$

So $S(n,m, a,b,c) \gt 3+2j.$

The proof is complete. By the way, the proof for $T(n,j)\le 3+2j$ shows that the minimum can always be obtained at $c=1,$ $a=1,$ $b=2(n-2)!.$

Exercises

Exercise 1. Prove the formula for $T(2,m)$.

Exercise 2. (Observation 5) Prove the formula for $T(3,m)$, $T(4,m)$, and $T(5,m)$. Hint, the proof of observation 6 above might be helpful.

Exercise 3. Let $T_1$ be defined over $\Bbb N_{+}\times\Bbb N_{+}$.
$$T_1(n,m)=\begin{cases}
1, & n=1\text{ or }m\leq (n-1)!\\
\min\limits_{a,b,c\geq 1,\ c\le n-1\\a\leq c!,\ b\leq(n-c)!}T_1(c,a)+T_1(n-c,b)+T_1(n,m-ab), & \text{else}
\end{cases}$$
Show that $$T_1(n,m)=\begin{cases}
1 & n=1 \text{ or }m\le (n-1)!,\\
3+2\Big\lfloor\dfrac {m-(n-1)!-1}{(n-2)!}\Big\rfloor & \text{otherwise}.\end{cases}$$


Smaller approximation ratio for larger input size? Is it possible for an approximation algorithm (for minimization optimization problem) to obtain smaller approximation ratios for inputs of larger size? For example, is $1/n$- or $1/\log n$-APX reasonable? If it is, do you know any natural problems?

In most cases it is possible to artificially enlarge an instance. For example, if you want to solve MAX-CLIQUE, you can add an independent set. In these circumstances, the approximation ratio cannot improve as the size of the instance gets larger. However, it is possible that there are some natural problems in which the phenomenon you describe does occur.


Hierarchy of complexity classes $\bigcup_{c > 0} \mathrm{Time}(2^{c \log^k n})$, w.r.t. $k$ This is a true/false question:

  For each integer $k > 1$, define the complexity class $\sf QP_k := \bigcup_{c > 0} Time(2^{c \log^k n})$. Then for all integers $k > 1$, $\sf QP_k \subsetneq QP_{k+1}$.

I have to prove it is true, or I have to give a counter example as to why it is not true.

I am having a lot of difficulty understanding the notation and also how to approach this problem. My understanding is that $c$ is some constant and effectively doesn't matter.

Edit: I guess I am unclear about how c and k work, the c seems like it doesn't matter so  its asking us if there is every a point where from k = 2 to k = infinity if there will ever be a situation in which $2^{c \log^k n}$ = $2^{c \log^{k+1} n}$ for all c and n.

Is this the right interpretation?

I cannot find a single counter example that would make this true for any k, so it must be true. I am not sure how I would go about proving this is true.

Hint: Use the time hierarchy theorem.

The first step, naturally, is understanding the question, that is, the definitions involved. The class $\mathsf{QP}_k$ consists of all problems solvable in time $2^{O(\log^k n)}$. We could similarly define $\mathsf{P}_k$ to consist of all problems solvable in time $O(n^k)$, and $\mathsf{P}$ to be a union over all $\mathsf{P}_k$:
$$ \mathsf{P}_k = \bigcup_{c>0} \mathsf{Time}(cn^k), \quad \mathsf{P} = \bigcup_{k>0} \mathsf{P}_k = \bigcup_{c,k>0} \mathsf{Time}(cn^k). $$
The class $\mathsf{QP} = \bigcup_{k>0} \mathsf{QP}_k$ is known as quasi-polynomial time. The question asks you to show that the corresponding hierarchy $\mathsf{QP}_2 \subseteq \mathsf{QP}_3 \subseteq \cdots$ is strict, that is $\mathsf{QP}_2 \subsetneq \mathsf{QP}_3 \subsetneq \cdots$. The same happens with the hierarchy corresponding to $\mathsf{P}$, again using the time hierarchy theorem: $\mathsf{P}_1 \subsetneq \mathsf{P}_2 \subsetneq \cdots$.

Why can't the same approach be used to prove $\mathsf{P} \subsetneq \mathsf{NP}$? Because here we're comparing deterministic computation to non-deterministic computation with the same time bounds, and there is no counterpart of the time hierarchy theorem which helps us here. Moreover, the time hierarchy theorems, in both the deterministic and non-deterministic case, are proved using diagonalization, a technique which is known to be unable to separate $\mathsf{P}$ from $\mathsf{NP}$ (in its vanilla form).


reduction technique for undecidability I have been reading about how to test the undecidability of a problem, and some tests talk about the reduction technique. For what I could understand of this technique is that if I want to prove that problem X is undecidable I can take a problem Y which has already been proven to be undecidable. Then by using logic or mathematical manipulation, I try to reduce or get an instance of problem X by modifying problem X, am I right?

So for example, if I want to test the undecidability of problem X, it would be fair if I pick up, for example, the undecidability of the detection of computer viruses, as stated by Cohen, as an undecidable problem by applying reduction to it, would that be fine?

To prove that problem X is undecidable you can reduce a problem Y (which has already been proved to be undecidable) to X. In fact if Y<mX then we know that X is at least as much hard as Y is. So what you have to do is to show a function f that maps instances of problem Y in instances of problem X, so that if y is an instance of Y with answer "yes" than f(y)=x is an instance of problem X with answer "yes", and if y is an instance of Y with answer "no" than f(y)=x is an instance of problem X with answer "no".


Does graph G with all vertices of degree 3 have a cut vertex? I'm asked to draw a simple connected graph, if possible, in which every vertex has degree 3 and has a cut vertex. I tried drawing a cycle graph, in which all the degrees are 2, and it seems there is no cut vertex there. I know, so far, that, by the handshaking theorem, the number of vertices have to be even and they have to be greater than or equal to 4. So, I kept drawing such graphs but couldn't find one with a cut vertex. I have a feeling that there must be at least one vertex of degree one but I don't know how to formally prove this, if its true. I'd appreciate if someone can help with that.

Not necessarily true, for example complete graph of 4 vertices have no cut vertex. But there exists a graph G with all vertices of degree 3 and there
is a cut vertex. See the picture. Red vertex is the cut vertex.


What mechanisms prevent a process from taking over the processor forever? Suppose a process keeps running code (e.g. an infinite loop). How can other programs take over? What prevents the process from remaining active forever?

Various peripherals are connected to the main processor. When an event happens in a peripheral, the peripheral sets an electric signal which causes the processor to take some action. The act of setting this signal is called an interrupt request (IRQ for short), and the aftermath of the interrupt request on the processor is called an interrupt.

When a processor receives an interrupt, it typically does something like this:

Mask interrupts. This means that if other IRQs happen (coming from the same peripheral or a different one), they won't be noticed just yet: they will not have any effect on the processor until interrupts are unmasked.
Save the value of the program counter register to a register dedicated to that effect. Also save the value of a register that contains the processor mode (e.g. user mode, kernel mode, interrupt mode, …). Depending on the processor architecture, other registers may be saved as well (e.g. stack pointer).
Switch the processor mode to interrupt mode.
Read a value from a predefined address in memory, or from a register. This value is called the interrupt vector.
Jump to the address given by the interrupt vector.

The code at that address is typically kernel code. On computer architectures with memory access permissions, the kernel normally prevents unprivileged processes from setting interrupt vectors or from changing the code at that address. The kernel code typically begins by copying the saved register values into memory, so that they won't be forgotten if some other interrupt occurs.

One of the peripherals that can send interrupts is the clock. To avoid a process running forever, whenever the operating system kernel allows a process to execute (by branching to its code), it first programs the clock to send an interrupt at a certain time in the future, allowing the program to run uninterrupted only for a time slice.

If the process is still running at the end of the time slice, the clock interrupt occurs. The code at the interrupt vector is kernel code, so the process is no longer running: it has been preempted. The process's code and data are still around: the kernel can later decide to let the process execute some more by restoring the saved register values (finishing with the program counter).

After the kernel has finished its basic interrupt processing, and has performed whatever tasks it deems useful, it decides which process to execute next. This decision is called scheduling.

Some operating systems (mostly on tiny embedded systems) allow processes to run as long as they like. This is known as cooperative multitasking. (And some operating systems are even more basic: they only allow a single task at a time.)


Is a simple graph connected, if every node has at least one adjacent edge and $|E|\ge |V|-1$? Let $G=(V,E)$ be an undirected graph without self-loops or parallel edges.

Is the following statement true?
If $|V|=n, |E|\ge n-1$ and every node has at least one adjacent edge, then $G$ is connected.

I've proved it for $|E|=n-1$:

Per induction:
Start:
For $\left|V\right|=1$ the graph is trivially connected.

Induction step:
Let the statement be shown for all graphs  $G=\left(V,E\right)$ where $\left|V\right|=n-1$ and $|E| = n-2$.

Let further $G=\left(V,E\right)$ with $\left|V\right|=n$ and $|E| = n-1$ be given.

We're now looking for an induced sub graph  $G|_{V^\prime}$ where $V^\prime\subset V, \left|V^\prime\right|=n-1$, so that  $G|_{V^\prime}$ has at least $n-2$ edges.

(Any such sub graph can have at most $n-2 $ edges, as there'll always be at least one edge that originally lead to the removed node)

Let's now assume that every sub graph $G|_{V^\prime}$ has less than     $n-2$ edges.
Then, the removed node in any sub graph would have at least $2$ edges.

Thus, every node must have at least $2$ edges, and therefore there'd have to exist at least $n$ edges in the graph.

Therefore, there's at least one sub graph $G|_{V^\prime}$ with $n-2$ edges, for which our induction assumption holds. And because there is one edge from $G|_{V^\prime}$ to the erased edge, we get that $G$ is connected.

Therefore, the induction is completed.

However, if I try to generalize the above proof, the same style leads to an inequality that only holds if $|E|>|V|$.

Therefore, if the above proof can be generalized, how would it look? If not, what's an example where it fails?

If $|V|=n, |E|\ge n-1$ and  every node has at least one adjacent edge , then $G$ is connected.

No, it is not true. Here is an counterexample.

Graph made at https://graphonline.ru/en/

Exercise. Construct a simpler counterexample where $|V|=n$ and $|E|=n-1$.


Prove that a language is in co-NP For a homework assignment, I have to prove that a given language $L \in coNP$.

I understand that one way of doing so, would be to prove that $\bar{L} \in NP$, i.e. give a polynomial time verifier for $\bar{L}$.

I am having trouble understanding what the complement of the language would be. eg: if

$$L = \{ (a, b, c) \in Z^{+}   |   \nexists \text{  } x \in Z^{+} \text{ s.t. } x < a \} $$

Then, is

$$\bar{L} = \{ (a, b, c) \in Z^{+}   |   \exists \text{  } x \in Z^{+} \text{ s.t. } x < a \} $$

Or is $\bar{L}$ a different language? Do I take the complement of the left hand side of the pipe operator? That is, can $\bar{L}$ contain strings from $Z^{-}$ now?

Languages are defines with respect to a finite alphabet. Thus, integers cannot be represents just by giving a triplet as you suggest, you need to encode it.

For convenience, let's assume a decimal encoding, with the "$-$" sign for negation, and the character $\#$ separating the numbers. Thus, for example, the word $8\#12\#-3$ represents the triplet $(8,12,-3)$ (note that usually we would use a binary encoding, but it doesn't really matter). Call our alphabet $\Sigma$.

Now, a word $w$ is in the language you describe iff the following hold:

$w=a\#b\#c$ where $a,b,c$ are either words in {0,...,9}^$\setminus {0}^. That is, they represent positive numbers (we allow leading 0's here, but we could also formulate without them).
There does not exist $x\in \mathbb{Z}_+$ such that $x<a$.

Note that we did not do anything yet, just wrote down the language. In particular, we purposely ignore the fact that condition 2 simply means that $a\le 1$.

The formal complement of your language is the set of words that either don't satisfy condition 1, or don't satisfy condition 2 (or both).

You could write this more succinctly or more explicitly, as words that are either not of the form $a\#b\#c$ with the condition 1 above, or words that are of that form, but where $a$ is not of the form $0^*1$.

It should be mentioned that once you are familiar with the notion of languages, we usually don't dig down to this level of formality, and in fact we would ignore the encoding somewhat. Then, you might see things such as
$\overline{L}=\{(a,b,c)\in \mathbb{Z}: \exists x\in \mathbb{Z}_+ \wedge x<a\}$.

Also note that throughout this answer we do not distinguish between a word and its numeric value, but if you really want to nitpick, then such a distinction should be made.


Show that $O(\text{max}\{f(n),g(n)\})=O(f(n)+g(n))$ Show that $O(\text{max}\{f(n),g(n)\})=O(f(n)+g(n))$

Can I keep the same constant $c$ in each of the cases?

Consider two cases:
$$1)f(n)>g(n);O(\text{max}\{f(n),g(n)\})⇒O(f(n))\Rightarrow d(n) ≤c⋅f(n);c>0$$
$$2)f(n)≤g(n);O(\text{max}\{f(n),g(n)\})⇒O(g(n))\Rightarrow e(n)≤c⋅g(n);c>0$$
Combining the 2 cases yields:
$$d(n)+e(n)≤c⋅f(n)+c⋅g(n)$$
$$d(n)+e(n)≤c⋅(f(n)+g(n))$$
Which is definition of $O(f(n)+g(n))$

I guess the proof is fine except for the fact that you have used same costant in two different eqns. Even if you use(and you must use, because the constant you choose is arbitrary) two different conts say c1 and c2, the solution will imply the same.


Mistake in the Algorithm Design Manual? Look at this excerpt from the Algorithm Design Manual by Skiena, 2nd Edition

The sum of the first $n$ even integers? Surely, the two sums given do not include only even numbers, right? Is this a mistake on the author's part, or am I missing something?

This is an explanation for the Gaussian sum formula (funfact: in German it is called "little Gauss"). Hence, as you recognized, the even here is not correct.

The equality of these sums can be shown inductively or simply by putting them into Wolframalpha

The "even" case works like Raphael stated, but doesn't seem to have any intellectual value.


How to describe the languages of these regular expressions in plain English? This is actually a question my lecturer gave us, so I know that it's kind of homework, but I tried to answer this and still had no luck.

The question is

  Give English description of the languages of the following regular
  expressions.

  $(1+\epsilon)(00^*1)^*0^*$
  $(a^*b^*)^*aaa(a+b)^*$
  $(a+ba)^*b^*$

I could only guess that the second one as the set of strings that at least have three consecutive $a$s. But I'm really clueless about others. Can someone make this clarified for me? Any help is highly appreciated.

The first regular expression captures all strings over $\{0,1\}$ not containing two consecutive 1s. It is not hard to check that any string in the language of the given regular expression has this property, and with some more work you can show the converse.

The second regular expression captures all strings over $\{a,b\}$ containing $aaa$ as a (consecutive) substring, as you also noticed.

The third regular expression captures all strings over $\{a,b\}$ not containing $bba$ as a (consecutive) substring, though this perhaps requires some verification.


Is there a way to make chess an absolutely fair game? Chess is usually considered a mostly "fair game" between White and Black because the opening position of pieces has mirror symmetry (between players). In practice it also appears to be a fair game because it is combinatorially complex, so if White has a first-move-advantage, it is hard to detect in actual play.

What are some examples of changes in the rules of chess where the game can be made exactly mathematically fair, including eliminating any possibility of White's possible first-move-advantage, and without adding any chance events (such as a coin toss as to who moves first)?

We can run a pair of games, sequentially, where player one first plays white, then black.

Let's write W for win, L for lose and D for draw, from the point of view of player one. In the cases WW,WD,DW, player one wins the match. In the cases LL,LD,DL, player one loses the match. In the cases WL,LW,DD, the match is a draw.
(If a draw match is undesired, play another match.)


Is it true that NEXP = EXP when the input binary strings have size O(n)? I have a question about this. Because if the input binary strings have size of O(n), it takes exponential time to list all possibilities of it. If an language is in NEXP, then we can list all input possible input strings and then use exponential time to check each one, which is still in exponential time in total. It seems like NEXP=EXP under this circumstance.

"When the input has size $O(n)$." Unless otherwise stated, $n$ is defined to be the length of the input. So, generally speaking, the input length is just $n$, and your question is just

  Is EXP equal to NEXP?

We don't know, but we suspect not.  Nondeterminism seems to add extra power that we don't know how to simulate deterministically without requiring exponential time.

  If an language is in NEXP, then we can list all input possible input strings and then use exponential time to check each one

That doesn't make sense. In a computational decision problem, you are given an input and you must determine whether the answer is "yes" or "no" for that specific input. Enumerating other possible inputs doesn't seem helpful: if you're asked a question, your job is to answer that question, not list off all the other questions you could have been asked instead.


Is the complement of { ww | ... } context-free? Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$.  In other words, $L$ contains the words that cannot be expressed as some word repeated twice.  Is $L$ context-free or not?

I've tried to intersect $L$ with $a^*b^*a^*b^*$, but I still can't prove anything. I also looked at Parikh's theorem, but it doesn't help.

It's context-free. Here's the grammar:

 $S \to A | B|AB|BA$
 $A \to a|aAa|aAb|bAb|bAa$
 $B \to b|aBa|aBb|bBb|bBa$

$A$ generates words of odd length with $a$ in the center. Same for $B$ and $b$.

I'll present a proof that this grammar is correct.  Let $L = \{a,b\}^* \setminus \{ww \mid w \in \{a,b\}^*\}$ (the language in the question).

Theorem. $L = L(S)$.  In other words, this grammar generates the language in the question.

Proof.  This certainly holds for all odd-length words, since this grammar generates all odd-lengths words, as does $L$.  So let's focus on even-length words.

Suppose $x \in L$ has even length.  I'll show that $x \in L(G)$.  In particular, I claim that $x$ can be written in the form $x=uv$, where both $u$ and $v$ have odd length and have different central letters.  Thus $x$ can be derived from either $AB$ or $BA$ (according to whether $u$'s central letter is $a$ or $b$).  Justification of claim: Let the $i$th letter of $x$ be denoted $x_i$, so that $x = x_1 x_2 \cdots x_n$.  Then since $x$ is not in $\{ww \mid w \in \{a,b\}^{n/2}\}$, there must exist some index $i$ such that $x_i \ne x_{i+n/2}$.  Consequently we can take $u = x_1 \cdots x_{2i-1}$ and $v = x_{2i} \cdots x_n$; the central letter of $u$ will be $x_i$, and the central letter of $v$ will be $x_{i+n/2}$, so by construction $u,v$ have different central letters.

Next suppose $x \in L(G)$ has even length.  I'll show that we must have $x \in L$.  If $x$ has even length, it must be derivable from either $AB$ or $BA$; without loss of generality, suppose it is derivable from $AB$, and $x=uv$ where $u$ is derivable from $A$ and $v$ is derivable from $B$.  If $u,v$ have the same lengths, then we must have $u\ne v$ (since they have different central letters), so $x \notin \{ww \mid w \in \{a,b\}^*\}$.  So suppose $u,v$ have different lengths, say length $\ell$ and $n-\ell$ respectively.  Then their central letters are $u_{(\ell+1)/2}$ and $v_{(n-\ell+1)/2}$.  The fact that $u,v$ have different central letters means that $u_{(\ell+1)/2} \ne v_{(n-\ell+1)/2}$.  Since $x=uv$, this means that $x_{(\ell+1)/2} \ne x_{(n+\ell+1)/2}$.  If we attempt to decompose $x$ as $x=ww'$ where $w,w'$ have the same length, then we'll discover that $w_{(\ell+1)/2} = x_{(\ell+1)/2} \ne x_{(n+\ell+1)/2} = w'_{(\ell+1)/2}$, i.e., $w\ne w'$, so $x \notin \{ww \mid w \in \{a,b\}^*\}$.  In particular, it follows that $x \in L$.


Minimize Deterministic Finite Automata with no accepting states I have a finite automaton with no final/accepting states, so F is empty.
How do I minimize it?

I got this on a test and I didn't know how to approach the problem because the automaton had no accepting states.
Is a single initial state with all the transitions into itself the correct answer?

A finite automaton without end states denotes the language L = $ \emptyset $ . To minimize a DFA we minimize the number of states and the denoted language must be the same. By definition of DFA we must have an initial state $ q_0$ so $| Q | \geq  1$ and as you say we need to include the transition function with all transition into $ q_0 $ (because creating dead states is counterproductive).


use of C library in operating systems I wonder, how is that operating systems make use of libraries as stdio.h if they themselves are the services? I am right? Is the operating system that interacts with the hardware to operations of I/O? How you write to a file system with the C library, for example?

The kernel of the system doesn't use the C library (at least not it's I/O facilities).

The kernel does offer system calls like read(3) and write(3) in Unix, and translates them into whatever magic the underlying hardware requires to do this. For example, as a very rough description of how this goes, to write to a serial port, the kernel copies the individual bytes to the serial port's register, signals that a new character is ready to transmit, and waits for it to be shipped off before placing the next one there. To write into a file the kernel keeps track of where the writing to the file has to take place, asks for space in the underlying device if the file will grow, and writes into the allocated space. Each filessystem has its own (rather complex) data structures on disk and in memory to keep track of free and allocated space, and so on. To manipulate it (and the underlying blocks on disk) usually another complex layer talking to the hardware is interposed.

Thus one way of looking at an operating system kernel is as a huge library offering nifty functions (system calls) that allow the programmer to access complex, even under the hood radically different functionalities, by a simple interface. That the programmer uses the convenience of the standard C library, some other language's library, or even chooses to write the system calls directly in assembler, is irrelevant.

The kernel does write messages on occasion. For this it has internal functions (in the case of e.g. Linux it is printk that mimics printf(3)) to do this by tickling the underlying hardware the right way.


Find a string that covers many sets of binary strings with don't-cares Consider $N$ sets $S_1,S_2,....,S_{N}$ of binary strings with don't-cares ($X$) with $|S_i| = n$ and the length of all strings is $m$.
In my application, $N=1000$, $n=100$ and $m=500$.

I have to find atleast one binary string with all set bits (either $1$ or $0$) that is compatible with at least one string of each set. Two strings are compatible if they are bit-wise similar. As we know $X$ bits are similar to both $0$ or $1$. For example, consider string $A=10XX0$ and string $B=X011X$. Here string $A$ and $B$ are compatible with each other.

As we can see, due to the size of each string ($m=500$), it's impossible to find a solution with brute force (i.e. create all possible strings of length $m$ and compare each with all strings of all sets). So, I am looking for a reasonable heuristic to find the solution.

Your problem is NP-hard.  It's basically a variant of SAT.  You shouldn't expect any algorithm that is provably efficient.  Instead, I recommend you use an off-the-shelf SAT solver; since your problem is basically SAT, that's probably about as good as you can do, without a lot of effort tuning for your particular scenario.

NP-hardness: In particular, if every element of every set $S_i$ has exactly $m-1$ don't-cares (has only a single bit set to 0 or 1), then your problem becomes exactly $n$-CNF-SAT with $m$ variables and $N$ clauses.  We know that $n$-CNF-SAT is NP-hard; it follows that this special case of your problem is NP-hard, and thus your problem in general is NP-hard.

Using a SAT solver: Introduce variables $x_1,\dots,x_m$ representing the string you're trying to find.  Then we obtain a formula of the form

$$\Psi(x_1,\dots,x_m) = \bigwedge_{i=1}^N \bigvee_{j=1}^n \phi_{i,j}(x_1,\dots,x_m),$$

where each $\phi_{i,j}$ is a conjunction of literals.  The goal is to find an assignment $x_1,\dots,x_m$ that makes $\Psi(x_1,\dots,x_m)$ true.

You can formulate this as a SAT instance by applying the Tseitin transform.  In other words, introduce variables $y_{i,j}$, then add CNF clauses enforcing that $y_{i,j} = \phi_{i,j}(x_1,\dots,x_m)$ as well as CNF clauses $(y_{i,1} \lor \dots \lor y_{i,n})$ for all $i$.  The Tseitin transform tells you how to add the former clauses.  In particular, you add the clause $(\neg y_{i,j} \lor \neg x_k)$ if the $j$th element of $S_i$ has a 0 in its $k$th bit; add the clause $(\neg y_{i,j} \lor  x_l)$ if the $j$th element of $S_i$ has a 1 in its $l$th bit; and add the clause $(y_{ij} \lor x_k \lor \neg x_l \lor \dots)$ if the $j$th element of $S_i$ has a 0 in its $k$ bit and a 1 in its $l$th bit and so on.  Or, use a SAT front-end that will let you input arbitrary formulas and will do the Tseitin transform for you -- for instance, STP is a nice tool for that purpose.

Then, let the off-the-shelf SAT solver look for a satisfying assignment for you.


Introduction to Algorithms (CLRS) Ex 5.2-5 solution The following is Ex 5.2-5 from Introduction to Algorithms (CLRS), 2nd Edition.

  Let $A[1...n]$ be an array of n distinct numbers. If $i<j$ and $A[i]>A[j]$, then the pair $(i, j)$ is called an inversion of $A$. Suppose that the elements of $A$ form a uniform random permutation of $<1,...,n>$. Use indicator random variables to compute the expected number of inversions.

The solution from https://walkccc.github.io/CLRS/Chap05/5.2/ says:

  Let $X_{ij}$ be an indicator random variable for the event where the pair $A[i], A[j]$ for $i < j$ is inverted. We have $\Pr\{X_{ij} = 1\} = \frac{1}{2} $, because given two distinct random numbers, the probability that the first is bigger than the second is $\frac{1}{2}$.

I would like to ask what is the rationale for $\Pr\{X_{ij} = 1\} = \frac{1}{2}$. I know that there can be only 2 outcomes, either be $X_{ij} =1$ or $X_{ij}=0$. Also, $\Pr\{X_{ij} = 1\}+\Pr\{X_{ij} = 0\}=1$.

After looking at the answer, it kind of make sense, but I would like to ask if there is a more "systematic" way to derive/justify this probability. Note that I am being very vague about the meaning of systematic because I simply would like to have a more reliable way of deriving this probability rather than only relying on intuition.

For a permutation $\pi$, let $\pi(i\;j)$ be the permutation obtained by switching the places of elements $i$ and $j$. Since $\pi(i\;j)(i\;j) = \pi$, we can partition the set of all permutations over the elements of $A$, into $n!/2$ pairs $\{\pi,\pi(i\;j)\}$.

Consider what happens to $A$ after permuting by $\pi$ and by $\pi(i\;j)$. In exactly one of these cases, the pair $(i,j)$ is an inversion. Therefore the pair $(i,j)$ is an inversion for exactly $n!/2$ of the permutations, i.e., with probability exactly $1/2$.


What are 'Butterfly Combinations' and why are they called this way? In some scientific work describing Discrete Fourier Transform-algorithms, such as the well-known Cooley-Tukey algorithm, I came across the term 'Butterfly operations' and 'Butterfly combinations', which seem to refer to the fact that an algorithm takes elements that are half an array away (where the array itself is a power-of-two in size), which mean that if you want to write an iterative implementation, that you will have to bit-reverse the indices of the input (or the output).

Is this indeed what is called 'Butterfly combinations'? And why are these called 'Butterfly combinations'? What is the origin of this name?

So, a summary of the Wikipedia page on Butterfly Diagrams:

In Computing Science, a Butterfly is the portion of a computation that combines the results of (two) smaller computations into the larger one.
This is common in Discrete Fourier Transformation algorithms, as well as in the otherwise unrelated Viterbi Algorithm for finding the most likely sequence of hidden states.
It is called 'Butterfly' because of how it works in the base case where you combine two single-point results: (Image courtesy of Wikipedia)
The earliest occurrence in print of the term 'Butterfly' is thought to be in a 1969 MIT technical report: C. J. Weinstein (1969-11-21). Quantization Effects in Digital Filters.


Defining L(G) in set notation Let G be the grammar:

S --> ASB | λ

A --> aAb | λ

B --> bBa | ba

Use set notation to define L(G).

So I came across two different answers to this question, none of which are mine, and then compared them to mine. I'm wondering if they are all equivalent.

Answer 1: $L(G) = \{a^{n_1}b^{n_1}...a^{n_k}b^{n_k}b^{m_1}a^{m_1}...b^{m_l}a^{m_l} | n_i, m_j > 0, l \ge 0, k \ge 0, k \le l\}$

Answer 2: $L(G) = \{(a^{n}b^{n})^i(b^{m}a^{m})^i |  n \ge 0, m > 0, i \ge 0\}$

My answer: $L(G) = \{(a^{n}b^{n})^k(b^{m}a^{m})^l |  n, k, l \ge 0, m > 0\}$

My answer seems similar to the second one. Are all three of these correct for this grammar?

They are not all equivalent.

Strings in the expression $(a^nb^n)^k$ have several (i.e., $k$) copies of the same string $a^nb^n$, whereas in $a^{n_1}b^{n_1}\dots a^{n_k}b^{n_k}$ the number of letters in each $a^{n_i}b^{n_i}$ may differ.

As $aaabbbaaabbbaaabbb$ versus $aabbaaaabbbbab$.

A shorter way of denoting words with different numbers would be
$\{ a^nb^n \mid n\ge0\}^*$.

Now check out your three languages and the given grammar.


How to show that f(x) is primitive recursive? Let

  $$f(x)=\begin{cases} x \quad \text{if Goldbach's conjecture is true
 }\\ 0 \quad \text{otherwise}\end{cases}$$

  Show that f(x) is primitive recursive.

I know a primitive recursive function is obtained by composition or recursion, but I don't know what should I do about this problem.

Goldbach's conjecture is either true or false. Do a case analysis on the two possibilities. In one case, $f(x)=x$, which is primitive recursive. In the other case, $f(x)=0$, which is also primitive recursive. Therefore $f$ is primitive recursive.


Given regular expression construct regex for the complement language Disclamer: this is my uni assignment, which is rated comparatively low, thus I assume that the answer should be simple.  Hints are appreciated (as opposed to direct answers).

  Write an algorithm which accepts a regular expression $r$ and produces a language $\overline{L[r]}$.

I think it is reasonable to assume that all operations I need to consider are just the concatenation, union and Kleene star.  For simplicity, I assumed the alphabet to be $\{a,b,c\}$.  I also think that I can invert individual operations as follows:

$a^* \to (a^*(b+c))^+$.
$(a+b) \to (\epsilon+(c(a+b+c)^*))$.
$ab \to \epsilon+((aa+b+c)(a+b+c)^*)$.

But attempting to combine these operations produces wrong results, for example:

$$
a^*b^* \to \\
(a^*(b+c))^+(b^*(a+c))^+ \to \\
(\epsilon+((a^*(b+c))^+(a^*(b+c))^++b+c)(a+b+c)^*)(\epsilon+((b^*(a+c))^++a+c)(a+b+c)^*))
$$

doesn't seem to do what I expect it to because, for example, it will match the empty string on both sides.

Should I perhaps consider transforming the regexp into DFA and "inverting" the DFA instead?

The problem with your attempt is that you've only looked at what happens when the regexp to transform is a simple one. For example, you've looked at what the complement of $a^*$ looks at. But in order to write a compositional complementation algorithm, you need to figure out how to compute a regular expression that recognizes the complement of the language of $r^*$, for an arbitrary regular expression $r$.

The bad news is that your approach to build a complement for $a^*$ does not generalize easily. Consider for example the regular expression $(a + b + c)$. A regular expression that recognizes its complement language is $\epsilon + (a + b + c) (a + b + c) (a + b + c)^*$ — but this isn't really useful to know if you're looking for the complement of $(a + b + c)^*$, which is the empty language. You can't reach the complement of $(a+b+c)^*$ from starring something related to the complement of $(a+b+c)$.

You can approach this problem by adding a complement operator to regular expressions, in which case the algorithm you're looking for is an algorithm to remove the complement operator from such generalized regular expressions. It turns out that this brings you close to an open problem, the generalized star height problem: it's unknown whether you can eliminate nested stars in such generalized regular expressions, which shows that the interaction between the star operator and the complement operator is poorly understood.

Your idea of transforming the regular expression into a DFA and back is a good one. It's perfectly reasonable a different representation of an object where the operation you're interested in is easier. In fact, this is the usual algorithm to find a regular expression for the complement language of a regular expression:

Build a DFA that recognizes the language of the regular expression.
Transform the DFA into one that recognizes the complement language.
Build a regular expression whose language is that of the second DFA.

   Step 2 is very easy: just swap accepting and non-accepting states. Note that this doesn't work on an NFA!


Kiln optimization problem Say I have a kiln for making castings. There are 3 shapes. I need to produce the following castings:

102 of A

364 of B

70 of C

I can put 50 molds in the kiln at a time.
I can have 75 molds made in any combination.

First, what is the optimal combination of molds to make.

Second, what is the schedule to make the castings in as few firings as possible.

I am trying to wrap my head around this problem. I see that the second part resembles task scheduling problems I've read about, but I have no idea how to tackle the first problem.

Any help/insight very much appreciated.

Either there is an additional constraint, either this problem is far more simpler than task scheduling.

Well you have to identify the limiting criterium of your problem which is 50 molds maximum in the kiln.

Let's call S = A+B+C = 536, the total number of molds. So You cannot do better than 11 firings (11*50=550).

First compute the euclidean division of the required elements to get the quotient and the remainder, that will be the constant molds and the variable molds to use.

- x, a = A/11 = 9, 3
- y, b = B/11 = 33, 1
- z, c = C/11 = 6, 4

So the constant molds are (x, y, z) = (9, 33, 6), that is to say 48 molds.

You now have 11 firings on the 2 (50-48) variables molds to complete the (a, b, c) = (3, 1, 4) remaining elements.
Let's say we want to minimize the number of molds to manipulate. Then just take one extra mold of each A, B, C to have a total of 51 molds.


Recipe book for SAT encodings? SAT solvers are getting more and more efficient in solving large instances and are being used as back-ends in various contexts.
Every time one wants to use them to solve a problem in a specific domain, he/she has to come up with an ad-hoc encoding that not only has the right set of solutions but also puts the constraints (even redundant) in a form that helps the heuristics of solvers in finding a solution faster.

Many such encodings seem to me would be very common, for example: asserting that a finite set of nodes is linked as a tree, or as a DAG, or a list is sorted...

Is there a repository/recipe book of common encodings for common problems with optimised solutions?

I read a survey paper a few years ago that seems relevant, "Successful SAT Encoding Techniques" by Magnus Björk.
Abstract:

This article identifies good practices for SAT encodings by analysing interviews with a number of well known SAT experts.  The purpose is both to determine the confidence in different encoding strategies by analysing whether there is consensus among the experts or not, as well as bringing out hidden knowledge to SAT users.
There is consensus that encoding techniques usually have a dramatic impact on the efficiency of the SAT solver, that it often takes much work to find a good encoding, and that the size of an enconding is only very loosely related to the hardness of finding a solution.  Topics where the interviewees disagree include the feasibility of including arithmetics in SAT problems and whether to formulate problems as clauses or circuits.
The article describes a number of strategies that are good in different situations, such as different ways to represent numbers and how to use incrementality.


Can we enumerate provably non-terminating functions? In trying to understand the Halting Problem better, I am trying to come up with classes of provably non-terminating programs.

For example, any program (including input) which leads to a finite-length infinite loop (with perfectly repeating state+tape) should be detectable. That leaves mostly induction/search problems like "get the first non-Goldbach even number above 4" as candidates.

Clearly, some of these halt, and some can be proven non-halting (eg we know "find $n$ such that $n\cdot 0=5$ " and "find a proof that the Poincare Conjecture is false" would not halt). More generally, it seems every non-halting problem corresponds to a Diophantine equation which (provably or not) has no solutions. This leads to a seemingly fairly general algorithm to find many non-halting programs:

Convert Turing machine to corresponding Diophantine equation with one unknown
Feed the equation, along with First-Order Peano Arithmetic, to Prolog/Isabelle/your favorite proof assistant
Assert the existence of a solution
Derive 0=1

So, my questions:

Is there a more natural way to search for such contradictions using the formalism of Turing Machines (or some other more conventional model of computation), without converting to Diophantine equations?
Are there provably non-terminating functions that can be found using some other algorithm, but not this one? What algorithm(s)? Would that require a "stronger" version of arithmetic?
If there are such algorithms, is there any notion of a "biggest" class of provably non-halting programs, or would that somehow lead to solving the Halting Problem (or some other contradiction)?
Are there any good references/keywords for this? I've searched for "provably non-terminating functions", but haven't come up with much

PS Feel free to fix/reformat anything, alert me to obvious theoretical mistakes, or let me know if this is a bad question.

EDIT: Some points to address responses so far:

I know that it's "easy" to prove that a program halts--just run it until it does; the challenge is to prove that a program does not halt, which obviously isn't always possible.
Re: D.W.♦, I know we can't enumerate all non-halting programs, and I know we can come up with many provable examples of non-terminating functions, I'm asking if there's a most general method of finding all non-halting programs that can be found/proven
I am aware of the Curry-Howard correspondance that directly relates programs and mathematical proofs. However, because of the halting problem there can be no type for "non-terminating programs", and it's not immediately obvious how to type "provably non-terminating" either
@chi's answer is exactly what I am looking for. To make sure I understand fully, let me restate my understanding of your enumeration of non-terminating programs, using the simplest possible axioms I can think of:

Start with a basic definition of "strings" in pure First-Order Logic: 0,1,add0,add1,equality
Define Turing machines using a rewrite relation on strings that captures the mechanics of a calculation step (ie, eval)
Define big-step calculation $\rightarrow$ as the transitive closure of one-step eval
Define a halting predicate as the existence of a fixed point
For a given program $x$, prove $\forall y.x\rightarrow y\Rightarrow \exists z\ne y.y\rightarrow z$

So, would the above work? Is it equivalent to my Diophantine equation scheme? Is there a yet simpler version? Would more axioms (eg using naturals under Peano Arithmetic to encode the machines) be able to prove more non-terminating programs than this version, ie is there a more general method?

Here is a simple non-terminating function:

while (true):
    do nothing

This certainly does not terminate.

On the other hand, it is not possible to enumerate all non-terminating functions.  The halting problem is recursively enumerable but not decidable, from which it follows that the complement of the halting problem is not recursively enumerable (if it were, the halting problem would be decidable).  See https://en.wikipedia.org/wiki/Recursively_enumerable_language and https://en.wikipedia.org/wiki/RE_%28complexity%29.


Is it possible to easily reduce 0/1 subset sum to subset sum with multiplicities? So both the 0/1 subset sum problem (find a subset of given numbers that add up to a target sum) and the subset sum problem with "multiplicities" (find non-negative integer coefficients for the set elements so that the linear combination of set elements equals a target sum) are NP-complete. Is there some fairly easy reduction from 0/1 subset-sum to subset sum with multiplicities? This seems perhaps non-trivial, because just because there is a solution with multiplicities doesn't mean there is a 0/1 solution.

Some ideas I had that don't seem to work: For element $s$, solve the subset sum with multiplicity problem both for total sum $S$ and $S-s$ with element $s$ removed from the set. Then try to argue that $s$ either is or is not included in the 0/1 solution depending on the answer.

This answer on CSTheory describes a reduction from 0/1 subset-sum to the unbounded knapsack problem (UKP).  That does exactly what you want.  The intuition is that UKP is basically subset sum with multiplicities, since UKP lets you put as many copies of an item as you want into your knapsack.


Automaton recognizing ambiguously accepted words of another automaton Let $A$ be a nondeterministic automaton. Let $X(A)$ the set of words for which there at least two accepting paths.

In one of the previous exam, for which no answers are available, it is required to prove that there exist a deterministic automaton whose language is $X(A)$. Furthermore, if the original automaton has $k$ states, then the new automaton should have $3^k$ states.

I have tried multiples approaches to no avail:

Make an automata that keeps track of which path was taken, but the size of the automata grew infinitely because of cycles...
An automaton for each state I also kept track of which state it came from, but it was just a scaled down version of previous attempt. Which didn't work if the path started to converge early.
Tried an automaton where I encoded each state with the set of all the states from automaton $A$. And for each state I included whether I went through that state 0, 1 or more than 2 times.

Construct an NFA which will simulate (nodeterministically) two runs of the original NFA on the input. The NFA also remembers one bit – whether the two runs have diverged so far or not. If the bit is off and the NFA chooses two different transitions, then you turn it on. The NFA accepts if both runs accept and the bit is on.

If the original NFA has $k$ states, then the new NFA will have $2k^2$ states. You can convert it to a DFA with $4^{k^2}$ states.

We can reduce the number of states in the corresponding DFA by performing the powerset construction directly. At each step, we will remember, for each step, whether (i) it is impossible to be at that state, (ii) it is possible to be at that state, but there is a unique such run, (iii) it is possible to be at the state, and there are at least two such runs. A state is accepting if there is an accepting states of type (iii), or at least two accepting states of type (ii). This construction uses only $3^k$ states, and so matches your hint.


How can Turing complete machines exist theoretically if the halting problem is undecidable As the question says, if I input on the tape of a Turing complete machine a program that solves the halting problem with the correct inputs the program will never end its execution regardless of memory and time. Isn't the halting problem a computational problem that can't be executed by a Turing complete machine so that it's halts sometime?

The halting problem is the problem of deciding whether a given Turing machine halts on a given input or not.

This problem is undecidable, meaning that no program running on a Turing machine can solve this problem for all possible inputs. Hence, your assumption that such a program exists is wrong.