How to optimize Dijkstra's algorithm for a grid graph? I'm trying to apply Dijkstra's algorithm to the Problem 83 on projecteuler.net. The problem reads:

  In the 5 by 5 matrix below, the minimal path sum from the top left to
  the bottom right, by moving left, right, up, and down, is indicated in
  bold red and is equal to 2297.

131   673   234   103    18
201    96   342   965   150
630   803   746   422   111
537   699   497   121   956
805   732   524    37   331

  Find the minimal path sum, in matrix.txt (right click and 'Save
  Link/Target As...'), a 31K text file containing a 80 by 80 matrix,
  from the top left to the bottom right by moving left, right, up, and
  down.

I wonder if the original algorithm can be simplified due to the fact that the graph is represented as a matrix?

In particular, I've noticed that every edge in the graph is only relaxed once (i.e. the node's distance is changed only once from infinity to some value). Can I rely on this fact in my code?

I am in love with Project Euler so that I am glad to see questions regarding it here. Be aware, however, that getting hints is somehow forbidden (note the italics :) ). The following is taken from the About page once you login:

I learned so much solving problem XXX so is it okay to publish my solution elsewhere?

It appears that you have answered your own question. There is nothing quite like that "Aha!" moment when you finally beat a problem which you have been working on for some time. It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, however, that will not be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.

So I hope to provide a useful answer to your question while I honor the statement above ...

Regarding your first question the answer is No. There is nothing particularly interesting from the fact that you have a matrix. I see this more a matter of convenience for posting the problem than for finding the solution. I think I am not uncovering any interesting observation here since the same technique for solving this problem can be applied to arbitrary graphs.

Regarding your second question, you are right if you apply Dijkstra directly in a forward manner (ie., from the top left corner to the bottom right corner) but you have then a problem, and this is that the number of paths grows exponentially. Be sure that this problem can be solved in less than a second, ... So you should try something slightly different. Do not give up, I can see you are on the right path, so keep up pushing ...

And that's all I should say to respect the pleasure you'll get when solving this problem. Your "Aha!" moment :)

Hope this helps,


A question regarding definition of Deterministic Subexponential Time (SUBEXP) First Look at the definition of SUBEXP from Complexity Zoo:

SUBEXP: (Deterministic Subexponential-Time)
The intersection of DTIME($2^{n^\epsilon}$) over all $\epsilon$>0. (Note that the algorithm used may vary with $\epsilon$.) or it can be written as: SUBEXP = $\bigcap_{\epsilon>0}$DTIME$(2^{n^\epsilon})$.

So, I bring the definition of EXP which is:

EXP = $\bigcup_{k\geq 1}$DTIME$(2^{n^k})$

The definition of EXP is clear, since it includes all polynomial of n to the power of 2. (e.g. $2^{n^{30}}$ or $100^{n^{99}}$ etc.)
First question: what is domain of $\epsilon$? I guess it is between 0 and 1 but it didn't specify in the definition. Is it usual that when we have $\epsilon$ then it means between 0 and 1.
Second question: Now, in case of SUBEXP, it is not clear how the definition is about the intersection? I mean, Shouldn't be written as following: $\bigcup_{1>\epsilon>0}$DTIME$(2^{n^\epsilon})$. For example by definition above what is the intersection of: $2^{n^{0.01}} \bigcap 2^{n^{0.02}} ?$
Third question: There are two definition of SUBEXP in wikipedia, Is there definition that take over all subexponential or we don't since this is why we have two definitions.
Thank you!

In the definition of SUBEXP, $\epsilon$ ranges over all positive reals. But you get the same definition if you ask that $\epsilon < \epsilon_0$, for an $\epsilon_0>0$ of your choice; if you ask that $\epsilon$ be rational; if you only go over $\epsilon = 1/n$; and so on. This is because DTIME is monotone: if $f \leq g$ then $\mathsf{DTIME}(f) \subseteq \mathsf{DTIME}(g)$.
An alternative definition of SUBEXP would be:
$$
\mathsf{SUBEXP} = \bigcup_{g(n) = o(1)} \mathsf{DTIME}(2^{n^{g(n)}}),
$$
often denoted simply by $\mathsf{DTIME}(2^{n^{o(1)}})$.
Some examples: $\mathsf{P} \subseteq \mathsf{SUBEXP}$; a function which can be computed in time $2^{n^{1/\log\log n}}$ is in $\mathsf{SUBEXP}$; and a function which can be computed in time $2^{\log^{10} n}$ is in $\mathsf{SUBEXP}$.
In contrast, a function which can be computed in time $2^{n^{1/10}}$ is not necessarily in $\mathsf{SUBEXP}$ (and by the time hierarchy theorem, there is such a function which lies outside $\mathsf{SUBEXP}$).
A function in $\mathsf{DTIME}(2^{n/\log n})$ lies in SUBEPT but not necessarily in SUBEXP.


What are the real world applications of set cover problem? I am studying about set cover problem and wondering that which problems in real world can be solved by set cover. I found that IBM used this problem for their anti-virus problem, so there should be many more others that can be solved by set cover.

Set-cover heuristics are used in random testing ("fuzz testing") of programs.  Suppose we have a million test cases, and we're going to test a program by picking a test case, randomly modifying ("mutating") it by flipping a few bits, and running the program on the modified test case to see if it crashes.  We'd like to do this over and over again.  If we do this naively, it will be less effective than it could be: typically many test cases cover basically the same code paths, but a small minority of test cases cover unusual code paths that would be interesting to test more intensively.

So, here's one solution that is used in industry.  We use a coverage measurement tool to instrument the program and record which lines of code are covered by each of the million test cases.  Then, we choose a small subset $S$ of those million test cases that has maximal coverage: every line of code covered by one of the million test cases will be covered by some test case in $S$.  $S$ is called a reduced test suite.  We then apply random mutation & testing to the reduced test suite $S$.  Empirically, this seems to make random testing more effective.  The smaller $S$ is, the more effective and efficient testing becomes.

So, how do we choose a reduced test suite $S$ that is as small as possible, while still achieving maximal coverage?  Answer: that's a set cover problem, so we use standard heuristics/approximation algorithms for the set cover problem.  The standard greedy approximation algorithm is typically used for this purpose.


Finite substitution and regular closure properties I'm not sure if I get the following definition right:

1.Def: A map $\varphi: \Sigma^{*} \rightarrow 2^{\Delta^{*}}$ is called Substitution iff:

$\forall u,v \in \Sigma^{*}: \varphi(uv)=\varphi(u) \varphi(v)$
$\varphi(\epsilon)=\{\epsilon\}$

My assumption: every string in $\Sigma^{*}$ with the size $>0$ maps to a Language from $\Delta^{*}$.

such as:

$\Sigma := \{a, b\}$, $\Delta:=\{0,1\}$

$\varphi(a) = \{01^{i}0 |i \in \mathbb N \}$, $\varphi(b) = \{w\in \Delta^{*} ||w|_{0} \neq |w|_{1}\}$

$\varphi(ab) = \varphi(a)\varphi(b)=\{01^{i}0w |i \in \mathbb N \land w \in \Delta^{*} |w|_{0} \neq |w|_{1}\}$

example strings: 001, 000, 0101, 01011, 010100, ...

My first question: Is this assumption and example right?

2.Def: $\varphi$ is finitie iff $\varphi(a)$ $\forall a \in \Sigma$ is a finite subset of $\Delta^{*}$

My assumption: $\Delta^{*}$ is every possible string over the alphabet $\Delta$ and an finite subset would be a limited set $X \subseteq \Delta^{*}$  $|X| < \infty$

I would now implie that my first example is not a finite substitution, because a and b are not mapping to finite sets.

an example could be:

$\varphi(a) = \{10^{i}1 | i \in \{1,...,100\}\}$, $\varphi(b) = \{\epsilon\}$

$\varphi(bba) = \varphi(b)\varphi(b)\varphi(a) = \{\epsilon\}\{\epsilon\}\{10^{i}1 | i \in \{1,...,100\}\}=\{10^{i}1 | i \in \{1,...,100\}\}$

now I can implie that the class $REG$ is closed under finite substitution, because a concatenation of finite sets is finite and every finite set is regular.

My second question: Is this my assumption about finite substitution and the closure propierty right?

You seem to have understood the operation of substitution. That maps any string into a language by concatenating the images of the letters.

Your argument that regular languages are closed under finite substitution does not work. Even if the substitution maps avery word into a finite language, the substitution of a regular language usually is infinite as the initial ragular language is infinite.

A possible approach is to use regular expressions.


In terms of the multiplicative constant, what comparison algorithm is fastest in average complexity? It is well-known that there is an asymptotic lower bound of $nlogn$ for comparison sorting. However, I am wondering what is the fastest known algorithm for comparison sorting, in terms of the multiplicative constant?

The "multiplicative constant" is quite a bit more complex, the real average time for e.g. quicksort is $a n \log n + b \log n + c n + d$ for some constants that depend on the exact cost of comparisons (and thus the layout of the elements), memory access (again, data layout related), machine architecture, how smart the compiler is, ...

To get real average time, you need to know the distribution of possible inputs. Most analysis is done assuming all possible inputs are equally likely, but some experiments have shown that sorted (or almost sorted) data is very likely. In that case, it turns out lowly insertion sort beats all, at $O(n)$.

Do you worry about worst time? Sorry, you can't grab the on average fastest quicksort, and have to fall back on much, much slower heapsort or mergesort variants.

If you want a complete answer to your question, go check Knuth's "The Art of Computer Programming", volume 3 (Sorting and Searching). Some 800 pages of heavy going math for your enjoyment.


If the parent in a bridge is the root, is it a bridge cut node? I am going through Professor Skiena's textbook and he says that there are 3 types of cut-nodes - root, bridge cut node, and parent cut node.

Now if the earliest reachable ancestor from a node is itself, it's parent and the node (if not leaf) become bridge cut nodes.

My question is that we have a simple 2-node undirected graph -> A --- B.

In this case, B's earliest reachable ancestor is B itself and hence A becomes the bridge cut node. However, I am unsure that should be the case; since if I delete A, even then B exists and the num_components = 1?

By definition, a graph that has only one vertex is connected.

That's to say if you delete A, the graph B is still connected. Clearly, A is not a cut-node because it can't disconnect the graph. So is vertex B.

A vertex is a parent/bridge cut-node if and only if it is not root vertex.

The concepts of these three types of cut-node are introduced by Skiena's in his own book, so these concepts are not very rigorous. An errata list may be a good supplement.


What is the difference between Big O, Omega, and Theta? I know that this question is asked a lot of time but I don't understand or I think, I got lost when I was reading Introduction to algorithms
They said, "It is not contradictory, however, to say that the worst-case running time of insertion sort is Omega(n^2), since there exists an input that causes the algorithm to take Omega(n^2) time.".
I read many articles that Omega is the best-case. As I understand correct me if I'm wrong, that the best-case is Omega notation and why they said, "since there exists an input that causes the algorithm to take Omega(n^2) time.", I don't understand why they called it worst-case and why I can call it Omega(n^2), isn't Big O for worst-case.
Also I don't understand they said, "Theta is notation is a stronger notion than Big O".
Why is that? and When should I call an algorithm that it's Big O of whatever, Theta or Omega?
Because I'm confused and I don't know which one is for or how to use them.

Check the definitions, e.g. in Hildebrand's Introduction to asymptotics. In a nutshell, for the usual computer science use for running times (all relevant functions positive), it is said that:

$f(n) = O(g(n))$ if there are $n_0$ and $c > 0$ so that for all $n \ge n_0$ it is $f(n) \le c g(n)$
$f(n) = \Omega(g(n))$ if there are $n_0$ and $c > 0$ so that for all $n \ge n_0$ it is $f(n) \ge c g(n)$
$f(n) = \Theta(g(n))$ if both $f(n) = O(g(n))$ and $f(n) = \Theta(g(n))$.

Note that the last implies two possibly different $n_0$ values, and different values for $c$ (one each for $O$ and $\Omega$).
Informally, $O(\cdot)$ gives an upper bound, $\Omega(\cdot)$ gives a lower bound, while $\Theta(\cdot)$ gives a sharp bound.
Some examples:
$\begin{align*}
   n
     &= O(2^n) \\
   (3/2)^n
     &= \Omega(n^3) \\
   n^2 (\sin n + \cos n)
     &= \Theta(n^2)
\end{align*}$}
There are functions that don't have a simple expression, like:
$\begin{align*}
   f(n)
     &= \begin{cases}
           n^2 & n \text{ odd} \\
           n^5 & n \text{ even}
        \end{cases}
\end{align*}$
Here clearly $f(n) = \Omega(n^2)$ and $f(n) = O(n^5)$, both best possible among functions $n^\alpha$; there is no simple $g$ so that $f(n) = \Theta(g(n))$.
Lower and upper bounds don't need to be "best possible" in any sense. Often people take great care to get best bounds, but they aren't implied in the notation at all.
To use $\Omega$ to mean best case and $O$ for worst case is misleading at best. For example, the best case for bubblesort on an array of $n$ elements is $\Theta(n)$ (bounded below and above by a linear function in the number of elements; when sorting an already sorted array it does one pass over the data), it's worst case is $\Theta(n^2)$ (if the data are in reverse order). We could say it is $\Omega(n^{1/2})$ and $O(n^3)$ as well, both valid for best and worst cases.


Why does the Java grammar have a StatementExpression that resolves to just Expression? Why have this and other redundant rules in the grammar? I'm looking at the following grammar rules for the Java language described on the Oracle docs:
Statement:
    ...
    if ParExpression Statement [else Statement]
    StatementExpression ;
    ...

StatementExpression:
    Expression

ParExpression:
    ( Expression )

I don't understand why the StatementExpression rule is present at all. I also don't understand why ParExpression had to be written as a separate rule.
Why couldn't the grammar just look like the following?
Statement:
    ...
    if ( Expression ) Statement [else Statement]
    Expression ;
    ...

StatementExpression is described in the same specification document as Expression Statements.
I would like to quote this passage specifically:

Certain kinds of expressions may be used as statements by following them with semicolons.
ExpressionStatement:
    StatementExpression ;

StatementExpression:
    Assignment
    PreIncrementExpression
    PreDecrementExpression
    PostIncrementExpression
    PostDecrementExpression
    MethodInvocation
    ClassInstanceCreationExpression

and this:

Unlike C and C++, the Java programming language allows only certain
forms of expressions to be used as expression statements.

ParExpression is described as Parenthesized Expressions and  Primary Expressions.

A parenthesized expression is a primary expression whose type is the
type of the contained expression and whose value at run time is the
value of the contained expression. If the contained expression denotes
a variable then the parenthesized expression also denotes that
variable.
The use of parentheses affects only the order of evaluation, except
for a corner case whereby (-2147483648) and (-9223372036854775808L)
are legal but -(2147483648) and -(9223372036854775808L) are illegal.

About your question:

Why have this and other redundant rules in the grammar?

They are not redundant, that is a mistake in the document, they are different types of expressions. See the grammar for the next version:
StatementExpression:
  Assignment
  PreIncrementExpression
  PreDecrementExpression
  PostIncrementExpression
  PostDecrementExpression
  MethodInvocation
  ClassInstanceCreationExpression


Variable programs and variable data I'm reading "Sets for Mathematics" by Lawvere, and he uses the following metaphor at the end of section 1.3: "we will see...how any abstract set F of the right size can act as mappings between given abstract sets. (For example, in computers variable programs are just a particular kind of variable data.)"

The internet seems silent on these so called "variable programs". Has anyone heard of them/has an accessible introduction (at an introductory graduate level)? Extra bonus points if you can explain how this relates to sets and functions.

It seems that the authors refer to "functions as first-class variables". In functional languages you have variables which store functions. You can think of them as program variables since they store programs. On the other hand, if you look at how the programs are stored physically, then you get unstructured variable data.

Let's be more concrete. The (somewhat functional) programming language Python has a function eval which takes as argument a Python program. Consider the following code:

prog = "sum([x for x in range(5)])"
print eval(prog)

This prints $10$ (since in Python range(5) = [0,1,2,3,4]). Here prog is a program variable since it stores a program. On the other hand, prog is also just a mundane string (variable data). From the point of view of Python, unless you try to evaluate it ("cast" it into a program), prog is basically just a string.

If we use an enumeration of programs like in recursion theory, then program variables really are unstructured — they are just integers. If Python supported this convention then prog would be just some number with no apparent structure.

In the same way, a set-theoretic function is just another set, unless you treat it as a function. Given two sets $A,B$, we can construct the set which contains all mappings from $A$ to $B$; I don't quite understand why only the "size" (i.e., cardinality) of this set matters, but I guess you'll have to wait until Chapter 5. Perhaps they mean that with the correct encoding function, every set of the correct cardinality can be used as an index set for all mappings from $A$ to $B$, just like the enumeration of programs mentioned above.


Why is the sequence "3,3,4,5,2" considered a bitonic sequence? Why do we consider the sequence "3,3,4,5,2" a bitonic sequence?

In the sequence, "3,3,4,5,2", the sequence is

constant for "3,3",
increasing for "4,5", and
decreasing for "5,2".

The words "increasing" and "decreasing" are used in inconsistent ways. Probably, you're assuming one definition while the author of the text that's confusing you is using the other.  Say that the sequence $a_1, \dots, a_n$ is

type A if $a_1\leq a_2\leq \dots\leq a_n$;
type B if $a_1<a_2<\dots<a_n$.

The problem is that

some people refer to type A sequences as "nondecreasing" and type B sequences as "strictly increasing", which is unambiguous;
some people call type A "nondecreasing" and type B "increasing";
some people call type A "increasing" and type B "strictly increasing".

This means that the term "increasing" is ambiguous because some people use it for type A and some people use it for type B. (And ditto for variants of "decreasing".)

The same problem occurs, though to a much smaller extent; with the terms "nonnegative", "positive" and "strictly positive": the first definitely means $\geq 0$, the last definitely means $>0$; the majority of people use "positive" to mean $>0$ but a few use it for $\geq 0$. (And ditto for variants of "negative".)


Randomly filling an $n$-length array with values from $0$ to $k$ that total to $0 < m < nk$ - is a linear-time algorithm possible? Let $n, k > 0$ and $0 < m < nk$. I want to fill an $n$-length array $A$ with random integer values in the range $[0,k]$ such that $\sum_{i=0}^{n -1} A[i] = m$. Furthermore, all such arrays should be equally likely (that is, any valid array should occur with equal probability to any other). For example, if $n = 3, k = 2, m = 3$, any of these results should be equally likely:

$$[0,1,2]$$
$$[0,2,1]$$
$$[1,1,1]$$
$$[2,1,0]$$
$$[1,2,0]$$
$$[1,0,2]$$
$$[2,0,1]$$

The closest solution I could find was this, which is $O(n)$ assuming that we use a linear-time sort and shuffle (such as radix sort and Fisher-Yates respectively). However, this approach does not limit what the integers in each array position can be. Is there a $O(n)$ algorithm which solves the version of this problem described above?

Once you know how to count  the number of such arrays, you can turn that into a procedure to generate a random such array, using ranking/unranking procedures.

Let's see how to count them.  Let $f(k,m,n)$ denote the number of such arrays.  Note that we have

$$f(k,m,n) = \sum_{x=0}^k f(k,m-x,n-1)$$

by enumerating all possibilities for $A[0]$.  So, this gives a dynamic programming algorithm to count the number of such arrays.

How does this lead to a way to generate a random array?  Well, in counting such arrays, we've implicitly established a bijection $\varphi$ from the set of such arrays to the set of integers $\{0,1,2,\dots,f(k,m,n)-1\}$.  So, we just need a way to compute $\varphi^{-1}$, and then we have a way to pick a random array: we pick a random number between $0$ and $f(k,m,n)-1$, then apply $\varphi^{-1}$ to obtain the corresponding array.

Now the recurrence above establishes such a bijection.  In particular, the arrays that start with $A[0]=0$ correspond to integers in the range $0 .. f(k,m,n-1)-1$, the arrays that start with $A[0]=1$ correspond to integers in the range $f(k,m,n-1)..f(k,m,n-1)+f(k,m-1,n-1)-1$, and so on.  So, given a random integer $y$, we find the smallest $x_0$ such that

$$y < \sum_{x=0}^{x_0} f(k,m-x,n-1),$$

and then set $A[0]=x_0$ and continue recursively to fill in the rest of the array (replacing $y$ with $y' = y - \sum_{x=0}^{x_0-1} f(k,m-x,n-1)$ and using $y'$ to fill in the array $A[1..n-1]$).


What algorithms for unification over (multidimensional) array terms? I am looking for references on implementing unification over multidimensional array terms.

Are there specialized unification algorithms for those cases? I wasn't able to find satisfactory literature on the topic, and I am attempting to write a logic programming library for the J language.

By way of context, I'll assume the goal is to do unification in classical first-order logic in a fixed language $\mathscr{L}$. (Formatting and other corrections welcome.)

Briefly, you can treat arrays as terms and multidimensional arrays as arrays of arrays. You'll also introduce a new term symbol that doesn't occur in $\mathscr{L}$.

So for example, if you have a multidimensional array like the following,

\begin{pmatrix}
1 & 2 & 3\\
x & y & z
\end{pmatrix}

you'll first convert it to an array of arrays,

$$\text{((1 2 3) (x y z))}$$

and then convert it to terms. Assuming the term symbol a is not in your language, you can now represent your multidimensional array as follows:

    a(a(1,2,3),a(x,y,z))


What would be the time complexity for following recurrence? T (n) = T (n/2) + 2^n

I am solving this using master theorem and I calculated it to be big theta(log2 n) (log n to the base 2). But answer state it to be 2^n.

Any help would be appreciated.

You asked for a solution with the Master Theorem, so let's have a look;

Define your Function as $T(n) = a \cdot{} T \left( \frac{n}{b} \right) + f(n)$. Here you have $a = 1$, $b = 2$ and $f(n) = 2^n$.

Master Theorem has 3 main cases (e.g. shown here):

Case 1 - $f(n) \in \mathcal{O} \left( n^{\log_b(a)-\epsilon{}} \right)$ with $\epsilon > 0$

Case 2 - $f(n) \in \Theta \left( n^{\log_b(a)} \log^k n \right)$ with $k \geq 0 $

Case 3 - $f(n) \in \Omega \left( n^{\log_b(a) + \epsilon}  \right)$ and $a \cdot f \left( \frac{a}{b} \right) \leq c \cdot f(n) $ for large $n$ and some constant $c < 1$

Let's check, which one applies: Inserting $a$ and $b$ into $\log_b(a)$ gives $\log_2(1) = 0$ we get $n^{\log_b(a)} = n^0 = 1$ resulting into $f(n) \in \Omega \left( n^{\log_b(a) + \epsilon}  \right)$.

The other precondition also holds obviously (just put in the numbers for $a$ and $b$ and find a $c$ for yourself).

This results in the 3rd case of the Master Theorem, giving $T(n) \in \Theta (f(n)) = \Theta (2^n) $.


Sort array of duplicate integers in place Given an array of integers within [1, n] where n = size of array, some elements may appear more than once.

Could we sort it with just 1 extra space and in O(n) time?

Use Radix sort. The time complexity is O(kn) and space complexity is O(k + n) . Here n is the number of elements and k is the number of bits required to represent largest element in the array.


Closure of context-free languages under left-half The regular languages are known to be closed under the operation "left half":
$$
\operatorname{left}(L) = \{ x \in \Sigma^* : xy \in L \text{ for some } y \in \Sigma^* \text{ s.t. } |x|=|y| \}
$$
What about the context-free languages?

Let $L = \{a^nb^na^mbba^{3m} : n,m \geq 1 \}$, which is clearly context-free. Then
$$
\operatorname{half}(L) \cap a^+b^+a^+b = \{ a^nb^na^nb : n \geq 1\},
$$
which is not context-free. Hence $\operatorname{half}(L)$ is not context-free.
(If $L$ is a unary context-free language then $L$ is regular, and so $\operatorname{half}(L)$ is regular.)


Showing resolution algorithm for 2SAT is polynomial time I don't quite understand why the resolution algorithm completes in polynomial time for 2SAT but not 3SAT.
I'm looking at slide 42 of these slides for reference. It is clear that given two clauses of length at most 2, their resolvent has length at most 2. From $k$ propositional variables $x_1,\dots,x_k$, I see that there are $(2k)^2=4k^2$ possible clauses of the form $(a\lor b)$ where $a,b\in\{x_i\}\cup\{\lnot{x_i}\}$, so there are $O(k^2)$ possible clauses of length at most 2.
But how is this used to show that the resolution algorithm runs in polynomial time for 2SAT but not 3SAT?

In the case of 2SAT, resolving two clauses does not increase their width (the width of a clause is the number of literals appearing in it). This is not the case for 3SAT, where resolution could increase the width. For example, if we resolve $a \lor b \lor c$ and $\lnot a \lor d \lor e$, both of width 3, we get the clause $b \lor c \lor d \lor e$ of width 4.
When running resolution on an instance of 2SAT on $n$ variables, we necessarily get stuck after at most $4n^2 + 2n + 1$ steps, since this is the total number of clauses that we could encounter. This shows that resolution runs in polynomial time on 2SAT.
Showing that resolution does not run in polynomial time on 3SAT is much more involved, among else since resolution is not really an algorithm but rather a proof system. Perhaps the simplest proof can be found in Ben-Sasson and Wigderson's classic paper Short proofs are narrow – Resolution made simple.


Reducible and NP Hard I have been confusing a bit about these relationship:

Given A polynomial reducible to B

1/ If A is NP hard, what is the hardness of B?

2/ If B is NP hard, what is the hardness of A?

3/ If A has polynomial algorithm, how is B?

4/ If B has polynomial algorithm, how is A?

Since "B is as hard as A", then for 1/, we can say B is also NP Hard. However, I'm not sure about the reverse order. In 2/, there is not enough evidence to conclude the hardness of A

Also, for 4/ If B has poly algorithm, then A also has a poly algorithm. I'm thinking 3/ is also similar, since A is reducible to B and B as hard as A, if A has poly algorithm so does B.

Can someone please verify this? Thanks very much

If a problem $A$ is reduced to $B$, this implies that an algorithm $\mathbb{A}$ that solves $B$ can also solve $A$.

If $\mathbb{A}$ is a polynomial-time algorithm, then $B \in \mathbf{PTIME}$ and also $A \in \mathbf{PTIME}$.

If it is the case that when $\mathbb{A}$ is polynomial-time algorithm, this implies that $\mathbf{P} = \mathbf{NP}$, then $B$ is an $\mathbf{NP}\text{-hard}$ problem. Which means $A$ is also an $\mathbf{NP}\text{-hard}$ problem.

These statements answer questions 1, 2, and 4. However, your third question cannot be answered with the information you provided. This is because any problem in PTIME is also in NP, and therefore having a polynomial-time algorithm does not necessarily mean that $B$ has a polynomial-time algorithm. It might or might not have.


Big O space complexity of this isAnagram method I'm currently debating with some friends what is the Big O space complexity of this isAnagram method:

public boolean isAnagram(String firstWord, String secondWord) {
    if(firstWord == null || secondWord == null || firstWord.length() != secondWord.length()) {
        return false;
    }

    Map<Character, Integer> charCounts = new HashMap<>();
    for(char c1 : firstWord.toCharArray()) {
        if(charCounts.containsKey(c1)) {
            int currentCount = charCounts.get(c1);
            charCounts.put(c1, currentCount + 1);
        } else {
            charCounts.put(c1, 1);
        }
    }

    for(char c2 : secondWord.toCharArray()) {
        if(charCounts.containsKey(c2)) {
            int currentCount = charCounts.get(c2);
            if(currentCount == 0) {
                return false; // not an anagram if it has more of one character than the first word
            }
            charCounts.put(c2, currentCount - 1);
        } else {
            return false; // not an anagram if it contains another character
        }
    }
    return true;
}

It's a point of contention because the space used by the method doesn't exactly depend on the input, but a characteristic of the input, namely the number of unique characters in the firstWord.

Let's say m is the length of the first word, and n is the length of the second word. Let's say that k is the number of unique characters in firstWord.

Some of us think that the space complexity is O(k), essentially the number of entries in the map. That is: k is the upper bound on the space used, because k will be the number of entries created in the map, one entry for each unique character.

Some think, it's basically just an O(1) space complexity, because even though the map is dynamically sized in reality, we could also think of it as O(1) and actually just pre-populate the map with counts of 0 for all possible alphabet. The argument against this is that you don't know "all possible alphabet" when latin alphabet is 26 characters, but ascii has 128, and unicode has > 137,000, and other character sets, who knows?

Others argue that we should take into account only m, the length of the first word. In some cases m < k, because it is shorter than k. In the worst case, m > k (because of duplicate characters) and, in very long strings, m will determine the choice of the type of the map's values. e.g. The code given uses "Integer" or 2^32 size counts, but you may need to go to 2^64 or even larger on very long strings. At any rate, this argument contends that m is a factor in how the algorithm scales and so it should be O(m).

A derivative of this last argument is that, on average, for any given character, there are m/k occurrences of that character in the string and the size of a value m/k in computer space is log(m/k), therefore a tighter  Big O is O(k * log(m/k)).

Does anyone have any thoughts?

You probably expected the following answer.

Everyone of your friends is correct from her/his own perspective.

All you need to realize is that complexity analysis depends on lots of assumptions. In many cases, those assumptions have been defined beforehand or different assumptions will not not affect the end result of time-complexity analysis and space-complexity analysis. So people usually do not even mention those assumptions, especially in situations where the assumptions are stated or illustrated beforehand such as at the start of a chapter or a course. However, from time to time, situations arise where those assumptions are unclear, debatable, missing or even plainly invalid. Once you have made it clear what are the assumptions, including the model of computation used, there should be no real conflict.

Let us check each perspective raised in the question.

"The space complexity is $O(k)$", where "$k$ is the number of unique characters in firstWord". This observation points out the basic quantity in space usage.

"It's basically just an $O(1)$ space complexity", which make sense if we assume the input come from a vocabulary with a bounded number of characters. This is consistent with (almost?) all natural languages, whose number of characters are bounded while words or strings can be created as long and as many as we wanted, if only for the purpose of playing IsAnagram. Note this proposition can be seen as the previous proposition applied to refined but very common situations.

"It should be $O(m)$", where "$m$ is the length of the first word". There is hardly any argument against the correctness of this more relaxed bound, although it may seem not as tight as other bounds.

"On average, for any given character, there are $m/k$ occurrences of that character in the string and the size of a value $m/k$ in computer space is log(m/k) therefore, a tighter big $O$ is $O(k\log(m/k))$". This bound is based on the sharper observation that a number consists of many bits. Instead of counting the number of numbers used, it counts the number of bits used. (To prove that bound is correct, a dose of non-trivial math is needed.) The positional number system is about the optimal system to represent integers in term of space usage in this world, a fact that is reflected in the $\log$ factor. It can hardly considered anywhere near the physical truth without that factor. This line of reasoning is interesting as it indicates a more realistic model of computation than the more-commonly-used models of computations as implied in virtually every tutorial for elementary complexity analysis ([1], [2], [3]), where any integer is considered occupying a unit of space for the sake of simplicity and uniformity. Those common models include the family of register machines that includes counter machine and random-access machine. That is why we rarely see that $\log$ factor showing up in most complexity analysis. Unless required explicitly, we usually ignore that factor in space-complexity analysis and time-complexity analysis on our daily programming.
On the other hand, that factor has to be taken into consideration, for example, in the bit by bit analysis of the Turing machines (Why do we reject Turing machines that use space less than the log of the length of the input?).

You might insist asking, which answer makes sense most? Well, even though I might have my personal preference, a single choice will appear opposite to the whole point of this answer. Each and every one of them is valid under their respective assumptions and useful in different situations. Of course, if you are in an exam, do remember the default assumptions in your course!

As you must have noticed, I have inserted time-complexity in this answer. That is because we could have similar contention over the time-complexity of many algorithms. The usual resolution will be the same: state the assumptions clearly and we can happily accept each other's view, even though we might feel less comfortable with others' perspectives.


What's this type of semantic analysis called in NLP? I'm speculating that this is very much known in NLP, but as I've not studied NLP, I don't know what concepts are related to this:

Basically I have entities that are connected by some strings. I want to do semantic analysis using this kind of constructs. I.e. by checking whether a given sentence has entities (the yellow ellipses) connected with the right strings.

Notice that this is also basically describable as a a deterministic context-free language. But I'd like to understand the semantical aspect of this, rather than mere parsing (string matching).

Given your example, Lexical Semantics may be what you are looking for. Things like WordNet provide hypernym (breakfast -> meal), hyponym (meal -> lunch), meronym (course -> meal), holonym (water -> oxygen) relationships. See chapter 19 of Speech and Language Processing by Jurafsky and Martin for more thorough set of details.


Does starvation freedom imply progress? The above answer taken from the book https://www.amazon.com/Operating-Systems-Sibsankar-Haldar/dp/8131730220 says starvation freedom may not imply progress as processes can be deadlocked.

I think that starvation freedom implies deadlock freedom so there is no chance of deadlock and progress is also satisfied.

Is the answer in the picture correct ?

It depends on how exactly you define "starvation freedom" and "liveness."

I believe the book is talking about starvation freedom from the perspective of the OS scheduler, which usually does not know about locks managed by user processes.  So, the book is partially right (in some context).

Your definition is more broad and is what someone working in distributed systems would think (see https://en.wikipedia.org/wiki/Liveness.  Note the important assumption "All processes are assumed to correctly use the mutex...").

However, I'd think that "liveness implies starvation freedom," but there's no justification in the book for the first statement in the answer.


Randomized Version of NP I came across interactive proofs and randomized computation, in particular, i read about the complexity classes $\text{IP}, \text{BPP}, \text{RP}$, etc.
Since the above classes are well-known, I will give a hand-wavy definition of $\text{IP}$. Then, I will state my question. Roughly speaking, a language $L \in \text{IP}$ iff there exist a pair of interactive algorithms Prover $P$ and Verifier $V$, with $V$ running in probabilistic polynomial time (in the length of the input $x$: $x$ is common to both $P$ and $V$), such that:

If $x\in L$, and the Prover $P$ follows the protocol, then the probability that the Verifier $V$ accepts is 1, and
if $x\notin L$, then for any Prover $P$ (even a cheating one), the
probability that the Verifier $V$ accepts is at most $\frac{1}{2}$.

I note that $P$ is allowed to be computationally unbounded.
Now to understand the power of interaction, I started to see what happens when restrict or give up the interaction between the prover and the verifier. I read the following in this lecture here, given by Jonathan Katz:
1- Assume that the verifier has input $x$. If the protocol is such that the prover $P$ sends a proof $\pi$ (to the fact that $x\in L$) to the verifier $V$, and then the interaction ends. The verifier has then to verify that $x \in L$, given $\pi$. If the verifier is deterministic and runs in polynomial time in $|x|$. Then, it is not hard to see that such interactive protocol is equivalent to the complexity class $\text{NP}$.
2- Now if we consider the interaction protocol in item 1, and additionally allow the verifier to be probabilistic, then we get more than $\text{NP}$. Specifically, it is known that in this case, any language in $L \in \text{BPP}$ can be handled by the protocol. Note that this actually suggest that we can eliminate the error when $x\in L$.
The protocol in item 2, can be thought of as a randomized version of $\text{NP}$.
Here comes my question: can the protocol given in item 2, handle any language in $\text{IP}$? That is, given a language $L\in \text{IP}$, can we give up the interaction entirely and still be able to verify that $x \in L$ in probabilistic polynomial time with completeness $1$, and soundness at most $\frac{1}{2}$? Intuitively, I think the answer is unknown because randomized complexity classes are conjectured to be contained in $\text{P}$ and we don't even know whether $\text{P}$ is a strict subset of $\text{PSPACE} = \text{IP}$.

The class you described is MA (interactive proofs consisting of one round where the prover, Merlin, sends one meassage to the verifier, Arthur, which then has to decide in probabilistic polynomial time whether to accept or reject).
Since $BPP\subseteq \Sigma_2\cap \Pi_2$  it immediately follows that $MA\subseteq \Sigma_2\cap \Pi_2$, which is believed to be a strict subset of PSPACE which contains the entire polynomial hierarchy.


Why doesn't the Needleman-Wunsch algorithm find solutions that begin with a gap? I have implemented in C++ the Needleman-Wunsch algorithm for pairwise sequence alignment using the following scores: +1 for match (regardless of base), -1 gap penalty and -1 for a mismatch. Given two sequences of length $m$ and $n$ the algorithm then generates the $mn$ search space row by row as per the algorithm's specifications and backtracks generating all solutions of maximum score. Given two sequences in which the first two letters overlap ie:

GCATGCU

and

GATTACA

the algorithm succesfully generates all the alignments of maximum score. Howeever, given two sequences of the kind:

ACTGCUGCTA

and

UGCTAATCGU

the algorithm fails to find any of the solutions that begin with a gap in sequence 1 or 2, thus failing to find the optimal solution as well:

ACTGCUGCTA-----
-----UGCTAATCGU

Once I add the letter A to the second sequence the algorithm once again has no problem finding the optimal solution (which in this case begins with a match and not a gap)

ACTGCUGCTA-----
A----UGCTAATCGU

Could someone explain to me why the algorithm doesn't find this subset of solutions and perhaps how I can modify it to find these solutions as well?

Your optimal alignment seems to be an optimal local alignment, the best substring match. Needleman-Wunsch is for global alignment. With the simple program by Eddy that you can find on the internet I have determined a global score of 0. This is better than the gobal score you get:  -5 (for 10 gaps and 5 matches).

Sequence X: GCATGCU
Sequence Y: GATTACA
Scoring system: 1 for match; -1 for mismatch; -1 for gap

Dynamic programming matrix:
             G    A    T    T    A    C    A
        0   -1   -2   -3   -4   -5   -6   -7
   G   -1    1    0   -1   -2   -3   -4   -5
   C   -2    0    0   -1   -2   -3   -2   -3
   A   -3   -1    1    0   -1   -1   -2   -1
   T   -4   -2    0    2    1    0   -1   -2
   G   -5   -3   -1    1    1    0   -1   -2
   C   -6   -4   -2    0    0    0    1    0
   U   -7   -5   -3   -1   -1   -1    0    0

Alignment:
X: GCA-TGCU
Y: G-ATTACA
Optimum alignment score: 0


How to test if my implementation of tree/graph data structures are correct? I've recently implemented RB tree, B-Tree and vEB tree. I was wondering however if there's any rule of thumb for testing if my implementation are actually correct.

Is there any reference that can tell how to develop proper test cases for such data structures?

Besides from mathematical techniques maybe.

What about graph in general?

Identify the representation invariants.  Add assert statements to check that the representation invariant holds (sometimes called a repOK function).  Use random testing to generate millions of test cases, and check that no assert ever fires.

Build a reference implementation of the abstract data type that implements all of the methods, but instead of using your data structure, implements the same semantics using some known-good data structure (e.g., a simple list or something).  Use random testing to generate millions of test cases, and check that in every case your implementation produces the same results as the reference implementation.

This isn't perfect but it'll probably be pretty good.


Find the minimum path to every vertex using Bellman-Ford I was studying the chapter 24 of the CLRS and got to the following question:

  24.1-5 $\star$ Let $G=(V,E)$ be a weighted, directed graph with weight function $w : E \rightarrow \mathbb{R}$. Give an $O(VE)$-time
  algorithm to find, for each vertex $v \in V$, the value $\delta^{*}(v) = \min_{u \in V}\{\delta(u,v)\}$.

From what I understood, he wants an algorithm to find the shortest path beginning in any $u \in V-\{s\}$ to every vertex $v \in V$. So, this algorithm would return one shortest path for each vertex in $V$ in $O(|V||E|)$. I couldn't come with any other answer besides using an All-Pairs Shortest Paths algorithm and choosing the paths with less value for each vertex. But, as this chapter is about the Bellman-Ford, this is probably some modification from the original algorithm.

If someone could point me in the right direction, I would really appreciate.

The algorithm is very similar to Bellman-Ford algorithm except that for each vertex $v$, you maintain $\delta^*(v)$, while in Bellman-Ford algorithm you maintain the length of shortest path from a certain source to $v$.

The correctness of the proof is also similar to that of Bellman-Ford algorithm. More specifically, you prove the following lemma by mathematical induction.

  Lemma. After $i$ repetitions of for loop:

  If $\mathrm{Distance}(u)$ is not infinity, it is equal to the length of some path from to $u$;
  If there is a path to $u$ with at most $i$ edges, then $\mathrm{Distance}(u)$ is at most the length of the shortest path to $u$ with at most $i$ edges.


Confusion in the added loop of the Halting Problem I know there's like a thousand questions about this topic in the site and elsewhere. I'm just going to pick one that at least for me it serves as a good basis for my question. The answer by Rick Decker is the one that I understood more, so I'm just going to take it as a basis for my actual doubt.
It's not difficult to see that if one adds an if (and extra loop) into 'Halting Program '  $H$, then feeding $H$ to itself yields a contradiction. What it confuses me is why to add the extra loop to force the contradiction, if by hypothesis $H$ solves (itself?)
It doesn't seem logical to say first (of course I'm missing something), hey I give you $H$ that solves your issue, but afterwards I give you an augmented $H$ that does not and so we reach a contradiction.

What we show is that this augmented $H$ can not even exist. You gave me $H$, and I gave you back an augmented $H$, called $\hat H$. We can build this $\hat H$ by adding the extra loop and if statement, but its easy to show that this augmented $\hat H$ will never be able to exist: $\hat H(\langle \hat H\rangle)$ is not either rejecting or accepting, nor stuck in an infinite loop, but we know that any TM must be either one of those.
Therefore, we get a contradiction to the existence of $H$: we showed that if $H$ exists, then some other $\hat H$ exists, but also $\hat H$ couldn't ever exist.


vertex cover reduction to subset sum Subset sum

  Input: A multi set $S$ of numbers and a natural number $t$
  Question: Does $S$ contain a subset $A$ such that $\sum_{x \in A} x =
 t$? (e.g., $\{1,1,2,3,4,5\}$, by multiset it means duplicates are allowed)

  Vertex cover

  Input: An undirected graph $G$ and a number $k$.
  Question: Does $G$ have a vertex cover of size $k$?

Show: vertex cover $\leq_P$ subset sum

My work so far:
 I need to somehow transform $(G, k) \to  (S, t)$

Above is a example graph $G$ that I constructed. It's vertex covers are $\{v_1, v_3\}$ so the size of the vertex cover is $2$, thus $k = 2$.

This is basically $S$

\begin{array}{|c|c|c|c|c|}
\hline
& e_1 & e_2 & e_3 & e_4 \\ \hline
v_1 & 1& 0& 0& 1\\ \hline
v_2 &  1& 1& 0& 0\\ \hline
v_3 &  0& 1& 1& 0\\ \hline
v_4 & 0& 0&  1&1\\ \hline
\end{array}

if $e_i$ and $v_j$ is incident I put $1$; otherwise $0$

Now what I need is a target $t$ to satisfy this.

The matrix above can be written in a set to be $S = \{1001, 1100, 0110, 0011\}$ if I were to add up all these values probably in base 2 since its binary, it would give me a value but I think I need a consistent value $t$, so this wont work. I'm also unsure how to integrate the $k = 2$ into this either.

Could someone help me construct this?

For simplicity write all the numbers in base $4$. Fix an arbitrary ordering of the edges of the graph $G$ and let $e_i$ be the $i$-th edge ($i= 1, \dots, |E(G)|$).

For each vertex $v \in V(G)$ define an integer $n_v$ of $|E(G)| + 1$ digits as follows:

the $i$-th least significant digit of $n_v$ is $1$ if $e_i$ is incident to $v$ and $0$ otherwise;
the most significant digit of $n_v$ is $1$.

For each edge $e_i \in E(G)$ let $m_{e_i} = 4^{i-1}$ (i.e., the $i$-th least significant digit of $m_e$ is $1$ and all the other digits are $0$).

The instance of subset sum is obtained by choosing $S = \{ n_v : v \in V(G) \} \cup \{m_e : e \in E(G) \}$ and $t = k 4^{|E(G)|} + 2\sum_{i=0}^{|E(G)|-1} 4^i$.
In other words, the most significant digits of $t$ encode the number $k$ in base $4$, while the $|E(G)|$ least significant digits of $t$ are all equal to $2$.

If there is a vertex cover $V' \subseteq V(G)$ of $G$ of size $k$,
let $E'$ be the set of edges $(u,v) \in E(G)$ such that exactly one of $u$ and $v$ is in $V'$.
Then, $A = \{ n_v : v \in V' \} \cup \{ m_e : e \in E' \}$ is a subset of $S$ that sums to $t$. Indeed:
$$
\sum_{x \in A} x = \sum_{v \in V'} n_v + \sum_{e \in E'} m_v
= k 4^{|E(G)|} + 2 \sum_{e_i \in E \setminus E'} 4^{i-1} +
2 \sum_{e_i \in E'} 4^{i-1}
= k 4^{|E(G)|} + 2 \sum_{e_i \in E} 4^{i-1} = t.
$$

If there is a subset $A$ of $S$ that sums to $t$, then $A$ contains exactly $k$ numbers from $\{ n_v : v \in V(G) \}$ (as otherwise the most significant digits of $\sum_{x \in A} x$ would not match those of $t$). Moreover, $V' = \{v_i : n_i \in A \}$ is a vertex cover for $G$.

To see this, pick any $e_i = (u,v) \in E(G)$ and notice the $i$-th least significant digit of $t$ is $2$.
Since, for $j=1,\dots, |E(G)|$, there are exactly $3$ numbers in $S$ whose $j$-th least significant digit is non-zero (namely $n_{u'}$, $n_{v'}$, and $m_{e_j}$, where $e_j = (u', v')$),
we have that in the summation $\sum_{x \in A} x$ no carry occurs among the $|E(G)|$ least significant digits. We conclude that $A$ contains exactly two numbers from $\{n_u, n_v, m_e\}$, implying that $u \in V'$ or $v \in V'$ (possibly both).

In your example graph, for $k=3$ you get the following (bold rows denote the elements of $A$ when $V'=\{v_1, v_3, v_4\}$):
$$
\begin{array}{|c|c|c|c|c|}
\hline
& & e_1 & e_2 & e_3 & e_4 \\ \hline
\pmb{n_{v_1}} & \pmb{1} & \pmb{1}& \pmb{0}& \pmb{0}& \pmb{1}\\ \hline
n_{v_2} & 1 & 1& 1& 0& 0\\ \hline
\pmb{n_{v_3}} & \pmb{1} & \pmb{0} & \pmb{1} & \pmb{1} & \pmb{0}\\ \hline
\pmb{n_{v_4}} & \pmb{1} & \pmb{0} & \pmb{0} & \pmb{1} & \pmb{1}\\ \hline
\end{array}
$$
$$
\begin{array}{|c|c|c|c|c|}
\hline
& & e_1 & e_2 & e_3 & e_4 \\ \hline
\pmb{m_{e_1}} & \pmb{0} & \pmb{1} & \pmb{0} & \pmb{0} & \pmb{0} \\ \hline
\pmb{m_{e_2}} & \pmb{0} & \pmb{0}& \pmb{1}& \pmb{0}& \pmb{0}\\ \hline
m_{e_3} & 0 & 0& 0& 1& 0\\ \hline
m_{e_4} & 0 & 0& 0& 0& 1\\ \hline
\end{array}
$$

$$
\begin{array}{|c|c|c|c|c|}
\hline
\phantom{m_{e_4}}& & e_1 & e_2 & e_3 & e_4 \\ \hline
t & 3 & 2& 2& 2& 2\\ \hline
\end{array}
$$


Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions? I'm currently reading the elements of programming book and have come across a section I don't quite understand

  A computational basis for a type is a finite set of procedures that enable the construction of any other procedure on the type. A basis is efficient if and only if any procedure implemented using it is as efficient as an equivalent procedure written in terms of an alternative basis. For example, a basis for unsigned k-bit integers providing only zero, equality, and the successor function is not efficient, since the complexity of addition in terms of successor is exponential in k

Given the successor function , wouldn't addition be linear? e.g. getting get the result of a + b the complexity would be O(b) starting from a? I know this is likely not the case as I'm sure the book knows more about what it's saying than me, but can someone explain why this operation would be exponential?

The complexity of getting "the result of a + b" would indeed "be O(b) starting from a".

However, b is a log(b)-bit integer, and O(b) = O(2^(log(b))).


Can I decrypt an RSA algorithm using only the message I am wanting to decrypt, an "e" value and a "n" value? I have a ciphertext $c$ encrypted with RSA algorithm that needs to decrypt. I have the public key $(n,e)$.

Is it possible to decrypt with this amount of information?

You have the public key. The whole point about public key cryptography is that the message is encrypted with the public key and must be decrypted with the private key, which you don't have.

The public key is not a secret: it is distributed publically so that people can encrypt messages for its owner. If you could decrypt the message knowing the cyphertext and the public key, RSA would be completely broken, because then anybody could decrypt any message. If anybody knows how to do this, they're keeping it a secret.


Maximize points of K dance moves In this problem, I want to maximize the number of points of K dance moves. There are N possible dance moves.

Each of the dance moves have a point value associated with it which can be positive or negative.

There are also points from transitioning from one dance move to another. We're given an $N\times N$ matrix that has the points gained from transitioning from one dance move to another.

The brute force solution is easy which is simply try every dance move for the 1st move, then the 2nd move, then the 3rd ... which is $O(N^K)$.

My interviewer says there's a $O(NK^2)$ or $O(KN^2)$ solution (don't quite remember if it's one or the other).

How do I get that solution or what's the best solution to this problem?

Thanks!

We can model the transition of one move to another using the following discrete dynamics:

\begin{align}
m_{n+1} &= u_{n}
\end{align}

where $m_{n}$ is the $n^{th}$ move you performed and $u_{n}$ is the $n^{th}$ choice of the next move you will make. Note that both $m_n$ and $u_n$ are members of the move set, $\mathcal{M}$. The cost function you wish to maximize might then be of the form:

\begin{align}
V &= P_{M}(m_{K+1}) + \sum_{j=1}^{K} P_{M}(m_j) + P_{T}(m_j,u_j)
\end{align}

where $P_{M}(\cdot)$ gives you points for your current move and $P_{T}(\cdot, \cdot)$ gives you points from the transition from $m_j$ to $u_j$. Given this formulation, you can then recursively find an optimal policy, $\mu^{*}_{j}(m)$, that will generate optimal sequences given some move at step $n$ of the sequence. This can be found via:

\begin{align}
V^{*}_{K+1}(m) &= P_{M}(m) \; \forall m \in \mathcal{M} \\
V^{*}_{j}(m) &= \max_{u \in \mathcal{M}} P_{M}(m) + P_{T}(m,u) + V^{*}_{j+1}(u) \; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\
\mu^{*}_{j}(m) &= \arg\max_{u \in \mathcal{M}} P_{M}(m) + P_{T}(m,u) + V^{*}_{j+1}(u) \; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\
\end{align}

Once you have found the optimal policy $\mu^{*}_{j}(m)$, you can obtain an optimal dance move sequence from some dummy starting move using the following:

\begin{align}
m_{n+1} &= \mu^{*}_{n}(m_{n})
\end{align}

In this case, $\lbrace m_2, m_3, \cdots, m_{K+1}\rbrace$ would be your optimal set of $K$ moves. Now as we can tell from the recursive algorithm, we would essentially have three nested loops to obtain the optimal policy. These nested loops together are $O(KN^2)$ because we loop through all $m$ and $u$ (both of size $\left| \mathcal{M}\right| = N$) at a given step for $K$ steps. Generating the optimal sequence is then just $K$ steps, but the recursive algorithm is the dominant part of the algorithm computationally.

Simplified Explanation

So in the explanation above, we defined the dynamics to obtain the next move $m_{n+1}$ based on information we know, like the current move $m_n$ and the choice of what move to make next, $u_n$. We also defined a cost function to maximize, $V$.

To solve this problem using Dynamic Programming, we treat the cost function as a reward for a discrete trajectory and try to find optimal sub-trajectories, starting from the end of the sequence. The logic behind this is we can incrementally solve the optimal trajectory by using previously found optimal sub-trajectories.

We can define the final cost trajectory term as:

\begin{align}
V^{*}_{K+1}(m_{K+1}) &= P_{M}(m_{K+1})
\end{align}

where $m_{K+1}$ is within the set of moves, $\mathcal{M}$. We can define this term because it is independent of the decision variable, $u$, which is what we are trying to find an optimal algorithmic strategy to choose. Now the recursive relationship for the next piece of the cost trajectory is:

\begin{align}
V_{K}(m_K, u) &= P_{M}(m_K) + P_{T}(m_K, u) + V^{*}_{K+1}(m_{K+1})
\end{align}

where $u$ can be any move within $\mathcal{M}$. Note how this equation depends on the value for $m_{K+1}$. This dependence is where you incorporate your knowledge of the dynamics. We know based on the discrete dynamics that this cost term can be redefined as:

\begin{align}
V_{K}(m_K, u) &= P_{M}(m_K) + P_{T}(m_K, u) + V^{*}_{K+1}(u)
\end{align}

Our goal now is to find the optimal value of $V_{K}(m_K)$, for each value of $m_K$ within $\mathcal{M}$, with respect to $u$. This is simply written as:

\begin{align}
V^{*}_{K}(m_K) &= \min_{u \in \mathcal{M}} V_{K}(m_K, u)
\end{align}

Note that we also define the optimal value of $u$ for a given step $j$ and a given state $m$ as the optimal policy $\mu^{*}_j(m)$. We can use the above findings to thus define a recursive formulation to find the optimal cost:

\begin{align}
V^{*}_{K+1}(m) &= P_{M}(m) \; \forall m \in \mathcal{M} \\
V^{*}_{j}(m) &= \max_{u \in \mathcal{M}} P_{M}(m) + P_{T}(m,u) + V^{*}_{j+1}(u) \; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\
\mu^{*}_{j}(m) &= \arg\max_{u \in \mathcal{M}} P_{M}(m) + P_{T}(m,u) + V^{*}_{j+1}(u) \; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\
\end{align}

Note that $j$ should start at $K$ and be decremented down to $1$. Implementing this algorithm becomes a series of nested loops. This can be shown in pseudo-code to be the following:

for m in {Set of Moves}
  V_opt(K+1,m) = P_m(m)
end

for j going from K to 1, increment -1
  for m in {Set of Moves}
    // initialize V_opt(j,m)
    V_opt(j,m) = -Infinity

    for u in {Set of Moves}
      points = P_m(m) + P_t(m,u) + V_opt(j+1,u)
      if( V_opt(j,m) < points )
        V_opt(j,m) = points
        policy_opt(j,m) = u
      end
    end // end for loop u
  end // end for loop m
end // end for loop j

After finding the optimal policy $\mu^{*}_j(m)$ (policy_opt(j,m) in code), you can generate the optimal moves using the dynamics as noted previously. As you can see looking at the pseudo-code, the algorithm uses 3 nested loops, two of size $N$ and one of size $K$. This makes the problem dominated by a computational complexity of $O(KN^2)$.


Remove vertices until no edges are left Given an undirected graph G(V,E), find the minimum number of vertices to remove so that the Edge Set of the graph becomes empty.
In other words: If we remove one vertex we remove that vertex along with all edges connected to that vertex. Find the minimum number of vertices to remove so that there are no edges left in G after their removal.

It sounds like you found the answer yourself, you are describing Vertex Cover, which in many ways are very similar to Independent Set, both problems are NP-complete.
The relation to Independent Set is that in a graph $G = (V,E)$, a set $S$ is a minimal vertex cover if and only if $V \setminus S$ is a maximal independent set.
If you know that Independent Set is NP-complete, then it follows that Vertex Cover is NP-complete too.
In other words, you are also looking for a maximum Independent Set.
Vertex cover.  Given a graph $G = (V,E)$ and an integer $k$, does there exist a set $S \subseteq V$ of size at most $k$ such that all edges in $G$ are incident to a vertex in $S$?
Independent set.    Given a graph $G = (V,E)$ and an integer $k$, does there exist a set $S \subseteq V$ of size at least $k$ such that the induced graph $G[S]$ has no edges?


Selecting a polygon within an array of complex polygons I have an array of polygons which are arrays of points. There are no gaps and none of them overlap like a Voronoi diagram.

Unlike a Voronoi diagram I cannot simply find the nearest centroid to select a polygon, this returns the correct polygon most of the time but sometimes the point lies within a neighboring polygon.

The developer tools in my chrome browser seem to be able to do it with the selection tool but I have no idea how it is doing it.

I would use a winding number algorithm. There are a few, but the fastest goes like this:Imagine a line from your point along the positive  x-axis. Now, for every edge of your polygon, determine if it crosses this line. if it crosses the line from below to above, then increment the winding number (which is initially zero), if it crosses going from above to below then decrement. If the winding number is zero, then the point lies outside of the polygon, otherwise it lies inside.

You probably don't want to test every polygon every time the point moves, so I would pre-compute a bounding box or sphere for every polygon. I would then only test winding numbers against those polygons whose bounding shapes collide with the point in question.

Hope this helped.
Good luck!


Ordered knapsack problem? I'm trying to find the name of this problem, and with it a reasonable algorithmic solution.

Setup: There are $n$ items with weights $w_1,\dots,w_n$, and $m<n$ buckets with target weights $a_1,\dots,a_m$, satisfying $\sum_iw_i=\sum_ja_j=1$.  The goal is to find an assignment $f:\{1,\dots,n\}\to\{1,\dots,m\}$ of the weights to the buckets such that $f$ is nondecreasing (the weights have to be in the same order as the buckets) and the sum of the weights in each bucket is "close" to the target for that bucket.

The sense of "closeness" is up to the implementation (whatever is easiest to model), but for concreteness let's suppose this is least-squares error; then we can define the error of a given assignment as $\varepsilon(f)=\sum_{i=1}^m(\sum_{j:f(j)=i}w_j-a_i)^2$, and the goal is to find the $f$ that minimizes $\varepsilon(f)$.

This problem seems similar to the knapsack problem, but there are some differences in the constraints and I don't know if this is also NP-complete. Does this problem have a name or reduce to a named problem?

The fact that $f$ is non-decreasing makes the problem much easier, solvable in polynomial time.

You have to find a way to split the weights so that weights $1,\ldots,x$ go to bucket $1$, weights $x+1,\ldots,y$ go to bucket $2$, weights $y+1\ldots,z$ go to bucket $3$, and so on.

If you define $D(i,j)$ to be the best way to assign weights $j,\ldots,m$ to buckets $i,\ldots,n$ you can apply dynamic programming.


Is there such a thing as an algorithm that runs in asymptotic time? For example: $O(-e^{-x} +1)$. Basically as the size of the input increases, the time it takes to run converges.

It is not hard to see that $O(-e^{-x} +1) = O(1)$.


Finding shortest path for DAG using dynamic programming vs topological sort? Why is it that when I read about finding the shortest path for a DAG I usually just hear about topological sort? Why not use dynamic programming where the shortest path to a vertex is simply the minimum of all vertices that have a path to it?

To use dynamic programming, you need to choose the order in which you fill in values for the vertices.  The correct order is a topologically sorted order (any other order won't work).  So, the two solutions are in some sense equivalent.  Any solution is likely to use both components: topological sorting to determine the order to enumerate the vertices, and something like dynamic programming to fill in the value at each vertex.


Bipartite Graph to solve the wolf river crossing problem I have just started studying about bipartite graphs and there is an example that bipartite graph can be use to solve the wolf, cabbage, and the sheep river crossing problem, as a kid i had fun solving this question, now I was wondering how can we describe the problem in bipartite graph, as to describe it we need to divide the problem into two disjoint and independent sets, I am getting very confused as how it can be done?
It will be helpful, if someone can help me understand it as there is no information about this wolf river crossing problem on the internet.

I have never really imagined solving this problem with a graph, but it is an interesting point of view.
My guess is that the graph you have to create is a bipartite graph with 16 vertices, each vertex representing the state of the situation, that is representing where is each of the different actors of the problem: the wolf, the goat, the cabbage and the boat. Each actor have two positions possibles (each side of the river), so $2^4 = 16$ different configurations. You might then delete forbidden configurations, representing a case where the wolf is alone with the goat or the goat alone with the cabbage.
Now, you can add an edge between two vertices $v$ and $w$ if and only if you can go from $v$ to $w$ by crossing the river with the boat, with one actor from wolf/goat/cabbage on board.
The graph is indeed bipartite, because there are no edges between two vertices where the boat is on the same side.
Solving the problem now results in finding a path between the two vertices where the four actors are on each side of the river.


Is DISCRETE LOG a NP hard problem? In cryptography there are two problems which are part of the foundation of modern public key cryptography. Both of them can be solved in polynomial time on quantum computers. I am talking about:

FACT

Given: A composite number, i.e. a positiv integer which is the product of some prime numbers: $x = p_1 \cdot p_2 \cdot \ldots \cdot p_n$  You know only $x$.

Wanted (calculation problem): At least one factor of this composite number.

As a decision problem: For a given $k \le x$: Is there a factor $p_i \le k$?
(You just need to solve the decision problem $\log x$ times to solve the calculation problem. So, as long as the complexity of the decision problem is polynomial or harder, both flavors of the problem belong to the same time-class.)
DISCRETE LOG

Given: $x = a^n \mod p$. There $p$ is prime and you know $x$, $a$ and $p$.

Wanted (calculation problem): Find $n$.

As a decision problem: Is there some $n \le k$ such that $x=a^n \mod p$?
(Also here you need to solve the decision problem only $\log p$ times to solve the calculation problem.)

I know, that both problems, as far as we know, are not in the complexity class $P$, i.e. for both problems there is no algorithm know that could solve them in polynomial time on a deterministic Turing Machine.

I know, that both problems can be solved in polynomial time on a non-deterministic Turing machine, which, per definition means, that both of them are in the class $NP$.

Let's suppose, that $P \ne NP$. Under this assumption $NP$ is partitioned into three sub-classes:

$P$
All problems which are solvable in polynomial time on a deterministic Turing Machine
$NPC$
NP-complete.
The subset of $NP$ to which all problems in $NP$ can be reduced, i.e. the subset of $NP$ that is NP-hard.
$NPI$
NP-intermediate
All problems which are in $NP$ but neither in $P$ nor in $NPC$.

It is known, than $NPI$ is not empty if $P \ne NP$ (Ladner's theorem).

(If $N=NP$, then also $NPC=P$, which means, that $NPI$ must be empty.)

I know, that under the assumption that $P \ne NP$, FACT seems to be in $NPI$, since until now nobody could prove that FACT $\in NPC$.

But I could not find similar statements about DISCRETE LOG.

Here are my questions:

Is DISCRETE LOG know to be in $NPC$? Or is it thought to be in $NPI$?
If it is in $NPI$:

Is there a know algorithm to reduce FACT to DISCRETE LOG?
Or is there an algorithm to reduce DISCRETE LOG to FACT?
Are they maybe even equivalent, i.e. reduzibel in both directions?

No one knows, but:

It is suspected that neither factoring nor discrete logarithm are NP-complete, but we have no proof.  (Evidence for the suspicion: they are in NP $\cap$ coNP.  See, e.g., https://cstheory.stackexchange.com/q/159/5038, https://cstheory.stackexchange.com/q/167/5038 for factoring.  It's similarly easy to prove that discrete log is in NP $\cap$ coNP; see, e.g., How hard is finding the discrete logarithm?.  Moreover, if any problem in NP $\cap$ coNP is NP-complete, it follows that NP = coNP.  This would be an unexpected result.)
It is suspected that there is no polynomial-time algorithm for factoring or discrete logarithm, but we have no proof.  (Evidence for the suspicion: we haven't been able to find a polynomial-time algorithm for either, despite a lot of trying.)
There is no known (classical) reduction between discrete log and factoring.  However, I personally wouldn't be shocked if one were found, or if both were found to be instances of some broader problem, or something.  For instance, when we find an algorithm technique that works against one, historically often we've been able to adapt it to the other as well.  So, they seem to be connected or related in some deep way.


Can someone help me fully grasp idea and time/space complexity with this code? My understanding is the following:
Time = With the initial not state is just to check if there are no elements in the list a. This is done in O(1) time. The first loop enumerates the second list b with the operation append() which is done in O(1) time therefore the first loop is O(n). The second loop I am confused if the sorting plays a factor since I know the sort method is O(nlogn) time. Within the second loop I am a bit confused about the operations as far as what it is specifically doing which I wanted to ask about although I do understand the fact that if the i-th element in a is < c it goes into the if statement.
Space = Overall I think it is O(n) as the only additional space needed was the list x plus the input space and the length of x grows as a or b grows.
Given the following Python code:
a = [3, 1, 2]  # input length will be size n
b = [1, 2, 3]  # input length will be size n
c = 4

def foo(a, b, c):
    res = 0
    if not a:
        return res

    x = []
    for i, j in enumerate(b):
        x.append((j, i))

    for j, i in sorted(x, reverse=True):
        if a[i] < c:
            res += a[i] * j
            c -= a[i]
        else:
            res += c * j
            break
    return res

Can someone help go over what the time and space complexity is plus the idea behind it mainly?

You are completely correct in your analysis.
Space.  You construct an array $x$ which has length the same as that of $b$, which is $n$.  It contains a pair for each element in $b$, so it has size $O(n)$.  The other variables do not count, hence space complexity is indeed $O(n)$.
Time.  You correctly observed that the sorting of $x$ takes time $O(n \log n)$, and that both iterations take time $O(n)$.  Everything else is arithmetic operations, which all run in $O(1)$ time.  Hence, something like $O(n) + O(n \log n) + O(n) + O(1)$, which all in all results in a time complexity of $O(n \log n)$.
Well done!


Single-tape Turing Machines with write-protected input recognize only Regular Languages Here is the problem:

Prove that single-tape Turing Machines that cannot write on the portion of the tape containing the input string recognize only regular languages.

My idea is to prove that this particular TM is equivalent to a DFA.

Using this TM to simulate DFA is very straightforward.

However, when I want to use this DFA to simulate TM, I encounter the problem. For the TM transition $\delta(q,a)=(q',a,R)$, DFA can simulate definitely by reading tape to the right and doing the same state transition.

For $\delta(q,a)=(q',a,L)$, I cannot figure out how to use this DFA or NFA to simulate the left move because the DFA only reads to left and has no stack or something to store.

Should I consider another way? Could anyone give me some hints? Thanks.

Introduction

I thought there might be an error in the original statement of the question,
and the OP was no longer around to ask. So I assumed that the tape was
read-only everywhere, and wrote a first proof based on that
assumption, motivated by the fact that the TM has full Turing power
outside the input part of the tape if it can write it, which induces the false belief
that it can recognize any RE language.

However, that is not the case: the restriction on writing on the input
part of the tape implies that only finite information can be extracted
from the input, limited by the number of states on entry and exit of
that part of the tape (combined with side of entry and exit). InstructedA is to be credited for remarking in a comment that there is a problem with recognizing any RE language, since it is not possible to make a copy of the input without EVER writing to the original input area,

Hence I wrote a second proof that assumes that only the input section
of the tape is read-only, the rest being read-write allowed.

I am keeping both proofs here, as the first did help me find the
solution, even though it is not necessary to understand the second
proof, is more complex, and is subsumed by the second proof. It can be
skipped. However, the weaker proof has the advantage of being constructive
(to obtain a FSA equivalent to the Turing Machine), while the more general result is not constructive.

However I am giving first the last and more powerful result. I am a bit surprised that I was not able to find this result, even without proof, elsewhere on the net, or by asking some competent users, and any reference to published work would be welcome.

Contents:

Turing machines that do not overwrite input accept only regular languages.
This proof is not constructive.
Turing machines with read-only tapes accept only regular languages.
It may be skipped as subsumed by previous proof, but it uses a different approach, which has the advantage of being constructive.

Turing machines that do not overwrite input accept only regular languages

We recall that, while the TM does not overwrite its input, and is thus
read only on its input, the TM can read and write on the rest of the
tape. The proof relies on the fact that the observational behavior of
the TM over an unlnown input can produce only a finite number of
different cases. Hence, though the TM has full Turing power just by
relying on the rest of its tape, its information on the input, which
can be any string in $\Sigma^*$, is finite, so it can compute only on a
finite number of different cases. This gives a different view of the
finite character of regular languages, behavioral rather than
structural.

We assume that the TM accepts when it enters an accept state.

Proof.

We define an input restricted computations (IRC) as a (read-only)
computation of the TM such that the TM head stays on the input part of
the tape, except possibly for the last transition that may move it to
a cell immediately at the left or the right of the input area.

A left input restricted computations is an IRC that starts on the
leftmost symbol of the input. A right input restricted
computations is an IRC that starts on the rightmost symbol of the
input.

We first prove that, for left input
restricted computations that start in state $p$, the following
languages are regular:

the language $K_{Lp\to Lq}$ of input strings such that there is a left input
restricted computation, starting in state $p$, that ends on the first cell left of the
leftmost input symbol in state $q$;
the language $K_{Lp\to Rq}$ of input strings such that there is a left input
restricted computation, starting in state $p$, that ends on the first cell right of the
rightmost input symbol in state $q$;
the language $A_{Lp}$ of input strings such that there is a left input
restricted computation, starting in state $p$, that reaches an accept
state.

And similarly, for right input restricted computations starting in
state $p$, the following similarly defined languages are regular:
$K_{Rp\to Lq}$, $K_{Rp\to Rq}$, and $A_{Rp}$.

The 6 proofs rely on the fact that two-ways non-deterministic finite
state automata (2NFA) recognize regular sets (see Hopcroft+Ullman
1979, pp 36-41, and execise 2.18 page 51). A 2NFA works like a
read-only TM on a tape limited to its input, starting initially from
the leftmost symbol, and accepting by moving beyond the right end in
an accepting state.

In each of the 6 cases, the proof is done by building a 2NFA that
mimics the input restricted computations, but with some extra
transitions to make sure it can start from the leftmost cell and
accept the language by exiting from the rightmost end in an accepting
state. For the $K_{??\to ??}$ languages, the original accepting state
of the TM are changed into states leading to a halting non-accepting
computation. In two cases, it may be necessary to add an extra cell
with a new guard symbol on the left to detect TM computations that
would terminate on the left end, so as to make them terminate on the
right end.

These languages are defined for all combinations of states $p$
and $q$ of the original Turing machine. They represent all that can be
observed (hence known and computed on) of the input by the TM.

If $k$ is the number of states, we thus define $4k^2$ languages
$K_{??\to ??}$ and $2k$ languages $A_{??}$, hence a total of $4k^2+2k$
languages. Actually, some of these languages can be equal.

These are the only possible input restricted computations of the TM
starting on one end of the input. Hence the computations induced by each input string (outside the input section of the tape) are
characterised by the set of such languages the input belongs or does not belong to, hence by an
intersection of each of these $4k^2+2k$ languages or its complement in $\Sigma^*$. All these intersections are finite intersections of r$4k^2+2k$ regular languages, or their complement which are also regular, and are therefore regular.

As a consequence, the set of these intersections defines a partition
$\mathcal P$ of $\Sigma^*$ into at most $2^{4k^2+2k}$ regular languages
(at most because some initial languages may be equal, and some
intersections may be too). All strings belonging to the same
equivalence class can produce exactly the same behavior, as seen from
the ends of the input. This implies that they cannot be distinguished
for computation of the Turing Machine, if you abstract away what
happens in the read-only input area.

If we take two strings $u$ and $v$ in the same equivalence class of
$\mathcal P$ , we can prove, by induction on the number of times the
input area is entered, that for any accepting computation of the TM on $u$,
there is an accepting TM computation on $v$ that is identical everywhere outside
the input area. Hence, either all strings of an equivalence class are
accepted, or none is. As a consequence, the language accepted by the
TM is a union of equivalence classes of $\mathcal P$. Hence it is a
finite union of regular languages, and thus it is a regular language.

To be very complete, we skipped the case of the empty input
string. In this case, we just have a normal TM, that can read or write
anywhere. If it reaches an accepting state, the empty string is in
the language, else it is not.  But that has little effect on the fact
that the language recognized is regular.

Of course, it is not decidable whether an equivalence class is or is
not in the language (the same holds for the empty string). This is a
non constructive proof.

QED

Turing machines with read-only tapes accept only regular languages

This is subsumed by the previous result. It is kept as it uses a different approach, probably less elegant, and helped me in finding the previous proof by understanding what matters. But it can well be skipped by readers. However, one advantage of this proof is that it is a constructive proof producing a FSA accepting the language. A sketch of a similar proof is given by Hendrik Jan in his answer to a previous similar question, which assumes the whole tape was read-only.

I assume that the blank symbol that is on the unused part of the tape
is never part of the input. This symbol is noted here $\Box$. The TM
is supposed to accept when it reaches an accepting state.

The first step of the proof is to show that the head need not ever
leave the input area of the tape. We thus analyze what happen when the
head moves off the rightmost input symbol. The analysis when moving
off the leftmost one is identical.

If we consider that the head has moved on the first blank cell on the
right of the input, the TM being in state $q$, we have to understand
what can happen. There are actually three cases, that may be
simultaneously possible when the TM is non-deterministic:

the TM keeps computing for ever, without the head ever coming coming
back on the input part of the tape;
the TM reaches an (a) accepting or (b) stops in a non-accepting state;
the TM head ultimately comes back on the rightmost cell of the
input,  the finite control being in state $r$.

So we have to analyze the behavior of the TM finite control, when
computing on a blank half-tape, starting in state $q$ on the leftmost
cell of a blank half-tape, infinite towards the right.

Since the TM does not write, and reads only the blank symbol $\Box$,
all the finite control can do is move left or right, and
configurations are differentiated only by the position of the head,
i.e. by an integer. The tape can be replaced by a counter, starting at
$1$, that is incremented when the head moves right and decremented
when it moves left, provided we consider only transitions that require
the blank symbol on the tape. If the counter goes down to $0$, that
correspond to a case of the head coming back on the rightmost input
symbol.

A first remark is that we can ignore computations that do not
terminate (case 1) or that terminate with rejection (case 2.b) since
termination with acceptance is the only relevant case for accepting a
string. So we only want to know whether the counter can go down to
$0$, and in what state, or whether the computation can reach an
accepting state.

We represent the relevant part of the finite state control by a
directed graph where the vertices are the states of the TM, and where
the edges are the blank transitions, with a weight +1 or -1 depending
on whether the head is supposed to move right or left.

We define $A_R$ the set of state $q$ from which an accepting state
can be reached with a positive weighted path.

We also compute the set $E_R$ of all pairs $(q,r)$ of states such that
there is a path of weight $-1$ from $q$ to $r$, but no prefix of that
path has a negative weight.

Then we modify the finite state control of the TM as follow (ignoring now
all transitions on blank symbol $\Box$):

We create a new accepting state $q_A$ with no transitions.

For every transition  $p,a\mapsto R,q$ you add a transition
$p,a\mapsto R,q_A$ if $q\in A_R$ (i.e. an acceptance is possible if
you are on the rightmost symbol).

For every transition $p,a\mapsto R,q$, and every pair $(q,r)\in E_R$
you add a dummy-transition $p,a\mapsto S,r$, where $S$ indicates that
the head should not move. Since this is not an allowed move with most
automata formalizations, these dummy states can be eliminated by
transitive closure afterwards.

Once this is completed, we proceed to remove the dummy
transitions. For every tape symbol $a$, we build the set
$F_a=\{(p,r)\mid \text{ there is a dummy transition } p,a\mapsto
S,r\}$, and we consider the transitive closure $F_a^*$ of the relation
defined by $F_a$. Then, for every transition $r,a\mapsto L,s$ of the
original TM, and every pair $(p,r)\in F_a^*$, we add a new transition
$p,a\mapsto L,s$. Then all dummy transitions can be removed.

We proceed similarly for the moves of the head left of the input part
of the tape, thus reversing left and right, and exchanging $+1$ and
$-1$  in the graph weights.

Once this has been done, we remove completely all transitions on blank
cells, since the corresponding computation are short-circuited by the
new transitions. And we now have a new TM with a head that stays on the
input all the time, except when accepting with state $q_A$, and still
recognizes the original language.

We now have to do a few cosmetic changes, so as to make this TM behave
exactly like a two-ways NDA (acceptance is only by exiting the input
on the right into an eccpting state). Then we can rely on the on the
know equivalence between 2-NDA and FSA (see for example Hopcroft+Ullman 1979, page 40) to obtain the proof that the
language is regular.

QED


Finding Statistical Signifigance for a Classifier I recently did work in the area of machine learning for one of my jobs and was able to build a classifier which evaluated to an F score of 85%. I also have access to correctly and incorrectly classified instances. My boss would like to make sure my classifier is good and and test it for statistical significance. I'm not quite sure what he means by this. I have taken a course in statistics quite some time ago where I did hypothesis testing and stuff with confidence intervals. Do you think that's what he means or does he want me to compare it with other algorithms? I don't want to say what kind of data set I am working with but it's comparable to something such as predicting spam or ham for email messages.

Any help or guidance on this question would be greatly appreciated. I am pretty new to the area of computer science research. But am I right in saying that statistics are used quite a lot to evaluate these types of things?

Thank you!

You can take a look at McNemar's Test or a Bayesian Testing. If you are comparing two or more classifiers, you can perform a to evaluate their performances.

Evaluating learning is actually a pretty wide research topic. A good book to refer to would be Japkowicz-Shah. This is a really nice book on evaluating classifiers and performances. To get some idea about the topic, take a look at this ICMLA talk.

If this is a one time thing, get done with McNemar or Bayesian test, however if you continue to work in the field, do see the book.

P.S. ask you boss if he means any real stat tests (like those mentioned above). Once I was working on a classifier, my professor asked me to evaluate its performance, after a long period of pain and agony of cluelessness, it turned out he just wanted me to test it on other 'toy problems'.


Complexity of vector comparison A question on SO about complexity of sorting vectors of vectors got me thinking about the complexity of comparing 2 vectors.

Let's consider vectors of average size 1) N.

The first formula we get for the comparison of 2 vectors is O(N), but my intuition says it could be lower. Worst case scenario is N comparisons (vectors are equal), but best case scenario is 1 comparison (vectors differ by first element). Obviously the range of values held is very important here. A vector of 64 bits integers (domain of 2^64 values) is much much more likely it will end the comparison early on than say a vector of 1s and 0s (domain of 2 values).

Let M be the size of the domain (number of values each element can hold; the size of the alphabet)

Now when we consider that M is fixed (which it is) we might be tempted to say that the complexity is still O(N), no matter how large M is. It may have a very small factor O(f*N), but it is still O(N). Mathematically we consider the greatest power in the polynomial. Intuitively a large enough N will hide the factor (which is the probability of 2 elements being equal, or a product of probabilities, correct me if I am wrong).

But... in real life (computation real life) a vector doesn't have unbounded size. A 64 bits integers vector of size 2^64 (N = M = 2^64) would need about 10^8 terra and even a 32 bits integers vector of size 2^32 (N = M = 2^32) would require 16 giga. So I would say it is safe to assume 2) that N < M: the size of the vector is less, much more less than the size of the alphabet.

(for me, intuitively that means that the time complexity doesn't get the chance to "explode" because of the very small factor and because N doesn't get the chance to get sufficiently big - compared to M)

So considering N < M does this mean that for a large fixed alphabet (e.g. 2^32 or 2^64) we can recompute the complexity of vector comparison to something lower than O(N)?

Or am I way off?

1) size of vector = number of elements (not size in bytes)

2) for vectors of large ints and for most real life uses (completely ignoring the rare applications that deal with very very large vectors)

extra) I think it goes without saying that element comparison is O(1)

Normally, in asymptotic analysis, it's most typical to analyze the worst-case running time.  It is correct to say that the worst-case running time of comparing two $N$-vectors is $\Theta(N)$; and not any less.

However there's nothing saying you have to focus on worst-case running time.  For instance, perhaps you are interested in the average-case running time (also known as expected running time).  In this case the answer will be $\Theta(1)$ if we assume that the vectors are uniformly distributed, as you predicted.

However average-case running time is tricky.  The expected running time depends on the distribution of values, so you must specify a distribution before you can begin the analysis.  If the distribution isn't uniform, then the expected running time might be very different.

Also the expected-running time doesn't add up like you might think.  What happens if you run Quicksort on a list of vectors?  Can we say that Quicksort does $\Theta(n \log n)$ comparisons on average, and each comparison takes $\Theta(1)$ expected time, so Quicksort on a list of vectors will take $\Theta(n \log n)$ time?  No, that doesn't follow.  Quicksort will tend to move similar vectors closer to each other, so as you get to later stages in the algorithm, it's possible that you might be mostly comparing vectors that are similar to each other.  In particular, the two vectors you're comparing won't be uniformly distributed; they'll come from some joint distribution which tends to make similar vectors more likely.  Of course similar vectors are (on average) slower to compare than independently uniformly-random vectors, so there's no longer any guarantee that every comparison takes $\Theta(1)$ time on average.

So, average-case running time analysis can be a lot trickier to get right than worst-case running time.  Beware!


Is repetition the origin of countability? The original question was "Do all non-regular languages have an uncountable number of strings?".

How can someone prove that..? I am squeezing my head but I can't figure it out.

And the other side of the coin: is a language always regular, if it has a countably infinite number of strings?

A bit more generally: is repetition (DFAs) the origin of countability (and/or vice versa?) and if so, why?

Thank you in advance for your help.

I assume by countability, you mean a set being countably infinite, like $\mathbb{N}$.

All languages over a finite alphabet are countably infinite, whether they are regular or not.

It's easy enough to show that we can encode any string in $\mathbb{N}$: just take map its letters onto $\{1,2,\ldots\}$ and interpret the string as a base-$(n+1)$ number for an alphabet with $n$ letters. (Starting at $1$ avoids the problems with multiple $0$s on the left side of a number). You can also use Gödel numbering, which is simpler but less efficient.

It's important to distinguish languages themselves from the set of languages:

Any language over a finite alphabet is countably infinite (or finite)
There are an uncountably infinite number of languages over any finite alphabet
Any class of languages we describe with a finite representation (including DFAs, CFGs, Turing Machines, or even logic statements) is countably infinite. So there are more languages than we will ever have ways to talk about or describe.

So no, repetition is not the origin of countability. Even undecidable languages are countably infinite.


How does the OS determine the CPU burst time of a process? This question is related to OS. After having solved many problems in CPU scheduling I was wondering how does the CPU know the burst time of all the processes in the main memory before executing them?

Selecting a process among a pool of processes using some scheduling algorithm is done based on CPU burst of each process(SJF,SRTF etc). And I'm aware of the predictor formula. And yet I'm trying to get the whole picture as clearly as possible.
How does that equation help choose which process is to be executed next?

Bursts values are needed for Shortest Job First (SJF) or Shortest Run Time First (SRTF) type scheduling. The burst is an estimate based on an initial starting default burst value and actual historical run values.  A process is assigned a default estimated value for its first burst and after it has run the actual burst is known.  The last estimated burst and the last actual burst are averaged to provide the process's next estimated burst.  This next estimated value is used for the next scheduling choice.  Assuming the actual bursts are roughly equal, as the process runs it's estimated burst will more closely approximate the actual value since the averaging process moves the estimated burst towards the actual value.   Of course if the actual burst for the process is somewhat random then the estimated burst will end up being closer to a median of the long and short burst times for the process.  As processes continue to run they will tend to move into either the long burst group of processes or the short burst group.

For example, when a process is created there is no historical information so it's burst value is set to a default of 10.  If the process always has an actual burst time of 20, then after the first scheduling period the estimated burst value assigned to the process will be (10+20)/2 = 15. The second run it will get (15+20)/2 = 17.5 estimated burst and so on. Each pass will move the estimate closer to the actual time required.

I probably wouldn't choose this method for scheduling a general purpose system, preferring instead a combined priority/quantum scheduling arrangement.  With SJF, a busy system with many short burst jobs could starve the longer burst CPU intensive jobs.  And if a job had short previous run times then got into a compute intensive loop, even other "short" jobs could wait excessive times before getting CPU time.  It can work well for systems that aren't excessively CPU bound and for systems where the process run times are reasonably consistent.

In a priority/quantum round robin based systems, jobs with the same priority are given at lease some CPU time, but will relinquish the CPU to other equal priority processes when it's quantum ends and will wait for its turn to come around again. If a higher priority process needs CPU time, it can preempt lower priority processes.  Various priority boosting methods can prevent complete starvation of low priority jobs on busy systems.


Does minimum cost flow problem work for real valued edge weights/costs? I'm a bit confused about the definition of the Minimum Cost Flow problem, in terms of the edge cost (or weight) values.

I don't remember a integral requirement on the cost/weight values for the edges when first learning the problem. But when I start to look for implementations, most algorithmic code I found require the edge weights to be integers. (I haven't delved into Simplex or LP related code though). For example, in here, and here, weight values are defined as int cost; and typedef long long int price_t; ... price_t _cost; // cost of arc;, resp.

Boost Graph Library (BGL) seems to allow different weight types through C++ templates, but the examples in documentation are using integer weight values. The only use of floating weight values I can find is a SO question about the errors associated with using the floating points (https://stackoverflow.com/questions/35746487/). Google optimization tool also has a bug/feature request for floating point weight values, which is closed immediately stating it only supports int64, currently.

Is there a fundamental reason behind this lack of real valued weights in mincost flow implementations (such as complexity)? That is, is the real valued Min Cost Flow more difficult or impossible to solve, or is this just a coincidence?

In the case of the Ford-Fulkerson algorithm, yes, it's due to complexity. When the edge weights/capacities aren't integers, things get really annoying, really fast.

If you allow all real numbers, you can end up with an instance that doesn't terminate. Normally, you augment paths until you can no longer do so. An irrational capacity value could allow the algorithm to continually find smaller and smaller augmenting paths.

Uri Zwick came up with a good example to show this:

  Consider the flow network shown on the right, with source $s$, sink
  $t$, capacities of edges $e_1$, $e_2$ and $e_3$ respectively $1$,
  $r=(\sqrt{5}-1)/2$ and $1$ and the capacity of all other edges some
  integer $M \ge 2$. The constant $r$ was chosen so, that $r^2 = 1 - r$.
  We use augmenting paths according to the following table, where $p_1 =
> \{ s, v_4, v_3, v_2, v_1, t \}$, $p_2 = \{ s, v_2, v_3, v_4, t \}$ and
  $p_3 = \{ s, v_1, v_2, v_3, t \}$.

  Note that after step 1 as well as after step 5, the residual
  capacities of edges $e_1$, $e_2$ and $e_3$ are in the form $r^n$,
  $r^{n+1}$ and $0$, respectively, for some $n \in \mathbb{N}$. This
  means that we can use augmenting paths $p_1$, $p_2$, $p_1$ and $p_3$
  infinitely many times and residual capacities of these edges will
  always be in the same form. Total flow in the network after step 5 is
  $1 + 2(r^1 + r^2)$. If we continue to use augmenting paths as above,
  the total flow converges to $\textstyle 1 + 2\sum_{i=1}^\infty r^i = 3
> + 2r$, while the maximum flow is $2M + 1$. In this case, the algorithm never terminates and the flow doesn't even converge to the maximum
  flow.

(Wikipedia)

The Stoer-Wagner algorithm will work with non-integer capacities, and so will Simplex/LP algorithms.