How does cache partitioning prevent covert/side-channel attacks?

Most L2 (and L3) caches are indexed with the physical (not virtual) address modulo a power of two that is larger than the page size. This allows different physical address colors to map to different indices, isolating replacement decisions (i.e., only accesses from the same color can cause a cache miss). The added latency from cache misses (often measured in the attacker program) can reveal the index of cache line that was replaced.

Partitioning also avoids capacity use measurement, which provides less specific information (compared to used index).

Color-based partitioning would typically not avoid bandwidth use measurement in a shared cache under default hardware configurations (which tend to be demand-based rather than fair-share; strict fair-share decreases throughput under variable demand).

For L1 caches, isolation based on physical page color would have no effect in caches that are virtually indexed. L1 sharing is more easily restricted to a temporal granularity that would not leak a significant amount of information.

It might be noted that performance isolation for multi-use systems (where different uses may give different values to different resources and even to the predictability of resource availability) is the primary/original motivation for Intel's Cache Allocation Technology ("ensuring consistent performance and prioritizing important interactive applications"), but such features can help narrow side-channels for security-oriented isolation.


What are the definitions of syntax and semantics?

To beging with, the expression "formal language" may refer to formally
defined sets of string as considered in the theory of automata and
formal languages. I shall write that "Formal Language" with capital
first letters. But "formal language" may also refer to some kind of
language that is intended for expressing meaning, but is precisely
defined mathematically. I shall rather call it formally defined language.

A first remark is that formally defined languages are similar to natural
languages (vernacular), in the sense that both are used to convey
meaning through representations of that meaning.

This is the fundamental issue. We have to convey meaning, to others,
or to ourselves (when we take notes). Meaning can concern all sorts of
things, some finite, some infinite, possibly about strange domains of
human imaginations, such as real numbers, or the set of all sets.
But we can always do that only through representation. The
representation may be a linear sequence of symbols. It may also be a
spatially organized collection of symbols. It may be drawings, or data
structures in a computer, or sound stream, or gestures. It is
physical.

To answer the question in a nutshell, and in a very general way: the
organisation of the physical representation of discourse is syntax,
while semantics is the meaning conveyed, and the way it is derived
into, or from, the representation.

A major characteristic of syntax is that syntactic representations
are finite: they convey a finite amount of information. This is true
of pictures that can de digitized with finite precision to convey what
they are supposed to convey, But the best example is one of the most
common form of representation: the written text. If one takes all the
symbols used for writing as digits in a proper base, any written text
may be read an integer number, which is a finite object. This does not
prevent the discourse from being about infinite objects, or whatever
else, including ghosts, leprechauns, the Zeta function, the turtle
that carries the planet on its back and the last Sunday before the
Big-Bang. And, this does not forbid having an infinite number of
representations, of sentences of the language.

But how is syntax connected to semantics? How do we associate a
meaning with physical representation. The most basic way is to
associate a specific meaning to specific representations, and learn
these associations. This is basically how ideographic writing gets
started. But it has limitation: you can define only a finite number of
meanings in this way. An important aspect of language is to
be able to handle unbounded number of meaning by associating in an
organized way the representation of elementary meanings.

So syntax is not just a collection of elementary representations, but
also a collection of rules to associate them to make more complex
representations. Elementary representations correspond to elementary
meanings, and rules associating them indicate how the simpler meanings
can be composed to make more complex meanings.

A simple example is the way formally defined languages are
specified in mathematics (I am simplifying somewhat, skipping over
some technical issues, parsing technology for example). The syntax is
defined as a set of string over an alphabet. This set is often defined
by a context-free grammar. that provides rules to create strings on
the alphabet. The rules also associate strctures to strings: the
parse-trees. The definition of semantics associate a value (of
whatever domain) to the elements of the alphabet, and associate
operations on these values to the rules of the grammar. This define a
homomorphism from the set of string in the context-free syntax to the
set of values in the semantic domain. (Note that, sometimes, the syntax is directly defined as a set of trees.)

So we have an infinite set (the syntax Formal Language) of finite
representations (string or sentences of the formal language) which has
a finite definition/description (the Context-Free grammar). The
semantics is defined by specifying a domain of values, and both the
domain and the values in it may be finite or infinite entities. For example
a mathematical text, though finite, can talk about real numbers which
are a continuously infinite set of infinite entities (in the sens that
most reals do not have a finite description). Furthermore, the mapping
is finitely defined, by associating a function with each grammar rule.
A rule composes subpart of the text into a larger text, and the
associated function composes the meaning of these subparts into a
meaning for the larger text.

Not all kinds of Formal Languages may be appropriate for syntax
definition. They must provide some structure to the language strings
that can be used to define the semantics mapping. Besides context-free languages and grammars, there are
many other kinds of Formal Languages and Formal Language Definitions
that can provide structure for syntax strings (tree adjoining grammars
for example). They are mostly used in computational linguistics for
natural language. Other mechanisms, such as attributes or features on
grammar symbols, can be added both to specify the strings of the
languages or the semantics mapping (but it may be disputed whether
they should be considered syntax or semantics).

However, as written earlier, syntax need not be composed of strings of
symbols. Other structured representations can be considered, such as
graphs, or sound stream. An interesting example is abstract syntax
trees that can represent programs of a programming language as tree
structures. Some programming systems and development environments
actually consider the abstract syntax tree (AST) as the primary
representation of programs, and provide tools to create programs
represented directly as AST, possibly without ever producing a string
representation in some cases. The language Lisp was probably the first to do that.
This is also very frequent in proof systems and other symbolic
computation systems that manipulate mathematical formulae, which
remain represented by tree structures, or even other data types.

This shows that different representation systems, different syntaxes,
may be used to represent the same semantic structures. Actually, when
these representations can easily be translated into each other, while
preserving semantic meaning, they are often considered the same
language. In other words, the same language may have multiple
syntactic representations, including multiple string syntaxes.  But
the semantics preserving intertranslatability shows that these
different representations are structurally similar. Another obvious
example is natural language, that can exist as text or as speech.

Conversely, given a syntax, it is possible to combine it with
different semantic interpretations, i.e. different semantic mappings.


Hint 1: As $A$ is regular, it is recognized by finite automata. Try to modify this automata to make it recognize $B$.

Hint 2: Skipping "deleted" symbols might be handled by adding $\epsilon$ - transitions to the original automata in a proper way.


You need to show that there is an index $n_0\geq 0$ and some $c>0$ such that $f(n) \leq c\cdot n^2$, for all $n\geq n_0$. Here you can take $c=2$.

This leaves you with showing that $n \log_2(n) + log_2(n) \leq n^2$, for high enough values of $n$.

This holds because $\lim_{n\to\infty}\frac{log_2(n)}{n} = 0$.


This problem can be cast into a familiar form: it's an example of what is known as a 0-1 linear programming problem. You have a set of variables $v_1, v_2, \dots v_n$ subject to constraints of the form $m\le a_1v_1+a_2v_2+\cdots +a_nv_n\le M$. In your particular problem, we also have $a_i \in \{0, 1\}$. You are looking for any feasible solutions, namely tuples $(v_1, \dots, v_n)$ which satisfy all the constraints.

For example, suppose we have
$$
M = \left( \begin{array}{cccc}
         0 & 0 & 1 & 0\\
         1 & 1 & 0 & 1\\
         1 & 1 & 1 & 0\\
         0 & 1 & 1 & 1
       \end{array} \right), \quad{\text{and}}\quad
z= \left( \begin{array}{c}
     0\\1\\0\\1
   \end{array}\right)
$$
then you want
$$
v= \left( \begin{array}{c}
     a\\b\\c\\d
   \end{array}\right)
$$
such that $Mv$ will be, in binary (with the lower-order bit unspecified)
$$
Mv=\left(\begin{array}{c}
c \\ a+b+d \\ a + b + c \\ b + c + d
\end{array}\right)
=\left(\begin{array}{c}
\mathtt{0\_}\\ \mathtt{1\_}\\ \mathtt{0\_}\\ \mathtt{1\_}
\end{array}\right)
$$
From this we have the constraints
$$
\begin{array}{c}
0\le a, b, c, d\le 1\\
2\le a + b + d\le 3\\
0\le a + b + c\le 1\\
2\le b + c + d\le 3
\end{array}
$$
and you want to find $a, b, c, d$ such that all the constraints are simultaneously satisfied.
We've moved into 0-1 LP land because there are established procedures for solving problems like this, though sadly there's nowhere near enough room in this post to introduce them, so you'll have to do the legwork yourself. Be aware that problems like this are very compute-intensive (by which I mean NP-hard) and as far as I know you're not going to get anything like an elegant formulation of the form "This can be solved if and only if $z$ is of the form ..."

By the way, the example I used does indeed have a solution, $v$, and in this particular case is unique, though in general you'll have several solutions (if there are any at all).


Simulate the concatenation of two log-space programs in log-space

The idea here is that we can't compute the output of the first algorithm completely because it can take more than logarithmic space (it can be polynomially large). But we don't need to if we are intelligent. What we can do is simulate the second algorithm and produce the bits it needs from the output of the first algorithm on-line. In other words, we will simulate the second machine, when it wants to read bit $i$ from its input, i.e. the bit $i$ from the output of the first machine, we stop the simulation of the second machine, simulate the first and count (but not store) the bits it outputs until it outputs the $i$th bit at which time we can stop the simulation of the first machine and continue with the simulation of the second machine as we now have the value of what it wanted to read.


Does Quicksort always have quadratic runtime if you choose a maximum element as pivot?

The worst case complexity for quicksort is $\Theta(n^2)$. This is achieved by picking pivots that divide the set such that one group has only a single member. With a bad pivot picking algorithm, this can easily be achieved by picking one end of a sorted set. Your assumption is correct.


Research in Graph Theory versus Graph Algorithms

Question 1

I would say that the two areas are definitely not identical, however there is a huge overlap. Partly it depends on where you draw some very fuzzy lines. Let's start with:

Graph Theory is about the properties of graphs as mathematical objects
Graph Algorithms as an area of research is about solving computational problems that are represented using graphs.

Of course graph theory is unsurprisingly very useful in developing graph algorithms, and graph algorithms can answer questions in graph theory. Indeed, as you have obviously noticed, many problems in Graph Theory can be cast as computational problems, and answered by giving an algorithm (in a sense this is an aspect of the Curry-Howard Correspondence), so especially at the introductory level, there is little more than the style of presentation that separates them.

Just to make things even more confusing, most researchers in one field have at least some interest and experience in the other, but there are a couple of points where we can draw certain lines of distinction:

Graph theory (as a field) will happily deal with infinite graphs, which are not so interesting from an algorithmic perspective.
Graph theorists will tend to be more interested in existential statements ("the chromatic number of a class of graphs is at most blah"), whereas graph algorithms people will be looking for the best algorithm to solve a problem ("how do we compute the actual value of the chromatic number as quickly as possible?").
Graph algorithms includes/overlaps with the application and tailoring of graph algorithms to solve problems that aren't really about graphs (e.g. developing a good algorithm to cluster protein interaction networks), which a graph theorist would be uninterested in (at least as a graph theorist).

Question 2

If you have access to university subscriptions or similar (this is no way exhaustive):

Journal of Graph Theory
SIAM Journal on Discrete Mathematics
Journal of Combinatorial Theory: Series B
Discrete Applied Mathematics
Journal of Graph Algorithms and Applications

To muddy things further, many of these include examples of both pure graph theory and graph algorithms.

A couple of lists for further exploration:

A list of graph theory journals
For unrelated reasons, John Lamp has several lists that have interesting journals in there, but you'll have to do some keyword searching: Pure Mathematics, Applied Mathematics, Theoretical Computer Science

There is the arXiv preprint server, which has preprint versions of research papers, but again, you'll have to spend a small amount of time to explore and find something you want (it's more set up for finding a paper you already know is there).

Question 3

This question cannot really be answered objectively. It depends entirely on things that you have no way of knowing (i.e. the future), and I have no way of knowing (how good the people are at your university, what opportunities you will gain or lose by taking that internship).

If you want my subjective general opinion, I would say yes. Graph theory is an important part of mathematics and computer science (I personally contend they're not different things anyway), and versatility and breadth of knowledge are important characteristics of a good researcher, even if you later decide you have no intention of being a graph theorist - it's not going to stop you from being able to do complex analysis or topology.

Again, this is about whether an arbitrary student would benefit from doing work in graphs (algorithms or theory) - you personally may be in a particular situation where it would not be beneficial, and we can't answer that here. For example, if taking the internship means that you don't get to do the internship in Category Theory that is actually the thing you want to do, then this could set you back. Early in a research career it is difficult to escape a particular path, without going back to step one. Later on, it's easier to transition, but for better or worse there's period effectively like apprenticeship where you can't easily jump to any job you're interested in, but that's a question for Academia.SE.


Grammar in formal languages versus programming language theory

Programming language theory usually does not care about parsing: it does not address this problem. So when you have this grammar in programming language theory:

e ::= 1 | e e

it does mean the same thing as in formal language theory but programming language theory really only talks about the generated syntax trees. However it is much better to have a non-ambiguous grammar. For example in the lambda-calculus, the grammar is written like this:

$$M ::= x ∣ λx.M ∣ M M$$

and things like $L M N$ have several meanings as you pointed out. Usually the author/context makes it non-ambiguous like this: he says the application case is left-associative, authorizes parentheses, or sometimes changes $MM$ into $(MM)$ and says "we omit parentheses when unnecessary" or several other ways.

In conclusion it may generates the same string for different trees but programming language theory only applies on the latter.


How to correctly contract an edge in a network?

The very next sentence (!) of Orlin's paper says

  We point out that the contraction operation may lead to the creation of multiple arcs, i.e., several arcs with the same head and tale nodes.

In some contexts, you might want to replace multiple arcs between the same two nodes with a single arc whose weight (or capacity or whatever it's being called) is the sum of the weights of the original arcs; in other contexts, it might make more sense to keep them separate.  Orlin is keeping them separate.

For example, if the arcs represent trading relationships between companies, it makes sense to merge the arcs: if companies $A$ and $B$ both sell to $C$ and $A$ and $B$ merge, it makes more sense to say that $C$ is a customer of the new company once, with a single arc, than to say that it's a customer twice, by having two arcs. On the other hand, if arcs represent roads between towns and two towns merge, it makes sense to keep the arcs separate: if there's a road from each of $A$ and $B$ to $C$ and $A$ and $B$ merge, there are still two roads from the merged town to $C$.

So, contracting the arc $(1,2)$ into a new node $6$ has the following effects:

it converts the arc $(1,2)$ into the loop $(6,6)$;
it converts the arc $(2,1)$ into a second copy of the loop $(6,6)$;
replaces the arcs $(0,1)$ and $(0.2)$ with two copies of $(0,6)$;


Alright we've to remove the unreachable state that is $Q$, for which we have to follow these steps:

Initialize a set $R$ containing the initial state.
Create a set $M$ which'll contain the states which are reachable from states in $R$ in single transition.
Perform $R = R\cup M$.
Repeat from step 2 until $R$ stops getting new states.
Remove states from complement of $R$.

Create set $R = \{q_1\}$.

Calculate $M$ by finding states which can be reached from $\{q_1\} = \{P\}$.

Perform $R = R\cup M:\{q_1\}\cup\{P\}=\{q_1, P\}$.

Calculate $M$ again from $\{q_1,P\}=\{P\}$.

Perform $R=R\cup M:\{q_1,P\}\cup\{P\}=\{q_1,P\}$. $R$ has no new states to add. Therefore, we'll remove states from complement of $R: \{q_1, P, Q\} - \{q_1,P\}=\{Q\}$. The FSM will be:

I learned this here http://www.cs.um.edu.mt/gordon.pace/Research/Software/Relic/Transformations/FSA/remove-unreachable.html


What is the point of (Compactness theorem in the) Overspill principle?

The theorem says that when a sentence has arbitrarily large (finite) models, then it also has infinite models.

The antecedent of the theorem:

  $\phi$ is a sentence of predicate logic such that for any natural
  number $n \geq 1$, there is a model of $\phi$ with at least $n$
  elements.

is equivalent to saying that there are infinitely many different models,
but it does not state that any of these models are infinite in size.

In fact, it would be clearer to use:

  $\phi$ is a sentence of predicate logic such that for any natural
  number $n \geq 1$, there is a finite model of $\phi$ with at least $n$
  elements.

This is not exactly the same statement, but as an antecedent within this theorem, it is equivalent.

The consequent:

  $\phi$ has a model with infinitely many elements.

does not say anything about how many different models there are - it just says something about the size of at least one of them.

To see that the truth of this theorem doesn't simply follow from its structure, consider the following statement, which has the same structure:

  Let $\phi$ be a sentence of predicate logic such that for any natural
  number $n \geq 1$, there is an equivalent sentence of predicate logic with at least $n$ elements. Then there is an equivalent sentence with infinitely many elements.

Is this a theorem, too?  No, this statement is false, for the simple reason that all sentences of predicate logic have finitely many elements by definition.


return a key of a node with maximum value within a range of keys in B+ tree

Augment each node to contain the key of the node with maximum value, among all nodes that are underneath it (among all of its descendants).  You can easily maintain/update this augmented information each time you modify the tree, by using the fact that the maximum for any node can be recomputed using just the information in its direct children (you don't need to look at its grandchildren etc.).

Now any range can be expressed as the union of $O(\log n)$ subtrees.  In other words, you can find $O(\log n)$ nodes such that their descendants cover the range exactly.  So, the max value of any node within that range can be obtained by looking at the values in those nodes, and taking the max of them.  In this way each query can be answered in $O(\log n)$ time.


You haven't quite defined your problem, so let me answer a more concrete one: when can there be an evenly spaced solution. I assume that by "evenly spaced" you mean that all the spaces are the same, and that there must be hooks and the first and last positions. If the space is $s$, then we must have
$$ L = 1 + (s+1)(H-1), $$
since the string is of the form $H(o^sH)^{H-1}$. This is possible if and only if $H-1$ divides $L-1$, in which case the spacing is
$$
 s = \frac{L-1}{H-1} - 1.
$$
In your case, 14 doesn't divide 37, so an even spacing is impossible.


A clairvoyant algorithm is a (usually hypothetical) algorithm that can look into the future to guarantee that it makes the best possible decisions. The typical application is in so-called "online" problems, where the input must be processed as it arrives, before the whole input is known, or in other situations where an algorithm must act based on incomplete knowledge. The point is that the hypothetical clairvoyant algorithm would be able to make perfect decisions so you can use that as a benchmark to judge your real algorithm for the problem.

The example given in the page you link is for page replacement algorithms. You need to swap some page of virtual memory out to disk and, of course, you'd rather not swap out a page that's just about to be accessed. The hypothetical clairvoyant algorithm would know which page will not be needed for the longest time and will swap that one out; a real algorithm would have to estimate, for example by assuming that a page that has not been used for a long time will not be used again in the near future.

Now, you can do a comparison.  Suppose you have enough physical memory to hold 1000 pages and you have a process that cycles through 1001 pages accessing them in the order 1, 2, ..., 1000, 1001, 1, 2, ...  The real algorithm performs terribly in this case: when page 1001 is requested, it swaps out page 1, which is the very next page to be requested. In fact, the page the process requests is never in memory. A clairvoyant algorithm might, for example, keep pages 1–999 in memory all the time and swap in pages 1000 and 1001 as needed, giving page faults only 0.2% of the time.

Other applications of this sort of idea are things like process scheduling (in most cases, a real algorithm doesn't know what demands a process will make, so it must guess) and various auction schemes where the auctioneer uses the early bids to figure out what people are prepared to pay for an item, before selling it to the next highest bidder.  The classic pop-science application is in deciding who you should marry which, for some reason, academics call the Secretary Problem. The clairvoyant algorithm would be to magically know who your ideal partner is and marry them; the best you can do in practice is to spend a few years dating and dumping people and then marry the next person you meet who is better than all the ones you dumped.  (This carries the risk that you'll meet your ideal partner during the date-and-dump phase and then never meet anyone else that good; math doesn't always make your life better.)


Can I assume every clause of 3SAT has one positive literal?

No, you can't.
If each clause has at least one positive literal, then, by assigning TRUE to all variables, one gets all clauses satisfied.


CLRS Exercise 24.3-4 - Confirm Output of a Program Claiming to Implement Dijkstra's Algorithm

So I'm going to go out on a limb with this one and attempt to answer my own question. It seems that when running the algorithm given in the solution, say that there are many vertices for which $v.\pi$ and $v.d$ is incorrect (call this set of vertices, $V_i$ and $V_i \subseteq V$).

When we run the algorithm, if there are at least some vertices for which $v.\pi$ and $v.d$ is correct (call this set of vertices $V_c$ and $V_c \subseteq V$), the algorithm is guaranteed to detect at some point that there is an incorrect vertex $u$, such that $u \in V_i$.

But, it may return a false positive for some vertex, $u$ (again such that $u \in V_i$) if all of the parents of $u$, WLOG say a parent($u$), is called $p$, so $p$ also has incorrect distance and predecessor values, thus $p.\pi$ and $p.d$ is incorrect for a parent, $p$ of $u$ therefore $p \in V_i$ but eventually we will come across some vertex $u \in V_i$ such that when we look at the incoming edges to $u$, we will find that $u.\pi$ is incorrect, since at least $1$ of the parents of $u$, call it $p' \in V_c$ has correct distance and predecessor values, and we would return false/something that indicates we have found the vertex $u$ such that $u.\pi$ and $u.d$ are incorrect.

In the case of all $v \in V$ outputted by the Professor's program are incorrect, we'd easily find a $v$ such that $s \xrightarrow{} v$ and see that $v.\pi$ or $v.d$ is incorrect.

I believe this explains how the algorithm works... Someone please correct me where/if I'm wrong. Thanks.


A Context free grammer is one in which LHS of atleast one of the productions is free from any terminal symbols (context).
According to your production rule,it is clearly CFG.


Are there criteria that will make: $A \subseteq B$, $A$ unrecognizable imply $B$ unrecognizable?

The condition about $B$ can be transformed into a condition about $B\setminus A$, as follows.
If $B\setminus A$ is decidable, then $B$ is unrecognizable.
Indeed, if you could recognize $B$, you could determine whether a word $w$ is in $B\setminus A$. If it is, then it's not in $A$, otherwise it is. So $A$ would be recognizable as well.

Note, however, that the converse does not work - there are sets $C,D$ such that $C\cap D=\emptyset$, both $C$ and $D$ are not recognizable, and $C\cup D$ is unrecognizable as well.


Psedu-polynomial Time : Conflict with the definition of input size

First, the size of the input is the number of bits required to represent the input. When talking about complexity, we often assume that our input is represented as some bit-string.

For the knapsack case, when we have $x= \Theta(N\log S)$ and running time $\Theta(N\cdot2^{\log S})$, we say that the algorithm is exponential in the size of the input, as $\Theta(N\cdot2^{\log S}) = \Theta(N\cdot2^{(N\log S)/N}) = \Theta(N\cdot 2^{x/N})$. For fixed $N$, the latter formula is exponential in $x$. However, when we fix $S$ instead, the formula is linear in $x$ (which then is $\Theta(N)$). Since we often do not assume bounds on $S$ in the general knapsack problem, we can consider the formula exponential.

A similar analysis can be done for the case of counting sort.

So, in summary, although the length of the input is indeed the full encoding of the input (usually as a bit-string), this doesn't change the fact that if you encode a number $N$ in your input $x$ with $\log N$ bits alongside perhaps other things, $\Theta(N)$ will be exponential in $x$.

Finally, let me make some comments on pseudo-polynomial time. Personally, I think that both the definition on Wikipedia and in the SO post lack generality and clarity. I prefer to take the definition alluded to in this answer: An algorithm is pseudo-polynomial if it is polynomial only in a specific encoding, such as unary. This implies the definition given on Wikipedia, as the unary encoding on the number $N$ has size $N$, but the binary encoding has size $\log N$.

I prefer the definition above, as it shows a bit more what is going on: it matters what sort of input encoding we use whether our algorithm is polynomial, which explains the name. The fact that this occurs precisely when we have a number in the input is a nice corollary, but hides a bit too much and is probably a reason for your confusion.


Information loss of a 9-input majority gate

Let me first explain what the entropy loss is for a gate like AND. The input entropy is $2h(1/2) = 2$ (where $h(p) = -p\log_2p-(1-p)\log_2(1-p)$), while the output entropy is $h(1/4)$ (since the probability that the output is $1$ is $1/4$). Therefore the entropy loss is $2 - h(1/4) \approx 1.189$.

In the case of recursive majority, the output is uniform, so the output entropy is $1$. The input entropy, in contrast, is $9$, and so the entropy loss is $9-1=8$.


What is the specific name for basic data types?

They are called primitive data types.

(This is a pretty basic find in Wikipedia's article on data types.)


Online set cover variant? Routing of requests

In general, there are two approaches you can take here:

Empirical evaluation. Pick a realistic workload (a data set with a bunch of scenarios, where each scenario is a sequence of requests).  Use this as a benchmark.  Test each candidate heuristic on that benchmark, and see which one performs the best on this benchmark.

Theoretical analysis. Alternatively, you can try to prove a theorem about the competitive ratio of these two heuristics.  That may be very difficult.

I suspect it's going to be a lot more feasible -- and potentially more useful -- to take the former approach.  It does require you to have a dataset of representative requests.

I can suggest another plausible heuristic.  Given a graph, you can find use bottleneck shortest paths to find the best path from $s$ to $t$, where "best" is measured by the number of slots in the least empty node that's visited along that path.  The larger that number, the better (it means there exists a path with plenty of spare capacity).  So, one possible heuristic is to choose whichever path reduces this number the least.

There are probably many other heuristics you could come up with.  I suggest brainstorming a few, then evaluating them empirically using the approach listed above.


Halting problem reducing to the blank tape halting problem

Short version first: The typical reduction for this problem assumes that we can decide the blank tape halting problem, but this gives us a way to decide the halting problem (which in this situation we already know is undecidable). It does so by taking the input to the normal halting problem, and making a new TM that always starts with a blank tape, and writes the normal halting problem input to the tape as its first set of steps - so if this modified machine halts when starting with an empty tape, the normal halting problem input halts with whatever its input. Therefore we can't decide the blank tape halting problem.

Now, with some formality.

We have two languages:

$HALT_{TM} = \{\langle M,w\rangle \mid M \text{ is a Turing Machine that halts on input } w\}$
$BLANKHALT_{TM} = \{\langle M\rangle \mid M \text{ is a Turing Machine that halts on input } \varepsilon\}$

  Lemma. $BLANKHALT_{TM}$ is undecidable.

Proof.
We already know that $HALT_{TM}$ is undecidable. We show that $BLANKHALT_{TM}$ is also undecidable by reduction from $HALT_{TM}$ (i.e. we show that if we could decide $BLANKHALT_{TM}$, we could decide $HALT_{TM}$).

Assume (for contradiction) that $BLANKHALT_{TM}$ is decidable, and we therefore have a Turing Machine $T$ that decides it. Using $T$, we can construct a Turing Machine $R$ that decides $HALT_{TM}$ where $R$ is:

On input $\langle M, w\rangle$

Construct a new Turing Machine $M_{w}$ that does the following:

Starts with a blank tape (or rejects otherwise).
Write $w$ to its tape.
Moves its head back to the start, and from here just copies what $M$ does.

Run $T(\langle M_{w}\rangle)$, if $T$ accepts $\langle M_{w}\rangle$, accept, otherwise reject.

But this would decide $HALT_{TM}$, which we know is undecidable, so $T$ can't exist and $BLANKHALT_{TM}$ is also undecidable. $\Box$

Again, note precisely what each machine is doing:

$R$ decides $HALT_{TM}$, with input $\langle M,w\rangle$.
$T$ decides $BLANKHALT_{TM}$ by assumption.
$M_{w}$ is basically a wrapper for the input $M$ given to $R$ that starts with a blank tape, but as its first actions writes the other input $w$ to its tape - so it starts with a blank tape, but it really does what $M$ does on input $w$.

Note that we "run" neither $M$ nor $M_{w}$, we just construct their descriptions, and give those as input strings to $R$ and $T$ respectively.


Is it possible to calculate the propagation delay if only the length of the link is known & not the speed at which a bit travels into the link?

I believe your approach is right. Since we don't have any other information given. Then this means the packets are getting consumed at the rate same as link bandwidth. So Avg packet waiting must be 0.


How does coarser lock granularity cause an decrease in time required to acquire and release locks?

Fine-grained locks need to be acquired and released more often.  Coarse-grained locks don't need to be acquired or released as often.  Therefore, you're both right.

For instance, suppose you're about to do a big, long operation.  With a coarse-grained lock, you'd grab the lock before beginning the operation, hold it throughout, and release it at the end -- a total of one acquisition & release.  With a fine-grained lock, you might grab and release the lock at multiple times, at each sub-step.  Also, you might grab and release multiple locks, because the operation touches multiple resources, each with its own lock.

That said, coarse-grained locks can cause other problems.  They can cause deadlock, or they can cause one thread to be stalled waiting for the other thread to perform a long operation.  Therefore, they can limit your ability to take advantage of parallelism.

Ultimately, you usually need to balance these competing considerations.


Early Deadline First (EDF) scheduling in real-time systems feasibility test proof

I might be too focus on the algebra. I believe I only need to argue or proof a scenario that would give the least density of the system that will fail to meet a deadline.
As shown in the figure below, all tasks start at the same time with same period and deadline. For each of period, each task only have time slot D=D1=D2=...=Dn to execute. In other words, they share exactly the same time slot to execute. If density > 1 then obviously schedule will fail. If the below system has a density of $1^+$(greater than 1 by the smallest amount), then any changes on Di or Pi will only increase the density of the system or make the system feasible.


You're overthinking. $T(\lfloor\frac{n}{2})\rfloor \ge 1 \Rightarrow T(n) = T(\lfloor\frac{n}{2})\rfloor + n > n \Rightarrow T(n) = \Omega(n)$


Fine-grained versioning of entities in programming languages

The Unison programming language is based around two simple fundamental ideas:

code is immutable
code is content-addressed

What does that mean? Code being immutable means just what it sounds like: since code is immutable, it will never change. You can only ever add new code to the system, but you can never change or remove existing code.
Code being content-addressed means that all addresses (references) are based on the content of the code, not any names. And computing the content address is invariant under α-conversion by using De Bruijn indices in the code database.
This has some interesting implications: since you only reference functions, types, modules, variables, etc. by their content address and the content address is based on a name-less representation, you can rename anything and everything to your heart's desire, and never break any code. Also, since all references are based on content, and content never changes (remember, code is immutable), code that works at one time, will always continue to work until all eternity.
This poses an interesting question, though: How do you fix bugs?
One part of the puzzle is how names are handled in Unison. I wrote above that Unison's code model is based on addresses, but that doesn't mean that there are no names at all. It would be very annoying to write code like
#1uekd4 = #lle0xy #5q17cp #h8i067

instead of
fullName = concat firstName lastName

and having to remember all the addresses.
Instead, Unison also stores a mapping of names to addresses in its code database. This is similar to how Unix filesystems work: in a Unix filesystem, a file has no name, it only has a file serial number. However, there are directories (which are also files) which map names to serial numbers (which could point to regular files or to another directory). Also, Git works in a similar fashion. There are blobs, which only have content, and there are trees which assign names to addresses (which could be blobs or trees).
If you want to fix a bug, then you create a new version of the buggy function which doesn't have the bug. But all existing code still references the old function! (Remember, all addressing is based on content, not names.) So, you have to update every function that references the old function. And you have to update every function that references a function that references the old function.
Obviously, this gets tedious really fast. This is where names come in. After updating the function (really creating a new function), you also update the name database (really creating a new database) with a version where the name now points to the new, fixed, function.
Unison will notice this update, and will automatically propagate this name change through all existing functions. So, it will automatically update all functions that reference the buggy function to now reference the fixed function, then it will update the functions which reference the functions it just updated, and so on.
Where "automatically propagate" can mean one of two things:

If the new function has the same type as the old one, Unison will automatically apply the update.
If the new function has an incompatible type, Unison will create a to-do list with all the places that need to be changed.

Once the change is made, regardless of whether it was done aumatically or it required manual intervention, this change is recorded in a patch and becomes part of the code database as well. So, anybody else who pulls in the changes will benefit from the fact that you already resolved the issue and they can pull in the patch as well.
Bringing this to your example: since the content of time::UnixTime hasn't changed, it still has the same address, and since code is immutable, it is guaranteed that this address will refer to this type for all eternity. And since both logger and totp only refer to it by its address, which will never change, they, too, will continue to work unchanged for all eternity.


In order to prove $A = B$, It is sufficient to prove that $A'B = 0$ and $A' + B = 1$. Try to think of why this should be the case intuitively. In case you are unable to understand, then think of $A$ and $B$ as sets, Boolean $+$ operation as set union operation and Boolean $.$ operation as set intersection operation.

Therefore, take $A = (X+Y)'$ and $B = X'Y'$.

So, $A'B = (X+Y)X'Y' = XX'Y' + YX'Y' = 0$.

Also, $A' + B = X + Y + X'Y' = 1$.

(Use the property $A + BC = (A + B )(A + C)$ for simplifying above expression.


What are the key differences between Spiking Neural Network and Deep Learning

Short answer:

Strictly speaking, "Deep" and "Spiking" refer to two different aspects of a neural network:  "Spiking" refers to the activation of individual neurons, while "Deep" refers to the overall network architecture. Thus in principle there is nothing contradictory about a spiking, deep neural network (in fact, the brain is arguably such a system).

However, in practice the current approaches to DL and SNN don't work well together.  Specifically, Deep Learning as currently practiced typically relies on a differentiable activation function and thus doesn't handle discrete spike trains well.

Further details:

Real neurons communicate via discrete spikes of voltage.  When building hardware, spiking has some advantages in power consumption, and you can route spikes like data packets (Address Event Representation or AER) to emulate the connectivity found in the brain.  However, spiking is a noisy process;  generally a single spike doesn't mean much, so it is common in software to abstract away the spiking details and model a single scalar spike rate. This simplifies a lot of things , especially if your goal is machine learning and not biological modeling.

The key idea of Deep Learning is to have multiple layers of neurons, with each layer learning increasingly-complex features based on the previous layer.  For example, in a vision setting, the lowest level learns simple patterns like lines and edges, the next layer may learn compositions of the lines and edges (corners and curves), the next layer may learn simple shapes, and so on up the hierarchy.  Upper levels then learn complex categories (people, cats, cars) or even specific instances (your boss, your cat, the batmobile). One advantage of this is that the lowest-level features are generic enough to apply to lots of situations while the upper levels can get very specific.

The canonical way to train spiking networks is some form of Spike Timing Dependent Plasticity (STDP), which locally reinforces connections based on correlated activity. The canonical way to train a Deep Neural Network is some form of gradient descent back-propagation, which adjusts all weights based on the global behavior of the network. Gradient descent has problems with non-differentiable activation functions (like discrete stochastic spikes).

If you don't care about learning, it should be easier to combine the approaches. One could presumably take a pre-trained deep network and implement just the feed-forward part (no further learning) as a spiking neural net (perhaps to put it on a chip).  The resulting chip would not learn from new data but should implement whatever function the original network had been trained to do.


Construct a recursion tree. The sum of the costs per level is less then $c\cdot n$, for $c$ being the constant in the $O(n)$. The tree has roughly $n\log_4 n$ full levels, and the deepest level is $n \log_{4/3} n$. So, summing up over all levels gives $T(n)=O(n\log n)$.


Is it decidable whether a Turing machine M will reach state q on input s?

Do we ever take into consideration a word with infinite length during such analysis?

Never say never. However, it is a safe bet that in the course of your undergraduate or even graduate study you can assume that all inputs to Turing machines are finite.

Here is a more formal restatement/understanding of the problem in the question.

  $$\begin{align}\text{TRIPLE }=&\{\langle M, q, w\rangle: M\text{ is a Turing machine. }\\
&q\text{ is one of the states of }M. \\
&w\text{ is a word over the input alphabet of }M.\}\\
\text{REACH }=&\{\langle M, q, w\rangle\in\text{TRIPLE}: M\text{ will reach }q\text{ on input }w. \}\end{align}$$
  Is $\text{REACH}$ decidable? (the problem of state reachability)

Assume $\text{REACH}$ is decidable. By definition, there is a Turing machine $T$, which, given a Turing machine $M$, its state $q$ and an input word $w$ as its input, it will accept the input if and only if $M$ will reach state $q$ on input $w$.

Recall that $A_{\text{TM}} = \{\langle M,w\rangle : M \text{ is a TM and }M\text{ accepts }w\}$. Construct a new Turing machine $T'$ such that given input $\langle M, w\rangle$ where $M$ is a TM and $w$ is an input for $M$, $T'$ will change the input to $w'=\langle M, q_{\text{accept}}, w\rangle$ where $q_{\text{accept}}$ is the unique accept state of $M$, and then simulate $T$ on input $w'$. We see that $T'$ is a decider for $A_{\text{TM}}$.

I would believe you have learned that $A_{\text{TM}}$ is not decidable. That contradiction shows that our assumption must be wrong, which means this problem of state reachability cannot be decidable.

(In case that the Turing machines defined for you could have multiple accept states, $T'$ could replace all accept states in $M$ with a unique accept state at first.)

Reader can also take a look at a more intuitive and less notation-cluttered but less rigorous version of this answer here, which is just the first version of this answer.


Counting the solutions to a restricted 0-1 knapsack problem

There are almost-matching lower and upper bounds for the running time of the best algorithm for this problem, considered as a function of $n$.  In particular, we can prove that the complexity is $\Omega(n)$ and $O(\text{poly}(n))$, when considered only as a function of $n$.

For the upper bound, there's an algorithm whose running time is polynomial in $n$.  Without loss of generality we can take $k \le n$ (for terms where $i>n$ contribute nothing to the sum).  Also you can compute ${n \choose i}$ in time polynomial in $n$.  Therefore, the whole sum can be evaluated in time polynomial in $n$.  In other words, it's solvable in pseudo-polytime.

The size of the output can be as large as $2^n$ (e.g., where $k=n$), so the output can take $\Theta(n)$ bits to represent.  This is exponential in the size of the input.  Thus, any algorithm for the problem must have worst-case running time at least $\Omega(n)$.


Cognitive Computing vs Artificial Intelligence?

A brief definition would be:

  Cognitive computing is the simulation of human thought processes in a computerized model.

more detailed explanation:

  Cognitive computing involves self-learning systems that use data mining, pattern recognition and natural language processing to mimic the way the human brain works. The goal of cognitive computing is to create automated IT systems that are capable of solving problems without requiring human assistance.

Cognitive computing is used in A.I. applications. Therefore I think it can be concluded that Cognitive Computing is a subset of Artificial Intelligence.

Cognitive Computing systems may include the following ostensible characteristics:

Natural Language Processing
Machine Learning
Algorithms that learn and adapt
Vision-based sensing and image recognition
Spatial and contextual awareness
Reasoning and decision automation
Sophisticated pattern recognition
Neural Networks
Semantic Understanding
Noise Filtering
Common Sense
Robotic Control
Emotional Intelligence

So basically, you can say that a cognitive computing system might be trained by neural networks.

Sources:

http://www.cognitivecomputingforum.com/
http://whatis.techtarget.com/definition/cognitive-computing


How does a wifi password encrypt data using WEP and WPA?

WEP uses the stream cipher $RC4$ for confidentiality and the CRC-32 checksum for integrity. All data frames sent by a router in a WEP protected network are encrypted. When a router sends a packet, the following steps are executed.

The router picks a $24$-bit value called the initialization vector $IV$.
A new $IV$ is used for every packet.
The $IV$ is prepended to the key (password you enter) and
forms the per packet key $K$.
A CRC32 checksum of the payload is produced and appended to the
payload. This checksum is called an Integrity Check value ($ICV$).
The per packet key $K$ is fed into the $RC4$ stream cipher to produce a
key stream $X$ of the length of the payload with checksum.
The plaintext with the checksum is XORed with the key stream and
forms the cipher text of the packet.
The cipher text, the $IV$ and some additional header fields are used
to build a packet, which is now sent to the receiver.

Weaknesses of WEP and why to choose WPA

An $IV$ size of $24$-bits provides only $16$ million different key streams for a given WEP key. If the $IV$ is reused, the key stream for a given $IV$ is found and hence an attacker can decrypt subsequent packets that were encrypted with the same $IV$ even without knowing the WEP key.

Since there are only $16$ million $IV$ values, how the $IV$ is chosen makes a big difference in the attacks based on $IV$. As explained above, some implementations choose $IV$s randomly and some are assigned sequentially. With a randomly chosen $IV$, there is a $50\%$ chance of reuse after less than $5000$ packets and if assigned sequentially, collisions are inevitable if the values are re-initialized.

WEP’s integrity check field is implemented as a CRC-32 checksum, which is part of the encrypted payload of the packet. However, CRC-32 is linear, which means that it is possible to compute the bit difference of two CRCs based on the bit difference of the messages over which they are taken. In other words, flipping bit ‘$n$’ in the message results in a deterministic set of bits in the CRC that must be flipped to produce a correct checksum on the modified message. An attacker can therefore change a bit in an encrypted message and know which bit of the encrypted $ICV$ will change as a result.


Are there minimum criteria for a programming language being Turing complete?

I always though that $\mu$-recursive functions nailed it. Here is what defines the whole set of computable functions; it is the smallest set of functions containing resp. closed against:

The constant $0$ function
The successor function
Selecting parameters
Function composition
Primitive Recursion
The $\mu$-operator (look for the smallest $x$ such that...)

Check above link for details; you see that it makes for a very compact programming language. It is also horrible to program in -- no free lunch. If you drop any of those, you will lose full power, so it is a minimal set of axioms.

You can translate those quite literally into basic syntactical elements for WHILE programs, namely

The constant 0
Incrementation _ + 1
Variable access x
Program/statement concatenation _; _
Countdown loops for ( x to 0 ) do _ end
While loops while ( x != 0 ) do _ end


Introductory books on nature sciences behind bioinformatics

As a previous response stated, it is not an absolute requirement that you study biology in order to do bioinformatics.  However, if you wish to have a background understanding of the foundational concepts such as genes, RNA, DNA, etc. then a good introductory biology book should provide everything that you need.

Molecular biology is not the kind of topic that one can simply dive into the middle of, though. Therefore, in order to understand it, you need to do some introductory reading.   The best book is one that has enough detail without assuming that you wish to become a biologist.

I suggest that you look at Collins Outline of College Biology. Reading chapters 2-5 and 12-15, should give you basic information you desire.  Another choice is Schaum's Outline of Biology, Third Edition, chapters 2-4 and 7-10.   Both books cost less than $20.00 and are easy to understand.  Hope this helps.


Designing CFG that accepts # of 1's = # of 2's + # of 3's

Given a grammar for $\{ w \in \{0,1\}^* : |w|_0 = |w|_1 \}$, you can obtain a grammar for $\{ w \in \{1,2,3\}^* : |w|_2+|w|_3 = |w|_1 \}$ by replacing $0$ in the first grammar by a non-terminal $Z$, and adding the productions $Z\to 2 \mid 3$.


Difference between decision tree and rule based reasoner

Decision tree classifiers could be easily converted to rule based classifiers in data mining and vice Versa. please have a look at "Introduction to Data Mining", chapters 4 and 5.

Usually it depends on the data characteristics, how to choose between these two methods and which of the mentioned methods give you smaller classification errors.


If there is no Hamiltonian path in a DAG then there are at least two different Topological sorts

Let's call two vertices $u$ and $v$ comparable if there is an oriented path from $u$ to $v$ or from $v$ to $u$, and call them incomparable otherwise. Now let's prove that if there is no Hamiltonian path in DAG then there exist two incomparable vertices. Let's use a proof by contradiction and prove instead that if all vertices in a given DAG are pairwise comparable then there exists a Hamiltonian path. Let's prove it by induction by a number of vertices. Obviously, this statement is true for $1$ and $2$ vertex DAGs. Not let's consider an arbitrary DAG where all vertices are pairwise comparable. There is exactly one vertex with zero in-degree in such graph. Let's call this zero in-degree vertex $a$. What is more, if you remove vertex $a$ from your DAG, the remaining subgraph will also be a DAG where every two vertices are comparable. By induction assumption you can build a Hamiltonian path $P$ in this subgraph. Let's call the first vertex of this Hamiltonian path $v$. Then there is an edge $(a, v)$ in the original DAG. Indeed, let's assume that such edge does not exist. But we know that there is a path from $a$ to $v$ (because they are comparable and there is no in-edges to $a$). Let $b$ be the second vertex of the path from $a$ to $v$. Then there is a path from $b$ to $v$, but there is also a path from $v$ to $b$ (by construction of $v$). Hence, there is a cycle in a considered graph. Contradiction. So there is an edge $(a, v)$ and $v$ is a start vertex of some Hamiltonian path $P$ in the subgraph without $a$. Thus $\{a\} \cup P$ is a Hamiltionian path in the original graph.
So in every DAG without a Hamiltonian path there is at least 2 incomparable vertices. Thus you can get two different topological sortings just by swapping the numerations on dfs subtrees of these two vertices.


In my opinion, this may be best approached as a sequence tagging problem, similar to part-of-speech tagging or named entity recognition. (So, this would be the seq2seq option, rather than regular classification). For example, think about it as trying to decide for each token, whether it is the start of a new verse or not.
The advantage of the sequence tagging approach compared to regular classification (at least when using some kind of neural architecture) is that you do not have to predetermine the length of the context taken into account for each distinct tagging decision.
To be clear, the classification approach (e.g, take 20 tokens to the left and 20 tokens to the right and decide whether the middle token is a verse boundary) is also viable, but the sequence tagging approach seems the more natural choice for me.
A final thought on the problem: Are you sure that (any kind of) classification/tagging approach is the right place to start? You may also want to think about this in terms of an alignment problem where you try to figure out which sentences from message edition correspondent to the ones in the NRSV version. Verse segmentation then comes for free. Alignment problems have been studied extensively in statistical machine translation.


Understanding the union of an undecidable language with a finite or decidable language

If $L$ is undedidable and $A$ is finite, then $L \cup A$ is undecidable.
To see this notice that, given $w \in \Sigma^*$:
$$w \in L \iff (w \in L \cap A) \; \vee \; (w \in L \cup A \;\wedge\; w\not\in A).$$
Since $A$ if finite both $A$ and $L \cap A$ (which is also finite) are decidable. That is, we can test whether $w \in L \cap A$ and whether $w \not\in A$.
If $L \cup A$ were decidable the above formula would then imply that $L$ must also be decidable, a contradiction.
If $L$ is undedidable and $B$ is decidable, then $L \cup B$ might or might not be undecidable, depending on $B$.
An example in which $L \cup B$ is undecidable is the one discussed before: let $B$ be any finite language, e.g., $B=\emptyset$.
An example in which $L \cup B$ is decidable is $B=\Sigma^*$ since $L \cup B = \Sigma^*$.


An online algorithm to find the Pareto frontier elements

In two dimensions, each update can be done in $O(\lg n)$ time, by using a balanced binary tree data structure.  But when you are working in a high-dimensional space, I don't know of any efficient solution.

Let me describe an efficient algorithm for the 2D case.  Let $F$ denote the set of points in the Pareto frontier.  Store $F$ in a balanced binary tree, using the $x$-coordinate of each point as its key.  Note that when you sort $F$ by increasing $x$-coordinate, they'll also be sorted by decreasing $y$-coordinate.

Now, given a new point $(x_q,y_q)$, you can check efficiently whether it is Pareto-dominated by any element of $F$.  Find the first element of $F$ to the right of $(x_q,y_q)$ (i.e., the element $(x,y) \in F$ such that $x \ge x_q$ and $x$ is minimal); then checking whether it dominates $(x_q,y_q)$.

Also, given a new point $(x_q,y_q)$, you can efficiently find whether it Pareto-dominates any element of $F$.  In particular, you can find indices $i,j$ such that the points $(x_i,y_i),(x_{i+1},y_{i+1}),\dots,(x_j,y_j)$ of $F$ are all Pareto-dominated by $(x_q,y_q)$ (assuming that the points of $F$ have been ordered by $x$-coordinate, Pareto-dominated points will be in a consecutive interval).  Here's how.  Find the first element of $F$ to the left of $(x_q,y_q)$ (i.e., the element $(x_j,y_j) \in F$ such that $x_j \le x_q$ and $x_j$ is as large as possible), and check whether $(x_q,y_q)$ dominates it.  If yes, find the smallest index $i$ such that $i<j$ (so $x_i<x_j$) and $y_i \le y_q$.  Both of these steps can be done in $O(\lg n)$ time.  (Finding $i$ can be done in $O(\lg n)$ time by treating the tree as branching on the $y$-coordinate of points, and taking advantage of the fact that the points of $F$ are sorted by decreasing $y$-coordinate.)

Now this tell us what to do.  If $(x_q,y_q)$ is dominated by some point of $F$, then don't add it to $F$; you're done.  Alternatively, if $(x_q,y_q)$ dominate points $i..j$ of $F$, then you need to delete those points from $F$ and add $(x_q,y_q)$ into $F$.  This can be done in $O(\lg n)$ time, by noting that any interval of consecutive indices can be expressed as the union of $O(\lg n)$ subtrees of the binary tree (roughly speaking, you work with the siblings of the nodes along the path from $i$ to the root, and the same for the path from $j$ to the root); you can delete each subtree in $O(1)$ time.  This lets us delete an entire range of consecutive points in $F$ in $O(\lg n)$ time, no matter how large the range is.  For details, see Delete a consecutive range of leaves from a binary tree.

All of this can be done in $O(\lg n)$ time, using a balanced binary tree data structure.

This works in 2 dimensions (i.e., 2-tuples).  In higher dimensions, the problem gets much harder.  You can find references to the literature, with techniques for higher dimensions, at How to find a subset of potentially maximal vectors (of numbers) in a set of vectors; but I'm afraid that in high dimensions, all the known algorithms are likely to be fairly slow (they have a factor that is something like $O((\lg n)^{d-1})$ where $d$ is the number of dimensions).


The law of excluded middle and decidability

You are conflating computationally decidable with logically decidable.

A (closed) formula, $\varphi$, is logically decidable iff $\vdash\varphi$ or $\vdash\neg\varphi$, i.e. if $\varphi$ is derivable or $\neg\varphi$ is derivable (with respect to some given logical system). This is the sense we mean when we say something like the Continuum Hypothesis is undecidable.

A unary predicate on naturals, $P$, is computationally decidable iff there is a Turing machine $M$ which terminates on all inputs with output either $1$ or $0$, and $P(n)$ holds if and only if $M$ terminates with output $1$ on input $n$. This is the sense we mean when we say something like the Halting Problem is undecidable.

(There are other ways we use the term "decidable" such as when we say a(n entire) logic or theory is decidable which, more or less, means something like $\vdash\varphi_n$ is computationally decidable where $\varphi_n$ is a formula encoded by $n$ via some suitable surjective encoding.)

Assuming the Law of the Excluded Middle (LEM) doesn't automatically make every unary predicate on the naturals computationally decidable. Indeed, usually computational decidability is formulated within a classical logic where LEM holds.

Intuitionistic logic connects logical decidability to LEM because it satisfies the disjunction property which states $\vdash\varphi\lor\psi$ if and only if $\vdash\varphi$ or $\vdash\psi$. This means $\varphi$ being logically decidable is equivalent to $\vdash\varphi\lor\neg\varphi$.

Now, there's a model of intuitionistic first-order logic such that $\forall n:\mathbb N.P(n)\lor\neg P(n)$ is modeled by a computable function taking a natural and producing a witness of (the interpretation of) either $P(n)$ or $\neg P(n)$. This means (the interpretation of) $\forall n:\mathbb N.P(n)\lor\neg P(n)$ is true in this model if and only if $P$ is computationally decidable. LEM, in this context, would imply the statement that all decision problems are computationally decidable. LEM is, of course, false in this model. Therefore, if you assume LEM, this interpretation ceases to be a model.

The fact that certain formulas are derivable in intuitionistic first-order logic implies that corresponding predicates are computationally decidable. This implication itself, though, is demonstrated in the meta-logic where the definition of "computationally decidable" resides, and this is usually a classical logic.

For an informal (meta-)logic in which you define "computationally decidable", it's up to you whether you want to accept non-constructive proofs or not. However, there is a big difference between proving a formula in constructive logic which can be interpreted as a witness to the computational decidability of a predicate, and proving a formula which states in the constructive logic that a predicate is computationally decidable which would involve constructive definitions of Turing machine and so forth. As an analogy, the circle as a (higher inductive) type in Homotopy Type Theory is very different from the construction of cirles, e.g. $\mathbb R/\mathbb Z$ within Homotopy Type Theory. As a more contrived example, let's say I interpret the theory of abelian groups into $3\mathbb Z$, i.e. $1$ is interpreted as $3$. Then it is still the case that the "internal" notion of $3$, i.e. $1+1+1$, is different from $1$.


Number of possible search paths when searching in BST

If looking for the key 60 we reach a number $K$ less than 60, we go right (where the larger numbers are) and we never meet numbers less than $K$. That argument can be repeated, so the numbers 10, 20, 40, 50 must occur along the search in that order.

Similarly, if looking for the key 60 we reach a number $K$ larger than 60, we go leftt (where the smaller numbers are) and we never meet numbers larger than $K$. Hence the numbers 90, 80, 70 must occur along the search in that order.

The sequences 10, 20, 30, 40, 50 and 90, 80, 70 can then be shuffled together, as long as their subsequences keep intact. Thus we can have 10, 20, 40, 50, 90, 80, 70, but also 10, 20, 90, 30, 40, 80, 70, 50.

We now can compute the number, choosing the position of large and small numbers. See the comment by Aryabhata. We have two sequences of 4 and 3 numbers. How many ways can I shuffle them? In the final 7 positions I have to choose 3 positions for the larger numbers (and the remaining 4 for the smaller numbers). I can choose these in $7 \choose 3$ ways. After fixing these positions we know the full sequence. E.g., my first example has positions S S S S L L L the second has S S L S L L S.

You ask for a generalization. Always the $x$ numbers less than the number found, and the $y$ numbers larger are fixed in their relative order. The smaller numbers must go up, the arger numbers must go down. The number is then $x+y \choose y$.

PS (edited). Thanks to Gilles, who noted that 30 is not in the question.


If L is a regular language, how to prove that L' is also regular?

Yes, but changing the transition function also might involve changing the states. In this case, the states should "remember" whether we have seen the letter $\sigma$ in the past.

Alternatively, one can prove closure properties like this using well-known properties, like the fact that regular languages are closed under intersection. The language of all words containing the letter $\sigma$ is regular.


Practical applications of disjoint set datastructure

Maze generation (using a modified Kruskal's algorithm)
Tarjan's off-line least common ancestors algorithm
Connected component labeling
Online maintenance of biconnected components
Validation Hindley–Milner rules
Computing the winner of Havannah board game (see Efficient Playouts for the
Havannah Abstract Board Game)
Alias analysis
Used in construction of contour trees (see Laying the Foundations for an Advanced
Visualization System in O'Caml and Multi-Resolution computation and presentation of Contour Trees)


The characterization of a problem as PSPACE-complete is ...?

Several are idiomatic: "coarse", "coarse-grained", "crude", "rough", "unrefined". These all (roughly) mean 'lacking in [fine] detail'.

"Coarsely grained" and "coarsely granular" don't work well in this case (though the meaning would not be lost, it just reads strangely). These two imply that you're talking about properties of the object (in this case the characterisation - the first that it has a grain of some kind which is coarse, the second that it comes in rough lumps).

"Gross", "grainy" and "granular" don't work at all, and would require the reader to guess that you actually meant to write something else. The "grain" in "coarse-grained" refers to meaning 5, not meaning 1 as described here, so the adjective granular is incorrect. "gross" at its root means "large", so doesn't give the right intent here either.

As an alternative with a different core meaning, you could say that it's "unenlightening", or "unilluminating", suggesting that it doesn't tell you much, rather than it's rough.


Impact on the order of elements on the cost of searching in a linked list

I'm assuming costs are strictly positive. Otherwise it doesn't make much sense to consider the quantity $P_i/C_i$.

Regarding 1: Consider any order, and suppose that for some $i$, $P_i/C_i < P_{i+1}/C_{i+1}$. Suppose that we switch the elements $i$ and $i+1$. Say that we switched between $\ldots,A,B,\ldots$ and $\ldots,B,A\ldots$. Let $\Delta$ be the difference in average search cost (new cost minus old cost). When looking for $A$, which happens with probability $P_i$, we have to pay $C_{i+1}$ more. When looking for $B$, which happens with probability $P_{i+1}$, we have to pay $C_i$ less. So
$$ \Delta = P_i C_{i+1} - P_{i+1} C_i = (P_i/C_i - P_{i+1}/C_{i+1}) C_i C_{i+1} < 0. $$
In other words, the switch was beneficial. We conclude that the optimal arrangement is to store the elements in non-increasing order.

How I found this proof: I tried to construct a counterexample by trying a few examples on two elements, but I didn't work. So I decided to write the inequalities enjoyed by such a counterexample, and solve them in order to find one. The solution showed that in fact no counterexample is possible.

Regarding 2: This is quite easy to construct, especially in view of part 1, which gives a condition for optimality in case there are only two elements. I'm sure you can handle this part yourself.


The algorithm is studied by Yijie Han in his paper [1].

There's also a relevant question on cstheory: Han's $O(n\log\log n)$ time, linear space, integer sorting algorithm.

[1] Han, Y. (2002, May). Deterministic sorting in O (n log log n) time and linear space. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (pp. 602-608). ACM.


What is the best algorithm for multiple matches?

Use an algorithm for bipartite matching.

Build a graph with one left-vertex per (user, fruit that user has) pair.  For instance, in the example above, we'd have one vertex for (User 1, Apples) and another vertex for (User 1, Bananas).  Add one-right vertex per user.  Draw an edge from (user $i$, $f$) to user $j$ if user $i$ has fruit $f$ and  user $j$ wants fruit $f$.

Now find a maximum matching in this bipartite graph.  The set of edges in that matching will be exactly what you want.

This does allow one user to be matched to multiple other users: for instance, the vertex (User 1, Apples) might be matched to the vertex User 2, and the vertex (User 1, Bananas) might be matched to the vertex User 3.


Method to recognize abstract objects such as hand-drawn objects?

It sounds like you're looking for shape matching techniques.  Sven Loncaric's well-cited survey paper "A Survey of Shape Analysis Techniques" from 1998 can be found here.

In 2002, Belongie, Malik and Puzicha proposed a similarity measure between two shapes based on

  solving for correspondences between points on the two shapes, then
  using the correspondences to estimate an aligning transform.

David Marr's book 'Vision', particularly §3.6 and chapter 5, also provides some background about the correspondence between shape recognition in human visual systems and computers.


Is it possible that low-resource Turing Machines can always "usually" agree with high-resource Turing Machines

Okay, I realized there's an uninteresting answer to this question via a "slow" diagonalization argument.  Let ${M_k}$ be an enumeration of the machines that run in $TIME(n^2)$.  Define $\bar{M}$ to be the machine that does the opposite of $M_k$ on all inputs of length $k$.  Then $\bar{M}$ is in $TIME(n^{2 + \epsilon})$, but there is no machine in $TIME(n^2)$ that is a $0.001$ approximation of $\bar{M}$, because there is some input length on which the two machines disagree everywhere.

I don't feel like this really captures the spirit of the question, though, and I'm going to try to think about how to re-formalize it.  Maybe I want to say something about circuits?  Like: is it possible that for all circuits on $n$ input wires, $SIZE(c)$ has a $.99$ approximation of $SIZE(c+1)$?


Need to understand signals received vs sent

Suppose I sent you 10 letters. Then the number of letters that you have received is at most 10 (some might still be en route).

The reason that this is stressed is that some of the signals could potentially be received by several threads. The operating system guarantees that each signal is received by at most one thread, chosen arbitrarily among threads which have not masked the signal.


Given a list of strings, find every pair $(x,y)$ where $x$ is a substring of $y$. Possible to do better than $O(n^2)$?

This can be solved with Aho-Corasick algorithm in $O(nm + Mm)$ time, where $M$ is the number of pairs outputted.

First build the Aho-Corasick automaton for the set of strings in $O(nm)$ time. Then run each string through the automaton - this takes $O(nm)$ time for running the strings through the automaton and $O(Mm)$ time for outputting the matches because the same string can match $m$ times in the worst case. (For example ab matches ababab 3 times.)

This can be improved to true linear $O(L + M)$ time, where $L$ is the total length of the strings and $M$ is the number of matches:

When running the strings through the automaton, store for each node of the automaton the index of the previous string for which this node was visited. When outputting the matches, stop following the dictionary links if the link leads to a node that has already been visited for this string - you have already outputted all matches that are upwards from that node. Now each match gets outputted exactly once, and we traverse dictionary links only when new matches are outputted.


How many rotations after AVL insertion and deletion

The obvious resource, Wikipedia, I did not find  very helpful.

When inserting an element at most one (single or double) rotation is needed, at the lowest point where the tree is out of balance. After rotation the height of that subtree is the same as in the original subtree, so all nodes upwards are balanced.
See the answer by colleague Raphael to "Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree?"

When deleting occurs, one is not always that lucky. Rotation does not necessarily restore the original tree height, so the tree has to be updated at other levels higher up in the tree. Worst case trees are those which are minimal AVL trees, meaning with no node can be removed without violating the AVL property. There you might have to rotate every level, thus a logarithmic number of times.


Generate a random combination in O(k) time and space?

Suppose that $k \leq n/2$ (the constant $1/2$ is arbitrary) – otherwise you can just use the $O(k)$ time, $O(n)$ space algorithm, which is the second algorithm that you mention.

One way of solving your problem is as follows:

Start with the empty list.
Repeat $k$ times:

Generate a random number from $1$ to $n$.
Check if it is already in the list.
If so, go back to step 1.
Otherwise, add it to the list.

The expected number of steps in this algorithm is
$$
\frac{1}{1-0/n} + \frac{1}{1-1/n} + \cdots + \frac{1}{1-k/n} = n \left(\frac{1}{n} + \cdots + \frac{1}{n-k}\right) \leq \frac{k}{2},
$$
since $k \leq n/2$.

Using a hash table, use should be able to implement step 2 in $O(1)$ expected time and $O(k)$ space.


The more common term is the "product construction".

The product of a PDA and a DFA is a PDA whose state space is the Cartesian product of the states of the two automata (just like in two DFAs), the transition function is similar to the product construction in DFAs, only the PDA component can act on the stack.


Speaker independent voice command recognition

Software

There are many many speech recognition toolkits and software packages, which should be able to do what you want.  See, e.g., https://en.wikipedia.org/wiki/List_of_speech_recognition_software for a partial list.

For instance, if you're looking for open source software, you could try Sphinx, Simon, or any number of other software packages.  They can be trained in various ways, and probably can be used for what you want.  There are also many proprietary speech recognition tools, which might meet your needs as well.

Algorithms

The algorithms used by speech recognition systems are pretty standard.  You split the audio into frames, use the MFCC transform to compute Mel features, then use Dynamic Time Warping or a HMM with Gaussian mixture model to recognize the spoken phrases.  I would anticipate this standard pipeline would likely work for your requirement, if you train it appropriately.

(I'm not sure why you want to start from a spectrogram rather than from the audio clip itself.)


Listing integers as the sum of three squares $m = x^2 + y^2 + z^2$

Your first approach is probably the simplest to implement.  Its running time will be $O(m)$.

Another approach: you could loop over all $x$ such that $0 < x < \sqrt{m}$, and for each $x$ enumerate all ways to express $m-x^2$ as a sum of two squares.  There's a lot of theory about how to express an integer as a sum of two squares (e.g., Lagrange's algorithm).  However, this will be more complex to implement.


Evaluating Statements Using a Parse Tree

An expression is composed usually of an operator (or function) applied
to some arguments, or in the simplest case, just a constant (aka
literal) or a variable.

For evaluation:
The value of a constant is that constant, The value for
a variable is the current value stored in that variable, as each
variable corresponds to a memory location where values can be stored.
The value of an operator or function applied to arguments is obtained
by evaluating arguments (recursively) and then applying the operator or
function to the values thus obtained.

Actually, things can be more complex for a function (and some
operator), depending on parameter passing mechanisms or evaluation
modes (lazy or not), but that is to complex to explain at this level
of discourse.

In your example the operator is child 2, and the two other children
are arguments.

In general the algorithm does pretty much what you would do if you had
to interpret the program by hand. That should be a good guide.


Halting problem reduction to Halting for all inputs

There are a couple of points here. First, you're confusing the direction of the reduction: You're reducing HALT to HAI, not the other direction. Then, your book suggests the transformation $(\langle\,M\,\rangle, x)\rightarrow\langle\,M'\,\rangle$ where $\langle\,M\,\rangle$ is the description of a TM $M$, $x$ is a string, and $\langle\,M'\,\rangle$ is the description of a TM:

M'(y) =
   erase the input y
   write x on the tape  // second point: we're erasing and writing different strings
   simulate M on x

Now if $M$ halts on input $x$, then $M'$ will halt on every input $y$ and so will be an instance of HAI. Conversely, if $M$ fails to halt on $x$, then $M'$ will not halt on any input $y$ and so will not be in HAI.

From here, we can see that HAI is undecidable. If it were, then we could decide whether $M'$ would halt or not, and hence we'd be able to decide whether $M$ halted on $x$. In other words, we'd have a decider for HALT, which we know is impossible.


Height and depth of every node in Path Compression

I assume that the height of a node $\small x$, denoted as $\small h(x)$, is recursively defined as:
$$
\small
h(x) = \begin{cases}
0 & \text{ if $x$ is a leaf} \\
1+\max\{h(y) \mid y\text{ is child of } x\} & \text{ otherwise }
\end{cases}
$$
Let the value of the potential function before calling $\small \texttt{Find}(x)$ be $\small \Phi$ and the value after the call be $\small \bar{\Phi}$. Similarly we can define $\small h(x)$ and $\small \bar{h}(x)$ respectively. Denote as $\small P_x$ the path from $\small x$ to the root $\small r$ of the corresponding tree. By path compression, nodes in $\small P_x$ (except $\small r$) are all set to point to $\small r$. Therefore, generally $\small \bar{h}(y) \leq h(y)$ for $\small y \in P_x$, since $\small y$ may have one child removed.

The amortized cost of $\small \texttt{Find}(x)$ is:
$$
\small
\mathcal{O}(|P_x|) + \bar{\Phi} - {\Phi} = \mathcal{O}(|P_x|) + \sum_{y \in P_x}\{\bar h(y) - {h}(y)\}
$$
where $\small |P_x|$ is the # of nodes in $\small P_x$ and $\small \mathcal{O}(|P_x|)$ is the actual cost of $\small \texttt{Find}(x)$. Now look at term $\small \bar h(y) - {h}(y)$, by the discussion above, its value is no greater than $\small 0$. Unfortunately, there are special cases where $\small \bar h(y) = h(y)$ for all $\small y \in P_x$. Therefore, what we can say about the amortized cost, using sum of heights as potential function, is the amortized cost is $\small \mathcal{O}(|P_x|)$, which is the same as the worse-case bound.


Terminology for describing a kind of server

Such a server would be stateful rather than stateless: roughly speaking, stateful means that it keeps some information, possibly partial information, on past queries.  If you are looking for a single word to capture the idea that the server stores a complete record of all past queries, in their entirety, I don't know of a single word that does that -- so just use a sentence to describe what you're talking about.


Divide-and-conquer: Determining the top two candidates and whether these two candidates received more than n/2 votes

The original problem is not quoted/rephrased correctly
Here is one correct version as it appears as exercise 18 in section 8.3 of the book Discrete Mathematics and Its Applications, 7th Edition by Kenneth H. Rosen, with slight modification.

Suppose that each person in a group of $n$ people votes for exactly two people from a set of candidates to fill two positions on a committee. The top two finishers both win positions as long as each receives more than $n/2$ votes.
Devise a divide-and-conquer algorithm that determines whether the two candidates who received the most votes each received more than $n/2$ votes. If so, determine who these two candidates are.

What is difference? As I have emphasized, only when it has been determined that each of the two candidates who received the most votes (the top two candidates) has received more than $n/2$ votes, the desired algorithm is required to determine these two candidates . In other word, if it has been determined that at least one of the top two candidates received at most $n/2$ votes, the algorithm is not required to determine these candidates.
The catch here is that it is possible to determine whether the top candidate received more than $n/2$ vote without identifying who is the top candidate. It is also possible to determine whether the second top candidate received more than $n/2$ vote without identifying who is the second candidate. For example, if we are able to ascertain the most votes received by any single candidate is at most $n/2$, which can happen when we have checked enough but not all of the votes (so we might not be able to identify who are the top candidates), then we are sure that none of the top two candidates received more than $n/2$ votes.
On the other hand, by its very nature, any (usual) divide-and-conquer algorithm cannot find the top (two) candidates unconditionally. The idea is that it can happen that the top candidates overall is not among the top candidates in either half of the list. In fact, it can happen that the top candidate overall is the bottom candidate in each half of the list. For example, 10 people can vote in the following way, $(A,B), (A,B), (A,B), (C,D), C,D), (E,F), (E,F), (E,F), (C,D), (C,D)$. While $C$ and $D$ are the top candidates overall, they are the bottom candidates voted by the first 5 people and they are the bottom candidates voted by the other 5 people.

The "answer" given by the OP, the fourth paragraph in the question, which starts with "our algorithm" and ends before the separator line, is in fact a part of an answer key. For brevity, I will refer to it as "the answer key".
How to understand the answer key
You can check the other cool answer written by D.W., which includes a very detailed analysis of the answer key.
D.W.'s answer describes in great detail, according to the answer key, an algorithm that returns a list of three candidates which contains all the candidates who got more than $n/2$ votes and possibly other candidates. More specifically, if a candidate got more than $n/2$ votes, then he/she must be in the returned list. However, the list may contain people who did not get more than $n/2$ votes. It can also happen that none of the people in the returned list is the top candidate, or the second top candidate, or the third top candidate.
D.W.'s answer also explains clearly "why we are coming up with at most six names" as well as "where the $12n$ comes from".
I have confirmed that D.W.'s algorithm is correct (since he, in his modest way, claim he does not "know whether this algorithm is actually correct") in that it conforms to the answer key and it is a full answer to the original problem except it omits the easy steps such as "if so, determines who these two candidates are".
A better written problem
It turns out, as you must have noticed by now, somewhat subtle to understand exactly what is the requirement of the original problem. Here is my version of the problem that should be much clearer, at least for me.

Suppose that each person in a group of $n$ people votes for exactly two people from a set of candidates. Devise a divide-and-conquer algorithm that determines all candidates who received more than $n/2$ votes.

If you are careful, you may point out the my version missed "... to fill two positions on a committee. The top two finishers both win positions as long as each receives more than n/2 votes". Well, although it is interesting to know that election goal and election rule, it has nothing to do with the specification of the desired algorithm. You may also point out that my version does not require "if so, determine who these two candidates are". Well, if we have determined all candidates who received more than n/2 votes, the number of whom is at most 3, then by just counting the number of votes received by each of those candidates, we can, easily, "if so, determine who these two candidates are".
An interesting algorithm as an exercise
There is an algorithm using linear time and constant space that determines all candidates who received more than $n/2$ votes. The construction of such an algorithm is left as an intriguing and challenging exercise for the readers who has read thus far.
Thanks to Tom van der Zanden, who pointed out a typo in my previous formulation of the exercise.


the OS saves the PC and user stack pointer of the currently executing process, and transfers control to the kernel clock interrupt handler.

This is not done by the OS, since the PC is still pointing to the process code. It is the CPU that performs this step, just before jumping to the kernel interrupt handler (hence modifying PC and SP), which can then save the rest of the state in the PCB.

Since the first step is implemented at a lower level (in the CPU hardware / firmware) it should be simple so that the CPU design does not require too much effort.

Saving registers is much simpler (cheap) when done at the assembly (OS) level, which requires less effort to design/code with respect to the CPU level. Hence, usually the CPU is made to save just enough to allow the OS to save the rest.


Floyd–Warshall algorithm ,Behavior with negative cycles

Given a graph, suppose to have a cycle given by Nodes $i \ $,$\ j$,$\ k$ of negative cost.

Example:

$w(i,j)=2,\ w(j,k)=4,\ w(k,i)-7$

+---+    +2      +---+
| i |+---------->| j |
+-+-+            +-+-+
  ^                |
  | -7             |+4
  |     +---+      |
  +----+| k |<-----+
        +---+

Suppose you want to find the shortest path between $i$ and $j$.

You have

$P=\{(i,j)\}$ with $cost(P)=2$

but you can loop through the negative cycle and have:

$P'=\{(i,j),(j,k),(k,i),(i,j)\}$ with $cost(P')=1$
 $P''=\{(i,j),(j,k),(k,i),(i,j),(j,k),(k,i),(i,j)\}$ with $cost(P'')=0$
and so on.

You could loop forever through the negative cycle and decrease the cost of the path.

Same if you consider an undirected graph with an edge that has negative weight.


Count unique increasing subsequences of length 3 in $O(n\log n)$

Here is an algorithm to count distinct subsequences of length $3$ in time $O(n \log n)$, regardless of how many times any value $a$ occurs in $A[j]$.

First, create a binary search tree $T$ containing all possible values $a = A[j]$, storing at each node how many times it occurs in $A$, and how many nodes there are which follow it in the tree (are further to the right) representing larger values $A[k]$. Note that with each insertion (and later, removals), the tally of further-right values will become out of date for many of the nodes. However, we can maintain these values for each node lazily, by maintaining at each parent node a count of the pending counter updates for its left and right subtrees. (When we later traverse to a child node, its own counter of larger elements, and its pending-update counters for its children can be adjusted by the amount indicated by its parent.) Similarly, any insertions or removals in the right subtree of a node leads to a pending update for the left subtree. This should also be implementable for balanced trees as well, such as AVL trees or red-black trees. We will henceforth suppose that as we traverse any particular node that its counter is thereby kept up-to-date, though it may become out of date in between visitations.  Constructing $T$ takes time $O(n \log n)$.

We traverse $A$ once more, creating a tree $F$ which also contains values $a = A[j]$ and the number of nodes to the left of each node, similarly to $T$. (We also maintain a separate counter at each node of $F$ of how many nodes have been added to its left since the last time we look up the node in the tree; this uses a similar update method as the total-counter, though because we would clear this counter each time the node is visited, in practise we just use the pending-update value for its parent node.) At the same time we will be disassembling the tree $T$, and counting distinct increasing subsequences in $A$ of length 3 by considering, using $F$ and $T$, how many different values of $a'$ and $a''$ can serve as the first and respectively third value in an ordered triple $(a',A[j],a'')$. We do this as follows.

Set $N := 0$. For each $1 \leqslant j \leqslant n$ in order, do the following:

Let $a := A[j]$. Decrement the occurance counter of $a$ in $T$. This takes time $O(\log n)$.
Search for $a$ in $F$. If it is not present, insert it, and set
$$\text{incr} := \#(\text{nodes left of $a$ in $F$}) \cdot \#(\text{nodes right of $a$ in $L$}).$$
Otherwise, if $a$ is already present, set
$$\text{incr} := \#(\mathop{*}\text{newly added}\mathop{*} \text{ nodes left of $a$ in $F$}) \cdot \#(\text{nodes right of $a$ in $L$}).$$
This takes time $O(\log n)$ as well.
Add $\text{incr}$ to $N$.
If the occurances counter of $a$ in $T$ has dropped to $0$, remove $a$ from $T$. This takes time $O(\log n)$.

[Edited to add: as Peter Shor notes in the comments, rather than storing in $T$ the number of times $a$ occurs in $A$, we can simply store the last index $1 \leqslant j \leqslant n$ such that $a = A[j]$ for the purposes of this algorithm. Then, rather than actually removing $a$ from $T$, we can just perform the decrement of the further-right tallies for all of the nodes to its left. The decrease in arithmetic and tree-modification operations would give rise to some modest savings in run-time.]

The total run-time of this algorithm is $O(n \log n)$. In each iteration of the loop above, we only count the number of ways in which elements smaller than $a$ which haven't been used yet as a subsequence starter can be combined with elements larger than $a$ which still have at least one occurance later in the list, with $a$ itself in the middle. Thus, we count the number of "newly possible" subsequences there are for each $A[j]$ as new first elements are made available for each remaining available third element, and accumulating them for  $1 \leqslant j \leqslant n$.


Is every undecidable language reducible to any other undecidable language?

There is no concept of "reducibility in general". You always have to specify the power of the reduction. For example, if you allow mapping reductions but with literally any function (not necessarily a computable function) performing the mapping, then any language is reducible to any non-trivial language (i.e., anything other than $\emptyset$ or $\Sigma^*$).

If you do limit the power of the reduction in any way, then there are always pairs of problems $X$ and $Y$ such that $X\not\leq Y$. For example, take any language $X$ that isn't decidable in whatever model of computation you're using to define your reductions. Under that model of reductions, $X\not\leq \{0\}$.

OK, but you asked about undecidable languages and $\{0\}$ isn't undecidable. So, let $H_0$ be the halting problem for the model of computation you're using for your reductions. Let $H_1$ be the halting problem for Turing machines that have an oracle for $H_0$ (if $H_0$ is decidable, this is just the ordinary Turing machine halting problem), and let $H_2$ be the halting problem for Turing machines that have an oracle for $H_1$. Essentially the same proof that the ordinary Turing machine halting problem is undecidable shows that $H_2\not\leq H_1$, and both of these languages are undecidable.

Actually, I don't think that last paragraph is quite right. In the case that your model of reductions is more powerful than Turing machines, you probably need to use the reduction model instead of Turing machines to define the pair of halting problems. I don't have time to fix this right now but I'll come back to it this evening (UK time).


NP-Completeness reduction, using a same input

You can do whatever you want as long as you satisfy the definitions.

For example, a polynomial time reduction from a language $A$ to a language $B$ is a function $f$ satisfying the following two properties:

$f$ can be computed in polynomial time.
For every $x$, we have $x \in A$ iff $f(x) \in B$.

Any function $f$ satisfying these conditions is a polynomial time reduction from $A$ to $B$.

In particular, if $A$ is NP-hard and there exists a function $f$ satisfying these two conditions, then $B$ is also NP-hard.

The definition doesn't specify anything beyond these two properties. In mathematics nothing is left unsaid; everything which is not forbidden is actually allowed. All the cards are open. The rules of the game are public, and there is no need to ask a judge about any of them.


Does the subset sum problem remain $NP$ complete when we increase word size and restrict number of words?

Your problem is not really well-defined, since it's not clear what is the parameter $n$. That said, under any reasonable interpretation, your problem is still NP-complete, as can be shown by padding. Given an instance of subset sum, we can create an instance of your restricted subset sum by adding a lot of zeroes to the set.

Subset sum is solvable in polynomial time if the weights are polynomially bounded. More generally, if there are $m$ integers and each one is bounded in magnitude by $B$, then subset sum can be solved in $O(mB)$. In your case the weights are not polynomially bounded.


How many bits would be needed for the byte?

In a processor architecture of 64 bits the smallest single 'word' is 64 bits. that is each cyclic transfer from buffer to buffer occurs on a 64 bit buss. to identify a single byte of this native word in fact would only take 3 bits, but the actual register might in fact be 8-16 bits... if it was designed that way. the compiler that was designed to handle this would take all this into account and when you incremented a pointer it would do the conversion for you. as well as if the 'byte ' was actually an Unicode 16 bit character'. you need to look at the cpu programmers guide or manual for actual specifics and also the compilers manual, specifically with regards to data types and to addressing them.


Complexity of numerical derivation for general nonlinear functions

The time to compute first-order derivatives (gradients) and second-order derivatives (Hessians) depends heavily on the particular function.

In general, I am aware of three approaches:

Analytical: With pencil and paper, figure out an analytical expression for the derivatives, by using the rules of calculus.  Then implement those expressions.  Here the running time depends entirely on how easy or hard it is to compute those expressions.  In some cases, you may be able to use a computer algebra system to help with this calculation.
Automatic differentiation: Use the computer to do compute the derivatives for you, given a program to compute the function itself.  See, e.g., https://en.wikipedia.org/wiki/Automatic_differentiation.  This will construct a program that evaluates the derivative at a value of your choice.  The running time and ability to do this depends entirely on the program you are differentiating.  Generally speaking, if you are differentiating a function $f$ that can be computed in $O(n)$ time as a straight-line expression (with loop-free code that uses only elementary operations and conditionals, but no arrays or random-access memory lookups or loops), then automatic differentiation can construct a program that evaluates the derivative at an arbitrary input in $O(n)$ time.  This is true even if the function is over multiple variables and you want to compute the gradient.  The Hessian is slower: if $f$ is a function of one variable, you can evaluate the Hessian at an arbitrary point in $O(n)$ time, but if $f$ is a function of $m$ variables, it will take $O(mn)$ time.
Numerical differentiation: You can use the method of finite differences to approximate the gradient, given only a black box that can compute the function (you don't even need the code of that black box).  See https://en.wikipedia.org/wiki/Numerical_differentiation.  Here if you have a function $f:\mathbb{R} \to \mathbb{R}$ of one variable that can be evaluated in $O(n)$ time using some black box, you can approximate the derivative or second derivative in $O(n)$ time.  If $f$ is a function of $m$ variables, you can approximate the gradient at an arbitrary point in $O(mn)$ time, and estimate the Hessian in $O(m^2n)$ time.

Finally, one more method that may be acceptible in some settings is to evaluate the function $f$ at several points, fit a model $\hat{f}$ based on those points, compute or estimate the first- or second-order derivatives of $\hat{f}$ using any of above methods, and use that as an estimate of the corresponding derivative of $f$.

Saying you are interested in "nonlinear least squares" does not narrow things down, because "nonlinear" allows a completely arbitrary function, so long as it is not linear.


What is branch factor for beam search in RNNs like TensorFlow's Magenta?

Branch factor in beam search refers to average number of branches at each level of a search tree. When predicting a sequence in an LSTM model, such as note selection in melody generation, $b$ branches will be decoded. Increasing the branch factor from 1 to 4 in the call to melody_rnn_generate will maintain the average number of branches to be at $b$.

Specifically for Magenta, it generates 4 branches for each event sequence. It will increase the accuracy of the prediction at the expense of time, and in melody creation at the risk of getting stuck in a local optimum. For example, increasing the branch factor from 1 to 2 decreased the average negative log-likelihood of a melody generation implementation from 36 to 8, but also made the sequence prediction more dependent on the primer sequence (repeating the primer note).