# Question
Title: Is it possible for a stack-based programming language to be concurrent?
I have been reading about stack-based programming languages, such as FORTH and Cat, and it seems that given their nature, they can only execute one action at a time regardless of their paradigm (FORTH is imperative whereas Cat is functional).

An imperative language would modify the stack, and a purely functional language, such as Joy, would return a new stack, but the point is that only one stack is used at a time.

**So, can stack-based programming languages be concurrent?** Could they achieve concurrency by using multiple stacks at the same time or something alike?

Is it possible to implement lazy evaluation in a stack-based programming language?

*Please correct me if I am misunderstanding anything about the languages and concepts mentioned above*

# Answer
> So, can stack-based programming languages be concurrent?

Sure.

> Could they achieve concurrency by using multiple stacks at the same time or something alike?

Already for normal languages multi-threading usually means having multiple "call" stacks. It would be completely natural to give each thread its own data stack. It would be straightforward to have an actor, say, whose body was implemented by code in a stack-based language. Explicit parallelism a la GHC's `par` annotations should be reasonably straightforward. The main issue with executing things in parallel is that you don't know what the stack effect of the code will be until you execute it. However, using a Joy-like syntax, one could imagine `[a b c] par` as executing `a b c` either against an empty stack or a copy of the stack and only keeping the top-most element of the stack on completion (or pushing some dummy value if the stack is empty). You could imagine variations. Implicit parallelism would be harder to do naively as compared to, say, a purely functional language, but certainly could be done as well. The compiled code of a user-defined combinator is often not too different from "normal" code.

> Is it possible to implement lazy evaluation in a stack-based programming language?

Unknown stack effects are again the tricky part. If you design the language such that all stack effects can be determined statically, then it doesn't seem too challenging. If you have laziness be explicit, then it also seems relatively straightforward and would look roughly like Joy's quotations and `i`. One language that calls itself a lazy concatenative language seems to do a mixture of both of the above approaches from what I can tell. I don't really see how an implicitly lazy concatenative language would work in the face of dynamic stack effects, at least not in any vaguely usable way, but that might just be a lack of imagination on my part.

Incidentally, it is not uncommon for stack-based languages to have multiple stacks, e.g. Forth has a data stack and a return stack upon which you can also place arbitrary data.
> 17 votes

# Answer
I know a bit about FORTH so I will confine myself to that. It is a low level language, giving you as programmer access to all the hardware resources. So you can do whatever you like.

# Concurrency

In order to have parallell programs (edit: used to say real concurrent programs) you need at least two execution units (CPU-s). It would be rather trivial to implement a word in FORTH saying, as example, "run this word on processor 2 using these two arguments". The word would allocate the two needed stacks on processor 2 and start running the word. You would need to restrict yourself somewhat in exactly what constructs you can use in that program.

If the number of concurrent programs is larger than the number of execution units you would go for "pseudo parallell" programs. Basically there are two ways to do that: coroutines or preemptive multitasking. In any case it is possible (not easy, but well described in literature) how to achieve this and FORTH allows you to access all the low level stuff you need.

# Lazy evaluation

Of course you can do this in FORTH as in just about any programming language. It will not be as elegant or "built-in" as in say Haskell. I will use a very naive example.

The idea is that you define a "function" (used loosely here) that returns a set of things. One example would be a function that returns all integers. You then do operations on this set and when you are done give the result. As example, you might want to sum all integers until the sum is larger then 1000. A non-lazy evaluation would firstly allocate all integers as a set, which is impossible as there are an infinite number of integers. It would then start to work on this set. A lazy implementation would have a way of "give me the next value in the set". Doing this really only needs one variable in the funktion "last value give".

Haskell does things this way. Of course it handles more complicated situations but the idea is the same. It sugarcoates the evaluation in a way that allows you as a programmer to concentrate on the problem, not on how to solve it.
> 8 votes

---
Tags: concurrency, stacks, evaluation-strategies
---


# Question
Title: What machine learning training algorithm to use for this kind of string dataset?
I am working on a project where I have to train the following data-set using machine learning algorithm. One of my friend suggested decision tree, but I have never seen a situation where independent variable has more than 100 values in decision tree. I need help for choosing algorithm. Dataset is custom made and small. I am confused, since there are 100+ songs.

Dataset looks like this. Song is to be predicted. Every activity etc. comes from a predefined set of possibilities.

PS: It's not class assignment question. I made this database. I am also noob in ML.

# Answer
> 2 votes
You want to perform supervised learning, i.e., you have set of training examples (in this case, a set of 4-vectors with a label that corresponds to one of the 100 songs). So in particular, you want to do classification: given a 4-vector, predict a song. It might feel silly to call the songs a "category", but when you look past the naming in this particular case it should make sense: given an "activity vector", what is the song out of the 100 possible songs that will be chosen?

A fair starting point is scikit-learn's flowchart for choosing an estimator. Assuming the vector entries come from a predefined set of possibilities, you can simply map the strings to integers. For example, replace "walking" by 0, driving by "1", or replace "nothing" by 0, reading by "1", and so on. So for concreteness, your training data might be a file, where each line is something like "{0,1,0,8},47" meaning that activity 0, mob act 1, session 0, and mood 8 corresponds to song 47.

Now, assuming you have less than 100k samples, a good starting point is a linear support vector machine as per the flowchart. Depending on your results, the flowchart guides you towards other choices.

---
Tags: algorithms, machine-learning, decision-tree
---


# Question
Title: What techniques could be used to support thread-local contexts and resources in a language?
I am interested in the subject of thread-local contexts, which is a feature that I use quite often in solutions, but seems to lack first-class support in any languages I have used.

Quite often in programming - especially if you are implementing a solution that repeatedly processes similar inputs - it is useful to have access to a thread-local context.

I am sure many are familiar with this problem: the typical case I am taking about is where you have a processing engine taking input messages/requests (e.g., an MDB or a Servlet in Java) that is instantiated individually for several threads, and this engine repeatedly processes the messages using some resources or context that it owns. These resources could be expensive to recreate (and therefore we would like to reuse them), or alternatively, they need to be retained across requests in the thread, but do not need global scope in the application.

In this case, code needs to be able to access that context in an efficient way, but due to the stack+heap-based approach of most languages this is difficult. The current solutions are to either use something like `ThreadLocal` in Java or to pass a pointer to the context down the stack, both which are not really language constructs, and both of which impose some overhead (and in the second case have practical issues).

It occurs to me that such a thread context is a bit like a second stack. A stack has thread scope and can be efficiently accessed by the thread.

Possibly solutions to implement this in-language might be to maintain the context at the base of the stack; however, this would have to be a fixed size. For a variable sized context, a reference could be stored at the base, but with some loss of efficiency for minimalist requirements. Other options might be possible if the hardware supported multiple stacks per thread.

As a trivial example of what I mean to illustrate the performance impact of existing solutions would be to imagine each "engine" receives a message and then increments a counter (counting the number of messages processed per for each thread). Using `ThreadLocal` would be many times less efficient that simply incrementing the contents of a known memory address. Even a global counter would require some synchronization and therefore would create a choke point.

A more practical example would be the maintenance of a resource pool such as an object pool where expensive-to-create objects or buffers can be re-used across invocations.

To be clear: this is not really a multi-threading issue, so solutions such as semaphores, etc. are not the solution - on the contrary, they are part of the problem.

A thread-local resource does *not* need to be shared between threads. It is local, so any solution adding the overhead of synchronization is adding an unnecessary performance penalty.

It would be interesting to know how this might be done (or if it has been done already), with particular consideration to the hardware support available to make it efficient.

# Answer
One example of a language system built from bottom up to support this kind of situation is Erlang. It is well worth looking into.

It is built around the concept that you create a lot of tasks. The tasks never share variables and only communicates via messages. The task has a "thread-local" context which is maintained using a very specific construct of tail-recursion. It is not uncommon to have thousands or even millions of task in a Erlang system.

Erlang comes with a set of constructs and tools known as OTP which helps in handling a number of common situation in soft real time systems. I especially like how it allows you to update the programs in a running system on the fly.
> 2 votes

---
Tags: programming-languages, concurrency, threads, stacks, language-design
---


title: Float type variable uncertainty

text:
# Question
Title: Float type variable uncertainty
I developed an image processing software and I need to do a numerical analysis of it, considering the error propagation associated to its operations and the uncertainty of float type variables caused by the inherent rounding up that happens with this type of variables.

Considering the IEEE 754 standard the `machine epsilon` for the float type variables is `1.19e-07`. From what I understood, this value is the distance to the nearest representable float.

I did some testing to find if this is true by adding a float value to this epsilon as such: `x + epsilon == x`. This notion does not hold for every value of the float range, which is understandable since great values of floats have more uncertainty associated with them caused by the rounding and the limited number of bits used to represent them.

My question is what is the uncertainty associated to a float value in such a way that `(x + y) || (x - y) == x` being the float value `x` and the float uncertainty `y`.

It might be my lack of knowledge about the english language but I can not seem to understand the literature about this topic.

If someone could be as detailed as possible can you explain me the error in a simple operation such as the following?

```
float result = valA * 0.587f + valB * 0.331f;

```

If I knew the uncertainty of a float type variable this error could be simply calculated with this formulas, right?

# Answer
The number 1.19e-07 is the difference from 1.0 to the next larger representable floating point number. Single precision floating numbers have the form $x = ± 2^k m$, where k is a small integer, and 1 ≤ m \< 2 is a multiple of $2^{-23}$.

If you calculate a result x, and $2^k ≤ x \< 2^{k+1}$, then x will be rounded to the nearest multiple of $2^{k-23}$, with a rounding error up to $2^{k-24}$.

Don't think of floating-point arithmetic to have "uncertainty". It gives a perfectly fine well-defined result, just not the one you might have wanted.

As far as your table is concerned, it doesn't make any sense to me, but I am *very* confident that there is no square root involved when you try to find upper bounds for floating point errors.

To analyse floating point errors: Multiplication and division may *add* the relative errors of their inputs, and then another rounding error is added (unless you can prove the result is exact, for example multiplying by 2.0). Addition and subtraction may *add* the absolute errors of their inputs, and then another rounding error is added (unless you can prove the result is exact, for example subtracting x-y where x/2 ≤ y ≤ 2x.

For tightest bounds, you analyse the error depending on the input values, and you can also improve the error by arranging operations in the right order.
> 1 votes

# Answer
The important thing to consider is than when using floating point numbers, everything is approximate. When you multiply x by 0.587, you don't actually multiply by 0.587, but by some other number within epsilon of 0.587. Usually the epsilon errors accumulate very slowly, but in specific cases even simple operations can yield answers with no significant bits in the result. Most code simply ignores the possibility, and the IEEE standard is designed to make that as OK as possible.

If you really need a bound on the error, you need a course in numerical analysis before you even start to look at your particular algorithms.
> 0 votes

---
Tags: floating-point, numerical-analysis
---


# Question
Title: Why use binary search trees when hash tables exist?
Hash tables perform lookup, insertion, and deletion in O(1) time (expected and amortized) while the different variants of binary search tree (BST) - treap, splay, AVL, red-black - offer at best O(log n).

So, in a course on data structures, is the study of BST's of any value except as a historical note?

# Answer
The most obvious answer is that trees can be traversed in their natural order very efficiently. If you need to visit every element of a dictionary in alphabetical order, a tree can support this directly, where a hash table cannot.

Another answer is that trees can be made immutable - where insertion and deletion only involve recreating a small number of elements back to the root, whereas hash tables can only be completely duplicated.

A related answer for mutable data is that trees can be modified concurrently, only requiring locking single nodes, whereas hash tables have to be locked as a whole if concurrent processes are to get consistent results.
> 16 votes

# Answer
Binary search trees (BSTs) of various sorts and their variations are widely used data structures today, so they are hardly a "historical note". For example, both the .NET Framework and the Java Standard Library provide a tree-based implementation of a dictionary. A red-black tree no less in the latter case.

One of the reasons for this is that tree-based implementations more easily provide desirable functionality. It's not a surprise that the .NET `Dictionary` type is a hash table, but the `SortedDictionary` type is a tree. Providing values in order or doing range queries is something that is awkward with hash tables. Making hash tables persistent (as in allowing old "versions" to be used, not as in on-disk) is also fairly awkward, but it is much more straightforward for trees. Most functional mapping data structures are based on trees, though usually quite a bit fancier than red-black trees and possibly also incorporating hashing as in hash array mapped tries (HAMTs).

Even if you don't need those extra features, sometimes "expected" isn't enough. Those "expectations" are based on assumptions that an adversary can exploit. It's not necessary to use trees to avoid the mentioned issue, but sometimes more predictable behavior than "expected" and "amortized" is necessary.

Finally, many data structures incorporate BSTs or at least ideas from BSTs. For example, most databases use variations on B-trees which are basically "non-binary" search trees. As a pedagogical aspect, proving things about red-black trees, say, is likely an easier exercise than proving things about PATRICIA trees or HAMTs but still exercises many of the concepts that are being taught.
> 10 votes

# Answer
You are right now thinking of a data structure from which just three operations are expected,

1. Insertion
2. Lookup
3. Deletion

But if you extend these range of operations, to let's say finding number of elements greater than a certain value, one can see how BST's can be useful. A BST can still manage this operation in $\log n$ time but a hash table can't.

Hence in a course of data structure, a BST is very important because it can be extended to support other operations while retaining good complexity while a hash table can't.
> 6 votes

# Answer
The two disadvantages of hash tables: 1. They don't support ordering. Search trees naturally support processing all items in sorted order, or processing all items in some range. 2. The speed will depend on the speed of the hashing function, which may be rather slow.

One brutal approach that I have seen recently is a datastructure that just uses an unsorted array up to a certain size, and then switches to hashing. Very nice when you have applications that often have dictionaries with one or two keys only.
> 3 votes

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


# Question
Title: Finding an index such that $A[i] = i$ in a strictly increasing integer array
I'm looking for a hint for solving the following problem :

> Given an array $A\[1, \dots, k\]$ of integers where $A\[1\] \< A\[2\] \< \dots \< A\[k\]$ write pseudocode for an algorithm that determines whether $A\[j\]=j$ for some $j\in \\{1,\dots,k\\}$. Worst-case running time should be $\Theta(\log k)$.

I shall find an easy to calculate criteria which finds the index involving the special structure of $A$.

Let's say $A = \[-3 , 2 , 4, 5, 7, 8, 9, 10\]$. My first approach would be to subdivide $A$ into two parts around the median (here $A\[4\]$). Since $A\[4\] = 5 \> 4$ and the sequence keeps increasing, I don't have to look at $A\[4,\dots,8\]$.

My criterion would then be: For a sequence of numbers $A\[a, \dots, b\]$, if $A\[a\] \> a$, then the solution can't be in that sequence since $A\[a\]\< \dots \< A\[b\]$.

Am I going in the right direction?

# Answer
Let $B\[i\] = A\[i\] - i$. Since $A\[i\] \< A\[i+1\]$, we have $A\[i\]+1 \leq A\[i+1\]$ and so (subtracting $i+1$ from both sides) $B\[i\] \leq B\[i+1\]$. In other words, $B\[1\] \leq \cdots \leq B\[k\]$ is nondecreasing. Your goal is to find an index $i$ such that $B\[i\] = 0$, if any such exists. You can use binary search to do this in time $O(\log k)$. In fact, you can even find *all* such indices (or rather, a succinct representation of them) in that running time.
> 2 votes

# Answer
My solution would be :

```
int Search( A , start = 1,end = A.length)
    m = (start + end + 1) / 2 ( rounded down )  // calculates median

    if ( end - start >= 0 )

       if ( A[m] == m )                       // checks if solution found
          return m

       if ( A[m] > m )
          return Search( A, start , m-1)   // solution must be in left subarray

       else
          return Search(A, m+1, end)      // solution must be in right subarray
   else
     return -1;                           // no solution exists

```
> 0 votes

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


# Question
Title: Finding missing number in an unsorted array
> You are given an unsorted array of all the integers in the range $0$ to $n = 2^k -1$ except for one integer, called the missing number. Find a divide and conquer algorithm to find the missing number in time $O(n)$. If you wish, you may use the fact that an algorithm $median(A)$ exists that can find the median of an array $A$ of $n$ numbers in time $O(n)$. The median of $n=2m$ numbers is the average of the $m$th smallest and $m$th largest number.

I am not sure where to start any hint would be much appreciated. The solution without Divide and Conquer would be to find the sum of the array and subtract it from the computed sum $n(n+1)/2$.

# Answer
You don't even need to use divide and conquer here. You can just run down the list and keep a checklist for all of the $2^k$ numbers, then find the missing entry. The list contains $2^k$ entries, so this takes $O(2^k)$ steps But since $n=2^k-1$ this is also $O(n)$.
You can do the same thing in divide and conquer fashion if you so choose, but that amounts to just checking all the numbers in a different order. You're not saving any time doing that.
> 2 votes

# Answer
An efficient way to do this kind of thing without using unusually precise knowledge of the contents of the array is to sort the array and then make a single pass to find the gap.
> -1 votes

---
Tags: algorithms, time-complexity, divide-and-conquer
---


# Question
Title: Why does this recurrence give O(n) time?
Given this following recurrence: $$T(n) = T(n/2) + O(n)$$Find the final time complexity.

My first thought is $O(n\log n)$, since there is at most $\log n$ times the $O(n)$ will appear.

However, if we adopt the following analysis and let $n=2^m$, then we have:

$$T(2^m) = T(2^{m-1}) + k(2^m) = T(2^{m-2}) + k(2^m + 2^{m-1})...$$

Which we can then condense to have the cost become:

$$2^m + 2^{m-1} .... + 1 = 2^{m+1} - 1$$

And so since the cost is $O(2^m)$, we have our $O(n)$ time as required.

Is the analysis valid? Because I have so very often seen proofs using recurrences of the form $T(n) = T(n/2) + ...$, and they all similarly concluded that there will be $\log n$ times of the relationship.

Which is correct?

# Answer
> 3 votes
Your second analysis is correct, and $T(n) \in \Theta(n)$. You can also use the Master Theorem to verify this.

The reason that the first "naive" analysis fails is that you don't have $O(n)$ at each step, you have $O(\frac{n}{2^{i}})$ where $i$ is how far down the recursion you've gone.

Ignoring the constant multipliers for the moment, this gives $$ \sum\_{i=0}^{\log n} \frac{n}{2^{i}} = \frac{\sum\_{i=0}^{\log n}n}{\sum\_{i=0}^{\log n}2^{i}} = \frac{n\log n}{2^{log n + 1}} = \frac{n\log n}{2 \log n} = \frac{n}{2} $$

Your second analysis basically does the same thing, just using variable substitution instead.

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


# Question
Title: Complexity Sorting a finite set of numbers from 0,..,N
I have a set of elements $x\_1,...,x\_N$, they take values $x\_i \in \\{0,...,N\\} $ for all $i \in \\{1,...,N\\}$; I need to sort them. I think I can do that with complexity $\mathcal{O}(N)$, where I can create a matrix of $N\times N+1$ where the colomns represent the sorted values of the range, i.e., $\\{0,1,2,...,N\\}$, and the rows are the elements. So my questions are:

Is this correct?

Is there a better way to do that?

What if I changed the values of some of these numbers afterwards (after sorting), but all still comply with the initial rule, can I do better than linear sorting to maintain the order?

# Answer
Since you have a bound on your set of elements you can radix-sort them.

Formally let consider the following procedure:

```
    // Read the whole table and store the number of occurrences
    T <- Table[N] // Suppose initialized at 0
    for i = 0 to N do
        T[x[i]] <- T[x[i]]+1
    done
    // Unpack the elements
    c = 0
    for i = 0 to N do
        for j = 0 to T[i]-1 do
            x[c] <- i
            c <- c+1
        done
    done

```

The soundness of the algorithm is evident. It's time complexity is in $\mathcal{O}(N)$ and its space complexity in $\mathcal{O}(N)$, estimated in arithmetic complexity (I mean by that the reading and writing complexities for your integers is independent of their bitsize).

The (bit) time complexity is in worst case a $\mathcal{O}(N\log N)$ since you might have to read $N+1$ bit strings of length $\Theta(log(N))$.

Notice that in any case, the algorithm is always **linear** in the size of its input.
> 1 votes

---
Tags: algorithm-analysis, time-complexity
---


# Question
Title: Real life applications of finite automata
I have some confusion about the differences between finite & infinite. can someone tell me how the Toll machine or Park meter, soda vending machine can be used with infinite language? if not, please give me an example of other application.

# Answer
> 4 votes
As Yuval Filmus said, the KMP substring matching is widely used in practice because of its modularity and efficiency.

A maybe more "practical" exemple is lexical analysis. (https://en.wikipedia.org/wiki/Lexical\_analysis)

Depending on your application (let say or the compilation of a programming language) the parsing phase can be done with some various generalisation of automatons (state transition machines or pile-automatons for instance). The language they accept is infinite (think of the set of all programs that are syntactically correct in your favorite language), yet the recognition of a correct program should be done by an automata (or a generalisation of it) which is finitely presented.

---
Tags: turing-machines, automata, finite-automata, computation-models
---


# Question
Title: Is deciding if there is a set that is intersected with some given sets and that has at most one common element with other given sets NP-complete?
Given 2 collections of ﬁnite sets $A\_1,A\_2,\ldots,A\_m$ and $B\_1,B\_2,\ldots,B\_n$, is there a set $T$ such that: $\left|T \cap A\_j\right|\ge 1$, for $j = 1,2,\ldots,m$ and $\left|T \cap B\_i\right|\le 1$, for $i= 1,2,\ldots,n$?

I tried doing this problem by considering it as a decision problem (pi). Please suggest me if you have an approach.

# Answer
> 2 votes
You can reduce 3SAT to this problem by converting each variable $v\_i$ to two elements $e\_{i1}$ and $e\_{i2}$ (one for its positive literal and one for its negative literal) and a set $B\_i$ containing $e\_{i1}$ and $e\_{i2}$, and converting each clause $c\_j=l\_{j1}\vee l\_{j2}\vee l\_{j3}$ to a set $A\_j$ containing elements representing $l\_{j1},l\_{j2},l\_{j2}$.

Now it's not hard to prove this problem is NP-complete using the reduction above.

---
Tags: np-complete, np, decision-problem
---


# Question
Title: Is there a name for this tree traversal?
This came when I was looking at block scoping in compiler design.

```
{   A   { B }   { C {D} {E} }   }

```

For the above pseudo code, the order in which the scope varies as we scan left to right is A B A C D C E C A, where A to E represent scopes.

A parse tree can be constructed for the above pseudo code:

```
  A
 / \
B   C
   / \
  D   E

```

Is their a term for such a traversal order, which for the above tree is A B A C D C E C A?

# Answer
For a binary tree that is triple order; each node is visited three times in pre- in- and post-order. Knuth cites it from a paper by Lindstrom and Dwyer; it can be done without a stack by updating the tree in place.
> 2 votes

---
Tags: trees, compilers, parsers
---


# Question
Title: Transforming undirected maximum spanning tree into directed augmented network
I am having trouble transforming a maximum weighted spanning tree into a directed tree such that each node is allowed at most one parent node. Taken from page 141 Friedman et. al (1997), the outline of the algorithm is as follows:

1) Compute $I\_{\hat{P}\_{D}}(X\_{i};X\_{j})$ between each pair of variables $i \neq j$ where $$I\_{\hat{P}\_{D}}(X\_{i};X\_{j}) = \sum\_{x,y} P(x,y) log\left(\frac{P(x,y)}{P(x)P(y)}\right)$$ 2) Build a complete undirected graph in which the vertices are the variables in $X$. Annotate the weight of an edge connecting $X\_{i}$ to $X\_{j}$ by $$I\_{\hat{P}\_{D}}(X\_{i};X\_{j})$$ 3) Build a maximum weighted spanning tree

4) Transform the resulting undirected tree to a directed one by choosing a root variable and setting the direction of all edges to be outward from it.

I have done steps 1-3, my trouble is on step 4. As of right now I have a set of names of continuous variables $X = \\{x\_{1}, x\_{2}, \ldots, x\_{n} \\}$ and a $(from , to)$ matrix of the form $$ \begin{bmatrix} x\_{1}&x\_{10}\\x\_{3}&x\_{7}\\ \vdots& \vdots \end{bmatrix} $$ For example in the undirected maximum weighted tree, there's an edge going from $x\_{1}$ to $x\_{10}$ and so forth (note that this could have easily been read as an edge from $x\_{10}$ to $x\_{1}$ because as of right now the graph is undirected). I understand exactly what's going on I'm just unsure how to actually program it. If somebody could give me a pesduocode-type overview of how I should go about implementing step 4 it would be much appreciated. If someone could provide a link to a detailed implementation of this algorithm that would be fine as well. This is my first post on stackexchange, please forgive me if I have not provided enough information or posted this question in the incorrect location.

# Answer
> 0 votes
Given an undirected tree, pick any node (it doesn't matter which one). Call that the root. Now do depth-first search (or breadth-first search, or any other kind of search) starting from the root, traversing only the edges of the tree. That will visit all the vertices and edges. When you visit an edge for the first time, it will always be in an "outward" direction, so now you know how to orient it (how to set its direction).

Work through a small example if this is still unclear.

---
Tags: spanning-trees, graphical-models, bayesian-network
---


# Question
Title: Kolmogorov complexity of prefixes of computable sequences
> Let the characteristic sequence of a set $A ⊆ \mathbb{Z^+}$ be the following infinite binary sequence:
>
> $$χ\_A = b\_1b\_2b\_3\ldots,$$
>
> whose $n$th bit is 1 if $n ∈ A$ And 0 otherwise. Write $χ\_{A,n}$ for the first $n$ bits of $χ\_A$.
>
> Prove for every decidable set $A \subseteq \mathbb{Z^+}$ there is a constant $c ∈ \mathbb{N}^+$ such that for all $n ∈ \mathbb{Z}^+$ the Kolmogorov complexity of $\chi\_{A,n}$ satisfies
>
> $$ C(χ\_{A,n})≤\log n+c. $$

Since $A$ is decidable there is a lexicograhic enumerator. Given that, how would I construct a Turing machine $\pi\_A$ satisfying $U(\pi\_A)= χ\_{A,n}$, where $U$ is the universal Turing machine, whose complexity is at most $\log n+c$?

# Answer
> 1 votes
Let $D$ be a decider for $A$, then in order to determine $\mathcal{X}\_{A,n}$ it is enough to specify $n$ and an encoding of $D$. Given $D,n$, you can loop over all integers $i\in \[n\]$ and check whether or not $i\in A$ by simulating $D(i)$. Thus, the overall description of $\mathcal{X}\_{A,n}$ consists of $n$, the encoding of $D$ and the encapsulating machine $M$ (described above) which uses $D,n$ to output $\mathcal{X}\_{A,n}$. $n$ contributes at most $\log n$ bits to the description, and $D,M$ have some encoding of length $c$ independent of $n$, bounding the overall description length by $\log n + c$.

---
Tags: kolmogorov-complexity
---


title: Two questions about complexity class

text:
# Question
Title: Two questions about complexity class
1. Does $2^{n-1}$ and $2^{n}$ share the same complexity complexity class as **exponential** named as $O(2^n)$? So the former belongs to $O(2^n)$ even though it's one order lower?
2. What is the name of the complexity complexity class of $O(n2^{n})$?

# Answer
> 3 votes
Since $2^{n-1} = \Theta(2^n)$, in (CS-style) asymptotic analysis the two functions are equivalent. They have the same "order of growth" from the point of view of asymptotic analysis.

When giving big O upper bounds, we often want to suppress lower-order information. Therefore we sometimes write $\tilde{O}(n)$ instead of $O(n\log n)$ or of $O(n\log^2 n)$, and $\tilde{O}(2^n)$ instead of $O(n2^n)$. Generally speaking, $\tilde{O}$ hides (poly)logarithmic factors, that is, $\tilde{O}(f(n))$ is the same as $O(f(n) \log^{O(1)} f(n))$.

A bound of the form $\tilde{O}(2^n)$ is an exponential bound, since $\tilde{O}(2^n) = O(3^n)$ (indeed, $O((2+\epsilon)^n)$ for any $\epsilon \> 0$). In fact, sometimes when saying *exponential* we also allow functions of the form $2^{n^2}$ in which there is a *polynomial* in the exponent; and sometimes we mean it in the strict sense of $O(c^n)$ for some constant $c\>1$.

Finally, let me mention that complexity classes are about the complexity of *problems*, not the order of growth of functions. For example, the complexity class $\mathsf{P}$ consists of decision problems solvable in polynomial time. It is *not* the same as the class of all polynomials.

# Answer
> 3 votes
1. Yes. Since $ 2^{n-1} $ is just $ \frac{2^n}2 $, which is a constant times $ 2^n$, they belong to the same complexity class $O(2^n)$.
2. It belongs in its own class. For example, it can't be of class $O(2^n)$ since, by the definition, there is no constant $c$ such that $c\*2^n$ will always be greater than $n\*2^n$ for any $n\>n\_0$, since for any $n\>c$, that condition will always be false.

---
Tags: asymptotics, landau-notation
---


# Question
Title: Sum of distances between points on one-dimensional axis
We have given integer array of $n$ points, let it be $A$, showing where it is on the x-axis. For this problem we are working only with the x-axis and the y-axis is not important at all. Now for given two indexes $l$ and $r$, such that $0\leq l\leq r \leq n-1$, we want to find the sum of distances from each point whose index is in the range $l, r$ to the point with index $r$.

For example $A = \\{1, 2, 4, 6, 8\\}$ and $l = 0$, $r = n-1$ The output should be $(8-8) + (8-6) + (8-4) + (8-2) + (8-1) = 0 + 2 + 4 + 6 + 7 =19$

I know that it can be implemented in $O(1)$ after $O(N)$ preprocessing but I don't get the intuition behind that, and the formula is very unclear to me.

# Answer
> 1 votes
Let us start with the formula for the sum of distances: $$ \begin{align\*} D(\ell,r) := \sum\_{i=\ell}^r \[A\_r - A\_i\] &= (r-\ell+1) A\_r - \sum\_{i=\ell}^r A\_i \\ &= (r-\ell+1) A\_r - \sum\_{i=1}^r A\_i + \sum\_{i=1}^{\ell-1} A\_i. \end{align\*} $$ In time $O(n)$ we can compute an array $B\_i = \sum\_{j=1}^i A\_j$: indeed, $B\_0 = 0$, and $B\_j = B\_{j-1} + A\_j$. The formula above then translates to $$ D(\ell,r) = (r-\ell+1)A\_r - B\_r + B\_{\ell-1}, $$ which can be computed in $O(1)$.

---
Tags: mathematical-programming
---


# Question
Title: Travelling salesman problem with small edge weights
Are there any advantages in finding the shortest tour for the problem if edge weights are much smaller than the number of vertices?

Let's say the maximum edge weight is $n$, and the number of vertices is $n!$, and the adjacency matrix is dense and all distances $d\_{ij}$ satisfy $0 \le d\_{ij} \le n$. Are there any known methods which work well in similar cases?

# Answer
Travelling salesman remains **NP**-complete even if you restrict to two different edge weights $a\<b$. Reduce from Hamiltonian cycle by giving weight $a$ to every edge and weight $b$ to every non-edge. Then the resulting complete graph has a TSP tour of length $na$ (where $n$ is the number of vertices) if, and only if, the original graph has a Hamiltonian cycle.
> 3 votes

---
Tags: algorithms, optimization, traveling-salesman
---


# Question
Title: How can I find a number whose sum of digits' cube is equal to n
I'm given a number $n$ and I have to find the smallest number possible whose sum of digits' cube is equal to $n$. For example $n=9$ then output should be $12$, because $1^3 + 2^3=9$.

# Answer
> 3 votes
Let us consider the more general problem in which we fix integers $0 \< a\_1 \< \cdots \< a\_m$, and then given a positive integer $n$, we want to determine the *smallest* non-negative integer combination $\sum\_{i=1}^m d\_i a\_i$ which is equal to $n$, if any exists, or determine the none exists. Here one combination $(d\_1,\ldots,d\_m)$ is smaller than another $(e\_1,\ldots,e\_m)$ if either $d\_1+\cdots+d\_m \< e\_1+\cdots+e\_m$, or $d\_1+\cdots+d\_m = e\_1+\cdots+e\_m$ and for some $i$ we have $d\_1=e\_1,\ldots,d\_{i-1}=e\_{i-1}$ and $d\_i \> e\_i$.

The main observation is that any optimal solution satisfies $d\_i \< a\_m$ for all $i \< m$. Indeed, if $d\_i \geq a\_m$ then we can decrease $d\_i$ by $a\_m$ and increase $d\_m$ by $a\_i$ to obtain a better solution. (In fact, this shows that $d\_i \< \mathrm{lcm}(a\_i,a\_m)/a\_i$.) This suggests the following algorithm:

> Go over all possible values of $d\_1,\ldots,d\_{m-1}$ such that $0 \leq d\_1,\ldots,d\_{m-1} \< a\_m$. For each such setting, check whether it can be completed to a solution, that is, whether $a\_m$ divides $n-\sum\_{i=1}^{m-1} d\_i a\_i$. Choose the smallest solution, if any exists.

This algorithm runs in time $O(\log n)$, where the hidden constant depends in some horrible way on $a\_1,\ldots,a\_m$. This is optimal (up to the value of the hidden constant) since clearly we need to read the entire input.

---

The algorithm above doesn't really help you solve your case in practice, since the hidden constant is too large. Presumably you were supposed to use dynamic programming, an algorithm which runs in time $O(n)$ and finds the minimal length of a solution (perhaps it can also be tweaked to find a solution of minimal value).

# Answer
> 2 votes
The smallest number producing n always consists of the digits 1 to 9, in non-decreasing order. Fill an array with the smallest number producing n, for n = 0, 1, 2, 3, .... I bet you will be able to show that for some N, the smallest number to produce n ≥ N consists of producing n - 729, followed by a digit 9.

Actually, the last number where this is not the case is n = 9\*512 + 1 = 4609 which is the sum of digit cubes of 1888888888. For every n ≥ 4610, the smallest number with sum of digit cubes = n is the solution for n - 729, followed by the digit 9.

So finding the solution as a decimal number requires O (n) because the size of the solution is O (n) (about n/729 digits), but describing it in the form a * 10^k - b can be done in O (log n).

---
Tags: algorithms, number-theory
---


# Question
Title: Is $T(n) = Ω (n^2)$ the same as $n^2=O(T(n))$?
**Question:** In the problem below, does proving $T(n) = O(n^2)$ and $n^2 = O(T(n))$ lead to the same result as proving $T(n)=O(n^2)$ and $T(n)=Ω (n^2)$? Which would be the better approach to take? I feel like I am not getting the big picture. Right now I am just trying around until I find something that seems plausible.

Here is what I have tried so far:

Problem: Prove that $T(n) = \theta(n^2)$ where $T(n) = \frac{n(n+1)}{2}$

**My Approach:** I know that T(n) is $\theta(n^2)$ if $T(n) = O(n^2)$ and $n^2 = O(T(n))$ both apply, if I can prove both, the statement is therefore true.

1. In order to proof $T(n) = O(n^2)$, I check if $\lim\limits\_{n\to \infty}\frac{T(n)}{n^2}$ exists, which it does: $\lim\limits\_{n\to\infty}\frac{n(n+1)}{\frac{2}{n^2}} =\lim\limits\_{n\to\infty} \frac{\frac{1}{2}n^2+\frac{1}{2}n}{n^2}=\lim\limits\_{n\to\infty}\frac{1}{2}+\frac{1}{2n}=\frac{1}{2}$
2. To prove that $n^2=\theta(T(n))$ I argue that $n^2 \le 2 * \frac{n(n+1)}{2}=n^2+n$ and that therefore, for all $c =2\>0$ and for all $n \ge n\_0 = 1:n^2 \le c \*T(n)$ applies $n^2 = O(T(n))$

# Answer
> 1 votes
It follows from the definitions that $f(n) = O(g(n))$ iff $g(n) = \Omega(f(n))$, in the same way that $a \leq b$ is equivalent to $b \geq a$. Therefore in order to prove $f(n) = \Theta(g(n))$, it suffices (and necessary) to prove $f(n) = O(g(n))$ and $g(n) = O(f(n))$.

The "quick" way to prove that $\binom{n}{2} = \Theta(n^2)$ is $$ \binom{n}{2} = \frac{1}{2} n^2 + O(n) = \frac{1}{2} n^2 + o(n^2) = \Theta(n^2), $$ where the last equality is a general result: $cf(n) + o(f(n)) = \Theta(f(n))$.

In practice, we take the following fact as well-known: if $P$ is a polynomial whose leading coefficient is positive then $$ P(n) = \Theta(n^{\deg P}). $$ Using this, you can immediately deduce $\binom{n}{2} = \Theta(n^2)$.

---
Tags: asymptotics, landau-notation
---


# Question
Title: NFA accepting $L=\{wbbav \;|\; w \in \{a,b\}^*, v \in \{a,b\}^+, v\; has\; suffix\; a\}$
I have to construct NFA that accepts language $L=\\{wbbav \\;|\\; w \in \\{a,b\\}^\*, v \in \\{a,b\\}^+, v\\; has\\; suffix\\; a\\}$.

My solution is this automata:

Can you tell me, if this is correct or not? If yes, it is possible to construct this NFA with less states?

# Answer
> 2 votes
I will address your second question, namely, whether there is an NFA with fewer states. The appropriate technique here is *fooling set*:

> Let $L$ be a language, and let $x\_1,\ldots,x\_n,y\_1,\ldots,y\_n$ be words such that $x\_iy\_i \in L$ but for every $i \neq j$, either $x\_iy\_j \notin L$ or $x\_jy\_i \notin L$. Then every NFA for $L$ contains at least $n$ states.

(The proof is a simple exercise.)

In our case, we take $$ \begin{array}{c|cc} i & x\_i & y\_i \\\hline 1 & bbaa & \epsilon \\ 2 & bba & a \\ 3 & bb & aa \\ 4 & b & aaa \\ 5 & \epsilon & bbaa \end{array} $$ For all $i$ we have $x\_iy\_i = bbaa \in L$. Conversely, if $i \< j$ then $|x\_jy\_i| \< 4$ and so $x\_jy\_i \notin L$.

In fact, we have proven the following more general result:

> If the minimal length of a word in $L$ is $\ell$, then every NFA for $L$ contains at least $\ell+1$ states.

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


title: MIPS control signal table(R-type add)

text:
# Question
Title: MIPS control signal table(R-type add)
I've been going through the control signal table and I noticed something confusing on when I should set the value as 'don't care' or 0 for control signal.

For example when doing the R type add instruction, we don't go through the data memory. When we are done with addition inside the ALU, the result will justbypass the data memory and will be written on the destination register.

So I thought, being 'don't care' for the MemWrite and MemRead would also be ok rather than being 0. But on the signal table, it says 0.

I wonder where the differences are made when deciding rather to put 'don't care' and 0.

Thanks!

# Answer
For certain instructions in certain pipeline stages, we don't care about the results or operation of one or more of the hardware's many functional units.

Let's say the processor implementation has several functional units, e.g. in the ALU, for addition/subtraction, one for and/or, one for multiplication, one for division, one for shifting, and maybe even (separate from the ALU) one for computing addressing, e.g. combined shift & add for the various load & store instructions. there may also be a completely separate adder next to the PC for doing pc-relative branches.

All that hardware is always there, but not all is always being used.

So, for example, when doing an unconditional branch instruction, the regular ALU is still there doing something, but we don't care about it. All we have to do is ignore the unit's output, e.g. don't write it to a register.

So, at the times when we don't care about the regular ALU's output, we also don't care about the signals going into the ALU — the source operands, and the code that says whether to add vs. and vs. other. We need to ignore not just the ALU's output, then but also any signals like overflow. However, that is pretty easy to do, so sometimes this is done (ignoring output while giving "don't care" input), instead of instructing the ALU to do something specific during don't care, like adding 0 + 0.

However, when it comes to memory *we never want to initiate a memory reference with a potentially garbage address*, even a read, let alone a write, which could be destructive of program state. Keep in mind that the memory reference goes thru the cache and then potentially off-chip, to the memory devices, and/or to I/O devices. We don't even want to issue a read to a known or hard-coded address (like 0). *If the instruction isn't a memory reference, we should not touch memory at all!!* And we do that by forcing both the read and write signals to 0.
> 1 votes

---
Tags: computer-architecture, mips
---


# Question
Title: How to avoid permutations in the n-Queens problem?
**EDIT:** if you are not familiar with the problem and the solution, it's nicely explained here.

I have solved the n-Queens problem as an exercise using backtracking (recursion), but the problem I have right now is I get multiple permutations of the same solution:

```
n = 4
(0,1) (1,3) (2,0) (3,2)
(0,1) (1,3) (3,2) (2,0)
(0,1) (2,0) (1,3) (3,2)
(0,1) (2,0) (3,2) (1,3)
(0,1) (3,2) (1,3) (2,0)
...

```

For `n=4` i get a total of 48 solutions. Of course there are rotations and mirroring which are fine and should be included, but as you can see in the example above permutations of the exact same solution appear.

My program works as follows:

```
solve(queens){
    if (n_queens_are_on_the_board){
        remember_solution();
        return;
    }
    for(x: 0 to n){
        for(y: 0 to n){
            if(current_position_not_attacked){
                add_queen_to_current_potision();
                solve(board);
                remove_prevously_added_queen();
            }
        }
    }
}

```

Obviously I can just find the permutations and remove them from the final result, but is there a faster way of getting rid of them or ideally completely avoiding them?

Any help is appreciated.

# Answer
Note that your solution is not optimized - if you really want a speed boost, you should handle rotations / mirroring instead of looping through every possible combination. With a large board, this will be much more significant than looping through the solutions one extra time.

There are a few ways you could handle the permutations. I would handle them as a secondary check under `if (n_queens_are_on_the_board)`, resulting in the following algorithm:

```
solve(queens){
    if (n_queens_are_on_the_board){
        if (solution_is_sorted) {
            remember_solution();
        }
        return;
    }
    for(x: 0 to n){
        for(y: 0 to n){
            if(current_position_not_attacked){
                add_queen_to_current_potision();
                solve(board);
                remove_prevously_added_queen();
            }
        }
    }
}

```

All that you have to do now is define a function to tell if the solution is sorted - again, there are a few ways you could do this. The simplest is probably to define the `hash` of a point to be `point[0] * length(points) + point[1]` and discard the solution if the hash of position `n + 1` is less than the hash of position `n`. With this algorithm, you will end up with the solution `(0,1) (1,3) (2,0) (3,2)` from the sample provided.
> 1 votes

---
Tags: algorithms, program-optimization
---


title: Caroll's paradox => Rice theorem?

text:
# Question
Title: Caroll's paradox => Rice theorem?
To me (but I might be wrong) Rice's theorem asserts that it's not possible to formalise the demonstration of a non-trivial property of a recursively enumerable language *within the same given language*. The modus ponens being the basis for demonstrating, Rice therefore says in substance that you will necessarily need a metalanguage to define it.

What I call Carroll's paradox is referred in Wikipedia under What the Tortoise Said to Achilles.

Wikipedia explains the following:

> The Wittgensteinian philosopher Peter Winch discussed the paradox in The Idea of a Social Science and its Relation to Philosophy (1958), where he argued that the paradox showed that "the actual process of drawing an inference, which is after all at the heart of logic, is something which cannot be represented as a logical formula ... Learning to infer is not just a matter of being taught about explicit logical relations between propositions; it is learning to do something" (p. 57). Winch goes on to suggest that the moral of the dialogue is a particular case of a general lesson, **to the effect that the proper application of rules governing a form of human activity cannot itself be summed up with a set of further rules, and so that "a form of human activity can never be summed up in a set of explicit precepts"** (p. 53).

In other words, Carroll's paradox shows that it's not formally possible to prove a property of a language purely with propositions of this language. You will need to *admit a rule* (or a *principle*) that "the modus ponens means X" with X using everyday words. I.e. you will need a meta language.

I will concede that it is a philosophical way to ask the question. But Carroll's paradox can be described in a formal (mathematical) way (done here).

Hence am I mistaken in principle to say that Caroll's paradox implies Rice's theorem?

# Answer
Well, any true statement implies every other true statement, so in that vacuous sense, I suppose one implies the other.

But no, I wouldn't say that Carroll's paradox implies Rice's theorem in any interesting or meaningful way. Carroll's Paradox is an explanation of why we need modus ponens as an inference rule in propositional logic and can't replace it with a finite list of axioms. It's nothing fancier than that. As such, it refers to what is true in a logical theory. It refers to what inference rules or axioms we need.

Rice's theorem is different. It talks about what is decidable, not what is true. It talks about what can be computed on a Turing machine, not about the inference rules or axioms we need.

Rice's theorem doesn't say "it's not possible to formalise the demonstration of a non-trivial property of a recursively enumerable language *within the same given language*". It has nothing to do with "within the same given language" (it's not even clear what that would mean; a language is a subset of $\\{0,1\\}^\*$ and doesn't demonstrate anything), but rather with that can be computed with a Turing machine. Rice's theorem talks about what a Turing machine can decide.

Rice's theorem doesn't say "you will necessarily need a metalanguage to define modus ponens". (I don't even know what a metalanguage would mean in this context.) It has nothing to do with what you can define. Rather, it has to do with what a Turing machine can decide.

In general, I warn you against trying to reason about mathematical statements using English language and analogies. That is notoriously error-prone. Rice's theorem is a mathematical statement with a precise mathematical meaning. At a suitable level of imprecision and vagueness, I suspect everything can seem similar and connected -- but when you look at the specifics, the situation often becomes richer and more interesting than that.
> 2 votes

---
Tags: rice-theorem, incompleteness
---


# Question
Title: How to do product construction with 2 DFA which has dead state
I have been trying to do a product construction(intersection) with 2 DFA which has dead states, but I'm stuck at the transition table with a confusion that,what should I do with dead state. Should I also combine the dead state with other states?

# Answer
> 2 votes
The product construction works for *any* two DFAs. There is nothing special you need to do. The resulting automaton would have many dead states and so won't be minimal, but that doesn't affect its correctness.

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


# Question
Title: A cache memory has a line size of eight 64-bit words and a capacity of 4K words
A cache memory has a line size of eight 64-bit words and a capacity of 4K words. The main memory size that is cacheable is 1024 Mbits. Assuming that the addressing is done at the byte level, show the format of main memory addresses using 8-way set-associative mapping.

So here's what I have understood from this question so far: Line size = 8 words = 2^3, which means that w = 3; Cache size = 4K = (2^3 + 2^6)/(2^3) = 2^6 lines; 8-way set associative means that each cache contains (2^6)/(2^3) = 2^3 Main memory size = 1024 Mbits = 128 M

I am stuck as to how to proceed next. Any help would be greatly appreciated.

# Answer
First, I'm going to do everything in bytes.

A 64-bit word means 8 bytes.

Line size: 8 words in a line, means 8 x 8 bytes = 64 bytes in a line = 26 bytes.

Cache size: 4k words, meaning 4096 x 8 bytes = 32k total bytes.

Cache indexes: 32k total bytes / 8 way set associative = 215 / 23 = 212 index positions in the cache line-set array.

Main memory: 1024 MBits = 1024 * 220 = 230 and, 230 / 8 bits-per-byte = 227 bytes (or 128 Mbytes).

So, that means there are 27 addressing bits in total for the cacheable memory. Those 27 bits break down into 3 parts:

```
+--------------------+
| tag | index | rest |
+--------------------+

```

The "index", which is 12-bits in width, is used to lookup into the cache array to identify one cache line set.

The tag bits are used to isolate one of the lines in the set of 8 (or determine a miss).

The "rest" bits determine which bytes in the 64-byte line are the particular bytes of interest for a given memory reference instruction. More precisely, the rest bits indicate the first byte of interest, and the memory reference instruction encodes the number of bytes of interest (e.g. 1, 2, 4, 8).

Since the line size is 64-bytes, then the "rest" is 6 bits; these 6 bits are used after the cache lookup identifies the line (on hit).

That means that the tag, which makes up the remainder, must be 27-12-6 = 9 bits wide. A tag of this size is stored in the each cache line in the set for comparison with the tag in the address bits.

So, the 27 bits of address break down into 9 tag bits, 12 index bits, and 6 "rest" bits. The cache line lookup operation consumes the 9 tag bits and 12 index bits, and, after the line is identified, the rest bits (and instruction-specified length) are used to extract the bytes of interest.
> 4 votes

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


# Question
Title: Turing machine + time dilation = solve the halting problem?
There are relativistic spacetimes (e.g. M-H spacetimes; see Hogarth 1994) where a worldline of infinite duration can be contained in the past of a finite observer. This means that a normal observer can have access to an infinite number of a computation steps.

Assuming it's possible for a computer to functional perfectly for an infinite length of time (and I know that's a big ask): one could construct a computer HM which travels along this infinite worldline, computing the halting problem for a given M. If M halts, HM sends a signal to the finite observer. If after an infinite number of steps the observer doesn't get a signal, the observer knows that M loops, solving the halting problem.

So far, this sounds okay to me. My question is: if what I've said so far is correct, **how does this alter Turing's proof that the halting problem is undecidable? Why does his proof fail in these spacetimes**?

# Answer
Note that Turing's proof is one of mathematics, not of physics. Within the model of a Turing machine Turing defined, undecidability of the halting problem has been proven and is a mathematical fact. Hence, Turing's proof will not 'fail' in the spacetimes, it will simply not prove anything about the relation of the halting problem and time dilation.

However, what you'll likely want to know is whether a 'time dilation Turing machine' can solve the halting problem.

If you want to study this the influence of 'time dilation' on a Turing machine, you'll have to specify a formal model by which we can formally understand what it means for a Turing machine to make use of time dilation. Unfortunately, this format is ill-suited for providing such a formal model (unless someone else has written a paper about it) as creating the model is far too broad.

However, it isn't unlikely that some formalisation indeed is able to solve the halting problem. This paper by Scott Aaronson, Mohammad Bavarian and Giulio Gueltrini looks at computational models under the assumption that so-called Closed time-like loops exist and conclude that the halting problem is indeed computable within that model.
> 28 votes

# Answer
The Turing machine is a formal mathematical model of computation, it does not answer to any physical limitations and does not care about relativistic effects. This means that Turing's proof does not fail, since the standard definition of Turing machine does not even contain a notion of "spacetime".

What you can try and do, is to define a different model of computation inspired by relativity. Again, this will only be a formal object, and the question of whether it can or can't solve the halting problem belongs to the realm of mathematics and depends on your specific definition. However, the true question now is whether this new model indeed correctly captures relativistic effects, i.e. does it really reflect our physics and can be implemented in our world?

You can see such a discussion regarding quantum computation. We have a formal definition of "quantum Turing machines", and their exact computational power remains an open problem in mathematics (not even close to the halting problem though). Still, you can argue that this definition does not really reflect our understanding of quantum physics, and a better one is needed. There are arguments that suggests that such machines cannot even be built, so their exact power has no effect on the (strong) Church-Turing thesis.

Back to your question. There is a formal notion of an infinite time Turing machine, but in order for it to have any effect on the Church-Turing thesis you need it to exist in practice. You might be interested in Scott's paper, which has a section about computations utilizing relativistic effects, though it seems that naive arguments are hopeless (in the sense that they are impractical, as time cost is replaced by energy cost).
> 10 votes

# Answer
Turing’s proof shows that no Turing machine can solve the Halting Problem no matter how much time you give it. If your spaceship used time dilation to give a computer a billion years to work, it still might not be able to tell you anything more definite than, “Not yet.”

Apparently, (Thanks, @DiscreteLizard!) if you have time travel that cannot cause paradoxes, you could set up a time loop that would cause a paradox if the computer cannot prove whether the Turing machine halts. Either it receives the answer from the future and transmits it back to itself, or it runs forever (and, cleverly, returns a quantum superposition that resolves to a stable time loop). But, before you try this, be very very sure that it’s safe to cause a time-travel paradox.
> 8 votes

# Answer
An objection is that you have defined a process that can produce infinite entropy in a compact region and that appears to do so in a finite segment of the observer's past. This means a few things

* The computational entropy in the compact region exceeds the Bekenstein bound on entropy (which bound is proportional to the surface area of the region), so it collapses into a black hole (instantly) and no signal can ever reach you from its interior. (The Kerr metric describes an M-H spacetime. The infinite process is only observed to complete as the observer passes into the inner event horizon. Disregarding the current uncertainty about the physics of such passage, no remote observer ever has access to the result of the computation -- only the observer who has vanished into the black hole has the result. This is not a description of a useful computational process. To paraphrase: "We have an oracle that produces the correct answer to any question you ask in constant time in such a way that the answer exists only at the instant it is destroyed by flushing it down a black hole.")
* A Turing machine destroys information every time it overwrites a symbol on a tape, so by Landauer's principle, a finite computation on an infinite world line compressed into a finite segment in the past light cone of the observe must be observed to require infinite power and emit infinite heat during the infinitesimal time it is observed to operate. That is, since a halt is achieved in finite time, it is achieved instantly from the point of view of the external observer, so all the power is consumed instantly and all the heat is evolved instantly. Alternatively, if the computation does not halt, the compact region continuously consumes infinite power and emits infinite heat. Net result: a black hole, again.
* Alternatively, the Landauer principle does not apply to reversible computing and there *are* (universal) reversible Turing machines. However, such a Turing machine requires the ability to represent the entire space of potential computational states, which is exponential in the size of the amount of tape used, so quickly runs into the Bekenstein bound. We end up being able to avoid the heat problem only by restricting to bounded-length tapes. Equivalently, we have an upper bound on usable tape length controlled by the surface area of the region that has an infinite worldline. If you don't account for this and your computation uses too much tape, you get a black hole, again.

It is an interesting open question whether and how these constraints apply to quantum computers. It may well be that the complexity of a computation performable by a quantum computer is limited by the surface area of the computer. So we may have to double the surface area of an extremal quantum computer to get one more usable qubit of computation. This quickly leads to impractically large computers.
> 5 votes

# Answer
Quote from Bangs, Crunches, Whimpers, and Shrieks:

> Thomson lamps, super $\pi$ machines, and Platonist computers are playthings of philosophers; they are able to survive only in the hothouse atmosphere of philosophy journals. In the end, M—H spacetimes and the supertasks they underwrite may similarly prove to be recreational fictions for general relativists with nothing better to do. But in order to arrive at this latter position requires that one first resolve some of the deepest foundation problems in classical general relativity, including the nature of singularities and the fate of cosmic censorship. It is this connection to real problems in physics that makes them worthy of discussion.

> There are also connections to the philosophy of mathematics and to the theory of computability. Because of finitist scruples, some philosophers have doubted that it is meaningful to assign a truth value to a formula of arithmetic of the form $(\exists x\_1)(\exists x\_2)\dots(\exists x\_n)F(x\_l,x\_2,\dots,x\_n)$. It seems to me unattractive to make the truth of mathematical statements depend on the contingencies of spacetime structure. The sorts of arrangements considered above can be used to decide the truth value of assertions of arithmetic with a prenex normal form that is purely existential or purely universal. (Fermat's last theorem, for example, has a purely universal form.) For such an assertion $\gamma\_1$ is set to work to check through the (countably infinite) list of $n$-tuples of numbers in search of a falsifier or a verifier according as the assertion to be tested is universal or existential, and $\gamma\_1$ reaps from these labors a knowledge of the truth value of the assertion. But as soon as mixed quantifiers are involved, the method fails. However, Hogarth (1994) has shown how more complicated arrangements in general relativistic spacetimes can in principle be used to check the truth value of any arithmetic assertion of arbitrary quantificational complexity. Within such a spacetime it is hard to see how to maintain the attitude that we do not have a clear notion of truth in arithmetic.
> 1 votes

---
Tags: turing-machines, halting-problem, church-turing-thesis, hypercomputation
---


title: Closest divisors in array

text:
# Question
Title: Closest divisors in array
Given an array $A\[1\],\ldots,A\[n\]$ of natural numbers, we have to construct a new array $B\[1\],\ldots,B\[n\]$, where $B\[i\]$ is equal to $A\[j\]$ for the minimal $j \> i$ such that $A\[j\]$ divides $A\[i\]$, or $-1$ if no such element exists. For example: $$ \begin{array}{c|ccccccc} A & 10 & 4 & 5 & 2 & 1 & 8 & 4 \\\hline B & 5 & 2 & 1 & 1 & -1 & 4 & -1 \end{array} $$

I can solve this in $O(n^2)$ using brute force. Is there a better solution?

# Answer
> 1 votes
No, probably not, if you care about theoretical worst-case running time. The problem is as hard as the subset containment problem: given sets $S\_1,\dots,S\_n$, check whether there exists sets $S\_i,S\_j$ such that $S\_i \subset S\_j$. It's known that there is no algorithm with $O(n^{2-\epsilon})$ running time, assuming the SETH conjecture is true. Thus, any faster algorithm would imply a disproof of SETH, which is a famous open problem -- so you shouldn't expect any easy algorithm that does significantly better than $O(n^2)$ in worst-case running time. (I don't count a $\log n$ factor speedup as significant.) See https://cstheory.stackexchange.com/q/9896/5038.

If you only care about the "average case" it might be possible to do better. The answer might also depend on the model of computation and the size of the integers, so it's possible there might be some choice of those that lets you evade this hardness result.

---

For instance, if your numbers are "random" in a particular specific way, you can use a divide-and-conquer algorithm. First recursively solve the problem for $A\[1..n/2\]$, and recursively solve the problem for $A\[n/2+1..n\]$. Then for each $i \le n/2$ such that $B\[i\]=-1$, we'll find the smallest $j \> n/2$ such that $A\[j\]$ divides $A\[i\]$ and overwrite $B\[i\]$ with $j$. Suppose we can do that last step in $U(n)$ time. Then the total running time will satisfy the recurrence $T(n) = 2 T(n/2) + U(n)$, i.e., $T(n) = O(U(n) \log n)$.

OK. So how will we do that last step? We'll solve that problem in turn using a separate divide-and-conquer algorithm. Pick a prime number $p$ that hasn't been picked yet, and construct the sets $S^0 = \\{i : p \not| A\[i\], i \le n/2\\}$, $S^1 = \\{i : p | A\[i\], i \le n/2\\}$, $T^0 = \\{i : p \not| A\[i\], i \> n/2\\}$, $T^1 = \\{i : p | A\[i\], i \> n/2\\}$. Now for each $i \in S^0$, find the smallest $j \in T^0$ such that $A\[j\]$ divides $A\[i\]$; and for each $i \in S^1$, find the smallest $j \in T^0$ such that $A\[j\]$ divides $A\[i\]$ (or, equivalently, such that $A\[j\]$ divides $A\[i\]/p$), and find the smallest $j \in T^1$ such that $A\[j\]$ divides $A\[i\]$ (or, equivalently, such that $A\[j\]/p$ divides $A\[i\]/p$). Those are three subproblems each of size $n/2$ (heuristically, assuming the numbers are random and half are divisible by $p$ and half aren't), and then you can combine them to get a solution to the original problem in $O(n)$ time, so the total running time to do this last step is $U(n) = 3 U(n/2) + O(n)$, which solves to $U(n) = O(n^{\lg 3}) = O(n^{1.585})$.

So, heuristically the total running time of this approach is $O(n^{1.585} \log n)$ *under a particular assumption on the distribution of the numbers*.

# Answer
> 0 votes
Tricky. You will often go much faster than $n^2$ if you check whether $x\_{i-1}$, $x\_{i+1}$, $x\_{i-2}$, $x\_{i+2}$, is a divisor of $x\_i$, so the effort is proportional to n times average distance to the nearest divisor.

To go better, you might go from numbers to multiples, and try using some data structure that keeps track of multiples of 2, 3, 5, 7 etc.

# Answer
> 0 votes
I've given this problem some thought and I say that you might get an average running time of less than $O(n^2)$, but a theoretical time complexity of less than $O(n^2)$ is not possible. The problem explicitly calls for a dividend-divisor check between past and future elements. There is no way to effect this regardless of how diligently you keep track of divisors.

Consider an array like $45, 40, 35, 30, 25, 5$. This would yield an array of $5, 5, 5, 5, 5, -1$. There is no way for you to fill in those $5$s without looking ahead. Even if you built some kind of tree or hash the effectiveness of such a structure is only realized when dividend-divisor relationships are made.

---
Tags: algorithms, arrays, number-theory
---


# Question
Title: Can we define a program by means of a walk of a graph induced by the category of types?
After reading about Category Theory at https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ I was wondering whether we can represent any program by means of a walk of a graph induced by the category of types.

EDIT: rephrasing the question a little bit.

So, given the category of types where the objects belong to a set of types $V$ and the morphisms are a set of functions $F$ with $f : a \rightarrow b$, if we define a **walk** on this category as a sequence $v\_0, e\_{0,1}, v\_1, ..., v\_n$, with $v\_i \in V$ and $e\_{i,j} \in E \subset F$, with $E$ as the default set of functions of any given programming language (*add*, *mul*, *\<*, etc.), the pure part of a program could be defined as a walk on this set $E$.

So, for example, a program to return the greatest of two integers could be represented as:

```
v0 -> e1 -> v1 -> e2 -> v2
(Int, Int) -> e1 -> (Bool, Int, Int) -> e2 -> Int

```

with:

```
e1 : (Int, Int) -> (Bool, Int, Int)
e1 x y = (x>y, x, y)

e2 : (Bool, Int, Int) -> (Int, Int)
e2 b x y = if b then x else y

```

given that *e1* and *e2* are part of the subset of morphisms.

So, is the definition of a **walk** and this set $E$ **sufficient** to represent the pure part of any program?

# Answer
> 6 votes
Consider the simply-typed $\lambda$ calculus: this is one of the simplest functional languages you can define.

It is very common to interpret it in a Cartesian closed category (CCC). Indeed, CCCs are the "ideal" categorical setting where to interpret simple types.

CCCs, being categories, admit morphisms composition and identity. Taking your definition of "walk" loosely, as a rough idea rather than a rigorous concept, I think you covered this aspect of CCCs.

However, they also allow products, which are not considered by "walking". Given $f:A\to B$ and $g:A\to C$ there is a unique morphism $\langle f,g \rangle: A\to B\times C$ satisfying a certain universal property. This is a way to craft new morphisms from old ones that "walking" does not consider.

There's even more. The main, fundamental property of CCCs is the "currying" adjunction. That is, there's a natural bijection between the set of morphisms $A\times B\to C$ and $A\to C^B$ (where $C^B$ corresponds to the functional type $B\to C$). So, given a morphism in one of this set, we can take the corresponding one in the other set. Doing this is important to interpret $\lambda x. \ldots$, and without that, we do not have a "lambda" calculus.

So, even in the simplest setting, interpreting a functional program is much more than "composing morphisms", or the proposed definition of "walking".

# Answer
> 5 votes
Your question sounds redundant to me. By definition of **category** whenever two morphisms with common object $f\colon A \rightarrow B$ and $g\colon B \rightarrow C$ exist, then their composition $g\circ f \colon A \rightarrow C$ **must** exists as another arrow in that same category. (otherwise, that situation is just not a category.)

So the redundant part in your question is: there is **no need** to convert a category of types to its underlying graph **then** find all the possible walks **then** decide what morphism (function) that walk correspond to. The morphism obtained this way was already in the category to begin with.

---

On the other hand, if I were to interpret your question less literally. Maybe you were wondering if composing morphism is the **only** way to build new programs from existing ones. This couldn't be more wrong. You'll see many more ways to construct new morphisms from existing ones. Some examples that you'll see soon after learning category theory are functors, limits, and adjunctions. Once you know how they translate in category of types, you'll see that they provide many essential construction in programming that isn't covered by just composition of function.

---
Tags: functional-programming, category-theory, haskell
---


# Question
Title: Can the higher-order oracle Turing machines simulate the lower-order machines so that the current oracle does not contradict the simulated oracle?
Here is a quote from the Source 1:

> For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the oracle.

But here is a quote from the Source 2:

> If you have an oracle for the halting problem, then you can compute the Busy Beaver function. Given an input $n$, just search through all Turing machines with $n$ states and check whether they halt or not. For the TMs that halt, run them through to completion, and count the number of steps or symbols printed. Keep track of the maximum score. After you have run through all possible Turing machines, you will have the Busy Beaver number.

I can imagine how this would work for the first-order oracle machine simulating a no-oracle machine, but I cannot understand how an oracle machine of the arbitrary order would simulate the lower-order oracle machine, assuming that the simulated machine can also simulate another machine with the arbitrary level of "nested" oracles!

For example, consider the computation process of a 4th-order oracle Turing machine equipped with a halting oracle for the 3rd-order oracle Turing machine. At some moment the program starts simulating some program for, say, 2nd-order machine. But how does the oracle interprets the content on the oracle tape when the simulated program goes into ASK state? If the oracle interprets this content as the question for the 4-th order machine, then the simulation is absolutely meaningless because the answer would not correspond to the answer provided by the simulated (2nd-order) oracle.

But if the mathematically correct simulation cannot be performed, then how would an $x$-th-order Turing machine with a halting oracle for the $(x-1)$-th-order machine compute the Busy Beaver number of any $(x-y)$-th Turing machine (where $1 \geq y \geq x$ and $y$ is a natural number)?

If such simulations can be performed without logical paradoxes, then is it possible to provide a pseudocode (similarly to this answer) that shows how some 5-th order oracle Turing machine obtains a value of $BB\_4(x)$, and then the value of $BB\_2(x)$?

# Answer
The halting problem $\mathrm{Halt}\_O$ for Turing machine with oracle access to $O$ is the language consisting of all oracle Turing machines $M$ that halt on the empty input when the oracle calls are interpreted as membership in $O$. A Turing machine with access to $\mathrm{Halt}\_O$ can compute the busy beaver number for oracle Turing machines with oracle access to $O$.

Now to your other question. Let $O\_0 := \emptyset$, and $O\_{i+1} = \mathrm{Halt}\_{O\_i}$ (so $O\_i = 0^{(i)}$ using the usual terminology). Let us show that given oracle access to $O\_{i+1}$ you can simulate oracle access to $O\_i$. Consider the following program:

> If $x \in O\_i$ then halt, else run an infinite loop.

Using oracle access to $O\_{i+1} = \mathrm{Halt}\_{O\_i}$ you can determine whether this program halts, which happens if and only if $x \in O\_i$.

Applying this construction inductively, you can simulate access to $O\_i$ given access to $O\_j$ for all $j \geq i$. This shows that having an oracle for $O\_j$ is indeed stronger than having an oracle for $O\_i$ (when $i \< j$).
> 2 votes

---
Tags: turing-machines, computability, logic, undecidability, oracle-machines
---


# Question
Title: Why line graph is a proper subclass of claw-free graph?
A **claw** is the graph isomorphic to $K\_{1,3}$, that is, a star graph with three edges, three leaves, and one central vertex. (see below)

A graph is **claw-free** if it does not contain a claw as an induced subgraph.

The **line graph** of G is the intersection graph of the edges of G, that represents the adjacencies between edges of G.

A graph $F$ is a line graph if there exists a graph $H$ such that $L(H) = F$.

**My question** is why are line graphs a subclass of claw-free graphs?? **Thanks a lot!**

# Answer
Your question is answered on Wikipedia:

> "Line graphs may be characterized in terms of nine forbidden subgraphs;<sup>\[2\]</sup> the claw is the simplest of these nine graphs."

The reference is to the following paper:

> \[2\] Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J., Beiträge zur Graphentheorie, Leipzig: Teubner, pp. 17–33.

Wikipedia contains a pictorial description of these nine graphs. One of them is $K\_5^-$, obtained from $K\_5$ by removing a single edge.

If you take any of the other forbidden subgraphs then you get a claw-free graph which isn't a line graph.
> 3 votes

---
Tags: graphs
---


# Question
Title: Justification for neglecting constant factors in Big O
Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing is varying 3 times more rapidly than other! Why do we neglect this fact?

# Answer
> 27 votes
To rationalize how asymptotic notations ignore constant factors, I usually think of it like this: asymptotic complexity isn't for comparing performance of different algorithms, it's for understanding how performance of individual algorithms scales with respect to the input size.

For instance, we say that a function that takes $3n$ steps is $O(n)$, because, roughly speaking, for large enough inputs, doubling the input size will no more than double the number of steps taken. Similarly, $O(n^2)$ means that doubling the input size will at most quadruple the number of steps, and $O(\log n)$ means that doubling the input size will increase the number of steps by at most some constant.

It's a tool for saying which algorithms scale better, not which ones are absolutely faster.

# Answer
> 11 votes
First, as other answers have already explained, $O(3n) = O(n)$, or to put it in words, a function is $O(3n)$ if and only if it is $O(n)$. $f = O(3n)$ means that there exists a point $N$ and a factor $C\_3$ such that for all $n \ge N$, $f(n) \le C\_3 \cdot 3n$. Now pick $C\_1 = 3 C\_3$: for all $n \ge N$, $f(n) \le C\_1 \cdot n$, so $f = O(n)$. The proof of the converse is similar.

Now on to the reason why this is the right tool. Observe that when we measure the complexity of an algorithm, we don't give a unit. We don't count seconds, or machine instructions: we count some unspecified elementary steps that each take a bounded time. We do that because executing the same algorithm on a different machine would change the time needed per instruction — multiply the clock frequency by $3$ and the execution time goes from $f(n)$ to $f(n)/3$. If we implement the same algorithm in a different language, or on a different system, the time taken by each elementary step might be different, but again that's too much detail: we hardly ever care about such differences.

When you do care about precise timings, asymptotic complexity is not relevant: asymptotic complexity tells you what happens for very large input sizes, which may or may not be the actual input sizes you're dealing with.

# Answer
> 4 votes
## Big O notation is a unit free mean of measuring performance variation, thus impervious to relative costs of computational primitives.

**In a nutshell:** *Big O notation is a unit free, relative type of measurement (as opposed to absolute measurement). It can only measure performance variation, not absolute performance, for which constants do matter a lot. The advantage is that this makes it largely implementation independent, by allowing simpler analysis that can ignore relative costs of elementary operations, as long as these costs have positive fixed upper and lower bounds. **But the consequence is that constant factors are meaningless**. Still, even for its intended purpose, **asymptotic complexity analysis can be questioned on other grounds**, and has to be considered with care. For example, raw input size may not be the right parameter to consider.*

A first remark is that your question is not quite accurately stated. When you neglect the constant $3$ in $3n$, there is indeed a "three fold change", but both vary at the same rate, and you cannot assert that "\[one\] thing is varying 3 times more rapidly than other".

A good reason to ignore the constant in Landau notation is that we have no unit we can rely on. When someone states that A lives twice as far from you as B does, this does have meaning independently of any unit. We can agree on it even though you measure distances in inches while I do it in light-years. But absolute distance measurement requires specifying units, and its numerical formulation depend on the chosen unit.

The actual time taken by an algorithm depends on the execution time of elementary operations, which is very machine dependent. You could count the number of elementary operations, but there is no reason to believe they all take the same time, and it is always possible to compound several operations into a single one, or conversely decompose an operation into smaller ones, so that the number of operations is not really meaningful, unless you agree on a reference virtual machine. Being reference independent is an advantage.

Another view of the advantage of the approach is that all you care in the analysis is counting the number of elementary operations, as long as their cost has an upper bound and a positive lower bound. You do not have to worry about individual cost.

However, the price to pay for that advantage is that computation cost assessment is given with unspecified unit, and computation time, for example, could be nanoseconds or millenia - we do not even try to know. In other words **constant factors are meaningless, since changing units is inseparable from changing constant factor**, and no reference units are used.

As noted by Patrick87, this is enough to understand how an algorithm scales with respect to input size, but it will not give an absolute measure of performance, short of relying on a reference unit. Unsing a common reference abstract machine can be done when one actually wishes to compare performance of distinct algorithms, but it is harder to make sure that the comparison is not biased by realization details. In asymptotic complexity, this risk is avoided because you compare the algorithm with itself.

Anyway, only a naive programmer would rely exclusively on asymptotic complexity to choose an algorithm. There are many other criteria, including the untold constant and the actual cost of elementary operations. Furthermore, worst case complexity can be a poor indicator, because the source of the worst case complexity can occurs rarely, and on fragments of the input small enough that it has a limited inpact. For example general parsers for Tree Adjoining Grammars have a theoretical complexity $O(n^6)$, and are quite usable in practice. The worst case I know of is the Damas-Hindley-Milner polymorphic type inference algorithm used for ML, which has exponential worst case complexity. But that does not seem to bother ML users, or to prevent the writing of very large programs in ML. There is more than the constant that matters. Actually, asymptotic analysis relates a measure of the cost of a computation to some measure of the complexity of the input. But raw size may not be the right measure.

Complexity is like decidability, it may be theoretically bad, but that may be irrelevant for most of the data space... sometimes. Asymptotic complexity analysis is a good and well designed tool, with its advantages and its limitations, like all tools. With or without expliciting the constant, which may be meaningless, using judgement is necessary.

# Answer
> 3 votes
Recall the definition of Big-O:

$f(n)\in O(g(n))$ iff there exists $c\>0$ such that $f(n)\le cg(n)$ for all $n$.

Under this definition, we have that $dn\in O(n)$ for every constant $d$. The purpose of the $O$ notation is exactly to simplify expressions in this manner. Indeed, $3n$ grows 3 times as fast as $n$, but they are both linear. Whether this is justified or not - that depends on the context. But if you agree to use the $O$ notation, then by definition this holds.

# Answer
> 2 votes
The other answers provide excellent explanations of why, according to the definition of Big-O, $O(n)=O(3n)$.

As for why we actually do this in CS, it's so that we have an compact description of the efficiency of an algorithm. For example, there might be an algorithm that has an if statement, where one branch executes $n$ instructions, and the other executes $3n$ instructions. This means that the exact number changes for each input, even for inputs of the same length. We could find a number for each input, but using big-O notation gives us a measure of time complexity that holds for ALL inputs.

This is much more useful at guessing how fast an algorithm will be. Otherwise, we'd have to look at a massive piecewise function, which would be very difficult to understand.

The other main reason is so that these measurements are hardware independent. Different compilers and architectures will change the same code into very different sets of instructions. However, if we know that the number of instructions is linear, exponential, etc., then we have an idea of the algorithms speed that holds, regardless of the actual computer that we compile or run it on.

# Answer
> 1 votes
$f(n)=O(g(n))$ means $\limsup\limits\_{n\to\infty} \frac{f(n)}{g(n)}\<+\infty$.

If this is true for $g(n)=n$, this is true for $g(n)=3n$ as well, and vice versa.

Similarly, $O(n^2)=O(.00005321n^2+1000000000n+10^{46803})$. Here the equality means that $f$ belongs to the LHS iff it belongs to the RHS. The $=$ sign here is a serious abuse of notation that I personally hate, because it is confusing.

# Answer
> -1 votes
Let me explain you simply. Let us take **n = 100000.** Now, what is 3n? It is 300000 (*Yeah, it is 3 folds of n*) But what is **n^2** ? **10000000000**. ( *it is 1 lakh folds of n*)..Compare n^2 with n. 3 is negligible when we compare with 1 lakh. so, we can remove it.

Think if n is some billions or trillions. In this case, again we are going to compare 3 with some billions or trillions. Now, you know why **we can neglect 3.**

---
Tags: complexity-theory, asymptotics, landau-notation
---


# Question
Title: Compute single-source shortest paths in O(n+m) time?
I found the following problem in my textbook and I'm having trouble with coming up with a solution. I'm thinking maybe there's a way to improve Dijkstra's algorithm by using a data structure other than a priority queue, since that's what causes the log(n) time complexity, but I'm a bit lost. Here's the question:

> Suppose you are given a connected weighted undirected graph, G, with n vertices and m edges, such that the weight of each edge in G is an integer in the interval \[1, c\], for a fixed constant c \> 0. Show how to solve the single-source shortest-paths problem, for any given vertex v, in G, in time O(n + m).
>
> *Hint: Think about how to exploit the fact that the distance from v to any other vertex in G can be at most O(cn) = O(n).*
>
> The "single-source shortest-paths" problem, is a problem in which we are given one vertex along with several nodes in a graph, and we are required to find the shortest path to any other node, given the edge length between each node.

I really appreciate any help in advance!

# Answer
> 6 votes
There are many ways to solve this problem in linear time. I'll write the one I found easiest to understand.

The main idea is to transform the weighted graph into an unweighted one. If the number of nodes and edges of the transformed graph remains linear to $n$ and $m$, then we can run BFS to solve it in $O(n+m)$.

The transformation is as follows: for each edge $(u,v)$ of weight $w$, create $w-1$ nodes to connect $u,v$. For example an edge $(a,b)$ of length $3$, we create two dummy nodes and transform it into

$a-d\_1-d\_2-b$

It is easy to check that this transformation preserves the shortest path between any pairs of nodes. The number of nodes is now $O(n+cm)=O(n+m)$ and the number of edges is $O(m+cm)=O(m)$. Since BFS is linear to the number of nodes and edges, we have a runtime of $O(n+m+m)=O(n+m)$.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: MIPS CPU (Single Cycle MIPS Processor)-R Type instruction ALUOp code confusion
I have question about the ALUOp control signal.

When doing R type instructions, 31-26th bits are all 000000. What decides the instruction is actually the func field of 5-0th bits.

In that case, I wonder why the ALUOp signals for the R type(add,sub,and,or,slt) below the table should all differ. I don't know why ALUcontrol needs to receive data from both instruction and Control when ALUOp for R type looks useless.

Can't ALUcontrol tells ALU what operations to do by just receiving 5-0th bits? If so, all the ALUOp signal can be all same for the R type.

Thanks in advance!

# Answer
First, there is a source of confusion between the table you're showing and the diagram. The table and diagram both use the term "ALUOp" but for the diagram this is the term for the output of the "Control" going into the "ALU control", whereas for the table this is the term for the output of the "ALU control" going into the ALU!

> Can't ALUcontrol tell ALU what operations to do by just receiving 5-0th bits? If so, all the ALUOp signal can be all same for the R type.

Not directly, it doesn't appear so. I don't see a simple bit pattern in the bit 5-0 that would result in the proper "ALUOp" shown in the table, so a lookup is necessary, which is what "ALU control" is doing when the ALUOp coming from Control is for 000000 (R-type).

> I don't know why ALUcontrol needs to receive data from both instruction and Control when ALUOp for R type looks useless.

This is because "ALU control" is also used by I-type instructions — lw & sw, addi/u, which use the add function of the ALU in computing an effective address, as well as slti, andi, ori, xori, which also require the ALU. Note that the ALUOp for lw & sw is 010, the same as add (as they use the ALU to compute the effective address). Further note that the ALUOp for sub and beq are also 110, which makes sense because a beq is comparing the two (albeit for equality, so xor might also have been used).

We don't see the other I-type instructions in the table, but you can imagine the slti/u also use ALUOp 110 for subtraction and addi/u also use 010 for addition, and that, andi, ori, xori, use the same codes as and, or, xor.

---

The J-type instructions have their own dedicated adders so, no need for ALUOp.
> 1 votes

---
Tags: computer-architecture, cpu, mips
---


# Question
Title: Markov Model to compute the probaility on the $n^{th}$ day
This is a question about Markov Models. Let's say we have the following situation

Let's say that we want to find the probability that $2$ rainy days follow a nice day. You'd simply have $0.25 \cdot 0.5=0.125=12.5\\%$. However let's take it up a notch. What's the probability that on the $7^{th}$ day it's snowy? Or in general how would you find the probability that on the $n^{th}$ day it's a certain weather?

I think that you could take one possibility of a sequence of events, such that on the $7^{th}$ day it snows, such as nice, rain, snow, nice, rain, snow and snow which has a probability of $0.1953\\%$ and then add all such probabilities but I'm not a 100% sure.

# Answer
> 1 votes
Yes, you just add up the probabilities of all the possibilities. However, there's a conceptually clearer way of doing it that's less error-prone.

The transition matrix tells you the probability of moving from one state to another in one step. The probability that it rains the day after tomorrow given that it's nice today is, as you've seen, given by $$\Pr(N\to N)\\,\Pr(N\to R) + \Pr(N\to R)\\,\Pr(R\to R) + \Pr(N\to S)\\,\Pr(S\to R)\\,.$$ If you look at this closely, you'll see that it's exactly the (Nice, Rain) entry of the square of the transition matrix. Similarly, the $n$th power of the transition matrix tells you the probability of moving between two states in $n$ steps.

Powers of the transition matrix can be computed efficiently with repeated squaring – for example $M^7 = (M^2)^2\times M^2\times M$ and there's the bonus that you get all the $n$-step probabilities instead of just one.

---
Tags: probability-theory
---


# Question
Title: Counting arrays with Euclidean distance at most 2 from a given binary array
I have a binary array like this:

$$A = \[0,1,0,0,1,0\]\\,.$$

I'm trying to find a way to calculate how many arrays of the same length exist that have a Euclidean distance of 2 or less from this array.

So, how many arrays of length 6 exist where

$$\sqrt{\Sigma(A\_{\_i} - B\_{\_i})^2}\leq 2\\,?$$

I'm trying to find or create a formula that takes an array like above and outputs a count of how many possible binary arrays exist that fit the conditions of the above formula.

I've looked online for a formula without success.

# Answer
> 2 votes
Don't search for a formula – you'll probably never find something so specific. Instead, try to break up the task into smaller units.

Since your arrays are binary, $$(A\_i-B\_i)^2 = \begin{cases}0 &\text{if }A\_i=B\_i\\ 1&\text{if }A\_i\neq B\_i\\,.\end{cases}$$

So $\sqrt{\sum(A\_i-B\_i)^2}\leq 2$ if, and only if there are at most four values of $i$ such that $A\_i\neq B\_i$. So you just need to compute the number of ways that $B$ could have zero, one, two, three or four different entries from $A$ (or, more simply, the number of ways that it could have five or six different entries, and subtract that from the total possible values of $B$). This calculation is high-school combinatorics. Note that, because the arrays are binary, there's only one value of $B\_i$ that's the same as $A\_i$ and only one that's different.

---
Tags: nearest-neighbour, euclidean-distance
---


# Question
Title: Finding a minimal subset of strings whose bitwise OR is the all ones string
Consider we're given a set $S\subset \\{0,1\\}^n$ and we want to find a minimal subset $A \subset S$ under the property that if we bitwise OR all of the strings in $A$ we get the all ones string $1^n$. I have been having trouble finding a polynomial time algorithm for this or finding evidence that one doesn't exist (e.g.- by showing this problem to be NP-Complete). Does anyone have any ideas or references which may help answer my question?

# Answer
This is the set cover problem, a well-known NP-complete problem, in disguise.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Why scholarly papers focus on DAGs instead of DCGs (Directed Cyclic Graphs)
In trying to understand how to convert DCG's (Directed Cyclic Graphs) to DAG's (Directed Acyclic Graphs) without removing all the edges, I came across this paper which says:

> Since the problem involves DCG, therefore a new algorithm to reduce the DCG into the form of a DAG should be proposed. **It is simpler when no cycle exists in a graph.** A DCGSimplify algorithm is presented to reduce the graph from DCG to DAG.

**Update**

I am wondering what advantages you gain by removing cycles from your data structure. For example, maybe it allows you to traverse it easier during graph matching, or it makes it so you can generate a graph covering of some sort that's not possible with cyclic graphs. Basically I have noticed many papers talk about DAG's, even in relation to CFGs (Control-Flow Graphs) and data-flow graphs, which in practice always have cycles. They restrict it to DAGs for some reason, and don't address Directed Cyclic Graphs, which CFGs and such are most of the time. Wondering why this is, what advantage does DAGs have from a mathematical perspective or computer science perspective.

# Answer
> 4 votes
Let me mention one thing which is absent in the other answers: DAGs actually occur in applications. For example, a Boolean circuit is an ordered DAG whose vertices are labeled by logic gates. Dependencies of various sorts, like prerequisites for different parts of a project, also form a DAG. Wikipedia has many other examples.

Some problems can only be stated for DAGs. For example, topological ordering only makes sense for a DAG. Other problems can be solved faster on a DAG due to its restricted nature. This suggests studying algorithms on DAGs. For similar reasons, there is a lot of literature on algorithms for planar graphs – another naturally occurring class of graphs on which some algorithms run faster.

# Answer
> 2 votes
First, you're drawing overly broad conclusions from one sentence. Just because that one paper happens to look at DAGs doesn't mean you should conclude that scholarly papers focus on DAGs instead of general directed graphs.

Why are some graph problems harder when you have to deal with cycles? Because acyclic graphs are promised to have no cycles, whereas general graphs either might have graphs or might not. As a consequence, in the latter case the algorithm will have to deal with both situations, whereas in the former case the algorithm only has to deal with one of the two situations.

Finally, the most significant reason: DAGs can be ordered. You can topologically sort them, to put the vertices in a particular order. Many problems become simpler to solve. Not all, but many of them. The best way to understand why is to study some examples on your own: say, how to find shortest paths in a general undirected graph vs a dag.

# Answer
> 1 votes
The advantages you get is that you can order vertices and facilitate searches in graphs and finding strongly connected components.

You may find more information in the excellent "Algorithms" (Papadimitriou, Dasgupta, Vazirani) at http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf page 96.

---
Tags: graphs
---