Digraph problem relating in- and out-degrees Given a digraph $D = (V, A)$ and $m \in \mathbb{N}$, the question is is there a subset $A' \subseteq A$, such that $\lvert A' \rvert \geq m$ and $d_{D'}^+(u) \leq d_{D'}^-(v)$ holds for every arc $(u, v) \in A'$ in the subgraph $D' = (V, A')$, i.e. the out-degree of $u$ is not larger than the in-degree of $v$? Note that the degree constraints should hold in the subgraph $D'$.

This seems like a straight-forward problem, alas I am unable to connect it to some more familiar graph problem. I am mostly interested in its complexity.

There is a formulation of this as integer linear programming (ILP).  There is no theoretical guarantee that the resulting ILP will be solvable in polytime, but off-the-shelf ILP solvers are pretty good, and I wouldn't be surprised if in practice an ILP solver is often effective at solving this problem.

In particular, for each edge introduce a variable $x_e$, with the intention that $x_e=1$ means that $e \in A'$ and $x_e=0$ means that $e \notin A'$.  Then we get the obvious constraints $0 \le x_e \le 1$ and $\sum_e x_e \ge m$.  Also introduce a variable $y_e$ for each edge $e \in A$, defined as

$$y_{(u,v)} = \sum_t x_{(t,v)} - \sum_w x_{(u,w)}.$$

Notice that $y_{(u,v)} = d^-_{D'}(v) - d^+_{D'}(u)$.

Now we want to express the requirement that if $x_e=1$ then we must have $y_e\ge 0$.  One way to do this is to introduce the variables $y^+_e, y^-_e$ and add the linear inequalities $y_e = y^+_e-y^-_e$, $y^+_e \ge 0$, $y^-_e \ge 0$, $y^-_e \le c \cdot (1-x_e)$, where here $c$ is a large constant (setting $c=|V|$ is large enough).  Notice that if $x_e=1$, then these constraints imply $0 \le y^-_e \le c \cdot 0 = 0$, i.e., $y^-_e=0$, which implies that $y_e \ge 0$.  In contrast, if $x_e=0$, then these constraints imply $0 \le y^-_e \le c$, which will always be satisfied (the difference of two degrees cannot be more than $|V|$, for trivial reasons), so if $x_e=0$, there are effectively no restrictions on the allowable values of $y_e$, just as we wanted.

There will be a feasible solution to this ILP if and only if there is a subset $A'$ satisfying the desired properties.

My thanks to @user12537, who pointed out that my original answer was flawed.  This revision attempts to address those problems.


Existence of bipartite perfect matching Let $B = G(L, R, E)$ be a bipartite graph. I want to find out whether this graph has a perfect matching. One way to test whether this graph has a perfect matching is Hall's Marriage Theorem, but it is inefficient (i.e $|\mathcal P(L)| = 2^{|L|}$ tests -- not polynomial). I can always find out whether a perfect matching exists by computing a maximum cardinality matching and testing its perfectness, but this involves computing that perfect matching.

Is there an efficient way of deciding whether a perfect bipartite matching exists without computing the matching it self? Ideally I would want an algorithm which is faster than algorithms like Hopcroft Karp or matrix based matching algorithms, which explicitly find out the matching (i.e so not computing the matching makes sense).

Edit: The italic part.

A quick literature review suggests that the fastest algorithm for deciding whether a dense bipartite graph has a perfect matching is still the matrix algorithm, which runs in time $O(|V|^\omega)$. You can reduce the space of the algorithm, see Isolation, Matching and Counting by Allender, Reinhardt and Zhou. A recent paper from 2010, which focuses on planar graphs, suggests that the result of Allender et al. is the best that is known.


Computing FOLLOW sets of left recursive grammar Left recursive ambiguous expression Grammar:

$E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$

I tried computing FIRST and FOLLOW sets of both left recursive grammar and after eliminating left recursion. In both the cases, I was able to compute FIRST sets successfully, but not FOLLOW sets. I have shown the work I did to compute the two sets below.
Note that to compute FIRST and FOLLOW sets, I followed the rules given in Compilers Principles, Techniques, & Tools Second Edition or The Dragon book

I computed FIRST and FOLLOW sets of left recursive grammar following this post.
Computing FIRST sets:

$First(E)$ = $First(E+E)$ $\cup$ $First(E*E)$ $\cup$ $First\bigl((E)\big)$ $\cup$ $First(id)$
Since $\epsilon\not\in\text{First}(E)$, ignore the rules $E$ $\rightarrow$ $E+E\mid E*E$
Therefore, $First(E) = \{(, id\}$

Computing the FOLLOW sets:

$Follow(E) = First(+E) \cup First(*E) \cup First\bigl()\bigr) \cup Follow(E) \cup$ {\$}
See that there is a recursive $Follow(E)$. I am not sure how to resolve this. I know that, a set does not include duplicates, so no matter how many times I union $Follow(E)$ with itself, the result does not change, though I am not sure if my argument even applies in this case. How do I proceed from here?

Since I was stuck, I tried computing FIRST and FOLLOW sets after eliminating left recursion.
Grammar after eliminating left recursion:

$E \rightarrow (E)E' \mid \mathbf i\mathbf dE'$
$E' \rightarrow +EE' \mid *EE' \mid \epsilon$

Computing the FIRST sets:

$First(E') = First(+EE') \cup First(*EE') \cup \{\epsilon\}$
Therefore, $Fisrt(E') = \{\epsilon, +, *\}$
$First(E) = First\bigl((E)E'\bigr) \cup First(\mathbf i\mathbf dE')$
Therefore, $First(E) = \{(, id\}$

Computing FOLLOW sets:

$Follow(E)$ = {\$} $\cup First\bigl()E'\bigr) \cup Follow(E')$
$Follow(E') = Follow(E) \cup Follow(E')$
Again I am stuck with the recursion issue. How do I proceed from here?

I suppose FIRST and FOLLOW sets do not change with elimination of left recursion, or do they?
If yes, should one always calculate the sets after elimination of left recursion?

The cited algorithm for FIRST and FOLLOW  is a least fixed-point algorithm; recursive inclusion of the same set is a no-op.
That's clearly stated in the Dragon Book's description of this algorithm, which involves repeatedly evaluating  the equations until no additional elements are added to any set during an iteration.
The algorithm works without the necessity to remove left recursion (and recursive equations in the FOLLOW set are possible without left recursion in the grammar). Left recursion elimination is not isomorphic, by the way; it's not a reversible procedure and the original grammar can not be recovered.


What mathematical guarantees gives alpha-beta pruning? In the alpha-beta pruning version of the minimax algorithm, when one evaluates a state p with $\alpha$ and $\beta$ cutoff and gets a v value, i.e.,
v = alphabeta(p, $\alpha$, $\beta$)
are these properties true?

alphabeta(p, -$\infty$, $\beta$) = v when $\alpha$ < v
alphabeta(p, $\alpha$, $\infty$) = v when v < $\beta$
alphabeta(p, $\alpha$', $\beta$') = v when $\alpha$ $\le$ $\alpha$' $\le$ $\beta$' $\le$ $\beta$
if v > $\beta$, then alphabeta(p, $\beta$, $\infty$) = alphabeta(p, $\alpha$, $\infty$)
if v < $\alpha$, then alphabeta(p, -$\infty$, $\alpha$) = alphabeta(p, -$\infty$, $\beta$)

I've reached to this results studying the algorithm itself after reading a couple of papers. After applying it to a real case I've got an improvement of ~30% (in number of states visited, and this gives about a 30% of time execution improvement also), but I want to know if there is a mathematical background that supports these changes to the algorithm.

For a complete reference you can check An Analysis of Alpha-Beta Priming
If I am not misunderstanding eq 15 and 16 apply to your case.


NFA that accepts 0* or 1* Problem statement: Produce an NFA that accepts the strings 0* and 1*. So 000 and 11 would be accepted, while 101 would not be.

I'm a bit concerned about my idea because not all combinations of the alphabet are producible in it. Is this NFA legitimate?

My idea (updated to include the empty string):

In a nondeterministic automaton, a given string may have multiple possible paths through the automaton, since the path may include $\varepsilon$-transitions and may reach nodes where there is more than one possible non-$\varepsilon$-transition. A given string may also have no possible path if all the ways to traverse the automaton reach a point where there is no outgoing transition with the correct letter. If there's no possible path through the automaton, the string is rejected, just as if there are paths but none of them reach an accepting state. To determine whether a string is accepted, what matters is only whether there is a way to reach an accepting state, not what happens on paths that don't lead to an accepting state.

You can add a sink state to your automata: add a state $q_s$ which has outgoing transitions to itself (and only to itself) on all letters ($q_s \xrightarrow{0} q_s$, $q_s \xrightarrow{1} q_s$) and add transitions from other states wherever a letter is missing ($q_0 \xrightarrow{0} q_s$, $q_0 \xrightarrow{1} q_s$, $q_1 \xrightarrow{1} q_s$, $q_2 \xrightarrow{0} q_s$). Since there is no way to reach an accepting state via $q_s$, adding this state and these transitions doesn't change the language that the automaton recognizes.

“Completing” the automaton in this way isn't very useful for a nondeterministic automaton. It lets you ensure that every string has at least one path, but note that some strings now have more paths — for example the string $0$ used to only have the path $(q_0, q_1, q_1)$ but now also has $(q_0, q_s)$. The situation is different with deterministic automata. A deterministic automaton must have a transition at every state for every letter. There's a convention to allow some transitions to be missing. Such an incomplete automaton (with missing transitions, i.e. the “transition function” is only a partial function) is equivalent to a complete automaton (where the transition function is a function) which has one extra state, called a sink state, with the missing transitions leading to it and outgoing transitions only to itself. This is a useful convention with deterministic automata, where it's useful to draw automata without “useless” transitions but easier to reason on complete automata where all transitions are present. With nondeterministic automata, since a string doesn't have a unique path through the automaton, making an explicit sink state isn't particularly useful.


When does an algorithm run in $O(1)$ time? When can an algorithm be said to have $O(1)$ complexity? My doubt is if $n$ is specified to be a large number but constant and we cannot implement it in reality without a loop even then can we call it to have $O(1)$ time complexity? Consider the following examples.

Algorithm to add first 1000 natural numbers (that is I mean to say if n is specified directly). Then can we say this has $O(1)$ time complexity?
Finding the $7$th smallest element in a min heap. This element is present in anywhere in the first 6 levels of the heap (considering root at level 0). So to find the element we need to check $2^7 - 1$ elements. Then can we say this has $O(1)$ time complexity?

If you follow the definition of $\mathcal O$, a function $f(x)\in\mathcal O(1)$ when there's an $x_0$ and $M$ such that for all $x>x_0$, $f(x) \leq M$.

For both algorithms you mention, there clearly is an upper bound on the number of steps a machine has to take to compute the result. Therefore, the time complexity for either problem will be some function $T(n)$, where $n$ is the length of the input, such that $T(n)\leq M$ for some $M$ for all $n$. Therefore $T(n)\in \mathcal O(1)$.

Note that the $\mathcal O$ notation has to do with asymptotic behavior of functions, i.e. their behavior as their input grows beyond all bounds. It doesn't care about tiny inputs, whether their length is $1$, $2^7$, or $10^{100}$.


How do I calculate the probability of a PCFG rule in a parser? I'm quite struggling with calculating the probability of a rule for a PCFG.

I've been looking for examples online and more information, but I am none the wiser.
Here is an image of the slides. I cannot understand how the numbers are calculated on the left. From what I understood, I have to take a rule and see how many times it's been used in the tree and then divide it. However, then the numbers that I get do not match this example at all. I feel like I'm missing something small and I've been starting at this for a few hours now and I'm going crazy.

Thank you!

A probabilistic context-free grammar is a generative model, which can be used to generate random words in the language of the underlying context-free grammar. In order to do this, for each nonterminal $A$ we give a probability distribution on the set of rules of the form $A\to \alpha$. To generate a sentence, you start with the starting symbol $S$. As long as the current sentential form contains some nonterminal, say $A$, you apply a random derivation rule $A\to \alpha$ according to the probability distribution. If the probabilities are chosen correctly, then eventually a terminal word will be generated (almost surely).

On the left of your image, you can see the probability distributions. You can estimate the probabilities from a collection of parse trees, but you can also come up with them in any other way. In particular, it doesn't make too much sense to determine them from a single parse tree, like your description seems to imply.

On the right of your image, you can see the calculation that the given parse tree be generated by the PCFG on the left. This probability is the product of all derivation rules that need to be applied to obtain the parse tree (the order of application is immaterial since it doesn't affect the product).

Your underlying difficulty seems to be that you don't understand what PCFGs are for and how they are used. Hopefully, my description above helps to clarify this somewhat.


Algorithm for units allotment to the customers based on preferences I'm searching for a simple algorithm to allotment a real estate unit for the customer based on the customer preferences like the following table.

Each customer has a priorities and we should allocate a unit for each customer, what is the name of this algorithms type to cover all scenarios.

This is not an answer.

This post is used to show that the problem in the question is not the same as the stable marriage problem. There are three differences.

The number of customers might not be the same as the number of units. However, there is an asymmetrical version of stable marriage problem as described here. So this is not a critical difference.
Each customer may not have ranked all units. However, it can be understood each customer ranks all units not explicitly ranked lower than all units ranked. So this is not a critical difference.
None of the unit ranks the customers at all. In stable marriage problem, each man ranks all women while each woman ranks all men. This is an important difference that makes every algorithm for stable marriage problem not applicable directly for the current situation.

We could assign a random (strict) ranking (and possibly different) of customers to each unit. Now we can apply any algorithm for stable marriage problem to our customers and units.
We could assume that all units rank all customers indifferently. We can then find super-stable or strongly-stable "marriage" between customers and units.

Although we could assign rankings of the customers to the units so as to apply the algorithms for stable marriage problem, it adds an extra dimension of condition as well as probably extra steps in the solution algorithms. It might/should be better that the problem and its solution is kept as it is, agnostic to any rankings of the customers by the units.

(This post could be changed to an answer should the question be updated with the addition of a priority table by units.)


Using a greedy algorithm to find a cut S which at least half of the edges cut Let $G$ be an undirected graph.

Find a greedy algorithm that finds a cut $S$ which at least half of the edges cut.

I tried to think about something like choosing the vertex with the highest degree, add it to $S$, remove it from the graph and then repeat this process until I'm done.

However, this is nothing more than a guess and I could not prove it.

I tried to think of the problem in another way - removing no more than half of the edges in the graph until I get a bipartite graph, but finding the cycles takes too long.

Online solutions to this problem included using random algorithms - something we haven't learned in the course where I was handed this question. Other solutions were not clear to me (including one that was posted on this site), or seemed too complicated for the course level.

Could someone provide guidance please?

List the vertices in some order, $v_1,\ldots,v_n$. Put $v_1$ in an arbitrary side of the cut. For each of the vertices $v_2,\ldots,v_n$, put it in the side of the cut which maximized the number of edges cut (only counting edges involving vertices which have already been processed). Since there are only two sides, each time you cut at least half the edges.


Reduction from 3-Partition problem to Balanced Partition problem The 3-Partition problem asks whether a set of $3n$ integers can be partitioned into $n$ sets of three integers such that each set sums up to some given integer $B$. The Balanced Partition problem asks whether $2n$ integers can be partitioned into two equal cardinality sets such that both sets have the same sum. Both problems are known to be NP-complete. However, 3-Partition is strongly NP-complete. I haven't seen in the literature any reduction from 3-Partition to Balanced Partition.

I'm looking for (simple) reduction from the 3-Partition to the Balanced Partition problem.

There are thousands of NP-complete problems in the literature, and most pairs do not have explicit reductions. Since polynomial-time many-one reductions compose, it suffices for researchers to stop when the graph of published reductions is strongly connected, making research into NP-completeness a much more scalable activity.

Although I really don't see the point, I'll humor you by giving a reasonably simple reduction from 3-PARTITION to BALANCED PARTITION, with a few hints about how the proof of correctness goes.

Let the input to the reduction be $x_1, \ldots, x_{3n}, B \in \mathbb Z$, an instance of 3-PARTITION. Verify that $\sum_{i\in[3n]} x_i = nB$. Let $\beta$ be a large number to be chosen later. For every $i \in [3n]$ and every $j \in [n]$, output two numbers
$$x_i \beta^j + \beta^{n+j} + \beta^{2n+i} + \beta^{(i+4)n+j}\\
\beta^{(i+4)n+j}.$$
Intuitively, the first number means that $x_i$ is assigned to 3-partition $j$, and the second number means the opposite. The $x_i \beta^j$ term is used to track the sum of 3-partition $j$. The $\beta^{n+j}$ term is used to track the cardinality of 3-partition $j$. The $\beta^{2n+i}$ term is used to ensure that each $x_i$ is assigned exactly once. The $\beta^{(i+4)n+j}$ term is used to force these numbers into different balanced partitions.

Output two more numbers
$$1 + \sum_{j\in[n]} \Bigl((n-2)B\beta^j + (3n-6)\beta^{n+j}\Bigr) + \sum_{i\in[3n]} (n-2)\beta^{2n+i}\\
1.$$
The first number identifies its balanced partition as “true”, and the other, as “false”. The $1$ term is used to force these numbers into different balanced partitions. The other terms make up the difference between the sum of a 3-partition and the sum of its complement and the size of a 3-partition and the size of its complement and the number of times $x_i$ is assigned.

$\beta$ should be chosen large enough to ensure that “overflow” cannot occur.


Non-trivial difference(s) between Computer Algebra System and Proof Assistant Disclaimer: I am not even an expert user of these two kinds of software.
I understand that the trivial difference between proof assistants and CAS is that in proof assistants, the goal is to show that the given proposition reduces to a tautology. Whereas CAS are used to perform various transformations on mathematical expressions to find results that are useful.
When we are doing mathematics on paper, the techniques used while deriving something are not all that different from the techniques used while proving something. In each case, we start with an expression, and apply one (previously established) rule after another, until we reach our goal. As far as I know, the rules that are applied in derivations are exactly the same as the rules applied while proving something. Looking at it in another way, the human skills honed on derivations are perfectly applicable while performing proofs.
When comparing computer systems, the list of computer algebra systems has no titles in common with the list of proof assistants. From my lay perspective, to name a specific example, I think we can use CAS to derive the roots of a generalized quadratic equation, but only when we have the formula, can we use a proof assistant to verify it.
So, given the vast amount of mathematical knowledge encoded in the libraries of both CAS and proof assistants, why can't we use a CAS to perform proofs, and why can't we use proof assistants for deriving anything beyond tautologies?

There are two major differences: CAS and proof assistant tend to focus on different application domains, and they tend to take a different position on correctness vs ease of deriving results.
Most CAS focus on scientific calculations: calculations that are useful to physicists, to chemists, to mechanical engineers, to roboticists, etc. Proof assistants tend to focus on mathematics, computer science and software engineering.
In a proof assistant, it is crucial that you can only derive true propositions. That's the whole point. In contrast, CAS usually have hidden assumptions. For example, you might derive equations that are only true if one of the variables is nonzero, or if some intermediate result is nonnegative. These assumptions are not always explicit. When modelling a real-world problem, these assumptions are usually justified by the physics – if T is a temperature, there's no point in wondering what the equations would look like for T < 0 K.
Some systems can be classified as both CAS and proof assistants because they make all such assumptions explicit.
There's a good reason why CAS take shortcuts: it makes them easier to use for their application domain. When you work in a proof assistant, you often spend a lot of effort directing the computer to the "interesting" path. You have to figure out that at this step, x>=3, so you guide the proof by telling the proof assistant to consider the cases x<3 and x>=3 separately, then you repeat with y+z>x, and so on. A proof assistant gives results that are true for all inputs, but the cost of that is that you have to make the proof work for all inputs. A CAS can give results for general inputs, which is generally good enough for physics and physical engineering (basically, anywhere that's modelled by continuous mathematics – as opposed to software engineering which is typically modelled by discrete maths and there's no such thing as general inputs).


Polynomial bound on sum of strings I am struggling with the following problem:

Given a set of finite binary strings $S=\{s_1,\ldots,s_k\}$, we say that a string $u$ is a concatenation over $S$ if it is equal to $s_{i_{1}} s_{i_{2}} \cdots s_{i_{t}}$ for some indices $i_1,\ldots, i_t \in \{1,\ldots, k\}.$

Your friend is considering the following problem: given two sets of finite binary strings $A=\{a_1,\ldots,a_m\}$ and $B=\{b_1,\ldots , b_n \}$, does there exist any string $u$ so that $u$ is both a concatenation over $A$ and a concatenation over $B$?

Your friend announces "at least the problem is in $\mathcal{NP}$, since I would just have to exhibit such a string $u$ in order to prove the answer is yes." You point out that this an inadequate explanation. How do we know the shortest string $u$ doesn't have length exponential in the size of the input?

Prove the following:
If there is a string $u$ that is a concatenation over both $A$ and $B$, then there is such a string whose length is bounded by a polynomial in the sum of the lengths of the strings in $A\cup B$.

Now, I have actually found a solution and the solution claims that the maximum length of $u$ is at most $n^2L^2$ where we assume $m \leq n$ and $L$ denotes the maximum length of any string in $A \cup B$. The solution then goes on to exhibit a proof by contradiction using the pigeonhole principle to show that if we assume $u$ has length greater than $n^2L^2$ we arrive at a contradiction.

My question is where does the bound $n^2L^2$ come from? I know that $n$ is the number of strings in set $B$ and $L$ is the max length string in $A \cup B$. But I feel as if the largest possible concatenation over both would be more like $2nL$ since we would need to include every string in both $A$ and $B$ and the longest string in either is $L$ and there are at most $n$ strings in each. What am I missing? I think I can handle the remainder of the proof once I understand where the $n^2L^2$ bound is coming from.

You can also prove this using automata theory. For a set $S = \{s_1,\ldots,s_k\}$ of strings over $\Sigma$, consider the following language over $\Sigma \cup \{1,\ldots,k\}$:
$$ L_S = (1s_1+2s_2+\cdots+ks_k)^+. $$
This language is accepted by a DFA of size roughly $\|S\| := |s_1|+\cdots+|s_k|$. The exact size depends on the model of DFA - in our case it makes sense to ask for at most one transition out of each state with a given label (rather than exactly one transition, as is usually the case).

Now we want to do the same, but for two sets of strings $A = \{a_1,\ldots,a_m\}$, $B = \{b_1,\ldots,b_n\}$. To this end, we consider languages $L_A,L_B$ which are defined as before, but with two differences:

$1,\ldots,k$ are replaced with $A_1,\ldots,A_m$ for $L_A$ and $B_1,\ldots,B_n$ for $L_B$.
The symbols $A_1,\ldots,A_m$ are ignored in $L_B$, and the symbols $B_1,\ldots,B_n$ are ignored in $L_A$.

As an example, suppose that $A = \{a,ba\}$ and that $B = \{ab,a\}$. Then the following word will be in our language: $A_1B_1aA_2bB_2a$.

As before, we can construct DFAs for $L_A,L_B$ having roughly $\|A\|,\|B|$ states, respectively. Using the product construction, we get a DFA of size roughly $\|A\|\cdot\|B\|$ for the intersection. It is well-known (and can be proved using the pigeonhole principle) that if a DFA having $N$ states accepts any word, then it accepts some word of size less than $N$. This implies your claim.

In terms of lower bounds, it is easy to refute your conjecture that $2nL$ is enough. Consider $A = \{ 0^L \}$ and $B = \{ 0^{L-1} \}$. It is not hard to check that the minimal solution has length $L(L-1) \approx L^2$.

It's less clear what is the correct dependence on $n$.


Predicate Logics - double negation HELP me understand Sorry for maybe a silly question but i need to understand how
¬(¬∀x ¬A(x)) equals ∀x ¬A(x)

In my mind, the negation before the parenthesis will be applied to both ¬∀x and ¬A(x). So it would look like this:

¬(¬∀x ¬A(x)) = ¬¬∀x ¬¬A(x)

A double negation would become positive and would then let
¬(¬∀x ¬A(x)) equal to ∀x A(x).

So, why would ¬(¬∀x ¬A(x)) equal ∀x ¬A(x)?
Why wouldnt ¬(¬∀x ¬A(x)) equal ∀x A(x)?

The semantics of negation are very simple:

  $\lnot \alpha$ is True iff $\alpha$ is false.

In your example, $\lnot (\lnot \forall x \lnot A(x))$ is True iff $\lnot \forall x \lnot A(x)$ is False iff $\forall x \lnot A(x)$ is True iff for all $x$, $\lnot A(x)$ is True iff for all $x$, $A(x)$ is false.

Perhaps the issue would become simpler if we fully parenthesize your expression:
$$
\lnot \stackrel 1( \lnot \stackrel2( \forall x \stackrel3( \lnot \stackrel4( A\stackrel5( x \stackrel 5) \stackrel 4) \stackrel 3) \stackrel 2) \stackrel 1).
$$
The superscripts count the nesting depth.


Why no context switch is required in case of spinlock in operating systems? I have a query regarding the fact that how Spinlocks are advantageous in terms of context switching ?

Ask yourself why you use a context switch in a lock operation in the first place. What are the benefits and the disadvantages?

Now ask yourself if there are situations where the benefits are slim. How does a spin lock minimise the disadvantages of a normal lock operation?

Consider the cases where a lock is released after a minute, second, millisecond, microsecond or nanosecond.


Is it possible to solve the critical section problem with an atomic subtract operation? In my Operating Systems class, our professor asked us to solve the critical section problem with the following atomic operation:

int sub(int &x, int val){
  x -= val;
  return x;
}

The homework was already due and nobody in my class could come up with a solution. The professor's solution does not even work. Here it is:

int x = 1; //let x be a shared variable between threads
entry(){
  int loop = sub(x, 1);
  while(loop < 0){
    loop = sub(x, 1);
  }
}

exit(){
  x = 1;
}

This solution suffers from the fact that the critical section may be very long, and thus x may loop all the way back around to positive values and eventually become zero before another thread calls exit(). I do not believe it is possible to solve the CS problem because this implementation of sub() does not return the original value of x, but the new value with val subtracted. The professor is convinced that it is possible, even though neither he nor the TA could come up with a proper answer.

If the number of threads is less than the number of values that you can hold in a memory location, then you can implement a non-overflowing test-and-test-and-set operation with atomic-fetch-and-decrement.

So, for example, if you have 32-bit integers and less than 4 billion threads the following should work:

initialize: x = 0

acquireLock:
  repeat:
    while x != 0:
      # do nothing
    tmp = atomicFetchAndDecrement(x) # (decrements x and returns *new* value of x)
  until tmp == -1

releaseLock:
  x = 0

Each thread only decrements the counter once for each time that it sees the counter get reset to 0, so the value of x never becomes smaller than -numberOfThreads.

The real value of fetch-and-increment is that you can make critical sections that are "fair" in the sense that threads are given the lock in the order in which they first request it.  Like this:

initialize: nextTicket = 0; current = 0

acquireLock:
  myTicket = atomicFetchAndDecrement(nextTicket)       # (decrements and then returns *new* value)
  myTicket = myTicket + 1                # make up for the weird atomicFetchAndDecrement semantics
  while current != myTicket:
    # do nothing

releaseLock:
  current = current - 1                  # does not need to be atomic, releaser is only writer

Again, with 32-bit integers this works as long as the number of threads is less than $2^{32}$.


Whether language of all turing machines is decidable or undecidable or semi-decidable? I recently came across this language:

$L=\{<TM>| \text{TM accepts recursively enumerable languages}\}$

It was asked in the question to find out whether language L is decidable or undecidable.

As far as I could reason out, language L is the set of all recursive enumerable languages or set of all turing machines.

But I can't figure out whether this language is decidable or not.

Can anyone please help me out??

Thanks in advance!!

Let us express $L$ slightly more precisely.
$$ L=\{<TM>\; \mid \text{The language accepted by } TM \\ \text{ is a recursively enumerable language}\}$$

Since for any Turing machine $TM$, the language accepted by it is a recursively enumerable language by definition, that restriction clause for $TM$ does not have any effect at all. We have, as indicated by OP,
$$L \text{ is the set of encodings of Turing machines.} $$

The question becomes "Whether the language of all Turing machines is decidable or undecidable or semi-decidable?" as in the title.

Now this question is really about how we encode all Turing machines (in some specified model). There are ways to encode them so that we could end up with undecidable or semi-decidable language. However, in most reasonable encodings of Turing machines of most common models such as the standard Turing machines described in Wikipedia, we can check whether a string encodes a Turing machine by an algorithm in finite time.

So the simplified answer is "$L$ is decidable". This is the generally accepted answer. It is especially suitable when the encoding of Turing machines is implied to be decidable such as in the book Introduction to the theory of computation by Michael Sipser. Or when a decidable encoding of Turing machines has been described explicitly and has been assumed to be the default such as in the book Introduction to automata theory languages and computation by John E. Hopcraft et. al.

(The complete answer would be "$L$ is decidable unless an unusual encoding of Turing machines is used", which sounds, however, pedantic and which is usually not a welcomed answer.)


Why do Bloom filters work? Let's say I am using Bloom filters to create a function to check if a word exists in a document or not.  If I pick a hash function to fill out a bit bucket for all words in my document. Then if for a given number of words, wouldn't the whole bit bucket be all 1s? If so then checking for any word will return true? What am I missing here?

Given that you want to insert $n$ words into the Bloom filter, and you want a false positive probability of $p$, the wikipedia page on Bloom filters gives the following formulas for choosing $m$, the number of bits in your table and $k$, the number of hash functions that you are going to use.  They give
$
m = - \frac{n \ln p}{(\ln 2)^2}
$
and
$$
k = \frac{m}{n}\ln 2=-\frac{\ln p}{\ln 2}=-\lg_2p,
$$
so you should choose
$$
m=\frac{nk}{\ln 2}.
$$

That actually works out quite nicely.  You are going to get a table with about half the bits set and half cleared, so the entropy per bit is going to be maximal, and the probability of a false positive is going to be
$0.5^k$.


Show that a language cannot be generated by linear grammar I have a language $ L= \{ w \in \{a,b\}^* ; |w|_b=2i, i \ge 0 \}$  that is a language with even number of b's.

I found a grammar for it with these rules:

$S \rightarrow aS \ | \ bL \ | \ \lambda  $

$L \rightarrow aL \ | \ bS \  $

How could I show that this language cannot be generated by linear grammar?

According to Wikipedia, a linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of its productions.

Your grammar is right-regular and can thus be used to prove that $L \in \mathrm{REG}$. Since every regular grammar is linear, your claim is impossible to prove.


Is there a complexity viewpoint of Galois' theorem? Galois's theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a polynomial there is no deterministic algorithm to find the roots?
Now consider a decision question of the form, "Given a real rooted polynomial $p$ and a number k is the third and the fourth highest root of $p$ at least at a gap of k?"

A proof certificate for this decision question will just be the set of roots of this polynomial and that is short certificate and hence it looks like $NP$ BUT isn't Galois theorem saying that there does not exist any deterministic algorithm to find a certificate for this decision question? (and this property if true rules out any algorithm to decide the answer to this question)

So in what complexity class does this decision question lie in?

All NP-complete questions I have seen always have a trivial exponential time algorithm available to solve them. I don't know if this is expected to be a property which should always be true for all NP-complete questions. For this decision question this doesn't seem to be true.

I assume you are considering polynomials with integer coefficients.

You've taken the wrong starting point for your investigations; your goal is to find good estimates for the real roots. Looking for an algebraic formula so that you can evaluate it to enough precision is something you can do, but it's not really the right thing to do here. (unless, of course, "the k-th largest real root of a polynomial" is one of your algebraic operations)

A much better starting point is to use Sturm's theorem to isolate the roots of the polynomial. You can then produce better estimates by binary search, but if that's too slow, you can use Newton's method to quickly produce estimates of high precision.

But that's just about finding certificates. There's still the question of what certificates can exist.

First off, I will point out that you can directly compute whether or not two of the roots are exactly $k$ units apart, e.g. by computing $\gcd(p(x), p(x-k))$. You will also have to decide what you want to do about repeated roots and deal with appropriately. I assume you will deal with these case specially.

If we know the two roots are not exactly $k$ units apart, that means that you can produce an estimate of sufficient precision to prove that they are either greater or less than $k$ units apart. e.g. there are two kinds of certificates:

The first kind (proof in the negative) is

$a$ is not a root of $p$
$p$ has no roots in $(a-k, a)$
$p$ has three roots in $(a, \infty)$

The second kind (proof in the positive) is

$a$ is not a root of $p$
$p$ has at least two roots in $(a-k,a)$
$p$ has two roots in $(a, \infty)$

A certificate can be verified by using Sturm's theorem. Now, your question about the size of a certificate boils down to finding how many bits of precision you need to represent $a$.

In other words, what are the bounds on the possible values of $a-b-k$, where $a,b$ are roots of $f$?

I'm not sure of a great approach, but one that should give you something is to observe that all of these values are roots of the polynomial:

$$ g(x) = \mathop{\text{Res}_y}(f(y), f(x + y + k)) $$

Why? Recall that the resultant of two monic polynomials is the product of all differences of their roots, so

$$ g(x) = c^{d^2} \prod_{a,b}(b - (a - x - k))
= \prod_{a,b} (x - (a-b-k))$$

where $c$ is the leading coefficient and $d$ is the degree of $f$. (maybe I've written the formula for $-g(x)$ instead of $g(x)$; I'm never sure on the sign)

So the question is to find estimates for how large the coefficients $g$ can be, and then once you know that, find estimates to how close a root of $g$ can be to zero.

(or, alternatively, find the largest magnitude that a root of the reverse polynomial of $g$ can have; the roots of the reverse polynomial are the inverses of the roots of $g$)


Do self-loops in DFA cause infinite languages? A true/false question: If a DFA $M$ contains a self-loop on some state $q$, then $M$ must accept an infinite language.

The answer is "false". I've read this question, but I'm still wondering why $M$ does not necessarily accept an infinite language. Isn't the language $b^*$ infinite? Don't all self-loops look like $b^*$?

the answer is False:

consider a DFA that has no accepting states at all: any loop is not relevant, the language will always be the empty set.

Another option - a loop on a dead state, etc.

However, if it contains a loop on an "accepting path", then indeed the language must be infinite. (this is actually the key idea behind the pumping lemma..)


Can I say ≤ O(f(x)) rather than = O(f(x)) if the bound is not tight? Suppose I just invented merge sort, but due to my limited ability was only able to prove that the running time is $O(n^2)$. However, I suspect that the running time is actually better (in reality it's $O(n \log n)$).

Technically in my paper I should say “runtime $=O(n^2)$”, but it’s somewhat misleading because people think I mean it's a tight bound (i.e. people generally  think big O actually means big theta). Therefore, I am considering saying “runtime $\leq O(n^2)$”, even though it's technically redundant. Obviously I will explain in the text what I mean, but I'm saying it many times for different equations and I don't want to keep repeating myself.

I am aware of the definitions of big O, Omega, Theta, but which is clearer in a CS paper? The paper is related to machine learning.

Technically in my paper I should say “runtime $=O(n^2)$”, but it’s somewhat misleading because people think I mean it's a tight bound

No, technically you should write "runtime $\in O(n^2)$".

  I am considering saying “runtime $≤ O(n^2)$”, even though it's technically redundant

I don't think "redundant" is the right word. In a way, it makes even less sense than "$= O(\_)$"

While you can not control your readers' misconceptions, you can try not to feed them. Why not make explicit what you mean?

  The running time is bounded by $O(n^2)$ but we suspect this bound can be improved to match the lower bound $\Omega(n \log n)$.

Or:

  We have thus shown that the running time is in $\Omega(n \log n) \cap O(n^2)$.

In formulae, my advice is to always use "$\in$" unless you can give more precise results. For instance,

$\qquad C(n) = 2n\log n - n \pm O(\log n)$

would be okay.


Bin packing with given bin sizes, not necessarily same I was thinking about variants of bin packing and thought of this variant wherein the given $m$ bins have size specified(not necessarily same) and we need to put $n$ objects in them. Is this still NP Hard, considering that bin packing is NP hard?

Yes, it's still NP-hard, because the input could specify that the bins actually are the same size, which is the standard NP-hard version.

A general rule of thumb is that allowing the input to be more general can't make the problem any easier, as long as the new setting includes the original hard case as a special case.


Time complexity of computing binomial coefficients (with binary representation of integers) Given two integers $n$ and $k$, I want to compute the exact value of the binomial coefficient ${n \choose k}$.

Here $n$ and $k$ are given in their binary representation, meaning that the size of the input is about $\log n + \log k$.

How fast, in big-O notation, can we compute ${n \choose k}$?

One can compute this in time $O(k)$ using, say, the multiplicative formula (see here).
But in the worst case, this is exponential in the size of the input.

Can ${n \choose k}$ be computed faster?

There is no sub-exponential algorithm. For example, $\binom{2n}{n}$ has $\log\binom{2n}{n}$ bits, and according to Stirling's approximation,

$$
\binom{2n}{n}=\Theta\left(\frac{2\sqrt{\pi n}\left(\frac{2n}{\mathrm{e}}\right)^{2n}}{\left(\sqrt{2\pi n}\left(\frac{n}{\mathrm{e}}\right)^{n}\right)^2}\right)=\Theta\left(\frac{4^n}{\sqrt{n}}\right),
$$

we have

$$
\begin{align*}
\log\binom{2n}{n}=\Omega(n).
\end{align*}
$$

So we need at least $\Omega(n)$ time to output the result of $\binom{2n}{n}$.


Best Fit Memory Allocation Algorithm Statistical Analysis I've been reading book on Operating System, in which author writes :

  Somewhat surprisingly, it(Best fit) also results in more wasted memory than first fit or next fit because it tends to fill up memory with tiny, useless holes. First fit generates larger holes on average.

I want to understand how generating larger holes would be better. It would be helpful if someone can share a link of article about statistical analysis of best fit, first fit.

You want your "holes" to be bigger because a big hole is more likely to be useful for an allocation in the future.  For example, if you have 2 128-byte holes that are not adjacent then you can't satisfy a request for 160 bytes.  If the 2 128-byte holes are adjacent and coallesced into a single 256-byte hole, then you could satisfy a future request for 160 bytes with that hole.

Here's the best article I know of on memory allocation policies:

Paul R. Wilson, Mark S Johnstone, Michael Neely, David Boles: Dynamic Storage Allocation: A Survey and Critical Review, Int'l Workshop on Memory Mgt, 1995.

They followed up with a more detailed experimental study a few years later:

Mark S Johnstone, Paul R Wilson: The Memory Fragmentation Problem: Solved?, First Int'l Symposium on Memory Mgt, 1998.

In the papers they find that best fit works quite well in practice.  Another lesson of both papers is that statistical analyses don't work (usually).  You need to run experiments on real traces of the alloc/free calls from real workloads.

A very good public domain malloc implementation was written in the mid '90's by Doug Lea: http://g.oswego.edu/dl/html/malloc.html.  It's essentially an approximation of best fit.


Recognizing a language given an automaton I'm trying to figure out which language can be recognized in this automaton

Automata http://cdn.imghack.se/images/64b81d259a1d403b810dd9744dc222f7.jpg

According to Wikipedia here "The language L ⊆ Σ* recognized by an automaton is the set of all the words that are accepted by the automaton."

So using what Wikipedia states and knowing that this automaton is a finite state automaton, I would dare to say that this automaton accepts regular languages.

If I would use M to define this automaton then I could say:

The language recognized by M is the regular language given by a certain regular expression.

But I'm having a a hard time figuring out the regular expression.

I'm not sure of about this but here is what I think the regular expression looks like

$$
L = (a|b)(a|b)^*a^*
$$

I would appreciate any help in this matter

In general, there is a dynamic programming algorithm for converting finite automata into regular expressions. But this one is simple enough that we can eyball it.

From the start state, we have two choices. So we can see our expression has the form | where _ represents the parts of the expression yet to be filled in.

Let's look at the top branch. There we must read two a's, then as many a's or b's as we want. So this part will have the form aa(a|b)*

For the second half, we see we must read at least one a or b. Then we can loop on a or b as many times a we want, and then we must read two a's. So we get (a|b)(a|b)*aa

Notice the patterns here. When we have more than one transition coming out of a state, that represents the "|" operation. A transiton on "a,b" is equivalent to having one transition on a and another on b.

So, our final expression is (aa(a|b)*) | ((a|b)(a|b)*aa).

Any time we have a cycle, either on a particular state, or on a path of states, we get something corresponding to *. And every time we have to read something in sequence, we have concatenation.


Lower bound of complexity of simple problem Consider the simple problem:

Given a list of objects L of length n, and an object O, determine if O is in L.

It is intuitive that there cannot exist an algorithm a with worst-case time complexity less than O(n) to correctly solve this problem.  But without considering individual algorithms, how can one mathematically prove that no faster algorithm exists?

The informal argument is that you need at least $n$ steps to read all the input assuming you can only read at most one element of the input per "step". Of course, you might state that maybe there's an algorithm that doesn't need to read all the input. The argument against that is an adversarial argument which produces an input where such an algorithm will get the wrong answer.

Let $x$ be an input of length $n$ that doesn't contain $O$, and $A$ an algorithm that completes in less than $n$ steps correctly reporting that the input does not contain $O$. There is necessarily an element of the list that $A$ did not look at. Pick one and call that the $i$th element. Running $A$ on $x'$ which is identical to $x$ except that the $i$th element is $O$ then produces the incorrect result. Since $A$ is deterministic and all the inputs $A$ actually reads are the same, then $A$ must behave in the same manner and so it will incorrectly report that the list does not contain $O$.


Minimum covering problem formulation Shouldn't I post this question on mathematics.stackexchange.com?

  Let be an airlaine company which has to affect its aircrew to several flights. We group som flights in subset, every flights of a subset have to be realised by the same aircrew according to the actual possibilites and labour regulations. We provide a list, as rich a way as possible, of those combinations. Let be $E_j$ the $j^{th}$ combination. We associate to $E_j$ a cost $c_j$ that take into account, for instance, the bonuses to aircrew for a time worked that would outreach th norms, etc...

  The problem is to determine the combinations such that all flights are covered and that the cost is the minimal one.

  I have to give a formulation of this problem as a linear programing problem.

The set of flights $V=\{v_1;...;v_m\}$

Let be
$x_j=
\begin{cases}
1 \mbox{ if the combination $E_j$ is taken}\\
0 \mbox{ else}
\end{cases}$

I don't understand the following formulation by my teacher.
\begin{cases}
\min &\sum_{j=1}^{m}c_jx_j\\
&\sum_{v_i \in E_j}x_j&\ge 1\\
\end{cases}

But I quite understand the one given by Vangelis Paschos in Combinatorial Optimization:

  An instance of the MIN WEIGHTED VERTEX COVER. An instance of this problem (given the incident matrix $A$, of dimension $m\times n$, of a gaph $G(V,E)$ of order $n$ with $|E|=m$ and a vector $\bar w$, of dimension $n$ of the costs of the edges $V$), can be expressed in terms of linear program in integers as

  $$\begin{cases} \min &\bar w.\bar x\\
&A.\bar x &\ge \bar 1\\
&\bar x \in \{0;1\}^n
\end{cases}$$

  such that $x_i=1$ if the vertex $v_i\in V$ is included in the solution $x_i = 0$ if it is not included. The block of $m$ constraints $A.\bar x \ge \bar 1$ expresses the fact that for each edge at least one of these extremes must be included in the solution.

But I don't quite understand this notation $\bar 1$

  The feasible solutions are all the transversals of $G$ and the optimum solution is a transversal of $G$ of minimum total weight, that is a transversal corresponding to a feasible vector consisting of a maximum number of 1.

Typically $\bar{1}$ represents the vector of 1s. In this case, $A\bar{x} \ge \bar{1}$ enforces the vertex cover constraint. The two formulations are the same, except the latter uses a more compact matrix notation to represent the inequality for each of the $j$ variables.


How is the space hierarchy theorem different for non space constructible functions? Sipser first introduces space constructible functions. Then uses the definition to prove the space hierarchy theorem:

  if f(n) is a space constructible function then there are languages that can be decided in O(f(n)) space but not in o(f(n)) space.

The author only mentions as most encountered functions are space constructible, it is a good assumption. Are there any cases where non space constructible functions of are interest ? How does the space hierarchy theorem changes under such conditions ?

Your question is answered on Wikipedia: for any $s(n)$, and $f(n) = O(s(n))$, and any computable $g(n) = o(s(n))$, $\mathsf{DSPACE}(f(n)) \neq \mathsf{DSPACE}(g(n))$. This is a result due to Geffert.


BlockChain: Always get a new Hash I am asking a simple question. Why we say that we would always get a new hash in a blockchain? Why we can't have collisions?

One way of collision is that the hard disk becomes full and there is no more space to store a transaction.

Some body please guide me.

Zulfi.

Blockchain uses a cryptographic hash function that is designed to have collision resistance.  Thus, while it's possible you might run into a pair of inputs that produce the same output... it's very very unlikely to happen by chance; and it is believed to be very difficult to intentionally find such a pair of inputs.

Disk space has nothing to do with collisions in the hash function.


Cast to boolean, for integer linear programming I want to express the following constraint, in an integer linear program:

$$y = \begin{cases}
0 &\text{if } x=0\\
1 &\text{if } x\ne 0.
\end{cases}$$

I already have the integer variables $x,y$ and I'm promised that $-100 \le x \le 100$.  How can I express the above constraint, in a form suitable for use with an integer linear programming solver?

This will presumably require introducing some additional variables.  What new variables and constraints do I need to add?  Can it be done cleanly with one new variable?  Two?

Equivalently, this is asking how to enforce the constraint

$$y \ne 0 \text{ if and only if } x \ne 0.$$

in the context where I already have constraints that imply $|x| \le 100$ and $0 \le y \le 1$.

(My goal is to fix an error in https://cs.stackexchange.com/a/12118/755.)

I think I can do it with one extra binary variable $\delta \in \{0,1\}$:

$$
-100y \le x \le 100 y
$$
$$
 0.001y-100.001\delta \le x \le -0.001y+100.001 (1-\delta)
$$

Update

This assumes $x$ is a continuous variable. If we restrict $x$ to be integer valued, then the second constraint can be simplified to:
$$
 y-101\delta \le x \le -y+101 (1-\delta)
$$


Find expectation with Chernoff bound We have a group of employees and their company will assign a prize to as many employees as possible by finding the ones probably better than the rest. The company assigned the same $2$ tasks to every employee and scored their results with $2$ values $x, y$ both in $[0, 1]$. The company selects the best employees among the others, if there is no other employee with a better score in both tasks.

Knowing that both scores are uniformly distributed in $[0, 1]$, how can i proof that the number of the employees receiving the price is estimated near to $\log n$, with $n$ the number of the employees, having high probability?

I need to use Chernoff bound to bound the probability, that the number of winning employees is higher than $\log n$.

In this answer I assume given scores are pairwise didtinct. Note that the probability of two scores being equal is 0 since we have continuous probability. I think the same proof can be tweaked to span the case where two probabilities are equal but it will make it more complicated.

Let $p_1, \dots p_n$ be the set of employees sorted in descending order according to the outcome of the first task. Let $X_i$ be an indicator random variable, that the employee $p_i$ wins a prize. This means
$$X_i =
\begin{cases}
1&;\text{$p_i$ wins a prize,}\\
0&;\text{Otherwise.}
\end{cases}$$
Let $C$ be a random variable equals to the number of employees who win a prize. Note that $C = \sum\limits_{i=1}^{n} X_i$ and by linearity of expectation we get $E[C] = \sum\limits_{i=1}^{n}E[X_i]$. Moreover, note that the variables $X_i$ are mutually independent, since an employee $p_i$ wins a prize if and only if the score of $p_i$ in the second task is greater than the score of $p_j$ in the same task for all $j < i$.

It is easy to see that $$E[X_i] = Pr[X_i] = \frac{1}{i}$$ (think about the values of the scores the first $i$ employees get and the probability that the $i$th gets the highest of them). Now we can compute
 $$E[C] = \sum\limits_{i=1}^{n}E[X_i]= \sum\limits_{i=1}^n\frac{1}{i} = H_n \leq \ln n,$$
where $H_n$is the $n$th term of the harmonic series.

Now since we already discussed that the variables are independent, we can apply Chernoff bounds to prove that the probability, that the expected value is higher than a constant factor of $\ln n$ is very small and hence, with  high probability the expected value is not greater than a constant factor of $\ln n$.

Here is the extension about Chernoff bounds.

Chernoff bound: Let $\mu := E[C]$ and let $\delta < 2e - 1$ be a positive constant, the bound can be written as follows (see link):
$$Pr[C > (1+\delta)\mu] <
e^{-\mu\delta^2/4}.$$
Now set $\delta = 4$. We get
$$Pr[C > 5\lg n] < e^{-16/4\ln n} = \frac{1}{n^{4}}$$


Is it possible to derive a deterministic CSPRNG given two functions, at least one of which is a CSPRNG? Let f and g be two functions with integer range 0..m-1. They may keep state and interact with the world (for example setting a seed or reading the current time), calling them multiple times may produce different results. f and g can see each other's state, but cannot modify the other's state.

Assume at least one of f and g is a cryptographically secure pseudorandom number generator, but it is unknown which one. Is it possible to create a function h that uses f and g and behaves as a CSPRNG? h is not allowed to set or read external state directly, the only way it can modify or read state is by calling f and g and observing their results. h should work for any given f and g.

Of course, h is not allowed to use any "true" source of randomness, and ideally the construction should not involve passing randomness tests.

As a related problem, I believe that if f and g were perfectly random, then f + g (mod m) would also be perfectly random. But I think in this deterministic case, it's always possible to create a g such that it "cancels out" f in h. Not sure how to prove this.

No.  There's no way to create such an $h$.

Here's an informal sketch of the proof.  Suppose $f$ is a CSPRNG.  Then for all $h$, there exists a $g$ such that $h(f,g)$ outputs only even numbers.  In particular, $g$ reads the state of $f$, deduces what $f$'s next output will be, and outputs something that will cause $h$ to output an even number (if necessary, by generating multiple candidate outputs and testing each one to see which will provoke $h$ to output an even number).

[This is the main idea of a proof.  To get a full formal proof, you'd also have to consider the case where $h$ ignores its second input or mostly ignores its second input.  However, it's pretty easy to see that such a $h$ can't possibly be any good, either.]

That's the theory.  What about practice?  In the real world, if you're not sure whether $f$ or $g$ are any good, don't let them read the internal state of anything else.  Don't ever let something that might be malicious read the internal state of security-critical parts of your system.

If you know that $f$ and $g$ are independent (as random variables), and you know that at least one of $f,g$ is a secure CSPRNG, then $f+g \bmod m$ is indeed good (it's a secure CSPRNG).  However, the critical requirement here is that they be independent.  If one can read the internal state of the other, then they're not independent.


How to implement two stacks in one array? I want to begin by saying that this is NOT a homework question. I am reading Introduction to Algorithms - the famous CLRS text to become a better programmer. I am trying to solve the problems and exercises given in the book by myself.

I am trying to solve Excercise 10.1-2 from Chapter 10 Elementary Data Structures from CLRS Second Edition. Here is what its states:

  Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.

The solution that I have come up with so far is:

  Let array A[1..n] implement two stacks: S1[1..i] and S2[i..n].

  For the PUSH-S1 and PUSH-S2 operations, if the stack is 'full' then start pushing elements into the other stack (eg. if stack S1 is full when a new element is trying to be pushed in, then push that element into stack S2 and vice versa).

The problem with this approach is I will not be able to POP-S1 or POP-S2 reliably as there is no way of 'remembering' which element belongs to which stack. If the elements of the stack are (key,value) pairs, the key being the stack number, then to pop an element I would have to search, in the worst case, i or (n-i) times - which will be O(n) (feel free to correct me if I am wrong here), which would not be O(1).

I have been banging my head on the question for quite a while now. Am I on the right track? Can someone give my possible pointers for solving this problem?

In general, how should I 'think' about these problems? Or can only really intelligent people solve these types of problems? Will tackling/solving problems like these (i.e. gaining experience) help me become better at this?

I await enlightenment.

Another hint in addition to what Yuval said: it helps to place the stacks in a specific way in the arrays and fix their direction of growth accordingly. They don't have to grow in the same direction.


Can an $NDTM$ simultaneously perform a set of operations on all strings of a given length? Can an $NDTM$ perform a set of operations on all strings of a given length $b$, at the same time? Aka can it operate on all strings of a given length by doing something like: spawn $2^b$ branches then operate on each string of length b on each branch?
How could it do this tho if the branches can't communicate? That's what I'm having a hard time with. How does any given branch, if it doesn't know what strings the other branches are running, know what string to run the operations on (so that all the strings are covered by $2^b$ branches)?

The easier way to think of NTM's is not as they are capable of "spawning branches", but as they are capable of "splitting into two branches, and each branch knows who it is (the first branch is 0, and the second is 1)"
In this way of thinking (that also actually represents what's going on inside the TM), splitting into $2^b$ branches means doing the "split" operation $b$ times.
Lets do a simple example with $b=2$:
In the first split, we have two branches: 0,1.
In the second split, the "0" branch splits into branches "00" and "01" (notice that these are not numbers! They are strings) and the "1" branch splits into "10" and "11".
Notice that every string of length 2 is either one of the 4 final branches, and therefore this is how we would be able to non-deterministically check every string of length $b=2$.
The same applies for any other $b$ (note that if its not a constant, it will maybe harm the time or space complexity of the machine)


Why is $n + 2n^2 + 10n^4 = O(n^5)$? I'm going through an algorithms text book. One of the questions asks:

True or false?
$n + 2n^2 + 10n^4$ is $O(n^5)$.

This is marked as true.
Shouldn't it be $O(n^4)$? What am I missing here?

This is an unfortunate inconsistency (or at least a frequent confusion) in terminology. Formally speaking, people usually define big-oh to be an upper bound, so that means running in time $O(n^5)$ just means the running time is bounded by $n^5$ times some constant if $n$ is sufficiently large.

In other words, $n^4$ is $O(n^5)$ (and it's also $O(n^4)$, $O(n^9)$, and $O(n^{1000})$, as well as many other things). In your example, $n + 2n^2 + 10n^4$ is both $O(n^4)$ and $O(n^5)$.

The usual formal notation for an exact asymptotic analysis (i.e. something that is both an upper and lower bound) is big-theta, or $\Theta$. So you would say that $n + 2n^2 + 10n^4$ is $\Theta(n^4)$, but it's not $\Theta(n^5)$.

The reason I call this terminology "unfortunate" is that it confuses many people, including you (as evidenced by you asking this question). The problem is that in informal speech, and often even in papers, people say $O$ when they really mean $\Theta$: when someone refers to a $O(n)$ algorithm, or an $O(n^2)$ algorithm, they often really mean $\Theta(n)$ or $\Theta(n^2)$. While using $O$ is usually not technically incorrect, it is misleading when $\Theta$ would also be correct and more precise. This is something you have to get used to: recognizing whether the writer really means $O$, or whether they could have said $\Theta$.


Which class of languages is accepted by PDA when we restrict the stack to logarithmic size? Let $\mathrm{LOG}_{\mathrm{CF}}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq \log n$ cells of its stack for each input of length $n$.

Obviously, this class is a proper subset of the class of context-free languages. Which languages are in this class, and what (closure) properties does it have?

I have found this class in Harrison's Book:

I have searched a lot about iterated counter languages but I can't understand them well. I also I don't know whether this problem is what I am looking for or not.

I think if we have L1 and L2 in this class so we can have their union in this class by adding two lambda- transition.

And if we have a Pda A with logarithmic stack height , if we can construct an equivalent  Pda B with  the extra property that always clear all its stack symbols except the bottom-of-stack symble after every acceptance so we this class will be closed under Kleene- star

I will be grateful if anyone can explain me whether this class is closed under intersection  and complement or not

I am still looking for just one non-regular-language that is in this class!!!

The class $LOG_{CF}$ is in fact the class of regular languages $R$ (and thus have all of the regular languages closure properties).

$R\subseteq LOG_{CF}$ is trivial, so we'll concern ourselves only with the the other direction.

Let $A$ be some PDA, and let $s(n)$ be the maximal stack size of $A$'s run on a length-$n$ word.
First notice that if $s(n)=O(1)$, then $L(A)$ is regular (you can always encode a finite set of stack configurations into a NFA).

We will claim that if $s(n)=\omega(1)$, then $s(n)=\Theta(n)$, thus there can't be any PDA which is guaranteed to use non-constant sub-linear space.

We define Automaton-Sub-Configuration to be a tuple $(q,x)\in Q\times \Gamma^*$ such that currently the automaton is in state $q$, and the top of his stack (the suffix of the stack word), is a word $x\in\Gamma^*$.

Now if $s(n)=\omega(1)$, there has to be some automaton sub-configuration, $(q',x')$, for the such that:

$(q',x')$ can be reached unbounded number of times, and on every time it is reached, the stack size grows by at least one symbol.

Let $w_0\in \Sigma^*$ be a word such that the automaton would reach $(q',x')$, and let $w_1$ be a word such that when reading $w_1$ out of $(q',x')$, the automaton ends at $(q',x')$ with at least one additional symbol in the stack.

Finally, consider the word $w=w_0\cdot w_1^k$. Notice that the automaton stack size after reading $w$ is (at least) $k$, while $|w|=|w_0|+k|w_1|$, hence the stack size could be linear in the length of the word.

The conclusion is that for any PDA $A$, $s(n)=O(1)$ or $s(n)=\Theta(n)$.


Simple path in a Finite Acceptor What is the definition of a 'simple path' in a finite acceptor?
My concern is whether self loops can be considered as a part of simple path from initial to final state?

The only reasonable definition for a simple path in a finite acceptor would be a finite path in its transition graph, i.e. no vertices (states) may appear twice in that path. This especially excludes paths that use self loops.


How to convert regular expression to CFG? How can I convert the regular expression (ab*)*b to a context-free grammar?
When I look for examples I keep seeing plus signs in the expression but I don’t have any. Is that just a different way of writing it?

There is a simple algorithm to convert regular expressions to context-free grammars. It goes as follows.
Base cases:

$\emptyset$ corresponds to the empty grammar.
$\epsilon$ corresponds to the grammar $S \to \epsilon$.
$\sigma$ (where $\sigma \in \Sigma$) corresponds to the grammar $S \to \sigma$.

Inductive cases:

$r = r_1 + r_2$. Given CFGs for $r_1,r_2$ with disjoint nonterminals and starting symbols $S_1,S_2$, add rules $S \to S_1 \mid S_2$ and make $S$ the new starting symbols.
$r = r_1r_2$. Same, adding the rule $S \to S_1 S_2$ instead.
$r = r_1{}^*$. Same, adding the rules $S \to S S_1 \mid \epsilon$ instead.


Is it possible to use a space-filling curve to index a 2D grid which is not $2^x$ by $2^y$? I am working on a project which needs to traverse a 2d spatial grid, and would like to use a space-filling curve indexing scheme.  Unfortunately, I have no guarantee that the input grid will be a power of two along either dimension.  In fact, it may be just barely over a power of two in some cases.  Virtually extending the grid to be a power of two in size may use too much memory (it is a very large grid).  Is it still possible to use a space-filling curve, such as a Morton curve, to index this grid?

What kind of indexing do you need? If it is just a lookup, your can interleave the bits of you coordinates to get a z-ordered Morton value. These could be stored in binary trie (critbit-tree) that uses prefix sharing. Traversing the tree gives you Morton-order, and the possible prefix sharing should reduce memory consumption.
I implemented one in Java: critbit

If you also need geometric queries (kNN, window queries, range queries), you could try the PH-Tree, it's like a bit like quadtree, but uses prefix sharing like a trie and some other things to be much more efficient (memory and speed) than a quadtree. The tree uses internally a Morton ordering so a full traversal or Window queries will always return Morton-ordered results.


Proof on tree size using Isabelle I'm trying to learn a little bit about Isabelle and proofs in general, and it's uses in Programming Language Theory. I'm following a book, "Concrete Semantics with Isabelle/HOL". I'm still in the beggining.

I was able to do the first exercises, but I got to a point where I noticed I just don't know what I'm doing. I just solved a question where I spent some time failing to prove something, than tried changing one little thing and it magically worked. Can someone explain what exactly is happening?

Ok, so here is what the question is basically about:

We had to make a simple tree structure with no data, like:

datatype tree0 = Tip | Node "tree0" "tree0"

The question ask us to make a function nodes t that count the number of nodes and leafs on the tree. Then, it provides a function:

fun explode :: "nat ⇒ tree0 ⇒ tree0" where
"explode 0 t = t" |
"explode (Suc n) t = explode n (Node t t)"

And ask us to provide an equation for the number of elements (nodes t) of the exploded tree, based on N and T, and prove that this equation is correct.

The equation I found was: nodes(explode n t) = (2^n)*(nodes t + 1) - 1

Which I tried proving using induction on "n" alone.

lemma aft_tree: "nodes(explode n t) = (2^n)*(nodes t + 1) - 1"
apply(induct n)
apply(auto)
apply(simp add: exp_grow)
apply(simp add: algebra_simps)

done

After "apply(auto)", the goal changed to:

goal (1 subgoal):
 1. ⋀n. nodes (explode n t) = 2 ^ n + 2 ^ n * nodes t - Suc 0 ⟹
         nodes (explode n (Node t t)) = 2 * 2 ^ n + 2 * 2 ^ n * nodes t - Suc 0

So, I thought that proving nodes(explode n (Node t t)) = 2*nodes(explode n t) + 1 would solve it. So I made a lemma for it, proved it and added the next two "simp"s.

But the proof failed, with:

goal (1 subgoal):
 1. ⋀n. nodes (explode n t) = 2 ^ n + nodes t * 2 ^ n - Suc 0 ⟹
         Suc (2 * 2 ^ n + nodes t * (2 * 2 ^ n) - Suc (Suc 0)) =
         2 * 2 ^ n + nodes t * (2 * 2 ^ n) - Suc 0

I don't quite get why this doesn't end the proof. I wondered if I was just proving the wrong thing, or maybe I'm just mixing everything up.

After this, I removed the simplification based on exp_grow, and tried generalizing the proof for "t". So I got:

lemma aft_tree: "nodes(explode n t) = (2^n)*(nodes t + 1) - 1"
apply(induct n arbitrary: t)
apply(auto)
apply(simp add: algebra_simps)
done

Which worked! And I just couldn't understand what happend. I tried following this proof step by step. After auto, the goal is:

goal (1 subgoal):
 1. ⋀n t. (⋀t. nodes (explode n t) = 2 ^ n + 2 ^ n * nodes t - Suc 0) ⟹
           2 ^ n + (2 ^ n + 2 ^ n * (nodes t + nodes t)) - Suc 0 =
           2 * 2 ^ n + 2 * 2 ^ n * nodes t - Suc 0

And it's proved on algebra_simps.
I don't understand what happened, and why it didn't work on the first time.
I think I'm misunderstanding everything. It has been a while since I took an Algebra course, and maybe I'm doing the proof by induction wrong. I was able to do the other questions, but this one left me a little lost :(

So, can someone help me on this? What am I getting wrong here?

Your first goal is provable, but is somewhat non-trivial arithmetic. I believe that the issue is essentially Isabelle not knowing that
$$S(x - 2) = x -1$$
is true for arbitrary $x$, and indeed, this property is false in general, if $x<2$! This is because $x-2=0$ in Isabelle for $x=1$.

Here this doesn't occur, because $x=2\cdot 2^n$, so $x\geq 2$ for all $n\in\mathbb{N}$. But the simplifier doesn't know this. Adding a lemma along those lines, or making sure 2*nodes(explode n t) + 1 doesn't get simplified to S(2*nodes(explode n t)) should solve your issue.

Alternately, you could re-cast your whole proof in $\mathbb{Z}$, where subtraction behaves more sanely.


What is wrong with this proof that proves that 0*1* is not a regular language? I know why cases 1 and 2 are wrong because our language can have different numbers of 0's and 1's. But I'm not sure how case 3 can be proved wrong for our language.
Exercise 1.30:
Describe the error in the following “proof” that $0^{∗}1^{∗}$ is not a regular language. (An error must exist because $0^{∗}1^{∗}$ is regular.)

The proof is by contradiction. Assume
that $0^{∗}1^{∗}$ is regular. Let p be the pumping length for $0^{∗}1^{∗}$ given by the pumping
lemma. Choose s to be the string $0^{p}1^{p}$. You know that s is a member of $0^{∗}1^{∗}$, but
Example 1.73 shows that s cannot be pumped. Thus you have a contradiction. So
$0^{∗}1^{∗}$ is not regular.

Example 1.73:

Let B be the language $\{0^{n}1^{n}|n ≥ 0\}$. We use the pumping lemma to prove that
B is not regular. The proof is by contradiction.
Assume to the contrary that B is regular. Let p be the pumping length given
by the pumping lemma. Choose s to be the string $0^{p}1^{p}$. Because s is a member
of B and s has length more than p, the pumping lemma guarantees that s can be
split into three pieces, s = xyz, where for any i ≥ 0 the string $xy^{i}z$ is in B. We
consider three cases to show that this result is impossible.

The string y consists only of 0s. In this case, the string xyyz has more 0s
than 1s and so is not a member of B, violating condition 1 of the pumping
lemma. This case is a contradiction.
The string y consists only of 1s. This case also gives a contradiction.
The string y consists of both 0s and 1s. In this case, the string xyyz may
have the same number of 0s and 1s, but they will be out of order with some
1s before 0s. Hence it is not a member of B, which is a contradiction.

Thus a contradiction is unavoidable if we make the assumption that B is regular,
so B is not regular. Note that we can simplify this argument by applying
condition 3 of the pumping lemma to eliminate cases 2 and 3.
In this example, finding the string s was easy because any string in B of
length p or more would work.

This question is from the book 'Introduction to the Theory of Computations' by Michael Sipser, exercise 1.30

The pumping lemma states that if $L$ is regular then there exists a constant $p$ such that any word $w \in L$ of length at least $p$ can be decomposed as $w = xyz$ so that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, and (iii) $xy^iz \in L$ for all $i \geq 0$.
The pumping lemma does not state that any decomposition which satisfies properties (i),(ii) also satisfies property (iii).
The pumping lemma only guarantees that some decomposition which satisfies all three properties exists.
In your case, you can take $p = 1$. If $w = 0^n1^m$ for $n \geq 1$, then you can take the decomposition $x = \epsilon$, $y = 0$, $z = 0^{n-1} 1^m$. If $w = 1^m$ for $m \geq 1$, then you can take the decomposition $x = \epsilon$, $y = 1$, $z = 1^{m-1}$.


Is every unambiguous grammar regular? While searching for an answer to this question I found out that there is an unambiguous grammar for every regular language.
But is there a regular language for every unambiguous grammar? How can I prove that this is/isn't true?

The following grammar is unambiguous yet generates a non-regular language:
$$ S \to aSb \mid \epsilon $$


Approximate LP for vertex cover problem I am studying the topic of vertex cover on coursera and how it can be solved approximately by linear programming. Suppose the optimal solution for the vertex cover problem is $OPT$. I do not understand why the approximate solution $$\sum_u w_u x^*_u \leq OPT$$
where $w_u$ is the weight to each vertex and $x^*_u$ is the approximate solution to the vertex cover problem and $0 \leq x_u^* \leq 1$
Can someone provide an explanation on how it is possible for the equation above ?

Let's start with an integer program for vertex cover:
\begin{align}
&\min \sum_{v \in V} x_v \\
\text{s.t.}\;\; & x_u + x_v \geq 1 &&\text{for every } (u,v) \in E \\
& x_v \in \{0,1\} &&\text{for every } v \in V
\end{align}
Here $V$ is the set of vertices and $E$ is the set of edges.
The optimal solution for this integer program is the minimum vertex cover in the graph. We denote its value by OPT.
Unfortunately integer programming is NP-hard to solve exactly, so we consider a linear programming relaxation, replacing the constraint $x_v \in \{0,1\}$ by the constraint $x_v \in [0,1]$:
\begin{align}
&\min \sum_{v \in V} x_v \\
\text{s.t.}\;\; & x_u + x_v \geq 1 &&\text{for every } (u,v) \in E \\
& 0 \leq x_v \leq 1 &&\text{for every } v \in V
\end{align}
Every feasible solution of the original integer program is also a feasible solution of the linear programming relaxation. In other words, the linear program is minimizing over a set of solutions which contains the set of solutions to the integer program. Therefore the optimal value of the linear program is bounded from above by OPT.
More abstractly, if $A \subseteq B$ then
$$
\min_{x \in B} \phi(x) \leq \min_{x \in A} \phi(x).
$$
In our case, $A$ is the set of solutions to the integer program, $B$ is the set of solutions of the linear program, and $\phi$ is the objective function $\sum_{v \in V} x_v$.


Language to define perfectly a programming problem Is there any language, which can be used to define all programming problems perfectly?

By perfectly, I mean with these two properties:

p is the problem.
d is the definition in the language.
P(d, p): "d is the definition of the problem p"

$$
\forall p\exists d(P(d, p))
$$
$$
\forall p\exists d1,d2((P(d1, p) \land P(d2, p)) \rightarrow (d1  \Leftrightarrow d2))
$$

Example: The simple problem to output the first N numbers, can be defined in many ways, for example in the english language. I want a language which restricts the number of definitions to 1 for every problem. In other words, no 2 distinct definitions can define the same problem, and every problem has a definition.

 1. This language exists?

 2. If such language does not exists, is it possible to create one?

This question is somewhat unclear to me; however, under one interpretation there is a result which indicates that the answer is unsatisfyingly yes: namely, the existence of Friedberg numberings. Roughly speaking, a Friedberg numbering is a programming language which is Turing complete but in which no two programs perform the same task.

(More formally: a Friedberg numbering is a computable function $\varphi$ of two variables such that for each computable function $\psi$ of one variable there is exactly one $e_\psi^\varphi$ such that $\lambda x.\varphi(e_\psi^\varphi,x)\cong\lambda x.\psi(x)$.)

A simple proof of the existence of such numberings was given by Kummer.

That said, it's easy to show that we can never "translate into" a Friedberg numbering, which renders the positive result above somewhat misleading at best: if $(\theta_i)_{i\in\mathbb{N}}$ is the usual numbering of computable functions of one variable and $\varphi$ is a Friedberg numbering, the map $$(*)_\varphi:\theta_i\mapsto e_{\theta_i}^\varphi$$ is not computable. Essentially, what this means is that programming in the usual sense is impossible in the context of a Friedberg numbering: while every computable function has a corresponding program, there's no way to find it.

To prove this, simply note that from the map $(*)_\varphi$ we can compute the set of indices for the never-defined function: let $c$ be the unique number such that $\lambda x.\varphi(c,x)$ is never defined, and to tell whether $\theta_i$ is never defined just check whether $(*)_\varphi(i)=c$. (Note that this can be improved: if we replace the never-defined function with the identity function, or more generally any partial computable function with infinite domain, the resulting set of indices is strictly more complicated than the halting problem - it has Turing degree $\bf 0''$. So in fact "translating into a Friedberg numbering" is really very impossible indeed.)

This "impossibility of translation" is what breaks the "obvious" proof that Friedberg numberings are impossible. It also points the way to the general study of numberings, which is a fruitful area of study within computability theory. The numberings which are Turing complete in a "non-stupid" way are the acceptable numberings, which are also those which are maximal in a certain natural pre-ordering on numberings.


Historical relation between computer science and the theory of dynamical systems I have asked this question at math.stackexchange, but I have been redirected here.

My question is, if there is any historical relation between the fields of Dynamical systems (and related fields such as Optimal control) and (theoretical) Computer science. The reason for which I ask this question is, that several older major journals, now considered to be primarily focused on theoretical computer science, were originally devoted both to computer science and to dynamical systems.

The example of such journals can be for instance Journal of Computer and System Sciences. Mainly in its beginnings (however, I am too young to remember these times), it published papers both on computer science and on system sciences, and both of the fields seemed to be of equal importance. Moreover, also the name of the journal Information and Control suggests the relation to optimal control. However, this journal was always focused mainly on theoretical computer science and information theory.

So therefore I wonder, if these fields (nowadays, up to my knowledge, considered to be substantially different) have something in common or if there is some purpose to consider these fields to be related.

Yes there did seem to be historically a strong connection between study of dynamical systems and advanced theoretical computer science, that is shifted dramatically over time. Some of this has become mainstream and incorporated into more "core CS" (for example the empirical study of algorithms running on the SAT transition point and their strong thermodynamic/physics analogies, or empirically studied behavior of differential equations too difficult to solve exactly, etc) and some of it has moved into separate areas of more "applied" research, eg simulations of complex systems. Here are some refs on the history that might be helpful:

Chaos, the making of a new science by Gleick
Complexity, the emerging science at the edge of order and chaos by Waldrop


Explain $\log_2(n)$ squared asymptotic run-time for naive nested parallel CREW PRAM mergesort On from Page 1 of these lecture notes it is stated in the final paragraph of the section titled CREW Mergesort:

  Each such step (in a sequence of $\Theta(\log_2\ n)$ steps) takes
  time $\Theta(\log_2\ s)$ with a sequence length of $s$. Summing these, we
  obtain an overall run time of $\Theta((\log_2\  n)^2)$ for $n$
  processors, which is not quite (but almost!) cost-optimal.

Can anyone show explicitly how the sum mentioned is calculated and the squared log result arrived at?

You want to compute this sum:
$$
\sum_{i=1}^{\mathrm{log}\left( n\right) }\mathrm{log}\left( \frac{n}{{2}^{i}}\right)
$$

This can be easily rewritten to:
$$
\sum_{i=1}^{\mathrm{log}\left( n\right) }\mathrm{log}\left( n\right) - \sum_{i=1}^{\mathrm{log}\left( n\right) }i
$$

The first term is clearly $(\log(n))^2$. The second term is $(\log(n))^2/2+o((\log(n))^2)$. Summed, the result is $\Theta((\log(n))^2)$.


Memory usage of a BST or hash table? I would like to use a data structure allowing fast access, either a balanced binary search tree (BST) for $O(\log n)$ access time or an open hash table for constant access time.

1) What is the exact memory usage of a BST or hash table, for storing $n$ values? For instance, if we consider a BST, are $n$ pointers sufficient for storing it? (We can neglect the size of the stored values. The only thing that interests me is the storage overhead involed by the use of a specific data structure)

2) If the choice has to be determined by the cost in space, subject to the constraint of a fast enough access time, what is the best data structure to use?

For the space cost criteria, I would like a precise description. I'm interested in two types of usage: static and dynamic. I ask this question in the context of a C implementation.

I'm mostly interested in values around $n=100000$.

When you're asking about "exact" memory usage, do consider that all of those pointers may not be necessary. To see why, consider that the number of binary trees with $n$ nodes is $C_{2n}$, where:

$$C_i = \frac{1}{i+1} { 2i \choose i }$$

are the Catalan numbers. Using Stirling's approximation, we find:

$$\log C_{2n} = 2n - O(\log n)$$

So to represent a binary tree with $n$ nodes, it is sufficient to use two bits per node. That's a lot less than two pointers.

It's not too difficult to work how how to compress a static (i.e. non-updatable) binary search tree down to that size; do a depth-first or breadth-first search, and store a "1" for every branch node and a "0" for every leaf. (It is harder to see how to get $O(\log n)$ access time, and much harder to see how to allow updates to the tree. This is an active research area.)

Incidentally, while different balanced binary tree variants are interesting from a theoretical perspective, the consistent message from decades of experimental algorithmics is that in practice, any balancing scheme is as good as any other. The purpose of balancing a binary search tree is to avoid degenerate behaviour, no more and no less. Stepanov also noted that if he'd designed the STL today, he might consider in-memory B-trees instead of red-black trees, because they use cache more efficiently. They also use $n + o(n)$ extra pointers to store $n$ nodes, compared with $2n$ or $3n$ for most binary search trees.

As for hash tables, there is a similar analysis that you can do. If you are (say) storing $2^n$ integers in a hash table from the range $[0,2^m)$, and $2^n \ll 2^m$, then it is sufficient to use

$$\log {2^m \choose 2^n} \approx (m-n)2^n$$

bits. It is possible to achieve close to this bound using hash tables.

To give you the basic idea, consider an idealised hash table where you have $2^n$ elements stored in $2^n$ slots (i.e. load factor of one where every "chain" has length one).

If you hash $m$ bits of key into $m$ bits of hash, then store this in a $n$-bit hash table, then $n$ bits of the hash are implied by the position in the hash table, and you therefore only need to store the remaining $m-n$ bits. By using an invertible hash function (e.g. a Feistel network), you can recover the key exactly.

Of course, traditional hash tables have Poisson behaviour, so you would need to use a technique like cuckoo hashing to get close to a load factor of one with no chaining. See Backyard Cuckoo Hashing for further details.

So if space usage is a far more important factor than time (subject to time being "good enough"), it may be worth looking into this area of compressed data structures, and succinct data structures in particular.


Augmenting a tree such that we preserve the insertion operation optimal runtime Suppose we are given a red-black tree with $n$ vertices with distinct keys and we want to store, as addition information in each vertex $v$, the biggest key out of the keys that are smaller than $v$ (or nothing if it doesn't exist). Can we insert a new element in this tree in $O(\log n)$ time?

I think that we can. My idea is that while traversing the tree in order to determine where to insert the new element, we could just update this additional information for every vertex that we encounter. The problem with this is that we may not update all the required vertices, for instance:

        (80)
      /      \
    (1)      (81)
   /   \     /   \
  (0) (79) (77)  (82)

Here, if we would try to insert $76$, we would not update the additional information in the vertex with value $77$ if we use the method I described above.

I would like strongly appreciate hints to improve my solution (mostly I would want only hints).

I think you mean $successor$ & $predecessor $.

Formally:
$predecessor(v): x  $ s.t $ x \leq v$ (or smaller if your keys are distinct) and no $y$ exists in your structure s.t $y \leq v$ and $y > x $

Symmetrical definition for $successor(v)$.

You can apply several methods for each node to know its $successor/predecessor $ in $O(1)$ time. A simple option is pointers - you "pay" $log(n)$ while inserting, pay another $log(n)$ to find $successor/predecessor$, and update the corresponding fields.

A doubly linked list would work just as well (in which case you save pointers to the list in the tree nodes, from which you can go to next or previous list node for successor/ predecessor respectively)

btw, your example is wrong. the key '77' cannot be in the right subtree of '80'


Impact of Polynomial Time Algorithm for an NP Complete problem on Complexity Theory Assuming (hypothetically) someone proves $P=NP$ by providing a polynomial time algorithm for a $NP-Complete$ problem the Polynomial Hierarchy collapses.

What are the other (important) questions that are still left in complexity theory in respect to the remaining complexity classes?

If possible can someone help with a link where it might have been answered already (which I am guessing it might be) is perfectly fine too.

If P=NP, then it follows that P=co-NP, and NP=NP-complete (i.e. there are no NP-intermediate problems, which are in NP but not NP-complete).

But there are plenty of other divisions in the hierarchy which might still hold, and might not. P=NP wouldn't necessarily tell us anything about this.

On the higher end of things, how does NP relate to PSPACE? It's entirely possible that they're the same (only if P=NP: if P≠NP, they're definitely different), in which case all the classes in the middle (such as PP, which uses a probabilistic Turing machine) are collapsed together too.

On the lower end, how does P relate to L (logarithmic space)? There are various classes between these ones too, such as NL (nondeterministic log space), and these might all be collapsed into a single class also.


Why there is no constraint on "Prover" in definition of $IP$? According to the definition of $IP$ given in Sanjeev Arora and Barak there is no constraint on the running time of the "Prover" ( when "verifier" sends a message to the "Prover" and expects a message in return from it ). Why is it so  ?
Also the book says the "Prover" might compute some undecidable function. How is that possible ? Am I missing something trivial ?

There's nothing canonical for what constraint one might put on it.  Requiring complete efficiency would give BPP, since the algorithm can just simulate the whole interaction.  Requiring efficient-given-a-polynomial-length-string would give MA, since the prover could just send its string to the verifier.  It turns out that PSPACE is always enough, so letting the prover be at least that powerful yields the same class as not constraining the prover.  I suppose

things from TFUP to [CH given a polynomial-length string] might give intermediate classes.


Removing Left Recursion Im currently learning about removing left recursion. Ive watched a few youtube clips and understand the basics. For example, i can remove left recursion for the following;

$E \rightarrow E+T \mid T$

Answer

$E \rightarrow TE'$

$E'\rightarrow \varepsilon \mid +TE'$

Ive been given the following question which has sort of 3 parts to it and has me confused a lot (compared to the question example above). The question is remove the left recursion from the following grammar;

$A \rightarrow Ba$

$B \rightarrow dab \mid cB$

$C\rightarrow cB\mid Ac$

Is there another rule to follow for this, or when it has more than 1 statement as such.

Any help will be much appreciated

The fact confusing you might be, that the given grammar isn't left recursive at all and so nothing has to be done.

To be left recursive there would have to be a nonterminal Symbol, that by a chain of productions results in a sequence of sybols starting with the same nonterminal.

This is not true for A since after A -> B the only options available are A -> B -> dab and A -> B -> cB both already starting with terminal symbols on the left.

Trivially the same goes for B as B -> dab and B -> cB are the only options.

Taking a look at C the production C -> cB can't cause any trouble, since the sequence is already starting with a terminal.

But even the second option C -> Ac is harmless, as after C -> Ac -> Bac the only options are C -> Ac -> Bac -> dabac and C -> Ac -> Bac -> cBac, both starting with a terminal symbol again.


Vertical sticks challenge explanation This is a question based on this one

I've also tried this problem but I can't seem to understand Henry's solution to it.

Why is the average distance between the sticks $(n+1) / (k+1)$ and not $n/ k$

Let me first repeat the setting. There are $k$ sticks, one of them distinguished. We randomly choose $k$ different positions for them from $1,\ldots,n$, and put a special stick at $0$. How far to the left of the distinguished stick is the closest stick?

The trick here is to observe that we obtain the same distribution if we first choose positions for the sticks and then permute the $k$ sticks (without changing the set of $k$ positions). This is equivalent to choosing the $k$ positions and then choosing one of the sticks at random as the distinguished one. If the positions are $i_1 < \cdots < i_k$, the average distance to the left is
$$\frac{(i_1 - 0) + (i_2 - i_1) + \cdots + (i_k - i_{k-1})}{k} = \frac{i_k}{k}. $$
Therefore the average distance to the left is $\mathbb{E}[i_k]/k$.

It remains to compute the average position of the maximum of $k$ distinct random positions. There is probably a smart way of doing that; here is a brute force calculation. The number of choices in which the maximum is $\ell$ is exactly $\binom{\ell-1}{k-1}$. Hence the average is
$$
\frac{1}{\binom{n}{k}} \sum_{\ell=k}^n \ell \binom{\ell-1}{k-1} =
\frac{k}{\binom{n}{k}} \sum_{\ell=k}^n \binom{\ell}{k} =
\frac{k}{\binom{n}{k}} \binom{n+1}{k+1} = \frac{k(n+1)}{k+1}.
$$
Overall, we get that the average distance to the left is
$$
\frac{1}{k} \cdot \frac{k(n+1)}{k+1} = \frac{n+1}{k+1}.
$$


find an element in array that appeared at least 51% times Given an array with n rational numbers, element in is array called popular if it have appeared at least in 51% of the indices.

I have to design an algorithm that finds such element in O(n) worst case complexity time, that if there is one.

The only ideas I have is to use hash tables but the complexity time is O(n) in average and counting sort but it only works with natural numbers.

Is there anything I am missing or I can use ?

If element appears more than 50% of time, you can use Median of medians algorithm by Blum et. al. It is not deterministic though.

Or use specialized algorithm by Boyer and Moore called "Majority vote algorithm". It works by keeping counters of seen element, incrementing on the same symbol and decrementing otherwise. If counter drops to zero, the next symbol is picked.

The trick is that number of increments (and decrements for other symbols) will leave the most frequent item at the end. The second pass is required, because algorithm always terminates with some symbol, which is either the most frequent symbol or some random one (if the most frequent item - the mode - occurs below 50%, there is no guarantee it will be returned).

Here is old-school animation of the majority vote algorithm at authors webpage.


what is the general name of this problem? what is the general name of a problems where learning agent observe new data as a learning goes on. For example when playing platformer games one must incrementally learn new level areas and states while remembering all previous states so as to successfully proceed through the level.

The machine learning subfield you are asking about is called Data Stream Mining.

(However I'm not sure about its relationship to platform games)


create divide and conquer algorithm I have to create an algorithm for homework, but cant figure out where to start.

The divide and conquer algorithm muse be O(nlgn) and returns a pair of numbers p and q in an array A. p must appear before q in the array, and q-p must be the highest possible value

heres and example I made up:

A=[1,4,12,5,9,1,3,8]

the return values would be p=1 & q=12

Hint: Divide $A$ evenly into two smaller arrays $A_1,A_2$, and solve the problem (recursively) on $A_1$ and $A_2$. Can that help you find the optimum on $A$? Don't forget you're allowed to use extra processing costing up to $O(n)$.

Another hint: Suppose that $p,q$ is the optimal pair for $A$. Either $p,q \in A_1$, or $p,q \in A_2$, or neither of these cases is true. What can you say in the third case about $p$ and $q$?

As an aside, this can be solved in $O(n)$, in fact even online. We maintain the minimal element seen so far $m$, and the maximum difference $D = q-p$ over elements seen so far. Upon getting a new element $x$, we put $D = \max(D,x-m)$ and $m = \min(x,m)$, and update $p,q$ with $m,x$ if needed.