# Question
Title: 3-SAT reduction to jobs scheduling problem (np-completeness)
In this paper with the title of "NP-Complete Scheduling Problem" by J. D. Ullman, I am trying to understand the reduction from 3-SAT problem to a scheduling problem in order to prove the later is also np-complete. An instance of 3-SAT is given as below:  and this is the instance of the scheduling problem defined as: Single Execution Time Scheduling Problem with a variable number of processors.

I can not totally understand the mapping between the two problems. Any hints that could help me getting the idea?

# Answer
> 2 votes
I see that you have posted this question before with no luck, and I think that this might be due to the amount of work needed to the answer such an open question. I looked at it also when you posted the first time, but needed a couple of hours to read through the proof and would have needed another couple of hours if I should have written a clear explanation for you (I know you are just asking for hints, but they are hard to give when I do not know which parts you already understand and which you don't). I at least, for one, would have been more inclined to write you an answer if you had asked more specific questions to the reductions, like e.g. what a role of a certain job is, or the like.

Also, your question does not contain all the info needed to answer, so one has to download the paper to find the relevant information oneself, and many people probably never go to that step, even when they are actually able to answer. You should have posted at least the definition of P4 and the time limits, and preferably also the example you posted in your last post, but with the explanation of the example and not just the table.

But, alas, after all this explanation of why you might not have gotten any answers, I really like these puzzle-y reductions so seeing that you posted again I made this little picture that can hopefully be of some help.

If you have questions after this, you are very welcome to write some (specific) questions, and I shall see if I can answer.

---
Tags: satisfiability, scheduling, 3-sat
---


# Question
Title: A Question about what it means to Compare two Vectors
Please consider the following question: Given an integer m by n matrix A and an integer m-vector b, the 0-1 integer programming problem asks whether there exists an integer n-vector x with elements in the set ${ 0, 1 }$ such that $Ax \leq b$. Prove that 0-1 integer programming is NP-complete.

Am I correct that $Ax$ is a vector, $b$ is a vector and $Ax \leq b$ is true iff every element of $Ax$ is less than or equal to its corresponding element of $b$?

Thanks, Bob

# Answer
> 1 votes
Yes, element-wise comparison is the usual convention for these constraint problems.

---
Tags: complexity-theory, terminology
---


title: Is this language NP Hard?

text:
# Question
Title: Is this language NP Hard?
$L=\\{$$($$m$,$w$,$n$$)$| $m$ is an encoding of a non-deterministic Turing machine, $w$ is any word/string in the closure of alphabet, i.e. $w\in\Sigma^\*$, $n$ is any positive integer, i.e. $n\in\Bbb{Z}$ and $n\>0$, and $m$ accepts $w$ for a maximum of $n$ moves/steps/operations $\\}$

Alphabet is $\Sigma=\\{0,1\\}$

If this language is NP Hard then what reduction proves it?

My effort to answer this question myself is:

If $L$ is NP Hard then every NP language reduces to $L$ in polynomial time deterministically.

More formally $L\in\Bbb{NPH}\implies\forall L'\in\Bbb{NP}:\\;L'\le\_PL$

Let $L'$ be any arbitrary NP language.

According to the assumption that $L'\in\Bbb{NP}$ by definition of the complexity class $\Bbb{NP}$ exists non-deterministic Turing machine $m$ that decides $L'$ in polynomial time.

This means that for every word/string $w\in\Sigma^\*$:

If $w\in L'$ then $m$ accepts $w$ for a maximum of $c\cdot N^k$ moves/steps/operations

AND

If $w\notin L'$ then $m$ rejects $w$ for a maximum of $c\cdot N^k$ moves/steps/operations

Where $c$ and $k$ are constant non-negative integers and $N$ is the length of $w$.

If $L'\le\_PL$ then exists deterministic Turing machine $m'$ that computes function $f:\Sigma^\*\rightarrow\Sigma^\*$ in polynomial time so that for every word/string $w\in\Sigma^\*$:

$w\in L'\iff f(w)\in L$

Let $m'$ be deterministic Turing machine that in the beginning $m'$ inserts the encoding of $m$ before input word/string $w$, which takes constant time $\mathcal{O}(1)$, because the encoding of $m$ is constant word/string and thus the length of the encoding of $m$ is constant non-negative integer, then $m'$ computes the length of the input word/string $w$ by counting all symbols of $w$, which suppose to take linear time $\mathcal{O}(N)$ where $N$ is the length of the input word/string $w$, then compute the power of the computed length by the constant non-negative integer $k$, which takes polynomial time, then multiply the result by the constant non-negative integer $c$, which also takes polynomial time, and at last append the result after $mw$ and the content of the tape of $m'$ will be $(m,w,c\cdot N^k)$ where $n=c\cdot N^k$

After doing all these actions $m'$ halts.

$m'$ is indeed deterministic Turing machine and runs in polynomial time and $w\in L'\iff (m,w,c\cdot N^k)\in L$ followed by the definitions of complexity class $\Bbb{NP}$ and non-deterministic Turing machines.

Hence by definition $L'\le\_PL$ because of $m'$

Conclusion: For arbitrary language $L'$ I showed that $L'\le\_PL$ holds.

Therefore every NP language reduces to $L$ in polynomial time deterministically and by definition $L$ is NP Hard.

What I wrote above suppose to be a proof that $L$ is NP Hard, but the proof doesn't reduce already proven NP Hard language to $L$, so I think that I did some mistake.

# Answer
> 1 votes
Indeed, this is the prototypical NP-complete language.

Recall what NP-hardness means: For all languages $L'$ in NP, there is a polynomial time reduction from $L'$ to $L$. Normally, when one wants to prove NP-hardness, one takes a language $L''$ which is itself already known to be NP-hard and establishes a reduction from $L''$ to $L$.

But not so in this case! It is much more natural to directly construct a reduction from $L'$ to our $L$, only using the fact that $L'$ belongs to NP.

---
Tags: complexity-theory, turing-machines, np-hard, np, nondeterminism
---


# Question
Title: Assuming that P=NP - Finding an optimal algorithm for 3SAT
Let assume that P=NP so we have both search and decision algorithms for 3SAT at polynomial time.
Can you help me to find an optimal algorithm for optimize 3SAT, i.e.: to find the maximum number of clauses in $\varphi$ that can be satisfied.

Thank you!

P.S.
You can assume that you have search and decision algorithms for 3SAT at polynomial time - so you can use them...

# Answer
> 1 votes
The following language is in NP (why?): $$ \\{ (\phi,k) : \text{$\phi$ is a CNF and there is an assignment satisfying at least $k$ clauses of $\phi$} \\}. $$ I’ll let you finish the proof.

---
Tags: algorithms, optimization, 3-sat
---


# Question
Title: Students in classroom problem - Flow in network
I have room, which is opened some days in week, in different hours each day.

I have multiple students, each has time some days in week, in different hours.

Each student have to visit the room exactly once in the week, for exactly 50 minutes.

Room is unusable for 20 minutes after 2nd student the day, it means, that after the 2nd student have to be at least 20 minute break before 3rd. So something like this:
7:00-7:50
7:50-8:40
(20 mimutes break)
9:00-9:50
There is no break after 4th, 6th, ... student. Only after 2nd one.

How can I find best solution to this? I want to position all (or the most I can) students.

I've thought of using flow in network (see image). Groups (G1, G2, ...) group times (7:00, 7:05, ...) that are within 50 minutes of each other. Pairing student (S1, S2) with time would instantly disable any groups, that contains the time. But that would require to flow going IN-\>Student-\>Time-\> to split into multiple groups -\>Group1+Group2-\>OUT. How can I achieve this? How should I modify maximum flow search algorithms to do so?

Or is there better way how to do what I'm trying to accomplish?

# Answer
> 1 votes
The best way I can see to solve this is with integer linear programming. This is not a polynomial-time algorithm, but it might work well enough in practice. (I don't think network flow algorithms will work here.)

In particular, you introduce zero-or-one variables $x\_{i,t}$, with the intent that $x\_{i,t}=1$ means that student $i$ is scheduled in the room starting at time $t$, or $x\_{i,t}=0$ otherwise. Then you add inequalities to ensure that these meet all of your requirements:

* $\sum\_t x\_{i,t} = 1$: each student is scheduled at a single time.
* $x\_{i,t} + x\_{j,t'} \le 1$ whenever $i \ne j$ and $t,t'$ are within 50 minutes of each other: no two students may be scheduled at an overlapping time.

Then you feed this to an off-the-shelf ILP solver and ask it for a feasible solution. The result is a valid schedule.

As described above, I have ignored the requirement about the 2nd student of the day. You can fix this by adding some extra variables and inequalities. Let $y\_{i,t}=1$ if student $i$ is assigned at time $t$ and is the first student assigned that day, and $z\_{i,t}=1$ if student $i$ is assigned at time $t$ and is the second student assigned that day. Then we have additional constraints:

* $y\_{i,t} \le x\_{i,t}$, $y\_{i,t} + \sum\_j \sum\_{t' \< t} x\_{j,t'} \le 1$, $x\_{i,t} - \sum\_j \sum\_{t' \< t} x\_{j,t'} \le y\_{i,t}$, and $\sum\_i \sum\_{t \in D\_k} y\_{i,t} = 1$ where the last sum is over all $t$ that fall on day $k$ (on the same day). These ensure that the $y$'s are consistent with the $x$'s.
* $z\_{i,t} \le x\_{i,t}$, $z\_{i,t} \le \sum\_j \sum\_{t' \< t} y\_{j,t'}$, $x\_{i,t} - 2 + \sum\_j \sum\_{t' \< t} (x\_{j,t'} - M z\_{j,t'}) \le z\_{i,t}$, $\sum\_i \sum\_{t \in D\_k} z\_{i,t} = 1$ where the last sum is over all $t$ that fall on day $k$ (on the same day) and where $M$ is sufficiently large (e.g., at least the number of students). These ensure that the $z$'s are consistent with the $x$'s.
* $z\_{i,t} + x\_{j,t'} \le 1$ whenever $i\ne j$ and $t,t'$ are within 110 minutes of each other: this ensures a 20-minute gap after the second student of the day.

This should enforce the additional constraints. Double-check the formulation; I haven't checked it carefully, and there might be small errors in what I wrote. In general, Express boolean logic operations in zero-one integer linear programming (ILP) gives some helpful tips on encoding constraints into linear inequalities for ILP.

---
Tags: network-flow, scheduling, matching, assignment-problem
---


# Question
Title: When using resolution variable elimination to simplify a cnf, does that change the truth values of the other variables?
When you use resolution variable elimination to preprocess/simplify a formula in cnf form the resulting formula is equisatisfiable.

What I wonder about is if I can use this technique to remove variables i don't care about while leaving the truth values of the variables I care about untouched in the final model I get from the sat solver.

# Answer
> 1 votes
Yes, you can. Any satisfying assignment for the simplified formula can be extended to a satisfying assignment for the original formula, by setting appropriate values to the eliminated variables (but not changing the values of the remaining variables), and vice versa.

---
Tags: satisfiability, boolean-algebra
---


# Question
Title: What is +1 in binary search time complexity
Why is binary search time complexity for worst case log (n) + 1 instead of just being log(n)? the way I understand it, the number of times we divide the list till we find our desired element is log (n) times in the worst case scenario. Where does this extra 1 come from? (it's log (n) + 1 according to the power point of my class)

# Answer
The exact number depends on your assumptions, so either is defensible. If you assume that the number you're searching for is definitely in the list, and it's just a matter of finding it, then the number of comparisons needed can be as large as $\lceil \lg n \rceil$, and won't be any larger than that. (Here $\lceil \cdot \rceil$ represents rounding up to the nearest integer.) Since $\lceil \lg n \rceil \le 1 + \lg n$, it is not unreasonable to describe the worst-case number of comparisons needed as $1 + \lg n$. Again, as a reminder, this assumes that the number you're searching for is definitely present.

That said, in theoretical analysis, we usually ignore constant factors. So, we summarize the running time as $O(\lg n)$. For these purposes, there is no difference between $\lg n$ or $\lg n+1$; they are both $O(\lg n)$.
> 1 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: How "meaningful" is Turing test? Are there better measures?
How "meaningful" is Turing test?

Because even though it's sometimes presented as a "scientific" way of classifying the goodness of AI, I do view it as a sort of naive, left-handed way for defining or measuring computer intelligence.

Because there are many more aspects to computer intelligence than mere "whether it can trick some people into believing that they talk with a human". Sure if the computer can answer any question similarly to how a humans expert would, then that would be pretty "hard", but computer intelligence is not there yet and it's unsure, whether it'll ever be due to the long-known differences between formal and informal semantics. It could be just a problem of inhuman system design capability. That is, no-one can ever in practice develop a computer program that's that good. It would just be too large.

Nowadays intelligence of computer programs could be measured by e.g. quantities of statements that they can evalute. That is, just the number of possibilities that they're able to process. Because even the goal of the Turing test would be a computer program with large enough database and large enough semantic analyzer and reasoner.

So, are there better measures?

# Answer
> Nowadays intelligence of computer programs could be measured by e.g. quantities of statements that they can evaluate.

So, the trick, is that the Turing Test was meant for an evaluation of *strong AI*: could there be a computer program that was as intelligent as a human? So evaluating statements isn't enough, since humans can do much more than that.

There are some things to keep in mind. First, while some people use the Turing Test as a metric of the quality of chatbots today, that wasn't necessarily its original intent. It was more of a thought experiment, trying to answer the question of "what does it mean for an AI to be intelligent?"

Secondly, the test wasn't mean to strictly evaluate the "question and answer" ability of an AI. It was more saying, "if there's an AI so good we can't distinguish it from a human, is there any meaningful difference?" It was a way to define sentience without bringing in complex philosophical (or possibly even religious) arguments about what is and isn't alive. The Turing Test says "if it looks sentient, we'll say it is, because there's no meaningful way to tell otherwise".

> That is, no-one can ever in practice develop a computer program that's that good. It would just be too large.

There are many possible ways around this. One is that we might not write every aspect of a program, but evolve one. We could write a program that writes a program that writes a program etc, each one being slightly more intelligent until it converges on something powerful.

Or, an AI could be developed from machine learning. With enough time and data, something close to human intelligence could grow from statistical observations, having the headstart of hand-coded AI at its core.

If a human brain is enough for human intelligence, a comparably complex program should be as well. But even if no such program is ever developed, the Turing Test still holds meaning as a thought experiment.
> 5 votes

---
Tags: turing-test
---


# Question
Title: Construct initial marking for marked graph so that the graph is live and safe
I am learning something about P/T petri nets from the book from Wolfgang-Reisig authors and on the seventh chapter's end there is an exercise I can not really work out.

It asks me to construct initial marking such that the following marked graph is live and safe. Note that yellow highlighted place is for the latter part of the question and does not bear any other special significance.

Right after this exercise, there is following task, which asks me to do this: *Show that the initial marking of each marked graph can be modified such that live and safe marked graph is obtained.*

Based on that, I assume that **it must be possible** for any marked graph to have initial marking such that the graph is live and safe. But still I was not able to construct such initial marking. Is there an algorithmic approach to the task? And if I were to remove the highlighted part of the marked graph, would it still be possible to construct such graph?

# Answer
Why can't you find a live and safe marking?

Number the transitions from left to right $t\_1,t\_2,t\_3,t\_4,t\_5$ and the places from left to right $p\_1, \ldots, p\_{12}$,

We need to find a firing sequence that is possible, fires all transitions at least once, has net effect zero, and never produces an unsafe marking.

It doesn't matter where we start: if the net is live, we can "cycle" any such firing sequence by moving its starting transition to the end or vice versa.

So we may as well start with the "thick" transition in the middle, $t\_2$. For it to be enabled, its input places must be marked. In order for the firing sequence we'll construct to be safe, its output places must be empty. So let's fire it. Now, its input places are empty, and its output places are marked. We must now be able to fire $t\_3,t\_4,t\_5$. This is possible iff exactly one of $p\_9,p\_{10},p\_{12}$ was (and is) marked. We can then fire all three in a row. So let's pick $p\_9$ as the one that was set. Then, after firing $t\_2$, $t\_3$ will be able to fire; firing it will enable $t\_5$; firing that will enable $t\_4$; firing that will put the token back into $p\_9$.

After firing $t\_3$, $p\_4$ will be set, enabling $t\_1$. The firing of $t\_1$ and of $t\_3,t\_5,t\_6$ are independent: they don't influence each other.

Having fired both $t\_1$ and $t\_3,t\_5,t\_6$, we're back at our initial marking. The net doesn't actually give us a choice: we must fire $t\_3$ first, and then both $t\_1$ and the sequence $t\_5,t\_6$ to enable $t\_2$, and no alternative firing sequences exist.

So with the initial marking $p\_2,p\_6,p\_8,p\_9$, the only possible firing sequences of this net are given by the regular language $(t\_2t\_3(t\_1|t\_5t\_4))^\* = (t\_2t\_3(t\_1t\_5t\_4 \cup t\_5t\_1t\_4 \cup t\_5t\_4t\_1))^\*$. All of the reachable markings are safe.

By the way the example is drawn, there appears to be theory behind this example. This marked graph is special in that it is composed from three plain cycles (the ovals) by fusing some of their transitions. I'll bet Reisig's book proves that all marked graphs constructed in such a way are live and safe.

Your second question: what if we remove the place marked in yellow? Well, this only removes a constraint on the firing sequences: all existing firing sequences will continue to exist, but new ones may arise.

Indeed: after $t\_4$ has fired, or in the initial marking above, $t\_3$ can now already fire before $t\_2$. However, this is merely a relaxing of the order in which transitions are fired, and it doesn't produce any unsafe or unlive markings. So the net remains live and safe. I suppose you'll have to prove this.

I'll guess there is another lemma in the book proving that this is true in general: that removing places from a live and safe marked graph always leaves it live and safe. I haven't read the book, so I'm not sure.
> 1 votes

---
Tags: petri-nets
---


# Question
Title: What is the asymptotic time complexity of the following 2 recurrences?
$$T(n) = (\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$

and

$$T(n) = (n\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$

for any given $i$ and $k$.

I think it helps to know that for $0\<j\leq 1$

\begin{equation} \lim\_{n\to\infty} \frac{n/n^j}{n/\log n} = 0. \end{equation}

But what is a simple way to derive the asymptotic time complexity for the two given recurrences?

# Answer
> 0 votes
For the first recurrence, let $n\_0 = n$ and $n\_{t+1} = n\_t/\log n\_t$. As long as $n\_t \geq \sqrt{n}$, we have $n\_{t+1} \leq n\_t/\log \sqrt{n\_t} = n\_t/((1/2)\log n)$, and so we reach $\sqrt{n}$ in $\log\_{(1/2)\log n} n \approx \log n/\log \log n$ steps. It takes us another $\approx (1/2) \log n/\log \log n$ steps to get to $\sqrt\[4\]{n}$, and so on. If you do the calculation in full, you will probably find out that $n\_m = O(1)$ for $m = O(\log n/\log\log n)$. In other words, for a constant fraction of the sequence $n\_0,\ldots,n\_m$, the value of $\log n\_t$ is $\Theta(\log n)$. This justifies the approximation $n\_t \approx n/\log^t n$. Under this approximation, we find out that (ignoring the $\Theta$) $$ \begin{align\*} T(n) &\approx n^i \log^k n + \log n \cdot (n/\log n)^i \log^k n + \log^2 n \cdot (n/\log^2 n)^i \log^k n + \cdots \\ &\approx n^i \log^k n + n^i \log^{k-(i-1)} n + n^i \log^{k-2(i-1)} n + \cdots \end{align\*} $$ The answer now depends on the value of $i$. If $i \> 1$ then the terms keep decreasing, and so we expect $T(n) \approx n^i \log^k n$. If $i = 1$ then the terms are roughly the same size. Since there are roughly $\frac{\log n}{\log \log n}$ of them, we expect the answer to be $T(n) \approx \frac{\log n}{\log \log n} n^i \log^k n$. If $i \< 1$ then the terms keep increasing, and so we expect the major contribution to come from $$\log n\_0 \log n\_1 \log n\_2 \cdots T(\mathit{const}).$$ By definition, $\log n\_t = n\_t/n\_{t+1}$, and so $$ \log n\_0 \log n\_1 \log n\_2 \cdots = \frac{n\_0}{n\_1} \frac{n\_1}{n\_2} \frac{n\_2}{n\_3} \cdots \approx n. $$ So in this case, $T(n) \approx n$.

---

If we do the same for your second recurrence, we get $$ T(n) \approx n^i \log^k n + n \log n \cdot (n/\log n)^i \log^k n + n \log n \cdot (n/\log n) \log n (n/\log^2 n)^i \log^k n + n \log n \cdot (n/\log n) \log n \cdot (n/\log^2 n) \log n (n/\log^3 n)^i \log^k n + \cdots \approx \sum\_{t=0}^m \frac{(n \log n)^t}{\log^{\binom{t}{2}}n} (n/\log^t n)^i \log^k n = n^i \log^k n\sum\_{t=0}^m n^t \log^{-t(i-1)-\binom{t}{2}} n $$ Let us denote the $t$th term in the sum above by $S\_t$. Then $$ \frac{S\_{t+1}}{S\_t} = \frac{n}{\log^{i+t+1} n}. $$ For the largest $t$ we consider, $\log^t n \approx n$, and so we expect the largest term to be near the end. This implies that $$ \begin{align\*} T(n) &\approx n\_0 \log n\_0 \cdot n\_1 \log n\_1 \cdot n\_2 \log n\_2 \cdots \\ &= \frac{n\_0^2}{n\_1} \frac{n\_1^2}{n\_2} \frac{n\_2^2}{n\_3} \cdots \\ &= n\_0 n\_1 n\_2 \cdots. \end{align\*} $$ The approximation $n\_t \approx n/\log^t n$ seems harder to justify in this context, but it should give us a ballpark estimate: $$ n\_0 n\_1 n\_2 \cdots \approx n \cdot \frac{n}{\log n} \cdot \frac{n}{\log^2 n} \cdots \approx \frac{n^{m+1}}{\log^{\binom{m}{2}} n}. $$ We chose $m$ so that $\log^m n \approx n$, and so we expect the ratio to be $n^{\Theta(m)}$. In other words, $T(n) \approx n^{\Theta(\log n/\log \log n)}$.

---

All the estimates above are non-rigorous, and for this reason, they could be wrong. However, they point the way toward a more rigorous treatment.

---
Tags: complexity-theory, algorithm-analysis, time-complexity, asymptotics, runtime-analysis
---


title: Consistent heuristic and A*

text:
# Question
Title: Consistent heuristic and A*
The following graph has consistent heuristic.

An A\* algorithm will alter its first guess ACD to the correct shortest path ABD... if it has consistent heuristic, doesnt it mean, that AB should be found before AC?

# Answer
> 1 votes
A\* isn't finished until all nodes with $f(n) \< f(goal)$ are expanded.

So even though you have added $D$ to the open set you still need to expand $B$ because $f(B) = 11 \< f(D) = 17$ after which $f(D)$ will become $12$

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


# Question
Title: how to prove a simple graph with this question
) Suppose G is a simple graph with n vertices. Prove that G has twice as many edges as vertices only if n ≥ 5. ?

Any one can help?

# Answer
> 0 votes
> Prove that G has twice as many edges as vertices only if n ≥ 5

Rephrased: prove that if $n \< 5$, $G$ has fewer than $2n$ edges.

Which simple graph on $n$ vertices has the most edges? How many does it have, as a function of $n$?

# Answer
> 0 votes
in a graph sum of the degree= 2\* number of edges. Let n \< 5 then sum of degree is at most n(n-1), so number of edges is at most n(n-1)/2. Let f(n)= n(n-1)/2. It is easy to show that f(n)\<= 2n when n\<5.

---
Tags: algorithms
---


# Question
Title: Conventions on NP regarding certificates with length exponential in a variable $k$
Non-computer scientist here. Suppose you have a problem of the following general form:

> There is a class of objects, and a restricted set of moves to pass between objects. It is known that all such objects are related by this set of moves. There's a problem of the form "Given two objects $X\_1$ and $X\_2$, can you move between them in at most $k$ moves?"

An example would be where the objects are graphs on the same number of vertices, and the moves are deletion and addition of edges. This question is obviously NP in the sense that you can just list the additions/deletions made to get a certificate.

Now the problem is if there is no a priori upper bound on how many moves you might need to move between two objects. In the previous example, If the graphs have $n$ vertices then you need at most $n(n-1)/2$ additions/deletions to pass between any two graphs (going from $n$ disjoint vertices to the complete graph on $n$ vertices). Thus, asking the question with very large $k\>n(n-1)/2$ can be answered easily, so the problem is in NP regardless of $k$.

However, if there is no such bound, then maybe $k$ could be very large compared to the size of your objects, requiring a large certificate compared to the size of the input (since $k$ only needs $\log k$ bits). So if $k$ is fixed before the statement of the problem then it is in NP, but if $k$ is given together with the input then it is not.

What's the convention for dealing with this type of situation? Do you just say that the problem is NP for any fixed $k$?

# Answer
No, you don't say it is NP for any fixed k, since that's not right; NP means something specific, and that's not it. Instead, I would suggest that you describe the situation, as you did, in a self-contained way, since your definition is different from the ones where we have existing terminology.
> 1 votes

# Answer
In many cases, if you have n objects, then either there is a sequence of at most n-1 moves getting you from A to B, or there is none. This will be clearly in NP.

If you have rules for the moves so that there can be a shortest route with length that is not polynomial in n, then it may be the case that the problem is not in NP.

The same would be the case if the move rules are so complicated that you cannot find whether moving from X to Y is allowed in polynomial time in n.

Remember that to prove that the problem is NP-hard, you need (roughly) to prove that if you are able to solve each "YES" instance in polynomial time, then you can also solve each "YES" instance of some NP-complete problem in polynomial time. And NP-complete just means "NP-hard, but also in NP".
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Any common problems solvable by DFA/NFA or PDA except recognizing languages?
I understand that DFAs recognize regular languages, and PDAs context-free languages, but these are a little bit too theoretical. I am wondering if we can implement common functions or solve common problems with DFAs and PDAs instead of Turing machines (or in a Turing-complete language).

By "common", I mean either one of the following:

1. problems like those in algorithm analysis and data structures, i.e. sorting, shortest path, etc.
2. functions seen in the everyday work of a common programmer, probably some useful business logic.

# Answer
> 1 votes
In imperative programming, state machines are quite common, and they usually look more or less like the following pseudo-code:

```
state = INITIAL_STATE;

while (token = read_an_input_token(input))
{
   if (state == STATE_1)
   {
      if ([some condition on the token])
      {
         [some actions]
         state = [some state]
      }
      else if ([another condition on the token])
      [etc.]
   }
   else if (state == STATE_2)
   [etc.]
}

if (state != ACCEPTING_STATE)
{
   [error handling, perhaps abort]
}
else
{
   [apply finishing touches]
}

```

All kinds of variations may occur: you'll see `case` statements being used in languages that have them, the order in which the conditions are tested and the way they are grouped may vary, more input scanning may occur than just reading separate tokens, et cetera.

You're likely to see similar loops wherever a regular language needs to be parsed. For instance, command line utilities usually parse their arguments in this way. (Mine do, anyway.)

There are other approaches to using state machines in software; I think this is the most popular and most informal one.

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


# Question
Title: Any mathematical tools for analyzing mutable memory
Wondering if there are any documents, theories, or methodologies for dealing with mutable memory mathematically. Basically a formal algebraic model of how computers manipulate memory. Along the lines of, say I want to model an `add` operation at a low level, and it writes its output to a register. Then we can model the computer state as a memory, and:

$$add : a \times b \times m \to m'$$

the function $add$ transforms the memory into a different state, holding the final value. Then the second time we call add, the memory is different than it was before. So it's always changing:

$$m \neq m' \neq m'' \neq \dots \neq m^{(n)}$$

Wondering if there are any formalisms out there that deal with this. I would specifically like to see it applied to abstract algebra or category theory. Whereas in abstract algebra typically, everything is immutable and you never worry about "state". I would like to explore the state / mutable memory from a math framework.

# Answer
See separation logic and theory of arrays in SMT solvers. Both of these provide a principled, mathematically rigorous foundation for reasoning about mutable memory.
> 2 votes

---
Tags: formal-methods, category-theory
---


# Question
Title: Merge Sort meaning of a bit part of code
I am studying this part for a merge sort implementation:

```
void mergeSort(int arr[], int l, int r) {
if (l < r)
{
    // Same as (l+r)/2, but avoids overflow for
    // large l and h
    int m = l+(r-l)/2;

    // Sort first and second halves
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);

    merge(arr, l, m, r);
}}

```

What is the meaning of:

```
    // Same as (l+r)/2, but avoids overflow for
    // large l and h
    int m = l+(r-l)/2;

```

in the code? Why can't I use `(l+r)/2`? (I didn't understand the comment)

# Answer
Because of integer overflow, `(l+r)/2` won't actually compute the midpoint like we want in some special cases. See https://stackoverflow.com/q/17358806/781723 and https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html for details.
> 1 votes

---
Tags: algorithms, sorting, integers, mergesort
---


title: rope data structure - undo operation

text:
# Question
Title: rope data structure - undo operation
I was reading (wikipedia) about how the rope data structure might be suitable for a text editor. Within the article it mentions "If only nondestructive versions of operations are used, rope is a persistent data structure. For the text editing program example, this leads to an easy support for multiple undo levels." I don't understand how the undo works in this.

For example, let's say i had an existing rope with the left leaf as "hello" and the right leaf as "world". The parent (root) would have the value 5 (length of hello). Then, if i were to delete "world" i am just left with the root and left (hello) node. Now, if i wanted to "undo" the delete, haven't I already discarded the "world" node? Traditionally "undo" is done by placing things on a stack, but in this case I don't understand if using a stack what to put on it or how to do the undo in general.

# Answer
> 6 votes
The approach is to build a fully persistent version of the rope data structure. This then lets you keep a pointer to each version of the data structure: you have a pointer to version 1 ("hello world") and version 2 ("hello"). To undo the last operation, you just start working from version 1 rather than version 2. In particular, yes, you can store these pointers in a stack data structure. The point is that each modification creates what is effectively a new *copy* of the data structure, without modifying the old version. Of course, actually making an entire copy would be inefficient, so what the data structure does is share the parts of the tree that are unchanged.

For details on how to make a persistent version of the data structure, see What classes of data structures can be made persistent?. See also Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration.

---
Tags: data-structures, balanced-search-trees
---


# Question
Title: Upper bound derivation of expected time for finding a large cut
Given an undirected graph $G$ with $n$ vertices and $m$ edges, we build a cut as following. Initially sets (of vertices) $A$ and $B$ are empty. For each vertex $v$ we flip a fair coin and according to outcome we put $v$ either in $A$ or $B$.

Let $X$ be a r.v. denoting the cut size, i.e. the number of edges between sets $A$ and $B$. A simple calculation produces $$E\[X\] = \frac{m}{2}$$ (see *Probability and Computing* by M.Mitzenmacher & E. Upfal, pg 130).

Now, let $p = \Pr\left(X \geq \frac{m}{2}\right)$. Then $$ \frac{m}{2} = E\[X\] = \sum\_{i \leq m/2 -1}{i\Pr(X=i)} + \sum\_{i \geq m/2}{i\Pr(X=i)}$$ $$ \leq (1-p)\left(\frac{m}{2}-1 \right) + pm.$$

I understand that for $i \< m/2 -1$, $\Pr(X=i) \leq \Pr(X \< m/2)$ and for $i \geq m/2$, $\Pr(X=i) \leq \Pr(X \geq m/2)$, but I don't understand how the last upper bound is derived.

Can anyone give me a hint or explain the derivation?

# Answer
We can upper bound the first summand by $$ \sum\_{i \leq m/2-1} i \Pr(X=i) \leq \sum\_{i \leq m/2-1} (m/2-1) Pr(X=i) = (m/2-1) \sum\_{i \leq m/2-1} Pr(X=i) = (m/2-1) Pr(X \leq m/2-1) = (1-Pr(X \geq m/2))(m/2-1) = (1-p)(m/2-1). $$ Similarly, we can upper bound the second summand by $$ \sum\_{i \geq m/2} i \Pr(X=i) \leq \sum\_{i \geq m/2} m Pr(X=i) = m \sum\_{i \geq m/2} Pr(X=i) = m Pr(X \geq m/2) = pm. $$
> 2 votes

---
Tags: probability-theory
---


# Question
Title: Alternatives to evolutionary computing for structure, design and policy optimization (optimal structure search)?
I once had this question https://math.stackexchange.com/questions/1083338/structural-design-meta-optimization-is-there-mathematical-theory-optimiza about the methods for finding optimal structures, designs and policies (as another kind of structures - set of rules), i.e. optimization of the structure of the models not just the parameters for some pre-selected structure. So far I am sure that the genes of evolutionary computation (EC) can effectively encode structure and evolutionary computing can perform effective search for more optimal structures. EC algorithms are quite sophisticated - there is evolutionary programming (for search of strings in some grammar) and there is cultural algorithms (which incorporates already known certain knowledge for speedup of the search). **But are there some other kind of search procedures (besides evolutionary computing) for searching more efficient structures. EC is stochastic search methods and is there deterministic search methods for the search of optimal structure?** I expect only key-words, pointers and trends.

Or - more clearly - **is EC the most general search framework? Are there search alogrithms or approaches than can not be reduced to the string of application of crossover, mutation and other operators of EC?**

# Answer
At a broad level, there are two types of optimization: continuous optimization, and discrete optimization. They tend to use different techniques.

Continuous optimization deals with problems where the parameters are continuous; methods include gradient descent, Newton's method, and other iterative methods, linear programming, and more.

Discrete optimization, or combinatorial optimization, deals with problems where the parameters come from a finite site; methods include integer linear programming, SAT, simulated annealing, particle swarm optimization, and more.

Genetic algorithms are another technique. However, my experience is that they are rarely the best one; other methods often beat genetic programming and evolutionary optimization methods. Your experience may vary.
> 1 votes

---
Tags: algorithms, optimization, search-problem
---


# Question
Title: Is it possible to detect a simple negative-weight cycle of weight $N$ in polynomial time?
Given a directed graph and an integer $N$, is it possible to detect a simple negative-weight cycle whose edges sum to $N$ in polynomial time? I thought about modifying the Floyd-Warshall algorithm to check if the diagonals equal $N$ as they get set, but I realized this wouldn't work if a vertex appeared in multiple negative-weight cycles.

# Answer
> 5 votes
No, there isn't (not unless P=NP). Take an unweighted directed graph on $n$ vertices, and set all of the edge weights to $-1$. Now there is a simple cycle of weight $-n$ if and only if there is a Hamiltonian circuit in the original graph. But detecting the existence of Hamiltonian circuits is NP-hard. Therefore your problem is NP-hard, too.

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


# Question
Title: The line-covering step in the Hungarian algorithm
I am trying to understand the Hungarian algorithm for the assignment problem.

I found this presentation which gives an excellent explanation about the algorithm. However, there is one step I do not understand.

Step 3 (pages 13, 16) says "Cover all the zeros of the matrix with the minimum number of horizontal or vertical lines". How can this step be done in polynomial time?

I.e, given an $n\times n$ matrix with some zeros, what is an efficient algorithm for finding the smallest set of rows and/or columns that contain all the zeros?

# Answer
> 4 votes
OK, after reading this much more complicated explanation of the same algorithm, using bipartite graphs instead of matrices, I realized how to find the smallest number of rows/cols.

Given the matrix, create the "graph of zeros" - a bipartite graph where the rows are on one side and the cols are on the other side, and there is an edge between row and column iff there is a zero in their intersection. Then, our problem becomes finding a smallest vertex covering of this graph.

Based on Koenig's theorem, a smallest vertex covering in a bipartite graph can be found using any algorithm for finding a largest matching in the graph, in polynomial time.

---
Tags: algorithms, matrices
---


title: Bloom Filter which does not fit in RAM

text:
# Question
Title: Bloom Filter which does not fit in RAM
Is it possible to efficiently create a bloom filter with 10^12 buckets on a single machine with 32GB of RAM and a hard drive. We can assume that the keys are already on the disk and are small in size?

# Answer
A Bloom filter doesn't have "buckets".

You can make a Bloom filter of any size you want. The smaller it is, the higher the false positive rate.

This should be covered in any good introduction to Bloom filters, of which there are many.
> 1 votes

---
Tags: distributed-systems, hash, bloom-filters
---


title: Equivalent Colorings of Graphs

text:
# Question
Title: Equivalent Colorings of Graphs
Call two proper graph colorings equivalent if one can be obtained from the other by a permutation of the colors. In other words, they are the "same" coloring.

I'm interested in finding proper non-equivalent colorings. Of course, the decision problem of determining whether or not there is such a non-equivalent coloring given one is NP-complete.

Are there FPT, approximation, etc. algorithms for finding such a coloring if one exists? I am currently running a randomized greedy coloring algorithm, which does often succeed in finding a proper coloring - however, I am unsure of when it actually produces a non-isomorphic one.

If it is helpful, I'm working with graphs which are essentially $k$-trees.

# Answer
Many existing heuristics for graph coloring can work even if you specify the colors of a few vertices. So, here is one plausible algorithm you could use:

We are given an existing coloring $C$. Pick two vertices $v,w$ randomly. We are going to assign colors for $v,w$ (in the new coloring), leave the other vertices unassigned, and use some existing graph coloring heuristic to extend this to a coloring for the whole graph. If $C(v)=C(w)$, assign $v,w$ two different colors in the new coloring (any two, it doesn't matter which two colors you use). If $C(v)\ne C(w)$, assign $v,w$ the same color in the new coloring (any color, it doesn't matter which you pick). Then extend this to a coloring for the new graph.

If this finds a coloring, then you're guaranteed that the new coloring will be non-equivalent to the old one. Moreover, if there exists a non-equivalent coloring, you're guaranteed to be able to find it with at most polynomially many invocations of this procedure. In particular, if $C'$ is non-equivalent, there must exist some pair of vertices $v,w$ where $C(v)=C(w)$ and $C'(v) \ne C'(w)$, or where $C(v) \ne C(w)$ and $C'(v) = C'(w)$. Therefore, if you repeat the above procedure for all pairs $v,w$ of vertices, at least one of those iterations should find a new non-equivalent coloring.

So, this might be one reasonable approach, if you want to find a new non-equivalent coloring once. On the other hand, if you are given $m$ existing colorings and want to find a $m+1$st non-equivalent coloring, that looks more complicated.
> 5 votes

---
Tags: graphs, approximation, colorings
---


# Question
Title: If a graph has a unique MST, then its edge weights are distinct. True or false ? Justify your answer.
If a graph has a unique MST, then its edge weights are distinct. True or false ? Justify your answer.

# Answer
> 5 votes
The answer is: not necessarily.

Counterexample: consider a graph that is a tree with all of its edges the same weight. Then the only MST is the entire graph and none of the edge weights are distinct.

---
Tags: graphs, minimum-spanning-tree
---


# Question
Title: DFA for exactly two of a and one or more of b
I'm totally new to DFA's and automaton in general -- this is the first week or two of class that I've actually seen this -- and I'm curious as to a pattern to match the following:

"Match the set of all strings on the alphabet {a, b} that have at least one b and exactly 2 a's"

I've tried to construct a DFA to represent this structure, but I have no idea how to form a structure to count for something and match for one.

Can someone help?

---

Okay, so. Here's what I got and I think it's the right answer.

# Answer
> 2 votes
If you're stuck on problems like this, it often helps to try to construct a regular expression first. Note that it's perfectly acceptable to make it the union of overlapping REs.

The RE $b^\* a b^\* a b^\*$ accepts strings with exactly two $a$'s, but doesn't take into account that there must be a $b$. A $b$ could be in any of the $b^\*$ parts, so this RE accepts the language:

$$(b b^\*) a b^\* a b^\* \cup b^\* a (b b^\*) a b^\* \cup b^\* a b^\* a (b b^\*)$$

Did that help?

# Answer
> 5 votes
Since it's for class, I won't actually build the DFA for you, but I will give you a way to look at it that'll help.

1. As far as $b$s go, you really only care about whether or not you've seen a $b$ so far in the string.
2. As for $a$s, you care about whether you've seen 0, 1, 2, or more.

Each combination of scenarios for both letters (like "seen none of either" or "seen one of each" or "seen one $a$ and no $b$s") changes in its own way depending on whether you read another $a$ or $b$. How might you express that in a DFA?

# Answer
> 0 votes
this Dfa will accept exactly two a's and one or more b. State q3 is having transistion on 'a' to q5(arrow is missing)

# Answer
> 0 votes
This is a good example of the utility of the product construction. If you can construct an automaton for all strings containing at least one $b$, and another automaton for all strings containing exactly two $a$s, then you can take their product to obtain an automaton for the conjunct condition.

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


# Question
Title: How to prove the correctness of the MinDistance algorithm?
My question is about how to prove the correctness of this algorithm, I know it is not a good algorithm, it is not efficient and can be improved. How could I prove it still returns the desired value? What are the loop invariant and variant? How to insert assertions between lines?

The algorithm goes like following,

**Algorithm** MinDistance (A \[0…n-1\])

```
//Input: Array A [0...n-1] of numbers

//Output: Minimum distance between two of its elements

dmin←∞

for i←0 to n-1 do

    for j←0 to n-1 do

        if i≠j and |A[i]-A[j]|<dmin

        dmin←|A[i]-A[j]|

return dmin

```

# Answer
> 1 votes
Define an order of pairs of indices $(i,j)$ according to the order in which they are accessed in your code. At the end of the $(i,j)$th iteration, $dmin$ holds the minimum of $|A(k)-A(\ell)|$ among all pairs $(k,\ell) \preceq (i,j)$ such that $k \neq \ell$. This loop invariant is easy to prove, and implies the correctness of the entire algorithm.

---
Tags: algorithms, correctness-proof
---


# Question
Title: Can anyone find a mapping from the set of all possible string to the natural numbers?
**Can anyone find a map(injection) $h$ from the set of all possible strings $S^\*$ to the natural numbers $\mathbb{N}$**?

$$h : S^\* \rightarrow \mathbb{N} $$

Assume $S$ is finite. I would prefer an efficient map.

There should be nice applications of this question for perfect hashing, right?

# Answer
> 3 votes
Just pretend that your alphabet $S = \\{0, \dots, s\\}$ for some $s$ and then a string in $S^\*$ is just a natural number written out in base $s+1$. There's the slight wrinkle that $0$, $00$, $000$, etc. are all representations of zero, but that's easily fixed by associating the string $x$ with the number whose base-$(s+1)$ representation is $1x$ (i.e., $x$ with a $1$ stuck on the front).

---
Tags: formal-languages, discrete-mathematics, hash, cryptography
---


title: Are hash onions inherently sequential?

text:
# Question
Title: Are hash onions inherently sequential?
An open problem in complexity theory is whether NC equals P.

I'm somewhat confused because I would have thought that it's obvious that NC != P because of hash onions. A hash onion is when you start with some input $i$ and repeatedly hash $n$ times:

$$H(i), H(H(i)), ..., H^n(i)$$

Given an input $i$ the amount of work to compute $H^n(i)$ is $O(n)$ so hash onions are part of P. And because the hash function $H$ acts like a random oracle you can't do better than sequential queries to $H$, therefore hash onions are not part of NC.

What am I missing?

# Answer
For all engineering purposes, you are right, if you choose a cryptographically strong hash function $H$.

For theoretical purposes, nope. There's no proof. Your argument is based on unproven assumptions, hence it can't be regarded as a proof that NC $\ne$ P. In particular, we don't know of any hash function $H$ that we can prove is cryptographically strong, or that we can prove is inherently sequential when repeated like this. All of our hash functions are either heuristic (we think they are good but we have no ironclad proof) or are based on other assumptions (such as that factoring is hard; something we suspect but have no proof of). And assuming that $H$ behaves like a random oracle is an unproven assumption. So if you're a theorist and what you care about is *proving* that NC $\ne$ P, none of these count as a suitable proof.

Personally, I do consider them pretty good evidence that in all likelihood NC $\ne$ P... but it's not a proof.
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: Doubt on declaring an array in pseudocode
So here's the code:-

DECLARE number as INTEGER

PRINT "Enter a number"

INPUT number

DECLARE randomarray \[1:number\] AS INTEGER

Is this possible? i.e whilst declaring arrays, can we use variables?

Note:The question is strictly limited to pseudocode or general programming language

# Answer
Pseudocode is *not* a formally defined programming language. Rather, it refers to textual description of code that is not in "paragraph" form but rather in "code" form. (Paraphrasing Molière, it is a third form of expression, after prose and poetry.)

The only rule in pseudocode is that it should be self-explanatory. If there is anything that the reader might misunderstand, you have to explain it. Otherwise, it's up to you how you write pseudocode, though it's good measure to be consistent in your paper.

Your pseudocode is self-explanatory. You have declared a variable "number" of type integer, printer "Enter a number", read a number from the input into "number", and then declared an integer array "randomarray" of length "number". Moreover, your array is "1-based" (i.e., the first index is 1). If this is what you intended to convey, then you were successful and there is nothing wrong with your pseudocode.

It's good practice to try to emulate the way other people in your field write pseudocode. This will cause your code to look more "standard", and so more "professional" and easier to read. But it's definitely not necessary, and you are encouraged to write the pseudocode in whatever way seems best or nicest to you.
> 1 votes

---
Tags: arrays, pseudocode
---


# Question
Title: What is the meaning of idiosyncratic when refering to multiprocess abstractions?
I am currently reading this paper on library operating systems, more specific on Graphene. I stumbled over the following sentence:

*"Because multiprocess abstractions, such as signals or System V IPC, tend to be idiosyncratic, an essential problem is identifying a minimal, host-independent substrate upon which to implement OS-specific abstractions."* (Page 3, design options paragraph)

But I don't understand what is meant by *idiosyncratic* multiprocess abstractions? What is the meaning of *idiosyncratic* in the context of multiprocess abstractions?

# Answer
Let me rephrase your quote:

> Implementations of multiprocessing in various systems tend to be rather different. Each system uses its own peculiar "vocabulary". When we port each such system to new hardware, we need to code afresh the entire multiprocessing subsystem. One way to address this difficulty is to come up with a small set of multiprocessing primitives which, on the one hand, can be used to implement all the multiprocessing mechanisms in known systems, and on the other hand, is simple enough to code for each particular hardware. This will drastically reduce the effort required in porting operating systems.
> 1 votes

---
Tags: operating-systems
---


# Question
Title: Closure of context-free languages under regular quotient
Knowing that $C$ is a context-free language and $R$ is a regular language, how to prove that $C / R = \\{w| \exists x \in R: wx \in C\\}$ is also a context-free language?

# Answer
> 1 votes
There is a simple proof uses PDAs. Start with a PDA for $C$. Add an $\epsilon$ transition to a copy of the PDA, multiplied by an NFA for $R$. Instead of reading characters from the input, this part guesses them and advances the NFA. The new machine accepts if both the PDA and the NFA accept. Details left to you.

# Answer
> 2 votes
Let me prove the following more general statement:

> Every full trio is closed under right quotient by a regular language.

Let $\mathcal{L}$ be the full trio, let $L \in \mathcal{L}$ be a language over $\Sigma$, and let $R$ be a regular language over $\Sigma$. Let $\Sigma' = \\{ \sigma' : \sigma \in \Sigma \\}$. Define the homomorphism $h\colon \Sigma \cup \Sigma' \to \Sigma$ by $h(\sigma) = h(\sigma') = \sigma$, and define the homomorphism $k\colon \Sigma \cup \Sigma' \to \Sigma$ by $k(\sigma') = \sigma$, $k(\sigma) = \epsilon$. Then $$ L/R = k(h^{-1}(L) \cap \Sigma^{\prime \*} R). $$

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


# Question
Title: number of pair of vertices with at least 2 distinct paths between them in a undirected graph
I need an algorithm to calculate number of pair of vertices with at least 2 distinct paths between them in a undirected graph \- the graph is connected \- distinct paths = distinct edges ex: no. of vert = 3 and no. of edges = 3 and we have (1, 3) (1, 2) and (2, 3) valid paths from 1 to 2 are 1-3-2 and 1-2 \- count only pairs (a,b) with a \< b for example :

> 5(no. of vert) 6(no. of edges) : (1, 2) (2, 3) (3, 1) (3, 4) (4, 5) (5, 4).

Output is 4 :

> (1, 2), (1, 3), (2, 3) and (4, 5).

# Answer
> 1 votes
I'm assuming that you're looking for the number of pairs of vertices having two *disjoint* *simple* paths connected them. A pair of vertices has two disjoint simple paths connecting them if they are in the same biconnected component. You can partition the graph into biconnected components in linear time. If the biconnected components have sizes $N\_i$, then the number of pairs is $\sum\_i \binom{N\_i}{2}$.

---
Tags: graphs
---


# Question
Title: How to model conditionals with first-class functions?
Since languages with recursible first-class functions are Turing-complete, they should be able to express anything expressible in any other programming language. Therefore, it should be possible to model conditional expressions (i.e. if-statements) with first-class functions. Could someone illustrate how to do this?

# Answer
> 6 votes
The usual encoding of booleans, due to Church, is

$$ {\sf true} = \lambda x. \lambda y. x \qquad {\sf false} = \lambda x. \lambda y. y $$

Roughly, "true" is the function which takes two arguments $x,y$ (first takes $x$, then also takes $y$) and returns the first one. Instead, "false" returns the second one.

If-then-else is then encoded as applying an encoded boolean to the "then" and "else" branches. In this way, the boolean chooses the right value to return.

$$ {\sf if}\ b\ {\sf then}\ t\ {\sf else}\ e = b\\, t\\, e $$

It is then easy to check the so-called "$\beta$" laws:

$$ {\sf if\ true\ then}\ t\ {\sf else}\ e = {\sf true}\\, t\\, e = (\lambda x.\lambda y.x)\\, t\\, e = (\lambda y.t)\\, e = t $$

and

$$ {\sf if\ false\ then}\ t\ {\sf else}\ e = {\sf false}\\, t\\, e = (\lambda x.\lambda y.y)\\, t\\, e = (\lambda y.y)\\, e = e $$

Essentially, these laws state what happens when you "construct" a boolean (using the constants $\sf true, false$), and then "destruct" it later on (using it in an $\sf if\ then\ else$).

Using functions in this way, one can write encodings for all the usual data types, like naturals, pairs, variants, lists, trees, etc.

---
Tags: haskell, lambda-calculus
---


title: What sort of code is this?

text:
# Question
Title: What sort of code is this?
Here is a question I encountered:-

Read this section of program code that inputs 10 positive numbers and then outputs the smallest number input. Identify three changes you would need to make to find the largest number input instead of the smallest number.

```
    Small = 1000
    Counter = 0
    REPEAT
    INPUT Num
    IF Num < Small THEN Small = Num
    Counter = Counter + 1
    UNTIL Counter = 10
    PRINT Small

```

The question refers to a vague 'program code'-which I do not know of. Neither does this seem like pseudocode due to presence of the equals sign as an assigning operator instead of the arrow '←'.Clearly, not a low-level programming language. So what is it?

Note:I am high school student. This code is part of the 0478 Computer Science IGCSE curriculum here:http://www.cambridgeinternational.org/programmes-and-qualifications/cambridge-igcse-computer-science-0478/past-papers/ If anyone of you know about what this code is and why it is used as part of this IGCSE, please include that in your answer.

# Answer
This is still a form of pseudocode, obviously just not of the form you might have seen thus far. It is worth noting that there is not strict standard or rules for writing pseudocode, as long as it describes the solution to a problem in such a way that someone could then implement it in a language of their choice.

The term *pseudocode* simply refers to some notation resembling a programming language, aimed more towards human readability and understanding rather than some language-specific syntax.
> 7 votes

---
Tags: programming-languages, pseudocode
---


# Question
Title: How to implement polymorphism in a turing complete environment?
I'm currently programming in an unnamed turing complete language which has support for pointers, primitive data types, structures, closures, and garbage collection, among other things.

I'm trying to use this language to implement an object oriented design pattern. So far, I have implemented the following algorithm:

```
make object (base class) subroutine:
    create data structure
    associate structure as an 'Object'
    return data structure

make shape (extends from object) subroutine:
    call make object
    associate data structure as a 'Shape'
    add 'getPerimeter' & 'getArea' subroutines to data structure
    return data structure

make circle (extends from shape) subroutine:
    call make shape
    associate data structure as a 'Circle'
    add 'getCircumference' as subroutine to data structure
    re-define 'getPerimeter' & 'getArea' subroutines to data structure
    return data structure

output shape area subroutine
    assert shape is a Shape
    print, call shape.getArea

```

This so far has worked great. Sub-classes correctly inherent the fields of their super-classes.

**However, I am no longer able to take the extended classes and 'treat them as their super-class forms' anymore**. For example, I can no longer treat a `Circle` specifically as a `Shape`, because when it was made into a `Circle` it was augmented with `Circle` member functions like `getCircumference`. I cannot typecast it to be strictly a `Shape` or an `Object`, as its now been defined with sub-class functionality.

In Java terms, I can do this:

```
Fruit a = new Fruit(); // eat()
Apple b = new Apple(); // removeSeeds()
b.removeSeeds();
b.eat();

```

But I cannot do this:

```
Fruit a = new Apple();
a.removeSeeds(); // undefined

```

How can polymorphism be implemented in this sense?

# Answer
> 3 votes
So, first, a question. Are you using dynamic or static dispatch? i.e. if `Circle` and `Shape` provide implementations of the same method, and you cast a `Circle` to a `Shape`, which one gets called?

If you're using static dispatch, one way to do it is, instead of making a Circle by taking a shape and adding fields, you make Circle its own type, with a special `Super` field that is a Circle. Any time Circle methods reference Shape fields/methods, you desugar into `Super.field`. Casting a Circle to a Shape then just involves looking up the shape that's stored.

If you're using Dynamic dispatch, but are using static typing, instead you can use "duck typing" internally, that is, the "type" of something is just which methods/fields are accessible. So in this system, you could construct a Circle as you've described, and when you cast it to a Shape, there's no runtime effect. Your typechecker just ensures that no `Circle` methods are called on a `Shape`, even if its runtime representation is a `Circle`.

Finally, if you're using dynamic dispatch and dynamic typing, then you probably don't need to ever cast a `Circle` to a `Shape` (since there's no typechecker to stop you from calling `Shape` methods on a `Circle`). The trick here is that your `assert shape is a Shape` should return `True` for anything that is a subclass of `Shape`. So as long as that check succeeds for a `Circle`, you're fine. This is why such a check is called `instanceof` in Python: you're not accessing the type of the value, you're checking if it is a subclass of the desired type.

I'm not sure how Turing Completeness factors into anything: Java, Python, and other subclassing languages are all Turing Complete. Java's type system is even Turing Complete!

One final pedantic note: what you call "polymorphism" is better described as "subclass polymorphism". There are, in PL theory, many other kinds of polymorphism, such as parametric (i.e. generics), and ad-hoc (i.e. overloading).

---
Tags: turing-machines, programming-languages, object-oriented, polymorphisms
---


# Question
Title: Number of leaf nodes in n-element red-black trees
Why the number of (NIL) leaf nodes in n-element red-black trees is n+1?

# Answer
> 2 votes
By definition, a red-black tree is a full binary tree in which each node is assigned either red or black and the leaves are labeled as **NIL-node** while internal nodes are labeled as **non-NIL node**. In a full binary tree all of the nodes have either 0 or 2 children. Thus, assuming that a full binary tree has `n` internal nodes, the number of leaf nodes will be `n + 1`. So what you are asking is: if red-black tree has `n` **non-NIL nodes** why does it have `n+1` **NIL-nodes** ?

---
Tags: balanced-search-trees
---


# Question
Title: Explaination for Variation of Boyer-Moore Majority voting algorithm
Boyer-Moore's majority vote algorithms can be used to determine the majority element in a linear time and constant space.

The intuition behind finding the majority element is understandable as it has to be greater than the count of other elements in the input sequence if a majority element exists.

However, there is a variation of this algorithm to find the elements occurring more than `[n / 3]` where `n` is the length of the sequence.

The algorithm goes like this.

> * Start with two empty candidate slots and two counters set to 0.
> * for each item:
>     + if it is equal to either candidate, increment the corresponding count
>     + else if there is an empty slot (i.e. a slot with count 0), put it in that slot and set the count to 1
>     + else reduce both counters by 1

I can understand there will be at most `(n /3) - 1` entries so we keep two containers and their counts.

But I'm not sure why the last reduce both by 1 is pivotal to this algorithm. I would be very helpful if you explain the intuition behind this.

Code of the above algorithm

> ```
> vector<int> majorityElement(vector<int>& nums) {
>     int cnt1=0, cnt2=0;
>     int a,b;
>     for(int n: nums){
>         if (cnt1 == 0 || n == a){
>             cnt1++;
>             a = n;
>         }
>         else if (cnt2 == 0 || n==b){
>             cnt2++;
>             b = n;
>         }
>         else{ // This part
>             cnt1--;
>             cnt2--;
>         }
>     }
>     cnt1=cnt2=0;
>     for(int n: nums){
>         if (n==a) cnt1++;
>         else if (n==b) cnt2++;
>     }
>     vector<int> result;
>     if (cnt1 > nums.size()/3) result.push_back(a);
>     if (cnt2 > nums.size()/3) result.push_back(b);
>     return result;
> }
>
> ```

Algorithm and code source

# Answer
Here is a different way to consider the same algorithm, or rather its general form with $k$ counters (in your case, $k=2$). There are $k$ "containers" and a trash bag. Each container will contain one type of element at a time. Initially everything is empty. When we read a new element $x$, we consider the following cases:

* If there is a container containing $x$'s, add $x$ to that container.
* If there is no container containing $x$ and there is an empty container, put $x$ in the empty container.
* If there is no container containing $x$ and there are no empty containers, remove one element from each container, and put $x$ in the trash.

When the algorithm terminates, each of the $n$ elements is either found in one of the $k$ containers, or in the trash bag.

Suppose that element $x$, not found in any of the containers, is found $m$ times in the input. Thus all $m$ copies of $x$ are in the trash bag. Each time an element is put in the trash bag, $k$ other elements are also put in the trash bag together with it. This means that the trash bag contains at least $(k+1)m$ elements, and so $(k+1)m \leq n$ or $m \leq n/(k+1)$.

Consequently, if an element appears more than $n/(k+1)$ times in the input then it will necessarily be found in one the $k$ containers. In other words, the algorithm correctly identifies all elements appearing more than $n/(k+1)$ times.

Note how this analysis crucially depends on the fact that when trashing $x$ in the third case above, we also trash $k$ additional elements together with it.
> 20 votes

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


# Question
Title: Turing machine deciding $\{1^{2^n} : n \geq 0 \}$
How can I design a Turing machine that accepts the language $\\{1^{2^n} : n \geq 0\\}$?

Here is my attempt:

\[!\[enter image description here\]\[1\]\]\[1\]

# Answer
Here is the idea:

> 1. Go over the entire input, crossing out every other 1 encountered.
> 2. Reject if the number of 1s encountered was odd but more than 1.
> 3. Accept if the number of 1s encountered was exactly 1.
> 4. Otherwise, go back to step 1.
> 4 votes

---
Tags: turing-machines
---


# Question
Title: Can any memory-less computer operation be represented in propositional logic?
Take any operation that is done by any type of computer (e.g. a cpu on a modern laptop), which doesn't use any type of temporary memory storage.

I.e. this computer operation computes a function $f(x)=y$, without using any form of memory storage.

> **Q1**: Is it possible for any arbitrary such $f$ to be represented by a formula $\phi(x,y)$ in propositional logic, such that $\phi(x,y) =True$ iff $f(x)=y$?

What if we relax the requirement that no temporary memory can be used?

---

**EDIT**: after reading the responses so far, perhaps it makes sense to phrase the question in the opposite way:

> **Q1b:** What restrictions on $f(x)$ are necessary and sufficient for it to be representable in propositional logic?

# Answer
Well you can just make a giant truth table for $f$ and then convert that to a Boolean formula. Boolean formulas are propositional formulas, are they not?
> 1 votes

# Answer
You asked about "computer operation".

One of the three RSAs (Rivest, Shamir, Adleman, can't remember which one) proposed a chip that would be able to find prime factors of 1024 bit integers in quite a reasonable time (feed in the number at one end of the chip, wait a few minutes, and a factor comes out at the other hand), at a proposed cost of about $50 million, a few years ago. Can't remember the exact time, but it was so enormous that there must be some kinds of loops involved. "Proposed" means that he actually figured out in detail how it would work.

(Memory coming back: Not one chip. Not one wafer worth of chips. Many, many wafers).

Whether you say there is "memory" or not is up for debate, but I'm quite sure that you can't replicate the operation of this chip with propositonal logic. Of course the whole problem, being fixed size, can be solved with propositional logic, but most likely of a size that any attempt to write it down would exceed the size of the universe.
> 0 votes

---
Tags: computability, propositional-logic
---


# Question
Title: Is it NP complete to decide whether a graph has $k$ disjoint triangles?
I'm trying to prove that $$k\text{-Matching}\le\_p k\text{-Disjoint-Triangles}$$ but I was told that the $k\text{-Matching}$ (decide whether a graph has a matching of size $k$ ) can be solve in polynomial time. Then I'm stuck here.

Could anyone help me out here?

# Answer
For the special case where $n$ is a multiple of 3 and $k=n/3$, this is the PARTITION-INTO-TRIANGLES problem, which is proved to be NP-complete here.

The idea is to reduce 3-DIMENSIONAL-MATCHING (3DM) to PARTITION-INTO-TRIANGLES. I quote the construction here.

> Let $X = \\{x\_1, x\_2, \ldots, x\_q\\}$, $Y = \\{y\_1, y\_2, \ldots, y\_q\\}$, $W = \\{w\_1, w\_2, \ldots, w\_q\\}$ and $M \subseteq X\times Y\times Z$ be the generic input instance of 3DM. Construct an initial set of vertices $V$, called the "public vertices", as the union of $X$, $Y$ and $W$. For every triple $m = (x\_a, y\_b, w\_c)$ in $M$, construct the graph $G\_m = (V\_m, E\_m)$, depicted in Figure 1. Here $V\_m$ contains the three public vertices $x\_a$, $y\_b$ and $w\_c$ plus three "private vertices" $v\_m^1$, $v\_m^2$ and $v\_m^3$. The ten edges in $E\_m$ are $v\_m^1v\_m^2$, $v\_m^1v\_m^3$, $v\_m^2v\_m^3$, $x\_av\_m^3$, $x\_av\_m^2$, $y\_bv\_m^3$, $y\_bv\_m^1$, $w\_cv\_m^1$, $w\_cv\_m^2$ and $x\_1y\_b$. The whole graph $G\_M$ is obtained from the union of all the gadgets $G\_m$ as follows: $G\_M = (V\_M, E\_M) = (\cup\_m V\_m,\cup\_m E\_m)$.
> 5 votes

# Answer
Isn't it 3 dimensional matching?

https://en.wikipedia.org/wiki/3-dimensional\_matching

Let us reduce 3-dimensional matching to deciding whether a graph has k disjoint triangles.

Let I be an instance o 3DM. Construct a graph G with X x Y x Z vertices and there is the edges of a triangle between vertices in x1 y1 z1 in G if there is the triple (x1 y1 z1) in the instance I. G has k disjoint triangles iff I has a 3DM M of size k. So, solve k-disjoint triangle in this class of graphs obtained from instances of 3DM solves 3DM for all its instances. As 3DM is NP-complete, k-disjoint triangles is NP-hard, and as it is clearly NP, it is also NP-complete.
> 2 votes

---
Tags: complexity-theory, np-complete, reductions, np-hard, decision-problem
---


# Question
Title: Find the sum of the first K subsets of integer array
We have given a multiset of $N$ integer, both positive or negative. Consider all $2^N$ subsets, sorted by their sum (the empty subset has sum 0). We want an algorithm that outputs only the first $K$ sums.

The problem is that $N$ can be very big number (up to 100000), so we cannot generate all subsets. How to optimize the search so we wont generate more than $K$ subsets.

$K$ in the problem will also be up to 100000.

I was thinking to get the smallest possible subset and then try to make it bigger and bigger, but I couldn't come to something that will work in all cases.

The problem is from past csacademy contest: https://csacademy.com/contest/round-79/task/smallest-subsets/

# Answer
Say the multiset is $S=M\cup P$ where $M$ is the set of negative numbers and $P$ is the set of non-negative numbers. Define $S^+=(-M)\cup P$ where $-M$ means the set of opposite numbers of elements of $M$. For a subset $T=(-M\_T)\cup P\_T$ of $S^+$ where $M\_T\subseteq M$ and $P\_T\subseteq P$, define $f(T)=(M\backslash M\_T)\cup P\_T$, which is a subset of $S$. Now easy to see $f$ is a bijection, and the sum of $f(T)$ is the sum of $T$ plus a constant (the sum of $M$). So we only need solve the problem on $S^+$, and transform the result, say $T\_1,T\_2,\ldots, T\_K$ to $f(T\_1),f(T\_2),\ldots, f(T\_K)$. That is to say, **we only need to solve the problem where all elements are non-negative**.

This is solved in this post. For completeness of this answer, I quote it here.

> (Going to assume nonempty subsets for simplicity. Handling the empty subset is a line or two.)
>
> Given a nonempty subset of indices S, define the children of `S` to be `S \ {max(S)} U {max(S) + 1}` and `S U {max(S) + 1}`. Starting with `{1}`, the child relation forms a tree that includes every nonempty subset of positive integers.
>
> ```
> {1}
> |  \
> {2} {1,2}______
> |  \     \     \
> {3} {2,3} {1,3} {1,2,3}
>
> ```
>
> Keyed by the sum of corresponding array elements, this tree is a min-heap. If you compute the keys carefully (by adding and subtracting rather than summing from scratch) and implement the min-heap deletion lazily, then you get an O(k log k)-time algorithm.
> 2 votes

---
Tags: algorithms, optimization, sets
---


# Question
Title: Understanding truncation and rounding error in IEEE floating point system?
I'm trying to understand the theory behind finding the optimal $h$ value for differentiation in this definition:

$$ \frac{f(x+h) - f(x)}{h}$$

as $h$ tends to 0.

Here is my understanding:

1. Truncation error comes from say approximating the value of $f(x+h)$ using the taylor series. In this case, it could be that:

$$ f(x+h) \approx f(x) + hf'(x) + \frac{h^2}{2!}f''(x) + O(h^3)$$

2. Letting $f'(x)$ to be the subject since we want to find gradient $f'(x)$, we have

$$f'(x) = \frac{f(x) - (hf'(x) + \frac{h^2}{2!}f''(x) + O(h^3))}{h}$$ $$\implies f'(x) = \frac{f(x+h)-f(x)}{h} - \frac{h}{2}f''(x) + O(h^2)$$

Intuitively, we can stop at here by letting $h \approx \sqrt\epsilon$ where $\epsilon$ is the machine epsilon, we can thus limit our truncation error. But suppose we continue, then our truncation error is $\frac{h}{2}f''(x)$.

3. Then rounding error comes from the interaction of the sums in the differentiation equation:

$$ \frac{f(x+h) - f(x)}{h} = \frac{\[f(x) + hf'(x) + O(h^2)\] - f(x)}{h}$$

But for $f'(x) \approx 1$ and since we have $h \approx \sqrt \epsilon$, we have

$$ \frac{f(x+h) - f(x)}{h} \approx 1 \pm \frac{\epsilon}{h}$$

Which means the rounding error is approximately $\frac{\epsilon}{h}$, which concurs with the fact that the left hand side of the equation is actually $f'(x)$ as well, just that we have managed to reduce the rounding error to what is seen on the right hand side.

4. Now, we see that our truncation error varies linearly with $h$ while our rounding error varies inversely with $h$. To find the optimal $h$ value, we equate both errors:

$$\frac{\epsilon}{h} = \frac{h}{2}f''(x) \approx \frac{h}{2}$$ since we have $f''(x) \approx 1$.

Letting $h$ be the subject, we have $$h = \sqrt{2\epsilon}$$ which means the optimal $h$ is around $h = \sqrt{\epsilon}$ as expected.

Is my understanding correct? Does the final factor of 2 in the end matter?

Big problem in the above argument: in point 3, one already use the fact that $h = \sqrt \epsilon$. Wouldn't that already defeat the purpose of finding the optimal $h$?

# Answer
As listed your reasoning is indeed circular: you start by assuming $h \approx \sqrt{\epsilon}$, then use the results in point 3 to infer that we should take $h \approx \sqrt{\epsilon}$. So that's not convincing. So let's redo the analysis more carefully, then we'll look at the meaning of the constant.

# A more careful analysis

As in your analysis, we'll assume $f'(x) \approx 1$ and $f''(x) \approx 1$.

Your analysis of truncation error is fine; the truncation error is indeed $\frac{h}{2} f''(x) + O(h^2)$, which given your assumptions is $\frac{h}{2} + O(h^2)$. In our analysis $h$ will be small enough that $O(h^2)$is negligible, so we'll call the truncation error $\frac{h}{2}$ for simplicity.

What about rounding error? The rounding error of representing $f(h)$ in floating point is $\epsilon$ in relative error, where $\epsilon$ is the machine epsilon; in absolute error, that is $\epsilon f(h)$. Since you assumed $f(h) \approx 1$, that is $\approx \epsilon$. Similarly, the rounding error of representing $f(x+h)$ is $\epsilon f(x+h)$ in absolute error; since $f(x+h) \approx f(x) \approx 1$, that is $\approx \epsilon$ as well. Now the absolute error of $f(x+h)-f(x)$ is at most about $2\epsilon + \epsilon (f(x+h)-f(x))$; the $2\epsilon$ comes from the error in each of the two subterms (and the triangle inequality), and the $\epsilon (f(x+h)-f(x))$ comes from roundoff error in representing the result. Since $f(x+h)-f(x) \approx h f'(x) \approx h$, that means the absolute error of $f(x+h)-f(x)$ is at most about $2\epsilon + \epsilon h$.

Then we divide by $h$. The absolute error becomes $2\epsilon/h + \epsilon$, plus a term due to representing the result in floating point; that extra term is $\epsilon ((f(x+h)-f(x)/h)$, and since $(f(x+h)-f(x)/h \approx f'(x) \approx 1$, we see that the extra term is $\approx \epsilon$. Therefore the absolute error in computing $(f(x+h)-f(x)/h$ is about $2\epsilon/h + \epsilon + \epsilon$. So, the total roundoff error is about $2\epsilon/h + 2\epsilon$, in absolute error.

The total error is at most the sum of the truncation error and the roundoff error, or about $$\frac{h}{2} + {2\epsilon \over h} + 2\epsilon.$$ We want to know what value of $h$ minimizes this expression. We can figure that out by letting $g(h) = \frac{h}{2} + 2\epsilon/h + 2\epsilon$ and minimizing $g(h)$; the minima must be at a point where the derivative is zero. So, differentiate: $$g'(h) = \frac{1}{2} - {2\epsilon \over h^2}.$$ Setting $g'(h)=0$ and solving for $h$ yields $h^2 =4 \epsilon$, i.e., the function $g(h)$ is minimized at $h=2\sqrt{\epsilon}$; at that point, we have a total (absolute) error of at most $g(2\sqrt{\epsilon}) \approx 2 \sqrt{\epsilon} + 2 \epsilon \approx 2\sqrt{\epsilon}$.

The summary: assuming $f(x)\approx 1$ and $f'(x) \approx 1$, the total error is minimized when you choose $h$ to be about $h\approx 2\sqrt{\epsilon}$. If you choose $h$ too much larger than that, the truncation error increases and starts dominating. If you choose $h$ too much smaller than that, the roundoff error increases and starts dominating.

So, if you know $f(x)\approx 1$ and $f'(x) \approx 1$, then it's reasonable to choose $h\approx 2\sqrt{\epsilon}$.

# The constant

Now, you might be wondering a bunch of things. Why the constant 2? Where did that come from? How critical is it for the constant to be 2? What if I use $h \approx \sqrt{\epsilon}$ instead of $h \approx \sqrt{2\epsilon}$?

Well, if you redo the calculation with a different value of $h$, you'll see that the total error is not too sensitive to the constant 2. For instance, if you choose $h=\epsilon$, then the total error will be at most about $g(\epsilon) \approx 2.5 \sqrt{\epsilon} + 2 \epsilon \approx 2.5 \sqrt{\epsilon}$, which is not that different. So don't worry too much about the exact value of the constant.

Where did the constant 2 came from? Well, partly it is coming from the fact that we are doing multiple operations, and you can get a little bit of roundoff error from each operation, so the error can accumulate. And, partly it is coming from the assumptions that $f'(x) \approx 1$ and $f''(x) \approx 1$. Of course, those assumptions are pretty sketchy. In practice, we don't know what $f'(x)$ is before doing the computation (that's the whole point of this computation; we are trying to estimate/compute $f'(x)$), and we don't know what $f''(x)$ is. So, that assumption also looks circular.

But here's why in this case it might be OK. You could redo the calculation with different assumptions, e.g., $f'(x) \approx 2$ and $f''(x) \approx 3$. If you do that, you'll find a slightly different optimal value of $h$; instead of $2 \sqrt{\epsilon}$, you'll have a slightly different constant replacing the 2. So we can see that the 2 comes from the assumptions about the magnitude of $f'(x)$ and $f''(x)$. But, crucially, if $f'(x)$ and $f''(x)$ aren't too large or too small, then the resulting constant in the optimal choice of $h$ won't be too different. It might be $5 \sqrt{\epsilon}$ or $0.5 \sqrt{\epsilon}$, but that's not so bad.

And, in practice, we're often dealing with smooth functions where the derivatives don't get too large, so while we don't know exactly what $f'(x)$ or $f''(x)$ are, we might be able to assume they won't be too large. As a result, taking $h \approx c \sqrt{\epsilon}$ for some small value of $c$ will be optimal. We don't know what the optimal value of $c$ is exactly, but we can just heuristically pick a small value for $c$, like $c=1$ or $c=2$, and even if that's not exactly optimal, we'll probably do reasonably well -- it won't be too much worse.

So, the final answer is: no, the 2 is not essential. It's perfectly reasonable to use $h = \sqrt{\epsilon}$ instead of $h = 2 \sqrt{\epsilon}$ -- but you probably want to choose $h$ somewhere in that neighborhood.
> 1 votes

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


# Question
Title: What is the difference between Coding and Programming?
In our daily life we use both coding and programming for the same meaning. I want to know the difference between these terms (If any).

If they are used for different meanings than please anyone can aware us about it, So we can correct ourselves.

# Answer
They are mostly synonymous. In that profession you can be called, or call yourself, a coder, a programmer, a software developer, or a software engineer. They all do the same job. If you call yourself an "engineer", then in many jurisdictions you would have to have training, pass some stringent exams, and may have legal responsibilities for the results - people calling themselves "software engineers" usually ignore that.

The name used usually goes with some expectations. Someone called a "coder" or "programmer" is usually expected to write code (also called programming), with no expectations of the actual outcome. A "software developer" is someone who is expected to produce complete, working, usable software as the result of his work. A "software engineer" is usually someone who fancies a nice title.

"Coder" is often used as a pejorative. Usually by people who couldn't do it themselves if their life depended on it.
> 2 votes

# Answer
They are synonymous. Programming is the act of writing "source code". Coding is just short for "source code" writing. As someone else stated, nobody has ownership of official definitions of these slang terms, so take any answer with a grain of salt.

If you had, however, asked me the difference between "programming" and "software engineering", then I'd say there is a big difference. Programming is something any hack can do to create a website or small software. Software engineering is a much deeper process which involves designing your software, developing an architecture, then coding it, and testing it afterward. It's like comparing an automotive engineer to a mechanic.
> 1 votes

# Answer
I agree that they are mostly synonymous; but in my experience:

**Coding** is used in less formal contexts (e.g. *coding competitions*, *coding challenge*, *coding snippets*, ...) and it usually refers to building small specific functions/procedures in a specific language or to implementation details.

**Programming** is used in broader and more formal contexts and it often implies more "high levels" concepts/activities (e.g. *programming paradigms*, *programming methodologies*, ...)
> 0 votes

---
Tags: knowledge-representation
---


# Question
Title: Use of existential quantifier in tuple relational calculus
It is somewhat confusing to me when to use quantifiers in tuple relational calculus (TRC). I stumbled upon following problem and I am still scratching my head thinking why not TRC query can be constructed without using existential quantifier.

The given problem reads like this:

> Relations:
> student (rollNo, name, degree, year, sex, deptNo, advisor)
> department (deptId, name, hod, phone)
> professor (empId, name, sex, startYear, deptNo, phone)
> course (courseId, cname, credits, deptNo)
> enrollment (rollNo, courseId, sem, year, grade)
> teaching (empId, courseId, sem, year, classRoom)
> preRequisite(preReqCourse, courseID)
>
> Question: Obtain the names of courses enrolled by student named "Roger".
>
> Given solution:

```
{ c.name | course(c) ^
                   (∃s) (∃e) ( student(s) ^
                                     enrollment(e) ^
                                     s.name = “Roger” ^
                                     s.rollNo= e.rollNo ^
                                     c.courseId = e.courseId}

```

Why I cant just have following? :

```
{c.name | course(c) ^
                 enrollment(e) ^
                 student(s) ^
                 c.courseId = e.courseId ^
                 e.rollNo = s.rollNo ^
                 s.name = "Roger" }

```

# Answer
> 1 votes
Something like `{ c.name | ... }` is shorthand for something like

```
{z : (name) | (∃c) (z.name = c.name ^ ...) }.

```

As described on, e.g., the Wikipedia page, the fundamental form of the set comprehension (i.e. query) notation expects a variable to the left of the `|`. If you are familiar with anonymous functions/lambda notation, it is very similar to $\lambda z.(\dots)$. If we named it, it's like we're defining a predicate $P(z)\equiv(\dots)$. The upshot is that the notation effectively binds `z` (or `c` in the original form). But in your version without existential quantifiers, nothing is binding `e` or `s`. It's like you're referring to undeclared variables in a programming language.

Since whether the variables are bound with a universal or existential quantifier and where exactly that quantifier appears in the formula are all relevant, it would be difficult to infer which quantifiers should be added and where. (And as an additional possibility, we could just imagine that the variables are completely free and essentially become additional parameters to the anonymous predicate we're defining, but that doesn't fit in well with the Tuple Relational Calculus.) Prolog and Datalog do use a syntax that makes existential quantifiers implicit, but they are (in their basic forms) also limited to a language that 1) omits universal quantifiers, and 2) only allows formulas where existential quantifiers can always be pulled to being the outermost connective. Actually, when negation is added to Datalog, this stops being true and this implicit syntax starts to become ambiguous and confusing. Some implementations add an explicit existential and/or universal quantifier in such cases.

The upshot is, at the most fundamental level, all variables need to be bound, either by a quantifier or by the set comprehension syntax. There do exist various shorthands and conventions that are often used that can cloud this picture up, but ultimately every variable is introduced by some binding form.

---
Tags: database-theory, databases, relational-algebra, relational-calculus, tuple-relational-calculus
---


# Question
Title: How do I build a left derivation tree from an expression including right-to-left associativity?
Suppose I want to make a left derivation tree of an expression, but the expression includes operators that are right-to-left associative. Would I still expand the left-most variable first in my tree? For example, the expression `a + b ** c ** d` where `**` is right-to-left associative, and `+` is left-to-right associative.

# Answer
In a leftmost derivation, you always expand the leftmost non-terminal, by definition. The question is, what do you expand it to, since you usually have more than one choice.
> 1 votes

---
Tags: formal-grammars, parsers
---


# Question
Title: What do two non-terminal symbols on the left hand side of a BNF grammar mean?
I'm learning BNF, and the text I'm using gives a simple grammar for integer expressions like this:

```
<expression> ::= <number> | <expression> <operation> <expression>
<operation> ::= + | - | x
<number> ::= <digit> | <digit> <number>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

```

This makes sense to me, but then it goes on to show that you can have two non-terminal symbols on the left hand side of expression like this:

```
e,f ::= n | (e o f)
o ::= + | - | x
n ::= d | d n
d ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

```

I don't understand what it means to have both `e` and `f` on the left hand side: what does it mean and what is the point of it?

# Answer
That seems unorthodox to me, but I'm certainly not current with all the formal language theory textbooks being used these days.

The point is that in

$$\langle expression\rangle :=\langle number\rangle \\;| \\;\langle expression\rangle\langle operation\rangle\langle expression \rangle$$

the two instances of $\langle expression\rangle$ on the right-hand side are unrelated to each other. In a derivation, they are derived independently and nothing constrains their derivations. Sometimes we need to refer to them (for example, when we get to semantic analysis) and then it might be convenient to give them different spellings.

I would normally use subscripts:

$$\langle expression\rangle :=\langle number\rangle \\;| \\;\langle expression\_1\rangle\langle operation\rangle\langle expression\_2 \rangle$$

but your professor seems to want to be able to say that $e$ and $f$ are aliases for the same non-terminal (but not the same derivation). This seems confusing to me. Is it really so hard to write:

$$e \Rightarrow n \\; | \\; e\_1\\; o \\; e\_2$$
> 1 votes

---
Tags: formal-grammars
---


# Question
Title: Equivalence rules for LTL - Getting stuck working with $ \square \lozenge $ & Until ($\textsf{ U}$ ) operators
## Need to prove equivalence for (or disprove equivalence for):

$ \hspace{1cm}\square ϕ → \lozenge ψ ≡ ϕ\textsf{ U }(ψ ∨ ¬ϕ) \\ $

My current attempt using the LTL equivalnce rules to determine equivalence:

$ \square ϕ → \lozenge ψ \\ ≡\ ¬\square ϕ \lor \lozenge ψ \hspace{1cm}(\textsf{"Mutual implication"} ϕ →ψ≡¬ϕ\lor ψ )\\ ≡ \lozenge ¬ϕ \lor \lozenge ψ \hspace{1cm}(\textsf{"Duality"} ¬\square≡\lozenge ¬ )\\ ≡ \lozenge (¬ϕ \lor ψ) \hspace{1cm}(\textsf{"Distributive law on"}\lozenge )\\ ≡true \textsf{ U} (¬ϕ \lor ψ) \hspace{1cm}(\textsf{"Def of"}\lozenge )\\ ≡true \textsf{ U} (ψ \lor ¬ϕ) \hspace{1cm}(\textsf{"Symmetry"}\lor)\\ $

After this I got stuck. I am not sure how to proceed from here to get the right side. Are other propositional logic rules allowed to be used in LTL, like for example identity disjunction?

# Answer
In order to prove the equivalence of two formulas $\phi,\psi$, it is enough to show that for every computation $\pi$, it holds that $\pi\models \phi$ iff $\pi\models \psi$. This is *semantic equivalence*.

Let's look at (1). You got to the formula $true{\bf U} (\psi\vee \neg \phi)$. Now, this holds in a computation $\pi$ iff there exists $i\ge 0$ such that $\pi^i\models \psi\vee \neg \phi$. Assume now that $i$ is *minimal* with respect to this property, and consider the computations $\pi^j$ for $j\<i$. If $\pi^j\models \neg \phi$, then $i$ is not minimal, so $\pi^j\models \phi$, which means that $\pi\models \phi {\bf U} (\psi\vee \neg \phi)$. Since the converse implication is trivial, we get that the two formulas are equivalent.

For (2) you should indeed show that the formulas are not equivalent. To do so, you need to show that *there exists* a computation $\pi$ that satisfies one but not the other.

Hint: It could be the case that $\phi$ holds only finitely many times, but $\psi$ does not hold after $\phi$.
> 5 votes

# Answer
\begin{alignat\*}{2} \Box \varphi \to \Diamond q &\equiv \neg \Box \varphi \lor \Diamond \psi &&\text{($\to$ elim)}\\ &\equiv \Diamond \neg \varphi \lor \Diamond \psi &&\text{(neg near var)}\\ &\equiv \Diamond (\neg \varphi \lor \psi) &&\text{(grouping $\Diamond$)}\\ &\equiv \neg (\neg \varphi \lor \psi) U (\neg \varphi \lor \psi) &&\text{(def of $\Diamond$ using Until)}\\ &\equiv (\varphi \land \neg \psi) U (\neg \varphi \lor \psi) &\quad&\text{(neg inside)}\\ &\equiv \varphi U (\neg \varphi \lor \psi) &&\text{($\land$ elim)}\\ &\equiv \varphi U (\psi \lor\neg \varphi) &&\text{(just arrange) QED} \end{alignat\*}
> 4 votes

---
Tags: logic, linear-temporal-logic, temporal-logic
---


# Question
Title: What are applications of alphabetic trees?
Earlier this week a paper was released describing an algorithm for building optimal alphabetic ternary trees. The alphabetic property as described on Wikipedia as

> Alphabetic trees are Huffman trees with the additional constraint on order, or, equivalently, search trees with the modification that all elements are stored in the leaves. Faster algorithms exist for optimal alphabetic binary trees (OABTs).

From this, I understand that an alphabetic binary tree will produce shorter paths from root to element for elements that have been inserted into the tree more times than elements that haven't, and the alphabetic property would be described the same way for a ternary tree.

I haven't been able to find a lot of discussion about applications for the alphabetic property outside of Huffman coding but it is not a requirement to implement the algorithm. Are there any applications where the alphabetic property would be a requirement, and if not, are there any benefits to guaranteeing the alphabetic property that justifies increased implementation complexity?

# Answer
> 3 votes
You use alphabetic trees when you need nodes to keep their input order in the resulting code. Huffman trees are used for coding purposes, and alphabetic trees for storing data and for allowing quick search and edit.

One example application is storing textual data in alphabetic order. The complete works of Shakespeare were stored in an OAT (optimal alphabetic tree), which was constructed using the Hu-Tucker algorithm. See here for another $O(n \log n)$ algorithm for constructing OATs.

# Answer
> 0 votes
Huffman codes are often used to efficiently encode a small alphabet, such as all bytes. In this case, the codewords can be stored in a lookup table. What happens if the source data consists of *strings* rather than *indices*? For example, suppose that we are interested in constructing a prefix code for all words in the English language. Given a word, how do we convert it to an index that can be looked up in a table?

Prefix codes can be alternatively thought of as *decision trees*. Every internal node has two children, and the corresponding pair of edges are labeled "0" and "1". The codeword corresponding to a leaf is the concatenation of labels on the path from the root to the leaf. We can think of each internal node as a *query*, the answer to which determines whether we take the edge labeled "0" or the one labeled "1".

The queries constructed by Huffman's algorithm can be completely arbitrary, which makes it hard to implement them. In contrast, the queries in an alphabetic tree correspond to simple comparisons: we can identify each internal node with an object $x\_i$ in the domain, and given an input $x$ to be encoded, we take the edge labeled "0" if $x \leq x\_i$, and the edge labeled "1" if $x \> x\_i$. By storing the $x\_i$ in the node, we facilitate efficient encoding.

For more on this perspective, see the paper Twenty (simple) questions.

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


# Question
Title: Given list of numbers find for each number in the list the next distinct number
Given a sequence of numbers $l\_1, \ldots, l\_n$, I want to find for each index $i$ the next possible number to the right of $l\_i$ (if any) that is different from $l\_i$. What is the best time and space optimal solution to do this?

The numbers may be repeating and are in no particular order.

# Answer
> 1 votes
Here is pseudocode for an algorithm which outputs the entire answer array $a\_1,\ldots,a\_n$:

> Set $\mathit{first} \gets 1$ (first index in the current run)
>
> Set $\mathit{curr} \gets 1$ (index of the current element being scanned)
>
> While $\mathit{curr} \< n$:
>
> Set $\mathit{curr} \gets \mathit{curr} + 1$
>
> If $l\_{\mathit{curr}} \neq l\_{\mathit{first}}$:
>
> Set $a\_{\mathit{first}},\ldots,a\_{\mathit{curr}-1} \gets l\_{\mathit{curr}}$
>
> Set $\mathit{first} \gets \mathit{curr}$
>
> End If
>
> End While
>
> Set $a\_{first},\ldots,a\_n \gets \bot$ (no different element to the right)

This algorithm uses linear time and $O(1)$ auxiliary space.

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