What's really meant by context-free in the term context-free grammar? I have been studying compilers for a while, and I have been searching what's meant by "context" in grammar and what it means for grammar to be "context-free", but with no result.

So can anyone help with this ?

The context can be explained with regards to the production rules allowed for different grammars in Chomsky hierarchy.

If you consider context-free grammars, their production rules have the following form:

$$ A \rightarrow \alpha$$

So, you can observe that the left part of this kind of rules is made up of only one non-terminal symbol; thus, the substitution of the non-terminal symbol takes place without considering its "context", that is the other symbols it is surrounded by.

On the other hand, if you consider production rules of context-sensitive grammars, they have the following form:

$$ \beta A \gamma \rightarrow \beta \alpha \gamma$$

where $A$ is a non-terminal and $\alpha$, $\beta$, $\gamma$ are sequences of non-terminals and terminals.

In this case the "context" (i.e., $\beta$ and $\gamma$) of the non-terminal symbol to be substituted influences the effect of the substitution and it is part of the rule itself.

You can find more details in this answer on mathematics and in this answer on software engineering.


Lower bound on the number of comparisons needed for finding the two largest elements Given a sequence of ݊different elements, there is an algorithm that finds the maximum element, and the 2nd largest element, using n +log_2(n) - 2 comparisons. Prove that any algorithm will have to perform at least n +log_2(n) - 2 comparisons in order to find both elements.

What I've done: I tried to compare it to a tennis tournament(sort of a binary tree that compare pairs of competitors in which each game has a winner and a loser - each winner goes up to the next level in the tree). It takes n-1 comparisons and every element is involved in a comparison log n times at most.

The biggest element will be the winner in the tournament. the second biggest element will have to face the winner so he's one of the log n elements the the winner competed against which means logn -1 comparisons. If I sum it all I get what I need to prove.

I got this note from the teacher: the proof is not correct because you assume the algorithm uses a tournament you have to prove any algorithm has an input for which the second largest element is in a group of size logn.

Can someone tell me how the proof should have looked like? I'm really struggling with it. Please be detailed as possible

With impossibility proofs, you don’t control the algorithm; you control
the input. For this particular impossibility proof, the input is the
outcome of the comparisons that the algorithm performs. Here’s one
possible adversary strategy.

This adversary never claims that elements in distinct positions are
equal. At each point in the algorithm’s execution, there are two classes
of elements: candidates, which are the elements that have not compared
less than another element; and non-candidates, which are the remaining
elements. Candidates always compare greater than non-candidates.
Non-candidates compare in an arbitrary consistent way. Comparisons
between candidates can be resolved arbitrarily (prove this); the
adversary declares the candidate involved in more previous comparisons
of this sort (“knockout” comparisons) to be greater.

At the end of the execution, there can be only one candidate; otherwise,
the algorithm can’t know which of the candidates is the maximum (prove
this). The only way to reduce the number of candidates is a knockout comparison, which reduces the number of candidates by one. This implies that there are
n - 1 knockout comparisons, forming a tournament tree of some
shape. We observe that, for each node of the tree, when an element
secures its place there, it has participated in a number of knockout
comparisons equal to the height of that node. The root has height at
least lg n, so it takes lg n - 1 comparisons to determine which of the
lg n elements compared less than the maximum only (otherwise, the second
maximum isn’t known). None of these comparisons are knockouts, so the total is at least n + lg n - 2.


NFA for binary words that do not end in 10 Construct an NFA over $\{0, 1\}$ whose language contains only words that do not end with $10$.

This is one of the first problems in the book, so it's supposedly easy. I just can't figure it out. It's easy using a DFA, but I'm not so sure using an NFA. Maybe I'm not understanding a particular concept in the NFA.

Every DFA is also, in particular, an NFA. Therefore if you have constructed a DFA for some language, then you have a fortiori constructed an NFA for it.


How to show potential pipeline hazards Based on following table, I have to show if there is any potential pipeline hazard in the following code segments:

X = R2 + Y
R4 = R2 + X
R1 = R2 + X
X = R3 + Y
Z = R1 + X

I've been a bit stuck in the problem involving instruction pipelining.

Any strategy about where to start according to the table?

A data hazard occurs whenever you access a register after updating it. Due to the pipeline structure updating the register happens after it is being accessed by the successive instruction. That is, when accessed, the register holds the old value rather than the updated value.

For instance:

1. R2 = R1 + 1    // update R2
2. R3 = R2 + X    // access R2

Instruction 1 updates R2 at S4 (see the table). Instruction 2 reads R2 at S2. But at this time the new value of R2 is not stored yet -- it will be stored only on the next clock. This problem is the hazard.


Are there any known implementations of a functional Heap's Algorithm? TL;DR: Is an implementation of the Heap's Algorithm adhering to the principals of functional programming possible, and are any implementations of it known? And by "adhering to the principals of functional programming", I mean mainly not relying on the mutation of an object to carry out the algorithm.

I decided to write a function that generates permutations of a list

(permutations [1 2 3])
=> [[1 2 3] [2 1 3] [3 1 2] [1 3 2] [2 3 1] [3 2 1]]

And after some quick searching, somewhat arbitrarily picked Heap's Algorithm.

The problem is, I'm writing in Clojure, trying to adhere to proper FP principals as close as possible, and the entire algorithm seems to hinge on mutating a "global" array while recursing. I worked on this for a couple of hours, and could not find a way of sanely getting the results passed "back up the stack", since the recursive calls just kind of float between mutations:

(defn- swap-v [v i1 i2]
  (let [x (get v i1)]
    (-> v
        (assoc i1 (get v i2))
        (assoc i2 x))))

(defn permutate [coll]
  (let [coll-atom (atom coll)
        result-atom (atom [coll])]
    ((fn rec [n]
       (when (> n 1)
         (let [n-even? (zero? (rem n 2))
               swap-pos #(if n-even? % 0)]

           (doseq [i (range (dec n))]
             ; Recursive call
             (rec (dec n))

             ; Mutate the "array" by swapping two elements
             (swap! coll-atom swap-v (swap-pos i) (dec n))

             ; Then mutate the results array so they can be returned later
             (swap! result-atom conj @coll-atom)) ; Mutate the

           ; ... And another recursive call down here
           (rec (dec n))))

      (count @coll-atom)))

    @result-atom)) ; Dereference the atom and return the results

I tried changing the doseq to a reduction, then I had the results returned nicely, but seemingly nothing to do with them.

I ended up giving up on a FP approach, wrote the above code, and tried to find an example of an FP approach to the algorithm to see where I had gone wrong. To my surprise, I wasn't able to find any. The closest I could find was a Haskell implementation, but honestly, I have no clue what most of the code is doing; it's pretty obscure. I see unsafe in a few places though, so I think they snuck some mutation in there.

Is this possible?

Note, I'm not looking for a review of the code here, since I'm aware this is very imperative-styled, and I already has a review request open.

I'm really not very familiar with clojure. I think this is probably the longest clojure program I've written so far. But I guess it provides some sort of answer.

On the whole, functional enumerations of permutations are going to suffer from the O(n) cost of creating a new permutation vector on each iteration. Pretty well all of the common imperative solutions make some attempt to avoid this cost, and many of them can produce amortised O(1) complexity (for a single permutation). Heap's algorithm is interesting in an imperative environment largely because it guarantees to perform a single swap on each iteration, which is clearly a minimal total number of mutations. That's particularly useful if the goal is to perform some sort of aggregate computation over the permutation which can be incrementally computed from the previous value and the modifications.

Heap's algorithm is not the only algorithm which performs just a single swap to produce the next permutation. The possibly even more famous bell-ringers' algorithm (often called the Steiner-Johnson-Trotter algorithm) produces sequences in which consecutive permutations differ only by a swap of two adjacent elements. This could be even more valuable for updating of aggregate computations, but it is more complicated to figure out which two adjacent elements to swap at each iteration. (Indeed, although tables of plain changes for up to seven bells were produced several centuries ago, the precise algorithm used to produce these table has not, as far as I know been recorded. However, the results line up with the algorithm proposed independently in the 1960s by the three mathematicians after whom it is named.)

The plain changes algorithm was motivated in part by the desire to keep the various bell ringers' attention on the changes; if a bell stays in the same position in the change for too long, its ringer may become bored and lose their place in the sequence. (In fact, current change ringing sequences try even harder to avoid leaving a bell in the same position for too long, so they no longer use the STJ algorithm.)

For many combinatorial problems, though, the opposite criterion is desired. For example, it may be useful to generate the permutations in lexicographic order, which means that the first item retains its value for (n-1)! iterations. Lexicographic ordering can still be performed in amortised O(1), and it involves O(1) mutations at each iteration, but the number of mutations may be as great as n-1 (or n, if the permutation sequence is circular, since the last permutation in lexicographical order is the reverse of the first one).

If the vector to be permuted may have repeated elements, and only unique permutations are desired, then lexicographic order is far and away the easiest solution. Furthermore, it is very easy to describe the next-permutation algorithm for lexicographic ordering:

Start with the vector sorted from left to right.
At each iteration:

Find the shortest suffix which is not monotonically non-increasing. (In other words, find the last element for which some subsequent element is greater.) If the entire vector is monotonically non-increasing, then it is the last permutation and the process is done.
Sort that suffix by shifting its first element to the right, and then reverse it. (This can be done by a modified reversal algorithm with k/2 swaps where k is the length of the suffix, but doing it in two steps is conceptually simpler.)

I think that algorithm would be quite simple to implement in functional style.

But let's get back to Heap's algorithm. Heap developed his algorithm in 1963, about the same time as Trotter and Johnson independently published the change ringing algorithm. (Steinhaus had published his version of the algorithm in 1958, but since he was writing in Polish it was relatively unknown until it was translated into English in 1963.) Heap's paper was a simple description of his algorithm, without formal proof, and it probably would have remained in the dusty archives of computer science had it not been rediscovered by Robert Sedgewick a decade later. In 1977, Sedgewick wrote a long survey on permutation algorithms, in which he devoted quite a bit of attention to Heap's algorithm, including producing an optimised implementation in a kind of virtual machine code. He concluded that for typical hardware architectures (in 1977), "Heap's method will run faster than any other known method."

A couple of years later, he presented a public lecture on permutation algorithms, during which he repeated this claim, and Heap's algorithm became the permutation algorithm of choice for programmers with a performance fetish. Unfortunately, the presentation slides (which are rather more easily found online than any of the other sources for Heap's algorithm) had a minor error in the algorithm pseudocode (not present in the 1977 paper, which presents a number of variant implementations, all impeccable). And because the presentation slides are rather more accessible than any of the academic references, that particular error has plagued implementations of Heap's algorithm ever since. Ironically, the error causes the algorithm to both run more slowly and to generate an incorrect sequence in which consecutive permutations sometimes do not differ by a single swap.

I have a certain affinity to Heap's algorithm because a few years ago, a question appeared on StackOverflow asking for help with that algorithm; the poster had carefully implemented the algorithm based on pseudocode in Wikipedia, and discovered that their code did not work as expected. In the course of reviewing the code, I soon realised that the poster's code was an entirely accurate implementation of the Wikipedia write-up, and in the course of trying to validate Wikipedia, I tracked down the history of the error which I summarised in the preceding paragraph. A Wikipedian noticed the answer and fixed the Wikipedia page. (Constant vigilance is necessary, however; every couple of months some aspiring computer science expert compares the  pseudocode on Wikipedia either with Sedgewick's buggy slide or with one of the many buggy implementations floating about the internet, and "corrects" the Wikipedia page.)

The beauty of Heap's algorithm is the simplicity of enumerating the swaps. The algorithm is similar to a lexicographic algorithm, in reverse, in that it always does a complete permutation cycle of a prefix of the elements before changing the next element. So the higher index of the swapped elements follows a kind of factorial variant on the ruler function, in which element i appears every i! iterations (except for the iterations which are multiples of a larger factorial). The lower index follows an only slightly more complex pattern: for prefixes with an odd number of elements, the lower index is always 0; for prefixes with an even number of elements, the lower index starts at 0 and is sequentially incremented. So, for example, in the case of a four element permutation sequence, the swaps are:

0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0
1 2 1 2 1 3 1 2 1 2 1 3 1 2 1 2 1 3 1 2 1 2 1

(Note that the element with index 3 appears as the larger index every 3! == 6 iterations, and the element with index 2 appears as the larger index every 2! == 2 iterations, except the ones which have already been taken by index 3.)

This sequence of pairs of indices is very easy to produce recursively, but one really wants it as a sequence. There is a non-recursive algorithm which effectively involves maintaining an explicit stack, but since the published algorithms tend to mutate this stack, I chose to use the recursive algorithm. In many Scheme's, one would use some kind of continuation to turn the recursive algorithm into a sequence, but since clojure doesn't have continuations (as far as I could see), I did it with nested calls to mapcat, the same approach as is taken by clojure's tree-seq standard library function.

Once you have the list of pairs of indices to swap, they can be repetitively (and lazily) applied to permutations by using reductions, which generates the result of successively applying a sequence of values to a seed value, using an arbitrary binary function. You can see that in the last line, where reductions is applied to the sequence generated by swaps using the swap-v function to turn each successive permutation into the next one.

I hope that's enough narrative to explain the (possibly non-idiomatic) clojure program which I came up with:

(letfn [(even-swaps [n]
            (if (= n 2) [[0 1]]
              (drop 1 (mapcat (fn [i] (cons [(- i 1) (- n 1)]
                                            (odd-swaps (- n 1))))
                              (range n)))))
          (odd-swaps [n]
            (drop 1 (mapcat (fn [i] (cons [0 (- n 1)]
                                          (even-swaps (- n 1))))
                            (range n))))
          (swaps [n]
            (cond
              (< n 2) '()
              (even? n) (even-swaps n)
              :else (odd-swaps n)))
          (swap-v [v [i j]] (assoc v i (v j) j (v i)))]
  (defn heap [sq]
    (let [v (vec sq)]
      (reductions swap-v v (swaps (count v))))))

Sample output:

user => (run! prn (heap '(a b c d)))

[a b c d]
[b a c d]
[c a b d]
[a c b d]
[b c a d]
[c b a d]
[d b a c]
[b d a c]
[a d b c]
[d a b c]
[b a d c]
[a b d c]
[a c d b]
[c a d b]
[d a c b]
[a d c b]
[c d a b]
[d c a b]
[d c b a]
[c d b a]
[b d c a]
[d b c a]
[c b d a]
[b c d a]


Does the DFS algorithm differentiate between an ancestor and a parent while computing back edges? Below is the general code for DFS with logic for marking back edges and tree edges. My doubt is that back edges from a vertex go back and point to an ancestor and those which point to the parent are not back edges (lets assume undirected graph). In an undirected graph we have an edge back and forth between 2 vertices $x$ and $y$. So after visiting $x$ when I process $y$, $y$ has $x$ as an adjacent vertex, but as its already visited, the code will mark it as a back edge. Am I right in saying that? Should we add any extra logic to avoid this, in case my assumption is valid?

DFS(G)
    for v in vertices[G] do
         color[v] = white
         parent[v]= nil
         time = 0

    for v in vertices[G] do
        if color[v] = white then
            DFS-Visit(v)

Induce a depth-first tree on a graph starting at $v$.

DFS-Visit(v)
    color[v]=gray
    time=time + 1
    discovery[v]=time
    for a in Adj[v] do
        if color[a] = white then
            parent[a] = v
            DFS-Visit(a)<br>
            v->a is a tree edge
        elseif color[a] = grey then
            v->a is a back edge
    color[v] = black
    time = time + 1

white means unexplored, gray means frontier, black means `processed'

The algorithm you describe works on directed graphs. In such a graph, an edge $(u, v)$ does not imply an edge $(v, u)$. Your confusion arises because you are probably trying it for undirected graphs.

For undirected graphs, the algorithm has to be modified slightly. Again, the modification will depend on whether this graph is a simple undirected graph or a multigraph. I will use the same variable names used that you use in your algorithm:

Simple Graph: When checking the colour of the adjacent vertex $a$ of a vertex $v$, if the colour is grey and the vertex $a$ is not a parent of $v$, then it is a back-edge. Ignore if $a$ is the parent.
Multigraph: If the colour of $a$ is grey and it is a parent of $v$, you need to check if $a$ occurs more than once in the adjacency list of $v$. This indicates multiple edges between $a$ and $v$, and one of them can be considered as a tree edge while the rest will be back edges. If there is only one edge between the two, it is a tree edge and has already been considered, so do nothing. Loops (edge from $v$ to $v$, that is, $a$ = $v$) are always back edges.

You are basically finding a spanning tree of the graph, and so try to go by the definitions and see how the algorithm should be modified for various cases. And how a tree-edge or a back edge are informally defined for various types of graphs.


Simplifying this expression with big O when several variables are involved I have an algorithm which depends on three variables an where the running time is in $\mathcal{O}(m+2 m\cdot n\cdot p+p\cdot(n+m))$ and I would like to simplified it. I proceeded as follows :

\begin{eqnarray}
   \mathcal{O}(3m+2 m\cdot n\cdot p+p\cdot(n+m)) &=& \mathcal{O}(m\cdot(3+2n\cdot p)+p\cdot(n+m))\\
                 &=& \mathcal{O}(2m\cdot n\cdot p+n\cdot p + m\cdot p)\\                 &=& \mathcal{O}(n\cdot p \cdot(2m+1) + m\cdot p)\\
                 &=& \mathcal{O}(2n\cdot m \cdot p + m\cdot p)\\
                 &=& \mathcal{O}(m \cdot p\cdot(2n+1))\\
                 &=& \mathcal{O}(2n\cdot m \cdot p)\\
                 &=& \mathcal{O}(m\cdot n \cdot p)\\
 \end{eqnarray}

I successively replace $3+2n\cdot p$  by  $2n\cdot p$, $2m+1$ by $2m$ and $2n+1$ by $2n$ since they are asymptotically equivalent.
Is it correct?

More generally can I always replace any subexpression with an asymptotically equivalent one within the big-O expression?

All is correct, but - it can be done in one step after you represent this expression as a sum of terms:
$$\mathcal{O}(3m+2m⋅n⋅p+p⋅n+p⋅m)=\mathcal{O}(m⋅n⋅p)$$
because:

The term $(m⋅n⋅p)$ dominates all the other terms - $(3m)$, $(p⋅n)$, and $(p⋅m)$ - in this sum.
Constants are eliminated according to the $\mathcal{O}$ definition.


How is $L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $} a regular language? My understanding is that a machine with finite states cannot keep track of the n's being the same  in $L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $}, similar to the case with how $a^nb^n$ is not a regular language. For instance, if we take a string $aaaa ab bb$, where the fifth a and the following b are $s$, how is this valid? We have a disproportionate amount of a's to b's. Using the pumping lemma, I feel that this is disproven easily if $y$ (from $xyz$ division) is any number of a's at the beginning.

If this can be proven using a DFA, what is it?

You don't need to "keep track of $n$ being the same." Another way to write the language is

$$L = \{a^na^ib^jb^n\mid n\geq 1,\ i,j\geq 0\}=\{a^{n+i}b^{j+n}\mid n\geq 1,\ i,j\geq 0\}\,.$$

So, now, given a string $a^sb^t$, you just need to decide if you can choose $n\geq1$ and $i,j\geq 0$ such that $s=n+i$ and $t=n+j$.  If so, then $a^sb^t\in L$; otherwise, $a^sb^t\notin L$. If $s=0$ or $t=0$, we can't choose $n$, $i$ and $j$ as required, since $n\geq 1$. However, as long as $s>0$ and $t>0$, we can take $n=1$, $i=s-1$ and $j=t-1$. Therefore,

$$L = \{a^sb^t\mid s,t\geq 1\}\,,$$

which is the language matched by the regular expression $aa^*b^*b$.


Returning sorted lowest k elements in a binary heap Given a binary heap of size $n$ and a number $k\le n$. How can I return an array with size $k$, which contains the $k$ lowest elements in the binary heap, so that it will be sorted in the end?

The problem is that the time-complexity needs to be $\Theta(k \log(k))$.

Construct a new min-heap $H$ using the root of the original heap $O$ as its only element. Then $k$ times you want to pop the smallest value from $H$, append it to our output array and add the children that node has in $O$ to $H$.

The maximum size $H$ gets here is $k + 1$, so all the above has a complexity of $O(k \log k)$.

If you meant to keep the original heap intact, you are now done. If you also want to remove these $k$ elements from $O$, then all you need to do is use $H$ as your new heap, making any leaf of $H$ use the child pointers that respective node had in $O$.

All of the above is assuming you have a pointer-based tree structure. If you use an array as your heap data structure using indices as implicit children, I doubt it's possible at all.

On top of that, this optimization is likely not worth it unless $n$ is very large and $k$ is very small.


Finding minimal strongly connected graph I have this question:
Given a strongly connected and directed graph $G = (V,E)$ with positive weights define $E(t)$ to be the group of edges whose weight is at most $t$. Find an algorithm that calculates the minimal $t$ such that $G(t) = (V,E(t))$ is strongly connected.

I thought about running Dijkstra $v$ times from every vertex and then all of the edges will be the minimal $t$ but I am not sure the time complexity is the best. Is there a better solution for this problem?

We can solve the problem in $\mathcal{O}(E \log V)$ by binary search.

We can identify the strongly connected components in a graph in linear ($\mathcal{O}(V + E)$) time. Thus we can check if the graph is strongly connected in linear time.

If $G(t_{0}) = (V, E(t_{0}))$ is strongly connected, so is $G(t) = (V, E(t))$ for $t \geq t_{0}$. Further, if $G(t_{0})$ is strongly connected, so is $G(t)$ where $t$ is the maximum edge weight that is at most $t_{0}$. Thus we can binary search for $t$ over all edge weights.

The algorithm is:

Sort edges by weight. Let $w_{i}$ be the $i$th smallest edge weight (1-indexed). Set $w_{0} = -1$.
Initialise binary search: set $l = 1$ and $h = |E| + 1$
While $l \neq h$:

set $m = \lfloor\frac{l + h}{2}\rfloor$. Then, If $G(w_{m})$ is connected, set $h = m$. Otherwise set $l = m + 1$.

If $l = |E| + 1$, no $t$ works. Otherwise, answer $t = w_{l}$

In the binary search, we maintain the invariant that $G(w_{h})$ is strongly connected (or $h = |E| + 1$), while $G(w_{l - 1})$ is not (assuming $|V| \geq 2$). We exit the loop when $l = h$, thus either $l = |E| + 1$ and the graph is not strongly connected for any $t$, or $G(w_{l})$ is strongly connected, but $G(w_{l-1})$ is not, thus $G(t)$ is not strongly connected for $t < w_{l}$. Thus the algorithm is correct.

The first step takes $\mathcal{O}(E \log E)$ time. The third step takes linear time and is executed at most $\log E$ times. Thus, the complexity is $\mathcal{O}((V + E) \log E) = \mathcal{O}(E \log V)$.


Max number of configurations of a Turing Machine I was wondering about a result in the Sipser book which states that any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$.

Is this because a configuration consists of a state, a position of the head and the contents of the work tape, which is $\vert Q \vert \cdot f(n) \cdot \vert \Gamma \vert ^{f(n)}$. To be honest I'm not quite sure why this is equal to $2^{O(f(n))}$. Wouldn't this only be the case when your work tape alphabet consists of 2 symbols?

Probably a silly question, but thanks anyway.

Also, I did not quite understand if this result changes when we consider logspace bound Turing machines.

Yes, that's right.  If there are $k$ possible configurations, then any such Turing machine either runs in time at most $k$, or it loops forever.  That's because if it runs for at least $k+1$ time steps, some configuration must be repeated; and if a configuration is repeated, it will continue repeating forever.

Let $|\Gamma|=2^c$, i.e., $c = \lg |\Gamma|$.  Then $|\Gamma|^{f(n)} = (2^c)^{f(n)} = 2^{c f(n)} = 2^{O(f(n)}$.  For similar reasons, $\vert Q \vert \cdot f(n) \cdot \vert \Gamma \vert ^{f(n)} = 2^{O(f(n)}$.  So, the number of possible configurations of a $f(n)$-space-bounded Turing machine is $2^{O(f(n)}$, and thus any such machine must either halt in time at most $2^{O(f(n)}$ or loop forever.


How to show that two vertices in a connected component are in the same set? (bi conditional) Show that after all edges are processed by CONNECTED-COMPONENTS, two vertices are in the same connected component if and only if they are in the same set.

The CONNECTED-COMPONENTS algorithm is the following:

It seems pretty obvious that when we keep adding the vertices of the direct edges of a connected component to a set, eventually the set formed has all the vertices in the connected component - directly connected as well as indirectly connected.
But how do I formally prove that? Also it seems like a biconditional to me.
I've thought of things like loop-invariant or a proof by contradiction. But unable to exactly figure out what to do. Any help is appreciated.

Below are two approaches to your problem.

detailed semi-formal proof

Since you've provided a minimal context, I will state my assumptions then provide a solution.
Moreover, I will use very basic loops rather than the fancy for-each loop since they are easier
to prove correctness with ─more accurately, easier for me with my current knowledge.

We are assuming simple undirected graphs: ie., pairs (V, E) of a set V of vertices
and a symmetric relation E ⊆ V × V.
Two vertices are “connected” precisely when there is a path along E between the two:
x ~ y  ∶≡ (∃ n : ℕ • x Eⁿ y) ─where the bullet serves to separate the bound variable
of the quantifier and the body of the quantifier, and exponentiation is iterated relational
product.
A “connected component” is a subgraph in which any two vertices are connected, and which
is connected to no additional vertices in the supergraph. For our needs, we only
consider connected components arising from subsets of vertices.

 connected-component
⇔ (∀ x,y :  • x ~ y) ∧ (∀  : ℙ V •  ⊆  ∧ (∀ x,y :  • x ~ y) ⇒  = )
⇔ (∀  : ℙ V • (∀ x,y :  • x ~ y) ∧  ⊆  ⇔  ⊆ )
⇔  is an ~-equivalence class

Note that ∧ means “and”.
Make-set assigns the emptyset ∅ to each vertex, in some look-up table.
We assume this to be the case at the very beginning and so need not worry about it.

Find-set looks up the set that is associated to a vertex, in the aforementioned look-up table.

Union(x,y) alters the set associated to x by unioning it what the set associated to y,
and does so as well for y. In particular, after this command we have
 Find-set x = old-Find-set x ∪ old-Find-set y.

The post-condition of the program is

∀ x : V •
   Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}

i.e.,

∀ x : V • connected-component (Find-set x)

That is, the algorithm assigns the connected components to the associated sets of the vertices.
Alternatively, it is: Find-set x = the ~-equivalence class of x.
From the post-condition,

  ∀ x : V •
   Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}

The simplest thing to do is to replace a constant, say E, with a new variable, and relate it
to the constant to obtain an invariant.

P ∷  ⊆ E  ∧
    (∀ x : V •
       Find-set x
       = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ  xᵢ₊₁))})

So it is obvious that the post-condition is obtained once we've arrived at the conclusion
E ⊆ . So a good idea is to increase  until this condition is true.
Moreover, the invaraint needs to hold before the loop and we can do this by setting
 ≔ ∅: indeed ∅ ⊆ E and intially every vertex is assigned the emptyset which is what
is needed since,

  {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ  xᵢ₊₁)))}
=⟨ initial value of  ⟩
  {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ ∅ xᵢ₊₁)))}
=⟨ definition of empty set ⟩
  {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • false))}
=⟨ “for all i, we have false  ≡ false” ⟩
  {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ false)}
=⟨ “false ∧ stuff ≡ false” ⟩
  {y : V ❙ (∃ x₀,…,xₙ : V • false)}
=⟨ “there is some stuff yielding false ≡ false” ⟩
  {y : V ❙ false }
=⟨ there are no y that make false true ⟩
  ∅
=⟨ initial value of Find-set ⟩
  Find-set x

So, to be very explicit, we assume that before the algorithm is run, we have

∀ x : V • find-set x = ∅.

Anyhow, the previous paragraph informs us that the algorithm we are looking for has the shape

{Pre: (∀ x : V • find-set x = ∅) }
 ≔ ∅
; {Invariant:  ⊆ E  ∧
(∀ x : V • Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y           ∧ (∀ i • xᵢ  xᵢ₊₁))}) }
while ¬ E ⊆  : do-stuff
{Post: (∀ x : V • Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}

Note that it is common to place “assert” statements within curly braces.
C♯ for example documents them in the form Contract.Assert.IsTrue(...).
It seems the only thing left to do is find an implementation of do-stuff.
Well, the loop terminates if we make the loop guard ¬ E ⊆  false.

By the invariant, we know ♯ ≤ ♯E and so increasing  will do the job.
We can choose an edge of E, it doesn't matter which one as long as it's one we haven't
considered it, and add that to . What, are there even such edges!?
Well, by the invariant, we have  ⊆ E ∧ E ⊈  within the loop, which implies
E -  ≠ ∅, whence there are such edges.

Hence, one possible candidate for do-stuff is

 (u,v) ≔ choose an edge from E -
 ;  ≔  ∪ {(u,v)}

The candidate is enough and we are done deriving our algorithm, “provided” that this choice
of do-stuff does not ruin the invariant.
It clearly does ruin the invariant since we have not altered the find-set for these two
vertices.

The final result is

 {Pre: (∀ x : V • find-set x = ∅) }
  ≔ ∅
 ; {Invariant:  ⊆ E  ∧
 (∀ x : V • Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ  xᵢ₊₁))}) }
 while ¬ E ⊆  :
   (u,v) ≔ choose an edge from E -
   ; if find-set u ≠ find set u then union(u,v)
   ;  ≔  ∪ {(u,v)}
 {Post: (∀ x : V • Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}

To relate this to your initial code, consider the following.

 for each i in S : do-stuff
≈
 visited ≔ ∅
 ; while visited ≠ S:
       i ≔ pick an element of S - visited
     ; do-stuff
     ; visited ≔ visited ∪ {i}

Our loop had ¬ E ⊆  and this is tantamount to E ≠ :

  E ≠
=⟨ bi-containment ⟩
  ¬(E ⊆  ∧  ⊆ E)
=⟨ invariant ⟩
  ¬(E ⊆  ∧ true)
=⟨ “stuff ∧ true ≡ true” ⟩
  ¬ E ⊆

We use basic while loops since they are easier to work with is all.
I've never really learned to write correctness proofs for for-each loops.

Hope this helps!

Bi-implication informal argument

The algorithm's post-condition is
find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}.

We show the equality using a bi-implication.

(⊆) ∷

By the construction of find-set, i.e., the way we add elements to the set associated to x,
we know that any added element is connected to x and so
find-set x ⊆ {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}.

(⊇) ∷

We will show by induction that any vertex y at-least n : ℕ edges away from
x must be within find-set x.

Base case: n = 0. Then x = x₀ = xₙ = y and clearly y ∈ find-set x.

Inductive step: if x E x₁ E x₂ E ⋯ E xₙ E xₙ₊₁ = y then by the inductive hypothesis
xₙ ∈ find-set x; moreover, the algorithm ensures find-set x = find-set xₙ.
Now since (xₙ, xₙ+1) is an edge ─a given─, the algorithm ensures
find-set xₙ₊₁ = find-set xₙ but by the previous equalities we then have
y ∈ find-set y = find-set xₙ₊₁ = find-set xₙ = find-set x.

:-)


How do incompressible strings and random strings share the same properties? I came across the following theorem in Sipser's about incompressible strings.

  Let $\;f$ be some computable function which holds for almost all strings. The for any $b > 0 $, the property $\;f$ is false only on finitely many strings that are incompressible by $b\;$.

where "almost all strings" means that as $n$ grows the fraction of strings of length $n$ for which $f$ is false approaches $0$.

The book proves the above theorem and says that if we select some sufficiently long string at random, it's likely that property $f$ would hold true for it. Thus incompressible strings and random strings share this property.

Though I understand the proof for the theorem, I am unable to understand its meaning. How does this show there is some sort of relation between incompressible strings and random strings?

Also how does this theorem help us? Although I can generate random strings, there is no method to generate incompressible strings in general.

The theorem says, in effect, that incompressible strings are a deterministic model of random strings. If you have some property that you can prove using random strings, you can also prove it using incompressible strings instead. If you have some construction involving a random string, you can make it somewhat more explicit using an incompressible string.

Another deterministic model of randomness, which is very useful in theoretical computer science, is expanders. These are models of random graphs with respect to a lot of properties. In many cases, instead of using a random graph you can use an expander. Since we can construct expanders explicitly, this allows us to derandomize many randomized constructions.

While the same cannot be said for incompressible strings, they are useful in some circumstances. Their use in lower bounds is known as the incompressibility method, which I encourage you to look up.


Using pumping lemma to prove a language is not context free When using the pumping lemma for a context free language, if I write any $w \in L$ as $uvxyz$, is my goal to show that a string will not pump for ANY arrangement of $uvxyz$ that I choose, or is my goal to show that THERE EXISTS some arrangement of $uvxyz$ over $w$ that will pump?

The pumping lemma claims that if the language is context-free, then there exists a configuration such that you can pump the string. Therefore, to prove that the language isn't context-free, you must show that pumping fails for every possible arrangement.


Time/Space Optimal k-Subset Operator Application - Is this a named problem? I have searched extensively and unsuccessfully for references to a
combinatorial problem that arises in my work. I am hoping someone
can tell me if this type of problem has a "name" and provably optimal solutions.

The problem: Given a set of objects denoted by $X_1,\ldots,X_N$, a commutative
and associative operator $\oplus$, and $K \leq N$, generate all $N \choose K$
subset-applications of the operator in a way that first minimizes the number of
operator applications, and then minimizes the number of partial results that
must be stored, assuming that once a complete combination is generated its
storage can be recovered. For example, for $5 \choose 4$ we need to generate the five
new objects
$$
X_1 \oplus X_2 \oplus X_3 \oplus X_4, \\
X_1 \oplus X_2 \oplus X_3 \oplus X_5, \\
X_1 \oplus X_2 \oplus X_4 \oplus X_5, \\
X_1 \oplus X_3 \oplus X_4 \oplus X_5, \\
X_2 \oplus X_3 \oplus X_4 \oplus X_5 \\
$$
which naively requires 15 operator applications and a single
accumulator. However a better solution
requires only 11 operator applications if storage is allocated for 3 partial
results.

Note that no negation or inverse of the operator $\oplus$ is assumed.  This rules
out using most popular combination-generation schemes such as Gray codes. In
the motivating application the operator is also idempotent ($X \oplus X = X$)
but I don't think this fact is helpful to a solution.

I have developed a good algorithm to solve the problem
using at most $N$ accumulators.  However it strikes me that others have
probably analyzed this type of problem and I simply don't know the correct
terminology to guide my search.

For $K \ll 2N/3$, a good solution goes as follows, for $K$ even (the case $K$ odd is very similar):

Generate all XORs of length 2.
Generate all XORs of length 3.
...
Generate all XORs of length $K/2$.
Generate all XORs of length $K$.

This requires $\binom{N}{K/2} + \binom{N}{K/2-1} \approx \binom{N}{K/2}$ memory and $\binom{N}{2} + \cdots + \binom{N}{K/2} + \binom{N}{K} \approx \binom{N}{K}$ operations. This is close to optimal in terms of number of operations, since clearly at least $\binom{N}{K}$ are needed.

You can optimize this a bit as follows:

Generate all XORs of length 2 of $X_1,\ldots,X_{N-K/2+2}$.
Generate all XORs of length 3 of $X_1,\ldots,X_{N-K/2+3}$.
...
Generate all XORs of length $K/2$ of $X_1,\ldots,X_N$.
Generate all XORs of length $K$.

The savings are not significant.


Is the simulation of how a warehouse functions (eg Amazon) a discrete event simulation problem If i wanted to write a piece of software that simulated a warehouse where typical warehouse procedures occur eg

loading of trucks onto conveyors
goods being transported around a warehouse by machines
goods being packed by operatives
goods being picked by operatives
... etc

should this be modelled / is this known as a discrete event simulation problem or a continuous event simulation problem.. or both?

Like many real-world models, this type of situation can be modeled both continuously and discretely. For example, if you defined the problem as a series of equations defining the rates at which items arrived and departed it would be continuous, but if you modeled it at a more microscopic level, showing individual arrivals and departures of trucks, it would be discrete. Then, going further, if you were to model the actual acceleration of the trucks as they departed the loading bay, it would become continuous again.

In general, job shop-type simulations are usually modeled as a series of discrete events. You may want to refer to queuing theory.

Note that there is an open source project called Facsimile that does discrete event simulation and is intended to do the kind of simulation you are aiming at. There are also a lot of commercial systems that specifically do industrial logistics and job shop simulation; for example AnyLogic is one such package.

You can also use generic simulation languages like Modelica to create the simulation.

In general, it is good idea to use simulation software rather than write your own simulation in many cases because there are many subtleties to it that you would not expect. Using an existing simulation package you can create your simulation in a fraction of the time it would take to program it and the result is potentially much more reliable with less risk of bugs.


What is the actual scope of the Halting Problem impossibility result? Consider the Halting problem : No TM H exists which given any TM and input, decides whether that TM will halt on that input. The usual proof (informally) is that if such an H existed, then a function D(X) = {if H(D,X) then loop; else Halt;} can be constructed, with D(D) leading to a contradiction => hence H can’t exist.
However, this proof relies on the fact that H decides Halting for any (TM,Input) pair as input - and so in particular, it can be given (D,D) to decide. But what if we suppose that H decides Halting for everything except D(D). Does the proof fall apart?
It seems that from “H can’t decide D(D)” we jump to the conclusion that “No TM exists that solves the Halting problem for any TM”. While that conclusion is technically valid, maybe there’s a TM that decides Halting for ‘virtually all’ Turing Machines, except a tiny subset - which includes D(D), or possibly D(any input), or even some slightly larger set. The above proof doesn’t preclude that.
Is there a more quantitative statement of the Halting Problem impossibility result - something that gives some measure of how many TMs (or a description/characterization of which ones), out of the set of all possible TMs, no single function can decide whether they halt or not?
To put it another way, maybe it's possible to construct a Halts() function that will be correct on 99.99999…% of its inputs? Or to be more precise, given a Halts() function candidate, we can state something quantitatively, along the lines of : Correctness = $ \lim \limits_{n \to \infty} \sum_{1}^{n} \frac {IsCorrect(Halts(n))}{n}$ (where the sum is over the indices of TMs in some fixed enumeration, and IsCorrect returns 1 if Halts(n) is correct). Now we can ask 1) Are there Halts() functions for which this limit exists? 2) Out of those, which ones maximize this limit?
The import of this is that if there's a Halts() function with a correctness close enough to 1, then the Halting undecidability theorem can be viewed as having little practical value and as being more of a curiosity applicable to a tiny subset of degenerate cases. Even though Rice's theorem shows a wide variety of questions that are undecidable because they can be reduced to the Halting problem, for each of those questions individually, the 'Correctness' limit above might still be close to 1, and so again, we'd be able to find algorithms that decide them for all practical purposes (save a few odd cases).
Note: This question is similar to what's asked in "Attempt #3" of this answer, but it doesn't look like that was ever addressed further (i.e. whether there's any research or literature that investigates such a limit).

Let us say that $H$ is a partial Halting oracle if it takes as input a pair $(M,x)$ where $M$ is the description of a Turing machine and an input $x$, and:

If $H$ terminates and outputs "yes" then $M(x)$ halts.
If $H$ terminates and outputs "no" then $M(x)$ does not halt.

In particular, $H$ is allowed to run forever and not give an answer.
Given two partial Halting oracles $H_1$ and $H_2$ we may combine their powers by running them in parallel, and if either one ever halts and gives an answer, we output that answer. Let us write $H_1 \oplus H_2$ for such a combined partial Halting oracle.
Consider the partial Halting oracle $L$ which works as follows on input $(M,x)$: it simulates the working of $M$ on input $x$, and if the simulation ever terminates, it terminates with output "yes". Then $L$ correctly predicts all cases that halt, and no others.
Given any partial Halting oracle $H$, we can always combine it with $L$ to get a partial Halting oracle $H \oplus L$ that correctly predicts all the halting cases. The only question then is, how good a predictor of non-halting can be implemented.
Define the non-halting set
$$\overline{K} = \{(M,x) \mid \text{$M(x)$ does not halt}\}$$
and for any partial Hlating oracle the set
$$S_H = \{(M,x) \mid H(M,x) = \text{"no"}\}.$$
We then have $S_H \subset \overline{K}$, $S_H$ is computably enumerable, and $\overline{K}$ is productive. Computability theory teaches us that $\overline{K} \setminus S_H$ is infinite, i.e., every partial Halting oracle fails infinitely often.
You may try to measure the ratio of $S_H$ to $\overline{K}$ in some fashion, such as the measure you suggest in the question. However, the problem with all such measures is that they heavily rely on how machines are coded. By passing to a different coding we can maipulate the measure to be whatever number we like, so that is not very helpful. For instance, to get a 99% success rate, use the following coding: a number of the form $100 n$ encodes the machine encoded by $n$ in some standard encoding, while a number of the form $100 n + r$ with $0 < r < 100$ encodes a machine that obviously never halts (always the same machine).


Given a minimum vertex cover can we find all the others in polynomial time? Having found one minimum vertex cover of a connected undirected graph, is there a known polynomial-time algorithm for finding all the other minimum vertex covers of the graph, or is this problem NP-complete as well?

Another question: what other ways (not necessarily polynomial-time) of finding the other MVCs when having one of them are there, Other than backtracking or re-running the algorithm that found the first MVC? A good answer to my original question would suffice marking it as such.

Just complementing on D.W.'s already correct answer.

Take a collection of disjoint copies of triangles.  This has $2^{n/3}$ many vertex covers.  If you add a universal vertex (a vertex connected to every other vertex), the graph obviously becomes connected.

Now, this universal vertex is always going to be in any minimum vertex cover.  However, for the rest of the graph (the original triangles), you still need to cover all the edges.  There are of course $2^{n/3}$ ways of choosing vertices to the vertex cover.

However, there is a well-known algorithm which enumerates every minimal vertex cover with polynomial delay, meaning that it takes polynomial time between every output.  This means that in graphs with few vertex covers, you can do this relatively quickly.

For your second question, the simplest is probably the $2^k n^2$ algorithm where $k$ is the size of the optimal vertex cover.  You branch on edges, deleting the vertex you chose to the vertex cover, and when you have an edgeless graph, you output the set of vertices you deleted.


NFA/DFA for $ L= \{a^n b^n a | n\ge0\}$ I have made two DFA’s for $ L= \{a^n b^n a | n\ge0\}$.

First one has several states. The second one is accepting an empty string also.

Somebody please guide me the correct one.

Zulfi.

Since FSM's can't count identical sequences, I don't think both of your answers would be correct. You can take a look here, (pumping lemma) to prove why $L= \{a^nb^n | n \ge 0 \}$ is not regular, thus you can't write a FSM for it. Also a good example here shows the proof. On the other hand it would be different if you are meaning $a^*b^*a$ which can be written as a FSM.


What's the difference between cache miss penalty and latency to memory? Can I say that cache miss penalty includes latency to memory? My current understanding is that cache miss penalty is the time moving data from the layer closer to main memory to it. But I'm not sure about what's the meaning of latency to memory? If they're not the same what's the overlapping part?

"Cache miss penalty" would be the extra time that is spent because of the cache miss.

Let's say your L1 cache has 5 cycles access time, and L2 cache has 23 cycles access time. That doesn't tell us enough yet.

A clever implementation might immediately detect that there is a cache miss, and send the data from the L2 cache simultaneously to the L1 cache and to whoever wanted the data. So without cache miss it might take 5 cycles, with cache miss 23 cycles. So you have 23 cycles latency for the L2 cache, but only 18 cycles miss penalty.

A less clever implementation might try the L1 cache first, then 5 cycles later start accessing L2 cache, put the data into L1 cache 23 cycles later, start the L1 cache access all over, and deliver the data another 5 cycles later. Total time 33 cycles, minus the 5 cycles without cache miss, so a 28 cycle miss penalty.


Achieving Randomness Can True Randomness be achieved by composing prngs in different states and with different algorithmsv(e.g. have $n$ different composition algorithms, use a prng to select any permutation of them. A lot $(\sum_{i=1}^{n}{^nP_i})$ of permutations exist. Compose the algorithms selected using the permutation. Whenever a new number is generated in a sequence of random numbers the entire algorithm selection process is repeated, and new seeds assigned to all algorithms.

The final result with/from the different prngs will be supplied as output.

For every new number, a fresh seed is taken to the random selection algorithm(to choose the composition of the PRNGs), this should be the most complex PRNG and have as much entropy as possible.

The sequence works something like this. Each PRNG takes two parameters; a seed, and some previous value.

For the first PRNG selected for composition, a seed $s$ is provided, and another randomly generated seed is used to generate another number $c$(This will be done by a randomly selected PRNG not in the sequence. So in actuality, we'll have $n+2$ PRNG algorithms). Each PRNG generates its own random number $k$. By choosing a permutation of some predefined composition algorithms (Whether the random number is to be floating or not, will define available composition algorithms, e.g final value $v \mod max$ will be used to arrive at the random integer) $c$ is used to modify $k$, to generate some $c_i$ to pass to the next algorithm in the sequence. The final $c_n$ will be adjusted to be within range as the random number.

I cannot conceive how such a system may be feasibly 'deterministic'.

Because of this, the algorithm shouldn't be philosophically deterministic. The next number is NOT based on previous numbers.

Arbitrarily designing a PRNG 'algorithm' isn't difficult (slightly modifying an existing algorithm, using different seeds to choose from, generating more than one result and choosing from it, etc). I read a post online about the security flaws of using prngs. How they are ultimately deterministic.

Will such a prng be deterministic?
Will it be able to achieve 'true' randomness?
Assuming all the prng algorithms have the same 'degree' of randomness
What is the minimum $n$ I should choose to make it non-feasibly deterministic? $\tag{*}$

My only worry now, is the computational expensiveness of such a model. It should have a worst case running time of $nf(n)$ where $f(n)$ is the worst case running time of the worst random algorithm. (Assuming PRNGS don't have their running time vary with their outputs) {Though the higher security, might be worth it}.

(*) Feasible deterministic, means that if all computers in the world were connected to make a super computer (assume this is possible and performance scales accordingly) this super computer will be able to 'crack' (be able to determine the next $k$ number(s) in line given an arbitrary list of generated numbers (from the same instance of this algorithm $n$ and arbitrary time $m$ s.
$n,m\colon n \ge m \gt 10^{10^{100}}$
$k$'s value is irrelevant. If it can crack the next 10, then given enough time, it'll crack the next 100.

True randomness, is defined as being non feasibly deterministic.

There are two types of answers:

Practical: You are looking for good stream ciphers. Several exist, though we don't know for sure that they are secure.
Theoretical: You are looking for cyptographically secure PRNGs. There are several suspected constructions, but such objects are not known to exist; if P=NP, then they don't exist.

In both cases, there is quite a wide literature on the subject.


$(\log n)^{\log n}$ lower-bound and upper-bound we know that $n \geq \log{n}$ however I understand that $(\log n)^{\log n}$ grows faster than $n$. I have been trying to prove this however I can't seem to figure it out.

Here is a way to show it without limits. Let $n = 2^x$. Now you are comparing the growth rates of $2^x$ and $x^x$.


Find the best set of triples of objects, using each object at max one time I stumbled upon an interesting problem and I'm stuck with it, since I can't find parallels to other problems or algorithms to solve it.

We have a set of objects $O = \{a,b,c,...,z\}$, objects can make triples, e.g. $T=(a,b,c)$  $a,b,c \in O$ and we have a set of triples $X = \{T_1, ... T_n\}$. Each triple is assigned a value $c: X \rightarrow \mathbb{R}$

not every object has to be in a triple
an object can be in multiple triples
there can be triples using the same objects, but in a different order e.g. $(a,b,c),(c,a,b)$

Goal: Find the subset of triples $S \subseteq X$, where $\forall x \in \bigcup S: \exists y \in \bigcup S => y =x$ (Every object may appear at most once in the selection) with maximum $\sum_{T \in S} c(T)$ (maximum value of selection).

Is there a fast way to get the maximum? If not, is there any fast strategy that may produce a good result?

A simple greedy strategy would be to sort the triples descending by value and take a triple into the subset if all of it's objects are unused. This can be done in $O(n \log n)$, but does not produce the optimal result.

Your problem is NP-hard.  In particular, 3-dimensional matching is a special case of your problem, and 3-dimensional matching is NP-hard -- so your problem is, too.


Converting any computable function into a sequence of additions Not sure if this question should be here, or on math.se.

That said, let me proceed:

On the Wikipedia page for the Ackermann function, it is mentioned that by passing the inputs of 0, 1 and 2 to the third parameter one could perform the three fundamental operations of addition, multiplication and exponentiation, respectively, on the other two parameters.
That is, addition, multiplication and exponentiation are the three fundamental operations.

But multiplication is merely repeated addition, and exponentiation repeated multiplication. So addition is the fundamental operation?

My question is this:

  Does there exist an algorithm to convert any sequence of (computable) mathematical operations, into another sequence of computable operations involving only addition.

I don't quite see the connection between the preamble and the question.

Regarding the three fundamental operations, this is of course an arbitrary selection. On one hand, you could say that the most fundamental operation is the unary successor function $x \mapsto x+1$. On the other hand, you have hyperoperations, some of them occurring naturally in Ramsey theory and combinatorial pseudorandomness.

Regarding your actual question, the answer is plainly no. No finite sequence of addition operations can compute the function $(x,y) \mapsto xy$, for example. Indeed, the output of any given sequence of additions on inputs $x,y$ is $O(x+y)$, which grows too slowly.

This is a special instance of a more general theorem about nested bounded iteration, which states that a function $f(n)$ can be computed using $m$ nested bounded loops iff it is recursive and eventually bounded by $A(n,m)$ (the binary Ackermann function). This is part of the circle of ideas around primitive recursive functions.


Is the FSA for that language right? Comparison between two solutions Given the alphabet $ Λ = \{a, b\}$ construct a FSA for the following language:

$$ L=\{α∈Λ^* ∧ |α|a =even ∧ |α|b =odd\}$$

where $|α|x $ is the number of occurrences of $x$ in $α$.
Basically, only strings where the number of $a$'s is even and the one of $b$'s is odd.

My attempt was the following:

whereas that's the solution of my teacher:

I wonder if mine is correct, too. I tried to follow the paths and I think that mine is working.

Your FSA would not accept the string AAB or ABBBA, or any string ending with a B or starting with AB... or starting with BA... etc., all of which it should.

One of your main issue is that you don't have any B paths out of state 1, but more problematically you only have three states, when you need at least four. This is because you have 4 different possible states, so you need at least 4 states to store all of them (odd A & odd B, odd A & even B, even A & odd B, even A & even B).

Your teacher's is correct because it has essentially divided up the responsibility of checking the parity of A's and B's to different halves. That is, you're in the top half of the graph whenever the number of A's is even, and the right half of the graph whenever the number of B's is odd. This works because each additional letter added is going to either make B go from odd to even (or vice versa) or A to go from odd to even (or vice versa).


Is there a largest class of halting programs? The halting problem says that a Turing machine cannot decide if another Turing machine halts.

However, we know that it is possible to determine if some programs halt. For example, FORTRAN DO statements are simple to formally verify. FORTRAN is however not Turing complete.

What is the largest subset or class of halting programs that can be decided?
Is there a class of such languages?

This blog entry
seems to hint at the fact that since the compiler optimized the code by eleminating the while(1) loop, Fermat's last theorem is disproved by a compiler.

There is no largest class of programs which have a decidable halting problem. If $L$ is such a class and $P \notin L$, then the class $L \cup \{P\}$ also has a decidable halting problem (why?). (This works since the class of all programs does not have a decidable halting problem.)

Responding to Raphael's comment, there is also no largest class of programs, up to finitely many exceptions, with a decidable halting problem. For each program $P$, let $L(P)$ be some infinite decidable set of programs equivalent to $P$ (for Turing machines, we can add dummy unreachable states, for example). Let $L$ be a class with decidable halting problem. I claim that there must be some $P$ such that $L(P) \cap L = \emptyset$. Otherwise, we could decide the halting problem for an arbitrary program $P$ by enumerating $L(P)$. Given a program $P$ such that $L(P) \cap L = \emptyset$, we can obtain a decider for $L \cup L(P)$, so that $L$ has infinitely many exceptions.


Calculate the amount of formal languages Statement:

  There are 256 formal languages $L$ with $L \subseteq \{w \in \{a,b\}^*
 \ \vert \ \ \vert w \vert = 3   \}$

Answer:

  True.

My question is why there are 256 formal languages. If I calculate the possible combinations with length 3 I get 6 combinations:

$M =\{aaa, aab, abb, bbb, bba, baa\}$

Calculalting the power set results in: $2^M = 2^6 = 64$

Where did I go wrong the get $64$ as result?

That would be eight combinations, as $2^3=8$. You missed $aba$, and another one.


What happens when all reference bits set to 1 in Second Chance Page Replacement Algorithm? I have a sequence like 5577334... and there are 3 frames available.

After the 6th clock, all pages (5, 7 and 3) will have their reference bits set to 1.
Now, when 4 comes in, 5 will go even though its reference bit is 1 because of the FIFO rule but what happens 7 and 3' referance bits? Do they stay as 1? or Is 7's reference bit set to 0 since there is FIFO rule? or Are both 7 and 3' referance bits set to 0?

Well, I found the answer in a textbook which is saying since there is a pointer looking for a page whose reference bit is 0, it will traverse the circular queue setting all reference bits to 0 and replacing the page who came first like FIFO.


Difference Between Residual Neural Net and Recurrent Neural Net? What is the difference between a Residual Neural Net and a Recurrent Neural Net?

As I understand,

Residual Neural Networks are very deep networks that implement 'shortcut' connections across multiple layers in order to preserve context as depth increases. Layers in a residual neural net have input from the layer before it and the optional, less processed data, from X layers higher. This prevents early or deep layers from 'dying' due to converging loss.

Recurrent Neural Networks are networks that contain a directed cycle which when computed is 'unrolled' through time. Layers in recurrent neural network have input from the layer before it and the optional, time dependent extra input. This provides situational context for things like natural language processing.

Therefor, a recurrent neural network can be used to generate a basic residual network if the input remains the same with respect to time.

Is this correct?

The answer is YES, they basically are the same according to this paper

The figure above shows how they compared both and how a ResNet can be reformulated into a recurrent form tat is almost identical to a RNN.
For more info you can read the paper and get deeper.


How can a distributed system cooperate to determine rules of its environment? I'm sorry if this question is silly or elementary. I'm not a computer scientist so I don't know the vocabulary to use to ask this question. Thus I've produced an analogy to explain the challenges I'm facing in my program. Please do point me in the right direction, I don't know what I need to learn to solve this problem:

An Analogous Puzzle:

Assume you are given a new house with 4 rooms. But this house is very strange; each room has 1-3 lights in it and 1-3 light switches. Some diabolical electrician has wired the house very strangely so that the switches can control lights in other rooms of the house. Furthermore, the behavior of the lights and switches may depend which lights are on at the time.

For instance a switch in room 1 may turn on on a light in room 2 if a light in room 4 is off, but it won't if room 4 is lit up. Almost all the light switches have a very strange relationship to some of or all of the other lights in this way. But they're not random, in their behavior: given the same state of the house a light switch will have the same effect as it did.

Now imagine you and 3 friends each occupy a room and are able to do one action in the house at a time. You can talk to each other by calling or texting each other on your cell phones, but every minute costs money, or every text costs money so you want to communicate as little as possible (thus you want to be efficient).

What I need to figure out is the answer to the following question:

How do you and your 3 friends need to communicate (what information do you need to share with each other) in order for the 4 of you to work together to deduce the wiring rules that govern the lights?

Does each person need to know the state of each room? Or do they only need to know the state of each room when something unexpected happens? How do they deduce the rules that govern the lights?

I need to find a universal way for the agents to infer the rules underlying the system efficiently. That's basically it.

In a more complicated scenario (thousands or millions of rooms), does anything change? What do I need to learn to solve this puzzle in a way that scales?

One other consideration: if necessary for a scalable algorithm you can recruit other friends from outside the house and give them information. I'm not sure why you would need to, but that's also a possibility.

That is the puzzle I have: many agents, mainly identical and independent are interacting with the same system.

I need to find an algorithm of cooperation/communication that results in the system as a whole, or each individual agent to infer/deduce (or even just behave in accordance with) the underly rules of the environment.

This is a non-mathematical riddle, so part of the solution is determining the rules of the game. The computer science way of solving this, however, would be to use a Gray code and a synchronized system. The idea is as follows. Suppose that there were only 3 switches. You will go over their states in the following order:
$$
000\\001\\011\\010\\110\\111\\101\\100
$$
(Here 0 is the original state of the switch, and 1 is the other state of the switch.)
Decide on a reasonable time interval $t$. There will be 8 rounds (or, in general, $2^k$ rounds if there are $k$ switches), each taking $t$ units of time. Each round other than the first begins with the appropriate person changing one of the switches (the appropriate person can be determined in advance once we know how many switches are in each room). Then they all record the "output" that they see in their room. When this process ends, they can compare notes and reconstruct the entire function.

This strategy is optimal with respect to the number of switch flips. While it takes $2^k$ rounds for $k$ switches, you can't really do any better since the function converting the input (switches) to the output (lights) is completely arbitrary. This does mean that it doesn't scale at all. If you want a strategy that does scale, you'll have to adjust the problem by restricting the set of possible functions (switch–light correspondences).


existence of a permutation that satisfies order-constraints I would like to know if there is a simple algorithm for checking the existence of a permutation that satisfies a number of order-constraints.

For example, suppose we have a set (1, 2, 3, 4, 5) and a number of constraints:

1 should be before 2
2 should be before 4
4 should be before 1

(which is of course infeasible).

Is there a simple algorithm for checking the feasibility of order-constraints? (that does not rely on lp-solvers)?

I do not have anything against Lp-solving, but i suspect that simpler algorithms are available.

Yes.  That task is called topological sorting.


Does a PDA immediately accept if at final state with empty stack? If computation on a PDA reaches a final state with an empty stack, will it immediately accept, regardless of whether or not the input tape has ended. For example if I have a PDA to recognize the language of strings where $a^nb^n$, if it was fed the string "aaabbba", will it stop after seeing the last "b" if the stack were empty and it was in an accept state? Or would the PDA, need to specify a dead state from the final state for incorrect strings?

For example, this PDA would seem to accept "aaabbba":

There are two ways in which a PDA may accept:

Final state: The PDA has finished reading the input and it is in the final state
Empty stack: The PDA has finished reading the input and its stack is empty.

The PDA in the example you have provided is non-deterministic, and when non-deterministic systems read an input for which a transition is not defined, they get stuck. In this case, when the PDA reads the string aaabbba, it would get stuck after reading the last b.


Why Isn't This Outlier Score/Reconstruction Error Not Squared? I was looking through a paper called "AI2
: Training a big data machine to defend", and saw this (http://people.csail.mit.edu/kalyan/AI2_Paper.pdf)

$score(X_{i}) = \sum_{j=1}^{p} (|X_{i} − R^{j}_{i}|) × ev(j)
$

Where $ev(j)$ is the percentage of variance.

I was wondering, why isn't the the term $(|X_{i} − R^{j}_{i}|)$  squared like other reconstruction error functions, or at least the ones I saw?

I believe the term $\sum_{j=1}^{p} (|X_{i} − R^{j}_{i}|)$ is a mean absolute error and is used here because it is better than a mean square error because it is better for a time series and is more robust. If I am wrong, please correct me.

there is a good explaination squarred vs flat.

But from the simple view squarred error aims at variance while flat at median.
Different outliers comes from both versions, this is task dependent - the choice has been made by authors.

In fact yes, it is called roboust (somehow missused term), but it is not "better" for time series, just gives better estimator for outliers in presented method, which from given equation uses neither mean error nor mean square error - it uses custom made estimator with variance calculated on it's own.


Data structures for general (non-tetrahedral) cell complexes For 2D polygonal meshes, the QuadEdge and HalfEdge data structure representations are sufficient to store and enable efficient query of all topological and incidence information. Are there compact and efficient data structures for 3D polyhedral meshes? I know there has been some recent work on compact representations for tetrahedral meshes, like, for example SOT. I don't know enough about these to know if they generalize to unstructured non-tetrahedral meshes.

I can imagine that half-edges might generalize to half-faces with associated half-edges, but it seems like that is a lot of data to store, and there might be more compact representations. I should add that I really only care about retrieving facet information (like which facets are on the boundary, which facets belong to a certain cell); the edge incidence information is not as useful.

There is an extension of half-edge in any dimension, called darts in combinatorial maps.
There are two packages in CGAL allowing to use these combinatorial maps in any dimension (see here for combinatorialMaps and here for LinearCellComplex).

You can use this data structure to represent any Quasi manifold orientable subdivided 3D object. Quoting from CGAL webpage(section 2.4 Combinatorial Map Properties):

A quasi-manifold object is defined as:

  A dD quasi-manifold is an object obtained by taking some isolated d-cells, and allowing to glue d-cells along (d-1)-cells.

and orientable as:

  It is orientable if it is possible to embed it in the Euclidean space and to define a global "left" and "right" direction in each point of the embedded object.


Generate all permutations of 1 to n with i stacks Assume we have i stacks. the possible actions are:

push to first stack form input
pop from stack i and push it to stack i+1
pop from last stack to output

If we have numbers of 1 to n starting from 1 in the input, what is the minimum value of i which  can generate all permutations of 1 to n at the output?

The options are:

1
2
n-1
n

Option 1 obviously is not the answer, and also it's totally possible with n and n-1 stacks witch removes the option 4.

The real question is "is it possible doing with 2 stacks or we need n-1"?

What is the minimum value of $i$ which can generate all permutations of 1 to $n$ at the output?
  The options are: 1) 1 $\;$ 2) 2 $\;$ 3) $n-1$ $\;$ 4) $n$

None of the given options are correct.

All permutations of 1 to 7 can be generated by 3 stacks.
The permutation 7132465 cannot be generated by 2 stacks.

The above facts can be verified by an exhaustive search by a program easily. So the minimum value of $i$ which can generate all permutations of 1 to 7 is 3. Note that $3\not=2$ and $3\not=7-1$.

Let $s_i$ be the minimum value of $i$ which can generate all permutations of 1 to $n$. Then
$s_1=0$, $s_2=s_3=1$, $s_4=s_5=s_6=2$, $s_7=s_8=3$.

It is not clear to me what are the value of $s_i$ for $i\ge 9$.


Looking for a simple example of Transition Semantics I want to define a semantics of a DSL through transition semantics. For my DSL I defined the syntax and implemented a code generator. Although I can provide a demo by giving examples, I want to write the semantics of my DSL to provide a formal specification of it.

However I don't know how to do it!. Can someone provide me with an example?

What do you mean by "transitional semantics"? If you mean structural operational semantics using transition systems, then maybe a good place to start is a good text on the semantics of programming languages, Examples:

Winskel's Formal Semantics of Programming Languages.
Hennessy's Semantics of Programming Languages.
Nielson & Nielson's Semantics with Applications.

I recommend ignoring denotational semantics for your task.

Since the semantics of programming languages is really well-understood, most of the work in formalising DSLs usually comes from the domain-specific part of the language.


How to give an upper bound on this bin packing problem? In the bin packing with fragile objects (BPFO) problem one is given a set of objects $\{1,\ldots,n\}$ where each object $i$ has a weight $w_i$ and a fragility $f_i$ for all $i$ in the set $\{1,\ldots,n\}$. (We assum that $w_i\le f_i$.) Also, we have a set of bins of infinite capacity (each) in which we want to place the objects.

The objective is to assign the objects to the minimum number of bins such that the sum of the weights in each bin is at most the minimum fragility. That is, if we assign the set of objects $S$ to bin $B$ than we must have:

$$\sum_{i\in S}w_i\le\min\limits_{i\in S}f_i.\quad\quad\quad  (1)$$

The BPFO problem is given in this paper. Let us denote the optimal value of BPFO by $OPT$.

I am trying to relax BPFO by modifying equation$~(1)$ as follows.

$$\sum_{i\in S}w_i\le f_i,\forall i\in S$$

Let us denote the optimal value of the relaxed problem by $OPTR$.

Now, I would like to upper bound $OPT$ by $OPTR$. How can I achieve this?

It is clear that a solution to BPFO is a solution to the relaxed problem and then $OPT\ge OPTR$.

Is there a way to say that $OPT\le \alpha(n)OPTR$ where $\alpha(n)\ge 1$ ?

Your relaxation is same as original problem.

$$\sum_{i\in S}w_i\leq f_j,\forall j\in S$$

is same condition as

$$\sum_{i\in S}w_i\leq\min\limits_{j\in S}f_j$$.

because

$$\min\limits_{i\in S}f_i \leq f_j,\forall j\in S$$.


How to implement graph search to solve Sudoku puzzle My teacher pointed out to us during lectures that we could use Graph Search to help us solve Sudoku puzzles which has left me puzzled .

I dont see how this is possible as Graph Search is mostly about getting from Node A to Node B. He mentioned about how its a directed graph where the nodes correspond to partially completed puzzle

What is the general idea behind using Graph Search to solve Sudoku Puzzle

A graph is defined abstractly as a set of vertices together with a set of edges connecting those vertices. You have to give the vertices/edges meaning to make sense of the problem. For Sudoku, a vertex is a board configuration and an edge from configuration $a$ to configuration $b$ exists if $b$ is obtained from $a$ by inserting a number in an empty cell of $a$. There are $(9^2)^9$ possible configurations; searching this graph for a solution will take a lot of time but you will find one eventually. Many of the configurations are invalid Sudoku grids so you can eliminate lots of them.

A typical Sudoku solver would search an implicit graph: the solver is not given a graph as input but it is given a procedure to generate candidate configurations given some configuration. One such procedure may be described as:

generate_candidates(config) {
  candidates = [] is a list of configs
  for every empty cell (call it C) in config
    for every number in [1..9]
      C = number
        if config is a valid grid
          add copy of config to candidates
}

In the implicit graph, the edges are the ones that look like 'config $\to$ candidate' where config is the input to generate_candidates and candidate is a configuration generated by generate_candidates. Of course you have to generate new candidates from the ones just generated; you keep growing that list of candidates until no more can be generated or you've found a solution.


Is there a known, fast algorithm for counting all subsets that sum to below a certain number? I recognize that the subset sum problem is NP-Complete. I have a different, yet similar problem, which I'll call subset below-sum:

Given a set of integers, $S$, and a target number, $n$, what is the number of subsets of $S$ that sum to less than $n$?

For example, if $S$ is $\{1, 2, 3, 7, 7, 15\}$, and $n$ is $20$, the answer is $38$.

Is this an NP-Complete problem? If not, what is a fast algorithm to compute the answer?

Subset below-sum appears to be NP-Hard. This is informal, but consider, if you can solve subset below-sum in polynomial time, you can solve subset sum in polynomial time.

Given: does any subset of $S$ sum to exactly $n$?
Let $A$ be $subset\_below\_sum(n)$ and $B$ be $subset\_below\_sum(n + 1)$. If $B - A \gt 0$, the answer is yes, otherwise, the answer is no.


How can an existential type be defined in terms of universal type? In Types and Programming Languages by Pierce,  how does the following achieve the definition of an existential type  in terms of universal type, by polymorphic version of Church encoding of pairs?

  24.3 Encoding Existentials

  The encoding of pairs as a polymorphic type in §23.4 suggests a
  similar encoding for existential types in terms of universal types,
  using the intuition that an element of an existential type is a pair
  of a type and a value:

{∃X,T} := ∀Y. (∀X. T→Y) → Y.

  That is, an existential package is thought of as a data value that,
  given a result type and a continuation, calls the continuation to
  yield a ﬁnal result. The continuation takes two arguments—a type X and
  a value of type T—and uses them in computing the ﬁnal result.

To complete the quote, the polymorphic version of Church encoding of pairs of numbers is given in Exercise 23.4.8 (p349 p546):

pairNat = λn1:CNat. λn2:CNat.
λX. λf:CNat→CNat→X. f n1 n2;
fstNat = λp:PairNat. p [CNat] (λn1:CNat. λn2:CNat. n1);
sndNat = λp:PairNat. p [CNat] (λn1:CNat. λn2:CNat. n2);

which is further generalized to pairs of elements of any types, on p352

  we use the abbreviation Pair X Y (generalizing the PairNat type from
  Exercise 23.4.8) for the Church encoding of pairs with ﬁrst component
  of type X and second component of type Y:

Pair X Y = ∀R. (X→Y→R) → R;

  The operations on pairs are simple generalizations of the operations
  on the type PairNat above:

> pair : ∀X. ∀Y. X → Y → Pair X Y
fst : ∀X. ∀Y. Pair X Y → X
snd : ∀X. ∀Y. Pair X Y → Y

Thanks.

As a general recipe, to figure out how to encode a type A, write down

∀Z . (A → Z) → Z

and massage it to something that does not involve A, using basic isomorphisms, such as currying and uncurrying. For example, if we plug in A := X + Y we get:

∀ Z . (X + Y → Z) → Z           ≅
∀ Z . (X → Z) × (Y → Z) → Z     ≅
∀ Z . (X → Z) → (Y → Z) → Z

You can also read the above lines as a sequence of logical equivalences. So this gives us the encoding of X + Y in terms of the universal quantifier.

I do not understand why in your question you speak about existential types, but since you do, it is worth explaining the encoding of ∃ X . B(X) in terms of ∀ this way:

∀ Z . ((∃ X . B(X)) → Z) → Z    ≅
∀ Z . (∀ X . (B(X) → Z)) → Z

Again, you can read the equivalence either as a type isomorphism or a logical equivalence in logic, using the fact that $(\exists x . \phi(x)) \Rightarrow \psi$ is equivalent to $\forall x . (\phi(x) \Rightarrow \psi))$.


multicasting in ethernet I am learning this topic and there is a concept that LSB ( bit ) of MSB ( byte ) should be set to 1 for multicasting . But why we need to do so as multicast address is unique so why can't we assign any multicast address which is not present in that network.

Without a flag that tells you whether an address is a group address or a host address, you can't tell whether it's a group address or a host address.
Remember, a switch only sees the source address and the destination address. It does not have any extra information. So, it needs to be able to tell just by looking at the address whether to multicast the frame or not.


permutations sampling by probability matrix I am looking for effective and reliable algorithm which is able to generate random samples of permutations by square doubly stochastic probability matrix $P$ (n x n) distribution ($\sum_{i}p_{i,j} = \sum_{j}p_{i,j} = 1$, $i,j = 1,2,...,n$).

Probability matrix elements $p_{i,j}$ define probability of $i = \pi(j)$ and $0 <= p_{ij} <= 1$.

The sampled permutations should correspond to the defined probability matrix $P$ and probability of each permutation should correspond to the following permutation probability

$$p(\pi)=\frac{\prod_{i} p_{i,\pi(i)}}{\sum_{all \pi}\prod_{j} p_{j,\pi(j)}}=\frac{\prod_{i} p_{i,\pi(i)}}{perm(P)}$$

Example: Probability distribution matrix

$$ P = \left( \begin{array}{ccc}
0 & 1 & 0 \\
1/2 & 0 & 1/2 \\
1/2 & 0 & 1/2 \end{array} \right) $$

produce only two permutations $\pi_1 = (2 1 3)$ and $\pi_2 =(2 3 1)$ with the same probability $p(\pi_1) = p(\pi_2) =1/2$

This question is a follow-up to Random permutations by probability matrix

I tried a few variations of node histogram based sampling algorithm (NHBSA) by Shigeyoshi Tsutsui. This method is used as a main tool on permutation optimization problems. But the results are not very promising. So, I ask this question here, to learn what is current state of art on this topic.

I tried to test a few algorithms, but all these methods produce permutations with more or less distorted probability matrix even for small n (3 <= n <= 10 ). This is the reason why I am asking for help.

  Some comments here states that interpretation of matrix $P$ and permutations probability $p(\pi)$ are not clear enough to define unique permutations distribution.

  So, is possible to use $\prod_{i} p_{i,\pi(i)}$ for ranking of permutation probabilities, where permutations $\pi$ are generated randomly only by (0,1) restriction matrix via Hungarian algorithm for bipartite graph matching?

Comment:
I am convinced now, that only "simple" way how to solve my problem is to generate arbitrary (random) permutations $\pi$ which satisfy to (0,1) restrictions in probability matrix only (elements $p_{i,j}>0$ should be transformed to $p_{i,j}=1$) and then rank all these permutations by $\prod_{i} p_{i,\pi(i)}$ probability.

The problem how to effectively generate (0,1) restricted permutations (permutations with restricted positions) is different problem.

The problem has recently been actively studied:
https://arxiv.org/abs/2007.15043
https://arxiv.org/abs/1904.03836
https://projecteuclid.org/euclid.ejs/1586419218
https://academic.oup.com/comnet/article-abstract/6/6/833/4772759
P.S. It is true, that problem is not fully or correctly defined, but Raphael's comments are at least a bit confusing.


Count unhappy numbers in a large interval An unhappy number is a number that is not happy, i.e., a number $n$ such that iterating this sum-of-squared-digits map starting with n never reaches the number 1.

For example, $23\rightarrow 2^2+3^2 = 13 \rightarrow  1^2 + 3^2 = 1$, so $23$ is a happy number. But, number $2$ is not and you can verify it.

The problem around my question (from 2010 acp icpc problem set) is to count unhappy numbers in an interval $[\textrm{lo}, \textrm{hi}]$. I'm looking for an algorithm that is practical for $\textrm{hi}$ up to $10^{18}$.

How can I  write an algorithm for this problem, efficient and correct?

I know that the solution is with dynamic programming, but I don't know how can I get it.

My approach when I read the problem was use a backtracking to mark all numbers in the interval, like a dfs, and see that when you're processing a number and got the result, you should mark all numbers with form permutations of digits for the initial number. Then, I thought that a backtracking approach is faster. But this is not enough for contest, because the interval is $[1, 10^{18}]$ so, clearly dynamic programming is the way.

I suggest you to start reading this Wikipedia page for an explanation, and then select from Rosetta code an implementation in one of the programming languages you know and to study it. Many algorithms are either based on caching or detecting the loop 4, 16, 37, 58, 89, 145, 42, 20, 4, ...

A dynamic programming solution, implemented in Haskell, is available here.

EDIT

The C source code available here uses the GNU GMP library to test for happiness of very large numbers. You can use it to test far beyond $10^{18}$, assuming you have enough memory. The code is for windows, but is easily portable to linux and Mac OS X.


Why is $\dfrac{1}{2}n^2-3n = \Theta(n^2)$? By definition:

  For a given function $g(n)$ we denote by $\Theta(g(n))$ the set functions

  $\Theta(g(n))$ = $\{f(n):$ there exists positive constants $c_1, c_2$ and $n_0$ such that $0 \leq c_1g(n) \leq f(n) \leq c_2g(n)$ for all $n \geq n_0$ .$\}$

We say $6n^3 \neq \Theta(n^2)$ becuase if it was, then there would be:

\begin{equation}
6n^3 \leq c_2n^2 \Rightarrow n \leq c_2/6  \hspace{100px} (1)
\end{equation}

which is not true because $n$ (size of the input) is not limited to any constant.

But to prove $\dfrac{1}{2}n^2-3n = \Theta(n^2)$ we can write

\begin{align*}
    c_1n^2 &\leq \dfrac{1}{2}n^2-3n \leq c_2n^2\\
    c_1 &\leq \dfrac{1}{2}-\dfrac{3}{n} \leq c_2
\end{align*}

by setting $c_1=1/14, c_2=1/2, n_0=7$ it becomes true.

Here is the problem,

$$\dfrac{1}{2}-\dfrac{3}{n} \leq  c_2$$

implies

$$
n \leq \dfrac{1/2-c_2}{3} \hspace{100px} (2)
$$

why in $(1)$ bounding $n$ is a contradiction, but in $(2)$ it is not?

Thanks

Since $n>0$, $\dfrac 3n >0$. Hence $\dfrac{1}{2}-\dfrac{3}{n} \leq  c_2$ is implied by $\dfrac 12\le c_2$.

That is, your (2) is not correct while everything else is fine.

Just in case you cannot see why your (2) is wrong, please take a look at the following deduction.
$$ \dfrac{1}{2}-\dfrac{3}{n} \leq  c_2\\
\dfrac{1}{2}-c_2\le\dfrac{3}{n} \\
\dfrac{1/2-c_2}{3} \leq  \dfrac 1n\\
\dfrac 1n\ge\dfrac{1/2-c_2}{3} $$
Compare the last inequality with your (2).


How Dynamic programming can be used for Coin Change problem? As far as I can unserstand Dynamic programming stands simply for memoization (which is a fancy name for lazy evaluation or plain "caching"). Now, I read that there is we can reduce complexity of coin-change problem by truncating some search branches with caching.

Here is the problem, by the way

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

I prefer the Scala translation

  def countWithoutRepetitions(s: Int, dimes: List[Int]): Int = {
    if (s == 0) 1 else
       if (s < 0 || dimes.isEmpty) 0
        else dimes match {
          case d :: ds => {countWithoutRepetitions(s, ds) + countWithoutRepetitions(s-d, ds)}
        }
  }

Odersky also asks for cache-based trimming algorithm in his course (pdf for those who are not enrolled). Yet, I do not understand what do people discuss at all.

The search tree never repeats itslef. It never calls the function with the same (sum, available_coins) arguments. What are you going to cache?

Work an example.  I worked through the Scheme version with the input 35 (and with the denominations of the coins as 1, 5, 10, 25, 50) and I'm seeing a ton of repetition in the search tree.  (cc 5 1) has already come up 3 times and I'm only about half way through.

Also, memoization actually does a little more than lazy evaluation.  Lazy evaluation caches the thunk for the expression assigned to a particular dynamic instance of a variable so that the thunk gets evaluated at most once.  But memoization caches all expression evaluations, so if the expression is assigned to different dynamic variable instances you'll also only get a single evaluation.  This requires a bit more machinery (you have to hash the arguments of the expression, and store the argument/result pair in a hash table.)  If you were to rewrite the function in a lazy functional language (like Haskell) you wouldn't automatically get memoization benefits in this case.


Implement Context-Free Grammar for $L=\{a^n b^m \mid n \neq 2m\}$ I am trying to implement a context-free grammar for $L=\{a^n b^m \mid n \neq 2m\}$.

I have a difficulty trying to implement it because I don't know how to ensure that $n \neq 2m$.

I can easily implement $n=2m$ but the other way around doesn't seem intuitive. How can I approach this problem?

Hint: A string of the form $a^nb^m$ where $n \neq 2m$ can be either

A string with too many $a$'s, or
A string with too few $a$'s

Create production rules for each of these cases.


Efficient algorithm to decide if a location is reachable I am designing a game solver. I have a binary $m*n$ Matrix, where $0$ stands for a free space, while $1$ stands for an occupied space. In the game we move a ball that we will call $x$. The ball can only move UP, DOWN, RIGHT or LEFT (no diagonal).

Imagine the following matrix:

$
1 0 0\\
0 1 0\\
x 0 1
$

We see that the ball is in the lower left corner -- which is "trapped".
What efficient algorithm can I use to decide if the ball is trapped, that is if there is no way to get to the other side (like the example given above)?

Another example where the ball is not trapped:

$
1 0 0\\
1 0 0\\
x 0 1
$

I am using bits matrices, I would rather not use graphs if possible.

The problem you're trying to solve is exactly graph connectivity. You don't necessarily need to construct the graph explicitly but this is a graph problem.

By "you don't necessarily need to construct the graph explicitly", I mean that you don't necessarily need to create any new data structures.  Every time your graph algorithm says "vertex", you can think "co-ordinates" and every time it says "neighbour" or "adjacent" or "edge", you can think of the squares above, below, to the left and to the right that contain 0.


Why is this expression (A and ¬A |= C) entailed? Hopefully I am posting this in the right place, I am currently in a course of knowledge representation, and I came across an exercise about entailment:
$$A\land\neg A\vDash C\,.$$

I would argue that this expression is not entail, but it is actually entailed, but I don't see how, can you help me figure out why?

The statement $X\vDash Y$ means "every assignment to the variables that makes $X$ true also makes $Y$ true." Or to put it another way, "There is no assignment of variables that makes $X$ true but fails to make $Y$ true." Well, there's no assignment of variables that makes $A\land\neg A$ true, so there's certianly no assignment that makes $A\land\neg A$ true and also makes $C$ false.  So $A\land\neg A\vDash C$ is a true statement.

False entails anything is a rule, analogous to false implies anything.


What is wrong with this solution for $\mathcal{O}({\log({n \choose \frac{n}{2}})})$? In this recitation on MIT OCW, the instructor uses Stirling's approximation to calculate that

$\mathcal{O}({\log({n \choose \frac{n}{2}})}) = \mathcal{O}(n)$.

However, I went through the following steps to conclude that $\mathcal{O}({\log({n \choose \frac{n}{2}})}) = \mathcal{O}(\log{n})$. Where did I go wrong?

First, note that ${n \choose \frac{n}{2}} = \frac{n!}{\frac{n}{2}!\frac{n}{2}!}$. By basic logarithm laws, we get that this is equal to $\log{(n!)} - \log{(\frac{n}{2}!\frac{n}{2}!)}$. From this it follows that:

$$
\mathcal{O}(\log{(n!)} - \log{(\frac{n}{2}!\frac{n}{2}!)})\\
= \mathcal{O}(\log{(n!)}) \\
= \mathcal{O}\Big(\log{\big(n(n-1)(n-2)\cdots(1)\big)}\Big) \\
= \mathcal{O}\Big(\log{n} + \log{(n-1)} + \ldots + \log{(1))}\Big)
= \mathcal{O}(\log{n})
$$

So, what is wrong here? I've gone over it for a while and I can't see any mistakes. Plotting these functions, though, I can see quite clearly that there must be a mistake.

$\mathcal{O}\Big(\log{n} + \log{(n-1)} + \ldots + \log{(1))}\Big)
= \mathcal{O}(\log{n})$

That is not right. When $n$ is large enough,

$$\begin{align}
\log{n} + \log{(n-1)} + \ldots + \log(1)
&\ge \log{n} + \log{(n-1)} + \ldots + \log(n/2)\\
&\ge n/2 \log(n/2)\\
&=\Theta(n\log n)
\end{align}$$

More precisely, since $n!\sim {\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}}$ by Stirling's approximation,

$$\begin{align}
\log{n} + \log{(n-1)} + \ldots + \log(1)
&=\log(n!)\\
&\sim \log\left({\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}}\right) \\
&\sim n(\log(n) -1) \\
&\sim n\log(n)
\end{align}$$

You can take a moment to try understanding intuitively why
$$\lim_{n\to\infty}\frac {\log(n!)}{\log (n^n)} = 1.$$


Are there any types of distributed databases which allows untrusted peers, like Blockchain? Are there any types of distributed databases which allows untrusted peers, like Blockchain?
If it exist, can I look its whitepapers and/or implementations?

Distributed Hash Tables (DHT) are key value stores that work in a P2P manner, which is basically a database. There are implementations that don't rely on trust between peers. Obviously this can only be achieved by strong replication and consensus on the current value to a given key. So you face similar problems as with a blockchain.

The Wikipedia Article https://en.wikipedia.org/wiki/Distributed_hash_table will give you a good overview. Chord and Tapestry are probably the most famous DHT concepts.

If you want to look at applications instead The DHT approach is mostly used in peer-to-peer file hosting and file sharing.

There might also be other distributed databases or database-like concepts out there. This is just one I know.


Does computational complexity theory take into account problems with subjectivity in the verification of a solution? When we discuss P vs NP we are looking at the difference between problems that are easily solved versus easily verified (wrt polynomial vs exponential time).

But in both cases these are black-and-white results. We do/don't solve the problem, we do/don't verify the problem.

What about cases where there is subjectivity to the verification? Problems where 2 people don't agree on the solution, since the solution may depend on context, environment, etc.

Does computational complexity deal with the subjectivity in verification, or are all problems modeled as black-and-white results?

No.  Computational complexity doesn't deal with subjectivity.  In computational complexity, we consider formal languages that are precisely defined, so there is no subjectivity.


Finding the interior of a connected graph I'm designing software that produces images such as the following:

Regions of interest are circumscribed by red pixels. I am interested in extracting the fully-enclosed pixel regions. Ultimately, I would like to calculate the approximate center, width, and height of the regions. Ideally, I would even like to eliminate interior loops--that is, only preserve the largest enclosing body of a region (a "region" being an isolated pixel group).

I have experience implementing search algorithms, so my first instinct is to traverse the edges until a loop is detected (arrival at the start); however, I recognize the potential for multiple solutions--alternate, valid loop possibilities--and then I would require a way to decide between them. Perhaps the one that is longer or encloses the greatest number of pixels.

If you are given the red pixels, try decomposing the pixels into strongly connected components (SCC), where two pixels are in the same SCC if they are adjacent and neither one is red.  Then each SCC represents a region.  This is a standard technique in computer vision.  Another way to think about this: try using flood fill from each possible starting point.

If you're not given the red pixels: you have a blob finding / segmentation kind of problem.  Try looking at existing methods for block detection.  You should also look at the watershed algorithm for image segmentation.  There are also methods based upon max flow (i.e., minimum graph cuts).

Doing some searches using these keywords will probably find you many more resources.