Skolem constant in existential instantiation for first order logic

Perhaps it will help to discuss this in a broader context, so let me explain this concept with regard to the resolution principle, which is used to check if some formula is unsatisfiable.
Resolution for propositional logic's formulae is rather straightforward and is based on the Conjunctive Normal Form.

We want to apply resolution to first-order formulae, i.e. sort of reduce FOL to propositional logic. One way to do that is to convert the original formula via Skolemization into a formula of the form
$$\forall x_1x_2...x_nM,$$
where $M$ (called 'matrix') is a formula without quantifiers and in CNF. To do this conversion we must get rid of existential quantifiers. The rule you provided does that in the special case where the current existential quantifier is not in scope of any universal quantifiers.

The intuition here is if it is known there exists some $\nu$ for which $\alpha$ holds, then why don't we "pretend" we know that $\nu = k$, where $k$ is some fresh constant. It needs to be 'fresh' in order not to introduce any dependencies between unrelated things.
And the reason we are allowed to "pretend" we know $\nu$ is that there is a theorem which claims that Skolemization preserves unsatisfiability.

Note: recall that we only want to check if a formula is satisfiable/unsatisfiable, so the skolemized formula is not necessarily equivalent to the original one.


Vertex coloring with an upper bound on the degree of the nodes

Yes, it's still NP-hard. 3-COL is still NP-complete for planar degree 4 graphs [1].

Dailey, D. P. (1980), "Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete", Discrete Mathematics 30 (3): 289–293, DOI:10.1016/0012-365X(80)90236-8


Correlation between high cpu/ram usage and poor computer performance

There's a general-interest article from the IEEE about transistor aging that's based on the paper "An Array-Based Odometer System for Statistically Significant Circuit Aging Characterization" (2011) by Keane, Zhang, and Kim. They present:

  A system that facilitates efficient statistical aging measurements involving the mechanisms of bias temperature instability (BTI) and hot carrier injection (HCI) stress.

Roberto Lacerda de Orio's dissertation "Electromigration Modeling and Simulation" (2010) has a comprehensive treatment of the physics of electromigration, as well as a numerical model and "several simulation studies of electromigration".

You may find more references in this SuperUser thread.


when to use preorder, postorder and inorder binary search tree traversal strategies

"Whatever you want in your application. This is like asking when you should drink beer, orange juice or water", commented by one wise user, Gnasher729.

"You use whichever gives you the results you need. Your question is like asking 'What are some examples of when to use subtraction/multiplication practically? When does it make more sense than addition?'", commented by another wise user, David Richerby.

What do the above similes mean exactly? If you have understood what are preorder/postorder and inorder traversals clearly, it becomes obvious for you to choose which one make more sense to use.

So the best answer could simply be reviewing the definition of those traversals. Here is one way to understand them in the usual context of binary trees.

A preorder traversal visits the root node first, followed by a preorder traversal of the left subtree, followed by a preorder traversal of the right subtree.
An inorder traversal does an inorder traversal on the left subtree, followed by a visit to the root node, followed by an inorder traversal of the right subtree.
A postorder traversal does a postorder traversal of the left subtree, followed by a postorder traversal of the right subtree, followed by a visit to the root node.

In a nutshell, each traversal traverses a binary tree recursively. The "pre/in/post" refers to when the root node, which store the value in the middle, is visited, which is first, between first and last, and last respectively. Note that left subtree is always visited before right subtree.

Understanding cannot be solid without relevant examples and exercises. You may check for example chapter 12, "Binary Search Trees" of CLRS to find some.

Here are some usual usage examples.

Preorder traversal is used to get prefix expression on of an expression tree, Polish notation
Postorder traversal is used to get postfix expression of an expression tree, reverse Polish notation
In case of binary search trees, inorder traversal will traverse  nodes in non-decreasing order. This is probably the easiest result if not the most common result. To traverse nodes in non-increasing order, inorder traversal but visiting right subtree before left subtree can be used.


Constructing the matrix of a controlled quantum operation

For any gate $U_n$ on $n$-qubits, you can create a controlled version by taking

$$\text{c-}U_n = \left (\begin{matrix}
I_n & 0 \\ 0 & U_n
\end{matrix}\right)$$

where $I_n$ is the identity matrix (of the same dimension as $U_n$). Note that this gate works on $n+1$ qubits, where the first serves as the control bit.

This should work because the controlled gate is required to satisfy

$\text{c-}U_n |0\rangle|x\rangle = |0\rangle|x\rangle $, and
$\text{c-}U_n |1\rangle|x\rangle = |1\rangle(U_n|x\rangle) $

where $|x\rangle$ is an $n$-qubit state. You should be able to check that the above matrix satisfies exactly this.


Cast to boolean, for integer linear programming

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

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

Update

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


Does the master theorem apply to T(n) = 3T(n/3) + nlogn?

Let's take the slightly more general case where $a=b$ and $f(n)=n\;log\;n$ (in your case, $a=b=3$). Assume the usual restrictions on $a$ and $b$ hold. Then $n^{log_ba}=n$. This might lead us to consider case 3 of the Master Theorem since $f(n)=\Omega(n)$.

However, the theorem requires that there exist an $\epsilon > 0$ such that $n\;log\;n = \Omega(n^{1+\epsilon})$. Is this condition met? Equivalently, is it true that $log\;n = \Omega(n^{\epsilon})$ ? As long as $\epsilon$ is positive, this is never true. The polynomial will grow faster. Therefore, the Master Theorem does not apply. You could use iteration or some other method to solve the recurrence.

After searching around, I've found a few references to a corollary of the Master Theorem that addresses polylogarithmic functions. In this version, if we can show that $f(n)=\Theta(n^{log_ba}log^{k}n)$ for some $k \geq 0$, then we can conclude that $T(n) = \Theta(n^{log_ba}log^{k+1}n)$. In our case, $f(n) = \Theta(n\;log\;n)$ with $k=1.$ Therefore, we could conclude that $T(n)=\Theta(n\;log^{2}n)$. However, I don't think this is commonly referred to (or taught) as part of the Master Theorem.

Reference 1

Reference 2


Distributed MST Construction in O(log log n) Rounds in a Clique

I think I've found an answer, so will post here what I have. My proof seem to cover both scenarios I've mentioned. I still think their proof is incomplete. But in case I'm wrong, I would love to be corrected.

Similar to them assuming there is $e'$ outgoing from $F_1$, I assumed there was $e'$ outgoing from $F_3$ that is in $\hat{F_{1}}$, of lower weight than $e$.

If it was chosen, than it happened before choosing $e$, since its lighter. But then we get a contradiction to $e'$ being outgoing of $H_1$. So it wasn't chosen. If it wasn't chosen because it created a cycle, then it's yet again a contradiction to it being outgoing from $H_1$, since if it created a cycle, then $F_3, F_4$ were already merged by the time we reached $e'$, and therefore when we reached $e$ as well.

Therefore we're only left with the option that it was deemed "dangerous" (and therefore removed). Then either $e'\notin\mathcal{A}\left(F_{3}\right)$ or $\hat{F_{3}}$ was finished by the time we reached $e'$ .

If $\hat{F_{3}}$ was finished , then by the time we get to $e$ (which happens after $e'$, as $e'$ is lighter). But we assumed $F_3$ is part of $H_1$ by the time we reach $e$, therefore $\hat{F_{1}}$ is also finished, which is a contradiction to it being unfinished.

Then $e'\notin\mathcal{A}\left(F_{3}\right)$. This can happen for two reasons (as per their proof):

There exists a lighter (than $e'$) $e''$ in $\mathcal{A}\left(F_{3}\right)$ (such that $e''$ touches the same base fragments $e'$ touchs, which means its basically the same logical edge, just of lower weight). Therefore since $\hat{F_{3}}$ wasn't finished, and there were no cycles, $e''$ was added earlier than $e'$ and therefore than $e$. But then by the time we reach $e$, $e'$ is no longer outgoing from $H_1$. Contradiction yet again.
Then there exists $\mu$ lighter edges in $\mathcal{A}\left(F_{3}\right)$. Let $e''$ be the heaviest there (that is still lighter than $e'$ and therefore than $e$). Therefore after inspecting $e''$, $\hat{F_{3}}$ is deemed finished, which is yet again a contradiction.


There are existing dictionaries that list pairs of characters that are visually similar.  See, e.g.,

https://security.stackexchange.com/q/36257/971
https://security.stackexchange.com/q/128286/971
https://stackoverflow.com/q/4846365/781723

Therefore, I suggest you try modified edit distance: compute the edit distance, but with a cost function that treats the distance between a pair of visually similar characters as zero or much smaller than the distance between a pair of different characters.

I recommend using the Damerau–Levenshtein edit distance. It includes transpositions among the changes it considers.  There's some reason to believe this corresponds better to mistakes made by humans.  So, maybe it'll correspond better to what humans consider similar.

Another plausible approach would be to render the two strings to images (using whatever font you think will be used to display them), then compare the images.

To compare how visually similar the images are, a basic starting point would be to use L1 or L2 distance (both have been shown to correspond well to human perception in some situations).  This probably won't be enough because it will fail badly if the images aren't perfectly aligned.  To address that, I suggest you apply a sort of edit distance that allows inserting or deleting entire columns of pixels (a full-height column), in addition to changing individual pixels.

It's not clear whether machine learning will be useful here.  The obvious approach to try first would be to compute the edit distance and compare it to some threshold.  That might be sufficient.


The PDA have to finish reading the input?

I think the PDA would stuck as to accept the input string "abcd", the complete input string needs to be read. But your PDA will work only till 'c' is read and get stuck when it finds another letter 'd', but has no transition state.


Well, that of course depends on what sort of program you are trying to design.

If you are designing an accounting program for your aunt's chocolate shop, I very much doubt category theory will be of much use.

But there are of course situations in which category theory is enormously useful in design of programs (by which I also mean data structures, libraries, and so on). Such situations occur mostly when the programs involved are of a mathematical nature.

If you want to write programs that compute with exact real numbers and other structures occurring in mathematical analysis, the first question you need to answer is what it means to correctly implement a complicated mathematical object (such as a differentiable function, a manifold, etc.). Here it helps very much to know some category theory and logic, because they give you a systematic way of translating definitions of mathematical structures to specifications and implementations of corresponding data structures. The buzzword you should look for is realizability theory. But this is just one example.

The best way to see how category theory comes in handy is to look at programs written by people who know a lot of category theory (and mathematics in general). An obvious example of this is Martín Escardó and his impossible functionals, for instance:

  M. Escardó and P. Oliva: What Sequential Games, the Tychonoff Theorem
  and the Double-Negation Shift have in Common, Mathematically Structured Functional Programming 2010, ACM Press. (with companion Haskell and Agda files)

You may complain that this is not just category theory but also logic and topology. Such complaints would be severely misguided. The best category theory is always mixed with other things.

Lastly, I would advise against drawing grand conclusions about nature of things based on a bit of self-assigned reading.


How can P =? NP enhance integer factorization

If $P=NP$, and we have an algorithm that can solve the k-SAT problem in polynomial time, then integer factorization can simply be reduced to k-SAT by describing factoring as a problem in k-SAT.

Essentially it works as follows: You make a bunch of variables each representing the bits of $p$, and $q$, and $n$. Then you formulate the k-SAT problem as $p*q=n$. Since $n$ is known, you can set those values. Then a satisfying assignment will describe a valid $p$ and $q$. To describe the multiplication in k-SAT, you can use any of the known multiplication algorithms and describe it's logical circuit in k-SAT. For more info on reducing factoring to k-SAT, see here.

As for understanding factoring better, that would probably require more research and analyzing the magic algorithm (that can solve NP-complete problems in deterministic polynomial time), and perhaps specializing it to the integer-factoring formulation of k-SAT problem (which obviously has a very specific structure, depending on the multiplication algorithm used).


How can mainstream OO languages support strong binary operations by classes?

I will attempt an answer, though, the discussion in comments with @yuval-filmus seems to be going in the right way.

Let's recap: The book discusses ADTs against objects in their strictest sense.

ADTs are entirely public about their unique representation. Belonging in the ADT means satisfying said representation, and so binary methods can rightfully assume that both operands have that exact representation.

Objects are entirely opaque about their non-unique representation. Belonging in the object type means satisfying its interface, with no guarantees as to how this is achieved internally, and so binary methods may only assume that the two objects can respond to the same set of messages, but are quite possibly implemented entirely differently.

Even if the interface has a getter getFoo, that is no guarantee that the object has a foo field that you could poke at directly. Maybe some mock object is faking it with a method that returns a constant Foo. All you know as a client is that it supports a getFoo call.

Where the class-based object approach differs from the pure object approach is that the knowledge of the type of an object (the class it belongs to) gives you some guarantees about the structure of the object, and so, allows you to partially break the abstraction barrier.  Because all objects of a class must have been built with, at least, a call to the constructor of that class, you can guarantee the presence of some fields (initialized during that constructor), and so the language lets you access those directly, foregoing the mandatory message-passing of the pure object style.

This is a strength and a weakness:

because you have access to the concrete representation, you might be able to implement operations more efficiently,
but because you ask for a member of the class, a "mock" implementation is no longer a valid object for this operation: if you want to allow such an object, you must define an interface, and you are effectively back to a pure-object approach.

As in my other answer to one of your question, this paper is extremely relevant:

http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf
"On Understanding Data Abstraction, Revisited", by William R. Cook

Of particular interest are section 3.3 on autognosis, which hints at why binary methods in the ADT style are strong, whereas in the object style are weak, and section 5 which explains a bit the difference between what is considered a pure object approach and the more general objects available in Java. (You can program in the pure object style in Java, but you have to follow a given discipline about not breaking certain abstraction boundaries, which relates to the discussion you've had in the comments)

I hope this makes sense, I'm sorry you had trouble with my other answer, this is a hard topic to get your head around, but once you have fixed your misunderstandings you will see it is not that complex!


Is there a canonical definition of “pure” function?

As noted in this paper Imperative Functional Programming, (1993) by Peyton-Jones and Wadler (among the group of researchers that created Haskell):

  We focus on purely-functional solutions, which rule out side effects,
  for two reasons. Firstly, the absence of side effects permits
  unrestricted use of equational reasoning and program transformation...

the focus is on absence of side-effects to enable program transformations (i.e compiler optimisations).

What are side-effects? This paper in turn points to Integrating functional and imperative programming (1986) by Gifford and Lucassen, which mentions four types of effect classes: Pure, Function, Observer and Procedure. So, the term "pure function" derives from this paper.

  a PURE is referentially transparent: it does not cause side-effects,
  its value is not affected by side-effects, and it returns the same
  value each time it is evaluated.

Note, however, that Peyton-Jones and Wadler mentioned shortcomings in this approach. Worth noticing, they say, is the programming language Clean that uses linear types to introduce side-effects in a safe manner (i.e. safe for the compiler). Basically, it threads the World as a variable in all I/O related functions, including the main entry point.

With that, it is possible to have a pure functional language interacting with the world and having side-effects (I/O, the OS, the Windowing system, etc), contradicting partially your wikipedia definition. One can in fact say that Haskell has Clean as one of its influencers; although it departs from linear types and uses another type-level construct (monads) to guarantee linearity, i.e. a single-reference at all times.


Maximum Changes that don't Break the Build

The problem you're trying to solve is undecidable, since you can't tell if any of the changes makes the program go into an infinite loop.


You haven't stated what the distribution of the initial vector is. I'm assuming that each $b_i$ is independently set to $0$ or $1$ with equal probability.

The first step is to find a formula for the expectation $E$. Let $k$ be the value of $k$, that is, the number of 1s in the vector. We know that $k$ has binomial distribution $\mathrm{Bin}(n,1/2)$. Then
$$
E = \sum_{\ell\text{ odd}} \Pr[k=\ell] \ell = \sum_{\ell\text{ odd}} 2^{-n} \binom{n}{\ell} \ell.
$$
A good idea now is to use the binomial identity $\binom{n}{\ell}\ell = \binom{n-1}{\ell-1}n$:
$$
E = \frac{n}{2^n} \sum_{\ell\text{ odd}} \binom{n-1}{\ell-1} = \frac{n}{2^n} \sum_{r\text{ even}} \binom{n-1}{r}.
$$
When $n$ is even, the binomial identity $\binom{n-1}{r} = \binom{n-1}{n-1-r}$ implies that
$$
\sum_{r\text{ even}} \binom{n-1}{r} = \frac{1}{2} \sum_{r\text{ even}} \left[\binom{n-1}{r} + \binom{n-1}{n-1-r}\right] = \frac{1}{2} \sum_r \binom{n-1}{r} = \frac{1}{2} \cdot 2^{n-1},
$$
and so
$$
E = \frac{n}{2^n} \cdot 2^{n-2} = \frac{n}{4}.
$$
I'll leave you the case of $n$ odd (you get the same answer, but a different trick has to be used).

The answer $n/4$ is what we expect. Here's why. If the if wasn't there, then $E$ would equal the expected value of $k$, which is $n/2$. As it is, we are only printing "with probability $1/2$", so we would expect the answer to be roughly half of $n/2$, that is, $n/4$. Since the printing condition depends on $k$, this heuristic calculation is wrong, though it turns out to predict exactly the correct value. Still, it lends credence to our calculation.


Regular languages over a finite alphabet are always countable: indeed, $\Sigma^*$ is countable. However, not every subset of $\Sigma^*$ is regular. This is because the set of regular languages is only finitely additive rather than $\sigma$-additive. That means that if $A_1,\ldots,A_\ell$ are regular then so is $A_1 \cup \cdots \cup A_\ell$, but the same isn't true for an infinite sequence. Indeed, every subset of $\Sigma^*$ can be written as an infinite sum of singletons (sets of size $1$), which are regular, but not all subsets of $\Sigma^*$ are regular. For example, the following subset of $\{0,1\}^*$ isn't: $\{ 0^n 1^n : n \geq 0 \}$.

You define a regular language as one which has a finite number of unique elements. Unfortunately, you don't define what these unique elements are, so your definition is vague at best. Regular languages have other definitions than the one given by Wikipedia - for example, they are the languages accepted by deterministic finite automata, by non-deterministic finite automata, and by Turing machines running in time $o(n\log n)$. Each of these has a finite number of states, which might correspond to your unique elements. A third approach defines a regular language as one having finitely many Myhill-Nerode equivalence classes (two words $x,y \in \Sigma^*$ are equivalent with respect to a language $L$ if for all $z \in \Sigma^*$, $xz \in L$ iff $yz \in L$).

Here is a Wikipedia-like definition of the regular languages (both definitions are the same for finite $\Sigma$). It is the smallest collection of languages which:

Contains all singletons $\{a\}$ for $a \in \Sigma$.
Closed under finite unions and intersections, under complementation, under concatenation, and under Kleene star.

Every regular language has a "proof" of its being regular which comes from applying the operations above. In the case of the Wikipedia definition, this proof is a regular expression, which is why they chose their particular definition. For example, $0^*1^* + 1^*0^*$, the language of "monotone" sequences over $\Sigma = \{0,1\}$, can be derived as follows from Wikipedia's rules:

$0$ is regular (singleton axiom).
$0^*$ is regular (Kleene star applied to (1)).
$1$ is regular (singleton axiom).
$1^*$ is regular (Kleene star applied to (3)).
$0^*1^*$ is regular (concatenation of (2) and (4)).
$1^*0^*$ is regular (concatenation of (4) and (2)).
$0^*1^* + 1^*0^*$ is regular (union of (5) and (6)).

My rules are more permissive: they allow complementation and intersection. You can try to prove that both definitions are equivalent - this is quite difficult from these definitions, but becomes much easier using either DFAs (deterministic finite automata) or Myhill-Nerode relations.


Showing a language is a subset of another language?

A language $B$ is a superset of another language $A$ if it contains all the strings of $A$ and some more. In your example, $A$ contains $ab$, but $B$ only contains string with $c$'s in them, so $ab\not\in B$, so $B$ is not a superset of $A$, i.e. $A \not\subseteq B$.

What you are looking for is a language $B$ which is not context-free but which does contain all of $A$. For example, you could let $C$ be some very difficult language, for example, the language of TMs that halt on the empty tape, or the language of prime numbers, and let $B=A\cup C$. Then whatever the complexity it $B$, you can be sure that it's not context-free. This trick won't always work. For example, if $A=\Sigma^{*}$, then no superset of $A$ exists, and certainly not one that isn't context-free.

What you read about one language a subset of another language is probably succinctly captured in the Wikipediag page on context-free languages (link) and that of regular languages (link) under the section of closure properties. A closure property is a theorem states that, for example, if $L_1$ and $L_2$ are both context-free, then $L_1 \cup L_2$ is also a context-free language. In this case you can say context-free languages are closed under union.


What is the $\mathcal O$ of subtraction-based GCD algorithm?

Suppose that $a,b$ are the two input numbers. At each step of the algorithm, the sum $a+b$ decreases, since (assuming $a > b$), the new numbers are $a'=a-b,b'=b$, and $a'+b'=a < a+b$ (since we stop when $b=0$). Thus the algorithm terminates in at most $a+b$ steps. This is almost tight: if $b = 1$, then the algorithm terminates in $a$ steps.

Summarizing, on inputs $a,b$, the number of steps (or arithmetic operations) is at most $a+b$, and could be as bad as $a$. In terms of the length $n$ of the input (number of bits needed to represent it), the number of operations is at most $O(2^n)$ (since $a,b \leq 2^n$), and could be as bad as $\Omega(2^n)$ (when $a = 2^n,b=1$). Thus the worst-case running time (as measured by number of steps) is $\Theta(2^n)$, where $n$ is the input length.


Jean Louis Krivine introduced an abstract calculus which extends the "Krivine Machine" in a very non-trivial way (note that the Krivine machine already supports the call/cc instruction from lisp):

He introduces a "quote" operator in this article defined in the following manner: if $\phi$ is a $\lambda$-term, note $n_\phi$ the image of $\phi$ by some bijection $\pi: \Lambda \rightarrow \mathbb{N}$ from lambda terms to natural numbers. Note $\overline{n}$ the church numeral which corresponds to $n\in\mathbb{N}$. Krivine defines the operator $\chi$ by the evaluation rule:
$$ \chi\ \phi \rightarrow \phi\ \overline{n_\phi}$$
I believe Kleene wizardry will show that this is sufficient to do what you wish: i.e. define a quote and eval operators, if $\pi$ is computable.

Note that Krivine is notoriously challenging to read (please don't get mad if you read this, Jean-Louis!), and some researchers have done the charitable act of trying to extract the technical content in a more readable manner. You might try to take a look at these notes by Christophe Raffali.

Hope this helps!

It occurs to me that there is another reference that may be relevant to your interests: the Pure Pattern Calculus by Jay and Kesner formalizes a variant of the $\lambda$-calculus which extends simple abstraction over a variable to an abstraction over a pattern representing a pattern calculus itself. This is phenomenally expressive and in particular allows one to deconstruct an application itself: if I am not mistaken, the term:

$$ (\lambda (x\ y). x)((\lambda x.x\ x)\ (\lambda y.y)) $$

reduces to $\lambda x.x\ x$. Again, I belive that this is more than enough to implement the quote and eval operators.


Doing matrix multiplication with $\lceil n^3 / \log n \rceil$ processors in $2\log n$ steps by Brent's principle

Yes, you are correct while all textbooks and lecture notes you and I have found so far are wrong in claiming "doing matrix multiplication with $\lceil n^3 / \log n \rceil$  processors in  at most $2\log n$ steps by Brent's principle"
There is hardly anything valuable to add to your meticulous calculation. Anyway, here is an example that specializes your calculation.
An example
Let $n=16$. We have two $16\times16$ matrices, $(A_{ij})$ and $(B_{ij})$ with $\left\lceil \dfrac{n^3}{\log_2n}\right\rceil=\left\lceil\dfrac{16^3}{\log_2 16}\right\rceil=1024$ processors.
It takes 4 parallel steps to compute all the $n^3=4096$ products of the entries $P_{ijk}=A_{ik} \cdot B_{kj}$ for $i,j,k \in \{1,2,\cdots,16\}$ with $1024$ processors.
How to compute $n^2=256$ sums of the $n=16$ numbers $P_{i1j}+ \ldots + P_{i16j}$ for $i,j\in\{1,2,\cdots,16\}$?
We first compute $256\times 8=2024$ sums of two neighbors $S_{ikj}=P_{i(2k-1)j}+P_{i(2k)j}$ for $i,j\in\{1,2,\cdots,16\}$, $k\in\{1,2,\cdots, 8\}$. It takes 2 parallel steps for 1024 processors, where $2$ is $\dfrac{\dfrac{n^3}2}{\dfrac{n^3}{\log_2n}}=\dfrac{\log_2n}2>1$.
There are $256 \times 4 = 1024$, $256 \times 2 = 512$, $256 \times 1 = 256$ sums of two numbers to calculate, respectively. Each of them will take one parallel step because of the serial dependency. We need $3 =\log_2n-1$ parallel steps.
So we need $4 + 2 + 3 = 9$ parallel steps in total, which is bigger than $\lceil 2\log_2 n\rceil = 8$.
Corrected statement
Multiplication of two $n\times n$ matrices can be done in no more than $3\log_2 n+1$ parallel steps with $\lceil n^3 / \log_2 n \rceil$ processors by Brent's principle.
Brent's principle
Here is one version of Brent's principle that applies to current situation.
(Brent’s principle): An algorithm involving $t$ time steps and performing a total of $m$ operations can be executed by $p$ processors in no more than $t + \lceil(m – t) / p\rceil$ time steps in PRAM.
In particular, we have $m=n^3+ n^2(n-1)$ operations and $t=1+\lceil \log_2n\rceil$ time steps for matrix multiplication. If we have $p=\lceil n^3 / \log_2 n \rceil$ processors, the upper limit of parallel steps given by Brent's principle,  $t + \lceil(m – t) / p\rceil$ is $3\lceil\log_2 n\rceil-1$ or $3\lceil\log_2 n\rceil$  or $3\lceil\log_2 n\rceil+1$.


Construct context-free grammars that generate for the languages L(G) = {01(110)^n 10 (11)^n : n >= 0}

Hint, the grammar $S \to a S c \mid b$ generates the language $\{a^n b c^n : n \geq 0\}$. Can you you adapt this? Do you understand why it generates that language?


Rice–Shapiro theorem in computation theory

Rice-Shapiro greatly helps in proving that a set is not RE, for some sets of the form $R_\Gamma$.

E.g. take $A = \{ n \ |\ {\sf dom}(\phi_n) \mbox{ finite} \}$. We have $A=R_\Gamma$ with $\Gamma = \{ \phi_n | {\sf dom}(\phi_n) \mbox{ finite} \}$. If $A$ were RE, since e.g. the always undefined function belongs to $\Gamma$, then by Rice-Shapiro any recursive extension of that would be long to $\Gamma$ as well -- but this is false, since e.g. the identity function  $\notin\Gamma$. Hence $A$ is not RE.

The above one is a typical use, where you reach a contradiction by extending a function inside $\Gamma$ to one recursive function outside.

We can also use it in the other direction: we reach a contradiction if we can take any function inside $\Gamma$ whose finite restrictions are all outside $\Gamma$. For instance, take $B = \{n \ |\ \forall k\in\mathbb{N}.\ \phi_n(2k)=5 \}$. Clearly $B=R_\Gamma$ with $\Gamma = \{\phi_n \ |\ \forall k\in\mathbb{N}.\ \phi_n(2k)=5 \}$. The function $f(x)=5$ is inside $\Gamma$, but any finite restriction of $f$ can not evaluate to $5$ on all even numbers, hence it must be found outside $\Gamma$. If $B$ were RE, by Rice-Shapiro one such restriction should instead be found inside $\Gamma$. We conclude that $B$ can not be RE.

I find Rice-Shapiro easier to use if I think about it as two separate results:

One is a monotonicity result, telling us that if $f \in \Gamma$ and $f \subseteq g$ with $g$ partial recursive, then $g \in \Gamma$. I.e. recursive extensions of functions in $\Gamma$ must belong to $\Gamma$ -- otherwise, $R_\Gamma$ is not RE.

The other is a compactness result. For any function in $\Gamma$, there must be a finite restriction of it inside $\Gamma$ -- otherwise, $R_\Gamma$ is not RE.

Many, many common examples of non-RE sets violate one of these two conditions, making it simple to prove they are not RE. For instance, consider $C = \{n\ |\ \phi_n(3)\neq 4 \land \phi_n(5)=2 \}$, where the notation $\phi_n(3)\neq 4$ is meant to be true when $\phi_n(3)$ is undefined. This immediately violates monotonicity, since I can always extend a (recursive) function which is undefined on $3$ so that it evaluates to $4$ on that point (and still get a recursive function). So $C$ is not RE.


For the sake of simplicity, I will assume that: 1) empty sets are allowed, 2) we count a set as a subset of itself (i.e.: both the big set and small set can represent the same set). If these assumptions don't hold, the math gets a little messier but the basic principles still hold.

First, we observe that there are $2^i{n\choose i}$ pairs of subsets where the bigger subset has cardinality $i$ and that there are a total of $\sum_i 2^i{n\choose i} = 3^n$ such pairs.

We proceed as follows:

1) We choose $k$ (between $0$ and $n$), the size of the bigger subset. This will not be a uniformly random choice but our initial observation lets us know the correct probabilities, i.e.: $P(k = i) = 2^i{n\choose i} / 3^n$.

2) We choose uniformly among the ${n \choose k}$ subsets of cardinality $k$ to be our bigger subset. Reservoir sampling should do the trick.

3) We choose uniformly among the $2^k$ subsets of the bigger subset to be the smaller subset. Simply choosing a random number from $0$ to $2^k-1$ and using the natural correspondence between sets and binary representations of integers should suffice.

EDITED TO ADD:

I just realized an even slicker way to do this but it depends heavily on the first two assumptions I stated. Unlike my originally provided method, I don't see an obvious way to adapt it if either of those assumptions fails to hold.

Recall that we deduced that the total number of eligible subset pairs was $3^n$. We can identify a bijection between each subset pair and $\{0,1,2\}^n$, i.e.: vectors of length $n$ with entries in $\{0,1,2\}$. Let $v$ be such a vector. If the $i^{th}$ entry of $v$ is $2$, then put $i$ in both sets; if it's $1$, then put it only in the bigger set; if it's $0$, ignore it.

So, the problem reduces to generating a number between $0$ and $3^n-1$ and examining its ternary representation.


Is the power of a natural number logspace-computable?

Yes, iterated multiplication is even in uniform TC0:

Hesse, William; Allender, Eric; Mix Barrington, David (2002). "Uniform constant-depth threshold circuits for division and iterated multiplication". Journal of Computer and System Sciences. 65: 695–716. doi:10.1016/S0022-0000(02)00025-9.

Explanation: We have TC0 ⊆ NC1 ⊆ L, where TC0 denotes the class of Boolean circuits with constant depth and polynomial size, where unbounded fan-in threshold gates are allowed, NC1 denotes the class of Boolean circuits with logarithmic depth and polynomial size, and L denotes logspace.


Can we compute the sum of a range of entries in $O(1)$ time?

Yes, calculation of range sum is possible in O(1) time.
Suppose the data is given in an array. You need to preprocess the array to find the prefix sums. For this you need another array. To find range sum S(i,j] you need to compute P[j]-P[i]. Where P[j] and P[i] are entries of prefix sum array. For example, the given array is:
4 5 -2 5 -77 45.
Corresponding prefix sum array is:
4 9 7 12 -65 -20.
So, S(2, 4] = -65 - 7 = -72 (Sum from 2 to 4, 2 excluded and zero based indexing)

Note: We preprocess the given data to build the prefix sum array which takes O(n) time where n is the number of entries. After that, each query of the form S(i,j] takes O(1) time.


How to split the array into two subarrays with the smallest sum difference?

This problem is the optimization version of the partition problem, and if it was solvable efficiently, that would mean that $P = NP$. That means it is unlikely that there is a polynomial time solution to split an array in two.
There are exact solution algorithms described on the wikipedia page, and some of them are in pseudo-polynomial time.


Show that the following language is undecidable

You haven't defined HALT, so let me assume that it consists of all Turing machines that halt on the empty input. If $M$ halts in time $f(n)$, then in particular it halts on the empty input, and so if $M$ belongs to your language then it also belongs to halt. But the converse doesn't hold, and $L \subseteq HALT$ doesn't imply anything about $L$ (for example, $\emptyset \subseteq HALT$, yet $\emptyset$ is decidable).

In other words, your proof doesn't work. It doesn't prove anything.

Your goal is to show that using an oracle to $L$ (your language), you can decide the halting problem; hence if $L$ were decidable, then so would HALT be, contrary to the known fact that HALT isn't decidable.

In fact, we can show that $L$ is coRE-hard. This means that there is a computable reduction that takes a description of a Turing machine $M$ and outputs a description of another Turing machine $M'$ such that:

If $M$ halts on the empty input then $M'$ doesn't run in time $f(n) := 100n^3 + 300$.
If $M$ doesn't halt on the empty input then $M'$ does run in time $f(n)$.

The construction goes as follows. On input of length $n$, $M'$ simulates $M$ on the empty input for $g(n)$ steps, where $g(n)$ is a function to be determined, which tends to infinity. If $M$ halts within $g(n)$ steps, $M'$ goes into an infinite loop, and otherwise $M'$ halts. We choose $g(n)$ so that the simulation runs in time $f(n)$. (Depending on the exact Turing machine model, we might be able to take $g(n) = n$ or so.)

If $M$ doesn't halt then, by construction, $M'$ also halts within $f(n)$ steps. If $M$ does halt, then for large enough $n$, $M'$ will never halt, and in particular won't halt within $f(n)$ steps.

The language $L$ is also coRE: we can enumerate machines not in $L$ by running all machines on all inputs, and outputting the description of a machine once it doesn't stop within $f(n)$ steps on some input of length $n$. This shows that $L$ is coRE-complete.


How to do amortized analysis for an expanding array?

This looks like a homework problem, so I will try to highlight the skeleton of the proof.

The cost of inserting and taking an element out of an array is 1
The cost of resizing an array is equal to the number of elements moved to the new/bigger array.
As a simple case, consider you increase the size of array by 1. Calculate the total cost of resizing?

Repeat the above analysis by doubling the size of array and check which one is better i.e. doubling the size OR increasing by 1? Calculate the amortized cost for both cases? Then you should be good to answer your own question...


The worst case for the number of function calls is (as you already observed)

$$\sum_{i=1}^{2N}\sum_{j=1}^{i/2} 2 =\sum_{i=1}^{2N} i = \frac{2N(2N+1)}{2}=2N^2+N,$$

by Gauß' summation formula.


Implementing a symbol table with a hash table and a stack

A stack of hashtables would be a perfectly fine representation.

A hashtable of stacks wouldn't be a good choice, but a stack of hashtables would work.

When you leave a scope (e.g., the } symbol), you need to pop off all of the symbol names defined in that scope.  That's easy with a stack of hashtables, but a bit more annoying with a hashtable of stacks.

A natural way to represent a stack is as a linked list, so this might turn out to be equivalent to the solution you've already been presented.


Why is $\forall x \in \mathbb{N}\ \Phi(x,x)$ unary but $\Phi$ is binary?

A lot of confusion arises because the sloppy notation and imprecise terminology involving free and bound variables. Let me try to clear some of it up.
The title of your question wrongly claims that $\forall x \in \mathbb{N} \,.\, \Phi(x,x)$ is a function, which it is not. It is a truth value. Let us see why this is the case.
Suppose someone defined $f$ by writing down
$$f(x,y) = x^2 + 3 y,$$
where $x$ and $y$ range over $\mathbb{N}$. First of all, it would be more precise to define $f$ like this:
$$f = ((x, y) \mapsto x^2 + 3 y).$$
The right-hand side is read as "the function which maps $(x,y)$ to $x^2 + 3 y$". The variables $x$ and $y$ are bound, i.e., we get the same function if we rename them, for example $(u, v) \mapsto u^2 + 3 v$ is equal to $f$.
The function $f$ is binary because it takes two arguments.
With $f$ defined as above:

The expression $f(x, y)$ is not a function! It is a number. Indeed, you would have no trouble claiming that $f(x,y) \in \mathbb{N}$, would you? However, this number is parameterized by two free variables $x$ and $y$. Thus, which number it is depends on $x$ and $y$.

The previous remark maybe becomes clearer if we contemplate the fact that $f(3, 4)$ is not a function but a number, and so is $f(u,u)$ where $u \in \mathbb{N}$ is a free variable.

We can fix just one of the arguments to get a unary function, for example $x \mapsto f(x, 7)$ is unary because it is a map $\mathbb{N} \to \mathbb{N}$.

The expression $f(x, 7)$ is not a function! It is a number, parameterized by the free variable $x$.

Next, consider the definition
$$g = (x \mapsto x^2 + 3 y).$$
The function $g$ is unary because it takes one argument. However, $g$ depends on the free variable $y$. (Some people may call this $y$ a "constant", or call $x$ an "argument" and $y$ a "parameter", but let us not do that. We will stick strictly to the terminology "$x$ is a bound variable" and "$y$ is a free variable".) We may rename the bound variable but not the free one:

$(u \mapsto u^2 + 3 y)$ is equal to $g$
$(u \mapsto u^2 + 3 v)$ is not equal to $g$ because $y$ and $v$ are different free variables
$(y \mapsto y^2 + 3 y)$ is not equal to $g$ because the free variable $y$ does not appear in it.

Some people might define $g$ above like this:
$$g_y = (x \mapsto x^2 + 3 y).$$
They want to indicate that $y$ is a free variable in the definition of $g$. In our notation, this would correspond to
$$g = (y \mapsto (x \mapsto x^2 + 3 y))$$
so that now $g$ is a unary function without free variables. When we apply $g$ to $y$ by writing $g_y$, we again get a unary function, this time wit one free variable $y$. By the way, writing $g_y$ instead of $g(y)$ is just cosmetics.
Consider
$$\Phi = ((u, v) \mapsto u < 7 \lor (v + u^2 > 6).$$
Then $\Phi$ is a binary function because it maps from $\mathbb{N} \times \mathbb{N}$ to $\{\bot, \top\}$. It should be clear that:

$\Phi(x,x)$ is not a function. It is a truth value parametrized by the free variable $x$.

$x \mapsto \Phi(x,x)$ is a unary function mapping from $\mathbb{N}$ to truth values $\{\bot, \top\}$.

$\forall x \in \mathbb{N} \,.\, \Phi(x,x)$ is not a function. It is a truth value. Indeed, we can plug in $\Phi$ and get $\forall x \in \mathbb{N} \,.\, x < 7 \lor (x + x^2 > 6)$, which is false (a truth value, not a function).

What I think you really wanted to ask was this: why is $\Phi$ binary but $x \mapsto \Phi(x,x)$ is unary? Is the answer not obvious, once we use correct notation that does not mess up free and bound variables?
Regarding the discussion with your teacher, there you need to correctly indicate which things are supposed to be free variables and which ones arguments of functions. You wrote:
$$\Phi^n(x_1, \ldots, x_n, y) = \Psi_y^n(x_1, \ldots, x_n).$$
I am sure you can see such thigs in textbooks, but they are a bit sloppy. To be very precise, we need information on which things in $\Psi$ are supposed to be free variables and which ones are arguments. I would guess that what is meant is that
$$\Psi_y^n : \underbrace{\mathbb{N} \times \cdots \mathbb{N}}_n \to \mathbb{N},$$
which means that
$$\Psi : \mathbb{N} \to (\mathbb{N} \to \underbrace{\mathbb{N} \times \cdots \mathbb{N}}_n \to \mathbb{N})).$$
We see that $\Psi$ is a unary function, $\Psi_n$ is a unary function, and $\Psi^y_n$ is an $n$-ary function with free variables $n$ and $y$.
If we read your definition as
$$\Phi = (n \mapsto ((x_1, \ldots, x_n, y) \mapsto \Psi_y^n(x_1, \ldots, x_n)))$$
then $\Phi$ is an unary function and $\Phi_n$ is an $(n+1)$-ary function with free variable $n$.


When is conditional Kolmogorov complexity zero?

The answer depends on whether your encoding is prefix-free or not, and in the latter case, on your universal Turing machine.

There are two variants of Kolmogorov complexity: one in which the set of programs form a prefix-free code, and one in which there is no such requirement. For the first variant, the Kolmogorov complexity is always positive. For the second variant, the universal Turing machine can do whatever it wants given an empty program (or indeed, any fixed program). You can arrange that $K(x_1|x_2) = 0$ for your choice of $x_1,x_2$, for example.


There are two kinds of minimizing in this sense,

the first is to minimize the sum of the distances.
the second is to minimize the maximum distance (finding a restaurant where the farthest friend is as near as possible).

In both cases it's not NP-Hard, since you can calculate all-pairs shortest path in $O\left(N^2\log\left( E+N \right)\right)$, sum up the distances from each restaurants to all friends and compare the sums.

Ps A special case is points laying on a line segment. The solution to the first type will be the restaurant dividing the vertices in two most-possible equal groups (has so many friends on its left as many friends on its right), the reason this works can be derived from the fact that median minimize absolute deviation.
The solution to the second problem is trivially the nearest restaurant to the middle point between the two farthest friends.

Ps2 In trees you can solve the second type using two DFSes to find the two farthest points and then choose the point in between them minimizing the distance to both of them.
The second type however, can be done in trees using a bfs traversal from leaves, counting the number of friends and distance to them in subtree of each node. Then a second bfs from the root of the tree summing all the numbers up.


Maximum number of positive literals in 2SAT

This problem is NP-hard (and in addition hard to approximate and W[1]-hard), because maximum independent set can be reduced to it. Reduction: Each variable represents a vertex and each clause represents an edge.


Size of Maximum Matching in Bipartite Graph

Given a bipartite graph $G = (U,V,E)$ and a maximum matching $M$ of $G$, via Konig's Theorem we see that $|M| = |C|$ where $C$ is a minimum vertex cover for $G$. Your statement is merely an upper bound on the size of the possible matching, not a strict equality.

The image on the wikipedia page provides a nice counterexample to your claim. We see that $|M| = 6$, while $\min(|U|,|V|) = 7$.

However, in the case of a complete bipartite graph $K_{n,m}$ your statement holds.


As mentioned in the comments, your NFA actually accepts all strings. What you have hit upon is the fact that NFAs are not resilient to complementation. Whereas given a DFA for a language, you can turn it to a DFA for the complement of the language by complementing the set of accepting states, the same doesn't hold for NFAs. In fact, "complementing" an NFA (that is, constructing an NFA for the complemented language) could result in exponential blow-up in the number of states!

As an example, consider the language of all words over $\{1,\ldots,n\}$ which do not contain all symbols. There is an NFA with $n$ states accepting the language (the NFA has multiple initial states, which might not be allowed under your definition), but any NFA for the complement must contain at least $2^n$ states. This blow-up is worst possible due to the powerset construction which converts an NFA with $n$ states to an equivalent DFA with $2^n$ states, which can be complemented without increasing the number of states.


Can any constant-time operation be applied N times in O(log(N)) time?

Not necessarily. Let us use the most common (according to some people) model of computation: the single tape Turing machine where the output of an algorithm is simply what is left on the tape. Here is a counterexample by Bergi. The operation $m$ that moves the head one step forward and writes a fixed symbol will absolutely need $n$ steps if we want to repeat $m$ $n$ times.

On the other hand, in some models of computation, any constant-time operation can be applied $N$ times in $\mathcal{O}(\log(N))$ time and in $\mathcal O(1)$ amortized time.

This section is devoted to prove the above partial positive answer.

For the sake of discussion/proof/disproof, let us make OP's question precise.

Let $f$ be a function that maps a set $S$ to $S$ itself. Define function $r(f,n)$ as applying $f$ repeatedly $n$ times. That is, for any $n\in\Bbb N$, $r(f,n): S\to S$ is defined by the following.
  $$ r(f,n) := \begin{cases}
     f               & \text{ if }n = 1,\\
     f\circ r(f,n-1) &\text{ otherwise.}\\
   \end{cases}$$

Claim: Suppose we can compute $f$ in constant time and $f(S)$ contains finitely many values, then we can compute $r(f,n)$ in $\mathcal{O}(\log n)$ time and in $\mathcal O(1) amortized time.

Proof of the claim: (The simple observation is that we are dealing with states whose cardinality is smaller than a constant.)

Without affecting the correctness of this proof, we will assume that $|S|$ is smaller than some constant; Otherwise, we can replace $S$ by $f(S)$ and $f$ by itself restriction to $f(S)$.

Let $SS$ be the set of functions from $S$ to $S$. Since $|S|$ is smaller than some constant, $|SS|$ is also smaller than some constant. So the sequence of functions $r(f,1), r(f,2), \cdots$ will be eventually periodic since each term in the sequence is determined by the previous term in the same way, that is, composition of the previous term with $f$. So, there are constants $c_1, c_2$ such that $r(f,n+c_1) = r(f,n)$ for any $n>c_2$. Now let us just compute and store the two dimensional constant array $a[i,s]$ where $a(i,s)=r(f,i)(s)$ for $1\leq i\le c_2+c_1$ and $s\in S$ in constant time. Given $N>c_2+c_1$, we will find the remainder $n_0$ of $N-c_2$ divided by $c_1$ in $\mathcal{O}(\log(N))$ time. Now we have
$$r(f,n)(s) = a(n_0+c_2,s)$$

Note that the only (possibly) non-constant operation needed for any $N$ is the one-time operation to get the remainder of $N$ divided by a constant. So once we have done some $\Theta(\log N)$ operations, the amortized time will become $\mathcal O(1)$.

We have proved the claim.

In which models of computation?

Now we want to show that there exists some models of computation such that $f$ can only have finitely many values if we can compute function $f$ in constant time or, more precisely, in less than $c$ steps for some constant $c$ independent of the input, $f(S)$ can only have finitely many values.

One such model of computation is, as mentioned by David Richerby, the multi-tape TMs where the output must be written on a designated tape which must not have any part of the input. (I would venture to say this might be the most common model that fits most people's mental image of computation, where we have input at one side of a box and output at the other side of a box. However, whether this model is even common or not is not the focus of this post.) In this mode of computation, since any constant-time operation $f$ can only move the head on that designated tape at most $c$ steps forward and at most $c$ steps backward for some constant $c$, it can produce at most $|\Sigma|^{|2c+1|}$ states, where $\Sigma$ is the set of symbols used on that designated tape. That is, $f$ can only have finitely many values.

Because of the multitude of the models of computation, we will not and cannot list all those complying models of computation. Anyway, thanks to the claim we just proved, in those models of computations, we will have the partial positive answer stated in the second paragraph of this post.

Although we have shown that in some models of computations, we can apply a given constant-time operation $N$ times in $\mathcal O(\log(N))$ time, the constant term hidden in the $\mathcal O$ notation might be impractically large. For example, for some endomorphism $f$ of a set of 1000 elements, the smallest $c_1=1516385558956728808659224171023365600$ (which is $g(1000)$ for Laudau's function g). For a cryptographic hash operation which can have about $2^{256}$ state, the smallest $c_1$ might have more than trillions of digits. Although that constant term can be reduced significantly, it remains impractically large. In that sense, that partial positive answer may not be what OP might have been hoping for at all. It does not lessen our confidence in those cryptographic hash operations in anyway.


Effective Procedures and P vs NP Problem

No. $\mathrm{P}\neq\mathrm{NP}$ means that there is no efficient (i.e., deterministic polynomial time) solution to $\mathrm{NP}$-hard problems, not that there is no effective (i.e., computable) solution. The fact that the solution is hard to find doesn't mean that it's impossible to find. Indeed, essentially the whole reason that $\mathrm{NP}$ is an interesting class of problems is that we know how to check proposed solutions to $\mathrm{NP}$ efficiently. Regardless of how hard it is to find satisfying assignments to Boolean formulas, if I give you an assignment and tell you that it satisfies the formula, you can easily check that I'm telling the truth.


Looking for a use case of a $k$-$d$ tree with a norm other than $L^2$

For example, when you want to report all the points in distance $r$ from a query point under the $L_1$ norm, which is a natural case. See https://en.wikipedia.org/wiki/Taxicab_geometry.


What's the hardness of the following problem: $\textbf{argmin}_x\{|x^2-2|\}$.

It is $O(1)$. There is a single answer: $x = \sqrt{2}$. That means that, regardless of how that answer is represented, a computer can just output the answer and it solves your problem.

In general, to consider the hardness or complexity of a problem, you need there to be at least one variable as input; in particular, you need infinitely many possible input values. Otherwise, every problem can be solved trivially by just outputting the answer.


Is linked list a preferable underlying basic DS for a collection mutable through an iterator

Well, if you're looking for easiness of operations, I would recommend a vector. Vectors support a wide array of operations, providing a large number of top-level methods, and iterators namely std::iterator, reverse iterator, and a lot more. With these top-level functions and iterators however, comes the caveat of not being able to modify these to suit your needs. Consider all of this when making the choice.


Show that A** subset of A*, where A is a regular language

Knowing that $A$ is regular is not relevant.

Hint. Just replace "made up of words of $A^*$" by "is a concatenation of words of $A^*$" in your sentence and you will have the answer.


Aggregate text data of some particular column

My assumption is that they want you to normalize the text data in those columns.  In other words, you may create a collection of the text, and the two columns would refer back to that collection.  Does that make sense?


Partition into pairs with minimum absolute difference, NP-hard?

You can reduce Numeric 3D Matching (N3DM) to your problem.

Given an instance of N3DM $X\times Y\times Z$ with the bound $b$, say $X=\{x_1,\ldots,x_m\},Y=\{y_1,\ldots,y_m\},Z=\{z_1,\ldots,z_m\}$, construct $2m$  elements $x_1+2M,\ldots,x_m+2M,M-y_1,\ldots,M-y_m$ and $m$ values $b-z_1+M,\ldots,b-z_m+M$ for your problem, where $M$ is a very large number. Now the constructed instance of your problem has a solution if and only if the instance of N3DM has a solution.


Could neural networks be considered metaheuristics?

The notion of a "metaheuristic" is not something with a precise formal definition.  Personally, a neural network isn't something I'd consider a metaheuristic; it doesn't seem quite like what we have in mind when we talk about metaheuristics.  But you can always use language however you like, as long as it is clear to others and doesn't cause confusion.


What is the fastest algorithm to check whether input table is a group?

There is a non-trivial randomized algorithm that can solve this in $O(n^2 \log (1/\delta))$ time, where $\delta>0$ is the desired error probability.  See

Verification of Identities.  Sridhar Rajagopalan and Leonard J. Schulman.  SIAM Journal on Computing, 29(4), pp.1155-1163.


No algorithm really has an $O(1/n)$ running time, but that notation might be used informally for an algorithm who's running time is really $O(m/n)$ where $m$ is large and not expected to vary. Here's an example of such an algorithm:

Given an unordered set (e.g. a hash table) containing $n$ values from the integer range $0 \le x \lt m $ (for some $ m \in \Bbb{N}^* $). (Note that $ n \le m $, as a set can't contain any duplicate values.)

We want to find the minimum value in the set as efficiently as possible.

If $n$ is much smaller than $m$, then a linear scan through the values in the set is the most efficient solution ($O(n)$).

But if $n$ is greater than $\sqrt m$, it will often be more efficient to iterate over the potential values starting with $0$ and going up, testing each one to see if it's in the set. We can of course stop as soon as we find one, since it will be the smallest one.

The expected number of tests (assuming the data is randomly distributed over the range) is $m/n$. If we consider $m$ to be a constant (as in real-world applications it will often be determined by something we can't easily change like the size of our integer data type), this seems like it would be $O(1/n)$ (with a large constant factor of $m$). And that does give an accurate description of how the performance of the algorithm changes as $n$ goes from $ \sqrt m $ towards $m$ while $m$ remains the same.

But the notation is not strictly correct. Asymptotic notation is intended to describe behavior as its variable terms go towards infinity. If an $O(1 / n)$ algorithm could run for $n$ approaching infinity, its running time would tend towards zero, but the $1 / n$ term would be dominated by constant terms (and so $O(1)$ would be a better description of its performance). For an algorithm that only makes sense on a bounded $n$, it's not correct to use asymptotic notation. For a strict asymptotic analysis, you need to consider $m$ a variable too so that both $m$ and $n$ can increase towards infinity.

I suspect that if you ever see $O(1/n)$, it's being used as an informal shorthand for $O(m/n)$.


Apparently, no relationship is known between $MA$ and $P^{NP}$. Even $BPP$ ($\subseteq MA$) vs $P^{NP}$ problem is still open. It is conjectured though that $MA = NP$ (Under standard hardness assumptions). So, it is likely that $MA \subseteq P^{NP}$.


Reachability queries on a tree in $O(1)$ time with $O(n+m)$ time preprocessing

Yes, I think you can do this in $O(1)$ time.  I outline a method below.  There's probably a simpler way to do it, but the following should suffice.

Preprocessing. I'll assume we can view your tree as a rooted tree, with some root.  In pre-processing, annotate each internal node $w$ with one example of a leaf that is a descendant of $w$.  This can be done in $O(n+m)$ pre-processing time, using a very simple top-down traversal (DFS).

Also, define $p^*(\cdot)$ recursively as follows: if $w$ has any siblings, then $p^*(w)=w$; otherwise, $p^*(w)=p^*(v)$ where $v$ is the parent of $w$; and $p^*(r)=r$, where $r$ is the root of $T$.  In English, $p^*(w)$ is defined to be the node obtained by starting at $w$ and continuing upwards until we reach a node that has two or more children (or the root).  In pre-processing, we'll compute the value of $p^*(w)$ for each node $w$ and store it associated with $w$.  This too can be computed in $O(n+m)$ time.

Answering a query. Now, here's how to answer the query return any leaf that is reachable from $v$ with a path including $(u,v)$, and no other edges incident to $v$:

Case 1: Suppose $u$ is a child of $v$.  Then, answering your query amounts to returning any leaf that is a descendant of $u$.  This can be done in $O(1)$ time using the annotation on $u$.
Case 2: Suppose $u$ is the parent of $v$, and $u$ has at least one other child.  Then, look at any other child of $u$, call it $w$.  Then, answering your query amounts to returning any leaf that is a descendant of $w$.  This can be done in $O(1)$ time using the annotation on $w$.
Case 3: Suppose $u$ is the parent of $v$, and $u$ has no other children.  Then let $u'=p^*(u)$ and let $w$ be any other child of $u'$ (not an ancestor of $v$).  Then, answering your query amounts to returning any leaf that is a descendant of $w$.  This can be done in $O(1)$ time using the annotation on $w$.

In all three cases, the answer to the query can be computed in $O(1)$ time.


Applications affected by memory performance

Memcache and other memory heavy software
software with large working sets
Diskless Servers
Software backed by Ramdisk
Any software that needs fast access to data (other than Databases)


If $f(n)=O(g(n))$ can I say there exists a $n_0$ for a specific $c$?

Let's take as an example $f(n) = g(n) = n$ and $c = 1/2$. Does there exist an $n_0$ such that $f(n) \leq cg(n)$ for all $n \geq n_0$?
In your case, you know more: $\log n = o(n)$. This means that
$$
\lim_{n\to\infty} \frac{\log n}{n} = 0,
$$
which implies that for every $c$ there exists $n_0$ such that $\frac{\log n}{n} \leq c$ for all $n \geq n_0$.


No. The grammar is defined like this:

G = (V,SIGMA, R, S) where V is your set of variables (non-terminals) and SIGMA is your alphabet (terminals). All the symbols you are allowed to use in the substitution of a rule are the union of V and SIGMA. If you simply cannot use a symbol out of that set, since it does not exists in the context of your grammar.


No.  As you said, the NFA can have $m=O(n)$ states, and the DFA can have as many as $2^m$ states, so the DFA can have as many $2^{O(n)}$ states.  Consequently, converting a regexp to a NFA and then complementing the NFA can yield an automaton with $2^{O(n)}$ states.  $2^{O(n)}$ is larger than $O(2^n)$: notice the difference between $2^{cn}$ vs $c \cdot 2^n$.


Is the shadow ray in a Whitted ray tracer occluded by transparent objects?

You should first refer to Rendering Equation. It is the general equation to describe the physically transmitting of light in the view of computer science.

Whitted model is just an approximation of the surface integration of the Rendering Equation. It only calculates three light rays(shadow ray, reflected ray, and refracted ray). In a more sophisticated ray tracer, you should use Monte-Carlo ray tracing, where at every intersection point on the object, you will use thousands of rays sampling according to BRDF. Such backward algorithms actually work not good at caustic scene, which is the scene you say. You can use Photon Mapping plus Monte-Carlo Ray Tracing to get a better visualization.

If you just want to use Whitted model, you can multiply the lighting of shadow ray by a factor defined by the occluded transparent object.


Does $20n$ belong to $O(n^{1-\epsilon})$ for some $\epsilon > 0$?

Big O notation hides constant factors. In particular, for every constant $C > 0$,
$$
f \in O(g) \Longleftrightarrow Cf \in O(g).
$$
In particular, for any $\epsilon > 0$,
$$
20n \in O(n^{1-\epsilon}) \Longleftrightarrow n \in O(n^{1-\epsilon}).
$$
This follows directly from the definition of big O. Indeed, suppose that $f \in O(g)$. Then there exist $N,A>0$ such that $f(n) \leq Ag(n)$ for all $n \geq N$. This implies that $Cf(n) \leq ACg(n)$ for all $n \geq N$, and so $Cf = O(g)$. Similarly, if $Cf = O(g)$ then the same argument shows that $f = C^{-1} C f = O(g)$.


Where did Don Knuth say that suffix trees were the "Algorithm of the Year 1973?"

The source of the quote seems to be From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction by Giegerich and Kurtz.

On page 347, at the start of Section 6 (An Explanation of Weiner's Algorithm), they write

  In this section we go back to the roots
  and take a look at the “Algorithm of the Year 1973” (D. E. Knuth according to [19]).

Reference [19] is an unpublished manuscript:

  [19] V.R. Pratt. Improvements and Applications of the Weiner Repetition Finder. Unpublished manuscript,
  Cambridge, MA, 1973.

Apparently these are lecture notes (this is how they are referred to in the monograph Image and Text Compression by Storer).


Computers have a "real-time clock" -- a special hardware device (e.g., containing a quartz crystal) on the motherboard that maintains the time.  It is always powered, even when you shut your computer off.  Also, the motherboard has a small battery that is used to power the clock device even when you disconnect your computer from power.  The battery doesn't last forever, but it will last at least a few weeks.  This helps the computer keep track of the time even when your computer is shut off.  The real-time clock doesn't need much power, so it's not wasting energy. If you take out the clock battery in addition to removing the main battery and disconnecting the power cable then the computer will lose track of time and will ask you to enter the time and date when you restart the computer.

To learn more, see Real-time clock and CMOS battery and Why does my motherboard have a battery.

Also, on many computers, when you connect your computer to an Internet connection, the OS will go find a time server on the network and query the time server for the current time.  The OS can use this to very accurately set your computer's local clock.  This uses the Network Time Protocol, also called NTP.


Why can't configuration counting decide undecideable problems?

Configuration counting can certainly detect infinite loops. But only if space is bounded. A TM could write non-repeating nonsense on the tape and never get caught.


Consistency and completeness imply soundness?

In the Scott Aaronson blog post you linked, (syntactic) consistency means that there is no sentence $P$  such that both $P$ and its negation can be deduced from the axioms of the theory.  (Syntactic) completeness means that either $P$ or $\neg P$ are deducible from the axioms.  And soundness means that if $P$ is deducible from the axioms then it is valid under all possible models/interpretations of the axioms.

Consistency + completeness does not imply soundness because you could have a set of axioms and a theorem $P$ where $P$ is deducible from the axioms, $\neg P$ is not deducible from the axioms but there is some model of the axioms under which $P$ is false and $\neg P$ is true.

Aaronson gives an example in his post:

  If I believe that there’s a giant purple boogeyman on the moon, then presumably my
  belief is unsound, but it might be perfectly consistent with my various other beliefs
  about boogeymen.

"There's a giant purple boogeyman on the moon" is (perhaps) syntactically consistent with your axioms because you do not believe that "there isn't a giant purple boogeyman on the moon."  Your axioms may be syntactically complete because they allow you to deduce at least one of the sentences "there's a giant purple boogeyman on the moon" or "there isn't a giant purple boogeyman on the moon."  But in fact it is not true that "there's a giant purple boogeyman on the moon," so your deduction is unsound even though your axioms and deductive system are both consistent and complete.

The hardest concept in the above is probably soundness.  Soundness relates the syntactic structure of your sentences and deduction rules to the interpretations (or models or semantics) of those sentences.  A model of a language is a set, along with some relations and functions on the members of that set.  For example, Gödel's language was the Peano axioms and the underlying model of the Peano axioms is the set of integers with (at least) an equality relation and a successor function.  The Peano axioms are (I think) sound: if you can prove something with the Peano axioms then it is true of the natural numbers.  But Gödel proved that the Peano axioms are not complete: there are sentences in the language of the Peano axioms that are in fact true of the natural numbers, but which are not derivable from the Peano axioms.


Do you get DFS if you change the queue to a stack in a BFS implementation?

No, this is not the same as a DFS.

Consider the graph

If you push the nodes in right to left order, the algorithm gives you a traversal:

$A, B , E, C , D$

while a DFS would expect it to be

$A,B,E,D,C$

The problem occurs because you mark it as seen at the time of pushing, rather than at the time of visiting. As pointed out in the comments, if you mark at the time of visiting, your space requirements might go up to $\Theta(V+E)$ rather than $\mathcal{O}(V)$.

I agree, the problem is not trivial.


Is computing a square root of a number and having more than 2 roots a reliable way to decide primality?

There are composite numbers where this primality test fails with probability 1: it always outputs "prime", even though the number is actually composite.  These numbers are basically the Carmichael numbers, with a slight twist.  Therefore, this is unfortunately not a correct primality testing algorithm.

Recall that $N$ is a Carmichael number if $x^{N-1}\equiv 1 \pmod N$ holds for all $x \in \mathbb{Z}_N^*$.  All Carmichael numbers are odd.  I'll define a super-Carmichael number to be a number $N$ such that $x^{(N-1)/2}\equiv 1 \pmod N$ holds for all $x \in \mathbb{Z}_N^*$.

Now consider what happens in your algorithm if $N$ is a super-Carmichael number.  We pick $x$ randomly, then compute

$$y=a^{(N+1)/4}=(x^2)^{(N+1)/4}=x^{(N+1)/2} = x^{(N-1)/2} \cdot x = x \pmod N,$$

since $x^{(N-1)/2} = 1 \pmod N$.  It follows that we also have $y^2 = x^2 \pmod N$.  Thus, no matter what value of $x$ you choose, you'll always find that $y^2 \equiv a \pmod N$ is true and that $y \equiv \pm x \pmod N$ (when $N$ is a super-Carmichael number).  So, your algorithm will always give an incorrect answer, when you run it on a super-Carmichael number.

For instance, $1729 = 7 \times 13 \times 19$ is a super-Carmichael number: we have $x^{36} \equiv 1 \pmod{1729}$ for all $x \in \mathbb{Z}_{1729}^*$, and $36$ divides $(1729-1)/2 = 864$.  Therefore, your algorithm gives an incorrect answer on 1729.  I suspect there are infinitely many super-Carmichael numbers.  I also suspect that your algorithm might actually give an incorrect answer on all Carmichael numbers (not just the super-Carmichael ones), but I haven't tried to check the details to see if that's actually true.


Can we say that Zookeeper updates are ACD (ACID without the I)?

Atomicity is not about being able to implement "atomic locks" or not.  Consistency as used in the CAP theorem (i.e. the C in CAP) is not the same thing as Consistency in ACID, and Consistency in CAP is way stronger than eventual consistency.  ZooKeeper is an ACID system and a CP system, albeit the ACID "C" is not doing much work here.

Atomicity means a "transaction" either completes entirely or not at all.  It's mostly orthogonal to concurrency.  If you had a system that was Atomic but not Isolated, transactions could see the intermediate results of other in-progress transactions regardless of whether those other transactions got rolled back or not. Meanwhile, a non-Atomic but Isolated system would not see any intermediate results of in-progress transactions, but failed transactions need not rollback their work, so the detritus of failed transactions would be visible to all. Atomicity alone would not allow you to implement atomic locks; Isolation is really the more important property for that though technically Atomicity is also required.

Consistency in ACID means maintaining integrity constraints.  ZooKeeper provides few such constraints, so this is accomplished more or less trivially.  Consistency in CAP refers to linearizability which is different than but related to Isolation.  Isolation refers to serializability.  Traditionally, (one-copy) serializability was effectively strict one-copy serializability which is the combination of serializability and linearizability, but serializability and linearizability are actually distinct (though similar looking) notions, neither implying the other.  ZooKeeper provides strict one-copy serializability (if you sync before every read), and thus it is both Isolated and Consistent in the CAP sense.


Find the smallest group of numbers with sum bigger then $X$

Assuming you are looking for $S' \subset S$ with minimal $\sum_{x \in S'} x > X$ like Steven suggested, then you should be able to reduce the problem to an instance of knapsack with weights $w_i$ and costs $c_i$ with $w_i = c_i = s_i$ for every $s_i \in S$ where the weight of the knapsack is bounded by $X$.
If the solution $K := \sum_{x \in S'} x$ is not greater than $X$, you need to repeat the process by setting $X := X + \varepsilon$ where $\varepsilon$ is the minimal distance between any two subset sums of $S$ and running knapsack again until it yields a solution $K > X$.
Edit: Turns out that finding $\varepsilon$ isn't an easy problem. I first assumed $\varepsilon$ is the minimum between any two numbers in $S$, which can be found by sorting the list and finding the minimum between two adjacent elements. This would yield a good approximation in most cases, but it might not be the optimal solution. If your problem statement uses $\geq$ instead of $>$, transforming the problem into knapsack will yield an optimal solution, no repetitions required.


looks entirely identity function to me, which can definitely be inhabited by a closed term

A proof of $\forall C : Prop, C$ is a function from an arbitrary proposition to its proof. Since a proposition isn't a proof, an identity function is not a function from propositions to proofs.

The identity function (or rather, a function returning the identity function on proofs of $C$) corresponds instead to the proof of $\forall C : Prop, C \to C$. That's even the example on the beginning of page 3!


To some extent it's a convenience. Not all languages have the hierachy you speak of. For instance Ocaml has no such hierarchy and you need to explicitly cast integers to floats. (This is the price you pay for having type inference with principal types in Ocaml.)

But there are other reasons as well. Numeric types are there because we want to do math with computers. In mathematics there are many kinds of numbers, and they are naturally organized according to what structure they carry: the integers form a ring, the rationals form a field, the reals form a complete field, and the complex numbers a complete algebraically closed field. So the mathematical hierarchy gets reflected in the organization of numeric types.

In Haskell there are a number of numeric type classes (Num, Float, Rational, ...) which give the programmer flexibility and modularity. In Haskell it is very easy to switch from one kind of Num to another – as opposed to other software systems where it takes years to switch the numeric data types (consider how big a project it was from 32-bit to 64-bit Windows).


How does the computational complexity of problems depend on the model specifics of a register machine?

The basic definitions of computational complexity are normally phrased in terms of plain Turing Machines, so one has to be careful about transferring results to different models. Naturally, if you can perform look-ups faster, any program that requires that functionality will also be faster (at least for that part).

However if the other model is not to extreme, then the gap in the precise running times falls below our normal threshold of caring. That is, most models of fairly general interest are polynomially equivalent to Turing Machines, so even though a register machine is in some sense faster than a Turing Machine, it's not so much faster that it breaks the definitions - it only speeds things up by a polynomial factor (i.e. an $O(n^{a})$ algorithm will only go down to a $O(n^{b})$ algorithm with $b \leq a$).

You can of course define models that are significantly faster than a Turing Machine (for a trivial example, a Turing Machine that can solve $\mathsf{Clique}$ in a single step), at this point, you can't feasibly replace "Turing Machine" in the definition of $\mathsf{P}$ or $\mathsf{NP}$ with the new model without changing things significantly (but models like this do have other uses).


To check whether the problem of a particular string being a member of CFG G is decidable or not, why can't we use a PDA?

Consider a pushdown automaton which has an $\epsilon$-transition which adds $A$ to the stack, and another $\epsilon$-transition that removes $A$ from the stack. Clearly, this PDA has accepting computations of unbounded length. There is no a priori bound on the shortest computation needed to accept a string of a certain length (though perhaps you can come up with such a bound if you're smart enough!).

Why is this a problem? Consider a deterministic Turing machine which runs all possible computations of the PDA, accepting if it finds an accepting computation, and rejecting otherwise. If there is no computable upper bound on the length of a computation, then the Turing machine will have to try infinitely many computations in the rejecting case, and so won't halt on rejecting inputs.

The same problem occurs with context-free grammars having unit productions (consider for example a grammar with the productions $A\to B$ and $B\to A$). After removing unit productions and $\epsilon$-productions, the problem goes away, and you can use dynamic programming to decide the language of the context-free grammar. This is (essentially) the CYK algorithm.


Double-Horn-SAT is polynomial-time solvable.

Given a set of Horn-clauses $X = \{C_1,C_2,...,C_n\}$ and a solution $x_1=b_1,x_2=b_2,...,x_n=b_n$, $b_i \in \{true,false\}$ we can observe that a second solution must differ in at least one variable $x_i$.
So we can run the Horn-SAT algorithm $n$ times on the augmented set $X_i' = X \cup \{ \lnot x_i \}$ if in the first solution $x_i = true$ or on the augmented set $X_i' = X \cup \{ x_i \}$ if in the first solution $x_i = false$. If we find  a solution for one of the $X_i'$ then it is a valid solution for the original set $X$, too and by construction it differs from the first one; otherwise the original set doesn't have a second solution, as can be easily proved by contradiction.

See also the question "Complexity of finding a second solution given a correct solution to an NP-complete problem" on cstheory and Laurent Juban, Dichotomy theorem for the generalized unique satisfiability problem (1999)


What is the number of degrees of freedom of my problem in this Simulated Annealing context?

The parameter $N$ is the length of the vector you're running simulated annealing on. In your case, $N = n$. The values $12,100$ are completely heuristic, and were probably chosen experimentally.


Walk around a coordinate in circular order to a distance of N

You can do this in a stateless manner.

Here is python code that generates the infinite walk:

def circular():
    yield (0,0)
    x,y = -1,0
    while True:
        yield (x,y)
        if x < 0 and 0 <= y < -x:
            y += 1
        elif y > 0 and x < y:
            x += 1
        elif x > 0 and y > -x:
            y -= 1
        elif y < 0 and x > y:
            x -= 1
        elif x < 0 and y < -1:
            y += 1
        elif x < 0 and y == -1:
            x -= 1
            y += 1


You can multiply variables in ILP with https://blog.adamfurmanek.pl/2015/08/29/ilp-part-2/ and https://blog.adamfurmanek.pl/2015/09/26/ilp-part-6/ and https://blog.adamfurmanek.pl/2015/10/03/ilp-part-7/
You don't need multiplication, though. Your objective function is effectively:
$
\min(500, x_1) \cdot 110 + \max(x_1 - 500, 0) \cdot 115 + \min(300, x_2) \cdot 120 + \max(x_2 - 300, 0) \cdot 84
$
You can represent max/min functions as comparison + absolute value, as explained in https://blog.adamfurmanek.pl/2015/09/19/ilp-part-5/


How to read this inductive language definition?

The recursive definition implies that a word $w$ is in $L$ if there is a sequence $w_0,\ldots,w_n=w$ such that $w_0$ is the empty word and for each $i=1,\ldots,n$, either $w_i = bw_{i-1}$ or $w_i = w_{i-1}aa$. This, in turn, implies that $L = b^*(aa)^*$.


How to solve this asymptotic complexity problem?

$f_3(n)$ has the highest asymptotic time since it is an exponential function. Although it is $(1+\epsilon)^n$ and might seem very tiny in terms of growth, there exists a real number $m$ where it grows faster than the rest.

Then, we have $f_4(n)$ as quadratic function.

$f_2(n)$ is unfortunately linear. Which means, it does not grow as fast as $f_4(n)$ and $f_2(n)$. Actually, while considering asymptotic growing, you should ignore the constants in the function. Thus, we can say that $O(1000000n) = O(n)$.

The tricky part is $f_1(n)$. It would grow faster than $f_2(n)$ if it was $O(n \log n)$. However, it is $O(n^{1-\epsilon} \log n)$, which makes it grow slower than a linear function.


Is there any connection between imperative programming and the Von Neumann architecture?

von Neumann architecture is memory for data and instructions and a CPU that fetches and executes instructions one after the other. That is intrinsecally imperative. Compare with functional programming (define functions that call among themselves) or logic programming (search for a solution  to a set of logic statements). Other paradigms like OOP are more or less orthogonal to the above.


No common terms between polynomials: an efficient check?

Here is an approach that might occasionally be a bit better in practice, but is still exponential-time in the worst case, so it is not a satisfying answer to your question.  Suppose we want to determine whether the polynomials $f(x,y,\dots),g(x,y,\dots)$ have a common term.  First write

$$\begin{align*}
f(x,y,\dots) &= f_0(y,\dots) + x f_1(y,\dots)\\
g(x,y,\dots) &= g_0(y,\dots) + x g_1(y,\dots).
\end{align*}$$

Then recursively check whether $f_0,g_0$ have a common term; and check whether $f_1,g_1$ have a common term.

To express $f$ in that format, note that

$$f_0(y,\dots) = f(0,y,\dots)$$

so it suffices to plug in $x=0$ into the expression for $f$ to get an expression for $f_0$.  Try to simplify that expression as much as possible using standard rules for simplifying polynomials.  Then, you can write

$$f_1(y,\dots) = (f(x,y,\dots) - f_0(y,\dots))/x.$$

Simplify that expression as much as possible.

If no simplification is done, the running time is exponential in $n$, the number of variables.  We obtain a recurrence of the form $T(n) = 2 T(n-1) + O(1)$, so the worst-case running time is exponential.  The room for hope is that if simplification is done at each stage, it's possible that for some inputs this might be faster than that.  In general it will still be exponential-time in the worst case, though, so I don't know whether this will actually be any better in practice.


What are the essential differences and similarities among "data", "Information" and "knowledge" in the context of Computer Science?

You're description is pretty accurate. There is no formal definition or precise meaning coming from a high level. There are only formal definitions in specific fields such as information theory for Information (bits) and knowledge such as in cognitive architectures. Data doesn't have a precise meaning either, haven't seen a formal model of that in any case.


Does this proof work for infinite regular languages

The problem with your argument is in the interpretation of the second lemma. Closure under union says "If $L_1$ and $L_2$ are regular languages, then $L_1\cup L_2$ is regular." By induction, then, the union of any finite collection of regular languages is regular. You cannot, however, conclude that the union of an arbitrary collection of regular languages is regular, as Raphael pointed out, since your observation
$$
L=\bigcup_{e\,\in\, L}\{e\}
$$
is true for any language at all, regular or not, so since a single string language is regular, then every language would be regular.

What you could do is exploit some other closure properties of regular languages. For instance

If $L_1$ and $L_2$ are regular languages, so is $L_1\cap L_2$.
If $L$ is a regular language, its complement $\overline{L}$ is too.
We can thus write the set difference $A\setminus B$ as $A\cap\overline{B}$ so regular languages are closed under set difference.
If $L$ is any regular language and $e\in L$ is any string in $L$, then $L\setminus \{e\}$ must also be regular.


Algorithm to turn gray-scale text into legible binary black and white text

It is possible that the literature on image vectorization might be useful.  That basically tries to reconstruct the strokes that produced the image.  However, I think this is going to be challenging when the width of the strokes is narrower than two pixels or so, and it is possible that standard techniques might work poorly in that domain.  I would recommend that you try increasing the font size or the resolution, and then try standard methods.

For your example image, I get somewhat more reasonable results by using a better threshold (0.8), but I think you'll do a lot better if you can increase the resolution.

If you know in advance what font and font size will be used, it might be feasible to render each possible character and capture an image of the anti-aliased rendered result for each possible character, in a few random locations, and then use simple pattern matching.


Yes, there are more algorithms to do so in $\mathcal O(n)$. The first is dated back to ElGindy and Avis in 1981, Lee 1983 and Joe & Simpson in 1985. The visibility algorithms use stack (the first one three stacks, further only one) and process vertices in order they appear at boundary.

The visibility algorithms described in book Art Gallery Theorems and Algorithms by Joseph O'Rourke. The book is out of print, available online.

Also author wrote a paper the vertex-edge visibility graph of polygon with Ileana Streinu in 1996, which with Chazelle's linear time triangulation and slight modification (simply by adding two edges from given point) would solve the problem in linear time.


Suggestions:

Varaibles:

introducing a dummy varaible $t$.

Objective function:

add term $-20t $ to the function

Constraints:

Replacing the last constraint w.r.t. Machine C with
\begin{align}
t \leq 16 \\
2x_1 + 1x_2 \leq t \\
t\geq 0.
\end{align}
Done !


Transforming a bounded knapsack to 0/1 knapsack

The approach you described does not work necessarily.

If you have the following situation (I made it simpler)

          | Profit | Weight | Total |
Object 1  |   5    |   3    |   3   |
Object 2  |   2    |   6    |   2   |

If you transform the problem according to your proposal we get the following situation

            | Profit | Weight |
Object 1.1  |    5   |   3    |
Object 1.2  |   10   |   6    |
Object 1.3  |   15   |   9    |
Object 2.1  |    2   |   6    |
Object 2.2  |    4   |  12    |

If the capacity of the knapsack here is $15$ the 0-1 knapsack algorithm will give you an invalid optimal answer. Taking object 1.2 and object 1.3 with profit $25$ and weight $15$, but this items are supposed to be exclusive (if you take 2 items of element 1 you can't take 3 also).

So another approach to transform it in a 0-1 knapsack is by creating a new item per instance.

            | Profit | Weight |
Object 1.1  |    5   |   3    |
Object 1.2  |    5   |   3    |
Object 1.3  |    5   |   3    |
Object 2.1  |    2   |   6    |
Object 2.2  |    2   |   6    |

The solution of this problem is equivalent to the original problem, but this don't scale very well, because if you have up to $10^9$ (or more) instance of an object, you need to create one item per instance.

Why this model works? and how can we improve it?
This model works because we split each object in several group of items (each group of size 1)and it allows us to combine them in order to get any number of objects up to the maximum. For example, if one object appear 7 times we split it in $(1,1,1,1,1,1,1)$ and if we want in the optimal solution only $3$ of them, then we pick any subset of size $3$ of this set.

But we can split them in other ways, keeping the condition that we can take a subset that sums whatever sum we want up to the maximum. For example you can split $10$ like $(1, 2, 3, 4)$, and this partition is useful since you can get any sum up to $10$. There is a canonical way to split a number in $log_2(n)$ numbers that has this property. Split the number in power of 2 starting from $1, 2, ...$ until you can't split it anymore, and add the remainder to the partition too.

For example:

5 -> (1, 2, 2)
10 -> (1, 2, 4, 3)
15 -> (1, 2, 4, 8)
1000 -> (1, 2, 4, 8, 16, 32, 64, 128, 256, 489)

Then if your original problem looks like this

          | Profit | Weight | Total |
Object 1  |   5    |   3    |   7   |
Object 2  |   2    |   6    |   17  |

We split $7=1+2+4$ and $17=1+2+4+8+2$
You transform it into this equivalent 0-1 knapsack problem

            | Profit | Weight |
Object 1.1  |   5    |   3    |
Object 1.2  |  10    |   6    |
Object 1.3  |  20    |  12    |
Object 2.1  |   2    |   6    |
Object 2.2  |   4    |  12    |
Object 2.3  |   8    |  24    |
Object 2.4  |  16    |  48    |
Object 2.5  |   4    |  12    |

The optimal answer here gives you a straight forward way to recover the original answer, and the amount of new elements you create for each different item is at most $O(log(frequency))$, where $freq$ is the instance you have of some particular object.


The "complexity" of the Turing machine state specification

Complexity theory typically handles asymptotics, not finite cases.  In particular, complexity theory looks at the asymptotic running time as a function of $N$.  If you have only a single fixed $N$, then the standard framework doesn't apply.  It's not possible to talk about the running time being asymptotically an exponential function of $N$, because with only a single value of $N$, it is just a fixed constant; it's not a function of anything.  Complexity classes like EXPTIME are defined in terms of these asymptotics, so they aren't applicable if you have just a single function you want to compute, for a single fixed value of $N$.

So, if you want to apply the machine of complexity theory, you need to consider a family of boolean functions, one for each $N$, and a single Turing machine that computes all of them.  Then you can characterize the running time of that Turing machine as a function of $N$ (the length of the input).  At that point, there is no opportunity to "hide exponentialness" in the definition of the Turing machine, because you need to pick a single fixed Turing machine that computes all of them, and your idea for "smuggling exponentialness" can't be done if you have a fixed Turing machine.  Whatever you do, you only get a constant-factor speedup.

I have seen some formalizations that characterize the complexity not by the running time of the machine, but by the running time plus the length of the machine specification.  For instance, in the RAM model, you can use the running time of the algorithm plus the length of the code of the program.  Then, you can measure how this behaves as a function of $N$.  You can even characterize it for a single $N$, but then you're not dealing with asymptotics or complexity theory or complexity classes like EXPTIME; you're just saying that the least-complexity program to implement this one function has time+size equal to such-and-such.  For instance, this approach is sometimes used in theoretical cryptography (called "concrete security"), where we care about a single value of $N$, rather than the asymptotic behavior as $N \to \infty$.  But again, then you can't talk about complexity classes like P or EXPTIME.


Proving that an equal partition does not exist

The current expectation is that most likely there is no efficient (polynomial-size, polynomially-verifiable) way to do that.

The partition problem is NP-complete.  For a NP-complete problem, we have an efficient way to certify that the answer to the question is YES, but not necessarily any efficient way to certify that the answer is NO.  If you find an efficient way to verify that the answer is NO (i.e., a polynomial-length proof that can be verified in polynomial time), then you have proven that the problem is in co-NP.  If you prove that any NP-complete problem is in co-NP, then you have proven NP = co-NP.  Currently, it is widely conjectured that NP $\ne$ co-NP.  Assuming that conjecture is correct, there is no polynomial-length polynomially-verifiable proof that an equal partition does not exist.


Maximum single-precision floating-point format number

The second exponent is FF, which signals NaN according to Wikipedia, and so the highest exponent is only FE. This is verified by the following C code snippet:

unsigned int i = 0x7FFFFFFF;
float f = *(float*)&i;

If you print f you get nan.


classify location of the expiry date on drug label and lot number

It seems plausible that it might be doable, using methods in the research literature on object detection and localization (Yolo, Faster R-CNN, etc.).  The only way to tell for sure is to acquire a large dataset of such images and try it out and see how well it works on your data.


How do I compute the power consumption of a DRAM refresh?

$P = I \cdot \Delta V$, meaning one has to find the current consumption $I$ and the difference in voltage $\Delta V$, often denoted by $V_{dd}$ of the respective DRAM, in this case one can choose an arbitrary DRAM since nothing is specified.


Is there a formal definition for iteration?

The $k$th iteration is just the $k$th element of some appropriate sequence. In general, I doubt it's a formally defined concept; it's just one of those things whose meaning is basically the natural-language meaning of the word.


Why and how geometric series are used for proofs?

Okay, this is the first case of my comment. This isn't a "tool"; this is simply the formula that comes up when you try to estimate the expected time complexity. Or more precisely, the expected number of iterations of the loop.

The $\frac{m}{\ln m}$ estimate for the number of primes less than $m$ comes from the prime number theorem. If we uniformly pick a number from $\{2,\dots,m\}$, then the probability that it will be prime is $\frac{1}{\ln m}$. The probability that it won't be prime is then $1-\frac{1}{\ln m}$. The probability that we will find a prime in exactly $i$ iterations is the probability that we fail to find a prime in the first $i-1$ iterations, and then find one on the $i$th iteration. Since the selection of the random numbers are (assumed) independent, this is $(1-\frac{1}{\ln m})^{i-1}\frac{1}{\ln m}$. Let $S$ be the number of iterations the algorithm takes. The probability that the algorithm takes exactly $i$ iterations, i.e. $S=i$, is $$P(S=i)=\left(1-\frac{1}{\ln m}\right)^{i-1}\frac{1}{\ln m}$$ except $P(S=0)=0$ since the algorithm always goes through at least one iteration.

By definition of expectation, the expected value of the number of steps is $$\mathsf{E}[S]=\sum_{i=0}^\infty SP(S=i)$$
Expanding this out, we get $$\mathsf{E}[S]=\sum_{i=1}^\infty i\left(1-\frac{1}{\ln m}\right)^{i-1}\frac{1}{\ln m}$$

In other words, exactly the geometric series you mention. At no point did I attempt to get the problem in the form of a geometric series, and there is no guarantee that it would be of that form. Instead, you can just start from the definition of expected value which is what you're trying to show. Then you see you need the probability of $S=i$ which happens to have a form that leads to the expectation being a geometric series. That said, if each iteration of a loop independently has a constant probability of terminating, which is common, then you will get a similar geometric series. If the probability changed with each iteration or the probabilities were correlated, then you would not end up with a geometric series in general, but the approach to the solution would be just the same, though actually simplifying the resulting infinite series in those cases might be quite difficult or impossible.


Is there a generic word for "thread or process"?

A process is a context with one or more threads of execution (concurrent with other threads of execution, either in the same process, or perhaps in other processes), and with its own address space (and usually other resources such as open file descriptors, IPC mechanisms, etc.).  More subtle details and implications are described here

So, if address space (and other such resources) isn't relevant to your discussion (and it's probably not given your description), then I would say that the word thread is sufficient to describe the entities involved in your discussion.  Historically task has also been used to describe a thread, and indeed it was perhaps the first word used to describe this concept (see this).

(Note of course there's a difference between concurrent threads and parallel threads -- concurrent threads may be executed in parallel, but it is not necessary for operations to occur in parallel for them to suffer from the issues related to concurrency.)


How come correctness proofs aren't tautological?

Membership is much more general than this recursive definition you give. At a higher level you could define membership as follows:

A tree can be defined as a collection of nodes, $V$, and edges $E$ where those edges and nodes satisfy particular constraints.
We say a value $x$ is a member of the tree if and only if there is a node $v$ in $V$ such that the value of $v$ is equivalent to $x$.

You then prove (probably with induction since it's recursive) that your function is equivalent to this definition. That is to say, your function returns true on value $x$ if and only if there is a node $v$ in $V$ such that the value of $v$ is equivalent to $x$.