# Question
Title: What is the set of operations of a Turing machine?
From https://en.wikipedia.org/wiki/Abstract\_machine

> A typical abstract machine consists of a definition in terms of input, output, and **the set of allowable operations** used to turn the former into the latter.
>
> The best-known example is the Turing machine.

1. In a Turing machine, what is its set of operations?
2. Is $\delta$ in the following definition of a Turing machine an operation? (If yes, then there is only one operation in a Turing machine?) Thanks.

From https://en.wikipedia.org/wiki/Turing\_machine

> a (one-tape) Turing machine can be formally defined as a 7-tuple $M= \langle Q, \Gamma, b, \Sigma, \delta, q\_0, F \rangle$ where
>
> $Q$ is a finite, non-empty set of states
>
> $\Gamma$ is a finite, non-empty set of tape alphabet symbols
>
> $b \in \Gamma$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
>
> $\Sigma\subseteq\Gamma\setminus\\{b\\}$ is the set of input symbols
>
> $q\_0 \in Q$ is the initial state
>
> $F \subseteq Q$ is the set of final or accepting states.
>
> $\delta: (Q \setminus F) \times \Gamma \rightarrow Q \times \Gamma \times \\{L,R\\}$ is a partial function called the transition function, where L is left shift, R is right shift.

# Answer
> 2 votes
The set of operations is what makes the machine work, i.e. read input somewhere, write output somewhere, and change its internal state (which includes anything it may change in its memory which can be a tape or some other device).

In the case of a TM, that is done by the transition function $\delta$.

Now, as you wish, you may see the transition function (actually a relation, when non-deterministic)) as the unique operation applied repeatedly. Alternatively you may consider that each instance of the (arguments, effect) pairs defined by the function, usually defined on a finite number of possible arguments pairs (state, tape content), each associated with a finite number of effect triples (state,tape output,move), are as many separate instructions, the transition relation being then the instruction set.

It is not a fundamental issue to decide whether you see it globally or case by case.

# Answer
> 1 votes
The Wikipedia definition makes more sense for machines like the RAM machine in which the "program" looks more like a program. Let me first give an example, and then explain what the counterpart is for Turing machines. In any case, the term "allowable operation" is informal, though the notion of abstract machine can be made formal, for example in the work of Yuri Gurevich.

A RAM machine is one in which the program looks very much like C code. Memory cells and registers (both unbounded) hold bounded-size integers, the exact bound depending on the input length. The machine supports integer arithmetic, bitwise operations, and comparison operations. One can think of other variants, for example the basic data type could be unbounded integers, or even unbounded reals ("real RAM"). We can also allow more basic operations: square root, general powers, logarithm, exponential, and so on. These variants can effect the computational complexity, but usually don't change the Turing-completeness of the model.

The Turing machine model is very primitive. The basic operations are very weak – the machine can read and write symbols, the head moves to the left or to the right, and that's all. Turing machines are also programmed differently.

One can imagine a Turing machine in which each cell would contain an integer. The control would have to be defined somewhat differently – for example, perhaps the decision what to do next could depend on comparing the current value to a value in some register, and then the allowed operations would be to copy some value to some register or from register to a cell, basic arithmetic on registers, and so on. But that would be quite a different model, one which I don't recall having ever seen.

---
Tags: terminology, turing-machines
---


# Question
Title: Why can't we search lexicographicaly ordered programs to compute Kolmogrov complexity?
Kolmogrov complexity is known to be uncomputable. Why can't we enumerate all programs of size i = 0 in lexicographical order - if any produce string s, that is the Kolmogrov complexity; if not, increment i and iterate? Won't that prove that no program of length \< i generates string s?

# Answer
The problem with your approach is that some programs never halt, and it's difficult (indeed, uncomputable) to tell whether they do. You can tell if a program outputs $s$ and halts, but you don't know how much to wait before declaring that the program never halts. However, your approach shows that it is possible to write a program that prints upper bounds on the Kolmogorov complexity of a give string, eventually printing the correct upper bound. This doesn't give you the Kolmogorov complexity since you don't know when the program will have printed its final upper bound.
> 4 votes

---
Tags: computability, kolmogorov-complexity
---


# Question
Title: Big-O Notation for Menezes-Vanstone Elliptic Curve Cryptography?
I need someone help me about . how can compute time complexity for this algorithm (Menezes-Vanstone Elliptic Curve Cryptography). I have spent much time reading journals and papers but as yet have been unable to find any record of that performance complexity. It is known that the algorithm is encryption function is :

$C1 = k1 * m1$ mod p

$C2 = k2 * m2$ mod p

The decryption function is:

$m1 = C1 * k1^ {-1}$ mod p.

$m2 = C2 * k2^{ -1}$ mod p.

I think the encryption function it take $O(N)^{2}$

where $T(C1) = O(\log n)^2$ bit operations.

$T(C2) = O(\log n)^2$ bit operations.

and the decryption function it take $O(N)^{3}$. where

$T(m1) = O(\log n)^2 + T(k1^{-1})$.

$T(k1^{-1}) = O(\log n)^3$, by extend Euclid’s method.

$T(m1) = O(\log n)^2 + O(\log n)^3$ bit operations.

$T(m2) = O(\log n)^2 + O(\log n)^3$ bit operations.

Is that true?.

# Answer
Your bounds seem to be correct, assuming $n$ is the length of $p$, though writing $T(C1) = O(\log n)^2$ is wrong on two counts. First, it should be $O(\log^2 n)$ or $O((\log n)^2$) on the right. While $O(\log n)^2$ has the same meaning, it's not a "closed form", rather like writing $O(\sum\_{k=1}^n k)$ instead of $O(n^2)$. Second, $T(C1)$ looks like $C1$ is some parameter like the input length or the number of vertices, whereas you intended $T(C1)$ to be the time needed to compute $C1$. Better notation would be $T\_{C1}$, say, and you could include the input length $n$ as a parameter.

Moreover, note that there are faster integer multiplication algorithms, and some of them are used in practice in cryptographic contexts (not necessarily the ones which are asymptotically best). So you can get even better bounds on the running time depending on the implementation.

The reason you couldn't find the time complexity is that the algorithms use a constant number of two very common operations, namely multiplication and inverse modulo $p$, so the running times can be read immediately by experienced practitioners. This is even the case with more complicated operations such as modular exponentiation.
> 1 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: Kleene positive closure - help in proofing this claim
I just started a course called 'Automata and Formal Languages'. I'm having difficulty in proofing\disproofing this equality.

$ (L\_{1} \circ L\_{2})^{+} = L\_{1}^{+} \circ L\_{2}^{+} $

Where:

$ L\_{1} $, $L\_{2}$ are Languages.

$\circ$ is the concatenation operation between two languages.

$+$ is the Kleene plus closure defined by $\bigcup \_{i = 1}^{\infty }L^{i} $

I tried finding a counter example and also tried to formally proof but had no luck. Can someone please point me in the correct direction?

# Answer
> 0 votes
Let's use $A$ for $L\_1$ and $B$ for $L\_2$. If you unpack both sides, you get $$ (AB)^+ = AB + ABAB + ABABAB + \cdots \\ A^+B^+ = AB + AAB + ABB + AABB + \cdots $$ Perhaps this can give you some ideas.

---
Tags: formal-languages, closure-properties
---


title: How is a Turing Test defined?

text:
# Question
Title: How is a Turing Test defined?
Turing Test definition taken from wikipedia:

> The Turing test is a test of a machine's ability to exhibit intelligent behavior equivalent to, or indistinguishable from, that of a human. In the original illustrative example, a human judge engages in natural language conversations with a human and a machine designed to generate performance indistinguishable from that of a human being. All participants are separated from one another. If the judge cannot reliably tell the machine from the human, the machine is said to have passed the test. The test does not check the ability to give the correct answer to questions; it checks how closely the answer resembles typical human answers. The conversation is limited to a text-only channel such as a computer keyboard and screen so that the result is not dependent on the machine's ability to render words into audio

But how is a Turing Test defined?

What type of questions are considered to be so good that trick the human judge?

What and who defines a human judge suitable to be a judge? (for example if the judge is 5 year old wouldn't he be more easily tricked than a 50 year old computer scientist?)

All those chatbots are considered to pass the Turing Test? Most people are not sure if the chat bot is an actual bot or not.

# Answer
Although Alan Turing is of course a very important computer scientist, the Turing test is only superficially related to computer science. It is more related to philosophy.

As long as machines exist people have wondered whether it is possible to construct a machine that can think. But to answer this question we must first answer the question what it *means* -- what is *thinking*? Turing tried to circumvent this philosophical problem by changing the question a bit: the goal is no longer a thinking machine but a machine which is *indistinguishable* from a thinking being.

The Turing test was intended as a thought experiment to make the reader think about (artificial) intellingence in some way, but it appealed to a lot of people. So people started to organize Turing tests for real, and if you're doing real Turing tests, then of course you need real rules. Last year the Turing test organized by the University of Reading attracted a lot of attention because, according to the rules fixed for that particular Turing test, one computer program beat the judges. See here for the press release.
> 10 votes

# Answer
The Turing test highlights that there is no scientifically rigorous or quantifiable definition/ measurement of "general" intelligence in Turing's time, over a half century ago, and despite large advances in AI and new theories/ understandings of intelligence, neuroscience, psychology, etc, (and some claims otherwise) that gap in scientific/ human understanding still exists today. ie there is still no universal consensus or definitive theory. so the test sidesteps that issue (that it cannot be defined objectively so far) and treats it as a subjective question e.g. similar to questions of law, where "judges" make decisions/ rulings based on law, history/ precedent etc, or e.g. "prize contests" like the Nobel Prize that have scientific committees/ judges.

The Turing test shows some connection/ similarity to the psychology theory of behaviorism that emphasized (roughly) treating organisms as black boxes with senses and actions, and not speculating so much on their internal "state". however it has long been downgraded in importance in psychology.

The worlds current leading/ foremost Turing test is known as the Loebner contest by its main sponsor and this is usually the results reported in the media of chat-bots fooling humans etc., it is held annually, has particular conventions and rules set up by a committee, and has modest cash prizes.
> 1 votes

---
Tags: artificial-intelligence, turing-test
---


title: Recursive methods with stacks

text:
# Question
Title: Recursive methods with stacks
I'm doing some practice papers for revision for my finals and I came across this question:

> "This question is about recursion. A recursive method can always be implemented by an iterative method that uses a stack to keep track of intermediate values. Could the stack be replaced by, for example, a queue? Explain (no explanation means no marks)."

And their answer is: "No, a stack is needed to reuse the results of the recursive calls, which means we need a LIFO (i.e., reversed) order. A stack is perfect since each call can be interpreted as a push and each return as a pop of the result."

Now this is sort of confusing me. Couldn't you also say that a queue is also okay because each call can be interpreted as an append and each return can be interpreted as a serve?

# Answer
> 2 votes
If you are allowed to use one extra variable, then a queue can simulate a stack, so in this model a queue plus a single extra storage location will suffice.

The idea is to represent a stack, say $\[\ a\ b\ c\ $(top), as a queue, (tail) $\langle c\ b\ a\rangle$ (head). Then the operation $\mathtt{push(x)}$ would correspond to $\mathtt{enque(x)}$, so $$ \[\ a\ b\ c\quad \stackrel{\mathtt{push(x)}}{\longrightarrow}\quad\[\ a\ b\ c\ x $$ would be simulated as $$ \langle\ c\ b\ a \rangle\quad \stackrel{\mathtt{enque(x)}}{\longrightarrow}\quad\langle\ x\ c\ b\ a\ \rangle $$ The $\mathtt{pop()}$ operation is a bit more complicated. We first enqueue a marker, #, and then keep pulling elements off the head of the queue and placing them back on the tail until we come to the marker, indicating that the last element we pulled off corresponds to the top of the stack, so we don’t replace that element on the queue and we finish by removing the marker. In pseudocode, what we do is:

```
enque(#)
v = head()              ; save the head element
deque()                 ; remove it
while (head() != #)
   enque(v)             ; put the element back on the tail
   v = head()           ; save the next element
   deque()              ; remove it
deque()                 ; finally, remove the marker

```

For example, starting with $\langle c\ b\ a\rangle$, we'd have $$\begin{align} \langle\ c\ b\ a\ \rangle &\longrightarrow \langle\ \mathtt{\\#}\ c\ b\ a\ \rangle \\ &\longrightarrow \langle\ a\ \mathtt{\\#}\ c\ b\ \rangle \\ &\longrightarrow \langle\ b\ a\ \mathtt{\\#}\ c\ \rangle \\ &\longrightarrow \langle\ b\ a\ \mathtt{\\#}\ \rangle \\ &\longrightarrow \langle\ b\ a\ \rangle \end{align}$$

# Answer
> 0 votes
I have no idea what "intermediary values" means.

The stack is used to keep the execution environment of the caller, so that this execution can be resumed when the callee returns. Since the first call to return is the most recent call, the stack LIFO strategy is naturally adapted for that purpose, event though there may be other ways of encoding this behavior (actually one while loop and an infinite tape is enough according to Alan Turing and Alonzo Church).

This is so true that, when the recursive call is the last thing done by the caller (other than returning the result), the recursion can be replaced by an iteration very simply and without a stack. This is a standard "optimization" in compiling code (see Stackoverflow and Wikipedia).

---
Tags: computation-models, recursion, stacks
---


title: Decision Tree with Unbalanced Data

text:
# Question
Title: Decision Tree with Unbalanced Data
I have a data set with two classes: one class has at most 2000 members while the size of the second class is unlimited, though it is typically in the hundreds of thousands. I have read that it is problematic to use a decision tree to naively classify this data. My question is, how how I modify the data or the classification scheme to classify such data, using a decision tree at some point?

# Answer
Most common approach to such problems is some form of sub-sampling: randomly draw equal numbers of examples for each class. For model tuning you can use Stratified Cross-validation which in essence uses exactly this approach.

Other possibility is to weight the examples according to the ratio of class sizes. However, since on of your class has infinite number of samples this is impossible, unless you'll first employ sub-sampling anyway, at least for this infinite class. One example for decision tree context is modified information gain: "A Robust Decision Tree Algorithm for Imbalanced Data Sets" by Wei Liu, Sanjay Chawla, David A. Cieslak, Nitesh V. Chawla (PDF)
> 1 votes

# Answer
A common practice for unbalanced data is to give higher weight to the samples of the small classes, e.g., we can weight each sample by the inverse class frequency. You can train the decision tree classifier using the method described on this answer: http://www.csresearchers.com/?qa=12/using-sample-weighting-with-svm-decision-tree-classifiers

Basically if you are using using mutual information gain as the splitting function, then you can just use a weighted variant of the mutual information that you are using for splitting.
> 0 votes

---
Tags: machine-learning, data-mining, classification
---


# Question
Title: What is the standard way to choose a new leader in Multi-Paxos?
If you are unfamiliar with multi-Paxos or paxos, the following link might be a good refresher on it:

http://amberonrails.com/paxosmulti-paxos-algorithm/

or the paper by Leslie Lamport:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

I was thinking about multi-Paxos and what one should do to elect a new leader if one is to fail (or in general, just if we want to re-elect a leader). I know that Multi-Paxos normally operates under the assumption that there is a stable leader. However, it does not mean that the Leader never fails or that we might never want to change the leader. It might be uncommon, but we must do something so that the system can function properly in the case that we might want to change leader.

I was wondering, what was the standard way to handle leader failures in multi-Paxos?

I have thought of different ways to handle failures of leaders and also google them, but it's still not clear to me how it should be done.

Let me also clarify what I mean by multi-Paxos and clarify that its not the mechanism described in the following source:

http://www.ict.kth.se/courses/ID2203/material/Lecture\_11.\_Sequence\_Consensus.pdf

What I mean by multi-Paxos is the abstract idea of deciding a list of Paxos instances by a single leader. This leader sends a range of Paxos Instances it wants to prepare and thus, it can hear a single a single prepare acknowledgement for the whole range instead of one per Paxos instances. Therefore, we can avoid a round-trip and have a more efficient prepare phase. Furthermore, we can now send accept messages immediately for that range since we have already prepared the values.

However, I was a little unsure of how multi-Paxos normally handled choosing a new leader, if the current leader happened to die. Does it doing by running a Paxos instance? Also, how often does it change leader? Can we do a leasing mechanism that after some time t a leader is re-elected? If we do, can this only be achieved if one assumes clock synchronization? The article I initially posted talks about multi-Paxos but kind of skips the detail I am trying to address.

If anyone has better sources or an idea of how one should implement leader election, I would love to hear about it, because I am sure that implementing multi-Paxos is not a "new" problem and that is has been addressed before at some point (and I would rather avoid very very weird "ad-hoc" ideas...)

# Answer
> 2 votes
Using the terminology of the Leslie Lamport Paxos Made Simple a leader is implicitly chosen when phase 1 is executed and a node hears it has the highest proposal. The problem is not leader election as phase 1 is leader election; the trick is that any server can start and win a new election before the previous leader can make any progress. So rather than the challenge of getting a leader the challenge is not getting too many competing leaders duelling; yet not waiting too long before attempting to get a new leader. See this answer that quotes where the original Paxos papers talk about having a stable leader after a proposal has been accepted.

The raft paper has a lot of detail about leader timeouts. Basically you should have the leader send heartbeats. These can be no-op values as described in the Paxos Made Simple paper. If a follower does not get a message for a while it can timeout and propose. You add a bit of randomness to the timeout to try to prevent simultaneous proposers. You should respond with nacks as mentioned in the Papxs paper stating the higher promise value. That way if you do get simultaneously proposers the nacks will suppress candidates as only one candidate will get the highest number to a majority leading to nacks to the other candidates inside of one full round of phase 1+2 messages to the winner.

If servers stay up after the failure and the network stays stable a new leader should emerge promptly without too much delay or wasted messages on failed rounds due to duelling. The exact timeouts to set can be tuned to a given environment exactly as described in the raft paper.

---
Tags: algorithms, distributed-systems
---


# Question
Title: Find a collection of sets where each number from a given list is contained in a different set
I have a set of numbers S of cardinality N, and a collection of sets each containing some subset of S. The cardinality of each of these sets can be anywhere from 1 to N. The number of sets is variable, but is necessarily at least N.

e.g.

$S = \\{1, 2, 3, 4, 5, 6, 7, 8, 9\\}$

Sets:

$\\{3, 6\\}$ $\\{1, 2, 5\\}$ $\\{5\\}$ $\\{2, 6\\}$ $\\{2, 5\\}$ $\\{7, 8\\}$ $\\{1, 3, 5\\}$ $\\{7, 9\\}$ $\\{4, 8, 9\\}$ $\\{4, 5\\}$

I'm looking for an algorithm that will let me determine if there is a group of N sets, where each element of S is contained in a different set (the other elements in the set are irrelevant). Note that every element of S will always be represented at least once in the collection of sets (otherwise it is obvious that no solution is possible).

For this example, a possible solution is:

$\\{\mathbf{1}, 2, 5\\}$ $\\{\mathbf{2}, 5\\}$ $\\{1, \mathbf{3}, 5\\}$ $\\{\mathbf{4}, 5\\}$ $\\{\mathbf{5}\\}$ $\\{2, \mathbf{6}\\}$ $\\{\mathbf{7}, 9\\}$ $\\{7, \mathbf{8}\\}$ $\\{4, 8, \mathbf{9}\\}$

(**bold** numbers indicate the element of S for which each set was selected)

But if we were to exclude the set $\\{4, 5\\}$ from the pool of available sets, there would be no possible solution, despite every number being represented at least once in the available sets, and the number of sets still being at least N.

My N will not be more than 100, and the number of sets could be up to 100,000. The frequency of numbers in the sets will likely be very unevenly distributed, so, for example, there might be 95% of the sets that contain a 1, but only \<1% of sets that contain a 3.

Obviously the best performance is desirable, but I would appreciate any algorithm that is better than a brute-force search of every possible combination of sets.

# Answer
You are looking for a perfect matching. Consider the bipartite graph in which the left side consists of $N$ vertices corresponding to the numbers in $S$, and the right side contains a vertex for each set. Connect $x$ on the left to $y$ on the right if $x \in y$. Your problem is solvable if there is a matching that matches all of the left side. This is the classical problem of unweighted maximum matching in bipartite graphs, which has many efficient algorithms.
> 2 votes

---
Tags: algorithms, sets
---


title: Bayes nets - calculating probabilities

text:
# Question
Title: Bayes nets - calculating probabilities
Given a Bayesian network, say a -\> b -\> c, all binary random variables (I won't show the CPTs, assume they are given). You are told b and c are true. How do you calculate the P(a=True)?

# Answer
> 2 votes
Bayesian networks encode a factorization of the joint probability distribution of a set of variables. Specifically, each variable is conditionally independent of all its non-descendants given its parents.

The joint probability distribution can be written as:

$P(X) = \prod\_i P(X\_i|Pa(X\_i))$

where Pa(X) are the parents of X in the network.

You should be able to find the answer to your question by computing this quantity for your specific network and CPTs.

---
Tags: graphs, statistics, bayesian-statistics
---


title: Addressing mode

text:
# Question
Title: Addressing mode
I'm studying for an exam called Computer Fundamental, and started taking some previous exam but the given documents i had is way inadequate to solve all the question mentioned, like this one :

> Which of the following is the correct combination of variousaddressing modes? Here, X1 is an address which is stored in a program counter. X2is an address part of an instruction which is addressed by X1.X3is an address in which an operand needed to execute an instruction is stored. X4is a value in an index register. (X2) means the contents of location X2.

I tried to google "Addressing mode" and came up with some resources that i can't understand.

Can someone recommend me some link where i can get to know more about addressing mode so that i can answer this question?

Thanks alot!

I'm sorry for the tag, can't find some thing like "address" or "addressing mode"

# Answer
> 0 votes
I recommend you start by understanding what "direct addressing", "indirect addressing", "PC-relative addressing", and "indexed addressing" mean. With any luck, your textbook will explain those. If not, you should be able to find many explanations on the Internet. At last resort, check out the manual for your favorite processor.

# Answer
> 2 votes
The correct answer is b.

1.In direct addressing mode the effective address is equal to the address part of instruction so X3 = X2.

2.In indirect addressing mode the effective address is equal to the content of the address part of instruction so X3 = (X2).

3.In relative addressing mode the effective address is equal to the sum of the address part of instruction and the content of program counter so X3 = X1 + X2.

3.In indexed addressing mode the effective address is equal to the sum of the address part of instruction and the content of index register so X3 = X2 + X4.

If you wanna read more about addressing mode then refer this http://www.cs.iit.edu/~cs561/cs350/addressing/addsclm.html

---
Tags: memory-hardware
---


# Question
Title: Find all $k$ local maximums in an array of length $n$ in $O(n \log k)$ time
Given a sequence of numbers $a\_1, a\_2, ..., a\_n$, a number $a\_i$ is called the $k$ local maximum $\iff i \> k$ and $a\_i$ is the largest number among the $(k+1)$ numbers $a\_{i-k}, a\_{i-k+1}, ..., a\_i$. Given a sequence of $n$ numbers $a\_1, a\_2, ..., a\_n$, and an integer $k$, I am requested to find all $k$ local maximums in $O(n \log k)$ time.

At first, this seems like a dynamic programming problem, where I first calculate the solution for $k'=1$, and goes from there to $k'=k$, but this approach seems to take $O(nk)$ time.

I have found a possible solution to my problem here , but this also seems to take $O(nk)$ time for my problem, as

1. Build a Cartesian tree of the first $k$ elements. $O(k)$
2. Insert and check whether the $(k+1)$th element is the $k$ local maximum (also remove the leftmost element). $O(k)$
3. Repeat step two until reaching the end of the sequence.

The overall complexity seems to be $O(k) + O((n-k)k) = O(nk)$.

Any help is appreciated. Many thanks.

# Answer
Hint: Use some data structure that allows insertion, deletion, and search in logarithmic time to maintain a snapshot of the $k$ preceding elements, and use it to determine whether the next element is a $k$-maximum in time $O(\log k)$.
> 1 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, search-algorithms
---


# Question
Title: Why does an acceptor send the highest numbered proposal with number less than n as a response to prepare(n) in paxos?
I was reading the Paxos notes from yale from the following link:

http://pine.cs.yale.edu/pinewiki/Paxos

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

I was trying to better understand the revoting mechanism to avoid deadlocks in Paxos. The revoting mechanism is explained as follows in the article:

> The revoting mechanism now works like this: before taking a vote, a proposer tests the waters by sending a prepare(n) message to all accepters where n is the proposal number. An accepter responds to this with a promise never to accept any proposal with a number less than n (so that old proposals don't suddenly get ratified) **together with the highest-numbered proposal that the accepter has accepted** (so that the proposer can substitute this value for its own, in case the previous value was in fact ratified).

The bold section is the one that I was trying to understand better. The author tries to justify it with:

> "...so that the proposer can substitute this value for its own, in case the previous value was in fact ratified..."

But I didn't really understand why the proposer would want to ratify the previous value. By doing this, what crucial safety property is he guaranteeing? Why is he responding with that and not something else? Responding with the highest could be problem, right, since the current proposal would get lost?

# Answer
As I was writing my question I realized what I believe to be the correct answer and wanted to share it just in case someone else was wondering this step in Paxos, or maybe correct it if its not 100% correct (or clear).

Recall that, in Paxos, the actual goal is to achieve some consensus (agreement) on some value. The actual value is not very important as long as its from the valid set of values. However, we only care that our protocol somehow achieves *some* agreement. Thus, if we are a proposer and want to propose a value, what we really care is that some value is agreed amongst the processes participating in the protocol (since that the goal of a consensus algorithm, that some valid value is accepted). If for some reason, we were desperate for our value to be accepted at some point, we could eventually re-run a different instance of Paxos later (or more instances of Paxos until that value is chosen), so its ok to try to suggest the value later (to a different paxos instance) if we really need to (but that will be a different set of rounds of Paxos, starting with round zero and doing Paxos all over again). Its crucial to understand that suggesting the value to the same paxos instance is pointless since the point is that once paxos reaches consensus, that it sticks to it. We have to run paxos for a different set of values if we want our value to still be decided at some point.

But, the point of the step that "acceptors respond with the highest-numbered proposal that the current acceptor has seen", is to guarantee that if a value in the past (with lower sequence number) had been ratified, then why complicate agreement by considering a different value? It's easier to eventually agree at *some* value if we just keep that ratified value instead. Furthermore, and the more important reason is, imagine if we decided to discard the value we had ratified previously and instead ratify the new incoming one. Well, if we did that and update our state it could be very bad, because, one important property we wish our algorithm to have is, "once an agreement by majority has been reached, we wish it to be impossible for our system to change its mind" (because consensus has occurred already, so a change in mind is completely unnecessary). If we take this new (wrong) approach I have suggested, then that property could not hold. However, if instead, we always just respond with the highest ratified value, then the proposer on the other side is **bound** to learn the chosen value, if one has been chosen (if he queries some majority). Thus, the safe thing to do is, just send the proposer the current ratified value with the highest sequence number, that way, if a value was chosen, then the system is not able to change its mind if a consensus occurred (since its not necessary for it to change its mind since some value has already been accepted by some majority!). The whole point of consensus means that we agree on something, so changing the value can be viewed as breaking consensus.
> 1 votes

# Answer
Paxos is a collaborative peer-to-peer algorithm where successive leaders collaborate to complete each other's work.

Consider three nodes `A`, `B` and `C` playing every role (proposer, acceptor, learner) each in a separate rack with an interconnected network switch in each rack. Node `A` is leading in steady state. The link goes dark between nodes `A` and `B`. After a short while of no messages node `B` times-out and proposes. Node `B` issues a prepare to itself and node `C`, accepts its own proposal, and awaits the response from `C` to get a majority. If `C` reports a value then it was issued by either `A` or `C`, if `A` then it has accepted its own value as well as `C` so that value is fixed and that fact may have been communicated as such to the client. Node `B` must propose that value to make itself consistent with the other two nodes and the knowledge of the client.

Extend the example to five nodes by adding node `D` into the same rack as `A`, and node `E` into the the same rack as `B`. Again `A` is leading and the link between the racks of `A,D` and `B,E` goes dark. Once again node `C` is the single node in overlapping majorities. Node `B` times-out, proposes getting back a promise from itself, `E` and `C` with `C` once again returning a value. Whether the value is fixed on the other side of the partition depends on whether nodes `A,D` accepted the message. This cannot be determined be asking `C` what's going on with `A,D` as it may be that the switch in the rack `A,D` is dead and the client who issued the value is also in that rack so it may or may not have been told that the value is fixed. The only safe decision is to assume a majority was obtained and to complete the work and propagate the value reported by `C` across all reachable nodes.
> 1 votes

---
Tags: algorithms, algorithm-analysis, distributed-systems
---


# Question
Title: Why having a simple multiplication loop and very good avalanche isn't enough to produce well-distributed hash values?
Modern non-cryptographic 32- and 64-bit valued hash functions, for example, lookup3, MurmurHash3 and CityHash, have quite sophisticated loops, each iteration of which include many multiplications, XORs and rotates. Why this is needed, since there are good avalanche procedures (32 -\> 32 and 64 -\> 64 bits), which mix the bits effectively randomly. So, even if this simple loop:

```
hash = seed;
while (input_len >= 8)
    hash = hash * prime + fetch_8_input_bytes();
... do something for rest 0..7 bytes of input

```

produce whatever flawed, biased results for similar input (or a certain subset of input), finalizing avalanche:

```
return good_avalanche(hash)

```

"fixes" this.

The last deal is direct collisions, but they are often not so important, assuming hash function produce decently little collisions. I think the above multimplication loop does.

What I'm missing?

# Answer
> 2 votes
Insufficient mixing between incorporating blocks of the key radically increases the possibility of collisions - as an example, imagine a hash like the following -

---

```
uint32_t badHash(std::vector<uint8_t> key) {
  uint32_t hash = 0;
  for (size_t i = 0; i < key.size(); i++) {
    hash += key[i];
  }
  hash = SomeFunctionWithPerfectAvalanche(hash);
  return hash;
}

```

---

Despite the final avalanche, this function is no better than a checksum at producing a good distribution - it is trivially easy for adjacent blocks to cancel each other out. The situation isn't much improved by multiplying the key block by a prime, or performing any other mix to the key block - I can instantly generate collisions by taking two keys that collide under a simple checksum and then applying the *inverse* of the per-key-block mix to each block of the colliding pair.

A strong hash function has to perform enough mixing *between* adjacent blocks to ensure that small changes in the key are overwhelmingly unlikely to cancel each other out. Balancing the amount of work done in mixing each key block and in mixing the hash between key blocks is the tricky part of making a fast and robust hash function.

-Austin, author of MurmurHash

---
Tags: hash
---


# Question
Title: Algorithm to maximize $j-i$ subject to $A[j]>A[i]$
We want an algorithm that, given an array $A$ of length $n$ of integers (indexed by $A\[0\],A\[1\],\ldots,A\[n-1\]$, determine values $i\<j$ that maximizes $j-i $ subject to $A\[j\]\>A\[i\]$ (if such values $i,j$ exist.)

One possibility is as follows: First check whether the array is non-increasing. If so, no such $i,j$ exist. Else, iterate through the elements from front to back, keeping a running array which we append the current element if it is the minimum so far. This running array is decreasing, and we can use binary search to find the greatest element that's less than the current element. We update $j-i$ if it beats the previous maximum. This takes time $O(n\log n)$ because of binary search.

Is there a faster way, e.g., an $O(n)$ algorithm?

# Answer
As you mention, the candidate $i$s are those who are left-to-right minima, and they form a decreasing sequence. Similarly, the candidate $j$s are right-to-left maxima, and they form an increasing sequence going from right to left (so a decreasing sequence in the usual order). Now imagine keeping two points, one on the left-to-right minima, starting at the leftmost, and another on the right-to-left maxima, starting at the rightmost. Is there a way to traverse both lists in $O(n)$, answering your question on the way?
> 1 votes

---
Tags: algorithms, arrays
---


# Question
Title: Calculating the runtime for a recursive algorithm
If the runtime of a recursive algorithm could be expressed as

$T(n) = \begin{cases}O(1) & n \leq c \\ k * T\left(\frac{n}{k}\right) + \left(k + n * k \right)\end{cases}$

what would be the result of the asymptotic analysis (the Landau class)? $k \in \mathbb{N}, k \neq 0 $ is a constant value.

I would say that $k$ even if it is larger than $n$ is still a constant and therefore $T(n) = O(1) * T\left(\frac{n}{k}\right) + O(n) = T\left(\frac{n}{k}\right) * n $ for $n \> c$.

So I would say that the algorithm is $O(n * log\_k(n))$. Is this right? How could I prove this (formally correct)?

I have two main problems with this algorithm:

1) What is the runtime of $f(n) = (k + n * k)$? Can the $k$ be ignored so the runtime is $O(n)$?

2) I would like to use the Master theorem. I could see $T(n)$ in the form $a \cdot T\left(\frac{n}{b}\right) + f(n)$ with $a = b = k$. But then I need to check if $f(n)$ is $\in O(log\_b a) = O(log\_1 1) = ?$ This logarithmus is undefined, so can't I use the Master theorem?

# Answer
> 1 votes
Applying the master theorem will give you $T(n) = O\_k(n\log n)$, but the interesting part is the dependence on $k$. For simplicity, let's assume that $n$ is a power of $k$, and that instead of $k+nk = k(n+1)$ you have the cleaner $kn$ (it's not going to change the answer appreciably). Then you have $$ T(n) = kn + kT(n/k) = kn + kn + k^2T(n/k^2) = \cdots = kn\log\_k n + nT(1). $$ Assuming, for example, that $T(1) = 0$, then we get $$ T(n) = \frac{k}{\log k} n\log n. $$ For general $n$ you probably get $T(n) = \frac{k}{\log k} n\log n (1 \pm o(1))$ if you sweat. This gives you the dependence on $k$.

Since $k/\log k$ is increasing for $k \> e$, in this scenario the best integral choice for $k$ would be either $k = 2$ or $k = 3$ (as it happens, $k = 3$ is better), which is probably the point of the exercise.

# Answer
> 1 votes
1) $f(n) \in O(n)$, since $k$ is a constant.

2) If $a=b=k$, then $\log\_b a = \log\_k k$. Your specific case of $\log\_1 1$ only appears for $k=1$. And if we insert $k=1$ into the original recurrence we get $T(n) = T(n) + n + 1$, which does not make much sense as a description of a runtime. So it is sensible to simply exclude this case.

---
Tags: algorithm-analysis, runtime-analysis, landau-notation
---


# Question
Title: Average Case runtime for random choice search
Assuming we have an array with $n$ Elements and want to find an unique element by randomly (uniformly) choosing. What would be the average case runtime?

**My thoughts so far:**

The chance to find the element is $\frac{1}{n}$ in every step. Thus, to find the element after $k$ steps is $(\frac{1}{n})^k$. Now we can calculate the expected value and get $\frac{n}{(n-1)^2}$. But: that doesn't really make as it returns results $\< 1$ for $n \> 2$.

# Answer
> 1 votes
The probability you find the element in each guess is $1/n$. The number of guesses until you find it is a geometric random variable with success probability $1/n$, whose expectation is $n$.

Your formula is wrong – the probability to find the element after $k$ steps is $(1-1/n)^{k-1} (1/n)$.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, randomized-algorithms
---


# Question
Title: Generating all factorials up to $n$: faster than naive approach?
I'm aware of prime decomposition and parallel approaches to calculating one factorial; however, if I want the factorials of all numbers up to $n$, is there anything more efficient than the naive approach? As far as I can tell, at least the prime decomposition algorithms aren't any more useful here than the naive approach. Karatsuba multiplication may be useful, but that's something that would have to be dealt with in the data structure that handles arbitrarily large integers, if I'm not mistaken.

# Answer
Just make a big table once and for all. The function grows so fast that you never really need to have "random access" to arbitrary values.

Running `[factorial(n) for n in range(101)]` produces the following output after a few seconds. Do you really need anything more?

\[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000, 51090942171709440000, 1124000727777607680000, 25852016738884976640000, 620448401733239439360000, 15511210043330985984000000, 403291461126605635584000000, 10888869450418352160768000000, 304888344611713860501504000000, 8841761993739701954543616000000, 265252859812191058636308480000000, 8222838654177922817725562880000000, 263130836933693530167218012160000000, 8683317618811886495518194401280000000, 295232799039604140847618609643520000000, 10333147966386144929666651337523200000000, 371993326789901217467999448150835200000000, 13763753091226345046315979581580902400000000, 523022617466601111760007224100074291200000000, 20397882081197443358640281739902897356800000000, 815915283247897734345611269596115894272000000000, 33452526613163807108170062053440751665152000000000, 1405006117752879898543142606244511569936384000000000, 60415263063373835637355132068513997507264512000000000, 2658271574788448768043625811014615890319638528000000000, 119622220865480194561963161495657715064383733760000000000, 5502622159812088949850305428800254892961651752960000000000, 258623241511168180642964355153611979969197632389120000000000, 12413915592536072670862289047373375038521486354677760000000000, 608281864034267560872252163321295376887552831379210240000000000, 30414093201713378043612608166064768844377641568960512000000000000, 1551118753287382280224243016469303211063259720016986112000000000000, 80658175170943878571660636856403766975289505440883277824000000000000, 4274883284060025564298013753389399649690343788366813724672000000000000, 230843697339241380472092742683027581083278564571807941132288000000000000, 12696403353658275925965100847566516959580321051449436762275840000000000000, 710998587804863451854045647463724949736497978881168458687447040000000000000, 40526919504877216755680601905432322134980384796226602145184481280000000000000, 2350561331282878571829474910515074683828862318181142924420699914240000000000000, 138683118545689835737939019720389406345902876772687432540821294940160000000000000, 8320987112741390144276341183223364380754172606361245952449277696409600000000000000, 507580213877224798800856812176625227226004528988036003099405939480985600000000000000, 31469973260387937525653122354950764088012280797258232192163168247821107200000000000000, 1982608315404440064116146708361898137544773690227268628106279599612729753600000000000000, 126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000, 8247650592082470666723170306785496252186258551345437492922123134388955774976000000000000000, 544344939077443064003729240247842752644293064388798874532860126869671081148416000000000000000, 36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000, 2480035542436830599600990418569171581047399201355367672371710738018221445712183296000000000000000, 171122452428141311372468338881272839092270544893520369393648040923257279754140647424000000000000000, 11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000, 850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000, 61234458376886086861524070385274672740778091784697328983823014963978384987221689274204160000000000000000, 4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000, 330788544151938641225953028221253782145683251820934971170611926835411235700971565459250872320000000000000000, 24809140811395398091946477116594033660926243886570122837795894512655842677572867409443815424000000000000000000, 1885494701666050254987932260861146558230394535379329335672487982961844043495537923117729972224000000000000000000, 145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000000, 11324281178206297831457521158732046228731749579488251990048962825668835325234200766245086213177344000000000000000000, 894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000, 71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000, 5797126020747367985879734231578109105412357244731625958745865049716390179693892056256184534249745940480000000000000000000, 475364333701284174842138206989404946643813294067993328617160934076743994734899148613007131808479167119360000000000000000000, 39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000, 3314240134565353266999387579130131288000666286242049487118846032383059131291716864129885722968716753156177920000000000000000000, 281710411438055027694947944226061159480056634330574206405101912752560026159795933451040286452340924018275123200000000000000000000, 24227095383672732381765523203441259715284870552429381750838764496720162249742450276789464634901319465571660595200000000000000000000, 2107757298379527717213600518699389595229783738061356212322972511214654115727593174080683423236414793504734471782400000000000000000000, 185482642257398439114796845645546284380220968949399346684421580986889562184028199319100141244804501828416633516851200000000000000000000, 16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000, 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000, 135200152767840296255166568759495142147586866476906677791741734597153670771559994765685283954750449427751168336768008192000000000000000000000, 12438414054641307255475324325873553077577991715875414356840239582938137710983519518443046123837041347353107486982656753664000000000000000000000, 1156772507081641574759205162306240436214753229576413535186142281213246807121467315215203289516844845303838996289387078090752000000000000000000000, 108736615665674308027365285256786601004186803580182872307497374434045199869417927630229109214583415458560865651202385340530688000000000000000000000, 10329978488239059262599702099394727095397746340117372869212250571234293987594703124871765375385424468563282236864226607350415360000000000000000000000, 991677934870949689209571401541893801158183648651267795444376054838492222809091499987689476037000748982075094738965754305639874560000000000000000000000, 96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000, 9426890448883247745626185743057242473809693764078951663494238777294707070023223798882976159207729119823605850588608460429412647567360000000000000000000000, 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000, 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000\]
> 1 votes

---
Tags: complexity-theory, enumeration, factorial
---


title: Is $AlwaysHalt$ recursively enumerable?

text:
# Question
Title: Is $AlwaysHalt$ recursively enumerable?
I was doing some complexity theory exercices and I came over this one:

$AlwaysHalt = \\{R(M) | M$ halts with all $x \in \\{0,1\\}^\*\\}$

Is $AlwaysHalt$ recursively enumerable?

I would say YES and construct the following TM that accepts this language:

Enumerate all $x \in \\{0,1\\}^\*$ starting with length 1 and then increasing the length in every iteration and try the current $x$ with our TM $M$. We only care about those machines $M$ that halt with all words (we do not care if we do not halt, it would only mean that $R(M)$ is not in our language) so each $x$ will halt eventually. There is only countably many words $x \in \\{0,1\\}$ so we can do that.

However, I am not sure if this is a correct proof? Can I enumerate all words from and infinite (but countable) language to show that a TM behaves in some way on every single one of them?

# Answer
Consider the language $ALL\_{TM}$ (sometimes also called $L\_{\Sigma^\*}$) $$ALL\_{TM}=\\{\langle M \rangle: M \text{ is a TM and } L(M)=\Sigma^\*\\}$$

It is well known that $ALL\_{TM}$ is not RE (nor co-RE). See, e.g., this question (and search for other related questions on this site).

From this fact, it is easy to see that *AlwaysHalt* cannot be RE: a reduction $$ALL\_{TM} \le AlwaysHalt$$ is rather trivial.
> 2 votes

# Answer
I can answer a slightly easier version of this question.

Is $AlwaysHalt$ *lexicographically* recursively enumerable?

Let's say it is. Then we will have an enumeration machine $M\_E$ that generates all Turing machines that always halt in some order without repetition.

Let's use this enumeration machine to create another machine $M$ as follows

* On input $\<w\>$, convert $w$ into an integer $n$
* Use $M\_E$ to enumerate and get the n-th generated Turing machine. Let's call this $M\_n$
* Run $M\_n$ on $w$, when simulation halts, append another symbol into the output.

We can see that $M$ is well defined and always halts because enumeration always succeeds and simulation on an always-halt machine $M\_n$ always halts. It is easy to see that $M\_E$ generates infinitely many machines because the set of all machines that always halt is not finite. Thus for any number $n$, we can get an always-halt $M\_n$ from $M\_E$

This machine $M$ is also different from all other machines generated from $M\_E$ because of the appending of symbol in step 3. This means $M\_E$ does not generate $M$, so $M\_E$ does not generate all Turing machines that always halt.

From this we can conclude that $AlwaysHalt$ is not *lexicographically* recursively enumerable.

This argument can be extended into showing $AlwaysHalt$ is not recursively enumerable by recognizing that eventually for each machine generated by $M\_E$ there is eventually a number $n$-th for it. So the machine $M$ is still a always-halt machine and $M$ is still different from all machines generated by $M\_E$. So we can conclude that $M\_E$ does not generate an always-halt machine. This means $AlwaysHalt$ is not recursively enumerable.
> 1 votes

# Answer
You don't have a single yes/no answer that you can find eventually by enumerating and testing the inputs. So, I think it is not recursively enumerable.

Yes you can enumerate the inputs with a procedure like 0,1,00,01,10... However, you cannot say that this machine accepts this language even if you tested a certain number of inputs.

You can try to reduce the problem to the Halting Problem but this would only indicate that your problem is not decidable.
> 0 votes

---
Tags: computability, halting-problem, semi-decidability
---


# Question
Title: Is Newton's Method to compute the zeros of a function an algorithm?
Looking for Newton's method in Wikipedia, I read the following:

> In numerical analysis, Newton's method (also known as the Newton-Raphson method), named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots (or zeroes) of a real-valued function.

After describing briefly the method, the Wikipedia page adds:

> This **algorithm** is first in the class of Householder's methods, succeeded by Halley's method. The method can also be extended to complex functions and to systems of equations.

The emphasis on "algorithm" is mine.

I know Wikipedia is not always to be trusted, and I have been wondering whether Newton's method as described in Wikipedia does qualify as an algorithm, and what could be the reasons why it would qualify or not qualify.

The same question applies to other similar methods, such as the whole family of Householder's methods, also described in Wikipedia, but an answer in the Newton-Raphson case is enough.

Note, as a last remark, that the same question could be applied to Euclid's method to compute GCD as described in Wikipedia, though I expect the answer would be: "yes, because ...".

Related questions:

# Answer
> 3 votes
It's pretty clearly an algorithm according to my definition in the linked question. I think your real question is "what is the problem, if any, for which this algorithm is correct?" The answer would be something like "given some stuff and a number of iterations, output a value satisfying some condition with an accuracy related to the iteration count."

# Answer
> 1 votes
My definition of an algorithm is a finite sequence of operations provided by an abstract machine, where the operations are executed one after another in the order specified by the sequence. Different machines may provide different sets of operations, so the definition of an algorithm depends on the abstract machine. (Correct me if I am wrong).

When given a specific function to work on, the Newton's method is an algorithm. But Newton's method also needs the 1st and 2nd derivatives of the function, besides the function itself as inputs.

If the problem is to find the root of any function from a set of functions, then Newton's method must be augmented with some algorithms which can derive the 1st and 2nd derivatives of any function from the functional set. After that, we have an algorithm for solving the problem.

The cause of the differences between the above two cases is how specific a problem should be.

---
Tags: algorithms, computability, computation-models, real-numbers, computable-analysis
---


# Question
Title: How to calculate the miss ratio of a cache
I know how to calculate the `CPI` or cycles per instruction from the hit and miss ratios, but I do not know exactly how to calculate the `miss ratio` that would be `1 - hit ratio` if I am not wrong. I know that the hit ratio is calculated dividing hits / accesses, but the problem says that given the number of hits and misses, calculate the miss ratio.

My reasoning is that having the number of hits and misses, we have actually the number of accesses = hits + misses, so the actual formula would be:

> hit\_ratio = hits / (hits + misses)

So the miss ratio would be

> miss\_ratio = 1 - hit\_ratio

If my reasoning is correct, right?

What is the hit and miss latencies? Because I need them to calculate the `mean access time` using the hit and the miss ratios and the hit and the miss latencies (in cycles)...

# Answer
Yes. The *hit ratio* is the fraction of accesses which are a hit. The *miss ratio* is the fraction of accesses which are a miss. It holds that $$ \text{miss rate} = 1-\text{hit rate}.$$

The (hit/miss) latency (AKA access time) is the time it takes to fetch the data in case of a hit/miss. If the access was a hit - this time is rather short because the data is already in the cache. But if it was a miss - that time is much linger as the (slow) L3 memory needs to be accessed. The latency depends on the specification of your machine: the speed of the cache, the speed of the slow memory, etc.
> 1 votes

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: Application of cosine similarity to detect plagiarism
Can anyone tell me how using cosine similarity to see the correlation between two documents actually shows you if someone is plagiarising the other? I understand how cosine similarity works but don't understand how using this shows how closely related they are when the cosine deals with vectors and angles. How can this relate to a document?

# Answer
> 2 votes
Usually this would be used in conjunction with a bag of words model. You need to convert each document to a vector where the length of the vector is the number of words in the vocabulary. The entries in the vector correspond to the number of occurrences of each vocabulary word in the document. You can apply cosine similarity to these document vectors.

You should consider using tf-idf weighting to make sure that a small set of very common words doesn't end up dominating the distance computation. https://en.wikipedia.org/wiki/Tf%E2%80%93idf

# Answer
> 1 votes
I do **NOT** believe people use Cosine Similarity to detect plagiarism.

In information retrieval, using weighted TF-IDF and cosine similarity is a very common technique. It allows the system to **quickly** retrieve documents similar to a search query. This often works well, when the searched corpus is quite different.

However, in the case of detecting plagiarism. The searched corpus is very homogeneous from a bag of words perspective. This is because, say for an essay submission, ALL submitted essays cover the same topic so they have very similar bag of words. Also, since the same topic is covered in those essays, it is with almost certainty that those words with the highest weighted IDF such as proper nouns and uncommon words appear in most of the bags. Bag of words model is a very bad idea for this task. I would say if you run Cosine Similarity on TF-IDF vectors of the documents, there is a good chance that you find the entire class has similar essay.

I know for a fact that in order to check similarity, a much better algorithm exists. It is call 'Edit Distance', Levenshtein distance. This takes into account the order of the words in each documents. It runs slower in $O(n^2)$, but there are many ways to remedy this, and is often not a problem. This situation is different from the information retrieval situation.

For computer programs, the check can be done by turning the program into the symbolic representation. This is usually in form of a parsed tree. Then one can generate in-order, pre-order, post-order of the tree (or a set of major subtrees of this parsed tree such as of the main loop, main method etc..) and run 'Edit Distance' to compare similarity.

Remember that a TF-IDF approach does not take into account any structural property of documents unlike using parsed tree and edit distance as I mentioned above.

---
Tags: algorithms, data-mining, information-retrieval, comparison
---


# Question
Title: Prove the upper bound on $T\left(n\right)=T\left(\log_{2}n\right)+O\left(\sqrt{n}\right)$
I need some help with the following recursion:

$T\left(n\right)=T\left(\log\_{2}n\right)+O\left(\sqrt{n}\right)$

More specifically I wish to find and prove the upper bound on it.

I have a hunch it is $O\left(\sqrt{n}\right)$ but have gotten stuck proving it really is this.

Any help is appreciated

Thank you!

# Answer
> 0 votes
By simple substitution, you can see that $T(n) = O(\sqrt{n}) + O(\sqrt{\log n}) + O(\sqrt{\log\log n}) + \dots = O(\sqrt{n})$.

---
Tags: asymptotics, recurrence-relation
---


title: Efficient Array Normalization

text:
# Question
Title: Efficient Array Normalization
I want to normalize elements in an array. The solution I found is to take the sum of the elements and divide each element with this total. Can you find more efficient way of doing this?

The runtime I achieve is 2N. Any better idea?

```
normalize(array)
{
   sum = 0;

   for i = 0 to array.size() do
      sum += array[i];
   end

   for i = 0 to array.size() do
      array[i] /= sum;
   end
}

```

# Answer
Given that at least N "operations" are needed since each array element is affected, you can't get the number of operations down by much. It's not clear what your complexity measure exactly is – why is `sum += array[i]` a single operation? What about the loop? The actual CPU needs to increment `i` and compare it to `array.size()`, there are jumps involved and so on. The operation `sum += array[i]` is probably more than one instruction. Not to mention things you actually forgot to count, like `sum = 0`.

That said, I can't see how to improve on your algorithm, and I don't think it's possible, though as mentioned above, the notion of complexity is very shaky here, so perhaps there is a "trick" which will work under your complexity measure, whatever it is.
> 2 votes

---
Tags: algorithms, efficiency, arrays
---


# Question
Title: difference between lzw and huffman coding technique
What is the difference between the LZW and Huffman's coding of text compression ?

I've read this and this , but I'm not able to distinguish ?

# Answer
Lempel–Ziv encoding (or rather, encodings, since there are many different variants) and Huffman coding are very different algorithms.

**Huffman coding.** Choose a block length, usually one byte. For each possible value of the block, we choose some bit string, so that no bit string is a prefix of another one (this is known as a prefix-free code). This choice is either fixed (like the JPEG Huffman code, which while in principle adaptive, is often fixed to some standard code) or adaptive (chosen according to the actual text being compressed). Each block is encoded by its bit string, and the results are concatenated.

The name *Huffman code* proper refers to the optimal choice of code given a distribution on the value of the blocks. Huffman code satisfy the following optimality property: if the source being compressed consists of i.i.d. copies of some distribution, then as the block length tends to infinity, the average number of bits used to encode one copy is the entropy of the source.

**Lempel–Ziv encoding.** Here the idea is to separate the input bits (instead of bits, we can choose longer blocks) into pieces, where each piece consists of an earlier piece plus an additional bit at the end. For example, the input 01011100010 can be partitioned as (0)(1)(01)(11)(00)(010). The idea is to encode each piece by referring to an earlier piece, including the additional bit. For example, if we number the pieces from 1, 0 being the empty piece, then the previous example could be encoded as (0,0)(0,1)(1,1)(2,1)(1,0)(3,0).

There are many different variants of Lempel–Ziv encoding. In particular, in practice we don't keep all earlier pieces in memory, and there is some specific encoding for the pairs (p,b) encoding the earlier piece and the new bit. Lempel–Ziv encoding is optimal for ergodic sources – the expected length of the compressed stream tends to the entropy.
> 3 votes

# Answer
Both are lossless data compression algorithms.

I would say that the main difference is that Huffman's coding is a static technique$^1$ based on given or estimated probabilities that should be know a priori and produce a variable-length code.

LZW is in the same family of LZ77 and LZ78, it is "online" and it is based on a dictionary built during the encoding phase.

Here you can find more details.

<sub>$^1$ There is a dynamic version called dynamic Huffman coding</sub>
> 0 votes

---
Tags: data-compression
---


title: Ford-Fulkerson algorithm clarification

text:
# Question
Title: Ford-Fulkerson algorithm clarification
In the second edition of the book of Cormen "Introduction to Algorithms" appears the following example (in the left part is the residual network while in the right part shows the flow results):

I have a problem understanding the part (c). The augmenting path is $s\rightarrow v\_2\rightarrow v\_1\rightarrow v\_3\rightarrow t$ with a minimum weight of 8. This weight should be added or decreased in the right part of b:

$s\rightarrow v\_2$: it was 0 by default, so now it has 8/13

$v\_1\rightarrow v\_3$: it has 4/12 adding 8 we would have 12/12

$v\_3\rightarrow t$, it has 7/20; adding 8 holds 15/20

the problem is in the vertices: $v\_1\rightarrow v\_2$, for what I see it has only capacity 4 (b right part), so how to put the flow of 8 that it needs the procedure?. I see that at the end we finish up with a $v\_1\rightarrow v\_2$ with a value of 1/4, but I have my doubts how to get that result.

Is it that because $v\_2:v\_1$ has only capacity of 4, and I should put 8 of flow, that only 4 units pass through $v\_2:v\_1$ and the remaining 4 goes back from $v\_1:v\_2$? In that case it finds a value of 7/10; so it needs only 3 units giving us $v\_1:v\_2$ equals to 10, and because there is 1 unit remaining that goes from $v\_2:v\_1$ giving us 1/4?

Is that logic correct?

# Answer
Prior to step (c) there are 7 units flowing from $v\_1$ to $v\_2$. The augmenting path pushes 8 units of flow from $v\_2$ to $v\_1$: 7 of these cancel the existing flow from $v\_1$ to $v\_2$, and 1 unit now flows from $v\_2$ to $v\_1$.

More generally, the residual network shows you how much flow you can push in each direction. The edge $v\_2 \to v\_1$ has a capacity of 11, so you can push up to 11 (=7+4) units in this direction.
> 2 votes

---
Tags: algorithms, network-flow
---


# Question
Title: Proof of commonality of acceptors in majorities
In the Paxos consensus protocol, a fact that follows from its construction is "any two majority sets of acceptors will have at least one acceptor in common". This observation can be extended to any *N* majority sets of acceptors having either at least one acceptor in common, or acceptors that are distinctly present in each *N-1* sets of acceptors.

"Therefore if two proposals are agreed to by a majority, there must be at least one acceptor that agreed to both. This means that when another proposal, for example, is made, a third majority is guaranteed to include either the acceptor that saw both previous proposals or two acceptors that saw one each."

I have an intuitive understanding of why this is so (should be a simple pigeonhole principle application), but I am having difficulty proving this formally. I would like a formal proof.

# Answer
Let $A,B,C$ be the first, second and third majorities. If there are $M$ players, we can think of $A,B,C$ as subsets of $\[M\] = \\{1,\ldots,M\\}$ satisfying $|A|,|B|,|C|\>M/2$.

If $A,B$ were disjoint then $|A \cup B| = |A| + |B| \> M$, which contradicts $A \cup B \subseteq \[M\]$; that's why two majorities always have an acceptor in common.

If $C$ intersects $A \cap B$ then the third majority includes an acceptor that saw both previous proposals, so suppose that $C$ is disjoint from $A \cap B$. Define $$ A' = A \setminus (A \cap B), \\;\\;\\; B' = B \setminus (A \cap B) \\;\\;\\; U = \[M\] \setminus (A \cap B). $$ In order to show that the third majority includes two acceptors that saw one of the previous proposals each, we need to show that $C$ intersects both $A'$ and $B'$. If $C$ didn't intersect $A'$ then $|C \cup A'| = |C| + |A'| \> M - |A\cap B|$, which contradicts $C \cup A' \subseteq U$ since $|U| = M - |A\cap B|$; so $C$ must intersect $A'$. Similarly, $C$ must intersect $B'$.
> 3 votes

---
Tags: distributed-systems, voting, consensus
---


# Question
Title: Prove the equality of two concatenations of words
Let $x$, $u$, $v$, $w$, $y$, $x'$, $u'$, $v'$, $w'$, $y'$ be words. If

1. $y'x' = xy$
2. $y'u'x' = xuy$
3. $y'v'x' = xvy$
4. $y'w'x' = xwy$
5. $y'v'u'x' = xuvy$
6. $y'w'v'x' = xvwy$

all hold, then I need to prove that $y'w'v'u'x' = xuvwy$.

I'm a little confused how to prove this, How can I form $y'w'v'u'x'$ from the equations above?

# Answer
Suppose without loss of generality that $|y'| \geq |x|$. If we write $y' = xa$ then $ax' = y$. The equalities then become

1. $xau'x' = xuax'$.
2. $xav'x' = xvax'$.
3. $xaw'x' = xwax'$.
4. $xav'u'x' = xuvax'$.
5. $xaw'v'x' = xvwax'$.

Cancelling $x,x'$, we get

1. $au' = ua$.
2. $av' = va$.
3. $aw' = wa$.
4. $av'u' = uva$.
5. $aw'v' = vwa$.

Using $y' = xa$, (5), (1), and $y = ax'$, we get $$ y'w'v'u'x' = xaw'v'u'x' = xvwau'x' = xvwuax' = xvwuy. $$ This is close to what we want, only we got $vwu$ instead of $uvw$.

Plugging (2) into (4) gives $uva = av'u = vau' = vua$, and so $u$ and $v$ commute. Similarly, plugging (2) into (5) gives $vwa = aw'v' = wav'=wva$, and so $v$ and $w$ commute. The set of words commuting with $v$ forms a commutative monoid (since all are powers of some primitive word), and so $u$ and $w$ also commute. Therefore $vwu = uvw$, completing the proof.
> 5 votes

---
Tags: formal-languages
---


# Question
Title: Is "duplicate" in RPN enough for replacing variable binding in term expressions?
I try to work out some consequences of storing (or "communicating"/"transmitting") a rational number by a term expression using the following operators: $0$, $\mathsf{inc}$, $\mathsf{add}$, $\mathsf{mul}$, $\mathsf{neg}$, and $\mathsf{inv}$. Here $\mathsf{add}$ and $\mathsf{mul}$ are binary operators, $\mathsf{inc}$, $\mathsf{neg}$, and $\mathsf{inv}$ are unary operators, and $0$ is a $0$-ary operator (i.e. a constant). Because I want to be able to also store numbers like $(3^3+3)^3$ efficiently, I need some form of variable binding. I will use the notation $(y:=t(x).f(y))$ to be interpreted as $f(t(x))$ in this question. Now I can store $(3^3+3)^3$ as $$(c3:=(1+1+1).(x:=((c3\*c3\*c3)+c3).(x\*x\*x))).$$ If I stick to the operators $0$, $\mathsf{inc}$, $\mathsf{add}$, and $\mathsf{mul}$, this becomes $$(c3:=\mathsf{inc}(\mathsf{inc}(\mathsf{inc}(0))).(x:=\mathsf{add}(\mathsf{mul}(\mathsf{mul}(c3,c3),c3),c3).\mathsf{mul}(\mathsf{mul}(x,x),x))).$$ Using RPN with a "duplicate" operation written $\mathsf{dup}$ instead of variable binding, this becomes $$0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{dup}\ \mathsf{dup}\ \mathsf{dup}\ \mathsf{mul}\ \mathsf{mul}\ \mathsf{add}\ \mathsf{dup}\ \mathsf{dup}\ \mathsf{mul}\ \mathsf{mul}.$$

---

My question is whether it is always possible to replace variable binding by the "duplicate" operation. The binary operations ($\mathsf{add}$ and $\mathsf{mul}$) are associative and commutative, but it seems to me that even this is not enough for ensuring that variable binding can be completely eliminated. Take for example $$(c2:=(1+1).(x:=(((c2+1)\*c2)+1).(y:=(x\*x).((y+c2)\*y)))).$$ If I stick to the operators $0$, $\mathsf{inc}$, $\mathsf{add}$, and $\mathsf{mul}$, this becomes $$(c2:=\mathsf{inc}(\mathsf{inc}(0)).(x:=\mathsf{inc}(\mathsf{mul}(\mathsf{inc}(c2),c2)).(y:=\mathsf{mul}(x,x).\mathsf{mul}(\mathsf{add}(y,c2),y)))).$$ Using RPN with a "store" operation written $\mathsf{sto}(x)$ instead of variable binding, this becomes $$0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{sto}(c2)\ c2\ \mathsf{inc}\ c2\ \mathsf{mul}\ \mathsf{inc}\ \mathsf{sto}(x)\ x\ x\ \mathsf{mul}\ \mathsf{sto}(y)\ y\ c2 \ \mathsf{add}\ y\ \mathsf{mul}.$$ After eliminating $\mathsf{sto}(x)$ and $\mathsf{sto}(y)$ by $\mathsf{dup}$, this becomes $$0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{sto}(c2)\ c2\ \mathsf{inc}\ c2\ \mathsf{mul}\ \mathsf{inc}\ \mathsf{dup}\ \mathsf{mul}\ \mathsf{dup}\ c2 \ \mathsf{add}\ \mathsf{mul}.$$ Using explicit substitution to eliminate $\mathsf{sto}(c2)$, this becomes $$0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{dup}\ \mathsf{inc}\ \mathsf{mul}\ \mathsf{inc}\ \mathsf{dup}\ \mathsf{mul}\ \mathsf{dup}\ 0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{add}\ \mathsf{mul}.$$ My issue with explicit substitution is that it might lead to an exponential increase in the size of the expression. It's easy to see that expressions like $(3^3+3)^3$ or $((3^3+3)^3+3)^3$ can't be stored efficiently without something like $\mathsf{sto}(x)$ or $\mathsf{dup}$. Is there another way to eliminate $\mathsf{sto}(x)$, like an additional first-in, first-out queue? Or can one prove that an exponential blowup of the expression won't happen, if only explicit substitution and $\mathsf{dup}$ are "suitably" used together?

# Answer
> 2 votes
> Is “duplicate” in RPN enough for replacing variable binding in term expressions?

No, it is not strong enough. One can eliminate $\mathsf{dup}$ by replacing each sequence of $\mathsf{dup}$ by a sequence of $x$ preceded by one $\mathsf{sto}(x)$ operation. Since the single variable "$x$" is enough to eliminate all $\mathsf{dup}$ operations, any term expression which requires more than one variable to be stored efficiently can't be expressed (efficiently) using only $\mathsf{dup}$.

If the $\mathsf{inv}$ operation is omitted, then this whole intended representation by a term expression can be seen as a special case of the directed acyclic graph representation of a polynomial used in arithmetic circuit complexity. So the RPN stack from the question turns out to be just a representation of a tree. Now a directed acyclic graph can't be "emulated easily" by a tree, and especially a non-planar DAG will be "too difficult" for the $\mathsf{dup}$ operation.

In order to add the $\mathsf{inv}$ operation again, note that the ring of polynomials in $x\_1,\dots x\_n$ over $\mathbb Z$ is just the free commutative ring with generators $x\_1,\dots x\_n$. The corresponding free algebra with an $\mathsf{inv}$ operation would be the free commutative regular ring with generators $x\_1,\dots x\_n$. To be faithful to the canonical representation of the free algebra of a variety (equationally defined collection of algebras), the $\mathsf{inc}$ operation should be replaced by $1$.

---
Tags: formal-languages, pushdown-automata, stacks, term-rewriting
---


# Question
Title: Is Context Free Language closed under perfect shuffle?
Note that this is not shuffle but perfect shuffle, defined as follows:

Let $w = a\_{1}a\_{2} \ldots a\_{n}$ and $x = b\_{1}b\_{2} \ldots b\_{n}$ be two strings of the same length. Then the perfect shuffle of $w$ and $x$ is defined as $a\_{1}b\_{1}a\_{2}b\_{2} \ldots a\_{n}b\_{n}$.

So the question is: are context free languages closed under perfect shuffle?

# Answer
> 5 votes
Nope. Shuffle $\\{ a^n b^{2n} \mid n\ge1\\}$ with $\\{ a^{2n} b^n \mid n\ge1\\}$ .

---
Tags: formal-languages, context-free, closure-properties
---


# Question
Title: Hamming distance necessary for detecting d-bit error and for correcting a d-bit error
I am trying to understand what hamming distance of a code is needed to detect a d-bit error, or to correct a d-bit error.

This is what I have found around the web:

> If two codewords are Hamming distance $d$ apart, it will take $d$ one-bit errors to convert one into the other.
>
> 1. To detect (but not correct) up to $d$ errors per length n of a codeword, you need a coding scheme where codewords are at least $(d + 1)$ apart in Hamming distance. Then d errors can't change into another legal code, so we know there's been an error.
> 2. To correct $d$ errors, need codewords $(2d + 1)$ apart. Then even with $d$ errors, bit string will be $d$ away from original and $(d + 1)$ away from nearest legal code. Still closest to original. Original can be reconstructed

I have seen in my other post that, in the image, the calculation of the bits that can be detected and correct is done using the reversed formula of the above statements 1. and 2:

If we have a hamming distance of $d$, we can detect $d - 1$ errors (inverse of the formula 1.), so to detect a $d - 1$ error, we need a hamming distance of `d` (same thing said in another way). So for example, if we want to know what is the hamming distance required to detect a 4 errors, we just have to apply the formula 1.

$4 = d - 1$

$4 + 1 = d$

We need a hamming distance of 5.

So to find the hamming distance required to correct $d$-bit errors, we have to apply the formula 1. $2d + 1$, where $d$ are the bit errors.

Am I correct?

If yes, could you explain me what the second part of the point 2. is saying:

> Then even with $d$ errors, bit string will be $d$ away from original and $(d + 1)$ away from nearest legal code. Still closest to original. Original can be reconstructed

By `d-bit errors`, we mean d number of errors, right?

# Answer
The first step towards clarifying your confusion is *forgetting about the formulas*. You should be able to understand this material without looking at the formulas. You should even be able to develop the formulas on your own.

Now to the actual question at hand. Suppose we have a bunch of codewords, and every two are different in at least 10 positions. Suppose I send one codeword on the air, and an adversary corrupts (flips) $x$ bits. I claim that if he flips a small enough number of bits, then the receiver can detect that the adversary modified my codeword. The way she is going to do that is by noticing that what she got wasn't a codeword at all. If $x \< 10$ then flipping $x$ bits, the adversary cannot reach another codeword, since by assumption any two codewords differ in at least 10 positions. So if the adversary flips $x \< 10$ bits, the receiver will notice that the communication was corrupted on air. That's the meaning of "$d$-bit errors can be detected", where here $d = 9$.

Continuing the same scenario, the receiver isn't really interested in knowing whether some bits were flipped. Rather, she wants to know what the original codeword was. Suppose we can promise her that at most $y$ bits were flipped. When can she recover the original codeword? How is she going to recover the original codeword? Suppose that what she gets is the word $w$. She is going to look for the closest codeword $c$, and guess that the original codeword that was sent was $c$. When can we be sure that she is right? Suppose that the original codeword was actually $o$. So the distance (number of different positions) from $o$ to $w$ is at most $y$ (since we allowed the adversary to flip at most $y$ bits). As $c$ is the codeword closest to $w$, the distance from $c$ to $w$ is also at most $y$. So the distance from $o$ to $c$ is at most $2y$. Since both $o$ and $c$ are codewords, either they are the same (and we win – the receiver found the original codeword), or $2y \geq 10$, since any two codewords differ by at least 10 positions. As long as $2y \< 10$, this cannot happen. Reiterating, if $2y \< 10$, then even if the adversary flips up to $y$ bits on air, the receiver can know what the original codeword was by looking for the codeword closest to the word she received. That's the meaning of "$d$-bit errors can be corrected", where here $d = 4$.

More generally, if the minimum distance of the code – the minimum distance between two codewords – is $D$, then the first argument will work as long as $d \< D$, and the second as long as $2d \< D$. Given $d$, the minimum value of $D$ satisfying $d \< D$ is $D = d+1$, and the minimum value of $D$ satisfying $2d \< D$ is $D = 2d+1$. That's where the formulas come from. But don't memorize the formulas. Understand where they come from instead.
> 10 votes

# Answer
Yuval Filmus is absolutely right. You should not remeber the formula, but reinvent it when needed. It is really so simple.

Let me try explaining a different way.

The Hamming distance between two binary strings of the same length is the number of bit positions where the string differ. But the important point to remember is that it is a distance, pretty much like distances you measure on a road or on a map.

Changing a bit, either from 0 to 1, or from 1 to 0 is just like taking a step (using the *step* as unit of distance). Consider a code, composed of a collection of code words. Each codeword is just like a house. If your codewords are at a hamming distance $h$ from each other, it is like houses being at a $h$ steps distance from each other.

Now you are in house $u$, and you use your GPS to get the coordinates of your house, which you want to send to a friend who is to join you. But your GPS is not quite exact an gives you coordinates that may be off by $d$ step at most, which you send your friend, who goes to the coordinates he receives.

Then your two questions are:

1. what should be the minimal distance $h$ between houses so that your friend is sure to realise you transmitted incorrect coordinates.
2. what should be the minimal distance $h$ between houses so that your friend can furthermore be sure to find the right house by simply going to the house closest to the given incorrect coordinates.

It is quite clear that if the error is at most $d$ steps, and houses are at a greater distance $h$ steps, i.e. $d\<h$, then the coordinates you send cannot be the cordinates of another house as they are further apart than the maximum error. Hence, your friend will see no house at the given coordinates and will know there is an error. Since we consider only integer number of steps (or bits), $d\<h$ implies $d+1\leq h$, hence $h$ must be at least equal to $d+1$. If $d=4$, you indeed need $h=5$.

Now, if the error $d$ is always less than half the distance $h$ between two houses, the coordinates will always give a place that is closer to your house than to any other. Hence, if your friend knows that $2d\<h$, he know that the house closest to the coordinates he has is actually your house. Since we consider only integer number of steps, then $2d\<h$ implies $2d+1\leq h$, hence $h$ must be at least equal to $2d+1$. If $d=4$, you need $h=9$.

Now a codeword with an error of $d$ bits is exactly like the error of $d$ steps on the position of your house. And sending successive codewords is like moving from house to house, sending each time your coordinate with some error not exceeding a distance $d$ ($d$ steps off, or $d$ wrong bits), and asking your friend to retrace your route.

In "*Hamming distance*", the name *Hamming* just says that you are considering distances in number of different bits, rathen than distance in steps, or meters. But in both case it is a distance, with a unit of measure, and the possibility of comparing distances.
> 6 votes

---
Tags: error-correcting-codes
---


# Question
Title: What is the decision version of integer programming?
I don't know what is meant by "decision version of integer programming".

I know ILP, but this terminology has me confused.

# Answer
> 8 votes
It's the same as for all NP problems; the optimisation problem is

> Find a valid solution $s$ that minimises¹ $f(s)$!

and the corresponding decision problem is

> Is there a valid solution $s$ with $f(s) \leq k$?

You see that the former immediately solves the latter, and you can solve the former by using the latter with binary search over the set of feasible $k$.

---

1. Of course, you can have "maximise" here and "$\geq k$" in the decision version.

# Answer
> 2 votes
The decision version of any problem is "Is there a solution?"

---
Tags: terminology, decision-problem, integer-programming
---


# Question
Title: Given n strings, is one of them a substring of another?
Suppose we are given a collection of $n$ strings, $S\_1,\dots,S\_n$. I would like to know whether any of those strings is a substring of any other string in the collection. In other words, I'd like an algorithm for the following task:

Input: $S\_1,\dots,S\_n$

Output: $i,j$ such that $S\_i$ is a substring of $S\_j$ and $i\ne j$, or None if no such $i,j$ exist

Is there an efficient algorithm for this?

If we replace "substring" with "prefix", there is an efficient algorithm (sort the strings, then do a linear scan to compare adjacent strings; sorting will ensure that substrings are adjacent). But it seems more challenging to test whether any string is a substring of any other string. A naive algorithm is to iterate over all pairs $i,j$, but this requires $\Theta(n^2)$ substring tests. Is there a more efficient algorithm?

I guess we could call this "all-pairs substring testing", or something like that.

My ultimate goal is to prune the collection so no string is a substring of any other, by removing each one that is a substring of something else in the collection.

# Answer
You can build a suffix tree in linear time and check if there's an inner node that corresponds to a full string (constant time per node).

In more detail, assume we are given strings $s\_1, \dots, s\_n \in \Sigma^\*$.

1. Build a (generalised) suffix tree of $s\_1\\$\_1, s\_2\\$\_2, \dots, s\_n\\$\_n$ with $n$ pairwise distinct terminal markers $\\$\_1,\dots,\\$\_n \notin \Sigma$.

Using Ukkonen's algorithm, this can be done in linear time; linear in the sum of all string lengths.
2. Assuming that you label leaves with $(i,j)$ if they represent suffix $s\_i\[j..|s\_i|\]$ of $s\_i$, traverse the tree and find those $n$ leaves labelled $(i,0)$, i.e. the leaves that correspond to the full strings.

This takes time linear in the tree size, which itself is linear in the input size.
3. The descendant leaves of the parent of $(i,0)$ (which is reached by an edge labelled $\\$\_i$) represent all matches from the set; this follows from the basic invariant of suffix trees. Find any one match by descending to any leaf (but $(i,0)$).

This again takes linear time.

The distinct terminal markers are not really necessary; a single one used to terminate all strings is quite sufficient as long as you allow multiple labels per leaf.
> 6 votes

---
Tags: algorithms, strings, efficiency, substrings
---


# Question
Title: Semantic information collections on the web. (Semantic Wikipedia)
There are lots of technologies supporting semantic information markup even as wiki software.

I am wondering if there is any kind of broad information collection project like Wikipedia which features semantic markup of those information.

Google didn't bring up a project like this (only for very specific topics like software) or i just didn't find the right keyword.

Does anyone know about something like this?

# Answer
> 4 votes
DBpedia provides structured information from Wikipedia.

It uses RDF, and is one of the most known Linked Data datasets.

Also of interest (but not using information from Wikipedia) may be Freebase and OpenCyc.

---
Tags: reference-request, semantics, data-sets, knowledge-representation, ontologies
---


title: A Black Box Algorithm

text:
# Question
Title: A Black Box Algorithm
I'm taking an introductory quantum computations class and I am attempting to solve the following question(s), but we haven't touched on black box algorithms like this in class, and I honestly don't know how to solve the question at all. Would it be possible to help me through the steps?

**Question.** Consider the set of all functions $f:\\{0,1\\}^n \rightarrow \\{0,1\\}$ that are of the form $f(x\_1,x\_2,...,x\_n)=x{\_j{\_1}} \oplus x{\_j{\_2}} \in \\{1,2,...,n\\}$ with $j\_1 \neq j\_2$. Suppose we are given such a function as a black box (without information about $j\_1,j\_2$ and our task is to determine the set $\\{j\_1,j\_2\\}$.

**(a)** Show that any classical algorithm must male at least $\Omega(log(n))$ queries to f to solve this problem exactly. (We have used the $\Omega$ notation to give lower bounds, defined as following: Suppose $f(n), g(n)$ are functions form the positive integers to the real numbers. Then we say $f(n) \in \Omega(g(n))$ if there exists a positive, real c, and an integer $n\_o$ such that for all $n\>n\_o, f(n)\geq cg(n)$.

We are also given the following hint: Note that the data that a k-query classical algorithm obtains is a k-bit string. Next, consider how big k needs to be so that there are enough k-bit strings to be uniquely assigned to each $\\{j\_1,j\_2\\}$.

**(b)** Give a quantum algorithm in the black box model that solves ths problems exactly with a single query to f.

Any possible assistance would be amazing. Thank you!

# Answer
> 1 votes
Regarding part (a): just like in the classical lower bound for sorting, any black box algorithm which queries $f$ can be described as a binary decision tree whose leaves contain the correct answer $\\{j\_1,j\_2\\}$. Every pair $\\{j\_1,j\_2\\}$ is possible, so the tree must have at least $\binom{n}{2}$ leaves, hence it must have height at least $\log\_2 \binom{n}{2} = \Omega(\log n)$.

If you don't understand the argument, look up the $\Omega(n\log n)$ lower bound on sorting in the comparison model (also known as the decision tree model).

Can we do it with $O(\log n)$ queries? Suppose for simplicity that $n = 2^k$ is a power of $2$. If we feed the algorithm the bit string $x(b\_{k-1}\ldots b\_0) = b\_i$ then we get the $i$th bit of $j\_1 \oplus j\_2$, so using $\log\_2 n$ queries we can find $j\_1 \oplus j\_2$. Suppose for simplicity that $j\_1 \oplus j\_2 = 1$. If we feed the algorithm the bit string defined by $x(b\_{k-1}\ldots b\_1 0) = 0$, $x(b\_{k-1}\ldots b\_1 1) = b\_i$, then we recover the $i$th bit of $j\_1$ (or $j\_2$), so using $\log\_2 n - 1$ more queries, we recover $j\_1,j\_2$. In total, we used $2\log\_2 n - 1$ queries, which practically matches the lower bound $\log\_2 n + \log\_2 (n-1) - 1$.

Unfortunately I can't help you with part (b).

---
Tags: algorithms, quantum-computing
---


# Question
Title: Finding vertices of a maximum clique in polynomial time
Say you were given a black box that solves a clique problem in constant time.

You give the black box an undirected graph G with a bound k and it outputs either "Yes" or "No" that the graph G has a clique with at least k vertices.

How would you use this black box to find the vertices of a maximum clique in polynomial time?

# Answer
You first give it $(G,k)$, and if it says yes, you do the following. You pick an arbitrary vertex $v$ and call your oracle with $(G-v,k)$. If the oracle says yes, throw away $v$ and forget about it. If it says no, then $v$ is in every clique of size at least $k$. Output $v$ and decrease $k$ by one and lather, rinse, repeat.
> 2 votes

---
Tags: np-complete, clique
---


# Question
Title: Prove the existence of a proposition logical formula so that following conditions are fulfilled
For two proposition logical formulas $\phi$ and $\chi$ so that $\phi\implies\chi$ is generally valid. How can I prove that there is a formular $\psi$ with $var(\psi )\subseteq var(\phi )\cap var(\chi )$ so that $\phi\implies\psi$ and $\psi\implies\chi$ are generally valid?

# Answer
> 2 votes
The formula $\psi$ is called an *interpolant* and the method of finding such an interpolant is called *Craig interpolation*. On the Wikipedia article you can find more information about it, including a proof that interpolants always exist in propositional logic.

---
Tags: logic, propositional-logic
---


# Question
Title: If L is context-free, must FH(L) be context-free?
> Define $FH(L) = \\{x \in \Sigma^\* : \exists y \in \Sigma^\* \text{ with } |x| = |y| \text{ such that } xy \in L\\}$. In other words, $FH(L)$ is the set of first halves of even length strings in $L$. Given this, if $L$ is context-free, must $FH(L)$ be context-free?

Here's my attempt at a proof:

Since $L$ is a CFL, there exists a non-deterministic PDA recognizing $L$, $M = (Q, \Sigma, \Gamma, \delta, q\_0, Z\_0, F)$, where $\Sigma$ is the input alphabet, $\Gamma$ is the stack alphabet, and $Z\_0$ is the symbol representing the initial stack contents. Construct PDA $M'$ from $M$, with $M' = (Q', \Sigma, \Gamma, \delta', q\_0', Z\_0, F')$, defined as follows:

> $Q' = {q\_0'} \cup (Q \times \Gamma\_{\varepsilon}) \times (Q \times \Gamma\_{\varepsilon}) \times (Q \times \Gamma\_{\varepsilon})$.
>
> $F' = \\{\[(q,X),(q,X),(p,Y)\] : X,Y \in \Gamma\_\varepsilon \text{ and } p \in F\\}$
>
> $\delta'(q'\_0, \varepsilon, \varepsilon) = \\{(\[(q,X), (q\_0,Y), (q,X)\], \varepsilon) : q \in Q \text{ and } X,Y \in \Gamma\_\varepsilon \\} $
>
> $\delta'(\[(q,X),(p,Y),(r,Z)\], a, \varepsilon) = \\{(\[(q,X),\delta(p,a,Y), \delta(r,b,Z)\], \varepsilon): X,Y,Z \in \Gamma\_\varepsilon\ \text{ and } b \in \Sigma\\} $

The first component of a state in $Q'$ records the guessed state $q$ and does not change once it is initially recorded. The second element records what state we are in after having processed some prefix of the input x, starting from state $q\_0$, and the third element records what state we are in after having processed some prefix of the guessed $y$, starting from $q$.

I am not sure if this proof works, because I am a bit confused as to what to do with the stack for $M'$.

# Answer
The intuition developed in the comments is right. The answer is NO, there is a counter-example, a CFL for which the first halves are not CFL.

$L = \\{ a^m b^n c^n a^{3m} \mid m,n\ge 1 \\}$, over the alphabet $\\{a,b,c\\}$, from the answer on our sister site.

> Proof by Pumping lemma: pick $a^p b^p c^p \in \mathrm{FH}(L)$; pumping either destroys the "$b^n c^n$"- or the "first half"-property.

A slight adaptation of that language is $K = \\{ a^m b^n c^n \\#\\# a^{3m} \mid m,n\ge 1 \\}$, over the alphabet $\\{a,b,c,\\#\\}$. We can now "force" the point where the cutting site of the first half is and get another proof technique.

> Let $H = FH(K) \cap a^\*b^\*c^\*\\#$. This means we only consider first halves where the middle is exactly at the point between the two $\\#$-symbols. Thus. $m+2n+1=1+3m$, or $m=n$. Thus $H=\\{a^nb^nc^n \mid n\ge 1\\}\\#$. Now if $K$ is context-free then $H$ is context-free (via the closure property intersection by regular languages). This language is close to a standard non-context-free example $\\{a^nb^nc^n \mid n\ge 1\\}$. This in turn can be obtained by right quotient with $\\#$ which also preserves context-freeness.
> 9 votes

---
Tags: formal-languages, context-free, closure-properties
---


title: What is the definition of a problem

text:
# Question
Title: What is the definition of a problem
1. In computation theory, when talking about the computability and complexity of a problem, what is the definition of a problem?

How specific should a problem be? For example, can the followings all be function evaluation problems?

* evaluate $f$, where $f(x)=x^2, x \in \mathbb R$
    * evaluate any function in $\mathbb R^{\mathbb R}$.
    * evaluate any function in $Y^X$, where $X$ and $Y$ are any two sets.
2. Without restriction to the computability and complexity of a problem (or even without restriction to computation theory), how is a problem defined?

Can the above examples in 1 all be function evaluation problems?

Thanks.

# Answer
> 3 votes
A problem is anything you're trying to solve computationally. Problems typically specify an input and a desired output which, for most models of computation, will both be finite. Any statement of the form, "Given $X$, compute/evaluate/find/determine/decide whether/..." is a problem.

So, yes, all the things you describe in the question are problems. (Though, in the case where the input is the uncountable set $\mathbb{R}$, you need to be careful about how you specify what the input is.)

# Answer
> 2 votes
A computational problem can be viewed as an infinite collection of instances together with a solution for every instance.

For example, consider the problem of finding $f(x)=x^2$. Then $x$ is the input; $\<5\>$ is an input instance and $25$ is the solution to that. Therefore, This problem is defined by the pairs of input and answer, i.e. $f=\\{(1,1), (2,4), (3,9),...\\}$.

Note that you should not confuse the problem instance with problem. A problem instance is a given input of a problem; Therefore, a problem is a set of instances and their solutions.

More formally, we encode each possible pair $(instance, solution)$ using an alphabet (usually $\\{0,1\\}$). The set of such strings is called the language of that problem. Therefore, the problem becomes the membership of a string in that language.

---
Tags: complexity-theory, terminology, computability
---


# Question
Title: Show that a regular language L contains only palindromes if and only if all words of length at most 3n are palindromes
This is an extension of a previous question asked by a different user earlier:

> Let $x, u, v, w, y, x', u', v', w', y'$ be words satisfying
>
> 1. $y'x' = xy$.
> 2. $y'u'x' = xuy$.
> 3. $y'v'x' = xvy$.
> 4. $y'w'x' = xwy$.
> 5. $y'v'u'x' = xuvy$.
> 6. $y'w'v'x' = xvwy$.
>
> Then $y'w'v'u'x' = xuvwy$.

Now, using the above result, show that a regular language $L$ recognized by an NFA $M$ consists purely of palindromes if and only if $\\{x \in L : |x| \< 3n\\}$ consists purely of palindromes, where $n$ is the number of states in $M$. When I say that some language "consists purely of palindromes," I mean that every string in the language is a palindrome.

# Answer
> 2 votes
Suppose that $L$ satisfies your condition. We prove that $L$ accepts only palindromes by induction on the size of the word.

Let $a \in L$ be a word of length at least $3n$. Tracing some accepting computation of $a$ on the given NFA, some state must repeat at least four times, so we can write $a=xuvwy$ (where $u,v,w$ are non-empty), where the state after reading $x,u,v,w$ is the same, say $s$. So $u,v,w$ all have a computation that goes from $s$ to $s$. This implies that the NFA also accepts $xy,xuy,xvy,xwy,xuvy,xvwy$. By induction, all of these are palindromes, and so they satisfy the prerequisites of the lemma with $x',u',v',w',y'$ being obtained by reversing the unprimed string. The lemma then implies that $a$ itself is a palindrome.

---
Tags: formal-languages, regular-languages
---