Baker, Gill, Solovay - construction of oracle B such that P^B != NP^B

As the original paper is showing a lot more, I use this one at page 69-70, Theorem 3.9, as this is the proof I also know.

As you can see there, the complete statement of Baker, Gill, Solovay is:

  There exist oracles $A, B$ s.t. $P^A = NP^A$ and $P^B \neq NP^B$

The second oracle cannot be considered a counterexample for $P = NP$ because you cannot "divide" by B so to say. Constructing a oracle language $L^A$ out of a "normal" language $L$ is not that easy. The languages $P^B$ and $NP^B$ behave completely different than $P$ and $NP$. To show you an example for this: Even if $P=NP$ is true, the statement $P^B \neq NP^B$ is still valid. This shows how different $P,NP$ and $P^B, NP^B$ behave.

  It seems to me that we have constructed a language recognizable in NP time but not in P time.

Be careful here. It is shown that unary language $U_B$ can be recognized by a $NP^B$-TM, not by a $NP$-TM. Again, this is because Oracle-Languages/TMs behave completely different than their "normal" counterparts. If you want to recognize $U_B$ in $NP$ without the oracle, you have to do a lot more work as you could guess a word $w$ of length $i$ in poly. time, but you cannot decide $w \in B$ that easy, as we have no clue by BGS if $B \in NP$ or not.

  And if it is not, can it be strengthened into one?

Maybe yes, maybe not. As this would solve $P=NP?$, which is unknown, it is unknown if you could strengthen it or not.

  In the proof there is the sentence "If $P_i^{B(i)}$ accepts $0^n$, then place no string into B at this stage." How can this possibly happen?

As you just simulate all TMs in $P_i^{B(i)}$ and don't change them, you cannot change whether the TM accepts or not. For example, the TM that accepts all words is in $P$, so it also is in $P^B$, so it will be simulated at some point. Then, your case will happen. Of course, this TM will not call the oracle once.

Edit 3:

Now I want to convince you that your Algorithm does not run in $NP$-time. I can't convince you by now that really $B \not \in NP$, but I think I can convince you now at least that this algorithm does not gives us $B \in NP$.

Let's try to formulate your algorithm as an $NP$-TM that decides $w \in B$ (using original BGS, Theorem 3 now):

Guess $i$ s.t. $M_i^B(1^{|w|})$ is the poly-TM where $n:=|w|$ is choosen. See that $M_i$ has access to oracle $B$. Guessing $i$ is possible because $i\leq n$ as each stage needs a unique $n$. However, can we verify that $i$ is right? To do so, we might have to really build $B$ from stage $i=0$, which would take to long.

2. Simulate $M_i(1^{|w|})$ for $2^n/10$ time. I'm not sure whether we can do this. We don't know if $M_i$ is a poly-time TM, so we can't really guess a polynomial $p : \mathbb{N} \rightarrow \mathbb{N}$  so it could really run for $2^n/10$ time as we enumerate all TM's so e.g. also the $EXP$-hard ones. Can you find a fix for this? If so, I will re-edit this answer to describe the next steps. Using original BGS now:
Simulate $M_i^B(1^{|w|})$ for $p(|w|)$ time. We can guess the polynomial $p$ in $NP$-time. However, can we verify that $p$ is the right polynomial? We cannot assume that it's right and I can't find an easy way to do this. But here comes the problem: Can we really simulate $M_i^B(1^{|w|})$ in poly. time? I want to convince you that this is not the case.

2.1. If $M_i^B(1^{|w|})$ writes $x_B$ on the oracle tape and asks $x_B \in B?$, what can we do in $NP$ without the oracle? We can only start another simulation, guess another $i'$ s.t. stage $i'$ takes $n':=|x_B|$ and simulate $M_{i'}^B(1^{|x_B|})$.

However, how many such new simulations do we have to do in the worst case? $M_i^B(1^{|w|})$ with running time $p(|w|)$ could ask the oracle $p(|w|)$ questions of length $p(|w|)$. Let's look at some arbitrary question at step $j$ now. Let the asked question in step $j$ be $x_B \in B?$. Now, we have to guess $i'$ s.t. $n':=|x_B|$ and simulate $M_{i'}^B(1^{|x_B|})$. Let $p'(|x_B|)$ be the running time of $M_{i'}^B(1^{|x_B|})$. Now, in the worst case, $M_{i'}^B(1^{|x_B|})$ asks the oracle $B$ in every of the $p'(|x_B|) = p'(p(|w|))$ steps again a question of length $p'(|x_B|) = p'(p(|w|))$. And this can go on and on.

In the end, we have build a tree with the vertex degree being $O(p''(|w|))$ for some polynomial $p''$. The depth of this tree can be pretty huge, because $i$ could equal $i'$. Let's assume just for simplicity that in each step $j$ we asked each stage $k \in \{1,\cdots,n\}$ exactly one question. Then we have depth $n$ for each path from the root to some leaf in the tree. Therefore, to answer the initial question $w \in B?$, we have to look at each of the $O(p''(|w|))^n$ verticies. Clearly, this can only be done in exponentioal time and not in polynomial time, because we have a exponention number of vertecies w.r.t $|w|$. Therefore, the algorithm does not run in $NP$-time.


Proving that a sentence in first-order logic is not valid

The completeness theorem states, in an equivalent form:

  If a formula $S$ is not valid, then there exists some model $\cal M$ such that $$ {\cal M}\not\models S$$
  or, equivalently
  $${\cal M}\models\neg S $$

This is simply the contraposative of the completeness theorem, as stated on e.g. wikipedia.

This shows that there is always a "certificate of invalidity" as you ask. This is still true if you ask for $\cal M$ to be countable.

However, obviously there is no procedure to compute $\cal M$, by a straightforward argument involving undecidability of Robinson's arithmetic.

Edit: To answer the question of how one might represent such a counter-model:

Unpacking the proof of the completeness theorem shows that such a certificate can be represented by a Herbrand structure, which are the syntactic terms of the language, possibly augmented with constants and function symbols, and recursively enumerable interpretations for the predicate symbols.

In general however, the interpretation of a formula cannot be decided by such a recursive enumeration (but it can be semi-decided).


Calculate $(u,v) \in \mathbb{R}$ so that $\sum (a_i + b_i)$ with $ a_i \geq u$ and $b_i \geq v$ maximizes

For each pair of elements, $(a_{i},b_{i})$, you can calculate the sum of all the $(a_j+b_j)$ where $a_{j}$ and $b_{j}$ are both greater than or equal to $a_{i}$ and $b_{i}$. So an algorithm could look like:

largest_pair = 0
largest_value = -∞
for each i:
    for each j:
        total = 0
        if(a[j] >= a[i] & b[j] >= b[i])
            total += a[j] + b[j]
    if(total>largest_value)
        largest_value = total
        largest_pair = i
u = a[largest_pair]
v = b[largest_pair]
output u,v

This algorithm is $O(n^2)$ but is easily adaptable to n-variables, and there should be some shortcuts that could speed it up


Key differences between interactive and time sharing operating systems?

Time sharing is a system of multi-tasking designed to allow multiple users to use a single machine at the same time.
A time sharing operating system is one that supports multi-tasking and multi-user.
In a time-sharing system the user typically interacts with the operating system through a secondary machine called a terminal.

In an interactive operating system there is typically only one user on the system that has full control over the system.

Because of the environment in which time-sharing machines are used (large cooperations and banks) security and separation between users is a prime concern.

Interactive computing originates from the hobby and personal computing revolution. Because there is only a single user security was initially not a concern.

From these starting points the lines have blurred.
First single user systems gained multi-tasking and then multi-user concepts were copied over from time-sharing systems into the interactive OS'es.

Meanwhile the security and performance of time sharing systems have also improved.


$T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$

At level 0, the top level, you'll have $1$ array, of size $n$.

At level 1, you'll have $n^{1/2}$ arrays for each array at level $0$, for a total of $n^{1/2}$ arrays, each of size $n^{1/2}$.

At level 2 you'll have $n^{1/4}$ arrays for each array at level 1 for a total of $n^{1/2}n^{1/4}$ arrays, each of size $n^{1/4}$.

At level 3 you'll have $n^{1/8}$ arrays for each array at level 2 for a total of $n^{1/2}n^{1/4}n^{1/8}$ arrays, each of size $n^{1/8}$.

In tabular form we have for the first few levels,
$$\begin{array}{ccccc}
\mathbf{level} & \mathbf{arrays} & \mathbf{size} & \mathbf{contribution/array} & \mathbf{total\ contribution}\\
0 & 1 & n & n\lg n & (1)(n\lg n)=n\lg n\\
1 & n^{1/2} & n^{1/2} & n^{1/2}\lg n^{1/2} & (n^{1/2})(n^{1/2}\lg n^{1/2})=n\lg n^{1/2}\\
2 & n^{1/2}n^{1/4} & n^{1/4} & n^{1/4}\lg n^{1/4} & (n^{1/2}n^{1/4})(n^{1/4}\lg n^{1/4})=n\lg n^{1/4}\\
3 & n^{1/2}n^{1/4}n^{1/8} & n^{1/8} & n^{1/8}\lg n^{1/8} & (n^{1/2}n^{1/4}n^{1/8})(n^{1/8}\lg n^{1/8})=n\lg n^{1/8}
\end{array}$$
So the total runtime, $T(n)$, will be the sum of the contributions at each level, namely
$$
n\lg n + n\lg n^{1/2} + n\lg n^{1/4} + n\lg n^{1/8} +\dotsb
$$
Use a property of the log function and you'll see that this simplifies to a simple expression.


The best book to answer your question would probably be: Cooper and Torczon, "Engineering a Compiler," 2003.  If you have access to a university library you should be able to borrow a copy.

In a production compiler like llvm or gcc the designers make every effort to keep all the algorithms below $O(n^2)$ where $n$ is the size of the input.  For some of the analysis for the "optimization" phases this means that you need to use heuristics rather than producing truly optimal code.

The lexer is a finite state machine, so $O(n)$ in the size of the input (in characters) and produces a stream of $O(n)$ tokens that is passed to the parser.

For many compilers for many languages the parser is LALR(1) and thus processes the token stream in time $O(n)$ in the number of input tokens.  During parsing you typically have to keep track of a symbol table, but, for many languages, that can be handled with a stack of hash tables ("dictionaries").  Each dictionary access is $O(1)$, but you may occasionally have to walk the stack to look up a symbol.  The depth of the stack is $O(s)$ where $s$ is the nesting depth of the scopes.  (So in C-like languages, how many layers of curly braces you are inside.)

Then the parse tree is typically "flattened" into a control flow graph.  The nodes of the control flow graph might be 3-address instructions (similar to a RISC assembly language), and the size of the control flow graph will typically be linear in the size of the parse tree.

Then a series of redundancy elimination steps are typically applied (common subexpression elimination, loop invariant code motion, constant propagation, ...).  (This is often called "optimization" although there is rarely anything optimal about the result, the real goal is to improve the code as much as is possible within the time and space constraints we have placed on the compiler.)  Each redundancy elimination step will typically require proofs of some facts about the control flow graph.  These proofs are typically done using data flow analysis.  Most data-flow analyses are designed so that they will converge in $O(d)$ passes over the flow graph where $d$ is (roughly speaking) the loop nesting depth and a pass over the flow graph takes time $O(n)$ where $n$ is the number of 3-address instructions.

For more sophisticated optimizations you might want to do more sophisticated analyses.  At this point you start running into tradeoffs.  You want your analysis algorithms to take much less than $O(n^2)$ time in the size of the whole-program's flow graph, but this means you need to do without information (and program improving transformations) that might be expensive to prove.  A classic example of this is alias analysis, where for some pair of memory writes you would like to prove that the two writes can never target the same memory location.  (You might want to do an alias analysis to see if you could move one instruction above the other.)  But to get accurate information about aliases you might need to analyze every possible control path through the program, which is exponential in the number of branches in the program (and thus exponential in the number of nodes in the control flow graph.)

Next you get into register allocation.  Register allocation can be phrased as a graph-coloring problem, and coloring a graph with a minimal number of colors is known to be NP-Hard.  So most compilers use some kind of greedy heuristic combined with register spilling with the goal of reducing the number of register spills as best as possible within reasonable time bounds.

Finally you get into code generation.  Code generation is typically done a maximal basic-block at a time where a basic block is a set of linearly connected control flow graph nodes with a single entry and single exit.  This can be reformulated as a graph covering problem where the graph you are trying to cover is the dependence graph of the set of 3-address instructions in the basic block, and you are trying to cover with a set of graphs that represent the available machine instructions.  This problem is exponential in the size of the largest basic block (which could, in principle, be the same order as the size of the entire program), so this is again typically done with heuristics where only a small subset of the possible coverings are examined.


I think you're trying to take too many steps at once. Try to think about it one small step at a time.

Always think about:

What are the definitions I have available
What do I know already? What is proven?

Proving sets equal

Since you have two sets, $\Omega(cf)$ and $\Omega(f)$ and you want to prove them equal, you first need to think about what it means for two sets to be equal:

$$A = B \Longleftrightarrow A \subseteq B \land A \supseteq B$$

This tells you, that you need to show two things:

$\Omega(cf) \subseteq \Omega(f)$
$\Omega(cf) \supseteq \Omega(f)$

Proving $A$ to be a subset of $B$

For this, you need to apply the definition of $A \subseteq B$:

$$ A \subseteq B \Longleftrightarrow \forall a  \in A:(a \in B)$$

Nature of our proof

As you can probably see by now, our proof will have the following form:

$$\begin{align*}"\subseteq":\\ & \text{Let } g \in \Omega(cf):\\
&\Rightarrow \dots\\
&\Rightarrow g \in \Omega(f)
\end{align*}
$$

The proof goes the same way for $"\supseteq"$.

Filling in the dots

Keeping this structure in mind, the path you need to follow is already laid out.

Using this definition for \Omega: $ \Omega(f) = \{ g |\, \exists\, n_0 \in \mathbb{N}, c > 0 \forall n \geq n_0: cf(n) \leq g(n) \} $

One direction of the proof could look as follows:

$$\begin{align*}"\subseteq":\\ & \text{Let } g \in \Omega(cf): \\
&\Rightarrow \exists\, n_0\in \mathbb{N}, c'>0: c'cf(n) \leq g(n)\ \ \forall n \geq n_0 &\text{definition of } \Omega\\
&\Rightarrow \exists\, d>0,  n_0\in \mathbb{N}: d f(n) \leq g(n)\ \ \forall n \geq n_0 &\text{Let } d=c'c\\
&\Rightarrow g \in \Omega(f) &\text{definition of } \Omega
\end{align*}
$$


Count numbers that can be generated by flipping bits according to position intervals

Hint: For given $N$ and a range $[L,H]$, let $v \in \mathbb{Z}_2^N$ be the characteristic vector of $[L,H]$, i.e. $v_i = 1$ if $L \leq i \leq H$ and $v_i = 0$ otherwise. Given a list of ranges $[L_j,H_j]$ and correspond vectors $v_j$, how can you represent the characteristic vectors of all numbers reachable by the operations you mention? What is the relevant parameter?

Another hint: What happens if all $L_i$ are distinct? How can you handle cases in which $L_i = L_j$ for some $i \neq j$? Try to reduce it to the former case.


Implementing reliable pairwise average in distributed systems

Full reliability is simply not possible in (distributed) systems; at some point of fractional system failure you reach a level where system state and/or data is no longer recoverable. You should consider that this is dependent not only on node failure, but also on data distortion (bits might flip as they travel across the network, etc.). As a result, you can reach very high levels of certainty about correctness but it's very difficult if not impossible to guarantee it.

One of the most well known examples of this is the Byzantine Generals/Byzantine Fault problem, which deals with consensus in networks (https://en.wikipedia.org/wiki/Byzantine_fault).


Help with question from Sipser chapter 1

I think I finally understood the concept.

This:

$A =\{0^ku0^k  \ | \ k \ge 1 \ and \ u \in \sum^*$}.

Means that A has strings that starts and ends with the same number of zeros.

For example, the string:

$0000000100$

Is recognized by A because:

$00|000001|00$

In the middle we can put any number of zeros and shrink the zeros at the edges.

$0^k10^k$ is another language that contains strings with equal number of zeros at the beginning and end separated by a 1. In this case, string from this language are accepted by the the first one but that doesn't means that the second language could be regular.


Difference between large-scale optimization and equation-based simulation

AMPL and Modelica are modelling languages, not a solver or optimization algorithm.  So, you don't use AMPL or Modelica to solve some optimization problem: you express the problem in AMPL or Modelica, then you use some other solver to find the optimal solution.

AMPL tends to be used for problems that can be solved with optimization methods: e.g., linear programming, integer linear programming, quadratic programming, convex optimization, that sort of thing.  Modelica seems to be used for problems that can be solved by solving differential equations or by using hybrid model-checking.

Modelica is for modelling how some continuous variables change over time.  Contrary to what you wrote, there's no simple way to model in that in AMPL by "adding a time variable".  To put it another way: Modelica lets us model, say, the position of a component as a function of time.  This is a function $f(t)$.  AMPL lets us model, say, the position, as a fixed continuous value.  This is a value $x$.  Adding a second variable $t$ still doesn't give you any way to model a function of $t$.

So, the two approaches are for modelling different kinds of problems; and typically they're used with different kinds of back-end solvers, which use different techniques.  They're not interchangeable.

Disclaimer: This is all based on my (rather limited) understanding of these systems.


Yes and no. Arguably, the lock is not a finite state machine, since the key can be inserted to any degree and, if it fits, rotated through any angle. However, we can abstract away these unimportant details, yes, the system can be modeled as a finite number of states: essentially, if you code up the ridges of the key as symbols in some alphabet, the lock is a DFA that accepts exactly one word (or perhaps more, if there's a master key).


How to prove certain parts of one regular language restricted by another regular language is also regular?

Let me point you to the proper tools.

The operation of (perfect) shuffle takes two languages $K,L\subseteq \Sigma^*$ and alternatingly takes a symbol from one of them:

$sh(K,L) = \{ a_1b_1a_2b_2 \dots a_kb_k\mid k\ge 0, a_i,b_i\in\Sigma,\text{ where }  a_1a_2\dots a_k\in L\text{ and } b_1b_2\dots b_k\in K  \}$

This operationhas been discused various times, using both automata and closure properties:
Proving regular languages are closed under a form of interleaving,
Show that regular languages are closed under Mix operations, and
Closure of regular languages to shuffle using closure operations, but probably more.

Then there is the kind-of reverse of this operation, given a language $K\subseteq \Sigma^*$, keep every second letter of its strings:

$2nd(K) = \{ a_2a_4 \dots a_{2k} \mid k\ge 0, a_i\in\Sigma,\text{ for some }  a_1a_2\dots a_{2k}\in K  \}$

An example for that is is:
If L is regular, show that even(L) is also regular. Both solutions there are enlightening.

Also in your case one needs some shuffling (to move the letters from $L_2$ within two other letters in order to compare with $L_1$) and some unshuffling (to keep every first letter of three for $L^{\land}$) but now with three letters/languages rather than two.


What's the decoding time complexity of LT codes?

The approach you describe can be implemented to run in linear time.

Build a bipartite graph where left-vertices are blocks and right-vertices are packets, and with an edge from block $b$ to packet $p$ if $b$ is one of the blocks xor-ed to create $p$'s message.  Store the bipartite graph in adjacency list format.  Also keep track of the degree of each packet, so given a packet $p$ you can compute its degree in $O(1)$ time.

Then it's easy to implement the algorithm you describe in $O(n)$ time, using a worklist algorithm.  The worklist is a list of all packets of degree one.  In each iteration, you remove a degree-one packet $p$ from the worklist, then process it as follows.  Find the corresponding block $b$, then find all other packets $p'$ containing the block.  Xor $b$ into $p'$, and delete the edge $(b,p')$ (and update the degree of $p'$).  This can be done in $O(1)$ time.  If the new degree of $p'$ is 1, add $p'$ to the worklist.  Repeat until the worklist is empty.

The running time is $O(1)$ per edge in the bipartite graph, i.e., $O(m)$ time where $m$ counts the number of edges in the graph (the sum of degrees of all of the packets).


Is per-record timeline consistency is somehow equivalent to causal consistency?

You may know that per-record timeline consistency is used in PNUTS: Yahoo!’s Hosted Data Serving Platform:

  We provide per-record timeline consistency: all replicas of a given record apply all updates to the record in the same order.

Answer your questions:

  Since all modifications to a specific primary key are causally related (a client reads it, then modifies or delete it), ...

They are actually totally (or sequentially) ordered, stronger than "causally related".

  ... then per-record timeline consistency is somehow equivalent to causal consistency.

Given the reason above, per-record timeline consistency is more like sequential consistency (wiki). In fact, per-record time consistency is also called per-key sequential consistency, which is stronger than per-key causal consistency. Because sequential consistency is not local, per-key sequential consistency is not equivalent to (i.e., weaker than) sequential consistency defined over multiple keys.


Is any State Space Tree always Binary Tree?

Think about the chess problem or more simple 8-Queen problem are Tic Tac Toe game. The states are not binary trees. As seen from Quoara  ;

  A state space tree is a tree constructed from all of the possible states of the problem as nodes, connected via state transitions from
  some initial state as root to some terminal state as a leaf.


Pumping lemma regular language can't be pumped

Have a look at the exact wording of the pumping lemma: It has a precondition that only words exceeding a certain size need to be pumpable. This is exactly so that only words with repetitions have to be pumpable.

For your language (and every other finite one) you can simply set that size beyond the maximum word size (e.g. at 4). No words are longer than that, and all of them can be pumped.


The reason is easier to see when you figure the big-$\mathrm O$ of the loop and the recursion (last line) separately and then add them. The loop takes $\mathrm O(n^2)$ time, and the recursive part takes twice the time of $f(n/2)$.

So we get
$$\mathrm{time} (f(n))=\mathrm O(n^2 + 2\mathrm{time}(f(n/2)))\tag a$$

and we can simplify this  by noticing that this will form a geometric sequence.

$$ = \mathrm O(n^2+2\left(n/2\right)^2 + 4\mathrm{time}(f(n/4)))\tag b$$
$$ = \mathrm O(n^2 + 2(n/2)^2 + 4(n/4)^2 + 8\mathrm{time}(f(n/8)))\tag c$$
$$= \mathrm O\left(\sum_{i=0}^{\inf} \frac{n^2}{2^{i}}\right)\tag d$$
$$= \mathrm O\left( n^2\sum_{i=0}^{\inf}\left(\frac{1}{2^{i}}\right)\right)\tag e$$

$\sum_{i=0}^{\inf}\left(\frac{1}{2^{i}}\right)$ on line $\mathrm (e)$ converges to a  nonzero value that is not dependant on $n$ (specifically, $2$), so it can be removed from the $\mathrm {O}()$, to give just $\mathrm O(n^2)$

Note that this way of solving (leaving constant factors and ignoring the base case of recursion) will not work for all problems.

For example what if the inner loop had time complexity $\mathrm O(n)$? $$\mathrm{time}(f(n)) = \mathrm O(n + 2\mathrm{time}f(n/2)) = \mathrm O(n + 2\frac{n}2+4\mathrm{time}f(n/4)) = ...$$ which would give $\mathrm O\left( n^2\sum_{i=0}^{\inf}1\right)$, which is obviously not correct because it diverges.
However, if we ingore the constant factor of 2, we get
$$\mathrm{time}(f(n)) = \mathrm O(n + \mathrm{time}f(n/2)) = \mathrm O(n + \frac{n}2+\mathrm{time}f(n/4)) = ...$$ which gives $\mathrm O\left( n^2\sum_{i=0}^{\inf}\frac1{2^n}\right)$, which converges to $2$

-- End note


Linear programming with inequality constraints treated lexicographically

If you want to have only initial constraints to be strictly equal and rest of them should be strictly less

First, add regular constraints:
$$
A_i x \le b_i
$$
Next, add checks for equality as in https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/ :
$$
e_i = A_i x \stackrel{?}{=} b_i
$$
Finally, we want only some initial of these variable to be true, and for that we can use material implication as in https://blog.adamfurmanek.pl/2015/08/22/ilp-part-1/ :
$$
e_{i+1} \implies e_i = 1
$$
or we can simply add the following constraints:
$$
e_{i+1} \le e_i
$$

Disclaimer: I am the author of the blog posts but I don't want to advertise here, only include them as a reference.

If you want some initial of the constraints to be strictly equal, the next one should be strictly less, and rest of them can be not satisfied

Do not add any regular constraints.

Create equality constraints as before:
$$
e_i = A_i x \stackrel{?}{=} b_i
$$

Calculate prefix conjunction of equality constraints:
$$
E_i = e_1 \wedge e_2 \wedge \ldots \wedge e_{i}
$$

Variables $E_i$ indicates whether first $i$ constraints are strictly equal.

Next, calculate less than constraints:
$$
l_i = A_i x \stackrel{?}{<} b_i
$$

Finally, make sure that after $i$ initial strictly equal constraints there is a strictly less constraint or another strictly equal constraint satisfied:
$$
E_i \implies \left( l_{i+1} \vee E_{i+1} \right) = 1
$$


how to prove that nlogn is not Θ(n) without using limits?

Remember that $f \in \Theta(g) \iff f \in O(g) \land g \in O(f)$, so $f \notin \Theta(g) \iff f \notin O(g) \lor g \notin O(f)$.

One definition of big-O notation that doesn't use limits is

$$
f \in O(g) \triangleq \exists c, N, \forall n > N, f(n) < c \cdot g(n)
$$

The negation is logically equivalent to

$$
\lnot (\exists c, N, \forall n,  n > N \implies f(n) < c \cdot g(n))\\
\lnot (\exists c, N, \forall n,  \lnot (n > N) \lor f(n) < c \cdot g(n))\\
\forall c, N, \lnot (\forall n,  \lnot (n > N) \lor f(n) < c \cdot g(n))\\
\forall c, N, \exists n, \lnot (\lnot (n > N) \lor f(n) < c \cdot g(n))\\
\forall c, N, \exists n, \lnot \lnot (n > N) \land \lnot (f(n) < c \cdot g(n))\\
\forall c, N, \exists n > N, \lnot (f(n) < c \cdot g(n))\\
\forall c, N, \exists n > N, f(n) \geq c \cdot g(n)\\
$$

So, to show that $n \log n \notin \Theta(n)$, you'll want to find a witness $n$ that will be based on a $c$ and $N$ that are abstract, and show that $n \log n \geq c \cdot n$.

Here is an example with some other functions:

Claim: $n^2 \notin O(n)$.

Proof:
Given $c$ and $N$ as above, let

$$n \triangleq \begin{cases}
c & N < 1\\
N c & N \geq 1.
\end{cases}$$

In the first case, $n^2 = c^2 \geq c \cdot c = c \cdot n$.

In the second, $n^2 = N^2 c^2 = N (N c^2) \geq N c^2 = c (c N) = c \cdot n$.

I won't do the example with $n \log n$, because I'd like you to see the principle and I don't want to accidentally do you homework.


How to approach NFA design questions intuitively?

There is one sentence in your question that is worth answering:

  I just want to know , how one can develop an intuition for solving the problems?

Same thing everybody does, be is musicians, crafts men or scientists: exercise. There is no shortcut.

You can certainly use the growing database of finite-automata questions we have here. There is little use in repeating techniques here as they more often than not depend on the concrete example.

For regular languages in particular, you can devise any formal representation of the language as long as the model is equivalent to regular languages. There typically are (computable) methods to transform such representations (e.g. regular expression) to finite automata.


Finding closest line segment intersecting rays

You'll need two data structures - for vertical rays and for horizontal rays. I'll describe a data structure for vertical rays. Draw a vertical line through each segment end - you'll get a set of vertical slabs. Each of these slabs will be divided by pieces of original segments into trapezoids (possibly infinite ones).

Number of these slabs will not exceed $2n$, and number of trapezoids in each slab will not exceed $n$. In order to find a segment, closest to the query point along a vertical ray (going up or down), you need to use binary search to find a slab at first, and then - another binary search to find a trapezoid inside the found slab. Upper and lower boundary of this trapezoid will give you the answer. These two binary searches will take $O(log(n))$ time.
The data structure for horizontal rays is similar - the only difference is that slabs should be horizontal.


dynamic programming: longest palindromic subsequence, recurrence relation question

Let T(i,j) = T(i,j-1) when L(i) != L(j)
You could be wrong if you take T[0, n-1] as the final answer as in the article on GeeksforGeeks. For example, let X = "abb". Then T[0, n-1] = 1 while the longest palindromic subsequence is bb with length 2.
You are right if you take the maximum of T[i,n-1] as the final answer, where i goes through all valid indices, i.e., from 0 to n-1 and n is the length of the given string X.
What is happening?
We need to understand/specify the meaning of T(i,j). We can let T(i,j) denote the length of the longest one among all subsequences that start at index i and end no later than index j, where i <= j. Then it is correct that T(i,j) = T(i,j-1) when X(i) != X(j), since any palindromic subsequence that start at index i cannot end at index j, i.e., it must end no later than index j-1.
Exercise

Describe the meaning of L(i,j) in that GeeksforGeeks article.

Suppose we let T(i,j) denote the length of the longest one among all subsequences that start at index i and end at index j, where i <= j.

What will be the recurrence relations?
Suppose we have computed all T(i,j). What would be the final answer, i.e., the length of the longest palindromic subsequence overall?


Language of Turing machines that loop on all inputs, recognizable?

$L$ isn't recognizable. We'll first establish a couple of preliminary results

I. $\overline{L}$ is recognizable

The complement of $L$,
$$
\overline{L}=\{\langle M\rangle\mid M \text{ halts on at least one input}\}
$$
is recognizable. Define a recognizer TM as follows:

R(<M>) =
   for n = 1, 2, 3, ...
      for each x in {x_1, x_2, ... , x_n}   // in some canonical order
         run M on x for one move
         if M halts
            return accept

It should be clear that $R$ accepts all and only those $\langle M \rangle$ for which $\langle M \rangle\in \overline{L}$ and so $\overline{L}$ is recognizable. Now if $L$ were also recognizable, then we could use the two recognizers to make decider for $L$, which brings us to our second result.

II. L is undecidable

If $L$ were decidable, then $\overline{L}$ would also be, and conversely. If that were the case, we could define a reduction from the known undecidable language
$$
HALT = \{(\langle M\rangle \mid M \text{ halts on input }w\}
$$
to $\overline{L}$ by the mapping
$$
(\langle M\rangle, w)\rightarrow M_w
$$
where, as babou has already noted,

M_w(y) =
   erase the input y
   write w on the input tape
   simulate M on w

Now observe that $M$ halts on $w$ $\Longleftrightarrow$ $M_w$ halts (on every input $y$, in fact) $\Longleftrightarrow$ $M_w\in \overline{L}$. In summary, if $L$ were decidable, then we could $L$'s decider (reversing the roles of accept and reject) to decide the halting problem, a contradiction.

Now we can show that $L$ is not recognizable. If it were, then, using (I) we could conclude that $L$ was decidable, a contradiction to result (II).


Partitioning connected graphs in the plane

This is not a full answer to your question, but at least you'll have something working.

Step 1. Calculate minimal bounding axis-aligned boxes for each connected component, and also a minimal "outer" bounding box for all the components.

Step 2. Try to split the outer bounding box by horizontal or vertical segment in such a way that this segment doesn't intersect with any bounding boxes for components - this can be done by analyzing coordinates of bounding boxes only. If that is not possible then split the outer box in halves horizontally or vertically. After splitting recalculate bounding boxes for components which were split as well.

Step 3. Repeat the Step 2 recursively for each box, which contains more than one component.

Step 4. After the Step 3 you'll have a partition of the original outer box into rectangles, each of which contain only one connected component (or part of it). Remove all the edges in this partition, for which both adjacent rectangles contain the same component. After this step you'll have a partition of the outer box, but it won't be a optimal one, and it'll consist of axis-aligned segments only.

Step 5. Amend the partition, replacing axis-aligned segments by arbitrary segments, trying to minimize the total number of segments - I don't know how to do that regularly for now.


I will prove it is NP-hard leaving the proof that it is in NP to you.

Let $\phi = c_1\land c_2\dots\land c_m$ be a 3SAT formula. Define
$$S = \{l \mid l \text { is a literal of  } \phi \}$$
$$S_i = \{l \mid l \text { is a literal of } c_i\}$$

Since each clause has to have at least one literal with TRUE value we have the following constraints
$$l_i=1 \leq |T \cap S_i|\leq 3 = h_i$$
Finally, we have to make sure that $T$ contains no variable $x$ (of $\phi$) and its negation at the same time
$$S_{x} = \{x,\overline{x} \} $$
$$l_x=0\leq |T \cap S_x| \leq 1=h_x$$

So, if $\phi$ indeed has a solution then $T$ consists of those literals whose true-value is TRUE. Then it is trivial that all constraints satisfy since $T$ may not have a variable and its negation at the same time and each clause has at least one TRUE literal.

On the other hand, if we have a set $T$ satisfying the above-described constraints then $\phi$ can be constructed by ORing each literal in $S_i$ (by ORing with arbitrary variables if $|S_i| < 3$) and ANDing all clauses corresponding to $S_i$. This formula is satisfiable since may make each clause TRUE by making true each literal in $S_i$ and since not $x$ and $\overline{x}$ are in $T$.


Isn't this Commentz-Walter algorithm buggy?

I figured it out, you have to reset v to root at the same time as you reset j to 0 (in fact if you just add depth to your node, you can skip j and just use v.depth)


How do I prove that all primitive recursive functions are computable?

You prove it by structural induction over the definition of primitive recursive functions. The definition of computable is: a function is computable if it is computable by a Turing machine. There are many other equivalent definitions.


Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor

$ T(n) = 25T(n/5) + 20(n\log n)^{1.99} $

Note that $(\log n)^m=O(n^\epsilon)$ for all $m,\epsilon\in \Bbb R^+$. In plain words, all polynomials of $\log n$ grows slower asymptotically than all polynomials of $n$. Here we abuse "polynomials" to include functions like $x\to x^k$ for all $k\in\Bbb R^+$ such as $x\to x^{0.618}$ or $x\to x^{2019.46}$. This abuse of the term "polynomial" is common when we are talking about the asymptotic behavior of functions.

In particular, $(\log n)^{1.99}=O(n^{0.005})$.

Since $(n\log n)^{1.99}=n^{1.99}(\log n)^{1.99}= O(n^{1.995})=O(n^{log_525-0.005})$, you can apply the case 1 of Master theorem. $T(n)=\Theta(n^2)$.

If $f(n)$ is indeed smaller or larger than $n^{\log_b a}$by less than a polynomial factor, then we are running into the cases strictly between case 1 and case 2 or between case 2 and case 3. The master theorem you were reviewing cannot be applied any more.

You may look into this answer that handles some of those situations.

Exercise. Show that $(\log n)^m=O(n^\epsilon)$ for all $m,\epsilon\in \Bbb R^+$. (For example, $(\log n)^{10000000}=O(n^{0.000001}).$)


Why does the insertion-sort algorithm have a quadratic instead of a quasi-linear time complexity?

On an array of length $n$ which is reversely sorted, the first element would be compared to 0 elements, the second element to 1, the third element to 2, and so on. In total, the number of comparisons will be
$$
0 + 1 + 2 + \cdots + (n-1) = \\
\frac{1}{2} \bigl((0 + 1 + 2 + \cdots + (n-1)) + ((n-1) + \cdots + 2 + 1 + 0)\bigr) = \\
\frac{1}{2} \bigl((0 + (n-1)) + (1+(n-2)) + (2+(n-1)) + \cdots + ((n-1)+0)\bigr) = \\\
\frac{1}{2} \bigl(\underbrace{(n-1) + (n-1) + (n-1) + \cdots + (n-1)}_{\text{$n$ times}}\bigr) = \\
\frac{n(n-1)}{2}.
$$
This number scales like $n^2$.


Some partial idea: You want to avoid a situation where the user receives the file and claims they didn't.

Bob adds some random padding to the file so that the user doesn't know the size. Bob sends part of the data and waits for a receipt, then sends more data and waits for a receipt. When the file is sent completely, the user doesn't know this. So refusing to send the receipt means they might never get the complete file. When Bob claims the whole file has been received, the user contacts Alice, who has a key to unlock the file.


How to purge a linked list in $\mathcal{O}(n\log n)$ time?

You can do it in $O(n)$ as follows.

1) Build an hash table by traversing the linked list and adding its elements to the hash table. In each iteration, search the hash table for the current element being considered in the iteration. If the element is not found, add to the hash table the element value as the key, and 1 as the corresponding value. If you instead find the element (which has been inserted in a previous iteration), you simply add 1 to the corresponding value and update the hash table entry (correctly updating the element multiplicity). At the end, your hash table will contain at most $n$ entries (this corresponds to the case that the element in the linked list are distinct), or less than $n$ elements, with at least one of the entries showing a multiplicity greater than one. This takes $O(n)$ time since in each of the $n$ iterations the work done on the hash table is $O(1)$.

2) Now, traverse the hash table and build a new linked list by adding a node for each element found. this takes at most $O(n)$ since the hash table contains at most $n$ elements, the work done on each element of the hash table is $O(1)$ and adding a node to the new list takes $O(1)$.

Therefore, the total complexity is at most $O(n)$.


Bucket sort has uniformly distributed data

Bucket sort will be slower if the data distribution is highly non-uniform.  The primary advantage of bucket sort over other sorting algorithm is that it is faster when the data is uniformly distributed; so if the data is highly non-uniformly  distributed, the advantages of bucket sort may evaporate.


Algorithm deciding if a radius of a graph is two

Yes. Given the adjacency matrix representation of a graph, computing its second power will allow you to see what nodes are connected by a path of length at most 2. The fastest known matrix multiplication algorithm is $O(n^{2.373})$, which is better than the $O(VE)$ you would get from doing BFS on each node.


Euclidean Steiner Tree Question in Approximation Algorithms

Hint 1: If there is a vertex that violate this condition, say a degree 3 vertex, take this vertex out. Now there are three vertices that have lost an edge remaining. Construct the Euclidean ST for these three points and add it back. Obviously your new solution cant be worse than what you head before. Now it remains to check that for 3 arbitrary points in the plane, the Euclidean ST fulfills the angle criterion mentioned in your question.

Hint 2: For a higher degree $v$, replace two consecutive edges $(v,u_1), (v,u_2)$ by the Euclidean ST spanned between $v,u_1,u_2$.


Schedule Optimization With Priority and Weighted Costs

We can construct a directed graph with events as vertices, where an event $E_2$ has an incoming edge from another event $E_1$ if starting from $E_1$, we can arrive $E_2$ in time to get its reward. The edge value is the time difference between the events.
For each vertex (event), we do a depth first search rooted at this vertex where on each iteration we add the value of the previous tree edge to the current tree edge and check to see if it is greater than the time associated with the current vertex. If it is then our considered sequence of events from the root vertex has just timed out.
var MaxReward = 0
var bestItinerary = []

f(graph):
  for vertex v in graph:
    _f(v, v.time, 0, [])

_f(v, curr_time, rewardSoFar):
  if time > v.time:
    if rewardSoFar > MaxReward:
      MaxReward = rewardSoFar
      bestItinerary = itinerarySoFar
  else
    rewardSoFar = rewardSoFar + v.reward
    itinerarySoFar.append(v)
    for edge, neighbor in v.getNeighbors:
      _f(neighbor, curr_time + edge.value, rewardSoFar, itinerarySoFar)


Yes. Here is the idea.

If $f(n) = \Theta(g(n))$ then there exist constants $C_1,C_2>0$ such that for large $n$,
$$ C_1g(n) \leq f(n) \leq C_2g(n). $$
Now consider the two recurrences
$$
T_1(n) = aT_1(n/b) + C_1g(n) \\
T_2(n) = aT_2(n/b) + C_2g(n)
$$
Choosing suitable initial conditions, you can prove inductively that
$$
T_1(n) \leq T(n) \leq T_2(n).
$$
You consider a regime in which applying the master theorem gives you that $T_1(n) = \Theta(g(n))$ and $T_2(n) = \Theta(g(n))$. It follows that $T(n) = \Theta(g(n))$.


efficient algorithm for min cut with specified number of vertices

For $n= \frac {|V|} 2$, it's called Minimum Bisection, and it's NP-hard. There exists an $O(\log^{3/2} n)$-approximation: "A polylogarithmic approximation of the minimum bisection".
If you are interested, the more general problem is splitting into multiple components of the same size, and it is called Balanced Graph Partitioning. For more than 2 parts no finite approximation exists unless P=NP: "Balanced Graph Partitioning" (Andreev, Rakke), since you can't efficiently check if the answer is 0.
If the parts are not necessarily exactly balanced (a small imbalance is allowed), an $O(\log n)$-approximation algorithm exists: "Balanced Partitions of Trees and Applications".

Some algorithms (also check https://en.wikipedia.org/wiki/Graph_partition and "references" sections of the following papers):

Local search with various flavors: we start with some partitioning and then try to swap vertices between parts to minimize the cut. E.g. we compute "gain" for each vertex (improvement if we move it to another part), and swap vertices with the maximum gain. Its advantage is that you can apply it after any other algorithm.

Spectral partitioning (see e.g. Spectral Graph Theory and Graph Partitioning): uses the second eigenvector of a Laplacian matrix to approximate the partitioning (e.g. by moving the smallest $|V|/2$ coordinates to the first part). Works surprisingly well. However, I'm not sure it can be adapted to the case when you want an unbalanced bisection (e.g. $1:2$ instead of $1:1$).

Linear embedding: "Distributed Balanced Partitioning via Linear Embedding". We embed vertices into a one-dimensional array while minimizing sum over all pairs of vertices: the distance between them multiplied by the weight of their edge. Then we just split this array into consecutive chunks of required sizes. Didn't work that well in my experience.

(Ads) Our paper: "Multi-Dimensional Balanced Graph Partitioning via
Projected Gradient Descent", where we used gradient descent to find minimum bisection: for each vertex we introduce a variable which roughly represents a probability that the vertex belongs to the first part, and minimizing the cut reduces to constrained optimization of a quadratic function. It's a bit outperformed in practice by a fine-tuned local search, but it works really well when you have multiple balance constraints.

Aside from the spectral method, all of them can be trivially adapted to partitioning the graph in arbitrary proportions.
There are also standard solvers: KaHIP, METIS. In my experience, KaHIP was pretty good. I'm not sure they support splitting into parts of arbitrary sizes though.


Which language is accepted by this Muller Automaton?

The solution given is incorrect.

The first clue that this might be the case is that $(a+b)^*(a+b)^\omega$ is a strange way to write anything: any finite number of $a$s and/or $b$s, followed by infinitely many $a$s and/or $b$s is just infinitely many $a$s and/or $b$s, so the given language is just a strange way of writing $(a+b)^\omega$.

Muller automata accept if the set of states visited infinitely often is one of the specified sets.
To see that the automaton doesn't accept $(a+b)^\omega$, consider the word $a^\omega$. This is a member of $(a+b)^\omega$ but it's not accepted by the automaton, since the run on that word visits every state infinitely often, and $\{p,q,r\}$ is not an accepting set.

If exactly two of the automaton's states are visited infinitely often, then there must be a point at which the third state is never visited again. From that point onwards, the automaton can only alternate between the remaining two states, so any accepted word must end $(ab)^\omega$. While the automaton is still visiting all three states, it can read in any word so, yes, the accepted language is $(a+b)(ab)^\omega$.


Differences between Fuzzy C-Means and EM

The difference between the two schemes is the model of the clusters. Fuzzy C-means and K-means model their clusters as circles (spheres in n-dimensional space), EM-clustering models the clusters as probability density functions (PDFs). In Euclidean space, the latter can have elliptical shapes (using Gaussian PDFs), determined by their covariance matrices.

Thus the difference is that the assignment criterion for K-means is the distance to a centroid whereas the criterion for the EM-algorithm is the probability of a data point given the PDF of the cluster center.

The cluster centers in K-means are hard-assigned, in Fuzzy C-means they are not; but it is rather simple to get a hard decision by, as you stated, taking the cluster with the highest probability/smallest distance for a given data point.


Combining merge sort with insertion sort - Time complexity

For your first question:
O(n logn) might be 4nlogn or 13nlogn or 0.1nlogn etc.

If you compare 4n^2 and 100nlogn you will see that for n < about 200 the O(n^2) is faster. Big O is an asymptotic measure. It says what happens when n approaches infinity, but does not say anything about “smaller” inputs.

For your second question:
You have n/k sublists. Each sublist has length k and needs k^2 to be sorted with insertion sort. So multiply and you get n/k * k^2 = nk worst case. This is a way of parametrizing your algorithm’s complexity. If you choose k to be a constant c ex. k = 3 then you have n/3 sublists of length 3. Each one needs 3^2 = 9 execution steps and the overall amount of work is n/3 * 9 = 3n. You can also choose k to be a function of n, ex. k = f(n) = n/5. Then you have n/(n/5) = 5 sublists of length n/5. Each sublist needs (n/5)^2 = n^2/25 execution steps and the overall amount of work is 5 * n^2 /25 = n^2 / 5. Again, don’t assume that the one is faster than the other. n^2 / 5 and 3n describe “the same thing” written differently.

Finally, keep in mind that big O describes neither time nor space. It describes amount of work it needs to be done. If you take account the parallelization then for example assuming an ideal choice of pivots, parallel quicksort sorts an array of size n in O(n log n) work in O(log² n) time using O(n) additional space.

Some algorithms can be parallelized and some others can’t. Insertion sort for example is CPU favorable when the input size is comparable to the “block size” of the CPU. Divide and conquer algorithms are not fast for small inputs because the cpu must populate the code recursively. This means lot of memory to be allocated, lot of stacks, etc

The approach you are describing is a hybrid algorithm.


What factors of the integer dataset being sorted can I change, in order to compare two sorting algorithms?

The simplest is not doing a proper shuffle, that is having partially (reverse) sorted sequences, in extremis this can be the entire range is sorted except a few elements at the end that need to be inserted somewhere in the range.
For comparison sorts the distribution of elements doesn't make a difference, only how many duplicate values there are. This is something you can adjust as well.


Why this problem has such a simple solution? How would you avoid looking for more complex solutions first?

In this case: It is obvious that you start with some task immediately, start a second task as soon as the first task is finished, then start a third task immediately after this etc.
It is obviously that you can swap the order of two consecutive tasks without affecting any other task. In an optimal solution, swapping the order of two consecutive tasks cannot improve the solution.
Now you look for a criterion when swapping two tasks would improve the solution. For an optimal solution, that criterion must fail for any two consecutive tasks. And lucky enough there is a simple criterion.
So any problem where tasks must be performed consecutively, and where swapping two tasks doesn't affect all the other tasks, you can solve if you can determine which order of the two tasks is better.
This doesn't work for the travelling salesman problem for example, because swapping two cities affects other cities as well.


Can anyone tell me why this search parition for quicksort works?

sortFirstMiddleLast() sorts the first, middle, and last elements in-place. Once that's done, there's no need to consider the first or last value because (if the middle value is used as the pivot) they're known to be correctly partitioned.


No, there are no guarantees.  SGD finds a local optimum but not a global optimum, and the solution it finds can be arbitrarily bad, if you have an unfriendly objective function.
The only results I've seen that provide guarantees start from strong assumptions about the objective function (e.g., convexity).


ML functions from polymorphic lists to polymorphic lists

Well, something known as parametricity tells us that if we consider the pure subset of ML (that is, no infinite recursion, ref and all that weird stuff), there is no way to define a function with this type other than the one returning the empty list.

This all started with Wadler's paper “Theorems for free!”. This paper, basically, tells us two things:

If we consider programming languages that satisfy certain conditions, we can deduce some cool theorems just by looking at the type signature of a polymorphic function (this is called the Parametricity Theorem).
ML (without infinite recursion, ref and all that weird stuff) satisfies those conditions.

From the Parametricity Theorem we know that if we have a function f : 'a list -> 'b list, then for all 'a, 'b, 'c, 'd and for all functions g : 'a -> 'c, h : 'b -> 'd we have:

map h ∘ f = f ∘ map g

(Note, f on the left has type 'a list -> 'b list and f on the right is 'c list -> 'd list.)

We are free to choose whatever g we like, so let 'a = 'c and g = id. Now since map id = id (easy to prove by induction on the definition of map), we have:

map h ∘ f = f

Now let 'b = 'd = bool and h = not. Let's assume for some zs : bool list it happens that f zs ≠ [] : bool list. It is clear that map not ∘ f = f does not hold, because

(map not ∘ f) zs ≠ f zs

If the first element of the list on the right is true, then on the left the first element is false and vice versa!

This means, our assumption is wrong and f zs = []. Are we done? No.

We assumed that 'b is bool. We've shown that when f is invoked with type f : 'a list -> bool list for any 'a, f must always return the empty list. Can it be that when we call f as f : 'a list -> unit list it returns something different? Our intuition tells us that this is nonsense: we just can't write in pure ML a function that always returns the empty list when we want it to give us a list of booleans and might return a non-empty list otherwise! But this is not a proof.

What we want to say is that f is uniform: if it always returns the empty list for bool list, then it has to return the empty list for unit list and, in general, any 'a list. This is exactly what the second point in the bullet list in the beginning of my answer is about.

The paper tells us that in ML f must take related values to related ones. I'm not going into details about relations, it is enough to say that lists are related if and only if they have equal lengths and their elements are pair-wise related (that is, [x_1, x_2, ..., x_m] and [y_1, y_2, ..., y_n] are related if and only if m = n and x_1 is related to y_1 and x_2 is related to y_2 and so on). And the fun part is, in our case, since f is polymorphic, we can define any relation on the elements of lists!

Let's pick any 'a, 'b and look at f : 'a list -> 'b list. Now look at f : 'a list -> bool list; we've already shown that in this case f always returns the empty list. We now postulate that all the elements of 'a are related to themselves (remember, we can choose any relation we want), this implies that any zs : 'a list is related to itself. As we know, f takes related values to related ones, this means that f zs : 'b list is related to f zs : bool list, but the second list has length equal to zero, and since the first one is related to it, it is also empty.

For completeness, I'll mention that there is a section on impact of general recursion (possible non-termination) in the Wadler's original paper, and there is also a paper exploring free theorems in the presence of seq.


The language of any constant-time Turing machine is regular

Hint: If the machine runs in time $t$ on all inputs then its decision only depends on the first $t$ symbols of the input.


Relative vertex capacity in max flow algorithm

For edge "consumptions" I believe the following approach should work: [I misread your question at first, but am leaving this part for the benefit of future people reading this]

Suppose you have some edge $u\rightarrow v$ with "consumption" $c$. Then you can model this by inserting a vertex $w$ in the middle to get $u\rightarrow w \rightarrow v$ and then add an edge $w\rightarrow t$ with capacity $c$, where $t$ is your sink. Then you have to ensure that your max-flow algorithm prioritizes pushing flow through $w\rightarrow t$ over $w\rightarrow v$. Thus this flow will be "consumed" as much as possible before going through the edge. I see two ways in which this can be done:

If your algorithm works by finding an augmenting path, make sure that this augmenting path goes through $w\rightarrow t$ rather than $w\rightarrow v$ if possible (i.e. if $w\rightarrow t$ is not saturated). Also make sure that this holds for the "reverse edges" (i.e prioritize taking flow away from $w\rightarrow v$ rather than $w\rightarrow t$). This should not be difficult to do, but depends on the exact implementation, and on your access to it.
Or you can use a max-flow min-cost algorithm and give a positive cost (say 1) to every edge except those of the $w\rightarrow t$ type (who receive a cost of 0).

Then to get the answer to your original problem just ignore all the $w\rightarrow t$ edges.

Now, for vertex $v$ with "consumptions" $c$ you can simply add an edge $v\rightarrow t$ with capacity $c$ and modify your algorithm in the same way.

If you don't care about the exact value of the flow through each edge but only the total max-flow, then you don't even need to change anything to the algorithm and can just use the returned value for the new graph as is.


The first option is to simply process all the imports and see what is in them. This is not what you are asking, because it is equivalent to having everything in a single file, more or less. And it can be prety expensive to process all the dependencies.

What you are looking for is the notion of interface, also known as signature. To simplify things, an interface lists all the constants that are implemented in a given unit (file, module) together with their types. Thus, given that some file imports file X, all we need is an interface for X. Such an interface may be written by the programmer, or generated automatically and stored somewhere by a compiler, there are many ways to accomplish this.


How to efficiently select the initial node to start a search in a Skip Graph

First, the skip graph is a distributed data structure. There is no reason to use it in a single machine context.

For a singly-linked skip list (on a single machine), you would start at the beginning. This is trivial to find; you just hold a pointer to the first node. For a doubly-linked skip list, you could start at any node, though unless you had some cursor-like abstraction, you'd presumably start at the beginning for most operations anyway.

A skip graph is effectively a collection of doubly-linked skip lists that share structure. There is no need to start at the beginning. This allows the machine on which to initiate an operation to be chosen arbitrarily. In a public peer-to-peer context, you are usually only aware of one or a few machines. In a data-center context, usually a load balancer will choose the machine.

A machine will generally host many nodes of the skip graph. It's not clear to me how much it matters to pick a local node at random. Typically, only some of the nodes will be connected to nodes on other machines, so picking any other node is the same as picking one of these as far as spreading load between the machines. Nevertheless, if you wanted to pick randomly from the local nodes there are a variety of approaches. Since you are only concerned about local nodes, you are free to use any non-distributed data structure to keep track of them. For example, a size-balanced tree would work. You would pick a number between 0 and the number of local nodes, and then do a rank query on a size-balanced tree containing (pointers to) the local nodes. Alternatively, you could probably get something close to a uniform distribution on average by assuming that the any one of the local portions of the skip lists making up the local portion of the skip graph is perfectly "balanced". This lets you estimate how many nodes you are skipping when you traverse a link at a given level which lets you do an approximate rank query directly against (the local portion of) the skip graph. Neither of these approaches is likely to affect the asymptotic complexity of any operation.


How can I make the following grammar unambiguous

This is a typical ambiguous grammar for arithmetic expressions. You can write different unambiguous equivalent grammars. For example, if you use the traditional precedences and associativities;
$\begin{align*}
   E &\to E + T \mid E - T \mid T \\
   T &\to T * F \mid T / F \mid F \\
   F &\to x \mid y \mid ( E )
\end{align*}$
You could also go the way of APL: All operations the same precedence, associate to the right.
$\begin{align*}
   E &\to T + E \mid T - E \mid T * E \mid T / E \mid T \\
   T &\to x \mid y \mid ( E )
\end{align*}$
The possibilities are almost endless.
To show the above aren't ambiguous isn't so easy.


Is the Rice Theorem applicable for these problems?

Rice's theorem cannot be used to show the undecidability of these two languages.

Most of the incorrect attempts that I have come across, are based on the misunderstanding that the notion of property is a vague notion from everyday life. However, a property means something very precise in the context of computability theory: A property is a class of Turing-recognizable languages.

Rice's theorem can be applied whenever we are faced with a non-trivial class of Turing-recognizable languages $\mathcal{S}$, that is, a class of Turing-recognizable languages that is neither the empty class or the class of all Turing-recognizable languages. Rice's theorem tells us that if $\mathcal{S}$ is a non-trivial class of Turing-recognizable languages, then

$$L_{\mathcal{S}} = \{ \langle M \rangle \mid M \text{ is a Turing machine such that } L(M) \in \mathcal{S} \}$$

is undecidable.

But there is no class of recognizable languages that corresponds to

$$A = \{ \langle M \rangle \mid M \text{ halts on no input} \}$$

For consider the Turing machines $M_1$:

"On input $x$, loop forever"

and $M_2$:

"On input $x$, reject"

We have that $\langle M_1 \rangle \in A$ but $\langle M_2 \rangle \notin A$, while we also have $L(M_1) = L(M_2)$.

Similarly, there is no class of languages that corresponds to

$$B = \{ \langle M \rangle \mid M \text{ halts on at least one input} \}$$

Here, we can choose $M_1$ as

$M_1:$ "On input $x$, if $x = aa$ then reject, else loop forever"

and $M_2$ as

$M_1:$ "On input $x$, reject"

Again we have that $\langle M_1 \rangle \in A$ but $\langle M_2 \rangle \notin A$, while we also have $L(M_1) = L(M_2)$.

A correct application of Rice's theorem to a decision problem about Turing machines must identify a non-trivial class of Turing-recognizable languages that the decision problem corresponds to.

See my note http://people.cs.aau.dk/~hans/ANoteOnRicesTheorem.pdf for more about correct applications of Rice's theorem as well as a discussion of incorrect applications of the theorem.


Reduction from 3-Partition problem to 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.


What is the purpose of Mark field in Fibonacci Heaps?

It does change the complexity of the operations. Simply speaking, the root list $W$ gets too large.
We have two expensive operations, which are ExtractMin and DecreaseKey. Remember that the amortized analysis uses the potential function
$$ \Phi(F)=|W| +2\cdot \text{# marks}. $$
If we call ExtractMin this might cost $O(\left|W\right|)$, however after the operation, the root list has only size $O(\log n)$, and we have charged most of the costs to the potential. The question now is how to charge-up the potential. Here come the DecreaseKey operations into play. They are responsible for a large root list $W$. Say, we add $k$ trees to the root list $W$ during the DecreaseKey operation. This means that we remove $k-1$ marks, and  we pay with the marks the costs of DecreaseKey and the change of the potential function (that is why we have a factor 2 for the marks in $\Phi$).
So what happens if we immediately put a vertex into the root list when decreasing the key. Then of course the root list might get large. But this is not the problem. The problem is, that you cannot show that after the repair-part of ExtractMin  $W$ has at most $O(\log n)$ elements. If I am not mistaken the size of $W$ can then contain up to $\Omega(\sqrt{n})$ elements. That means that if we delete directly the DecreaseKey operations are in $O(1)$ and their worst-case running time is even better than for Fibonacci heaps, but the ExtractMin is $O(\sqrt{n})$.
Another softer perspective is the following: The marks guarantee that you only delete one child for every node. Without deletion every tree in a Fibonacci heap is a binomial tree. The marks ensure that we do not diverse from the binomial tree structure too much.


Don't understand the merge part of the mergesort

The merge subroutine takes two sorted arrays and creates one sorted array out of these two arrays. It does so in linear time.

Say the sorted arrays are A = [1 2 3] and B = [2 3 4]. Since these two are already sorted, the minimum is going to be either the first element in A or the first element in B. So take the minimum among these two values and append it to the output array C. We get C = [1] and the two arrays now look like A = [2 3] and B = [2 3 4] (you don't have to remove 1 from A, you can increment an index to implement this step).

Now iterate this process until both arrays are empty and the final sorted array is C.


$NP \ vs \ co-NP$: tautology to SAT and vice versa?

Your algorithm doesn't prove NP = co-NP because you're using a Cook reduction to go from DNF-TAUTOLOGIES to CNF-SAT.  NP and co-NP aren't separate complexity classes under Cook reductions, they are separate under Karp reductions.  Under Karp reduction, changing the output of Turing machine after you've performed the polynomial-time transformation is specifically disallowed.

So while your algorithm is a way to use a SAT solver to validate proofs, it doesn't say anything about whether NP = co-NP.


Is the union of two non-regular context-free languages always non-regular?

Let $L$ be any non-regular context-free language over $\{0,1\}$, for example $\{ 0^n 1^n : n \geq 0 \}$. Take
$$
\begin{align*}
L_1 &= 0L \cup 1\Sigma^* \cup \{\epsilon\}, \\
L_2 &= 1L \cup 0\Sigma^* \cup \{\epsilon\}.
\end{align*}
$$
Then $L_1$ and $L_2$ are also non-regular context-free (exercise), but $L_1 \cup L_2 = \Sigma^*$.


All paths of less than a given length in a directed graph between couple of nodes

If I am not missing something about your question, you can apply the standard trick for reducing the question about multiple sources and destinations to the case of single source and single destination:

  Add two new nodes $s$ and $t$,
  Connect $s$ to all sources,
  Connect all destinations to $t$.

After this reduction we are in the standard question setting
with two extra vertices $s$ and $t$ and
we want to find walks from $s$ to $t$ of length at most $k+2$.


How does the OS determine the CPU burst time of a process?

Bursts values are needed for Shortest Job First (SJF) or Shortest Run Time First (SRTF) type scheduling. The burst is an estimate based on an initial starting default burst value and actual historical run values.  A process is assigned a default estimated value for its first burst and after it has run the actual burst is known.  The last estimated burst and the last actual burst are averaged to provide the process's next estimated burst.  This next estimated value is used for the next scheduling choice.  Assuming the actual bursts are roughly equal, as the process runs it's estimated burst will more closely approximate the actual value since the averaging process moves the estimated burst towards the actual value.   Of course if the actual burst for the process is somewhat random then the estimated burst will end up being closer to a median of the long and short burst times for the process.  As processes continue to run they will tend to move into either the long burst group of processes or the short burst group.

For example, when a process is created there is no historical information so it's burst value is set to a default of 10.  If the process always has an actual burst time of 20, then after the first scheduling period the estimated burst value assigned to the process will be (10+20)/2 = 15. The second run it will get (15+20)/2 = 17.5 estimated burst and so on. Each pass will move the estimate closer to the actual time required.

I probably wouldn't choose this method for scheduling a general purpose system, preferring instead a combined priority/quantum scheduling arrangement.  With SJF, a busy system with many short burst jobs could starve the longer burst CPU intensive jobs.  And if a job had short previous run times then got into a compute intensive loop, even other "short" jobs could wait excessive times before getting CPU time.  It can work well for systems that aren't excessively CPU bound and for systems where the process run times are reasonably consistent.

In a priority/quantum round robin based systems, jobs with the same priority are given at lease some CPU time, but will relinquish the CPU to other equal priority processes when it's quantum ends and will wait for its turn to come around again. If a higher priority process needs CPU time, it can preempt lower priority processes.  Various priority boosting methods can prevent complete starvation of low priority jobs on busy systems.


$\omega$-automata where string is accepted iff a final state is accessible from starting state

Yes, it was studied before. In one of the early papers on accepting infinitary languages Landweber introduced five acceptance types that included those of Büchi and Muller. On the lowest level where two types that referred to the set of states entered, and the other three levels considered the more classic set of states entered infinitely often.
Your type is called 1-acceptance (if I recall right) and a string is accepted if a state from an accepting set $D$ is entered at least once. The dual 1'-acceptance required that the states entered are always within $D$.
One level up one requires that a state from $D$ is entered infinitely often (Büchi), respectively that from some moment on the states are within $D$.
These definitions can be considered not only for finite state automata, but also for automata with external storage, like pushdown automata. One common fact for all such automata is that the 1-acceptance (your type) is of low "topological" complexity. Those $\omega$-languages are of the form $L\cdot \Sigma^\omega$, where $L$ is an ordinary language of the type of automata. This means one cannot accept $(a^*b)^\omega$.
In general there is a clear link between topological complexity of the $\omega$-language and the acceptance type.
L.H. Landweber, Decision problems for $\omega$-automata, Math. Systems Theory 3 (1969) 376-384.


How come the Bernstein operator creates a polynomial of the same degree as its input function?

The coefficients of $t^k$ for $k \gt m$ can cancel out.

For instance, let $f(x) = x^m$ and consider the coefficient of $t^n$ for $n \gt m$.

The coefficient we get is

$$n^{-m}\sum_{i=0}^{n} \binom{n}{i} i^m (-1)^{n-i}$$

which can be shown to be zero by starting with

$$\sum_{i=0}^{n} \binom{n}{i} x^{i} (-1)^{n-i} = (x-1)^{n}$$

And differentiating and multiplying by $x$, $m$ times, and then setting $x=1$.

For $m \lt n$, this indeed comes out to be zero.


A binary file is a file that is simply not a text file. It means that a bin file has a specific format (mp3, exe, jpg...) and can not be interpreted only as a character sequence. There are many ways data can be formatted and read.


How can I find a number whose sum of digits' cube is equal to n

Let us consider the more general problem in which we fix integers $0 < a_1 < \cdots < a_m$, and then given a positive integer $n$, we want to determine the smallest non-negative integer combination $\sum_{i=1}^m d_i a_i$ which is equal to $n$, if any exists, or determine the none exists. Here one combination $(d_1,\ldots,d_m)$ is smaller than another $(e_1,\ldots,e_m)$ if either $d_1+\cdots+d_m < e_1+\cdots+e_m$, or $d_1+\cdots+d_m = e_1+\cdots+e_m$ and for some $i$ we have $d_1=e_1,\ldots,d_{i-1}=e_{i-1}$ and $d_i > e_i$.

The main observation is that any optimal solution satisfies $d_i < a_m$ for all $i < m$. Indeed, if $d_i \geq a_m$ then we can decrease $d_i$ by $a_m$ and increase $d_m$ by $a_i$ to obtain a better solution. (In fact, this shows that $d_i < \mathrm{lcm}(a_i,a_m)/a_i$.) This suggests the following algorithm:

  Go over all possible values of $d_1,\ldots,d_{m-1}$ such that $0 \leq d_1,\ldots,d_{m-1} < a_m$. For each such setting, check whether it can be completed to a solution, that is, whether $a_m$ divides $n-\sum_{i=1}^{m-1} d_i a_i$. Choose the smallest solution, if any exists.

This algorithm runs in time $O(\log n)$, where the hidden constant depends in some horrible way on $a_1,\ldots,a_m$. This is optimal (up to the value of the hidden constant) since clearly we need to read the entire input.

The algorithm above doesn't really help you solve your case in practice, since the hidden constant is too large. Presumably you were supposed to use dynamic programming, an algorithm which runs in time $O(n)$ and finds the minimal length of a solution (perhaps it can also be tweaked to find a solution of minimal value).


What kind of languages can be recognized by a restricted one-tape deterministic Turing Machine?

It's famously unknown whether deterministic and non-deterministic LBA accept the same set of languages.


Fine-grained security models for XML data

I'm no expert on access control for structured data. This is a 10000-foot view. Don't assume a correlation between what my answer covers, what is scientifically interesting and what is significant in terms of deployment.

Take any access control or permission mechanism and slap some angle braces around it, and you have an XML access control mechanism. It's been done a lot, but it looks like each effort has had little visibility outside the community it originated in.

XACML is a standard (that some people actually use) for specifying access control policies. Some of these policies control data access. I believe the model it uses for actors (PAP, PDP, PEP, PIP) is common in distributed access control systems (for managing data access and otherwise).

XACL (not to be confused with XACL or XACML) is a rich model for access control over elements or subtrees, allowing redaction, encryption and other transformations of content as well as logging.

There's a 2006 survey by Mark J. Estlund. It covers both XML for access control and access control of XML. It's nowhere near complete.

Access Control in Data Management Systems by Elen Ferrari (2010) has a section on XML.


What is an example of set $A$, that is decidable if $AA$, but which is not decidable if it is $A$ alone

You can pick your favourite undecidable language $L$ and build $A$ in this way:

$A = \{ 1 \} \cup \{ 2n \} \cup \{ 2n + 1 \mid n \in L \}$

$A$ contains $1$ and all even numbers, but it also contains ... (I let you try to complete the proof)

Note that I assume that $AA = \{ xy \mid x, y \in A\}$; because if you define $AA=\{ xx\mid x \in A\}$ then it doesn't exist an undecidable language $A$ such that $AA$ is decidable (again I let you try to prove it :-).


Would $\sf RP = NP$ imply $\sf NP = coNP$?

If we will able prove that RP is closed under complement then we can say that
If RP = NP then it imply NP = Co-NP.

But we don't know whether RP=Co-RP or not.  BPP = P can be proved under some reasonable assumptions but RP $ \subseteq $ BPP.

If we show that RP = BPP then your statement will be correct.

References:

RP in Wikipedia
Notes on Randomized Algorithms (pdf)
RP in the Complexity Zoo


Help understanding this algorithm that's supposed to solve the critical section problem through mutual exclusion

Note that the while bodies are empty, i.e., if the condition is false, they just fall through to the next line.

Horrible, horrible code; extremely restrictive (taking turns!), and very inefficient (busy waiting), if you ask me.


Show that a $\alpha$-approximation algorithm is not a ($\alpha-x$) approximation algorithm for $x > $0

Suppose that you have one fast machine and one small machine, and consider jobs of the following durations: $t_1=t_2=\epsilon$, $t_3=1$, $t_4=2$.

The greedy algorithm first puts a job taking time $\epsilon$ on each machine (immaterial of tie-breaking rules). It then puts the third job on the fast machine (since it ends in $\epsilon/2$ rather than $\epsilon$), and then the fourth job on the slow machine. The makespan is $2+\epsilon$.

In contrast, if we put jobs 1,2,4 on the fast machine and job 3 on the slow machine, then the makespan is $1+\epsilon$.

This shows that your algorithm is not a $(2-\delta)$-approximation for any $\delta > 0$.

Indeed, suppose, for the sake of contradiction, that the algorithm was a $(2-\delta)$-approximation for some $\delta > 0$. Find $\epsilon > 0$ small enough so that $(1+\epsilon)(2-\delta) < 2+\epsilon$ (exercise: show that this is always possible), and consider the corresponding example.

Since the optimal makespan is at most $1+\epsilon$ and the algorithm is a $(2-\delta)$-approximation, it must produce a solution whose makespan is at most $(1+\epsilon)(2-\delta)$. However, the algorithm produces a solution with makespan $2+\epsilon > (1+\epsilon)(2-\delta)$, and we reach a contradiction.

You might be able to give an even worse example. This is just to demonstrate the proof technique.

I suggest looking at the proof that the algorithm is a $k$-approximation algorithm, and try to find an example for which the analysis is tight. This will show that the algorithm is not a $(k-\delta)$-approximation for any $\delta > 0$.


Finding a partition with minimum "maximal length"

This problem is slightly misleading in that one might wonder how to use the condition that the number of points to choose from is the square of the number of chosen points. That is actually a distraction.

Here comes an hint:

   How about instead of $n^2$, you are given some $m$ different numbers where $m\geq n$? This more general problem is not in any way harder then the original question.

This problem can indeed be solved by dynamic programming efficiently. In case when the previous hint is not enough, here are the subproblems stated explicitly.

   Can you compute the following function of integer $w$ and $k$, where $1\leq k \leq w$?
 $$ m(w,k) := \min_{i_0 = 0,\,i_k = w,\,i_1\lt\cdots<i_k} \max\{x_{i_1} - x_{i_0},\,x_{i_2}-x_{i_1},\,\cdots,\,x_{i_k} - x_{i_{k-1}}\} $$
 What is the technique? We replace the last item $1-x_{i_n}$ with $x_k - x_{i_{k-1}}$. We can compute subproblem $m(w,k)$ from subproblems $m(w',k-1)$ with $w'<w$. The original problem is just the special case $m(n^2+1, n+1)$ if we set $x_{n^2+1} = 1$.


Raptor Algorithm: Differences between trip and route

Trip represents a sequence of stops plus associated arrival and departure times on each stop.

Group all trips by their sequence of stops, ignoring the time information, then each group of trips sharing the same sequence of stops forms a route.

eg. for air traveling, each flight is a trip, while each airline is a route, grouping all flights flying on the same airline.

What I saw in the paper is

  Typically, there are many more trips than routes.

Which is obvious since there is an one-to-many mapping between route and trips.


What is the time complexity of this function?

Time complexity of mentioned algorithm is $O(1)$, because for $K>100$ you have a constant operation (println), and you know: $j=3,k = 3 \cdot n / 345 \implies 100 = 3\cdot n / 345 \implies n=11500$, means for $n\ge 11500$ your algorithm has a constant running time (also other part is constant, because just for $n<11500$ will be called).

For being more clear take a look at this question.


How to show MULT={a#b#c| a,b,c binary natural numbers and a ✕ b = c} is in Log Space?

In high-school multiplication, you multiply $a$ by $b$ by summing shifted copies of $b$, some of them zeroed out (according to $a$). You can implement this algorithm in logspace by calculating the result from LSB to MSB, keeping track of the carry. The crucial point is that the carry is only $O(\log n)$ bits long.


Mathematically determine if two strings are permutations of each other

Your algorith isn't correct.

Take $abbc = [1, 2, 2, 3]$ and $acd = [1, 3, 4]$. Their product is $12$ and their sum $8$, yet they aren't permutations of each other; they don't even have the same length.


How to find $c$ and $n_0$ for Big-Oh questions

In general, you should first set up the inequality and then try to solve for $n$ in terms of $c$. Often, this won't be feasible - there may not be a way to analytically obtain a closed-form solution involving only $c$ and $n$. In such cases, you can usually massage the inequality down to something where solutions can be determined by inspection.

In this case, we can start with the inequality $2^n \leq cn!$. You should be able to convince yourself that this isn't going to be a super-clean solution for $n$ here. Instead, we can try to massage this into a form that can be reasoned about.

Both of these terms involve repeated multiplication; we can write them out like that and see whether we notice a trick: $2 \times 2 \times ... \times 2 \leq c \times 1 \times 2 \times ... \times n$. We notice that the LHS is a product of $n$ terms, and the RHS consists of $c$ multiplied by $n$ other terms. Of the $n$ terms on the RHS besides $c$, all but $1$ are greater than or equal to the corresponding term on the LHS. If we rewrite the RHS as $(c \times 1) \times 2 \times ... \times n$ and choose $c = 2$, we get $2 \times 2 \times 3 \times ... \times n$. All $n$ of these terms are greater than or equal to the corresponding terms on the LHS, meaning the product is bigger, as we wanted. Thus, the choice $c = 2$ works for all choices of $n_0$.

Just to give you an idea of what a boring resolution would look like: let's show that $f(n) = 2n + 3$ is $O(g(n))$ if $g(n) = n + 1$.

We get $2n + 3 \leq c(n+1)$. Solving for $n$, we get $2n + 3 \leq c(n+1) = cn + c$, so $2n - cn \leq c - 3$ and $n(2 - c) \leq c - 3$. Note that if we choose $c \leq 2$, there are no valid solutions for $n$. We now have two cases: either $c \geq 2$ or $c < 2$. In the latter case, we can write $n \leq \frac{c-3}{2-c}$ which, along with the constraint that $n > 0$, yields no solutions. In the former case, we write $n \geq \frac{c-3}{2-c}$. You may now plug in any value of $c$ you like and find an $n_0$ to suit. We can see that the choice $c = 3$ allows us to choose $n_0 \geq 0$; the choice $c = 2.5$ requires that we choose $n_0 \geq 1$; etc.

If you're dealing with more complicated functions - specifically, ones that aren't monotonically increasing - you'll want to choose $n_0$ from the rightmost interval. Otherwise, the functions cross over each other again for a period, making your choice wrong. Usually, you don't have to worry about runtimes being other things than monotonically increasing, but it is a mathematical possibility of which you should be aware.


Is it possible to detect cats from dogs in image with single layer perceptron?

No, that's just not possible.

  Although the perceptron initially seemed promising, it was quickly proved that perceptrons could not be trained to recognise many classes of patterns.

Check the Wikipedia article on the subject.


in a graph G= (V,E), finding a clique of size |V|- d where d is some constant

The brute force algorithm would check all vertex subsets of size $n-d$, where $|V|=n$. There are $$\binom{n}{n-d} = \binom{n}{d}=\frac{n(n-1)\dots (n-d+1)}{d!}$$ different subsets. This quantity is $\mathcal{O}(n^d)$ and since $d$ is constant this problem is in $P$.

You are asking

  Is the question above still NP?

Even though the problem is in $P$, this problem is still in $NP$ since $P \subseteq NP$, however, unlike $k$-clique problem this problem  may not be NP-complete.


Representing "but not" in formal grammar

For context-free grammars (I guess your question concerns this type of formal grammars), it would be not only painful, but also impossible in general.

Suppose we have an algorithm that provides such "expansion" and yields a new grammar without $\text{but not }$occurrences. Then we can take two arbitrary context-free languages $L, L'$ with start nonterminals $A, A'$ respectively, write down a rule $B \longrightarrow A \text{ but not } A'$, run the algorithm on it, and get a context-free grammar for $L\backslash L'$. It contradicts a well-known fact that difference of two context-free languages can be not context-free.


If modern computers aren't actually Turing-complete, does that mean that it is possible to determine if a program run on such a computer halts?

You can take a look at:
https://en.wikipedia.org/wiki/Halting_problem#Common_pitfalls

One can realize that a program is not halting by seing that it's repeating its behavior.
"A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state"

It also says that even computers are finite state machine, it's more useful to model them as infinite state machines, just because the number of states it's huge.
"Minsky warns us, however, that machines such as computers with e.g., a million small parts, each with two states, will have at least $2^{1,000,000}$ possible states"


Yes.  You want to look at the bag-of-words model and n-gram models.

The bag-of-words model corresponds to the part of your characteristic vector: namely, the parts <A>, <B>, <C> of your characteristic vector, i.e., the frequencies of a single letter.  These are used as features for the ML algorithm.

n-gram models generalize this to a substring of length n.  For each substring of length n, we count the frequency of that substring.  These frequencies are again used as features.  For instance, we'd have a feature for the frequency of AB, the frequency of AC, and so on.

In real-world computer science, we don't deal with infinite systems; we only deal with finite systems.  (Our lifetime is finite, so a computer can only examine a finite portion of the input.)


You're on the right path.  Here's my suggestion.  First, apply the definition of conditional probability:

$$ \Pr[e|a,c,\neg b] = {\Pr[e,a,c,\neg b] \over \Pr[a,c,\neg b]}. $$

So, your job is to compute both $\Pr[e,a,c,\neg b]$ and $\Pr[a,c,\neg b]$.  I suggest that you do each of them separately.

To compute $\Pr[a,\neg b,c,e]$, it is helpful to notice that

$$ \Pr[a,\neg b,c,e] = \Pr[a,\neg b,c,d,e] + \Pr[a,\neg b,c,\neg d,e]. $$

So, if you can compute terms on the right-hand side, then just add them up and you've got  $\Pr[a,\neg b,c,e]$.  You've already computed $\Pr[a,\neg b,c,\neg d,e]$ in part (b).  So, just use the same method to compute $\Pr[a,\neg b,c,d,e]$, and you're golden.

Another way to express the last relation above is to write

$$ \Pr[a,\neg b,c,e] = \sum_d \Pr[a,\neg b,c,D=d,e]. $$

If you think about it, that's exactly the same equation as what I wrote, just using $\sum$ instead of $+$.  You can think about whichever one is easier for you to think about.

Anyway, now you've got $\Pr[e,a,c,\neg b]$.  All that remains is to compute $\Pr[a,c,\neg b]$.  You can do that using exactly the same methods.  I'll let you fill in the details: it is a good exercise.  Finally, plug into the first equation at the top of my answer, and you're done.


We count the number of array element reads and writes. To do bubble sort, you need $1 + 4n$ accesses (the initial write to the end, then, in the worst case, two reads and two writes to do $n$ swaps). To do the binary search, we need $2\log n + 2n + 1$ ($2\log n$ for binary search, then, in the worst case, $2n$ to shift the array elements to the right, then 1 to write the array element to its proper position).

So both methods have the same complexity for array implementations, but the binary search method requires fewer array accesses in the long run... asymptotically, half as many. There are other factors at play, naturally.

Actually, you could use better implementations and only count actual array accesses (not accesses to the element to be inserted). You could do $2n + 1$ for bubble sort, and $\log n + 2n + 1$ for binary search... so if register/cache access is cheap and array access is expensive, searching from the end and shifting along the way (smarter bubble sort for insertion) could be better, though not asymptotically so.

A better solution might involve using a different data structure. Arrays give you O(1) accesses (random access), but insertions and deletions might cost. A hash table could have O(1) insertions & deletions, accesses would cost. Other options include BSTs and heaps, etc. It could be worth considering your application's usage needs for insertion, deletion and access, and choose a more specialized structure.

Note also that if you want to add $m$ elements to a sorted array of $n$ elements, a good idea might be to efficiently sort the $m$ items, then merge the two arrays; also, sorted arrays can be built efficiently using e.g. heaps (heap sort).


approximation algorithm with polynomial complexity

As you say, we believe there is no polynomial-time algorithm for solving an NP-hard problem. So if we wanted to have a polynomial-time algorithm, it seems like we need to give up the hope of always finding an optimal solution. So you are right: typically, we strive to find approximation algorithms that run in time polynomial in the input size. But sure, there is nothing that prevents you from considering approximation algorithms that run in exponential-time (or for example in FPT-time for some parameter).

Sometimes these approximation algorithms are very simple to state. This is perhaps often the case for greedy algorithms, like the one you mention for vertex cover. To see that it runs in time polynomial in the size of the input graph, you need to perform a runtime analysis in the usual way.


Didn't look at your code, but in general there are two important points that distinguish recursion from dynamic programming.

First recursion is top-down (starting with the big instances, by decomposing them into smaller instances and combining the answers) while DP is bottom-up (first solving the small cases, and combining them into larger ones).

The second important point is the table that contains the solutions to instances with certain parameters. This is to avoid computing certain cases more than once (as recursion tends to do).

So DP is upside down recursion in general. But one can also start with recursion and a lookup table that tests whether a certain subproblem was already solved.


Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?

The input to 0/1 knapsack is a list of $n$ items each with a weight $w_i$ and value $v_i$ with knapsack size $W$ and maximum value $V$.  Thus the input list has size $O(n (\log W + \log V))$.

So $n \log n$ is polynomial in the input.

The problem with the traditional dynamic programming solution of knapsack is not that it is exponential in $n$, but that it is polynomial in $W$ (or $V$), which makes it exponential in $\log W$.


Finding all edges of an undirected graph which are in some cycle in linear time

It is not difficult to prove that an edge is a cut-edge if and only if it does not lie on a cycle. So you can find the set $E'$ of cut edges, and what you are then looking for is $E \setminus E'$.

For finding $E'$, there are several well-known linear-time algorithms. Wikipedia gives e.g., Tarjan's bridge-finding algorithm.


Let's introduce a variable $x_i$ for every node $i$, representing the condition that the node is part of the vertex cover. Then for every edge $\{v,w\}$ we introduce the clause $x_v \lor x_w$.

We have the additional condition $x_1  + x_2 + \ldots \ +\ x_n \leq k$. We can combine an addition circuit  to compute the bits of the sum with a comparator circuit to enforce the inequality. The CNF of the resulting circuit has only polynomially many clauses.


Graph Has Two / Three Different Minimal Spanning Trees?

Kapoor & Ramesh (proper SIAM J. Comput. version, free(?) personal website version) give an algorithm for enumerating all minimum spanning trees in both weighted and unweighted graphs.

My understanding of the basic idea is that you start with one MST, then swap edges that lie along cycles in the graph (so as long as the weights are okay, you're replacing one edge with another that you know will reconnect the tree).

For the weighted case they give a running time to list all minimum spanning trees of $O(N\cdot|V|)$ where $N$ is the number of such spanning trees. It enumerates them in order of increasing weight, and my current (cursory) understanding suggests that it's perfectly feasible to terminate the algorithm after it has generated a given number of trees (as it just starts with the MST and produces them sequentially).


What is the difference between the study of Evolutionary algorithm vs. Optimization?

Indeed, in evolutionary algorithms, you are optimizing an objective function. Hence, evolutionary algorithms are algorithms for optimization. Hence, they are the specific case of optimization methods. However, there are a vast variety of optimization methods that are not an evolutionary algorithm (such as simplex methods in OR, Lagrange methods and so on). See more about the evolutionary algorithms here:

  In artificial intelligence, an evolutionary algorithm (EA) is a subset of evolutionary computation1, a generic population-based metaheuristic optimization algorithm.


0/1 Integer Programming and Karp's Reduction

I believe there's a typo in Karp's definition of the problem. If we replace $Ax=b$ with $Ax \geq b$, the reduction goes through as is. The easiest way I can think of to show the hardness of your problem (the one as written in Karp's paper), is via 1-in-3 SAT or via hypergraph perfect matching.


Why do we pop the dollar symbol when it's already present in the stack in PDA?

The "end-of-stack" symbol (often $\$$) is necessary for the automaton to know when there are no more stack symbols. Therefore, when we reach $\$$ we have two options:

Remove the $\$$ and terminate¹.
Put it back there for later, maybe adding additional symbols.

Ergo, as long as you do not want to terminate you have to keep putting $\$$ back when you find it.

Why does it have ot be like that, you ask? In the definition I know, PDAs always "take out"² the top-most symbol. So the creator of the PDA has no choice but to deal with the $\$$ once it is on the top of the stack.

But why define it like that, you ask? If PDAs were allowed to not consume the topmost stack symbol they'd be inherently nondeterministic. And since you gain nothing by this choice -- doing nothing with the stack is trivial to simulate by just putting the symbol you read back -- there is no reason to introduce this source of nondeterminism.

Depending on the definition, termination is defined by empty stack or you have to switch into a final state. The definitions are equivalent.
Remember that it's an declarative, not an algorithmic definition!


Generating a Context Free Grammar(CFG) from a Language

You can construct the grammar using the following nonterminals:

$S$ is the initial nonterminal. We will include a production $S \to 00S0$ to capture the inequality $i+j \geq 2k$ being satisfied just using $i$.
$T$ will similarly be a nonterminal that will include a production $T \to 11T0$ which captures the inequality $i+j \geq 2k$ being satisfied just using $j$. We also add a termination production $T \to \epsilon$.
The production $S \to T$ will allow us to mix both kinds of ways to satisfy the inequality $i+j \geq 2k$. However, there are two problems:

We need to allow $i+j > 2k$.
We need to allow the case $i+j = 2k$ in which $i,j$ are both odd, i.e., at some point the inequality $i+j \geq 2k$ is satisfied by increasing $k$ by 1, and compensating by increasing both $i$ and $j$ by 1.

To handle the second problem, we will add a production $S \to 01T0$.
To handle the first problem for $i$, we will add the production $T \to 1T$, and to handle it for $j$, we will add the production $S \to 0S$.

In total, we obtain the following grammar:

$$
\begin{align*}
& S \to 0S \mid 00S0 \mid 01T0 \mid T \\
& T \to 1T \mid 11T0 \mid \epsilon
\end{align*}
$$

You can prove by induction the following statements:

$T \Rightarrow^* xTy$ iff $x = 1^j$, $y = 0^k$, and $j \geq 2k$.

As a conclusion, $T \Rightarrow^* w$ if $w = 1^j0^k$, where $j \geq 2k$.

$S \Rightarrow^* xSy$ iff $x = 0^i$, $y = 0^k$, and $i \geq 2k$.

As a conclusion, $S \Rightarrow^* xTy$ if either $x = 0^i$, $y = 0^k$, and $i \geq 2k$, or $x = 0^i1$, $y = 0^k$, and $i+1 \geq 2k$.
As a conclusion from (1), $S \Rightarrow^* w$ if $w = 0^i 1^j 0^k$, where $i+j \geq 2k$.


Principles of Distributed Computing - "processors" and "states"

Based on the wording of this, it seems to imply that there are n of each buffer

Assuming that each edge in the network graph $G=(V,E)$ corresponds to a bidirectional channel, there are $4|E|$ many buffers in total: For an (undirected) edge $(p_i,p_j)$, we have one pair of in/out buffers for $p_i$ and one pair for $p_j$.

  Each state of the processor $p_i$ contains $2r$ special components: $inbuf_i[l]$ and $outbuf_i[l]$.

Let's look at an example to get an intuition for what the above means:
Suppose that we have some network where $p_3$ is connected to $p_1$ and $p_2$.
Let's assume that process $p_3$ sends a message $m$ to process $p_1$ and has received (but not yet processed) a message $m'$ from process $p_2$. Moreover, $p_3$ has a local variable $counter$. Then we could represent the current state $\sigma_3$ of $p_3$ as  $$\sigma_3 = (inbuf_3[1],inbuf_3[2],outbuf_3[1],outbuf_3[2],counter).$$
According to the above example, $m' \in inbuf_3[2]$ and $m \in outbuf_3[1]$. Note that the state of the network is given by $(\sigma_0,\dots,\sigma_n-1)$.