Dealing with test condition '=' for a while loop when determining a bound function/loop variant The following is the definition of what a bound function for a while loop must satisfy:

The bound function is an integer-valued, total function of some of the inputs, variables and global data that are defined when the loop is reached.
When the loop body is executed, the value of this function is decreased by at least one before the loop’s test is checked again, if at all.
If the value of this function is $≤ 0$ and the loop’s test is checked then the test fails (ending this execution of the loop).

I am given a while loop as such,

while (j ≤ n) {.....; j = j + 1}

where j is not touched by the rest of the body of the loop.

I am trying to find a bound function for this simple while loop. Here is what I tried:

$n-j$ is not a bound function since point (3) fails.
$n-j-1$ is not a bound function since the loop would not run initially if $n=j$ (since $n-j-1=-1 \ge f(j,n)$), and I am not sure if the latter is a total function due to the presence of $-1$.

How do I deal with the '=' in the '≤' to determine a bound function that satisfies the while loop?

$n-j+1$ should work as it satisfied the three properties of a bound function.

It is definitely an integer valued function as all variables and 1 are integers.
Since $j$ is increased by 1 in every iteration, the function decreases by 1 each time. For example let's say $n$ was 5 and $j$ was 4. Then for the first iteration it would be 5-4+1=2, then the second iteration would be 5-5+1=1, and then when $j$ is 6, 5-6+1=0, which is also the upper bound for the number of executions of the loop body left.
Finally, if the value of the function is at most 0 then the test has to fail, and that is true for this function since if
$n-j+1\le0$ then $n+1\le j$, which means that $n < j$, since both $n$ and $j$ are integers. Since $j>n$, that means the test must fail and that satisfies the final condition.

Thus $n-j+1$ is a bound function for this algorithm. The answer below is wrong: if $n$ was 5 and $j$ was 4 then $n-j-1$ would be 5-4-1=0 and so the function is at most 0, meaning that the test $j\le n$ must fail, but $4\le 5$ does not fail.

Furthermore, stating that $n-j-1\le0$ then $j\ge n-1$ implies $j>n$ is incorrect, as if $j\ge n -1$ how would $j$ be greater than $n$ for sure when it was just stated that $j$ could be greater than or equal to $n-1$? I am pointing out that the answer is wrong because I too had this same exact question and believed the answer provided before realizing it was incorrect, and so hopefully others would realize that too.


Error correction code without error detection Error detection and correction codes require many bits of redundancy for correcting even a modest number of erroneous bits. However, we often have out-of-band methods to determine when and where the errors occured, such as if we observe a voltage spike that exceeds the usual signal levels.

Are there any well-established error correction codes that use less redundancy, but require that the receiver explicitly declares some bits as unknown and corrects only those? In theory, we should be able to correct one erroneous bit for every bit of redundancy.

Are there any such codes which are also able to detect and correct a small number of unknown errors, in addition to the known ones?

Are there any such codes where the receiver augments each bit with some kind of non-binary confidence score, and the code then finds the most likely original sequence?

You might be interested in the binary erasure channel, in which each symbol is erased with probability $p$. The capacity of this channel is $1-p$, and there are practical erasure codes that achieve it.
In the second scenario you describe, some symbols are erased, and some are received with error. This is known as the binary symmetric error channel, and there is some work on it.
Finally, if each symbol is associated with a confidence, then the corresponding notion of decoding is soft decoding.


Examples of difference between Hidden Markov Model and Bayesian Network? I am trying to more deeply understand the difference between Hidden Markov Models and Bayesian Network? The general idea is that HMMs have a single variable which has probabilities of entering different states, known and unknown, whereas the Bayesian network relates multiple random variables.

So, given that, what would examples of particular problems that would be appropriate for each?

A Hidden Markov Model can be expressed as an instance of a Bayesian network of a particular form.  Consequently, a HMM can be viewed as an special case or kind of Bayesian network.  Bayesian networks are more general, and can express other kinds of probabilistic structures as well.  All HMM's are Bayesian networks, but not all Bayesian networks are HMMs.


Reducing from a Turing machine that recognizes is regular to the halting problem I'm trying to understand reduction, this is from my textbook and is not a homework problem or even any exercise, just trying to understand an example they present.

This is the reduction they give:

PROOF We let R be a TM that decides REGULARTM and construct TM S to
decide ATM . Then S works in the following manner.

S = “On input $M$, $w$ , where M is a TM and w is a string:

Construct the following TM $M_{2}$ .

$M_{2}$ = “On input x:

If x has the form $0^{n} 1^{n}$ , accept .
If x does not have this form, run M on input w and
accept if M accepts w.”

Run R on input $M_{2}$ .
If R accepts, accept ; if R rejects, reject .”

So, we start with a machine that decides whether a language of a TM is regular. And we want to use that to decide if a TM halts on a given input.

My question: What if $w$ does have the form $0^{n} 1^{n}$? Well, $M_{2}$ accepts that string just cause of the form. But we never actually run $M$ on $w$. So how can we say that it will accept or reject it? We have no idea what it does because we never ran it on $w$.

Here's the key: work out what $L(M_2)$ is.

Notice that $M_2$ takes a string $x$ as input, so we are trying to identify which strings $x$ will cause $M_2$ to accept.

There are two cases:

Case 1: If $M$ accepts on input $w$.  Then  $L(M_2)=\Sigma^*$.

In other words, in this case, it doesn't matter what $x$ is.  $M_2$ will always accept on input $x$.  If $x$ has the form $0^n 1^n$, then $M_2$ accepts (in step 1).  If $x$ does not have the form $0^n 1^n$, then $M_2$ also accepts (in step 2).  $M_2$ accepts either way; it accepts on every possible input.
Case 2: If $M$ does not accept on input $w$.  Then $L(M_2) = \{0^n 1^n : n \in \mathbb{N}\}$.

Let's look at why this is.  If $x$ has the form $0^n 1^n$, then $M_2$ accepts in step 1.  If $x$ does not have the form $0^n 1^n$, then $M_2$ runs step 2 and doesn't accept (since $M$ doesn't accept on input $w$).

So, $L(M_2)$ is one of two possibilities: it is either $\Sigma^*$ (everything) or $\{0^n 1^n : n \in \mathbb{N}\}$.  Which of those two possibilities it is will depend upon $M$ and on $w$ (and in particular on whether $M$ accepts on $w$).  Remember that implicitly $M_2$ is dependent upon $M$ and $w$: it's got them hard-coded into its code.

Moreover, $\Sigma^*$ is regular, but $\{0^n 1^n : n \in \mathbb{N}\}$ is not regular.  So if we have a way to tell whether the language of a TM is regular or not, we have a way to tell whether $L(M_2)$ is $\Sigma^*$ or $\{0^n 1^n : n \in \mathbb{N}\}$ -- which in turn means we have a way to distinguish Case 1 from Case 2, or in other words, we have a way to tell whether $M$ accepts on input $w$ or not.

That means, if we have a way to tell whether the language of a TM is regular or not, we have a way to solve the halting problem.  (It's not the same TM; it's a related TM.  The way we tell whether $M$ accepts on $w$ is not by analyzing whether the language of $M$ is regular; we construct some new TM that is related to $M$ and $w$ in a crazy way, and then test whether the language of that new TM is regular or not.)

It's important to remember that $w$ is not an input to $M_2$.  Instead, $w$ is just a constant that is hard-coded into the source code of $M_2$.  It would be like hard-coding the value of pi as 3.1415927 in your code, except here the hardcoded constant is going to be whatever $w$ is.  Each different $w$ corresponds to a different $M_2$.

P.S. I'll also repeat a crucial point from Karolis Juodelė: "Strings are not regular, languages are."


How can words instruct machines? How words can instruct hardware to do an operations . I understand that these are converted to 0s and 1s . But still I can't intuitively understand How it works .  A detailed explanation would be appreciated .

When converted to 0s and 1s, they're not words anymore, they are a configuration for the machine. In a way, they are words only as a help to our human understanding. As it often happens, we end up confusing our own conceptions with reality.

Computer networks, distributed systems and interactive computing add other layers of complexity to this picture. Since you cannot consider standalone computer as closed systems of hardware and software, it becomes even more tempting to see programs as transcendent writings, whose meaning commands the machines were they run.

It is definitely not the case. Words are aids, nothing more.

To put it differently: a program, or any kind of source code, is already given to the compiler as a sequence of 0s and 1s. Even if not directly composed of machine instructions, this sequence of bits can be deterministically converted to machine code. That's what a program translator (compiler, interpreter, emulator, etc.) does.


Is it still transfer learning if you consider input as well as output? (neural networks) I'm new to the CS stack exchange, so a fond hello to you all!

I joined since I have a question I've been curious about. I have recently been running some experiments in transfer learning - specifically I train a network to recognise a certain image, let's say a cat, and then I transfer the input and hidden layers of the network to another dataset and see if the trained weight distribution is a better starting point as opposed to a random distribution through XAVIER etc. etc.

I now wonder, what if the input is different, rather than the output? For example, if I have a dataset of Hotel reviews and build a sentiment analysis type predictor that would predict whether a review is negative or positive, one would have a binary classification problem. If you were then to apply those layers and weights as the starting point to Restaurant reviews, one has changed the input attributes (eg. word stems from a different domain) but the output may still be a binary classification problem for positive and negative classes.

All of the examples of transfer learning I see will change the input and output layers while retaining the hidden layers. If the input changes, but the output does not, is it still Transfer Learning?

Thank you!

This type of transfer learning only applies if you have the same features.  If you don't, you'll either have to do something else, or find some way to first extract a common set of features from both, or choose a feature set that is the union of the two features.  The latter choice would handle the example you gave of hotel reviews vs restaurant reviews.

That said, there is emerging evidence that for deep neural networks, it's not clear that transfer learning (pre-training on a different task) provides any advantage in aaccuracy over training from scratch on the second task.  Recent research has shown that if you train long enough on the second task, you get accuracy as good as if you start with weights from a network that was pre-trained on the second task.  So, it appears the main advantage of this kind of transfer learning might be to speed up training time, rather than to build better models.


NP Complete Proof - Polynomial Reduction We know that the INDEPENDENT-SET problem is NP Complete i.e $\langle G',k'\rangle$ means graph $G'$ has an Independent set of size $k'$. I am preparing for the finals an a sample question is to prove TRIANGLE-FREE-SET to be NP Complete.
$$TRIANGLE-FREE-SET:=\{\langle G,k\rangle| \text{$G$ has a subset of vertices of size $k$ whose induced subgraph is triangle free}\}$$

To give a polynomial reduction of IS instance $\langle G',k'\rangle$ to TFS, I thought of adding an extra vertex and connecting this extra vertex to all the original vertex of the IS problem instance and then have $k=k'+1$. However, I am stuck trying to prove that if $\langle G,k\rangle \in TFS$ then $\langle G',k'\rangle \in IS$. Any leads appreciated.

Probably you can get your answer from here: Reducing independent set to triangle-free subgraph
Basically in order to prove that $TFS$ is NP-complete you can just check the first proof in the link's answer. Given a graph $G$ with an independent set $k$, there exists a $G'$ with a $TFS$ of size $|V|+k+1$.


Understanding simulated annealing information theoretically So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's stationary distribution is the distribution produced by normalizing some function. It's a small leap to realize that you can use this to optimize lots of things and you can even keep rejections that happen to be the minimum you've found so far. But further more you could also reshape the cost function so that it rewards the optimum with much higher probability than anything else (say by exponentiation or squaring the function or something). This has the effect of lowering the entropy of the normalized distribution. If we reshape the target distribution too much though our mixing times could be quite bad. We can solve this by gradually reshaping the target distribution to a low entropy distribution however. Further more higher entropy target distributions should (I think? A proof would be appreciated) have lower mixing times so if our actual target function has low entropy and long mixing times we can fix that. After one researches this line of thinking it quickly becomes clear that this is simulated annealing from a different angle than its generally presented.

The notion of entropy used in physics is deeply connected (or so I'm told) to the notion of entropy used in information theory (which is why Shannon named it as such). The physical notion of entropy is deeply connected to temperature. I've never taken thermodynamics so I don't really understand the bridge between information theoretical entropy, and temperature (which has physical entropy in the middle as the bridge).

Can this link be explained? Given a probability distribution can we define the "temperature" of the distribution? Is there an information theoretical way to define temperature? Perhaps only a subset of distributions have a temperature but we can generate probability distributions that correspond to a given temperature? I'm trying to understand the notion of temperature used in simulated annealing without learning about thermodynamics.

To give a better example of what I'm trying to ask I'll ask by analogy. Understanding what a quantum circuit is doesn't require understanding much of anything about quantum physics for a computer scientist. What's the equivalent understanding of temperature for a computer scientist that knows a bit about information theory?

Along the lines of entropy, what you are trying to get to when using Metropolis or Simulated Annealing is a low entropy state.  You want to find order within the disorder.  Now, Metropolis and Simulated Annealing are slightly different things.  Metropolis' goal is not to find the absolute minimum entropy, it is to recreate a distribution, which may be single mode.  What simulated annealing does is focus the Metropolis to find the absolute minimum.
So in annealing you start at a high temperature, which means basically that anything is possible.  Think of quantum tunneling.  The most improbable thing can happen when temperatures are very high.  So when we begin the optimization, we allow for a whole lot of jumps that you would not see otherwise.  As you cool you focus on just what makes sense so that jumps are made only when they are better.
At a high temperature you will accept propositions at a higher rate to test the space and eventually you stop accepting these wacky ideas to focus on the best solutions only.  In the end you should have a good idea of the optimal solution.


Given 2 regular languages and their DFA's, how to construct the DFA of the union? Suppose $L1, L2$ are both regular languages and $A1, A2$ are their corresponding DFA's.
How can I construct a new DFA for the regular language $L1 \cup L2$?

Let's denote the sets of states in $A_1$ and $A_2$ by $Q_1$ and $Q_2$, respectively. Furthermore, let's denote by $F_1$ and $F_2$ the accepting states of these machines, $q_0'$ and $q_0''$ the start states of these machines, and $\delta_1$ and $\delta_2$ the transition functions of these machines.

We can use the Cartesian-product-machine construction to define an automaton $A_3$ which accepts $L(A_1) \cup L(A_2)$ as follows. First, let $Q_3 = Q_1 \times Q_2$ be the set of states. Now, define $F_3 = \{(q_1, q_2) \in Q_3 \mid q_1 \in F_1 \vee q_2 \in F_2\}$. Let $q_0'''$ be the start state and define $\delta_3((q_1, q_2), \sigma) = (\delta_1(q_1, \sigma), \delta_2(q_2, \sigma))$.

Consider the functioning of such a machine. By virtue of its being in some state $(q_1, q_2) \in Q_3$, we know by construction that $A_1$ would have be in state $q_1$ after seeing the same input, and we know $A_2$ would be in stare $q_2$ after seeing the same input. $A_3$ will accept if either $q_1$ was accepting in $A_1$ or $q_2$ was accepting in $A_2$, because of how we defined $F_3$.

Intuitively, this works by demonstrating that we can model two DFAs executing in lockstep using the DFA formalism itself; two DFAs executing in lockstep is equivalent to the DFA constructed above. We have chosen to accept a string if either of the machines accepts, but as you can see, we could define a DFA for any of the standard binary set operations: union, intersection, difference, symmetric difference, etc.


Show Language is not context free without pumping lemma Can we show that following language is not context free using Push down automata approach?

L = {a^i b^i a^i : i>=1}

For every a we will Push 'A' onto stack, for every b we will pop 'A' out of stack so at the end we will have a's onto stack and the input word would be empty as string would be something like aabbaa

Does it seem correct?

Your approach doesn't work. We don't know how a putative push-down automaton for the language works. What you show is that a particular PDA doesn't work, but perhaps another one does.


Is it possible to include numerical values or constants within brackets(time complexity)? I am currently trying to learn a bit more about the theoretical side of computer science and I have stumbled upon this example I found online:

  $5n^2 + 5n = O(0.5n^2)$

I do have basic understanding of how time complexity works but it is the only example I have found that has a number attached to the $n$ (right side). Does it mean that the person writing that article made a mistake or it is possible to include values this way (like in the definition: $0 ≤ f(n) ≤ cg(n)$ where $c = 0.5$ in this case)?

Sorry if I missed an obvious aspect of this concept but I try learning this stuff on my own and have nobody apart from the internet to ask for help. :)

What you read is slightly unusual, but absolutely correct. Follow the definition of Big-O literally: It means there is a c > 0 such that for large n, f(n) <= c * 0.5 * n^2. It’s exactly the same as O(n^2), except that the constant c is different (twice as big will work).

In your example, for n >= 5 we have 5n <= n^2 and therefore 5n^2 + 5n <= 6n^2. So f(n) <= 12 * 0.5 n^2 and f(n) <= 6*n^2, c=12 instead of c=6.


function in big O but not in little o? Give two functions that is in O(n^2) but not in o(n^2).

The answer is nlogn and n,But I think a lot but can't understand why answer are them.I doubt answers is wrong.

And this question,Give two functions that is in big-omega(n^2) not in
little-omega(n^2)?

The answer is n^2logn and n^3.But I think a lot but can't understand why answer are them.

The answers you give are wrong. It is easy to verify that $n, n\log n \in o(n^2)$, and similarly $n^2 \log n,  n^3 \in ω(n^2)$.

  Give two functions that is in $O(n^2)$ but not in $o(n^2)$.

Looking at the definitions, we see that there are two ways to come up with such a function:

Pick any function from $\Theta(n^2)$.

Besides the obvious candidates of the form $cn^2 + o(n^2)$, there are also more obscure ones like, for instance $ 2^{\frac{\sin n}{\log n}} \cdot n^2$.
Pick any function $f \in O(n^2)$ for which $\lim_{n \to \infty} f(n) \cdot n^{-2}$ does not exist.

Simple examples are $(2 + \sin(n)) \cdot n^2$ or $2^{\sin n} \cdot n^2$ or

$\qquad \displaystyle f(n) = \begin{cases}n^2, &n \in 2\mathbb{N};\\n, &n \in 2\mathbb{N}+1.\end{cases}$

There are many more.

I'll leave the proofs to you as an exercise, as well as the symmetric case with $\Omega$ vs $\omega$.


Optimal algorithm for finding the girth of a sparse graph? I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity.

I thought about some modification on Tarjan's algorithm for undirected graphs, but I didn't find good results. Actually I thought that if I could find a 2-connected components in $O(|V|)$, then I can find the girth, by some sort of induction which can be achieved from the first part. I may be on the wrong track, though. Any algorithm asymptotically better than $\Theta(|V|^2)$ (i.e. $o(|V|^2)$) is welcome.

See Optimal algorithm for finding the girth of a sparse graph from cstheory.SE which has an accepted answer.


Number Partitioning targeting a Ratio of subset sums? I have a problem, which appears to be similar to number partitioning:
a set of numbers partitioned (two-way), such that the sum of the numbers in each subset are as close as possible to a targeted ratio (instead of having the minimum difference, as in the number partitioning problem). Can I use the same algorithms? How would I modify them? Is another approach more suitable?

Context:

I am implementing a load-balancing algorithm, for a work conserving Group Weighted Round Robin (GWRR) scheduler. In some corner-case (some groups have less tasks than CPUs in the system), I want to partition the weighted groups and assign them to the subsets of a partitioning of the set of CPUs, so that the ratio of the sums of (predicted) CPU idle times, in the subsets of the CPU partition, is as close as possible to the ratio of the weight sums, in the subsets of the group partition. The group partition splits the groups, using a normal number partitioning algorithm (CKK), so that group weight sums, in each subset, have the minimum possible difference (but they are unlikely to match, in the general case).

Any ideas?

Yes.  Suppose the numbers are $x_1,\dots,x_n$ and the target ratio is $r$.  Define

$$y=\left\lfloor {1-r \over 1+r} \times (x_1 + \dots + x_n) \right\rceil,$$

and then look for the partition of $x_1,\dots,x_n,y$ that has minimum difference.  I suspect this might be either the solution to your original problem, or very close to it.

Why?  A partition of $x_1,\dots,x_n$ with exactly the ratio $r$ will have one group whose total is $c (x_1+ \dots + x_n)$ and another whose total is $cr(x_1+\dots+x_n)$.  These two must sum to $x_1+\dots+x_n$, so we find that $c+cr=1$, i.e., $c=1/(1+r)$, so their difference is

$$c(x_1+\dots+x_n) - cr(x_1+\dots+x_n) = {1-r \over 1+r} (x_1+\dots+x_n).$$

We have defined $y$ to be this difference, rounded to the nearest integer.  So, if you add $y$ to the smaller group, you get a perfect partition of $x_1,\dots,x_n,y$ with difference zero.  And the converse is true as well.


In LPA*, how are predecessors/successors of a vertex defined? While trying to implement LPA* (mostly based on its description in the same authors’ paper on its derivative D*Lite), I noticed it mentions predecessors and successors of a vertex without giving a full explanation.

I understand that $Pred(u)$ is the set of all vertices from which an edge leads towards $u$, and $Succ(u)$ is the set of all vertices towards which an edge leads from $u$. Predecessors and successors must be immediate neighbors (thus e.g. a predecessor of a predecessor of $u$ is not necessarily a predecessor of $u$).

In practice, however, it is quite common to have edges that are not directional, i.e. can be traversed both ways (which is equivalent to the same two nodes being connected by two antiparallel directional edges). I infer that for two vertices $u$ and $v$ connected in this way, $u$ would be both a predecessor and a successor of $v$ (and vice versa). In other words, $Pred(u) \cap Succ(u)$ is not necessarily empty.

Am I correct to assume that predecessor and successor are defined only by the existence of an edge traversable in a given direction, and are specifically not related to start cost?

If you have an undirected graph, you can convert it to a directed graph by including edges in both directions: for each undirected edge $(u,v)$, add directed edges $u \to v$ and $v \to u$.  So, if you have undirected edges, imagine applying this transformation and then running LPA* on the resulting graph.  That should make it clear what to do.

Alternatively: in an undirected graph, Pred(u) is the set of all edges incident on $u$, and so is Succ(u) (there is no distinction between them in an undirected graph).  So, yes, they can overlap.

The cost of the edges are irrelevant.


How to show that a problem is easy? Let $P$ be a problem that you need to study its difficulty, i.e., NP-hard, Polynomial-time solvable, etc.

  My question is: If I reduce a known polynomial time problem (say,
  maximum matching in bipartite graph) to $P$, why I can say that $P$ is an
  easy problem?

  My guess is: No, we cannot say that.

  Why? Because from an instance of maximum matching problem, $I_{ MM }$,
  I create an instance of $P$, $I_{ P }$, and then I show that maximum
  matching is solved with $I_{ MM }\iff P$ is solved with $I_{ P }$.

  But what if from another instance of maximum matching problem, $I_{ MM }'$
  , I create another instance of $P$, $I_{ P }'$, which is hard to
  solve?

I have read that the reduction is correct and works, for example from sorting to convex hull, but I do not why.

I do not know what I am missing here.

You are right. Any problem in $\mathsf{P}$ can be (polytime) reduced to the halting problem, for example. (In fact, any problem in $\mathsf{P}$ can be polytime reduced to any non-trivial language, that is any language other than $\emptyset$ or $\Sigma^*$.)

What is true is that if A reduces to B and B is easy, then so is A. In particular, if A polytime reduces to B and B is in $\mathsf{P}$, then A is also in $\mathsf{P}$.


How is a Transition System in Operational Semantics defined? I'm describing the semantics of a new optimization for Java using Operational Semantics but I'm not sure how to define the transition system.

I found this link :http://www.irisa.fr/celtique/teaching/PAS/opsem-2016.pdf where in slide 20 the transition system is defined but I don't get it.

Operational semantics utilizes the tools of logic, so as a prerequisite we must understand judgements and inference rules.

A judgement is like a proposition, but more general. It asserts a relation between two entities of our language. For example, in programming, we often employ the judgement $e: \tau$, asserting that expression $e$ has type $\tau$.

Inference rules are used to define judgements. They have the general form

$$ \frac{J_1 \dots J_n}{J} $$

which reads: if we know judgements $J_1$ through $J_n$, we can infer judgement $J$. For example, we may have the following self-explanatory inference rule for the previously defined typing judgement:

$$ \frac{n: \text{int} \quad m: \text{int}}{n+m: \text{int}}. $$

A structural operational semantics is defined using a transition system between states. In a programing language, the states are all closed expression in the language, and the final states are values. Formally, we make use of two judgements:

$e_1 \to e_2$, stating that expression $e_1$ transitions to state $e_2$ in one step
$e \space \text{final}$, stating that expression $e$ is a final state of the system.

Here are some example inference rules in a language with arithmetic and function abstraction:

$$ \frac{}{n \text{ final}} $$
$$ \frac{}{n+0 \to n} $$
$$ \frac{n + m \to k}{s(n) + m \to s(k)} $$
$$ \frac{}{\lambda x. e \ \text{final}} $$
$$ \frac{(\lambda x. e_1)e_2}{[e_2/x]e_1} $$

Most languages do not have a formal definition, including Java (as far as I know). There are also other methods for defining the semantics of a language, but for describing an optimization, I believe structural dynamics is a wise choice, as it has a natural notion of time complexity (the number of transitions).


Prove NP-completeness of deciding whether there is an edge-tour of at most a given length We are given a graph G, integer b < |E|, and subset F in E. The problem is to detect whether there is a cycle in the graph with length at most b and includes each edge in F. Prove that this is NP Complete.

I'm thinking of reducing from Hamiltonian Path, but still can't think of the appropriate transformation function.

It is a standard variation of the Travelling Salesman Problem.

To force an edge to be a part of the answer, break it in half and insert a new vertex.

Update A reduction in the other direction consists of "breaking all vertices in two".

More precisely, given a directed graph $G$, form another graph $G'$. For each vertex $v$ in $G$, create a pair of vertices $v_i$, $v_o$ in $G'$. For each edge $(uv)$ in $G$, create an edge $(u_ov_i)$ in $G'$. Also, for each $v_i$, $v_o$ add an edge ($v_iv_o)$, and let it belong to $F$. Now every cycle in $G'$ that contains all edges in $F$ also contains all vertices, and corresponds to a Hamiltonian cycle in $G$.


How to calculate whether a parenthesis string is valid using a 2-tape Turing machine? If I have a language over alphabet $\Sigma=\{(,[,],)\}$. How can I find out if a tape has a valid (matching) parentheses structure in linear time?

So far, my attempt is as follows:

state 0: accept ( or [ i.e. no open parentheses
state 1: accept ), ( or [ i.e. a ( has occurred previously
state 2: accept ], ( or [ i.e. a [ has occurred previously

The problem with this setup is that I won't know how many ( or [ has occurred previously. One idea was to store how many occurrences of open parentheses of each kind on the second tape, but this would potentially require an infinite tape alphabet. So it seems as if I'm approaching the problem the wrong way.

How can I create a Turing machine that wouldn't need to store the amount of open parentheses while still being able to accomplish this in linear time?

I looked at this question already, but couldn't figure out how this would be applicable to multiple types of parentheses and still be done in linear time.

Any input would be much appreciated!

As others have pointed out, you can use a stack to check for matching parentheses. Such manipulation is the base idea of the shunting yard algorithm by Dijkstra.


Why do we need $k \geq n$ in Dijkstra's token ring self-stabilizing system? Let's say I have a ring with four nodes $n=\{0;1;2;3\}$ and three possible states $k=\{0;1;2\}$. A transient failure happens and the system ends up in an illegal state.

I know from the restriction ($k \geq n$) that there should be an execution that makes the system stay in its illegal state indefinitely, but for all the executions I try in my head and on paper, it still stabilises at some point. Could you give me an execution where it loops always back into its illegal state?

Here is how to solve this for your particular $n$ and $k$. Your system has $k^n = 81$ possible states. You can describe the evolution of the system as a directed graph: there is an edge $s_1 \to s_2$ if state $s_1$ evolves in one step to state $s_2$. Some states are legal, some are illegal. You want to find an illegal state $s$ from which no legal state is reachable. This is a question that can be solved using a graph traversal algorithm such as DFS.

Once you find such a state, you can try to generalize the construction to other values of $n$ and $k$. Other simulations (with other values of $n$ and $k$) could be helpful here.


Are SAT problems with at most two false clauses NP-complete? Is the problem of deciding whether a SAT instance, where at most two clauses are false (that is, any given variable assignment will either lead to all clauses being true, all but one, or all but two), is satisfiable solvable in polynomial time?

This is a follow-up from my previous question. The problem presented in that question (at most one false clause) was solvable in polynomial time, because we could take advantage of the fact that the set of truth assignments that make a clause false is disjoint to that of any other clause. With two or more clauses, the sets that make a clause false can overlap with each other. Does this mean that problems with at most two (or more) false clauses (when I say "or more," I do not mean that the number can change with the problem size. A problem with five clauses where at most five are false is a trivial version of regular SAT, but what about a problem of a few million clauses where are most five can be false?) are NP-complete, or are all versions of SAT where you limit the number of false clauses solvable in polynomial time?

Yes.  You can solve this in polynomial time.  The same strategy as in Are SAT problems with at most one false clause NP-complete? works.

Let $\varphi$ denote the CNF formula you care about, and $n$ the number of variables in $\varphi$.  Let $A_{i,j}$ denote the number of truth assignments that do not satisfy clauses $i$ or $j$ of $\varphi$, let $A_i$ denote the number of truth assignments that do not satisfy clause $i$ but do satisfy all other clauses of $\varphi$, and let $A$ denote the number of truth assignments that satisfy all clauses of $\varphi$.

These three cases are mutually exclusive.  Therefore,

$$\sum_{i,j} A_{i,j} + \sum_i A_i + A = 2^n,$$

where $n$ counts the number of variables in the formula.  In other words,

$$A = 2^n - \sum_{i,j} A_{i,j} - \sum_i A_i.$$

You can compute $A_i$.  Let $S_i$ denote the set of variables mentioned in clause $i$.  There is only one assignment to the variables in $S_i$ that will make clause $i$ false, so substitute in those values for the variables in $S_i$ and simplify the formula; the result is a CNF formula $\varphi'$ where we are guaranteed that every assignment to the remaining $n-|S_i|$ variables satisfies at most one clause, so https://cs.stackexchange.com/a/115849/755 tells us how to count the number of satisfying assignments to $\varphi'$, say $n_i$.  Then $A_i = n_i$.

You can compute $A_{i,j}$.  It is either $2^{n-|S_i \cup S_j|}$ or $0$, depending on whether there is any variable $x_k$ such that both $x_k$ and $\neg x_k$ appear in those clauses $i$ and $j$ of $\varphi$.

Therefore, you can compute $A$, the number of assignments that satisfy the formula.  Now, if $A \ne 0$, then you know that the formula is satisfiable; if $A=0$, the formula is not satisfiable.


Beginner help with Arrays & Complexity My goal is to create a method that gets an array that only has 1's and 0's in it, and then turns every number into the amount of 'steps' it is away from the closest 0, left or right.

So for example [1] - [1] - [0] - [1] - [1] - [1] - [1] - [1] - [0] - [1]  would be
[2] - [1] - [0] - [1] - [2] - [3] - [2] - [1] - [0] - [1]

I also need to do it as simple as possible in terms of time and space complexity.

I'm not sure how to make it count how far a certain spot is from a 0 if it's from the right of the 0, or if there's another 0 nearby I'm not sure how to make it count which one is closest.

I'm assuming two for loops are needed?

Made a sketch: no idea if it makes sense.

 for (int i=0; i<a.length; i++)
{

    for (int j=i; j<a.length; j++)
    {
     if (a[j]==0)
      {
       if (i<j)
         {
           a[i]=j-i;
         }
        if(j<i)
         {
           a[i]=i-j;
         }
       }
    }
 }

Let's try to solve a simpler problem first:

Given an array that only has 1's and 0's in it, the method turns every number into the amount of 'steps' it is away from the closest 0 to the left.

Now this problem is easy. A simple solution is: traverse the array from left to right, keeping track of the distance from the last zero encountered and updating each element with the distance.

A simple code:

dist = INF
for(i=0;i<a.length;i++){
    if(a[i] == 0)
       dist = 0;
    else
       dist++;
    b[i] = dist;
}

Now once you have solved the simpler problem for closest 0 to the left, you can similarly solve the problem for closest 0 to the right. With these two solutions, you should be able to easily get a solution for the original problem (by taking a min of the two solutions).

The solution evidently has O(n) time complexity, and can be easily coded to use only O(1) space by carefully manipulating the updates in the original array only.


How to analyze the performance of a genetic algorithm experimentally? I have a genetic algorithm for an optimization problem.
I plotted the running time of the algorithm on several runs on the same input and the same parameters (population size, generation size, crossover, mutation).

The execution time changes between executions.
Is this normal?

I also noticed that against my expectation the running time sometimes decreases in place of increasing when I run it on a larger input.
Is this expected?

How can I analyze the performance of my genetic algorithm experimentally?

The typical approach is performing several runs of the evolutionary algorithm (EA) and plot the average performance over time (average performance of best-of-run-individual NOT population average).

A good rule of thumb is performing a minimum of 30 runs (of course 50-100 runs is better).

The average is better than the best-value-achieved-in-a-set-of-runs but variance should also be taken into account.

There are some nice examples on Randy Olson's website:

  The average fitness of both algorithms over several replicates. From this graph, we would conclude that our algorithm performs better than the current best algorithm on average.

  The average fitness with a 95% confidence interval for each algorithm. This graph shows us that our algorithm does not actually perform better than the current best algorithm, and only appeared to perform better on average due to chance.

The basic breakdown of how to calculate a confidence interval for a population mean is as follows:

Identify the sample mean $\bar{x}$. While $\bar{x}$ differs from $\mu$, population mean, they are still calculated the same way: $$\bar{x} = \sum {x_{i} \over n}$$
Identify the (corrected) sample standard deviation $s$: $$s = \sqrt{\frac{\sum_{i=1}^{n}{(x_i - \bar{x})^2}} {n-1}}$$
$s$ is an estimation of the population standard deviation $\sigma$.
Calculate the critical value, $t^*$, of the Student-t distribution. This value is dependent on the confidence level, $C$, and the number of observations, $n$.

The critical value is found from the t-distribution table (most statistical textbooks list it). In this table $t^*$ is written as $$t^*(\alpha, r)$$ where $r = n-1$ is the degrees of freedom (found by subtracting one from the number of observations) and $\alpha = {1-C \over 2}$ is the significance level.

A better way to a fully precise critical $t^*$ value is the statistical function implemented in spreadsheets (e.g. T.INV.2T function), scientific computing environments (e.g. SciPy stats.t.ppf), language libraries (e.g. C++ and boost::math::students_t).
Plug the found values into the appropriate equations:
$$\left({\bar x} - t^{*}{\frac {s} {\sqrt n}}, {\bar x} + t^{*}{\frac {s} {\sqrt n}}\right)$$
The final step is to interpret the answer. Since the found answer is an interval with an upper and lower bound it's appropriate to state that, based on the given data, the true mean of the population is between the lower bound and upper bound with the chosen confidence level.

The more the confidence intervals of two algorithms overlap, the more likely the algorithms are to perform the same (or we haven't sampled enough to discriminate between the two). If the 95% confidence intervals don't overlap, then the algorithm with the highest average performance performs significantly better.

In EA, the source distribution is essentially never normal and what said so far formally applies only if it's a normal distribution!

Indeed it still tells many things. The following table summarizes the performance of the t-intervals under four situations:

                             Normal curve | Not Normal curve
Small sample size (n < 30)      Good      |       Poor
Larger sample size (n ≥ 30)     Good      |       Fair

For more accurate answers non-parametric statistics are the way to go (see An Introduction to Statistics for EC Experimental Analysis by Mark Wineberg and Steffen Christensen for further details).


What can Idris not do by giving up Turing completeness? I know that Idris has dependent types but isn't turing complete. What can it not do by giving up Turing completeness, and is this related to having dependent types?

I guess this is quite a specific question, but I don't know a huge amount about dependent types and related type systems.

Idris is Turing Complete! It does check for totality (termination when programming with data, productivity when programming with codata) but doesn't require that everything is total.

Interestingly, having data and codata is enough to model Turing Completeness since you can write a monad for partial functions. I did this, years ago, in Coq - it's probably bitrotted by now but here it is nevertheless: http://eb.host.cs.st-andrews.ac.uk/Partial/partial.v.

You do need one escape to actually run such things, but Idris allows you to do that.

Idris won't reduce partial functions at the type level, in order to keep type checking decidable. Also, only total programs can reasonably be believed as proofs.


Runtime analysis of while-loop analysis s = n
while (s > 4)
  s = s / 2
else
  s = s - 1

Let $T(n) = \Theta(S(n))$ where $S(n)$ is number of while-loop runs.

$S(n)=1 + S(n/2)$ if $n$ is even

$S(n)=1 + S(n-1)$ if $n$ is odd

$S(n)=0$ if $n \leq 4$

By converting n to a binary number, and I think

if $n < 2^k$, then $S(n) \leq k - 1$

I have come to this relationship, yet can't figure out how to approach to $\Theta $ bound.

Any help or guidance is appreciated.

It is a strange grammar that while is combined with else in your pseudocode. There is such grammar in Python but it is obviously not the case. I guess you mean

s = n
while (s > 4)
  if (s is even)
      s = s / 2
  else
      s = s - 1

Anyway, let's start with your recursion formula.

Consider $n>4$. Note if $n$ is even, $S(n)=1+S(n/2)=1+S(\lfloor n/2\rfloor)$, and if $n$ is odd, $S(n)=1+S(n-1)=2+S((n-1)/2)=2+S(\lfloor n/2\rfloor)$. So anyway, for $n>4$ we have

$$1+S(\lfloor n/2\rfloor)\le S(n)\le 2+S(\lfloor n/2\rfloor).\quad (1)$$

Suppose $2^{k-1}\le n < 2^k$, you can prove

$$ k-2\le S(n)\le 2(k-2).$$

using mathematical induction (the formal proof is  left to you as an exercise). So $S(n)=\Theta(k)=\Theta(\log_2 n)$.

From (1) we can write $S(n)=S(\lfloor n/2\rfloor)+f(n)$ where $1\le f(n)\le 2$, i.e. $f(n)=O(1)$. Then Master Theorem applies.


How to best calculate the best possible path with weights Given a set of nodes, with connections in certain directions (see image), what is the most coins you can collect between the first and last given node. Not all rooms have coins, and we want to output the path taken, as well as total coins taken. You may only travel in the direction of the arrows. We are allowed to take the same path twice. The solution for the situation in the figure below is the path 1 - 4 - 3 - 2 - 1 - 5 - 7 - 9 - 10 - 8 - 12, with a total of 7 coins. I think this should be possible in linear time. My idea so far is to start at the last node and go back, saving the "best attainable score" for each node. However, this implementation runs into issues when there are cycles in the graph. Is there a better way of doing this?

edit: Assuming n nodes, there will never be more than 10n connections total.

Build the metagraph of strongly connected components.  Then execute your idea on the metagraph.  Note that once you enter a strongly connected component through any in-edge, you can collect all coins within it and leave through any out-edge out of that component.


What is the complexity of determining Satisfiability of a CNF containing both Horn and Dual Horn clauses? If a CNF contains both horn and dual horn clauses and does not contain clauses of other types, then can its Satisfiability always be determined in polynomial time?

If the answer to the above problem is yes, then suppose we only add XOR clauses in addition to horn and dual horn clauses, can the Satisfiability of this type of CNF be determined in polynomial time?

3-CNF formulas contain a mixture of only Horn and dual-Horn clauses.  3-SAT, the Boolean satisfiability problem over 3-CNF formulas, is known to be NP-complete.  So it is unlikely that the satisfiability of such formulas can be decided in polynomial time.


What is a loop variable? In the context of compilers, what exactly is a loop variable (if there is a standard definition)?

Every read/write make up for the loop variable, or only writes make them up? Or is it writes in the body and reads in the condition?

The term that I was taught (thanks, Dragon Book!) is "induction variable". It refers to any variable which is a linear function of the number of iterations in a loop.

I don't know the term "loop variable", but if I had to guess, it would refer to a variable whose value changes inside the loop, and which is tested to decide the loop termination condition.

But to be honest, it would depend what you were trying to use it for. Pick whatever definition helps your analysis.


Generate random matrix and its inverse I want to randomly generate a pair of invertible matrices $A,B$ that are inverses of each other.  In other words, I want to sample uniformly at random from the set of pairs $A,B$ of matrices such that $AB=BA=\text{Id}$.

Is there an efficient way to do this?  Can we do it with expected running time approaching $O(n^2)$?

Assume we are working with $n\times n$ boolean matrices (all entries 0 or 1, arithmetic done modulo 2).  I am fine with an approximate algorithm (say, it samples from a distribution exponentially close to the desired distribution).  My motivation is solely curiousity; I have no practical application in mind.

The obvious approach is to generate a random invertible matrix $A$, compute its inverse, and set $A=B^{-1}$.  This has running time $O(n^\omega)$, where $\omega$ is the matrix multiplication constant -- something in the vicinity of $O(n^3)$ in practice.  Can we do better?

An approach that occurred to me is to choose a set $T$ of simple linear transformations on matrices such that, for each $t \in T$, we can apply the modifications $M \mapsto tM$ and $M \mapsto Mt^{-1}$ in $O(1)$ time.  Then, we could set $A_0=B_0=\text{Id}$, and in step $i$, sample a random $t$ from $T$, set $A_{i+1}=tA_i$ and $B_{i+1}=B_it^{-1}$, and repeat for some number of steps (say $O(n^2 \log n)$ iterations).  However I'm not sure how we would prove how quickly this approaches the desired distribution.

Efficient Generation of Random Nonsingular Matrices by Dana Randall covers exactly this topic. In particular Corollary 1.1 states:

  We can uniformly generate a matrix and its inverse in time $2M(n) + \mathbb{E}[O(n^2)]$.

Where $M(n)$ is the time it takes to multiply two $n \times n$ matrices.

Unfortunately this is not better than what you had hoped for.


How to pronounce "P/poly"? Another question is about the reasons for calling P/poly "P/poly".  My question is instead about its (verbal) syntax rather than its compositional semantics:

How is "P/poly" pronounced (in English)?

Like "p polly"?
Like "p slash polly"?
Like "p given polly"? (Maybe the slash for advice is analogous to slash or vertical bar for conditional probability: $\mathsf{P}(A/B)$.)

I hope it's OK to ask such a trivial question.  I'd rather not develop a bad habit during self study.

The Complexity Zoo has a pronunciation guide by Scott Aaronson "for those who insist on communicating verbally about complexity." It recommends the "p slash polly" option.


Comparing the complexity of algorithms for listing k-cliques Chiba and Nishizeki showed that it is possible to list all $k$-cliques (cliques on $k$ nodes) in time $O(m \cdot a^{k-2})$ where a is the arboricity of the graph and $m$ the number of edges in the graph. http://www.ecei.tohoku.ac.jp/alg/nishizeki/sub/j/DVD/PDF_J/J053.pdf

We have designed an algorithm that can do it in time $O(m \cdot \frac{(2a)^{k-2}}{(k-2)!})$.
In practice, on real-world graphs (which have a small arboricity), our algorithm performs much better than the one of Chiba and Nishizeki. We now want to show through theory that it is better.
So the question is, how can we show that $O(m \cdot \frac{(2a)^{k-2}}{(k-2)!})$ is better than $O(m \cdot a^{k-2})$?
Note that we are interested in instances of small $k$, say 10 or less. Is the big O notation relevant here? Or should we work with upper bounds and lower bounds on the number of operations (quantifying the constants in the big O)?

$O(m \cdot \frac{(2a)^{k-2}}{(k-2)!})$ is not necessarily better than $O(m \cdot a^{k-2})$, since the big-oh notation $O$ is an upper bound. To compare the two algorithms, you'd better analyze using the $\Theta$ notation. In addition, note that if you set $k$ to some fixed value, terms such as $\frac{2^{k-2}}{(k-2)!}$ are considered to be constants and thus omitted in asymptotic analysis.


Finding a graph-theoretic representation of expressions in Boole's algebra I just read "Boole's Algebra Isn't Boolean Algebra" by Theodore Halperin (behind a paywall here). I don't have a strong background in abstract algebra, so, frankly, the paper is a bit over my head but the gist of it is as follows: the algebra developed by Boole in the 19th century has some strange properties. Boole interprets every term in an expression as representing a set and restricts the domain of valid expressions on the basis of relationships between the underlying sets. In particular, he asserts that the expression $x + y$ is valid iff $x$ and $y$ represent disjoint sets, and $x - y$ is valid iff the intersection of $x$ and $y$ is nonempty. He also defines an operation $w = \frac x y$ such that $w$ has many solutions. Halperin goes to great lengths to construct a commutative ring that satisfies Boole's constraints.

I think that there might be a nice, intuitive, graph-theoretic interpretation of Boole's algebra where we can say something like "Given a complex expression in Boole's algebra, $\Phi = \{\phi_1, \phi_2\, \dots, \phi_n\}$, we can construct a (di)graph $G$ such that $\Phi$ is valid if and only if $G$ has some property $P$."

For example, to test if $X + Y$ is valid, we could do something like the following:

Let $G$ be a graph. Let $V(G) = X \cup Y \cup \{v_X, v_Y\}$, i.e. make a vertex for every element of the underlying set, plus a vertex for each term in the expression. Then define

$$E(G) = \{uv_X \mid u \in X \} \cup \{uv_Y \mid u \in Y \}$$

and let $\partial(G)$ be the set of all valid bonds formed by subsets of $V(G)$. It follows that $X + Y$ is valid if and only if $|\partial(G)| = 2$.

From there, I'm not sure how to go about forming graphs for complex expressions like $\frac {y(x + z)} {z^2 + 1}$ by composing simpler graphs. I imagine that there is literature about representing Boolean algebra on graphs, but I haven't been able to find it.

Does anyone have an elegant interpretation? Or a pointer to relevant literature that might get me started?

EDIT: I can't find the article for free anywhere, but wikipedia touches on the issues:

  In places, Boole talks of terms being interpreted by sets, but he also
  recognises terms that cannot always be so interpreted, such as the
  term 2AB...Such terms he classes uninterpretable
  terms...uninterpretable terms cannot be the ultimate result of
  equational manipulations from meaningful starting formulae.

Halperin's paper shows that his algebra is isomorphic to "a commutative ring with unit having no additive or multiplicative nilpotents." I think, for that reason, that it will require heavier machinery to represent than normal Boolean logic operations.

A bit of shameless self-promotion, but you might find http://www.sciencedirect.com/science/article/pii/0895717794001669 relevant, as well as the earlier paper I cite there by Frank Harary.

Those papers present the idea that a boolean function can be represented as a hypercube in which the vertices represent combinations of truth values. That is, rather than construct a graph with a vertex for each boolean variable X, Y etc, construct a graph where one vertex represents the tuple <X=0,Y=0>, one represents <X=0,Y=1> etc.


is it possible to have a mapping reduction between 2 NP complete languages? so i have a good understanding about languages that belong to NP, P and NP complete, and how Polynomial reduction works between languages that belong to those areas.  but i just can't figure out a conclusion about mapping reduction between languages in those areas.
for example if i have 2 languages - A and B, that both of them are NP-Complete,
can i do a  A ≥m B (mapping reduction) or B ≥m A ?

You certainly can! This is how NP-completeness works: every NP-complete problem can be mapping-reduced to every other NP problem, by definition.

For example, consider the Boolean Satisfiability Problem: given some assortment of variables joined together by AND, OR, and NOT, is there any assignment of True and False to those variables that will make the whole thing evaluate to True? This problem is NP-complete.

Consider also the 3Sat problem, a convenient one to use in all sorts of NP-completeness proofs. This is the same as the Boolean Satisfiability Problem, except that the input is a series of clauses joined by AND, where every clause consists of exactly three terms joined by OR, and a term is either a variable or the negation of a variable.

Since every 3Sat input is a Boolean formula, 3Sat can be trivially reduced to Boolean Satisfiability. And there's a method of converting any Boolean Satisfiability problem into an equivalent 3Sat input in polynomial time.

Therefore, $\mathrm{3Sat} \leq_M \mathrm{BooleanSatisfiability}$, and $\mathrm{BooleanSatisfiability} \leq_M \mathrm{3Sat}$.

(It's easier to understand this with general problems, but this can be trivially rephrased to work with languages, as in your question: let the language $\mathrm{BooleanSatisfiability}$ consist of the binary encodings of inputs for which the Boolean Satisfiability Problem should return true, for example.)


How can one byte hold 256 possibilities? Forgive this seemingly "troll-ish" question, but I must lack the ability to understand how one byte (two nibbles, eight bits, however you wish to describe it) can hold 256 different states, possibilities, values or such.

First of all, one bit would look like this:

Any way of being able to input two states (in the poor example above, two separate circuits at different voltages can be treated logically as "yes" or "no").

So if one bit is two possible states, multiplication factors yield that by two:

Bit = 2 values

Two bits = 4 values

Three bits = 6 values

Four bits = 8 values

Five bits = 10 values

Six bits = 12 values

Seven bits = 14 values

Eight bits = 16 values

In total, I get a sum of sixteen values multiplying the factors by two for every increasing bit. How would it make sense that one byte can hold 256 different values in a circuit?

In a four bit adder, we'd have something like this:

This also yields 8 possible values. How would it get 128? Could anyone clarify this confusion??

NOTE: This doesn't have to just apply to adders circuits with transistors and logic gates, but to the pits and lands on an optic disc, the platter representation of data on a disk drive, flash drive binary storage, RAM, anything. I just want to know how increasing factors of two is multiplied by (seemingly) powers thereof.

I just did a quick animation to convince you. Yellow is one, blue is zero.


Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$ Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$

My first intuition is "Yes", since we may look at $M_1, M_2$ which accepts $L_1, L_2$, respectively. Then, WLOG there's $w$ such that $M_1$ doesn't halt for, and so the machine $M$ which runs $M_1, M_2$ in parallel, may not halt.

Hint: Let $L$ be any language in $\mathsf{RE} - \mathsf{R}$, and consider
$$ L_1 = 0\Sigma^* \cup 1L, \quad L_2 = 1\Sigma^* \cup 0L. $$


Determine if a string is a permutation of another string efficiently Given two strings of the same length, determine if they are permutations of each other.

I can come up with two solutions, one in O(n log n) time with O(1) extra space, and one in O(n) time with O(n) extra space, but I'm wondering if there are more efficient algorithms.

If we sort the strings in-place and compare them, we get O(n log n) time with O(1) extra space.

If we use a hashtable from character to count, we can keep track of how many of each character we have in the first string, and subtract accordingly when reading characters from the second string. That's O(n) time and O(n) extra space.

Can we do better?

You can establish a trivial lower bound of $\Omega(n)$, because you must at least observe all characters of each string (in worst case) to determine if they are permutations of each other. So $O(n)$ time complexity is the best you could do.

Perhaps you could improve the space complexity though. Raphael describes a unique approach here to achieve constant space and linear time using properties of prime numbers.


Words generated by CFG whose parse tree contain even number of $X$ Let $G$ be a context-free grammar with set of terminals $A$. Let $X$ be a non-terminal in $G$. Is the language of words over the alphabet $A$ with a syntax tree in which the non-terminal $X$ appears even number of times is context-free?

Add a new terminal $x$ to the alphabet, and replace $X$ with $xX$ in the right-hand side of all productions. Denote the corresponding context-free grammar by $G'$, and let $h\colon A \cup \{x\} \to A^*$ be the homomorphism erasing $x$. Then your language is $$ h(L(G') \cap A^*(xA^*xA^*)^*). $$
Since the context-free languages are xlosed under homomorphism and intersection with a regular language, it follows that your language is context-free.


DFA that accepts a*b*c* Beginner in DFA related studies, was trying to figure out how to create a DFA with {a,b,c}, that can recognize a * b * c *.

Appreciate the help.

Here is a possible DFA:

Basically, just send any invalid string like baac, caa*, etc. to a junk state.

As suggested by Yuval Filmus, you can minimize the number of states further by merging $s$ and $a$ :


Efficient map data structure supporting approximate lookup I'm looking for a data structure that supports efficient approximate lookups of keys (e.g., Levenshtein distance for strings), returning the closest possible match for the input key. The best suited data structure I've found so far are Burkhard-Keller trees, but I was wondering if there are other/better data structures for this purpose.

Edit:
Some more details of my specific case:

Strings usually have a fairly large Levenshtein difference from each other.
Strings have a max length of around 20-30 chars, with an average closer to 10-12.
I'm more interested in efficient lookup than insertion as I will be building a set of mostly static data that I want to query efficiently.

What you are looking for is "approximate near neighbor search" (ANNS) in the Levenshtein/edit distance. From a theoretical perspective, edit distance has so far turned out to be relatively hard for near-neighbor searches, afaik. Still, there are many results, see the references in this Ostrovsky and Rabani paper. If you are willing to consider alternative distance metrics for which there are simpler and better solutions, move on to the next paragraph. For ANNS in edit distance, there is a result due to Indyk, who shows how to build a data structure of size $n^{O(\sqrt{d})}$ that answers any query in time $O(d)$ and reports a string which is at most three times further than the string nearest to the query string (this generalizes to size $n^{O(d^\epsilon)}$ and approximation $3^{1/\epsilon}$). Here $n$ is the number of strings and $d$ is the maximum length of any string. The Ostrovsky and Rabani paper I linked above improve this result by mapping strings to vectors so that the $\ell_1$-distance (a kind of natural geometric distance similar to the euclidean distance) between vectors approximates the edit distance between the corresponding strings (this is called a "low-distortion embedding"). Once this is done, an ANNS data structure for $\ell_1$ can be used, and these turn out to be more efficient (see next paragraph).

If you are willing to consider other distances, then locality sensitive hashing (LSH) does a great job. Locality sensitive hashing is a technique pioneered by Indyk and Motwani for solving the ANNS problem, where points that live in a high-dimensional space (read long vectors, long strings, etc.) are hashed into a small number of buckets so that points that are near each other are mapped to the same bin with good probability and points that are far from each other are mapped to different bins, also with good probability. There is a great and very accessible survey article by Indyk and Andoni in CACM. This technique is simple and fast, and has small space requirements; there is code out there too (I think the article links to the code). It works well for things like Hamming distance (and in certain regimes $\ell_1$ distance) and Euclidean distance, cosine distance. Also, Muthu and Sahinalp design LSH schemes for a very natural generalization of edit distance, the block edit distance (where a some edit operations can operate on a block of symbols).

This kind of question is a good fit for cstheory.SE. There is a related question there, but it seems to ask for exact near neighbor.


Is it possible to prove Turing irreducibility Given two languages $L_1$ and $L_2$, is there a known way to show that $L_1\not\leq_T L_2$?

In other words, is it possible proving that there is no Turing reduction from $L_1$ to $L_2$?

Let $A_{TM}$ be the language of the Halting problem. Then $\overline{A_{TM}} \nleq_T A_{TM}$, otherwise $A_{TM }$ would be recursive.

Another well-known theorem by Friedberg–Muchnik proves (using the finite injury priority argument) that there are recursively enumerable languages $A$ and $B$ such that $A \nleq_T B$ and $B \nleq_T A$ (pairwise incomparable).

R. Soare's book, for example, has more on this subject.


trace vs. computation vs. run vs. execution vs. walk Many folks use the terms "trace", "execution", "computation", "run", "walk" ... interchangeably when they speak about state machines with labeled transitions.  Does any work distinguish between these concepts?  E.g., which work says that XXX is a sequence of states, YYY is a sequence of labels and ZZZ is a sequence of states and labels between them, for pairwise different XXX, YYY, ZZZ in {trace, execution, computation, run, walk, ...}?

Here, a state machine with labeled transitions is simply a rooted directed graph (where arbitrarily many roots are allowed, which are interpreted as initial states) with edges labeled by letters from a fixed alphabet.

There is no set terminology for this. Check the definition/use of the term where it appears.

Personally, I'd call it "computation", meaning the sequence of configurations the automaton goes through. And try to be consistent with this usage.


Does NP-completeness require to find the solution? In the paper "Computing Equilibria:A Computational Complexity Perspective" by Tim Roughgarden, they consider the problem:

Problem 2.1 (Clique).  Given a graph $G = (V, E)$ and an integer $k$:

if there is a set $K ⊆ V$ with $|K| = k$ and with $(i, j) ∈ E$ for every distinct $i, j ∈ K$, then output such a set;
otherwise, indicate that $G$ has no $k$-clique.

Then they claim that Problem 2.1 is NP-complete in the Theorem 2.7.

My question is about the part (1).  I always thought NP-completeness is for yes/no problems and thus they didn't require that the the solution be output if the decision is an yes?

So is this definition of NP-complete problem 2.1 right? Or should part (1) be rephrased as "if there is a set $K \subseteq V$ with $|K| = k$ and with $(i, j) \in E$ for every distinct $i, j \in K$, then output yes;

The Problem 2.1 is a half decision problem and half feasibility problem, what are such problems called?

P.S the paper can be found at http://theory.stanford.edu/~tim/papers/et.pdf

I went through Optimization version of decision problems and still not sure where Problem 2.1 belongs to.

You are right that NP-completeness applies only to decision problems. What they mean by "Problem 2.1 is NP-complete" can be either

  The decision problem corresponding to Problem 2.1 is NP-complete

or

  The decision problem corresponding to Problem 2.1 is NP-complete, and the search problem is in FNP

Here the search problem is finding a clique of size $k$ if one exists. We think of the search problem as a two-place predicate $f(\langle G,k \rangle,K)$ which is true if $G$ is a graph and $K$ is a $k$-clique of $G$. This search problem is in FNP if the predicate $f$ is in P. (Usually FNP is defined for functions, i.e. for relations which are functions, but you can also define it for general relations.)


Wrong DFA from NFA. String Does not contains 110 I am doing problem 1.g.
My Approach is to first create a NFA that accepts this string i.e. all strings having 110. Then converting it into DFA and then complementing it. I have the answer what should I get however my NFA to DFA conversion doesn't work. I don't know why. Can anyone guide me. Thanks. Here is my NFA. Note this is not full answer as there is complement left to be done. But I am stuck in between.

Then I converted it into FSA

This is What I got

I know there is a mistake that there should be self loop of 1 on the AC state but from my above NFA, I am unable to obtain it. Is my NFA wrong? Or I have done some mistake in conversion.

I don't think you did the conversion correctly.  You don't show your steps so I can't tell where you went wrong, but check your work again.  If the NFA is in state A and it receives a 1, what states might it go to?  If the NFA is in state C and it receives a 1, what states might it go to?  So what state should the DFA (FSA) go to if it is in state AC and receives a 1?

There appear to be multiple errors in the conversion.  For instance, the edge out of AB also looks incorrect.

Try applying the standard algorithm and running it by hand, one step at a time.


Order a list of whole numbers so that no two numbers have the average of them sitting between them Given a whole number N..

Arrange 1 to N in a sequence such that no two numbers have their average sitting between them...

Note -
If N=20.. average of 19 and 2 = 10.5 is not a whole number .. hence we do not need to worry about such numbers and their averages..
In other words, if average of two numbers is not a whole number.. we assume that their average does not exist in the list 1 to N..

Here's a simple recursive construction for the more restrictive version of the problem.  First of all, note that the average of an odd number and an even number is never a whole number; if $a=2i-1$ and $b=2j$, then $\frac12(a+b)=i+j-1+\frac12$.  This means that if we put the $\lceil N/2\rceil$ odd numbers $a_i$ first (in some as-yet-to-be-determined order) and then the $\lfloor N/2\rfloor$ even numbers $b_j$ (likewise, in some as-yet-to-be-determined order), then we can be guaranteed that the average of a $a_i$ and a $b_j$ can never be between them (because it'll never be a whole number), so we've split the problem into two subproblems: one for the set of odd numbers $a_i$ and one for the set of even numbers $b_j$.

But note now that if we have two odd numbers $a_m=2m-1$ and $a_n=2n-1$, then their average is $2\left(\frac{m+n}2\right)-1$, and so the subproblem of 'sorting' the $a_i$ correctly is exactly the same as sorting the numbers $c_i\in 1\ldots n$, where $c_i=\frac{a_i+1}{2}$ and $n=\lceil N/2\rceil$; a similar result holds true for the even numbers $b_j$.  This means that we can keep applying the same procedure to both of these groups recursively.  For instance, when $N=8$ this construction produces the ordering $15372648$.  Note that if we subtract one from these values and look at the numbers $0\ldots(N-1)$, then this ordering is $04261537$; looking at the bit patterns for these numbers ($000, 100, 010, 110, 001, 101, 011, 111$) shows that they're just the bit patterns of the numbers $0\ldots 7$, reversed!  This 'bit reversal' shuffle is used by Fast Fourier Transform (FFT) algorithms to correct the output ordering of their data (see, for instance, http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html ).

In fact, this construction shows that there are at least $O(2^{N/2})$ such orderings, since at each of the $N/2$ 'internal' nodes we can choose to either put the odd or the even numbers first without spoiling the result.  These don't exhaust all of the orderings, though; for instance, we can exchange $2$ and $7$  in the constructed $N=8$ ordering to get the ordering $15327648$ which also clearly satisfies the constraint but can never be constructed by this procedure (since odd and even numbers are 'intermingled').  I don't know how many of the $N!$ orderings of $1\ldots N$ actually satisfy the problem.


Reduce EXACT 3-SET COVER to a Crossword Puzzle I have an assignment where I have to prove that solving a crossword puzzle is an $NP$-complete problem by reducing from EXACT 3-SET COVER. I have more or less given up at this point. If anyone could give me a hint or know where to find the proof, it would be much appreciated.

  Problem: [${\bf CrossWordPuzzleConstruction}$]

  Input: Given are an alphabet $\Sigma$ not containing  the symbols "blank" or "#", a non-empty set of strings $S=\{s_1,\dots,s_m\}$ over $\Sigma$, and an $n\times n$ matrix $A$ for a non-negative integer $n$. The entries in $A$ are either "blank" or "#".

  Output: YES if the blank entries in $A$ can be filled with letters from $\Sigma$ in such a way that the result is a crossword puzzle with strings from $S$. That is, every maximal horizontal or vertical sequence in $A$ consisting of letters from $\Sigma$ is a string from $S$ when read left-to-right respectively downwards. The same string may occur more than once.

We call the problem ${\bf CPC}$ for short.

Example: $\Sigma=\{a,b,c\}$, $S=\{aa,bb,cac,ab,cab,ca,a,ac,bba,aab,bab\}$,

The answer to this input is YES as the following solution shows:

  Problem: [${\bf ExactThreeCover}$]

  Input: The set $X=\{1,2,\dots,n\}$ where $n=3q$, $q\geq1$, and a collection $\mathcal{C}=\{C_1,C_2,\dots,C_m\}$ of subsets of $X$ of sixe $3$. That is, for $i\in\{1,\dots,m\}$, we have $C_i\subseteq X$ and $|C_i|=3$.

  Output: YES if there exists a set $\mathcal{A}\subseteq\mathcal{C}$ such that the elements of $\mathcal{A}$ are a partition of $X$, i.e., $\cup_{C_i\in \mathcal{A}}=X$ and $C_i\cap C_j=\emptyset$ for $C_i,C_j\in\mathcal{A}$ and $i\neq j$.

A reduction from PLANAR 3-SAT with bounded occurrences is more viable.

The upper bound of occurrences should be $3$ for each variables $x_i$ (two positive and one negative OR two negative and one negative).


What happens if the associativity level is greater than the cache size? I am working on a computer organization caching problem
The Problem:  What happens if the associativity level is greater than the cache  size?

I know that associativity level is how many blocks are in a set. Say we have a 16 way set associative cache and a cache size of 15. What would happen? Would the cache break or would it turn into a fully associative cache(1 set)

Since the associativity is equal to the number of cache blocks in a set, in a traditional cache design there is no sensible interpretation of having associativity greater than capacity; a set cannot have more cache blocks than are in the entire cache.

Having more tags than full-sized blocks in a set can make sense.

If the data in a block can be compressed (possibly in a lossy manner), then data from multiple blocks may fit in the storage provided in a single block. In this case having more tags than uncompressed cache blocks allows such compressed data to be cached and indexed normally. For example, with twice as many tags, a 64-byte cache block compressed to 24 bytes and one compressed to 40 bytes could fit into a single 64-byte storage (with some metadata overhead beyond just the extra tag).

Related to compression, extra tags can also be used to facilitate use of large cache blocks with sectors allocated to different tags. For example, each tag could include a full set of valid bits for all subblocks (sectors) in a cache block, reducing the tag overhead (a valid bit is smaller than a tag) at the cost of less effective allocation. This was proposed for off-chip DRAM caches with on-chip SRAM tags (i.e., limited tag storage budget relative to cache capacity).

Extra tags can also be used to reduce back invalidation in a cache that is tag-inclusive of another cache. Tag inclusion allows the inclusive cache to be probed and avoid accessing the included cache unless the data is present there (this is a form of snoop filtering), but a replacement in an inclusive cache that victimizes an entry shared in the included cache forces the block to be removed (back invalidation) from the included cache to maintain the inclusion property.

Extra tags can also be used to improve replacement policy by keeping a record of recent victims. For example, on a tag hit but data miss, the block might be allocated with a "sticky" bit set that would be unset when the block would normally be evicted using the standard (LRU-oriented) replacement policy (this is not the best replacement policy helped by extra tags but it is a clear example).

Similarly, extra tags might be used to improve prefetch accuracy. For example, a proposed prefetch to an address that is a tag hit is more likely to be used than one that is a tag miss.

Extra tags can also be used in decoupling indexing of tags and storage of data. For example, Moinuddin K. Qureshi et al.'s "The V-Way Cache : Demand-Based Associativity via Global Replacement" proposes using twice as many sets as a cache of the capacity and associativity would normally have. This has the benefit of reducing conflict misses under a constant number of tag comparisions because generally some blocks would be allocated to the alternate set that would map to a single set normally (the number of currently used ways in a set can vary). This excess associativity also allows global replacement with full utilization of data storage capacity; if the capacity was equal to the product of associativity and number of sets, then an victimized block (invalidated tag) would mean fewer valid tags than data storage blocks.


If we prove that there is an NP-complete problem that is P, Can we consider that P=NP? I discover this in All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

If problem B is in P and A reduces to B, then problem A is in P.
Problem B is NP-complete if B is in NP and for every problem in A in NP, A reduces to B.
Problem C is NP-complete if C is in NP and for some NP-complete problem B, B reduces to C.

My questions are (if I then II then(?) III/I. If III/I and III/II then IV.)

I: Are there a generalized form to reduces NP problem to either P or NP-complete?
II: Are there a certain number of NP-complete problems?
III/I: Are all of the NP-complete problems can be reduces to all other NP-problems?
III/II: If we can reduce B in NP-complete problem to A in P, can we prove that all problem reduces to B is in P?
IV: If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?

I. I was not able to parse the question, sorry.
II. There is an infinite number of NP-complete problems.
III/I. Each NP-complete problem can be reduced to any other NP-complete problem.
III/II. If you show that there exists a (Karp) reduction from a NP-complete $B$ problem to a problem in P, then you have proved that all problems that reduce to $B$ are also in P. In particular this implies NP $\subseteq$ P, and hence P=NP.
IV. If a NP-complete problem is in P, then P=NP.


Running time complexity of Binary Search Trees and Big-Omega I know that the main operations (Insert, Search, Delete) have a worst-case running time of $\mathcal{O} (h)$. But I wanted to dig into this deeper.

Basically I am having some difficulties understanding "Big-Omega" when it comes to the worst-case time complexity. I usually define them as follows:

Let $t(x)$ be the number of steps taken by an algorithm $\mathcal{A}$ on input $x$.

Let $T(n)$ be the worst-case running time complexity of $\mathcal{A}$.

$T(n) = max(t(x))$ where max is over all inputs x of size n.

Then $T(n) \in \mathcal{O}(g(n))$ if for every input of size $n$, $\mathcal{A}$ takes at most $c \cdot g(n)$ steps.

Moreover,

$T(n) \in \Omega(g(n))$ if for some (there exists) inputs of size $n$, $\mathcal{A}$ takes at least $c \cdot g(n)$ steps.

Returning to BSTs....

We know that for all inputs of size $n$, in the worst case, the height of the tree is $n$, which means we need to visit all $n$ nodes in the worst-case. This is the "ultimate" worst case (forgive my lack of rigour here!), meaning it cannot get any worse, and hence $\mathcal{O}(n)$ running time. But we also know that a tree may be balanced, in which case we could argue that there exists such an input (a balanced tree) such that we would take at least $\Omega(logn)$ for the running time. This is still a "worst case", but a lower bound to that worst case.

I don't feel that is quite right, nor does it make much sense. Perhaps I am just lacking an understanding of how to determine when $T(n) \in \Omega(g(n))$.

any help appreciated!

Big $O$ and big $\Omega$ are not about running times, they are about the rate of growth of functions. If $f(n)$ is the worst-case running time of some operation on inputs of length $n$, then $f(n) = \Omega(g(n))$ means that there exists $C > 0$ such that for some input of length $n$, the running time is at least $Cg(n)$. The fact that we are talking about big $\Omega$ rather than big $O$ doesn't mean that we switch from worst case to best case. On the contrary, we are estimating the very same function, but from below rather than from above.


"Huffman coding is unsuitable for text files"? My lecturer for information theory says that "Huffman coding produces efficient codes but is unsuitable for text files where the letters are represented by a fixed length ASCII code".

I do not understand this statement. I understand that as you change the text file, you'll have to update the probabilities and thus the Huffman table/code itself but I don't think this is what is being referred to here.

Can someone explain?

Thank you so much for all your help

It's not unsuitable, it is just not optimal. That's because letters in human readable text are not independent, but quite strongly correlated. That correlation can be used to get huge savings. For example, the letters q and Q are almost always followed by u. Comma and period are almost always followed by a space character, and period space is almost always followed by an uppercase character. These correlations mean text can be compressed a lot more than by using Huffman coding. But Huffman coding does work and will you get some amount of compression.


What does the R superscript notation mean in regular/formal languages? What does the capital R superscript notation mean in regular languages?  I am working on a homework assignment and don't recall my professor mentioning what the what the R superscript means.  For example in this syntax:

$L = \{ww^R\mid w \in \Sigma^{\ast} \}$

Reverse. So for example $(001)^{R} = 100$. Or to overdo it, for an string $s = s_{1}s_{2}\ldots s_{n}$, the reverse $s^{R}$ is $s_{n}s_{n-1}\ldots s_{2}s_{1}$.


Is there a name for an inverted state machine? I recently needed something like a state machine, but with a slightly different use case.

In general, I would say a state machine knows about a set of states, and different events. Depending on the current state and the event, a state machine is able to decide if this is a valid event for this state, and to which state it should transition to.

What I need is slightly different: Again, I have a state machine knowing some states, transitions and events, but it does tell me which events have to happen to transition to a certain state.
I already implemented such a machine and posted it for code review.

So, while the first machine is able to tell in which state it is after an event, the second machine is able to tell what has to happen to transition to a state.

According to this, my transition table looks different too.
Instead of having new states in the intersection of current states and events, I'm storing the events in the intersection of current and new states.

Is there a name for this kind of inverted state machine, or is it just another implementation of a finite state machine?

If I understand you correctly, you could achieve this using transducers (i.e. automata which also produce outputs when taking a transition).

Suppose we are given a DFA $A = (Q,q_0,\Sigma,\delta)$ describing which events lead to which state transitions. Here $Q$ is the set of states, $q_0$ is the initial state, $\Sigma$ the alphabet of events, and $\delta:Q\times\Sigma\to Q$ the transition function. Then we can define a (nondeterministic) transducer $A'$ as $(Q,q_0,Q,\Sigma,\delta')$ as follows:

$Q$ is the same set of states as before, and $q_0$ is still initial;
The input alphabet is now also $Q$ (representing the target state you are trying to reach);
$\Sigma$ is now the output alphabet;
The transition relation $\delta'$ contains a tuple $(q,\delta(q,a),a,\delta(q,a))$ for each $q\in Q$ and $a\in\Sigma$ (representing the fact that to get from $q$ to $r$, you can use $a$ if $r=\delta(q,a)$).

Note that I'm assuming that you actually want to proceed to the given target state, otherwise you need to adapt the transition relation. Also, if there is no transition from $q$ to $r$, the computation simply fails; you may want to handle this case differently.


Showing bounds of a recurrence I'm working exercises on solving recurrences, just using subsitution, master theorem is after this chapter. I'm sort of stuck on one of the exercises. It states that:

The solution of $T(n) = 2T(\lfloor n/2 \rfloor) + n$ is $O(n \lg n)$. Show that it's also $\Omega(n \lg n)$ and conclude that the solution is $\Theta(n \lg n)$.

For showing that it's $O(n \lg n)$, I've to show that $T(n) \leq cn \lg n$. This can be solved by choosing an $m < n$, like $\lfloor n/2\rfloor$, and substituting.

But if we arrive at the conclusion that $T(n) \leq cn \lg n$ for any appropriate $c > 0$ and $n \geq n_0$, than how can we say that it is also $\Omega(n \lg n)$ which implies that $T(n) \geq cn \lg n$?

Some more clarification would be nice!

First, I would like to modify your statement slightly to remove any chance of confusion. When you say, "... $T(n) \le cn\log n$ for any appropriate $c > 0$ and $n \ge n_0$", it actually means $T(n) \le cn\log n$ for some appropriate $c > 0$ for all $n \ge n_0$.

Next, these constants for proving the lower bound can be (and generally are) different from these when proving the upper bound. I will demonstrate with your example:

Upper bound:
$T(n) = 2T(\frac{n}{2}) + n \le 2(c\cdot\frac{n}{2}\log{\frac{n}{2}}) + n$ (induction hypothesis)
$T(n) \le cn\log n - cn\log 2 + n = cn\log n - (c - 1)n$
$T(n) \le cn\log n$ for all $n$ for any $c \ge 1$
Therefore, $T(n) = O(n\log n)$

Lower bound:
I'll use a different constant $b$ for this, just to emphasize that the two constants are different.
$T(n) = 2T(\frac{n}{2}) + n \ge 2(b\cdot\frac{n}{2}\log{\frac{n}{2}}) + n$ (induction hypothesis)
$T(n) \ge bn\log n - bn\log 2 + n = bn\log n + (1 - b)n$
$T(n) \ge bn\log n$ for all $n$ for $0 \le b \le 1$
Therefore, $T(n) = \Omega(n\log n)$

So basically, you need to choose some constant such that the inequality holds for all sufficiently large $n$. These constants can (and generally are) different for different inequalities.

Note: I have assumed that $n$ is a perfect power of 2 in the above recursions to do away with the floor function. For asymptotic analysis, they do not really matter. These notes may help things become clearer.


Are regular languages closed under inverse homomorphism? Let $\Sigma$ and $\Delta$ be alphabets. Consider a
function $\varphi: \Sigma \rightarrow \Delta^*$. Extend $\varphi$ to
a function from $\Sigma^* \rightarrow \Delta^*$ such that:
\begin{eqnarray*}
\varphi(\varepsilon) & = & \varepsilon \\
\varphi(w\sigma ) & = & \varphi(w)\varphi(\sigma ), \textrm{ for any }
w \in  \Sigma ^*, \sigma  \in  \Sigma
\end{eqnarray*}
Any function $\varphi:\Sigma^* \rightarrow \Delta^*$ defined in this way
from a function $\varphi: \Sigma \rightarrow \Delta^*$ is called a
homomorphism. We can extend this definition to languages as follows:
for any language $L$ and homomorphism $\varphi$, let
$$\varphi(L)=\{\varphi(w) : w\in L\}.$$

Are regular languages are closed under inverse homomorphism?

Yes, regular languages are closed under inverse homomorphism.

Here is a proof.
We start with a DFA of $L$, $X$. To prove that $\varphi^{-1}(L)$  is regular, we will construct a DFA, $Y$ for $\varphi^{-1}(L)$.

$$ X = (Q,\Sigma,\delta_X,q_0,F)$$

So our construction will be as follows:

$$ Y = (Q,\Delta,\delta_Y,q_0,F)$$

Where:

$$\delta_Y(q,w) = \hat{\delta_X}(q,\varphi(w))$$

Or in other words, the transition in Y on w is the result of the sequences of transition that X makes on the string of symbols $\varphi(w)$. So all we need to do now is prove this transition. To do this we will induct on $|w|$. Our hypothesis being $\hat{\delta_Y}(q,w) = \hat{\delta_X}(q,\varphi(w))$.

Base: When $w = \epsilon$:

$$q_0 = \delta_Y(q_0,\epsilon) = \delta_X(q_0,\varphi(\epsilon)) = \delta_X(q_0,\epsilon) = q_0$$

Inductive Step: First let $w = \sigma s$:

$$\hat{\delta_Y}(q_0,w) = \hat{\delta_Y}(\delta_Y(q_0,\sigma),s)$$

Then by our inductive hypothesis:

$$\hat{\delta_Y}(\delta_Y(q_0,\sigma),s) = \hat{\delta_Y}(\delta_X(q_0,\varphi(\sigma)),s)$$

Now by our DFA definition above:

$$\hat{\delta_Y}(\delta_X(q_0,\varphi(\sigma)),s) = \hat{\delta_X}(\delta_X(q_0,\varphi(\sigma)),\varphi(s))$$

Pulling the $\delta$ back in:

$$\hat{\delta_X}(\delta_X(q_0,\varphi(\sigma)),\varphi(s)) = \hat{\delta_X}(q_0,\varphi(\sigma)\varphi(s))$$

Now by the definition of homomorphism:

$$\hat{\delta_X}(q_0,\varphi(\sigma)\varphi(s)) = \hat{\delta_X}(q_0,\varphi(\sigma s)) = \hat{\delta_X}(q_0,\varphi(w))$$


Efficient Algorithm to determine highly composited numbers Im writing an algorithm to determine highly composited numbers.
But it's very unefficient with $\Omega(f(n)) = n³$.
Does someone know how i can make my code more efficient. Is my approach ok?

Here is my code:

import tools.Tools;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.TreeMap;

public class HighCompositeNumbers {

ArrayList<Long> hcnList = new ArrayList<>();

public HighCompositeNumbers(){
    hcnList.add(1L);
}

public TreeMap<Long, Long> primeFac(long n){
    final long limit = n;
    TreeMap<Long, Long> map = new TreeMap<>();
    for (long i=2; i<=limit/2+1; i+=1){
        long counter = 0;
        if (n % i == 0) map.put(i, 0L);
        while (n % i == 0) {
            n /= i;
            counter++;
        }
        if (counter != 0) map.put(i, counter);
    }
    return map;
}

public long numberOfDivisors(long n){
    TreeMap<Long, Long> map = primeFac(n);
    long divisors = 1;
    for (Long l : map.values()){
        divisors *= (l + 1);
    }
    return divisors;
}

public boolean isHighlyComposite(long n){
    long numOfDiv = numberOfDivisors(n);
    for (long i = n-1; i>=hcnList.get(hcnList.size()-1); i--){
        if (numberOfDivisors(i) >= numOfDiv) return false;
    }
    return true;
}

public static void main(String[] args) {
    long max = Tools.nextLong("max: ");
    HighCompositeNumbers hcn = new HighCompositeNumbers();
    //Tools.printHashMap(hcn.primeFac(max));

    for (long i=2L; i<= max; i++){
        if (hcn.isHighlyComposite(i)) hcn.hcnList.add(i);
    }

    System.out.println(hcn.hcnList);

}
}

As in many cases, read the problem carefully first. The problem asks for all numbers that have more divisors than any small numbers. Nobody asks you to determine the number of divisors of lots of numbers.

First write down the formula how to calculate the number of divisors of n, given its factorisation into prime numbers. Then figure out rules that say what kinds of prime factors a highly composite number might have. Quite obviously a highly composite number must be a product $2^a·3^b·5^c·7^d...$ where a ≥ b ≥ c ≥ d and so on. That's because if for example a < b, then $2^b·3^a$ would be smaller than $2^a·3^b$ but have the same number of prime factors.

That's just the start of it, but this should already help you to find highly composite numbers up to n a lot, lot faster than O (n).


How can primitive recursion be a special case of minimization? In several posts on StackExchange and elsewhere, I have seen claims that you only need to show you can construct constants, successor, projection, composition, and minimization to prove a language Turing-complete, since primitive recursion is allegedly a special case of minimization. But as I have been thinking about it, I don't see how minimization can be used effectively at all without primitive recursion.

Minimization searches for zero
The only way to get zero without primitive recursion is a constant zero
So any application of minimization must either:
Return a constant zero all the time (since there is no way to do conditionals either w/o p.r.), or
Return the input unmodified, since any number of successors other than zero would never return zero

So if every minimization must either return constant zero or zero only when the input is zero, how can you construct any function more powerful than this? Or is this a false assumption?

Your suspicion is correct. Without primitive recursion we get a very small class of functions, namely maps of the form $f(\vec{x}) = x_i + m$, possibly with some undefined values.
Let $\mathcal{F}_k$ be the least class of partial maps $f : \mathbb{N}^k \to \mathbb{N}$ closed under $0$, successor, projections, composition and minimization.

Theorem: For every $f \in \mathcal{F}_k$ there exist $i$ and $m$ such that, for all $\vec{x} = (x_1, \ldots, x_k) \in \mathbb{N}^k$, either $f(\vec{x})$ is undefined or $f(\vec{x}) = x_i + m$.

Proof. We proceed by induction on the structure of $f$. It is obvious that $0$, successor, projections, and compositions preserve the stated property. Now consider $f \in \mathcal{F}_k$ which is defined by minimization of $g \in \mathcal{F}_{k+1}$, so that
$$f(\vec{y}) = \min \{x \in \mathbb{N} \mid g(x, \vec{y}) = 0\}.$$
By induction hypothesis there are two possibilities:

There exists $m$ such that $g(x, \vec{y}) = x + m$ whenever $g(x, \vec{y})$ is defined. In this case:

If $m = 0$ then $f(\vec{y}) = 0$
If $m > 0$ then $f$ is everywhere undefined

There exists $m$ and $i$ such that $g(x, \vec{y}) = y_i + m$ whenever $g(x, \vec{y})$ is defined. In this case:

if $m = 0$ then $$f(\vec{y}) = \begin{cases}0 & \text{if $y_i = 0$ and $g(0, \vec{y})$ is defined}\\ \text{undefined} & \text{otherwise} \end{cases}$$
if $m > 0$ then $f(\vec{y})$ is everywhere undefined.

In all cases minimization preserves the stated property. $\Box$
Let us also try to speculate how the falacy "primitive recursion is a special case of minimization" arises. Suppose $f : \mathbb{N} \to \mathbb{N}$ is defined by primitive recursion by
\begin{align*}
f(0) &= k\\
f(n+1) &= h(n, f(n)),
\end{align*}
where $h : \mathbb{N}^2 \to \mathbb{N}$ is primitive recursive. Then there is a primitive recursive function $g : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ such that
$$
g(x, y) = \begin{cases}
0 & \text{if $f(x) = y$},\\
1 & \text{otherwise.}
\end{cases}
$$
The map $g$ involves a good deal of arithmetic, encoding of lists as numbers, etc. Cruicially, $g$ may be more complicated than $f$ and $h$.
Therefore, we could define $f$ by minimization as
$$f(x) = \min \{y \mid g(x,y) = 0\}.$$
However, we need the entire primitive recursion machinery to get the suitable $g$, so we cannot infer from this that primitive recursion can be dispensed with in the presence of minimization.


Is this grammar LALR(1) I am working through creating a LALR(1) parser generator. I have the following grammar which I designed to highlight the epsilon for rule 3.

0. S' -> A
1. A -> a B b
2. B -> b
3. B ->

This recognizes ab and aab. It is my assumption that with one symbol of look-ahead, I would know whether to reduce using rule 3 or shift using rule 2. That is, when scanning ab, I need to reduce using rule 3 to get a B onto my stack. But when the input is abb I want to just shift the first b, then reduce it by rule 2.

As I work through creating a LALR(1) parsing table, I get the following:

 , $ , a , b , A , B
0,   , s2,   , g1,   ,
1, a ,   ,   ,   ,   ,
2,   ,   , s5,   , g3,
3,   ,   , s4,   ,   ,
4, r1,   ,   ,   ,   ,
5,   ,   , r2,   ,   ,

The issue is that there is an ambiguity on state [2, b]  A 'reduce by 3' was rejected. Of course, this is why I chose the grammar.

I calculated first and follow as:

**************
* First sets *
**************
A { a } epsilon=false
B { b } epsilon=true
S' { a } epsilon=false

***************
* Follow sets *
***************
S' { $ }
    A { $ }
B { b }

Anyway, I have implemented this as best I know how and the ambiguity remains. Am I doing something wrong? Am I expecting too much from LALR(1)?

EDIT - one possible place where I am confused could be when 'lookahead' occurs. If the lookahead symbol is only used to make a decision on whether a reduction should occur, then to be successful we require enough information after we shift the first a. Basically, if we see two b's coming, we can infer our only chance of success is to shift the first one and then reduce it to B. If there is only one B, we'll need to reduce the epsilon to get a B onto the stack.  Then we'll be set up to successfully reduce aBb. By this metric, this would be an LALR(2) grammar. Does this make sense (in the scope of LALR(k) parsers,) or am I just wrong?

A simpler way to see that this grammar is not LALR(1) is to look at the LR(1) item sets:

$S' \rightarrow \bullet A,\enspace \$$
$A \rightarrow \bullet aBb,\enspace \$$
$S' \rightarrow A\bullet ,\enspace \$$
$A \rightarrow a\bullet Bb,\enspace \$$
$B \rightarrow \bullet b,\enspace b$
$B \rightarrow \bullet ,\enspace b$
$A \rightarrow aB\bullet b,\enspace \$$
$B \rightarrow b\bullet ,\enspace b$
$A \rightarrow aBb\bullet ,\enspace \$$

You can see that in state 3 the shift/reduce conflict remains, even in LR(1). This grammar is not LR(1), and thus not LALR(1).


Practical Implementation for Refinement Order on Integer Partitions The refinement order on partitions of an integer $n$ can be defined as follows: $\lambda=(\lambda_1,\dots,\lambda_k)\leq\mu=(\mu_1,\dots,\mu_\ell)$ if there is a partition of the parts of $\lambda$ into blocks whose sums are the parts of $\mu$.

It is known that the problem of deciding whether $\lambda\leq\mu$ is NP-complete.  However, for a practical application I would need an algorithm which performs reasonably when $n$ is around $200$.  Ideally, this algorithm would already have a (free) implementation...

I tried the following naive approach:

find the last index $j$ such that $\mu_j>\lambda_1$
if $\mu_{j+1} = \lambda_1$ remove $\mu_{j+1}$ from $\mu$ and $\lambda_1$ from $\lambda$ and recurse
otherwise, for $j\in\{j,j-1,\dots,1\}$:

subtract $\lambda_1$ from $\mu_j$ and reorder to obtain a new partition, and recurse with this partition and the rest of $\lambda$

Although this seems to work reasonably well for many pairs $(\lambda,\mu)$ of partitions of size around $200$, it performs poorly when $\lambda$ has many small parts but is not a refinement of $\mu$.

I suggest you try using integer linear programming.  Introduce $k\ell$ zero-or-one variables $x_{i,j}$, with the constraints

$$\sum_j x_{i,j} \lambda_j = \mu_i$$

and

$$\sum_i x_{i,j} = 1.$$

Feed it to an off-the-shelf ILP solver.  If it can find a feasible solution for you, then you know that $\lambda \le \mu$.  If it can determine that no solution exists, then you know that $\lambda \not\le \mu$.


What's the big deal with the knapsack problem? In my CS course, we are covering things from one topic to another in sort of a sensible manner. For example, binary search tree -> 234-tree -> red-black tree -> heap -> greedy algorithms -> dynamic programming.

And all the sudden, bam, there is this whole chapter on the knapsack problem. How is this problem different from weighted interval scheduling? Or longest common sub-sequence?

What's the importance of the knapsack problem?

I think mainly the techniques that are covered in that section (dynamic programming and greedy algorithms) are very important.

There are several other properties. First of all, integral knapsack problem belongs to the famous class of problems called NP-complete (there is no known polynomial time algorithm for them), while the fractional knapsack is polynomial time solvable using a greedy algorithm. Thus, as an algorithm designer, you need to be able to recognize the difference between the nature of these two problems in order to solve them.

Also, one interesting point is that, although the dynamic programming technique is psuedo-polynomial time for the integral knapsack problem, it can be run exponentially in general case.