# Question
Title: Do Combinational Logic circuits describe a set of languages?
I was looking at this picture: https://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Automata\_theory.svg/640px-Automata\_theory.svg.png

Which made me think, that if all Turing Machines PDA's and FSA's recognize certain sets of languages, there has to be a set of languages which is recognized by Combinational Logic circuits.

A quick look around on this site and on wikipedia has led me to believe that circuits cannot recognize languages because theyre stateless but I want to hear that preferably from someone who knows more than me in this subject.

# Answer
> 1 votes
Yes IF we accept some restrictions regarding the fixed size of the input, and we consider the outputs to be part of the domain of discourse appended at the end of the input (or, for single-bit outputs, use it as an indicator of valid inputs).

There is a mapping betweeen types of grammar and the type of automaton that can recognise them:

```
Type    Grammar Accepted          Automaton
Type 0  Unrestricted grammar      Turing Machine
Type 1  Context-sensitive grammar Linear-bounded automaton
Type 2  Context-free grammar      Pushdown automaton
Type 3  Regular grammar           Finite state automaton

```

One one hand, we can always build a finite state automaton that accepts the same set of valid inputs, arriving at the same final state / output, as any given combinational circuit.

Inversely, the set of valid inputs for a combinational circuit does define a language which is produced by a grammar, and a regular (type 3) grammar is guaranteed to be enough to generate that language (albeit it may not be the best approach to model a given combinational circuit, and the complexity and semantics of the resulting grammar may be no better than a huge input/output table).

Let's think, for example, of a circuit that validates a parity bit for a given byte, with a 9-bit input: you could say that such combinational circuit implements a grammar, and the produced language is the set of bytes with correct parity bits.

Again, in many applications of combinational logic, however, thinking in terms of formal languages theory is not the most useful approach (since their input is limited, we often think in terms of truth tables and boolean logic).

This answer provides further insights: What is the connection between combinatorial circuits and finite state automata?

---
Tags: formal-languages, automata, chomsky-hierarchy
---


# Question
Title: Shuffle of a DCFL and a regular language
This is problem 88 from Miscellaneous exercises of Kozen's "Automata and Computability".

> The shuffle $A||B$ of two languages $A$ and $B$ is defined as $\\{w \mid w = a\_1b\_1\ldots a\_kb\_k,$ where $a\_1\ldots a\_k ∈ A$ and $b\_1\ldots b\_k ∈ B,$ each $a\_i,b\_i ∈ Σ^∗\\}$.
>
> 1. Show that if $L$ is context-free and $R$ is regular, then $L||R$ is context-free.
> 2. If $L$ is a DCFL, is $L||R$ necessarily a DCFL? Give proof.

The first part is easy by the product construction. I believe that the shuffle of a DCFL and a regular language is not necessarily a DCFL but I am unable to come up with a proof. Any help will be appreciated.

# Answer
> 1 votes
If $L$ is a DCFL and $d$ a symbol, then $\\{d\\}^\*{\cdot} L$ is not necessarily a DCFL. Thus DCFL is not closed under pre-concatenation with regular languages.

An example of that is given in a related answer Why DCFL is not closed under kleene star? (see the comment by Raphael below that answer!)

> The language $L = \\{ a^nb^nc^k \mid n,k \ge 1\\} \cup \\{d\\;a^nb^kc^n \> \mid n,k \ge 1\\}$ however, *is* deterministic. The $d$ prefix gives away which part we are in.

It now follows that DCFL are not closed under shuffle with regular $\\{d\\}^\*$, as we can intersect that shuffle with regular $\\{d\\}^\*\\{a,b,c\\}^\*$ without losing determinism.

---
Tags: regular-languages, automata, context-free, pushdown-automata
---


# Question
Title: how to find the most optimal path for this problem?
There are N islands and there is one pirate. The pirate can start out from any one of the n islands and has the option of either staying on the same island for the next day or moving to a different island.

All the islands are connected to each other by routes. Each evening of the day the pirate steals some gold on the island he is in. The amount of gold the pirate steals depends on the day and the island the pirate is on, and this is given by S\[n\_i\]\[m\_j\], where m represents a day of out M days and n represents an island out of N islands.

The pirate has only m number of days to explore whichever islands he wants and steal.

The pirate also looses some percentage of his gold **first before** getting the day's steal of gold. The percentage the pirate looses depends on the current (i) then the previous island (j) he was in, and is given by L\[i\]\[j\], where 0 \<= L\[I\]\[j\] \<= 100. There is no limitation on the number of times the pirate can visit an island i.

I need an O(N^2\*M) algorithm to calculate the maximum gold that the pirate can steal and also provides the path the pirate takes.

What I tried to do:

I tried to maximise the steal and minimise the gold lost

For day one, choose the island with the most steal

For the rest of the days: calculate best combination of loss and steal by: (net total = current total gold - loss + gain).

I am not sure if this is the way to go about it. Help is much appreciated.

# Answer
The first thing I notice is the required bound: $O(N^2\cdot m)$ This is a nice cushy bound, which is good news for us. The $N^2$ bit tells me that we can visit all pairs of islands (leaving one of $N$ islands and arriving at one of the $N-1$ other islands). And the $M$ bit tells me that that process of visiting all of the islands can be done once for every day on the journey. So if you can come up with a process that visits each pair of islands once on each leg of the journey, you'll meet the bounds needed.

The second thing I notice is that there's no connectivity graph to worry about. Every island appears to be connected to every other island. This is useful because it means you don't really need to find a "path," in the graph theory sense, but rather a "sequence" of islands to visit. Pathfinding is much harder, so I'm happy not to have to do it!

Thinking from a pareto point of view, given any two paths that end on the same island, there is never a reason to consider the one that earns less gold. So we can use this as a filter to cut down the number of paths considered. While I might want to accept less gold in order to end up on a more favorable island, I will never accept less gold *and* end up at the same island.

Algorithm:

* Start on the first day. Initialize an array of $M$ "best path ending in island $m$ after day 0". This is trivial: the only way to end up on an island is to visit it on day 0 is to visit it, so we initialize our "best path ending in island $m$" to $S\[0\]\[m\]$, and record the 1-step path.
* Iterate until we reach the last day
    + Determine the best path to each island on day $j$
    + For each island $m$, compute the best path ending in island $m$ after $j$ days. This can be computed in $(N^2)$ time simply by looking at the best path to every island in the previous steps, and computing the paths to every island on this step from there. The best path to each island is simply the maximum gold-earning path to that island from any of the previous islands.

This takes $M$ iterations. Each iteration involves creating $N$ new "best path to island $i$". Each best path requires looking at $N$ possible previous paths, one ending on each island.
> 0 votes

---
Tags: algorithms, optimization, dynamic-programming
---


# Question
Title: What context-free grammar recognizes a list of numbers 1 - N in order?
I'm looking for a context-free grammar that recognizes precisely the numbers `1` \- `N` in order:

`1,10,11,100` valid (numbers `1` \- `4` in base-2)

`1,1,10,11,100` invalid (duplicate `1`)

`1,10,100` invalid (missing `3`)

`10,1,11,100` invalid (has all numbers but `1` and `2` are not in the correct position)

I'm not sure where to start to create the grammar.

The closest I could come up with are these rules, which I believe recognize a list of `N` natural numbers (with no constraints to order or duplicates or missings).

```
S -> B
B -> B,B | 1A | 1
A -> AA | 1 | 0

```

`A`, `B`, `S` are non-terminals

`1`, `0`, `,` are terminals

`S` is start symbol

What context-free grammar recognizes a list of numbers `1` \- `N` in order?

# Answer
This language $L$ is not context-free, so there is no CFG generating it.

Indeed, suppose it is context-free, and let $n$ be the pumping length. Let $u \in L$ be a word of length $\geqslant n$ (for example $u = 1, 2, …, n$ in binary). The pumping lemma states that $u$ can be written $u = vwxyz$ such that:

1. $|wxy| \leqslant n$;
2. $|wy| \> 0$;
3. for all $k\geqslant 0$, $vw^kxy^kz\in L$.

Suppose there is a decomposition $u = vwxyz$ verifying the first two points. Without loss of generality, suppose $w\neq \varepsilon$ (the same reasonning can be done if $y\neq \varepsilon$). Then:

* if $w$ contains two symbols `,`, then $w^2$ will contain twice the same number, so $vw^2xy^2z$ contains repetitions so is not in $L$;
* if $w$ contains no symbol `,`, then $vw^2xy^2z$ will skip some numbers (we made the integer where $w$ appears bigger), so it is not in $L$;
* if $w$ is exactly `,`, then $vw^2xy^2z$ contains `,,` so it is not in $L$;
* finaly, if $w = w\_1,w\_2$ with $w\_1$ and $w\_2\in\\{0,1\\}^\*$, then $vw^3xy^3z$ will contain $w\_1,w\_2w\_1,w\_2w\_1,w\_2$, so it contains twice the number $w\_2w\_1$, so it is not in $L$.

In all cases, the decomposition does not satisfy the third item. By contradiction, we conclude $L$ is not context-free.
> 1 votes

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


# Question
Title: Suggest good books for Advanced Data Structure and Algorithms
I don't really need hands on coding help, I need to clear my concepts of some of the more complex topics of DS and Algo like NP-Completeness, Computational Geometry, String Matching, Multithreaded Algorithms and Backtracking Algorithms. I have so far read CLRF(Cormen) as my go to book. But sometimes I just can't wrap my head around the more complex topics as mentioned above.

# Answer
> 1 votes
I find Algorithm Design by Kleinberg and Tardos an excellent resource. It will cover some of the topics you mentioned.

---
Tags: algorithms, np-complete, computational-geometry, books, backtracking
---


# Question
Title: Fpt algorithm for hypergraph basis problem
While working through the book Parameterized Complexity Theory of Flum and Grohe, I encountered exercise 1.42:

Let $H = (V, E)$ be a hypergraph. A basis of $H$ is a set $S$ of subsets of $V$ with the property that for all $e \in E$ there are $s\_1, \dots, s\_\ell \in S$ such that $e = s\_1 \cup \dots \cup s\_\ell$. The parameterized hypergraph basis problem is the following: Given a hypergraph $H$ and $k \in \mathbb{N}$ as an input ($k$ is also the parameter), decide whether $H$ has a basis of cardinality $k$.

The task is to show that this problem is fpt. For this, note that if $|E| \> 2^k$, it follows immediately that we have a no-instance. If $|E| \leq 2^k$, we may assume that every vertex appears in at least one edge, otherwise we delete it. Therefore the number of vertices is bound by $2^k$ too. Now we are able to brute-force through the number $k$-element subsets of $\mathcal{P}(V) = \\{ V' \subseteq V \\}$ and test if this is a basis of $H$. This has running time $ O \left( { 2^{2^k} \choose k } \cdot |E| \cdot 2^k \right) $, which is quite bad, but it is fpt.

**Edit:** I recognized that this is not correct. You cannot bound the number of vertices like this as the hypergraph may *not* be uniform.

Is there a better solution? I found nothing alike in a quick google search.

# Answer
Let's call two vertices $x,y\in V$ *equivalent*, if they aren't discerned by any hyperedge: For all $e\in E$ we have $x,y\in e$ or $x,y\not\in e$.

It does not make sense to discern equivalent vertices by basis sets. Thus, when searching for candidate bases, one can constrain oneself to unions of equivalent classes. You have already bounded $|E|$ by $2^k$. There are at most $2^{|E|}$ equivalence classes.
> 1 votes

---
Tags: algorithms, graphs, parameterized-complexity
---


title: Efficient storage of overlapping sets

text:
# Question
Title: Efficient storage of overlapping sets
I have a bag of sets which overlap, and I am looking for an efficient (if possible, optimal) way to leverage that overlap to store those sets with minimal space requirements. For example, consider these two sets:

```
S = {1,2,3,4}
T = {2,3,4,5}

```

An efficient storage solution would somehow make use of the overlap, e.g.

```
X = {2,3,4}
S = {1} + X
T = {5} + X

```

The query pattern I'd need to support is retrieving all the sets that contain a given member (sets would be labelled, so retrieving all the labels). Ideally I'd also like to be able to retrieve the members of any given set (by label) efficiently, but that is not as important.

Is this an instance of a well-known problem? Any pointers towards literature, or a solution, would be much appreciate.

# Answer
I don't think there is any one-size-fits-all answer to this problem. In the worst case, no compression is possible. Which compression algorithm is best is going to depend on the distribution of problem instances that you see in real life. That information is not provided, so the question is not answerable.
> 0 votes

---
Tags: database-theory
---


# Question
Title: P = NP: Doesn't a search generate more information than a check?
I feel like I am understanding P ≠ NP fairly well, but there is one issue I feel like I am missing. It seems like a search for an answer generates information that a check does not.

Is this a correct way of looking at it, and if so, how does that not already imply that P ≠ NP?

**Example for Clarification** Let's take the wedding table example problem. We have a very large table for our wedding and a large number of guests. Each guest has a list of preferences about all the other guests. For any guest, there are some other guests they are willing to sit beside and others they will not.

In this case, it is easy to check that a solution works, but very hard to find a solution.

Here is where my understanding breaks down. It seems like, unless we can prove that the problem has only one outcome, a successful check of a solution provided to us merely tells us that the proffered outcome succeeds. By contrast, a search tells us that every outcome that was checked and rejected does not succeed. That is, the search gives us extra information.

Another example I have seen is a search that finds the first number that violates the Goldbach Conjecture (provided one exists). A solution offered to us could be checked far quicker than said solution could be located via an algorithm, and yet the fact that this number violates the conjecture does **not** tell us it is the first such number that does so. The search, however, **can** determine if this is true.

In terms of information theory, this also suggests to me that there might be an issue with Kolmogorov Complexity in some respects. If a shorter description of an object tells us everything we need to know to identify it, and yet the identity of that object remains indiscernible to us from many other candidates until we generate a boatload of new information using the search, it seems to me that the shorter description is not equivalent with the object (that it has less information). Rather, for them to be equivalent, we'd have to include the information generated by all the checks, which would then make the search algorithm longer than a code that simply types the number out.

Or: if you can have a description of an object, but you can still be surprised by said object's identity, then the two (description and identity) are not equivalent. However, I fear I may be missing something essential here, hence the question.

# Answer
> 1 votes
What you describe is one of the reason some people tend to think that $\mathsf{P}$ indeed is different than $\mathsf{NP}$. However, you suppose here that checking all possibilities is the only way to solve a problem, which it is not necessarily.

As an example, consider primality testing. One of the naive way to find if an integer $n$ is a prime or not is to test all number lesser or equals than $\sqrt{n}$ and to see if one of them is a divisor of $n$. That would result in a $\Theta(\sqrt{n})$ algorithm in the worst case (when $n$ is prime), which is exponential in the memory size of $n$.

The AKS algorithm however, can decide if a number is a prime without testing all divisors, in time $\mathcal{O}((\log n)^6)$. That was the proof that primality testing is in $\mathsf{P}$.

I can give other examples:

* the example you gave looks like a matching problem. It is well-known that 3D matching is $\mathsf{NP}$-complete, however 2D matching is solvable in polynomial time, without checking all possible matchings ;
* 3SAT is $\mathsf{NP}$-complete, but 2SAT is in $\mathsf{P}$, and can be solved in polynomial time without checking all truth assignments.

The important thing, here, is that in the general case, we don't know if checking all possibilities is the only way to deterministically solve a problem. That's why the $\mathsf{P}\neq \mathsf{NP}$ conjecture is so hard to crack.

---
Tags: p-vs-np
---


# Question
Title: Modified set cover to identify "orthogonal" partitions
**Setup**

I have a non-empty set of elements $U$ that are arranged spatially.

I would like to partition $U$ into $N$ non-empty, disjoint subsets, $A\_i$, having up to $M$ elements each. Each subset is only allowed to contain neighboring elements.

I would like to also partition $U$ into $N$ non-empty, disjoint subsets, $B\_j$, having up to $M$ elements each. Each subset is only allowed to contain neighboring elements.

Finally, I'd like to require that for every subset $A\_i$, and $B\_j$ that $\lvert A\_i \cap B\_j \rvert = 1$.

**Concrete example**

Consider a 3 x 3 grid of elements. The first partition would consist of one subset for each row. The second partition would consist of one subset for each column. Every element would then only exist in exactly one subset of each partition.

This is of course not the only solution. One could have a partition consisting of the upper left three elements, antidiagonal elements and lower-right three elements. The second partition would then consist of the top right three elements, diagonal elements, and lower left three elements.

**My goal**

1. I would like to identify a process where I provide the set $U$ and parameter $M$ and the first and second partitions are produced.
2. As a modification to that first goal, to find an optimal partition that minimizes the aggregate distance between elements within all subsets.

My intuition is that this is a variant of set cover, and could be modeled via ILP, but I want to open this up to get other opinions on how to approach this.

**Clarifications**

1. What do you mean by "Each subset is only allowed to contain neighboring elements"?

Every element in the subset is within a fixed distance of at least one other element in the subset. Assume some distance metric to measure distance.

2. What do you mean by "the aggregate distance between elements within all subsets"?

Given the elements in a subset, construct a weighted complete graph. Each edge has weight equal to the distance between the elements. Find the minimum spanning tree. Take the sum of the edges. Call that $d(S)$.

Goal is to minimize $\sum\_i d(A\_i) + \sum\_j d(B\_j)$

# Answer
For part 1, another approach is to use a SAT solver. This might be slightly faster than an ILP solver.

Let the boolean variable $a\_{v,i}$ be true if $v \in A\_i$, and $a\_{v,i}$ be true if $v \in B\_i$. Then you obtain some constraints (CNF clauses) as follows:

* The $A\_i$'s form a partition: $\neg a\_{v,i} \lor \neg a\_{v,j}$ for all $i\ne j$, $\lor\_i a\_{v,i}$ for all $v$. Do the same for the $B\_i$'s. (Or see Encoding 1-out-of-n constraint for SAT solvers for more compact encodings.)
* Only neighboring elements: $\neg a\_{v,i} \lor \neg a\_{w,i}$ for all $v,w$ that aren't neighboring. Same for the $b$'s.
* Limited size: use an "at most $M$" constraint to ensure that, for each $i$, at most $M$ of $a\_{v,i}$ are true. See Reduce the following problem to SAT.
* Overlap: for each pair $i,j$, we have $\lor\_v (a\_{v,i} \land b\_{v,j})$, and we also have $\neg a\_{v,i} \lor \neg a\_{w,i} \lor \neg b\_{v,j} \lor \neg b\_{w,j}$ for all $v \ne w$. (Or see Encoding 1-out-of-n constraint for SAT solvers for more compact encodings.)

If you use Z3, many of these can be expressed more effectively using pseudo-boolean constraints.

Solving your part 2 with a SAT solver looks messy, so for part 2, ILP looks like a better fit.
> 0 votes

---
Tags: integer-programming, set-cover
---


# Question
Title: Compare and find the best match from multiple lists
Lets say I have n lists from different sources, each contains m possible location of the user. I need to choose the most probable prediction of the user location. My idea was to pick one location from each source that so that those n locations are closest to each other. The average of those n locations will be my estimated user location.

My approach so far was to find every combination of n locations of those lists, and choose the smallest cluster. This works however for each prediction I have to iterate m^n times for all the possible combinations. The time complexity becomes too high if i have many sources with many possible locations. Is there a way to achieve what I wanted without iterating through every single combination or is there any other algorithms that does the similar thing even at the cost of reduced accuracy? Any help would be appreciated.

# Answer
I don't know whether there is a polynomial-time algorithm for this problem that always gives the optimal solution. Below I show a candidate heuristic that might be useful in some settings. For notation, let $L\[i,j\]$ be the location of the $j$th source in the $i$th list.

* Initialize a queue $Q$ with all of the $L\[i,j\]$ locations.
* Repeat until $Q$ is empty:

+ Pop the first element of $Q$, and call it $\ell$.
    + For each $i$, let $\ell\_i$ be the $L\[i,j\]$ that is nearest to $\ell$ (where $j$ ranges over all $m$ possibilities).
    + Let $\hat{\ell}$ be the average of the $\ell\_i$'s.
    + Measure the "goodness" of $\hat{\ell}$ according your objective function (e.g., $\sum\_i \\|\hat{\ell}-\ell\_i\\|\_2^2$, or whatever objective function you use).
    + If $\hat{\ell}$ is better than anything seen so far, remember it.
    + If $\hat{\ell}$ has not been previously added to $Q$, append $\hat{\ell}$ to $Q$.
* Output the best location seen during this process.

If you want to spend more computation time in exchange for the possibility of finding more accurate solutions, at initialization you could also add all averages of all pairs of locations from $L$.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Does a language have the same time complexity as its complement language?
If $L ⊆ \\{0, 1\\}^\*$ is a language, then we denote by $ \overline{L}$ the complement of $L$

For example, the definition of $coNP$ is $coNP =\\{L | \overline{L} \in NP\\}$

The complement of $SAT$ language is $\overline{SAT} = \\{\phi | \phi$ is not satisfiable$\\}$

Of course, there are other $P$ languages

What I want to ask is，Does a language have the same time complexity as its complement language?

# Answer
Yes. Consider decidable language $L$ and its complement $\bar L$. Note that the decidability of $L$ implies the decidability of $\bar L$. Thus, there exists a TM $D$ that can decide $L$ in $\text{TIME}(f(n))$. Similarly, there exists a TM $D'$ that can decide $\bar L$ in $\text{TIME}(g(n))$. We now consider three cases:

1. $f(n) \text{ is } \Omega(g(n))$

We then construct a more efficient TM $D\_L$ such that

$$ \forall x \in \\{0, 1\\}^\*. D\_L(x) = \overline {D'(x)}$$

That is, $D\_L$ simulates $D'$ on input $x$ and flips the answer. Then $D\_L$ decides $L$ in $\text{TIME}(g(n))$

2. $g(n) \text{ is } \Omega(f(n))$

We then construct a more efficient TM $D\_{\bar L}$ such that

$$ \forall x \in \\{0, 1\\}^\*. D\_{\bar L}(x) = \overline {D(x)}$$

That is, $D\_{\bar L}$ simulates $D$ on input $x$ and flips the answer. Then $D\_{\bar L}$ decides $\bar L$ in $\text{TIME}(f(n))$.

3. $f(n) \text { is } \Theta(g(n))$

$D$ and $D'$ decide $L$ and $\bar L$ respectively in the same time asymptotically (i.e. $\text{TIME}(f(n)) = \text{TIME}(g(n))$).

Thus, both $L$ and $\bar L$ can always be decided in the same time asymptotically.
> 0 votes

---
Tags: complexity-theory, time-complexity, np, co-np
---


# Question
Title: Maximal Profit of 'legal' cutting of a board
I'm facing this problem for some time now, I've tried a greedy approach yet I result to trying a DP-ish approach, only to get stuck at a standstill.

Given a board of length $n$, and an increasing monotonic "price" function $p:\mathbb{N}\rightarrow\mathbb{R}^+ $, an acceptable partition (Notated by $X=\\{x\_1,x\_2,\ldots x\_m\\}$) of the board to $m\leq n$ pieces is defined by: $$ x\_1, x\_2, \ldots x\_m \in \mathbb{N}^+ $$ $$ \sum^{m}\_{i=1}x\_i=n $$ the profit of an acceptable partition is defined to be the sum:$$\sum^{m}\_{i=1}p(x\_i)$$

The problem asks to describe an efficient algorithm to find an acceptable partition which produces the maxiaml profit, out of all acceptable cuts.

I've tried to apply the solution to the "Woodcutter's problem" to this situation, yet the "Woodcutter's Problem" doesnt apply when a price/profit function is introduced.

# Answer
> 2 votes
This problem is known as the "rod cutting problem". See, e.g., here.

Let $OPT\[i\]$ denote the maximum profit that can be attained by partitioning a board of length $i$ (according to $p$).

Then $OPT\[0\] = 0$ since the only acceptable partition has $m=0$. For $i = 1, \dots, n$: $$ OPT\[i\] = \max\_{j=1, \dots, i} \left( p(j) + OPT\[i-j\] \right). $$

The optimal profit is then in $OPT\[n\]$. The partition itself can be reconstructed by retracing the dynamic programming choices that led to the value in $OPT\[n\]$.

---
Tags: dynamic-programming, greedy-algorithms, partitions, maximum-subarray
---


# Question
Title: Nesting algorithm for rectangular-based, fixed-orientation polygons
I'm looking for an algorithm that is closely related to the 2-dimensional nesting problem (also known as lay planning, bin packing, and the cutting stock problem).

The main differences between this and normal nesting are:

* A fixed number of elements to be placed
* The elements cannot rotate
* The elements must be placed in as *small* an area as possible, as opposed to placing as *many* pieces as possible in a fixed-size area.
* The elements are rectangular pieces with 0-4 fixed-orientation rectangular corner cutouts (“Utah-like”), as opposed to being randomly shaped

**Input:** *`n`* “Utah-like”, fixed-orientation polygons. *`n`* is in the range 1-20. The figures are *not* shaped to align perfectly with each other. Example figure set:

**Desired output:** A fixed-orientation nesting for a scaleable area with predefined proportions. The scaleable area should be scaled to fit the nested figures as snugly as possible, like so:

Note the area where the figures' rectangular boundaries overlap, preventing this from being a more trivial rectangle-packing problem.

I have perused several packing questions on SE (e.g. , , ) as well as puzzle-solving questions (e.g. , , ), and also outside Stack Exchange (, , ), but they don't describe this particular problem or don't include source code. Related GitHub repos: , , . Online solvers: SVGnest.com and Nestable.xyz.

# Answer
I will describe how you can solve this with an ILP (integer linear programming) solver. For the size of problem you have, I expect it will work acceptably well.

Let's focus on just two of your shapes, say shape $S\_i$ and $S\_j$. Let $(x\_i,y\_i)$ denote the position of some fixed point of $S\_i$ (say, the lower-left corner), and $(x\_j,y\_j)$ the position of some fixed point of $S\_j$. Then it is possible to write down a formula $\Phi\_{i,j}$ that captures the condition that $S\_i,S\_j$ do not overlap. This formula will have the form

$$(x\_j-x\_i \ge \alpha\_1 \land y\_j-y\_i \ge \beta\_1) \lor \cdots (x\_j-x\_i \ge \alpha\_k \land y\_j-y\_i \ge \beta\_k),$$

except that some $\ge$'s might be replaced with $\le$. Here the $\alpha,\beta$ values are constants that can be easily calculated from the shapes $S\_i,S\_j$. We can express $\Phi\_{i,j}$ in a form suitable for use with an ILP solver using the methods in Express boolean logic operations in zero-one integer linear programming (ILP). In particular, we can encode $\Phi\_{i,j}$ as the linear inequalities

$$\begin{align\*} x\_j-x\_i &\ge \alpha\_1 - C(1-t\_1)\\ y\_j-y\_i &\ge \beta\_1 - C(1-t\_1)\\ &\vdots\\ x\_j-x\_i &\ge \alpha\_k - C(1-t\_k)\\ y\_j-y\_i &\ge \beta\_k - C(1-t\_k)\\ t\_1 + \cdots + t\_k &\ge 1 \end{align\*}$$

except that whenever you replace $\ge$ with $\le$, you also replace $-C(1-t\_u)$ with $+C(1-t\_u)$. Here, $t\_1,\dots,t\_k$ are fresh new variables that are specific to $\Phi\_{i,j}$, and they are constrained to be integers and constrained to be 0 or 1 (via the inequalities $0 \le t\_1 \le 1$, etc.) Also $C$ is a large constant.

Finally, introduce a variable $z$, which represents the width of the containing rectangle. The containing rectangle's height will be $\gamma z$ where $\gamma$ is a known constant (the aspect ratio).

Add constraints to ensure that all shapes fit within the rectangle $\[0,z\] \times \[0,\gamma z\]$. In particular, for shape $S\_i$, we obtain inequalities on $x\_i,y\_i$ (something like $0 \le x\_i \le z-\text{width}(S\_i)$, $0 \le y\_i \le \gamma z - \text{height}(S\_i)$ if $(x\_i,y\_i)$ is the lower-left corner of $S\_i$, but the exact inequalities may vary depending on which fixed point of $S\_i$ you chose).

Add the linear inequalities for each $\Phi\_{i,j}$, for every pair $i,j$ with $i\ne j$.

The objective function is to minimize $z \ge 0$.

Finally, solve the resulting ILP instance obtained in this way. This should give you an optimal nesting.
> 3 votes

---
Tags: linear-programming, packing
---


title: Checking if Schedule is recoverable

text:
# Question
Title: Checking if Schedule is recoverable
Consider the following schedule S.Is S conflict–serializable? Append the commit operations of these transactions at the end of the schedule in an appropriate order such that S is recoverable. How many such orders are there?

$$S: r1(X); r2(Z); r1(Z); r3(X); r3(Y); w1(X); w3(y); r2(Y); w2(Z); w2(Y);$$

I have already found the whether S is conflict serializable or not by using precedence graph(it is indeed conflict serializable!!). Now coming to the whether the S is recoverable or not. Here's what I got: For T1 to commit it has to wait for T2 to commit (r1(Z) and w2(Z)) For T2 to commit it has to wait for T3 to commit (r2(Y) and w3(Y)) For T3 to commit it has to wait for T1 to commit (r3(X) and w1(X)) So no transaction can commit , it is like a deadlock. So it this schedule irrecovearable.Am I correct. In general is there any way to check for recoverability . Thank you.

# Answer
A schedule is said to be irrecoverable if it has a Dirty read, and the commits are not in order of the dirty reads. There is one dirty read $w3(Y); r2(Y)$. So the order of commits should be where $T(3)$ commits before $T(2)$, giving 3 commit orders $$T(1);T(3);T(2);$$ $$T(3);T(1);T(2);$$ $$T(3);T(2);T(1);$$
> 0 votes

---
Tags: database-theory, database-concurrency
---


title: Proof: CFG has balanced parentheses

text:
# Question
Title: Proof: CFG has balanced parentheses
I'm currently enrolled to a CS course about programming languages and we learned about structural induction. In a question from our home assignments we need to proof that the following CFG has balanced parentheses:

My initial solution used simple induction and following the derivation rules of the CFG but the TA told us we need a stronger induction assumption that R has one more left parentheses than right parentheses. Can someone give me general direction to follow?

# Answer
I'm assuming that the axiom is $E2$. By substituting $R$ in $E2$ you get the equivalent grammar: $$ E2 \to \varepsilon \mid \text{id} \mid () \mid (E2) $$

You can show by induction on the number $i$ of productions used that every sentential form of the above grammar has balanced parentheses.

The base case is $i=0$ and is trivial since $E2$ has no parentheses. For the inductive step notice that the only possible production replaces a single occurrence $E2$ with a sequence of symbols that has balanced parentheses. Therefore the resulting sentential form also has balanced parentheses.
> 1 votes

# Answer
We perform the induction on derivation steps. Let's say that our derivation of some sentence in $L(E2)$ is composed of $k$ steps, the first step is denoted as $V \xrightarrow{k} \alpha$, the second step (if $k \>= 2$) will be $ \alpha \xrightarrow{k-1} \beta$, and so on. I'll be assuming that the starting symbol is $E2$

It's trivial that $E2 \xrightarrow{1} id | \epsilon $ lead to balanced parentheses. Also $E2 \xrightarrow{2} (R \xrightarrow{1} () $ is well balanced

So now we perform the inductive step for $k \> 2$, with induction hypothesis that $E2 \xrightarrow{h} \cdots \xrightarrow{1} \alpha$ has well balanced parentheses for $h \< k $. We must have the derivation steps $E2 \xrightarrow{k} (R \xrightarrow{k-1} (E2) \xrightarrow{k-2} \cdots \xrightarrow{1} (\alpha)$, where $\alpha$ will have balanced parantheses by induction hypothesis
> 0 votes

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


# Question
Title: "Largest set" in coinductive definitions
In several explanations of coinductive definitions (for example, in the answers to What is coinduction?), we're told that while an inductive definition gives us the smallest set with a specified set of properties (the constructors), coinduction gives us the *largest* set such with a specified set of properties (the destructors).

I'm having trouble understanding this because the notion of "largest set" doesn't seem like it should be well-defined. Clearly I'm thinking about this wrongly, but it would be helpful to know what my mistake is.

As a simple example that I've picked up from a few introductions, let's consider infinite streams over some alphabet $\Sigma$. We consider some set $\mathcal{E}$, such that if an element of $\mathcal{E}$ is of the form $\sigma{:}s$ for $\sigma\in\Sigma$, then $s\in \mathcal{E}$.

This makes some intuitive sense, even though it's a bit informal. (What does it mean for an element of an arbitrary set to "be of the form" $\sigma{:}s$?) But then the next part of the story is that we want the *largest* set $\mathcal{E}$ such that this is the case.

Here's my problem: surely the set $\Sigma^\infty$ of infinite streams does obey the specified property. But then surely so do other, larger sets such as $\Sigma^\infty\cup \mathbb{R}$. An element of this set is either an infinite stream (hence it's of the form $\sigma{:}s$ and we can conclude $s\in \Sigma^\infty\cup \mathbb{R}$), or it's a real number (in which case it's not of the form $\sigma{:}s$, but that's ok because we never introduced a rule saying it has to be). So it seems I can make the set as big as I want just by adding arbitrary members to it, and $\Sigma^\infty$ isn't actually the biggest set that satisfies the given property at all.

So where's my mistake? How can I think about the "largest set" in this context in a way where it's actually well-defined?

Note: I know that coinductive definitions can be formalised as final coalgebras of polynomial functors on $\mathbf{Set}$, and I actually understand that reasonably well. But I'm coauthoring a paper aimed at an audience who won't know anything about that, so my aim is to understand the more informal motivation for coinductive definitions, so that I can explain to the reader what's going on without requiring a lot of technical background. It would be quite helpful for me to know how this informal idea of "largest set" relates to the more formal notion of a terminal coalgebra.

# Answer
> 1 votes
Here is a tentative self-answer.

I think it must just be that there is an additional requirement that wasn't mentioned in the tutorials I read, namely that one of the destructors must apply to each element of the set.

So in the case of infinite streams we are looking at a set $\mathcal{E}$ such that

* *every* member of $\mathcal{E}$ is of the form $\sigma{:}s$ for some $\sigma$, *and* $s\in \mathcal{E}$.

When we ask for the largest set of this form it makes sense. (At least it does intuitively - it still seems a bit formally iffy to me, but it's hard to put my finger on why.)

It then becomes much more clear how this relates to the terminal coalgebra idea. A set where every member is of the form $\sigma{:}s$ can be modelled as a set $\mathcal{E}$ equipped with a function $\operatorname{decompose}\colon \mathcal{E}\to \mathcal{\Sigma}\times\mathcal{E}$, which we think of as splitting a stream up into its head and tail. If we think of this as a coalgebra of $\Sigma\times{-}$ then when we ask for a "larger set", we're asking for a new pair $(\mathcal{E}',\operatorname{decompose}')$ and a monomorphism $m\colon \mathcal{E}\to\mathcal{E}'$ such that $m$ is a coalgebra homomorphism. So then it's not so hard to imagine that the notions of "largest set" and "final coalgebra" are the same.

# Answer
> 1 votes
I think the precise definition of a final coalgebra might help.

Fix a set of symbols $\Sigma$. For any set $X$ define $F(X) = \Sigma \times X$, and for any $f : X \to Y$ let $F(f) : F(X) \to F(Y)$ be the map $(s, x) \mapsto (s, f(x))$. Then $F : \mathsf{Set} \to \mathsf{Set}$ is a functor.

An **$F$-coaglebra** is a pair $(A, a)$ where $A$ is a set and $a : A \to F(A)$ is a map, called the **structure map**. Such a structure map is equivalent to having two maps $\mathsf{hd}\_a : A \to \Sigma$ and $\mathsf{tl}\_a : A \to A$, commonly called the *head* and the *tail* operations. The relationship with with $a$ is characterized by $a(x) = (\mathsf{hd}\_a(x), \mathsf{tl}\_a(x))$.

A **homomorphism** of $F$-coalgebras $h : (A, a) \to (B, b)$ is a map $h : A \to B$ between their underlying sets that respects the structure maps: for all $x \in A$ we require $\mathsf{hd}\_b(h(x)) = \mathsf{hd}\_a(x)$ and $\mathsf{tl}\_b(h(x)) = h(\mathsf{tl}\_a(x))$.

$F$-coalgebras and homomorphisms form a category. A terminal object in this category is the **terminal $F$-coalgebra**. Concretely, it is an $F$-coalgebra $(E, e)$ such that for any coalgebra $(A, a)$ there is a unique homomorphism $h : A \to E$.

Let us show that $E = \Sigma^\omega$ with $e(s\_0s\_1s\_2s\_3\cdots) = (s\_0, s\_1s\_2s\_3\cdots)$ is a final $F$-coalgebra. For an arbitrary $A$, there is a unique map $h : A \to E$ satisfying $h(x) = (\mathsf{hd}\_a(x), h(\mathsf{tl}\_a(x))$ for all $x \in A$. It is easy to verify that this is the only one.

The unique homomorphism $h : A \to E$ need not be injective. For example, take $A = \Sigma \times \\{0,1\\}$ and let $a : A \to F(A)$ be $a(s, d) = (s, (s, d))$. Then $h(s,0) = h(s, 1)$ as they are both the infinite sequence of $s$'s. It is therefore somewhat imprecise to call $E$ the “largest” $F$-coalgebra – which is why officially it is called the “terminal” one. But it is helpful to think of it as being “large” in the sense that every other $F$-coalgebra maps into it.

---
Tags: logic, proof-techniques, formal-methods, coinduction
---


# Question
Title: Show that the decision version of the Traveling Salesman problem is in NP
*Given a graph G = (V, E) with edge lengths c : E → R, and a number d ∈ R, is there a Hamilton cycle of length l ≤ d in G? Show that the Travelling-Salesman problem is contained in the complexity class NP.*

I am somewhat struggling with this exercise because I have little problem understanding the formality. I know that we need to show that there is a polynomial algorithm which verifies a given solution which we refer to as "certificate". But what exactly is the certificate here? Is it a given path (which would be easy to verify since you only have to check whether the nodes are adjacent and the costs are ≤ d) or is it just d and we have to check whether there exists a path ≤ d? But the latter is not verifiable in polynomial time as it is requires n!.

# Answer
> 1 votes
TSP can be expressed as a decision problem and an optimisation problem.

Here, as you said, a solution to the optimisation problem can be seen as a certificate to the decision problem: if you are given a certain path in $G$, you can verify in polynomial time that:

1. it is a Hamiltonian cycle;
2. its weight is lesser or equal to $d$.

That's enough to prove that TSP $\in\mathsf{NP}$.

# Answer
> 1 votes
Definition of an NP problem: An NP problem is a decision problem, which means for every instance there is an answer, either “Yes” or No”. For each yes-instance there is a polynomial size correct certificate. And there is a program which given an instance and a certificate will tell you in polynomial time “Yes” if given a yes-instance and a correct certificate, and “don’t know” if it is a yes-instance with an incorrect certificate, or a no-instance.

It’s up to the person trying to prove that a problem is in NP to define what the certificate would be. For example for the travelling salesman decision problem the order in which to visit nodes seems a good choice for a certificate.

(What would be an incorrect certificate? For example an order to visit nodes in, with total distance more than required).

For TSP, the problem is “is there a tour with length \<= K”. The similar problem “Does the shortest tour have length exactly K” will have problems defining and finding a certificate.

---
Tags: traveling-salesman
---


# Question
Title: Time complexity of finding the minimum by dynamic programing
How can I calculate the complexity of computing $MD(b)$, where $b=(b\_1,b\_2,\dots,b\_n)$?

$$MD(s) = \max(s)-\min(s) + \min(MD(s\setminus\\{\max(s)\\}), MD(s\setminus\\{\min(s)\\}))$$ where $s$ is a finite multi-set of numbers with base case $$MD(\text{one element})=0.$$

Thoughts: I think the time complexity is $O(n^2) $ because we need linear time to calculate the maximum and minimum of each $s$ and we have to do that $n$ times So, $n+ (n-1)+ (n-2) + \dots = O(n^2)$

# Answer
> 0 votes
No, the time complexity is not $O(n^2)$.

Assume all elements in the given $b$ are different. Then the number of different multi-sets that appear on the left-hand side of the recurrence relation you will compute is $\Omega(n^2)$. The average time to find the minimum or the maximum is $\Omega(n)$. Hence the time-complexity of the whole algorithm is $\Omega(n^3)$.

---

What you can do (and you did) is to sort $b$ first, which takes $O(n\log n)$ time. Then it takes $O(1)$ time to locate the minimum and the maximum.

There are $O(n^2)$ $MD(c)$'s that the algorithm will compute. More specifically, each sequence of consecutively ordered elements of $b$ will appear as $c$. Such an sequence is determined by the starting element and the ending element. There are $n(n+1)/2$ of them.

* Each base case of one-element sequence takes $O(1)$ to set up.
* Thanks to the recurrence relation and and caching, it also takes $O(1)$ time to compute and store each non-base entry.

It takes $O(n^2)$ time to compute all entries. Since the entry $MD(b)$ is the wanted, the time complexity is $O(n^2)$.

# Answer
> 1 votes
If done recursively by brute force, the computation follows the recurrence

$$T(n)=2n+2T(n-1),$$ assuming that the cost of a $\min$ or $\max$ is $n$. The solution of this recurrence is exponential $O(2^n)$.

But if you look closer, you only apply the function $MD$ to $\dfrac{n(n+1)}2$ different subsets, namely those corresponding to all subsequences of the sorted sequence. So I assume that you can solve in time $O(n^2)$, after sorting and using memoization, or using a bottom-up procedure.

---
Tags: time-complexity, optimization, dynamic-programming, polynomial-time
---


# Question
Title: How $N$ qubits correspond to $2^N$ bits?
I read everywhere that $N$ qubits correspond to $2^N$ bits. Let's start with 1 qubit, which is commonly represented by $\alpha |0\rangle + \beta |1\rangle$ where alpha and beta are complex numbers. This looks to me like infinite bits. How do they choose alpha and beta so that it becomes 2 bits?

Edit: Why is it commonly said that $N$ qubits correspond to $2^N$ bits?

# Answer
Despite what badly written pop-science explanations of quantum computation may tell you, a qubit is *not* two classical bits and $N$ qubits is *not* $2^N$ bits. Qubits are fundamentally different from bits, pairs of bits or anything else (except for a representation of $\alpha$ and $\beta$ in binary to precision sufficient to classically simulate the computation to whatever precision is required).

As for *why* people talk about $N$ qubits being equivalent to $2^N$ bits, it's hard to say. To paraphrase Tolstoy, all correct explanations are alike but all incorrect explanations are incorrect in their own particular way. Perhaps it comes from the widespread mistaken belief that quantum computers somehow try all the options in parallel; perhaps it's a mistranslation of the fact that quantum computers offer exponential speedup over some classical algorithms. Scott Aaronson has some thoughts along these lines:

> Fueling the belief that countless more quantum algorithms should exist (or that are not finding them is a failure), seems to be the idea that a quantum computer could just “try every possible answer in parallel”.
>
> But we’ve understood since the early 90s that that’s not how quantum algorithms work! You need to choreograph an interference pattern, where the unwanted paths cancel
>
> The miracle, I’d say, is that this trick yields a speedup for any classical problems, not that it doesn’t work for more of them
> 6 votes

# Answer
You can think of $ \lvert 0 \rangle $ or $ \lvert 1 \rangle $ as the standard basis of $ \mathbb{C}^2 $. In this sense, a single qubit $ \lvert \psi \rangle $ is nothing more than a unit vector in $ \mathbb{C}^2 $, that is, a linear combination of $ \lvert 0 \rangle $ and $ \lvert 1 \rangle $ with length $1$. Now, a $N$ qubit is an element of $ \mathbb{C}^{2^N} $ since it is defined via the tensor product of single qubits. Maybe that is where (the absurdity) "$N$ qubits correspond to $2^N$ bits" comes from.
> 1 votes

---
Tags: computation-models, quantum-computing
---


# Question
Title: Prove that $L = \{ \langle M \rangle | \text{ M is a PDA, L(M) contains at least 1 string w that } |w| \leq n \}$ is recursive?
## Description

Similar to the encoding of a Turing Machine, we can encode a Push-Down Automata. Denote $\langle M \rangle$ as the encoding of PDA M, and a natural number n, is language $L = \\{ \langle M \rangle | \text{ M is a PDA, L(M) contains at least 1 string w that } |w| \leq n \\}$ a recursive language?

## Question

By the definition of a recursive language, I have to prove that there exists a Turing Machine that can accept L and for any input string x, the TM will end up in a halt state.

But how exactly should I do to find/construct that? Or I don’t really have to construct a Turing Machine but use some existing theorem?

# Answer
You should think in algorithms instead of thinking in Turing Machine. Turing Machines are just a very formal way to express algorithms but writing a Turing Machine even for simple algorithms is a chore.

It suffices to know that if one really wanted to, they could construct a very complicated Turing Machine to encode an algorithm.

What the question is really asking is "Is there an algorithm that, given a PDA $M$ and an integer $n$, decides if $L(M) \cap \Sigma^{\leqslant n}\neq \emptyset$?".
> 0 votes

---
Tags: turing-machines, computability, automata, decidability
---


# Question
Title: The set of possible values of linear programs
Consider the set of all linear programs of the form:

maximize $c x$

subject to $A x \leq b$

$x \geq 0$

where there are $m$ variables, $n$ constraints, and all coefficients in $A, b, c$ are integers from a given finite set $K$.

Since the number of such programs is finite, the number of possible optimal values of these programs (those that have an optimal value, that is, are feasible and bounded) is finite.

My questions are:

* Is there any non-trivial upper bound on the number of possible optimal values? (besides the number of possible programs).
* Is there any simple representation for the set of all possible optimal values, as a function of $m, n$ and $K$?

# Answer
> 2 votes
For simplicity, assume $0 \in K$. It allows us to treat $x \geq 0$ constraints in the same way as other constraints. For an LP that has an optimal solution, there is an optimal solution in the basis. Therefore, it is sufficient to consider the set of possible solutions for systems of $m$ non-singular linear equations on $m$ variables.

By Cramer's rule, a solution of a system of linear equations $Ax = b$ can be represented by ratios of determinants $x\_i = \frac{\det(A\_i)}{\det(A)}$. Therefore, an optimal value of an LP can be represented by a ratio $\frac{\sum\_i c\_i \det(A\_i)}{\det(A)}$.

If the maximum absolute value of the coefficients is small, say $k$, we can use Hadamard's theorem. The absolute value of the denominator is at most $\det(A)$ is $k^m m^{m/2}$. Similarly, the numerator has an absolute value at most $mk \cdot k^m m^{m/2}$. Because both the numerator and the denominator are integers, the number of possible values is $O(k^{2m+1} m^{m+1})$.

---
Tags: linear-programming
---


# Question
Title: What are the guidelines/tips for calculating the complexity of a chained-recursive function?
Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions..

Are there any tips or general guidelines for calculating the complexity (time/space) for functions of the following form?

```
int f1(int n)
{
    if(n < k) // for an arbitrary k
        return 1;
    return f1(f1(n/2) + f1(n/3) - f1(n/5));
}

```

Or:

```
int f2(int n)
{
    if(n < k)
        return k;
    return f2(g(n/k));
}

int g(int n)
{
    // Some code of known complexity here to calculate an arbitrary c
    return f2(n/c);
}

```

Specifically, recursive functions that call themselves with their own return value as a parameter (e.g func(func(value)); )

Thank you in advance for any assistance provided.

# Answer
I cant think of one simply way to solve such questions, but I can show you a way to start tackling the questions and making them simpler.

In such cases, that $f$ recursively calls itself with their own return value, the running time of $f$ might depend heavily on its output. So contrary to usual complexity computation tricks, here we *want* to know precisely what the output of $f$ is. For example, we can prove by induction that `f1` will always output 1.

Now, replace each inner recursive call to $f$ with the value it returns. In the `f1` case, we replace `f1(f1(n/2) + f1(n/3) - f1(n/5))` by `f1(1+1-1)` which is simplified to `f1(1)`. This means that we did a total of 4 calls to $f$, and for each call to $f$ we know exactly what the input was. Here, in this example, the inputs are $n/2,n/3,n/5,1$.

Finally, we can start calculating the time complexity: since we know how many recursive calls happened and what input was there for each recursive call, we can build a recursive formula for the time complexity. In the case of `f1`, it will be: $T(n)=T(n/2)+T(n/3)+T(n/5)+T(1)+c$, since we add a recursive call with the input of `f1` for each time `f1` was invoked.

This can be solved using traditional techniques, such as the master theorem.
> 0 votes

# Answer
For your $f\_1$, you need to solve the recurrence

$$T(n)=\begin{cases}n\<k\to T(1)\\n\ge k\to T(f\_1(\frac n2) + f\_1(\frac n3) - f\_1(\frac n5))+T(\frac n2)+T(\frac n3)+T(\frac n5).\end{cases}$$

This mandates the resolution of the recurrence on $f\_1$ itself, probably not the easiest thing.

---

Your second example is contrived. "$\frac nc$ for some code" could just be written $g(n)$, and $$n\ge k\to T(n)=T(g(n))+U(n)+c$$ where $U$ is the "known complexity".

---

**Update:**

As shown by others, one can check that $f\_1(n)=1$ for all $n$. So the recursion simplifies to

$$T(n)=\begin{cases}n\<k\to T(1)\\n\ge k\to T(1)+T(\frac n2)+T(\frac n3)+T(\frac n5).\end{cases}$$
> 0 votes

# Answer
If k ≤ 1 then we are stuck; there will be infinite recursion unless the input is n = 0 for k = 0.

Otherwise: The result is 1 if $n \< k \cdot 2^m$, for every m ≥ 0. Proof by induction: It is obviously true if m = 0. Assume it is true for all m' ≤ m: Let $n \< k \cdot 2^{m+1}$. If $n \< k \cdot 2^m$ then the result is 1 by induction. Otherwise we calculate f(n/2), f(n/3), f(n/5), each argument less than $k \cdot 2^m$, so the three results are 1, and the final result is 1.

With the result always being 1, we can try to find the complexity using the master theorem. It will be proportional to $n^{1/2 + 1/3 + 1/5}$ = $n \cdot n^{1/30}$
> 0 votes

---
Tags: time-complexity, algorithm-analysis, asymptotics, recursion, space-complexity
---


# Question
Title: Set intersection using bloom intersection
Let $A \subseteq Z$, where $Z=\\{1,2,3,\cdots,n\\}$. Now given any $B \subseteq Z$, we need to check whether $A \cap B =\varphi$ or not. I am looking for a randomized algorithm.

I am trying to implement it using a bloom filter. Create a bloom filter for $A$ and $B$ respectively. Now consider the intersection of $A$ and $B$ which means AND operation of $A$ and $B$. Assume that there are $n$ elements in both arrays. Then the number of bits required in bloom filters will be $O(n)$ many bits and $O(n/\log n)$ many words. AND operation is going to take $O(n/\log n)$ time

Is there any better (faster runtime) algorithm for the above problem?

# Answer
> 2 votes
Without any special knowledge about the distribution of data, you cannot do better than that. In the worst case, you have to read every element of $B$. There can be $\Theta(n)$ elements of $B$. So, every correct algorithm must take at least $\Omega(n/\log n)$ time in the transdichotomous model, where you can read an entire $O(\log n)$-size word in 1 step.

---
Tags: bloom-filters
---


# Question
Title: Is there an existing similarity measure for comparing sequences similar to this one?
I work with elements that have a representation in two different vector spaces and I would like to compute an indicator of how similar the neighbors of the elements are in these two spaces.

To do so, I start by computing the list of the $n$-nearest neighbors of all elements, then I use a sequence similarity measure that, given two sequences, return a score between 0 and 1.

For now I used :

I would like to use a distance that take neighbors order into account and that gives more weight to firsts neighbors since they are more significant.

I have thought about the following similarity measure that appears to deals with both these properties but I can not find it anywhere so I wonder if someone have heard of such similarity measure :

Given to sequences $ a = (a\_1, a\_2, ..., a\_n)$ and $b = (b\_1, b\_2, ..., b\_n)$ I define the similarity $S(a,b)$ as :

$$S(a,b) = \frac{1}{n}\sum\_{k=1}^{n} \frac{|(\\{a\_i | i \in \[1,k\]\\} \cap \\{b\_i | i \in \[1,k\]\\}|}{k}$$

Some examples :

For $a = b = (1, 2, 3, 4)$ : $$S(a, b) = \frac{1}{4} \times \left( \frac{1}{1} + \frac{2}{2} + \frac{3}{3} + \frac{4}{4}\right) = 1$$

For $a = (1, 2, 3, 4)$ and $b = (9, 8, 7, 6)$ : $$S(a, b) = \frac{1}{4} \times \left( \frac{0}{1} + \frac{0}{2} + \frac{0}{3} + \frac{0}{4}\right) = 0$$

For $a = (1, 2, 3, 4, 5, 6)$ and $b = (2, 1, 4, 3, 6, 5)$ : $$S(a, b) = \frac{1}{6} \times \left( \frac{0}{1} + \frac{2}{2} + \frac{2}{3} + \frac{4}{4} + \frac{4}{5} + \frac{6}{6} \right)$$

Thus :

* if $a = b$, $S(a,b) = 1$
* if $\\{a\_i | i \in \[1,n\]\\} \cap \\{b\_i | i \in \[1,n\]\\} = \emptyset$, $S(a,b) = 0$

Does anyone have heard of such similarity measure between sequences ?

# Answer
> 2 votes
Given two sequences $ a = (a\_1, a\_2, ..., a\_n)$ and $b = (b\_1, b\_2, ..., b\_n)$ you define the similarity $S(a,b)$ as :

$$S (a,b) = \frac{1}{n}\sum\_{k=1}^{n} \frac{|(\\{a\_i | i \in \[1,k\]\\} \cap \\{b\_i | i \in \[1,k\]\\}|}{k}. $$

If instead you had

$$S(a,b) = \frac{1}{n}\sum\_{k=1}^{n} \frac{|(\\{a\_i | i \in \[1,k\]\\} \cap \\{b\_i | i \in \[1,k\]\\}|}{| \\{a\_i | i \in \[1,k\]\\} \cup \\{b\_i | i \in \[1,k\]\\} |}$$ this would be the arithmetic mean of partial *Jaccard distances* on the first $k$ symbols as $k$ varies from $1$ to $n.$

So you chose to normalize by $k$ instead of the union. In some cases people normalize Jaccard by the maximum of the two set sizes, namely $$\max(|(\\{a\_i | i \in \[1,k\]\\}|, |\\{a\_i | i \in \[1,k\]\\}|)$$ but you have chosen to normalize by the maximum possible value of the two set sizes which is $k$ when all symbols in the partial sequence are distinct.

I haven't found anything else at a quick look over the book *Dictionary of Distances* by Deza and Deza.

---
Tags: algorithms
---


# Question
Title: How to select a subset from the array $A=\{\frac{S_1}{K_1},\frac{S_2}{K_2},...,\frac{S_n}{K_n}\}$ such taht the subset can meet this requirement?
Given an array $A=\\{\frac{S\_1}{K\_1},\frac{S\_2}{K\_2},...,\frac{S\_n}{K\_n}\\}$ whose any $S\_i$ and $K\_i$ are positive floating-point, and an positive floating-point $R$, how to select a set of element $C=\\{\frac{S\_{p\_1}}{K\_{p\_1}},\frac{S\_{p\_2}}{K\_{p\_2}},...,\frac{S\_{p\_m}}{K\_{p\_m}}\\}$ such that the absolute value of the difference between $\frac{\sum\_{i=1}^m S\_{p\_i}}{\sum\_{i=1}^m K\_{p\_i}}$ and $R$ (i.e. $|\frac{\sum\_{i=1}^m S\_{p\_i}}{\sum\_{i=1}^m K\_{p\_i}}-R|$)is minimal. The subset $C$ has at least one element.
This problem has confused me for many weeks. I can't even prove whether it is an NP or NP-hard problem. Could anyone give me some ideas on how to address it? I really appreciate any help you can provide.

# Answer
The special case where $K\_1=K\_2=\cdots=K\_n$ is as hard as the subset-sum problem, which is NP-hard -- so your problem is NP-hard as well.

A plausible approach is to use integer linear programming. Let $x\_i$ be a zero-or-one integer variable. You are looking for $x\_i$ such that

$$-\epsilon \sum\_i x\_i K\_i \le \sum\_i x\_i S\_i - R \sum\_i x\_i K\_i \le \epsilon \sum\_i x\_i K\_i.$$

For fixed $\epsilon$, you can test whether there is a solution to this linear inequality using an ILP solver. Then, you can use binary search on $\epsilon$ to find the smallest $\epsilon$ for which a solution exists.
> 0 votes

---
Tags: algorithms
---


# Question
Title: if we have $f(n)=f(n-7)$ and $f(2)=3$ can we conclude that $f(n) \in \theta(1)$?
if we have $f(n)=f(n-7)$ and $f(2)=3$ can we conclude that $f(n) \in \theta(1)$? what if we also have $f(1)=2$?

# Answer
> 0 votes
Since $f(n)=f(n-7)$, $f$ can take at most $7$ different values: $f(0),f(1),f(2),f(3),f(4),f(5)$ and $f(6)$ (the others values are obtained by translation)

So, obviously, $\forall n$, $|f(n)| \leq \max\_{i=0}^6 |f(i)| = C$ and you indeed have $f \in \theta(1)$.

# Answer
> 0 votes
$$f(n)=f(n-7)$$ implies $$f(n)=f(n\bmod7)$$ and the function is periodic, hence perforce $\Theta(1)$, regardless the particular values of $f(n\bmod7)$.

---
Tags: algorithms, data-structures
---


title: Is infinite union of RE a RE?

text:
# Question
Title: Is infinite union of RE a RE?
Is an infinite set of RE languages create a language that is also RE?

I think it's true, and my first intuition is to try induction to prove this statement.

Am I on the right way?

Thanks!

# Answer
The statement is not true; any language $L$ can be written as the (countably infinite) union of singleton languages which each just contain one word of $L$.

Also, even if the statement was true, one could not prove it using (regular) induction. This is because the *finite* union of RE languages is indeed RE. My go-to example here is that one can show using induction that every natural number is finite, but there exists no infinite natural number.
> 4 votes

---
Tags: formal-languages, computability, automata
---


# Question
Title: Probabilty of Elements being smaller than a specific value
Right now i am looking at the following statement, but i cant grasp why it is correct. Can somebody help?
"If we look at F0 uniformly distributed (and, say, pairwise independent) elements of \[0, 1\], we expect about t of them to be smaller than t/F0."

Kind Regards, Ilian

# Answer
Consider defining indicator random variables $X\_1, X\_2, ..., X\_{F\_0}$ such that

$$ X\_i = \begin{cases} 1 \text{ if } x\_i \< \frac{t}{F\_0} \\ 0 \text{ otherwise } \end{cases} $$

Then, we can count the number of elements $\< \frac{t}{F\_0}$ as follows

$$ \[ \text{# of Elements} \< \frac{t}{F\_0} \]= \sum\_{i=1}^{F\_0} X\_i $$

Thus,

$$ \mathbb{E} \[\text{# of Elements} \< \frac{t}{F\_0}\] = \mathbb{E} \[\sum\_{i=1}^{F\_0} X\_i\] \\ = \sum\_{i=1}^{F\_0} \mathbb{E}\[X\_i\] $$

By linearity of expectation. Note that by virtue of $X\_i$'s being indicator random variables, and independently identically distributed, we have that

$$ \mathbb{E}\[X\_i\] = 1 \cdot \mathbb{P}\[X\_i=1\] + 0 \cdot \mathbb{P}\[X\_i=0\] = \frac{t}{F\_0} $$

For all $1 \leq i \leq F\_0$. Substituing, we get that

$$ \mathbb{E} \[\text{# of Elements} \< \frac{t}{F\_0}\] = \sum\_{i=1}^{F\_0} \mathbb{E}\[X\_i\] = \sum\_{i=1}^{F\_0} \frac{t}{F\_0} = t $$
> 1 votes

# Answer
If you cut the interval in 5 pieces of length 1/5 and pick one then you would expect an element drawn uniformly at random to have chance 1/5 to belong to it. So for, say t =3, an interval of length 3/N the chance is 3/N. Hence you would expect 3 out of N draws to belong to it. Apply this to the interval with boundary 0 and 3/N.
> 0 votes

---
Tags: complexity-theory, probability-theory, probabilistic-algorithms
---


# Question
Title: Why must 2 distinct strings go to the same state in a DFA?
I'm finding it difficult to understand why due to the pigeonhole principle, 2 distinct words must go to the same state in a DFA.

Is it that if there are n words and m states, where there are more words than states (n \> m), that 2 words must end up in the same state?

Is this somewhere along the right path?

# Answer
> 0 votes
Count the number of strings reaching each state. If you have m states, and none is reached by two or more strings, then the total number of strings is at most m. If the number of strings is greater than m then one state is reached in two or more ways.

You can use the same argument if no state is reached by more than 100 strings, then the total number of strings is at most 100m. If you have more than 100m strings then one state can be reached by more than 100 strings.

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


# Question
Title: Heterogenous Resource Allocation Using Dynamic Programming
I'm working on a resource allocation problem, where there are $n$ different Items and $m$ different tasks ($n\geq m$). Also, The profit of assigning subset $I=\\,(\\, |I|\leq n)$ of items to task $j$ is calculated by $f(I;j)$. If no item is assigned to task $j$, then the profit is calculated as $f(\emptyset;j)$. The objective is to find the subset of items ($I\_j$) for each task $j$ to maximize $\sum\_{j=1}^nf(I\_j;j)$. $$ maximize \sum\_{j=1}^nf(I\_j;j)\\ s.t. |I\_j|\leq n , \forall j \in \\{m\\} $$

All items should be assigned, and each item should be assigned to one and only one task. Of course one can think of a brute-force search with the complexity of $O(m^n)$. Could there be a dynamic programming (DP) approach with less complexity?

# Answer
You can't avoid an exponential running time. It takes $m \cdot 2^n$ space even to write down $f$, and any correct algorithm needs to read every entry of that, so any correct algorithm must take at least $\Omega(m \cdot 2^n)$ time.

It is possible to solve the problem in $O(m \cdot 4^n)$ time, using dynamic programming. In particular, let $A\[S,j\]$ be the lowest-cost assignment to tasks $1,2,\dots,j$ using the items in $S$ (every item in $S$ is used exactly once). Then we obtain a recurrence relation

$$A\[S,j\] = \min \\{A\[T,j-1\] + f(S\setminus T;j) \mid T \subseteq S\\}.$$

Finally, we can fill in the entries of $A$ using dynamic programming, by first filling in all of $A\[\cdot,1\]$, then all of $A\[\cdot,2\]$, and so on.

A more careful analysis shows that this dynamic programming algorithm actually runs in $O(m \cdot 3^n)$ time. I am not sure whether it is possible to solve it in $O(m \cdot 2^n)$ time.
> 0 votes

---
Tags: time-complexity, dynamic-programming, resource-allocation
---


# Question
Title: can you find an algorithm for this function?
consider the following function $$ \begin{align\*} f(m,n) &= \begin{cases} k & \text{if program $m$ halts on input $n$ after $k$ steps} \\ m & \text{if program $m$ loops on input $n$} \\ \end{cases} \end{align\*} $$ can you find an algorithm for this function?

# Answer
> 2 votes
The halting problem is a very well known undecidable problem. Suppose your function $f$ is computable. Then the following algorithm can solve the halting problem:

```
Input: code m and input n
Output: true if program m halts on input n, false otherwise

Let k = f(m, n)
if k ≠ m:
   return true
else:
   simulate k steps of program m on input n
   if it halts before k steps, return true, otherwise return false

```

We conclude by reduction that your function is not computable.

---
Tags: turing-machines, computability, halting-problem
---


# Question
Title: Are there arbitraraly hard worst case problems with polynomial time average case complexity?
For example, are there worst case Decidable(but non primitive recursive or other insane time complexity)problems that have a polynomial average case complexity? If so Are there undecidable worst case problems that have polynomial time average case algorithms? Is there a limit on the arithmetical hierarchy where there cannot be Polynomial time average case algorithms past a certain point? Is there an upper bound on the worst case complexity for an algorithm to be polynomial in the average case?

If they exist, What are some examples of practical problems with a worst case complexity of worse then PSPACE? that have polynomial time average case algorithms? I think computing a groebner basis would be an example of this(it is doubly exponential in the worst case, but im pretty sure in the average case it isn't super bad based on the fact that it is actually used for stuff in practice)

# Answer
> 1 votes
Sure. Let $L\_0$ be a hard language (decidable but not primitive recursive, or whatever) and $L\_1$ be in $P$. Define

$$L = \\{ 1^n || x : x \in L\_0, |x|=n \in \mathbb{N} \\} \cup \\{ w||x : x \in L\_1, |w|=|x|=n \in \mathbb{N}, w \ne 1^n \\}.$$

Then the average-case complexity of $L$ (under an appropriate uniform distribution) is polynomial, like $L\_1$, but its worst-case complexity is hard, like $L\_0$.

---
Tags: algorithms, polynomial-time, average-case
---


# Question
Title: Finding optimal paths for multiple agents
This is a real world problem, which due to some specific aspects of it I am having a hard time finding relevant literature for it.

I am looking for either an algorithm, or a pointer to relevant paper(s) describing a solution. I'm assuming one was already published, but I am just fumbling with my search terms.

Problem statement: I have many sites across town in which IoT hardware is deployed. Every day, a team of engineers need to service some subset of these sites. The time which an engineer would need to spend in a site to service it is a constant determined by today's schedule, and is not dependent of the engineer.

All engineers must start at the depot at the start of the day, and return to it at the end of the day, but for any given day, the number of engineers vary, and the number of hours any one engineer is rostered for might also vary.

How do I assign ordered lists of sites to different engineers in order to minimise the total time spent outside of the depo?

To put formally: if I have a graph with weighted edges, and weighted vertices, and a list of `N` max weights, how do I find `N` loops, all containing a specific vertex `v_0`, and each uniquely corresponding to a specific max weight, and not exceeding it, such that each vertex other than `v_0` is visited exactly once, and the total weight across all loops is minimised (where the weight of the loop is defined as the total weight of all edges, and vertices which are part of it)?

# Answer
> 1 votes
The problem is NP-hard: the special case of $N=1$ is the traveling salesman problem. Therefore, you can't expect any efficient algorithm that will always work.

A reasonable approach in practice is to use integer linear programming (ILP). The problem you are describing could be viewed as basically an operations research problem, and operations research makes widespread use of ILP solvers. The basic idea is to introduce zero-or-one integer variables $x\_{i,j,(u,v)}$, which will be 1 if the $i$th loop uses the edge $(u,v)$ as the $j$th step of the loop, or 0 otherwise. Now we can express all the constraints required for this to form a valid solution to the problem using linear inequalities. For instance:

* Forms a valid path that ends at $v\_0$: $0 \le \sum\_u x\_{i,j,(u,v)} = \sum\_w x\_{i,j+1,(v,w)} \le 1$ for all $v \ne v\_0$, and $\sum\_w x\_{i,j+1,(v\_0,w)} = 0$.
* Starts at $v\_0$: $\sum\_w x\_{i,1,(v\_0,w)}=1$.
* Forms a loop: $\sum\_j \sum\_u x\_{i,j,(u,v\_0)}=1$.
* Each loop respects the max-weight constraint: $\sum\_j \sum\_{u,v} \text{wt}(u,v) x\_{i,j,(u,v)} \le \text{maxwt}\[i\]$.
* Each vertex is visited by exactly one loop: $\sum\_{i,j,u} x\_{i,j,(u,v)} = 1$ for every $v \ne v\_0$.
* Minimize total cost: minimize $\sum\_{i,j,u,v} \text{wt}(u,v) x\_{i,j,(u,v)}$.

You might need to adjust some of the details above to exactly match your problem formulation, but hopefully this gives you the idea. If your problem size is fairly small (the graph is fairly small, $N$ is fairly small), then an off-the-shelf ILP solver might be able to solve this. If you are dealing with large problem instances, it might be infeasible to find the optimal solution, and you might need to resort to other approaches, like heuristics or approximation algorithms.

---
Tags: algorithms, graph-traversal, traveling-salesman
---


# Question
Title: What is the complexity of determining whether a graph has a maximal clique of a given size?
What is the complexity class of: given a graph G, is the graph has a maximal clique of size k? k is integer less than or equal the number of graph vertices.

A related question,

Given a Graph G, Find a maximal clique of size k. This is np because it is polynomially verifiable. Right?

The essential question if the above questions are np, then how to reduce them to the maximum clique problem, which is well-known np-complete problem?i.e. if we can find the maximum clique in polynomial time, how can we find a maximal clique of fixed size polynomially?

Thanks!

# Answer
> 0 votes
The standard NP-completeness reduction for Independent Set is from 3-SAT. In this reduction, you there is an independent set of size $|C|$ where $C$ is the set of clauses, if and only if the 3-SAT instance is a yes-instance. By construction, there cannot be any larger independent sets.

Therefore, you can trivially show that the *Maximal Independent Set* problem, i.e. Does $G$ have a maximal independent set of size $k$ is NP-complete in the same manner.

Now, proving similar results for clique should be effortless.

---
Tags: complexity-theory, graphs
---


title: Equivallent characterization of trees?

text:
# Question
Title: Equivallent characterization of trees?
I am a teacher of undergrad graph theory and we tend to invent some weird (and false) characterizations of trees and recently I stumbled upon this one.

Is the following true? $G$ is a tree if and only if $G$ is connected and between each pair of vertices of same degree, there is an unique path connecting them.

If we remove the connectivity condition, then any tree together with an isolated vertex is a counterexample. What if we add the connectivity?

Obviously if $G$ is tree, then the condition is true. But is it sufficient to show that $G$ is a tree? I tried to approach by contradiction that it contains a cycle. Given any circle $C$ in $G$, all vertices inside $C$ must necessarily have distinct degrees. But that's all I can come up with. Any ideas on how to proceed?

Edit: Some more thoughts. Assume, aiming for a contradiction, that $G$ contains a cycle $C$ and that $v\_i, v\_j$ are two vertices of the same degree (because for $|V|\geq 2$, it cannot happen that all vertices in $V$ have distinct degrees). $v\_i,v\_j$ cannot lie on a circle (not only they cannot be on C, but on *any* circle at all). Which in turn means that $v\_i,v\_j$ belong to distinct $2$-connected components. Now, Denote them $X,Y$. Assume the graph $G'$ whose vertex set consists of $2$-connected components of $G$ and there is an edge between $C\_i$ and $C\_j$ if and only if they share an articulation. Let $X,C\_1,C\_2,\ldots,C\_k,Y$ be a path in $G'$ between $X$ and $Y$... Now if the components were nontrivial (i.e. contained a cycle), this would imply a contradiction, but $G$ could be just a path, so here I am stuck again ... There must be assumption about the location of the cycle $C$ w.r.t. $v\_i, v\_j$ and the components $X,Y$. Here I am stuck again.

# Answer
This seems to be a correct characterization of trees, here is my proof of it (hope there is no mistake).

Let $G = (V, E)$ an undirected graph. Denote $(P)$ the property "$G$ is connected and between each pair of vertices of same degree, there is an unique path connecting them."

Suppose there exists a graph verifying $(P)$ without being a tree. Let $G$ be such a graph with the least possible number of edges. There exists two vertices $u, v\in V$ such that $\deg\_G(u) = \deg\_G(v)$. By $(P)$, there is a unique path $p = (v\_1, …, v\_k)$ from $u = v\_1$ to $v = v\_k$. Since there is a unique path between any two vertices of $p$, deleting the edges of $p$ will create $k$ connected components $C\_1, …, C\_k$, such that $C\_i$ contains $v\_i$ (otherwise, there would be more than one path between two vertices of the path).

* **Fact 1**: for each $i \in \\{1, …, k\\}$ such that $|C\_i| \> 1$, $C\_i\setminus \\{v\_i\\}$ contains a vertex $w$ such that $\deg\_G(w) = 1$.
    + **Proof of fact 1**: suppose there is a $C\_i$ of size $\>1$ with no vertex of degree $1$ other than $v\_i$. Then consider the graph $H$ obtained from $G\[C\_i\]$ adding one (if $i = 1$ or $i = k$) or two (if $1 \< i \< k$) dummy vertices, adjacent only to $v\_i$. In $H$, all non-dummy vertices have same degree as in $G$ (dummy vertices are here to insure that $v\_i$ keeps the same degree). Moreover, there is a unique path between the two dummy vertices (if there are two).

    Note that there are very particular cases where $H$ has the same number of edges than $G$. This can only happen if both $u$ and $v$ are of degree $1$, and either $k = 2$, or $k = 3$ and $i = 2$. In the first case, $G$ is clearly a tree; in the second case, then $C\_2$ contains two vertices of same degree $\>1$ and we can use those vertices instead of $u$ and $v$.

    In all other cases, since $H$ satisfies $(P)$ and contains strictly less edges than $G$, it is a tree. By deleting the dummy vertices, it stays a tree. That means that $G\[C\_i\]$ is a tree and contains at least two vertices of degree $1$. This is absurd given the hypothesis on $C\_i$.
* **Fact 2**: let $C\_i$ be a connected component of size $\> 1$, and $w\in C\_i, w\neq v\_i$ a vertex of degree $1$. Then there is a unique path from $w$ to $v\_i$.
    + **Proof of fact 2**: suppose there are at least two paths from $w$ to $v\_i$. WLOG, suppose $i \neq 1$ (if $i = 1$, just swap the role of $1$ and $k$). Then consider $w'$ that is either $v\_1$ if $\deg\_G(v\_1) = 1$ or a vertex $w'\in C\_1, w'\neq v\_1$ of degree $1$. Therefore, there would be at least two paths from $w$ to $w'$. This is absurd because $G$ satisfies $(P)$.
* **Fact 3**: for each $i \in \\{1, …, k\\}$, $G\[C\_i\]$ is a tree.
    + **Proof of fact 3**: either $|C\_i| = 1$ hence $G\[C\_i\]$ is a trivial tree, or $|C\_i| \> 1$. If that's the case, consider the same construction $H$ as before. There is still a unique path between two vertices of same degree $\> 1$. Given fact 2, there is a unique path between two vertices of degree $1$. Again, we conclude that $H$ is a tree, and that $G\[C\_i\]$ (obtained by removing dummies) is a tree.

Adding the path $p$ to all $G\[C\_i\]$, we cannot create a cycle, and therefore $G$ is a tree.

We conclude by contradiction that $G$ is a tree if and only if $G$ satisfies $(P)$.
> 2 votes

---
Tags: graphs, trees
---


# Question
Title: What is the difference between Data Hazard and Dependencies in Pipelining
In my GATE Exam I have given with the following question statements and

1. R5 ← R0 + R1
2. R6 ← R2 * R5
3. R5 ← R3 - R6
4. R6 ← R5/R4
5. X ← R6

the question was to calculate number of *Output*, *True* and *Anti Dependencies* in the instructions.

I calculated and it turns out to be

RAW (True Dependency)

* I1 - I2 (R5)
* I2 - I3 (R6)
* I3 - I4 (R5)
* I4 - I5 (R6)

WAR (Anti-Dependency)

* I2 - I3 (R5)
* I3 - I4 (R6)

WAW (Output Dependency)

* I1 - I3 (R5)
* I2 - I4 (R6)

Now my friend argued

> Had the question been to calculate the number of possible **data** hazards the answer would have been different because Dependencies and hazards are not same

When we calculate possible hazards we should reorder the instructions and find the dependencies. Dependencies and hazards are closely related but not same. He has also gave me a pdf which implies that a dependency may not be a hazard. A dependency is a "possible hazard" considering all cases which involve reordering of instructions etc. But the solution of GATE question is involving those dependencies only which are causing hazards only not potential or possible hazard.

I go through them but was not able to finalize proper relationship between hazard and dependencies.
Can someone please explain how **Dependencies**, **Possible Hazards** and **Potential Hazards** relate to each other in a way more easily understood? (Explanation using the above instruction set is preferred)

# Answer
> 1 votes
I think a **dependency** is something you see by looking at the code and trying to figure out possible WAW, WAR, RAW hazards that could happen. **Actual hazards** instead are a property of the pipeline which means that a dependency you found earlier may or may not generate an hazard depending on the actual code execution in the processor.
In your example there's an output dependency between the instructions I2 - I4, but if we assume that the pipeline does not stall for any reason between the two and that the execution time for each instr. is the same, I2 wll be completed before I4 thus not generating any hazard.
To make the answer more clear, with the information you give about the excercise it's impossible to know the number of hazards because we don't know the architecture on which that code is executed nor the state of the pipeline.
I found your question searching for an answer so I'm not completely sure. Since you asked some months ago maybe you already found the correct answer. If so could you share it please ?

# Answer
> 0 votes
I am answering late and I guess you may have found the answer. According to geeksforgeeks, your solution is correct since **true**, **anti** and **output** dependance are types of Data Dependences. The article urgue that hazards and dependences are used interchangeably. Meaning they are the same.

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: I need to test the speed of performing arithmetic operations on binary numbers
As part of a college project, I need to compare the speed of arithmetic operations directly in binary on different processors.

Example: At what speed will binary addition be performed on an Intel Core I5-12400 processor?

Initially, I had the idea to write a program myself that would perform the appropriate tests. The problem is that I'm programming in python so the final results wouldn't be accurate. I don't have time to learn another language.

I was looking for ready-made solutions in the form of programs or repositories on the Internet. I also looked for ready-made final data in various scientific papers.

I have a question for the community here. Do you know any ready-made programs, repositories or scientific papers that will allow me to obtain the data needed to prepare the study?

Thank you very much for your help on behalf of myself and the rest of my group.

# Answer
You don't really need to learn an entire new language.

Here's a 1-line program in C (running on Linux):

```
$ cat test.c
int main() { register long i; for (i=-10L*1000*1000*1000; i<0; ++i); }

$ gcc test.c

$ time ./a.out
real    0m5.064s
user    0m5.056s
sys     0m0.008s

```

It took 5 seconds to perform 10 billion iterations.

Isolating how much of that was spent on the addition itself won't be as easy.

But we can look at the assembler that was generated by the compiler:

```
$ gcc -S test.c

$ more test.s
…
        jmp         .L2
.L3:
        addq        $1, %rbx
.L2:
        testq       %rbx, %rbx
        js         .L3
…

```

The loop consisted of an addition, a comparison, and a jump.

You'd have to look at the manufacturer's specs for how many clock cycles are required for each of the three operations. Knowing that, you can assign the appropriate fraction to the addition.

Of course there are other factors to consider too.
In this case "addition" means adding 1 to *i*, but perhaps the timing would be different if it added the value of *j* instead of 1. As asked, the question doesn't specify exactly what is meant by "arithmetic operations directly".
> 1 votes

# Answer
There are two possibilities: Either you write code in a language where you can see the assembler instructions that are produced. Or you go through processor manuals and figure it out.

Now on basically every processor one addition, subtraction, and, or, xor operation will be performed in one cycle - the result is available one cycle after the operands were available.

What that doesn't tell you is how long say 100 operations take. Newer processors can usually perform more than one operation at the same time - as long as one operation doesn't depend on the results of the previous one. And you usually have vector operations that can do two, four, eight or more integer operations at one time, in one cycle. And you have processors with multiple cores. A processor with eight cores can do eight times as many operations.

To measure that, you really have to write code.

And according to computer scientists, an addition of two n-bit numbers takes O (log n) time with a good implementation :-)
> 1 votes

# Answer
"Speed" does not have a well-defined meaning at that level. Basic CPU instructions have a *latency* (or in general, more than one) and a *throughput*. Different ways of measuring the "speed" could result in either the latency or the throughput or, if not done carefully, neither. Arbitrarily executing instructions without designing a specific experiment will give *some* answer, but may not yield useful information with a clear interpretation.

Multiple latencies can occur because the latency from one input of an instruction to the output may be different from the latency from another input to the output, for example a complex multi-µop instruction may perform some operations on one input first and only read the second input later. Addition is not that complex though.

The latencies and throughputs of many x86 instructions on a variety of x86 processors have been determined with a methodology described in uops.info: Characterizing Latency, Throughput, and Port Usage of Instructions on Intel Microarchitectures, with the data available at https://uops.info/index.html

Your processor, the Intel® Core™ i5-12400, is an Alder Lake. It has two different types of cores, P-cores and E-cores. Instruction latencies and throughputs are different on the different types of core.

There are similar lists available for, for example, Apple M1
> 0 votes

# Answer
In modern computers, the time for an operation cannot be measured, full stop. Because it is highly non-deterministic.

The running time depends on important factors such as memory response time (across several levels of cache plus virtual memory), as well as (hyperthreaded) pipeline utilization. In addition, for the heaviest operations, time can depend on the values of the operands. Last but not least, you will be timing a loop at the same time.

So any empirical measurement will not necessarily reflect the behavior in real use.

The best that you can do is to refer to the manufacturers' timing tables.
> 0 votes

---
Tags: arithmetic, cpu, binary
---


title: Confusion about B-Tree

text:
# Question
Title: Confusion about B-Tree
In a B-Tree, one of the rules is:

*Every node (except the root) is at least half full*

But then, in a 4-way B-Tree, we have the following case. Suppose we want to insert $10,20,30,40$ to the tree.

After inserting the 3 first element we get the following root:

```
  [10  20  30]

```

After adding the 40, we split as follows:

```
        [30]
[10 20]       [40]

```

For a node to be half full in a **m**-way B-Tree there must be in that node $\lceil \frac{m}{2} \rceil$ elements. So there must be 2 elements in every node, but the node $\[40\]$ clearly breaks this rule! So why is this allowed and what should we do?

B-Tree is seriously confusing me and i couldn't find any answers online.

# Answer
According to wikipedia, the condition of being half-full only applies on internal nodes, and it concerns the number of children, not the number of keys (which is always one less than the number of children, except for leaves).

In your example, the node \[40\] is a leaf, therefore the half-full property does not apply.
> 1 votes

---
Tags: data-structures, search-trees, b-tree
---


title: influence of neighourhood points

text:
# Question
Title: influence of neighourhood points
Im trying to understand the following question. Suppose $h,f:\\{-1,1\\}^n\rightarrow \\{-1,1\\}$ satisfy $\sum\_x h(x)f(x)\leq 0.5$, then one can rewrite this as $\textsf{Pr}\_x \[h(x)=f(x)\]\leq 3/4$. Can we use this statement to show: there exists $i\in \[n\]$ such that $\sum\_i h(x)f(x)h(x^i)f(x^i)$ is small (where small here is unquantified, but im guessing it depends on $0.5$)? Also $x^i$ means the $i$th bit of $x$ is flipped.

In order to understand the above (either in proving its true or false), I started looking at $\sum\_w h(w)f(w)\textbf{E}\_i \[h(w^i)f(w^i)\]$ and seeing if it could be shown to be small as well. This requires one to understand the following: suppose $\textsf{Pr}\_x \[h(x)=f(x)\]\leq 3/4$, then can we use that to say anything about the fraction of $w$s for which $h(w)=f(w)$ and $h(w^i)\neq f(w^i)$? Even this is unclear to me.

Any thoughts/counterexamples/references in this direction would be appreciated.

# Answer
No. Suppose $h$ is the parity function and $f(x)=-h(x)$. Then $\sum\_x h(x) f(x) = -2^n \le 0.5$, but $\sum\_i h(x) f(x) h(x^i) f(x^i) = n$ (which is as large as it can get) for all $x$.
> 1 votes

---
Tags: probability-theory, boolean-algebra, boolean-complexity
---


# Question
Title: Known results for games like "twenty questions"?
Consider the following game: You are given a set $S$ and a fixed list $q\_1$, $q\_2$, ..., $q\_n$ of yes or no questions about the elements of $S$. Your opponent chooses an element of $S$ without telling you which. You then ask a series of questions taken from the list and your opponent truthfully answers "yes" or "no" to each. Your choice of each question can depend on the answer to the previously asked question. Your goal is to deduce the secret element of $S$ your opponent has chosen in as few questions as possible.

For example, $S$ might be $\\\{\text{banana}, \text{orange}, \text{football}, \text{basketball}\\\}$ and the list of questions might be "Is it a fruit?", "Is it spherical?", "Is it an animal?". In this case you could deduce the secret by asking just the first two.

This is a simple enough problem that I suspect a lot has been said about it in the computer science literature. I'm beginner enough that I don't even know what keywords to search to read more. So here are some questions:

1. Does this problem go by a certain name? Or is easily it reducible to some other well-known named problem?
2. Are there results about the number of queries necessary in various cases, say where the questions take a certain form? (For example, binary search is a special case of this problem where the allowed questions are of the form, "Is the index of the sought after value less than $i$?" The result there would be that the worst case takes $\log(|S|)$ queries.)
3. I'm also interested in the variant of the problem where you have a set number of queries and the goal is to maximize the probability of guessing the secret after using up these queries. E.g. in the example above, with just one query you can narrow down the secret to two possibilities, giving you a 50% chance of guessing the right answer (assuming the secret is chosen uniformly at random). With two queries you can narrow it down entirely, so your probability of success is 100%.

# Answer
> 3 votes
This is the problem of building a decision tree of minimal depth. Each question is a feature that you can branch on in a node of the tree. The tree structure captures the adaptive nature of the queries.

See ID3 for one heuristic algorithm, and decision tree learning for the general area.

---
Tags: complexity-theory
---


# Question
Title: A basic question about approximation algorithms for the Traveling Salesman Problem
Approximating the traveling salesman problem (TSP) within a constant factor $k$ is hard. The standard proof shows that the existence of such an approximation allows the Hamilton Cycle problem to be decided. This standard proof is discussed in many places including accepted answers on cs.stackexchange here and here.

Briefly, the standard proof for $k=2$ works as follows. Suppose a graph $G$ with $n$ vertices is given as input to the Hamilton Cycle problem. We create a weighted complete graph $H$ with the same $n$ vertices as follows: The edges in $G$ are given weight 1, and the added edges are given a large weight, say $n+2$. Notice that every Hamilton cycle in $H$ either has total weight $n$, or at least $(n-1) + (n+2) = 2n+1$. This **gap** allows a 2-approximation algorithm for TSP to answer the decision problem. More specifically, if $G$ has a Hamilton Cycle, then the 2-approximation algorithm must return the value $n$ since the other Hamilton cycles have total weight $\>= 2n+1$. On the other hand, if $G$ does not have a Hamilton cycle, then the 2-approximation algorithm will return a value larger than $n$.

I'm uncertain about something even more basic. What would a 2-approximation algorithm return if we did not add the edges of weight $2n+1$? In other words, suppose we take graph $G$ and create a weighted graph $G\_1$ by assigning weight 1 to each edge in $G$, and we do not add any new edges. In this case, the Hamilton cycles in $G\_1$ (if any) all have total weight $n$, and they all correspond to Hamilton cycles in $G$. There is no *gap* in the total weights of the Hamilton cycles.

What exactly would the 2-approximation algorithm return if $G$ has a Hamilton cycle? And what if $G$ does not have a Hamilton cycle?

# Answer
The misunderstanding comes from two variations of the TSP problem:

1. The input graph is complete.
2. The input graph is arbitrary.

The standard proof above must assume the first variation of TSP. Thus, there is no k-approximation algorithm for the first variation unless $P=NP$. The same result then follows for the second variation due to the fact that the second variation generalizes the first variation.

To answer the question directly: The input to the TSP variation in question must be a complete graph.

Note: The Wikipedia article states the following: *Often, the model is a complete graph (i.e. each pair of vertices is connected by an edge). If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour.*
> 4 votes

# Answer
The 2-approximation algorithm returns a TSP (cyclic) tour whose value is at most twice the optimal value. The input to the algorithm is a complete weighted graph – you need to specify a weight for each edge. If there is a Hamilton cycle, which has the minimal value $n$, the a 2-approximation algorithm will return some tour whose value is at most $2n$. It could return a Hamilton cycle. Or it could return something else. It depends on the algorithm and on the graph. If there is no Hamilton cycle, and the minimal TSP tour has weight $m$, then the algorithm will return some tour of weight at most $2m$.

The construction you describe ensures that a 2-approximation algorithm will return a Hamilton cycle if there is one; if there isn't, it of course would return any. So looking at the output, we could know whether the original graph contained a Hamilton cycle. In fact, it is enough to know only the weight of the cycle returned by the 2-approximation algorithm.
> 1 votes

# Answer
In the "Hamilton cycle" problem, two nodes are either connected or not connected. Let's replace this with a "Travelling salesman" instance, where any two connected nodes have a distance of 1, and any two unconnected nodes have a distance of 2. If there is a Hamilton cycle, then the TSP instance has a solution of length n. If there is no Hamilton cycle, then the TSP instance must use some connection of length 2 instead of 1, so the optimal route has a length ≥ n+1.

This makes it easy to check if there is a Hamilton graph: Create and solve the TSP instance, then check if the optimal solution had a length n or a length ≥ n+1. And that proves that TSP is NP-complete, because it can be used to solve instance of the NP-complete "Hamilton cycle" problem.

Now there is an obvious way to show that "finding an approximation that is at most k \> 1 times longer than the optimal" is NP-hard:

Take a "Hamilton cycle" instance. Create a TSP instance where nodes have a distance of 1 or 1 + M. We'll figure out M. The optimal solution of the TSP problem has a length of **exactly n** if there is a Hamilton cycle, and **at least n + M** if there is no Hamilton cycle. Your approximation algorithm will find a solution of **length ≤ n * K** in the first case. In the second case, there is no solution shorter than n + M, so your approximation algorithm will find a solution of **length ≥ n + M**. Being a K-approximation, it might actually find a solution of length K * (n + M), but n + M is the minimum.

If we choose M \> n * (K - 1), then the solution will have **length ≤ n * K** in the first case, and **length \> n * K** in the second case. So by finding a K-approximation to the optimal tour, we can check its length and figure out whether there was a Hamilton cycle or not. So for any K \> 1, being able to find K approximations solves an NP-complete problem and is therefore at least as hard as solving the NP-complete problem.
> 1 votes

---
Tags: complexity-theory, approximation, traveling-salesman, hamiltonian-path
---


# Question
Title: What is the most critical component of a processor?
We know that there are basically 3 fundamental parts of a processor namely :

1. Control Unit (CU)
2. Arithmetical Logic Unit (ALU)
3. Clock

Also we know that they maintain several important and different functions of the processor.

However, if we had to arrange them according to their importance/priority , then which one should have been on the top of the list ?

I mean what is the most critical component of a processor ?

# Answer
The clock is not a significant part of the CPU. Both the controller and ALU are complex. You can add the register bank.
> 1 votes

# Answer
I would say the *control unit*.

Every processor must be able to process a sequence of instructions in order.

It's possible (but tricky, and very silly) to design a processor with no ALU\**. The processor might have one type of instruction: copy address X to address Y and branch to address Z. I suspect this is enough to implement a bounded Turing machine emulator\*, but if not, you could add paged addresses or conditional branches. On this processor, doing any useful computation is rather difficult, but it should be possible. You have to use silly quantities of lookup tables and self-modifying code.

But a processor with only an ALU and no control unit is not a processor because it can't run programs. A program is necessarily a sequence of instructions, so without sequencing, you don't have a program, and sequencing is a control-unit function.

* It will never be unbounded, because you have no way to generate addresses that don't appear somewhere in the program.

\** The control unit will have to increment the program counter to read the 3 parts of an instruction, but you can avoid using actual math for this if you add an unused 4th part and use concatenation. If you did choose to add 1 to PC, though, that still wouldn't be an ALU.
> 1 votes

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