Is structural induction on terms applicable when a function is involved?

You probably shouldn't write $\cfrac{\phi(t)\Downarrow \phi(u)}{t\Downarrow u}$ for "For any terms $t,u$, $\phi(t)\Downarrow \phi(u)$ implies $t\Downarrow u$".

I'll take a concrete example: Terms are made using $0,S,+$. And there are six rules:

$$\cfrac{}{0 \Downarrow 0}(0)\hspace{2em}\cfrac{x\Downarrow y}{Sx \Downarrow Sy}(S)\hspace{2em}\cfrac{x\Downarrow y}{x+0 \Downarrow y}(+0)\hspace{2em}\cfrac{x\Downarrow y}{0+x \Downarrow y}(0+)\hspace{2em}\cfrac{x+y\Downarrow z}{x+Sy \Downarrow Sz}(+S)\hspace{2em}\cfrac{x+y\Downarrow z}{Sx+y \Downarrow Sz}(S+)$$

Note that $(0+)$ and $(S+)$ are superfluous (but do not break the uniqueness of the normal form).

I'll provide three examples where different proof techniques apply.

Let's take $\phi(x)=Sx$.

Suppose that for some $a$, $Sa=\phi(a)\Downarrow \phi(b)=Sb$. The only rule that allows you to prove this is the rule $(S)$ with $x=a$ and $y=b$ (because it's the only rule that can have successor on both sides of $\Downarrow$ in the conclusion), so you must have $a\Downarrow b$, which is what you want. So you can prove that "For any terms $t,u$, $\phi(t)\Downarrow \phi(u)$ implies $t\Downarrow u$".

You were able to prove it without even using induction because the definition of $\phi$ wasn't inductive.

Remark

But you can not compose rules to get $\cfrac{St\Downarrow Su}{t\Downarrow u}$ (because there are more $S$ in the conclusion than in the premise and all rules have at most as many $S$ in the conclusion as in the premise).

Your result is a meta-theorem but not a theorem (because it's not just a combination of the rules).

A theorem would, for example, be $\cfrac{}{S0\Downarrow S0}$ (that you get by composing $(0)$ and $(S)$ or $\cfrac{x\Downarrow y}{x+S0\Downarrow Sy}$ (that you get by composing $(+0)$ and $(+S)$).

Let's take another example: $\varphi(0)=0$, $\varphi(Sx)=SSx$ and $\varphi(x+y)=\varphi(x)+\varphi(y)$.

Now suppose that $\varphi(a)\Downarrow \varphi(b)$.

We'll prove $a\Downarrow b$ by induction on the size of the proof of $\varphi(a)\Downarrow \varphi(b)$.

If it's of size $1$, then it has to be just an application of $(0)$ so $\varphi(a)=0=\varphi(b)$ and so $a=0=b$ and $(0)$ gives us the proof we want.

If it's of size $>1$, the last rule is not $(0)$ so you do case analysis and apply the induction hypothesis on the premise of the rule. You'll have to do case analysis, but you should be able to prove that it works.

There should be some case where you can do induction on terms to prove the thing but I couldn't find one. It feels more natural when you have a small step transition system $\to$ and define a big step one $x\Downarrow y$ by $x\to^* y$ and for any $z$, $y\not\to z$. Then, it you manage to prove that $\phi(x)\to \phi(y)$ implies $x\to^+ y$ and that $x\to y$ implies $\phi(x)\to^+\phi(y)$, you will get that $\phi(x)\Downarrow \phi(y)$ implies $x\Downarrow y$.

The main thing you should remember is that "case analysis" < "induction on terms" < "induction on proofs" in terms of what you can proove but often, the number of cases you have to handle often grows. So you should try the proofs techniques in that order until you get one that works.


Dijkstra algorithm vs breadth first search for shortest path in graph

BFS does not fail if a cycle is detected. http://en.wikipedia.org/wiki/Breadth-first_search
Dijkstra's doesn't calculate all paths from A to F either. It stops when it finds the shortest path from A to F.
In an unweighted graph, you can use BFS to search for the shortest path from A to all other nodes in the same run too! (just don't make it stop as soon as it finds F)
You can use a BFS type algorithm to find the shortest path if you know all lengths are integers less than a 'small' number k in O(k(v+e)) time by replacing every edge (u,w) of length n with a path of n-1 nodes between u and w, the length of each edge in the path is 1.

Hope this helps.


The min number of distinct sequence numbers required to ensure correct operation of the ARQ scheme is

Your interpretation of bidirectional is correct.

First of all, it should be bi-directional. Here is the reason. The receiver window size M is not equal to sender window size N so it must be bidirectional. If it is unidirectional, then the receive window should be 1 for Go-Back-N protocol and N for Selective-Repeat protocol.

Then it is very straightforward: the minimum sequence number should be N+M. For example, the sender could choose [0, N-1] as sequence numbers while the receiver could choose [10000, 10000+M-1] as sequence numbers.

One thing to note, this problem is not strict. If you use Selective-Repeat protocol, then the minimum sequence number should be 2*(N+M) to handle both new packet and a retransmission.


Expected gain of a game of chance with differently-priced tokens

They probably meant you to solve it using dynamic programming. Since I'm guessing this is an exercise, I won't say anything more on this front. Also, your program is incorrect: it doesn't consider the actions of Bar.

The game is not really a game of strategy, since there are no choices involved, only chance. In order to compute the expected value that Foo gets, it is enough to compute the probability that Foo takes each particular item. Let $p_{a,b}$ be the probability that Foo takes an item which is the $a$th from the left, $b$th from the right ($a,b \geq 0$, total number of elements is $a+b+1$). Then
$$
\begin{align*}
p(0,0) &= 1, \\
p(0,1) &= 1/2, \\
p(1,0) &= 1/2, \\
p(1,1) &= 1/2, \\
p(0,b+2) &= 1/2 + p(0,b)/4, \\
p(a+2,0) &= 1/2 + p(a,0)/4, \\
p(1,b+2) &= p(0,b+1)/2 + p(1,b)/4, \\
p(a+2,1) &= p(a+1,0)/2 + p(a,1)/4, \\
p(a+2,b+2) &= (p(a+2,b)+2p(a+1,b+1)+p(a,b+2))/4.
\end{align*}
$$
You could precompute the requisite values for $a+b+1 \leq 2000$ and then your program will be blazingly fast.

It turns out that for fixed $c$, $p(c,n-c)$ tends to a limit $p_c = 1/2(1 + (-1)^c/3^{c+1})$. To see why, note first that $p_0$ is the ability that if you and a friend alternate tossing fair coins, yours will come up HEAD first. There are many ways to see that $p_0 = 2/3$. Next, we have the formula $p_{c+1} = p_0 (1-p_c) + (1-p_0) p_c$ (exercise), from which the formula for $p_c$ follows by induction.


Can two deterministic turing-machines avoid each other in a sidewalk?

You have to teach the robots how to keep track of their identity, either by remembering the initial position, or by signing their messages.
Then they can perform their individual programs.
Something like this:

t = "turn"
m = "move"
program1 = [t, m, t, t, t, m, m, m, m, m, m, m]
program2 = [t, t, t, m, t, m, m, m, m, m, m, m]

def brain(otherPos, myPos, message):
    if message == "1":
        return (program1.pop(0), "2")
    else:
        return (program2.pop(0), "1")


Are subsets of $PSPACE$ closed under common operations

$SPACE(n^k)$ is closed under Kleene star. Just enumerating all possible partition (which can be done in linear space, or at most quadratic or $nlogn$ space), then decide each partition using the $n^k$-space machine.

This class is not closed under poly-time reduction. Prove by padding technique. This part would be found here at CS.SE or CSTheory.SE


Solving recurrence relation where the $f(n)$ has some constant factor $k$ where $0 < k < 1$

The error is where you claim that $kn=n^c$ where $0<c<1$.  This is not correct.    Even when $k<1$, it is still the case that $kn=\Theta(n)$; it is not $O(n^c)$ for any $c<1$.  (Check the definition of big-O notation.)


Scientific soundness of computer science papers

This is a complex issue that affects all areas of science but has been getting higher visibility as the mainstream media has reported some cases in headlines. An answer seems to be better review systems. However, one might argue that nonsense papers are not necessarily a failure of the peer review system. All peer review systems must be human to some degree and all human systems are fallible/ subject to failure. any peer review system will have both false positives and false negatives in the sense of papers that were accepted but shouldnt be on 2020 hindsight, and papers that were rejected but were of acceptable quality. There is some increasing awareness/ sociological study of peer review systems. Cyberspace can in fact aid the process in some ways by increasing reviewers, increasing visiblity of reviews, adding rating systems, etc. and it can have downsides such as computational ease of creating fake submissions, increased AI capabilities to fool humans, etc.

An example of a CS specific peer review (meta-) analysis can be found in the recent NIPs experiment where peer reviewers were split into two groups, the same papers were given to each, and the overlap in acceptance/ rejection decision was measured. not unsurprisingly to many, results had quite high variance. Researchers overcome "false negatives" by resubmitting papers to other conferences. Unfortunately this NIPs experiment never seemed to be documented except across a lot of CS blogs and there is already some "link rot" of key links. It was announced informally at the conference and many insiders blogged on it including those participating. A full documentation might be considered "airing dirty laundry".

The NIPS Experiment
NIPs peer review experiment / many links


Calling heapify once isn't going to build a heap in one iteration  . Instead merge the two arrays which contain both heaps initially and call BuildHeap() procedure. You will get a heap in O(n) time.


Hint: The star of a language always contains the empty string. The complement of a language containing the empty string never does. With that in mind, look at the left and the right hand sides of your proposed equality.


The CPU has direct access to registers.  If A and B are already in the registers then the CPU can perform the addition directly (via the Arithmetic Logic Unit) and store the output in one of the registers.   No access to memory is needed.  However, you may want to move your data A and B from memory or the stack into the registers and vice-versa.  These are separate operations.
Registers can be of different sizes 8 to 64 bits, this depends on your CPU architecture. On a x86-64 CPU registers are 64bit thus addition of two 64bit numbers is a single operation.


I actually touched upon this in response to your previous question, but the general idea is that there are $n$ nodes in a binary tree, and starting from the root, at each depth there is: 1, 2, 4, 8, 16 ... maximum nodes. We see that at the greatest depth, there is (at most) half of all nodes ($n/2$). Remember that the height of a node is the distance from the node to a leaf, such that the height of a leaf is 0 (and the height of the root is the height of the tree). So for a leaf, $\frac{n}{2^{0+1}}=n/2$. For the root, $h=\log_2 n$, so $\frac{n}{2^{\log_2 n+1}}=n/n=1$. And the rest of the tree follows from there.


Using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant?

I don't think that will be effective.  I don't recommend this approach.  I think there's a significant risk that the machine learning will just learn to handle those specific synthetic variants, but not get any better at handling real speech.  It might even get worse, if you cause the ML to overfit to your synthetic variants.

The problem is that real speech has a lot of variety in how people express things.  Your synthetic examples are not going to capture that variety.  Training machine learning on synthetic examples that aren't representative of what it will see during deployment is not likely to be effective.  I suggest you try to obtain more realistic data, even if it can't be easily programmatically generated.


What is the proper runtime for visiting all outgoing edges in an adjacency list?

You're right that $\Theta(\deg^+ v)$ is a bit sloppy, but it is usually understood that $\Theta(\deg^+ v)$ is actually $\Theta(1 + \deg^+ v)$. Perhaps it's better to use the more accurate $\Theta(1 + \deg^+ v)$.

You're also right that more formally a $\Theta(\cdot)$ notation should state the underlying variable, but here there is only one variable and so no confusion can arise. Also, since $\deg^+ v$ is always non-negative, the simpler definition of $\Theta(\deg^+ v)$ - there exists $C > 0$ such that the running time is at most $C \deg^+ v$ - is unambiguous. That's also how we should understand expressions like $\Theta(n + m)$, where the two variables $n,m$ are independent.


There's a soft introduction in Rolf Niedermeier's book Invitation to Fixed Parameter Algorithms. Daniel Marx also has quite a few slides available on his homepage that contain short examples of modeling a problem in MSOL. One set of relevant slides is here. For more links, see a related question on CSTheory.


Space efficient representation of Regular graphs

No.  Even ignoring the requirement to answer queries, you can't store such a graph in $o(nk)$ space, assuming each word is $\Theta(\lg n)$ bits long (i.e., each word has space to store the index of a single vertex).

In particular, there are ${n-1 \choose k}$ ways to choose $k$ neighbors of a single vertex, so there are ${n-1 \choose k}^n$ possible $k$-regular graphs.  Now

$$\lg {n-1 \choose k}^n = n \lg {n-1 \choose k} = kn \lg(n/k) + \Theta(kn) = \Omega(kn \lg(n/k)).$$

Thus, information-theoretically, you need at least $\Omega(kn \lg(n/k))$ bits to store such a graph, or equivalently, at least $\Omega(kn \lg(n/k)/\lg n)$ words.  Notice that for $k=O(\log n)$, we have $\lg(n/k)/\lg n = \Theta(1)$.

Therefore, we find that we need at least $\Omega(kn)$ words just to represent all possible $k$-regular graphs, so there is no hope for a data structure with space complexity $o(kn)$, even if you ignore the query time requirement.


Question on the definition of computable function and non-terminating behaviour

The short answer is that: this part of Wikipedia's explanation kinda sucks.  Hey, it happens.  Wikipedia is pretty good, but it's not perfect.

The relevant part of the Wikipedia article says:

  Equivalently, computable functions can be formalized as functions which can be calculated by an idealized computing agent such as a Turing machine or a register machine. Formally speaking, a partial function $f : \mathbb{N}^k \to \mathbb{N}$ can be calculated if and only if there exists a computer program with the following properties:

  If $f(x)$ is defined, then the program will terminate on the input $x$ with the value $f(x)$ stored in the computer memory.
  If $f(x)$ is undefined, then the program never terminates on the input $x$.

The second sentence is not strictly wrong (that sentence does say that "a partial function can be calculated if...") but it sure seems misleading to include that sentence in an article on computable functions, as computable functions are required to be total functions.  Also, the combination of those two sentences leaves the wrong impression as it omits the requirement that $f$ be a total function.

Advice: if you're reading something in Wikipedia that seems confusing or doesn't seem quite right, check another source.  Check a good textbook -- they are a more definitive source for the precise definition of mathematical concepts.


I suggest you formulate this as an instance of integer linear programming (ILP).  Let $m$ be the largest number in $S_0$.  For each $i$ such that $1 \le i \le m$, introduce the zero-or-one variable $x_i$, with the intended meaning that $x_i=1$ means that $i \in S$ and $x_i=0$ means that $i \notin S$.

Now your constraints can be readily converted into linear inequalities: e.g., for each $s$ such that $2<s \le m$, we obtain that $x_s=1$ implies $\lor_{s_a,s_b} (x_{s_a}=1 \land x_{s_b}=1)$, where the disjunction is taken over all $s_a,s_b$ such that $1 \le s_a < s$ and $1 \le s_b < s$.  This can be converted into a linear inequality; see Express boolean logic operations in zero-one integer linear programming (ILP).  Also, for each $i \in S_0$, we add the requirement $x_i=1$.  Finally, we minimize $\sum_i x_i$.  Feeding this to an off-the-shelf ILP solver should yield a solution.

This should find the exact optimal solution, as long as the largest number in $S_0$ is not too large.  However, the running time is potentially exponential in $m$, the largest number in $S_0$.  I don't know if there is a polynomial-time solution.

(You could also formulate it as an instance of SAT instead of ILP.  This will require applying the Tseitin transform to convert the implication/disjunction into CNF, and it will require constructing an adder-circuit to add the requirement that the size of $S$ is at most $k$ and then doing binary search over $k$.  Then, you could feed it to an off-the-shelf SAT solver.  I have no idea whether this will work better than the ILP approach.)


Null Characters and Splitting the String in the Pumping Lemma

Yes, it is possible for $x$ or $z$ to be 'null', if by 'null' you mean the empty string. The empty string, $\epsilon$, is the string of length zero.

If the loop in the automaton (which is ultimately what the pumping lemma refers to) starts at the initial state and the initial state is also an accepting state, then strings of the form $y^i$ will be accepted, where $y$ is some string that will take you around the loop.

Whitespace plays no role in this theorem. Formal languages are defined over a given alphabet, in your case $\{0,1\}$. This is the only alphabet relevant for the question.  There is no preceding or trailing whitespace when talking about the pumping lemma. Spaces, tabs, return characters play absolutely no role.


Finding the shortest sublist that contains all search terms

Go over the list, and maintain the last occurrence of each word in the search list. Whenever you find a word in the search list, find the minimum last occurrence among all other words in the search list - this gives you a candidate closest occurrence, which you take note of if it's the best seen so far. In the end, return the best closest occurrence observed.

To execute this algorithm efficiently, you need an efficient array-like data structure which supports the following operations:

Change the value of item $i$.
Return the minimum value of all items other than item $i$.

When the search list is very short, you can just use an array. For large search lists, you can probably use a modified heap to support all of these operations in $O(\log m)$ time, where $m$ is the size of the search list. The end result is an $O(n\log m)$ algorithm, where $n$ is the size of the main list.


No. Bitcoin mining can be solved in $O(1)$ time. Unfortunately the hidden constant is quite large.


Landau Notation, Definitions: Limits vs. Corman's

To expand on Raphael's answer, both definitions are equivalent. The second definition is Landau-style (i.e. number theory style), while the first definition is computer science style.

The Landau-style definition is clearly more succinct and I personally prefer it. There are two reasons to state the definition in the computer science style:

Textbook writers don't want to assume that their readers know calculus.
The Landau-style definition for $f = \Theta(g)$ is more awkward: $\lim\inf f/g > 0$, $\lim\sup f/g < \infty$.


Is there any real difference between a compiler and an assembler?

An assembler translates assembly code to machine code. The translation is mechanical, and can be done in only one way. In contrast, a compiler has more freedom when it compiles the relevant programming language - it can optimize, for example, and even non-optimizing compilers produce different code. Also, compilers can be written in a way that separates the "front-end" (corresponding to the programming language) and the "back-end" (corresponding to the computer architecture), whereas with assemblers the two are always the same.


How do I prove that $3x^3 +2x + 1 $ is $\omega(x \cdot \log x) $

The easiest way is to check that $\lim_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} = +\infty$, which is a sufficient condition for $3x^3 + 2x +1 \in \omega(x \log x)$.

$$
\lim_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} =
\lim_{x \to \infty} \frac{3x^3}{ x \log x} =
\lim_{x \to \infty} \frac{3x^2}{  \log x} =
\lim_{x \to \infty}  6x^2
= +\infty.
$$


Yes, you could solve the summation in exact formula. Yes, you could obtain $T(n)=\Theta(n^3)$, a tighter asymptotic bound. Your professor would and should not forbid you to do  that.

The message from your professor could be that an upper bound such as $O(n^3)$ is as good as $\Theta(n^3)$ more often than not. For example, once we know an algorithm runs in $O(n^3)$ time without a huge constant multiplier on a problem of input size $n$ less than 1000, then we can be comfortable starting implementing the algorithm,  without worrying much that the code may take hours to run. A tighter asymptotic bound such as  $\Theta(n^3)$ will not help us move ahead significantly further. On the other hand, such a tighter asymptotic usually comes with a heavier price, which is not much heavier in this particular problem, though.


Don't understand minimax algorithm in terms of chess

In minimax you fully explore the game tree. So the answer to "which piece" is all of them. All possible moves for all movable pieces. And then it selects the minimum or maximum (depending on the depth) out of those options.

Obviously this isn't feasible which is why we never apply raw minimax to chess. It is always with other optimizations such as alpha-beta, and stopping after a certain depth and using a heuristic evaluation of that position instead of continuing.


Calculate the number of distinct permutations of length n in the closure of a language

The language $S^*$ is regular.  Therefore, it can be expressed by a DFA.  Now use Why isn't it simple to count the number of words in a regular language? or https://cstheory.stackexchange.com/q/8200/5038.


Closed-form Expression of the Expected value of the Cost of D&C Algorithm?

Expectation is additive, so your expectation equals
$$ E := 2E[w(O(x))] + 2E[w(O(O(x)))] + \cdots + 2E[w(O(\cdots(x)\cdots))] + 1, $$
where $w(\cdot)$ is Hamming weight.
Let's calculate $E[w(O(x))]$, again using the fact that expectation is additive. The probability that the $i$th bit of $O(x)$ is $1$ is exactly $1-p^2$, and there are $N/2$ of them, therefore $E[w(O(x))] = (N/2)(1-p^2)$. Similarly, the probability that the $i$th bit of $O(O(x))$ is $1$ is exactly $1-p^4$, and there are $N/4$ of them, and so $E[w(O(O(x))] = (N/4)(1-p^4)$. If $N = 2^n$, then we get
$$ E = 2^n (1-p^2) + 2^{n-1}(1-p^4) + \cdots + 2(1-p^{2^n}) + 1.$$
We can simplify this slightly by summing the geometric series:
$$ E = 2^{n+1}-1 - 2^n p^2 - 2^{n-1} p^4 - \cdots - 2p^{2^n}. $$


There is no one complexity for all suffix tree algorithms.  There are multiple algorithms, with different running times.  It is not helpful to talk about this as though there was only one complexity that applies to all algorithms for computing a suffix tree.  If you want to ask what is the running time of an algorithm for this task, you need to specify which algorithm you are asking about.

There are also multiple different models.  Some algorithms are designed for the regime where $\Sigma=\{0,1\}$ or where you have a small finite-sized alphabet (e.g., $|\Sigma|=256$), where it is reasonable to consider $|\Sigma| \in O(1)$.  Consequently, the running time for those algorithms might not include any dependence on $|\Sigma|$ -- which is reasonable if you assume that $|\Sigma| \in O(1)$.  Other algorithms are designed to work even when the size of the alphabet is large.  For those, the dependence on $|\Sigma|$ is at the heart of the problem.  Therefore, you'll also find some algorithms designed for the large-alphabet regime, and typically the running times that are quoted for those algorithms do show the dependence on $|\Sigma|$.  Therefore, when you read a paper on a suffix tree algorithm, if you want to use the algorithm on a situation where the alphabet size is large, you need to carefully examine the assumptions that were made during the running time analysis.  Does the quoted running time include the dependence on $|\Sigma|$?  Does the paper assume $|\Sigma| \in O(1)$?

Finally, the dependence on $|\Sigma|$ can depend on subtle aspects of how the data structures are instantiated.  Therefore, a high-level description of the algorithm is often not enough -- you often need to know how the tree is represented and how the individual steps are instantiated to tell what the dependence on $|\Sigma|$ will be.

I suggest you read What are the effects of the alphabet size on construct algorithms for suffix trees?

I also suggest you take a look at What is the difference between an algorithm, a language and a problem?, to help you think clearly about the difference between a problem vs an algorithm.


The Inverse of a function with logic operators

The above is an injective function so that means it has an Inverse but will that be p= ¬q?

Yup. We have $f(T)=F, f(F)=T$ so $f^{-1}(F)=T, f^{-1}(T)=F$, which means that $f^{-1}(q)=\lnot q$. In this case $f^{-1}=f$: they're the same function.


Definitions of an algorithm running in polynomial time and in strongly polynomial time

Before formal definitions, consider what the "strongly/weakly" classification aims to distinguish.

First, consider running either one on a Turing Machine. Both will run in a number of steps polynomial in the length of binary-encoded input. Consequently, the number of arithmetic operations performed by both would have to be polynomial in the length of binary-encoded input. Hence, for both Turing Machine running time would grow polynomially as the number of input values or their magnitudes grows. To emphasize the latter, note that even the strong one will take more TM steps on larger magnitudes (it needs to at least read the extra bits). Under no circumstance does one become exponential (as is the case with the unrelated pseudo-polynomial time). With a Turing machine alone, a fundamental difference doesn't seem detectable.

Now consider running each on an arithmetic machine where any operation is an arithmetic operation on whole numbers and arithmetic operations are $O(1)$. As you increase the magnitudes of the input numbers, the length of the binary-encoded input grows, and the running time of the weak algorithm would grow, however the running time of the strong algorithm would not change, because can be bound by the number of input numbers, which you are not changing (e.g. matrix multiplication vs. Euclid's GCD).

The set of algorithms that run in number of arithmetic operations polynomial in the number of input numbers is well-defined, but overlaps with the class of algorithms that take number of TM steps exponential in the length of binary-encoded input (see examples). Hence, for this set, the properties in the second paragraph would not hold. To exclude the unwanted intersection, we add a condition for a polynomial TM space [*].

In [1] this is stated in two ways:

The algorithm runs in strongly polynomial time if the algorithm is a polynmomial space algorithm and performs a number of elementary arithmetic operations which is bounded by a polynomial in the number of input numbers.
A polynomial algorithm is a polynomial space algorithm (in our standard Turing machine model) and polynomial time algorithm in the arithmetic model (see this question for a clarification).

This sub-classification of what are already "efficient" algorithms might be  be useful since physical computers resemble arithmetic machines more than Turing machines, so the sub-class might identify the algorithm that would run faster on a physical machine if their polynomial bounds in length of binary-encoded input are otherwise comparable (which is not the case in e.g. strong $O(n^3)$ vs. weak $O(n^2)$)

[*] The second condition is stated everywhere as polynomial space, whereas requiring polynomial time makes more sense to me. The former is more inclusive, but strange. Are there strongly-polynomial algorithms that take more than polynomial time? Note that repeated-squaring example takes neither polynomial time nor polynomial space.

[1] Grötschel, Martin; László Lovász, Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.


Scala as a language for Generic Programming

Exact answer is given on p. 17 of “Type classes as Objects and Implicits” by Oliveira et al.


Prove any binary tree with $n$ nodes has at least $1+\log_2 n$ levels

Hint: A binary tree with $1+h$ levels contains at most $1+2+2^2+\cdots+2^h = 2^{h+1}-1$ vertices.


A physical algorithm that finds all integer partitions of a number

Let us aim at generating the partitions in the following order (below, for $n=6$):

$$
\begin{align*}
& 6 \\
& 5 \, 1 \\
& 4 \, 2 \\
& 4 \, 1 \, 1 \\
& 3 \, 3 \\
& 3 \, 2 \, 1 \\
& 3 \, 1 \, 1 \, 1 \\
& 2 \, 2 \, 2 \\
& 2 \, 2 \, 1 \, 1 \\
& 2 \, 1 \, 1 \, 1 \, 1 \\
& 1 \, 1 \, 1 \, 1 \, 1 \, 1
\end{align*}
$$
We start with the partition $n$.

To generate a new partition, identify the last non-1 entry in the preceding partition (if there is no such, we’re done); reduce it by 1, and delete all following entries; complete it to a partition by repeatedly adding the maximum possible number, under the constraint that the partition is non-increasing.

You can check that this indeed generates all partitions.


A non-mechanical way to get an infinite decidable subset of a Turing-recognizable language?

Let $\Sigma$ be an alphabet, let $\mathcal{R}$ be the collection of all recognizable subsets (languages) of $\Sigma^{*}$ and let $\mathcal{D}$ be the collection of all decidable subsets of $\Sigma^{*}$.

Say that $n \in \mathbb{N}$ is a code for $L \in \mathcal{R}$ if the Turing machine encoded by the number $n$ (via some Gödel encoding of Turing machines) recognizes $L$. Let us write $L_n$ for the set that is recognized by the $n$-th Turing machine.

Similarly, say that $n$ is a code of $D \in \mathcal{D}$ if the $n$-th Turing machine is the decider for $D$. If $n$ is the code of a decider (not every number is!) then we write $D_n$ for the set it decides.

Consider the statement: "For every infinite $L \in \mathcal{R}$ there is an infinite $D \in \mathcal{D}$ such that $D \subseteq L$."

You are asking whether we can prove the statement by giving an effective procedure which assigns to every $L$ a corresponding $D$ in such a way that $D$ does not depend on the choice of the code of $L$. (Clearly, we can do this inefectively by an application of the axiom of choice.) More precisely, the question seems to be whether there a computable map $f$ such that

if $n$ codes an infinite $L \in \mathcal{R}$ then $f(n)$ codes an infinite $D \in \mathcal{D}$ such that $D \subseteq L$, and
if $L_n = L_m$ then $D_{f(n)} = D_{f(m)}$.

The answer is no, there is no such map: you must appeal to a particular recognizer for $L$ and obtain a $D$ which depends on the recognizer.

To prove that this is really so we appeal to Rice's theorem. Suppose we had such an $f$. There exists $n, m, a \in \mathbb{N}$ such that $a \in D_n$ and $a \not \in D_m$. The subset $S \subseteq \mathcal{R}$ defined by
$$L \in S \iff \exists n \,.\, L = L_n \land a \in D_{f(n)}$$
is a non-trivial decidable subset of $\mathcal{R}$, which violates Rice's theorem.


It only flood-fills the graph if there is no path to the end-node.

What would be the point of including a heuristic if you were just going to visit every node anyways?


Is writing a compiler for a compact language easier?

In almost every case, the more compact languages like APL will be harder write a compiler for:

On the front end (parser), in the worst case, you have a ton bunch of special cases for your symbols in your parser, and in the best case, you treat them as generic symbols, in which case you're in the exact same parsing position as a language that has
In the back-end, with type checking, optimizers, etc., you either treat your symbols as standard library functions, in which case you're in the exact same place as a more verbose language, or you treat them as parts of the language, in which case you will have a bunch of special cases in your type checker, code generation, etc.

In general, compilers are easiest for smaller languages. This is why most languages feature syntactic sugar, where some features are translated into a subset of your original language at compile time (for example, eliminating for-loops by turning them into while-loops). Many languages also keep code-generation and optimization simpler by compiling their language into a smaller intermediate language after parsing or type checking, then optimizing and compiling that language into machine code.

  I should add that i am especially interested in whole-program optimization.

Syntax will not influence this in the slightest. Parsing is generally the least interesting part of writing a compiler, since there's many solutions for parsing, and once you have things into an Abstract Syntax Tree, what concrete syntax you used is entirely irrelevant. That is, two languages that parse to isomorphic ASTs will be exactly the same for difficulty to optimize.

The only case where having a more compact language could help optimization is if you have a bunch of special cases of known optimizations (e.g. fusion rules) for your operators, but you could just as easily write special cases for standard library functions of a more verbose language.


Here is a reduction from SAT to your problem. Let $\phi = C_1 \land \cdots \land C_m$ be a CNF on the variables $x_1,\ldots,x_n$. Consider the following graph with parallel edges (those can be easily eliminated if need be). There is a vertex for each variable and each clause, and additionally there are is a vertex $s$. There are $2n$ colors, one per literal, and we will choose $k := n$. The edges are:

From $s$ to $x_1$ there are two edges, colored $x_1$ and $\lnot x_1$.
From $x_{i-1}$ to $x_i$ there are two edges, colored $x_i$ and $\lnot x_i$.
From $x_n$ to $C_1$ there is an edge per literal in $C_1$, colored as the literal.
From $C_{j-1}$ to $C_j$ there is an edge per literal in $C_j$, colored as the literal.

Then $\phi$ is satisfiable iff there is a path from $s$ to $C_m$ which uses at most $n$ different colors.


Does proving a problem is in P typically mean it will eventually be practically solvable?

One example in which the running time became significantly better but still not necessarily practical is submodular function minimization, which went down from $O(n^7)$ (Grötschel, Lovász and Schrijver, 1981) to $\tilde{O}(n^4)$ (Lee, Sidford and Wong, 2015). The latter paper (and the ones preceding it) has many such results.


Reduction from partition to multiprocessor scheduling

(This is the answer that the OP wanted to have checked.)

Let $S=\{a_1,...,a_n\}$ be an arbitrary instance of Partition. In our reduction we set $J=S$. if $\sum\limits_{a \in S} a$ is even, we set $m=2$. Note: If the sum of elements in $S$ is odd, there cannot be a Partitioning. Further, we set the length $l_i$ of job $j_i$ to the value of $a_i$.

So this is my reduction. But I am very unsure if this is just too easy? Note that I do not have to provide the correctness proof but just the reduction. Is this somehow a right reduction? I am very unsure if I have to distinguish between the two cases where the sum of elements of $S$ is odd or even. What if the sum is odd?

Can someone give me some hints on that?


How are bitwise operators used in normalisation of floating-point numbers?

It's helpful to think of the number in the following representation( I choose 3.75 as an example):
$$2^0 * 11.11_2  = 3.15$$
Now $2^0 = 1$ so we can just write it in front of the number. Now we want to normalize $3.75$ meaning we need to transform it to $2^e * 1.m$ where $e$ and $m$ are some bitstrings. Notice that we can shift a binary number to the left by dividing it by to e.g. $4 = 100_2 = 2* 010_2 = 2*2* 001_2$. I hope you can see how dividing/multiplying by 2 corresponds to shifting (in base 2!). Lets shift 3.75 in such a way that a 1 is in front of the comma:
$2^0 * 11.11_2 0 = 2^1* 1.111_2$; as you can see we shifted 3.75 and thereby pulled a $2$ out of it and increased the exponent to account for the $2$. The value of the number is still 3.75 it's just written down as $2* 1.875$. This is the normalized form. Now the exponent $e$ and the places behind the comma are stored in a floating point number. Why don't we need the $1$ in front of the comma? Cause the normalized form guarantees that there is a 1 so it's redundant to store it.


Limiting memory usage while keeping score

Your idea of an array of size $c_3$ is a good one.
But you can do better. First, since you need only be withing a range $r$,
you can use an array of size $c_3/r$, rounding upward, and just mark the entry
corresponding to the integer segment you fall in (there may be some details to work out).

Then, rather than using an array, if it is still too large, you can
build a binary structure, so that you create only the array entries you
need. Each node of the binary structure corresponds to a range of
consecutive entries.

    Then, you can reduce the memory requirement further by merging contiguous ranges where all entries have been hit, and rebalance the tree.

 Of course, there is a $\log_2 c_3/r$ price in access time. But this cost is limited by the tree shrinking as it gets full.


Minimum time to assemble multipart object

Your solution (of greedily merging the two smallest objects available) is indeed correct. This problem is very classic and you can find it under the name 'rod connection' or 'rope connection'. Here (https://stackoverflow.com/questions/43715207/how-to-prove-this-greedy-algorithm-as-optimal-rod-connection) is the proof of optimality.


The complement (note spelling) of $\mathrm{SAT}$ is the set of all binary strings that do not encode a satisfiable Boolean formula. That is all strings that encode unsatisfiable formulas, and also any strings that don't encode any formula at all.

In practice, we tend to ignore strings that don't encode a valid input to the problem. For any sane encoding, recognising which strings are valid encodings is computationally very easy.  For any such encoding, the computational complexity of the two languages
$$\{w\mid w\text{ encodes an unsatisfiable formula}\}$$
and
$$\{w\mid w\text{ encodes an unsatisfiable formula or is not a valid encoding}\}$$
is the same, so we tend not to distinguish between them.

Alternatively, it's usually fairly straightforward to come up with an encoding where every string is a valid encoding of some input. For example, consider a problem whose input is a graph.  Naïvely (and normally!) we would encode a graph as the binary listing of its adjacency matrix. However, that means that only inputs whose length is a perfect square are valid.  We could make every string valid by adding zeros to the end until the length is a perfect square so that, e.g., the string $01101$ would encode the graph whose adjacency matrix is
$$\left(\begin{matrix}0&1&1\\0&1&0\\0&0&0\end{matrix}\right).$$
If our input is supposed to be an undirected graph, that's still no good, since the matrix isn't symmetric.  In that case, we could just encode the entries above the diagonal, again padding with zeros to reach the next triangular number.  In this encoding, $01101$ would encode the graph with adjacency matrix
$$\left(\begin{matrix}0&0&1&1\\0&0&0&1\\1&0&0&0\\1&1&0&0\end{matrix}\right).$$

But translating between these inputs is easy (it can be done in, e.g., deterministic logspace), so we usually just ignore these fine details.


Does there exist context-free grammar with words of length n^2 or n^3?

For a language $L$, let $N(L) = \{|w| : w \in L\}$, and let $U(L) = \{1^n : n \in N(L)\}$. Parikh's theorem shows that if $L$ is context-free then $U(L)$ is regular. In particular, since $\{1^{n^2} : n \geq 0 \}$ is not regular, no context-free language $L$ satisfies $N(L) = \{n^2 : n \geq 0\}$. In fact, no infinite context-free language $L$ even satisfies $N(L) \subseteq \{n^2 : n \geq 0\}$ (exercise).


Understanding google's user level threads in kernel threads

This is talking about user level threads, so they should all have the same memory context (virtual memory map).  So while the threads need to be careful in doing so, they can all access each other's objects directly without using inter-process communication.

The scheduler will give each thread a time slot to run in (length possibly depending on priority).  He is discussing an addition to the kernel to allow a request:

  pid_t switchto_switch(pid_t tid)

  Synchronously transfer control to target sibling thread, leaving the
  current thread unscheduled.
  Analogous to: Atomically { Resume(t1); Wait(NULL); }

So as a programmer, if you had work on a task that you need to stop and wait for information from another task before you can continue, then you could request to immediately switch to that specific thread.

Your intial thread would immediately be put in a wait state, and the other thread would resume execution using the initial thread's currently scheduled time ("B inherits A’s virtual runtime").


Time Complexity: Intuition for Recursive Algorithm

Based on the code you show there, your intuition is right.

However, it looks like there is a typo in the code and the next-to-last line should have been

  q = max(q, p[i] + CutRod(p, n-i))

i.e., n-i rather than n-1.  Try to work through a proof of correctness, or through a few examples, to see why I say that.  The running time analysis they show is for the corrected code, rather than the code with the typo, and then once you make that correction to the code, the recurrence relation they provide is correct.


how can i say a given problem is in co-NP using it's definition?

Following the brief discussion in the comments, let me write an answer summarizing it.

When defining decision problems (e.g., based on $\{ 0, 1 \}^\ast$ strings), we usually make the assumption that every word in $\{0,1\}^\ast$ is a valid problem instance. Perhaps your source of confusion is that, usually, this is not made as explicit or given as much importance as it should or, rather, it is only too late (i.e., when discussing complementary problems such as those in $\textbf{coNP}$) that one realizes what the assumption actually entails. Under such an assumption it is obvious why $\textbf{coNP}$ is simply the complements of the problems in $\textbf{NP}$; in fact, without the assumption, such a definition would not make that much sense (since $\textbf{coNP}$ problems would contain invalid problem instances).

In the comments, I have also mentioned the notion of promise problems. This is an alternative way of defining decision problems without needing the aforementioned assumption. Basically, when the input string is not an encoding of a problem instance, the behavior of an algorithm solving the problem is left unspecified. The result is the $\{0,1\}^\ast$ string space being partitioned in three parts: valid "yes" instances, valid "no" instances, and invalid instances. Note that for poly-time algorithms this notion is equivalent to the former one since recognizing a valid instance (for reasonable problems) can always be done efficiently.


Topological sorting would work if all $b_k$'s were zero.  Here is a way that takes into account the $b_k$'s.  Build a dag where each vertex is a task and there are edges from each task to its child tasks.  Then, use the following algorithm:

Out of all sinks (vertices with out-degree zero), find the one whose $b_k$ value is smallest.  Output it, then delete it and all edges into it.

Repeat, until all vertices have been output.

I believe this will output an optimal schedule, in reverse order (last task first).


Let $S$ be a subset of at most $K$ vertices. Let $a_d$ be the number of vertices on the right side which are connected to exactly $d$ vertices in $S$. Since the left degree is $D$,
$$
\sum_{d \geq 1} da_d = D|S|.
$$
Since $S$ has at least $(1-\epsilon)D|S|$ neighbors,
$$
\sum_{d \geq 1} a_d \geq (1-\epsilon)D|S|.
$$
Therefore
$$
\sum_{d \geq 2} a_d \leq \sum_{d \geq 1} (d-1) a_d = \sum_{d \geq 1} da_d - \sum_{d \geq 1} a_d \leq D|S| - (1-\epsilon)D|S| = \epsilon D|S|.
$$
It follows that
$$
a_1 = \sum_{d \geq 1} a_d - \sum_{d \geq 2} a_d \geq (1-\epsilon)D|S| - \epsilon D|S| = (1-2\epsilon)D|S|.
$$


What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity?

Here is one benefit:

Some grammars aren't LR(k).  Then it's useful to have CYK or some other form of GLR parsing.  GLR parsing is used in some compilers, where the most natural way to express the grammar leads to a grammar that isn't LR(k), or where ambiguities are resolved in a later pass (not part of the parser).


Undecidability instance on a "find a proof/disproof" machine

So $f(M,I)$ is this machine that "takes our standard set of axioms (ZFC, let's say, or Peano arithmetic, or whatever) and first tries every one-page proof that machine M halts on input I"...

That's fine, but later on you say "The above constitutes a proof that $g(g)$ never terminates, and so the function $f(g,g)$ should find this proof."

That is not true, since you didn't write that proof as a formal proof in terms of "ZFC, let's say, or Peano arithmetic, or whatever", so there is no reason to expect $f(g,g)$ to find it.  You didn't even define $f(a,b)$ of $g(x)$ in terms that would translate into most such formal systems.

You assume that you would be able to specify a real formal system if you had to, with sufficient power to express $f$ and $g$ in concrete terms and prove what you say about them, but Godel's theorem says that's not necessarily so.

Furthermore, you say that $f$ and $g$ are real programs, but that is not true until this formal system is specified.  Because of this you have not proven what you set out to prove.  What you have proven is Godel's theorem -- any formal system that allows you to express your claim in terms of itself will either be inconsistent, or will not contain your proof.


What are some approaches to solve these classes of problems efficiently

This is an instance of the assignment problem.  There are polynomial-time algorithms for solving the assignment problem, e.g., using the Hungarian algorithm (or other algorithms).


Why is solving of diagonal quadratic equations over $\mathbb R$ and $\mathbb C$ in $P$?

We assume that we are allowed to take square roots in $\mathbb{F}$.

$\mathbb{F} = \mathbb{C}$: If $b = 0$ then $x_1 = \cdots = x_n = 0$ is a solution. If $b \neq 0$ and $a_1 = \cdots = a_n = 0$ then there is no solution. Otherwise, let $a_i \neq 0$, and then a solution is $x_i = \sqrt{b/a_i}$ and $x_j = 0$ for $j \neq i$.

$\mathbb{F} = \mathbb{R}$: If $b = 0$ then $x_1 = \cdots = x_n = 0$ is a solution. Otherwise, without loss of generality assume that $b > 0$ (otherwise, multiply all of $b,a_1,\ldots,a_n$ by $-1$). If $a_i \leq 0$ for all $i$ there is no solution. Otherwise, let $a_i > 0$, and then a solution is $x_i = \sqrt{b/a_i}$ and $x_j = 0$ for $j \neq i$.


What is meant by problems not in NP but in NP hard?

A language $L$ is NP-hard if you can reduce every language in NP to $L$ in polynomial time. For example, the halting problem is NP-hard: if $A$ is any language in NP, say accepted by a nondeterministic polynomial time Turing machine $T$, there there is a polynomial time reduction which accepts an input $x$ and constructs a Turing machine which simulates all computation paths of $T$ on $x$, and halts if and only if any of these paths accepts.

On the other hand, the halting problem is not in NP, since it is not computable. So the halting problem is an example of an NP-hard problem which is not in NP.
You can think of NP-hard problems as being "at least as hard" as all of NP. They are allowed to be even harder.


Getting the idea behind pumping length correct

One thing that's worth pointing out is that there can be many lengths that satisfy the pumping lemma. In your example, setting the pumping length to 2 does satisfy the pumping lemma. And so does length 3, 4, 5, etc. I think what you're asking about is the minimum pumping length. The pumping lemma is generally used to show proof that a language is not regular, in which case it doesn't really matter what the minimum pumping length actually is, just that there is some finite pumping length.

Anyway, I believe that the minimal pumping length for 0*1* is actually one, not two. It's true that the 01 is the the longest word accepted without an iteration, but that's not precisely the definition of the pumping length. There are two possible words of length one:  0 and 1. Both of these words can be pumped, and as you've shown, any words of length two or more can be pumped. Therefore, any word of length one or more can be pumped, so the minimal pumping length is one.

For your second example, I assume you mean the language L = {0n 1* | n is a specified constant}. In that case I believe you're right that the minimum pumping length is n + 1. We can pump 0n1, but we can't pump 0n.


Hint: Show that an FPTAS for $Q$ implies a polytime algorithm for $L_Q^*$. This contradicts the assumption $P \neq NP$, which is missing from your question but seems to be tacitly assumed.


Since each place in a binary number is a power of two, the binary expansion of $2^k$ for any $k$ will be a 1 followed by $k$ zeroes.  Examples:

$$1 = 2^0 = 1$$
$$16 = 2^4 = 1\underbrace{0000}_{4\ zeroes}$$
$$512 = 2^9 = 1\underbrace{000000000}_{9\ zeroes}$$

Multiplying a number that ends in zeroes by another number (integer) produces at least that many trailing zeroes.  So any number divisible by a number ending in $k$ zeroes has to end in at least $k$ zeroes.


What determines the "speed" of a programming language?

There are many reasons that may be considered for choosing a language
X over a language Y. Program readability, ease of programming,
portability to many platforms, existence of good programming
environments can be such reasons. However, I shall consider only the
speed of execution as requested in the question. The question does not
seem to consider, for example, the speed of development.

Two languages can compile to the same bytecode, but it does not mean
that the same code will be produced,

Actually bytecode is only code for a specific virtual machine. It does
have engineering advantages, but does not introduce fundamental
differences with compiling directly for a specific harware. So you
might as well consider comparing two languages compiled for direct
execution on the same machine.

This said, the issue of relative speed of languages is an old one,
dating back to the first compilers.

For many years, in those early times, professional considered that
hand written code was faster than compiled code. In other words,
machine language was considered faster than high level languages such
as Cobol or Fortran. And it was, both faster and usually smaller. High
level languages still developed because they were much easier to use
for many people who were not computer scientists. The cost of using
high level languages even had a name: the expansion ratio, which could
concern the size of the generated code (a very important issue in
those times) or the number of instructions actually executed.  The
concept was mainly experimental, but the ratio was greater than 1 at
first, as compilers did a fairly simple minded job by today standards.

Thus machine language was faster than say, Fortran.

Of course, that changed over the years, as compilers became more
sophisticated, to the point that programming in assembly language is
now very rare. For most applications, assembly language programs
compete poorly with code generated by optimizing compilers.

This shows that one major issue is the quality of the compilers
available for the language considered, their ability to analyse the source
code, and to optimize it accordingly.

This ability may depend to some extend on the features of the language
to emphasize the structural and mathematical properties of the source
in order to make the work easier for the compiler. For example, a
language could allow the inclusion of statements about the algebraic
properties of user defined functions, so as to allows the compiler to
use these properties for optimization purposes.

The compiling process may be easier, hence producing better code, when
the programming paradigm of the language is closer to the features of
the machines that will intepret the code, whether real or virtual
machine.

Another point is whether the paradigms implemented in the language are
closed to the type of problem being programmed. It is to be expected
that a programming language specialized for specific programming
paradigms will compile very efficiently features related to that
paradigm. Hence the choice of a programming language may depend, for
clarity and for speed, of the choice of a programming language
adapted to the kind of problem being programmed.

The popularity of C for system programming is probably due to the fact
that C is close to the machine architecture, and that system
programming is directly related to that architecture too.

Some other problem will be more easily programmed, with faster
execution using logic programming and constraint resolution languages.

Complex reactive systems can be very efficiently programmed with specialized synchronous programming languages like Esterel which embodies very specialized knowledge about such systems and generate very fast code.

Or to take an extreme example, some languages are highly specialized,
such as syntax description languages used to program parsers. A parser
generator is nothing but a compiler for such languages. Of course, it
is not Turing complete, but these compilers are extremely good for
their specialty: producing efficient parsing programs. The domain of
knowledge being restricted, the optimization techniques can be very
specialized and tuned very finely. These parser generators are usually
much better than what could be obtained by writing code in another
language. There are many highly specialized languages with compilers that produce excellent and fast code for a restricted class of problems.

Hence, when writing a large system, it may be advisable not to rely on
a single language, but to choose the best language for different
components of the system.  This, of course, raises problems of
compatibility.

Another point that matters often is simply the existence of efficient libraries for the topics being programmed.

Finally, speed is not the only criterion and may be in conflict with
other criteria such as code safety (for exemple with respect to bad
input, or resilience to system errors), memory use, ease of
programming (though paradigm compatibility may actually help that),
object code size, program maintainability, etc.

Speed is not always the most important parameter. Also it may take different guises, like complexity which may be average complexity or worse case complexity. Also, in a large system as in a smaller program, there are parts where speed is critical, and others where it matters little. And it s not always easy to determine that in advance.


How does one formally show that two lambda functions are $\alpha$ equivalent?

By definition of substitution we have
$$x [x \leftarrow z] = z$$
therefore
$$\lambda z . x [x \leftarrow z] = \lambda z . z \tag{1}$$
because $\lambda$-abstraction is a congruence (it preserves equality). By the definition of $\alpha$-equality we have
$$\lambda x . x = \lambda z . x [x \leftarrow z] \tag{2}.$$
By transitivity of equality we get from (1) and (2) that
$$\lambda x . x = \lambda z . z$$
If you require more details than this, you should use a computer proof assistant to check the details.


The research is well in progress, though not so much talked about in comparison to machine learning, deep learning in particular.

Genetic algorithms are applied in particular research areas (examples: "Genetic Programming for Estimation of Heat Flux between the Atmosphere and Sea Ice in Polar Regions" (link), "Genetic Programming with Alternative Search Drivers for Detection of Retinal Blood Vessels" (link), "Optimal placement of water-lubricated rubber bearings for vibration reduction of flexible multistage rotor systems" (link)).
If you are interested in a research of genetic algorithms themselves, see the papers by Claire Le Goues.
There is an annual conference dedicated to evolutionary computation.
Programming frameworks are far from dead as well.

  Is genetic programming relevant today?

Not so long ago, in early 2000-s, people asked the same question about neural networks. Hugo Larochelle mentions how the neural networks papers have been reviewed back then. And we know how it turned out. So don't be so quick in your conclusions, it all can change one day.


Are decidable set/languages EQUIVALENT to type 1 grammars (non-contracting)?

Yuval's answer is absolutely right, but note that there's a more general principle in play here as well: diagonalization. Any time we have a class of decidable languages for which we have a "decidable syntactic description" (I'm being vague about this for a moment), we can diagonalize out of this class to get a decidable language not in the class. Basically, we whip up a notion of "$n$th language in the class" and then consider the new language which contains word $1...1$ ($n$ times) iff the $n$th language in the class does not contain that word (or something similar); granting the complexity assumption on the starting class, this results in a decidable language.
(In snappier computability-theoretic terminology: if $f(x,y)$ is a total computable function then there is a total computable $g(z)$ such that for each $x$ there is some $y$ with $f(x,y)\not=g(y)$.)
Classes like type $1$ grammars are defined by simple syntactic conditions, and so can be diagonalized out of. Of course this does not necessarily result in a natural example of a decidable language not in the starting class, but it does prove that that class misses many decidable languages.


Should i work with tree representation as an array of nodes and an array of edges

In the unforgettable words of Donald Knuth

Premature optimization is the root of all evil.

Your best option is as follows.  Do what is simplest for you, while maintaining a good abstraction with good encapsulation.  A good abstraction (a well-defined and thought out API) will make it easy for you to change and improve the underlying implementation in the future while not having to change the rest of the application.
When (or really if) you discover that the application is too slow, then you start changing the underlying implementation, but only after a proper complexity analysis.
It is very difficult (if not impossible) to say in advance what will be the bottleneck of the application, so it's best to leave this decision until you actually know.


Prove that following graph problem is in $L$

Let $N_k$ be the set of vertices at distance $k$ from 1. A graph satisfies the property if the sets $N_k$ are intervals, and $N_{k-1} < N_k$ (every member of $N_{k-1}$ is smaller than every member of $N_k$). We will check this property inductively: assuming $N_{k-1}$ is known (starting with $N_0 = \{1\}$), we will show how to calculate $N_k$ and verify that it has the correct properties.

Suppose that $N_{k-1} = \{a,\ldots,b\}$. If $b = n$, we can stop. Otherwise, go over all neighbors of the vertices in $N_{k-1}$, and record the minimal and maximal indices $c,d$ encountered among those larger than $b$. Verify that $c = b+1$. Now go over all $e \in \{c,\ldots,d\}$, and verify that it is a neighbor of some vertex in $N_{k-1}$. If so, we have verified that $N_k = \{c,\ldots,d\}$, and can continue with $N_{k+1}$.

You can check that this algorithm can be implemented in logspace.


Whats exact definition of 'atomicity' in programming?

If an operation X is atomic, that means that anyone observing the operation will see it either as not yet started, or as completed, and not in any state that is partially completed. That's it.

Obviously if you write code to perform an operation X, and other code can see it half performed, or interfere with it, then your implementation of the operation X is not atomic.

In some contexts, an”atomic” operation can succeed or fail; if such an atomic operation fails then the effect must be exactly the same as if the operation had never been started.


First of all I find it rather artificial to argue with reductions, since a more direct argument is applicable here. However, you can of course do it.

I think your approach follows basically the right direction. But it is not a clean reduction. Here is how I would phrase it.

We want to show that ${\sf 2Strings}$ is recognizable by showing ${\sf 2Strings}\le_m {\sf Halt}$. The reduction  goes as follows: Assume we have  a TM $M$ and based om $M$ we define a different TM $M'$. Let us first define a NTM $N$:

 0. Delete the input
 1. Guess two words u and w
 2. If u=w cycle
 3. Simulate u on M
 4. Simulate w on M
 5. Accept if both simulation accepted, otherwise cycle

Now let $M'$ be the deterministic version of $N$. The reduction maps $\langle M \rangle $ to $\langle M',\varepsilon \rangle$. By construction,
$$
\begin{align}
\langle M \rangle \in {\sf 2String} & \iff N \text{ accepts every input}\\
 & \iff M' \text{stops on every input}\\
 & \iff M' \text{stops on }\varepsilon \\
 & \iff \langle M',\varepsilon\rangle \in {\sf Halt} \\
\end{align}
$$


Find maximum in array without comparisons between elements

a) am I correct?

No, that's not correct. Suppose this array is an unsorted array, and you want to find a maximum element in this array.

First, sorting this array in the increasing order. You can use mergesort or quicksort to sort the array. Mergesort will guarantee the time complexity in the worst and average cases is O(nlogn). However, quicksort will take O(nlogn) for the average case, and O(n) for the worst case. Regarding the worst case of quicksort, if partitioning the array into two groups which one group is empty and another one is (n-1), this will take O(n) time complexity.

Second, after you have a sorted array in increasing order, you can get the maximum element at the last element in the sorted array.

b) is it possible to do better?

You can use heapsort with max heaps property. In this case, the largest element is at the root for max heaps. Heapsort will take O(nlogn) since building maxheap takes O(n) and max-heapifying takes O(logn). It takes only O(1) to find a maximum element.


On the definition of Error-Correcting Codes

Here is what the remark says:

A code $C \subseteq A^n$ is $t$-error-correcting if for all $x \in C$ and $y \in A^n$ such that $d(x,y) \leq t$, all $z \in C$ other than $x$ satisfy $d(x,y) < d(z,y)$.

When is a code not $t$-error-correcting according to this remark?

A code $C \subseteq A^n$ is not $t$-error-correcting if there exist $x,z \in C$ and $y \in A^n$ such that $x \neq z$ and $d(z,y) \leq d(x,y) \leq t$.

Given $x,y,z$, either $d(z,y) \leq d(x,y)$ or $d(x,y) \leq d(z,y)$, and so, since the other constraints on $x,z$ are symmetric in $x,z$, the above definition is equivalent to

A code $C \subseteq A^n$ is not $t$-error-correcting if there exist $x,z \in C$ and $y \in A^n$ such that $x \neq z$ and $d(x,y),d(z,y) \leq t$.

This is exactly Definition 2.


The first is a counting sort with the change that you use a hashtable instead of an array to hold the mapping between element value and the number of elements of that value.

The second is a near textbook Bucket Sort with the change that you don't sort the bucket.


How do I form a parse tree for equations?

To produce a parse tree you need a string to parse, which you have, but
you also need a grammar to tell you how well-formed (legitimate)
strings are to be structured.

In your case you did not give a grammar. so that your question makes
no sense. Usually this is done with context-free grammars

Furthermore I suspect that what you really want is an abstract syntax
tree (AST), which is often very close to parse trees, but is supposed
to be defined more abstractedly (for example with a sorted algebra),
indpendently of any parsing process, and from which semantics is more
easily defined. Note that, while the AST may be defined independently of any arsing process, it is usually associated to textual representation via a parsing process, though other means do exist.

Below is what an AST could look like for your example. But, as for parse trees, an AST can be properly given only if you have defined formally what the abstract syntax is for your language.

To be very complete, you need at least one formal definition that relates tree structures you may be interested in (parse trees or AST) for your text with corresponding textual strutures.

              if
     ________/|\________
    /         |         \
   >          if        :=
  / \    ____/|\____   /  \
 x   y  /     |     \ x    b
       <     :=     :=
      / \   /  \   /  \
     y   a x    a y    b

Warning: the referenced wikipedia articles could be much improved, at least on the pedagogical side.


How is a type system related to a progam?

Your understanding that a type system is a set of rules in a formal system is right, but the rest is a bit garbled.  The purpose of the type system is to delineate which terms or programs make sense.  It is up to the language designer to decide which programs "make sense".  There is no claim that the language specifies all programs that make sense.  When somebody proposes a new type system, they are saying, "here are more programs that make sense and our type system captures them."

Andrej is saying one shouldn't equate the type system with the type checker (which is a program).

There is nothing too deep about it.  Merely that the type system, i.e., the set of rules, stand independently of any particular implementation.  One could even devise type systems that are undecidable, i.e., no possible type checking program exists.  Admittedly such type systems may not be of much practical use, but nobody denies that they are type systems in the first place!


Take the concatenation of $\Sigma^*$ with any language that contains the empty word but is known not to be in NP (for example, an undecidable language).


Just count the busses.  Most of the registers in this design only have an input from the single common bus.  The only exception is the ACcumulator, which also has an input from the DR.


How to compare algorithms in class NC time complexity with other classes?

The class NC is by definition a subset of P, since it consists of uniform polynomial size circuits with some restrictions (namely, polylogarithmic depth). It is unknown whether $NC \neq P$, but this is strongly suspected.

Let me comment that $O(NC^2)$ is a syntax mismatch since $NC^2$ is a complexity class rather than a function. We simply say that topological sort is in $NC^2$.


There are many methods for computing the eigenvalues of a matrix.

If you just want the largest eigenvalue, the power method is an efficient way to do that, as Yuval suggests.  Typically the power method takes $O(n)$ time to find (an approximation to) the largest eigenvalue of a $n \times n$ matrix, if the matrix is sparse (it has $O(1)$ non-zero entries per row), with a constant of proportionality that depends on the matrix (and specifically on the value of $|\lambda_1/\lambda_2|$).

A generalization is the Lanczos algorithm, which lets you find the top $k$ eigenvalues in a sparse Hermitian matrix in $O(kn)$ time, with a constant of proportionality that depends on the matrix.  Arnoldi iteration is a generalization to non-Hermitian matrices.

If you want to find all eigenvalues, there are multiple methods.  The QR algorithm has $O(n^3)$ running time, though it doesn't take advantage of the sparsity of your matrix.  Arnoldi iteration can apparently be used to find all eigenvalues, or the $k$ largest eigenvalues, but I don't know what its asymptotic running time is.  There are apparently also software libraries that support eigenvalue computation on sparse matrices, e.g., Eigen, ARPACK, SuperLU, Spectra, OpenNL.  I have no experience with them and cannot recommend one.

For more you might check Computational Science.SE, e.g., https://scicomp.stackexchange.com/questions/tagged/sparse+eigenvalues.


Counting an integer's divisors without just enumerating them (or estimating if not possible)?

As far as I know we don't know a smart method of distinguishing between numbers which have $a$ divisors and numbers which have $b$ divisors, unless (say) $a$ is prime (in which case necessarily the number is an $(a-1)$th power of a prime, and we can use root extraction and primality testing). On the other hand, if you factor $n = \prod_i p_i^{d_i}$ then you can compute the number of factors using the formula $\prod_i (d_i + 1)$.


I think the usual way of doing this is that you hash each record (with a known cryptographically secure hash) and provide the client with $N$ hash values. The client chooses $k$ out of those hash values and you reply with the corresponding $k$ records. The client can then verify that the hash values match up correctly with the provided records plus whatever record validation they'd like to do. Note that if you have duplicate records in your DB, those duplicates could be inferred from provided hash values (e.g.: the client could get a pretty good estimate of the number of distinct records in your DB). If this is undesirable, then you can salt the hashes.


Measuring the hardness of SAT instances Lemma

First, $[a\to 1]\Gamma = (1)(1)(c)(c')$. A refutation of this consists of resolving $c$ and $c'$. Following the proof, we reinstate $a'$ to get the CNF $(1)(1)(a'+c)(a'+c')$, and then resolve $a'+c$ and $a'+c'$ to get $a'$.

Similarly, $[a\to 0]\Gamma = (b)(b')(1)(1)$, which can be refuted by resolving $b$ and $b'$. Reinstating $a$, we get $(a+b)(a+b')(1)(1)$, and resolving $a+b$ and $a+b'$ we get $a$.

Note that your notation, which is different from the paper's, is confusing you. For example, $x'$ is not the negation of $x$ but rather a new variable symbol.


How to find a minimum set of axioms within a set of propositions?

Determining whether a proposition follows from a set of axioms is an NP-Complete problem. Finding a minimal set of axioms from a set of propositions naturally invokes this problem many times as a subroutine.

For example, consider the following set of propositions:

$$P = \{v_1, v_3 \vee v_2, v_1 \wedge v_3\} $$

A minimum set of axioms from this set is $\{v_1 \wedge v_3\}$. But to find it, you have to prove $v_1$ and $v_3\vee v_2$, and those proofs are in general hard to find. The problem is there a set of axioms $A$ for a set of propositions $P$ with at most $k$ axioms? is in $\Sigma_{3}^{p}$, which means it's in the third level of the polynomial hierarchy, which means that it's two levels higher than NP in the way that NP is one level higher than P, to give you an idea of its complexity. I do not know if it is also in a lower level. Browsing through this survey (link) [1] of problems that are complete for various levels of the polynomial hierarchy, I do not see this problem among them, so it's possible that it's not $\Sigma_{3}^{p}$-Complete, but it wouldn't surprise me.

Before you go out to look for a set of axioms, you may want to know whether the set of propositions is sound and any subset is complete (untrue propositions cannot be proved, all true propositions can be proved). These problems have similar NP-scary complexity. First, Is this set of propositions complete? is a problem in $\Pi_{2}^{p}$ of the polynomial hierarchy, because it asks, for all $p\in P$, can $p$ be proved from propositions $P\setminus \{p\}$? Completeness of your system is in co-NP as it asks, Forall all $p\in P$, can $p$ not be proved from $P \setminus \{p\}$? So it seems that checking for soundness and completeness is easier than finding a minimal axiom set, but not by much. (I'm less sure about this paragraph. Is it true that a logical system of propositions $P$ is sound iff for all $p\in P\colon \neg p$ cannot be proved from $P\setminus \{p\}$?)

The comments to your question pertain to the context of database entries, but they are purely syntactic and only establish redundancy in the database, whereas if your question is about propositions, as I understand it, then the contents of the database must be inspected semantically, and this leads you to this complexity nightmare.

[1] M. Schaefer, C. Umans, Completenss in the Polynomial Hierarchy, A Compendium, 2008.


How can I prove that a Regular Language is closed under Union given two languages with different alphabets?

Suppose you have alphabets $\Sigma\subseteq\Sigma'$.  You can view any language $L\subseteq \Sigma^*$ as being a subset of $(\Sigma')^*$: it just happens to be language of strings that don't contain any symbols from $\Sigma'\setminus\Sigma$.

So, given languages $L_1\subseteq \Sigma_1^*$ and $L_2\subseteq\Sigma_2^*$, you can view both of these as languages over $\Sigma_1\cup\Sigma_2$, since $\Sigma_i\subseteq \Sigma_1\cup\Sigma_2$ for $i\in\{1,2\}$.  Given automata for $L_1$ and $L_2$, you can also modify them to work over alphabet $\Sigma_1\cup\Sigma_2$.

Now, you have two languages over the same alphabet, so you should be on familiar ground.


Transforming 3 SAT to Simultaneous In-Congruence Problem?

Given a SAT instance on $n$ variables, find $n$ relatively prime integers $p_1,\ldots,p_n \geq 2$ of polynomial size (for example the first $n$ primes). The idea is to encode the value of variable $x_i$ as $x \bmod{p_i}$. The first step is to ensure that the variables are indeed binary. To this end, for each $i$ and for each $2 \leq a < p_i$, we add the constraint $x \not\equiv a \pmod{p_i}$.

Each clause involving $p_i,p_j,p_k$ corresponds to one forbidden value of $x \bmod{p_ip_jp_k}$ via the Chinese reminder theorem. For example, consider the clause $x_i \lor x_j \lor \lnot x_k$. Find the value $0 \leq a < p_ip_jp_k$ which satisfies $a \equiv 0 \pmod{p_i}$, $a \equiv 0 \pmod{p_j}$, and $a \equiv 1 \pmod{p_k}$. Add the constraint $x \not\equiv a \pmod{p_ip_jp_k}$.

The resulting system is completely equivalent to the original 3SAT instance.


Comparing the closed behaviors corresponding to finite state automata

Your claim implies that $L(G)$ depends only on the alphabet of $G$, but this is clearly false. So the claim itself must be false.


Does array always have a wasted space of O(n)?

It depends on the algorithm used. Someone made the assumption that when an array has space for n items, and the n+1st item needs to be added, the array would be resized to a size c·n for some constant c > 1. But there is nothing forcing us to do this; we could resize from n items to f (n) items, where f (n) ≥ n+1 obviously but f (n) - n = o (n).


This is yet another example of combinatorial enumeration. There are altogether $\binom{M+4}{4}$ different quadruples. Given $j_0$, there are $\binom{M+3-j_0}{3}$ quadruples with $i_0 = j_0$. This means that the first $\binom{M+3}{3}$ quadruples start with $0$; the following $\binom{M+2}{3}$ start with $1$; the next $\binom{M+1}{3}$ start with $2$; and so on. In this way, given a number between $1$ and $\binom{M+4}{4}$, you can find $i_0$.

You then zoom in on a list of length $\binom{M+3-i_0}{3}$, and again you are given a $1$-based index to it. There are $\binom{M+2-(j_1-i_0)}{2}$ quadruples with $i_1 = j_1$. This means that the first $\binom{M+2}{2}$ quadruples start with $i_0,i_0$; the following $\binom{M+1}{2}$ with $i_0,i_0+1$; and so on. Having found $i_1$ this way, you can find $i_2$ and $i_3$ by repeating the same argument twice more.

The same argument, run in reverse, can be used to calculate the index given the quadruple.  Assuming binomial coefficients can be calculated in constant time and that integer arithmetic is constant time, this algorithm runs in time $O(4\cdot M)$, or $O(4\cdot\log M)$ with $O(4\cdot M)$ preprocessing (for fixed $M$). I'm including the $4$ since if you had $t$-tuples instead of quadruples, you could replace it with $t$.


Differences between Church and Scott encoding

It's correct as long as all the arguments $x_1 ... x_{A_i}$ are recursive occurrences of the same structure. Otherwise there's no way to say what the Church encoding should be without more information.

That is the major difference between the Church and Scott encodings. If we think in terms of types, then for a fixed point type:

$T \cong F T$

the Church encoding of $T$ has a type like:

$(F r \to r) \to r$

while the Scott encoding has a type like:

$(F T \to r) \to r$

So, Scott encodings generally require some other source of recursion/iteration, both at the value level, because it only gives you access to one level of unfolding at a time, and at the type level (if you have one), because the fixed point type $T$ is still present in the type of the Scott encoding.

However, this means that Scott encodings are much better than Church encodings for some things. For instance, it's obvious how to write the (clamped) predecessor for Scott encoded naturals $\mathbb{N} = \forall r. r \to (\mathbb{N} \to r) \to r$:

pred n = n 0 (\pn -> pn)

However, for the Church encoded naturals:

$\mathbb{N} = \forall r. r \to (r \to r) \to r$

writing the predecessor function is a challenging exercise (and the resulting function is expensive).


is it possible to create an avl tree given any set of numbers?

AVL trees are a kind of binary search trees. As such, they implement the following operations, among else:

Initialize an empty tree.
Add a value to the tree.
Remove a value from the tree.
Search a value in the tree.

Try to use some of these operations to answer your question.


Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$

The pumping lemma can only be used to show that a language is not regular, not that it is regular. This is, I think, the fundamental misunderstanding here... that you are unable to use the pumping lemma to prove a language irregular does not constitute a proof of irregularity.

A language is regular if, equivalently,

it can be accepted by an NFA
it can be generated by a regular grammar
it can be described by a regular expression
it can be partitioned into finitely many equivalence classes under the indistinguishability relationship (as per the Myhill-Nerode theorem)

This last point can usually be pretty helpful in cases where the pumping lemma fails. Here, you merely need to demonstrate that there are infinitely many equivalence classes for strings in your language; you could argue that strings of the form $ab^nc$ constitute separate classes for all $n$.

Furthermore, as pointed out in the comments, you can often use closure properties of language classes in order to demonstrate that a particular language isn't in the class. For instance, you know that regular languages are closed under intersection. Using that fact, you could show that your language can't be regular, since if it were, the language $ab^nc^n$ would be regular (a contradiction, since you know that language isn't regular... you could even prove this easier version with the pumping lemma).

EDIT: Just in case how to apply the pumping lemma here is unclear, I'll give an example.

Choose the string $uvw = ab^pc^p$. Since $|uv| < p$ and $v > 0$, $v$ must be some non-empty string possibly beginning with a single $a$, followed by multiple $b$'s. If $v$ contains the $a$, pumping will cause there to be a different number of $a$'s, so we get a string not in the language. If the string does not contain the $a$, it consists only of $b$'s, and pumping will cause the number of $b$'s to be different from $n$. The resulting string is not in the language since the number of $b$'s is not equal to the number of $c$'s. Therefore, this string cannot be pumped to another string in the language, a contradiction of the assumption the language was regular; hence, the language is not regular.


Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph

(Answered also on https://cstheory.stackexchange.com/questions/47691/)
A ($2C_4$, $C_5$, $P_5$)-free graph may have exponentially many maximal cliques.
For example, the complement of the disjoint union of $n/3$ triangles with $3^{n/3}$ maximal cliques is $K_1 \cup K_2$-free, and thus has none of $2C_4$, $C_5$, $P_5$ appear as an induced subgraph.
https://doi.org/10.1007/BF02760024
Note: If the complement of a graph has $k$ pairwise independent edges, then they give you $2^k$ maximal cliques. Conversely, it is known that the number of maximal cliques is upper-bounded by a function of the maximum number of independent edges in the complement .
https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230230308


What is the difference between speculative execution & branch prediction?

“Branch prediction” will predict whether a particular branch is taken or not. The prediction can be right or wrong; whoever designs the hardware for it will want the prediction to be correct as often as possible.
Starting with a predicted branch, we don’t know if the instructions we execute should actually be executed, so we start with speculative execution. At some point the processor will learn correctly whether the branch should have been taken or not. If the branch was predicted correctly, the speculative execution is turned into non-speculative. If the branch was predicted incorrectly, all the results of speculative execution are thrown away and you continue with the correct branch.
Car analogy: You drive a car, I have the map. I say “I think you need to turn left” = branch prediction. You turn left = speculative execution. Later I tell you if the turn was correct or wrong.


Minimum circles to cover a set of points and avoid another set of points

The following algorithm will find some set of circles, containing all the points in the set $A$ except all the points in the set $B$. This solution might be not optimal (please see the @j_random_hacker counterexample in comments), and it's unclear how close this solution will be to the optimal one. The time complexity of this algorithm is exponential, cause it needs the Set Cover Problem solution as one of its steps.

Step 1. Build Voronoi Diagram of the set $B$. This diagram will consist of cells, nodes, line segments and rays. Each node will correspond to (at least) three points from the set $B$, and each ray will correspond to exactly two points from the set $B$.

Step 2. For each Voronoi node construct a maximal empty open disk with center in this node. These disks will have (at least) three points from the set $B$ on their boundary, and they won't contain any points from the set $B$. The number of such disks will be $\Theta(|B|)$.

Step 3. For each Voronoi ray construct a maximal empty open disk with center at this ray and infinitely large radius - it'll be actually a halfplane, corresponding to two points from the convex hull of the set $B$. These "disks" will have exactly two points from the set $B$ on their boundary, and they won't contain any points from the set $B$. The number of such "disks" will be $\Theta(|B|)$.

Step 4. For each point from the set $A$ find all disks, constructed above, containing this point. Each such point may belong to more than one disk, and each disk may contain any number of points from zero to $|A|$. Find a minimal subset of the set of all disks, which contains all the points from the set $A$. This is the classic Set Cover Problem, which is NP-complete (it's tempting to try to use geometric nature of this sub-problem to accelerate the search, however it won't be possible - please see the Geometric Set Cover Problem page for more details).

I'm thankful to @DiscreteLizard for pointing my error out in the previous version of this answer, and for suggesting the term "disk", which looks more adequate than the "circle".

I'd call this problem a "Bomber Problem" - we try to use a minimal number of bombs to strike all needed locations except some friendly ones. Sorry for militaristic jargon!


What is a fixed point in the context of Roger's fixed-point theorem?

The notation is explained in the Wikipedia entry (though regrettably after its first use): for partial functions $f,g$, we say that $f\simeq g$ if for all inputs $x$, $f$ halts on $x$ iff $g$ halts on $x$, and if both halt on an input $x$, then $f(x) = g(x)$. In other words, $f$ and $g$ compute the same partial function, and so they are semantically equivalent: they result in the same outcome.

The idea behind semantic equivalence is that two programs might be different but could be equivalent in the sense that they compute the same function. For example, if there are two statements $x \gets 0; y \gets 1$ and we switch their order to $y \gets 1; x \gets 0$ then the resulting programs are different syntactically but equivalent semantically.

Roger's theorem shows that for every total computable function $P$, which we think of as a transformation rule for programs, there is some program $e$ that is equivalent to $P(e)$. The rest of the Wikipedia entry explains why this is useful.


Is P = {  | M rejects w} the complement to Atm = {  | M accepts w}?

The answer to the question in the title (is $P$ the complement of $A_{tm}$) depends on several issues. To see why, let's start by computing the complement of $A_{tm}$:
$$
\overline{A_{tm}} = \{ \langle M,w \rangle : M \text{ does not accept } w \} \cup \{ x : x \text{ is not of the form } \langle M,w \rangle \}.
$$
If you choose an encoding for $\langle M,w \rangle$ for which there exist strings which are not of the form $\langle M,w \rangle$, then $P$ is definitely not the complement of $A_{tm}$. However, there do exist encodings in which you can decode any string into a Turing machine and an input string. In that case,
$$
\overline{A_{tm}} = \{ \langle M,w \rangle : M \text{ does not accept } w \}.
$$
You are asking whether this is the same as
$$
P = \{ \langle M,w \rangle : M \text{ rejects } w \}.
$$
The question is how you define acceptance and rejection. Here is one possible definition:

  A Turing machine accepts an input if it halts on an accepting state. It rejects an input if it halts on a non-accepting state.

Under this definition, there is also a third option: the Turing machine never halts. So $P$ and $A_{tm}$ are not complements of each other. Here is another definition:

  A Turing machine accepts an input if it halts on the input. Otherwise it rejects it.

Under this definition, $P$ and $A_{tm}$ are complements of each other. If you define the language of a Turing machine as the set of strings it accepts, then both definitions are equivalent (you can modify a Turing machine to fit either), but the exact choice does matter for your particular question.


I don't think the term has a clear standard accepted meaning, so if you are reading it somewhere, you'll either have to infer from context or hope they defined the term.  But as a general guideline, I would guess your former choice is much more likely than your second choice; I think it's much more likely to be a single bit than a bitstring.

If you are thinking of using that term in your own writing, I encourage you to define that term before using it.


Combine abstract factory with decorator pattern

I don't see that as a problem.

Factory are used to implement the Dependency Injection (DI) pattern, where one wish to dispense a section of code from having to know how to construct objects of a certain class, which could involve other secondary classes and render the aforementioned section of code more coupled to the rest of the codebase. The less coupling, the easier it is to update the code — the client part (that section of code), or the service part (the object being created — Cake in your case).

When it comes to decorators, you are essentially describing an algebra on the object: you start from some class instance (Cake object), and by applying an operator (the decorator), you obtain another object from the same class (to be precise, it's a subclass, so it's more akin to a refinement operation, but for our purpose, ignoring that part is OK).

The client code needs to know about that algebra, as a part of how it may manipulate the object, so you have to disclose this information. Now it could be in the form of a set of methods on the Cake class, a set of functions acting as operators,  or methods on a class implementing that algebra.

The 2nd option might be more complicated to implement,  if decorators need to share some information on the Cake class only available at runtime; you'd have to implement the DI pattern on them,  and you would end up with either the first or the 3rd solution.

The remaining options are equivalent from the client code point of view, not adding more dependency either way.


Is there a name for a graph whose vertices consist of edges of an existing graph connected by an edge if they shared a common vertex?

This is called the line graph of $G$. It actually has a wide variety of uses, as seen on that Wikipedia page, and the terminology is sufficiently standard that you should be able to mention it in a paper without defining it.


First, I would like to modify your statement slightly to remove any chance of confusion. When you say, "... $T(n) \le cn\log n$ for any appropriate $c > 0$ and $n \ge n_0$", it actually means $T(n) \le cn\log n$ for some appropriate $c > 0$ for all $n \ge n_0$.

Next, these constants for proving the lower bound can be (and generally are) different from these when proving the upper bound. I will demonstrate with your example:

Upper bound:
$T(n) = 2T(\frac{n}{2}) + n \le 2(c\cdot\frac{n}{2}\log{\frac{n}{2}}) + n$ (induction hypothesis)
$T(n) \le cn\log n - cn\log 2 + n = cn\log n - (c - 1)n$
$T(n) \le cn\log n$ for all $n$ for any $c \ge 1$
Therefore, $T(n) = O(n\log n)$

Lower bound:
I'll use a different constant $b$ for this, just to emphasize that the two constants are different.
$T(n) = 2T(\frac{n}{2}) + n \ge 2(b\cdot\frac{n}{2}\log{\frac{n}{2}}) + n$ (induction hypothesis)
$T(n) \ge bn\log n - bn\log 2 + n = bn\log n + (1 - b)n$
$T(n) \ge bn\log n$ for all $n$ for $0 \le b \le 1$
Therefore, $T(n) = \Omega(n\log n)$

So basically, you need to choose some constant such that the inequality holds for all sufficiently large $n$. These constants can (and generally are) different for different inequalities.

Note: I have assumed that $n$ is a perfect power of 2 in the above recursions to do away with the floor function. For asymptotic analysis, they do not really matter. These notes may help things become clearer.


Theory

There's a simple argument to show you can't help to do that much better.  In particular, testing for feasibility of a set of linear inequalities can't be too much easier than optimizing a linear objective function subject to a set of linear inequalities.

Why?  If we want to optimize the objective function $\Psi$ subject to a set $\mathcal{S}$ of inequalities, one way to do that is to use binary search on the value of the objective function.  This can be done by repeated feasibility testing of a set of linear inequalities of the form $\mathcal{S} \land \Psi \ge c$, where $c$ is a constant.  In particular, you use binary search to find the largest value of $c$ such that $\mathcal{S} \land \Psi \ge c$ is feasible.

Very roughly speaking, binary search can be expected to succeed within $O(\lg n)$ iterations.  Therefore, testing for feasibility can't be more than $O(\lg n)$ times faster than maximizing an objective function.

Practice

I don't know of any more efficient way to test for feasibility of a set of linear inequalities, than simply to solve a linear program using standard linear solvers.  Basically, you pick any old objective function, and use the linear solver to maximize it subject to the set of linear inequalities.  I don't know of any procedure that is faster in practice than this straightforward approach.


I Asked this once and my post was closed. I remember saying i have no idea, and i'm in need of some enlightenment. Eventually i found the solution somewhere and i think that my problem was that i was not as comfortable as i thought with the ideas appearing in the proof of the Cook-Levin theorem.

The interesting direction is $EXP\subseteq APSPACE$. Let $L\in EXP$ be some language decidable in $2^{n^c}$ time, i.e. there exists a Turing machine $M_L$ which runs in $2^{n^c}$ time deciding $L$.

For any input $x$, we can look at the $2^{|x|^c}\times 2^{|x|^c}$ computation table of $M_L$ on x. The i'th row describes the $i'th$ configuration during the computation: $\sigma_1\sigma_2...\sigma_i q\sigma_{i+1}...\sigma_{2^{|x|^c}}$, where $\sigma_i\in \Sigma\cup \Gamma, q\in Q$. This means that at the $i'th$ step $\sigma_1...\sigma_{2^{|x|^c}}$ is the content of the working tape, we are at state $q$, and the head is at the symbol appearing after $q$ (we should also include the input somewhere, but specifics don't really matter here).

We denote by $C_{ij}$ the content of the cell in the $i'th$ row and $j'th$ column in the computation table of $M_L(x)$.

Our APSPACE machine will be able to decide whether or not $C_{ij}=\sigma$ (then you can go over the last row and check if $q_{acc}$ is written somewhere). Note that the index $i$ can be written in polynomial number of bits.

As in the Cook-Levin theorem, the important fact is that computation is local. The value of $C_{ij}$ is determined by the values $C_{i-1,j-1},C_{i-1,j},C_{i-1,j+1},C_{i-1,j+2}$, say by some known function $g$ ($g$ of course depends on the transition function of $M_L$), meaning:

$\forall \sigma\in\Sigma\cup \Gamma\cup Q: \hspace{1mm} C_{ij}=\sigma \iff \exists \sigma_1,\sigma_2,\sigma_3,\sigma_4: \hspace{1mm} C_{i-1,j-1}=\sigma_1 \land
C_{i-1,j}=\sigma_2\land C_{i-1,j+1}=\sigma_3 \land C_{i-1,j+2}=\sigma_4 \land \sigma = g\left(\sigma_1,\sigma_2,\sigma_3,\sigma_4\right).$

To decide whether $C_{ij}=\sigma$, under existential quantifiers, nondeterministically guess $\sigma_1,\sigma_2,\sigma_3,\sigma_4$. Verify that
$\sigma = g\left(\sigma_1,\sigma_2,\sigma_3,\sigma_4\right)$, if not reject.

The next step is to verify recursively that $C_{i-1,j-1}=\sigma_1 \land
C_{i-1,j}=\sigma_2\land C_{i-1,j+1}=\sigma_3 \land C_{i-1,j+2}=\sigma_4$. Let us denote by $S_i$ the space used by our machine, when it begins with the i'th configuration (i.e. verifying $C_{ij}=\sigma$ for some $j,\sigma$). Even if we use the same space for all four calls, you get $S_i=S_{i-1}+poly(|x|)=...=2^{|x|^c}poly(|x|)$. This happens because we keep a call stack (we dont overwrite the current frame), to overcome this:

under universal quantifiers, write nondeterministically $\left(J,\sigma_J\right)\in \left\{\left(j-1,\sigma_1 \right),\left(j,\sigma_2 \right),\left(j+1,\sigma_3 \right),\left(j+2,\sigma_4 \right)\right\}$ (suppose for simplicity that your machine has four transition functions), and output "yes" if $C_{i-1,J}=\sigma_J$.

The universal quantifiers allowed us to compute the conjunction of four recursive calls simultaneously, thus we dont need to keep a call stack. In that case, in all times we need only remember $i,j,\sigma$, which requires polynomial space (in the recursive call for $C_{i-1,J}$, we use the same space that was used to store $i$).


Chernoff-Hoeffding bounds for the number of nonzeros in a submatrix

Okay, here is a full answer.

We will use the fact, that any bipartite graph of maximum degree $d$ can be broken into (at most) $d$ matchings.

In our case, this means that we can split $A$ into (at most) $\sqrt{k}$ disjoint sets of elements $S_i\subseteq\{(i,j)\in[n]\times[n] \mid A_{i,j}=1\}$ of size at most $n$ such that any every element in each set has a unique row and column.
(This uses that a $1$ in $A$ can be seen as an edge in the $n\times n$ bipartite graph that is the matrix.)

Now let $X$ be the total number of $1$s in your $n/\sqrt k\times n/\sqrt k$ matrix, $A^\ell$, and let $X_i$ be the number of elements coming from $S_i$.
Then $X\ge t\implies \exists_i\, X_i\ge t/\sqrt k$ and so
$$\Pr[X\ge t]\le \sqrt k \Pr[X_1 \ge t/\sqrt k]$$
by the union bound.
Now, because elements in $S_1$ don't share any rows/columns, it is easy to analyze using your original approach.

In particular, reorder the rows and columns using the matching, so that the first element in $S_1$ is $(1,1)$ the next is $(2,2)$ and so on.
Let $r_i$ be the random variable that is 1 if row $i$ is chosen and $c_i$ likewise. Then we want to upper bound $\Pr[\sum_i r_ic_i \ge t]$.
Notice $E[r_ic_ir_jc_j] = E[r_ir_j]E[c_ic_j] \le E[r_i]^2E[c_i]^2$ by Maclaurin’s Inequality, so
$$\exp(t\sum_i r_ic_i) = \sum_k t^k/k!\,E\left(\sum_i r_ic_i\right)^k \le \sum_k t^k/k!\,E\left(\sum_i b_i\right)^k = \exp(t\sum_i b_i)$$
where $b_i$ is a normal binomial variable with $p=(n/\sqrt{k}/n)^2=1/k$.

Finally, we then get

$$\Pr[X\ge t]\le \sqrt k \Pr[X_1 \ge t/\sqrt k] \le \sqrt k \exp\left(-2\left(\frac{t-p n \sqrt{k}}{n\sqrt k}\right)^2 n\right)$$

or more simply

$$\Pr[X\ge \lambda\sqrt{nk}+n/\sqrt k]\le \sqrt k \exp(-2\lambda^2)$$

or if we use the Hoeffding bound for small values of $p$ (large $k$):

$$\Pr[X\ge \lambda\sqrt{nk}+n/\sqrt k]\le \sqrt k \exp\left(\frac{-\lambda^2}{2/k+\lambda/\sqrt n}\right)$$

Note that if we had simply assumed all elements were independent, we would have gotten the bound $\Pr[X\ge \lambda\sqrt{n\sqrt{k}}+n/\sqrt k]\le \exp(-2\lambda^2)$. Equal to ours except for a factor $k^{1/4}$ in the exponent.


In my opinion the problem statement seems poorly posed.  It's not clear what is meant by the problem statement.

Normally, if we write $a$ or $b$ the assumption is that they are a constant: they do not depend on $n$.  If they are intended to be a function of $n$, then they should be written as $a(n)$ or $b(n)$.  Since that wasn't done, the only assumption I can see that makes sense is to assume they are constants.  But then if they are constants, then writing $a,b = \omega(1)$ doesn't seem to me to make sense.

So, I suggest you go talk to your instructor to ask them what they had in mind and how one should interpret the question.  We can't solve the question until we know what the question is asking.

Basically, I am validating that the confusion you are having seems reasonable: it seems reasonable to me to be confused about that, as I find the problem statement confusing.