Language is recursive, hence recursively enumerable I was going through a book of proof and I read:

  If L is recursive, L is r.e.

And the proof goes:

Let L be recursive, hence there is a TM that decides it
Convert an halt state to a normal state
Add to program that when it enters this state it goes to infinite loop

How can this be a proof for it?

Depending on what definitions you use, the proof can be trivial.  We can all agree that a set $S$ is recursive if there is a Turing machine that halts on every input, accepts the members of $S$ and rejects the non-members of $S$. Such a Turing machine is called a decider of the set.

One definition of the recursively enumerable sets is that $S$ is RE if there is a Turing machine that accepts every member of $S$ and does not accept any non-member.  That is, if $x\notin S$, the machine either rejects it or loops forever.  By this definition, it is trivial that every recursive language is RE: the machine that decides the language has the property that it accepts everything in the set and nothing outside it.

The other definition is that a set $S$ is RE if there is a Turing machine that accepts every member of the set and loops forever for every non-member.  This appears to be the definition your book is using.  Now, suppose you have a machine that decides a set $S$.  Modify it so that, instead of rejecting non-members of the set, it loops forever.  This gives a machine that accepts every member of $S$ and loops forever for every non-member.  This is exactly what you need to conclude that $S$ is RE.

The same idea proves that the two definitions of RE are the same.  Any machine that obeys the second definition also obeys the first one (the first says it can either loop or reject for non-members: it happens to loop for all of them but that's a valid choice).  Any machine that obeys the first definition can be converted to obey the second by the same trick: replace rejection with looping.


What is a safe programming language? Safe programming languages (PL) are gaining popularity. I wonder what is the formal definition of safe PL. For example, C is not safe, but Java is safe. I suspect that the property “safe” should be applied to a PL implementation rather than to the PL itself. If so, let’s discuss a definition of safe PL implementation. My own attempts to formalize this notion led to a strange outcome, so I would like to hear other opinions. Please, do not say that every PL has unsafe commands. We can always take a safe subset.

There is no formal definition of "safe programming language"; it's an informal notion.  Rather, languages that claim to provide safety usually provide a precise formal statement of what kind of safety is being claimed/guaranteed/provided.  For instance, the language might provide type safety, memory safety, or some other similar guarantee.


Is the empty string ε in regular languages implicitly between any two characters in a string? I'm wondering if this visualization makes sense with the definition of the empty string ε. I suppose it does because it doesn't seem to contradict its definition (ε is a string with no characters).

If that's the case, in finite state machines with empty transitions, is it always possible to assume ε is "before" the character a that should be read next, and take the empty transition instead?

If the next state also has an empty transition to another state, can I assume ε is "before" a again, even though the automata had just "consumed" ε in the last operation? In other words, can I assume there is an indefinite number of empty strings between any two characters in a string in a regular language?

The empty string is not there between every two characters implicitly but quite explicitly. In fact, there are two empty strings between any two characters, and between those two empty strings there is another, third, empty string. However, since empty strings are empty, them being there is like them not being there at all.

Let's consider this situation from a slightly more general point of view, but without using fancy words. In a sum $1 + 2$ is there a zero in between? Yes, since obviously $1 + 0 + 2 = 1 + 2$, and in fact also $0 + 0 + 1 + 0 + 0 + 0 + 2 + 0 = 1 + 2$, so that's a whole lot of zeroes. Is this sort of thinking useful? Well, in certain situations it is, for instance when we perform algebraic manipulations of numbers.

It might help to write strings as finite lists, i.e., instead of aabab we write $[a, a, b, a, b]$. With this notation the empty string is just $[]$, which is probably less confusing than the Greek letter $\varepsilon$. Concatenation then is actually concatenation (link together in a chain or series, according to my dictionary):
$$[a, a, b][b, a] = [a, a, b, b, a].$$
And now, it makes perfect sense to say that there are empty strings everywhere, like ghosts:
$$[a, a, b][][b, a] = [a, a, b, b, a] = [a, a, b][b, a].$$
Finite automata with silent transitions do not "consume $\varepsilon$". A silent transition happens when no symbol is consumed. You might think that "to consume no symbol" is the same as "to consume the empty string" but that is not so! An automaton (at least of the ordinary kind) consumes one symbol when it makes a transition, or it does not consume anything at all. An empty string is not a symbol, and therefore it cannot be consumed during the transition of an automaton.

More formally, the transition function $\delta$ has the type $S \times \Sigma \to \Sigma$, where $S$ is the set of states and $\Sigma$ is the alphabet. The empty string has type $\Sigma^*$ and so it cannot be an argument to $\delta$. The types don't fit.


Reviews of work in the field of partial evaluation (post 1993) I'm looking for relatively new reviews of research work on partial evaluation. The most recent work I've found is "Tutorial notes on partial evaluation" by Charles Consel and Olivier Danvy (1993). The book Partial Evaluation and Automatic Program Generation (1993) also gives a comprehensive overview of the work in this field.

In particular, I want to write a brief overview of the history of this field of research. And with the sources I've found so far, I only have enough to write about it up to the early 90s.

Terminology: In the literature, other more-or-less interchangeable terms are sometimes used instead of "partial evaluation". Like "mixed computation" (introduced by A.P. Ershov) and, as Respawned Fluff has mentioned, "program specialization". "Partial deduction" seems to be used in the context of partial evaluation applied to logic programming.

The PEPM (Partial Evaluation and Program Manipulation) Symposium Series is still running. That'd be a good place to start to see what the current hot topics are and who is still working on Partial Evaluation.


Determining if (infinite) binary language DFAs contain at least 1 prime? This problem has been given by Shallit as an open DFA/ complexity theory problem and is currently not even known to be decidable. It seems to be circulating on the internet in a few places (e.g. [1][2]) but not in any papers. Almost nothing seems to be known or published. I am looking for any nontrivial analysis or references.

  Given: binary DFA D. Does L(D) contain at least 1 prime?

(Binary means Σ = {0, 1}.) As an example of something nontrivial about it (a subproblem), what can be said of the base-2 DFA language representations, what is their general form? Or, given any d, does there exist a DFA (language) that contains only multiples of d in binary? Are there arithmetic progressions embedded in DFA binary languages? Note there are many number theoretic investigations into primes in arithmetic sequences/ progressions and recent findings/ research, could any be demonstrated to be applicable?

[1] a simple problem whose decidability is not known / cstheory.SE

[2] are there any open problems left about DFAs? / cstheory.SE

It's a standard intro theory exercise that for any $d\ge 0$ there's a FA that accepts all and only those strings in $\{0, 1\}^*$ that are the binary representations of integer multiples of $d$. Thus, the answer to your second question is "yes".

For your third question, the answer is "no". Consider the regular language denoted by $1(10)^*0$. This language consists of those binary representations of
$$
\frac{10\cdot 4^n-4}{3}
$$
and clearly this sequence is too sparse to contain an arithmetic subsequence of any length greater than 2.


What is the significance of context-sensitive (Type 1) languages? Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a single stack (i.e. a push-down automaton) and Type 0 by a state machine with two stacks (or, equivalently, a tape, as is the case for Turing Machines), how do Type 1 languages fit into this picture? And what advantages does it bring to determine that a language is not only Type 0 but Type 1?

The context-sensitive languages are exactly the languages that can be recognized by a Turing machine using linear space and non-determinism. You can simulate such a Turing machine using exponential time, so you can recognize any such language in exponential time. Do note that the problem of recognizing some context-sensitive languages is $PSPACE$-complete, which means we're pretty sure you can't do better than exponential time.

Comparing this to type 0 languages, this means you can at least say something about how long it takes to recognize the language. A type 0 language may not even be decidable: the language of all Turing machines that halt is a type 0 language, but as recognizing this language is exactly the halting problem, it is not decidable.

Context-sensitive grammars are not very useful in practice. Context-free grammars are intuitive to work with, but as the examples on Wikipedia show, context-sensitive grammars very quickly become rather messy. Programs using polynomial space are much more easily designed (and the $PSPACE$-completeness guarantees the existence of some equivalent CSG that is only polynomially larger than the space usage of your algorithm).

The reason for their existence is that they form a very natural extension of context-free grammars (you allow context to determine which productions are valid). This will probably have inspired Chomsky to define them and name them the type 1 languages. Remember that this definition was made before computers became as fast as they are today: it's more of interest to formal language theorists than for programmers.

Unrestricted grammars get even weirder: there's no longer a notion of 'expanding' a nonterminal and replacing it with a production, possibly depending on context. You're allowed to freely modify the context as well. This makes unrestricted grammars even less intuitive to work with: programs are equivalent and a lot more intuitive.


How to Add IEEE 754 Floating Point Numbers I'm trying to add two 16 bit numbers that use a similar format as IEEE 754. The format is in the image below:

I can't figure out how to add together two numbers for the life of me.

Specifically, 0x82A3 + 0x0B98. In my attempt to solve this, I got 0x0B98 as the final sum, but that doesn't seem right to me.

It is difficult, and there are lots of special cases to handle.

Step 1: Determine if any of the operands is an Infinity or a Not-A-Number. In this case, look up the IEEE 754 standard and determine the result accordingly.

Step 2: Extract the sign, the biased exponent, and the mantissa. Add any implicit leading bit to the mantissa. Check whatever special rules there are: In the IEEE 754 32 and 64 bit format, a biased exponent of 0 means that there is no implicit leading bit in the mantissa, but the exponent should be treated as if it was 1. Add three extra bits containing zeroes to the mantissa.

Step 3: Make sure the exponents are the same. If one number has an exponent that is smaller by k, then shift that numbers mantissa to the right by k bit positions. If k is greater than 3, then set the last bit of the mantissa to 1 if any non-zero bits were shifted out. If k is so large that all mantissa bits would be shifted out then set the mantissa to zero, and don't try to shift by some huge amount.

Step 4: If the operands have different signs and the second mantissa is larger then exchange the operands. Add or subtract the mantissas, depending on the sign bits.

Step 5: If you added the mantissas and there was a carry, then increase the exponent, and shift the mantissa one bit position to the right. If the bit that is shifted out is non-zero, then set the last bit of the mantissa.

Step 6: If you subtracted the mantissas then count the number of leading zero bits in the mantissa. If all mantissa bits are zero then set the biased exponent to 1. Otherwise, shift the mantissa to the left and decrease the exponent, making sure that the biased exponent doesn't get smaller than 1.

Step 7: Perform rounding according to IEEE 754 rules. That's where the three extra mantissa bits are used. Remove the extra 3 mantissa bits. Due to the "round to even" rule, you round up (increase the mantissa by 1) if the last bit is 0 and the bits removed are 101 or larger, or the last bit is 1 and the bits removed are 100 or larger.

Step 8: If you rounded up and there is a carry then shift the mantissa one bit to the right and increase the exponent. If the biased exponent is too large then the result is infinity. If the biased exponent is 1 and the highest mantissa bit is zero then the biased exponent is changed to 0.

Step 9: Drop the highest bit of the mantissa, and pack sign, biased exponent, and mantissa together.


Choosing spanning trees to maximise node connectivity Given: n variables in X, and m sets of variables where each set, Ci contains a subset of X. I am trying to generate the graph G = (X, E) by picking the edges in E given the following constraints.

Variables in each set Ci must be connected by a spanning tree (no extra edges).
The graph should prefer spanning tree configurations so that the variance of the degrees of all nodes is maximised.
Following the previous constraint, prefer spanning tree configurations such that the degrees of nodes have greater variance, rather than average all around. So given the choice between  configurations resulting in nodes of degree 1, 2, 3 vs 2, 2, 2. Prefer 1, 2, 3.

X = {x1, x2, x3, x4, x5, x6}

C1 = {x1, x2, x3}

C2 = {x2, x4}

C3 = {x4, x5}

C4 = {x3, x5, x6}

The optimal solution for the given variables is:

Each subset of variables Ci is connected by a spanning tree, and the degree of x3 is maximised. x3 has a maximised degree, and there are nodes with degrees of 1 (preferred).

There are a few things I am having trouble with.

Actually defining the problem: this graph is a constraint graph which is to be processed under some tree decomposition or cycle cutset algorithm. Variables in each set Ci share a common attribute. I am trying to remove redundant constraints so that I can get a favourable tree structure, under some ordering, for the next stage. I'm wondering if this preprocessing step is a known problem.
Efficiently implementing this preprocessing step. I am thinking that it may be able to be reformulated as trying to minimise the average all pairs shortest paths, and then if there is a tie, pick the one with the greatest variance. And if this is the case, whether there is an efficient algorithm to do this.

EDIT: A simpler example without cycles.

X = {x1, x2, x3, x4}

C1 = {x1, x2}

C2 = {x2, x3, x4}

There is a spanning tree between, x1 and x2 for C1.

This image shows the graph if I chose all the edges instead of just the spanning tree. It is undesirable as I am trying to minimise the edges, and there is an avoidable cycle.

If I didn't create the x2 to x3 edge, the graph would have the minimal edges satisfied, but not optimal as x2 has a degree of 2. When choosing to not create the  x3 to x4 edge, x2 has a degree of 3.

If I summed the degrees in both cases they are 6. But the second case has a greater variance in the degrees (which is preferred). This is where the concept of dependency comes in, if x2 is removed in the second case, all other nodes are disconnected. In the first case, there would still be an edge between x3 to x4.

My suggestion would be to try simulated annealing.  This looks like a good candidate for that heuristic.  It sounds like you have some idea what the objective function you want to minimize is (that's good; you need one).

I would suggest that you use simulated annealing as follows:

A state is a possible graph (a set of edges).
The cost function for a state might be your objective function plus some penalty for the number of $C_i$'s that aren't fully connected.
To transition between states, you might randomly choose among the following options:

Add an edge chosen at random (or: choose a $C_i$ that isn't fully connected, and add a randomly chosen edge between some pair of variables $C_i$ that aren't currently in the same connected component)
Delete an edge chosen at random
Pick an existing edge $(u,v)$, delete the edge, then randomly choose some other variable $w$ that is in the same connected component as $v$ and add the edge $(u,w)$.

but of course you can play around with it and try different variations to see which works the best.  This might just give you some reasonable solutions.

You could also try formulating this as a SAT or ILP instance, but my sense is that I would try simulated annealing first.  If you're lucky, it just might work well enough that you don't need to bother with anything else.


Confluence proof for a simple rewriting system Assume we have a simple language that consists of the terms:

$\mathtt{true}$
$\mathtt{false}$
if $t_1,t_2,t_3$ are terms then so is $\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$

Now assume the following logical evaluation rules:

$$ \begin{gather*}
\dfrac{}
      {\mathtt{if}\: \mathtt{true} \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 \to t_2}
      \text{[E-IfTrue]} \quad
\dfrac{}
      {\mathtt{if}\: \mathtt{false} \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 \to t_3}
      \text{[E-IfFalse]} \\
\dfrac{t_1 \to t_1'}
      {\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 \to \mathtt{if}\: t_1' \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3}
      \text{[E-If]} \\
\end{gather*} $$

Suppose we also add the following funky rule:

$$
\dfrac{t_2 \to t_2'}
      {\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 \to \mathtt{if}\: t_1 \:\mathtt{then}\: t_2' \:\mathtt{else}\: t_3}
      \text{[E-IfFunny]}
$$

For this simple language with the given evaluation rules I wish to prove the following:

Theorem: If $r \rightarrow s$ and $r \rightarrow t$ then there is some term $u$ such that $s \rightarrow u$ and $t \rightarrow u$.

I am proving this by induction on the structure of $r$. Here is my proof so far, it all worked out well, but I am stuck at the very last case. It seems like induction on the structure of $r$ is not sufficing, can anyone help me out?

Proof. By induction on $r$, we will seperate all the forms that $r$ can take:

$r$ is a constante, nothing to prove since a normal form does not evaluate to anything.
$r=$ if true then $r_2$ else $r_3$. (a) both derivations were done with the E-IfTrue rule. In this case $s=t$, so there is nothing to prove. (b) one deriviation was done with the E-IfTrue rule, the other with the E-Funny rule. Assume $r \rightarrow s$ was done with E-IfTrue, the other case is equivalently proven. We now know that $s = r_2$. We also know that $t =$ if true then $r'_2$ else $r_3$ and that there exists some deriviation $r_2 \rightarrow r'_2$ (the premise). If we now choose $u = r'_2$, we conclude the case.
$r=$ if false then $r_2$ else $r_3$. Equivalently proven as above.
$r=$ if $r_1$ then $r_2$ else $r_3$ with $r_1 \neq $ true or false. (a) both deriviations were done with the E-If rule. We now know that $s =$ if $r'_1$ then $r_2$ else $r_3$ and $t =$ if $r''_1$ then $r_2$ else $r_3$. We also know that there exists deriviations $r_1 \rightarrow r'_1$ and $r_1 \rightarrow r''_1$ (the premises). We can now use the induction hypothese to say that there exists some term $r'''_1$ such that $r'_1 \rightarrow r'''_1$ and $r''_1 \rightarrow r'''_1$. We now conclude the case by saying $u =$ if $r'''_1$ then $r_2$ else $r_3$ and noticing that  $s \rightarrow u$ and $t \rightarrow u$ by the E-If rule. (b) one derivation was done by the E-If rule and one by the E-Funny rule.

This latter case, where one derivation was done by E-If and one by E-Funny is the case I am missing... I can't seem to be able to use the hypotheses.

Help will be much appreciated.

Okay, so let's consider the case that $r = \mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$, $s$ has been derived by applying the E-If rule and $t$ has been derived by applying the E-Funny rule: So $s = \mathtt{if}\: t'_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$ where $t_1 \rightarrow t'_1$ and $t = \mathtt{if}\: t_1 \:\mathtt{then}\: t'_2 \:\mathtt{else}\: t_3$ where $t_2 \rightarrow t'_2$.

The $u$ we're looking for is $u = \mathtt{if}\: t'_1 \:\mathtt{then}\: t'_2 \:\mathtt{else}\: t_3$. $s \rightarrow u$ follows from rule E-Funny and $t \rightarrow u$ follows from rule E-If.


Why is the start symbol "not allowed" on the right hand side in Chomsky normal form? I had a question regarding CNF (Chomsky normal form) in formal language theory.

I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow the start symbol to be on the right hand side of the production. However, I just can't wrap my head around why this is so.

In these cases, they put as the first step of converting a general context-free grammar into CNF to add the production

$$S_0 \rightarrow S$$

but I noticed that in some cases this actually leads to having one more unnecessary production, and in other cases it's impossible to completely remove the start symbol completely from the right hand side of productions (excluding the $S_0 \rightarrow S$ production). Also, the textbook that I'm using (Formal Languages and Automata, 6e - Peter Linz) allows the start symbol to be on the right side of a production.

What's the reason that this production is frowned upon?

Thank you.

Recall that in Chomsky normal form, we are allowed productions of three forms:

Productions of the form $A \to a$.
Productions of the form $A \to BC$.
The production $S \to \epsilon$.

We have to allow the production $S \to \epsilon$, since otherwise it will be impossible to generate the empty string.

Suppose for a moment that the production $S \to \epsilon$ is absent. Then we have the following very useful property:

  If $A \Rightarrow^* w$ then $w \neq \epsilon$.

This comes up in some proofs of the pumping lemma, for example.

If we have the rule $S \to \epsilon$, then we no longer have the property above. However, a similar property holds:

  If $A \Rightarrow^* w$ and $A \neq S$ then $w \neq \epsilon$.

This is due to our insistence of not having $S$ on the right-hand side of productions; otherwise we might have rules like $A \to SS$ and then derivations like $A \Rightarrow SS \Rightarrow^* \epsilon$.

If the rule $S \to \epsilon$ is absent, then there is no reason to disallow $S$ on the right-hand side of productions. Indeed, some authors allow $S$ on the right-hand side of productions as long as the production $S \to \epsilon$ is absent.


Exponential nested Loop Big O complexity calculation Can I get a bit of help over here, I can't seem to get to a finish point with this code complexity. I have trouble with making notations, exponential ones in particular..... I spent hours with this particular piece of code to get BIG O but i can't mathematically..... I'm a newbie.

I tried to logarithmate the whole thing like:
j= n, n^(1/2), n^(1/4), ........, 2
then:

j= log (2,n), log(2, n^(1/2)), ..... log (2, (n^(1/2))^K) need to find out K from this notation

If i try to sum them up: log(2,n) + 1/2*log(2,n) + 1/4*log(2,n) + ..... + (1/2)^K * log(2,n)

then:

log(2,n) * [1/2 + 1/4 + ....... + (1/2)^K]
The number of terms this sum has should give me the number of steps for j
I can't proceed to i without it but i get stuck right there at that sum at this point and i get lost from here.....

I also made a piece of code to count the steps and have a better view here are the results for

n = 1000

for j: 1000   i: 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1,   steps: 10

for j: 31   i: 31, 15, 7, 3, 1,   steps: 5

for j: 5   i: 5, 2, 1,   steps: 3

for j: 2   i: 2, 1,   steps: 2

n = 65

for j: 65   i: 65, 32, 16, 8, 4, 2, 1,   steps: 7

for j: 8   i: 8, 4, 2, 1,   steps: 4

for j: 2   i: 2, 1,   steps: 2

for (int j=n; j>1; j=sqrt(j))
       for (int i=j; i>0; i/=2)
             k++; // O(1)

Let n = 65,536 and write down what exactly happens. That should be enough to figure it out.


Comparing A* search to Simulated Annealing Good Afternoon,

I am comparing A* search to Simulated Annealing for an assignment, mainly the algorithms, memory complexity, choice of next actions, and optimality. Now, I am not 100% sure about my answer, and was wondering if someone could give me some input.

A*: Optimal, finds path of shortest distance to goal state based on heuristic.

SA: Complete, stochastic, randomly selects next state and either rejects/accepts based on change in energy state. If it is a bad move (less energy than previous state) then it either accepts/rejects based on probability.

Now, I understand that A* requires bookkeeping in order to track the path from goal state to start state. This is why I think that the memory requirements would be linear, where there are n nodes in the path from start to finish.

On the other hand SA doesn't require bookkeeping, since it's trying to find the state with the maximum "energy". Could someone explain exactly what "energy" would mean? Also, I am confused about comparing the functions of these two algorithms. A* is good at finding the path to a goal state (which is already known) with the lowest cost, whereas SA only finds a state that is most desirable. what is the point of comparing A* to SA when they seem to have two different purposes?

"Energy" is just the output of your cost function that you define for the SA problem. You are right that the two algorithms seem to have two different purposes, and in most cases, I would say that is true. However, you could pose a pathfinding problem as a simulated annealing problem, depending on how you define your cost (energy) function.

Let's say you have a cost function that equals the total cost to get from point A to point B. Your SA algorithm would try to find the minimum in this cost function, but imagine how difficult that may be. Your cost surface could potentially by many-dimensional. Plus, there is no guarantee that your cost surface is smooth, so finding that minimum on this enormous cost surface may be computationally intractable.

I think you've stated well many of the differences, but the next step is to try to understand the benefits/drawbacks of each algorithm solving the problem they are best suited for.


Rice Theorem - Problem to understand and apply it I have struggle to understand the Rice Theorem.

My understanding of Rice Theorem:

The purpose of this Theorem is to proof that some given language L is undecidable iff the language has a non-trivial propertie.

So, if I want to apply this Theorem I have to show that the following conditions are satisfied:

1) There are two TM's which have the same language and they are either both in the language $L(M_1)=L(M_2)$ or neither is in L ($M_1 \wedge M_2$ are no specific (picked) machines).

2) I have to show that there exists two specific TM's: $M_1'$ which has the property and $M_2'$ which doesn't have the property.

Is this correct?

Perhaps someone can give an example, so that I know how to apply the rice theorem.

What's about the language: $L=${$<M>$|$\emptyset$ $\subseteq$ $L(M)$}

For the first condition:

There are two turing-machine's which have the same language and doesn't accept the language L.

For the second condition:

$M_1$ is the turing-machine that accepts all, and...
$M_2$ is the turing-machine that rejects all.

So both conditions are true which implies I can apply the Rice Theorem?

Thank's for your help.

From Wikipedia:

Let S be a set of languages that is nontrivial, meaning

there exists a Turing machine that recognizes a language in S,
there exists a Turing machine that recognizes a language not in S.

Then it is undecidable to determine whether the language recognized by an arbitrary Turing machine lies in S.

It's the language (determined by the TM) that has the property, not the TM itself. Your first condition is not needed at all, and the second condition should state
"$L(M_1')$ has the property, and $L(M_2')$ does not."
An example of application of Rice's Theorem might be the following statement. The set
$$S = \{<M> : \varepsilon \in L(M)\}$$ is undecidable. The corresponding TMs might be $M_1$ which only accepts $\varepsilon$ and $M_2$ which doesn't accept any words.
Your example is not correct since the property is trivial. $\emptyset \subseteq A$ for any set $A$, even an empty set.


Understanding facts about regular languages, finite sets and subsets of regular languages I am aware of following two facts related to two concepts: regular languages and finite sets:

  Regular languages are not closed under subset and proper subset operations.
  It is decidable whether given regular language is finite or not.

However I feel these facts are quite insufficient to prove whether following statements are true or false:

If all proper subsets of $L$ are regular, then $L$ is regular.
If all finite subsets of $L$ are regular, then $L$ is regular.
If a proper subset of $L$ is not regular, then $L$ is not regular.
Subsets of finite sets are always regular.

I feel 3 is false, as regular languages are not closed under proper subset operation. Right?

But I am unsure of the other points. What facts I am missing to answer above statements true or false?

One useful fact about regular languages is that a union of finitely many regular languages is regular. From this it follows that all finite languages are regular: the language that recognizes a single constant string is always regular, and a finite language is a union of finitely many constant strings.

(Proof: remember that regular languages are exactly those representable by regular expressions. A regular expression can be trivially written to recognize a single constant string. To recognize a finite union of regular languages, simply combine their regular expressions with the union operator. Now you have a (potentially enormous but) finitely-long regular expression recognizing the entire language.)

This means that 1 is true, because a finite set is equal to the union of all its proper subsets, and an infinite language always has a non-regular subset.

(Proof: if a language $L$ is finite, then it has finitely many subsets, and is equal to the union of these subsets. If $L$ is infinite, then it has uncountably many subsets. But there are only countably many regular languages over a given alphabet, because regular expressions are strings and thus can be enumerated. Thus by diagonalization there exists a non-regular subset.)

2, on the other hand, is false as long as there exists an infinite non-regular language. (And such a language does exist: $\{ 0^n 1^n | n \in \mathbb{N} \}$ is a classic example.) It's not regular, but all its finite subsets are finite, and thus regular.

Your intuition is correct: 3 is false. The non-regular language I just mentioned is a proper subset of $\{ 0^a 1^b | a, b \in \mathbb{N} \}$, which is regular.

4 is also true, since any subset of a finite set is always finite.


Convert finite automata to regular expression I am trying find the regular expression that describes the finite automata in the image below.
Given the following finite automata
which of the following regular expressions describes the same language as the automaton.

(ab)+c*d+
a+b+c*d+
a(ba)*bc*dd*
[ab]+c*d+
a(ba)*bc+d?d+
(ab)+c+d*

I tried converting it to a regular expression and I got (ab)*ac*dd*, which is not among any of the options. Could someone help me select the correct answers?

You have an error in your regular expression. The correct one is $(ab)^*ab c^*dd^*$ (notice that after reading $(ab)^*$ you are in state $A$ and that the edge from $B$ to $C$ is labelled $b$).
This can be rewritten as $(ab)^+ c^*d^+$ since $(ab)^*ab = (ab)^+$ and $dd^* = d^+$.
Another equivalent expressions is $a(ba)^*bc^*dd^*$ since $(ab)^+ = a(ba)^*b$.


prove sufficient number of comparisons for the merge problem It is given two subsequences. Their length are following: $2$ and $5$.
I can show that lower bound of comparisons is $5$. My problem is that I can't show that $5$ is sufficient number of comparisons to merge these subsequences.
In order to show lower bound I use tree of comparisons (number of leaves is $21$, so height is at least $5$).
However, when it comes to proof of sufficient number of comparison I have no idea.  The only idea that comes to my mind is following:
Let our subsequences will be: $(a, b)$ and $(c, d, e, f, g)$. Let say, that we must use $k$ comparisons to find place for $a$, where $k\le 5$. Now, because of fact that $b\ge a$ we must do at most $5-k$ additional comparisons. Thus, $5-k+k=5$.
What about this proof ? Maybe you have other approach?

You asked about what approach to take, so I'll explain the general approach to take for this kind of problem.

The way to prove that 5 comparisons are sufficient is to exhibit a specific algorithm for merging these two sequences, and prove that your algorithm uses no more than 5 comparisons (no matter what the input is).

So, here's the approach I'd suggest for you, as your next step.  Flesh out the algorithm that you have in mind.  You seem to have an idea in mind, but take it the rest of the way: actually write down some pseudocode.  Then, once you've written it down, try to analyze/upper-bound the number of comparisons your algorithm uses.  See if you can prove that it uses at most 5 comparisons.  (Try it on some example inputs if you need, to spot a pattern.)  If you have proven that it correctly merges the two subsequences and you have proven it will never use more than 5 comparisons, you've proven that 5 comparisons are enough.

On the other hand, if you can't prove that (maybe your algorithm might take more than 5 comparisons on some inputs), you can't conclude anything -- you'll need to keep trying to find another algorithm.


N-Grams - how to predict further into the future and how far can we predict? I am using N-Grams to predict future character input. For n+1, it performs really well.

I've been looking, but I have not been able to find any information on what the feasible maximum distance into the future N-Grams are capable of.

One way I could do this is to predict the next character (n+1) and then use that result to predict n+2, use n+2 to predict n+3... etc... but obviously an incorrect prediction will cascade and impact the future predictions as there is a dependency.

Is there a better (more accurate, reliable) way to do this? Also, I can easily use N-Grams to predict the next (n+1) character in an incoming stream, but what about n+2? How about n+3? When does it become unrealistic to predict further?

I'm sure there is some research on this, so I'd love it if you could link me to a paper or give me a brief overview to get me going.

There's no simple answer to "how far into the future can you predict?".  Obviously, the further you go, the less your ability to predict.  For English text, I would expect that ability to predict would decrease rapidly.

You asked if there's a better wya to do this.  You can of course consider a generalization of $n$-grams where you use the characters at positions $i-n+1,i-n+2,\dots,i-1,i$ to predict the character at position $i+k$ (instead of predicting the character at position $i+1$), for any fixed $k$.  This will probably perform worse the larger $k$ is.

You might also be interested in skipgrams.


Do unconditional branches cause control hazards? Do unconditional branches, such as jump/goto instructions cause control hazards? If so, why?

I am wondering because if unconditional branches did cause control hazards, that is like saying if A were the jump foo instruction and another instruction B was the first one under foo:, B would have a control dependency on A. While this is technically true, I don't see how this would cause a hazard in a pipeline since we know with 100% certainly that B will be executed since an unconditional jump instruction A preceded it.

YES, unconditional jumps can cause a control hazard in a pipelined machine.

  we know with 100% certainly that B will be executed since an unconditional jump instruction A preceded it.

Well, we know, but the CPU does not know.
I mean, the CPU does know that we need to jump to B, but only after the CPU decodes the jump instruction and realizes that the instruction is a jump (to B). Until that point thee CPU did not know it is about to jump and during that period it continued inserting other instructions to the pipe (not necessarily from B).

When the CPU finds out it has a jump it is "too late": the pipe is already contaminated with other instructions.

In your example, the "contamination" is in fact the correct code, but in the general case it may a different code segment.


Finding Conflict algorithm doubt Let $e_1,e_2,\cdots,e_n$ are some events are given by their starting time and ending time.

I have to find an event that conflict with maximum number of other events.

Conflicts means interval overlaps

The idea is as follows: Sort events according to their starting times and then for each event check whether it conflict with other evenets or not. The first step seems to me doable in $\mathcal{O}(n \log n)$ time, but second step i.e. to find the number of events with which it conflicts is seems to $\mathcal{O}(n)$ Can we do it in $\mathcal{O}(\log n)$ time?

Question : Is it possible to do the second step as mentioned above in $\mathcal{O}(\log n)$ time?

Take all $2n$ starting and ending times and sort them, then walk through the list in sorted order, increasing a counter at each "starting" time, and decreasing the counter at each "ending" time.  On every counter increase, check whether this is the highest the counter has gone so far, and if so update the best-so-far event.


A restatement of Moore's law that takes into account quantum computing The first line of the Wikipedia article on Moore's law states that

  Moore's law is the observation that the number of transistors in a dense integrated circuit doubles about every two years

As scientists groan on about running into the physical limits of Moore's law, another bunch of scientists[or the media?] seems to feel like they can keep up the trend by leveraging characteristics of quantum computers.

However, a quantum computer doesn't use transistors in the same way that a traditional computer does, and adding another qubit, according to my knowledge, can double the computational power of the computer!

For that reason, is it time to restate Moore's law in such a way that it can take into account computational power as an abstract concept, and not necessarily a physical one?

Does it even make sense to ask that question?

Quantum computers are interesting, but I don't think the primary motivation for quantum computers has anything to do with Moore's law.  You might want to double-check where you got that impression from.  Quantum computers -- if possible -- will be faster for some narrow set of problems, but by no means for all problems.  See Why and how is a quantum computer faster than a regular computer? and Is it proven that quantum computation is no better at solving NP complete problems than classical computation?.

It's not really accurate to say that adding another qubit doubles the computational power of the computer.  I suspect you might be falling for a common misconception about quantum computing (that they "try all possible combinations...").  See The Limits of Quantum by Scott Aaronson for some explanation.

I don't think there is any need to restate Moore's law.  It is a rough rule of thumb about classical computers.  It doesn't claim to say anything about quantum computers or computational power in general.


When problem A reduces to problem B, which problem is more complex? When discussing complexity classes, when we say that problem $A$ reduces to problem $B$, are we saying that problem $A$ is at least as complex as problem $B$, or the other way around?

When we reduce $A$ to $B$, we are saying "If I could solve $B$ in some model of computation, then I could solve $A$ in that model, too" (as long as the reduction is sufficiently simple that it can be performed within the relevant model of computation).

This means that $B$ is at least as hard as $A$. But $A$ could be easier – much easier. For example, let $A\in$ P and let  $B$ be any EXP-complete problem. Because $B$ is EXP-complete, every problem in EXP reduces to $B$ so, in particular, $A$ reduces to $B$. But we know that $A$ is strictly easier than $B$ by the time hierarchy theorem.


Undecidable/Decidable Language This question might sound stupid but, can the language of a TM be not recursively enumerable ?

Thank you ~

No, because A TM has 3 possibilities: run forever, accept, or reject. So the language of a TM is recursively enumerable as the TM M either accepts some input x, which means x is in L(M), or otherwise rejects or runs forever.

A language can be non-recursively enumerable, but the language of a concrete TM is always recursively enumerable.


Is potential causality relation equals to set of consistent happens before relations? In a book dedicated to distributed algorithms, I found the following definition - potential causality diagram is consistent with happens before diagram if potential causality relation between system events is a subset of happens-before relation. So far so good.

But then I have read following claim potential causality diagram equals to the set of happens before diagram to which it consistent with. But how that is possible? I mean that cardinality of potential causality relation is less than the cardinality of happens before relation to which it consistent with. How may potential causality relation be composed of union of such happens-before relations? I agree that potential causality relation may be composed of a set of happens-before relations, but from my point of view happens before relations in such case should be subsets of potential causality relations? Could you explain what I missed?

Update: Quotation from the book. "Given a potential causality diagram $(E, \xrightarrow{p})$, a happened before diagram $(E, \rightarrow)$ is consistent with it if $\xrightarrow{p}\subset \rightarrow$.

is consistent with

Observe that $e_2 ->f_4$ but $\neg(e_2 \xrightarrow{p} f_4)$. A potential causality diagram is equivalent to the set of happened before diagrams that are consistent with it.

Vijay K. Garg. Elements of Distributed Computing (Kindle Locations 301-302). Kindle Edition.

The book says "A potential causality diagram is equivalent to the set of happened before diagrams that are consistent with it."  (emphasis added)

You seem to have interpreted that as "A potential causality diagram is equal to the union of happened before diagrams that are consistent with it."  But that's not the same statement.  I would suspect that this might be the cause of your confusion.  Go back to the original statement and disregard the idea of taking the union, and see if you can make sense of the original statement.

Perhaps there is additional explanation or context after that sentence.

If not, perhaps the book is claiming there is a bijection between (a causality diagram C) and (the set of happens-before relations that are consistent with C).  That claim sounds accurate.  To construct the inverse map: given such a set of happens-before relations, take the smallest element in the set, and that's C.


Is there an algorithm for selecting best matching data in a data set given a set of parameters? What I am trying to do is for a diet app that I am planning to build. The goal is the users will input their desired macros (carbs, fat, protein) and the system should find all recipes that match the provided macros. It does not have to match it exactly, just the best match.
Another idea is users provide their daily calorie intake and the system will find the best match, regardless of the macros.

Links and study materials are much appreciated.

Assuming you don't have that many recipes, you could just go over all of them and choose the best $k$ (use a heap of size $k$). You should test the naive approach before looking for fancier approaches.

Otherwise, you could use a data structure supporting nearest neighbor search. These are hard to implement, but good implementations should be available in computational geometry libraries.


Circular Queue using Dynamic Array I'm learning data structures from "Fundamentals of Data structures in C" by Sahni . In the topic, Circular Queue using Dynamic Array, the author has mentioned below point,

  Let capacity be the initial capacity of the circular  queue,We must first
  increase the size of the array using realloc,this will copy maximum of capacity elements on to the new array. To get a proper circular queue configuration, we must slide elements in the right segment(i.e, elements A and B) to the right end of the array(refer diagram 3.7.d). The array doubling and the slide to the right together copy at most 2 * capacity -2 elements.

I understand array doubling copies at most capacity elements. But how does array doubling and slide to right copy at most 2 * capacity -2 elements??

I think the author is just saying the circular list has capacity of $n-1$ where $n$ is the total cells. When the array is doubled there is copying of these $n-1$ elements to new array in addition with shifting of these $n-1$ elements in the worst case, thus making it total $2n-2$ doubling and sliding in the worst case.


Guidance for Theory of Computation I have been studying Introduction to Theory of Computation by Micheal Sipser and I just complected it. Now I want to take this a step further what should I do next to increase my skills. I tried looking at some papers from FOCS but they were beyond my understanding. I want to know what should I study next.

Theory of Computation, as practiced in the US, focuses mainly on two areas: algorithms and complexity. For algorithms, the standard textbook is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein, also known by its acronym CLRS. For complexity, there's the advanced textbook Computational Complexity: A Modern Approach, but it might be too much for a beginner.


Reservoir sampling algorithm probability I'm reading about the reservoir sampling technique called Algorithm R.

The idea is we can take a sample of size $n$ from a population of size $N$ even when $N$ is unknown/too expensive to retrieve in $N$ time. I quote a sample implementation from wikipedia:

(*
 S has items to sample, R will contain the result
*)
ReservoirSample(S[1..n], R[1..k])
 // fill the reservoir array
 for i = 1 to k
     R[i] := S[i]

 // replace elements with gradually decreasing probability
 for i = k+1 to n
   j := random(1, i)   // important: inclusive range
   if j <= k
       R[j] := S[i]

The explanation for why this works:

  The algorithm creates a "reservoir" array of size $k$ and populates it with the first $k$ items of $S$.

That is pretty clear, the first for loop in the code sample does that. Then:

  It then iterates through the remaining elements of $S$ until $S$ is exhausted. At the $i$-th element of $S$, the algorithm generates a random number $j$ between $1$ and $i$. If $j$ is less than or equal to $k$, the $j$-th element of the reservoir array is replaced with the $i$-th element of $S$.

Also clear. But here comes the Math:

  In effect, for all $i$, the $i$-th element of $S$ is chosen to be included in the reservoir with probability $\frac{k}{i}$.

Hmm, I'm probably not well versed enougn in probablility theory, so can someone explain in more detail how the probability is $\frac{k}{i}$?

What I also don't get: do all elements have the same chance of being included in the (final) reservoir? From my understanding, it seems like the probability decreases for the elements at the end of $S$ to be included, then the reservoir will be skewed towards including the earlier elements, or am I misled?

The whole reason for performing this sampling method is to get an uniform sample even if the population size is unknown at the start. So, if this method works, the probability cannot be skewed.

What happens, is that the samples chosen in the beginning have a chance to be overwritten by the samples chosen later. Intuitively, this balances it somewhat. But we must show that this 'balance' holds precisely:

The probability of $\frac{k}{i}$ refers to the  probability that sample $i$ is added to the reservoir, as it is added when a uniform random integer from $[1,i]$ is less than $k$, i.e. $k$ positions in the range $[1,i]$ lead to inclusion in the reservoir. (Total number of events is $i$, number of events that we 'want' is $k$, all events are equally likely, so final probability is $\frac{k}{i}$)

Now what is the probability that $i$, when chosen, remains in the reservoir until the end? It gets removed when a single integer in the range $[1,m]$ is picked, for all $i<m\leq N$. The probability that it doesn't get replaced at position $m$ is $1-\frac{1}{m}$. As these events are independent, the total probability that $i$ doesn't get replaced is $\prod_{m=i+1}^N (1-\frac{1}{m}) = \frac{i}{N}$ $^*$. As $i$ is in the reservoir at the end if it gets picked and not replaced, this probability is $\frac{k}{i}\cdot \frac{i}{N} = \frac{k}{N}$.

We're not done yet, as the calculation above only holds for the samples not originally in the reservoir. However, that case is similar: as they are always put in the reservoir, we only need the probability they stay, which is $\prod_{m=k+1}^N (1-\frac{1}{m}) = \frac{k}{N}$.

So the probability of being included in the final sample is the same for all positions, which means the final sample is uniform.

*: The expression $\prod_{m=i+1}^N (1-\frac{1}{m})$ can be simplified as follows:

\begin{align}\prod_{m=i+1}^N (1-\frac{1}{m}) &= \prod_{m=i+1}^N (\frac{m-1}{m})\\ &= \frac{i}{i+1}\cdot\frac{i+1}{i+2}\cdots \frac{N-2}{N-1}\cdot \frac{N-1}{N}\\ &= i\cdot\frac{i+1}{i+1}\cdot\frac{i+2}{i+2} \cdots \frac{N-1}{N-1}\cdot \frac{1}{N} =\frac{i}{N}.
\end{align}

It is also possible to show by induction on $N$, but I think the previous is more insightful.


What is the fastest way to check if an integer is divisible by another? What would the Big O be?
Can something like this be done in O(log(n)) where n is the number of bits?

Integer division

The best algorithm known for integer division has running time that is slightly more than linear, i.e., a bit more than $O(n)$.  In particular, it is something like $O(n \lg n 2^{\Theta(\lg^* n}))$ (which is a bit faster than $O(n \lg n \lg \lg n)$.  The time complexity of integer division is the same as the time complexity of integer multiplication.  See https://en.wikipedia.org/wiki/Division_algorithm and https://en.wikipedia.org/wiki/Multiplication_algorithm.

Caution: these algorithms are purely theoretical.  The constants hidden by the big-O notation make them impractical for most sizes you'll run into in real life.  But there are plenty of other algorithms that are faster than the naive algorithm and are useful in practice.

No, you can't do it in $O(\lg n)$ time, where $n$ is the number of bits in the input: you obviously can't do it in less than $O(n)$ time, since it takes that much time just to read in the entire input.

Testing divisibility

The problem of testing divisibility could in theory be easier: it asks for just a yes-or-no answer (is $y$ divisible by $x$ or not?) instead of the result of the full division (compute $\lfloor y/x \rfloor$).  Obviously, you can use any algorithm for integer division to test integer divisibility (with the same running time).  I don't know if there is any faster way to test integer divisibility.

A conceptually simple way to test whether $y$ is divisible by $x$ is to check whether $y \bmod x$ is zero or not.  However, I don't know of any way to compute the remainder $y \bmod x$ in linear time (in time linear in the number of bits of the input, i.e., in $O(n)$ time, where $n=\lg(x)+\lg(y)$).  As before, you obviously can't do it in less than $O(n)$ time.

See also https://cstheory.stackexchange.com/q/16788/5038, which basically states the same thing: no faster algorithms are known, but no one has proven lower bounds ruling out the possibility of faster algorithms.


Reduction to Hamiltonian cycle Given that the Hamiltonian cycle problem is NP-complete, I want to prove that the following problem is NP-complete:

  Given an undirected graph $G(V,E)$ and vertices $s,t\in V$, does there
  exist a path from $s$ to $t$ with at least $k$ edges such that all vertices
  in the path are distinct?

I thought of assigning a weight of $1$ to every edge and on similar grounds, but I am not able to compensate for the "at least $k$" edges part.

It would be appreciated if somebody could help me with  the approach.

Problem is in NP

You can easily verify an answer to your problem: if a path is given, and it is goes from $s$ to $t$ and has $k$ edges with distinct vertices, then it is correct.

Reduction from Hamiltonian Cycle Problem

You can pick any vertex as $s$, and then for each neighbor, $(s,t_i)\in E$, attempt your algorithm, with $k=\left|V\right|-1$ after cutting that edge. If the algorithm succeeds for any attempt with $(s,t_i)$, then you have found a Hamiltonian cycle. This means Hamiltonian path reduces to your given problem.

Given that it is in NP, and the Hamiltonian Cycle Problem can be reduced to it, it is NP-complete.

EDIT
I suppose an even simpler reduction is just to set $s = t$, and for any vertex in $V$, with $k=\left|V\right|-1$.

Though I am unsure of how one would solve this problem given $s,t,k,V,E$ in the general case. Nor do I know how to reduce this problem to the Hamiltonian cycle problem. A roundabout way would be to reduce this problem to 3-SAT, and then reduce the result back down to Hamiltonian cycle. However, as I pointed out above, you can easily see it is NP-complete, due a reduction from Hamiltonian cycle to this problem, in conjunction with the fact that the problem is in NP (you can verify the answer easily).

k-Stroll / k-Tour

A similar problem is named the k-Stroll problem in Approximation Algorithms for the Directed k-Tour and k-Stroll Problems:

  The input to the k-Stroll problem is a directed $n$-vertex graph with nonnegative edge lengths, an integer $k$, and two special vertices $s$ and $t$. The goal is to find a minimum-length $s$-$t$ walk, containing at least $k$ distinct vertices.

Also related is the k-Tour problem, which is the case where $s=t$.


Why do AlphaGo and AlphaGo Zero include board history in the input features Both AlphaGo and AlphaGo Zero include prior board states as input features (the "Turns Since" planes for AlphaGo, and the repeated 8-step history planes for AlphaGo Zero).

What is the purpose of including this history information in the input to the neural networks?

If we ignore the ko rule, the best move at a position should not depend on the history of moves leading up to that position. If we don't ignore ko, a single step of board history should be sufficient in the vast majority of games, so including 8 steps of history seems excessive (and possibly even harmful, since if the same position were reached by two different paths, the learned response might not be shared between those two paths).

This doesn't seem to be discussed in either of the papers, or in any of the media reporting that I have seen.

The primary reason for including a history of states is likely indeed the ko rule. Even if having a long history will often be redundant, it's unlikely to hurt either (except that it might take some computation time... but that doesn't appear to be a major concern throughout the entirety of the papers).

I imagine that having a history of states can also help the Neural Network to more easily "focus" on important areas of the board during training (maybe only in the beginning of the training process, maybe for a longer time). You're right that, from a game-theoretic point of view, the current game state should be sufficient (ignoring rare cases). However, the learned components of AlphaGo Zero are not optimal in a game-theoretic sense early on in training (and likely still aren't after training either). Architectural choices in the Neural Network that may be redundant in a game-theoretic sense may still be beneficial for more rapid learning.

For example, in early stages of learning when learned components are still performing poorly, I imagine a useful heuristic may be to pay more "attention" to areas of the board where moves have recently been made; these are more likely to be important areas of the board than some different area of the board where nothing is going on (especially for an amateur-level component in the beginning of a learning process). Such areas of the board can easily be identified by subtracting game states in the recent history from each other.

I would not be surprised if this indeed ends up happening to some extent during the learning process. Stochastic Gradient Descent tends to, intuitively, take the path of "least resistance" and greedily optimizes parameters wherever it happens to notice some correlation between inputs and outputs. Of course this whole argument is rather handwavy, and it also may not at all be happening... I suppose the main point is what I put in boldface above. Neural Network-based components are not optimal in a game-theoretic sense, and they're also trained using algorithms (SGD-style) that may take suboptimal paths to global minima or not even find a global minimum at all. Modifications that would not be necessary for an "optimal" solution may still help to more easily or more quickly find good solutions.

David Silver, one of the first authors on both of the AlphaGo papers, describes a similar hypothesis to what I described as "focus" (more commonly described as "attention") here (emphasis mine):

  Actually, the representation would probably work well with other choices than 8 planes! But we use a stacked history of observations for three reasons: 1. it is consistent with common input representations in other domains (e.g. Atari), 2. we need some history to represent ko, 3. it is useful to have some history to have an idea of where the opponent played recently - these can act as a kind of attention mechanism (i.e. focus on where my opponent thinks is important).


How to construct a DFA which accepts all the strings endig with aa and no two consecutive b (bb) I have to construct a DFA which ends with aa and does not contain any pair of b-s. A = {a,b}, {aa,baa,aaa,abaa,babaa,...}. I know how to construct them as separate DFAs but not together merged.

If you know how to construct DFAs for two languages separately, you can use systematic methods to build the DFA which recognises the intersection of the languages (e.g. https://math.stackexchange.com/questions/147457/intersection-of-two-deterministic-finite-automata). However to achieve a minimalist and elegant result (as well as for learning purposes) you may want to try and find ad-hoc methods.
NB: You can always apply a DFA minimization procedure to 'clean up' the automaton obtained via the above general method (https://en.m.wikipedia.org/wiki/DFA_minimization).


Using dynamic programming to maximize work done Say that there are $n$ days and there is $x_1, x_2, ...,x_n$ amount of data to process on each day. Your computer can process $s_1$ amount of work on the first day since rebooting your computer, $s_2$ work on the second day since a reboot, up to $s_n$. On each consecutive the day the amount of work your computer can perform without being rebooted decreases. In other words, $s_1 >s_2>...>s_n>0$. Any day you reboot your system you cannot do any work.

The problem is to find an algorithm using dynamic programming to figure out the maximum amount of work possible given $x_1...x_n$ and $s_1...s_n$. This means we must determine which day(s), if any, we should reboot on.

For example:

n| 1 | 2 | 3 | 4
x| 8 | 3 | 11| 5
s| 9 | 4 | 2 | 1

The most optimal solution here would be to reboot on day 2, so that we can perform 8 work on day 1, 9 work on day 3, and 4 work on day 4 for a total of 21.

This seems somewhat similar to the partition problem but I am having trouble coming up with a recurrence relation I can convert to dynamic programming.

If we say that our final reboot occurs on day $i$, then our maximum work should be the amount of work done from days $i$ to $n$ plus the maximum work we can do on days $1$ to $i-1$.

So if we say $M[x_1...x_m,s_1...s_n]$ represents the maximum amount of work we can do on days $1$ to $m$, I write the following recurrence relationship:

$$M[x_1...x_m,s_1...s_n] = \max_{i=1}^m\{M[x_1...x_{i-1},s_1...s_n]+R[i]\}$$

Where $R[i]$ is simply the max amount of work you can do from days $i$ to $n$ without rebooting, which is simple to calculate.

Does this seem like it is a valid recurrence relation? Also, I am not quite sure what my base cases would be. Perhaps that $M[x,s] = \{x$ if $s \geq x$ else $s\}$? I am not sure if this covers all possibilities though.

This seems to be exercise 9 from Kleinberg's Algorithm Design, chapter six. I'll report how i tried to solve it.

Let's define $OPT(i)$ as the maximum amount of work from day $1$ to day $i$, with $i \leq n$

For every $i$, there can be a reboot in any previous day $1\leq j < i$. If it was on day $j$, than you processed $\sum_{k=j+1}^i \min\left\{s_{k-j}, x_k\right\}$ terabytes. Furthermore, on day $j$ you cannot process anything. Than you can define the following recurrence relation:
$$
OPT(i) = \displaystyle\max_{1\leq j < i} \left\{\displaystyle\sum_{k=j+1}^i \min\left\{s_{k-j}, x_k\right\} + OPT(j-1)\right\}
$$

The algorithm can be implemented in a bottom-up fashion, with $O(n^3)$ running time:

let OPT[0...n] be a new array of n+1 elements
OPT[0] = 0, OPT[1] = min(s[1], x[1])
for i = 2 to n
  m = -infinity
  for j = 1 to i-1
    l = 0
    for k = j+1 to i do l = l + min(s[k-j], x[k])
    l = l + OPT[j-1]
    if l > m then m = l
  OPT[i] = m
return OPT[n]

There is also a $O(n^2)$ solution based on a matrix of subproblems. Define $OPT(i, j)$ as the maximum from day $i$ to $n$ with last reboot done $j$ days before, more exactly on $i-j$ day. For every day $i$ you have to consider these alternatives:

you have a reboot. So on day $i$ you cannot process anything: $OPT(i,j) = OPT(i+1, 1)$
go on with processing: $OPT(i,j) = \min\left\{s_j, x_i\right\} + OPT(i+1, j+1)$

Because it's of no use reboot on last day, you have $OPT(n,j) = \min\left\{s_j, x_n\right\}$.

This last approach is taken from Mangat Rai's work, a user that shared a collection of solutions to Kleinberg's book problems, although the first one i reported is also very close to what you can find there. I suggest you to do a web search for it (no official site as far as i know).


Why is the probability used in the definition of RP complexity classes, arbitrary? I was looking at the following wikipedia article on the RP complexity class:

https://en.wikipedia.org/wiki/RP_(complexity)

In its definition it states:

If the correct answer is NO then it always returns NO
If the correct answer is YES then it returns YES with a probability of 1/2

At the end of the introduction it says:

  The fraction 1/2 in the definition is arbitrary. The set RP will contain exactly the same problems, even if the 1/2 is replaced by any constant nonzero probability less than 1; here constant means independent of the input to the algorithm.

What I don't understand is why this 1/2 is arbitrary? If you change it to 1/3 does it really still contain the same set of decision problems as with 1/2?

Yes, the constant is entirely arbitrary. Call an algorithm a $p$-algorithm if:

When the correct answer is NO, it always answers NO.
When the correct answer is YES, it answers YES with probability at least $p$.

Note that the probability in the YES case is only over the algorithm's coin tosses.

Given a $p$-algorithm and a constant parameter $m$, we construct a new algorithm which runs the original algorithm $m$ times (with independent coin tosses) and takes the OR of the result. This algorithm is a $1-(1-p)^m$-algorithm (exercise). For every constant $q < 1$ you can find a constant $m$ such that $1-(1-p)^m \geq q$. Hence if a problem admits a $p$-algorithm it also admits a $q$-algorithm, for every $0 < p,q < 1$.


Find a maximum matching that saturates a given set of vertices In an unweighted bipartite graph $G = (X + Y,E)$, we would like to find a maximum matching, but among all those maximum matchings, we would like to find one that saturates a given subset $X_0\subseteq X$.
A necessary condition for the existence of such a matching is that $X_0$ satisfies Hall's marriage condition, i.e., for every $X'\subseteq X_0$, the number of neighbors of $X'$ is at least $|X'|$.
If this condition is satisfied, we can find a matching $M$ that saturates all vertices of $X_0$, but $M$ is not necessarily a maximum matching in $G$.
Is it always possible to extend $M$ into a maximum matching? Alternatively, is there a different way to find a maximum matching that saturates $X_0$ when the necessary condition is satisfied?

After some research, I found out that my question is a special case of the problem of priority matching. In this case there are two priority classes, $X_0$ and $X_1 := V\setminus X_0$. The goal is to find a matching that maximizes the number of saturated vertices in $X_0$, and subject to that, the number of saturated vertices in $X_1$. There are efficient algorithms that solve this problem for any number of priority classes. It is known that any priority matching is also a maximum-cardinality matching.


Maximizing integer sets intersection (with integer delta) There are two sets of integers with different numbers of items in them.

X= { x_0, x_1, ... x_n }, x_0 < x_1 < ... < x_n
Y= { y_0, y_1, ... y_m }, y_0 < y_1 < ... < y_m

And there is a function of a single integer defined as

F(delta) = CountOfItems( Intersection( X, { y_0+delta, y_1+delta, ... y_m+delta) ) )

That is - i add delta integer to every element of the Y and then count how many same integers  are in the X and the modified Y.

And then the problem - find delta that maximizes F(delta).

max( F(delta) ), where delta is integer

Is there some "mathematical" name for such task and optimal algorithm for this?
Obviously i can use brute-force here and enumerate all possible combination - but it does not work for big n and m.

You can compute the sumset (well, difference set) $X-Y$ using standard techniques (Computing Cardinality of Sumsets using Convolutions and FFT).

As an optimization, I suggest first replacing $X,Y$ with $X'=X \bmod p$, $Y'=Y \bmod p$ where $p$ is at least $n+m$ or so.  Then, enumerating through the elements of the multiset $X'-Y'$ by decreasing cardinality will give you good candidates for $\delta \bmod p$.  The running time to compute $X'-Y'$ will be $O((n+m)\log (n+m))$, and if the maximum value of $F(\delta)$ is sufficiently large, I expect you should be able to find the correct value for $\delta$ among the first few candidates.


Why Finite Automata are restricted in reading the input? Well, I should have posted this question before Why NFA is called Non-deterministic?. Anyways now this is pondering in my mind.

Why people who came up with this automaton theory restricted the input format of it as a read-only, symbol-stream tape.

Is it not so that if we provide random accessible input tape (as in case of many computer programs) to the automaton it will be more powerful? (however it is purely my intuition having no standard proofs)

Yes, there are things you could do to finite automata to make them more powerful. However, "with great power(er) comes great(er) responsibility."

Finite automata aren't very powerful but the languages they express – the regular languages – form a natural and important class.  Furthermore, for a fixed automaton, you can decide in linear time (with respect to the input) and constant working space whether it accepts or rejects any particular string. This is true even if the automaton is nondeterministic.

OK, but lots of important languages can't be decided by finite automata.  Important examples include anything that involves bracket matching, including the syntax of any sane programming language. How might you try to make automata more powerful and what would the cost be?

Suppose we allow the machine to scan both left and right along its input. This gives a two-way automaton.  Well, it turns out that two-way automata (deterministic or nondeterministic) still only accept regular languages – the same as ordinary automata. The two-way automaton might require fewer states and you can still determine whether it accepts a given input in linear time.  But now there's the possibility that the automaton can loop forever, so you need to check for that, which requires a logarithmic amount of working space, instead of constant.  (Since the number of steps before termination is bounded by some linear function of the length of the input, you can detect looping by counting steps and halting if the computation runs too long.  The counter needs a logarithmic number of bits.)
Suppose you allow the automaton to move backwards and forwards as well as overwrite its input, but not to use any more space than the input takes up.  This does make the machine more powerful (for example, you can now detect well-matched bracketings by "crossing out" the brackets one by one) but it makes it even harder to determine whether the machine accepts its input and to check for infinite loops.  Now, halting might take exponentially many steps, so you need a polynomial-length counter (linear is probably enough).
Suppose you allow the automaton to move backwards and forward, overwrite its input and use as much additional space as it wants.  Now your automaton has become a Turing machine.  It can do (we think) anything that any reasonable computer can do but there's no way of determining whether it accepts its input except for running the machine and hoping it eventually stops. This could take arbitrarily long and use arbitrarily much working space.

There are plenty of other possible additions to automata (for example, stacks) but they don't fit as neatly into the discussion above.

So, yes, you might want to make automata more powerful.  But doing so brings risk and expense that you might not be prepared to tolerate, if you don't need it.


Find original array from array with pairs of adjacent elements Given an array composed of pairs, like this:
[[3,5],[1,5],[3,2],[1,4]]
Each element in the array (call it pair) means that pair[0] and pair[1] are adjacent in the original array. Note, they can come in either order. For instance, for the sample array above, the original array would be:
4,1,5,3,2 (or the reversed version of this)
How can I do this quickly? I tried doing this as follows, which works, but it's too slow:
Create a hashmap that maps adjacent elements. Map = {3: [5,2], 1: [5,4], 5: [1,3], 4: [1], 2:[3]}. My algorithm would then start with one of the keys that only has a corresponding value length of 1 (in this case either 4 or 2), and then add to an output array, and go through the hashmap. I.e. First I would add 4 to my output, and then go from key of 4 (with a corresponding value of 1), to the key of 1, with corresponding values of 5 and 4. I'd ignore 4 (since it's already in output), and add 5, then go to the key of 5, and so on and so forth. This is too slow! Is there a better algorithm?

Use indegree or DFS:
    unordered_map<int, int> indegree;
    unordered_map<int, bool> visited;
    unordered_map<int, vector<int>> mp;
    for (auto& vect: adjacentPairs) {
        mp[vect[0]].push_back(vect[1]);
        mp[vect[1]].push_back(vect[0]);
        indegree[vect[0]]++;
        indegree[vect[1]]++;
    }
    int start = 0;
    for (auto& in : indegree)
        if (in.second == 1) {
            start = in.first;
            break;
        }
    }
    int n = indegree.size();
    vector<int> result;
    result.push_back(start);
    visited[start] = true;
    while (result.size() != n) {
        for (auto& val : mp[start]) {
            if (!visited[val]) {
                result.push_back(val);
                visited[val] = true;
                start = val;
            }
        }
    }

    return result;


When average , worst and best case time complexity happens in quick sort? I know recurrence relation corresponding to quick sort worst case is

$T(n)=T(n-1)+T(0)+\Theta(n)$

and time complexity is $O(n^2)$.

This happens when we select pivot which is either largest element or smallest element in the current sub problem.

This can occur when array is sorted in either descending or ascending order and we select either largest or smallest element as pivot.

I also know that best case occurs when median is chosen as pivot, giving recurrence relation

$T(n)=T(n/2)+T(n/2)+\Theta(n)$.

and time complexity $O(n \log n)$.

  Statement 1: Any other partition should result in average case.

I have come across problems each time choosing pivot which partition array in some fixed proportion (say $T(n)=T(n/10)+T(9n/10)+\Theta(n)$) ending in average case performance of $O(n \log n)$ (and I understand its proof).

However I have also came across text saying:

  Statement 2: Any pivot which does not partition array in some proportion should result in worst case. If $n$th smallest or largest element is selected as pivot, it will result in worst case.

Q1. Is statement 1 true? If no, which other pivot selection strategies could result in worst case or best case behavior?

Q2. Is statement 2 true?

Remember, for big-O we care about the asymptotic limit. If you choose the $k$th largest (or smallest) element, for constant $k$, then when you make $n$ big enough it's as though you chose the single largest or smallest. The $k$ elements on the other side just aren't enough to matter any more. So statement 2 is true.

Statement 1 is also true; you say you understand the proof of it, so I'm not sure how much detail to go into here. But intuitively, the amount on each side of the pivot grows proportionally to $n$. That's what makes it different from the constant $k$.


Dijkstra's Notes on Structured Programming - concerning the program to compute first 1000 prime numbers In his "Notes on Structured Programming" essay, E. W. Dijkstra gives an example of a program that computes the first 1000 primes (Section 9. "A First Example of Step-Wise Program Composition").

The idea is to iterate all the numbers from 1 to 1000 in increasing order, to test each one and if found to be prime save it into an array p. The test consists of giving an answer to the question of whether the number j is divided by one of the primes found earlier: if it is divided - the number is not prime; otherwise - it is prime.

j is the number under test and here it is assumed to be incremented by 1 at each iteration (in the original paper an optimization has been introduced where j is odd and incremented by 2).
The smallest array index is 1.

Next is an excerpt from the paper followed by the question proper:

  We use the facts that
  (1) [...] the smallest potential factor to be tried is p[1]
  (2) the largest prime number to be tried is p[ord - 1] where p[ord] is the smallest prime number whose square exceeds j.

  (Here I have also used the fact that the smallest prime number whose square exceeds j can already be found in the table p. In all humility I quote Don Knuth's comment on an earlier version of this program, where I took this fact for granted:
  "Here you are guilty of a serious omission! Your program makes use of a deep result of number theory, namely that if $p_n$ denotes the $n$-th prime number, we always have
  $$
p_{n+1} < (p_{n})^2
$$
  " Peccavi.)

In my analysis I have arrived at the conclusion that the program does not depend on this result; that is - the program will work correctly even if the inequality above were not true.
Help is needed in finding the error in my line of reasoning, or to identify the misunderstanding of the source material, if that were the case.

The program makes use of a lemma

  If a natural number $n > 1$ is composite, then $n$ is divisible by some prime number $p \leq \sqrt{n}$.

(A proof can be found in "Discrete Mathematics" 2nd ed., by Edgar G. Goodaire, page 116)

Thus when we test number j for primality we only need to consider those primes whose squares are less than or equal to j.

Suppose that we have computed the first $n > 1$ primes and all of them are in the array p. We next initiate the process of computing the next prime $p_{n+1}$ by incrementing j and testing it for primality.
In the case where $p_{n} < j < (p_{n})^2$, there exists a prime $p_{k}$ such that $$(p_{k-1})^2 \leq j < (p_{k})^2$$
The potential factors of j are $p_{1},p_{2},..,p_{k-1}$ and all of them are in the array p, thus if the next prime lies in the interval $p_{n} < j < (p_{n})^2$ we are guaranteed to find it.
This is the case which corresponds to the theorem pointed by Don Knuth, and since we know it to be true, we could stop here as far as program correctness is concerned.

But for the sake of argument, let's continue and consider the case $j > (p_{n})^2$. All of the numbers $p_{n} < i < j$ are composite, so the largest prime less than j is $p_{n}$ and, by our assumption $(p_{n})^2 < j$. Thus the potential factors of j are $p_{1},p_{2},..,p_{n}$ and all of them are in the array p.

Given that in both cases the entire list of primes whose square is less than or equal to j is in the table p, and that's the necessary and sufficient condition for the primality test, we conclude that the relation $p_{n+1} < (p_{n})^2$ plays no role in the operation of the program.

Statement (2) requires that the smallest prime number whose square exceeds $j$ is in the list. If $j=p_{n+1} > (p_n)^2$, then the smallest prime number whose square exceeds $p_{n+1}$ is $p_{n+1}$ itself. As $p_{n+1}$ is not in the list while tested, (2) no longer holds.

You indeed show that all primes that are divisors of $j$ are in the list. So, an algorithm that tests all divisors in the list would be correct. However, this isn't what the algorithm in the text does, it first looks for a prime of which the square exceeds $j$, but doesn't have to be a proper divisor of $j$.

So, the algorithm as stated in the text does require property (2), which relies on the fact that $j=p_{n+1} > (p_n)^2$. In your analysis, you made the change that only the primes that divide $j$ properly need be in the list. This is a valid algorithm, but it is a different algorithm than the one in the text.

In other words, while having all primes that are proper divisors of $j$ in the list is nessecary, it isn't sufficient to run the algorithm as stated in the text.


Finding the maximum of a random forest If we have some collection of decision trees with single-variable splits and a constant value at each leaf node, the average over all trees gives some function from $\mathbb{R}^n \to \mathbb{R}$. Is it possible to efficiently find the subspace on which this function achieves its maximum? Enumerating all intersections could take exponential time in e.g. the case where each tree is a stump which bisects a different dimension.

It is possible to do better by computing bounds and doing some pruning, but I wonder whether a polynomial-time solution is possible.

If the leaf values are taken from $\{0, 1\}$ then this is a restricted max-clique problem, but I suspect it should be possible to exploit the decision-tree structure to create a faster algorithm.

Any thoughts?

Apparently, it's NP-hard.  See the following paper:

Evasion and Hardening of Tree Ensemble Classifiers.  Alex Kantchelian, J.D. Tygar, Anthony D. Joseph.  ICML 2016.

Section 4.2 says that solving the problem exactly is NP-hard.  However, the paper then goes on to develop techniques that, in practice, might often find an approximate maximum, using integer linear programming.

For a proof of NP-hardness, see Section 5.2 of Kantchelian's PhD dissertation.


Represent a DNF formula as a multivariate linear formula? Lets say I have the following DNF: (x or y) and (z or i) / $(x\lor y)\land(z\lor i)$
How do I convert that into a polynomial form?

Usually one represents disjunction by addition and conjunction by multiplication, so a suitable polynomial would be $(x + y) \cdot (z + w)$ (I renamed $i$ to $w$ here as to not create confusion w.r.t. the imaginary unit).
Note that plugging in $0$ or $1$ depending on the desired truth values yields 0 precisely if the original formula would evaluate to false while any value greater than zero indicates that such an assignment would satisfy the formula.
You mention linear in your title, however I do not think that there is a sensible way to represent propositional formulas by linear functions.


Online generation of uniform samples A source provides a stream of items $x_1, x_2,\dots$ . At each step $n$ we want to save a random sample $S_n \subseteq \{ (x_i, i)|1 \le i \le n\}$ of size $k$, i.e. $S_n$ should be a uniformly chosen sample from all $\tbinom{n}{k}$ possible samples consisting of seen items. So at each step $n \ge k$ we must decide whether to add the next item to $S$ or not. If so we must also decide which of the current items to remove from $S$ .

State an algorithm for the problem. Prove its correctness.

Due to the dubious nature of the question, I only provide hints.

Have you tried the obvious? With probability $\frac{1}{n}$, add the new element to the sample. If it is added, choose one of the elements already in the sample uniformly at random and drop it. Sounds about fair, does it not?

For a proof, you will have to proceed inductively. In the step, you assume that $S_{n-1}$ is indeed a uniform sample. From this and the way you choose whether to include $x_n$ and which element to drop, you have to get that $S_n$ is a uniform sample, too.

Try if you can prove above idea correct. If it is not, find out where the problem is and fix it. See this answer to a similar question for a detailed application of this technique.


Reverse An Array whats wrong with this type of code? import java.io.*;
import java.util.*;
public class reverseAnArray2
{
    public static void main(String args[])throws IOException
    {
        Scanner sc  = new Scanner(System.in);
        System.out.println("Enter size");
        int  n = sc.nextInt();
        int a [] = new int [n] ;
        int b [] = new int [n] ;
        System.out.println("Enter elements");
        for(int i=0;i<n;i++)
        {

            a[i]=sc.nextInt() ;
        }
        int size = n;
        System.out.println("Reverse array is : ");
        int p=0;
        while(n>=0 && p<n)
        {

            a[--n] = a[p] ;
            ++p;
        }
        for(int i =0;i<size;i++)
        {
             System.out.println(+ a[i]);
        }

}
}

The output comes correct but only up to the last $n/2$ terms, rest of it gets repeated. The output was correct when I used another fresh array to store data. But that's not an optimal code. I want to reverse it without using another array.

Notice that you increment $p$, whilst also decrementing $n$. Since your condition in the while loop is that p < n, then the while loop will only work for half the elements.
Also, note that you delete the last $n/2$ values, since you modify them without first reading them.


Prove or disprove: Complement of language $L=\left\{baba^2ba^3b...ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ is context-free Prove or disprove: Complement of language
  $L=\left\{baba^2ba^3b...ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ is
  context-free.

I'm not quite sure how this is done. I would first try to find out whether $L=\left\{baba^2ba^3b...ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ itself is context-free.

The language creates words $x$ of length $|x|= n+1+\frac{n(n-1)}{2}= \frac{n(n+1)}{2}$

So $L$ is not context-free. But I was looking for the complement of $L$, i.e. $\bar{L}$, the language.

Is it possible to argue that $\bar{L}$ is context-free because $L$ is not?

Or how would you show it better?

No, reasoning with the complement will not work as context-free languages are not closed under complement.

Consider an alternative description of $L$: it consists of all strings $ba^{a_1}ba^{a_2} \dots ba^{a_n}b$ such that (1) $a_1 =1$ and (2) for all $1\le k<n$, $a_{k+1} = a_k+1$.


Addition modulo 2 notation (Quantum Computing) I am studying Quantum Computing using the book Quantum Computation and Quantum Information of Michael Nielsen and Isaac Chuang. I am confused by the meaning of the $\oplus$ (addition modulo 2) symbol in the notation.

Given a starting state $|\psi\rangle|\phi\rangle$ and a unitary gate $U$ such that $U|\psi\rangle|\phi\rangle = |\psi\rangle|\phi \oplus f(\psi)\rangle$. What does in this case $\oplus$ mean, in the general case for $|f(\psi)\rangle = \alpha_0 |0\rangle + \alpha_1|1\rangle$ and $|\phi\rangle = \beta_1 |0\rangle + \beta_2 |1\rangle$?

The definition shows how $U$ is defined on the standard basis (that is, when $\psi$ and $\phi$ are pure states). You can extend it to general states in a linear way.

Two more comments:

$\psi$ could be one qubit, but it could also be longer.
$f$ is probably a deterministic function.


Difference between fractional knapsack & greedy solution I am trying to understand what the difference is between the fractional knapsack problem using dynamic programming, and the greedy solution version. Im looking at an example of the fractional problem which looks like:

What's the difference between that and the greedy solution? Are you not just taking the value-per-pound in this example too but it's just not explicitly stated?

The fractional Knapsack problem isn't solved using Dynamic Programming, but can be solved using a greedy algorithm. Item A is \$50/unit, B is \$5/unit and C is \$40/unit. The greedy method is to use as much of the highest value items as possible, which gives the solution on the image.

Dynamic Programming allows you to solve the problem when you cannot split the items.


How to prove $(n+1)! = O(2^{(2^n)})$ I am trying to prove $(n+1)! = O(2^{(2^n)})$. I am trying to use L'Hospital rule but I am stuck with infinite derivatives.

Can anyone tell me how i can prove this?

Well, since this upper bound is not nearly tight, you can just use basic transformations to get

$$(n+1)!< (n+1)^{n}=2^{\log (n+1)^{n}}= 2^{n\log (n+1)}=O(2^{n\log n})\subset O(2^{(2^n)}). $$


In an FSA, can you have more than one transition for the same symbol from a single state? My textbook asks:

  Consider the sets of strings on $\{0,1\}$ where the 4th symbol from the right end is different
      from the leftmost symbol. Construct an accepting FSA.

The answer it provides is below. However, I don't understand how you can have one transition for 0,1 and another for 1 from the same state. What does this mean?

The FA in the image is an NFA as clearly a DFA cannot have more than one move for a symbol from a particular state. Also, it doesn't have any moves for state $q_5$ nor for $q_{10}$.


Can we break the Shannon capacity? I have a friend working in wireless communications research. He told me that we can transmit more than one symbol in a given slot using one frequency (of course we can decode them at the receiver).

The technique as he said uses a new modulation scheme. Therefore if one transmitting node transmits to one receiving node over a wireless channel and using one antenna at each node, the technique can transmit two symbols at one slot over one frequency.

I am not asking about this technique and I do not know whether it is correct or not but I want to know if one can do this or not? Is this even possible? Can the Shannon limit be broken? Can we prove the impossibility of such technique mathematically?

Other thing I want to know, if this technique is correct what are the consequences? For example what would such technique imply for the famous open problem of the interference channel?

Any suggestions please? Any reference is appreciated.

Shannon proved that the capacity of the channel is a limit on its capacity. This is actually the easy part of Shannon's theorem — it is much harder to show that capacity can always be achieved. A good source for this is Shannon's paper from 1948, A mathematical theory of communication, page 24, last paragraph before Section 14. As Shannon writes, the Shannon capacity is the limit more-or-less by definition.

While Shannon already found a formula for the capacity of a channel, namely the Shannon capacity, two directions are still open (though they have partial solutions):

Zero-error encoding, also known as block codes. The best capacity in this regime is a major open problem in coding theory.
Codes with efficient coding and decoding. Shannon's theorem is non-constructive (it uses a random code), and so the codes it implies cannot be used in practice. It is more difficult to construct codes having efficient encoding and decoding. There have been lots of developments in the recent years in constructing efficiently decodable capacity-achieving codes.

Another problem is the rate of convergence in Shannon's theorem - I'm not sure what the status of that is.

In your specific case, it seems that the improvement is not be breaking the Shannon barrier (which is impossible) but by effectively changing the channels, just as telephone lines can be used to carry high-speed network traffic.


How to find left-hand side of tape on a Turing Machine? I am pretty new to Turing Machines and am trying to figure something out. So let's say I have a tape with input

0 0 1 0 0 1

The language is twice as many 0's than 1's. So first time through, I will mark an X on the first 1 I find. Then when I am heading back to the start of the tape, how do I know when to stop? Can you "run" off the left hand side of the tape?

for above example before you start your tape is like this ($e$ means empty and right side of $>$ is block of tape that you are reading it)

e>001001e

as you said you should first mark $X$ on the first $1$ and it become like this

e00>X001e

now you should clear two zeros because the number of zeros is twice of the number of ones. you can clear the first two zero of the tape. go to the beginning of the tape like this (when you read $e$ it means you are at the beginning of tape and go one step to the right so that marker be over the first symbol of tape)

e>00X001e

now you can mark two zeros with $X$ or $Y$ it does't matter but for readability it's better to mark it with another symbol

eY>YX001e

now go back to the beginning of tape

e>YYX001e

now it's like a for loop you should do this until there is no $1$ on the tape. when you got end of the tape while searching for $1$ it means that you ran out of ones. you should check two cases

is number of ones less than twice of zeros
is number of ones greater than twice of zeros

if the first case happens while you are searching for zeros you cant find two of them and you got to the end of tape like below

e>00010111e

become

eYYYXYXY1>e

so in this case you should reject the string.

and checking the second case is in the last step when you ran out of ones you should check that is there any zeros one the tape right now. if you found any zero you should reject.

remember never write empty over $0$ or $1$ because when you reach empty it means you are at the end or the beginning of the tape.

based on definition of Turing Machine you can run off the left hand side or not. there are Turing Machines that their tapes are infinite at the right side and finite at the left side so you can run off at the left side. but standard Turing Machine is infinite at both site so you can run off at the left hand side.


Minimum depth of a leaf in a tree that corresponds to a comparison-based sorting algorithm The lower bound of comparisons in a comparison-based sorting algorithm is $\log_2 n!=Θ(n\log n)$. Yet there can be less comparisons needed in an algorithm.
If you take a sorted array, it will take $n-1 = O(n)$ comparisons (with insertion sort) to sort the array — comparing every adjacent pair of numbers. I don't understand then how is $\log_2 n!=Θ(n\log n)$ the lower bound.

I also don't understand the corresponding trees to the sorting-based algorithms:
each leaf in the tree corresponds to one of the permutations of the $n$ numbers. If the minimum number of comparisons needed is $\log_2 n!$ then the depth of every leaf should be at least $\log_2 n!$, yet I saw that it's possible for a leaf to be with depth of $O(n)$.

Can there be leaves with depth even smaller than $n-1$?

The lower bound is for the worst-case number of comparisons. Every comparison-based sorting algorithm performs $\Omega(n\log n)$ comparisons in the worst case. This means that the tree has depth $\Omega(n\log n)$.

If you don't like the tree argument, here is an adversary argument which is basically a reformulation of the tree argument. We will maintain the set $\Pi$ of all permutations consistent with the answers so far. When the algorithm compares $i$ to $j$, we answer the result which reduces $\Pi$ by at most a half (one of the two answers must have this property). After $\log_2 (n!/2)$ steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least $\log_2 n! = \Omega(n\log n)$ comparisons on this branch.

In fact, we can strengthen this result (going back to the tree argument): every comparison-based sorting algorithm makes $\Omega(n\log n)$ comparisons on average (when the input is a random permutation of $1,\ldots,n$). For the proof, note that there can be at most $2^k$ leaves at depth $k$. In particular, the number of leaves at depth $(\log n!)/2$ is at most $\sqrt{n!}$. Therefore for at least $n! - \sqrt{n!}$ permutations, all leaves are at depth more than $(\log n!)/2$, and for this $1-o(1)$ fraction of permutations, the algorithm will make at least $(\log n!)/2 = \Omega(n\log n)$ comparisons.

Finally, let us show that you cannot possibly know the correct permutation if you perform less than $n-1$ comparisons. Construct a graph whose vertices are the elements of the array, and $(i,j)$ are connected if you compared the elements at these positions. If you make less than $n-1$ comparisons, then the graph won't be connected. In particular, you can partition the vertex set into two non-empty parts $A,B$ such that no element of $A$ was compared to any element of $B$. In particular, there is a permutation consistent with the performed comparisons in which all elements of $A$ are smaller than all elements of $B$, and another one in which all elements of $A$ are larger than all elements of $B$.


How to prove that average complexity is N/2 for linear search in the unsorted array All tutorials on algorithms show the complexity for the linear search in the unsorted array in the average case as N/2. I understand that the average case means the items in the list are randomly distributed.

Can anyone show how I would arrive at N/2 if I have items randomly distributed? Or does it come out of randomly shuffling array bazillion times and recording the number of operations?

First assume input is uniformly distributed. More precisely it is $\frac{n+1}{2}$. When you search for a particular element $x$ in an array of size $n$, that element may be located at the position either $1$, or $2$, $\dots$ or $n$. When we search we check each element in the array and compare it with $x$, and so when we reach $k^\text{th}$ element of the array we have already done $k$ comparisons.

If it is at $1$ then you find it in 1 comparison, if it is at $2$, you find it in 2 comparisons, $\dots$, if it is at $n$ then you do $n$ comparison in order to find it. In order to average it you sum the total number of comparisons $1+2+\dots + n = \frac{(n+1)n}{2}$ and divide it by $n$ (size of the array) resulting in $\frac{n+1}{2}$.

More formal proof:
Assume that the input has uniform probability and the the size of the array is $n$. Let $X$ be a random variable denoting the number of comparisons. Then $p(X=x)$ will denote the probability that we do $x$ comparisons. Since the distribution is uniform, $p(X=x) =\frac{1}{n}$. Once we formally defined our probability distribution now we can calculate the average number of comparisons in the linear search. What we do is compute the expected value
$$E[X] = \sum_{x=1}^{n}{xp(x)} = \sum_{x=1}^{n}{\frac{x}{n}} = \frac{1}{n}+ \frac{2}{n} + \dots +\frac{n}{n} = \frac{n+1}{2}$$


Difference between memory access and write-back in RISC pipeline I'm a little confused about the difference of the memory access and the write-back stage in a RISC pipeline.

We learned in class these following assumptions:

arithmetic & logic: IF, OF, EX, WB
load: IF, OF, EX, MA, WB
store: IF, OF, EX, MA
branch: IF, OF, EX

IF=Instruction Fetch, OF=Operand Fetch, EX=Execution, MA=Memory Access, WB=Write-Back

Lets say we have the following code now:
    I1: LD R1, 0(R2) ; load R1 from address 0 + R2
    I2: ADD R1, R1, #1 ; R1 = R1 + 1
    I3: ST 0(R2), R1 ; Store R1 at address 0 + R2

According to what I've learned I1 will pass all five stages, I2 won't have to access the memory, and I3 won't have a write-back.

But then I wonder, how and where does I3 store the value then? Just in the memory? And I2 fetches the value from memory, but needs to write-back to some place other than the memory? So does that mean that write-back is always to the HDD?

I think I'm missing some core concepts here, as to where the operand is fetched from and where it gets stored to.

In a classic 5-stage RISC pipeline, WB writes a value into a register. If the instruction doesn't write a value into a register (e.g. store), then that stage isn't used.

I1 stores a result into a register (namely R1), so it uses WB.

I2 stores a result into a register (R1) so it uses WB.

I3 does not store a result into a register, so it doesn't use WB.

You basically got it with I3: the store instruction stores to memory, so the "write" is performed inside MA.

Incidentally, on "real" RISC machines, MA tends to be more complex (and multi-cycle) because of multi-level caches and virtual memory. A store instruction may cause a page fault, so in a sense it has a "result" that isn't just the memory access.