Here is one possible way to reduce Clique to SAT (you can then further reduce it to 3SAT). This type of reduction is often used in (propositional) proof complexity, an area of complexity theory.

Given a graph $G = (V,E)$ and a number $k$, we will have variables $x_{iv}$ for every $1 \leq i \leq k$ and every $v \in V$. You should think of $x_{iv}$ as stating that $v$ is the $i$th vertex in the clique. We want to encode the following constraints:

For each $i$, there is an $i$th vertex in the clique: $\bigvee_{v \in V} x_{iv}$.
For each $i,j$, the $i$th vertex is different from the $j$th vertex: for each $v \in V$, $\lnot x_{iv} \lor \lnot x_{jv}$.
For each non-edge $(u,v) \notin E$, $u,v$ cannot both belong to the clique: for each $i,j$, $\lnot x_{iu} \lor \lnot x_{jv}$.

You can think of the second constraint as a special case of the third one.

If we take all these clauses together, we get a CNF which states that "the $x_{iv}$ encode a $k$-clique in $G$". This CNF is satisfiable iff $G$ contains a $k$-clique.

If you want to get a 3CNF, all you need to do is to convert the constraints of the first kind into 3-clauses. There is a standard way to do this: if the vertices are $v_1,\ldots,v_n$, we replace $\bigvee_{v \in V} x_{iv}$ with
$$
x_{iv_1} \lor x_{iv_2} \lor y_{iv_2} \\
\lnot y_{iv_2} \lor x_{iv_3} \lor y_{iv_3} \\
\lnot y_{iv_3} \lor x_{iv_4} \lor y_{iv_4} \\
\ldots \\
\lnot y_{iv_{n-2}} \lor x_{iv_{n-1}} \lor x_{iv_n}
$$
Here the $y_{iv}$ are new variables. This set of clauses is equivalent to the original clause $x_{iv_1} \lor x_{iv_2} \lor \cdots \lor x_{iv_n}$.


Counterexample to big-O claim looks wrong

The counterexample is fine. Any function that is $O(n)$ is also $O(n^2)$ – if a function's "smaller than" $n$, it's also "smaller than" $n^2$.

And note that even weaker statements are false.  In fact, there is no function $g$ such that $T_1,T_2=O(f)$ implies that $T_1(n)/T_2(n)=O(g(n))$.  For example, take $T_1(n)=1$ and $T_2(n)=1/g(n)^2$. So, now, $T_1(n)/T_2(n) = g(n)^2\neq O(g(n))$.


To properly produce a formal grammar, you should designate a non-terminal for each different part of a decimal. Here is a sample grammar in Backus–Naur form that also uses square brackets for optional items.

            <decimal> ::= [<sign>]<nonnegative_decimal>
               <sign> ::= - | +
<nonnegative_decimal> ::= <nonnegative_integer>[<fractional_part>]
<nonnegative_integer> ::= <positive_integer> | 0
   <positive_integer> ::= <nonzero_digit>[<digits>]
    <fractional_part> ::= .<digits>
             <digits> ::= <digit>[<digits>]
              <digit> ::= <nonzero_digit> | 0
      <nonzero_digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

It can be made more compact as the following.

            <decimal> ::= [ - | + ]<nonnegative_decimal>
<nonnegative_decimal> ::= <nonnegative_integer>[.<digits>]
<nonnegative_integer> ::= <nonzero_digit>[<digits>] | 0
             <digits> ::= <digit>[<digits>]
              <digit> ::= <nonzero_digit> | 0
      <nonzero_digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Please note that the above grammar defines a decimal as a string that starts with a possible sign followed by an integer, possibly followed by a dot and some digits, where only 0,1,2,3,4,5,6,7,8 and 9 are allowed in an integer or digits and where an integer must not start with 0. Many other kinds of decimals are used, too.


Show that the SAT Problem for CNF formulas with at most two occurences of each variable can be solved in polynomial time

Consider a variable $x_i$. If it appears once, or if it appears twice but in the same polarity (i.e., both times as a positive literal or both times as a negative literal), then we can set it accordingly and satisfy all the clauses that contain it (more formally, any satisfying assignment can be converted into a satisfying assignment in which $x_i$ has this value).

The remaining case is the in which $x_i$ appears once positively and once negatively, that is, there are clauses $x_i \lor C$ and $\lnot x_i \lor D$. These two clauses are logically equivalent to the single clause $C \lor D$, which no longer contains $x_i$.

In this way, we keep eliminating the variables one by one, until we either eliminate all of them (in which case the formula is satisfiable), or we reach an empty clause (in which case the formula is unsatisfiable), which happens when both $C$ and $D$ are empty in the second case.


Proofs of $P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$

This is not the full proof but the complete idea:
Let Turing machine $M$, define  $L_M$  be the language defined as  $L_M = \{ ((x, y) \in \Sigma^*\times \mathbb{N}  ~|~ \#\text{accepting path of } {M}(x) > y \} $
Then prove that $L_M\in PP$.
Now use the binary search technique to compute the function g(x) in $\#P$ using $L_M$.
And other way around its easy by using $\#P$ function TM you can always answer whether no. of accepting paths are more $\frac{1}{2}$ or not.
Let $L\in P^{\#p}$, then there is a deterministic oracle Turing machine $M'$ that runs polynomial time, and a function $g\in \#p$
such that  $L= M'^{g}$. Let $M$ be a poly time Turing machine that uses at most $poly(n)$ non-deterministic steps such that $g(x)=\# acceptig pathof M"(x)$.   Use the standard binary search technique to show that  $g(x)$ can be computed  using $O(n)$ many queries to the language $L_M$.
$x$, oracle access to $L_M$ and output $g(x)$.

Initialize $p=|x|$, $y=2^p$.

Repeat steps 3 & 4 until $p\ge 0$

Query $(x,y)$ to the oracle;  If YES, then set $y=y+2^{p+1}$;
Else
break .

Set $p=p-1$

Now we know the range for g which is $2^{p-1}<g<2^{p}$
$use binary search technique in this range and since there can be exponential terms hence binary search technique will take O(|x|) time.
Clearly, the algorithm  above runs in time ${\sf poly}(n)$, and hence computing $g$ can be done in $poly$ with oracle access to $L_M\in PP$.


Hint: This way lists are represented as folds. So if you have a lambda term representing a list, you just supply a folding function and a value to start with and the result will be the folded value.


How many RAW dependencies are present in these instructions?

TL;DR: According to a 5-stage pipeline scenario, there are just two true RAW hazards:

1. I2 to I1 for R1
2. I3 to I2 for R2

Explanation

The answer might depend on the pipeline stages. For the sake of this question, let's consider a basic 5-stage pipeline: Instruction Fetch (IF), Decode (DE), Execute (EX), Memory Op (MEM) and Writeback (WB).

    Instr\Cycle      C1   C2   C3    C4    C5    C6    C7    C8
 ------------------ ---- ---- ----- ----- ----- ----- ----- -----
  I1: R1 = R2 - R3   IF   DE   EX1   MEM   WB1
  I2: R2 = R1 + R3        IF   DE    EX2   MEM   WB2
  I3: R3 = R1 + R2             IF    DE    EX3   MEM   WB3
  I4: R1 = R2 - R2                   IF    DE    EX4   MEM   WB4

At first, it may seem like there are many RAW dependencies in this instruction sequence but let's analyze how the pipeline behaves with this sequence. The above table might indicate the following:

EX2 depends on WB1 (WB1->EX2)
EX3 depends on WB1 (WB1->EX3)
EX3 depends on WB2 (WB2->EX3)
EX4 depends on WB2 (WB2->EX4)

After the first stall in the pipeline by EX2, the scenario changes a bit. WB1->EX2 (1) was a true dependency. But, WB1->EX3 (2) is no more a dependency:

    Instr\Cycle      C1   C2   C3    C4    C5    C6    C7    C8    C9    C10
 ------------------ ---- ---- ----- ----- ----- ----- ----- ----- ----- -----
  I1: R1 = R2 - R3   IF   DE   EX1   MEM   WB1
  I2: R2 = R1 + R3        IF   DE    EX2   EX2   EX2   MEM   WB2
  I3: R3 = R1 + R2             IF    DE    DE    DE    EX3   MEM   WB3
  I4: R1 = R2 - R2                   IF    IF    IF    DE    EX4   MEM   WB4

After the second stall in the pipeline by EX3 (3) (which truly waits for WB2), the scenario changes again. Clearly, WB2->EX4 (4) is revealed to be no more a dependency.

    Instr\Cycle      C1   C2   C3    C4    C5    C6    C7    C8    C9    C10   C11   C12
 ------------------ ---- ---- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
  I1: R1 = R2 - R3   IF   DE   EX1   MEM   WB1
  I2: R2 = R1 + R3        IF   DE    EX2   EX2   EX2   MEM   WB2
  I3: R3 = R1 + R2             IF    DE    DE    DE    EX3   EX3   EX3   MEM   WB3
  I4: R1 = R2 - R2                   IF    IF    IF    DE    DE    DE    EX4   MEM   WB4

Therefore from our original list above, only following true RAW hazards are revealed:

EX2 depends on WB1 (WB1->EX2)
EX3 depends on WB2 (WB2->EX3)


How do modern Operating Systems detect process starvation?

Inline with @chi 's comment;  lets say process "x" gets starved in linux or windows, then for example if we are in the windows, wouldn't we get an error message saying the process "x" is not responding? Approximately no.

Now let's assume we want to detect process "x",before starvation nor aging;we have to read it's  arrival time, burst time,process id, priority from the text file and calculate the average waiting time and show the central processing unit utilization of each cycle,for instance;

Time 1 process X arrives

Time 2 process X runs

Time  3 process B arrives

Time 4 process X finishes..........,randomly.

Hope this can give you a little bit of insight.


A systematic approach to creating a simple test parser

As far as I can tell, you can model this easily using any number of formalisms. Of course, if you insist on the specific syntax you have invented, you may be out of luck and may have to build your own engine.

I wouldn't to that if I were you: you have both forward and backward references, and your "data access" tokens closely resemble your "logic" tokens, so processing may become troublesome.

Consider this instead:

{if weight}; Weight is: {weight}kg{endif}

This can easily be parsed using standard techniques, and is immediately familiar to many people. It also supports nesting (if you use a context-free parser).

That all said, here is a sketch of an algorithm that will parse your syntax, assuming that there is no nesting at all (which you don't seem to specify).

We simply work in two phases:

Lex the input into tokens: regular text, and your special tokens. Represent the former by text(text) latter by two types, data(name) and conditional(left, right, text).

Go over the token list, evaluating each token according to these rules:

 eval text(t) ==> t
 eval data(n) ==> value(n)
 eval conditional(left, right, text) ==>
    if   (!left || (eval predecessor) != "")
      && (!right || (eval successor) != "") {
        text
    } else {
        ""
    }

You see that you have to keep two copies in memory, at least for a time.

I think it's straight forward to transform this solution so that you move a three-token window over the token stream; this way, you can forget old tokens, and only need to lex one token in advance. So, as long as your conditional tokens only depend on their immediate neighbours, this can be efficiently parsed.


Why is OPT at least the most valuable item for FPTAS Knapsack?

It is common to assume without loss of generality that the maximum item weight is at most as large as the knapsack capacity. That is okay (in the context of complexity theory) because filtering out items that are too large to fit even alone is easily possible in a polynomial-time preprocessing step.

If the sources do not mention that they are sloppy.

And in that case, every item fits into the knapsack alone, hence you can obtain the maximum item value with a trivial singleton solution.

Nota bene: As soon as we are talking algorithms and want to derive running times, such assumptions are not necessarily w.l.o.g. In case the running time cost of the preprocessing is dominant we should not lie it away.


Would hypercomputation machines be capable of simulating/computing/programming everything?

I think you have an important misunderstanding about what "uncomputable" means. It doesn't mean "doing something mathematically impossible", such as producing a non-trivial factorization of a prime number. There simply are no integers other than $1$ and $181$ that divide $181$ and it doesn't matter what method of computation you use, you will never find these non-existent factors because they just don't exist.  The factoring problem is not uncomputable: you can write a computer program that will correctly factorize any number that you give it. In the case of $181$, the program will just say, "The factors are $1$ and $181$ and that's all."

A problem is uncomputable if there is no Turing machine ("computer program") that can solve it. The standard example is what's called the halting problem: you have a computer program and you want to know if it will terminate, or get stuck in an infinite loop. Turing's famous result is that there is no Turing machine that will take the description of another Turing machine as input and correctly say either "this terminates" or "this loops forever".

Some models of hypercomputation can solve this problem. That is, the "hypercomputer" can decide whether given Turing machine will terminate. However, Turing's proof is very general and applies to any sufficiently powerful model of computation. So, although the hypercomputation model might be able to solve the halting problem for Turing machines, Turing's proof can be easily adapted to show that the hypercomputer cannot solve its own halting problem. That is, there is no hypercomputer program which takes as input the source code of another hypercomputer program and correctly determines whether that program will halt.

In summary, every sufficiently powerful model of computation has uncomputable problems, so no model of hypercomputation can compute everything.


How hard is it to solve for $P$ in $A = PBP^{-1}$?

Graph isomorphism has been well-studied.  A short summary: the graph isomorphism problem is not known to be in P (there are no known polynomial-time algorithms), but it is not believed to be NP-complete.  There are heuristic algorithms for  graph isomorphism that work extremely well on most instances that arise in practice.  Read the Wikipedia page on graph isomorphism for more.

As for your particular proposed approach: the Wikipedia page you linked to already explains why that method does not work in general.  That method only works if there are no repeated eigenvalues in the matrix corresponding to the adjacency graph.  Therefore, it will fail for graphs where there are repeated eigenvalues.  Such graphs cannot be ignored.  Consequently, that method may work for some graphs but it will fail (or work poorly) for other graphs, so it is not a general solution.

Graph isomorphism is not a good candidate for a basis for a cryptographic system, for two reasons.  First, existing heuristic algorithms are very good at solving the problem in practice, and it's not clear how to generate hard instances of graph isomorphism.  Second, and more seriously, to be useful for cryptography, we need to not only have a hard problem; we need to have a "hidden trapdoor" that the creator of the public key can embed, which makes the problem easy for the creator, but which is hard for anyone else to detect.  No one  knows how to embed such a "hidden trapdoor" into the graph isomorphism problem.


When an ISAM index is built, how is the number of leaf nodes per index node (the "fan-out") calculated?

In a page-structured file, each page has a fixed size. This effectively eliminates internal fragmentation.

Each index page needs to store a bunch of keys and corresponding pointers to other disk pages. The number of keys-and-pointers that can be stored in a disk page is what determines F.

So how big is a page?

In a real-world DBMS, the lower limit is the virtual memory page size, which is determined by the hardware and the operating system. The physical block size of a disk is typically smaller than this, so that's not a concern. Setting your file page size to be some multiple of the VM page size lets the operating system buffer cache act as the database buffer cache.

The upper limit is set by efficiency considerations, since pages which are too big require more I/O and also potentially wastes space when pages are under-full.

So in practice, a small power-of-two multiple of the VM page size is appropriate.


How many strings are close to a given set of strings?

See Levenshtein's paper. It contains bounds on the number strings obtained from insertion and deletion of a string. If $n$ is the length of the string and the string is binary, then the maximum number of nearest neighbors in the Levenshtein distance is $\Theta(n^2)$. It is comparatively harder to say anything about $k$-nearest neighbours, but one can get bounds. These should give you an estimate on the complexity.


How to prove the set of Turing machines that accept a string and its mirror is undecidable?

It's the standard reduction from the Halting problem: given a machine $M$ and an input $w$ to it, construct a new machine $M$ that accepts your favourite string and rejects its reverse if $M(w)$ halts, and accepts nothing if $M(w)$ does not halt.

This technique applies to any question of the form "Prove that it's undecidable whether a Turing machine accepts a string or language of some specific kind."

Or just use Rice's theorem, if you've been taught that.


The trick used in the proof of the doubly exponential complexity of Presburger arithmetics

Martin's comment (and Yuval's follow up) gives the reference which explains the construction in some detail.

I'll elaborate a bit because I think it's a gorgeous proof: basically it's performing the "usual" proof of undecidability of PA (arithmetic with addition and multiplication), but relativized to $2^{2^{c\cdot n}}$! That is, there is a (short) formula which expresses multiplication up to that number, i.e. a formula $M_n(x,y,z)$ such that
$$M_n(x,y,z) \Leftrightarrow x\times y=z\ \wedge x< 2^{2^n} $$

Now you build $M_n$ by induction on $n$, with a crucial trick that is reminiscent of the Karatsuba algorithm for multiplying binary numbers or certain tricks for matrix multiplication:

In the definition for $M_{n+1}(x,y,z)$ you end up with a conjunction of the form
$$M_{n}(x_1,y_1,z_1)\wedge M_{n}(x_2,y_2,z_2)\wedge M_{n}(x_3,y_3,z_3)$$

But you can replace this with
$$ \forall u v w,(u=x_1\wedge v=y_1\wedge w=z_1)\vee(u=x_2\wedge v=y_2\wedge w=z_2)\vee(u=x_3\wedge v=y_3\wedge w=z_3)\Rightarrow M_n(u,v,w)$$

This trick allows a linear increase in size instead of an exponential one (as a function of $n$).

There's a couple of other tricks involved, but this is the main one. The internals of the recursion are important, of course, but the similarity to the Karatsuba trick is really quite striking.


Automata that recognizes Kleene closure of permutations of three symbols

There are a few things wrong with this automata:

It does not accept the empty string.
It is not a DFA – there should be no undefined transitions in a DFA.
It only accepts strings of length three, not multiples of three.

You are on the right track. Dealing with 1. and 3. above are fairly straightforward.
 Feed in an empty string. What state do you end up in? What does it mean to accept?
Feed in some longer strings. What's the pattern?
Dealing with 2. is rudimentary too, just a matter of filling in the missing transitions.

It's a good idea to read and understand again the definition of DFA, in particular, understanding what is allowed and what is not allowed.

EDIT: Here is a prettier solution:


Intersection of Deterministic Context-Free Languages

The statement itself doesn't imply that.  It just means that the intersection of two DCFLs might or might not be a DCFL; and thus presumably could be a DCFL; could be a CFL but not a DCFL; or could be not context-free.
However, we know more actually.

The intersection of two DCFLs could be, of course, a DCFL. For example, you can let both of them be the same DCFL. For another example, just take any two regular languages. Every regular language is a DCFL and the intersection of two regular language is still regular.

Here is an example of two DCFLs the intersection of which is not a CFL.  The intersection of $\{a^{n}b^{n}c^m \mid n\ge0, m\ge 0\}$ and $\{a^{n}b^{m}c^m \mid n\ge0, m\ge 0\}$ is the most classical non-CFL, $\{a^{n}b^{n}c^n \mid n\ge0\}$.

Exercise. Find two different non-regular DCFL the intersection of which is a DCFL.
Deeper fact. Given any natural number $n$, there is a language that is the intersection of some $n+1$ DCFLs, but it is not the intersection of any $n$ DCFLs.


After removing the first vertex, the new graph has $n' := n-1$ vertices and $m' := m-d_G(u) > m-k$ edges. Therefore
$$
\frac{m'}{n'} > \frac{m-k}{n-1} = k.
$$
Continuing in this way, we see that at any point in time, the ratio between edges and vertices is always at least $k$. Any graph on $\ell$ vertices has a ratio of at most $\binom{\ell}{2}/\ell = \frac{\ell-1}{2}$, so the number of vertices always satisfies $\ell \geq 2k+1$. In other words, when the algorithm terminates, there will be at least $2k+1$ vertices left.


Lambda calculus: difference between contexts and evaluation contexts

Context are used for many purposes, but typically to define congruences on programs. Evaluation contexts are a subset of contexts. They are typically used to define reduction relations. Let me give an example of each.

One formal way of defining program equality is to say two programs $M$ and $N$ are contextually equal they can replace each other in each context without a change of behaviour. We can define this as follows: $M$ and $N$ are contextually equal provided for all closing contexts $C[\cdot]$ for $M$ and $N$: $C[M] \Downarrow t$ if and only if  $C[N] \Downarrow t$. We say a context is closing for $M, N$ if neither $C[M]$ nor $C[N]$ have free variables. The expression $M \Downarrow t$ means that the program $M$ reduces in a finite number of steps to the value $t$. (As an aside, note that the definition of contextual equivalence is more involved for rich notions of computation, e.g. concurrent processes.)

In contrast, evaluation contexts are contexts that do not block evaluation.
More precisely, an evaluation context is a term with a hole at the point where the next atomic reduction step must  take place (or may take place for non-deterministic computation).
 So the following rule should hold for evaluation contexts:
$$
  \frac{M \rightarrow N}{E[M] \rightarrow E[N]}
$$
As an example of using evaluation contexts, consider the reduction rules for
call-by-value $\lambda$-calculus, where we do not reduce under $\lambda$. So even when $M \rightarrow N$, we don't have a reduction $\lambda x.M \rightarrow \lambda x.N$. This can easily be expressed with the  general contextual rule above,
together with a grammar for evaluation contexts that omits $\lambda$-expressions. Evaluation contexts were first used in The Revised Report On The Syntactic Theories of Sequential Control and State by Felleisen and Hieb.


Distinction between 2 languages.One is regular the other is not

This is one of those trap questions where $L_2$ can actually be written in a different way that makes it obvious that it is a regular language. See if you can figure out what $L_2$ is "really doing", and the answer will become obvious.

Solution:

   $L_2 = 0(1010)^*$


What is the regular expression describing this language?

Yes, your idea is correct.
Basically here two things are happening.

Regular languages are closed under compliment operation
If L1 is accepted by DFA1 and DFA2 is obtained by interchanging the final states to non-final states and non-final states to final states of DFA1 then the language accepted by DFA2 is compliment of L1. That is, if

DFA1 is a quintuple (Q, Σ, δ , q0, F)
And L1 is language accepted by DFA1
DFA2 is (Q, Σ, δ , q0, (Q - F))
And L2 is language accepted by DFA2 Then L2 is compliment of L1.

In this case the languages L1 = {w∣w is any string except 11 and 111} and L2 =
{v∣v is either 11 or 111} are compliment o each other .
Hence your approach is correct.


In fact, the VC dimension is 3.

To show this, we need to show that there is a set of 3 points which is shattered, and that no set of 4 points is shattered.

All sets of 3 points behave the same, but for definiteness let us choose three points $x,y,z$ which form the corners of an equilateral triangle. By symmetry, there are only 4 cases to consider:

$\emptyset$: choose some arc which avoids all points.
$\{x,y,z\}$: choose the complement arc.
$\{x\}$: choose a small arc around $x$.
$\{y,z\}$: choose the complement arc.

This shows that the VC dimension is at least 3.

To show that the VC dimension is at most 3, let us consider some arbitrary set of points $x,y,z,w$, presented in clockwise order starting at an arbitrary point. An arc that contains both $x$ and $z$ must contain either $y$ or $w$, and in particular there is no arc that contains exactly $\{x,z\}$.


Maximum-cardinality matching in unbalanced bipartite graphs

I just found the answer myself. In this paper:

  Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs". Technical reports, HP research labs.

in section 5, the authors show that the Hopcroft-Karp algorithm in fact solves the following problem: given an integer $s$, find matchings with $1,\ldots,s$ edges. The run-time is $O(|E|\sqrt{s})$. In particular, if $|X|<|Y|$, we can take $s=|X|$ and the run-time is $O(|E|\sqrt{|X|})$.


Find longest common subsequence in limited space

The standard dynamic programming algorithm for the LCS$(x,y)$ problem runs in time $O(|x|\cdot |y|)$. Simply speaking you fill out a $|x| \times |y|$ table $T$ using the recursion
$$T[i,j] =
\begin{cases}
0
& \mbox{ if }\ i = 0 \mbox{ or }  j = 0 \\
 T(i-1,j-1) +  1
& \mbox{ if } x_i = y_j \\
  \max\{T[i,j-1],T[i-1,j]\}
& \mbox{ if } x_i \ne y_j \\
\end{cases}.$$

A natural extension of this recursion leads to an algorithm that fills out an $|x|\times |y|\times |z|$ table and computes the LCS of three strings.

Notice that you can improve the required space even further (while keeping the asymptotic running time) using  Hirschberg's extension.


It's not so clear what is meant by "sum of all values in the range $i$ to $j$". This probably means the sum of entries in locations $i$ to $j$.
Let us denote the entries of the array by $a_1,\ldots,a_n$. The entry $a_k$ is counted in those $c_{ij}$ such that $i \leq k \leq j$. There are $k(n+1-k)$ of these, out of a total of $\binom{n}{2}$. Therefore the quantity you are interested in is
$$
\frac{1}{\binom{n}{2}} \sum_{k=1}^n k(n+1-k) a_k.
$$

Here is another interpretation, in which we sum all values in the array which belong to $\{i,\ldots,j\}$. Even this can be solved in linear time!
Suppose that some entry of the array has value $k$. What is its contribution to the average of the $c_{ij}$? It is counted in some $c_{ij}$ iff $i \leq k \leq j$. Out of the $\binom{n+1}{2}$ many $c_{ij}$'s, there are exactly $k(n+1-k)$ in which the entry is counted, therefore its contribution to the average is
$$
\frac{k(n+1-k)}{\binom{n+1}{2}} \cdot k = \frac{2k^2(n+1-k)}{(n+1)n}.
$$
Summing this over all values in the array, we obtain the desired $O(n)$ algorithm.


Does my simple, static hash table have O(1) worst case lookup?

Yes, your access time is $\mathcal{O}(1)$. Your construction time is a bit more complicated. Let $P(k)$ be the propability, that a set structure containing $k$ elements has a bucket with more than 1000 entries. If there is an overflow after the initial construction in $\mathcal{O}(k)$, everything is rearranged with costs of $\mathcal{O}(k)$. But this might clash again. Thus you get expected costs of $\mathcal{O}(k) + \sum \limits^\infty_{j=1}P(k)^j\mathcal{O}(k)=\mathcal{O}\left(\frac{k}{1-P(k)}\right)$.


$${\displaystyle \mathrm {H} (Y|X)\ =-\sum _{x\in {\mathcal {X}},y\in {\mathcal {Y}}}p(x,y)\log {\frac {p(x,y)}{p(x)}}}$$

Based on chain rule, we have:

\begin{aligned}\mathrm {H} (Y|X)&=\sum _{x\in {\mathcal {X}},y\in {\mathcal {Y}}}p(x,y)\log \left({\frac {p(x)}{p(x,y)}}\right)\\[4pt]&=-\sum _{x\in {\mathcal {X}},y\in {\mathcal {Y}}}p(x,y)\log(p(x,y))+\sum _{x\in {\mathcal {X}},y\in {\mathcal {Y}}}{p(x,y)\log(p(x))}\\[4pt]&=\mathrm {H} (X,Y)+\sum _{x\in {\mathcal {X}}}p(x)\log(p(x))\\[4pt]&=\mathrm {H} (X,Y)-\mathrm {H} (X).\end{aligned}

So for $H(X|Y)$ in your sample, we have:
$$
H(X|Y) = -( 0.25 \times \log(\frac{1}{2}) ) - ( 0.25 \times \log(\frac{1}{2}) ) -( 0 \times \log(\frac{0}{0.5}) ) -( 0.5 \times \log(\frac{0.5}{0.5}) )
$$


No, they are not the same.

There are different equivalent representations for any problem (e.g. Turing machines, neural networks, differential equations, ...). But changing from one representation to another does not change whether the problem is fundamentally solvable - otherwise they would not constitute equivalent representations.

Zeno machines can be considered as Turing machines plus hypercomputation which, if it were possible, would permit solving certain previously undecidable problems.

Differential equations can be seen as extension of algebraic equations (or, conversely: an algebraic equation is a differential equation where no derivatives appear).

However, those two types of extensions are independent of each other:

There exist differential equations which are solvable by Turing machines.
There exist differential equations which are not solvable by Zeno machines.

If what made Zeno machines different from Turing machines was that only Zeno machines could represent differential equations, then there could be no Turing machines which can solve for differential equations.

But if you search for "differential equation solver" you get a lot of results: there exist programs which can solve certain differential equations. So a Zeno machine is not necessary for solving differential equations. Therefore Zeno machines and differential equations cannot be the same.

You can interpret the computations of a Zeno machine as a differential equation only insofar as you can already interpret the computations of a Turing machine as a differential equation. So neither do differential equations tell you anything about Zeno machines nor do Zeno machines tell you anything about differential equations.


Is this restricted promise-3SAT version coNPComplete?

Your problem is coNP-complete when the property is "all variables are zero". Given a SAT formula $\varphi$ on $x_1,\ldots,x_n$, construct a new SAT formula $\psi$ by replacing each clause $C$ of $\varphi$ with $\lnot y \lor C$ (where $y$ is a new variable), and adding clauses $y \lor \lnot x_i$ for $1 \leq i \leq n$. The satisfying assignments of $\psi$ are obtained from those of $\psi$ by setting $y = 1$, and there is an additional satisfying assignment in which all variables are zero. Hence $\varphi$ is satisfiable iff not all satisfying assignments of $\psi$ satisfy the property.


Approximation rate for Greedy Set Cover algorithm (RESOLVED)

I have figured out the answer.

The trick is not really coming from $\frac{k}{t} > ln(n)$ to $\frac{k}{t} \leq ln(n) + 1$ directly. Lets take 1 step back.

Lets say there is no item uncovered at k-th step. So, $|U_{k}| = 0$ and $n \times exp(-\frac{k}{t}) < 1$ (otherwise, there could be a remaining uncovered item in $U_{k}$, and this would be a contradiction of $|U_{k}| = 0)$;

The step above can be rewritten as:

Lets say there is no item uncovered at k-th step. So, $|U_{k}| = 0$ and we are done. We are interested in how much steps we can take before that happens. So, find the upper bound of k such as $|U_{k}| \geq 1$;
$|U_{k}| \geq 1 \Leftrightarrow n \times exp(-\frac{k}{k}) \geq 1$. This results in $k \leq \frac{ln(n)}{t}$. So, $k = \frac{ln(n)}{t}$ is our upper bound for iterations. If $k = \frac{ln(n)}{t}$, $|U_{k}| = 1$. It's almost done. There is only 1 last item to cover and, consequently, 1 last round to run.
Therefore, $k \leq \frac{ln(n)}{t} + 1$ in order to get $|U_{k}| = 0$. It's easy to see that $\frac{k}{t} \leq ln(n) + \frac{1}{t}$.

One can still get a cleaner solution and say $\frac{k}{t} \leq ln(n) + 1$ since $t \geq 1$.

k is the number of steps taking to get G_OPT. At each step, G_OPT increases by 1. Then, $|G\_OPT| = k$. We defined $t = |OPT|$. We end up with

Approx. rate $= \frac{|G\_OPT|}{|OPT|} \leq ln(n) + 1$


Count number of linearly independent subsets of columns of a binary matrix

Snook, Counting bases of representable matroids shows that counting the number of maximal linearly independent subsets of columns is $\mathsf{\# P}$-complete. Your problem is probably also $\mathsf{\#P}$-complete. This suggests that you need an enumerative approach.

On the other hand, you can efficiently (in theory) approximate the number of maximal linearly independent subsets arbitrarily well, see for example Anari et al., Log-Concave Polynomials II: High-Dimensional Walks and
an FPRAS for Counting Bases of a Matroid (might be an overkill).


How to show composition of one way function is not such?

You come up with an example: two functions $f,g$ which are one-way functions, but $f \circ g$ is not. To show that the latter is not a one-way function, you come up with an algorithm breaking it.

Here is an example. Choose some genuine one-way function $h$.  Let $f(x) = h(x) 0^{|x|}$, and let $g(x,y) = h(x)$ if $y \neq 0^{|x|}$, and $g(x,y) = 0^{|x|}$ if $y = 0^{|x|}$ (we break the input in such a way that $|x|=|y|$). Note that the composition is just the zero function.


Segmenting a human body point cloud into limbs

Suggestion: for each point $P$ in the point cloud, find which bone it is nearest to, and associate it with that bone.  In other words, find which point $Q$ on the skeleton is closest to $P$, and associate $P$ with $Q$.  Now associate $Q$ with a particular part of the skeleton (e.g., arm, leg, etc.); that will let you associate $P$ with a particular part of body (e.g., arm, leg, etc.).  Do this for each point in the point cloud.

Try that -- it's a very simple approach, and it might just work.


Raphael is correct in stating the states of a TM is a theoretical construct defining the operating program.  What you are thinking of ("reading", "writing", and "moving") are operations the machine can do out of a particular state.

Wikipedia has a nice little write up about it.  Explaining that each state, tells the machine what next operation to perform based off of a current state.


recurrence - Iteration method T(n)=T(n-a)+n

Hint: Let's solve the case $a = 1$; I'll leave the generalization to you:
$$
\begin{align*}
T(n) &= n + T(n-1) \\ &=
n + (n-1) + T(n-2) \\ &=
n + (n-1) + (n-2) + T(n-3) \\ &= \cdots \\ &=
n + (n-1) + (n-2) + \cdots + (1) + T(0) \\ &=
\frac{n(n+1)}{2} + T(0).
\end{align*}
$$
In the general case, if $n = ma$ then you'll get $am(m+1)/2 + T(0) \approx n^2/(2a) + T(0)$.


An instance of propositional STRIPS planning is a quadruple $\langle P,O,I,G \rangle$

$P$ is the set of atomic ground formulas;
$O$ is the set of operators (actions); an operator  $a \in O$ has the form $Pre \Rightarrow Post$, where $Pre$ is a satisfiable conjuction of positive ($a^+$) and negative preconditions ($a^-$) of the operator; $Post$ is a satisfiable conjunction of positive ($a_+$) and negative ($a_-$) postconditions of the operator ($a_+$ is called the add list, $a_-$ is called the delete list);
$I \subseteq P$ is the initial state;
$G = \langle G_+, G_- \rangle$, called the goals, is a satisfiable conjunction of positive and negative conjunctions;
the state $S$ is a subset of $P$.

The result of applying operator (action) $a$ on state $S$ is:

$(S \cup a_+) \setminus a_-\quad$ if $a^+ \subseteq S$ and $S \cap a^- = \emptyset$
$S$ otherwise

In your example simply set:
$$a^+ = \{q\}, \quad a^- = \{p\}$$
$$a_+ = \{p\}, \quad a_- = \{q,r\}$$

For a formal definition and a nice computational complexity characterizations of STRIPS with various constraints on the preconditions/postconditions see:
The Computational Complexity of Propositional STRIPS Planning (1994), by Tom Bylander.


Why do particles in particle swarm optimization converge to the global best when their personal best has just as much weight?

The random number biases distance along the vectors, so it changes per update helping in escaping local optimum, and the global best also changes during the algorithm, if you really want some of these answers try programming a visual particle system using PSO.


Write Serialization for Cache Coherence in the presence of Store Buffers

From a coherence perspective, I think your example is coherent.  All processors believe that the write and read from A happened first, then the write and read from B happened later.

From a consistency standpoint you need to be more careful.  (Consistency is the global ordering of memory operations to different addresses.) The way consistency is handled in practice is that the store buffer sits before retirement, not after.  The store buffer acts as a little coherent cache for the speculative memory state.  A store instruction is not permitted to retire until its processor has acquired write ownership of the appropriate cache line.

The store buffer needs to be aware of all the coherence traffic reaching the cache.  If a speculative load gets its value from the store buffer, but the corresponding memory location is invalidated before the load retires, the load (and everything following it in the reorder-buffer) needs to be squashed and reexecuted.


How can primitive recursion in two variables be made to be of only one variable?

A few facts that should help:

1 - You can encode lists with primitive recursive functions

I can expand if needed.

I'll write lists as $[x_1, \dots, x_n]$, write $x::[x_1,\dots ,x_n]$ for $[x,x_1,\dots,x_n]$ and $\operatorname{hd}([x_1,\dots ,x_n])$ for $x_1$.

2 - You can use any order you want when defining a function by primitive recursion

Let $b$ be a primitive recursive bijection whose inverse is also primitive recursive. Then you can use recursion with respect to the order $x<_by$ defined as $b(x)<b(y)$ and it will still define primitive recursive functions. Suppose that you have $g(x,b(0))=g_0(x)$ and $g(x,b(k+1))=h(x,b(k),g(x,b(k)))$. Then you can define $g'(x,0):= g_0(x)$ and $g'(x,k+1)=h(x,b(k),g'(x,k))$ and you will get $g'(x,k)=g(x,b(k))$ so that you can now define $g(x,y):=g'(x,b^{-1}(y))$.

3 - Your function can know its value on all smaller inputs when defining a function by primitive recursion

Let $X$ be the domain of your function $g$ defined by $g(x,0)=g_0(x)$ and $g(x,k+1)=h(x,k,[g(x,k),g(x,k-1),\dots,g(x,0)])$. Then you can define $g'(x,0):=[g_0(x)]$ and $g(x,k+1):=h(x,k,g'(x,k))::g'(x,k)$ and you will have $g'(x,k)=[g(x,k),g(x,k-1),\dots,g(x,0)]$. You can therefore define $g(x,k):=\operatorname{hd}(g'(x,k))$.


Longest path length in an undirected tree, can we prove this algorithm is correct (which it is)?

I think this might help. Copied from https://stackoverflow.com/questions/20010472/proof-of-correctness-algorithm-for-diameter-of-a-tree-in-graph-theory.

Let s, t be a maximally distant pair. Let u be the arbitrary vertex. We have a schematic like,

    u
    |
    |
    |
    x
   / \
  /   \
 /     \
s       t

where x is the junction of s, t, u (i.e. the unique vertex that lies on each of the three paths between these vertices).

Suppose that v is a vertex maximally distant from u. If the schematic now looks like

    u
    |
    |
    |
    x   v
   / \ /
  /   *
 /     \
s       t ,

then

d(s, t) = d(s, x) + d(x, t) <= d(s, x) + d(x, v) = d(s, v),
where the inequality holds because d(u, t) = d(u, x) + d(x, t) and d(u, v) = d(u, x) + d(x, v).
There is a symmetric case where v attaches between s and x instead of between x and t.

The other case looks like

    u
    |
    *---v
    |
    x
   / \
  /   \
 /     \
s       t .

Now,

d(u, s) <= d(u, v) <= d(u, x) + d(x, v)
d(u, t) <= d(u, v) <= d(u, x) + d(x, v)

d(s, t)  = d(s, x) + d(x, t)
         = d(u, s) + d(u, t) - 2 d(u, x)
        <= 2 d(x, v)

2 d(s, t) <= d(s, t) + 2 d(x, v)
           = d(s, x) + d(x, v) + d(v, x) + d(x, t)
           = d(v, s) + d(v, t),
so max(d(v, s), d(v, t)) >= d(s, t) by an averaging argument, and v belongs to a maximally distant pair.

PS: I saw many answers after searching the question. I do not have enough repuation to comment otherwise I would have done so.


Shannon Entropy of 0.922, 3 Distinct Values

Here is a concrete encoding that can represent each symbol in less than 1 bit on average:

First, split the input string into pairs of successive characters (e.g. AAAAAAAABC becomes AA|AA|AA|AA|BC). Then encode AA as 0, AB as 100, AC as 101, BA as 110, CA as 1110, BB as 111100, BC as 111101, CB as 111110, CC as 111111.
I've not said what happens if there is an odd number of symbols, but you can just encode the last symbol using some arbitrary encoding, it doesn't really matter when the input is long.

This is a Huffman code for the distribution of independent pairs of symbols, and corresponds to choosing $n = 2$ in Yuval's answer. Larger $n$ would lead to even better codes (approaching the Shannon entropy in the limit, as he mentioned).

The average number of bits per symbol pair for the above encoding is
$$\frac{8}{10} \cdot \frac{8}{10} \cdot 1 + 3 \cdot \frac{8}{10} \cdot \frac{1}{10} \cdot 3 + \frac{1}{10} \cdot \frac{8}{10} \cdot 4 + 4 \cdot \frac{1}{10} \cdot \frac{1}{10} \cdot 6 = 1.92$$
i.e. $1.92/2 = 0.96$ bits per symbol, not that far from the Shannon entropy actually for such a simple encoding.


How to collect all states of a behavior in TLA+?

An answer from Stephan Merz at tlaplus-googlegroup:

In a linear-time framework such as TLA+, a system satisfies a property if the property holds of all system behaviors, and from your description it appears to me that this is what you want. TLC will compute all states that are reachable in your system and evaluate the property over all behaviors: there is nothing that you need to do explicitly.

The potential problem with this is that your system may have a lot of states, and TLC may not finish computing the entire state graph (or at least not in a reasonable amount of time). The TLA+ literature and resources give much advice for working around this problem, in short, you will want to choose small parameters and perhaps constrain the set of states considered by TLC using a state constraint (in the advanced options pane of the Toolbox interface).


Test two LTL expression trees for equivalence

Unfortunately, the approach of constructing automata for each formula and testing their equivalence is pretty much the best you can do.
The problem of checking whether an LTL formula is valid, that is, whether it is satisfied in every computation, is PSPACE complete (this is an easy exercise, given that LTL satisfiability is PSPACE complete).
Thus, checking whether two LTL formulas are equivalent is also at least PSPACE hard, since you can reduce from the former by testing equivalence with the formula "true".
In order to show membership in PSPACE, you can take the standard approach of checking equivalence of the corresponding automata "on the fly", without actually constructing them  explicitly.


Can the pumping lemma for context free languages be extended to any subword?

The extended form of pumping lemma for regular languages you mentioned is called "the general version of pumping lemma for regular languages".

It is indeed natural to suspect that a similar general version of the usual pumping lemma for context-free languages as said in the title should hold. Unfortunately, it does not. For example, take context-free language $L=\{a^nb^n\}$. The initial subword $a^n$ of $a^nb^n$ can be arbitrarily long. However, no part of that subword can be pumped.

There are, however, a few valid generalizations of the usual pumping lemma for context-free languages. You may want to take a close look at them.

Ogden's lemma.
Interchange lemma.


It depends on context, languages, operating systems
In many languages, Prologues and Epilogues are the parts automatically added by compilers at the beginning and end of each function, for example adjusting stack pointers or copying parameters.


Updating an MST $T$ when the weight of an edge not in $T$ is decreased

Let $T$ be a minimum spanning tree of $G$. Let $e$ be the edge we modify to get $G'$, and let $T'$ be the tree computed according to the algorithm. We know that weight of $T'$ is less than or equal to the weight of $T$.

Firstly, $T'$ is a tree - we create exactly one cycle in the algorithm, and break it, so we have no cycles in $T'$.

Secondly $T'$ is a spanning tree of $G'$. Let $e'$ be the edge removed and $e''$ be the edge added in the algorithm (we have either $e'' = e'$ or $e'' = e$) . To be a spanning tree, we must have a path between every pair of vertices $u$, $v$ using only edges of $T'$. Suppose that in $T$ (which is definitely a spanning tree), the path from $u$ to $v$ did not involve $e'$, then the same path exists in $T'$. Alternatively, suppose that it did use $e'$, then there is a path (without loss of generality) from $u$ to one endpoint of $e'$ and from the other endpoint of $e'$ to $v$. There is also a path from one endpoint of $e'$ to the other endpoint via $e''$ (around the cycle), all within $T'$. Then we can construct a path from $u$ to $v$ via $e''$ in $T'$ by merging these three paths and removing the overlap (although a walk is sufficient for connectivity).

Now, the important part, we wish to prove that $T'$ is a minimum spanning tree for $G'$.

Case 1: The algorithm does not add $e$ to the tree. In this case $T' = T$. Suppose that there is a minimum spanning tree $H$ for $G'$ that is different to $T'$. If $H$ has the same weight as $T'$, we're done. Now suppose for contradiction that the weight of $H$ is less than the weight of $T'$. There must be some edge $e'$ of lowest weight that is in $H$ but not in $T'$ (there must be some edge that does better, otherwise $G$ would not be of lower weight than $T'$, moreover we can assume that the edge that does better is the lowest weight edge that's not in $T'$ - we can take any $H'$ that is a lower weight tree than $T'$ and look at the candidate for $e'$, if it is not smaller than any edge in its cycle, then either $H'$ is not an MST, or we can create a new $H'$ where we swap the $e'$ for some edge of $T'$, this process must terminate with an edge $e'$ which has the property that it is the edge that does better).

If $e' \neq e$, then consider the tree obtained by adding $e'$ to $T$ (note, not $T'$), and removing the highest weight edge on the cycle formed. This new tree has weight less than that of $T$ and is a spanning tree for $G$, contradicting the fact that $T$ is an MST for $G$ - so we know this can't happen.
If $e' = e$, consider the cycle formed by adding $e' = e$ to $T'$ (i.e. the one the algorithm considered). All other edges in the cycle have lower weight than $e'$ (otherwise the algorithm would've included $e$ as an edge), and hence must be in $H$ (as $e'$ is the lowest weight edge that is not already in $T'$), but then $H$ must contain a cycle, so isn't a tree and we have a contradiction.

Case 2: The algorithm adds $e$ to $T'$. Let $x$ be the edge in $T$ that is removed by the algorithm (and hence not in $T'$) Again assume we have another MST $H$ as before. If the weight is the same, we're happy. So assume for contradiction that $H$ has lower weight, and as before $e'$ is the lowest weight edge in $H$ that's not in $T'$. We can make similar arguments as before with $x$.

If $e' \neq x$, (note also that $e' \neq e$), then we can improve $T$ as before, but we know that $T$ is an MST, and recalling the property that we can assume $e'$ has lower weight that at least one edge in the cycle its addition induces, this gives a contradiction and $H$ can't exist.
If $e' = x$, then again $e'$ must have higher weight than all the other edges in the cycle, hence $H$ must contain all these edges and $H$ is not a tree, and we derive a contradiction.

So in every case we derive a contradiction, therefore there can be no spanning tree of lower weight that $T'$, hence $T'$ is a minimum spanning tree for $G'$.


The $n$ where the two expressions are equal isn't all that huge. Here's how to calculate it.

We want
$$ 1.000001^n \approx n^{1000001}.$$
This is the same as
$$e^{n \log 1.000001} \approx e^{1000001 \log n}.$$
Now, taking the $\log$ of both sides, and using Taylor's formula to approximate the left-hand side, we get
$$ n*10^{-6} \approx 10^6 \log n,$$
or
$$\frac{n}{\log n} \approx 10^{12}.$$
Since this means $\log n \approx \log 10^{12},$ we get $$n \approx 10^{12} \log 10^{12} = 2.7 * 10^{13}. $$
More exactly, using Maple to solve the equation numerically (you have to give it the estimate above as a starting value or it gives up), we find that $n \approx 3.1*10^{13}$.


LL(1) parsing table of left-recursive grammar

It appears you have misunderstood your professor. "If the leftmost nonterminal is S and the input is 'b', the production is both Sa and b." means that both Sa and b are correct answers if the leftmost nonterminal is S and the input is 'b'. This means that the parser does not know which production to go to and is stuck.

This means that this grammar cannot be parsed using this type of parser technology. You would either have to change the grammar or use a different type of parser.


Turing machine states, lost in the jungle

The only terms I have seen used with any consistency are "dead" and "unreachable".

There is also the dual, "unproductive" states. This term comes from formal grammars and means that you have a state/non-terminal from which you can not reach a final state/terminal string.


Equivalent DPDA that always halts for every DPDA with empty stack language

The look-ahead property for pushdown automata is that a PDA $Z$ can answer certain questions of the form "how would PDA $X$ behave when given my stack", and then make moves based on that information. In particular, also deterministic PDA $Z$ can use this even when $X$ is nondeterministic.

You know, as I understand from the formulation of your question, this is possible because the property "when started on stack $\alpha$ PDA $X$ empties its stack" defines a regular set of stacks. The PDA look-ahead test can then be build in the original PDA.

So, to solve your problem, you have to formulate which PDA tests you would like to perform on the stack in order to avoid infinite computations.

I do not know whether it is necessary to actually construct the regular language of stacks that gives a positive answer.


Invertible function that randomizes order

You are looking for a pseudorandom permutation on the set $\{0,1,2,\dots,n-1\}$.  In cryptography, this has been studied under the (counter-intuitive) name "format-preserving encryption".  There are a number of constructions you could use for your purposes.

There's a bunch of research literature on the problem, with different schemes that are optimized for different values of $n$.  You can also find some summaries on Cryptography.SE.

I recommend you start by reading the question and the answers at Lazily computing a random permutation of the positive integers and Encrypting a 180-bit plaintext into a 180 bit ciphertext with a 128-bit block cipher and What are the examples of the easily computable "wild" permutations?.


Why does the total credit associated with a data structure must be nonnegative at all times for the accounting method?

The amortized analysis calculates complexity for a sequence of $ n \in \mathbb{N} $ operations, no matter how large $ n $ is and what is the structure of sequence (i.e. which operations are within the sequence). If you would allow $ \sum_{i = 1}^{n}{\hat{c_i}} < \sum_{i = 1}^{n}{c_i} $ for some $ n $ and some sequence of operations, then the same inequality would hold for any multiplication of $ n $. Thus you would not have an upper bound, so no analysis would be possible. This reasoning is for both accounting and potential method.


DFS algorithm and how do I show/put it into practice?

The first thing you need to do is pick a data structure - i.e a representation for your node graph.  For this I suggest you pick up any undergraduate-level book on data structures and read it carefully, and choose something appropriate.  For example, given the tree above, I would represent each node with a record containing whatever data is to be stored in that node (e.g the name - A, B, etc) plus a list of (pointers to) child nodes.  E.g your root would have the list {A, B, C}, node A would have the list {N}, node J would have the list {K, L, M}, and so on.  Each childless node ('leaf') would have an empty list.

Then you code your DFS procedure, which you may find easier to do if you use recursion to process children (although there are ways to make this non-recursive if you insist).  Regardless of implementation, the core behavior of DFS is: To process each node, you must do something with the node, then scan the list of children and process each child -and its entire subtree- before processing the next child.  You can get different effects according to whether you process each node before its children, or after [if each node has at most two children AND explicitly distinguishes 'left' child from 'right' child, then there is also the option of processing each node -between- left and right].

And yes, you can still perform DFS if there are cross-connections.  The key new thing to do here is to keep track of whether the node you are about to process has already been processed; generally what you will want to do in that case is skip that node and go back up to the parent.  This is particularly true if 'children' really means 'neighbors', so the edges between nodes aren't directed; then you really need to avoid running in cycles.


Find a binary matrix so that no vector from {-1,0,1}^n is in its kernel

I have a method for you that will help you find valid solutions (matrices) for many possible values of $m,n$.  However, it is not a complete answer to your question.  It can try to find a matrix for a particular value of $m,n$, but it might fail, and if it fails, you've learned nothing; my method cannot prove that no such matrix exists.
The method is based upon the following observation:
Theorem. If we have a valid $m_1\times n_1$ matrix $X_1$ that meets all your requirements (for parameters $m_1,n_1$) and a valid $m_2\times n_2$ matrix $X_2$ that meets all your requirements (for parameters $m_2,n_2$), then we can find a valid $m\times n$ matrix that meets all your requirements (for parameters $m,n$), where $m=m_1+m_2$ and $n=n_1+n_2$.
Proof.  Use the following matrix:
$$X = \begin{pmatrix} 0 &X_1 \\ X_2 &Z \end{pmatrix},$$
where $Z$ is arbitrary.  Suppose $Xy=0$, where $y \in \{-1,0,1\}^n$.  Then since the last $m_1$ coefficients of $Xy$ are zero, and since $X_1 y_1 =0$ implies $y_1=0$, it follows that the last $n_1$ coefficients of $y$ are zero.  Thus by letting $y_2$ be the restriction of $y$ to its first $m_2$ coefficients, we find that $X_2 y_2 = 0$.  But this implies $y_2 = 0$, i.e., $y=0$.  In other words, if $Xy=0$, then $y=0$.  This proves that $X$ is a valid matrix.

Now this lets us find many values of $m,n$ where it is possible to find a valid matrix $X$.  In particular, seed things with some small matrices for various small values of $m,n$ (using any convenient method); then you can derive some larger values of $m,n$ that also have such a matrix.
Here are some observations that will help you identify seed values $m,n$ where such a matrix $X$ exists:

First, a trivial observation: Obviously, if $n \le  m$, it is easy to find a valid solution $x$: just use the identity matrix (if $n<m$, fill in the extra rows arbitrarily).  No need to use integer linear programming.  So this problem is only interesting when $n>m$.

Second,  if $n$ is small enough, you can express this as a SAT instance and apply an off-the-shelf SAT solver.  The SAT instance will be of exponential size: it will have more than $3^n$ constraints, so this is only helpful for very small values of $n$, but it will still help you construct some values of $m,n$ where you can find a valid matrix $X$.

Third, you can use bcorso's answer to handle all cases where $n=m+1$ (there is always a valid solution, for $m\ge 3$).
In particular, you can construct a SAT instance where the $x_{i,j}$ are the variables.  Now, for each possible non-zero vector $y \in \{-1,0,1\}^n$, you can add a complicated constraint enforcing the requirement that $Xy \ne 0$.  (You'll need to have $m$ adders, each of which adds up to $n$ 0-or-1 values, and then a comparison to test whether the results of all of the $m$ adders are all zero or not.)

In this way, I would expect that, for each $n\le 8$ (or so), you can probably find the largest value of $m$ such that there exists a valid $m\times n$ matrix.  Now once you have those seed values, you can use the Theorem above to help you find additional values of $m,n$ where such a matrix exists.
As I stated above, this is not a complete solution, but it might help you solve your problem at least some of the time.

For general $m,n$, I doubt that there's any straightforward formulation of this as a polynomial-size integer linear program (unless $\text{NP} = \text{NP}^\text{co-NP}$ or the polynomial hierarchy collapses or something like that, which is not expected to hold; or unless you use some special knowledge about the solution to this problem).
Just telling whether a candidate value of $x$ is indeed a valid solution to this problem is $\text{co-NP}$-complete.  See https://cstheory.stackexchange.com/q/20277/5038.  In other, recognizing a solution to this problem can't be done in polynomial time (as far as we know); just recognizing a valid solution is $\text{co-NP}$-complete.  This means that the problem of finding a valid solution is in $\text{NP}^\text{co-NP}$.  In contrast, integer linear programming is in $\text{NP}$.  Therefore, without using some special knowledge about this problem, I don't think you can find a generic reduction from your problem to integer linear programming unless $\text{NP}^\text{co-NP} = \text{NP}$ (something that most complexity theorists believe is not likely to hold).
Don't take this too seriously.  I'm not trying to prove a formal theorem or anything like that; I'm just trying to give some weak evidence why this problem does not look like it has a straightforward, generic formulation as an instance of integer linear programming.
Of course, you can probably get a formulation as an integer linear program with a number of constraints that is exponential (say, in $m$), similar to how we got a SAT instance.  It'll be uglier, because expressing the constraint that some vector (namely, $Xy$) is not identically zero is ugly in ILP.  But it's doable.  See, e.g., Express boolean logic operations in zero-one integer linear programming (ILP).  However, I'm not sure this will be any better than the SAT-based method.  If I were implementing this, I would start by trying the SAT-based method, because (if you use a suitable front end, like STP) I think it will be easier to implement and might work just as well or better than an ILP-based formulation.


Proving undecidability of a language with mapping reductions

Usually, when the context of the statement "if $M$ accepts $x$" is in a loop simulating the execution of $M$ on $x$, we just mean to say that if the simulation stopped and $M$ accepted/rejected then do something, otherwise just continue simulating (the more precise way of writing this would be to say "if $M$ accepted after $t$ steps then...").
Your pseudocode doesn't do anything magical, it simply checks at a specific point of the simulation whether or not $M$ already accepted/rejected.


max, min gradient and other terms in Neural Network

I suggest you to read an introduction to neural networks. I like neuralnetworksanddeeplearning.com, but I can also recommend chapter 4.3 of my bachelors thesis.

  max, min gradient in each layer

The gradient is like the derivative for high-dimensional functions. Imagine it as an arrow on a landscape. The arrow points into the direction of the steepest ascent, we want to go into the other direction (where the error becomes smallest).

  2.max, min activation in layers

The activation is $\sum w_i x_i$ (details and my BS thesis). Hence it is what each neuron returns, before the activation function is applied. Now you have many neurons per layer and hence a set of activations $A$. Hence you can take the min / max of it. I don't know why you would take the min, but the maximum might give you an indicator which neurons are "responsible" for which feature.

For CNNs, a complete feature map is usually considered to be one neuron (see my MS thesis for some more details). In your case, it simply seems to be the maximum feature returned (hence the brightest pixel; see input layer)

  3.Forward time per example

Measure how long it takes to process the input of a neural network.
(There is also the backward pass for the gradient)


Calculating the structural integrity of a pixel grid

So I found a solution using maximum flow algorithm with some tradeoffs.
The setup involves:

Connecting the source node to every node in the grid with an edge capacity equal to the nodes mass.
Connecting the sink to the bottom layer
Connecting every node in the grid to each other with some capacity defined by the node (i.e. the maximum stress/load from that direction)

After Dinic Max Flow algorithm runs, I traverse the residual graph starting at nodes which do not get the maximum flow from the source (i.e. nodes that can't apply their full mass) and find all nodes which have an edge with max capacity.
[CodePen Example]
Example configuration:

So the algorithm works much faster than mine, and that is because it does not spread mass evenly. As shown above the white squares are nodes which have edges with maximum flow. This does not necessarily mean that the node is overloaded, and as you can see there are alternative flows that are not at full capacity.
However since my goal was to simply find the overloaded nodes and destroy them (and floating parts) this does not matter so much.


What is instruction throughput and instruction latency?

Latency = time from the start of the instruction until the result is available. If your division has a latency of 26 cycles, and you calculate (((x / a) / b) / c), then the result of the division by a is available after 26 cycles. That's when the division by b can start, with the result available after 52 cycles, and the result of dividing by c is available after 78 cycles.

The throughput is one division every six cycles, which means you can start another division every six cycles. So if you want to calculate x/a, y/a, z/a, u/a, v/a, the five divisions can start at cycles 0, 6, 12, 18, 24, and the results are available at cycles 26, 32, 38, 44, and 50.

As an exercise, figure out how long it takes to evaluate (((x / a) / b) / c), (((y / a) / b) / c), (((z / a) / b) / c), (((u / a) / b) / c) and (((v / a) / b) / c) .


As long as there's a computable mapping between the two encodings, changing from one to the other won't affect computability, since computable functions compose. If there isn't a computable mapping between the encodings, you can't effectively use at least one of them, since there's no way to figure out what the encoding of your input should be in that scheme. (For example, suppose you come up with a coding of graphs that isn't computably translatable from the adjacency matrix. How would you use that encoding? If I give you a graph, you can't figure out what string encodes it.)


Decidability of a problem concerning polynomials

I'm not knowledgeable in that field either, but I think I can provide a non-constructive answer.
The first-order theory of real closed fields is decidable. Your problem can be stated as a system of algebraic equations and inequations over the real algebraic numbers. Consider $2 (\deg P + \deg Q)$ variables $x_1,\ldots,x_{\deg P}, y_1,\ldots,y_{\deg P}, x'_1,\ldots,x'_{\deg P}, y'_1,\ldots,y'_{\deg P}$. You want to know whether the following system is satisfiable:
$$\begin{align*}
  P(x_j+i\,y_j) &= 0 & \text{for \(1 \le j \le \deg P\)} \\
  Q(x'_k+i\,y'_k) &= 0 & \text{for \(1 \le k \le \deg Q\)} \\
  x_j^2 + y_j^k &\le x_1^2 + x_2^2 & \text{for \(2 \le j \le \deg P\)} \\
  {x'}_j^2 + {y'}_j^k &\le {x'}_1^2 + {x'}_2^2 & \text{for \(2 \le k \le \deg Q\)} \\
  x_1^2 + y_1^2 = {x'}_1^2 + {y'}_1^2 \\
\end{align*}$$
The first two equation families express that the $x_j+i\,y_j$ and $x'_k+i\,y'_k$ are roots of the polynomials, the next two inequation families express that $x_1+i\,y_1$ and $x'_1+i\,y'_1$ have the largest absolute value, and the last inequation compares these largest absolute values.
It is decidable whether this system is satisfiable: your problem is decidable. However, this statement is probably not the most efficient way to go about it.
A more useful answer probably involves the theory of Gröbner bases. If you're trying to solve that problem for yourself, I think reading the first few chapters of any computational algebra book will give you the requisite background. If you're just aiming to solve your underlying problem, there is probably an off-the-shelf algorithm you can implement.


Lexicographical position of a string in its type class

This is yet another example of enumerative encoding. Suppose that $x$ has $\alpha_i$ symbols of type $i$. The size of $S$ is then the multinomial coefficient $\binom{n}{\alpha_1,\ldots,\alpha_M}$. Pascal's identity reads
$$ \binom{n}{\alpha_1,\ldots,\alpha_M} = \sum_{i\colon \alpha_i \neq 0} \binom{n-1}{\alpha_1,\ldots,\alpha_i-1,\ldots,\alpha_M}. $$
In the lexicographic ordering of $S$, the strings starting with $1$ (if any) constitute the first $\binom{n-1}{\alpha_1-1,\ldots,\alpha_M}$ positions, the strings starting with $2$ (if any) constitute the following $\binom{n-1}{\alpha_1,\alpha_2-1,\ldots,\alpha_M}$ positions, and so on. So $x_1$ already gives you an interval of length $\binom{n-1}{\alpha_1,\ldots,\alpha_{x_1}-1,\ldots,\alpha_m}$ to which $x$ belongs in the lexicographical ordering of $S$. To find its location within the interval, recurse: examine $x_2$, then $x_3$, and so on.

Here is the resulting algorithm, returning a $0$-based position:

Set $P \gets 0$.
For $i=1,\ldots,n$:

Set $P \gets P + \sum_{j < x_i, \alpha_j \neq 0} \binom{n-i}{\alpha_1,\ldots,\alpha_j-1,\ldots,\alpha_M}$.
Set $\alpha_{x_i} \gets \alpha_{x_i} - 1$.

Return $P$.


An NFA with no equivalent DFA with fewer than $2^n$ states: Example and Proof

The proper way to do this proof is using Myhill–Nerode theory, which I will now explain. For a regular language $L$, say that $x,y$ are inequivalent if there exists a word $z$ such that $xz \in L$ and $yz \notin L$, or such that $xz \notin L$ and $yz \in L$. In every DFA accepting $L$, the state that is reached after reading $x$ is different from the state that is reached after reading $y$ (exercise). Hence, if we find a collection $x_1,\ldots,x_M$ of words such that $x_i,x_j$ are inequivalent for all $i \neq j$, then every DFA for $L$ must contain at least $M$ states (exercise).

For your language $L = \Sigma^* 1 \Sigma^{n-1}$, you can take as your collection of words the set of all words of length $n$. If $x,y$ are two different words of length $n$ then $x_i \neq y_i$ for some $i$; say $x_i = 0$ and $y_i = 1$. Then $x 0^{i-1} \notin L$ (since the $n$th from last bit is $x_i$ = 0), whereas $y 0^{i-1} \in L$ (since the $n$th from last bit is $y_i$ = 0). This completes the proof.


How to decide whether a language is decidable when not involving turing machines?

It might come as a surprise to you, but the language $$L=\{k\in\mathbb N :\text{the binary expansion of} \sqrt2\text{ contains $k$ consecutive $1$s}\}$$ is decidable, even if we could not construct an algorithm that can demonstrate whether the binary expansion of $\sqrt2$ contains $k$ consecutive $1$s or not given arbitrary $k$.

As Yonatan N indicated, let us take a closer look at $L$. There are two disjoint cases.

$L$ is $\mathbb N$. Then $L$ is trivially decidable. For any given $k$, just return "Yes".
$L$ is not $\mathbb N$. Then there are some numbers in $\mathbb N$ that is not in $L$. Let $m$ be the minimum of such number. Then $L$ must be $\{1, 2, 3, \cdots, m-1\}$. Why?

Since $m>2$ is the minimum number that is not in $L$, $m-1$, which is a number smaller than $m$, must be in $L$. That is, $\text{bin}(\sqrt 2)$ contains $m-1$ consecutive $1$s. So it also contain $k$ consecutive $1$s for all $k\le m-1$.
Since $\text{bin}(\sqrt 2)$ does not contains $m$ consecutive $1$s, it does not contain $k$ consecutive $1$s for any $k\gt m$. That is, $k\not\in L$.

Now we can construct an algorithm that decides $L$. For any given $k$, check whether $k\lt m$. If yes, return "Yes". Otherwise, return "No".

In either case, there exists an algorithm that decides $L$. Hence $L$ is decidable.

Most people, I believe, felt a bit disoriented the first time when this kind of proof/conclusion was encountered. Or at least myself.

The essential point is we do not have to identify/construct/bind to one algorithm that decides $L$.  We do not have to understand fully what is $L$. All we need is there exists an algorithm that decides $L$, whatever $L$ turns out to be. This deviates from "the naive sense of decidability" that you might have even before you encountered the theory of computation/decidability/computability.

In particular, I do not know whether $L$ is $\mathbb N$ or not. Some people claimed to have proved that $L=\mathbb N$. I have not checked their proof, yet. Although it is certainly interesting to find whether $L=\mathbb N$, its result will not change the fact that $L$ is decidable.


An Exact Method for Solving Small Instances of XORSAT

I'll assume all of the equations take the form $x_i + \cdots + x_j = 0$ (i.e., always 0 on the right-hand side).  Then, your problem is: given a boolean matrix $M$, find a $x$ such that $Mx=0$ (modulo 2) that minimizes the Hamming weight of $x$.

I think this is equivalent to the problem of finding the minimum-weight codeword of a linear code.  That problem is NP-hard, and hard to approximate.  The equivalence: we think of $M$ as the parity-check matrix of a linear code; then $x$ is a codeword iff $Mx=0$, so your goal is to find a minimum-weight codeword. I encourage you to check my reasoning here.

There is a brute-force algorithm that runs in $O({n \choose w})$ time, where $n$ is the number of boolean variables and $w$ is the weight of the solution.  Assume that $w$ is known (in practice we can search over increasing values for $w$, as there aren't too many possibilities for it).  Then, you simply enumerate all ways to choose a subset of $w$ of the variables to set to true and check whether any of them work.

I think there is a meet-in-the-middle algorithm that takes exponential time but is faster than enumerating all possibilities.  The algorithm takes $O({n/2 \choose w/2} \sqrt{w})$ time and space, which is significantly better than the brute-force algorithm.  We'll write $x=u+v$, where $u$ is zero in its right $n/2$ bits and $v$ is zero in its left $n/2$ bits.  Then $Mx=0$ is equivalent to $Mu=Mv$.  We'll optimistically hope that $u$ has weight $w/2$ and $v$ has weight $w/2$; as I argue later, this happens with good probability.  So, we enumerate all ${n/2 \choose w/2}$ values of $u$ and store $Mu$ in a hashtable.  Then, for each of the ${n/2 \choose w/2}$ possible values of $v$, we compute $Mv$ and look it up in the hashtable.  If we find a match $Mu=Mv$, we've found solution $x=u+v$.  What's the success probability of this algorithm?  It is ${n/2 \choose w/2}^2 / {n \choose w} \approx \sqrt{2/(\pi w)}$.  Thus, if we repeat the algorithm about $\sqrt{\pi w/2} = O(\sqrt{w})$ times, with a different split of the $n$ coordinates into two equal-size subsets, we expect to find one solution.  Check my reasoning here -- this is from memory, so I can't vouch for this.

I believe there are algorithms in the literature that improve upon this scheme.  See, e.g., A new algorithm for finding minimum-weight words in a linear code: application to McEliece’s cryptosystem and to narrow-sense BCH codes of length 511 by Canteaut and Chabaud.  I think there has been more recent work but I'm not up to speed on it.


Integer set disjointness query on sketches with something like homomorphic hashing

Here is one simple idea -- not sure if it's practical.
Define $\mathsf{sketch}_n(X)$ to be a length-$n$ bitstring in which bit $i$ is set iff there exists $x \in X$ such that $x = i \mod n$. In practice, this means that inserting an element $x$ into a set involves turning on bit $x \mod n$. $\mathsf{disjoint}_n(\cdot)$ is defined as before. Then $\mathsf{shift}_n(\cdot, \delta)$ can be found by rotating the sketch right by $\delta$ bits (which can be done implicitly by storing a "rotation amount" in the data structure).
To reduce the false positive rate for membership tests (but increase the false negative rate for disjointness tests), you can store multiple bitstrings using different moduli -- e.g., if the moduli 100, 101 and 105 are used, there would be 306 bits in total. Intuition suggests relatively prime moduli would work best, but I have not tried looking into this in detail.


Is there a difference between the Bulk Synchronous Parallel Computing model and the Turing Machine

I don't know the particulars of the bulk synchronous parallel machine, but it is highly likely that both have the same computational power, that is, both machines compute exactly the class of recursive languages. The difference between the models lies in their corresponding complexity measures: a language that has a certain (time or space) complexity in one model could have a different complexity in the other model.


Interview q: Small possible length of stick from an array of stick lengths

Pragmatic approach: If I were given this in an interview, I'd formulate it as an integer linear programming problem and let an off-the-shelf ILP solver look for a solution for me.
Theoretical approach: As Dmitry mentions, this problem is related to bin packing.  (It's not identical because you require the bins to be full, whereas normal bin packing doesn't require that.)  Wikipedia says that there is a pseudopolynomial time algorithm for bin packing when the bin size is fixed, so you might look up that algorithm and see if it can be modified to apply to your problem.  You might also explore this paper:
Michel X. Goemans, Thomas Rothvoß. "Polynomiality for bin packing with a constant number of item types". SODA 2014.


Does making the keys of a hashtable the same length make the hashtable any better?

It makes the hash table unusable if I can’t have x and yz and abc as keys.


How exactly does a two stack pushdown automaton work?

To write a program that simulates a 2-PDA (which will be able to process any transition function $\delta$, not just a particular language) what you need to do is to implement a stack class, with just the operations that it is allowed to have. The simulator is essentially a loop that keeps track of the current state of $\delta$, which has to be stored in a suitable way, and of the current input symbol. You will receive as input the encoding of a function, and the input string.

As for the specific language at hand: the $\$$ in the middle actually makes it quite easy to design a transition function for this language. Without it, you would have a more difficult (and more interesting) problem. Just push symbols into one of the stacks and wait for the $\$$ to come up. You can then start using the other stack for the second half of the input string. Pop them both together. If in the process all symbols match, and in the end both stacks are empty, accept.

As you can see, we won't necessarily use the two stacks as if they stood for the content of the tape at each side of the head of a Turing machine.


Is there a difference between type safety and type soundness?

Type safety and type soundness are synonyms in most theoretical work. Type soundness is often formulated with respect to an operational semantics as (type) preservation and progress. Preservation states that if an expression has some type, then after a step of evaluation (via the operational semantics), the resulting expression can be given the same type. Progress states that if an expression is not a value, i.e. it is not fully evaluated, and it is well-typed, then it can be further evaluated.

"Type safety" and "soundness", but particularly "type safety", are also widely used by the (non-theoretical) programming community often in vague, ambiguous, or outright incorrect ways. For example, an API that uses enumeration types instead of allowing arbitrary strings when only a subset are meaningful, say, might be referred to as being "more type safe", but this statement doesn't make sense using the theoretical definition of "type safe" which is a binary property of the language as a whole.


Arithmetic on signed 12-bit octal number stored in sign magnitude form


Let's start the algorithm with these 3 sets:

$V$ = {all vertices}
$K$ = {}
$K'$ = {}

with the semantics:

$V$ stores unprocessed vertices
$K$ stores vertices known to be in the kernel
$K'$ stores vertices known to be outside the kernel

You're right that all vertices without incoming edges always belongs to the kernel. Add the them to the set $K$ & remove from $V$.

The next step is realizing that any vertices that can be immediately reached from vertices in the current $K$ must be outside the kernel. Add these to $K'$ &  remove from $V$.

Now, all the vertices that is left in $V$ without incoming edges (from other vertices inside $V$) again can be added to $K$ (and remove from $V$).

...

Repeat the process until $V$ is empty.


Prove correctness of the iterative algorithm

Let Nums be the value of the array after method execution,
and nums the initial value. Let,

P(i) = Nums[0..i-1] is the same as nums[0..i-1], but ignoring `val`.

Your algorithm is correct if P(nums.length) is true.
This can be shown by realising that P is true at the beginning
of the loop, and each iteration of the loop preserves P.

Initially, i = 0 in the for loop, and we have

   P(0)
 = Nums[0..0-1] is the same as nums[], but ignoring `val`.
 = Nums[] is the same as nums[], but ignoring `val`.
 = true

Next, assuming P(i), for $i \leq nums.length$, show P(i+1) ;-)

This is some of the work of the Hoare Calculus mentioned above.


Do all the cells in a recurrent neural network share learned parameters?

Indeed, the copies of a cell in an unfolded version share their learning parameters.

Why is it done this way? If the sequence processed by the LSTM is always the same lenght, we could conceivably get a better result with different parameters, but there are two key caveats:

Shared parameters are faster to learn
We want to be able to process cases when the lenght of the sequence processed is not fixed!


Computational Complexity and P vs. NP, A New Insight

No.  The paper appears to be total baloney.   I noticed multiple unjustified statements in my first 60 seconds reading the paper.  Don't waste your time with it.

arxiv is not peer-reviewed.  Some papers on arxiv are great; some papers are arxiv are terrible and a waste of time.  Its presence on arxiv says very little about its quality.  It's like finding a paper on someone's personal website.


Understanding How Double Precision Numbers are Stored in a Computer

I don't know how old your book is, but some architectures (I know of the early SPARCs, there may be others) only had 32 bit floating point registers. Double precision instructions used pairs of registers for storage. This became much less common on general-purpose hardware when 64-bit integer registers became the norm.

If anything, we have the converse today, thanks to vector/SIMD operations. If you have, say, a 128 bit vector register, you can fit four single-precision or two double-precision numbers in it.


Single big BST vs multiple smaller BSTs? Which is faster for search?

Searching among $N$ in a BST takes (roughly) $\log_2 N$ comparisons. So searching in $10^9 \approx 2^{30}$ takes around 30 comparisons. Searching in $10^6 \approx 2^{20}$ takes 20 comparisons. The cost of farming out the work to 1000 processors, collecting the results and figuring out the answer is surely costlier than 10 comparisons.


Channel Capacity or maximum data rate is the maximum rate at which data can be transmitted over a given communication link, or channel.

In general, information is conveyed by change in values of the signal in time. So more the frequency of a signal, more is the achievable data rate.

For a communication channel,

Δf⋅Δt≈1

To transmit one signal, a pulse of length Δt (in time) is required. If one signal represents one bit, then the data rate is about 1/Δt. So the maximum data rate in bit/second is about the same as the band width Δf in Hertz.

But this is an incredible underestimate of the information capacity of a transmission system. It assumes that you are sending rectangular shaped pulses.
Using different encoding schemes, more than one bit can be represented by one cycle of signal.

The channel capacity of a channel increases proportionally with the bandwidth. But in practice, we cannot keep increasing the signal bandwidth infinitely. Apart from this, there are other standard transmission constraints in the form of different channel noise sources that strictly limit the signal bandwidth to be used. According to Shannon Hartley equation, the only limit to data rate in a given bandwidth is, the Signal to Noise Ratio.

Using Shannon formula we can obtain an absolute limit of the maximum data transmission rate.

$C = B + log_2(1 + S/N)$

C - Channel capacity
B - Bandwidth
S - Average received signal power over the bandwidth
N - Average noise over the bandwidth


In what follows, I'm going to assume that $x \ge 0$, and then try to put that back later.

First, we'll simplify the notation a little. The length of the code for $x$ should be:

$$L_m(x) = a + b \left(\frac{x}{\sigma}\right)^2 + \log_2 \sigma$$

where:

$$a = \frac{\log_2 2\pi}{2} \approx 1.325$$
$$b = \frac{1}{2 \ln 2} \approx 0.721$$

This suggests that you should divide $x$ by $\sigma$, encode the remainder in $\log_2 \sigma$ bits, then encode the quotient $q$ in $a + bq^2$ bits (say, using arithmetic coding). Instead of storing $20002$ codes using Yuval's method, you now only need $20$ or so.

In a sense, what you're doing here is converting the normal distribution to a standard distribution. Moreover, if you move $\sigma$ to the nearest power of 2, the division can be done using bit shifts and masks. $\sigma=1024$ is close enough to $1000$, so that part of the operation is extremely cheap.

However, there is a catch. To arithmetic code $L_0(10)$, you need about 60 bits. On a 64-bit machine, this is pushing the practical limit of an efficient arithmetic coder. So you should probably consider partitioning the space for more efficient encoding.

One possibility is to use binary arithmetic coding, with one binary symbol per $\sigma$. The probability that $x$ is within $\sigma$ of the mean is $0.6826895$ (or so). The probability that $x$ is within $2\sigma$ given that it is not within $\sigma$ is $0.85660651$ (or so), and so on. I calculate the code length for the $8\sigma$ symbol to be around 27.3 bits, and trying to calculate the length for $9\sigma$ breaks into numeric instability using the simple calculation that I did.

No matter what you try, representing numbers that are more than about $8\sigma$ from the mean is going to be difficult to do well, but given that those numbers are extremely rare, perhaps you should just fall back to a universal code (e.g. one of the Elias codes) for that case.

So in summary, here's the representation that I'd try.

Divide $\left| x \right|$ by $\sigma$. Call the quotient $q$ and the remainder $r$.
Store the sign of $x$ as a single bit.
Arithmetic encode $q$ using a sequence of binary variables:

Use a single binary symbol with $p_0 = 0.6826894921370859$. Store $0$ if $q=0$, or $1$ if $q>0$.
If you stored $1$, use another binary symbol with $p_0 = 0.8566065013011934$. Store $0$ if $q=1$, or $1$ if $q>1$.
...and so on. Stop when you get to $q \ge 8$).

If $q<8$, binary encode $r$ in $\log_2 \sigma$ bits.
If $q\ge 8$, use a universal binary code of choice (Elias gamma is a popular choice) to store $x - 8\sigma$.

Now having said all this, a common approach used in many compression standards, which works fairly well when $\sigma$ is small, is to use exp-Golomb coding. It's not theoretically perfect, but seems to work well in practice.


Given N positive integers are they the integers 1-N : What is the relationship between this problem and NP?

Recognizing that a path is a Hamiltonian path is easy. Finding one in the first place may be hard (the number of candidates is large).
The defining property of problems in NP is that verifying a solution is "easy" (in P). Your problem is one part of verifying a solution of a Hamiltonian path problem. (You also have to verify that the path is a subgraph of the input graph.)


Your first algorithm as written cannot be correct since it has a time complexity of at least $\Omega(n \log^2 n)$ and the solution to your recurrence equation is $T(n)=\Theta(n)$. To see this notice that at least half of the $\Theta(n)$ leaves of the recursion tree requires time $\Theta(\log^2 n)$ to execute the two nested for loops at the end.

Your second algorithm is correct but it is overcomplicated and has a misleading name.

Assuming that $n$ denotes the value of the input (and not its size), that arithmetic operations require constant time, and that / denotes integer division, a simple algorithm is:

Input: a positive integer n.

f(n):
   if(n==0)
      return;

   f(n/2);
   f(n/2);

   for(i=1; i<x; i=i*2)
      for(j=1; j<x; j=j*2)
         no-op;


Time interval correction for step detection algorithm

I managed to solve the problem of the algorithm by using a different approach. Algorithm is not clear on what is happening with the initial values or how to reliably capture a set of peak/valley candidates and how to deal with them.

Therefore, we decided to use only magnitude part of the paper, which radically simplifies the whole algorithm, and in fact works great ( assuming you are getting reasonable sensor readings).


Goldbach Conjecture and Busy Beaver numbers?

The statement is about infinitely many numbers, but its demonstration (or refutation) would have to be a finite exercise. If possible.

The surprise may come from the (false) assumption that finding BB(100) would be a "theoretically easier" problem, only made impossible for practical reasons - since there are so many machines, and they can run for such a long time before stopping, if at all - after all, they're just machines...

The truth is that discovering BB(n), for n large enough, has to be an unsurmountable task, for both theoretical and practical reasons.


There are two different "laws" being graphed here, Moore's law, and Dennard scaling.  Moore's law is an economic observation, made by Gordon Moore in 1965, that predicts that the number of transistors on a die will tend to double about every two years.  It does not seem to be slowing down (yet).  While there are reasons to believe that transistors will stop scaling down soon (14nm is 140 Angstroms (about the width of 140 hydrogen atoms)) it may be possible to continue Moore's law scaling for some time, either by making bigger chips (what Moore originally predicted) or by stacking multiple layers of transistors in the 3rd dimension.

Dennard Scaling, on the other hand, is an observation, made by Robert Dennard in 1974 that every time you scale down the width of a CMOS gate by a factor of 2, you can reduce both supply voltage and the threshold voltage by a factor of 2, the clock frequency can improve by a factor of 2, and the power density will stay constant.  (Or you can scale down the voltage by less than 2, and you'll get a better than 2x clock frequency boost, but an increase in power.)  When Dennard's observation was made a CMOS transistor was about 5 micron = 5000 nm wide.  (So we've scaled transistor widths by a factor of about 360 in about 40 years.)

The limit that showed up in the early 2000s has to do with threshold voltage.  Clock frequency (at a particular transistor size) is at best proportional to
$V_{dd} - V_{th}$ (supply voltage minus threshold voltage), but as you scale $V_{th}$ down leakage current (and power) increases exponentially.  That was fine from 1974 to about 2000 because $V_{dd}$ was much larger than $V_{th}$.  (In 1974 $V_{dd}$ was usually about 12V.)  So we could hold $V_{th}$ at around a volt or so, and just change $V_{dd}$.  But now with $V_{dd}$ around 1.3V and $V_{th}$ around .5V, we can't scale voltage much anymore (without dramatically increasing leakage power.)


Why is Savage's Vertex Cover algorithm a 2-approximation?

First of all, you have to show that $V_C$ is a vertex cover. This is because any edge touching a leaf also touches an internal node.

Next, we show that the DFS tree has a matching of size at least $|V_C|/2$. Since each vertex cover must contain at least one vertex from each edge in the matching (since any one vertex covers only one edge from the matching), this shows that the minimum vertex cover has size at least $|V_C|/2$, so we get a 2-approximation algorithm.

It remains to show that any tree $T$ has a matching of size at least $I(T)/2$, where $I(T)$ is the number of internal node. The proof is by induction on $|T|$. If $T$ contains one vertex then $I(T)=0$ and so there is nothing to prove. Now suppose that the tree contains a root $r$ and subtrees $T_1,\ldots,T_n$. Let $r_1$ be the root of $T_1$, and let $S_1,\ldots,S_m$ be the subtrees of $T_1$. The matching we are going to construct consists of matchings in $S_1,\ldots,S_m,T_2,\ldots,T_n$ together with the edge $(r,r_1)$ (you can check that this is indeed a matching). This matching contains at least $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2$ many edges. We obtained the forest $S_1,\ldots,S_m,T_2,\ldots,T_n$ by removing two vertices $r,r_1$, so $I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n) = I(T)-2$. This completes the proof since $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2 = 1+(I(T)-2)/2 = I(T)/2$.


How to scale down parallel complexity results to constantly many cores?

If you assume that the number of processors is bounded by a constant, then you are right that a problem being in NC does not mean much in practice.  Since any algorithm on a PRAM with k processors and t parallel time can be simulated with a single-processor RAM in O(kt) time, the parallel time and the sequential time can differ only by a constant factor if k is a constant.

However, if you assume that you can prepare a computer with more processors as the input size grows, then a problem being in NC means that as long as you can prepare more processors, running time will be “very short” or, more precisely, polylogarithmic in the input size.  If you think that this assumption is unrealistic, compare it to the assumption of unbounded memory: actual computers have only finite amount of space, but in the study of algorithms and complexity, we almost always assume that a computational device does not have a constant upper bound on space.  In practice, this means that we can prepare a computer with more memory as the input size grows, which is how we usually use computers in the real world.  NC models an analogous situation in parallel computation.


Cover $n$ points in the plane with $k$ circles of radius $1$

Use a greedy algorithm to cover your points with circular disks of radius 2. In other words, repeatedly choose an uncovered point, and cover it with a circular disk of radius 2 centered at the point. Now cover each of your disks with seven disks of radius 1.

Why does this work? Suppose that you covered the points using $k$ circular disks of radius 2 centered at the points $p_1,\ldots,p_k$. It is not hard to check that the distance between any two different points $p_i,p_j$ is larger than 2 (otherwise $p_j$ would have been covered by the disk around $p_i$, assuming $i < j$), and so no circular disk of radius 1 can cover both $p_i$ and $p_j$. This implies that $k$ circular disks of radius 1 are needed to cover the points $p_1,\ldots,p_k$, and so at least $k$ are needed to cover the original set of points. The solution produced by the algorithm uses $7k$ circular disks.


What is the difference between complexity theory and computability theory?

Put succinctly, computability theory is concerned with what can be computed versus what cannot; complexity is concerned with the resources required to compute the things that are computable.

As such, the fields are somewhat disjoint. Complexity theory is interested in a fine-grained classification of computable problems, with "it's uncomputable" as a worst-case scenario where we throw up our hands and give up. Computability theory (though one wouldn't realise this from an undergrad course) is interested in a fine-grained classification of uncomputable problems, with "it's computable" as the case at the bottom that's left to others to deal with.

However, there is some overlap of techniques, at least at a high level.  In both cases, one typically uses the existence of an algorithm to demonstrate membership in a class and proofs of hardness are usually by reductions. Diagonalization also plays a role in both, proving things like the time and space hierarchy theorems in complexity, and the undecidability of halting problems in computability.


How does a File System handle an internal edit to a file?

Filesystems typically don't handle internal edits to files as you describe them.  When you edit a program file, a text editor will pull the whole file into memory, allow you to make modifications to a buffer and then write the whole thing back out to disk.  Actual file I/O operations are usually quite limited by the operating system, e.g. overwrite existing file contents, truncate the file to a smaller size discarding what's beyond EOF, and appending to the file.

Text editors manage the business of allowing arbitrary insertion and deletion of lines and blocks of text.  These programs use an assortment of data structures, from arrays of lines to gap buffers to more elaborate structures, depending on the editor.  An old Blogspot article describes how a few popular text editors work internally; I commend you to it and to the source code of the many open-source text editors available if you wish to learn more.


Difference between Tail-Recursion and structural recursion

Structural recursion: recursive calls are made on structurally smaller arguments.
Tail recursion: the recursive call is the last thing that happens.

There is no requirement that the tail recursion should be called on a smaller argument. In fact, quite often tail recursive functions are designed to loop forever. For example, here's a trivial tail recursion (not very useful, but it is tail recursion):

def f(x):
   return f(x+1)

We actually have to be a bit more careful. There may be several recursive calls in a function, and not all of them need to be tail recursive:

def g(x):
  if x < 0:
    return 42             # no recursive call
  elif x < 20:
     return 2 + g(x - 2)  # not tail recursive (must add 2 after the call)
  else:
     return g(x - 3)     # tail recursive

One speaks of tail recursive calls. A function whose recursive calls are all tail-recursive is then called a tail-recursive function.


Call by reference is cheaper than call by value since you don't need to copy your object. That's why we prefer it when possible. If the thread needs to change its local copy, then you need it to have a copy of its own, which is the same as call by value.


The role of the root switch after Spanning Tree Protocol has established a tree network in a LAN?

I can find no requirement that all traffic is routed through the root switch. For example, in A<-->B<-->C, with C the root switch, traffic fom A to B does not pass through the root switch.

The spanning tree protocol first selects a root switch. In Cisco, this is the switch with the lowest bridge ID. So the selection of the root is arbitrary. Now a tree is built that connects all switches, without creating cycles. Even if initially a minimum spanning tree is created because links with maximum bandwidth (minimum cost) are selected, at some future point this may no longer be when a link fails and a redundant link or path is enabled. This new link may result in the total tree not being a minimum spanning tree anymore. I can imagine that reconfiguring the whole tree to be minimum again can cause unwanted overhead.

I found this information on Wikipedia and Cisco. I am not a network guru so my answer may not be complete. I found no information that the initial tree created is minimum though it seems to meet the requirements and seems to follow e.g. Kruksal's algorithm.


Convert an IF statement in Mixed Integer Programming

Let $x_i$ represents the quantity bought from the $i$-th supplier, and
consider the following scenario: the price of the 2nd supplier is 170\$ per tonne but, if you buy at least 300 tonnes, then you get to choose a non-negative quantity $d \le x_2 - 300$ and you get a 20\$/tonne discount on $d$ tonnes, otherwise $d=0$ (i.e., you get no discount).
Clearly this is equivalent to your original problem since, given $x_1, \dots, x_3$, it is always convenient to maximize $d$.
You can model this as follows:
$$
\min 150x_1 + 170 x_2 + 170x_3 - 20d \quad \mbox{s.t.}\\[6pt]
\begin{align*}
x_1 &\le 100 \\
x_2 &\le 400 \\
x_3 &\le 1600 \\
x_1 + x_2 + x_3 &= 800 \\[6pt]
100 y &> x_2 - 300 & (1)\\
300 y &\le x_2 &(2)\\[6pt]
d &\le x_2 - 300y &(3)\\
d &\le 100y &(4)\\[6pt]
x_1, x_2, x_3,d &\ge 0 \\
y &\in \{0,1\}
\end{align*}
$$
Notice that $y$ is a binary variable that equals $1$ if and only if $x_2 \ge 300$. Indeed, if $x_2 \ge 300$ the constraint $(1)$ is satisfied only when $y=1$ (recall that $x_2 - 300$ is at most $100$), and the constraint $(2)$ simplifies to $300 \le x_2$, which is true. If $x < 300$ then the constraint $(2)$ forces $y=0$ and the constraint $(1)$ simplifies to $0 \ge x_2 - 300$, which is true.
If $y=0$, then $d$ must be $0$, and this is enforced by constraint $(4)$ which becomes $d \le 0$ (recall that $d$ is non-negative), while $(3)$ is always satisfied. If $y=1$, then constraint $(3)$ enforces $d \le x_2 - 300$, which also implies constraint $(4)$ since $d \le x_2 - 300 \le 100 = 100y$.


Is there any Boosting algorithm with closed-form solutions?

Basically: no.  Boosting is a "meta-method".  If you have a weak learner (an algorithm for learning), it is a way of taking advantage of that weak learner algorithm iteratively to do better at learning some concept than the weak learner would do on its own.

Many/most weak learners don't have a closed-form solution for the model they build; instead, their learning algorithm may fundamentally rely upon iterative methods, optimization algorithms, or other techniques.  As a result, boosting with such a weak learner won't have a closed-form solution, either.