# Question
Title: Method for finding correlation between data sets
Let's say that I have $N$ data sets where I have data points at some fixed frequency, such as "daily".

What would be a good method for finding correlation between any of the data sets, or choosing a single data set, and asking what other data sets are most correlated?

To make it less abstract, imagine that I'm logging how much water I drank a day in ounces, how much exersize i did a day in minutes, my mood level, and how bad of a headache I had that day from 1 (no headache) to 10 (bad headache). I'd want to be able to see if my headaches were correlated (keeping in mind, it might not be causation) to me drinking less water perhaps, or doing less exercise. However, it's possible that there may be a lag between cause and effect (or correlation), etc.

That's my basic question, but in case it's relevant to the answer, I'm also wondering how I might be able to handle missing data (maybe some days didn't get data?).

Also, I was wondering what if the data sets AREN'T at the same frequency? Like one data set may be weekly while the others are daily.

My best guesses at how to approach this could be to use a discrete Fourier transform of each data set, and then do a dot product between the frequency histograms to find ones that had similar frequencies (even if different phases), and then I could use the phase information to figure out the kind of lag time there is.

Since I'm also interested in negative correlation, I'm thinking that when i do the dot product between the histograms and get my 0 to 1 answer, that i would report "correlation" as $abs(dotProduct-0.5)$ so that things close to either 0 or 1 were treated as important.

Is there a better way? Is my best guess a reasonable approach?

Thanks!

# Answer
> 1 votes
Let's start with comparing two time series. To compare them, you probably want to use cross-correlation. The cross-correlation computes the correlation between signal $f$ and a delayed version of signal $g$, for all possible delays. An efficient way to compute the cross-correlation is indeed by using a FFT, taking the product, and then applying an inverse FFT.

Now suppose you have $k$ time series. I think the best you can do is to compute the cross-correlation between each pair of time series. This requires ${k \choose 2}$ cross-correlation computations.

---
Tags: data-mining, data-sets
---


# Question
Title: What is the complexity class of solving hash decision problems?
With $hash\_n$, I mean a standard cryptographic hash like sha256, scaled up to have arbitrary length $n$ of its output with the same underlying principles. What is the time complexity class of the following problem?

> Given an $n \in \mathbb{N}$ and data $d$ with $length(d) = n$, determine whether $\exists p : ((length(p) \le n) \wedge (hash\_n(p) = d))$.

I find it really hard to find a class for it because it seems like a hard problem and it's definitely not $\in P$ (except if $P = NP$ or there is a vulnerability of the hash function (assume there isn't one not already known (so sha256 basically just printing the state of a state machine can be used, of course))) but you can't use it to solve any of the classical NP hard problems.

Determining the space complexity is of course trivial: It's only $\mathcal{O}(n)$.

This is of course just one example of a hash decision problem and it's meant to only be an example. I'm more interested in the general classification of hash decision problems.

Edit: You may assume a perfect hash function instead of a commonly used cryptographic hash function. E.g. if you're more comfortable with it, you don't want to exploit properties of cryptographic hash functions which are commonly used in practice, what you want to show is threatened by those properties, etc.

# Answer
It's in NP. In particular, it is easy to provide a witness for a yes answer (the witness is such a value $p$) and given a witness, you can verify the yes answer in polynomial time.

As you say, it's not in P if the cryptographic hash function is cryptographically secure.

I don't think it's likely to be NP-complete, but at the moment I can't articulate a specific reason why I think that.

(If you have a one-way permutation, then it's in NP $\cap$ coNP, so unlikely to be NP-complete... but that doesn't apply to your question.)
> 1 votes

---
Tags: complexity-theory, time-complexity, hash, hashing
---


# Question
Title: Complexity class (P/NP) variants of Hamiltonian paths problems
I know that the following problems related to Hamiltonian paths in graph are NP-complete:

* Undirected Hamiltonian circuit:
Given an undirected graph, does it has a cycle that passes through each node exactly once?
* Undirected Hamiltonian path:
Given an undirected graph, does it has a path that passes through each node exactly once?
* Directed Hamiltonian circuit:
Given a directed graph, does it has a directed cycle that passes through each node exactly once?

But then my textbook says following problems are NP-Hard but not NP-complete:

* Problem A: Finding a Hamiltonian circuit in a graph with number of vertices $|V|$ divisible by 3
* Problem B: Determining if Hamiltonian circuit exists in the graphs as given problem A.

Why is this so?

# Answer
> 1 votes
Problem A is not a decision problem. This means that by definition it is not NP-complete.

Problem B is NP-complete. But every NP-complete problem is NP-hard.

Let me remind you the definitions.

NP-complete problem. Problem P is said to be NP-complete if it is in NP and every problem in NP can be reduced in polynomial time to P.

NP-hard problem. Problem P is said to be NP-hard if every problem in NP can be reduced in polynomial time into P.

---
Tags: np-complete, np-hard, decision-problem, complexity-classes
---


# Question
Title: What precisely differentiates Computer Science from Mathematics in theoretical context?
I am a university level student of Computer Science having a great passion to study Mathematics. I have a firm belief that Computer Science or Theoretical Computer Science is a direct branch of Mathematics and Logic and also of the opinion that a Computer Science degree has always to be Math oriented as a matter of fact. Please correct me if I am wrong.

I frankly feel that there isn't a lot of difference in the 2 subjects to be frank as every *"computation"* involves *"calculation"*, although every *"calculation"* might not be a *"computation"*. Again please provide substantial information and evidence and do update me if I am mistaken here. Thank you

# Answer
Theoretical computer science is what theoretical computer scientists do; and mathematics is what mathematicians do. Other than that, there is no accepted definition of either. One might argue that theoretical computer science is a particular branch (or branches) of mathematics, influenced (at least originally) by the problem of efficient computation.

Many areas of mathematics are clearly *not* theoretical computer science, say functional analysis, category theory, algebraic geometry, algebraic number theory, and many others. However, sometimes these areas are *applied* to theoretical computer science. Parts of them might then form part of theoretical computer science, if there is a community of theoretical computer scientists who decided to work on them.

On the other hand, *computability theory* is not necessarily part of theoretical computer science, depending on which community of theoretical computer science one takes as reference. Theoretical computer science (or at least its part known as "Theory A") is traditionally about what can be *efficiently* computed rather than about what can be computed at all.

Many mathematical theorems have no computational content, and in some cases this can be made precise. One example is Kawamura's result that ODEs are hard to solve in general. It is not true that every mathematical proof has constructive content – indeed there are mathematical techniques which are inherently non-constructive, for example the use of compactness or the axiom of choice in any of its other guises.

If you are interested in the computational content of mathematical statements and proofs, you might want to look into *reverse mathematics* and *bounded arithmetic* (sometimes known as *feasible mathematics* or *feasible arithmetic*).
> 18 votes

# Answer
Computer Science is to Software Engineering as Chemistry is to Chemical Engineering.

In fact, most areas of science have one or more engineering disciplines that hang off them. Biology gives rise to Biomedical Engineering, Genetic Engineering, and so on. Physics gives rise to Aerospace Engineering, Electronic Engineering, and so on. There isn't a one-to-one correspondence partly because engineering often relies on more than one branch of science, and the various branches of science aren't really distinct anyway.

The relationship of Mathematics to Computer Science is pretty much the same as the relationship of Mathematics to Physics: it's the language that underpins them both. Theoretical Computer Science could be thought of, pretty much, as a branch of Mathematics. But then, so could Theoretical Physics...
> 8 votes

# Answer
In one phrase, I'd say the distinguishing concern is concern with **computational complexity**.

In math, you're just concerned with possibility and correctness; in TCS, you're worried not just about that, but also the computational *difficulty* of the problem, in terms of time complexity, approximability, space complexity, I/O complexity, and the like.

You may be able to find an odd exception somewhere just like with any rule, but it seems to me that this is pretty accurate overall.
> 6 votes

# Answer
Mathematics is the study of definitions and their consequences; of structures and patterns. Computer science is the art and science of getting things done. A mathematician studies a problem in order to understand the abstract structure behind it. A computer scientist, on the other hand, wants to find a general approach to solving similar problems.

Some subfields of computer science overlap mathematics. Others are closer to statistics, engineering, science, and even social science.
> 1 votes

# Answer
Complementing Pseudonym's answer, I'd add that computer science, like physics, has an experiential component that *pure* math doesn't have, and cannot have.

Differently from physics, the experiential component of computer science has to do with time and space, but as they are engaged by language, a posteriori. That means we are interested in formalize in mathematical terms (because we are scientists) aspects of thought processes that have to do with the experience of language, and in language. Philosophically speaking, this definition is just a conversation starter, but I thought it would be helpful (which is why I decided to post it).

That said, boundaries between neighbouring (or complementary) fields are never absolute. Science is always much richer and more complex than our academic categorizations can express.
> 1 votes

# Answer
Following my conversation in comments with Mehrdad on his answer, I feel I should provide my own answer; there are in fact philosophic sides to this question which admit of a wider interpretation than the classification prevailing amongst modern Computer Scientists.

To address your exact statement (emphasis added):

> I have a firm belief that **Computer Science or Theoretical Computer Science is a direct branch of Mathematics and Logic** and also of the opinion that a Computer Science degree has always to be Math oriented as a matter of fact. **Please correct me if I am wrong.**

Your classification disagrees with Wikipedia and with many modern Computer Scientists, but does that mean that it is *wrong?* Not necessarily. Even Wikipedia itself acknowledges opposing views on this subject, including your own view, which I share.

---

First let's consider definitions. (Emphasis is added.) Each of these excerpts is taken from Wikipedia; links are provided in the first word or phrase of each excerpt.

> Science is a systematic enterprise that builds and organizes knowledge in the form of **testable explanations and predictions about the universe.**
>
> Contemporary science is typically subdivided into the natural sciences, which study the material universe; the social sciences, which study people and societies; and the formal sciences, which study logic and mathematics. **The formal sciences are often excluded as they do not depend on empirical observations.**

And further (from a different page):

> Mathematics (from Greek μάθημα máthēma, “knowledge, study, learning”) is the study of topics such as quantity (numbers), structure, space, and change. There is a range of views among mathematicians and philosophers as to the exact scope and definition of mathematics.
>
> Mathematicians seek out patterns and use them to formulate new conjectures. **Mathematicians resolve the truth or falsity of conjectures by mathematical proof.**
>
> ...
>
> Today, no consensus on the definition of mathematics prevails, even among professionals.
>
> ...
>
> **Many philosophers believe that mathematics is not experimentally falsifiable, and thus not a science....**

And now, as to CS:

> Theoretical computer science is a division or subset of general computer science and mathematics that **focuses on more abstract or mathematical aspects** of computing and includes the theory of computation.

---

According to the Wikipedia article on "Branches of Science,":

> Unlike other sciences, the formal sciences are not concerned with the validity of theories based on observations in the real world (empirical knowledge), but rather with the properties of formal systems based on definitions and rules.

The classification there goes on to specify theoretical computer science as a branch of formal science, *alongside* of mathematics.

However, given the clear fact that mathematics has no generally accepted definition but certainly involves mathematical (formal) proofs, it would *not* be outrageous to include everything in the "formal sciences" classification within the scope of the definition of "mathematics," as you seem to do.

---

My own definitions (classifications) exclude "formal sciences" from the scope of "science," for the above-cited reason that they do not depend on empirical observations.

Further, my own definition of "mathematics" includes within its scope the entirety of the so-called "formal sciences," including Computer Science.

The differentiation I would make between these terms is that *science* is empirical; *mathematics* is based on deductions from primary assumptions.

**The validity of science is based on the accuracy of observations.**

**The *applicability* of mathematics depends upon the applicability of primary assumptions.**
> 0 votes

---
Tags: mathematical-foundations
---


title: The stability of log(1+x)

text:
# Question
Title: The stability of log(1+x)
I am trying to understand why the formula

$$ \frac{\log(1+x)}{(1+x)-1} \times x,$$

which simply reduces down to $\log(1+x)$, is considered as more stable to compute than $\log(1+x)$. In my head it doesn't make sense to me as my brain automatically simplifies it to $\log(1+x)$, which I am guessing a computer doesn't do, but then why does adding in "extra" calculations make it more stable for the computer? My intuition would have been the opposite, the more calculations performed, the more error is introduced. Why is this not the case here?

# Answer
> 6 votes
Consider the case that x is small. (1 + x) has a rounding error; the result that you get is not (1 + x) but (1 + x') for some x' close to x. If x is very small, the relative difference between x' and x can be quite large. Trying to calculate log (1 + x) will calculate log (1 + x') which can have a large relative error. Instead the better formula calculates log (1 + x') / x' * x.

You can just enter both formulas into a spreadsheet and compare with the Taylor polynomial ln (1 + x) = $x - x^2/2 + x^3/3 - x^4/4...$.

Note that it is easy to calculate ln (z) with very high precision when z is close to 1. The damage is done when 1+x is calculated with a small absolute rounding error which turns into a huge relative error, and that's what the modified formula compensates for.

---
Tags: algorithms, numerical-algorithms, numerical-analysis, error-estimation
---


# Question
Title: Closure of regular languages to shuffle using closure operations
Given a language: $L = \\{\\; a\_1b\_1a\_2b\_2a\_3b\_3\dots a\_nb\_n \mid \forall i: a\_i,b\_i \in \Sigma, a\_1\dots a\_n \in L\_1\ , b\_1\dots b\_n \in L\_2 \\;\\}$

Also $L\_1, L\_2$ are regular languages.

Using closure only (homomorphism) prove that L is also regular language.

---

I think there can be a mapping $h\colon (L\_1 \cup L\_2) \to \Sigma$, then use $h^{-1}(\Sigma)$ in order to show regularity. I'm a bit stuck over here.

# Answer
The idea is to create two copies of the alphabet $\Sigma$, say $\Sigma\_1,\Sigma\_2$; each $\sigma \in \Sigma$ corresponds to $\sigma^{(i)} \in \Sigma\_i$. You now show that the following languages are regular: $$ \begin{align\*} \tilde{L}\_1 &= \\{a\_1^{(1)}b\_1^{(2)}\ldots a\_n^{(1)}b\_n^{(2)} : a\_1 \ldots a\_n \in L\_1 \\}, \\ \tilde{L}\_2 &= \\{a\_1^{(1)}b\_1^{(2)}\ldots a\_n^{(1)}b\_n^{(2)} : b\_1 \ldots b\_n \in L\_2 \\}, \end{align\*} $$ where in both cases only some of the letters are constrained. Now take $\tilde{L}\_1 \cap \tilde{L}\_2$ and transform it to $L$.

I leave the rest of the details for you to complete.
> 1 votes

---
Tags: regular-languages, closure-properties
---


# Question
Title: Context-freeness of $\{a^nb^mc^k \mid n \leq m \leq k\}$ and its complement
Was analysing old exam, still, even in home condition can answer this:

> Determine which of the following languages over the alphabet $\\{a,b,c\\}$ are context-free. Prove the claim.
>
> (a) $L\_1 = \\{a^nb^mc^k \mid n \leq m \leq k\\}$,
>
> (b) $L\_2 = \\{a,b,c\\}^\* \setminus L\_1$, that is, $L\_2$ is the complement of $L\_1$ from (a).

Any help would be appreciated, it doesn't seem like CFL to me, but I struggle to apply pumping lemma here.

# Answer
> 1 votes
The language $L\_1$ is not context-free, and you can show this using the pumping lemma. Try to pump the word $a^nb^nc^n$ where $n$ is large enough.

The language $L\_2$, in turn, is context-free. This is because we can write it as a union of context-free languages:

* Words not of the form $a^\*b^\*c^\*$.
* Words of the form $a^nb^mc^k$ where $n\>m$.
* Words of the form $a^nb^mc^k$ where $m\>k$.

---
Tags: context-free, pumping-lemma
---


title: Cofiniteness is $Σ_3^0$-complete

text:
# Question
Title: Cofiniteness is $Σ_3^0$-complete
How can we prove that the language $COF=\\{M\mid L(M)\text{ is cofinite}\\}$ is m-complete for the class $ Σ\_3^0$ ?
I have shown that $COF\inΣ\_3^0$ but I can't prove that $COF$ is m-hard for $Σ\_3^0$ which means that every other problem $L\in Σ\_3^0$ satisfies $L\leq\_m COF$.

# Answer
> 1 votes
Your problem is not so trivial, though classical. See the proof of Corollary 11.9 in lecture notes of Kevin T. Kelly.

---
Tags: computability
---


# Question
Title: how to identify patterns in program execution flows?
Consider a library, that is used by different programs. Under certain (unknown) circumstances, an error can occur. I want to feed execution traces of faulty programs to some kind of an algorithm / framework so it learns about the "pattern" which led to the error. It should then, when fed a live trace, detect when that error will occur and halt the program execution.

So what I have is a list of totally ordered invocations of library functions with their parameters and return value. A simple fault program, where a memory area is used after being freed, may look like

```
mylib_allocate()=0x100
mylib_dosomething() // unrelated "noise"
mylib_free(0x100)
mylib_dosomething() // unrelated "noise"
mylib_set(0x100, 0); // error here

```

So my question is: Are there any existing frameworks that could be fed with that kind of data, which tries to automatically identify patterns from many traces leading to the same error (e.g. "use after free"), and which produces some output which could be used to detect the error (i.e. trigger an event if such an error is going to happen)?

I looked through some data mining approaches, but it seems like they all target "manual" analysis for pattern identification, e.g. by graphic processing to visualize potential "cluster". Then I tried to look at "process mining", but this seemed to be a dead-end as well, because - as far as I understand - my invocation data with an arbitary amount of parameters doesn't fit into that "process" schema. At least I didn't get any reasonable results with ProM.

# Answer
There's probably no existing turnkey solution that will do what you want, out of the box. I suspect this would be a research-level task, so you might want to start by searching the research literature to see if anyone else has tried to do something like this. (Google Scholar is useful.)

If you some advice on how to pursue this yourself, my advice would be:

1. Try to narrow the scope. Rather than trying to detect all bugs, pick a single class of bugs (e.g., use-after-free would be a fine choice) and see if you can have any success detecting those, as a first step. If you're successful then you could broaden the scope.
2. Think now about how you'll obtain enough data to work with. I suspect one of the biggest challenges will be how to obtain a large training set with known labels, that have many instances of in-the-wild use-after-free bugs, as well as many other traces with no instances of those type of bugs, labelled with whether there was a bug or not and which function invocations were responsible.
3. Take a look at association rule learning, sequential pattern mining, grammar induction and automata learning (e.g., my links here; e.g., you might try to learn a small automaton that detects use-after-free bugs), and recurrent neural networks (especially LSTM).
4. Also, you might need to do some feature engineering. For instance, when you have pointers or handles (like `0x100`), you might want to canonicalize them, as the only useful information is whether two calls used the same pointer or a different pointer -- the actual value of the pointer is irrelevant. Since you have domain knowledge of that fact, by transforming the data before you feed it to the data mining / machine learning framework, you can help it learn a lot faster and more effectively.
> 2 votes

---
Tags: algorithms, machine-learning, pattern-recognition
---


# Question
Title: ground terms in logic and $\lambda$-calculus?
What are the differences of ground terms in first-order logic and higher-order logic?

I found on the Wikipedia: "In mathematical logic, a ground term of a formal system is a term that does not contain any free variables."

That mentioned "free variable" is the same thing with free variables of $\lambda$-terms?

I know the closed terms and open terms $\lambda$-calculus. How can we connect closed terms of $\lambda$-calculus with ground terms of logic?

I am bit confused between these concepts, could anyone explain?

# Answer
I think you're basically correct. "Ground term" is more or less the same as "closed term". Certainly the definition you gave is the same as closed term. Personally, I don't think I've seen "ground term" used much for first-order logic or any system with binders. The place where I most commonly see "ground term" used is universal algebra where there are no binders and so "ground term" means a term with no variables at all.

To be pedantic, the notion of "free variable" is used defined when defining the syntax of whatever formal system you're using. As such, the notion is tied to the system being defined. Conceptually, though, the it's the same idea. In the last decade or so, there's been a lot of research in the CS community in capturing and manipulating binders in a languange-agnostic manner so that tools, libraries, and languages can be defined that allow easy definition and manipulation of languages with binders. For example, the languange Beluga and the various "nominal" systems.
> 3 votes

---
Tags: logic, lambda-calculus
---


# Question
Title: Are finite-domain binary constraint satisfaction problems solvable in polynomial time?
> Suppose a CSP has $n$ variables with finite domains of maximal size $d$. Furthermore, all constraints on the variables are binary. Can such a CSP be solved in polynomial time in $n$ and $d$?

This was an exam question on last year’s AI exam, but I’m not sure how to solve it.

I know the problem of graph coloring is easily reduced to such a binary CSP, so solving them is NP-complete. Thus, I’m pretty sure that there is no known polynomial-time algorithm. Can I *prove* that there isn’t one?

# Answer
> 4 votes
I don't know, but if you manage, make sure to let us know.

The reduction seems easy indeed, with $d$ mapping to the number of colors and each constraint to an edge.

However, a polynomial-time algorithm for *any* $\mathcal{NP}$-complete problem exists if and only if $\mathcal{P} =\mathcal{NP}$; doing what you ask would imply $\mathcal{P} \neq \mathcal{NP}$.

---
Tags: complexity-theory, polynomial-time, constraint-satisfaction
---


title: Is this index algorithm worth anything?

text:
# Question
Title: Is this index algorithm worth anything?
I have theorised a indexing algorithm (like a B-tree).

However, there's a mental block stopping me actually implementing it.

The algorithm comes in to forms:

form 1:

A look up time of O(1) to O(log2(n))

Each value in the index will have metadata associated to it that is of the size log2(n)\*memory address size

form 2:

A look up time of O(1) to O(log2(n)/2)

Each value in the index will have metadata associated to it that is of the size log2(n)\*2\*memory address size

**Unlike B-tree/other index algorithms, there's no time penalty for a add/deletion.**

You can for example do a add, then do a search straight after (with no waiting in between).

You get a faster search at the expense of more metadata (memory) along with being able to insert/delete in real time.

You can also do sequential access/search sequential data values fast.

I can't find any other algorithm that has that attributes and time complexity.

If I can get it to work, I plan to sell it.

My question is; would this actually worth anything to anyone/or useful in any particular application?

Or is the amount of memory it uses too much of a deal breaker?

# Answer
> 4 votes
If I understand correctly, you have designed a data structure for what is known in the scientific literature as **dynamic dictionary problem**: keep an index I that can dynamically maintain a set S supporting queries like "is $x \in S$?" under a stream of insertions/deletions.

There are many solutions to this problem. The classical solution is to use a dynamic perfect hash function, which takes $O(1)$ worst case lookup time and $O(1)$ expected amortized update time (it's randomized) and $O(n)$ bits of space.

An arguably more practical solution to your problem is given by Cuckoo hashing, that has the same theoretical bounds of the previous solution but is much easier to understand and implement, and has reportedly better experimental performances.

These solution take much less space than your solution and have favorable time bounds (even if the bound on the update time hold only in expectation).

Moreover, your claim that "add/deletion have no penalty" is unclear to me. If your claim is that an insertion/deletion takes $O(1)$ time, then that's obviously impossible because you cannot build a data structure of size $\Omega(n \log n)$ with time complexity $O(n)$, and if you mean that they take as much time as a look-up, then your solution is no better than any self-adjusting binary tree, like AVLs or Splay trees.

Provided that this problem is well-studied and that there are quite a few high-quality implementations around, I think it is quite hard to design a new competitor that might enjoy commercial success.

---
Tags: algorithms, search-algorithms
---


title: Time Complexity of Sort-Merge Join

text:
# Question
Title: Time Complexity of Sort-Merge Join
According to this German Wikipedia article, the time required to merge relations $R$ and $S$ is $\in \mathcal{O}(|R| + |S|)$ if both relations are already sorted. \[***Note****: You don't really need to read the text and the link jumps right to where the time complexity is stated. But I added a translation of that section to this question for some clarity.*\]

Assume $R = S$ with $R$ having 2 columns. One is a random number and one is always 5 for every line. Join $R$ and $S$ on the column which is 5 for every line. The resulting output's space complexity is $\in \Theta(|R| \cdot |S|)$. Time complexity is always $\in \Omega(\text{spaceComplexity})$.

How can the time complexity stated by the Wikipedia article be true?

---

Here is the "Sort-Merge Join" section translated to English. Sorry, no markdown quote, just everything from here on is the quote. It's translated poorly (not how you would write it in English if you know what you're writing) in some parts to preserve the meaning as well as possible. I marked my own inline comments with `///`.

# Quote of https://de.wikipedia.org/wiki/Joinalgorithmen#Sort-Merge\_Join

## Sort-Merge Join

Both relations get sorted by their join attributes. The result can be determined via a single scan through both sorted relations.

The algorithm is only suited for natural join and equi-join.

### Pseudocode

Implementation of $R\bowtie\_{R.a=S.a} S$ in pseudocode:

```
p_r := first tuple in R
p_s := first tuple in S
while(p_r != endof_r && p_s != endof_s)
    // Collect all tuples in S with the same join attributes.
    M_s := set with contents p_s /// Yes, it says "with", not "of".

    foreach(t_s in S > p_s)
        if(t_s.a = p_s.a)
            M_s += set with contents t_s
        elseif // I think they mean "else".
            p_s := t_s
            break foreach
        endif
    endforeach

    // Seach suitable start tuple in R. /// "passend" can also be translated "fitting" or "matching", not just "suitable".
    foreach(t_r in R > p_r)
        p_r = t_r
        if(t_r.a >= t_s.a)
            break foreach
        endif
    endforeach

    // Output tuples.
    foreach(t_r in R > p_r)
        if(t_r.a > t_s.a)
            break foreach
        endif

        foreach(t_s in M_s)
            Write output: (t_r, t_s)
        endforeach
        p_r = t_r
    endforeach
endwhile

```

### Evaluation

Sorting can be done with effort $\mathcal{O}(|R|\log|R|+|S|\log|S|)$. The number of block accesses to sort $S$ is $b\_s\left(2\log\frac{b\_s}{b\_{free}}\right)+b\_s$ in the worst case, analogous for $R$.

A **merge** of both relations after sorting them costs $\mathcal{O}(|R|+|S|)$. In the best case – i.e. the relations are already sorted –, the costs of merging are the only ones.

In the normal case, the total costs are $\mathcal{O}(n\log n)$.

### Variants

\[Not translated because it doesn't seem to be important for the question.\]

# Answer
> 5 votes
You are absolutely correct. Wikipedia has an error -- or perhaps, if we are feeling more charitable, we could call it an oversimplification.

It is *not* true that the running time is at most $O(|R|+|S|)$. For instance, if we consider the case where the value of attribute $a$ is 42 for all elements of $R$ and $S$, we output $|R| \times |S|$ tuples. It is also easy to see that the pseudocode does $|R| \times |S|$ iterations of the nested inner loop (i.e., that many iterations of the statement "Write output:"), so the running time is also $O(|R| \times |S|)$.

Here are some statements that *are* true:

* If there are no repeated values of $a$ (i.e., each value for $a$ appears at most once in $R$ and at most once in $S$), then the running time for the merge is $O(|R|+|S|)$, and the size of the output is also $O(|R|+|S|)$.
* If any value appears at most $c$ times in attribute $a$, where $c$ is a constant, then the running time for the merge is $O(|R|+|S|)$, and the size of the output is also $O(|R|+|S|)$.
* If we count only the I/O complexity (the number of disk/cache transfer operations), *and* if memory is large enough to hold $|S|$ items, then the I/O complexity is $O(|R|+|S|)$... though the running time and the size of the output might be as large as $O(|R| \times |S|)$. More generally, the same statement is true if any value for attribute $a$ appears at most $k$ times in $S$, *and* main memory is large enough to hold at least $k$ items (here $k$ does not need to be a constant).

So Wikipedia's statement is misleading or wrong or (at best) over-simplified. Perhaps what they really meant was one of the bullet items above. Your understanding is absolutely correct.

---
Tags: time-complexity, database-theory, databases
---


# Question
Title: Detecting approximate sum collisions in two lists.
Suppose two equal-length lists of double precision numbers $A=(A\_1, \ldots, A\_N)$ and $B=(B\_1, \ldots, B\_N)$. Given a constant, $\epsilon \> 0$, I want an efficient algorithm for finding 4-tuples of the form $(A\_a, A\_b, B\_c, B\_d)$ for which $|A\_a + A\_b - (B\_c + B\_d)| \< \epsilon$.

One thing you could do is form the sum sets $S\_A:=\\{A\_j + A\_k\\}$ and similarly, $S\_B$, sort them, and then iterative over these in parallel looking for elements that satisfy the requirement.

This algorithm should have complexity of the form $O(N^2)$ (with perhaps a constant multiplicative factor). Forming the sum sets has complexity $\sim O(N^2)$, the sorting has complexity $\sim N \log N$; the final step is a single pass through both sum sets; also complexity $O(N^2)$.

Is there an algorithm that does better than $O(N^2)$?

# Answer
> 2 votes
I believe there is no known algorithm with running time faster than $O(N^2)$, even if you work with integers and ask for a tuple such that $A\_a + A\_b - (B\_c + B\_d) = 0$ (i.e., is exactly zero).

There *are* algorithms with running time $O(N^2)$ and space $O(N)$. Basically, they iterate through the sum sets $S\_A$ and $S\_B$ in order, without ever storing the entire sets in memory, by using a priority queue.

There are also algorithms that with running time $O(N^{4/3})$, if the numbers are chosen uniformly at random over some range and if you can choose $N$ appropriately (i.e., if the relationship between $N$ and the size of that range can be chosen appropriately) and if you only care about finding one such 4-tuple (even though many might exist). I suspect this probably isn't of use to you.

---
Tags: sorting
---


# Question
Title: computer science vs computer programming?
What's the difference between *Computer Science* and *Computer Programming*? I've spent nearly all my experience with compsci writing programs and what not, and I certainly like it, but I feel like there's a higher level I could pursue, like the ideas precede concrete programming.

I suppose my question is, what does it mean to be a computer *scientist*?

EDIT: I've done some thinking, and I have a *somewhat* more specific question-- what's the difference between the stuff on this stackexchange and the stuff on the cstheory stackexchange?

# Answer
> 3 votes
In some countries, for example in Latinoamerica, I found this "mixing" of terms for careers related to Computer Science, but let's consider that this is not your case and I will venture to pinpoint some differences about CS and CP that you are looking for:

* Computer Science refers to the study of the theoretical part of the use of computers. Of course, that it has also its application part, but this is not directly related to programming. If you search for some articles in ACM you will find that there are a lot of authors that state that CS is not necessarily programming. If you choose this path you will be more studying topics more related to algorithms, math in its continuous and discrete flavors, statistics and so on. So I would dare to say that CS is more related to the fields I described before that only to programming.
* Computer Programming, as I saw in some Universities as I said before, is more related to the technical field (or IT field according to the ACM standards). For example in a career related to this field, you will learn about the differences between Java, C, Ruby, etc., and you will increase your skills of using those tools, but not necessarily you will get a grasp of the generalities that those languages share (for example in CS you have a course called Programming Languages that deal with that).

So bottom line, CS refers to algorithms, math, theory and applications of this theory; while CP is related to the technical aspects of the different IT tools.

# Answer
> 1 votes
Lets use an analogy. Let say a computer program is a Drill. It is a tool used for a specific purpose. It drills hole and screws screws. The computer programmer knows how to assemble a drill. He knows he needs a motor a power supply and a trigger to turn it on and off. The programmer knows how to use the drill and he probably even knows a why the motor spins when electricity is fed through it. The computer scientist designs new a better drills. Making new drills cut through material easier, use less power ect...

There is a large overlap between computer scientist and programmers. Typically computer scientists are focused on areas of research and development (faster search engines, better compression algorithms, better encryption methods, other math heavy stuff) while programmers are focused on practical software development (websites, databases, commercial software. apps).

Even with this overlap I know lots of computer scientists who can't program and I know lots of computer programmers who can't maths.

If you really want to pursue a higher level of understanding I would recommend taking any Statistics, Graph Theory, Number Theory, Dynamic Programming, Analysis or Group Theory course you can find. After all what is Computer Science but applied math.

---
Tags: programming-languages
---


# Question
Title: Coordinates of the center and the radius of the circle on the image
What is the simplest possible way to calculate the coordinates of the center and the radius of the circle on the image (for example BMP and I'm interested in image of the Sun included below)?

# Answer
If you want to automate the process I would use Hough Circle Transform. It is an algorithm used to detect circles in an image. This Wiki article will describe Hough Transform better than I can.

You can manually find the center of a circle using these methods.
> 1 votes

---
Tags: algorithms, image-processing
---


# Question
Title: Is there a correspondence between the syntaxes and the type systems of programming languages?
I was reading the first chapter of Robert Harper's *Practical Foundations for Programming Languages* in which it introduced **abstract binding tree**s, aka *abt*. It seems pretty like typed lambda calculus.

1. There are ground sorts, which are similar to ground types in typed lambda calculus.
2. There are abstractions; they accept multiple arguments. They remind me of uncurried version of lambdas. It's a bit odd that abstractions at the syntax level aren't first-class, though.
3. Later at the end of the chapter in the book, **symbol**s are introduced. They seem to correspond to data types. (Or do they?)
4. *Indexed operator*s are $\Lambda$ bounded terms in the sense of system F.

The author of the book seemed to be aware of the similarities. The set of symbols is even written $\mathcal{U}$ in the book!

What I'm asking is, is there known to be a correspondence of abt's and type systems, or is it too good to be true? Are there more advanced systems of abt's that correspond to system Fω or dependent types?

The question is kind of too broad. Hopefully it can be accepted on this website.

# Answer
> 9 votes
You seem to have a misunderstanding of the purpose of abstract binding trees (ABTs). They are a tool for describing syntax, much like abstract syntax trees (ASTs). They simply allow you to describe syntax that includes binders in a way that generic tooling can be applied. Capture-avoiding substitution, for example, works basically the same way for first-order logic as it does for the untyped lambda calculus, so it would be nice to implement it once and then "instantiate" it to these particular languages. This is what ABTs accomplish.

Just like ASTs, ABTs have little to no semantics on their own, even when instantiated to a particular syntax. An ABT describing the syntax for the untyped lambda calculus is doing just that, describing syntax. Until you add the beta rule, it's not the lambda calculus. Similarly, if I make an ABT for the the syntax of the simply typed lambda calculus, the ABT won't stop me from making ill-typed nonsense. A type checker still needs to be implemented. Indeed, the exact same ABT could be used for very different type systems or semantics. For example, the difference between the linear lambda calculus and the typed lambda calculus is not a matter of syntax. Similarly, the difference between the call-by-value untyped lambda calculus and the call-by-name lambda calculus is entirely in when the beta rule can be applied, syntactically they are identical.

---
Tags: lambda-calculus, type-theory, syntax, syntax-trees
---


# Question
Title: Complete $\mu$-recursive function that is not primitive recursive
Could you find an example of a complete $\mu$-recursive function that is not a primitive function?

# Answer
> 5 votes
There are two standard approaches: diagonalization and rate of growth.

The definition of primitive recursive functions (whichever one you use) allows enumerating them $f\_1,f\_2,\ldots$. Since each primitive recursive function is total, the function $f(n) = f\_n(n)+1$ is recursive. It is clearly *not* primitive recursive.

The other approach is exemplified by the Ackermann function, which is clearly recursive but grows too fast to be primitive recursive.

---
Tags: computability, recursion, primitive-recursion
---


# Question
Title: How to prove Q1 and Q2 are equal using state equivalence algorithm
I was applying state equivalence algorithm in this diagram. On input a and b Q1 and Q2 are going to different states. Which implies the states are not equal according to the state equivalence algorithm. But they are equal and we knows that , right ? Where am I going wrong ? Please help me how to prove these state are equal using state equivalence algorithm

# Answer
> 2 votes
The algorithm is working fine on this DFA. At step 2 you'll get the table as:

```
  1 2
1 G G
2   G

```

`G` is green.

*If there is an unmarked pair (Qi, Qj), mark it if the pair {δ(Qi, A), δ (Qj, A)} is marked for some input alphabet.* Where A is set of all inputs.

{δ(1, 'a'), δ(2, 'a')} = {2,1} = {1,2}
{δ(1, 'b'), δ(2, 'b')} = {1,2}

{1,2} or {2,1} is not marked. Hence move to step 4, *Combine all the unmarked pair (Qi, Qj) and make them a single state in the reduced DFA.*

I prefer the method of partitioning for minimizing the DFA. Consider the following DFA
State transition table for the DFA will be:

```
   0  1
a  b  c
b  a  d
c  e  f
d  e  f
e  e  f
f  f  f

```

Draw 0 equivalent partitions, by separating final and non-final states in different sets.
`[a b f] [c d e]`
Draw 1 equivalent partitions, by taking every possible pair from each set and checking whether their transitions on an input symbol belongs to a single set or not. For example {a,b} on 0 goes to {a,b} and it belongs to a single set \[a b f\], {a,b} on 1 goes to {c,d} which belongs to 1 single set \[c d e\], hence {a,b} are 1 equivalent. But {a,f} on 1 goes to {c,f} and it doesn't belong to a single set, hence they are not equivalent. So separate them. (you can check for {b,f},{c,d},{c,e},{d,e} as well, result will be the same)
`[a b] [f] [c d e]`
Draw 2 equivalent partitions, by repeating the procedure and you'll find nothing is changed. Hence final configuration is reached. Merge \[a b\] and \[c d e\]

In your example:
0 equivalent partitions: `[q1 q2]`
1 equivalent partitions: `[q1 q2]`

Hence they are combined.

---
Tags: automata, finite-automata
---


title: NFA automata with ϵ moves proof

text:
# Question
Title: NFA automata with ϵ moves proof
How can I prove that for every NFA with $\epsilon$ moves if $q\_0 \in F$ then $\epsilon \in L(A)$? I can't think of any technique since it seems so trivial.

# Answer
Use the definition of $L(A)$.

There are several different ones, so let me illustrate with the definition I know. We define a function $\hat\delta$ inductively so that $\hat\delta(q\_0,w)$ is the set of all states reachable from $q\_0$ by reading the word $w$. We then define $L(A)$ as the set of words $w$ such that $\hat\delta(q\_0,w)$ intersects $F$.

Given this definition, we argue as follows. First, the definition of $\hat\delta$ (which I haven't specified) easily implies that $q\_0 \in \hat\delta(q\_0,\epsilon)$. Since $q\_0 \in F$, it follows that $\hat\delta(q\_0,\epsilon)$ intersects $F$, and so $\epsilon \in L(A)$.
> 1 votes

---
Tags: automata, finite-automata, proof-techniques
---


# Question
Title: NP-Hardness of Hamiltonian cycle with $|V|$ divisible by 3
Let **SHAM3** be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $|V|$ divisible by 3 and **DHAM3** be the problem of determining if a Hamiltonian cycle exists in such graphs. Are **DHAM3** and **SHAM3** $\mathcal{NP}$-hard?

What I tried is I proved that the problem of finding Hamiltonian cycle is in $\mathcal{NP}$ and that **3-SAT** problem, which is $\mathcal{NP}$-Complete, is reducible to Hamiltonian cycle problem which makes it $\mathcal{NP}$-hard, but I am not sure what's the purpose of $|V|$ divisible by 3, does that change anything?

# Answer
> 1 votes
There is no "purpose" for the condition that the number of vertices be divisible by 3 – it is part of the problem statement. DHAM3 is the special case of DHAM in which the number of vertices is divisible by 3. In principle this might make the problem easier (a special case can only be easier), but in this case DHAM3 is also NP-hard (and so NP-complete), as you can show by reduction from DHAM.

The problem SHAM3 is not a decision problem and so not eligible to be NP-complete or NP-hard.

How do you show that DHAM3 is NP-hard by reduction from DHAM? You have to come up with an efficiently computable function $f$ that takes an instance $x$ of DHAM and outputs an instance $f(x)$ of DHAM3 in such a way that $x \in DHAM$ iff $f(x) \in DHAM3$. In other words, $f$ takes a graph $G$ and outputs a graph $f(G)$ whose number of vertices is divisible by 3, and moreover $G$ is Hamiltonian iff $f(G)$ is Hamiltonian.

The difficulty here is that the original graph $G$ might have a number of vertices which is not divisible by 3 (otherwise you can take $f(G) = G$). I'll let you figure out how to overcome this difficulty.

---
Tags: np-complete, np-hard, hamiltonian-path, hamiltonian-circuit
---


# Question
Title: Encoding of graphs as an input to neural nets
Given a directed graph $G=(V,E)$ with a node labelling function $l:V\rightarrow L$, how would you encode this best for a neural network?

If it simplifies the problem, we can add the following assumptions about $G$:

* $|V|$ is of fixed size $n$.
* Every node $v$ in $V$ has exactly two successors.
* $l:V\rightarrow L$ is injective; in particular, instead of using node labels, a total ordering of the nodes would be good enough to "infer" the original graph labels.

What I'm trying to learn is a successor selection for every node $v$ in $V$; in other words, a map $m:V \rightarrow V$ with $m$ subset $E$.

Taking all assumptions into consideration, we more or less only have to encode $E$. Obviously, we could use a "two hot encoding" for every node $v$, resulting in a quadratic number of inputs, but is this the preferred way of going about it?

Thanks!

# Answer
So I ask myself this question:

> Suppose 2 encoding contains the same amount of information, that is, all the information about the graph. What factor would make one encoding better than the other in terms of performance of neural nets (trained with the same number of iterations, etc)

The my personal answer to that is:

Trained neural net (in its simplest version) is just a linear function of its input. So, do you suspect that the function you want to learn can be expressed as a linear function of the input? And this is where the choice of encoding makes a difference.

My stance on these kind of algorithm is that. Ultimately, if you want it to perform well, you need to have a good hypothesis on what kind of function your answer should actually be.
> -1 votes

---
Tags: graphs, machine-learning
---


# Question
Title: Why proving programs correctness doesn't have the same importance as algorithms analysis or the theory of computation in practice?
What are the major causes that makes "Proving Programs correct", not a widely attractive subject? though from it's name, and from what we know from other disciplines (like mathematics) it looks like it should be on the top of the "must know list". And by the way I'm talking about "the real world", in practice.

# Answer
> 9 votes
On the contrary, it's certainly important practice, and is a huge area of research!

Perhaps a better question might be, "why is proving programs correct not common in practice, or not a main feature of an undergraduate curriculum?"

There's a few reasons for this:

* Proving programs correct is hard. The proofs often end up being long and tedious proof-by-cases, and will usually have less interesting intellectual content that you'd see in most math proofs.
* You need a formal semantics for whatever language your program is specified in. For real world programming languages, developing such a semantics is often difficult, since there are possibly corner cases or odd compiler behaviors that are difficult to model
* Proving a program correct only proves that it matches a given specification. What if there's a bug in the specification?
* Proving a program correct assumes that it's being compiled by a correct compiler, or run by a correct interpreter, which almost never the case.

Things also change by what you mean by a "program". For example, in real world algorithms research, almost every time someone publishes a new algorithm, they will provide a proof of correctness. Usually this is working on pseudocode with a simple but straightforward semantics, so lots of the formal details from above aren't an issue.

Also, just to counter your claim that it's not an area of research:

* The entire field of Dependent Types is focused on proving real, running programs correct using type theory. There are lots of great projects in this area, like DeepSpec.
* Formal methods is an entire field devoted to proving program correct, usually adapting methods from hardware verification to software.

---
Tags: proof-techniques, correctness-proof
---


# Question
Title: Graphs that are connected vs strongly connected vs reachable
What is the difference between "connected", "strongly connected", and "reachable" in a graph?

# Answer
**Connected**: Usually associated with undirected graphs (two way edges): There is a path between every two nodes.

**Strongly connected**: Usually associated with directed graphs (one way edges): There is a route between every two nodes (route ~ path in each direction between each pair of vertices).

**Reachable** (from $A$ to $B$): A path exists in the graph between nodes $A$ and $B$. (Ability to get from one vertex to another)

Note: Got some terminology from: https://mathoverflow.net/questions/6833/difference-between-connected-vs-strongly-connected-vs-complete-graphs
> 5 votes

---
Tags: graphs
---


title: Operation on binary tree

text:
# Question
Title: Operation on binary tree
I would like to confirm below understanding,

> A **binary tree** is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
>
> ##
>
> **Insertion:**
>
> In binary trees, a new node before insert has to specify 1) whose child it is going to be 2) mention whether new node goes as left/right child. For example(below image),
>
> ---
>
> To add a new node to leaf node, a new node should also mention whether new node goes as left/right child.

---

> **Deletion:**
>
> For deletion, **only certain nodes** in a binary tree can be removed unambiguously.
>
> Suppose that the node to delete is node A. If A has no children, deletion is accomplished by setting the child of A's parent to null. If A has one child, set the parent of A's child to A's parent and set the child of A's parent to A's child.
>
> In a binary tree, a node with two children **cannot** be deleted unambiguously.

---

Is this understanding correct ?

# Answer
> 1 votes
Its hard to say without the knowledge of why a node goes to the left or right of another, and if this carries as a property throughout the tree. If by ambiguously you mean there is more then one valid way of replacing the node and the tree has an ordering structure (such as a binary search tree) then your understanding is correct. The deleted verticie can be replaced with either its in order predecessor, or its in order successor. Both of these will be valid with the ordering property.

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


# Question
Title: What are some of these "high-level" instructions found in CISC architectures?
The Wikipedia article on complex instruction set computing says

> Before the RISC philosophy became prominent, many computer architects tried to bridge the so-called semantic gap, i.e. to design instruction sets that directly supported high-level programming constructs such as procedure calls, loop control, and complex addressing modes, allowing data structure and array accesses to be combined into single instructions.

What do these "high-level" instructions that can handle loops look like? What does an instruction for a procedure call (strikes me as something of a nebulous term to use here) look like? Can a loop instruction be strung together with multiple instructions for multiple conditions like in a C loop? Does "procedure call" mean something like an instruction that can pass parameters to a function? "High-level" means nothing here without examples.

# Answer
> 2 votes
I know of two main aspects of complex instructions.

* addressing modes. There are two sub-aspects here:

+ RISC tend to be load/store machines (that this the only instructions which access memory are those whose sole goal is that access), CISC tend to allow operands to be in memory and to be accessible with a variety of addressing modes. When each operand can have an independent addressing mode like on the VAX, that make the instruction complex.
    + the addressing modes of CISC tend to be more complex than those of RISC. When, like the PDP-10, the number of memory access needed to determine the true operand is unbounded, it makes the instruction complex.
* the instructions themselves. That's what you are probably thinking about. Setup of complex stack frames with automatic saving of registers, which register to be saved being determined by a bitmap (see VAX) and other complex context switching state mechanism (see 80386 task gate or whatever their name is), polynomial evaluation (see VAX), insertion in a linked list (I don't remember where I've seen that and don't want to dig it out, VAX and PDP-10 are candidates), it is folklore (I don't know how true it is) that some machines in the IBM 360 family had instructions who where designed for the only usage of improving their Cobol library sorting function.

I think they all can be regrouped with one characteristic: complex instructions are those who need to do a relatively large (and I'd not argue strongly against defining large as being greeter than one), sometimes variable number of memory accesses. That characteristic brings true nightmare:

* you need a relatively complex state machine to handle them, and to decide how to handle interrupts during the time they execute;
* you need to be handle multiple page fault (in simple instruction you have two: one for the instruction, one for the data memory) which means that they may be interrupted and resumed for internal reasons several times, making the first issue more important.

# Answer
> 1 votes
Mapping high level language concepts to instructions has gone out of fashion (because of a multitude of problems that it causes, which make code using these instructions slower nowadays).

What has become fashionable is instructions that can be used as building blocks for very specialised purposes, for example encryption/decryption and searching strings. For example Intel processors have an instruction doing the following: Given the first up to 16 characters of a string A, and the first up to 16 characters of a string B, find the smallest index i such that the string B might match the characters of string A at offset i.

Example: A = abcdxyzxaaaaaabc, B = abcde, result is 13 because the characters from offset 13 (abc and more characters that we don't know) might match abcde. B = vvvv, result is 16 because the characters of A from offset 16 (which we don't know at all) *might* match vvvv.

This instruction compares up to 136 pairs of characters and can make finding a substring very efficient.

# Answer
> 1 votes
CISC and RISC acronyms used to describe instruction sets were popularized many years after computers following these styles were designed. (A bit like "baroque" or "classical" styles which were named centuries later)

The way computers were designed and the constraints on the instruction sets were quite different when using discrete transistors, LSI, MSI or high integration chips.

One important aspect to understand for the traditional complex CISC instructions is that before the 80's, high performance computers were made of dozens or hundreds of ICs connected together. And the coordination between all these parts was made by microcode.

Microcode allows to create complex sequencing. And that sequencing was necessary because chips were very expensive : The same adder was used for the ALU, for calculating addresses, ... Instructions last many cycles.

So, once you have a lot of microcode in a programmed ROM for sequencing everything in the CPU, the additional cost for adding very complex instructions is low.

Additionally, having complex instructions allows to save some code RAM (and RAM was very expensive), and run faster (microcode accesses were faster than fetching code in RAM).

Contemporary processors try to avoid microcode or reserve it to rarely used instructions. Even for the CISC x86, modern CPUs transform most instructions into 1 or 2 elementary operations.

Some CISC examples : DEC VAX, IBM System 360, Data General Eclipse.

(http://stephenmerrony.co.uk/dg/Docs/DG-Originated/Software/EclipseMV-Family32-BitSystemsPrinciplesOfOperation.pdf)

The microcode was sometimes extensible, reprogrammable, or partly in RAM.

Some instructions that were complex in the 70's, as floating point instructions, are now implemented by brute force using huge pipelined multipliers, adders, ... Another example are bit field insertion and extraction instructions which were sequenced and now implemented with barrel shifters.

Obsoleted instructions are those that used complex indirect addressing, function calls with automatic copying of parameters (present in x86 call gates), decimal, ASCII (or other character encoding) instructions, queue/linked list management. Some CPUs even had graphic instructions as bitblt (copy/fill a rectangle) or line drawing directly written in microcode.

Nowadays, the instruction sets of modern RISC CPUs as ARMs or IBM POWER is arguably more complex than ever, and every year new instructions are added, for multimedia, crypto... The difference with traditional CISCs is that they are not designed to be microcoded as a long sequence of calculations or memory accesses.

---
Tags: computer-architecture
---


# Question
Title: How to determine enumerability after applying Rice's theorem?
To my knowledge, lots of languages can be classified as undecidable after applying Rice's theorem, for example {"M" | L(M) is regular}.

But what I am not sure is, how to determine if a language is enumerable after applying Rice's theorem? I reckon we can examine that whether the M halt on some specific input, i.e. test if L(M) is an empty set. Am I right? Is there any principled way to determine a language's(composed of lots of Turing machines) enumerability?

# Answer
> 2 votes
You can use the fact that if $L$ is undecidable and $\overline{L}$ is enumerable then $L$ is not enumerable (since if both $L$ and $\overline{L}$ are enumerable, then $L$ is decidable). In order to determine whether an undecidable language is enumerable or not, you can try to construct an enumerator for the language or its complement.

# Answer
> 1 votes
In addition to Yuval's approach You can also read about monotonic and non-monotic properties of languages as well. This statement usually an extension to Rice theorem says :

“Every non-monotone semantic property

of Turing machines is unrecognizable”

---
Tags: computability, rice-theorem
---


title: Determining Asymptotic Tight Bound

text:
# Question
Title: Determining Asymptotic Tight Bound
Let's say I have an algorithm, MyAlgo(n) as follows:
for i: = 1 to n do
(something)
Where in the i-th iteration, (something) executes i^2 steps.
How can I determine an asymptotic tight bound (Big-Theta) on the running time of this algorithm? I know I have to determine Big O and Big Omega, but since the actual algorithm isn't shown, I don't know where to start.

# Answer
If the number of steps executed in the $i$th iteration is $i^2$, then the number of steps overall will be asymptotic to $$ \sum\_{i=1}^n (C+i^2) = \Theta(n^3), $$ for some constant $C$ that comes from the loop control (i.e., incrementing $i$ and checking whether it equals $n$).

To see that $\sum\_{i=1}^n (C+i^2) = \Theta(n^3)$, use $$ \sum\_{i=1}^n (C+i^2) \leq n(C+n^2) = Cn+n^3 = O(n^3), \\ \sum\_{i=1}^n (C+i^2) \geq \sum\_{i=n/2}^n i^2 \geq (n/2) (n/2)^2 = n^3/8 = \Omega(n^3). $$ (In fact, $\sum\_{i=1}^n i^2 \approx n^3/3$, as can be seen by approximating it by the integral $\int\_1^n i^2 \\, di$, or by using the exact formula $\sum\_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$.)
> 2 votes

---
Tags: time-complexity, asymptotics, runtime-analysis
---


# Question
Title: Compute pair of similar list from a collection of lists
Given a list of list of integers how to find pair of lists which have overlapping i.e. 1 or more elements are common.

Is it possible to solve without having cartesian product of initial list with itself

# Answer
Build a hash of element -\> list of lists that contain that element. From that it's easy to find all pairs of lists that share an element. Of course listing all pairs is still $O(n^2)$, since there might be quadratically many. But finding just $k$ pairs is $O(k+m)$, where $m$ is the total number of elements in all sets.
> 2 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: Using two hash functions for increased password security?
Forgive me for my brief knowledge on hash functions as I am not from a computer science background, however I am researching password security for my thesis and have been looking into hashing functions for password security. I understand that a password goes through a hashing function and is stored in a separate database, at which point if the user enters the same password at a later date, that entry is then ran through the same hashing function and checked the output is the same. My question is, if lots of companies are being breached and passwords have been found out using the algorithms, would it be more secure to then use a second hashing function on the already hashed password and store all the password entries 'double hashed'?

# Answer
> -2 votes
Current best practice goes like this: Step 1, the password is combined with a random sequence of characters (the "salt"), which means that even if two users use the same password, the combination salt + password will be unique for each user, and cracking one combination salt + password does *not* help at all cracking anyone else's password. Step 2, the combination salt + password is hashed using a cryptographic hashing function, but not once, not twice, but a gazillion times so that calculating the hashed password takes a significant amount of time. Step 3, the salt is stored, but the hashed password is not actually stored, but used to encrypt a master password for that user which is required to decrypt that user's information.

The hashed password is not stored, so someone who manages to steal the complete information on the server still cannot access any user's data. To steal one user's data, an attacker has to guess passwords. Turning each password into a hashcode takes significant amounts of time, so cracking just one good (hard to guess) password should be very hard to crack. And that's just one password.

# Answer
> 2 votes
Simply hashed passwords *are* susceptible to brute force or rainbow table attacks. Hashing the passwords again will simply increase the cost of computing an entry in these tables (by one hash), but that is not an appreciable increase in the challenge of cracking them.

Several techniques available in practice including salt ing the password, wherein you prepend the password with a random substring (known as the *salt*), which you also prepend (in plaintext) to the hash. So, whereas a password "hello" might hash to h("hello"), the salted password would be foo || h("foo" || "hello"). If "foo" is random, then this means that I may need to store all possible salted hashes for a given password in order to crack it.

To complicate the crack-ability of the password hash even further, one may add a pepper, which is a random (but not published) string prepended to password before hashing. Checking a password in this case requires checking all possible peppers with a given password to see if any hash to the stored hash value.

# Answer
> 0 votes
Password is not always in a separate database (but that is a good practice). It many just be in another table.

A double (or more) hash is not really more secure. It just takes a brute force attack longer.

Salt a password makes is harder to crack as cannot use a dictionary attack. A brute force attack is required on every password.

Most of these security breaches is not password. They just copy (steal) user data (e.g. credit card number). The breach is the hacker somehow got direct access to the database.

# Answer
> 0 votes
> I understand that a password goes through a hashing function

That is correct!

> ... and is stored in a separate database ...

Implementation dependent but yes definitely could be.

> ... at which point if the user enters the same password at a later date, that entry is then ran through the same hashing function and checked the output is the same ...

Back in the days of ye'old security this would be true. Modern security requires a more secure method!

**The problem with unseasoned hashes**

Lets pretend your the administrator of a database with 100 million users.

This is an example of your password database:

Jeff and Adam have the same hashed password!

This means there is a very high likely hood they have the same password.

Since Adam's hint is good enough to determine what the actual password is. Jeff is also compromise and so is everyone else who used the same password!

**How to prevent this**

Salt your hash!

When a user creates their account assign them a randomly generated string called a 'salt'.

Store this salt alongside the password in the database.

You will need a deterministic way to mix the salt with the hash. A simple way is to simple concatenate the salt on the end of the users password.

```
bool isPasswordValid(string const username, string const userGivenPassword){
    string const hash = magicDataBaseLookupHash(username); //Get hash associated with user
    string const salt = magicDataBaseLoopupSalt(username); //Get salt associated with user
    return myHashFunction(userGivenPassword + salt) == hash; //Test if hash matches
}

```

**Your Original Question**

> My question is, if lots of companies are being breached and passwords have been found out using the algorithms, would it be more secure to then use a second hashing function on the already hashed password and store all the password entries 'double hashed'?

Yes it is. If done correctly.

As long as the hashes preserve Entropy the password will be more secure as it requires more iterations of hash functions to crack it.

However this comes with a trade-off!

It takes more processing power on your end every time someone tries to log-in.

So it's your decision as an Administrator to determine if you need more security or or less overhead on user login (generally results in a worse user experience).

**Just remember your security is only as strong as the weakest hash.**

Consider the following pseudo code:

```
hashOne( hashTwo( hashThree ( ...  hash5million(password)   ... ) ) );

```

If hashFive (or any of them) always returns "1" then any password will work for any user.

---
Tags: security, hashing
---


# Question
Title: How does the halting theorem interact with the recursion theorem?
Recursion theorem (paraphrasing Sipser, Introduction to the Theory of Computation):

Let T be a program that computes a function t: N x N --\> N. There is a program R that computes a function r: N --\> N, where for every w,

```
        t(<R>, w) = r(w)

```

The proof is by construction. The program R thus constructed computes the same thing as program T with one input fixed at \<R\>. But what if the right side does not compute anything? In that event we can reason as follows:

```
T(<R>, w) halts  <-->  R(w) halts

```

and by modus tollens

```
T(<R>, w)  does not halt  <-->  R(w) does not halt

```

In particular we have

```
R(w) halts  --> T(<R>, w) halts
T(<R>, w)  does not halt  --> R(w) does not halt

```

The transposition is based on the table below

T(\<R\>, w) halts\__________________R(w) halts

```
   T                         T
   F                         F

```

But what if the value in the right column is unknown and unknowable?

T(\<R\>, w) halts\__________________R(w) halts

```
   T                         T
   ?                     unknowable
   F                         F

```

We know that there is no universal halting decider, so the value in the right column may be unknowable to a given decider. So what if the decider concludes that T(\<R\>,w) does not halt? Is there anything wrong with the table below?

T(\<R\>, w) halts\__________________R(w) halts

```
   T                         T
   F                     unknowable
   F                         F

```

In particular is there any compelling reason that if the value in the left column is F that the value in right column must also be F, i.e. that it cannot remain unknowable? It seems to me that if T(\<R\>, w) does not halt then it does not imply anything.

Is it possible for a decider to say \[for some T\] that T(\<R\>, w) does NOT halt yet remain agnostic about R(w) halting??

# Answer
The recursion theorem states that for every two-place *partially computable* function $t$ there is a program $R$ which computes a *partial function* $r$ satisfying $$ r(w) = t(\langle R \rangle, w) $$ for all $w$. The function $t$ is given by a program that doesn't necessarily halt, and so we can think of it as a function from $\mathbb{N}^2$ to $\mathbb{N} \cup \\{ \bot \\}$, where $\bot$ means that the program doesn't halt. We call such a function a *partial function*, since a different way of specifying such a function is as a function from some *subset* $S \subseteq \mathbb{N}^2$ to $\mathbb{N}$; the function doesn't halt on inputs outside $S$.

The equality $r(w) = t(\langle R \rangle, w)$ is an equality of partial functions: the functions have the same domain (or the same set of inputs on which the output is a natural number rather than $\bot$), and they agree on their domain.
> 1 votes

---
Tags: computability, halting-problem
---


# Question
Title: Why can level-triggered interrupts be shared but not edge-triggered interrupts?
> A key difference between the edge-triggered and level-triggered interrupts is interrupt sharing. **Level-triggered interrupts can be shared. Edge-triggered interrupts cannot be shared**.

I read the line above in an IBM document. Need help to understand why is it so.

# Answer
Consider the scenario where an interrupt IS shared by two devices with the following scenario:

1. Device 1 requests service.
2. The processor starts serving device 1.
3. Device 2 requests service.
4. Device 1 no longer requests service.
5. The processor finishes serving device 1.
6. The processor starts serving device 2.

Here device 1 will assert an interrupt request in step 1. It de-asserts that request in step 5, but the request remains asserted due to step 3.

Now in step 6, if level triggered requests are used, the processor will service the other device since the request level is still asserted. With edge triggered requests, nothing will happen because there will be no new "edge" to be detected. The request remained asserted throughout the scenario. This is a failure of the interrupt system.

This is why only level triggered interrupts, in general. may be shared.
> 2 votes

---
Tags: computer-architecture, operating-systems, cpu
---


# Question
Title: every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar
Here is one discussion that says, "every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar."

And wiki says, "a language can be generated by an LR(k) grammar if and only if it is deterministic \[and context-free\], if and only if it can be generated by an LR(1) grammar"

Is the first statement in that discussion forum is correct?

I found wiki statement at many places but nowhere I found the first statement except in that discussion.

Please tell me if first one is correct or not, and If possible provide some source that confirms this statement. Thanks in advance.

# Answer
> 4 votes
The linked discussion thread comes from `comp.compilers`, which at one time was the definitive discussion forum for questions of this form (disclaimer: I was a constant reader and occasional contributor to that forum, so my opinion might be biased.)

The rather interesting discussion thread in question dates from October 2002, and was an attempt to discover if there were unambiguous languages (*not* grammars) which could not be parsed with any $LR$ algorithm. In the course of the discussion, Sönke Kannapinn noted that the $LR(k)$, $LALR(k)$ and $SLR(k)$ sets of *languages* are identical, for all $k\ge 0$. (That's the message cited in the question, but in a more readable presentation.)

Kannapinn cites the source of his assertion: the 1990 text *Parsing Theory Vol II* by S. Sippu & E. Soisalon-Soininen, which definitely should be considered a "standard" textbook (as Kannapinn notes in an earlier message in the same thread). The question is addressed in Chapter 6.6 (*SLR(k) Parsing*, from pages 70-84), which terminates with Theorem 6.71:

> *For any fixed $k\>=0$, the families of $LR(k)$ languages, LALR(k) languages and SLR(k) languages are all equal.*

The proof is too long to reproduce here, but the textbook should be available in any good university library. (If it isn't, demand that they acquire it.)

Coincidentally, there was another similar discussion thread the next year, in which I offered a simpler proof outline. I reproduce it here (without modification aside from an attempt to fight with MathJax and Markdown to make it a bit more readable), in case it's useful to someone, although of course it might be wrong since discussion posts in comp.compiler are not subject to the thorough review accorded to Springer Monographs. So if you find an error, let me know, and if you find the formatting ugly, feel free to fix it.

> Take an $LR(1)$ grammar $$G = \<N, T, P, S\>$$ and create $$G' = \<N', T, P', \<S,\\$\> \>$$ where $N'$ is a subset of $N \times T$ (that is, the non-terminals in G' are the cartesian product of the original non-terminals and the original terminals.) $N'$ and $P'$ are constructed basically with the LR construction: Start with $N' = \\{\<S, \\$\>\\}$ and repeat the following until no new non-terminals are added: * Let $\<A, a\>$ be an element of $N'$ for which there are no productions in $P'$. Now, for each production in $P$ of the form: $$A \to w\_1 w\_2 ... w\_n$$ add all possible productions $$\<A, a\> \to w'\_1 w'\_2 ... w'\_n$$ where $$w'\_i = w\_i \text{ if } w\_i \in T$$ $$w'\_i = \<w\_i, b\> \text{ for each } b \in FIRST(w\_{i+1}...w\_n ++ a) \text{ if } w\_ \in N$$ The second definition is multiple valued, so you might have to add a lot of rules :)
> * Furthermore, if any new rule mentions a non-terminal $\<W, w\>$ which is not yet in $N'$, add it to $N'$
>
> It is clear that this must terminate, because all the sets are finite. Also, the function $FIRST$ used above never yields epsilon.
>
> Now, I assert that $G'$ recognises exactly the same language as $G$, and furthermore that if $G$ is $LR(1)$ then $G'$ is $SLR(1)$, because it is impossible to have a reduce/reduce conflict between $\<W, a\>$ and $\<W, b\>$.
>
> Of course, all this has done is move the lookahead sets into the definition of the non-terminals, so the resulting $SLR$ table is going to be just as big as the original $LR$ table (bigger, actually, since no merging of lookaheads has been done), but I think it does answer the original question.

---
Tags: formal-languages, context-free, formal-grammars
---


# Question
Title: Time complexity of a greedy approach for Independent Set: the Heaviest-First Algorithm
The heaviest-first algorithm is a greedy approximation algorithm that finds an independent set $S$ of nodes in a graph $G=(V,E)$, so that the sum of the weights of the nodes in $S$ is as large as possible.

My question is that I want to find the time complexity of the following algorithm (when applied on $N \times N$ grid graphs):

# Answer
Let's analyze the runtime. In each iteration of the loop we look for the maximum weight node. If you do this naively, you look at all nodes. By using a clever data structure you could speed this up. Adding the node to S takes constant time for all reasonable set data structures. Now we remove $v\_i$ and its neighbors. This can be done in time proportional to the number of incident edges at $v\_i$ and at its neighbors, for reasonable graph representations, e.g. an adjacency list.

In your comment you stated that you had problems analyzing the algorithm because you didn't know the number of iterations of the loop. You could conservatively assume that you remove only $v\_i$ itself to get a runtime of $O(|V| \times $finding the max$)$, so $O(|V|^2)$. Since $G$ is a grid graph, each node has degree at most four. So even if you assume optimistically that you remove five nodes in each iteration you get the same asymptotic runtime.
> 0 votes

# Answer
The running time of adding a vertex to the independent set $S$ is $O(1)$ if you use an appropriate set data structure, such as a linked list, an array, or a dictionary. Also, deleting a vertex $v$ from $G$ (once you have identified the vertex) takes time proportional to the number of neighbours, which, in this case, is bounded above by a constant ($4$), so it also takes $O(1)$ time.

The running time of your greedy algorithm will, therefore, be dominated by the costs of the **maximum-weight vertex computations**. I can think of three ways to implement this operation:

* **Naive approach - $O(|V|)$**: identifying the maximum-weight vertex of a graph takes linear time in the number of vertices if you explore all of them.
* **Priority queue - $O(log \\: |V|)$** : since you are doing repeated maximum computations, it makes sense to use a priority queue, which allows you to extract the maximum element in logarithmic time.
* **Sorted array - $O(1)$** : the maximum-weight vertex of a graph can be identified in constant time if you sort the vertices by weight beforehand.

The number of times that the algorithm computes the maximum-weight vertex is equal to the number of iterations, which is $O(|V|)$. Therefore, the naive approach takes $O(|V|^2)$ time and the priority queue based solution takes $O(|V| \\: log \\: |V|)$ time. In the sorting-based solution, each iteration takes $O(1)$ time; however, the overall running time is not $O(|V|)$, but, rather, $O(|V| \\: log \\: |V|)$ because the running time is dominated by the sorting operation.
> 1 votes

# Answer
We can't say what the runtime of your "algorithm" is because it is not a complete algorithm - too many non-trivial things that can be done in different ways.

It can be done quite trivially in O (n log n + v), where n is the number of nodes and v is the number of vertices. Sort the nodes by weight in O (n log n). Then iterate through the nodes from heaviest to lightest: If a node is not marked as "removed" then add it to S and mark its neighbours as "removed". You will try to remove at most v nodes (actually the number of neighbours of the heaviest nodes that you find).

The number is actually less than n log n + v, because when you remove a node with many neighbours, the number of remaining candidate nodes gets a lot smaller as well.

The n log n can likely be made smaller: Start sorting with Quicksort, but only sort the parts of the array with larger values. Then you can start removing the heaviest nodes, and as you do that, nodes are removed from the array, so you don't have to sort everything.
> 0 votes

---
Tags: graphs, greedy-algorithms
---


# Question
Title: Coercing a list of nodes into the most probable tree
Suppose that we have an RTF document which contains sections and sub-sections. The sections and subsections all have headings that are visually marked up (e.g., bold and italic), but the document structure is not made explicit (i.e., we have a linear flow of text). From the section headings, we wish to automatically determine the most likely document structure.

For titles on the same sectioning level, we know that they probably have the same kind of markup, and they probably increment in numbering, but we don't know *exactly* what they should look like (e.g., **bold**/*italic*; arabic/roman; how deep subsectioning goes), and their relatedness may be fuzzy (the author might forget a number in a sequence, for instance *1. First section*, *Second section*, *3. Third section*).

To make things more explicit, we can assume assume that we have a features vector *fs* with a fixed number of features, that combines linearly into a fitness function f(*fs*) = *w₁ f₁* \+ *w₂ f₂**wₙ fₙ*, given a weight vector *ws*. The fitness function is arbitrary, this is just to make the problem explicit.

So from list *G*:

We wish to create a tree *G'* such that:

* *G'* maintains the preorder relations of *G*
* *G'* maximizes some fitness function f(*G'*), where f calculates how alike nodes are that are children of the same parent (same markup; incrementing numbering).

<sup>(root not displayed)</sup>

---

My question: does this problem reduce to another well-known problem?

---

This problem reminds me of a lot of stuff I've seen before, from finding the best path through a DAG to hierarchical clustering, except nothing seems to hit the sweet spot in terms of describing or solving the problem. I guess it's closest to the problem of finding the minimum spanning tree, except calculating the spanning tree score is not as straighforward.

---

I have thought of my own solution, but I was surpirised that I could find no resources that deal with this problem exactly.

My solution would be a dynamic programming algorithm that attaches a score to each possible tree as a linear function. (Meaning we can cache subtrees without re-calculating everything.) We can learn the constants of our function using some expectation maximization algorithm based on existing document structures.

# Answer
In the end, I ended up solving my particular problem using Stochastic Context Free Grammars.

There may be some additional cost incurred for production, or otherwise probability operations that you can't express in the CFG. The probabilistic Earley algorithm (Stolcke, 1995) allows us to intervene in the parsing process somewhat by producing callbacks on scannning a token (or predicting / completing).

I have arbitrarily chosen my rule probabilities, but you can train them using the inside-outside algorithm, although that will probably mess up the the soundness of any probability-tinkering callbacks.

---

Practically, this question lead me to create a Probabilistic Earley Parser for Javascript and for Java. These libraries only allow the user to multiply scan probability given a token at a position the sentence, but it is easy to add other callbacks with more information. Please create an issue in Github if you need this. Also, these libraries do not support training a grammar on a test set (inside-outside), because I did not have time to implement this.

For an exposition of my use case, consider the chapter in my master thesis *Automatic Assignment of Section Structure to Texts of Dutch Court Judgments*, *Inferring a Section Hierarchy*
> 1 votes

---
Tags: algorithms, graphs, optimization, trees
---


# Question
Title: Find Number of elements X in the Tree that lie between a and b
**Question**

Suppose there is a balanced binary search tree with n nodes, where at each node, in addition to the key, we store the number of elements in the sub tree rooted at that node.

Now, given two elements a and b, such that a$\<$b, we want to find the number of elements x in the tree that lie between a and b, that is, $a≤x≤b$ This can be done with (choose the best solution).

* O(logn) comparisons and O(logn) additions.
* O(logn) comparisons but no further additions.
* O(√n) comparisons but O(logn) additions.
* O(logn) comparisons but a constant number of additions.
* O(n) comparisons and O(n) additions, using depth-first- search.

**My Approach**

Now there are two possibilities,

1. $b$ can be in the right subtree of $a$

We simply search for b, in the right subtree of aa and at each step we add the number of elements in the left subtree +1 (BST being balanced, this can be retrieved from the depth of the node without any finding method), if we are moving right and simply 1 if we are moving left. When we find $b$, this sum will give as the required number of elements. This requires $O(logn)$
2. $b$ can be in the right subtree of any of the parents of $a$.

For the second case also we do the same method. But first we find the common ancestor of $a$ and $b$ (possible in $O(logn)$\- say $p$ and also count the no. of nodes in the right subtree of each node from $a$ to $p$ excluding $p$. Now, from $p$ to $a$ we proceed the counting as in the earlier case when $b$ was in the subtree at $a$. So, in the worst case we have to do $O(logn)$ additions

How to make use of the nuber count more efficiently than this ?

Answer is given by my professor is

> O(logn) comparisons but a constant number of additions.

Please elaborate the efficient approach using neat diagrams for clear cut understanding for both (when $b$ is right subtree of $a$ and $b$ is right subtree of parent of $a$ )

# Answer
> 1 votes
We may assume without loss of generality that the lowest common ancestor of $a$ and $b$ is the root. Let $S = \\{x \in T| key(a) \le x \le key(b) \\} $. Observe that $|S| = |T| - |\bar{S}|$, and that $|\bar{S}|$ is the sum of the sizes of the left subtree of $a$ and of the right subtree of $b$.

---
Tags: algorithms, time-complexity
---


# Question
Title: Real time application with DFA or NFA application
Can anyone here give an example of DFA or NFA **real time application**?

And, can I know what are **complexity and decidability problems** in real time application? Does every real time application have **complexity and decidability problems**?

# Answer
DFA/NFA in a real time application ? consider designing a parser for user inputs where each input is a word w="http://some-address.com?key\[1\]=value1&key\[2\]=value2..."

consider having each key\[i\] as the string ##i now you can easily build a regex /##./ to accept all input-strings having key values contained in w.

Since we have a regular expression that recognize this pattern there exists an equivalent NFA that recognizes such words, now your parser server can recognize http requests that holds information valuable to your application and distinguish them from normal static requests for pages/images.

There is a big difference from Complexity to Decidability problems, Decidability problems is a question whether for all inputs w the algorithm A will halt and yield a result, Not every problem is Decidable (i.e loop to infinity doesn't halts), moreover not every problem that is decidable has the same complexity.

problems can be solved by different algorithms Complexity analysis is about trying to understand the time/space complexity of a problem and its boundaries.

Moreover by Complexity analysis we can try and break up different problems into different classes, for example class A could be "All problems that have an algorithm solving them in (some\_constant)*(n*log(n) time" could be an hypothetical class of problems.

Here is some nice short video trying to summarize some of the ideas of Complexity. https://www.youtube.com/watch?v=YX40hbAHx3s
> 1 votes

# Answer
A *real time application* is one in which some computation needs to be done very fast, always. For example, controlling an airplane, decoding an MPEG, and Skype are real time applications. Web browsing is not an example since it needn't be very fast, and it is also tolerable if it is occasionally a bit slow.

You are asking for complexity and decidability problems in real time applications. This question is a bit hard to interpret. You might as well ask for complexity and decidability problems in airborne computers. What you *could* be asking is what kinds of problems come up when designing real time applications. Sometimes we are faced with decision problems, sometimes with function problems (requiring us to compute some function whose output is not necessarily Boolean), sometimes with interactive tasks which are not considered in classical theoretical computer science.

You then ask whether all real time applications have complexity and decidability problems. This is again hard to interpret, and this time I won't offer any interpretations.

Finally, you ask whether finite state automata have real time applications. It so happens that finite state automata and, more generally, finite state transducers are very efficient to implement, even compared to other linear time parsing algorithms such as LR parsing. Therefore they may very well be used in high traffic TCP/IP stacks, as you mention in a comment on a deleted answer.

In the same comment you ask for the meaning of real time in these examples. The meaning is that the worst case running time of simulating a finite state automaton is very small. Contrast that with garbage collection, which has a small amortized running time, but a large worst case running time. Garbage collection epitomizes what you want to avoid in real time applications.
> 1 votes

---
Tags: complexity-theory, finite-automata, undecidability, real-time
---


# Question
Title: Does the aliasing problem show up in a virtually indexed physically tagged cache?
Basically, and as a simple method, we can access cache with **Physical Address** which is from the TLB.

But, as another method, we can access cache with **Virtual Address**. But, in this case, if the cache is not fully flushed between context switch(other process's datas can be exist in cache), there is an aliasing problem. Same memory can be directed from the different virtual address.

But in my text book, including these problem, many can be solved by **virtually indexed physically tagged**. I think this still can make an aliasing problem.

Am I wrong?

# Answer
> 7 votes
The Aliasing problem can be solved if we select the cache size small enough. If cache size is such that the bits for indexing the cache all come from the page offset bits , multiple virtual address will point to the same index position in the cache and aliasing will be solved.

For example consider 32-bit virtual address 0xFFFF FFFF , this system uses a page size of 64kB suppose which make the page offset bits 16 bits. Now if we select The index bits to be 10 (number of sets 1024) and block size as 64 Bytes. Then the index bits and the block offset bits both are accommodated in the page offset bits of the virtual address. Consider another address 0xEEEE FFFF this address looks like it will cause aliasing but despite of having different virtual address the lower order bits force it to map to the same location in the cache and there is no aliasing. Only drawback of this approach is cache size is limited by the page size.

# Answer
> 2 votes
There are two aspects related to VIPT caches and aliasing. And the issues can be a bit different between instruction set architectures.

**1)**

There are several ways to map the virtual addresses of each process to the external physical addresses.

Some use "process identifiers" or "address space identifiers" (iirc ARM, SPARC, MIPS) where each running process is given a different value used to select different page tables.

Some use "logical/physical" addresses where the addresses for each process (=logical) are translated o a larger address space (for example from 32 to 52 bits) (=virtual) shared between all processes, and TLBs transform these extended virtual addresses to physical addresses. PowerPCs are like that.

To avoid needing to flush all the TLBs and all the cache during each context switch, the cache tags (and TLBs) can store the corresponding address space identifiers or extended virtual addresses : Each adress of each process is different, and no aliasing is possible (well, sometimes aliasing is expected, for example where running privilegied kernel code mapped in the same virtual address range of all processes)

**2)**

A more subtle issue is when several processes share the same physical memory area. This range of physical memory may be mapped in different virtual addresses by each process. Modification by one process may not be visible by the other. Particularly with write-back caches where writes are not immediately forwarded to RAM. One solution, with the OS assistance, is to guarantee some alignment between processes depending on cache size, even if the virtual addresses are different between the different processes, they will be aliased in the same cache line, and will automatically eject one another.

Virtually Indexed caches are used principally on simple (old) CPUs, because of these aliasing issues. Nowadays, a very common technique is to limit each way of the L1 cache to the MMU page size (4kB or 8kB usually) so that the cache index is shared between physical and virtual addresses, cache fetch occurs at the same times as MMU address resolution.

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


title: Finding the sum of four squares

text:
# Question
Title: Finding the sum of four squares
There is Lagrange's four-square theorem, which statea that

> Given an integer $N$, we can write $N$ as a sum of four squares $A^2+B^2+C^2+D^2=N$.

How can I find a valid solution with time complexity of $O(1)$ or $O(\sqrt N)$? I only have to find one solution.

Here is my $O(1)$ algorithm:

```
while(count!=4){
     solution = sqrt(N)
     print solution
     N-= solution*solution
     count++
}

```

But it does not works for all $N$, for example it fails for $N=23$. Is there any other solution?

# Answer
Try this: Legendre's\_three-square\_theorem

Assume $4\not\mid N$. If not, divide $N$ by $4^k$ and multiply $2^k$ back in the end. Find an $A$ satisfying $N-A^2\not\equiv0,4,7 \mod 8$. It's always valid to choose $A=\lfloor\sqrt{N}\rfloor$ or $\lfloor\sqrt{N}\rfloor-1$. (Choose the even one if $N\equiv 1,5 \mod 8$ and the odd one otherwise.) Now $N-A^2$ is an integer in $O(\sqrt{N})$ and you can find $B,C,D$ in $O(\sqrt{N})$ easily.

Edit: Since $B,C,D\le cN^{\frac{1}{4}}$ for some small constant $c$, we can enumerate two of them (suppose $B$ and $C$) and check whether the corresponding $D$ is an integer. This works in $O(\sqrt{N})$. There might be some faster solutions.
> 4 votes

# Answer
I am going to provide you with 4 links and I hope it will help you.

this one is an online calculator based on an algorithm from math overflow.

http://www.mathcelebrity.com/foursquare.php?num=+178&pl=Show+Lagrange+Four-Square+Notation

the math overflow algorithm can be found here.

https://stackoverflow.com/questions/11732555/how-to-find-all-possible-values-of-four-variables-when-squared-sum-to-n

and then there is also this algorithm from cs stackexchange

How fast can we find all Four-Square combinations that sum to N?

and if you want to do a bit of work, then there is this algorithm that can find the sum of 2 squares for a given integer. So you would have to divide your number in two ( not necessarily equal part ) and then add up the results to get a 4 square representation.

https://math.stackexchange.com/questions/1972771/is-this-the-general-solution-of-finding-the-two-original-squares-that-add-up-to/1977767?noredirect=1#comment4062390\_1977767
> -2 votes

---
Tags: algorithms, time-complexity, number-theory
---


# Question
Title: How do you convert this iterative code to recursive?
How do you convert the following algorithm from the iterative paradigm to the recursive paradigm?

Input: array $A\[1\],\ldots,A\[n\]$

Output: last index $i$ such that $A\[i\] = i$, or $-1$ if none

Algorithm:

> $index \gets -1$
>
> For $i \gets 1,\ldots,n$:
>
> $\quad$ If $A\[i\] = i$: $index \gets i$
>
> Return $index$

# Answer
> 0 votes
Here is one way to convert your code into a recursive procedure:

> procedure MagicIndex($A\[1\],\ldots,A\[n\]$):
>
> $\quad$ If $n = 0$: Return $-1$
>
> $\quad$ If $A\[n\] = n$: Return $n$
>
> $\quad$ Return MagicIndex($A\[1\],\ldots,A\[n-1\]$)

This recursion splits the array $A\[1\],\ldots,A\[n\]$ into $A\[1\],\ldots,A\[n-1\]$ and $A\[n\]$, but any other way of splitting it into two contiguous halves will do.

Why does this work? Ignoring the trivial case $n=0$, the algorithm considers two cases:

1. If $A\[n\] = n$ then the answer is always $n$.
2. Otherwise, the last index such that $A\[i\] = i$ (if any) satisfies $i \leq n-1$, and so the answer for $A\[1\],\ldots,A\[n\]$ is the same as the answer for $A\[1\],\ldots,A\[n-1\]$.

---
Tags: algorithms, recursion
---