Using pumping lemma to prove {a^ib^j | i > j} non-regular I'm having issues using the pumping lemma to prove $L_2 = \{a^ib^j \mid i > j \}$   is non-regular. It's obvious to know that the language is non-regular as there is no way of tracking $a^{i's}$ and $b^{j's}$

So I've done some digging.
On page 2 here I found a proof. However, it doesn't make sense to me.

Here is the proof, I will list my understandings as we go through the proof:

  Assume by way of contradiction that $L_2\in \mathrm{REG}$, then $L_2$ satisfies
  the conditions of the pumping lemma. Let $p > 0$ be the pumping
  constant. Consider the word $w = a^{p+1}b^p$.

Makes complete sense.

  Clearly $w \in L_2$ and $|w| > p$, so according to the pumping lemma
  there exist $x, y, z ∈ Σ^∗$ such that $w = xyz,$ $ |xy| ≤ p,$ $ |y| >
 0$ and for all $i ≥ 0$ it holds that $xy^iz ∈ L$.

Now if an $i$ is chosen to be $0$, this would conflict with $|y| > 0$? It seems it's using $L$ instead of $L2$. Is there a reasoning?

  Since $|xy| ≤ p$, then $x = a^n, y = a^m$, and $z = a^kb^{p+1}$ such that
   $m + n + k = p$, and $m > 0$.

This makes sense to me, as $z$ is equal to the rest of the $a's$ not in $x$ and $y$ plus all the $b's$.

  We pump with $i = 0$ and
  get the word $xz = a^nz = a^na^kb^{p+1}$. Since $m+n+k = p+1$ and $m >
 0$, then $n+k < p+ 1$.

Now this doesn't make sense to me. Pumping down ridding of $y$ contradicts the $|y| > 0$ rule and how does $m+n+k$ change to now equal $p+1$

  Thus, $xz \notin L_1$, in contradiction to the pumping lemma. So $L_2$ is not
  regular. Note that it is crucial to “pump down” for this language.

If you guys can help me understand this proof, that would be great thanks

Now if an $i$ is chosen to be 0, this would conflict with $|y|>0$?

Note it's $|y|>0$, not $|y^i|>0$, so there's no problem.

All your other confusions come from the typos in the proof. I rewrite the proof (the fixed typos are colored red) as follows.

... Clearly $w \in L_2$ and $|w| > p$, so according to the pumping lemma there exist $x, y, z \in \Sigma^∗$ such that $w = xyz,$ $ |xy| \le p,$ $ |y| >
 0$ and for all $i \ge 0$ it holds that $xy^iz \in L$. Since $|xy| \le p$, then $x = a^n, y = a^m$, and $z = a^kb^\color{red}p$ such that $m + n + k = \color{red}{p+1}$, and $m > 0$. We pump with $i = 0$ and get the word $xz = a^nz = a^na^kb^\color{red}p$. Since $m+n+k = p+1$ and $m >0$, then $n+k \color{red}{\le p}$ ...


Optimization-factoring $\le_p$ Decision-factoring Optimization factoring:
Input: $N\in \mathbb{N}$
Output: All prime factors of $N$

Decision factoring:
Input: $N, k\in \mathbb{N}$
Output: True iff $N$ has a prime factor of at most $k$

How can I solve the optimization problem in polynomial time if the decision problem is polynomially solvable?

You need to get an algorithm polynomial in $n$ where $n = \log N$ is the size of your input, i.e. the binary representation of $N$ (naive factorization algorithms are $O(N^2)$ which is of course exponential).

Given dec(k, x) solving the decision factoring problem, let's write a procedure to find the smallest prime divisor of $x$ using a dichotomy to keep logarithmic the number of steps.

sp(x):
  min = 2
  max = x - 1
  while (max >= 1 + min):
    k = floor ((min + max) / 2)
    if dec(k, x):
      max = k
    else:
      min = k + 1
  if x % (min + 1) == 0:
    return (min + 1)
  else if x % min == 0:
    return min
  else:
    return 1

The procedure above calls dec $O(\log x)$ times and find the smallest prime number that divides $x$, or 1 if it does not exist. Now we can easily define the following factoring function:

factor(x):
  p = sp(x)
  if (p == 1):
    print x
  else:
    print p
    factor(x / p)

Factor is called less than $\log x$ times (since $p ≥ 2$) so the number of calls to dec is bounded by $\log^2 x$ times on values less than $x$. If the complexity of dec is polynomial, let's say bounded by an increasing $P(n)$, then the complexity of factor is still polynomial, bounded by $n^2P(n)$.


Capsule networks for classification with limited data Capsule networks seem to match performance of convolutional neural networks on image classification tasks (more specifically on classification of handwritten digits in the MNIST dataset) 1.

I have also read in various articles that capsule networks require less training data than convolutional neural networks. Does this mean that a capsule network could reach the same accuracy as convolutional neural networks with less data? Eg. could a capsule network achieve the same accuracy as convolutional neural networks on the MNIST while only training on a fraction of the dataset?

Actually, the literature so far suggests that convolutional networks have better accuracy than capsule networks on many tasks, so it's by no means clear that capsule networks are superior across the board to CNNs.  This is perhaps not surprising; we have many years of experience working out how to engineer convolutional networks so we get the best possible performance out of them, whereas capsule networks are still new and haven't yet benefitted from that degree of engineering.  So, we might see further improvements in the performance of capsule networks in the coming years, now that they are getting more attention.

There are some specific areas where capsule networks have significantly outperformed convolutional networks.  Those seem to be primarily those where viewpoint invariance is especially critical.  There are others where so far they are worse.  For instance, capsule networks so far have done significantly worse than convolutional networks on CIFAR10.  There is active research and an active debate in the machine learning community about how well capsule networks will perform.  I think it's too early to say how that will pan out.

As far as amount of training data, it is likely that this will depend on the task as well, and is probably an open problem at this point.  I would imagine that capsule networks might need significantly less training data for tasks where viewpoint invariance is especially central, but that might not be true across all tasks.

In general, not a lot is known yet about the performance of capsule networks, and the answer to most questions of the form "how well will capsule networks perform on X?" is "you'll have to try it and see".


How profiling is done in trace scheduling? I'm trying to understand how trace scheduling works. The book that I'm reading, Engineering a Compiler by Keith D. Cooper & Linda Torczon, states that this method is using profiling. Profiling ranks each edge if the CFG by its frequency of execution. In other words the more a particular edge is followed the higher rank it has. So basically first the algorithm profiles the CFG and then runs  trace scheduling. The only way (in my view) to do profiling is to run the code so that each edge of the CFG can be ranked. Somehow I don't think this is being done.

Here are my questions:

So how is profiling done?
Does the compiler guess the rank of each edge?
If it does, then what is the foundation for the guess?

Yes, profiling is normally done by running the program.  Yes, running the program and then gathering information about execution frequencies is how this is normally done.  As Paul A. Clayton suggests, read more about profile-guided optimization to learn more about techniques commonly used in this field -- there's a rich literature on profile-guided optimization.

There are alternatives based on various heuristics or static analysis algorithms, but profiling normally implies running the program, and profiling will usually be considerably more accurate than any static technique.


Turing reducible in natural numbers? I'm confused about Turing reducible things.
I understanded Turing reducible like this
"There is an oracle algorithm which is about set A and when this algorithm is derived from oracle algorithm of set B, it is called A is Turing-reducible to B"
So by this, I have to solve the problem.

N is the set of natural numbers = {1, 2, 3, ...}
Let A be the set of all even natural numbers.
Let B be the set of all odd natural numbers.
Prove that A is Turing-reducible to B.

Here is what I have thought.
The oracle algorithm of A is n%2==0 which n belongs to natural numbers.
And oracle algorithm of B is n%2==1 which n belongs to natural numbers.
How can I derive n%2==0 from n%2==1 ?
Or my approach is wrong?
Thanks for your help.

To show that $A$ is Turing-reducible to $B$ you need to prove the existence of a Turing Machine that is able to decide $A$ when given access to an oracle for $B$.

In your specific case a possible Turing Machine $M$ takes as input a string $x \in \{0,1\}^*$ encoding the natural number $n$ (I'm assuming $0 \in \mathbb{N}$) in binary and operates as follows:

It flips the last bit of $x$. Now $x$ represents an odd number iff the input number $n$ was even.
It invokes the oracle for $B$ with input $x$.
It accepts iff, according to the oracle, $x \in B$.

Notice that the fact that $M$ has access to an oracle for $B$ does not mean that $M$ must use that oracle. The following is also a valid choice for $M$:

Locate the last bit $y$ of the input string $x$.
If $y=0$ accept. Otherwise reject.


Maximum cut optimisation Consider the algorithm below which calculates a V cut

Initialize $V_1 = V$ et $V_2 = \emptyset$
Attempt to improve the value of the cut in any of the following ways

Check if there is a $v \in V_1$  such as $c(V_1-\{v\}, V_2 \cup \{v\}) > c(V_1,V_2)$

If yes continue with $V_1 = V_1 -\{v\}$ et $V_2 = V_2 \cup \{v\}$.

Check if there is a $v \in V_2$ such as $c(V_1 \cup \{v\}, V_2 - \{v\}) > c(V_1,V_2)$ If yes continue with  $V_1 = V_1 \cup \{v\}$ et $V_2 = V_2 - \{v\}$.
When improvement is no longer possible, return the cut $V_1, V_2$

1 . How can I prove that the algorithm is executed in polynomial time by displaying done at most $|E|$ iterations.

Let $(V_1,V_2)$ be a cut. For a $v \in V_1$ we call $\alpha(v)$ the neighbors of $v$ which are in $V_1$ and $\beta(v)$ the neighbors of $v$ which are in $V_2$.If $v \in V_2$, we set $\alpha(v)$ and $\beta(v)$ the neighbors of $v$ which are in $V_2$ and $V_1$ respectively.

How to prove that if the algorithm can no longer advance then for everything $v \in V$ we have $|\alpha(v)| \leq |\beta(v)|$

1) is easy. As you say the algorithm can perform at most $O(|E|)$ iterations. Initially $c(V_1, V_2)=0$. Each iteration, except the last, increases $c(V_1, V_2)$ by at least $1$. The claim follows since $c(V_1, V_2) \le |E|$.

2) Suppose that, for some $v \in V_1$, $|\alpha(v)| > |\beta(v)|$ Then moving $v$ from $V_1$ to $V_2$ increases the value of $c(V_1, V_2)$ by $|\alpha(v)|$ and decreases it by $|\beta(v)|$, therefore $c(V_1 \setminus \{v\}, V_2 \cup \{v \}) = c(V_1, V_2) + |\alpha(v)| - |\beta(v)| > c(V_1, V_2)$. This shows that  the algorithm could not have terminated. The case $v \in V_2$ is symmetric.


Reducibility and Artificial Neural Networks I have read (here and here
) about the computational power of neural networks and a doubt came up.

There is a way to reduce an ANN to another ANN (not taking into count the training algorithm) ? e.g. Reduce a Recurrent Neural Network to a Multilayer Perceptron, meaning that if I have a trained RNN, I can get a MP that maps the same inputs given to the RNN to the same outputs produced by the RNN.

And if exists an answer to the above question, we can show the equivalence between neural networks, e.g., all problems solved by an Multilayer Perceptron can be solved by a Recurrent Neural Network but the opposite is not true, i.e., $MP \subset RNN$ (I do not know if this is true, is just an example). So, if we obtain this relationship between all neural networks, we can get a neural network $X$ that is more powerful than others, so, we can throw away all other neural networks because $X$ can solve any problem that other NN can. Is this reasoning correct ?

Thanks.

Not really.  I respect what you're trying to achieve, but I don't think it's possible to achieve what you want, given our current level of knowledge of neural networks.

We already know that convolutional neural networks perform better for some problems, and fully-connected neural networks (what you call MP) work better for other problems.  So you can't expect to find that one is always better than the other.

It has been proven that any computable function can be approximated arbitrarily well by some fully-connected neural network.  However, the catch in this theorem is that the theorem doesn't tell us how large the neural network needs to be.  We already know that sometimes a larger network is more accurate, but is also slower to train, so that's a pretty big caveat in the theoretical result.

And if you want to compare two different network architectures -- say, convolutional vs fully-connected -- then such a comparison won't be useful if it doesn't take into account the size of the network.  If you need 1 billion parameters to make a fully-connected network work well, or 1 million parameters to make a convolutional network work well, are they equally good?  No, you'll probably prefer the convolutional network.  It's not at all clear how to get useful reductions between the two architectures that tells us anything about the size of the neural network.

So, no, you're probably not going to get some useful theory this way that says "you can throw away all other architectures other than type X".


reverse string to pattern matching I have a list of patterns, and I need to find the pattern that matches an input string the most. I.e.:

Patterns:

[
    'AB1XXX',
    'AB2XXX',
    'ABXXXX-0080',
    'BC1XXX',
    'BC15XX'
]

The X character in the patterns is reserved as the wildcard or don't care character. It can be any single alphanumeric character.

I then get an input, i.e.: AB1100. In this case I expect the pattern AB1XXX to be the best match.
However, if I get an input AB1100-0080 I expect ABXXXX-0080 to be the best match for the given input.

I currently use a Trie to find the matching pattern, but it doesn't really work for the given example as it either can't find a match once it gets to -0080.

Best match can be seen as "shortest Levenshtein distance with the least amount of X characters used".

Is there a known algorithm I could implement or should I stick to implementing a Levenshtein distance algorithm?

The Shortest Levenshtein's Distance should be good enough.
See if this Matching Wildcards Wikipedia page can be of help.


Overflow rule in two's complement arithmetic In the book by William Stallings the overflow rule overflow rule for 2's complement addition is stated as follows:

  Overflow rule: If two numbers are added, and they are both positive or both negative, then overflow occurs if and only if the result has the opposite sign.

Then the book gives the following examples:

Doubts:

If two numbers with the same sign are added, shouldn't the result have the same sign?  How can the result have an opposite sign (e.g., $+1+2=+3$ and $-1-2=-3$)?
Point 1 is reflected in the examples (d), (e) and (f). An overflow seem to occur in all of them  (though the word "Overflow" is not printed in example (d)), but the sign of the result is the same as that of operands.

Yes, if we are talking about integers. In two's complement representation with length $n$ you can only represent the integers between $-2^{n-1}$ and $2^{n-1} - 1$ (both bounds inclusive). Thus, the addition operation is not the same as the one over the integers—it is not even a proper operation because of overflows, which are left undefined; since it is a completely different operation, other rules apply (as I expect to have been previously mentioned in the book's text).
Do not mistake "overflow" for the result having a 1 carry at the left end. In example (b), for instance, the result of addition has such a carry, but it is truncated back to 4 bits, hence producing a correct result; the same happens in (d). However, an overflow occurs in both (e) and (f) because then the result is outside the representation range for 4-bit two's complement, that is, between $-2^{4-1} = -8$ and $2^{4-1} - 1 = 7$.


Why doesn't Dijkstra's use a shortest-path first search? When using BFS search on an unweighted graph to find the single-source shortest paths, no relaxation step is required because a breadth-first search guarantees that when we first make it to a node, we have found the shortest path to it.

However, my understanding is that Dijkstra's algorithm has no such guarantee because the neighbours of each node are checked in no specific order. Therefore, we need a relaxation step to update the shortest path of each node if we later find a shorter path.

Instead of choosing a random neighbour, why not always follow the neighbour with the shortest path? I think that would guarantee we have always found the shortest path and no relaxation step is required. I implemented this in Python and it seems to work. Am I missing something?

from heapq import heappop, heappush

def shortest_path_lengths(graph, source):
    dist = {}
    q = [(0, source)]
    while q:
        source_to_v1_dist, v1 = heappop(q)
        if v1 in dist:
            continue
        dist[v1] = source_to_v1_dist
        for v2, v1_to_v2_dist in graph[v1].items():
            if v2 not in dist:  # check it hasn't been visited already
                heappush(q, (source_to_v1_dist + v1_to_v2_dist, v2))
    return dist

graph = {
    'a': {'b': 3, 'c': 5},
    'b': {'c': 1},
    'c': {'d': 4},
    'd': {},
}
print(shortest_path_lengths(graph, 'a'))

Congratulations! You have discovered an interesting variation of Dijkstra's algorithm.

However, it is misleading to state the standard version of Dijkstra's algorithm (stDA) described here as mentioned in the question does not use a shortest path first search. You might have overlooked the following statement in that article

  We now need to pick a new current node. That node must be the unvisited node with the smallest minimum distance.

In fact, using a shortest path first search so that the weight of each edge is checked at most once is the hallmark of Dijkstra's algorithm. That is the main reason that your algorithm can be labelled as a variation of Dijkstra's algorithm.

While the neighbours of each node are selected in no specific order in stDA, the same unorderly selection is also done in your algorithm in the following lines

        for v2, v1_to_v2_dist in graph[v1].items():
            # code to record the distance to v2 via v1.

Instead of including each vertex exactly once in the priority queue of unvisited vertex as in stDA,  your algorithm pushes each vertex multiple times, once for every path that could possibly be the shortest path to that vertex at the moment that path is found. (This might make your algorithm slightly slower than stDA, since the number of operations to insert a new  distance-vertex pair into the bigger min-heap in your algorithm will probably be more than the number of operations in the stDA needed to update the shortest distance so far to that vertex. For example, when the new distance is not shorter than the shortest distance so far.)

Instead of the separate relaxation step as in the stDA, your algorithm cleverly accomplished the object of the relaxation step in the same step that selects the shortest path to an unvisited vertex by also ignoring all other paths to visited vertices. It is fair to say your algorithm includes the relaxation step implicitly.

Overall, your algorithm is slightly easier to code than the stDA.


Lamport logical clock: what does partial mean in the concept of `Partial ordering`? In lamport's paper[1], he define two concept The partial ordering and The totally ordering.

What does partial mean in partial ordering?

assumption: this ordering only handle two cases, one is to order events happening in single process, second is communication events between two process. It can't handle concurrent events, so it's named as Partial ordering.

Is my assumption correct?
What does totally ordering mean?

Does that mean it can handle all the events in a distributed system?

Reference

Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System.”

The "partial ordering" in the papar means partial order as in standard mathemtics theory. To be more rigorous, the "partial ordering" in that paper, also called "irreflexive parital ordering" in that paper, means strict partial order.  (Yes, "strict" means "irreflexive".) (Yes, "order" can be used interchangeably with "ordering" sometimes. I prefer "order" in a mathematics environment and "ordering" in non-mathematics environment, since "order" is such a common English word.)

Informally, that "partial" means it is possible a "<" relation thereof is missing for some pairs of elements. Here is an example. Let $S=\{a,b,c\}$. We can define a relation $<_1$ on $S$ by $a<_1 b$ and $a<_1 c$. That is all. Note we did not say anything about the relationship between $a$ and $c$. In fact, we have specified that there should not be a relationship between $a$ and $c$. These two elements are incomparable. That is why we say $<_1$ is a "partial" relation on $S$.

In that paper, for example, $p_3$ and $q_3$ are two incomparable events. We cannot say $p_3\to q_3$ nor $q_3\to p_3$. The order relationship between $p_3$ and $q_3$ is missing. It is not defined. That is why it is referred as a "partial" ordering. "It can't handle concurrent events, so it's named as Partial ordering." That understanding is pretty good. However, I would phrase it as "It does not order concurrent events, ...". I mean, it does handle concurrent events, resulting in that concurrent events should be treated as incomparable.

In contrast, "a total ordering" or, a total order is a partial ordering under which every pair of elements are comparable. If you find these two math terms sound contradictory, think of them as square are also rectangles. In fact, the "total ordering" in the paper is the strict total order. Yes, you can understand that "total ordering" means "it can handle all the events in a distributed system", or "it can order every pair of events in a distributed system (as defined in the paper)".

You may find lots of terminologies in the theory of partially ordered set and order theory. It looks like overwhelming initially. However, most of the concepts are very easy to understand intuitively.

In your case, all you need to understand is how is $\to$ defined on the set of events of a system and that a total ordering is such a special $\to$ that for any two events $e_1$ and $e_2$, either $e_1\to e_2$ or $e_2\to e_1$ must hold. You could ignore all those formal concepts in math theory even though they might help understand more things later more clearly.

As mentioned by Gokul, here is a pretty good explanation about Lamports's logical clocks.


Which grows asymptotically faster, $\log \sqrt{n}$ or $4 \log n$? I have been looking at the question as to which grows faster asymptotically; $\log \sqrt n$ or $4 \log n$.  I have applied L'Hopitals rule and ended up with 1/8.  This would imply that they grow at same rate.
Graphically $4 \log n$ is always above $\log \sqrt n$.  Also from a perspective that $4 \log n$ is $\log n^4$ would imply intuitively that growth of $4 \log n$ is faster asymptotically
There appear to be contradictions.

The asymptotic growth of
$4 \log n$ is referred to as $\Theta(\log n)$.  You will have to look at
the definition of asymptotic growth to see why that is the case, but
intuitively, it is the growth of a function when we discard constant
factors and only look at the function "in the limit".
You have found out that the difference between the two functions "is
1/8", which makes sense, and which would put these two functions in the
same "growth class".
When it comes to $\Theta\left(\log ( \sqrt n ) \right)$, it is, as you
likely have found out
$$\Theta\left(\log ( n^{1/2} ) \right) = \Theta\left( \frac{1}{2}\log n
\right) = \Theta\left(\log n \right).$$


interval scheduling variant: 1 machine with 2 tasks need to complete only I am looking for an optimal solution of an interval scheduling variant.

Basically, given n tasks with the start time Si and end time Ei, select EXACTLY two tasks whose execution periods are maximum and do not over lap (Equal start/end time counts as overlapping).

So if there are these task [9-14], [7-13],[1,4],[2-5],[2-10],[4-9]

The answer would be [1,4] and [7-13], whose execution time are 3+6=9 in total.

I can only think of an algorithm with n^2 complexity. That is the obvious solution of matching every period together, check if they overlap, and if they don't, replace a previously initialized Max value with their sum if it > Max. It does not seem to be optimal, as it does not pass the time test in my professor exercise.

So anyway, can anyone think of a more optimal solution?

Let $max$ be the maximum period of the tasks we have checked so far. Let $max2$ be the maximum sum of two non-overlapping tasks we have checked so far. Both of them are 0 initially.

Sort all start times and end times of the given tasks. Iterate over them, from the smallest to largest.

A start time is encountered. If the sum of the period of the corresponding task and $max$ is greater than $max2$, update $max2$.
An end time is encountered. If the period of the corresponding task is greater than $max$, update $max$.

Now $max2$ is what we wanted. The algorithm runs in $O(n\log n)$.

The above algorithm does not specify what to do when multiple times are encountered at the same time. That part should be easy for you to fill in.


What is a good example of an NL-complete context free language? Setting
Exactly as the title stated:

  Give an example of an $\mathsf{NL}$-complete context free language. $\newcommand{\angle}[1]{\langle #1 \rangle}$

Current Solution

Recall in the past we proved that $E_{DFA}$ is regular, so it is also context free. $E_{DFA}$ is in $\mathsf{NL}$ since given DFA $\mathcal M$ over $n$ states, we can start at the initial state and nondeterminstically traverse through states of $\mathcal M$ for at most $n$ steps, storing only the current state ($\log n$ space). Note if there is a path to an accept state, then it must be $\le n$ steps long. So if there is no path to an accept state within $n$ steps, then $\mathcal M$ does not accept any string, thus $\mathcal M \in E_{DFA}$.

Now we show $\overline{PATH} \le_l E_{DFA}$ and since $PATH$ is $\mathsf{NL}$-complete and $\mathsf{NL} = \mathsf{coNL}$, it follows that $E_{DFA}$ is also $\mathsf{NL}$-complete. Given an instance $\angle{G,s,t}$, we construct a DFA $\mathcal M$ by letting $s \in G$ be $q_{initial}$, and $t \in G$ be $q_{accept}$. We label the edge arbitrarily from $\{0,1\}$. Clearly this can be done in log-space. So now we show
    $$\angle{G,s,t} \in \overline{PATH} \Leftrightarrow \mathcal M \in E_{DFA}.$$

Suppose $\angle{G,s,t} \in \overline{PATH}$, then there is no path from $s$ to $t$, so there is no path from $q_{initial}$ to $q_{accept}$ in $\mathcal M$, then $\mathcal M$ does not accept any strings so it is in $E_{DFA}$. Conversely, suppose $\angle{G,s,t} \not\in E_{DFA}$, then there is a path from $s$ to $t$, taking this path in $\mathcal M$ correspond to a $\mathcal M$ accepting some string, so $\mathcal L(\mathcal M) \ne \emptyset$ and $\mathcal M \not\in E_{DFA}$.

Problem

I don't think my algorithm for proving $E_{DFA} \in \mathsf{NL}$ is correct.

In other words, you are asked to find an $\rm NL$-complete language $A$ and a context-free language $B$ such that $A \equiv_{\rm{L}} B$. We choose $A = \it{PATH}$ and $\{{\tt{0}, \tt{1}， \tt{\#}}\}^* \supseteq  B = f(A)$, in which $f: A \to B$ is defined as follows.
    $$
\newcommand{\Bra}[1]{\langle #1 \rangle}
  f(\Bra{G, s, t}) = \Bra{s}^{\mathcal{R}}({\tt{\#}} \Bra{e_1} \Bra{e_2} \cdots \Bra{e_m} {\tt{\#}} )^n\Bra{t},
 $$
    where $G = (V, E)$, $|V| = n$, $E = \{e_1, \dots, e_m\}$, $\Bra{e_i} = {\tt{\#}}\Bra{u_i}{\tt{\#}}\Bra{v_i}^{\mathcal{R}{}}{\tt{\#}}$ if $e_i = (u_i, v_i)$.


Find one-variable recursive formula for running time of Karatsuba multiplication I'm currently trying trouble to set up the recursive expression for the Karatsuba multiplication of two integers with $n$ and $m$ bits (both having a different number of bits). Usually, the recursion for two $n$ bit integers for Karatsuba multiplication would be:

$T_{n} = \begin{cases} 3T_{n/2} + cn &\mbox{if } n > 1 \\ 1 &\mbox{if } n = 1\end{cases}$

However, when working with two integers with different number of bits, the expression would be different, as we would have $T_{n,m}$ as a recursion. Is there any way to reduce the problem of setting up the recursion in terms of only one variable $n$? I was thinking of letting $T_{n}$ be the maximum number of operations with the pairs $(n,m)$, and basically giving the same recursive formula as stated above. Would that change the running time of the program or is there a more clever way to change it into a one variable recursion?

The recurrence with two variables $n,m$ is as what you have obtained:

$$T(n, m) = 3T(n/2, m/2) + O(\max(n,m))$$

Assume $n = \Omega(m)$. We have

$$T(n, m) = 3T(n/2, m/2) + O(n)$$

Although the master theorem cannot be applied directly, if you expand this recurrence, then you will eventually identify the patterns and the result:

$$T(n, m) = 3T(n/2, m/2) + O(n) = \cdots = \sum_{k=?}^{k=?} (3/2)^{k} \cdot O(n) + c \cdot T(n/m,1) = \cdots$$
Please find out $c$ and the range of $k$, and fill the gaps.

There is a method to reduce the two variables $n,m$ recurrence to a single one:

  Assume $n = \max(n,m)$ and pre-append $n-m$ $0$'s to the integer with less bits.

The problem is this will yield a different time complexity from that given above. This can be seen from an extreme example: $1$-bit $\times$ $O(n)$-bit.


Finding a small Moore machine that checks the last four bits I am looking for a Moore finite state machine that returns true if and only if the last 4 bits (the input is of bits) are 0011 or 0101, the FSM can return any value at the first 4 bits (yes, even at the 4th).

The issue is that I was asked for a 7 conditions (vertexes) limit, and despite my efforts could not create one, my questions are the following :

Is there a FSM that solve this at 7 conditions (7 vertexes)? If there is than what is it and if not how can I prove there isn't?
Is there any type of 'algorithm' to approach this? I can easily well define one if we can use as much conditions as we wish (16 for our case) but what way other than intuition can lead me to reducing to 7 conditions?

Since you have been given an upper limit to number of states, the best way to go about solving this problem is to get a correct solution first independent of number of states and then minimize the automata. Every moore automata has a canonical unique automata of minimum number of states (meaning all minimum state automata are equivalent).

As the solution is following and you cannot minimize the moore automata any further, you can declare that you cannot solve the problem with 7 states:

By the way, minimization of moore automata is similar to minimization of deterministic finite automata. We need to find equivalent states and merge them. Refer DFA Minimization.


Conceptual question about entropy and information Shannon's entropy measures the information content by means of probability.  Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that we are more uncertain about what will happen next.

What I would like to know is if entropy increases, does this mean that information increases?
If there are 2 signals, one is the desired and the other is the measurement signal. Let error be the difference between the two. Or error can be the estimation error in the context of weight learning.

What can we infer if the entropy of this error term decreases? Can we conclude that the error is reducing and the system is behaving close to the desired signal's behavior?

Shall be grateful for these clarifications

Information = Entropy = Surprise = Uncertainty = How Much You Learn By Making an Observation.  They all increase or decrease together.  The entropy of a random variable $X$ is just another number summarizing some quality of that random variable.  Just like the mean of a random variable is the expected value of $X$ or the variance of a random variable is the expected value of $(X - \mu)^2$, the entropy is just the expected value of some function, $f(X)$ of the random variable $X$.  You find expectations of functions by using
$\mathbb{E}[f(X)] = \sum_{x\in X}p(x)f(x).$  In this case the function of $X$ you care about is the log (base 2) of the probability mass function.

$$ H(X) = \mathbb{E}[-\log_2 P(X)] = -\sum_{x \in X} p(x) \log_2 p(x).$$

This particular expectation is useful because it doesn't depend on the actual values that $X$ can take on, just the probabilities of those values.  So you can use it to talk about situations where you aren't sending numbers, or where the numbers are just arbitrarily assigned to particular messages or symbols that you need to send.

What you want for your second question is the conditional entropy of the measurement random variable $X$ given the random variable $Y$ that represents what was sent.  When there is no error the conditional entropy will be 0, when there is error the conditional entropy will be greater than 0.


Is {xyx | |x|≥1} context-free? Is $L=\{ xyx \mid x,y \in \{a,b\}^* \text {and } |x| \ge 1 \}$ context-free?
If yes, please explain how we can write grammar or create a PDA for it. If not a CFL, then prove it through pumping lemma.

I have tried to apply the pumping lemma with $w = a^nb^naba^nb^n$ as the word in $L$, but without success.

Consider $w = a^nb^na^nb^n$, then it is similar to proving language {ww} is not CFL.

In the given language there is no restriction on length of y. So, let it be zero.
Now, for any valid decomposition w = uvxyz, $uv^ixy^iz$ belongs to L.


Scheduling algorithms and quantum time I would like to know what impacts does a scheduling algorithm, let's say Round Robin or FIFO, have on an Operating System. I understand that a scheduling algorithm has the processes run in burst then switch between one another. But what does this mean for an OS. All I can figure out is that the OS has to keep track of which process is running, see if it has done/completed its operation, choose/switch to another process and run it for a given time. Am I missing the obvious here? It does not really seam to me that a scheduling algorithm really affect the OS per se but the CPU hardware.

It seems that the missing piece here is that the switching does not only occur when a process completes.  The switch will occur when either 1) the process completes, or 2) when the process explicitly yields its remaining run time slice (whatever it has not used of its time quantum), or 3) when the OS pre-emptively interrupts the process due to that process having been running for all of its assigned time quantum.

The OS is responsible for allowing all the processes that need to get 'OnProc' (on processor) some time to actually be running on a processor.  The scheduling algorithm is what determines how "fair" the choice of which process next gets to run on a processor is.  Note that technically all of the above really should have the word 'process' replaced with the word 'thread' (of which a single process may have many, and also not all threads necessarily have a process associated with them)

As for what the impact is on the OS - that is a question that needs more definition.  I can say that other than the scheduler threads and timers and interrupts, generally all threads are subject to the scheduler so the OS will be impacted by the choice of algorithm.


Why does many to one reduction imply Turing reducibility? So, $ A\leqslant_mB $ (many to one reduction) means that language $A$ can be reduced to language $B$ if there exists a Turing-calculable function $f$ so $ f(A) \subseteq B$ and $ f(\overline{A}) \subseteq \overline{B} $.

$ A\leqslant_TB $ (Turing reducibility) means that language $A$ can be Turing-reduced to language $B$ if there exists an oracle machine $O^B$ which decides $A$.

I sort of get them both individually, but I don't get why $ \leqslant_m $ implies $ \leqslant_T $.

To put it informally, $A\leq_{\mathrm{T}}B$ means "If I had a subroutine for $B$, then I could solve $A$", whereas $A\leq_{\mathrm{m}}B$ means, "If I had a subroutine for $B$, then I could solve $A$ using a program that calls the subroutine only once and, furthermore, just returns the answer of the subroutine without doing any further calculation."

If you can solve a problem using a subroutine such that blah blah blah, you can solve that problem using the subroutine.


Presentation of context rules for the lambda-calculus Reading Chris Hankin's book, "An Introduction to Lambda Calculus for Computer Scientists", I learnt that the rules for reductions in the pure  $\lambda$-Calculus are the $\beta$-reduction rule,
$$(\lambda x.M)N = M[x:= N]$$
and also these:
$$\frac{M=N}{N=M}$$
$$\frac{M=N}{MZ=NZ}$$
$$\frac{M=N}{ZM=ZN}$$
$$\frac{M=N}{\lambda x.M = \lambda x.N}$$
The author calls this "The Theory $\lambda$"; and although he formally defines contexts, he does not use them there.

Now, some other works -- for example, Didier Rémy's "Type Systems for Programming languages" -- seem to imply that there are only the $\beta$-reduction rule, and a context-rule:
$$(\lambda x.a)v \to a[x:= v]$$
$$\frac{a\to a'}{e[a]\to e[a']}$$
Here $e[]$ is an evaluation context, "$a$" is an arbitrary term, and "$v$" is a value (which the author defines to be an abstraction -- variables, he says, are not values).

I am a bit confused. I think (but I'd need confirmation) that they are saying the same thing, but Rémy's approach actually allows for the specification of evaluation strategy (because I can then decide if the context hole will be to the left or to the right, etc), while the presentation by Hankin does not.

Is this correct, or did I completely miss the point?

The two formulations are saying almost the same thing. Hankin's presentation has a symmetry rule ($\frac{M=N}{N=M}$), which is strange: it ends up defining the relation “$M$ reduces to $N$ or $N$ reduces to $M$”. That's unusual; usually, when a relation is written $=$, it's either explicitly defined to be an equivalence relation (with explicit or deducible rules for reflexivity symmetry and transitivity) or implicitly defined as the equivalence induced by the explicitly-given rules.

Giving separate rules for different context forms is equivalent to stating a single context rule and, separately, describing contexts. For example, for the pure lambda calculus, you can have a separate deduction rule for each way to decompose a term syntactically:
$$
\frac{M \to N}{M\,Z \to N\,Z} \qquad
\frac{M \to N}{Z\,M \to Z\,N} \qquad
\frac{M \to N}{\lambda x.M \to \lambda x.N}
$$
or you can have a single deduction rule plus a grammatical presentation of contexts:
$$
\frac{M \to N}{C[M] \to C[N]} \qquad
C ::= [] \mid C Z \mid Z C \mid \lambda x. C
$$
(In both cases, that's in addition to the beta rule.)

Other notions of reduction with more restrictive contexts can be expressed in two ways as well. For example, weak head reduction (which forbids reduction under lambda) can be given as the beta rule plus either
$$
\frac{M \to_H N}{M\,Z \to_H N\,Z} \qquad
\frac{M \to_H N}{Z\,M \to_H Z\,N}
$$
or
$$
\frac{M \to_H N}{C_H[M] \to_H C_H[N]} \qquad
C_H ::= [] \mid C_H Z \mid Z C_H
$$

If you're going to manipulate several different notions of reduction, the presentation in terms of contexts is more compact: there's a single context rule, and its formulation is usually obvious so it can be omitted, all that needs to be stated is the permitted contexts if some syntactically valid contexts disallow reduction.

If you're only ever going to use a single notion of reduction, introducing contexts requires some extra syntactic baggage. But this extra baggage has the advantage of making it clearer what's going on: it makes it easier to see where a reduction is happening in a context and where actual computation is happening. So it's a pedagogical trade-off.


Deterministic algorithms for computational distance between distributions Computational distance between sequences of distributions $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ can be defined as the maximum, over all probabilistic polynomial time algorithms $A$, of
$$ \left|\underset{x \sim X_{n}}{\mathsf{Pr}}(A(x) = 1) - \underset{x \sim Y_{n}}{\mathsf{Pr}}(A(x) = 1)\right|, $$
for each $n \in \mathbb{N}$. We can, very similarly, define computational indistinguishability to be when the computational distance is a negligible function of $n$. Here is my question: can we use a deterministic polynomial-time algorithm in place of a probabilistic one without loss of generality? Can we say that the maximum computational distance is achieved by a deterministic algorithm? Will this algorithm be non-uniform?

Hint:

 Every randomized algorithm $A(x)$ can be expressed as a deterministic algorithm $A(x;r)$ where $r$ is randomly chosen.  Now what can you say about the value of that absolute difference for different choices of $r$?  What would you like to be able to say about it?


Prove disprove an existence of mapping reduction between 2 sets I am currently studying mapping reduction in computational theory and finding it hard to grasp the concept fully.

For reference, consider the following given WHILE-Prog sets:

A = { (p.d) | p doesn't halt on input d } = Complementary HALT set.
B = { p | p halts on exactly one input (the input is unknown) }

Is A < B. meaning, is there a mapping reduction from A to B?

Can someone suggest a hint?

knowing that A belongs to coRE did not help much.
B doesn't seem to belong to either RE nor coRE.

One basic idea is to observe that $B$ looks harder than $A$ since

we need to run a given Turing machine on one given input in order to find whether the pair is in $A$ but
we may need to run a given Turing machine on infinity many inputs in order to find whether it is in $B$.

That observation should motivate us to find a reduction from $A$ to $B$.

Suppose $(p,d)\in A$. Construct a machine that behaves as the following.

Upon an input string $s$, it checks whether $s$ is $d\sigma$, where $\sigma$ stand for a fixed letter in the alphabet.

If yes, it halts.
If no, it checks whether $s$ is $d$.

If no, it loops forever.
If yes, it simulate $p$ on $d$.

It should be routine to verify the construction above is indeed a reduction from $A$ to $B$.


Analysis of Dijkstra algorithm's (Lazy) running time I'm trying to figure out the running time for a Dijkstra algorithm. All the sources I have read say that the running time is O(E * log (E)) for a lazy implementation.

But when we do the math we get O(E * (Log(E)+E*Log(E))).

Since E isn't a constant, I don't see how someone could reduce this to O(E * log (E).

Are we analyzing the wrong or is it possible to reduce?

        while (!minPQ.isEmpty()) { <=== O(E)
            Node min = minPQ.poll(); <=== O(log(e)

            for (Edge edge : graph.adj(min)) { <=== O(E)
                if (min.getId() == target.getId()) {
                    // Source and Target = Same edge
                    if (edgeTo.size() == 0) edgeTo.put(target, edge);

                    return;
                }

                relax(edge, min, vehicle); <=== log(e) (because of add method on PQ)
            }
      }

First of, you can make some of the bounds a little tighter and replace some $E$s with $V$s.
The while loop at the beginning will only run $O(|V|)$ iterations (you visit every node only once), and the for (Edge edge : graph.adj(min)) loop will run only $O(|V|)$ iterations at most (a node can have at most $O(|V|)$ adjacent edges).
Same with the log factors, although in that case it doesn't matter as much since $O(\log |V|) = O(\log |E|)$ (if the graph is connected).
Via simple multiplication this gives you $O(|V| \cdot (\log |V| + |V| \cdot \log |V|)) = O(|V|^2 \cdot \log |V|)$.
In a dense graph, this is already the desired complexity. Since a dense graph has $O(|V|^2) = O(|E|)$.

However in a sparse graph, e.g. when $O(|E|) = O(|V|)$, then you can still do a lot better.

The problem you are facing is that multiplying the upper bounds can lead to overestimation. Look at the following example:

for (i = 1 to N) {
    limit = N if i == 1 else 1
    for (j = 1 to N) {
        constant_work()
    }
}

The outer loop clearly runs $O(N)$ times, and the inner loop runs also $O(N)$ times (because in the worst case it does).
You can say that in total the complexity is $O(N^2)$ times. But this is just an upper bound.

Most of the time the inner function actually does almost no work.
In reality if you count the number of times you run the function constant_work(), you will get
$$N + 1 + 1 + \cdots + 1 = 2N - 1 = O(N)$$
$N$ iterations for i == 1 and otherwise only $1$ iteration.
So the code runs in $O(N)$ time.

The same effect happens when you loop over edges next to a node: for (Edge edge : graph.adj(min)).
Yes, in the worst case you have $O(|V|)$ edges, but in a sparse graph, most of the time you have a lot less.

You can count them from a different angle. If you fixate an edge $(u, v)$, how often will you touch that edge, and move into the body of the loop?
Only twice! Once when min == u, and once when min == v.
Therefore the inner part of the loop, with runtime $O(\log |V|)$, will run only $O(2 |E|) = O(|E|)$ times. Which means that the whole thing runs in $O(|E| \log |V|)$.


How is this reduction of 3-SAT to Half-SAT not valid? I am studying algorithms and there is a question in CLRS called the Half-SAT problem

We are given a 3-CNF formula with n variables and m clauses where m is even. We wish to determine whether there exists a truth assignment to the variables of f such that exactly half the clauses evaluate to zero and the other half to 1. Prove that the half 3-SAT problem is NP-Complete.

What is to stop me from taking any input f to 3-SAT and adding m clauses (y or y or y) where y is not in the original m clauses. The transformation of input and output is clearly polynomial time.
And, given a solution to 3-SAT, there must be a satisfying solution to Half-SAT (the solver sets y to false). If there is not a solution to 3-SAT this means that one of the original m clauses is not satisfied these clauses are disjoint from the new clause, so either m - 1 or 2m - 1 clauses are True.
Yet all the solutions online are more complicated which makes me think I am missing something obvious.

As mentioned in the comments, this reduction is incorrect because it is necessary to have equivalence. While we may have 3-SAT => Half-SAT we do not have !3-SAT => !Half-SAT or Half-SAT => 3-SAT (the contrapositive). A proper reduction would need to do something like so:
Add m + 1 clauses (y or y or y)
Add a contradictory clause (y or not y)
Now exactly half of the clauses are True iff there is a solution to 3-SAT.


Exactly how many clocks does a Computer consists of and how do they synchronize with each other? I am currently trying to understand how Computers are arranged and organized internally (so that I can learn Assembly Language) through an online book called The Art of Assembly by Randall Hyde. Irrespective of whether or not I'll learn Assembly, I'm finding it difficult to understand exactly how is everything synchronized in the Computer. I'm currently at 3.2 - System Timing topic.

Below are my observations and the things I currently understand not only from the book but also from the things I learned through understanding computers in general.

Reading the book, I've came to understand that there are atleast 2 clocks in the whole system. One is the System Clock which makes one of the lines within the Control Bus go HIGH and LOW periodically. The CPU also has it's own Internal Clock which controls the operations which are done by the CPU. Now the Internal Clock should be in sync with the System Clock for the whole system to make sense which means the control line (which oscillates between low and high) should be connected to the CPU so that both the clock combine and act like a single clock. But then this happened:

The above snippet is from the PDF version of the same book.

I still didn't get confused after reading this. I perfectly understood that the Internal Clock just runs twice as fast as the System Clock which is fine. My confusion came when the Author mentioned the words "On a 5 MHz 8088/8086 CPU the memory access time..." and "On a 50 MHz 80486, the memory access time...". The question is, 'How can CPUs have their clocks running at certain frequencies when their Clock depends on the System Clock?'. 'Shouldn't their Internal Clock run at a certain multiple of the System Clock?'. I've also came across overclocking the CPU and stuff. 'Won't that make the Internal Clock of the CPU go out of Sync with the System Clock?'

Perhaps the main problem in understanding how everything is synchronized in Computer is the understanding of the word 'synchronized'. And also, 'How many clocks are there in the Computer as a whole?'. Because "Zafaria Kansa" says on the following link on Quora that there are 'Internal' and 'External' Clocks on the CPU: https://www.quora.com/What-does-GHz-mean-How-does-it-relate-to-processor-speed (I don't have enough reputation to post more than two links). Does she mean 'System Clock' when she said 'External Clock'? How does everything fit together?

Modern processors tend to have more clocks than processors in the past, because that means when a part of the processor isn't used, it may be possible to switch off that part completely, including the clock, to save energy.

Clocks are often not synchronised, because synchronising and keeping them synchronised is expensive and complicated, and if you can make a part of the processor work correctly without synchronising its clock, that's overall cheaper.


shortest form $s$ to $t$ stopping at $u$ Suppose you want to go from vertex $s$ to vertex $t$ in an unweighted graph $(V, E)$, but you would like to stop by vextex $u$ if it is possible to do so without increasing the length of your path by more than a factor $\alpha$. Find an efficient algorithm that would determine an optimal $s-t$ path given your preference to stopping at $u$ along the way if doing so is not prohibited costly.

Here is my try :

First perform a BFS from $s$. When you get at $t$ you know what is the shortest past in $G$ from $s$ to $t$. We denote the size of this shortest path by $P$. Now we perform an other BFS from $s$, when we get at $u$ we know what is  the shortest path $M$ from $s$ to $u$. Once again we perform a BFS from $u$ and when we get at $t$ we know what is  the shortest path $K$ form $u$ to $t$.
If $\mid M \mid+\mid K \mid \leq \alpha P$ then the optimal path $(M,K)$ is a solution. So we are performing $3$ times a BFS in $G$, thus the overall complexity is $O(X + Y)$ where $X$ is the number of edges and $Y$ the number of vertex.

Is it possible to do better? Is what I said correct?

What you said is true.

Using your notations:

$P$ : path from $s$ to $t$

$M$ : path from $s$ to $u$

$K$ : path from $u$ to $t$

Notice that $P,M,K$ are all shortest paths from their respective sources to their targets.

Following the logic above:

$M \cup K$ is the shortest path from $s$ to $u$ to $t$

hence if $|M \cup K|$ is a good enough result for you - accept it. If it's not, i.e $|M \cup K| > \alpha|P|$, then essentially no shorter path exists from $s$ to $t$ using $u$.

(you can try proving $|M \cup K| \geq |P|$, may help your intuition!


A* without heuristic more efficient than Dijkstra I am using the module networkx to operate on graphs made from OpenStreetMap.
I wanted to compare the shortest path algorithm to find which one is faster, and I compared Dijkstra and A*.
The problem is : A* is most of the time faster than Dijkstra even though I didn't defined any heuristic function.
I understood that A* with $h=0$ was equivalent to Dijkstra, then why is it not the same time?

It depends how you implement Dijkstra.  The usual description of Dijkstra adds every vertex of the graph to the queue at the start, which is rather inefficient.  A* without a heuristic is often called "uniform cost search" (UCS) and the way it's described, you only add vertices to the queue when you discover them.

This means that, especially in sparse graphs (such as road maps, which are almost planar), UCS has a much lower memory footprint, which can make it considerably faster.  Also, the various operations on the queue are much faster, since the queue is typically much shorter.

There's more information in Ariel Felner's paper Dijkstra's algorithm versus uniform cost search or a case against Dijkstra's algorithm (Proceedings of 4th International Symposium on Combinatorial Search, SoCS-2011, AAAI, 2011).

By the way, straight-line distance is probably a very good heuristic for A* in your situation.


Data points as outcomes of a random experiment It is well known that

Random variable is a function from sample space of a random experiment to $\mathbb{R}$.

Consider the following sentences from deep learning book

  Let $\{x^{(1)}, \cdots , x^{(m)}\}$ be a set of $m$ independent and
  identically distributed data points. A point estimator or statistic is
  any function of the data: $$\hat{θ}_m = g(x(1), \cdots , x(m))$$.
  ...........................................................................................................................................................
  For now, we take the frequentist perspective on statistics. That is,
  we assume that the true parameter value $θ$ is ﬁxed but unknown, while
  the point estimate $\hat{θ}$ is a function of the data. Since the data
  is drawn from a random process, any function of the data is random.
  Therefore $\hat{θ}$ is a random variable.

Now my doubts are

1) Input to a random variable is an outcome of a random experiment. Then is it true that each data point is an outcome of a random experiment? If yes, then what may be that random experiment and who are running it?

2) If dataset is a subset of or itself a sample space, then what is the reason for many statements stating every dataset has an underlying probability distribution? instead of saying that each dataset is a subset of a sample space of a random experiment?

3) Output of a random variable is a real number. But in general parameter can be a vector of real number. How to understand it?

It is well known that

  Random variable is a function from sample space of a random experiment to ℝ.

Well-known, but false. Check out random variable on Wikipedia. We will not need the formal definition. Rather, a random variable is an object whose value is determined randomly. For example, consider a dice whose faces are labeled $a,b,c,d,e,f$. A dice throw is a random variable over $\{a,b,c,d,e,f\}$.

  1) Input to a random variable is an outcome of a random experiment. Then is it true that each data point is an outcome of a random experiment? If yes, then what may be that random experiment and who are running it?

I'm not sure what "input to a random variable is an outcome of a random experiment" means. In your case, here is what happens. You are interested in solving some learning problem, say digit recognition for concreteness. The process providing your samples goes like this:

choose a random person.
choose a random digit.
let the person draw that digit.
return the drawing as well as the digit.

As to who is running this experiment, it is the people who created the dataset.

  2) If dataset is a subset of or itself a sample space, then what is the reason for many statements stating every dataset has an underlying probability distribution? instead of saying that each dataset is a subset of a sample space of a random experiment?

The dataset is a bunch of samples drawn from the random experiment described above. It consists of $N$ pairs of drawings and digits.

  3) Output of a random variable is a real number. But in general parameter can be a vector of real number. How to understand it?

In this case the random variable ranges over pairs (drawing, digit).

There is a slightly different way of looking at the creation of a dataset. We are given a large dataset, which we randomly divide into training and test. The random experiment in this case corresponds to this random partition. But I think that it's more useful to think of both training and test to be coming from the same underlying random experiment, which corresponds to the process we are trying to learn.


Does an abstract syntax tree have to be a tree? Does the output of a parser have to be a tree or could it also be general graph?

Moreover, is there any existing language or a plausible one that uses general graphs representation instead of trees for their syntax?

The output of a parser need not be a tree. Indeed, when you consider things such as references from the USE of a variable to its DEFinition overlaid on the abstract syntax tree, you immediately have a graph.

The thing is that parsing generally is designed to take place in a single pass – this mattered for historical reasons, such as lack of space and processor speed, but also because it is simpler to reason about. Then subsequent phases decorate the parse tree with additional information.

There are such things as graph grammars, though I don't know whether they are used for parsing programming languages.


Forward must problem explanation in compiler design While studying, I came across the following statements:

A join point is a program point where two branches meet.

Available expressions is a forward, must problem.

Forward = Data Flow from in to out.

Must = At joint point, property must hold on all paths that are joined.

I get what joint point, available expression and forward is. But I am getting what exactly is meant by MUST.

Someone please explain what MUST is with example.

Edit: Could you please relate your statement with the following example.

I typically think of must as meaning logical and.

In the case of available expressions, when you reach a join point, the expression in question is available at the join point if and only if the expression is available on all of the input edges to the join point.  That is: if the expression is available on the first input edge, and it is available on the second input edge, and it is available on the third input edge, etc.

There are other properties, such as "could be a null pointer" which are may properties instead of must properties.  May I think of as meaning logical or.


Efficiently remove nodes from a connected graph Suppose you have a connected graph and want to remove k nodes such that the result is still connected.  How could you do this efficiently?

It occurs to me that you could find any spanning tree, say by a tree search of any kind.  Identify all leaves in the spanning tree, all of these can be removed without disconnecting the remaining vertices.  If you have more than k leaves then you're done, but in any tree you're only guaranteed 2 leaves.  So you may need to reiterate the process until you've removed k vertices.

That implies O(k) runs of a tree search. Does a more efficient algorithm exist? I don't think you can just look for articulation points or bridge edges because removing a single vertex may suddenly make other vertices which weren't articulation points now turn into articulation points.

Let $G$ be your graph. Compute any spanning tree $T$ of $G$. Perform a postorder visit of $T$, and keep track of the set $D$ of the first $k$ vertices visited ($T$ and $D$ can be computed by the same DFS visit).

The graph $G'$ obtained by deleting the vertices in $D$ from $G$ is still connected (and $T-D$ is a spanning tree of $G'$).
To prove this notice that if $v \in D$, then all descendants of $v$ in $T$ must belong to $D$ as well.


Redundant States During Removal of Null-Moves (Regular Expression to DFA) I've had this little doubt bothering me since four semesters now, so I've come here to resolve it. Theoretical CS was probably not the right place to ask.

Coming to the question, my old coursebook (Theory of Computer Science - Automata, Languages and Computation (Eastern Economy Edition) by KLP Mishra) details the conversion of the regular expression -:

$(0 + 1)^* (00 + 11)(0+1)^*$

to a finite automaton. The book details the process as follows:

I am able to grasp the process uptil step (d). I do not understand how (e) was obtained, and there is no explanation given. I tried to convert (d) to (e) by removing null-moves, but I am not able to get (e) - I obtain a bunch of redundant states (extra initial and final states).

It is not possible to use the DFA minimization procedure to obtain (e) after the null-moves are deleted, simply because this isn't a DFA yet - it's still an NFA. Note that I've not shown the NFA to DFA conversion procedure, which was on the next page. Could someone point me in the right direction?

There are no steps given to obtain (e) from (d). That's what's confusing - I know I have  to remove the null-moves but not how to get the neat and 'minimized' transition system given by (e).

[answer by UncleDolan originally embedded in the question post]

I believe I just solved the problem on trying it again. The strategy was to remove the nulls in the right sequence, not follow a random sequence of null-deletion. Following that, I had to remove unreachable and redundant states.

First, I state the algorithm used to remove null-moves as given in my coursebook.

For two vertices A and B with a null link from A to B,

Duplicate all the edges which are going outside from B, from A.
If A is an initial state, make B an initial state.
If B is a final state, make A a final state.
Remove the null link.

Now I'll go step-wise through the solution. I generated the images using Graphviz on Ubuntu.

First, I removed the null link between q5 and q1. q0-q5 and q2-q6 are risky at this time because I would be inadvertently duplicating the null links from q5-q1 and q6-qf.

Second, I removed the null link between q6 and qf. qf now becomes unreachable.

Third, I removed the null link between q2 and q6. q6 evidently becomes redundant.

Fourth, I removed the last null link between q0 and q5. q0 becomes redundant as we now have two initial states, both having (almost) the same moves.

I remove q0, q1 and qf for being either unreachable or redundant. The end result looks very close to (e) in the question.

I find that q2 could do q6's job without making any changes to the language. q6 is redundant as well. This is the final result.


Are "method" and "function" synonyms? Would saying "Call the printf function" be the same as "Call the printf method"?

These are a different level classifications:
A method is a function (or procedure) associated with object – a concept from Object Oriented Programming.

A function is the logical unit (a piece of reusable code called by name) independent of any objects (those might not even exist in particular language). So the method is a function, but a function exists also in non-OO languages, so the reverse is not true.


Prove hash family is 3-wise independent Let $q$ be a prime number and let $\mathbb{Z}_q = \left\{1,\dots,q-1\right\}$; I need to prove that the family $\mathcal{H} = \left\{h_s \colon \mathbb{Z}_q \rightarrow \mathbb{Z}_q\right\}_{s \in \mathbb{Z}_q^3}$ is 3-wise independent, where $h_s$ is defined as:

$$h_s(x):=h_{s_0,s_1,s_2}(x):=s_0 + s_1 x + s_2 x^2 \bmod q$$

How could I do it? My intuition would be proving that it is 1-wise independent and use the property $$x_1,\dots,x_t \in \mathcal{X}, \quad y_1,\dots,y_t \in \mathcal{Y}, \quad \Pr[h_s(x_1)=y_1 \wedge \dots\wedge h_s(x_t)=y_t \mid s \leftarrow _\$ \mathcal{S}]=\frac{1}{|\mathcal{Y}|^t},$$ but I'm not sure how to do that.

Let's assume that $\mathbb{Z}_q$ is the field of size $q$. In order for your family to be 3-wise independent, we need the following condition to hold: for every $x_1,x_2,x_3,y_1,y_2,y_3 \in \mathbb{Z}_q$ where the $x_i$ are all different,
$$
\Pr_s[h_s(x_1) = y_1 \land h_s(x_2) = y_2 \land h_s(x_3) = y_3] = \frac{1}{q^3}.
$$
Since your family consists of $q^3$ functions, this is the same as the following property:

  If $x_1,x_2,x_3 \in \mathbb{Z}_q$ are all different, then for every $y_1,y_2,y_3 \in \mathbb{Z}_q$ there exist unique $s_0,s_1,s_2 \in \mathbb{Z}_q$ such that
  $$ s_0 + s_1 x_i + s_2 x_i^2 = y_i, \quad i \in \{1,2,3\}. $$

This is a property that you can prove using linear algebra.


How to answer the following queries on a tree? Given a tree of "N" nodes(each node has been assigned a value A[i],node-"1" is the root of the tree), and a constant "K" , we have Q queries of the following type : [w]
(which means find the lowest valued node in the sub-tree of [w] , only considering those nodes in the sub-tree of [w] which have a depth less than equal to K) .
Example :
Value of nodes of tree :
A[1] = 10
A[2] = 20
A[3] = 30
A[4] = 40
A[5] = 50
A[6] = 60
Edges of tree : [1-2],
[2-3],
[3-4],
[4-5],
[4-6].
K=2.
Query-1 : [w]=1 . All nodes in subtree of [w] : (1,2,3,4,5,6) , now, all nodes in sub-tree of [w] having depth less than equal to K : (1,2) . Hence , minimum(A[1],A[2])=min(10,20)=10 is the answer .
Query-2 : [w]=4 . All nodes in subtree of [w] : (4,5,6) , now, all nodes in sub-tree of [w] having depth less than equal to K : (4,5,6). Hence , minimum(A[4],A[5],A[6]) = min(40,50,60)=40 is the answer .

Without any precomputation, a depth-limited version of depth-first search would be a natural approach to this problem: then it's like finding the minimum of an array, you could find the minimum weight during the search. But a time-efficient way (if you have multiple queries for different nodes and $K$) is to indeed precompute the answer for all the nodes: a linear algorithm seems achievable, starting from the bottom level up to the root, level by level. You have to store for each node an array $a$ such as $a(K)$ gives the desired value. And if you modify the value of a node later, I think a backpropagation scheme could be also considered.


How strong "Consistent Guessing Problem" is? I saw "Rosser’s Theorem via Turing machines" at:

https://www.scottaaronson.com/blog/?p=710

The modified halting problem (Consistent Guessing Problem) CGP is used in the proof:

CGP(M) - accepts if M accepts on a blank tape
CGP(M) - rejects if M rejects on a blank tape
CGP(M) - either accepting or rejecting if M runs forever on a blank tape

It's shown in the proof TM which solves CGP doesn't exist.
Consider I have CGP as oraculum. Does it allow me to solve halting problem?

Andy Drucker, in a comment (with follow-up) to Scott Aaronson's blog post, shows that

  HALT does not reduce to Consistent Guessing (CG).

Here is his proof (copied verbatim), which uses diagonalization:

  We’ll build a language $L$ that’s a solution (i.e., refinement) of CG. On stage $i$ we’ll try to set finitely many bits of $L$ so as to ensure that the $i$th machine $M_i$ doesn’t solve HALT when given oracle access to $L$.

  If this works, then we’re done! So assume for contradiction’s sake that we get stuck on some stage $i$. We’re going to use this premise to solve HALT — without an oracle. This absurdity will prove the result.

  So — say we’re stuck at stage $i$, and we have some finite setting $L[i]$ to some of the bits of $L$, consistent with CG.

  Let $L^*$ be $L[i]$ augmented with all of the bits ‘forced’ by CG: i.e., $L^*(M) = 0$ whenever $M$ halts with output $0$, and similarly for $1$. So, $L^*(M)$ still is undefined for all but finitely many of the machines $M$ that run forever.

  Now, for each input $M$ to $M_i$, by our assumption we have that

  $$ M_i^{L’}(M) = HALT(M) $$

  whenever $L’$ is an extension of $L^*$. An application of König’s lemma tells us that for each $M$ there is a number $n = n(M)$ such that any extension of $L^*$ with arbitrary values up through input lengths $n$, causes $M_i(M)$ to output $HALT(M)$.

  So, here’s how we can determine the value $HALT(M)$: we dovetail simulations of all Turing machines. On stage $j$ we simulate the first $j$ machines for $j$ steps each. Whenever a machine halts with output ($0$ or $1$), we extend our finite approximation of $L^*$. (This approximation begins with the finitely many values of $L[i]$, hard-coded into the algorithm). Let $L^*[j]$ be the finite approximation to $L^*$ on the $j$th stage.

  On the second part of stage $j$, we simulate $M_i(M)$ on all extensions of $L^*[j]$ up to length $j$. That is, we take the values we have so far, and we try extending them in all possible ways.
  We then simulate $M_i(M)$ on all of these extensions as oracle, for $j$ steps each. If on all such simulations, the machine halts with some output $b$, without ever trying to access an undefined oracle bit, then we output “$HALT(M) = b$”.

  The claim is, this always halts with the right answer. Using our earlier analysis with König’s lemma (and the fact that $L^*[j]$ converges to $L^*$), we find that for large enough $j$, we will output the correct bit, if we reach stage $j$.

  So we just need to argue that we never output a wrong bit earlier. But this is easy: at every stage $j$, at least one of our simulations is an initial segment of a correct simulation of $M_i(M)$ on a valid CG oracle. Thus that simulation always either halts with the correct output, or doesn’t halt, or tries to access an undefined oracle bit. So we never get a unanimous incorrect vote.


Can the encodings set of a non-trivial class of languages which contains the empty set be recursively enumerable? Let $C$ be a non-trivial set of recursively enumerable languages ($\emptyset \subsetneq C \subsetneq \mathrm{RE}$) and let $L$ be the set of encodings of Turing machines that recognize some language in $C$: $$L=\{\langle M \rangle \mid L(M) \in C \}$$

Suppose that $\langle M_{loopy}\rangle \in L$, where $M_{loopy}$ is a TM that never halts.
I wonder if  it is possible that $L \in \mathrm{RE}$?

By Rice's theorem I know that $L \notin \mathrm{R}$ (the set of recursive languages), so either $L \notin \mathrm{RE}$ or $\overline{L} \notin \mathrm{RE}$. Does it have to be the first option since $M_{loopy} \in L$?

to complete Raphael's answer, there is an extension of Rice's theorem that says the following:

  Generalized Rice's Theorem

  Let $S \subseteq RE$ be some property, and let $L_S$ be all the TMs that satisfy the property $S$, that is,
  $$L_S = \{ \langle M \rangle \mid L(M) \in S \}.$$
  Then, $L_S \in RE$ if and only if all the following conditions hold:

  for any $L_1,L_2 \in RE$, if $L_1 \in S$ and $L_1 \subseteq L_2$ then $L_2 \in S$.
  if $L_1\in S$ then there exists a finite $L_2 \subseteq L_1$ such that $L_2 \in S$.
  The language of 'all finite languages in $S$' is in RE.  (in other words, there exists a TM $M_S$ that, if $L$ is a finite language $L=\{w_1, w_2, \ldots w_k)$, and $(w_1, w_2, \ldots, w_k)$ is given to $M_S$ as an input, $M$ accepts only if $L\in S$.

Now back to the original question. We now that $\langle M_{loopy}\rangle\in L$ so $L(\langle M_{loopy}\rangle)\in C$. But $L(\langle M_{loopy}\rangle)=\emptyset$ since this TM never halts. This means that $\emptyset \in C$.

Now lets look on the first condition of the above theorem. ANY language $L$ satisfies $\emptyset \subseteq L$. Thus in order to satisfy condition 1, it must be that $C=RE$. However, the question states that $C\subsetneq RE$ and therefore, by the theorem, $L\notin RE$.


How to show that any computable function is bounded above by Busy Beaver Function? Despite the endless hours of googling, pretty much all of them used an alternative definition of Busy Beaver function. The definition BB(k) I'm interested in is the maximum number of 1's that can be written by k-state before it halts, but the other definition they used was the maximum number of steps, and they're not equivalent.

And one of the techniques they used is by reduction from halting problem, that if there was any computable function f(x) bounding above the function BB(k), you can solve halting problem in a finite amount of time using the alternative definition, but this argument doesn't work for the definition of BB(k) I am interested in. How do we show that BB(k) is asymptotically larger than any computable function f(x)?

I think a sketch of the proof could be as follows.

First prove BB(k) is uncomputable. Assume it is computable, then it means there is some machine with some number of states m that can compute this value. Show that there exist a larger machine with some number of states M that calls this function on BB(M) and outputs BB(M)+1 1s, and then halts. Therefore there is a contradiction since it outputed more 1s than predicted by BB(M). It's easy to see M = m + C for some constant.

Now regarding the growth.

Assume G(k+1) >= BB(k+1) - BB(k) is computable for k >= K0.

Now, if the above is true then there must exist a machine with m states that computes G(k).

And there must also exist a machine, with a larger number of states M, that guesses BB(K0) and then computes UBB(M) = sum(K0..M)G(k) + BB(k0) and output UBB(M)+1 1s.

So this machine outputs more 1s than our assumed computable upper bound.

Therefore G(k) can not be computed for any K0.


Application of Expander Codes I need to give a talk about expander codes at university (I'm a student of computer science). Since they have been introduced to show a family of codes looking good when thinking of the Shannon theorem, I wonder what real world application for expander codes exist.

As far as I know one has a real hard time when encoding but decoding is quite fast. Why aren't they used to encode write only media or similar? What is their big disadvantage?

One area that you could consider is Fault Tolerant Parallel Computation. Expander codes and graphs could be efficiently used in them like:

Highly fault-tolerant parallel computation, by Daniel A. Spielman

On word-level parallelism in fault-tolerant computing


Guessing Number Game I was solving this question. It is as follows

  Joe picks an integer from the list $1,2,\cdots,N$ with a probability $p_i$ of picking $i$ for all $1\leq i \leq N$. He then gives Jason $K$ attempts to guess his number. On each guess, Joe will tell Jason if his number is higher or lower than Jason's guess. If Jason guesses Joe's number correctly on any of the $K$ guesses, the game terminates and Jason wins. Jason loses otherwise. If Jason knows all $p_i's$ and plays optimally, what is the probability he wins?
  $1\leq N\leq 200000$
  $1\leq K\leq 20$

I tried this problem by dynamic programming. Let $DP[i][j][k]$ stores the winning probability such that the number is between $i$ and $j$ inclusive and only $k$ chances are left. So
$$DP[i][j][k] = \max_{i\leq l\leq j} \{p_l + DP[i][l-1][k-1] + DP[l+1][j][k-1]\}\\DP[i][j][1] = \max_{i\leq l\leq j}p_l\ \quad \quad \text{Base Case}$$
But since the range of $N$ is very high this solution is not feasible. So while I was seeking an $\mathcal{O}(n)$ solution I came across the following solution(on the internet which got accepted)

Sort($p[]$)
$\sum_{i=0}^{\min(n,2^k-1)}p_i$

If we run both the solution on input $N=5,K=2, p=[0.2, 0.3, 0.4, 0.1, 0.0]$ we get the same answer. So, my question is how is the above algorithm working and can we get to the same conclusion starting form my dp formulation{if it is correct}.

The reason why the sorting solution works is that if you are given $K$ guesses, then with any deterministic strategy you can only guess at most $2^K - 1$ values. This can be proved by induction, first noting the base case $K = 1$ and then for $K + 1$, note that after you guess the first value then you have $K$ guesses left and you guess either on the left or right of your original guess depending on the outcome of the original guess, so by induction that gives $2(2^K - 1)$ values you can guess after the first, so if you add the original guess then you get $2^{K+1} - 1$.

Furthermore, if any of these $2^K - 1$ values is the correct value, it will be guessed and you will win. None of the other $N - 2^K + 1$ values will ever be guessed. So the probability that you win is the sum of the probabilities for the $2^K - 1$ values your deterministic strategy can guess. Obviously the optimal solution is to take the top $2^K - 1$ probabilities.


What is an example of a (simple) tail recursive algorithm that doesn't use a helper function? I know one can compute things using tail recursion with helper functions like:

let sum_helper n accumulator =
match n with
| 0 -> accumulator
| _ -> sum_helper (n-1) (accumulator+n-1);;

let sum_tail n = sum_helper n accumulator 0;;

sum_tail 3;;

which gives:

# sum_tail 3;;
- : int = 3

but I wanted an example of something that didn't use a helper function (idk if the above can be made without a helper function).

Ideally something simple so to understand the concept better since I'm trapped into thinking all tail recursions look like that.

There's an example staring at you in the face: write a function that takes two arguments a and b and returns the sum of the integers from 0 to a, plus b.

Here's another example: write a function that returns the last element of a list, or a special value if the list is empty.

let rec last l =
  match l with
  | [] -> None
  | [x] -> Some x
  | h::t -> last t

Here's another example, in an imperative language: apply a function to all the elements of a list, in order, without returning a value.

let rec iter f l =
  match l with
  | [] -> ()
  | h::t -> f h; iter f t

So you can see that tail-recursive don't have to take an extra argument. However, taking an extra argument is a common pattern, and there is a deep reason for that.

A common reason to write a recursive function is to traverse a recursive data structure. For example, the list data structure is defined recursively: a list is either the empty list (“nil”), or a pair (“cons”) consisting of an element (“head”) and a list (“tail”). In Ocaml syntax:

type list_of_foo = Foo_nil | Foo_cons foo * list_of_foo;; (* Foo_cons (head, tail) *)

To act on a list, you need to specify what to do on the empty list, and what to do on a non-empty list. To traverse the whole list with a function, you make a recursive call to process the tail in the case of a non-empty list. A generic list traversal is called a fold. Writing a recursive function is one way to write a fold; another way is to call a generic fold function and tell it what to do with nil and what to do with a cons (as a function of the head and the result of processing the tail of the list).

This generalizes to all recursive data structures. A particularity of lists is that there's never more than one sub-list, so the call to process the tail can be a tail call. Contrast with a binary tree, for example:

type btree = Leaf of int | Node of btree * btree

To process a btree, when you reach a Node, you need to process both the first subtree (left child) and the second subtree (right child). They can't both be tail calls. But with lists, the one recursive call can be a tail call.

Integers don't look much like a data structure. But in fact recursion on an integer is typically based on the structure of integers. For example, when you recurse by enumerating integers from 0 to n or from n to 0 (or 1 to n, etc.), you're using the structure provided by the Peano axioms: an integer is either 0 or the successor of an integer.

So you have a recursive function which takes a data structure as an argument. It makes a recursive call, calling itself on a sub-structure of the original data. What does it return? If the recursive call is a tail call, what it returns has to be the value returned in a case where the function doesn't make a recursive call. Often, that's the “starting” case, e.g. 0 for a function that recurses on an integer or the empty list for a function that recurses on a list. What can you return in the starting case? If you return a constant, that's not very interesting. If you want to return something that depends on information collected from the data structure, you need to pass this information through the tail calls. And that's where the extra argument comes from. A tail-recursive function needs an extra argument (in addition to the data structure that it recurses over) to collect data read from the data structure.

In the starting case, you often do want to return a constant. Hence you write a pair of functions: a tail-recursive functions with two arguments (the data structure to traverse and the accumulator), which returns the accumulator when it reaches the end of the data; and an auxiliary function just to give an initial value to the accumulator. This corresponds to the initial value argument for fold functions.


can a machine generate truly random numbers? I know that for most programs pseudo-random numbers are sufficient, but there are ways that machines can generate truly random numbers! There are devices that generate unpredictable processes. However, they tend to be biased somehow. So, is it possible to make devices that can generate unpredictable processes and also unbiased (truly random)? (Please note that I am not asking whether true randomness can be achieved by composing PRNG)

What is true randomness, and is it necessary? Algorithms cannot distinguish truly random bits from pseudorandom bits (by definition!), and so in practice we are only interested in generating strongly pseudorandom bits. As indicated above, true randomness ensures that even if we run the same algorithm twice, we get different results.
True randomness is required only in highly classified cryptographic applications, such as one-time pads, used for strategic communication. Although pseudorandom bits are still enough, now the bar is a lot higher, due to the importance of the data being encoded. Nevertheless, by crunching more pseudorandom and truly random (but biased and correlated) bits together, we can create highly secure one-time pads.
High-quality randomness is generated by combining physical noise and "bit crushers"; stated differently, by injecting "true" randomness into a pseudorandom number generator.
The idea is to start with a high-quality pseudorandom generator, and stick a "pipe" of low-quality true noise into it. The low-quality true noise is truly random, but not iid: it could be highly biased, there could be significant correlations, and so on. By combining it with a good "bit cruncher", the resulting stream of random bits combines the advantages of both sources: it is more unpredictable than the already highly unpredictable pseudorandom generator, and it does not suffer from the bias and correlations of the actual physical source of noise.
Is this "true randomness"? No. But computers won't be able to distinguish the difference. This is already true for high-quality pseudorandom generators, so what did we gain? Two things. First, we may think that the pseudorandom generator is strong, but perhaps it's weak; by injecting true randomness, we strengthen it. Second, even a high-quality stream of pseudorandom bits can be predicted if you know the initial seed. For this reason, when reproducibility is not required, pseudorandom generators are initialized with a seed produced from actual (although low-quality) physical randomness.
The pseudorandom generator used in Unix systems employs this methodology. It keeps an "entropy pool" — a source of true, low-quality randomness — and mixes it into a pseudorandom generator. In practice, it works quite well, although it's not completely bullet-proof. Using a dedicated physical random noise generator would result in a much enhanced stream of random bits which should be difficult to attack.


Approximately counting the number of marked elements in a list of n numbers Assume that we have n sealed boxes. There are k boxes with a ball inside. The goal is to approximate k  by an additive error epsilon, using the minimum number of box probing. I know that this is possible using O(n/k. 1/epsilon^2) box probing but I don't know the algorithm and its analysis.

You calculate the average number of balls in a box (k / n), and the variance. From this you calculate the estimated number of balls and the variance when probing m random boxes. Convert variance to standard deviation. The number of balls will be normal distributed, and there is a simple formula for diverging by more than k standard deviations.


How to prove greedy algorithm for number partitioning? the partition problem (or number partitioning1) is the task of
  deciding whether a given multiset S of positive integers can be
  partitioned into two subsets S1 and S2 such that the sum of the
  numbers in S1 equals the sum of the numbers in S2.

There is a greedy algorithm for this problem:

  One approach to the problem, imitating the way children choose teams
  for a game, is the greedy algorithm, which iterates through the
  numbers in descending order, assigning each of them to whichever
  subset has the smaller sum. This approach has a running time of O(n
  log n). This heuristic works well in practice when the numbers in the
  set are of about the same size as its cardinality or less, but it is
  not guaranteed to produce the best possible partition. For example,
  given the set S = {4, 5, 6, 7, 8} as input, this greedy algorithm
  would partition S into subsets {4, 5, 8} and {6, 7}; however, S has an
  exactly balanced partition into subsets {7, 8} and {4, 5, 6}.

But, I don't know how to prove "This heuristic works well in practice when the numbers in the set are of about the same size as its cardinality or less". Can anyone help?

There is nothing to prove about the statement you highlight. It is an empirical statement.

In order to have something to prove, you will need to formulate this claim formally in some way or another. There are many options, including average-case analysis, smoothed analysis, and restricted instances (which is what the statement points at). Until you have done so, it is impossible to prove or refute the statement.

The example given in your source shows that, in fact, the heuristic doesn't always succeed. Perhaps it gives a good approximation in some circumstances. The statement, unfortunately, doesn't hint at a provable claim which has any chance of being true.


Any option other recursive search possible to go from one 2d point to another point with fixed set of possible moves? Problem:  Given (a,b) and (c,d), find if you can you reach from (a,b) to (c,d) if we can only have the following moves
(a, b) to either (a+b,b) or to (a,a+b).

Example (1,4) to (5,9) is possible because:  (1,4) -> (5,4) -> (5,9)

Solution:  I can think of is recursive search

Set 1: TestedPoints, initially empty
Set 2: PointsToTest, initially (a,b)

While (PointsToTest not empty):
   Remove nextPoint (x,y),
   Compare (x+y,y) with (c,d):
          If x+y=c and y=d, return TRUE
          Else if x+y < c and y < d, add (x+y,y) to PointsTotest if it is not present in TestedPoints set

   Compare (x,x+y) with (c,d):
          If x=c and x+y=d, return TRUE
          Else if x < c and x+y < d, add (x,x+y) to PointsTotest if it is not present in TestedPoints set

Is there anything faster?

if we can express the progressive X,y points in an expression, I thunk we can do faster.  For e.g: Get a as close to c as possible and b as close to d as possible using equations and then do recursive search over smaller interval.

There is a simple method that is often faster: If you have $n$ moves to go from $A$ to $B$, determine the set of all points that you can reach from $A$ in $\lfloor \frac{n}{2} \rfloor$ moves, and the set of all points from which $B$ can be reached in  $\lceil \frac{n}{2} \rceil$ moves, and then find if there are points in the intersection of these sets.


Where is the OS when a process is running? We know that operating system is responsible for handling memory allocation, process management etc. CPU can perform only one task at a time(assuming it to be single core). Suppose an operating system has allocated a CPU cycle to some user initiated process and CPU is executing that. Now where is operating system running? If some other process is using the CPU, then, is operating system not running for that moment? as OS itself must need CPU to run. If in case OS is not running, then who is handling process management, device management etc for that period?

This question was previously asked on Stack Overflow by vish. I answered it, and so did Martin James, and our answers feel partly contradictory.

The question is mixing up who's in control of the memory and who's in control of the CPU. The wording “running” is imprecise: on a single CPU, a single task is running at any given time in the sense that the processor is executing its instructions; but many tasks are executing in the sense that their state is stored in memory and their execution can resume at any time.

While a process is executing on the CPU, the kernel is not executing. Its state is saved in memory. The execution of the kernel can resume:

if the process code makes a jump into kernel code — this is called a system call.
if an interrupt occurs.

If the operating system provides preemptive multitasking, it will schedule an interrupt to happen after an interval of time (called a time slice). On a non-preemptive operating system, the process will run forever if it doesn't yield the CPU. See How do modern operating systems like linux handle multitasking? for an explanation of how preemption works.

Tasks such as process management and device management are triggered by some event. If the event is a request by the process, the request will take the form of a system call, which executes kernel code. If the event is triggered from hardware, it will take the form of an interrupt, which executes kernel code.

(Note: in this answer, I use “CPU” and “processor” synonymously, to mean a single execution thread: a single core, or whatever the hardware architecture is.)


A hash function with predicted collisions As far as I know, the more collision-resistant a hash function is, the better. But is there any way to define a hash function with predicted collisions? In other words, a hash function that collides for some known set of possible inputs and avoids collisions for other input values. To state the problem simpler:

Let $A$ be some set of strings.
Define a function $f$ such that $f(x_i) \rightarrow y_i$ with $y_i \neq y_j$ for all $i,j \notin A$ with $i \neq j$, and otherwise $f(x_i) \rightarrow y$ where $y \notin \{y_i \mid i \notin A\}$ is constant.

Is it possible? In addition, is it possible for performance of such a hash function not to depend on the size of $A$?

Generally the collisions in a hash function are, in a way, what winds up improving the running time.

This is because running time (or size, or insertion time) is generally defined in terms of worst-case input.  If you use an algorithm without any randomness or hash, you need to deal with the worst case.  For example, finding duplicate elements in an array has an $\Omega(n\log n)$ in the comparison model, same as sorting.  But if you just hash the values, you can determine whether or not there's a duplicate in $O(n)$ time and space with a small probability of error.    Determining a hash function that wouldn't collide, eliminating the possibility of error, has to take $\Omega(n\log n)$ time.  (You may notice that these are, in a way, the same problem--though of course hashed values generally belong to a smaller universe and the comparison model may not be appropriate).

That said, there are some ways to take advantage of the ways hash functions collide.  One is locally sensitive hash functions, in which elements with small differences (i.e. normal distance functions for points) hash to the same value.  Recently I've been reading this paper(1), which I found really easy to read, and shows some good, intuitive applications for how a locally sensitive hash function can be used to solve seemingly difficult problems--in this case the nearest neighbor problem with small probability of error.

Incidentally, the space advantage of possible collisions is how bloom filters work, a data structure that allows you to store elements of a set, each in space smaller than their actual size.  They are a constant factor away from optimal, and the upper and lower bounds demonstrate the tradeoff between error and space.

(1) Neylon, T.  A locally sensitive hash for real vectors.  SODA2010.


Is there a "sorting" algorithm which returns a random permutation when using a coin-flip comparator? Inspired by this question in which the asker wants to know if the running time changes when the comparator used in a standard search algorithm is replaced by a fair coin-flip, and also Microsoft's prominent failure to write a uniform permutation generator, my question is thus:

Is there a comparison based sorting algorithm which will, depending on our implementation of the comparator:

return the elements in sorted order when using a true comparator (that is, the comparison does what we expect in a standard sorting algorithm)
return a uniformly random permutation of the elements when the comparator is replaced by a fair coin flip (that is, return x < y = true with probability 1/2, regardless of the value of x and y)

The code for the sorting algorithm must be the same. It is only the code inside the comparison "black box" which is allowed to change.

No, this is impossible unless $n \leq 2$. The probability that a permutation is generated by your algorithm using a random comparator is dyadic, i.e. of the form $A/2^B$, whereas the probability should be $1/n!$. When $n > 2$, there is no way to write $1/n!$ in the form $A/2^B$.


How to prove Shortest Common Superstring is NP-Hard After some research and many youtube videos I have learnt that to prove a problem is NP-Hard; you would need to reduce that problem to known NP-Hard problems such as Subset Sum Problem, Halting Problem, Satisfiability Problem or Traveling Salesman Problem. Now my problem is Shortest Common Superstring

Input: A finite set R = {r1, r2, ..., rm} of binary strings (sequences of 0 and 1); positive
integer k.
Question: Is there a binary string w of length at most k such that every string in R
is a substring of w, i.e. for each r in R, w can be decomposed as w = w0rw1 where w0,
w1 are (possibly empty) binary strings?

In this link it states that the problem is NP-Hard(https://www.geeksforgeeks.org/shortest-superstring-problem/), besides I am using the greedy algorithm stated there to solve the problem.

So I need help with choosing which NP-Hard Algorithm to reduce to and a way to reduce it. I do not expect a full solution(even though it would be welcome), just guidance would be enough. I honestly do not have much clue on how to go about it.

This article may help you.

Theorem 1 states that Hamilton path problem can be reduced to SCS even if all strings have fixed length $H \ge 3$.

For your case with strings of any length but fixed alphabet, this is also true, but the proof is more technical.


Algorithm for minimizing the number of "inversions" in a graph Given the following graph:

With the assumptions below:

A node on the left is linked to several nodes on the right
Nodes on the right are paired together: one is black, one is white
Each pair of nodes on the right can be swapped (black becomes white and white becomes black)
A node on the left is green if linked to only white or only black; red if linked to two colors.

The idea is to minimize the amount of red nodes, by flipping some black and white nodes. What is the best algorithm to do that?

(I think this problem has something to do with some sort of cycle detection? This problem is probably well-known on some equivalent form.)

Of course it will be often impossible to make all nodes green; here node V can never be (it is linked to B0 and B1). Some cycles also make all green impossible.

Extra question — same as above, but with a weight associated to each edge. Minimize the sum (for each node) of absolutes delta between white and black (difference between the sums of weights for white and black for each left node).

Where does this problem comes from?

A transit network is composed of stops, routes and trips.

Each trip belongs to one route
Each trip has one natural direction (0 or 1, inbound/outbound)
Each trip goes through a list of stops.
The direction of all trips within a route is arbitrary; so it is possible to invert the direction of all trips of a given route (but all trips together).

If all trips passing through a stop do have the same direction (all 0 or all 1) we can compute a "natural" direction for the stop. Otherwise we cannot. The idea is to flip route trips direction to minimize the number of stops where we cannot compute this "natural" direction.

Here the nodes on the left are stops, pair of nodes on the right routes, with black/white all trips for each route direction.

You can reduce MAX-2-SAT to your problem. Therefore, your problem is NP-complete.

In MAX-2-SAT we have $n$ boolean variables $x_1, \dots, x_n$ and $m$ clauses of the form $a\vee b$ where $a$ and $b$ are $x_i$ or $\bar{x_i}$ (its complement). The goal is to assign $0$, and $1$ values to $x_i$'s such that the number of true clauses is maximized. This problem is NP-complete. For an arbitrary instance of MAX-2-SAT, we build an instance of your problems as follows. Hence, your problem is also NP-complete, i.e., kind of no chance for a polynomial-time algorithm for all cases.

We put $n+m$ pair of nodes ($x_i$ and $\bar{x_i}$ for $1\leq i\leq n$, and $y_k$ and $\bar{y_k}$ for $1\leq k\leq m$) on the right side and $3m$ node on the left (three nodes $v_{k,1}, v_{k,2}, v_{k,3}$ for $k$'th clause where $1\leq k\leq m$).
Let $(x_i\vee x_j)$ be the $k$'th clause in our instance (other cases are similar). We put three nodes $v_{k,1}, v_{k,2}, v_{k,3}$ in the left side of our graph. We then connect

$v_{k,1}$ to $x_i$ and $x_j$,
$v_{k,2}$ to $x_i$, $\bar{x_j}$, and $y_k$,
$v_{k,3}$ to $\bar{x_i}$, $x_j$, and $y_k$.

At most one of the $v_{k,1}, v_{k,2}, v_{k,3}$ can gets a green color. Moreover, this happens if and only if the clause gets a true value. Therefore, the maximum number of green nodes in the instance of your problem is equal to the solution to MAX-2-SAT.

Your bonus problem is harder than the original version and is also NP-complete.