A "packing" optimisation problem with application in dynamic programming

Yes.  This can be solved in polynomial time using a straightforward dynamic programming algorithm.  You build a table $A[\cdot,\cdot]$ where $A[i,m]$ denotes the maximal value of $f_1(n_1)+\dots+f_1(n_i)$ subject to the requirement that $n_1,\dots,n_i$ be a partition of $m$, i.e., $n_1 + \dots + n_i = m$.  The entries satisfy the following recursive relation:

$$A[i,m] = \max \{A[i-1,m-t] + f_i(t) : 0 \le t \le m\}.$$

You can fill in this array using the recursive relation in $O(kn^2)$ time, which is polynomial in $n$.  Then, $A[k,n]$ contains the answer to your problem.


Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?

Let $L$ be any NP-complete language, and consider what happens when $L_1 = L_2 = L$. Given an instance $x$, by applying $f$ a linear number of times we would get that $x \in L$ iff $y \in L$, where $|y| < n$. Since there are only finitely many strings of length smaller than $n$, we can hardcode the correct answer for these strings, thus obtaining a polynomial time algorithm for $L$.


How do I know the height from recursion tree of $T(n)=4T(n/2+2)+n$?

Suppose that $n = 2^m+4$. Then
$$
\frac{n}{2} + 2 = \frac{2^m+4}{2} + 2 = (2^{m-1} + 2) + 2 = 2^{m-1} + 4.
$$
We conclude that if $n = 2^m+4$ then the height is $m$ (or $m+1$, depending on how you count), with $T(5)$ in the leaves. This shows that for this type of $n$, the height of the recursion is $\log_2(n-4)$ (or $\log_2(n-4)+1$, depending on how you count).

For general $n$, the exact answer depends on the interpretation of $n/2$ — whether you take floor, ceiling, or anything else — but the height will still be very close to $\log_2 n$.


Exit quickly from a maze with a local view of the maze

The fact that the exit is in the bottom right and has coordinates $(49, 49)$, while the player has coordinates $(1,1)$ makes me think that the maze has a fixed size of $49 \times 49$. If that's the case the exit can be found in constant time.
In fact, there is a fixed strategy (i.e., a sequence of moves) that uses a constant number of moves and exits the maze, regardless of the maze layout!
You can construct this strategy as follows: enumerate all possible maze layouts $L_1, L_2, \dots$ (a crude upper bound on the number of mazes is $2^{49^2}$).
You can construct the sequence $S$ of moves iteratively. Initially $S$ is the empty sequence. Then, for each $L_i$ you can extend $S$ as follows:

Assume that the maze layout is $L_i$, and compute the position $p$ in which the player would end up by following the steps in $S$ from position $(1,1)$ in $L_i$.
Find a sequence $S_i$ of at most $49^2$ moves that make the player walk from $p$ to $(49,49)$ in $L_i$. This sequence always exists and can be found, e.g., with a breadth first search from $p$ in the graph induced by $L_i$.
Append $S_i$ to $S$.

The resulting sequence $S$ has length at most $2^{49^2} \cdot 49^2 < 2^{2413} = O(1)$.
Notice that the above algorithm is only needed to construct $S$ once and for all.
An algorithm that solves your original problem can just output the hardcoded strategy $S$, without even looking at its input.


Understanding of Turing's Answer to the Entscheidungsproblem

What Gödel showed is that there is no finite first-order axiomatization of the theory of the natural numbers. What this means is that if you give a finite list of first-order axioms and schemas, then the corresponding proof system won't be able to prove all true statements about the natural numbers. For example, it won't be able to prove its own consistency (this is Gödel's second incompleteness theorem). (A proof system is consistent if it doesn't prove a statement and its converse.)

Turing's machine, when applied to any given finite first-order proof system $\Pi$, will thus be able to prove neither the statement that $\Pi$ is consistent nor its negation.

Of course, this is not a proof that the Entscheidungsproblem itself is unsolvable; perhaps there is an altogether different approach that does work. Turing was able to show that, in fact, no (computable) approach works.


Clarification on interplay between cache line size and read/write sizes

Cache lines always start at a byte address that is a multiple of the cache size, like 0, 64, 128 etc. If you need 8 bytes starting at byte 30, then the cache line containing bytes 0 to 63 will be loaded.

If you need 8 bytes starting at byte 60, then you need bytes from two cache lines, so the cache line from byte 0 to 63 is loaded, then the line from byte 64 to 127. (Since this is more complicated, it very much depends on the CPU how long this will take, usually anything from "a little bit longer" to "a lot longer". Compilers will usually try to align data to minimise the cost of data straddling cache lines).

Sometimes the cache line size is bigger than the amount of bytes that can be read from RAM in one operation (say 64 byte vs 32 bytes). Some CPUs can then read the "right" 32 bytes first and deliver the data to the CPU, while the rest of the cache is being loaded. So if you want bytes 40..47 the CPU may be able to load bytes 32..63 first, then give the 8 bytes to the CPU while loading the second half.


You seem to have chosen a strange metric, in that your wheelchair user apparently prefers travelling 1000km over concrete to even 1cm over gravel.

However, in general, the way to proceed is to combine your two metrics into a single metric in such a way that even the best possible score on the secondary metric can't make the algorithm prefer a path that does worse on the primary metric.

So, I'm going to assume that each edge $e$ has a quality $q_e$ and a length $\ell_e$.  The quality will be a nonnegative integer; the length can be a nonnegative real (or integer – it doesn't matter). Because Dijkstra likes to minimize, I'll take $q=0$ to be the best possible quality (in the question, you take it to be the worst, but this makes no real difference).

Any path between two vertices can't possibly have length more than $L = \sum_{e\in E} \ell_e$.  This means that, for any path of total length $\ell$, $\ell/(L+1)<1$.  We'll take the weight of the edge $e$ to be $w_e = q_e + \ell_e/(L+1)$, and use these values $w_e$ to run Disjkstra's algorithm. The point is that if a path has total quality $Q$, then it has total weight $W$ with $Q\leq W<Q+1$.  Therefore, the least-weight path is guaranteed to be one of the  best quality paths (smallest $q$-values) and, among those, it's the one of least total length.


Which one grows faster asymptotically: $\log(\log^an)$ or $\log^a(\log n)$

Assuming $\log^a n$ means $\log n$, raised to the power $a$:

Let $t = \log \log n$, then the first expression equals $t·a$, while the second expression equals $t^a$. For $a > 1$ the latter grows faster, for $a < 1$ the former is faster, and for $a = 1$ they are identical.


Poly-time reduction is not antisymmetric

By definition, a relation $R$ is antisymmetric if $aRb$ and $bRa$ implies $a=b$. Therefore, to show that $R$ is not antisymmetric, we have to find $a \neq b$ such that $aRb$ and $bRa$.

Specializing this to your case, you have to find two different languages $L_1 \neq L_2$ such that $L_1 \leq_p L_2$ And $L_2 \leq_p L_1$. Finding a pair of such languages isn't too challenging, so I leave it to you.


Practicality of compressing data with hashing algorithms

This idea is not practical, because there are some serious problems:

You have to calculate all interesting hashes (less than hash length, here 128 bits), which is infeasible.
There must be a way to tell apart compressed and not compressed strings, so some kind of terminator or escape sequence must be introduced.
Since hash functions are designed with avalanche effect (small change in the input should yield huge difference in the output) there are no shortcuts for computations.
The preimage resistance prevents from fast reversing, given hash calculate the input, this also gives another problem, once the data is compressed, the decompression also requires full hash -> input mapping.
The hash signature is quite specific, there are almost none naturally occuring natural texts with such substrings.
If you want to use them in cascade it will be greedy approach, optimal one would require to calculate all cases to given depth and choose the smallest
Multiple hashing algorithms enhance the additional description sequence, now the simple one bit (compressed or not) is not enough, it should also encode which algorithm was used.
With collisions, the number of available hashes of given length decreases. The guarantee of better hash increases the complexity (both time and code).

The idea itself may be tempting, but it is not practical enough to be used in the common compression software, this tells quite a lot.

Please see also Compression with PRNG and Collision free hashes to compress and the compression of random data


Online Learning Resources for Discrete Mathematics

There is a whole course being offered by Udacity*, Logic and Discrete Mathematics, which has interactive quizzes and homework assignments.

The course description is as follows:

  This course presents key concepts in discrete mathematics, specifically, elementary propositional logic and elements of enumerative combinatorics, elementary number theory, and graph theory, with partially ordered sets and lattices as a unifying concept.

*I am not affiliated with them in any way, but I have taken some of their prior courses


How can I make my algorithm more efficient or Is there a better way to solve the problem

Your attempt runs into a huge problem with the input [1, 2, $2^{63}$].

Either your numbers are so small that it doesn’t matter. Otherwise, you start with a solution, find its speed and why it is slow, and then iteratively improve it. That’s usually a much better method than hoping that someone does the work for you.

For this specific problem, I think that for any algorithm you give someone will be able to come up with input that makes it behave badly. So I would try to find what are typical inputs and design a solution for those.

With the given restrictions, if the numbers are unique, I’d probably turn the number into a bit array, so to find all multiples of k only max / k numbers need checking. If k is tiny, check the elements of the original array. If k = 1 return the number of array elements. And cache the results.

For example to count the multiples of 1,234 you’d check if bits 1,234, 2,468, 3,702 etc are set which would be 800 checks or so. If large numbers are allowed the solution would be awful.


Prove $\{xy: x \in A \land y \in B \land |x| = |y|\}$ is context-free

There are many ways to prove this. Here is another one, which proves a stronger result: $A \diamond B$ is linear.

Suppose that both $A,B$ are languages over a common alphabet $\Sigma$. Let $\langle Q_A,q_{0A},\delta_A,F_A \rangle$ and $\langle Q_B,q_{0B},\delta_B,F_B \rangle$ be DFAs for $A^R$ (the reverse of $A$) and for $B$. We construct a linear grammar with a nonterminals $\{S\} \cup Q_A \times Q_B$, with the following rules:

For every $f_A \in Q_A$ and $f_B \in Q_B$, the rule $S \to \langle f_A, f_B \rangle$.
For every $q_A \in Q_A$, $q_B \in Q_B$, and $\sigma_A,\sigma_B \in \Sigma$, the rule $\langle \delta_A(q_A,\sigma_A), \delta_B(q_B,\sigma_B) \rangle \to \sigma_A \langle q_A, q_B \rangle \sigma_B$.
The rule $\langle q_{0A},q_{0B} \rangle \to \epsilon$.

In fact, your proof also shows that $A \diamond B$ is linear, since $\{a^n \# b^n : n \geq 0 \}$ is easily seen to be linear, and all the closure properties you use also hold for linear languages.


Church–Turing thesis and infinite Turing machines

The Church–Turing thesis is the following philosophical claim:

Our intuitive notion of computability coincides with the mathematical notion of computability.

Here the mathematical notion of computability states that a language is computable if some Turing machine computes it, and the intuitive notion of computability is necessarily vague.
Turing machines with infinitely many states can compute any language (exercise), and so are more powerful than the usual Turing machines, which can only compute computable languages. We know that not all languages are computable. Indeed, almost all languages are uncomputable, since there are only countably many computable languages, but uncountably many languages. Also, certain concrete languages such as the Halting Problem are known to be uncomputable.


How do compilers implement symbolic (rather than textual) insertion?

The Java compiler reads the files you listed with the import statements to see the definitions. For historical reasons C compiler doesn't do this and prefers to get everything in one file, hence the preprocessor.

In the end, there is no magic. If you want to make sure at compiletime that the functions that you're calling exist, then the compiler has to see the definitions. Dynamic languages like Python don't do this check, so they have to see less of the code.


Which algorithm for predicting the next word(s) based on previous words, given a sentence?

You can use anything you like.  Right now neural networks are the state of the art: they produce the best predictions.  But you could also use HMMs, or n-grams, or other methods; they just will be lower quality than a state-of-the-art neural network.


Is a set $B = \{y, \exists x \in A, f(x)=y\}$ recursive if A is a recursive set and f is a $N->N$ total computable function?

In general, no, we can't conclude that $B$ is recursive. We can choose $f$ so that $B$ is the halting problem, for instance.

To do that, choose any TM $M_0$ which halts on the empty input.

We define $f(x)$ as follows. Let $M,n$ be such that $\langle M, k \rangle = x$ where
$\langle -, - \rangle$ is any computable pairing function (bijection).
Then, run $M$ on empty input for $k$ steps. If that halts, return $\langle M \rangle$, otherwise return $\langle M_0 \rangle$.

It is then easy to verify that, using such $f$, we have

$$
\begin{array}{ll}
B &= \{ \langle M' \rangle \ |\ \exists M,k. f(\langle M,k \rangle)= \langle M' \rangle \}
\\
&= \{ \langle M' \rangle \ |\ \exists k. M' \mbox{ halts in $k$ steps } \}
\\
&= \{ \langle M' \rangle \ |\ M' \mbox{ halts} \}
\end{array}
$$

With some more effort, we can even make $f$ injective, yet obtain the same $B$ (halting problem).

Indeed, a well-known result states that any RE nonempty set $A$ is the image of some total computable function $g: \mathbb N \to \mathbb N$. For the halting problem $A$ is infinite and RE, so there is such a $g$. Exploiting $g$ we can define $f(x)$ as $g(y)$ where $y$ is the least number such that $\{g(0),g(1),\ldots,g(y)\}$ contains exactly $x+1$ (non-duplicate) elements.

Note that $y$ exists since the image of $g$ ($A$) is infinite.

In such way the image of $f$ is the same as the one of $g$, i.e. $A$, but $f$ is now injective by construction. ($f$ is not surjective, of course)


Optimization of Church-encoded booleans in System F

Without further assumptions you cannot perform the optimization because it is unsound in general. For example, we could interpret System F in a model that has fixed point operators, in which case there will be elements of Bool that are different from false and true (namely "undefined" ⊥). In such a model, dumb will not be equal to \ b . false because dumb ⊥ = ⊥ but (\b . false) ⊥ = false.

In your question you assumed that we know what it means to "optimize" a function. If we leave aside questions about efficiency, we still have to answer the question what it means for two closed terms in System F to be equal. There are several possibilities:

closed terms $M$ and $N$ are equal if they reduce to the same normal form,
closed terms $M$ and $N$ are equal if they are equal in some preferred model,
closed terms $M$ and $N$ are equal if they are observationally equivalent,
closed terms $M$ and $N$ are equal if they are extensionally equivalent (they give extensionally equivalent results when applied to extensionally equivalent arguments).

Parametricity, which was mentioned in the comments, may be helpful with some of the above. But it's difficult to discuss "optimization" until we know what counts as "equal", or else we cannot tell which optimizations are valid.


Construct a deterministic finite automation

Hint: Here is a regular language which "accepts" exactly $n$ members of $\{0,1\}^n$ for every $n$: $0^* 1 0^*$. For example, for $n=4$ we have the strings $0001,0010,0100,1000$. The minimal DFA for this language contains three states.


Raft algorithm: What's the meaning of concept `index`?

TL;DR Just as said by Yuval Filmus, a log index in Raft algorithm is just an integer that tells the position of a log entry in a series of log entries.

Here is a figure that show clearly the meaning of an index of a log entry in Raft algorithm. The figure is taken from the award-winning paper In Search of an Understandable
Consensus Algorithm by the creaters of Raft algorithm.

This usage of index is in accordance with the most common usage of index as in mathematics and computer programming, which is "a value that identifies and is used to locate a particular element within a data array or table" as said in its entry in dictionary.com. You can also check index notation.

Specifically, a log index in Raft algorithm is used by each server to identify the log entry that is numbered with that index in that server's log. All (indices for) committed log entries will always be consistent across all servers having those entries. Non-consistent (indices for) log entries across servers will be replicated or repaired, depending on the situations.

"For web developer, index usually refers to database index." It looks like that you come with a training in computer databases. As a web developer myself, I would not agree with you readily at all. Indices are used much more frequently to access array elements in everyday programming in just about every programming language. For example, in JavaScript, if there is an array persons=["alice", "bob", "Diego"], then we can use index 1 to access its second element "bob", persons[1]. You will find the same or similar usage that are also abundant in Java, C, C++, C#, Python, Ruby, Go, etc.

If you want to understand Raft algorithm, one of the best introductory material is the video presented by Diego Ongaro.


Find the origin and the destination of a trip from a serie of tickets

Using a hash table, record for each city mentioned how many times it was mentioned as a source and how many as destination. The source of the trip is the city that has appeared as a source an odd number of times, and similarly for the destination of the trip. That's linear time and space (with high probability).

Also, as Jan comments, the statistic that should be odd is the total number of times that the city has appeared. If a city appeared an odd number of times, then it is the source if it appeared as a source more than as a destination, and vice versa for destination.


Looking for cheat sheet to J.C. Reynolds symbols

You aren't going to find a list of all notations ever used. Apart from a few standard notations, each paper will define the notation that it uses.

This paper is from the dark ages of typewriter typesetting, so the typographic quality is subpar. The character ε stands for $\in$, which is the standard mathematical notation for set membership.


Does the complement of sigma Kleene star exist?

Note that the complement of $A \subseteq \Sigma^*$ is defined as $\Sigma^* \setminus A$; so yes: the complement of $\Sigma^*$ itself is the empty set.

To be completely accurate, you need to state with respect to which universe you want to take the complement. For instance, if you were to take the complement of $\Sigma^*$ w.r.t. $\Sigma'^*$ where $\Sigma' = \Sigma \mathbin{\dot\cup} \{a\})^*$, $a \not\in \Sigma$, it would not be empty but $\Sigma'^* \cdot \{a\} \cdot \Sigma'^*$ (the set of words with at least one $a$).


Hint: What $L \in \mathsf{NP} \cap \mathsf{coNP}$ means is that if $x \in L$ then there is a witness for this, and if $x \notin L$ then there is a witness this. From these witnesses for $L_1,L_2$ you can easily construct witnesses for $L_1 \oplus L_2$. A witness for $x \in L_1 \oplus L_2$ would be:

A witness for $x \in L_1$ and a witness for $x \notin L_2$; or
A witness for $x \notin L_1$ and a witness for $x \in L_2$.

A witness for $x \notin L_1 \oplus L_2$ is similar and left as an exercise.

More generally, if $L_1,\ldots,L_k \in \mathsf{NP} \cap \mathsf{coNP}$ and $\phi$ is any function on $k$ inputs, then $\phi(L_1,\ldots,L_k) \in \mathsf{NP} \cap \mathsf{coNP}$ (defined analogously to $L_1 \oplus L_2$), for similar reasons.


BIT: Unable to understand update operation in Binary index Tree

If you don't stick to the claim of "switching all 1's to 0's and 0's to 1's" (I am also confused) in that post, here is the simple bitwise trick for updating used in the original paper "A New Data Structure for Cumulative Frequency Tables" (Figure 5) by Peter Fenwick (Ix for index).

Repeat:
Tree[Ix] := Tree[Ix] + val;
Ix := Ix + BitAnd(Ix, -Ix);    // add the least-significant one
Until Ix >= TableSize

That is, the nodes accessed via a left link upward from the original node i can be calculated by
i += i && -i.

i && -i is the least significant bit of i. i += i && -i moves you to the ancestor that is closest to the right side of i. This is the next node you will need if you want to add all the nodes to the right of i.

In your example, i = 5_(10) = 101_(2). The first i && -i gives 001 and i + i && -i moves you to node i' = 110_(2) = 6_(10). The second i' && -i' on i' gives 010 and i' + i' && i' moves you to node i'' = 1000_(2) (which is too large).

For an example with 31 nodes and i = 9 = 1001, you will access the following nodes: i' = 1001 + 0001 = 1010, i'' = 1010 + 0010 = 1100, and i''' = 1100 + 0100 = 10000 (which is too large).

By the way, in the case of query, the bitwise trick is simply modified to i -= i && -i. It is easy to verify that this trick agrees with the procedure of "Clearing the rightmost 1 bit". Also see the related post here.


Partitioning vertices in a bipartite graph according to minimum vertex covers

The following idea comes from a Chinese blog.

Find a maximum matching $M$ ($2m$ vertices and $m$ edges) firstly. For convenience, for a vertex $v$, we denote by $M(v)$ the vertex that is matched with $v$ in $M$, and denote by $N(v)$ the set of neighbors of $v$.

We have the following observations:

All vertices not in $M$ must belong to $\mathrm{Never}$.

Proof. Suppose a minimum vertex cover contains a vertex $v$ not in $M$, to cover the $m$ edges in $M$, the vertex cover must also contains another $m$ vertices, so the size of the vertex cover is at least $m+1$, which contradicts to Kőnig's theorem.
If a vertex $v$ in $M$ belongs to $\mathrm{Always}$, then $M(v)$ must belong to $\mathrm{Never}$.

Proof. Suppose a minimum vertex cover contains both $v$ and $M(v)$, to cover the rest $m-1$ edges in $M$, the vertex cover must also contains another $m-1$ vertices, so the size of the vertex cover is at least $m+1$, which contradicts to Kőnig's theorem.
If a vertex $v$ belongs to $\mathrm{Never}$, then $N(v)$ must be a subset of $\mathrm{Always}$.

These observations lead us to the following algorithm:

A = A[0] = empty set
N = N[0] = all the vertices not in M
i = 0
while True:
    i = i + 1
    A[i] = empty set
    for each vertex v in N[i - 1]:
        temp = N(v) \ A
        A[i] = union(A[i], temp)
        A = union(A, temp)

    if A[i] is empty:
        break

    for each vertex v in A[i]:
        add M(v) into N[i]
        add M(v) into N

After the execution of this algorithm, all vertices in A belong to $\mathrm{Always}$ and all vertices in N belong to $\mathrm{Never}$. For those rest vertices, we partition them into two sides by intersecting respectively with $L$ and $R$, where $L$ and $R$ are respectively the two sides of the bipartite graph. We can see either side along with the vertices in A forms a minimum vertex cover, so these vertices belong to $\mathrm{Exist}$.


Memory Addressing - Alignment Clarification

Let's take a sample address, written in binary: 110100100110.

Now let's compute it modulo 2, 4, 8, 16, writing the answer in binary:

mod 2: 0
mod 4: 10
mod 8: 110
mod 16: 0110

(I recommend checking this.)

Hopefully you can connect the dots now.

As an additional hint, let's do a decimal example: 987348957943 mod 100 = 43. Why? Since the $i$th digit from the right (counting from 0) is "worth" $10^i$, so all the digits other than the two on the far right are "worth" some multiple of 100.


Is this a correct way to show that a problem is coNP-complete?

No, the steps are insufficient. You need to use a Karp reduction, since that's the type of reduction used in the definition of coNP-completeness.

SAT is NP-complete, but probably not coNP-complete (unless NP=coNP); and coSAT is coNP-complete, but probably not NP-complete. This distinction would be lost if you used Cook reductions.

Some questions on this site which are relevant are this one and that one, as well as a few others.


First of all, I believe that chess algorithms look more than 2 plies down, although they don't consider all different possibilities; pruning the search tree is very important to avoid the combinatorial explosion in the number of possible moves.

For a game like chess, there are three possibilities as to the identity of the winner: either player 1 has a winning strategy, or player 2 has a winning strategy, or both players draw under optimal play. It is not known which is the case for the game of chess. However, since chess is a finite game, there is a computer algorithm, consisting of a very large table, which plays chess optimally.

Of course, such an algorithm wouldn't be practical. But for some simpler games, the "value" of the game (which player wins, if any) has been determined, and an optimal algorithm has been devised. Such a game is known as a solved game.

The mathematical subject that deals with (what are known as) combinatorial games is combinatorial game theory. Mathematicians have developed a recursive method to determine the value of a game given the graph of the game, which includes all the allowed positions and moves. You should be able to find a description of this algorithm in the Wikipedia entry or any lecture notes on the subject.


How is memory address applied to address pins in RAM chips

Actually those 4 dots mean repeat. This means there are $2^{20} = 0x0FFFFF = 1,048,576$ memory cells, each with a line from the decoder. A few too many to draw them all.

Each of the lines from the decoder to a cell is an enable line. If not enabled the memory cell will do nothing (and have any output lines set to the data bus high impedance). If enabled the memory cell will read and write as you would expect.


What is the upper bound on the number of nodes in a tree with n leaves where each internal node has at least two children?

Is there a way to find the upper bound on the total number of nodes in the tree?

Yes. There is actually a formula for the exact number: see e.g. these notes:

A full $m$-ary tree with $l$ leaves has $n = \frac{ml - 1}{m - 1}$ vertices and $i = \frac{l-1}{m-1}$ internal vertices.

Here, $m$-ary means that every internal node has between $1$ and $m$ children, and full means that every internal node has exactly $m$ children (the maximum). So in your case, for a full binary tree, just plug in $m = 2$ to these formulas.

By the way, to derive such formulas, you can count the number of vertices in the tree in two ways. First, they are either internal or leaves, so
$$
n = i + l
$$
Second, we can obtain the total number of vertices by adding up the number of children over all nodes, plus the root, so
$$
n = 1 + \sum_{v \in V} \text{children}(v) = 1 + mi,
$$
because each internal node has $m$ children and leaves have no children.
Now set the two equal and we have
$$
i + l = 1 + mi,
$$
from which we can derive the above results.


What is usually the next step after showing the VC dimension?

A distinction should be made between constructing practical machine learning algorithms and theoretical algorithms, such as PAC learning algorithms. A machine learning practitioner doesn't usually invoke the concept of VC dimension — indeed, many of them probably have never heard of it, especially if they're applying machine learning in some other subject. While VC dimension might be useful in coming up with algorithms (as in the case of SVMs), it appears to have no practical import.

When constructing theoretical algorithms such as learning algorithms under the PAC model, the story could be different, but unfortunately I don't know too much about that. From the little I've seen, VC dimension doesn't get mentioned even there. In fact, it seems that VC dimension is mentioned mostly in literature attempting to relate it to other parameters.


Are logarithmic Big-O complexities defined with constant base equal to those defined with variable base?

Let's look at the root of question: we have  $\log_2 n=\frac{\ln n}{\ln 2}$ and $\log_t n=\frac{\ln n}{\ln t}$, so $\log_2 n = \frac{\ln t}{\ln 2} \log_t n$ and when $t$ is constant, then logarithms are in same complexity class.
Bit if $t=t(n)$, then we can ruin this relation and create any class $O(f(n))$ of complexity taking $t(n)=e^{\frac{\ln n}{f(n)}}$ we have $\log_t n=\frac{\ln n}{\ln t}=f(n)$.


Which is better, Flood Fill or Scanline Fill algorithm ?

They have different purposes.

Flood fill implies that you have a graph with neighbours and a starting node. You need a data structure to hold the frontier of nodes you still have to fill (and possible one for all the nodes you have visited). But each node is visited exactly once.

Whereas the scanline implies that you have points in a coordinate system. Each point you visit may add new points of interest further along. You need a data structure to hold the sorted points.


Rice's Theorem - usage on $DFA$ or $LBA$

If when you say  "$M$ is a $LBA$ (or $DFA$ or $PDA$)" you mean that $M$ has a fixed decidable structure (i.e. some properties of its internal state/transition structure) that forces its behaviour to be like a $LBA$ (or $DFA$ or $PDA$) then Rice's theorem cannot be applied directly.

For example, if "$M$ is a $DFA$", is formally defined as "$M$ has no left moves and always enters a halting state on the first blank symbol whatever the current state is" then

$ALL_{DFA} = \left \{ \langle M \rangle \mid \text{$M$ is a DFA and $L(M) = \Sigma^*$} \right \}$ is decidable

Note that even if "$M$ is a $LBA/PDA$" is formally defined using some decidable properties of the structure of $M$, the sets $ALL_{LBA}$ and $ALL_{PDA}$ are undecidable but the proof cannot rely on Rice's theorem: it must use the LBA/PDA ability to "parse" a valid partial computation trace (tape+state) of an arbitrary Turing machine $M$.


What happens if there is context switch while executing system call?

If the kernel decides to do a context switch, it's in response to some event which caused the processor to enter kernel mode. This can be either a system call or an interrupt (which can be a timer interrupt or some other interrupts).
Whether the kernel is processing an interrupt or a system call, there are good and bad times to do a context switch. The kernel does what it wants to do, and then at the end of the processing it decides which user thread to schedule next. If it decides to schedule a thread which wasn't the last scheduled thread, it then does a context switch.
During critical parts of the processing, the kernel may disable interrupts. If an interrupt happens while the kernel is already active and doesn't have interrupts disabled, what usually happens is that the kernel does what needs to be done immediately (for example, read data from a peripheral), and adds an element to a queue to remember what needs to be done later. In Linux, these are called the “top half” and “bottom half” of interrupt processing; I don't think there's a standard term even though the concept is common. For example, if a network interrupt is triggered while the kernel in the middle of communicating with a disk, the kernel reads the network packet and stores it into a queue; then, when the disk I/O is finished (or can be paused), the kernel processes the network packet, and at this point it may decide to schedule a task that has received some input from the network.
In case there's any doubt, a timer is not required for a context switch. A context switch can happen any time a system call is in progress. The connection between timers and context switches is that if user code never makes any system call, and there is no system event (user input, networking, etc.) that causes an interrupt, the only way a context switch can happen is if a timer interrupt causes the kernel to wake up. And there are operating systems that only have non-preemptive multitasking; such kernels don't set a timer interrupt, and only do a context switch during a system call.


Can I use Θ if tightest lower and upper bound are not the same?

When analyzing the asymptotic running time of an algorithm where the tightest lower bound and upper bound are not the same, is it bad to denote the running time in theta notation?

Do you mean to say that we can only prove an $\Omega(f_1)$ and an $O(f_2)$ bound, respectively, on the same cost function (such as "worst-case running time)? Then yes: you can only use $\Theta(f_1) = \Theta(f_2)$ to combine the bounds if, well, $f_1 \in \Theta(f_2)$.

If you mean to say that best case and worst case have different growth rates, then that's a different issue: "lower bound" and "best case" as well as "upper bound" and "worst case" are not the same concepts! You can have $\Theta$-bounds for either case, but they still don't combine in a meaningful way since they are talking about different cost functions.

  Also, if an algorithm has a running time of theta(n), is it safe to assume that the upper and lower bound are the same?

That's not a "safe assumption", that's the definition of $\Theta$.

I suggest you revisit the definitions of the different Landau symbols and the basics on how to use them in algorithm analysis. Maybe start reading at our reference question.


I don't know whether your problem is feasible, but here is another way to express it, in the language of linear algebra instead of the language of DAGs.

The upper bound on the path length means that each output vertex depends on at most $2^{27}$ input vertices... which is technically a constant.

Your problem is equivalent to the following:

Input: a matrix $M$, a vector $c$
Question: do there exist vectors $x,y$ all of whose entries are 0 or 1, such that $y=Mx+c \pmod 3$?

In your particular case, we are guaranteed that each row of $M$ has at most $2^{27}$ non-zero entries, and you're asking whether this is sufficient to make the problem feasible.  I don't know the answer to that.

Here is the equivalence between your formulation based on DAGs, and the linear algebra formulation above: we think of each non-input vertex as summing (modulo 3) the two inputs entering it, so it represents an addition (modulo 3) gate.  Suppose the two numbers on an input gate are $a,b$.  Then we can equivalently think of the input vertex as accepting a zero-or-one input variable $x$, and outputting $(b-a)x + a$ (modulo 3).  Note that $b-a$ and $a$ are known constants, so an input vertex computes an affine function of the corresponding zero-or-one input variables.  As a result, we have one zero-or-one input value per input vertex, and one output value per output vertex, and we are hoping that all the output values will be zero or one.  By unfolding the summations, we see that each output value is the sum (modulo 3) of at most $2^{27}$ expressions of the form $\alpha_i x_i + \beta_i$ where the $\alpha_i,\beta_i$ are known constants and the $x_i$ are the zero-or-one inputs.  That then leads to the reformulation I listed above.


Prove that every regular subset of $a^nb^n$ is finite

This is a simple application of the pumping lemma. Suppose that $L'$ is an infinite subset of $L$. Given $p$, since $L'$ is infinite, there exists some $n \geq p$ such that $w = a^nb^n \in L'$. Let $w = xyz$ be a decomposition of $w$ such that $|xy| \leq p$ and $y \neq \epsilon$. Then $y = a^t$ for some $t \neq 0$, and so $xy^0z = a^{n-t}b^n \notin L'$. Therefore $L'$ is not regular.
One might be tempted to think that this argument generalizes to every $L$ whose non-regularity can be proved using the pumping lemma. However, this is incorrect, as the example of $L \cup c^*$ shows.
This raises the following intriguing question:

For which infinite languages $L$ is it the case that all regular subsets of $L$ are finite?


I'm researching related ideas using context-free grammars at the moment, so I might be able to give you some things to think about by describing the approach I've taken (which is just one approach).

Firstly, I use rules that describe the production of multisets and not sequences (or trees in fact). So whereas a conventional production rule:

$s \rightarrow abc$

would produce the (ordered) string 'abc', the rule below would produce an unordered set of the same symbols

$s \rightarrow \{a, b, c\}$

In such a grammar non-terminal symbols can operate as variables in the same way as sequential grammars, e.g.:

$
s \rightarrow \{X, c\}\\
X \rightarrow \{b, a\}
$

Now, going back to 2D images. Perhaps surprisingly, it turns out you can encode an image as an (unordered) collection of non-terminal symbols, each producing a (unordered) multi set that describes each pixel. In your question you describe a set of terminal symbols that describes that possible values of each pixel, let's say $\Sigma=\{0,1\}$. I'm going to add to that 2 terminal symbols $x$ and $y$, each of which representing an offset of 1 pixel from the origin on each axis, so  $\Sigma=\{0,1, x, y\}$.

Now consider the pixel $A[2,2] = 1$. This can be encoded in the grammar scheme I describe using a multi set production:

$p \rightarrow \{x, x, y, y, 1\}$

So, you could encode a whole image this way. It's easy to imagine the amount of bloat you'd get in such a grammar. However, it is possible to compress the whole grammar by using a hierarchy of production rules that can be inferred. For example, take the derivation of the point $A[18, 9]=1$

Instead of:

$p \rightarrow \{x, \text{(repeat 17 more times)}, y, \text{(repeat 8 more times)}, 1\}$

you can have:

$p \rightarrow \{D, A, G, y, 1\}\\
A \rightarrow \{x, x\}\\
B \rightarrow \{A, A\}\\
C \rightarrow \{B, B\}\\
D \rightarrow \{C, C\}\\
E \rightarrow \{y, y\}\\
F \rightarrow \{E, E\}\\
G \rightarrow \{F, F\}\\
$

With of course the non-terminals $A$ to $G$ being reused to describe multiple points. So actually something that looks like it would be hideously inefficient can be compressed very efficiently. It is possible to easily infer such a grammar from a series of points (this is the subject of my research), using similar techniques as normal sequential grammar inference.

The cool feature of this type of grammar is it is possible for the grammar to encode complex patterns that are non-sequential (in this case graphical) in nature.

This is all a work in progress but it might help you with your problem.


I want to know where there is the flaw in my argument

accepts if $M$ doesn't halt on $x$

That's not something a Turing machine can do in general: informally, keep in mind that accepting has to happen at some finite stage while we can't in general tell that a program isn't going to halt in finite time (which is why HP is undecidable).

Your $M'$ is implicitly treating a co-r.e. event (non-halting) as r.e. (so that it can wait for it to occur and, when it does, halt and accept).

It's worth noting that we can do this with $HP$ as an oracle, and this shows (correctly) that $L$ is r.e. over $HP$. But we have to be careful about what exactly that means. At first glance we might think that "r.e. over $HP$" implies r.e., since $HP$ itself is r.e., but when a set is presented as an oracle we get both positive and negative information about it. So r.e. over $HP$ - that is, the domain of some $HP$-computable partial function - is not the same as r.e.: for example, $\overline{HP}$ is r.e. over $HP$.

This is a good example of how we have to keep track of the various different reducibilities we might be using, with the relevant ones here being Turing versus many-one: in the context of this question we're interested in many-one reductions but oracles correspond to Turing reducibility.


What's the time complexity of Monte Carlo Tree Search?

According to http://stanford.edu/~rezab/classes/cme323/S15/projects/montecarlo_search_tree_report.pdf

  Time Complexity
  The runtime of the algorithm can be simply be computed as
  $O(mkI/C)$
  where $m$ is the number of random children to consider per search and $k$ is the number of parallel searches, and
  $I$
  is the number of iterations and
  $C$
  is the number of cores available.

  Memory Complexity
  The memory complexity is
  $O(mk)$ since in each iteration we map
  $mk$
  states over the cluster.


Neither the code you have nor the Wikipedia article highlight the concept of selection sort. Therefore, consider this (functional) pseudocode:

def selection-sort []         = []
|   selection-sort x::xs as l =
      let m = min l
      in
        m::(selection-sort (delete m l))
      end;

Here the idea is more clear

    $\ \ $1. Select the minimum from the list and delete it.
  $\ \ $2. Sort the remainder recursively.
  $\ \ $3. Prepend the minimum.

 The same works the other way around with the maximum, obviously.

Iterative code on arrays works slightly differently -- but the idea remains the same.


What are the most expressive, terminating languages?

There are plenty of classes of programming languages where all programs terminate. The most common form of enforcing termination is by way of types. The most well-developed theory of typing systems for terminating computation might be that of Barendregt's Lambda cube, which decomposes typing into three orthogonal axes:

Parametric polymorphism
Higher kinds
Value-dependency of types

Starting from a terminating languages such as the simply typed $\lambda$-calculus, one can add any combination of those three axes and retain termination.

This has close connections with logic, via the Curry-Howard correspondence.

There are many extensions and refinements, including types that capture complexity classes.


Determine if the sequence of numbers is a post order traversal of a binary tree

Probably you consider binary search trees, otherwise the exercise is a little useless.

You already concluded that your input has postorder: post-left-subtree, post-right-subtree, root.
Now the value of the root determines which values belong left, and which values belong right. So you are right: this is divide and conquer. Split the numbers according to the subtrees, and repeat for each of the two subtrees.

If a split of the input does not have the form post-left-subtree < root < post-right-subtree, you know what to conclude from that.

An example. The sequence is 1, 5, 9, 7, 3, 13, 17, 15, 11.
So the root is 11. And we can split the sequence accordingly into left and right subtrees: 1, 5, 9, 7, 3 < 11 < 13, 17, 15. Continue with the left and right subsequences.

Another sequence is 1, 5, 13, 9, 7, 3, 17, 15, 11. No split 'at' 11 possible.


Why does the formula 2n + 1 find the child node in a binary heap?

I would like to propose my revisited version of Hiroki's answer.
Currently it's been sitting in peer-review (https://cs.stackexchange.com/review/suggested-edits/66932) for a while, so it's not being of use to anyone.
Credits to Hiroki for the original answer and structure.
I've simply clarified the math and made every step explicit and chosen a slightly different terminology.

Let's assume that each tier of the heap is an array.
T1 [                n0                 ]

T2 [      n1,                n2        ]

T3 [  n3,     n4,       n5,       n6   ]

T4 [n7, n8, n9, n10, n11, n12, n13, n14]

It may not be clear, but I want you to imagine that $n0$ is the parent of $n1$ and $n2$.
Likewise,  $n1$ is the parent of $n3$ and $n4$.
For example, $T2$, the second tier, contains nodes $[n1, n2]$ and has length $2$.
Let's say $i$ is the global index of the node in question (i.e. the node's index if the entire tree were to be collapsed within a single array), and
$j$ is the local index of the node, i.e. the index of the node within its tier.
For example, in the diagram above, if the node in question is $n3$, $i = 3$ and $j = 0$, because $n3$ is the first element in the 3rd tier.
i = global index of a node n
j = local index of a node n within the tier where the node exists
T = tier

The maximum number of nodes in a tree up to a certain tier can be expressed by:
$total\_nodes\_up\_to(T) = 2^T - 1$
e.g. when you have 3 tiers, you can have at most 7 nodes, as $2 \cdot 2 \cdot 2 - 1 = 7$
This is because there are $2^{T-1}$ nodes in each tier (note: tier numbering in our example arbitrarily starts from $1$, not $0$) and the sum of powers of $2$ up to $n$ is equal to $2^{n+1} - 1$, as you can see here https://math.stackexchange.com/questions/1990137/the-idea-behind-the-sum-of-powers-of-2
Since indexes start from 0, the index of the last node in an array of nodes will be $numNodes - 1$. This means that the global index of the last node in some tier $T$ is:
$i_{last} = total\_nodes\_up\_to(T) - 1 = 2^T-1-1$
While the local index of the last node in the tier is:
$j_{last} = 2^{T-1} - 1$ // since there are $2^{T-1}$ elements in tier $T$
We can now compute the global index of the first node in the tier by subtracting the local index of the last node in the tier from its global index. You can visualize it mentally as "walking backwards" starting from the the last node - if you take local-index-many steps back you land onto the first node in the tier:
$i_{first} = i_{last} - j_{last}$
$i_{first} = 2^T - 1 - 1 - j_{last}$
$i_{first} = 2^T - 1 - 1 - (2^{T-1} - 1)$
$i_{first} = 2^T - 2^{T-1} - 1$
$i_{first} = 2*2^{T-1} -2^{T-1} - 1$
$i_{first} = (2 - 1)*2^{T-1} - 1$
$i_{first} = 2^{T-1} - 1$
We can now compute the global index of a node $n$ by adding its local index and the global index of the first node in its tier:
$i = i_{first} + j$
$i = 2^{T-1} - 1 + j$
Let's now think about the first (left) child of the node in question.
The left child, n', will be in the next tier, T+1.
The indices in T+1 will be referred to as i', j', i'_first ...

Based on what we've shown so far, we can say that the global index of the first node in the next tier is:
$i_{first}' = 2^{T+1-1} - 1 = 2^T - 1$
Now, for each predecessor of the parent node $n$ in tier $T$ there will be 2 predecessors of left-child node $n'$ in $T+1$. Also, given index $j$ in $T$, we know there are $j$ predecessors of $n$ in $T$ - i.e. the index of a node is equal to the number of its predecessors. So we can conclude that:
$j' = 2j$
Putting it all together, we can conclude that
$i' = i_f' + j'$
$i' = 2^T - 1 + 2j$
Now let's rework the previous equation for the global index of parent node $n$, $i = 2^{T-1}-1+j$ to the following:
$i + 1 = 2^{T-1} + j$
Finally, let's compare that to the equation of the global index of the left-child node:
$\begin{align}
i' &= 2^T - 1 + 2j\\
   &= 2*2^{T-1} + 2*j - 1\\
   &= 2*(2^{T-1} + j) - 1\\
   &= 2*(i + 1) - 1      \text{//NOTE: Here we use $i + 1 = 2^{T-1} + j$ mentioned above}\\
   &= 2i + 2 - 1\\
   &= 2i + 1\\
\end{align}$
Although the question was why the $2n + 1$ formula works, note that I used $i$ instead of $n$!
Let me know if there is anything unclear.


Where can I find rules for source to source transformation optimization rules?

Martin Feather's thesis and papers (and similar theses from the 70s) are full of examples of
such rules for functional languages.  See http://dl.acm.org/citation.cfm?doid=357153.357154. (pdf)  Most of the formal types like such (functional) rules.

More recent would be any work by Martin Ward using his functional language WSL including his thesis.   See http://www.cse.dmu.ac.uk/~mward/martin/papers.

If I were you, I'd look to the Haskell community, which is always trying to optimize functional programs, and particularly to the Haskell compilers which implement many of these ideas.

But I get the impression you're looking for the the book of program optimization rules.  There are some pretty standard ones based basic algebra as applied to integers, etc.
And you can see a bunch of these coded explicitly for DMS in an example of how to define algebra to a program transformation system: Algebra as a DMS domain.

You aren't likely to find "the general book" for the following reasons:

Every syntax formalism in which rules are represented makes a choice about how to write down the details of the rules.  Nobody has agreed on a universal notation; that's not a flaw of software engineering, the mathematicians haven't figured this out yet either.  So any rules you find will be cast using a particular encoding scheme.  Unless you get the tool that uses this encoding scheme, you probably can't use the rules. (See the algebra example for a specific encoding scheme.)
"Optimizations" are essentially about equivalent sequences of operations where one sequence is "cheaper" than another by some metric (smaller number of steps, less computation, less memory, less heat, less code, ...)  The number of entities for which you can define operations is boundless:  booleans, naturals, floats, strings, structs, crossproducts, linkedlists, arrays, arbitary compositions of the above, each with predicates possibly constraining them to a subset (eg., all naturals less than 10).  The number of operations you define is equally boundless.  Which ones are worth writing down?
A variation on the above theme is that the syntax and semantics of the programming languages you want to manipulate are egregiously different (did we really need both Java and C#?), or deeply semantically different (COBOL and Prolog, for example), or just outright egregious complex (consider C++11).  So your rules need to be case in a form that is dependent on your target language syntax and semantics.  And there are thousands of those.
Source to source transformations seem to offer nirvana, but they have limitations. In particular, most ways you can represent a transformation to be matched against code, what it can match has a limited radius of the match.  If your optimization needs information from "far away", e.g., beyond the radius of what you can write in the rules, no single rule can realize your optimization.  You can only succeed by composing more than one rule (and you can succeed spectacularly in theory because Post systems are Turing capable, and most rewrites are Post systems almost trivially).   However, writing long strings of transformations to achieve an effect is much like writing long sequences of Turing machine steps: you really, really don't want to do that.  So in practice transformation systems usually offer the ability to compose arbitrary code procedures, and source transformations, that make "bigger" source-to-source transformations.  So now your real transformations are mixed code and rewrites.  Using code from one of those thousands of programming languages. (oops).

My belief (uh-oh, opinion coming up) is that source-to-source transformation tools are really useful, because you can build program manipulation engines with them more easily (by a lot!) than with any procedural code or any other techniques I know about.  The differences in syntax and semantics of the target languages means you are pretty much doomed to not find such transformations off the shelf (well, you can pray for C++ to become stable for 20 years, and then maybe you have a chance).  So, what is needed is a system which will let you define the rules you need, for the language you want to manipulate, relatively easily, when you need them. (And I've spent the last 18 years of my life building such a system).

Good luck finding the universal ruleset.


Does Dijkstra's Algorithm actually check nodes marked as visited?

It depends on the implementation, but generally those edges are considered, but the algorithm immediately notices the target node is already visited or the new distance is greater than the old one, and doesn't process the edge further.


Efficient way to concatenate strings to find specific split up values

If all the words are going to be English words, you can run all the words through a dictionary. If you find any non-dictionary words at the start or end of the sections and you are unable to find the "key", you can just combine those words until the key is found.

Alternatively, you can trivially just combine the the words (once) at the start/end of sections until the word is found. I don't believe this will to too inefficient computationally since the described sections are quite large.


Yes.  It's always possible, if $s,t$ are at hamming distance one from each other.  Let $s,t$ be your two strings at distance one from each other.  Then there exists a Gray code sequence where they are adjacent in the Gray code sequence, say $s$ appears right before $t$.  Now you immediately obtain a valid solution.  Find where $t$ appears in the Gray code sequence, and start going through strings in the Gray code sequence until you get back to $s$.  This will have the property you want, as a Gray code sequence is a cyclic sequence where every adjacent pair of strings has hamming distance one.

How do you find that Gray code sequence?  There are many possible methods, but here's one easy one.  Note that if you have a mapping $f$ on strings that permutes the order of the bits, and you apply $f$ to each element of a Gray code sequence, you obtain another Gray code sequence.  The same is true for a mapping $g(x)=x\oplus c$ that xors the input with a constant string $c$.  These two facts are enough.  Start with any Gray code sequence of your choice; let its first two strings be $a,b$.  Let $s,t$ be your two strings that have Hamming distance one.  Now you can choose $f,g$ so that $g(f(a))=s$ and $g(f(b))=t$ (namely, choose $f$ to move the bit position where $s,t$ differ to the bit position where $a,b$ differ; and then choose $g(x)=f(a) \oplus s$).  This choice of $f,g$ induces a new Gray code sequence: you start with your original Gray code sequence, and apply $f$ to each element of it, then apply $g$ to the result of it.  The result is a new Gray code sequence whose first two elements are $s,t$.  Thus, if you can iterate through the original Gray code sequence, you now have an easy way to iterate through the new Gray code sequence: you just start iterating at its 3rd element, skipping its first two elements (which will be $s,t$).

The requirement that $s,t$ have Hamming distance one is critical, as otherwise there is a trivial counterexample.  Consider 2-bit strings.  Suppose the two strings you already have are 00 and 11.  Then you want to visit the two strings 01 and 10.  However, it doesn't matter what order you visit them in: you won't obtain a solution of the form you want.  In particular, there are only two possible sequences (01,10 or 10,01), and neither one has the hamming-distance-one property you wanted.


Prove that context free languages aren't closed under DropMiddle

First off, you are right about looking for a counter example. However, $ww$ is a dead end, since no matter what you add to the middle, you'll stiil have a language that is not context-free.

Hint 1: If the middle character is in some way special in $L$, you can essentially modify a PDA for $L$ to nondeterministically guess the middle and the removed letter and it will accept $\operatorname{DropMiddle}(L)$. So you should try to look for a language, where the dropping makes the middle special.

Hint 2: If the specialness of the middle is the only feature of $\operatorname{DropMiddle}(L)$, a PDA could just use its stack to determine the middle. So you need to force it to use the stack in a different way.

Solution:

   $L = \{ aw_1aw_2aw_3a\ldots aw_na \mid w_i\in \{(,)\},~ w_1\ldots w_n \text{ is correctly parenthesized} \}$.

 The $w_i$ part forces any PDA for $L$ or $\operatorname{DropMiddle}(L)$ to use its stack to count open parens. Thus it is impossible to check if, the single missing $a$ after dropping is indeed missing from the exact middle of the word.

 Formally proving that $\operatorname{DropMiddle}(L)$ is not context-free should be doable with Ogden's Lemma.
Choose a word $(^k)^k(^k)^k$ (plus the $a$s inbetween) and mark $k$ characters each left and right of the middle.


Finding the values for a particular bucket in a list

You should use the Quick Select algorithm. I will spare you the details and let you look up the algorithm on your own if you do not know it, but quick select roughly does the following:

Given a list A of size n and and index i, the algorithm will return the ith smallest element of A. Additionally, A will be such that this ith element is in index i, all element earlier in the array are less than or equal to this element, and all later element are greater than or equal to this element. And it does this in O(n) time!

So, just use this algorithm twice on the two indices (you will need to restrict which part of the array you are using for the second query and change the index appropriately, but you can work this out), and you will get what you want! Hope that helps.

Here is a link to the Quickselect Wikipedia article (I have not read it to verify its accuracy): http://en.wikipedia.org/wiki/Quickselect


Software code generation from the (operational) semantics - reference request for automatic programming

I haven't seen anything on this but the closest I could find is Evolving Algebras:

Evolving Algebras: An Attempt to Discover Semantics
Evolving Algebras: Mini-Course
Communicating Evolving Algebras

In that mini course there are several papers outlining different aspects and applications of the Evolving Algebra. From one of them:

  In 1988 Yuri Gurevich has discovered the notion of evolving algebra in an attempt
  to sharpen Turing's thesis by complexity theoretic considerations (see
  [22]). Through numerous case studies (see [4] for an annotated list which is
  complete up to 1994) it has become clear since then that using the notion of
  evolving algebras one can develop a powerful and elegant specication methodology
  which has a huge yet unexplored potential for industrial applications. In
  this report we are going to explain the basic concepts of this approach to the design
  and analysis of complex systems and illustrate its salient features through
  a challenging example from real life.

They also talk about successive refinement and hierarchical modeling.

Maybe if you could describe more on what you're trying to accomplish with the code generation part that would be helpful. It sounds like you are wondering about generating/forming a verified program from cognitive reasoning somehow, automatically generating the operational semantics. I haven't seen anything on that.


No. I was writing an answer based on vertex and edge counts, but then I realised that there's a simpler argument: the de Bruijn graph of strings of length $n$ over an alphabet of $m$ symbols has $m$ self-loops, whereas a hypercube has none.


if an argument of a lambda only passes itself if it is further evaluated, is runtime always finite?

(This is not a proper answer, but I wanted to share some thoughts)

To have a definitive answer one would need to precisely define what's allowed and what's not.

I noticed this, however, which perhaps could help. The term $M = \lambda xy. x(xy)$ is typeable in the simply-typed lambda calculus, which is strongly normalizing.

Instead, your other two examples, $\lambda xy. (xy)x$ and $\lambda xy.(yx)(yx)$ are not typeable in STLC.

Perhaps exploiting this, and formalizing everything precisely, one can indeed prove that using $M$ "alone" does not lead to non termination. It's hard to say, since the STLC constrains the calculus significantly.


What is the effect of operating systems on execution speed?

This question doesn't have a straight forward answer, or rather the answer is very case dependent.  (And as some of the comments pointed out, attempting to qualify this as MHz is meaningless, your CPU will run at the same speed regardless {not counting power optimizations}, it's just a case of who's code it's running, yours or the OS's).

An operating system does many things for you so your simple code that does a couple of I/O operations wouldn't be as simple without calls to the operating system.  To take the OS out of the equation, you'd have to write more code to replace device driver functionality.  Your OS is doing a LOT of work just to accept that letter "A" you typed and display it on a screen.

If your I/O is to a file system, you'd have to write code to replace the file system code provided for you by the OS.

If you expect multiple tasks to run simultaneously or do multithreading, you'll also have to write code to replace the scheduling functionality.

If you allocate and deallocate memory, you'd have to write code to perform those functions.

If you want your program to be notified when an event occurs or keep time or any of a number of other functions, you'll have to supply all that code as well.  And that's just PART of what an Operating System is doing.

You also have to consider that all that OS code that you're taking advantage of has been optimized and debugged for you.  You're likely to write replacement code that is buggier and slower than the OS code you're replacing.

Then once you've got all that written, you'll have to figure out how to load the program into memory and start execution...

That said, there definitely IS overhead involved in using an operating system.  Most OS's are built for a general use case and will have many features and functions that you don't need for your specific program.  But most of us are willing to give up a few % of CPU and memory in order to get the convenience that an OS will bring.

As for which OS will make it go faster... again it depends on your application and needs.  Some OS's will definitely run some applications faster than others, but which OS runs faster depends on the features being used.

And there are reasons other than speed to choose one over another.  Application availability, security, interoperability, device compatibility, availability of programming tools, etc. are all factors to consider.


A $\mathsf{P^{NP}}$ machine can solve $\mathsf{coNP}$ problems: it can query an $\mathsf{NP}$ oracle, and then return the opposite answer. This is not something that you can obviously simulate with an $\mathsf{NP}$ machine.

More concretely, you can construct $\mathsf{P^{NP}}$ machine which gets a formula as input, accepts if the formula is unsatisfiable, and rejects if the formula is satisfiable. How would you implement this as an $\mathsf{NP}$ machine? We only know how to construct witnesses for satisfiability (namely: a truth assignment), but not for unsatisfiability.


NP-hardness of language of graphs with $\alpha(G)=n/3$

1-IN-3SAT is the following problem: given a 3SAT instance, determine whether there is a truth assignment in which each clause contains exactly one true literal. It is known that 1-IN-3SAT is NP-complete.
Given an instance of 1-IN-3SAT, construct an instance of your problem in which each clause corresponds to a triangle, and contradicting literals are connected by edges. Details left to you.


Check if two separate ranges have some number in common

You can get $\tilde{O}(NM)$ preprocessing time and $O(1)$ time per query.

Assume for simplicity that $N$ and $M$ are powers of $2$.
For each index $i = 1, \dots, n$ and $h = 2^0, 2^1, \dots, 2^{\log N}$, let $A[i, h]$ be the set of the elements in positions from $i$ to $i + 2^h -1$ in $A$. Define $B[j, k]$ similarly.

Let $R[i, h, j, k]$ be true if $A[i,h] \cap B[j, k] \neq \emptyset$ and false otherwise.
You can compute each $R[i, h, j, k]$ in constant time by exploiting the following relations:
$$
R[i, h, j, k] = R[i, h-1, j, k] \vee R[i + 2^{h-1}, h-1, j, k]  \quad \mbox{for }h>0
\\
R[i, h, j, k] = R[i, h, j, k-1] \vee R[i, h, j + 2^{k-1}, k-1]  \quad \mbox{for }k>0$$

where $R[i, 0, j, 0]$ is true iff the i-th element of $A$ equals the $j$-th element of B.

There is an intersection between the elements of A in positions $i, i+1, \dots, i+\ell_A - 1$ and the elements of B in positions $j, j+1, \dots, j+ \ell_B - 1$ iff the following condition is true:
$$
R[i, h, j, k] \vee R[i + h, h, j, k] \vee R[i, h, j + k, k] \vee R[i + h, h, j + k, k],
$$
where $h = \lfloor \log \ell_A \rfloor$ and $k = \lfloor \log \ell_B \rfloor$.


A (binary) code $C$ is a collection of binary strings of some length $n$, known as codewords. The minimal distance of $C$ is the minimum Hamming distance between (different) codewords. Hamming codes have minimum distance 3, which means that (1) every two codewords differ in at least 3 places, (2) there exist two codewords which differ in exactly 3 places.

Hamming codes are examples of an important class of codes known as linear codes. You can think of linear codes in many ways:

A linear code of length $n$ is a linear subspace of $\{0,1\}^n$. The dimension of the code is known as the rate $k$.
A linear code is a code which is closed under XOR, that is, the XOR of any two codewords is again a codeword. It turns out that the number of codewords is always a power of 2, say $2^k$. The parameter $k$ is known as the rate.
A linear code is a way of encoding $k$-bit messages using $n$ bits. The original bits of the message are put in fixed places, and every other bit is an XOR of a certain fixed subset of the message bits. For example, the SEC(7,4) code encodes a 4-bit message $x,y,z,w$ using 7 bits:
$$
x \oplus y \oplus w, x \oplus z \oplus w, x, y \oplus z \oplus w, y, z, w
$$

The minimal distance of a linear code is also the minimal Hamming weight of a non-zero codeword. So the fact that Hamming codes have minimum distance 3 means that (1) every non-zero codeword has at least 3 ones, (2) there exists a codeword having exactly 3 ones.

We have mentioned three parameters: the length of the code $n$, the rate of the code $k$, and the minimal distance $d$. There is no exact relation between these three parameters, though there are various  bounds relating the three quantities. One of these bounds is the Hamming bound:
$$
\sum_{\ell=0}^{\lfloor \frac{d-1}{2}\rfloor} \binom{n}{\ell}\leq 2^{n-k}.
$$
For example, for the SEC(7,4) code this gives
$$
\binom{7}{0} + \binom{7}{1} \leq 2^{7-4}.
$$
You can check that equality holds, and indeed this is the case for all Hamming codes. Codes for which equality holds are called perfect codes. Apart from a few trivial and exceptional cases, Hamming codes are (essentially) the only perfect codes.


If a DFA can be simulated by a real program, can it be simulated by a TM

Assuming the same limited view on computation as Turing machines, then yes: typical programming languages are Turing complete and thus (for all we know) equivalent in power to TMs.

A simpler proof presents itself, too: if you look closely enough, finite automata are just Turing machines that don't use their tape.

Keep in mind, though, that Turing machines lack some features of modern real machines/languages: distributed computation (i.e. communication), user interaction, online algorithms and never terminating systems with continuous I/O (e.g. operating systems) are just some examples. If your simulation program uses such features, the simulation may not carry over to TMs.


Single Source Shortest Path: What does the weights on the vertex and edges tell you?

In this example, the numbers on the edges are "given" - they are weights of the edges of the graph in which you want to compute the shortest paths from the source vertex S to all other vertices.

The rest of the information on this graph is the result of the shortest path computation (though this slide doesn't give the algorithm used to compute it - the algorithm is given in subsequent slides).

The result consists of two parts:

The numeric value of the shortest distance from S to each other node. Every node is labeled with its shortest distance. E.g. it's 0 for S itself, -2 for C, 8 for D, etc.
The "shortest paths tree", which allows to reconstruct the actual shortest path to any vertex, not just the length of the path. More on it below.

The actual shortest paths are encoded in a peculiar way, relying on the fact that if you take all edges that participate in at least one shortest path from S to some other vertex, you'll get a tree. Here's why:

Take any vertex - e.g. B. The shortest path from S to B is S-C-A-B. The vertex A is B's "predecessor" ("parent") in this path. For a fixed vertex S, obviously each other vertex has a predecessor (parent). On this picture, "X's predecessor is Y" is denoted as $ X.\pi = Y $.

What's a structure where each vertex has a parent? It's a tree! So we obtain a tree of shortest paths. This tree is a subset of the graph's edges. On your picture, the edges included in this subset are highlighted with red color.

This tree can be used to reconstruct the shortest path from S to any vertex. E.g., for vertex D, its parent is B, B's parent is A, A's parent is C, C's parent is S, so we get S-C-A-B-D.

Note that this tree construction relies on a certain (rather obvious) property of shortest paths: for any vertex, the shortest path to it goes through the shortest path to one of its adjacent vertices.


How to prove that in an AVL tree with height h, the depth of every leaf node is at least $\lceil h/2 \rceil$

Denote by $d(h)$ the minimum height of a leaf in an AVL tree of height $h$. One subtree of the root necessarily has height $h-1$, and the other one has height either $h-2$ or $h-1$ by the defining property of AVL trees. Therefore
$$
d(h) = \min(d(h-1),d(h-2)) + 1.
$$
Also, one checks that $d(0) = d(1) = 0$ (if one measures height as the maximum number of edges in a root-to-leaf path). The recurrence makes it clear that $d$ is monotone, and so $d(h) = d(h-2) + 1$. From here it's easy to calculate $d(h) = \lfloor h/2 \rfloor$.


Determine if there is a path with alternating edge colours in directed graph

Let's construct a new graph $G'$.

Every vertex $u$ from $G$ will become a pair of vertexes in $G'$, namely $u_{blue}$ and $u_{green}$ (index stands for the color of incoming edge).

Edge $u_{c_1}\rightarrow w_{c_2}$ in $G'$ exists iff

There is an edge $u \rightarrow w$ in $G$ colored $c_2$
$c_1 \ne c_2$

Now it's easy to see that every path in $G'$ corresponds to a color-alternating path in $G$ (and the converse is also true), i.e. color-alternating path from $v$ to $u$ in $G$ exists iff there is path from $v_{c_1}$ to $u_{c_2}$ in $G'$ for some $c_1, c_2$.


NFA for words which start and end with different letters with $O(\log(| \Sigma |))$ states

The original question referred to DFA (and not NFAs). However, no DFA for $L$ with $O(k)$ states exists.
Consider $\Sigma$ as a set of words (i.e., each word consists of a single  character from $\Sigma$).
Given any two distinct words $a,b \in \Sigma$, the word $a$ is a distinguishing extension for $a$ and $b$. I.e., $aa \not\in L$ but $ba \in L$.
This shows that the number of equivalence classes of $L$ w.r.t. the equivalence relation "not having a distinguishing extension" is at least $|\Sigma|$.
By the Myhill-Nerode theorem, any DFA for $L$ must have at least $|\Sigma|$ states.

The idea to build a NFA with $O(k)$ states is as follows:
in addition to an initial state $s$, and to an accepting final state $t$ there are $2k$ states indexed with $1, \dots, 2k$.
Assign a distinct integer $x_a$ from $0$ to $2^k-1$ to each character $a \in \Sigma$ and consider the binary string $b_a$ of length $2k$ obtained by concatenating the binary string of length $k$ representing $x_a$ in binary, with its complement.
For each character $a \in \Sigma$ let $S_a$ be the set of all states $i$ such that the $i$-th least significant bit in $b_a$ is $1$, and define $\overline{S}_a = \{1, \dots, 2k\} \setminus S_a$.
For each $a \in \Sigma$, add the following transitions:

A transition from $s$ to each state $i \in S_a$.
A transition from each state $i \in \{1, \dots, 2k\}$ to itself.
A transition from each state $i \in \overline{S}_a$ to $t$.

Given a word $\sigma_1, \sigma_2, \dots, \sigma_n$ with $\sigma_1 \neq \sigma_n$, let $i$ be an index such that the $i$-th least significant bit of $b_{\sigma_1}$ is $1$  while the  $i$-th least significant bit of $b_{\sigma_n}$ is $0$ (such an index always exists).
Then, $s \to i \to i \to \dots \to i \to t$ is an accepting path in the NFA.
Conversely, any accepting path is of the form $s \to i \to i \to \dots \to i \to t$ for some $i$. This implies that $i \in S_{\sigma_1} \cap S_{\sigma_n}$, i.e., $b_{\sigma_1}$ and $b_{\sigma_n}$ differ (at least) on the $i$-th least significant bit. This shows that $\sigma_1 \neq \sigma_n$.
The number of states of the NFA is $2k+2$.
Here is an example for $\Sigma = \{x,y,z,w\}$. All edges for which no label is shown are actually labelled with $x,y,z,w$.


Karp hardness of searching for a matching split

It is NP-complete. Clearly it belongs to NP. To prove its NP-completeness, we'll reduce not-all-equal 3-satisfiability (NAE3SAT) to this problem.

Given an instance of NAE3SAT with $n$ variables and $m$ clauses, construct a graph as follows:

For each literal $l$, construct a complete graph with $m+1$ vertices $v_0(l),\ldots,v_m(l)$.
For each variable whose positive and negative literals are respectively $l_i$ and $l_j$, add an edge between $v_0(l_i)$ and $v_0(l_j)$.
For each clause $c_i=l_i^1\vee l_i^2\vee l_i^3$, add the following structure:

In addition, for each literal $l$ other than $l_i^1,l_i^2,l_i^3$, add a new vertex $v_i'(l)$ and an edge between $v_i(l)$ and $v_i'(l)$.

Now we assert that the instance of NAE3SAT is satisfiable if and only if the graph has a matching split.

If the instance of NAE3SAT is satisfiable, consider a valid truth assignment. If $l$ is a truth literal, we put $v_i(l)$'s into $A$ and $v_i'(l)$'s (if exists) into $B$ for all $i=0,\ldots,m$, otherwise we put $v_i(l)$'s into $B$ and $v_i'(l)$'s into $A$. In addition, for the structure corresponding to $c_i$ (we assume $l_i^1$ and $l_i^2$ are truth literals while $l_i^3$ is a false literal without loss of generality), we put $v_i^{12}, v_i^{123}$ into $A$ and put $v_i^{23}, v_i^{31}, v_i^{122331}$ into $B$. We can see this partition is a matching split.

If the graph has a matching split, we can observe firstly that $v_0(l),\ldots,v_m(l)$ should be put into the same part since they make up a complete graph (assume $m\ge 2$ without loss of generality). In addition, if $l_i$ and $l_j$ correspond respectively to the positive and negative literals of the same variable, $v_k(l_i)$ and $v_k(l_j)$ should be put into different parts otherwise $v_0(l_i)$ or $v_0(l_j)$ has no neighbor in the other part. If the positive literal corresponding to a variable is put into $A$, we assign the variable to True, otherwise we assign it to False. Note for each clause $c_i$, $v_i(l_i^1), v_i(l_i^2)$ and $v_i(l_i^3)$ cannot be put into the same part otherwise $v_i^{123}$ has either no neighbor or $3$ neighbors in the other part. Hence this assignment is a valid assignment for the instance of NAE3SAT.

Edit: One can simply add edges among $v_0(l)$'s to make the graph connected. For example, if the clauses are $l_1\vee l_2\vee l_3$ and $l_4\vee l_5\vee l_6$, one can simply add an edge between $v_0(l_3)$ and $v_0(l_4)$. The idea is that for a valid assignment, if we flip all the values of variables involved in one connected component, the assignment is still valid. In the example, this means we can always assume $v_0(l_3)$ and $v_0(l_4)$ are put into the same part.


Subset sum problem with many divisibility conditions

This problem can be solved in polynomial time using linear programming, and this is actually true for any partial order $(S,\le)$. By the way, we can prove by induction that for any finite partial order set  $(S,\le)$, there exists a finite set $S'\subseteq\mathbb{N}$ and a bijection $f:S\rightarrow S'$, such that for all $s_1,s_2\in S, s_1\le s_2 \Leftrightarrow f(s_1) | f(s_2)$.

Let $\mathcal{C}$ be the set formed by the chains in $S$. Remind that $C$ is a chain iff for all $v,v'$ in $C$, $v\le v'$ or $v'\le v$

Now create a boolean variable $x_v$ for each $v\in S$, and a boolean variable $y_C$ for each chain $C$. We can write the following linear program $(P)$ for our problem :
$$
\begin{split}
\text{Max} \displaystyle\sum\limits_{v\in S} x_v \\
\text{subject to} \displaystyle\sum\limits_{v\in C} &x_v \le 1, \forall C\in\mathcal{C}\\
                                         &x_v \in \{0,1\}, v\in S
\end{split}
$$

and its dual $(D)$  :

$$
\begin{split}
\text{Min} \displaystyle\sum\limits_{C\in \mathcal{C}} y_C\\
\text{subject to} \displaystyle\sum\limits_{C:v\in C} &y_C \ge 1, \forall v\in S\\
                                         &y_C \in \{0,1\}, C\in \mathcal{C}
\end{split}
$$

Then the problem of finding the minimum cover of an ordered set by chains is the dual of our problem. Dilworth's theorem states that

There exists an antichain A, and a partition of the order into a family P of chains, such that the number of chains in the partition equals the cardinality of A

which means that the optimal solution of these two problems match : $Opt(P)=Opt(D)$

Let $(P^*)$ (resp. $(D^*)$) be the relaxation of $(P)$ (resp. $(D)$) i.e. the same linear program where all constraints $x_v\in\{0,1\}$ (resp. $y_C\in\{0,1\}$) are replaced by $x_v\in [0,1]$ (resp. $y_C\in [0,1]$). Let $Opt(P^*)$ and $Opt(D^*)$ be their optimal solutions. Since $\{0,1\}\subseteq [0,1]$ we have :
$$
Opt(P)\le Opt(P^*) \text{ and } Opt(D^*)\le Opt(D)
$$
and weak duality theorem establishes that $Opt(P^*)\le Opt(D^*)$ then by putting everything together we have :
$$
Opt(P)= Opt(P^*)=Opt(D^*)=Opt(D)
$$

Then, using Ellipsoid method, we can compute $Opt(P^*)$ ( $=Opt(P)$) in polynomial time. There are an exponential number of constraints but there exists a polynomial time separation oracle. Indeed given a solution $X$, we can enumerate all couples $s_1,s_2\in X$ and check if $s_1\le s_2$ or $s_2\le s_1$, and therefore decide in polynomial time whether $X$ is feasible or otherwise the constraint associated to the chain $\{v_1,v_2\}$ is violated.


You know that:

A belongs to NP
B is NP-Complete
C is NP-Complete
If A accepts given word then B accepts this word as well
If we can solve C - we can solve A.

To prove that A is NP-Complete you need to prove that it belongs to NP (which is given to us) and that any problem from NP can be reduced to it (so that it is NP-Hard). To show the second one you need to show a reduction from an NP-Complete problem to A.

The last (5th) of our information basically means you have a polynomial reduction from A to C which is no surprise, since A is in NP and C is NP-Complete (meaning, among others, that every NP problem can be reduced to it, including A). This doesn't give you much about A (it only confirms that A is no harder than C).

The 4th information gives us knowledge like this: if some word belongs to A it also belongs to B, but there are some possible words that belong to B but not to A. In other words, A is a subset of B. This does not gives us much about A either, because A could belong to P only and still be a subset of B (as NP "contains" P).

In my opinion, if I understood this well, this information is not sufficient to say more about the complexity of A.


Actually, bruteforce should work just fine.  You can quickly find a set of taps that doesn't have a full period, then find a value that's not in the period.  Here's what I'd do:

Randomly pick a set of taps (a feedback polynomial).
Verify whether this has a single full period of size $2^{32}-1$, as follows. Randomly pick a starting state $s_0$ (not the all-zeros state).  Iterate forward starting from $s_0$, and see whether you get back to $s_0$ within at most $2^{32}-1$ steps.  In this way, you can compute the period after starting from $s_0$.  If this period is $2^{32}-1$, go back to step 1.
Now you have a LFSR and a starting state $s_0$, such that the full period is less than $2^{32}-1$; next you want to find a state $t$ that is not within the set of states reachable from $s_0$.  Here's one way to do that:

Randomly pick 10 states $t_1,t_2,\dots,t_{10}$.  These will be your 10 candidates for $t$.  Initially, each of them is unmarked.
Now run the LFSR forward, starting from $s_0$, until you get back to $s_0$.  At each step compare the current state of the LFSR to $t_1,t_2,\dots,t_{10}$.  If the current state of the LFSR is equal to $t_i$, then mark $t_i$.
At the end, when you get back to $s_0$, look at which of the $t_i$ are marked.  If one of the $t$'s is unmarked, say $t_j$, then you are done: you have a LFSR feedback polynomial and a starting state $s_0$ such that you know $t_j$ is not within the period of values starting from $s_0$.  If all of the $t_i$'s are marked, go back to step 1.

How long will this take?  Probably about $2^{32}$ operations.  I would expect at least $1/2$ of the choices of feedback polynomials to lead to a LFSR with less than full period, so you shouldn't have to repeat steps 1-2 too many times (on average about 2 times).  Each repetition takes $2^{32}$ operations.

Now once you find a good LFSR, where $s_0$ does not lead to a full period, then the period that's reachable from $s_0$ will be on average about $2^{31}$ or smaller.  Thus, step 3 will take about $2^{31}$ operations.  Also, this means that about $1/2$ of all possible states will be unreachable.  Therefore, with probability $1-1/2^{10}$, at least one of your 10 candidates for the $t$'s will be good, so the chances that you have to repeat step 3 is very low.

So, this is probably good enough.  This is easy to code up and will probably finish within a few hours or less.

There are cleverer things you can do, but they probably don't make sense in practice.  You could spend a bunch of hours thinking hard to write tricky code, to save an hour or two of CPU time -- that's not a good tradeoff.

Nonetheless, since it sounds like you appreciate the math and clever tricks, here are the tricks you could use to make this more efficient.  Let $p(x)$ be the feedback polynomial for your LFSR.  If $p(x)$ is reducible, then the LFSR will certainly not be full period.  In other words, if $p(x)$ factors as $p(x)=q(x) r(x)$, the LFSR won't be full period.  So, you could start by picking two polynomials $q(x),r(x)$ randomly of suitable degree (their degrees must sum to 32, and neither should be a constant), then use their product as the feedback polynomial.

Now once you have a feedback polynomial, there are efficient algorithms to check whether a state $t$ is reachable from starting state $s_0$.  This basically becomes a discrete logarithm problem in $GF(2^{32})$, which can be solved very efficiently.  See, e.g., https://crypto.stackexchange.com/q/17970/351.  That said, you wouldn't want to implement those algorithms for this problem.  They are overkill, and much harder to implement than the simple bruteforce approach I outlined above.

If you want to make the problem easier, you could use a maximally factored feedback polynomial, such as $p(x)=(x+1)^{32} = x^{32} + 1$.  Now the all-ones state has a period of 1, i.e., it repeats forever.  So, you can take $s_0=111\cdots 1$ and $t$ to be anything else.  This is a bit of a trivial example, so it might not be what you are looking for.


Why can't we use a hash tables for collision resolving in hash tables?

The method you propose is, as far as I know, the historically first one for "perfect" hashing in linear space. In perfect hashing, lookup takes $O(1)$ time in the worst-case. (Recall that in most simple hash tables, lookup takes $O(1)$ time only in expectation.)

The idea is to use chaining (rather than open addressing), but make each chain a hash table of size $\Omega(m^2)$ where $m$ is the number of items in the bucket.

This is sometimes called "FKS", after the initials of the inventors. Here are some freely available resources:

"Universal and Perfect Hashing" by Avrim Blum
"Storing a Sparse Table with $O(1)$ Worst Case Access Time" by Fredman et al.
"Dynamic perfect hashing" (Wikipedia) supports dynamic insertion and deletion with expected amortized $O(1)$ time, in addition to (like other perfect hashing algorithms) $O(1)$ worst-case lookup time.


The claim is false. Let $f(n) = n^{1.75}$ and $g(n) = 2^{\lfloor \log_2 n \rfloor} n$, and note that both are increasing. When $n = 2^t$, we have $g(n) = n^2$, while when $n = 2^t-1$, we have $g(n) \approx n^{1.5}$. This shows that
$$
\liminf_{n\to\infty} \frac{f(n)}{g(n)} = 0, \quad
\limsup_{n\to\infty} \frac{f(n)}{g(n)} = \infty.
$$
In particular, it is not the case that $f = O(g)$, nor is it the case that $g = O(f)$.


Finding square root without division and initial guess

OK, let's go with floating point. Any positive floating point number is of the form $m \times 2^e$ where $m$ is in the range $[1,2)$ and $e$ is an integer.

If $e$ is even, then:

$$\sqrt{m \times 2^{2p}} = \sqrt{m} \times 2^p$$

And if $e$ is odd, then:

$$\sqrt{m \times 2^{2p+1}} = \sqrt{m} \times \sqrt{2} \times 2^p$$

We can precompute $\sqrt{2}$. So we have reduced the problem to finding a square root of a number between 1 and 2. So far, so good.

We could use the Newton-Raphson method for square roots, but you specifically didn't want division, and it's a bad idea anyway; division is more expensive than multiplication on a modern FPU.

But we could use the Newton-Raphson method for reciprocal square roots. The iteration looks like this. If $x_0$ is an initial approximation to $\frac{1}{\sqrt{m}}$, then iterate:

$$x_{i+1} = \frac{1}{2} x_i \left( 3 - m x_i^2 \right)$$

When this has converged, $m x_k$ is an approximation to $\sqrt{m}$. No divisions here, and the problem is now just to come up with an initial estimate.

But wait, we can do better.

Given $b_0 = m$, let's suppose we could come up with a sequence of numbers $Y_i$ such that $b_i = b_0 Y_0^2 Y_1^2 \cdots Y_n^2$ approaches $1$. Then $x_i = b_0 Y_0 \cdots Y_{i-1}$ approaches $\sqrt{m}$ and $y_i = Y_0 \cdots Y_{i-1}$ approaches $\frac{1}{\sqrt{m}}$. Please pause for a moment and convince yourself that this is the case.

We already know such a sequence, because we can use the Newton-Raphson iteration for reciprocal square roots:

$$b_i = b_{i-1} Y_{i-1}^2$$
$$Y_i = \frac{1}{2}(3 - b_i)$$

And so:

$$x_0 = m Y_0$$
$$x_{i} = x_{i-1} Y_i$$

and:

$$y_0 = Y_0$$
$$y_{i} = y_{i-1} Y_i$$

But observe that $b_i = x_{i-1} y_{i-1}$. So we don't actually have to retain $b_i$:

$$Y_i = \frac{1}{2}(3 - x_{i-1} y_{i-1}) = 1 + \frac{1}{2}(1 - x_{i-1} y_{i-1})$$

Substituting this into the equations for $x_i$ and $y_i$ gives:

$$x_{i} = x_{i-1} \left( 1 + \frac{1}{2}(1 - x_{i-1} y_{i-1}) \right) = x_{i-1} + \frac{1}{2}(1 - x_{i-1} y_{i-1}) x_{i-1}$$
$$y_{i} = y_{i-1} \left( 1 + \frac{1}{2}(1 - x_{i-1} y_{i-1}) \right) = y_{i-1} + \frac{1}{2}(1 - x_{i-1} y_{i-1})y_{i-1}$$

Removing the redundant computation gives:

$$r_i = \frac{1}{2}(1 - x_{i-1} y_{i-1})$$
$$x_{i} = x_{i-1} + r_i x_{i-1}$$
$$y_{i} = y_{i-1} + r_i y_{i-1}$$

But we're not done! We can save the multiplication by a half by substituting $h_i = \frac{1}{2} y_i$.

Given $Y$ as an approxmiation to $\frac{1}{\sqrt{m}}$, set:

$$x_0 = m Y$$
$$h_0 = \frac{1}{2} Y$$

Iterate:

$$r_i = \frac{1}{2} - x_{i-1} h_{i-1}$$
$$x_{i} = x_{i-1} + r_i x_{i-1}$$
$$h_{i} = h_{i-1} + r_i h_{i-1}$$

Then $x_i$ converges to $\sqrt{m}$ and $y_i$ converges to $\frac{1}{2\sqrt{m}}$. Not only does the inner loop have no divisions, it can be implemented on modern FPUs using three fused multiply-adds and nothing else. Perhaps it's unsurprising that this algorithm, known as Goldschmidt's algorithm, is the one used in your FPU.

The final question: How do we come up with $Y$? Well, you could use $\frac{1}{m}$ or something if you want to allow one division. But you said no divisions. So since $m$ is known to be between 1 and 2, you could use its high-order bits to consult a lookup table, or use an interpolating polynomial approximation, such as a Chebyshev polynomial. I'll leave the details of that to you.


Prove that any tree contains a matching of size |InternalNodes|/2

You can prove the following stronger claim by induction:

  Given a rooted tree containing more than one vertex, there is a matching which covers all non-leaf nodes.

The proof is quite simple – we match the root to an arbitrary child, remove the edge, and recurse on the remaining rooted trees. Each remaining tree in which the root is a non-leaf in the original tree will contain more than one vertex, and so the induction hypothesis applies.

I'll let you come up with the details.


Sequential History in Herlihy and Wing's Linearizability paper

I've come to the conclusion that the constraint "each response is followed by a matching invocation" should omit the word "matching", and the paper should be read as if it weren't there. My evidence for this is that related literature and conference proceedings seem to omit it, either literally or effectively.

For example, the proceedings Principles of Distributed Systems: 14th International Conference (Google Books) includes a summary of a sequential history and linearizability and omits the second constraint completely:

  History $H$ is called Sequential if the first event of $H$ is an invocation, and each invocation, except possibly the last, is immediately followed by a matching response.

Another conference proceedings that I found, Networked Systems: Second International Conference (Google Books) includes the second constraint without the word "matching":

  A history is sequential if its first event is an invocation, and then (1) each invocation event, except possibly the last, is immediately followed by the matching response event, and (2) each response event, except possibly the last, is immediately followed by an invocation event.


The trick is to realize that if a graph has a clique of size $k$, the inverse graph has an independent set of size $k$. A clique of size $k$ means that $k$ nodes all have edges in between them. In the inverse graph these $k$ nodes are not (directly) connected and can be used to create an independent set of size $k$

Hence, the polynomial time algorithm you are looking for is merely the one that inverts the graph.

You will find a youtube explanation here.

I suspect that if you try to draw some very simple graphs with cliques and the inverses of said graphs you will realize why this is true.

As for (2), you need to show that an algorithm to the independent set problem can be used to solve the clique problem. Furthermore you need to show that using the solution to the independent set problem can be used to find the solution to the clique problem in polynomial time. This proves the following:

You can now reduce the clique problem to independent set. As all problems in NP can be reduced to the clique problem (the definition of clique being in NPC) all problems in NP can be reduced to independent set too and so it is in NPC. And since you reduced clique to independent set in polynomial time it cannot be harder than the clique problem either.

So (2) is equivalent to the following: If you were given a polynomial time algorithm for the independent set problem, how would you use it to find out whether a graph had a clique of size $k$?


Monotone property of heuristic in $A^*$ algorithm

When is a node visited twice?
Consider the following graph, where the heuristic satisfies the condition to always underestimate the length, but is not monotonic because $h(b) > d(b,c) + h(c)$.

When we visit $a$, we add $b$ and $c$ to the priority queue with priorities
$$p(b) = d(a,b)+h(b) = 1+8 = 9$$
$$p(c) = d(a,c)+h(c) = 3+1 = 4$$
Obviously, $c$ is visited first despite the shortest path to $c$ is actually via $b$. Later, when we visit $b$, $c$ is visited again from $b$ and has it's total weigth updated to $2$.
Strategy to find the shortest path without visiting a node twice.
If $a\rightarrow b\rightarrow c$ is shorter than $a\rightarrow c$, we want to visit $b$ first, so we reach $c$ from $b$ before reaching it from $a$. If we can ensure this, we don't even need to visit it from $a$ later on, because $a\rightarrow b\rightarrow c$ is shorter anyway.
This boils down to:
If
$$d(a,b)+d(b,c) < d(a,c)$$
is true, we must visit $b$ first.
We can add $h(c)$ on both sides without changing anything.
$$d(a,b)+d(b,c)+h(c) < d(a,c)+h(c)$$
If the monotonic constraint is fulfilled, we can replace $d(b,c)+h(c)$ by $h(b)$, since it's less or equal. The equation
$$d(a,b)+h(b) < d(a,c)+h(c)$$
is still true. This also happens to be the test the $A*$ algorithm uses do decide whether or not it will visit $b$ before $c$. If it is true, it visits $b$ first. This is exacly what we wanted to achive.


Is WPA2 with pre-shared key an example of a zero-knowledge proof?

In authentication you often come accross zero-knowledge password proof (ZKPP). EAP itself is a rather generic framework and it might involve revealing the identity of the client for instance to transfer it to the next layer of authentication such as RADIUS.

PACE (BSI TR-03110) is one example of ZKPP protocols used for authentication. EAP-SPEKE is another.

The security of the key relies on the use of only parts of the key in the exchange between the client and the server. The client offers a nonce encrypted with the key to the server. Therefore a rogue server receives a encrypted nonce and holds its plaintext version. This is not zero-knowledge, since in a finite time a rogue server might accumulate enough information to break the AES-128 encryption.

Hence EAP-PSK may not be considered an example of zero-knowledge password proof, though other proposed authentication schemes based on EAP such as EAP-SPEKE have this property.

To illustrate the problematic part of the EAP-PSK protocol consider the message flow as presented in RFC 4764.

  The first message is sent by the server to the peer to:

  *  Send a 16-byte random challenge (RAND_S).  RAND_S was called RA
     in Section 3.2

  *  State its identity (ID_S).  ID_S was denoted by A in
     Section 3.2.

  o  The second message is sent by the peer to the server to:

  *  Send another 16-byte random challenge (RAND_P).  RAND_P was
     called RB in Section 3.2

  *  State its identity (ID_P).  ID_P was denoted by B in
     Section 3.2.

  *  Authenticate to the server by proving that it is able to
     compute a particular MAC (MAC_P), which is a function of the
     two challenges and AK:
     MAC_P = CMAC-AES-128(AK, ID_P||ID_S||RAND_S||RAND_P)

  o  The third message is sent by the server to the peer to:

  *  Authenticate to the peer by proving that it is able to compute
     another MAC (MAC_S), which is a function of the peer's
     challenge and AK:
     MAC_S = CMAC-AES-128(AK, ID_S||RAND_P)

Here AK is a part of the secret key that is used at this stage and may be revealed to the rogue server that is able to decrypt AES-128.


Polynomial size Boolean circuit for counting number of bits

You can write a straight-line program (an equivalent way to define a circuit) that computes the Boolean variables $z_{i,j}=[x_1+y_1+\cdots+x_i+y_i \equiv j \pmod{3}]$ (where $i=1,\ldots,n$ and $j=0,1,2$) as follows:

$z_{1,0} = \lnot x_1 \land \lnot y_1$.
$z_{1,1} = (x_1 \land \lnot y_1) \lor (\lnot x_1 \land y_1)$.
$z_{1,2} = x_1 \land y_1$.
$z_{i+1,j} = (z_{i,j} \land \lnot x_{i+1} \land  \lnot y_{i+1}) \lor (z_{i,j-1} \land ((x_{i+1} \land \lnot y_{i+1}) \lor (\lnot x_{i+1} \land y_{i+1})) \lor (z_{i,j-2} \land x_{i+1} \land y_{i+1})$

The output of the circuit is $o = \lnot z_{n,n \bmod 3}$.

The circuit has size $O(n)$.


What you want is called indirection. Instead of physically moving the rows/columns, you move their names.

Let's say I call row 1 r[0], and row 3 r[2], in a matrix A, which has size n  by n. Initially, the rows are exactly as I call them, so we initialize r[i] = i for all i < n.

Now I want to swap the third (r[2]) and the fifth row (r[4]). I could move the elements in matrix A, but this would require n swaps. Instead, I can just swap r[2] and r[4]! This is just swapping one integer.

The tradeoff is that now we must read matrix A as A[r[i]][c[j]] (where c is the equivalent of r, but for columns) instead of A[i][j]. This is a bit slower.


Is there a name for this graph search strategy?

I don't think it has any standard name, but you might arguably call it a depth-first search with one level of lookahead.


Understanding the definition of reduction

The definition you're quoting is very abstract, but the concepts you're trying to understand are pretty intuitive. A problem $A$ is NP-hard if you can solve any problem in NP using it. This means that any $B \in NP$ can be reduced to $A$, i.e. there is some polytime function $f$ such that $x \in B$ iff $f(x) \in A$; so you can test whether $x \in B$ by computing $f(x)$ and test whether the latter is in $A$.

A problem is NP-complete if it is both in NP-hard and in NP. This means that it is hardest among problems in NP. A problem can be NP-hard without being in NP, for example the halting problem.

You're mentioning sets of problems as belonging to NP, but that's a typing error: members of NP are problems, in the guise of subsets of the set of natural numbers (or of the set of finite binary strings, which is the same). The subset specifies the set of inputs for which the problem has the answer YES.


Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$?

You calculated “Big-Theta for n = power of two - 1”. That’s not a useful thing. Try calculating T(n) for n = (4^k - 1) / 3 and be surprised. (Write n down in binary first). Or n = 3 * (8^k - 1) / 7 where T(n) ≈ n^(2/3).
You found the values for a good case and for a bad case. You’ll have to prove they are lower and upper bound.