Why cannot we enumerate all Turing machines that have no fixed point? The language

$$
L_1 = \{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon M_w(x) = x\}
$$

($w$ is an encoding of a DTM, $M_w$ is the respective DTM.)

is not decidable, according to Rice's theorem. However, it is recursively enumerable: an NTM simply chooses an $x$ for which the condition is fulfilled non-deterministically.

Consider the very similar language

$$
L_2 = \{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon M_w(x) \neq x\}
$$

Rice's theorem argues that this is undecidable, but neither is it semi-decidable according to my sources.

Why can't we argue for $L_2$ as we did for $L_1$, stating that an NTM chooses the input $x$ non-deterministically, the condition is fulfilled, $L_2 \in \mathsf{RE}$?

The proof that $L_2 \not\in \mathsf{RE}$ performs the reduction $\overline H \leq L_2$, where $H$ is the halting problem. I understand this proof by reduction, but to me, it seems contradictory to the argument for recursive enumerability I give above.

Because we cannot find, given a NTM $N$ and an input $x$, whether $N$ fulfills the condition $N(x)\not= x$ in any given finite amount of time. More precisely, we cannot enumerate all pairs $(N,x)$ such that $N(x)\not= x$, although we can enumerate all pairs $(N,x)$ such that $N$ halts on $x$ and $N(x)\not= x$.

Think for a moment. When can you consider $(N,x)$ fulfills the requirement $N(x)\not=x$?

We run $N$ with input $x$ for some time and it stops. If it does not output $x$, great, we have found one.
We run $N$ with input $x$. However $N$ does not stop yet. It seems $N$ just won't stop. We want very much to say $(N,x)$ does not fulfill that requirement; however, there is no moment we can be sure of that. $N$ is just running at all times. If we conclude $(N,x)$ does fulfill the requirement at some moment, it can happen $N$ will stop at the next moment, outputting $x$. Because of this possibility, we will never add $(N,x)$ when $N$ never stops on input $x$, even though $(N,x)$ does satisfy the requirement.

Note this is vastly different from the other case. When can we consider $(N,x)$ fulfils the requirement $N(x)=x$?

We run $N$ with input $x$ for some time and it stops. If it does output $x$, great, we have found one.
We run $N$ with input $x$. However $N$ does not stop yet. Fine, we just do not consider $(N,x)$ fulfils the requirement yet. Continue running $N$.

You might argue that NTM $N$ can guess $x$ such that $N(x)$ will halt and output $y\not=x$. So we will find one such $N$.
There is no problem in that.

However, consider the case when $N$ never stops on every input. Now, imagine the exact moment you consider that $N$ fulfills the condition that $N(x)\not= x$ for some $x$, using any  algorithm. What is known to you at that moment? All you know is that $N$ has not stopped yet on any input. That, however, does not exclude the possibility that $N$ might stop later on for all inputs along all paths, always outputting the input. We can never exclude that possibility, forever. (More precisely, we can exclude that possibility for some $N$ for some inputs. However, there is no algorithm can determine that possibility for all $N$.)

  If I chose a DTM in place of an NTM to run $M_w(x)$ for all possible inputs, it would be game over if $M_w(x)$ didn't halt because that would prevent subsequent runs of $M_w(x)$ with different $x$es.

It would also be game over if $M_w(x)$ will not halt for all $x$. Your $NTM$ will be running forever without ever outputting anything. That $(M,x)$ is in $L_2$ but your algorithm cannot claim it is in $L_2$ since there is no moment when the algorithm is able to claim that.

The explanation above is meant to be a way to understand the situation. A rigorous proof is still needed to confirm the conclusion mathematically (or "compute sciencely"). Since you have known a rigorous proof, I will not provide one here.


Do the newest computers still have ROM? Now that many computers use UEFI instead of BIOS to boot the computer, and UEFI instructions are usually stored in a hidden hard disk partition, does this mean the newest computers do not need to have ROM, which is used to store BIOS program in the old days? Or, was ROM unnecessary long ago even before UEFI existed, as BIOS program and settings were stored in flash memory (so as to store the changes in settings by user)?

Yes, or maybe no, depending on your definitions. Commonly some small 8-pin SPI NOR-Flash ROM is used, for example my slightly older motherboard has a W25Q64FV. This replaces the older non-flash based EEPROM technology since Flash is cheaper, but it fills the same role, and often the flash versions are still called EEPROM. Since it's Flash memory, you could call that "not ROM", if your definition of ROM excludes Flash.
An other problem with relying on a disk is that a disk cannot come pre-programmed correctly. It needs to contain code specific for the motherboard, and be pre-loaded with microcode for the various diffent CPU models supported by that motherboard (which is why recently AMD motherboard manufacturers had some trouble). A disk does not know which motherboard it ends up in, so it cannot fill this role.


Eligibility trace and the role of gamma and lambda From R.Sutton's book, the eligibility trace update rule is:
$$
E_t(s)\leftarrow\gamma~\lambda~ E_{t-1}(s)+\mathbb{1}(S_t=s)
$$
I wonder why do we need both $\gamma$ and $\lambda$ to assign credit to most recent states.

At least for gamma I can answer it generally without looking in the book:

Gamma is commonly used as the discount factor. That is a number in (0, 1) which defines how much of the reward you got in step i will be also given to step (i - n). Commonly, the reward is discounted exponentially (like gamma^n)


Solving " Tricolor Arrangement " Efficiently A rectangular board with three rows and $n$ columns is filled with $3n$ counters, of which $n$ are red, $n$ are white, and $n$ are blue. The object is to rearrange the counters to have counters of each of the three different colors in every column. The only operation allowed is to swap counters in the same row. Design an algorithm to accomplish such a task or prove that such an algorithm does not exist.

Let $\mathcal{O}(1)$ be the cost of swapping the counters in the same row.

Iterate over each column. Let us consider that up to column $i-1$, we are done. Now we are at column $i$, there will be three counters, if they are of different colors then we are done, else fix one counter ( say white ) and scan other two rows to get two different color counters ( red and blue ). Running the previous step for a constant number of times ( six ) will solve the problem. More precisely there will be six possibilities in each column (123,132,.....,321), so I will try each of those.

The runtime of the above algorithm will be $\mathcal{O}(n^3)$ as there are $n$ columns and time spent on each column is $\mathcal{O}(n^2)$.

Question: Is it possible to solve the above-described problem linear time $\mathcal{O}(n)$ time as input here has size $\mathcal{O}(n)$? I am not even able to come up with an algorithm faster than $\mathcal{O}(n^3)$ time.

I have taken this question from the book titled Algorithmic Puzzles ( problem 46 )

Here is an algorithm with $O(n)$ time-complexity.

First, count how many counters of each color there are on each row. With $O(n)$ time, we will obtain the number of red counters $r_i$, the number of white counters $w_i$, the number of blue counters $b_i$ on row $i$, $i=1,2,3$.

Second, we can solve the following equations for nonnegative integer variables $a_k$, $1\le k\le6$ in $O(1)$ time.

$$r_1 = a_1 + a_2$$
$$w_1 = a_3 + a_4$$
$$b_1 = a_5 + a_6$$
$$r_2 = a_4 + a_5$$
$$w_2 = a_1 + a_6$$
$$b_2 = a_2 + a_3$$
$$r_3 = a_3 + a_6$$
$$w_3 = a_2 + a_5$$
$$b_3 = a_1 + a_4$$

Third, we arrange the three rows into the following configuration.
$$
\begin{array}{|l|l|l|l|l|l|} \hline
    a_1\text{ red} & a_2\text{ red} & a_3\text{ white} & a_4\text{ white} & a_5\text{ blue} & a_6\text{ blue}  \\\hline
    a_1\text{ white} & a_2\text{ blue} & a_3\text{ blue} & a_4\text{ red} & a_5\text{ red} & a_6\text{ white}  \\\hline
    a_1\text{ blue} & a_2\text{ white} & a_3\text{ red} & a_4\text{ blue} & a_5\text{ white} & a_6\text{ red}  \\\hline
\end{array}
$$

We are done.

Here are a couple of exercises that fill the gap in the above specification of the algorithm.

Exercise 1. Find an algorithm that solves in $O(1)$ time that system of 9 equations for nonnegative integer variables $a_k$, $1\le k\le6$, given the condition that $r_i+w_i+b_i=n$ for all $i$ and $\sum_{i=1}^3r_i=\sum_{i=1}^3w_i=\sum_{i=1}^3b_i=n$. Show that there is always a solution.

Exercise 2. Check that arrangement in third step can be done in $O(n)$ time by swapping the counters in each row.

Here is a problem that may not be easy to do.

Problem 1. Generalize the problem of tricolor arrangement to $m$ rows and $m$ colors, $m>3$. Solve it with an $O(n)$ algorithm, assuming $m$ is a constant.  (Hint, use Hall's marriage theorem to reduce the sum of the number of distinct colors in each row.)


Existence of Pseudorandom Generator How to show that for $\epsilon>0$, there exists a function $G:\{0,1\}^n->\{0,1\}^{2^{\epsilon n}}$ that is a $2^{\epsilon n}$-prg, without the condition that is is computable in $2^{O(n)}$ time. What I am trying to show is with high probability, if we take $\epsilon=1/10$, a random $G$ satisfies this condition. But in order to show that, we need to show, no circuits of size $<2^{3/10n}$ are able to distinguish between uniform distribution of length $2^{n/10}$ and output of $G$. This I am not able to get. Can anyone give me an approach?

If you choose $G$ from the uniform random distribution on $\{0, 1\}^n \to \{0, 1\}^{2^{\epsilon n}}$ without restrictions, then nothing can (correctly) distinguish between the uniform distribution and the output of $G$, because you made it uniformly random by definition. At this point the output of $G$ is no longer pseudo-random, it is random.


What algorithm should I use to find the closest solution to a given total using a list of integers? My problem is this:
Let's say I have an arbitrary list of integers A[2013, 54, 3, 32 1, 23...]
What is the best strategy to find which of those numbers I should add together to have a sum equal or closest to a given number ?
Obviously there is always the brute force method but I'm interested in knowing if there is a more optimised one.

When packing luggage into a car, you put the biggest items in first and then fit the smaller items around them. By analogy, a heuristic approach to your problem is to start with the member of your set that is as large as possible while still being smaller than your target. Then repeat the process for the difference between you current total and your target, and so on. This is known as a greedy algorithm.
For example, if your set is $\{2,3,5,8,13,21, 34\}$ and you target is $32$, start with $21$ (the largest value less than $32$), then add $8$ (because this is the large value less than $32-21=11$), and then add $3$.
A greedy algorithm is quick and simple, but will not always give you the best solution. For example, if your set is $\{1, 5, 23, 26\}$ and you target is $30$ then the greedy algorithm gives $26+1=27$, whereas the best solution is $23+5+1=29$.


Data structure for getting the k'th largest element I'm given a set of $n$ numbers. Is there a data structure that builds in $O(n)$ (linear time) and gets the $k$'th largest element in $O(k)$ time? Also, is there anything better than $O(k)$?

Here is a solution that uses only comparisons. For simplicity, assume that $n$ is a power of 2.

Find the median of the original array in $O(n)$, and extract the largest $n/2$ elements. Then find the median of the new array in $O(n/2)$, and extract the largest $n/4$ elements. Continue in this way, extracting the $n/8,n/16,\ldots,1$ largest elements. In total, preprocessing takes time
$$ O(n+n/2+n/4+\cdots) = O(2n) = O(n). $$

Given $k$, find $\ell$ such that $n/2^{\ell+1} < k \leq n/2^{\ell}$. By construction, $n/2^\ell < 2k$. The $k$th largest element is thus one of the $n/2^{\ell}$ largest elements. Using the linear time selection algorithm, locate the $k$th element among them in $O(n/2^\ell) = O(k)$.

We can improve the running time for $k \leq Cn/\log n$ (for arbitrary $C$) to $O(1)$ as follows.

During preprocessing, use a linear time selection algorithm to locate the $Cn/\log n$-th largest element in $O(n)$, and extract all larger elements. Sort them in $O(n)$.

During query time, locate the $k$th largest element for $k \leq Cn/\log n$ in $O(1)$ using the new array.

Conversely, we can show that this $O(1)$ behavior cannot extend beyond $O(n/\log n)$ for comparison-based algorithms. Indeed, suppose that there is an algorithm which preprocesses an array in $O(n)$, and is able to locate the $k$th element in $O(1)$ for $k \leq f(n)$, where $f(n) = \omega(n/\log n)$. This allows us to sort an array of size $f(n)$ in time $O(n) + O(f(n)) = o(f(n) \log f(n))$ by adding $n - f(n)$ dummy elements, contradicting the well-known lower bound for sorting.


Maximum Independent Set of special Directed Graph I was given this special type of Directed Graph and was asked to find it's Maximum Independent Set.
Graph Properties :

Graph has $N$ vertices and $N$ edges
There can be no edge from a vertex $v$ to itself
Each vertex $v$ has only 1 outgoing edge and 0 or more incoming edges

I framed this problem as a linked list with potentially some cycles. So far I've tried a DFS approach, two Greedy ones and right now I am thinking of a DP one trying to convert the linked list to a Binary Tree by removing the cycles somehow.
All of the approaches below respect the fact that there can be no edges between vertices of the under construction independent set.So when a vertex is under consideration to be a member of it I check if it points to a vertex of the under construction independent set.
First Greedy approach :
Sort the vertices based on the number of incoming edges and keep taking the ones with the least incoming edges let's call them $v_1,v_2...$ as well as the ones who point where $v_1,v_2...$ do as they are basically free and so on.
Second Greedy approach :
Take the ones with no incoming edges let's call them $z_1,z_2...$ as well as the ones who point where $z_1,z_2...$ do as they are basically free as well and from there see which vertices have the most incoming edges and take the ones who point at them.
Both approaches seem to fail by 1 in some test cases.
As for the DFS one it was something like take 2 a time where in $v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4 \rightarrow v_5$ I would take $v_1,v_3,v_5..$ and so on.
I also tried prioritizing the ones with 0 incoming edges in the DFS approach but no luck and I think I am in the right direction but I am missing a small detail.
Any thoughts or insight would be really helpful.

The type of graph you are describing is identical to the one encountered in Pollard's rho algorithm. Connected components of your graph are cycles with directed trees feeding into them (possibly none). It follows that it suffices to solve your problem for such graphs.
The first step is to compute, for each directed tree, the maximum size of an independent set, depending on whether the root is included or not. Denote the maximum size of an independent set in the first case by $\alpha_+(T)$, and in the second case by $\alpha_-(T)$, and let $\alpha(T) = \max(\alpha_+(T),\alpha_-(T))$. If $T$ is a single vertex then $\alpha_+(T) = 1$ and $\alpha_-(T) = 0$. If $T$ is composed of a root and subtrees $T_1,\ldots,T_d$, then $\alpha_+(T) = \alpha_-(T_1) + \cdots + \alpha_-(T_d) + 1$, and $\alpha_-(T) = \alpha(T_1) + \cdots + \alpha(T_d)$.
Now suppose that we have a cycle of length $\ell$, and let $T_1,\ldots,T_\ell$ be the directed trees whose roots are the vertices of the cycle (the trees could be single vertices). Let $\alpha_{\pm_1,\pm_2,i}$ be the maximum size of an independent set in $T_1,\ldots,T_i$ which contains the root of $T_1$ according to the first $\pm$, the root of $T_i$ according to the second $\pm$, and which doesn't contain two adjacent roots. First, $\alpha_{\pm,\pm,1} = \alpha_\pm(T_1)$, and $\alpha_{\pm,\mp,1} = 0$. Second, $\alpha_{\pm,+,i+1} = \alpha_{\pm,-,i} + \alpha_+(T_{i+1})$ and $\alpha_{\pm,-,i+1} = \max(\alpha_{\pm,+,i},\alpha_{\pm,-,i}) + \alpha_-(T_{i+1})$. Finally, the maximum size of an independent set of the entire component is $\max(\alpha_{+,-,\ell},\alpha_{-,+,\ell},\alpha_{-,-,\ell})$.


Find maximal difference between two consecutive numbers You are given $n$ real (unsorted) numbers $_1,_2,...,x_n$. We want to compute the maximal difference between two consecutive numbers in sorted order. Explain how to do it in $()$ time when you are allowed to use additions, subtractions, multiplications, divisions and “floor” function. Notice that sorting immediately leads to $( log)$ time.
Please help !

Determine the minimum $a$ and maximum $b$ in a first pass.
Create $n+1$ buckets, each of width $\frac{b-a}{n+1}$, with the first beginning at $a$. We have $n+1$ buckets and only $n$ points, so by the pigeonhole principle, there must be at least one empty bucket. Since we know that the first and last buckets contain at least one point, we know furthermore that there must be an empty bucket with a nonempty bucket somewhere to its left and another nonempty bucket somewhere to its right, implying that the solution must be at least $\frac{b-a}{n+1}$.
This means that no two points within the same bucket can provide the solution, since they must be strictly less than $\frac{b-a}{n+1}$ apart from each other. So, any solution will consist of a pair of points from different buckets.
A valid solution must consist of the rightmost point from some bucket $i$ and the leftmost point from some bucket $j > i$ with all buckets in between (which may be no buckets at all, when $j=i+1$) empty. So it is sufficient to know, for each bucket, its leftmost and rightmost points.
To compute these, iterate through all the points again, updating the leftmost and rightmost positions of the current point's bucket whenever necessary. (For the first point in a bucket, both of these positions will need to be updated.) A point's bucket can be computed by subtracting $a$ and dividing by $\frac{b-a}{n+1}$.
Finally, iterate through all the buckets, keeping track of the rightmost point in the last nonempty bucket seen, and comparing it with the leftmost point in the current bucket: Update the maximum whenever this exceeds the current maximum.


Proof of correctness for a triangulation-algorithm I'm working on the following exercise:

  Consider a point set $S = \{ p_1, p_2, ..., p_n \}$ in the plane in general position (i.e., no three points of $S$ are collinear). The points of $S$ have pairwise different $y$-coordinates and are sorted in increasing order of them, i.e., $y(p_i) < y(p_j) $ if and only if $i < j$.
  Develop an algorithm that computes a triangulation of $S$ and needs $O(n)$ runtime and memory.

I got the following algorithm (based on Andrew's monotone chain algorithm) from Marcelo Fornet in his answer to one of my previous questions (I condensed it a bit):

Input: a list P of points in the plane.

Precondition: There must be at least 3 points.

# Initialize T as empty list to store triangulation
Initialize U and L as empty lists.
The lists will hold the vertices of upper and lower hulls respectively.

for i = 1, 2, ..., n:
    while L contains at least two points and the sequence of last two points
            of L and the point P[i] does not make a counter-clockwise turn:
        Add the last two points from L and P[i] to T (the triangulation)
        remove the last point from L
    append P[i] to L

for i = n, n-1, ..., 1:
    while U contains at least two points and the sequence of last two points
            of U and the point P[i] does not make a counter-clockwise turn:
        # Add last two points from U and P[i] to T (the triangulation)
        remove the last point from U
    append P[i] to U

The triples of points in T will be the triangles

While I understand how this algorithm works I'm struggeling to show it's correctness in a formal way.

My idea would be to use induction on the invariant that this algorithm always prodcuces a triangulation of the given point set. This is what I tried:

Assertion: The said algorithm always returns a triangulation for a given point set.

The assertion is clear for a set of three points, so we got our induction start.

Now lets suppose the assertion holds for all sets with at most n points.

But I'm stuck at the induction step. I tried to make a case analysis wether the new point $p_{n+1}$ lies in the upper or the lower half of the convex hull of $\{p_1,....,p_n\}$, but it didn't work out.

I'd be thankful for any kind of help.

I am here again :)
I prove it by induction as you already did. But instead of assuming that the new point is in the lower/upper hull, I assume that the point is the rightmost one (a stronger condition), so it will belong to both, lower and upper hull.
Applying euler formula we know that the total amount of triangles in a valid triangulation is $2\cdot n − h − 2$. Where $n$ is the amount of points and $h$ is the amount of points in the convex hull.
I change a bit the algorithm I proposed you before. Instead of making one sweep from left to right to build the upper hull and one from right to left to build the lower hull, lets build the lower hull with a sweep from left to right too, but this time changing the counter-clockwise condition for clockwise.
Applying the above algorithm to build the triangulation with this slightly new approach will lead you to the same solution. Let's work again on the induction, but this time assuming the new point is the rightmost one and prove the euler condition holds.

Assertion: The said algorithm always returns a triangulation for a given point set.
The assertion is clear for a set of three points, so we got our induction start.
Now lets suppose the assertion holds for all sets with at most n points.
The total number of triangles is $2n - h - 2$
When you add a point in the rightmost position the amount of points will be $n_1=n+1$ and the amount of points in the convex hull will be $h_1 = h + 2 - t$ where $t$ is the total number of added triangles. The total number of triangles we are expecting is:
$$2 \cdot n_1 - h_1 - 2 = 2 \cdot (n + 1) - (h + 2 - t) - 2$$
$$ =(2 \cdot n - h - 2) + t $$
Then the number of triangles that we have built in this last step is $t$ which implies that we have all triangles we need in the solution. Check the picture to get an intuitive idea about what is happening.

I have coded this solution in Codeforces problem, but I can't find it right now :(


Is Rice's Theorem equivalent to the Halting problem? As I understand it Rice's Theorem seems to imply the existence of the Halting problem. That is, with Rice's Theorem, we can prove that the Halting problem is undecidable. However, to me, it seems like one could write a proof using that the Halting problem is undecidable to show Rice's Theorem. I'm not exactly sure how one would go about proving such a thing (though it seems by contradiction would be the natural thing to do), but it feels to me that that it should be possible?

Yes, you can prove Rice's theorem by reduction from the Halting problem.  See https://en.wikipedia.org/wiki/Rice%27s_theorem#Proof_by_reduction_from_the_halting_problem.
The reverse direction is also provable and is trivial.
In some sense all statements that true and provable are equivalent, in the sense that you can prove any by starting from any other, but that probably isn't a useful observation.


Loop Invariant summation So I am stuck:

I have this algorithm from which I need to find a loop invariant but I just can't get my head around it :

main_f = x
follow_up = x
while (follow_up < y):
   follow_up = follow_up + 1
   main_f = main_f + follow_up

return main_f

So basically I have a list of values of this function(main_f):

Initialisation : i = 0 , main_f = x

Iteration 1: i = 1 , main_f = 2x+1

Iteration 2: i = 2 , main_f = 3x+3

Iteration 3: i = 3 , main_f = 4x+6

Iteration 4: i = 4 , main_f = 5x+10

Iteration 5: i = 5 , main_f = 6x+15

And basically it goes on and on like this in a while (main_f < y) loop;

The loop invariant is certainly a sigma from i=x to y  with the "x" part:
(i+1)x but i can't find the formula that fits the integer part I got after the iterations.

Thanks in advance for your help

From your table, the following is apparent: at iteration $i$,
$$
\text{main_f} = (i+1)x + \binom{i+1}{2}.
$$
You should be able to prove this formula by induction.


Merging rectangles into rectilinear polygon Having a set of adjacent rectangles, what would be the algorithm that gets the rectilinear polygon wrapping around them?

Form a list of the $4n$ edges making up the $n$ rectangles.
Delete every edge that appears twice.

The edges that remain describe the outside of the polygon.  If you want to list these edges in clockwise or anticlockwise order, that's easy enough to do -- just pick an arbitrary starting vertex and find one of the two edges it is incident on, then find the other edge that the other vertex of that edge is incident on, repeating this until you hit the original vertex again.  If you encounter two edges in the same direction, you might want to turn them into a single, longer edge as you go.


Info about dataset from which a Huffman tree was generated I know that given the following huffman tree:

you can say that C occurs most in the dataset from which it was generated and D and B occur the least. Can you also say that the left most leaf on a level has a occurence that is greater than or equal to the rightmost?

My claim was not true. I've found counterexample on mathworld. If you look on the 4th level, you will see that 5th element is not in the correct position (if my statement were to be true).


What is the error-detection-probability of CRC I have a table which stores all serial numbers of devices in my system:

|------------------------|--------------------------|
|            #           |  Serial number (4 bytes) |
|------------------------|--------------------------|
|            1           |        0x????????        |
|------------------------|--------------------------|
|            2           |        0x????????        |
|------------------------|--------------------------|
|           ...          |            ...           |
|------------------------|--------------------------|
|           31           |        0x????????        |
|------------------------|--------------------------|

If I add a device to the system the position in the table is not predictable. If something in the system changes (e.g. add one or more devices, remove one or more devices, replace a device) I want to detect with a "high" propability that the system change. Therefor I want to use a CRC-32. In my system I have at least always 2 devices but max. 31 devcies. Meaning that the input of the CRC can vary between $2^{64}$ to $2^{992}$ different input streams.

As far as I understand:

The minimum input should be at least 32 bits
The most important is to use the right generator polynom. E.g.:

CRC-32
CRC-32-IEEE
CRC-32C

The selection of generator polynom depends on:

Input stream length
Error-detection-feasability
Collision probablility

Detection of a single bit error: All CRC's can do this
Detection of burst errors: All $n$-bit CRC's can detect burst errors up to $n$ consecutive bits. Also meaning appending new $n$-bit to the end of the input stream.

My concerns are the collision probability of the CRC32 is to high and due to that I don't detect a change in the configuration. Therefor I want to calcualte this probabilities and my questions are:

Is CRC the right method to use for my use case? If not what would be the best?
What is the "best" generator polynom for my use case?
How to cacluate the error-detection-feasability or collision probability if more then 32 consecutive bits change?
How to cacluate the error-detection-feasability or collision probability if $x$ not consecutive (different locations in the complete input stream) bits change?

There's nothing in your requirements that forces you to use a CRC32.  You could use any checksum.  If the collision probability for a CRC32seems too high, use a different checksum.

For instance, if you use SHA256, you will never have to worry about collisions -- for all engineering purposes, you can treat them as impossible (something that will never happen in your lifetime).  And then you won't need to worry about selecting generator polynomials or anything like that; someone else has done all that work for you.  You just use the standard SHA256 algorithm.

P.S. Using a basic checksum algorithm will require you to recompute the checksum on the entire table any time you insert or delete one row.  If that's too slow, there are a number of schemes to speed that up, such as a Merkle hash tree.


NL- definition and a problem The question is: What is the smallest complexity class in which the following problem is contained: Given a graph with $n$ nodes, Is there independent set of size of at least $n-10$?

I have a little difficulty to understand the meaning of being in ${\sf L}$ and examine problems in a correct way for deciding if they are in ${\sf NL}$ or ${\sf L}$

First I know that for being in ${\sf NL}$ I need to provide a verifier for a Turing machine which uses only $O(\log n)$ space on its working tape- So I wonder- I can give as a verifier this set of nodes to be independent set as requested, but how does the checking work? Can it go to all the lists of the pointers to the neighbors of each node , and for every node to check whether all the other nodes in the set given as independent set is not on that list- Is this considered of not using any space and I only need to count the nodes in the list that fulfill the requirement and therefore use only $O(\log n)$ space? Is this correct? Is there a way to prove that the problem is in ${\sf L}$?

Hint: How much space do you need to store a set of $10$ vertices? How much space does it take to go over all pairs of nodes in a graph?

Another hint: How much space does it take to implement the following algorithm? (I replaced 10 with 3 to make it easier to follow)

 int algorithm(int n, int G[n][n]) {
   int x, y, flag;
   int v1, v2, v3;

   for (v1 = 0; v1 < n; v1++)
     for (v2 = 0; v2 < n; v2++)
       for (v3 = 0; v3 < n; v3++) {
         flag = 0;
         for (x = 0; x < n; x++)
           for (y = 0; y < n; y++)
             if ((x != v1) && (x != v2) && (x != v3) &&
                 (y != v1) && (y != v2) && (y != v3))
               flag |= G[x][y];
         if (flag == 0)
           return 1;
       }
   return 0;
 }


Independent Set Problem Variant, Induction So the question gives us some mysterious algorithm, that given a graph G and an integer k, it outputs true/false to whether there is an independent set of size k in G.

So we have to design an algorithm that can call this mysterious algorithm within a polynomial number of times, to return an independent set of size k from G if it exists, or outputs impossible. The hint is induction.

I'm having trouble figuring an algorithm to solve this. I know however, that the proof for this algorithm involves removing or adding a vertex in the inductive step.

Hint:  Suppose you have a graph $G = (V,E)$ which is yes, and then there is a vertex $v \in V$ such that $G - v$ (the graph where you have removed $v$ from the graph) is no.  What can you say about $v$ and $G$?

Let us take an example, namely the following graph:

$G= (\{a,b,c,d\}, E=\{ab, bc, cd, ad, ac\})$

a —— d
| \  |
|  \ |
b —— c

and with $k=2$.  This is currently a yes instance.

First we ask:  If we delete $a$ from $G$, will the resulting instance still be a yes instance?

     d
     |
     |
b —— c

The answer is yes, this graph is still a yes instance.

Then we delete $b$ and ask the same question:

     d
     |
     |
     c

The answer is now no, this instance is no longer a yes instance.  Hence we cannot delete $b$.  Instead we try to delete $c$:

     d

b

The answer is still yes, and $|V(G')| = k$, so we conclude that $\{b, d\}$ is an independent set in $G$ of size $k$.


Finding weakest precondition I have the following program

x := y + 1;
if (y > 0) then
x := x + y
else x := y + 100;
x := x + y;

I want to compute the weakest precondition for getting {x = y} by executing this program.

The solution of this problem is the following

{(y > 0 & y + 1 + y = 0) | (y = -100)} = {( y > 0 & y = -0.5 | y = -100} = {false | y = -100}
x := y + 1;
{(y > 0 & x + y = 0) | (y =< 0 & y=-100)} = {(y > 0 & x + y = 0) | (y = -100)}
if (y > 0) then
{x + y = 0}
x := x + y
{x=0}
{y + 200 = 0} = {y = -100}
else x := y + 100;
{x=0}
{x+y = y} = {x=0}
x := x + y;
{x=y}

Can anyone explain this solution with a breakdown for each line?

Weakest precondition (WPC) can be computed with a procedure that takes your program, as well as the given postcondition (in this case, x=y), as inputs, and applies certain rules on how the precondition is computed for each part of the program (e.g. how to compute WPC for an if statement), until it reaches the point of computing the precondition for the whole program. Now, since the program you've given is a sequence of statements, this procedure will compute WPC for each of these statements and effectively start with computing WPC for the last statement and "propagate" WPC back to the first statement in the sequence.

In order to understand computation of WPC, it's good to be aware of some relevant notions like the semantics of the programming language your program is given in, i.e. what each statement means, (for your example the semantics is quite straitghforward), the way the WPC is computed according to rules that depend on the given part of the program and its semantics, and then specific rules on how WPC is computed for the given language. (Some links to useful materials are given at the end.)

Specifically for your program, which we will label for more convenient notation of P[x..y], which designates the program part consisting of lines from x to y

1. x := y + 1;
2. if (y > 0) then
3. x := x + y
4. else x := y + 100;
5. x := x + y;

the procedure for computing WPC would be given as

wpc(P, x==y) === wpc(P[1..5], x==y) === wpc(P[1], wpc(P[2..5], x==y))

where we use === for equivalence on the top-level (not be confused with assignments = and equality == in the language), and in turn

wpc(P[2..5], x==y) === wpc(P[2..4], wpc(P[5], x==y))

as P[2..4] represents the if statement. Now,

wpc(P[5], x==y) === wpc(x := x + y, x==y) === x + y == y === x = 0

given the rule for handling assignments, wp(x:=E,R) = R[x ← E],
which says that, intuitively, in order for some condition to hold after the assignment of x is executed, same condition should hold before that assignment, where instead of x we have the right-hand side of the assignment, since that will exactly be the value of x after assignment is done.

The next step is computing wpc(P[2..4], wpc(P[5], x==y)), i.e. wpc(P[2..4], x=0), since based on the WPC computation we discussed above, wpc(P[5], x==y) === x==0.

Now, there is again one statement (the if-condition) and one postcondition. (Note that you've written this postcondition two times, once for each branch of the if statement).  Without going into all the details, the WPC computation would follow the rule for conditionals, i.e. wp( E  S_1  S_2 ,R) = (E ∧ wp(S_1,R)) ∨ (¬E ∧ wp(S_2,R)), which guarantees the postcondition is satisfied if either branch is taken, thus the WPC becomes a logical OR between WPCs for each branch computed separately, i.e.

wpc(P[2..4], x==0) === (y > 0) & wpc(x := x + y, x==0) | !(y>0) & wpc(x := y + 100, x==0)

which is the same as the condition you wrote

(y > 0 & x + y = 0) | (y =< 0 & y=-100) === (y > 0 & x + y = 0) | (y = -100)

where WPCs for both branches are computed similarly as given before, as both of them represent assignments.

There are many good resources that cover program semantics and generation of verification conditions (including the computation of weakest precondition): some of them are mentioned on Wikipedia, while some courses like the "Program Analysis" course provide good views on the material and might represent a good step to start.


When would best first search be worse than breadth first search? I am studying best first search as it compares to BFS (breadth-first search) and DFS (depth-first search), but I don't know when BFS is better than best-first search. So, my question is

  When would best-first search be worse than breadth-first search?

This question is one of the back exercises in Artificial Intelligence by Rich & Knight, and it asks for an answer in terms of time & space complexity and allows you to define any heuristic function.

Best first search is different from BFS and DFS by that that it uses problem specific information to chose which node of the search tree to expand next. Best first search is informed search and DFS and BFS are uninformed searches.

In order to use informed search algorithm you need to represent the knowledge of the problem as heuristic function.

Best first search is sometimes another name for Greedy Best First Search, but it may also mean class of search algorithms, that chose to expand the most promising node based on an evaluation function(not necessary the same as the heuristics) such as Greedy Best First Search, A* and others.

If you meant Greedy Best First Search:

it is complete (finds a solution in finite graphs) like BFS
it is not optimal(to find the least cost solution) as DFS, but BFS is optimal when the cost of each arc is the same
in the worst case its time and space complexity is O($b^n$), where b is the branching factor and n is the maximal depth. For BFS time and space complexity is O($b^m$), where m is the depth of the shallowest goal.
Greedy best-first search is in most cases better than BFS- it depends on the heuristic function and the structure of the problem. If the heuristic function is not good enough it can mislead the algorithm to expand nodes that look promising, but are far from the goal. Here is one simple example

Let all arcs have the same cost, S - start node, G - goal node and h-heuristic function

Here Greedy best-first search will expand : S,B,C,D,G

And BFS will only expand : S,A,B,G


A specific version of a job scheduling problem I'm looking for a solutions or book references to a given variation of a job scheduling problem:

Given $n$ machines (let's denote it by $m_1, m_2, \ldots, m_n$) and $r$ tasks ($t_1, t_2, \ldots, t_r$). Each task $t$ can be described as a tuple $\left( (a_1, b_1), (a_2, b_2), \ldots, (a_k, b_k) \right)$, where $a_i$ is a number of some machine and $b_i$ is a required time to complete task $t$ on machine $a_i$. To complete the task, you need to start it on the first machine in the sequence ($a_1$) for a given amount of time ($b_1$), then start it on the second ($a_2$) and so on, until you finish your job on all of the given machines. It could be possible that number of machines in job description is smaller than $n$.

We will assume that tasks are atomic and one machine can do only one task in the same time, so it's possible that some task need to wait for a moment when a given machine is free.
Finally, we want to find the ordering of tasks to given machines to minimize the total time of all tasks.

This scheduling problem is called non-preemptive job shop scheduling.  The classic reference is

  Edward G Coffman, Jr, and Peter J Denning: Operating Systems Theory, Prentice-Hall, 1973.

Job-shop scheduling is discussed in Section 3.7 and 3.8 (although they mainly focus on a restricted version of the problem called the flow shop problem where the $a_i$ are in the same order for every task.)

It is called job shop scheduling because most of the early work on it was done by industrial engineers who were trying to optimize work schedules for machines in a factory, rather than computers.


Strassen Algorithm for Unusal Matrices The Strassen algorithm is developed for multiplying the matrices faster. It enables us to reduce O(n^3) time complexity to O(n^2.81).

However, this algorithm is applied for the matrices which are square and the dimension of the matrices must be a power of 2.

Assume that the matrices are called A and B.

Problem 1: A = 3x3 B = 3x3

Problem 2: A = 2x3 B = 3x1

How can we apply Strassen algorithm to multiplication of these matrices ?
The only thing which comes to mind is enlarging the matrices to convert them into square non matrices by adding zeros, which is called padding operation. However, I am not sure whether this method is proper or not.

Is there another method ?

Is my notion correct ?

Almost the same as Yuval's answer, except...

If I gave you two 1025 x 1025 matrices, you wouldn't extend them to 2048 x 2048. You'd extend them to 1026 x 1026, and use one layer of Strassen's algorithm with 513 x 513 matrices - if you decided that this is faster than direct calculation of a 1025 x 1025 product. One recursion level lower, you'd decide whether your seven 513 x 513 products are faster to calculate directly or as a 514 x 514 product using one layer of Strassen's algorithm and so on.

I very much doubt that Strassen's algorithm will be an improvement for 65 x 65 products. There are fewer floating-point operations, but probably a lot more overhead.

For non-square matrices: If you want to multiply a (100x100) by a (1000x100) matrix, that can be done trivially by calculating ten (100x100) x (100x100) products. Filling up to 1000x1000 would be madness.


Difference between encoding and modulation in transmission What is the difference between encoding and modulation?

I have seen these terms used sometimes inter-changeably and sometimes differently (the ratio is 50:50).

Can somebody clearly explain this with some non-technical and technical examples both? I have searched this a lot on net and in the end I end up scratching my head.

Modulation: Way to send signals (information) from one place to another. exanmple: you have a carrier wave like a sine wave and your Information signal 10101010 or any analog signal you want to transmit. You simply just change the properties of carrier wave with respect to your signal. Like: AM, FM, ASK, PSK, QAM

Encoding: Somthing else than modulation. It is representation of data. Example: 5Volts could be 1 or 0 according to logic (examples are Unipolar encoding, Bipolar Encoding).


Fast computation of k-fibonacci numbers Let's define the sequence of $k$-Fibonacci numbers as
$$ F_i = 2^i, ~~ 0 \leq i \leq k-1 $$
$$ F_i = F_{i-1} + \dots + F_{i-k}, ~~ i \geq k $$

I have a problem which requires to compute $n$-th $k$-Fibonacci number modulo $10^9 + 7$ efficiently. $n$ can be as large as $10^6$, $k$ can have any value between $1$ and $n$, time limit is $1$ second.

When $k$ is small enough i can use matrix-power approach for computing $n$-th members of linear recurrent sequences. This requires $O(k^3 \log(n)$ operations which is not feasible when $k > 250$ since takes more than one second.

When $k$ is large but $n$ is small i can compute this exactly by definition with $O(nk)$ operations. This approach is also not feasible when $k,n \approx 10^5$ or larger.

So how can i compute them faster? I neither derived nor found on the web any useful formulas which allow to represent this recurrence with smaller depth. Thus i believe that it's more an algorithmic than combinatorial question.

It's trivial to do in O (n), using the obvious formula $F_{i+1} = 2F_i - F_{i-k}$. Just write down the definition of $F_{i+1}$ and note that it is mostly (but not quite) the same as the definition of $F_i$.


What is the complexity of sum of Logarithm of an arithmetic series this is the arithmetic series:

$a/b,2a/b,3a/b,...,ba/b$

The new series:

$log(a/b),log(2a/b),log(3a/b),...,log(ba/b)$

I want the complexity of sum of the latter.

p.s: sorry about formatting.

edit 1: I realized that I need to provide more info:

$a,b \in \mathbb{N} $

$a>b$

a and b are not constants.
and the answer is something similar to :
$O(b*log(a))$

$f(a,b)=\sum_{k=1}^b \log(k*\frac{a}{b})=\log\prod_{k=1}^b \left(k*\frac{a}{b}\right)=\log \frac{b!*a^b}{b^b}=\log(b!)+b\log\frac{a}{b}=b\log a +[\log(b!)-b\log(b)]$

by Stirling's formula, $\log(b!)=b\log b -b +\mathcal{O}(\log{b})$

Therefore $f(a,b)=b\log a +o(b\log a)$ so $f(a,b)\sim b\log a$

NB: all asymptotics ($\sim$, $\mathcal{O}$ and $o$) are taken as $a,b\to\infty$ with $a<b$)

For a more precise evaluation than just an equivalent, replace Stirling's approximation (https://en.wikipedia.org/wiki/Stirling%27s_approximation) with Stirling's bounds (same wikipedia article).


Unique representation of 5-number sets with values 1-13 From a simulation I get 5 numbers 1-13. The nature of the simulation is that I do not get the numbers ordered. The value/rank of the the tuple is not order dependent 5 5 5 2 2 = 2 5 2 5 5.   Values can repeat but they can repeat at most 4 times (it is a deck of cards).  As it turn out there are 6175 combinations.  Calculate the value of the tuple is expensive but it is pretty cheap to just generate the tuples in value order - save that and do a dictionary lookup. Without sorting the numbers what is the smallest number to uniquely represent the 5 number combination and how to generate that number?

Right now I just raise 5 to the 0-12 power and add the 5 as a proof of concept and it works.  But that is fairly expensive and uses 32 bits.  I want to get the bits and compute down.  How might I do that?

Yes I have had few questions on this subject but I promise to make this my last.

In a related question got an answer for 5 numbers 1-52 in 27 bits using some magic numbers and XOR.  I cannot figure out how to create those magic numbers for 1-13.

Here is a solution with 20 bits. Consider the following array:

0x000f2616, 0x000dbcce, 0x000533cf, 0x0007d943, 0x000a180c,
0x000f69f2, 0x0005e214, 0x0009da04, 0x000e101a, 0x000c495c,
0x0009cfaa, 0x000ff60d, 0x0000103d

Each of these numbers $x_1,\ldots,x_{13}$ is 20 bits long. Given a hand $a,b,c,d,e$, compute the 20 least significant bits of $x_a+x_b+x_c+x_d+x_e$. You can easily check that this results in a value that identifies a hand uniquely.

I found these values by randomly generating arrays until one of them worked, so it's possible that a better construction exists (such as one using codes over $\mathbb{F}_5$).

Here is another solution, which results in keys in the range [0,441100]. Let $p = 441101 \approx 2^{18.75}$, which is prime. The key corresponding to a hand $a,b,c,d,e$ is $5^a+5^b+5^c+5^d+5^e \bmod{p}$. This is the minimal prime that works. I calculated it by factoring all differences of $5^a+5^b+5^c+5^d+5^e$ for all pairs of hands.

You can also implement this using the array

1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 188721, 61403, 307015, 211772

Add the corresponding numbers, and (optionally) reduce modulo 441101.


How to do asynchronous programming with only global variables? If a programming language only supports global variables, is it still possible to use asynchronicity, like callbacks, event-driven programming, other kinds of parallelisation?
How can it be done?

Every program that uses local variables can be converted to one that uses only global variables.  So, the answer is trivially yes.  However, it might not be pleasant for the software developer.


How can a TM M' have a property P if it only accepts a single string x from language of P? Here is the document: More Undecidable Problems

For a given property $P$ of languages, define $L_P$ as the set of all Turing machines (resp. their encodings) that accept languages with $P$, that is

$\qquad \displaystyle L_{p} = \{ ⟨M⟩ \mid \mathcal{L}(M) \text{ has property } P \}$

If $P$ is a trivial property, that is if $P$ holds for all or no language, $L_P$ is decidable, too (as $L_P=\emptyset$ or $L_P = \{\langle M\rangle \mid M \text{ Turing machine }\}$. If $P$ is not trivial, $L_p$ is undecidable (by Rice's theorem), which means the strings in this language (or with such property) cannot be determined if it can be halt.

We determine a language $M$ has property $P$ by reduce $M$ to another $M'$, and check that if $M'$ accepts the reduced string $x$ from the initial string $w$, we can conclude that $L(M)$ and $L(M')$ have property $P$.

However, as the title suggests, we only reduce a single string $w$ to $x$ and if $x$ is accepted, but we conclude the whole $L(M')$ has property $P$. Thus, $M'$ is obviously part of $L_p$. What if some random strings in $L(M')$ do not have property $P$?

What if M accepts some string, but the reduction of those strings are not accepted by M'?

A reduction from language $L$ to language $L’$ is an algorithm (TM that always halts) that takes a string $w$ and converts it to a string $x$, with the property that: $x$ is in $L’$ if and only if $w$ is in $L$.

Does this imply the reduced language $L'$ will contain every property $P$ from $L$? Since we can conclude that if $L'$ is decidable, then $L$ is decidable as well and vice verse. Can we conclude the same thing to property $P$?

I think I got it. Here is Rice's Theorem (Rice Theorem and Turing machine
b ehavior prop erties):

I looked it up here: Decidability for the definition of a problem in the context of Turing Machine (slides 9 and 11):

  Formally, a problem is a language.
  Each string encodes some instance.
  The string is in the language if and only if the answer to this instance of the problem is “yes.”

  A problem is decidable if there is an algorithm to answer it.

  Recall: An “algorithm,” formally, is a TM that halts on all inputs,    accepted or not.
  Put another way, “decidable problem” = “recursive    language.”

  Otherwise, the problem is undecidable

That answers why I only need one string w and reduced x from w to prove a language L with property P is undecidable.

According to Rice's Theorem, if language L with property P has Turing Machines that does not accept language of L, L is undecidable. Thus:

$$L_{p} = \{ L(M_{0}), L(M_{1}), L(M_{2}),..., L(M_{n})\}$$
$$L'_{NotInp} = \{ L(M_{0}), L(M_{1}), L(M_{2}),..., L(M_{n}) \}$$

$$M_{i}\mspace{8mu} \text{is}\mspace{8mu} \text{an}\mspace{8mu} i\text{th}\mspace{8mu} \text{Turing} \mspace{8mu} \text{machine},\mspace{8mu} i ≤ n. $$

If the language L' (which contains TMs not in P) is not an empty set, the above L sub P is undecidable. Recall that language with property P is decidable if and only if it is trivial, which means either it contains every RE languages or not at all. Since if a language L with property P is decidable, every Turing Machines accept every string in L, so we don't need to test the acceptance of input to a given TM.

Also, according to the definition of a problem in the context of Turing Machine, if we have the answer (an algorithm) to every instance of the language L sub P (obviously, since L sub P contains every TM), L sub P is decidable. Otherwise, it's not.

Let's be more concrete with an example from here: More Reduction Examples

Aside from the proof given on the page, let's look at it more intuitively. We may have Turing Machine M which accepts the three strings. Other than that, the input w can be anything which is not in M, but belong to other M'. Input w can be "Not UIUC", "Not Iowa", or "Not Michigan" or any other strings which do not belong to M. Since we do not have the answer to every instance of the problem with M (because if we do, M will accept every string since every string has property P. In this case, it's not). The language is not trivial, thus it is undecidable.

This is my reasoning. What do you think?


Local search (Hill Climbing) scope and definition I'm taking an artificial intelligence class and in one of the recent lectures the topic was local search algorithms, more specifically Hill Climbing. At one point the professor showed the classic 8-queens puzzle to illustrate the algorithm working, he stated that in it a queen can only move one row up or down, so for example in a column with the following configuration:

In the first iteration the queen can only move to either rows 4 or 6 (8 rows, 0-based index), then in the next iteration it would be stuck in a local maxima because neither row 3 nor 7 have values lower than 14, so the algorithm would then proceed to the next column or terminate. He argued that even tough a queen can legally move directly through all the rows of its column doing so would make the algorithm fall of the concept of "Local search", because a local search move is limited to only one of its closest neighboors per time/iteration.

I found this weird because it appears to me that such a limitation greatly reduces the usefulness of hill climbing (in the  8-queen problem it makes the success rate abysmal). So I would like to know what's the correct/formal definition of local search and hill climbing, should it always be constrained to the closest neighboor? what constitute a closest neighboor? I would especially appreciate some book references.

Local search and hill climbing assume that you have defined a notion of "neighbor" and have defined an objective function.  It's up to you to define those for your particular application.  As you have noticed, some choices of the "neighbor" relation might make local search more effective or less effective.

In the 8-queen problem, there are multiple ways you could define the notion of "neighbor".  One option is to treat two configurations as neighbors if you can get from one to the other by moving one queen one step; then the example in the question shows that local search with this notion of neighbor might get stuck.  That is a consequence of defining "neighbor" in a particular way as much as a consequence of using local search, and is not fundamental to the notion of local search.  Nothing prevents you from defining "neighbor" differently.  For instance, one alternative is that you could consider two configuration neighbors if you can get from one configuration to the other by moving one queen any number of steps in a single direction.  That might have different properties.

What is fundamental is that local search and hill climbing can risk getting stuck in a local minimum (where all neighbors are worse than your current location, but you're not in a global minimum).  The likelihood of this may depend on the particular problem you are working with, the specific notion of neighbor you choose, and which local search method you use.  Hill climbing is particularly susceptible to local minima; other methods are designed to try to reduce the risk of local minima.


Computational complexity based in the input size In an answer to a previous question Luke Mathieson wrote:

  A place where this might fall down is when you are working with numbers. As a number with magnitude $m$ can be encoded in $n=O(\log m)$ bits, if our running time were $O(m)$, this would be $O(2^n)$ - exponential in the actual input size - which would make the magnitude $m$ a bad choice for a proxy for the input size if we wanted to talk about membership in $\mathcal{P}$ for example (when you come to Strongly-$\mathcal{NP}$-complete and Weakly-$\mathcal{NP}$-complete, remember this). On the other hand, if all we were interested in was decidability, then it would be a good enough proxy measure.

Can you explain to me how if the running time is $O(m)$ goes to $O(2^n)$?

Let the length of the input (in bits) be $n$ and let the number represented be $m$.  We have $n \approx \log_2 m$ (that's how many bits it takes to write down the number $m$) so $m\approx 2^n$.


Non linear neural networks? The activation of a perceptron style neuron is:

$DotProduct(Inputs, Weights)+Bias > 0$

That is essentially classifying what side of a (hyper)plane a point is on (positive or negative side), like the below:

$DotProduct(Point, Normal)+D > 0$

Looking at an N input, M layer perceptron network that has a single output can be seen as classifying a point as inside or outside some hyper shape.

But, it seems like all the tests are linear, and switching to sigmoid activation doesn't seem to add a whole lot of non linearity - like if you were visualizing this NN shape, even a sigmoid activated network would be mostly made up of planes, not curved surfaces.

On the other hand we have support vector machines as a machine learning tool, and using things like the "kernel trick" which can make a non linear classification of points for being inside or outside.

This makes me wonder, is there a version of neural networks that has more free form separation shape?

It seems like it would be possible to have a better performing neural network with fewer neurons and/or layers.

Sigmoid does add nonlinearity -- and the nonlinearity "builds" as you add more layers.  Neural networks can recognize arbitrary decision boundaries (given enough neurons and enough layers).

I think your visualization of what the sigmoid activation does is a bit off.  Take a look at http://playground.tensorflow.org/ and play with some of the tuning knobs to see the kinds of decision boundaries that can be achieved -- that site is a helpful way to get some intuition.

So, the answer to your question is: we don't need a separate version of neural networks.  Standard neural networks already can support arbitrary decision boundary shapes.

[ About the kernel trick: The kernel trick can be used here, but is possibly a bit more expensive than in the case of SVM's; for SVM's, there's a particular mathematical trick that avoids the need to generate all of the "extra features", but that trick is specific to SVM's.  You can still construct derived features and add them to the feature vector before applying a neural network, though, if you want -- nothing prevents you from doing it.  But the kernel trick isn't needed, because neural networks can learn non-linear functions.  In contrast, without the kernel trick, SVMs can only learn linear decision boundaries, so it's needed more there. ]


Minimizing DFA - Dead state elimination Following is a Question from a competitive exam, it is given that the solution is A but I don’t know why the dead state 4 is not eliminated.Dead states like 4 which has transitions only to itself, should be eliminated right?

UPDATE:
My solution to the question in the comment

The given dfa (d) will be formed.
As far as your question about removal of state r: it can't be removed because state q is having transition to state r on input b. This is necessary because a dfa cannot leave any input transition, that is, it must define all the transitions for each and every state and for each and every input given to those states.


Do white box methods for feature extraction exist for facial recognition? Part of something I'm working on (or rather begin working on) involves white box approaches to facial recognition. I previously worked on something for character recognition using scene segmentation and neural networks but for faces I'm trying to challenge myself by not using neural networks or other AI strategies.

Consider a potential algorithm that takes a headshot photo as an input and the outputs are some metrics about said face. Like the eye color, skin color, hair color, philtrum width and height, distance between eyes, etc. What techniques exist that I should look into on how to implement this?

My concern is mostly with feature extraction from points of interest from a face. I think my difficulty is algorithmically describing the composition of a face to pull metrics.

For every feature $F$ you want to extract you need an algorithm extracts $F$.

the color histogram is good for color. For example if you need to extract eye color you need find eye in face (you can use open cv and see documentation) that is a 3 2D-matrixes for pixels(Red and Green and Blue filters) and if you find the histogram of these 3 matrixes you can use this histogram as eye color feature.

If you find face (with open cv) and extract the histogram, this feature isn't bad for skin color.

I think the heights and distances are not good features.

For finding face's shape HOG feature is good and also HOGColor


Is this reduction from 3D-MATCHING to PATH SELECTION invalid? I'm a bit confused about some proof that PATH-SELECTION-PROBLEM  is NP-complete (Problem 9, chapter 8 in "Algorithm Design" by Tardos and Kleinberg) that I found in some solution manual here:

https://github.com/weimin/CS-180/blob/master/Algorithm%20Design%20(Kleinberg%20Tardos%202005)%20-%20Solutions/Algorithm%20Design%20-%20Kleinberg%20%26%20Tardos%20-%20Solutions/chapter_08/problem%20(8).pdf.

The PATH-SELECTION PROBLEM is defined as follows: for a given directed graph and a set of paths we ask if it is possible to select at least $k$ paths so that no pair of paths share any node.

The solution uses polynomial reduction from 3D-MATCHING problem defined as: for distinct $n$-sets $X, Y, Z$ and a set of triples $T$ $\subset$$X \times Y \times Z$ we ask if there is an $n$-subset of $T$ that covers $X \cup Y \cup Z$.

For a given arbitrary instance of 3D-MATCHING, the proposed reduction constructs a directed graph $G=(V, E)$ such that $ V := X \cup Y \cup Z$ and for each triple $\langle x, y, z \rangle $ from $T$ it adds edges $\langle x, y \rangle, \langle y, z \rangle $ to $E$ which define set of paths $\mathcal{P}$. It then claims that there are $n$ legal paths in $G$ iff there exists $n$-subset of distinct triples from $T$ (which is equivalent to saying that it covers sum of $X, Y, Z$).

My confusion is that adding edges as above produces too much paths that yield a solution to PATH-SELECTION having no correspondence in 3D-MATCHING. Let's consider $n=2$, $T= \{ \langle x_{1}, y_{1}, z_{2},  \rangle, \langle x_{2}, y_{1}, z_{1},  \rangle, \langle x_{2}, y_{2}, z_{2},  \rangle \}$. There is no solution for 3D-MATCHING here but in reduction described above we have paths $\langle x_{1}, y_{1}, z_{1},\rangle $ and $\langle x_{2}, y_{2}, z_{2},\rangle $.

EDIT:
I think I missed one point: over all paths $\mathcal{P}$ the solution defines a subset $\mathcal{P'} \subset \mathcal{P}$ of the paths that strictly correspond to the triples and then we are only allowed to search for a solution in $\mathcal{P'}$. But this is still odd as it reformulates the PATH-PROBLEM adding up additional constraint ...

The "additional constraint" is part of the problem definition:

  for a given directed graph and a set of paths we ask if it is possible to select at least k paths so that no pair of paths share any node.

The key is "and a set of paths". The Path-Selection Problem has a set of paths from which you are allowed to chose as part of its input.

Note that the definition is kind of strange, since the fact that a graph is involved seems irrelevant (we could always take the graph to be a clique, which doesn't change the answer). However, if the graph has special structure, then the problem can become tractable (e.g., if the graph is a tree the problem is polynomially solvable).


Fast sampling from discrete space Assume we are given a set $X = \{x_1,...,x_n \}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=x_i) =p_i$.

More specifically, I assume $A$ can generate a uniformly distributed real number in the interval $[0,1]$ in a constant time, and try to characterize the distributions $P$ which can be sampled in $o(|X|)$ time.

For example, if $P$ is the uniform distribution, I can assign to each element of $X$ a string from $\{0,1\}^{\log(n)}$, then sample each bit uniformly (toss of a coin) and independently, which means I can sample in $O(\log(n))$ time. Are there distributions such that any algorithm requires $\Omega(|X|)$ time? Are there known results in this direction?

The Alias Method provides a means of sampling from a discrete distribution in $O(1)$ time, with $O(n)$ space and $O(n)$ pre-processing time.


What is the SetHorspool string searching algorithm and how is it implemented? What is the SetHorspool string searching algorithm with pseudo-code so it can be easily implemented in a language of choice?
This has been implemented in 2 libraries I have come across:

https://app-db.com/seqan/1.3/SPEC_Set_Horspool.html,
http://stringsearchalgorithms.amygdalum.net/.

But there seem to be very little details of the algorithm available online to understand its working.

Reading the source code we can see that it is an extension of Horspool to find a match from a set of needle strings $S$, rather than matching a single needle string.
How it works is by representing the set $S$ as a trie. This allows you to efficiently check character by character whether starting at position $i$ any of the strings on the trie can be found in the haystack. And like in Boyer–Moore–Horspool, if a position $i$ of the haystack fails to match any of the strings in $S$, instead of simply trying $i' = i+1$, a smarter skip lookup table is used: $i' = i + T[\text{haystack}[i + |\text{needle}| - 1]]$.
The second difference is how $T$ is computed. Normally the pseudocode is as follows (from the Wikipedia article):
function preprocess(pattern)
    T ← new table of |Σ| integers
    for i from 0 to |Σ| exclusive
        T[i] ← length(pattern)
    for i from 0 to length(pattern) - 1 exclusive
        T[pattern[i]] ← length(pattern) - 1 - i
    return T

But in SetHorspool, the minimum safe skip considering all patterns is computed instead:
function preprocess(S)
    T ← new table of |Σ| integers
    for i from 0 to |Σ| exclusive
        T[i] ← min(length(pattern) : pattern ∈ S)
    for pattern in S
        for i from 0 to length(pattern) - 1 exclusive
            T[pattern[i]] ← min(T[pattern[i]], length(pattern) - 1 - i)
    return T


What is the deterministic finitite automaton (DFA) for the regex ".*b." I'm looking for a finite state machine that can match inputs to the regular expression .*b. deterministically (i.e. it cannot change state w/o being fed input and the transition to a new state is solely determined by the current state and the input word).

Consider the following examples that should be matched by the automaton: abc, abbc, abcbc, abcabc. The first one reflects a "happy path" while the remaining all require some level of backtracking, because the automaton will incorrectly match the first b it finds in the input with the b in the pattern.

My nondeterministic attempt looks like this:

You can see from the conditions on the edges that the transition to a new state not only depends on the current state and the input word, but also on the previous input word.

Can this converted to a DFA? Is there even a DFA for this regular expression?

This site claims yes, but in my opinion the DFA it produces for the regex cannot match all the examples w/o doing some magic behind the curtains:

Consider the transition steps for the example abbc:

word a: 0-.->1
word b: 1-b->2
word b: 2-.->3
word c: fail because there is no matching edge from state 3

Or am I missing something?

Based on David Richerby's answer I drew this DFA:

Every language described by a regular expression has a DFA – this is Kleene's theorem (not to be confused with Kleene's recursion theorems, which are something completely different).  Standard algorithms to translate from regular expressions to automata give nondeterministic automata (NFAs), such as the one you found on the web.  There are standard algorithms to determinize NFAs but they make the state space exponentially larger.

In this case, though, it's straightforward to produce a DFA by thinking about the language you're interested in. The language is all strings whose second-to-last character is $b$. So your automaton needs to accept if it gets to the end of the string and the previous character it saw was a $b$.  I don't have any drawing software to hand but the following textual description is, I think, more useful.  You need four states, corresponding to the combinations of "the character I just read was/was not $b$" and "the character before that was/was not $b$". You start in (not $b$, not $b$), since you haven't read any $b$s before you've read any characters.  The transition function and so on should be pretty obvious.


$\mathsf{co\text{-}NP}$ and Cook reductions Can someone help me understand the steps in this argument? There is a decision problem that is in $\mathsf{co\text{-}NP}$ (under standard Karp reductions) and is $\mathsf{NP}$-hard with respect to Cook reductions. Does this imply that if it is in $\mathsf{NP}$ then $\mathsf{NP} = \mathsf{co\text{-}NP}$ and if so, why?

Every NP-complete program $A$ is co-NP hard under Cook reductions: given a problem $B$ in co-NP, its complement $\overline{B}$ is in NP, so there is a polytime function $f$ such that $f(x) \in A$ iff $x \in \overline{B}$. Therefore the following is a Cook reduction from $B$ to $A$: given $x$, ask whether $f(x) \in A$, and return the opposite.

This shows that Cook reductions are not sensitive to the difference between NP and co-NP. Karp reductions are, and that's why we use them in the usual definition of NP-complete. (If we were only interested in P vs. NP, Cook reductions would be fine.)


Height of AVL after entries Problem: Suppose $V$ is an AVL tree (a self-balancing binary search tree) of $n$
  elements. After the insertion of $n^2$ elements, what would be its
  height?

My idea: the height of an AVL tree is originally $O(\log(n))$ where $n$ is the number of elements. After insertion of $n^2$ elements, its height will be:$$O(\log(n+n^2))=O(\log(n^2))=O(2\log(n))=O(\log(n))$$

My answer would be $O(\log(n))$ but I'm having doubts.

Why is the asymptotic complexity of the result the same despite the fact that there are more elements?

To show that this isn't always the case, imagine you added $e^n$ elements, then it would take

$$O(\log(n+e^n))=O(\log(e^n))=O(n)$$

But what does that really mean? It's not that your binary tree takes $O(n)$ time on $n$ elements to find something. Rather, it takes $O(\log(m))$ time for $m=n+e^n$ elements.

I can understand why you would be confused; if you had to search linearly through a list, and then you added $n^2$ elements, it would take $O(n^2$) time in terms of the original input, but not the new input, for which it would take $O(m)$ time on $m=n+n^2$ elements.

Chances are you didn't want to solve for the asymptotic solution; it generally doesn't make sense to. What you probably want is the approximation $\log(n+n^2)\approx\log(n^2)=2\log(n)$; that is,

  For a self-balancing tree, squaring the input size doubles the search time.


Formal definition of hash function I was reading through the classic CLRS with the intention of reviewing the hash tables theory, more specifically the hash function definition I just wanted a reference to quote.

I cannot find a formal definition given but I think it's fair to say a hash function (not univerisal) $h$ is a surjective map from a set of keys $K$ to a subset of integers $U$, for each $k \in K$ we define $h(k)$ to be the hash value of $k$. From the explanation given in CLRS it seems though this restriction on $U$ (be integers) might be too restrictive, however since I think the definition has to show some practical aspects I think this might be correct.

Can you either give me:
1. A paper/book with a formal definition
2. Confirm if my definition is correct?

Thank you

A hash function is used to map a set of keys to a subrange of the integers (it is used as an index into an array, in the end). So it must be (assuming zero based arrays, as in  C), $h \colon \mathcal{U} \to [0, m - 1]$ if $\mathcal{U}$ is the universe of keys.


What kind of math problems can be solved by automated theorem provers? Can I prove following statements with using available automated theorem provers?

$(a+b)^2=a^2+b^2+2ab$.
If $ 11 \mid 2a-3b$, then $ 11 \mid 7a-5b   $.
If $ ax^2+bx+c=0$, then $x=\frac{-b\pm\sqrt{b^2-4ac}
}{2a}$.
If $a$ is even then $4a$ is even.

and so on!

I am asking this question because I just found the application of Automated theorem provers in proving theorems in logic.

Most of your statements are elementary algebra, so these can be proved automatically by a computer algebra system (CAS), such as Maple or Mathematica.

(In case you're interested in the mathematics behind CAS, I can recommend the book Modern Computer Algebra by Joachim von zur Gathen and Jürgen Gerhard,  a beautiful book, considered the 'bible' of the field)

Automated theorem proving tends to be mostly a case of doing heuristic search on a structure that represents proofs, if the proof is not one of the few cases for which there is an algorithm that can conclusively solve it. Given that this statements aren't very complicated, it is likely that an automated prover is able to 'find' a proof.

However, I think it is interesting to say a bit more about the statements for which there are nice algorithms:

Statement 3 is (a very simple case of) about roots of a (system of) polynomial equations and can be solved by finding a Gröbner basis with Buchberger's algorithm. The Gröbner basis and Buchberger's algorithm to find one are very nice tools for automated theorem proving. For example, we can even automatically prove elementary theorems in geometry by automatically transforming the problem to finding a root of a polynomial equation in a clever way!

Another interesting class of theorems are statements expressible in quantifier-free Presburger arithmetic (in particular, this arithmetic is without multiplication, so this doesn't apply to your statements), as there is an algorithm to solve all such statements, even though the algorithm is a bit slow.


how to prove that a language is regular? I know that this language is not regular L = {w | na(w) = nb(w)} where na(w) is the number of a's in w. But what if now the language changes to that the number of a's has to be greater than b's? I think not, because we do not have finite number of prefix equivalence class. And in that case, how can I prove it? Or if it was regular, how would it be?

Both mentioned languages are irregular
This can be easily shown for both languages using the pumping lemma
First consider L = {w | w has more as than bs}
Let p be the pumping length then clearly  b^p a^(p+1) is in L and it cannot be pumped
We know that |xy| ≤ p ,and thus x and y will have only bs , then pumping the string for i > 1 , xy^i z will give you a string with bs equal to (for i=2) or more than ( for i >2)  as, since this string cannot be pumped L is irregular
In a similar manner the language with the number of as equal to bs can be shown to be non-regular , consider a^p b^p clearly it has equal number of as and bs , using the same argument as above x and y will have only as and thus pumping the string gives more as than bs and thus this language is also non-regular
Intuitively we know both are irregular since we need to keep count of the number of as and bs to compare them something , and the number of as and bs is not a finite specified number .


Ask about a non-RE language I have a question about undecidability. And I hope you could point out where I am wrong.

The question is: to decide the following question as (A) recursive, (B) RE but not recursive, (C) not RE.

$L = \{\langle M\rangle|M \text{ is a TM and } |L(M)| \geq 3\}$

If we use $HP$ as halting problem and $\overline{HP}$ as the complement of halting problem. Then the solution could be (B) RE but not recursive (Taken from the Internet):

I understand this proof. But I have another proof as follows, and I can't figure it out why it is wrong.

We prove this by a reduction from $\overline{HP}$. Simulate $M'$ on input $w$ works as follows: it runs $M$ on $x$ and rejects if $M$ halts on $x$.

(1) $\langle M, x\rangle \in \overline{HP}$ $\rightarrow$ $M$ doesn't halt on $x$ $\rightarrow$ $M'$ accepts all inputs $\rightarrow$ $|L(M')| \geq 3 $ $\rightarrow$ $M' \in L$

(2) $\langle M, x\rangle \notin \overline{HP}$ $\rightarrow$ $M$ halts on $x$ $\rightarrow$ $M'$ doesn't accept any input $\rightarrow$ $|L(M')| < 3$$\rightarrow$ $M' \notin L$

Thus $\overline{HP} \leq_m L$. As $\overline{HP}$ is not RE, $L$ is not RE, which is wrong.

So where is wrong?

Thanks!

Recall that if a TM $M$ doesn't halt on input $x$, then $x \notin L(M)$

Your mistake is in (1), if $M$ doesn't halt on $x$, then $M'$ doesn't halt too (since the simulation of $M$ on $x$ doesn't halt). so  $M'$ doesn't accept any input, that is $L(M')=\phi$.


Finding recurrence relations for dynamic programming algorithms Consider a function $f(n)$ whose definition requires one to compute $f(1),f(2),..f(n-1)$ in order to evaluate $f(n)$. Suppose that some algorithm to compute $f(n)$ has time complexity that is given by the recurrence: $T(n) = n  + T(1) + T(2) +...+ T(n-1)$. This is $O(2^{n})$.

One can use dynamic programming to store the values of $f(1),f(2),..,f(n-1)$  in an array so that computation of $f(n)$ only requires $O(n)$ time as long as the values of $f(1),f(2)...,f(n-1)$ are already stored in an array. The total time complexity of such a dynamic programming algorithm would be $O(n^{2})$ which makes sense if you consider the actual psuedocode of such an algorithm. But what would be the recurrence? Would it be $T(n) = n + \max(T(1),...,T(n-1))$ ?

If all of your values start out unstored, then $T(n) = n + T(1) + T(2) + \cdots + T(n - 1)$ still, however, when computing $T(n - 1)$, $T(1)$ through $T(n - 2)$ have already been found, so $T(n - 1) = n - 1 + O(1)$. Same for $T(1)$ through $T(n - 2)$ ($T(1)$ is just $O(1)$). This gives an overall runtime of
$$T(n) = n + O(1) + (1 + O(1)) + \cdots + (n - 1 + O(1)) = \frac{n(n-1)}{2}+n(1+O(1))=O(n^2)$$


How to solve a knapsack problem with increased weight limit? Let us consider the knapsack problem. Given a set $P$ of $n$ items where each item has weight $w_i$ and value $v_i$ for all $i=1,2,\ldots,n$. We have two bins, one has a weight limit of $W$ and the other has a weight limit of $W'=2W$. Assume that we have an optimal algorithm $\texttt{OPT}$ that solves the knapsack problem.

Let $O$ denotes the value of an optimal solution when we apply $\texttt{OPT}$ to the first bin (that has a weight limit of $W$) and to the set of items $P$. Also, let $O'$ denotes the value of an optimal solution when we apply $\texttt{OPT}$ to the second bin (that has a weight limit of $W'=2W$) and to the same set of items $P$.

Can we compare $O$ and $O'$?

I guessed that $$O'\leq 2O.$$

That guess is obviously wrong. If all items have weight 666 and value 1, then you can fit 3 items into a bin of size 2000, and only one into a bin of size 1000.

If all weights are W < $w_i$ ≤ 2W, then O = 0 and O' = highest value of a single item.

There is very little that you can say except the obvious O ≤ O'. You might have "valuable" items with a total weight ≤ W, and all other items are worthless. Then O' is not or only very little greater than O. Or all items with weight ≤ W might be worthless with some items with weight W < $w_i$ ≤ 2W very valuable, then the ratio O' / O can be arbitrarily large.


Cut costly functions in inter-procedural abstract interpretation I am performing some inter-procedural abstract interpretation to capture certain program properties. Following the standard way, what I am doing is to maintain a work list of to-be-analyzed functions, and pick one from the work list to perform intra-procedural analysis until the work list is empty.

Currently, I observed that the intra-procedural analysis of certain functions would not terminate. Basically, it is just taking too much memory and become too slow to reason for even one more statement.

Of course, I can optimize my code base and improve the memory efficiency, but fundamentally that shouldn't help too much.

Now I am seeking for some strategies to bypass such obstacle. Intuitively, what I can do is to cut a intra-procedural analysis off whenever the memory usage grows too high, return a Top as the return value, and switch to the next function in my work list for analysis.

This seems very naturally, and should be sound as well! However, after some quick review of some abstract interpretation work, I don't see any related work performing such cut off.

So here is my question:

What is the standard approach in abstract interpretation if a intra-procedural analysis becomes too costly to finish?
I assume the cut off and return Top approach is sound. Then why shouldn't I find any related literature employing such approach? Is it too ad-hoc and naive?

Sure.  "Cut off and return Top" is sound.  It's valid.  It seems like a reasonable thing to do.

I don't know if it has been studied or used before in the literature.  I wouldn't be surprised if it has.  It feels to me like a variant on widening, even though it's not identical to the usual widening operator.   I've seen similar methods applied before (if you get stuck, give up and return Top) in other situations.

I don't think there's a single standard approach to this problem.  My impression is that there are multiple techniques. You can memoize analysis of a function (so you lazily generate a transfer function that summarizes the effect of the function, in terms of its arguments, and then reuse that information when you need it again in the future).  You can use widening operators.  You can use counter-example guided refinement to start with a coarse abstraction (which is efficient for static analysis), and then make the abstraction more precise as needed.  I imagine you could also do the converse: start with a fine-grained abstraction, and if it is taking too long, switch to a more coarse abstraction and restart the analysis with that coarser abstraction.  There are probably many other possible techniques, and the best one might depend on the specifics of your particular analysis.


Is smn theorem the same concept as currying? I am studying the s-m-n theorem and the concept reminded me of currying.

From wikipedia article about s-m-n theorem:

  the theorem says that for a given programming language and positive integers m and n, there exists a particular algorithm that accepts as input the source code of a program with m + n free variables, together with m values. This algorithm generates source code that effectively substitutes the values for the first m free variables, leaving the rest of the variables free.

From an article about currying:

  Intuitively, currying says "if you fix some arguments, you get a function of the remaining arguments"

Seems like the same idea to me. The only reason why I am unsure is that the materials I came across on s-m-n don't mention currying (and vice versa), so I wanted to consult it to make sure I actually get it.

Yes, it is the same thing.

Currying is a concept from $\lambda$-calculus. It is a transformation between $A \times B \to C$ and $A \to (B \to C)$. Think of this as "if we have a function of two arguments of types $A$ and $B$, then we may fix the first argument (of type $A$), and we will get a function of the remaining argument (of type $B$)". In fact, this transformation is an isomorphism. This is made mathematically precise by mathematical models of (typed) $\lambda$-calculus, which are cartesian closed categories.

There is a category of numbered sets. A numbered set is a pair $(A, \nu_A)$ where $A$ is a set and $\nu_A : \mathbb{N} \to A$ is a partial surjection, i.e., a map from numbers onto $A$, which may also be undefined. If $\nu_A(n) = x$ then we say that $n$ is a code of $x$. In computability theory there are many examples. Whenever we encode some information with a number we get a numbered set. For instance, there is a standard numbering $\varphi$ of partial computable functions, so that $\varphi_n(k)$ is the number computed by the partial computable function encoded by $n$ when applied to $k$. (The result may be undefined.)

A morphism of numbered sets is a realized map $f : (A, \nu_A) \to (B, \nu_B)$, which means that there exists $n \in \mathbb{N}$ such that $f(\nu_A(k)) = \nu_B(\varphi_n(k))$ for all $k$ in the domain of $\nu_A$. This looks complicated, but all it says is that $\varphi_n$ does to codes what $f$ does to elements. It is the mathematical way of saying that "program $\phi_n$ implements function $f$".

Here is the punchline: the category of numbered sets is cartesian closed. We may therefore interpret the typed $\lambda$-calulus in it, and ask what program implements the currying operation. The answer is: the program given by the s-m-n theorem.


DFAs that must reach a certain state at least once I was given this question:

  Let M = (Q,Σ, δ, q0, F) be a deterministic finite automaton. Assume that r∈Q is a state of M that is different from the start state q0.

  Define the language A⊆Σ* to be the language consisting of all strings that are accepted by M and cause M to enter the state r at least once.

  Give a precise description (the 5-tuple definition) of a deterministic finite
  automaton N that accepts the language A.

My question is, wouldn't it be possible to define N as (Q,Σ, δ, q0, F) with F={r}? Unless I am sorely mistaken, it should be able to meet the question's criteria shouldn't it?

If it happened that $F \{r\}$, then that would also happen to be a DFA to which you wouldn't have to do anything to answer the question, but it doesn't cover the case where $r \notin F$.

To rephrase the question a little, imagine you have a DFA $M$ that accepts language $L$, and someone picks a random state $r\neq s_{0}$, can you construct a DFA $M'$ that accepts language $L' \subseteq L$ where $s \in L'$ if it's in $L$ and it makes $M$ use state $r$?

Note that you don't get to pick $r$, it's essentially given as part of the input.

Taking it a little beyond your question, the answer is yes, it's possible, the trick is to do something special when you reach $r$.

A slightly more direct hint:

   Make a copy of $M$'s states (including accept status), cancel the accept status of any original states, and change the transitions out of $r$ to point to the counterparts in the duplicated set.


Path in an edge-weighted undirected graph Is it an $NP$-hard problem?

You're given an undirected graph $G(V,E)$ with edge weight $w: E \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$ in unary.

Does there exist a path in $G$ with overall product of edge weights equal $W$ and that does not visit any vertex $v$ more than $\mathrm{max}$-$\mathrm{visit}(v)$ times?

As D.W., point out in his comment. This problem is not $NP$-hard unless $NP\subseteq QuasiPoly$. The idea is that any such path must not contain more than $\log(n)$ edge of weight > 1.

Enumerate every such sequences of edges (with edge-weight > 1). There are ${O(n^2)}^{\log(n)}$ sequences like that.

For each sequence, to turn it into a solution, we need to fill in the "gap" with weight-1 edges.

This one is a little bit different from his comment. A flow is not the exact idea. What we need is the $k$ vertex-disjoint paths from classical work of Robertson and Seymour.

If the above description is not satisfying enough. Just note that we may split each vertex $v$ into a $\text{max-visit}(v)$-clique, and remember to connect each pair of cliques according to the original edges.


Longest possible path from root to a leaf of a red black tree For the worst case of a red-black tree, what would a tree with 10 nodes look like?Since there can not be 2 consecutive red nodes and there is rotation is it safe to say that it balances out the trees leveling it I tried this attempt at creating a tree with 10 nodes:

As you can read as "Properties" in the "Wiki Red-Black Tree", "the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.".

For a Red-Black Tree having 'N' nodes, the mean length path is 'ln(N + 1) + 1' (for 'N=10' 'Lmean = 2.397 + 1 >> 4').

Note: `ln(X) = neperian logarithm'.

So the Longest balanced-path from root to leaf is shorter than the double of the mean length '< 2 * ln(N + 1) + 1'. (for 'N= 10' longest < 8).


Determine the number of reachable states in a subset construction? Is there a polynomial time algorithm to determine the number of reachable states in the subset construction of a NFA to a DFA without having to construct the entire DFA?

Start with a 3SAT instance $\phi$ on $n$ variables with $m$ clauses $C_1,\ldots,C_m$. For each clause $C_j$, we construct an NFA $A_j$ which reads a binary input string, interpreting its first $n$ symbols as encoding a truth assignment, and checks whether the clause is satisfied. If $C_j$ is satisfied, then on the $(n+1)$'th symbol it branches to $n$ new states.
Now consider an NFA consisting of the NFAs $A_1,\ldots,A_m$ together with an initial state with $\epsilon$-transitions to the starting states of $A_1,\ldots,A_m$ (alternatively, if you allow multiple initial states, you can just put all of them together). If $\phi$ is satisfiable then the number of reachable states in the corresponding DFA will be at least $n^m$, otherwise it will be at most $n^{m-1} + 2^m n + 1$.


Is there a known maximum for how much a string of 0's and 1's can be compressed? A long time ago I read a newspaper article where a professor of some sort said that in the future we will be able to compress data to just two bits (or something like that).

This is of course not correct (and it could be that my memory of what he exactly stated is not correct). Understandably it would not be practical to compress any string of 0's and 1's to just two bits because (even if it was technically possible), too many different kind of strings would end up compressing to the same two bits (since we only have '01' and '10' to choose from).

Anyway, this got me thinking about the feasibility of compressing an arbitrary length string of 0's and 1's according to some scheme. For this kind of string, is there a known relationship between the string length (ratio between 0's and 1's probably does not matter) and maximum compression?

In other words, is there a way to determine what is the minimum (smallest possible) length that a string of 0's and 1's can be compressed to?

(Here I am interested in the mathematical maximum compression, not what is currently technically possible.)

Kolmogorov complexity is one approach for formalizing this mathematically.  Unfortunately, computing the Kolmogorov complexity of a string is an uncomputable problem. See also: Approximating the Kolmogorov complexity.

It's possible to get better results if you analyze the source of the string rather than the string itself.  In other words, often the source can be modelled as a probabilistic process, that randomly chooses a string somehow, according to some distribution.  The entropy of that distribution then tells you the mathematically best possible compression (up to some small additive constant).

On the impossibility of perfect compression, you might also be interested in the following.

No compression algorithm can compress all input messages?
Compression functions are only practical because "The bit strings which occur in practice are far from random"?
Is there any theoretically proven optimal compression algorithm?


NP-Complete Problem and Polynomial Hierarchy I have tried to search the internet to check if the following is correct:
If $\sum_{2}$ contains a NP-Complete problem then PH collapses to NP: $PH=NP$
For example if $SAT\epsilon\sum_{2}$ than: $PH=NP$

$\mathrm{SAT}$ and all $\mathrm{NP}$-complete problems are certainly in $\Sigma_2^P$, as $\mathrm{NP} \subseteq \Sigma_2^p$. It is true however that if $\mathrm{SAT}$ (or any $\mathrm{NP}$-complete problem) ever gets proven to be $\Sigma_2^p$-hard, then $\mathrm{NP} = \Sigma_2^p$, and consequently the polynomial hierarchy collapses to $\mathrm{NP}$.


Complete the following table by specifying the scope of each declaration I'm having a hard time understanding this question. Can each declaration have more than one scope or can a declaration have more than one scope?

If it's the later it would be:

Declaration              Scope
int a = 1;               B1
int b = 1;               B1
int b = 2;               B2
int a = 3;               B3
int b = 4;               B4

Or can it have more than one scope:

Declaration              Scope
int a = 1;               B1, B2, B4
int b = 1;               B1
int b = 2;               B2, B3
int a = 3;               B3
int b = 4;               B4

I'm sorry if this is a simple question. I just want to make sure what I'm doing is correct.

Thanks.

Your first answer is good (assuming the scope to assign is in order as declarations go).
Each declaration is in the scope, where it is declared. In inner scope (say B2) variable $b$ is declared shadowing previous declaration. Now you cannot use outer scope variable (read, write) as is by name without scope resolution operator.

Your second table suggests that variables are available in given scopes (say B1, B2, B4), and you have taken into account shadowing, so it still looks good, but technically it is accessible and not shadowed in that scope, not declared in that scope.


CFG to CFL conversion (production rule with both left and right recursion) Is there a general rule to convert a CFG to its CFL?
For example, how do I approach the following question?

What is the language generated by the following CFG?
$$ S \to aS \mid Sb \mid \epsilon $$

As per my understanding, $S\to aS$ is $a^*$ and $S\to Sb$ is $b^*$.
But how do I make sure that the language is $a^* b^*$ without having to derive a lot of strings?
In particular, is there a way to make it either in left or right recursion, so that it is easier to understand the structure?

Is there a general rule to convert a context-free grammar to a context-free language?

The answer depends on what you mean by "context-free language". A context-free grammar is one way to describe context-free languages, so in some sense the answer is a trivial "yes" – a context-free grammar is already a description of a context-free language.
Presumably you are interested in a more explicit description. In this case, the answer is probably "no", though it's impossible to tell unless you define your problem formally. The reason for the negative answer is the following undecidability result: given a context-free grammar over an alphabet $\Sigma$, determining whether it generates $\Sigma^*$ is undecidable.

How do I make sure that the language is $a^* b^*$ without having to derive a lot of strings?

In mathematics, the way to know things for sure is to prove them.

Is there a way to make it either in left or right recursion so that it is easier to understand the structure?

If a grammar contains only left-recursion or only right-recursion, then it is a left-regular grammar or a right-regular grammar, respectively (actually, whether this is true depends on what you mean by left-recursion and right-recursion, so I am making a guess). (Another common term is left-linear/right-linear grammar.) Such a grammar generates a regular language. Given that it is undecidable whether a given context-free grammar generates a regular language, there is no simple transformation that can change an arbitrary context-free grammar into one with only left-recursion or only right-recursion.
A grammar mixing left-linear and right-linear rules is known as linear; such grammars describe linear languages, a sub-class of all context-free languages which contains non-regular languages such as $\{a^nb^n \mid n \geq 0\}$, generated by $S \to aT \mid \epsilon, \, T \to Sb$.
It seems that even determining whether a given linear grammar describes a regular language is undecidable, see the comments to this answer by J.-E. Pin.


Why is big omega of peak finding Omega(lg n)? Why is big omega of finding a peak in an unsorted array Omega(lg n), not Omega(1)?

I understand that peak finding is O(lg n), because in the worst case, we find a peak in the last possible step, so when drawing a decision tree, the height of the tree (lg n) would be the worst case situation. However, in the best case, can't we get "lucky" and find a peak in the first try?

I think you got a bit confused with the definition of Big-Omega ($\Omega$).
The $\Omega(f(n))$ is a lower bound for an algorithm. It means that your algorithm's running time can not be less than $kf(n)$ where $k$ is a constant. And it applies to worst case not the best case.

edit
If you calculate your algorithm running time as $c\log{n}$, it's asymptotic analysis says that it is $\Omega(\log{n})$.

big omega notation


How is Dijkstra's algorithm related to breadth first search(BFS)? I've read in Introduction to algorithms(CLRS) that Dijkstra's algorithm uses ideas similar to those of  BFS? I think it really makes sense with respect to Dijkstra's algorithm with relationship to BFS when there are multiple short paths.
Consider the following problem for conclusion if you can see.

Yes the shortest path trees produced by djikstra's and BFS are identical in the case where the graph edge weights are represented by hop counts or in other words all the edge weights are 1 . Multiple Short Paths don't actually signify any relation with BFS . For finding the shortest Paths with BFS in a weighted graph we have modified versions of the algorithm.