Show that P is closed against the Kleene star I have that question that looks kinda easy at first but it is quite hard.

  Let $L\in P$. Prove that $L^*\in P$

my approach:

I tried to generate a Turing machine but I got stuck with the thing of the poly time machine, I only managed to create a non-deterministic machine. I know that there is a complicated method with graphs or with dynamic programming, But I am asking for a full proof or a more gentle one, "computational models"-oriented and not with algorithmic approach, but both kinds of proof will be good.

Hint: Use dynamic programming. If the input is $x_1 \ldots x_n$, compute inductively whether $x_1 \ldots x_i \in L^*$. Use the fact that you can check whether $x_{j+1} \ldots x_i \in L$ in polynomial time.


$NL^2 = NDSPACE(\log^2n)$ is closed under complement From Savitch's theorem we have $NL^2 \subseteq L^4$, which is deterministic and thus closed under complement.
From Immerman–Szelepcsényi theorem we have $NL = coNL$.

Why then $NL^2 = coNL^2$

The Immerman–Szelepcsényi theorem states that $\mathsf{NSPACE}(s(n))$ is closed under complementation whenever $s(n) \geq \log n$.


Why can't we simulate an NP oracle with an NP machine? In this question : Does $NP^{NP}=NP$? ,
it says that one of the reason is that we don't know how to detect 'no' answers from the oracle.
Why is that true though? There is an NTM for any language L in NP, that runs in polynomial time. IIRC we can simulate the NTM with a deterministic TM M that runs in exponential time, that tries every non-deterministic option, and decides L... So why can't we simulate the oracle using that M in another NP machine?

Thanks.

You don't have exponential time, what you have is a nondeterministic polynomial time machine.

What you can try to do, in order to simulate the oracle call to $\mathcal{O}\in NP$ on a string $s$, is to run the nondeterminstic polynomial machine $M_\mathcal{O}$ on input $s$. If $M_\mathcal{O}$ returned "yes" then you know $s\in\mathcal{O}$, but if it returned "no", then you cant be sure, and you don't have enough resources to try out all possible branches in an NP machine.


Proving NP-hardness of strange graph partition problem I am trying to show the following problem is NP-hard.

  Inputs: Integer $e$, and connected, undirected graph $G=(V,E)$, a vertex-weighted graph

  Output:  Partition of $G$, $G_p=(V,E_p)$ obtained by removing any $e$ edges from $E$ which maximizes

  $$\max \sum\limits_{G_i \in \{G_1,G_2,...,G_k\}} \frac1{|G_i|}\left(\sum_{v_j \in V_i}w(v_j)\right)^{\!2},$$

  where $G_p=G_1 \cup G_2 \cup \dots \cup G_k$ and elements of $G$ are disjoint.
  $V_i$ is the vertex set for $G_i$ and $w(v_j)$ is the weight for vertex $v_j$

Plain English explanation:
We wish to partition a graph by removing $e$ edges to maximize an objective. The objective computes for each of the resulting disjoint subgraphs the sum of the vertices for the subgraph, squares that value, and divides by the cardinality. Finally we sum this over all subgraphs.

So far I have attempted to reduce from NP-hard problems such as ratio-cut, partition (non-graph problem), and max multicut. I've also attempted to show special cases of the problem are NP-hard (less ideal). The reason I suspect this problem to be NP-hard (besides most graph partitioning problems being NP-hard) is the presence of the cardinality term and cross terms between partition weights. Any input/problem suggestions would be helpful. A NP-hard proof for any kind of specific graph would be useful.

Let's reduce multiway cuts problem, a variant of minimum $k$-cut, to your problem.  In particular, consider the minimum 3-way cut problem, which is NP-hard for all edge weight equal to 1 (see The complexity of multiway cuts).

A (minimum) 3-way cut problem is: given a graph $G = (V,E)$ and terminals $s_1,s_2,s_3\in V$, find a minimum set of edges $E'\subseteq E$ such that the removal of $E'$ from $E$ disconnects each terminal $s_i$ from the others.  Its decision version is to find out if it's possible to disconnect $s_1,s_2,s_3$ by removing no more than $w$ edges, where $w$ is a part of the input.

Given graph $G$, terminals $s_1,s_2,s_3$ and integer $w$, we would like to reduce the 3-way cut problem to your "strange graph partition problem".  For each terminal $s_i$, we add $N$ more verteces to be its neighbors.  As hinted by its name, $N$ would be a sufficiently large number.  The weight of all verteces are 0 except for $s_1,s_2,s_3$, whose weights are $1,10,100$ resp.  Denote this new graph by $G'$.  It's obvious that $s_1,s_2,s_3$ can be disconnected by removing $w$ edges in $G$ if and only if they can be disconnected by removing $w$ edges in $G'$.

If a partition $G'_p$ of $G'$ disconnects $s_1,s_2,s_3$, its score is roughly $10101/N$, or more precisely, no less than $$\frac{10101}{N+n}$$
as the part containing $s_i$ has no more than $N+n$ verteces, where $n$ is the number of verteces in $G$.  On the other hand, if a partition $G'_p$ fails to disconnect $s_1,s_2,s_3$, its score is no more than $$\frac{10060.5}{N-w}$$.  When $N$ is sufficiently large, $\frac{10101}{N+n} > \frac{10060.5}{N-w}$, so $G$ can be 3-way partitioned by removing $w$ edges if and only if $G'$ has a partition removing $w$ edges, whose score is at least $\frac{10101}{N+n}$.


Transitivity of concat comparison I am trying to solve the problem of finding the permutation, amongst all possible ones, of an array of strings, where the concatenation of them compares smallest lexicographically. I solve it with an sort with the following comparison

def concat_cmp(x, y):
    return cmp(x + y, y + x)

+ is the string concat operator.

The solution passed all the test cases, but I cannot prove its correctness. Specifically, I cannot prove that this binary relation is transitive. Any help?

We denote the concatenation of $x$ and $y$ by $xy$. Your relation is $x \prec y$ iff $xy < yx$ (where $<$ is the lexicographic order). You want to show that $x \prec y \prec z$ implies $x \prec z$. Suppose therefore that $xy < yx$ and $yz < zy$. Our goal is to show that $xz < zx$.

Say that two strings $s,t$ are incompatible if neither is a prefix of the other. If $s \prec t$ and $s,t$ are incompatible then there is an index on which they differ, and the first such index $i$ satisfies $s_i < t_i$. Conversely, if there exists an index on which $s,t$ differ and the first such index $i$ satisfies $s_i < t_i$ then $s,t$ are incompatible and $s \prec t$.

The proof is by induction on $|x|+|y|+|z|$. We consider several cases.

Case 1. $x,y$ are incompatible, and $y,z$ are incompatible. Let $i$ be the first index on which $x,y$ differ, and let $j$ be the first index on which $y,z$ differ. Then $k = \min(i,j)$ is the minimal index on which $x,z$ differ and $x_k < z_k$, implying $x \prec z$.

Case 2. $x = yw$. In this case $xy < yx$ implies $ywy < yyw$, and so $w \prec y$. Induction shows that $w \prec z$, and so $xz = ywz < yzw < zyw = zx$.

Case 3. $z = yw$. In this case $yz < zy$ implies $yyw < ywy$, and so $y \prec w$. Induction shows that $x \prec w$, and so $xz = xyw < yxw < ywx = zx$.

Case 4. $x = zw$. In this case $xy < yx$ implies $zwy < yzw < zyw$, and so $w \prec y$. Induction shows that $w \prec z$, and so $xz = zwz < zzw = zx$.

Case 5. $z = xw$. In this case $yz < zy$ implies $xyw < yxw < xwy$, and so $y \prec w$. Induction shows that $x \prec w$, and so $xz = xxw < xwx = zx$.

Case 6. $y = xw$ and $x,z$ are incompatible. In this case $xy < yx$ implies $xxw < xwx$, and so $x \prec w$. Moreover, $yz < zy$ implies $xwz < zxw < zwx$. Since $x,z$ are incompatible, there exists an index on which they differ, and the minimal such index $i$ must satisfy $x_i < z_i$. It follows that $x \prec z$.

Case 7. $y = zw$ and $x,z$ are incompatible. In this case $yz < zy$ implies $zwz < zzw$, and so $w \prec z$. Moreover, $xy < yx$ implies $xwz < xzw < zwx$. Since $x,z$ are incompatible, there exists an index on which they differ, and the minimal such index $i$ must satisfy $x_i < z_i$. It follows that $x \prec z$.


How to create a suffix tree by hand I will soon have to be able to draw a suffix tree of a word on an exam. I tried to understand the different algorithms available, but they seem rather complicated to do "by hand".

I do not see a simple way how to draw such a tree. Is there a simple step by step method for people not knowing the algorithms?

Here is how to draw the suffix tree for the example $abaab\$$ mentioned in the lecture notes appearing in greybeard's comment.

Root. There are two characters appearing in the word, $a,b$, so the root has two outgoing edges, labeled $a$ and $b$.

Root->a. Following $a$, we have both characters $a,b$ appearing in the word. So this note has two outgoing edges, labeled $a$ and $b$.

Root->a->a. There is only one suffix $aab\$$ starting with $aa$, so we replace this node with a leaf, and modify the edge label to $ab\$$.

Root->a->b. There are two suffixes $abaab\$$ and $ab\$$ starting with $ab$. Correspondingly, we add two children with edges labeled $aab\$$ and $\$$.

Root->b. Following $b$ we have the two suffixes $baab\$$ and $b\$$. Correspondingly, we add two children with edges labeled $aab\$$ and $\$$.

The general method is similar. At each node $w$, we add children corresponding to all possible continuations of $w$ in the word. If there is only one continuation possible, we modify instead the edge label. This algorithm is easy to implement by hand, but could be hard to implement in linear time on a computer.


Why is it that Ternary search trees are memory efficient? I'm trying to figure out why ternary search trees are memory efficient. I have tried to read up on this, but all articles I find only state it's memory efficient compared to tries, but not why.

I believe it has something to do with the middle node, and with its ability to handle duplicate keys in a better way than tries, but I'm still not sure.

Why are TST's more memory efficient then tries?

Tries

Tries store strings character by character. See the figure below of a tree that represents the same set of 12 words.

Each input word is shown beneath the node that represents it. In a tree representing words of lowercase letters, each node has 26-way branching. Searches are very fast: A search for "is" starts at the root, takes the "i" branch, then the "s" branch, and ends at the desired node. Unfortunately, search tries have exorbitant space requirements: Nodes with 26-way branching typically occupy 104 bytes, and 256-way nodes consume a kilobyte. Eight nodes representing the 34,000-character Unicode Standard would together require more than a megabyte!

Ternary Search Trees

Ternary search trees combine attributes of binary search trees and digital search tries. Like tries, they proceed character by character. Like binary search trees, they are space efficient, though each node has three children, rather than two. A search compares the current character in the search string with the character at the node. If the search character is less, the search goes to the left child; if the search character is greater, the search goes to the right child. When the search character is equal, though, the search goes to the middle child, and proceeds to the next character in the search string.

The figure above shows a balanced ternary search tree for the same set of 12 words. The low and high pointers are shown as solid lines, while equal pointers are shown as dashed lines. Each input word is shown beneath its terminal node. A search for the word "is" starts at the root, proceeds down the equal child to the node with value "s," and stops there after two comparisons. A search for "ax" makes three comparisons to the first letter ("a") and two comparisons to the second letter ("x") before reporting that the word is not in the tree.

Searching for a string of length k in a ternary search tree with n strings will require at most O(log n+k) comparisons.

The primary challenge in implementing digital search tries is to avoid using excessive memory for trie nodes that are nearly empty. Ternary search trees may be viewed as a trie implementation that gracefully adapts to handle this case, at the cost of slightly more work for full nodes. Ternary search trees combine the best of two worlds: the low space overhead of binary search trees and the character-based time efficiency of digital search tries.

Hope it helps! Reference: Link


How to make the standard DP algorithm for 0/1 Knapsack make larger steps? The standard knapsack problem solution is O(nW) where we will increment the weight +1 at a time to get to the solution.

Is there any approach to the knapsack problem that does not require incrementing weight +1 at a time.

e.g. One way that I can think of is to divide all the numbers by its common

Capacity = 100 weights = [5, 10, 20] -> Capacity = 20 weights = [1, 2, 4]

Your assumption is wrong; the dynamic programming algorithm does not do that. It computes $m(n,W)$ according to the recurrence

$\qquad\displaystyle
  m(i,w) = \begin{cases}
    0, &i=0 \lor w=0; \\
    m(i-1,w), & w_i > w; \\
    \max \{ m(i-1,w), m(i-1, w - w_i) + v_i \}, &w_i \leq w .
  \end{cases}
$

Here, $(w_1, v_1), \dots, (w_n, v_n)$ are the weight-value pairs and $W$ is the knapsack size. Note how $m(i,w)$ is the maximum value that can be achieved with items $1, \dots, i$ and up to weight $w$; prove that by induction.

You can note two things:

The algorithm does not "move towards" $W$ in a straight fashion; it investigates many "paths" from $0$ to $W$ in an interleaved fashion, optimizing locally.
When it makes a stept, it does not have to be by $1$; all steps correspond to a $w_i$.


Are URI's a regular language? Do URI's, as defined in rfc3986, form a regular language?

How can I tell?

There's a BNF grammar provided, but I don't know how to check that it has a unique representation of every URI, or that it describes a regular language.

Here are some checks you can perform for yourself:

Is there any recursion in the rules?
No: The language is finite, hence regular.
Can the recursions all be written in the form of $A \to \alpha B$, with $\alpha$ a terminal string and $A$, $B$ non-terminals?
Yes: The grammar is (or can be transformed into an equivalent) right-regular (one), hence the language is regular.

If there are constructs like $A \to \alpha B \beta$ or even $A \to \alpha A \beta B \gamma$, then you'll have to look more closely, and there's no easy way: deciding whether a context-free grammar generates a regular language is, in general, undecidable (cf. Greibach's theorem).
See our reference questions for techniques for showing either direction.


Is $L=\{\langle M \rangle|M$ makes more than 10 steps on some input$\}$ decidable? I want to show that it satisfies Rice's theorem:

(i) $L$ is non-trivial, since $\langle M\rangle \notin L$ where $L(M)=\emptyset$, as $M$ halts/rejects any input string in the first step.

(ii) if $L(M_1)=L(M_2)$ where $M_1$ and $M_2$ are turing machines, then $M_1$ makes more than 10 steps on some input iff $M_2$ makes more than 10 steps on some input.

I'm not sure if the second condition is true, and if so, why?

I know that you can always create redundant states/transitions by moving the read-write head go back and forth without changing anything, thus increasing the number of steps on a given input but giving the same outcome. But I'm not sure if you can always "shorten" a turing machine.

Your first statement is true. The second is not true. You can construct infinetly many TMs accepting the same language by introducing redundant states and transitions (as you already mentioned). "Minimizing" a TM has nothing to do with the second statement since two machines accepting the same language do not have to be identical and minimizing a TM gives you another machine while you compare M1 and M2.


Recurrence relation complexity I just learned about recurrences and I just can't solve this problem. I have this recurrence relation:

$$
T(n) = \begin{cases}
k\cdot T(\frac{n}{k}) & n > 0\\
1 & n = 0\\
\end{cases}
$$

where $k$ is a constant number.

I tried drawing a recurrence tree or replacing for lower $n$s but no success. I hope you can help me with an idea!

Suppose that $n$ is a power of $k$, say $n = k^t$. Then
$$
T(k^t) = kT(k^{t-1}) = k^2T(k^{t-2}) = \cdots = k^tT(1) = k^t,
$$
assuming a base case of $T(1) = 1$. So for powers of $k$, we have $T(n) = n$. You can also prove that by induction: if $T(n/k) = n/k$ then $T(n) = kT(n/k) = k(n/k) = n$.


Is the length of the shortest quine in a programming language computable? The length of the shortest program in a given (fixed) programming language that produces a given output is that output's Kolmogorov complexity, which is not a computable function on the set of possible outputs.

This is a classical result and is easily proven; a proof outline appears in the Wikipedia article on Kolmogorov complexity.

My question is about a related complexity metric operating on programming languages rather than program outputs. A quine is a program that outputs its own source code (and nothing else). Every Turing-complete programming language is capable of formulating quines (by Kleene's recursion theorem). We can therefore define the quine complexity of a programming language as the length of the shortest quine possible in that language.

Is the quine complexity a computable function on the set of programming languages?

My gut tells me that it is not, but the standard approach used to prove the uncomputability of the Kolmogorov complexity metric does not seem to work here.

You need to formally define the computational problem. It appears that the input is "a programming language" and the output is the length of the shortest quine in that language. But how is the programming language specified? The only way I can think of is to specify it by giving the encoding of a Turing machine that interprets the language. So, then, our input is $\langle M\rangle$ and our output is $\min\,\{|x|\mid M(x)=x\}$. This is uncomputable: it's uncomputable even whether $M(0)=0$


What algorithm is suitable for very small scale, time dependent optimization? I have a time-dependent (dynamic) optimization problem:
$$
f_t : [0;1]^2 \mapsto \mathbb{R}^+;  t \in [1, \dots, n]
$$
$f_t$ is to be maximized. That is for each $t$ I would like to find a relatively high value of $f_t$. Mostly, $f_t$ is a relatively simple, continuous, unimodal function. It changes with time, but not much and not predictably. I know only that the scale of the function goes down exponentially.

The problem is that at each time I can perform only a handful (5-10) of evaluations of $f_t$.

I am absolutely new to dynamic optimization and therefore I am looking for some simple approach. Any suggestions or references to literature are welcome.

I have considered particle swarm optimization, but the papers on PSO I read are usually dealing with at least 10 dimensional problems, so PSO may be an overkill. Also I do not know if it is appropriate to use just 5-10 particles.

Many optimization procedures are based upon successive approximation: they start with a value of $x$, and try to successively refine $x$ to move it closer and closer to the optimum.  For instance, hill climbing and gradient ascent both have this structure.

You can use this structure to solve your problem.  Let $x_t$ be the maximum for $f_t$.  Then you can use $x_t$ as the starting point (the initial approximation) when looking for the maximum for $f_{t+1}$.  Now iterate, using the maximum for the previous time period as the starting point for hill climbing / gradient ascent / .... in the next time period.  If the maximum for $f_{t+1}$ is close to the maximum for $f_t$, this might work reasonably well.

There are many different possible ways to instantiate this basic approach.  Here are some possible examples of how this might look:

With gradient ascent, you evaluate $f_{t+1}$ three times at three points near $x_t$: e.g., at $x_t$, $x_t+(\varepsilon,0)$, and $x_t+(0,\varepsilon)$.  You use the result to estimate the gradient around $x_t$, and then move in the direction of the gradient.

As a possible optimization/variation, you might align the axes in the direction of the gradient for $f_t$.  For instance, if the gradient was maximum in the angle $\theta$ for $f_t$, you might evaluate $f_{t+1}$ at the three points $x_t$, $x_t+(\varepsilon \cos \theta, \varepsilon \sin \theta)$, $x_t + (\varepsilon \cos (\theta+\pi/2), \varepsilon \sin (\theta+\pi/2))$, then use those values to estimate the gradient.
As another possible optimization, you could follow this with a line search.  Suppose $\delta$ is the direction that maximizes the gradient.  Then you could evaluate $f_{t+1}$ at $x_t,x_t+\delta,x_t+2\delta,x_t+3\delta,x_t+4\delta,\dots$, stopping at the first one that stops providing any improvement.  Or, you could evaluate $f_{t+1}$ at $x_t,x_t+\delta,x_t+2\delta,x_t+4\delta,x_t+8\delta,\dots$.  You could even follow this with an iteration or two of binary search to find the best stopping point, though that might not be worthwhile.
If you are trying hill-climbing, you will do something simple like this: pick a random point $x'$ in the neighborhood of $x_t$, and if $f_{t+1}(x') > f_{t+1}(x_t)$, then move to $x'$.  You can repeat this a few times.

Of course, you can combine these methods.  There may be many other variations you could try.  I would suggest that you read about methods for optimization, brainstorm other similar methods, and then try them all to see which work best.

Also, you might want to try a simulation: choose $f_t$ that you believe to be representative and where you can evaluate them as many times as desired to find the true maximum and their shape, and then simulate each of these strategies to see how well they work.  You might also want to visualize the shape of the $f_t$ and what these strategies are doing (what points they are visiting), in case that helps you refine them or choose suitable constants that are appropriate for your particular application domain.


Two's complement max with a different base Working with fixed size integer representations,
use a number system with b-complement notation, base b = 9 and
n = 4 digits.
 What is the smallest number that can be represented in this number system?
State the number in decimal, and also express it in this number
system.
I assume that it will be 0888 for max, and 8000 for min. If I am right, then what is the max number of integers that I can represent using this notation.

As long as different 4 digit numbers in base b represent different decimal numbers, the particular notation one uses is not relevant to see how many integers can be represented. I'm not sure how the two-complement notation generalizes to the b-complement notation, but if the above property holds, then clearly there will be 9^4 representable integers.

My guess is that the first digit does not need to be 0 or 8, it can be any digit. That is, I think one could use the following encoding:

0000 0
...
4444 MAX
4445 MIN = -MAX
4446 MIN+1
...
8888 -1


Linear Regression. Why do we take sum of errors to compute the cost? While calculating the cost in linear regression (for either with multiple features or a single one using gradient descent) we compute the cost by squaring and summing up the cost related to each training set. What is the point of summing up the cost related to each training example is what I do not understand.
Why not just calculate the cost for each training example individually ?

( I am following the Machine Learning course taught by Andrew Ng on coursera. )

You can usually view the cost function as the average squared error over some dataset with $N$ pairs of data, thus being defined as:

\begin{align}
J &= \frac{1}{N} \sum_{i=1}^{N} \left(f(x_i,\beta) - y_i \right)^2
\end{align}

We want the average error of our model (for all data we have) to decrease as we fine tune values for $\beta$, the vector parametrically defining how our model $f(\cdot,\cdot)$ works. So we like to look at all the data at once since it can be used to make changes to $\beta$ that should actually make the model improve as a whole.

If we instead made the cost function based on a subset of the dataset, you would end up with a cost function that may sub-optimally modify the value for $\beta$. This sub-optimal behavior may make us take longer to get to a local minimum of the cost function or even diverge from a good solution if you aren't careful with your hyper parameters.

Stochastic gradient descent or mini-batch gradient descent are methods that use a single piece of data or a subset of data from the dataset to make adjustments. These methods have actually found use for really large datasets where the longer convergence time is more worthwhile than the time it takes to do a whole pass on the data to compute necessary gradients and costs.


Description of resolution algorithm as it applies to SAT SAT [5] can be solved with resolution definitively, i.e. if the formula has a true assignment, resolution can find it, and if it cant be satisfied, resolution can show that no assignment exists (at least in exponential time/space.). [4]

  Is there a good fully-self contained description somewhere of solving SAT with resolution?

The descriptions on Wikipedia of resolution are focused on a single logical operation, not how to use it in an algorithm to solve SAT, and the Davis Putnam algorithm is described mostly in terms of 1st order logic. I am looking for a description of solving SAT with resolution that does not refer to 1st order logic, just in terms of boolean input variables. Online description is preferred if possible. The connection with DPLL would be helpful also.

[1] Davis Putnam algorithm, Wikipedia

[2] Resolution in logic, Wikipedia

[3] Davis Putnam Logemann Loveland algorithm, Wikipedia

[4] Is resolution complete or only refutation-complete?

[5] The boolean satisfiability problem

What you are looking for is a proof of the completeness of resolution. Here is one example. The relation to DPLL is that a run of DPLL which terminates in failure can be converted to a resolution proof that the formula is unsatisfiable.


Is writing a compiler for a compact language easier? I am contemplating the project of writing a compiler. I am wondering if, aside from the availability of easy google results, it is easier to write a compiler for a more explicit/verbose language such as ada, compared to a very compact language such as APL, for example.

I should add that i am especially interested in whole-program optimization.

Edit: my question boils down to "do highly abstracted symbols/keywords (as in APL, where a single operator represents a function) make it easier to write a compiler, or is a language with a more traditional syntax (where a function includes a variety of operators) easier?"

In almost every case, the more compact languages like APL will be harder write a compiler for:

On the front end (parser), in the worst case, you have a ton bunch of special cases for your symbols in your parser, and in the best case, you treat them as generic symbols, in which case you're in the exact same parsing position as a language that has
In the back-end, with type checking, optimizers, etc., you either treat your symbols as standard library functions, in which case you're in the exact same place as a more verbose language, or you treat them as parts of the language, in which case you will have a bunch of special cases in your type checker, code generation, etc.

In general, compilers are easiest for smaller languages. This is why most languages feature syntactic sugar, where some features are translated into a subset of your original language at compile time (for example, eliminating for-loops by turning them into while-loops). Many languages also keep code-generation and optimization simpler by compiling their language into a smaller intermediate language after parsing or type checking, then optimizing and compiling that language into machine code.

  I should add that i am especially interested in whole-program optimization.

Syntax will not influence this in the slightest. Parsing is generally the least interesting part of writing a compiler, since there's many solutions for parsing, and once you have things into an Abstract Syntax Tree, what concrete syntax you used is entirely irrelevant. That is, two languages that parse to isomorphic ASTs will be exactly the same for difficulty to optimize.

The only case where having a more compact language could help optimization is if you have a bunch of special cases of known optimizations (e.g. fusion rules) for your operators, but you could just as easily write special cases for standard library functions of a more verbose language.


Why do we do topological sorting to find shortest or longest path in weighted DAG? I was wondering why do we need to do the topological sort before performing relaxing of edges.

Wouldn't it'd be better if we do :
if starting vertex is "s"

queue.add(s)
while(the queue is not empty)
 for every adjacent vertex v of u
   if( dist[v] > dist[u] + weight(u,v) )
       dist[v] = dist[u] + weight(u,v)
       add v to the queue

I had intentionally left out visited[] array

By using this algorithm the expected time complexity would not be O(V+E) as we have to visit an edge multiple times.

queue.add(s)
while(the queue is not empty)
 for every adjacent vertex v of u
   if( dist[v] > dist[u] + weight(u,v) )
       dist[v] = dist[u] + weight(u,v)
       add v to the queue

But by using the topological sorting, we get the order in which the vertices should be traversed so that an edge is visited exactly once. So we could have guaranteed T.C. of O(V+E).

So to solve this problem to work in O(V+E) we use topological sort.

But I think this is not enough, we should also know why to use Topological ordering here and so that it helps in other problems.

Why Topological ordering ?

Topological ordering gives us the order like 0 1 2 3 4 5 then, once we reach a node in this ordering (let's say 4) then we've already computed the shortest path to it (4) as all the edges(as well as paths) of type u -> v (v = 4) and have already been visited.


lambda-calc program which halts on only one input Does there exist a normal-form lambda calculus program $f$ such that

$f (\lambda x . x)$ normalizes
For all normal form $e \ne \lambda x . x$, $f e$ does not normalize

Well nevermind this has an easy answer.

Let $r_n = \lambda x_1 ... x_n . \lambda p . p \: x_1 ... x_n$

Note that for $m < n$, $r_n\: A_1 ... A_m$ normalizes for any normal $A_1 ... A_m$.

Then for any $f$, let $n$ be larger than the number of subterms in $f$.

$f \:r_n$ normalizes, so therefore no $f$ exists which only normalizes for a specific input.


Decoding a binary linear code given its generator matrix Let $C$ be the binary linear code with the following generator matrix

$G= \begin{bmatrix}
    1 & 1 & 0 & 1 & 0 & 0 & 0 \\
    0 & 1 & 1 & 0 & 1 & 0 & 0  \\
    0 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 1
\end{bmatrix}$

I need to decode the received word $r$, $\begin{pmatrix} 1 & 1 & 0 &0 & 0 &1 &1\end{pmatrix}$.

I am really strugggling with this. I know a message $m$ is encoded as $mG$.

So $mG$=$\begin{pmatrix} 1 & 1 & 0 &0 & 0 &1 &1\end{pmatrix}$.

I have tried doing this by eye but couldn't find a single $m$ that I could multiply $G$ by to give me $r.$ Is there another method? Also I know that there must be $2^4=16$ codewords and when I wrote them out this one wasn't in them? Not sure if that helps or maybe I did that wrong?

If you don't want to check all possibilities, you can use row operations to convert four columns of the matrix (of your own choosing) to the identity matrix, which will enable for very quick decoding. The code generated is exactly the same.

In more details, each row operation corresponds to multiplying the generator matrix from the left by some invertible matrix. In all, the effect of row operations is to multiply the original generator matrix by some invertible matrix from the left, say $H = AG$ is the new generator matrix. Since $A$ is invertible, both generator matrices generate the same code. If $r = xH$ then $r = (xA)G$, so if you decode $r$ for $H$, you can also decode it for $G$ very easily.

In your case, the row operations result in the following matrix:
$$
\begin{bmatrix}
1 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 0 & 1
\end{bmatrix} =
\begin{bmatrix}
1 & 1 & 1 & 0 \\
0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 1
\end{bmatrix}
$$

To decode $\begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}$, we simply add the first two rows to get the vector $\begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 0 & 1 \end{bmatrix}$. This shows that the original vector doesn't belong to the code.


Allocating tasks among two people equitably Given that we have 2 people, and 2n tasks, find the minimum time to complete the tasks. Both persons should solve exactly n tasks each and any task j has to be solved before task j+1. Required time complexity is O(nlogn).
E.g- given this input:

A B

5 3

2 1

3 2

1 2

the intended output is 8, because A solves the second and fourth task, and B solves the first and second.

Suppose that the time for completing task $i$ is $a_i$ for $A$ and $b_i$ for $B$. Let $S$ be the set of tasks performed by $B$. The total time required is
$$
\sum_i a_i + \sum_{i \in S} (b_i-a_i).
$$
Your goal is then to find a subset $S \subseteq [2n]$ of size $n$ which maximizes $\sum_{i \in S} (b_i - a_i)$. You take it from here.


Are these languages RE? How would I determine this? Are these languages recursively enumerable?

$L = \{ \langle A\rangle \mid x\in L(A)\implies |x|\leq 13\}$
$L = \{\langle A\rangle \mid L(A) \subseteq \overline{L_{\mathrm{uni}}}\}$, where $L_{\mathrm{uni}} = \{\langle T\rangle x \in \{0,1\}^*\mid x \in L(T)\}$.

How would I prove / disprove that these languages are RE?

Neither of these languages are RE.

Here's an intuitive way to think about this - a language $L$ is RE iff for any string $w$, there is some finite piece of information you could provide about $w$ that could convince a computer that $w$ belongs to $L$.

In the case of language (1), what information could you give me that would convince me that a TM belonged to this language?  To show that a TM belonged to that language, you'd need to convince me that every string ever accepted by that TM has length at most 13.  It doesn't seem likely that there is any finite piece of information you could give me that could convince me that the TM has this property.  (On the other hand, if a TM didn't have this property, it's easy to convince me of this - give me a string that the TM accepts that is longer than length 13, and I could confirm it by running the TM on that string and observing it accept).

To formally prove that language (1) is not RE, you could try doing a reduction from a language that's already known to not be RE.  One good example of this would be the diagonalization language $L_D$:

$$ L_D = \{ \langle M \rangle | M \mbox{ is a TM and } \langle M \rangle \notin L(M) \}$$

This is the set of all descriptions of TMs that don't accept themselves.  You can reduce $L_D$ to your language $L$ using the following reduction: given a TM $M$, build a new TM $N$ that does the following:

  When $N$ receives an input string $w$, it first runs $M$ on $\langle M \rangle$.  If $M$ accepts its own description, then $N$ accepts $w$.  If $M$ rejects its own description, then $N$ rejects $w$.  (Implicitly, if $M$ loops on its own description, then $N$ loops on $w$)

This machine has the property that if $M$ does not accept itself, then $N$ never accepts anything at all, and so $\langle N \rangle \in L$.  On the other hand, if $M$ does accept itself, then $N$ accepts everything, so $\langle N \rangle \notin L$.  This is a mapping reduction from $L_D$ to $L$, and since $L_D \notin RE$, this shows $L \notin RE$.

I'll leave the second of these as an exercise.  Use the same intuition as before to think about why the language isn't $RE$, then try using a mapping reduction from $L_D$ to formalize it.

Hope this helps!


Why the time complexity of Prim's algorithm is not $|V||E|lg|V|$ but $|E|lg|V|$? In the CLRS, time complexity of Prim's algorithm is $O(|V|lg|V|+|E|lg|V|)=O(|E|lg|V|)$.

But, for my understanding, Prim's algorithm iterates $|E|$ times for DECREASE-KEY operation which takes $O(lg|V|)$ times and it leads to $O(|E|lg|V|)$.

So, it iterates $|V|$ times then, I think $O(|E||V|lg|V|)$ is right because whole time complexity is like below.

Initialization of key and predecessor + making a binary heap = $O(|V|)$
EXTRACT-MIN operation = $O(|V|lg|V|)$
DECREASE-KEY operation is iterated for $|V|$ times = $O(|E||V|lg|V|)$

Consequently, $O(|V|+|V|lg|V|+|E||V|lg|V|)=O(|E||V|lg|V|)$.
Why is it $O(|E|lg|V|)$?

From 2 answers, first while loop iterates $|V|$ times and $DECREASE-KEY$ operation iterates $|E|$ times and time complexity of that operation is $O(lg|V|)$ because min heap has to be reconstructed.

From this, I got a $O(|V||E|lg|V|)$ because for loop is in while loop. What your answers are saying is that I don't know $DECREASE-KEY$ operation iterates $|E|$ times, but I know that.

The pseudocode for Prim's algorithm, as stated in CLRS, is as follows:

MST-PRIM(G,w,r)
1   for each u ∈ G.V
2      u.key = ∞
3      u.π = NIL
4   r.key = 0
5   Q = G.V
6   while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9         if v ∈ Q and w(u,v) < v.key
10           v.π = u
11           v.key = w(u,v)

The loop in line 6 will execute exactly $|V|$ times, since $Q$ starts with $|V|$ elements and we remove one each iteration. For each node $u$, the loop in line 8 will execute $\text{deg}(u)$ times, so the DECREASE-KEY operation (lines 10 and 11) will execute at most $\text{deg}(u)$ times.

In total, the loop in line 8 will be executed $2|E| = \sum_{u \in G.V} \deg(u)$
times, and DECREASE-KEY $O(|E|)$ times.

I would suggest you to grab a piece of paper, draw a graph, and run the algorithm on it while counting how many times you do the DECREASE-KEY operation.


Knuth's Algorithm X - why do we backtrack rows but not columns? Knuth's Algorithm X (described here in more details) prescribes that we select a column deterministically (but arbitrary), when we backtrack rows we do not backtrack columns, so we do not have an opportunity, to "rewind", select a different column and try again, during the course of the algorithm.

How can we be sure, that we find all solutions if we do this, and don't miss a few? Or did I get this wrong, and the algorithm cannot actually find every solution? Reading the research paper linked above I got an impression, that it is able to find / enumerate all the solution. So what makes sure we do not miss some of these?

No, it is not necessary to backtrack the columns.

Take an arbitrary solution $X = \{\text{some row indices}\dots\}$.
In the first step the algorithm picks some column $j$, and in the second step it iterates over all rows $i$ with $A_{ij} = 1$, makes the matrix smaller and recursively calls itself for each such row.

Since $X$ is a valid solution, there exists some $i_0 \in X$ with $A_{i_0 j} = 1$. Let's analyze the iteration step, in which the algorithm chooses the row $i_0$. How does the matrix change?

It removes all columns $k$ with $A_{i_0 k} = 1$: this doesn't bother us. $X / \{i_0\}$ is still a valid solution for the smaller matrix.
It removes all rows, that have at least one set $1$ in a same column as row $i_0$: this still doesn't throw away any important stuff. Because we know that all rows in $X$ have the $1$s in different places. So still all rows of the solution will be part of the smaller matrix.

As you see, it doesn't matter how the algorithm picks the column (any choice of column is possible), you will still find a row, that is part of your solution, the solution is still a solution of the smaller matrix. And by induction, we the algorithm will find the solution. Just the order of the rows of the solutions will differ, if we pick some other column. But we will find the same solutions.


Explanation about the condition for connectivity in Erdos Reyni model I am currently studying the Erdos-Reyni model, the $G(n,p)$ model to be specific.

Its easy to understand that all graphs with $m$ edges have generating probability of $p^{m}(1-p)^{n(n-1)/2 - m}$ where p is the probability that there is an edge between a pair of vertices.

What I am not able to understand is the following:

Almost every graph in $G(n, 2ln(n)/n)$ is connected. In other words,
As $n$ tends to infinity, the probability that a graph on $n$ vertices with edge probability $p = 2ln(n)/n$ is connected, as $n$ gets very large.

Any idea how to get this?

If a graph is not connected then there must be a set $S$ of vertices not connected to its complement. Furthermore, we can assume that $|S| \leq n/2$. For a given set $S$, the probability that $S$ is not connected to its complement is
$$
(1-p)^{|S|(n-|S|)} \leq e^{-p|S|(n-|S|)}.
$$
The union bound shows that the probability that some such $S$ exists is at most
$$
\epsilon := \sum_{k=1}^{n/2} \binom{n}{k} e^{-pk(n-k)} =
\underbrace{\sum_{k=1}^{n/4} \binom{n}{k} e^{-pk(n-k)}}_{\epsilon_1} +
\underbrace{\sum_{k=n/4+1}^{n/2} \binom{n}{k} e^{-pk(n-k)}}_{\epsilon_2}.
$$
When $k \leq n/4$, we have $n-k \geq (3/4)n$ and so $$e^{-p(n-k)} \leq e^{-(3/4)pn} = \frac{1}{n^{3/2}}.$$
Using the bound $\binom{n}{k} \leq n^k$, we get
$$
\epsilon_1 \leq \sum_{k=1}^{n/4} n^k \cdot n^{-(3/2)k} =
\sum_{k=1}^{n/4} \frac{1}{n^{k/2}}.
$$
We can estimate this by considering separately $k=1$, $k=2$, and $k \geq 3$:
$$
\epsilon_1 \leq \frac{1}{\sqrt{n}} + \frac{1}{n} + \sum_{k=3}^{n/4} \frac{1}{n^{3/2}} \leq \frac{1}{\sqrt{n}} + \frac{1}{n} + \frac{n}{4} \cdot \frac{1}{n^{3/2}} = O\left(\frac{1}{\sqrt{n}}\right).
$$
When $n/4 < k \leq n/2$, we have $n-k \geq n/2$ and so $e^{-p(n-k)} \leq e^{-pn/2} = 1/n$. Using the sharper upper bound $\binom{n}{k} \leq (\frac{en}{k})^k$, we get
$$
\epsilon_2 \leq \sum_{k=n/4+1}^{n/2} \left(\frac{en}{k}\right)^k \cdot \frac{1}{n^k} = \sum_{k=n/4+1}^{n/2} \left(\frac{e}{k}\right)^k.
$$
The summands $(e/k)^k$ are decreasing, and so
$$
\epsilon_2 \leq \frac{n}{4} \left(\frac{4e}{n}\right)^{n/4} \leq \left(\frac{4e}{n}\right)^{n/4-1} = O\left(\frac{1}{\sqrt{n}}\right),
$$
since when $n \geq 6$, the exponent is at least $1/2$.

Putting everything together, we get that the probability that the graph is not connected is at most
$$
\epsilon = O\left(\frac{1}{\sqrt{n}}\right).
$$

Using more refined arguments, one can show that when $p = \frac{\ln n + c}{n}$ for constant $c$, the probability that $G(n,p)$ is connected tends to $e^{-e^{-c}}$. Moreover, in a certain precise sense, the only obstacle to connectivity (whp) is isolated vertices.


Is this problem NP-hard? Good day.
Subset sum selection problem is NP-hard.

I trying to solve following problem:
Input: a grid NxN and subset size K and radius R. Every entry in grid contains a value.
Solution: subset of size K, so that sum of all selected items and items within radius(when selected items is in center) is maximal.

Here example(with radius 1 and K=2):

On this picture 2 orange items selected. all blue and green items are added to sum also, but green item, added only once( in other words any item on grid can be taken once in final sum).

So sum of selected subse: 2xOrange(selected)+9xBlue(adjacent)+1xGreen(taken only once into account).

When radius is 0 the problem is trivial: Just choose K best items,
But when radius 1 or more is following problem NP-hard?

If yes, what is the best way to prove it ?

If no, is there an algorithm that return optimal solution?

Many thanks for help!

It seems very likely that it is $NP$-complete.

A good "trick" to tackle a problem like this would be to create an instance where there are $X$ very big numbers in the grid and you're allowed to choose $X$ items. Choose the goal amount so that you need all of these big numbers, and this constrains you to "use" all of the $X$ items to cover the $X$ big numbers. The only freedom is in where exactly you pick the position of the rectangles relative to the big numbers.

A good candidate for a reduction would be Vertex Cover, which is $NP$-complete even for planar, 3-regular graphs. You could fix some embedding of the graph in the plane, and then place large numbers on the edges, so that you need to collect these numbers to win. You'd make $K$ so large that you can cover almost all of the big numbers in each edge, but not quite. Placing a rectangle at the position of a vertex would cover numbers in all of the incident edges.

I'll leave it to you to figure out the details (since you only asked for a "way" to prove it) but I'm pretty sure this is a feasible approach.


Runtime Calculation Sort-Algortihm I'm really struggling with the following exercise and I would really appreciate your help:
I have to calculate the expected runtime of a sort Algorithm with the following variants:

Variant   Runtime Behavior
1            n(n-1)
2              n
3            n log(n)

Given is, that the runtime for variant 1 is 1000 elements(n) is 20ms.
With the calculation for the other elements from variant 1, I have no problem because it's O(n^2) but I really don't know how to calculate the values for variant 2 & 3.

Variant    Length n    expected runtime in ms
   1        500          20ms * 0.5^2 = 5ms
   1        4'000        20ms * 4^2   = 320ms
   2        2'000'000    ?
   3        4'096        ?

Thanks for your help in advance

Kind Regards

Do not even mention big-O here because that is for asymptotic behaviour and f(1000) doesn’t give you the slightest clue what f(2000000) would be.

You are given that the runtime is f(n) = c x g(n) for three different functions c. Given the value of c x g(1000) for the first function g, you calculate c. Then you substitute c and n for all the cases.


What is the Curry-Howard analogue for linear logics? As defined by Wikipedia,

  (The Curry-Howard correspondence) is a generalization of a syntactic analogy between systems of formal logic and computational calculi that was first discovered by the American mathematician Haskell Curry and logician William Alvin Howard.

Related to it is the λ-cube, which is a graphical representation of the possible axes of refinement from simple types to the calculus of constructions, which has a logical interpretation:

As far as I know, the Curry-Howard correspondence is a connection between type theory and classical logics. My question is: is there any analogue correspondence between type systems and linear logics?

Linear logic corresponds to a type system for a process calculus (a variant of the internal π-calculus), where:

proofs correspond to processes;
propositions correspond to session types (communication protocols).

This is a pretty active area of research. While people expected a correspondence between linear logic and some concurrency model since the inception of linear logic by Girard [1987], finding something that is satisfying from both the logical and the concurrency modelling perspectives has been somewhat elusive.

Here is a summary of the key developments so far.

Abramsky [1994] and Bellin and Scott [1994] proposed the first "Proofs as Processes" correspondence, where linear propositions are types for linear channels in a process calculus. For example, the proposition $A \otimes B$ is interpreted as the channel type "send $A$ and $B$"; it is used to type a process that uses a channel to output a message including something of type $A$ and $B$ (a pair, if you like), respectively, and then the channel must not be used anymore. The key idea is that the cut rule of linear logic can be used to type the parallel execution of two processes that communicate over a private channel. The duality check performed by the cut rule in linear logic corresponds to checking that the two processes use the shared private channel in compatible ways.
The idea of duality inspired also several typing disciplines for process calculi, most notably linear types and session types, but the direct link to linear logic was lost. Session types in particular, by Honda [1993], describe communication protocols and their applicability became evident pretty soon: the idea spawned a research area.
Seven years later after Honda developed session types, Caires and Pfenning [2010] found that propositions in intuitionistic linear logic can be interpreted as session types. For example, the proposition $A \otimes B$ is interpreted as the protocol "send $A$ and then proceed as $B$". This discovery has rejuvenated the "Proofs as Processes" research line: there are a lot of papers on this topic published in the last decade. Thanks to the logical foundations, we can import ideas from logic for extending the typing discipline of session types.
Wadler [2014] reformulated the correspondence with session types for classical linear logic and formalised the first connection between a standard presentation of session types for a functional language and linear logic.
There is an "issue" shared by all the works cited above: while the linear logic side is the expected one, the process calculus side is not, both syntactically and semantically. For example, a notable discrepancy is that parallel composition ($P|Q$) is not a standalone term constructor, because it lacks a corresponding rule for reasoning about it directly in linear logic. This issue has been resolved in [Kokke et al., 2019] (disclaimer: I'm one of the authors), by conservatively reformulating the rules for $\otimes$, cut, and mix. This gives rise to new proof transformations, which turn out to correspond to the expected observational semantics of the π-calculus.

If you're looking for a couple of papers to get started, I would start from [Wadler, 2014] and then [Kokke et al., 2019] (to see the latest system).


Unifiers modulo commutativity in terms of syntactic unifiers and $\approx_{C}$-class I am studying Term Rewriting by reading Baader's book "Term Rewriting and All That". I am in the chapter of Equational Unification, in the section of Commutative Functions. I am trying to do the following exercise:

Let $s, t \in T(\Sigma, V)$. By exercise 10.10 we know that the $\approx_{C}$-classes of these terms are finite. Let $\{s_1, \ldots, s_m \}$ be the $\approx_{C}$-class of $s$, and let $\{t_1, \ldots, t_n \}$ the $\approx_{C}$-class of $t$. Show that:
$$ \mathcal{U}_{C}(\{ s \approx_{C}^{?} t \}) = \bigcup\limits_{1 \leq i \leq m \\ 1 \leq j \leq n} \mathcal{U}_{\emptyset}(\{s_i =^{?} t_j \})  $$
and that $\{ \sigma \ | \ \sigma \ \text{ is an mgu of } s_i =^{?} t_j \text{ for some } i, j, 1 \leq i \leq m, 1 \leq j \leq n \}$ is a complete set of C-unifiers of $s \approx_{C}^{?} t$.

It seems obvious, but how can I prove that:
$$\mathcal{U}_{C}(\{ s \approx_{C}^{?} t \}) = \bigcup\limits_{1 \leq i \leq m \\ 1 \leq j \leq n} \mathcal{U}_{\emptyset}(\{s_i =^{?} t_j \}) ? \tag{1}$$
After I prove that, I know how to proceed: let $\delta$ be an arbitrary C-unifier of $s \approx_{C}^{?} t$. By the equation (1) above, this means that $\exists_{i, j}: \ s_i \delta = t_i \delta$. Take $\sigma$ the mgu of $s_i =^{?} t_j$ and we have that $\sigma$ is more general than $\delta$.
Therefore, $\{ \sigma \ | \ \sigma \ \text{ is an mgu of } s_i =^{?} t_j \text{ for some } i, j, 1 \leq i \leq m, 1 \leq j \leq n \}$ is a complete set of C-unifiers of $s \approx_{C}^{?} t$.
How can I prove (1)? Any hint/suggestion is very much appreciated. Thanks in advance.

Note that for all $s, t \in T(\Sigma, V)$ we have:
$$s \approx_{C} t \iff \exists_{i, j}:  s_i = t_j \tag{*}$$
Using (*) for the terms $s \sigma$ and $t \sigma$ we obtain:
$$s \sigma \approx_{C} t \sigma \iff \exists_{i, j}: s_i \sigma = t_j \sigma, $$i.e,
$$\mathcal{U}_{C}(\{ s \approx_{C}^{?} t \}) = \bigcup\limits_{1 \leq i \leq m \\ 1 \leq j \leq n} \mathcal{U}_{\emptyset}(\{s_i =^{?} t_j \})$$


Is there any development in continuous-value computers? Is there anything that hints at the possibility of a (modern) continuous-value computer, since modern computers are based on discrete arithmetic?

I guess the old analog computers were of this continuous-value type, but is there any modern development?

Do you know something about the issues regarding computability on such machine?

Since you asked about computability and computational complexity for computers working on continuous values, you might be interested in research on computational complexity for the reals.  In particular, there is a great deal of research on computational complexity for computations that work with real numbers ($\mathbb{R}$).

Normally, we think of algorithms as operating on discrete values (which can be expressed using bits).  However, one can also study algorithms that work with real numbers, where the algorithm can use standard operations on real numbers: addition, multiplication, comparison, etc.  Imagine that each basic operation on real numbers takes $O(1)$ time.  Now we can talk about the running time of algorithms that use these basic operations, and talk about the class of polynomial-time algorithms.  We can also look at a computational task, and ask about its complexity: about the running time of the best algorithm for that task.  For example, a task might be something like: given a polynomial $p(x)$ with real-valued coefficients, determine whether it has a real root or not.

One can then define an analog of P, namely, $P_\mathbb{R}$ -- the class of problems that have a polynomial-time algorithm, where the algorithm is allowed to do basic operations on real numbers.  One can also define an analog of NP, namely, $NP_\mathbb{R}$.  This lets one ask interesting questions, like whether $P_\mathbb{R} = NP_\mathbb{R}$.  Anyway, there is a rich literature on this, pioneered by Blum, Cucker, Shub, Smale, and others.  It is known as complexity and real computation, and sometimes known as the BSS model.  If you search the research literature, you'll find lots of work in this area.

The BSS model does have significant limitations.  It assumes that all computations on real numbers can be done in $O(1)$ time, to infinite precision, with no error.  Real analog computers won't have that property.  But it's still a useful and interesting theory, nonetheless.

To learn more, you can look at https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine and https://cstheory.stackexchange.com/q/2119/5038 and https://cstheory.stackexchange.com/a/2062/5038 and https://cstheory.stackexchange.com/q/31626/5038 and https://cstheory.stackexchange.com/q/27508/5038.


Shortest distance from a set of points Consider an unweighted, undirected, simple graph $G=(V,E)$. We have some subset $S \subseteq V$, and we want to determine the shortest distance from any vertex $v\in V$ to some vertex $s\in S$.

To be clear, each $v\in V$ has a distance $d_1, d_2,\dots , d_{|S|}$ to each $s\in S$, and we want to find the smallest value of all $d_1, d_2,\dots , d_{|S|}$, and do this for every $v\in V$. So every $s\in S$, for example, would have a distance of $0$.

The algorithm should run in $O(|V|+|E|)$ time. Note that this is independent of $|S|$. I was thinking of running simultaneous BFS's on each $s\in S$ and only assign a vertex a distance if it doesnt already have a distance estimate (i.e. no other node in $s$ reached to $v$ earlier). I'm not really sure how to make the runtime work out though, since we would have to cut off the BFS at some point to prevent a factor of $|S|$ in the runtime.

Also, this is not a homework problem, it's a question from a midterm from a class a few years ago that I am using to study for my final coming up, and the solutions are not available. Thanks for the help!

Introduce a new node $s_0$ with edges to all $s \in S$ (but no others). Run BFS starting in $s_0$; the quantity you are looking for is

$\qquad\displaystyle \min_{s \in S} d(s, v) = d(s_0,v) - 1$

for every $v \in V$.

Nota bene: The idea extends to weighted graphs; you have to a) give the new edges weight $1$ and b) use an SSSPP algorithm, of course.


Is the halting problem specific to Turing machines? The proofs that the halting problem is undecidable seem to make very few assumptions about the kind of program/machine under consideration: just that the programs take one input and either loop or produce an output. Not just Turing machines have these characteristics: for example, a linear-bounded automaton can also loop.

So, as well as a proof that you can't use a Turing machine to decide whether a Turing machine will halt, is it not also a proof that you can't use a pushdown automaton to decide whether a pushdown automaton will halt, and so on, for any automaton/language that has the ability to loop?

The halting problem applies to any model of computation: you can always ask, "Given this machine and this input for it, does the machine halt?" Indeed, for any two models of computation $A$ and $B$, you can always ask the more general question, "Is there an $A$-machine that, given a description of a $B$-machine and its input, determines whether that machine halts?" Often, we take $A=B$.

What does vary between machine models is decidability of the halting problem.  If we say "decidable" on its own, it means Turing-decidable, i.e., model $A$ above is Turing machines. For, e.g., $B$ is DFAs or PDAs, the halting problem is decidable: the machine always halts because it halts when it reaches the end of its input, the input is finite and the machine consumes one character of input at every step. For $B=$Turing machines, the well-known diagonalization argument proves undecidability, and this extends by reduction to any Turing-equivalent model of computation.  That is, any model of computation that can simulate and be simulated by Turing machines.

The diagonalization proof has few assumptions – see Wikipedia for more details. There needs to be a coding of machines so they can be used as inputs to the machines themselves and the machines need to be able to simulate an "if" statement, loop forever, return a value, duplicate a value and be closed under subprograms (i.e., the model wouldn't become more powerful if you let machines call each other as subroutines). Therefore, no model of computation that has these properties can decide its own halting problem.

Note that this includes any model that can simulate a Turing machine, even if that model is more powerful. For example, consider the class $H$ of Turing-like machines with an oracle for the Turing machine halting problem. That is, the machines operate just like Turing machines but have a special instruction that can look at the tape and give an immediate yes or no answer to the question, "Does the ordinary Turing machine described there halt on the input described?" Thus, the machines are more strictly powerful than ordinary Turing machines. These oracle machines cannot decide their own halting problem, by the same diagonalization proof as for ordinary Turing machines. In fact, there's a strict, infinite hierarchy of machines: consider machines $H'$ that have an oracle for the $H$-halting probem, and then machines $H''$ with an oracle for the $H$-halting problem and... See Turing degree and the arithmetical hierarchy for more on that.


Is this push-down automaton non-deterministic, as JFLAP states? There is a tool called JFLAP, which, among other things, can analyze push-down automata, and find non-determinism.
In this example it is detecting non-determinism in state q0:

The first symbol in the transition represents the symbol read as input; the second symbol represents the symbol extracted from the stack; and the third symbol is the symbol pushed to the stack. λ represents the empty symbol, so this is an empty transition without checking the stack or pushing anything to it.
I am surprised, as that state seems to fulfill the conditions for determinism for push-down automatons (if only because it only contains a single transition!). I would expect the next state to be q1 under any circumstance.
In comparison, JFLAP doesn't find any non-determinism here:

Mind you, the transition is the same, it only changes that this one adds something to the stack. Am I missing something or is JFLAP wrong in the first instance?

All deterministic push-down automatons are also nondeterministic push-down automatons, so it is correct to say that your automaton is nondeterministic.
That said you are correct in saying that your first push-down automaton is also deterministic, according to the definition on Wikipedia.


Complexity of 4-coloring a map with constraints The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color.
In fact, there exists a quadratic algorithm for 4-coloring planar graphs.
Suppose you are given a map (e.g. the world's map) and a list of $k$ constraints, e.g. Greece is colored blue, and Spain, Italy and Uruguay are red.

Can this problem be solved in poly time if $k$ is part of the input?
Can this be solved in poly time if $k$ is fixed (i.e. is the problem fixed parameter tractable with respect to $k$)?

It is $NP$-complete. Consider a graph $G$ which is modified by duplicating every vertex, and connecting every duplicate vertex to its original. Then if we constrain all the duplicate vertices to a fixed color, then the thus obtained graph is 4-colorable (with constraints) if and only if the original graph is 3-colorable.


How to name documents in windows? What is the best way to name documents and folders in windows? Im thinging about maybe there will be some conflict in some programs? Or when searching in terminal

This_Is_Best.doc

ThisIsBest.doc

This Is Best.doc

u can try: http://msdn.microsoft.com/en-us/library/aa365247(VS.85).aspx

i hope this'll help.


Relation between digraph and NP-Complete problem Can there be any relations regarding the number of nodes available in a digraph so that to qualify it as NP-Complete problem.
If we consider this problem for instance:
Input: A digraph $G=(V,E)$ and two nodes $u,v \in V$
Question: Is there a path in $G$ from $u$ to $v$?
Can we say this problem is NP-Complete problem since the digraph have only two nodes that they have a path from one another and this makes it be a Hamiltonian Path. Hints are appreciated!

When a problem is NP-complete, it doesn't necessarily mean that all instances are hard to solve. It just means that enough instances are hard to solve that, if you could solve this problem efficiently, you could do the same for all problems in NP. Enough, in this case, does mean infinitely many1 and that should lead you towards looking at large inputs if you want to find hard cases.2

For example, the fact that 3-SAT is NP-complete doesn't mean that you would have any difficulty telling me whether the formula $(X\vee Y\vee Z)$ is satisfiable. In your example, you've observed that, for a graph with a single edge, that edge is a Hamiltonian path. That doesn't mean that it's hard to tell whether a graph has a single edge, or that it's easy to compute Hamiltonian paths on all graphs.

1 Probably infinitely many, anyway. If P = NP, there wouldn't be any "hard" instances of NP-complete problems.

2 Note that, strictly speaking, there's no such thing as a single "hard case" since, if we restrict to that single input, the problem can be solved in constant time. Properly, I mean a whole infinite class of instances such that it's "hard" to write an algorithm that answers the problem on that whole class of inputs.


Prove the following language is regular? Assume $L_1$ is a regular language, and define:
$$L = \{wcv ∈ \{a, b, c\}^* \mid |w|_a + 2|v|_b ≡ 3 \bmod 5, w, v ∈ L_1\}.$$
Show that $L$ is regular.

I first tried to prove by showing that the pumping lemma holds true, then learned that it was not a double implication and can only be used to prove languages are not regular.
Then I tried to draw an NFA, but didn't make any progress.
What's a good way to prove that a language like this is regular?

The answer depends on whether $L_1$ is a language over $\{a,b\}$ or over $\{a,b,c\}$.

$L_1$ is a language over $\{a,b\}$

In this case, the easiest way to proceed is using closure operations. Show first (by constructing a DFA) that the following language is regular:
$$
L_2 = \{wcv \mid |w|_a+2|v|_b \equiv 3 \bmod 5 , w,v \in \{a,b\}^*\}.
$$
Your language is $L = L_1cL_1 \cap L_2$.

$L_1$ is a language over $\{a,b,c\}$

In this case we have to be more careful. Given a DFA (or an NFA) for $L_1$, we construct one for $L$ which in three stages:

Simulate $L_1$ and keep track of the number of $a$s modulo 5. Whenever at an accepting state of $L_1$, add a nondeterministic move to stage 2.
Read $c$.
Simulate $L_1$ (starting from its initial state again) and keep track of the number of $b$s modulo 5. A state is accepting if it is accepting for $L_1$ and the constraint $|w|_a+2|v|_b$ is satisfied, where $w$ is the word read at the first stage, and $v$ is the word read at the third stage.

I'll let you fill in the details.


What is the common terminology to refer to the nth ancestor of a tree root? Reading the Wikipedia article for common terminology for tree (data structure) there are several near references, but I don't read a formal declaration for how to refer to a specific generation of a tree's subtrees.
For example,

Definition
As a data type, a tree has a value and children, and the children are
themselves trees;  [...] Due to the use of references to
trees in the linked tree data structure, trees are often discussed
implicitly assuming that they are being represented by references to
the root node, as this is often how they are actually implemented.

And also,

Terminology.
"The height of a node is the length of the longest downward path to a
leaf from that node. The height of the root is the height of the
tree. [...] The root node has depth zero..."

The former implies subtree n could be refered to as the nth decendant of root or the nth tree. Can I be sure subtree only refers to decendants and not other branches at the same distance from root?
The latter refers to the height counting from the root (0). Again, height sounds uncommon to me. As in, "Please refer to the nodes at height 4 to see..." Since a tree is commonly displayed from the root branching downward, I'm predisposed to bias against the term height versus my preferred notion of depth.

Commonly used phrases include,

"vertex at height $h$",
"vertex at depth $d$",
"vertex at distance $d$ from the root".

"Subtree $n$" doesn't make any sense, except as the $n$th element in some enumeration of subtrees.

By the way, I'd avoid using $n$ for anything other than the number of vertices in the graph.  That bit of notation is so standard in graph theory that it's confusing for the reader to have $n$ mean anything else.


Using A* search with different heuristic values I am currently trying to use A* to create cyclical routes (for plotting driving routes of set distances). I want to find a driving route from my start location that is as close to my specified length as possible. If it is bigger or smaller that is fine, just as close as possible

I have therefore adapted the heuristic function to:

|target distance-distance Travelled so far| + distance left to travel.

for example, I want to travel 20 miles, so my target distance is 20. At some point in the route i may have travelled 18. Therefore my h would be 20-18+2 = 2. I always pick the smallest h value, the idea being a route of 20 miles will be created finished where i starts.

I had 2 immediate issues with this.

The Start node can't be added to the closed list immediately or it will never create a cyclical route - I believe I have solved this one.
If the search goes into a cul-de-sac it gets stuck and the openlist becomes empty and the search terminates.

The second problem I cannot think of how to solve. It occurs because the successor node that would get the search out of the cul-de-sac is already in the closed list.

Can anyone help me come up with a general solution to my problem? Furthermore do you for see any other issues with my implementation?

would really appreciate any help you can give.

This problem is known as the Target Value Search Problem (TVS) and it can be succintly described as follows:

Given a graph $G(V,E)$, two nodes $s$ and $t$ ($s, t\in V)$ and a target value $T$ find a path $P$ from $s$ to $t$ such that the cost of the path is as close as possible to $T$

Of course, $s$ and $t$ might be the same node (as in your case). Note that the problem is not asking for paths (or, alternatively routes) whose cost equals exactly $T$ but that no path with a cost closer to $T$ exists. This is known as solving the Target Value Search Problem optimally. As usual, the cost of a path is defined as the sum of the costs of all edges traversed in the path.

There are different variations of this problem. All of them are described in the paper:

Carlos Linares López, Roni Stern, Ariel Felner: Target-Value Search Revisited. IJCAI 2013

The specific case that interests you most has been also investigated. You can find a short summary of results in the paper:

Carlos Linares López, Roni Stern, Ariel Felner: Solving the Target-Value Search Problem. SOCS 2014

The best solution currently known (to the best of my knowledge) consists of applying a bidirectional search. From your considerations and the notes provided by other people contributing to this thread:

You are right! The problem is that you'd like to come back to the same node but the route to traverse when going back is in the closed list. This problem is specifically addressed in the backwards search suggested in the algorithm $T^*$
David Richerby is right also! A* should traverse a state space which is exponential.

In fact, regarding the second comment. A very simple baseline for solving this problem consists of either using A$^*$ or IDA$^*$ in the path space. IDA$^*$ naturally generates paths (and thus it traverses a state space which can be exponentially large); A$^*$ can do that also if you just ignore nodes in the closed list!

In both cases, a node is never re-expanded if and only if it is an ancestor of the current node. However, it seems to me that you might find this acceptable. In that case, you are forced to expand all nodes!

Hope this helps,


Summation and big theta Can anyone suggest a starter book or website where I can find information and examples of putting functions under summation signs into Big Theta. basic Arihmetic , geometric, Quadratic are fine , but I would like to work on examples like
$$\sum_{i = 1}^{\log n} i \cdot n \text{ or } \sum_{i = 1}^{\log n} 10^i$$

Take a look at Appendix A in the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.
Besides you say that you'd like to know how to handle summations besides arithmetic and geometric series (and others) but the two examples you provide are (essentially) an arithmetic and a geometric series.


Worst-case input for median-of-medians with groups of size 3 Typically, median of medians algorithm is written with groups of size $5$ or $7$ to ensure worst-case linear performance. The argument against groups of size $k=3$ is typically that we get a recurrence of:

$$\begin{align*}
  T(n) & \leq T(n/3) + T(2n/3) + O(n)\\
       & = O(n \log n)
\end{align*}$$

However, this assumes that there exists an input which would always split the recurrence in the worst possible case. I am not convinced that this input always exists.

Question: Is there a general procedure to create a worst-case input for the median-of-medians algorithm with $k=3$ for an input of any length $n$?

If it helps, you can assume $n$ is of some particular format and that we are always searching for the exact median (as opposed to querying the $i$-th order statistic). You can also assume that the algorithm groups elements deterministically (e.g. incrementally group 3 elements).

You can choose any deterministic implementation if it helps, here is one for reference. Given an input array $A$ of $n$ distinct elements and query $i$ for the $i$-th order statistic, the $\mathrm{SELECT}(A, i)$ procedure is as follows:

Divide $A$ into $\lfloor \tfrac{n}{3} \rfloor$ groups of length $3$.

We can do this by putting $\{a_1, a_2, a_3\}$ as group $G_1$, then $\{a_4, a_5, a_6\}$ as group $G_2$, and so on...
If $n \neq 3k$ then we can create one more group with the remaining 1 or 2 elements.

Find the median of each group $G_i$ and store them in a list $M$.

We can do this by creating $M = [\mathrm{med}(G_1), \mathrm{med}(G_2), \ldots ]$.

Recursively call this function to get the median of medians $x = \mathrm{SELECT}(M, \lfloor \tfrac{n}{6}\rfloor)$.
Partition $A$ about $x$ into $A_1$ and $A_2$.

Let all elements in $A_1$ be less than $x$. (Assume order is retained)
Let all elements in $A_2$ be greater than $x$. (Assume order is retained)

If $i = |A_1| + 1$ return $x$
If $i < |A_1| + 1$ return $\mathrm{SELECT}(A_1, i)$.
If $i > |A_1| + 1$ return $\mathrm{SELECT}(A_2, i - |A_1| - 1)$.

The biggest issue I am having for constructing a worst case input, is that we need $A$, $M$, and $A_1$ or $A_2$ to exhibit worst-case behavior. Since $M$ is nested in $A$ and $A_1$ or $A_2$ are subsets of $A$, getting all of this coordinated is very difficult.

Additional Notes:

We can always show that the initial recurrence will split into a problem of size $n/3$ and $2n/3$, perhaps we can also do this for the next level down, however I doubt it can be done consistently for levels below. This is relevant and important, because if you can show that our second recurrence will in fact be on something less than $2n/3$, then we have a linear time algorithm! This is because we'd get a recurrence:

$$T(n) \leq T(n/3) + T(\alpha n) + O(n)$$

Where $\alpha < 2/3$ thus, by the uneven split theorem this must be linear a la $T(n) = O(n)$.

Whether or not the median-of-medians algorithm with groups of size 3 runs in linear time is an open problem as said in [1] (while they proposed a variant running in linear time). I checked some follow-up papers and no one has a progress on showing the complexity of this algorithm. I believe it still remains open now.

[1] Chen, K., & Dumitrescu, A. (2015, August). Select with groups of 3 or 4. In Workshop on Algorithms and Data Structures (pp. 189-199). Springer, Cham.


If L is a regular language then the language replace(L,σ,τ) is also regular I am stuck at the following problem:

Prove that if $L$ is a regular language over some alphabet $\Sigma$ and that $\sigma, \tau \in \Sigma$, Then the language $replace(L,\sigma,\tau)$ is regular.

Where $replace(L,\sigma,\tau)$ is defined as:

$replace(L,\sigma,\tau) = \{x\tau y\in \Sigma^*| x\sigma y\in L\}$.

My try:

Since $L$ is a regular language there exists a deterministic finite automaton $A=(\Sigma, Q, q_0, F, \delta_A)$ such that $L(A)=L$.

Now for each state $s\in Q$ we will define a non deterministic finite automaton $B_s=(\Sigma\cup\{\gamma\}, Q\times \{1,2\}, q_s, F\times \{2\}, \delta_{B_s})$
where $\gamma\notin \Sigma$ such that:

$\forall p\in Q,\mu\in\Sigma, \delta_{B_s}((p,1),\mu)=\{(\delta_A(p, \mu),1)\} $

$\forall p\in Q-\{s\}, \delta_{B_s}((p,1),\gamma)=\emptyset$

$\delta_{B_s}((s,1),\gamma)=\{(\delta_A(s,\sigma),2)\}$

$\forall p\in Q,\mu\in\Sigma, \delta_{B_s}((p,2),\mu)=\{(\delta_A(p, \mu),2)\} $

$\forall p\in Q, \delta_{B_s}((p,2),\gamma)=\emptyset$

Now we'all define a new non deterministic finite automaton with $\epsilon$ moves $B$ by linking he starting state of this automaton to all of the starting states of the automatons $B_{s}$ for every state $s$, And we will also link the final states of all of the $B_{s}$ automatons to the final state of the automaton $B$.

The automaton $B$ will satisfy the property $L(B)=\{x\gamma y|x\sigma y\in L\}$ ( This is probably incorrect!!!)

Now we will define an homomorphism $h:\Sigma\cup\{\gamma\}\longrightarrow\Sigma$ such that:

$\forall \mu\in\Sigma,h(\mu)=\mu$

$h(\gamma)=\tau$

Since regular languages are closed under homomorphisms we can conclude that $h(L(B))$ is regular, But $h(L(B))=h(\{x\gamma y|x\sigma y\in L\})=\{x\tau y|x\sigma y\in L\}$ and so $replace(L,\sigma,\tau)$ is regular over $\Sigma$.

Thanks for any hint or help.

Let $A$ be the alphabet and let $a$, $b$, $c$, ... be the letters
(this is easier to type).

Hint.
Consider the (non-deterministic) transducer $A^* \to A^*$ defined by $1 \xrightarrow{c \mid c}1\xrightarrow{a \mid b} 2 \xrightarrow{c \mid c} 2$
(more precisely, there are transitions $1 \xrightarrow{c \mid c} 1$ and $2 \xrightarrow{c \mid c} 2$ for any letter $c$ of $A$, including $a$ and $b$, but there is a single transition form $1$ to $2$). For each transition, the left hand part of the label is the input letter, the vertical bar is a separator and the right hand part is the output letter.


Aggregate Rate and Poisson Process in Aloha I'm having a hard time understanding what is mean't by the aggregrate rate $\lambda$ and what it means for throughput in unslotted and slotted Aloha protocols. The more I seem to read about poission process the more confused I get.

I understand that the probability a packet is transmitted in a time interval $\delta t$ is $\lambda \times \delta t$ where you have $N$ senders and $Y$ is the aggregate rate from all $N$ senders.

However I don't understand what is mean't by aggregate rate. It's quite a perculiar phrase. Does it mean the probability that any of the $N$ senders will try to transmit, or is the number of packets to be sent by $N$ senders over the time?

Next we're then told that the individual rate for a sender is $\lambda / N$. Because I'm so confused by what is mean't by rate it's hard to begin to think about what this even means.

The dictionary definition of aggregate might be helpful: https://www.wordnik.com/words/aggregate

You have $N$ senders.  Each sender sends packets on a network at some rate, say, $\lambda/N$.  Now think about all the packets that are sent over that network, without regard to who sent it.  What's the rate at which such packets appear on the network?  That's a total over all packets.  The aggregate rate will be something like $\lambda$.

It might also be helpful to refresh your understanding of what a rate is.  A rate is an amount divided by a time period: e.g., the number of packets sent by Alice per unit time interval.  The aggregate rate is also a count divided by a time period, but in this case, the count is of a different quantity: it's a count of all packets, not a count of the packets sent by Alice.  So, the number of packets sent (in total, from anyone) per unit time interval is a rate.  That is what your book is calling the aggregate rate.


Myhill-Nerode - Prove irregularity for $\{a^{n^3}\}$ I need to prove that the following language is not regular by showing there are infinite pairwise  distinct equivalence classes:
$$
  L = \{a^{n^3} \mid n \geq 1\} \subseteq \{a\}^*
$$
Looking at a few examples, I intuitively noticed that for each $i \geq 1$ there is an equivalence class $[a^{i^3}] \neq [a^{j^3}]$ for $i \neq j$ because the number of  $a$'s we need to add increases exponentially with $i/j$. Thus for every $i$ we can add a suffix of $a$'s to reach the next higher power $(i+1)^3$ but the length of that suffix is different for every other power, so that each equivalence class only actually contains the representative itself.
Example:
$$
\begin{align*}
  &n = 1 \implies a \\
  &n = 2 \implies a^8 \\
  &n = 3 \implies a^{27} \\
  \vdots
\end{align*}
$$
Then
$$
\begin{align*}
& [a] = \{x \in \{a\}^* \mid a \; R_L \; x\} = a \\
& [a^8] = \{x \in \{a\}^* \mid a^8 \; R_L \; x\} = a^8 \\
\vdots
\end{align*}
$$
Consider $[a]$. For $z = a^7$ we get $az = aa^7 = a^8 \in L$, but starting from $i \geq 2$, we have that $a^{i^3}z \notin L$.
How can I write this down in a more formal/rigorous way?

More generally, you can use Myhill–Nerode to prove the following characterization:

For $A \subseteq \mathbb{N}$, let $L(A) = \{ a^n : n \in A \}$.
The language $L(A)$ is regular iff $A$ is eventually periodic.

In particular, if $A$ is an infinite set with density zero then $L(A)$ is not regular. Here density zero means:
$$
\lim_{n\to\infty} \frac{|A \cap \{0,\ldots,n-1\}|}{n} = 0.
$$
This shows that $\{a^{n^k} : n \in \mathbb{N}\}$ is not regular for any $k \geq 2$.

Let us prove the claimed characterization. If $A$ is periodic, say with period $m$, then $L(A)$ is clearly regular: it is accepted by a circular DFA with $m$ states. If $A$ is eventually periodic then there is a periodic $B$ such that $L(A),L(B)$ differ in finitely many words, and so standard closure operations show that $L(A)$ is regular.
Now suppose that $L(A)$ is regular. The equivalent class of $a^m$ is the set $E_m = \{ k \in \mathbb{N} : m+k \in A \}$. Since there are finitely many equivalence classes, there exist $m < p$ such that $E_m = E_p$, that is, for all $k \in \mathbb{N}$, $m + k \in A$ iff $p + k \in A$. In other words, for all $\ell \geq m$, $\ell \in A$ iff $\ell + (p-m) \in A$. Hence $A$ is eventually periodic (with period $p-m$).


Algorithm for modified knapsack problem We have $n$-players in a game. We have a population of players we can choose from. Each player score is a normally distributed random variable and each player has a cost to add to the team. We are limited to $n$-players and the total cost must be less than or equal to $m$.

The total score for a team is calculated as the sum of all of the individual player's score on that team. Our goal is to maximize the expected team score while staying under our allowed player weight and number of players.

Now, suppose that in this game we drop the score of the player that has the lowest score on the team and do not consider it in the total team score.

Does a deterministic algorithm exist that will allow us to reach the optimal solution?

Let $X_1,\dots,X_n$ denote the scores of the individual members of the team.  Then the score $Y$ of the team is given by

$$Y = X_1 + \dots + X_n - \min(X_1,\dots,X_n).$$

So, by linearity of expectation, the expected value of the score of the team will be

$$\mathbb{E}[Y] = \mathbb{E}[X_1] + \dots + \mathbb{E}[X_n] - \mathbb{E}[\min(X_1,\dots,X_n)].$$

This suggests a natural approach.  Given a candidate list of members of the team, calculate the expected team score $\mathbb{E}[Y]$ using this formula.  Try all possibilities for the list of team members, compute the expected team score for each, and pick the one that has the highest expected team score.

The biggest challenge is to evaluate the above formula for a particular list of team members.  It is easy to evaluate $\mathbb{E}[X_i]$, but evaluating $\mathbb{E}[\min(X_1,\dots,X_n)]$ where $X_1,\dots,X_n$ are independent Gaussian random variables is challenging.  This is an order statistic, and there are various techniques for approximating its expected value.  One is to numerically estimate a certain integral.  Another is to use the approximation $-\Phi^{-1}({n-0.375 \over n+0.25})$, where $\Phi$ is the cdf of the normal distribution.  See J.P. Royston, Expected Normal Order Statistics (Exact and Approximate), Journal of The Royal Statistical Society Series C (Applied Statistics), vol 31 no 2, pp.161-165.  There may be better algorithms; hopefully this gives you the technical terms to use for searching.


Closure of Star-Free Languages under Substitution Let $L$ be a star-free language over finite alphabet $\Sigma$.  A substitution will be a map $\sigma : \Sigma \to \mathcal{P}(\Sigma^*)$.  It seems obvious that if $\sigma(a)$ is star-free for every $a \in \Sigma$, then $\sigma(L)$ will be star-free.
($\sigma(L) = \{ w_1 ... w_n | w_i \in \sigma(a_i) \land a_1 \ldots a_n \in L \}$)
Take a star-free regular expression for $L$, and substitute star-free expressions for $L_i$
for each $a_i$ in that expression.  The result will still be a star-free expression.

Now, my question is this: why is the following not a counterexample?
$\Sigma = \{ 0, 1 \}$. $L = 1^*$ and $\sigma(1) = 0^* 1 0^* 1 0^*$.
Both of these languages are star-free:
$L = L( (\emptyset^c 0 \emptyset^c )^c )$ and similar tricks can be given to show that $\sigma(1)$ is star-free.

Now, the reason it seems like a counterexample: a word in $L$ contains only 1s. The substitution replaces each 1 with a word from a language whose words contain exactly 2 1s.
So won't $\sigma(L)$ be the set of words with an even number of 1s, which is known to be non-star-free?

(Note: my proof suggestion of closure under substitution is a bit sketchy.  The star-free expression for $1^*$ only has 0s in it.  But I could then substitute
the star-free expression for $\sigma(1)$ under a complement, no?)

I do not understand your proof sketch. Where do you want to subtitute $\sigma(1)$ under a complement. The only thing substituable in the star-free expression for $1^*$ is $0$. But 0, or $\sigma(0)$ is an independent element in the substitution, it is in no way related to the complement of $\sigma(1)$. So this can in no way make a proof.

Actually, if there was such a closure property, it should be easy to find in
the literature on star-free RE. But all closure results under substitution put
constraints on the type of substitution, such as being length
preserving, or being injective.
See in particular papers by Jean-Eric Pin and others.

Also,Pin defines star-free substitutions on $\Sigma$ as requiring an additional property, namely that $(\sigma(\Sigma))^*$ is star-free. (though I did not check
the precise role of this property)

It seems that you have just proved that star-free languages are not closed under star-free substitution as you define it.

This does not seem too surprising, since non injective substitution does not in general commute with complement or distribute with intersection.

Among other papers:
Jean-Eric Pin, H. Straubling, and D. Thérien. Some results on the generalized star-height problem. May 12 2002.


Why the extra state in this automaton? Why does the following DFA have (to have) the state $b_4$?

Shouldn't states $b_1,b_2,b_3$ already cover "exactly two 1s"?
Wouldn't state $b_4$ mean "more than two 1s", even if it doesn't trigger an accept state?

$b_4$ is what is called a trap state, that is, a state that exists just so that all possible transitions are explicitly represented, even those that do not lead to a final state.

It doesn't change the language that is being defined, and can be omitted for the sake of brevity.


How to find highest normal form of a relation, given its functional dependencies Let's say that I have a relational model, defined as:

$$X(A,B,C,D,E,F,G)$$ with the functional dependencies:
$$f_1: \{A,B,C\} \to \{D,E,F,G\}$$
$$f_2: \{A,B\} \to \{C\}$$

Using this information I need to determine the highest normal form (for us it's BCNF) that this relation will go to. It's clear that the relation is already in it's atomic form, therefore it's already in it's first normal form. The to proceed to the second normal form, I found that the candidate key is $\{A,B\}$ and since all non prime attributes are fully dependent on the candidate keys, it's in the second normal form. But from this point I'm not sure where to go because all the non prime attributes (excluding $C$), $D,E,F,G$ are dependent on $C$ which is also a non prime attribute.

How can I separate this relation and proceed to the third normal form?

PS - I'm not sure if this is the right place to ask a database question but since the stack exchange for database is for professionals, I thought I should post it here. If someone knows a better stack exchange for this sort of a question, I'll transfer it over to that one.

In your example $C$ is derived attribute from $A, B$, but none of: $D, E, F, G$ is more dependent on $C$ than $A, B$, or solely functionaly dependent on $C$, so there is no transitive dependency. Since you have 2NF it is in 3NF.

For BCNF it is sufficient to be in 3NF and do not have overlapping candidate keys, which you do not have, hence it is in BCNF.


How can I prove this language is not CFL? I have a question to find out that $L = \{a^m b^n\mid n>0, m - is prime \}$ is CFL or not. I know that it is not a CFL. But I don't know how to prove that. I know how to prove that $L = \{a^m\mid m - is prime \}$ is not CFL, by taking a random length for $vx$ ($uvwxy$) and prove that the length of the whole word is not prime (I manage to prove that this length is product of two factors). But with this problem I can't do this because of that $n$. At the end it results a non prime number (this product), but I have to decrease the length of $b$'s so I know nothing about that final number. Is there another method to prove that this language is not CFL or am I wrong somewhere?

The easiest way goes as follows: if $L$ were context-free than so $L \cap a^*$ would be. Now $L' = L \cap a^* = \{ a^m : m \text{ is prime}\}$ is a unary language, so $L'$ is context-free iff it is regular iff it is eventually periodic. If it were eventually periodic then it would be either finite or have finite asymptotic density, but we know that primes are infinite and have zero asymptotic density.

You can also prove that $L'$ is not context-free using the pumping lemma. The pumping lemma shows that for some $p$, every prime $q > p$ satisfies the following: there is $1 \leq t \leq p$ such that $q + (\ell-1)t$ is prime for all $\ell$. Choosing $\ell = q+1$, we get that $q(t+1)$ has to be prime, which it isn't.


Planar Embedding with Some Nodes Constrained I've read about basic planar-graph embedding and about embedding a planar graph onto a set of fixed points, but I was wondering how one might constrain the locations of some nodes—perhaps to a set of points—while allowing others complete freedom.

Is this achievable with a current popular algorithm, or with minor modification thereto? I guess the nature of the problem would lend itself better to grid-based embeddings, right?

I'm entirely new to graph theory, so it's possible the answer is obvious to those familiar with the field. I didn't see anything about it while searching.

This was meant to be a comment but it was a bit too long, sorry!

There is a well known algorithm to draw a planar graph, namely Tutte's drawing algorithm. The input graph is assumed to be 3-connected and planar. The idea of the algorithm is to fix the position of vertices of a face in convex position and from those coordinates deduce the positions for the rest of the vertices. The resulting drawing being a planar drawing of the input graph. Perhaps you can find more about this at [1].

With respect to grids, there are a couple of well known algorithms for drawing planar 3-connected graphs. One is Schnyder's algorithm (through the a Schnyder wood decomposition of the edges), and the canonical ordering algorithm (through a partition of the vertices of the graph). Both of these algorithms run in $O(n)$ time and produce drawings in an $O(n)\times O(n)$grid, where $n$ is the number of vertices of the input graph. At [2] you may find an overview of these two algorithms for the case of planar triangulations. You could even go to references [4] and [9] cited there for the original papers. It is worth noting that these algorithms have been generalized to work on 3-connected planar graphs as stated above.

Are you thinking about drawings subject to more specific constraints?


What is combinatorial explosion? In the theory of NP-completeness, researchers refer to the concept of combinatorial  explosion. Some researchers use it as justification for intractability or NP-completeness. Others use it to refer to the exponential growth of possible solutions of an intractable problem while others use to refer to the apparent exponential time required to solve NP-complete problems. I am interested in formal connection to combinatorics.

  Is there combinatorial basis that captures and explains the phenomena of combinatorial explosion?

There is no formal connection to anything because "combinatorial explosion" is an informal term. It refers to rapid growth of a function caused by the combinatorics of the situation.


Any book for learning to correctly find out complexity of one's algorithm? Suppose we have designed an Algorithm and we want to find out its complexity. I am looking for a book which mainly focuses on finding out complexity of algorithms rather than introducing me to different search, sort, and ... algorithms.

Simply pick up any algorithms book out there, they will all take you through these things.  What you are describing is essentially the algorithms (and computational complexity) field.

The most popular books are Algorithms by Sedgewick and Wayne, which is free for download, the CLRS Introduction to Algorithms, and the epic Art of Computer Programming by Knuth.


Minimizing DFA built on set of words A set of English words is given.
Is there linear or sublinear algorithm to build minimal DFA for the given dictionary?
I tried different approaches, and they all were concerned with building Trie and then minimizing such automata.
So it is very interesting for me is there some algo using it to solve my problem.

P. S. The problem must be quite common because of DFA connection with regexps, and at the same time its statement seems like special case, so I think I am missing some simple idea.

There is clearly no sublinear-time algorithm; any algorithm needs to look at all words in the input to have a hope of being correct.

There is a straightforward algorithm to construct a trie that recognizes these words in linear time.  The trie is a DFA, but not a minimal DFA.

The trie is acyclic, and apparently there are algorithms for minimizing an acyclic DFA in linear time, so this yields a linear-time algorithm to construct such a minimal DFA.  See for example

Johannes Bubenzer.  Minimization of Acyclic DFAs.  Proceedings of PSC 2011.


what is the relationship between increasing the number of cores and scalability? Whenever I increase the number of cores the speedup will increase. with this increasing can I consider the system as scalable?

I mean based on the speedup obtained for a different number of cores e.g. 10,20,30, is the system scalable with the increase of cores?

If the problem size (input data set and/or computation) is fixed , then NO. Amdahl's law says that. Speed up will be bounded by serial portion of the program.

If the problem size (input data set and/or computation) increases with the increase in the number of cores, then YES, Gustafson's law says that.


Distinct variables for different clauses In resolution theorem proving, it is normally assumed variables in different clauses are distinct. This is not something that happens automatically; it requires significant extra code and computation to implement. Given that, I'm looking for a test case for it.

The problem is, in all the test cases I've tried so far, it makes no difference. Presumably it matters only in unusual edge cases. As Wikipedia puts it, "variables in different clauses are distinct... Now, unifying Q(X) in the first clause with Q(Y) in the second clause means that X and Y become the same variable anyway."

Are there any known test cases that will actually give the wrong answer if different clauses use the same variables?

Edit: I found a better example. Consider these clauses:
\begin{align}
& \lnot P(x) \lor P(f(x)) \\
& P(x) \\
& \lnot P(f(f(x)))\\
\end{align}
Obviously, this set of clauses is contradictory. But without renaming variables, the only possible resolvent is $P(f(x))$ and no more resolvents are possible - all lead to substituting $f(x)$ for $x$, which is impossible.

Edit: Consider the meaning of clauses. Each clause is implicitly universally quantified. So the meaning of its variables isn't fixed to anything. Now let's say you have two clauses both containing $x$. If you perform resolution without renaming $x$ in one of them, then you add a meaning to $x$ which it doesn't have: you say that $x$ means the same thing in both clauses, which is not true.
If you don't have distinct variables in your clauses, resolution will give you too weak conclusions.

(The original answer.)
For example, let's have 4 clauses:

$A\lor B(x)$
$\lnot A\lor C(x)$
$\lnot B(c)$
$\lnot C(d)$

where $x, y$ are variables and $c, d$ constants. If we perform resolution on the first two without renaming $x$, we'll get $B(x)\lor C(x)$. We can proceed with $\lnot B(c)$ to get $C(c)$ but now we cannot resolve it with $\lnot C(d)$.

On the other hand, if we rename $x$ to $y$ in the second one to have disjoint set of variables, we'll get $B(x)\lor C(y)$ from the first resolution step and we can derive an empty clause using $\lnot B(c)$ and $\lnot B(d)$.


Mapping reduction to show NeverHalt is undecidable I need help with showing that
$$NeverHalt_{TM} = \{\langle M\rangle \mid \text{$M$ is a TM which runs forever on every input $w$}\}$$
is undecidable by giving an explicit mapping reduction.

To show that a language reduces to any other language we must show that yes-instances are mapped to yes-instances and no-instances are mapped to no instances. We need to find a TM whose language will "help" us solve $NeverHalt_{TM}$, given $\langle M\rangle$.

I am not really sure where to go from here or in general how to proceed with undecidability problems.

You will not prove that $NeverHalt_{TM}$ is undecidable by "finding a TM whose language will "help" us solve" it. This would actually prove the opposite, if $M$ is a TM deciding some language.

You have to suppose $NeverHalt_{TM}$ to be decidable by a turing machine $D$, and show that with its help you can decide other non-recursive language. In other words, you have to pick a suitable undecidable language and reduce it to $NeverHalt_{TM}$. There is a reduction from the emptiness problem for turing machines : $E_{TM} = \{\left < M \right >\ :\ \mathcal L(M) = \varnothing \}$.