What is the significance of ⟨B, s⟩ -> ⟨B', s'⟩ as the initial rule in this question about small-step semantics? Revising for an exam and I'm trying to get to grips with operational semantics. Here's the exam question that prompted me posting this:

Exam Question:

We add to the language $\mathsf{SIMP}$ two new commands, with abstract syntax defined by the grammar rule:

$$C ::= \mathsf{assert}\ B\ \mathsf{before}\ C \mid \mathsf{abort}$$

The small step semantics of $\mathsf{SIMP}$ is extended with the following rules:

$$\frac{\langle B, s \rangle \to \!\, \langle B', s' \rangle}{\langle \mathsf{assert}\ B\ \mathsf{before}\ C, s \rangle \to \!\, \langle \mathsf{assert}\ B'\ \mathsf{before}\ C, s' \rangle}$$

$$\frac{}{\langle \mathsf{assert}\ \mathsf{True}\ \mathsf{before}\ C, s\rangle \to \!\, \langle C, s \rangle}$$

$$\frac{}{\langle \mathsf{assert}\ \mathsf{False}\ \mathsf{before}\ C, s\rangle \to \!\, \langle \mathsf{abort}, s \rangle}$$

The configuration $\langle \mathsf{abort}, s \rangle$ is stuck (no transitions are available from this configuration). Explain with your own words the behaviour of the new commands.

Given $\mathsf{SIMP}$ Language:

$$
\begin{align*}
C &::= \mathsf{skip} \mid l\ \mathsf{:=}\ E \mid C;\, C \mid \mathsf{if}\ B\ \mathsf{then}\ C\ \mathsf{else}\ C \mid \mathsf{while}\ B\ \mathsf{do}\ C \\
E &::= \mathsf{!}l \mid n \mid E\ op\ E \\
op &::= \mathsf{+} \mid \mathsf{-} \mid \mathsf{*} \mid \mathsf{/} \\
B &::= \mathsf{True} \mid \mathsf{False} \mid E\ bop\ E \mid \neg B \mid B \wedge B \\
bop &::= \mathsf{>} \mid \mathsf{<} \mid \mathsf{=} \\
\end{align*}
$$

My Question:

Firstly let me get my understanding of the question out of the way: We're adding a new command $(C)$ to the list of commands we have defined in our $\mathsf{SIMP}$ language. $C$ asserts $B$ before $C$ or aborts the program/process running. Using small step semantics the question has shown us each step of the process as it runs. Here's my issue:

Assuming my knowledge is correct, every rule written below the line holds if what is written above it holds. If this is the case, what is the importance of the first line

$$\langle B,\ s \rangle \ \to \!\ \ \langle B',\ s' \rangle$$

The rule we have implemented makes no reference of a $B$ in some state $s$ becoming/transitioning into $B'$ in some state $s'$. How can that suddenly be what decides the rule

$$\langle \mathsf{assert}\ B\ \mathsf{before}\ C,\ s \rangle\ \to \!\ \ \langle \mathsf{assert}\ B'\ \mathsf{before}\ C,\ s' \rangle$$

I feel like that rule should be what we start with, not what comes in second. The rule we decided to add to $\mathsf{SIMP}$'s grammar seemed to be more about checking with $B$ before we continue on to $C$, not checking with $B$ so we can go to $B$ (or something to that effect?).

I know that it's not directly related to the exam question at hand but I feel like understanding why might clear up some gaps in my knowledge regarding operational semantics on the whole. That said, here is my answer to the exam question itself:

'The behaviour of the command $C$ ($C ::= \mathsf{assert}\ B\ \mathsf{before}\ C \mid \mathsf{abort}$) is such that when $B$ is asserted it must return either $\mathsf{True}$ or $\mathsf{False}$, as it is a Boolean command. When it returns $\mathsf{False}$ the program/process is aborted, meaning to transitions from this state cannot be made. If it returns $\mathsf{True}$ then you are able to continue on to $C$ in some state $s$.'

Is this correct? If not, where did I go wrong? Like I said, I don't understand the top two rules and as such I feel it hurts my answer not being able to include them in my reasoning.

It seems you have some doubts about the first added evaluation rule
$$
\frac
{\langle B, s \rangle \to \!\, \langle B', s' \rangle}
{\langle \mathsf{assert}\ B\ \mathsf{before}\ C, s \rangle \to \!\, \langle \mathsf{assert}\ B'\ \mathsf{before}\ C, s' \rangle}
$$

It might be redundant, but I ought to point out it's one rule: the top part is called a premise of the rule, the bottom part is called a conclusion.

We call rules of this type rules of congruence (and the next two are computation rules). One needs rules of congruence to reduce subparts of a bigger expression or command, i.e. reduce something in its context. Usually, one applies rules of congruence until one can use a computation rule to dispose of some parts of the context. Here, the premise serves you as a means of reducing a Boolean expression $B$ to its value $(\mathsf{True}$ or $\mathsf{False})$.

Let me illustrate this by example: if you have a command $\mathsf{assert}\ \mathsf{True}\ \mathsf{before}\ \mathsf{skip}$, and an initial state $s$, then you reduce it to $\mathsf{skip}$ (without changing $s$) using the second added rule:
$$
\langle \mathsf{assert}\ \mathsf{True}\ \mathsf{before}\ \mathsf{skip}, s\rangle \to \!\, \langle \mathsf{skip}, s \rangle
$$

But what should we do if the command we've got is $\mathsf{assert}\ \mathsf{True \wedge \mathsf{True}}\ \mathsf{before}\ \mathsf{skip}$? There is no computation rules for this, i.e. rules that are able to get rid of the $\mathsf{assert}$... part. Here comes the congruence rule: first you reduce $\mathsf{True \wedge \mathsf{True}}$ to $\mathsf{True}$, using some evaluation rule defined for Booleans (not shown here) -- that's why you need the premise ${\langle B, s \rangle \to \!\, \langle B', s' \rangle}$ -- then you use the 2nd added rule to finish off your computation:

$$
\langle \mathsf{assert}\ \mathsf{True} \wedge \mathsf{True}\  \mathsf{before}\ \mathsf{skip}, s\rangle
\to
\langle \mathsf{assert}\ \mathsf{True}\ \mathsf{before}\ \mathsf{skip}, s\rangle
\to
\!\, \langle \mathsf{skip}, s \rangle
$$


Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$ In an exercise, I am asked to find a context free grammar for language $L = \{a^{2^k}, k \in \mathbb{N}\}$.

I have been trying to use a "doubling" variable. If $a^{2n} \in L, n\in\mathbb{N}$ then use this variable to double the $a$'s that have been produced by the other language rules.

Is this thinking valid? So far I haven't been able to get anywhere with it, but it seems logical given the double-stack of powers.

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context-free language according to Pumping lemma for context-free languages.

Suppose $L$ is context-free. The pumping lemma says there exists some integer $p \ge 1$ such that every string $s$ in $L$ where $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \ge 0$.

Let $s$ be a string in $L$ longer than $p$, and $u$, $v$, $w$, $x$, and $y$ have the properties given by the pumping lemma. Thus $uwy, uvwxy, uv^2wx^2y\in L$. Let $a$ and $b$ be such that $$|uwy|=2^a, |uvwxy|=2^b$$ Note $b>a$. Then $$|uv^2wx^2y|=2|uvwxy|-|uwy| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$ But $2^a(2^{b+1-a}-1)$ is not a power of 2, and so $uv^2wx^2y\notin L$.


Fundamental idea of this memory denial of service simulation using array copy? I am just watching this lecture Computer Organization - Introduction And Basics where
the lecturer mentions about using a simple code to demonstrate how memory denial of service can be simulated in DRAM by exploiting an optimzation DRAM Controller does internally. The optimization seems to be that DRAM Controller serves the same row buffer whenever possible for the instructions coming to the pipeline and so it can be exploited by sending instructions that use a very localized data giving it priority.

//initialize large arrays A and B

for(j=0; j<n; j++)
{
index = j*linesize;
A[index] = B[index]
}

I just wanted to understand the fundamental concept of this approach. The Lecturer says that the above code would copy an Array from B to A. However I am not sure how it actually would copy an Array from B to A because it doesn't seem to go over each index item.

My real doubt, assuming that this is just a simulation code which copies some part of B to A for demonstration purpose and that linesize is just a large value to make a cache miss, is if the central idea behind this something like:

a) chose an index that is sufficiently wide apart so that a       cache miss happens

b) yet the memory is close enough for it to be in the same row for the memory controller to serve from the same row buffer

Which is needed to simulate this DoS (denial of service) scenario?

Quoting from the paper that explains this in depth Memory Performance Attacks - Denial Of Service In Multi Core Systems

  The arrays in stream are sized such that they are much larger than the
  L2 cache on a core. Each array consists of 2.5M 128-byte elements. Stream (Figure 3(a)) has very high row-buffer locality since
  consecutive cache misses almost always access the same row (limited
  only by the size of the row-buffer).

The idea is that this code does not copy the complete array, but due to the design of the memory hardware it takes just as much time as if it would. Reading and writing a single byte will move a whole cache line. So the code reading and writing does very little work, but causes the memory subsystem to perform a whole lot of work.


decider for a question not clear This question was asked and answered but I cannot understand the solution.

Why is it sufficient to test all strings of |Q| + 1 length?
Why should special state q be found?

the original question:
Show that the set of all TMs that move only to the right and loop for some input is decidable

L2={ M | M is a TM and there exists an input w such that in the computation of M(w) the head only moves right and M never stops}

The pigeonhole principle. If you go through $|Q|+1$ states, then there must be a state you have been in twice already. This means that because the input is $\sqcup$ almost all of the time, then we are stuck in a loop and the machine wont halt


Regular Expression with at least one a, even number of b I've been working on some regular expression questions, and came across one that I cannot figure out. Working on the language over $\{a, b\}$, the text asks for a regular expression for the language of all words having at least one a and an even number of b's, using only | and * (maybe $\varepsilon$ too). My idea so far has been something like $(a^*ba^*b)^*a^*a(a^*ba^*b)^*a^*$, but this doesn't match cases like bab, bbbab, or baaab.

Another way of seeing this which gives a factorized representation is to try to locate the first $a$. It appears after either an odd or an even number of $b$.

If it appears after an even number of $b$ then you only have to check that what follows also has an even number of $b$ which can be done with Yuval's expression $a^*(ba^*ba^*)^*$.

If the first $a$ comes after an odd number of $b$, then you also have to find another $b$ and then check that the rest contains an even number of $b$.

This could be translated as follows: $(bb)^*(a+ba^+b)a^*(ba^*ba^*)^*$. Again, you can replace $a^+$ by $aa^*$.


Recurrence relation for time complexity $T(n) = T(n-1) + n^2$ I'm looking for a $\Theta$ approximation of
$$T(n) = T(n-1) + cn^{2}$$

This is what I have so far:

$$
\begin{align*}
T(n-1)& = T(n-2) + c(n-1)^2\\
T(n) &= T(n-2) + c(n-1) + cn^2\\[1ex]
T(n-2) &= T(n-3) + c(n-2)^2\\
T(n) & = T(n-3) + c(n-2)^2 + c(n-1)^2 + cn^2 \\[1ex]
T(n-3) &= T(n-4) + c(n-3)^2 \\
T(n) &= T(n-4) + c(n-3)^2 + c(n-2)^2 + c(n-1)^2 + cn^2
\end{align*}
$$

So, at this point I was going to generalize and substitute $k$ into the equation.

$$T(n)= T(n-k) + (n-(k-1))^2 + c(k-1)^2$$

Now, I start to bring the base case of 1 into the picture. On a couple of previous, more simple problems, I was able to set my generalized k equation equal to 1 and then solve for $k$. Then put $k$ back into the equation to get my ultimate answer.

But I am totally stuck on the $(n-k+1)^2$ part. I mean, should I actually foil all this out? I did it and got $k^2-2kn-2k+n^2 +2n +1 = 1$. At this point I'm thinking I totally must have done something wrong since I've never see this in previous problems.

Could anyone offer me some help with how to solve this one? I would greatly appreciate it. I also tried another approach where I tried to set $n-k = 0$ from the last part of the equation and got that $k = n$. I plugged n back into the equation towards the end and ultimately got $n^2$ as an answer. I have no clue if this is right or not.

I am in an algorithms analysis class and we started doing recurrence relations and I'm not 100% sure if I am doing this problem correct. I get to a point where I am just stuck and don't know what to do. Maybe I'm doing this wrong, who knows. The question doesn't care about upper or lower bounds, it just wants a theta.

Just continue your reasoning as follows.

\begin{eqnarray}
T(n) &=& T(n-1) + cn^2 \\
&=& T(n-2) + c(n-1)^2 + cn^2 \\
&=& \ldots \\
&=& T(n-n) + c(1^2) + c(2^2) + \ldots cn^2 \\
&=& T(0) +c\sum_{1\leq i\leq n} i^2.
\end{eqnarray}

Do you know how to simplify this using the addition formula for the first $n$ squares?


What is the origin of λ for empty string? I usually use the symbol $\varepsilon$ for empty string (empty word or null string). But I know some people use $\lambda$ instead of $\varepsilon$.

I think $\varepsilon$ is derived from the word "Empty". However I don't know what's the origin of $\lambda$.

In automata theory, there is the epsilon transition of automata, and it's also said to be the lambda transition. For example, JFLAP software uses $\lambda$ for the label of epsilon transitions by default.

I googled on the origin and searched cs.stackexchange, but I couldn't find. Does anyone know a reference that describes this?

The German Wikipedia claims that $\lambda$ comes from "leer", which means "empty" in German. That seems plausible, as German used to be one of the major languages in mathematics.

Chomsky used $I$ as the empty string (or actually as the identity element for string concatenation) in his early papers. Some people in combinatorics still use $1$ as the empty string, with the same justification.


Could a modification of Krom's proof system be used to solve 3-SAT in polynomial time? A literal is a nonzero integer, and we define $\sim x = -x$.
A clause is a nonempty set of literals.
A CNF is a set of clauses.
A K-rule is a pair $(F,C)$ where $F$ is a CNF and $C$ is a clause.
A Krom-style proof system (KPS) is a set of K-rules.
If $S$ is a KPS, then an $S$-proof of $C$ from $F$, or an $(S,F)$-proof of $C$, is a sequence $\langle C_1,..,C_n\rangle$ of clauses such that $C = C_n$ and for all $1\le i\le n$, either $C_i \in F$ or there is a K-rule $R = (G,A) \in S$ and a function $f : \{x,\sim x : x \in B \in G \lor x \in A\} \rightarrow \mathbb{Z}_{\ne 0}$ which respects negation such that letting $g(B) := \{f(a) : a ∈ B\}$, we have $C_i = g(A)$, and for all $B \in G$, there exists some $j < i$ with $C_j = g(B)$.
For fixed $S$, the language $\{(F,C) : F \vdash_S C\}$ is polynomial-time decidable:

read inputs F and C
if C ∈ F
    return true
let D = {x1,~x1,..,xn,~xn} be the set of literals occuring in F or C, and their negations
Contin := true
while Contin
    Contin ← false
    for (G,A) in S
        for h : {abs(x) : x ∈ B ∈ G ∨ x ∈ A} -> D # there are |D|^c such functions
            f(x) := (x > 0 ? h(x) : -h(-x))
            g(B) := {f(a) : a ∈ B}
            for B in G
                if g(B) ∉ G
                    continue in the for-loop where h is chosen
            if g(A) ∉ F
                push g(A) to F
                Contin ← true
if C ∈ F
    return true
else
    return false

$S$ is sound if for all CNF's $F$ and clauses $C$, the existence of an $(S,F)$-proof of $C$ implies that $F \vDash C$.
$S$ is complete for a class $\Gamma$ of CNF's if for all $F \in \Gamma$ and $C$, if $F \vDash C$ then $C$ is $(S,F)$-provable.
No KPS is complete for full $SAT$, since any clause of the form $\{-1,1,2,3,..,n\}$ is tautological, but for any system $S$, $sup\{|A|  : (\emptyset,A) \in S\}$ is only finite, making the clause $(S,\emptyset)$-unprovable for sufficiently large $n$.
$\{(\{\{1\},\{-1\}\},\{2\})\}$ is complete for $1$-$SAT$, and represents the rule $a,\sim a \vdash b$.
$\{(\emptyset,\{1,-1\}),(\{\{1\}\},\{1,2\}),(\{\{1,2\},\{-1,3\}\},\{2,3\})\}$ is complete for $2$-$SAT$, and represents the system consisting of the rules (1) $\vdash a\lor\sim a$, (2) $a\lor a \vdash a\lor b$, and (3) $a\lor b, \sim a\lor c \vdash b\lor c$.
Question 1. Is it known that no sound KPS can be complete for $3$-$SAT$?
If such a KPS was found, it would imply $P=NP$ and the polynomial-boundedness of natural propositional proof systems.
I am particularly interested in the completeness of the system $S_3 = \{(\emptyset,\{1,-1,2\}),(\{\{1,2,3\},\{1,2,4\},\{-3,-4,5\}\},\{1,2,5\})\}$ for $3$-$SAT$, where the main rule corresponds to the fact that if $a \land b \Rightarrow c$, $a \land b \Rightarrow d$, and $c\land d\Rightarrow e$, then $a\land b\Rightarrow e$.
Question 2. Can $S_3$ be shown to be complete for $3$-$SAT$, or at least some restricted class thereof such as $Horn$-$SAT\cap 3$-$CNF$ or the pigeonhole principle?
An $(S,F,d)$-proof is the same as an $(S,F)$-proof $\langle C_1,..,C_n\rangle$, except that we have a function $h : \{1,..,n\} \rightarrow \{0,..,d\}$, and the last part of the old definition, namely "$C_j = g(B)$", is strengthened by additionally requiring that $h(j) < h(i)$.
So far, I have been able to show that if $\langle C_1,..,C_n,C_{n+1}\rangle$ is an $(S_3,F\cup \{\{a,b,c\}\})$-proof of $C_{n+1} = \{d,e,f\}$ with $C_1,..,C_n \in F$, then for $x=a,b,c$ there exists an $(S_3,F\cup\{ \{\sim d\}, \{\sim e\}, \{\sim f\}\},5)$-proof $\langle D_1,..,D_{23}\rangle$ of $\{\sim x\}$.
However, the algorithm given above takes $O(n^8)$ steps on the RAM model of computation in the case of $S_3$. Krom's original algorithm for 2-SAT had a running time of $O(n^3)$, but this upper bound has since been improved to $O(n)$, even if we want to find a satisfying assignment when one exists.
Question 3. How quickly can we solve the $S_3$-provability problem? If this system happens to be complete for $3$-$SAT$, how quickly can we find satisfying assignments to consistent formulae?

Any proof in KPS (with whatever rules) can be rephrased as a sequence of lines, each of which is either a clause or follows from preceding lines according to one of finitely many inference rules. Additionally, the lines come from one of finitely many "patterns" (formulas with placeholders to variables), and so all proofs are polynomially bounded.

Suppose that the maximum depth of a pattern is $d$. Then your proof is also a proof in depth $d$ Frege. It is known that the pigeonhole principle needs $2^{\Omega(n^{1/5^d})}$ lines to refute in depth $d$ Frege. This implies that KPS systems cannot be complete for 3SAT, since all proofs in KPS are polynomially bounded.


Push down automata acceptance by Empty stack and final state I have a very basic question.  Can we have a PDA which can accept a string by  both final states and empty stack?
Can the same PDA accept by the two modes simultaneously ? If there are final states for acceptance and in addition to that at some point in time the input string is read completely and simultaneously the stack is empty but the state is non-final. Will it be accepted in that case ?

Yes, that is possible. If you start with one that accepts by final state, you can change that one into an automayon that accepts by final state and empty stack as follows.

First create a new final state $f$. From every old final state have an epsilon transition to the new state $f$. Add transitions to $f$ that empty the stack.

It seems best to keep the old final states. A computation of the old automaton might end in one of the old final states with an empty stack, in which case it should be accepted, but we have no contents of the stack, so we cannot move to $f$.


Is this correct in term of big-oh notation: given $g = O(f)$ and $h = O(f)$ can we say $g = O(h)$? We have two equations $g = O(f)$ and $h = O(f)$ , then can we derive that $g = O(h)$.
I came up with following proof but i dont know it's correct or not.
$$g = O(f)$$
$$g \le c_1*f $$
$$h \le c_2*f $$

Now we have to prove,
$$g = O(h)$$
$$g \le c_3*h$$
$$g \le c_3*c_2*f  $$
$$ c1 \le c3*c2 $$
We can find $c_3$ such that last equation $ c1 \le c3*c2 $ will be true.

  Is this correct or not? If not what will be correct proof for this?


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)

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)$.


Breadth First Traversal for graph with multiple connected components I read BFS and DFS from CLRS and realized that the BFS algorithm does not consider graph with multiple connected components but only with single connected component, whereas DFS algorithm considers graph with multiple connected components as can be seen in below pic:

Are my observations correct? If yes, why is it like that? Is their any significance to it? Is their any reason for CLRS to give such algorithm or its perfectly acceptable to modify BFS to loop over all vertices, something similar to DFS in order to traverse all connected components of graph?

This is not a fundamental difference.  You can easily do BFS on a graph with multiple connected components by using the same loop as in lines 5-7 of the DFS procedure you show:

for each vertex $u \in G.V$:

if $u.\text{color} == \textsf{white}$:

BFS($G,u$)


Closed formula for two variable recurrence I would like to know if there exists a closed form formula to the following recurrence:

$f(s, 0) = 1$
$f(s,b) = \displaystyle\sum_{i=1}^{min(s, b)} \left[
  (s-i+1)\times f(i, b-i) \right] $

This recurrence gives the solution to problem F of the ICPC Latin American regionals of 2019.

The problem itself can be solved in $O(n^2)$ by using dynamic programming and keeping a matrix of precomputed sums. I'm just curious about if there is some technique that allows obtaining a closed formula to recurrences like this, so I can solve it in better runtime complexity.

I do not have a strong mathematical background, but I am afraid that recursive functions cannot always been written in closed form.

ex1.

f(n) = sum([1,2,..,n]) can be written as
f(1) = 1
f(n) = n + f(n-1)

Of course f(n) = n*(n+1)/2

ex2.

f(n) = prod([1,2,3,4,..n]) = n!
f(1) = 1
f(n) = n * f(n-1)

No known closed formula :( (I don't even know how to prove something like this)

In your case, I find it extremely difficult because your recursion makes use of an if statement under the min() function.


Looking for an algorithm to find a shortest path in a special graph I have the following problem: given a directed unweighted graph and a set of source vertices, it's needed to find the shortest path to the specified vertex. The mentioned graph has two special extensions:

A graph's edge can be active or inactive depending on edges placed in the path before. In other words, the edge $E$ can be placed in the path at position $i$ only when $ f( E, path[1..i-1] )$ is true. The $f$ function in not specified explicitly; each path has a corresponding set of named properties and each graph edge has a function which modifies property values if the edge is involved (placed in the path). The edge $T$ is active (i.e. can be inserted in the path) if $g(T, set\ of\ properties)$ is true. A property may have a boolean or enum value, but it is desirable for me to allow properties to have integer and string values too.
Two adjacent edges in a path are not required to be linked. I.e. $path[j].end$ is not necessary equal to $path[j+1].start$. For example, we want to add the edge $B$ to the path and it has a property requirement which can only be satisfied if the edge $A$ is placed in the path before the $B$. In this case a $path[j]$ edge equals to the $A$ and $path[j+1]$ edge corresponds to the $B$. Still, $path[j+1].start$ should be equal to at least one of $path[1..j+1].end$ vertices.

The graph examples I've seen are sparse and pretty small (several dozen vertices). However some paths may contain up to several thousands of edges to satisfy the complex transition rules.

My current solution to this problem is based on the BFS algorithm. First, I construct a new graph where each vertex represents a vertex in the source graph plus the current path and it's property values. This is similar to how a game like Chess can be represented as a graph: a set of vertices each describing a current state of the game and a set of edges which describe the possible actions. Then, I simply use the BFS to find the shortest path. This approach has several drawbacks:

For each combination of property values a new vertex should be created. If property has an integer value, the number of vertices is going to be really large.
Because of the extension number two, the vertex can have a large number of edges connected. We need to represent an each edge which can be visited from this state, and when path is long the number of edges becomes big too.
If I need to find a path to several vertices, it's necessary to start a search several times and combine received paths. In some cases it is possible to make a shorter path if the algorithm will be aware that I actually need to reach several vertices, not the single one only.

My questions are:

Are there an existing name for such graphs? I've learned about dynamic graphs and they don't fully correspond to my description because they don't usually have a state (a state is the main feature of my graph).
Are there any better (faster, with less computational complexity, more functional) algorithms to find the shortest path in such graphs? To be more specific, are there an algorithm which solves at least some of the issues mentioned before?
If such algorithms exist, are there any libraries that implement it?

P.S. $f$, $g$ functions are simple logical predicates or integer arithmetic expressions. For example, to require some edge to repeat 100 times in the path I may set transition function for this edge as $i_{new} = i_{old} + 1$ and place another edge after it with $g$ equal to $i > 100$. SMT solver may be a helpful tool for this task, but I don't know how to encode the problem itself in a solver format. Also I'm not sure that applying SMT is the best approach.

The "state" of a traversal (after visiting $k$ edges) is the set of $k$ edges that you've traversed so far, in the order they were traversed.  You can now use any method for exploring this state space: e.g., BFS; or A*, if you have a suitable heuristic.

In other words, we define a new graph $G'$ where each vertex of $G'$ is a possible state of a traversal (after visiting some number of edges), and where there is an edge $u \to v$ if starting from state $u$ it is possible to add one edge to the end to reach state $v$.  Then you do BFS in $G'$.  You don't need to build up $G'$ explicitly before doing BFS; the graph can be represented implicitly (where each time you reach a state $u$, you can compute all possible next-states reachable from $u$ in a single step).

If BFS takes too much memory, you can use techniques from explicit-state model checking.  This will reduce the space consumption but not the memory usage.

None of this avoids the fact that, for arbitrary functions $f,g$, the running time of these algorithms might all be exponential in the worst case, because you might need to explore an exponentially-sized state space.  I suspect the only hope to do better is to take advantage of knowledge of some particular structure in $f,g$.


Hardware thread context and register renaming I'm having some issues understanding what happens on a context switch with the physical register file in an out-of-order CPU that implements context switching. Suppose that a CPU consists of 4 hardware thread contexts and that the ISA consists of 32 architectural registers. Does the physical register file get overwritten when a context switch occurs, or do the 4 hardware thread contexts compete on the use of physical registers, for faster context switches (because they don't need to be overwritten)?

More concrete: "Does a CPU with 4 hardware thread contexts and an ISA consisting of 32 architectural registers and 96 physical registers in total make sense?"

I am not expert about hardware threading but I know two different ways to achieve it with potentially different answers:

Architectures where the CPU executes one thread at a time but switches on some events (quantum expire, cache miss, switch instruction, ...). In that case, the CPU only really needs 32 registers and on a context switch it can store/load them from either physical registers or memory. Another option is to to register renaming (see below)
Architectures where the CPU really executes the thread in parallel: this can be a Barrel processor that switches on every cycle, or a more complicated out-of-order architecture like Hyper-threading. In both cases, the CPU really needs 128 registers. The way it is usually implemented is that registers are renamed: the CPU has registers 0-95, and register i of thread j is renamed to 4*i+j (for example register 2 of thread 3 is renamed 3*32+2=98). The advantage of doing that is that the pipeline and functional units scheduling and all becomes almost thread agnostic.


Feedback Vertex Set with vertex partitions? I've encountered this problem in a program analysis project I'm working on, where I've got a bunch of functions defined in terms of each other, and because I'm using SMT which doesn't support recursion, I'd like to define as many functions outright as possible, so that fewer are left to be solved by the SMT solver.

In terms of pure graph theory, my problem is this:

Given:

A directed (possibly cyclic) graph $G=(V,E)$
A partitioning of $V$ into disjoint subsets $V_1, \ldots, V_k$

I want to choose:

$v_i \in V_i$ for each $1 \leq i \leq k$ that minimizes the feedback-vertex number of the subgraph of $G$ induced by $\{v_1,, \ldots v_k \}$

I'm fairly guessing the problem is $NP$-hard, because of its reliance on the Feedback Vertex Set problem. If we assume that our $V_i$ sets are small, say with a maximum size $M$, then there are at most $M^k$ combinations to try.

I'm wondering:

Has this problem (or anything similar) been studied before?
Is this problem $NP$-hard, or does it fall into one of the subsets of feedback-vertex that is tractable (e.g. chordal graphs, convex-bipartite, etc.)
Does anyone know of a way to reduce the Feedback Vertex Set problem to this? It's solvable in $O(1.7548^n)$ time, so if I can translate my problem into this one it's entirely possible it's solvable for small inputs. But for all I know, my problem is harder than Feedback-vertex.
Are there any approximation algorithms that can be adapted to my variant of the problem, that are maybe not optimal, but would give near-optimal results quickly

Your problem reduces to Feedback Vertex Set by turning every subset $V_i$ into a clique, and creating one additional vertex $v_i$ for each subset $V_i$ that is adjacent to all vertices in $V_i$. It might be easier to think in terms of the complement problem, Maximum Induced Forest.

Since $V_i\cup \{v_i\}$ is a clique, we can select at most two vertices from this set to be in our solution (to Maximum Induced Forest). We can assume $v_i$ is always in the solution, since if less than two vertices of $V_i$ are in the solution we can safely include $v_i$, and if exactly two vertices of $V_i$ are in the solution then $v_i$ is not, but we can swap one of these two vertices (from $V_i$) with $v_i$.

A solution to Maximum Induced Forest thus selects at most one vertex from each set $V_i$ such that the result is a acyclic, and these are exactly the vertices we should select in a solution to the original problem (from the sets $V_i$ from which no vertices are selected, we can just arbitrarily select a vertex, and this vertex will be in our feedback vertex set). Conversely, it is easy to see how a solution to the original problem corresponds to a Maximum Induced Forest/Feedback Vertex Set in the graph created in this reduction.

This gives you a $O(1.7548^{n+k})$-time algorithm. If you allow parallel edges you can (instead of creating this additional vertex $v_i$) double up the edges in every clique, which has the same effect (and may give a faster algorithm, if your algorithm for solving feedback vertex set allows for parallel edges).

The problem is $NP$-hard. We can reduce from Feedback Vertex Set. To decide whether a graph has a Feedback Vertex set of size at most $s$, we create $s$ cliques of size $n+1$. We can force that one vertex of this clique is always in the solution (by including it in a singleton set $V_i$). We then create for each vertex $v$ in the original graph a set $V_i$ that contains $v$, and one vertex from each of the $s$ cliques. In at most $s$ of these sets $V_i$, we can select a vertex from each clique, but in the remaining $n-s$ sets we must select a vertex from the original graph. Therefore, we can find a solution to the original problem with feedback vertex set number $0$ if and only if the input graph had feedback vertex set number of at most $s$.


in O(n) time: Find greatest element in set where comparison is not transitive Title states the question.

We have as inputs a list of elements, that we can compare (determine which is greatest). No element can be equal.

Key points:

Comparison is not transitive (think rock paper scissors): this can be true: A > B, B > C, C > A (note this is not a valid input since there is no valid answer here, I'm only describing what "non-transitive comparison" means)
Each input array will is guaranteed to have an answer
greatest means the element must be greater than every other element
Converse property holds i.e. A > B implies that B < A

Example:

Input: [A,B,C,D]
A > B, B > C, C > A
D > A, D > B, D > C
Output: D

I cannot figure out a way to do this in O(n) time, my best solution is O(n^2).

I get stuck on every approach because of the fact that to be certain of an answer, the element needs to be explicitly compared to every other element, to prove it is indeed the answer (because comparison is not transitive).

This rules out the use of a heap, sorting, etc.

The standard algorithm for finding a maximum still works. Start with $a_1$ and go over the elements, if you see a larger value, update the maximum to be that value. The reason this works is that every element you skipped is smaller than at least one element, and can thus not be the maximum.

To be clear, by the "standard algorithm" I mean the following:

max <- a_1
for i=2 to n
   if a_i > max
      max <- a_i
output max

For completeness, I will discuss here the issues raised in the comments. The setting in the above discussion is finding a maximum relative to an anti symmetric relation $<$, where $a_i$ is a maximum if for all $j\neq i$ we have $a_i>a_j$. The above algorithm works under the assumption that a maximum exists, however if this is not known, one can use it to verify the existence of a maximum (check whether the returned element is indeed greater than all other elements, this is mentioned in Chi's comment and in Ilmari Karonen answer).

If $<$ is not necessarily anti symmetric, then the above algorithm fails (as Emil mentioned in the comments). If $<$ is an arbitrary relation (i.e. we are relaxing both transitivity and anti symmetry), then it is not hard to show that finding a maximum in linear time is not possible. Denote by $\#a_i$ the number of times $a_i$ participated in a query, we define an adversarial relation in a way that the maximum cannot be revealed without enough queries. Given the query $a_i >?a_j $, answer $a_i>a_j$ if $\# a_i < n-1$ and $a_i<a_j$ otherwise. If the number of queries is $o(n^2)$, then a maximum was not yet seen, and it can be set to be either of the elements in the set.


Optimizing a strictly monotone function I am looking for algorithms to optimize a strictly monotonic function $f$ such that $f(x) < y$

$f : [a,b] \longrightarrow [c,d]
\qquad \text{where } [a,b] \subset {\mathbb N},  [c,d] \subset {\mathbb N}$
such that $\arg\max{_x} f(x) < y$

My first idea was to use a variant of binary search, pick a point $x$ in $[a,b]$ at random; if $f(x) > y$ then we eliminate $[x, b]$, and if $f(x) < y$ we eliminate $[a, x]$. We repeat this procedure until the solution is found.

Do you have any other ideas to maximize the function $f$ ?

Given the discrete intervals $[a,b]\subset\mathbb{N}$ and $[c,d]\subset\mathbb{N}$, we might be able to do slightly better than binary search using the midpoint without utilizing gradient descent.

Instead, we could use binary search with $x=a+\lfloor\frac{y-c}{d-c}(b-a)\rfloor$, which corresponds to the below intersection of the dotted purple line denoting $y$ and the line from $f(a)=c$ to $f(b)=d$.

The red and blue lines represent the extremes of strictly monotonic functions.
When $f$ is linear, this would immediately find the closest $x$ (which is a big improvement over binary search with the midpoint). Without additional information, I think linearity is the best assumption you can make; there are as many concave functions as convex functions, as well as functions that switch.

One justification for not using gradient descent is if an array $[a,a+1,\dots,b]$ is simply mapped to another array of the same size but different range of data $[c,d]$, which is  randomly chosen (and sorted).

Otherwise, you could use Newton's method as suggested by Dave Clarke or gradient descent as suggested by Raphael, which I just learned are different.


Is this argument wrong "since DOM is special kind of RDOM, then RDOM is NP-hard"? The domination problem $DOM$ is defined as
$$
DOM = \{ \langle G,k \rangle\ | \ G \text{ has a domination of size } k, K \in \mathbb{N} \},
$$
and the rainbow domination problem $RDOM$ is defined as
$$
RDOM = \{ \langle G,r,k \rangle \ | \ G \text{ has a r-dominating set of size } k; r,k \in \mathbb{N} \}.
$$
A $r$-rainbow domination for a graph $G=(V,E)$ is a mapping of the form  $f:V \rightarrow 2^{\{ 1,\ldots, r\}}$ such that $f(v) = \emptyset$ implies $\cup_{u \in N(v)} f(u) = \{ 1,\ldots , r\}$ where $N(v) = \{ u \ | \ \{u,v\} \in E \}$.  The size of $r$-domination is defined as $\sum_{v \in V} |f(v)|$.

To show that $RDOM$ is $\mathbf{NP}$-hard, one must show that $DOM \leq_P RDOM$, i.e. given an instance $\langle G,k \rangle$, construct an instance $\langle G',r,k' \rangle$ in polynomial time such that $\langle G,k \rangle \in DOM$ if and only if $\langle G',r,K' \rangle \in RDOM$.

My friend states that we know that a domination is a $1$-rainbow domination in the same graph, i.e. domination is a special kind of rainbow-domination, and since domination is $\mathbf{NP}$-hard, then $RDOM$ is also $\mathbf{NP}$-hard. How to convince him that this is wrong? or this argument is correct?

There are two statements here that rule the argument. The first statement:

  Statement 1.
  To show that $RDOM$ is $\mathbf{NP}$-hard, one must show that $DOM
 \leq_P RDOM$, i.e. given an instance $\langle G,k \rangle$, construct an instance
  $\langle G',r,k'\rangle$ in polynomial time such that $\langle G,k \rangle \in DOM$ if and only
  if $\langle G',r,K'\rangle \in RDOM$.

is a general framework for showing that RDOM is NP-hard. However, in this statement, you have not shown how to prove that this reduction works. You just said how to prove that this problem (or any problem) is NP-hard. In order to prove it, you need a proper reduction from all instances of DOM to instances of RDOM. The second argument however,

  Statement 2.
  By the way, my friend states that we know that a domination is a
  $1$-rainbow domination in the same graph, i.e. domination is a special
  kind of rainbow-domination, and since domination is
  $\mathbf{NP}$-hard, then $RDOM$ is also $\mathbf{NP}$-hard. How to
  convince him that this is wrong? or Is this argument correct?

looks like a proper reduction. If "every domination is a $1$-rainbow domination in the same graph", then this proof is completely right. This is a proper reduction from every instance of DOM problem to instances of RDOM or 1DOM problem. However, if "every domination is NOT a $1$-rainbow domination in the same graph", then this proof is completely wrong.

My understanding is that a domination, can be any of 1-rainbow domination, ...,or |V|-rainbow domination. In this case, it is implied that by having a polynomial algorithm for RDOM problem, you can iterate $|V|$ times thorough $r$-dominations and determine if the graph is dominating. Thus, if you have a polynomial algorithm for RDOM problem, you can solve the DOM problem polynomially.


minimizing the summed cardinality of set unions this optimization problem, I am working on, is kind of making me crazy. ;)

Given is a list o of sets (with finite cardinality) of strictly positive integer values (Z>0), e.g.:

o_without_sizes =
[ {1, 2, 3, 4}
, {5, 6}
, {2, 3, 4, 5}
, {5, 6, 7}
, {7, 8}
. {9} ]

Every set has a name n (also in Z>0, but only for identification) and a fixed independent size value s (also in Z>0), e.g.:

type O = [(Name, Size, Values)]
o =
[ (1, 2, {1, 2, 3, 4})
, (2, 1, {5, 6})
, (3, 2, {2, 3, 4, 5})
, (4, 3, {5, 6, 7})
, (5, 2, {7, 8})
. (6, 1, {9}) ]

These sets are to be combined to unions b of a maximum size value sum h (>= max s, that means that no set has a size making it too big to fit into a single union), e.g. 4.

The goal is to find the b so that the sum of cadinalities of the unions in it is as small as possible.
here is a bad b:

size:   3,  cardinality:   6,   sets: [1,2]  ,  values: [1,2,3,4,5,6]
size:   2,  cardinality:   4,   sets: [3]    ,  values: [2,3,4,5]
size:   3,  cardinality:   3,   sets: [4]    ,  values: [5,6,7]
size:   3,  cardinality:   3,   sets: [5,6]  ,  values: [7,8,9]
cardinality sum:  16

and the optimum b for this example:

size:   4,  cardinality:   5,   sets: [3,1]  ,  values: [1,2,3,4,5]
size:   4,  cardinality:   3,   sets: [2,4]  ,  values: [5,6,7]
size:   3,  cardinality:   3,   sets: [5,6]  ,  values: [7,8,9]
cardinality sum:  11

Until now I only implemented a naive brute force solution (Haskell code): http://lpaste.net/7204008959806537728

I was hoping to find a dynamic programming solution like it exists for the (Z>0) 0-1 knapsack problem, but did not yet succeed.
Is my problem perhaps NP-hard? If so, is it many-one-reducible to SAT or something? Or is there a good approximation?

Of course, if there exists a known efficient optimal algorithm, it would be awesome if you could enlighten me. :)

Your problem is NP-complete. We show this by reducing Partition to it.

In Partition you are given a set of numbers $a_1, \ldots, a_k$ and have to decide, if this set can be partitioned into two sets that sum up to the same value.

We map an instance of Partition to your problem by introducing for each $a_i$ the set $(i, a_i, \{1\})$. Set the maximum size to $\frac 12\sum_{i=1}^ka_i$. The original instance can be partitioned if and only if the resulting one can be united to cardinality sum 2.


Constructing a Turing machine which decides whether a fixed TM will halt on a fixed input or not It is known that the halting problem is decidable for every fixed $M_0$ Turing machine and every fixed $w_0$ input.

My related question would be the following: is it true that for every fixed $M_0$ Turing machine and every fixed $w_0$ input, an $M_{M_0,w_0}$ Turing machine can be constructed for which the possible inputs are $(M, w)$ machine-input pairs, and for the $(M_0, w_0)$ pair, the output is "1" if $M_0$ will halt on $w_0$ and "0" if $M_0$ will not halt on $w_0$? ($M_{M_0, w_0}$ can give false answers for other pairs, it is not demanded that it has to run correctly for every $(M, w)$ pair.)

Since $M_0$ and $w_0$ are fixed parameters of the problem, the answer is yes: for every fixed $M_0$ and $w_0$, there exists a Turing machine $M_{M_0, w_0}$ (depending on  $M_0$ and $w_0$) such that, for the input $(M_0, w_0)$, $M_{M_0, w_0}$ returns $1$ if $M_0(w_0)$ halts and 0 otherwise.

In particular one such Turing machine $M_{M_0, w_0}$ must be one of the following two machines:

$M'_1$: Write $1$. Halt.
$M'_0$: Write $0$. Halt.

If, instead, you are looking for an algorithm that takes $M_0$ and $w_0$ as input and outputs a machine $M_{M_0, w_0}$ with the above property, then you are out of luck: there is not such algorithm in general (it might exist if you restrict the set of input machines $M_0$).
Suppose that such an algorithm (i.e., Turing machine) $A$ existed, then it would allow to solve the halting problem:

Given $M_0$ and $w_0$, compute $M_{M_0, w_0}$ by simulating $A$ on input $(M_0, w_0)$.
Simulate $M_{M_0, w_0}$ on input $(M_0, w_0)$. By definition of $M_{M_0, w_0}$ this step requires finite time.
Return "yes" if the output of $M_{M_0, w_0}( (M_0, w_0) )$ was $1$, otherwise return "no".


Covering a directed graph with particular requirements I'm actually trying to solve a task from an old OII (Italian national pre-IOI competition) in which I'm given an unweighted directed graph $G$ with $N$ vertices and $M$ edges and I'm asked to find a set of vertices $S$ which satisfies these conditions.
If we call $S^1$ the set of vertices that can be reached by crossing a single edge from any of the vertices in $S$, there can't be any vertex in both $S1$ and $S$.
Then we call $S^2$ the set of vertices that can be reached by crossing a single edge from any of the vertices in $S^1$.The set $S$ is a solution to this problem only if every vertex in $G$ is part of at least one of the sets above.
Couldn't think of anything better than an $O(2^n)$ solution, which leads to TLE. I'm given a time limit of 3 seconds, with $N < 1000$ and $M < N(N-1)/2$.

Something I realized is that I have to consider each different connected part on it's own and some vertices simply must be part of $S$ (if there are no edges starting from another vertex that reach them), but this assumptions didn't help much.

I apologize for my english and my poor computer science knowledge, I'm sure some parts should be reformulated but I couldn't find the right words to do that.

This problem is solvable if you have studied computer science, know standard graph problems, can spot a relationship to one of them, and then diligently study what is known about algorithms for that sort of problem.

If this immediately makes you think that it sounds related to some standard, well-known graph algorithm problem (call it Problem X), then go read about what is known about algorithms for Problem X and variants of Problem X.  You'll soon find an existing algorithm that can be adapted for this.

If you can't spot any relationship to any graph problem you already know, then you should spend more quality time studying an algorithms textbook.  Pick a good algorithms textbook and read it through cover to cover.

Alternatively: What algorithm design paradigms do you know?  For each paradigm you know of, try to find an algorithm of that type.  You should be able to find one for this.

I'm not going to say more than this.  It's your exercise, so you should have the joy of finding the answer on your own; I don't want to take away from that.  Also, practicing problem solving on your own is the best way to strengthen your problem-solving skills.  If you just read someone else's solution, you won't learn nearly as much.


Does the circuit value problem require only log space in alternating Turing machines Why does the circuit value problem run in log space on an alternating Turing machine? It is claimed to be so in my university's lecture notes. Also, it is claimed that monotone circuit value problem has the same space complexity on an alternating Turing machine.

I think it requires at least linear space because it needs to store the current assignment that we are checking and also some bits for the working and storing outputs of sub circuits.

It is a classical result that ALOGTIME=P. You can find a proof in lecture notes of Madhu Sudan. Both the circuit value problem and the monotone circuit value problem are P-complete, and in particular in P, and so can be solved in alternating logarithmic space.

One thing which might be confusing you is that we only measure space on work tapes. Space on the input tape is for free, though this comes at a price: you are not allowed to modify it.


How do we fix area of detectors in object detection? I have gone through various articles on medium and also some from other sites trying to understand SSD. I am able to figure out most of the things from articles except this one.

They always say that the area and location of detectors/anchors in fixed in the model. They also show us the various shapes of detectors based on aspect ratio. But I can't understand how to fix the location of detectors.

Suppose, I want my detector to focus only on the top-right of the image, how can I achieve that? I mean, the filters learned by CNN are applied to the whole image by sliding through its parts. How can we actually achieve this?

Is this related to 'receptive field' or '1x1 convolution'? I am trying to understand these two concepts too but haven't progressed much.

If you want to only look for matches in part of the image and ignore the rest, crop out the part you want to look in (removing the rest of the image), then apply the object detector to the cropped image.


A good-enough version of good-enough? When should I stop iterating? I am studying Abelson and Sussman's Structure and Interpretation of Computer Programs, 2/e. I solved the exercise 1.7, which asks for a better stopping criteria for an iterative function to calculate the square root function, and then checked my solution against one that I found on this site: http://community.schemewiki.org/?sicp-ex-1.7

The original function iterated until $|\mathtt{guess}^2 - \mathtt{x}| < 0.001$, but the book points out that something better is needed because this does poorly both for very large and for very small x.

The solution on schemewiki.org iterates until $|\mathtt{improve(guess, x)-\mathtt{guess}}| < .001\; \mathtt{guess}$, following the book's suggestion of watching "how guess changes from one iteration to the next and stopping when the change is a very small fraction of the guess."  (The improve function takes a guess and x and generates a better guess by averaging the guess with x/guess.)

While I instictively went for a precision relative to the magnitude of the radicand. $|\mathtt{guess}^2-x| < 0.001\;\mathtt{x}$.

Both functions seem to yield similar results. Mine seems more obvious and efficient to me. Maybe too obvious... I suppose there is something I missed ?

I did not check the code used in Abelson and Sussman's book or wiki.
My guess is that the recursive (or iterative) procedure will somehow
organize to compute improve(guess,x) only once. In a recursive
procedure, you just compare the formal parameter which is the previous
guess with the actual value (current guess) that you would pass for a
recursive call, in order to decide whether actually do the call rather
than return it. There may be a difference of one (wasted) iteration
depending on how you do the test.

Regarding the fact that you do the test on $x$ or on $\sqrt x$, or
rather $\mathtt{guess}^2$ or $\mathtt{guess}$, that does not give you the same
precison if you look for the same difference.

One way of explaining it is that $|\mathtt{guess}^2-x|=
|\mathtt{guess}^2-{\sqrt x}^2| = |\mathtt{guess}-\sqrt
x|(\mathtt{guess}+\sqrt x)$
since the second factor has to be positive (at least when relative
imprecision gets small).

Since $\mathtt{guess}$ is supposed to be very close to $\sqrt x$, we know that
$\mathtt{guess}+\sqrt x$ is very close to $2\sqrt x$ or
$2\;\mathtt{guess}$.

Hence $|\mathtt{guess}^2-x|$ is close to $2\sqrt
x\;(\mathtt{guess}-\sqrt x)$, so that the condition
$|\mathtt{guess}^2-x| < 0.001\;x$ can be replaced by
$2\sqrt x\;|\mathtt{guess}-\sqrt x| < 0.001\;x$, i.e.
$|\mathtt{guess}-\sqrt x| < 0.0005\sqrt x$
or, still using the same approximation:
$|\mathtt{guess}-\sqrt x| < 0.0005\;\mathtt{guess}$

This can be further formalized, but the above informal reasonning
gives you the idea.

However, I did not check how fast this conputation is converging, and
what is the difference between $|\mathtt{improve(guess,
x)-\mathtt{guess}}|\;$ and $|\mathtt{guess}-\sqrt x|$, i.e. how fast one
gets closer to the exact answer with each new iteration (assuming the
precision of the arithmetics is still good). Their ratio should also be accounted for. It depends on the formula used for computing the approximation, which I did not look at.


Find pairs of integers (a, b) in an array such that a = b + k in linear time - elements are not unique A while ago, I was asked to solve a question similar to this:

  We are given an array arr and we would like to find all pairs of items (a, b) where a = b + k. The items are NOT unique and it is also possible to have k = 0.

I know that if items are unique, this problem can be solved in linear time by using a hashmap. However, when items are NOT unique, I think that the problem becomes very different.

See this example:

arr = [1, 1, 1, 1, 1]
k = 0

The expected output is:

(1, 1), (1, 1), (1, 1), (1, 1) // For the first element
(1, 1), (1, 1), (1, 1)         // For the second element
(1, 1), (1, 1)                 // For the third element
(1, 1)                         // For the fourth element

As it is obvious to me, in the worst case (the above example) the output is of size $n \choose 2$, which is $\Theta (n^2)$. How is it possible to have a linear algorithm, when the output size is definitely $\Theta (n^2)$?

My interviewer insisted that it is possible to still solve it in linear time, if the correct data structure is used.

If you must write out all of the pairs individually, then the overall problem takes quadratic time because the running time of this last post-processing step is $O(n^2)$.

If you are allowed to represent the output in a different way, then you can simply keep track of distinct pairs and associate them with a counter (see run-length encoding). Thus, you can compute the solution in $O(n)$ time using the following algorithm:

Initialize an auxiliary array (or hash map) $Aux$.
Perform a first linear scan of the input array $Arr$ and use the auxiliary array to keep track of how many times each of the elements appears. For example, $Aux[2]=3$ indicates that $2$ appears $3$ times in $Arr$.
Perform a second linear scan of the input array $Arr$. During the $i$th iteration, $a=Arr[i]$ and you must look for the element $b =a-k$, which appears $c =Aux[b]$ times in $Arr$. If $c \gt 0$, then you will add the pair $(a,b)$ to your solution, associated with the count $c$. Two special cases that must be considered at step 3:

If the pair already exists in your solution, you can simply increment the existing counter by $c$.
If $k=0$, you must add the pair $(a,b)$ only if $c \gt 1$. The counter associated with this pair will not be set to (or incremented by) $c$, but, rather, by $c-x-1$, where $x$ stores how many times we have seen $a$ before.


number of comparisons in searching algorithms i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these.

For linear search :

procedure Linear_search(a1,a2,...,an:integers,k)
1.location = 0;
2.for i = 1 to n      #n+1 times
3.    if (a_i = k)  then location = i # n times
4.return location;

so total comparisons are =n+n+1=(2n+1). Right?

For Binary Search and ternary search,we know the algorithm.But the number of comparisons are,

T(n) = T(n/2) + 2,  T(1) = 1
 T(n) = T(n/3) + 4, T(1) = 1

Hence solving this will give 2clogn + O(1) and 4clogn + O(1).

how to constants(2 ,4) are formed??
Also correct me if my comparsions are wrong.

When measuring comparisons, we usually only charge comparisons of elements of the array (more accurately, we charge comparisons for the datatype of array elements, but not of array indices). In the example of linear search, at each iteration you are comparing one element of the array to the input element being searched. So in total, you are making exactly $n$ comparisons in the worst case.

For binary search, at each step you are making a 3-way comparison between the middle element of the current segment of the array and the input element. The number of 3-way comparisons satisfies the recurrence $T(n) \leq T(\lceil \frac{n-1}{2} \rceil) + 1$, with base case $T(1) = 1$ (when $n = 1$, you are making a 2-way comparison). If you are only allowing 2-way comparisons, then each 3-way comparison has to be simulated using two 2-way comparisons, which might be the reason why the recurrence has $+2$ instead of $+1$.

For ternary search, you are making two 3-way comparisons (comparing the two middle thirds to the input element), which translates to four 2-way comparisons.

(A 2-way comparison is one which has two outcomes: for example, "$x = y$?" is a 2-way comparison, as is "$x \leq y$?". A 3-way comparison is one which has three outcomes: given two elements $x,y$, the comparison tells you whether $x < y$, or $x = y$, or $x > y$.)


Design patterns for simple text based scripting language? In my current application I am trying to determine the best way to implement a simple scripting language. This language would allow a user to create a script that controls a machine with various inputs and outputs. I have defined most of the commands and created a nice editor for the language though I am stuck now trying to figure out how to verify, parse, and "compile" it.

I currently treat the commands as const String and plan to parse the input script text with regex and these strings. Most of the commands have the syntax

COMMAND Arg1 Arg2 Arg3 etc.

The types and numbers of arguments are currently not defined anywhere in my code, only in my head. I need a design pattern that would allow me to take a line from the script and determine if it is valid; check the command versus some list and check its arguments against the match in that list.

Are there any known design patterns for situations like this; scripting languages in general?

I feel like I need a class Command that holds the command string and information about its arguments, also the translation from string to "action" (performing the actual real life action the command describes). Then if I am to encounter the string representing the command I can lookup the command class instance, pass in the line, and get some result if it is valid. Though I feel like I would end up (in my case) with quite a few Command sub classes.

Any ideas or recommendations?

The last time somebody asked this question, I replied: why not just use an existing language?

What you have right now is an API.

You can provide a library in which your commands are function calls, or method calls, or whatever suits you.  This saves you from having to design and implement a language, and it saves your users from having to learn yet another little special-purpose language. They still need to learn your API, of course.

I'd say this is the standard design pattern for exposing APIs: as libraries for one or more existing languages.

If you really want to create a new language, you need to specify and implement its syntax and semantics.

For dealing with syntax, using a parser generator is definitely the standard approach. Any language whose programs don't just consist of simple lists of statements will have nested structures and most will allow syntactic recursion (i.e. among the various types of language constructs, some can appear within themselves arbitrarily often). For instance, you may wish to allow a command invocation as an argument to another command invocation, or you may want to have a construct to express iteration or choice that can be arbitrarily nested. In that case, you don't want to parse and process nested constructs with regular expressions, you want grammars, and parser generators are the standard way to work with grammars.

As to the surface syntax, the basic way in which the source code is chopped up into meaningful tokens of your language, I think the most important general lesson is: keep it general, easily readable and context-independent. Make the structure of your programs easy to understand for humans and computers.  Examples not to follow are such atrocities as Makefiles or /bin/sh in which the correct application of whitespace and quotes is advanced witchcraft.

As to the semantics, one of the things to decide is what sort of programming paradigm to support.  Are all commands of a program executed strictly in sequence without anything else ever interfering?  Then, a standard, strictly sequential imperative programming language may be a good option. Can commands set concurrent events in motion, or can multiple programs be running at once?  Then, a fundamentally concurrent language may be more appropriate.

Another thing to decide is to what extent you want your language to scale. If scripts can grow large and can be invoked by other scripts, you probably want to provide mechanisms for preventing different pieces of code from biting each other in the leg (e.g. scopes for names, local variables). But this is probably a later concern.


Are all minimum spanning trees optimized for fairness? I know by definition that a minimum spanning tree (MST) of a weighted, connected graph has the lowest global value for for sum of all edges in a path that connects all vertices.

I'm curious if all MSTs are also optimized for lowest individual edge value possible. (I know that ones calculated with Kruskal's Algorithm are!)

As an example, is it possible to have two MSTs in a graph (equal global sum of their edges) but have one of those MSTs contain an edge of higher value than any edge on the other MST in the graph.

Thanks for any help you can give!

is it possible to have two MSTs in a graph (equal global sum of their edges) but have one of those MSTs contain an edge of higher value than any edge on the other MST in the graph.

No, it isn't; assume it is, let $X$ be the MST with the heavy edge, and call that heavy edge $e := \{u,v\}$. Now there is some other MST $Y$ that doesn't contain edges that are at least as heavy as $e$. In $Y$, we know that there is a path from $u$ to $v$ since $X$ has such a path, so $Y$ must have one as well. Let $p$ denote that path in $Y$. There must be an edge $f$ on $p$ that isn't in $X$, since otherwise $X$ would contain the cycle formed by $p$ and $e$. Now add $f$ to $X$ and delete $e$ from it to get $X'$, which is a spanning tree as well. However, $X'$ has lower weight than $X$ since $f$ has lower weight than $e$, contradicting the assumption that $X$ is an MST.

For something more general which might answer your question more succinctly, here and here are proofs that all MSTs of a graph have the same multiset of edge weights, that is: if $k$ edges of weight $w$ occur in some MST, then $k$ edges of weight $w$ occur in all MSTs for any $w$ and $k$.

Something else that isn't proven in those answers that might be of interest to you: every MST only contains paths with smallest maximum weights for all pairs of vertices $\{u,v\}$, or in words: let $p$ be the unique path between $u$ and $v$ in a given MST $T$ of graph $G$; then for any $u$-$v$-path $q$ in $G$, the heaviest edge on $q$ is at least as heavy as the heaviest edge on $p$.

To prove this, assume that there is some pair $\{u,v\}$ such that the heaviest edge in the unique $u$-$v$-path $p$ in some MST $T$ is heavier than the heaviest edge in some other $u$-$v$-path $q$ in $G$. Let $e$ denote the heaviest edge in $p$; now remove $e$ from $T$, which partitions $T$ into two connected components $U$ and $V$ such that $u \in U$ and $v \in V$. We know that $q$ starts in $U$ and ends in $V$, so there must be an edge $f$ that belongs to the cut $(U,V)$. Now we find that $(T \cup \{f\}) - \{e\}$ is a spanning tree again, and since the weight of $f$ is smaller than the weight of $e$ by assumption, we find that $(T \cup \{f\}) - \{e\}$ has lower weight than the MST $T$, contradicting the minimality of $T$. Thus, no such path $q$ can exist in $G$.

Spanning trees with the heaviest weight being minimal are called minimum bottleneck spanning trees, and you can use the above to show that every MST is an MBST (the converse does not hold, i.e. there may be an MBST that is not an MST, specifically: an MBST might use too many heaviest edges). If an MST $T$ wasn't also an MBST, then there would be a heavier edge in $T$ than in some other spanning tree, and that edge would be on some path, and then the arguments above apply to that path.


Understanding arguments in Haskell type classes and instances I am trying to understand a Haskell class declaration and instance from a paper. I am trying to understand the class declaration:

class (Surfaces v o, Paths a b (v o)) => Vehicles v o a b

My current understanding is that the first occurance of types "v o" in the Vehicles context seems to refer to two distinct data types. I assume that it is the same for the "v o" on the right of =>.

Question 1

Is my understanding correct?  Does the bracketed "(v o)" in the Vehicles context refer a type constructor and its argument, rather than two independent types?

Question 2:

Is the instance OK? Why do I need FlexibleInstances

 instance Vehicles Boat Person Route (Water Source)

I apologize for the level of detail, but I believe that the context is important to my question.
Regards,
Pat

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
data Person = Person deriving Show
data House a = House a  deriving Show
data Boat a  = Boat a deriving Show
data Route a b = Route a b deriving Show
data Source = Source deriving Show
data Destination = Destination deriving Show
data Water a = Water a deriving Show
data Land = Land deriving Show

-- The three top level classes are constructor classes, indicated by the signatures of the methods (not the class header).
-- The kinds in the class headers have kinds * and *->*
-- "Containers a b" stands for all container types "a" holding things of type "b".
class Containers a b where
 insert :: b -> a b -> a b
 remove :: b -> a b -> a b
 whatsIn :: a b -> [b]

-- Type "a" is the type of  surface
-- Type "b" is the type object on the surface e.g. boat is on water.
class Surfaces a b where
 put :: b -> a b -> a b
 takeOff :: b -> a b -> a b
 whatsOn :: a b -> [b]

-- The path class represents motion
-- Type "c" represents the moving object e.g Boat.
-- Type "a" route
-- Type "b" origin and destination place
class Paths a b c where
 move :: c -> a b c -> a b c
 origin, destination :: a b c -> b
 whereIs :: a b c -> c -> b

class People p
class HeavyLoads l
class Surfaces w o => WaterBodies w o
class Containers h o => Houses h o

-- The types "v o" in the Vehicles the context seems to refer to two distinct data types.
-- I assume that it is the same for the "v o" on the right of =>
-- But "(v o)" in the Vehicles the context seems to refer a type constructor and its argument??.
-- Vehicles are derived from surfaces (affording to ride on the vehicle) and paths (affording motion).
-- Vehicles type class has  parameters for
--  the type "o" of the transported object
--  the type "a" of the path,
--  the type "b" of the origin and destination places.
--  "o" has kind *, "a" has kind *->*->*,  "v" has kind *->*
class (Surfaces v o, Paths a b (v o)) => Vehicles v o a b

instance Surfaces Boat Person
instance WaterBodies Boat Person  -- Boats carrying people on water
instance Paths Route (Water Source) (Boat Person) -- boat moving on water carrying people
instance Vehicles Boat Person Route (Water Source)  -- Boat as a vehicle

Question 1
Does the bracketed "(v o)" in the Vehicles context refer a type constructor and its argument, rather than two independent types?

In the constraint Surfaces v o, v and o are two separate type arguments to class Surfaces. Constraint Paths a b (v o) has three arguments: a, b, (v o). The third is v applied to o, so we can infer parameter v to class Vehicles is a type constructor, kind * -> *.
I'm not sure what you're trying to say by "independent types": v, o, are distinct parameters to Vehicles. The constraints are telling us we can't freely choose just any types for a, b, v, o, so they're all inter-dependent.

Question 2:
Is the instance OK? Why do I need FlexibleInstances
   instance Vehicles Boat Person Route (Water Source)

Firstly, class Vehicles needs FlexibleContexts. That's because not all of the constraints are of the form class name followed by bare type variables. Argument (v o) is the culprit.
Similarly for that instance, not all the type arguments are plain type constructors or constructors followed by bare type vars. Argument (Water Source) is the culprit. If it were (Water b), that wouldn't need FlexibleInstances.


Does every regular language have a linear grammar? Some definitions and facts (from Wikipedia):

A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.
the left-linear or left regular grammars, in which all nonterminals in right hand sides are at the left ends;
the right-linear or right regular grammars, in which all nonterminals in right hand sides are at the right ends.
Collectively, these two special types of linear grammars are known as the regular grammars; both can describe exactly the regular languages.

Doubts

Fourth fact used word "collectively" and then "both". What does it actually mean?

there is both right linear and left linear grammar for all regular languages
there is either right linear or left linear grammar for all regular languages

Can all non-linear regular grammars be converted into linear regular grammars? (Is there any systematic procedure for that?)

Update

I got it now how we can translate RLG to LLG and vice versa. So any given regular language has both RLG and LLG. Now the second question is remaining: Can all non-linear regular grammars be converted into linear regular grammars?

Answer to the last question of the update.

The grammar $S \to aSb + 1$ is linear, but it generates the nonregular language $\{a^nb^n \mid n \geqslant 0\}$. Therefore, it cannot be converted into a regular linear grammar.


Solving $$f(x, k) = f(x, k-1) + f(x-1, k-1) + \dots + f(1, k-1)$$ in terms of $x$ I'm having trouble determining the complexity of an algorithm.
Let's say the number of operations of my algorithm is described by
$$f(x, k) = f(x, k-1) + f(x-1, k-1) + f(x-2, k-1) + \dots + f(1, k-1)$$
where $f(x, 1) = x$

How can I describe the growth of $f(x)$ in terms of

$x$
$k$
$x$ when $k=x-1$

For 1), I believe $f(x, k)$ would be exponential in $x$ as $k$ can be taken to be a constant which would reduce the above equation to being similar to

$$f(x) = f(x-1) + f(x-2) + \dots + f(1) $$

Similarly, for 2), I believe $f(x, k)$ would be exponential in $k$ as I would need to take $x$ as a constant which would lead to the below equation

$$f(k) = xf(k-1) $$

Need help with 3) and also validating my thinking for 1) and 2)

The answers to all three questions become easier once we proved the following formula for all positive integer $k$ and $x$.
$$ f(x,k) = \frac{x(x+1)(x+2)\cdots(x+k-1)}{k!}$$
Proof: The formula is easily seen to be true for $k=1$ and all positive integer $x$.

Assume the formula is true for some positive integer $k$ and all positive integer $x$.
Then,
$$\begin{align}
 &f(x, k+1)\\
&=f(x, k) + f(x-1, k) + f(x-2, k) + \dots + f(1, k)\\
&=\frac1{k!}(x(x+1)(x+2)\cdots(x+k-1) + (x-1)x(x+1)(x+2)\cdots(x+k-2)\\
&\quad\quad+\cdots+1\cdot2\cdots k\\
&=\frac1{k!}\left(\frac{x(x+1)(x+2)\cdots(x+k)-(x-1)x(x+1)\cdots(x+k-1)}{k+1}\right.\\
&\quad\quad+\frac{(x-1)x(x+1)\cdots(x+k-1)-(x-2)(x-1)x\cdots(x+k-2)}{k+1}\\
&\quad\quad+\cdots\\
&\quad\quad+\frac{2\cdot3\cdots(k+1)-1\cdot2\cdots k}{k+1}\\
&\quad\quad+\left.\frac{1\cdot2\cdots k}{k+1}\right)\\
&=\frac1{k!}\frac{x(x+1)(x+2)\cdots(x+k)}{k+1}\\
&=\frac{x(x+1)(x+2)\cdots(x+(k+1)-1)}{(k+1)!}\end{align}$$

By mathematical induction on $k$, the formula is true for all positive integer $k$ and $x$.

Here are the answers to your three cases.

1) For fixed $k$ and $x\to\infty$,
$$f(x,k)=\frac{x^k}{k!}\frac xx\frac{x+1}x\cdots\frac{x+k-1}{x}\sim\frac{x^k}{k!}$$
That is, $f(x,k)=\Omega(x^k)$.

2) For fixed $x$ and $k\to\infty$, by Stirling's approximation,
$$\begin{align}f(x,k)&=\frac{(x-1+k)!}{(x-1)!k!}\\
&\sim\frac1{(x-1)!}\frac{\sqrt{2\pi(x-1+k)}\left(\frac{x-1+k}{e}\right)^{x-1+k}}{\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}}\\
&=\frac1{(x-1)!}\sqrt\frac{x-1+k}k
(x-1+k)^{x-1}\left(\frac{x-1+k}{k}\right)^k\frac{1}{e^{x-1}}\\
&=\frac1{(x-1)!}\sqrt\frac{x-1+k}k\left(\frac{x-1+k}{k}\right)^{x-1}k^{x-1}\left(1+\frac{1}{\frac k{x-1}}\right)^{\frac k{x-1}(x-1)}\frac{1}{e^{x-1}}\\
&\sim\frac1{(x-1)!}k^{x-1}e^{x-1}\frac{1}{e^{x-1}}\\
&=\frac{k^{x-1}}{(x-1)!}\end{align}$$
That is, $f(x,k)=\Omega(k^{x-1})$

3) Let $k=x-1$ go to infinity, again by Stirling's approximation,
$$f(x,k) = \frac{(2k)!}{k!k!}\sim \frac{\sqrt{2\pi2k}\left(\frac{2k}{e}\right)^{2k}}{\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}}=\frac{2^{2k}}{\sqrt{\pi k}}$$
That is, $f(k+1,k)=\Omega(k^{-1/2}2^{2k})$.


Are there lossless data compression techniques that do not exploit repetitive patterns? Lossless Data compression (source coding) algorithms heavily rely on repetitive  pattern (redundancy).

Is there a Lossless Data compression method/algorithm that is independent of repetitive  pattern (redundancy)?

Note:

Most lossless compression programs do two things in sequence: the first step generates a statistical model for the input data, and the second step uses this model to map input data to bit sequences in such a way that "probable" (e.g. frequently encountered) data will produce shorter output than "improbable" data.

Techniques  take advantage of the specific characteristics of images such as the common phenomenon of contiguous 2-D areas of similar tones. Every pixel but the first is replaced by the difference to its left neighbor. This leads to small values having a much higher probability than large values. This is often also applied to sound files, and can compress files that contain mostly low frequencies and low volumes. For images, this step can be repeated by taking the difference to the top pixel, and then in videos, the difference to the pixel in the next frame can be taken.

A hierarchical version of this technique takes neighboring pairs of data points, stores their difference and sum, and on a higher level with lower resolution continues with the sums. This is called discrete wavelet transform.

Modeling data compression as a combination of statistical modeling and encoding seems a bit obsolete these days. In many compression algorithms, the most important step is combinatorial modeling, which finds structure in the data and uses the structure to transform the data into something that can be compressed with statistical methods. For example:

Burrows-Wheeler transform permutes the characters based on the lexicographic ordering of the suffixes starting after them.
Algorithms in the Lempel-Ziv family describe the text in terms of exact and/or inexact repeats.
A graph can be described in terms of bicliques (subgraphs with an edge from every node in vertex set $A$ to every node in vertex set $B$).
A text can be represented by a context-free grammar.
A collection of similar strings can be described by the edit operations required to transform a reference string into each of the individual strings.
The collection can also be described by a finite automaton recognizing a more general language, plus the paths used to produce each of the strings.
A suffix array has self-repetitions, where each pointer in the source substring is incremented by 1 in the target substring.
A (multi)set of integers can be represented as a binary sequence.

In principle, one can describe these combinatorial models in statistical terms, but the statistical viewpoint may not be very useful. Furthermore, many practical algorithms skip the statistical modeling/encoding part completely or do them in a naive way, as decompression speed may be more important than maximal compression.

All of these methods take advantage of the redundancy in the data or make it more explicit for the subsequent compression steps. After all, data compression is basically just getting rid of the redundancy in the data.


ground terms in logic and $\lambda$-calculus? What are the differences of ground terms in first-order logic and higher-order logic?

I found on the Wikipedia: "In mathematical logic, a ground term of a formal system is a term that does not contain any free variables."

That mentioned "free variable" is the same thing with free variables of $\lambda$-terms?

I know the closed terms and open terms $\lambda$-calculus. How can we connect closed terms of $\lambda$-calculus with ground terms of logic?

I am bit confused between these concepts, could anyone explain?

I think you're basically correct. "Ground term" is more or less the same as "closed term".  Certainly the definition you gave is the same as closed term.  Personally, I don't think I've seen "ground term" used much for first-order logic or any system with binders.  The place where I most commonly see "ground term" used is universal algebra where there are no binders and so "ground term" means a term with no variables at all.

To be pedantic, the notion of "free variable" is used defined when defining the syntax of whatever formal system you're using.  As such, the notion is tied to the system being defined.  Conceptually, though, the it's the same idea.  In the last decade or so, there's been a lot of research in the CS community in capturing and manipulating binders in a languange-agnostic manner so that tools, libraries, and languages can be defined that allow easy definition and manipulation of languages with binders.  For example, the languange Beluga and the various "nominal" systems.


Find hamming codewords in r=2^k dimensions There is the original problem, and an equivalent problem.

The equivalent problem: construct a set $A$ that contains bit arrays of length $r-1$, where $|A|=2^{r-1}/r$ and $hamming \space distance (i, j) = 3 \quad \forall i, j \in A, \space i \neq j$.

Misha Lavrov gave an excellent answer on Math.SE that solves the original problem. However, I don't get his construction.

If you could prove that his algorithm solves the problem for any $r=2^k$, or provide your own algorithm that solves the problem / equivalent problem for any $r=2^k$, I'd really appreciate it.

The original problem: choose $2^r/r$ bit arrays, where each bit array is of length $r$, and $r=2^k$ for all $k \ge 2$, such that the chosen arrays can be split into 2 sets, $A$ and $B$, where

$|A|=|B|=2^{r-1}/r$
$\forall x \in A.(\exists y \in B.(hamming \space distance (x, y) = 1))$
and $\forall y \in B.(\exists x \in A.(hamming \space distance (x, y) = 1))$
$hamming \space distance (i, j) = 3 \quad \forall i, j \in A, \space i \neq j$
$hamming \space distance (i, j) = 3 \quad \forall i, j \in B, \space i \neq j$

Here is the answer for $k = 2$, where blue circles are chosen bit arrays.

(P.S. Instead of $n=2^r$ dimensions in my question on Math.SE, I used $r=2^k$ here, because Misha's answer referred to bit arrays of length $r$. I hope this is not too confusing.)

I completely misunderstood Misha's answer. Here is my updated understanding of the equivalent problem. All quotes are from his answer.

Let $S = \{0,1\}^{r-1}$, $|S| = 2^{r-1}$ bit arrays, each bit array has length $r-1$.
Let $S_i = \{x\ |\ x \in S\ and\ x_i = 1\}$, where $x_i$ is the $i^{th}$ bit of bit array $x$. We set the $i^{th}$ bit of array $x$ to $1$.

An even number of bit arrays is always chosen from $S_i$. If initially an odd number of bit arrays is chosen, then choose the bit array corresponding to the parity bit as well, so finally an even number of bit arrays are chosen.

This corroborates with Misha's answer, as the coordinates numbered off exactly match the parity bit coverage.

  Among the coordinates numbered $0\dots001, 0\dots011, 0\dots101, 0\dots111, \dots, 1\dots111$, an even number are $1$'s.
  Among the coordinates numbered $0\dots010, 0\dots011, 0\dots110, 0\dots111, \dots, 1\dots111$, an even number are $1$'s.

Repeat step 2 for all $i \in [1,\ r-1]$.

Let $A$ be the set of chosen bit arrays from $S_i$ for all $i$, where chosen bit arrays are hamming codewords.

The hamming code is an even parity bit, single error correction code for arrays of length $r - 1$.

The following describes single error correction, where "vertex" means "bit arrays", and "picked vertices" means "bit array in $A$" or "hamming codeword".

  If a vertex is not one of the picked vertices, find all the parity conditions that fail, let $i$ be the coordinate with a $1$ in all the bits corresponding to the failed conditions; change the $i^{\text{th}}$ coordinate, and you will get a picked vertex.

This solves the equivalent problem of finding set $A$.

Now, to solve the original problem.

(I originally thought the $00\dots00^{\text{th}}$ coordinate was for double error detection, and was wondering why I needed that in a single error correction code. I was completely wrong.)

  Given a vertex, if it is one of the picked vertices, change the $00\dots00^{\text{th}}$ coordinate, and you will get another picked vertex.

This is equivalent to prepending a new bit, $b$, for each bit array within the set $A$ that we derived earlier, thus making all bit arrays have length $r$.

Arbitrarily let bit $b = 0$. Define $A_{new} = \{b\ x_1\dots x_{r-1}\ |\ x \in A\}$.

Let $B = \{\neg b\ x_1\dots x_{r-1}\ |\ x \in A\}$, so all bit arrays are same as $A_{new}$, except for every array, the $b$ bit is flipped.

This fits well with Misha's explanation that bit arrays from $A_{new}$ and $B$ are nearly-identical, because the only difference is the flipped bit $b$.

  the $00\dots00^{\text{th}}$ coordinate of a vertex [...] is the "free" coordinate where we pick a vertex with $0$ and also pick a nearly-identical vertex with $1$.

This solves the original problem, such that the $2^r/r$ bit arrays are in sets $A_{new}$ and $B$.


Minimizing Trimmed Distances I'm trying to understand what is the minimum of the following function,

$$
f(\mu) = \frac{1}{n}\sum_{i=1}^n F\left(\frac{\pi(i)}{n}\right) (x_i - \mu )^2
$$

where $F$ is a step function that assign $1$ to any $t \in [0, \gamma]$ and $0$ in $(\gamma, 1]$, $\pi$ is a permutation that sorts the $i$s based on the ascending ordering of the losses $( x_i - \mu )^2$ and  $\mu$ and $x_1,\ldots,x_n$ are real numbers. I was thinking that perhaps the minumum of $f$ is achieved by the trimmed mean, namely: sort the $x_i$s discard the first $(1-\gamma)/2$ and the last $(1-\gamma)/2$ of the $x_i$ and compute the arithmetic mean of the remaing points. However, it isn't as a simple numeric example shows.

Any ideas or maybe suggestions (perhaps it is a known problem)? Many thanks in advance.

Your loss function is proportional to the $\gamma n$ smallest square differences with respect to $\mu$.

This is minimized by sorting your $x_i$ and choosing the mean of the contiguous substring $x_k, x_{k+1}, \dots, x_{k+\gamma n-1}$with the smallest variance.


Missing part of the proof of Master Theorem's case 2 (with ceilings and floors) in CLRS? I am trying to go through the proof of the Master Theorem in Introduction to Algorithms of Cormen, Leiserson, Rivest, Stein (CLRS). The theorem providers an asymptotic analysis for recurrence relations $T(n)=aT(n/b)+f(n)$ where $a\geq 1, b > 1$  and $f(n)$ is an asymptotically positive function.

The authors create a formulation of the following lemma (4.3):

  if $f(n) = \Theta(n^{\log_ba})$, then $g(n)=\Theta(n^{\log_ba}{\log_bn})$

where $g(n) = \sum_{j=0}^{\lfloor \log_b n \rfloor - 1} a^jf(n_j)$ and $n_j = \begin{cases}
n,  & \text{if j = 0} \\
\lceil n_{j-1}/b \rceil, & \text{if j > 0}
\end{cases}$

When it is proving for the situation in which floors and ceilings appear the autrors make a statement:

  For case 2, we have $f(n)=\Theta(n^{\log_b a})$. If we can show that
  $f(n_j) = O(n^{\log_ba}/a^j) = O((n/b^j)^{\log_ba})$, then the proof for
  case 2 of Lemma 4.3 will go through.

Well, I got it. When this condition is true we can find some constant $c$, such that

$g(n) \le c\sum_{j=0}^{\lfloor \log_b n \rfloor - 1} n^{\log_b a}$

and conclude that $g(n) = O(n^{\log_b a}{\log_bn})$.

But it's not a proof that $g(n) = \Omega(n^{\log_b a}{\log_bn})$. Where is one? Should it be obvious? How can I prove this statement?

As you said, the book does not include a proof for $g(n) = \Omega(n^{\log_b a}{\log_bn})$. There is no need to.

Recall that part of proof is to show the upper bound of $f(n)$, when $f(n)$ is defined by the following recurrence relation using the ceiling function, which is the formula 4.25 in CLRS.
$$T(n) = aT(\lceil\frac nb\rceil) + f(n)$$
Noting that the lower bound for $T(n)$ "is routine, since we can push through the bound $\lceil\frac nb\rceil\ge\frac nb$", the book proceed to prove an upper bound for the above $T(n)$, where we only need to show an upper bound for $g(n)$.

What you meant might be the corresponding situation in the case when $f(n)$ is defined using the floor function as the formula 4.26 in CLRS,
$$T(n) = aT(\lfloor\frac nb\rfloor) + f(n)$$
in which case, we will defined $h(n) = \sum_{j=0}^{\lfloor \log_b n \rfloor-1} a^jf(n_j)$ and $n_j = \begin{cases}
n,  & \text{if j = 0} \\
\lfloor n_{j-1}/b \rfloor, & \text{if j > 0}
\end{cases}$.

Note that the definition of $h(n)$ is not the same as that of $g(n)$, although the two are almost the same.

I will leave as an exercise for you to prove a lower bound for the above $T(n)$ using $h(n)$. In particular, you will need to show that in case 2, i.e., when $f(n)=\Theta(n^{\log_b a})$,
$$h(n) = \Omega(n^{\log_b a}{\log_bn}).$$

Hint, as said in the last statement of section 4.6.2 and by Yuval's comment, the proof of the lower bounds is similar.


Loop Invariant Code Motion - am I missing something? I've been implementing LICM for a project, and came upon a strange observation.

Let's say we have a loop

int i = 10;
while (i > 0) {
    a = 2;
    i--;
}

One can easily see that a = 2 is invariant. What we do next is check (for each invariant candidate) if the containing basic block dominates all uses of the said variable and all exits of the loop.

The former is clearly true, as a is only used once. The latter is what I don't seem to get. The CFG of the example above is

By looking at the graph we can clearly see that the cycle body (which is just a single basic block in this case) does not dominate all exits!

After thinking about this for some time, I got to the following conclusion:

In a general case, we can not know for sure if the body of a loop is going to be executed at least once. This implies that one can not simply move invariant instructions out of the loop, as they will then be executed dependless of the actual value of the loop termination condition.

I have not seen this adressed in any of the material covering LICM, as well as in the wikipedia article. In fact, their example, in which they transform

for (int i = 0; i < n; ++i) {
    x = y + z;
    a[i] = 6 * i + x * x;
}

into

x = y + z;
t1 = x * x;
for (int i = 0; i < n; ++i) {
    a[i] = 6 * i + t1;
}

seems incorrect, as the loop condition generally could have been false on the first iteration, and so x = y + z should not have been executed at all.

My proposed solution

All code deemed invariant should be put in an if (expr), where expr is the loop condition. For my original example, that would give us

int i = 10;
if (i > 0) {
   a = 2;
}
while (i > 0) {
    i--;
}

You can also replace with

if (loop_condition) {
    loop_invariant_code
    do {
        loop_body
    } while (loop_condition)
}

With all he precautions of course. That makes the loop a bit simpler, and saves one test of the condition. And because you have no extra evaluations of loop_condition, this should be correct even if loop_condition has side effects.

And in the first example starting with i = 10 you should be able to optimise the first loop condition away.

But absolutely, you cannot just move code with side effects out of a loop, and you should be careful moving code without side effects, in case the loop is not executed and the moved code just wastes time. This more critical in languages that do overflow checks, so adding a+b can actually have a side effect on overflow.

Note: The wikipedia article also mentions strength reduction (for example, instead of calculating i*6, set tmp = 0 before the loop starts, and increase tmp by six at each iteration). Setting tmp = 0 would also only be executed if the loop condition is tested once.


A simple way to find the feasible region of a system with simple constraints I'm coding something... weird, and I'm running into some constraint satisfaction and graph theory problems, which are fields I'm not too experienced in.  Here's the problem:

I start out with this directed acyclic graph:

The values describe the range that the edge lengths are allowed to be.  So the edge B->E can't be shorter than 9, but can be any size larger, while the edge B->C has to be between 0 and 1 (inclusive).

Also, it's constrained as if they were flattened onto a number line: for example, the distance from A->B->C is equal to the distance from A->C.  And BE=BC+CD+DE, DF=DE+EF, AF=AB+BE+EF=AC+CD+CF, and so on.  It's important to note that the ordering matters: D must come before E and F. Here's a visualization of that.  Think of the gray lines as extendable/retractable bars:

My goal is to create an algorithm that narrows down the values to the most constrained possible range that is legal.  For example, D->F has range (2,∞), but it can't be shorter than 3, since the smallest D->E->F can be is 3.  So I would want to raise the minimum value of D->F's range to (3,∞). Note that real numbers are allowed. The end result would look like this:

The challenge is that I need performant method that runs ideally in roughly linear time.  In practice, the graphs will be enormous and I will need to run this algorithm hundreds of thousands of times.

Originally, I was just dealing with minimum values, and had a version that was simple and worked well.  It just added the previous min values up, did the same in reverse, and found the difference:

- put the root A in queue Q
- while Q is not empty:
    - node N = Q.dequeue
    - if N has no previous edges:
        - N.prev_range = (0,0)
    - else:
        - N.prev_range = (0,∞)
        - for each edge PN in N.previous_edges:
            - N.prev_range.min = max(N.prev_range.min, P.prev_range.min + PN.min)
            - N.prev_range.max = min(N.prev_range.max, P.prev_range.max + PN.max)

- now do the exact same thing in reverse:
    - start at F and move down, storing values in N.next_range instead

- total_length = 15 (AF, in this example.  We can treat AF as a special edge in my case,
as I think my data will always have such an edge, although ideally the best solution
would not need to designate a particular edge for this)

- then, for each edge XY:
    - XY.min = max(XY.min, total_length - X.prev_range.max - Y.next_range.max)
    - XY.max = min(XY.max, total_length - X.prev_range.min - Y.next_range.min)

This algorithm just traversed the graph twice, and only looked at neighbors, so it ran fine on increasingly large graphs.  However, once I started adding constraints with maximum values, like the B->C and D->E in this example having a max value of 1, I started getting a problem where edge B->E is essentially locking C->D into having a min size of 7 (through BC and DE), and that locking relationship isn't captured by the process I implemented, so it's not constraining it to 6.

Is it even theoretically possible to find the real sizes without having to search local edges for these kinds of relationships?  I've been thinking about some physical analogs (ropes and knots, or sliding tubes) but they haven't helped. Does anyone have any ideas, or what kinds of things I should researching?  Or if such a solution isn't possible, if there's a simple and relatively performant non-linear solution?

Thanks!

This can be formulated as a linear programming (LP) problem. Arbitrarily state that $A$ is at coordinate 0, then for your example graph we get equations

$$ A = 0$$
$$ B-A \ge 1 $$
$$ C-A \ge 1 $$
$$ 1 \ge C-B \ge 0 $$
$$ \dots $$
$$ F - E \ge 3 $$
$$ F - A = 15 $$

In particular, with $V$ nodes and $E$ edges, we have $V-1$ variables and at most $2E$ linear constraints. Linear programs can be solved in polynomial time (via e.g. the ellipsoid method), but it's not necessarily linear -- more like quadratic or cubic. However! You have a very sparse system: each constraint has only two nonzero entries. This means it will likely perform very well in practice. If you use a free (and usually very well optimized) library, like Gurobi or GLPK, they can use the Simplex method and pretty efficiently use the sparsity.

I realize this might not be completely satisfactory, but: LP solvers are pretty intelligent, and I'm not convinced there's a whole lot more structure to your problem that you could take advantage of that they won't. They will probably do something sort of like your take-min-first strategy, and then "fix" appropriately, and efficiently.

Finally, quick note: You didn't really specify what your goal is, but the solver will want some function to minimize. I would have suggested just saying "minimize $F$", but in your example graph $F$ is actually fixed. So a reasonable objective function might be "minimize $B+C+D+E+F$" or something. Depends on your application. But this should get you basically linear runtime on nearly all cases.


Decomposition of a directed graph into Hamiltonian paths I was wondering if anyone knew of an algorithm that when given a directed graph will split it up into separate Hamiltonian paths. I don't really mind about nodes that can't be added to a path but as few paths as possible should be made to include the most nodes.

Any ideas would be greatly appreciated.

Finding an Hamilton path in directed (and un-directed) graphs, is an $NP$ complete problem.
Thus, there is probably no efficient algorithm (polynomial) to split a given graph to several hamiltonian paths.


How to show that Language is not Context Free? There is a question to show that $L=\{a^{n!} \mid n \geq 0 \}$ is not regular using Pumping Lemma. However, I have the answer in the book which is found to be somewhere wrong. I am sharing the snapshot of the answer which I could not figure out. Could anybody correct it so that the puzzle could be solved?

There is a pumping lemma for context free languages too.

In you case, if $L$ was context free, then there would be some constant $n_0$ such that all words $a^{n!}$ with $n! \ge n_0$, $a^{n!}$ could be decomposed as:
$$
a^{n!} = a^x a^y  a^v a^w a^z
$$
such that $y+v+w \le n_0$, $y+v \ge 1$, and for all $i \ge 0$:
$$
a^x a^{yi}  a^v a^{wi} a^z \in L.
$$

Calling $\ell = y+w$ and simplifying, the above can be rewritten as:
$
a^{n!} = a^\ell a^{n! - \ell}
$
such that, for all $i \ge 0$, $a^{n!+(i-1)\ell} \in L$.

This cannot be true. To see this pick, e.g., $n=n_0+2$, and $i=0$.
Then $a^{n!+(i-1)\ell} = a^{(n_0+2)!-\ell}$, where
$
(n_0+2)! - \ell \le (n_0+2)! - 1 < (n_0+2)!
$
and
$
(n_0+2)! - \ell \ge (n_0+2)! - n_0 = (n_0+1) \cdot (n_0+1)! - n_0 > (n_0+1)!
$, showing that $n!-\ell \in ((n_0+1)!, (n_0+2)!)$ and hence it cannot be expressed as a factorial.


Determine missing number in data stream We receive a stream of $n-1$ pairwise different numbers from the set $\left\{1,\dots,n\right\}$.

How can I determine the missing number with an algorithm that reads the stream once and uses a memory of only $O(\log_2 n)$ bits?

From the comment above:

Before processing the stream, allocate $\lceil \log_2 n \rceil$ bits, in which you write $x:= \bigoplus_{i=1}^n \mathrm{bin}(i)$ ($\mathrm{bin}(i)$ is the binary representation of $i$ and $\oplus$ is pointwise exclusive-or). Naively, this takes $\mathcal{O}(n)$ time.

Upon processing the stream, whenever one reads a number $j$, compute $x := x \oplus \mathrm{bin}(j)$. Let $k$ be the single number from $\{ 1, ... n\}$ that is not included in the stream. After having read the whole stream, we have
$$ x = \left(\bigoplus_{i=1}^n \mathrm{bin}(i)\right) \oplus \left(\bigoplus_{i \neq k } \mathrm{bin}(i)\right)
= \mathrm{bin}(k) \oplus \bigoplus_{i \neq k } (\mathrm{bin}(i) \oplus \mathrm{bin}(i)) = \mathrm{bin}(k), $$
yielding the desired result.

Hence, we used $\mathcal{O}(\log n)$ space, and have an overall runtime of $\mathcal{O}(n)$.