# Question
Title: Max sum cyclic path of fixed length in matrix
Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves are up, down, left, right and each position can be visited multiple times but only contributes to your sum once.

Example: for K = 8

```
7 3 5 9
1 2 0 4
9 4 2 7
7 6 3 2

```

Optimal route (I think): 0 2 4 9 7 6 3 2 0

First off, of course K has to even (or the problem should state of length at most K). Secondly I was thinking of a solution along the lines of:

```
opt[i][j][t] = the maximum sum that can be obtained at position (i,j) at time t

```

The problem with this is that you can't be sure where you can come from. There is no way to (efficiently) know what values you can use to calculate opt\[i\]\[j\]\[t\]. I could keep the actual path for each position but that would be $O(nmk^2)$ memory, which is essentially $O(n^6)$ \- which is extremely unfeasible. Even the solution itself which is $O(nmk) = O(n^4)$ is probably a little too slow. And, in fact, if I have to check each path that would make the complexity as bad as the memory necessary.

Does anyone have any ideas? I would appreciate hints to try to figure it out myself, not actual solutions. Thanks!

# Answer
> problem with this is that you can't be sure \[which path\] you can come from.

Indeed. So do it exhaustively for all feasible paths. That is, work on subproblems where you vary $t$ up to $K$, and store their results, at least for a little while. It should be possible to discard partial results corresponding to clearly bad solutions, and consume just $O(t^2)$ memory to remember the cells we should avoid.

Naively one could access a dense matrix `opt` by dereferencing `opt[i][j]`. To access the $n$th variant of a matrix with sparse edits applied to it, first probe a mapping to see if `edit[(i, j, n)]` exists, and if not fall back to dereferencing the dense matrix in the usual way. You may find it convenient to build up a path for the $n$th variant as a list of `(i, j, value)` tuples.

Additionally, we can decompose into the "outbound" and "inbound" sub-problems. Visiting a cell essentially sets that cell to zero, so each candidate outbound path gives rise to a new matrix. In the end the outbound path length will be $\frac{K}{2}$ and each new matrix gives rise to another $\frac{K}{2}$ inbound problems. The inbound solver would probe a hash map, and would add zero to the reward for any cell appearing in the outbound path.

Consider the Manhattan distance between current cell and origin. A decent heuristic for 1st stage search would be to make that distance strictly increasing on the outbound path, then strictly decreasing on the inbound path, which reduces the search space a little. Your idea about storing optimal values is a good one for further pruning the search space.

Please do keep us posted on your progress, especially on any pruning techniques that seem promising.
> 0 votes

---
Tags: algorithms, algorithm-analysis, dynamic-programming
---


# Question
Title: Given a set of intervals on the real line, find a minimum set of points that "cover" all the intervals
I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval $I$ there should be some time point $t$ from the chosen set such that $t \in I$. However, I am not sure if it's that straightforward. I tried modeling it as a minimum edge cover problem ("P" polynomial time complexity: intervals are vertices and intersection between intervals is an edge), but that doesn't work because for 1 time point in optimum solution there can be multiple edges.

I developed a greedy solution: have intervals sorted in increasing order of their end times. Then iterate over the intervals in the order. If a time point hasn't been inserted into the solution that covers the current interval, then insert it and remove all intervals that are covered by it from consideration. Continue till no intervals remaining. Example: (0, 10), (3, 12), (11, 15)

Add time 10 to the solution. Remove (0, 10) and (3, 12) from consideration. Add time 15 to solution. Remove (11, 15) from consideration. Final solution is of size 2. (time 10 and 15).

I can't prove it's optimum because it's not modeled as edge cover or vertex cover or known graph problem. I tried modeling it as "minimum clique cover problem" but not sure if it works.

* How to model it properly to understand its complexity (P vs NP complexity)?
* How to know if the above solution is optimum?

# Answer
> 2 votes
## The problem is in $\mathbf{P}$.

In fact, there is even a (very) efficient algorithm for it:

Let $\[a\_1, b\_1\], \dots, \[a\_n, b\_n\]$ be the input intervals and assume $a\_i \le b\_i$ for all $i$. Additionally, let us assume (for now) that the intervals are given in sorted order as a list, sorted firstly respective to the $a\_i$ and secondly to the $b\_i$.

An optimal solution can be found as follows: Set $r$ to $a\_1$. Then, starting with $i = 1$, check if $a\_{i+1} \le b\_i$; if that is the case, set $r$ to $a\_{i+1}$ and increment $i$; otherwise, add $r$ to the solution and eliminate all intervals from $\[a\_1, b\_1\]$ up to $\[a\_i, b\_i\]$. Repeat until no more intervals are left.

Why is this an optimal solution? $\[a\_1, b\_1\]$ must be covered, so there must be some $r \in \[a\_1, b\_1\]$ in the solution. Then, either $r$ covers all $n$ intervals or there is $i$ such that $r \< a\_{i+1}$. The way our solution is constructed, $r$ is chosen so as to cover a maximal number of intervals while preserving these two conditions for $r$ (i.e., $a\_1 \le r \le b\_1$ and $r \< a\_{i+1}$). Apply induction on the remaining intervals (i.e., $\[a\_j, b\_j\]$ with $j \ge i + 1$).

The above procedure runs in linear time in $n$. The bulk of the time complexity, thus, lies in sorting the intervals, which can be done in $O(n \log n)$. I do not believe there is a better solution than this (though how to prove it does not occur to me at the moment).

---

## A note

After some thought, the solution you have given also seems to be optimal (in fact, the only significant difference is you pick end times instead of start times). Proving it is optimal is analogous to the argument above: Set $r$ to $b\_1$; if $a\_2 \le b\_1$, then $r$ already covers $\[a\_2, b\_2\]$, so disconsider it; otherwise, $a\_2 \> b\_1$ and there is no $r$ covering both $\[a\_1, b\_1\]$ and $\[a\_2, b\_2\]$. Apply induction.

The time complexity is still $O(n \log n)$, though, since you require sorting the end times first.

---
Tags: complexity-theory, graphs, np-complete, set-cover, clique
---


title: Vertex Cover approximation algorithm

text:
# Question
Title: Vertex Cover approximation algorithm
I have an algorithm that solves the Vertex Cover problem. The algorithm is

> Repeat while there is an edge:
>
> Arbitrarily pick an uncovered edge $e = uv$ and add $u$ and $v$ to the solution. Delete $u$ and $v$ from the graph.

I know this strategy is a *2-approximation* to Vertex Cover and that its worst example is the *complete bipartite graph* $K\_{n,n}$. In this graph, the algorithm will return a vertex cover of size $2n$ whereas the optimal solution is of size $n$.

**Question:** Does there exist a graph with Minimum Vertex Cover of size 10 where this strategy finds a minimum vertex cover?

# Answer
You ask for a graph where your (nondeterministic) algorithm gives the optimal solution even in the worst case. We're looking for a set of vertices that cover all edges. The difficulty with your algorithm is not only that it could pick the edges in an "inconvenient" order, but also that it adds both vertices belonging to the edge, which is suboptimal in most cases (since adding one of the vertices already covers the edge).

An example where your algorithm does always find the optimal solution of size 10, is the graph below. If you meant the problem the other way around (cover all vertices), the same graph applies.
> 4 votes

---
Tags: optimization, approximation
---


# Question
Title: Two Problems in understanding the algorithm for computing shortest paths in undirected graphs with possibly negative edge weights
Section 2 of this Lecture Note: Shortest Path Algorithms Luis Goddyn, Math 408 describes an algorithm using Edmonds' Minimum Weight Perfect Matching Algorithm to solve the shortest path problem for undirected graphs with negative-weight edges but no negative cycles.

I have two problems in understanding this algorithm:

* In step 3, why must $G'$ have perfect matchings so that we can apply Edmonds' Minimum Weight Perfect Matching Algorithm to $G'$?
* In step 4, why must each circuit in $S$ have total weight $0$?
(A possible argument is like this: Because there are no negative cycles, we only need to show that each circuit in $S$ cannot have positive total weight. Maybe this can be proved by contradiction. Suppose that some circuit in $S$ have positive total weight, we need to show that $M$ is not a mimimum weight perfect matching or this cannot be a circuit. However, I failed to reach a contradiction.)

---

Related post: Finding shortest paths in undirected graphs with possibly negative edge weights.

# Answer
Your answer to the second problem is nice.

Here is an hint or strategy for the first problem.

Select a path $P$ from $s$ to $t$. Verify that there is perfect matching for the corresponding $P'$. Form graph $Q$ from $P$ by adding one vertex $u$ of $G$ not in $P$ (if there is) and all edges from $u$ to vertices in $P$. $P'$ is extended to $Q'$ correspondingly. A bit of reasoning by cases will show the previous perfect matching of $P'$ can be extended to a perfect matching of $Q'$. Now you can add another vertex, repeatedly.
> 1 votes

# Answer
An answer to the second problem:

**Problem:** Each circuit in $S$ must have total weight zero. Why?

**Proof:** By contradiction.
Suppose that some circuit $C$ in $S$ have nonzero total weight.
Because $G$ has no negative cycles, $C$ has positive total weight.
Note that $C$ does not contain $s$ or $t$. Therefore, the edges of $C$ are all $5$-edge gadgets; see step 2.
Then we can construct another perfert matching on $C$ whose total weight is zero by choosing the middle edge with weight $0$ of each $5$-edge gadgets and the edges between $v$ and $v'$ (for each $v$ in $C$; see step 1) also with weight $0$.
This contradicts the assumption that $M$ is a minimum perfect matching.
> 1 votes

---
Tags: graphs, shortest-path, correctness-proof, matching
---


# Question
Title: Does this DFA describe this regular expression?
For the expression `(ab)*ba` I came up with the following (very poorly drawn):

However, this was not the correct answer - apparently the solution requires five states. I don't understand why my DFA doesn't describe the expression. My interpretation of the expression is "`ab` any number of times, followed by `ba`". Is this correct?

# Answer
For something to be a DFA, it should have transitions from every state for every letter in the alphabet. Your alphabet is {$a, b$}, so every state should have a transition for $a$ as well as $b$, e.g., your state 2 does not have a transition for $a$. Complete your DFA and you'll get what is that 5th state that you are missing.
> 1 votes

# Answer
Your solution is correct—but you've built an NFA, not a DFA.

The difference is that an NFA can have any number of transitions on a single symbol from a single state. Anything from zero upward.

A DFA needs to have exactly one transition for each symbol from each state. Right now you're missing several of those. The fifth state to add is a "failure state" that transitions only to itself; make all the missing transitions go to this failure state.
> 1 votes

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


# Question
Title: picking a word for pumping lemma for L = {a^n b^m c^n b^m a^n | m,n≥0}
If i have a language like $L = \\{a^n b^m c^n b^m a^n \mid m,n\ge0\\}$

when i pick a word for the language, would it be correct if i pick any of

these words: $w = a^k c^k$, $w = a^k b^m c^k $, $w = b^m b^m$, $w = b^m c^n b^m$.

# Answer
If you want to apply the pumping lemma for regular languages, you can pick any word in the language whose length is no less than the pumping length. The same applies to the pumping lemma for context-free languages.

However, some of the words in your list may not be in the language.

$a^k c^k$ is in the language if and only if $k=0$.
$a^k b^m c^k $ is in the language if and only if $k=0$ and $m$ is even.
$b^mb^m$ is always in the language.
$b^m c^n b^m$ is in the language if and only if $n=0$.

Yes, a general approach is to check the balance between different symbols. Had the language been $\\{a^nc^n\mid n\ge0\\}$ or $\\{a^n b^m c^n b^m\mid m,n\ge0\\}$, you could select $a^kc^k$ towards a contradiction. You cannot if the language is $\\{a^n b^m c^n b^m a^n \mid m,n\ge0\\}$, since $a^kb^k$ is not a word in the language in the first place. For that language, you can choose $a^kc^ka^k$.

Specifically, here are all the words in $\\{a^n b^m c^n b^m a^n \mid m,n\ge0\\}$. Note that all of them start and end with the same symbol.

$$\begin{align} &\epsilon,\\ &aca,\ a^2c^2a^2,\ a^3c^3a^3,\ a^4c^4a^4,\ \cdots\\ &bb,\ a^1bc^1ba^1,\ a^2bc^2ba^2,\ a^3bc^3ba^3,\ a^4bc^4ba^4, \cdots\\ &b^2b^2,\ a^1b^2c^1b^2a^1,\ a^2b^2c^2b^2a^2,\ a^3b^2c^3b^2a^3,\ a^4b^2c^4b^2a^4,\ \cdots\\ &b^3b^3,\ a^1b^3c^1b^3a^1,\ a^2b^3c^2b^3a^2,\ a^3b^3c^3b^3a^3,\ a^4b^3c^4b^3a^4,\ \cdots\\ &\vdots \end{align}$$
> 1 votes

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: Are physical laws uncomputable in any type of computation (according to this article)?
It seems that this article (https://arxiv.org/pdf/1312.4456.pdf) proposes that laws of physics are uncomputable (i.e., they could not be reproduced on a computer), but I'm not sure about it.

In some part of the article it says:

> If we expand the set of computational devices that we use to define computational complexity, then the consequences of the known laws of physics can in principle be elaborated in polynomical \[sic\] time on classical and quantum computers.
>
> If we restrict our attention to laws whose consequences can be evaluated in polynomial time, then the problem of finding concise expressions of physical laws is no longer uncomputable.

So, what is it saying? That laws of physics are uncomputable? That laws of physics could not be reproduced in a computer? That laws of physics could not be reproduced in any type of computer?

Also, in the conclusions it says:

> This chapter reviewed how uncomputability impacts the laws of physics. Although uncomputability as in the halting problem arises from seemingly esoteric logical paradoxes, I showed that common and basic questions in physics have answers that are uncomputable. Many physical systems are capable of universal computation: to solve the question of whether such a system has discrete or continuous spectrum in a particular regime, or whether it is gapped or gapless, requires one to solve the halting problem. At a more general level one can think of the all scientific laws as providing concise, easily unpacked descriptions of obserbational \[sic\] and experimental data. The problem of finding the most concise description of a data set is uncomputable in general, and the problem of finding the most concise description whose predictions are easily evaluated is NP-complete.

So, what can we conclude from this? Also, what does it exactly mean that "finding the most concise description whose predictions are easily evaluated is NP-complete"?

# Answer
The reasoning given in the paper is too vague to be of much value. The question whether laws of physics are computable cannot be decided by a philosophical discussion. It already takes some hard physics and math to even properly formulate the question.

Let me give an analogy. It is impossible to travel faster than light, right? But if I shine a laser at the moon and move it fast enough, the laser dot on the moon will move faster than light. So how is this possible? We have a contradiction in physics. Or do we?

It is easy to have a discussion about computability in the real world, or computability of the laws of physics, at the level of the previous paragraph. For instance, the very nice and seriously presented result on the Undecidability of the spectral gap is easy to misinterpret, because the devil is in the details. The actual experiment cannot be set up because it requires unrealistic conditions. If we approximate the experiment, then the theorem does not hold anymore. But this does not stop people from misinterpreting the result.

For a more reasonable account of computability of the laws of physics I recommend A computable universe, in which you can find discussions of many aspects of computability. If you are interested in computability of the laws of physics then the Matthew Szudzik's contribution The Computable Universe Hypothesis.

Personally I would say that the question "is the universe computable" is ill-formed, because this is not a falsifiable statement. The question "are the laws of physics computable" makes more sense, but one really has to be careful how it is phrased.
> 3 votes

---
Tags: computability, np-complete, quantum-computing, physics
---


title: Private IP and public IP

text:
# Question
Title: Private IP and public IP
What we see on our devices is essentially the private IP given to us by the ISP; thereby, whenever we access the internet, this private IP is first converted to public IP (by ISP through NAT), following which requests are made on the internet. If the assumptions above are right, then how does a website gets my private IP? Do websites/servers interact with me over my public IP or the private IP?

I am a bit confused over this topic as books often say that only private IP goes in the internet (i.e., the one assigned by the ISP) but websites/servers are able to make a log of your private IP. This gets me confused.

# Answer
A private IP is not necessarily assigned by an ISP. It is actually a much more general concept: Any node (or cluster of nodes) realizing NAT separates two networks, a *public* and a *private* one. Most routers in home networks separate your internal network (private) from your ISP's or the wider internet (public). In the case of an ISP, it might be so that the ISP uses NAT to separate its own network of subscribers (private) from the wider internet (public), though not all ISPs have such a policy; actually some ISPs may even provide you with a reserved public IP (i.e., an IP which is accessible from the wider internet and which is statically assigned to you).

A private IP is only valid within its own network. In fact, the values for private IPs are standardized and are not routed in the wider internet. Thus, even if a node (e.g., a webserver) in the internet came to know the IP of your device in its private network—which, up to exploits, is unfeasible because of NAT—, it cannot really do anything with that IP unless it is also part of the device's private network: any packets sent to that IP will be immediately dropped (i.e., not routed) by the next node. Rather, what is logged in webservers and the like is the public IP of the NAT node through which you are accessing it.
> 2 votes

---
Tags: computer-networks, communication-protocols
---


# Question
Title: Can this set of propositions be represented and proved in Haskell?
I used a set of natural language statements and their formalization from Gries and Schneider. I attempted to transform the propositions into Haskell equations. For example, for S0 : $a \land w \Rightarrow p$ the conjunction was split giving $a \Rightarrow p$ and $w \Rightarrow p$ and then the contrapositive rule was applied giving $\neg p \Rightarrow \neg a$ and $\neg p \Rightarrow \neg w$. I then translated those propositions into Haskell conditional equations.

Is the Haskell representation a reasonable transformation? Is there a relation between the execution of the Haskell expression `not e` a proof of theorem $\neg e$?

**Natural language**

If Superman were able and willing to prevent evil, he would do so. If Superman were unable to prevent evil, he would be ineffective; if he were unwilling to prevent evil, he would be malevolent. Superman does not prevent evil. If Superman exists, he is neither ineffective nor malevolent. Therefore Superman does not exist.

**Formalize**

$a$: Superman is able to prevent evil.

$w$: Superman is willing to prevent evil.

$i$: Superman is ineffective.

$m$: Superman is malevolent.

$p$: Superman prevents evil.

$e$: Superman exists.

S0 : $a \land w \Rightarrow p$

S1 : $(\neg a \Rightarrow i) \land (\neg w \Rightarrow \neg m)$

S2 : $\neg p$

S3 : $e \Rightarrow \neg i \land \neg m$

```
module SUPERMAN where
 a::Bool
 w::Bool
 i::Bool
 p::Bool
 e::Bool

 a | (not p) = False  -- S0a
 w | (not p)  = False -- S0b
 i | (not a) = True   -- S1a
 m | (not w) = True   -- S1b
 p = False            -- S2
 e | (i || m) = False -- S3
-- Theorems (not e), (i || m), and (i && a) all hold

```

# Answer
> 5 votes
Your Haskell encoding fails to capture proofs in propositional calculus (which is what the book you referred to does). The failure is not due to your using Haskell, but because of your encoding evaluation of Boolean values instead of proofs, and these are two completely different things.

When people speak about "Haskell proving things" they mean the following: given a type `t` which represents a proposition $T$ via the propositions as types translation, does there exists a Haskell program `p` of type `t` which corresponds to a proof of $T$?

Example: the proposition $((A \land B \Rightarrow C) \Rightarrow (A \Rightarrow B) \Rightarrow (A \Rightarrow C)$ corresponds to the (polymorphic) type `((a,b) -> c) -> (a -> b) -> (a -> c)`. The program `\ f g x -> f (x, g x)` has this type, and therefore corresponds to a proof of the proposition. The kind of logic that can be represented in this way is *intuitionistic*.

However, because Haskell has general recursion, not every Haskell program corresponds to a proof, and in fact Haskell cannot be considered as a proof system. It is a programming language. A better choice is Agda or Idris.

You are translating propositions into Boolean algebra which you then encode using the Haskell datatype `Bool`. You are therefore misusing the phrase "prove in Haskell". At best you are trying to evaluate Boolean expressions, which is not the same thing. You defined, in a somewhat convoluted way, a (partial) evaluation strategy that evaluates various Boolean propositions. It's not a very good one, for instance if you change `p = True` line to `p = False`, your program fails to evaluate `a`.

This has nothing whatsoever to do with Haskell because it is not specific to it. You can do the exact same thing in just about any programming language, and even in Excel. However, as was suggested already twice, prolog seems to be the most appropriate tool for the problem at hand. You are not "researching" Haskell here. I believe we already tried to explain this to you in the previous question you linked to. I hope it gets across this time.

---
Tags: logic, propositional-logic, haskell
---


# Question
Title: Are there strings which get accepted only by PDA by empty stack and not by PDA by final state, and vice versa?
Can the same PDA accept both by final state and empty stack in the sense that there are some set of strings that are getting accepted by empty stack, while other set of string by final state and language accepted by the PDA is union of these two?

For example, Consider the PDA shown below:-

I was trying to figure out the language accepted by this PDA and I got confused on the point that a string w=b is given as input, that will be popped out and the stack will be empty so would b be an element of language accepted by PDA or if we consider it only as acceptance by final state (considering that acceptance by final stack requires the bottom of stack symbol to be left in the stack ) the language accepted by this PDA will be :

```
{w| any prefix of w has number of a's more than number of b's}

```

However a string like "ab" can also be accepted if we allow both acceptance by empty stack and final state (The confusion here is strictly more a's or it can be equal too).

# Answer
> 1 votes
Since it was not explicitly mentioned, I'll assume that the PDA in the question is a PDA $P\_s$ that has been defined for acceptance by empty stack. Let the language accepted by $P\_s$ be $L\_s = N(P\_s)$.

There definitely exists another PDA $P\_f$ which produces a language $L\_f = L\_s$ by defining acceptance on final state. This is why we say that:

> A language L has a PDA that accepts it by final state **if and only if** L has a PDA that accepts it by empty stack.

However, it is wrong to expect that the two PDA $P\_s$ and $P\_f$ are the same.

---
Tags: finite-automata, context-free, pushdown-automata
---


# Question
Title: Is a set $B = \{y, \exists x \in A, f(x)=y\}$ recursive if A is a recursive set and f is a $N->N$ total computable function?
Obviously, B would be recursive if for every TCF f, there was an inverse fuction that would return all possible values, as we could just take these and then check if any of them is in A. However I cannot find a proof (or counter-proof) that you can invert TCFs this way. AFAIK, all injective functions are invertible, but can we also invert a non-injective function and compute all the possible inputs that would result in the desired output?

# Answer
In general, no, we can't conclude that $B$ is recursive. We can choose $f$ so that $B$ is the halting problem, for instance.

To do that, choose any TM $M\_0$ which halts on the empty input.

We define $f(x)$ as follows. Let $M,n$ be such that $\langle M, k \rangle = x$ where $\langle -, - \rangle$ is any computable pairing function (bijection). Then, run $M$ on empty input for $k$ steps. If that halts, return $\langle M \rangle$, otherwise return $\langle M\_0 \rangle$.

It is then easy to verify that, using such $f$, we have

$$ \begin{array}{ll} B &= \\{ \langle M' \rangle \ |\ \exists M,k. f(\langle M,k \rangle)= \langle M' \rangle \\} \\ &= \\{ \langle M' \rangle \ |\ \exists k. M' \mbox{ halts in $k$ steps } \\} \\ &= \\{ \langle M' \rangle \ |\ M' \mbox{ halts} \\} \end{array} $$

---

With some more effort, we can even make $f$ injective, yet obtain the same $B$ (halting problem).

Indeed, a well-known result states that any RE nonempty set $A$ is the image of some total computable function $g: \mathbb N \to \mathbb N$. For the halting problem $A$ is infinite and RE, so there is such a $g$. Exploiting $g$ we can define $f(x)$ as $g(y)$ where $y$ is the least number such that $\\{g(0),g(1),\ldots,g(y)\\}$ contains exactly $x+1$ (non-duplicate) elements.

Note that $y$ exists since the image of $g$ ($A$) is infinite.

In such way the image of $f$ is the same as the one of $g$, i.e. $A$, but $f$ is now injective by construction. ($f$ is not surjective, of course)
> 0 votes

---
Tags: computability, sets
---


title: Problem: covering holes on a pipe

text:
# Question
Title: Problem: covering holes on a pipe
The problem is informally defined as follows:

There is a pipe with holes in it, located at discrete positions. We have tubes that are used to cover the holes. Tubes come at fixed radius. Having a tube of a radius of 1, say, placed at position 3, covers holes at positions 2, 3, and 4. The puzzle is about providing positions for placing the tubes so that the lowest possible amount of tubes are used. Note that tubes are allowed to overlap each other.

For example, the tube radius is 1 and the holes are located at {2, 4, 6, 10}. Tubes need to be placed at position 3 (covering 2 and 4), 6 and 10.

Obviously this seems to be a covering problem, yet I wasn't able to find a specific, studied problem equivalent to this one. Any ideas on how to efficiently approach it?

**EDIT**: please consider an additional condition, which requires a tube's center to be placed exactly on top of a hole (for whatever strange reason). This should change the solution considerably.

# Answer
> 2 votes
If you see your position from left=0 to right=length(pipe), you can simply cover your holes from left to right.

When adding a new tube, put the leftmost remaining hole at the leftmost covered position by the tube. Then you cannot waste tube.

For instance with radius 2, a tube centered on pos k covers \[k-2, k+2\]. Then a tube with leftmost on k covers \[k, k+4\].

With holes at {2, 4, 5, 7, 9, 11}: \- first hole at 2 =\> first tube at \[2, 6\] centered on 4 \- next hole at 7 =\> next tube at \[7, 11\] centered on 9

# Answer
> 1 votes
First an observation: This problem could be stated with different sets of rules. If you try to find a solution that minimises the cost, and using a tube has an associated positive cost independent of the position of the tube and the holes covered by it, then you can always find an optimal solution where each tube is positioned such that the leftmost hole it covers is at the left edge of the tube, and is not covered by any other tube.

Why is that? Because given any optimal solution where this is not the case, we can move one tube to the right until the leftmost hole it covers is not covered by any other tube (if that is not possible, then the tube would be redundant), and then further to the right until the leftmost hole it covers is at its left edge.

This shows immediately that Vince's algorithm is optimal for the case that all tubes have the same radius and the same cost, since it is always necessary to cover the leftmost hole that isn't covered yet, *and* we can cover it as described by Vince's algorithm, and still get an optimal solution.

With different rules, the situation becomes more difficult. For example, we might have tubes of different sizes and cost. In that case, we can use dynamic programming - the best way to cover n holes is always to cover the first m holes at optimal cost, then add a tube covering the next n-m holes.

If there are limited numbers of some tubes, then we still use dynamic programming, but we need to keep track of the optimal solutions with different usage of limited resources. For example, if we had unlimited numbers of tubes of size 1, and at most three tubes of size 5, we would separately calculate how to best cover the first n holes, using 0/1/2/3 tubes of size 5.

PS. Another condition was added: The center of a tube must be exactly on top of a hole. So if I have holes at 3 and 5 but not at 4, I cannot cover them both with a tube of radius 1 but only with a tube of radius 2, centered at either 3 or 5.

An optimal solution with all tubes the same size will still cover the leftmost uncovered hole with a tube positioned as far to the right as possible. So if the leftmost uncovered hole is at location h, and the tube has radius r, instead of always placing the center of the tube at (h + r) which may not be possible, you place it at the first of the locations (h+r, h+r-1, ..., h+1, h) which has a hole.

# Answer
> 0 votes
One tube of radius 4 placed at position 6 should do'er..

If you must use tubes of radius 1, then 3 tubes at positions 3,5, and 10 should suffice.

If you need an algorithm for find the most efficient placements given tube radius and hole locations, I could cook one up for you..

Otherwise you'll need to provide more rules to this puzzle.

---
Tags: algorithms
---


# Question
Title: Are all integers kept in 2's complement form in all microprocessors?
Are all integers kept in 2's complement form in all microprocessors or do microprocessors use 1's complement form and unsigned integer form too?

# Answer
> 2 votes
If there was the keyword "almost" attached to the question then answering it could have been much more easy. As people have mentioned in the comments that nothing can be said with certainty about "all" the processors but yes majority of them do.

2s compliment is definitely preferable over the 1s compliment as it provides you a better range for instance if you have 8 bits the you can represent numbers in the range -2^7 to 2^7-1 with it (1 bit being for the signed bit). its interpretation also is easy and quick for the processors.

However for floating point numbers most processors use a different strategy to save them efficiently. This post would fall short if I needed to explain about them but matter of fact they don't use 2s compliment they rather have the concept of exponential, mantissa and signed bit. And there are 2 commonly used variant of these known as the single precision and double precision floating point representation which are technically same and vary only by the range they can represent. If you want to read further about this you can visit https://steve.hollasch.net/cgindex/coding/ieeefloat.html (not my website, but the website explains the whole thing fabulously).

Let me know if I could help you further in this regard.

# Answer
> 0 votes
All integers in all microprocessors, that is a lot of integers in a lot of microprocessors!

Not all microprocessors are CPUs. There are a lot of special-purpose processors in a lot of weird niches. It is not inconceivable that one of those will have a perfectly good reason to use some other representation than two's complement.

Historically, there have been a lot of weird architectures. I'm not sure if any ever used one's complement or explicit signs, but there were certainly ones that didn't even use binary! Decimal representation was not uncommon in the early days. Some Russian computers apparently used ternary.

Even if we ignore ancient history and special-purpose processors, there is still heavy usage of binary coded decimals in the mainframe and midrange area. E.g. IBM's z Processors, and some CPUs in the POWER line have support for binary coded decimals.

---
Tags: computer-architecture
---


# Question
Title: For Loop Range with Smaller Number on Right
Simple question from an algorithm noob...

If $i=1$ then the inner loop will include what I believe to be an invalid range. Is this acceptable pseudocode?

```
For i=1 to n
  For k=1 to i-1
    ...

```

# Answer
> 1 votes
It is acceptable.

The loop says “do something for each integer $k$ in some range”. If there is no integer in that range, the loop just won’t do anything.

---
Tags: algorithms, syntax, pseudocode
---


# Question
Title: Finding the k-th smallest ternary sum of elements from three different arrays
The problem goes like this:

Given arrays $\\{ a\_i: 0\leq i \leq n-1 \\},\\{ b\_i: 0\leq i \leq n-1 \\} $ and $\\{ c\_i: 0\leq i \leq n-1 \\}$, we want to know what is the $k$-th **smallest combination** $a\_r+b\_s+c\_t$ where $r, s, t$ are arbitrary indices.

Since $k$ is relatively much smaller than $n^3$ (we may suppose $k \approx n $ for simplicity), it would be wasteful to: naively enumerate all $n^3$ possibilities and find the $k-$th smallest using a binary heap.

What is a more efficient way (in terms of time complexity) to solve this problem? I try to optimize the naive algorithm described above by first sorting three arrays then do the heaping for $\\{ a\_r + b\_s + c\_t: r+s+t \< k \\}$, but I believe this is far from a most efficient algorithm. Thanks.

*(Rmk: the algorithm is intended to be comparison-based, since elements might be non-integers.)*

# Answer
You can first sort the three arrays. In the following answer we assume these arrays are already sorted.

You can maintain a priority queue $Q$. Initially it contains only $a\_0+b\_0+c\_0$. Then in each iteration, you pop the smallest element (say $a\_r+b\_s+c\_t$), and add $a\_{r+1}+b\_s+c\_t$, $a\_r+b\_{s+1}+c\_t$ and $a\_r+b\_s+c\_{t+1}$ (duplicates are not allowed, while it is easy to check whether a combination already exists in $Q$). Now we can claim the popped sum in the $i$-th iteration is the $i$-th smallest sum.

This algorithm takes $O(n\log n)$ time. If the given three arrays are already sorted, the time is reduced to $O(k\log k)$.

We can use mathematical induction on $i$ to prove the correctness. Suppose the $i$-th smallest sum is $a\_r+b\_s+c\_t$, then we have the following chain:

\begin{align} &a\_0+b\_0+c\_0\\ \le\ &a\_1+b\_0+c\_0 \\ \le\ &\cdots \\ \le\ &a\_r+b\_0+c\_0 \\ \le\ &a\_r +b\_1+c\_0 \\ \le\ &\cdots \\ \le\ &a\_r +b\_s+c\_0 \\ \le\ &\cdots \\ \le\ &a\_r+b\_s+c\_t. \end{align}

For convenience, we denote by $S\_0,\ldots,S\_{\ell}$ these sums in the chain. Let $S\_j$ be the first sum in the chain that is not popped before the $i$-th iteration. Then in the iteration that $S\_{j-1}$ is popped, $S\_j$ is added to $Q$ according to our algorithm. This means the sum popped in the $i$-th iteration must be no more than $S\_j$, thus no more than $S\_{\ell}=a\_r+b\_s+c\_t$. By inductive assumption, the first $i-1$ smallest sums are popped before the $i$-th iteration, so the sum popped in the $i$-th iteration is exactly the $i$-th smallest sum.
> 1 votes

# Answer
I haven't tried to implement it but how about making 3 new arrays say A\[k\],B\[k\] and C\[k\] . These array would store the k smallest elements of all individual predefined arrays and would take O(N) time here N is the number of elements the biggest array, To sort these array we could use the heap sort incurring - O(klogk) time complexity.

initialise a new array - result\[K\]

now the following loops won't take more than O(k) time.

int a=0,b=0,c=0; variables for indices to the array

for(i in range (0,k-1)) {

```
result[i]=A[a]+B[b]+C[c];

select smallest amongst A[a+1],B[b+1],C[c+1]; -(let's say A[i+1] is smallest)

increment the variable to the array which has been found to be the smallest in the previous step(here, a=a++;)

```

}

the ith element of the array would contain the ith smallest integer in the combinations of the array. The worst case time complexity would also be just O(n+klogk). Hope this helps you :) Let me know if I could assist you further.
> 0 votes

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


# Question
Title: What is the behavior of the given counter?
I found the following question -

For the circuit shown in the figure, the delay of the bubbled NAND gate is 2ns and that of the counter is assumed to be zero

If the clock (Clk) frequency is 1GHz, then the counter behaves as a

(A) mod-5 counter
(B) mod-6 counter
(C) mod-7 counter
(D) mod-8 counter

---

What I can see is, in this particular case clock time period is smaller than the delay in the NAND gate. But I am unable to see how it will affect the counter exactly!

# Answer
ANS: MOD8 COUNTER

It still is a mod 8 counter only. But the point where anyone can get confused is the clock speed and the nand gate delay. Basically as soon as we get 111 as the answer. the nand gate gets set to 0 and hence the reset is activated now one may argue that because of this the counter won't count further as it already has the reset pin on. However since the delay of nand gate is more than the time required for the counter to give next output thus before the nand gate could change the counter to 000. The counter would have already produced the next sequence that is 001. that would help it get out of the reset configuration. Steps can be written as follow:-

1. counter produces 111
2. nand gate receives 111 and starts processing it
3. counter produces 000
4. nand computes 0 and hence counter is set to reset i.e. 000.
5. nand receives 000, processes it and the counter gets out from reset state.
6. counter produces 001 as expected.

The only change one could observe with this configuration compared to the normal 3 bit counter is the duration for which the counter would produce the state 000. Rest all would remain the same. Let me know if I could help you further.
> 2 votes

---
Tags: digital-circuits
---


# Question
Title: Do quantum logic gates work differently than traditional logic gates?
In a traditional computer calculations are done with logic gates that check inputs with AND gates etc. But in a quantum computer, are calculations performed differently since the qubit can be in states other than 1 or 0? I understand that qubits can have values other than 1 and 0, however, before it is used as input into a logic gate, does the qubit need to be observed and defined as either a 1 or a 0? Or is the logic gates used in a quantum computer fundamentally different from a traditional computer?

# Answer
In layman's terms, the answer is yes: quantum gates are quite different from classical gates.

One reason is that quantum gates must be *reversible*. This practically means that AND gates don't even exist in the quantum world (at least, not in the same sense of a classical AND gate). Instead, there is a different set of gates (e.g., CNOT, TOFFOLI, FREDKIN, etc.) that allow to do all that is possible by quantum computing, without breaking the reversibility condition.

The other issue is what you hint in your question. Qubits can be "both in 0 and 1", and the quantum gate must take care of this. But this is not a problem, it just means that the output must be a superposition of 0 and 1. For instance, let's take a simple NOT gate. If the input is a "superposition" of 30% 0 and 70% 1, then the output becomes 70% of 0 and 30% of 1. Of course this is a very superficial explanation, and quite inaccurate, but the idea is exactly that.

Finally, no measurement is done in gates, unless the gate is a measurement gate (also, measurement is not reversible, so it cannot happen in "standard" gates)

For more information, check
> 8 votes

# Answer
Yes quantum logic gates work differently than traditional logic gates, the fact that a logic gate operates in 2 logical states, whereas a quantum gate operates according to a quantum instance.
> 0 votes

---
Tags: logic, quantum-computing
---


# Question
Title: How to formulate constraints in zero-one linear programming
There is a factory which produces 5 types of ice cream. If the $i\_{th}$ ice cream is produced then $b\_i=1$ otherwise $b\_i=0$

How can I express the following constraints:

* The simultaneous production of all 5 types ice cream is not possible
* The type 1 and type 2 must be either both produced or none be produced ($b1 \oplus b2$)
* If type 4 is produced, type 5 must be produced too, but if type 4 isn't produced, type 5 can be produced or not.
* If type 4 isn't produced, type 5 must not be produced, otherwise, if type 4 is produced, type 5 can be produced or not

# Answer
> 1 votes
* $b\_1+b\_2+b\_3+b\_4+b\_5 \le 4$
* $b\_1-b\_2=0$
* $b\_4- b\_5 \le 0$
* $b\_5- b\_4 \le 0$

---
Tags: linear-programming
---


# Question
Title: Any CPUs using value prediction, dynamic instruction reuse?
There is a lot of research about techniques that try to reuse the previous result of an instruction, either memory loads or arithmetic, such as dynamic instruction reuse, value prediction, based on the concept of value locality.

What I wonder if there is any commercial CPU from Intel/AMD/ARM that actually uses any of these techniques, or are they still far away from being implemented in CPUs?

I mostly see these techniques as the runtime, CPU version of compiler optimizations such as common-subexpression elimination, loop invariant code motion, redundant load removal, catching cases that cannot be handled due to pointer aliasing, side-effects, etc.

Two of the papers that seem to have introduced these ideas:
Dynamic instruction reuse
Value Locality and Load Value Prediction

# Answer
Modern Intel processors use prediction of values in several situations.

One, when the target of a branch instruction is stored in memory including the location where the return address of a call is stored, that value is predicted.

Second, when a store is followed by a load, it is predicted whether the addresses are the same (or overlapping) or not. That allows the load to be performed speculatively even before the value to be stored is calculated, if it is predicted that the addresses are different.
> 1 votes

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


title: Where can I code in C?

text:
# Question
Title: Where can I code in C?
I have an upcoming CS course in uni that uses C and I want to get ahead a little bit this Christmas break but I'm having a hard time figuring out where I can actually code using C. My school uses this compiler called Seashell but it's not available until the term starts.

I've looked at visual studio but I only see C++, and I've heard of stuff like Vim, GCC, but I'm pretty new to CS and I don't know what any of that really means...

Help?

# Answer
**Visual Studio Code**
Supports many languages including C/C++. It's a very simple IDE. Have a look at it.
https://code.visualstudio.com/
> 1 votes

# Answer
The fifty-year-old C compiler is included with Linux operating systems. The C compiler was also ported to Windows as part of a legal agreement.

Here is a link:

https://gcc.gnu.org/

Now I see the comments so this subject might be a "Software Recommendation".
> 0 votes

---
Tags: c
---


# Question
Title: Is there a term for the distribution of numbers-of-digits of a bounded uniform distribution
Let $X$ be an integer sampled uniformly from the (integer) range $\\{ 0...2^k - 1 \\}$ .

Now, consider the distribution of

$\\#\text{bits}(X) = \begin{cases} 1 & X = 0 \\\\ 1 + \lfloor \log\_2(X) \rfloor & \text{otherwise} \end{cases}$

and

$\\#\text{bytes}(X) = \begin{cases} 1 & X = 0 \\\\ 1 + \lfloor \log\_{256}(X) \rfloor & \text{otherwise} \end{cases}$

which are the numbers of bits and of bytes respectively necessary to hold $X$.

My question: Is there some commonly-used *term* for the one of the *distributions* of $\\#\text{bits}(X)$ or $\\#\text{bytes}(X)$ ? Or for a distribution which is very similar to them?

# Answer
> 1 votes
As @YuvalFilmus suggests, these distributions are very close to being geometric. They *aren't* geometric, since they're bounded, which is what threw me off, but think about it this way:

A geometric distribution corresponds to the number of Bernouli trials up to and including a first success (in some formulations: not including the first success). The distribution parameter p is the probability of succeeding in each individual experiment. Now,

* Our first "experiment" involves sampling the most significant bit (or byte): Will it be 0, or something else? A 0 is a success, something else is a failure.
* Our second "experiment" is the same, but for the second-most-significant bit (or byte).
* and so on.

In a geometric distribution proper, experiments never cease until the first success. In our case, $k$ experiments are conducted, and if you've failed them all then you're simply at 0, with probability $2^{-k}$.

---
Tags: terminology, probability-theory
---


# Question
Title: How does one prove that Big Step semantics and Small Step semantics are equivalent for IMP?
I know there is this paper but I wanted to do a special case proof for just IMP for fun. So the theorem is:

> $$ \langle P , \sigma \rangle \to\_{Big} \langle \\{ \\} , \sigma' \rangle \iff \exists N \in \mathbf N: \langle P , \sigma \rangle \to^N\_{Small} \langle \\{ \\} , \sigma' \rangle $$

in words; the program P in state $\sigma$ evaluates to the empty block IFF there exists a certain number of small step steps inference steps that arrives us to the same configuration, the empty program in state $\sigma'$. Note $\langle P, \sigma \rangle$ stands for a program configuration with state $\sigma$. I am assuming both small step and big step have the same sort of configuration, which might be a big assumption and hard to formalize in real code...

I am happy with just an outline/sketch since a rigurous proof might be too much work probably and I'd rather get something than nothing.

I want to focus on $\Rightarrow$ (big to small). I think one of my main difficulties is finding such an $N$ that works. But conceptually to me I think I would break the proof by induction on the program P. The program has 6 constructors/cases:

1. Empty Block {}
2. Block B which is just $\\{ S \\}$
3. Assignments $x = AExp ;$
4. Sequences $S\_1 ; S\_2$ where $S\_i$ is a statement.
5. while statements $ While \ (BExp) \ do \ S $.
6. ifElse statements $If \ (BExp) \ do \ S\_1 \ Else \ S\_2 $.

for the first case 1) its simple we have $\langle \\{ \\} , \sigma' \rangle$ on the RHS for big step and on the LHS $\langle \\{ \\} , \sigma' \rangle$ for small step, which are the same configuration. Done.

3) For the case assignment case we have to show that the AExp expressed uin the semantics, say big step or small step evaluates to the same as the "aeval" function that recursively just evaluates a real arithmetic expression. Not sure how I can make this more rigorous but at least it is a start.

Things with Boolean expression in them also need the same beval equivalence with boolean evaluation equivalence in their corresponding semantics.

However when things involve statements I am honestly not sure what one would need to argue to show they are equivalent. Do we do induction again on each statement and then proceed by apply the inference rules as many times as possible and show they evaluate to the same final state and empty block? Or what does one need to do? Then especially, how does one find the $N$?

---

The inference rules I had in mind are just any standard IMP semantics:

# Answer
Don't proceed by induction on $P$, i.e. by structural induction on the syntax of programs. This is because structural induction is quite weak, and is likely to fail on `while` loops.

Look at the inference rules for the big step semantics for `while`, in particular at the `while-true` rule which handles the case where the guard is true. In such case, you'll see that in one of the premises we have the same `while` loop. Roughly, the rule defines the behaviour of `while` in terms of itself.

(I didn't check your own rule, and used mine instead, but it should be simple to adapt the reasoning to yours.)

$$ \dfrac{ \sigma\models \phi \quad \langle c, \sigma \rangle \to\_b \sigma' \quad \langle while\ \phi\ do\ c, \sigma' \rangle \to\_b \sigma'' }{\langle while\ \phi\ do\ c, \sigma \rangle \to\_b \sigma''} $$

If we proceed by structural induction, when we handle such case, we only get an induction hypothesis for $c$, wince it is a subterm of $while\ \phi\ do\ c$. That however provides no help in coping with he last premise involving the $while$ itself.

The solution is to use the induction principle generated by the rules for $\to\_b$, instead. Doing that, when handling the rule above, we have *two* induction hypotheses, namely that the small step semantics

1. reduces $\langle c, \sigma \rangle$ to some $\sigma'$ state in some $N$ steps
2. reduces $\langle while\ \phi\ do\ c, \sigma' \rangle$ to some $\sigma''$ state in some $M$ steps

Exploiting those properties, it is possible to show that, using (something like) $N+M+1$ steps, we can reduce $\langle while\ \phi\ do\ c, \sigma \rangle$ to $\sigma''$ using small steps.

The other rules can be handled in a similar way.

When you write such proofs, I strongly suggest to always check the `while-true` case first, since that's the "hardest". Checking it first helps avoiding wasting effort on other simpler (but long) cases, only to discover that the proof can not be completed and all the work done has to be thrown away.

---

Assume we have these as the inference rules for the big step semantics. (If rules omitted) $$ \begin{array}{c} \dfrac{ }{\langle skip, \sigma \rangle \to\_b \sigma} \qquad \dfrac{ \langle e, \sigma \rangle \to\_e v }{\langle x:=e, \sigma \rangle \to\_b \sigma\[x\mapsto v\]} \\ \dfrac{ \langle c\_1, \sigma \rangle \to\_b \sigma' \qquad \langle c\_2, \sigma' \rangle \to\_b \sigma'' }{\langle c\_1;c\_2, \sigma \rangle \to\_b \sigma''} \\ \dfrac{ \sigma\models \lnot\phi \quad }{\langle while\ \phi\ do\ c, \sigma \rangle \to\_b \sigma} \qquad \dfrac{ \sigma\models \phi \quad \langle c, \sigma \rangle \to\_b \sigma' \quad \langle while\ \phi\ do\ c, \sigma' \rangle \to\_b \sigma'' }{\langle while\ \phi\ do\ c, \sigma \rangle \to\_b \sigma''} \end{array} $$

We immediately get the following induction principle.

Let $p(c,\sigma,\sigma')$ be any property of a command and two states. To prove that $$ \forall c,\sigma,\sigma'.\ \langle c \sigma \rangle \to\_b \sigma' \implies p(c,\sigma,\sigma') $$ it suffices to check all of the following:

1. $\forall \sigma.\ p(skip,\sigma,\sigma)$
2. $\forall x,e,\sigma,v.\ \langle e, \sigma \rangle \to\_e v \implies p(x:=e, \sigma, \sigma\[x\mapsto v\])$
3. $\forall \sigma,\sigma',\sigma''.\ p(c\_1, \sigma, \sigma') \land p(c\_2, \sigma', \sigma'') \implies p(c\_1;c\_2, \sigma, \sigma'')$
4. $\forall \phi,c,\sigma.\ \sigma\models \lnot\phi \implies p(while\ \phi\ do\ c, \sigma, \sigma)$
5. $\forall c,\phi,\sigma,\sigma',\sigma''.\ \sigma\models \phi \land p(c, \sigma, \sigma') \land p(while\ \phi\ do\ c, \sigma', \sigma'') \implies p(while\ \phi\ do\ c, \sigma, \sigma'')$

Note that in item 4 we get the induction hypotheses on the subterms, very much like what would happen using structural induction.

In step 5, instead, we get both an induction hypothesis on the subterm $c$, and (crucial!) another induction hypothesis on the $while$ itself (on different states).

For your case, choose a suitable property $p(c,\sigma,\sigma')$ such as "there is some natural $N$ for which $c,\sigma$ terminates in $N$ small steps in stale $\sigma'$".
> 3 votes

---
Tags: semantics, operational-semantics, small-step-semantics
---


# Question
Title: Example of tree with > 6 vertices, tree would have depth = n after splay() deepest vertex
How to build tree with more than 6 vertices, that after operation splay() would have depth = number of vertices? Is it possible?

UPD: Example for n = 4:

* insert 60
* insert 10
* insert 20
* insert 50
* splay(10)

You can use splay tree visualization

# Answer
This is a good question whose answer can help us understand how splay tree tends to keep away from being imbalanced.

No, it is impossible for any rooted tree with more than 5 vertices to become a linear tree after operation splay() one of the deepest vertices, i.e. its depth is one less than the number of vertices.

Why?

For the sake of contradiction, let there be a rooted tree with more than 5 vertices which becomes a linear tree after splaying $x$, one of its deepest vertices. Consider the point of time just before the last splay step that moves $x$ to the root. There are three cases.

* That last step is a zig-step (the following graph) or its mirroring zag-step. Since the resulted tree is linear, part $A$ and $B$ are empty. That means, the left subtree of the root before that step contains node $x$ only. Since $x$ is the deepest node, the whole tree has at most 3 nodes, which is not true.

* That last step is zig-zig step (the following graph) or its mirroring zag-zag. Since the resulted tree is linear, part $A$, $B$ and $C$ are empty. That means, the left subtree of the root before that step contains node $P$ and $x$ only. Part $D$ can have at most two nodes; otherwise, either $x$ was not the deepest node or the resulted tree is not linear. So the whole tree has at most 5 nodes, which is not true.

* That last step is a zig-zag step (the following graph) or its mirroring zag-zig. However, after that step, the root will alway has two children, which is not ture.

---

Exercise. Draw a tree with 5 vertices that becomes a linear tree after splaying one of its deepest vertices.
> 1 votes

---
Tags: data-structures, trees, splay-trees
---


title: Multi-level Paging

text:
# Question
Title: Multi-level Paging
Consider a system which has 2 level paging.The page table is divided into 2K pages and each page is having 4K entries.Memory is word addressable and Physical address space is 64MW which is divided into 16K frames.Page table entry size is 2 words.

(A)Length of logical address

(B)Length of physical address

(C)$1^{st}$ level page table size

(D)one $2^{nd}$ level page table size

My Work

Page table of process is divided into 2K pages, means at second level we have 2K pages.So, this means we should have 2K entries at the first level page table and hence number of bits to index first level page table should be $p\_1=log\_2(2K)=11$

Each page has $4K$ entries and each such entry size is $2$ words.So, Page size must be $8KW$.Since, at second level, each page table is represented by a page, and each such page has $4K$ entries,so number of bits needed to index second level page table

$p\_2=log\_2(4K)=12$

Page Size=$8KW=2^{13}words \rightarrow d(page\\,offset\\,bits)=13$

Physical Address space=$64MW=2^{26}$

$f+d=26$

so $f=13$

That means maximum frames must be $2^{13}=8K$, but question mentions it's 16.

Have I done anything wrong or the question is poorly framed?

# Answer
> 1 votes
your approach is right however some maths isn't making sense in the question itself. for example, we have 4k entries in each page table, each of this entry is 2 W long so total space of a page should be 8K words.

And we got 16K frames in MM whose size is 64MW, thereby the size of each frame should be 2^(26-14)=2^12 word= 4kW

Since the frame size and page size should always be equal but in this particular case the frame size is different than page size hence it could be said that question itself is wrong.

---
Tags: paging
---


# Question
Title: General Approach To Calculate Minimum Number Of Flip-Flops Required
In the previous two years of the GATE exams, a question has been asked for finding number of flip flop's for counting sequence $0−1−0−2−0−3$ in 2016 and $0−0−1−1−2−2−3−3−0−0$ in 2015. But still, the approach discussed in these questions hasn't arrived at Common answer (or) solution.

For $0−1−0−2−0−3$, there are $6$ different states, and thus it acts as a mod−6, counter So, 3 FF's are suffice. In another approach it is said that $2$ bits are used to distinguish three $0$′s and $2$ for $1,2,3$. So number of FF's required =2+2=4

Similar is the case in $0−0−1−1−2−2−3−3−0−0$, one approach says setting clock such that output of FF will be sampled at twice the input frequency makes me think 2 FF's would suffice. But on the other-hand using 2 FF's for $1,2,3,4 $ and 1 FF for identifying which 1 out of two 1′s makes me think $3$ is also right.

So, I want to be sure in answering these type of questions as they have been asked in recent past \[GATE\]\[3\] Exams.Please tell the general approach to solve these type of questions also please comment about minimum number of JK FF's required for following counting sequence so that i will be able to work out myself using the technique provided by you and evaluate my understanding.

1. $0−0−0−1−1−2−2−3−3−...$
2. $0−1−0−2−0−2−0−3−0−2−...$
3. $1−2−3−0−0−1−0−2−2−...$

# Answer
The links you have provided (gateoverflow) are themselves quite helpful. However if you want a even more elaborate explanation then read further.

In the very first question you have sequence 0--1--0--2--0--3 now these numbers represented in binary are: 00--01--10-00-10--00-11 So clearly you would need 2 bits to determine each of those number so 2 FF for that. Moreover there are 3 similar states for that are 000,000,000 so in order to differentiate between them you further would require 3 combinations that would need log(3)base2 digits =2 digits. thereby 2 FF would be required here too.

So that is a total of 2+2 Flip flops required. Let me know if I could help you further.
> 0 votes

---
Tags: digital-circuits
---


# Question
Title: Show that the following algorithm takes $O(n)$ time
You are given a linked list of size $n$. An element can be accessed from the start of the list or the end of the list. The cost to access any location is $\min(i,n-i)$, if the location being accessed is at index $i$ and it belongs to a list of size $n$. Once an index $i$ is accessed, the list is broken into two lists. One list contains the first $i$ elements and the second list contains the rest of the elements. It has something to do with cartesian trees, but I am not clear how to proceed with this chain of thought.

Show that the total cost incurred to access all the elements is any arbitrary order is $O(n)$.

# Answer
Can't be done.

Consider the following sequence of access: $$\tfrac{1}{2}n, \tfrac{1}{4}n, \tfrac{3}{4}n, \tfrac{1}{8}n, \tfrac{3}{8}n, \tfrac{5}{8}n, \tfrac{7}{8}n, \ldots$$

The first access costs $\tfrac{1}{2}n$. The next two cost $\tfrac{1}{4}n$ each, for a total of $\tfrac{1}{2}n$. The next four also cost a total of $\tfrac{1}{2}n$. Overall we get a cost of $\tfrac{1}{2}n \lg n$.
> 1 votes

# Answer
We assume that $n=2^k$ ($k\in \mathbb{N\_0}$). It must be that the maximum cost to the element that is first accessed is $2^{k}/2$ or $2^{k-1}$, since every other element have less cost than that. After this element is being accessed, the linked list must be broken into two equal size that has size $2^{k-1}$. But then, the maximum cost to access an element for both the linked list is just $2 \times (2^{k-2})=2^{k-1}$. Repeating this again and again, we find that the total cost spent must be $$2^{k-1}+2\cdot2^{k-2}+2^2\cdot2^{k-3}+\ldots+2^{k-2}\cdot2+2^{k-1}=k\cdot2^{k-1}=\mathcal{O}(n \lg n)$$ I don't think that's a $\mathcal{O}(n)$.
> 1 votes

# Answer
As mentioned in the other answers, there are counterexamples with cost $c\cdot n \log n$. Here's a quick argument for why the bound $O(n \log n)$ is tight. Let's build a binary tree from the access sequence: when we split at some $i \in \[n\]$ we make element $i$ the root, and then turn $\[1, i-1\]$ and $\[i+1, n\]$ into binary trees recursively using the same procedure. The resulting two trees will be the two children of $i$ (as long as they are non-empty).

Now what was the cost incurred for element $i$? Note that $\min(i, n-i)$ is proportional to the size of the smallest of the subtrees rooted at $l(i)$ and $r(i)$ in the tree we constructed above. So the cost incurred by each element is the size of its smallest child subtree. We can then reverse the question and ask: how often does an element $j$ appear in the smallest subtree of one of its ancestors? When we travel from $j$ to the root, each time this happens, the size of the subtree (at least) doubles, and so this can happen at most $\log n$ times.

Hence the total cost, for any access pattern, is $O(n \log n)$.
> 1 votes

---
Tags: algorithms, runtime-analysis
---


# Question
Title: How to prove a LTL formula correct in a specific model?
I have been learning **Verification by model checking** recently and I get the following question:

$Whether\ the\ LTL\ formula\ M, q\_3\ \models (X\ \lnot a) \rightarrow (F\ G\ \lnot a)\ is\ established\ or\ not\ in\ this\ model\ M?$

And there is the description of the model. .

I think it is correct, because the next state of $q\_3$ is $q\_1$ or $q\_2$ and the next state of $q\_1$ is $q\_2$. So I get an infinite loop about $q\_2$, which satisfies $F\ G\ \lnot a$. But I only can give the thought of my prove in natural language not mathematical rigor way.

if not mind, could anyone tell me my thought is right or wrong and prove it in a mathematical rigor way?

Thanks in advances

# Answer
Your intuition is correct.

Consider an arbitrary path starting from $q\_3$: let it be $q\_3\\, q\\, q'\\, q'' \ldots$. We need to prove it satisfies $\varphi = (X\lnot a)\rightarrow (FG \lnot a)$.

We proceed by cases on the second state $q$ in the path. It can be one of $q\_1,q\_2,q\_4$.

If $q=q\_4$ then $X\lnot a$ is false in the path, hence $\varphi$ is true in the path.

If $q=q\_1$ or $q\_2$ then we must have $q'=q''=\cdots=q\_2$. The whole path is of the form $q\_3\\, q\\, q\_2\\, q\_2\\, q\_2 \ldots$. This path makes $FG\lnot a$ true, since there exists a suffix (namely, $q\_2\\, q\_2\\, q\_2 \ldots$) where $G\lnot a$ is true ($a$ is false in each state of the suffix). Hence, $\varphi$ is true in the path.

You could make this even more formal by explicitly referring to the definition of validity.
> 1 votes

---
Tags: logic, formal-methods, model-checking, linear-temporal-logic
---


# Question
Title: How to properly calculate dependent nested loops for big-O
I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, both of which iterate $n$ times, the order will be of $n^2$; but if we have a dependent nested loop such as:

```
input = an n-dimensional array
For i = 0; i < n; i++:
        For j = 0; j < i; j++:
            ...

```

Am I correct in thinking this would always be $O(n^2)$ as in the worst case, this loop will always be $n^2$?

The lecturer gave us the forumla $\frac{1}{2}n(n+1)$ but has not explained in what context this is to be used for calculating the running time of a 2-nested loop with dependency. Is there a general way to calculate the running time of a dependent nested loop, like there is with standard nested loops?

# Answer
We can write the for loop as the sums;

$$\sum\_{i=1}^{n} \sum\_{j = 1}^{i} 1 = \sum\_{i=1}^{n}i = \frac{n(n+1)}{2} \in\mathcal{O}(n^2) \\, .$$

Note: set the starting values from $i = 1$ and $j = 1$, and increment the upper boundaries also. The calculation in the inner function is assumed as a constant operation and it will not change the calculation.
> 2 votes

# Answer
Well that all depends how you want to do it and how comfortable are you with the different ways. You could either make a tree and calculate the leave nodes for the time order. Or you could use the mathematical way as mentioned by others in the answer section. For example if you have a loop like-

```
for(i=1;i<n;i++)
{ for(j=1;j<n;j=j*2)
  {anyfunc();
}}

```

the you would understand that the outer loop works from 1 to n and the inner loop would work from 1 to n also however the step in the inner loop is not a single increment but with every iteration it is becoming double of the previous value hence would execute for logn time. Thereby the net complexity would become O(n\*logn).

Hope this helps, I would be more than happy to help you further.
> 1 votes

# Answer
You need to focus on how many times the instructions on the innermost loop will get executed. The outer loops are more like counters.

The inner-loop count will be as follows:

$i = 0; j = \emptyset$
$i = 1; j = 0$
$i = 2; j = 0, 1$
$i = 3; j = 0, 1, 2$
$\dots$

So you have a recurring sum of 1 for $j$ from $0$ to $i-1$, which can be mathematically expressed as:

$$\sum^n\_{i = 1}\sum^{i-1}\_{j = 0} 1 = \sum^n\_{i = 1} i = \frac{n(n + 1)}{2}$$
which is still $O(n^2)$.
> 0 votes

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


title: Pipelining and instruction cycle

text:
# Question
Title: Pipelining and instruction cycle
Consider the sequence of machine instruction given below: \begin{array}{ll} \text{MUL} & \text{R5, R0, R1} \\ \text{DIV} & \text{R6, R2, R3} \\ \text{ADD} & \text{R7, R5, R6} \\ \text{SUB} & \text{R8, R7, R4} \\ \end{array}

In the above sequence, $R0$ to $R8$ are general purpose registers. In the instructions shown, the first register shows the result of the operation performed on the second and the third registers. This sequence of instructions is to be executed in a pipelined instruction processor with the following $4$ stages: $(1)$ Instruction Fetch and Decode $(IF)$, $(2)$ Operand Fetch $(OF)$, $(3)$ Perform Operation $(PO)$ and $(4)$ Write back the result $(WB)$. The $IF, OF$ and $WB$ stages take $1$ clock cycle each for any instruction. The $PO$ stage takes $1$ clock cycle for $ADD$ and $SUB$ instruction, $3$ clock cycles for $MUL$ instruction and $5$ clock cycles for $DIV$ instruction. The pipelined processor uses operand forwarding from the $PO$ stage to the $OF$ stage. The number of clock cycles taken for the execution of the above sequence of instruction is \_________.

I got the answer as 15 however the correct answer is 13. Am I doing something wrong or is the answer key at fault? The link for reference: https://gateoverflow.in/8218/gate2015-2-44

# Answer
Note the sentence "The pipelined processor uses operand forwarding from the PO stage to the OF stage". That means if a result is written at cycle n, the same result can be read as an operand at the same cycle n. This happens twice in your instruction sequence. If you ignore this, your count will be too high by two.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: Validity of CTL formula $s_0 \models EG\ AF\ p$ in given model
I have been learning **Verification by model checking** recently and I get the following question:

> Is the CTL formula $s\_{0} \models EG\ AF\ p$ valid in the following model?

I think it is incorrect because there is a deadlock or infinite loop about $s\_0$ after the state is starting from $s\_0$, which make it invalid under $EG\ AF\ $ condition.

Am I correct? How can I prove it (or give a counterexample)?

# Answer
You're correct. Another way to see would be to consider the de-morgan equivalent: $\neg (AF~EG~\neg p)$. To show this invalid, we can show its negation $AF~EG~\neg p$ is valid, which is easier: The formula $AF~EG~\neg p$ says on all paths starting at $s\_0$, we eventually get to a state such that there is a path where $\neg p$ holds forever. And indeed that is true in the path $s\_0 \rightarrow s\_0 \rightarrow\ldots~.$ Since we established the negation, your original formula is invalid as you yourself concluded.

Thinking about CTL can be tricky. A good way is to always double-check using a CTL model checker, like the following:

```
MODULE main()
  VAR
    state: {s0, s1, s2, s3};

  ASSIGN
    init(state) := s0;
    next(state) := case
                     state = s0: {s0, s1, s3};
                     state = s1: s2;
                     state = s2: s1;
                     state = s3: s2;
                   esac;

  DEFINE
    p := (state = s1) | (state = s3);
    r := (state = s0) | (state = s1) | (state = s2);
    q := (state = s2) | (state = s3);
    t := (state = s1);

  SPEC EG AF p;

```

Using nuSMV (http://nusmv.fbk.eu/), I get:

```
-- specification EG (AF p)  is false
-- as demonstrated by the following execution sequence
Trace Description: CTL Counterexample
Trace Type: Counterexample
  -> State: 1.1 <-
    state = s0
    t = FALSE
    q = FALSE
    r = TRUE
    p = FALSE

```

Which is NuSMV's way of saying you can simply stay in the starting state and it would be a counter-example to your property.
> 1 votes

---
Tags: logic, model-checking, computation-tree-logic
---


title: Greedy Algorithm Proof Min Swaps

text:
# Question
Title: Greedy Algorithm Proof Min Swaps
**Problem to get the min. no. of swaps required for arranging pairs togethe.**

There exists an array of size 2N with integers ranging from 0 to 2N-1 arranged at random. Each integer is paired with another i.e. 0 paired with 1, 2 paired with 3,...2N-2 paired with 2N-1. What is the minimum number of swaps required to have all pairs next to each other.
E.g. : `[5,4,2,6,3,1,0,7] -> [5,4,2,3,0,1,6,7]` Output 2 swaps needed

**Solution: Greedy Approach**

```
for i from 0 to 2N-2:
    if array[i] and array[i+1] does not constitute a pair:
        find the pair for the ith one and swap position with i+1 element

```

What is the proof for why the above greedy algorithm is optimal?

# Answer
The algorithm in the question can be stated more clearly in the following form since considering the odd $i$ does not have any effect once $i-1$ has been take care of.

```
for even i from 0 to 2N-2:
    if array[i] and array[i+1] does not constitute a pair:
        find the pair for the i-th one and swap position with i+1 element

```

---

Here is an outline of the proof.

Given an array $A$ of size $2N$ with integers ranging from $0$ to $2N-1$, let us construct a graph $G$. Replacing $2i-1$ with $2(i-1)$ for all $i$, we will have a new array $B$ of even integers from $0$ to $2(N-1)$, each of which appears twice. Let $G$ have vertices $0, 2, \cdots, 2(N-2)$.

* If $B\[0\]=2i$ and $B\[1\]=2j$, we will add an edge between $2i$ and $2j$ in $G$.
* If $B\[2\]=2i$ and $B\[3\]=2j$, we will add an edge between $2i$ and $2j$ in $G$.
* $\cdots$
* If $B\[2N-2\]=2i$ and $B\[2N-1\]=2j$, we will add an edge between $2i$ and $2j$ in $G$.

Please note since $2i$ might be the same as $2j$, $G$ may have self-loops. Since each even number appears twice in array $B$, the degree of each of vertices of $G$ is 2 (2-regular graph). That means $G$ is a disjoint union of cycles.

Define a function $s$ from arrays which are permutations of $0, 1, \cdots, 2N-1$ to $\Bbb N$, $s(A)=$ the number of cycles in $G$, where $G$ is obtained from $A$ by the above deterministic construction.

Claim (**at most 1 increase with one swap**). Suppose an array $A$ is changed to $A'$ by a swap of two elements. Then $s(A')\le s(A)+1$.

Suppose we have proved the claim. Notice that $s(A)=N$, the maximum value of $s$ if and only if all pairs are next to each other. Since you can only increase at most 1 to $s(A)$ by each swap and the greedy algorithm does increase $s(A)$ by 1 with each of its swaps, the greedy algorithm must be optimal.

---

I will leave the gaps in the above proof as two easy exercises.

Exercise 1: The greedy algorithm increase the value of $s$ by 1 with each of its swaps.

Exercise 2: Prove the claim of at most 1 increase with one swap.
> 0 votes

---
Tags: greedy-algorithms
---


# Question
Title: Shortest path with nodes containing collectibles of negative cost
Suppose you have a graph with weighted edges and nodes. Edges always have non-negative costs (representing e.g. fuel costs), and nodes always have non-negative benefits (representing e.g. collectible fuel tanks). A path from A to B is a series of contiguous edges starting at A and finishing at B. The net cost of a path is the sum of the weights of edges (including multiplicity) on the path minus the sum of the benefits of the distinct nodes (ignoring multiplicity) on the path.

In principle paths are permitted to visit a node more than once, but the node's benefit is only ever collected once (i.e. you can't pick up the same fuel can twice).

Is there an efficient algorithm to find a minimum cost path from A to B in this situation? What if you're promised that the input contains no paths from A to B with net negative cost? What if you're happy with heuristics that perform well when nodes containing 'fuel' are scarce?

# Answer
This is NP-Complete, by reduction from Traveling Salesman Problem (TSP).

Take any TSP. Give every city an extremely large "negative-benefit," and set the origin city as both the start and finish. Now running a solver for your problem will give the solution to the TSP.

---

I'm not sure of any "efficient heuristics", but if you remove the condition that nodes are allowed to be visited twice, the problem becomes much easier. If you subtract every nodes' "negative benefit" from all its incoming edges, it becomes a normal shortest path problem.
> 1 votes

---
Tags: algorithms, optimization, shortest-path
---


title: Boolean Functions

text:
# Question
Title: Boolean Functions
Say you have N input Boolean function, let's use a parity tree for the example. The function outputs a one or a zero depending on the values of the N inputs. Are the N inputs considered the preimage of the function?

# Answer
> 2 votes
*Functions* don't have preimages; outputs do. Your Boolean function has *domain* the set of $2^N$ binary $N$-tuples, that is, the set $$\big\\{(000\ldots 00),~ (000\ldots 01),~ (000\ldots 10),~ (000\ldots 11),~ \cdots , (111\ldots 10),~ (111\ldots 11)\big\\}$$ and *range* (a.k.a. the set of outputs) the set $\\{0, 1\\}$. The *outputs* have *preimages* which are defined as the set of all inputs that are mapped onto that particular output by the specified function; in this instance the Exclusive-OR of the $N$ bits. For example, with $N=3$,

* the *preimage* of $0$ is the set $\big\\{(000),~ (011), ~ (101),~ (110)\big\\}$
* the *preimage* of $1$ is the set $\big\\{(001),~ (010), ~ (100),~ (111)\big\\}$

Notice that the preimages are a *partition* of the domain; every element of the domain is necessarily a member of one (and only one) of the preimages.

In short, the answer to your question

> Are the N inputs considered the preimage of the function?

is **No, they are not.**

# Answer
> 0 votes
An $n(=N)$ input Boolean function $f$ has $2^n$ input space, and output 0 or 1. Formally;

$$f:\\{0,1\\}^n \mapsto \\{0,1\\}$$

The pre-image of $\\{0,1\\}$ under $f$ is the all input space $\\{0,1\\}^n$.

The pre-image of $0$ under $f$ is the set $$f^{-1}\[0\]=\\{ x \in \\{0,1\\}^n |\\; f(x) = 0\\}$$

and the pre-image of $1$ under $f$ is the set $$f^{-1}\[1\]= \\{ x \in \\{0,1\\}^n |\\; f(x) = 1\\}$$

And;

$$f^{-1}\[0\] \cup f^{-1}\[1\] = \\{0,1\\}^n $$

Don't confuse pre-image with the inverse function.

---
Tags: boolean-algebra
---


# Question
Title: Big-Endian/Little-Endian argument - paper by Danny Cohen
Reading a book I was redirected to "On holy wars and a plea for peace" paper by Danny Cohen, which covers the "holy war" between big-endians and little-endians considering byte-order.

Reaching the summary of the memory section I got confused as the author sais:

> To the best of my knowledge only the Big-Endians of Blefuscu have built systems with a consistent order which works across chunk-boundaries, registers, instructions and memories. I
> failed to find a Little-Endians' system which is totally consistent.

Which kind of contradicts his previous text sections covering little-endian:

e.g.

> When they add the bit order and the byte order they get:
>
> ```
>                ...|---word2---|---word1---|---word0---|
>               ....|C3,C2,C1,C0|C3,C2,C1,C0|C3,C2,C1,C0|
>              .....|B31......B0|B31......B0|B31......B0|
>
> ```
>
> In this regime, when word W(n) is shifted right, its LSB moves into the MSB of word W(n-1). 4
>
> English text strings are stored in the same order, with the first character in C0 of W0, the next in C1 of W0, and so on.
>
> This order is very consistent with itself, with the Hebrew language, and (more importantly) with mathematics, because significance increases with increasing item numbers (address).

he even lateron sais:

> The Big-Endians struck again, and without any resistance got their way. The decimal number 12345678 is stored in the VAX memory in this order:
>
> ```
>                        7 8  5 6  3 4  1 2
>                   ...|-------long0-------|
>                  ....|--word1--|--word0--|
>                 .....|-C1-|-C0-|-C1-|-C0-|
>                ......|B15....B0|B15....B0|
>
> ```
>
> This ugliness cannot be hidden even by the standard Chinese trick.

**How did the author get to this completely different conclusion on overall consistency?**

An answer does not have to only base on the text, but may also include other sources which might clear up how the statement is sound.

# Answer
The first statement says that there is a *system* that consistently uses the big-endian convention for various things (instructions, registers, etc.) The second statement says that the little-endian *convention* is more elegant ("consistent with itself").

How are these contradictory?
> 3 votes

# Answer
In the first statement, the author states that he failed to find a little-endian system that is totally consistent across chunk-boundaries, registers, instructions, and memories.

In the second statement, the author states that the little-endian representations are consistent with Hebrew but the English characters appear to be written backward and he considers this only as an aesthetic problem which was worked around by using Chinese top-down representation.

When the author moved on to compare the floating point number representations in big-endian and little-endian, the little-endian representations were not consistent.

He also states: "Having scored so easily in the floating point department, the Blefuscuians moved to new territories: Packed-Decimal. "

In the third statement, the author moved on from floating point representation to Packed-Decimal where he states that the big-endian struck again by being consistent and the decimal number '12345678' stored in VAX memory is ugly and cannot even be worked around by Chinese top-down representation. VAX is little-endian.

So, in all 3 statements/methods, the author figures that big-endian representations were consistent unlike little-endian.

He concludes by stating that it does not matter whichever way is chosen but it is important that both parties agree upon an order.

The author states: "I do hope that my way will be chosen, but I believe that, after all, which way is chosen does not make too much difference. It is more important to agree upon an order than which order is agreed upon."
> 1 votes

---
Tags: terminology, computer-architecture
---


title: findMax reduce to sort

text:
# Question
Title: findMax reduce to sort
Can I reduce the find max (or find min) problem to the sort problem? Because if so, knowing the lower bound for find max is Ω(n) I can also infer that the lower bound for sorting is Ω(n) too?

I'm confused with this spread of lower bounds and applicability of reductions.

# Answer
After you sort an array, the minimum can be found in the first position, and the maximum can be found in the last position. This reduces finding the minimum and maximum to sorting an array. However, sorting is actually more difficult than just finding the minimum or maximum, so it's not clear what this reduction is good for.
> 1 votes

# Answer
You've mostly got it. You also have to add in the time that the reduction takes: usually reductions are to show that something is in $P$ vs $NP$, so what matters is "poly-time" versus "not poly-time", but here you're going more fine-grained.

This is the basic structure you're looking for:

* You can solve `FindMax` by calling `Sort` and then doing $O(1)$ work (taking the first/last element of the array, depending which way your sorting goes).
* Therefore, if you could solve `Sort` in less than $O(n)$ time, you could solve `FindMax` in less than $O(n)$ time.
* It's known that `FindMax` can't be done in less than $O(n)$.
* Therefore, you can't solve `Sort` in less than $O(n)$.
> 0 votes

---
Tags: reductions, sorting, lower-bounds
---


# Question
Title: MergeSort k arbitrary words in linear time
Given $k$ arbitrary words, such as $\\{\text{"fjqke"}, \text{"gbqig"}, \text{"a"}\\}$, is there a way to mergesort these words in linear time so that the final output would be "abefgggijkq"? I tried to approach it by first sorting all the words independently and then merging the words into the final output, but sorting all the words takes $O(kn\log n)$ time.

# Answer
**General case:**

If there is a linear time sorting algorithm $\mathcal{A}$ for this problem, then one can divide a list into random parts, and use $\mathcal{A}$ to sort. But comparison based sorting has a lower bound $\Omega(n \log n)$. Therefore there is no such algorithm $\mathcal{A}$.

Note: Merge routine combines sorted arrays into one sorted array. There is a similar problem to your problem called k-way merging, but that is also required sorted arrays. The complexity of k-way is $\mathcal{O}(n \log k)$

**Finite alphabet case:**

If we assume that the alphabet is finite, and in your case it seems only lower case letters then one can use the Counting Sort algorithm.

Assuming that the total length of the words is $n$ and there are at most $t=26$ letters, the Counting sort can sort this array in $\mathcal{O}(n+t)$-time.

To achieve this with Counting sort, you need to convert this into an array and map the letters with an integer. And, call;

```
 countingSort(array,26)

```

The Counting sort is not in-place. The space requirement for this question is $\mathcal{O}(t)$

* Note 1: Counting sort is not a comparison based sorting algorithm, it uses counting, thus it is not bounded by the lower bound of the comparison based sorting algorithms.
* Note 2: Counting sort, also, can be implemented stable.
> 2 votes

---
Tags: algorithms, sorting, efficiency, mergesort
---


# Question
Title: Complexity of an instance of a NP-complete problem
I am trying to prove the NP-Completeness of problem **\[A\]**.

I know there is a well-known NP-Complete problem called problem **\[B\]**.

I can model **\[A\]** into an instance of **\[B\]** (**\[B\]** is a very general problem and when I assign some edges a weight value then it becomes **\[A\]**).

Is this sufficient to say **\[A\]** is NP-Complete?

# Answer
> 0 votes
To show $A$ is NP-complete, you need to prove the following:

1. $A \in \mathbf{NP}$
2. $A$ is *NP-hard*: any problem $B \in \mathbf{NP}$ is *poly-time* (many-one) reducible to $A$

**or**

equivalently (because reduction relations are transitive): there is an NP-hard problem $B$ which is *poly-time* (many-one) reducible to $B$.

You have shown neither, so you cannot say $A$ is NP-complete.

What you did do is a many-one reduction from $A$ to $B$, but you want *the other way around*. In addition, you also need to show the reduction is *efficient*, that is, takes polynomial time; you did not explicitly state whether this is the case. And, of course, you must not forget to show $A \in \mathbf{NP}$ (which is usually the easier part).

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


# Question
Title: A context-free grammar for all strings that end in b and have an even number of bs
I'm trying to find CFG's that generate a regular language over the alphabet {a b}

I believe I got this one right: All strings that end in b and have an **even** number of b's in total:

$\qquad S \to SS \\ \qquad S \to YbYb \mid \varepsilon \\ \qquad Y \to aY \mid \varepsilon$

However, Im not sure how to accomplish this with an odd number of *b*'s.

So for example, how could I find a CFG that generates all strings that end in b and have an **odd** number of b's in total: So far I have this,

$\qquad S \to SS \\ \qquad S \to YYb \mid \varepsilon \\ \qquad Y \to abY \mid baY \mid \varepsilon$

But this can generate abababb so it's incorrect and Im stumped at this point.

# Answer
> 1 votes
Assuming $\Sigma = \\{a, b\\}$ this probably should do the trick

$\qquad S \to Yb\\ \qquad Y \to YXbXb \mid X \mid \varepsilon \\ \qquad X \to Xa \mid \varepsilon$

This should work because Y always has even number of *b*'s and *S* adds one *b* at the end which makes number of *b* odd.

# Answer
> 4 votes
There is an easy and very natural way how to derive a context-free grammar $G=(V,\Sigma,R,S)$ from a DEA $M=(Q,\Sigma,\delta,q\_0,F)$. We set

* $V=Q$
* $S= q\_0$
* $R$ consists of the following rules:
    + for all $X\in Q$ and $a\in \Sigma$ with $Y=\delta(X,a)$ we add the rule $X \to aY$
    + for all $X\in F$ we add the rule $X \to \varepsilon$
    + there are no other rules in $R$

It's an easy exercise to show that $L(G)=L(M)$. With this technique you can now build your automaton first (which is an easy two-state example in your case), and then apply this construction.

# Answer
> 1 votes
You mention correctly that the language is regular, so a regular grammar is the easiest way to go:

$\qquad \begin{align} S &\to aS \mid bT \\ T &\to aT \mid bS \mid b \end{align}$

This solution uses the "counting" trick: we store in the "state" (whether we have $S$ or $T$ in the sentential form) whether we have generate an even number of $b$ so far.

# Answer
> 0 votes
In both cases (even number of b's and odd number of b's) the language cannot contain empty string ε as in the question in both cases it is mentioned that each string must ends in b. But ε does not end in b, therefore:

1) For even number of b's and ends in b:

S → TbTb

T → aT | bTb | ε

2) For odd number of b's and ends in b:

S → Tb

T → aT | bTb | ε

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


# Question
Title: propositional Modal logic filtration definition
Hello I have a slightly unusual question which relates to a definition of filtration structure. The following is my current state of the definition:

$ \mathcal{M} = (W, R, L) $, W is a set of worlds, $R$ is a binary relation on the worlds, $ R \subseteq W \times W$, and $L$ is a labelling function $ L : W \rightarrow\ \mathcal{P} (PropAtoms) $, here $PropAtoms$ is the set of atomic formulas.

Let $ \mathcal{M} = (W, R, L) $ be a Kripke model and let $\Gamma$ be a set of formulas that is closed under subformulas. Now, for each world $ w \in W$ we define the following: $ \Gamma\_{w} = \\{ \psi \in \Gamma : (\mathcal{M},w) \vDash \psi \\}$,

that is, $\Gamma\_{w} $ contains formulas from $ \Gamma $ that are true at $w$ and consequently in model $\mathcal{M}$. Next we define an equivalence relation $\sim\_{\Gamma} $ on worlds $w, w' \in W$, $ \sim\_{\Gamma} w w' $ if and only if $\Gamma\_{w} \sqsubset \Gamma\_{w'}$, that is, worlds $w$ and $w'$ are equivalent if and only if they satisfy the same formulas in $\Gamma$. We also have equivalence classes $\[w\]$ of worlds $w$ with respect to $\sim\_{\Gamma}$.

Lets now present the following quotient structure $ \mathcal{M}\_{\Gamma} = (W\_{\Gamma}, R\_{\Gamma}, L\_{\Gamma})$ which is in fact filtration of $\mathcal{M}$ with respect to $\Gamma$. $\mathcal{M}\_{\Gamma}$ is defined as follows: .........

Here is the bit I need help with, I am struggling to define my filtration model. This is mainly because the definitions online don't use the same labelling function but rather use a valuation function which is of the form $v(p)$. And such function takes an atomic formula whearas my labelling function takes in a specific world written $L(x)$. **Could someone please help me our here and try providing correct definition which will match my model $M$ definition?**

# Answer
You are probably looking for something like: $L\_\Gamma(\[w\]) = L(w) \cap \Gamma$. This will falsify any propositional letter not in $\Gamma$.

(Filtration is (afaik) usually defined as a property that a model may have. There could be several (or none) concrete models satisfying this property.)
> 0 votes

# Answer
You got quite close to the final model.

Keeping your $\mathcal{M} = (W, R, L)$, $\Gamma$, $\sim\_{\Gamma} $ on worlds $w, w' \in W$, and $\[w\]$ of worlds $w$ with respect to $\sim\_{\Gamma}$. Define further $W\_\Gamma = \\{ \[w\] \mid w \in W \\}$.

Suppose that $\mathcal{M}^f = (W^f, R^f, L^f)$ is *any* model satisfying

* $W^f = W\_\Gamma$,
* If $Rwv$ then $R^f\[w\]\[v\]$
* If $R^f\[w\]\[v\]$ then for all $\Diamond \phi \in \Gamma$, if $\mathcal{M}, v \Vdash \phi$ then $\mathcal{M}, w \Vdash \Diamond \phi$
* $V^f(p) = \\{ \[w\] \mid\mathcal{M}, v \Vdash p \\}$ for all $p$ in *PropAtoms*.

Then $\mathcal{M}^f$ is called a *filtration of $\mathcal{M}$ through $\Gamma$*.

Now, for your question on *construction*. The above restrictions only impose restrictions on $R^f$:

Let

1. $R^s\[w\]\[v\]$ if and only if $\exists w' \in \[w\], \exists v' \in \[v\] . Rw'v'$
2. $R^l\[w\]\[v\]$ if and only if for all formulae $\Diamond \phi$ in $\Gamma$, $\mathcal{M}, v \Vdash \phi$ implies $\mathcal{M}, w \Vdash \phi$

These two give rise to the largest and smallest filtrations, $(W\_\Gamma, R^s, L^f)$ and $(W\_\Gamma, R^l, L^f)$.

Based on P Blackburn, M De Rijke, and Y Venema. "Modal Logic (Cambridge Tracts in Theoretical Computer Science)." (2002), pp 77-80.
> 0 votes

---
Tags: complexity-theory, logic, finite-model-theory
---


# Question
Title: invite 12 person from 24 that we have 6 men and 6 womens
i had a question and its

"A man has 5 female and 7 male friends and his wife has 7 female and 5 male friends. In how many ways can they invite 6 males and 6 females if husband and wife are to invite 6 friends each? Answer. 267,148."

i tried to have cases by that each person invited six and total of 6 females and 6 males

1 = 5 mens * 1 female \+ 1 man * 5 females and cont

and then sum them up but the answer was less than the answer given it was 1848

# Answer
Say the man invites 2 of his male friends so he has to invite 4 female friends to get to a total of 6. The female fills the gaps - she invites 4 male friends and 2 females. Now the guy has C(5,4) options to invite female friends and C(7,2) for his male friends in this example. The female has C(7,2) for the female part and C(5,4) for the male part.

Now you sum over all variants:
> 2 votes

---
Tags: combinatorics, discrete-mathematics, permutations
---


# Question
Title: Constructive proof to show the quotient of two regular languages is regular
I have a question regarding the quotient of two regular languages, $R$ and $L$.

I saw the answers to this question: are regular languages closed under division and the proof sketch is not constructive, because $L$ can be any language. I'm thinking about a constructive proof when $L$ is regular: how can we construct that $F2$ group in the case when $L$ is regular?

We can't go over every word $x$ in $L$ and check if $\delta(q,x)\in F1$ in the case when $L$ is infinite...

# Answer
> 4 votes
In the question you link to, the automaton for the operation "division" (usually known as "quotient") $L\_1/L\_2$ is obtained from a FSA $M\_1 = (Q,\Sigma,\delta,q\_0,F\_1)$ for $L\_1$ by changing the final states. The new states are given as $F\_2=\\{q\in Q \mid \delta(q,x)\in F\_1 \text{ for some } x\in L\_2\\}$.

The quotient is regular for regular $L\_1$ even when $L\_2$ is arbitrarily complex.

> We can't go over every word $x$ in $L\_2$ and check if $\delta(q,x)\in F\_1$ in the case when $L$ is infinite...

You are right that in general the construction is not effective. We just know how the final states are chosen, but we cannot definitely say which states are final. But in case $L\_2$ is regular, we *can* determine which states are final, as regular languages are closed under intersection.

For any state $q$ change $M\_1$ simply by setting $q$ as its new initial state (instead of $q\_0$): $M\_q = (Q,\Sigma,\delta,q,F\_1)$. Now $q$ is final (in $F\_2$) iff the intersection $L(M\_q) \cap L\_2$ is nonempty. Because any $x$ is the intersection is precisely an $x\in L\_2$ for which $\delta(q,x)\in F\_1$ as required.

# Answer
> 4 votes
The quotient of two languages $R$ and $L$ is $$R/L = \left\\{x\in \Sigma^{\*} : \exists y \in L. xy \in R\right\\}$$

Here is a constructive solution using a non-deterministic finite automaton (NFA) to show $R/L$ is regular when both $R$ and $L$ are regular.

Let $(Q\_1,\Sigma,\delta\_1,s\_1,F\_1)$ and $(Q\_2,\Sigma,\delta\_2,s\_2,F\_2)$ be deterministic finite automata for $R$ and $L$ respectively. Define a NFA

$$D=(Q\_1 \times \\{s\_2\\} \times \\{1\\} \cup Q\_1 \times Q\_2\times \\{2\\}, \Sigma, \delta, (s\_1,s\_2, 1), F\_1 \times F\_2\times \\{2\\})$$ where the transitions are:

* $\delta((q\_1,s\_2,1),\sigma) = \\{ (\delta\_1(q\_1,\sigma),s\_2, 1)\\}$.
* $\delta((q\_1,s\_2,1),\epsilon) = \\{ (q\_1,s\_2, 2)\\}$.
* $\delta((q\_1,q\_2,2),\sigma) = \\{ (\delta\_1(q\_1,\sigma),\delta\_2(q\_2,\sigma), 2)\\}$.

I'll leave it as an exercise for you to verify the language accepted by $D$ is $R/L$.

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


# Question
Title: set cover where only certain special subsets are allowed
I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate enough for my needs.

Specifically I have a fixed, finite, list of special sets and I am trying to create a function which when given a set returns the smallest list of special sets which cover that given set, and that list should contain no sets which contain elements not in that given set. The fixed list seems like it should make the problem easier to solve than set cover, but I'm not sure how the additional requirement of no extra elements affects the difficulty. My sets also have a known maximum size which should also make this easier to solve.

A toy version of the problem is as follows:

> Let $U$ be the set $\\{a,b,c,d,e,f,g,h\\}$. All the sets we mention from here on will be subsets of this set.
>
> Let $S$ be a list of special sets. For this version of the problem we can use the following list:
>
> $$ S = \[\\{a,b,c,d,e,f,g,h\\}, \\{a,b,c,d\\}, \\{e,f,g,h\\}, \\{a,e\\}, \\{b,f\\}, \\{c,g\\}, \\{d,h\\}, \\{a,b\\}, \\{b,c\\}, \\{c,d\\}, \\{d,e\\}, \\{e,f\\}, \\{f,g\\},\\{g,h\\}, \\{a\\}, \\{b\\}, \\{c\\}, \\{d\\}, \\{e\\}, \\{f\\}, \\{g\\}, \\{h\\}\]$$
>
> For a given set $G$ what is the smallest list of sets which are part of $S$ which cover $G$, (that is where the union of the sets in the list is $G$).

For the above toy problem, the greedy approximation I've implemented, if presented with a set like $\\{b, c, g, h\\}$, produces $\[\\{c, g\\}, \\{b\\}, \\{h\\}\]$ instead of the smaller list $\[\\{b, c\\}, \\{g, h\\}\]$.

Has this sort of problem been well studied? Is there a known non-approximate algorithm given the additional constraints, that would be better than naive dynamic programming? A well-known name for the version of set cover where extra elements are not allowed would also be useful.

# Answer
Your problem is hardly easier than the general set cover problem.

Given a set $G=\\{b, c, g, h\\}$, we remove all elements in $S$ that are not contained in $G$, obtaining a collection of set $C=\[\\{c,g\\}, \\{b,c\\}, \\{g,h\\}, \\{b\\}, \\{c\\}, \\{g\\}, \\{h\\}\]$. Now the problem becomes the standard set cover problem with $G$ being the universe and a collection of 7 subsets. Since this reduction process takes $O(n^2)$ time where $n$ is the total number of elements in $U$, your problem cannot not significant easier than the general set cover problem unless there are further conditions to be exploited.

Unfortunately, the general set cover problem is NP-hard. It is one of Karp's 21 NP-complete problems. Even more unfortunately, the simple greedy algorithm achieves about the best approximation ratio, $H(s')$, where $S'$ is the maximum cardinality of the sets. Here $H(n)$ is the $n$-th harmonic number.

If you have to obtain the exact minimum set cover, you will have to resort to exponential algorithms. One simple simplification that can be done is to remove all elements in $C$ that are subsets of another element of $C$. That is, we can replace $C$ by $\[\\{c,g\\}, \\{b,c\\}, \\{g,h\\}\]$. A simple brute force algorithm is just to test all subsets of $C$ of size 1, those of size 2, those of size 3, etc. A common way to attack the problem is by integer linear programming.

Just in case, you might want to take a look at some literature on the set cover problems. For example, An Exact Algorithm for Unicost Set Covering and LP techniques for set cover.
> 1 votes

# Answer
I am trying to solve a problem that is some how similar to the set cover problem and would like to share my thoughts. What about trying an SMT solver or CSP solver?. However, I don't know yet if one of them would give better results
> -1 votes

---
Tags: dynamic-programming, approximation, sets, greedy-algorithms, set-cover
---