Are comparison sort algos appropriate for SUBJECTIVE sorting?

I suggest reading about the theory on rating systems and ranking systems.  There are many standard algorithms and methods for this.  I would recommend reading the following resources, to get you started and to give you an entry-point and overview and let you figure out which might be best-suited for your particular situation:

The Bradley-Terry model
Pairwise comparison
The Elo rating system, and other rating systems (TrueSkill, Glicko, etc.)
Resources on Stats.SE: https://stats.stackexchange.com/q/30976/2921, https://stats.stackexchange.com/q/71297/2921, https://stats.stackexchange.com/q/15776/2921, https://stats.stackexchange.com/q/6379/2921
Finally, there is work on experiment design: how to sequentially select which pair of characters to compare, based on the results of comparisons so far.  (Think of this like matchmaking in chess, where you want to figure out which pairs of players to have play each other, based on their results so far.)  I can't remember pointers right now, but I remember that I've seen some material on Stats.SE about this as well, so do some searching there and you might find additional references and resources.

I suspect it is likely that one of these will be a reasonable choice for you.

There is a major caveat.  It is important to understand is that there may not be any linear ordering of characters that has the property you want.

Think of the game rock-paper-scissors; there is no linear ordering of these three choices that ranks them in order of "power", and polling people about pairs of them won't let you find a linear order.  In particular, none of those three choices are any more powerful than any other; rock beats scissors, paper beats rock, and scissors beats rock.  This can show up in fantasy settings, too.


But $M_{\mathsf{F},p^*}$ will take double exponential time in the length of $x$ to arrive at that conclusion, if I'm not mistaken.

That $M_{\mathsf{F},p^*}$ will take double exponential time is a conjecture at best. Too see that this conjecture is pretty strong, take any formula $\phi$ that is formally independent of $\mathsf F$, and ask whether a short proof of $\phi$ can be found in $\mathsf F$. Any algorithm that can answer this question quickly (with "no") can also answer the same question for $\phi=\bot$ quickly (with "no"), because any formula can be derived in a single step from $\bot$.

  Now I wonder whether there are more interesting ways to make $M_{\mathsf{F},p^*}$ look bad, perhaps similar in spirit to Rice's theorem?

Formal systems are not just bad at proving their own consistency, they are also famously bad at proving some sequence to be random. So we could ask whether a given finite sequence can be reproduced by some program shorter than $m$ symbols taking fewer than $n$ steps. The restriction to fewer than $n$ steps allows us to implement $p^*$ as a brute force search. If the sequence and $m$ are kept fixed and binary encoding is used for $n$, the resulting problem seems to be in $EXP$. Maybe it's better not to fix the sequence and $m$, because then the problem seems to be in $NEXP$.

What about a function $p^*$ based on Rice's theorem? No progress yet...


Why more and more languages do not have link stage when compiling?

You seem confused about what a linker does. It does not produce machine code. It merely sticks together (links, if you will) pieces of machine code that have already been produced by a compiler (typically).

What you were probably thinking of is that a linker produces an executable, or at least that's what a linker like ld does. This was the point of ld: to take pre-compiled libraries (.a files in UNIX parlance) and combine them together with object files to produce executables so you wouldn't need to recompile a library for every program that used it.

That said, there's nothing that keeps a compiler from just outputting an executable directly, but I don't think that this is actually happening that commonly. I'm pretty sure most languages that compile to native code do still have a linking stage. They just don't require you to explicitly call it yourself. In fact, LLVM is a popular backend for modern languages targeting native code, and building a new linker is one of the projects of LLVM. The premise that modern languages, at least those that directly produce native code, don't have a linking stage is incorrect.

For languages that primarily target a VM, they may not use ld, but that doesn't mean they don't have linkers. The recent addition to Java of "modules" has lead to jlink. More fundamentally and historically, the most natural thing to call a linker in Java is the ClassLoader. It even mentions linking the class. This is a dynamic linker. It performs the link stage at runtime. Here's the description of linking from the Java Language Specification. Of course, as always, there's nothing that stops you from compiling Java to a native executable. In that vein, there's also nothing stopping Java bytecode from being machine code.


Vapnik-Chervonenkis Dimension: why cannot four points on a line be shattered by rectangles?

The definition of "a set $P$ can be shattered by rectangles" is that for every subset of $P$, there is a rectangle that contains precisely that subset and excludes the rest of $P$. Equivalently, every labeling of the points as positive and negative is consistent with at least one hypothesis in $H$.

Now consider four points $p,q,r,s$ along a line in the plane.  Since there is no rectangle that contains $p$ and $r$ but excludes $q$ and $s$, these four points cannot be shattered by rectangles.


How to find an IP in overlapping ranges of IPs?

Store your IP address as an integer or long depending on whether it is 32 or 64 bit. Then put the ranges into an interval tree or similar data structure that will allow you to find all ranges that intersect with a given range or point (in this case the IP address you want to check against). This will have a query time of O(lg N) after a preprocessing time of O(N lgN). For K queries this is thus O((N+K)*lg N) which should be fast enough.


If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))?

You need to find a number $n'_0,c'$ such that

$$\log(c) + \log(g(n)) \le c' \log(g(n)) \text{ for all $n \ge n'_0$,}$$

and such that $n'_0 \ge n_0$.

So, see what you can find.  Note that it's ok for $n'_0,c'$ to depend on $c$ and on $g(\cdot)$.

Hint: If you can find $n'_0,c'$ such that $\log(c) \le \log(g(n'_0))$, does anything good happen?  Can you find such a $n'_0,c'$?


What cannot be proven at compile-time about a computer program?

In the theory of programming languages there are the so-called safety theorems which tell us that programs "do not do bad things". A typical safety theorem says:

  Safety theorem: If a program $P$ has a type $T$, then it either runs forever or it terminates and yields a value of type $T$.

Not every language satisfies such a theorem, and in fact, it usually takes a bit of work to make sure that a language is safe. Once we have the theorem, the compiler can make a strong guarantee by checking that the program has a type.

The safety theorem guarantees that:

A program which has a type will never get stuck, i.e., it will not encounter an undefined state.
A program which has a type will not suddenly switch to doing something completely diffrerent, for instance, it will not return a string if its type is int.

What exactly this means in practice depends a lot on what sort of information is expressed by the types of the language. For example, since a well-typed program will not get stuck, we can be sure that it will not segfault, and it will not perform an invalid pointer dereference. This is quite useful to know. Many modern programming languages strive to provide this sort of guarantee, or actually have it in cases of programming languages that have formal definitions (SML).

There are other kinds of errors which we might try to prevent, for example division by zero. Since it is non-computable whether a particular operation will happen at runtime, we cannot expect that the compiler will simply figure out whether division by zero is possible. In order to recover the safety theorem in presence of division by zero we can introduce exceptions into the language and make sure that division by zero raises an exception (rather than encounters an undefined state). The safety theorem then says:

  Safety theorem (with expcetions): If a program $P$ has type $T$, then it runs forever or terminates by either returning a value of type $T$ or raising an exception.

This sounds like cheating but is the best we can do with this sort of language. It is also a very common solution, also because exceptions are a generally useful programming concept (they are not errors, but rather a flow control mechanism). We can do slightly better if we allow the types to contain information about exceptions. Java does this with the throws declaration. Note however, that types cannot describe runtime exceptions exactly because that would make type checking non-computable.

Another way to deal with division by zero is to design the language in such a way that it is impossible to divide by zero. This could be accomplished by having a construct

x / y orelse z

which divides x by y if y is not zero, or returns z otherwise. Most programmers would find this kind of solution impractical.

Deadlock and race conditions are problematic in the same way as division by zero. In the general case it is non-computable whether a deadlock, or a race condition will happen. There are two lines of attack (just as with division by zero):

We can have more expressive types which guarantee that deadlock does not happen. The danger is that the types will be so fancy that type checking becomes undecidable, or that programmers will find the types too complex to understand.
We can design the language so that deadlock is impossible. The danger is that we will impoverish the language by doing so.

Regarding the second point above: programmers and designers of programming languages both like to use loss of expressivity as an excuse for a non-safe design. A case in point is the null pointer/object/value, where it is often falsely claimed that not having null is impractical and results in slower code. Good design goes a long way, and sometimes requires change of habits, but brings many many advantages. (It used to be the case that "real programmers" disliked garbage collection, and never admitted to themsleves that their programs leaked memory because humans could not allocate and deallocate memory by hand correctly).

In general, by making types even fancier, we can make sure that the safety theorem precludes other kinds of bad behavior by specifying good behavior. For example, in a dependently typed langauge such as Idris you can specify that your program sorts lists, in which case it can't cause division by zero, nor can it run forever. (But now the compiler may possibly need a lot of help from the programmer in order to establish that the program really has the stated type.)

You might expect also that a compiler shold be able to guarantee that a well-typed program must terminate. However, this is non-computable (Halting Oracle), not to mention that there are many useful possibly non-terminating programs (such as the browser you're using right now, and the operating system). If you need termination guarantees, then instead of referring to a safety theorem, you can design the language so that it cannot express a non-terminating computation. An example of such a language is Agda, which is also dependently typed and it doubles as a proof assistant. Note however that there is an important theorem stating that a language with computable syntax in which all programs terminate is not Turing complete.


Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3)

The paper says

  By an easy induction, there exist neighbors $C_0, C_1 \in \mathscr{C}$ such that $D_i = e(C_i)$ is $i$-valent, $i = 0, 1$

Here is a proof:

The set of configurations forms the nodes of a multidigraph in which the edges are labelled by events. $\mathscr{C}$ is the set of nodes reachable in any number of steps from $C$ while not following any edges labelled $e$. $\mathscr{D}$ is the set of nodes reachable from $\mathscr{C}$ by paths labelled $e$.

Let $i$ be the valence of $e(C)$: $e$ applies to $C$ by assumption; it is in $\mathscr{D}$ by definition; it is univalent by the assumption from paragraph 2. Let $D$ be a $(1-i)$-valent node in $\mathscr{D}$, which exists because paragraph 3 shows that $\mathscr{D}$ has both 0-valent and 1-valent configurations. By the definition of $\mathscr{D}$, there must be some node $P \in \mathscr{C}$ such that $D = e(P)$. By the definition of $\mathscr{C}$, there is a path from $C$ to $P$ consisting of nodes in $\mathscr{C}$.

The valences of $e(C)$ and $e(P)$ are unequal. For every node $V$ along the path from $C$ to $P$, $e(V) \in \mathscr{D}$, so every one is univalent. Thus, there must be two adjacent nodes along the path with different valences under $e$. These constitute $\{C_0, C_1\}$.


How MO'S algorithm with update query works?

A short (or long?) recall:
Mo's algorithm is used for problems, when you want to answer a lot of range queries over an array, in which it is not possible to generate an efficient data structure like a Segment tree, because combining multiple nodes can be very inefficient. The famous problem is to count the number of distinct elements in ranges $(l, r)$. Precomputing some ranges, like in a Segment tree, would not help, because combining two ranges is not efficient, and in general is an $\Omega(n)$ operation.

To answer such queries efficient, we need two ideas:

Mo's algorithm uses the fact that we know all queries at the start, so we can answer them offline (in any order we like).
We order the range queries by the tuple $\left(\left\lfloor\frac{l}{B}\right\rfloor, r\right)$ with $B = \sqrt{n}$ and compute the answers for them in this order.
This means we split the array into $\sqrt{n}$ blocks of size $\sqrt{n}$. First answer all range queries that start in the first block (sorted by their range ends), then all range queries that start in the second block, an so further.
The second idea is to use a data structure that represents a specific range $[L, R]$, can give us the answer to its range quickly, and it's possible to add/remove single numbers quickly to modify it's range.
And we will maintain this data structure the entire time, starting with the empty range $[0, 0)$.

E.g. in the example we just use a set together with the information how often each number appears in the current range. Adding a number will increases the count of the number (or adds the number with count 1 if it doesn't exit), and removing a number just decreases the count (or removes the number from the set).
Assuming that the data structure currently maintains the range $[L, R]$, and the next query covers the range $[l, r]$. Then we just need to individually add the parts of the array, that were not covered by the old range but are covered in the new range, to the data structure: $[l, r] / [L, R]$, and remove the parts that were covered before and are now not covered $[L, R] / [l, r]$.
It can be easily be proven, that we only add/remove $\sqrt{n}$ numbers on average per query (if we assume that we have $Q \approx n$ queries).

To handle updates we have to handle a new dimension: time. Because an identically query $(l, r)$ asked multiple times, can give different answers depending on the updates in the time between them.
So we represent each query as a tuple $(l, r, t)$. The first query gets $t = 1$, the second $t = 2$, and so on.

Again as before, we just order the queries, this time by $\left(\left\lfloor\frac{l}{B}\right\rfloor, \left\lfloor\frac{r}{B}\right\rfloor, t\right)$ with $B = n^{\frac{2}{3}}$.
So here we have blocks of size $B$ for $l$ and $r$, and answer them accordingly. First all with $\left\lfloor\frac{l}{B}\right\rfloor = 0$ and $\left\lfloor\frac{r}{B}\right\rfloor = 0$ (sorted by $t$), then all queries with $\left\lfloor\frac{l}{B}\right\rfloor = 0$ and $\left\lfloor\frac{r}{B}\right\rfloor = 1$ (sorted by $t$), and so on.

But now, if the data structure currently represents the range $[L, R]$ at timepoint $T$, and we want to answer the query $[l, r]$ at timepoint $t$, then we additionally to adding the parts $[l, r] / [L, R]$ and removing the parts $[L, R] / [l, r]$, perform the updates in the time range $(T, t]$ if $T < t$, or undo the updates in reverse if $T > t$.
It can be proven, that we add/remove/update $n^{\frac{2}{3}}$ numbers on average during each query.


How to modify semantic actions when removing left-recursion from a grammer

From what I have discovered, there is no general technique to modify the semantic actions while removing left-recursion. Instead, the best method is to take a representative example, draw its parse tree, and then checking which semantic actions give us the same result as the previous grammar.


Why do we need hashed page tables for Paging in Operating Systems?

There are several advantages of hashed page tables over the standard flat/hierarchal page tables. One of these being size, a hashed page table will use less space in memory than using a flat or hierarchal page table. It will at most have one entry for every physical frame (worst case scenario; unlikely  as many page numbers will end up having same hash value) instead of having an entry for every page (many of which will be left unused; although this problem is alleviated with the use of hierarchal page tables). Inverted page tables also have this advantage, however hashed page tables have a performance advantage over inverted tables, as the lookup is much faster in hashed page table. So a hashed page table combines the space advantage of an inverted table with the lookup advantage of a standard page table.


half precision floating point multiplication

When multiplying floating points:

we add the (real) exponents, to get the output exponent
we multiply the two mantissas (remember the implied 1), round and shift as necessary.

So the new exponent is $E=(19-15) + (3-15)= -8$.

The multiplication of the mantissas give
$$1.0011110111_2  \times = 1.0010011000_2 = 1.01101100111010101$$

taking only 10 digits (rounding down, see here) we get
$M= 0110110011$.

The sign is a minus.

So the output is
$Out= 1\ 00111\ 0110110011$.

For sanity check, let's convert to decimal and see that it makes sense.

$A = (-1)^0 \times 2^{4} \times 1.2412109_{10} = 19.8593744$

$B = (-1)^1 \times 2^{-12} \times 1.1484375_{10} = -0.0002804 $

Then,

$A\cdot B = -0.0055686$

We can convert $Out$ from above to decimal, and get
$Out = (-1)^1 \times 2^{-8} \times 1.4248047 = -0.0055656$ and the error is $0.000003 \approx 2^{-18}$ which makes sense (since the real exponent is $2^{-8}$ and we have a 10 digit significand)

See also https://oletus.github.io/float16-simulator.js/  for a calculator, and https://en.wikipedia.org/wiki/Half-precision_floating-point_format or https://en.wikipedia.org/wiki/Floating_point for definition and some more explanations.


Is there any hope to use a computer to guess combinatorial formulas for a sequence of integer values, given some initial terms?

An exact solution to this problem is of course impossible (for example is $3,5,7$ the sequence of odd integers or of primes?) but there are ways to get answers when the sequence is not in oeis but its "related" to some sequence in the database.

One way to do so is to use superseeker. Basically you send the sequence that you got to superseeker@oeis.org and then the server tries some algorithms in order to find a relationship between your sequence and the ones in oeis.

Hence a good start is to check what kind of tests/algorithms are used by superseeker (iirc there is a description about that somewhere on the site)


How a range query works on a simple B+tree

This is up to the individual database system.  There are multiple ways one might index the data and support this type of query.

One natural approach is that the system might compute in advance an index over the x-values (i.e., a B+ tree that is keyed by the x values) and a second index over the y values (i.e., a B+ tree that is keyed by the y values).  Given those indices, you can now implement the search query by doing a range query on the first B+ tree to find all values where x > 10 AND x < 100, then iterate through them and keep the ones that also satisfy y > 20 AND y < 200.

It is also possible to build multi-dimensional data structures that support 2D range queries, but those are more complex and might not be used in a typical database system.


They don't.  The urgent flag doesn't affect the handling of the packet by routers.  The urgent flag is an instruction to the TCP stack on the destination host, not an instruction to routers along the path.


When should we construct trees, graphs to analyse an algorithm?

There's no hard-and-fast rule.  Use them if they are useful; don't if they are not.  As a broad guideline:

Graphs are often useful when you have relationships between a pair of items.

Trees are often useful when you have a hierarchical relationship.


Can systems that prevent double-spending (e.g. crypto-currencies) be used to attach other unique data?

In theory, yes, a peer-to-peer validation network could be used to enforce any unique content (not just money) assuming a sufficiently large validation network.

"Sufficiently large" is the catch. Bitcoin validates transactions by having the network nodes "vote" on the transaction's validity. According to Satoshi's proposal:

  The system is secure as long as honest nodes collectively control more CPU power than any cooperating group of attacker nodes.

Getting enough honest nodes into your validation network that no amount of compromised or attacker nodes can affect validation would be very hard. You would also probably want these nodes to be controlled by a large number of people. With a large number of nodes and a small number of controllers, it would be easier to compromise significant portions of the network and it would also reduce trust in the network since, despite the number of nodes, the control is still only in the hands of a few. Bitcoin (and all of the other cryptocurrencies that I am familiar with, which admittedly, isn't a lot) accomplished this by incentivizing its validators; Bitcoins are periodically awarded to the "miners" who solve the proof of work problems in the transactions. This also happens to be a convenient way to introduce new Bitcoins.

However, this would be particularly difficult for the digital trading card scenario you mentioned, since that kind of service would likely only appeal to a niche audience. Even if you incentivized by awarding cards, there might not be enough individuals interested in operating validation nodes.

A scheme where a central authority issues the money (or other content) might not fare much better, since, in practice, the central authority would probably either end up controlling or having material influence over a large portion of the network. Remember that the Bitcoin network issues coins, not the Bitcoin devs or any other single person or small group of people.

The take-home is that if you can get enough people to participate in the validation network, then you should be able to defend the uniqueness of any information (money isn't special in this regard). However, getting enough people to participate would probably be incredibly difficult.


Every regular language has a finite index

The Myhill-Nerode theorem suggests that a language $L\subseteq \Sigma^*$ is regular iff $L$ has a finte index, and this clearly implies that a regular language has a finite index. So, let's prove this direction of the Myhill-Nerode theorem directly. Assume that a language $L$ is regular, and let $\mathcal{A} = \langle Q, \Sigma, q_0, \delta, F\rangle$ be a DFA for it.

The idea is to define an equivalence relation, denoted $\sim_{\mathcal{A}}$, over $\Sigma^*$, and then prove that:

The number of equivalence classes of $\sim_{\mathcal{A}}$ equals $|Q|$.
The Myhill-Nerode equivalence relation w.r.t $L$,  which i denote by $\sim_L$,  is coarser than the relation $\sim_{\mathcal{A}}$:
for every two words $x, y\in \Sigma^*$, if $x\sim_{\mathcal{A}} y$ then $x\sim_L y$.

Note that $2$ implies that the index of $L$ is at most the number of the equivalence classes of $\sim_{\mathcal{A}}$, and thus by $1$ and the fact that $|Q|$ is finite, we get that $L = L(\mathcal{A})$ has a finite index.

To begin with, the transition function $\delta$ which is a funtion from $Q\times\Sigma$ to $Q$ can be generalized to $\delta^*$ inductively to read words as follows. The generalized transition function $\delta^*: Q\times \Sigma^*$ is defined by:

$\delta(q, \epsilon) = q$, for every state $q$.
and, $\delta(q, u\sigma) = \delta(\delta^*(q, u), \sigma)$ for every word $u$ and letter $\sigma$.

Intuitively, $\delta(q, w)$ is the state that is reached from $q$ upon reading the word $u$.

Now we define the relation $\sim_{\mathcal{A}}$ over $\Sigma^*$. For every two words $x, y \in \Sigma^*$ we say that $x \sim_{\mathcal{A}} y$ iff $\delta^*(q_0, x) = \delta^*(q_0, y)$. In words, $x$ and $y$ are equivalent iff the automaton $\mathcal{A}$ reaches the same states upon reading $x$ and upon reading $y$.

The following lemma can be proved by induction and i leave it to you.

Lemma: $\delta^*(q, u\cdot v) = \delta^*(\delta^*(q, u), v)$, for every state $q$ and words $u$ and $v$.

Let's prove 1 and 2:

Follows immediately by the definition of $\sim_{\mathcal{A}}$. Indeed, every state $q$ of $\mathcal{A}$ defines an equivalence class.
Assume that $x$ and $y$ are such that $x \sim_{\mathcal{A}} y$. By definition we have that $\delta^*(q_0, x) = \delta^*(q_0, y)$. Let $z\in\Sigma^*$ be a word. We need to show that $xz\in L$ iff $yz\in L$: using the above lemma and what we have so far, we get the following:

$$xz \in L$$ $$iff$$

$$\delta^*(q_0, xz) \in F$$ $$iff \ \          (\text{By the lemma})$$

$$\delta^*(\delta^*(q_0, x), z) \in F$$ $$iff \ \         (\text{By the fact that $\delta^*(q_0, x) = \delta^*(q_0, y)$})$$

$$\delta^*(\delta^*(q_0, y), z) \in F$$ $$iff  \ \       (\text{By the lemma})$$

$$\delta^*(q_0, yz) \in F$$ $$iff$$

$$yz\in L$$.

thus, $x \sim_L y$ and so we are done.


Create a DFA and a NFA where the word includes (two) consecutive zeroes

The difference of DFA and NFA is in the transition map (or "outgoing arrows" as you describe) and has nothing to do with "incoming arrows". Namely, if $\Sigma$ is the input alphabet then the transition function of the DFA must be uniquely defined for each state and input symbol pair

$$\delta(q,a) = p, \text { for } q,p \in Q, a\in \Sigma$$

In case of the NFA the transition function maps each pair $(q,a)$ to a subset of states $Q$
$$\delta(q,a) = Q' = \{p_1, p_2, \dots, p_n\}, \text { for } Q' \subseteq Q, a\in \Sigma$$

In simply words, for DFA for each input symbol a state must have exactly one outgoing arrow, but in the case NFA for each input symbol a state may have more than one outgoing arrows or no outgoing arrow.

In your example $\Sigma=\{0,1\}$ and thus the DFA must have exactly two outgoing arrows for each state, but the NFA may have no outgoing arrow or up to $|Q|$ outgoing arrows.


Algorithm Comparison with Theta-notation

If $T_1(n) = \Theta(n^2)$ and $T_2 = \Theta(n^3)$, then since $n^2 = o(n^3)$, it follows that $T_1(n) = o(T_2(n))$. In particular, $T_1(n) < T_2(n)$ for large enough $n$. In fact, for every $C>1$, $T_1(n) < CT_2(n)$ for large enough $n$ (how large depends on $C$).


Finding the largest linear combination that is not possible

First of all, there is a known formula that gives the correct answer in this case: if $a,b$ are relatively prime, then the maximal element which cannot be written as a non-negative combination of $a,b$ is $(a-1)(b-1)-1$. (Extending this to the case where $a,b$ are not relatively prime is a nice exercise.)

Second, suppose you don't know this formula, and want to prove that 47 is the largest value that cannot be generated. You have to prove two things:

47 cannot be generated.
Any larger number can be generated.

To show that 47 cannot be generated, note that if $47 = 9x + 7y$ with $x,y \geq 0$ then $x < 7$ and $y < 9$. This means that it suffices checking all $x \in \{0,\ldots,6\}$ and $y \in \{0,\ldots,8\}$.

To show that any larger number can be generated, you first show that $48,49,50,51,52,53,54$ can be generated, by giving the appropriate values of $x,y$ (for example, $48 = 3 \cdot 9 + 3 \cdot 7$). You then complete the proof by induction (how?).


Inspecting the correctness proof and/or executing any non-trivial example, you'll note that push-relabel algorithms are different from Ford-Fulkerson and variants in that they do not maintain a flow; that's just not part of the invariant, and it's blatantly violated right at the start.

This whole "push flow to the sink, then push the excess back to the source" idea is only that: an idea. The algorithm does not really work like that, always. But it's still useful.

Once the "wave" reaches the sink $t$, it saturates the cut $V \setminus \{t\}$. You still have vertices with excess left¹, though; the conservation of flow property is violated. This has to be remedied before we can terminate with a flow -- hence the "push flow back to the source" phase.

Whenever the cut $V \setminus \{s\}$ is not by coincidence a min-cut.


Do recursive algorithms generally perform better than their for-loop counterpart?

The answer will depend on the compiler.  As @vonbrand wrote, "Given a good enough compiler, you might even get the very same object code."  In particular, good compilers will do tail-call elimination.  In some cases this can effectively transform the code into a for-loop.  Your example looks like a good example of an instance where this could happen.

As @vonbrand says, "And unless circumstances are exceptional, your time is much more valuable than the computer's, so think first in terms of ease of writing/understanding the program".  Or, to quote Tony Hoare and Donald Knuth: "Premature optimization is the root of all evil."  To this I'd add, focus first on algorithm and data structure improvements (where one can often make the biggest improvements) and on user needs: and then if performance of this particular part of the code is really critical, try both a loop and recursion and measure.  Don't rely on your intuition; measure.


Difference between specifying argument and not in NumPy

This due to the order of optional arguments. Perhaps this example can explain thing for you:
def foo(x = 1, y = 2, z = 3):
    print((x, y, z))

In [1]: foo()
(1, 2, 3)

In [2]: foo(4)
(4, 2, 3)

In [3]: foo(z = 4)
(1, 2, 4)

Now looking at help about np.random.normal, we get:
In [4]: help(np.random.normal)
Help on built-in function normal:

normal(...) method of mtrand.RandomState instance
    normal(loc=0.0, scale=1.0, size=None)

That means that since loc is the first optional argument, np.random.normal((size, size)) is interpreted as np.random.normal(loc = (size, size)) and not as np.random.normal(size = (size, size))


how two phase commit ensure serializability

Let me try to explain this using an example. Suppose there is coordinator and two participants named P1 & P2.
Now suppose both P1 & P2 creates a transaction to modify a variable A and no other transaction is raised in between, in this case coordinator know that both participants are doing same this coordinator will raise a commit message indicating that both participants can commit and changes will be saved.
Now let's take other example Suppose variable A depends on variable B, now participant P1 raises message to modify variable A and at the same time participant P2 raises message to modify both B & A, in this case coordinator know that participants are going out of sync by executing these commands so master will decline this transaction since it will not serialize.
An assumption about the outcome of transactions, either commit, or abort, can save both messages and logging operations by the participants during the 2PC protocol's execution. For example, when presumed abort, if during system recovery from failure no logged evidence for commit of some transaction is found by the recovery procedure, then it assumes that the transaction has been aborted, and acts accordingly. [Wikipedia]


What is complexity class for #XOR-2-SAT?

The given problem is in $\mathsf {FL}$:

Solve if it is satisfiable. Let the result be number $s$. Can be done in logarithmic space.
Set $t=0$.
Count the number of clauses of form $(a\oplus \overline a)$ where $a$ does not appear in any other clause except clauses identical to that one. For each such clause increase $t$ by $1$.

Step 3 can be performed in log space as follows:
for every i in V:
    flagIndependent = true
    flagAppears = false
    for every j in C:
        if C_j isIdentical(`(x_i xor not(x_i))`):
            flagAppears = true
        elseif C_j contains(`x_i`):
            flagIndependent = false
    t += flagAppears * flagIndependent

Two variables i and j take space $\log(|V|)$ and $\log(|C|)$ respectively. Variables flagIndependent and flagAppears take $1$ bit each. Functions checking clauses also require $O(\log(n))$ space at most. Therefore the total space used is logarithmic.
The answer is $s2^t$.


Choosing which workers (limited number) to use in a binary assignment problem?

Your problem is known as maximum coverage.


Are compilers able to detect alternating accesses to arrays and interleave them in memory?

Some work has been done that matches your description. For instance:

Compiler-directed array interleaving for reducing energy in multi-bank memories. by Delaluz, V.  Design Automation Conference, 2002. Proceedings of ASP-DAC 2002. 7th Asia and South Pacific and the 15th International Conference on VLSI Design. Proceedings.

describes a such an optimization.


You can use the depth as the heuristic function I guess. The start node is at depth 0, the ones adjacent to it will be at depth 1 and so on! As the function will explore nodes, the heuristic function value will gradually increase with depth and that will make the function to choose next node with more caution, so that overall cost (distance to next node + heuristic value) is least affected.

Edit: You can use powers of 2 where the exponent term will be the depth. So the start node has heuristic value 2^0 = 1, the nodes adjacent to it have heuristic value 2^1 = 2 and so on.


Complexity of linear programming with restricted quadratic constraints

The intersection of convex sets is a convex set, therefore the region defined by your inequalities is convex. Essentially, that implies you can solve the problem efficiently within any fixed positive accuracy $\epsilon>0$.


First of all, note that you should use pseudo-code in your question to make it readable by anyone.

You cannot treat this problem by just listing possible ends and give them equal probability. Consider this trivial case with no tunnel:

%AO*

the frog does not have a total 50 % to escape. On first move it has 50 % to go left to exit and 50 % to go right. But if it goes right it has 50 % to die on the mine and 50 % to come back on initial cell. Finally you build the series:

to exit $\sum_n \frac{1}{2^{2n+1}} = 2/3$
to die  $\sum_n \frac{1}{2^{2n+2}} = 1/3$

Of course finding the series expression can be very complicated on hard mazes. So how to solve this problem ? You can for example use a dynamic programming solution.

The sub-problem is having the probabilities for the frog to be on any cell after the $k^{th}$ move, what are the probabilities after the $(k+1)^{th}$ move ? These probabilities also contain exit and death.

So let's take again the small example %AO*, indexing the cells 1 to 4 from left to right.

at $k=0$, the frog is on cell 2 so $P(2) = 100 \%$,
at $k=1$, the frog moves left or right, so $P(exit) = 50\%$, $P(3)=50\%$,
at $k=2$, $P(exit) = 50 \%$, $P(2) = 25 \%$, $P(dead)=25\%$

ans so on, until $P(exit) + P(dead)$ is sufficiently close to 100 % for the precision you need.

Due to tunnels or even from start position, there may be some cells unable to reach a mine, an exit or any of them (as your first example). You should first investigate this, any cell that cannot reach an exit shoud be considered as a mine. And a cell that cannot reach a mine but can reach an exit should be considered as an exit. This will prevent any infinite loop and save some time.


How to identify object(s) in image when given a list of all images?

Think of images as matrices (2D arrays) of numbers that indicate brightness. If you are looking for an exact match of an image in another, you are looking for comparing 2D integer arrays, which could be done with a double for loop that is done for each possible match location (so it is a 4 deep for loop acutaly).

A more interesting related problem is searching an image with no exact match, but with some kind of similarity instead. For that task you should read into template matching algorithms.


What is an example of complex random string, in the Kolmogorov-Chatin sense?

It is impossible to give a specific example of a string with high Kolmogorov complexity. If I was to give an example in this answer, then the following piece of code would retrieve it:

wget http://cs.stackexchange.com/q/9721

(plus some O(1) post-processing).

A string of high Kolmogorov complexity is as elusive as a random number:

There is in fact a connection between randomness and Kolmogorov complexity: a random string has maximal complexity for its length. (At least for one definition of randomness, appropriately called Kolmogorov randomness.)

This observation that it is impossible to exhibit a string of high Kolmogorov complexity can be put into a mathematical form and proved: it is called Chaitin's theorem.

The high-complexity strings are all the ones that you cannot describe.


Travelling Salesman which can repeat cities

This is directly equivalent to metric TSP. That is, TSP in which the distances obey the triangle inequality: for all cities $A$, $B$ and $C$, the distance from $A$ to $B$ is no greater than the distance from $A$ to $C$ to $B$.

As Raphael points oun in the comments, you can reduce an instance of your problem to metric TSP by setting the distance from $A$ to $B$ to be the length of the shortest $A$–$B$ path in the original graph. This shows that your problem is no harder than metric TSP. But, conversely, every instance of metric TSP is already an instance of your problem. This is because, in metric TSP, the triangle inequality guarantees that it's never necessary to revisit a vertex so allowing revisiting doesn't change the optimal solution.


Composition of polynomial and logaritmic function

Consider a Turing machine computing $f$. Suppose that it has $q$ states and $m$ tapes, that the tape alphabet is $\Sigma$, and that on input of length $n$, it uses at most $M(n)$ space. The number of possible configurations of the Turing machine is at most $N(n) = qM(n)^m|\Sigma|^{M(n)}$. In particular, if it runs for more than $N(n)$ steps then some configuration must repeat, and so it never terminates. Since the machine computes $f$, it does terminate, and so it runs in time $N(n)$. In particular, the output size is at most $N(n)$.

When $M(n)$ is polynomial, $N(n)$ is exponential ($2^{n^{O(1)}}$).


I think the answer partially intersects that of Do system calls always means a context switch?: it depends on the exact definition of "context switch". On most CPUs, an interrupt is not serviced in user mode but rather in a more privileged mode (IRQ mode on ARM, on x86 the IDT can specify the ring level). This is necessary because simply clearing the interrupt or determining its source requires accessing hardware registers (which by definition user mode cannot in general). That being said, the OS does not need to run the entire ISR in a privilege mode. Typically in a microkernel, an IRQ will be added to a queue and processed by a (user space) driver.

So an interrupt implies a privilege switch, which implies some amount of context switching (saving registers for example) but not necessarily a full process switch, depending on the architecture and the kernel.


Yes, a simple one is coming to my mind, a dynamic graph where the search operators are not reversible, i.e. both predecessors and successors of a node in the graph can not be calculated.


Smaller approximation ratio for larger input size?

In most cases it is possible to artificially enlarge an instance. For example, if you want to solve MAX-CLIQUE, you can add an independent set. In these circumstances, the approximation ratio cannot improve as the size of the instance gets larger. However, it is possible that there are some natural problems in which the phenomenon you describe does occur.


Is there an efficient algorithm for determining whether or not a graph has a non-trivial automorphism?

Since you are also interested in the theory behind it, I would give you a quasi-polynomial time algorithm for your problem.

For each pair of vertices $u\neq v$ (of same degree) in $G$, we try to see if it it possible to swap $u$ and $v$.

To do this, make a copy of $G$, call it $G'$. Now, delete $u$ from $G$, delete (copy of) $v$ from $G'$.

Then, for each $w\in N(u)$ attach to it a very long path, but only polynomially long.

Then, for each (copy of) $w\in N(copy\ of\ v)$ attach to it a very long path, but only polynomially long.

All the mentioned above very long path, but polynomially long, should be of the same length.

Call Babai's algorithm on the input of this newly produced pair of graphs.

If for any pair $(u, v)$, we have a $YES$ answer from Babai's, answer $YES$ and halt.

If none returns a $YES$ answer, answer $NO$ and halt.

Clearly, attaching to all vertices in $N(u)$ and $N(v)$ forces the graph isomorphism of Babai's inner working mechanism of his algorithm to only map vertices in $N(u)$ to $N(v)$. Thus, if Babai's answer is $YES$ then we can safely plug in back $u$ and $v$ to have a non-trivial automorphism of $G$, since $G'$ is a copy of $G$.

The run-time complexity is still quasi-poly.


Why Is KD-Tree-based Nearest Neighbor Exponential in K?

kNN tends to be exponential because the search space increases with $2^k$. Imagine you partition the space around your search point into quadrants. For k=1 you just have to search two 'quadrants' (higher and lower values), for k=2 it's 4 quadrants, for k=3 it's 8 quadrants, i.e. exponential growth of search space. That is what the kD-tree suffers from, because it has to search $2^k$ sub-branches.

Other trees perform much better, for example the CoverTree. I also found that the PH-Tree works quite well, it seems to consistently take twice as long as the CoverTree for datasets between k=8 and k=27 (I didn't have datasets with higher k).


We can consider $NUM$ and therewith $P$ a terminal symbol. Furthermore, $S$ does only occur once in every derivation. Therefore, if there is any ambiguity, it has to stem from

$\qquad \displaystyle S' \to\, = PS' \mid\, \neq PS' \mid \varepsilon$

Now, that fragment is a right-regular grammar with only one non-terminal whose right-hand sides do not share any prefixes. So clearly every term has only derivation, given by its length and permutation of $=$ and $\neq$.

In total, your grammar is unambiguous. Above observations also suggest that the grammar can be parsed in one pass from left to right with one token lookahead (distinguish $=$ and $\neq$). In fact, the grammar is basically a deterministic (no shared prefixes) and right-regular (replace all $P$ with $NUM$) grammar, so it's certainly an LL(1) grammar.

So I suggest you revisit the construction of the parsing table (your favorite textbook or Wikipedia) -- you must have made a mistake.


Some questions regarding compilers and assemblers

I agree with Raphael, don't look too far for a precise meaning of those terms. AFAIK, there is none. (And that rule is also true for terms which have a precise meaning, often the same word in used with a different precise meaning in different contexts).

  A compiler converts a human-readable codes to object codes,

I'd say that compiler is used for translators which lower the abstraction level or do deep restructuring.  The source doesn't have to be human-readable (but often is), it was common for compiler to generate assembler and not object code (gcc still does it even if it call the assembler itself) and compilers generating C are quite common.

  and those are converted to a machine code (executable) by linker.

I don't think making a difference between machine code and object code is common (and I'm not even sure which difference you are making). That makes your question 1 irrelevant. Traditionally, the linker doesn't convert, it takes several object files and resolves symbolic references between them. But pushing things traditionally part of the compilation to link time is more and more common in order to take advantage of the knowledge of the whole program.

  Question 2: Are *.class (bytecode) files created by java compiler object files? If yes, then can we say that the JVM that runs them is a type of linker (however its not creating the executable)?

The JVM contains a type of linker as it is able to combine several .class files.

  Question 3: When we compile a C++ program in Turbo C++, we get *.obj files which are the object files. Can we use them to generate the executable in some other architecture?

You could write a translator doing that (Apple did for the 68000 at the time of its transition to PowerPC for instance). Machine language is a programming language. Depending on the amount of transformation you are allowing yourself, you could even call that a compiler.


Rank operation in search tree, number of nodes between 2 values

Use an AVL tree $T$ that is augmented so that each vertex $v$ also stores the number of vertices in the subtree of $T$ rooted at $v$.
Given two vertices $u$ and $v$ of the tree you can find the number of values between $u$'s and $v$'s key by summing the sizes of at most $O(\log n)$ subtrees of $T$ dangling from the (unique) path from $u$ to $v$ in $T$.
These are exactly the highlighted trees/vertices in this answer, which also gives you a $O(\log n)$-time algorithm to find them.
The time complexities of insertions, deletions, and searches are asymptotically unaffected (i.e., they are in $O(\log n)$).


A quick search reveals that

POFS is page offset.
VPN is virtual page number.
PFN is page frame number.

Since the page offset is 13 bits long, assuming that the page is byte-addressed, the conclusion is that page size is $2^{13}$ bytes.

I trust that you can solve the other parts in a similar way, especially having been taught these concepts in class.


Is there a system behind the magic of algorithm analysis?

Translating Code to Mathematics

Given a (more or less) formal operational semantics you can translate an algorithm's (pseudo-)code quite literally into a mathematical expression that gives you the result, provided you can manipulate the expression into a useful form. This works well for additive cost measures such as number of comparisons, swaps, statements, memory accesses, cycles some abstract machine needs, and so on.

Example: Comparisons in Bubblesort

Consider this algorithm that sorts a given array A:

 bubblesort(A) do                   1
  n = A.length;                     2
  for ( i = 0 to n-2 ) do           3
    for ( j = 0 to n-i-2 ) do       4
      if ( A[j] > A[j+1] ) then     5
        tmp    = A[j];              6
        A[j]   = A[j+1];            7
        A[j+1] = tmp;               8
      end                           9
    end                             10
  end                               11
end                                 12

Let's say we want to perform the usual sorting algorithm analysis, that is count the number of element comparisons (line 5). We note immediately that this quantity does not depend on the content of array A, only on its length $n$. So we can translate the (nested) for-loops quite literally into (nested) sums; the loop variable becomes the summation variable and the range carries over. We get:

$\qquad\displaystyle C_{\text{cmp}}(n) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \dots = \frac{n(n-1)}{2} = \binom{n}{2}$,

where $1$ is the cost for each execution of line 5 (which we count).

Example: Swaps in Bubblesort

I'll denote by $P_{i,j}$ the subprogram that consists of lines i to j and by $C_{i,j}$ the costs for executing this subprogram (once).

Now let's say we want to count swaps, that is how often $P_{6,8}$ is executed. This is a "basic block", that is a subprogram that is always executed atomically and has some constant cost (here, $1$). Contracting such blocks is one useful simplification that we often apply without thinking or talking about it.

With a similar translation as above we come to the following formula:

$\qquad\displaystyle C_{\text{swaps}}(A) =  \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$.

$A^{(i,j)}$ denotes the array's state before the $(i,j)$-th iteration of $P_{5,9}$.

Note that I use $A$ instead of $n$ as parameter; we'll soon see why. I don't add $i$ and $j$ as parameters of $C_{5,9}$ since the costs do not depend on them here (in the uniform cost model, that is); in general, they just might.

Clearly, the costs of $P_{5,9}$ depend on the content of $A$ (the values A[j] and A[j+1], specifically) so we have to account for that. Now we face a challenge: how do we "unwrap" $C_{5,9}$? Well, we can make the dependency on the content of $A$ explicit:

$\qquad\displaystyle C_{5,9}(A^{(i,j)}) = C_5(A^{(i,j)}) +
    \begin{cases}
        1 &, \mathtt{A^{(i,j)}[j] > A^{(i,j)}[j+1]}  \\
        0 &, \text{else}
    \end{cases}$.

For any given input array, these costs are well-defined, but we want a more general statement; we need to make stronger assumptions. Let us investigate three typical cases.

The worst case

Just from looking at the sum and noting that $C_{5,9}(A^{(i,j)}) \in \{0,1\}$, we can find a trivial upper bound for cost:

$\qquad\displaystyle C_{\text{swaps}}(A) \leq  \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1
    = \frac{n(n-1)}{2} = \binom{n}{2}$.

But can this happen, i.e. is there an $A$ for this upper bound is attained? As it turns out, yes: if we input an inversely sorted array of pairwise distinct elements, every iteration must perform a swap¹. Therefore, we have derived the exact worst-case number of swaps of Bubblesort.
The best case

Conversely, there is a trivial lower bound:

$\qquad\displaystyle C_{\text{swaps}}(A) \geq  \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 0
    = 0$.

This can also happen: on an array that is already sorted, Bubblesort does not execute a single swap.
The average case

Worst and best case open quite a gap. But what is the typical number of swaps? In order to answer this question, we need to define what "typical" means. In theory, we have no reason to prefer one input over another and so we usually assume a uniform distribution over all possible inputs, that is every input is equally likely. We restrict ourselves to arrays with pairwise distinct elements and thus assume the random permutation model.

Then, we can rewrite our costs like this²:

$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$

Now we have to go beyond simple manipulation of sums. By looking at the algorithm, we note that every swap removes exactly one inversion in $A$ (we only ever swap neighbours³). That is, the number of swaps performed on $A$ is exactly the number of inversions $\operatorname{inv}(A)$ of $A$. Thus, we can replace the inner two sums and get

$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A)$.

Lucky for us, the average number of inversions has been determined to be

$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}$

which is our final result. Note that this is exactly half the worst-case cost.

Note that the algorithm was carefully formulated so that "the last" iteration with i = n-1 of the outer loop that never does anything is not executed.
"$\mathbb{E}$" is mathematical notation for "expected value", which here is just the average.
We learn along the way that no algorithm that only swaps neighbouring elements can be asymptotically faster than Bubblesort (even on average) -- the number of inversions is a lower bound for all such algorithms. This applies to e.g. Insertion Sort and Selection Sort.

The General Method

We have seen in the example that we have to translate control structure into mathematics; I will present a typical ensemble of translation rules. We have also seen that the cost of any given subprogram may depend on the current state, that is (roughly) the current values of variables. Since the algorithm (usually) modifies the state, the general method is slightly cumbersome to notate. If you start feeling confused, I suggest you go back to the example or make up your own.

We denote with $\psi$ the current state (imagine it as a set of variable assignments). When we execute a program P starting in state $\psi$, we end up in state $\psi / \mathtt{P}$ (provided P terminates).

Individual statements

Given just a single statement S;, you assign it costs $C_S(\psi)$. This will typically be a constant function.
Expressions

If you have an expression E of the form E1 ∘ E2 (say, an arithmetic expression where ∘ may be addition or multiplication, you add up costs recursively:

$\qquad\displaystyle C_E(\psi) = c_{\circ} + C_{E_1}(\psi) + C_{E_2}(\psi)$.

Note that

the operation cost $c_{\circ}$ may not be constant but depend on the values of $E_1$ and $E_2$ and
evaluation of expressions may change the state in many languages,

so you may have to be flexible with this rule.
Sequence

Given a program P as sequence of programs Q;R, you add the costs to

$\qquad\displaystyle C_P(\psi) = C_Q(\psi) + C_R(\psi / \mathtt{Q})$.
Conditionals

Given a program P of the form if A then Q else R end, the costs depend on the state:

$\qquad\displaystyle C_P(\psi) = C_A(\psi) +
    \begin{cases}
        C_Q(\psi/\mathtt{A}) &, \mathtt{A} \text{ evaluates to true under } \psi \\
        C_R(\psi/\mathtt{A}) &, \text{else}
    \end{cases}$

In general, evaluating A may very well change the state, hence the update for the costs of the individual branches.
For-Loops

Given a program P of the form for x = [x1, ..., xk] do Q end, assign costs

$\qquad\displaystyle C_P(\psi) = c_{\text{init_for}} + \sum_{i=1}^k c_{\text{step_for}} + C_Q(\psi_i \circ \{\mathtt{x := xi\}})$

where $\psi_i$ is the state before processing Q for value xi, i.e. after the iteration with x being set tox1, ..., xi-1.

Note the extra constants for loop maintenance; the loop variable has to be created ($c_{\text{init_for}}$) and assigned its values ($c_{\text{step_for}}$). This is relevant since

computing the next xi may be costly and
a for-loop with empty body (e.g. after simplifying in a best-case setting with a specific cost) does not have zero cost if it performs iterations.

While-Loops

Given a program P of the form while A do Q end, assign costs

$\qquad\displaystyle C_P(\psi) \\\qquad\ = C_A(\psi) +
    \begin{cases}
        0 &, \mathtt{A} \text{ evaluates to false under } \psi \\
        C_Q(\psi/\mathtt{A}) + C_P(\psi/\mathtt{A;Q}) &, \text{ else}
    \end{cases}$

By inspecting the algorithm, this recurrence can often be represented nicely as a sum similar to the one for for-loops.

Example: Consider this short algorithm:

while x > 0 do    1
  i += 1          2
  x = x/2         3
end               4

By applying the rule, we get

$\qquad\displaystyle C_{1,4}(\{i := i_0; x := x_0\}) \\\qquad\ = c_< +
    \begin{cases}
        0 &, x_0 \leq 0 \\
        c_{+=} + c_/ + C_{1,4}(\{i := i_0 + 1; x := \lfloor x_0/2 \rfloor\}) &, \text{ else}
    \end{cases}$

with some constant costs $c_{\dots}$ for the individual statements. We assume implicitly that these do not depend on state (the values of i and x); this may or may not be true in "reality": think of overflows!

Now we have to solve this recurrence for $C_{1,4}$. We note that neither the number of iterations not the cost of the loop body depend on the value of i, so we can drop it. We are left with this recurrence:

$\qquad\displaystyle C_{1,4}(x) =
    \begin{cases}
        c_> &, x \leq 0 \\
        c_> +  c_{+=} + c_/ + C_{1,4}(\lfloor x/2 \rfloor) &, \text{ else}
    \end{cases}$

This solves with elementary means to

$\qquad\displaystyle C_{1,4}(\psi) = \lceil \log_2 \psi(x) \rceil \cdot (c_> +  c_{+=} + c_/) + c_>$,

reintroducing the full state symbolically; if $\psi = \{ \dots, x := 5, \dots\}$, then $\psi(x) = 5$.
Procedure Calls

Given a program P of the form M(x) for some parameter(s) x where M is a procedure with (named) parameter p, assign costs

$\qquad\displaystyle C_P(\psi) = c_{\text{call}} + C_M(\psi_{\text{glob}} \circ \{p := x\})$.

Note again the extra constant $c_{\text{call}}$ (which might in fact depend on $\psi$!). Procedure calls are expensive due to how they are implemented on real machines, and sometimes even dominate runtime (e.g. evaluating the Fibonacci number recurrence naively).

I gloss over some semantic issues you might have with the state here. You will want to distinguish global state and such local to procedure calls. Let's just assume we pass only global state here and M gets a new local state, initialized by setting the value ofp to x. Furthermore, x may be an expression which we (usually) assume to be evaluated before passing it.

Example: Consider the procedure

fac(n) do
  if ( n <= 1 ) do         1
    return 1               2
  else                     3
    return n * fac(n-1)    4
  end                      5
end

As per the rule(s), we get:

$\qquad\displaystyle\begin{align*} C_{\text{fac}}(\{n := n_0\})
  &= C_{1,5}(\{n := n_0\}) \\
  &= c_{\leq} +
    \begin{cases}
      C_2(\{n := n_0 \}) &, n_0 \leq 1 \\
      C_4(\{n := n_0 \}) &, \text{ else}
    \end{cases} \\
  &= c_{\leq} +
    \begin{cases}
      c_{\text{return}} &, n_0 \leq 1 \\
      c_{\text{return}} + c_* + c_{\text{call}} + C_{\text{fac}}(\{n := n_0 - 1\})
       &, \text{ else}
    \end{cases}
\end{align*}$

Note that we disregard global state, as fac clearly does not access any. This particular recurrence is easy to solve to

$\qquad\displaystyle C_{\text{fac}}(\psi) = \psi(n) \cdot (c_{\leq} + c_{\text{return}})
                                        + (\psi(n) - 1) \cdot (c_* + c_{\text{call}})$

We have covered the language features you will encounter in typical pseudo code. Beware hidden costs when analysing high-level pseudo code; if in doubt, unfold. The notation may seem cumbersome and is certainly a matter of taste; the concepts listed can not be ignored, though. However, with some experience you will be able to see right away which parts of the state are relevant for which cost measure, for instance "problem size" or "number of vertices". The rest can be dropped -- this simplifies things significantly!

If you think now that this is far too complicated, be advised: it is! Deriving exact costs of algorithms in any model that is so close to real machines as to enable runtime predictions (even relative ones) is a tough endeavour. And that's not even considering caching and other nasty effects on real machines.

Therefore, algorithm analysis is often simplified to the point of being mathematically tractable. For instance, if you don't need exact costs, you can over- or underestimate at any point (for upper resp. lower bounds): reduce the set of constants, get rid of conditionals, simplify sums, and so on.

A note on asymptotic cost

What you will usually find in literature and on the webs is the "Big-Oh analysis". The proper term is asymptotic analysis which means that instead of deriving exact costs as we did in the examples, you only give costs up to a constant factor and in the limit (roughly speaking, "for big $n$").

This is (often) fair since abstract statements have some (generally unknown) costs in reality, depending on machine, operating system and other factors, and short runtimes may be dominated by the operating system setting up the process in the first place and whatnot. So you get some perturbation, anyway.

Here is how asymptotic analysis relates to this approach.

Identify dominant operations (that induce costs), that is operations that occur most often (up to constant factors). In the Bubblesort example, one possible choice is the comparison in line 5.

Alternatively, bound all constants for elementary operations by their maximum (from above) resp. their minimum (from below) and perform the usual analysis.
Perform the analysis using execution counts of this operation as cost.
When simplifying, allow estimations. Take care to only allow estimations from above if your goal is an upper bound ($O$) resp. from below if you want lower bounds ($\Omega$).

Make sure you understand the meaning of Landau symbols. Remember that such bounds exist for all three cases; using $O$ does not imply a worst-case analysis.

Further reading

There are many more challenges and tricks in algorithm analysis. Here is some recommended reading.

How to come up with the runtime of algorithms?
How to describe algorithms, prove and analyse them?
Why use comparisons instead of runtime for comparing two algorithms?
How can we assume that basic operations on numbers take constant time?
What constitutes one unit of time in runtime analysis?
Solving or approximating recurrence relations for sequences of numbers
Basics of Amortised Analysis

There are many questions tagged algorithm-analysis around that use techniques similar to this.


How does the OS detect B&B violation from hardware?

When an invalid access is detected, the #BR exception is triggered, the CPU will switch to privilege mode and load the corresponding vector (Bounds range exceeded) from the IVT. The CPU also pushes the faulty EIP (as well as other things) to the kernel stack and updates the BNDSTATUS register to describe the fault.

Note: the #BR exception saves other purposes as well because Base & Bound works like paging: there is a 2-level hierarchy to store B&B values (since the CPU can only store 4 of them in registers), so it works a bit like a TLB but for B&B.


Proving NP-hardness of strange graph partition problem

Let's reduce multiway cuts problem, a variant of minimum $k$-cut, to your problem.  In particular, consider the minimum 3-way cut problem, which is NP-hard for all edge weight equal to 1 (see The complexity of multiway cuts).

A (minimum) 3-way cut problem is: given a graph $G = (V,E)$ and terminals $s_1,s_2,s_3\in V$, find a minimum set of edges $E'\subseteq E$ such that the removal of $E'$ from $E$ disconnects each terminal $s_i$ from the others.  Its decision version is to find out if it's possible to disconnect $s_1,s_2,s_3$ by removing no more than $w$ edges, where $w$ is a part of the input.

Given graph $G$, terminals $s_1,s_2,s_3$ and integer $w$, we would like to reduce the 3-way cut problem to your "strange graph partition problem".  For each terminal $s_i$, we add $N$ more verteces to be its neighbors.  As hinted by its name, $N$ would be a sufficiently large number.  The weight of all verteces are 0 except for $s_1,s_2,s_3$, whose weights are $1,10,100$ resp.  Denote this new graph by $G'$.  It's obvious that $s_1,s_2,s_3$ can be disconnected by removing $w$ edges in $G$ if and only if they can be disconnected by removing $w$ edges in $G'$.

If a partition $G'_p$ of $G'$ disconnects $s_1,s_2,s_3$, its score is roughly $10101/N$, or more precisely, no less than $$\frac{10101}{N+n}$$
as the part containing $s_i$ has no more than $N+n$ verteces, where $n$ is the number of verteces in $G$.  On the other hand, if a partition $G'_p$ fails to disconnect $s_1,s_2,s_3$, its score is no more than $$\frac{10060.5}{N-w}$$.  When $N$ is sufficiently large, $\frac{10101}{N+n} > \frac{10060.5}{N-w}$, so $G$ can be 3-way partitioned by removing $w$ edges if and only if $G'$ has a partition removing $w$ edges, whose score is at least $\frac{10101}{N+n}$.


Confusingly, the terms $LL$ and $LR$ are overloaded. There are two related but fundamentally different classes of objects that we'd call $LL$ or $LR$:

The sets of all grammars that are $LL(k)$ or $LR(k)$ for some choice of $k$. Let's call these sets $LL_{CFG}$ and $LR_{CFG}$.
The sets of all languages that have an $LL(k)$ or $LR(k)$ grammar for some choice of $k$. Let's call these sets $LL_{LANG}$ and $LR_{LANG}$.

The example you've given is a grammar that is $LL(2)$ (I believe) but not $LR(1)$. This shows that $LL_{CFG} \not\subseteq LR(1)_{CFG}$. However, there is a different grammar that you could pick for the same language that is $LR(1)$, which follows because $LL_{LANG} \subseteq LR(1)_{LANG}$. This happens because $LR(1)_{LANG}$ is precisely the set of all deterministic context-free languages and all $LL$ languages are deterministic.


Show that a language is decidable iff some enumerator enumerates the language in decreasing order

If there is an enumerator in decreasing order then the language is finite and hence decidable.
But that means any infinite language wont have such an enumerator, and in particular there is some infinite language that is decidable (such as $\Sigma^*$) and it wont have such an enumerator.
So, this theorem is incorrect


Check whether an undirected graph contains a simple cycle of length four using the "Squares" method

Square $M$, to get $M^2$.  Write $M^2 = D + P$, where $D$ is the diagonal part (all non-diagonal entries are zero) and $P$ is the non-diagonal part (all diagonal entries are zero).
Compute $Q=P^2$.  Note that $Q_{aa}$ counts the number of ways to start at $a$ and end at $a$, excluding cycles of the form $ababa$ and $abaca$ etc., but not avoiding cycles of the form $abcba$.
Now compute $R = MDM - D$.  Note that $R_{aa}$ counts the number of cycles of the form $abcba$ where $c \ne a$.
Let $S = Q-R$.  We find that $S_{aa}$ counts the number of simple 4-cycles that start and end at $a$.  Thus, the graph has a simple 4-cycle if and only if one or more of the diagonal entries of $S$ are non-zero.


Choice of algorithm for hierarchical clustering for minimizing network communication costs

This is a form of assignment problem; in particular, it is an instance of quadratic assignment problem.  There are some known techniques available for solving this sort of problem.

Using integer linear programming

One approach is to use integer linear programming.

Let $d_{p,q}$ denote the amount of data communicated between processes $p$ and $q$, for each pair of processes $p,q$.  Also, let $c_{i,j}$ denote the communication cost for data sent between machines $i$ and $j$, for each pair of machines $i,j$.  These are given.

The goal is to find an assignment of processes to machines, that minimizes the total communication cost.  I'll assume that you only allow one process to be assigned to each machine.  We can model this as follows.  For each process $p$ and each machine $i$, let $x_{p,i}$ be an unknown that is either 0 or 1, with the intent that $x_{p,i}=1$ means process $p$ is assigned to machine $i$.  You can force it to be 0 or 1 with the constraint $0 \le x_{p,i} \le 1$.  You can force each process to be assigned to one machine with the constraint

$$\sum_i x_{p,i} = 1.$$

You can also force each machine to be assigned at most one process with the constraint

$$\sum_p x_{p,i} \le 1.$$

The total communication cost is

$$\sum_{p,q,i,j} x_{p,i} x_{q,j} c_{i,j} d_{p,q},$$

where the sum is over all $p\ne q$ and $i \ne j$.  That's what we'd like to minimize.

This is not yet a linear objective function, so we can't apply integer linear programming directly, but we can transform it into an integer linear program as follows.  Let $y_{p,q,i,j} = 1$ if process $p$ is assigned to machine $i$ and process $q$ is assigned to machine $j$.  We have $y_{p,q,i,j} = x_{p,i} \land x_{q,j}$.  Now logical AND can be expressed in an integer linear program by adding the constraints

$$y_{p,q,i,j} \ge x_{p,i} + x_{q,j} - 1$$
$$y_{p,q,i,j} \le x_{p,i}$$
$$y_{p,q,i,j} \le x_{q,j}$$
$$0 \le y_{p,q,i,j} \le 1.$$

With these extensions, the total communication cost becomes

$$\sum_{p,q,i,j} y_{p,q,i,j} c_{i,j} d_{p,q},$$

which is a linear function.  Thus, you now obtain an integer linear program, where the goal is to minimize the total communication cost, subject to the constraints listed above.  You could try solving it using an off-the-shelf integer linear programming (ILP) solver.

There is no guarantee that this will efficiently find an optimal solution -- after all, integer linear programming is NP-hard in the worst case -- but in practice ILP solvers often work surprisingly well on many problems.  So, you could give it a try and see how well it works on  your particular problem instances.  I don't know if there is a better algorithm, but this is one approach you could try.

P.S. In fact, in this particular case, you could skip the constraints $y_{p,q,i,j} \le x_{p,i}$ and $y_{p,q,i,j} \le x_{q,j}$ without changing the final solution.  This makes the program a little bit simpler, at the cost of making it a little harder to understand why it "works" correctly for your problem.

Dedicated algorithms

An alternative is to use a dedicated algorithm for the quadratic assignment problem.  For instance, Wikipedia mentions QAPLIB, a dedicated solver for instances of the quadratic assignment problem.  You could try using QAPLIB on your problem instance, to see how well it works.

There may be other algorithms for the quadratic assignment problem -- I recommend doing a literature search to see what you can turn up.


Can the pseudo-random-sequence generator be described as a finite state automaton?

A finite-state automaton can output an unending sequence of outputs, so you don't need to do anything special.  The regular language will contain all prefixes of possible output streams.

If you really want to consider infinite strings, you could use  Büchi automata to model that. Personally, I don't see the point.


If we try to apply your recurrence to $n = 9$ and add the base case $F(0) = 1$, then we get $F(9) = 2$. Now this might be the answer you want, since there are indeed two possibilities: penny+nickel and nickel+penny, but usually we consider these the same.

There are two ways to proceed if we want to compute the number of ways without regard to order. The first way is to consider three different functions $F,G,H$ which correspond to using all coins ($F$), only nickels and dimes ($G$), and only dimes ($H$). The recurrences are
$$
F(n) = F(n-4) + G(n-5) + H(n-10), \\
G(n) = G(n-5) + H(n-10), \\
H(n) = H(n-10),
$$
with initial conditions $F(0) = G(0) = H(0) = 1$ and $F(m) = G(m) = H(m) = 0$ for negative $m$. This gives a joint linear recurrence for the triplet $F(n),G(n),H(n)$.

The other approach is to use generating functions, which give us the following expression:
$$
\sum_{n=0}^\infty F(n) x^n = \frac{1}{(1-x^4)(1-x^5)(1-x^{10})} = \frac{1}{1-x^4-x^5+x^9-x^{10}+x^{14}+x^{15}-x^{19}}.
$$
This shows that the sequence $F(n)$ satisfies the recurrence
$$
F(n) = F(n-4) + F(n-5) + F(n-10) \\- F(n-9) - F(n-14) - F(n-15) + F(n-19)
$$
with initial conditions $F(0) = 1$ and $F(m) = 0$ for negative $m$.

This can be seen as a kind of inclusion/exclusion principle — I'll let you work out the details.


It is a special caterpillar.
Let $d(i)$ be the number of such trees with root $i$. We have $d(1)=1$; and $d(n)=\sum_{i=1}^{n-1}d(i)+1$, where "plus 1" is for the case of no children and $d(i)$ in sigma for the case that the left child is $i$.
One can easily compute $d(n)$ in $O(n)$ time using a simple loop. Or it is not hard to solve the recurrence relation and get $d(i)=2^{i-1}$ for $i\geq 1$.


If $Q$ reduces to $L$ then $\overline{Q}$ reduces to $\overline{L}$

By hypothesis $Q \le_p L$, i.e., there exists a poly-time computable function $f(x)$ such that $x \in L \iff f(x) \in Q$. Then:
$$
x \in \overline{L} \iff x \not\in L \iff f(x) \not\in Q \iff f(x) \in \overline{Q}.
$$

Therefore $\overline{L} \le_p \overline{Q}$.


Language described by inverting accepting states of NFA

The answer is basically in the question you link, but to make it explicit: no, there is no "nice expression" since anything can happen.

For an example, let $L$ be any regular language; let's say it's accepted by NFA $A_L$:

[source]

Now consider this automaton $A'_L$:

[source]

Clearly, $A_L$ and $A'_L$ accept the same language $L$. However, the automaton obtained from flipping $A'_L$ accepts $\Sigma^*$ (since $s$ is accepting in this one).

So we see that we need further assumptions on the automata if flipping is to yield anything meaningful. For instance, if we require that for every input, either all computations are accepting or all are rejecting -- a property $A'_L$ above does not have -- then flipping yields the complement of the original language.


single agent vs multiple agent reinforcement learning

A key difference between RL and MARL arises when you consider that other agents are strategic and their behaviour is adaptive. Game theoretical concepts are very important within the scope of MARL and bring in a new range of issues. From a single agent perspective, the environment is non-stationary as every strategic agent is changing their policies to best respond to the each other.

A good discussion on the challenges of MARL can be found here:
http://busoniu.net/files/papers/marl_chapter_springer.pdf

Regarding your question:
Yes, you can use a single agent RL as long as the preys are not learning. If you plan to apply RL to every agent (hunter and preys), you will find new issues such as convergence problems, etc. There is a lot of research going on around this. To start I would suggest you have a look at some basic and classic concepts such as Fictitious Play and WoLF (Win or Learn Fast).


Where can we put primitive recursive functions in Chomsky hierarchy?

The Chomsky hierarchy concerns languages. Languages are total functions from $\Sigma^*$ to $\{0,1\}$, where $\Sigma$ is some non-empty finite set.

A language can be computed by a primitive recursive function if it can be computed by a total Turing machine which has a primitive recursive time upper bound. In particular, every language accepted by an LBA is primitive recursive, since we can simulate an LBA by a deterministic Turing machine running in double exponential time, and $2^{2^n}$ is primitive recursive.

In contrast, it is known that the Ackermann $A(n)$ function is decidable but not primitive recursive. Hence the language $\{ \langle n, A(n) \rangle : n \in \mathbb{N} \}$ is decidable but not primitive recursive.

Consequently, we find that primitive recursive languages sit between Type 0 and Type 1. In other words, every Type 1 language is primitive recursive, and every primitive recursive language is Type 0. Moreover, there are primitive recursive languages which are not Type 1 (for example, any EXPSPACE-complete language), and there are Type 0 languages which are not primitive recursive (for example, the graph of the Ackermann function).


What can I deduce if an NP-complete problem is reducible to its complement?

If an NP-complete problem is reducible to its complement then NP=coNP (why?). Conversely, if NP=coNP then every NP-complete problem is reducible to its complement (why?).


Addition, multiplication, and apostrophe used to represent boolean algebra expressions?

Usually $+$ means $\lor$, "multiplication" means $\land$, and $'$ means $\lnot$.


Binary search uneven split number of queries?

The number of queries in the question is assumed to mean the exact upper bound of the number of queries in the worst case. So, only the worst case is considered except in exercise 3. That is,  the wanted element will be in the "2/3" part after each query.

Suppose we have $3m$ ordered items currently. After a split by ratio 1/3:2/3, we will be left with $2m$ choices. So each query reduces the number of choices by a ratio of $3m:2m=3:2$.

After $k$ queries, the number of choices will be reduced by a ratio of $(3/2)^k$. In order to have only one choice left after $k$ queries, we should have $\frac{n}{(3/2)^k}\approx 1$, where $n$ is the number of original items. So the number of queries, $k$ is about $\log_{3/2}n$. That is the simple intuition.

Of course, the above reasoning is not rigorous since we could have $3m+1$ ordered items. The number of items left after one query will be $2m$ or $2m+1$ (depending on how we round the fractional item), which is approximately $(2/3)(3m+1)$.

Or we could have $3m+2$ ordered items. The number of items left after one query will be $2m+1$ or $2m+2$, which is still approximately $(2/3)(3m+2)$.

It turns out that the number of queries will be between $-3+\log_{3/2}n$ and $1+\log_{3/2}n$ for all $n>1$. So there is not much error to say the number of queries is log of $n$ with base 3/2.

Exercise 1. How many queries are needed if we binary search 26 items with splitting ratio $1/3:2/3$? ( Answer: 6 for floor, 7 for rounding or 8 for ceiling.)

Exercise 2. Write the approximate formula for the number of queries needed if we binary search $n$ items with splitting ratio $1:t$.

Exercise 3. Write the approximate formula for the number of queries needed in the best case if we binary search $n$ items with splitting ratio $1/3:2/3$.


Big O Proof , f(n) = 2n + 1 and I have to prove f(n) is O n^2

It all depends on the case and how easy it is to search $n_0$ or use $c$, in your case you can show that $2n + 1$ belongs to $n^2$, taking the constant $c = 1$, so that in the proof of BigO, $g (n)$ dominates $f(n)$, what is the same $2n + 1 \le c (n^2)\to  2n + 1 \le n^2$; now you can search a $n_0$.


What is the type system (or class of type systems) that that ensures all your tree Branches end in Leaves?

To be honest, I'm unsure about whether this is a CS question or a programming question. There is a strong programming part to it, yet encoding requirements in types requires reasoning on types which is more on the CS side. Anyway, here is an answer.

There are several options to encode that requirement into types.

Basically, we need to encode that each BranchNode has at least one child. This means that a leaf can only be a LeafNode.

A naive approach would be

final class BranchNode<T> implements Node<T> {
    Node<T> firstChild;
    List<Node<T>> otherChildren;
}

We can even keep only a (private) children list, and enforce that using a constructor.

// Make these private
private Node<T> firstChild;
private List<Node<T>> otherChildren;

// Make this to be the only public constructor of the class
BranchNode(Node<T> firstChild, List<Node<T>> otherChildren) {
    children = otherChildren.clone();
    children.add(firstChild);
}

Note the usual caveats, though. One can break this invariant using nulls, non termination, or by creating circular references, e.g. a BranchNode which is its own child (this is easy to achieve if the tree is mutable, for instance). Unwanted subclasses also can break the invariant.

Another option is to exploit the usual Church encoding of algebraic data types into polymorphic types. In theory, this is related to initial algebras and catamorphisms. In OOP practice, this is known as the "visitor pattern".

I'll pretend leaves contain a single int. One can generalize this using generics, as usual.

interface Visitor<R> {
   R visitNode(int data);
   R visitBranch(R firstChild, List<R> otherChildren);
}

interface Node {
   <R> R visit(Visitor<R> v);
}

Pseudo code follows, since Java is too heavy for writing this in a readable way, and I'm not completely familiar with its functional libraries.

class LeafNode implements Node {
  int data;
  visit(v) = v.visitNode(data);
}

class BranchNode implements Node {
  Node firstChild;
  List<Node> otherChildren;
  visit(v) = v.visitNode(firstChild.visit(v),
                         otherChildren.map(_.visit(v)));
}

The advantage of this approach is that the invariant can not really be broken by adding subclasses. One can create a new Leaf2Node subclass, but if that has the same visit(v), it will behave as LeafNode. The implementation of visit(v) in general will be limited by types, and running visit(v) will always (if terminating) end with calling v.visitNode(data) when a leaf is encountered.


How probable is a deadlock in the dining philosophers problem

the dining philosopher problem seems to be somewhat of a pedagogical "toy" example of concurrency and (dead)locking concepts for educational purposes. however it is studied seriously in some literature and there are some performance analyses of its probability of deadlock scenarios. here are some examples of quantitative models and performance analysis and other frameworks on the problem which attempt to consider the probability of deadlocks from theoretical derivations and observed scenarios (simulations etc).

Expected Robustness in Dining Philosophers Algorithms / Galron
Dynamic Lock Dependency Analysis of Concurrent Systems / Schrock
Performance analysis of the dining philosophers
system in dtsPBC / Tarasyuk (Dining Philosophers sec 8.1.3)


Finding containing sets in a set of sets

The right approach will generally tend to depend on your data -- size of sets, number of sets, range of elements, size of input, number of queries etc. Here are a couple of approaches:

Approach 1: You could use a Bloom filter for each of the sets in $A$, and for the input set $I$. Assuming the same number of bits for each set, and the same $k$ hash functions for each bloom filter, you could do a bitwise AND of two filters to do a probabilistic test for subsets. This will give no false negatives, but may give false positives. For example, let $F_I$ and $F_{A_i}$ be the bit-arrays of the Bloom Filters for the input set $I$ and some set $A_i$ in $A$. Then, if $F_{A_i} \cdot F_I = F_I$, then there is a possibility that $I \subseteq A_i$. If they are not equal, then $A_i$ definitely does not contain $I$. Using 64 bit integers, you can quickly perform bitwise AND, and comparison operations on a large number of bits, and so can quickly eliminate sets which do not contain $I$. If they turn out to be equal, then for confirmation, you might then have to check each element of $I$ for presence in $A_i$, where $A_i$ might be a hash set.

One downside of Bloom filters is that addition of elements to the set increases the probability of false positives, and deletion of elements is not possible (in simple implementations) since they introduce false negatives. So for deletion of some integer from a set in $A$, the corresponding Bloom filter will have to be recreated. Also, this method will generally give best results when the size of sets is large enough that querying from hash sets starts becoming slow.

Approach 2: If the number of sets is fairly large, but the data distribution is such that there are relatively few unique integers (what is relatively few will depend on your implementation and requirements), you could store the unique integers instead of the sets. You could have a hash-map where each integer is the key, and the value contains a bit-vector (or list) of the sets to which the integer belongs to. Then, you check each integer of $I$ for presence in the hash-map. If it is not found in the hash-map ($O(1)$), then no set of $A$ contains $I$. Otherwise, keep taking the intersection of the sets associated with the integer being checked, with the sets so far found that contain all elements checked thus far. Thus, the problem boils down to efficient set intersection. If the list of sets in the hash map is a bit vector, you need to perform bitwise AND. If they are a list (say, sorted), you can use an adaptation of merge-sort.


Prove correctess of recurrence result by mathematical induction

We prove by induction that for every $n\in\mathbb{N}$ it holds that $T(n)=2n^2-n$.
The inductive hypothesis is that for all $1\le k<n$ we have:

$T(k)=2k^2-k$.

We proceed to show that $T(n)=2n^2-n$.

By definition, $T(n)=4T\left(\frac{n}{2}\right)+n$. Since $\frac{n}{2}<n$, we can use our inductive hypothesis and obtain $T\left(\frac{n}{2}\right)=2\left(\frac{n}{2}\right)^2-\frac{n}{2}$. After substituting this back into $T(n)$ we have:

$T(n)=4\left(\frac{n^2}{2}-\frac{n}{2}\right)+n=2n^2-n$.


Prove that there exists an undecidable complementary language

Take $\Sigma=\{0,1\}$ for simplicity.

Define $A \oplus B = 0A + 1B$. We have that $(A \oplus B)^c \equiv_m A^c \oplus B^c$ since they differ only by the empty string.

We now take any non recursive $A$, and consider $B = A \oplus A^c$. We have $A \leq_m B$, so $B$ is not recursive as well. Further, $B = A \oplus A^c \equiv_m (A^c \oplus A)^c \equiv_m (A \oplus A^c)^c = B^c$.


The second level can contain other numbers than 2 and 3. See for example

      1
     / \
    2   5
   / \
  3   7
 / \
4   6

It is also unclear if you count isomorphic trees. See this question for a related answer.


First, I assume that it doesn't matter which box a pair of books go into, e.g., the value of book 1 and 2 being in box 1 is the same as the value of book 1 and 2 being in box 2.
Now, denote $B_1, B_2$ as the books in boxes 1 and 2 respectively.  The value of this partitioning is precisely
$$ \sum_{{i,j} \in B_1:\ i<j} p_{ij}+ \sum_{{i,j} \in B_2:\ i<j} p_{ij}= \sum_{{i,j} \in N:\ i<j} p_{ij} - \sum_{i \in B_1}\sum_{j\in B_2}p_{ij}$$
(in words, the value of the paired books in box 1 + the values of the paired books in box 2 = the value of all paired books - the value of the books that aren't paired)

Observe that $\sum_{{i,j} \in N:\ i<j} p_{ij}$ is constant regardless of how you place your books and therefore maximizing $\sum_{{i,j} \in B_1:\ i<j} p_{ij}+ \sum_{{i,j} \in B_2:\ i<j} p_{ij}$ is equivalent to minimizing $\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}$ (as you've roughly stated).

Under this assumption (that the box doesn't matter), we now exactly have a min cut problem.

Let your set of vertices be $N$ (there is no need for a source node to identify which box is which).  We let the graph be complete (there is an edge between every pair of nodes) the value of the edge between $i$ and $j$ is $p_{ij}$.  A cut on this graph is a partitioning ${B_1,B_2}$.  The value of such a cut is $\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}$.  Hence, to find the maximum way to place your books, it suffices to find a minimum cut on this graph.

In the event you want a formulation with terminal nodes (sink/sources), you can add in dummy nodes s and t (denoting box 1 and box 2), connect edges from all books to these nodes with an arbitrary weight W. A partitioning that divides s, t has weight
\begin{align}\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}+\sum_{j\in B_2}p_{sj}+\sum_{i\in B_1} p_{it}&=\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}+|B_2|⋅W+|B_1|⋅W\\
&=\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}+|N|⋅W.\end{align}

In this formulation, a valid cut is $\{s\},\{t,N\}$ with value $W\cdot |N|$ and therefore to ensure at least one book goes in each box, $W$ needs to be made large.

There is one final component of your problem we have not addressed, i.e., there is a set of books $S_1$ that MUST go into box 1 and a set $S_2$ that MUST go into box 2.

Off the top of my head, I do not see a way to fix this without incorporating a source and sink $s$ and $t$ (for box 1 and 2 respectively).  The formulation I've given above is almost sufficient.   If $j\in S_1$ (book j MUST go into box 1), make $p_{sj}$ arbitrarily large (much more than $W$).  This ensures an arbitrarily large cost will be charged if you try to but a book that must go into box 1 into box 2.  Similarly, if $i\in S_2$, make $p_{jt}$ arbitrarily large.

Assuming $S_1$, and $S_2$ are non-empty (that books are already forced into each box), $W$ can be taken as 0 (since a proper partition is enforced by $S_1,S_2$) and $p_{sj}=p_{it}$ for $j\in S_1, i\in S_2$ can be as little as $\sum_{{i,j} \in N:\ i<j} p_{ij}$ (assuming each $p_{ij}\geq 0$).


Assuming you know what leftmost and rightmost derivations are, let $S \Rightarrow^*W_1W_2\dots W_m$ be a derivation (a sequence of replacement using derivation rules), where $W_i$ is a terminal or nonterminal symbol. Then the string $W_1W_2\dots W_m$ is a sentential form of a grammar $G$. In addition, if $W_1W_2\dots W_m$ contains only terminal symbols then it is called a sentence.

If the derivation $S \Rightarrow^*W_1W_2\dots W_m$ is leftmost (rightmost) then the sentential form $W_1W_2\dots W_m$ is called left-sentential form (right-sentential form).

  Is the concept "sentential form" so different from the concept "derivation"

Yes, these are different concepts. A derivation is a sequence of replacements of nonterminals using derivation rules given as a part of grammar, while a sentential form is a string over terminals and nonterminals. You generate/derive/obtain sentential form using derivation (process).

Example:

$S \rightarrow aSa \mid bSb \mid \epsilon$

Derivation: $S\Rightarrow aSa \Rightarrow abSba \Rightarrow abbSbba \Rightarrow abbbba$

Sentential form: $abbSbba$.
Sentence: $abbbba$ (since it has no nonterminal)


Succinct data structure for "bookkeeping problem"

Let's suppose that there the occupancy rate is 25%. Then given an array of $n$ elements, there are ${ n \choose 0.25n}$ possible bitmaps. The theoretical minimum number of bits per entry that you need is, then:

$$\lim_{n \rightarrow \infty}\frac{1}{n} \log_2 { n \choose 0.25n } \approx 0.81$$

At 5%, the minimum number is:

$$\lim_{n \rightarrow \infty}\frac{1}{n} \log_2 { n \choose 0.05n } \approx 0.29$$

Note that I didn't actually calculate it this way. I used the binomial entropy function:

$$B(p) = -\left(p \log_2 p + (1-p) \log_2 (1-p)\right)$$

Then $B(0.05) \approx 0.29$.

So given a 25% occupancy rate, there is no data structure which compresses better than 80% of the size of the uncompressed bitmap.

Given that it sounds like you have a real problem to solve, does shaving 20% off the size of the bitmap seem like a reasonable benefit, given that the cost is likely to be a much higher-constant-factor data structure?

Besides, 1kB just isn't that big. It's a fraction of a page in size, and likely to be in cache most of the time if this is really your inner loop.

EDIT

OK, if you really need this, I suspect that succinct hashing might be your best bet. There are dynamic bitmap data structures which support the rank operation, but none of them have constant time queries to my knowledge.


Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?

The class $LOG_{CF}$ is in fact the class of regular languages $R$ (and thus have all of the regular languages closure properties).

$R\subseteq LOG_{CF}$ is trivial, so we'll concern ourselves only with the the other direction.

Let $A$ be some PDA, and let $s(n)$ be the maximal stack size of $A$'s run on a length-$n$ word.
First notice that if $s(n)=O(1)$, then $L(A)$ is regular (you can always encode a finite set of stack configurations into a NFA).

We will claim that if $s(n)=\omega(1)$, then $s(n)=\Theta(n)$, thus there can't be any PDA which is guaranteed to use non-constant sub-linear space.

We define Automaton-Sub-Configuration to be a tuple $(q,x)\in Q\times \Gamma^*$ such that currently the automaton is in state $q$, and the top of his stack (the suffix of the stack word), is a word $x\in\Gamma^*$.

Now if $s(n)=\omega(1)$, there has to be some automaton sub-configuration, $(q',x')$, for the such that:

$(q',x')$ can be reached unbounded number of times, and on every time it is reached, the stack size grows by at least one symbol.

Let $w_0\in \Sigma^*$ be a word such that the automaton would reach $(q',x')$, and let $w_1$ be a word such that when reading $w_1$ out of $(q',x')$, the automaton ends at $(q',x')$ with at least one additional symbol in the stack.

Finally, consider the word $w=w_0\cdot w_1^k$. Notice that the automaton stack size after reading $w$ is (at least) $k$, while $|w|=|w_0|+k|w_1|$, hence the stack size could be linear in the length of the word.

The conclusion is that for any PDA $A$, $s(n)=O(1)$ or $s(n)=\Theta(n)$.


Uniform convergence for a class of finite dimension

The keyword to look for is Dudley's chaining integral, see e.g. Vershynin's book "High Dimensional Probability" which contains a chapter on the chaining technique. Chaining allows us to bound the empirical Rademacher complexity in terms of the empirical $L_2$ covering numbers of $\mathcal{A}$. Your result is directly obtained from the chaining integral and a result (which is think is credited to Dudley-Pollard) which relates the $L_1$ covering numbers (irrespective of the distribution) to the pseudo dimension, see e.g. theorem 4.2 in these notes. You still need to go from $L_2$ covering to $L_1$ somehow, this is easy when the functions are binary valued.


Doest sorting accept a dynamic programming solution?

Dynamic programming is an algorithmic technique, algorithms are classified as dynamic programming according to what their high-level structure "looks like", not according to a formal definition. If you really wanted to, you could force some sorting algorithms to fit into the dynamic-programming paradigm.

Let $A[1:n]$ be the array to sort, assume for simplicity that all its elements are distinct, and define $OPT[i]$ as the sorted array containing the smallest $i$ elements of $A$.

According to this definition $OPT[0]$ is the empty array and, if you solve the subproblems in increasing order of $i$, you can recombine them as follows:

$$\displaystyle \forall i=1,\dots,n  \quad\quad OPT[i] = OPT[i-1] \circ \min_{x \in A \setminus OPT[i-1]} x,$$

where $\circ$ denotes concatenation. The optimal solution is in $OPT[n]$. Computing any $OPT[i]$ requires $O(n)$ time, therefore the total time needed is $O(n^2)$. At any point in time, you only need to store one $OPT[i]$, so the space complexity is $O(n)$.

This is essentially an ugly way to describe selection sort.


Adaptive step size constrained to a limited number of iterations

I've come to the conclusion that it's not worth doing for my application, so I thought I would post my progress here for anyone else who might be interested in this same problem.
My more "proper" solution, which does not put any constraints on the differential equation but instead uses an error estimation for the adaptive steps, more like a traditional approach. For anyone dealing with the same problem or interested in a solution here it goes.
For the Euler method we can assume that the error is: $ \varepsilon = c h^2 $, and that $c \approx | \ddot x_t - \ddot x_{t-1}$|. In order to limit the number of iterations we will take we have to make some assumptions about the future. The assumption I made is that we will have some average error when we take an equidistant step, and this error will be constant. So let's define the "future average error" as $\hat \varepsilon = \hat c {\hat h}^2$. Since we assume that the future points will be equidistant we know that $\hat h = l/n$ where $l$ is the remaining length (of time) and $n$ is the remaining number of iterations. We don't know $\hat c$ but after some testing I found that the current average $c$ worked rather well, and an exponentially smoothed $c$ worked even better. Making projections on how $c$ will change based on previous data might yield even better results, but I'm trying to do this with few operations so I don't have time to make any advanced predictions.
Now we have all we need, given the assumption that the best accuracy is reached when the error is constant we can set the two equations equal and get: $c h^2 = \hat c (l/n)^2$ which gives us a step size of:
$h = \sqrt{ \frac{\hat c}{c}} \frac{l}{n}$
This step size alone performs rather well, but we do not have any upper bound on the step size and we will get division by 0 if c is zero (if the acceleration is constant between two points). So we simply introduce a lower bound on c defined by an upper bound on h:
$c_{min} = \hat c ( \frac{l}{n h_{max}} )^2$
After some testing I've found that a good value for $h_{max}$ is $\frac{l}{max(n-1,3)}$
So to recap, for the one who just want to test it the algorithm is as follows:
h_max = length/(max(n-1,3))
c = max(abs( a - a_previous ),c_hat*(length/(n*h_max))^2 )
c_hat = alpha*c + (1-alpha)*c_hat

h = sqrt(c_hat/c)*length/n

where a and a_previous is $\ddot x_t$ and $\ddot x_{t-1}$ for the differential equation. If you implement this it's important to remember that length and n is the remaining length and iterations, not the total, so it needs to be updated every iteration. It's also important to note that c_hat is updated with the current c value, I found this to yield much better results.
On to why I don't think it's worth it. During my testing I got a maximum of a 40% decrease in Mean Squared Error compared to the "true" solution (evaluated using many many more points). The error for the final point however was often worse than simple equidistant evaluation, even for 'simple' differential equations like y' = a -y. It was only for differential equations which varied a lot (like those with sinusoidal solutions) which gave an improvement in the accuracy of the final point, and since I'm mostly interested in the accuracy of the final point I think it's worth spending those computational resources on doing more iterations rather than adapting the step size. I can probably cram in twice the number of evaluations instead of doing adaptive step sizes which in my testing was always better than the adaptive strategy.
For anyone who wishes to test this further, the main reason why this method doesn't perform as good as one might expect is because of how $\hat c$ is evaluated. Since it's based on previous values (and heavily skewed toward the current value) the algorithm holds off on small step sizes which often is detrimental to performance. Trying to predict how $\hat c$ will actually look in the future would probably yield much better results and it would be a good place to start exploring further.
TLDR;
If you have this problem, just spend the computing resources on more iterations (or higher order methods) instead of advanced methods to adapt the step size.