Grover's algorithm on probabilistic classical machines As a starting point for this question, I came across this question, which AIUI is citing a construction showing how to simulate quantum circuits with a $PP$ algorithm, i.e. implying quantum computation in general is in $PP$.

However,  it struck me as counterintuitive to say that the only way to implement a specific example of QC, like Grover's algorithm, would be to do so by emulating a quantum computer and running it in there. I then tried to imagine what implementing it more naturally might look like, e.g. operations in terms of list items directly rather than transforming them into a quantum state vector.

For background, I understand that non-$BPP$ algorithms in $PP$ are allowed to be arbitararily close to random, and so we potentially need to repeat them exponentially many times to arrive at any particular confidence in their answer. I'm specifically interested in what a single iteration (that then needs to be repeated exponentially many times) of a Grover-like algorithm looks like. I presume, from the fact that the translation in the linked thread is 1-1, that this single iteration would be expected to take $O(\sqrt n)$ time, but please let me know if this inference is incorrect.

(I'm also presuming that this Grover-like algorithm is not in $BPP$, because otherwise search theory would be very different. It being outside $BPP$ means we're talking about a search algorithm that in practice takes $O(2^\sqrt n)$ time, which isn't going to revolutionize anything.)

Also, since $PP$ is generally defined in terms of binary decision problems and Grover's algoritm is not one, I had to extrapolate slightly about what the success criteria looks like in a $PP$ rather than $BQP$ context. The criteria I tentatively came up with is that the algorithm should be create and pick from a probability distribution over the $N$ items of a list, with the property that the most likely item to be selected is the (a, if more than one) item marked by the oracle function, i.e. it has the pluarity, but not necessarily majority, of probability mass.

That has the obvious caveats that because the list in general contains more than two items, it is not more likely than not that that item gets selected, only that no single item is more likely. The difference in probability between the most and second-most likely items being chosen is also allowed to be arbitararily small. An algorithm that returns the marked item from a list of $N$ with probability $\frac{1}{N}+2^{-N}$ would be allowed so long as all other items were less likely.

Is there any existing work on algorithms that achieve the corresponding outcome as Grover's (or similar specific quantum algorithms), but in more direct/natural terms?

Let $F$ be a function that maps integers from $0 \dots N-1$ to $\{0, 1\}$. We want to find $x$ (which is promised to be unique) such that:

$$F(x) = 1$$

Now let's take two random integers $a$ and $b$ from $0 \dots N-1$ and output:

$b$, if $F(a) = 0$
$a$, if $F(a) = 1$

For any fixed $x$ and $y$ we have:

$$P_{a=x} = P_{b=x} = P_{a=y} = P_{b=y} = \frac{1}{N}\\
P_{a \ne x} = P_{b \ne x} = P_{a \ne y} = P_{b \ne y} = \frac{N-1}{N}$$

Knowing that $a$ and $b$ are independent random variables, the probability that we output $x$ is

$$P_{a = x \lor a \ne x \land b = x} =
P_{a = x} + P_{a \ne x} P_{b = x} =
\frac{1}{N} + \frac{N - 1}{N^2}$$

and the probability that we output some other value $y \ne x$ is

$$P_{a \ne x \land b = y} = P_{a \ne x} P_{b = y} =
\frac{N - 1}{N^2} < \frac{1}{N}$$


Number of substrings possible with even characters Consider a string 'ABBAA'
Possible substrings with even number of characters are $4$
'ABBA' : Count of 'A' is even and 'B' is even
'AA' : Count of 'A' is even and 'B' is even - ($0$)
Similarly 'BB' and 'BBAA' substrings.
So a total of $4$ substrings are possible.
If given string is 'AABCCBBCAA'
substrings possible are "AA" "BB" "AA" "CC" "BCCB" "CCBB" "CBBC" "CBBCAA" "AABCCB"
So total $9$ substrings are possible
Is there any pattern or sequence or algorithm to find this?

Assuming that your alphabet has constant size, you can solve your problem in linear time in the length of the input string.
Let  $\Sigma = \{a_1, a_2, \dots, a_m\}$ be your alphabet and $s = s_1 s_2 \dots s_n$ be your input string.
For $i=0, \dots, n$, and $j=1,\dots,m$ let $n_j(i)$ be $0$ iff the number of occurrences of $a_j$ in $s_1 \dots s_i$ is even and $1$ otherwise.
Let $\eta(i) \in \{0,1\}^{m}$ be the vector $(\eta_1(i), \dots, \eta_m(i))$.
Consider any substring $s_{hk} = s_{h+1},s_{h+2}, \dots, s_k$ of $s$, where $0 \le h < k \le n$.
The number of occurrences of each $a_j$ in $s_{hk}$ is even if and only if $\eta(k)-\eta(h) = (0, \dots, 0)$, where the difference is taken modulo $2$, i.e., iff $\eta(k)=\eta(h)$.
Then your problem is equivalent to counting the number of unordered pairs of distinct indices $\{h,k\}$ for which $\eta(h)=\eta(k)$.
This can be done as follows: given $x \in \{0,1\}^{m}$ let $\alpha(x)$ be the number of times of $x$ appears in $\eta(0), \dots, \eta(n)$, so that the number of unordered pairs $\{h,k\}$ for which $\eta(h) = \eta(k) = x$ is $\binom{\alpha(x)}{2} = \frac{\alpha(x) (\alpha(x)-1)}{2}$.
To find the find the overall number of substrings of interest it suffices
to sum the above quantity over all choices of $x \in \{0,1\}^m$:
$$
\sum_{x \in \{0,1\}^m} \binom{\alpha(x)}{2} = \frac{1}{2} \sum_{x \in \{0,1\}^m} \alpha(x) (\alpha(x)-1).
$$
Since $m=O(1)$, all values of $\eta(i)$, for $i=0, \dots, n$ can be computed in $O(nm) = O(n)$ time. Moreover, all values of $\alpha(x)$ for $x \in \{0,1\}^m$ can also be found in $O(n m \log \min\{n, 2^m\}) = O(n)$ time by scanning $\eta(0), \dots, \eta(n)$ once and maintaining a counter for each $x$ (these counters can be stored in a dictionary with at most $\min\{n,2^m\}$ elements).
Finally, the final sum can be computed using $O(\min\{n, 2^m\}) = O(1)$ arithmetic operations (as it only needs to extend to $x \in \{0,1\}$ for which $\alpha(x) > 0$).

An example implementation due to @orlp of the above in Python using a binary integer as the vector $x$ and storing all $a(x)$ in a hashmap counter is as follows:
def num_even_substrings(s):
    a = {0: 1}
    x = 0
    for c in s:
        x ^= 1 << ord(c)
        a[x] = a.get(x, 0) + 1
    return sum(ax*(ax-1)//2 for ax in a.values())


Pros and cons of representing strings as lists of characters I am writing a compiler for my programming language (both almost complete), but they are stuck in the, I would call, "String vs List-of-Char dilemma".
Maybe some more experienced compiler programmer could help.

It is a functional, strongly typed (with inference) and almost pure (immutable vars) language.
As I could perceive, using a list of chars is better for simplicity/generality of the language. But it adds complexity to the runtime/stdlib, because the user may require sometimes to print a List-of-Char as a text and sometimes as a list.

Perhaps a built-in function just to print a List-of-Char as text would be a good compromise? I may be missing something here.

In the other hand, defining a "String" type different from "List", requires duplicity of all list functions like "head", "tail", "replace" etc. to preserve the soundness and simplicity of the type system. It also requires duplicity from the user when implementing similar methods.

Perhaps a built-in function just to convert a List-of-Char to String and vice-versa would be a good compromise? I may also be missing something here.

obs.: The code is in github if anyone has interest into delving in the problem.

I'd say that the main reason for having a separate String representation is performance. For example, Haskell defines a string to be a list of characters type String = [Char]. But in many applications it turns out that this is too slow - you have one constructor for every character, which requires a lot of work from the garbage collector. Then of course you have to duplicate most of the string functions, but the benefit is that you can implement them natively to be very fast.

So I'd suggest: If you are concerned about performance, define a native string type. If not, use list of characters instead.


Insert-only Levenshtein distance I am wondering if a constrained insert-only form of Levenshtein distance has been implemented before by someone? In my particular use case, all other operations should not count as they are not possible. Only parts of the strings can be stripped off. As an example, if our library has "Hello" and "complex".

These strings can be stripped and we might only see "Hel" or "llo" or "com" etc. I want to explore, if what we see is part of a sequence in our library.

Thanks for any suggestions.

Your problem appears to be:

Given strings $S,T$, determines whether $S$ appears as a subsequence of $T$.

There are several ways you could approach this.

One way is to use dynamic programming and apply a straightforward modification to computing the Levenshtein edit distance, where you set the cost of an insertion to be 1 and the cost of a deletion or replacement to be $\infty$.

Another solution to use a string-matching algorithm.  Build the regexp $.\star S_1 .\star S_2 . \star \cdots . \star S_n . \star$ and check whether $T$ matches this regexp, using any standard method (e.g., convert the regexp to a NFA or DFA).  For instance, if $S$ is the string HOT and $T$ is the string HELLO THERE, then you will check whether HELLO THERE matches the regexp .*H.*O.*T.*.  I suspect this might be faster, but the best way to find out is to try it and see.


How to find a regular expression I know how to find a regular expression when given a FA. But how do I find a regular expression given just a language and its rules?

For example, for the language $L \subset \{ a,b\}^* $ which accepts all words that contain exactly one $aa$. How do I find a regular expression in this case?

I know that I would be able to FA and convert it into a regular expression, but this can be time-consuming. Is there a faster/easier way that I could use in an exam to save time?

I'm not aware of any general methods, and personally I'm not interested in tricks which are only useful in exams. However, I can explain how to find an expression for your particular example. The way to get better with this kind of exercise is to solve a few of them.

A word which contains exactly one $aa$ has the form $xaay$, where $x,y$ contain no $aa$, $x$ doesn't end with $a$, and $y$ doesn't start with $a$. This suggests first determining how to write a regular expression for the set of words avoiding $aa$.

If a word avoids $aa$, then any two occurrences of $a$ are separated by $b^+$.  We can describe all such words by the following infinite regular expression: $$b^* + b^*ab^* + b^*ab^+ab^* + b^*ab^+ab^+ab^* + \cdots.$$
This can be represented by the finite regular expression $b^* + b^*(ab^+)^*ab^*$.

For the sake of our original problem, we need to impose the further constraint that the word not end with $a$. We obtain the following infinite regular expression for the set of all words avoiding $aa$ and not ending with $a$:
$$
b^* + b^*ab^+ + b^*ab^+ab^+ + \cdots = b^*(ab^+)^*.
$$
Similarly, a regular expression for the set of all words avoiding $aa$ and not starting with $a$ is $(b^+a)^*b^*$.

Putting everything together, a regular expression for the set of all words containing exactly one copy of $aa$ is
$$
b^*(ab^+)^*aa(b^+a)^*b^*.
$$


solving Recurrence relation f T(n)=T(n/2)+log log(n) T(n)=T(n/2)+log log(n)--------1
T(n)=T(n/4)+log log(n/2)+log log(n)-------------2
T(n)=T(n/8)+log log(n/4)+log log(n/2)+log log(n)-----------3
T(n)=T(n/2k)+log log(n/k)+....+log log(n/2)+log log(n)
T(n)=1+log log(n/k)+....+log log(n/2)+log log(n)
 n/2k=1 => n=2k
 T(n)=1+log log(2K/k)+....+log log(n/2)+log log(n)
 T(n)=1+log log(2)+....+log log(n/2)+log log(n)
 T(n)=1+log (log(2)*....*log(n/2)*log(n))

I ARRIVED AT THIS POINT BUT I DIDN'T KNOW HOW TO CONTENU ANY HELP PLEASE

Let's consider $n=2^k$:
$$\begin{array}{l}T(n)=T\left(\frac{n}{2}\right)+\log\log n = T\left(\frac{n}{2^2}\right)+\log\log \frac{n}{2}+\log\log n = \\
=T\left(\frac{n}{2^3}\right)+\log\log \frac{n}{2^2}+\log\log \frac{n}{2}+\log\log n=\\
=\cdots=\\
=T\left(\frac{n}{2^k}\right)+\log\log\frac{n}{2^{k-1}}+ \log\log\frac{n}{2^{k-2}}+\cdots+\log\log n=\quad(3)\\
=T(1)+\log\log 2 + \log\log 2^2 + \cdots + \log\log 2^k=\\
=T(1)+\log\left[ \log2\cdot \log2^2 \cdots  \log2^k \right] =\\
= T(1)+\log\left[ k!\log^k2 \right]=\\
=T(1) + \log k! +k \log\log 2 \in \Theta(k \log k)\end{array}$$
where $k=\log_2 n$.


Dijkstra function for navigation for disadvantaged Is there a way we can write a function for Dijkstra to determine which node to enqueue and which to discard. This is for a navigation solution for people with disabilities where path to stairs may be shorter but not preferable to wheelchair bound individuals. The navigation solution should also support all individuals and only give a path discarding stairs if the specified user group is someone who is wheelchair bound etc. So basically i am attempting to write a function that checks if user group = wheelchair bound then removes the shortest path to stairs and gives the path to the nearest elevator.
I am pretty new to this so any assistance would be very much appreciated. My apologies for being unclear previously.

Dijkstra's algorithm already solves your problem. If a staircase is unusable for the wheelchair-bound, then the corresponding edge should not appear in the graph. If some other route is usable but very slow, then it should be weighted accordingly.

The same kind of problem is already encountered with cars – some paths are too narrow for them. A smart GIS takes this into account, removing the corresponding edges when you navigate your car, and keeping them when you navigate your walk.

The difficult aspect here is obtaining this information – which path is suitable for the wheelchair-bound, and which ones should get penalties. Whether it can be done automatically (with a few mistakes) depends on your situation, which you haven't described in enough detail.


Number of induced paths in an interval graph Let $G$ be an interval graph. For any two vertices $u,v$ in $G$, how many induced paths are between them in $G$? Is it polynomial in terms of the number of vertices in $G$?

Consider the following example:

Say the total number of intervals is $n$. To get from one red extremity to the other, you can take a path which alternates between green and blue intervals. Each of those paths is induced, and there are $2^\frac{n-2}{2}$ such paths. Thus, the number of induced paths between two vertices in an interval graph is not necessarily polynomial in the number of vertices.


What are some efficient ways to find the differences between two large corpuses of text that have similar, but differently ordered content? I have two large files containing paragraphs of English text:

The first text is about 200 pages long and has about 10 paragraphs per page (each paragraph is 5 sentences long).
The second text contains almost precisely the same paragraphs and text as the first. It is also 200 pages long with 10 paragraphs per page. However, the paragraphs are randomized and in a different order when compared to the first text. Also, a large percentage of the paragraphs have small changes in wording compared to similar paragraphs. For example, a paragraph in the first text might have a sentence like Like Jimmy, I wanted to go to the palace while the corresponding sentence in the paragraph of the second text would read Like Jimmy, I really wanted to go to the castle.

I want to be able to capture the changes here like the addition of really and the deletion of palace with replacement of castle. If the paragraphs were roughly aligned, then this would be pretty trivial as there are plenty of ways to diff text. However, since the paragraphs aren't aligned, that isn't the case.

If the files were small (handful of paragraphs), Levenshtein Distance probably would work fine, but because the files are huge, it would be inefficient to compare each paragraph of text 1 to each paragraph of text 2 to find out which paragraphs match.

What would be some other approaches to this problem to handle it efficiently?

Comparing 2000 paragraphs to 2000 paragraphs is only four million comparisons.

The key to the problem is not to use a function that computes the Levenshtein distance but to use one that computes the Levenshtein distance if the distance is less than a certain threshold, and fails (or, rather, returns +∞) if the distance is greater than the threshold.

This is because you are only interested in closely similar paragraphs. You have no interest at all in the precise distance between paragraphs that are different enough to be unrelated. So as soon as a distance has got high enough to be uninteresting, the function can exit at once; and this will mostly happen very early on indeed during the execution of the function.

The higher the threshold, the longer the running time but the smaller the proportion of false negatives.

If you know something more about the documents (such as that each paragraph matches at most one paragraph in the other document) then you could make one pass with a low threshold, exclude the matched paragraphs from further consideration, make one pass over your now reduced corpus with a higher threshold, exclude those reduced paragraphs, and so on.

Implementation detail: Presumably you would be calculating a Levenshtein distance on words rather than on characters. If that is the case, you should first assign a number to each word - for example, by sorting the entire corpus, calling the first word '1', the second word '2', and so on. That way your paragraph comparisons would be done by comparing numbers rather than words, which is faster.


What is the difference between rateless and online encoding? Definitions of Rateless encoding and Online encoding are as follows.

Error-correcting codes that employ no fixed block length are called rateless or fountain codes.

Online encoding refers to the property that a symbol is encoded at once and without knowledge of previous encodings.

Do both properties indicate the same thing? Are Fountain codes both rateless and online?

They are not the same thing. The difference is when you know the message to encode.

In fountain codes, you know the message at the onset. The code allows you to keep generating more and more redundancy. The message, however, is fixed.

In online codes you do not know the entire message at the beginning, but you learn it as time goes by. Each time you learn an additional part of the message you can encode this part in a coherent way to the encodings of the (prefix of the) message you have already obtained or sent.


consider a base 16 adder how to modify the adder so that it can perform a base 8 addition? Consider a base 16 adder. How can I modify the adder so that it can perform a base 8 addition?

I expect this question will appear in my exam tomorrow; if anyone can give me a hint or a solution, I'd be grateful. I've tried searching the net and my textbook to get some insight, but nothing is clicking.

my textbook digital design 5th morris mano

Assumptions/Statements:
A base 16 adder: an adder that adds two 4-bit binary numbers I1 and I2 and outputs the 4-bit result R and a carry bit C

To use as a base 8 adder (as above) discard the Most Significant Bit from both I1 and I2 (i.e. ground/zero them). Now your inputs are base-8. From the output discard the Carry bit C it will always be zero. Your new Carry bit will be the Most Significant Bit from result R. Your new result will be the 3 least significant bits from R.

Please check Assumptions/Statements are in accordance to your book!


Looking for algorithm to iterate over matrix I have such a product example:

{
  "color": ["red", "blue"],
  "material": ["metal", "textile", "plastic"],
  "options": ["handle", "wire", "bt"],
  "textile": ["silk", "cotton"]
}

I need to know what algorithm can help me to produce all options possible for such product, f.e.:

{
  "color": "red",
  "material": "metal",
  "options": "handle",
  "textile": "cotton"
}

Each option can be single for a product.

Obviously, I don't want to use tons of for loops.
It should be possible to easily add new options and new variations, f.e.:

{
  "color": ["red", "blue", "new"],
  "material": ["metal", "textile", "plastic", "new"],
  "options": ["handle", "wire", "bt", "new"],
  "textile": ["silk", "cotton", "new"],
  "newOption": ["new option]
}

The classical recursive algorithm to calculate the Cartesian product $A_1 \times \cdots \times A_n$ goes as follows:

If $n = 0$, return the empty tuple.
Otherwise, for every $x_1 \in A_1$ and $(x_2,\ldots,x_n) \in A_2 \times \cdots \times A_n$, output $(x_1,x_2,\ldots,x_n)$.

In the second step, you compute $A_2 \times \cdots \times A_n$ recursively.

You can convert this into an iterative algorithm. Suppose that $|A_i| = m_i$, and that the individual elements are $a_{ij}$. We count from $0$ to $m_1 \cdots m_n - 1$, and interpret each of these numbers as a mixed base number, involving the bases $m_1,\ldots,m_n$. We then convert the number into a tuple.

An alternative presentation of the iterative approach uses $n$ counters $c_1,\ldots,c_n$ counting from $0$ to $m_i-1$; when a counter reaches $m_i$, we reset it and all following counters to zero, and update the tuple accordingly.

Details of all these approaches left to you.


How can I explain to my parents that I study programming languages? I am currently finishing my MSc in computer science. I am interested in programming languages, especially in type systems. I got interested in research in this field and next semester I will start a PhD on the subject.

Now here is the real question: how can I explain what I (want to) do to people with no previous knowledge in either computer science or related fields?

The title comes from the facts that I am not even able to explain what I do to my parents, friends and so on. Yeah, I can say "the whole point is to help software developers to write better software", but I do not think it is really useful: they are not aware of "programming", they have not clue of what it means. It feels like I am saying I am an auto mechanic to someone from the Middle Ages: they simply do not know what I am talking about, let alone how to improve it.

Does anyone have good analogies with real-world? Enlightening examples causing "a-ha" moments? Should I actually show a short and simple snippet of code to 60+ year-old with no computer science (nor academic) experience? If so, which language should I use? Did anyone here face similar issues?

If you have a few minutes, most people know how to add and multiply two three-digit numbers on paper. Ask them to do that, (or to admit that they could, if they had to) and ask them to acknowledge that they do this task methodically: if this number is greater than 9, then add a carry, and so forth. This description they just gave of what to do that is an example of an algorithm.

This is how I teach people the word algorithm, and in my experience this has been the best example. Then you can explain that one may imagine there are more complex tasks that computers must do, and that therefore there is a need for an unambiguous language to feed a computer these algorithms. So there has been a proliferation of programming languages because people express their thoughts differently, and you're researching ways to design these languages so that it is harder to make mistakes.

This is a very recognizable situation. Most people have no concept that the computers they use run programs, or that those programs are human-written source code, or that a computer could 'read' source code, or that computation, which they associate with arithmetic, is the only thing computers do (and data movement, and networking, maybe).

My research is in quantum computing, so when people ask me what I do, I don't attempt to explain that. Instead, I try to explain that quantum physics exists (they've usually heard of Schrödinger's cat, and things that are in two places at once), and that because of this strange physics, faster computation might be possible.

My goal is to leave the person feeling a little more knowledeable than they did going in, feeling excited about a world they didn't know existed, but with which you have now familiarized them. I find that that's much more valuable than explaining my particular research questions.


Reduce the following problem to SAT Here is the problem. Given $k, n, T_1, \ldots, T_m$, where each $T_i \subseteq \{1, \ldots, n\}$. Is there a subset $S \subseteq \{1, \ldots, n\}$ with size at most $k$ such that $S \cap T_i \neq \emptyset$ for all $i$? I am trying to reduce this problem to SAT. My idea of a solution would be to have a variable $x_i$ for each of 1 to $n$. For each $T_i$, create a clause $(x_{i_1} \vee \cdots \vee x_{i_k})$ if $T_i = \{i_1, \ldots, i_k\}$. Then and all these clauses together. But this clearly isn't a complete solution as it does not represent the constraint that $S$ must have at most $k$ elements. I know that I must create more variables, but I'm simply not sure how. So I have two questions:

Is my idea of solution on the right track?
How should the new variables be created so that they can be used to represent the cardinality $k$ constraint?

It looks like you are trying to compute a hypergraph transversal of size $k$. That is, $\{T_1,\dots,T_m\}$ is your hypergraph, and $S$ is your transversal. A standard translation is to express the clauses as you have, and then translate the length restriction into a cardinality constraint.

So use your existing encoding, i.e., $\bigwedge_{1 \le j \le m} \bigvee_{i \in T_j} x_i$ and then add clauses encoding $\sum_{1 \le i \le n} x_i \le k$.

$\sum_{1 \le i \le n} x_i \le k$ is a cardinality constraint. There are various different cardinality constraint translations into SAT.

The simplest but rather large cardinality constraint translation is just $\bigwedge_{X \subseteq \{1,\dots,n\}, |X| = k+1} \bigvee_{i \in X} \neg x_i$. In this way each disjunction represents the constraint $\neg \bigwedge_{i \in X} x_i$ - for all subsets $X$ of $\{1,\dots,n\}$ of size k+1. That is, we ensure that there is no way that more than k variables can be set. Note that this is not polynomial size in $k$

Some links to papers on more space-efficient cardinality constraint translations which are polynomial size in $k$:

Translating Pseudo-Boolean Constraints into SAT - Niklas Eén and Niklas Sörensson, JSAT vol 2 (2006), pg 1-26 (a good survey).
Efficient CNF encoding of Boolean cardinality constraints - Olivier Bailleux and Yacine Boufkhad, Proceedings of Principles and Practice of Constraint Programming 2003, LNCS vol 2833, pg 108-122 (a nice, fairly easy to implement translation).
Towards an Optimal CNF Encoding of Boolean Cardinality Constraints - Carsten Sinz - Proceedings of Principles and Practice of Constraint Programming 2005, LNCS 3709, pg 827-831.
Towards Robust CNF Encodings of Cardinality Constraints - Joao Marques-Silva and Inês Lynce, Proceedings of Principles and Practice of Constraint Programming 2007, LNCS 4741, pg 483-497.

If you are actually interested in solving such problems, perhaps it is better to formulate them as pseudo-boolean problems (see wiki article on pseudo-boolean problems) and use pseudo-boolean solvers (see pseudo-boolean competition). That way the cardinality constraints are just pseudo-boolean constraints and are part of the language - hopefully the pseudo-boolean solver then handles them directly and therefore more efficiently.


Look Ahead buffer vs Translation Look aside buffer I know that Translation look aside buffer is used for address translation in  paging to achieve better performance.

I came across term called Look Ahead buffer in a document which said it implements Temporal locality.

I tried searching for Look Ahead buffer's but could not get any significant data.

Please help

I do not know the exact definitions of TLBs and look-ahead buffers, but here is what I understand about them.

TLBs help make translations from virtual to physical addresses quicker via caching. So, you can see how the TLB is implementing temporal locality (any kind of caching is implementing temporal locality) in some sense.

Look ahead buffers on the other hand come into play when while bringing data from disk to memory. Pages that are explicitly requested may be brought into the disk buffer along with other pages (often selected based on spatial locality to the requested page -- but there are other heuristics that the disk can use). The idea is to not have to go to disk too often. Instead the disk will try to predict what pages will be required in the RAM in the future (hence the term "look-ahead").

Note: I have heard people call the TLB the look-aside buffer and the look-ahead buffer. To me it seems like "translation look-aside buffer" is the correct expansion (because I dont see where any "looking ahead" is happening).


Minimize the total execution time of jobs executed by 3 processors in sequence There are 3 processors: $P_1$, $P_2$, $P_3$. $P_1$ can execute only one job while the other two can execute any number of jobs in parallel.

Each job consists of 3 parts, and each part is processed by their respective processor (eg. part 1 by $P_1$). Furthermore part 2 can be executed only after $P_1$ finishes executing part 1, and part 3 can be executed only after $P_2$ finishes executing part 2.

Suppose there are $n$ jobs, and again each job has 3 parts. The processor $P_k$ takes time $T_{i\,k}$ to complete part $k$ of job $i$.
Can anyone suggest an algorithm that takes set of $n$ jobs and determines the the jobs should be processed  so that the total time is minimized?

This is a homework problem and I don't know where ti start

Well since no one else is giving an answer, here goes:

Assume the jobs are represented as $J=\{x_1,\ldots,x_n\}$

Since $P_1$ must process only one job at a time, it doesn't matter which order the jobs are processed, the time taken by $P_1$ is always the same, $\sum_{i=1}^n t_{i,1}$, each job's 3 parts are represented as $(t_{i,1},t_{i,2},t_{i,3})$. So to minimize the total time, we only need to consider the order that affects $P_2$ and $P_3$. Since both of them can execute any number of jobs in parallel, to minimize their time we want the jobs that need longer time to be processed first. So you arrange the jobs in decreasing order of $t_{i,2}+t_{i,3}$. Now to prove that this is optimal.

We need to show that in any optimal solution to the problem, if the ordering of the jobs is not the same as the ordering described above, we can convert it to our ordering without increasing the total time.

Let $C$ be an optimal ordering. Assume $C$ does not have the same ordering as that given by the algorithm. Which means, there exists jobs $x_i$ and $x_j$ such that $t_{i,2}+t_{i,3}<t_{j,2}+t_{j,3}$ and $x_i$ is listed immediately before $x_j$ in $C$, call such a pair of jobs an inversion. Consider the ordering $C'$ obtained from $C$ by swapping the position of $x_i$ and $x_j$. Thus $x_j$ would appear finish earlier here.

We can see that in $C'$, $P_2$ starts on job $x_i$ exactly when $P_2$ starts on job $x_j$ in $C$. This is independent of how long the first parts of $x_i$ and $x_j$ require. Since $t_{i,2}+t_{i,3}<t_{j,2}+t_{j,3}$, it's clear that in $C'$ job $x_i$ finishes sooner than job $x_j$ in $C$. So the total time taken by $C'$ is no larger than the time taken by $C$.

Repeat the above till all inversions are removed from $C$ and we have an ordering which is the same as that of the algorithm. Thus, the ordering returned by the algorithm is optimal.

Running Time: It's clear that the running time is $O(n\log n)$, I don't think I need to elaborate on that.

Hope this helps! Cheers!


Adding words to DFA, maintaining minimality How can we add new words to DFA, maintaining minimality?

Maybe, you can advise some completely different approach to solve the following problem:

  A program must process two types of queries:

  Add new word to the language.
  Check if some word of the language occurs in the input string as a substring.

  Time and space complexity should be as low as possible.

The only solution that I know so far is to rebuild an automaton from scratch every time, using Aho-Corasick algorithm, but, you know, it's really-really inefficient.

I've performed some search on Internet and found some papers like "Incremental Construction of Minimal Acyclic Finite-State Automata", but, unfortunately, algorithm described there produces and maintains just a minimal trie (not a complete FSM with suffix links, like an automaton produced by Aho-Corasick algo).

For number 2, I think you would just check if the DFA ever enters an accept state, instead of just checking if it ends in an accept state.  So just run the algorithm as normal, but halt and accept as soon as the automation transitions to an accept state, instead of waiting until the end of the input.  (The number of times the automation enters an accept state is the number of substrings of the language contained in the input string)

Not sure about number 1 though.  I am not sure what operations (if any) minimal DFAs are closed under, but I think the number of operations required by a slightly modified version of Hopcraft's algorithm would be proportional to the size of a word you add via union.


Easiest way to find y in $x \text{ xor } y = z$ with given $x \text{ and } z$ Let's say we have given two numbers $x, z$, and we need to find another number $y$ such that $x \text{ xor } y = z$. The xor ( exclusive or ) is bitwise operation: xor table
.

I know that this can be solved if we analyze both $x \text{ and } y$ bit by bit, starting from the first, but I was wondering if it can be solved by some easier way with bitwise operations.

One can observe that, for any boolean values $a,b,c$, we have
$a=b$ if and only if
$a \text{ xor } c = b \text{ xor } c$.

(To prove that we note that $\Rightarrow$ is trivial, and $\Leftarrow$ follows by xor-ing with $c$ once more and applying the cancellation law.)

Hence, the equation
$x \text{ xor } y = z$
is equivalent to
$(x \text{ xor } y) \text{ xor } x = z \text{ xor } x$
which in turn (by the cancellation law), simplifies to
$y = z \text{ xor } x$.

If we wanted to be more pedantic we could explicitly point out those steps where we also implicitly used associativity, commutativity, and the identity law.


Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$? In my analysis of algorithms class we were given the following recurrence relation:
\begin{eqnarray}
T(n) &=&
\begin{cases}
    T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is even number}& \\
    2T\left(\displaystyle\frac{n-1}{2}\right),　&n \ \mbox{is odd number}&
\end{cases} \nonumber \\
T(1) &=& 1
\end{eqnarray}
I have proved by iteration (expand) that when $n = 2^k$ (always the even case), $T(n) = O(\log{n})$; when $n = 2^{k+1}-1$ (always the odd case), $T(n) = \Omega(n)$.
Is this actually possible? After looking at some other posts, I am thinking this is possibly because the $\Omega(n)$ obtained here is the lower bound runtime of the worst case scenario, and the $O(\log{n})$ is the upper bound runtime of the best case?
Am I confusing something? Or is there any other conclusion can be drawn from the result that $T(n) = O(\log{n})$ and $T(n) = \Omega(n)$ for the recurrence?

You calculated “Big-Theta for n = power of two - 1”. That’s not a useful thing. Try calculating T(n) for n = (4^k - 1) / 3 and be surprised. (Write n down in binary first). Or n = 3 * (8^k - 1) / 7 where T(n) ≈ n^(2/3).
You found the values for a good case and for a bad case. You’ll have to prove they are lower and upper bound.


Clone an Undirected Graph I was reading an article on Clone an Undirected Graph, It says I have do do bfs and have to keep track of visited/cloned nodes.

I have another approach- I will initialize an empty adjacency list and then traverse the original adjacency list and copy it. Its time complexity is O(V+E) and I don't have to keep track of anything.

Is there anything wrong with this approach?

Assume that you are only given a source vertex and not given the whole adjacency list, then this method won't work.


What does "Every CFL is decidable" exactly mean? I am trying to prove the fact that every CFL is decidable, however I can't come to terms with what the statement exactly means.

I know that generation of a particular string by a given CFG is a decidable problem. This means that we can design a TM that will definitely halt and tell us whether the given string is generated by a CFG.

But coming to this problem, what does it mean? I am making the interpretation that this means - The problem of determining whether a given arbitrary language is a CFL is decidable.

Am I right or does it mean something else?

The phrase

  Every context-free language is decidable

has the following meaning:

  If the language $L$ is context-free, then $L$ is decidable

or in other words

  If $L$ is a context-free language then $L$ is a decidable language


Understanding lemma found in proof of quotient construction for DFAs Lemma 13.6    $p \in F \Longleftrightarrow [p] \in F'$
Proof. The direction $\Rightarrow$ is immediate from the definition of $F'$. For the direction $\Leftarrow$, we need to show that if $p \approx q$ and $p \in F$, then $q \in F$. In other words, every $\approx$-equivalence class is either a subset of $F$ or disjoint from $F$. This follows immediately by taking $x = \epsilon$ in the definition of $p \approx q$. $\quad\square$

The excerpt above found in Dexter C. Kozen's Automata and Computability.  This lemma is found in a proof of the Quotient Construction for DFA.
I do not understand how the author concludes that if one wants to show $[p] \in F' \implies p \in F$ (1), then it is equivalent to showing that $p≈q$ and $p \in F \implies q \in F$ (2). Can someone please provide as detailed as possible an explanation of why if we want to show (1) it is equivalent to show (2)? Any idea on why the author does not feel the need to justify this?

Let us start with explaining the notation:

$F$ is the set of accepting states of some DFA.
We define an equivalence relation $\approx$ on the states of the DFA as follows: $p \approx q$ if for all words $x$, $\hat\delta(p,x) \in F$ iff $\hat\delta(q,x)$, where $\hat\delta$ is the transition function of the DFA (extended from symbols to words).
We denote the equivalence class of a state $p$ by $[p]$.
$F' = \{ [p] : p \in F \}$.

Now suppose that $[p] \in F'$. According to the definition of $F'$, $[p] = [q]$ for some $q \in F$. Standard properties of equivalence relations imply that $[p] = [q]$ iff $p \approx q$. By definition of $\approx$, $\hat\delta(p,x) \in F$ iff $\hat\delta(q,x) \in F$ for all words $x$. Taking $x = \epsilon$, we see that $p = \hat\delta(p,\epsilon) \in F$ iff $q = \hat\delta(q,\epsilon) \in F$. Since $q \in F$, this shows that indeed $p \in F$.


Bounded waiting and starvation free in critical section problem i have 4  question regarding relation between starvation and bounded waiting.

1.Does starvation-freedom imply deadlock-freedom?

My Answer-:

From here,

definition of starvation free is

  Freedom from Starvation -:Every thread that attempts to acquire the lock eventually succeeds

  Freedom from Deadlock -:f some thread attempts to acquire the lock, then some thread (not necessarily the thread referred to in the if statement; emphasis added) will succeed in acquiring the lock.

so i can state that starvation-freedom imply deadlock-freedom

2.Does starvation-freedom imply bounded-waiting?

Approach-:

  Starvation free implies  that every thread that will attempt to acquire lock will succeed.

on the other hand

  bounded wait insures that  there exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections
  after a process has made request to enter its critical section and before that request is granted

which implies that there must not be any starvation.

Am i correct? but the explanation is  here confuses me.

Please help me out !!

Thanks!!!

No, starvation-free doesn't imply bounded waiting.

For instance, consider a procedure that never even attempts to acquire any lock; but the amount of time it takes is variable and can be arbitrarily long.  Then there is no bound on the amount of time it might take to complete its operation.

Here is another example of how it can fail.  Starvation-free means that every attempt to acquire the lock eventually succeeds -- but that says nothing about how long it might take.  Maybe the amount of time it will take to acquire the lock is variable and can be arbitrarily long -- there is no upper bound on how long it takes to acquire the lock.  Then a procedure that first attempts to acquire the lock before doing anything else won't satisfy bounded waiting.


Why is Heapsort in O(n log n) if not all n operations take time log n? let's consider that we already have constructed heap array.

so from this, when we do heap sort, the number of elements that have to be sorted decreased. I mean heap decrease.(which also means heap tree level decreases -> downheap operation level decreases

but nlogn means each n nodes has logn operation. But not all nodes do logn(original down heap operation level) operation because of heap tree level decrease.

$n \log n$ means each $n$ nodes has $\log n$ operation.

No, it does not. That's like saying:

  \$100 means I sold 100 drinks for \$1 each

Obviously, you could have sold any number of things as long as they add up to \$100.

With algorithm costs it's the same. A sequence of operations taking "time" $\Theta(n \log n)$ means that the "time" costs of all the operations add up to something that behaves roughly like $n \log n$.

Once Landau terms enter the pickture, things get muddled. It's tempting to tread $\sum_{i=1}^n O(\log i)$ in the same way as $\sum_{i=1}^n \log i$, but the former sum doesn't really make sense. I recommend you read our reference questions on algorithm analysis and asymptotics to see how one can arrive at the final result here.


How do I calculate MDS codes? We are given $n, m$ with $n - m > 1$. Let $S$ be the set of all $n$-bit words. Form $2^{n-m}$ disjoint subsets of $S$ of size $2^m$, denote a typical one of them by $A$, and let $B = S \setminus A$. With $H(a,b)$ denoting the Hamming distance of elements $a \in A$ and $b \in B$, let $G(a) = \max_{b \in B} H(a,b)$ and $F(A) = \min_{a \in A} G(a)$. How could one construct the $A$s such that the $F(A)$ values are as small as possible?

It seems you are looking after (linear) MDS codes. A linear $[n,k,d]$-MDS code  "partitions" the space into $2^k$ balls of size $2^n/2^k$ elements each, so that the minimal distance between any two codewords is at least $d=n-k+1$. This is the maximal possible distance by the singleton bound.

Now, Let $C$ be such a code, and consider its cosets, that is, given any word $w\in \{0,1\}^n$ look at the affine subspace $w+C = \{ w+u \mid u\in C\}$. It is not difficult to see that any such coset is also an MDS code (namely, it partitions the entire space into balls of the same size, with the same distance guarantees; however it are no longer a linear space, but an affine one).

To answer your question, given any $\alpha\in \{0,1\}^n$ and any coset $\beta = w+C$, $\alpha$ is within distance $\lceil d/2\rceil$ from one word in $w+C$ (the center of the appropriate ball where $\alpha$ lies). Due to the singleton bound, such a distance is optimal.


Linear Grammar in less than cubic time I have a linear grammar $G$ and a string $s$.  $G$ is is not limited to right or left linear only but rather has a mix of rules of both types.
Is there an algorithm to determine whether $s \in L(G)$ in less than cubic time?
Converting to CNF and applying the CKY algorithm takes cubic time, and I am wondering if there is a more efficient algorithm.

Yes, you can.  As Dmitry explains, CYK parsing can be used to parse a linear grammar in $O(n^2)$ time, where $n$ is the length of the input word.
CYK parsing is a dynamic programming algorithm that  sets $P[l,s,R]$ to be true if $a_{s .. s+l-1}$ can be generated from the non-terminal $R$, where $a_{1..n}$ is the input word.
Note that there is a recurrence relation that can be used to compute $P[l,s,R]$ from values of the form $P[l',s',R']$ with $l'<l$, in $O(1)$ time.  In particular, if we have the rule $R \to b_1\cdots b_k Q c_1 \cdots c_m$, then we should set $P[l,s,R]$ to true if $a_{s .. s+k} = b_{1 .. k}$ and $P[l-k-m,s+k,Q]$ is true and $a_{s+l-m .. s+l-1} = c_{1 .. m}$.  Do this for each rule with $R$ on the left-hand side.  If none of them sets $P[l,s,R]$ to true, set $P[l,s,R]$ to false.  This takes $O(1)$ time (treating the size of the grammar as a constant).
We repeat this for each of the entries $P[l,s,R]$.  There are $O(n^2)$ such entries (treating the size of the grammar as a constant), and each entry takes $O(1)$ time to compute, so the entire algorithm runs in $O(n^2)$ time.


clarification in tf-idf formula According to the wiki-article, http://en.wikipedia.org/wiki/Tf%E2%80%93idf the term frequency of term $t$ in document $d$ is given as follows:
$$
tf(t,d) = 0.5 + \frac{0.5 \times f(t,d)}{\max{\{f(w,d): w~\epsilon~d\}}}
$$

This is the augmented way of computation. But what does $w$ stand for?

A document is modeled as a set $d$ of words.  Since we're maximizing $f(w,d)$ over all $w\in d$, this means that $w$ ranges over all possible words contained in $d$.

In the future, please check a textbook before asking.  We expect you to do some research on your own before asking, and this is a standard topic that's well-covered in standard explanations of tf-idf.


Best time complexity of sorting numbers in range [1...n log n] given an array $A$ of $n$ numbers in range $1$ to $n\log n$, what is the time complexity of the best method to sort them?

The answer is $O(n)$ but I don't understand this. of course counting sort itself is irrelevant, perhaps radix sort with base changing is the way to go, but I'm not sure of to change the base of $n\log n$.

Note in the RAM model, indirection always takes constant time regardless of how large the address is, so each process of radix sort with base $b$ takes $O(n+b)$ time. As a result, the radix sort takes $O((n+b)\log_b(n\log n))=O((n+b)\log_b n)$ time. Choosing $b=n$ makes the asymptotic time linear.

Edit: as suggested by Thinh D. Nguyen, since extracting each digit under base $b$ requires division and modular arithmetic, which are not supported by the standard RAM model, we may want to use the word RAM model instead.


vector hashing function having collisions for permutations let's consider vectors in space dim=3 and values {0,1,2,...,99} on each dimension I would like to create hash function but with special trait: collisions only for permutations on input

$\forall_{x, y \in N^3} (y = permutation(x) <=> hash(x) == hash(y))$

is it even possible but without sorting? if so please attach example :)

one idea is to sort these values and then just create a key like $x_1*10e4 + x_2*10e2 + x_3$, for higher dimensions sorting would slow down solving a bit, so is it possible without sorting?

With your limitations, you put all values into about 166,000 or so buckets, so yes, easily. If x, y, z are arbitrarily large, of course not.


standard sequential algorithm with polylog runtime? At the Wikipedia article on time complexity, only a PRAM example is given for polylogarithmic time.

Let $T(n)$ denote the largest number of steps used by a machine to reach a final state on any input with size $n$ bits.

  Is there a program for a standard sequential model of computation (e.g. a Turing machine or a sequential random-access machine), solving some natural problem, so that $T(n) \in \Theta((\log n)^k)$ for some fixed $k>1$?

Where each operation is $ O\left(\log^kn\right)$ amortized/expected; I don't know if necessarily $\Theta\left(\log^kn\right)$:

Dynamic graph connectivity algorithms

Poly-Logarithmic Deterministic Fully-Dynamic Algorithms
for Connectivity, Minimum Spanning Tree, 2-Edge,
and Biconnectivity (PDF)
Dynamic graph connectivity in polylogarithmic worst case time (PDF, slides)
Fully Dynamic 2-Edge Connectivity Algorithm in
Polylogarithmic Time per Operation (PDF)
Lists of connectivity problems

Maintaining Dynamic Sequences under Equality Tests
in Polylogarithmic Time (PDF)
Distances and point-sets:

Maintaining the miminal distance of a point set in polylogarithmic time (PDF, $O\left(\log^2n\right)$, Smid)
New techniques for some dynamic closest-point and farthest-point problems ($O\left(\log^D n\right)$ Supowit)
New Techniques For Exact And Approximate Dynamic Closest-Point Problems (PDF, Kapoor, Smid, $O\left(\log^D n \log \log n\right)$, though cites others with just $O(polylog)$)
TOPP 63: Dynamic Planar Nearest Neighbors, lists 3 papers with data structures that have operations that run in $O\left(log^k n\right)$ time
Point location algorithms,
Monotone subdivisions, without fractional cascading, query-time is $O\left(\log^2 n\right)$
Best known algorithms for point-location in higher-dimensions ($\gt 2$) have a trade-off; $O\left(\log n\right)$ query-time has large memory requirements that make them unscaleable. Reducing the memory requirements (for example to $O\left(n\log n\right)$ results in query-times of $O\left(\log^k n\right)$

Efficient Partition Trees (PDF, Matousek, $O\left(\log^2 n\right)$ insertion time)
An Implicit Data Structure For The Dictionary Problem That Runs In Polylog Time (Munro, $O\left(\log^2n\right)$)

There are also many algorithms with polylogarithmic factors; $\tilde {O}(\cdot)$ is notation that is used when hiding polylogarithmic factors. So $O\left(n\log^k n \right)\in\tilde {O}(n)$.


How to find a subset of potentially maximal vectors (of numbers) in a set of vectors I have a set S (so no duplicates) of d-dimensional vectors of non-negative real numbers (or if you would prefer, floats).

I say a vector u "covers" a vector v if, in every dimension 1..d, u[i] >= v[i]. So for d=3, (3,3,2) covers (2, 3, 1), but (3, 3, 1) doesn't cover (2, 2, 2).

I am interested in finding a subset T of S, such that for every v in T, there is no u in S with u != v, such that u covers v.  Alternatively, I'm interested in removing from S those vectors that are covered by other vectors in S.

What is an efficient algorithm for this?  Barring that, what is at least the "real name" of this problem to help me search for it?

An O(n^2) algorithm is obvious: for every vector in S, check it against every other vector in S, and add it to T if nothing covers it.  I'm having trouble doing much better than that.

I have considered trying to use kd-trees and range trees, but this is for a real world problem, and in practice d is too high and the number of vectors too low, so that e.g. the O(n * log^d(n)) running time is actually worse than the naive O(n^2).  (d is approximately 20-40, and the number of vectors is in the millions).

Edit - Particular Problem Details

As requested, more information about the specific problem I am trying to solve.

The implementation problem at hand involves several sets of vectors, approximately 60-100 sets, each with about 10-20 vectors in them. For every set s, for every vector v in s, v has dimension d, and all axes of v are zero save for one which is positive. A result vector is formed by choosing precisely one vector from each set and adding them together, and a given result vector is strictly worse if it is covered (or apparently the real word is 'dominated') by another result vector. You can assume the non-zero axis of a base vector varies uniformly in [.9, 1.1].  In practice most intermediate results appear to be dominated, and size(T) << size(S)

You're looking for a set of Pareto-optimal alternatives.  If you're looking for all such possibilities (i.e., looking to make $T$ as large as possible), you're looking for the Pareto-optimal front.  You asked for keywords or names to search for this -- those are standard terms for this concept.  See https://en.wikipedia.org/wiki/Multi-objective_optimization.

For specific situations, if the data is structured, it may be possible to take into account knowledge of the structure of the data to find a better algorithm -- but this will depend on the nature of the data.

In your specific case, there are algorithmic techniques that might lead to significant improvements in running time.  In particular, in your setting, each vector $v \in S$ is obtained as a sum of some component vectors $v = \sum_i v_i$, where we have a collection of sets $S_1,S_2,\dots,S_k$ and each $v_i$ is chosen from some set $S_i$.

Let me establish some notation and definitions, prove some mathematical results, and then show them how to compute the Pareto-optimal front for your specific situation.

Definition. We say that $u$ dominates $v$ if $u[j] \ge v[j]$ for all dimensions $j$.  (This is the same as what you call "covers", but "dominates" is the more standard term.)

Definition 1. If $S,T$ are sets, then $S+T$ is defined to be the set $S+T=\{s+t : s \in S, t \in T\}$.

Definition 2. If $S$ is a set of vectors, define $P(S)$ to be the Pareto-optimal front of $S$, i.e., the set of vectors $s \in S$ such that there does not exist any vector $t \in T$ that dominates $s$.

Your problem is the following: given sets $S_1,\dots,S_k$ of vectors, find the Pareto-optimal front of $S_1+\dots + S_k$, i.e., compute $P(S_1 + \dots + S_k)$.  I'll show an algorithm to compute this.

The following lemmas will be helpful:

Lemma 1. If $u$ dominates $v$, then $u+w$ dominates $v+w$.

Lemma 2. If $u_i$ dominates $v_i$ for each $i$, then $\sum_i u_i$ dominates $\sum_i v_i$.

Lemma 3. $P(S+T) = P(P(S)+P(T))$.

(Lemmas 2 and 3 follow immediately from Lemma 1.)

We'll now use Lemma 3 repeatedly to compute $P(S_1 + \dots + S_k)$.  We build a binary tree over the $k$ leaves $S_1,\dots,S_k$.  At each node, we compute the Pareto-optimal front of the sum of the two sets corresponding to its two children.

In other words, here's how we compute the Pareto-optimal front for several values of $k$:

$$P(S_1+S_2) = P(P(S_1)+P(S_2)).$$

$$P(S_1+S_2+S_3+S_4) = P(P(P(S_1)+P(S_2)) + P(P(S_3)+P(S_4))).$$

(In other words, to compute $P(S_1+S_2+S_3+S_4)$, we first compute $U_1 = P(S_1+S_2)$ efficiently using Lemma 3 and $U_2 = P(S_3 + S_4)$ using Lemma 3, then we compute $P(U_1+U_2)$ and use Lemma 3 to conclude that this is equal to $P(S_1+S_2+S_3+S_4)$.)

You can see how this works recursively.  To compute $P(S_1+\dots + S_k)$, we divide the sets in half, recursively compute $X=P(S_1+\dots + S_{k/2})$ and $Y=P(S_{k/2+1} + \dots + S_k)$ using the efficient algorithm, and then compute $P(X+Y)$.

At each stage of the binary tree, we are filtering out all dominated vectors.  If you're lucky, this greatly reduces the number of possibilities that remain at each level of the binary tree.

I suggest you try this on your specific application.  If, as you say, the final size of $P(S_1+\dots + S_k)$ is not too large (say $m$), then this should be efficient: the size at each internal node of the tree will be no larger than $m$, so the time to merge the two children of any node will be $O(m^3)$ [using the trivial quadratic algorithm mentioned in the question], and the total running time will be at most $O(m^3 k)$.  In practice, the actual running time might be significantly faster than that.

You could also explore different algorithms for computing $P(\cdot)$, the Pareto-optimal front of a set.  There are basically two standard algorithms: the "simple cull" algorithm [which is the same as the quadratic-time algorithm you mentioned in the question], and a recursive divide-and-conquer algorithm.

The simple cull algorithm has $O(n^2)$ worst-case running time, as you say.  Actually, if we know that the Pareto-optimal front has size $m$, the running time is a bit better: the running time is $O(mn)$.  (In other words, if we let $n=|S|$ and $m=|P(S)|$, then you can compute $P(S)$ from $S$ in $O(nm)$ time.)  The divide-and-conquer algorithm has $O(n (\log n)^{d-1})$ worst-case running time, which as you say in the question will likely be too small for your parameters.

However, it is also possible to combine the two techniques, where you use the recursive divide-and-conquer algorithm but once the problem size becomes small enough you switch to the simple cull algorithm.  Whether this will lead to any improvement in your actual setting can probably only be determined through experimentation.

For an overview of these algorithms, see for example Section of the following paper:

A Calculator for Pareto Points. Marc Geilen and Twan Basten.  Design, Automation & Test in Europe Conference & Exhibition 2007 (DATE'07), IEEE.

To compute $P(P(S)+P(T))$, the best algorithm I know is to compute $S'=P(S)$ and $T'=P(T)$ using one of the above methods, then compute $S'+T'$ using the obvious quadratic-time algorithm (combine all pairs), then compute $P(S'+T')$ using one of the above methods.


Is linked list a preferable underlying basic DS for a collection mutable through an iterator I need to implement a collection DS that exposes an iterator which can be used to iterate an underlying collection and possibly remove the current item. I can use either a vector (dynamic array) or a linked list as an underlying DS. I'm inclined toward toward linked list because of the easiness of operations. Is it a good decision? What other things I need to consider?

Thanks

Well, if you're looking for easiness of operations, I would recommend a vector. Vectors support a wide array of operations, providing a large number of top-level methods, and iterators namely std::iterator, reverse iterator, and a lot more. With these top-level functions and iterators however, comes the caveat of not being able to modify these to suit your needs. Consider all of this when making the choice.


Minimum number of states in DFA accepting strings where the numbers of a and b are divisible by X and Y respectively? While studying automata theory a typical problem that I face is of the following type:

  Constructing a DFA with minimum number of states for all strings over
  $\{a,b\}$ which have number of $a$’s divisible by $X$ and number of $b$’s
  divisible by $Y$ (where $X$ and $Y$ are some positive integer values).

Is there some standard way of solving such problems?

I looked it up over the net and most people seem to have an idea that minimum number of states will be $X \cdot Y$. I don't think that is right. I constructed a DFA with 15 states for $X = 6$ and $Y = 8$.

Also along a similar line suppose the problem is changed slightly and we are
given "number of $a$'s mod $X$ = $P$ and number of $b$'s mod $Y$ = $Q$".

I believe this type of problem will also have a similar solution as the above problem. Only difference will be in the final states of the two machines. Can someone please confirm whether I am right about this?

I think the minimum number of states is $X\cdot Y$.  In particular, for $X=6$ and $Y=8$, I think 48 states are required.

One can prove this using Myhill-Nerode.  The equivalence class (in Myhill-Nerode) of string $s$ is uniquely determined by the pair $\langle n_a(s) \bmod X, n_b(s) \bmod Y \rangle$, where $n_a(s)$ counts the number of $a$'s in $s$, and $n_b(s)$ the number of $b$'s.  Two different equivalence classes $\langle i,j \rangle$, $\langle i',j' \rangle$ can be separated by the suffix $a^{X-i} b^{Y-j}$, since that'll take the former to an accepting state and the latter to a non-accepting state (if $i \ne i'$ or $j \ne j'$).  This gives us $X \cdot Y$ different equivalence classes, so any DFA accepting this language must have at least $X \cdot Y$ states.

Are you sure you can do it in 15 states, for $X=6$ and $Y=8$?  Is it possible you might have made a mistake somewhere in your DFA?


Decision problem for a Regular Langauge I'm not sure if my logic is correct when it comes to the algorithm for decision problems. The concept is confusing me when I fail to distinguish its answer from that of a proof.

For example:

Given two finite automata $M_1, M_2$ that operate on a common alphabet, find an algorithm to show that:

$$L(M_1) \subseteq L(M_2)$$

And how I viewed it was:

Find a string $w$ from the alphabet $\Sigma$
Feed $w$ to $M_2$; if accepted then $w$ is part of $L(M_2)$
Feed $w$ to $M_1$; if accepted then $w$ is part of $L(M_1)$
If $w$ was accepted by $M_2$ and $M_1$, then $L(M_1) \subseteq L(M_2)$
Otherwise reject

Unlike proofs which require mathematical arguments, algorithms for decision problems seem more like a logical flow or sequence description. If it were a proof I would have to perhaps design a language or expression using properties and lemmas where as here I just describe the process of determining if the statement can be answered (via "yes" or "no").

Your algorithm is not really specified completely, since you don't explain how you choose the word $w$. However, even once you do specify how $w$ is chosen, your algorithm will be incorrect. The reason is that it is completely symmetric in $M_1$ and $M_2$. In other words, if the algorithm accepts on the pair $(M_1,M_2)$, then it will also accept on the pair $(M_2,M_1)$. This means that it will necessarily fail for machines satisfying $L(M_1) \subseteq L(M_2)$ but $L(M_2) \nsubseteq L(M_1)$.
Presumably in class you were shown other decision algorithms for regular languages. I suggest you try to emulate them. As an example, here is an algorithm that determines whether $L(M) \neq \emptyset$, for a DFA $M$.

Input: A DFA $M = \langle \Sigma, Q, q_0, F, \delta \rangle$.
Accept if some state in $F$ is reachable from $q_0$, and reject otherwise.

(In class you will probably need to be more verbose.)
To show that this algorithm is valid, we need to show two things:

If $L(M) \neq \emptyset$, then the algorithm accepts.
If $L(M) = \emptyset$, then the algorithm rejects.

To prove the first part, suppose that $w \in L(M)$. By definition, the state $\delta(q_0,w) \in F$ is reachable from $q_0$, so the algorithm accepts.
To prove the second part, we will prove the contrapositive: if the algorithm accepts, then $L(M) \neq \emptyset$. Suppose that some state $q \in F$ is reachable from $q_0$. This means that there is some path from $q_0$ to $q$. If $w$ is the concatenation of all symbols on this path, then $\delta(q_0,w) = q \in F$, and so $w \in L(M)$, showing that $L(M)$ is non-empty.
(Once again, in class you will probably need to be more verbose.)


After implementing a novel encryption algorithm, how would one go about analyzing its security or get help from others in doing so? Preface: This question was originally asked on Theoretical Computer Science, and the kind people there referred me to this web site. It is being repeated here in an attempt to find a satisfying answer.

Over the years, two novel encryption techniques have come to mind and been implemented as programming libraries that could be integrated into applications. However, how to analyze their security and vulnerability characteristics has never been very clear, and their usage has been limited to mainly experimental tests. Are there tools available for automated examination of such parameters one may be interested in understanding for an encryption library? Are there bodies of people who are interested in being introduced to new encryption concepts for the purpose of executing their own personal analysis on such a process? I'm not sure where to look.

The first encryption algorithm is a mono-alphabetic simple substitution cipher. It requires two keys to operate and is designed to frustrate frequency analysis. The longer of the keys forms a table by which plain-text has a normal substitution cipher applied. Each encoded byte is then split into four values of two bits each. The second, shorter key is then used to allow a random selection from four groups of sixty-four unique bytes each. Each two bit value from the encoded byte is used to select which group of sixty-four bytes to use. Encoding has two disadvantages: the output is four times larger, and repeated data encoding may allow some frequency analysis.

The second encryption algorithm is a stream cipher like the first but internally operates on blocks of data. It utilizes two keys to operate: the first is a two-dimensional array that describes how to construct a (virtual) multidimensional grid, and the second is an initialization vector for the encoding/decoding engine. It attempts to overcome frequency analysis by encoding bytes with a window of preceding bytes (initialized from the second key). A byte with its preceding window of bytes form a multidimensional index into the aforementioned grid. Unfortunately, encoding duplicate blocks of data longer than the window size starts yielding equivalent data.

Typically, there are a variety of steps in evaluating a new algorithm.  They start with the quick review

is it already known?
does it vary only in nonrelevant ways from what is known?

which is commonly enough to show vulnerabilities in many amateur attempts at encryption.  The point is that there are a number of well known ways to translate strings of symbols into other strings of symbols, and many of those have been evaluated in common cryptographic studies.  Good books on cryptography cover these.

Then, the more intensive analyses begin.  These include:

functional inversion
analysis of the symbol statistics
differential cryptanalysis

and a variety of other mathematical techniques for extracting information of the keys from the intercept stream.

Also, if the technique involves nontraditional information stores (if it doesn't have keys, if it has strange communication channels and protocols, etc.), then you have to also analyse the various impersonation and interception scenarios on each channel.

For the description given, it would appear that the first cryptographic algorithm would fail the first quick view.  Substitution ciphers are well known.  It doesn't really matter how many times you compose substitution ciphers, their properties are the same.  If you had 10 keys and did substitution 10 times before final send, it would be equivalent to a single key substitution cipher and have no better security.  Unless there is some other tweak to the algorithm, that would quickly be dismissed as already known.


What does the following algorithm approximate? (Assume m>1,ϵ>0) x = m;
y = 1;
While (x-y > ϵ)
{
    x = (x+y)/2;
    y = m/x;
}
print(x);

The answer is m½, its the Babylonian algorithm for square roots.
I understand the algorithm but haven't been able to reverse engineer what this code does (which is the point of this question since its not part of the curriculum and almost no one would have prior knowledge of it). So again, my question is how can I deduce this code calculates square roots, just from the code itself?

By simply looking at the structure of the loop, we know that if the while loop terminates after going into the loop (I'll assume this for simplicity as it's the interesting case) that $y=\frac{m}{x}$ (last instruction) and that $x-y<\epsilon$ (exit condition). Combining the two gives you $x< \sqrt{m+x\dot\epsilon}$. If you manage to notice that $x\geq y$ at the end of each iteration of the loop, then you also get $x\geq y=\frac{m}{x}$ and therefore $\sqrt{m}\leq x< \sqrt{m+x\dot\epsilon}$.

You could write down the sequence of values taken by $x$ and $y$ mathematically (this is what you would do anyway to prove correctness and termination of the algorithm if you knew what it did/was supposed to do, but it can also help you to determine this!).

Initially, $\begin{cases}x_{0}=m\\ y_{0}=1\end{cases}$.
At the end of the $n^{\text{th}}$ iteration of the while loop: $\begin{cases}x_{n}=\frac{x_{n-1}+y_{n-1}}{2}\\ y_{n}=\frac{m}{x_n}\end{cases}$

Now, analysing the two sequences we find that:

$(x_n)$ is decreasing
$(y_n)$ is increasing
$x_0>y_0$

This is enough to say both sequences converge (as they are monotonic and bounded), to say $x$ and $y$. Using $\begin{cases}x_{n}=\frac{x_{n-1}+y_{n-1}}{2}\\ y_{n}=\frac{m}{x_n}\end{cases}$ we can say that $x=y$.

So $\forall n>0,x_n\geq x=y\geq y_n$. In particular the algorithm must terminate (as $x_n-y_n$ is non-negative and converges to $0$). From there you can continue like in the first part ('By simply looking at the$\dots$').


Algorithm for identifying polygons (set of points) Are there any known algorithms for uniquely identifying some set of points despite scaling, moving and with some amount of threshold?

I have an "ideal" set of points with coordinates and I need to check if other set matches the ideal one. Other set could be rotated, scaled or distorted a bit (points could be placed with slight offset).

All sets have one common property: there are 2 points located farthest apart. This can be used to, at least, negate rotation. We do know angle (45deg) that line between farthest points create with axis, and we do know needed distance between them.

I've tried following algorithm:

Rotate "other" set to some point (so that farthest points create
line that is 45 degrees to "x" axis);
Scale set so farthest points distance = "ideal" distance;
Use sort of GeoHashing algorithm to get point hash with some accuracy (like threshold).

But that approach gave nothing. "GeoHashing" produces semi random results and probably not suitable for 1000x1000 calculations. And using geometric operations furthermore reduced accuracy (initial distortion of points + inaccuracy of some geometric methods).

EDIT:

I want to add some details to it:

Points set contains only 5 points (including those distant ones);
There could be several "ideal" point sets and I want to find if given set matches something (that's why I used GeoHash);
Basically task is to find matching polygon/set of points with given accuracy. If points do not match exactly (not located in the same coordinates), but are pretty close to ideal location (like +-2) it's a match.

I'll assume you are given two sets of points and want to determine whether one can be transformed to match the other.   This is the pointset registration problem in computer vision.  There are standard algorithms for this problem.

One of the crucial challenges is outliers -- e.g., points in the first set that don't have any corresponding point in the second set, or that have a large amount of error in their location.  If you don't have outliers in your setting, then the problem becomes noticeably easier: simple least-squares linear regression might suffice.

If you have to deal with outliers, one standard way is to use RANSAC to find a rigid transformation that, when applied to the first set, makes it match the second set.  A rigid transformation is determined by the correspondence between two points.  So, you can use RANSAC: repeatedly pick a pair of points in the first set, choose a candidate pair of points in the second set for them to be matched to, compute the rigid transformation that maps the first two points to the latter two points, apply it to all points in the first set, find all inliers (points that are well-matched), update your estimate of the rigid transformation, count the number of inliers, and do this many times and keep the best rigid transformation you've found.

There are many other approaches as well.  If you do some research, you should be able to find many algorithms, techniques, and even existing tools.


Where to put the state in a two-stack push down automaton? theoretically, the state is between the two kleene-stars of the work-alphabet
gamma* q gamma*

where q is the current state and each gamma* is the content of one of both stacks. But where is "the middle" with the state? Regarding the one tape of the classical Turing Machine it is obvious.
Yours,
von Spotz

A configuration of a TM is usually defined as $uq\sigma v$, where $u\sigma v$ is the tape's content up to a cell from which there are only blanks, $q$ is the current state, and the head of the machine points at the letter $\sigma$. So the place of the state $q$ in the configuration $uq\sigma v$ is there simply to indicate at which letter the head points. Generally, a configuration holds a snapshot of the model during its run, including all information that is relevant to carry out the computation one step at a time.
Now consider a two-stack PDA $\mathcal{A}$, and think how to defined a configuration of it. Here, unlike TMs, we always point (in each stack) at the top of the stack, and therefore an indication to the stacks contents is sufficient - storing where the heads point does not add valuable information to help us compute the next configuration, given the current one. Specifically, the necessary information a configuration of $\mathcal{A}$ needs to hold are:
1- the content of the two stacks.
2- the current state.
3- the input left to be read.
So, we can define a configuration as a word of the form $ u q v \# w$, where $u$ is the content of the first stack, $v$ is the content of the second stack, $q$ is the current state, $w$ is the input left to be read, and $\#$ is a special charecter to indicate the end of $v$ and the beginning of $w$. Please note that the fact that $q$ is between $u$ and $v$ is not crucial. We could have defined a configuration of $\mathcal{A}$ as $qu\#v\#w$, and that makes no difference as long as we agree on which definition we stick. Anyway, I think the later definition is closer to being standard.


How to prove that $\{\$x\$\}$ is a regular language if $x$ is derived from $L=\{w\}$ by substituting substrings? Prove that if $L$ is regular over $\Sigma=\{0,1,2\}$ then the following language over $\{0,1,2,\$\}$ is also regular:
  $$
G=\{\$x\$|\exists w\in L: x\text{ is derived from }w\text{ by substituting } 01 \text{ with }\$\$ \}
$$
  For example, if $10112\in L$ then $\$1\$\$12\$\in G$.

I think this can be solved using closure properties of regular languages.

1) Let $H=\$L\$$. $H$ is also regular because it's concatenation.

2) Let $h:\Sigma\to \Sigma^*$ be defined as follows:
$$
h(\$)=h(0)=h(1)=\$
$$
Then:
$$
G=h^{-1}(H)\cap \$(\Sigma^*\$\$\Sigma^*)^+\$
$$
which is regular because $h^{-1}$, intersection and regular expressions are closed in regular languages.

I wonder if my proof using closure is correct or automaton should be built in this case? In addition if I managed to think of a regular expression to describe $G$ then this alone would've proved that $G$ is regular?

Unfortunately, your argument breaks down at step 2). For example, let $L=\{01\}$. Then
$G =\{\$\$\$\$\}.$
$H=\{\$01\$\}$.
$h^{-1}(H)=\emptyset$ since every word in the range of $h$ contains neither 0 or 1.
$h^{-1}(H)\cap \$(\Sigma^*\$\$\Sigma^*)^+\$=\emptyset.$
However, $G$ is not empty.

  If I managed to think of a regular expression to describe G then would this alone have proved that G is regular?

Of course. However, it looks like it is not immediate to figure out a regular expression for $G$ even if we have been given the regular expression for $L$ and DFA for $L$.

Here is a way to show $G$ is regular by DFA.

Let the DFA for $L$ be $(\Sigma,Q, q_0,\delta_L, F)$.

Define (an incomplete) DFA $D$ with alphabet $\{0,1,2,\$\}$, states $Q\times \{s_0, s_1, o\}$, initial state $(q_0, s_0)$, accepting state $F\times\{s_0, o\}$, transition function $\delta_D$ such that
$\delta_D((q, s_0), 0)= (\delta_L(q, 0), o) $
$\delta_D((q, s_0), 1)= (\delta_L(q, 1), s_0) $
$\delta_D((q, s_0), 2)= (\delta_L(q, 2), s_0) $
$\delta_D((q, s_0), \$)= (\delta_L(q, 0), s_1) $

$\delta_D((q, s_1), \$)= (\delta_L(q, 1), s_0) $

$\delta_d((q, o), 0)= \delta_L(q, 0), o) $
$\delta_d((q, o), 2)= \delta_L(q, 2), s_0) $
$\delta_d((q, o), \$)= \delta_L(q, 1), s_1) $

Here is how we can understand the states

state $(q,o)$ corresponds to the states that are reached by words that end with $0$.
state $(q,s_1)$ corresponds to the states that are reached by words that end with odd number of $\$$'s.
state $(q,s_0)$ corresponds to the states that are reached by words that end with $1$ or $2$ or even number of $\$$'s.

We can check that $G=\$L(D)\$$.

Exercise. Prove that if $L$ is regular over $\Sigma=\{0,1\}$ then the following language over $\{0,1,2\}$ is also regular.
$$
G=\{x\mid \exists w\in L: x\text{ is derived from }w\text{ by substituting } 00 \text{ and } 11 \text{ with } 2 \text{ from left to right} \}$$
For example, if $w=1000111110$, then $x=1202210$.


What is the best algorithm for image comparison in terms of speed? Problem domain - I'm implementing a home monitoring system using smart phones. At regular intervals rear camera of the phone takes images and compare them for a change detection. This change detection is done inside the android app itself. Only after a change is detected, image is sent to server.

I want to know a fast algorithm to compare two images and detect whether a significant change is occurred. I want to avoid changes due to light effects and negligible changes. So far I have come up with multiple options
 1. Feature matching using SIFT
 2. Comparing histograms
 3. Template matching

But I'm not sure which one is more appropriate to my problem domain or whether there are better options.

I want to avoid changes due to light effects

A similarity measure based on binary descriptor can deal with this issue since it designed for multimodal images.

Also, you can try correlation coefficient since it cloud be used for real-time applications. for more information visit this page. Hence this algorithm in Matlab as a function called corr2 to find the degree of similarity between 2 images.


Contour pushing algorithm I'm implementing push contour feature for web application. It is an ability to change the contour by touching it. Mouse pointer becomes a circle that bumps contour (like in Photoshop). Contour is polyline object and pushing circle is some point with defined radius.

Sequence of actions on mousemove is following:

Detect points in polyline that are closer to pushing point than defined radius
push those points or just draw circle segment in the defined area.

Questions:

How to determine points that are need to be pushed? I can iterate all segments in polyline (300-600 segments) and calculate distance for each like here: https://gist.github.com/mattdesl/47412d930dcd8cd765c871a65532ffac . But in this case full iteration 60 times per second is quite performance hard. May by some algorithm can do it more afficient?
How to push the point? we can't just change it position. As 1 point finally can become 2 points. It is more like drawing circle segment.

I suggest you use a data structure for nearest neighbor search to speed up the process of finding all points in the polyline that are closer than the defined radius.  That should lead to a significant speedup.


Kolmogorov randomness for Pseudo random number generator I am working on pseudo random number generation for one of my projects. My goal is to prove that the output is almost Kolmogorov Random since Kolmogorov complexity is uncomputable.
So would appreciate any help or guidance for this subject matter.

You can't.  Kolmogorov complexity is not computable.  See, e.g., https://en.wikipedia.org/wiki/Kolmogorov_complexity.


Performance gain by implementing streamlined simplex I have to solve linear transportation problems for a research project. Ideally, I should design an application that will recieve the problem data as an input and then show some results. The size of the problems are in the order of N=10.000 sources and N=10.000 destinations, and 2N=20.000 restrictions of equality, one for each source and one for each destination.

I've been using Python's PuLP with the standard solver(COIN-OR) and with GLPK. As a general rule, the performance of COIN-OR is superior than that of GLPK, but even with COIN-OR the problems are taking too long to be solved. As far I as know, there's a streamlined version of the simplex algorithm for transportation problems, but I ignore the magnitude of the improvement in performance I should expect by using that streamlined version of simplex algorithm.

So, my first question is if those solvers identify the transportation problem structure of the problems I'm dealing with and act accordingly.

If the answer turns out to be no, then my second question is if I can exploit that particular structure of the transportation problems with a free solver that has a Python interface.

Also, will I note some improvement if I implement myself the streamlined version of the simplex algorithm? Or implementations must be too far from naive to really beat a well-established simplex solver like the ones I mentioned before?

By "streamlined", I assume you are talking about a minimum cost flow algorithm, and you have been using the standard LP solver from Coin-OR. Then I would advise using the solver from the Lemon library (from Coin-OR as well). It has Python bindings.

As for the performance, I never benchmarked it myself. Given the algorithms involved, however, just the datastructure specialization may well be a 10x improvement. For some problems, I guess the difference may well be orders of magnitude.

I don't think Coin-LP detects the network structure - I'm pretty sure neither it nor GLPK does.

There are algorithms specialized for transportation problems (even more specific than MCF), but here you'd probably have to reimplement them, and not gain as much as going from generic simplex to minimum cost flow.

While looking for benchmarks, I just found two other solvers linked from this blog post, with performance claims: Google OR-tools and PyMCFSimplex.


How does a computer distinguish two separate transmissions on a wire My basic idea of networking at the lowest layer is that one computer will send a bunch of parallel bits at a time down a cable and another computer will read these bits.  For example, computer #1 sends a bunch of parallel bits to computer #2.  Computer #2 then gets the bits then waits for the next bunch of bits.  And so on.

I have a couple of questions about how this works and how we get around a few problems.

Problem #1: Say Computer #2 doesn't wait long enough for the next series of bits.  Computer #2 may accidentally read the first set of bits twice, messing up communication.

Problem #2: Computer #2 waits too long.  It doesn't read the second set of bits in time and only starts reading after the second set of bits are shown.

[to summarize problems 1 & 2, it seems like it would be very difficult to exactly sync the rate of transmition between the two computers)

Problem #3: We can't rely on every transmission to be different.  So it's not like we can just wait for the transmission to change and then store the new value.

Problem #4: Say we use a special phrase.  So after every transmission computer #1 signals to computer #2 that the transmission is going to change by flashing a bunch of 1's.  This is a problem because what if our data is a bunch of 1s?  We won't know if the transmission changed or not.

The only solution I can think of is to have some extra bit that alternates for each transmission, bit this seems like it wouldn't work for one-bit-at-a-time transmission networks like wifi. What part of all of this am I missing?  How is this problem solved in the real world?

On a wire you encode bits by changing the voltage, for example +5V could mean 1 and -5V could mean 0. If you do this naively you get problems with long sequences of 1's or 0's. For example you mentioned clock drift, i.e. when do I know that one 1 ended and the next 1 starts? But it's also problematic to have one voltage for a long time, because charge could build up at one end that needs to be dissipated somewhere.

So instead of using a naive encoding, we use a trick. For each bit we use two clock cycles, and encode the bit as the change in voltage. This way we implicitely also transmit our clock down the wire, the receiver can synchronise their clock using the same edge detection algorithm that they use to read the bits. This scheme is called Manchester code.

If you use more voltage levels to encode multiple bits at a time, the same basic idea can be applied. Instead of encoding the bits naively, we ensure that there is enough change in the data so that we can keep the clocks synchronised and the voltage on average 0. Check the related articles in the Wikipedia, for example 8b/10b encoding.


Solving $T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n$ without the Master Theorem I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$
with base case $T(n) = 1$ if $n \leq 1$.
I know that the solution is(with the help of the Master Theorem) $$\Theta(n*log^2(n))$$
I tried without the Master theorem and witht the help of the substuition method I got the following expression
$$T(n)=n+2*n*\sum_{k=0}^{log_{3}(n)-1}log(\frac{n}{3^k})$$
How can I convert this expression into a valid $\Theta(n*log^2(n))$ expression ?

Let's suppose $n=3^k$. Then we have:
$$T(n)=3^kT(1)+2n\log \frac{n^k}{3^{k-1}\cdots3^0}=n+2n\log 3^{k^2-\frac{k(k-1)}{2}} =\\
=n+2n\log n \cdot \frac{\log_3 n+1}{2}   $$
Hope it helps.


If c ∈ Σ denotes terminals, then is Y = Σ∖{c} the set of non-terminals? If $c\in \Sigma$ denotes terminals, then is $Y=\Sigma \setminus \{c\}$ the set of non-terminals?

These notations are used here, p. 379. But I cannot find their definitions.

So what I'm asking is, is the above a reasonable interpretation?

No. $\Sigma$ is the set of symbols that the strings in the two languages are over ("the alphabet"). So $c$ is one symbol, and $Y$ is the set of all the other symbols in the alphabet. These will all be terminals when the CFG is constructed in the proof.

What the theorem is saying is that if you have a context-free language $L$ that uses only symbols from $Y$, then $L$ is also regular if and only if the new language where you prepend a $c$ to every string in $L$ (i.e. $cL$) is also regular.

At this point there's no mention of a CFG, so there's no terminals or nonterminals. The proof is where the CFG is introduced as a consequence of $L$ being context-free. Note however that this proof is very very truncated, there's a lot of detail and reasoning left out, so it's a lot harder to follow than it should be if you don't already see the reason that the theorem is true. There's also a series of mistakes in it.


Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is? I am not sure I see it. From what I understand, edges and vertices are complements for each other and it is quite surprising that this difference exists.

Is there a good / quick / easy way to see that in fact finding a Hamiltonian path should be much harder than finding a Euler path?

Maybe the following perspective helps:

When you are trying to construct a Eulerian path, you can proceed almost greedily. You just start the path somewhere and the try to walk as long as possible. If you detect a circle, you will delete its edges (but record that this circle was constructed). By this you decompose the graph in circles, which can be easily combined to an Eulerian tour. The point is, none of your decision "how to walk across the graph" can actually be wrong. You will always succeed and never get stuck.

The situation with Hamiltonian paths is different. Again, you might want to construct a path by walking along edges of the graph. But this time you can really make bad decisions. This means you cannot continue the path, but not all vertices have been visited. What you can do is back-track. That means you revert some of your old decisions and continue along a different path. Essentially all algorithms that are known for the general problem rely on some way or the other on back-tracking, or trying out a large set of solutions. This, however, is characteristic for NP-complete problems.

So (simplified) bottom-line: Eulerian path requires no back-tracking, but Hamiltonian path does.

(Notice that it might be that P=NP and in this case a clever Hamiltonian path algorithm would exist.)


Algorithm to find the shortest walk with k leaf nodes on a tree Let's say I have a general tree. What algorithm can I use to find a shortest walk that starts at the root, passes through exactly $k$ different leaves, and ends at the root?  Passing through a node/edge more than once is allowed.

For example, consider this graph:

For $k = 1$, the shortest walk would have the node 4. For $k = 2$, the leaf nodes would be 4 and 12. For $k = 3$, the leaves would be 4, 16 and 17.

What I actually need is the length of the shortest walk (if this simplifies anything).

I could not find an algorithm for this, but maybe I searched with the wrong terms.

This can be solved by a fairly standard dynamic programming algorithm. For a given node $v$, let $C(v,k)$ be the minimum length of a (closed) walk through the subtree rooted at $v$ passing through exactly $k$ leaf nodes ($C(v,k)=\infty$ if there is no such walk).

If a node $v$ has children $c_1,\ldots c_m$, then $C(v,k) = min_{k=a_1 + \ldots + a_m} \Sigma_{\{i:a_i\not = 0\}} 2 + C(c_i, a_i)$ (i.e. taking the minimum over all ways to split up $k$ over the children of the node).

With some modification, this can be made to run in $O(n^3)$.


Is there a formalization of a general version of the sweep line algorithm? If not is it easy to derive? A well known algorithm in computational geometry is the sweep plane algorithm. I've been trying to find if there's a general version of the sweep plane algorithm  in $\mathbb{R}^n$, I don't need to implement it but I need to study how the general version would work.

If there's nothing you known in literature, how difficult is trying to formalize it?

I believe it could be formalized recursively (like sweeping hyper planes from dimension $n-1$ downto $2$. But I need to be sure.

Update:

I've been asked to elaborate a bit more...

In the best reference I know, the plane sweep is basically explained as "Imagine this plane that moves through event points, where something happens". The specific instance are almost 2D and 3D cases (involving problem like segments intersection, triangulation and voronoi diagrams), nothing is mentioned how the paradigm works in general.

Perhaps this is too broad a question for a coherent answer, so let me first try to say something about line segment intersection, at least. The main reason the sweep-line algorithm is efficient is that we only have to worry about neighboring line segments. We can generalize this procedure to $\mathbb{R}^n$ by noting that if we sweep a line over a sub-plane of $\mathbb{R}^n$ (i.e. the projections of all segments from $\mathbb{R}^n$ on this plane), any intersecting segments in $\mathbb{R}^n$ cannot be 'separated' on this line by a segment that intersects neither of them (If such a segment exists, the segments would be separated by the $n-1$-dimensional hyper-plane orthogonal to the projected plane). So, we can in fact apply the $2D$ algorithm on some plane projection, with the only difference being that we test individual intersections in $\mathbb{R}^n$. (some non-general position edge-cases might get even nastier, but I think the general procedure still applies)

Now, for the sweep line paradigm in general:

I think the main algorithmic idea is that if we want to answer questions about objects in $\mathbb{R}^n$ that concern only their 'neighbor' objects (line segment intersection is the most clear, but Voronoi diagrams and even triangulation fit this description to a certain extent), it is efficient to only query for 'local' objects. To achieve this, sorting seems like a good idea. However, there is no clear method to sort points in $\mathbb{R}^n$ in an useful way, for $n>1$ (I will explain why later*), while sorting in $\mathbb R$ can be efficiently maintained, using binary search trees.

So, the sweep line algorithm attempts to solve this problem by sorting on the order in one direction, on the sweep line. The main thing that the algorithm has to do is to 'make up' for this simplification by traversing the space in a structured matter. Therefore, it makes little sense to use an $n-1$-dimensional hyper-plane to sweep the space with, as we cannot sort the projections on this plane.

Another idea is that the sweep line paradigm allows the algorithm to 'ignore' already visited points. While this is intuitive, I don't think that this idea is the key to efficiency. This idea leads to replacing $n^2$ by $\sum_{i=0}^n i$, so it gives no asymptotic improvements.

So, I think that we have an answer to your statement:

  I believe it could be formalized recursively (like sweeping hyper planes from dimension $n−1$
  downto $2$. But I need to be sure.

The sweep line paradigm uses a line**, even in $\mathbb{R}^n$.

*: Why can't we just use a lexicographical sort on a 2D-plane and call it a day? Recall why we sort: we want to find 'neighbors' of the objects since we don't need to compare non-neigbors. In $\mathbb{R}^n$, point $p$ being a neighbor of some point $q$ usually means that the (Euclidean) distance between them (in some direction) is minimal, i.e. there is no closer point $r$ 'in between them'. So, our order must be 'distance preserving'. This property is not satisfied by a lexicographical sort.

For example, draw a 4x4 grid of dots, choose to sort by row major or column major order, give them a number to indicate their rank and observe that some neighboring dots differ by 5, more than all other points in the same row/column! We can show that there is no (total) ordering on $\mathbb{R}^n$ that preserves 'neighbors' of points.

However, we must first make this more precise. Observe that an ordering of $\mathbb{R}^n$ is actually a function to some subset of $\mathbb{R}$! (You can also consider it a space-filling curve, the idea is similar) That is, given a total ordering on $\mathbb{R}^n$, there is a function $F : \mathbb{R}^n \rightarrow \mathbb R$ that completely characterizes it (I could make this more precise, but I feel that that's for another question). For a function $F$ (or functional, in this case) to be 'distance preserving', it means that there exists some $c\in \mathbb R$ such that $\|Fx\| = c\|x\|$ for all $x\in \mathbb{R}^n$. If $F$ is non-linear, it is not distance preserving (again, showing this is out of scope).

If $F$ is linear, our condition implies that it is an (linear scaling of an) orthogonal linear map (by definition, depending on your point of view), which means in particular that $F$ is of full rank. This means that $F$ cannot map from a subspace (the plane) to one of strictly lower dimension (a subset of $\mathbb R$). Therefore, there exists no distance preserving $F : \mathbb{R}^n \rightarrow \mathbb R$ and therefore no 'distance preserving' ordering of $\mathbb{R}^n$ for $n>1$ exists. Finally, this means (here I'm making an 'informal leap') that there is no 'neighbor preserving' ordering on planes and hyper-planes.

**The key part of the sweep line paradigm is the projection to a one-dimensional space to be able to use sorting, such as a line. This space does not have to be linear, however. Therefore, we can in some cases (line segment intersection is  not such a case) do something similar with not a line, but with a curve (In the setting when our objects are lines, this curve needs to always intersect each line exactly once, so we cannot use a space-filling curve). This is called a topological plane sweep. See the lecture notes by David M. Mount for more information.


QuickSelect with Median of Medians runtime I know that Median of medians itself is $O(n)$.
With a good pivot, QuickSelect is $O(n)$, too -- but with a bad one, it's $O(n^2)$.
But if I now were to use the element gotten through median of medians as the pivot for QuickSelect, what would the new worst-case runtime of QuickSelect be? Would it be $O(n)$ guaranteed too?

Why would it not be $O(n\log n)$? I'm a bit confused, I guess. Since we have to choose the median of medians, which takes $O(n)$, for each subproblem, and we have $\log n$ subproblems (always recursing on one side of the median).

The medians of medians algorithm will return a pivot with a rank between $\frac{3}{10}n$ and $\frac{7}{10}n$ in time $O(n)$.

You can then describe the worst-case computational complexity of Quickselect on an instance of $n$ elements with the following recurrence relation:
$$
T(n) = T\left(\frac{7}{10}n\right) + O(n),
$$
where $O(n)$ accounts both for the work needed to run the median-of-medians algorithm an for the partitioning of the input.

Unrolling the recursion shows that (you can prove this formally by induction):
$$
T(n) \le c n \sum_{i=0}^{+\infty} \left( \frac{7}{10} \right)^i = cn \cdot  \frac{1}{1-\frac{7}{10}} = \frac{10cn}{3} = O(n),$$

where $c>0$ is a suitable constant (hidden in the $O(n)$ notation of the recurrence relation).


Runtime of Euclidean Algorithm Given two $n$-bits numbers $a$ and $b$, I am not sure on how to find the runtime of the euclidean algorithm for finding the $\gcd$ of $a,b$. The problem (for me) in here is that apart from the size of $a$ and $b$, I don't feel like I have any other information that will help me  to know what is the runtime of the algorithm. I saw somewhere that the number of rounds is $\log_2 a = n$, but, assuming this is correct, I have no intuition as for why it is such?

My question is for an explanation to how much time it takes to calculate the $gcd$ (as a function of $n$)?
Is it linear in $n$?

Let's analyze two consecutive steps of the GCD algorithm: given $a > b$, we compute $c = a \pmod{b}$ (replacing $a$) and $d = b \pmod{c}$ (replacing $b$). The two new numbers $c,d$ we are left with satisfy

$$ c+d \leq b \leq \frac{1}{2} (a+b). $$

So the sum of the two numbers decreases by a factor of at least a $1/2$ every two iterations. If $a,b$ are at most $n$-bit long, then at the start of the algorithm, $a+b \leq 2^{n+1}$. After $2(n+1)$ steps, the two remaining numbers have sum at most $1$, so by that time the algorithm must have terminated.