Regular languages that can't be expressed with only 2 regex operations I thought all regular languages could be expressed with regular expressions (if a language is regular, it can be expressed with regex), but
I have been told that you need all three of the regular operations (concatenation, union, and star) for that to hold.

For example, I have been told that if I can only use the union and concatenation regex operations (2 out of the 3), there would be a regular language I can't describe with just those two.

Same with just Kleene star and union. What are some examples of this?

With only union and concatenation, you can't describe any infinite language. The union and concatenation can only produce finitely many strings. With only union and the Kleene star, you can't describe a language such as $L = \{ab\}$, because there's no way to concatenate an expression generating only $a$ with an expression generating only $b$.  With only concatenation and the Kleene star, you can't describe a language such as $L = \{a,b\}$.


Simplification of regular expression I have some issue with how to simplify regular expression. I cannot find any suitable method to approach these types of problems.

How would one approach simplifying the following regular expression:

(01(11)* (10+0)+00+1)* 0(11)*

Thanks in advance,

Erik

Minimizing a regular expression is PSPACE-hard, so there is no general method that is generally applicable and can be completed in a reasonable amount of time.  You'll need to inspect each individual situation on a case-by-case basis.

If you want to read about general methods, see https://cstheory.stackexchange.com/q/31630/5038 and https://cstheory.stackexchange.com/q/12361/5038.  CSTheory has a nice blog post with an overview of the field.  The alternative is to stare at that regular expression, understand very well what language it recognizes, and write down a shorter regexp.  You might be able to find some simplifications that work for that particular case, even though they are not general.


Problem with the pseudo random number generator One-Time-Pad I've started learning cryptography in class and we've come across One-Time-Pads, in which the key (uniformally agreed upon) is as long as the message itself. Then you turn the message into bits, do $XOR$ and get the cipher text. This encrypts the message and to decrypt the message you'd  do $XOR$ with the cipher and key bits.

Now to make a more efficient One-Time-Pad you'd use a pseudo-random number generator, where the original key is $n$-bits long (and doesn't have to be as long as the message). Then you'd put the key in the generator and get a pseudo random number. But since it's pseudo random, wouldn't the sender and receiver get different keys? Then how can the receiver decrypt the message if they don't have the same key?

You seem to have misunderstood what the key is.

In the context of symmetric encryption, the key is a shared secret: something that is known to both the sender and receiver.  For OTP, the key is the entire pad and, if two people wish to encrypt some message using OTP, they must ensure beforehand that they have a long enough pad to do that.

For your proposed "efficient" OTP, the key is the PRNG seed: both parties must ensure beforehand that they know it. Then, they both initialize the PRNG with the same seed and it is guaranteed to produce the same sequence of "random" numbers for each of them.

However, note that this is a massive, massive weakening of OTP.  An actual OTP gives perfect security, as long as the pad is kept secret.  If you intercept the 17-character message

nsmklmfmwnfmngner

you have zero knowledge of whether it is

maketrumpthepotus

encoded with one pad, or

ensureclintonwins

encoded with a different pad. Or

kittensarethebest

or literally anything else. However, using a pseudorandom pad means that only certain pads are possible (maybe there's no key at all that encrypts the kitten message to "nsmklmfmwnfmngner", so you can rule that out).  Anybody who knows the PRNG algorithm can start guessing keys to try to decrypt messages.  Anyone who captures some pad material can start trying to reverse engineer the PRNG.  Anyone who captures encrypted messages can start trying the same.

You really shouldn't call it OTP unless the key material is as long as the message. Your proposal for using a PRNG is just a generic stream cypher.


Avoiding loops in Bellman-Ford algorithm If you apply standard Bellman-Ford algorithm to a graph containing negative loop it can only report its existence. Are there approaches to modify it to find shortest path containing any vertex not more than once so effectively avoiding loops? I would appreciate if an answer will contain a link to a paper.

As far as we know, you can't.  The problem of finding the shortest simple path in a graph is NP-hard; it is equivalent to the problem of finding the longest simple path (just negate all edge lengths), which is at least as hard as Hamiltonian path, which is NP-hard.  Therefore you shouldn't any simple modification to Bellman-Ford to yield an efficient algorithm for this problem; best guess right now is that no such algorithm exists.

See also https://cstheory.stackexchange.com/q/17462/5038 and https://en.wikipedia.org/wiki/Longest_path_problem.  According to Wikipedia, the longest path problem is fixed-parameter tractable and can be solved in time exponential in the length of the longest path and linear in the size of the graph, which also applies to your problem as well.


What combination of data structures efficiently stores discrete Bayesian networks? I understand the theory behind Bayesian networks, and am wondering what it takes to build one in practice. Let's say for this example, that I have a Bayesian (directed) network of 100 discrete random variables; each variable can take one of up to 10 values.

Do I store all the nodes in a DAG, and for each node store its Conditional Probability Table (CPT)? Are there other data structures I should make use of to ensure efficient computation of values when some CPTs change (apart from those used by a DAG)?

The "best" data structure probably depends on what particular problem you're trying to solve with it. Here's one approach that I've seen (and have used myself), which simply stores all the information and leaves it up to the algorithm what to do with it.

First you index the nodes by unique integers, 0 through n-1. Then you simply store, for each node, the list of its parents as an array of integers --- in C++, for instance, you could have a std::vector<std::vector<int> >: first vector over nodes, second vector lists the respective parents). That captures the entire DAG structure.
Furthermore, since each node has exactly one conditional probability table associated with it, you could index those with the same integer IDs. For each probability table you need to store its scope, i.e. the set of random variables its defined over. Secondly you'd probably have one large list of floating point numbers that contains the actual conditional probabilities (and you'll want to make sure you get the indexing right). To give a C++ example again, something like this could do:

struct CondProbTable {
    std::vector<int> scope;    // list of random variables the CPT is defined over
    std::vector<double> table; // appropriately sized and indexed table of
                               // conditional probabilities
};

With that, you could use a std::vector<CondProbTable> to store all your CPTs.

Again, this basically only stores the Bayes net, it does not assume anything about what you want to do with it. Including the CPT scope in CondProbTable is somewhat redundant, since it could be inferred from the list of parent nodes described under point 1.


What do the commas separating atomic events in a Relational Calculus formula means? For instance, take the example of this book here on page 30. About the formula $$ Q(x,x') = R(x), S(x,y), S(x',y), R(x') $$ described there, what do the commas mean? Is it the same as an "and" operation? Or a natural join maybe?

The notation is defined on page 17 and 18. The authors define a couple notations and state that they will "freely switch back and forth" between them.  This example doesn't seem super-consistent, I'd expect $Q(x,x'):\!\!-\,R(x),S(x,y),S(x',y),R(x')$ rather than an equals sign, but presumably it means $Q(x,x') = \exists y.R(x)\land S(x,y) \land S(x',y)\land R(x')$.

It doesn't really make sense to talk about natural joins in this context, as those rely on named attributes/columns. But yes, this query includes (equi-)joins. To be clear, the comma stands for conjunction.  Any joining is implicit in duplicate uses of a variable. In particular, if all variables were used only once in the right hand side, then there would be no equi-joins, even implicitly.  In SQL, the query would look something like:

CREATE VIEW Q
AS
SELECT DISTINCT S1.Field1, S2.Field1 AS Field2
FROM S AS S1
INNER JOIN S AS S2 ON S1.Field2 = S2.Field2
WHERE S1.Field1 IN (SELECT Field1 FROM R)
  AND S2.Field1 IN (SELECT Field1 FROM R)

or to be more systematic,

CREATE VIEW Q
AS
SELECT DISTINCT S1.Field1, S2.Field1 AS Field2
FROM S AS S1
INNER JOIN S AS S2 ON S1.Field2 = S2.Field2
INNER JOIN R AS R1 ON R1.Field1 = S1.Field1
INNER JOIN R AS R2 ON R2.Field1 = S2.Field1

or going a different direction,

CREATE VIEW Q
AS
SELECT DISTINCT S1.Field1, S2.Field1 AS Field2
FROM S AS S1, S AS S2, R AS R1, R AS R2
WHERE R1.Field1 = S1.Field1
  AND S1.Field2 = S2.Field2
  AND S2.Field1 = R2.Field1


Enumerating every "partnering" without repeating partners I'm taking a class. In this class every week we have a partner. There are an even number of people in the class. We'd like avoid having repeat partners if possible so that everyone gets to work with as many people as possible. I'd like to know how many weeks we could accomplish this before we're forced to partner someone again.

More formally given a set $S$ with an even number of elements, define a "partnering" of $S$ to be a set of partitionings where each part in each partition is of size 2. The empty set is a valid partnering. The set containing any single partitioning of $S$ is a valid partnering. What the largest "partnering" we can define?

If there are $2N$ elements in $S$ then there is no partnering of size greater than $2N-1$. I've also been able to get a rough lower bound on the size of the maximal partnering. The best I've been able to do is half the size of the set but in special cases I can do a bit more. For instance if the size of the set is $2^k*N$ I can get $N+\frac{N}{2} + ... + \frac{N}{2^k}$ but that's a very special case. For powers of two this ideal since $2N-1 = N+\frac{N}{2} + ... + \frac{N}{2^k}$. Ok so for powers of two I have the answer but for other numbers I just have a lower bound.

My current method:

If you have $2N$ elements in your set you can arbitrarily split them into two groups, $A$ and $B$ of size $N$ and assign each element in each group a member of $Z_N$. Call the functions assigning these indexes $Z_a$ and $Z_b$ for the functions that assign them for each group. You can then define $N$ different partitions by first paring $a \in A$ with $b \in B$ if $Z_a(a) = Z_b(B) + k$ for each $k \in Z_n$. That gives you a partnering of size $N$ already. After those pairings have been used up you can recursively split $A$ and $B$ into two groups since no one in $A$ has been partnered with anyone in $A$ yet and likewise for $B$

Intuitively we're splitting the group in two, putting each group in a circle, and then rotating one of the circles. Then if we're lucky we can repeat the process.

Can we do any better or is this optimal? My expectation is that there must be a better result here since otherwise it would mean the size of the maximal partnering has something to do with how many times you can divide the size of the set by 2.

If $|S|=2N$, then the largest "partnering" is a $1$-factorisation of the complete graph, or a round-robin tournament schedule. There always exists a schedule that pairs all people exactly once in $2N-1$ rounds without repeating pairs. There are various algorithms to find such a schedule, see the previous link.


Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm? If we have any arbitrary computer program that can modify its instructions, is it possible to simulate that program with a program that cannot modify its instructions?

Edit:

I am new to stackexchange so not sure if I'm allowed to ask a NEW question here, but here goes:
Ok so the proof that it is possible is actually really simple as you guys have shown.
Now, I am wondering: Are there problems for which it is more efficient (and to what extent) to use the most efficient self-modifying algorithm to solve the problem, versus the input-output-equivalent most efficient non-selfmodifying algorithm?

Yes, it's possible. You can simulate the program by using an interpreter for the language it's written in. Now, the program (the interpreter) is fixed and the thing that used to be a self-modifying program is now the interpreter's data.

In particular, you could perfectly well have a universal Turing machine that allowed the TM it's simulating to modify its own description.  (The description of the simulated machine, I mean; not the UTM.)


Is this problem NP-hard? Maximizing selected sets so that their union is less than k? There is an NP-hard problem called Minimum k-Union where we are given a set system with $n$ sets and are asked to select $k$ sets in order to minimize the size of their union.

I'm currently interested in a very similar problem, but don't know how to convert one to another:

Given a set system with $n$ sets and a bound $k$. Select as many sets as possible while their union is at most $k$.

Is this problem NP-hard? Any hint is welcome!

Updated 2020: I found a paper called "Unbalanced Graph Cuts" by Hayrapetyan et al. [ESA'05] which describes the Minimum-size bounded-capacity cut (MinSBCC) problem which is very similar to what I looked for.

Very easy. Clique problem reduces to yours.

Each set is the 2-element edges $\{u,v\}$ of $G$.

A $k$-clique has as many edges as possible while only involves $k$ vertices. So, $K={k \choose 2}$.


How to best maintain a sorted list from a stream of integers? If I have an incoming stream of integers how can I best maintain a sorted list of them? The only way I can think of is to binary search for the position and shifting the remaining elements to the right. This would amount to $O(N + \log N)$ time. Is there a better data structure that can help me achieve the same in better time? I know we can use a Balanced Binary Search Tree with $O(\log N)$ insertions but I would like to have efficient access on the list.

A balanced binary search tree can support access to arbitrary elements in $O(\log N)$ time per access.  Augment the data structure to store, in each node, the number of values stored in the subtree under that node.  Then you can find the $i$th largest value in the list in $O(\log N)$ time as well; thus, all basic operations can be done in $O(\log N)$ time.


Are all partial functions partial computable? If we have some function $f\colon \mathbb{N} \rightarrow \mathbb{N}$ that is not total, i.e. for some values $x \in \mathbb{N}$, $f(x) = {\perp}$, is $f$ always partial computable? By partial computable I mean there exists a program that $f(a)$ is defined for $a \in \mathrm{dom}(f)$ and $f(a)$ is not defined for $a \notin \mathrm{dom}(f)$.

I expect that this isn't the case but cannot come up with a counter example.

The fact that we can encode Turing machines as strings means that there are only countably many Turing machines, so only countably many computable or partial-computable anythings.  Since there are uncountably many partial functions $\mathbb{N}\to\mathbb{N}$ (or even partial functions $\mathbb{N}\to\{0\})$, it follows that, in a very strong sense, "most" partial functions are not partial computable.

For a concrete example, use the fact that, if a set and its complement are both semi-decidable, they are both decidable (exercise: prove this), and the analogous result for partial functions. This means that, if you take any set $S$ that is semi-decidable but not decidable, then $\overline{S}$ is not semi-decidable.  So, for example, the function
$$f(x) = \begin{cases}
0 &\text{ if }x=\langle M\rangle \text{ for some TM $M$ that loops on every input}\\
{\perp} &\text{ otherwise}
\end{cases}$$
is not partial computable.


Can Non-Linear Grammars generate Regular Language? I stumbled upon the following non-linear grammar

$$S \to AB$$
$$A\to aaA\mid \epsilon$$
$$B \to Bb\mid \epsilon$$

and the language generated by this non-linear grammar is {a^2nb^m : n ≥ 0, m ≥ 0} which looks to be regular. I was successful in drawing a DFA for this language.

Thus far, I have studied that Left Linear and Right Linear grammars classify as Regular Grammar and generate Regular Languages. I know there are certain Linear Grammars that can be converted to corresponding Left Linear or Right Linear equivalent forms. Similarly, I am guessing, we can write a Right or Left Linear grammar in a Non-Linear fashion and get the same regular language which is what is happening here.

Thus, what I understand is that Left Linear or Right Linear Grammars always generate Regular languages but a Non-Linear grammar may or may not generate a regular language. Is that the correct way to put it? Are there any gaps in my understanding?

Wkipedia states "an example of a linear, non-regular language is {a^nb^n}". Can I then say that above language is an example of non-linear, regular language? That sounds and probably is wrong.

You are confused a bit I believe by using the terms grammar and language somewhat interchangeably.

A grammar is a set of production rules. A language is a set of words. A language is described, or generated by a grammar.

They are not the same and you should be careful at all times to see which is which.

There are a lot of terms such as "context-free", "linear", "regular", etc, that are direct properties of grammars. That is their original definition.

These terms when applied to a language, has a different, indirect meaning. When I say that a language L is X for those above properties, I mean that there exists a grammar with property X that generates L.

Now this can get confusing. Let's take your original grammar. It itself is not linear or regular, but the language it generates is both. Why? Because I can construct another grammar for it which generates the same language, which has those properties:

$$S \to A$$
$$A \to aaA \mid B$$
$$B \to bB \mid \epsilon$$

If you want to be even stricter I could make it a strictly right-linear grammar without epsilon productions (other than the whole language being nullable):

$$S \to aA_2 \mid bB \mid \epsilon$$
$$A_1 \to a A_2$$
$$A_2 \to aA_1 \mid aB \mid a$$
$$B \to bB \mid b$$

Finally, we have that for language classification we have (among others):

$$\text{Left-linear} = \text{Right-linear}   =\text{Regular} \in \text{Linear} \in \text{Context-Free}$$

  Can I then say that above language is an example of non-linear, regular language?

That is indeed wrong, because the language above is linear. You are confused because you are looking at the grammar, which isn't linear. Just because a certain grammar for a language isn't property X doesn't mean that there doesn't exist another grammar that generates the same language that has property X.

That's why it's generally hard to prove that a language doesn't have some property X. You need to show that every possible grammar you can construct for that language doesn't have that property, because a single one is enough to give that property to the language.


What is the formal way to prove this is still a minimum spanning tree? I don't get the formal way of proving the following cases:

Suppose I have a minimum spanning tree $T$ in a graph $G(V, E)$, with positive edge weights $w$, I want to prove the following:

1) If I increase the edge weight of an edge that is not in $T$, then my resulting tree is still the minimum spanning tree.

This obviously makes sense since none of the edges of $T$ have been modified, and even so, the new edges will only have weights higher than $T$. Is there a way I could put this in a formal way?

2) If I decrease the edge weight of an edge that is in $T$, then my resulting tree is still the MST.

Again, this is very intuitive since the minimum weight of my MST is already the minimum, any reduced amount will still make it minimum. Again, the problem is putting this into formal proof.

3) After adding a new edge $e$ with a unique weight $w(e)$ in $G$, the tree will still be an MST.

For part (1), denote by $w$ the weight of a tree in the original tree, and by $w'$ its weight in the new tree. Since $T$ is an MST, we have $w(T) \leq w(T')$ for every tree $T'$. Also, $w'(T) = w(T)$ and $w'(T') \geq w(T')$ for all $T'$. Therefore $w'(T) = w(T) \leq w(T') \leq w'(T')$ for all trees $T'$, that is, $T$ is an MST with respect to $w'$ as well.

Part (2) is similar to part (1), though slightly more challenging. Suppose that we decreased the weight on an edge in $T$ by an amount $\delta$. Then $w'(T) = w(T) - \delta$, and $w'(T') \geq w(T') - \delta$ for every tree $T'$. Therefore $w'(T) = w(T) - \delta \leq w(T') - \delta \leq w'(T')$ for every tree $T'$, and so $T$ is an MST with respect to $w'$ as well.

I couldn't quite understand part (3), but I think you've seen enough examples of how these proofs go.


Is this NIM game tree correct? I have an assignment to construct a game of Nim (a game in which two players must divide a pile of tokens into two unequal sizes; 6 can be divided into 2 & 4 but not 3 & 3). I was provided a game tree (the same one I find on Google), but I am confused. Shouldn't the first turn of the second player have access to S6, S5, and S4 and S3 since 7 can be divided into 4 & 3?

There are many kinds of NIM. The one in the picture is a rather classic example. Take either one or two tokens, the one who takes the last token looses.

Does not sound like the version you suggest. Your game does not state what happens with the divided heaps?


Parse DAG into task tree Suppose we have a DAG of tasks:

Arrows represent flow (reversed dependencies: 8 must be run after 7). Some of the tasks (like 4, 5, 6) can be run in parallel (Par block). Dependent tasks (like 7, 8, 9) must be run sequentially (Seq block).

I need to parse this DAG into recursive structure of Seq and Par blocks (collections). DAG from the image above may be represented by the following structure:

Seq(
    1,
    2,
    Par(
        Seq(7, 8, 9),
        Seq(
            3,
            Par(4, 5, 6),
            10
        )
    )
)

Each DAG may be represented by a set of Seq-Par structures. I want to search for the most optimal. Optimality criteria — run in parallel as much as possible (without breaking dependencies).

More on optimality criteria: all tasks' have the same execution time T. Execution time of Seq(1, 2 ... N) equals to N * T. Par(1, 2 ... N) = T.

I believe, that this task is pretty well-known and simple. Can you, please, name some algorithm solving this problem.

If we add edge from 7 to 4 (proposal from comments), then one of representations may be:

Seq(
    1,
    2,
    Par(
        7,
        3
    ),
    Par(
        Seq(8, 9),
        Seq(
            Par(4, 5, 6),
            10
        )
    )
)

Your problem is equivalent to scheduling unit-time tasks on infintely many machines with precedence constraints (which are by necessity DAGs) minimizing the maximum completion time. In scheduling literature, this is called project scheduling and also denoted as $P_{\infty} \mid \text{prec} \mid C_{\max}$.

This problem is known to be amenable to the critical path method (CPM) which creates an optimal schedule in time $O(n^2)$, $n$ the number of tasks.

Given a schedule $s : \mathbb{N}^2 \to T$ that maps pairs of time slot and  machine indices to tasks, you can derive a tree consistent with the precedence DAG of the form

$\qquad\displaystyle \mathrm{Seq}\bigl( \mathrm{Par}(s(1,1), \dots, s(1,i_{1})),\ \dots,\ \mathrm{Par}(s(t,1), \dots, s(t,i_{t}))\bigr)$;

here, $t$ is the time of the last scheduled task, and $i_j$ is the maximum index of busy machines at time $j$. (I assume that at any given time $j$, machines $1, \dots, i_j$ are busy and $i_j+1, \dots$ idle.)

If that schedule is optimal, the tree is, too. It does not hold information about the original DAG, though.


Is there a theory/abstraction behind OOP? Functional programming has the very elegant Lambda Calculus and its variants as a backup theory. Is there such a thing for OOP? What is an abstraction for the object oriented model?

There are four main approaches, though these only scratch the surface of what is available:

via lambdas and records: the idea is to encode objects, classes and methods in terms of more traditional constructs. Benjamin Pierce's work from the mid 90s is representative of this approach.
Abadi and Cardelli's object calculi (see Abadi and Cardelli's book A Theory of Objects: their main abstraction is a record of methods, and the approach is closer to the prototype-based realisation of object-oriented programming, though classes and inheritance can be encoded in terms of the more primitive elements.
Castagna's multimethod calculus (see Castagna's book Object-Oriented Programming A Unified Foundation): his approach takes multimethods are the key abstraction.
Class-based calculi (such as in Kim Bruce's book Foundations of Object-oriented Languages: Types and Semantics or Featherweight Java): these approaches aim to capture the essence of class based programming and focus on classes and inheritance.


Turing Machine 'marking' specific portion of encoding Given a turing machine $T$ that receives an encoding of another turing machine and a word $<M><w>$, can $T$ 'run' through the encoding and 'mark' specific transitions/states?

For example, if I want to show that the language $L = \{<M><w>\}$ such that when we run $w$ in $M$ we will visit at least two unique states different than the starting state.

Now for this, I suggested this algorithm, but I am not sure it is even compuatable:

  Given the encoding $<M><w>$, we will run through the encoding and 'mark' all states that can be reached from the starting state of $M$, if two or more states have been marked after finishing, accept, else, reject.

I know that since this an encoding of a turing machine and a word, we indeed -can- run through the encoding. But can we really do the 'marking' operation? if so, how?

A quick answer: if the tape alphabet is large enough ($\geq 18$ symbols), then $L = \{\langle M,w\rangle \mid $ M on w  visits at least two unique states different than the starting state $\}$ is undecidable; indeed for every $M$ with $n$ states there is an equivalent $M'$ with only 2 states such that  for all $x$ $M(x)$ halts if and only if $M'(x)$ halts. To prove that L is undecidable, you can use the following reduction from the halting problem: given $\langle M\rangle$ build the equivalent two states machine $M'$ (the starting state plus another one), and add an additional final and accepting third state that can be reached only if $M'$ halts when run on the empty tape. Clearly $\langle M',w\rangle  \in L$ (i.e. visit the second and the third accepting state) if and only if $M$ halts ($w$ is irrelevant), so if $L$ is decidable you can solve the halting problem which is a contradiction.

Reducing the number of symbols, doesn't help too much, indeed you can encounter Turing machines that behaves like the Collatz function (e.g enter the third state only when the sequence reaches 1) ... and it is an open problem if for all $n$ the Collatz function reaches 1.

For a proof that you can build an Universal Turing machine (using 2-tag simulation) with only 2-states and 18 symbols see:

Y. Rogozhin. Small universal Turing machines. Theoretical Computer Science,
168(2):215–240, Nov. 1996.

Finally, as an exercise, you should be able to easily prove that the following language is undecidable:

$L' = \{ \langle M,w,k \rangle \mid$ when run on w the Turing machine M visits at least $k$ different states $\}$


Knapsack problem question Based on this video,  the tutor explains the knapsack problem with dynamic programming approach. One thing is not cleared in this video, which is my main question.

All the values on the first row (except 0) are set to 1 because value and weight (on that row) are 1 hence, we cannot exceed that number

Below is the complete example of the tutor as linked in the above video.

My question:

  -What would be the values of the first row if weight and value were not both the same?

So let's say  value is 25 and weight 3 (first row values):
I suppose the first row results would be 0,25,25,25,25,25,25,25

Let me know if i am wrong.
Thank you.

Note that the first row is important to be correct as every row depends on the previous one. The tutor's example in the video, is not the best as the first row value and weight are both 1.

First row indicates the optimal knapsack for each weight using only that item. Then each subproblem in that row asks what is the maximal value one can reach with using only first item and maximum weight indicated by the columns. Then because your first item would have a weight of 3, there is no way for you to include an item for any total knapsack of weight less than 3. Therefore the optimal knapsack for each weight less than 3 would be 0.

Then the first row would look like:
0 0 0 25 25 25 25 25


Confused with the proof that Edmonds-Karp always monotically increases the shortest-paths The proof for the lemma from "Introduction to Algorithms by Cormen et. al." is not clear for me. I can't comprehend a few things. Here is a lemma and its proof. My questions are below.

  The notation $\delta(u, v)$ is used to denote shortest-path from $u$  to $v$.

Question 1:

  Because of how we chose $v$, we know that the distance of vertex $u$ from the source $s$ did not decrease, i.e., $\delta_{f'}(s, u) \geq \delta_{f}(s, u)$

Why the shortest-path from $s$ to $u$ after the augmentation of flow $f$ must be greater than or equal to the distance before the augmentation ? How it is possible to have greater distance that it was ? The augmentation only removes the edge $(u, v)$. But, the vertex $u$ still in place, isn't it must be strictly equal ?

Question 2:

  If we had $(u, v) \in E_f$, then we would also have $\delta_f(s,v) \leq \delta_f(s, u) + 1$

This looks like ok for me to have such case. We claim that distance from $s$ to $v$ is less than or equal to the distance from $s$ to $u$ plus 1. But in the graph before the first augmentation this case must be true. It is false for less than case, but true for equal case.

Question 3:

  How can we have $(u, v) \notin E_f$ and $(u, v) \in E_{f'}$ ? The augmentation must have increased the flow from $v$ to $u$. The Edmonds-Karp algorithm always augments flow along shortest paths, and therefore the shortest path from $s$ to $u$ in $G_f$ has $(v, u)$ as its last edge.

The edge set $E_f$ is before the first augmentation and $E_{f'}$ is after it. The first augmentation must remove the edge $(u, v)$ and put the reverse edge $(v, u)$ into the edge set $E_{f'}$, but not the same edge $(u, v)$. That is why how we can have $(u, v)$ in $E_{f'}$ ?

Answer to Question 1:

Because of how we chose , we know that the distance of vertex  from the source  did not decrease, i.e., ′(,)≥(,)
Why the shortest-path from  to  after the augmentation of flow  must be greater than or equal to the distance before the augmentation ? How it is possible to have greater distance that it was ? The augmentation only removes the edge (,). But, the vertex  still in place, isn't it must be strictly equal ?

Because in the Proof, "We will suppose that for some vertex $v \in  V - \left \{  s, t\right \}$, there is a flow augmentation that causes the shortest-path distance from $s$ to $v$ to decrease". So, if we consider $u$ is the opposite type compared to $v$, that is to say, the shortest-path distance from $s$ to $u$ does not decrease: equation (26.13)  $\delta _{f'}\left ( s,u \right )\geq \delta _{f}\left ( s,u \right )$ holds.
Of course, if you suppose that $u$ is same type as $v$, which has decreasing shortest-path distance from $s$ to $u$, then we can take $u$ to replace the $v$, and find the path, $p:s\rightarrow x \rightarrow u$, where $\delta _{f'}\left ( s,x \right )\geq \delta _{f}\left ( s,x \right )$ holds. In this case $x$ takes the place of $u$ in eq(26.13).
Answer to Question 2:

If we had (,)∈, then we would also have (,)≤(,)+1
This looks like ok for me to have such case. We claim that distance from  to  is less than or equal to the distance from  to  plus 1. But in the graph before the first augmentation this case must be true. It is false for less than case, but true for equal case.

If the shortest path from $s$ to $v$, $p_v: s\rightarrow u \rightarrow v$ overlaps with the shortest path from $s$ to $u$, $p_u: s\rightarrow u$, the equal case happens.
$\delta_f(s,v)=\delta_f(s,u)+1$.
If the two paths $p_v$ and $p_u$ are not overlapped, the shortest path from $s$ to $v$, $p_v: s \rightarrow v$ would not contain the node $u$. Since $p_v$ is the shortest path, obviously the length of $p_v$ should be shorter than the length of $p_u$ + $(u,v)$ (another path from $s$ to $v$). Therefore the less than case happens: $\delta_f(s,v)<\delta_f(s,u)+1$.
Answer to Question 3:

How can we have (,)∉ and (,)∈′ ? The augmentation must have increased the flow from  to . The Edmonds-Karp algorithm always augments flow along shortest paths, and therefore the shortest path from  to  in  has (,) as its last edge.
The edge set $_$ is before the first augmentation and $_{′}$ is after it. The first augmentation must remove the edge (,) and put the reverse edge (,) into the edge set $_{′}$, but not the same edge (,). That is why how we can have (,) in $_{′}$ ?

$(u,v)\notin E_f$ and $(u,v)\in E_{f'}$ mean that the newly augmentation augments flow (a cancellation flow for $(u,v)$) along the edge $(v, u)$. Recall that, augmentation happens on the shortest path, which means that $(v,u)$ is on the shortest path $p$ from $s \leadsto v \rightarrow u \leadsto t$. If $p$ overlaps with the shortest path from $s \leadsto u$, $\delta _{f}\left ( s,v \right ) =  \delta _{f}\left ( s,u \right )-1$ holds. However I am not sure now that the overlapping does happen.


Can every DFA be converted to an equivalent one that has a single accept state I know that it is true for NFAs. It seems similar.

Myhill–Nerode theory implies the following result:

  Every DFA for a regular language has at least as many accepting states as the minimal DFA.

Indeed, suppose that the minimal DFA has $m$ accepting states. Let $w_1,\ldots,w_m$ be words which cause the minimal DFA to reach these states. Now consider any DFA for the same language, and let $q_1,\ldots,q_m$ be the states that the DFA reaches upon reading $w_1,\ldots,w_m$. Since $w_1,\ldots,w_m$ are in the language, all these states must be accepting. Furthermore, they must be different, since they are pairwise inequivalent (for each $i \neq j$ there exists a word $x$ such that $w_ix$ is in the language and $w_jx$ isn't, or vice versa). So the DFA contains at least $m$ accepting states.

It is not difficult to construct a regular language whose minimal DFA contains more than one accepting state - for example, the language of all words whose length is not divisible by 3. This language refutes your conjecture.


Getting sum of all numbers contained in substrings of S on a segment I have a string of digits $S$ and K queries $l_i, r_I$ - get the sum of all numbers contained in segment of $S$ from $l_i$ to $r_i$.

For example, $S$ = 1034, $l = 1$, $r = 3$. So answer will be $1 + 10 + 103 + 3$ (note: $03$ was not counted, as it starts with $0$)

It has an obvious solution with $O(K\cdot N)$ performance, but I need the faster one. It looks like I need to use segment tree for storing these sums, but I can't figure out how to do it when $|\ S\ |>2$. If it's possible to use segment tree I'll get an $O(K\log{N})$ solution, it'll be great.

Any ideas of how to use segment tree here?

$O(N \log K)$ running time looks achievable.

Hints:

Suppose you know the answer to the query $l,m$ and the query $m+1,r$.  Can you work out the answer to the query $l,r$ efficiently?  Would precomputation help?  What information do you need to know?
Use a balanced binary tree, where each digit is at a leaf.  At each internal node $\eta$, you will store the answer to the query $l_\eta,r_\eta$, where $l_\eta$ is the leftmost leaf under $\eta$ and $r_\eta$ is the rightmost leaf under $\eta$.  Also, story the sum of all numbers that can be made by starting at index $i$ (for $l_\eta \le i \le r_\eta$) and ending at index $r_\eta$, as well as the sum of all numbers that can be made by starting at $l_\eta$ and ending at some index $j$ (where $l_\eta \le j \le r_\eta$).

Now for any particular query $l,r$, the answer can be obtained efficiently given only $O(\lg K)$ numbers in the tree.

I'll let you have the joy of working out the rest, since this sounds like a programming contest problem and you should probably make some effort on your own.


How can we minimize the total distance of cross pairs in an array Suppose we had 2 arrays of the same size with positive numbers and we wanted to pair up the elements of each array such that the total difference between the pairs is minimized.

The first thought would be to choose pairs with the minimum difference and so on. But it turns out the correct algorithm is to sort them and them pair accordingly.

Any ideas on how to prove that the latter algorithm correctly minimizes the sum of differences?

Let's follow Karolis's suggestion. Consider any solution with pairs $(a,b)$ and $(A,B)$ with $a \leq A$ and $B \leq b$, and write $A = a + \delta$, $B = b - \epsilon$. If we instead pair them $(a,B),(A,b)$, then instead of $|a-b|+|A-B|$ we get $|a-B|+|A-b|$. So we want to show
$$ |a-b|+|A-B| \geq |a-B|+|A-b|. $$
Substitute the expressions for $A,B$:
$$ |a-b| + |a-b+\delta+\epsilon| \geq |a-b+\epsilon| + |a-b+\delta|. $$
In terms of $C = a-b$, this is
$$ |C| + |C+\delta+\epsilon| \geq |C+\epsilon| + |C+\delta|. $$
Rearranging, this is the same as
$$ |(C+\delta)+\epsilon| - |C+\delta| \geq |C+\epsilon| - |C|. $$
So we need to look at the function $D \mapsto |D+\epsilon| - |D|$, whose values are
$$ |D+\epsilon| - |D| = \begin{cases} \epsilon & D \geq 0, \\ 2D+\epsilon & -\epsilon \leq D \leq 0, \\ -\epsilon & D \leq -\epsilon \end{cases} $$
We see that this is an increasing function of $D$, and so $C+\delta \geq C$ implies the inequality we want,
$$ |(C+\delta)+\epsilon| - |C+\delta| \geq |C+\epsilon| - |C|. $$


Why minimum vertex cover problem is in NP I am referring to the definition of the minimum vertex cover problem from the book Approximation Algorithms by Vijay V. Vazirani (page 23):

Is the size of the minimum vertex cover in $G$ at most $k$?

and right after this definition, the author states that this problem is in NP.
My question: What would be a yes certificate?
Indeed, our non-deterministic algorithm could guess a subset of vertices, denoted by $V'$, and we can verify if $V'$ is a vertex cover of some cardinality in polynomial time, but how could we possibly show that $V'$ is minimum in polynomial time?

You don't have to verify that $V'$ is minimum.
The decision version of Vertex Cover (which you have quoted in your question) only asks you to decide whether there is a vertex cover of size at most $k$.
To verify that $V'$ is a valid yes-certificate for an instance $\langle G=(V,E), k \rangle$ you just check that:

$V' \subseteq V$,
$|V'| \le k$, and
$\forall (u,v) \in E, \{u,v\} \cap V' \neq \emptyset$.


Finding the maximum s-t flow of a graph $G$ in $O(n+m)$ time when $G-t$ is an arborescence You are given an directed graph $G = (V , E)$ with positive edge capacities, a source vertex $s \in V$, and a target vertex $t \in V \setminus \{s\}$. $G$ is guaranteed to have the following additional property: The graph obtained by deleting $t$ from $G$ has exactly one path from $s$ to each other vertex in $V \setminus \{t\}$.
How can we compute the maximum flow from $s$ to $t$ in $G$ in time $O(|V|+|E|)$?

First, I read this post, and i think start from $s$ then run BFS, when we visit each node then set it to minimum flow that we find from $s$ to that vertex. Do this until we achieve vertices that have edges to $t$ and push each flow inside that vertices to $t$ this way we have an algorithm with linear time. Is argument correct?

Construct a new graph $T=(V', E')$ by modifying $G=(V,E)$ as follows: for each edge $(u,t) \in E$ of capacity $c$ add a new vertex $t_u$ and an edge $(u, t_u)$ of capacity $c$, then delete $t$ and all its incident edges.
Notice that $T$ is an arborescence and that the maximum flow in $G$ from  $s$ to $t$ is equal to the maximum total flow in $T$ from $s$ to the vertices in $L = \{ t_u \mid (u,t) \in E \}$.
We will now find $f^*$ in time $O(|E'|) = O(|E|)$.
In order to do so, explore $T$ with a postorder DFS from $s$ and, for each visited vertex $v \in V'$ keep track of the maximum amount of flow $f(v)$ that can be sent from $v$ to the vertices in $L$ (so that $f^* = f(s)$).
When a leaf $v$ of $T$ is visited we have $f(v) = \begin{cases}+\infty &\mbox{if } v \in L \\ 0 &\mbox{otherwise}\end{cases}$.
When an internal vertex $v$ of $T$ is visited, let $u_1, \dots, u_k$ be its out-neighbors in $T$, and let $c_i$ be the capacity of the edge $(v, u_i)$. We have:
$$
\begin{equation}
f(v) = \sum_{i=1}^k \min\{f(u_i), c_i\}
\tag{1}
\end{equation}
$$
Of course  you don't actually need to construct $T$. A slight modification of a postorder DFS visit from $s$ in $G$ suffices. Here is a possible recursive implementation in pesudocode where $t$ is  assumed to be a global variable, $c(u,v)$ is the capacity of $(u,v) \in E$, and the first call is $\mathrm{flow}(s)$.
flow(v):
  if v==t:
    return +infinity

  f=0
  for each out-neighbor u of v in G:
      f += min(c(v,u), flow(u))

  return f


Understanding $\epsilon$ transitions on NFA I can't understand why $\epsilon$ is accepted. I thought if $\epsilon$ is inputed then it would go from $q_1$ to $q_3$. $a$ is also accepted, but I though if $a$ is inputed then then the NFA would die, because in $q_1$ there's no where to go.

I read on another post about $\epsilon$ being at two states at the same time, but couldn't get it. What exactly is happening when $\epsilon$ is entered and when $a$ is entered (two different strings)?

              q1
epsilon---------------------
           q1    q3

I think the above is the correct tree when $\epsilon$ is inputed, but makes no sense to me.

$\epsilon$ is an empty string just like "". It is not a symbol of the alphabet. It simply means (in the NFA in your picture) that if you are on state $q_1$, without consuming any symbol you can move to state $q_3$ but you are not obliged to do so. but if you are on $q_1$ and you read $b$, then you must go to $q_2$.

Note that a word is accepted in a NFA if there exists a path from the initial state to an accepting state labelled by the symbols of this words. if should be rejected if no such a path exists.

When $a$ is entered then the possible path is move to $q_3$ without consuming anything and then consume $a$. This lead to the accepting state $q_1$.


How to implement the regret matching algorithm? My question is the following: How to calculate the regret in practice?

I am trying to implement the regret matching algorithm but I do not understand how to do it.

First, I have $n$ players with the joint action space $\mathcal{A}=\{a_0, a_1,\cdots,a_m\}^n.$
Then, I fix some period $T$. The action set $A^t\in\mathcal{A}$ is the action set chosen by players at time $t$. After the period $T$ (every player has chosen an action). So I get $u_i(A^t)$.
Now the regret of player $i$ of not playing action $a_i$ in the past is: (here $A^t\oplus a_i$ denotes the strategy set obtained if player $i$ changed its strategy from $a'_i$ to $a_i$)
$$\max\limits_{a_i\in A_i}\left\{\dfrac{1}{T}\sum_{t\leqslant T}\left(u_i(A^t\oplus a_i )-u_i(A^t)\right)\right\}.$$
I do not understand how to calculate this summation. Why there is a max over the action $a_i\in A_i$? Should I calculate the regret of all actions in $A_i$ and calculate the maximum? Also, In Hart's paper, the maximum is $\max\{R, 0\}$. Why is there such a difference?

I mean if the regret was:  $\dfrac{1}{T}\sum_{t\leqslant T}\left(u_i(A^t\oplus a_i )-u_i(A^t)\right),$
the calculation would be easy for me.

The regret is defined in the following two papers [1] (see page 4, equation (2.1c)) and [2] (see page 3, section I, subsection B).

A simple adaptive procedure leading to correlated equilibrium by S. Hart et al (2000)
Distributed algorithms for approximating wireless network capacity by Michael Dinitz (2010)

I would like to get some helps from you. Any suggestions step by step how to implement such an algorithm please?

The index set of the max operation is $A_i$, the actions of player $i$. The formula says: take each such action $a_i \in A_i$ and compute its regret (with the sub-formula you say you can implement easily), and then take the maximum of those regrets.

The reason for the $\max(R,0)$ is that actions with negative regrets are performing worse than the action currently chosen.

To implement this in code, just set a temporary variable $t$ to be 0. Now loop through the actions one by one, and for each action $a$, compute its regret $r$, and set $t$ as $\max(r,t)$. Note that this approach includes the $\max(R,0)$ operation; to do this without that, set $t$ initially to $-\infty$.


Interview q: Small possible length of stick from an array of stick lengths I was asked this question in a phone interview recently and I bombed it completely. Zero clue how to approach it. I wasn't able to find any similar patterns on google-ing. Thought maybe folks here might be able to help?

Statement: Given m sticks with different lengths. Combine these sticks to form longer sticks with the same length. What’s the smallest possible length of these newly unified sticks?
Conditions:

Must use all sticks
m < 50
max length of single stick less than 20

Example:
Input: 5 2 1 5 2 1 5 2 1
Output: 6
(Process: 1+5, 1+5, 1+5, 2+2+2)

Input: 3 3 3 2 2 5
Output: 9
(Process: 3+3+3, 2+2+5)

Input: 1 2 3 4 5
Output: 5
(Process: 2+3, 1+4, 5)

Input: 1 3 4 5
Output: 13
(Process: 1+3+4+5)

Pragmatic approach: If I were given this in an interview, I'd formulate it as an integer linear programming problem and let an off-the-shelf ILP solver look for a solution for me.
Theoretical approach: As Dmitry mentions, this problem is related to bin packing.  (It's not identical because you require the bins to be full, whereas normal bin packing doesn't require that.)  Wikipedia says that there is a pseudopolynomial time algorithm for bin packing when the bin size is fixed, so you might look up that algorithm and see if it can be modified to apply to your problem.  You might also explore this paper:
Michel X. Goemans, Thomas Rothvoß. "Polynomiality for bin packing with a constant number of item types". SODA 2014.


How to go about proving an algorithm correct? The algorithm (called as rmax(1,n)) finds the maximum of a list of numbers contained in an array S[1..n].

rmax(x, y)
// return maximum in S[x..y]
if y − x ≤ 1
then return maximum(S[x], S[y])
else max1 ← rmax(x, [x+y]/2)
     max2 ← rmax([x+y]/2 + 1, y)
     return maximum(max1, max2)

How would I go about arguing that the algorithm is correct?

To prove the correctness, we have to prove actually the function
rmax(x,y) returns the the maximum number with index between x and
y in the array S[1..n], provided the hypothesis: 1≤x≤y≤n.

There is a semantic technique that often works nicely for recursively
defined functions such as this one.

Your function can be defined as the least fixed-point of a functional:

F = λ rmax, x, y. if y-x≤1 then max(S[x],S[y]) else
                  else max(rmax(x,(x+y)/2), rmax((x+y)/2+1,y))

I have changed a bit the style, for convenience. You note that F is a
function of 3 arguments, and you original function rmax is defined
as its least fixpoint in the semantic domain. Also, here rmax is a local name for the first argument of F. I could replace it by any other name (alpha conversion). I kept rmax only for readability.

Now, the way you prove correctness is by checking that this
functionnal preserves correctness when it is applied to a function
foo that is correct, when it is defined (it is undefined for example
if it does not terminate, but being defined is actually a formal
semantic property).

That is, you only have to check that if the function foo(x,y) is correct, then
the function F(foo) is also correct.

F(foo) = λ x, y. if y-x≤1 then max(S[x],S[y]) else
                 else max(foo(x,(x+y)/2), foo((x+y)/2+1,y))

When y-x≤1, we know that either x=y or x=y-1, since by
hypothesis 1≤x≤y. In both cases we see that max(S[x],S[y]) is the
right answer.

Otherwise, we see that 1≤x≤(x+y)/2≤n and 1≤(x+y)/2+1≤y≤n. Hence the
hypothesis is verified for the two calls to the function foo. So,
since the function foo is correct by hypothesis, each call (when
giving a defined result) returns the maximum array value between the
bound given by its parameters (if it is defined). Since both ranges
cover the range between x and y, the maximum of these two values
is the maximum value between x and y.

Note that there is no base case in this recursion. The reason is that
it starts using with the totally undefined function $\bot$ (read "bottom"), which is
thus always correct when it is defined.

Note that this does not prove termination of the algorithm. But you get that easily by induction.

Some further explanations.

This proof is in a way very similar to the proof suggested by Yuval
Filmus. It is not too surprising as they are both supposed to prove
the same result. However they are quite different in spirit. Yuval's
proof is a recursion on the steps of an actual interpretation of the
program (operational semantics). The proof I am proposing is by
recursion on the structure of the program code seen as an infinite
program defined as the limit of an infinite sequence of finite program
(denotational semantics). It assumes continuity properties (so that
passing to the limit makes sense), which are verified for usual
computing operations and predicates.

The former proof is on the use of the program, while the latter is on its structure.


Is λx. a valid Lamda Calculus abstraction? For demonstration purposes I was wondering about some very easy to grasp LC abstractions and I came to the idea of a function that simply eats its argument, and nothing more.

If you apply λx. (Yes no lambda term after the point) to an argument the abstraction reduces to nothing.

Although this isn't very useful for computation maybe, do you think the idea itself is valid or not?

Ok thanks everyone. Although I still like to tinker with the idea in my head, I understand it's simply not an option to use this throwaway function when dealing with LC.

Every application in LC returns an expression. There are no birds in the forest of Smullyan that can not sing.

Thanks again.

No, $\lambda x.$ is not a syntactically valid expression. By the definition of the syntax of lamda terms,

  $\lambda x.M$ is a term if $x$ is a variable and $M$ is a term.

You need a term $M$ to abstract over, and there are no empty terms. (This also means that there can be no application that reduces to "nothing". Any lambda term must consist of at least an atom (= a variable or a constant)). So $\lambda x.$ is not a term.


Proving an algorithm wrong So I have this algorithm that outputs the largest value of an array:

Input: $A[1,\dots,n]$, $n\geq 1$
Output: Largest value of an array

Maximum (A)
  m = A[1]
  i = 1
  while i < n
    if A[i+1] > A[i]
      m = A[i+1]
    i = i+1
  return m

I have to prove this algorithm wrong and I'm confused how to do that, because to me the algorithm seems correct. Any advice on how to do this are very much appreciated.

Consider the input $100,0,1$.

As a follow-up, identify the bug, and correct the algorithm.


Condition for infinitude of the language of a finite state automaton There is a theorem which says that:

  Given a finite state automaton having $n$ states, if there exists a string $w$ whose length satisfies $n \leq |w| \leq 2n-1$ then the language accepted by the automaton is infinite.

I understand the constraint $|w| \geq n$, but I don't understand why the constraint $|w| \leq 2n-1$ is there.

The additional condition allows you write a straight-forward algorithm -- check all strings with lengths in this interval -- for deciding (in)finiteness of the accepted language. Thus, you get a proof that this property is decidable (which it isn't for most automata models with super-regular power).


Find the grammar for the given language $L = \{ w: |w| \bmod 3 \geq |w| \bmod 2 \}$

I know, when the length of strings is not $3, 9, 15, 21,\dots,$ they will be members of the given language but unable to write a grammar for this language.

Please confirm one more thing, that this given language is regular?

Note that this language excludes all strings of length divisible by 3 but not by 2, i.e., of length $3, 9, 15, 21,\dots$.

Consider languages
$$L_1 = \{w\mid |w|=2k, k\geq 0\}$$ and $$L_2 = \{w\mid |w|=3k, k\geq 0\}$$
They are regular, since it is very easy to design DFA for both languages; the first has three states, the second has four states. The complement of the language $L$ is equal to $L_2-L_1$, and by the closure properties of regular languages $L=\overline{L_2-L_1}$ is also regular.


Logic of multiple variables in ILP Is there a better way to represent an AND of $n$ variables together other than creating $O(n)$ new variables and constraints?

There's a straightforward way to represent the logical AND of $n$ variables $x_1,\dots,x_n$: add the linear inequalities $y \ge x_1+ \dots + x_n-(n-1)$, $y \le x_i$ for each $i$, and $0 \le y \le 1$.


Stable matching problem is greedy or Dynamic? Is the stable matching problem greedy or Dynamic ? Please anyone can give a strong explanation as i tried to find it on the net but it isn't available.

If you consider the Gale–Shapley algorithm, it takes a greedy approach.

By the definition of Wikipedia:

  A greedy algorithm is an algorithmic paradigm that follows the problem
  solving heuristic of making the locally optimal choice at each stage
  with the hope of finding a global optimum.

The Gale-Shapley Algorithm does exactly that. At each step, the 'proposers' take a greedy decision of selecting the best partner (locally optimal choice) that was not yet proposed.


How to convert the left recursive grammar into right recursive grammar I have a grammar: $A\rightarrow Aa|bB|c$

The above is the left recursive grammar.
I understand that I have to remove the string "Aa" from the above grammar or to convert it into the form "aA" to avoid left recursive.

Some body please guide me how to do that.

Consider where "a" terminals can appear in a string produced by this grammar. Based on that, you should be able to split the "A" nonterminal up to make a right-recursive grammar that matches the same strings.

(Also, your "B" nonterminal appears to be missing...? Or just has no productions?)


A pretrained model for mathematical equations characters detection I am working on a project to convert equations to LaTeX code. After segmenting out the characters, I got stuck on the detection part and was looking for some pre-trained model that could detect characters of the equation for later conversion to LaTeX. Is there any such pre-trained model available on the internet that could be used in Python to identify characters. If not then can somebody share some source to find a dataset to train such kind of model in Keras? I was able to find one on GitHub but It doesn't detect symbols accurately.

Detexify is a service that recognizes LaTeX symbols from handwritten figures. Their training dataset is freely available on Github.


can we do binary search to solve quadratic equation? Suppose i have a quadratic equation like this, 2x^2 - 4x - 5 = 0, the solution here is x1=2.87 and x2=-0.87. I tried this python snippet to find the non-negative solution(2.87) by setting range 0 to 1000 and it worked but how to find the negative one too?. I tried the range -1000 to 0, but no luck!

def solve():
    low, high=0,1000
    while (high-low)>10e-5:
        x = (low+high)/2
        fx = 2*(x**2)-4*x-5
        if fx>0:
            high=x
        else:
            low=x

    return low

print(solve())

Or I am doing this whole thing wrong? What is the strategy to work with negative ranges and floating numbers in binary search?

Consider the value of fx on line 6.

def solve():
    low, high=-1000,0
    while (high-low)>10e-5:
        x = (low+high)/2
        fx = 2*(x**2)-4*x-5
        if fx<0:
            high=x
        else:
            low=x

    return low

print(solve())

or

def solve():
    low, high=-1000,0
    while (high-low)>10e-5:
        x = (low+high)/2
        fx = 2*(x**2)-4*x-5
        if fx>0:
            low=x
        else:
            high=x

    return low

print(solve())


What exactly would stop me from registering a domain from my own nameserver? Can I just make a nameserver and claim away? Are there implemented measures to stop this from happening?

Nothing stops you from setting up such a nameserver.  However, this wouldn't be of any use to you, because no one is going to contact your nameserver to ask whether domainexample.com exists: they're only going to contact the official name server for .com.

It'd be like saying "can't I lie about the location of the White House if anyone asks me?" -- well, yes, I can, but if no one ever asks me that, then this isn't achieving much.

What prevents you from lying about .com?  People aren't going to ask you; they are going to contact the root nameserver and ask that question.  How do people know who the root nameservers are?  The root nameservers are publicly known (specified in a RFC) and hardcoded in everyone's DNS software.  So ultimately the recursion bottoms out.

That's why setting up your own nameserver won't help you: no one is ever going to ask your nameserver anything or have any trust in it, so its lies won't affect anyone.


Movement on Labyrinth with Best First Search I have the following labyrinth where R is the robot(the parent node), red blocks are the obstacles where the R cannot move and GOAL is the node where we want the robot to go. Every node should be written in this form R(1,2,4), 1 is the row, 2 is the column and 4 is the distance from the current node to the goal node GOAL.

I am in a position where the solution tree looks like this

Now, I don't know which node should I select C or D ? Both of them have the same distance to the goal.

It doens't matter which one you take, because they both have exactly the same value. Which one actually gets taken will depend on unimportant details of the implementation, such as the order the nodes were added to the tree.


Knapsack up to the heaviest item There are $n$ items with weights $w_1,\ldots,w_n$ and values $v_1,\ldots,v_n$. There is a knapsack with capacity $W$. A subset of items is called feasible up to heaviest item if, once the heaviest item is removed from the subset, the weight of the remaining set is at most $W$. The knapsack up to heaviest item problem is to find a subset that maximizes the total value subject to being feasible up to one item.

I was trying to solve this problem, and I think I found that it is NP-hard - by reduction to standard knapsack problem. Given a standard knapsack problem, construct a knapsack-up-to-heaviest-item problem as follows.

There are $n+1$ items: the $n$ items in the original problem, plus one "big item".
The big item has value $v_B > \sum_{i=1}^n v_i$ and weight $w_B > \sum_{i=1}^n w_i$.
The size of the new knapsack is $W+w_B$.

In the new problem, any optimal solution must contain the big item, since if it does not contain the big item, the sum of weights in the knapsack is less than $W+w_B$, so the big item can be added and the solution is still feasible.  Moreover, in any optimal solution, the heaviest item is the big item. Hence, once the big item is in the knapsack, the problem is equivalent to the original knapsack problem.

My questions:

Has this problems been studied before?
Is my hardness proof correct?

The problem (are there items such that all except the largest fit, and the total value is ≥ V) is obviously in NP. It is also NP complete because we can use it to solve Knapsack:

Given a knapsack problem, add an item with sufficiently large weight w, and sufficiently large value v, solve the problem with V + v, and the solution with the large item removed is the solution for the knapsack problem.

We can also solve this problem using knapsack: For each item with weight w and value v, solve knapsack removing this item and all items with weight > w and a goal for the value of V - v.


Validity of list of articulation points in a graph after a node is deleted Say I have a bidirectional graph G and I have the list of articulation points and bridges of this graph. Say, the list of articulation points is ap[] and the list of bridges are bridges[]. Now, if I remove a node which does not belong to the list of ap[], meaning, this node is not an articulation point and deleting this node will not divide the nodes of this graph into different connected components. Now, do I have to update the list of the articulation points ap[]? I mean after deleting the node, is it possible that some more node(s) in the graph will become articulation points? The same question is for the list of bridges. If I remove an edge which is not a bridge in the graph, after deleting it, is it possible that some more existing edge(s) will become bridge?

Yes and yes. Look at this graph:

$V=\{1,2,3,4\}$
$E=\{\{1,2\},\{2,3\},\{3,4\},\{4,1\}\}$

There is neither articulation point nor bridge. But if you delete any node/edge...


How to predict the next image in a sequence, or predict the deblurring of an image? I have 3 versions of an image at lower resolutions - 480p, 720p, and 1080p. Is it possible to use those 3 images to predict the next highest resolution image (the 4k image)?

My first guess was that I could calculate the difference (or momentum or acceleration?) of each pixel between images and use that to predict the new 4th image. I assume this would require me to give all pictures the same number of pixels. I also assume that the differences in each pixel between images would need to be smooth. Would this work?

My other guess was that maybe there is some kind of statistics or machine learning technique that I could use, but I don't know anything about that stuff.

Thanks!

Ps - this man is not my real data. My real images are an intensity map (temperatures over an area) at different resolutions. I suspect that the introduction of colors might complicate things, so should we pretend that the images below are black-and-white images?

Here are the pictures:

No.  You can't create information out of nothing.  There's no magic.  There's not enough information in the three lower-res to uniquely determine the high-res image.

Of course, you can always upscale an image, but that won't make it any higher quality or sharper than what you started with.

Note that "4K" is a marketing term, not a precise specification of an image resolution.  There are multiple different resolutions that are all marketed as "4K".  See https://en.wikipedia.org/wiki/4K_resolution.


Time complexity of finding an integer between $x$ and $2x$ Consider receiving as input $x\in\mathbb N$ and computing some (any) prime $p\in[x,2x]$.

  What is the complexity of the above problem?

A natural way to approach this problem is to generate random integers in $x,\ldots,2x$ and check for their primality using Miller-Rabin or a deterministic algorithm such as AKS.

However, this may be suboptimal. What is the best-known runtime for the problem?

You can speed up this algorithm somewhat by generating a random integer which is coprime to all small primes. This can be done efficiently using a sieve: pick an appropriately sized random interval inside $[x,2x]$, and cross off all integers in the interval which are multiples of small primes (you can do this efficiently by finding the first multiple of a given prime, and then iterating over the remaining multiplies). Now use your favorite algorithm to find a prime within the integers not ruled out. The size of the interval should be chosen so that it guarantees that there is a prime (so about $\log x$ or somewhat larger).


Can we always transform a set of lines to a function? If I have n lines in a programming language like Python (globally or inside a function):
..
..
# from here
..
..
..
..
# to here
..
..

or
def example():
    ...
    ...
    # from here
    ...
    ...
    ...
    ...
    # to here
    ...
    ...

can I always transform it to a function of the form s1, s2, s3 … = function(s1, s2, s3 ...), where:

s1, s2, and s3 etc are the local/global variables created/updated after the n lines gets executed.
function is almost the same code as the n lines above except it collects them and returns them?

As an example, in the below function:
def example():
    ...
    ...
    # from here
    ...
    ...
    a = 'c'
    b = 'd'
    ...
    ...
    # to here
    ...
    ...

I know I can do this:
def example():
    ...
    ...
    a, b = transform('a', 'b')
    ...
    ...

But my question is if I can extend this idea to any arbitrary n lines of code, abstracting them as an input-output block?
According to me, the only thing that happens after any n lines is executed, is a state change (as far as the program is concerned) - which can always be represented as a function with an input and output.
Am I missing something? Can someone please clarify?

The short answer is yes. The longer answer is no.

The short answer is yes: that's a fundamental computation operation and it's pretty much the definition of a function. The equivalence between

def f(x):
    do something with x
f(foo)

and

do something with foo

is in fact the definition of a function, or more precisely of function application. This is so fundamental that it's the basis of the lambda calculus. In the lambda calculus, there are just three syntactic constructs:

variables ($x$, $y$, …);
applying a function to an argument ($F X$ where $F$ is a function and $X$ is the argument);
lambda abstraction $\lambda x. M$ where $x$ is the parameter name and $M$ is the function body.

The lambda calculus gets its name from that $\lambda$ notation, and it's where Python got lambda. In the lambda calculus, there is a single computation rule, called beta conversion (beta reduction when done from left to right, beta expansion from right to left):
$$ (\lambda x. M) N \equiv M[x \leftarrow N] $$
where $M[x \leftarrow N]$ means to replace $x$ by $N$ in $M$. (Details omitted because it would take a book chapter or two.) That single rule is enough to express all possible computations, in the sense that the lambda calculus is Turing-complete.

Beta conversion can be done in any language that has something that can reasonably called a function. But you need to take care of the details, and there are some language features that require additional effort or make it impossible in certain cases. Pretty much any language that isn't purely functional has restrictions on when beta expansion is correct.

In any language, the lines that you move to the new function must form a syntactic block. For example, if you have lines that are part of a multi-line construct like

while condition():
    instruction1()
    instruction2()

then you can move the loop out as a whole, but you can't move out while condition(): instruction1() and keep instruction2() in place.

One superficial but easily understood feature where beta conversion changes the behavior is introspection features. For example, if the language exposes a way to identify the current function or the function call stack trace, such as traceback.extract_stack() in Python, beta conversion changes that trace. If you put a call to traceback.extract_stack in a new auxiliary function, it's going to return something different. To make a beta-expansion that preserves the behavior, you'd need to modify calls to traceback.extract_stack to remove the new function from the trace. Note that this includes calls that may be deeply nested (if a function called inside the moved code calls a function that calls a function that … that calls traceback.extract_stack), so doing a fully behavior-preserving beta expansion turns into a global program transformation.

Another introspection feature of Python that breaks beta conversion is that it exposes local variables through locals(): locals()['x'] evaluates to the same value as x. If the code that you move calls locals(), you also need to pass the variables accessed through locals() as arguments to the new function and return their new values. So it isn't a purely syntactic transformation anymore.

A more interesting interaction is with flow control features. If the instructions that you put in the new function have self-contained flow, meaning that they're executed by starting at the top and either finishing at the bottom or raising an exception, then beta expansion or beta conversion doesn't change anything. It's ok if the code has loops and function calls inside it. But if the block of code that you move contains a non-local exit, i.e.  an instruction that makes the execution jump outside that block of code such as return or break, you can't just move it. Likewise if the block contains a jump target (in imperative languages that have goto). It's possible to get around this with a local transformation: make the auxiliary function take one more argument which indicates the entry point (if there's a way to jump into the middle of the code), and one more return value which indicates where to exit to (if there's a way to jump out to a place other than the end of the code block). For example:

def outer_function(x):
    if x == 1: return 2       #
    else: x = x - 1           #
    return x

If you want to extract the two lines marked with # on the right into a function, you need to remember whether to return the 2 or continue on to return x.

def new_auxiliary_function(x):
    if x == 1: return "RETURN", 2
    else: x = x - 1
    return "FALLTHROUGH", x
def new_outer_function(x):
    tmp = new_auxiliary_function(x)          #
    if tmp[0] == "RETURN": return tmp[1]     #
    x = tmp[1]                               #
    return x

Your transformation also changes exactly when variables are modified. This can become an issue due to aliasing. Aliasing is not normally an issue in Python since there's no way for a variable to designate another variable, as opposed to designating the same object as another variable. I wouldn't swear that it's never an issue, but I can't think of a way to do it. So instead I'll give an example in C, where aliasing is common due to pointers.

int x = 3;
int *p = &x;
*p = 2;                    //
printf("%d\n", x);         //

This code prints 2, since the pointer p points to x and the line *p = 2 therefore sets x to 2. Now let's create an auxiliary function for the part marked with //. Since C can't create compound values on the fly, we need to define a structure type for the return values, but that's just a cosmetic change compared with Python.

typedef struct {
    int x;
    int *p;
} values;
values new_function(int x, int *p) {
    *p = 2;
    printf("%d\n", x);
}
…

int x = 3;
int *p = &x;
values tmp = new_function(x, p);
x = tmp.x;
p = tmp.p;

The line *p = 2 in new_function sets the outer variable x to 2, since that's where p points to. It does not change the variable x that is inside new_function. Therefore this program prints 3.

When a compiler performs a beta reduction, it's called inlining. This is a common optimization, which typically makes the program run faster at the expense of larger code size. Compilers much more rarely do beta expansions. It's a worthwhile optimization when the same block of code (or more generally similar-enough blocks) appears more than once and code size is more important than execution speed, but it's difficult to detect worthwhile cases. Both transformations have limitations as to exactly when they're correct.


Average of all sums of subarrays I ran into a very hard question.
We have array of $n$ integers. for $1 \leq i \leq j \leq n$. we want to set $c_{ij}$= Sum of all values in the range $i$ to $j$ of this array. we want to finding average of all possible $c_{ij}$ in this array. if 4 basic operation in math $(+,-,*,/)$ can be done in $O(1)$. the best algorithm can be works in $O(n)$.
this example is example from my made easy preparation class. anyone can describe me in simple words how this algorithm can be?

It's not so clear what is meant by "sum of all values in the range $i$ to $j$". This probably means the sum of entries in locations $i$ to $j$.
Let us denote the entries of the array by $a_1,\ldots,a_n$. The entry $a_k$ is counted in those $c_{ij}$ such that $i \leq k \leq j$. There are $k(n+1-k)$ of these, out of a total of $\binom{n}{2}$. Therefore the quantity you are interested in is
$$
\frac{1}{\binom{n}{2}} \sum_{k=1}^n k(n+1-k) a_k.
$$

Here is another interpretation, in which we sum all values in the array which belong to $\{i,\ldots,j\}$. Even this can be solved in linear time!
Suppose that some entry of the array has value $k$. What is its contribution to the average of the $c_{ij}$? It is counted in some $c_{ij}$ iff $i \leq k \leq j$. Out of the $\binom{n+1}{2}$ many $c_{ij}$'s, there are exactly $k(n+1-k)$ in which the entry is counted, therefore its contribution to the average is
$$
\frac{k(n+1-k)}{\binom{n+1}{2}} \cdot k = \frac{2k^2(n+1-k)}{(n+1)n}.
$$
Summing this over all values in the array, we obtain the desired $O(n)$ algorithm.


Optimize a linear recurrence $$\begin{align*}
  T[1] &= 1 \\
  T[2] &= 2 \\
  T[i] &= T[i-1] + T[i-3] + T[i-4] & \text{for \(i \gt 2\)} \\
\end{align*}$$

I have to calculate $T[N]$, but $N$ is too big ($\approx 10^9$), how can I optimize it?

As Bartek commented, you are missing a base case. You can compute large values of $T$ in several ways:

Bartek's suggestion: Use an array to store all the entries computed so far.
You can optimize the previous method, dramatically reducing the memory needed: store only the last $4$ entries of the array at each point in time.
Use matrix powering. There are vectors $x,y$ and a matrix $A$ such that $T[N] = x'A^N y$. This approach is very similar to the previous one.
Find an explicit solution to your recurrence $T[N] = \sum_{i=1}^4 c_i \lambda_i^n$ (there are other possible forms, but this is the most probable), and use this formula to calculate $T[N]$ directly.


Is this lower bound proof for the comparison-based sorting problem correct? Here is a lower bound proof for the comparison-based sorting problem:

Any comparison-based sorting algorithm can be considered to work by putting elements into their final positions one by one (Take the last time one element is put into its final position.).
To put the element $e$ which is the $i$-th one being put into its final position, the algorithms should know the relative ordering between $e$ and the first $n-1$ elements that are already put into their final positions. This costs at least $\Omega(\lg i)$ comparisons.
Therefore, the total number of comparisons is at least
$$\sum_{i=1}^{n-1} \lg i = \Omega(n \lg n).$$

Is this a reasonable proof? (I am quite confused about the second step.) If so, how to formalize it more rigorously?

No, I don't think it's a reasonable proof.  This makes claims without justification.  For instance, the second bullet says that the only way to put an element into its final position is (the algorithm must know something..).  How do you know that is correct?  How would you prove that?  What does it even mean for an algorithm to know something?  Why does knowing that cost at least $\Omega(\lg i)$ comparisons?  All of that seems a bit unclear to me, so I don't find it a persuasive proof.


Directed graph where DFS returns on a node before all its child nodes are visited? Give an example of a directed graph in which a depth-ﬁrst search backs
  up from a vertex $v$ before all the vertices that can be reached from
  $v$ via one or more edges are discovered.

My professor recently asked this question as a warm up to lecture, but never answered it. I still have not figure how that is possible. Why would it return if it's not complete?

I just can't see a scenario where this would happen.

It would never return, since DFS is (essentially) recursive and it can't return without having hit all base cases.

Consider the following graph. If DFS will first go to the second node, it will back up even though the third node is reachable from the second.


Which bound is better, a logarithmic or a polynomial with arbitrarily small degree? I have a randomized approximation algorithm which can be tuned by selecting the randomization probabilities. I found out that:

For any $\epsilon >0$, there are probabilities for which the approximation factor is $O(n^\epsilon)$.
There are probabilities for which the approximation factor is $O(\ln n)$ (smaller factor is better).

I know that $O(\ln n)$ is asymptotic smallerer  than any $O(n^\epsilon)$ when $\epsilon$ is fixed, but here $\epsilon$ can be made arbitrarily small, so I don't know, which of these two bounds is considered better? Specifically:

A. Theoretically, which of these two bounds should I report in a paper? Is the bound $O(n^\epsilon)$ interesting, or is it considered useless given the logarithmic bound?

B. Practically, if I have to run the algorithm on very-big-data, with no possibility of making tests in advance, which tuning is better?

(Just to get some feeling, I compared $n^{0.1}$ with $\ln n$. It turns out that $n^{0.1}$ is better even for very large $n$ - they become equal at about $n=4 \cdot 10^{15}$)

Since $\log n = O(n^{\epsilon})$ for an $\epsilon > 0$, if you can prove an approximation ratio of $O(\log n)$, then approximation ratios of $O(n^{\epsilon})$ (for any $\epsilon > 0$) immediately follow. You should always prove the best approximation ratio that you can, unless:

The best approximation ratio holds only in expectation, and some other approximation ratio holds with high probability.
You have several incomparable approximation ratios (this is more common in expressions involving more than one parameter).

That is, your worse guarantee needs to have some advantage over your better guarantee for you to report both.

Regarding practical performance, you are highlighting the fact that asymptotic performance can be misleading when it comes to evaluating algorithms in practice. The most well-known instance is probably "fast" matrix multiplication, which is usually slower than the trivial algorithm. Here you have two options:

Prove non-asymptotic guarantees on the approximation ratio, say $100\log n$ and $(2/\epsilon)n^{\epsilon}$. This allows you to obtain concrete guarantees for every $n$.
Do experiments. The experiments reveal the actual approximation ratio on the average. If you can fit your results to a nice function, you can say that empirically, the average approximation ratio is (say) $10\log n$, though in the worst case all you know is (say) $100\log n$. Experiments, however, are not so welcome in theoretical papers, unfortunately.


Given two DFA's accepting the same language, does one have to refine the other? I have a logical question that I can't quite crack:

Given two automata accepting the same language $L$, does one have to refine the other?

In other words, if $A_1$ and $A_2$ both accept $L$, with associated equivalence relations $R_{A_1}$ and $R_{A_2}$, does $R_{A_1}$ have to refine $R_{A_2}$, or vice versa?
I am leaning toward the answer yes because if we have a regular language $L$ which is accepted by an automaton $A$, we can show that the relation $R_A$ refines the relation $R_L$, meaning $R_A \sqsubseteq R_L$,
which means that both $R_{A_1} \sqsubseteq R_L$ and $R_{A_2} \sqsubseteq R_L$.
We are currently studying the Myhill-Nerode Theorem, so I'm guessing it has something to do with it.
I've tried combining few theorems together, but came out empty.

For an integer $n$, consider the following DFA $A_n$ on the alphabet $\{a\}$. The set of states is $\{q_0,\ldots,q_{n-1}\}$. The initial state is $q_0$. All states are accepting. The transition function is $\delta(q_i,a) = q_{i+1}$, where we identify $q_n$ with $q_0$.
Do the relations of $A_2$ and $A_3$ refine each other?


Combinatorial optimization problem - What would you call this? I'm trying to solve an optimization problem which can be described as follows.

There are four sets objects. For simplicity, let's call them :

Apples
Oranges
Pears
Lemons

The sets can contain unequal numbers of their respective objects
These objects must be organized into groups containing exactly one of each object
Each possible group can be evaluated by some merit function (ie: function of the difference between the masses of the constituent objects of the group, say)
The maximum number of groups with a merit function below some threshold must be formed with the objects in the input sets.
In the above set of groups, no object can be duplicated - it must belong uniquely to one group.

My question is not necessarily how to solve this problem - this is no doubt an extremely broad question.  What I would like to know is whether or not this problem has, or is of a class of problem, with some formal name.

Primarily, I'm looking for search terms to help research similar problems (and the types of solutions that are known for it).

It's called four-dimensional matching and it's NP-complete.


Name of a tree with arbitrary number of branches at each fork point? A binary tree is a rooted tree with the root having an indegree of 0 and all other nodes of 1. The outdegree is 0, 1 or 2 for all nodes.

How do you call a rooted tree if the number of branches per node is arbitrary (outdegree of n) but the indegree 1 for all nodes other than the root node?

Rooted Tree

  How do you call a rooted tree if the number of branches per node is arbitrary (outdegree of n) but the indegree 1 for all nodes other than the root node?

That is none other than an rooted tree itself or, more accurately, an arborescence or branching tree or out-tree according to the following quote from Wikipedia entry on rooted tree.

  A rooted tree is a tree in which one vertex has been designated the root. The edges of a rooted tree can be assigned a natural orientation, either away from or towards the root, in which case the structure becomes a directed rooted tree. When a directed rooted tree has an orientation away from the root, it is called an arborescence, branching, or out-tree; when it has an orientation towards the root, it is called an anti-arborescence or in-tree.

Multitree

Your are also interested in what you might call "Poly-hierarchical rooted graph".

  An arbitrary rooted tree could also be a poly-hierarchy as far as I understand, with some nodes having an indegree > 1 i.e. multiple parents.

However, since every vertex other than the root has a single parent in a rooted tree by definition, it is not a viable idea to call them "Poly-hierarchical rooted tree". The conventional name for them is multitree as illustrated below, thanks to Wikipedia.

  A multitree may describe either of two equivalent structures: a directed acyclic graph in which the set of nodes reachable from any node form a tree, or a partially ordered set that does not have four items $a$, $b$, $c$, and $d$ forming a diamond suborder with $a\le b \le d$ and $a\le c \le d$ but with $b$ and $c$ incomparable to each other (also called a diamond-free poset).

Polytree

You might be interested in polytree, as illustrated below, thanks to Wikipedia again. It is "also known as oriented tree or singly connected network". It is "a directed acyclic graph whose underlying undirected graph is a tree."

Hasse Diagram

Another related concept is Hasse diagram, which is "used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction", as illustrated below.

Exercise 1. Draw a polytree that is not a rooted tree. Draw a multitree that is not a polytree. Draw a Hasse diagram that is not a multitree.

Exercise 2. Every rooted tree is a polytree. Show that every polytree is a multitree. Show that every multitree is the Hasse diagram of some finite partially ordered set.


Existence of one and two state PDAs I came across following fact in Automata book by Hopcroft, Ullman:

  Theorem 1: For every PDA accepting by empty stack (PDAeS), there is an equivalent one state PDA accepting by empty stack.

I was wondering how this applies to:

PDA accepting by final state (PDAfS)
Deterministic PDA accepting by empty stack (DPDAeS)
Deterministic PDA accepting by final state (DPDAfS)

My understanding is, it applies equally to PDAfS, since I read in the book that both PDAfS and PDAeS are of equal power. Am I right? Also what about DPDAs?

Also I came across this post, which states:

  Theorem 2: All PDAs are equivalent to two state PDAs.

I want to know what all variants (PDAfS, PDAeS, DPDAeS, DPDAfS) it refers to by PDA? Reading the explanation given in the problem itself, my guess is that it is possible with PDAeS and DPDeS. Am I right?

Added later

I came across two more theorems in the book:

  Theorem 3: For every regular language L, there is DPDAfS, such that L = L(DPDAfS)
  Theorem 4: For every regular language L, there is one state PDAeS, such that L = L(PDAeS)

So in all above highlighted theorems (total four, two originally stated and two added later), I want to know to what they apply? PDAeS, PDAfS, DPDAeS, DPDAfS.

So let me enumerate problems explicitly:

(From theorem 1)

For every PDA, is there equivalent one state PDAfS?
For every DPDA, is there equivalent one state DPDAeS?
For every DPDA, is there equivalent one state DPDAfS?

(From theorem 2)

Is all PDAs are equivalent to some two state PDAeS?
Is all PDAs are equivalent to some two state PDAfS?

(From theorem 3)

For every regular language L, is there DPDAeS, such that L = L(DPDAeS)? (details in Update 1)

(From theorem 4)

For every regular language L, is there one state PDAfS, such that L = L(PDAfS)?

Update 1

Realized that the answer to 6th question is no. DPDAeS are not even capable of generating all regular languages. This leads to the possible next question:

Cant any DPDAeS generate any regular language?

PS:

Sorry, if you didnt like how I am referring to PDAs with fS and eS suffixes (which mean "acceptance by final state" and "acceptance by empty state" respectively). But I find it very convenient.
Sorry for asking absolutely too much on one post. But all those problems form a part of one big problem: how FAs, PDAeS, PDAfS, DPDAeS, DPDAfS and their variants (one state and two state) generate each other.

For final state acceptance one needs two states in general. The reason is simply that one needs to distinguish accepted and not-accepted strings. That is why single state PDAf are not a very useful concept. But if you have one, the prefix of every accepted string will itself be also accepted. These languages are prefix-closed.

If a deterministic automaton with empty stack acceptance indeed accepts a string, there is no longer string that can be accepted. The reason is that with empty stack in the classical model of Hopcroft&Ullman the automaton blocks, no steps are possible. Here determinism is important because nondeterministic automata just may have alternative computations on the same string. These languages are prefix-free.

Let me summarize.

The answer to question 1, question 3 and question 7 [single state with final state acceptance] is "no" as not every (D)PDA language is prefix closed, for example regular $(aa)^*$, or in fact finite $\{a,aa\}$.

The answer to question 2 [single state, deterministic, empty stack] is "no", as not every DPDA language is prefix-free, examples as before.

The answer to question 4 and question 5 [two states] are "yes", see Yuval's answer. These results are 'classic'. Perhaps you want to know the deterministic version of these results?

For question 8 observe that DPDAe's can accept 'any' regular language when the end of the string is marked by a special symbol. This makes the language immediately prefix-free.


is conflict possible In accepting state of LR(0)? Consider the following grammar:

Stmts -> Stmt | Stmts;Stmt

Stmt -> Var =E

Var ->id[E] | id

E-> id | (E)

in accepting state we get

S' -> stmts .

stmts -> stmts . ;stmt

isn't it a conflict ?

I don't think there is a real conflict here.

It does look like a shift/reduce conflict but if you are at
the end of the input there is no ";" symbol that can be shifted so only reduction to S' applies.

There are ways you can deal with things that look like conflicts near the accepting state.

One is to have a pseudo token for end of input.
This distinguishes a parse where you consume all the input from one where you have
unconsumed tokens (garbage) remaining.

If you have a choice between which rules to apply you can have a preference for a reduction to the start symbol and thus to accepting rather than applying further rules.


Bubble Sort with "while" loop - why is average case n^2? If Bubble Sort is written as:

    while True:
        False
        for i in (0 to n - 2):
            if list[i] > list[i + 1]:
                swap.(list[i], list[i + 1])
                True
    return list

(where n is len(list))

Seems to me that in the worst case (a list in descending order):

the while loop runs $n$ times
the for loop runs $n - 1$ times per while loop $∴$ there will be $n^2 - n$ comparisons
the list is in decreasing order so there will ultimately be $(n^2 - n)/2$ swaps
$∴$ worst case is $O(n^2)$

In the best case (a list already sorted):

the while loop runs $1$ time
there will be $n - 1$ comparisons
the list is already sorted so there will ultimately be $0$ swaps
$∴$ best case is $\Omega(n)$

So for the average case...

the while loop will run more than $1$ time but less than $n$ times
there will be more than $n - 1$ but less than $n^2 - n$ comparisons
there will be more than $0$ but less than $(n^2 - n)/2$ swaps, depending on the state of the list
$∴$ how can we show that the average case is also $n^2$ and $\Theta(n^2)$?

I don't understand where $n^2$ can be observed?

Is it because the number of swaps will always be equal to $(n^2 - n)/x$, where $x$ is determined by the state of the list?

And, as stated here (and in other places), on average, with uniform distribution, the number of swaps would be  $(n^2 - n)/4$, which is half the worst case?

I'm confused :( Any help would be appreciated! Thank you.

Let's prove a more general result:

  Any sorting algorithm which only swaps adjacent elements makes $\Omega(n^2)$ swaps on average.

Let us assume that the elements being sorted are $1,\ldots,n$, and their positions are $i_1,\ldots,i_n$. We need to move element $j$ from position $i_j$ to position $j$. Each swap changes the position of two elements by 1. It follows that the number of swaps is at least
$$
\frac{1}{2} \sum_{j=1}^n |i_j - j|.
$$
The marginal distribution of each $i_j$ is uniform over $\{1,\ldots,n\}$, hence the expected number of swaps is at least
$$
\frac{1}{2n} \sum_{i=1}^n \sum_{j=1}^n |i-j| = \frac{n^2-1}{6}.
$$


Understanding $\text{handle}$ in parsing problem Originally https://math.stackexchange.com/questions/22614/help-understand-texthandle-in-parsing-problem but unaswered there

The BNF is defined as followed:

S -> aAb | bBA
A -> ab | aAB
B -> bB | b

The sentence is:

aaAbBb

And this is the parse tree:

Phrases: aaAbBb, aAbB, bB
Simple Phrases: bB
Handle: ?

From the book, handle is defined as followed:
B is the handle of the right sentential from $y = aBw$ if and only if:
$S \to_{rm} \cdot aAw \to_{rm} aBw$

So in my case, what's the handle? Any idea?

I'll assume you talk about the 'handle' as often defined in the context of LR-parsing. I'm not entirely sure if the definition you use is the proper definition: $A$ and $B$ seem to stand for nonterminals, but $B$ should really stand for some string of terminals and nonterminals (as the right hand side of a production of $A$, to be precise) to have a proper meaning.

Let's parse your example using LR machinery, and illustrate what happens. In particular, we'll find multiple handles during the parse. The dot '$\bullet$' will show where in the parse we are at the moment. We're looking for suffixes of the part to the left of the bullet that exactly match productions of our grammar.

$\bullet aaAbBb$ - we're starting at the beginning.
$a \bullet aAbBb$ - moving on, '$a$' is not a handle as it is not a production.
$aa \bullet AbBb$ - moving on, '$aa$' or '$a$' is not a handle as it is not a production.
$aaA \bullet bBb$ - '$A$', '$aA$' and '$aaA$' are not productions.
$aaAb \bullet Bb$ - '$b$' and '$aAb$' are candidate handles (they are right-hand sides of productions), but your parse tree shows that neither gets reduced, so we ignore them.
$aaAbB \bullet b$ - '$bB$' is a handle! We reduce it to $B$.
$aaAB \bullet b$ - '$aAB$' is a handle! We reduce it to $A$.
$aA \bullet b$ - '$A$' and '$aA$' are not productions.
$aAb \bullet$ - '$aAb$' is a handle! We reduce it to $S$.
$S \bullet$ - Oh hey, we're done: the input was part of the grammar.


Number of words within Hamming distance $\delta$ This is a problem I'm having reading Arora & Barak's book, page 378-379.  They define:

  For two words $x, y \in \{0, 1\}^m$, the fractional Hamming distance of $x$ and
  $y$ is
  equal to the fraction of bits on which they differ, i.e.  $\frac{1}{m} \cdot  |\{i : x_i \neq y_i\}|$, where the $x_i$ refers to the $i$-th bit of $x$ (same
  for $y_i$).

Now, in the proof of Lemma 18.9, they use the fact that

  for every string $y_i$ of $m$ bits, the number of strings
  that are of distance at most $\delta$ to it is ${m \choose \lceil \delta m \rceil}$

meaning that there are ${m \choose \lceil \delta m \rceil}$ words that disagree on not more than a $\delta$ fraction of bits.

But, I can't convince myself of that.
Suppose for simplicity that $y_i = 0000 \ldots 000$.  Here are the words that are of distance at most $\delta m$: all the words that have exactly one $1$, or two, or three, up to $\lfloor \delta m \rfloor$ of bits set to $1$.  Thus I rather think that this number is

$$
\sum_{k = 1}^{\lfloor \delta m \rfloor} {m \choose k}
$$

Can anyone explain?

That's an inaccuracy. If $\delta < 1/2$ is constant then it is the case that $\sum_{k=0}^{\delta m} \binom{m}{k} = O\left(\binom{m}{\delta m}\right)$, since the binomial coefficients increase very fast until they finally level out around the central binomial coefficient. The hidden constant depends on $\delta$. (When $\delta$ is close to $1/2$ this doesn't hold: for example, $\sum_{k=0}^{m/2} \binom{m}{k} = 2^{m-1}$ for even $m$, while $\binom{m}{m/2} = \Theta\left(\frac{2^m}{\sqrt{m}}\right)$.)

At any rate, what they are interested in really is the estimate $\sum_{k=0}^{\delta m} \binom{m}{k} \leq (1-\epsilon) 2^{H(\delta)m}$, which holds for every $\epsilon > 0$ and large enough $m$ (depending on $\epsilon,\delta$).


Why does the following function distribute things in a binomial distribution? I was reading the following FDS paper:

https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf

and it says that the the following hash function does not distribute things uniformly (instead it creates a binomial distribution):

$$i = (hash(g + t)) \pmod n$$

while the following did distribute things uniformly:

$$i = (hash(g) + t) \pmod n$$

Why does the above distribute things evenly while the other one doesn't?

g = is the global UID for a blob

t = tract number. (tract is the measure/units of reads and writes to a blob).

n = is the number of tract servers or a multiple of the tract servers.

hash = SHA-1 (according to the paper)

Paper Reference:

Title: Flat Datacenter Storage

Author(s): Edmund B. Nightingale, Jeremy Elson, Jinliang Fan, Owen Hofmann, Jon Howell, Yutaka Suzue

Institution(s): Microsoft Research, Univeristy of Texas at Austin

The second function is easier to explain: it sends tract $t$ to position $t + h \pmod{n}$, where $h = hash(g)$. The function $t \mapsto t + h \pmod{n}$ is injective (one-to-one), and so every index $i$ gets mapped exactly once (in fact, by $i - h \pmod{n}$).

For the first function, we can think of $t \mapsto hash(g+t)$ as a random function (this is a common assumption whenever hash functions are involved; the fact that we use SHA-1 is completely irrelevant). Therefore for each fixed index $i$, the probability that $t$ is mapped to $i$ is $1/n$, and the total number of $t$s mapped to $i$ is distributed $\mathrm{Bin}(1/n,1) \approx \mathrm{Po}(1)$, that is it has binomial distribution which is approximated well by a Poisson distribution with mean $1$.


P, NP and polynomial time reduction? If $P = NP$ would this imply that polynomial time reduction from an $NP$- to a $P$-problem would be possible? And if $P\neq NP$ does it imply that a polynomial time reduction from an $NP$- to a $P$-problem would be impossible?

Since $P \subseteq NP$, every problem in $P$ is also in $NP$. So in both cases there is an $NP$-problem that can be reduced to a $P$-problem. Simply choose a problem in $P$ as the $NP$-problem and the same problem as the $P$-problem.

If you replace $NP$-problem by $NP$-complete problem, both of your statements hold.


Example of Random Binary Tree? I'm trying to understand what a random binary tree is. According to Wikipedia:

  Two different distributions are commonly used: binary trees formed by
  inserting nodes one at a time according to a random permutation, and
  binary trees chosen from a uniform discrete distribution...

If I start with a root and then append nodes randomly with no consideration to depth. Would that be considered a random binary tree? Or am I missing something?

A random binary tree is any tree that is generated by any random process.  So, yes.  You have described a random process that generates a binary tree; you can describe the result as a random binary tree.

At a technical level, if you have any random variable whose values are binary trees, it would be reasonable to call that a "random binary tree".

Wikipedia is saying that there are two random processes that are particularly commonly considered.  But those aren't the only possibilities.  You've described a third possibility, and that's also valid.