Why does it seem as if I can apply the Pumping lemma to a language that is regular? We learn about the Pumping Lemma at the class and I tried to make few examples to understand it...

There I make this example:
Let's say: $L=\{w\in L|w=(0+1)^*1\}$ - i.e. - L is the language of all the words that finish with $1$. (The language is regular of course).

Now, I can take the word: $w=0^{n-1} 1$. $w\in L$ and $|w|\ge n$.
I can take: $u=0^{n-1},v=1,z=\varepsilon$.
$|uv|\le n$ and $|v|>0$, but:
$uv^0z\notin L$ because $uv^0z$ ends with $0$...

What I miss here?
I'd like to understand more where is my mistake...

The pumping lemma says that, for every regular language there exists some pumping length $p$* such that blah blah blah.

You made two mistakes. First, you tried to choose $p$ based on a specific word, rather than based on the language as a whole. Second, you chose the wrong value of $p$. In particular, for the language you've given, $p=1$ has the property required of the pumping lemma: for every word $w$ in that language, you can write $w=\epsilon y z$ with $|y|=1$, and you'll find that $\epsilon y^n z$ is in the language for all $n\geq 0$.


First half of context-free palindromes If $L\subseteq\Sigma^*$ is a regular language, then $\text{mir}(L) = \{ww^R \mid w\in L\}$ is context-free. This is a nice exercise.

Question: does the reverse hold? Thus, if $\text{mir}(L)$ is context-free, do we always have $L$ is regular?

Yes.

Sándor Horváth, J. Karhumäki and H. C. M. Kleijn characterized the context-free languages consisting only of palindromes in their paper Results Concerning Palindromicity, 1987.

Theorem. A context-free language $L\subseteq\Sigma^*$ is palindromic, iff it is of the form
$$ L= \bigcup_{x\in\,\Sigma\cup\{\lambda\}}\{uxu^R : u\in L(x)\}$$

where the $L(x)$ is a regular language uniquely determined by $L$ for all $x \in\Sigma\cup\{\lambda\}$.

In particular, the theorem tells that a context-free languages that consists of only palindromes of even length must be of the form $\{uu^R : u\in L\}$ for some regular language $L$.


Is there a formal difference between $f:X \to X$ and $f\in X \to X$? We can denote by $X\to X$ the set of all functions from $X$ to $X$.
Therefore, we can use the following statement to say that $f$ is a function from $X$ to $X$:
$$f\in X\to X$$

But we usually state instead

$$f:X \to X$$

In fact, we could say that $X\to X$ is defined as $\{f| f:X\to X\}$. If I'm not mistaken, $:$ is a notation that belongs to type theory, rather than set theory as $\in$ does.

So is there a fundamental difference between these two notations? Does it make sense to say that one of the two is more "fundamental" than the other?

No, they're mostly notational variations. There are different connotations to the different notations, and different notations are common in different fields where they can mean quite different things. Also, sometimes they are used in a particular context for different (but usually related) things. You'll, of course, have to see how it has been defined in that context.

Any use of $\in$ usually strongly suggests a set-theoretic context (though you occasionally see it in a type-theoretic context). The $f:X\to Y$ notation was, I believe, popularized in mathematics by category theory. In this case, it means $f\in\mathsf{Hom}(X,Y)$. This is compatible with $f\in Y^X$ in the case that the category is the category of sets and functions. In a general categorical context, $Y^X$ is usually reserved for exponential objects for which it makes no sense to ask if $f\in Y^X$, though you (usually) can ask if there is an arrow $1 \to Y^X$.

In logic, when $X$ and $Y$ are sorts, usually $f:X\to Y$ means that $f$ is a function symbol. In this case, $X$ and $Y$ aren't sets and neither is $X \to Y$. It makes no sense to say $f\in X\to Y$ unless $\in$ isn't being thought of as set membership or we want to say $X\to Y$ means the set of function symbols from $X$ to $Y$. This latter view starts to get rather similar to the categorical view.

In type theory, usually $f:X\to Y$ means something like $f$ has type $X\to Y$ and $X\to Y$ is the type of functions from $X$ to $Y$. Types are not sets and part of the purpose of this notation is to remind one of that fact. Indeed, types are more like sorts and this notation is similar to how it is used in logic. Sometimes $Y^X$ is also used where $Y^X$ is used in a more first-class sense in a way that is compatible with the similar distinction I mentioned for category theory, so we might write $X\to Z^Y$ rather than $X\to(Y\to Z)$. Sometimes no distinction is being made and the notation is completely synonymous and the choice is made purely for typographical reasons. For computer programming, the choice is mostly typographical, f : X -> Y is easier to write and easier to read, though programming languages are also closely related to type  theories.

It doesn't really make sense to talk about which of these notations is "more fundamental" than the others in general. That said, the $f:X\to Y$ notation is usually making the least commitments if multiple notations are in use. Often $f:X\to Y$ isn't a proposition with a truth value, so it wouldn't make much sense to write $\{f\mid f:X\to Y\}$. Admittedly, in the context where it isn't a proposition, you usually aren't using set theory. If you really wanted to, you could meta-theoretically write $\{t\mid \cdot\vdash t:X\to Y\}$ to mean the set of closed terms of type $X\to Y$, say. This would have nothing to do with a set of functions though.


Is the relation between the input and output of an arbitrary algorithm describable by a mathematical function? I hope that this question is clear, and not off-topic:

I have been reading about neural networks (in the AI sense), and the textbook said that an artificial neural network can always be described by a single mathematical function (rather than by an "algorithm" in a register-machine, which is the standard way I intuitively look at an AI neural network).

So this made me think: is it possible for any arbitrary algorithm, meaning an arbitrary Turing machine, to be simulated by a mathematical function? (I do not mean a function as used in programming languages).

By simulated in this case I mean that given any arbitrary input in the algorithm, that function produces the same output as the algorithm.

Suppose $M$ is a Turing machine which halts for all inputs $x\in\Sigma^*$, then we can define the corresponding function $f_M$ in the following way:

$$
f_M(x) = \begin{cases}
             1,  & \text{M accepts x} \\
             0,  & \text{otherwise}
       \end{cases} \quad
$$

$f_M(x)$ is a legitimate mathematical function from $\Sigma^*$ to $\left\{0,1\right\}$, it does not care about concepts such as "machine" or "algorithm" or any implementation you have in mind. Obviously the function $f_M$ was tailored for the machine $M$, but this does not make it illegitimate in any way.

You could ask whether i can describe the output of $M$ using a simple function? Perhaps using only the four basic arithmetical operations (we can treat the input strings as numbers represented in binary). The term you should look up in this regard is expressibility, what functions can your model express? For example, when talking about neural nets, the more neurons we use, the bigger our expressive power gets (we can implement more functions).

Note that the converse is not true, not every function can be described by a Turing machine (look up the arithmetical hierarchy, a famous example is the halting problem, but we got a whole hierarchy of even "harder" functions).


Isoecursive Types When to Fold and Unfold I'm trying to implement recursive types into my programming language. I've implemented extensible rows and was hoping to add some recursive typing in order to get something like this or self within a record (thus imitating objects). Recursive types would only occur in record definitions, like

record IntObject:
  val: int
  add: (IntObject -> IntObject)

Now IntObject is an alias for the type mu X. {val: int, add: (X -> X)}.

This represents an IntObject with a field val that has the type of a primitive integer, and an add method that takes in an IntObject and returns another IntObject, so I can use it like so:

IntObject(1).add(IntObject(2))

The definition of add would be something like.

record IntObject:
  def add(self, other):
    return IntObject(self.val + other.val)

Like in Python, instance method invocations have a reference to the object calling the method implicitly passed in as the first parameter. I'm not sure how Python does this, but I was thinking of doing the partial application of the instance methods at object creation. Therefore,

IntObject(1)

creates a record like this (using Haskell lambda syntax)

{val: 1, add: \other -> IntObject.add(self, other)}

I tried reading TAPL's section on recursive types, and isorecursion seems much easier to implement, especially since I will only allow records to have recursive types. What I'm unsure about is when to add folds and unfolds. TAPL says

  In Java each class definition implicitly introduces a recursive type, and invoking a method on an object involves an implicit unfold.

This is exactly what I want to do. If invoking a method introduces an unfold, that means that there needs to be a fold somewhere, and I'm unsure where to introduce that fold.

If this question is too vague, specifically since I probably haven't given enough information about the current state of my language, a general answer would suffice. Any advice regarding where to introduce folds and unfolds in an OOP language, say Java, would help a ton.

As you've stated, the type of IntObject is mu X. {val: int, add: (X -> X)}. fold and unfold witness the isomorphism between a recursive type and its body, i.e. in this case between mu X. {val: int, add: (X -> X)} and {val: int, add: ((mu X. {val: int, add: (X -> X)) -> (mu X. {val: int, add: (X -> X)))}. Letting Y stand for mu X. {val: int, add: (X -> X)}, this can be more compactly written unfold : Y ~= {val: int, add: (Y -> Y)} with fold going the other direction.

You need unfold whenever you want to access any fields/methods. mu X. {val: int, add: (X -> X)} doesn't have any fields; {val: int, add: (Y -> Y)} does. Dually, whenever you want to make an IntObject, you need to use fold. A value of type {val: int, add: (Y -> Y)} is not an IntObject, but fold can inject that value into the type IntObject. In particular, any time you new up an IntObject, i.e. invoke the constructor to create an object.

Basically, your IntObject(i) "really means" something like

let self = fold({val: i, add: \other -> IntObject.add(self, other)}) in self

Similarly, your add method would look like:

def add(self, other):
    return IntObject(unfold(self).val + unfold(other).val)

where we'd use the definition of IntObject just mentioned above.


Can nodes in red-black trees have one nil child and one non-nil child? I don't recall hearing that nodes in red-black trees can't have one nil child and one non-nil child. However, I did hear that red-black trees have a worst-case height of $2log_2(n + 1)$, where n is the number of nodes, and I don't see how this could be the case if nodes can have one nil and one non-nil child, as a tree could be constructed that is simply a straight line/linked list, which would have a height of n.

Can nodes in red-black trees have one nil child and one non-nil child?

Yes. A red-black tree is a special case of binary search tree: each node is colored red or black. In red-black tree, if a child does not exist, the corresponding pointer field of that node contains the value NIL. NILs are treated as leaves.

  red-black trees have a worst-case height of $2 \log 2(n+1)$

The fact that the height is of $O(\lg n)$ is guaranteed by the red/black coloring rules (copied from CLRS):

A node is either red or black.
The root is black.
All leaves (NIL) are black.
If a node is red, then both its children are black.
For each node, all paths from the node to descendant leaves contain the same number of black nodes.

These rules, especially rules 4 and 5, ensure that the tree is approximately balanced: no any path is more than twice as long as any other. In terms of tree height, we have

  A red-black tree with $n$ internal nodes has height at most $2 \lg (n+1)$.

Finally,

  how this could be the case if nodes can have one nil and one non-nil child, as a tree could be constructed that is simply a straight line/linked list, which would have a height of $n$.

By the red/black coloring rules, a non-trivial (with enough number of nodes) red-black tree cannot be a straight line/linked list.

For more details, you may want to read the book "Introduction to Algorithms" by CLRS.


Pairwise comparisons with confidence There is a lot of information available on the subject of Pairwise Comparisons but I haven't found any guidance on how to optimize pair measurements that have confidence values attached to them.

Imagine that an AI black box has been trained on many pairs of objects in order to predict the distance between the objects in novel pairs. All objects are colinear. The black box also provides a confidence level for each distance. Here is a simple example of outputs based on a set of 5 objects ($a$ to $e$):

Pair, Distance, Confidence

a-b,  5,        0.4
a-c,  9,        0.7
a-d,  -3,       0.9
a-e,  2,        0.6
b-c,  6,        0.8
b-d,  -10,      0.7
b-e,  -2,       1.0
c-d,  -6,       0.5
c-e,  -2,       0.6
d-e,  7,        0.9

So, the distance between $a$ and $b$ is predicted to be 5 units ($b$ is to the right of $a$) and the black box's confidence in that measurement is 0.4 (0.0 = no confidence and 1.0 = perfect confidence). The distance between $a$ and $d$ is -3 units ($d$ is to the left of $a$) and the confidence is 0.9.

I would like to understand the process for deriving the solution, which is the optimization of the four distances between these objects given the predicted distances and their associated confidence levels.

There are several possible ways to solve this problem. One way is to assume some measurement model (usually Gaussian noise) and then find the maximum likelihood solution.

That is, we start with some distribution of the measured distance given the actual distance  and the noise level, for example if the actual distance is $d$ and the noise level is $\sigma$, then perhaps the measured distance is distributed $N(d,\sigma)$.

Given a sequence of measurements, for each potential list of positions (say with $a=0$ to break the symmetry), we can calculate the likelihood that we would get the actual measurements. In your case, we would get
$$ L(a,b,c,d,e) = \frac{1}{\sqrt{2\pi} 0.4} e^{-(5-(b-a))^2/(2\cdot 0.4)} \cdot \frac{1}{\sqrt{2\pi} 0.7} e^{-(9-(c-a))^2/(2\cdot 0.7)} \cdots. $$
The idea is to find the setting of $a,b,c,d,e$ that maximizes $L(a,b,c,d,e)$. To that end, we can calculate
$$ -\log L(a,b,c,d,e) = C + \frac{(5-(b-a))^2}{2\cdot 0.4} + \frac{(9-(c-a))^2}{2\cdot 0.7} + \cdots.$$
We want to minimize the latter. We can substitute $a = 0$, and then differentiate with respect to each of the other variables, and equate to zero. For example, differentiating with respect to $b$, we obtain
$$ 0 = -\frac{\partial \log L}{\partial b} = \frac{b-5}{0.4} + \frac{b-c+6}{0.8} + \frac{b-d-10}{0.7} + \frac{b-e-2}{1.0}. $$
In this way, we get linear equations which we can solve for $b,c,d,e$. (This is the method of least squares.)

For other models of noise, we might have to use numerical optimization instead. You can find more examples in any machine learning textbook.


How can I make the variance of a multiple sum of set of fixed number of variables minimum? Here is the problem:
There are $MN$ people, where there are $M>1$ seeds and $N>0$ people are in each seed.
We have to make $N$ teams of $M$ people where everyone in the team have different seeds.
Each person have their own value; values are positive integers.
Assume there are no two people with same values.
For two distinct seeds $I$ and $J$, we say $I<J$ if for all $x\in I$ and $y\in J$, $x<y$ holds.
It is guaranteed that for any two distinct seeds $I$ and $J$ in the problem, $I<J$ or $J<I$ holds. In other words, we can set $M$ seeds $I_1,I_2,\cdots,I_M$ in the problem to satisfy $I_1<I_2<\cdots<I_M$.
I am interested in two versions of this problem:

There are no paired people. This means in process of making $N$ teams, there is no restriction except given above.
There may be some paired people. This means a set of paired people that cannot be split is given, so that if a team contains one person from some pair, the team should also contain the other person from that pair. It is provided that every pair contains exactly two people from different seeds.

For each version, the task is to design an algorithm to make the variance of the sum of values of people in each team to be minimum.
Since this problem is NP (complete?), I would accept heuristics.
I hope that the heuristic method gives the solution with variance at most $25\%$ larger than the optimal solution, as I don't want to harm the balance of the team.
Could you please give an algorithm or heuristic that can solve this problem? Also, adding a time complexity would be highly appreciated!

If you're willing to replace 'variance' with 'max minus min' (spread), then you could formulate this as an instance of integer linear programming and apply an off-the-shelf ILP solver.  There is no guarantee that it finds an optimal solution in a reasonable amount of time, but if you're lucky, it might complete without taking too long; or if you stop it early, you might get a decent solution.
To formulate this as an instance of ILP, add zero-or-one variables $x_{i,j}$, with the intended meaning that $x_{i,j}=1$ means that person $i$ is assigned to team $j$.  Each requirement in the problem statement can be expressed as a linear inequality; for instance, the requirement that everyone in a team has a different can be expressed by inequalities of the form $x_{i,j} + x_{i',j} \le 1$ for each pair $i,i'$ of people from the same seed.
To minimize the spread, introduce variables $\ell,u$.  Let $v_i$ denote the value of person $i$ (this is a constant, not a variable).  Add linear inequalities $\ell \le \sum_i x_{i,j} v_i \le u$ for each team $j$.  Finally, minimize $u-\ell$, subject to the inequalities above.
If you want to use the variance, this becomes a mixed-integer quadratic program instead of a mixed-integer linear program, and I think quadratic programs are significantly harder.


What's an intuitive distinction between semi-computable problems and noncomputable problems/functions? The definitions I've found were highly technical and using terms I've never seen before.

Say, I have a certain irrational number e that I get get closer and closer to with a computer and I want to determine if there is a particular digit d appearing after a certain position. Or what about the halting problem (give a program and ask 'will the computer ever halt?')? Are these problems semi-computable problems or noncomputable?

Intuitively, a set of numbers is computable or decidable or recursive if there is an algorithm deciding membership for the set. A set of numbers is semidecidable or recursively enumerable (r.e.) if it has verifiable "proofs" of membership. For example, the set of programs which halt is semidecidable, since given a program $A$ and a time bound $t$, one can check that $A$ halts after at most $t$ steps. But this set is not computable, since without the time bound, we don't know how long to wait for. (That's an intuitive explanation; you can google for a proof that the halting problem is not decidable.)

There are several equivalent definitions of semidecidable sets:

A set $S$ is semidecidable if there exists an algorithm $A$ which always terminates with either YES or NO as an answer, such that $x \in S$ iff there is a witness $w$ for which $A(x,w)$ answers YES.
A set $S$ is semidecidable if there exists an algorithm $A$ such that $x \in S$ iff $A(x)$ halts.
A set $S$ is semidecidable if there is an algorithm that enumerates all members of $S$.

See if you can show that all these definitions are equivalent. You might want to look up the technique of "dovetailing".

What about the digits of $e$? We need to phrase the problem of computing the digits of $e$ in our framework. The set of digits of $e$ is the set of pairs $(k,d)$, where $d$ is the $k$th decimal digit of $e=2.71828\ldots$, i.e. $\{(0,2),(1,7),(2,1),(3,8),(4,2),(5,8),\ldots\}$. Since there is an algorithm computing the $k$th digit of $e$ (e.g. using the Taylor series $e = \sum_{k=0}^\infty 1/k!$), the set of digits of $e$ (under this encoding) is computable.

Edit: Following the OP's comment, suppose we're interested in the set of positions $n$ such that the decimal expansion of $e$ contains the digit $2$ somewhere past the $n$th digit. This set is decidable, for the following reason: either the digit $2$ appears infinitely often, or its last appearance is at digit $N$. In the first case, the set in question contains all natural numbers, in the second case it is $\{0,\ldots,N-1\}$.

The same trick works for any fixed real number. Consider, however, the set consisting of pairs $(A,n)$ such that $A$ is an algorithm that enumerates the decimal expansion of some real number, which contains the digit $2$ somewhere past the $n$th digit. This set is not computable, only semidecidable, since one can reduce the halting problem to it and vice versa (how?).


Big Theta for finding combinations of arbitrarily sized subsets from n total elements Given n elements, where the n elements are grouped into arbitrarily sized subsets, what is the Big Theta (tight bounds) of outputting all permutations of items from each subset?

Assume the elements are all unique.

For example:

n=2, `a b` there are two cases.
`(a), (b)` which has one permutation 1: `a, b`
`(a, b)` which has two permutations 1: `a`, 2: `b`

And then for a larger n:

n=3, `a b c` there are three cases.

3 subsets of 1 element: 1^3 permutations
`(a), (b), (c)` which has one combination 1: `a, b, c`

1 subset of 2 elements and 1 subset of 1 element: 2^1*1^1=2 permutations
`(a, b) (c)` which has two combinations 1: `ac`, 2: `bc`

1 subset of 3 elements: 3^1=3 permutations
`(a, b, c)` which has two combinations 1: `a`, 2: `b`, 3: `c`

Basically for a given n its the maximum value of S1*S2*S3... where S# is the size of subset #.

It's easy enough to demonstrate that big lambda is 2^(n/2).

And I think that 3^(n/3) may be a big omega.

I've been mulling this problem over for a little while now, if it's a known problem then I'd love to be pushed towards the right solution, but I've found that it's a bit difficult to search for.

If we denote by $q(n)$ the number of permutations, the first few values are
$$\begin{array}{ccccccccc}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
q(n) & 1 & 1 & 3 & 6 & 14 & 25 & 56 & 97
\end{array}$$
This sequence can be found at the online encyclopedia of integer sequences, which is a really helpful site. It has a lot of information about the sequence in question, including the fact that you were right in your guess that $q(n)=\Theta(3^{n/3})$.

[Yes, I'm aware that this doesn't answer all of your question, since this only counts how many permutations there are, and doesn't enumerate them.]


Why does Slotted Aloha work? So the way I understand it, if station A and station B, for example, try to transmit a frame at the same slot, a collision occurs, leading to an attempt at the next slot. But wouldn't the algorithm just repeat itself? The same two stations would try again on the second slot and it would still cause a collision. Also, it means that the first slot would remain unused.

Am I understanding it wrong?

This is a good question. As you study more, will find that all the Aloha protocol variants are highly inefficient and ambiguous. And yes, slotted Aloha’s central concept seems to suggest that a collision sparks an infinite loop of data collision. Let’s look at the (only) two tenets of the Pure Aloha protocol from UOH, 1971:

If any device has data to send, send it
If a collision occurs, scrap and try again later

Slotted Aloha is just an extension of Pure Aloha that adds one more tenet:
Data must be sent at regular intervals (slots)

The use of regular intervals increases efficiency significantly.

Now, about collisions, observe the following diagram:

Source: Wikimedia

Notice how devices C, F, and H encounter a collision when they all try to send data in the same interval? Device C tries to resend the data right away, device F waits for a few frames and device H has yet to try sending the data again.

When it comes to the Aloha protocols, what does one mean by sending the data “later”? One second from now is later. Three slots is later. Two years is later. That is up to each device to decide.

If later means the same frame for every device, than yes, infinite collision will occur. This is why a quality method must be developed to prevent this behavior. In programming this is called a back-off scheme.

A predictable and efficient back-off scheme will attempt to implement a probable generation of frames (both new frames and repeats from data that collided) that reduces the probability of collision, such as a Poisson Distribution.

Recommend Reading: Poisson Distribution


It is decidable whether a pushdown automaton will accept a word? I'm asking myself if the problem of decide whether a push down automaton will accept a word is decidable.

I would say that you can simulate a push down automaton with a Turing Machine and, if it doesn't loop forever, accept the word when the automaton accepts, or reject when it does. In this case, the problem of decide if a push down automaton accept a word would be semi-decidable. But I'm not sure if that is correct and also, I can't find a way to prove if it is decidable or not.

Any ideas here?

Pushdown automata are nondeterministic, and there is no a priori bound on the length of computation (imagine $\epsilon$-transitions that add and remove the same element from the stack). Therefore it's not clear how to perform your simulation.

Fortunately, we know how to convert a pushdown automaton to an equivalent context-free grammar, and the latter have parsing algorithms such as CYK. Using these algorithms, we can dedice whether a given pushdown automaton accepts a word by first converting the automaton into a context-free grammar.


Deciding on Sub-Problems for Dynamic Programming I have used the technique of dynamic programming multiple times however today a friend asked me how I go about defining my sub-problems, I realized I had no way of providing an objective formal answer. How do you formally define a sub-problem for a problem that you would solve using dynamic programming?

The principle of dynamic programming is to think top-down (i.e recursively) but solve bottom up. So a good strategy for designing a DP is to formulate the problem recursively and generate sub-problems that way.


Clear interrupt instruction in a pipelined CPU Say you execute a clear interrupt instruction (CLI) in a pipelined CPU. While that instruction is being fetched, an interrupt occurs, so the instruction after the CLI is from the interrupt handler.
You excepted no interrupts because of the CLI instruction but you still got one. How is this problem solved?

Such a control hazard can be handled effectively the same way that a branch misprediction is handled. Either the CLI instruction commits and the interrupt handler fetch is treated as the mispredicted path and fetch is restarted after the CLI or the CLI instruction is not committed and the interrupt handler is treated as the correct path.


Looking for two-way communication/consensus/contract algorithm for use in marriage proposal I am looking for some sort of communication or consensus algorithm with the following properties:

Can be used with just two parties (and ideally doesn't collapse to a trivial case with two parties)
Requires each party to initiate some sort of communication to which the other responds (ideally in a binary way)
Non-hierarchical
Bonus points if it's some sort of consensus, decision-making, or contract signing algorithm

Context: my boyfriend and I are planning on getting engaged soon. For various reasons, we would both like to propose to each other. The challenge is that we don't want whichever proposal is second to feel like it was unnecessary. Since we're both computer scientists, we figure there must be an algorithmic solution to this problem! So we are looking for a communication protocol/consensus algorithm/something else in that vein in which it is necessary for both parties to initiate and respond to a communication. We will be implementing the chosen algorithm verbally, not over an actual internet connection. In case you're having a hard time picturing this, it would be kind of like how a lot of textbooks will have conversational English versions of the messages being sent under various communications protocols, e.g.:

Except we would replace "Hey. Can I talk to you?" with something more like "Will you marry me?".

Before anyone asks, yes, this is entirely symbolic/for fun, but we feel that's true of most aspects of getting engaged/married. And yes, we are nerdy enough that we will happily exchange random numbers with each other in public if that's what the protocol (or its associated cryptography) demands.

Possibilities we've considered so far:

TCP: This was our first thought, but it's not a great fit. For connection establishment all the server sends is a SYN-ACK, which isn't really satisfying either as a response to the first proposal or as the question being asked in the second proposal. The connection termination protocol seems like it would be weird to adapt to verbal communication.
Dining cryptographers: Would be great (although we'd have to use 0 to mean yes, which is a little gross), except it falls apart with only two parties. So we'd have to include a third person (and give them veto power over our engagement). It would be perfect for a polyamorous engagement, though!
Some sort of blockchain consensus algorithm: All the ones I'm aware of seem like they'd collapse to a trivial case with two parties (but I could be wrong about this)
Some sort of contract signing algorithm: Probably the best option we've found so far. These are the closest to being designed to solve the actual problem that we have, but all the ones I've seen require some sort of trusted third party (we could make that work but it wouldn't be ideal).

Does anyone know of an algorithm that is a better fit than these? Apologies if this is off-topic (I'm hoping it falls under "we do not hate fun")!

If you're feeling up for something particularly geeky, you might enjoy a fair exchange protocol, either one based on gradual release (see e.g., this paper) or one based on Bitcoin (e.g., this).  The number of steps is very large though!  Probably not suitable to carry out by hand.

You could try a simpler protocol:

Alice picks a message $m_A$, computes a commitment $C(m_A)$ to  $m_A$, and reveals the commitment $C(m_A)$.  For instance, maybe Alice writes down $C(m_A)$ in view of Bob.
Bob picks a message $m_B$, computes a commitment $C(m_B)$ to  $m_B$, and reveals the commitment $C(m_B)$ -- say, writing it down too.  (Steps 1 and 2 can be done simultaneously or in any order.)
Alice opens her commitment to reveal $m_A$ (e.g., she writes $m_A$ down on the piece of paper).  Bob verifies that the message matches her commitment.
Bob opens his commitment to reveal $m_B$.  Alice verifies that the message matches his commitment.  (Steps 3 and 4 can be done in any order; but they shouldn't be started until both Steps 1 and 2 are complete.)

In your case, Alice could choose as her message "Bob, will you marry me?" or "Bob, let's not get married yet" and Bob could choose as his message "Alice, will you marry me?" or "Alice, let's not get married yet" and then you could compare at the end.

There are various ways to do a cryptographic commitment.  One way is with a cryptographic hash function (you could use a web site to compute it for you).  A simpler method is to secretly write down the message on a piece of paper, then put the paper in an envelope, seal the envelope, and place the envelope on the table in front of both of you.

See, e.g., https://keybase.io/blog/cryptographic-coin-flipping for a gentle introduction to related ideas.

Another idea is to execute a two-phase commit protocol.


Calculate the sum of all sub-arrays with given indices I am new to Algorithms and Competitive Coding. I have a problem as follow:

For this problem, the time limit is 1 second so brute force is not a good way to solve. The only way I think must be Dynamic Programming or any other way which can run in less than O(nlogn) or even O(n) and the limit memory is 256 Mb.
Initially, I have a simple approach to dynamic programming as follows: I just create a table size nxn and fill it with numbers that represent the minimum element from the index I to index j (i <= j). After that, I refer to the given indexes (ik and jk) on the table and add them up.
However, as submitting the code as the previous approach, I get 3 cases of wrong answers and even runtime errors. The runtime error is due to the input constraint: up to 10^6 elements which cause the exceed of memory (10^6 * 10^6 = 10^12, which is very large). I also get accepted status on 3 tests however, the number of wrong answers makes me quite confused. I really need your help to check and update the algorithms.
Sample test case:
Input:

16

2 4 6 1 6 8 7 3 3 5 8 9 1 2 6 4

4

1 5

0 9

1 15

6 10

Output:

6

void make_table()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = i; j < n; j++)
        {
            if(i == j)
            {
                Table[i][j] = arr[i];
            }
            else
            {
                Table[i][j] = min(arr[j], Table[i][j - 1]);
            }
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    make_table();
    ll sum = 0;
    cin >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        sum += Table[x][y];
    }
    cout << sum << endl;
}
```

You can use the concept of segment trees. Check this link:
https://en.wikipedia.org/wiki/Segment_tree and https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
The above link works for finding the sum of all the elements in a given range [i,j]. However, you can use the same approach to find the minimum element in the range [i,j] in $O(\log n)$ time. The idea is that you can break the range [i,j] into $O(\log n)$ smaller ranges, and for each of these ranges you already know their minimum values via some binary tree (built during pre-processing step). Thus, you can take the minimum over all these small ranges, and it will give the overall minimum in the range [i,j] in $O(\log n)$ time.

Building the binary tree comes under the pre-processing step and it will only take $O(n)$ time.
Also, there are $m$ queries and each query takes $O(\log n)$ time. The overall time complexity would be $O(n + m \log n)$. Since $m < n$, the overall complexity is $O(n \log n)$.


How to interpret "Windows - Virtual Memory minimum too low" from a CS student point of view? On my old 256MB RAM, pc I get this message. (I guess it is quite common)

  Windows - Virtual Memory minimum too low
  Your system is low on virtual memory. Windows is increasing the size of your virtual memory paging file. During this process, memory requests for some applications may be denied. ...

Please explain from a CS student point of view-

"Windows is increasing the size of your virtual memory paging file." and
"during this process...". what is this process called?

Thanks, I am currently studying virtual memory management in OS.

A computer typically has vastly more hard disk space that RAM. To compensate for limitations in the size of RAM, the operating system reserves part of the disk to use as additional RAM. This is called virtual memory. The RAM and the virtual memory are then divided into even chunks called pages. From the programmer's perspective, there is a large amount of memory available. Under the hood, the operating system keeps some of the pages of memory in RAM and leaves the remainder in virtual memory, on the disk. The operating system tries to ensure that the more commonly used pages are in RAM, as this is more efficient. If a program needs to access memory that it stored on disk, the operating system swaps out a page from RAM and swaps in a page from the disk. This is called paging. Paging is expensive, so the operating system tries to reduce how often it occurs.

If the amount of memory demanded by a program (or the collection of running programs) exceeds the amount of virtual memory, it is possible that the operating system increases the amount of virtual memory. As virtual memory is essentially a file, this explains what is going on when "Windows is increasing the size of your virtual memory paging file."

The "process" you refer to could be called "increasing virtual memory". I'm not sure whether it has a special name.


Finding hit ratio of a cache Consider an array A[100] & each element occupies 4 word. A 32 word cache is used and divided into 8 word blocks. What is the hit ratio for the following statement. Assume one block is read into cache in case of miss:

for(i=0;i<100;i++)
  A[i]=A[i]+10

each array element is of 4 word & each cache block size is 8 words, so we load 8 words into cache.

When program tries to read A[0], for the first time it will be miss. Hence it will be brought to memory (& also A[1]). Next, A[1] will be hit. So, it will be like :

A[0] - Miss
A[1] - Hit
A[2] - Miss
A[3] - Hit
.....

So hit ratio is 50% ? Am I wrong anywhere ?

I also have one more doubt. First when it tries to access A[0], it will be miss. And then when it brings A[0] to cache, CPU tries to access A[0] again, now it should be considered as hit ? Like,

A[0] (Read) - Miss
A[0] (Write) - Hit
A[1] (Read) - Hit
A[1] (Write) - Hit

If above is correct, then Hit ratio will be 75%.

Any help regarding this is appreciated.

Since there is 8 word block, 2 element can stay in one block.
Now notice that each element is refered twice, one read and one write operation.
So when in a block when 1st element is refered for read, it will be miss, and hence that block will be copied to cache.
Now 2nd reference to that 1st element will be hit, as well as both reference to 2nd element will also ne hit sience block has 2 elements.
So out of 4 reference, 1 miss and 3 hit for one block. Gets repeated for each and every block.
So hit 3/4
and miss 1/4


Why there must be a relationship between user threads and kernel threads? The following is an excerpt from OS concepts by galvin.Here is the book.

Multithreading Models
Our discussion so far has treated threads in a generic sense. However,
support for threads may be provided either at the user level, for user
threads, or by the kernel, for kernel threads. User threads are
supported above the kernel and are managed without kernel support,
whereas kernel threads are supported and managed directly by the
operating system. Virtually all contemporary operating
systems—including Windows, Linux, Mac OS X , and Solaris— support
kernel threads.
Ultimately, a relationship must exist between user threads and kernel threads.

It then goes on to discuss Many-To-One Model,One-To-One Model and Many-To-Many Model.
Question :
Why there must be a relationship between user threads and kernel threads?
Does kernel thread here means a thread of the kernel(i.e OS)? I don't think so since it clearly specifies that it relates to support for threads.

This section of the book appears to be talking about how the details of the threading and scheduling are implemented for a user mode program.

When threading first became popular, most operating systems were Multi-processing OS's, but not "multithreaded" in the sense that the operating system provide support for multiple user code streams sharing the same user address space and allowing these threads to be scheduled separately by the OS.   Threading was a concept not dealt with by the OS at all.  The OS knew processes, what the processes did with the user mode time they were given was their business.

With User mode threading, support for threads was provided by a programming library and the thread scheduler was a subroutine in the user program itself.  The operating system would schedule the process to run and the process would schedule the threads within it.  There were problems with this model because an event on one thread that caused the OS to block the process effectively blocked all threads within that process.  This model only allowed the threads to run on a single CPU at a time, limiting parallelism.  This is the many to one mapping model listed in the book.  The single Kernel thread is the user process that the kernel schedules.

With Kernel threads, the OS becomes aware of the threads as separate schedulable entities that share the same address space.  The OS can then allow each thread to compete for CPU time separately with other threads in the system.  This allows the OS to schedule multiple threads from the same process on multiple CPUs at the same time. It also allows it run threads from a process where one thread is blocked, but the others have computable work to do.  In this case each user thread has a backing Kernel thread that is a schedulable entity.

The MUST relationship they are talking about is that even if you are using User threads there is an underlying Kernel thread that the OS can schedule. There MUST be a schedulable entity even if it's at the process level. So your first comment is correct.


How do bridges divide a larger network into smaller broadcast domains? I am recently brushing up my computer network knowledge, and came across a seemingly peculiar statement:

  A network bridge divides a network into smaller broadcast domains.

As far as I could grasp the details, a bridge operates on the two lower layers of the ISO OSI model - the physical and the data link layers.
What this means is bridge selectively forwards data link frames on the basis of the destination MAC address that can be found on each received frame.

But, the doubt arises when we consider the fact that the broadcasts are achieved using a broadcast IP address of that particular network. Now, due to the broadcast address being an entity/property of the network layer, should principally be not paid attention to by the bridge, and be flooded into all the interfaces available to it.

Then, how exactly does the bridge manage to filter the broadcast packets?

After quite a bit of research through YouTube and whatnot, I finally managed to find the answer.

A bridge (or a switch, both being data-link layer devices) DOES NOT divide the broadcast domains of the VLAN (the virtual LAN is formed by connecting the different physical segments using the bridge/switch).

A broadcast is sent with a special MAC address FF:FF:FF:FF:FF:FF (48 bits of 1s), of which the bridge/switch has no entry in its bridge table (and for that matter, will never have). The essential point to be noted here is that a bridge/switch follows a learning approach, in which until it is absolutely sure on which of it's port (or interface) a MAC address lies, it just forwards the frame to all the ports (except the one from which the frame has arrived). Hence, the bridge/switch, having no details of the destination MAC address of the broadcast frame, will go on to forwarding the frame to all of its ports (except one, the one from which it arrived).

What this means is that a bridge/switch cannot break the broadcast domain of the VLAN it is forming.

More related information:

https://youtu.be/reXS_e3fTAk?t=335


Why are multi-threading programs more prone to errors? Why are multi-threading programs more prone to errors than single threaded programs ? or why is multi-threading programming one of the areas where developers are (more) prone to errors? Is this in general or is it valid only for scenarios where there are shared resources being used by multiple threads ? Are the difficulties to detect errors or simulate bugs in multi-threaded programs just related to inexperience or immature tool support, or are they fundamentally more difficult than the same tasks for single threaded programs ?

Overview

Multi-threaded programs are more prone to errors than single-threaded programs because of the problem of concurrency bugs.  Concurrency is hard for most developers to reason about, which causes many bugs in multi-threaded programs; this issue normally doesn't arise in single-threaded programs, because single-threaded programs typically have no concurrency.

Mutable shared state, and plan interference

The core problem is due to the combination of multi-threaded programming plus mutable shared state.  If there was no shared state, or if all shared state was immutable, then you wouldn't have to worry about concurrency bugs.  But when you have mutable shared state, then the programmer has to start thinking about all possible interleavings of the thread A's accesses to the shared state with thread B's accesses to the shared state.  There can be exponentially many possible interleavings that the programmer needs to reason about, if they want to avoid concurrency bugs, and no surprise, that's non-trivial.

Mutable shared state introduces the possibility of data races and other kinds of concurrency bugs.  These can be tricky to reason about.

Multi-threaded programming makes it easy to have plan interference problems.  Programmers tend to think in a single-threaded way: they think about a single sequential path of execution.  When they're writing the code for a particular function/method/module, they build in their head a "plan" of the operations/actions they want to have happen, typically based on a single-threaded mental model (e.g., based on the implicit assumption that nothing else will interrupt them in the middle of this sequence of actions or concurrently modify their internal state).  However, when you have multiple threads with mutable shared state, they can cause unexpected interference while the code is in the middle of execution (changing something out from under the code while it is in the process of executing the programmer's plan).

For example, here is one classic example of plan interference.  Imagine you have a publish-subscribe data structure that lets clients register themselves as observers, and delivers events to all registered observers.  Imagine its code is in the middle of delivering an event to the observers, one by one, and the code of one of the observers happens to mutate the underlying state; this mutation might cause the notifications to the other observers to happen in the wrong order, or to expose an inconsistent state to them.

Further reading

For a more general description of the plan interference problem and more general discussion of why multi-threaded programming is more error-prone, I recommend the following papers:

The Problem with Threads.  Edward A. Lee.  IEEE Computer, May 2006.
Concurrency Among Strangers: Programming in E as Plan Coordination.  Mark S. Miller, E. Dean Tribble, and Jonathan Shapiro.  TGC 2005.  (See especially Sections 1-4.)

Candidate solutions

Multiple candidate solutions have been proposed:

One possible solution is to avoid using threads, and program in a sequential single-threaded way.  This is how Javascript works in browsers, for instance.
Another is to use threads but avoid all mutable shared state.  For example, Erlang.
A third is to use message-passing rather than mutable shared state for interaction between the threads.  One can build systems based on the actor model.  For example, E.
A fourth is to use threads with mutable shared state, but just be really careful.  You can have systematic ways of locking shared data and preventing data races and avoiding plan interference and so on.

See also https://cs.stackexchange.com/a/27803/755 for similar ruminations (I borrowed some text from there).


why it said the "The left recursion has been removed at the cost of an extra non-terminal symbol(E1) and a little extra complexity"? When I read the book "A Practical approach to compiler construction" the chapter 4 "approaches to syntax analysis" and the section 4.2.3.3 Left Recursion, it says:

  "The left recursion has been removed at the cost of an extra non-terminal symbol"

I have no idea why say that, since $A_1$ still contain recursion?

That grammar has recursion but not left recursion.  Check the definition of left recursion (e.g., https://en.wikipedia.org/wiki/Left_recursion, or consult your favorite textbook on formal languages).


Why the Goemans-Williamson's MAX-CUT algorithm relax the variables to vectors of $n-$dimension on unit sphere? Why not to some constant like 3 or 4 dimension? I suspect that it is because Cholesky Decompostion will work only for $n \times n$ matrix $B$ where $B^TB = P$ where $P$ is a semidefinite matrix. Is it true? Or there is something else?

The MAX-CUT algorithm relies on semidefinite programming, a convex optimization problem which can be solved in polynomial time. What you solve directly is the semidefinite program

$$
\begin{align*}
& \max \sum_{ij} w_{ij} \frac{1-a_{ij}}{2} \\
s.t. \quad& (a_{ij})_{i,j=1}^n \text{ is positive semidefinite} \\
& a_{ii} = 1 \text{ for all $i$}
\end{align*}
$$

Given a solution for this program, you can extract the vectors using Cholesky decomposition.

The problem you are interested in is different:

$$
\begin{align*}
& \max \sum_{ij} w_{ij} \frac{1-\langle v_i, v_j \rangle}{2} \\
s.t. \quad& v_i \in \mathbb{R}^d \\
& \|v_i\|^2 = 1
\end{align*}
$$

When $d = 1$, this is just MAX-CUT. When $d$ is constant, optimizing over $\{v_i \in \mathbb{R}^d : \|v_i\| = 1 \}$ is likely NP-hard. When $d = n$, this can be solved using the semidefinite program described above. This is why we allow the dimension to be unbounded.

If you could force the dimension to be small, then you could improve the approximation ratio of the algorithm, see for example Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT by Avidor and Zwick. Assuming the unique games conjecture, however, the approximation guarantee of the Goemans–Williamson algorithm is tight. This shows that even in the particular case of MAX-CUT, it is likely that finding a low-dimensional solution cannot be done efficiently.


Concise Way To Specify The Space Of All Python Programs Under A Certain Size And Running Time? Given the grammar of the Python language, is there a concise way to specify the space of all possible (and correct) Python programs?

To avoid the underlying halting problem, the specification would include a user-definable maximum program size and running time. This concise specification could then be fed to another program, a search/optimization algorithm to be precise, as the domain to operate in. And yes, I'm aware of how intractable such a space would be.

I don't know much about computer science or language theory, so any help would be appreciated.

You can't determine the running time of a generic program automatically, this is an undecidable problem similar to the Halting problem.

Maybe you can try to enumerate a very well defined subset of the possible codes up to certain size. But in order to be useful for an search/optimization algorithm (other than random search), this subset needs to be equipped with some sort of vicinity function. Moreover, this vicinity function should allow you to explore genuinely different programs. Preferably this function should form a connected space among all plausible programs in this subset, and have a short diameter so optimizer can succeed on the search. All that said, is pretty clear that the problem is far from being easy.

I read recently a very interesting post about applying genetic algorithm to produce brainfuck code to solve specific simple tasks. You can read it here. The post is from 2013, but there is no particular breakthrough in this area that I'm aware. This field is known as program-synthesis and there are a lot of teams working on it, most recently they are trying to use classic combinatorial algorithms boosted with deep learning to prune the search space.


Is every linear language in NL? I wonder if all the linear languages are in NL?

I was thinking that we can take an input-language $L$ and convert it to linear normal form. If this is not possible, the machine rejects. If the language can be written in linear normal form, the machine accepts. The work tape only needs to store the current production, so that it works in logarithmic time.

Am I completely lost or is this a good start?

The following survey states that the result is proved by Ibarra, Jiang, Ravikumar in Information Processing Letters (1988).

Unambiguous Auxiliary Pushdown Automata and Semi-unbounded Fan-in Circuits. Niedermeier R., Rossmanith, P.,  Information and Computation 118(2), 227-245, 1995.


Minimum edge deletion partitioning I'm interested in the time complexity of the following problem:

Given an undirected graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color the vertices in such a way that the sum of the weights of the monochromatic edges (i.e. those between same color vertices) is minimized.

The closest NP-hard problem I could find is the "minimum edge deletion k-partition" (https://www.nada.kth.se/~viggo/wwwcompendium/node43.html), however, in that problem $k$ is known and fixed beforehand, whereas in my problem, the  optimal $k$ (i.e. the number of different colors) is not known.

Any hints, pointers, comments are welcome.

I believe this problem is NP-hard and it can be shown by a reduction from the vertex coloring problem with $k$ colors.

Assume we are given a graph $G' = (E',V')$ and we want to decide whether there exists a coloring of the vertices in $V'$ using only $k$ colors. To do so, we construct a new graph $G$ that consists of $G'$ as well as the complete graph $K_k$. Furthermore, we add edges of weight $-1$ from every vertex in $G'$ to every vertex in $K_k$. The edges inside of $G'$ as well as $K_k$ on the other hand have a very large weight.

Now, I claim that $G'$ admits a $k$-coloring, if and only if we can color $G$ and achieve a profit of $|V'|$. To see this, we first observe, that due to the large weight on the edges inside of $G'$ and $K_k$, both sub-components must be colored in such a way that no adjacent vertices inside of them share the same color. For $K_k$, this trivially implies a $k$-coloring. Next, note that all vertices with matching colors between $G'$ and $K_k$ add a profit of one to the total profit. However, there can be at most one such edge between $G'$ and $K_k$ for every vertex in $G'$. This is exactly the case if $G'$ has a $k$-coloring (using the same colors that were used in $K_k$). Thus $G'$ admits a $k$-coloring if and only if we can find a coloring of $G$ with a profit of $|V'|$. This in turn implies NP-hardness of your problem.


What is considered an asymptotic improvement for graph algorithms? Lets say we are trying to solve some algorithmic problem $A$ that is dependent on input of size $n$.
We say algorithm $B$ that runs in time $T(n)$, is asymptotically better than algorithm $C$ which runs in time $G(n)$ if we have:
$G(n) = O(T(n))$, but $T(n)$ is not $O(G(n))$.
My question is related to the asymptotic running time of graph algorithms, which is usually dependent on $|V|$ and $|E|$.
Specifically I want to focus on Prim's algorithm. If we implement the priority queue with a binary heap the run-time would be $O(E\log V)$. With Fibonacci heap  we could get a run-time of $O(V\log V + E)$.
My question is do we say that $O(V\log V + E)$ is asymptotically better than $O(E\log V)$?
Let me clarify: I know that if the graph is dense the answer is yes. But if $E=O(V)$ both of the solutions are the same.
I am more interested in what is usually defined as an asymptotic improvement in the case we have more than one variable, and even worse - the variables are not independent ($V-1\le E<V^2$, since we assume the graph is connected for Prim's algorithm).
Thanks!

The most permissive definition is as follows.
Suppose that $f(V,E),g(V,E)$ are two running times of graph algorithms solving the same problem.
We say that $f$ is an asymptotic improvement in some regime on $g$ if there exists a sequence $V_n,E_n$ with $V_n \to \infty$ such that
$$
\lim_{n\to\infty} \frac{f(V_n,E_n)}{g(V_n,E_n)} = 0.
$$
Sometimes the regime is not deemed interesting, but that's a more subjective matter.
Note also that the problem already manifests itself for one-variable functions. Consider
$$
f(n) = n^2, \qquad g(n) = \begin{cases} 2^n &\text{if } n = 2^m, \\ n & \text{otherwise}. \end{cases}
$$
Is $f$ an asymptotic improvement over $g$? It is for inputs of a certain length, and is indeed so under our permissive definition above.


Finite state automata: final states In our programming language concepts course, our instructor claimed that it's okay for a final state to lead to another state in a finite state diagram.

But this seems to be a fundamentally contradictory concept. Because a final state by definition is one that terminates transitions, i.e., that once you reach it, there's nothing else left to do.

And yet he presented a slide such as this one, where final states are represented by two circles... How is it possible for B, D, E, and H to be final states when they're so clearly not?

You seem to have a misunderstanding of generative models v.s. "recognizing" models.

The grammar you have on the right generates words by applying rules, starting from the initial variable, and stopping after there are no more variables.

Automata, however, recognize a language as follows: you feed the automaton a word, letter by letter, and the automaton takes transitions based on the letters given to it.

If, after reading all the letters, the automaton ends up in an accepting (a.k.a final) state, then we say that the automaton accepts the word.

So it's better  to think of those as "accepting" states, rather than "final" states, although both terms are commonly used.


Proving that Pre(L) is regular using automatas: Should I prove that Pre(L) is the semantic of the new automata? Let $L$ be a regular language, and $Pre(L)$ be the set of all words that are prefix of some word in $L$. Prove that $Pre(L)$ is regular.
My proof:

Let $M = (\Sigma, Q, \delta, q_0, F)$ be an automata such that $\mathcal{L}(M) = L$ and $Q' = \{ q \in Q \ | \ (\exists q_f, w \ | \ q_f \in F \ \wedge \ w \in \Sigma^{*}: [q, w] \mapsto^{*} [q_f, \lambda]  ) \}$, that is, $Q'$ is the set of all states that have a path to a final state of $M$.
Hence, $M' = (\Sigma, Q', \delta, q_0, Q')$ is an automata such that $\mathcal{L}(M') = Pre(L)$. QED.

Is the last step right or should I now proof that the semantic of $M'$ is in fact $Pre(L)$?

If you are unsure whether it is right, yes, you should prove it!  This is a good general principle. If you are unsure whether or why a particular step is correct, there's a good chance a reader will be unsure, too -- so prove it in more detail until there is no doubt.


Advice speeds up computations I want to show that reasonable advice can really speed up computation.

Show, that every time-constructible function $t$, there exists a set $S$ in time $\text{DTIME}(t^2) \setminus \text{DTIME}(t)$ that can be decided in linear time using an advice of linear length, $S \in \text{DTIME}(l) /  l$ (definition in analogy to $P / \text{poly}$), where $l(n)=O(n)$.

The problem is that I cannot come up with the structure of set.

Hint: Start with a problem in $\mathrm{DTIME}(e^{2t}) \setminus \mathrm{DTIME}(e^t)$.


Spatial Locality in Cache - Which addresses are loaded? I don't quite understand the concept of spatial locality in cacheing. I understand that on a cache miss, not only the specific address we want is loaded into the cache, but also "nearby addresses" are loaded too.

However, I can't understand WHICH addresses are loaded. I have an assignment with the following question:

The cache consists of 16 words (4 bytes for each word), and is arranged in blocks of 2 words each.
The following addresses are in BYTES in decimal base. The cache is initially empty.
12,8,24,28,36,44,48,52,60,64,68,76,136,140,144,148,152,220,224,228,220,224,228
Determine what are the addresses which are a MISS (determine whether it's a valid or a tag miss).

What is hard for me is to understand which addresses are loaded, when, for example, the address 12 is reached. Is 13 loaded into the cache? 14? 15? or maybe 11? How do I know that?

I think that if understand this fundamental question, I could answer this question with ease.

When inserting an entry in the cache, an entire block of addresses is copied. In your case 2 words (8 bytes) are inserted.

So when address 12 is reached, the block of 8 bytes  having address 12 is inserted into cache.

Likewise in case of subsequent misses a maximum of 8 such "blocks" can be inserted into cache, after which eviction process shall start. Further sequence of cache hits/misses shall depend on the eviction policy.


What is the density of a regular language $L$ over an alphabet $\Sigma$ in $\Sigma^n$? In other words, what is the likelihood that a recognizer of a given regular language will accept a
random string of length $n$?

If there is only a single non-terminal $A$, then there are only two kinds of rules:

Intermediate rules of the form $ S \to \sigma S $.
Terminating rules of the form $ S \to \sigma $.

Such a grammar can then be rewritten in shorthand with exactly two rules, thusly:

$$\left\{\begin{align}
&S  \enspace \to \enspace \{\sigma, \tau, \dots\} S = ΤS\\
&S  \enspace \to \enspace \{\sigma, \tau, \dots\} = Τ'\\
\end{align}\right.\\ \space \\
(Τ, Τ' \subset \Sigma) $$

So, we simply choose one of the $Τ$ (this is Tau) symbols at every position, except for the last
one, which we choose from $Τ'$.

$$ d = \frac {\lvert Τ\rvert^{n - 1} \lvert Τ' \rvert} {\lvert\Sigma\rvert^n} $$

I will call an instance of such language $L_1$.

If there are two non-terminals, the palette widens:

Looping rules of the form $ S \to \sigma S $.
Alternating rules of the form $ S \to \sigma A $.
Terminating rules of the form $ S \to \sigma $.
Looping rules of the form $ A \to \sigma A $.
Alternating rules of the form $ A \to \sigma S $.
Terminating rules of the form $ A \to \sigma $.

In shorthand:
$$\left\{\begin{align}
&S  \enspace \to \enspace Τ_{SS} S \\
&S  \enspace \to \enspace Τ_{SA} A \\
&S  \enspace \to \enspace Τ_{S\epsilon} \\
&A  \enspace \to \enspace Τ_{AA} A \\
&A  \enspace \to \enspace Τ_{AS} S \\
&A  \enspace \to \enspace Τ_{S\epsilon} \\
\end{align}\right.\\ \space \\
(Τ_{SS}, Τ_{SA}, Τ_{S\epsilon}, Τ_{AA}, Τ_{AS}, Τ_{S\epsilon} \subset \Sigma) $$

Happily, we may deconstruct this complicated language into words of the simpler languages $L_1$ by
taking only a looping rule and either an alternating or a terminating shorthand rule. This gives us four
languages that I will intuitively denote $L_{1S}, L_{1S\epsilon}, L_{1A}, L_{1A\epsilon}$. I will
also say $L^n$ meaning all the sentences of $L$ that are $n$ symbols long.

So, the sentences of this present language (let us call it $L_2$) consist of $k$ alternating
words of $L_{1S}$ and $L_{1A}$ of lengths $m_1 \dots m_k, \sum_{i = 1 \dots k}m_i = n$, starting
with $L_{1S}^{m_1}$ and ending on either $L_{1S\epsilon}^{m_k}$ if $k$ is odd or otherwise on
$L_{1A\epsilon}^{m_k}$.

To compute the number of such sentences, we may start with the set $\{P\}$ of integer partitions
of $n$, then from each partition $P = \langle m_1\dots m_k \rangle$ compute the following numbers:

The number $p$ of distinct permutations $\left(^k_Q\right)$ of the constituent words, where $Q = \langle q_1\dots\ \rangle$ is the number of times each integer is seen in $P$. For instance, for $n = 5$ and $P = \langle 2, 2, 1 \rangle$, $Q = \langle 1, 2 \rangle$ and $p = \frac{3!}{2! \times 1!} = 3$
The product $r$ of the number of words of lengths $m_i \in P$, given that the first word comes
from $L_{1S}$, the second from $L_{1A}$, and so on (and accounting for the last word being of
a slightly different form):

$$ r = \prod_{i = 1, 3\dots k - 1}\lvert L_{1S}^{m_i} \rvert
   \times \prod_{i = 2, 4\dots k - 1}\lvert L_{1A}^{m_i} \rvert
   \times
        \begin{cases}
            & \lvert L_{1S\epsilon}^{m_k} \rvert &\text{if $m$ is odd}\\
            & \lvert L_{1A\epsilon}^{m_k} \rvert &\text{if $m$ is even}\\
        \end{cases}
   $$

If my thinking is right, the sum of $p \times r$ over the partitions of $n$ is the number of
sentences of $L_2$ of length $n$, but this is a bit difficult for me.

My questions:

Is this the right way of thinking?
Can it be carried onwards to regular grammars of any complexity?
Is there a simpler way?
Is there prior art on this topic?

If I understand the question, your problem is the following:

  Given a regular language $L$ over alphabet $\Sigma$ and a positive integer $n$, compute the probability that a word chosen uniformly at random from $\Sigma^n$ will be in $L$.

That's equivalent to computing $|L \cap \Sigma^n|$, i.e., the cardinality of the language $L \cap \Sigma^n$.  Note that $L \cap \Sigma^n$ is regular, so your problem is equivalent to the problem of counting the number of words in a finite regular language.  This is a standard problem that is well-studied; see https://cstheory.stackexchange.com/q/8200/5038, https://cstheory.stackexchange.com/q/32473/5038, Why isn't it simple to count the number of words in a regular language?, Counting the number of words accepted by an acyclic NFA.  Here are some results:

If the language $L$ is specified as a DFA or as an unambiguous regexp, then the problem can be solved in polynomial time.
If the language $L$ is specified as a NFA and $n$ is specified in unary, the problem is $\#P$-complete.  Thus, there is an exponential-time algorithm but you should not expect a polynomial-time algorithm.
If the language $L$ is specified as a NFA and $n$ is specified in binary, the problem is $PSPACE$-complete.  Thus, you should not expect a polynomial-time algorithm.

There are approximation algorithms that you might be able to use in practice to estimate the probability you're seeking (using a SAT solver as a subroutine).


Minimum steps to sort array Consider you have a permutation of $1$ to $n$ in an array $array$. Now select three distinct indices $i$,$j$,$k$, there is no need  to be sorted. Let $array_i$, $array_j$ and $array_k$ be the values at those indices and now you make a right shift to it, that is $new$ $array_i$= $old$ $array_j$ and
$new$ $array_j$= $ old$ $array_k$ and $new$ $array_k$=$old$ $array_i$. Find the minimum number of operations required to sort the array or if is impossible how to determine it.

Example :
Consider $array= [3,1,2]$; consider indices $(1,3,2)$ in the given order after applying one operation it is $s =[1,3,2]$.

Can anybody share your approach.

Your operations correspond to applying a 3-cycle on the input permutation. You can reach the identity by applying 3-cycles iff the input permutation is even. Given the cycle decomposition of the input permutation, it shouldn't be hard to answer your question (though the answer is not immediate).


What is the strongest weaker version of the halts() function? I was wondering about some questions related to the Halting problem. I might have not understood all the assumptions in it fully. Would you kindly help me, please?
I understand that the construction in the proof leads to a contradiction. My thoughts are:

If one runs these theoretical programs in the real world, I would expect that the output of halts(f()) will oscillate between true and false with a frequency dependent on the processing speed. This all happens because the execution of f() is made dependent on the output of halts(f()). Self-referenced.

Obviously there are programs which do not need to be run by a testing halts() function and they can be still decided if they halt or not. For example the following will obviously not halt and there are IDEs which already detect it:
while(true)
;

Based on the previous 2 thoughts, can we state that there can be such halts() program that tells us if a program halts or not and oscillates between the two values only if the input program code takes the output of a halts(f()) function as an input in the inside?

Such halts() is still useful. Even if it cannot tells us a certain answer for a constructed, self-referenced pathological case.
Basically I am trying to figure out what is the strongest weaker version of the halts() function. What can we expect from it?

The gist of the argument is that the assumption that a one can write a function halt(f) that always halts and always answers correctly if f halts leads to a contradiction (by way of self-reference, applying it to a variant of itself), thus such function can't be written.
Sure, you can write functions that answer "Yes", "No", or "Don't know" (or even never stop) always correctly. Say we consider C programs only, it is (more of less) easy to check they are just a main function that doesn't include any loops, and so answer "Yes" for them, and "Don't know" for anything else. You can certainly refine the above a lot, and each refinement can in itself be further refined (if a program could identify the cases where all have to answer "Don't know", it'd know that for them the answer is "No" --just running the program would tell eventually if the answer is "Yes"). The point is there can't be a way to answer all cases correctly.


Quickly locating nearest rectangle from a point The problem is as follows:

  There are several rectangles in the plane (they are not necessarily axis-aligned), how can we index them in such a way that given a point $p$ we can quickly locate the nearest rectangle from $p$? The distance from a point $p$ to a rectangle $R$ is defined as the Euclidean distance between $p$ and its nearest counterpart $q \in R$. If $p$ is inside the rectangle, then the distance is $0$.

Actually what I want is the distance between $p$ and its nearest rectangle, so if we can directly get this distance, it's even better.

The naive solution is to compute the distance between $p$ and each rectangle, however this is time consuming in my case, so I want to know if there exists such a data structure.

Edit:

These rectangles may intersect, and the total number is very likely less than 20 (typically around 5). It is trivial if we only want to know this minimal distance for a few points, linear scan will do the work. However when the number of such points becomes very large, the overall computation overhead cannot be ignored, that's why I want to quickly find the nearest rectangle.

I expect the best option is to use some kind of spatial index. Here's a first suggestion, but I'm sure there are better solutions.

Create a quad tree with a maximum bucket capacity of $m$.
For each new rectangle, traverse the tree, and store a pointer to the rectangle at each bucket that intersects the rectangle.

Now to find the nearest rectangle for a point $p$:

Find the bucket $B$ the point falls in.
Find the distance $d$ to the nearest rectangle $B$.
Check all surrounding buckets for rectangles that might be closer than $d$.

The last step might still be expensive if you're unlucky, but you can effectively eliminate all buckets that are itself further from $p$ than $d$.


EPI question on multiplying two integers The Elements of Programming Interviews book has a question on "computing x*y without arithmetical operators" (question 5.5). The solution is here: https://github.com/epibook/epibook.github.io/blob/master/solutions/cpp/MultiplyShiftAdd.cc

I am confused about the Add() function in the solution. For example, if I want to add a=1110 and b=1, the while loop will execute only once (because temp_b will decrease from 1 to 0). The iteration goes as follows:

ak = 1110 & 1 = 0, bk = 1 & 1 = 1,
carryout = (0 & 1) | 0 | 0 = 0,
sum = sum | (ak ^ bk ^ carryin) = 0 | 1 = 1,
carryin = carryout << 1 = 0,
k = 10,
temp_a = 111,
temp_b = 0

Then we return:

sum | carryin = 1

But the sum of 1110 and 1 should be 1111

EDIT: I realised that the while loop would not stop after the first iteration

Judging from your comment, it looks like you might see what the issue with your explanation was, but it might be fruitful for someone to see this example worked out, so I'll post this anyway.

We can see that this works by stepping through the execution of this function. Let's use your examples of values for a and b:

a = 0b1110;
b = 0b0001;

We can now step through the function. Here are the initial variable assignments:

sum     = 0;
carryin = 0;
k       = 1;
temp_a  = a; // = 0b1110
temp_b  = b; // = 0b0001

We can now look at the first while loop iteration:

// (temp_a || temp_b) == (0b1110 || 0b0001), so we loop
ak = a & k; // = (0b1110 & 0b0001) = 0
bk = b & k; // = (0b0001 & 0b0001) = 1
carryout =  (ak & bk);      // =      (0 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (1 & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (0 | (0 ^ 1 ^ 0)) = (0 | 1) = 1
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 1      << 1 = 0b10
temp_a >>= 1; // = 0b1110 >> 1 = 0b111
temp_b >>= 1; // = 0b0001 >> 1 = 0b000

Thus, after this loop, we have the following variable assignments:

sum     = 1;
carryin = 0;
k       = 0b10;
temp_a  = 0b111;
temp_b  = 0b000;

We then check the condition ((temp_a || temp_b) == (0b111 || 0b000)), and see that it is true, so we loop again:

ak = a & k; // = (0b1110 & 0b010) = 0b10
bk = b & k; // = (0b0001 & 0b010) = 0
carryout =  (ak & bk);      // =      (0b10 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0b10 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (0    & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (1 | (0b10 ^ 0 ^ 0)) = (1 | 0b10) = 0b11
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 0b10  << 1 = 0b100
temp_a >>= 1; // = 0b111 >> 1 = 0b11
temp_b >>= 1; // = 0b000 >> 1 = 0b00

Thus, after this loop, we have the following variable assignments:

sum     = 0b11;
carryin = 0;
k       = 0b100;
temp_a  = 0b11;
temp_b  = 0b00;

Checking our condition again, we loop again (there are two loops left, so I will just go ahead and put both of them):

ak = a & k; // = (0b1110 & 0b100) = 0b100
bk = b & k; // = (0b0001 & 0b100) = 0
carryout =  (ak & bk);      // =      (0b100 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0b100 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (0     & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (0b11 | (0b100 ^ 0 ^ 0))
                            //   = (0b11 | 0b100) = 0b111
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 0b100 << 1 = 0b1000
temp_a >>= 1; // = 0b11  >> 1 = 0b1
temp_b >>= 1; // = 0b00  >> 1 = 0b0
// Variable assignments:
/* sum     = 0b111;
   carryin = 0;
   k       = 0b1000;
   temp_a  = 0b1;
   temp_b  = 0b0; */
// Loop again ((1 || 0) is true)
ak = a & k; // = (0b1110 & 0b1000) = 0b1000
bk = b & k; // = (0b0001 & 0b1000) = 0
carryout =  (ak & bk);      // =      (0b1000 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0b1000 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (0      & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (0b111 | (0b1000 ^ 0 ^ 0))
                            //   = (0b111 | 0b1000) = 0b1111
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 0b1000 << 1 = 0b10000
temp_a >>= 1; // = 0b1    >> 1 = 0b0
temp_b >>= 1; // = 0b0    >> 1 = 0b0
// (temp_a || temp_b) == false, so we are done.
// Final variable assignments:
/* sum     = 0b1111;
   carryin = 0;
   k       = 0b10000;
   temp_a  = 0b0;
   temp_b  = 0b0;*/

Lastly, we calculate sum | carryin and return:

return sum | carryin; // = 0b1111 | 0 = 0b1111

This returns the result 0b1110 + 0b0001 = 0b1111, which we expect.


Find typing derivation of STLC term with reference types The problem is to find the typing derivation of a term of the call-by-value STLC extended with reference types. The evaluation and typing rules for this language is given in Types and Programming Languages by Pierce on page 166. The term is
$$
t = (\lambda a:\mathrm{Ref}\mathrm{Bool}. \mathrm{if}\, \mathrm{true}\,\mathrm{then}\, !l_1\, !a\, \mathrm{else}\,0)\,\mathrm{ref}\,\mathrm{true}
$$
where
$$
\mu(l_1)=\lambda x:\mathrm{Int}.x
$$
So I need to find $\Gamma, \Sigma,$ and $T$ so that
$$
\Gamma\,|\,\Sigma\vdash t:T
$$
I know you are supposed to show your work, but my problem is that $t$ doesn't seem well-typed... What am I missing?

The expression $t$ does not contain any free variables, so one can start typing it with an empty context: $\emptyset\,|\,\Sigma~\vdash~t : \mathrm{Int}$, and attempt to build the full derivation tree in a bottom-up way.

The tricky part of the typing derivation is where we try to type-check the subexpression $(!l_1\,!a)$. Because $(!l_1\,!a)$ lies in the body of a $\lambda$-expression which introduces the variable $a$ of type $\text{Ref Bool}$, at that point the context will be extended with an entry $(a : \mathrm{Ref~Bool})$, therefore $\Gamma=\emptyset,a : \mathrm{Ref~Bool}$.

$\dfrac{\dfrac{(a)}{\Gamma\,|\,\Sigma~\vdash~!l_1 : \mathrm{Bool \to Int}}{\text{T-Loc}}~~~~~~~~~~~~~\dfrac{\Gamma\,|\,\Sigma~\vdash~a : \mathrm{Ref~Bool}}{\Gamma\,|\,\Sigma~\vdash~!a : \mathrm{Bool}}{\text{T-Var}}}{\Gamma\,|\,\Sigma~\vdash~!l_1\,!a : \mathrm{Int}}{\text{T-App}}$

Completing the above sub-derivation by filling in the missing premise in $(a)$, shows what $\Sigma$ we must choose so that $t$ is typable. From the $\text{T-Loc}$ rule, clearly $\Sigma$ must contain the entry $(l_1:\mathrm{Bool \to Int})$.

This contradicts the expectation that $\Sigma(l_1) = \mathrm{Int \to Int}$. But this expectation is there only because we know that $\mu(l_1)$ is a term of type $\mathrm{Int \to Int}$. However, $\mu$ plays no role in the typing of an expression. It only plays a role in the evaluation process.

What is violated here is not the typing of $t$. Indeed, $t$ is straight-forwardly typable by following the typing rules and choosing appropriate $\Gamma$ and $\Sigma$. What is violated is the typing of $\mu$. Following the theory and notation of the book, the judgment $\Gamma\,|\,\Sigma\vdash\mu$ does not hold. Because of this, the preservation theorem does not apply and if you try to evaluate $t$, a run-time error will occur.


How do I find maximum and minimum number of times the search loop will execute when searching through an array of 1,048,576 integers I have tried to calculate the maximum number of times the loop will search through this large array, but I am not sure if I have that correct and I also need help with or pointers of how I can calculate the number of minimum times it will search through the array using both the binary search and sequential search. Here is what I have done so far.

Maximum Number of Times with Binary Search: Maximum: $\log_2(1,048,576)= 20$ times
Maximum Number of Times with Sequential Search: Maximum: $1,048,576 + 1 ÷ 2= 524,289$ times

But I am confused about how I can obtained a solution with Minimum number for each algorithm. Any suggestions?

I assume your input is random and your array of size $N$, $A[1..N]$.

In case of binary search if the number you are searching for is located at $(1+N)/2$, i.e. right in the middle of the input array then you will find it after the first if-statement.

Similarly in case of sequential search, if number your are searching for is the first element of the array then you stop after the first if-statement.

In both cases you do only one comparison.


Complexity of the Kitten Adoption problem This came up while I was trying to answer this question on  Wiring Length Minimization.  I was going to call this the "polygamous marriage" problem, but the internet, so kittens.  Yay!

Suppose we have $M$ kittens that need to be adopted by $N$ people, $M > N$.  For each kitten, $i$ and each person $j$ there is a cost $c_{ij}$.  We would like to minimize the total cost of getting all the kittens adopted.  There is also a set of constraints: each person $j$ is able to adopt no more than $u_j$ kittens.

Without the constraints the problem is easy; each kitten $i$ goes with the person $j$ for which $c_{ij}$ is minimal.  With the constraints is there an efficient algorithm for this problem or is it NP-hard?

This is the min-cost max-flow problem.

Consider a graph $G=(A\cup B\cup \{s,t\},E)$, where $A$ is the set of kittens, $B$ is the set of people.

Let $C:E\to \mathbb{R}^+$ be the capacity of the edges, and $c:E\to \mathbb{R^+}$ be the cost of an edge. We make sure that

There is an edge between $a_i,b_j$, where $a_i\in A$ and $b_j\in B$, and $C(a_i,b_j)=1$, $c(a_i,b_j)=c_{i,j}$.
There is an edge between $s$ and $a_i\in A$, and $C(s,a_i)=1$, $c(s,a_i)=0$.
There is an edge between $b_j\in B$ and $t$, and $C(b_j,t)=u_j$, $c(b_j,t)=0$.

If the max flow is $M$, then we know there exist a solution. You can construct a min-cost solution from the min-cost max-flow.


Can I notate time complexity depending on the result of an algorithm? I have a program that calculates the first year some two events happen on the same day. I have not calculated any upper limit for the year. The time complexity of the program would be equivalent to O(Years), where Years is the result of the algorithm.

Is such a notation possible?

If yes, can I call the algorithm "linear"?

If not, what would be the correct way of notating the complexity?

You can express algorithms costs in whichever parameters you desire, so long as you define them. The parameters don't even have to be known given the input; that gives your bound limited use, but well.

Warning: Landau bounds are asymptotic, that is they only hold meaning when you let the parameter(s) go towards infinity. That is you can not really use parameters that can not be arbitrarily large.

Warning: It's unlikely that your cost is independent of the input, which is what your bounds seems to suggest. You probably made a mistake.


Proof for variation of Prim's and Kruskal's to find maximum-weight acyclic subgraph I have been scratching my head to find good counter examples to the following problem:

  Suppose we are given a directed graph G=(V,E) in which every edge has
  a distinct positive edge weight. A directed graph is acyclic if it has
  no directed cycle. Suppose that we want to compute the maximum-weight
  acyclic subgraph of G (where the weight of a subgraph is the sum of
  its edges' weights). Assume that G is weakly connected, meaning that
  there is no cut with no edges crossing it in either direction.

  Here is an analog of Prim's algorithm for directed graphs:
  Start from
  an arbitrary vertex s, initialize S={s} and F=∅.
  While
  S≠V, find the maximum-weight edge (u,v) with one endpoint in S and one endpoint in V−S. Add this edge to F, and add the appropriate endpoint to S.

  Here is an analog of Kruskal's algorithm. Sort the edges from highest
  to lowest weight. Initialize F=∅. Scan through the edges; at each
  iteration, add the current edge i to F if and only if it does
  not create a directed cycle.

Both algorithm fail.
There should be a 4 vertices graph with 2 cycles that demonstrate this.

So far I played with different weights for this:

A<----B
^⟍    ^
|  ⟍  |
|    ➘|
C<--- D

However I am not yet able to prove that both algorithms fail.
I would love any suggestioin

This is a nice exercise.  You should probably do it yourself, to get the learning benefit.  I suggest that you enumerate all non-isomorphic graphs with 3 vertices or 4 vertices, and for each such graph, try playing with the weights to try to find a counter-example.  Basically, keep trying what you've been doing, but be more systematic and exhaustive about it.  You're on the right direction -- keep at it.


Searching related works for papers How do you search related works for your papers? To be concrete I have implemented few techniques of indirect call promotion for pure C and want to share my results. But at first I want to understand if there are some existing papers about it.

I searched with Google, Google shcolar, citeseerx, microsoft academic search, acm library and semanticscholar. I found only papers on C++ devirtualization but not for pure C. I searched the papers referenced to those what I found but I still did not found anything about pure C.

Can I think my research will be uniqe and interesting for scientific community or I just failed to find existing papers?

This site may also offer you a resource for locating content similar to your paper. Most academic institutions and public libraries have free access to these sorts of research tools to look for published work in selected areas of research. Good Luck.

Click Here


How to maximize $(h[j]-h[i])(j-i)$ in $O(n)$ I see many algorithmic problems that always reduce to something a long the lines of:

You have an integer array $h[1..n]\geq 0$, you need to find $i,j$ such that maximizes $(h[j]-h[i])(j-i)$ in $O(n)$ time.

Obviously the $O(n^2)$ time solution is to consider all pairs, however, is there any way we can maximize the expression in $O(n)$ without knowing something else about properties of $h$?

One idea I thought of is to fix $j$, then we need to find $i^*$ from $1$ to $j-1$ that is equal to $\text{argmax}_i\{(h[j]-h[i])(j-i)\}$ or $\text{argmax}_i\{h[j]j-h[j]i-h[i]j+h[i]i\}$ and since $j$ is fixed, then we need $\text{argmax}_i\{-h[j]i-jh[i]+ih[i]\}$.

However, I see no way of getting rid of the $j$ dependent terms inside. Any help?

This is an $O(n\log n)$ solution. An $O(n)$ solution pointed out by Willard Zhan is appended at the last of this answer.

$O(n\log n)$ solution

For convience, denote $f(i,j)=(h[j]-h[i])(j-i)$.

Define $l_1=1$, and $l_i$ be the smallest index such that $l_i>l_{i-1}$ and $h[l_i]<h[l_{i-1}]$. Similarly, define $r_1=n$, and $r_i$ be the largest index such that $r_i<r_{i-1}$ and $h[r_i]>h[r_{i-1}]$. The sequences $l_1,l_2,...$ and $r_1,r_2,\ldots$ are easy to compute in $O(n)$ time.

The case where there are no $i<j$ such that $h[i]< h[j]$ (i.e. $f(i,j)>0$) is trivial. We now focus on non-trivial cases. In such cases, to find the solution, we only need to consider such pairs.

For each $i<j$ such that $h[i]<h[j]$, let $u$ be the largest index such that $l_u\le i$, and $v$ be the smallest index such that $r_v\ge j$, then $h[l_u]\le h[i]$ (otherwise $l_{u+1}\le i$ by definition of $l_{u+1}$, thus contradicts to the definition of $u$), and similarly $h[r_v]\ge h[j]$. Hence
$$(h[r_v]-h[l_u])(r_v-l_u)\ge(h[j]-h[i])(r_v-l_u)\ge(h[j]-h[i])(j-i).$$
This means we only need to consider pairs $(l_u,r_v)$ where $l_u<r_v$.

Denote $v(u)=\arg\max_{v:\ l_u<r_v}f(l_u,r_v)$, we have the following lemma.

  A pair $(l_u,r_v)$ where $l_u<r_v$, and where there exists $u_0$ such that $u<u_0$ and $v<v(u_0)$ or such that $u>u_0$ and $v>v(u_0)$, cannot be a final optimum solution.

  Proof. According to the definition of $v(u_0)$, we have
  $$
(h[r_{v(u_0)}]-h[l_{u_0}])(r_{v(u_0)}-l_{u_0}) \ge (h[r_v]-h[l_{u_0}])(r_v-l_{u_0}),
$$
  or
  $$
(h[r_v]-h[r_{v(u_0)}])l_{u_0}+h[l_{u_0}](r_v-r_{v(u_0)})+h[r_{v(u_0)}]r_{v(u_0)}-h[r_v]r_{v(u_0)}
\ge 0.
$$

  In the case where $u<u_0$ and $v<v(u_0)$, note $h[r_v]-h[r_{v(u_0)}]<0$ and $r_v-r_{v(u_0)}>0$, and also $l_u<l_{u_0}$ and $h[l_u]>h[l_{u_0}]$, we have
  $$
\begin{align*}
&(h[r_v]-h[r_{v(u_0)}])l_u+h[l_u](r_v-r_{v(u_0)})\\
>\ &(h[r_v]-h[r_{v(u_0)}])l_{u_0}+h[l_{u_0}](r_v-r_{v(u_0)}).
\end{align*}
$$

  This means
  $$
(h[r_v]-h[r_{v(u_0)}])l_u+h[l_u](r_v-r_{v(u_0)})+h[r_{v(u_0)}]r_{v(u_0)}-h[r_v]r_{v(u_0)}
> 0,
$$
  or
  $$
(h[r_{v(u_0)}]-h[l_u])(r_{v(u_0)}-l_u) > (h[r_v]-h[l_u])(r_v-l_u).
$$

  So $(l_u,r_{v(u_0)})$ is a strictly better solution than $(l_u,r_v)$. Proof for the other case is similar. $\blacksquare$

We can compute $v(\ell/2)$ firstly where $\ell$ is the length of the sequence $l_1,l_2,\ldots$, then recursively compute the optimal solution $o_1$ among $(l_u,r_v)$'s for $u=1,\ldots,\ell/2-1$ and $v=v(\ell/2),v(\ell/2)+1,\ldots$, and the optimal solution $o_2$ among $(l_u,r_v)$'s for $u=\ell/2+1,\ell/2+2,\ldots$ and $v=1,\dots,v(\ell/2)$. Due to the lemma, the global optimum solution must come from $\{(l_{\ell/2},r_{v(\ell/2)}),o_1,o_2\}$.

$O(n)$ Solution

Let $f(l_u,r_v)=-\infty$ if $l_u\ge r_v$. The proof of the lemma also shows an important property: for $u>u_0$ and $v>v_0$, if $f(l_{u_0},r_{v_0})\ge f(l_{u_0},r_v)$, then $f(l_u,r_{v_0})>f(l_u,r_v)$. This means the matrix $M[x,y]:=-f(l_x,r_{c-y+1})$ is a totally monotone matrix where $c$ is the length of the sequence $r_1,r_2,\ldots$ (so $r_{c-y+1}$ means the $y$-th element from the end), then SMAWK algorithm can apply to find the minimum value of $M$, thus the maximum value of $f$.


Minimum number of bits to represent negative number Minimum number of bits required to represent $(+32)_{base10}$ and  $(-32)_{base10}$ in signed two's compliment form?

My attempt:
32 = 0100000 ( 1st zero - sign bit as positive)
So to represent +32 we need 7 bits
-32 = 1100000 (1st bit 1 - sign bit as negative)
So to represent -32 we need 7 bits

But answer is given as 6 bits to store -32 and 7 bits to store +32(positve case i understood, negative in my opinion it should be 7 bits). His reason - one 1 bit enough to represent negative number. I am confused. Please clarify here

Also i have following Questions:-

Can we say number of bits required to represent a negative number is strictly less than( or less than equal to) number of bits required to represent that corresponding positive number?
how can we generalise minimum number of bits required to represent a given positive and negative number say +N and -N in signed magnitude representation, signed 1's complement notation and signed two's compliment notation.

The representations of the numbers as 6-bit two's complement binaries are
\begin{align}
+32_{10} &= 10\,0000_2\\
-32_{10} &= \overline{10\,0000}_2 + 1_2\\
         &= 01\,1111_2 + 1_2\\
         &= 10\,0000_2
\end{align}
which would give the same representation for both numbers. That means you cannot use 6-bits numbers to represent both values using two's complement.

For 7-bit binaries it works, however:
\begin{align}
+32_{10} &= 010\,0000_2\\
-32_{10} &= \overline{010\,0000}_2 + 1_2\\
         &= 101\,1111_2 + 1_2\\
         &= 110\,0000_2
\end{align}
As you can see, the most significant bit represents the sign of the number.

Another perspective on your question: What is the biggest positive/smallest negative number you can store in an $n$-bit two's complement binary? Then the answer is $2^{(n-1)}-1$ for the biggest positive and $-2^{(n-1)}$ for the smallest negative number.

That means that a 6-bit binary can hold values $-32, \ldots, 31$ and a 7-bit binary values $-64, \ldots, 63$. The number $-32$ then fits into the range of 6-bit binaries, while $+32$ doesn't. You'd need one more bit for the latter.


Pumping lemma to show a language is not context free I have started pumping lemma for context-free grammar by reading Sipser's book and there are two questions right at the end end of the topic which I don't understand how to solve or where to start from?

I have to show that the following languages are not context-free

    L = { w | w = 0a  1 b   2 ab   where a, b are >= 1 }

and another question that goes like this:

    L = { w | w = x11x21...1xk where k >=0 and each xi is ∈ {0}*, and xi ≠ xj whenever i ≠ j

How would I tackle this problem? I understand pumping lemma in general but for these questions I can't seem to apply it.

First language: $0^{p}1^{p}2^{p^2}$ - If we make $0$ or $1$ longer, $2$ must get longer too to satisfy the condition of the language. Because of $|vwx|\le p$ $v$ cannot contain $0$ when $x$ contains $2$. Also if either $v$ or $x$ contained two different symbols, we know that it would break the language (there would be a sequence of e.g. $0^{i}1^{k}2^{l}1^{m}2^{n}$ with $l,m > 0$).
The last possibility is when $v$ is of form $1^k$ and $x$ of form $2^{l}$. We will prove by contradiction that this is impossible too. We would need such $k, l>0$ that the next equation holds for all $i \ge 0$
$$p(p+i\cdot k) = p^{2}\cdot i \cdot l \\
p^{2} + p\cdot i \cdot k = p^2 \cdot i \cdot l \\
l = \frac { p^2 + p \cdot i \cdot k }{p^2 \cdot i} \\
l = \frac {1}{i} + \frac {k}{p} $$
From $|vwx|\le p$ and $k,l>0$ we know that $k<p$. Similary $\frac{k}{p}<1$ and $\frac{1}{i} < 1$ for $i > 1$. From those and the fact that $l$ is natural number, the only possible value of $l$ is $1$. That would mean
$$p^{2} + p\cdot i \cdot k = p^2 \cdot i \\
k = \frac{p \cdot i - p}{i} \\
k = p - \frac{p}{i}$$

There are two problems with this: first it would hold only when $i$ divides $p$ and $k$ would be dependant on $i$ but has to be a constant. Thus we have proved this is impossible too and the lemma is complete.

For the second language, I believe it is pretty difficult example I and I would advise you to first try some easier languages, if you have just started using the lemma.

You can chose for any $p$ a string $0^{0}10^{1}10^{2}1...10^{p-1}10^{p}$ and then you have to enumerate all the possibilities and prove they don't hold for some $i$.

Either $x$ or $v$ contains two (or more) $1$'s - then it also contains $10^m1$ so with $i>1$ the pumped string will contain two $x_m$'s so it will not be from $L$.
Both $x$ and $v$ contain no $1$'s - with $i=0$ the substrings $x_m$ and $x_n$ containing $x$ and $v$ respectively will get shorter. Since the original string $s$ contained all shorter strings $x_k$ at least one of them will colide with some shorter string.
Either $x$ or $v$ contain only $1$. - If that substring is pumped, the new string will contain $...11... = ...1x_{0}1...$, but the original string started with $1... = x_{0}1...$, thus we have a collision.
Either $x$ or $v$ are of form $0^{n}10^{m}$ with either $n$ or $m$ greater than $0$. With $i=3$ we get $...0^{n}10^{n+m}10^{n+m}10^{m}...$ where we immediately see a collision.

I hope I did not forget some special case.


If a set S is infinite and recognizable, is there an infinite subset of S that is decidable? If a set S is infinite and recognizable, how can I prove that, if any, some subsets K is infinite and decidable? how about infinite and recognizable?

The second question is the easier one, we can just pick any string $\varsigma$ in the infinite Turing recognizable language $S$, and let $S' = S\setminus\{\varsigma\}$. Then you should be able to construct a TM that recognizes $S'$ from the recognizer $R$ for $S$.

The normal proof for the first question is trickier, relying on two facts:

Every Turing recognizable language has an enumerator (a TM that prints out the strings in the language one by one).
If a language has a lexicographic enumerator (a TM that enumerates the strings in the language in lexicographic order), then it is decidable.

So you start with $S$, which must have an enumerator $E$ that prints out, one by one, the strings in $S$ in some order, which may include repeats. What you have to do is construct a lexicographic enumerator using $E$ as a subroutine. It doesn't have to print out everything in $S$, just a subset of course, the trick is to ensure that the ones it prints are in lexicographic order. As noted Jeremy West in the comments, we must also ensure that the subset is infinite, this is easy enough, just not to be forgotten.


How do I follow the text of this Longest Common Sequence proof? I'm working through a proof that is a simplified version of David Maeirs LCS reduction from the VERTEX-COVER problem and I had a question about a specific set of instructions and how to execute them by hand.

Background Information
This works out to look like the below as a graph (please excuse the grid lines)

The part I don't understand of the proof

Now I think this would imply that I need to line up S0-S7 vertically and using that rule show I can find the LCS, which was shown in my proof to be

  $$00000001000000000000000000000100000000000000100000001$$
  $$0^710^{21}10^{14}10^71$$

I tried doing that but was unable after many attempts to show that I could in fact induce $Topt$ from the sequences below. Could someone explain where I'm going wrong here? Did I misinterpret the instructions?

  $S0 =00000001000000010000000100000001000000010000000100000001$

  $S1 =00000000000000100000000000000100000001000000010000000100000001$

  $S2 =00000001000000000000001000000000000001000000010000000100000001$

  $S3 =00000001000000000000001000000010000000000000010000000100000001$

  $S4 =00000001000000010000000000000010000000100000000000000100000001$

  $S5 =00000001000000010000000000000010000000100000001000000000000001$

  $S6 =00000001000000010000000100000000000000100000000000000100000001$

  $S7 =00000001000000010000000100000001000000000000001000000010000000$

EDIT: I tried everything I could think of to see if I could make any of them work but didn't think it was relevant enough to include, if you want to know what I did I can list them.

The two red-underlined parts of the proof is to standardize an LCS solution, that is called $T_{opt}$ therein.

The idea is to push all the $0$'s farthest possible to the right (without passing through its nearest $1$ to the right).

Consider the following two strings:

$s_1=0001000100010001$ (i.e. $n=4$ vertices)

$s_2=0001000\ 00010001000$ (where the space is for visualizing purpose only) (i.e. $u=2$, $v=4$)

A common subsequence (not necessarily longest) can be: $s=0001000 00010001$ (i.e. $u$ is omitted)

The standardization process in the proof is to actually align $s$ against $s_1$, $s_2$.

And, this MUST be standardized to be as follows:

s1= 0001 0001 0001 0001

s2= 0001 000  0001 0001000

s = 0001 000  0001 0001

Similarly, if we omit $v$, then $s=000100010001000$

And, this should be standardized as follows:

s1= 0001      0001 0001 0001

s2= 0001 000  0001 0001 000

s = 0001      0001 0001 000

Finally, we will be able to construct an $n^2+k$-long common subsequence if there exists an independent set of size $n-k$, where for each edge $\{u,v\}$, we omit at least one of them (the ones that are in the independent set) so that it is possible to align like we do above (note that each edge-string $e_j$ contains only $n-1$ symbol $1$'s). And lastly, by complementing a $k$-VC, we have an $(n-k)$-IS.