title: Binary regular language?

text:
# Question
Title: Binary regular language?
Given $m,n\in\mathbb{N}$, finite alphabet $A=\\{a,b,c\\}$, and $L=\\{(a^m,a^n)\\}^\*=\\{(a^{mk},a^{nk})|k∈N\\}\subseteq A^\*\times A^\*$. Is this binary language $L$ regular over $A(2,\\$)$ (i.e. $\\{A∪\\{\\$\\}\\}\times \\{A∪\\{\\$\\}\\}\setminus \\{\\$,\\$\\}$)?

For example, is this binary language $L=\\{(a^3,a^7)\\}^\*=\\{(a^{3k},a^{7k})|k∈N\\}=\\{(a^3,a^7),(a^6,a^{14}),(a^{9},a^{21})(a^{12},a^{28})...\\}$ regular over $A(2,\\$)$?

An illustration of the difference between binary regular language and unitary regular language: Let $L=\\{(w,w')\mid w\in L^1,w'\in L^2\text{, and }L^1,L^2\text{ are unitary languages}\\}$ be a binary language, the length of $w$ and $w'$ maybe not all the same (suppose some $|w|\>|w'|$). Firstly, we must add \\$'s behind $w'$ such that all $|w|=|w'\\$...|$, then we get a new language $L^{\\$}$. And we will say $L$ is regular if and only if $L^{\\$}$ is regular (i.e. there is exist a finite binary automaton to recognize $L^{\\$}$).

And if the binary language $L$ can be showed as finite regular binary languages with the operations: union, intersection, complement, concatenation, $L$ is also regular.

# Answer
If I understand your question, you should consider $(a,aa)^\* = \\{ ( a^n, a^{2n} ) \mid n\ge 0 \\}$.

Perhaps the following notation helps $(a,aa)^\* = \\{ \left(\begin{array}{c}a^n\\ a^{2n} \end{array}\right)\mid n\ge 0\\}$. Interpreted over a two level alphabet this should be interpreted as $\\{ \left(\begin{array}{c}a\\ a\end{array}\right)^n \left(\begin{array}{c}\\$\\ a\end{array}\right)^n \mid n\ge 0\\}$.

Your turn to conclude.

Here I assume \\$'s can only be added at the end of the string.
> 1 votes

# Answer
If I have understood your notion of "binary language" (which is unfortunately not defined in the question), it appears that your question (in the special case $m=3,n=7$) is isomorphic to the following:

> Is the language $K^\\$ = \\{b^{3k} c^{4k} : k \in \mathbb{N}\\}$ regular over the alphabet $\\{b,c\\}$?

The answer to that question is "No". To see why, see the relevant reference questions here: Reference answers to frequently asked questions and How to prove that a language is not regular?.

**Explanation:** The isomorphism is as follows: $b=(a,a)$ and $c=(\\$,a)$. In other words, when you have the pair $(a,a)$ in the binary language, we can map this to a new symbol $b$ (in an ordinary, "unitary" language); when you have $(\\$,a)$ in the binary language, we can map it to a new symbol $c$; and when we have $(a,\\$)$, we can map it to a new symbol $d$. Now all words in the binary language $L^\\$$ are a concatenation of some sequence of $(a,a)$, $(\\$,a)$, and $(a,\\$)$, so we can map them to a word over the alphabet $\\{b,c,d\\}$.

Or, to put it another way: if I've understood the definition of a binary language correctly (which I might not have), you can think of the language $L^\\$$ as a binary language, or you can alternatively think of it as an ordinary, "unitary" language over the alphabet $\\{(a,a), (\\$,a), (a,\\$)\\}$.

When $m=3,n=7$, applying the above isomorphism to $L^\\$$ yields the language $K^\\$$ I defined above. Now standard methods suffice to determine whether $K^\\$$ is regular; indeed, for $m=3,n=7$, it is not regular.

**The general question:** You should be able to use similar techniques to answer your question for all $m,n$, on your own.

**Background on the site:** To give you a little bit of further explanation about this site: The expectation on this site is that you will work out the details of those on yourself. If your question can be answered using the techniques described there, then it is most likely not a good fit for this site. This site's primary purpose is to create an archive of content that will be useful for others. Also, we expect people to do some research/work on their own first before asking here. If the question can be answered using standard techniques (for proving that a language is not regular), then the question is not likely to be a good fit for this site, because it is likely too localized to be of use to others and because it does not meet the requirement for self-effort.

If this is not what you were asking, you'll need to edit the question to be more clear about what you are asking and to define all terms. You should also edit the question to show what you have tried so far.
> 1 votes

---
Tags: regular-languages, automata
---


# Question
Title: What future working opportunities do computer science students have?
If I am right students learning computer science at universities learn very theoretical kind of knowledge. A knowledge most of which (e.g. algorithm theory) can't be used to create everyday software (e.g. MS Word, IE, etc.).

What opportunities do computer science graduates have if they don't want to do research but rather work at some company where they can make use of what they have studied. (e.g. not writing MS Word)

In case of still not being clear enough, generally speaking, what I would like to know is what can a computer science gradute work?

# Answer
> 6 votes
First opportunities that come to my mind:

* data mining: it is used by e-commerce websites like Amazon to understand consumer behavior; also used by banks to calculate how likely the debt will be payed back;
* systems design, that can have high throughput: this is used by search engines like Google, but also in conterterrorism, and finance;
* geographic information systems: companies like TomTom and Foursquare, but also airports and airline companies
* performance analysis and finding bottle necks in systems: this is any company that has a big investment in ICT;
* embedded systems programming: Siemens, Ericcson and other companies and producers of embedded devices, also electronics for cars;
* hardware software interface in mobile systems: Motorola, Samsung, Apple, you name it;
* operating systems for mobile devices: Nokia and Microsoft are doing a lot of work here, also Google and Apple
* mathematical models in finance
* power grid networks management systems: Austin Energy, Etap

# Answer
> 8 votes
> If I am right students learning computer science at universities learn very theoretical kind of knowledge.

You are largely incorrect. A significant portion of most CS curricula includes hands-on, applied, practical programming, computer systems and software development exposure. The ACM publishes curriculum guidelines for ABET/CAC-accredited CS programs in the US. You should check their list of recommendations to get a more-or-less complete picture of what most CS programs worth the name cover.

> A knowledge most of which (e.g. algorithm theory) can't be used to create everyday software (e.g. MS Word, IE, etc.).

Algorithm theory is absolutely and vitally important for creating everyday software (such as MS Word, IE, etc.), specifically, for differentiating the software sufficiently to compete. To even write a web browser, one needs to understand HTTP, TCP, multithreading, parsing, etc.

> What opportunities do computer science graduates have if they don't want to do research but rather work at some company where they can make use of what they have studied. (e.g. not writing MS Word)

Any company that needs people to write software will need to hire somebody. Having academic credentials is a plus and a computer science degree is more applicable than just about any other option. More applicable, applied, practical options are typically viewed with some skepticism in the US since they're viewed as less rigorous (perhaps rightly so).

> In case of still not being clear enough, generally speaking, what I would like to know is what can a computer science gradute work?

Anywhere most graduates can work. Most of industry bases hiring decisions on individual circumstances; a CS major with experience in mechanical engineering could be hired as a mechanical engineer. A CS major with experience making puff pastry could be hired as a chef. Most CS majors would be well qualified to take jobs writing software since, by virtue of being a CS major, they have some experience writing software.

# Answer
> 4 votes
You are just wrong.

First of all I would hope that any four-year bachelor's degree (in any major) would teach basic critical thinking skills, which is really the prerequisite that employers (of any kind) are looking for.

Second of all I don't think you understand what software engineers actually do. (They design algorithms to solve real problems, and then make sure that the algorithms are implemented in reusable, testable, and composable ways.) I guarantee that majority of the programmers who work on the IE and MS Word teams have at least an undergraduate degree in computer science, and use *something* they learned in that degree every day.

Third of all, I don't think you understand what computer science programs actually teach. A computer science degree involves a lot more than a single course on complexity theory and a single course on computability theory. It involves *dozens* of courses all aimed at helping the student think *algorithmically*. All the computer science programs I've been associated with have required significant amounts of basic mathematics (calculus, statistics, linear algebra, analysis), and also things like digital, computer, operating system, database, networking, and compiler design. (And algorithm design.) Also linear programming, numerical analysis, signal and image processing, cryptography, machine learning, graphics.

I would never hire someone who didn't understand algorithms and complexity theory to write software (even web apps). (Or more accurately: I would hire just about any clear thinker to write software, but if they didn't already know how to design algorithms I would realize that I was going to have to invest a substantial amount of time and money teaching them to design algorithms.)

# Answer
> 2 votes
other answers are good, heres another angle. its worth pointing out that many elite corporations have very good, even world class R&D departments that have research quality on the level of, or exceed, top universities. in some cases it can be very theoretical but in other ways its a much more applied research related to building products, creating new applications, enhancing existing products, etcetera, ie a different applied/commercial/profitability focus vs university research. but notice also its usually only the much larger corporations that can afford it.

its possible to get internships or jobs in these areas & it can be a nice hybrid area of the \[at times abstruse/esoteric\] theory of academia vs the \[admittedly more narrow\] applied focus of corporations in general.

here are several companies renowned for world class CS research departments or at least some CS-focused R&D activity:

another alternative (as mentioned in comments) are tech startups which sometimes need specialized experience in advanced/theoretical CS technology. there are many examples of this but a few come to mind:

---
Tags: education
---


# Question
Title: Checking whether a digraph on $n$ vertices contains exactly $10\sqrt{n}$ strongly connected components in NL
I am studying now for a test in my complexity course. When I solved previous exams I saw the following question: Prove that the language $L$ of all directed graphs on $n$ vertices that contain exactly $10\sqrt{n}$ strongly connected components is in $NL$.

We saw in class that checking whether a directed graph contains exactly $C$ strongly connected components is in $NL$ for any fixed $C$, but I thought about this question the whole day and I absolutely have no idea how to do it in $NL$ when then number of SCC required is $10\sqrt{n}$. In the test this question was worth 20 points, so it shouldn't be too hard so I thought that maybe I am missing something important.

# Answer
Hint: Suppose $C\_1,\ldots,C\_\ell$ are the connected components and $v\_i$ is the minimal vertex in $C\_i$. Suppose further that $v\_1 \< v\_2 \< \cdots \< v\_\ell$. Show how to certify the fact that this data is correct in NL by keeping at most two of these indices at a time.

Here are some more details for a slightly simpler problem: verifying whether an undirected graph contains exactly $10\sqrt{n}$ connected components. We keep a counter $k$ of vertices accounted for. Suppose the vertices are numbered $1$ to $n$, and for $t$ going from $1$ to $10\sqrt{n}$, do the following:

1. Guess a vertex $v\_t \> v\_{t-1}$ (where $v\_0 = 0$).
2. For all $v \< v\_t$, verify that $v$ is not connected to $v\_t$.
3. For each $v \geq v\_t$, guess whether $v$ is connected to $v\_t$ or not, and verify the guess; for each vertex connected to $v\_t$, increase $k$.

If at the end $k = n$ then all vertices are accounted for, and the graph contains exactly $10\sqrt{n}$ connected components.

I leave the straightforward modification that solves the actual problem to the reader.
> 7 votes

---
Tags: complexity-theory, space-complexity, nondeterminism
---


title: Hierarchy of undecidable languages

text:
# Question
Title: Hierarchy of undecidable languages
Let us define two languages of Turing machines. $$ EQ\_{TM} = \\{\<M\_1,M\_2\> : L(M\_1) = L(M\_2)\\} $$ $$ ALL\_{TM} = \\{\<M\> : L(M) = \Sigma^\*\\} $$ It is easy to show that neither of the languages are in $RE \cup coRE$, and also it is easy to construct a reduction $ALL\_{TM} \leq EQ\_{TM}$.

I suspect that there is no reduction in the other direction, but I don't know how to prove it. Is there some sort of hierarchy of undecidable/non-recognizable languages that proves it?

# Answer
Let's fix the following definition for $L(M)$: it's the set of strings $x$ such that $M$ halts on input $x$.

Given machines $M\_1,M\_2$, consider a machine $M$ which accepts two inputs $x$ and $t$ and runs the following algorithm:

1. Run $M\_1$ on input $x$ for $t$ steps.
2. If $M\_1$ halted: run $M\_2$ on $x$.
3. Otherwise:
    1. Run $M\_2$ on input $x$ for $t$ steps.
    2. If $M\_2$ halted: run $M\_1$ on $x$.
    3. Otherwise: halt.

The machine $M$ rejects an input $x,t$ iff one of the machines $M\_1,M\_2$ accepts $x$ within $t$ steps and the other one rejects $x$. So $M$ accepts all inputs iff $L(M\_1) = L(M\_2)$.
> 5 votes

---
Tags: undecidability
---


title: Connection CSP and 3SAT

text:
# Question
Title: Connection CSP and 3SAT
I am interested in showing connection between CSP (Constraint Satisfaction Problems) as it's defined in CSP (definition with Constraint graph, sometimes called binary CSP) and 3SAT problem, when domain of CSP contains of 7 values.

The specific requirement is to show reduction from 3SAT to GAP CSP, when domain of CSP contains of 7 values.

Let try to reduce 3SAT to CSP, every clause of 3SAT can be represent as a vertex of CSP, and edges connect two clauses (vertices) when these clauses have at least one common variable. Set the values (assignments) from the domain of 7 values to every nodes such that to ensure the consistency (each variable get the same value in all clauses).

The problem is I cannot get what is so special about 7 values, apparently, we should have 8 different assignments to the vertices, how can I show that 7 values is enough?

In addition, I still don't have a good intuition about the constraints, for me constraints represented by the edge of the graph, and they ensure the consistency of the assignment (each variable get the same value in all assignments).

Having codded 3SAT as CSP how can we show the reduction to GAP CSP?

# Answer
Hint: There are seven satisfying assignments to the variables in each clause.
> 3 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: Complexity class that properly included in DLOGTIME
Is there any decision problem that is in a complexity class properly included in DLOGTIME? (except $O(1)$, of course)

If there is, can we create complete problems for DLOGTIME? So, can there be reduction by $O(\log(\log n))$ or smaller?

# Answer
Regan & Vollmer suggest in the conclusion of the linked paper that such classes are constructible (though fiddly). The paper itself is about LOGTIME, and mentions where changes have to be made to adapt the results to LOGLOGTIME, LOGLOGLOGTIME etc., but don't explicitly demonstrate the results.
> 3 votes

---
Tags: complexity-theory, time-complexity, complexity-classes
---


# Question
Title: Show that only a few multiples of .01 decimal are powers of 2
I am asking this to advance the argument that BigDecimal is better than float or double for representing exact amounts of currency.

Can someone refer me to a proof that between any two integers there are only four values that multiples of .01 and can be exactly represented in base 2? Or at least confirm I'm correct in my belief that it's true?

# Answer
> 2 votes
Hint: The four values are $25/100 = 1/4$ and its multiples.

If all you want to do is store an exact amount of currency, you can use an integer which represents the amount of cents. (This is known as fixed-point arithmetic.)

---
Tags: number-formats
---


# Question
Title: Proving that a language is not in P using diagonalization
Pardon me if i'm missing something which is very obvious here but i cant seem to figure it out.

$E=\\{ \langle M, w \rangle \mid \text{ Turing Machine encoded by $M$ accepts input $w$ after at most $ 2^{|w|}$ steps}\\}$

We have to prove $E\notin P$

The book (Papadimitrou, Elements of the ToC) assumes $E\in P$ and it constructs another language (a diagonal one)

$E\_1=\\{\langle M\rangle \mid \text{ Turing Machine encoded by $M$ accepts input $M$ after at most $ 2^{|M|}$ steps}\\}$

and takes its complement language $E\_1'$ and it follows that with the assumption $E\in P$ , it is true that $E\_1' \in P$

The question it then asks is the following: Say the polynomially bounded turing machine to decide $E\_1'$ is $M^\*$ then what happens when $M^\*$ is presented with $M^\*$ as an input? Now I understand it cant give an yes because that results in a contradiction. My doubt is where is the contradiction if the answer is no?

# Answer
The idea (which doesn't quite work) is that given that $E'\_1 \in P$, $M^\*$ runs in time at most $2^n$ on an input of length $n$ (that's not quite true). Given that, if $M^\*$ rejects $M^\*$ then by the definition of $E'\_1$, $M^\*$ accepts input $M^\*$ after at most $2^{|M^\*|}$ steps, which is a contradiction.

The other direction, which you were happy with, is problematic: if $M^\*$ accepts $M^\*$ then by the definition of $E'\_1$, $M^\*$ does not accept input $M^\*$ after at most $2^{|M^\*|}$ steps. That's not a contradiction since our assumption that the running time of $M^\*$ is $2^n$ was wrong - perhaps it's $2^{|M^\*|} n$. So you need to be more subtle - presumably Papadimitriou addresses this.
> 5 votes

---
Tags: complexity-theory, polynomial-time, check-my-proof
---


# Question
Title: What makes type inference for dependent types undecidable?
I have seen it mentioned that dependent type systems are not inferable, but are checkable. I was wondering if there is a simple explanation of why that is so, and whether or not there is there a limit of "dependency" where types can be indexed by values, below which type inference is possible and above which it is not?

# Answer
> 42 votes
For a rather simple version of dependent type theory, Gilles Dowek gave a proof of undecidability of typability in a non-empty context:

Gilles Dowek, *The undecidability of typability in the $\lambda\Pi$-calculus*

Which can be found here.

First let me clarify what is proven in that paper: he shows that in a dependent calculus **without** annotations on the abstractions, it is undecidable to show typeability of a term **in a non-empty context**. Both of those hypotheses are necessary: in the empty context, typability reduces to that of the simply-typed $\lambda$-calculus (decidable by Hindley-Milner) and with the annotations on the abstractions, the usual type-directed algorithm applies.

The idea is to encode a Post correspondence problem as a type conversion problem, and then carefully construct a term which is typeable iff the two specific types are convertible. This uses knowledge of the shape of normal forms, which always exist in this calculus. The article is short and well-written, so I won't go into more detail here.

Now in polymorphic calculi like system-F, it would be nice to be able to infer the type abstractions and applications, and omit the annotations on $\lambda$s as above. This is also undecidable, but the proof is much harder and the question was open for quite some time. The matter was resolved by Wells:

J. B. Wells, *Typability and type checking in System F are equivalent and undecidable*.

This can be found here. All I know about it is that it reduces the problem of semi-unification (which is unification modulo instantiation of universal quantifiers, and is undecidable) to type checking in System F.

Finally it is quite easy to show that inhabitation of dependent families is undecidable: simply encode a Post problem into the constructor indices. Here are some slides by Nicolas Oury that sketch the argument.

As to whether there is a "limit", it much depends on what you are trying to do with your dependent types, and there are many approximations which try to be either decidable, or at least close enough to be usable. These questions are still very much part of active research though.

One possible avenue is the field of "refinement types" where the language of expression of type dependencies is restricted to allow for decidable checking see, e.g. Liquid Types. It's rare that full type inference is decidable even in these systems though.

---
Tags: undecidability, type-theory, type-inference, dependent-types
---


# Question
Title: What is the proper runtime for visiting all outgoing edges in an adjacency list?
Suppose that we have a directed graph $G = (V, E)$ represented as an adjacency list. Suppose that we want to list all of the edges incident to some node $v \in V$. We can do this by iterating over all the elements in the adjacency list.

My question concerns the runtime of this operation. Is it proper to say that the runtime is $\Theta(deg^+(v))$ (since the runtime is a linear function of the outdegree of $v$)? Or should it be $\Theta(1 + deg^+(v))$, since even if $deg^+(v)$ is zero, there is some amount of work that's still done? Or are both of these terminologies incorrect because there is no underlying variable $n$ for which we could apply the formal definition of $\Theta$?

Thanks!

# Answer
You're right that $\Theta(\deg^+ v)$ is a bit sloppy, but it is usually understood that $\Theta(\deg^+ v)$ is actually $\Theta(1 + \deg^+ v)$. Perhaps it's better to use the more accurate $\Theta(1 + \deg^+ v)$.

You're also right that more formally a $\Theta(\cdot)$ notation should state the underlying variable, but here there is only one variable and so no confusion can arise. Also, since $\deg^+ v$ is always non-negative, the simpler definition of $\Theta(\deg^+ v)$ - there exists $C \> 0$ such that the running time is at most $C \deg^+ v$ - is unambiguous. That's also how we should understand expressions like $\Theta(n + m)$, where the two variables $n,m$ are independent.
> 4 votes

---
Tags: terminology, graphs, asymptotics
---


title: Multicommodity circulation formulation

text:
# Question
Title: Multicommodity circulation formulation
On the circulation problem page on wikipedia, the multicommodity circulation problem formulation seems to be insufficient, since we can just set all but one flow to $0$, and reduce it to a circulation problem.

I can't find any concrete description of multicommodity circulation problem to verify the correctness. There is only one paper I can find and it's behind a pay wall.

Here is a formulation I thought to make more sense:

Let $G=(V,E)$. $l\_i,u,c\_i:E\to \mathbb{R}$ for $1 \leq i\leq n$. We want to find a sequence of flow function $f\_i$, such that:

$$ \begin{align} \text{min} & \sum\_{(v,w) \in E} c\_i(v,w)f\_i(v,w) \\ \text{s.t.} & \sum\_{(v,w) \in E} f\_i(v,w) = 0 \text{ for } 1 \le i \le n, v \in V, \\ & l\_i(v,w) \leq f\_i(v,w) \text{ for } 1 \le i \le n, (v,w)\in E\\ & \sum\_{i=1}^n f\_i(v,w) \leq u(v,w) \text{ for } (v,w)\in E\\ \end{align} $$

Is this a formulation of multicommodity circulation problem?

# Answer
> 3 votes
I think the reference for many optimization and structural problem is Schrijver's book:

Combinatorial Optimization - Polyhedra and Efficiency

In the case, you do not have access to the book you can find his lecture notes on disjoint paths, but it's not complete, and is not comparable to the book.

Circulation is just a general definition and it's not important alone, it's important with given underling context, e.g here difference between the muticommodity circulation is just we have multiple circulation (no matter if all of them are 0), but if we want to use it for the muticommodity integer flow problem we cannot reduce it to the normal flow unless $P=NP$.

As a side note: In the Schrijver's book circulation does not include lower bound or upper bound, just flow's conservation rule holds.

This is the definition of circulation in that book:

**Circulation:**

> Let $D = (V,A)$ be a digraph. A function $f : A \rightarrow R$ is called a circulation if
>
> $f(\delta^{in}(v)) = f(\delta^{out}(v))$ for each vertex $v \in V$ . So now the flow conservation law holds in each vertex $v$. (in page 171)

And:

> $δ^{in}(v)$ := set of arcs entering $v$,
>
> $δ^{out}(v)$ := set of arcs leaving $v$. (in page 29)

The corresponding problem is defined as follow:

**Circulation Problem:**

> **Input:** Let $D = (V,A)$ be a digraph and let $d, c : A → Q$ with $d ≤ c$.
>
> **Question:** Is there a circulation $f$ satisfying $d ≤ f ≤ c$. (page 175, with a little variation).

But the minimum-cost circulation problem is as follow:

**Minimum-Cost Circulation Problem:**

> **Input:** A digraph $D = (V,A)$, a *demand* function $d : A → Q$, a *capacity* function $c : A → Q$, and a *cost* function $k : A → Q$.
>
> **Question:** Find a circulation f subject to $d ≤ f ≤ c$, minimizing $\text{cost}(f)$. (Page 177).

Finally I should mention that, I didn't see the multicommodity circulation definition (or corresponding problem) explicitly, and in my opinion, as I mentioned at start is not important alone. But I do agree with the owner of problem, that wikipedia's definition is not good, and the definition provided in this question is better and more precise than the wiki's.

---
Tags: reference-request, optimization, network-flow
---


# Question
Title: A text-classifier that explains its decisions
I am building a text categorizer for short sentences. In addition to telling the user "the category of the text you entered is C", I want to be able to explain why I made this decision, in a short and understandable way. For example, I don't want to tell the user "I put your sentence into a complex 3-layered neural network and that's the answer that scored the best"; I want explanations such as "Your sentence contains the words U, V and W, that are characteristic of this category, because of sentences such as X, Y and Z that appeared in the training data".

My question is: what classification algorithms are best suited for such application?

k-nearest-neighbours seems like a good candidate, because I can tell the user "Your sentence has category C because it is similar to sentences X, Y and Z that have the same category. But its performance on text categorization problems is known to be poor. I am looking for a classifie that balances performance with explanation ability.

EDIT: After spending a lot of time looking for such a classifier, I started to build a machine-learning library called limdu, that allows the classifiers to explain their decisions. It is still under development, but, it has already helped me explain to myself and my colleagues why our classifiers fail so often...

# Answer
> 7 votes
Although it performs poorly on text classification tasks, if you want a clear explanation of the classification reasoning, a decision tree would be your best option as it provides clear rules for how an instance is classified. A trace of the tree would provide the determining values and by analyzing the instances close to the root node, you might even be able to determine which attributes where more significant in the classification.

Another option would be to use a Naive Bayes classifier, which performs better for text mining tasks and would give you a comprehensible evaluation scheme based on probabilities that you could use to generate the "why" you're looking for, even providing an indication of which attribute values were more important than others in making the determination.

Support Vector Machines, specifically Sequential Minimum Optimization (SMO), seem to work well with these tasks and likewise provide indication of the values used to make the classification in the form of attribute weights and support vectors, but I think you may have a harder time making explicit how these weights and vectors influenced the overall classification decision.

Good luck with your project! Sounds very interesting.

# Answer
> 3 votes
I vaguely recall that Peter Norvig had an implementation of MYCIN, a medical diagnosis expert system, written in LISP in his book *Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp*, which did exactly this.

Maybe that is a good place to start your research. You will find the source code online, together with a rule base, however, I strongly recommend reading the text and not try to understand it from the source code alone.

You can also head directly to the page for Emycin (my emphasis),

> Emycin is an **expert system** shell, a framework for building programs that record the knowledge of domain experts and use that knowledge to help non-expert users solve problems. It provides an interface that helps experts define data types and rules, a backwards-chaining reasoning algorithm (similar to Prolog, but with key differences), **a mechanism for dealing with uncertainty, and facilities for introspection that permit users to learn what the system knows and what it is doing**.

---
Tags: machine-learning, classification
---


# Question
Title: How to do pixel array rotation whose angle not a multiple of 90 degree?
It is easy to rotate pixel array if the angle is a multiple of 90 degree.

For example, (quote from *Computer Graphics with OpenGL*)

> We can rotate a two-dimensional object or pattern 90' counterwise by reversing the pixel values in each row of the array, then interchanging rows and columns.

But I could not understand how to rotate pixel array when the angle is not a multiple of 90 degree from the textbook.

> Each desitination pixel area is mapped onto the rotated array and the amout of overlap with the rotated pixel areas is calculated.

Why does this means?

# Answer
> 1 votes
1. Choose an origin for your coordinate system. A corner or the middle of the image is typical.
2. For each pixel, compute its (x, y) coordinates relative to the origin.
3. For each pixel, compute its new coordinates when keeping its distance from the origin the same and adjusting its angle by the desired rotation.
4. In a temporary buffer, copy pixels from the original image using the new coordinates.
5. Go over the temporary buffer, and for each pixel that wasn't assigned a color, interpolate the colors from surrounding pixels.

There are some details glossed over there, but the basic idea is sound. Coordinate transformations can be accomplished using basic trigonometry.

---
Tags: graphics
---


# Question
Title: Find node with key of at least n in a binary search tree
Working on a project for my Data Structures class.

I've implemented a Red/Black tree in Java. One of the operations required of the data structure is "find a node which has a key of at least n". The leaves of the tree are the sentinel node.

My initial thought was using the regular search with modifications:

1. Search for a node with key == n
2. If result == sentinel, call getSuccessor on parent until a node with key \> n is found

I -think- this is $O(m\*lgm)$ ($m$ being number of nodes in the tree) at the worst case.

Inspired by the getSuccessor code - if right subtree of target node is empty, find smallest ancestor which has a left child also an ancestor - was wondering if there is a better way to do this.

Would appreciate any advice; thanks.

# Answer
Try a binary search tree. The leaves will be in sorted order. In $O(\lg m)$ time, you can either find a node with value $n$, or you can find the next node larger than $n$.

EDIT: If you don't find the $n$ valued node you'll reach a $nil$ node, WLOG if you reach it from the right then it's successor is the consecutive node, if you reached it from the left then the first successor in the tree of the leaf you reached which is on the right of where you reach it from is the consecutive node. Each traversal is no more than the height of the tree so you're still within $O(\lg m)$
> 0 votes

---
Tags: data-structures, binary-trees, search-trees
---


title: What are lattices used for?

text:
# Question
Title: What are lattices used for?
Wikipedia says:

> Complete lattices appear in many applications in mathematics and computer science

Is it just referring to the fact that the standard Boolean algebra used in computation is a complete lattice? Is there anything we gain by working at the abstract level of lattices instead of with Boolean logic specifically?

A google search doesn't find much on the subject, but I'm probably using the wrong keywords.

# Answer
> 12 votes
See for instance this book: Lattice Theory with Applications, Vijay K. Garg, which starts off as follows:

> Partial order and lattice theory now play an important role in many disciplines of computer science and engineering. For example, they have applications in distributed computing (vector clocks, global predicate detection), concurrency theory (pomsets, occurrence nets), programming language semantics (fixed-point semantics), and data mining (concept analysis). They are also useful in other disciplines of mathematics such as combinatorics, number theory and group theory. In this book, I introduce important results in partial order theory along with their applications in computer science. The bias of the book is on computational aspects of lattice theory (algorithms) and on applications (esp. distributed systems).

The book doesn't seem to mention recursion theory (theory of computable sets), but from Wikipedia's article on Computability theory, we see:

> When Post defined the notion of a simple set as an r.e. set with an infinite complement not containing any infinite r.e. set, he started to study the structure of the recursively enumerable sets under inclusion. This lattice became a well-studied structure. Recursive sets can be defined in this structure by the basic result that a set is recursive if and only if the set and its complement are both recursively enumerable. Infinite r.e. sets have always infinite recursive subsets; but on the other hand, simple sets exist but do not have a coinfinite recursive superset. Post (1944) introduced already hypersimple and hyperhypersimple sets; later maximal sets were constructed which are r.e. sets such that every r.e. superset is either a finite variant of the given maximal set or is co-finite. Post's original motivation in the study of this lattice was to find a structural notion such that every set which satisfies this property is neither in the Turing degree of the recursive sets nor in the Turing degree of the halting problem. Post did not find such a property and the solution to his problem applied priority methods instead; Harrington and Soare (1991) found eventually such a property.

Further reading, see the blog post Lattice Theory for Programmers and Non Computer Scientists.

# Answer
> 4 votes
I have since found the free paper Ordered Sets and Complete Lattices: A Primer for Computer Science, for other interested readers.

# Answer
> 3 votes
Regular edge labelings and related structures form a distributive lattice (see for example here). This can be exploited to search efficiently through the space of all regular edge labelings for a given graph (see here) . As an application you can determine if a map can be drawn as cartogram with a certain area assignment for the faces.

# Answer
> 3 votes
The references given by Pål GD are indeed very appropriate. So let's focus on a minor side issue in this answer instead. I have done some reading on lattices some time ago, and started to wonder whether the notion of semilattice wouldn't have been more appropriate for applications. You might object that a complete semi-lattice is automatically also a lattice, but the homomorphisms and substructures (i.e. sublattices and subsemilattices) are different.

I first encountered (semi-)lattices when studying semigroups, as the commutative idempotent semigroups. Then I thought about the relation between hierarchic structures and lattices, and noticed that a tree is naturally also a semilattice. Then I found lattices in security contexts and in program analysis, and always it seemed to me like the semilattice structure was the really important part, and the lattice was just taken because it could be obtained "for free". Even for a Heyting algebra, there is an asymmetry between conjunction and disjunction which suggests to me that the asymmetric semilattice model might provide more insight here than the symmetric lattice model.

# Answer
> 3 votes
a very important, but not-so-famous case—it is well known among theorists but not so well known in the sense of being taught to undergraduates—of the use of a lattice is to prove superpolynomial lower bounds on the size of monotone circuits computing Clique for which Razborov won the Nevanlinna prize. the original construction is very technical however and later constructions eg Berg/Ulfberg simplify the framework without the reference to lattices.

so in this case lattice theory was used as a framework to discover the original proof but later formulations tended to not refer to it directly as a conceptual simplification.

so yes lattices may be regarded as a more exotic mathematical object \[Razborov has spoken elsewhere of his style of applying advanced mathematics to CS\] that might correspond to some other more "concrete" object in CS, in this case it is "approximation gates" ie boolean gates in circuits that give "approximately correct" answers and which the lattice is a sort of "induction structure" for converting between an exact circuit to an inexact, approximate circuit.

# Answer
> 2 votes
Also, surprisingly (for me, at least) cryptography. Check it out, it allows new attacks of known cryptosystems and gives hopes for post-quantum-computing cryptography.

---
Tags: lattices, order-theory
---


title: How to show that problems are in NP?

text:
# Question
Title: How to show that problems are in NP?
I want to show that the following problems are in NP (NP-completeness is irrelevant) by textually describing a non-deterministic Turing machine which runs in polynomial time. The assumptions are that addition, multiplication, tests for divisibility can be done in polynomial time and natural numbers are represented in binary.

a) $\\{n \in \mathrm{N} \ | \ n \ $is not a prime number$\\}$

b) $\\{x\_1, ..., x\_n, y \in \mathrm{N} \ | \exists M \subseteq \\{1, ..., n\\} : \sum\_{m \in M}x\_m = y \ \\}$

For a) it's clear that there must be a non-trivial divisor if $n$ isn't a prime, but how does it exactly work? How can I reject invalid and verify valid inputs?

# Answer
> 7 votes
The easiest way to prove some problem is in $\mathsf{NP}$ is using the certificate definiiton of $\mathsf{NP}$ mentioned in other answers. The nondeterministic definition of $\mathsf{NP}$ is usually not very useful for showing a problem belongs to $\mathsf{NP}$. Intuitively, a problem is in $\mathsf{NP}$ iff we have an efficient (polynomial time) verification algorithm with polynomial size certificates/proofs.

For example, if you want to check if a given number $m$ is composite, the following works:

* Format of certificates: certificates are a pair numbers $(a, b)$,
* Verification algorithm: a certificate $(a,b)$ is accepted iff $1\<a,b\<m$ and $ab=m$.

If a number is composite then there is a pair of number $(a,b)$ which satisfies the condition and has size $O(\lg m)$. It is important that the certificate has polynomial size in the size of input (here the size of input is $\lg m$).

If a number is not composite there are no such pairs.

Note that we fix a particular certificate verifier for all inputs. You cannot change the verification algorithm from one input to another one.

A more challenging question is to show that primeness is also in $\mathsf{NP}$, i.e. there are polynomial size primality certificates.

# Answer
> 3 votes
In order to show that problem 1 is in NP, we follow your advice and use the fact that a number is not prime iff it has a non-trivial divisor. Problems in NP have an algorithm which accepts a "proof" that the input belongs to the language. These algorithms must satisfy two properties:

1. Every $x \in L$ has some proof $\pi$.
2. No $x \notin L$ has *any* proof $\pi$.

In addition, $\pi$ needs to be polynomial size, and the algorithm verifying the proof must run in polynomial time. The maximal size of the proof $\pi$ needs to be fixed in advance.

For your example, the proof $\pi$ is a non-trivial factor of the input $x$. Let's check all the requisite properties:

1. If $x \in L$ then $x$ is not a prime and so has a non-trivial factor $\pi$.
2. If $x \notin L$ then $x$ is prime and so it doesn't have any non-trivial factors.
3. The size of a non-trivial factor is at most the size of $x$, and so we can bound the size of $\pi$ by the size of $x$ (which is polynomial size).
4. Verifying that $\pi$ is a non-trivial factor of $x$ can be done in polynomial time, since division takes polynomial time.

As a side remark, it is now known that primality testing is in P, and so the language in question actually has a polynomial time algorithm. This means that we can dispense with the proof $\pi$.

---
Tags: complexity-theory, np
---


title: Can we read N numbers in O(N) time?

text:
# Question
Title: Can we read N numbers in O(N) time?
In a different post it came up that (using the Turing machine model of computation), it is not even safe to say that $N$ numbers can be read in $O(N)$ time. To me this is boggling since it's something I take for granted in the RAM model of computation, and I admittedly only have a cursory understanding of Turing machines.

However, the more boggling part is that the same person claimed that in the Turing machine model we cannot read $N$ numbers even in exponential time, BUT that we can read the input for Knapsack and fill a table of size $N$ by $w$ in exponential time.

How can filling a two-dimensional $N$ by $w$ array take less time than an $N$ by $1$ array?

# Answer
The complexity of an algorithm is defined in the size of input. You can talk about the running time of algorithm in other parameters but the classic complexity classes like $\mathsf{P}$ and $\mathsf{NP}$ are defined in the size of input (in Turing machine model).

For an algorithm to read $N$ numbers in $O(N)$ time it needs to be able to read a number in constant time. This might seem OK at first but it is not. The time that it takes to read a number depends on the number of bits needed to store it. If you want to read a number which has $2$ bits and a number which has $2^{100}$ bits to see even on an actual computer it really depends on the number of bits.

This confusion about reading a number in constant time comes because in programming languages the data types for numbers has a maximum number of bits. For example, in many programming languages an integer variable cannot store a number more than 64 bits. So it always reads 64 bits and therefore seems constant time. But if you don't have an upper bound on the size of numbers that you might read it can take arbitrary large amount of time.

Therefore we cannot bound the running time of an algorithm reading $N$ numbers simply in $N$, it depends on how large those numbers are.

OK, so does this mean we shouldn't use the RAM model based analysis for algorithms since it hides these issues? Well, we can use them, and it is usually much easier to use them. But one should be careful about these issues. That is the reason we put emphasis on what is the size of the input for a problem when teaching data structures and algorithms.

But it is not just the input. Take for example the following program:

```
Input: n
x = 2
for i from 0 to n
  x = x*x
return x

```

At first glance this looks like to be a polynomial time algorithm. We have a loop that is executed $n$ times and inside the loop we perform a single simple multiplication. So this is polynomial time?

No, it is not. The size of input is $\lg n$ (the number of bits used to give $n$) so this the loop is executed exponentially many times. But that is not the only problem. Let's look at

```
Input: n
x = 2
for i from 0 to log n
  x = x*x
return x

```

Is this one polynomial time?

It is not. Although the loop is executed only a linear number of times in the input length the number $x$ grows and it grows it takes more time to multiply it. To see this ask we can look at the number of bits $x$ the algorithm returns. Surely an algorithm running in polynomial time cannot return exponentially many bits, right?

$$ (0,2)\\ (1,4)\\ (2,16)\\ (3,256) .\\ .\\ .\\ (i, 2^{2^{i}}) $$

So the output is $2^{2^{\lg n}}$ which has $2^{\lg n}$ bits, exponentially more than the number of bits in input.

Now why this algorithm is not polynomial time? Well, multiplying two numbers is not constant time, and as $x$ grows the multiplication will take longer and longer time, and the amount of time it takes to multiply two numbers grows with the number of bits they have.

In a language like C you will quickly overflow if you define $x$ to be of the standard data types for storing integers.

OK, so why people use the RAM model for algorithms analysis then? Because it is much easier to analyze algorithms in the RAM model and if one is careful the result is correct. for example, if you only use operations which are polynomial time in the size of their input (like multiplication) and *during the execution you only store and use objects which are of polynomial size in the size of input* then if your algorithm executes a polynomially many operations then your algorithm is actually polynomial time.

Now, returning to the dynamic programming algorithm for the Knapsack problem. The space complexity of the algorithm is roughly $w^2n$ and the number of operations executed by the algorithm is $wn$. The size of input is something between $n+\lg w$ and $n\lg w + \lg w$ since we can assume all numbers are at most $w$ (otherwise we can ignore them). The exact size of input depends on the size of the numbers given to use. So it is not going to be polynomial time in general.

However, when $w$ is exponentially small relative to $n$, i.e. $w \approx \lg n$ the size of input becomes roughly something between $2n$ and $n^2$ and the running time becomes roughly $n^2$. In this case the running time is going to be bounded by a polynomial in the size of input.

When $w \approx \lg n$, it means that the numbers are so small that you can encode them in unary in place of binary with a at most polynomial increase in the size. This is why people sometimes say that Knapsack is polynomial time when the input numbers are encoded in unary. That is essentially the same as saying $w \approx \lg n$.

Note that if we encoded the numbers in the input in unary, the size of input would be between $n+w$ and $nw+w$ and then the algorithm *is* polynomial time in the size of the input.

In short, dynamic programming for Knapsack is polynomial time when the number $w$ is at most a polynomial in the total length of the input. This can be phrased in different ways but that is what essentially *pseudo-polynomial* means.

I think these confusion happen partly because people forget to emphasis the encoding used for input and output and without fixing those encodings the computational problem is not completely defined. All objects whether numbers, graphs, strings, etc. should be encoded with the basic objects that the machine deals with, which is usually bits. And there are many different ways of encoding other objects with bits, this is particularly important in practice when dealing with graphs. Some graph problems can be solved faster using adjacency matrix, other graph problems can be solved faster using adjacency lists, etc. and until the encodings are not fixed the complexity of the graph problem is not well defined.
> 10 votes

---
Tags: complexity-theory, turing-machines
---


# Question
Title: Minimum path in an undirected graph with 2 kinds of edges
Given an **undirected** graph with **positive weights**, there are 2 kinds of edges: locked edges and unlocked edges. Determination if a given edge is either locked or unlocked edge takes O(1).

For given two vertices s , t and a positive number k = O(1), How can I find the shortest path between s and t which contains **at most** k locked edges? How to find that path if it must contains **exactly** k locked edges? note that the second path might be contains the same locked edge **more than 1 time**.

So my first solution was to define a counter that is initialized to k, and decrease its value each time I found locked edge during dijkstra algo. but it doesn’t meet the requirement, so @tmyklebu suggest me to copy the graph k times, and modify each graph to **directed one** so that a locked edge vw in G\_i turns into an edge from u in G\_i to v in G\_{i+1} and from v in G\_i to u in G\_{i+1}. I didn’t undertand this solution, so I hope you can help (or suggest another one to solve this problem) :-)

Thanks a lot!
Tomer.

# Answer
I hope the following makes the solution clearer. Suppose the set of locked edges is $L$ and the set of unlocked edges is $U$. Let $G\_U$ be the graph with the same vertex set as $G$ but the edge set is $U$. Now make k+1 copies of $G\_u$. Since we now have $k+1$ copies of a vertex $v$, lets call them $v\_1 \ldots v\_{k+1}$.

Now add edges between the copies as follows. There is an edge between $u\_i,v\_{i+1}$ iff there exists a corresponding edge $u,v$ in G and the edge $u,v$ is locked. Now note that in this new graph we make a transition from one copy to the next copy if and only if we take a locked edge.

Now lets start a path from vertex $S\_1$ in the first copy and lets say we are at a vertex $V\_{i+1}$ in the $(i+1)^{th}$. Note that this means that we must have already traversed exactly $i$ locked edges. Therefore if we want to travel exactly $k$ locked edges we need to find a shortest path from $S\_1$ to $T\_{k+1}$.

Another way to think of what this path would look like is that imagine the required shortest path and cut it off into pieces where the locked edges. Now you can see that in your path the pieces in between the $i^{th}$ locked edge and the $(i+1)^{th}$ locked edge happen in the $(i+1)^{th}$ and each locked edge moves you to another segment. Hope this helps.

If you want the shortest path with atmost k edges you can look for the shortest path from S to $T\_1,T\_2 \ldots T\_{k+1}$ and take the minimum.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Which are the most effective sorting algorithms for a large dataset?
A bit of background, the work that I currently and will be doing involves sorting very large amounts of data (in this case, grayscale pixels in descending order), sometimes up to 4 million.

Which are the most effective and efficient sorting algorithms that could handle multiple large datasets (such as descried in the 1st paragraph)? Is there an algorithm that could simultaneously sort through 2 or more sets of pixels?

# Answer
> 1 votes
1. quick sort. in C++, it's better to use std::sort rather than qsort(), since it allows compiler to perform much better optimization (both implements quick sort algorithm)
2. depending on your data, sometimes better: http://en.wikipedia.org/wiki/Counting\_sort and http://en.wikipedia.org/wiki/Radix\_sort

> simultaneously perform sorts on multiple large datasets?

i've not heard of such algorithms at all. but you can distribute tasks among CPU cores. moreover, you can split one dataset between two cores, and then merge results of sorting

---
Tags: algorithms, algorithm-analysis, sorting
---


# Question
Title: What are flops and how are they benchmarked?
Apple has just proudly stated that their new mac pro will be able to give up to 7 teraflops of computing power. Flops stands for Floating Point Operations Per Second. How exactly is this benchmarked though? Certain floating point operations are much heavier than others, so how exactly would a FLOP be a benchmark for computing power?

# Answer
As far as I know, they give *peak performance* values. Given clock speed $f$ (in Hz) and number of cycles per (shortest) floating point operation $c$, the peak performance is essentially $f \cdot c$.

Of course, modern machines execute multiple floating point operations in parallel, have multiple cores etc. A more accurate formula can be found on Wikipedia.

This measure ignores all of the pain any real program encounters, e.g. cache misses and pipeline stalls. That is, any (reasonable) benchmark will not reach this number. But as an (unattainable) ultimate figure it can be useful to compare machines and even programs (how close to peak performance do they get?) -- take such statements with a grain of salt, always.
> 3 votes

# Answer
I guess you should ask Apple how they got that figure. For instance, maybe they ran the lapack/linpack benchmarks (or similar) like they do for the Top500. If they're using benchmarks, this will include real-world limiting factors that Raphael mentions. Performance in the range of several teraflops is pretty respectable for a modern consumer system, equivalent to a beefy CPU and a mid-range GPU or two.

To answer your question, then, FLOPS stands for "floating point operation per second", it's measured by executing code that performs a known number and mix of floating point operations, and reporting the number of operations divided by the total time. Professionals will look at FLOPS measurements from a variety of scenarios and report appropriate metrics based on the collected data. Measuring FLOPS is a well-studied and supported endeavor and lots of benchmark suites exist for precisely this purpose. Analytical computations can be useful for upper bounds but are otherwise basically useless.
> 1 votes

# Answer
> Apple has just proudly stated that their new mac pro will be able to give up to 7 teraflops of computing power. Flops stands for Floating Point Operations Per Second. How exactly is this benchmarked though?

The 7 TFLOPs spec comes from Apple's new MacPro page.

The spec is probably based on the workstation having two AMD FirePro W9000's; each according to AMD is capable of "4.0 TFLOPs single precision" performance.

> Certain floating point operations are much heavier than others, so how exactly would a FLOP be a benchmark for computing power?

I could not find information on how AMD benchmarks this particular GPU for FLOPS measurements, but in general benchmarks use a mixture of operations (addition, multiplication and division) in problem sets, attempting to simulate real world conditions. FLOPS is not useful benchmark for general computing power. Unless you're doing embarrassingly parallel single-precision floating point computations, you should just ignore the Apple FLOPS number.
> 1 votes

# Answer
that's much simpler than one could imagine. first, since it's a commercial world, they say about *peak* performance, i.e. maximum number of FP operations that it can execute in a second. yes, it easily may be just additions. or since many modern cpus/gpus implement MAD (multiple-then-add) - it may be MAD counted as two FP operations

next, most of this power goes from GPU rather than CPU. modern GPUs are massively parallel computers, after all. i don't want to look into actual GPU specs, but it have something like 2000 cores running at about 1 Ghz. So it may perform 4 TFLOPS per GPU (remember MADs!) and 8 TFLOPS with 2 GPUs installed

Of course, since it's the *peak* performance, you have problems reaching the same speed in real application - you may be limited by memory/PCI-Express speed, or by the fact that those 2000 cores are joined into only a few dozens of independent execution unites, with all cores inside single unit performing the same program with different data (i.e. SIMD operation)
> 0 votes

---
Tags: computer-architecture, efficiency, benchmarking
---


# Question
Title: Binary Search Tree: Replace $k$ min elements with their average
Given a valid binary search tree whose keys are unique real numbers, and a set of $k$ pointers to the $k$ minimum elements in the tree, will the BST property be maintained if I replace all $k$ elements with the average of the $k$ elements?

The BST property as given in Corman:

> Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $y.key \geq x.key$.

I've tried this with a few test cases for $k=3$ and a few different trees, and it seems to hold, but I'm not sure if it actually does *and how I could prove it*.

# Answer
The following is either a proof, or an argument that runs in circles.

Given a binary search tree the ordered sequence of keys can be retrieved using the symmetric inorder traversal. Conversely any ordered sequence of keys can be stored in a binary tree with the BST property only if the keys are mapped precisely in inorder. (Proof: the root has a unique value as all keys the the left must be smaller, to the right must be larger. Use recusion for the subtrees).

Now take a BST tree and retrieve its keys in order. Take any *consecutive segment* of the keys and replace these keys by any value between the first and last of the segment. The result is again an ordered sequence of keys and remapping to the original tree will give again a BST.

Taking the minimum $k$ values and replacing with the mean is a special case.
> 4 votes

# Answer
Let $M = \\{T\_{(1)}, \dots, T\_{(k)}\\}$ the set of the $k$ smallest elements in a BST $T$. Replace all elements in $M$ with $\tfrac{1}{n} \cdot \sum\_{i=1}^k T\_{(i)}$.

Let $x$ some node in $T$ and $y$ some other node in the left (right) subtree of $x$. Perform a complete case distinction:

1. $x,y \in M$
2. $x \in M$, $y \notin M$
3. $x \notin M$, $y \in M$
4. $x, y \notin M$

Show for all cases that they either can not occur, or that the BST property still holds.
> 1 votes

---
Tags: data-structures, proof-techniques, search-trees
---


title: Theta Runtime of Nested for Loops

text:
# Question
Title: Theta Runtime of Nested for Loops
I have two for loops, one nested within the other. I have two int variables n and U, where `U > n`. I know that the outer loop runs exactly U times (pretty much `for(int i = 0; i < U -1; i++)`), and the inner loop runs exactly n times in total **for the duration of the entire execution**. It can run n times once and never run again, or it can run once in each iteration of the outer loop n times, or anything in between.

It's obvious that this runs in O(nU) time. However, I think I can also state it runs in `theta(U + n)` time because the inner loop runs independently of the outer one. But still, they are nested, and not multiplying the runtimes of nested loops feels awkward.

Intuitively I know I am right, but I don't really know how to show it. I'm not looking for a formal proof, but any kind of insight is welcome.

# Answer
Yes, the running time is $O(U+n)$, assuming that each iteration of the inner loop takes $O(1)$ time. The way to prove it: try to write down an expression for the running time, as a function of $U$ and $n$. What did you get? Now, see you can show that this expression is at most $c \cdot (U+n)$, for some constant $c$ that you get to specify.
> 2 votes

---
Tags: algorithm-analysis, runtime-analysis, loops
---


title: Finding an Uncomputable Function

text:
# Question
Title: Finding an Uncomputable Function
Let there be 2 sets $X$ and $Y$, both are countable (assume the bijection from $\mathbb{N}$ to the respective sets is computable) and infinite. Let $S$ be the set of all possible functions (NOT necessarily computable, i dont care about computability at this point) from $A$ to $Y$ for all $A \subset X$ (Remember that $A$ is not fixed here and it varies to cover all subsets of $X$. Note that $X$ and $Y$ are fixed in this question).I understand that $S$ is uncountable (as the number of subsets of $X$ will be uncountable) and hence all functions in it cannot be computable because there are countable number of computable functions. My question is that if there are indeed uncomputable functions in $S$, can somebody please give me an example of one such function or example of a subset of $S$ which contains only uncomputable functions ?

Thankyou!

# Answer
Your definition is a complicated way to say that $S$ is the set of partial functions $X\to Y$ (the sets $A$ you choose are the domains of the partial functions).

Now, if you want to talk about computability, you have to be more precise on $X$ and $Y$: every element of $X$ and $Y$ have to be finitely described, so that they can be manipulated by algorithms.

We can for instance consider that $X=Y=\mathbb{N}$. Since they are countable and infinite, we just have to apply some bijections to get this.

Now, the framework you define is exactly the one of computability theory, you can define turing machines etc, and find out what the uncomputable are. Go here for more details.

For instance the halting function (which is in fact a function $\mathbb N\to \\{0,1\\}$) is uncomputable. As for an example of subset of $S$ which contains only uncomputable functions, it is true as soon as the domain of the function is not a recursively enumerable set. For instance there is no recursive function $NH\to \mathbb N$, where $NH$ is the set of indices of Turing machines that do not halt on input $0$.
> 4 votes

# Answer
The halting function is a classic example of an uncomputable function.

If $S$ is countable, you can put it into a one-to-one bijection with the set of all binary strings (or the set of all possible program source codes), so then you can think of the halting function as a function with $S$ as its domain.
> 1 votes

---
Tags: computability
---


title: Semi-local Levenshtein distance

text:
# Question
Title: Semi-local Levenshtein distance
If you have a long string of length $n$ and a shorter string of length $m$, what is a suitable recurrence to let you compute all $n-m+1$ Levevenshtein distances between the shorter string and all substrings of the longer string of length $m$?

Can it in fact be done in $O(nm)$ time?

# Answer
If you want the minimum number of single-character changes (insert, delete, substitute) that transforms the shorter string $S$ into some length-$m$ substring of $T$, then this can be done in $O(nm)$ time.

The standard algorithm for computing the edit distance between two strings runs in $O(nm)$ time. It uses dynamic programming to build up a matrix $d\[\cdot,\cdot\]$ where $d\[i,j\]$ denotes the minimum number of single-character changes that transform $S\[0\ldots i\]$ to $T\[0 \ldots j\]$.

You can use a simple variation of this algorithm to build up a matrix $d'\[\cdot,\cdot\]$ where $d'\[i,j\]$ denotes the minimum number of single-character changes that transform $S\[0\ldots i\]$ to some suffix of $T\[0 \ldots j\]$ (i.e., to some string $T\[k \ldots j\]$ for some $k\le j$). The running time remains $O(nm)$. This is sometimes known under the name fuzzy string search.

This gives you a single distance, which represents the smallest number of single-character changes needed to transform $S$ into a length-$m$ substring of $T$. (If you wanted to get all $n-m+1$ edit distances from $S$ to each length-$m$ substring of $T$, I don't know whether that can be done in $O(nm)$ time.)
> 1 votes

---
Tags: recurrence-relation, dynamic-programming, strings, string-metrics, edit-distance
---


title: Nash Equilibrium of 2-players game

text:
# Question
Title: Nash Equilibrium of 2-players game
I have a rather interesting exercise in Game Theory.

*Assume there is a 2-players game, and player $i$ has $n\_i$ pure strategies. The game is given by listing the payoffs for each player for each $n\_1 × n\_2$ possible plays.*

*Give a polynomial time algorithm to check if there is a Nash equilibrium for the game in which each player mixes between at most two strategies. Give a ﬁnite algorithm for finding a Nash equilibrium for general games with two players. Your algorithm may run in exponential time.*

The answer to the first question hopefully can be solved by convex optimization.

In the second case some kind of exhauivet search can be used.

Unfortunately I don't know how to proceed.

# Answer
Hint: Given a mixed strategy for both players, how can you verify that it's a Nash equilibrium? How many potential strategies do you need to consider in both cases?
> 1 votes

---
Tags: algorithms, linear-programming, game-theory
---


# Question
Title: Understanding an example of coin toss expectation maximization
I've been trying to get my head around Expectation maximization algorithms, and I thought I'd start simple. I found this 3-coin example here: http://cs.dartmouth.edu/~cs104/CS104\_11.04.22.pdf I understand the calculation of all of the probabilities but I don't understand how the recalculation of lambda, p1 and p2 is actually done. (Page 18)

I understand how the maximization of a log-likelihood/likelihood function by differentiation works, but can't figure out the recalculation method here.

Can anyone explain why the recalculation of lambda, p1 and p2 take the form they do?

# Answer
From mcdowella's answer to IcySnow's question Expectation Maximization coin toss examples, Michael Collins' EM Algorithm (pdf) paper presets the "Three Coins Example" in section 3.1 (pdf page 8-9) and explains the steps for recalculating the parameters $\lambda, p\_1, p\_2$ in accordance with the EM Algorithm.

The derivation is too lengthy to type up here, but to summarize, you'll formulate the conditional expectation in terms of the previous iteration of parameter values and then differentiate the expectation with respect to each parameter from the previous iteration then perform algebra to obtain the maximum after setting the derivative to zero.
> 1 votes

---
Tags: probability-theory, statistics
---


# Question
Title: Speaking of "randomness" in computing terms, to what sense can any extant digital processor make "random" results?
From a very strictly adhering sense to the hardware and circuit-level operations of any standard (non-specialized, DSPs, or supercomputing systems, etc.) microprocessor follow very similar, almost exact in some ways, operations.

The typical role of the (main) processor in a computer, integrated with other hardware circuits or not, and excluding DMA is to have a memory subsystem fetch byte(s) for it to "process" in whatever way. To have a processor "randomly" selective something can be abstracted and seen from a data algorithm HLL-type point of view, but on the circuit-level the operations can only get so complex. I know some Assembly of x86, so I can demonstrate further on the details of what I'm asking.

If you fetch a byte, or series of bytes, and then use some schematic to cycle through potential jump offsets, that is the only way to do randomness? Are their other ways?

# Answer
> 3 votes
Everything you can do in a high-level language can be done in assembly. After all, the high-level language is compiled to machine code.

What you seem to be describing is *pseudorandom numbers*, which are numbers generated by a computer using an algorithm, and look (computationally) random. It is also possible to generate "somewhat random" numbers by harvesting (say) thermal heat, or other "random" phenomena. The result won't quite be a sequence of i.i.d. fair coin tosses, but if you run it through an extractor it will look (computationally) pretty similar, and be theoretically unpredictable (since it's based on actual physical randomness).

---
Tags: randomized-algorithms, randomness
---


# Question
Title: Complexity of recursive solution to coin change
How do you go about analysing coin change recursive solution. i.e, `T(N,K) = T(N,K-1) + T(N-1,K)` for K denominations that add up to amount N.

You can find the problem description and pseudo code here - http://www.algorithmist.com/index.php/Coin\_Change#Recursive\_Formulation

# Answer
A general method for solving recurrences of this form is generating functions. The exact solution also depends on the initial values. In your case, one possible solution is $T(n,k) = C 2^{n+k}$.
> 2 votes

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


title: Automaton for substring matching

text:
# Question
Title: Automaton for substring matching
Given $s$ as a string over some alphabet, what is the best known algorithm to compute a corresponding deterministic finite-state automaton (DFA) that accepts any string that contains $s$?

I am mostly interested of the lowest time complexity so if you tell me what is the best known complexity in O notation to build an automaton for a string that would be just as good.

# Answer
Hendrik Jan is correct about the Knuth-Morris-Pratt algorithm (warning, wikipedia doesn't explain it particularly well, a text on algorithms is probably a better bet). The failure function can be used to extract a DFA that can perform the string matching. It's not immediately obvious that the failure table is a DFA, but with very little work the transition table for the DFA can be constructed. If $W$ is the pattern string you want to match, the time to build the table (and hence construct the DFA) is $O(|W|)$.

The central idea is that the failure table $T$ (I'll try to use the same names as wikipedia, just to get a ready-made example) tells you where you could be up to in the string if the current match doesn't work out, i.e. if you don't see the next character you're expecting, perhaps the beginning of the match you want has already been seen, you're just mistakenly further ahead, so you only want to "back-track" a little (note, there's no real backtracking in the usual algorithmic sense).

So, shamelessly stealing the example from wikipedia, say we have the failure table $T$:

$$\begin{array}{c|cccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline W\[i\] & A & B & C & D & A & B & D \\ T\[i\] & -1 & 0 & 0 & 0 & 0 & 1 & 2 \end{array} $$

We can construct the DFA as follows; we have $|W|+1$ states, with a backbone of transitions that match the entire pattern. To match the table we'll call the start state $q\_{-1}$ and the final state $q\_{|W|}$ (so in the example $q\_{6}$). The backbone is then the transitions $\delta(q\_{i-1},W\[i\]) = q\_{i}$, so in the example, we go from the start state $q\_{-1}$ to state $q\_{0}$ on an $A$ and from $q\_{2}$ to $q\_{3}$ on a $D$.

Now the trick is to add the correct "backwards" transitions so that we don't go too far back along the backbone when we get something wrong. This is where we us the failure function. If we're in state $q\_{i-1}$ and we don't see $W\[i\]$ as the next symbol, then we can alternatively transition to $q\_{T\[i\]}$ if we see $W\[T\[i\]\]$. From the example, if we're in state $q\_{5}$, and we don't see a $D$, but we do see a $C$, we can go to $q\_{2}$. Every other symbol returns us to the start state.

Reiterating; there are three types of transitions, the backbone transition if everything's going fine, the transition given by the failure table so we might be able to recover a bit, and $|\Sigma| - 2$ other transitions that take us back to the start state.

The start and final states are a little special of course, the start state can't go back further, so the failure recovery transition appears with the other transitions, and once we reach the final state, it doesn't matter what else we see, so it's a sink state too.

There's one final wrinkle, the case where the failure symbol is the same as the expected (e.g. $W\[1\]$ and $W\[5\]$) in this case we can just defer the decision until they're different, or we can create an NFA.

The example then results in a DFA that looks (barring mistakes) like:

The dashed transitions represent the "everything left over" transitions.

It should be easy enough to see that given the table, we can construct the DFA in $O(|W|)$ time (in one pass really). The table can also be constructed in $O(|W|)$ time - the source code on wikipedia is sufficient. If we get clever, of course we can skip the intermediate table step and use the table building algorithm to just create the DFA immediately. This running time is also the best we can hope for, as a DFA that matches only this string has to have at least $|W|$ transitions (and $|W|+1$ states), so we need to read the entire string $W$, which takes $\Omega(|W|)$ steps.
> 8 votes

# Answer
**Answer.** Although I have seen a deleted answer, I still think the construction is linear in the length of the string (considering the alphabet size constant). Aho Corasick 1975, doi:10.1145/360825.360855

**Or perhaps KMP.** Aho & Corasick consider pattern matching automata for a finite set of words, forming a tree with back-pointers in case of mismatches=failures. This is in the style of the Knuth-Morris-Pratt algorithm, that considers a single string. I could not find whether KMP actually *explicitly* move from match/failure automata to the deterministic automata (with a transition for every letter in the alphabet). Thus basically the KMP approach suffices together with a clever argument that this can be turned into a DFA in linear time. A&C explicitly mention that last step. The KMP failure table however is slightly simpler than the A&C construction (one does not need a tree of strings) and can be found all over the web.

**A note.** Anyone interested in pattern matching *should* read the original KMP paper, doi: 10.1137/0206024, or at least the historical remarks from Section 7. Quote: "Knuth was chagrined to learn that Morris had already discovered the algorithm, *without* knowing Cook’s theorem \[..\]". The KMP paper was published only in 1977 while Morris already implemented his version in a text-editor in 1969, while Knuth and Pratt discovered their slighly later as an application of a proof of Cook.
> 6 votes

---
Tags: automata, finite-automata, strings, substrings
---


# Question
Title: Partition problem with distinct integers
The partition problem is a well-known NP-complete problem. In the definitions I have seen, the input is assumed to be a multiset of integers, and we want to decide the existence of a partition into two sets that have the same sum. My question is:

> Is the partition problem still NP-complete if all input integers are distinct (i.e., no integer is repeated)?

# Answer
Here is an outline of a reduction from PARTITION to UNIQUE PARTITION. Suppose the original numbers are $x\_1,\ldots,x\_n$ and the target is $T$. I assume that all $x\_i$ are positive integers. The new numbers are going to be $2^n x\_i + i$, as well as $1,2,4,\ldots,2^{n/2}$, and the new target is $2^n T + 2^{n/2}$. (The numbers $2^n,2^{n/2}$ are quite arbitrary and could be made much smaller.)
> 13 votes

---
Tags: complexity-theory, np-complete, partitions
---


# Question
Title: Solve modulus with constraints for multiple equations
I'm trying write a program to solve equations from the following form:

$$ \begin{align} a \bmod x &= t\_1 \\ b \bmod x &= t\_2 \\ \end{align} $$

where $a$, $b$, $t\_1$ and $t\_2$ are known values.

I have multiple equations of the same form and I'd like to solve them for $x$. Assuming I have constraints on $t\_1$ and on $t\_2$ for some constant $C$:

$$ \begin{align} 0 \le t\_1 \lt C \\ 0 \le t\_2 \lt C \\ \end{align} $$

e.g : for $a=150$, $b=50$, $t1=2$, $t\_2=1$: $$ \begin{align} 150 \bmod x &= 2 \\ 50 \bmod x &= 1 \\ 1, 2 \lt 5 \\ \end{align} $$

What would be the most efficient way to program such a thing?

# Answer
As user8962 explains, an equation of the form $a \pmod{x} = b$ is equivalent to $x | a-b$ and $x \> b$. Now suppose you have equations $a\_i \pmod{x} = b\_i$ for $i=1,\ldots,n$. You first compute $g = \gcd(a\_1-b\_1,\ldots,a\_n-b\_n)$ (you do that iteratively: $\gcd(x,y,z) = \gcd(\gcd(x,y),z)$ and so on); we know that $x$ is a divisor of $g$ satisfying $x \> B = \max\_{i=1}^n b\_i$. If $B \geq g$ then there is no solution. Otherwise, $g$ is one solution, and there may be other solutions: all divisors of $g$ larger than $B$.

In your example, $150 \pmod{x} = 2$ and $50 \pmod{x} = 1$. So $g = \gcd(150-2,50-1)=1$ and $B = \max(2,1) = 2$, and since $B \geq g$ there is no solution.
> 2 votes

# Answer
Expand the equivalences $150 \equiv 2 \pmod{x}$, $50 \equiv 1 \pmod{x}$ into $150 = 2 + k\_1 x$, $50 = 1 + k\_2 x$ for some integers $k\_1, k\_2$ and deduce that $148 = k\_1 x, 49 = k\_2 x$. There is no *integer* solution since $\gcd(148, 49) = 1$. But (for example; another system) if you replace $150$ with say $65$, then you have $\gcd(49, 63) = 7$. Since $x$ must be $\> t\_1, t\_2$ (or your given upper bound on $t\_1, t\_2$), we can set $x = 7$ (or other factors of the gcd which satisfy the aforementioned conditions). You can probably turn this into an algorithm. The dominant cost is gcd computation.
> 4 votes

---
Tags: algorithms, computer-algebra
---


# Question
Title: Dynamic Programming To calculate the combinations
This is a problem from a past contest at topcoder : Problem.

Its solution is given here : Solution \[Scroll Down to Penguin Emperor\]

I am unable to understand how the section with subheading "Combinations are associative" works. What is actually going on in this step ? How is the convolution property being used ? Or the Associative property of Combination ? How is the exponentiation squaring being performed ?

**EDIT**

*Problem Statement*

You are Given N cities numbered from 0 to N-1 in a circular order. You are currently at city index 0. On **first** day you can move from your your current city with index **i** to a city with index **j** such that

```
j = (i+N-1)MOD N
or
j = (i+1)MOD N

```

On **second** day you can move from your your current city with index **i** to a city with index **j** such that

```
j = (i+N-2)MOD N
or
j = (i+2)MOD N

```

and so on. So on Day **x**, you can move from your your current city with index **i** to a city with index **j** such that

```
j = (i+N-(X MOD N))MOD N
or
j = (i+(X MOD N))MOD N

```

You **have** to travel on each day.

Given the number of Days **M**, find the total number of ways, you can travel starting from city index 0 such that at the end of M days you are back to city index 0 , modulo 1000000007.

The solution given is as following :

```
final int MOD = 1000000007;
// Discrete convolution:
int[] combine(int[] A, int[] B)
{
    int n = A.length;
    int[] C = new int[n];
    // Skipping when B[i] = 0, is a key optimization:
    for (int i=0; i<n; i++) if (B[i] != 0) {
        for (int j=0; j<n; j++) {
            int k = (j - i + n) % n;
            C[k] += (int)( (A[j]*(long)B[i]) % MOD );
            if (C[k] >= MOD) {
                C[k] -= MOD;
            }
        }
    }
    return C;
}
// Exponentiation by squaring, for our convolution operation:
int[] power(int[] A, long x)
{
    int n = A.length;
    int[] R = new int[n];
    R[0] = 1;
    while (x > 0) {
        if ( (x & 1) != 0) {
            R = combine(R, A);
        }
        A = combine(A, A);
        x >>= 1;
    }
    return R;
}

public int countJourneys(int numCities, long  daysPassed)
{
    // Generate R and Q:
    int[] Q;
    int[] R = new int[numCities];
    R[0] = 1;
    Q = R;
    for (int i=1; i<=numCities; i++) {
        //B holds T[i]
        int[] B = new int[numCities];
        B[i % numCities] = 1;
        B[numCities - i] = 1;

        R = combine(R, B);

        if (i == daysPassed % numCities) {
            Q = R;
        }
    }
    R = power(R, daysPassed / numCities);
    R = combine(R, Q);
    return R[0];
}

```

countJourneys(N, M) is called to get the answer.

# Answer
The idea is to use dynamic programming. For each day $k$, we find the number of ways (modulo $p = 1000000007$) to get from $0$ to $x$ for each $x \in \\{1,\ldots,N\\}$. Given the array $A\_k$ for day $k$, the array $A\_{k+1}$ for day $k+1$ is given by $$ A\_{k+1}(x) = A\_k(x-k-1) + A\_k(x+k+1), $$ where all indices are modulo $N$. The actual computation is done modulo $p$.

In your case, it seems that $M \gg N$, and then this method is a bit slow. That's why we want to use convolution. There is another way to describe the calculation above. Consider formal variables $x\_0,\ldots,x\_{N-1}$ that satisfy the rule $x\_i x\_j = x\_{i+j \pmod{N}}$ (for concreteness, we could take $x\_j = e^{2\pi i (j/N)}$; but we could also just treat them as formal variables.) We represent the array $A\_k$ in the form $$ A\_k = \sum\_{i=0}^{N-1} A\_k(i) x\_i. $$ We have $A\_0 = x\_0$ and $A\_{k+1} = (x\_{k+1} + x\_{-k-1}) A\_k$ (all indices modulo $N$). This kind of multiplication is known as *convolution*, and it satisfies all the usual rules of multiplication (it is commutative and associative).

When $M$ is big, we want to take advantage of the fact that $A\_k = A\_{k \pmod{N}}$. So $$ A\_k = \prod\_{i=1}^N (x\_i + x\_{-i})^{\lceil (k-i+1)/N \rceil} A\_0. $$ The idea now is to compute $(x\_i + x\_{-i})^d$ using *repeated squaring*, which you can look up. For example, to compute $X^{10}$ we would compute $X,X^2,X^4,X^8$ and multiply $X^2$ and $X^8$ (more generally, we look at the binary expansion of the exponent). Given all the factors, we multiply everything together and then look at the coefficient of $x\_0$.

Since we only want the result modulo $p$, we do all the computations modulo $p$.
> 1 votes

---
Tags: combinatorics, dynamic-programming
---


title: Pairwise comparisons with confidence

text:
# Question
Title: Pairwise comparisons with confidence
There is a lot of information available on the subject of Pairwise Comparisons but I haven't found any guidance on how to optimize pair measurements that have confidence values attached to them.

Imagine that an AI black box has been trained on many pairs of objects in order to predict the distance between the objects in novel pairs. All objects are colinear. The black box also provides a confidence level for each distance. Here is a simple example of outputs based on a set of 5 objects ($a$ to $e$):

```
Pair, Distance, Confidence

a-b,  5,        0.4
a-c,  9,        0.7
a-d,  -3,       0.9
a-e,  2,        0.6
b-c,  6,        0.8
b-d,  -10,      0.7
b-e,  -2,       1.0
c-d,  -6,       0.5
c-e,  -2,       0.6
d-e,  7,        0.9

```

So, the distance between $a$ and $b$ is predicted to be 5 units ($b$ is to the right of $a$) and the black box's confidence in that measurement is 0.4 (0.0 = no confidence and 1.0 = perfect confidence). The distance between $a$ and $d$ is -3 units ($d$ is to the left of $a$) and the confidence is 0.9.

I would like to understand the process for deriving the solution, which is the optimization of the four distances between these objects given the predicted distances and their associated confidence levels.

# Answer
> 2 votes
I suggest that you define a *loss function*, which characterizes how much a candidate solution is penalized if the true distance between (say) $a$ and $b$ differs a bit from your prediction.

For instance, one candidate loss function might be $L(d) = c \times |d - d\_0|$, where $d$ is the actual distance in the candidate solution, $d\_0$ is the predicted distance, and $c$ is the confidence in the prediction. Another candidate loss function could be $L(d) = c \times (d-d\_0)^2$. There could be many other loss functions.

Suppose we let $L\_{a,b}$ denote the loss function for the pair $a,b$, and so on. We might define the overall loss to be the sum of the losses for each pair:

$$L = L\_{a,b}(|a-b|) + L\_{a,c}(|a-c|) + L\_{b,c}(|b-c|) + \dots$$

where $a,b,c,\dots$ denote the positions of the points in the candidate solution.

With this framework, one could then ask for the optimal solution, i.e., the values of $a,b,c,\dots$ that minimize this total loss $L$. That is an optimization problem that could be solved a variety of optimization methods (e.g., by differentiating and setting the derivatives to zero; by using numerical optimization methods, such as gradient descent; or by solving this particular optimization problem directly).

For the loss function $L(d) = c \times |d-d\_0|$, this optimization problem can be solved using linear programming. Instead of using $a,b,c,\dots$ to represent the locations of the points, I'd like to use $x\_1,x\_2,x\_3,\dots$, as that is more convenient. Also, let $d\_{i,j}$ represent the predicted difference between $x\_i$ and $x\_j$, and $c\_{i,j}$ represent the confidence of this prediction, for all $i,j$. We are given the $d\_{i,j}$'s and the $c\_{i,j}$'s, and we want to solve for the $x\_i$'s. In particular, we want to find the $x\_i$'s that minimize the overall loss

$$L = \sum\_{i,j} c\_{i,j} \times (|x\_i-x\_j-d\_{i,j}|).$$

To find the optimal solution, we'll write a linear program, with $x\_1,x\_2,x\_3,\dots$ as unknowns, where the solution to the linear program is the optimal solution to your problem. To make this work, we need to translate the optimization problem into one with linear inequalities. To facilitate that, I'll introduce variables $l\_{i,j}$ for each $i,j$; intuitively, $l\_{i,j}$ represents the loss associated with $x\_i,x\_j$, i.e., it represents the value $c\_{i,j} \times (|x\_i-x\_j-d\_{i,j}|)$. We can express these relationships as linear inequalities as follows. We want to have $c\_{i,j} \times (|x\_i-x\_j-d\_{i,j}|) \le l\_{i,j}$, but unfortunately this is not the sort of inequality we can write directly in a linear program. Fortunately, if we just manipulate this a bit we can get two inequalities that *are* allowable in a linear program:

$$x\_i-x\_j \le d\_{i,j} + \frac{1}{c\_{i,j}} l\_{i,j}$$ $$x\_i-x\_j \ge d\_{i,j} - \frac{1}{c\_{i,j}} l\_{i,j}.$$

Since $d\_{i,j}$ and $c\_{i,j}$ are known values (constants), the above inequalities are linear in the unknowns $x\_i,x\_j,l\_{i,j}$, so they are allowed to appear in linear programs. Thus, we minimize the function $\sum\_{i,j} l\_{i,j}$, subject to all of the above linear inequalities (we get two of them for each $i,j$). This is a linear program, and its best solution is the optimal set of locations $x\_i$ for your points.

You can solve this linear program using any standard linear solver (e.g., `lp_solve`). There are $n(n-1)$ linear equations and $n(n-1)/2 + n$ unknowns, which is not too many: I would expect existing linear solvers to be able to handle this kind of linear programming problem without difficulty.

But before you can solve the problem, *you* must decide what are suitable loss functions and what is a suitable formalization. Then, and only then, can you construct an algorithm to solve this problem.

# Answer
> 2 votes
There are several possible ways to solve this problem. One way is to assume some measurement model (usually Gaussian noise) and then find the maximum likelihood solution.

That is, we start with some distribution of the measured distance given the actual distance and the noise level, for example if the actual distance is $d$ and the noise level is $\sigma$, then perhaps the measured distance is distributed $N(d,\sigma)$.

Given a sequence of measurements, for each potential list of positions (say with $a=0$ to break the symmetry), we can calculate the likelihood that we would get the actual measurements. In your case, we would get $$ L(a,b,c,d,e) = \frac{1}{\sqrt{2\pi} 0.4} e^{-(5-(b-a))^2/(2\cdot 0.4)} \cdot \frac{1}{\sqrt{2\pi} 0.7} e^{-(9-(c-a))^2/(2\cdot 0.7)} \cdots. $$ The idea is to find the setting of $a,b,c,d,e$ that maximizes $L(a,b,c,d,e)$. To that end, we can calculate $$ -\log L(a,b,c,d,e) = C + \frac{(5-(b-a))^2}{2\cdot 0.4} + \frac{(9-(c-a))^2}{2\cdot 0.7} + \cdots.$$ We want to minimize the latter. We can substitute $a = 0$, and then differentiate with respect to each of the other variables, and equate to zero. For example, differentiating with respect to $b$, we obtain $$ 0 = -\frac{\partial \log L}{\partial b} = \frac{b-5}{0.4} + \frac{b-c+6}{0.8} + \frac{b-d-10}{0.7} + \frac{b-e-2}{1.0}. $$ In this way, we get linear equations which we can solve for $b,c,d,e$. (This is the method of least squares.)

For other models of noise, we might have to use numerical optimization instead. You can find more examples in any machine learning textbook.

---
Tags: machine-learning, artificial-intelligence, computational-geometry
---


# Question
Title: Finding the difference between two number in a sorted list using divide-and-conquer
How to find the smallest difference between two numbers in a sorted list using divide-and-conquer approach? For example,

```
   (smallest-dif '(5 500 510 670 750 10000)) => 10

```

# Answer
The smallest difference between two numbers in a sorted list is given by the difference between some consecutive numbers in the list. This can be found out in linear time without using a divide and conquer approach. Since you have a `O(n)` algorithm which is the least possible time required to solve this problem it is not advisable to use a divide and conquer approach.
> 2 votes

# Answer
Let's take your example. I'll show how to find the minimal difference, and hopefully you'll be able to generalize (though there's no divide and conquer involved). The minimal difference is always obtained at some consecutive elements. We compute all the relevant differences $500-5 = 495$, $510-500 = 10$, $670-510=160$, $750-670=80$, $10000-750=9250$, and take the minimum $10$.
> 1 votes

---
Tags: encoding-scheme, divide-and-conquer
---