# Question
Title: How to find the lightest path that has at least one vertex of each color?
I've faced this question in my homework.

In a graph $G=(V,\ E)$ where every $v\in V$ has a color, a colored path is a path such that it has at least one vertex of each color.

We're given a directed graph $G=(V,\ E)$, weight function $w:E\rightarrow \mathbb{N}^+$ (in other words the weights are positive) and every vertex is colored one of $\\{r,g,b\\}$. We're required to find the lightest colored path from a given vertex $s\in V$ to every $v\in V$ (including $s$ itself). Such a path may not be simple. If such a path doesn't exist then the lightest path equals $\infty$.

I solved this problem where edges instead of vertices are colored. The problem where vertices are colored is harder in my opinion.

It is clear we have to use Dijkstra's algorithm.

I thought of a possible solution of splitting every vertex to two vertices and then adding an edge between these two copies but the problem is still with the edges between the main vertices which we can't decide which color to give them.

# Answer
> 1 votes
Let $P$ be all non-empty subsets of $\\{r,g,b\\}$, i.e., $$P=\\{\\{r\\},\\{g\\},\\{b\\},\\{r, g\\},\\{r,b\\},\\{g,b\\},\\{r,g,b\\}\\}.$$

Build a weighted directed graph $H=(V', E', w')$ where:

* $V' = V \times P$
* $E'= \left\\{((u, \alpha), (v, \beta))\mid (u,v)\in E \text{ and }\beta=\alpha\cup\\{\text{the color of } v\\} \right\\}$
* $w'((u, \alpha), (v, \beta)) = w(u,v)$.

In plain words, for $H$,

* The vertices are seven copy of original vertices with each copy colored a combination of $r, g, b$. The color combination will be used to track the colors of the visited vertices in a path.
* If there is an edge from $u$ to $v$ in $G$, then for every color combination, there is an edge from $u$ of that color combination to $v$ of the color combination that extends that color combination with the color of $v$. In other words, we include the color of $v$ into the visited-color combination when we travel from $u$ to $v$.
* The weight of an edge is the same as the given weight of the edge between the vertices in $G$ ignoring the colors.

Now we can apply Dijkstra's algorithm on $H$ with source $(s,\\{\text{the color of } s\\})$ and destination $(v, \\{r,g,b\\})$. With the second component, the color combinations ignored, the result becomes the shortest colored path between $s$ and $v$ in $G$.

---

This answer is quite similar to this answer to another question of yours. The general idea is to keep track of the additional requirement such as the order of colors traversed so far or all colors traversed so far in one or more additional parameters, or, in the terminology of this answer, in a finite state machine.

---
Tags: algorithms, shortest-path, weighted-graphs, colorings, dijkstras-algorithm
---


# Question
Title: Subclass of problems of an NP hard problem
I have an NP hard problem $P$ that takes in arbitrary $G = (V, E)$ as input. I have another problem $Q$ that I want to show is NP hard, and this problem has arbitrary complete graphs $G'$ as input. Is this enough to say that $Q$ is also NP hard, since it is a subclass of the NP-hard problem with arbitrary inputs, or is this insufficient?

# Answer
It is not sufficient, an "input restriction" like that can easily move that problem to a lower complexity class.

For example, graph coloring in general is NP hard, graph coloring on only complete graphs is trivial.
> 0 votes

---
Tags: np-complete, np-hard
---


# Question
Title: Sorting a list over rounds of binary comparisons
You have a list of $n$ items you want to sort over $r$ rounds using binary comparisons. In each round, you specify $k$ binary comparisons to be made **in parallel**. The objective is to fully sort the list.

For example, if you want to sort in $r\in \Theta(n \log(n))$ rounds, then you only need to make $k=1$ comparison per round (and use any decent algorithm like mergesort). This is the fully sequential case.

If you want to sort in $r=1$ round, you need to make $k\in\Theta(n^2)$ comparisons to successfully sort the list with a probability that doesn't vanish asymptotically (https://cs.stackexchange.com/a/118535/90344). This is the fully parallel case.

Using sorting networks (in particular, the bitonic mergesort network), then one can successfully sort a list in $r\in(\log^2(n))$ rounds with $k=n$ comparisons made per round.

My question is, what is the optimal tradeoff between $r$ and $k$? I.e. if I specify some $r$ (e.g. $r\in\Theta(\sqrt{n})$), then what is the minimum $k$ needed, or vice versa? And what might the accompanying algorithm be?

Lastly, is there aught to be gained by adjusting the number of comparisons made each round? E.g. is it the case that doing more comparisons in earlier rounds (and less in later rounds) will sort the list in fewer overall comparisons/rounds?

# Answer
> 2 votes
Your problem is known as *sorting in rounds* or *parallel sorting*, first considered by Valiant.

The celebrated AKS sorting network (simplified by Patterson) has depth $\Theta(\log n)$, showing that when $r \geq C\log n$ (for an appropriate constant $C\>0$), the optimal number of comparisons per round is $\Theta(n\log n/r)$.

For smaller $r$, the optimum is $\tilde\Theta(n^{1+1/r})$, as shown by Alon and Azar (lower bound) and Bollobás and Thomason (upper bound); the two bounds differ by polylogarithmic factors.

For pointers to the literature, consult Wigderson and Zuckerman, Expanders that beat the eigenvalue bound: explicit constructions and applications.

---
Tags: algorithms, complexity-theory, time-complexity, sorting, parallel-computing
---


# Question
Title: What does type theory as a theory of inductive definitions mean?
Unfortunately copy/paste doesn't work for this paper Inductive Definitions and Type Theory, but here is a snippet.

The paper begins by stating:

The first sentence of the second paragraph says **type theory as a theory of inductive definitions**. I have never really paid much attention to how central induction is to type theory, but it seems to be one of the main requirements, hence this question.

**Is induction a requirement for type theory?** That is, can you have a modern robust type theory or typed programming language without induction? If not, why not? If so, what would it look like generally speaking (just looking for pointers for the right research to look into). Why is induction central to type theory? What does type theory as a theory of inductive definitions mean?

Sorry if this is a really basic question. I am just trying to get a solid grasp of the foundations, and asking anything that is unclear to me in the process without having a full picture and being an expert yet.

# Answer
Induction is not a requirement. You can take inductive definitions out of Martin-Löf type theory, and you still get a consistent theory. It's just not an interesting theory.

Without induction, you can only make finitary, non-self-referential descriptions of data and proofs. If you interpret types as sets of terms, without induction, types are just certain finite subsets of certain finite sets. You don't need such theoretical machinery to reason about finite sets. Reasoning about finite sets opens different problems, mostly about keeping the descriptions down to a reasonable size.

Type theory aims to reason about infinite classes of objects. For example, there's a type containing all lists of integers, not just some finite collections of integers. And you can make functions that work over arbitrary lists, regardless of their length: without induction, a function could only act on a limited number of objects for a given length of the function's source code.

Type theory lets you reason about interesting properties of objects *even when* those objects are inductively defined.
> 1 votes

---
Tags: reference-request, type-theory, induction
---


# Question
Title: Tight bound for T(n) = T(n/2) + T($\sqrt{n}$) + n
I have seen examples of how to find the solve the recurrence for T(n) = T($\sqrt{n}$) + n, but how do we go about if there is another T(n/2) in there?

So I tried to unfold the recurrence out and this was what I got:

T(n) = T(n/2) + T($\sqrt{n}$) + n

= T(n/4) + T($\sqrt{n/2}$) + T($\sqrt{n}$/2) + T($\sqrt{\sqrt{n}}$) + n/2 + $\sqrt{n}$ \+ n

But I can't seem to find any discernable patterns here, and I'm not sure if I'm supposed to continue expanding?

I also tried substituting n = 2k, and then using S(k) = T(2k) as I've seen in T(n) = T($\sqrt{n}$) problems, but this leads to:

T(2k) = T(2k/2) + T(2k/2) + 2k

S(k) = ???

I'm quite lost as to how to continue from here! Appreciate the help as I'm quite new to this!!

# Answer
> 1 votes
Try to prove that $T(n) \leqslant 3An$ for a certain constant $A$.

If you want to be rigorous, I think that $A = \max\\{1,\max\limits\_{1\leqslant n \leqslant 36}\left\\{\frac{T(n)}{3n}\right\\}\\}$ should suffice, but that may not help you to understand the upper bound.

# Answer
> 1 votes
The related recurrence $S(n) = S(n/2) + n$ has the solution $S(n) \approx 2n$ (depending on the initial conditions and on the interpretation of $n/2$), and this suggests considering $R(n) = T(n) - 2n$, which satisfies the recurrence $$ R(n) = T(n) - 2n = T(n/2) + T(\sqrt{n}) - n = R(n/2) + R(\sqrt{n}) + 2\sqrt{n}. $$ The master theorem (which doesn't quite apply here!) suggests that $R(n) = \tilde{O}(\sqrt{n})$, and so that $T(n) = 2n + \tilde{O}(\sqrt{n})$, where $\tilde{O}$ is hiding logarithmic factors.

Informally, since $T(n)$ is of order $n$, we expect $T(\sqrt{n})$ to be of order $\sqrt{n}$, and so to have little effect on the asymptotics. This can be proved formally by considering the recurrence $R(n)$ above.

---
Tags: complexity-theory, algorithm-analysis, recurrence-relation
---


title: Shortest path with exactly $k$ edges

text:
# Question
Title: Shortest path with exactly $k$ edges
From Skiena's book The Algorithm Design Manual, chapter 6, problem 22:

Let $G = (V,E,w)$ be a directed weighted graph such that all the weights are positive. Let $v$ and $u$ be two vertices in $G$ and $k \leq |V|$ be an integer. Design an algorithm to find the shortest path from $v$ to $u$ that contains exactly $k$ edges. Note that the path need not be simple, and is permitted to visit vertices and edges multiple times.

This is **not homework**, its me preparing for an interview. I have no clue how to approach this.

# Answer
> 13 votes
Since you allow non-simple paths(i.e. walks), seems like a dynamic programming algorithm will work.

For each $1 \le m \le k$, and every vertex $u$, we compute $D\[m,u\]$ where $D\[m,u\]$ is the weight of the shortest walk of length exactly $m$ starting at $v$ and ending at $u$. We are looking for $D\[k,w\]$.

This can be computed as

$$D\[m+1, u\] = \min\_{x \in Pred(u)}\\{D\[m,x\] + w\[x,u\]\\}$$

Where $Pred(u)$ (predecessor) is the set of vertices which have an outgoing edge to $u$ and $w\[x,u\]$ is the weight of edge $x\to u$. You start with $D\[1,u\] = w(v,u)$ (allowing $\infty$).

You can add auxiliary structures to find the actual walk.

Running time: $O(k |E|)$.

This is because for each number of required edges from 1 to k, we go through the indegree of each vertex and in total, we visit all $|E|$ edges. We visit all $|E|$ for each number of the required edges ($k$) so the final run time is $O(k |E|)$ .

btw, if we wanted only simple paths, then this is probably $NP$-Hard, as we can set $k=n$ and reduce some variant of Hamiltonian Path problem to it.

# Answer
> 0 votes
Non-DP solution so it's less efficient but a bit more general: we will find shortest path using $k$ edges from $v$ to any other $u\ne v$ in $V$.

We'll make more copies of the graph so we'll have $G\_0, G\_1,..., G\_k$ in total. Each original edge $e=(u,v)$ will be connecting $u\in G\_i$ to $v \in G\_i+\_1$ for all $0\leq i\leq k-1$. Denote $u\_i$ the copy of node $u$ in $G\_i$.

Run **Dijkstra** algorithm from vertex $v\_o$ (all non-negative weights) and get $\delta (v\_0,u)$ the shortest path from $v\_0$ to each $u$ in this "master graph", in particular to each $u\_k \in G\_k$. You can get now your desired shortest path.

Note that each path from $v\_0$ to some $u\_k$ contains exactly k edges. Complexity is $O(k\cdot(|V|+|E|))$ for constructing the graph. Since there are now $k|V|$ vertices and $k|E|$ edges Dijkstra's run time is $O(k\cdot (|E|+|V|log|V|))$ using Fibonacci heap.

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


# Question
Title: In the Recursion Theorem, does obtaining a description of SELF increase the length of the program?
In the following video, he mentions that x \<- \<SELF\> (x obtaining a description of itself) is a "legal" operation for a Turing Machine to make. https://youtu.be/5yO\_l2w0wIA?t=93

My question is, what is the description length of x with and without that 'line' of code? Does obtaining the description of x double the length of the description of x, because it's basically 'baked in' to x, or does x 'compute' its own description without needing to have it written down anywhere else?

# Answer
The following is a CPP code for a program that prints its own code:

```
#include <iostream>

using namespace std;

int main()
{

    for(int i=0; i<2; i++){
        cout << "#include <iostream> \n using namespace std; \n int main(){ \n  for(int i=0; i<2; i++){ \n cout << WOW! it is printing its own code! << endl; \n } \n return 0; \n } \n\n\n" << endl;
    }
    return 0;
}

```

And you may find some challenges about the SELF programs like this with some solutions. If you are interested in its theory aspect you may read Lemma 6.1 in Introduction to the theory of computation. So, if I want to answer your title question, yes I believe the program that has the ability to obtain its source code may have a longer code.
> 0 votes

---
Tags: turing-machines, computability
---


# Question
Title: Algorithm to find for each vertex, a vetrex that it can reach with the lowest cost in a graph
We have a **directed** graph $G=(V,E)$ and each vertex $v\in V$ has a cost: $price(v)$. Our mission is to find an algorithm that runs in time **$\mathcal{O}(|E|+|V|)$** that finds $\forall v\in V$ the minimal price of all vertices $w$ which are reachable from $v$ (all vertives $w$ s.t. there is a path from $v$ to $w$). Note that $v$ can reach itself.

As an example if the graph simply was $3\to 5 \to 1$ then the minimal price of all vertices was $1$, since all vertices can reach $1$ and its minimal.

I tried using a BFS-like algorithm but failed.

# Answer
Consider a strongly connected component $C$ of $G$ and notice that the sought value associated with all vertices $v$ in $C$ is the same. Let's call this value $P(C)$.

Compute all strongly connected components of $G$ (there are several ways to do this in time $O(|V|+|E|)$, see for example Tarjan's algorithm) and let these be $C\_1, \dots, C\_k$.

Now consider a directed graph $G'=(V', E')$ whose vertex set is $V' = \\{ C\_1, \dots, C\_k\\}$ and such that there is a directed edge $(C\_i, C\_j)$ in $E'$ if and only if $i \neq j$ and $(u,v) \in E$ for some vertex $u$ in $C\_i$ and some vertex $v \in C\_j$. Notice that $G'$ is a directed acyclic graph, and therefore admits a topological ordering.

Compute such an ordering and assume w.l.o.g. that it is $\langle C\_1, \dots, C\_k \rangle$ (otherwise we can just rename the components). This can be done in time $O(|V'|+|E'|) = O(|V|+|E|)$ (actually, Tarjan's algorithm already returns the strongly connected components in reverse topological order).

Notice that if some $C\_i$ is a sink in $G'$ (i.e., it has no outgoing edges) then $P(C\_i)$ can be immediately computed as $\min\_{w \in {C\_i}} \text{price}(w)$

If $C\_i$ is not a sink, then we have: $$ P(C\_i) = \min \big\\{ \min\_{w \in C\_i} \text{price}(w), \min\_{(C\_i, C\_j) \in E'} P(C\_j) \big\\}. $$

By examining the vertices of $G'$ in reverse topological order, we are able to compute all values $P(\cdot)$. Moreover, notice that the time needed to compute $P(C\_i)$ is proportional to the number $|C\_i|$ of vertices in $C\_i$, plus the out-degree $\delta\_i$ of $C\_i$ in $G'$. Therefore, the overall time complexity of computing $P(\cdot)$ once the topological order is known is upper bounded (up to multiplicative constants) by: $$ \sum\_{i=1}^k ( |C\_i| + \delta\_i ) = \sum\_{i=1}^k |C\_i| + \sum\_{i=1}^k \delta\_i = |V| + |E'| \le |V| + |E|. $$
> 0 votes

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


# Question
Title: For every language $L_1$, there exists a language $L_2$ such that $L_2$ is not mapping reducible to $L_1$
I've tried approaching this problem by contradiction, but that did not lead anywhere. Now I am attempting a proof by construction.

i.e. given a language $L\_1$, construct a language $L\_2$ that cannot be mapping reduced to $L\_1$.

# Answer
> 1 votes
Note that the set of all words is countable, and so is the set of all computable functions.

Suppose $\Sigma^\* = \\{x\_1, x\_2, …\\}$ is the set of all words and $\mathcal{F} = \\{f\_1, f\_2, …\\}$ is the set of all computable functions.

For $L\_1\subset \Sigma^\*$, define $L\_2 = \\{x\_i\in\Sigma^\* \mid f\_i(x\_i)\notin L\_1\\}$. Then $L\_2$ is not reducible to $L\_1$.

---
Tags: formal-languages, turing-machines, computability
---


# Question
Title: If greater than or equal to zero then binary variable equals 1: integer linear program
I have a variable $d\_{i} \in \mathbb{Z}$ with an upper and lower bound. I also have a binary variable $v\_{i}$ which I want to $=1$ if $d\_{i} \geq 0$; else $v\_{i} = 0$. How do I enforce this as a *linear* constraint?

I have seen this post but it is different to my problem as I have the inequality ($\geq$) whereas they merely have ($\>$). I presume this changes the problem but please correct me if I am wrong as I am new to this.

I thought about adding a slack variable so that my constraint becomes like that in the post referenced; however, my problem is one of maximization and I do not want to include $-d\_{i}$ in my maximization objective as it does not make sense for my problem.

Any help is much appreciated!

# Answer
Assuming that $L \le d\_i \< U$ with $L\<0$ and $U\>0$, you can add the following two constraints.

The following encodes "if $d\_i \ge 0$ then $v\_i=1$": $$U v\_i - d\_i \> 0.$$

The following encodes "if $d\_i \< 0$ then $v\_i=0$": $$ -L (1-v\_i) + d\_i \ge 0. $$
> 1 votes

---
Tags: linear-programming, integer-programming, mathematical-programming, constraint-satisfaction, constraint-programming
---


# Question
Title: Which algorithm is most suitable for comparing two images to find differences?
I have two images of two objects that are suppose to be exactly the same. I use one for reference and one as my model. I want to find an algorithm that will help me find on which areas these images vary? and return a binary map (the size of the image), that indicates of the variation. Its an easy task when we don't take into acount noise and small shifts, but in real life it does not work like that.

What is considered state of the art to tackle that problem in a way that would fit such factors? Thanks!

# Answer
On top of other suggestions, feature registration may be appropriate if the images are difficult to register. Detect features using an algorithm like SIFT, and then use RANSAC to find correspondences between the images.
> 1 votes

# Answer
You'll have to experiment with methods. The exact approach is likely to depend on the specifics of exactly what kinds of variations occur and you want to ignore. Start with https://en.wikipedia.org/wiki/Image\_registration and https://en.wikipedia.org/wiki/Image\_differencing and SSIM and MSE, and get some experience with in what ways they do or don't need your needs, and that will help you formulate a more precise question.
> 0 votes

---
Tags: computer-vision, image-processing, digital-image-processing
---


# Question
Title: Proving the grammar S → SS+ | SS∗ | a is unambiguous
Consider the context-free grammar G = ({a, +, ∗}, {S}, {S → SS+ | SS∗ | a}, {S}) and consider the string aa+a\* generated by this grammar.

Is this grammar unambiguous?

I have browsed the Internet and I have found that there is no standard procedure for proving if a grammar is unambiguous or not. But sometimes induction on length of the string or maybe length of the derivations works. I think in this question I can do something via length of sentential forms but I am not sure if its rigorous or not.

My approach: induction on length of sentential forms

Base case: length=1 then it has to be S -\> a hence unambiguous.
Induction step: for length \<= n assume all sentential forms are unambiguous. Consider a sentential form ww'. So here w can be either S or a. If a then done since unique derivation else if S then only possibility is that there has to be SS+ or SS\* hence we know S produces these unambiguously and the rest is unambiguous by hypothesis hence proved.

This seems more of a cyclic argument to me so I would be glad if someone could help me out.

By the way, what is the language generated by a grammar?

In this case, I think that it's the language that does postfix operation on addition and multiplication that is being described here. But how do we generalise for grammars?

# Answer
> 0 votes
### $L(G)$ is the set of all p-expressions

Let an operator mean either $+$ or $\*$. In order to characterize the strings generated by $G$, we may observe the number of operators and the number of $a$'s in a string.

Call a string $w$ over alphabet $\\{a, +, \*\\}$ a p-expression if

* $w$ is non-empty, and
* there are at least as many operators as $a$'s in each proper suffix of $w$ while there are one less operators than $a$'s in $w$. (In particular, $w$ ends with an operator and starts with two $a$'s unless $w=a$.)

**Claim**: $L(G)$ is the set of all p-expressions.
**Proof**: Use structural induction. This is an easy exercise for the readers.

### $G$ is unambiguous

**Proof**: Let us show that $w\in L(G)$ has a unique parse tree using induction on $|w|$.

* Base case, $|w|=1$. Then $w$ must be $a$. $S\to a$ is the only derivation for $w$.
* As induction hypothesis, assume the proposition is true for $|w|\le n$.
Let $|w|=n+1$. WLOG, suppose $w$ ends with $+$. So the first step in the derivation for $w$ must be $$S\to SS+.$$
Let $w\_1$ be the string produce by the first $S$ on the right hand side and $w\_2$ be the string produced by the second $S$ so that $w=w\_1w\_2+$. Note that $w\_1, w\_2\in L(G)$.
Scanning $w\_1w\_2+$ from right to left character by character, let us track the difference of the number of operators and the number of $a$'s scanned. The claim above implies the last scanned character of $w\_2$ must be the character at which that difference have dropped to 0 for the first time.
So $w\_2$ is determined uniquely by $w$. Hence $w\_1$ is also determined uniquely by $w$.
By induction hypothesis, there is a unique parse tree for $w\_1$ and for $w\_2$. Hence, there is a unique parse tree for $w$. $\quad\checkmark$

### Inspect $G$ reversed

Here is another way to show $G$ is unambiguous, which may appear simpler for readers with more experience.

Let $G^r$ be $G$ with production rules reversed, i.e., $$G^r=(\\{a,+, \*\\}, \\{S\\}, \\{S\to +SS, S\to \*SS, s\to a\\}, \\{S\\}).$$ It is easy to see that $G$ is unambiguous iff $G^r$ is unambiguous.

With some simple routine computation, we can obtain the $LL(1)$ parsing-table of $G^r$, $$\begin{array} {|c|c|c|c|}\hline &{\\\\$} &+ & * & a \\\hline S & &S\to +SS &S\to \*SS & S\to a \\\hline \end{array}$$ As an $LL(1)$ grammar, $G^r$ is unambiguous. Hence, $G$ is ambiguous as well.

More generally, we can prove that a context-free grammar is unambiguous if all production rules end with different terminals.

### An exercise

Prove $(\\{0, 1,+, \*\\},$ $\\{S, B\\},$ $\\{S\to SS+,$ $S\to SS\*,$ $S\to B,$ $B\to 0B,$ $B\to 1B,$ $B\to 0,$ $B\to 1\\},$ $\\{S\\})$ is an unambiguous grammar.

# Answer
> 1 votes
I would like to suggest another easy method to prove that the grammar $G$ is unambiguous. We can use the LR(0) parsing property to do so.

The language $L(G)$ is not prefix-free. If we add the endmarker $\\\\$$ to the language, thus introducing a new initial nonterminal $S'$ and the rule $S'$ $\rightarrow$ $S$ $\\\\$$ then the prefix property is satisfied. If the resulting grammar $G'$ is LR(0) then the initial grammar is necessarily unambiguous, otherwise we would get a parsing conflict for some word in $L(G')$. The LR(0)-property of $G'$ can be easily proven by constructing the corresponding finite state automaton.

Btw, this method does not provide a criterion of unambiguety, it gives only a sufficient condition. There are some unambiguous grammars that generate non-deterministic CFLs (the most famous example is the grammar generating even palindromes).

---
Tags: context-free, parsers, ambiguity
---


# Question
Title: How does the `Word` type work in Kind Lang?
The Word type (in kind lang) looks like this:

```
type Word ~ (size: Nat) {
  e                              ~ (size = Nat.zero),
  o<size: Nat>(pred: Word(size)) ~ (size = Nat.succ(size)),
  i<size: Nat>(pred: Word(size)) ~ (size = Nat.succ(size)),
}

```

The syntax is defined here.

All it says is:

> ```
> type Name (A: Par0, B: Par1 ...) ~ (i: Idx0, j: Idx1 ...) {
>   ctor0(field0: Fld0, field1: Fld1 ...) ~ (i = id0, j = idx1 ...)
>   ctor1(field0: Fld0, field1: Fld1 ...) ~ (i = id0, j = idx1 ...)
>   ...
> }
>
> ```
>
> Declares an inductive algebraic datatype. A simple datatype starts with the type keyword, followed by its name, followed by any number of parameters ("static polymorphic types"). Inside {} follows any number of constructors, each one is followed by its fields.
>
> As an example, the following type, in Haskell:
>
> ```
> data List a = Nil | Cons a (List a)
>
> ```
>
> Can be written in Kind as:
>
> ```
> type List (A: Type) {
>   nil
>   cons(head: A, tail: List(A))
> }
>
> ```
>
> ... Where ~ (it's optional) stands for any number of indices ("dynamic polymorphic types"). In the constructor, its fields are also optionally followed by ~ and its concrete indices.

The `Word` type is used all over, mainly like this:

```
type U8 {
  new(value: Word(8))
}

```

That makes sense to me, we have a type record with a value field which is type `Word(8)`. But how does the `Word` type itself work? I don't follow. Take one constructor line, like this:

```
o<size: Nat>(pred: Word(size)) ~ (size = Nat.succ(size))

```

What does that mean? Passing the `pred: Word(size)` seems like an infinite loop.

Another type with similar definition is `Bits`:

```
type Bits {
  e,
  o(pred: Bits),
  i(pred: Bits),
}

```

Maybe it has to do with self types?

# Answer
> 4 votes
I remembered this question seeing you issues in the Kind repo. The best way to understand the `Word` type is to understand the problem it solves. In our case we had the problem of defining a type for bytes, 32-bit integers, 64-bit integers etc. The first idea is to define it like this

```
type Byte {
  new(
    b0: Bool, b1: Bool, b2: Bool, b3: Bool, b4: Bool, b5: Bool, b6: Bool, b7: Bool
  )
}

```

this is correct, but writing algorithms using this type would be a pain. If we tried this with 32-bit integers it would cease to be a pain and become completely impractical. It's tempting to use

```
type Bits {
  e
  i(pred: Bits)
  o(pred: Bits)
}

```

because the algorithms would be much shorter. But this isn't correct since this type includes bit sequences of any length. However you could do something like this

```
type Bits0 {
  e
}
type Bits1 {
  i(pred: Bits0)
  o(pred: Bits0)
}
type Bits2 {
  i(pred: Bits1)
  o(pred: Bits1)
}

```

and so on. Of course this would make the algorithms terrible again, but what if instead of writing all these types we could write a function `Word :: (n: Nat) -> Type` that would serve that purpose? With Kind you can do that! And in two different ways. The simplest, easiest to understand and in hindsight what we should've done looks like this

```
type WordTip {
  e
}

type WordBit (n: Nat) {
  i(pred: Word(n))
  o(pred: Word(n))
}

Word(n: Nat): Type
  case n {
    zero:
      WordTip
    succ:
      WordBit(n.pred)
  }

```

The actual `Word` definition uses indexes to build the type as Labbekak explained. The difference between the two approaches is that our function uses the length to determine the constructors of the type. Indexed types go the other way around and use the constructors and parameters to determine the index of the constructed value. Indexes are more flexible. Functions that return types are generally easier to use. To give an example of what kinds of information we can keep track of using indexes. Consider this type

```
type NatList ~ (odds: Nat) {
  nil ~ (odds = 0)
  cons(tail_odds: Nat, head: Nat, tail: NatList(tail_odds)) ~ (odds = Nat.add(Nat.mod(head, 2), tail_odds))
}

```

It keeps track of the amount of odd numbers in a list of natural numbers. The `(odds = Nat.add(Nat.mod(head, 2), tail_odds))` tells us what the index of the resulting will be after we call the constructor. So

```
NatList.cons(0, 5, NatList.nil)
  :: NatList(Nat.add(Nat.mod(5, 2), 0))
NatList.cons(0, 5, NatList.nil)
  :: NatList(1)

```

and

```
NatList.cons(0, 4, NatList.nil)
  :: NatList(Nat.add(Nat.mod(4, 2), 0))
NatList.cons(0, 4, NatList.nil)
  :: NatList(0)

```

Also note that we could use the same name for a parameter of the constructor and for the index. Like this

```
type NatList ~ (odds: Nat) {
  nil ~ (odds = 0)
  cons(odds: Nat, head: Nat, tail: NatList(odds)) ~ (odds = Nat.add(Nat.mod(head, 2), odds))
}

```

but that's confusing.

# Answer
> 3 votes
Giving the datatype in Agda-style syntax:

```
data Word : Nat -> Set where
  e : Word zero
  o : {size : Nat} -> Word size -> Word (suc size)
  i : {size : Nat} -> Word size -> Word (suc size)

```

So `e` is an empty bitstring (word), it contains `zero` bits! `o` adds a `0` to the bitstring and `i` adds a `1` to the bitstring. Both of these constructors add 1 bit to the bitstring so the "size" increases with 1 (using the `suc` constructor of `Nat`).

This is an indexed datatype (also known as an inductive family or a Generalized Algebraic Datatype). In this case the datatype is indexed by a `Nat`. You can see that each constructor may give a different value for the `Nat`. This allows you to gain knowledge about the instance of the datatype by looking at the index (or by pattern matching). For example you know that a `w : Word zero` must be an `e`, because none of the other constructors allow a `zero` for the index!

---
Tags: type-theory
---


# Question
Title: Using Flow graph to find maximum matching
I recently submitted an answer to the following question (homework in algorithms course):

A guy has m shirts, n pants, and p belts. he wants to make the maximum amount of outfits while abiding by these rules:

1. Every item can appear at most in one outfit
2. Not every pant can go with the same shirt (we have n X m boolean matrix representing legal combinations)
3. Not every pant can go with every belt (again we have n X p boolean matrix)

my attempt:

create a bipartite graph where V1 ={ v | v is a pair of shirt and a belt} V2= {v | v is a pant}.
we draw an edge between a vertex v from V1 and vertex u from V2 only if the three make a legal combination.

after constructing the graph we create a source connected to all the vertexes of V1 and a sink connected to all the vertexes of V2 and use Ford-Fulkerson algorithm to find the maximum flow which yields the maximum matching of the graph.

My T.A said this was wrong since it won't give me the correct answer, but didn't explain why. Is he right? if he is, where is the fallacy of my solution? (I'm not looking for a better solution, I have seen a better one already, just want to know if this particular one is correct)

# Answer
> 0 votes
Your TA is correct. Your algorithm is wrong.

Here is a simple counterexample for your algorithm. We have two shirts, two pants and one belt. All combinations are legal.

The bipartite graph has 2 nodes representing two shirt-belt pairs and 2 nodes represent two pants. There is an edge between any shirt-belt pair and any pant.

The maximum-matching of the bipartite graph consists of two matches. However, since there is only one belt, we can make at most one outfit.

---
Tags: algorithms, graphs, network-flow, bipartite-matching
---


# Question
Title: Genetic algorithms applied to topological orderings of a DAG
I need to solve an optimization problem, whose search space is all possible topological orderings of a DAG. There is a cost function associated with each ordering, which has no simple mathematical representation -- I have a black box which, given one of the orderings, will return the cost associated with that ordering.

I'd like to apply e.g. genetic algorithms to solve the problem. In order to do that, I understand I need to find some kind of representation (e.g. a vector in a certain $n$-dimensional space) to which I can apply mutations and breeding with other candidates, outputting a new ordering whose cost I can then compute using the black box.

I learned that this can be done with generic permutations, as in this example for the traveling salesman problem. However, not every permutation will be a valid topological ordering. In principle, I could follow the procedure to generate an arbitrary permutation, and then discard and repeat in case it's not a valid topological ordering. However, I'm afraid that, depending on the structure of the DAG, I may have to test a very large number of orderings before a valid one is found.

Thus, I'm looking for a procedure to perturb a topological ordering, and to combine two topological orderings, such that the result is guaranteed to be another topological ordering.

# Answer
> 2 votes
Another way of performing the combination operation is this:

* Randomly interleave both linear orderings (obtaining a tuple containing each node twice)
* Discard the second occurrence of each node

The result will be another topological ordering since

* It contains each node once
* If a\<b in the DAG, then a will precede b in each original ordering, and whatever interleaving you use will have its first a before its first b.

# Answer
> 7 votes
There is no one correct answer. You may have to try different possibilities and see how well they work.

One candidate mutation operation is the following: pick a random pair of adjacent nodes (i.e., adjacent in the ordering), swap them, and check if the result is still a valid topological ordering. If not, try again.

Usually with genetic programming we want to do local search, i.e., we want each mutation to make a small change to the ordering -- not replace it with something entirely different.

---

Here is another approach you could try. Imagine labelling each node with a number. Now, this labelling induces an ordering: run a topological sort algorithm on the graph, but whenever the algorithm has multiple chioces for what to do next, break ties based on the labelling. For instance, use Kahn's algorithm, but replace "remove a node n from S" with "remove the node n from S with the smallest label". Now you can use your genetic algorithm to try to optimize the labelling, and you can apply mutation and breeding to the labelling, not to the ordering. Because the labelling does not have any complicated constraints, you can easily use simple mutation and breeding operators (e.g., a mutation is "change a single label", breeding is the standard crossover).

# Answer
> 2 votes
I am not sure if this will be good enough for the performance of your problem, but here are some things I could think of.

## Combination

Find the shortest prefix of the two topological sequences which are permutations of each other and choose randomly between the two. Continue greedily from this point and so on. It might happen that this often results in very long substrings being selected. If that is the case, any substring which gives the permutation of the same elements in the two sequences can be swapped. Given that there are O(n^2) subsequences, it may be too expensive to do this but a compromise might be possible.

## Mutation

Take a random element and find out how far it can be "bubbled" backward or forward without destroying the topological ordering. And select a random position out of those to place the element. It might even be enough to choose randomly among allowed swaps of adjacent elements. Now this might make certain graphs more probable than others (not sure), but I think it should be enough of a mutation for a genetic algorithm.

---
Tags: graphs, optimization, genetic-algorithms, topological-ordering
---


# Question
Title: How to design a simpler Version of CARDIAC (Cardboard Illustrative Aid to Computers)?
I'm trying to make a simpler version of CARDIAC for only performing addition. Now, I am encountering several problems in making something similar and looking for some ideas (I'm new to Computer Architecture).

Here's an excerpt of what CARDIAC is (Wikipedia):

> CARDIAC (CARDboard Illustrative Aid to Computation) was a learning aid developed by David Hagelbarger and Saul Fingerman for Bell Telephone Laboratories in 1968 to teach high school students how computers work. The kit consisted of an instruction manual and a die-cut cardboard "computer". The computer "operated" by means of pencil and sliding cards. Any arithmetic was done in the head of the person operating the computer. The computer operated in base 10 and had 100 memory cells which could hold signed numbers from 0 to ±999. It had an instruction set of 10 instructions which allowed CARDIAC to add, subtract, test, shift, input, output and jump.

Basically it's a simple illustration of how a computer works internally to do basic stuff(as explained in the excerpt). I'm only trying to do addition but I am trying to find a way to show what the output is. Here's how I thought it would be: I would use a 16-bit register with binary base and 10 memory cells. I guess this should be more than enough for a basic addition illustration.

Now my problem is, I'm not very sure how to output the values. Let's say for example, I input 10(binary for 2) in register R1 and 1(binary for 1) in register R2. Now this goes to the ALU, which calculates the addition immediately and places it in register R3. This would be represented using arrows and sliding cards(values for R1, R3 and R3) in specific slots on the illustration.

My problem is, now that I have the value in R3, how do I output it using that cardboard illustration? Also, does the ALU work as logic gates to calculate the sum?

# Answer
The wikipedia page you referenced has a link to a much more in-depth instructions on how to use CARDIAC. https://www.cs.drexel.edu/~bls96/museum/cardiac.html There is also a CARDIAC simulator here: https://www.cs.drexel.edu/~bls96/museum/cardsim.html

The answer to your first question

> My problem is, now that I have the value in R3, how do I output it using that cardboard illustration?

is in the table of instructions. The `OUT` instruction (the instruction with opcode `5`) writes the value from a memory location to the output card.
> 1 votes

# Answer
You want to make a binary adder. You can make one out of boolean logic gates. Your register will be based on your binary adder. It is not a more simple computer than the CARDIAC computer, because the CARDIAC works with base ten and the beginner does the arithmetic by hand. Boolean logic is taught much later in school than addition in base ten.
> -1 votes

---
Tags: computer-architecture, arithmetic, cpu
---


# Question
Title: Isn't de-duplication faster, if you stop search as soon as some threshold of duplicates is found, delete duplicates, and restart search?
Let $d\_j \in \mathbb{Z}\_{\ge 0} =$ jth duplicate unearthed by a freeware de-duplicator (like AllDup1).
$t\_j \>0 =$ time taken to unearth the jth duplicate.
$f \in \mathbb{N} =$ total number of files being searched.
$f\_j =$ number of files already searched by de-duplicator at $t\_j$. Plainly, $\uplus\_j \\; f\_j = f$.

### My questions

1. At some $t\_j$ for some *j*, isn't it faster if you stop the search in AllDup, delete all $f\_1, \dots, f\_j$, then restart the search on AllDup?

Then you save electricity and time! Why? AllDup doesn't need to pair up all the $d\_j$ with the other files. In other words, you spare AllDup from analyzing $d\_j \times (f - f\_j)$?

2. As a corollary, can it be swifter to de-duplicate each subset of $f$ separately first? Rather than de-duplicating the whole of $f$?
3. As a corollary, can it be quicker to search for all duplicate pictures, then duplicate video files, duplicate audio files — before searching for all duplicate files regardless of file type?

1 NON-AFFILIATION DISCLAIMER — I have no affiliation or financial, commercial or ownership interest.

# Answer
> 2 votes
I think you're imagining that deduplicators compare every file to every previously scanned file. That would be too slow to be usable. They actually maintain a cache of known properties of already-scanned files, and use it to decide which comparisons are needed.

For example, they might do something like this:

* Scan all files and assign them to bins by size. Discard bins that contain only one file at the end of the scan.
* Group the files of each remaining bin into sub-bins based on a checksum of the first 4K of the file, then discard sub-bins that have only one file.
* Group into sub-sub-bins based on a checksum of the rest of the file (if any), then discard sub-sub-bins that have only one file.
* Group into sub-sub-sub-bins based on the actual file contents. Any groups with more than one file are duplicates.

In the last step, if there are $n$ files $d\_1,\ldots,d\_n$ in the ss-bin, and all are duplicates, then first $d\_1$ will be placed in a sss-bin by itself, then $d\_2$ will be compared to it and added to the same bin, then $d\_3$ will be compared with some representative of the bin, i.e., with $d\_1$ *or* $d\_2$, etc. In total only $n-1$ pairwise comparisons happen. If the files are all different then $n(n{-}1)/2$ comparisons are needed, but that case happens very rarely if the checksum is any good.

The last step may not even be necessary if the checksum is good enough. The chance of two different files having the same BLAKE2b-256 checksum is so small that it's senseless to worry about it (a false positive is much more likely to be due to a cosmic ray), and storing 256-bit checksums of 1 million files takes only 32 MB.

---
Tags: algorithms
---


# Question
Title: Is the following language with a finite bound Turing Recognizable?
Consider the language $A = \\{\langle M\rangle : M$ is a Turing Machine and $| L(M) | = 9\\}$. That is, $M$ accepts the language of a set of exactly 9 strings. I want to determine if this language is Turing Recognizable or co-Turing Recognizable or neither.

I think it might be Turing Recognizable considering the construction of the following Turing Machine Below:

1. On a tape insert each of the accepted strings of $L(M)$ in each cell mod 10. So the concatenation of every cell 1,2,3,...,9 mod 10 would be one of the strings in $L(M)$
2. Then on any input string $w$, compare each character of $w$ one-by-one based on all the characters in the tape cells so far and write $w$ in the 0 mod 10 cells of the tape
3. Accept if $w$ matches any of the strings in cells 1,2,3,...,9 mod 10 or reject otherwise

I believe this construction of the Turing Machine above is correct and also is the synthesis of a 10-tape Turing machine. I'm just not sure if this is the correct approach for this question. Can someone please provide me with some feedback if this approach is correct?

I would also like to identify if $B = \\{\langle M\rangle : M$ is a Turing Machine and $| L(M)| \geq 9\\}$ is Turing Recognizable or co-Turing Recognizable but haven't identified a solid argument as yet since I'm not 100% confident in my argument above.

# Answer
> 1 votes
The problem with $A$ is that you don't know in advance which $9$ strings to check. There are infinitely many words.

Moreover, intuitively (and *only intuitively, this is not a formal argument*), if you start checking whether a given machine $M$ accepts strings, even if you try all of them in parallel (in increasing number of steps), you can never know if you'll reach 9, and if you reached 9, you still won't know if you'll reach more.

Thus, the intuition is that $A$ is not going to be neither recognizable nor co-recognizable.

Now, to prove this you'll need to come up with appropriate reductions. A good approach is to try reductions from $A\_{TM}$ and $A\_{\overline{TM}}$. Try it and let us know if you get stuck.

As for $B$, the reasoning is a bit similar, but here if you ever reach $9$ words that are accepted, you're done. So there is a way to recognize the language (but it's still not co-recognizable).

---
Tags: turing-machines
---


# Question
Title: Polynomial algorithm for the «Input Series» Problem
Can you help me design an algorithm to solve the following problem in **polynomial** time?

Let n be a given natural number. We define an **input series** of length n to be a string of length n which is built by using only the characters F, S and - (hyphen).

At least one F or S is guaranteed to appear in each valid input series.

```
e.g. For n = 7:

FF---SF is valid

-F-S-FS is valid

SSSFFSS is valid

------- is not valid (only -)

FS-F    is not valid (length)

ABCD--- is not valid (characters)

```

Any valid input series can be **developed** by enumerating *all* the input series of same length, n, such that each "-" (hyphen) of the initial input string changes into either F or S.

```
e.g. For n = 5,
"FS--F" is developed into:
FSFFF
FSFSF
FSSFF
FSSSF

```

Each of the above series obtained, through developing the initial serie, will be called a **result serie**.

Question: given two natural non-zero numbers (n and k) and k valid input series of length n, **how many duplicate** result series can be found **in total**?

```
e.g.

Input:
k=2, n=4 and the series:
FS-F
FSF-

Output:
1

```

Explanation: The first serie develops into FSFF and FSSF.

The second serie develops into FSFF and FSFS.

Since FSFF is repeated, the output answer to this exact problem instance will be 1 (since there is only 1 duplicate to an already existing result series).

Point I thought one might consider when designing the poly algorithm:

* the problem asks for the *number* of duplicate result series and not for their actual content or value

Do you have any strategy that could determine the duplicate number avoid some weird brute force approach?

Thank you for your help!

# Answer
When $k = 2$, we can proceed as follows.

If the two given inputs disagree on one of the positions (one of them contains F and the other contains S), then there will be no intersection.

Otherwise, the answer is $2^m$, where $m$ is the number of positions in which both inputs have $-$.
> 0 votes

# Answer
No polynomial-time algorithm is possible unless $P = \sharp P$.

I reduce the $\sharp P$-complete problem of counting the number of variable assignments satisfying a DNF formula.

Let $n$ be the number of variables. For a conjunctive clause, compute a pattern of length $n$. The $i$'th character of the pattern is "F" if the clause contains variable $i$ as a positive literal, "S" if for a negative literal, "-" otherwise.

A string is associated with a variable assignment. Set true for "F", false for "S". A pattern computed from a conjunctive clause develops to a string if and only the variable assignment satisfies the clause.

In addition to the computed patterns for the set of conjunctive clauses, a "-"-only pattern of length $n$ is added.

The "-"-only pattern develops every string. Thus, a string is a duplicate if and only if the corresponding variable assignment satisfies the DNF formula.
> 0 votes

---
Tags: algorithms, algorithm-analysis, strings, substrings
---


# Question
Title: is it a common practice to refer to a complexity of O(mn) as O(n^2) with no known relation between m and n?
I had a computer science test in school and we were asked to give the complexity of a code we had to write. the complexity was undoubtedly O(mn) where m,n were unrelated to each other. I got deducted some points as I should've assumed m=n and therefore the complexity is O(n^2). I was later told we were taught to do so and I guess that regardless of whether I'm right or not I'm in the wrong here (I learned some computer science long ago so I was paying too much attention in class). but is there any reason such assumption should be done apart from making it easier for high school pupils?

# Answer
> 1 votes
If there is no relation between $n$ and $m$, then $O(mn)\neq O(n^2)$.

To illustrate this, think for example what would have happened if we assumed someone would have put an input with some $n$ and $m=2^n$. In this case, the complexity could be thought of as $O(2^n\cdot n)$. Is that equal to $O(n^2)$? **No!**

What about if we assume someone always inputs an $m=5$? Then the complexity is $O(5n)=O(n)$, which is smaller than $O(n^2)$.

As we can see from the examples, since there is no known relation between the two variables, one cannot convert this $O(mn)$ to any other form containing only one variable.

# Answer
> -2 votes
An upper bound $O$ notation is used to describe an upper bound for the function growth, i.e. the growth will never be greater than what $O$ says. So in your case $O(mn)$ think about how you can maximize the term $mn$ such that any combination of $m$ and $n$ can never be greater than the maximized function. For this particular case you can think of it as maximizing the area of a square with sides $m$ and $n$. You would get the maximum area when $m=n$ and hence $O(n^2)$ is a more appropriate upper bound(with $n$ being $max(m,n)$).

---
Tags: time-complexity
---


# Question
Title: Why do non Context Free languages need more stacks?
In an example question sheet for my exams our professor included “Know to explain why for non CF languages 1 stack is not enough.”

We haven’t delved into CS and reclusively enumerable languages much and I can’t find the answer to this in my book either. I understand how PDAs work for CF languages though and I have a few info on LBAs, but I still don’t grasp why non CF need more than one stack.

# Answer
As you probably know a language like $\\{a^nb^n|n\in \mathbb{N}\\}$ is context-free since we can first save the number of all $a$ we read using some symbols (for example A) in the stack and then check that the $b$'s number ( denote it by $n\_b$) is equal to $a$'s number or not, by removing all $A$ symbols.

Now, try to look at what makes a language like $\\{a^nb^nc^n| n\in \mathbb{N}\\}$ to not belong to the context-free class. By having only one stack we are not able to check the equality of three numbers (i.e. $n\_a=n\_b, n\_a= n\_c, n\_b=n\_c$) at a same time. In the other words, if we want to use what data we have saved, we lose it in a way we can not have the data as before.

So we need more than one stack to overcome the limitation of storing data.

By the way, the automaton equipped with two stacks is as powerful as a Turing machine! (That is the class of languages they decide is equal).
> 1 votes

---
Tags: turing-machines, automata, context-free, pushdown-automata, context-sensitive
---


# Question
Title: How many Huffman codes can be written for a set of n characters?
In my textbook there was the following question:

> How many Huffman codes can be written for a set of three characters?

In the solution they said:

> The Huffman code is determined by the source's probability vector. The code is determined by the order of the probabilities and their combinations. When given a vector of probabilities of the set of symbols the code is determined. The match between the vector space of probabilities and the appropriate code is not 1-1. The match depends on the relationship between the probabilities in the vector. For a group with one symbol there is one code. For a group with two symbols there is one symbol whose probability is greater than or equal to the other symbol and therefore there is a single Huffman code. For a group with 3 symbols - After arranging the vector of probabilities we get that the union of the two symbols with the same small probabilities is equal. But there are two options for uniting the groups in the second stage. We will get two possible codes: $0,10,11$ or $1,00,01$.

It made me wonder - what if we have $n$ elements in the set? Is there a general formula to count the number of ways? Also, why for set with one element it's $1$ and not $2$? (I can encode the element to be $0$ or $1$ no?)

# Answer
A non-redundant prefix code on $n$ elements (which seems to be what your textbook means by *Huffman code*) is the same as a binary tree with $n$ leaves, and those are counted by Catalan numbers.
> 4 votes

---
Tags: algorithms, huffman-coding
---


# Question
Title: Optimal prune of a mutually-exclusive bipartite graph
I start with a complete edge-weighted unbalanced bipartite graph.

For a known, fixed $n$ on the order of 1000:

$$0 \lt n, n \in I$$

Left and right cardinalities might not be equal; for sides $U$ and $V$:

$$0 \< |U| \le |V| = n$$

All edge weights are known, fixed, integral and non-negative.

I need to prune this graph such that

* for every $U$ node, there remains exactly one edge ($U$ becomes 1-regular);
* for every $V$ node, there remains at most one edge;
* it will become disconnected and acyclic;
* the edges are chosen such that the total remaining weight is minimised.

I've had limited success in writing a solution better than a brute-force traversal of all edge permutations. The best attempt - which still scales poorly - is roughly

1. construct an ordered sequence of $U$ nodes
2. let depth $d := 0$, to index into the $U$ nodes
3. at each $d$, let $i$ index into the set of possible edge nodes at $d$
4. If $i$ has not exhausted the possible edges at $d$,
    1. select one of the possible edges $e\_{d,i}$ for $U\_d$;
    2. calculate the next set of all possible edge choices for $U\_{d+1}$ excluding $e\_{d,i}$ to pass to state $d+1$;
    3. $d := d + 1$ \- but only if the short-circuiting predicate is not true
5. if $i$ has encountered the end of possible edges at $d$, then $d := d - 1$
6. store the lowest-cost option for all depths up to $d$
7. iterate 3-6 until $d = 0$.

The short-circuiting predicate terminates a tree if its accumulated cost from $d=0$ to the current depth is equal to or greater than the lowest cost ever seen to the bottom depth.

To give a sense of how poorly this scales,

```
n=2 t=7.120e-05
n=3 t=6.440e-05
n=4 t=6.450e-05
n=5 t=6.540e-05
n=6 t=8.680e-05
n=7 t=6.550e-05
n=8 t=8.890e-05
n=9 t=4.275e-04
n=15 t=5.372e-04
n=20 t=1.674e-03
n=30 t=4.620e-02
n=35 t=1.858e-01

```

Is there an established algorithm that can do better?

# Answer
Your problem is known as the assignment problem.
> 1 votes

---
Tags: optimization, bipartite-matching, bipartite-graph
---


# Question
Title: How to match a string with any linear transformation of the pattern?
The following exercise in my homework is about string matching using the $KMP$ algorithm with a pattern that can be modified by a linear transformation.

Question: We're given a text $T \in \mathbb{N}^\*$ where $|T|=n$ and a pattern $P \in \mathbb{N}^\*$ where $|P|=m$, in other words $T$ and $P$ are consisted of natural numbers (an example appears below). We're required to describe a **linear** algorithm that finds all the matches in $T$ with the pattern $P'$ such that: $$P'=cP+k$$ for every $c\in \mathbb{R} \neq 0$ and $k\in \mathbb{R}$. Note that $c$ and $k$ aren't given and we have to find them.

For example: let $T=(3,7,9,5,0,0,3)$, $P=(1,3,4)$. In this situation we have a matching in the first 3 numbers if we let $c=2$ and $k=1$.

I have a solution for this question but it has a problem with it so if anyone could help. Here is my algorithm:

1. Create $P'$ such that $P'\[i\]=P\[i\]-P\[i+1\]$ for every $1\leq i\leq n-1$.
2. Create $P''$ such that $P''\[i\]=\frac {P'\[i\]} {P'\[i+1\]}$ for every $1\leq i\leq n-2$.
3. Do same things that We've done with $P$ for $T$ and get $T''$.
4. Run $KMP$ with text $T''$ and pattern $P''$.

My algorithm works until there are $0$'s in $P'$ or $T'$. The example above will divide by 0 to get $P''\[4\]$. I tried to let $\frac x 0 = 0$ for every $x\in \mathbb{R}$ but it won't work if we take for example $T=4221$ and $P=3221$. I had an idea to skip the 0's if there is while making $P''$ and $T''$ but I don't know really how to describe this. I know it should work but it is hard to describe.

# Answer
Your idea of extracting the ratios of successive differences between the adjacent numbers is brilliant.

### Let $P''$ retain all needed information

The $0$'s in $P'$ or $T'$ pose some difficulty in producing the ratios. Your idea of "skipping the $0$'s" is the right approach. In order to make your idea working, we should also track how many $0$s are skipped.

At step 2, instead of dividing by $P'\[i+1\]$, divide $P'\[i\]$ by the nonzero number in $P'$ at the smallest index $j\lt i$. We have to keep track of the difference between $j$ and $i$ as well.

Since $c\neq 0$, if $P'\[i\]$ matches $T'\[j\]$, then both of them are zeros or none of them is $0$, i.e., it cannot happen that exactly one of them is $0$. So The information whether a number in $P'$ or $T'$ is $0$ or not is critical. If it is $0$, then whether the number before it is $0$ or not can be helpful information as well.

Following the ideas above, here is one way to create $P''$.

* if $P'\[i\]==0$,
    + if $i== 1 $ or $P'\[i-1\]==0$, let $P''\[i\] = (555555, -1)$
    + otherwise, let $P''\[i\] = (55555, -2)$
* Otherwise,
    + if there is no nonzero element before index $i$ in $P'$, let $P''\[i\] = (55555, -3)$.
    + else, suppose $j$ is the index of last such element. Let $P''\[i\] = (P'\[i\]/P'\[j\], i-j)$

When $P''\[i\]$ is one of $(55555,-1)$, $(55555,-2)$ and $(55555, -3)$, the second parts, $-1, -2, -3$ carries all the information in $P''\[i\]$. The first parts, $55555$, are padded so that $P''\[i\]$ is always a pair of numbers for all $i$.

Create $T''$ from $T'$ in the same way.

### What does "match" mean?

How can we apply/tweak KMP algorithm to process $P''$ and $T''$ so that we will find all affine transformation of $T'$ in $P'$? The key point is to customize the meaning of "$P''\[i\]$ matches $T''\[j\]$" to suit our purpose.

They match if

* either they are the same,
* or the second part of $T''\[\[j\]$ is $-3$ -- which means all elements before index $j$ in $T'$ are $0$s and the second part of $P''\[i\]$ is greater than $j+1$ -- which means all $j$ elements before index $i$ in $P'$ are $0$s).

### An implementation in Python

The arrays/lists in the explanation above start at index 1. Of course, when it comes to Python, all lists start at index 0.

```
def get_ratios(numbers):
    """Return the enriched ratio of ratios of successive differences between
     the adjacent numbers. 55555 is used only for padding."""
    n = len(numbers)
    diffs = [numbers[i + 1] - numbers[i] for i in range(n - 1)]

    to_previous_index = [-1] * n  # of nonzero element in diffs
    index_of_previous_nonzero = -1
    for i in range(n - 1):
        to_previous_index[i] = index_of_previous_nonzero
        if diffs[i]:
            index_of_previous_nonzero = i

    def compute_enriched_ratio(index):
        if diffs[index] == 0:
            return (55555, -1) if index == 0 or diffs[index - 1] == 0 \
                    else (55555, -2)
        else:
            if to_previous_index[index] == -1:
                ratio = (55555, -3)
            else:
                ratio = (
                    diffs[index] / diffs[to_previous_index[index]],
                    index - to_previous_index[index])
            return ratio

    ratios = [compute_enriched_ratio(i) for i in range(1, n - 1)]
    return ratios

def is_matched(pattern, j, nums, i):
    """return whether pattern[j] matches nums[i]"""
    return pattern[j] == nums[i] or (pattern[j][1] == -3 and nums[i][1] > j + 1)

def compute_partial_match_table(pattern):
    """ return an array the element of which at index i is the length of
    the longest suffix of pattern[0:i] that matches a prefix of the pattern"""
    m = len(pattern)

    pmt = [0] * m
    pmt[0] = 0
    longest = 0  # length of the previous longest prefix suffix
    i = 1
    while i < m:
        if is_matched(pattern, longest, pattern, i):
            longest += 1
            pmt[i] = longest
            i += 1
        else:
            if longest:
                longest = pmt[longest - 1]  # i is not increased
            else:
                pmt[i] = 0
                i += 1

    return pmt

def find_all_matches_with_affine_transformation(pattern, nums):
    """return all indices such that for each index j, there exists an affine
    transformation of `pattern` that is a prefix of `nums[j:]`"""
    m, n = len(pattern), len(nums)
    if m > n:
        return []
    if m == 1:
        return list(range(n))
    if m == 2:
        if pattern[0] == pattern[1]:
            return [i for i in range(n - 1) if nums[i] == nums[i + 1]]
        else:
            return [i for i in range(n - 1) if nums[i] != nums[i + 1]]

    ratios_pattern = get_ratios(pattern)
    ratios_nums = get_ratios(nums)

    # KMP algorithm
    pmt = compute_partial_match_table(ratios_pattern)

    m -= 2
    n -= 2
    j = 0  # index of current number in pattern
    i = 0  # index of current number in nums
    matches = []
    while i < n:
        if is_matched(ratios_pattern, j, ratios_nums, i):
            i += 1
            j += 1

        if j == m:
            matches.append(i - j)
            j = pmt[j - 1]

        elif i < n:  # mismatch after j matches
            if j != 0:  # since pattern[0..lps[j-1]] matches
                j = pmt[j - 1]
            else:
                i += 1
    return matches

def demo():
    pattern = [1, 3, 4]
    nums = [3, 7, 9, 5, 0, 0, 3]
    indices = find_all_matches_with_affine_transformation(pattern, nums)
    for i in indices:
        print("starting at index", i, nums[i: i + len(pattern)])
    # starting at index 0 [3, 7, 9]

demo()

```
> 2 votes

---
Tags: algorithms, string-matching
---


# Question
Title: Sorting lower bound is linear when only a constant number of distinct keys?
I saw this proposition on Sedgewick's lecture slides on QuickSort, and I've been wondering why the number of comparisons is linear in the case of a constant number of distinct keys. I tried to establish a linear upper bound but failed to find the appropriate linear lower bound. Here are my workings($N$ is the total number of keys): $$\begin{align} &-\sum\limits^{n}\_{i=1}x\_{i}\lg{\frac{x\_i}{N}}\\\&=\frac{1}{\ln2}\sum\limits^{n}\_{i=1}x\_{i}\ln{\frac{N}{x\_i}} \\ & \leq \frac{1}{\ln2}\sum\limits^{n}\_{i=1}\frac{N}{e}\ln{\frac{N}{\frac{N}{e}}} \quad(\text{by differentiation the maximum occurs when $x=N/e$}) \\ & =\frac{N}{e\ln2}\sum\limits^{n}\_{i=1}\ln{e} \\ & =\frac{n}{e\ln2}N \end{align}$$ When $n$ is constant, it's linear in $N$. But I failed to find a similar lower bound.

I also found another result given by Sedgewick using entropy. The number of compares can be written as $NH$, where $H=-\sum\limits^{n}\_{i=1}\frac{x\_i}{N}\lg{\frac{x\_i}{N}}$. I'm not familiar with information theory, but does this mean that when $n$ is constant, the entropy can be considered constant, so the number of compares is linear?

# Answer
You are missing an easy approach.

The case of $n=1$ is trivial. No comparison is needed.

Otherwise, let $n\ge2$. Suppose we have sorted $N$ keys with $m$ comparisons. For each comparison, connect two keys involved with an edge, considering each key as a node. With $m$ comparisons, we obtain a graph of $N$ keys. That graph must be connected; otherwise, we cannot sort the keys that belong to different connected components. That means there are at least $N-1$ edges in the graph, i.e., there must have been at least $N-1$ comparisons. This lower bound of $N-1$ comparisons for general cases (which include the worst case of course) can be the linear lower bound you want.

The lower bound of the worst case could be refined to be something like $\displaystyle\Theta(nN)$ for some appropriate meaning of $\Theta$ for two variables $n$ and $N$. However, it is probably another question to prove that.
> 1 votes

---
Tags: complexity-theory, sorting, information-theory
---


# Question
Title: Decidability of a given grammar if it is regular
According to my course the question "Is $L(G)$ regular?" undecidable. But I was more interested in knowing the exact algorithm or proof that makes this question undecidable. To further elaborate what I mean it is like saying "Is 2 bigger than 1?" is pretty much decidable intuitively because $2 = 1 +1$.

# Answer
Undecidability is counter-intuitive at the best of times, and proofs of undecidability might feel unsatisfying at first glance, since they are necessarily non-constructive. (How can you construct an algorithm for something which has no algorithm?)

The basis for a lot of undecidability proofs is Rice's theorem, which basically says that for any non-trivial semantic property $P$, there is no algorithm which can determine whether an arbitrary program has that property. ($P$ is non-trivial if there is at least one program which satisfies it and at least one program which doesn't satisfy it.) We usually represent programs as Turing Machines, here, since any program can be rewritten as a Turing Machine (although it might not be a practical endeavour). I'm not going to attempt a precise definition of "semantic property" —you can read the Wikipedia page or look at some of the references— but it basically refers to any property which requires running the program.

Here's it's useful to note that any Turing Machine can be represented as a general grammar which derives precisely those inputs which the Turing Machine would accept.

You might think that you can avoid the pathological cases by restricting the grammar to being context-free, but it turns out that even though context-free grammars are a lot easier to reason about than general grammars, there is still no way to tell whether the language recognised by an arbitrary context-free grammar is regular. Nor is there an algorithm to tell whether a context-free grammar recognises every sentence produced with a given alphabet. These two statements were proven in 1963 by Sheila Greibach; the linked Wikipedia page summarizes her elegant proof.
> 2 votes

---
Tags: regular-languages, formal-grammars, undecidability
---


# Question
Title: Does the reliability of polynomial hashing depend on whether the modulus is prime, for coprime base and modulus?
A polynomial hash of a string $s$ with base $b$ and modulus $M$ is defined as

$$ H(s) = (s\_0 + s\_1 b + s\_2 b^2 + \dots + s\_{n-1} b^{n-1}) \mod M. $$

I have proven (and this is quite obvious) that collisions are more likely if $b$ and $M$ have common factors.

I have also proven that if $b \perp M$ and $s\_i$ are random numbers in range $\left\[0; M\right)$, the probability that a hash is zero (and, therefore, the approximate probability of collision) is $\frac{1}{M}$. This seems to imply that, as long as $b \perp M$, it does not matter whether $M$ is prime or not.

However, for all practical purposes, including when implementing polynomial hashing manually, prime $M$ is considered more reliable than a similar (and possibly twofold larger) power of two. Why is that so? Does the answer depend on the magnitude of $b$ and whether $s\_i$ are arbitrary numbers from $\mathbb{Z}/M\mathbb{Z}$ or are from a lesser subset of the ring, e.g. alphabetic characters?

P.S. I am aware of the well-known and easily constructible anti-hash tests for powers of two. The question is about more "random" input, I am asking about the probability of two uniformly random strings colliding, or the probability of two "similar" strings colliding.

# Answer
It does matter. Primes are better, at least in some sense. If we choose $b$ randomly, then the probability of a collision between two different strings is at most $n/M$ when $M$ is prime, but can be much higher when $M$ is not prime. In particular, when $M$ is prime and $b$ is random, this hash function is 2-universal, and is known as the multiplicative hash function. If $b$ is not random but is a fixed value, then the situation is less clear -- it is harder to formulate a precise definition of what counts as "good" -- but the above provides some evidence why primes are better.

It seems you are evaluating the probability of a collision if you hash two strings that are each chosen uniformly and independently at random. That is relatively easy to achieve. What is more challenging to achieve is to ensure that, for every pair of different strings, the probability of collision is low (e.g., the probability of collision is low even if the two strings are similar or related). The latter is achieved by 2-universal hash functions.

So, one intuitive way to explain why it might be better to choose $M$ as a prime is that we expect it may be better in situations where you hash two related strings. I think those kinds of situations arise frequently in practice. That said, as a heuristic, you can always use a non-prime value of $M$. If it is good enough in your application, then all's well. In practice the worst case situations often don't arise, and even imperfect hash functions can often do well.
> 1 votes

---
Tags: probabilistic-algorithms, hashing, polynomials, modular-arithmetic
---


# Question
Title: Data structure to efficiently add zero-rows to a sparse matrix
I would like to create a data structure representing a sparse matrix, where the number of non-zero values is $\mathcal{O}(n)$ (the matrix is $n\times n$).

The matrix should support the following operations with the following time complexities:

1. peek/poke an entry in the matrix - $\mathcal{O}(n)$.
2. add a row of zeros somewhere in the matrix - $\mathcal{O}(1)$.

I tried simply using a linked list or a list of lists but these approach doesn't work because when we add a zero row all indices get mixed up.

# Answer
> 1 votes
An easy but probably undesired way is doing the operation lazily. The list of lists representation can be modified slightly to support "add row" in $O(1)$ time.

When you add a row, you don't actually touch the main structure. But only add the row index to the list as an "unprocessed operation". This is $O(1)$ time.

When you access an entry, check for the unprocessed operation list. If there are unprocessed operations, sort and merge the added rows to the main structure. This can be done in $O(n)$ time.

# Answer
> 1 votes
You can achieve $O(\log n)$ time for all operations, by using a balanced binary search tree for the index that maps from a row index to the row. Such a tree can support $O(\log n)$ time lookup of any index, and can also support inserting a row in $O(\log n)$ time. Each row can be represented in any convenient way, e.g., a hashtable that maps from column index to the value, or a tree to representing this mapping.

# Answer
> 0 votes
You can use your lists of list representation. But your main list $M$ will be a circular, double linked list. A new row will be inserted at the head of $M$, which takes $O(1)$ time. Each row will store its own row position $p$. Now, it's possible for multiple rows to have the same row position at any time. Say you insert $r\_i$ first as row 0 then $r\_j$ next, again as row 0. Inserting $r\_j$ should have "pushed" $r\_i$ one position forward, however we will not update $r\_i$'s position until later. Note that $r\_j$ will appear in front of $r\_i$ in $M$. In general, it's possible that a new row $r$ inserted at position $p$ to "push" some rows that were inserted much earlier if the position of these rows is $\geq p$. Updating all row positions will be done during peek.

We will use $r.p$ to represent the stored position of a given row $r$. Now for peek, we will use "bucket-sort" like technique. Create a new array $B$ whose size is $n$, the current number of rows in $M$. This array is actually an array of linked list (like a hash table). Now traverse $M$ backwards, removing each row along the way. When a row $r$ is removed, insert it at the head of list $B\[r.p\]$. This will empty $M$ and transfer everything to $B$, but rows with different positions are stored in separate buckets. As for rows with the same position, their order in $B$ are preserved. From the example above, $r\_i$ and $r\_j$ will be stored on the same bucket and $r\_j$ will still be in front of $r\_i$. Let $i = 0$. Empty $B$ by removing the contents (rows) of each bucket one at a time starting from $B\[0\]$ up to $B\[n-1\]$. When a row $r$ is removed from $B$, set $r.p = i$, increment $i$, then insert it to $M$ but this time at the tail. Inserting at the tail of a circular, double linked list also takes $O(1)$ time. Observe that once $B$ is empty all rows have their correct position and are stored in $M$ in order of their position. Now you can start traversing $M$ to peek the row you need. Transferring rows from $M$ to $B$ back and forth takes $O(n)$ time and the actual accessing of a row takes $O(n$) time, thus overall you have $O(n)$ for peek.

---
Tags: data-structures, matrices, sparse-matrices
---


# Question
Title: Deciding whether there always exist k different disjoint paths between any pair of vertices in a graph
Given a graph $G$ and an integer $k$, is it NP-complete to decide whether there always exist $k$ different disjoint paths between any pair of vertices of $G$?

# Answer
Assuming you meant "decide whether any two nodes in $G$ can be connected by $k$ or greater disjoint paths" (i.e.: only the paths between any two vertices have to be disjoint, the paths between different vertices can overlap), you can use a max flow algorithm to determine the maximum number of disjoint paths between two nodes. Running this algorithm on all $n^2$ pairs of vertices and checking that this maximum number is greater than $k$ will solve your decision problem.
> 0 votes

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


# Question
Title: recursive algorithm to sort children and parents based on value
## Task

Consider the following recursively-defined tree structure:

```
const tree = {
  val: 1,
  children: [
    {val: 2},
    {
      val: 3,
      children: [
        {
          val: 4,
          children: [
            {val: 5},
            {val: 6},
            {val: 7}
          ]
        }
      ]
    }
  ]
};

```

Here, each node in the tree is an object with a required "val" property that maps to a non-unique integer and an optional "children" property that, if present, maps to an array of child nodes. There will only be a single root node in the outermost object.

This challenge involves writing a function prioritizeNodes(tree, targetVal) which accepts a valid nested tree object conforming to the above definition. The function should sort all "children" arrays containing one or more nodes with node.val === targetVal to the front of the array. For the above tree, the output for a call to prioritizeNodes(tree, 7) would be:

```
const expected = {
  val: 1,
  children: [
    {
      val: 3,
      children: [
        {
          val: 4,
          children: [
            {val: 7},
            {val: 5},
            {val: 6}
          ]
        }
      ]
    },
    {val: 2}
  ]
};

```

Each node in a tree with a value or child matching the target was moved to the front of its respective array.

Non-prioritized nodes should be kept in their original relative ordering with respect to one another, and prioritized nodes which were moved to the front of an array should also maintain order with respect to other priority nodes in the array. Your function may mutate the parameter tree in-place in addition to returning it if you wish.

## Examples

**Example 1**

```
const tree = {val: 1};
prioritizeNodes(tree, 1); // => {val: 1}
This is a trivial example.

```

**Example 2**

```
const tree = {
  val: 1,
  children: [
    {
      val: 1,
      children: [
        {val: 7}
      ]
    },
    {
      val: 3,
      children: [
        {val: 55}
      ]
    },
    {
      val: 2,
      children: [
        {val: 15}
      ]
    },
    {
      val: 7,
      children: [
        {val: 2}
      ]
    }
  ]
};

```

A call to prioritizeNodes(tree, 2) on the above structure should return

```
const expected = {
  val: 1,
  children: [
    {
      val: 2, // <-- this moved up
      children: [
        {val: 15}
      ]
    },
    {
      val: 7, // <-- this moved up because its child has a val of 2
      children: [
        {val: 2}
      ]
    },
    {
      val: 1,
      children: [
        {val: 7}
      ]
    },
    {
      val: 3,
      children: [
        {val: 55}
      ]
    }
  ]
};

```

Note that the parent node with value 7 was considered to be prioritized because it contained a descendent with a value matching the target. All children of the root maintained relative ordering after moving high-priority nodes to the front.

**Example 3**

```
const tree = {
  val: 1,
  children: [
    {
      val: 2,
      children: [
        {
          val: 7,
          children: [
            {val: 2},
            {val: 18},
            {val: 12}
          ]
        }
      ]
    },
    {
      val: 4,
      children: [
        {val: 5},
        {
          val: 6,
          children: [
            {val: 12},
            {val: 11},
            {val: 10},
            {val: 9},
          ]
        },
        {val: 13}
      ]
    },
    {
      val: 3,
      children: [
        {val: 15}
      ]
    },
    {
      val: 17,
      children: [
        {val: 16},
        {
          val: 2,
          children: [
            {val: 14},
            {val: 11},
            {
              val: 18,
              children: [
                {val: 4},
                {val: 11},
                {val: 7}
              ]
            },
            {val: 27},
            {val: 18},
            {val: 29},
          ]
        }
      ]
    }
  ]
};

```

In this large example, prioritizeNodes(tree, 18) is expected to return

```
const expected = {
  val: 1,
  children: [
    {
      val: 2,
      children: [
        {
          val: 7,
          children: [
            {val: 18}, // <-- this moved up
            {val: 2},
            {val: 12}
          ]
        }
      ]
    },
    {
      val: 17, // <-- this moved up
      children: [
        {
          val: 2, // <-- this moved up
          children: [
            {
              val: 18, // <-- this moved up
              children: [
                {val: 4},
                {val: 11},
                {val: 7}
              ]
            },
            {val: 18}, // <-- this moved up
            {val: 14},
            {val: 11},
            {val: 27},
            {val: 29},
          ]
        },
        {val: 16}
      ]
    },
    {
      val: 4,
      children: [
        {val: 5},
        {
          val: 6,
          children: [
            {val: 12},
            {val: 11},
            {val: 10},
            {val: 9},
          ]
        },
        {val: 13}
      ]
    },
    {
      val: 3,
      children: [
        {val: 15}
      ]
    }
  ]
};

```

## And My solution was:

class Node {
    val;
    children;

    constructor(data) {
        this.val = data.val || null
        if(data.children?.length > 0){
            this.children = []
            this.addChildren(data.children)
        }else if(this.children?.length <= 0){
            delete this.children
        }
    }
    addChildren(children) {
        if(children?.length > 0){
            for (let i = 0; i < children.length; i++) {
                let newNode = new Node(children[i])
                this.children.push(newNode)
            }
        }
    }
}

function repeater(node, targetVal) {
    let parentFlag = false
    if(node.children?.length > 0){
        for (let i = 0; i < node.children.length; i++) {
            if(repeater(node.children[i], targetVal)){
                node.children.unshift(...node.children.splice(i, 1))
                parentFlag = true
            }
        }
    }
    return node.val === targetVal || parentFlag;
}

const prioritizeNodes = (tree, targetVal) => {
    if(!tree.children){
        return tree
    }
    let newTree = new Node(tree)
    for (let i = 0; i < tree.children.length; i++) {
        repeater(newTree, targetVal)
    }
    return newTree
}
```
</code></pre>

# Answer
I don't see a need for any interesting algorithm. In its essence it is equivalent to the following: given an array $A$ of integers and an integer $x$, move all instances of $x$ to the front of $A$, keeping the rest in the same order. Once you can solve that, you can apply it to each node of your tree.

To move all instances to the front, one approach is to collect a list of instances of $x$, collect a list of all the other instances, and then concatenate those lists. Implemented correctly, you can do this in $O(n)$ time, where $n$ is the number of elements in the array. Or, you can do it in $O(n)$ time and $O(1)$ space with a linear scan over the array and a clever bit of "swapping" of elements -- I'll let you work that out.
> 2 votes

# Answer
Your solution is almost correct, you just have to add an else statement to the repeater function to delete children when node.children are undefined

```
    if(repeater(node.children[i], targetVal)){
                    node.children.unshift(...node.children.splice(i, 1))
                    parentFlag = true
                }else{
 delete node.children
}

```
> 0 votes

# Answer
I got stuck in the same challenge and with some help from stackoverflow community here's what worked for me :

shifting priority nodes into the children array will inverse the order of the priority nodes, which is not what is asked for.

avoiding mutation and creating two new children arrays in which the children are divided: one for the priority ones, and one for the other children. Then concatenate those two. Let the recursive function return both the new children array and the flag.

```
   function prioritizeNodes(tree, targetVal) {
        function recur({val, children}) {
            if (!children) {
                return [{ val }, val === targetVal];
            }
            let categories = [[], []],
                isPrio;
            for (let child of children) {
                [child, isPrio] = recur(child);
                categories[1-isPrio].push(child);
            }
            return [
                { val, children: categories.flat() },
                categories[0].length > 0 || val === targetVal
            ];
        }
        return recur(tree)[0];
    }

    // Example input
    let tree = {"val": 1,"children": [{"val": 2},{"val": 3,"children": [{"val": 4,"children": [{"val": 5},{"val": 6},{"val": 7}]}]}]}

    let result = prioritizeNodes(tree, 7);
    console.log(result);

```
> 0 votes

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


title: MAE greater than MSE - is it possible?

text:
# Question
Title: MAE greater than MSE - is it possible?
I have used KNN for predicting the output power of solar panels. I have done feature scaling based on normalization for all data points. The problem is that the MAE is equal to 0.08, and MSE is equal to 0.06. I know that MSE must be greater than MAE. What is the reason behind that ?

# Answer
No, it is not correct that MSE must be greater than MAE, particularly when the errors are small. For instance, if all errors are 0.01, then MAE will be 0.01, and MSE will be 0.0001. See also https://stats.stackexchange.com/q/375925/2921, https://stats.stackexchange.com/q/307553/2921.
> 2 votes

---
Tags: machine-learning, python
---


# Question
Title: Internet speeds vs. computer boot speeds
**Internet speeds vs. computer boot speeds:** Both cases involve digital signals being decrypted, analyzed, and transmitted via software and hardware. Signals from a computer boot only travel as far as the distance between its internal components. But, internet signals travel all over the world. How come when you search Google or Amazon around the world, you get results instantly, where modern computers take between 6 seconds and minutes to boot up?

Let's analyze this further. Many factors, obstacles, and bottlenecks determine the latency and speed of internet signals. It starts with the click of the ENTER button, traveling from your PC around the world and back—ending in drawing the results in pixels on your monitor. The same goes for PC boot speed.

Additionally, the CPU core runs only one thread at a time; threads wait in queues, or tasks are split among multiple cores. When traveling around the world, there are many more signals "in line" than there are inside your own computer.

I'm no expert on digital speeds but let's think like a 6-year-old. To simplify, I'll use three factors: Hardware, Software, and Distance.

**DISTANCE:**

This one is obvious. Signals from the Internet travel worldwide while signals from a booting computer don't leave your desk.

**HARDWARE:**

Google or Amazon searches travel through many hardware components - many of which are known to be speed bottlenecks. First, it must pass through YOUR hardware: keyboard, HDD, internal parts, cables, router. Then it passes through many other components, including underwater fiber-optic cables, routers, and hard drives at your ISP, Google's and Amazon's servers, and probably 16 more places where the signals "hop" around.

On the other hand, signals only need to use the hardware within your chassis while booting up a computer.

**SOFTWARE:**

MANY software programs process Internet signals. A browser's software gathers input and creates packets for transmitting. Your operating system then handles everything. Then your router's software. After that, your ISP's router and server software. And finally, Google and Amazon's routers and servers use sophisticated algorithms to provide you with the most relevant results. When the packets return, your router and PC software is used again. Signals are received analyzed, and instructions are sent to the GPU to display results on your monitor. There's probably a ton more.

On the other hand, when your computer boots, it only needs some software from the BIOS, CPU, GPU, OS, and maybe a few more from various PC components. It loads some software into RAM, and ok, I think you get my point. Booting a computer utilizes a fraction of the software used for internet travel.

**TO SUMMARIZE THE QUESTION:**

Why do you get internet results in a split second, yet modern 2022 computers take between six seconds and minutes to boot?

# Answer
> 5 votes
There is no connection between those two times. It's like asking why it takes 10 minutes to cook a pot of pasta but 17 minutes to listen to In-A-Gadda-Da-Vida. Boot time is not limited by the time it takes for an electrical signal to travel from your CPU to your devices, but by other factors.

Boot time varies widely. One of the factors that often makes booting take a long time is a rather obscure matter: when you boot a computer, it probes all connected devices and accessories to find out what is attached to it. For reasons that I don't understand, apparently it can take some devices a long time to respond -- maybe as much as a minute. So, this probing process has to wait for the maximum amount of time it might take for any possible device to respond. There is no fundamental reason why it necessarily needs to take that long for a device to respond; it's just an accidental consequence of engineering and limitations in existing devices.

Another factor has to do with the slowness of hard drives. If you use a magnetic hard drive, then boot time is affected by the time it takes to read in all of the data that is needed during boot -- both the code of all programs, and all the data they use. This, in turn, is limited by the speed of your hard disk. A magnetic hard disk uses a spinning platter. So, the time it takes to read this data can depend on the time it takes for the platter to rotate around from where it currently is, to where the data you need is stored. Notice this has nothing to do with the propagation of electrical signals, but has to do with the speed of movement of a mechanical device, and the latter speed is much much slower than the speed of propagation of electrical signals.

There's a lot more one could say about the time it takes to boot, and it likely depends on many factors, but hopefully this gives you some idea about the complexity and some of the factors that can cause booting to take a while.

---
Tags: algorithms
---


# Question
Title: Why does Hierholzer's algorithm have a time complexity of O(E) instead of O(V+E)?
I saw on Wikipediathat Hierholzer's algorithm has a time complexity of O(E), but won't the dfs used in this algorithm would cause the total time complexity to be O(V+E) instead of only O(E). Assuming we performed the dfs on an Adjacency list. Assume the graph is a connected graph with only one component.

Thanks for the help.

# Answer
> 2 votes
I'm going to assume that you have a reasonable representation of the graph (for example adjacency lists with vertices indexed by small integers).

The only interesting case is $E \in o(|V|)$ (otherwise you already have $O(|V|+|E|) = O(|E|)$).

Then there are at most $O(|E|)$ non isolated vertices. You can find the set $S$ of these vertices (and hence construct the subgraph induced by $S$) in time $O(|E|)$ by simply creating an array (of size at most $2|E|$) containing all endpoints of the edges in $E$, sorting them (in linear time), and dropping the duplicates (again, in linear time).

Then you can apply the algorithm on the remaining subgraph with has $\Theta(|E|)$ vertices and $|E|$ edges (besides, if the number of remaining vertices is larger than $|E|+1$, then the graph has at least two connected components containing at least one edge each, hence no Eulerian path exists).

---
Tags: algorithms, graphs, time-complexity, eulerian-paths
---


# Question
Title: How are instructions from software sent to digital circuit in cpu?
I am studying computer architecture in my university and there is something that's troubling me. I get the bigger picture of how instructions are executed in the fetch - execute cycle and the complete process of a program being read by the compiler and then into machine code....

In my Digital Logic Design class I have used gates and ICs which require a high or low voltage to work. But since it was just hardware, the input was provided using switches / batteries. What I cant grasp is how does a piece of software provide the same "high / low" input to the cpu for the computation to be done.

For example, I make a program which just saves a number "10" in my RAM when I click a button on screen. After it is decoded to machine code, how are the electrical signals sent to the memory cells in RAM to store data? I have tried reading answers here but they weren't really satisfactory.

I would be really thankful if anyone could give a detailed overview using an example and not mark this as duplicate.

Thanks!

# Answer
> 2 votes
A computer program is after all just a sequence of bits.

Each bit that composes the program has this "high voltage" / "low voltage" information, similarly to how your "switch and battery" input system worked.

What might be confusing here is that it seems like a "closed loop" - the inputs are digital bits, but where did they come from? The output of a logical circuit. But where did *its* inputs come from? Again, from the storage in the computer. And this cycle continues...

In reality, this of course doesn't go forever. The inital values for the bits in the storage of the computer are literally hard-coded by hand. For example, the bios is a hard-coded instruction list that determines how to start running the rest of your computer when you click on the "power on" button on your computer.

# Answer
> 0 votes
All software executed by a hardware processor is a sequence of machine-code instructions. Each instruction contains an opcode which stands for operation code. The opcode is an nonnegative integer prefix‡ that identifies which operation to perform and how zero, one, or two (or more rarely more) parameters that the operation takes. Some operations (and thus opcodes) are the familiar integer arithmetic operations: add, subtract, multiply, and divide. Other operations (and thus opcodes) are the familiar floating-point arithmetic operations: add, subtract, multiply, and divide. Still more operations are the familiar bitwise logic operators: bitwise inclusive or, bitwise exclusive or, bitwise and, and bitwise not/inversion. Other operations are branching instructions that you'd think of as either goto or conditional-goto but to an integer offset forward or backward adjustments to the current instruction's address. Still other operations are for accessing memory, especially on RISC processors where accessing memory is practically never performed within the arithmetic or bitwise-logic operations.

‡ VLIW architectures are effectively multi-way infix of a sort with an opcode prefix embedded into the infixed multiple instruction-bundle, but that is too advanced for this basic introduction.

The nonnegative integer of the opcode is where you will find a sequence of ones and zeros arranged into powers of 2 from 0 upward. Each integer parameter is either always a nonnegative integer or sometimes negative or sometimes positive. This latter form is represented in the modern era via what is called twos-complement numerals where the negative numbers “wrap around” so that –1 is all-bits-one such as 0xFF in a twos-complement 8-bit numeral, with –2 as 0xFE and so forth decrementing. This also is where you will see the zeros and the ones appearing as powers of 2.

All software is a sequence of instructions where the address of the current instruction being executed is pointed to by the program-counter register (a.k.a. instruction-pointer register on Intel). Branching is performed by adding or subtracting offsets to this program-counter register for loops and if-else constructs and the like, to point to a new instruction to execute next that is non-sequential after the branch instruction.

---
Tags: computer-architecture, digital-circuits
---


# Question
Title: Why is the input of the algorithm in "Linear-Time Self Attention with Codeword Histogram for Efficient Recommendation" a matrix?
My question is about the algorithm in the article Linear-Time Self Attention with Codeword Histogram for Efficient Recommendation, as described in the picture below.

It is written at beginning section 3.1 in the article $X$ is a matrix but It is seen the figure 2 a sequence of codeword indices represented as a vector and in figure 3 a sequence of codeword indices is represented as a matrix, so I don't understand these details.

Please explain why the codeword indices are depicted as a vector in figure 2 and as a matrix in Figure 3.

# Answer
> 1 votes
Because Figure 2 shows the case with only 1 codebook. In Figure 3, the $B$-dimension represents the codeword indices of an item in the $B$ codebooks.

By the way, the "matrix" mentioned at the beginning of Section 3.1 is different from the "matrix" in Figure 3. the former is in $\mathbb{R}^{L\times D}$ and is the original input. Since Section 3.1.2, $B$ codebooks are introduced, and the input is then encoded as a matrix in $\\{1,\ldots,W\\}^{L\times B}$. Please refer to Section 3.1.2 for details.

---
Tags: algorithms, algorithm-analysis, machine-learning
---


# Question
Title: Is there a solution faster than O(n^2) for this greedy/sorting problem?
In a market there are N different items where each item is unique and identified by id (1-N). There are also K buyers with names (1-K). Each buyer has 2 items that they want to buy (A, B), where A is the id of the first item and B is the id of the second item. Each buyer will either buy one or no item. If the first item is available they buy it, and if it isn’t available they buy the second item.

Print the order of the buyers that will maximize items sold.

# Answer
> 1 votes
Just do a maximum matching in a bipartite graph corresponding to buyers and items where each buyer is connected to the two items she/he wants to buy.

It is obvious that the maximize items sold cannot exceed the value of the maximum matching. On the other hand, we can always turn the maximum matching into a valid maximum matching, meaning we can arrange the order of the buyers such that the items matched are sold to the corresponding buyers.

Suppose in the maximum matching, buyers in $A$ first-match (match their favorite items) items in $B$ and buyers in $A'$ second-match (match their second favorite items) items in $B'$. We adjust the matching as follows. Note we always maintain the set $A, B,A',B'$ such that $A$ ($A'$) and $B$ ($B'$) respectively represent the buyers and the items that are first-matched (second-matched). We do not state explicitly how elements are added in or deleted from these sets for simplicity. For a buyer $a$, we denote by $\mathrm{first}(a)$ and $\mathrm{second}(a)$ the items she/he wants to buy respectively.

```
For each a in A' such that first(a) is not in B:
    If first(a) is not in B':
        replace the second-match a-second(a) with a first-match a-first(a)

# Now for each a in A', first(a) is either in B or in B'

For each a1, ..., an in A' such that first(a1) == second(a2), first(a2) == second(a3), ... and first(an) == second(a1)
    replace the second-matches [a1-second(a1), ..., an-second(an)] with the first-matches [a1-first(a1), ..., an-first(an)]

```

After the adjustment above you can check that the resulting matching is a valid maximum matching. The buyers in $A$ come firstly, the buyers $a\in A'$ such that $\mathrm{first}(a)\in B$ come secondly, and the rest buyers in $A'$ come lastly. Note the order of the rest buyers must obey the rule that if $\mathrm{first}(a\_1) = \mathrm{second}(a\_2)$ then $a\_2$ must come before $a\_1$. You can obtain this order by topological sorting.

---
Tags: algorithms, time-complexity, dynamic-programming, sorting, greedy-algorithms
---