DFA/NFA/ε-NFA: subsetting each other or different sets? I know that an ε-NFA (NFA with epsilon transitions) is not an NFA or a DFA and an NFA is not a DFA.

HOWEVER, say you have a complete DFA. Isn't that theoretically an NFA and an ε-NFA? Just because it doesn't have ε transitions, does it mean it is not ε-NFA? If a question asks you to turn a DFA into an ε-NFA, can't you just write the complete DFA as an answer? What properties make DFA different from ε-NFA and NFA?

The same question applies to NFA → ε-NFA, isn't NFA a more "primitive" version of ε-NFA? It's just NFA without the ε...

If I understand your question correctly, you are essentially talking about the syntactic difference between DFAs, NFAs and NFAs with $\epsilon$ transitions.

Well, in a way, every DFA is also an NFA, and every NFA is also an NFA with $\epsilon$ transitions (it just so happens that the former does not use these transitions).
A caveat here is that if you really stick to the standard definitions, then in a DFA the "type" of the transition function returns a state, whereas in an NFA it returns a subset.
This is just a technicality, of course, as you can define a DFA to be an NFA whose transition function only returns singletons.

I would look at things this way:
An $\epsilon$-NFA would be the "standard".
Then, define an NFA to be an $\epsilon$-NFA that does not use the $\epsilon$ transitions.
Finally, define a DFA to be an NFA with a single initial state and a transition function that only returns singletons.

In the comments, you ask about the size of the different models, w.r.t a fixed language. This is an entirely different issue. As it turns out, $\epsilon$ transitions can always be removed, and no new states are introduced in the process, only new transitions.
As for the translation to DFA - this may involve an exponential blowup in the state space.


Distribution of random Fourier coefficients Let $f : \{0, 1\}^{n} \rightarrow \{-1, 1\}$ be a Boolean function. Let the Fourier coefficients of this function be given by
$$ \hat f(z) = \frac{1}{2^{n}} \sum_{x \in \{0, 1\}^{n}} f(x)(-1)^{x \cdot z}$$
for each $z \in \{0, 1\}^{n}$, where $x \cdot z$ is the bitwise inner product between $x$ and $z$. Let me choose a function uniformly at random from the set of all Boolean functions $$\{f : \{0, 1\}^{n} \rightarrow \{-1, 1\}\}. $$
What is the distribution that each Fourier coefficient $\hat f(z)$ is distributed as?

Each Fourier coefficient on its own is the average of $2^n$ independent uniformly random $\pm1$ variables. Its distribution is roughly normal with mean $0$ and variance $2^{-n}$.


Is it Regular Language? According to Wikipedia, Regular Language is Recognized by Some DFAs, or expressed by Regular Expression .. and all finite Language are regular but, not all regular is finite ..

that's mean it may be infinite language is regular ?

my example is L = {a^n b^n+1, n >0 } is it regular ?
it generate infinite set of strings
how to represent it as DFA or a regular expression (can represent this language using RegExp ?).. i can guarantee the exact number, how to automata to maintain the exact number of a's or b's

i tried some grammar, i do not get the regular grammar ..
my grammar looks like

S -> AB

A -> aA | e

B -> bbB | e

final question, how the language is regular and infinite in the same time ?

Here's a derivation in your grammar, assuming that your 'e' denotes the empty string:
$$
S\Rightarrow AB\Rightarrow B\Rightarrow bbB\Rightarrow bb
$$
This is clearly not in $L=\{a^nb^{n+1}\mid n>0\}$. There is, however, a non-regular grammar for your language:
$$\begin{align}
S&\rightarrow AB\\
A&\rightarrow aAb\mid ab &\text{generates $a^nb^n$}\\
B&\rightarrow b &\text{generates the $b$ on the right}
\end{align}$$
There is no regular grammar that will generate $L$, since $L$ is not a regular language.

For your last question, "how can a language be regular and infinite?", you appear to be confused by your observation that any finite language is regular. This is true: logically we'd write this as "If a language is finite, then it is regular."

This does not, however, imply the converse: "If a language is regular, then it is finite." To see this, consider the true statement "If a number is a multiple of 6, then it is even". That's certainly true: 42 is a multiple of 6 and is also even. However, the converse, "If a number is even, then it is a multiple of 6" is certainly false sometimes, since 10 is even but not a multiple of 6. In logical notation, we have that the truth of $P\rightarrow Q$ does not guarantee that $Q\rightarrow P$.

The statement "If a language is finite, then it is regular" just says that the set consisting of finite languages are a subset of the set of regular languages, not that the two sets are the same. For example, the language $\{a^n\mid n\ge 0\}$ is regular (since that language is denoted by the regular expression $a^*$ and also generated by the grammar $S\rightarrow aS\mid \epsilon$) but is obviously not finite.


Formal construction of PDA intersecting a DFA Given the PDA $P = (Q_P,\Sigma,\Gamma_P,\delta_P,F_P)$
and the DFA $D = (Q_D, \Sigma, \delta_D,q_D,F_D)$

What is the 6-tuple definition of the PDA such that: $L(P') = L(P) \cap L(D)$

I don't understand what the intersection of these two FAs represent, and my only guess at what the 6-tuple is would be something along the lines of: $P'=(Q,\Sigma,\Gamma,\delta,q_0,F)$ such that:

$P=Q_P$ x $Q_D$
$\Sigma = \Sigma$
$\Gamma =..?$
$\delta =..?$
$F =..?$

The only other resource on this site I found that is remotely similar to this question is:
Cartesian construction of PDA and DFA

However, I didn't find the answer to be sufficient.

The idea of the intersection is to construct a PDA that keeps track of the original PDA's state in the first component of the state (in the $Q_P$ component) together with the stack, and keep track of the DFA's state in the $Q_D$ component. If both accept by final state, you just need to accept if both automata end up in a final state.


Fixed point, what does it mean in the world of computer science I keep coming across references to fixed point in questions and answers at stackexchange and I look up the meaning on the web obviously finding reference at sites such as Wikipedia. However none of the references really answer my question of what is a fixed point and what does it mean in the world of computer science.

EDIT

After 8 years this finally popped into my head.

How would you explain fixed point to a kindergartner?

A fix point is when you do the same thing again and again and nothing changes. So if your room is messy and you clean it, it is now at a fixed point because if you clean it again it is still clean.

I know there is a joke or comic in there somewhere but I don't have my comedian hat on today.

In computer science, the arguably most prominent use of fixed-points is in lattice theory¹. A lattice is a partially ordered set $(S, \leq)$ with the additional property that given any two elements $x,y \in S$, the set $\{x,y\}$ has both a supremum and infimum (in $S$).

Now you often consider monotone functions $f$ on this lattice which "converge", that is for some $x \in S$ you have $f(x)=x$. Important results in this area are Kleene's fixed-point theorem and the Knaster-Tarski theorem.

A prominent example is the lattice $(2^A,\subseteq)$ for $A$ some set, and $f$ induced by an inductive definition. For example, let $A = \{a,b\}^*$ and we define a language $L \in 2^{\{a,b\}^*}$ by

$\qquad \begin{align}
  \phantom{w \in L} &\phantom{\implies} \varepsilon, a \in L \\
  aw \in L &\implies baw \in L \\
  bw \in L &\implies abw, bbw \in L
\end{align}$

This inductive definition corresponds to the monotone function

$\qquad \displaystyle f(A) = \{\varepsilon, a\} \cup A \cup \{baw \mid aw \in L\} \cup \{abw, bbw \mid bw \in L\}$

By Knaster-Tarski theorem, we know $f$ has a smallest fixpoint which is a supremum of all smaller "intermediate results" (which correspond to finitely often applying the constructors of the inductive definition), and that smallest fixpoint is indeed $L$.

By the way, the largest fixpoint also has uses; see here for an example.

In recursion theory, there is another fixed-point theorem, also due to Kleene. It says²,

  Let $\varphi$ a Gödel numbering³ and $ r :\mathbb{N} \to \mathbb{N}$ a total, computable function (intuition: a compiler). Then there is $i \in \mathbb{N}$ such that $\varphi_{r(i)}=\varphi_i$.

In fact, there are even infinitely many such $i$; if there where only finitely many, we could patch $r$ (by table-lookup) to not have fixed-points, contradicting the theorem.

Everybody uses it every day, even if you don't realise it.
I don't like that Wikipedia article; you are probably better off checking a genre book.
A special kind of function numbering. For intuition, think of it as a (Turing-complete) programming language.


DPDA - a language that contains the same number of A and B I need help with creating Deterministic pushdown automaton for language:
L = {v1w | v, w ∈ {a, b, c}*, #a(v) = #c(w)} where the number "a" in the string v is the same as "c" in the w string.

In the first state, I try to load the first string v. But I do not know how to control the same number of "a" and "c" characters.

Thanks for help

Your language:

L = {v1w | v, w in {a, b, c}* and #a(v) = #c(w)}

The first thing to notice is that bs and cs in the first part of the string can be ignored, whereas as and bs in the second part of the string can be ignored. In the first part of the string, push onto the stack; and in the second part of the string, pop off. You know you've moved from the first part of the string to the second when you read a 1. Reject if you (a) run out of stack before you're done seeing cs in the second part of the string or (b) if you still have stuff on the stack when you're done reading the second part of the string. If you run out of input with an empty stack, accept. Something like this:

Q    s    S    |    Q'    S'
---------------+---------------
// first part of the string
---------------+---------------
q0   a    Z/a  |    q0    aZ/aa
q0   b    Z/a  |    q0    Z/a
q0   c    Z/a  |    q0    Z/a
---------------+---------------
// transition to 2nd part
---------------+---------------
q0   1    Z/a  |    q1    Z/a
---------------+---------------
// second part of the string
---------------+---------------
q1   a    Z/a  |    q1    Z/a
q1   b    Z/a  |    q1    Z/a
q1   c    a    |    q1    -

We can define acceptance to be by empty stack in state q1. If you want a separate accepting state you can add a new one and an empty transition for that purpose, although that results in a non-deterministic PDA. We can get a DPDA with a separate accepting state if we really want to as follows:

read bs and cs in a loop on the initial state (accepting).
if you read an a, go to state A. In state A, read bs and cs in a loop, and if you read as, push as onto the stack.
from the initial, upon seeing 1, go to state E, which is accepting, and loop on bs and cs. Crash on an a, or transition to a dead state.
from A, upon seeing 1, go to state C read as and bs in a loop, and if you read c with an a on the stack, pop the a. If you read a c with Z on top of the stack, transition to B.
state B loops to itself on a and b and crashes, or transitions to a dead state, on c.


Could this be an NP-Complete problem? Consider the following problem statement:

  Given an initial number, you and your friend take turns to subtract a perfect square from it. The first one to get to zero wins.
  For example:

  Initial State: 37

  Player1 subtracts 16. State: 21

  Player2 subtracts 8. State: 13

  Player1 subtracts 4. State: 9

  Player2 subtracts 9. State: 0

  Player2 wins!

  Write a program that given an initial state, returns an optimal move, i.e. one that is guaranteed to lead to winning the game. If no possible move can lead you to a winning state, return -1.

This problem can be solved in pseudo-polynomial time using dynamic programming. The idea is just filling an array of length n (where n is the initial state) bottom up with the optimal moves, or -1 if no move leads to winning. This would take O(n * sqrt(n)) since for every number we need to consider subtracting each possible perfect square smaller than it (there are ~sqrt(n) of them). However, this is a pseudo-polynomial runtime complexity since the runtime actually scales exponentially with relation to the size of the input in binary (# of bits used to represent number).

Can anyone think of a polynomial algorithm for solving this problem? If not, could it be NP-Complete? Why?

The sequence of losing positions can be found in the OEIS, A030193, as is the sequence of positions having Grundy value 1, A224839. The encyclopedia cites several relevant articles. Perhaps some of them discuss non-trivial algorithms for computing the sequence.


Problem in downvote system Problem

For my game, I'm building a system where players have power/weight, and they can downvote each other, players with 66% of downvote weight are banned. The weight of the votes is calculated based on the total weight of the active players, and banned players cannot vote, so the total weight of the system can change during the computation.

Can I make this computation, avoiding infinite loops?

Constraints

The whole system is unveiled simultaneously, players and votes.
I have to compute this on the fly, so I cannot fix the total weight by using the final weight of a previous computation
I absolutely cannot count the banned players' votes, trolls are common
Also because trolls are common, a big percentage of the players can be banned at any point, so I can't either just count them in the final weight even if their actual votes don't count, because the minimum downvote percentage by legit players can grow beyond 100%.

Cases

I already spotted the trivial case of a player with 66%+ weight voting himself down, resembling "this sentence is false", so I disabled that.

But there's also the case where there's N players that together account for 66%+ weight, and where every combination of N-1 players still account for 66%+, and each of those agents downvote each other. So together they downvote each other but at the same time, because all of them are downvoted, all of their votes don't count. It's almost the same as the previous case but way harder to solve and even detect.

However, I think that case is unlikely because most of the players have to conspire for that to happen, or just by chance which is even more unlikely I believe.

I come from a database / transaction background which will influence this answer.

My take would be to serialize the downvotes and handle one at a time. The banned function will be handled this way. Unbanning (is this a Word? ) will need to be handle separately: imagine that a troll is banned, a while later the total weight has increased enough for that player to be undammed.

When a player does a downvote, add the downvote to a queue (or similar). Save the id of the downvoted player, the id of the downvoter and the downvote quotient = downvoter current weight divided by current total weight.
In the serial function handle one item from the queue at a time.
Link the downvote to a list for the downvoted person. If one downvoter has downvoted a person several times, save only the latest. If the downvote player is already banned, nothing more needs to be done.
Now calculate the total downvote quotient by traversing the list. Only sum quotient for currently not banned users.
If the quotient is above 66% ban the user.
Take next item from the queue, see above

Now in order to unban a user you need to have a separate function. It might be a good idea to remove all old downvotes Before unbanning, or perhaps mark them as invalid?


Rounding logarithm to next integer — Potential function The problem is IV-3 of this pdf: potential function.

Defining a potential function as $\Phi(i) = 2i - 2^{\lfloor{\log_2i}\rfloor+1} + 1$

The solution states that if $i$ is not an exact power of $2$, we have:

$$\Phi(i) = 2i - i + 1 .$$

This means that $2^{\lfloor{\log_2i}\rfloor+1} = i$. I'm having some trouble understanding this equality.

Can somebody shed some light?

The analysis there is slightly wrong, though the conclusions are correct. Here is the correct calculation:

$i$ is not a power of 2. In that case $\lfloor \log_2 i \rfloor = \lfloor \log_2 (i-1) \rfloor$ and so $\Phi(i) - \Phi(i-1) = (2i+1) - (2(i-1)+1) = 2$.
$i$ is a power of 2. In that case $2^{\lfloor \log_2 i \rfloor} = i$ and $2^{\lfloor \log_2 (i-1) \rfloor} = i/2$, and so $\Phi(i) - \Phi(i-1) = (2i - 2i + 1) - (2(i-1) - i + 1) = 2-i$.


Use pumping lemma to show L is not context free Show that L = $\{0^{2^n}| n\geq 0\}$ is not a context free language.

Let string $s = 0^{2^p}$. Then we know we can write $s$ as $s = uvxyz$. I know that |vy| > 0 and $|vxy| \leq p$.

So how do I show that $uv^2xy^2z$ is not in $L$.

$\{ 0^{2^n} \mid n \ge 0 \}$ is not context-free.

To show this, you can use any of the usual techniques to show that a language is not context-free, such as the pumping lemma for context-free languages.

The pumping lemma states that if $L$ is context-free, then there exists a pumping length $p$ such that for all $n \ge p$, there exist $u,v,x,y,z$ such that $0^{2^n} = uvxyz$ and $|vy| \ge 1$ and for all $k \ge 0$, $uv^kxy^kz \in L$. Take $n = p$: for all $k \ge 0$, $|uv^kxy^kz| = |uxz| + k |vy|$ must be a power of $2$. This is not possible for large $k$ since it would imply that the distance between consecutive powers of $2$ is never more than $|vy|.

You can also use Parikh's theorem, which states that the set of possible numbers of occurrences of a letter in a context-free language is semi-linear (i.e. it's of the form $\{a p + b \mid a \in \mathbb{N}, b \in B\} \cup C$ for some integer $p$ and some finite sets $B$ and $C$). For a language with a singleton alphabet, this means that the set of lengths of words in the language is semi-linear, which $\{2^n \mid n\in\mathbb{N}\}$ isn't.


Source Coding Theorem: what happen when go below N⋅H(x) bits? I was following the text book by David Mackay: information theory inference and learning algorithms, this could be found online on his website.

I have question on the source coding theorem (emphasis mine):

  Shannon's source coding theorem (p81): $N$ i.i.d. random variables each with entropy $H(x)$ can be compressed into more than $N \cdot H(x)$ bits with negligible risk of information loss, as $N \to \infty$; conversely if they are compressed into fewer than $N \cdot H(x)$ bits it is virtually certain that information will be lost.

My question is the emphasised part of the above, what happens when you go below $N \cdot H(x)$ bits?

There is an example in the textbook (p77), which he shows that, as $N$ increases, the average entropy per symbol approaches $H(X)$, for the risk tolerance between $0< \delta< 1$. (So it becomes more flat as indicate on the diagram).

Therefore,  $N \cdot H(x)$ is the number of bits you can compress no matter how much risk tolerance you are willing to take. In the theorem above, however, it is saying that information will be lost if you go below $N \cdot H(X)$. My question is, how much information will be lost?

For each bit that you compress beyond the entropy limit you lose one bit of information. Keep in mind that this theorem deals with random variables. If you want to know what happens to a specific input then you need a different kind of analysis.


Is Knapsack Feasibility and Knapsack with Unit Values NP-Hard? It is well known that the maximization problem of Knapsack if NP-hard. How about just finding a feasible solution i.e. objective is set to zero?

And also if we set the values to all one (not the weights) in the objective of the Knapsack problem is it still NP-hard i.e. $\max v^Tx$ where $v=(1,1,1..,1)$?

Just finding a feasible solution is in $P$.  The empty set is a feasible solution.  It achieves an objective of zero.  So, the answer to "does a feasible solution exist?" is always "yes!" (to the extent that the question is even well-defined).  Similarly, the answer to "is any solution whose value is $\ge 0$?" is always "yes!".  Thus, those problems are not NP-hard.

When all values are one, there is also a trivial polynomial-time algorithm to find the optimal solution.  You should be able to find it yourself: just try a few examples, and you will quickly discover the trick.


Can every regular expression be written as sum of products? I was trying to prove that Parikh Image of every regular language is semi-linear. Even though it is true for CFL, but this question was about regular languages.
To prove this, I decided to proceed as follows:

Lemma 1: Every regular expression can be written as sum of products with star, i.e., $R = R_1 + R_2+ ... +R_n $ where each $R_i$ is a regular expression not involving any $+$.

Lemma 2: The Parikh image of a language corresponding to a regular expression that doesn't involve any $+$ is linear.

I proved the lemma 2 by induction on the structure of this specific type of regular expression. (which was easy and correct, by the way).

After proving (allegedly) these, it was easy to state that the Parikh image of the language defined by $R$ is just the union of linear sets, hence it is semi-linear.

I proved the lemma 1, again, using induction on the structure of the regular expression, but I am not sure if it is correct. Moreover, I am not sure if the Lemma 1 is even valid or not!

My proof was as follows:

$R = a $ where $ a \in \Sigma$ or $a=\epsilon$. This is already in the same form we required.
$R = R_1.R_2$ . This is also in required form.
$R = (R_1 + R_2).R_3$. Replace by $R_1.R_3 + R_2.R_3$.
$R = (R_1 + R_2)^* $ Replace by $(R_1^*.R_2^*)^*$

Do you think this proof is wrong, or even worse, the statement if wrong!

I think you have to be more careful in the inductive steps, but it seems you basically have the argumentation ready. According to me proper induction would be

  If $R_1$ and $R_2$ can be written as sum of products, then so can
  $R_1\cdot R_2$, $R_1+R_2$ and $R_1^*$.

The proof could be completed as:

If $R_1$ and $R_2$ can be represented as sum of products as $R_1 = R_{11} + R_{12} + ... + R_{1n}$ and $R_2 = R_{21} + R_{22} + ... + R_{2m}$, then:

$R = R_1\cdot R_2$ will be equivalent to ($R_{11}\cdot R_{21} + R_{11}\cdot R_{22} + ... + R_{11}\cdot R_{2m}) + ... (R_{1n}\cdot R_{21} + R_{1n}\cdot R_{22} + ... + R_{1n}\cdot R_{2m})$, by the distributivity of concatenation over union, which is in the required form.
$R = R_1 + R_2$, then $R$ is already a sum of products.
$R = R1^{*}$ can be reduced to sum of products by repeated application of the law: $(R_1 + R_2)^* = (R_1^*\cdot R_2^*)^*$ and distributivity of concatenation over union.

Hence we can write each regular expression as sum of products.

This is called the disjunctive normal form of regular expressions.


Quantum vs classic in NP-hard problems Is there any quantum algorithm (algorithm for quantum computers) for any NP-hard problem that has better runtime than the best known classic algorithm's runtime?

It is conjectured that the complexity of SAT on $n$ variables is $\tilde\Omega(2^n)$ (a version of this is SETH, the strong exponential time hypothesis). In contrast, Grover's algorithm solves it in $\tilde O(2^{n/2})$.

On the other hand, it is conjectured that quantum computers cannot solve NP-hard problems in polynomial time, that is $\mathsf{NP} \not\subseteq \mathsf{BQP}$.


packing with time-variant weights This appears to be a knapsack / bin-packing problem, but I seem to have got stuck and could appreciate contributions.

Scenario 1: Tough (for me!)
There is a one day conference with a set of (4 or more) sessions.
The conference will be attended by a number of companies, each one being represented by a (1 or more) representatives.

Across sessions the number of representatives for each company will vary (and may be zero), with each individual having the same chance of being present as any other individual (so there is an increasing likelihood of a company being represented when it has more representatives).

There is a single row of seats in the conference. There are more than enough seats for the most popular session. (e.g., if the most popular session has 100 delegates, there could be 120 seats for the whole conference).

Constraints

A rep. belongs to one company
A rep. must be seated in a session they are going to.
A rep. must not change seats across consecutive sessions
A rep. is assigned to one chair in each session they attend.

Goal
To fit the constraints and priorities optimally.
Example. 15 chairs, 4 companies (A-D), 4 sessions (S1-S4).

// Session attendees by company
S1: A2 B6 C3 D3
S2: A4 B5 C1 D2
S3: A3 B3 C4 D1
S4: A5 B2 C5 D0

// Possible solution (I did this manually!)
S1: [AA.BBBBBBCCCDDD]
S2: [AAAABBBBBC...DD]
S3: [AAA...BBBCCCC.D]
S4: [AAAAA..BBCCCCC.]

Question
How can I solve this algorithmically?  The algorithm doesn't have to be particularly fast but it does need to yield working results.

Scenario 2: Tougher?!
The same as above but the row of seats has enforced break points (like pillars, walkways, etc).
I think this latter issue is merely a 'knapsack'-type modification to the above problem

Thoughts towards a solution
It seems that it should be possible to have consecutive seating available in most cases, which implies that a solution could be found by identifying company-invariant seats by filling the minimum company representation across all sessions, leaving gaps between companies that are somehow calculated based on the variation of the company and it's neighbour.

It is trivial to find cases where there is only a partial solution, eg the following, but that's okay. I still need to get the best solution I can.

S1:   [AAAACB]
S2:   [ACCCCB]

Edit: I managed to resolve this, using OR-Tools.  It required 3 separate solvers in the end, in order to split the problem into tranches.

Tranche division is done with a solve for the rows, based on a count of seats to work per tranche.
This uses two slack criteria to allow for (a) allocation wiggle room - and (b) one for an overflow (where there are large rows)!

Then a weight-change-over-each-session bin-packing variation to allocate organisations to the tranches.

Finally, seat allocation is managed. The seat allocation can manage about 100 representatives per tranche before it slows down due to scaling problems that seem to be inevitable with constraint programming systems. The constraints are as listed above. eg. for the constraint that one rep belongs to one company:

model.AddImplication(del_chairs[d_tuple], org_chairs[o_tuple])

I'd suggest formulating this as an instance of SAT or ILP, then using an off-the-shelf SAT or ILP solver.  This smells like the kind of problem that might be NP-hard in general and thus it might not be reasonable to expect a general, efficient algorithm that always outputs the optimal solution.

For example, if you only wanted to find a solution that meets all of the constraints, and you ignore the priorities, then you could express this as a SAT instance easily.  You could use a one-hot encoding, where the boolean variable $x_{i,j,k}$ if representative $i$ is assigned to seat $j$ in session $k$.  Then each constraint can be translated into a logical predicate on these boolean variables and thus into SAT.  I find the Z3 solver convenient for expressing these kinds of constraints.

To capture the priorities, you could introduce additional boolean variables, say $y_{i,k}$ is 1 (true) if representative $i$ changes seat after session $k$ or 0 (false) otherwise, and then add constraints to capture the relationship between the $x$'s and $y$'s, and finally minimize the sum of the $y$'s, or require that the sum of the $y$'s be below some threshold $\tau$ and use binary search on $\tau$.  For that, pseudo-boolean inequalities or integer linear programming might be useful.

There are many details that would need to be filled in. I'll let you work out the details.

See, e.g., Express boolean logic operations in zero-one integer linear programming (ILP), Encoding 1-out-of-n constraint for SAT solvers, Reduce the following problem to SAT, When to use SAT vs Constraint Satisfaction?, https://stackoverflow.com/q/43081929/781723 for some relevant reading.  The operations research community and tools (e.g., OR-Tools) might also be relevant.


Construct an equivalent NFA for the given regular grammar Given is the regular grammar G = ({A,B}, {a,b}, P, A) with the rules

P : A → aB, a, ε (where ε is the empty word)
    B → bA, b

  For this regular grammar, create an equivalent NFA.

A regular grammar is a 4 tuple G = (N, Σ, P, S).

So our NFA is made up of 2 states, A and B. The initial state is A and it's also the ending state because the rule says we have the empty word ε in the state A. If we read an a from state A, we go to the state B.
But I don't know what that single a means in the first rule?

From state B, if we read a b, we go to state A. But again, what does this single b mean in this rule?

All in all I would construct the NFA for the regular grammar G like that:

The single $a$ indicates that if we are in state $A$, and read $a$, we must go to an ending state, same with single $b$. If we follow that, we get this automaton :

If we were less prudent, we would argue that if we can generate an $a$ with variable $A$ and stop, and because $A$ is an ending state, then we can put a loop on state $A$ labeled with $a$, like this :

But this automaton doesn't match with grammar $G$. This one recognize strings of the form $a^i$, but grammar $G$ can't generate them.

But something that can be done to lighten our automaton would be to remove state $B_f$, and count on our ending state $A$ to handle the case where we end generation with a single $b$, like the following :

And that actually correct, because we have : empty word on variable $A$, and a rule $B \rightarrow bA$ (In fact, we can remove from $G$ the rule $B \rightarrow b$, because it can be replaced with $B \rightarrow bA \rightarrow \epsilon$).

EDIT : As @rici said, if we apply subset construction to the last automaton, we get this one : (without dead states)

So this is an automaton that matches with $G$.


Name for Turning DAG into redundant tree I am looking for a term:

How is the tree called that you can obtain from a DAG by going top-down and appending all visited nodes to a tree, thereby copying nodes from the DAG into multiple occurences in the tree?

The resulting tree will contain all edges and nodes from the original DAG and a number of nodes multiple times.

A -> B
|    |
v    v
C -> D

Will be turned into:

A -> B -> D
|
v
C
|
v
D

If you need clarifications, please ask.

I am not aware of any standard name for that kind of tree.  One of the wonderful things about language is that we can describe things we don't already have a name for; there are many more interesting concepts than there are pre-existing widely-recognized names.  I recommend that, if you find in your writing you need a concise name for it, you choose a name that seems suitable to you, and define it before first use.


Hardness of boolean functions For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$, $H_{avg}(f)$ is a function from $\mathbb{N}\longrightarrow \mathbb{N}$, termed as the average case hardness, if $\forall$ circuit $C_n$ of size $H_{avg}(f)(n)$, $Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+\epsilon$, $\epsilon >0$.
Similarly, for a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$, $H_{wrs}(f)$ is a function from $\mathbb{N}\longrightarrow \mathbb{N}$, termed as the worst case hardness, if $\forall$ circuit $C_n$ of size $H_{wrs}(f)(n)$, $Pr_{x\in U_n}[C_n(x)=f(x)]<1$.
This I know from the definition of average and worst case hardness. My question is what is the motivation behind these definitions. Can anyone  help?

In the average case, you want the circuit to succeed in computing the function for a large portion of all possible inputs. Since a constant function always succeeds for at least half the inputs (the majority of $f$), the interesting case in where you can achieve advantage which is greater than $\frac{1}{2}$.
In the worst case, you want the circuit to succeed in computing the function for all inputs, so you want to say that $f$ is at least $H(n)$ worst case hard if any circuit of size $\le H(n)$ disagrees with $f$ on at least one input in $\{0,1\}^n$.


Big-O when iterations do not correlate with input Sorry for the perhaps basic question, but my time at university is long ago and I need to brush up on Big-O stuff for interviews.
My question is, what would the time complexity be when an algorithm does depend on the input but not on the size of the input? For example, assume I have this function:
func doSomething(numbers []int) int {
    // find maximum number
    maxNumber := max(numbers)
    for i := 0; i < maxNumber; i++ {
      // magic happens here
    }
}

func maxNumber(numbers []int) (max int) {
     for _,num := range numbers {
           if num > max {
              max = num
            }
     }
     return max
}

How would you define the Time-Complexity of doSomething? The amount of iterations happens to be the maximum number in the input, so if the input is [1000000] we  get 1000000 iterations with input size 1. Yet if the input would be [1,1,1,1,1,....] the iteration would still only be 1 even though our input size would be much greater.
Of course the maxNumber would be O(n) but my understanding is that you would ignore  this in the calculation of doSomething.
I could say O(1) because it's not dependent of the input size, but that seems wrong to me because different input could have different iterations.

The time complexity of doSomething is $O(\max(n,m))$, where $n$ is the length of the input, and $m$ is the maximum number in the input. The letter $m$ is not standard – you can use a different one if you prefer.


What is a good reference for NP hardness in the machine learning/optimization/operations research context? I am reading some papers in machine learning and at the very beginning (introduction) you will see statements of theorems that says, for example:

Theorem 1.1. For any constant ϵ > 0, it is NP-hard to find a
halfspace that correctly labels (1/2 + ϵ)-fraction of given examples
over {0, 1} n even when there exists a monomial that agrees with a (1
− ϵ)-fraction of the examples.
https://people.eecs.berkeley.edu/~prasad/Files/mono.pdf

At this point, the definition of NP-hard is not even defined. I have seen many examples like this, which makes me wonder
"Do all these  thousands of authors have the same definition of NP-hard/complexity notions"?
"These contexts seem so different from the usual contexts where NP-hardness come up such as graph coloring or traveling salesman problem, how can I be sure that these notions of complexity/NP hardness are equivalent?"
Can someone point out a good reference for studying complexity theory in a machine learning/operation research/optimization context? Many thanks!

In modern papers, and unless stated otherwise, NP-hardness is one of the following:

A decision problem is NP-hard if it is NP-hard with respect to many-one reductions.
An optimization problem is NP-hard if its decision version is NP-hard.

Sometimes, more informal notions are used. The most common one is probably hardness of approximation. When a theorem states that maximization problem X is NP-hard to approximate within a factor of $\alpha < 1$, it usually means that there is a many-one reduction from SAT (or some other NP-complete problem) an instance of X and a parameter $k$ such that

If the original SAT instance is satisfiable, then the value of the X-instance is at least $k$.
If the original SAT instance is unsatisfiable, then the value of the X-instance is at most $\alpha k$.

However, to be sure, you need to look at the exact statement being proved.
Your case is similar. The complete version of your paper proves the main theorem in Section 5. Theorem 5.2 on page 21 states exactly what holds in the Yes case and what holds in the No case (Theorem 5.1 shows that it is NP-hard to distinguish the two cases). You should be able to relate this to the informal statement appearing in Theorem 1.1.


How to write recurrence relation for backtracking problem? I am not able to understand how to write a recurrence relation for n queen problem. I searched on web and everywhere it was given directly without explaining how can we arrive to that.
Recurrence relation is for n*n board $T(n)=n*T(n-1)+O(n^2)$ but  think it should be $T(n)=T(n-1)+O(n^2)$ as if we put the queen anywhere in first row, we are left with $(n-1)*(n-1)$ board and it is sub-problem for T(n-1). But how n gets multiplied is not understandable. Can anyone help in explaining such recurrence relation.

Recurrence relation is for n*n board $T(n)=n*T(n-1)+O(n^2)$ but  think it should be $T(n)=T(n-1)+O(n^2)$ as if we put the queen anywhere in first row, we are left with $(n-1)*(n-1)$ board and it is sub-problem for T(n-1). But how n gets multiplied is not understandable.

How many cells are there in the first row? $n$. That is where the factor $n$ come from.

We put the Queen in the first cell of the first row. Removing the first row and first column, we then check the remaining $(n-1)*(n-1)$ board.
We put the Queen in the second cell of the first row. Removing the first row and second column, we then check the remaining $(n-1)*(n-1)$ board.
$\vdots$
We put the Queen in the last cell of the first row. Removing the first row and last column, we then check the remaining $(n-1)*(n-1)$ board.


Managing an hotel using AVL trees - Data Structures I have a Data Structure question where I need to manage an hotel, each room has a number between $1-n$
and it can be occupied or not.

Available Data structures: AVL* Trees, B-Trees, Arrays, Stacks, Queues, Binary Trees.

$O(n)$ Space complexity available.

Using AVL OR B-Tree is a must.

I have to support these functions:

1) $\text{Init(n)}$ : Initializes the data structure with $n$ unoccupied rooms, the indexing of the rooms is $1-n$
this has to work at $O(n)$ time complexity

For the next functions: $l$ and $r$ do not have to be a number of an occupied room-

2) $\text{GetUnOcc(l,r)}$ : Gets $l$ -Left and $r$ - Right (Does not have to be an occupied room number) , 2 numbers that defined a range of numbers and I need to count how many hotel rooms are not occupied between them (Including).  Has to work at $O(\log_2{n})$ Time complexity

3) $\text{GetMinUnOcc(l,r})$ : Gets $l$-Left and $r$-Right, 2 numbers that define a range of numbers, this one adds the person to the hotel at the smallest room that is not yet occupied between $l-r$ (Including).
Has to work at $O(\log_2{n})$ Time complexity

4) $\text{GetOut(r)}$ : It gets a room number and deletes the person from that Room/Hotel, making room number $r$ unoccupied.
Has to work at $O(\log_2{n})$ Time complexity

My Go:

Init: I thought about using an AVL tree with a boolean array.
We initialize it $O(n)$ by just making an array of False (Unoccupied) which takes $O(n)$

GetUnOcc(l,r) : I thought about this formula:
$\text{#UnOcc} = r - l + 1 - \text{Occupied}$  so we need to find how many rooms are occupied between $l-r$ but I am not sure how to do so in $O(\log_2{n})$

GetMinUnOcc is much harder because I cannot determine which value is the smallest, let's say $l=3$ and $r=10$ and every room between $3-8$ and room $10$ are occupied, and I need to return $9$ (because it is the smallest which is not occupied)

Let's say I have this tree (as Steven suggested to build an AVL of unoccupied rooms) so in this matter it is $\text{Init(10)}$  And Now I want to do $\text{GetMinUnOcc(5,7)}$ so it should delete $5$ from the tree as it will become occupied. But in what you suggest, we find the successor of $l=5$ which is his parent, $6$ and delete it, but, $5$ is not occupied and we want to return the minimum so we need to actually delete $5$, where am I wrong?  Thank you!

I would appreciate your help / hints to solve this hard question! Thank you!

Maintain an AVL tree $T$ containing the indices of the unoccupied rooms. For each vertex $v$ of the tree additionally maintain the number $\eta(v)$ of vertices in the subtree of $T$ rooted at $v$.

1) Init: create an AVL tree with keys $\{1, \dots, n\}$. This requires $O(n)$ time.

2) GetUnOcc($l$, $r$): Find the vertex $u$ associated with the successor of $l$ in $T$ (possibly $l$ itself). Find the vertex $v$ associated with the predecessor of $r$ in $T$ (possibly $r$ itself). If the key of $u$ is larger than the key of $v$ return $0$. Otherwise find the least common ancestor $w$ of $l$ and $r$. Initialize the number $x$ of unoccupied rooms to $0$.
Walk from $u$ (inclusive) to $w$ (exclusive). Whenever you encounter a vertex $z$ such that $z=u$ or the previous vertex in the walk was the left child of $z$, let $z'$ be the right child of $z$ (if any) and add $1 + \eta(z')$ to $x$ (if $z'$ does not exist then add $1$ to $x$).
Walk from $v$ (inclusive) to $w$ (exclusive). Whenever you encounter a vertex $z$ such that $z=v$ or the previous vertex in the walk was the right child of $z$, let $z'$ be the left child of $z$ (if any) and add $1 + \eta(z')$ to $x$ (if $z'$ does not exist then add $1$ to $x$). Return $1+x$.

3) GetMinUnOcc($l$, $r$): Search for the vertex $u$ associated with the successor of $l$ in $T$ (where the successor of $l$ might be $l$ itself).
If the key of $u$ is at most $r$, delete $u$ from the tree subtract $1$ from the values $\eta(z)$ of all proper ancestors $z$ of $u$.
Otherwise all rooms between $l$ and $r$ are already occupied.

4) GetOut(r): Insert a new vertex $z$ with key $r$ into the tree with $\eta(z)=1$. Increment by $1$ the values $\eta(z')$ of all the proper ancestors $z'$ of $z$.


Does my Algorithm Qualify as MergeSort? I've been trying to internalize some of the basic sorting algorithms recently, and to do so I've been looking at their wikipedia pages to refresh myself with how they work, and then coding my own "version" of the algorithm from there.

I did this with MergeSort recently, and I got an algorithm that for what I can tell works but I'm not sure it runs in O(nlogn) time like MergeSort does.  Here's my code, it's in Python:

def mergeSortAlgorithm(x):

    listOfLists = []

    for i in range(len(x)):
        temp = [x[i]]
        listOfLists.append(temp)                          #I first put every item in the array into
                                                      #its own list, within a larger list -> divide step

                                                      #so long as there is more than one sorted list, then we need to keep merging
    while(len(listOfLists) != 1):
        j = 0

                                                      #for every pair of lists in the list of lists, we need to merge them
        while(j < len(listOfLists)-1):
            tempList = merge(listOfLists[j], listOfLists[j+1])
            listOfLists[j] = tempList
            del listOfLists[j+1]                          #I shift the new list to index j, and delete the second list from the now-merged pair at index j+1
            j = j+1                                       #increment the value of j, basically a counter
        print(listOfLists)

    print(listOfLists[0], "is sorted!")

def merge(a, b):                                          #function to merge two lists in order
    newList = []
    count1, count2 = 0, 0

                                                      #basically, walk through each list, adding whichever element is smallest
    while((count1 < len(a)) and (count2 < len(b))):

        if(a[count1] > b[count2]):
            newList.append(b[count2])
            count2 = count2 + 1                           #update the counter along b

        elif(a[count1] < b[count2]):
            newList.append(a[count1])
            count1 = count1 + 1                           #update the counter along a

        elif(a[count1] == b[count2]):                     #if they're equal, add the value from a first
            newList.append(a[count1])
            newList.append(b[count2])
            count1, count2 = count1 + 1, count2 + 1       #update the counter on each

    if(count1 < len(a)):                                  #if the while loop exited with left-over values in a, add them
        for f in range(count1, len(a)):
            newList.append(a[f])
    elif(count2 < len(b)):                                #do the same for b - the values are already in order so you're good
        for k in range(count2, len(b)):
            newList.append(b[k])

    return newList

The algorithm correctly sorts what I give it, but I'm thinking that the runtime is more like $O(\log n\cdot \log n\cdot n)$ because the outer while loop in mergeSortAlgorithm() will do $\log n$ passes, as will the inner while loop, and the merge() algorithm will take in total $n$ operations.

Is that right?  If so, in what respect does my algorithm differentiate from MergeSort?  (i.e. where am I going wrong?)

Thanks so much for your help, please let me know if you have further questions I can help explain.

I agree in principle with the comment suggesting that a recursive implementation would be simpler to analyze, and the other comment mentioning that there is no "legal" definition of such an algorithm like merge sort.

However, I think you've done yourself a favor (in terms of your learning objectives) by attempting to implement this bottom-up (rather than top-down), iterative (rather than recursive) merge sort, which is essentially what you have above. I think this shows good understanding on your side. Perhaps you can attempt to implement an in-place version, rather than creating a newList (etc.).

Typically, you would divide the input into two equal parts, sort each, and then merge. Instead, you start "at the leaves" and progress up the chain -- merging singletons, then merging pairs, then merging pairs of four items, etc. Each iteration of your loop "looks like" a particular depth-level in the recursive tree of typical merge sort.

That said, your delete-based approach isn't the most suited for arrays (which, it seems, CPythons lists are under the hood -- a Google search found this) at all in terms of cost. You should be able to fix this, but when doing so, be careful to handle non-power-of-two input sizes.


Find and sort 2d array elements like radar I don't know relevant keywords about this algorithm.
I can show you visually

Any ideas are appreciated

For each of your points in the field, calculate the red angle:

Then sort all the (point, angle)-tuples by the angle.


Proof that $A^* - \{x\} = A^+$ such that $A=\{a,b\}$ and $x \in \{a,b\}^*$ Exercise 1.1 (2) from Problem Solving in Automata, Languages, and Complexity by Du and Ko. P.7. the question is as following:

  Let A be a langauge over {a,b} and $x \in {a,b}^*$. Find necessary and sufficient conditions in terms of x and A for the equation:
  $$A^* - \{x\} = A^+$$

thus, by substation:
$$\{a,b\}^* - \{\{a,b\}^*\} = \{a,b\}^+$$

Now this the LHS should equal to $\{a,b\}^*$ because if we have two sets A and B, then $A \cap B = \phi$, then $A-B=A$. Now where is wrong?!!

I'm also trying to prove from RHS since this is equality to proof should be from both direction.

Your problem is that in going from $A^*-\{x\}$ to $\{a,b\}^*-\{\{a, b\}^*\}$ you went a step too far. In the first expression, $x$ is a single string over the alphabet. Replacing that with the general expression $\{\{a,b\}^*\}$ is incorrect, if for no other reason that $\{\{a,b\}^*\}$ is a set consisting of a set of words and not a single word.

To complete this answer, see newbie's comment on your original post.


In the learning theory version of Occam's razor, why can't I just declare whatever hypothesis I want to be "shortest"? Occam's razor states that shorter explanations (formally speaking, hypotheses) are more likely to be correct. Indeed this can be formalized: for a hypothesis class $\mathcal H$ one may ascribe representations to each hypothesis and take their literal length as strings. The shorter ones are more correct. But the problem is I can just rearrange the language to make perverse hypotheses shorter, at which point they will be more likely. This seems contradictory. What gives?

There are several ways to formalize Occam's razor in learning theory, and they yield theorems that are powerful. However, these theorems do not obviate the need for inductive bias, nor do they create it. That would be like asking a computer program to create entropy. They do not create the ghost in the machine. What they do provide is a way to formalize inductive bias and provide useful theorems for what one may conclude about a set of hypotheses weighted with inductive bias.

If you get "lucky" and the inductive bias you encode happens to match the real world - which you believe is prone to happen if you subscribe to Occam's razor out-of-universe - then the theorems will do a very good job of teasing out the matching hypothesis and will even know how to make tradeoffs between good, short hypotheses and excellent, less-short hypotheses. They will then provide a bound on the error.

What if you are living in a Kuhnian paradigm shift and you are not sure which of two sets of inductive biases is better? Will Occam's razor help you? Yes and no - if you have twice the data you can study both just as before but "twice the data" is of course asking for more information to enter the system. So they cannot magically decide between Newton and Einstein.

One presentation of Occam's razor, from Understanding Machine Learning as Theorem 7.7 is the following. It is a weaker presentation in that it is designed for nonuniform agnostic PAC learnability, which is quite weak, in that no perfect hypothesis can ever be returned. So the conclusions will also be weak.

  Let $\mathcal H$ be a hypothesis class and let $d:\mathcal H \rightarrow \{0,1\}^*$ be a prefix-free description language for $\mathcal H$. Then, for every sample size $m$, every confidence parameter $\delta > 0$, and every probability distribution $\mathcal D$, with probability greater than $1 - \delta$ over the choice of $S \sim \mathcal D^m$, we have that $$\forall h \in \mathcal H, L_{\mathcal D}(h) \leq L_S(h) + \sqrt{\frac{|h| + \ln(2/\delta)}{2m}}$$ where $|h|$ is the length of $d(h$).

This gives rise to the Minimum Description Length learning paradigm: For $\mathcal H, \mathcal D, d$ as above and a loss function, output the hypothesis $h$ that minimizes $L_S(h) + \sqrt{\frac{|h| + \ln(2/\delta)}{2m}}$, i.e. the empirical loss plus the estimation error given by the theorem.

So by itself the theorem isn't making any claim about which hypothesis is best. It's actually making a much more boring claim that short hypotheses are easy to estimate well. It is possible to estimate a hypothesis $h$ up to an error factor of $O(|h|^{1/2})$ (where $O$ holds $m,\delta$ constant), and moreover, it is possible to do this for all hypotheses simultaneously. You can get each and every error estimate and only degrade the quality of the estimate in $O(|h|^{1/2})$.

Now I will convince you this is not trivial. Bear in mind at the other extreme, if you have a single hypothesis $h$ and you want to estimate its error, that's actually really easy to do on a small number of examples. It's the question of determining the weight of an unbiased coin by flipping it a few times, which is given by the Hoeffding/Chernoff bounds. Spoiler alert, you can achieve an estimation error of $\sqrt{\frac{\ln(2/\delta)}{2m}}$ with probability $1-\delta$. In above notation, that's $O(1)$ in $|h|$. All you were trying to do in the Theorem, for all $h$ equipped with some length function, is estimate the error and you achieved $O(|h|^{1/2})$ but here you achieved $O(1)$. What gives?

Let's try estimating for $1000$ hypotheses and try to achieve an estimation error of $10\%$ with probability $99\%$ just by using a simple Hoeffding bound. We calculate we need $265$ examples to achieve this. Not bad. So the first hypothesis we estimate within $10\%$ with probability $99\%$. The second hypothesis we estimate within $\10\%$ with probability $99\%$. But wait, that means the probability that either may fail could exceed $1\%$. By basic probability we only know the probability both estimates succeed is at least $98.01\%$.

And that's not good, because we have 1000 hypotheses. $.99^{1000}=0.004\%$. Not good. And in the context of machine learning, if one hypothesis is estimated wrong, very often the hypothesis is an overfitter. So one failure is enough to ruin the whole model.

So if you do want to estimate 1000 hypotheses simultaneously, you will need many more examples (not too bad -- $\ln(2/\delta)$ does not grow too fast in $1/\delta$) to achieve this.

And if you have infinitely many, you simply cannot do it by naive application of the Hoeffding bound.

So the Theorem lets you achieve an $O(|h|^{1/2})$ estimation error for all hypotheses simultaneously. This is powerful.

What if you try to rig the game and take a complex hypothesis and rig it so its length is just $1$? Then you will get a good estimate for this hypothesis and a worse estimate for many others. The estimation error power is conserved. If you were interested in that hypothesis, you may have also just drawn 265 (or however many) examples and run a Hoeffding bound on it. This is no different.

And if you want to try two totally different schema, you may do exactly that, but you will need a tighter $\delta$ to assure that both succeed. This is a serious mistake you can make when running a machine learning algorithm!

The MDL learner makes no guarantees about returning the best hypothesis. It guarantees to return one that solves a particular set of bounds. That particular set of bounds incorporates "out of universe" Occam's razor, your own inductive bias as the learner or programmer or source of entropy, and will formalize that inductive bias into a set of bounds that will focus more attention onto "simpler" hypotheses, and if your inductive bias is on track, they will output aggressive error bounds on the hypothesis. I reiterate this is the nonuniformly PAC learnable model, so it's too much to ask for a guarantee on the resulting hypothesis. In that sense MDL is weak, as it must be.

A finite PAC formulation of Occam's razor is:

  Fix $\mathcal H$ and fix $\epsilon, \delta$. Suppose there exists a finite $\mathcal L \subset \mathcal H$ with the following property: Take $m \geq \frac1\epsilon(\ln|\mathcal L| + \ln(\frac1\delta)$.  If for every $S \sim \mathcal D^m$ there is an $h \in \mathcal L$ so that $h$ is consistent with $S$, then $h$ is $\epsilon$-accurate and $\delta$-confident, so $\mathcal H$ is PAC learnable with this algorithm.

i.e. if a small hypothesis class can consistently represent pretty large sets of examples, then it is PAC. This is another version of Occam's Razor that, being in a PAC setting, is stronger than the nonuniform PAC discussion above: if the hypothesis class is surprisingly rich for how surprisingly small it is, then it actually describes the world accurately. But it demands a lot, as a real-world machine learner would be pressed to find a noiseless set of data that clean, and I'm not sure if this particular "Occam's razor" theorem generalizes to harsher terrain.


RAM can be accessed hundreds of times faster than a hard drive. Explain How? I have been reading this for quiet a long time that "RAM can be
accessed hundreds of times faster than a hard drive".
But, no one has been able to explain it properly.
I searched on Internet and found that "Access time of RAM is faster because they have less addresses(~4GB RAM) than Hard Drive(~1TB), and therefore address-resolution is faster".

Please guide me on this topic.

Wikipedia has great information on this topic, but as a brief, simplified explanation, know that it boils down mainly to the involvement of mechanical moving parts in a traditional Hard Disk Drive (HDD).

The size of the addressing space in itself doesn't affect the access times. Otherwise you could theoretically build a very small hard-disk drive with only 4GB and expect it to run just as fast as your RAM chip. In reality that  is not possible.

Hard Disk Drives

All the data is read and written by the read and write heads, laying on the round disks that physically store all the data. Whenever data in a specific address is specified, the heads must move to the correct track (the time it takes is the Seek Time) and the disk must rotate until the requested sector is under the head (Rotational Latency). The time until both of these tasks are completed is the Access Time, and only then the data transfer can actually start.

A - Track ; C - (Track) Sector

RAM

In contrast, RAM cards have no such mechanical moving parts and therefore the time constraints are much lower. They are mainly there to allow proper synchronization of the electronic components that comprise the memory card and ensure that it works reliably.

SSD

You probably also heard of the term Solid State Drive (SSD). Seagate recently manufactured such a drive with 60TB capacity, and its access times are still much shorter than those of hard-disk drives. How? Like RAM chips, they have no moving parts.


Directed cyclic graph with node rewards and arc costs The problem I have seems fairly simple and I feel it must have some kind of name. I have a (directed cyclic) graph. Each node has an associated reward for visiting it, and each arc costs a certain amount of time to traverse it.
The reward is consumed on visiting once, so a path may visit a node multiple times but receives 0 reward for future visits.

Is there an algorithm for maximising the reward while proceeding from node A to node B (or back to A again) in a given maximum amount of time available?

Note that the times and rewards cannot be combined as a single "weight".

The data is sparse and isn't that big: a few hundred nodes which typically have less than 5 arcs each.

Any tips on modelling and/or algorithms greatly appreciated.

I think this problem is NP-Complete via reduction to Knapsack Problem

An instance of the Decision Problem involves: a  Graph g, time alloted, sum_reward, and two nodes s,t
: Is there path from s to t with sum of rewards>=sum_reward within the alloted time period?

Reduction

Add nodes $s,t$ and an edge $s->t$ with reward,weight =0.
For every item a=(value(a),weight(a))
create a node  $n_{a}$ and the following two edges:

$e_{a}= s->n_{a}$ with $reward(e_{a})=value(a)$ and $cost(e_{a})=weight(a)$
$e_{b}= n_{a}->s$ with both values zero

I just noticed that rewards are on nodes instead of edges. But  this does not change the reduction(just transfer reward from edge to node)

Now run the algo for input ($G',knapsack$ $size$,$sum$ $reward,s,t$)$

IFF proof

=> if knapsack is feasible, simply iterate over edges of nodes contained in the knapsack and finally hop from s to t. This will give the desired sum_reward

<= More or less, the same idea.

I hope this helps you somehow :)

Since your data is kind of special, perhaps someone can provide  an exact algorithm instead of an approximation one. I cannot (yet :P)


Operation on two CFLs which results in a non-CFL Suppose we have two context-free Languages $L_{1}$ and $L_{2}$, and we form a new language $L_{3}=L_{1} \circ L_{2} = \{\alpha\beta | \alpha \in L_{1},\beta \in L_{2},|\alpha|=|\beta|\}$. Is it possible that $L_{3}$ is not context-free?

Let's denote your operation by $\diamond$, so the question is, if $L_1$ and $L_2$ are CFLs, is $L_1\diamond L_2$ always a CFL? The answer is no.

Let $L_1=L_2=\{0^n1^n\mid n\ge 0\}$. This is, of course, a CFL. However,
$$
L_1\diamond L_2=\{0^n1^n0^n1^n\mid n\ge 0\}
$$
and it's not too hard to show that this language is not context-free.


Quicksort Time Complexity I am learning the Quicksort algorithm and I am struggling with understanding the time complexity.

Here is the JavaScript ES6 code for the partition function that is used in the algorithm:

let partition = function(arr, low, high) {
  let pivotValue = arr[low];
  let i = low;
  let j = high;

  while (i < j) {
    while (i <= high && arr[i] <= pivotValue) {
      i++;
    }

    while (arr[j] > pivotValue) {
      j--;
    }

    if (i < j) {
      // swap arr[i], arr[j]
      let temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }

  arr[low] = arr[j];
  arr[j] = pivotValue;

  return j;
};

I read that there is n work done for a single invocation of the partition function because there is n - 1 work being done in the while loop and 1 unit of work being done when copying the pivot back.

I don't understand why there is n - 1 work done in the while loop. As per my understanding, every time you make a comparison between the array value and pivotValue (arr[i] <= pivotValue or arr[j] > pivotValue), that is a unit of work being done.

So aren't there actually n units of work being done in the while loop, for a total of n + 1 in the partition function?

The number of "work" being done, should be counted with the big-O notation. This means - that you count the while loop as $O(n)$  and any other constant work done (for example, the work after the while) is $O(1)$ and $O(n)+O(1)=O(n)$ so it wont make a difference.

Counting the "work" without big-O is not well-defined in the general case - so you should avoid it altogether


Prove multiple cell move instructions don't increase power of Turing Machines How can you prove that multiple-cell-move instructions, for example (X, Y, 5R) and (X, Y, 17L), do not increase the power of a Turing Machine?

A quick answer: the control of every TM is finite, so given a TM $M$, the jumps in its transition table are finite. Suppose that it has the following jump transition:

on state_x: if read symbol a -> write b, jump 3R, goto state_y

then you can simulate it using 3 single step transitions :

on state_x: if read symbol a  -> write b, move R, goto state_x2
on state_x2: if read symbol <anysymbol> -> write <anysymbol>, move R, goto state_x3
on state_x3: if read symbol <anysymbol> -> write <anysymbol>, move R, goto state_y

In general if $len$ is the length of the jump of a transition, you can simulate it adding $len-1$ new states to $M$ and the new states are used simply to move the head for $len-1$ more steps and finally enter the same target state of the original jump transition.

To be pedantic, you need to add additional states only for distinct triples (jump length, jump direction, target state). For example if a transition has (jump 5, right, and goto state z) the added single step states can be reused on every transition with the same value of jump  length, jump direction and target state.


Prove Vertex-Cover of maximum degree 3 is NPC This is a homework question. I need to prove that the following language is in NP Complete:

  3-VERTEX-COVER = $\{\langle G,k\rangle \mid$ G is an undirected graph, each vertex in $G$ has at most $3$ incident edges, and there is a vertex cover of size $k$ in $G\}$

Showing that it is in NP is easy. Now, to show that it is in NPC I thought about showing a reduction from Vertex-Cover. But I can't seem to think of what to do with a graph I get as <G,k> which is in Vertex-Cover, to make each vertex degree at most 3 without changing the vertex-cover property. Any hints?

Hint: Here is how to handle vertices of degree 4 (taken from Alimonti and Kann).

Let $v$ be a vertex of degree $4$, with neighbors $x_1,x_2,x_3,x_4$. Replace $v$ with a path $v_1-w-v_2$ and connect $x_1,x_2$ to $v_1$ and $x_3,x_4$ to $v_2$ (arbitrarily). A vertex cover in the original graph containing $v$ corresponds to a vertex cover in the new graph containing $v_1,v_2$. A vertex cover in the original graph not containing $v$ corresponds to a vertex cover in the new graph containing $w$. In total, we get that the original graph has a vertex cover of size $k$ iff the new graph has a vertex cover of size $k+1$.

The same idea works for vertices of higher degree.


Decidability of Unary Languages / One-to-One Mapping I'm trying to prove that there exists an undecidable subset of {1}* by showing a one-to-one correspondence between it and {0, 1}* (which would imply a one-to-one correspondence between their power sets), but I'm struggling with how to do the one-to-one mapping. Isn't it just surjective? That is, there's one unary representation of potentially many binary strings (e.g., 1 = 01 = 0000000000001).

What am I misunderstanding here? Or am I just taking the wrong overall strategy?

(This isn't homework; I'm reviewing for a midterm, and it's a little concerning I'm getting tripped up here)

Instead of mapping the string $x\in\{0,1\}^*$ to $1^{\mathrm{bin}(x)}$ (where $\mathrm{bin}(x)$ is the number denoted by interpreting $x$ as a string in binary, map it to $1^{\mathrm{bin}(1x)}$. Now every string in $\{0,1\}^*$ maps to a unique number of $1$s.


Question about a semi-decidable property of languages Consider the following property of recursively enumberable (RE) languages

$$ L = \{ J \in \text{RE} \mid J \cap L_{uni} \ne \emptyset \}$$

where $L_{uni}$ is the language of the Universal Turing machine.

I am wondering if $L$ is semi-decidable. That is (by definition) if the set $$ S = \{ \langle T \rangle \mid L(T) \in L\}$$ is recursively enumerable.

If I am not mistaken then this should be true because one can always construct a Turing machine $M$ that accepts a code $\langle T \rangle$ and  (using non-determinism) generates the "right" input for $T$ and $T_{uni}$, verifies that both accept the generated word (simulating the machines) and if so accepts the supplied string.

Can someone verify this claim?

Let $M$ be any computably enumerable set and define the set $$J_M = \lbrace n \in \mathbb{N} \mid W_n \cap M \neq \emptyset\rbrace,$$
where $W_n$ is the $n$-th computably enumerable set. Then $J_M$ is a computably enumerable set because
$$m \in J_m \iff W_n \cap M \neq \emptyset \iff \exists m . m \in W_n \land m \in M$$
is obviously a semidecidable condition, as c.e. sets are closed under finite intersections and  existential quantification over $\mathbb{N}$.

We may now get your result by taking $M = L_{\mathrm{uni}}$.

If you are wondering about the "obviously semidecidable" condition, we can put in a bit more details: to semidecide whether $W_n \cap M \neq \emptyset$ just keep enumerating the elements of $W_n$ and $M$ in parallel, until an $m$ appears in both enumerations.


Given a r.e. (recursively enumerable) language, L, how many Turing machines semi-decide L? $L\subseteq \{0,1\}^*$

Since the language is r.e. there is definitely at least one Turing Machine that semi-decides the language. I'm thinking that if you have one Turing Machine that semi-decides the language, you can arbitrarily extend this Turing Machine (by adding redundant states), which means there are a countably infinite number of Turing Machines that semi-decide L. Does this reasoning sound right, or does the answer depend on what the language L is?

You are correct.

One can always add redundant states to obtain different Turing machines deciding (or semi deciding) the same language. This yields countably infinite Turing machines deciding $L$ (for any decidable $L\subseteq \Sigma^*)$.


Determine whether a flow can satisfy node demands in a directed acyclic graph I have the following problem that I'm unsuccessfully trying to solve:

I have a directed graph with node demands. Unlike circulation with demands, these node demands do not "subtract" from the flow - the nodes merely demand that there would be a flow of strength k flowing through them. The graph is acyclic, however, it is not a tree - multiple routes exist from the higher to the lower nodes.

The question is, whether a flow of strength R can satisfy all of the nodes' demands. Of course, a flow with strength more than k can flow through a node with demand k. Also, there are no capacity limits in the input graph.

I need to reduce this problem to the max-flow problem. I have been trying to reduce it to Circulation with lower bounds and Circulation with demands, but unsuccessfully, as I am unable to find out a good way on how to somehow limit the flow in the nodes to be minimal while satisfying the demands and measuring it at the same time.

Add a new source $s'$ and the edge $(s', s)$ with maximum and minimum capacity $R$.

For each vertex $v$ with demand $d$ do the following:

Replace $v$ with two vertices $v_1$ and $v_2$.
Replace all the former edges $(u,v)$ with $(u, v_1)$
Replace all the former edges $(v, u)$ with $(v_2, u)$.
Add the edge $(v_1, v_2)$ with minimum capacity $d$.

The problem is now equivalent to checking whether there exists a feasible flow in a network with minimum and maximum edge capacities.

This problem is well known and can be reduced to max-flow (see, e.g., "Balances and Pseudoflows" in the book Algorithms by Jeff Erickson).

Essentially, if $D$ is the sum of all the edges' minimum capacities:

Add a new source vertex $s^*$ and a new target vertex $t^*$.
Add the edge $(s^*, s')$ with maximum capacity $+\infty$.
For each edge $(u,v)$ with minimum capacity $c \neq 0$ and maximum capacity $C$, add the edge $(u, t^*)$ with capacity $c$, the edge $(s^*, v)$ with capacity $c$, remove the minimum capacity from $(u,v)$, and change the maximum capacity of $(u,v)$ to $C-c$ (if $C$ was $+\infty$ then the new capacity is also $+\infty$).
Check whether the maximum flow from $s^*$ to $t^*$ is equal to $D$.


Confusion about compiler and assembler I have two questions.

After compilation of any C program result is assembly language code which should depend on processor. So my question is: how do different computers with different processor types, for example Intel i3,i5,i7 etc., are able to run the same software, for example, media-player, browser, etc.?
(I guess strangely it depends on Operating System) and on that software site they do not ask for processor type.
Do programs interact with any part of operating system for conversion of assembly code to machine code?

Regarding your first question, the Core i3, Core i5 and Core i7 share the same instruction set, apart for a few marginal instructions. In particular, there is backward compatibility, and so code that works for Core i3 would also work for Core i5 and Core i7 (unless it uses some undocumented behaviours, or specifically tests for the processor version). However, to get superior performance, optimizers need to know the exact target processor, and special instructions should be utilized. This can be handled in at least two ways: (1) crucial functions could have several versions, depending on the processor (either completely different versions or just different optimizing parameters), (2) libraries are used which implement the previous approach.

Regarding your second question, the operating system is usually relied on for handling files, so yes, even an assembler needs to interact with the operating system.


Understanding CLIQUE structure I am working on the following problem:

Recall the definition of a complete graph Kn is a graph with n vertices such that every vertex
is connected to every other vertex. Recall also that a clique is a complete subset of some graph.
The graph coloring problem consists of assigning a color to each of the vertices of a graph such
that adjacent vertices have different colors and the total number of colors used is minimized. We
define the chromatic number of a graph G to be this minimum number of colors required to color
graph G. Prove that the chromatic number of a graph G is no less than the size of a maximal
clique of G.

So far, I have been thinking about the problem and came up with the following:

In a clique, every vertex is adjacent to every other vertex
Therefore, since the problem states adjacent verteces always have different colors, the number of colors needed would be the number of verteces in the clique
Thus, the chromatic number of any graph G has to be at least the maximal size of the clique, per the definition of a clique.

Can someone verify if my understanding is correct? Or am I glaringly not understanding a clique?

Your understanding is right. So in particular, for any graph $G$ with a clique of size $k$, you will need at least $k$ colors to properly color it. In case this is not obvious, you can think about it via a contradiction. So assume $G$ contains a clique of size $k$, and you have a proper coloring with less than $k$ colors. It follows that the clique contains at least two vertices with the same color. By definition of a clique, these two vertices are adjacent. But this is a contradiction to the coloring being proper.

Further, one might also wonder if the chromatic number of a graph would always equal the clique number. In this direction, you can have a look at perfect graphs for which the chromatic number of every induced subgraph equals its clique number. On the other hand, the Mycielski graphs show that there are graph that don't even contain a triangle (equivalently, a clique on 3 vertices), while the chromatic number can be arbitrarily large.


On the exponential hierarchy? We know $P\subseteq PH\subseteq PSPACE\subseteq EXP\subseteq NEXP$.

Is it known or believed that $\Delta_2^{exp}=EXP^{NP}\subseteq NEXP=\Sigma_1^{exp}$ and/or $EXP^{PH}\subseteq NEXP$?
Does $NP=coNP\iff NEXP=coNEXP$ hold?

Note $NEXP=coNEXP\implies \Delta_2^{exp}=\Sigma_1^{exp}$?

1) Both two unbelieved scenarios that $\mathrm{NP}=\mathrm{P}$ and $\mathrm{NP}=\mathrm{EXP}$ implies that $\mathrm{EXP}^\mathrm{NP} = \mathrm{NEXP}$ and $\mathrm{EXP}^\mathrm{PH}=\mathrm{NEXP}$. So we cannot refute these two claims at present.

On the other hand,

assuming $\mathrm{EXP}^\mathrm{PH}=\mathrm{NEXP}$ would imply $\mathrm{BPP}\neq\mathrm{NEXP}$, since $\mathrm{BPP}\subseteq\Sigma_2^{p}$ and $\Sigma_2^p\subsetneq\mathrm{\Sigma_2^{exp}\subseteq\mathrm{EXP}^\mathrm{PH}}$
assuming $\mathrm{EXP}^\mathrm{NP}=\mathrm{NEXP}$ would imply $\mathrm{P}^\mathrm{NP}\neq\mathrm{NEXP}\cap\mathrm{co}-\mathrm{NEXP}$

2) First of all, your implication that $\mathrm{NEXP}=\mathrm{co}-\mathrm{NEXP}\implies\Delta_2^{exp}=\Sigma_1^{exp}$  is not known since exponential-time hierarchy does not possess the upward collapsing property like polynomial-time hierarchy (some inner collapse at some level does not necessarily imply the collapsion of all the exponential-time hierarchy to that level).

Beside from that, $\mathrm{NP}=\mathrm{co}-\mathrm{NP}\implies\mathrm{NEXP}=\mathrm{co}-\mathrm{NEXP}$ is true by standard translation technique, but the opposite implication is not known due to the difficulty in achieving the downward closure theorems for non-determinism and co-non-determinism. It has been done for probabilistic classes (zero-sided, one-sided, bounded-error all done, but general probabilistic $\mathrm{PrTime}$ still open). For more details on downward closure theorems, see the reference in this answer.


Are these two algorithms the same? An algorithm is a finite sequence of operations on an abstract machine. (Correct me, if I am not correct).

If two algorithms can take the same set of inputs, and for each input, they generates the same sequence of intermediate and final results/output, are they the same algorithm?

What I am thinking is if an algorithm can be thought of just as a mapping from the set of inputs to the set of sequences of intermediate and final results/output.

Thanks.

Starting with a vague definition of algorithm, you won't get a clear-cut answer. Here are two possible ways to look at it.

Algorithms are high-level constructs, that is we distinguish idea from implementation. In that sense,

for ( i=1; i<n; i++ ) {
  print i
}

and

i = 1
while ( i < n ) {
  print i
  i++
}

are implementations of the same algorithm, but clearly not the same program. And while this simple example may actually translate to the same machine code for many real languages, it's clear that they don't have to. So whether the programs create the same sequence of states depends on your machine model.

This is a hint that tying your notion of algorithm to a specific machine model is probably not useful.
Algorithms are specific sequences of instructions for fixed machine models. Then, the answer depends on your machine model.

If there is exactly one statement for every possible state change, then
a sequence of states induces a unique sequence of statements. Hence, if
all inputs cause identical state sequences, the algorithms/programs are
the same.
If multiple statements can cause the same state change, then the opposite is true.


Proving that Hamiltonian Cycle is reducible to a travelling problem? I chanced upon the following question online:

  A company has two trucks, and must deliver a number of parcels to a
  number of addresses. They want both drivers to be home at the end of
  the day. This gives the following decision problem.

Instance: Set V of locations, with for each pair of locations
v, w ∈ V , a distance d(v, w) ∈ N, a starting location s ∈ V ,
and an integer K.

  Question: Are there two cycles, that both start in s, such that every
  location in V is on at least one of the two cycles, and both cycles
  have length at most K?

The solution provided uses Hamiltonian Cycle to prove the parcel problem is NP-Complete.

  Given any instance of Hamiltonian Cycle with n vertices, construct the
  following special instance of the above problem.

  Copy the graph and make the distance d(v, w) equal to 2 if there is    an edge in the graph, and 4, otherwise.
  Label one of these vertices as s. Add one vertex 0 such that d(s, 0)    = d(0, s) = n and d(v, 0) = d(0, v) = 2n + 1 for all v != s. The
  threshold K is equal to 2n.

The explanation provided is as follows:

  The only thing we have to do is to keep the other driver busy, which
  is easily taken care of by including an additional vertex with
  distance K/2 from s and distance K + 1 to all other addresses.

I tried constructing a simple graph of N = 3 whereby each vertex is connected by an edge of distance 2. Then I introduced a new node which is distance 4 away from the source vertex(i.e. starting point), and distance 7 from every other vertex.

But I am unable to understand how this construction fits into the original decisional problem. What exactly does the solution mean by "keeping the other driver busy?"

Solution link.

Basically, Hamiltonian Cycle is the parcel problem with just one driver. To reduce Hamiltonian Cycle to the parcel problem with two drivers, you get one of the drivers to solve your Hamiltonian Cycle problem, and you make enough work for the other driver that they can't "cheat" by helping the first driver (but not so much work that the first driver has to help the second one).


Triangulation of disjoint line segments Given a set of disjoint line segments in the plane, prove (or disprove) that you can always join the line segments to make a near-triangulation where the vertices are the endpoints of the segments, the outer face is a cycle and every segment is an edge of the triangulation.

This task interested me, at least in non-degenerate case. I've tried to google it and suddenly found a beautiful approach described here (starts with "Next, the constraints are added to the Delaunay triangulation...", but we don't care about Delaunay here).

Name the set of segments $S$. First, forget about segments and build any triangulation $T$ of all endpoints of $S$. Then repeat the following process for all segments one-by-one:

If $e \in T$, we are done with this step. Otherwise, remove all edges of $T$ having an interior intersection point with $e$. One can see that it will unite some triangles of $T$ into one polygon. Add $e$ to $T$; it will break this polygon into two smaller polygons. Triangulate them both and add needed edges to $T$.

The key point is that if $e \in S$ was added to $T$, it will never be removed, because segments in $S$ don't have interior intersection points. So, after this process $S \subset T$.


How is RANSAC used to estimate a homography given the descriptors of both images computed with SIFT? Let image $x$ be an original (non-warped) image. Let $I_1$ be $I_1'$ having suffered some projective transformation and possibly some noise.
Suppose we have computed SIFT descriptors for both images.

Can you explain how RANSAC is concretely used to find the homography that aligns image $x$ and $y$?

More concretely, I understand we give to the RANSAC function the keypoints ($I_1$) and keypoints ($I_1'$).

My understanding (from various papers/tutorials I've read) is that it will take the positions of keypoints in $I_1$, which I denote as $(x,y)$, and the positions of keypoints $I_1'$, $(x', y')$, i.e. RANSAC($(x,y),(x',y')$), and then take randomly pairs of $(x',y')$ and $(x,y)$, and then compute the homography by trying to solve for each $x_i', y_i'$: $$[x'_i, y'_i]=H*[x_i, y_i]$$

But then how to estimate inliers? I guess by looking at the Euclidean distance between each pair of points found in the homography.

However, I don't really see the 'big picture'. I don't completely link this process of 'finding homography' and checking inliers etc.

It would be great if someone could summarize that in a clear way?

P.S.
In general, tutorials say that they "find the homography" and then check for inliers - in some way - but they don't explain in a more pragmatic way what really happends.... w.r.t sift descriptors

How do you estimate inliers?  You use RANSAC.  That's what RANSAC does for you: it computes a homography and gives you a prediction for which pairs are inliers and which are outliers.

In SIFT, we first generate keypoints and the feature vector for each keypoint.  Also, if $k$ is a keypoint in image $x$ and $k'$ is a keypoint in image $x'$, the feature vectors give a way to tell whether $k,k'$ are good matches.  For each $k$, we look for a good match: a $k'$ from $x'$ that is significantly closer to $k$ than any other keypoint in $x'$.  The set of good matches forms a set of possible inliers.

Then, we apply RANSAC.  We randomly pick four good matches, compute a homography from these four, and test how good this homography is by checking how many of the good matches are consistent with the homography (if $k,k'$ are a good match, we're hoping that in most cases the homography will map $k$ to something near $k'$).  Good matches that are consistent with the homography are called inliers (for this homography), and those that aren't are called outliers (for this homography).  We count the number of outliers for this homography.  Then, we repeat this 1000 times (picking a set of four good matches anew each time), in each iteration deriving a homography and counting the number of outliers associated with it.  We keep the homography with the smallest number of outliers.

This is a simplification of the procedure but it will give you the gist of how SIFT works.


When do deadlocks occur? I was reading about deadlocks in Operating Systems. Where I came across two examples below.

Circles with label $P_x$ are processes. Squares with label $R_x$ are resources.  Each dot in the square represents single instance of resource type $R_x$. An edge from $R_x$ to $P_x$ means an instance of resource $R_x$ is allocated to process $P_x$. An edge from $P_x$ to $R_x$ means the process $P_x$ is waiting for getting an instance of resource $R_x$ allocated.
Now consider below two resource allocation graphs

The example on left involves deadlock while the one on the right did not involved deadlock.

I can understand that in right-side figure, if $P_2$ releases its instance of $R_1$, it can be assigned to $P_1$, breaking the circular wait. Or if $P_4$ release its instance of $R_2$, it can be assigned to $P_3$, breaking the circular wait. However we cannot break circular wait in left-side figure.
While I can try out this on any given resource allocation graph and decide if there is deadlock or not, I want to know can we have a generalized rule for this which can tell what exactly it is which is contributing to the deadlock, especially in case of multiple instances of resources are there. I did not found any reference / book speaking of this clearly. So after a bit of thinking I came up with following fact:

If there are multiple instances of same resource, for deadlock to exist, for any combination of two processes, if both are allocated an instance of same resource, then both should be a part of at least one cycle.

In right-side figure above, there is no deadlock because

processes $P_2$ and $P_3$ are allocated instances of $R_1$, but they both are not part of any cycle
similarly processes $P_1$ and $P_4$ are allocated instances of $R_2$, but they both are not part of any cycle

In left-side figure above, there is a deadlock because

processes $P_1$ and $P_2$ are allocated instances of resource $R_3$ and are part of same cycle,$P_1-R_1-P_2-R_3-P_3-R_3-P_1$

So am I correct with the above realization of fact? Or there are more aspects/conditions to the above fact (of when deadlock is present and when not) that I am missing?
What I am asking is if there is any other condition which if met, instead of the above one, will still result in the deadlock (in the context of multiple instances of resources and apart from four classic conditions of deadlock: mutual exclusion, no preemption, hold and wait and circular wait)?

All 4 conditions must be satisfied at the same time.

Hold and Wait
Non-preemption of resources
Mutual Exclusion
Circular wait

In case of single instance of resources:

Cycle in resource allocation graph represents deadlock.

In case of multiple instance of resources:

Cycle in RAG doesn't mean deadlock.
You must check in the same way as you did. Let me write clear steps.

We need to identify a process, in the cycle, which can execute without any dependency and execute that.
Release the resources held by process.
Next check the process which has all the resources to execute and execute completely and release the resources held by it.
Keep doing till all the processes are executed.
If you can't execute all the processes this way, then there is deadlock.

Hope that helps!


For selection in worst-case linear time ambiguity in consideration of $n$ for which $T(n) =O(1)$ and $T(n)\leq cn$ I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the recurrence relation for analyzing the time complexity of the linear SELECT algorithm and I felt that few things probably mismatch with respect to the range of $n$, the input size for which $T(n)$ is assumes $O(1)$ and $cn$ in the substitution method.
The details of the text are as follows:

We can now develop a recurrence for the worst-case running time $T(n)$ of the algorithm SELECT. Steps 1, 2, and 4 take $O(n)$ time. (Step 2 consists of $O(n)$ calls of insertion sort on sets of size $O(1)$ Step 3 takes time $T(\lceil n/5 \rceil)$, and step 5 takes time at most $T(7n/10+ 6)$, assuming that T is monotonically increasing. We make the assumption, which seems unmotivated at ﬁrst, that any input of fewer than $140$ elements requires $O(1)$ time; the origin of the magic constant $140$ will be clear shortly.$^\dagger$ We can therefore obtain the recurrence
$$T(n) \leq \begin{cases}
        O(1)&\quad\text{if $n<140$ $^\ddagger$} \\
       T(\lceil n/5 \rceil)+T(7n/10+ 6)+O(n)&\quad\text{if $n \geq 140$ $^\|$}\\
\end{cases}$$
We show that the running time is linear by substitution. More speciﬁcally, we will show that $T(n)\leq cn$ for some suitably large constant $c$ and all $n > 0$. We begin by assuming that $T(n)\leq cn$ for some suitably large constant $c$ and all $n < 140$ $^{\dagger\dagger}$; this assumption holds if $c$ is large enough. We also pick a constant a such that the function described by the $O(n)$ term above (which describes the non-recursive component of the running time of the algorithm) is bounded above by an for all $n > 0$. Substituting this inductive hypothesis into the right-hand side of the recurrence
$$T(n) \leq c\lceil n/5 \rceil + c(7n/10+6) +an$$
$$\leq cn/5 + c + 7cn/10 + 6c +an$$
$$= 9cn/10+7c+an$$
$$= cn+(-cn/10+7c+an).$$
which is at most $cn$ if
$$-cn/10 + 7c + an \leq 0.\tag 1$$
$$\iff c\geq 10a(n/(n-70)) \quad\text{when n>70} $$
Because we assume that $n\geq 140$ $^{\ddagger\ddagger}$ we have $n/(n-70)\leq 2$ and so choosing $c\geq 20a$ will satisfy the inequality $(1)$

$$ \dagger \quad \text{The statement here complies with the $\ddagger$ in the recurrence relation} $$
$$ \dagger\dagger \quad \text{The statement here does not comply with the $\|$ in the recurrence relation} $$
$$ \ddagger\ddagger \quad \text{The statement here does comply with the $\|$ in the recurrence relation} $$

I could not quite understand this discrepancy, however I did not include the entire algorithm (available in CLRS Section $9.3$) but if incase it is needed please say then I shall include it as well.

It seems that $\dagger\dagger$ is consistent with $\|$. You just need to pick a constant $c$ that is larger than or equal to the constant $\gamma$ hidden in the $O(1)$ notation in the definition of $T(n)$ for $n < 140$ (i.e., the line marked with $\ddagger$).
Then, for any $n \in \{1, \dots, 139\}$, you have $T(n) \le \gamma \le c \le cn$, as desired.


Is Post's Correspondence Problem decidable with fixed word size? So, it's known that PCP is undecidable even when we fix the number of tiles to $n \geq 7$.

I'm wondering, can anything similar be said for when there is a fixed word length?

To be precise, here's the problem:

  Given fixed $m$ and $n$, with $n \geq 7$, and words
  $u_1, \ldots u_n$ and  $v_1 \ldots v_n$ such that $|u_i| \leq m$ and $|v_i| \leq m$,
  is there an index sequence $i_1, \ldots i_k$ such that
  $u_{i_1} \cdots u_{i_k} = v_{i_1} \cdots v_{i_k}$.

For what values of $m$, if any, is this known to be undecidable?

Note that this is similar to this question, but none of the 8 linked papers seemed by their titles to answer my question, and I haven't fully read all 8 of them yet.

For all $m \geq 3$, the problem is undecidable.

Proof by reduction from the word problem of unrestricted grammars:

Take an arbitrary formal grammar. W.l.o.g. all left and right sides of rules have length at most $3$.

This can be seen by translating any grammar into an equivalent TM and then converting back.
Map the resulting grammar to PCP instances; no tile is longer than the longest left or right side of a rule.

That is, with step 1, all tiles have length $\geq 3$.


Graph search or shortest path algorithm for graph with multiple “goals”? I did a project in a class using A* search to solve an 8-puzzle.
But what about a puzzle with multiple ‘solved’ states? For example, and 8 puzzle with some repeated tiles.
I’m not sure whether something like A* search could still work or not. I have trouble fathoming how a heuristic might be designed.
Are their other shortest path algorithms or search algorithms that are better suited for this kind of problem?

If you have multiple goal nodes and a consistent (or admissible) heuristic to each of them, taking the minimum of them will be still be a consistent (or admissible) heuristic.
Aside from that, there is nothing in A* that prevents you from having multiple goal nodes.  The algorithm works fine unchanged.

[Edit] Another heuristic for your problem specifically: for each tile, compute the distance to the nearest valid goal-space, then take the sum over all tiles as the heuristic.
With $n$ spaces, $n-1$ tiles, and $g$ goals, this can be done in $O(n)$ time during the pathfinding by pre-computing the distance to the nearest goal, for each tile, using eg. BFS. This will require $O(n^2)$ space and $O(gn^2)$ time (by searching backwards from each goal).


Equivalence of two definitions of substitution Preliminary definitions

Barendregt [2004] introduces the following two definitions of substitution and their equivalence:

Ottamnn variable convention (p. 26)

  2.1.13. Ottamnn variable convention. If $M_1, ..., M_n$ occur in a certain mathematical context (e.g. definition, proof), then in these terms all bound variables are chosen to be different from the free variables.

Remark 1: I'm using the name 'Ottmann variable convention' because in the 6th impression of "The Lambda Calculus. Its Syntax and Semantics", Barendregt replaced the name 'variable convention' by this name. See 'Addenda for the sixth imprinting', p. E1.
First definition (p. 27)

Second definition (p. 578)

Equivalence (p. 579)

  If one observes the variable convention, then $M[ x:= N ]$ as in definition 2.1.15 is the same substitution as in Curry's definition C.1.

Question

Since (1) follows the Ottmann variable convention its normalisation using both definitions of substitution should be the same.

$$(λxx.x)yz \qquad \qquad (1)$$

Remark 2: I know it is silly to abstract over $x$ twice in (1), but this is not banned anywhere.

Using Definition C.1, the normalisation of (1) is $z$, but using Definition 2.1.15 I got stuck in

$$(λxx.x)yz = ((λx.x)[ x:=y ])z$$

because Definition 2.1.15 doesn't include a clause when the bound variable and the variable to substitute are the same, that is, the missing clause is

$$λx.M[ x:=N ] ≡ λx.M.$$

Are really both definitions the same using the Ottmann variable convention? Am I missing something when using Definition 2.1.15?

Reference

Barendregt, H. P. (2004). The Lambda Calculus. Its Syntax and Semantics. Revised edition, 6th impression. Vol. 103. Studies in Logic and the Foundations of Mathematics. Elsevier.

The following remark from definition 2.1.15 gives you a clue:

  In the third clause it is not needed to say "provided that $y \not \equiv x$ and $y \not \in \mathsf{FV}(N)$". By the variable convention this is the case.

Since you can't make substitutions, it means that there is some violation of the variable convention (§2.1.13):

  If $M_1, ..., M_n$ occur in a certain mathematical context (e.g. definition, proof), then in these terms all bound variables are chosen to be different from the free variables.

In the meta-level expression

$$((λx.x)\ [ x := y ])\ z,$$

let us denote $M_1 = (λx.x)$ and $M_2 = x$. Notice that $x$ is bound in $M_1$, but free in $M_2$. That violates the variable convention, so you can't use definition 2.1.15, because it relies on that convention.


Booth's algorithm Question : Binary Number Arithmetic (Multiplication) It's being said booth's algorithm produces the output exactly as normal binary multiplication while reducing the number of operations performed and can be used for both positive and negative numbers !
I tried multiplying two 4-bit numbers while I don't get the same result...Please guide what am doing wrong.
Multiplicand : 1101 ,
Multiplier : 1110,
Recorded Multiplier(Applying skipping over 1's) : 00-10

The Result's are different Please Help !

When you use normal multiplication, multiplicand and multiplier are represented using (Sign + Magnitude) representation. So effectively 1101 is +(13) in Decimal and (1110) is +14 in decimal as they represent the magnitude. Sign bit would be separate. So the result is (+13)*(+14) = +182 which is 1011 0110 in binary.
When you use booth multiplication, operand are in 2's complement representation. So 1101 is -3 and 1110 is -2 in decimal. So the answer will be 0000 0110 that is +6 in decimal. The problem is with your representation of multiplicand and multiplier.


Fitting a low-degree polynomial to a function on a finite 1d grid - a combinatorial problem? I need to fit a low-degree polynomial $p$ (with $\text{deg}(p) \leq k$) to a function $f$ evaluated on the grid $\{0, 1, ... n-1\}$, so as to minimize the $L_\infty$ norm, i.e. minimize $\text{max}_{0 \leq i < n}{\left| f(i) - p(i) \right|}$.

Now, I know that for $L_2$, this can be solved using a system of linear equations (for getting a zero vector as the derivative of the error) - that is the "Least Squares" method. But - the $L_\infty$ error is not a derivable function. I also know that for a continuous interval rather than a finite grid, there's an iterative approximation algorithm - the Remez Algorithm (although I'm not entirely clear about the specifics - I just noticed it.) And I also had a vague hunch which I didn't manage to act on that Chebychev polynomials, each of which being the optimal solution to the problem with $f = 0$ and a fixed leading coefficient 1, might be relevant here somehow.

Anyway, what I'd like to know is:

Is this problem is essentially combinatorial or essentially numero-analytic?
Can it be solved in PTIME (assuming operations on real values are O(1))?
If so, what's the numerical stability features of such a solution (since my n is large-ish)?
If not, does it admit an efficient (PTIME) approximation scheme?
If not, how do people deal with it in practice?

The problem can be solved in polynomial time using linear programming.

Write $p(x) = c_k x^k + \dots + c_1 x + c_0$, and think of $c_0,\dots,c_k$ as unknowns.  Also introduce an unknown $d$, which will represent the $L_\infty$ norm.  We will minimize $d$, subject to the following inequality:

$$-d \le f(i) - (c_k i^k + \dots + c_0) \le d.$$

Notice that, since $i$ and $f(i)$ are constants, this is a linear inequality in the unknowns.  We obtain one inequality per value of $i$.  Now the minimum achievable value of $d$ corresponds to the polynomial $p$ that minimize the $L_\infty$ norm, so you can solve this using any algorithm for linear programming.  Since linear programming is in P, your problem is in P, too.

I expect that this algorithm will be efficient in practice, as linear programming over $k+2$ unknowns and $n$ inequalities should be pretty efficient for reasonable values of $k,n$.

I don't know what the numerical stability issues might be.

Another solution in practice might be to find a solution that minimizes the $L_p$ norm.  You could start by minimizing the $L_2$ norm, using any standard method (e.g., least squares).  Then you could start from that solution and find a solution that minimizes the $L_p$ norm, for some larger value of $p$, say using gradient descent.  After increasing $p$ a few times I expect the resulting solution might often turn out to be a reasonable approximation, even if not optimal.