Is there any way that I, a CLI PHP developer, could "hook into" some kind of AI blackbox? For many years now, I have heard about "AI" and "neural networks" and all these buzzwords, and it is regularly claimed on Slashdot that this or that open source program is able to "do AI". But then I go to its website and I have no idea what I'm even looking at, let alone how to actually use it. I give up and forget about it... until the next time I hear something about "AI" and how it's now apparently seen as something as fundamental and crucial as a variable or function or constant.

Is this just utter fiction, made up nonsense, vaporware, or is it concretely possible to "hook into AI" like a "turn-key blackbox"?

I imagine that, from CLI PHP, I send a command such as:

ai_blackbox.exe --input="What are 1 + 1?"

And the ai-blackbox.exe then calculates my input, by spinning up a whole "neutral net" or whatever AI does internally, and quickly spits out:

2

Is that "a thing"? Is there something fundamentally wrong with my understanding of this?

Of course, in reality, I assume that the input is much more advanced than that. Something which would be unbearably slow to calculate in PHP but goes super fast with the ai-blackbox.exe?

Every single time I have asked anyone about this, I have never got a clear answer or reply. They either agree with me that it's just nonsense and doesn't actually exist, or they link me to some massive manual which I'm utterly unable to comprehend.

Can I actually use this, today, for anything meaningful, in a simple way?

Or is this exclusively useful for a handful of scientists doing some very specific work and who need to "train" the AI in all kinds of ways before it can answer anything?

something which would be unbearably slow to calculate in PHP but goes super fast with the ai-blackbox.exe

I think you are massively overestimating the state-of-the-art of AI.

Any AI blackbox is implemented in some programming language. PHP is not the fastest language, but its slowness is likely to be a constant factor in any computation. So the difference between you calculating it in PHP and the black-box calculating it is mostly whether you wrote the code yourself or someone else wrote it.

A general purpose question-and-answer system is actually likely to be slower than something you write yourself, because you probably have some idea of the kinds of questions you are going to be feeding the system, and could optimize based on this.

You seem to want to phrase your questions using natural language i.e. English or another human language. Natural Language Processing is a huge open area of research, and is far from solved. There are some existing techniques for this, but they are far from perfect. Anyone who has spent a day with a Siri, Google Home or Amazon Echo sees that we are a long way from being able to properly process human language.

What kinds of questions do you want to answer? Even assuming you could fully process the input to your question, you're going to have a hard time if the range of possible solutions includes "all of human knowledge." Representing such knowledge, collecting the information, and searching it, are all areas of current research.
Most modern AI techniques are for specialized AI i.e. you train a Neural Network to perform a single task very well. So they don't really apply to what you're talking about.

They either agree with me that it's just nonsense and doesn't actually exist, or they link me to some massive manual which I'm utterly unable to comprehend.

This is because AI is hard. Even with specialized AI, it takes a lot of expert knowledge to train a neural network. Generalized AI is even harder.

Can I actually use this, today, for anything meaningful, in a simple way?

I think the closest you will get to this is the Wolfram Alpha API. This is a system that lets you put in a question, and sometimes returns an answer. It's best with math-style things, or with facts it can guess from i.e. Wikipedia. It is far from perfect, and far from the kind of generalized AI you're talking about. It's also proprietary software i.e. you can only run it on their servers and make requests to them. And it is not free after a certain number of requests.
You can test it out at https://www.wolframalpha.com/.

Or is this exclusively useful for a handful of scientists doing some very specific work and who need to "train" the AI in all kinds of ways before it can answer anything?

There is a reason there is currently a huge demand for data science and AI specialists. Currently, it takes a lot of specific work to train an AI even to perform a single task. A Neural Network is basically a graph with weighted edges, and you can automatically optimize the edge weights, but you have to figure out the graph structure yourself. There is some work into "Automated Machine Learning", which tries to guess these structures automatically, but it's very much an open problem.
Essentially, it currently takes an expert to train an algorithm to perform a single task. General question and answering is mostly out of reach, even for experts.


How are these problem variants that ask about the size of optimal solutions in NP? I just started reading Vazirani's book "Approximation Algorithms". It is legally available online here.

On page 5 (23 in the pdf), it says that the following decision problems are in NP:

Is the size of the minimum vertex cover in $G$ at most $k$?
Is the size of the maximum matching in $G$ at least $l$?

I can't see why this is true. If, say, the first problem is in NP, then each valid instance (graph) has a Yes certificate which proves that the graph has a minimum vertex cover of size at most $k$.

But, how can one deduce from a certificate something regarding the size of the minimum vertex cover?

Any vertex cover of size $k$ is a witness that the smallest one has at most size $k$. Hence, the questions

  Is there a vertex cover of size at most $k$?

and

  Does a smallest vertex have size at most $k$?

are equivalent.


What is the formal statement of the dining philosopher's problem? I've read about it in a few places and I'm not sure I get it.
Are the philosopher's allowed to act simultaneously?
Do they each take 1 action simultaneously, then go on to their next action?

In most models of concurrency, each participant performs one elementary action at a time. This applies both to philosophers and to forks. So if two philosophers try to grab the same fork around the same time, one of them will make the attempt first.

Concurrency models usually do not have a global time, so there is no concept of actions happening “at the same time” if they don't involve the same object. Each participants sees events according to its own notion of time. If an action happens which doesn't involve a particular participant, that participant only learns about it later when it receives some message informing it that the action has taken place.

Think of the participants as nodes in a network (which they often are). If two actions happen on different nodes, it doesn't matter whether they're “exactly” simultaneous. And physically speaking, they wouldn't be exactly simultaneous: without perfectly synchronized clocks, there's always some slight measurement error or reaction delay that means that you can't distinguish perfectly simultaneous actions from actions that happened within an extremely small time frame.

Each philospher decides to pick up and set down forks at their own pace. One philosopher may pick up a fork, eat and set it down before his neighbor has lifted a finger. Or they may race for the same fork, but only one of them will manage to grab it. Meanwhile the other philosophers are doing whatever they please.

Having one timeline per participant, rather than a global timeline, both simplifies the model and makes it closer to the reality of most concurrent systems. The model is simpler because there's never any reason to treat actions as simultaneous, and never any reason to care about the exact order of actions happening in different places. It's closer to the reality of concurrent processes and distributed systems because each thread or each network node does have its own perception of when actions take place.

An exception is the modeling of circuits where all actions happen on a clock cycle. This is one of the fundamental ways in which parallelism differs from concurrency. In a circuit, it often does make a difference that two actions happen at different parts of the system on the same clock cycle (e.g. two inputs change simultaneously), rather than on distinct clock cycles.


DFA and equivalence relation I was studying Theory of Computation and I'm kind of lost in solving this problem.

Let $R$ be a relation defined on the set of states $Q$ of a DFA as $q_1Rq_2$ if $\delta(q_1,a)=\delta(q_2,a)$ for some $a\in\Sigma$.

Is $R$ an equivalence relation? Prove.

So to prove that $R$ is an equivalence relation, I have to show that

$R$ is reflexive
$R$ is symmetric
$R$ is transitive

But since it's related to DFA, I'm not sure how to approach this problem. Some help is much appreciated.

Let me spell what $R$ being an equivalence relation means:

Reflexivity: for all $q \in Q$ there exists $a \in \Sigma$ such that $\delta(q,a) = \delta(q,a)$.
Symmetry: for all $q_1,q_2 \in Q$, if there exists $a \in \Sigma$ such that $\delta(q_1,a) = \delta(q_2,a)$ then there exists $b \in \Sigma$ such that $\delta(q_2,b) = \delta(q_1,b)$.
Transitivity: for all $q_1,q_2,q_3 \in Q$, if there exist $a,b \in \Sigma$ such that $\delta(q_1,a) = \delta(q_2,a)$ and $\delta(q_2,b) = \delta(q_3,b)$ then there exists $c \in \Sigma$ such that $\delta(q_1,c) = \delta(q_3,c)$.

Now it's no longer about DFAs. It's about functions $\delta\colon Q\times\Sigma \to Q$.


How to solve recurrence of a binary tree I'm trying to solve this recurrence of a function of a binary tree with a recursive tree. But I can't find any pattern to solve it.
This function calculates both the height and if its a balanced tree.
template <typename T>
std::pair<bool, int> balanced_height(const BinTree<T> &tree) {
  if (tree.empty()) {
    return {true, 0};
  } else {
    auto [bal_left, height_left] = balanced_height(tree.left());
    auto [bal_right, height_right] = balanced_height(tree.right());
    bool balanced = bal_left && bal_right && abs(height_left - height_right) <= 1;
    int height = 1 + std::max(height_left, height_right);
    return {balanced, height};
  }
}

And the recurrence, $n$ is the number of tree nodes. I think that $n_l$ and $n_r$ should decrease in each call by 1.
$$
T(n) = \begin{cases}
   T(n_l)+T(n_r) + 1 & \text{if } n \gt 0,
   \\
   1 & n = 0 \\
\end{cases}
\\ \text{Given that }n_l+n_r+1=n
$$

There are several slightly different ways of defining binary trees. You seem to be using the following: a binary tree is either a leaf, or an ordered pair of binary trees.
Your recursive procedure actually computes two different functions: the first output is a Boolean function $b$ which measures whether the tree is balanced, and the second is an integer-valued function $h$ which computes the height of the tree.
The height function $h$ is defined as follows: if $T$ is a leaf then $h(T) = 0$, and if $T = (T_\ell,T_r)$ then $h(T) = 1 + \max(h(T_\ell),h(T_r))$. This function computes the height of the tree.
The balancedness function $b$ is defined as follows: if $T$ is a leaf then $b(T) = \mathsf{true}$, and if $T = (T_\ell,T_r)$ then $b(T) = b(T_\ell) \land b(T_r) \land |h(T_\ell) - h(T_r)| \leq 1$. In words, a tree is balanced if in every internal note $v$, the heights of the left and right subtrees differ by at most one.
As you can see, the argument of both functions is a tree.
Your recurrence describes the worst-case running time of the procedure as a function of the number of nodes. The base case is $T(1) = O(1)$ (when the tree is a leaf), and when $n > 1$,
$$ T(n) = \max_{\substack{n_\ell,n_r \geq 1 \\ n_\ell+n_r+1=n}} T(n_\ell) + T(n_r) + O(1). $$
The solution is $T(n) = \Theta(n)$. You can prove this by induction. In particular, if you replace $O(1)$ by $1$, a simple induction shows that $T(n) = n$.
In fact, it is not hard to check that your procedure has running time $\Theta(n)$ on any tree having $n$ nodes, since the recursive calls "visit" every node in the tree, and do $O(1)$ processing per node.


Minimal number of nodes needed to connect a disconnected graph Given a graph $G = (V, E)$ with $V = U \uplus T$ (let's say the vertices are
labelled $U$ or $T$), I am looking for the smallest set $U' \subseteq U$ such
that $G[U' \cup T]$ is connected.

If we eleminate all the type-U nodes from the graph, the type-T nodes (terminals) might form several disconnected subgraphs.
That is, the graph $G[T]$ on only the "terminal nodes" might be disconnected,
and I want to pick as few vertices from $U$ as possible to make the graph
connected again.

What kind of graph problem does this relate to?

I think you are looking for the vertex version of the Steiner tree where

$A$ is the set of terminal nodes and
$B$ is the set of vertices you want to use to create a tree.

In the Vertex-Weighted Steiner Tree problem you are given a graph $G = (V,E)$ and a set of terminal nodes $T \subseteq V$ and are asked for a minimum set $U$ such that $T \subseteq U$ and $G[U]$ is connected.

This problem has been studied as the node‐weighted Steiner tree problem by

Segev, 1987, The node‐weighted steiner tree problem, Networks.
Yeh and Chang, 1998, Weighted connected domination and Steiner trees in distance-hereditary graphs, Discrete Applied Mathematics.

and is indeed NP-complete.

On the positive side, it might be solvable in time $3^k \text{poly}(n)$ where $k$ is the number of connected components in $G[T]$.  The simplest preprocessing step is to contract all the edges in $G[T]$ first, that is, replace all the connected components with a single node, and remove parallel edges.  (That is, it is fixed-parameter tractable (FPT) in the number of connected components in $G[T]$).


Does an array count as a primitive operation when it is used as an argument in a function call? Say I have
return A[n-1] + Sum(A, n - 2).
I counted the following primitive operations:

return A[n-2] + Sum(A, n - 2)
   1    2 3   4  5  6   7

I know accessing a certain index in A counts as 1 primitive operation, but I am not sure about A in the function call. Did I count the right number of operations?

As pointed out by Raphael, it depends on the machine model. Under the assumptions of the RAM model of computation ...

  Simple operations (+, -, call, return, etc.) take one time step.
  Loops and subroutines are not simple operations: they may involve many of them.
  Memory accesses (e.g., indexing into an array) take one time step.

... you counted correctly operations [1-4] and 7. As for operation 5, it depends: the subroutine call does count as one single-step operation (according to assumption 1), but the subroutine itself doesn't: it is a composite operation (according to assumption 2). Finally, I would not consider passing A as a parameter to be an operation: A affects running time when it is accessed within the Sum subroutine, not in the subroutine call.


Can a machine choose whether or not to accept a state in a FSM We were given a question in class with this FSM and had a debate over what the regex would be and the corresponding accepted strings. Does this FSM make sense as on state 1 there seems to be a choice between going to state 3 or looping on state 1 with the input of b.

![enter image description here][2]

Please forgive the bad drawing as we were given the question on paper.

The diagram appears to be of a Nondeterministic finite automaton, or NFA. A NFA is a model of a theoretical machine that accepts a given string if any path through the NFA for that string can end up at an accepting node.

So the simple answer to the question in the title is "yes, if you're talking about NFAs". (As opposed to Deterministic finite automata, or DFAs, which must have a unique outgoing edge for each character at a given node)

One traditional way to write a program to check if a string is accepted by an NFA is to keep track of all the states that the machine could be in after seeing a particular character, and then at the end declare that the string is accepted if one of the states we could be in now is an accepting state.

For example, consider the input string abbbbb.

At the start, the machine can only be in state $S_0$, so the set of states it can be in is $\{S_0\}$.

After a, the machine can now only be in $S_1$, so $\{S_1\}$.

After ab, the machine could be in $S_1$ or it could be in $S_3$, so $\{S_1, S_3\}$.

After abb, the machine's set of possible states is $\{S_1, S_2, S_3\}$.

After abbb, the machine's set of possible states is $\{S_1, S_2, S_3\}$.

After abbbb, the machine's set of possible states is $\{S_1, S_2, S_3\}$. You should see a pattern by now.

And in fact, at the end of the whole input string abbbbb, the machine's set of possible states is $\{S_1, S_2, S_3\}$, and that contains an accepting state ($S_3$), so the string is accepted.

The regular expression should now be easily readable from the machine: ab*(a|b)


Big-Oh and Growth Rate So, in the book I'm studying from it says :

  The statement “f(n) is O(g(n))” means that the growth rate of f(n) is no more than the growth rate of g(n).

What I understood from this statement is that since 9n is O(n), the growth rate of the functions 9n and n have the same growth rate, which does not make sense. I know that growth rate is the increase of a certain quantity over time. So, obviously the function 9n will grow way faster towards infinity, than the function n.

Did I understand the sentence given in the book incorrectly or is the statement incorrect?

You understood it correctly, but have interpreted it differently than the book wanted it to be interpreted. You are right that $9n$ grows faster than $n$ so the main problem in your book may be trying to express a mathematical definition of $O$ with too few words.

The definition
The function $f(n)$ is in $O(g(n))$ if there exist $n_0 \in \mathbb{N}$ and a positive real number $c$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$.

Now it is clearer how $9n$ is in $O(n)$. Because there exist, say $c=10$ and $n_0=0$ such that $9n \leq c \cdot n$ for all $n \geq n_0$.

Why compare so loosely?
The problem is, if we would compare growth rates by exact function values, then two very similar functions may not end up in the same class. For example, with your "strict-O notation"; for any function $d > 0$, $f+d$ would not be in the same class as $f$, and that is not very useful. So, we have to draw the line somewhere (pun intended). Also, we use asymptotic analysis for describing algorithm complexity dependant on the input size $n$, and it is often not possible to calculate computation steps that precise.

Other notations
But, there are other asymptotic notations except big-O so you might want to look at those. You will find that $\Theta$ is, for example, more restrictive than $O$.


Pseudo-polynomial time algorithm for NP-Complete Problems For problems like Knapsack there is a pseudo-polynomial time algorithm and it is NP-complete. So we reduce every other problem in NP in polytime to Knapsack.

But why don't we have then a pseudo-polynomial time algorithm for all problems in NP?

An algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric values in the input. It doesn't make sense to talk about pseudo-polynomial time algorithms for all problems in $NP$ since many of them do not have numeric values in their input at all.

However, if you are looking at two problems for which the definition does apply (for instance 2-Partition (weakly $NP$-complete, has a pseudopolynomial time algorithm) and 3-Partition (strongly $NP$-complete, not believed to have a pseudopolynomial time algorithm) then how is it possible a polynomial reduction from 3-Partition to 2-Partition does not result in a pseudopolynomial algorithm for 3-Partition?

The answer is that a polynomial reduction may create very large numeric values. Every known reduction from 3-Partition to 2-Partition creates numbers that are exponentially bigger than the orignal numbers. Exponentially larger numbers only take polynomially more space to represent, so a polynomial reduction can very easily create exponential numeric values.

So even though we have a pseudopolynomial time algorithm (that runs in polynomial time in the numeric values of the input) for 2-Partition it does not work as a pseudopolynomial time algorithm for 3-Partition, because the reduction makes the numbers much larger, so the algorithm is no longer pseudopolynomial in the original numbers.


What is the algorithm for a decider to get the language accepted by a DFA? I am trying to understand the larger problem of the decidability of the equality of two DFAs. I understand that this problem can be solved using minimizing DFAs, but my textbook states this can be done using symmetric difference.

Theorem: Let $EQ$ be a language, where $EQ$ = $\{<A,B> \mid \text{A and B are both DFAs and L(A) = L(B)}\}$.
In my notation, $L(X)$ stands for the language that DFA $X$ recognizes.

Prove that $EQ$ is decidable. This relies on the symmetric difference of 2 sets.

Proof: Let $Q$ be a decider defined as:

On input $<A,B>$ do:

Construct a DFA $C$ such that $L(C) = (L(A) \cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B)) $
Run $<C>$ on the algorithm used to determine if the language recognized by a DFA is $\emptyset$  (We proved this is decidable before, and I have no issues with that).
If that algorithm accepts, then $Q$ accepts
If that algorithm rejects, then $Q$ rejects

For $Q$ to be a decider, we must prove that $Q$ will halt. Since we have proven that the algorithm used in step 2 is decidable, it will halt. So I have no problems with steps 2-4.

But the first step, how can I prove that constructing $C$ in that way will halt? I understand that the symmetric difference will result in a regular language because of the closure properties, but how can a decider actually carry out this process and be guaranteed to halt?

So this is my primary question, what is the algorithm for determining the language that a DFA accepts? I.e. given DFA $X$, how can I determine $L(X)$ (Again, this must halt, so we can't try every string in existence or something like that).

Some follow up questions are: What if the DFA in question accepts an infinite set of strings, how can we possibly represent that on the decider's tape (or if the complement of $L(A)$ is infinite, etc.)? How can a decider determine the compliment of a set? And if $L(C)$ ends up being an infinite set of strings, how can we process that so that we can construct DFA $C$?

My book simply states

  These constructions are algorithms that can be carried out by Turing
  machines.

which drives me nuts! Prove it.

Suppose that $A,B$ are two DFAs on a common alphabet $\Sigma$ with states $Q_A,Q_B$, initial states $q_{0A},q_{0B}$, final states $F_A,F_B$, and transition functions $\delta_A,\delta_B$. We define a product DFA as follows:

$Q = Q_A \times Q_B$.
$q_0 = \langle q_{0A}, q_{0B} \rangle$.
$F$ consists of all pairs $(q_A,q_B)$ such that either $q_A \in F_A$ and $q_B \notin F_B$ or $q_A \notin F_A$ and $q_B \in F_B$.
$\delta(\langle q_A,q_B \rangle, \sigma) = \langle \delta_A(q_A, \sigma), \delta_B(q_B, \sigma) \rangle$.

You can prove by induction that $\delta(q_0, w) = \langle \delta_A(q_{0A}, w), \delta_B(q_{0B}, w) \rangle$, and so our definition of $F$ guarantees that the language of this DFA is the symmetric difference of $L(A)$ and $L(B)$.

In order to know whether $L(A) = L(B)$, we have to check whether their symmetric difference is empty. This happens exactly when no accepting state is reachable from the initial state in the product DFA, a condition which we can check using BFS/DFS.


Asymptotic Improvements in Hardware? One of the main benefits of algorithm analysis, is that it offers asymptotic improvements to complexity as opposed to hardware, which offers only constant improvements. E.g switching to a super computer from a workstation might give a $\times 1,000,000$ increase in speed, but if that supercomputer is running a linear search on a sorted array, it will eventually be trumped by a desktop running a binary search for large enough problem sizes.

My question is this:

  Are there any improvements in hardware(theoretical or practical) that could offer an asymptotic speedup over pre-existing hardware?

In this case pre-existing refers to at least 3rd generation computing technology. I'm not really interested in speedups over vacuum tubes.

Quantum computers, if they ever get built, will be asymptotically faster than existing computers in certain tasks. Limited quantum computers might already exist, though this is a contentious issue.


Is there a free online computer calculator that is more powerful than wolframalpha.com? I need a calculator that accepts inputs using product notation, can compute the following, and can return the result in scientific notation:

$$\dfrac{\prod_{i=1}^{3.1536\times10^{16}}(52!-i)}{52!^{3.1536\times10^{16}}}$$

I have tried wolframalpha.com, desmos.com, and Excel. None of them can do the calculation. Is there another calculator that would work?

There are absolutely huge numbers involved in this calculation, no wonder you won't get the result by simple numerical computation.

However,

Let $x = 52!$ and $y=3.1536\times 10^{16}$.

A crude lower bound yields:
$$ \frac{\prod_{i=1}^y(x-i)}{x^y} \geq (1 - \frac{y}{x})^y \geq 1-\frac{y^2}{x} .$$
Putting numerical values and wandering on the safe side of approximations you get:
$$1-\frac{y^2}{X} \geq 1-10^{-34}$$.

Thus,

$$ 1-10^{-34} \leq \frac{\prod_{i=1}^y(x-i)}{x^y} \leq 1 $$.

The value you are looking for is basically $1$.


Context-free Grammar Exercise Could someone explain me how to form a context-free grammar with all rules R by this example language, please?
\begin{equation}
L:=\left\{w c v c \overleftarrow{w} | w, v \in\{a, b\}^{+}\right\}
\end{equation}
The arrow over w means, that the word w is written backwards.

I already know that \begin{equation}
\Sigma=\{a, b, c\}
\end{equation}
and V (non terminal symbols) maybe have to be \begin{equation}
V=\{S, A, B, C\}
\end{equation}

Thank you for helping.

I think you can solve this using this construct:

$$S \rightarrow ASA|BSB|ATA|BTB $$
$$T \rightarrow CAZC|CBZC$$
$$Z \rightarrow AZ|BZ|\epsilon$$
$$A \rightarrow a , B \rightarrow b, C \rightarrow c$$

First rule provides the $w$ and $w^R$ in the language, second rule makes sure $v \ge 1$ and has 1 c in both sides and third is just constructing the $v$ further. My assumption was your arrow on top of last $w$ was just meant it is reversed.


Why is the orthogonal line segment intersection algorithm $O(n\log n+R)$ instead of $O(n\log n + Rn)$? In the same lecture notes without providing many details it says that the complexity of the algorithm which uses a balanced search tree is $O(n\log n+R)$ where $R$ is the total amount of intersections.

However I don't understand why this is the case.

Suppose that the sweep line is travelling from top to bottom. Whenever we encounter a vertical line segment, we pick its $x$ coordinate and add it to a search tree. Assuming that we are using a balanced search tree like AVL, this operation will take $O(\log n)$ time. Now when we reach an end point of a vertical line segment, we remove its $x$ coordinate from the search tree, which is going to take $O(\log n)$ time as well.

Whenever we encounter a horizontal line segment defined by points $A$ and $B$, we have to do a range search on our search tree and use the range defined by these two points, that is $(A.x, B.x)$

Now how is this range search going to happen? We use $A.x$ and travel to the left most point in the search tree, and do the same for $B.x$, we can do this in $O(2\log n)$.

All the points in our tree between these two end points are going to be the intersecting the horizontal segment, which is going to be let's say $R$ in total, so $O(2\log n+R)$ in total.

We do this $n$ times (the amount of horizontal segments) so we get a complexity of $O(2n\log n+nR)$.

It's a bit hard to get through your text since a lot of information is missing. However I assume that you have the following misunderstanding.

Let me ignore the constants in the big-O for this argument since this is irrelevant. For every horizontal segment $h$ you perform an action that takes $O\log n + R_h$ time, where $R_h$ are the intersections you output. Then the overall running time is
$$\sum_h \log n + R_h =  n\log n +R.$$

Simply speaking, you only output every crossing once. So the overall time for the output is $O(R)$.


Two Generals Problems - What's wrong with my approach? Some time ago, I've come across the Two Generals Problem and that it cannot be resolved. Now, recently, I've had an idea how to approach it. IMHO, it is a very obvious way to handle it but I haven't found this way to handle it anywhere and therefore assume my idea is flawed but I can't find the error.
The approach I've found online (from Wikipedia):

A pragmatic approach to dealing with the Two Generals' Problem is to use schemes that accept the uncertainty of the communications channel and not attempt to eliminate it, but rather mitigate it to an acceptable degree. For example, the first general could send 100 messengers, anticipating that the probability of all being captured is low. With this approach the first general will attack no matter what, and the second general will attack if any message is received.

This seems very crude and the chance of a non-delivery stays at $(1-p)^c$.
My Approach

General A sends a message to General B when to attack. The message contains the following information:

Attack at time $T$.
Send confirmation of receival.
I will not confirm your confirmation.
I will resend the time of attack after time $t$ if I did not get a confirmation.

That way, General A can be sure General B got the message when he gets the confirmation. General B can be $(1 - p)^{m \cdot c}$ sure that it passed after not getting the time of attack again, where

$p$ := probability the confirmation passed
$m$ := multiple of time $t$ that has passed.
$c$ := count of messages sent per time unit (one of the solutions I've come across is to send a lot of messages at the same time).

It does not solve the problem that General B can't be 100% sure that General A received the confirmation but after some time, he can be very certain.
Special Case
Now, if we were to change the scenario slightly, we can reach a 100% certainty for both:

Assume both Generals do not only communicate in order to synchronize the attack but also for other purposes. In that case, General A can send the message:

Attack at time $T$.
Send confirmation of receival.
I will not confirm your confirmation.
I will resend the time of attack after time $t$ if I did not get a confirmation.
I will not send any other communication until I've received your confirmation.

That way, General A can be sure that General B received the plan, when he gets the confirmation and General B can be sure General A received the confirmation when General A sending messages about something else.

So, what is wrong with my approach?

New answer
After thinking some more and searching around for a bit I beleive both of your approaches are already implemented in TCP, as can be seen here:

[...] Acknowledgements (ACKs) are sent with a sequence number by the receiver of data to tell the sender that data has been received to the specified byte. [...]
Reliability is achieved by the sender detecting lost data and retransmitting it. TCP uses two primary techniques to identify loss. Retransmission timeout (abbreviated as RTO) and duplicate cumulative acknowledgements (DupAcks).
Timeout-based retransmission
Whenever a packet is sent, the sender sets a timer that is a conservative estimate of when that packet will be acked. If the sender does not receive an ACK by then, it transmits that packet again. [...]
Dupack-based retransmission
If a single packet (say packet 100) in a stream is lost, then [...] the receiver acknowledges packet 99 again on the receipt of another data packet. [...] if the sender receives three duplicate acknowledgements, it retransmits the last unacknowledged packet. [...]

Retransmission timeout
Retransmission timeout is similar to your first approach: if general A did not receive the confirmation, he will send the same message again.
Duplicate cumulative acknowledgements
First we need to understand the steps taken in each algorithm.
TCP

The sender did not receive an acknowledgement so it sends the same message again.
The receiver notices that the same message is being sent again so it sends the same acknowledgement it sent previously for this message.
Only when the sender receives this acknowledgement it will send the next message. Only when the sender sends a new message will the receiver know that the confirmation has been received.

Your special case

General A did not receive an acknwoledgement so he sends the same message again.
General B notices that the same message is being sent again so he sends the same confirmation he sent previously for this message.
Only when general A receives this acknowledgement he will send the next message. Only when general A sends a new message will general B know that the confirmation has been received.

We can see that both algorithms are the same, except for their terminology. So there isn't any problem with your approaches.

Old, wrong answer
The problem with your Special Case approach is that B cannot do anything until new communication is sent. Because this can happen after the attack time has passed, this is not a functional approach.
Translated to real life networking, this means that the message has to sit in the buffer until the next message is received. This is not a usable strategy in most applications.


Maximal derangements When one shuffles playing cards, the goal is evidently to achieve a possibly big derangement
of a given deck. For manual shuffling there are terms like inshuffle, outshuffle etc. I like
to know whether there is a sensible general measure of derangements of n objects and
efficient algorithm to compute that measure and eventually also to determine the set representing maximal derangements.

I second Raphael's remark that when shuffling cards, you don't want the deck to be "unsorted", but rather random. However, when analyzing any specific shuffle, there can be measures of randomness that can be used to prove that a small number of shuffles isn't enough to make the deck random enough.

As a simple example, consider the "top card shuffle", in which you repeatedly take the top card and place it at an arbitrary location. If you don't repeat this enough times, then the top $k$ cards will retain their relative order (since you never put the top card somewhere among the top $k$ cards). So a reasonable measure of "sortedness" would be the maximal $k$ such that the top $k$ cards retain their relative order - for a shuffled deck, we expect this to be very small.

There is a similar measure for riffle shuffle, namely the number of ascents, two adjacent cards which retain their relative order. A random permutation has $n/2$ ascents, while an (under-)riffle-shuffled deck will have too many.

All this and more is described in David Aldous and Persi Diaconis, Shuffling cards and stopping times.


Computing average access time A computer has a cache memory and a main memory with the following features:

-   Memory cache access time: 4 ns
-   Main memory access time: 80 ns
-   The time needed to load a line in cache is 120 ns.
-   Write-through policy.
If the hit ratio in this computer is 95 % and the 90% of the memory accesses are read operations, what is the average access time?

It seems a bit weird to me since I have read through this site calculate the effective (average) access time (E AT) of this system but I still do not know how to do it.
I would appreciate any help. Thanks!

This is just a single-level cache, then? That means just two possibilities when accessing: a hit or a miss, with hit rate + miss rate = 100%. It follows that the average is simply the time spent with hits and the time spent with misses, which comes out to:

hit rate * hit time + miss rate * miss time


Is $Ω(n\log n)$ the lower-bound for *all* sorting algorithms or *just comparison-based* sorting algorithms? Is $Ω(n\log n)$ the lower-bound for all sorting algorithms or just comparison-based sorting algorithms?

If the latter, is it possible for there to be general-purpose sorting algorithms which perform better than $Ω(n\log n)$?

General-purpose, for example, means you aren't assuming elements have a fixed number of bits.

The input to the algorithm is a sequence of $n$ bits.  The bits are an encoding of integers.

O($n$ $log$ $n$) lower bound complexity assumes the length of each key bit is constant.  If not, then in the worst case you must compare nearly all bits, and multiply the complexity by that length and get O($kn$ $log$ $n$)

In contrast, some non comparison sorts with arbitrary key lengths can be done in worst case O($kn$).

EDIT: To add more detail:

For Counting Sort, the worst case and average case are O($n+r$) where $r$ is the range of keys (max - min).

For LSD Radix sort the worst case and average case are O($n+k/d$) where $k$ is the key length and $d$ is the digit size.

You mention that there is no limit on key bit length.  It would seem that LDS Radix has better worst case performance:  $O(k(n+ln\ n))$ > $O(n+k/d$), putting aside other factors such as space.


Confusion about the definition of de Bruijn terms in the TAPL book I'm working through Types and Programming Languages right now, and I'm a little confused about the recursive definition given for nameless/de Bruijn terms  (chapter 6, definition 6.1.2). Below is the definition given:

  Let $\mathcal{T}$ be the smallest family of sets $\{\mathcal{T}_0,
\mathcal{T}_1, \mathcal{T}_2, \ldots \}$ such that

  $k \in \mathcal{T}_n$ whenever $0 \leq k < n$;
  if $t_1 \in \mathcal{T}_n$ and $n > 0$, then $\lambda.t_1 \in \mathcal{T}_{n-1}$;
  if $t_i \in \mathcal{T}_n$ and $t_2 \in \mathcal{T}_n$, then $(t_1 t_2) \in \mathcal{T}_n$.

It further clarifies that the elements of $\mathcal{T}_n$ are terms with at most $n$ free variables, numbered between $0$ and $n-1$.

I think I understand the first two points, but the third is confusing me. Here's my understanding of what the points mean:

The numbers $0, 1, \ldots, n-1$ are all terms in $\mathcal{T}_n$ (representing $n$ unbound variables).
$t_1$ has at most $n$ free variables, and $\lambda. t_1$ binds a single variable ($0$), so it has at most $n-1$ free variables.

Assuming these are correct, my current feeling about point 3 is that $(t_1 t_2)$ should actually be in $\mathcal{T}_{2n}$, because the resultant term will have up to $2n$ free variables ($n$ each). I don't follow how $(t_1 t_2) \in \mathcal{T}_n$.

Could somebody help correct my understanding?

The $n$ isn't indexing how many references to variables there are, it's indexing how many free variables are able to be referred to.

You can think of $0,1,\dots,n-1$ as being variables $v_0,v_1,\dots,v_{n-1}$. A term in $\mathcal T_n$ is a term that is allowed to refer to variables $v_0$ through $v_{n-1}$. If you have two terms of $\mathcal T_n$, then each is allowed to use variables $v_0$ to $v_{n-1}$. If you combine them into a new compound term, i.e. $(t_1, t_2)$, then that compound term still only refers to/uses the free variables $v_0$ through $v_{n-1}$. A use of a free variable $v_{n+4}$ hasn't suddenly appeared.

In the $\lambda.t_1\in\mathcal T_{n-1}$ case, while $t_1$ can contain an instance of $n-1$, i.e. an occurrence of $v_{n-1}$, such an occurence doesn't refer to a free variable. It refers to the variable bound by the $\lambda$. (Or $v_0$ doesn't depending on the convention: de Bruijn levels vs de Bruijn indices.) You could describe this as $\mathcal T_n$ only allows occurrences of $v_m$ if $v_m$ is under at least $m-n+1$ lambdas. From this perspective, $(t_1,t_2)\in\mathcal T_n$ when $t_1,t_2\in\mathcal T_n$, is just saying that if all occurrences of $v_m$ in $t_1$ and $t_2$ occur under at least $m-n+1$ lambdas, then they still occur under at least $m-n+1$ lambdas in $(t_1,t_2)$ since we haven't added or removed any lambdas.


How are statistics being applied in computer science to evaluate accuracy in research claims? I have noticed in my short academic life that many published papers in our area sometimes do not have much rigor regarding statistics. This is not just an assumption; I have heard professors say the same.

For example, in CS disciplines I see papers being published claiming that methodology X has been observed to be effective and this is proved by ANOVA and ANCOVA, however I see no references for other researchers evaluating that the necessary constraints have been observed. It somewhat feels like as soon as some 'complex function and name' appears, then that shows the researcher is using some highly credible method and approach that 'he must know what is he doing and it is fine if he does not describe the constraints', say, for that given distribution or approach, so that the community can evaluate it.

Sometimes, there are excuses for justifying the hypothesis with such a small sample size.

My question here is thusly posed as a student of CS disciplines as an aspirant to learn more about statistics: How do computer scientists approaches statistics?

This question might seems like I am asking what I have already explained, but that is my opinion. I might be wrong, or I might be focusing on a group of practitioners whereas other groups of CS researchers might be doing something else that follows better practices with respect to statistics rigor.

So specifically, what I want is "Our area is or is not into statistics because of the given facts (papers example, books, or another discussion article about this are fine)". @Patrick answer is closer to this.

As a graduate student in computer science, who has exposure to research in fields other than computer science, and whose research group works in an area of computer science where statistics can be fruitfully applied, I can offer my experience; your mileage may vary.

In general, even the most well-meaning scientific research can fail to rigorously apply statistical analysis to results, and it is my experience that this does not always preclude papers including such poorly-analyzed results from being accepted for publication. The area in which my group operates is mainly in distributed computing and high-performance computer architecture. Often, research involves experimental designs the performance of which cannot easily be understood analytically in the required detail. As such, empirical results are often used as evidence for claims.

Clearly, experiments should be design - and results analyzed - in such a way as to provide some confidence that the results are statistically significant. Most of the time, this is not done, even in some of the most important venues. When statistical analysis is applied, it is almost never rigorous in any meaningful sense; the most one typically sees (and one is glad to see it!) is that an experiment was repeated n times, for some arbitrarily-chosen n, where typically $1 < n < 5$. The selection of error bars (if any are indicated) seems to be mainly a matter of personal preference or taste.

In summary, no, it's not just you; and it's not just software engineering. In general, based on my experience, several areas of computing research seem to err on the side of not doing enough. Indeed, it might be even be detrimental to the viability of a submitted paper to dwell on statistical considerations. That's not to say that I find the situation satisfactory; far from it. But these are my impressions. For instance, you may take a look at section 5 of this paper, which was presented at Supercomputing 2011, one of the most high-profile conferences in the area of high-performance computing. Specifically, take a look at some of the discussion of results in section 5, and see whether you arrive at the same conclusions that I do about the rigor of statistical analysis of experimental results.

More generally, this shortcoming may be symptomatic of a condition in some areas of computing to publish more papers rather than fewer, to target conferences rather than journals, and to emphasize incremental progress rather than significant and fundamental improvements in understanding. You might consult this article, which provides valuable insight along these lines.


Line separates two sets of points If there is a way to identify if two sets of points can be separated by a line?

  We have two sets of points $A$ and $B$ if there is a line that separates $A$ and $B$ such that all points of $A$ and only $A$ on the one side of the line, and all points of $B$ and only $B$ on the other side.

The most naive algorithm I came up with is building convex polygon for $A$ and $B$ and test them for intersection. It looks time the time complexity for this should be $O(n\log h)$ as for constructing a convex polygon. Actually I am not expecting any improvements in time complexity, I am not sure it can be improved at all. But al least there should be a more beautiful way to determine if there is such a line.

Both uli and Dave Clarke correctly observe that this is a linear programming problem, even in higher dimensions (Can these two point sets be separated by a hyperplane?) and so it can be solved in polynomial time.  But because your points lie in the plane, your problem can actually be solved in $O(n)$ time, where $n$ is the total number of points.

The simplest solution is probably Seidel's randomized algorithm.  Choose an input point $p$ uniformly at random, and recursively compute a separating line $\ell$ for all the points except $p$.

If no such line exists, then the original points are not separable.
If $p$ is on the correct side of $\ell$, then $\ell$ separates the original points.
If $p$ is on the wrong side of $\ell$, then either the original points can be separated by a line through $p$, or the original points are not separable at all.  This condition is easy to check in $O(n)$ time [exercise].

This algorithm runs in $O(n)$ time with high probability (with respect to the algorithm's random choices).  For more details, see the original paper or any number of online lecture notes.


Is the calculation of infinite sums solvable by a computer? The question is: I give the computer a sum, such as $\sum_{n=1}^\infty\frac{1}{n^3}$, the computer is expected to return an elegant closed-form solution, because the answer may be irrational. Has this problem been solved using a computer? Or, has it been proved to be undecidable? Or is it open?

It's complicated. Some very broad classes have been solved completely, but that's still one way of saying that it's only been done for special cases. The book A=B by Wilf, Zeilberger and Petrovšek would probably interest you: it describes algorithms for some of these broad classes.


Proving 2P2N SAT is NP-Complete I hope I named this CNF Boolean sentence the correct way. The way I see it, a 2P2N is where each literal appears twice (or at most twice, but we can say twice without loss of generality).

I am trying to prove it is Satisfiable. How do I do this? Do I need to try to reduce it to 3-SAT (might need some help doing that as well). Or is there another method of proving satisfiability?

So here is my take on this. You reduce 3SAT (or SAT, the 3-literal limit does not make anything easier here) to 2P2N in the following way:

As noted above, you cannot easily add variables with an enforced equivalent truth mapping as existing ones (specifying $x \Leftrightarrow y$ in CNF requires 1 positive any 1 negative literal of each $x$ and $y$, so you cannot extend this to an arbitrary number of "copies"). At least not directly: $(x \Leftrightarrow y) \wedge (y \Leftrightarrow z) \wedge (z \Leftrightarrow w)$ will leave you with no free literals for $y$ and $z$. However, an equivalent to the above is
$(x \Rightarrow y) \wedge (y \Rightarrow z) \wedge (z \Rightarrow w) \wedge (w \Rightarrow x)$ (note that $x \Rightarrow y \equiv \overline{x} \vee y$). Hence, this "chain" requires you to use up your two positive, two negative literals for your existing variable $x$, but leaves you with one free negative respectively positive literals for each of $y$, $z$ and $w$. These you can use to replace any occurences of $x$ or $\overline{x}$.


How to check if a given point is inside a polygon with holes? How to check if a given point lies inside or outside a polygon with holes?

Does the below algorithm works for polygon with holes?

https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/

Yes, basically.

That algorithm is called ray casting algorithm, also known as the crossing number algorithm or the even–odd rule algorithm.

Why is it correct? "The algorithm is based on a simple observation that if a point moves along a ray from infinity to the probe point and if it crosses the boundary of a polygon, possibly several times, then it alternately goes from the outside to inside, then from the inside to the outside, etc. As a result, after every two 'border crossings' the moving point goes outside. This observation may be mathematically proved using the Jordan curve theorem." Note this reasoning works in all basic situations, whether the polygon is convex or not and whether the polygon has holes or not.

However, you should be aware of the degenerate cases as well as the case of a hole inside a hole. For an example of degenerate case, consider a degenerated polygon that are two triangles intersecting only on their only common vertex. Then the algorithm may fail when the ray goes through that common vertex. For the case of a hole inside a hole, you have to define the area inside the smaller area is inside the polygon so as to not invalidate the algorithm.

It is actually not easy to make a rigorous statement mathematically about the general situations when the ray casting algorithm works. For this particular question, let me just say the ray casting algorithm will work for a polygon with separate polygon holes inside it where all line segments of the outer polygon and inner polygons do not intersect each other.


Formal language without grammar Definitions:

Alphabet $Σ$: finite, non-empty set
Language: subset of $Σ^*$
Grammar: Unrestricted grammar (Chomsky Type 0)
Language of a grammar: all words that can be produced by applying $P$ multiple times, starting from $S$

Grammars are finite, therefore there are only countable infinite of them. But there are uncountably infinite many languages. Each grammar can only describe one language. Therefore, there are languages without grammars.

Can you give an example for such a language without grammar?

I searched the internet, but strangely, I could not even find the question in context of formal language.

I assume that by "grammar" you mean type-0 grammars. One can probably extend those to capture more languages.

Type-0 grammars are equivalent to Turing machines in expressive power. So, in order to show that a given language does not have a grammar, we can proceed as follows with suitable $L$:

  Assume there was a grammar for $L$. Then, we could semi-decide the word problem of $L$. That contradicts the known fact that $L$ is not recursively-enumerable.

Note the semi here; assuming a grammar does not give us decidability, so the halting problem is not a suitable candidate -- we need a problem/language that is not even semi-decidable/recursively enumerable. From your computability background you should know that the complement of the (special) halting language, namely

$\qquad \overline{H} = \{ \langle M \rangle \mid M \text{ loops on } \langle M \rangle \}$,

is not semi-decidable. Thus, by the reduction outlined above, there is no (Chomsky) grammar for $\overline{H}$.


Corresponding noun for "side-effect-free"? For functions or computations we have terms like:

Deterministic – Determinism
Pure – Purity

Now what is the correct corresponding noun for side-effect-free?

"Side-effect freeness"? "Side-effect freedom"? "Non-side-effective"?

A good rule of thumb for grammatical questions is, if it's so complicated that you need to ask, it's better to just rephrase the sentence.  For example, "Side-effect-freedom of the function guarantees X" is more simply and elegantly written, "Because the function is side-effect free, X is guaranteed" or even, "The function has no side-effects, so X is guaranteed."

Having said that, keywords for articles are expected to be noun phrases so that would be a place to use "side-effect freedom".

(By the way, "non-side-effective" is an adjective.)


PDA of the language where the number of a's are NOT equal to the number of b's I have this NPDA for language L = {w: num_a(w) == num_b(w)}
all loops in q1

a, $ -> 0$       b, $ -> 1$
a, 0 -> 00       b, 1 -> 11
a, 1 -> \lambda  b, 0 -> \lambda

       ------>q1-----------------\lambda, $ -> $------>q2

initial state: q1
final state: q2
What if I modified L such that the number of a's is not equal to number of b's.
That is L' = {w: num_a(w) != num_b(w)}.
What would be the modification I have to make in the original NPDA.

Your PDA can act as follows. For each $a$ being read, it pushes $A$ into the stack. Then, for every $b$ being read, it attempts to pop $A$ off the stack. If there are no more $A$s, it moves to an accepting state, checking that the rest of the input consists of $b$s; this handles the case in which there are more $b$s than $a$s. Alternatively, it could decide at some point to move, via an $\epsilon$ transition that pops an $A$, to a different accepting state at which no more symbols can be read; this handles the case in which there are more $a$s than $b$s.


Can Edge Belong to a cycle if it is part of multiple BFS products Given a simple connected undirected graph. with V vertices and E edges.
Let e be some edge from E.
If I perform |V| different BFS runs - meaning started each time from a different vertex - and in every run e is part of the Spanning tree produced from the run.
Can it be belonging to some cycle?
The multiple answers I have to choose from are:

it does not belong to any cycle
e might belong to a cycle but if it belongs to an odd-length cycle, then it must belong to an even-length cycle.
e might belong to a cycle but if it belongs to an even-length cycle, then it must belong to an odd-length cycle.
None of the above.

My claim is, because BFS is deterministic and because we performed |V| BFS on the graph, each time from a different vertex. if e was on some cycle, and it doesn't matter even-length or odd length, one of the vertices on the cycle would have caught up with it and remove it.
The only way that it belongs to every Spanning tree, is if it's un replaceable, meaning it's the only thing connecting two vertices.
Am I right? is there any formal proof th

As Yuval pointed out, there is some ambiguity of the original exercise as the enqueueing order of the neighbors of a node is not stipulated by the definition of a breadth-first-search (BFS).
Proposition 1: Let $G$ be a simple undirected connected graph and $e$ is one of its edges. If $e$ is a part of a cycle, then there is a BFS of $G$ that produces a BFS tree that does not contain $e$. (If $e$ is not part of any cycle, then it is a bridge of $G$ and, hence, appears on every spanning tree.)
Since this proposition is, apparently, clear to the OP, no formal proof will be given here.
If we stick to this (indeterministic) version of BFS, the answer to the exercise should be choice 1, "it does not belong to any cycle".

Let us add some context so that that exercise becomes more interesting.
Suppose that for every node, the order of its children to be enqueued in a BFS is fixed beforehand. Now, it can happen that an edge that is part of a cycle can be part of the spanning tree produced from each of $n$ BFS runs. For example, graph $G_1$ with $C_0=[1,3]$, $C_1=[0,2]$, $C_2=[1,3]$, $C_3=[2,0]$, where $C_i$ is the list of neighbors of node $i$ in the enqueueing order. The following lists shows the edge $\overline{1,2}$ is always part of the BFS tree produced.

The BFS starting from node 0 produces the tree with edges $\overline{0, 1}$, $\overline{0,3}$, $\overline{1,2}$.
The BFS starting from node 1 produces the tree with edges $\overline{1, 0}$, $\overline{1,2}$, $\overline{0,3}$.
The BFS starting from node 2 produces the tree with edges $\overline{2, 1}$, $\overline{2,3}$, $\overline{1,0}$.
The BFS starting from node 3 produces the tree with edges $\overline{3, 2}$, $\overline{3,0}$, $\overline{2,1}$.

We have the following proposition.
Proposition 2: Let $G$ be a simple undirected connected graph and $e$ is one of its edges. Suppose we have selected an enqueueing order for the neighbors of each node.   If a BFS of $G$ will always include $e$, then $e$ is either not part of any cycle or $e$ is a part of cycle of even length.
Proof. For the sake of contradiction, suppose that there is a cycle of odd length that contains $e$ and every cycle that contains $e$ is of odd length.
Consider $\mathcal C$, one of the shortest cycles that contains $e$. Since the length of $\mathcal C$ is odd, we can select $v_0$, a node of $\mathcal C$ that is "opposite" to $e$, i.e, the cycle is $v_0, v_1, \cdots, v_k, v_{k+1},\cdots, v_{2k-1}, v_{2k}, v_0$ for some $k$ and $v_i$'s, where $\overline{v_k,v_{k+1}}$ is edge $e$.  Since any cycle containing $e$ must be longer than $\mathcal C$, we have,
$$\text{distance}(v_0, v_{k}) = \text{distance}(v_0, v_{k+1}) = k.$$

Let us run BFS from node $v_0$. Let tree $T$ be the BFS tree produced. We claim $T$ does not contain $e$. Otherwise, suppose $T$ does contain $e$. WLOG, suppose $v_k$ is nearer to $v_0$ than $v_{k+1}$. Since $T$ is a shortest-path tree from $v_0$, we have
$$\text{distance}(v_0, v_{k+1}) = \text{distance}(v_0, v_{k}) + \text{distance}(v_k, v_{k+1})=\text{distance}(v_0, v_{k}) + 1,$$
which contradicts previous equality. This contradiction shows that $T$ does not contain $e$. That, however, contradicts the given condition that every BFS tree contains $e$. $\ \checkmark$

With respect to proposition 2, the answer to the exercise should be choice 3, "$e$ might belong to a cycle but if it belongs to an odd-length cycle, then it must belong to an even-length cycle.", if the context, i.e. the way in which BFS is supposed to run, implies that the enqueueing order of neighbors of a node is fixed before all runs.


Complexity class for polynomial algorithm for 3SAT, but with exponentially large values? I have a hypothetical question: suppose there exists an algorithm that solves an NP-Complete problem polynomial time, but requires the computation
of values that grow exponentially big (or small).

For example, suppose POLY-3SAT solves 3-SAT in N^17, however to do so it must compute/evaluate the value of a number C whose value grows as N^1000 (or 1/N^1000).

What would this imply?  Does computing/evaluating an exponentially large value automatically place the algorithm in EXP-SPACE (or some other complexity class)?  It seems like this would be a different complexity class than just ordinary P.

Complexity classes are classes of problems, not classes of algorithms. For example, the existence of Dijkstra's algorithm means that the problem of computing shortest paths in graphs is in P, but it doesn't make sense to say that "Dijkstra's algorithm is in P".

Exponentially large values can be stored in binary in a polynomial numebr of bits, and we can compute on such numbers using a polynomial number of operations. This notwithstanding, it seems that you're trying to get a polnomial-time algorithm that somehow dows exponentially much work, which is an oxymoron.


Why do we use dynamic memory allocation in general and why did we use it in this particular example? Dynamic Programming C/C++ implementation of LIS(Longest Increasing Subsequence) problem

/* lis() returns the length of the longest increasing
subsequence in arr[] of size n */

int lis( int arr[], int n )
{
int *lis, i, j, max = 0;
lis = (int*) malloc ( sizeof( int ) * n );

/* Initialize LIS values for all indexes */
for (i = 0; i < n; i++ )
    lis[i] = 1;

/* Compute optimized LIS values in bottom up manner */
for (i = 1; i < n; i++ )
    for (j = 0; j < i; j++ )
        if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
            lis[i] = lis[j] + 1;

/* Pick maximum of all LIS values */
for (i = 0; i < n; i++ )
    if (max < lis[i])
        max = lis[i];

/* Free memory to avoid memory leak */
free(lis);
return max;
}

It is a code from www.geeksforgeeks.org . I have seen explanations that memory is allocated(when done dynamically) on heap,  which is a free store of (very large) memory, so it makes sense to only use dynamic allocation when memory required exceeds memory of stack used for storing variables and data locally allocated in functions.

Would it make a difference if I declared array as int arr[n] (as n is given by user in input) and then in main function use lis(arr, n) ? If so, why? If not, what else does dynamic allocation benefit from in this case and in general?

If you declared array as int arr[n] then the memory might be allocated on the Stack and arr would exist as long as the function lis exists, i.e., it would be allocated locally in the lis. malloc on the other hand, would allocate the memory on the Heap and the array would exist until you explicitly free it using free. Nevertheless, as Yuval Filmus noted, memory allocation for the variable length arrays depends on compiler implementation and environment (for example underlying environment may have no distinction between heap and stack). In addition, the GNU C Compiler allocates memory for variable length arrays on the stack.

However, regarding the time or space complexity of the algorithm, it would not make any difference. In particular, the time complexity of an algorithm has nothing to do with its implementation in a particular language.


Mutual information intuition I was creating an example for a casual talk on mutual information. I considered a system of two coins, which with probability 1/2 are copies of each other, and with probability 1/2 are independent.

Then $P(A=B)=1/2+1/2\times 1/2=3/4$, so $P(HH)=P(TT)=3/8$ and $P(HT)=P(TH)=1/8$.

Total information is then $E(-\log_2 p) = 1.81$.

Therefore mutual information is $H(X)+H(Y)-I(X;Y)=1+1-1.81=0.19$ bits.

Is this correct? Because intuitively in this case one might expect, as 50% of the times the coins are equal, the mutual information is $0.5$ bits.

Is there any simple intuition why it is less than $0.5$ bits?

Mutual information tells you how much you learn about $X$ from knowing the value of $Y$ (on average over the choice of $Y$). In other words, mutual information measures how many fewer bits you need to encode $X$ if you already know $Y$, than if you didn't. In your example, learning $Y$ enables you to guess $X$ correctly with probability 0.75, but as $H_2(0.75)>0.5$ ($H_2$ being the binary entropy function), you still need more than half a bit to encode the correct value of X even if you know Y. So your "savings" in encoding length are less than 0.5.

Here is a more illustrative example, I think. You have three random bits, $X$, $Y$, $Z$. $X$ and $Y$ are independent and unbiased, while $Z$ is the exclusive or of $X$ and $Y$. Then $H(X,Y) = 2$, while $H(X,Y|Z=z) = 1$ for any $z \in \{0,1\}$, because knowing $z$ and the value of $X$ determines $Y$. Then $I(X,Y;Z) = H(X,Y) - H(X,Y|Z) = 1$. In words, if you know $Z$ you only really need to encode $X$ rather than both $X$ and $Y$.


If 3SAT reduces to its complement then PH=NP In Chapter 5 of the Arora–Barak complexity theory textbook we are asked to prove the following statement:

  If 3SAT is polynomial-time reducible to its complement then PH=NP.
  How do I prove this statement?

Show that in that case $\text{NP=coNP}$ which means $\Sigma^p_1=\Pi_1^p$, so the hierarchy collapse to the first level.


Non intersecting paths in a graph I'm trying to come up with a good algorithm for the following decision problem:

Let $G=(V,A)$ be a directed graph and let $s,t \in V$. Are there at-least 2 non-intersecting paths from $s$ to $t$?

By non-intersecting I mean that if $P_1$ and $P_2$ are non-intersecting paths from $s$ to $t$ then $\forall e\in P_1\in A, e\notin P_2$ (can share vertices but not edges).

I thought of the following algorithm:

Find the shortest path $P\in A$ in $G$ from $s$ to $t$. if no such path exist, return false;
Find the shortest path $P'\in A-P$ in $G$ from $s$ to $t$. if no such path exists, return false; else return true.

I didn't find a contradicting example but so far I was unable to prove its correctness.

Ideas about proof approaches for this algorithm or suggesting other algorithms is welcome.

Nope, this algorithm doesn't work.  It is possible to find an explicit counterexample.  Since it sounds like this is an exercise you're doing to learn algorithms, I won't spoil the exercise for you, but I'll just give you some hints that may help you find a counter example.

Start with a graph containing just a single path from $s$ to $t$, and nothing else.  Make it a fairly short path, say, 5 edges long.
Introduce a long path from $s$ to $t$ (say, 10 edges long or so) that coincides with the short path for a brief while then diverges.
Now introduce a second long path from $s$ to $t$ with two properties: (a) it is edge-disjoint with the first long path, (b) it has at least one edge in common with the short path.

Finding a counterexample is a little tricky, but draw it out and try some ideas, and I bet you'll be able to figure out.

Your approach doesn't work, but there are other algorithms to solve this problem.  However, they're fairly complicated: more complicated than your could reasonably be expected to discover on your own.  Assuming this is a homework/exercise, I can't just can't believe your teacher would assign you an exercise that requires you to independently re-discover those algorithms -- so there must be some other trick or background information available to you.  You might check in with your teacher.

The other algorithms use the following idea: Look for a "funnel" edge $e$ such that all paths from $s$ to $t$ "funnel through" the edge $e$ (i.e., all paths from $s$ to $t$ must include the edge $e$).  If you find such an edge, obviously there is no pair of edge-disjoint paths from $s$ to $t$.  If you don't find such an edge, then it turns out that there's guaranteed to exist two edge-disjoint paths from $s$ to $t$.  Proving this is tricky, though, as is devising an efficient algorithm to rapidly test for the existence of such an edge.

Since you asked for references, this problem is solved by the following characterization: there are two vertex-disjoint paths from $s$ and $t$ if and only if $s,t$ are part of the same biconnected component.  There are fancy algorithms to decompose a graph into biconnected components in linear time.  Similarly, there are two edge-disjoint paths from $s$ and $t$ if and only if $s,t$ are part of the same 2-edge-connected component.  There are fancy algorithms to decompose a graph into 2-edge-connected components in linear time (or, you can reduce to the problem of computing biconnected components by computing a new graph that swaps vertices and edges).

So, an efficient answer to your question is: decompose the graph into 2-edge-connected components (using the algorithms mentioned in the previous paragraph), then test whether $s$ and $t$ are in the same component.

For more, see e.g., https://en.wikipedia.org/wiki/Biconnected_component and  https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29 and https://en.wikipedia.org/wiki/K-edge-connected_graph.


Recursive, Recursively Enumerable and None of the Above Let

$A = \mathrm{R}$ be the set of all languages that are recursive,
$B = \mathrm{RE} \setminus \mathrm{R}$ be the set of all languages that are recursively enumerable but not recursive and
$C = \overline{\mathrm{RE}}$ be the set of all languages that are not recursively enumerable.

It is clear that for example $\mathrm{CFL} \subseteq A$.

What is a simple example of a member of set B?

What is a simple example of a member of set C?

In general, how do you classify a language as either A, B or C?

You can choose the language of the halting problem

$\qquad \displaystyle B_1 = \{\langle T \rangle \mid T \text{ halts on } \langle T \rangle\} \in B$

and its complement

$\qquad \displaystyle C_1 = \overline{B_1} \in C$.

This is fairly standard material. The proof for $B_1$ not being recursive is the well-known diagonalization. Proving $B_1$ to be RE (recursively enumerable) is a tad tricky, involving interleaved simulation of multiple TMs, but is widely documented. If $C_1$ were RE, then $B_1$ being RE would imply that both are recursive; hence $C_1$ is not RE. This illustrates some of the techniques for such proofs in general.


Why is the sequence, "1,3,2,4", not a bitonic sequence? A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing.

According to the definition of a bitonic sequence, we know that a graph of a bitonic sequence can have at most one "peak" and one "valley".

So, why is the sequence 1,3,2,4 not a bitonic sequence?

I have referred the book, "Parallel Computing", by M. J. Quinn.

In this sequence, lets consider 3 as the bitonic point. So 1,3 makes for a strictly increasing series.

However after we cross the bitonic point 3, 2 and 4 do not make a strictly decreasing series.

Another point in Bitonic Series' is that we have to take into account circular bitonic patterns. So a series like 1 2 5 0 -5 -2 is bitonic since we monotonically increase from 1 to 5, then monotonically decrease from 5 to -5 and again we monotonically increase from -2 to 5.

In the case of 1 *3* 2 *4* 1, there are 2 peaks occurring and hence its not even circularly bitonic.


NP Problems with unique solution Is there any class of NP problems that have one unique solution?
I'm asking that, because when I was studying cryptography I read about the knapsack and I found very interesting the idea.

Yes, the class is called UP (the U standing for "unambiguous"). David points out in the comments that another answer is US.

UP: If $x \in L$, then there is exactly one "proof" ("witness", "certificate", "accepting path"). If $x \not\in L$, there are exactly zero "proofs".

US: If $x \in L$, then there is exactly one "proof". If $x \not\in L$, there may be zero proofs, or 2+ proofs, as long as there is not exactly one.


Consequences of the Time Hierarchy Theorem The form of the Time Hierarchy Theorem that I have is this:

  If $f$ is time constructible then $\text{DTIME}(f(n)) \subsetneq \text{DTIME}(f(2n+1)^3)$.

We want the consequences of this to be that $\text{P} \neq \text{EXP}$ and $\text{EXP} \neq \text{2-EXP}$ etc. But I can't see how this follows.

I have $\text{P}$ defined as $\text{P} := \bigcup_{c=0}^\infty \text{DTIME}(n^c) $ and $\text{EXP}$ as $\text{EXP} := \bigcup_{c=0}^\infty \text{DTIME}(2^{n^c}) $.

I know that $\text{DTIME}(n^c) \subsetneq \text{DTIME}((2n+1)^c)=\text{DTIME}(2^c(n+0.5)^c)$. But $c$ is a constant, so surely the RHS is just another polynomial class.

Additionally, even if I had, say, $\text{DTIME}(n^c) \subsetneq \text{DTIME}(2^{n^c})$, how would I know that the limit of infinitely many of these classes still preserves the "not equal to" relation? (For instance, $\{n\} \subsetneq \{n, n+1\}$ but $\bigcup_n \{n\} = \bigcup_n \{n, n+1\} = \mathbb{N}$.)

Let $f(n) = n^{\log n}$. Then $\mathsf{P} \subseteq \mathsf{DTIME}(f(n))$ while $\mathsf{DTIME}(f(2n+1)^3) \subseteq \mathsf{EXP}$.

(Actually, whether this argument works depends on the exact definition of $\mathsf{DTIME}$. If it doesn't, take $f_C(n) = Cn^{\log n}$ and sum over all integer $C>0$.)


Consider a social network. The goal is to find in the in the network a largest group of people who are all friends with each other. Describe the problem as a graph problem. I've tried to modify the breadth first search algorithm, but haven't gotten anywhere. Any ideas?

This is the Maximum Clique problem, one of the canonical NP-complete problems. On general graphs it probably cannot be solved efficiently, though social networks, with their very particular structures, may lend themselves to more efficient solutions.


A puzzle related to nested loops For a given input $N$, how many times does the enclosed statement executes?

  for $i$ in $1\ldots N$ loop
  $\quad$for $j$ in $1\ldots i$ loop
  $\quad$$\quad$for $k$ in $i\ldots j$ loop
  $\quad$$\quad$$\quad$$sum = sum + i$ ;
  $\quad$$\quad$end loop;
  $\quad$end loop;
  end loop;

Can anyone figure out an easy way or a formula to do this in general. Please explain.

You need to solve simple formula

$\sum_{i=1}^N\sum_{j=1}^i\sum_{k=i}^j1$

this will give you overall result of

$\frac{1}{6}N(N+1)(N+2)$

Math is easy to do here but I used Wolfram Alpha


Reduction from Independent Set with fixed vertex to Independent Set I was looking to solve this reduction, but I dont see how to construct the new graph. It seems very simple but I'm not capable of do it.
I give you the complete explanation about this reduction.
We consider a variant of the independent set problem which we shall call, Independent Set with
a Fixed Node, in which the input contains additionally a vertex $u$ and it is required that the
independent set contains $u$.

As I understand, your problem is a decision problem defined as such:
Independant set with fixed vertex (ISFV):

Input: a graph $G = (V, E)$, a vertex $u \in V$, an integer $k$.
Question: is there an independent set of size $k$ containing $u$?

Independent set (IS) is defined as:

Input: a graph $G = (V, E)$, an integer $k$.
Question: is there an independent set of size $k$?

Suppose you can solve ISFV. Then you can solve IS by running ISFV for each $u\in V$ and checking if the answer is yes for any $u\in V$. Since there are a polynomial number of vertices, the reduction is indeed polynomial.
Another way to do it is to construct the graph $G' = (V\cup\{u\}, E)$ (adding a vertex with no other edge), and check ISFV with $G'$, $u$ and $k + 1$, since the vertex $u$ can always be added to an independent set.


Depth-2 circuits with OR and MOD gates are not universal? It is well-known that every boolean function $f:\{0,1\}^n\to \{0,1\}$ can be realized using a boolean circuit of depth 2 (over the variables, their negation and constant values) containing AND gates in the first level and one single OR gate in the upper level; this is simply the DNF representation of $f$.

Another type of gate which is of great interest in circuit complexity is the $MOD_m$ gate. The usual definition is the following:

$$\mathrm{MOD}_m(x_1,\dots,x_k)=\cases{
  1 & if \(\sum x_i \equiv 0 \mod m\) \\
  0 & if \(\sum x_i \not\equiv 0 \mod m\) \\
}$$

These gates sometimes have surprising power; for example, any boolean function can be represented by a depth-2 circuit having only $\mathrm{MOD}_6$ gates (this is folklore but I can elaborate is someone is interested).

However, another folklore is that circuits with a single OR gate at the top and $\mathrm{MOD}_m$ gates in the bottom layer (with $m$ being fixed once and for all, and in particular being the same for all the gates) is not universal, i.e. for any value of $m$, there are boolean functions that cannot be computed by $\mathrm{OR} \circ \mathrm{MOD}_m$ circuit.

I'm looking for a proof for this claim, or at least some direction.

The Boolean AND function can not be computed. Suppose actually that the AND function is computed by an $\text{OR} \circ \text{MOD}$ circuit. Then it follows that one of the MOD subcircuits must compute then AND function already, which is impossible.


Can a cellular automata structure simulates another cellular automata structure? In Elementary Cellular Automata, rules can show one pattern, but i am wondering if there is something where a cellular automata structure can simulate another structure?

Is there a category for this in Cellular Automata?

Any cellular automata that could be classified as a universal Turing machine would be able to do this. The Game of Life is one such cellular automata. Here is it (rather pointlessly) simulating itself on a larger scale. Here is a Turing machine implemented in it. This 'category' that you want is probably "cellular automata that qualify as universal Turing machines".
I suspect this question will be of interest to you.


Congestion Game with Varying Price I molded my problem as the following game (it is a congestion game with varying price):

$N$ players share resources $E$,

$S_i$ is the strategy space of player $i$ which is in $2^E$ (where $2^E$ is the power set of resources).

$P_e^i$ is the price of resource $e \in E$ considering player $i$. The price of resource $e$ is different for different users.

The goal of each player is to select a strategy $S_i$ which minimize its price $\sum_{e\in S_i}P_e^i$ .

My questions are:

Does this game have any Nash Equilibrium (NE)? If so under which conditions?
If it has any NE, what is a sample algorithm for achieving it?

I searched literature but could not find any appropriate information! Any solution is appreciated!

I think the answer is yes, there is a Nash equilibrium, and it can be attained just by letting each person in turn change his selection to the best possible alternative.

For more information, read this paper:

Weighted congestion games with separable preferences

by: Igal Milchtaich

http://www.citeulike.org/user/erelsegal-halevi/article/12205199


Why do we prefer DFS to find connected components? In finding the connected components in a graph, why do we use DFS, instead of BFS?

Two components $G_1(V_1, E_1)$ and $G_2(V_2, E_2)$ are connected if and only if there is a path between any vertex $v_1\in V_1$ and any other vertex $v_2\in V_2$. Here I'm assuming that both components are known to be connected, i.e., there is a path between any pair of vertices $v_i, v_j$ in any component (so that finding a path between any pair of vertices between both components fully connects them).

Hence, in finding connected components the procedure consists of starting in any vertex of $G_1$ and collecting all nodes that are reachable from it. Clearly, this can be done either with depth-first search or breadth-first search:

Breadth-first search visits nodes in order of their depth from the start state, $s$. This way, it finds all paths of length 1, then length 2 and so on. Its main advantages are: it guarantees it will eventually find a solution (given sufficient memory, see below) and that the solution found is optimal; also, it can avoid transposition by maintaining a CLOSED list that stores all nodes previously expanded. Its main disadvantage is that it takes an exponential amount of memory (unless the graph being traversed is known to be polynomial but this is a rare case indeed).
Detph-first search generates paths of arbitrary length until a goal is found or a threshold is reached. Its main advantage is that it takes memory which is linear in the depth of the search tree developed. Its main disadvantage is that it cannot guarantee that it will ever find a solution and, if it does, that the solution is optimal.

Now, considering the problem stated above it becomes clear that the goal is not to reach a specific goal but to collect nodes reachable from the goal state. For this, there is no specific need to be optimal so that the question reduces to whether the available memory might be enough or not: whereas Breadth-First search does not provide any guarantee, Depth-First search does.

That is why we use Depth-First Search Mostly because: one, there is no need to find an optimal solution; second, memory matters!

Cheers,


Time complexity analysis of 2 arbitrary algorithms - prove or disprove We are given 2 algorithms A and B such that for each input size, algorithm A performs half the number of steps algorithm B performs on the same input size.

We denote the worst time complexity of each one by $g_A(n),g_B(n)$

Also, we know there's a positive function $f(n)$ such that $g_A(n)\in\Omega(f(n))$

Is it possible that $g_B(n)\in\Omega(f(n))$? Is it necessary?

It seems naive to think that it's necessary, but I can't figure out to contradict it.

It is possible. Example $g_A(n)=1$, $g_B(n)=2$, and $f(n)=1$.

It is also necessary, since $g_B(n) = 2 g_A(n) \in\Omega(f(n))$.

To see that $ 2 g_A(n) \in\Omega(f(n))$ you can use the definition of $\Omega(\cdot)$.

From $g_A(n) = \Omega(f(n))$ you know that here is some $n_0$ and some $c>0$ such that, $\forall n \ge n_0$, $g_A(n) \ge c f(n)$.
This implies that, for the same value of $n_0$ and $c$, $2 g_A(n) \ge 2 c f(n) \ge c f(n)$, i.e.,  $ 2 g_A(n) \in\Omega(f(n))$.


Negation of nested quantifiers The problem is:

$$\exists x \forall y (x \ge y)$$

With a domain of all real positive integers.

The negation is:

$$\forall x \exists y (x < y)$$

so, if $y = x + 1$, the negation is true.

That means the negation of the negation (i.e. the original problem) is false.

My question is, that if the original problem is $\exists x \forall y (x \ge y)$, why can't I take $x = y$ and prove the problem true?

I'll start with your last question (in the comments); namely "Why doesn't x = y satisfy the initial problem".

The answer is in the quantifiers. Read from left to right. It starts with "there exists" X. So pick an X in your head. Say X = 5. We can not pick Y here because it doesn't have a value yet and we MUST pick a value for X NOW. Now proceed to read the next quantifier which reads "for all Y". Oops. We can't say for all Y because we already set Y = X.

Actually if you are going to look for a solution that satisfies the original formula, it should be of the form "X=(some positive integer)", with Y not involved at all, as it is a bound variable (as opposed to being a free variable which we can choose).

However, the formula says "there is a (single, and specific) positive integer X which all integers are less than or equal to it" which is clearly false because given any positive integer X, X+1 is a positive integer which is not less than nor equal to it (which is what the negated formula says!).


Why Convolutional codes is easy to factor/handle the uncertainty of a bit being a 0 or a 1 into the decoding? Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 208:

My question is about this part.

[Convolutional codes have been popular in practice because it is easy to factor the uncertainty of a bit being a 0 or a 1 into the decoding.]

Why is it easy to use convolutional codes to factor the uncertainty of a bit?

Is it because the convolutional code circuit is designed in such way as to handle uncertainty properly? I couldn't really find the exact answer. I think the answer has something related to the fact that a convolutional code is not a linear code but I couldn't really understand exactly why a convolutional code is special to handle uncertainty.

An important idea with convolutional codes is that the output sequences of bits (of the convolutional coder) consists of sequences of bits that are correlated with one another, i.e., not independent. Hence, in the receiver side, you know that, given what the convolutional coder is, the sequence of bits can only be some sequences, out of the big set of possibilities. Imagine a big space (say, it may be easier to imagine in 2 or 3 dimensions, then just imagine it gets extended to more dimensions), that has many points in it with integer coordinates, e.g., (1,0,1,1,0), but only only a few of these are allowed possibilities. So you look for the maximum likelihood sequence, which you could think of as the allowed point with the highest probability of having been the input to the convolutional coder.

Having soft-decision decoding, helps when you get to the stage of decoding the sequence of bits, as now, you have the probabilities of each bit being 1 or 0 (by itself, apart from the sequence), which can be fed into the computation of the likelihood of each sequence in the maximum likelihood sequence detection.

A simple example to illustrate: imagine if there are two allowed sequences coming out of the convolutional code: 10 and 01. Now, the receiver gets a sequence that it thinks is 11, but the first 1 only with high certainty (a very likely 1, let's say) whereas the second 1 only with low certainty (maybe 1, if we have to decide between 0 and 1, we say 1). This information helps to decide that the sequence was probably 10 rather than 01. Whereas, with hard decisions, you have 11 and both 10 and 01 are equally likely (e.g., same Hamming distance).

Why is it easy to handle the uncertainty of the bit by bit decisions? This is merely a statement that the decoding algorithms like the Viterbi algorithm, are fundamentally designed to accept the uncertainty values (probabilities) of the bit by bit decisions, as inputs. You could imagine some other algorithms where this is not true. But it is very natural and easy with such maximum likelihood sequence detection algorithms like the Viterbi algorithm.


DCFL with prefix property have LR(0) grammar? There are two important theorems about LR(k) grammars and DCFL. Mentioned here.

A language has an LR(1) grammar iff it is DCFL.
A language has an LR(0) grammar iff it is DCFL and has prefix property.

I have counter example for 2nd theorem, plz see if it is valid counterexample.
(Ofcourse its not valid and I am wrong, But what wrong I am doing here ?)
DCFL without prefix property:    $\{b(ab)^n \mid n\geq0\}$
2nd theorem says it should not have $LR(0)$ grammar, but here it is-
$ S \rightarrow Sab \\S \rightarrow b$
PS: This is my first question here, sorry if I violated any protocol.

Your grammar is $\mathrm{LR}(0)$ by adding a $\mathrm{\$}$ symbol to the alphabet and a starting deduction rule $S'\rightarrow S\$$ when constructing the $\mathrm{LR}(0)$ automaton (and it is a standard construction).

Omitting syntactical purposes, every DCFL $\mathrm{L}$ can be parsed by an $\mathrm{LR}(0)$ grammar for $\mathrm{L}\$$. What makes $\mathrm{LR}(k)$ ($k>0$) more practical is that it may include more syntactical information which is very important in compiler design. Otherwise, all these techniques would never be used in practice. In that case, $\mathrm{LL}(k)$ with local manipulation for expressions would be used instead, even with prohibitive cost of time and space.


Natural language query processing I am trying to implement a natural language query preprocessing module which would, given a query formulated in natural language, extract the keywords from that query and submit it to an IR (information retrieval system) system.

At first, I thought about using some training set to compute TF-IDF values of terms and use these values for estimating the importance of single words. But on second thought, this does not make any sense in this scenario - I only have a training collection but I dont have access to index the indexed IR data. Would it be reasonable to only use the IDF value for such estimation (is IDF enough to establish weight of a term in general)? Or maybe another weighting approach?

Could you suggest how to tackle this problem? Usually, the articles about NLP processing that I read talks about training and test data sets. But what if I only have the query and training data?

I don't know the relative sizes and the nature of your problem, these details could completely change the view. But generally, if the only thing you have at your disposal is a small set of test documents, I would not recommend using that for term weighting at all. A small set of documents would give you an illusion of coverage, a skewed set of weights that would not accurately cover the domain.
If you do have general access to the IR system, though, you could try using the system itself for obtaining statistics by hitting it with random words and recording the number of search results, for example.


Binary subtraction with numbers in 2's complement How can i perform binary subtraction of two numbers that are already in 2's complement?
I have to subtract 01010011 from 10100110,both numbers are in 2's complement.
I know that 10100110 is -90,and 01010011 is 83,so the result should be -173.
So if i use 8 bits that means that there's overflow.
But i don't get how can i perform the subtraction when both the numbers are in 2's complement.
If i just perform the subtraction i get the same number 01010011. How do i show the result and that there's overflow?

You cannot represent –173 using 8 bits, since the range is –128 to 127.
To subtract two numbers in two's complement, you use the identity $a - b = a + (-b)$. In your case, $a = 10100110$, $b = 01010011$, and $-b = 10101101$. Adding $a$ and $-b$, there is overflow, so you know that the number is outside the range.


Why unsafe state not always cause deadlock? I was reading Operating Systems by Galvin and came across the below line,

  Not all unsafe states are deadlock, however. An unsafe state may lead
  to deadlock

Can someone please explain how deadlock != unsafe state ?
I also caught the same line here

  If a safe sequence does not exist, then the system is in an unsafe
  state, which MAY lead to deadlock. ( All safe states are deadlock
  free, but not all unsafe states lead to deadlocks. )

Deadlock means something specific: there are two (or more) processes that are currently blocked waiting for each other.

In an unsafe state you can also be in a situation where there might be a deadlock sometime in the future, but it hasn't happened yet because one or both of the processes haven't actually started waiting.

Consider the following example:

Process A                  Process B
lock X                     lock Y           # state is "unsafe"
                           unlock Y
lock Y                                      # state is back to "safe" (no deadlock this time.  We got lucky.)

There's a more interesting example in Section 7.5.1 of the link you gave:

  Consider a system with 12 tape drives with:

Process       Max Need       Current
P0:             10              5
P2:              9              3

This is an unsafe state.  But we're not in a deadlock. There's only 4 free drives, so, for example, if P0 does request an additional 5, and P2 does request an additional 1, we will deadlock, but it hasn't happened yet.  And P0 might not request any more drives, but might instead free up the drives it already has.  The Max need is over all possible executions of the program, and this might not be one of the executions where we need all 10 drives in P0.


Label coloring to maximize number of "balanced" triangles (NP-hardness) Define a triangle in undirected graph $G$ is balanced if the edge labels  in the triangle are $(+1, +1, +1)$, $(-1, -1, +1)$, $(+1, -1, -1)$ or $(-1, +1, -1)$ (social balance theory).

Problem definition:

Given undirected graph $G=(V, E)$, initial edge label function $f: E \rightarrow \{+1, 0, -1\}$ and $k \in \mathbb{Z}^{+}$, find another label coloring function $g: E \rightarrow \{+1, 0, -1\}$ that maximizes the number of "balanced triangles" in $G$

s.t.

$\forall e \in E \text{ such that } f(e) \neq 0, g(e)=f(e) \text{ holds}$ ($g$ conforms with $f$ for non-zero valued edges).
$|\{e \in E \mid g(e) \neq 0 \text{ and } g(e) \neq f(e)\}| \le k$ (up to $k$ unlabeled edges can be labeled.)

I am trying to prove the NP-hardness of this problem, failing to find an appropriate problem reduction.

Here is what I have thought:

First, the problem can be decomposed using recursion.

We consider assigning label to only one edge, then fix it and solve the sub-problem with updated $f$ and $k-1$ labelings.
However, this approach runs in exponential time.

Second, this problem can be seen from the "set cover" perspective.

We can consider each edge as a set containing a subset of all triangles (the universe), triangles can be classified into three types:

1st-order triangle which has only one unknown label edge ($f(e) = 0$)
2nd-order triangle which has two unknown label edges
3rd-oder triangle where all the labels in the triangle are unknown.

A triangle is considered covered if it's 1st-order and the labeled edge makes it balanced.

If we consider some greedy approach by labeling the best edge one by one, then whenever each edge is labeled, the triangle type information will change accordingly.

For example, some 1st-order triangles will no longer be 1st-order while some 2nd-order triangles will become 1st-order because of the newly-labeled edge.

The "chaining" effect actually couples edges together, which makes things more difficult.

Reduce from 2-Lin(2):

Start with a star that has one edge per variable, and let those initial-labels all be 0.

For each equation    xi + xj  =  b  ,    create an edge from the outer vertex of xi's edge to the outer vertex of xj's edge, and let that edge's initial-weight be (-1)b.

That will produce the output weighted-graph.  Just let k be the number of variables, so the cardinality constraint doesn't matter.

Triangles whose weights are all forced are forced to be good or bad, so their existence affects approximation quality but not which g's are optimal.  Other triangles use at least one variable-edge, and so exactly 2 variable-edges, since being a variable-edge is equivalent to being incident with the central vertex.  Thus no unintended triangles affect which g's are optimal, so those g's are exactly the g's for which composing with log-1 yields an optimal solution to the input 2-Lin(2) instance.

Your problem is obviously in W[P]O, and I have no other clue regarding its parameterized complexity.


Show that run time complexity of operations on 2-4 tree is $O(\lg n)$ I just studied about this 2-4 tree which is a self-balanced tree. Various sources and textbook often mentioned that the insertion, deleting and searching of this tree is $O(\lg n)$.

However, none of them explain the detailed reasons for that run-time complexity. Neither of them also explains them mathematically for the reason behind that run-time complexity.

Therefore, I would like to ask how do i basically show that the run time complexity to process a 2-4 with n keys is $O(\lg n)$?

The tree is height-balanced, therefore the height of the tree is $O(\log n)$. So any insertion has to travel at most $O(\log n)$ steps deep into the tree to find the proper insertion place. Then it also takes another $O(\log n)$ steps the rebalance the tree. The same idea can be applied to searching and deleting in the tree.

The $O(\log n)$ height bound may be difficult to see in a 2-3-4 tree, so I will offer an alternative way to come to this realization. Any 2-3-4 tree is isometric to a proper Red-Black tree. That is to say, "they are equivalent data structures. In other words, for every 2–3–4 tree, there exists at least one red–black tree with data elements in the same order." A Red-Black tree is a balanced binary search tree whose height is more clearly bounded by $O(\log n)$ and so are all of its operations.


complexity of determining whether a language given by context free grammar is empty I know that it is decidable problem to check whether given context free grammar represents empty language -- for instance, AFAIR one could convert it to Chomsky normal form, and then check if any word of length $\leq 2^n$ (or maybe $\leq 2^{n+1}$, I'm not sure) belongs to the language, where $n$ is IIRC the number of nonterminals in CNF. If not, then no longer words belong either and the grammar is empty.

The above algorithm has the unpleasant property of having exponential complexity. The questions that interest me are:

Is there a polynomial algorithm to check whether given CFG represents empty language?
What's the (asymptotically) best known algorithm for that?
What's the simplest polynomial algorithm for that (not necessarily having best known complexity)?

First, omit all terminal symbols. Then the language is empty iff the grammar does not generate the empty string.

An algorithm to check acceptance of the empty string is straightforward. A non-terminal $A$ is nullable, i.e., $A\Rightarrow^* \lambda$ iff $A \to w$ where each symbol in $w$ is nullable.

Determine the symbols nullable with a derivation tree of depth $k$, $k=0,1,\dots$. First find all $A$ such that $A\to \lambda$. Remove these $A$ from the right-hand side of productions and repeat. Axiom $S$ is nullable iff the language is non-empty.
This can be implemented in linear time, making lists of all productions that contain a certain letter at their right-hand side.

Seems to be equivalent to HORN-SAT.


Algorithm to compute average length of a simple path Given a connected graph and two nodes s and t, there can be many different simple paths (without cycles) from s to t.  Is there an efficient algorithm to find the average length of these paths?

I guess you already know that a polynomial algorithm for counting the number of simple paths between two nodes would imply P=NP, this result is due to Valiant (The complexity of enumeration and reliability problems, 1979).
Now imagine, expecting to discover a contradiction, that you could compute $\text{avg}(G, u, v)$ in polynomial time.
Let $G+l$ be the graph resulting from adding a simple path of length $l$ between $u$ and $v$ in $G$. This new path is made of $l-1$ new nodes and it does not interfere with any previous path from $u$ to $v$, provided $l \geq 2$.
Then, $\text{avg}(G+3,u,v) - \text{avg}(G+2,u,v)$ = $1/(\#\text{Paths}(G,u,v)+1)$, from which you can get $\#\text{Paths}(G,u,v)$ in polynomial time. But we know this cannot be expected to be done in polynomial time, a contradiction.