Can the same node appear twice in a tree? Can the same node appear twice in a tree?

I'm asking about the node object itself, not the node's value. For example, in the following code, a's left and right are the same node, b.

a = new TreeNode(1);
b = new TreeNode(2);
a.left = b;
a.right = b;

Is this valid? Why or why not?

A tree is defined to be a set of nodes, with a parent-child relationship that satisfies certain properties.  Thus, it doesn't make sense to ask whether a node can "appear" twice.

In your code snippet, you have constructed a DAG, not a tree.


A robot arm consisting of a sequence of rigid line segments L1, L2, . . . , Ln hinged together consecutively Hi I am a Computer Science student attempting to solve this problem for extra credit. Problem is I am unsure what this algorithm is asking for as the language is a bit hard for me to follow:

  Imagine that you have a robot arm consisting of a sequence of rigid
  line segments $L_{1}, L_{2}, \dots , L_{n}$ hinged together
  consecutively. The lengths of the line segments $l_{1}, l_{2}, \dots ,
> l_{n}$ are positive integers. You may rotate freely around the hinges
  and the line segments are allowed to cross over. Our goal is to pack
  in the line segments into one line segment as compactly as possible.
  More precisely, given positive integers $l_{1}, l_{2}, \dots , l_{n}$
  (and $l_{0} = 0)$ and a sequence of
  $\pm1$’s, $s_{0}, s_{1}, \dots , s_{n}$, where $s_{i} = 1$ or $s_{i} = −1$, $0 ≤ i ≤ n$, define

  $$m_1 = \min_j\left(\sum_{i=0}^j s_il_i\right) $$
  $$m_2 = \max_j\left(\sum_{i=0}^j
s_il_i\right) $$
  where ($0 ≤  j ≤ n$).
  Find $\min_s (m_{2} − m_{1})$, where the minimum is taken over all sequences
  $s = (s_0, s_2, \dots , s_n)$.

The goal is for me to write an algorithm that solves this problem. But I am not entirely sure what the question is asking. My understanding is drawn below:

The arms shall be compacted as much as they can be such the vertical height of the extended arm is minimized. But I don't understand what the $s_0, s_1,\dots, s_n$ sequence is for? And if someone could describe in layman's terms what the sequences $m_1$ and $m_2$ are asking for that would be great.

The $s$'s tell you which way each segment of the arm is pointing: $s_i=+1$ if the $i$th segment points up and $s_i=-1$ if the $i$th segment points down.

This means that $S_j := \sum_{i=0}^j s_i\ell_i$ is the distance of the end of the $i$th segment from the pivot. So $\min_j S_j$ and $\max_j S_j$ are the height of the lowest and highest points of the arm when it's folded in the way that $s_0, \dots, s_n$ describe.


Asymptotic growth of $\log(n^n + n)$ I would like to know if my understanding of this is correct:

The question asks to show that the Big-Oh of the following function is $O(n\log(n))$

$$
\log(n^n + n)
$$

I think the first step is to play with the expression so:

$$
\log(n^n + n) = \log(n(n^{n-1}+1)) = \log(n) + \log(n^{n-1}+1)
$$
However, I don't know what to do next.
Please help me move forward.
Thanks.

You could continue with
\begin{align*}
    \log n + \log (n^{n-1}+1)
        &\leq \log n + \log(2n^{n-1})\\
        &= \log n + (n-1)\log 2n\\
        &= \log n + (n-1)\log 2 + (n-1)\log n\\
        &= O(n\log n)\,.
\end{align*}
(Leaving out whatever steps you feel are obvious.)


Determining which states in a transition system satisfy a specific CTL formula Trying to answer the following question:

However, my answer is that only one of these states satisfy the TS (which is for sure wrong since the next part of this question asks to remove states that don't satisfy the formula and compute the new TS).

Reasoning follows:

1 - does not satisfy the formula since if you go to 4, EXISTS NEXT c is violated

2 - does not satisfy the formula since if you go to 4, EXISTS NEXT c is violated

3 - does not satisfy the formula since if you go to 1, EXISTS NEXT c is violated

4 - satisfies the formula since all paths satisfy EXISTS NEXT c

5 - does not satisfy the formula since if you go to 6, EXISTS NEXT c is violated

6 - does not satisfy the formula since if you go to 4, EXISTS NEXT c is violated

Can anyone see where I have gone wrong with my reasoning?

Something else I'm not sure about is for example if we take 4, it is satisfied since all paths lead to other states that (together) satisfy the equation. Do we need to include these 'other states' in the satisfaction set?

Really grateful for any help.

A hint that might put you in the right direction:
Note that $\exists Xc$ (where $X$ is the "next" operator) holds in every state from which there exists a neighbor with $c$. Thus, for example, $1\models \exists Xc$.

Now, $\forall (\phi U \psi)$ holds if in all computations $\phi$ holds until $\psi$ holds. In particular, every state that satisfies $\psi$ also satisfies $\forall (\phi U \psi)$, since the eventuality holds immediately.

Thus, $1$ satisfies the formula. See if you can complete the rest of them now.


Can the complement of a context-free language be regular? I know that the context-free language is not closed under the complement ,
and the result could be context-free language or non-context free language
but my question is :

is it possible of the complement of context-free language = regular language ?

Since regular languages are all context-free and REG is closed against complement, every regular language is such an example.

As for non-regular context-free languages, the same closure property with a sprinkle of proof by contradiction easily shows that none of them can have a regular complement.


Can a perceptron forget? I would like to build an online web-based machine learning system, where users can continuously add classified samples, and have the model updated online. I would like to use a perceptron or a similar online-learning algorithm.

But, users may make mistakes and insert irrelevant examples. In that case, I would like to have the option to delete a specific example, without re-training the perceptron on the entire set of examples (which may be very large).

Is this possible?

As I understand the process, altering a perceptron without retraining is impossible. The weight adjustments are not only relative to that specific example but also relative to the other training examples that have gone before.  Identifying the incorrectly classified instance and removing it from the test set before retraining the model would seem to be the most effective way of correcting the weights.

I think it's worth pointing out that in comparison to other machine learning algorithms, perceptrons are relatively resistent to noise and incorrectly classified instances in the training set.  If you're encountering a large number of misclassified instances, it would seem more prudent to have better validation at the point you ingest the data prior to training than to come up with some way to correct for misclassified instances after the perceptron has been trained.  If that's not possible and you're able to identify the incorrectly classified instances as such, then removing them and retraining would seem the only way to effectively remove the impact of the misclassified instances.


RICE theorem applications I am having some confusion in understanding RICE's theorem.

It says every non trivial property of RE in undecidable.

I need to understand when to apply RICE's theorem and when to not.

Questions like:- Turing machine makes at least five moves,It  accepts a string input of length atleast five ,TM halts for every input on length <50 are all decidable.

But  these  are  NON TRIVIAL properties?Some TM will make 5 moves and some will not,Some will halt on every input <50 and some will not?So if this is Non trivial property then why cant we apply RICE's theorem?

On other side questions like:- TM accepts at least 10 strings is undecidable because some TM will say yes and some will say NO.Then why can't we use same concept on above mentioned questions?

Please help me in understanding how to identify whether question is based on Rice's theorem or not?

The major hypothesis of Rice theorem is that you are dealing with a set which is "extensional", or "semantically closed". Formally this requires that when the encoding of a TM $M$ belongs to the set, and $N$ is a TM equivalent to $M$, then the encoding of $N$ must also belong to the set.

Equivalence here means that the TMs $M,N$ terminate on the same inputs, with the same output (including acceptance).

Conditions like "halts in 50 steps" break equivalence, in general. I.e. it is possible that $M$ halts in 10 steps with output zero on every input, yet $N$ does the same after "wasting" 100 steps. So, Rice can not be applied to these.

  Questions like:- Turing machine makes at least five moves,It accepts a string input of length at least five ,TM halts for every input on length <50 are all decidable.

No. The property "at least five moves" is decidable. The properties "accepts a string of at least five" and "halts for every input of length <50" are NOT decidable. Indeed, these properties only care about the input/output behavior of the TM, hence if $M$ satisfies one of those, and $N$ is equivalent, then $N$ also satisfies the same property. So, Rice applies to those.


Upper bound on the number of edges relative to the height of a DFS tree Let $T$ be a depth-first search tree of a connected undirected graph $G$ and $h$ be the height of $T$. How do you show that $G$ has no more than $h \times |V|$ edges where $|V|$ is the number of vertices in $G$?

After running a DFS, all the edges in $G$ can be classified as tree edges or back edges. Each back edge connects a vertex on the tree to one of it's ancestors. For each vertex it can point to at most $h-1$ ancestors, thus you can have at most $(h-1)|V|$ back edges. There are $|V|-1$ tree edges. You can have at most $h|V|-1$ edges.


Choose minimum subset of edges in tree that connects all important nodes Let's say we have given weighted tree of size $n$ and list of important nodes in the tree $k$.

We want to choose subset of edges of the tree such that:

For each two important nodes at least one edge of the path between them will be choosen
The sum of the subset of edges will be minimized

Note that we only need to find the sum of the edges in the subset, not the edges in the subset.

For example if we have the tree with the edges $(1, 2) \text{ weight = 3}, (1,3) \text{ weight = 10}$ And our important nodes are: $2, 3$. We should chose only the edge $(1,2)$

Note this is equivalently finding edges with minimum sum of weights such that their removal leaves each important node in a separate component, which is called minimum multiway cut problem.

This problem is NP-hard in general graph, while Chopra, Sunil, and Mendu R. Rao developed a polynomial time algorithm for tree in 1991 [1].

[1] Chopra, Sunil, and Mendu R. Rao. "On the multiway cut polyhedron." Networks 21.1 (1991): 51-89.


Objective function and constraint satisfaction over a set of multi-attributes elements I'm looking for an approach to solve a problem consisting of maximizing an objective function over a set of discrete elements, while respecting a set of constraints.

To illustrate my point, I'll try to come up with an example.

A bag contains several items with the following attributes:

Value (Int)
Size (Int)
Material (Enum)
Origin (Enum)

As an example, we can imagine a bag consisting of the following items:

value     size     material    origin
    4        1         wood        FR
    4        2        stone        US
    3        3         gold        JP
    2        2         wood        FR
  ...      ...          ...       ...

The goal is to maximize the total Value, while at the same time respecting a set of constraints. An example set of constraints would be:

total size < 80
between 20 and 35 items in total
at least five elements with origin FR
at least two elements with material wood OR at least two elements with material stone
strictly less elements with material gold than elements of material stone
no more than 5 elements with size > 10

Below are some approaches I've thought about, and the reason why I can't use them directly:

(Integer) Linear Programming: here we're not dealing with the full space of Integers, but instead only with the values found in the bag (and tied to the other properties for each item)
Stochastic Constraint Satisfaction: it would be easy to stochastically come up with a selection of Items which respects the constraints, but here we're not looking for any solution, instead we're looking for the solution which yields the highest total Value, which would need us to exhaustively list all possible satisfying solutions before picking the one with highest value (which may be a very inefficient approach)
SMT solver: I think it could be the way to go, but so far I can't see how to model the link between the constraints, the objective function and the bag of elements

Can you think of an approach to solve this kind of problems?

I don't see any problem with modeling this as an integer linear program, for example:

maximize V.x
st:
1) s.x < 80
2) 20 <= e.x <= 35
3) FR.x >= 5
4a) Wood.x + 2 - 2W >= 2
4b) Stone.x + 2W >= 2
5) Gold.x - Stone.x < 0
6) Size10p.x <= 5
x[i] ∈ {0, 1}
W ∈ {0, 1}

Where . is the dot product, x is a binary vector indicating which items to take, e is the vector of all-ones, FR is a boolean vector where an element is 1 iff the corresponding item is from France, Wood is a boolean vector that indicates that the material wood, etc. Size10p indicates that the item has a size higher than 10.

I've made all the left-hand sides of dot products the constant vector, so you can easily see that there are no sneaky quadratic constraints.

Most of the constraints are obvious, but constraint 4 is a bit trickier. It involves a disjunction, and uses an extra binary variable to choose which "side" of the disjunction to take. The other half is then trivially satisfied, by either adding 2 and not also subtracting 2 (W = 0, not taking the wood-side of the disjunction) or by just adding 2 (W = 1, taking the wood-side).

  here we're not dealing with the full space of Integers, but instead only with the values found in the bag

This is usually not a problem, since you can binarize constraints of the form v ∈ some enum to v1 = [v == item1], v2 = [v == item2] etc combined with v1 + v2 + ... = 1. But I did not even need that here, the decision is just "do I take this item or not", and things such as "item has property 'Gold'" are just constant booleans.

More tricks are available in other answers, for example Express boolean logic operations in zero-one integer linear programming (ILP).


Practical Page-Replacement Algorithms Could anyone suggest other page replacement algorithms that are applicable to the real world aside from

FIFO,
Second Chance (Clock),
Enhanced Second Chance and
Random?

The Least-Recently Used (LRU) is a very common algorithm for page replacement, especially in system softwares that are exposed to data access of temporal locality.


Memory addressing rapidity I've got a few questions related to the different types of memory that we can find:
To my understanding, since there are registers that are close physically to the CPU, these are much faster to access, same goes for the cache that is further to the CPU but still relatively closed, and the RAM which is further than everyone else and which is the slowest to gain access too. My question is: Why can't we simply put all of the RAM memory close physically to the CPU since apparently this is what is required in order to be fast. Is there another criteria to being fast apart from being close ? As I've seen, apparently since the RAM has a bigger memory size, the address in bits to access a register is longest and therefore require more time to gain access to the latter register. What if we had let's say 1000 units of cache memory each one size 8mb, in order to have a fast access to each one of them and still store 8GB of memory ? I think this would fail because since we have 1000 cache units, we'd still have to precise which one of the units we would want to have access to and therefore we'd still have the problem of having more bits in the address (at least I think so), if not, why would this logic fail ? Thank you for your help

Why can't we simply put all of the RAM memory close physically to the CPU

Because that is not how geometry works. You cannot have everything close to the CPU, because the stuff that is close to the CPU is blocking the space close to the CPU, and thus other stuff has to be farther away.
Geometry works the same on the CPU as it does everywhere else: why don't all your neighbors live directly next door to you? Well, because your neighbors are taking up that space, so you simply can only have two direct neighbors. Everybody else has to live further away.
There are actually already 3-dimensional designs where the memory is stacked on top of the CPU, in order to be able to bring more memory closer to the CPU. But that only pushed the problem out, it does not solve it.
There is, however, a whole slew of other reasons, not just geometrical ones, why we have a memory hierarchy and not just a single flat memory. The main problems are that, in general, faster memory is also

more expensive,
more power hungry,
more complex, and
physically bigger (less dense).

That latter problem actually leads to an interesting optimization problem: as we said above, we can't have all the fast memory close to the CPU, because the space close to the CPU is limited. However, since slower memory is more dense, and thus takes up less physical space for the same memory capacity, you can actually put more slower memory close to the CPU than you can faster memory!
And even if you were to use only the fastest memory technology for all your memory, you quickly run into problems with the fundamental speed limit of the universe: the speed of light. As a general rule, our systems are designed in such a way that a single clock pulse must be able to propagate through the entire clock domain within a single clock cycle.
This means that no matter how close and how dense we pack our memory to the CPU, there comes a point where we cannot clock the memory with a high clock rate anymore. The further away we get, the lower the clock rate. But then it doesn't make sense to use the super-expensive, super-fast memory anymore, if we have to make it slower anyway. It makes more sense to use the cheaper, more dense, more energy-efficient memory.
And that is why the memory hierarchy exists: because the difference is not just speed, it is also cost, space, and energy. Here is an example of one possible memory hierarchy:

Registers (discrete flip-flops)
Level 0 Cache / µOP Cache (typically SRAM; per thread)
Level 1 Cache (typically SRAM; per core)
Level 2 Cache (typically SRAM; per core)
Level 3 Cache (typically SRAM; per die)
Level 4 Cache (typically SRAM; per module)
Local Main Memory (typically DRAM; per module)
Remote Main Memory (typically DRAM; "not this module")
SSDs (Flash; per node)
HDDs (magnetic; per node)
SAN (mix of SSDs and HDDs; per system)
Tape Library (per system)
Offsite Cloud Storage

Obviously, not all of these levels exist in all systems. This is an extreme example of a multi-core, multi-CPU, multi-node NUMA cluster with a separate storage network – my laptop doesn't have #6, #8, #10, #11, and #12, for example.
#8 only exists in so-called "NUMA" systems (Non-Uniform Memory Architecture), i.e. systems where not all RAM is "created equal". Typically, these are systems with a large number of CPUs, where it is not feasible to give all CPUs the same access to all of the RAM. Instead, the RAM is split into parts and typically one block of CPUs has direct access to one block of memory, and if it wants to access the rest of the memory, it typically has to talk to the CPU(s) that "own(s)" that block.
As a closing remark, I want to say that while the answers here have shown why your idea doesn't work, that does not mean that your idea is stupid! In fact, your idea is pretty much the Holy Grail of storage technology, and every couple of decades, a new technology comes along that tries to be fast, cheap, dense, energy-efficient, and ideally even non-volatile, at the same time, so that it can replace a large portion of that memory hierarchy.
However, as of today, none of those technologies have been able to live up to the hype, so to say: MRAM, FeRAM, T-RAM, Z-RAM, and many others. The latest entry being Intel's / Micron's 3D XPoint (better known under Intel's marketing brand Optane).


Completing tasks on a graph Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. The graph $G$ is complete, which means we can traverse $(i, j)$ for all $i, j \in V$. At each vertex $v \in V$, there is a task that we must complete. The task at vertex $v$ takes $q_v > 0$ minutes for $v \neq 0$, and we must complete all tasks. We start at Vertex $0$, and we have $q_0 = 0$.
It will obviously take us exactly $\sum_{i = 1}^{n} q_i$ total time for us to complete all of the tasks on our own  (it doesn't take any time to traverse the edges). However, suppose we have a single helper. We are allowed to dispatch the helper at any node (say $v$), and we can leave the node, go work on other tasks, and pick up the helper after $q_v$ minutes to drop it off at another node. A caveat is that the helper cannot move on its own; it must be picked up and dropped off.
Is there some sort of algorithm that allows one to find the best strategy (i.e., one that minimizes the total time) when we are allowed one helper?
A naive strategy would be a greedy strategy that always drops off the helper at the vertex with the largest $q_i$. It seems like this would minimize the time that the helper is idle; however, I have no reason to believe that this is optimal.
Does anyone have any suggestions or heuristics for an approximate solution?

Hardness
The problem is strongly $NP$-hard so there likely is no fast algorithm solving it.
Consider the 3-Partition problem wherein we are given $3n$ distinct integers $x_1,\ldots, x_{3n}$ and an integer $T$ such that $T/4< x_i< T/2$ and asked to decide whether we can group the $3n$ integers into $n$ groups of $3$ integers with sum equal to $T$ for each triple.
We create an instance of the problem with $4n$ tasks, $3n$ of those tasks having length $x_i$ (one for each $1\leq i\leq 3n$) and $n$ tasks having length $T$.
There exists a solution with no idle time if and only if the 3-Partition instance is solvable. Clearly, if there is a solution to the 3-Partition instance there is a solution to the task planning instance: just have the helper do the length $T$ tasks and have us handle the other tasks in groups of 3 (each with length exactly equal to $T$).
Conversely, in any solution with no idle time, the helper cannot do any task of length less than $T$. If we start the helper on some task with length less than $T$ (i.e., some length $T/4< x_i< T/2$), we must find tasks to do ourselves with length exactly equal to $x_i$. However, no task other than $i$ itself has length $x_i$ (since all the integers $x_i$ are distinct) and for any two integers $x_j,x_k$, $x_j+x_k > T/2 > x_i$.
Thus, in any solution with no idle time, all the tasks done by the helper are of length $T$. The tasks we do ourselves during each task done by the helper must then form a solution to the 3-Partition instance.
Heuristic/approximation
Clearly the idle time cannot be approximated (since it is already hard to decide whether it is non-zero). There is however an EPTAS for the makespan.
Consider the algorithm that always assigns the longest job to the helper, and then fills out the schedule of the master by considering jobs in order of decreasing length and assigning each job that still fits (so that the length of master's schedule does not exceed that of the helper). Repeat this process with the remaining jobs untill all are scheduled. We call a single job done by the helper together with a set of jobs done by the master a "round".
This yields a solution with idle time of at most $L_\textrm{max}$ where $L_\textrm{max}$ denotes the length of the longest job. To see this, note that if during a round the master is idle for $\epsilon$ units of time, $L_\textrm{max}$ decreases (in the set of remaining jobs) by at least $\epsilon$: if there was a job longer than $L_\textrm{max}-\epsilon$ the master would have done that job and obtained a shorter idle time.
Suppose that the sum of all job lengths is $1$ and let $\epsilon < 1$. If $L_\textrm{max}\leq \epsilon$, the above procedure returns a $1+2\epsilon$-approximation (since the optimal solution has makespan $\geq 1/2$). Otherwise, consider the jobs with length $\geq \epsilon$ of which there are at most $1/{\epsilon}$ (long jobs). Consider also the jobs with $\epsilon <$ length $\geq \epsilon^2$ of which there are at most $1/{\epsilon^2}$ (medium jobs). The remaining jobs (with length $<\epsilon^2$) are called short.
We now, by brute force, enumerate all schedules with the following properties: all long jobs are scheduled, and possibly some medium jobs are scheduled and every round contains at least one long job. For each such schedule, we greedily fill any idle time the master may have with short jobs (so that the master does not work longer than the helper in any round). This is the first phase schdule. We then schedule the remaining short/medium jobs according to the previous greedy algorithm. This is the second phase schedule.
The idle time in the second phase is at most $\epsilon$ (since $L_\textrm{max}< \epsilon$). We now need to bound the additional idle time (over that in an optimal solution) in the first phase.
Take an optimal schedule. If the helper does a short job while the master does a long one, swap the jobs done by the helper and the master -- this does not change the makespan. Delete all short jobs from the schedule and all rounds containing only short/medium jobs. Assume the solution obtained by our approximation algorithm is based on this (modified) schedule, which will be part of the brute force enumeration (so our approximate solution will be at least as good as one obtained from this schedule).
If there are no short jobs in the second phase, then it is easy: We know that the medium jobs scheduled in the second phase do not need to be scheduled together with any long job in an optimal solution. In an optimal case they would be scheduled with at most zero idle time, and the greedy algorithm adds at most $2\epsilon$ extra idle time. We also have not increased the makespan of the brute-force schedule, so it must be optimal.
If there are any short jobs in the second phase, the first phase has at most $1/\epsilon$ rounds (because every round contains a long job) and no phase has more than $\epsilon^2$ idle time for the master (since otherwise we could have scheduled some of the remaining short jobs). Thus the total idle time for the master is at most $\epsilon$. In rounds were the helper has idle time, note that this round is unmodified from the original optimal schedule (since the master would not start a new job if the helper was idle). Thus, the additional idle time, over that of an optimal schedule, is at most $\epsilon$ (from rounds in which the master is idle; the rounds in which the helper is idle do not contribute any additional time).
An interesting question is what happens if the master is impatient and always starts a new job instead of having the option to wait for the helper to finish.


What is the loop invariant of the following function? x = n; y = 0

while x >= b:

   x = x DIV b

   y = y + 1

return y

This function takes in $n,b\in\mathbb{N}, n > 0, b > 1$, and returns $k\in\mathbb{N}$ such that $b^k\leq n \lt b^{k+1}$

So far I think it is:

$b^y \leq n$

$x \leq n$

but now I'm stuck

Try finding a loop invariant of the following form:
$$
f(x,y) \leq n < g(x,y).
$$

For example, when $y=0$ you could choose $f(x,y) = x$ and $g(x,y) = x+1$, and in the end you want this invariant to imply $b^y \leq n < b^{y+1}$.

To get some intuition, note that if $n = b^k z + w$, where $0 \leq w < b^k$, then after $k$ iterations, we have $x = z$. This can help you formulate the loop invariant.


Undecidability of telling if a program returns true or false Consider the problem of taking an input Turing machine and determining if the final cell is a $0$ or $1$ after computation halts. On cases where it writes something else or does not halt, you are allowed to give any answer (but you have to halt and give some answer on all inputs).

Is this problem undecidable? My gut says that it should be, but I can't find a reduction to the halting problem. Given a Turing machine that may or may not halt, we can set up the machine to finish with a $0$ in the case that it halts, but can't finish with anything in the non-halting case, so the oracle could just say $0$ in this case without having to figure out whether in fact the machine halts.

Note that a reduction in the other direction is simple; if you can solve the halting problem, then given a TM that either finishes with $0$ or $1$, we replace the $1$-writing step with an infinite loop to create a new TM. If the new TM halts, we say "it writes a $0$" and if it does not halt we say "it writes a $1$". This answer is guaranteed to be correct as long as the TM in fact halts with a $0$ or $1$, so we can solve the original problem.

Assume you have a function like the one you described:

def haltify(f):
    # Never fails to halt.
    # If 'f' halts, returns f().
    # If 'f' doesn't halt, anything could be returned.
    ... magic ...

But then someone comes along and does this:

def evil():
    return not haltify(evil)

See the problem?

If haltify(f) is guaranteed to halt for all f, then evil is also guaranteed to halt because it just calls haltify on a specific f and inverts the output.
Since evil halts, haltify(evil) must evaluate to the same thing as evil().
So not haltify(evil) simplifies to not evil() and that's what evil() returns.
That's a problem, because there's no x satisfying x == not x. Evil's result is contradictory.
Therefore one of the assumptions we used is wrong: either haltify isn't guaranteed to halt, or it isn't guaranteed to return f() when passed a halting f.

Bonus exercise: why doesn't the function def good(): return haltify(good) cause problems for haltify, despite apparently simplifying to the infinite loop def good(): return good()?


Proving correctness of an exponentiation routine I have the following exponentiation routine, which takes $O(\log n)$ steps

function power(a:real, n:positive integer)
begin
  x:=1;
  i:=n;
  while i > 0 do
  begin
    if(i % 2 == 1) then   //i odd
      x:=x*a
    i:=floor(i/2)
    if(i > 0) then
      a:=a*a
  end;
  power:=x
end

I'm trying to prove that it always gives $a^n$.  I think it might be provable via induction on $n$.  in the examples i went through i found that it always ends with $i=1$ before the final division down to $0$.

A standard approach to proving correctness of a program involving a loop is to use a loop invariant. Loop invariant $P(j)$ is a statement indexed by the iteration number $j$ (or a parameter related to the iteration number) that asserts a certain mathematical relationship between some variables appearing in your code. Proving $P(j)$ is true for all $j$ is typically done by induction. You show that $P(0)$ is true, i.e., the loop invariant is true prior to the beginning of the loop. You show that $P(i)$ is true implies $P(i+1)$ is true. Then you can conclude that the statement $P(n)$ (or $P(n+1)$) must be true, which asserts the relationship between the variables of interest that is directly relevant to the correctness of the algorithm. Note that if $j$ is some parameter related to the iteration number (e.g., $j$ could be $n$ minus the iteration number), the starting point and the direction of the induction might be different. Finding the right loop invariant is usually the hardest part.

Let's find a loop invariant for your code. Note that you overwrite the variable $a$ inside the loop. This means that I cannot use $a$ in the loop invariant to refer to the original input, but I'd like to. Therefore I introduce a new letter $\alpha$ to refer to the value of $a$ that is passed to the function, i.e., the first input. The rest of the variables are exactly as in your code. Our loop invariant $P(i)$ will be indexed by the variable $i$, which is related to the iteration number, but starts with $n$ and decreases to $0$ similar to what I wrote about above. Define the following loop invariant:
$$P(i) \text{ is true if and only if } x*a^i == \alpha^n$$
Clearly, at the beginning you have $x=1$,  $a=\alpha$, and $i = n$, so $P(n)$ is true. I leave proving the inductive step to you (note you will be proving $P(n)$ is true implies $P(\lfloor n/2 \rfloor)$ is true, so this induction skips over lots of values, but it's okay - why?). When the algorithm terminates you have $P(0)$, which asserts $x*a^0 = \alpha^n$, i.e., $x = \alpha^n$, which is what you needed to prove.


Calculating all products of $n-1$ factors when given $n$ factors Let's assume we have an operator
$$ \times: E^2\to E$$
of which we merely know that it is associative. Let's say a multiplication $e\times f$ always takes up a time of $M$ for all $e, f\in E$.

We're now given $n$ elements $e_1,...,e_n\in E$, and are tasked to calculate all $n$ products
$$\def\bigtimes{\mathop{\vcenter{\huge\times}}} p_j :=\bigtimes_{i=1\\i\neq j}^n e_i$$

Naively multiplying out all $n$ products takes $O(n^2M)$.

A more sophisticated approach that runs in $O(n^{3/2}M)$ splits $\bigtimes_{i=1}^n e_i$ at arbitrary positions into $\sqrt n$ factors.
For each of the $n$ products, we now only have to recalculate one factor, and multiply the resulting factor, and the other $k-1$ factors together.

What is the fastest algorithm for this problem, and how does it look like?

Here is the fastest algorithm. I bet. The idea of the algorithm can be seen from the one-line explanation between step 4 and step 5 below.

Input: $e_1,\cdots,e_n\in E$, where $n\ge 3$.
Output: $p_1, \cdots, p_n$, where $p_j=e_1\cdots e_{j-1}e_{j+1}\cdots e_n$, the product of all input elements except $e_j$.
Procedure:

Allocate array $p_1, p_2,\cdots, p_n$ of $n$ element in $E$.
Let $s=e_1$, $p_1=1$
For $i$ from 2 to $n-1$ inclusive, let $p_i = s$ and $s= se_i$.
Let $p_n=s.$

Now
$$
\begin{pmatrix}
p_1\\p_2\\ p_3\\p_4\\\cdots\\ p_{n-1}\\ p_n
\end{pmatrix}
\text{is}
\begin{pmatrix}
 1\\e_1\\e_1e_2\\ e_1e_2e_3\\\cdots\\ e_1e_2\cdots e_{n-2}\\e_1e_2\cdots e_{n-2}e_{n-1}
\end{pmatrix}
$$.
Let $b=e_n$.
For $i$ from $n-1$ to 2 inclusive downwards, let $p_i=p_ib$ and $b = e_ib$.
Let $p_1=b$.

The number of multiplications performed by the algorithm above is $3(n-2)$.

I believe that is the tight lower bound. However, I have not been successful proving it even though I have tried a few times. I am still trying from time to time.


Clustering algorithm with specific cluster grouping areas I'm looking for a way to cluster points in a given space, where clusters form around specific closed, allowed zones of that initial space. Each allowed zone should be surrounded by points of its cluster.

However, it is not only necessary to match the points to the closest allowed zone, but also to take into consideration the distance to other points of the same cluster.

In the example image given, in the clustered picture, the green points at the top right belong to the green cluster despite being closest to the blue area, because their neighbours are all green.

Ultimately, a network would be created from each cluster (lets say the points are a series of sinks), and linked to each respective zone via a single optimally placed point within the zone (which represents the source). A cost function would evaluate the cost of the network (i.e. minimizing the cost of a weighted graph). The difficulty is that the optimal placement of the source point is not known until the cluster is defined. The overall goal is to minimize the cost of all the networks combined.

Is there any algorithm available that can do this type of clustering? Otherwise how would you proceed?

One approach would be to devise a loss function for each point, that says how much you will penalize the cluster assigned to that point, as a function of what clusters are assigned to its neighbors and what the nearest zones are; then let the total loss be the sum off the losses for each point; and then use some optimization algorithm to find the assignment that minimizes the total loss.


Proving that an algorithm $A$ runs in $\Theta(f(n))$ time in the worst-case I wanted to understand how to establish both the lower $\Omega$ and upper bound $O$ on an algorithm to conclude it runs in $\Theta$ (note that I am not trying to prove that the algorithm is the most optimal and that no better algorithm exists).

To establish a $O$ I thought that one just has to prove somehow that the algorithm will never take more than $f(n)$ (for sufficiently large inputs) for alll possible input to the algorithm $A$. I think that should establish an upper bound in the worst-case, right? (since we are considering an upper bound for all inputs, it satisfies the worst-case scenario because it considers every single input).

But to establish a $\Omega$ in worst-case we need to argue that it will take at least $f(n)$ for some family of inputs (of size $n$). Is this correct?

My reasoning: In worst-case analysis we care about the performance of our algorithm in the worst-case. So to establish a $\Omega$ we need to show that there is exists some input (i.e. one that makes the specific algorithm perform the slowest) that could be given to use adversarial (that is why we need the quantifier exists rather than for all). So if there is some input that makes $A$ run in $f(n)$ in the worst case, an adversary could give us that input every time so we always run in $f(n)$. So we only need one to exists. But if we show we can never run in more than $f(n)$ then that input is really the "worst-case" because there cannot be any input that makes us run is more than $f(n)$. Is that sort of right? Basically, there exists guarantees worst case lower bound since an adversary could always give us that input and the for all guarantees a upper bound on any other potentially "worst" input.

Your observations are correct for the worst-case time complexity, which is the most common measure of time complexity, other than a small point – usually we prove an upper bound of $Cf(n)$ and a lower bound of $cf(n)$, where the constants $c,C$ need not match (and usually aren't explicit, being instead hidden in asymptotic notation).

There is a subtlety here – as you correctly mention, formally speaking we need a hard instance for every $n$. Usually this is not a problem since instances can be "padded" – if we have a construction that only works directly for even $n$, perhaps we can pad it to get a construction that also works for odd $n$. But in computational complexity we are sometimes considering more general and abstract cases in which this is not the case, and the only guarantee is that the running time is $f(n)$ for infinitely many $n$. We denote this by $\Omega^\infty(f(n))$ or $\Omega_\infty(f(n))$. This is the negation of $o(f(n))$, that is, all we can conclude if $o(f(n))$ doesn't hold.


Can I mix LL and LR parsing? I want to go RD parsing with Shunting Yard for expression (for the sake of  easier operator precedences and less left-recusion), is that considered no-good because nobody did that before?

Using recursive descent in combination with an operator precedence variant for expressions is a very common approach. You might also want to search for Pratt parsing.

An older, now uncommon technique which combines LL and LR parsing is "left-corner" (LC) parsing, which should also be easy to search for.

In practice, the existence of easy-to-use and efficient LR parser generators makes all of these less powerful techniques much less useful. LC parsing was pretty well obsoleted as a technique with the discovery of the LALR algirithm.


Definition of complexity classes? My book uses this definition for the Polynomial complexity class ($L$ is a language over $\{0,1\}$):

$$\mathrm{P} = \left\{L\subseteq\{0,1\}^*\;\middle|\; \begin{array}{l} \text{there exists an algorithm $A$ that decides $L$} \\ \text{in polynomial time}\end{array}\right\}\,.$$

But by this definition, don't all languages belong to the polynomial complexity class? Because if I define $A$ to be 1 for all languages, then $A$ would decide all $L$ in constant time (and therefore polynomial time), since it would return 1 immediately, meaning all languages would belong to polynomial complexity.

Why is my logic incorrect?

You seem to be confusing languages and strings.

An algorithm that decides a language $L$ is an algorithm whose input is a string $w$ and whose output is true if $w\in L$ and false if $w\notin L$.  As such, an algorithm can only decide one language: specifically, the language
$$L_A = \{w\mid A(w)=\mathrm{true}\}\,.$$

So, when you say, "then $A$ would decide all $L$", you're making a category error. An algorithm cannot possibly decide more than one language. What you've described is an algorithm that outputs true for every input: in other worse, an algorithm that decides the language $\{0,1\}^*$.

Note that $A$ decides a language by taking strings as inputs; it doesn't take languages as input and decide whether that langauge is in P.


Calculating this sum in $O(n)$ time Assume that $\forall 1 \leq i \leq n : a>0, c_i > 0 $ where $n \in \mathbb{N}$. I need to show that it is possible to compute this sum in $O(n)$ time:

$$I = \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n}$$

(a sum over all binary vectors of length $n$)
I notice that in $I$, for any fixed $1\leq i \leq n$, we have that $a^{c_i\epsilon_i} = 1$ in $2^{n-1}$ of the times, and $a^{c_i}$ in the other $2^{n-1}$ of the times. So $I$ can be written as follows:

$$2^{n-1}\cdot a^{c_1} \cdot \sum_{(\epsilon_2,...,\epsilon_n)\in \{0,1\}^{n-1}}a^{c_2\epsilon_2}\cdot ... \cdot a^{c_n \epsilon_n} + 1 \cdot \sum_{(\epsilon_2,...,\epsilon_n)\in \{0,1\}^{n-1}}a^{c_2\epsilon_2}\cdot ... \cdot a^{c_n \epsilon_n}$$

But coming to expand this for $i=2,...,n$ I immediately realize that this won't turn out to be $O(n)$. I would appreciate some guidance.

You can prove this by full induction, which gives you an algorithm, too. The claim is $$I_n = \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} = (1 + a^{c_1})(1 + a^{c_2}) \ldots (1 + a^{c_n}) $$
The product of the right side can be computed in $O(n)$ steps if the exponentiation requires constant time.

Proof:

For $n=1$ the claim is obviously true: $I_1 = 1 + a^{\epsilon_1}$.
$n \rightarrow n+1$: Let the claim be true for $n$:
\begin{eqnarray}
(1 + a^{c_{n+1}})I_n & = & (1 + a^{\epsilon_{n+1}})\sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} \\
 & = & \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} + a^{c_{n+1}}\sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} \\
 & = & \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n,\\ \epsilon_{n+1}=0}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n + c_{n+1} \epsilon_{n+1}} + \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n,\\ \epsilon_{n+1}=1}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n + c_{n+1} \epsilon_{n+1}} \\
 & = & \sum_{(\epsilon_1,...,\epsilon_n,\epsilon_{n+1}) \in \{0,1\}^{n+1}}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n + c_{n+1} \epsilon_{n+1}} \\
 & = & I_{n+1}
\end{eqnarray}


Need to remove indirect left recursion from CFG I need to remove indirect left recursion from the following CFG:
remove indirect left recursion from the following CFG.
$$A → Ba| b$$
$$B → Cd | e$$
$$C → Df | g$$
$$D → Df | Aa | Cg$$

In the following solution, I have expanded all the non-terminals to get them converted to direct recursion, instead of indirect recursion (if applicable), so that I may apply Rule for removal of direct left recursion:

$$A → Ba → Cda → Dfda → Aafda$$
$$C → Df → Cgf$$
$$D → Df$$
$$D → Cg → Dfg$$
$$D → Aa → Dfdaa$$
So, it becomes:
$$A → Aafda| b$$
$$B → Cd | e$$
$$C → Cgf | g$$
$$D → Df | Dfg | Dfdaa | ba | gg$$
So, it becomes (after removal of direct left recursions):
$$A → bA'$$
$$A' → afdaA'| eps$$
$$B → Cd | e$$
$$C → gC'$$
$$C' → gfC' | eps$$
$$D → baD' | gg D'$$
$$D'→ fD' | fgD' | fdaaD' | eps$$

My specific Question is: Do I have to follow this way (convert all production rules emanating from all non-terminals or should I do that for only one, e.g. D?

You should focus on trying to only modify productions that aren't "good". A production is "good" if it :

Starts with a terminal,
Is an epsilon production, or
Is in the form A->B (followed by a series of terminals and non-terminals) and we can partially order the non-terminals so that A<B. We'd also have to do some extra checks if B being nullable. That is, if B is nullable, we'd have to consider all productions in which B occurs and is nulled. For example, suppose we have the grammar:

A -> BAa
B -> b | esp

At first glance, the rule A->BAa might appear good (because we can assert that A<B), but if B is nulled, we end up with the production A->Aa which is bad. This is usually not a big problem, but you've got to make sure you cover all your cases. Note that this doesn't apply to your example, but I'd figure I'd be thorough.

For your grammar:

A->Ba is good since we can assert that A<B.
b is good because this is a terminal.
For similar reasons, all the productions of B and C are also "good", so we shouldn't change them.
For D, there are several problems. Obviously, we cannot assert that D<D, and we also can't assert that D<A or D<C (since we assumed that A<B<C<D in our previous step). However, the productions for A, B, and C are all "good", so we can substitute those in and expose the hidden left recursion (as you've done in your work).

In short, you should only worry about modifying "bad" productions and leaving any "good" ones as they are. It's not always possible to do this, but in general, it'll save you work.


Upper bound on the average number of overlaps for an interval within a set of intervals Let $\mathcal{I}$ be a set of intervals with cardinality $L$, where each interval $I_i \in \mathcal{I}$ is of the form $[a_i, b_i]$ and $a_i, b_i$ are pairwise distinct non-negative integers bounded by a constant $C$ i.e. $0 \leq a_i < b_i \leq C$. We say a pair of intervals $I_i, I_j \in \mathcal{I}$ overlap if the length of overlap is $> 0$.

Define a function $F(i)$ which computes the number of intervals in $\mathcal{I} \backslash I_i$ that interval $I_i$ overlaps with.
\begin{equation}
F(i) = \sum_{j=1, j \neq i}^{L} Overlap(I_i, I_j)
\end{equation}
where the function $Overlap(I_i, I_j)$ is an indicator function which returns 1 if $I_i, I_j$ overlap, else it returns 0.

The average number of overlaps for the intervals in $\mathcal{I}$, denoted by $Avg(\mathcal{I})$ is given by $Avg(\mathcal{I}) = \dfrac{\sum_{i=1}^{L}F(i)}{L}$.

The question is, suppose we are allowed to choose the intervals in the set $\mathcal{I}$ with the following additional conditions:

For any $t \in [0, C]$, we have at most $M$ (and $M < L$) intervals in $\mathcal{I}$ such that $t$ is contained within those $M$ intervals. Stated differently, at most $M$ intervals overlap at any point in time.
Any interval in $\mathcal{I}$ overlaps with at most $K$ other intervals, and $M < K < L$.

then, what is an upper bound on $Avg(\mathcal{I})$ for any choice of the intervals in $\mathcal{I}$ satisfying 1, 2?

In case you are wondering, this problem is of interest to me in order to be able to study the run-time of a scheduling algorithm.

I am unable to come up with a non-trivial upper bound for $Avg(\mathcal{I})$ and would be interested to know if the problem I stated has been studied. I am also open to ideas on how one may be able to obtain a tight upper bound for $Avg(\mathcal{I})$.

If we ignore $L$ and focus only on the parameters $C,K,M$, the following upper bound is asymptotically tight, i.e., it's about the best you can do, up to a constant factor:

$$\text{Avg}(\mathcal{I}) \le \min(MC,K).$$

Proof that it's an upper bound: Fix any interval.  We're promised that it overlaps with at most $K$ others.  Also, the interval has at most $C$ points in it, so by a union bound over those points, we can also infer it overlaps with at most $MC$ others.  Therefore, it overlaps with at most $\min(MC,K)$ others.  Now the average of a bunch of numbers that are all $\le \min(MC,K)$ will itself be $\le \min(MC,K)$.

Proof that it's tight: I will show the construction of a set of intervals where $\text{Avg}(\mathcal{I}) \sim \min(MC,K)/4$.  There are two cases:

Case 1: $K \ge MC$.  Then use $M/2$ copies of each interval of the form $[i,i]$ (i.e., each length-0 interval), and use $M/2$ copies of the interval $[1,C]$.  You can observe that the latter each intersect with $\sim MC/2$ other intervals (and all intersect with fewer than $K$).  So, the average is about $MC/4$.  This gives a collection of intervals where each point intersects with $M$ intervals, each interval intersects with $\le K$ others, and $\text{Avg}(\mathcal{I}) \sim MC/4 = \min(MC,K)/4$.
Case 2: $K < MC$.  Set $C' = K/M$, apply the above construction to the interval $[1,C']$ instead of $[1,C]$, and we obtain a collection of intervals where each point intersects with $M$ intervals, each interval intersects with $\le K$ others, and $\text{Avg}(\mathcal{I}) \sim MC'/4 = K/4 = \min(MC,K)/4$.

If you also care about the dependence on $L$,  you might be able to build on the above analysis to see how it might depend on $L$.


Infinite sequence has $m$ consecutive digits – regular languages Suppose we have an infinite sequence over the decimal alphabet, call it $w$. For $k\in \{0,1,2,3,4,5,6,7,8,9\}$, let $L_k = \{m\geq 0: \text{$w$ contains a run of $m$ $k$'s}\}$ be a language. Here a run denotes a contiguous block of the sequences. Prove that $L_k$ is a regular language.

Here is my idea. Clearly, if $w$ contains arbitrarily long runs of $k$, then $L_k$ is pretty much just the set of all positive natural numbers, which is regular. But if $w$ has a maximum run of $k$'s, then $L_k$ is a finite set, which means it's regular. This is as far as I got, this language "feels" like it shouldn't be regular, but I am told it is. Would the regularity of $L_k$ even depend on whether it is possible to compute whether $w$ has a maximum run of $k$'s?

You don't explain how the input to $L_k$ is encoded, but $L_k$ will be regular under any reasonable encoding.

Indeed, if $w$ contains a run of $m$ many $k$'s, then it also contains a run of $m'$ many $k$'s for any $m' \leq m$. Therefore either $L_k$ is finite (indeed, of the form $\{0,\ldots,m\}$) or it consists of all of $\mathbb{N}$.

You seem to be troubled by the fact that $L_k$ is not necessarily computable from (a description of) $w$. But there is absolutely no such requirement – all we have to show is that for each $w$, the languages $L_k$ are regular. We are not claiming that we can compute $L_k$ from (a description of) $w$.


You prove that vertex cover reduces to some problem A, does that mean that A is NP-Complete? My question is essentially the title. Let's say you have some random problem A. You prove that Vertex Cover (which is NP-Complete) reduces to A. You know nothing else about A besides that Vertex Cover reduces to it. Does that mean that A is NP-Complete? Or because we don't know if P = NP, we technically don't know if A is in NP or P?

Let's start with the relevant definitions:

  A problem $A$ is NP-complete if:

  $A$ is in NP, and
  $A$ is NP-hard.

  A problem $A$ is NP-hard if for every problem $B$ in NP, there is a polytime reduction from $B$ to $A$.

Using these definitions, you can prove the following result:

  If a problem $B$ is NP-hard and there is a reduction from $B$ to $A$, then problem $A$ is also NP-hard.

Applying this to your problem, if there is a reduction from vertex cover to $A$, then $A$ is NP-hard. If $A$ is also in NP, then it is furthermore NP-complete. Whether P=NP or not has absolutely no bearing on this.

Note that there are NP-hard problems which are provably not in NP. For example, the halting problem is NP-hard, but is known not to be in NP.


Space complexity of Horner's method Following is the excerpt from wiki

If numerical data are represented in terms of digits (or bits), then
the naive algorithm also entails storing approximately $2n$ times the
number of bits of $x$ (the evaluated polynomial has approximate
magnitude $x^n$, and one must also store $x^n$ itself). By contrast,
Horner's method requires only $n$ additions and $n$ multiplications, and
its storage requirements are only $n$ times the number of bits of $x$.

I don't understand, how?

Storing the output requires roughly $n|x|$ bits (where $|x|$ is the size of $x$ in bits); this is since the numbers involved have magnitude $\Theta(x^n)$. This is all that Horner's method requires, since it only keeps track of one value, the current "partial sum".

In contrast, the naive method keeps track of two values: the current partial sum, and also the current power of $x$. Each of these requires (towards the end of the process) roughly $n|x|$ bits to store, and both of them require $2n|x|$ bits in total.


Boolean algebra truths with more than one digit I understand that when you 0 AND 0 it will result in 0 and that 1 AND 1 will result in 1 etc but what I don't understand is if the question was 01 AND 11. How would I work this out?

This notation is usually used for bitwise operations. You compute the operation bit by bit – the $i$th bit of the answer is (in this case) the AND of the $i$th bits of the inputs.

From a more theoretical side of things, this bitwise rule does turn $k$-bit numbers into a Boolean algebra. Boolean algebras are sets together with several operations that satisfy certain axioms (there are several equivalent versions which are easy to find online). Stone's representation theorem states that every Boolean algebra is a field of sets, which in the finite case just means that it consists of $k$-bit numbers for some $k$.

Boolean algebras have found deep applications in set theory, though the relevant Boolean algebras are always infinite. In this application at least, it is certainly possible to think of the values of the Boolean algebra as truth values. One can then obtain a more conventional truth value by using an ultrafilter.


Search string excluding longer string containing substring that contains string, not exclusively longer string How you define a search of text to find a string A, but exclude results that contains B only (which contains A), but not the both string A and string B?

For example:

String A : "Great Wall"
String B : "Great Wall of China"
Text 1: "The Great Wall"
Text 2: "The Great Wall of China"
Text 3: "The Great Wall of China is a Great Wall"
Text 4: "Lorem Ipsum"

I've used Bold to indicate when String A is present and Italics when String B is present.

We would like to search for Texts that contains A, and A + B, but not B only.

So the results should be the Texts 1 and 3.

What approach would enable us to find these results?

Also, we are using a search that can provide us only a list of items that contains a string.

Finite automata to the rescue!

Let

$\mathcal{A} = \Sigma^* \cdot \{A\} \cdot \Sigma^*$ and
$\mathcal{B} = \Sigma^* \cdot \{B\} \cdot \Sigma^*$

be the regular languages that contain all strings with substring $A$ resp. $B$.

Note then that

$\qquad\displaystyle L = \overline{\mathcal{B}} \cdot \{A\} \cdot \overline{\mathcal{B}}
\ \cup\
\mathcal{A} \cdot \mathcal{B}
\ \cup\
\mathcal{B} \cdot \mathcal{A}$

is the set of all strings you are looking for, and from basic closure properties of REG we know that it is regular as well.

Constructing a (minimal) DFA from the above description using standard constructions yields an effective method that may or may not be efficient.


ML Algorithm for getting top pick in each sample I have a dataset of streets - and each street contains several houses.
street_id | house_id | number of calls | number of people living | etc...
1         | 1        | 10              | 5
1         | 2        | 3               | 1
2         | 3        | 4               | 2
2         | 4        | 15              | 19

My goal is to find for each street, the most popular house.
I have GT - streets with several houses, and for each street, which house was the most popular house.
For the data example above - the results should be (street 1 -> house 1, street 2 -> house 4) because houses #1, #4 are the most popular in their street.
Popular will be determined with classification algorithm - we have much more features than the 2 above (they are just for example). That's why we have the GT for - so our algorithm can learn what popular is.

We can find the most popular street using features about each house -

number of calls made from house
number of people living in house
etc

But we don't need to find all of the popular houses from all of the houses - we need for each street, to find the most popular house.
Do you know how can I solve this task?
I've thought about regular classification, but that would results giving all of the popular houses, and not one for each street.
Thanks in advance!

You will have to restructure your data in such a way that one input contains data pertaining to only one street (but of all the houses.) This involves grouping the data by street_id.
You should then use several inputs in such a way to train your model to find out the popular house. Since it will be a supervised-learning task, you'll have to label your data accordingly.
But there's a problem here. Each street has different number of houses. One way to handle this problem is by fixing an upper bound on the number of houses per street and padding your data up to this upper bound.


How to prove with induction So far I have learned how to write proofs by induction and it went fine until I got this recursive problem, which I'm not quite sure how to begin and how to prove that with induction.

            P(2·a,⌊b/2⌋) : b>1 and b is even number
P(a,b):=    P(2·a,⌊b/2⌋)+a : b>1 and b is odd number
            a :b=1

to prove is for all a,b ∈ N+ -> P(a,b)=a·b

Please don't show me the proof but how to deal with this kind of question.

Thank you

In the recursive definition

$$ P(a,b) = \begin{cases} P(2a,\lfloor b/2 \rfloor) & b > 1, b \text{ even} \\
P(2a,\lfloor b/2 \rfloor) + a & \text{if } b > 1, b \text{ odd} \\
a & \text{if } b = 1
  \end{cases} $$

the value of $b$ always decreases in a recursive call. Therefore you should prove the property $P(a,b) = a \cdot b$ by induction in $b$. We use the strong induction principle.

Base case - $b=1$:   $P(a,1) = a$ and $a \cdot 1 = a$.

Inductive step - assume for all $k < n$, prove for $n$:

Suppose $b$ is even. We then have $P(a,b) = P(2a,\lfloor b/2 \rfloor)$. Since $b$ is even, we have $\lfloor b/2 \rfloor = b/2$. Since $\lfloor b/2 \rfloor < b$, we have by induction hypothesis that $P(2a,\lfloor b/2 \rfloor) = 2a \cdot \lfloor b/2 \rfloor = 2a \cdot b/2 = a \cdot b$.

Suppose $b$ is odd. Since $b$ is odd, we have $\lfloor b/2 \rfloor = (b-1)/2$. We now have $P(a,b) = P(2a,\lfloor b/2 \rfloor) + a = 2a \cdot (b-1)/2 +a = a(b-1) + a = a (b-1 + 1) = ab$.


Find the longest subsequence of two strings I want to know which is the best way to find the longest common subsequence of two strings

You know the recipe for dynamic programming: define some subproblems, then show how to use solutions to smaller subproblems to help you solve larger subproblems.  So, what you have tried as candidate subproblems?

Hint: When you have a dynamic programming problem that takes a string as input, what are some candidate ways to define subproblems?  (Prefixes, suffices, substrings...)  Now, how might you apply that general advice here?

I'm not going to spell out the full answer, as this sounds like homework, and to learn from homework, you need to struggle with it yourself.


Can a second process execute when the Operating System is performing a context switch? A process was running on a uniprocessor system. It is being context switched. While the scheduler is performing this context switch can another process be allocated the CPU while the context switch is being performed?

(1) First, lets define our terms. From Wikipedia:

  In computing, a context switch is the process of storing and restoring the state (more specifically, the execution context) of a process or thread so that execution can be resumed from the same point at a later time.

In other words, a context switch is the act of transfering control from one process to another. To recall the current process, the CPU has to take a snapshot of its state before allocating resources to the new process.

(2) Now let's answer exactly what get's saved. Also from Wikipedia:

  registers and memory maps, updating various tables and lists, the PC, stack pointer, etc.

So, pretty much everything in the CPU needs to be stored somewhere else before loading in a new process' state.

Now let's consider your question by reasoning about two arbitrary processes, PID 1 and PID 2

PID 1 is preparing to hand the CPU to PID 2 and begins storing its state. Thus, all critical CPU elements are in use. One by one as these elements are stored, they are freed (often the timing is more complex) and the CPU can allocate those resources to PID 2.

Squeezing in an extra process would just cause overhead in the primary context switch between PID 1 and PID 2. You might even consider it a context switch inside of a context switch for any nontrivial process. Sure, if the ALU is open, it could probably do a quick calculation or two but what good would those results do when not a part of a process which is far more than just a few calculations?

Theoretically possible? Sure. Reasonable, NO. Instead of trying to use that time "lost" during a context switch, innovations focus on classifying different degrees of context switches. Basically, if you have a lightweight switch between a process, or perhaps a thread, the entire processor is not held up while doing so. For more reading, I suggest: https://en.wikipedia.org/wiki/Light-weight_process to see the difference in process types.

Clarification: The scheduler is a kernel space process.


Why is this grammar an LL(2) grammar? I had a question regarding LL($k$) grammars. I came across a problem that I attempted to solve, but my answer varied from the solution and I wasn't sure why.

$$L = \{a^{n + 2}b^mc^{n + m}\ :\ n \ge 1,\ m \ge 1\}$$

The grammar I came up with is:

$$
\begin{align}
S & \rightarrow aaA \\
A & \rightarrow aAc\ \vert\ bBc \\
B & \rightarrow bBc\ \vert\ bc \\
\end{align}
$$

According to the solution, this given language has an LL($2$) grammar, but the answer I came up with was LL($4$).

My reasoning is that since the start of the language has at least three $a$'s, you need to check the fourth position in order to see which production to use afterwards. Then you can "slide" the window one position to the right to check subsequent productions.

Why is it considered LL($2$)?

Thank you.

An LL parse produces a leftmost derivation, which means that at each point in the derivation, the leftmost non-terminal must be replaced by one of its productions. The issue is to decide which production to use.

A grammar is LL(k) if the production to be used in the leftmost derivation can always be determined by examining only the terminals prior to the first non-terminal and the $k$ following terminals in the input. (These will be the next $k$ symbols in the input if we're doing a left-to-right parse; the terminals prior to the non-terminal will already have been input.)

In your grammar, neither $S$ nor $A$ present any problems at all. $S$ only has one production, so there is no need to examine any terminal at all to make a decision. $A$ has two productions, but their first terminal differs so it is trivial to predict which one to select: if the next input symbol is $a$, select the first alternative; if it is $b$, select the second one.

$B$ also has two productions, but both of them start with a $b$. So we need to look at least one symbol further in the input. Now, what is the second symbol in a derivation starting with each production for $B$? For $B \to b c$, the second symbol is clearly $c$. In $B \to b B c$, the second symbol must be the first symbol in some derivation of $B$. But, as we've just observed, every derivation of $B$ starts with $b$. So the second symbol in $B \to b B c$ must be a $b$.

With that, we have a complete decision procedure:

If the non-terminal to expand is $S$:

choose the production $S \to a a A$

If the non-terminal to expand is $A$:

If the next input is $a$:

choose the production $A \to a A c$

If the next input is $b$:

choose the production $A \to b B c$

If the non-terminal to expand is $B$:

If the next two input symbols are $bb$

choose the production $B \to b B c$

If the next two input symbols are $bc$

choose the production $B \to b c$

If there is no non-terminal left

Report success

If none of the above rules apply

Report failure

The longest sequence of terminals we need to examine in any of those rules is 2. So the grammar is LL(2).


Why do we take null closure two times while converting from Epsilon-NFA to NFA? I am studying Theory of Automata. I was studying conversion of Epsilon-NFA to NFA. I had to take null closures of states two times, before and after the specific input.

Could someone explain, what is the reason behind this?

You might need to do some $\varepsilon$-transitions before reading the first character of the input, and after reading the last character. It's probably easier to just consider them before and after every character, so every character is treated the same way, than to make a special case of the first or last character.


What are some applications of computing the permanent of a matrix? What are some applications that require computing the permanent of a matrix?

One application I know of is related to graph theory and matchings. Apparently, the number of perfect matchings of a bipartite graph is the permanent of its incidence matrix.

I am curious to know more applications of matrix permanent.

Valiant proved that the permanent is $\# P$-complete, which means that an efficient algorithm for computing the permanent can be used to solve any problem in $\# P$, such as counting the number of satisfying assignment to a CNF, the number of Hamiltonian circuits, the number of $k$-colorings and so on. In particular, it could be used to solve NP-complete problems.


Eliminate non-local references from closure For a code similarity detection framework I need to eliminate references to non-local variables, for example having the following closure:

{
  var a;
  var b;

  var f = function() {
    a = 5;
    b = 6;
  }

  f();
}

would be converted into something like:

{
  var a;
  var b;

  var f = function() {
    var a = 5;
    var b = 6;
    return tuple(a, b);
  }

  a, b = f();
}

Another approach would be:

{
  var world;
  var a;
  var b;

  var f = function(world) {
    world = update_world(world, "a", 5);
    world = update_world(world, "b", 6);
    return world;
  }

  world = f(world);
  a = get_world(world, "a");
  b = get_world(world, "b");
}

Basically, convert a stateful program to a purely functional one. The goal is then to transform the resulting program into the lambda calculus, normalize and look for isomorphic subtrees.

Is there a formalization of what I'm trying to do?

I think what you want is essentially conversion to static single assignment (SSA) form, followed by closure conversion, followed by conversion to continuation passing style.

Static single assignment form guarantees that each variable is written exactly once in the program text.  That this is the key step in converting imperative to functional programs is argued by

  Andrew W. Appel. SSA is functional programming.
  SIGPLAN Notices, 33(4), 1998.

  Richard A. Kelsey. A correspondence between continuation
  passing style and static single assignment form.
  Proc ACM SIGPLAN Workshop on Intermediate
  Representations, January 1995.

  Peter J. Landin. The mechanical evaluation of expressions.
  Computer Journal, 6(4):308–320, 1964.

This starts to get really interesting for programs with loops. You need to convert the loops into recursive calls, and make a unique copy for the variables written in each iteration of the loop.  In the traditional loop optimization community this technique is called scalar expansion or (sometimes) dynamic renaming.

  David J. Kuck, R. H. Kuhn, David A. Padua, B. Leasure,
  and Michael Wolfe. Dependence graphs and compiler
  optimizations. In Conference Record of the Eighth
  Annual ACM Symposium on Principles of Programming
  Languages, pages 207–218, Williamsburg, VA, January
  1981.

  Ron Cytron and Jeanne Ferrante. What’s in a name?
  The value of renaming for parallelism detection and
  storage allocation. In Proceedings of the 16th Annual International
  Conference on Parallel Processing, pages 19–27,
  St. Charles, IL, August 1987.

In the functional programming community this involves making closures and continuations explicit:

  Andrew W. Appel and Trevor Jim. Continuation passing,
  closure-passing style. Proc. Symp. on Principles of Programming Languages (POPL),
  1989.

  Guy Lewis Steele. RABBIT: A compiler for Scheme.
  Technical Report AITR-474, MIT Artificial Intelligence
  Laboratory, May 1978.

I needed to do these conversions, for the automatic parallelization techniques described in my dissertation.  Chapters 3, and 9.1.

  Matthew Frank, SUDS: Automatic Parallelization for Raw Processors, Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, May 23, 2003.


Is it necessary to traverse every letter in the tape of a Turing Machine? Say I want to make a very simple Turing Machine that accepts only strings that contain one or more a's. Can I simply send have the machine move a HALT state once it reads one a, even if there are many letters after that first a? Or would this be bad practice or unacceptable for a Turing Machine?

To the title question - no, to the flipped version of the same question in the body - yes. It is typically fine to halt without processing the entire input (however see Raphael's answer for certain technicalities in this respect).

There's not really such a thing as "good" or "bad" practice with a Turing Machine in the sense that there are "good" and "bad" practices when programming on a "real" computer.

As they are theoretical models for computations, they are at their best when they prove (or assist in proving) what you need to prove in as clear and direct manner as possible. In this light, as long as your machine only performs permissible actions, then everything is fine - so no cheating, but beyond that it's all good.


Data structures as algorithms themselves Can data structures be thought of as algorithms themselves?

For example, I could implement a stack data structure that has certain non-functional characteristics.

Is the separation between data structures and algorithms formally defined?

Yes, a data structure can be thought of as an algorithm.  A data structure is a collection of state together with one or more algorithms that operate on that state.

A data structure can be thought of as a tuple $(s,f_1,f_2,\dots,f_k)$ where $s$ is its state, and each $f_i$ is an operation that can be performed on the data structure; the operation $f_i$ can read the state $s$ and its input parameters, and possibly modifies $s$ and possibly returns a new value.  Alternatively, from an object-oriented viewpoint, you can think of a data structure as an object; $s$ is the state of the object, and $f_1,\dots,f_k$ are the methods that can be invoked on the object.  Normally, $f_1,\dots,f_k$ are described as algorithms that operate on $s$ and their inputs.  This lets you use the language and concepts of algorithms to analyze various data structures.

I'm not sure there is a formal specification of what counts as a data structure, but this seems to get about close as I've seen.

You might be interested in the notion of abstract data type (ADT) from programming languages.  You can think of a data structure as an ADT, or more carefully, you can think of an ADT as the specification and the data structure code as a particular implementation of that ADT.  When people talk about data structures informally, they don't always distinguish between specification vs implementation; the term ADT helps make that distinction more precise.

I don't know if people normally try to formally define what we mean by "data structure"; it's a loose term that is more useful to illustrate a particular type of concept in computer science.  If I wanted to make it as precise as possible, the notion of an ADT would probably be the first formalization I'd consider.  An ADT is like an interface specification, and a specific data structure is like a particular way of implementing that specification.


Operator-precedence grammar`s symmetrical rule I have a basic question, but I cannot find an answer anywhere on the Web. I have the following grammar rules:

S -> if C ;
C -> O < O
O -> O + i
O -> i

The part than I`m interested in is at rules 1,2 and 4.

I have calculated First(O) = {i, +} and Last(O) = {i}.

So, First(C) = {i,+,<} and Last(C) = {<, i}.

Also, if  <*  First(C) and Last(C)  >*  ;

I have build the precedence table and now I want to parse the input: if < ;

So when i parse it, I first have if on top of my stack. Then I look at <, if <* <, so I push < on top of the stack. So now I compare < to ;, ; has higher precedence according to the rules, so I must pop. The last part is trivial, and leads me to S, thus accepting the sentence.

BUT, as we can clearly see from the rules, this sentence should not be accepted (we only have 1 <, not enough to form C in order to reduce it).

I have noticed that this happens because there is a symmetrical rule (rule 2 in our case), which means that if <* {i, <} >* ;, so we cannot verify that there was indeed an < or only an i.

What is the solution to this problem? How do we handle these special cases where symmetrical rules`s precedence relations overlap? I`m sure there must be one, because this grammar is conceptually close to a programming language parsing problem itself.

Thank you for your time!

It's not the symmetry of rule 2 which is the problem (whatever you mean by symmetry). The problem is (more or less) inherent to the operator precedence algorithm.

O-P parsing was dropped from the Dragon book between the first and second editions, presumably because the authors no longer believed to be a useful parsing technique [Note 1]. So I'm quoting from the first edition, which I still have on my bookshelf for odd sentimental reasons [Note 2]. And what it says is: (p. 203)

  As a general parsing technique, operator-precedence has a number of disadvantages… since the relationship between a grammar for the language being parsed and the operator-precedence parser itself is tenuous, one cannot always be sure the parser accepts exactly the desired language.

And that's the case. Operator-precedence grammars tend to accept a superset of the desired language, and you need to augment them with a number of checks to ensure that invalid sentences like the one you threw at your parser don't actually get recognized.

The classic O-P construction -- the one I think you are referring to with your use of $First$ and $Last$ -- has two problems, one inherent to O-P parsing and the other which can be (mostly) avoided. The first problem is that all non-terminals look the same to an operator-precedence grammar. That's the essence of the O-P parsing technique, so there's not much that can be done about it. The other problem is that $First$ (and $Last$) don't even distinguish between the presence and absence of a non-terminal. For this reason, $First(O)$ (not to be confused the the $LL$ algorithm's $FIRST_k$ function) includes $\fbox{+}$, and $First(C)$ includes $\fbox{<}$. In both cases, the terminal would not be in the $LL$ $FIRST$ set, because it does not appear exactly at the beginning of the right-hand side, but rather  immediately following the non-terminal at the beginning.

Given that the $First$ function can't distinguish between terminals which follow non-terminals and terminals which just start a production, it is hardly surprising that the parser doesn't really care whether or not $\fbox{<}$ has an argument. Regardless of whether there is an expression before the $\fbox{<}$ or not, the grammar simply sees that $\fbox{if} \lessdot \fbox{<}$. And consequently, it doesn't complain when the two tokens are consecutive.

Now, in theory, the O-P parser uses precedence relations only to find a possible handle. Once it does so, the parser should find the grammar rule for which the handle is the right-hand side, if any, or throw an error. But I've rarely seen a description of O-P parsing which actually does that. Instead, the simplifying assumption is made that you can figure out which rule to reduce with by just looking at the last terminal on the stack, and that the input is correct [Note 3].

It's actually pretty easy to extend O-P to get around this problem. The basic idea is to divide the relations into two classes: those which apply to adjacent terminals, and those which apply to terminals separated by a single-non-terminal. (Since the grammar is an operator grammar, those are the only two possibilities.) I refer to these as 0- and 1-superscripted relations, where the number refers to the number of intervening non-terminals.

To compute these relations, we start by compute two groups of $First$ and $Last$ sets, using the same subscript notation. So $First^0(N)$ is the set of terminals which immediately start a right-hand side of $N$, and $First^1(N)$ is the set of terminals which immediately follow a non-terminal which immediately starts a right-hand side.These two sets are not necessarily disjoint, for example in the case of an operator like $\fbox{-}$ which can be either prefix or infix, but their union is the classic $First(N)$ set.

More precisely, using the standard convention that lower-case letters $a$, $b$, $c$… represent terminals, upper-case letters $A$, $B$, $C$… represent non-terminals while $P$, $Q$… represent productions, and greek letters $\alpha$, $\beta$, $\gamma$… represent possibly-empty sequences of grammar symbols, either terminals or non-terminals, we define:

$$First^0(N) = \{ a : N \Rightarrow^*  a\beta \}$$
$$First^1(N) = \{ a : N \Rightarrow^*  B a\beta \}$$
$$Last^0(N) = \{ a : N \Rightarrow^*  \beta a\}$$
$$Last^1(N) = \{ a : N \Rightarrow^*  a\beta aB\}$$
Correspondingly, we define two of each precedence relationship.

$$a \lessdot^0 b \iff \exists N,B : N \to \alpha a B \beta, b \in First^0(B)$$
$$a \lessdot^1 b \iff \exists N,B : N \to \alpha a B \beta, b \in First^1(B)$$
$$a \gtrdot^0 b \iff \exists N,A : N \to \alpha A b \beta, a \in Last^0(A)$$
$$a \gtrdot^1 b \iff \exists N,A : N \to \alpha A b \beta, a \in Last^1(A)$$
$$a \doteq^0 b \iff \exists N : N \to \alpha a b \beta$$
$$a \doteq^1 b \iff \exists N,X : N \to \alpha a X b \beta$$
For each production $N \to \alpha A x \beta$, add $Last_0(A) \gtrdot_0 x$ and $Last_1(A) \gtrdot_1 x$

To parse, we use essentially the standard algorithm taking account of the presence or absence of non-terminals. Conceptually, we store both terminals and non-terminals on the stack. (In practice, I would keep separate stacks and use a flag on the terminal to indicate whether it has a non-terminal on top of it or not -- there can only be one, because it is an operator grammar.) At each step, we compare the incoming terminal with the topmost terminal on the stack. If the actual top of the stack is a non-terminal, we use the 1-superscripted relations; otherwise, we use the 0-superscripted relations. As before, if no relation exists between the two terminals an error is signalled (and that will catch your error).

Now, to assist with the identification of the production corresponding to the handle, we can store a little bit more information on the stack. When we push a terminal onto the stack, it is either because there was a $\lessdot$ relation with the previous stacked terminal, in which case we are starting a right-hand side, or there was a $\doteq$ relation with the previous terminal, which must be part of the same right-hand side. In either case, we can record the prefix of the appropriate RHS (up to the curren point) instead of the terminal. That has two advantages.

it lets us distinguish between prefix and infix operators in a natural way; and
it really lets us assign them different precedences, because we can actually define the precedence relations as relations between RHS location and incoming terminal, instead of terminal and incoming terminal, thereby allowing a bit more discrimination. (That's needed to give unary minus tighter binding.)

Now before you rush out and start coding a parser generator based on this idea, please re-read [Note 1], because at this point we are 90% of the way to rediscovering $LR$ parsing. I really believe that if you follow this algorithm closely, you will gain some useful intuitions for understanding $LR$ parsing. And it should be obvious that it is only a small step between "extended" O-P parsing and a table-driven $LALR(1)$ parser, at which point you might as well haul out bison or some other yacc-derivative and let it build your parser for you. [Note 4]

Notes

Personally, I would have dropped LL-parsing, but who am I to judge :) It's not that O-P parsing is at all useful once the LALR(1) construction algorithm is known. It isn't, and the problem you're having is a case in point. Any language parseable by O-P can be parsed correctly and unambiguously with LALR(1), and with the same computational complexity. (Indeed, with essentially the same amount of time and space.) The only reason to keep O-P hanging around at all is that (again, in my opinion), thinking about O-P parsing will (if you think about it the right way) lead you to the key insights which lead to LR parsing.
I like the cover.
In practice, there is another classic problem with O-P parsing, which was mentioned in the text I replaced with an … in the Dragon book quote: the algorithm as described can't distinguish between prefix and infix uses of $\fbox{-}$. The usual hack used to fix that problem is to use a small state machine (two states, typically) which is sufficient to reveal whether or not an operator was preceded by an operand. That's also sufficient to throw an error if an operator cannot be used as a prefix operator, so practical O-P parsers don't really have a problem. A while back, I described such an algorithm in a StackOverflow answer
I'm sure I'm not the first person to have thought up this idea, in several decades of very clever people thinking about parsing algorithms, but I haven't ever seen it described anywhere. As I said, I worked it out while I was trying to grasp the mechanics of bottom-up parsing, and afterwards it seemed a bit redundant. But if anyone passing by happens to know a literature reference, I'd appreciate a pointer.


I can construct DFA for $a^{3n+1}$ but pumping lemma says it is not regular Recently I stumbled across this language $L=\{a^{n}a^{{(n + 1)}^2-n^2} \in \Sigma^* \mid n\geq 0\}$ that I can rewrite as $a^{3n + 1}$.
So I applied the pumping lemma to see if it is non regular, and I get:

given a pumping length p I should have a string $z\in L$ such that $\mid z \mid \ge p$
I choose $z=a^pa^pa^pa$ such that $z\in L$ and $\mid z \mid = (3p + 1)\ge p$
now I can slipt the string in 3 parts, $z=uvw$ with $u=a^{p-1}, v=a,w=a^{2p}a$ and it satisfies the two following conditions of the lemma $\mid uv \mid \leq p$ and $\mid v \mid > 0$
then given $z = uv^iw$, if I pump $v$ I see that $z \notin L$ because if for example I choose $i=2$ than $\mid z \mid = (p-1)+i+2p+1=3p+2 \geq 3p+1$

So $z \notin L$ and it means that $L$ is not regular, but I noticed that I can construct a DFA that accepts this language:

So now I'm really confused. Probably I'm applying the pumping lemma in the wrong way but I don't understand where.
UPDATE
Now, thanks to all of you, I think I understood my mistake. So to prove that a language is not regular I have to show that every decomposition fails to satisfy the pumping condition for some pumping number $i$. But in this case there is a decomposition that satisfies the pumping condition so I can't prove that the language is regular (but we know it is regular because we can construct a DFA that accepts it).

You should notice that if the conditions hold, the language can be regular (necessary, but not sufficient). However, you proved the third condition is not held in your case, hence it is not regular which this is not true. Therefore, your proof is not correct.

On the other hand, if we suppose $x = a$ and $y = a^{3}$ and $z = 3n-4$ we can say $xy^nz$ is in $L$ for all $n\geq1$ ($p = 4$). Hence, we can't proof $L$ is not regular by pumping lemma.


Is every decidable language a deterministic context free language? I'm trying to get a better understanding for the relationship between decidability and a few other things so that I can get a better grasp of the topic. Any info helps!

Is every decidable language a deterministic context free language?
Are there any decidable languages that are not recognizable?
Is the question "Does a given PDA accept a given input?" decidable?
Under what operations are decidable languages not closed?

You are asking several disparate questions:

Is every decidable language a deterministic context-free language? No. There are even context-free languages which are not deterministic context-free. Furthermore, membership in a context-free language (deterministic or not) can be decided in polynomial time, whereas the time hierarchy theorem shows that there are languages decidable in time $O(n^{\log n})$ (say) but not in time $O(n^{\log\log n})$, and in particular not in polynomial time.
Are there any decidable languages that are not recognizable? A language is decidable iff both the language and its complement are recognizable.
Is the question "Does a given PDA accept a given input?" decidable? Yes, though the algorithm isn't obvious. One way is to convert the PDA to an equivalent context-free grammar in Chomsky normal form, and then use the CYK algorithm.
Under what operations are decidable languages not closed? Decidable languages are not closed under taking prefixes. The language of pairs $M,n$ such that $M$ halts within $n$ steps is decidable. But the language of all prefixes ending with $,$ is the halting problem, which is not decidable. (I'm skipping a few steps here.)


How do I solve these questions regarding homomorphism? Questions:

Give an example of a homomorphism, using the same alphabet, Σ, for both languages A and B.
Now, give a second example of a homomorphism but this time using two different alphabets, Σ and Γ, for languages A and B, respectively.

Questions to stack overflow:

How do I give the examples above? Do I make the state diagrams? Do I show it through the tuple-definition?
What are some examples of the questions above?

Notice the abuse of notation used. The quote overload symbol $f$ with three meanings which I will now denote differently with $f,f',f''$.
First is map from alphabet to words $$f: \Sigma \rightarrow \Gamma^*$$.
The second is the map between words $$f':\Sigma^* \rightarrow \Gamma^*$$.
The third is the map between languages $$f'':\mathbb{P}(\Sigma^*) \rightarrow \mathbb{P}(\Gamma^*)$$.

The The main point of the quote is that given $f$ there is the particular way to construct the corresponding $f'$ and $f''$. So, what one might call homomorphisms between languages $f''$ is specified by just giving map from alphabet to words $f$. And $f$ is usually easier to describe directly than $f''$.

Another important observation is that not all function of type $$\mathbb{P}(\Sigma^*) \rightarrow \mathbb{P}(\Gamma^*)$$ is a homomorphism of languages. (Because it doesn't "preserve structure" w.r.t. concatenation operation languages are equipped with.) However, the said construction is special in that given any $f$ with the correct type, $f''$ will be a valid homomorphism of languages.


prove that $h(x)$ is partial recursive If $f:A^*\rightarrow A*$ and $g:A^* \rightarrow A^*$ are partial recursive we want to prove $h:A^* \rightarrow A^*$ with the following definition is partial recursive
$$ h(x) =
  \begin{cases}
    \lambda       & f(x) = \lambda\\
    g(x)  & \textrm{otherwise}
  \end{cases} $$
for $x \in Dom(f)$.

One of my friends tried using a $\textrm{step}$ function that we know is primitive recursive and also partial recursive
$$ \textrm{step}(x,y) =
  \begin{cases}
    C_{\lambda}       & x = \lambda\\
    y  & \textrm{otherwise}
  \end{cases} $$
and defined $h(x) = \textrm{step}(f(x),g(x))$. but I think there is a problem here because we are not using the fact that $f$ and $g$ are partial recursive. Is this solution correct or not?

I think there is a problem here because we are not using the fact that $f$ and $g$ are partial recursive.

Yes, you are, or at least you should be. Consider $h'(x) = \textrm{step}(f(x), \Omega(x))$ where $\Omega$ is not partial recursive. Would you consider that to be partial recursive? If not, why not?

If you define $h(x)$ as your friend has, you need to prove firstly that it's equivalent to the original definition. Once you've done that, it suffices to prove that it's partial recursive. But composition of p.r. functions gives a p.r. function, which is the key step that either your friend forgot to state or that you have overlooked.


Find all intervals that are contained in a query interval Given a set of intervals $S = I_1, ..., I_n$, what is the fastest way to find all intervals of $S$ that are completely contained in an interval $I_\text{query}$? It should also support incremental (dynamic) insertion of new intervals to $S$.

Interval trees are not suitable for this, since they are designed to query overlapping intervals. Similarly, segment trees are designed to query all intervals that contain a query point.

A solution would be to use an interval tree to find overlapping intervals, then use linear search and eliminate those from the results that are outside of the specified query interval.

Is there any better/faster solution for this?

You were too quick to reject interval trees and segment trees.  You can search an segment tree for all intervals that are contained in a query interval $q=[\ell_q,u_q]$, using a straightforward recursive procedure:

Any node $v$ of a segment tree has a corresponding interval $\text{Int}(v)$.  Do a recursive search of the tree, except that you only visit nodes $v$ such that $\text{Int}(v)$ overlaps $q$.  Each such node stores a list of intervals from $S$.  For each such node, if $\text{Int}(v)$ is contained in $q$, check all of the intervals stored with $v$ is contained in $q$.

That's all you need to do.  Just because a data structure is designed to support one kind of operation doesn't mean it's unable to support other operations, too.

That said, one challenge with segment trees is that it's not clear how to update them dynamically (to add new intervals).

I think similar ideas can also be applied to interval trees, too.  The root of an interval tree has a value $x$.  Now do a case analysis:

If $x$ is to the left of $q$ (i.e., $x < \ell_q$), then you only need to look at intervals that are completely to the right of $x$, so you just recurse to the right child of the root.
If $x$ is to the right of $q$ (i.e., $x > u_q$), then you only need to look at intervals that are completely to the left of $x$, so you just recurse to the left child of the root.
If $x \in q$ (i.e., $\ell_q \le x \le u_q$), then you recurse to the left child and output all matches found there; recurse to the right child and output all matches found there; and finally, find all intervals that contain $x$ and are contained in $q$.  The latter can be done by scanning the list of intervals associated with the root (which is a list of intervals that contain $x$), to see which meet your condition.

I suspect there might be other approaches as well.  For instance, you could build a $k$-d tree, with $k=2$ dimensions, where the interval $[\ell,u]$ is represented as the point $(\ell,u)$.  Then given a query interval $q=[\ell_q,u_q]$, you want to do a range search to find all points $(x,y)$ such that $x \ge \ell_q$ and $y \le u_q$.  That should be a straightforward recursive search in a $k$-d tree.  Or, you could build a quadtree.


Is the given grammar LL(2)? http://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf

The book by Grune and Jacobs presents an example of a grammar that is $LL(K + 1)$ but not $LL(K)$

The example is $S -> a^kb/a^ka$

The grammar of this type is $LL(K + 1)$ but not $LL(K)$.

I have an example based on the grammar shown. Is this also $LL(2)$ ?

$S-> cca/ccb$

Based on the information above, I just want to confirm that is this grammar also $LL(2)$ but not $LL(1)$ ?

It is actually $LL(3)$. Try to prove it yourself.


Finding total valid strings of length N that could be formed using characters A,B and C which satisfies given criteria You have to find out the number of good strings of length N characters in size which you can make using characters A B and C.

A string is a good String if it satisfies the following three criteria:

The total number of C in the string should not be greater than equal to 4.
There should not be more than two consecutive A's in the string.
Any two B's should be at least two characters apart.

How do I find total possible good strings for N length string?

Any psudo code will really help. Thank you.

Let $0 \leq i \leq n, 0 \leq c \leq 3, 0 \leq a \leq 2, 0 \leq b \leq 2$, and $DP[i][c][a][b]$, denote the number of good strings of length $i$, but which also have more restrictions:

It should have $\le c$ number of C's
At most $a$ of its ending characters are A
None of the last $b$ characters are B.

The final answer that we are looking for is $DP[n][3][2][0]$. Note that having 2 in the third parameter  adds nothing extra over the restriction that the string already be a good string. Similarly, the fourth parameter being 0 also adds no further restrictions.

To compute $DP[i][c][a][b]$, we look at the possibilities of the last character:

If $c > 0$, then the last character can be C, and the term that would be added is $DP[i-1][c-1][2][\text{max}\{0, b-1\}]$.

If $a > 0$, then the last character can be A, and the term that would be added is $DP[i-1][c][a-1][\text{max}\{0, b-1\}]$.

If $b = 0$, then the last character can be B, and the term that would be added is $DP[i-1][c][2][2]$.

The base case would be $DP[0][c][a][b] = 1$.

This Dynamic Programming can thus be solved in $\mathcal{O}(n)$ time and space.


Given permutation $p$, compute $p^{-2}$ I'm now to problem solving, and I need some help and insight on the following problem from HackerRank:

Given a sequence $p(1),\ldots,p(n)$ of distinct numbers from $1$ to $n$, find numbers $y_1,\ldots,y_n$ such that $p(p(y_1))=1,\ldots,p(p(y_n))=n$.

My approach was to perform a double index lookup on each element in the provided input: for each $i \in \{1,\ldots,n\}$, I find an index $z_i$ such that $p(z_i) = i$, and then an index $y_i$ such that $p(y_i) = i$.
Is there a more efficient way to solve this problem?

The first step in answering your question is determining the complexity of your algorithm. Determining the index $z_i$ takes time $\Theta(z_i)$, and so determining all of $z_1,\ldots,z_n$ takes time $\Theta(1+\cdots+n) = \Theta(n^2)$. Determining the $y_i$ from the $z_i$ likewise takes $\Theta(n^2)$, which is the running time of your algorithm.
If we are willing to spend memory $O(n)$, then we can improve the running time to $O(n)$. The idea is to notice that $p$ is a permutation, and therefore has an inverse $p^{-1}$, which can be computed easily as follows: go over $i=1,\ldots,n$, and set $p^{-1}(p(i))=i$. Given that, we can simply compute $z_i = p^{-1}(p^{-1}(i))$.
If you are really short on memory, there are algorithms for inverting a permutation in nearly linear time and small space, see for example Matthew Robertson, Inverting permutations in place. After inverting $p$, you need to square the result $p^{-1}$, which might be achievable using similar techniques (or even easier).


Delaunay to Voronoi ... and back? Learning about Voronoi Diagrams, one quickly finds out that Delaunay Triangulations are clearly the easiest way to generate them from a set of points.

How about the other way around? Given a subdivision of (2D) space, how to determine unknown generators? Are there any common ways to do this?

Things I could think of were, assuming an underlying Delaunay triangulation, equal distances to Voronoi Vertices/"Delaunay Circumcenters", resulting in a system of quadratic equations.

Or searching for circles in the graph given by the Voronoi Vertices, and determining the center of the resulting polygons.

There is also a relationship to k-means clustering, as clusters defined by k-means, being the generators, yield a Voronoi Diagram in turn. This would leave me having to determine k and populate the regions with elements that are precisely not equidistant to two means.

I feel likely to be missing something very obvious and I would be happy for any direction in which to get started.

Unfortunately, you cannot generally reconstruct the generators from Voronoi polygons. Look at the four simple examples below: all have the same two Voronoi cells but different placement of the generators.


Chord algorithm - how to map nodes to keys? I'm trying to understand Chord algorithm (for Peer-to-Peer systems) but I can't understand how it maps the documents to the nodes.

I have one example where we have:

keys with 4 bits
5 active nodes with the following identifiers: 1, 5, 7, 10, 13

After mapping the documents to the nodes, we have:

Key 0 - Node 1

Key 2 - Node 5

Key 8 - Node 10

Key 11 - Node 13

Key 15 - Node 1

If somebody could help me with the steps that lead to this results I'd be truly grateful.

Chord implementations use a defined function which is used to map the key identifiers (0, 2, 8, 11, 15 in your case) to the node identifiers (1, 5, 7, 10, 13). In the example you provided, the function works like this:

NodeID = KeyID % N

where NodeID is the (identifier) node where the key will be inserted, KeyID is the identifier of the key to be inserted, and N is the total number of nodes.

After you calculate the NodeID, it might be the case that this NodeID does not exist. For example, when KeyID is 0, the NodeID will be 0. Since NodeID doesn't exist, it will be allocated to the next highest (existing) node identifier which is NodeID = 1.

The keys identifier can be calculated using some hash algorithm.