Can a dynamic language like Ruby/Python reach C/C++ like performance?

To all those who said “yes” I’ll offer a counter-point that the answer is “no”, by design. Those languages will never be able to match the performance of statically compiled languages.

Kos offered the (very valid) point that dynamic languages have more information about the system at runtime which can be used to optimise code.

However, there‘s another side of the coin: this additional information needs to be kept track of. On modern architectures, this is a performance killer.

William Edwards offers a nice overview of the argument.

In particular, the optimisations mentioned by Kos can’t be applied beyond a very limited scope unless you limit the expressive power of your languages quite drastically, as mentioned by Devin. This is of course a viable trade-off but for the sake of the discussion, you then end up with a static language, not a dynamic one. Those languages differ fundamentally from Python or Ruby as most people would understand them.

William cites some interesting IBM slides:

  Every variable can be dynamically-typed: Need type checks
  Every statement can potentially throw exceptions due to type mismatch and so on: Need exception checks
  Every field and symbol can be added, deleted, and changed at runtime: Need access checks
  The type of every object and its class hierarchy can be changed at runtime: Need class hierarchy checks

Some of those checks can be eliminated after analysis (N.B.: this analysis also takes time – at runtime).

Furthermore, Kos argues that dynamic languages could even surpass C++ performance. The JIT can indeed analyse the program’s behaviour and apply suitable optimisations.

But C++ compilers can do the same! Modern compilers offer so-called profile-guided optimisation which, if they are given suitable input, can model program runtime behaviour and apply the same optimisations that a JIT would apply.

Of course, this all hinges on the existence of realistic training data and furthermore the program cannot adapt its runtime characteristics if the usage pattern changes mid-run. JITs can theoretically handle this. I’d be interested to see how this fares in practice, since, in order to switch optimisations, the JIT would continually have to collect usage data which once again slows down execution.

In summary, I’m not convinced that runtime hot-spot optimisations outweigh the overhead of tracking runtime information in the long run, compared to static analysis and optimisation.


RAM BSS model based (or its variant) computer recognizing Boolean languages

Christine Gaßsner studied the question you are asking. These papers seem relevant, but you should have a look at her list of publications (DBLP):

The Separation of Relativized Versions of P and DNP for the Ring of the Reals. J. UCS 16(18): 2563-2568 (2010)
Oracles and Relativizations of the P =? NP Question for Several Structures. J. UCS 15(6): 1186-1205 (2009)
Relativizations of the P =? DNP Question for the BSS Model

You seem to be asking a basic question, namely: can BSS RAM machines recognize any boolean languages? Well, a BSS machine always has some kind of comparison operator, at the very least $<$ on real numbers. We can use it to decide equality of $0$ and $1$, from which it follows that a BSS machine can recognize at least all the languages that an ordinary RAM machine can. The more interesting question is whether it can do more than that, or perhaps more efficiently.


Inequality over the entropy of an integer-valued random variable

Man, that's a nasty inequality.

Anyways, given a certain expectation $E[Z]=\mu$, it is known that the distribution that maximizes $H(Z)$ while keeping $E[Z]=\mu$
 is the the Geometric Distribution with parameter $p=1/\mu$.

Then, it is easy to check that the inequality is satisfied (in fact the equality holds).
Indeed, if $Z\sim Geo(p)$ then $E[Z]=1/p$ and $H(Z)=-\log p -\frac{1-p}{p}\log(1-p)$.
Since this distribution maximizes $H(Z)$, any other distribution with the same expectation will have a lower left-hand side, while the right-hand side won't change (since $E[Z]=\mu$ didn't change). This proves the claim.


Return destinations for an expression-oriented programming language

1) In a sense, yes. Guy Steele wrote the "Lambda papers", where he reduced many different constructs to lambda expressions, in a compositional way. He used the lambda abstractions of Scheme for this, but the construction is general.

2) You should read about continuation passing style. Scheme, for instance, uses  "call with current continuation" call/cc to achieve what you describe: "returning" from a deeply nested location.

call/cc is probably not the most convenient notation, but it works, and can be used with any expression. E.g.

(call/cc (lambda (k)
  (+ 1 (if (some-condition) 10 (k 2)))

Above, if the condition is true, the if evaluates to 10, which is added to 1, so that the whole result is 11. If it is false, (k 2) is evaluated, "returning" to the point call/cc was used with result 2. Note that this skips the (+ 1 ..) part. You can nest call/cc arbitrarily, providing many "return points" as wanted.


Proving that collision is less likely if the table size is prime in case modulo arithmetic is used

It requires Theorem 31.20 on Page 927 from the CLRS (for which there is a proof of the theorem on the same page) that "if $d = gcd(a, n)$ then $\langle a\rangle = \langle d \rangle = \{0, d, 2d, \ldots, ((n/d) -1)d\}$ in $\mathbb{Z}_n$, and thus $|\langle a\rangle| = n/d$"

But it's Corollary will be more useful to the proof:
"The equation $ax \equiv b \mod n$ is solvable for the unknown $x$ if and only if $d|b$, where $d = gcd(a, n)$"

These conclusions will be the core of the proof.


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

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

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

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

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

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


Let $D(z,k,l)$ be the number of permutations $p_1,\ldots,p_z$ of $1,\ldots,z$ in which the condition $p_i + p_{i+1} \leq k$ is violated exactly $l$ times. Then $D(z,k,l)$ is given by the following recurrence relation, which is valid whenever $z \geq 2$ and $z+1 \leq k \leq 2z-1$:
$$
D(z,k,l) = \begin{cases}
(z-l) D(z-1,z,z-2-l) + (l+1) D(z-1,z,z-3-l), & k = z+1, \\
(z-l) D(z-1,k-2,l) + (l+1) D(z-1,k-2,l+1), & k \neq z+1.
\end{cases}
$$
I leave the proof of correctness to you.

(Here is a hint for the first case: show that $D(z,z+1,l) = D(z,z,z-1-l)$ and that $D(z,z,l) = (z-l) D(z-1, z, l-2) + (l+1) D(z-1, z, l-1)$.)

The following Python program implements this recurrence:

def D(z, k, l):
    if z < 2 or k < z+1 or k >= 2*z:
        raise "Error"
    if z == 2:
        return 2 * int(l == 0)
    if k == z+1:
        return (z-l) * D(z-1, z, z-2-l) + (l+1) * D(z-1, z, z-3-l)
    return (z-l) * D(z-1, k-2, l) + (l+1) * D(z-1, k-2, l+1)

A more efficient implementation will use dynamic programming, I leave that also to you. One thing to notice is that case II preserves the quantity $2z-k$ while case I always has $k = z+1$, so the algorithm is quadratic rather than cubic.

For concreteness, here is a Python implementation of the dynamic programming method:

def DP(z, k):
    if not (z >= 2 and z+1 <= k <= 2*z-1):
        raise "Error"
    z_crit = 2*z-k+1
    L = [2, 0]
    for w in range(3, z_crit+1):
        L = [(w-l) * L[w-2-l] + (l+1) * L[w-3-l] for l in range(w-2)] + [2 * L[0], 0]
    for w in range(z_crit+1, z+1):
        L = [(w-l) * L[l] + (l+1) * L[l+1] for l in range(w-2)] + [2 * L[w-2], 0]
    return L[0]


What is the theoretical speedup with pipeline system over a nonpipelined system?

The total time to compute $n$ tasks with no pipelining is $nT$ (the top of your fraction).  The total time to compute $n$ tasks with a pipeline $k$ stages deep, and a clock cycle time of $t$ is $nt$ (to produce the results once the first task reaches the last pipeline stage) + $(k-1)t$ to get the first task from the beginning of the pipeline to the last stage.  This is the $(k + n - 1)t$ in the bottom of your fraction.

The part you are missing is that $kt$ (the time for each task to get from beginning to end of the pipeline) must be larger than $T$.  This is because in the perfect case you would divide the circuit of delay $T$ into $k$ exactly equal segment, but then you would need to insert a register between each segment and the next, which will add delay.

So replace $t$ with $T/k$ in your fraction and take the limit as $k\rightarrow\infty$ and you will have your answer.

More interesting is to replace $t$ with $T/k + r$ where $r$ is the  constant extra register delay that you need to add between stages, take the derivative of your fraction with respect to $k$ and set it equal to 0 and solve


Is there an algorithm for algorithms time/space complexity optimisation?

Look up Blum's speedup theorem (yes, this article is less than informative; look at a book on complexity theory). It essentially says that there are programs for which there is a program doing the same job that is faster by any specified margin for almost all input data.

By Rice's theorem, it is impossible to know if two given programs do the same job.

Yes, for some very restricted notions of "program", given an example one can construct the "best possible" program for the job. Important classes, even. But a very far cry from anything which is able to express bubblesort.


Space and time complexity of balanced parentheses enumeration algorithm

This is a simple enumeration algorithm. The space complexity is $O(n)$, and the time complexity is the size of the output, since you do not doing anything useless.

By the way, the number of rows in the Catalan number. $C_n=\frac 1 {n+1}\binom {2n} n$.


Can a Markov Algorithm Replace the Empty String?

Rules of the form $\epsilon \to w$ are allowed for Markov Algorithms. Be aware, however, that they will not only match, when the string is empty. Instead they will match every string, since every string contanins $\epsilon$ as a substring.

Since a rule that matches at multiple positions will be applied to the leftmost of them by definition, Rule 3 from your question will prepend a 0 to the string and terminate, whenever no rule before it is applicable. So, unless your previous processing relies on the fact that the algorithm will terminate when no rule is applicable (or already contains a rule for a or b), adding the three rules from the question as the last rules will give you the desired result.


Longest subsequence accepted by DFA (Dynamic Prog algorithm)

You can add an extra parameter $s$, which represents a state of the DFA, for your dynamic programming.

Let $f(i,s)$ be the length of the longest subsequence of $A[1\ldots i]$ accepted by a DFA obtained by changing the end state of the primary DFA to $s$. Now $f(i+1,s)$ can be computed by comparing $f(i,s)$ (representing $A[i+1]$ is not chosen) and $f(i,t)+1$ (representing $A[i+1]$ is chosen) for each state $t$ that transforms to $s$ when reading $A[i+1]$.

But note, the time complexity this algorithm is not bounded by $O(qn)$ because we may have to check no more than constant $f(i,t)$'s for each computation. A simple improvement is to consider $A[i\ldots n]$ instead of $A[1\ldots i]$. Now $f(i,s)$ represents the length of the longest subsequence of $A[i\ldots n]$ accepted by a DFA obtained by changing the start state of the primary DFA to $s$, and $f(i,s)$ can be computed by comparing $f(i+1,s)$ and $f(i+1,t)+1$ where $s$ transforms to $t$ when reading $A[i]$. Now the running time is improved to $O(qn)$.


What are the minimum memory requirments a microprocessors must have to perform any calculation?

unlimited complexity?

That requires unlimited memory, after all - the numbers must be stored somewhere, and the place to store them is always in memory.

So you need 1 memory 'cell' for each number, and another for each operation. You also need a counter to keep track of the next number or operation. Add to that a register to perform the calculation (only 1 is needed as you can use it to store the results in-place. In reality you'll use another register to notify you of errors such as overflow or division by zero).

Or to put it another way: you need sufficient RAM, an accumulator and a program counter. You can get away without the counter if the memory are streamed in sequentially on a specialist computing machine (eg on tape as per Euphoric's comment).


Data structure for a quantity to price multiplier table

It's hard to see anything beating the obvious implementation with arrays. You have an array whose columns are indexed by price bands and whose rows are indexed by quantity bands. Store that as a 2D array. Use a pair of 1D arrays to store the minimum value in each price and quantity band. To look up a value, just use linear search through the bands.  Binary search would be faster if the array is huge but it's probably not necessary for small arrays (and your "20 if-statements" suggests the array is very small).

Load the data from a file so you can easily rebuild the data structure if you change your discounting schemes. I'm assuming this is a relatively rare event and, with a small table, it takes no time anyway.


Any CPUs using value prediction, dynamic instruction reuse?

Modern Intel processors use prediction of values in several situations.

One, when the target of a branch instruction is stored in memory including the location where the return address of a call is stored, that value is predicted.

Second, when a store is followed by a load, it is predicted whether the addresses are the same (or overlapping) or not. That allows the load to be performed speculatively even before the value to be stored is calculated, if it is predicted that the addresses are different.


The problem is not decidable (by reduction from the Halting problem), so there is no perfect algorithm that always terminates and always gives the correct answer.  Therefore, you'll need to make some tradeoffs.  That will depend on the specifics of your particular application, so it's hard to recommend a particular technique without knowing how you plan to use it.


Genetic algorithms are a metaheuristic and as such there is no general analysis that applies to all genetic algorithms at once (without being super loose). In general, when you are searching for information on the run-time of genetic algorithms, you will have more luck if you use the terms "convergence time", since that is the more common terminology. A good start on some formal techniques:

Y. Rabinovich, A. Wigderson. Techniques for bounding the convergence rate of genetic algorithms. Random Structures Algorithms, vol. 14, no. 2, 111-138, 1999.

For more resources on formal treatments, consider the cstheory question: Provable statements about genetic algorithms.


How to compare the time-complexity of an optimized algorithm with that of the original?

I am not sure what you mean by "complexity optimization".

A proper way to compare complexities is by considering their
ratio, which is defined up to a constant factor. Considering the difference makes no sense, as there is always
the invisible constant factor lurking around, invisible but not
negligible.

However your problem here is that you have several variables, not the
same in both variants of your algorithm, and no indication of how they
relate. If you do not say precisely how $n$ and $m$ relate to $h$ and
$w$, there is nearly nothing that can be done.

Given That all you know is that $n<h$ and $m<w$, the best you can say
is that  $n\times m<h\times w$. But they may differ by a constant
additive term or by a constant multiplicative factor, which does not
change the complexity.

So the best you can say is that $O(m\times n)\subseteq O(h\times w)$,
short of more precision on how $n$ and $m$ relate to $h$ and
$w$

Thus $O(h)+O(m\times n)\subseteq O(h)+O(h\times w)$.

But $O(h)\subseteq O(h\times w)$, because both are linear in $h$ and
the first is constant in $w$ while the second is linear.

Hence you get: $O(h)+O(m\times n)\subseteq O(h\times w)$.

All we know is that the complexity is not worse than before.

But that should not worry you too much. You seem to have the wrong
vision of complexity, when asking:

  is it a real optimization ?

Your optimizations aim at improving performance in your range of
applications.

Complexity does not measure performance but scalability. A
  constant multiplicative factor of ten zillions does not change the
  complexity but has a drastic effect on performance. The matrix
  multiplication algorithm that have the best complexity are never
  used because they have abysmal performance. You have to consider
  huge matrices for them to be any use.

Furthermore, raw complexity on arbitrary measure of the size of the
problem may have little practical meaning in some cases. The relevant
size for some complexity analyses may be the number of occurences of a
specific feature of the problem input, rather than the length of the
problem in number of symbols. Some exponential algorithms are
routinely used without problems because the feature causing the high
complexity is actually rarely used, independently of the input size.

Your modification of the algorithm may be a real optimization, that
may give you an algorithm ten times faster, but this may not show in
complexity analysis.

This is why it is sometimes useful to do precise cost analysis. But
that is more difficult since you must account for the different costs
of different elementary operations (which is not required for
complexity analysis).

A possible way to assess your optimization is benchmarking, rather
than tedious theoretical counting.

Your question did not say whether you were considering worst case or
average complexity. I did not ask because my remarks apply in both
cases.

Note: The fact that the algorithm has better performance, with the same
worst case complexity does not imply that the average complexity was
improved.


Machine code: How can an OS prevent user-level programs from accessing each other's memory?

The key is Virtual Memory.

There might be many ways to do this, but the reigning one across most OSes (*nix or Windowses alike) is Virtual Memory. And it needs CPU support, which is given in x86 by the MMU (Memory Management Unit) and in which I'll base my examples further on.

The secret is: no user-level process has access to the whole CPU. x86 has four rings of execution, and certain CPU opcodes (instructions) execute only within the appropriate ring. Ring 0 is for the kernel (the heart of the OS), and ring 3 is for user-level processes (rings 1 and 2 are most often not used, and if used, it's usually for virtualisation purposes -- out of the scope of this answer). If you execute an instruction within the wrong ring, the CPU faults to the kernel. Hence, if a process tries to execute a privilege instruction, when the CPU is on ring 3 mode, the CPU itself stops that process and gives control to the kernel, which will usually kill that process. Only the kernel can change the ring mode.

The secret-key for memory protection is that, all memory accesses, unless executed within the kernel's ring 0 (and perhaps even within that ring mode, but that's not relevant for this discussion, as we're talking only about user processes, not the kernel), need to go through the MMU, which will translate the memory address of the process to that which the kernel has actually given.

So two different processes can access a memory cell by the same address, say, 0x45b3c1, whatever. In reality, the MMU will translate real-time each process's request to what the kernel says it should be.

For this, the kernel prepares page tables, which you can imagine as a "map<void*, void*>" (forgive my over-simplification here, and try to imagine the crazy optimisations needed), of what the process actually has. And it prepares tables only for what the process previously said it would use. If the process asks for an address that hasn't previously asked the kernel to prepare a table for him, then the CPU says this process got nuts and in reference of this process, it signals the infamous SEGFAULT to the kernel, which will decide what to do next.

I know that this is sort of self-promotion, but I just recently wrote a lot about this topic and even gave a talk at my company, in case the link is welcomed I'd like to share: https://www.farfromready.com/malloc-alone-a-story-of-the-computers-memory/


What is the purpose of M:N (Hybrid) threading?

I think hybrid threading is very similar to a thread pool.

In thread pool, you are using $N$ kernel threads to execute $M$ “tasks”, where $M$ can be much higher than $N$. The advantage over using one thread for each task (kernel only threading) is that you consume less resources, like memory (both virtual and physical) and kernel objects (at least in the specific case of Windows threads, but I imagine other OSes are similar in this regard). You also get less context switches, which increases performance (in the ideal case, where you have as many running threads as you have processors, you may have almost no context switches).

The advantage over user only threading is that you can take advantage of multiple CPUs or multiple CPU cores. And if one task blocks, you can create another kernel thread to use the available CPU more efficiently.

So, you get the advantages of both approaches, at the expense of some additional user-mode scheduling.

A disadvantage over kernel only scheduling is possibly bigger latency: if all the threads in the pool are busy and you add new short task, you may wait a long time before it starts executing.


Array contains elements that differ by K correctness proof

My line of thought for deriving this algo:

there is well-known Merge algo (part of Merge Sort) combining two sorted arrays
we can modify it to output only equal elements of arrays (i.e. producing intersection instead of union)
we can further modify it to return true on the first match, and false at the end
and finally, we can modify it to compare elements with given offset k

I suggest you to practice developing algos at leetcode or similar site, it will allow you to come up with similar solutions in a few minutes.


Proving that converting min-heaps to max-heaps requires time Ω(n)

You could argue that the level-hierarchy gives more information, but not by much. Assuming a full max-heap of distinct values the $min$ element is on the deepest level of $\frac{n+1}{2}$ nodes. Unless there is some additional ordering to the heap, it would then take $\Omega(n)$ just to find the $min$ element.


What aspects of linguistics are necessary or good for natural language processing?

NLP is a big place, you might want to be more specific.

Within information retrieval, stemming is a linguistic idea that has become useful as a heuristic means of reducing vocabulary size.  As a practitioner I learned about it from An Introduction to Information Retrieval.


Languages with infinitely many but finite Myhill-Nerode equivalence classes

A random language would do. If $L$ is chosen by putting every word in $\Sigma^*$ in $L$ with probability $1/2$, then for every two given words $x \neq y$ and any third word $z$, the probability that $xz \in L \Leftrightarrow yz \in L$ is $1/2$. Hence almost surely $x$ and $y$ are not equivalent (since we can choose an infinite sequence $z_i$ so that the words $xz_1,yz_1,xz_2,yz_2,\ldots$ are all distinct). Since there are only countably many pairs of words, we find that almost surely, every word is its own equivalence class.

It is also not too difficult to explicitly construct such a language. It suffices to find a subset $A$ of the natural numbers such that for every $x,y \in \mathbb{N}$ there exists $z \in \mathbb{N}$ such that $x+z \in A \not\Leftrightarrow y+z \in A$ (why?). Let
$$
A = \bigcup_{i=0}^\infty \{4^i+1,\ldots,2\cdot 4^i\}.
$$
Given $x < y$, let $z = 4^y + 1 - y$. Then $z + y = 4^y + 1 \in A$, while $x + z < 4^y + 1$ and $x + z \geq z = 4^y + 1 - y > 2 \cdot 4^{y-1}$ (check!), showing that $x + z \notin A$.


Yes, using a bitvector, the running time will be $\Theta(n)$, i.e., $\Theta(2^k)$, for all operations.

If most sets are small in cardinality, a better option may be to use a sorted list of the elements in the set.  In this way, you can compute the intersection or difference of two sets of size $m_1,m_2$ in $\Theta(m_1+m_2)$ time (they work similar to the "merge" operation in mergesort).  You can compute the cardinality of a set of size $m$ in $\Theta(m)$ time, and test emptiness in $O(1)$ time.  If the size of the sets is small compared to $n$, this might be much faster.

You can make the cardinality operation take $O(1)$ time when using a sorted list by augmenting the data structure: when you construct the list, compute its cardinality and store that in a separate slot along with the list.  Now cardinality lookup takes $O(1)$ time.  It is easy to keep track of the cardinality of the new set when performing an intersection or differencing operator.

If there is some "pattern" to the set of elements in the set, another option might be to use a binary decision diagram (BDD).  You think of each element of $U$ as a $k$-bit vector, and think of a set as a set of $k$-bit vectors.  Then, you can use a BDD to represent that set.  Alternatively, we can associate to any set $S$ of a function $f:\{0,1\}^n \to \{0,1\}$ so that $f(x)=1$ if $x \in S$; then represent $f$ as a BDD (this is equivalent, and just a different way of thinking about the same thing).  If there is sufficient "structure" in the elements of the set, this might allow a more concise representation of the sets and more efficient operations.  The running time to compute the intersection or difference of two BDDs is related to the sizes of those BDDs.  In many contexts BDDs might be ineffective (they add implementation complexity with no improvements in performance), but in some special cases they might be useful.


why does the poly-time reduction from dominating set to vertex cover require adding a vertex to every edge?

The key reason we need $w_{uv}$ is because not every dominating set is necessarily a vertex cover, but $w_{uv}$ "patches" that up.
In particular, assume isolated vertices can be ignored. Then every vertex cover is a dominating set, but not every dominating set is a vertex cover. Hence, if we tried to do the reduction without adding $w_{uv}$, then only one direction would work: we can show that if $G$ has a vertex cover of size $k$, then $G$ also has a dominating set of the same size. However, the converse is not true; only by adding the $w_{uv}$ does every dominating set of $G^\prime$ necessarily dominate the $w_{uv}$ as well, and thus cover all edges in $G$.


Influence of the dimension of cellular automata on complexity classes

I will explain pieces of this article: Simulating 3D Cellular Automata with 2D
Cellular Automata.

Let's start by the encoding of the grid, a function $t:\mathbb Z^3 → \mathbb Z^2$. Intuitively $t$ can't preserves the distance because the number of cells at a distance less than $R$ from the origin won't be the same. You will need to embed these about $R^3$ cells into some the same number of cells but which will be somehow of the form $r^2$ but then you must have $r>R$. These $r$ and $R$ are a bit like the radius of the notion of neighborhood you find in any cellular automaton.

So the transformation of the article will make things essentially bigger by a power of at least $3/2$. That if points are distant of $d$ in the first grid, they will be distant of at least $O(\sqrt d^3)$ in the second grid. Unfortunately the given embedding is only in $O(d^3)$.

However, and this is a very important remark, you don't obtain the same neighborhood than in the first automaton and that's why I previously said "a bit like". To quote the article:

  it is obvious that there will be cells that are very close in $\mathbb Z^3$ and such that [their encoding will be] arbitrarily far in $\mathbb Z^2$

That works for time, too: the execution time of one step in $\mathbb Z^3$ can be arbitrary long in $\mathbb Z^2$. Note that the encoding is more of a simulation: the 2D CA the author even simulates the computation of the function $t:\mathbb Z^3 → \mathbb Z^2$.

It is a safe bet to say that the complexity (in time) of any algorithm ran on a 3D CA will explode when ran on the encoding of this 3D CA into a 2D CA. The author says it cannot be bound by any function in his simulation. And I say the explosion is at least exponential in general, because of the propagation time of the information depends on the position.

The idea of running algorithms on cellular automata seems already a bit weird to me, but that's personal. However that's nothing compared to the idea of an implementation of a cellular automaton into a silicon chip, or is it just me?


Wikipedia says that a graph all of whose non-trivial components are paths is a linear forest. Alternatively, you could call it just a disjoint union of paths.


Biggest number of components in a graph?

Suppose that a graph having $n$ vertices and $m$ edges consists of $k$ connected components, say of sizes $n_1,\ldots,n_k$. Then
$$
m \leq \binom{n_1}{2} + \cdots + \binom{n_k}{2}.
$$
Conversely, given $n_1,\ldots,n_k$ summing to $n$ which satisfy this inequality, we can construct a graph with $n$ vertices, $m$ edges, and at least $k$ connected components. We conclude that the maximum number of connected components of a graph with $n$ vertices and $m$ edges is the maximal $k$ such that we can find $n_1,\ldots,n_k \geq 1$ summing to $n$ satisfying the inequality above.

This leads to the following question: given $k$, maximize $\binom{n_1}{2} + \cdots + \binom{n_k}{2}$ subject to the constraint that $n_1,\ldots,n_k \geq 1$ are integers summing to $n$. The key is the following observation:
$$
\binom{a+1}{2} + \binom{b-1}{2} - \binom{a}{2} - \binom{b}{2}  = a-b+1.
$$
This shows that as long as $n_i \geq n_j$, moving a vertex from $n_j$ to $n_i$ increases $\binom{n_i}{2} + \binom{n_j}{2}$. It follows that the choice of $n_1,\ldots,n_k$ maximizing $\binom{n_1}{2} + \cdots + \binom{n_k}{2}$ is $n_1=n-k+1$, $n_2=\cdots=n_k=1$.

We have proved: the maximal number of connected components of a graph with $n$ vertices and $m$ edges is the maximal $k$ such that $$ m \leq \binom{n-k+1}{2}. $$


Base of logarithm in runtime of Prim's and Kruskal's algorithms

To expand on what David Eppstein said, you can assume it's in any base.

If the log were initially in base $b$, it is asymptotically the same as if it were in base $k$:

$$O(\log_b n) = O\left(\frac{\log_k n}{\log_k b}\right) = O(\log_k n)$$

because $k$ and $b$ are both constants; $\log_k b = O(1)$.

The logs in any two bases are the same in big-O notation.


The transition function of the union of regular languages

In the definition of a deterministic finite automaton, we require that the transition function $\delta$ is well defined on all of $Q\times\Sigma$, i.e. $\delta: Q\times \Sigma\rightarrow Q$. Sometimes we allow omitting transitions, and say that the automaton is "stuck" if it stumbles upon this transition, however in Sipser's book he defines the transition function as above (defined on all of $Q\times\Sigma$).

If you insist on allowing the the automaton to get stuck, then this results in a slight modification of the proof. Instead of looking at $Q_1\times Q_2$ (where $Q_i$ is the state set of the $i'th$ automaton), consider the state space
$\left(Q_1\cup\left\{\widehat{q_1}\right\}\right)\times\left(Q_1\cup\left\{\widehat{q_2}\right\}\right)$, where $\widehat{q_1},\widehat{q_2}$ are special states designed to deal with lack of transition. You can now complete the details yourself.


Understanding Closest Pair Algorithm (CLRS)

Assume that a point exists in every corner in the figure (including the inside corners). If points cannot overlap, then you have 6 points that can reside in the x2 box, and since you must be looking at one of them, you need only compare it to the next 5 in Y'.


Word- or byte-addressable? Correct terminology

From a computer architecture point of view, and with the caveat that nomenclature sometimes varies, especially when there is a family of related architectures which has evolved for a long time, or when the marketing department decides to that the usual terms have to used in another way (either to put the product in better light by using a bigger number, or to have a simple number to differentiate more or less related products).

A word has the size normally used for integer operations (often expressed as size of the integer or the general purpose registers, i.e. not address or data, internal or external buses, not address registers, not index registers).  A common issue is that when an architecture is an evolution of a previous one, one often keep the term word for the initial size and one use "double word" or "quad word" for what is a word if you look at the architecture in isolation.  Historically words have not always been a power of two (I know of sizes: 12, 16, 18, 24, 32, 36, 60, 64 and I don't think my knowledge is exhaustive).

Word addressable means that the memory is considered as arrays of words, and thus no smaller unit has an individual addresses.

A byte has various definitions.  The term was introduced to mean the unit used in character encoding at a time where multi-byte encoding didn't exist.  It is often used to means the smallest addressable unit for machine which are not word addressable (well as long at it is not one bit). I don't think those two definitions have ever given a different size. (nor a size different from 6 or 8 bits). For word addressable machine it often means some unit smaller than a word that the machine has some support for (for instance the PDP-10 -- a 36 bits word addressable computer -- had byte instructions which could manipulate any size from 1 to 35 or 36 bits).  Nowadays it is also often 8 bits.  Often several of those definitions are practically equivalent.

Byte addressable characterizes machines where the memory is considered as arrays of bytes in one of the above meaning.

AFAIK nibble has only been used for 4 bits quantities.

  E.g. someone could design some new CPU and memory type and define her byte to be 16bit?

Yes, but I'm not sure if it would make much sense to do so if one keeps the CA usage to use byte for something smaller than the word.  Having a word addressable 16-bit processor with no support for something smaller than a word may be a good choice for a special purpose processor.

  Secondarily, what is the antonym to this word I'm looking for? Page-addressable, block-addressable?

Bit-addressable, byte-addressable and word-addressable are the only terms I've seen use.  It doesn't make much sense to address only units bigger than the word at the architectural level.  Word-addressable is nowadays only used for special purpose processors such as DSP.  I don't think bit-addressability has been used for anything else than special purpose one excepted the IBM Stretch.

About your new main question

  What is the precise term for the smallest addressable memory block?

I know of none used in Computer Architecture (byte has been used for something smaller in word adressable machines), but is the definition used by C for byte.


Placing small circles randomly inside a larger circle, where no two small circles intersect

Suppose the small circles have radius $r$, and the large circle has radius $R$.  If there are less than, say, 100 small circles, then the following simple algorithm should be fast enough:

Generate a larger number, say 1000, of points at random locations inside a circle of radius $R-r$ (this smaller radius guarantees that a small circle centered at each point will fit within the radius-$R$ circle).
Calculate all roughly 500000 pairwise distances between points.
Sort these distances in increasing order.
Loop through the distances.  For each distance $< 2r$, randomly pick either point and delete it.  (Such a distance implies that there could not be a radius-$r$ circle at both points without overlap.)  If the distance refers to a point that has already been deleted, ignore it.
All points that remain are at least $2r$ apart from each other, so you can put a radius-$r$ circle at each.

If this is too slow, you could use a grid to speed things up: Make the step size of the grid $2r$, and only bother comparing point pairs that are in the same grid cell or adjacent grid cells.  (Every pair of points $x \in X, y \in Y$ for 2 non-adjacent grid cells $X$ and $Y$ is at least $2r$ apart, so we don't need to bother testing them.)

NOTE: This could leave holes where a small circle could fit.  My intuition is that having enough initial potential centre points will make this unlikely.  You could use a smaller grid, of step size $r$, to find some (not necessarily all) of these holes: A grid cell that does not overlap any circle is definitely a "hole" (a circle can be added there).

In case you're wondering, the problem you "really" want to solve is to find an independent set of vertices in a graph in which you have a vertex for each circle and an edge between 2 points whenever they are at distance $< 2r$.  The general form of this problem is NP-hard, though I suspect there is enough additional structure here that a faster solution (maybe poly-time, maybe not) is possible.


What is the best you can do with a noisy message?

Suppose that $k \ll n$. In that case, your friend can send you the index of the first door containing a treasure. Of the $k$ numbers you get, you pick the smallest one. If $k$ is small enough compared to $n$, then it is very likely that the smallest of the $k$ numbers is the one that your friend sent you.

More concretely, suppose that $k$ is constant. With probability $1-1/n$, the number that your friend sends you is at most $\log n$. The probability that the other $k-1$ numbers are more than $\log n$ is $(1-\log n/n)^{k-1} \approx 1-k\log n/n$. We conclude that this strategy fails with probability at most roughly $1/n + k\log n/n$, which tends to $0$ as $n \to \infty$.

To determine how small $k$ should be, let us be a bit more careful. Denote by $m$ the number that your friend sends you; the distribution of $m$ is geometric (we ignore for now the event in which there are no treasures at all), and so $\Pr[m] = 2^{-m}$. The probability that one of the other $k-1$ numbers is smaller than $m$ is $1-(1-(m-1)/n)^{k-1}$. Overall, this strategy fails with probability
$$
\frac{1}{2^n} + \sum_{m=1}^n 2^{-m} \left(1 - \left(1 - \frac{m-1}{n}\right)^{k-1}\right) = 1 - \sum_{m=1}^n 2^{-m} \left(1 - \frac{m-1}{n}\right)^{k-1}.
$$
We can non-rigorously estimate this as
$$
1 - \sum_{m=1}^\infty 2^{-m}e^{-(m-1)k/n} = 1 - \frac{1}{2-e^{-k/n}} = \frac{1-e^{-k/n}}{2-e^{-k/n}} \approx \frac{k}{n}.
$$
This suggests that if $k = o(n)$ then you win with probability $1-o(1)$.


Does "standard" Dijkstra's algorithm work with bi-directional edges and zero cost edges?

Yes, both of these cases work. You can even have zero-cost loops.


The only two methods I've seen are (a) a reduction or (b) direct proof (as in the proof of the Cook-Levin theorem).  It is almost universally the case that a reduction is easier than a direct proof.  Therefore, I suggest you keep trying to find a reduction, and consider other reduction partners.  There are lots and lots of problems known to be NP-complete; perhaps you can find one that is a more suitable partner than 3SAT.

Possibly useful: How do I construct reductions between problems to prove a problem is NP-complete?.


Consider the language $ALL_{TM}$ (sometimes also called $L_{\Sigma^*}$)
$$ALL_{TM}=\{\langle M \rangle: M \text{ is a TM and } L(M)=\Sigma^*\}$$

It is well known that $ALL_{TM}$ is not RE (nor co-RE). See, e.g., this question (and search for other related questions on this site).

From this fact, it is easy to see that AlwaysHalt cannot be RE: a reduction
$$ALL_{TM} \le AlwaysHalt$$ is rather trivial.


Algorithm to match / link complementary pairs

Assuming you don't want to repeat a song, this is the problem of finding a longest path in a directed graph.  Here the graph has one vertex per song, and an edge $s \to t$ if the ending of song $s$ blends well with the beginning of song $t$.

Unfortunately, the longest-path problem is NP-hard.  (See, e.g., Is finding the longest path of a graph NP-complete?,  How to prove NP-hardness of a longest-path problem?.)  This means that you should not expect to find an efficient algorithm for your problem that works on all graphs and that is always correct.  Instead,if you want to solve it in practice, your best will be to look for approximation algorithms or heuristics.

Unfortunately, it is also known that there are no approximation algorithms with guaranteed performance, i.e., that are guaranteed to find a path that is close to the longest, for all graphs.  (See
https://en.wikipedia.org/wiki/Longest_path_problem#Approximation.)  So your best bet is to look for heuristics... or hope your graph has some special structure.

If you are willing to allow repeated songs, then the problem becomes tractable in theory, but the resulting algorithms are probably going to provide poor-quality results in practice.  In particular, if you find any cycle in the graph, then it is possible to traverse the cycle an unbounded number of times, achieving an arbitrarily long path.  Unfortunately these algorithms have a decent chance of producing a cycle of short length, which means that your playlist will just repeat the same few songs over and over... which is probably not what you'd hope for.

One simple heuristic might be to pick a starting vertex randomly, do depth-first search starting from that vertex, find the leaf in the tree with largest depth, and use the path from the root to that leaf as your playlist.  You could repeat a few times from a few different random starting points and take the best playlist found.  There are no guarantees for how well this will perform; you'd have to try it out to see.


You can use the program ministat to get statistical information about runtime differences. This blog post gives an example for the usage.

But in general, comparing runtimes is difficult and very machine dependent. Ideally you would find another performance measure that doesn't change so much between processors.

You should also take care that your input instances are well chosen. Random instances might behave very differently from real-world cases, but the latter are typically hard to come by. You should try modelling "interesting" properties of real-world instances and generating instances that also have those properties. You can also try to look very hard at the data structures and try to generate instances that trigger worst-case behaviour, but that is typically also very hard.


Complexity of "Fast Poisson Disk Sampling in Arbitrary Dimensions"

I have just implemented this algorithm, generalized for an arbitrary number of dimensions. You are absolutely correct in your suspicions about the exponential growth with $n$, as far as I see.
Each of these $2 N - 1$ iterations require a lookup in the neighbourhood for each candidate, and the neighbourhood scales up exponentially with the dimension: from a line to a square to a cube, etc. A more accurate implementation can slow this growth by excluding the corners of the hypercube in higher dimensions, since they don't fulfil the distance criteria, but it won't stop the exponential growth.
Increasing the $k$ for the higher dimensions, on the other hand, does not make much sense to me. $k$ are the candidate points to be tested for acceptance, so if you find at least one valid point among them, the algorithm will continue until the entire space is filled. If anything, I think it's easier to find a valid point for a higher-dimensional case, since there are more degrees of freedom.
Also, here's a link to my implementation: https://github.com/diregoblin/poisson_disc_sampling


The language is regular:
$$ L = \{\}$$
It doesn't contain any word not even the empty word $\varepsilon$.
The automaton recognizing it has only one state; a reject state.
Or if you are using DFA the automaton just wouldn't have an accept state.
Notice that the language is regular but that the grammar is written in a form that's usually used for context free grammars, but the language produced by it is still regular.


How does an Operating System without kernel mode work?

It's more like an operating system without a user mode.  In many embedded systems there is only one (or a small number) of "applications" and so the application is just built right into the lowest-level of the system.

Desktop/server operating systems provide many services, some of them unnecessary for embedded systems.

At the lowest level you typically need some wrapper routines for accessing various physical devices (serial buses, sensors, actuators) and interrupt service routines for devices that need asynchronous attention.  In a desktop/server OS the device registers or memory mapped locations for accessing the device registers would be protected/hidden from the applications, but in an embedded system you can trust the application writer.

As you go up the stack some services may be necessary for a particular embedded system, but those can be provided by library routines.  For example, you might need a file system, but you just implement this as a library that provides open, read, write, close, make_directory and such routines to the rest of the system.

Your embedded system may (or may not) need to be able to load and execute programs not built into the kernel.  Again, you can provide the ability to load the executable part of a file off the disk into memory and then jump to some start location.

Your embedded system may (or may not) need dynamic memory allocation.  This just means that all the memory not otherwise in use is managed by a library routine (usually called malloc and free or something similar).

Your embedded system may (or may not) need multiple threads.  Many embedded systems manage the threads cooperatively.  That means that there are library routines to allocate and initialize memory for a new thread, and then the library selects one thread to run for awhile and when the thread calls some function (often called yield) this jumps back to the thread management library, which then selects a different thread to run and performs any necessary book-keeping.  This can be taken a step further by making the thread library preemptive (an interrupt handling routine calls the library's yield routine on a timer interrupt if the current thread doesn't call it itself.)

Since you know the apps that are running (and trust their authors) you generally don't bother with the hardware expense of different protected address spaces.  Similarly you generally don't bother with virtualizing the memory (using the disk or SSD to make the memory look larger than it really is.)


Is there a language with non-isomorphic minimum-state UFAs?

In their paper "A note about minimal non-deterministic automata" Arnold, Dicky and Nivat observe that the problem of finding non-isomorphic minimal automata was solved in a report by Christian Carrez (Lille, 1970).

They give the following example, which happen to be both unambiguous, so are applicable in your case too.


Is master theorem applicable for $T(n) = 8T(\frac{n-\sqrt n}4) + n^2$?

The master theorem isn't applicable, but the Akra–Bazzi theorem is, and it shows that your recurrence has the same solution (asymptotically) as the simpler one without the square root, that can be solved using the master theorem.


From a general point of view: there are tons, but I do sincerely recommend you the latest volume on Heuristic Search: Heuristic Search: Theory and Applications by Stefan Edelkamp and Stefan Schroedl.

From a specific point of view: in spite of the graph being directed or not, breadth-first search taking costs into account

If no heuristics are available, then it amounts to either Dijkstra or Uniform Cost Search. An excellent discussion between these two algorithms is presented in Felner, Ariel, "Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm", Symposium on Combinatorial Search, Barcelona (Spain), 2011.
If heuristics are available Then there are also a number of interesting alternatives: A$^*$ is the usual one but RBFS also expands the same nodes in the same order with a linear consumption of memory. For these, I do strongly recommend the book by Stefan Edelkamp and Stefan Schroedl.

Hope this helps,


Run along the columns of the matrix keeping three numbers. For each row determine the minimum score assuming the last number chosen came from that row.


Why does the cut $(V_C,V-V_C)$ respect $A$?

The cut $(V_C,V-V_C)$ respects $A$ since $C$ is a connected component in $(V,A)$.


Proving Infinite Turing Machine Language (with finite subset) is Recursively Enumerable

Regarding your first question, a reduction from the halting problem only shows that a problem is hard, not that it's easy. If the halting problem reduces to some problem $P$, then you know that $P$ isn't co-computably enumerable. So if you manage to reduce the halting problem to $L$, then this shows that $L$ is not co-computably enumerable. Perhaps that can inform your guess on the answer.

Regarding your second question, if you show that $L$ is c.e. but not computable, then indeed it follows directly that $L$ is not co-c.e. This is because a language that is both c.e. and co-c.e. is computable.

Let me give you a hint. Every Turing machine can be modified so that it accepts only strings beginning with 0: the new machine accepts $0x$ iff the old machine accepts $x$. Such a Turing machine belongs to $L$ iff it accepts infinitely many strings. Similarly, a machine which only accepts strings beginning with 1 belongs to $L$ iff it accepts finitely many strings.


Clarify the steps: what happened in this mathematical modelling of TSP?

You seem to have misunderstood pretty much every part of the statement

$$\sum_{i,j\in\{1,2,3\},i\neq j} x_{ij}=3>2=|\{1,2,3\}|-1\,.$$

  I get that $x_{ij}$ is equal to 3,

No, the sum of all values $x_{ij}$ where $i$ and $j$ are distinct values from $\{1,2,3\}$ is equal to $3$.

  but why the "> 2" ?

Because three is bigger than two.

  And what is the deal with subtracting 1 from a set? How do you even do that?

No, it's subtracting one from the cardinality of the set. Notice the $|\dots|$.

  How come $|\{1,2,3\}|-1 = 3 > 2$   ?!?

It isn't. When we write something like $A=B>C=D$, it means that $A=B$, $B>C$ and $C=D$. You can't just re-order the terms and expect the statement to remain true, just as you can't reorder $3>2$ as $2<3$ and expect it to remain true.

So, the statement as a whole means:

The sum of the values $x_{ij}$ is equal to $3$.
Also, $3>2$.
Also, $2=|\{1,2,3\}|-1$.

  So how is he allowed to write:
  $$|\{1,2,3\}|-1 = 3 > 2\,?$$

He isn't and he doesn't.


Explanation of pseudocode and time complexity analysis

First question: some book, for example well known CLRS 3ed. p25-26, counts, that in for loop test in loop header is executed one times more, then loop body. Accordingly you see $n^2=n(n+1)-n$ in 3-d line.
Second question: simplify $T(n)$ and write it as polynomial from $n$. Then you obtain representations for $a,b,c$: $$T(n)=c_2n(n+1)+c_3n^2 +c_1(n+1)+c_4=\\=(c_2+c_3)n^2+(c_2+c_1)n+(c_1+c_4)=\\=an^2+bn+c$$
So $a=(c_2+c_3)$, $b=c_2+c_1$ and $c=c_1+c_4$. If we speak about asymptotic estimation, then $T(n)=O(n^2)$.


How is this equation (involving a recurrence and $\phi(N)$) derived?

Here's the relevant part of the proof, quoting verbatim:

  First, show that $\phi(\phi(n)) < n/2$. This can be done as such:

  Let $n = \prod_{i=1}^rp_i^{k_i}$ be the prime factorisation of $n$
  ($p_i$ prime, $k_i>0$)

  Suppose $n$ is even. Then $\phi(n) = n\prod_{i=1}^r(1-\frac{1}{p_i}) \leq n(1-\frac{1}{2}) \leq n/2.$ Thus $\phi(\phi(n)) < n/2$.
  Suppose $n$ is odd and $n > 1$. Then $\phi(n) = \prod_{i=1}^r (p_i-1)p_i^{k_i-1}$ is even and smaller than $n$. By the previous
  result $\phi(\phi(n)) < n/2$.

  So we get the desired result.

This lemma is slightly mis-stated, because when $n=2$, $\phi(\phi(n)) = n/2$. But it doesn't invalidate the main result. We will state the lemma as:

Lemma For all $n \ge 2$, $\phi(\phi(n)) \le \frac{n}{2}$.

Tasse's proof sketch is a proof by induction in disguise, but this may not have been obvious to you. I'm going to simplify the proof sketch a little bit and lay it out more like a proper proof by induction.

Proof By induction on $n$.

Base case: If $n=2$, see above.

Inductive step: Suppose that for all $2 \le m < n$, $\phi(\phi(m)) \le \frac{m}{2}$. We want to prove that $\phi(\phi(n)) \le \frac{n}{2}$.

Case 1: Suppose $n$ is even, that is, $n = 2q$ for some $q$. In this case, the multiplicative property of the totient function says that $\phi(2q) = \phi(2) \phi(q) = \phi(q)$.

That is, $\phi(n) = \phi(\frac{n}{2})$. However, another useful property of the totient function is that for all $m \ge 2$, $\phi(m) \le m-1$. Therefore $\phi(\phi(n)) \le \frac{n}{2} - 1$.

This proves what we wanted for this case, but we have also incidentally proven another useful thing: If $n$ is even, then $\phi(n) \le \frac{n}{2}$. This will be important in the next step.

Case 2: Suppose $n$ is odd. That is, $n = p^k q$ for some odd prime $p$, and some positive integer $k$, and some $q$ which doesn't have $p$ as a divisor. Then:

$\phi(n) = \phi(p^k) \phi(q) = \left(p^k - p^{k-1}\right) \phi(q)$.

Now there are two things you need to notice about the right-hand side.

First off, it's less than $n$. Why? Because clearly $p^k - p^{k-1} < p^k$, and it's a standard property of the totient function that $\phi(q) \le q$. (Note that this is also true if $q = 1$.)

Secondly, it's even. Why? Because if $p$ is odd, $p^k - p^{k-1}$ is even.

So by that incidental result we discovered in case 1:

$\phi(\phi(n)) = \phi(\left(p^k - p^{k-1}\right) \phi(q)) \le \frac{\left(p^k - p^{k-1}\right) \phi(q)}{2} < \frac{n}{2}$.

QED


Prove that a language is bounded if and only if it's finite

The claim holds only for languages over finite alphabets.

Bounded $L$ $\implies$ Finite $L$

Let $\Sigma$ be the alphabet of $L$ and $L$ be bounded by some $n \in \mathbb{N}$.

The largest possible such $L$, call it $L^\#$, is $\bigcup_{\,i=0}^{\,n} \Sigma^i$ elements. $L^\#$ is finite since $|L^\#| = \sum_{i=0}^{n} |\Sigma|^i$. Therefore, any $L \subseteq L^\#$ must also be finite.

Finite $L$ $\implies$ Bounded $L$

Let $x^\#$ denote the longest string in $L$. Such a string must always exist since $L$ is finite.

Then, $\forall x \in L \ldotp |x| \leq |x^\#|$ and thus, $L$ is bounded.

A simple counterexample to the infinite alphabet case:

Consider an infinite alphabet $\Sigma = \{ s_0, s_1, ... \}$. The language $L = \Sigma$ is bounded since $\forall x \in L \ldotp |x| \leq 1$, but is infinite.


How many unique counting functions there are for strings of N bits?

Suppose that a set of functions $F_0,\ldots,F_{N-1}$ satisfies the constraints, generating the sequence $x_0 = 0^N, x_1, \ldots, x_{2^{N-1}-1}$. When does a function $F_N$ satisfy the constraints?

If $F_N$ works, then it generates a sequence of the form
$$ x_0\alpha_0, \ldots, x_{2^N-1}\alpha_{2^N-1}, \\x_0\alpha_{2^N}, \ldots, x_{2^N-1} \alpha_{2^{N+1}-1}. $$
The $\alpha_i$'s are given by the following rules: $\alpha_0 = 0$, and for $0 \leq i \leq 2^N-1$,
$$
\alpha_{i+1} = F_N(x_i\alpha_i), \\
\alpha_{2^N+i+1} = F_N(x_i\alpha_{2^N+i}).
$$
In order for the period to be $2^{N+1}$, we must have $\alpha_{i+1} \neq \alpha_{2^N+i+1}$. This means that there is a function $G_N\colon \{0,1\}^{N-1} \to \{0,1\}$ such that
$$ F_N(x\alpha) = G_N(x) \oplus \alpha. $$
It follows that for $0 \leq i \leq 2^N-1$, we have
$$
\alpha_{i+1} = F_N(x_i \alpha_i) = G_N(x_i) \oplus \alpha_i, \\
\alpha_{2^N+i+1} = F_N(x_i \alpha_{2^N+i}) = G_N(x_i) \oplus \alpha_{2^N+i}.
$$
In particular, this implies that
$$
\alpha_{2^N} = G_N(x_0) \oplus \cdots \oplus G_N(x_{2^N-1}).
$$
We must have $\alpha_{2^N} = 1$ in order to have a period of $2^{N+1}$, and this gives one constraint on $G_N$.
One can check that there are no other constraints, and so the number of possibilities for $F_N$ is $2^{2^N-1}$. In total, the number of possibilities is
$$
2^{2^0-1 + \cdots + 2^N-1} = 2^{2^{N+1}-N-2}.
$$
When $N=0,1,2$, this works out to be $2^0,2^1,2^4$. The corresponding sequences are:

For $N=0$, we have one sequence, $0, 1$.

For $N=1$, we have two sequences, $00, 10, 01, 11$ and $00, 11, 01, 10$.

For $N=2$, we have 16 sequences:
$$
000, 100, 010, 110, 001, 101, 011, 111 \\
000, 100, 010, 111, 001, 101, 011, 110 \\
000, 100, 011, 110, 001, 101, 010, 111 \\
000, 100, 011, 111, 001, 101, 010, 110 \\
000, 101, 010, 110, 001, 100, 011, 111 \\
000, 101, 010, 111, 001, 100, 011, 110 \\
000, 101, 011, 110, 001, 100, 010, 111 \\
000, 101, 011, 111, 001, 100, 010, 110 \\
000, 110, 010, 100, 001, 111, 011, 101 \\
000, 110, 010, 101, 001, 111, 011, 100 \\
000, 110, 011, 100, 001, 111, 010, 101 \\
000, 110, 011, 101, 001, 111, 010, 100 \\
000, 111, 010, 100, 001, 110, 011, 101 \\
000, 111, 010, 101, 001, 110, 011, 100 \\
000, 111, 011, 100, 001, 110, 010, 101 \\
000, 111, 011, 101, 001, 110, 010, 100
$$


Information Systems (IS) and Data Warehouse

Yes, I'd say that a data warehouse is an information system.  It stores information, using information technology; it's an information system.

That said, I think focusing too much on trying to obtain a precise definition of "Information System" and "Data Warehouse" is not likely to be super-helpful.  Those are just phrases.  "Information system" is a broad phrase that doesn't have an especially precise definition -- it gets used in whatever way the author finds helpful.  And that's OK.  It doesn't need a precise, universally-agreed-upon definition.  It's just an aid to communication.  Ultimately, it just doesn't matter that much how we classify data warehouses; if I told you they are (or aren't) an information system, that wouldn't really change how you should think about them.

My advice would be not to worry too much about terminology and trying to classify things into some taxonomy.  Instead, think about what are the relevant characteristics and properties of the kinds of data warehouse systems you are looking at.  Figure out what is your actual goal, and then identify what characteristics are relevant to that goal, and use that to hone in on the aspects of the system that are relevant.  Not all information systems are alike -- the range of issues that arise in information systems is incredibly broad.


What is the best known simulation result on a single tape TM? Does the result above also still hold?

We can simulate a multiple-tape TM on a single-tape TM with quadratic increase in time. The simulation time is $O(n^2)$. The quadratic increase is required since there are languages (e.g. palindromes) that require time $\Omega(n^2)$ on a single-tape DTM but can be solved in time $O(n)$ on a two-tape DTM.

In short, the result above does not work when the simulator is a single-tape TM.

For simulation of single-tape TMs on a single-tape TM (with arbitrary finite alphabet), the result holds, i.e. the simulation can be done with $\lg$ factor increase in time. See   (2) and (3). The reference seems to be (6).

  Is there any improvement on [HS66]? Can we simulate TMs on a two-tape TM for $f(n)$ steps in a faster way? Can we take $g(n)$ to be in $\omega(f(n))$ in place of $\omega(f(n)\lg f(n))$?

It seems that there hasn't been any improvement since that would imply a better time hierarchy theorem than currently known.

Correction: The usual hierarchy theorems are based on time complexity classes defined using single tape TMs. For $n$-tape TMs a tight result similar to the space hierarchy theorem is proven by Furer in 1982 (5). The $\lg$ factor is not needed. Also see (4).

References:

Peter van Emde Boas, "Machine Models and Simulation", in Handbook of Theoretical Computer Science, 1990
(in particular, pp. 18-21)
Michael Sipser, "Introduction to the Theory of Computation", 2006
(time complexity classes are defined using TMs with single-tape infinite in both directions and arbitrary finite alphabet, see pages 140 and 341)
Odifreddi , "Classical Recursion Theory", vol. I & II, 1989 & 1999
(definitions are similar to Sipser, see Def. I.4.1 in vol. I page 48, Def. VII.4.1 in vol. II page 67, and Thm. VII.4.15 in vol. II page 83)
Piergiorgio Odifreddi, "Classical Recursion Theory", vol. II, 1999
(page 84)
Martin Fürer, "The Tight Deterministic Time Hierarchy", 1982
Juris Hartmanis, "Computational Complexity of One-Tape Turing Machine Computations", 1968
F.C. Hennie and R.E. Stearns, "Two-Tape Simulation of Multitape Turing Machines", 1966
Other related questions:

Lower bounds and class separation,
Justification of $\lg f$ in DTIME hierarchy theorem,
Alphabet of single-tape Turing machine,
For the time hierarchy theorem, how is the input translated efficiently?,
a comment by Luca Trevisan.


So, I think part of the problem is that the resource you're using is not using standard lambda calculus notation.

In most texts, there is a space between arguments. I would write $\lambda x\ y\ z\ldotp z$ in place of $\lambda x y z\ldotp z$. But, if you assume a convention that variables are always single letters, you can omit the space without ambiguity.

But I can't imagine one would ever write whole programs this way. Rather, this is more likely to show up in examples, code snippets, and small proofs, where there aren't many variables and the names don't matter.

Basically it boils down to this:

A minimal lambda calculus only allows one argument per function, so there's no need for a delimiter. The dot denotes the function body.
There is common syntactic sugar for multiple arguments, which abbreviates $\lambda x \ldotp (\lambda y \ldotp (\lambda z\ldotp z))$ as $\lambda x\ y\ z\ldotp z$.
In a situation where variable names are assumed to be single letters, one could use $\lambda x y z\ldotp z$ in place of $\lambda x\ y\ z\ldotp z$.

There is no delimiter, other than the space, that I know of for arguments. Commas would be frowned upon, since they indicate tuples, rather than curried arguments.

EDIT: to respond to the OPs edit:

There is no such thing as multiple arguments in an untyped lambda calculus, at least not in standard ones. There are two ways to simulate multiple-argument functions.

Tuples: you can use a Church encoding to pass a single argument, which can be decomposed into multiple values. So you would write $f (<x,y>)$, where $<x,y>$ is some special syntax for making a pair, and then decompose it as $HD\ t$ and $TL\ t$ inside your function to get at each argument.
Currying: When, in an imperative language, you would write f(x,y,z), you write $(f\ x\ y\ z)$, which is syntactic sugar for $(((f\ x)\ y)\ z)$. A function accepting multiple arguments is just a function which returns another function.

It turns out that these two are basically isomorphic, so which you do doesn't much matter.

Some languages, like Scheme, have built in syntax for multiple-argument functions, but I haven't seen anything like that in a formal lambda calculus. Usually they're intended to be minimal, and so when you don't need multiple-argument functions, you don't put them in.


What does it mean to multiply or divide polynomials?

I am a bit uncertain by what you mean by graphical. One notion is to plot or graph a function, like $y=f(x)$, as you would in a highschool level algebra course. Another notion of "graphical" may include some similar to a Cayley graph. I just want to be upfront that the extent of my knowledge does not extend greatly into topology and some algebraic geometry. I will go off on the assumption that overly abstract "graphical" representations do not count.

Graphical Plots: In abstract algebra, the polynomials that work with the $y$ vs. $x$ type of graphing are in the ring of polynomials over $\mathbb{R}$, otherwise known as $\mathbb{R}[x]$. Evaluating any of these for an $x \in \mathbb{R}$ gives you a continuous function that you can plot. This works for $\mathbb{R}[X]$'s extensions, too ($\mathbb{C}[X]$).

Graphs: Cryptography and coding theory involve a massive number of structures, each of which can be represented as a graph. A notable set of examples are graphs depicting algebras over structures of finite size. Rings of polynomials are not one of them, since they contain, at minimum, a countable number of elements. Some intuition can be gathered from how these graphs change as you vary/limit the degree of your polynomial (more on this later). Though I imagine that this is not the kind of representation that you had hoped.

For other graphical/geometrical/topological aspects of crypto and coding theory, you might want to look into things like vector spaces, sphere packing, and lattices.

Polynomials Over Finite Fields:

Even so, it is important to realize that the inclusion of rings of polynomials in cryptography and coding theory are over finite fields. That is, they usually only consider $\mathbb{F}_q[X]$, which is the finite field with $q$ elements. An easily recognized one would be $\mathbb{F}_2^k = \{0,1\}^k$ (your typical algebra over binary strings).

A slight extension of this idea, rings of multivariate polynomials, are also useful. They are typically represented by $\mathbb{F}[X_1,X_2,...]$ where $\mathbb{F}$ is a field. An algebra of multivariate polynomial over $\mathbb{F}_2$ is equivalent to a boolean algebra. A boolean formula, $\varphi(x_1,x_2,...,x_n)$, would be equivalent to evaluating a degree $n$ multivariate polynomial over $\mathbb{F}_2$. The intuition behind this is to see that $+$ and $\times$ act like XOR and AND logic gates on your binary inputs, $x_1,x_2,...,x_n \in \{0,1\}$.

Beyond drawing something fundamentally equivalent to circuit diagrams, I do not see a fruitful way to represent this graphically. Though, this did not stop these guys from trying (I still think it is the same): http://polybori.sourceforge.net/zdd.html

There are obviously way more concepts from abstract algebra that are involved in these areas (e.g. $\mathbb{Z}_p$, the ring integers mod $p$). Some may even have graphical representations that make the idea more intuitive. Though these fall outside the scope of the question, which is specific to algebras over polynomials.


Is There An Established Way To Send Code Over a Network?

From memory Java applets and COM components could do this (But mostly discontinued due to security reasons)  The approach was mostly based on a pull strategy.  That is Machine B pulled code from Machine A and then executed in Machine B.

OS and application updates (e.g. Windows Update) also do this approach.  They download the update from a different machine and execute locally.


How can unifying 2 sentences in first-order logic result in a variable becoming 2 different things?

The variables called x in the two sentences are not related. We can rename them to make it clear:

~Loves(x1,F(x1)) v Loves(G(x1),x1)
~Animal(x2) v Loves(Jack,x2)

Now when matching ~Loves(x1,F(x1)) and Loves(Jack,x2), you can see you'll get Jack/x1, F(Jack)/x2 and the final result as in the book.


Yes, the right one is shown for convenience. Whether it is a standard convention I do not know and I think it is not so important as both trees are the same, the right one is just formatted neatly so that it matches the structure of the original graph.

It is not wrong to use the first layout (as shown on the left). However, readers might prefer the right one.


First of all, let me correct maximal matchings (that is, matchings which cannot be extended) to maximum matchings (that is, matchings of maximal size).
Suppose first that the starting vertex $v$ doesn't lie on all maximum matchings. Pick a maximum matching $M$ which doesn't contain $v$. The second player will always play an edge from $M$ – we will show that this is always possible. Suppose that the game play so far has been $v,a_1,b_1,\ldots,a_t$. We know that $M$ doesn't touch $v$. If it also doesn't touch $a_t$, then this is an augmenting path (check!), which contradicts the maximality of $M$. Hence $M$ must contain an edge $(a_t,b_t)$, which the second player can play.
Suppose next that the starting vertex $v$ does lie on all maximum matchings. Pick some maximum matching $M$ which contains $v$. The first player will always play an edge from $M$. Suppose that the game play so far has been $v,a_1,\ldots,b_t$. If $M$ doesn't touch $b_t$ then we could switch edges according to this "almost-augmenting" path to obtain another maximum matching which doesn't contain $v$. Hence $M$ must contain an edge $(b_t,a_{t+1})$, which the first player can play.


Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem?

Integer linear programming can potentially be more efficient.  ILP solvers normally combine backtracking with many other methods, so for many problems ILP might be faster than backtracking alone.  There are no hard-and-fast rules about which will do better on every problem, though.  It's not just implementation in C++.


What is the difference between superposition and paramodulation?

This is late for you, but probably might be of help to others. I myself had asked this question and I wrote the summary of my findings to the acl2-help mailing list on 8 and 9 September 2013: https://utlists.utexas.edu/sympa/arc/acl2-help/2013-09/msg00005.html
https://utlists.utexas.edu/sympa/arc/acl2-help/2013-09/msg00006.html

Disclaimer: What follows is my understanding of the subject and I am not an expert.

I assume you are familiar with what is called
term-rewriting. Informally its a very simple notion where one uses a
rule to reduce or rewrite another expression.

A rewrite rule is usually a universally quantified formula of the form
$C \Rightarrow l=r$, where $C$ is a formula and $l$ and $r$ are terms. One says that a
rule $R$ applies to another formula $\Phi$, if there is some subterm $s$ of
$\Phi$ and some substitution $\sigma$ such that $l\sigma = s$ (this process
is called matching) and $C\sigma$ is true. If $R$ applies to $\Phi$, then
one can rewrite $\Phi$ to $\Phi\sigma$. Demodulation is another name for
unconditional term-rewriting, i.e., $C$ is simply true and so $R$ is just
$l=r$.

Rewriting involves matching,i.e., one-way unification.
Paramodulation involves full unification.  Moreover, the equality
($l=r$) that is used to perform paramodulation, is not directed, either
lhs or rhs can be unified with a subterm in the other literal
paramodulated upon.

Superposition is a restriction of Paramodulation. In particular, the
rules of inference named 'Superposition (left/right)' are restrictions
of "ordered" paramodulation, i.e., the paramodulation rule is applied
only when equation $l=r$ (to be instantiated/unified) satisfies certain
properties: $l >> r$ for a given reduction order $>>$, $l=r$ is maximal (wrt
$>>$) in the clause etc etc.

Here are some fundamental papers that are interesting from a historical point of view.

[1] The concept of demodulation in theorem proving - L Wos, GA
Robinson, DF Carson, L Shalla - Journal of the ACM (JACM), 1967

[2] Handbook of Logic and Automated Reasoning - J Harrison.

[3] Paramodulation and theorem-proving in first-order theories with
equality- G Robinson, L Wos - Machine intelligence, 1969

[4] Rewrite-based equational theorem proving with selection and
simplification - L Bachmair, H Ganzinger - Journal of Logic and
Computation, 1994

[5] Simple word problems in universal algebras - DE Knuth, PB Bendix -
Computational problems in abstract algebra 1970

[6] A superposition oriented theorem prover - L Fribourg - Theoretical
Computer Science, 1985 - Elsevier

[7] Completion without failure - L Bachmair, N Dershowitz, DA Plaisted -1989


How are Bayesian Nets, Hidden Markov Chains, Conditional Random Fields and Neural Nets related?

No, needing training has nothing to do with unsupervised/supervised. Supervised learners need labels, unsupervised learners do not (they do things like clustering, density estimation, dimensionality reduction). In fact you can use all of them for supervised and unsupervised learning, except maybe CRFs, since an unsupervised CRF would more likely be referred to as a markov random field (MRF) since there is no conditional per se. Someone might argue with me on this last point and I probably wouldn't argue back.
No, CRFs have undirected edges. ANNs can have undirected edges also (for example autoencodes with tied weigths). ANNs don't need have a probabilistic interpretation.
Sometimes it would be obvious. For example, if I'm doing Image Denoising I'm not going to use an HMM. Other times it will depend on things like what the practitioner has experience with, what works well in this domain, or a myriad of other factors.
Out of all the thing on your list ANNs are the only one that need not have a probabilistic interpretation. Furthermore, the techniques used for training ANNs normally are of a different flavor than what is used for other methods. That being said there are lots of classes that will focus on other types of models and likely not discuss ANNs, for example Probabilistic Graphical Models, Generalized Linear Models, etc.


How can you check if a 2SAT problem has a bad loop

The implication graph is constructed using the following ingredients:

Vertices: One vertex for each variable, and one for each negation of a variable
Edges: For each clause {x,y}, create an edge from -x to y and one edge from -y to x

The following should be the implication graph corresponding to your set of clauses:

A bad loop (I'm guessing this is what you want, haven't encountered that wording before) is a loop in the implication graph that contains both a variable and its negation (i.e. both x and -x). Clearly there is no such loop in your case.

Why "bad loop"? It is because each edge represents an implication that necessarily must hold for your 2-SAT instance. For example, the first clause reads "a or b". If this clause is to be satisfied, then we must have one of the two variables true. So:

If a isn't true (i.e. -a is true), then b must be true, which is the implication -a$\to$b
If b isn't true (i.e. -b is true), then a must be true, which is the implication -b$\to$a

In a "bad cycle", you have a cycle of such implications, so that x$\to$...$\to$-x$\to$...$\to$x. Such a cycle of implications can never be satisfied, otherwise x would be both true and false at the same time. So if you have any bad cycles, the 2-SAT formula is unsatisfiable!

In fact, a 2-SAT formula is unsatisfiable when, and only when, there is a bad cycle in the implication graph. So your formula is, by the absence of bad loops, satisfiable. The proof of satisfiability in the case of no bad loops even yields a poly-time algorithm to find a satisfying assignment (which is great : ) )

So how to assign values to the variables and satisfy your (or any) 2-SAT formula? I'll refer to https://en.wikipedia.org/wiki/2-satisfiability#Strongly_connected_components for the algorithm, but be warned that you need to know of the concept of "strongly connected component" to fully understand the algorithm.


How to Optimise the following algorithm? maximum good value of an element in an array

Depending on the input values the following strategy might work:
keep an array $C$ of $10^6$ elements where $C[i]$ will store the number of times number $i$ appears in the elements of the input array that have already been processed.

Initially $C$ is identically 0, then you consider the elements $A_i$ one at a time. When you are processing the $A_i$ you can compute the "good value" by taking the sum of all $C[k A_i]$ for $k=1,\dots,\lfloor 10^6 / A_i \rfloor$. Then, increment $C[A_i]$.

At the end of the process return the maximum sum.

A more refined strategy is that of handling separately small and large values of $A_i$. If $A_i \ge 1000$ then the above algorithm check at most $10^3$ entries in $C$.
If $A_i < 1000$ then you can find the number of its multiples by checking and keeping track of how many of the input elements seen so far are divisible by the numbers between $1$ and $1000$. This also requires $\approx 1000$ operations. So you'll be performing $\approx 2 \cdot 10^5 \cdot 10^3$ operations as opposed to $10^{10}$ of your algorithm.

An even better strategy is to keep an array $D$ where $D[n]=j$ means that  $j$ of the numbers seen so far have $n$ a divisor. Since the number of divisors grows slowly (as $O(\log n / \log \log n)$, and it is always at most $240$ for your values) this strategy will only increment a few values per input number (less than 14 on average, assuming an uniform input distribution. See here for a plot of the number of divisors of the first $10^5$ integers).
The leaves you with a number of operations of the order of $10^6$ to $10^7$.

The problem is now that of enumerating, for each number $n$, its divisors efficiently. But you can just do this as a preprocessing step by multiplying each $i=1,\dots,10^6$ by consecutive integers $k$ until it exceeds $10^6$. For each such $k$ add  $i$ to the list of divisors of $k \cdot i$. This could even be done once-for-all and hardcoded in your algorithm.


Book CS:APP, using bit set and bit clear

If $z=\mathrm{bis}(x,m)$ then
$$
z_i = \begin{cases}
x_i & \text{if } m_i = 0, \\
1 & \text{otherwise}.
\end{cases}
$$
This is exactly bitwise OR.
If $z=\mathrm{bic}(x,m)$ then
$$
z_i = \begin{cases}
x_i & \text{if } m_i = 0, \\
0 & \text{otherwise}.
\end{cases}
$$
This is bitwise AND of $x$ and the bitwise complement of $m$.
In order to see how $\mathrm{bis}(\mathrm{bic}(x,y),\mathrm{bic}(y,x))$ computes bitwise XOR, we just need to compute the truth table:
$$
\begin{array}{c|c|c|c|c}
x & y & \mathrm{bic}(x,y) & \mathrm{bic}(y,x) & \mathrm{bis}(\mathrm{bic}(x,y),\mathrm{bic}(y,x)) \\\hline
0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 \\
1 & 1 & 0 & 0 & 0
\end{array}
$$
Another way of seeing this is replacing $\mathrm{bis}(x,y)$ with $x \lor y$ (read: $x$ or $y$) and $\mathrm{bic}(x,y)$ with $x \land \lnot y$) (read: $x$ and not $y$):
$$
(x \land \lnot y) \lor (\lnot x \land y),
$$
which is one of the standard formulas for XOR. In C, it would look as follows: (x & ~ y) | (~x & y).


You are correct: it's $\Theta(n)$ in the worst case. Suppose you're looking for something that's no bigger than the smallest value in a max-heap. The max-heap property (that the value of every node is at least as big as everything in the subtree below it) gives you no useful information and you must check both subtrees of every node.


Bits of memory address used for page number?

Your virtual address is of size $64$ bits. This means your system can address $2^{64}$ bytes. Each virtual address your system generates points to a byte of memory.

Your system has a page size of $2^7$ bytes. Operating systems like to group bunches of memory bytes together into what is called a page. Think about each page as a block of memory that contains many bytes.

We have a virtual space of $2^{64}$ bytes that we need to page. How many blocks of memory (of size $2^7$ bytes) can we fit in this address space (of size $2^{64}$ bytes) ? $2^{64}$ / $2^7$ = $2^{57}$ blocks (or pages).

We need $2^{57}$ pages. Therefore, there would be $57$ bits required to address each page that we have.

Now, remember each page has $2^7$ bytes. If your OS were looking for a specific byte, the first $57$ bits in the address would have the page number it wants. Then, the last $7$ bits would address a byte on that page. The number of bits used to address a byte in a page is called the offset.

So, $7$ bits for the offset, $57$ bits for the page number. Together, they equal a $64$ bit virtual address.


Algorithm playing modification of "Hey, That's My Fish!" game

You are probably supposed to use exhaustive search, that is, recursively try all possible moves. They made it easier by restricting the number of possible moves. One optimization which might be needed is storing board positions and the number of fish obtained from them, so that you don't analyze twice the same sub-position; there might be too many of them to store, and in that case you should only store "large" positions. Alpha-beta pruning could also be useful perhaps, but if you haven't learned about that, there is probably no need to use it.


Compiler instructions to sync core caches: are they really needed?

This is very simple actually, and has nothing to do with hardware whatsoever. If you have a variable

static bool b;

and some code

b = true;
dosomething();
b = false;
dosomethingelse();
b = true;

If the compiler can figure out that dosomething() and dosomethingelse() don't read or write b, then the compiler is not required to generate code for the assignments to b, except the last one.

With the book's subtitle "Write robust, concurrent, and parallel applications" this is quite worrying.


counting binary, with moving position (turing machine)

Noting that every increment starts from the lowest significant bit (LSB). Consider each increment operation this way: starting from LSB, move towards MSB, flipping 1's to 0's until a 0 is encountered. Flip it to 1 and move back to LSB, stop. It is then clear that the total move distance is just double the number of flips.


Say that a stack frame only contains total functions: could the maximum stack size be statically determined?

No. That would allow you to determine the runtime of any given (recursive) program (assuming it always terminates), but that is not a computable problem.


You cannot avoid enumerating all elements. Consider the following two posets, with elements $x,y,z_1,\ldots,z_n$:

$x,y < z_i$ for all $i$.
$x,y < z_i$ for all $i < n$, and $z_n < x,y$.

The first poset has two minima, and second only one. You can only tell the difference by enumerating over all elements.

If there is a unique minimal element $z$, then $z < w$ for all other elements $w$ (since there is a minimal element below any given element). This allows us to use the following constant space algorithm, which assumes that the elements of the poset are $z_1,\ldots,z_n$:

Initialize $t \gets z_1$.
For $i=2,\ldots,n$: if $z_i < t$, let $t \gets z_i$.
Go over all elements again, and verify that $t \leq z_i$ for all of them.

There is a unique minimal element iff the verification succeeds.


How to decide whether a real life problem can be dealt with by computers?

The way we decide is we try to solve it and see if we are successful; or we look to see whether someone else has solved it (e.g., in the research literature).

Usually the question doesn't really make sense, as it is not well-defined what it means to "solve" or "deal with" a problem.  It's not like in mathematics, where it is a crisp black-and-white.  Instead, one may need to measure how well computer systems can address the problem, in what contexts they do or don't suffice, what their strengths and limitations may be, and so on.

Normally, the way we assess all of this is through experiments, not mathematics: we try techniques and evaluate how well they work empirically, and see what we can learn from that.


Exploring and interpolating a function using machine-learning?

I would look into the field of "optimal experimental design" in bayesian inverse problems, particularly the recent work of Alen Alexandrian.

http://arxiv.org/abs/1410.5899

http://www4.ncsu.edu/~aalexan3/research.html

Essentially, one has an inner inverse problem for approximating the function based on point measurements of derived quantities, hosted within an outer optimization problem for choosing the points based on minimizing a combination of the error and the variance.

Furthermore, you don't need to do a full inner-outer solve procedure. Rather, you can use the KKT conditions for the inner problem as the constraint for the outer problem, and formulate a "meta" KKT system for the combined problem.

It is formulated in the language of PDE-constrained inverse problems, but would also apply to simpler situations like your problem (the "PDE" becomes the identity matrix..)


Number of triangles in an undirected graph

I'm assuming that the graph is given as an adjacency matrix. The trivial algorithm for counting triangles goes over all triples of vertices $u,v,w$ and checks whether $\{u,v,w\}$ is a triangle, for a total running time of $\Theta(N^3)$. This can be improved using matrix multiplication: if $A$ is the adjacency matrix, then the number of triangles can be extracted from $\operatorname{Tr} A^3$, taking into account the number of vertices and edges in the graph (details left to you). This takes time $O(n^\omega)$, where $\omega$ is the exponent of matrix multiplication.


NP-hard proof: Polynomial time reduction

Yes and no. To cut a long story short, it's enough that the pre-image of $f$ is NP-hard.

Intuitively, the point of NP-hardness is that, if you had an efficient algorithm for an NP-hard problem, then you would have an efficient algorithm for all problems in NP. Let's suppose you've come up with a new problem, Triomphe's Problem (TP), and you want to prove that it's NP-hard. You need to show that every problem in NP can be reduced to TP.  There are, on the face of it, two ways of doing this.

The direct way. Show that there is a polynomial-time computable function $f$ with the following property: for any nondeterministic polynomial-time Turing machine $M$ and every input $x$, $f(M,x)$ is an instance of TP and $f(M,x)$ is a "yes" instance of TP if, and only if, $M$ accepts $x$. This is how Cook proved NP-completeness of Boolean satisfiability and how Fagin proved NP-completeness of evaluation of formulas of existential second-order logic.

The indirect way. Show that there is an NP-hard problem $P$ and a polynomial-time computable function $f$ with the following property: for any instance $x$ of $P$, $f(x)$ is an instance of TP and it is a "yes" instance of TP if, and only if, $p$ is a "yes" instance of $P$. This is how just about every other NP-hard problem, apart from the two listed above, was proven NP-hard.

The indirect way works through a chain of reductions.  We need to establish that every problem in NP can be reduced to TP. So, we start with our nondeterministic polynomial-time Turing machine $M$ and its input $x$.  We convert that to an instance of Boolean satisfiability. Then we convert that into, say, an instance of 3-SAT. Then we convert that into, say, an instance of 3-colourability. Then maybe we convert that into an instance of $P$ and, finally, convert that into an instance of our fictional problem TP. Because all of these reductions work for every instance of the problem, we have a reduction from our generic NP problem to TP.

Both in theory and in practice, that is how reductions are done: you need to translate every instance of the problem. But we don't actually need that much. Look at the first step of the chain of reductions in the previous paragraph. We started with any Turing machine at all, and we converted it into a Boolean formula. Without looking closer, all we know is that we've produced some Boolean formula, and we don't know any details about it. However, looking more closely at the reduction, we see that the formula is in conjunctive normal form (CNF) (or that the proof can easily be modified to make it so). For the next step, converting to 3-CNF, the definition of reductions tells us that we have to be able to translate every Boolean formula into one in 3-CNF, but we know we don't need to do that much. It would suffice to translate only the formulas that are already in conjunctive normal form, because those are the only ones that the translation from Turing machines will produce. And that's actually what the standard proof does.

Normally, when a new problem is proven NP-hard, a full reduction is given from some known NP-hard problem to the new problem, which translates all instances. However, in principal, you could get away with a reduction that does less than that, as long as it covers enough instances to establish the chain back to the generic Turing machine $M$ and its input $x$. To give another example, 3-colourability is NP-hard because of a standard reduction from 3-SAT. You could prove a new problem to be NP-hard by a reduction that only translates the instances of 3-colourability that could be produced by that reduction from 3-SAT. This works because 3-colourability is already NP-hard when its input is restricted to be from the class of graphs that can arise from the reduction from 3-SAT.

However, if you're a student doing exercises and exam questions, I'd recommend that you always produce reductions that map the whole problem, rather than just a subset of it.


If $T(1)\le 6$ and $T(2)\le 12$, we can show that $T(n)\le 6n$ by induction.

$$T(n) = T(n/2) + T(n/3) + n \le 6(n/2)+ 6(n/3)+n= 6n.$$

More generally, let $c\gt6$ be a constant such that $T(1)\le c$ and $T(2)\le 2c$,  then we can prove routinely that $T(n)\le cn$. Although it might seem unbelievable to you, it is true that
$$T(n)=O(n).$$

Intuitively, since $\dfrac12+\dfrac13\lt1$, the terms $T(n/2)$ and $T(n/3)$ is not big enough to lift $n$ to a power of $n$ of a larger exponent.

There is nothing wrong in your application of Akra-Bazzi method, which tells us that $T(n)=\Theta(n)$.


There is a general cryptographic theory of provably secure hash functions. There are several inequivalent notions of security. Hash functions are a cryptographic primitive, and the goal of cryptography is to explore relations between different primitives – can one primitive be constructed using the other.

All of this, however, has no relevance on hash functions practically used, for various reasons. Practically, hash functions come in two flavors: cryptographically secure and not cryptographically secure. There isn't really any theory regarding the construction of both types. Cryptographically secure hash functions are constructed according to various and changing heuristic principles, but their strength lies in the community trying to break them and failing. Non-secure hash functions have other properties, and successful one have emerged from practice.

Don't construct your own hash function. If you attempt to construct a cryptographically secure hash function, you will probably fail unless you're an expert. Constructing a non-secure hash function is less harmful, but still, existing ones are probably better than one you would come up with.

If you want a hash function with a particular integer range $[a,b]$ (as indicated in the comments), there are two basic options:

If your function doesn't need to be cryptographically secure, you can use the formula $h \pmod{b-a+1} + a$, where $h$ is a general-purpose hash function. The range of $h$ should be large compared to $b-a+1$, unless $b-a+1$ happens to divide the range of $h$.
If your function does need to be cryptographically secure, you have to be more careful. In that case I suggest you ask a question on the dedicated crypto stackexchange site.


The variable $ob$ is an object reference variable of type $A$.  As such, it can only reference those attributes and methods defined in $A$.  The attribute $e$ is defined in $B$, not $A$, so $ob$ cannot reference $e$.  It is okay to reference $add$ because it is defined in $A$, even though it is overridden in $B$.


Busy Beaver problem - Proof by contradiction

I know it took me a few reads before a grasped what it was saying, so maybe if we build $Q$ in a different and (much) more verbose way, it'll help.

So let's start by assuming a Turing machine $\Sigma$ exist which, given a line of n 1's on an otherwise blank tape, can compute the busy beaver of n ($\Sigma(n)$) and write's out that many 1's on the tape.  Now, this Turing machine has some number of states, which we will say is a.

Next, let's assume that another Turing machine, $+1$ which runs to the end of a line of 1's and adds one more 1 to that line.  This Turing machine has some number of states, which we will say is b.

Next, let's assume that even another Turing machine exists, called $D$, short for Double.  Given a tape with some number of 1's on it, it doubles the number of 1's on the tape.  And let's say that it has some number of states c.

We now have three Turing machines, each with a, b, and c states respectively.  So now let us define a number k, such that k = a + b + c.

Now let us build another Turing machine, $K$, short of Write K.  $K$ will print out k 1's on a blank state, and have k states.  A simple machine, where each state writes 1, moves to the next position on the tape, and then goes to the next state.

So now let's combine all our machines into one big machine.

We start with $K$, then go to $D$, then $\Sigma$, and finally $+1$.  Let's call it $Q$.  Now, to find the number of states $Q$ has, you have to add up the members.  In order, that is k + c + a + b.  And given that a + b + c = k, this mean that $Q$ has 2k states.

Now, let's run $Q$ and see what happens.

We start with a blank tape.  Then $K$ runs and puts k 1's on the tape.  Next, $D$ doubles this tape in size, so it now has 2k 1's on the tape.  Next, $\Sigma$ runs and computes $\Sigma(2k)$ and prints that many 1's on the tape (replacing the 2k 1's).  Finally, $+1$ runs and adds one extra 1 on the end of the line.  So there are now $\Sigma(2k) + 1$ 1's on the tape.

Now, this means that $Q$, a Turing machine with 2k states, just wrote $\Sigma(2k) + 1$ 1's on a tape, which is impossible because the maximum number of 1's possible to write on a tape, given 2k states (and not counting cases that never halt), is $\Sigma(2k)$.  Contradiction (and thus $Q$ cannot exist, and namely $\Sigma$ inside of $Q$ cannot exist).

In short, $Q$ has 2k states because we purposefully built it to have exactly 2k states to aid in creating the contradiction.


How can I calculate the effective bandwidth of a memory system?

An N-bit wide data bus can transfer N bits in one clock cycle, after a latency of d clock cycles (or t seconds).

I think the above sentence has everything you'd need to solve this problem.


How to schedule n jobs that come at different times on 1 machine (each taking a different time to complete the task)?

This problem lends itself to Mixed Integer Programming. The trick is to consider that there are multiple versions of each job for each machine, and you have to cover each job once.

So you can have $c_{j,m}$ as the indicator variables that say if a job is assigned to a machine. You have to introduce a constraint that says $$\sum_m  c_{j,m} \geq 1.$$


Can quantum computer become perfect chess player?

I've already answered essentially this question, on Chess Stack Exchange. The executive summary is that chess doesn't seem particularly well-suited to quantum computation's strengths so there's no particular reason to believe that a quantum computer would be any better at it than a classical one.


How to schedule events optimally given when the events are available?

I assume that by "optimally" you mean using the least number of periods. Thirst thing is that you can renumerate the dictionary such that there are no gaps in available periods, so:

$$
\text{Event 1} \rightarrow\ [1, 2, 10]\\
\text{Event 2} \rightarrow\ [3, 5, 11, 12]\\
$$

becomes

$$
\text{Event 1} \rightarrow\ [1, 2, 5]\\
\text{Event 2} \rightarrow\ [3, 4, 6, 7]\\
$$

So now the largest number on the right side is not greater then the sum of sizes of lists on the right side. Assume that, there are $n$ events and sum of sizes of lists on the right side is $m$. Now to check if there is a solution, which uses only first $i$ periods we can reduce the lists to the numbers smaller or equal to $i$, so for $i=4$ this example will change to:
$$
\text{Event 1} \rightarrow\ [1, 2]\\
\text{Event 2} \rightarrow\ [3, 4]\\
$$
Now to check if there is a solution for given $i$ we can create bipartite graph with events on one side, periods on the other side and edges between event $e$ and period $p$ if $e$ is available during $p$. If there is matching of size equal to $n$ in this graph then we can schedule events using only first $i$ periods. If we find smallest $i$ with such property then we have a solution to our original problem. It's easy to see that if there is such matching for $i$ then there is also for $i+1$, so we can use binary search to find smallest $i$. This solution will work in time $O(m\sqrt{n+m}\log{m})$ where $O(m\sqrt{n+m})$ comes from finding matching and $O(\log{m})$ comes from binary search.


Selah, instead of asking for more references and definitions, you can just use the fact that for the n values n ≤ k < 2n, we have $1/{2n} ≤ 1/k ≤ 1/n$. So the sum of $1/k$ for n ≤ k < 2n is between 1/2 and 1.

Not nearly as nice as Yuval's result, but it should be more than good enough to solve your problem.


Find the minimum count of elements summing to a pre-defined sum

This can be solved in $O(n \lg n)$ time by computing prefix sums and then using divide-and-conquer.

Step 1. Compute the prefix sums $p_0,p_1,\dots,p_n$, where we define $p_i = a_1 + a_2 + \dots + a_i$.  Throw away the $a_i$'s.  Now the problem becomes: count how many index-pairs $i,j$ there are where $0 \le i \le j \le n$ and $p_j = p_i + s$.

Step 2. Solve this problem using divide-and-conquer.  First, count the number of solutions where $0 \le i \le j \le n/2$ (recursively).  Second, count the number of solutions where $n/2 < i \le j \le n$ (recursively).  Third, count the number of solutions where $0 \le i \le n/2$ and $n/2 < j \le n$.  This third step can be done in $O(n)$ time (expected running time).  Since this is your exercise, I'll let you work out how: it's not too hard.

The total running time satisfies the recurrence $T(n) = 2 T(n/2) + O(n)$, so this yields a $O(n \lg n)$ time solution.