# Question
Title: What is the complexity of sum of Logarithm of an arithmetic series
this is the arithmetic series:

$a/b,2a/b,3a/b,...,ba/b$

The new series:

$log(a/b),log(2a/b),log(3a/b),...,log(ba/b)$

I want the complexity of sum of the latter.

p.s: sorry about formatting.

---

edit 1: I realized that I need to provide more info:

$a,b \in \mathbb{N} $

$a\>b$

a and b are not constants. and the answer is something similar to : $O(b\*log(a))$

# Answer
$f(a,b)=\sum\_{k=1}^b \log(k\*\frac{a}{b})=\log\prod\_{k=1}^b \left(k\*\frac{a}{b}\right)=\log \frac{b!\*a^b}{b^b}=\log(b!)+b\log\frac{a}{b}=b\log a +\[\log(b!)-b\log(b)\]$

by Stirling's formula, $\log(b!)=b\log b -b +\mathcal{O}(\log{b})$

Therefore $f(a,b)=b\log a +o(b\log a)$ so $f(a,b)\sim b\log a$

NB: all asymptotics ($\sim$, $\mathcal{O}$ and $o$) are taken as $a,b\to\infty$ with $a\<b$)

For a more precise evaluation than just an equivalent, replace Stirling's approximation (https://en.wikipedia.org/wiki/Stirling%27s\_approximation) with Stirling's bounds (same wikipedia article).
> 1 votes

# Answer
The complexity of the former is constant. Since we are talking about an Arithmetic Series (a finite sequence of numbers where the difference between any $i+1$ and the $i$ element is constant) the sum can be calculated as half of the product between the number of elements in the sequence and the sum of the first and last

$$ \text{Given a sequence of numbers } s = (e\_1, \ldots, e\_n) $$ $$ \text{where for each } i = 1 \ldots n,\\: e\_{i+1} - e\_i = const$$ $$ \sum\_{i=1}^n e\_i = \frac{n (e\_1 + e\_n)}{2}$$

For your specific example, the sum above will be: $$ \sum\_{i=1}^b i\frac{a}{b} = \frac{b (\frac{a}{b} + b\frac{a}{b})}{2} = \frac{a(1 + b)}{2} $$ That means that the sum of an Arithmetic Series can be calculated in a constant number of operations, no matter how many numbers in the sequence: $ \mathcal{O(1)} $

The second series of sums it's not anymore an Arithmetic Series, thus you need to calculate the following: $$ \sum\_{i = 1}^n log(e\_i) = log(\prod\_{i=1}^ne\_i)$$ due to the properties of logarithms. In your case that will traslate to $$ \sum\_{i = 1}^b log(i\frac{a}{b}) = log(\prod\_{i=1}^bi\frac{a}{b}) $$ In this case you will need to perform $n$ products (well $b$ given your formula...) and the final logarithm, so the complexity strictly depends on the input and linearly: $ \mathcal{O(n)}$
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: What constant in the latest fast matrix multiplication is hidden by Big-O notation?
I'm evaluating the theoretical run time of matrix multiplication algorithms as it has improved within the last few decades. Algorithms to solve matrix multiplication run in O(n^w) time, where w has evolved in the following way:

* w = 3 if using a brute-force approach,
* w = 2.8074 if using Volker Strassen's algorithm \[1969\],
* ... (some interesting improvements later :))
* w = 2.3729 if using Virginia Vassilevska-Williams analysis of the Coppersmith–Winograd algorithm \[2011\]
* w = 2.3728639 if using François Le Gall's adaptation of the Coppersmith–Winograd algorithm \[2014\]

I often hear that the more recent algorithms presented, while theoretically interesting since w approaches 2, are not practical due to the large constant hidden by Big-O. In other words, that the size of the input matrix would need to be extremely large in order for it to be an improvement over Strassen's algorithm, for example. I would like to put a number to this.

What is the rough value of this hidden constant for any of the more recent fast matrix multiplication algorithms? Or, for roughly what input size n of a matrix would the fast matrix multiplication algorithm use less operations than Strassen's algorithm, or the brute force approach?

# Answer
All improvements since Strassen's original algorithm only achieve their exponent in the limit. That is, if they are stated as $O(n^c)$ algorithms, what they really show is that for every $\epsilon\>0$ you can multiply two $n\times n$ matrices using at most $C\_\epsilon n^{c-\epsilon}$ multiplications, where the constant $C\_\epsilon$ blows up badly (exponentially in $1/\epsilon$?) as $\epsilon\to0$. (Coppersmith and Winograd showed that this kind of behavior is actually *necessary*.)

The papers don't explicitly compute $C\_\epsilon$. One reason is that if you are serious about the constant, then you will probably need to apply low-level optimizations that will improve $C\_\epsilon$ at the expense of the simplicity of the algorithm. Another reason is that due to the exponential dependence on $1/\epsilon$, you don't expect the result to be practically meaningful, so it's not really worth it. A third reason is that fast matrix multiplication algorithms are developed in a more abstract framework, which makes it awkward to come up with an actual explicit algorithm.

Fast matrix multiplication algorithms are recursive, that is, they iterate a smart $m\times m$ multiplication algorithm. Whereas for Strassen's original algorithm $m = 2$, for the improvements $m$ depends on $\epsilon$ (exponentially?), and so you will only be able to apply the base case for very large matrices; and for such large matrices, you would actually do much worse than the high school algorithm. The benefits of these algorithms only show up once they have been iterated many times, which would correspond to astronomically high (or worse) dimensions.

If you do feel like working out a constant, there are several expositions of the theory of fast matrix multiplication. You could take the first improvement over Strassen's original algorithm, and try to work out what the parameters are like.
> 3 votes

# Answer
You need to know what you are up against. I assume that you compare one of the "fast" algorithms against an efficient implementation of either naive matrix multiplication or Strassen's 1969 algorithm (it seems that Strassen created an algorithm in 1986 that formed the basic of Coppersmith-Winograd and others).

While the number of multiplications and additions in the naive algorithm is very easy to calculate, the time it takes is much more complicated.

The first problem is that a naive implementation will take most of its time reading the same matrix elements again and again. So the first step is to rearrange the operations so that we read the same numbers again and again. For example, we split the matrices into blocks of 80x80 items or however many fit into the fastest cache. If done properly, this leads to every number being read 80 times from the fastest cache for each time it is read from slower memory.

The next problem is latency. If we naively add up a sum of products, where each addition relies on the result of the previous one, we are limited by the speed of an addition. Instead we calculate multiple sums in parallel, so we are only limited by the number of additions that can be done in parallel.

Then we would use vector instructions. Modern processors may be able to do 4 additions in one instruction as fast as a single one. And then we have to try to use multiple processors that may be available. So with a perfect implementation, the total runtime might be one cycle per four multiplications per available processor.

For large n, say n ≥ 1000, Strassen's method is perfectly efficient. However, it doesn't gain *much*. If you multiply n by 1000, the number of multiplications grows by 264 millions instead of 1000 millions. Absolutely worthwhile but the gain is not that much.

If you examine a faster algorithm, you really need to examine an implementation. And you can assume that the implementation has been done very carefully to gain the maximum speed, because otherwise what is the point?

So you need to check: How many multiplications and additions are needed? And how many can be performed per cycle? For example, if your algorithm addresses items with no simple pattern, just *reading* a value might take 100 times longer than a multiplication.
> 0 votes

---
Tags: algorithm-analysis, asymptotics
---


# Question
Title: Solving recurrences (tree method) with square roots
I am trying to find the upper and lower bounds for this recurrence, but I am not sure how to handle to square root: $$ T(n) = 4T(n/2) + n^2\sqrt{n} $$

# Answer
$n^2 \cdot \sqrt{n} = n^{5/2}$, then you can proceed with the Master Theorem as normal.

If you specifically need to use the Recursion Tree Method for solving recurrences, then you can still proceed normally.

1. Root Level : $n^{5/2}$
2. Next Level : $4 \cdot (n\ /\ 2)^{5/2} = 2^{4/2} \cdot n^{5/2}\ /\ 2^{5/2} = n^{5/2}\ /\ 2^{1/2}$
3. Next Level : $16 \cdot (n\ /\ 4)^{5/2} = 4^{4/2} \cdot n^{5/2}\ /\ 4^{5/2} = n^{5/2}\ /\ 4^{1/2}$
4. etc.
> 1 votes

---
Tags: algorithms, recurrence-relation
---


# Question
Title: How can $\Theta$ and $O$ complexities be different?
From the definition of the $\Theta$-notation, $$f(n)=\Theta(g(n))\\\implies \exists n\_0, \exists c\_1,c\_2\gt 0, \forall n\gt n\_0, c\_1\cdot g(n)\le f(n)\le c\_2\cdot g(n)$$

We can see that the inequality is followed for all $n\gt n\_0$, and hence we can say that $c\_2\cdot g(n)$ is the maximum that this function can reach. Therefore, $f(n)=O(g(n))$ as well.

If we take the example of quicksort, sources say that the $\Theta$ complexity is $n\log{n}$, but $O$-complexity is given as $n^2$.

If the $O$-complexity given is true, then $f(n)\le c\_2\cdot n\log{n}$ will not always be true. So in this case, how is $\Theta$-complexity different from $O$-complexity?

# Answer
There is a bit of confusion. The number of comparisons when using Quicksort to sort n elements isn't a function of n, it's a function of n and the unsorted array. Now if you ask for "the largest number of comparisons for any array of n elements", "the smallest number of comparisons for any array of n elements", or "the average number of comparisons over all arrays of size n", that is a function of n.

The number of comparisons is not $\Theta$-anything because it can vary from about n log n to about n^2 / 2. It is $O(n^2)$ because it is smaller than some constant times $n^2$. The largest number of comparisons for any array of n elements is $\Theta(n^2)$. It would not be $\Theta(n^2)$ if the worst case number of comparisons varied largely with n.

The average number of comparisons over all arrays of size n is simultaneously $\Theta (n \log n)$, $O(n \log n)$, $O(n^2)$ and $O(n!)$ (Big-O allows you to use an unnecessaryly large function, while $\Theta$ doesn't).
> 2 votes

# Answer
> If the $O$-complexity given is true, then $f(x)\leq c\_2n\log n$ will not always be true. So in this case, how is $\Theta$-complexity different from $O$-complexity?

Yuval has covered the quicksort aspects of your question but you have a couple of fundamental misunderstandings about asymptotics.

There is no such thing as "$\Theta$-complexity" or "$O$-complexity". Asymptotic notations such as $\Theta$ and $O$ are simply ways of describing the growth rate of functions. Those functions could be used to measure anything at all (including nothing at all). The complexity is the function (or, rather, the running time is measured by the function); the asymptotic notation is just a way of describing that function's behaviour. As an analogy, suppose that I tell you that my height is "less than two metres": you wouldn't say that my "less-than height is two metres". Likewise, if I say that I weigh about 70kg, you wouldn't say that my "about weight is 70kg." "Less than" and "about" are just ways of describing the numbers that measure those physical properties.

The second misconception is that, for a given function $f$ there is some unique function $g$ such that it's correct to write $f=O(g)$. Remember that $f=O(g)$ means (in a way that's more precise than the following description) "$f$ is kinda less than $g$." To continue the analogy of the previous paragraph, it's completely true to say that my height is less than 2m and that my height is less than 102m. Indeed, there's also no contradiction in saying "My height is about 1.8m and less than 2m", which is directly analogous to "The running time is $\Theta(n\log n)$ and $O(n^2)$."
> 6 votes

# Answer
The worst-case running time of quicksort is $\Theta(n^2)$, and therefore quicksort always runs in $O(n^2)$, and this bound is tight (that is, best possible).

The average-case running time of quicksort is $\Theta(n\log n)$.

The best-case running time of quicksort is also $\Theta(n\log n)$, and therefore quicksort always runs in time $\Omega(n\log n)$, and this bound is tight.

I suggest taking a look at this question for more information.
> 4 votes

---
Tags: time-complexity, asymptotics, big-o-notation
---


# Question
Title: Please provide me a solution of Max-Heapify using Recursion Tree
I tried my best to solve the recurrence relation.

$T(n) \le T(2n/3) + \Theta(1)$

Using the recursion tree.

I could reach out the boundary condition when at depth `i`:

$i= \log\_{3/2}n$

Can someone please help me out in adding the costs and taking out the upper-bound. I know at each depth the cost is increasing by a power of $2$, i:e- $2^i$.

What I have done so far is adding up the costs:

$\sum\_{i=0}^{log\_{3/2}n-1} 2^i+ \theta(log\_{3/2}n)$.

Please correct me if I am wrong. Thank you.

# Answer
Try to solve the recurrent by expanding equality case:

$$T(n) = T(2n/3) + \Theta(1) = T(2^2n/3^3) + \Theta(1) + \Theta(1)$$

Now you can see $T(n) = \Theta(\log\_{\frac{3}{2}}(n))$. Because each time $\Theta(1)$ is added up to reach to the leaf of the expnasion tree. Also, you can reach this result using the master theorem.
> 2 votes

---
Tags: algorithms, recurrence-relation, heap-sort
---


# Question
Title: I need help in this regural expression exercises
> Write a regular expression for the language of words over $\\{0,1,2\\}$ satisfying the following requirements:
>
> * The word has length at least 3.
> * The last symbol is 2.
> * The second to last symbol isn't 0.
> * The combination of the last two symbols doesn’t appear anywhere else in the string.

# Answer
In order to solve this exercise, we need to come up for regular expressions for two classes of words:

* Words of the form $x00$, where $x \neq \epsilon$ and the only occurrence of $00$ is at the end.
* Words of the form $x01$, where $x \neq \epsilon$ and the only occurrence of $01$ is at the end.

Let us start with the first class. For starters, $x$ must end with $1$ or $2$. So such words are of one of the forms $y100$ or $y200$, where $y$ doesn't contain $00$. Presumably you already know how to describe all words not containing $00$ using a regular expression.

For the second class, the only constraints on $x$ are that it is non-empty and doesn't contain $01$. If you don't like the "non-empty" constraint, you can use the following case distinction:

* If $x = y0$ or $x = y2$, then the only constraint on $y$ is that it doesn't contain $01$.
* If $x = y1$, then $y$ cannot end with $0$. It could be empty. If it ends with $2$, then $x$ is of the form $z21$. If it ends with $1$, then we're again in the same situation: the preceding symbol (if any) cannot be $0$. Continuing in this way, we see that either $x \in 1^+$ or $x$ is of the form $y2z$, where $y$ doesn't contain $01$ and $z = 1^n$ for some $n \geq 1$.

I'll let you figure out how to describe strings $y$ avoiding $01$ – this is very similar to the case of avoiding $00$.
> 1 votes

---
Tags: regular-expressions
---


# Question
Title: Select certain number of column elements of a stochastic matrix, maximum one element per row
Consider a $m \times n$ Matrix.
Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1. We now want to choose elements $a\_{i,j}$ of the Matrix.
For every column $k\_j$ elements have to be chosen, but we can choose just one element per row. The sum of the chosen elements have to be maximized.

I guess this problem is NP-hard. I didn't found an efficient solution. To prove that, I want to find a reduction from a NP-hard problem to my problem.

Hopefully someone has an idea for a reduction (or an efficient algorithm).

# Answer
> 3 votes
Duplicate the $j$th column $k\_j$ times to reduce to the case in which $k\_j = 1$. You are now looking at the assignment problem, which can be solved efficiently.

---
Tags: algorithms, optimization
---


# Question
Title: Creating a priority search tree to find number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates in O(n) time
A priority search tree can be constructed on a set of points P in O(n log(n)) time but if the points are sorted on the y co-ordinates then it takes O(n) time. I find algorithms for constructing the tree when the points are not sorted.

I am thinking of a way to do this, which is as follows:

1. Construct a BST on the points. Since the points are sorted then it will take O(n) time.

I followed the approach given in this link for this step.
2. Check if all the nodes satisfy the min-heap property based on the x-coordinates

This will take O(n) time.

So total time complexity will be O(n)

Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates??

# Answer
> Is there a way to make PST in O(N)

The simple is answer is *No*. It will take a minimum $O(NlogN)$ time to construct the tree.

> Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates.

*No*, the algorithm you mentioned will fail when you try to maintain the min-heap property based on $x-coordinates$.When you perform the *min-heapify* operation, the $y-coordinates$ will move from original position and the property of BST (based on $y-coordinates$) will fail. You can't maintain BST property for $y-coordinates$ anymore. So the tree will just reduce to min-heap based on $x-coordinates$.

Here's a thought to construct priority search tree sorted on $Y$-coordinates:

For a given set of points $S$(sorted on $X$-coordinates), create a priority search tree as follows:

1. If $S$ is empty, return a NULL pointer and stop.
2. The point $P$ in $S$ with the greatest $Y$-coordinate becomes the root $R$.
3. If $S-P$ is an empty set , then $R$ is a leaf so we return it and stop.
4. Let $X(P)$ be a value such that half of points in $S-P$ have $X$-coordinate lower than $X(P)$, and half having higher value. Basically $X(P)$ is median(based on $X$) of your $S-P$
5. Recursively create a priority search tree on the lower half of $S-P$, let its root be the left child of $R$.
6. Recursively create a priority search tree on the upper half of $S-P$, let its root be the right child of $R$.

Total time complexity will be $O(nlogn)$ as the tree will be height balanced.

Notes:

1. Since you have sorted points based on $X$coordinates finding median will take $O(1)$.
2. To find the maximum $Y$, for simplification you could also maintain a max-heap based on $Y$. Finding maximum $Y$ from it and subsequently removing from it during creation of priority search tree will take $O(logn)$.
> 1 votes

# Answer
> Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates?

*No*.
In revision 8, it constructs a valid search tree on $y$.
The check in step 2 will almost always yield ***not*** *satisfied*.

The best I thought up, ignoring non-unique priority values:

Proceed the complete binary search tree construction as usual, annotating each node with a priority value that allows to bound searches in the sub-tree it roots.
Inserting node $k$, the path to/from the root will have a length equal the the depth of $k$, and for "the priority side of a PST under construction", its value would have to be annotated to an unknown number of nodes, worst case: to every one on this path for a total of $O(n \log n)$ construction time.
If instead of annotating this "winner", D.E. Knuth presents annotating the loser in TAoCP 5.4.1:
*this is the top priority in this sub-tree without the values on the path from the root*.
Here, only *one* node needs to be annotated, it is on the path between the node inserted in the previous step and the root, with priority increasing in this direction: one can find it in $O(\log \log n)$ steps for a total of $O(n \log \log n)$ construction time.

This does *not* yield a PST.
It *should* yield a search tree supporting $\[-inf, qx\] \times \[qy, qy'\]$ queries no worse than a PST does.
> 1 votes

---
Tags: algorithms, data-structures, computational-geometry
---


# Question
Title: Is Palindrome subset of a regular language regular?
Suppose we have $L$ being a regular language with alphabet $\Sigma$, if we define $M=\\{ x \in \Sigma^{\*} \mid xx^{R} \in L \\}$, then we know that $M$ contains all half copies of palindrome strings of $L$, now here comes the question, is $M$ regular?

Is it easy to see that when $L$ is finite, then $M$ is clearly also finite hence regular. However, what if $L$ is infinite? I think it will be non-regular and try to pumping lemma but does not work...

# Answer
The subset of all palindromes in L is obviously not usually regular, take the simple example $a^\*ba^\*$ where the subset of palindromes $a^nba^n$ is not regular. But that is not the question. The question is about the set of all left halves of palindromes in L.

Assume you have an FSM for L (that is an FSM describing and defining L). You can take that FSM and use a simple algorithm to determine if w is in M:

Given a state S, define succ(S, a) as the state that the FSM will transition to from state S with input a, or nil if there is no transition for a. For a set of states T, define pred(T, a) as the set of states S such that succ(S, a) is not nil and an element of T.

To determine if w is in L, you would start with S = $S\_0$. Then for every symbol s in w, you replace S with succ(S, s), exiting the loop if S is nil. Finally, w is in L if and only if S ≠ nil and S is an accepting state.

To determine if w is in M, you start with S = $S\_0$ and T = set of accepting states. Then for every symbol s in w, you replace S with succ(S, s) and T with pred(T, s), exiting the loop if S is nil or T is empty. Finally, w is in M if and only if S ≠ nil and S is an element of T.

Instead of using this algorithm, you can quite easily construct an FSM for M.
> 2 votes

---
Tags: formal-languages, regular-languages, finite-automata, pumping-lemma
---


# Question
Title: Is it possible to use "and", "or" "not" as relation/predicate in an ontology? In order to represent causality?
If we use an ontology we can represent knowledge, using notably semantic triple `<s,p,o>`.

I was wondering how can I represent this:

A and B cause C

or

A or B cause C

?

I don't want to do reasoning, I only want to represent.

Is it possible to use and, or, negation as predicate/relation in an ontology?

I only see that researchers use causal networks to represent causality, but I was wondering why it is not possible in an ontology.

Thanks in advance,

# Answer
The ontologies that are used today are mostly based on Description Logics (DLs). The basic building blocks of DLs consists of concepts and relationships between concepts where a concept represents a set of individuals (elements) and a relationship states that an individual of one set is related to an individual of another set.

A good book in this regards is An Introduction to Description Logics. There are different DLs with different expressivities and indeed many DLs exist that allow for negation and relations. A freely available tool for creating ontologies is Protege.

The `<s,p,o>` you refer to is related to RDF data and RDFS which do not support negation. Roughly RDFS (similar to relational DB schemas) can be seen as defining the schema and RDF as defining the data (similar to the data of a relational database).

How to design what you require depends on the inferences you want to make from your ontology. Since you don't want to reason over the ontology, you can really model this however you want. Though I am wondering whether using an ontology is the most appropriate if you do not intent do any reasoning.

**Option 1: Using concepts**

```
Class: D
  EquivalentTo: A or B
  SubClassOf: C

```

This will result in any individual belonging to `A` or `B` to be inferred to belong to `C` as well. Concept `D` is introduced to provide a name for the concept `A or B`.

**Option 2: Using Relations**

```
Class: D
  EquivalentTo: A or B

ObjectProperty causes:
  Domain: D
  Range: C

```

This will result in the inference that whenever two individuals `a` and `b` are related via `causes` (written as `causes(a, b)`), it will infer that `a` belongs to `D` and `b` belongs to `C`.

On my blog I have a few posts that give some explanations wrt ontologies as well as some examples.
> 1 votes

---
Tags: artificial-intelligence, knowledge-representation
---


title: in order of binary search tree

text:
# Question
Title: in order of binary search tree
This is what I got for the in-order of the bst but it's wrong because I'm answering some questions about some successors of some of the letters and I got them wrong. so I'm wondering where in this in-order i've gone wrong?

d, b, m, h, i, e, a, j, k, f, g, c

(Sorry if these questions aren't allowed here, please let me know where I can ask it if not!)

# Answer
> 3 votes
Remember that an in-order traversal lists the elements from left-to-right, descending the tree: `Left`, `Root`, and `Right`. This means that starting from the root (`a`), we will traverse the whole left branch, *then* print `a`, and finally traverse the right branch.

You started off correct; however, your mistake was that you put `m` beforee `h`. It is an easy mistake to make so you have to be careful. The `m` node is the *right* node of `h` so the traversal for that subtree will be `h, m`. The same goes for `i` and `e` in your traveral---they should be flipped.

The correct answer for this in-order traversal is `d b h m e i a j f k c g`.

---
Tags: binary-search-trees
---


# Question
Title: On the hardness of satisfying K number of linear constraints
**Background:** Normally in linear programing we have some objective function $$\text{maximize}\sum\_{i = 1}^n a\_i x\_i $$ $$\text{subject to} \sum\_{i =1}^n b\_{ji}x\_i \leq c\_j \text{ for all } 1 \leq j \leq m$$ where $a\_i, b\_{ji}, c\_j$ are all constants given in the problem statement and each $x\_i$ is an optimization variable which we may choose the value of. Note that the above problem may not have a feasible solution if all of the linear constraints cannot be satisfied at the same time. Determining if the constraints are satisfiable and optimizing the objective function can both be done in polynomial time.

**Problem Statement:** Consider a slightly modified version of the above problem where we don't care about the optimization function and are just given the set of constraints

$$\sum\_{i =1}^n b\_{ji}x\_i \leq c\_j \text{ for all } 1 \leq j \leq m $$ We are interested in answering the question "can at least $k$ of these constraints can be satisfied?".

This feels NP-Hard as it it seems to amount to a combinatorial selection problem in the sense that we are now selecting a specific set of $k$ items out of $n$ possible items, and there could only be one such set of $k$ items that works.

**Question:** Is this problem NP-hard, what if we impose $0\leq x\_i \leq 1$ for all $i$? If so, what problem could be used to construct a good reduction?

# Answer
As j\_random\_hacker suggested, we can reduce MAX-2-SAT to this problem.

Given an instance of MAX-2-SAT with $n$ variables $x\_1,\ldots,x\_n$ and $m$ clauses, we can encode it as the following constraints:

1. For each variable $x\_i$, add $m$ identical constraints: $x\_i\le 0$ (if identical constraints are not allowed, we can use $x\_i\le 0,x\_i\le 0.1,x\_i\le 0.01,\ldots$ instead) and $m$ identical constraints: $x\_i\ge 1$.
2. For each clause, say $x\_i\vee x\_j$, add a constraint $x\_i+x\_j\ge 1$. If a negative literal is involved, for example, $x\_i\vee\neg x\_j$, then the constraint becomes $x\_i+(1-x\_j)\ge 1$.

Now we can conclude that there exist $nm+k$ constraints that can be simultaneously satisfied if and only if there exist $k$ clauses that can be simultaneously satisfied in the MAX-2-SAT instance.
> 3 votes

# Answer
Instead of having a constraint $C\_j: \sum b\_{ij}x\_i ≤ c\_j$, introduce another variable $y\_j$, change the constraint to $\sum b\_{ij}x\_i ≤ y\_jc\_j$, add a constraint $y\_j$ ≤ 1, maximise the sum of $y\_j$ (everything straightforward so far), then add a requirement that $y\_j$ must be an integer.

If you fix all mistakes that I may have made :-) then checking that the optimal solution has a value ≥ k should be exactly what you want, with the advantage that you get the maximum number of restrictions that could be fulfilled.

It's now a mixed integer programming problem, and therefore probably NP-complete, but there are algorithms that work probably better than you starting from scratch.

For example, you may get an initial solution ignoring the "integer" requirement with a sum \< k which immediately shows you there is no solution. And an ILP algorithm will probably have some heuristics which y\_i can most likely to 1.
> 0 votes

---
Tags: algorithms, complexity-theory, np-complete, linear-programming
---


# Question
Title: Proving $({L_A}^* L_B)^+ = (L_A \cup L_B)^*L_B$
I'm trying to prove the following identity: $$ ({L\_A}^\*\ L\_B)^+ = (L\_A \cup L\_B)^\*L\_B $$

which is clearly true as both sides will exactly match **"*any sequence of A and B ending with B*"** :

$$ B, AB,AAB, ABBABAB, ... $$

I tried thinking about the set properties and even tried to reasoning about the NFA constructed by the the two sides of the equation but to no avail so far.

Does anyone know how to prove it?

# Answer
The idea is to prove separately the two inclusions, each of them using induction.

**Part 1: $(L\_A^\*L\_B)^+ \subseteq (L\_A \cup L\_B)^\* L\_B$**

We will prove by induction that for all $n \geq 1$, $(L\_A^\*L\_B)^n \subseteq (L\_A \cup L\_B)^\* L\_B$.

When $n = 1$, we need to show that $L\_A^\* L\_B \subseteq (L\_A \cup L\_B)^\* L\_B$. This is clear since $L\_A \subseteq L\_A \cup L\_B$. (More formally, we could prove inductively that $L\_A^mL\_B \subseteq (L\_A \cup L\_B)^m L\_B$ for all $m \geq 0$.)

Suppose that $(L\_A^\* L\_B)^n \subseteq (L\_A \cup L\_B)^\* L\_B$, and let $w \in (L\_A^\* L\_B)^{n+1}$. Thus we can write $w = xy$, where $x \in L\_A^\* L\_B$ and $y \in (L\_A^\* L\_B)^n$. Since $L\_A,L\_B \subseteq L\_A \cup L\_B$, it follows that $x \in (L\_A \cup L\_B)^\*$. By assumption, $y \in (L\_A \cup L\_B)^\* L\_B$. Hence $xy \in (L\_A \cup L\_B)^\* L\_B$.

**Part 2: $(L\_A \cup L\_B)^\* L\_B \subseteq (L\_A^\* L\_B)^+$.**

We will prove by induction that for all $n \geq 0$, $(L\_A \cup L\_B)^n L\_B \subseteq (L\_A^\* L\_B)^+$.

When $n = 0$, we need to show that $L\_B \subseteq (L\_A^\* L\_B)^+$. Since $\epsilon \in L\_A^\*$, it follows that indeed $L\_B \subseteq L\_A^\* L\_B \subseteq (L\_A^\* L\_B)^+$.

Suppose that $(L\_A \cup L\_B)^n L\_B \subseteq (L\_A^\* L\_B)^+$, and let $w \in (L\_A \cup L\_B)^{n+1} L\_B$, so that $w = xy$, where $x \in L\_A \cup L\_B$ and $y \in (L\_A \cup L\_B)^n L\_B \subseteq (L\_A^\* L\_B)^+$. We consider two cases.

*Case 1: $x \in L\_A$.* Since $y \in (L\_A^\* L\_B)^+$, we can write $y = st$, where $s \in L\_A^\* L\_B$ and $t \in (L\_A^\* L\_B)^\*$. Thus $xs \in L\_A L\_A^\* L\_B \subseteq L\_A^\* L\_B$, and so $w = xst \in L\_A^\* L\_B (L\_A^\* L\_B)^\* = (L\_A^\* L\_B)^+$.

*Case 2: $x \in L\_B$.* In this case $x \in L\_A^\* L\_B$, and so $w = xy \in L\_A^\* L\_B (L\_A^\* L\_B)^+ \subseteq (L\_A^\* L\_B)^+$.
> 1 votes

# Answer
Although I can't do the proof completely right now, maybe looking at $(L\_A^\* L\_B)^+ \subseteq (L\_A \cup L\_B)^\*L\_B$ and $(L\_A \cup L\_B)^\*L\_B \subseteq (L\_A^\* L\_B)^+$ helps here. So from left to right: If you take a word $w \in (L\_A^\* L\_B)^+$, can you split it up into $0..m$ subwords of the form $(L\_A \cup L\_B)$ and one postfix-subword of form $L\_B$? I hope this helps you.
> 1 votes

---
Tags: regular-languages
---


title: Finding the fastest sorting algorithm

text:
# Question
Title: Finding the fastest sorting algorithm
I was thinking about how many compares it takes to sort a list of comparable data, and I had an algorithm I was wondering the viability of.

(Its not unlikely that someone has come up with this before me \[though I didn't find anything by researching it\]. So if either this isn't useful, or someone has already come up with this, feel free to close the question.)

So heres my proposition for finding the fastest sorting algorithm. (With no elements equal to each other)

```
1: Create a list of n elements
2: Compare every permutation of elements (e.g. for [A,B,C] compare A to B, A to C, B to C).
3: The element can either be greater than or less than the element it is compared to, so each of these becomes a branch
4: Each of the elements then gains the information from that comparison (eg now A knows its greater than B in case 1, or now A knows its less than B in case 2)
5: Continue until all branches are finished.

```

I'm not too great at explaining, so let me include some examples.

I'll use the symbol "\<\>" to represent comparison @ = done ! = not done For n=3

```
                          [A,B,C]

                          *Start

       A<>B                 A<>C                     B<>C
   /         \           /          \           /          \
 A>B         A<B        A>C         A<C        B>C         B<C
B<>C A<>C  B<>C A<>C  B<>C A<>B  A<>B B<>C   A<>B A<>C   A<>B A<>C
 /\   /\    /\   /\    /\   /\    /\   /\     /\   /\     /\   /\
@  ! !  @  !  @ @  !  !  @ !  @  @  ! !  @   @ !  !  @   !  @ @  !

```

I don't really have space to continue this, but all of the exclaimation points would end on the next iteration.

This shows how when comparing, 3 objects, its doesn't matter how you compare them, all methods are equally good, and end the same quickly.

My idea would be that by running this, you could find the best sort algorithm by adding the minumum from the left and the minimum of the right branch together. This would be recursive, so the shortest on the left branch of A\<\>B is The shortest of \[B\<\>C A\<\>C\].

So this algorithm would return which compares to do to get the list sorted. Since most sort algorithms, do about the same moves on any length list, if we get a couple of examples of the shortest algorithm, its probably feasible to figure out how to generalize it. At the very least, it allows us to compute the least amount of moves to sort a list (which is still an open problem https://en.wikipedia.org/wiki/Comparison\_sort#Number\_of\_comparisons\_required\_to\_sort\_a\_list). You can safely ignore this section if you already know how you would implement this algorithm. The below code is just what I used to program what I have so far, and might be useful to clarify my ideas.

```
import java.util.ArrayList;
public class Compare {
    /*
        These are the objects to be compared, they include a list of integers that
        corresponds to the locations of the objects greater than this object,
        a list of integers represeting position for less than
        And a list of integers that represent positions that corresponds thigns we don't know how relationship to

    */

public ArrayList<Integer> greater = null; //things this is GREATER than
public ArrayList<Integer> less = null; //things this is LESS than
public ArrayList<Integer> unknown = null;
int id;

Compare (int id) {
    this.id = id;
    unknown = new ArrayList<Integer>();
    less = new ArrayList<Integer>();
    greater = new ArrayList<Integer>();
}
public boolean is_defined(Integer other) {
    return !in(unknown,other);
}
public void update_unknown(Compare[] items) {
    //gets rid of all unknown that are already defined
    all_greater(items);
    all_less(items);
    for (int i = 0; less.size() > i; i++) {
    }
    for (int i = 0; unknown.size() > i; i++) {

        if (in(less,unknown.get(i)) || in(greater,unknown.get(i))) {
            unknown.remove(i);
            i--;
        }
    }

}
public boolean done() {
    return (unknown.size() == 0);
}
public Compare copy() {
    Compare res = new Compare(this.id);
    res.greater = copy(greater);
    res.less = copy(less);
    res.unknown = copy(unknown);
    return res;
}
    public ArrayList<Integer> copy(ArrayList<Integer> c) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        for (int i = 0; c.size() > i; i++) {
            res.add(c.get(i));
        }
        return res;
    }
public void compare(Compare other, boolean greater, Compare[] items) { //true if greater than other
    if(greater) {
        this.greater.add(other.id);
        other.less.add(this.id);
    }
    else {
        this.less.add(other.id);
        other.greater.add(this.id);
    }
    this.update_unknown(items);
    other.update_unknown(items);
}
public void all_greater(Compare[] items) {
    for (int i = 0; greater.size() > i; i++) {
        ArrayList<Integer> g =items[greater.get(i)].greater;
        if(g != null) {
            for (int j = 0; g.size() > j; j++) {
                if (!in(greater,g.get(j))) {
                    greater.add(g.get(j));
                }
            }
        }
    }

}
public void all_less(Compare[] items) {
    for (int i = 0; less.size() > i; i++) {
        ArrayList<Integer> g =items[less.get(i)].less;
        if(g != null) {
            for (int j = 0; g.size() > j; j++) {

                if (!in(less,g.get(j))) {
                    less.add(g.get(j));
                }
            }
        }
    }

}
public boolean in(ArrayList<Integer> list, Integer o) {
    for (int i = 0; list.size() > i; i++) {
        if (list.get(i) == o) {
            return true;
        }
    }
    return false;
}
public void init(Compare[] all) {
    for (int i = 0; all.length > i; i++) {
        if (all[i].id != this.id) {
            unknown.add(all[i].id);
        }
    }
}

}

```

Sort Alg:

```
import java.util.ArrayList;

public class SortAlg {
    Compare[] compares;
SortAlg(Compare[] compares) {
    this.compares = compares;
}
public boolean done() {
    for (int i = 0; compares.length > i; i++) {
        if (compares[i].unknown.size() != 0) {
            return false;

        }
    }
    return true;
}

public String print() {
    int res = 0;
    for (int i = 0; compares.length > i; i++) {
        res += compares[i].unknown.size();
    }
    return "" + res;
}

public static Compare[] init_r(int l) {

    Compare[] c = new Compare[l];
    for (int i = 0; l > i; i++) {
        c[i] = new Compare(i);
    }
    for (int i = 0; c.length > i; i++) {
        c[i].init(c);
    }
    return c;
}

public SortAlg copy() {
    Compare[] res = new Compare[compares.length];
    for (int i = 0; compares.length > i; i++) {
        res[i] = compares[i].copy();
    }
    return new SortAlg(res);
}
}

```

Sorts:

```
import java.util.ArrayList;
public class Sorts {
ArrayList<SortAlg[]> sorts = new ArrayList<SortAlg[]>();
public void init(int sz) {
    SortAlg a = new SortAlg(SortAlg.init_r(sz));
    SortAlg[] items = new SortAlg[]{a};
    sorts.add(items);
}

public ArrayList<Sorts> step() {
    ArrayList<Sorts> res = new ArrayList<Sorts>();
    for (int i = 0; sorts.size() > i; i++) {
        for (int j = 0; sorts.get(i).length > j;j++) {
            Sorts s = new Sorts();
            s.sorts = perm(sorts.get(i)[j]);
            res.add(s);
        }
    }
    return res;
}

public ArrayList<SortAlg[]> perm(SortAlg s_) {
    ArrayList<SortAlg[]> res = new ArrayList<SortAlg[]>();
    for (int i = 0; s_.compares.length > i; i++) {

        for (int j = i+1;s_.compares.length > j; j++ ) {

            if ( !(s_.compares[i].done() && s_.compares[j].done()) && !(s_.compares[i].is_defined(j)) ) {

                SortAlg[] tree = new SortAlg[2];
                SortAlg s = s_.copy();

                s.compares[i].compare(s.compares[j],true,s.compares); //going to have problems with memory addresses with this
                tree[0] = s;
                s = s_.copy();
                s.compares[i].compare(s.compares[j],false,s.compares); //going to have problems with memory addresses with this
                tree[1] = s;
                res.add(tree);

            }
        }
    }
    return res;
}
}

```

One of the major problems of this algorithm is the speed. I believe that computing takes somewhere around the O(sum of n! from 1 to length of list).

But there are a lot of ways to speed it up. For example, you could make a greedy algorithm, which only moves down the paths which look promising, and then stop when you've gone above (log\_2(n!)+1) deep (since that means your not looking at the shortest algorithm).

Also, the first step doesn't matter, so you can cut the algorithm down by however many permutation there are on the first step.

# Answer
Your method doesn't scale, since the complexity grows super-exponentially. For small $n$, the best known algorithm is Ford–Johnson, but it is known not to be optimal for larger $n$; this is explained in the linked Wikipedia entry.

Optimal algorithms for small $n$ are not necessarily unique, which makes it harder to generalize them. Moreover, the Ford–Johnson algorithm, which is such a generalization, isn't optimal for all $n$. So this kind of approach doesn't seem to work.

You can read about the state of the art in this pursuit in the OEIS entry A036604.
> 1 votes

---
Tags: sorting
---


# Question
Title: Method to construct a finite state machine for a finite-size language L
I need to define a method to construct a finite automata for a finite language L (part of my proof for something else). My idea:

1. Create $|L|$ accepting states.
2. For each input string $s$ from $L$, create appropriate transitions from a starting state to unique accepting state of s.

I don't know how to formally describe this, or if this idea is even good.

# Answer
Let $S$ be the list of all prefixes of words in $L$. Create a DFA with a state $q\_s$ for each $s \in S$, and an additional sink state $q\_\bot$. The starting state is $q\_\epsilon$, and a state is accepting if it corresponds to a word in $L$. When at a non-sink state $q\_s$, upon reading $\sigma$, move to $q\_{s\sigma}$ if $s\sigma \in S$, and to $q\_\bot$ otherwise. When at $q\_\bot$, always stay there.

To show that this works, prove inductively that when reading a word $w$, if $w \in S$ then the DFA is at state $q\_w$, and otherwise it's at state $q\_\bot$.
> 1 votes

---
Tags: formal-languages, regular-languages, finite-automata
---


# Question
Title: What can't you do without Turing-completeness?
I suppose that, since a Turing-complete language can simulate a Turing-machine, a non-Turing-complete language can't, but most programs do not have the simulation of a Turing machine as their purpose.

I also know that some non-Turing-complete languages can't use unbounded loops, and I suppose that making unbounded loops forbidden is enough to make a language non-Turing-complete. But it doesn't mean that it's the only way.

So, in general, what common properties or abilities of general purpose languages are only possible with a Turing-complete language?

If I decide to design a non-Turing-complete language, what common purpose functions won't I be able to implement with it? Which common source code structures should I forbid?

# Answer
Real world computers are not Turing complete (they have a finite amount of memory) and are equiparable to Linear Bounded Automata.

So the easiest way to design a non-Turing-complete language is to design a language that has only a limited amount of memory (the memory can also be a function of the input length) and don't worry about other restrictions.

But as soon as you allow some kind of unboundness it's not an easy task to avoid Turing completeness, for example two variables that can store an arbitratrily large integer, a JUMP operator, an IF condition and a + operator already defines a Turing complete language (Counter mmachines).

It's curious that even some games (Chess, Magic The Gathering, Minecraft, ...) if you allow level/boards of unbounded size.

The common way is to use bounded loops or bounded recursion; you can take a look to some real-world non Turing-complete languages: SQL, data languages (e.g. Regular expressions,HTML,...), LOOP language, Charity, ...
> 4 votes

# Answer
As an example where unbounded loops are needed: I can write an emulator for any machine, running in a loop. With unbounded loops, that emulator can run forever. With bounded loops, I must calculate beforehand how long that emulator runs. That calculation might return "the simulator will run for one trillion trillion trillion years", which in theory makes a huge difference, but in practice not.

But mostly questions about Turing completeness are asked in a context like "Postscript is Turing complete", "A C++ compiler is Turing complete", "Conway's Game of Life is Turing complete", where the question isn't so much about primitive recursive vs. non-primitive recursive, but whether we can run useful programs at all.
> 3 votes

---
Tags: turing-machines, programming-languages, turing-completeness
---


title: creating a binary search tree (manual)

text:
# Question
Title: creating a binary search tree (manual)
I've been given the following values to add to a binary search tree (in the order given)

56, 35, 55, 58, 29, 15, 16, 5, 71, 92, 69, 95

and this is what my tree ended up like:

but apparently it's wrong?

# Answer
> 0 votes
Yes, it's wrong... The node 29 must be a left child of the node 35, the node 5 must be a left child of the node 15, and the node 69 must be a left child of the node 71 etc. - so, your algorithm makes wrong decision when there is a need to create a left child.

# Answer
> 1 votes
The property that makes a binary tree a binary search tree is that for every branch labeled $x$, all of the labels in the left subtree are smaller than $x$ and all of the labels in the right subtree are greater than $x$.

If you look at your tree, that property is violated in many places. For example, $5$ is in the right subtree of the node labeled $15$, yet $15 \not \< 5$.

---
Tags: binary-search-trees
---


# Question
Title: How can I prove that a Regular Language is closed under Union given two languages with different alphabets?
I need some help to prove that a Regular Language is closed under the union, using a DFA with two differents alphabets.

# Answer
Suppose you have alphabets $\Sigma\subseteq\Sigma'$. You can view any language $L\subseteq \Sigma^\*$ as being a subset of $(\Sigma')^\*$: it just happens to be language of strings that don't contain any symbols from $\Sigma'\setminus\Sigma$.

So, given languages $L\_1\subseteq \Sigma\_1^\*$ and $L\_2\subseteq\Sigma\_2^\*$, you can view both of these as languages over $\Sigma\_1\cup\Sigma\_2$, since $\Sigma\_i\subseteq \Sigma\_1\cup\Sigma\_2$ for $i\in\\{1,2\\}$. Given automata for $L\_1$ and $L\_2$, you can also modify them to work over alphabet $\Sigma\_1\cup\Sigma\_2$.

Now, you have two languages over the same alphabet, so you should be on familiar ground.
> 3 votes

# Answer
Using the accepted answer by @David Richerby -\> I think what we have to do is modify the DFAs that recognize `L1 and L2`. Let L1 alphabet Σ1 and L2 alphabet Σ2,

let `Σ = Σ1 ∪ Σ2`

let's say we have DFA for L1 called M, For M DFA add a extra state called y and for all the letters in Σ but not in Σ1 add a transition from all the states of M to state y. then for all the letters in Σ add a transition from y state to y. Then we have a new DFA (let's call it M1) that recognize the same strings as M DFA but, over Σ alphabet rather than Σ1 alphabet.

we can do the same for L2 language and create a modified DFA with alphabet Σ.

Then we can use them to create a new DFA that can prove the Regular Language is closed under Union given two languages with different alphabets.
> 3 votes

---
Tags: formal-languages, finite-automata
---


title: Path finding through bipartite graph

text:
# Question
Title: Path finding through bipartite graph
Is there a path finding algorithm that exploits a directed bipartite graphs' structure?

I found this: Shortest-Path for Weighted Directed Bipartite Graphs but it didn't seem like the OP needed a bipartite graph and the answer reflected that.

I also found this: https://www.degruyter.com/downloadpdf/j/comp.2013.3.issue-4/s13537-013-0110-4/s13537-013-0110-4.pdf but it's not clear whether the solution is performant and I also don't have a APSP problem.

# Answer
Clearly, an algorithm that runs on bipartite graphs only can't be slower than an algorithm that works on any graph. Therefore, the bipartite-shortest-path problem is in P.

In the opposite direction, consider a transformation that splits every edge into a pair of edges. It results in a bipartite graph and it preserves shortest paths. Therefore, *any algorithm that can find the shortest path in a bipartite graph* with v+e vertices and 2e edges *can also find the shortest path in an arbitrary graph* with v vertices and e edges.

Time complexity of Dijkstra's algorithm is O(e + v log v), so any performance improvement gained by a bipartite-shortest-path algorithm over a regular algorithm is limited to the constant factor of 2. Any faster, and it supersedes the regular algorithm entirely.

The Wikipedia page on the shortest path problem lists several special cases but never mentions bipartite graphs even in passing. It does include an algorithm from 2004 which reduces the time complexity to just O(e + v log log v).

Conclusion: There most likely is no known algorithm for bipartite path search that improves upon the best known algorithm for path search on arbitrary graphs. There is also no room for such improvement in terms of algorithmic complexity, and for only a factor of two in terms of runtime (treating log(log v) as a constant).
> 2 votes

---
Tags: bipartite-graph
---


# Question
Title: Data hazard or forward in MIPS SW after LW in this case?
so we know data hazards may occur on data that is not ready yet and we can solve them by forwarding data in between the pipes.

Look at this piece of code:

```
lw $6, -16($6)
sw $6, -16($5)

```

So the `sw` wants the data that comes from the MEM read and it wants it just for the MEM write. So we can use a bypass to forward the output of the MEM to the input of the MEM (in the data write input) and this is solving the hazard without a bubble (nop).

Is it implemented into the MIPS core and if not, what will it do?

# Answer
Basically no, but what does happen differs.

Typical educational material doesn't forward into the MEM stage, even though indeed it *could* do that, and may show a hazard detection unit (which makes the acronym MIPS a bit of a lie). For example from Patterson & Hennessy - Computer Organization and Design 4th edition (MIPS ver.):

Any load-use hazard is handled by inserting a bubble (the Hazard detection unit at the top does that), even `lw` into the data-operand of `sw` (we cannot forward into the address operand since it needs to go through the ALU), for which there *could* be a separate forwarding unit but there just isn't. In this case, the example code would have a bubble inserted between the load and the store.

In the real MIPS I ISA, implemented by early hardware such as R2000 and R3000, the load-use hazard is *exposed* (leading to a "load delay slot"), as is the control hazard of a branch ("branch delay slot"). This simplified the hardware as there was no need for a hazard detection unit (nor second forwarding unit). It doesn't mean that it runs code *incorrectly* by the way, rather, the code would be incorrect if it doesn't take those things into account: the ISA is "correct by definition" even if it is odd.

These features are not very friendly to students.. and actually also not to more advanced implementations of the ISA. For example, if you have a cache then the latency of a load is variable, delay slots don't solve that, the control logic has to deal with it. MIPS II removed the load delay slot, but the branch delay slots stayed in some form until they were removed quite recently in MIPS32/MIPS64 Release 6 (2014).
> 1 votes

# Answer
It is unclear to me if you ask about the "real" MIPS chips, or about the simplified educational version one sees in class.

If you mean the former, then I would guess it does. Well, the CPU probably has *way* more steps in its pipeline, caches, and tons of other fancy machinery, but I think it is safe to assume that any valid code will run correctly on it.

As for the simplified 5-step pipelined MIPS: again, it depends on which version you refer to. Certain books have load-hazard circuits which are supposed to take care of most situations. But if you have a drawing of the circuits I guess you will be able to tell by yourself if forwarding units exist or not.

The moral is - the MIPS must run correctly any piece of code. If the code you present causes a hazard, then the MIPS hardware must$^\*$ deal with it somehow. In most classes that teach MIPS they leave some parts off so maybe you saw a partial design that doesn't take care of it. If you have a specific version in hand, you can check.

$^\*$Well, if the MIPS hardware doesn't take care of this, then the programmer (i.e., the compiler) must take care of it. This is less desirable.
> 0 votes

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


# Question
Title: Dealing with test condition '=' for a while loop when determining a bound function/loop variant
The following is the definition of what a bound function for a while loop must satisfy:

1. The bound function is an integer-valued, total function of some of the inputs, variables and global data that are defined when the loop is reached.
2. When the loop body is executed, the value of this function is decreased by at least one before the loop’s test is checked again, if at all.
3. If the value of this function is $≤ 0$ and the loop’s test is checked then the test fails (ending this execution of the loop).

I am given a while loop as such,

```
while (j ≤ n) {.....; j = j + 1}

```

where `j` is not touched by the rest of the body of the loop.

I am trying to find a bound function for this simple while loop. Here is what I tried:

* $n-j$ is not a bound function since point (3) fails.
* $n-j-1$ is not a bound function since the loop would not run initially if $n=j$ (since $n-j-1=-1 \ge f(j,n)$), and I am not sure if the latter is a total function due to the presence of $-1$.

How do I deal with the '=' in the '≤' to determine a bound function that satisfies the while loop?

# Answer
> 3 votes
$n-j+1$ should work as it satisfied the three properties of a bound function.

1. It is definitely an integer valued function as all variables and 1 are integers.
2. Since $j$ is increased by 1 in every iteration, the function decreases by 1 each time. For example let's say $n$ was 5 and $j$ was 4. Then for the first iteration it would be 5-4+1=2, then the second iteration would be 5-5+1=1, and then when $j$ is 6, 5-6+1=0, which is also the upper bound for the number of executions of the loop body left.
3. Finally, if the value of the function is at most 0 then the test has to fail, and that is true for this function since if $n-j+1\le0$ then $n+1\le j$, which means that $n \< j$, since both $n$ and $j$ are integers. Since $j\>n$, that means the test must fail and that satisfies the final condition.

Thus $n-j+1$ is a bound function for this algorithm. The answer below is wrong: if $n$ was 5 and $j$ was 4 then $n-j-1$ would be 5-4-1=0 and so the function is at most 0, meaning that the test $j\le n$ must fail, but $4\le 5$ does not fail.

Furthermore, stating that $n-j-1\le0$ then $j\ge n-1$ implies $j\>n$ is incorrect, as if $j\ge n -1$ how would $j$ be greater than $n$ for sure when it was just stated that $j$ could be greater than *or equal* to $n-1$? I am pointing out that the answer is wrong because I too had this same exact question and believed the answer provided before realizing it was incorrect, and so hopefully others would realize that too.

# Answer
> 1 votes
`while (j <= n)` is the same as `while (j < n+1)`, and you know how to handle that, right?

So you find the correct solution for the first case, then replace n with n+1 everywhere. You could handle things like `while (j+3 <= 2n-4)` in exactly the same way, changing it to `while (j < 2n-6)`, finding the solution for the first case, and replacing n with 2n-6.

# Answer
> 0 votes
A bound function is $n-j-1$. Let us check the conditions one by one:

1. $n-j-1$ is an integer-value total function of some of the variables. (A function is total if it is defined on all inputs.)
2. When the loop body is executed, $j$ is increase by one, and so $n-j-1$ is decreased by one.
3. If $n-j-1 \leq 0$ then $j \geq n-1$ and so $j \> n$, hence the loop condition "$j \leq n$" fails.

Another bound function is $n-j-2$: if $n-j-2 \leq 0$ then $j \> n+1$ hence the loop condition fails.

---
Tags: lower-bounds, loops, loop-invariants
---


# Question
Title: What is "Hindley-Milner (i.e., uniﬁcation-based) polymorphism"?
In *Types and Programming Languages* by Pierce, Ch11 *Simple Extensions* extends the typed lambda calculus.

Section 11.5 *Let Bindings* says:

> In Chapter 22 we will see another reason not to treat let as a derived form: in languages with **Hindley-Milner (i.e., uniﬁcation-based) polymorphism**, the let construct is treated specially by the typechecker, which uses it for generalizing polymorphic deﬁnitions to obtain typings that cannot be emulated using ordinary λ-abstraction and application.

What is "Hindley-Milner (i.e., uniﬁcation-based) polymorphism"?

* Is "Hindley-Milner (i.e., uniﬁcation-based) polymorphism" the same thing as let polymorphism?

In Ch22, I searched for "polymorphism", but only find one form of polymorphism: Section 22.7 Let Polymorphism.
* Does "Hindley-Milner (i.e., uniﬁcation-based) polymorphism" mean polytype in the Hndley-Milner type system?

Does Ch22 define or study the Hindley-Milner type system? I can't find it. In particular, does it have the polytype and monotype concepts in the Hindley-Milner type system?

# Answer
> 2 votes
Yes, in that context Hindley-Milner polymorphism is let-polymorphism, since such language uses $\sf let$ to introduce polymorphic functions.

In the untyped lambda calculus, we can consider a (non recursive) ${\sf let}\ x = e \ {\sf in}\ t$ to be syntactic sugar for $(\lambda x.t)e$.

In System F, where polymorphism is introduced by explicit $\Lambda \alpha$ abstractions, we can similarly regard $\sf let$ as syntactic sugar.

By contrast, H-M based languages do not use $\Lambda \alpha$ in terms. Roughly, these languages achieve polymorphism by making $\sf let$ perform the wanted type generalization, as if $\sf let$ implicitly added the $\Lambda \alpha$ binders we would explicitly write in System F. This is done during type inference. For instance the H-M term

$$ \begin{array}{l} {\sf let}\ f = \lambda x.\ x \\ {\sf in}\ (f\ 3, f\ {\sf true}) \end{array} $$

works similarly to the System F (-like) term

\begin{array}{l} {\sf let}\ f = \Lambda \alpha.\ \lambda x:\alpha.\ x \\ {\sf in}\ (f\ \[{\sf int}\]\ 3, f\ \[{\sf bool}\]\ {\sf true}) \end{array}

where the type of $f$ is $\forall \alpha.\ \alpha$, as wanted.

---
Tags: programming-languages, type-theory, types-and-programming-languages
---


# Question
Title: Does a type-1 automaton always have to terminate?
For push-down automata it seems obvious to me that a program must always terminate (given the input is finite), because for each input symbol they advance until eventually they run out of symbols and then terminate.

The opposite is true for Turing machines as they read their input from the tape and are able to alter the position in the input string.

Linear bounded automata are basically Turing machines that have to operate on a bounded range on the tape. As far as I can see, that doesn't prevent you from writing a program for such a machine that just toggles between two states infinitely and thus never terminates.

Is this assumption correct? And can we infer anything about the language an automaton is able to accept from the property if it must terminate eventually? I'm a bit confused about the fact that type-1 languages are a subset of the decidable languages, where the decidable languages require an always halting Turing machine, but I can't find any such restriction for linear bounded automata.

# Answer
> 1 votes
Pushdown automata do not necessarily halt. They are not forced to read input each step, they can also do so-called $\lambda$-instructions where the tape is not advanced. Then we can have an infinite loop at a certain tape position.

Likewise, linear bounded automata may loop, and do not always halt. However, they can be simulated by a Turing machine, which stores each configuration, and tests for loops. That is not efficient of course, but can be done. In that way we get halting machines, but of a different type.

---
Tags: formal-languages, linear-bounded-automata, termination
---


# Question
Title: Proving a DFA recognizes a language using induction
The following DFA recognizes the language containing either the substring $101$ or $010$. I need to prove this by using induction.

So far, I have managed to split each state up was follows:

q0: Nothing has been input yet.

q1: The last letter was a $1$ and the last two characters were not $01$.

q2: The last letter was a $0$ with the letter before that a $1$.

q3: The last letter was a $0$ and the last two characters were not $10$.

q4: The last letter was a $1$ with the letter before that a $0$.

q5: At least one of the two substrings has been seen.

Induction basis: The empty string does not have either of the substrings, so is correctly rejected.

But I am not too sure on how to proceed after this. I do not know how I should split the string up to prove that the $DFA$ is accurate.

If anyone knows how I should proceed with this, I would love some help!

# Answer
> 1 votes
The induction you probably want is to show that a string $w$ ends in state $q\_i$ iff it satisfies the property associated to that state.

The basis then is that the empty string, which must end in $q\_0$, satisfies the property there.

You should be more precise in some of your properties. In $q\_4$, the string ends in 01 as you state, but has never seen any of the special strings, in particular it did not end in 101.

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


# Question
Title: Need help Understanding Concept of Pumping Lemma & Regular Languages
So my professor suddenly decided to make our homework difficult. He did not provide any examples or ways to proof so now I've been stuck on this for a while.

I'm not asking for the solution but rather the right direction in order to get the right answer.

# Answer
> 1 votes
Here's some brief ideas on the pumping lemma that might help get you started.

Essentially the pumping lemma says:

* Any DFA must have a cycle in it at some point. It takes at most $P$ transitions to go from the start state to the end of the cycle. We call $P$ the pumping length.
* We can then break up any word $S$ into three parts:

+ The characters it takes to get from the start state to the beginning of the cycle
    + The characters it takes to go around the cycle (once or more)
    + The characters it takes to get from the end of the cycle to some ending state

That's more or less the same as saying:

* $S = xy^iz$, where:
    + $|xy| \leq P$
    + $|y| \geq 1$ ($y$ is essentially the characters it takes to loop the cycle once)
    + $i \geq 0$ ($i$ is essentially the number of times you go around the cycle)

So you can basically use this as a jumping off point: If you can show that a DFA for a language can't have a cycle in it (that is, it does not satisfy the pumping lemma), then it can't be a regular language.

---
Tags: automata
---


# Question
Title: Solving the recurrence relation T(n) = 2T(n/2) + nlog n via summation
I have seen a few examples of using the master theorem on this to obtain O(n\*log^2(n)) as an answer. I am trying to solve this by unrolling and solving the summation, but I can't seem to get the same answer. My steps are below.

Given $T(1) = 1$, $T(2) = 1$ (Time taken is constant in these two cases)

I noticed that by unrolling a few times: $$T(n) = 2\left\[2T\left(\frac{n}{4}\right)+\frac{n}{2}\log{\frac{n}{2}}\right\] + n\log n$$ $$T(n) = 2^{2}T\left(\frac{n}{2^{2}}\right)+n \log{\frac{n}{2}} + n\log n$$ $$T(n) = 2^{2}\left\[2T(\frac{n}{8})+\frac{n}{2}\log{\frac{n}{4}}\right\]+n \log{\frac{n}{2}} + n\log n$$ $$T(n) = 2^{3}T\left(\frac{n}{8}\right)+2n\log{\frac{n}{4}}+n \log{\frac{n}{2}} + n\log n$$

This looks like it follows $$T(n) = \underbrace{2^{k}T\left(\frac{n}{2^k}\right) + 2^{k}n\log\left(\frac{n}{2^{k+1}}\right)}\_{\log\_2n \text{ times}}$$

I use the fact that $\frac{n}{2^k} = 1$, so $k = \log\_2n$. Substituting this in: $2^{k}T(\frac{n}{2^k})$ = $2^{\log\_2n}T(1) = n$

Doing this summation as: $$T(n)=n + n\log\_2{n}+\sum\_{k=0}^{\log\_2{n}-1}2^{k} n \log\_2\left(\frac {n} {2^{k+1}}\right)$$ $$T(n)=n + n\log\_2{n}+n\sum\_{k=0}^{\log\_2{n}-1}2^{k} \log\_2\left(\frac {n} {2^{k+1}}\right)$$ $$T(n)=n + n\log\_2{n}+n\sum\_{k=0}^{\log\_2{n}-1}2^{k} \log\_2(n-k+1)$$

This is where I get stuck, I have a feeling I messed something up somewhere and it is making this summation much harder to solve, but I am not sure where. Where did I go wrong?

# Answer
First, you can get the the result from the second xase of master theorem. Second, you have a mistake in your exapnsion:

$$T(n) = 2T(\frac{n}{2}) + n\log(n) = 2(2T(\frac{n}{2^2} + \frac{n}{2}\log(\frac{n}{2})) + n\log(n) = n\log(n) + n\log(\frac{n}{2}) + 2^2T(\frac{n}{2^2}) = n\log(n) + n\log(\frac{n}{2}) + 2^2(2T(\frac{n}{2^3} + \frac{n}{2^2}\log(\frac{n}{2^2})) = n\log(n) + n\log(\frac{n}{2}) + n \log(\frac{n}{2^2}) + 2^3T(\frac{n}{2^3})$$

Hence, we will have the following, if we suppose $T(1) = 0$, w.l.o.g:

$$T(n) = \sum\_{i=0}^{\log(n)}n\log(\frac{n}{2^i}) = n \log(\Pi\_{i=0}^{\log(n)}\frac{n}{2^i}) = n \log(\frac{n^{\log{n}}}{2^{\frac{\log(n) \times (\log(n) + 1)}{2}}}) = n \log(n) \log(\frac{n}{\sqrt{2}\sqrt{n}}) = n \log(n)\log{\frac{\sqrt{n}}{\sqrt{2}}} = \Theta(n \log^2(n))$$

Be aware that, if we change the values of $T(1)$ and $T(2)$ to the given constant values, nothing changed in the asymptotic analysis.
> 3 votes

---
Tags: recurrence-relation, recursion, big-o-notation
---


# Question
Title: Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?
NL-Complete languages are defined by Log-space reduction, while PSPACE complete languages are defined by poly-time many-to-one reduction.

According to these posts :

Why not polynomial-space reductions for $PSPACE$-hardness?

PSpace-completeness under PSpace reductions

Every PSPACE language would be PSPACE-Complete if we defined completeness using a Poly-**SPACE** reduction (instead of a poly-**TIME** reduction).

My question is, why does Log-space reduction doesn't imply completeness for every $L \in NL$, for the same reasoning?

Take any **A,B $\in$ NL** , and fixed $y,n$ s.t $y\in A$ and $n\notin A$.

We can define the following log-space reduction **$f$** : $$f(x)=\begin{cases}\ y&\text{if }x\in A\\ \ n&\text{if }x\notin A.\end{cases}$$

Just solve A in log-space and let our output be the fixed instance according to the right case.

How come log-space reductions are NOT useless for NL completeness while Pspace reductions are useless for PSPACE completeness? What am I missing ?

# Answer
Your reduction $f$ works in *nondeterministic* logspace, which is conjectured to be stronger than logspace. Assuming this conjecture, it follows that the concept of NL-completeness is not trivial, that is, not all problems in NL are NL-complete; in particular, problems in L are not NL-complete.

What might be confusing you is that PSPACE=NPSPACE, which is proved using Savitch's theorem. In the context of logarithmic space, the theorem only shows that problems in NL can be decided in space $O(\log^2 n)$.
> 1 votes

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


# Question
Title: If DFA has two states, which of the conditions hold?
Let $L$ be a regular language ,and $M = (Q, Σ, δ, q\_0, A)$ is a DFA such that $L(M) = L$.
Prove that if $|Q| = 2$ then one of the following holds :
a) $L=∅$ b) $ε∈L$ c) $∃a∈Σ$ and $a∈L$

The problem is, I think all of these are FALSE. If there is 2 states, none of them are accepting states, then L will have no elements. This disproves b) and c). However if one of the states is accepting, then a) is false ! I dont see how one of these statements is always true.

# Answer
> 2 votes
You seem to be misunderstanding the statement of the exercise. It wants you to show that if $L$ is a language accepted by a DFA containing two states, then either $L$ is empty, or $L$ contains the empty word, or $L$ contains a word of length 1. Which of the cases holds depends on $L$. More explicitly:

* If no state of the DFA is accepting, then $L = \emptyset$.
* If the initial state of the DFA is accepting, then $\epsilon \in L$.
* If the other state of the DFA is accepting, then either the state is reachable, in which case $\sigma \in L$ for some $\sigma \in \Sigma$, or else it is unreachable, in which case $L = \emptyset$.

More generally, the proof of the pumping lemma shows that if $L$ is accepted by a DFA containing $n$ states, then either $L = \emptyset$ or $L$ contains some word whose length is less than $n$. This is sharp, in the following sense: for each $n \geq 1$ and $m \in \\{0,\ldots,n-1\\}$, there is a language accepted by a DFA of length $n$ whose shortest word has length exactly $m$ (exercise).

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


# Question
Title: Average number of full nodes in rooted m-ary tree
I am looking for a formula to express the average number of full nodes (i.e. nodes having exactly $m$ children) in a $m$-ary tree having $n$ nodes, i.e., $$ \mu\_{n}^{(m)} = \frac{\\# \text{full nodes in all $m$-ary trees having $n$ nodes} }{\\# \text{nodes in all $m$-ary trees having $n$ nodes}}$$.

As to the denominator, according to this answer, it sholud be given by $$n C\_m^n = \binom{mn}{n} \frac{n}{(m-1)n + 1}$$ As to numerator, at the first glance, I tought that this answer would have provided a hint; but then I have realized that it is not the case because it gives how many trees have $n$ full nodes, but I need to know how many full nodes are in the set of all the $m$-ary trees having $n$ nodes.

Could someone help me to understand how to solve it and provide (if any) a usable formula for $\mu\_{n}^{(m)}$?

# Answer
> 1 votes
Every $m$-ary tree is a node together with up to $m$ children, which are also $m$-ary trees. Let $T(x,y)$ be the generating function in which the coefficient of $x^ny^k$ is the number of $m$-ary trees with $n$ nodes and $k$ full nodes. Then $$ T(x,y) = x(1 + T(x,y) + \cdots + T(x,y)^{m-1} + yT(x,y)^m). $$ The generating function of the total number of $m$-ary trees is $A(x) = T(x,1)$, and the generating function of the total number of full nodes in $m$-ary trees is $B(x) = \frac{\partial}{\partial y} T(x,y)|\_{y=1}$.

The generating function $A(x)$ satisfies the equation $$ A(x) = x(1 + A(x) + \cdots + A(x)^m). $$ The generating function $B(x)$ satisfies the equation $$ B(x) = x(B(x) + 2A(x)B(x) + 3A(x)^2B(x) + \cdots + mA(x)^{m-1}B(x) + A(x)^m), $$ and so $$ B(x) = \frac{xA(x)^m}{1-x(1+2A(x)+3A(x)^2+\cdots+mA(x)^{m-1})}. $$

You can try solving these equations.

For example, in the trivial case $m=1$, we have $A(x) = x(1 + A(x))$, and so $$ A(x) = \frac{x}{1-x} = \sum\_{n \geq 1} x^n. $$ It follows that $$ B(x) = \frac{x\cdot \frac{x}{1-x}}{1-x} = \frac{x^2}{(1-x)^2} = \sum\_{n \geq 1} (n-1)x^n. $$ Therefore the average number of full nodes in $1$-ary trees with $n$ nodes is $\frac{n-1}{1} = n-1$.

---
Tags: trees, combinatorics
---


# Question
Title: Give an example of a connected graph where α(G) =100 and β(G) = 200
So I need to find a form of a graph such that its vertex cover is twice that of its matching, but I am running into problems brainstorming, I know K3 is of this form, but not one at such a magnitude.

# Answer
> 1 votes
You are on the right track, just keep going: what if you take a slightly larger complete graph? Specifically, what if you take a $K\_{101}$?

---
Tags: graphs, matching, vertex-cover
---


title: Strongly connected graph proof

text:
# Question
Title: Strongly connected graph proof
Here I have a proof related to strongly connected graph from Algorithms book.

However, when I run DFS on the following 2 strongrly connected graph, I get different result than the proof.

According to property, highest post number in C is bigger than the highest post number in D but it is not. Where am I making mistake?

# Answer
Your post-traversal numbering of the component $C$ is incorrect. The vertex labeled as $1,6$ was assigned its post-traversal number too early; a depth-first search will also explore the vertices of $D$ before assigning the post-traversal number to this vertex.
> 2 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: Simple cycles of length two in an undirected graph
Pedagogical question.

**Background**

A cycle in a graph can be defined as a sequence of vertices $v\_1,\dots,v\_n$ with $v\_1=v\_n$ such that, for each $i \in \\{1,\dots,n-1\\}$, the graph has an edge $(v\_i,v\_{i+1})$. (One can define it differently.)

**The point**

Every definition of *simple* cycle I have seen is: a cycle with no repeated vertices, except the first and last.

But this definition implies that even in undirected graphs, we can have simple cycles of length two, e.g. $u \to v \to u$. However, we probably do not want to consider this a simple cycle because it re-uses the edge $(u,v)$ and this would break several algorithms and proofs.

Of course for cycles of length $3$ or more, requiring no repeated vertices implies there are no repeated edges.

**The question**

Which of the following is right? Justify your answer.

(1) The standard definitions are incorrect, they ought to explicitly exclude simple cycles of length 2 in undirected graphs.

(2) The standard definitions are correct, the cycle of length 2 **is simple**.

(3) This question is wrong in claiming this is the standard definition of simple cycle. There are other better definitions that are standard (references please!).

# Answer
I'll go with (3)

From Bondy and Murty's *Graph Theory with Applications* (http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph\_Theory\_Bondy\_Murty.pdf), sections 1.6 "Paths and Connections" and 1.7 "Cycles":

A *walk* is a finite non-null sequence of alternating vertices and edges (repetition of both allowed).

If the edges of a walk are distinct then it is also a *trail*. If in addition the vertices are distinct then the trail is a *path*.

A walk is *closed* if it has positive length (defined as its number of edges) and its origin and terminus are the same (vertex). **A closed trail whose origin and internal vertices are distinct is a cycle.**

SUMMARY: So in this system of definitions, a *cycle* cannot repeat edges or vertices except the origin/terminus, which excludes walks of length two.

However, it is true that there are other contradictory definitions in the literature which is why it is best to always restate the definitions in say a paper or course.

PS: For the sake of completion, I believe that in this system of definitions (although I did look for it in this particular reference), a *circuit* is a closed trail (repetition of vertices allowed, but not of edges).
> 3 votes

# Answer
It turns out that the very popular textbook *Introduction to Algorithms* by Cormen, Leiserson, Rivest, and Stein, sneakily avoids this issue by giving a different definition of cycle in undirected vs directed graphs.

In Section B.4, it defines cycle and simple cycle as I do (they also require at least one edge), *in directed graphs*. In an undirected graph, they define cycle the same way *except* they require that all of the edges in the cycle be distinct; and they say the cycle is simple if in addition the vertices are distinct, other than $v\_1=v\_k$.
> 5 votes

# Answer
Arguably two of the most definite textbooks on graph theory are Bundy & Murty (BM) (roughly 15000 citations at the time of writing) and Diestel (at least hundreds of citations).

In BM (Section 1.6), the definition of a cycle is obtained via walks and trails, i.e., a *cycle* is a non-empty *trail* in which the first and last vertex are repeated. In your example, $uvu$ is not a cycle because in a trail all edges are distinct. So in particular, there's no need to explicitly forbid length-2 cycles as the definition of a trail takes care of this.

In Diestel (Section 1.3), the author begins by defining a *path* $P=(V,E)$ with $V=\\{x\_0,x\_1,\ldots,x\_k\\}$ and $E=\\{x\_0x\_1,x\_1,x\_2,\ldots,x\_{k-1}x\_k\\}$. Then, if $P=x\_0,\ldots,x\_{k-1}$ is a path and $k \geq 3$, the graph $C := P + x\_{k-1}x\_0$ is a *cycle*.

In addition, the current Wikipedia entry on a cycle refers to Bender & Williamson which seems to use the same definition as BM.

In summary, both definitions should capture precisely the set of objects.
> 3 votes

---
Tags: graphs, pedagogy, definitions
---


# Question
Title: How is this equation (involving a recurrence and $\phi(N)$) derived?
As in another question, let

$$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\phi(N)) + \lg(\phi(N))^3 & \text{otherwise} \end{cases}$$

where $\phi(N)$ is Euler's totient function.

Tasse kindly reasoned that we can write

$$T(N) = T(\phi(N))+\log(\phi(N))^3 = T(\phi(\phi(N)))+\log(\phi(\phi(N)))^3 + \log(\phi(N))^3$$

I can't at all see why this is true. How is this equation derived? I do understand his proof that $\phi(\phi(N)) \< N/2$.

# Answer
> 2 votes
Here's the relevant part of the proof, quoting verbatim:

> First, show that $\phi(\phi(n)) \< n/2$. This can be done as such:
>
> Let $n = \prod\_{i=1}^rp\_i^{k\_i}$ be the prime factorisation of $n$ ($p\_i$ prime, $k\_i\>0$)
>
> * Suppose $n$ is even. Then $\phi(n) = n\prod\_{i=1}^r(1-\frac{1}{p\_i}) \leq n(1-\frac{1}{2}) \leq n/2.$ Thus $\phi(\phi(n)) \< n/2$.
> * Suppose $n$ is odd and $n \> 1$. Then $\phi(n) = \prod\_{i=1}^r (p\_i-1)p\_i^{k\_i-1}$ is even and smaller than $n$. By the previous result $\phi(\phi(n)) \< n/2$.
>
> So we get the desired result.

This lemma is slightly mis-stated, because when $n=2$, $\phi(\phi(n)) = n/2$. But it doesn't invalidate the main result. We will state the lemma as:

**Lemma** For all $n \ge 2$, $\phi(\phi(n)) \le \frac{n}{2}$.

Tasse's proof sketch is a proof by induction in disguise, but this may not have been obvious to you. I'm going to simplify the proof sketch a little bit and lay it out more like a proper proof by induction.

**Proof** By induction on $n$.

Base case: If $n=2$, see above.

Inductive step: Suppose that for all $2 \le m \< n$, $\phi(\phi(m)) \le \frac{m}{2}$. We want to prove that $\phi(\phi(n)) \le \frac{n}{2}$.

Case 1: Suppose $n$ is even, that is, $n = 2q$ for some $q$. In this case, the multiplicative property of the totient function says that $\phi(2q) = \phi(2) \phi(q) = \phi(q)$.

That is, $\phi(n) = \phi(\frac{n}{2})$. However, another useful property of the totient function is that for all $m \ge 2$, $\phi(m) \le m-1$. Therefore $\phi(\phi(n)) \le \frac{n}{2} - 1$.

This proves what we wanted for this case, but we have also incidentally proven another useful thing: If $n$ is even, then $\phi(n) \le \frac{n}{2}$. This will be important in the next step.

Case 2: Suppose $n$ is odd. That is, $n = p^k q$ for some odd prime $p$, and some positive integer $k$, and some $q$ which doesn't have $p$ as a divisor. Then:

$\phi(n) = \phi(p^k) \phi(q) = \left(p^k - p^{k-1}\right) \phi(q)$.

Now there are two things you need to notice about the right-hand side.

First off, it's less than $n$. Why? Because clearly $p^k - p^{k-1} \< p^k$, and it's a standard property of the totient function that $\phi(q) \le q$. (Note that this is also true if $q = 1$.)

Secondly, it's even. Why? Because if $p$ is odd, $p^k - p^{k-1}$ is even.

So by that incidental result we discovered in case 1:

$\phi(\phi(n)) = \phi(\left(p^k - p^{k-1}\right) \phi(q)) \le \frac{\left(p^k - p^{k-1}\right) \phi(q)}{2} \< \frac{n}{2}$.

QED

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: What are the elements of the modular ring mod 7?
Are the elements of a modular ring simply the set of all the numbers from 1 to p−1?

in this case p−1 = 6 ?

I asked this on the math stack exchange https://math.stackexchange.com/q/3375667 and was told that 0 is included in the the ring. Is this treated differently in CS ?

# Answer
> 2 votes
You might be confusing the ring and the multiplicative group of invertible elements mod p. The first one is isomorphic to the integers from 0 to p-1, 0 being the additive neutral element, and 1 being the multiplicative neutral element.

If p is prime, the intervible elements are the integers from 1 to p-1, and they form a multiplicative group.

By the way, when p is prime, such a ring (all elements except 0 are invertible) is called a field.

# Answer
> 1 votes
They aren't treated any different.

The elements in the mod ring of any integer x include all numbers in the range `[0,x-1]`.

However, different programming languages treat negative numbers in different ways.

`(-5) MOD 3 = 1` in Python.

whereas,

`(-5) MOD 3 = -2` in C.

This problem can be solved by simply adding the value to the negative result.

In this case `-2 + 3 results in 1`.

---
Tags: cryptography, modular-arithmetic
---


title: post order for binary search tree

text:
# Question
Title: post order for binary search tree
I got this as the post order sequence but the answer says it is wrong. I do get a bit confused with the post order logic as well.

8 11 10 9 13 16 18 15

# Answer
There are two `13` in the Binary Search Tree.

The left node of 15 can not be a 13 since it violates the BST property.

Instead, it can be replaced with `14` or any value in `(13,15)`.

Resultant Traversal will be `8 11 10 9 x 16 18 15 13`

where x is the value you choose to replace the left child of `15`
> 0 votes

# Answer
The correct ordering is $8, 11, 10, 9, 13,16,18,15,13$
> 0 votes

---
Tags: binary-search-trees
---


# Question
Title: Is Space Complexity Always Less Than Or Equal To Time Complexity?
**Background**
I am working on proving a novel problem to be P-Complete, and this requires using a logspace reduction to reduce some known P-Complete problem to the novel problem. Particularly, I am reducing the Circuit Value Problem, the de facto P-Complete problem, to the novel problem.

**The Experienced Difficulty**
P-Complete reductions must use logarithmic space in the reduction in order to be meaningful. However, for the novel problem, it is very easy to show that the reduction takes logarithmic time, whereas it is difficult to show that it takes logarithmic space.

**The Complicating Factor**
There are many Q and A sites online which declare that an algorithm's space complexity is always less than its time complexity. For example: https://www.quora.com/Is-there-any-algorithm-whose-space-complexity-is-more-than-time-complexity. This is just one of many. I have scoured the literature on the subject, reading through Cook, Karp, Stockmeyer, and many more, yet I am unable to find this claim that space complexity is always less than time complexity captured in a rigorous manner. Yet this claim seems pervasive and almost treated as "common knowledge".

**Why the Complication Matters**
If it is true that space complexity is always less than or equal to time complexity, then instead of doing a logspace reduction, I can show that the reduction can be done in log time, which is much easier in my particular case.

**What I Need**
Can anyone point me to the paper which established this "common knowledge" idea that space complexity is always less than or equal to time complexity? Or a textbook or other authoritative source?

-Thank You

# Answer
The reason it's common knowledge and not formally proved anywhere is because it's obvious. During each time step, you can only access one memory location. Therefore you can never access more memory locations than you have time.

I found the following reference, showing an even slightly stronger result: every deterministic multitape Turing machine of time complexity $t(n)$ can be simulated by a deterministic Turing machine of tape complexity $t(n)/\log t(n)$.

> If it is true that space complexity is always less than or equal to time complexity, then instead of doing a logspace reduction, I can show that the reduction can be done in log time, which is much easier in my particular case.

This suggests that something is wrong with your understanding. Showing that it runs in logarithmic time is strictly harder than showing it uses logarithmic space. Something really weird has happened. As Robert Anderws rightfully points out in his comment, no reduction from the Circuit Value Problem can run in logarithmic time and be correct, since it can't even read the entire input.
> 6 votes

---
Tags: complexity-theory, time-complexity, space-complexity
---


title: Euclidean Models

text:
# Question
Title: Euclidean Models
I am asked to prove that every Euclidean models satisfies $\diamond \diamond \diamond \varphi \to \diamond \diamond \varphi$. How can this be done? I don't see how it could even be true.

# Answer
Suppose $w$ is a world in an Euclidean frame, and $w\mathbin R v$, then by the Euclidean property $w$ reaches both of the "two" worlds $v$ and $v$ (indeed, the same world), and thus $v\mathbin R v$. So in a Euclidean frame, any world that is reachable from some other world, reaches itself (or every world with an incoming arrow has a reflexive arrow).

Now, suppose $w\vDash\Diamond\Diamond\Diamond\phi$, then we know that $w\mathbin R v$ for some world $v$ such that $v\vDash \Diamond\Diamond\phi$. This, in turn, means that $v\mathrel R u$ for some world $u$ such that $u\vDash \Diamond\phi$. By the above argument we see that $v\mathbin R v$, since $v$ is reachable from the world $w$. Thus we have $v\mathrel R v$ and $v\mathrel R u$, which implies that $u\mathrel R v$ by the Euclidean property. Furthermore, we have $u\mathrel R u$ as well, since $u$ is reachable from $v$.

The final step is to see that because $u\vDash \Diamond \phi$, there is some $z$ such that $u\mathrel R z$ and $z\vDash\phi$. By the same reasoning as before, we can find out that not only $u\mathrel R z$, but also $v\mathrel R z$. This gives us that $w\mathrel R v\mathrel R z$, and thus $w\vDash \Diamond\Diamond\phi$.

---

As a sidenote, the way to see Euclidean frames, is as a bunch of "clusters" of worlds, where a cluster is a group of worlds that are completely connected with each other (i.e. each world in the cluster can reach every other world in the cluster), with (optionally) some "outside" worlds that reach any number (including 0) of the worlds inside one (and only one) cluster, but are not reachable from any other world.

An example in a picture, with the "clusters" in dots connected with red arrows, and the "outside" worlds those dots with blue arrows leaving them:
> 4 votes

# Answer
It's true actually. As a hint, the Euclidean property $$xRy \quad\\&\quad xRz \implies yRz$$ does not require the $x,y,z$ to be distinct. So for instance it implies $$xRy \quad\\&\quad xRy \implies yRy.$$

Try to construct a counterexample model with 4 worlds $w,x,y,z$ where $\phi$ holds only in $z$ and where $wRx, xRy, yRz$.
> 1 votes

---
Tags: logic, modal-logic
---


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

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

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

---

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

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

Now, analysing the two sequences we find that:

1. $(x\_n)$ is decreasing
2. $(y\_n)$ is increasing
3. $x\_0\>y\_0$

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

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

# Answer
> 1 votes
One method is guessing that x ends up close to $m^{1/2}$ and prove it. The guessing is the hard part.

My method would be to try this for a few values of m, print out the results, make the same guess and prove it in the same way.

Another method is to solve a few hundred problems, look at the code, recognise it, guess x and prove it.

A not very promising method is staring at the code and waiting for enlightenment.

Now if you have the guess: You will find for m \> 1 that initially x is almost divided by 2 in each step. When x is close to $m^{1/2}$, write $x = m^{1/2} * (1 + c)$ and see how the calculation changes c.

---
Tags: algorithms, c
---


# Question
Title: Is language {M | M halts and print "Hello World"} recursively enumerable?
Is language {M | M halts and print "Hello World"} recursively enumerable? I'm not sure my proof is correct. Let universal Turing machine U start another Turing machine M2 that reads result of work of given Turing machine M1, which halts on "Hello World" and goes to infinite loop otherwise. Then M2(M1) halts if and only if M1 prints hello "Hello World".

# Answer
> 2 votes
Enumerate all turning machines $M\_1, M\_2, \dots, $ and simulate them in a dovetail fashion, i.e., proceed in rounds:

* In the first round simulate $M\_1$ for $1$ step;
* In the second round simulate $M\_1$ and $M\_2$ for one (more) step each;
* In the third round simulate $M\_1$, $M\_2$ and $M\_3$ for one (more) step each;
* ...

In general, at the $i$-th round you perform one additional step for all turning machines in $\\{ M\_1, \dots, M\_i \\}$ that have not yet halted. Whenever a Turing machine $M$ halts, check if its output is "Hello World" and, if so, return $M$.

---
Tags: turing-machines
---


title: Find N best subset of quotations

text:
# Question
Title: Find N best subset of quotations
I am faced with the following problem;

We are provided cost quotations for shipping cost per packet by various shipping companies, let's call these quotations $Q\_1 ... Q\_k$. Each Quotation is a $M \times N$ matrix with weights categories of packets along one axis and size categories along the other axis. We are provided with a list of packets as well with respective weights and sizes such that we can convert the packages to be shipped into a 2d matrix of size $M \times N$ as well based on categorization of each packet and each cell shall contain the relevant number of packets in that weight+size category. Let's call this matrix $P$.

The total shipping cost for all the packets should we chose a shipping company '$i$' is sum of ( $Q\_i \times P$ ) where '$\times$' is the element-wise multiplication of the two matrices.

We are required to find a subset of size '$w$' shipping companies (or quotations) such that the overall shipping cost is minimum.

I understand that a brute force algorithm trying out all combinations is not going to work due to the explosion of the number of combinations as '$w$' starts to increase. Moreover, I have also convinced myself that I can not iteratively build out a solution by first selecting two best quotations, merging them into one and then continue to add one more till I reach '$w$'.

Can someone help me find the relevant class of problems and suggest a solution?

# Answer
This problem is $\textrm{NP}$-hard by a reduction from (the decision version of) set-cover: given an integer $k$, a set of items $I = \\{x\_1, \dots, x\_n\\}$ and a collection $S = \\{S\_1, \dots, S\_m \\} \subseteq 2^I$ of subsets of $I$, decide whether there is a subset $C$ of $S$ such that $|C| \le k$ and $\bigcup\_{S\_j \in C} S\_j = I$.

Given an instance of set-cover, we can reduce it to your problem as follows:

* There are $n$ packages to be shipped. Each package has a unique combination of weight class and category. For simplicity you can think of all the packages being in same category but having different weight classes. I will denote by $W\_i$ the weight class of the $i$-th package.
* There are $m$ shipping companies. The $j$-th shipping company ships a package of weight class $W\_i$, with $x\_i \in S\_j$, for a cost of $\varepsilon \< \frac{1}{n}$ and a package of weight class $W\_i$, $x\_i \not\in S\_j$, for a cost of $1$.
* Pick $w = k$.

There is a set-cover of size at most $k$ iff the cost for shipping all the packages using at most $w$ companies is at most $\varepsilon n \< 1$.

Indeed, given a set-cover $C = \\{ S\_{j\_1}, \dots, S\_{j\_\ell} \\}$ of size $\ell \< k$ we know that $\bigcup\_{i=1}^\ell S\_{j\_\ell} = I$, i.e., if we select the $j\_1$-th, $j\_2$-th, $\dots$, and $j\_\ell$-th shipping companies, we can send each of the $n$ packages at a cost of $\varepsilon$.

On the other hand, if there is a way to send all the packages using at most $w$ shipping companies with a cost of at most $\varepsilon n \< 1$ then, for each of the $n$ packages, there must be at least one selected company that ships it with a cost of $\varepsilon$. In other words the sets $S\_j$ corresponding to the selected companies are a set-cover of size at most $w = k$.

Notice that any solution has either a cost of $\varepsilon n$ or a cost of at least $1$. Choosing $\varepsilon$ small enough shows that this problem is also inapproximable (in fact, if a shipping cost of $0$ is allowed, you can directly set $\varepsilon = 0$).
> 2 votes

---
Tags: algorithms, subset-sum
---