using 2 short CRC(s) VS one longer CRC I'm doing some research on the CRCs, but i can't find informations about the use of two (or more) short CRCs compared to the use of a longer CRC:

Suppose that i have a dataword A of some length and 3 different generator polynomials, 2 of degree 8 and one of degree 16. These polynomials are used respectively by CRC1, CRC2 and CRC3 algorithms, where CRC1 and CRC2 generate 8-bit codes while CRC3 generates 16-bit codes.

Suppose also that the three CRC have the same Hamming Distance for datawords of the same size.

now consider these 2 options:

Compute CRC1(A)=x1 and CRC2(A)=x2 and use codeword A|x1|x2 (where '|' means concatenation);
Compute CRC3(A)=y and use codeword A|y;

what are the eventual advantages and disadvantages of the first approach in respect to the second considering error detection capabilities?

Please provide also some references if you have them!

Ok, i found what i was searching in a paper "Selection of Cyclic Redundancy Code and Checksum Algorithms to Ensure Critical Data Integrity" https://www.faa.gov/aircraft/air_cert/design_approvals/air_software/media/TC-14-49.pdf

in Section 5.7 we can read that: "[...] Based on the results of this study and a literature review, there is no evidence  that  multiple  error  codes  on  the  same  dataword  increase  HD.    However,  adding  more  bits  of  error-detection code does tend to increase the coverage at that HD by creating more bits that  must  be  randomly  matched  to  form  a  valid  codeword. Quantifying  such  a  gain  requires  careful analysis of common-mode undetected error patterns for the multiple error coding schemes used, with a caution that pure mathematical analysis is prone to subtle errors and should always be validated via Monte Carlo simulation."

So the answer to my question is that it's impossible to select the best option unless they have been evaluated through mathematical analysis and subsequent experimental validation :(


Splitting summations? From CLRS Introduction to Algorithms, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and bound each term separately. For example,

$$\begin{align*}
\sum_{k=1}^{n} k &= \sum_{k=1}^{n/2} k + \sum_{k=n/2 + 1}^{n} k\\
&\geq \sum_{k=1}^{n/2} 0 + \sum_{k=n/2 + 1}^{n} (n/2)\\
&= (n/2)^2\\
&= \Omega(n^2)\,\end{align*}$$

I get step 1, that makes sense, but I didn't understand step 2 where they have replaced $k$ with $0$ in one part and $k$ with $n/2$ in the other. Why did they do this?

Thanks!

In the first sum, you know that k ≥ 0. In the second sum, you know k ≥ n/2. Therefore, adding k in the first sum is ≥ adding 0 in the first sum, and adding k in the second sum is ≥ adding n/2 in the second sum.

You can adapt this for example to show that the sum of $k^5$ for 1 ≤ k ≤ n is $O(n^6)$: You have n/2 terms each at least $n^5/32$, for a total of $n^6/64 = O(n^6)$. Or a lower bound for n!, where you have a product including n/2 terms each larger than n/2, so n! > $(n/2)^{n/2}$.


Why discriminate the base case allows me to complete the induction proof? I have a successful completed proof which used induction. but I essentially proved the goal on the base case by tactic discriminate.  Why is this induction proof still stands?
the principle of induction tells us induction involves three steps:
     - show that the P(O) holds, (* O stands for the first item *);
     - show that, for any n, if P(n) holds, then so does
       P(next(n));
     - conclude that P(n) holds for all n.

but if I finished proving subgoal P(O) by discriminate, that is, confirmed the subgoal is impossible, how does that constitue as a holding base case?
Here's the proof in question:
Fixpoint filter {X:Type} (test: X->bool) (l:list X) : (list X) :=
  match l with
  | [] => []
  | h :: t =>
    if test h then h :: (filter test t)
    else filter test t
  end.

Theorem filter_property : forall (X : Type) (test : X -> bool) (x : X) (l lf : list X),
filter test l = x :: lf -> test x = true.
Proof.
induction l.
- intros. discriminate.
- simpl. destruct (test x0) eqn:Etest.
 + intros. injection H. intros. rewrite -> H1 in Etest. apply Etestx.
 + apply IHl.
Qed.

You want to prove that if the result of of filter test l is a non-empty list, then its first element passes test. You're using induction on l.
The base case for the induction is the empty list []. For the base case, you need to prove that if filter test [] = x :: lf then test x = true. In order to prove this, you assume that filter test [] = x :: lf, and prove that this hypothesis is a contradiction. Indeed it is: there is no value of x and lf that makes filter test [] = x :: lf true, because filter test [] is the empty list. So, for the base case, for any x and any lf, the proposition filter test l = x :: lf -> test x = true is true.
Using the notation you've used to state the principle of induction, P(n) has the form “Q(n) implies R(n)” (where Q(n) is “the result of filter is a non-empty list” and R(n) is “the first element passes the test”). It would be strange if P(0) was vacuously true, but that's not what's going on here: what's going on is that R(0) is vacuously true, because Q(0) is impossible. The base case P(0) is possible. It happens to have the form of an implication where the premise is impossible, but that's just happenstance.


Transform regular grammar in linear grammar My problem is how can I transform a regular grammar into a linear grammar?

I know that a linear grammar has the form

$\begin{align} A &\to w_1Bw_2 \\
               A &\to w \end{align}$

where $A,B \in N$ and $w,w_1,w_2 \in \Sigma^*$.

A (right) regular grammar is one in which all production rules are of one of the following:

$$B \rightarrow a$$
$$B \rightarrow aC$$
$$B \rightarrow \lambda$$

Where $B$ is a non-terminal, $a$ is a terminal and $\lambda$ is the empty word. A regular grammar is a grammar which is either right-regular xor left-regular. As you have said in a linear grammar one does not require the nonterminals to appear on the far side of the right of the production rules. Therefore, every regular grammar is already a linear grammar.


How to compare an element with other elements within an array efficiently for a condition I need to compare each index with one another and associated array value as well.

For example,

for(int i = 0; i < n - 1; i++) {

    for(int j = i + 1; j < n; j++) {

        if(a[i] > a[j]) { // Condition will be any

            swap(a[i], a[j]); // Any action
        }
    }
}

Inside loops, there is a condition to check. Similarly I need to use any condition

eg: if(i + j == a[i] + a[j])

Could anyone help to optimize this index comparison? How to compare each index with other and element value with others efficiently i.e. less than O(n²)

In the general form you present, you have $\Theta(n^2)$ things to compare so you need $\Omega(n^2)$ time. If you know more about the arrays or the comparison operator (e.g., the arrays are sorted and the comparison is $<$ or $>$) then you can probably do something better but, without more restrictions, there's no hope.


Is this algorithm actually a graph-traversal algorithm? I was given in a lecture the following algorithm that wwas said to be a graph-traversal algorithm.

The algorithm given during the lecture

The algorithm

EXPLORE (s:sommet, D:list of the following vertices of the vertices ahead,
var visited:tab)
var: LIST:list; i,j: vertexes;
visited[s]←_true_;
LIST←{s}
While LISTE ≠ 0
    Select i∈LIST
    if ∃ j ∈ D[i], not visited[j]
    visited[j]←true;
    Else LIST←LIST-{i}

PARCOURS(D: list of the out-going vertices or ahead vertices)
for all vertex x in X
     {visited [x]<-false}
for all x in X
    if not visited [x]
    EXPLORE(x,D,M or visited)

 the example I tried

\begin{array}{|l|cr|}
x & \Gamma^+(x)\\
\hline
X1 & X2,X4 \\
X2 & X1,X3\\
X3 & X4,X5 \\
X4 & X6,X7 \\
X5 & X2,X6 \\
X6 & X4,X7 \\
X7 & \emptyset \\
\end{array}

I assume that this is the list (tell me if you think this is not the case).

Select 1 $\in$ LIST

LIST(1)=X2,X4 $\not= \emptyset$

X2 $\in$ LISTE(1) is not visited, so we change visited2 to true
X4 $\in$ LISTE(1) is not visited, so we change visited[4] to true
no more elements are not visited, we do LISTE <-LISTE-(1)

the array-list thus becomes:

\begin{array}{|l|cr|}
x & \Gamma^+(x)\\
\hline
X2 & \not X1,X3\\
X3 & X4,X5 \\
X4 & X6,X7 \\
X5 & X2,X6 \\
X6 & X4,X7 \\
X7 & \emptyset \\
\end{array}

And I can plot $X1$

Then I do the algorithm again

Select 1 $\in$ LIST

LIST(2)=X3 $\not= \emptyset$

X3 $\in$ LISTE(2) is not visited, so we change visited$[3]$ to true
no more elements are not visited, we do LISTE <-LISTE-(2)

the array-list thus becomes:

\begin{array}{|l|cr|}
x & \Gamma^+(x)\\
\hline
X3 & X4,X5 \\
X4 & X6,X7 \\
X5 & \not X2,X6 \\
X6 & X4,X7 \\
X7 & \emptyset \\
\end{array}

I can plot anew:

Then I'm not sure wether to SELECT X4 or X3. It seems that it is the whole difference between Depth-first search algorithm and Breadth-first search ones.

I think this the way the first part of this algorithm run, yet I'm not sure on how does the second partt works. It seems that it allows to explores every paths in my mere opinion...

The algorithm given by a friend of mine

Yet, a friend of mine just wrote the following one rather shorter to do the same thing:

EXPLORE (s:sommet, D:list of the following vertices of the vertices ahead,
var visited:tab)
var: LIST:list; i,j: vertexes;
visited[s]←_true_;
LIST←{s}
While LISTE ≠ 0
    Select i∈LIST
    if ∃ j ∈ D[i], not visited[j]
    visited[j]←true;
    LIST←LIST+{j};
    Else LIST←LIST-{i}

I don't understand how the first one is a graph traversal algorithm and I wonder if it is the best one as far as it seems that the second one is shorter, (but unclearly to me actually).

There seems to be a bug in the first algorithm which is fixed in the second algorithm, namely the first EXPLORE explores only the starting vertex and its neighbors, but nothing beyond that. However, the first algorithm at least explores the entire graph; the second one only explores the connected component of $s$. The second one also doesn't bother to initialize the array visited.

I strongly suggest that you try and understand what these algorithms are doing. It could help running them manually on a few examples. You could also program them and have the programs print out the actions performed by the algorithms.


Turing-recognizable languages closed under star operation I'm tasked with demonstrating that the class of Turing-recognizable languages is closed under the operation of star, but I'm confused about how this is true. For example, I have a TM to recognize a language A = { a2n: n >= 0 }, all strings of a's which length is a power of 2. So here's where I get confused, if I have A*, then I can have (aa)*, which could then lead to (aa)(aa)(aa) = aaaaaa, and this has a length that is not a power of 2. What part of my logic here is wrong?

You're confusing the definition of $A^{\ast}$ and $A$. It is only $A$ in your example that contains strings of $a$s whose lengths are powers of two. $A^{\ast}$ does not have this restriction - it has that restriction that its strings are made up of strings from $A$.

So the individual components of each string in $A^{\ast}$ have to have lengths of powers of two (because they're from $A$), but together we only get that for every string $a^{m}$ in $A^{\ast}$ there is some set $N = \{n_{1},\ldots,n_{k}\}$ (different for each string) such that $m = \sum_{n_{i} \in N} 2^{n_{i}}$.


Are Random Forests Turing-Complete? Is the random forests algorithm Turing-complete? As in, can any algorithm be represented by a given "tree" in the forest?

No, they're not Turing complete.  The handle inputs of a fixed size.  Also, they can't loop, so will always halt -- it follows that they don't have the ability to perform Turing-complete computation.


Covering radius of a code in the Hamming space A deterministic $(2−2/(k+1))^n$ algorithm for $k$-SAT based on local search

　I have read this paper and I couldn't understand how to culculate the $covering$ $radius$ of a code in the Hamming space. It is defined as follows in the paper.

　We identify assignments with binary words. The set of these words of length $n$ is the $Hamming$ $space$ denoted by $H_n=\{0,1\}^n$. The $Hamming$ $distance$ between two assignments is the number of positions in which these two assignments differ. The $ball$ of radius $r$ around an assignment $a$ is the set of all assignments whose Hamming distance to $a$ is at most $r$.
　A $code$ of length $n$ is simply a subset of $H_n$. The $covering$ $radius$ $r$ of a code $C$ is defined by
$$r=\max_{u∈\{0,1\}^n}\min_{v∈C
}d(u,v),$$
where $d(u,v)$ denotes the Hamming distance between $u$ and $v$.

　The $\max$ of $\min$ is exactly the point I couldn't calculate. So I considered the instance of $C$ and tried to calculate its covering radius.
e.g.)$$C=\{000,010,011,100,101,110\}⊆H_3$$

　In this case, how can I calculate the covering radius $r$?

It's easier to remove from your table all lines with codes already in C. In your case only two lines will remain, minimum distance in both lines are 1, so the maximum distance of these two is max(1,1)=1

Overall, the algorithm is the following:

for each possible code x, find the closest element c in C (i.e. the one with minimum distance d(x,c)) and record this distance
find the maximum of all distances recorded at the previous step

I find that it's well visualized with set of spheres covering part of 3D space. You check all points outside of spheres and find one that has the largest distance to its closest sphere.


Why not use large $k$ in a $k$-ary tree? Obviously binary trees are great because of $O(\log_2 n)$ search, inserts, and deletes in best case.

To "maximize" occurrence of best case, we can use self-balancing trees like red-black trees, AVLs, splay trees, etc.

If we use a $k$-ary tree, we can get $O(\log_k n)$ searches, inserts, and deletes in best case. Similarly we can "maximize" the occurrences by using self-balancing trees.

I know these are asymptotically of the same order, i.e. $O(\log n)$, but the constant could be huge in practice.

The huge reason I can think of is that by using larger $k$'s, you lose the ability to make a decision based on one comparison.

What are other reasons larger $k$ $k$-ary trees aren't used in practice?

BTrees are used in practice - file systems, database with $k$ for example equal 1024 or 4096, so it seems to be bigger than binary.

Probably you have not encountered need yet.
For example ternary tree with comparing >, =, < gives theoretical improve $O(log_3 n)$, but self balancing trees in basic form do not accept duplicates, so there is more overhead and not strictly practical.
But bigger ones, yes, they give boost and you use it right now (on the computer).


is modulo of hash function is evenly distributed? if I take the result of a 32bit hash function(the param is random string) and apply module N on the result - will the values be evenly distributed?

so if I have a histogram of values [0,N-1] will the histogram be evenly distributed ?

Thanks

if I take the result of a 32bit hash function(the param is random string) and apply module N on the result - will the values be evenly distributed?

It depends on the hash function. For a good hash function the output should be uniformly distributed.

  so if I have a histogram of values [0,N-1] will the histogram be evenly distributed ?

For any reasonable hash function, yes.

Keep in mind that real-world hash functions are sometimes terrible. Many programming languages will, as the hash of an integer (using the built-in hashing function), return the original value. This is not a problem if your input is truly random, but usually the reason to use a hash function is to take an input that has some structure, and produce hashes that (hopefully) don't.


Infinite chain of big $O's$ First, let me write the definition of big $O$ just to make things explicit.

$f(n)\in O(g(n))\iff \exists c, n_0\gt 0$ such that $0\le f(n)\le cg(n), \forall n\ge n_0$

Let's say we have a finite number of functions: $f_1,f_2,\dots f_n$ satisftying:

$O(f_1)\subseteq O(f_2)\dots \subseteq O(f_n)$

By transitivity of $O$, we have that: $O(f_1)\subseteq O(f_n)$

Does this hold if we have an infinite chain of $O's$? In other words, is $O(f_1) \subseteq O(f_\infty)$?

I'm having trouble imagining what's going on.

We first need to clarify what we mean by "does this hold if we have an infinite chain?".
We interpret it as an infinite sequence of functions $\{f_i:\mathbb{N}\to\mathbb{N} \mid 1\leq i\}$ such that for all $i$ we have $f_i(n) = O(f_{i+1}(n))$. Such a sequence might not have a last function.

We can look at the limit of the functions in the sequence, i.e. $f_\infty(n) = \lim_{i\to \infty} f_i(n)$. However it is possible that the limit does not exists. And even in the case that it exists we might not have $f_1(n) = O(f_\infty(n))$. For example consider the sequence of functions $f_i(n) = \frac{n}{i}$.
For each $i$,
$f_i(n)=\Theta(n)$ and therefore $f_i(n) = O(f_{i+1}(n))$.
However $f_\infty(n)=\lim_{i\to\infty}f_i(n)=0=\Theta(1)$
thus $f_1(n) \neq O(f_\infty(n))$.

On the other hand we can look at the limit of the sequence of the classes which doesn't need to be equal to the class of the limit of the functions.
We have $f_i \in \mathcal O(f_{i+1})$, therefore $\mathcal O(f_i) \subseteq \mathcal O(f_{i+1})$ and $f_j \in \lim_{i\rightarrow\infty} \mathcal O(f_i) = \limsup_{i\rightarrow\infty} \mathcal O(f_i) = \liminf_{i\rightarrow\infty} \mathcal O(f_i) = \bigcup_{n \in \mathbb{N}}\bigcap_{k>n}\mathcal O(f_k)$ for all $j$. The limit superior contains all elements (functions in this case) which occur infinitely often and the limit inferior contains all elements which occur in all $\mathcal O(f_i), i \ge n_0$ for some $n_0$ (which may depend on the element). Since the sequence of classes is monotonically increasing both exist and they are equal. This justifies the usage of $\lim$.


How to solve this max contiguous subarray sum with a twist? How to solve the max contiguous subarray problem, where we have an addition parameter $M$, and the contiguous subarray must include both $A[M]$ and $A[M-1]$?
For example, for the zero-indexed array $1, -4, 2, -2, 4, 1, -1, 1$, if $M=1$ then the contiguous subarray must include the first two elements, and so the answer is $-1$ (corresponding to the contiguous subarray $1,-4,2$).
The code I have right now without this "twist" is:
procedure MaxSubarraySum(A):
    current_sum <- 0
    max_sum <- (-infinity)
    N <- A.length
    for i <- 0 to N do:
        current_sum <- current_sum + A[i]
        if current_sum > max_sum then:
            max_sum <- current_sum
        endif
        if current_sum < 0 then:
            current_sum <- 0
        endif
    endfor

    return max_sum

But I'm stuck on how to change it so that max_sum always include $A[M]$ and $A[M - 1]$.

Let the input array be $A[1 \dots n]$ and consider any contiguous subarray $A[i \dots j]$ of $A$ such that $i \le M-1$ and $j \ge M$ (that is, $A[i \dots, j]$ includes both $A[M-1]$ and $A[M]$).
The subarray $A[i \dots j]$ maximizes $\sum_{k=i}^j A[k]$ if and only if:

$A[i,\dots M-2]$ is a (possibly empty) suffix of $A[1 \dots, M-2]$ that maximizes $\sum_{k=i}^{M-2} A[k]$;
$A[M+1,\dots j]$ is a (possibly empty) prefix of $A[M+1 \dots,n]$ that maximizes $\sum_{k=M+1}^{j} A[k]$.

This is easy to prove using a cut-and-paste argument.
Notice that 1. and 2. are essentially the same problem, which can be solved by a trivial $O(n)$-time algorithm that computes the sum of all prefixes/suffxes of $A$.


Finding A String Using A Suffix Array/Table Is it possible to find out a string only having its corresponding suffix array/table and knowing that the string contains only, for instance, letters "f", "g", "r"? If so, how is that possible?

Sure: the longest stored suffix is the string itself.

In a suffix array, it's particularly easy to find: scan the array for starting index $1$ -- the suffix starting at the first character is, quite obviously, the string itself.


Closure of regular languages are closed under certain cut operations Let $f : \mathbb{N} \to \mathbb{N}$ be an integer function. For a language $L$, define

$$f(L) = \{w \mid \exists x : |x| = f(|w|) \text{ and } wx \in L\}$$

For example, if $f(n) = n$ this is just the "halving" operation, and regular languages are well known to be closed under this -- just simultaneously walk forwards and backwards (where the backwards walk tries all possible paths, like in the subset construction).

According to HMU, regular languages are also closed under taking the functions $2n, n^2, 2^n$. It is easy to see for $2n$, or any linear function for that matter - just walked backwards with whatever the speed. How can this be done for $n^2$ or $2^n$? It doesn't seem feasible to just increase the speed, since that would require remembering the number of steps taken so far.

Also, can we adapt the solution to get some general sufficient conditions on which $f$ has this property? (I doubt there are necessary and sufficient conditions, but would love to be proved wrong)

Take a DFA $\langle Q,q_0,F,\delta \rangle$ for $L$. For every state $q \in Q$, it is known that
$$
N_q = \{ n : \delta(q,x) \in F \text{ for some $|x|=n$} \}
$$
is an eventually periodic set. In these terms, we have
$$
f(L) = \bigcup_{q \in Q} \{ w : \delta(q_0,w) = q \text{ and } |w|+f(|w|) \in N_q\}.
$$
A few simple arguments show that $f$ is admissible (the set of regular languages is closed under $f$) if for every modulus $m$, there is a DFA $\langle Q',q'_0,\delta' \rangle$ over the alphabet $\{0\}$ which "computes" $|w|+f(|w|) \bmod m$, in the sense that on input $0^n$, you can recover $n+f(n) \bmod{m}$ from $\delta'(q'_0,0^n)$. This, in turn, happens if for every modulus $m$, the function mapping $n$ to $n+f(n) \bmod{m}$ is eventually periodic. Since $n \bmod{m}$ itself is periodic, we conclude that:

  A function $f$ is admissible iff for all $m$, the function $\psi_{f,m}(n) = f(n) \bmod{m}$ is eventually periodic.

The Chinese Remainder Theorem shows that it suffices to consider values of $m$ which are prime powers.

All polynomials are clearly admissible: if $f$ is a polynomial, then $\psi_{f,m}$ has period $m$. Exponential functions $a^n$ are also admissible: if $m=p^k$, then either $p \mid a$, in which case $\psi_{f,m}$ is eventually zero, or $(p,a)=1$, in which case Euler's formula shows that $\psi_{f,m}$ has period $\varphi(m)$.

I'm not sure if the set of admissible functions can be characterized any further – this is an interesting research direction.


Symbolic Evaluation for Type Inference in a Dynamic Language Say I have the following contrived example code:

a(1)

function a(x) {
  var n = b(x)
  var m = c(x)
  return n + m
}

function b(x) {
  var n = d(x / 2)
  var m = e(x)
  return n - m
}

function c(x) {
  var n = d(x)
  var m = e(x)
  return n * m
}

function d(x) {
  return x + 2
}

function e(x) {
  return x + 3
}

Then, I am analyzing the method d(x). From just analyzing it by itself, we can infer that x must be some sort of number. We do this by what seems like simulating x + 2, and realizing that for that to be satisfied x must be a number. Not quite sure how to implement the type inference here, not sure if it uses symbolic evaluation too.

But then we get to the function call a(1). In this case to do typechecking / type inference on d(x), we have to somehow traverse down the tree of functions, simulating how x is transformed along the way. It finds out that it is divided by 2 somewhere in there, so it goes from integer to float. So we check based on our original assumption that d(x) is a number, and agree that it will be valid.

That is just me roughly trying to figure out how to do type checking / type inference.

I'm wondering two things:

If you need to do some sort of symbolic evaluation to do type checking / inference. If so, any suggestions on resources or places/ways to better understand that.
Say we have a gigantic app with millions of lines of code. Say between a(x) and d(x) there were 500 function calls, doing all sorts of things to x. Wondering if we have to simulate that entire process to figure out if x will be a valid type, or if we can somehow limit the scope and do some sort of shortcut. If we had to traverse the 100's of functions for every variable, that would be a ton of evaluation and would be slow. So wondering how to limit the scope of the search somehow, to do type checking / inference.

Basically I am figuring out how to do type checking / inference. The resources are mostly on the lambda calculus from what I've found, which I am not too familiar with and works differently I would imagine than an imperative program.

For example, they seem to be mentioning that here:

  (1) 3.2 Type Graph

  After each method has been converted into its intermediate
  representation, zscript gradually builds a type graph by each
  method called by the program.
  The CPA is non-iterative. Only the methods that could
  potentially be called are processed, and (except for templates)
  they are only processed one time only.
  In our implementation of the algorithm, we use a work list. First,
  the constructor of the class containing the main method, and the
  main method itself is added to the work list. Then, while the
  work list is not empty, the methods of the work list are
  processed. During the processing of a method, more methods
  may be added to the work list. The algorithm terminates when no
  more methods remain to be analyzed.

I am not sure you actually understand the terms you use here.

Symbolic execution has nothing to do with type inference

Symbolic execution is used for static analysis of programs, and is a special case of abstract interpretation. The symbolic executor provides an symbolic input value and traces the program execution given that symbolic input value.

Type inference is much simpler: it involves automatically deducing the type of programs. Nowhere is symbolic execution of the program involved.

Type inference is usually undecidable

For a dynamic typed language, type inference is not decidable. Moreover, even we have a static type system, type inference is usually still undecidable.

The only (?) type system we know of that has decidable type inference is the Hindley-Milner type system, i.e. System F with only Rank-1 types (plus a few conservative extensions). It is known that H-M can type imperative programs (such as Standard ML), as long as you can give good typing rules. When I was an undergraduate, we did an exercise in which we implemented H-M type inference for a restricted, strongly-typed version of Scheme (which was imperative). It was a lot of fun, but it also proves that
type inference is possible for imperative programs.

Update: oh, how could I have left out the canonical reference for polymorphic, inferable typing of imperative programs? The canonical reference would be Xavier Leroy's PhD thesis, Typage polymorphe d'un langage algorithmique (translated into English as Polymorphic typing of an algorithmic language).

I suggest that you start reading on Hindley-Milner and Algorithm W, as a first step (see, e.g., Chapter 22 of Types and Programming Languages by Benjamin C. Pierce). I also suggest that you do more basic reading and learning before asking on CS.SE, as that would make this site work much better. The theory of programming languages is not like coding and must be studied systematically if you want to have a solid grasp of it :-)


does a non-terminated string count as a token in c? so, I am preparing for an exam which includes lexical analysis from compiler design. I was wondering what is the number of tokens in the following code-

int main() {
  /* comment
  printf("Hello */ There ");*/
  return 0;
}

so, I am thinking upto first "*/" it will be a multiline comment, so, after "there" a string will start without terminating. will the last string is counted as a token?

No, in C unterminated strings are not tokens. The C language definition precisely describes what a token is; among other things, they include (complete) string literals and a fallback category of "single non-whitespace characters" which are not otherwise matched by the lexical grammar. This latter category does not, however, include " and ' characters; if these characters are not matched as part of a longer token, the result is specifically flagged as undefined behaviour.

So your text is invalid precisely because it cannot be divided into tokens. A conforming implementation must respond by providing at least one diagnostic message.

All of the above is specific to the C language standard. It is not a "principle of computation" and should not be applied to any other programming language.

For additional precision, the C standard defines two categories of tokens. Initial program text analysis (in phases 1 and 2) splits the text into preprocessing tokens and whitespace (whitespace includes comments, which are not tokens). The translation process then passes the stream of preprocessing tokens through phases 3 to 6, commonly known as "the preprocessor" although it is an integral part of program translation.

Preprocessing leaves most tokens intact but there are features which allow adjacent tokens to be fused or converted into a string literal token. Also, macros may ignore their arguments causing those tokens to vanish. It is not possible to split a token into multiple tokens.

In phase 7, the preprocessing tokens which survive preprocessing must be converted to tokens. Although this is described as a conversion, no textual modification is made; what is converted is the category of the token. Not every character sequence which qualified as a preprocessing token can be treated as a token; phase 7 conversion of such a token will fail and a diagnostic message will be produced.

So it can make sense to talk about an "illegal token" (@, for example) which is still a token. But unterminated string and character literals do not all into that category. They really are not tokens at all.

See §5.1.1.2 of the C standard for a precise description of the translation phases. Tokens are defined in §6.4, which includes the prohibition on unmatched " and ' in paragraph 3:

  A token is the minimal lexical element of the language in translation phases 7 and 8. The categories of tokens are: keywords, identifiers, constants, string literals, and punctuators. A preprocessing token is the minimal lexical element of the language in translation phases 3 through 6. The categories of preprocessing tokens are: header names, identifiers, preprocessing numbers, character constants, string literals, punctuators, and single non-white-space characters that do not lexically match the other preprocessing token categories. If a ' or a " character matches the last category, the behavior is undefined.


Expressiveness of modern regular expressions I recently discussed with a friend about a website that proposed regex challenges, mainly matching a group a of words with a special property. He was looking for a regex that matches strings like |||||||| where the number of | is prime. I immediatly told him that won't ever work because if such a language was regular, the translation of pumping lemma would gives the fact that for a prime $p$ large enough, it exists $k \leq p$ such that $p + nk$ is prime for all $n \geq -1$, and well this is not likely to be the case at all (repartition of primes, triviality of such an unknown and crushing property, ...)

But then someone came with the solution : NOT MATCHING (||+?)\1+
This expression tries to match the capture group (that can be ||,|||,|||| and so on of $k \geq 2$ occurences of |) $n \geq 2$ times. If it matches, it means that the number represented by the string is divisible by $k$, and hence is not prime. Otherwise, it is.

And I felt stupid, because it became obvious that grouping and backreference allows regex to be actually a lot more expressive than...regular expression, in the theoritical sense. Now they even added lookarounds and other operators I didn't know about when I used to do real regex.

According to Wikipedia, it is even more expressive that languages generated by a context-free grammar. So here is my question :

can we represent any algebraic language (generated from a context-free grammar) with modern regular expression engines
is there a more general description, or at least an upper bound on the complexity of what kind of languages can be described by a modern regex ?

More pragmatically, is there any serious theory behind it or are we just adding any new features as it comes each time it seems implementable to the initial block of real regular expressions based on finite automata ?

I know that "modern regex" isn't very specific while the question is, but I mean at least with backreferences, and possibly more. Of course, if you have partial anwsers assuming certain restrictions on this "modern regex" language, feel free to post it.

The word problem of regular expressions with backreferences is NP-complete;
citing Aho (1990) via Blaisorblade/Charles Stewart.

I don't know the whole set of operators some flavors of regexps have, but several are no more powerful than regular; they have probably been added as syntactic sugar.


Decidability of Turing Machine accepting exactly 14 words Would you say that the following problem is undecidable?
$$L_1 = \{\langle T \rangle \mid T \text { accepts 14 words}\}$$
My intuition says that this must be undecidable, and I want to try to reduce it from the emptiness problem for Turing Machines. If we can tell whether or not a TM accepts 14 words, then we should be able to tell if it accepts 0. Since we know EMPT is undecidable, I have been trying to do reduce EMPT to this problem, but I am not sure exactly how to do it.

Can anyone confirm if this is actually a valid starting point, and if it is, any hints on how to formulate a formal reduction?

Your intuition is correct. Probably you can reduce emptiness (or maybe its complement) to this language but it's not the way I'd do it. Instead, think about how you prove that emptiness is undecidable.

You want to know if $M$ halts on input $w$ so you produce a TM that accepts everything if $M$ accepts $w$ and rejects everything if $M$ rejects $w$. A slight modification of that proof will show that your language is undecidable.


Can a Turing machine have infinite states? Does it make sense for a Turing machine to have infinite number of states ? I had previously asked a question Can Turing machines have infinite length input. From which I came to know about Type-2 Turing machines. If there can be infinite states, encoding of such a Turing machine would be infinite ( but again I am not sure if it make sense to encode a Turing machine with infinite states thus having an infinite description ). So it would make sense that if I have to give the encoding of such a Turing machines as input, I would give it as input to Type-2 Turing machines.
But is there any use of infinite states ( and what is there link to Type-2 Turing machines ? ) ? If I am not wrong there is no function which is uncomputable by normal Turing machine but computable by Turing machine with infinite states.

No.  The definition of Turing machines requires that the finite-state control unit have a finite number of states.  It's not allowed to have an infinite number of states.

A machine that could have infinitely many states in its control could accept any language (unlike a Turing machine).  However such a machine could not be implemented in practice.  For these two reasons, it would not be a good model of the computational power of real computers.

In addition, once you allow an infinite-state automaton, there's no need to have any tape -- the tape doesn't add any computational power, because an infinite-state automaton can already do "everything".  For these reasons, while it would be possible to construct machines that look like Turing machines but have infinite state, there would be little point: their power would be equivalent to an infinite-state automaton on their own, i.e., every language can be accepted by such a machine.


Rules to follow to create edges in graph I am currently writing a graph object in Swift, I see that there are different types of graphs, some that are undirected and some that are directed. Here are my questions :

Can a graph be both directed and undirected, is there a specific name for such graph?
What is the common approach to make an edge that would be bi-directionnal but whose weight depends on the direction you are following. Would it be acceptable to make an edge that hold two weights, one for each direction? Or should I create two edges?

Thank you.

A graph that is both directed and undirected is called a Mixed graph.

All graph libraries that I know don't have direction dependent edge properties. Hence I would advise against introducing them if two directed edges do the job.


A problem about Huffman codeword Under Huffman Encoding, what circumstances codeword length  of each character
be equal?(suppose number of character is power of 2)

I think if all frequency of characters is same then codeword length of all characters be the same.
Surprisingly, if there are two characters that differences between frequency of two characters be $2$, and frequency of other be equal then codeword length of all characters be the same.
Main problem is, can i say, for each constant $c$, if there are two character that difference of  frequency be $c$, and all remaining of characters  have equal frequency then codeword length  of each character be equal?

Assume there are 2^n symbols, n >= 2, and the frequencies of the most common and the two least common symbols are f, g, and h. We could use a code of n-1 bits for the most common and n+1 bits for the two least common symbols. This will reduce the average code length if f > g+h.
You were specifically asking for the frequencies 2^-n + c/2, 2^-n, and 2^-n - c/2, so that’s the case for c > 2^-n / 2.


CPU frequency per year I know that since ~2004, Moore's law stopped working for CPU clock speed.
I'm looking for a graph showing this, but am unable to find it: most charts out there show the transistor count or the capacity per year.

Where can I find some data showing the CPU frequency of computers (anything is fine, personal computers, servers, laptops, ...) from the last few decades to today?
Raw data that I can plot myself would be fine as well (hum, probably even better).

The graphs you want are printed in the book “CMOS VLSI Design” Weste/Harris (2005), on page 5 of the freely available introduction.


NP complete language having no Polytime decidable superset Is there an NP complete language having no polytime decidable superset (apart from the set of all strings)?

A slightly simpler proof is to note that $\Sigma^* \setminus \{w\}$ is polynomial-time decidable and a superset of any language $L$ where $w\notin L$. Formally:

Suppose $P\not = NP$ and let $L$ be some $NP$-complete language. Then there exist at least $2$ strings $v\not = w$ so that $v\not \in L, w\not \in L$ or $L$ would not be $NP$-complete (since $L$ would either be $\Sigma^*$ or $\Sigma^*\setminus L$ would be a singleton). Then $\Sigma^{*}\setminus \{w\}$ is polynomially decidable and a superset of $L$ (since $v\in \Sigma^{*}\setminus \{w\}$).

If $P=NP$ then every language that is not $\emptyset$ or $\Sigma^*$ is $NP$-hard, so in particular $\Sigma^* \setminus \{x\}$ is $NP$-complete (where $x$ is any string in $\Sigma^*$). However, $\Sigma^* \setminus \{x\}$ has no (proper) superset that is not $\Sigma^*$. So if $P=NP$, there is a a language having no superset $\in P$ that is not $\Sigma^*$.


Bits of memory address used for page number? A $64$-bit computer has a virtual mem space of $2^{64}$ bytes and the computer also uses memory paging with size of $2^7$ $(128)$ bytes.

Work out the bits of the memory address which are used for the page number?

No. of bits of the memory address which are used for the offset?

Can someone explain how I would go about doing this ?

Your virtual address is of size $64$ bits. This means your system can address $2^{64}$ bytes. Each virtual address your system generates points to a byte of memory.

Your system has a page size of $2^7$ bytes. Operating systems like to group bunches of memory bytes together into what is called a page. Think about each page as a block of memory that contains many bytes.

We have a virtual space of $2^{64}$ bytes that we need to page. How many blocks of memory (of size $2^7$ bytes) can we fit in this address space (of size $2^{64}$ bytes) ? $2^{64}$ / $2^7$ = $2^{57}$ blocks (or pages).

We need $2^{57}$ pages. Therefore, there would be $57$ bits required to address each page that we have.

Now, remember each page has $2^7$ bytes. If your OS were looking for a specific byte, the first $57$ bits in the address would have the page number it wants. Then, the last $7$ bits would address a byte on that page. The number of bits used to address a byte in a page is called the offset.

So, $7$ bits for the offset, $57$ bits for the page number. Together, they equal a $64$ bit virtual address.


What's the algorithm for floating points equality test? I've found that 0.1 + 0.2 == 0.3 is not true in Java (see this demo).

So, I'm interested in how equality testing can be implemented for floats. Is there a standardized algorithm?

You cannot meaningfully test floating point values for equality. A floating point value does not represent a real number, it represents a range of real numbers, but it fails to store the width of this interval. All you can do with floating point values is to test them for approximate equality, and it's up to you to define the approximation you're willing to make. You can test whether the difference is smaller than a certain constant ($|x-y| \le \epsilon$), or whether it's relatively small ($|x-y| \le \epsilon \min\{x,y\}$), or something else; the right method and the value of $\epsilon$ depend on the calculation.

There is a seminal article on this topic: the aptly titled What Every Computer Scientist Should Know About Floating Point Arithmetic by David Goldberg [PDF]. Sure, it's long — that shows how difficult floating point is to use, if you care about things like whether 0.1 + 0.2 equals 0.3. And no, there is no magic bullet that would let you sweep the difficulties under the carpet. There is a good, more accessible summary called What Every Programmer Should Know About Floating-Point Arithmetic*, or, Why don’t my numbers add up?

Applications that require exact computations, such as financial computations, do not use floating point. They use integer or fixed-point arithmetic.

Applications that use floating point require a careful, expensive analysis to find out what the uncertainty in the result is. Keep in mind that a floating point value does not really represent a real number $m \cdot 2^e$ nor even a specific interval like $\left[(m-\frac12) 2^e, (m+\frac12) 2^e\right]$, but an interval whose width increases as the computation becomes longer as the uncertainty accumulates.

There is a standard for floating point operations, which most (but not all) systems today implement: IEEE 754 (“IEEE floating point”). This standard defines storage formats, rouding rules, denormalized numbers, etc. It tries to arrange for typical computations to be as precise as possible. Arranging for 0.1 + 0.2 to equal 0.3 is beyond its abilities (that would be possible, but then it would cause 0.2 + 0.3 not to equal 0.5 or some similar misfit).

Some threads on Stack Overflow on this topic:

Is floating point math broken?
Why Are Floating Point Numbers Inaccurate?
Floating point inaccuracy examples
Why does changing the sum order returns a different result?


Quick way to do bit AND mapping By writing out a number in binary I can arrive at the value of taking the first x number of bits out of it.

For example 00001101 (13) taking the first 6 bit would be 3
                          taking the first 5 bit would be 1
                          taking the first 4 bit would be 0 etc

This results, I can easily compute by spelling out the bits that makes up the number I am operating on, take the first couple of bits I am interested in and convert to binary.

I was wondering if there is any common short hand step which allows the same operation to be done, but in decimals (more like how we can do addition on decimals by carrying digits over) where I can use it to calculate what the result of taking the first x bits from a value y would be without having to mentally convert to a binary representation.

If your number $x$ is $n$ bit long, the number formed by the first $k$ is $x/2^{n-k}$, rounded down. The number formed by the last $k$ is the remainder in that division.


Language comprising of Turing machine encodings Let $A$ be the language $\{\langle M\rangle\mid M\text{ is a Turing machine that accepts only one string}\}$

According to my understanding, if a Turing machine is able to decide if another Turing machine will accept only one string, then the halting problem could also be solved. Therefore, $A$ is non-recursively enumerable in my understanding.
Is it correct ?

As the question suggests, it is not too hard to show a reduction from the halting problem (HP) to the language $A$ stated in the question, $HP \le A$.
This means that $A$ is undecidable, $A\notin R$ (also, it is not in co$RE$). But, is it in $RE$ or not?

Lets show that $\overline{HP} \le A$ and conclude that $A\notin RE$.

The reduction goes like that: on input $(\langle M\rangle,x)$ we generate the TM $M_x$ that, on input $w$:

If $w$=$\varepsilon$, ACCEPT.
Run $M$ on $x$. If M halts, ACCEPT (otherwise, we're in a loop anyways)

The reduction is valid: if  $(\langle M\rangle,x) \in \overline{HP}$, then $M$ does not halt on $x$. This means that $M_x$ accepts only the empty string (and loops on any other input). Thus $\langle M_x\rangle \in A$.
On the other hand, if $(\langle M\rangle,x) \notin \overline{HP}$, then $M$ halts on $x$, and $M_x$ accepts any input, thus $\langle M_x\rangle \notin A$.

It is easy to verify that the reduction is computable and complete.


What's the most efficient way to print all paths from root to leaves in a directed graph? I have a directed graph created in matlab. I am trying to print all paths from root to leaves. I used stack to implement my algorithm but it seems very slow when I have large number of nodes and edges.

Is it possible to solve this problem in O(nlogn) time ?

%This is my graph:
output =
   edges: {[0 1]  [0 2]  [1 3]  [1 4]  [1 5]  [2 6]  [3 6]  [2 7]  [3 7]  [4 7]}
vertices: [0 1 2 3 4 5 6 7]

%I am traversing with this code
maximal_sets = {};
stack=java.util.Stack();
stack.push(0);
CP = [];
Q = [];
labels = ones(1,size(output.vertices,2));
while ~stack.empty()
    flag = 0;
    x = stack.peek();
    for e = 1:size(output.edges,2)
        if output.edges{e}(1) == x && labels(output.edges{e}(2)+1) == 1
            flag = 1;
            w = output.edges{e}(2);
            stack.push(w);
            CP = union(CP,w);
            break
        end
    end
    if flag == 0
        Q = [];
        % PRECEDES are leaves of the graph
        if any(PRECEDES{end}==x)
            for v=1:size(CP,2)
                Q = union(Q,CP(v));
            end
        end
        if size(Q,2) > 0
            maximal_sets{end+1} = Q;
        end
        for ed = 1:size(output.edges,2)
            if output.edges{ed}(1) == x
                labels(output.edges{ed}(2)+1) = 1;
            end
        end
        labels(x+1) = 0;
        stack.pop();
        CP = CP(find(CP~=x));
    end
end

for i = 1:size(maximal_sets,2)
    disp(maximal_sets{i})
end

%The paths from root to leaves (not including root which is 0) are listed:
 1     3     7

 1     4     7

 1     5

 2     6

 2     7

This works well with toy examples, but when I have 403 vertices, and 6717 edges. It does not stop. I think it is exponential.

The traversing code was taken from [http://drum.lib.umd.edu/bitstream/handle/1903/4638/TR_87-130.pdf?sequence=1&isAllowed=y] and modified.

In a directed graph with $n$ vertices there may be $(n-2)!$ different simple paths (paths without cycles) between any two vertices. Just consider a complete directed graph. So its running time is $O(n!)$ and hence it is impossible to solve the problem in $O(n\log{n})$.


Balanced Network max flow review I would like a review for my algorithm for the following question:
A flow network is a “balanced network” if for every $v∈V- {s,t}$ it holds that $c_in (v)=c_out (v).$
Let G be a balanced network in which in-degree(s)=out-degree(t)=0
Find max-flow for G.
My Algorithm so far:

We will define the following capacity-function: $∀(u,v)∈E,f(ⅇ)=c(ⅇ)$
Run over the adj. list and update for every edge it to be our function, and return c(e)

I was also wondering how to prove its a max flow in the correctness part
Thank you

The flow defined by you, satisfies both the constraints: a) conservation of flow at each vertex -- by the definition of balanced network and b) the capacity constraint because $f_{e} = c_{e}$ for every $e \in E$. Therefore, it is a valid flow.

It is a max-flow because it is sending the flow of value which is equal to the capacity of the cut $C$ defined as: $\{s\}$ and $V \setminus \{s\}$, i.e. max-flow = $\sum_{(s,u) \in E} c(u,v)$ since there is no incoming edge to $s$. Note that any flow can not exceed the capacity of this cut. This fact follows from the min-cut max-flow theorem. i.e., max-flow $=$ min capacity of an $s$-$t$ cut $\leq$ capacity of cut $C$. Therefore, what we have is a max-flow.


Self study materials for computational complexity theory I will be taking a computational complexity theory course in about a year, and as the reference material will be Computational Complexity A Modern Approach I am more than confident that without a proper preparation that course will eat me alive. The book seems to have excellent practise problems in the sense that it will build up my CS toolbox. But I am going to need extra material to help me to get to a level where I can confidently self study the book in quetion. Therefore I was wondering that does there exist a solution manual for the book or are conference papers my only option to check how the quality of my proofs/work as a hint when I am stuck?

To self-study from Computational Complexity: A Modern Approach, the prerequisites are:

A few courses in algorithms* (you should be comfortable reading and writing pseudocode, using Big-$\mathcal O$ notation, and using abstract data structures like lists, sets and hashmaps)
A course in discrete math
A course which treats Finite State Machines and formal languages** (To the point where you are comfortable drawing and reading finite state machines)
Any course which teaches proofs

Most Bachelor (undergraduate) courses teach all the above. I recommend at least $3$ of the above; the book is written well enough that it remains quite accessible. It does not assume any prior knowledge about complexity classes or Turing Machines.
If you wish to prepare well for a particular course a year in advance, then find out which chapters the course discusses, and read those and then some more, including some exercises (a single-semester course can probably cover less than half the book). Ask the professor which chapters are used, as this changes from one year to the next (Be prepared that the professor has not decided this a year in advance, because she will decide based on what works this year. If she does give an answer, don't treat it as binding or unchanging).
When these requirements are met, my experience is that a big obstacle to overcome is that some students from a CS background have a ``coding mindset" in which, when presented with a problem, they try to solve it with an algorithm. That is not the objective here. Instead, the objective is to understand how different problems relate to each other, and to understand what is the computational power different computational models (e.g. Turing Machines, polynomial-size circuits, FSMs, Turing Machines which use a polynomial amount of memory. And what if they are allowed to flip random coins?). We wish to understand how these two things - problems and computational models - map onto each other. Inevitably, this means proving statements of the form "This problem is too difficult to be solved by that computational model", and "This computational model is more powerful than that one'', and you can't program your way out of that. This is more similar in flavour to abstract algebra, in which one simply tries to comprehend all the groups and rings that are out there; you compare their properties, without trying to code up the multiplication for a particular group.
If you have more time, then read Quantum Computing Since Democritus by Scott Aaronson, because (it is a fun read and) it motivates the questions that are asked in complexity theory.
If you have infinite time, then you can program a SAT Solver; this will help you get familiar with Boolean formulas.
*For example, The Design and Analysis of Algorithms, by Anany Levitin.
**I learned from and recommend Introduction to Languages and the Theory of Computation, by John Martin. It goes all the way from Finite State Machines to Turing Machines. Any book on formal languages should suffice.


address spaces of changing processes I read that the mapping for user-space processes is changed after each process switch. By mapping I mean the translation from virtual addresses to "real" memory address. I thought that processes are loaded into RAM and are held there (that's what the RAM is for). So the addresses in "real" memory addresses shouldn't change too much over time, because the process is held in RAM.

Where am I mistaken?

Processes don’t use real RAM addresses. If they did, virtual memory couldn’t possibly work.

If the data is actually in RAM, then the data of process A at A’s location 1000 is not the same and therefore not stored in the same place as the data of process B at B’s location 1000

So the mapping must change when we switch from process A to process B. Address 1000 must be mapped to different addresses in RAM or not in RAM at all.

And processes are not loaded into RAM, they are loaded into address space, that is a mapping between address space and RAM or virtual memory is set up. This allows having processes larger than RAM and allows switching between processes with large amounts of data quickly.


Not able to convert from NFA to DFA I have a simple problem of making a DFA which accepts all inputs starting with double letters (aa, bb) or ending with double letters (aa, bb), given $\Sigma =\{a, b\}$ is the alphabet set of the given language.
I tried to solve it in a roundabout way by:

Generating a regular expression
Making its corresponding NFA
Using powerset construction to deduce a DFA
Minimizing the number of states in DFA

Step 1: Regular expression for given problem is (among countless others):
((aa|bb)(a|b)*)|((a|b)(a|b)*(aa|bb))

Step 2: NFA for given expression is:

(source: livefilestore.com)
In Tabular form, NFA is:
State    Input:a     Input:b
->1        2,5         3,5
  2        4           -
  3        -           4
 (4)       4           4
  5        5,7         5,6
  6        -           8
  7        8           -
 (8)       -           -

Step 3: Convert into a DFA using powerset construction:
Symbol, State       +   Symbol, State (Input:a) +   Symbol, State (Input:b)
   ->A, {1}         |        B, {2,5}           |        C, {3,5}
     B, {2,5}       |        D, {4,5,7}         |        E, {5,6}
     C, {3,5}       |        F, {5,7}           |        G, {4,5,6}
   (D), {4,5,7}     |        H, {4,5,7,8}       |        G, {4,5,6}
     E, {5,6}       |        F, {5,7}           |        I, {5,6,8}
     F, {5,7}       |        J, {5,7,8}         |        E, {5,6}
   (G), {4,5,6}     |        D, {4,5,7}         |        K, {4,5,6,8}
   (H), {4,5,7,8}   |        H, {4,5,7,8}       |        G, {4,5,6}
   (I), {5,6,8}     |        F, {5,7}           |        I, {5,6,8}
   (J), {5,7,8}     |        J, {5,7,8}         |        E, {5,6}
   (K), {4,5,6,8}   +        D, {4,5,7}         +        K, {4,5,6,8}

Step 4: Minimize the DFA:
I have changed K->G, J->F, I->E first. In the next iteration, H->D and E->F. Thus, the final table is:
  State    +   Input:a     +   Input:b
   ->A     |      B        |      C
     B     |      D        |      E
     C     |      E        |      D
    (D)    |      D        |      D
    (E)    |      E        |      E

And diagramatically it looks like:

(source: livefilestore.com)
...which is not the required DFA! I have triple checked my result. So, where did I go wrong?
Note:

-> = initial state
() = final state

You are fine up to step 3 (the DFA) but your minimization is incorrect.

It's clear that the minimized DFA is not right, because both the inputs ba and ab (which are not in the original language, nor are they accepted by the DFA in step 3) lead to final state E.

Looking at your minimization steps, it seems that you have unified final and non-final states; for example J (final) -> F (not final) and I (final) -> E (not final). Merging a final state with a non-final state changes the language accepted by the automaton, leading to the acceptance of incorrect strings as noted above.


Can a CPU be replaced without interrupting the processes running on it? When I need to replace the CPU of my computer, I turn it off, replace the hardware, then reboot it. But what if you need to replace the CPU (in a single CPU machine) without stopping the processes running on it?

Is that possible, and if so, how?

This is a theoretical question. It doesn't matter if the procedure is complicated and impractical or cost-intensive.

On a multitasking operating system, any process can be paused while other processes are executing. When a process is paused, all of its data is in RAM, outside the CPU. The CPU itself only contains a small amount of data in registers.

On a multiprocessor system, this same mechanism also allows processes (or more precisely threads) to migrate from one processor to another. As long as the processors are connected to the same RAM, a processor switch is no more complicated than a context switch.

The operating system kernel can save the few pieces of data that it normally stores in registers to a fixed place in RAM, and can make its startup code read this data back. All major multiprocessing operating systems can in fact do that: it's called suspend to RAM.

What prevents replacing the CPU during a suspend-to-RAM is not a difficulty with software architecture, but with hardware architecture. It is possible on some expensive servers, but not on a consumer device.

You can actually replace your CPU and restart with your old processes, even on a computer where this requires turning off the power, by using suspend-to-disk. Take all the data in RAM and save it to disk. This is similar to swapping. The kernel needs to do more work, because it has to power down all peripherals and restore their state afterwards. But again there is no extra theoretical difficulty, just a lot of practical difficulties in writing drivers.


Is $(\sqrt{n})!=Θ(\sqrt{n}^{\sqrt{n}})$? I would like to express $(\sqrt{n})!$ in terms of $Θ()$ notation.

My approach is the following:

$$(\sqrt{n})!=f(n)\Leftrightarrow$$
$$\log(\sqrt{n})!=\log(f(n))$$

Now from Stirling's approximation we get: $$Θ(\sqrt{n}\log(\sqrt{n})=\log(f(n))\Leftrightarrow$$
$$f(n)=Θ(\sqrt{n}^{\sqrt{n}})$$

So, $$(\sqrt{n})!=Θ(\sqrt{n}^{\sqrt{n}})$$

Is this approach correct? I am a bit confused since I used $\log$ equality to prove this and in some cases this doesn't work correctly.

For example, if we get $n!$ and $n^{n}$ we observe that $Θ(\log(n!))=Θ(\log(n^{n})$ .

However we know that $n!=o(n^{n})$ (which means that $n!<n^{n}$ asymptotically)

Stirling's approximation states that
$$
n! \sim \sqrt{2\pi n} (n/e)^n = \Theta(\sqrt{n} (n/e)^n).
$$
Therefore $\sqrt{n}! = \Theta(n^{1/4} (\sqrt{n}/e)^{\sqrt{n}})$. In particular, $\sqrt{n}! = o(\sqrt{n}^{\sqrt{n}})$.

Note also that if all you want is to express $\sqrt{n}!$ in big Theta notation, you can just write $\sqrt{n}! = \Theta(\sqrt{n}!)$.

If $\log f(n) = \Theta(\log g(n))$ then it doesn't follow that $f(n) = \Theta(g(n))$. For example, $\log (a^n) = \Theta(\log (b^n))$ for all $a,b > 1$, but $a^n$ is not $\Theta(b^n)$ (unless $a = b$).


What is the time complexity of the following algorithm on graphs Consider undirected graph with $O(n)$ nodes and $O(m)$ edges. We store the edges in adjacent list, so for each node we keep list of the nodes such there exist edge between those nodes.

Our search goes as follows: For each node in the graph (let it be i) we iterate over all pairs of nodes(let it be $n_1 \text{ and } n_2$) such that there is edge between $i \text{ and } n_1 \text{ and between } i \text{ and } n_2$.Let's just analyze the complexity of those iterations.

Here is the pseudo code to make sure everything is understood well

for each node i in graph G:
    for each node n1 in adjacent list of i:
        for each node n2 in adjacent list of i:
            O(1) work here

From first look it looks like $O(n^3)$ since there are three nested loops, however I don't think that this is correct. What is the correct way to analyze the time complexity here?

For every $v$, there are $\binom{n-1}{2}$ pairs in the worst case that need to be checked, since $v$ may be connected up to $n-1$ other vertices.

Since $\binom{n-1}{2} = \Theta(n^2)$, your algorithm performs $O(n^2)$ queries for every vertex. Since there are $n$ vertices, the time complexity is $O(n^3)$ and your analysis is correct.

Suppose we want to express the algorithm cost in terms of $m$.

For every $v_i$, we perform work equal to the number of neighbours over 2 of $v$, denoted by $N_i$. Or $\binom{N_i}{2}$

It is clear that the runtime would be $O(N_1(N_1-1) + N_2(N_2-1) +\dots +N_n(N_n-1))$ $$ = O(\sum_{i=1}^n (N_i)(N_i-1)$$

We know that $\sum_{i=1}^n (N_i) = 2m$, since every arc is counted exactly twice. What is left is to prove
$$\sum_{i=1}^n (N_i)(N_i-1) = O(nm)$$

Since $N_i \leq n-1$ it follows:
$$\sum_{i=1}^n (N_i)(N_i-1) \leq \sum_{i=1}^n (N_i)*n = n\sum_{i=1}^n (N_i) = n*2m=O(nm)$$


Show that $T(2^n) = \Theta(3^n)$ We have a function $T(n)$ defined by $T(1) =1$ and $T(n)=3T(\lfloor n/2\rfloor)+n$ for $n > 1$. We need to show that $T(2^n)=\Theta  (3^n)$.  How should I approach this question? Any suggestion?

First of all, try to solve the recurrence relation using the master method.

Since $f(n) = O(n^{\log_2 3 - \epsilon})$ for some $\epsilon$, this is the first case of the master method. Therefore $$T(n) = \Theta(n^{\log_2 3})$$

If you replace $n$ by $2^n$, you will get your answer. i.e.
$$T(2^n) = \Theta(2^{n\log_2 3}) = \Theta(3^n)$$


Randomizd String Searching I need to detect whether a binary pattern P of length m occurs in a binary text T of length n where m

I want to state an algorithm that runs in time O(n) where we assume that arithmetic operations on O(log2n) bit numbers can be executed in constant time. The algorithm should accept with probability 1 whenever P is a substring of T and reject with probability of at least 1−1n otherwise.

I think fingerprinting could help here. But I can't get it.

The average complexity of the search from the back to the front is equal to
$$
  \sum_{i=1}^n  \frac{2i}{n(n+1)}(n-i+1) = \frac{2}{n(n+1)}\sum_{i=1}^n i(n-i+1) = \frac{2}{n(n+1)} \frac{1}{6}n (n+1) (n+2) = \frac{1}{3}(n+2)
$$
which is indeed linear.


$2k$ number assignment Given $k$ numbers $A_1 \leq A_2 \leq ... \leq A_k$ such that $\sum\limits_{i=1}^k A_i = k(2k + 1)$ is there an assignment of numbers $i_1, i_2, ... , i_{2k}$ which is a permutation of $1, 2, ... , 2k$ such that

$i_1 + i_2 \leq A_1\\ i_3 + i_4 \leq A_2\\ .\\.\\.\\ i_{2k-1} + i_{2k} \leq A_k$

?

I cannot find an efficient algorithm and that solves this problem. It seems to be a combinatorial problem. I was unable to find a similar NP-Complete problem. Does this problem look like a known NP-Complete problem or can it be solved with a polynomial algorithm?

This problem is strongly NP-complete.

Suppose all the $A_j$ are odd. Then we know that since $i_{2j-1} + i_{2j} = A_j$ is odd, one of $i_{2j-1}$ and $i_{2j}$ is even and the other is odd. We can assume that $i_{2j-1}$ is odd and $i_{2j}$ is even. By letting $\pi_j = \frac{1}{2}(i_{2j-1}+1)$ and $\sigma_j = \frac{1}{2}(i_{2j})$, we can show that this is equivalent to asking for two permutations, $\pi$ and $\sigma$, of the numbers $1 \ldots n$ such that $\pi_j + \sigma_j = \frac{1}{2}(A_j+1)$.

This problem is known to be NP-complete; see this cstheory.se problem and this paper of W. Yu, H. Hoogeveen, and J. K. Lenstra referenced in the answer.


Is there a measure of space usage over time? We typically measure algorithm efficiency by space efficiency and then time efficiency e.g. this algorithm takes O(n) time and O(n) space.
However, I feel this does not capture the full story.

Say we have a process that looks like this. Assume memory allocation is O(1) time complexity for simplicity.

process(n):
  mem = allocate(n)
  for 0 to n:
    ... do O(1) stuff
  end
  free(mem)
  end

The above process takes O(n) time and O(n) space.

Here's another process that takes O(n) time and O(n) space.

process(n):
  for 0 to n:
    ... do O(1) stuff
  end
  mem = allocate(n)
  ... do O(1) stuff
  free(mem)

In the both processes you're using O(n) space. In the first one you're using the space over the course of the entire process. In the second, you're using it only at the very end. Is there a way to formalize the difference?

Sure.  Of course, you are absolutely right, that time complexity and space complexity don't capture the whole story.  No one metric is likely to.

There are many ways one could plausibly distinguish between those two programs.  For instance, one could ask about average space usage (averaged over the lifetime of the program).  These metrics might be harder to use, but might be more relevant in some situations.  Only you can know what you want to optimize, so you only you can determine which metric is most suitable for your particular situation.  You might find that asymptotic analysis is not the best tool for the job and instead you want to measure space usage on a real-world benchmark/workload. That is also reasonable.


How is a compiler related to the runtime system? A quick search on the role of compiler brings up the following:

  A compiler is a special program that processes statements written in a
  particular programming language and turns them into machine language
  or "code" that a computer's processor uses.

However, I also read that every language needs to have a target runtime system and programs written in that language execute in the context of the runtime system.

Adding up the two, it appears that a compiler converts programs into bits understandable by the runtime system and the runtime system acts as the agent interpreting the bits, translating them to the processor intructions. Is this correct? If not, how else are compiler and runtime system related?

And if the above is correct, it would imply the following:

two executables compiled from programs with identical logic written
in different languages would not be identical
with people typically installing several programs from disparate sources, an average machine would have to have dozens of runtimes which doesn't seem to be the case.

What am I missing here?

I just looked on my machine (which is running macOS Sierra), and I found four runtime systems for C and C++ alone:

/usr/lib/crt1.10.5.o
/usr/lib/crt1.10.6.o
/usr/lib/crt1.o
/usr/lib/gcrt1.o

They're not huge; only about 10kB each. Small enough that if you statically linked them to a typical program they would barely register. Still, there they are.

I'm certain that I have a bunch of others for different languages, too: Python and Java are fairly standard. Emacs seems to come pre-installed so there's a Lisp-like language. There's probably a Swift runtime if I look hard enough. And, of course, that's not including all the languages I installed myself because I like collecting programming languages.

Many modern operating systems are designed with C in mind (in that their system call APIs are C calls), and many languages with a "foreign function" interface support C natively because so many third-party libraries support a C API. So runtimes for many languages are often built on top of the C runtime.

It's useful to think of a runtime system as some kind of virtual machine. However, many programming languages do compile to machine code, so the job that the runtime system has to do can be as simple as initialisation and shutdown only, with nothing further needed while the program is running.

For example, a typical runtime for C and C++ (they are often shared these days) has to perform the following initialisation before any C code is run:

Set up the C stack.
Initialise any standard library data structures that need to be initialised (e.g. atexit or stdin/stdout/stderr).
Invoke static constructors (e.g. for C++).
Process command-line arguments and environment variables to pass to main().
Call main().

There's nothing here that really corresponds to interpreting the output of the compiler, with the possible exception of information that the compiler generates about static constructors.

Even for compiled languages, however, the runtime may provide subroutines to support source-level operations for which it would be wasteful or inconvenient for the compiler to generate code.

Exceptions in C++ are one example. Another is where some particular platform doesn't have a suitable instruction; many 32-bit platforms don't have a native 64-bit division instruction, but the compiler may still want to support 64-bit integers.


Will a vertex present in the set of vertices present in each basis cycle be present in all the cycles? I read that the XOR of basis cycles can generate all the cycles present in the graph.

I was just wondering if there exists any one vertex which is present in all the basis cycles and is present in all the cycles of the graph.

Can someone point me to something that might help me tackle this problem?

Consider the following graph:

Let $S$ be the set containing the cycles formed by i) the red and black edges, and ii) the blue and black edges. $S$ is a cycle basis in which every cycle contains vertex $x$, yet the cycle formed by the red and blue edges does not contain $x$.

Edit: it is also not true that the existence of a vertex $x$ that lies in all cycles of a cycle basis implies that $x$ belongs to all cycles of the graph. See the following counterexample:

The $3$ cycles that can be formed by taking an edge $e$ of color $c$ for $c \in \{ \mbox{red, green, blue}\}$ along with the two black edges incident to the endpoints of $e$ form a basis $S$. Vertex $x$ belongs to all the cycles in $S$ but it does not belong to the cycle formed by the red, green, and blue edges.


Finding the minimum number of calls in a tree I was asked this question in an interview and struggled to answer it correctly in the time allotted. Nonetheless, I thought it was an interesting problem, and I hadn't seen it before.

Suppose you have a tree where the root can call (on the phone) each of it's children, when a child receives the call, he can call each of his children, etc. The problem is that each call must be done in a number of rounds, and we need to minimize the number of rounds it takes to make the calls. For example, suppose you have the following tree:

   A
  / \
 /   \
 B    D
 |
 |
 C

One solution is for A to call D in round one, A to call B in round two, and B to call C in round three. The optimal solution is for A to call B in round one, and A to call D and B to call C in round two.

Note that A cannot call both B and D in the same round, nor can any node call more than one of its children in the same round. However, multiple nodes with a different parent can call simultaneously. For example, given the tree:

      A
    / | \
   /  |  \
   B  C   D
  /\      |
 /  \     |
E   F     G

We can have a sequence (where "-" separates rounds), such as:

  A B - B E, A D - B F, A C, D G

(A calls B first round, B calls E and A calls D second, ...)

I'm assuming some type of dynamic programming can be used, but I'm not sure which direction to take this in. My initial inclination is to use DFS to order the longest path from the root to leaves in decreasing order, but when it comes to the nodes actually making calls, I'm not sure how we can achieve optimality given any tree, nor how we can output the paths that the optimal calls would make (i.e. in the first example we could output

  A B - B C, A D

You can traverse the tree in postorder and compute for each node the number of rounds that the subtree below that node needs as follows:

If the node is a leaf, the subtree takes 0 rounds.
If the node is not a leaf, sort its children by the number of rounds their respective subtrees take, from longest to shortest. You will traverse them in this order. The number of rounds for the current node is $\max_i\{n_i +i\}$, where $n_i$ is the number of rounds the subtree of the $i$-th child (in sorted order) takes.

Regarding output: The best format depends on what you want to do with the data. Do you need information on which calls happen concurrently? Or do you want to actually implement the calls?
In the latter case, listing the processing order for each node seems like a reasonable format.
In the former case, your format is nice, but probably needs an additional traversal to be obtained.


Is Smoothed Analysis used outside academia? Did the smoothed analysis find its way into main stream analysis of algorithms? Is it common for algorithm designers to apply smoothed analysis to their algorithms?

I could be wrong, but I view smoothed analysis as a way to explain the in-practice behaviour of algorithms that have bad theoretical guarantees (simplex, k-means, and so on). I'm not sure what it would mean to use smoothed analysis in practice, except to justify the use of a particular heuristic with bad worst-case performance ("My heuristic has blah blah worst-case behaviour but a smoothed analysis indicates that it will do well in practice etc etc")


Modeling concurrent algorithms I'm working on a class library (C++) that can be thought of as a producer/consumer queue of producer/consumer queues. There are many queues of data, and the goal is to assign worker threads to process these queues, as needed, using coroutines. At any rate, the details aren't necessarily important to the question, but I'm struggling to wrap my head fully around the synchronization requirements.

I've started with a list of basic operations (like adding an element to the top level queue), along with some preconditions, postconditions, and what I'm calling "exclusions" which are things that are not supposed to happen during the operation. It seems to only scratch the surface though.

Finally, my question: Is there a way to model algorithms (either notation or diagram) that helps to tease out temporal ordering requirements? What needs to be locked when? What transactions need to be atomic? What order can reads/writes be carried out in?

You have mentioned the temporal ordering of events, then you may have known about temporal logic [1] such as LTL [2] and CTL [3]. Temporal logic allows you to reason about time and thus temporal ordering of events. For instance (from [1]), one may wish to say that whenever a request is made, access to a resource is eventually granted, but it is never granted to two requestors simultaneously.

The greatest advantage of using LTL or CTL to express the properties of the system is that you can automatically verify them. This process is known as model checking [4].

There are quite a few of model checkers [5]. For instance, in SPIN, systems to be verified are described in Promela (Process Meta Language), which allows one to specify "atomic blocks" (Is this your intention of What transactions need to be atomic?)?

As for the producer/consumer problem, it has been extensively studied in the context of model checking. This lecture note uses it as an example for SPIN (you can easily find other resources). In addition, [6] verifies an edition written in SystemC, and [7] verifies it using TLA+.

[1] temporal logic (wiki)

[2] LTL (wiki)

[3] CTL (wiki)

[4] model checking (wiki)

[5] model checkers (wiki)

[6] Verifying SystemC: a Software Model Checking Approach

[7] An Example of Debugging Java with a Model Checker (web page)


Error in the use of asymptotic notation I'm trying to understand what is wrong with the following proof of the following recurrence

$$
T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n
$$
$$
T(n) \leq 2\left(c\left\lfloor\frac{n}{2}\right\rfloor\right)+n \leq cn+n = n(c+1) =O(n)
$$

The documentation says it's wrong because of the inductive hypothesis that
$$
T(n) \leq cn
$$
What Am I missing?

Let's say the final goal is to prove $T(n) = \mathcal{O}(n)$. You start with the induction hypothesis:

$T(i) \leq ci$ for all $i < n$.

And to complete the proof, you have to show that $T(n) \leq cn$ as well.

However, what you're able to deduce is $T(n) \leq (c+1)n$, which is not helpful to complete the proof; you need one constant $c$ for (almost) all $n$. Therefore, we cannot conclude anything and $T(n) = \mathcal{O}(n)$ isn't proved.

Notice that you are confused between the result and the proof process. And one more point, $T(n)$ is actually $\Theta(n \log n)$ in this case so you may consider an appropriate induction hypothesis to be able to prove it.


Proof that n^2 = O(logn)? DEFINITION: $f = O(g)$ if positive integers c and $n_0$ exist such that for every integer $n$ $\geq$ $n_0$, $f(n) ≤ c·g(n)$

so:

$n^2 \leq c·log(n)$

$\frac{n^2}{log(n)} \leq c$

is this enough proof? since the fraction will grow larger and larger depending on n>1, so its false?

This is not "enough proof". The main problem of your proof is that it just lacks words. A proof should explain what you have in your head. So the first thing is to clearly states what you want to prove.

  We want to prove that $n^2$ is not $O(\log n)$.

Then you have to explain how you will do it:

  Assume toward a contradiction that $n^2=O(\log(n))$.

So you are going to do derive a contradiction from this assumption. We just apply definitions.

  By definition, it means that there exists $c, n_0$ such that for every $n \geq n_0$, $n^2 < c \log n$, that is, ${n^2 \over \log n} < c$.

Now you need to explain why this is absurd. There are many ways of doing it depending on what you assume the reader to be familiar with. One way to go is the following:

  It is well known that $\lim_{n \rightarrow \infty}{n^2 \over \log n} = \infty$. Thus, there exists $n_1 \geq n_0$ such that ${n_1^2 \over \log n_1} \geq c$, contradicting the initial assumption.

Now, you conclude:

  Thus, $n^2$ is not $O(\log n)$.

If you think your reader is not familiar enough with limits you can then go more into details:

  We know that for every $n \in \mathbb{N}$, $\log(n) \leq n$. Tus, $n = {n^2 \over n} \leq {n^2 \over \log n}$. Thus, $n_1 = \max(n_0,c)$ verifies both $n_1 \geq n_0$ and $c \leq n_1 \leq {n_1^2 \over \log n_1}$ which contradicts the intial hypothesis.


Matrix chain multiplication recurrence and its solution We want to calculate $A_1 \times A_2 \times \cdots \times A_n$, where $A_i$ has dimensions $d_{i-1} \times d_i$.
In the classical matrix chain multiplication problem, we wish to minimize the total number of scalar multiplications. In this problem, we consider the all intermediate matrices arising in the computation (including the final result but excluding the original matrices), and the cost of a specific order is the maximal number of entries of such an intermediate matrix. As usual, we want to minimize the cost.
As an example, if $n = 2$ the answer is simply $d_0d_2$, and if $n = 3$, then there are two orders:

$(A_1A_2)A_3$, in which the intermediate matrices are $A_1A_2,A_1A_2A_3$. The cost is therefore $\max(d_0d_2,d_0d_3)$.
$A_1(A_2A_3)$, in which the intermediate matrices are $A_2A_3,A_1A_2A_3$. The cost is therefore $\max(d_1d_3,d_0d_3)$.

Denote by $C_{ij}$ the optimal cost of multiplying $A_i,\ldots,A_j$. We can write the following recurrence for $C_{ij}$:
$$C_{ij}=\min_{i \leq k <j} \max \{C_{i,k},C_{k+1,j},d_{i-1}d_j\},$$
with base case $C_{ii} = 0$.

How do we get this recurrence?

We get the recurrence by considering all possible ways of breaking up $A_i \times \cdots \times A_j$.
Specifically, we consider $(A_i \times \cdots \times A_k) \times (A_{k+1} \times \cdots \times A_j)$ for all relevant values of $k$, which are $i,\ldots,j-1$.


How to define a path between two sets of vertices? In section 17.2 of the book "Combinatorial optimization polyhedra and efficiency" by Schrijver, he describes the Hungarian method for maximum weight matching in bi-partite graphs (with classes $U$ and $W$). He defines for a matching, $M$, $U_M$ and $W_M$ as the set of vertices in $U$ and $W$ missed by $M$. He then says "if there is a $U_M - W_M$ path, find the shortest such path". I'm not sure what this means. How is a path between two sets of vertices defined?
He is describing this path on a directed graph, $D_M$ where all edges in $M$ are directed from $U$ to $W$ and edges not in $M$ are directed from $W$ to $U$.

An $A$-$B$ path is a path that starts at some $a \in A$ and ends at some $b \in B$.


How do I design a DP algorithm to count the minimum amount of continuous palindromic subsequences in sequence? Taking a sequence, I am looking to calculate the minimum amount of continuous palindromic subsequences to build up such a sequence. I believe the best way is using a recursive DP algorithm.

I am having trouble picturing the problem space or the most efficient way to do it. (For example, is it best to find the longest palindromic continuous subsequence first, or rather find the earliest one first?)

For example:

Sequence: [A, C, C, C, A, B, Y, B] is made up from 2 subsequences, namely [A, C, C, C, A], [B, Y, B]

So, therefore, my output for this example would be 2.

Thanks in advance!

Let $S$ be your input sequence and denote by $S[i:j]$ the subsequence going from the $i$-th to the $j$-th element of $S$ (inclusive).

Let $OPT[i]$ be the minimum amount of continuous palindromic subsequences in which $S[1:i]$ can be partitioned. Let $OPT[0]=0$. For $j=1,\dots,|S|$, you have:

$$
OPT[j] = \min_{\substack{i=1,\dots,j\\S[i:j] \text{ is a palindrome}}} \{1+ OPT[i-1] \}.
$$

The value you are looking for is $OPT[|S|]$. This algorithm requires time $O(|S|^2)$. Notice that all the pairs $(i,j)$ for which $S[i:j]$ is palindrome can be precomputed in $O(|S|^2)$ time.


Clarification with Kuhn-Munkres/Hungarian Algorithm I have been attempting to get my mind around the Kuhn-Munkres/Hungarian Algorithm. I have been using the following statement of the algorithm which I found here.

Based on my readings on the algorithm, my understanding is that the improvement of the feasible vertex labeling in step 2. is supposed to be such that $G_l \subset G_l'$.

The part I'm getting stuck on is that it seems to me that it is possible for there to be an edge $xy$ in $G_l$ with $y \in T$ but $x \not \in S$ resulting in the fact that
$$
l'(x) + l'(y) = l(x) + (l(y) + \alpha_l) \not = w(xy)
$$
and so $ xy \not \in G_l'$ and $G_l \not \subset G_l'$.

Can anyone point out where I'm going wrong?

You are right that $G_{l'}$ is not necessarily a superset of $G_l$. However, you can still prove that the algorithm runs in strongly polynomial time. You have the following invariants:

all edges in $M$ remain edges of $G_{l'}$
we don't remove vertices from $S$ and $T$ until we increase the size of the matching $M$, at which point $S$ and $T$ are reset (step 1); so the size of $S$ and $T$ is monotonically increasing until the size of $M$ is increased by 1
after updating the labels to $l'$, the size of $T$ is increased by at least 1 in the next step

What can you conclude from this? The size of the matching $M$ never decreases. At each iteration we either increase the size of $T$, or we update the labels, which will cause us to increase the size of $T$ in the next iteration. So after $2n$ iterations, the size of $T$ will be $n$. Since $T$ cannot grow anymore, we will have to increase the size of $M$. But the size of $M$ is at most $n$, so the algorithm will finish after at most $O(n^2)$ iterations. An iteration can be executed in time $O(m)$, so the total running time is bounded by $O(n^2m)$.

BTW the sets $S$ and $T$ are a bit mysterious in this description of the algorithm. Here is how we usually think about them. Orient all edges in $G_l$ as follows: the edges in $M$ go from $Y$ to $X$ and all other edges go from $X$ to $Y$. Then $x$ is an unmatched vertex, $T$ is computed to be the set of vertices in $Y$ reachable from $x$ by a directed path, and $S$ is the set of vertices in $X$ reachable from $x$ by a directed path. If $T$ contains an unmatched vertex, we have found an odd-length alternating path, and we can augment the matching (increase its size by reversing the direction of the edges along the path). Otherwise, we can change $l$ so that the size of $T$ increases.


What is the equation for a spiral path in 3D? I am developing games in Unity 3D. Currently, I am trying to place 3D objects in 3D space in a spiral pattern that looks like one of 2 the strands in a pair of the DNA (helix) spiral pattern.

Would anyone please show me the equation for 3D spiral patterns, which should involve X, Y, and Z coordinate ?

Thanks.

I have just found this correct answer on the web (by someone else):

A helix is a circle that moves up with time.  Hence, the equations for one helix are:

x(t) = sin t

y(t) = cos t

z(t) = t

A double helix include two helices that are offset by half a turn.  So, the equations for the second helix would then be :

x(t) = sin t

y(t) = cos t

z(t) = t + \pi


Why don't compilers automatically insert deallocations? In languages like C, the programmer is expected to insert calls to free. Why doesn't the compiler do this automatically? Humans do it in a reasonable amount of time(ignoring bugs), so it is not impossible.

EDIT: For future reference, here is another discussion that has an interesting example.

Because it's undecidable whether the program will use the memory again. This means that no algorithm can correctly determine when to call free() in all cases, which means that any compiler that tried to do this would necessarily produce some programs with memory leaks and/or some programs that continued to use memory that had been freed.  Even if you ensured that your compiler never did the second one and allowed the programmer to insert calls to free() to fix those bugs, knowing when to call free() for that compiler would be even harder than knowing when to call free() when using a compiler that didn't try to help.


Finding a unambiguous grammar As an exercise we were supposed to find a grammar $G$ that generates language $L(G) = \{w \in \{a,b\}^* \mid  |w|_a = |w|_b\}$.
That was not so hard, I found a grammar which I think is correct:

$S \longrightarrow bA \mid aB$

$A \longrightarrow a \mid aS \mid bAA$

$B \longrightarrow b \mid bS \mid aBB$

Though then I found out that this grammar is ambiguous.

So the question is, is there any context free grammar generating language $L$ that is not ambiguous? I've read that there is no algorithm to determine whether a grammar is ambiguous. So if there is such grammar, how can we prove it is? Or is there any way to transform my grammar $G$ to become unambiguous?

You can get an unambiguous grammar by thinking of words in $L$ as walks that start and end on the Y axis; each $a$ corresponds to a move $\nearrow$, and each $b$ corresponds to a move $\searrow$. Each such walk can be decomposed into segments of the form $\nearrow \cdots \searrow$ and $\searrow \cdots \nearrow$ which only touch the Y axis at the endpoints. Moreover, this decomposition is unique.

In turn, in a walk of the form $\nearrow \cdots \searrow$, the $\cdots$ part is itself a concatenation of walks of the same form, and this decomposition is unique. Alternatively, if you convert $\nearrow \mapsto ($ and $\searrow \mapsto )$, then walks of the form $\nearrow \cdots \searrow$  become valid strings of balanced parenthesis, surrounded by a pair $()$.

Putting everything together, we get the following unambiguous grammar:
$$
\begin{align*}
&S \to AS \mid BS \mid \epsilon \\
&A \to a X b \\
&X \to AX \mid \epsilon \\
&B \to b Y a \\
&Y \to BY \mid \epsilon
\end{align*}
$$
Actually proving that this grammar generates $L$ and that it is unambiguous is tedious, and left to you.


Deriving epsilon with a context free grammar with epsilon rules The below problem is from my Formal Languages class. The professor suggested drawing derivation trees for the language until we reach epsilon in all the leaves, and that it should begin to look like a geometric series. But I'm still having trouble getting started.

The way it was explained: if a context free grammar G contains epsilon rules and can reach epsilon, then show that it does so in N replacements, where N is <= the sum of a geometric series. What's the proof for showing an implication like this?

Here's an example to get you started. Suppose our grammar had productions
$$
S\rightarrow TT\qquad T\rightarrow UU\qquad U\rightarrow \epsilon
$$
so $l=2, m=3$.

Then, how fast can you get from $S$ to $\epsilon$? Clearly, it'll take 7 steps:
$$
S\Rightarrow TT\Rightarrow UUT\Rightarrow UUUU\Rightarrow UUU\Rightarrow UU\Rightarrow U\Rightarrow \epsilon
$$
Notice that $(l^m-1)/(l-1)=(2^3-1)/(2-1)=7$.

What does the parse tree for this derivation look like? In particular, how many leaves will it have?

Now generalize this construction.


Covering a polygon with n circular rings Question 1: Why we can/can't solve the following problem using a geometric constraint solver?
Question 2: Is there any algorithm to solve this problem?
Question 3: Can we reduce this problem into some known computational problems?

Input:
1. $C_1, ..., C_n$: Centres of $n$ circular rings.
2. $S$: A polygon of arbitrary shape in the 2D plane.

Notations:
1. $(OR_i, IR_i)$: outer radii and inner radii respectively for circular ring $i$
2. $R = \text{ring}_1 \cap \dots \cap \text{ring}_n$: the intersection of the rings (i.e., the region of space formed by their intersection: the set of points that are contained in all $n$ of the rings)

Output:
Find $(OR_1, IR_1),..., (OR_n, IR_n)$, such that region $R$  covers the polygon $S$ with minimal error area.

Error area is defined as:
$$\text{Area}(S - R) + \text{Area}(R -S)$$

Intuitively, I want an algorithm to find optimal $(OR, IR)$ for each ring to cover a given shape $S$, so the error area (the parts of $R$ outside the given shape: [$\text{Area}(R - S)$] + the parts of the shape not covered by $R$:  [$\text{Area}(S - R)$]) is minimal.

The problem differs from this problem in following ways:

The polygon should be covered by the ring formed by two circles with same centre.
This is a simpler problem in the sense that it has fewer variables. The position of the centres are given; we only need to find the inner and outer radii.

This problem might be hard to solve exactly.  I would suggest you try gradient descent (or another mathematical optimization technique).

[ The stuff below here is obsolete, now that the question has been edited to change the problem statement along these lines. ]

Note that minimizing your error ratio is equivalent to minimizing

$$\text{Area}(S-R) + \text{Area}(R-S),$$

since $S$ is given (so $\text{Area}(S)$ is fixed).  This observation does not seem to help very much, though.


Trie sorting based on word frequency Given a trie with word occurrences (frequency), how can we sort the words( both ascending and descending) on the basis of their frequency?

As the comments say, the basic trie will not help with this task. So I'll propose a special trie for this task. It is the same in every way to normal trie except the "end-of-word" (EOW) nodes (Note that these are not necessarily leaf nodes as words may overlap, e.g. "the" and "theory").

Forget the trie for a moment and imagine all words of frequency 1 in a linked list. Now imagine we have multiple linked lists for each frequency. Now we have $k$ linked lists if there are $k$ distinct frequencies. We can chain these links together, in order of frequency, to create a linked list of linked lists. You could imagine something like this:

We will try to add this same idea into the EOW nodes in the trie without messing up the trie structure. It will be similar, but we will also need every EOW node to point to the sentinel node of their respective frequency list. We will have the following properties in the EOW nodes:

head - head (or sentinel) of this frequency list.
next - next EOW node in this frequency list.
prev - previous EOW node in this frequency list.
frequency - frequency of the word that ends at this EOW node.

The sentinel node will also have a next_head and prev_head field to go to the next and previous frequency list. Similarly the empty root of our trie will act as a sentinel to the first frequency list (i.e. root.next_head is frequency_list_1.head). It will look something like this:

Now we just need to modify the insertion procedure a little bit to accommodate these changes. Specifically the changes will occur when we reach the EOW node. I had started writing the changes out in pseudocode but it became a bit cumbersome. So there are probably easier ways to do this. The idea still is the same. Insertions should only increase by $O(1)$ operations because you'll never have to move a node more than one frequency list at a time, and if you have the necessary pointers this is fine. From there it's as simple as iterating over the list of lists of EOW nodes.

Analysis:

Let the words be a set $S$ of $n$ words and $k$ unique words (apologies for reusing $k$, this is different than the first $k$ we define).

Then we have that the insertion time for all words will be $O(sum\{|S_i|\})$. Or if we say $m$ is the length of the longest word, then it is $O(m \cdot n)$. Then after insertions getting the frequencies in order is $O(k)$ and $O(n)$ for the simple traversal.


What kind of order is binary tree ancestry? Let isAncestor be a relation on binary tree nodes such that isAncestor x y means y can be reached from x in n steps from parent to child, where n may be zero. It is clear from this definition that isAncestor is a partial order. (Two nodes are mutual ancestors if and only if they are identical, and ancestors of ancestors are also ancestors.)

But on a second reflection, isAncestor is not just a partial order. For instance, it has the property forall x y z, isAncestor x z -> isAncestor y z -> ( isAncestor x y \/ isAncestor y x ), which I don't think is common to all partial orders.

Is there a kind of order that precisely designates isAncestor? Since binary trees are extensively studied in CS, I'm guessing there must be a name and a well known set of properties for this kind of relation.

Your condition is almost equivalent to the statement that the partial order is a tree.

Consider the following two conditions on a partial order $\ge$:

C1: There exists a top element $r$ (also called "the root") such that $\forall x . r \ge x$.

C2: For all $x,y,z$, $x \ge z \land y \ge z$ implies $x \ge y \lor y \ge x$ (this is your condition).

Notice that every tree satisfies both conditions (i.e., its isAncestor partial order satisfies both of these conditions).

Moreover, I claim that every partial order that satisfies both of these conditions has a Hasse diagram that is a tree.

Why?  Well, if C1 is true, then C2 is equivalent to

C3: For all $v$, there is a single unique path from $v$ to the root $r$ in the Hasse diagram of $\ge$.

This is easy to prove by looking at the contrapositive: if there were two incomparable paths from $v$ to the root, then we could find a violation of C2 (let $x,y$ be two incomparable elements, each on one of the paths).

And if C1 and C3 is true, then the Hasse diagram is a tree.

Bottom line: there's no particular reason to expect any special name for your property.  Your property almost characterizes trees, once we take into account the correspondence between a partial order and its Hasse diagram (which is a DAG).


Quantum oracle in Grover's problem? Here's the exact problem I'm having with Grover's search algorithm.. Given a function f:{0,...,N-1} -> {0,1}, Grover's problem is to find x such that f(x)=1, provided that there exists such x.

The phase inversion step: Invert the phase of the "key value".

So my question is, when we can already distinguish the key from the others, there is nothing to solve. Why do we need to solve the problem at all when we can already separate the key value? I am missing a point here but I don't understand what it is.

Many thanks for your help.

When computing the oracle in Grover's algorithm, you prepare a qubit entangled with the search register such that the qubit is ON in the parts of the superposition where the search register contains a satisfying solution and OFF in the other parts of the superposition. This is not hard to do: you just use any old circuit that would determine if a given input was a solution, and apply that to the search register.

By preparing the solution qubit, applying a Z gate to it, then uncomputing the solution qubit, you negate the parts of the superposition corresponding to solutions. Having that qubit available is not the same thing as finding a solution. For example, if you measured it you'd almost always get an OFF result and find that your search register contained a non-solution. But, by using the prepared qubit as a tool to negate the phase of the solution space, Grover's algorithm can set up a gradual rotation towards the solution space.

More information: http://algassert.com/post/1719