on p4-5 of your 2nd ref by Faro and Lecroq they write:

  Online string matching algorithms (hereafter simply string matching algorithms)
  can be divided into three classes: algorithms which solve the problem by making
  use only of comparisons between characters, algorithms which make use of deterministic
  automata and algorihtms which simulate nondeterministic automata using
  bit-parallelism.

however, while sounding general, these statements seem to be wrt "within the realm of string matching algorithms". in other words there is massive use/ research of bit parallelism of NFAs for string matching algorithms in particular, but have not seen much bit parallelism ideas applied to arbitrary NFAs, even though it is clearly applicable. here are two refs turned up that do consider bitwise operations on a more general/ arbitrary case (apparently the focus of your question). in the 2nd case, "vector algorithms" are capable of/ nearly the same as "bit parallelism".

Implementing WS1S via Finite Automata / Glenn, Gasarch, sec 4, "internal representation of Automata"

  we do this with elementary bitwise operations

Fast Implementations of Automata
Computations / Bergeron, Hamel sec 2.2 "solving more complex automata"

  In this section, we establish a sufficient condition for the existence of a vector
  algorithm for an automaton.


Algorithm for guessing a word in a dictionary with weighted operators

A good heuristic: greedy choice

Here is a greedy algorithm.  It might not be optimal, but I suspect will yield a solution that is good enough.  It is basically an instantiation of your thought, but taking into account a bit of information theory.  The idea will be to greedily choose which operator to query at each iteration; to tell which operator is best, we'll simulate all possibilities for the choice of operator and see which gives us the best gain.

Basically, we're building a decision tree on the fly, via greedy choice at each step.

Keep a set $T$ of all possibilities for the unknown word.  (Initially this is $S$, but you'll narrow down the possibilities as you go.)  In each iteration:

For each possible operator $f$ you could possibly try, compute the "information gain" of using that operator,
$$I(f) = H(X) - H(X | f(X)),$$
where $X$ is a random variable that is uniformly distributed on the current set $T$.  This tells you the expected number of bits of reduction of the entropy -- roughly speaking, the reduction in uncertainty about the word.
For each possible operator $f$, compute the cost of that operator, $\text{cost}(f)$.  Also compute the gain-per-unit-cost, $I(f)/\text{cost}(f)$.
Pick the operator $f$ with the largest value of $I(f)/\text{cost}(f)$, and query that operator.  Use the response to reduce the set of possible words, i.e., remove from $T$ each word that is inconsistent with the response you got.

Repeat until you are left with only one possibility.

Notice that there are only $26+50=76$ different possible operators, so it is easy to enumerate over them all in each iteration.  This algorithm will be pretty fast.

Information gain

How do you compute the information gain of an operator $f$?  Well, you know the set $T$.  Also, given any word $w \in T$, you can compute the result $f(w)$ of applying $f$ to word $w$.

It's easy to compute the entropy $H(X)$: that is just $\lg |T|$.  The entropy of a uniform distribution on some set is the base-2 logarithm of the size of that set.

To compute $H(X|f(X))$, we partition $T$ into subsets $T_1,T_2,\dots,T_k$ according to what the operator returns (all word that return the same value in response to this operator are grouped into the same subset).  Now $H(X|f(X)=y)$ is just $\lg |T_i|$, where $T_i$ is the subset corresponding to words that yield response $y$.  The conditional entropy $H(X|f(X))$ is the average of $H(X|f(X)=y)$ over all possible values of $y$, weighted by the probability of getting $y$.  Thus,

$$H(X|f(X)) = \sum_i {|T_i| \over |T|} \cdot \lg |T_i|.$$

It follows that

$$I(f) = \lg |T| - \sum_i {|T_i| \over |T|} \cdot \lg |T_i|.$$

Optimal sequence

The algorithm above doesn't guarantee to output the optimal solution.  What if we want the optimal sequence of queries?  Well, basically this corresponds to building a decision tree, where each node of the tree applies one operator and then branches upon the result.

We can evaluate the "cost" of a decision tree according to the expected cost spent by the decision tree to narrow down the word to a single possibility, with the expectation taken over the random choice of the unknown word.  Given a decision tree, it is easy to compute its expected cost.  For each of the 100 words, you can simulate what path it will take through the decision tree and the total cost before it hits a leaf; averaging those 100 costs yields the expected cost.

You could now enumerate over all decision trees, and take the one whose expected cost is minimal.  Of course, this will be highly inefficient, as there are exponentially many trees, but it does find the optimal solution.

It should be possible to make this more efficient using branch-and-bound.  Explore the space of decision trees, by building them up in a top-down fashion (from the root downwards).  At any point, you have a partial decision tree (the top of some decision tree, with bottom parts yet to be filled in).

You can get an upper bound for the cost of the best way to complete a partial decision tree to a full decision tree, by applying the greedy heuristic above to complete it to a tree and seeing what the result costs.

Also, you can get a lower bound as follows.  Suppose we have any set $U$ of words.  Find the letterx such that the number $b$ of different possible results of getOccurrences(x) [taken over all words of $U$] is as large as possible.  Then the cost of any decision tree for $U$ will necessarily be at least $\lceil \log_b U \rceil$.  For each bottom node in a partial decision tree, find the set $U$ of words that reach that node, compute a lower bound on the cost of the best decision tree to put as a subtree of that node, and average these up over all the bottom nodes of the partial decision tree (together with the cost of reaching that node).

Now use these lower and upper bounds to prune your exploration, following standard branch-and-bound techniques: if the lower bound for a partial decision tree is at least as large as the expected cost of the best complete decision tree seen so far, then you can prune that partial decision tree (there is no need to explore any of the candidate ways to complete it to a complete decision tree).

Whether this algorithm will be efficient enough to use, I don't know.  You could implement it and give it a try.


Merge sort worst case running time for lexicographical sorting?

The recurrence formula is incorrect.

Lets say you have $t$ strings, so the running time of merge isn't $O(t^2)$ but $O(t\cdot n)$.

Change variables: the input size is $m=n^2$, and the recurrence formula should be

$$T(m)=2 T\left( m/2 \right) + O(m) $$

So you get $T(m)=O(m\log(m))$ and therefore $T(n^2)=O(n^2\log(n))$.


It's a fairly reliable rule of thumb that Turing-completeness depends on the ability to construct answers or intermediate values of unrestricted "size" and the ability to loop or recurse an unrestricted number of times. If you have those two things, you probably have Turing-completeness. (More specifically, if you can construct Peano arithmetic, then you certainly have Turing-completeness!)

Let's assume for the moment that you've already stripped arithmetic. We'll also assume that you don't have any non-logical features like atom_chars, assert, and so on, which enable general shenanigans.

If you stripped out function symbols, you can't construct answers or intermediates of unrestricted size; you can only use atoms which appear in the program and the query. As a result, the set of all possible solutions to any query is finite, so taking the least fixed point of the program/query will always terminate. Datalog (a relational database query language based on Prolog) works on this principle.

Similarly, if you restricted Prolog to primitive recursion only (that includes no recursion as a degenerate case), then the amount of recursion that you can do is bounded by the size of the query, so all computation terminates. So you need general recursion for Turing-completeness.

And, of course, if you have general recursion, you can cut a whole bunch of features and retain Turing-completeness, including general unification (construction and top-level pattern matching is sufficient), negation, and the cut.


Can adjacency lists be used in directed graphs?

Your graph is actually undirected. The notation is a list of edges in the graph. Since edges are undirected, each edge is a set of two vertices. Your lists contains three edges, since a triangle has three edges. It actually contains all possible edges involving the vertices $a,b,c$.

A directed graph is one in which edges consist of two ordered vertices. The edge points from the first vertex to the second. You can represent such a graph using a list of pairs.

Adjacency lists are a different data structure, which is described in the Wikipedia page you link to, so I skip its description here. It can be used for both undirected and directed graphs, in the natural way.


Find all nodes on simple paths between two nodes in cyclic directed graph

This problem is NP-hard. It is actually NP-Hard to prove if a vertex $w$ lays on a simple path from $u$ to $v$. Here is a prove of hardness through a reduction from the two disjoint paths problem.

Given a directed graph $G = (V, E)$ and two pairs of vertices $(s_1, t_1)$ and $(s_2, t_2)$, we build the new graph $G'$ by adding a new vertex $w$ to $G$ and add an edge from $t_1$ to $w$ and an edge from $w$ to $s_2$. The new graph admits an $s_1, t_2$ simple path passing through $w$ if and only if the original graph admits two disjoint paths one from $s_1$ to $t_1$ and the other from $s_2$ to $t_2$. Try to prove this claim as an exercise!


Early termination of A* with weak heuristic if solution is known

In order to prove that the solution is optimal, with a consistent heuristic A* needs to expand all states with f < f* (the perfect solution cost) and it also may expand some states with f = f* so it seems hard that knowing an upper bound on the number of expansions can help to reduce the number of node expansions without modifying the heuristic.

A potential way of helping A* in this context may be that of heuristic selection. That is, in cases where more than one heuristic is available, meta-reason about what subset of heuristics should be used [1,2].

In this scenario it could be possible to use the sub-optimal path to select which ones to use (e.g., it may be worth it to compute more expensive heuristics because they have greater chances of pruning the node). However, this is an open problem and I'm not aware of any work on that direction.

[1] David Tolpin, Tal Beja, Solomon Eyal Shimony, Ariel Felner, Erez Karpas:
Toward Rational Deployment of Multiple Heuristics in A. IJCAI 2013: 674-680

[2] Levi H. S. Lelis, Santiago Franco, Marvin Abisrror, Mike Barley, Sandra Zilles, Robert C. Holte:
Heuristic Subset Selection in Classical Planning. IJCAI 2016: 3185-3191


Why does Dijkstra's algorithm not account for updating node distances after expanding a node?

Since Dijkstra's algorithm always expands the shortest path first, the first time we reach a node will be along the shortest path to that node. That is the key insight that allows the algorithm to be efficient compared to a breadth-first-search.

There is no way to construct a graph where no costs are negative and there exists a path from a to b shorter than the one Dijkstra's algorithm finds.


Are all context-sensitive languages decidable?

First, all context-sensitive languages are decidable, since they can be accepted by a LBA (as you said), and a Turing machine is more powerful than a LBA.

However, you were asking about something else. Can there be LBA that cycles? The answer is yes. You gave an example. However, you can modify every LBA $M$ to a Turing machine $M'$ that accepts the same language but never cycles. To see this, observe, that you can simulate $M$ on $M'$ and keep track of all configurations the LBA has attained so far. If there is one configuration that shows up twice, you detected a cycle. In this case you stop rejecting. The important thing here is that the LBA uses on linear space, and hence the number of its configurations is bounded.


How to use PHOG and LPQ features for Emotion Recognition?

To train your SVM inevitably you need some baseline, which can be accquired from FERA 2011 contest. The whole procedure using this data is described in Emotion Recognition Using PHOG and LPQ features by Abhinav Dhall, Akshay Asthana, Roland Goecke and Tom Gedeon. After reading that there is a follow up FERA 2015.


Why does merging two sorted arrays take 2N - 1 comparisons?

The question asks to show the lower bound on the number of comparisons in merging two sorted arrays of length $N$. Therefore, you need to argue that no matter what comparison-based algorithm you use, it has to make $2N-1$ comparisons, otherwise it would make an error on some input, i.e., it's a worst-case analysis. An algorithm that you come up with might as well do fewer comparisons on some inputs, you just need to show it can't make fewer comparisons on all inputs.

Since we are counting comparisons, I assume we are in a so-called comparison model. Assume your arrays are $A_1 < A_2 < \ldots < A_N$ and $B_1 <  B_2 < \ldots < B_N$. Usually proofs in this model are information-theoretic. Imagine your algorithm as a comparison tree, where each node queries $A_i < B_j$ for some indices $i, j \in [N]$. Then each leaf has to correspond to a correct interleaving of the two arrays $A$ and $B$. How many interleavings are possible? Well you need to choose positions for elements of $A$ and fill in the rest with elements of $B$ (elements of $A$ and $B$ have to appear in order, so there is only one way of doing so). This leads to $2N \choose N$ possible interleavings - these should all appear as leaves in your comparison tree. If a tree has $K$ leaves it has depth at least $\log_2 K$ (since it's binary). Unfortunately, using Stirling's approximation it leads to a lower bound of $2N - \frac{1}{2} \log N - 1$, which does not match the upper bound of $2N-1$. This is surprising, because for sorting, the information-theoretic bound is optimal in the comparison model.

Knuth describes an adversarial argument (which he in turn attributes to Graham and Karp) in The Art of Computer Programming, Volume 3. It goes like this. Consider answering a query $A_i < B_j$ as "YES" when $i < j$ and "NO" as $i \ge j$. Then the algorithm will terminate at a leaf
$$ B_1 < A_1 < B_2 < A_2 < \cdots < B_N < A_N.$$
Moreover, the algorithm has to make all $2N-1$ comparisons $B_1$ vs $A_1$, $A_1$ vs $B_2$, $B_2$ vs $A_2$, and so on. Why? Suppose it doesn't perform all these comparisons. For instance it does not compare $A_1$ with $B_2$, then the following order is also consistent with our responses:
$$ B_1 < B_2 < A_1 < A_2 < B_3 < \cdots < B_N < A_N.$$


Since $n>0$, $\dfrac 3n >0$. Hence $\dfrac{1}{2}-\dfrac{3}{n} \leq  c_2$ is implied by $\dfrac 12\le c_2$.

That is, your (2) is not correct while everything else is fine.

Just in case you cannot see why your (2) is wrong, please take a look at the following deduction.
$$ \dfrac{1}{2}-\dfrac{3}{n} \leq  c_2\\
\dfrac{1}{2}-c_2\le\dfrac{3}{n} \\
\dfrac{1/2-c_2}{3} \leq  \dfrac 1n\\
\dfrac 1n\ge\dfrac{1/2-c_2}{3} $$
Compare the last inequality with your (2).


All these languages are regular. This comes from the fact $w$ could simply be a single letter, and thus the languages admit the following regular expressions (assuming here $\Sigma=\{a,b\}$, but this would work for any finite alphabet):

$$L_1=a(a+b)^+a+b(a+b)^+b$$
$$L_2=a(a+b)^+a(a+b)^++b(a+b)^+b(a+b)^+$$
$$L_2=(a+b)^+a(a+b)^+a+(a+b)^+b(a+b)^+b$$

A more detailed explanation:

In the definition we had: $w\in\{a,b\}^+$.

This mean that $w$ could be a single letter, $a$, or $b$, and thus we can attribute the rest of the word to $x$ (or $y$).

For example, if:
$$u=abbababa\in L_1$$, because it can be decomposed as $w=a, x=bbabab$ and $$u=wxw^R$$. Similarly, each word which starts and ends with a $a$ is in $L_1$ (pick $w=a$), and each word that starts and ends with a $b$ is also in $L_1$ (pick $w=b$). This is why $$L_1=\{axa|x\in\{a,b\}^+\}\cup\{bxb|x\in\{a,b\}^+\}$$, and thus regular. Same tricks apply to the other languages and all three are indeed regular (by the regex I gave).


ip/tcp packet decoding without wireshark

My guess is that what you are seeing is a Level 2 Ethernet frame and therefore the preamble is missing. Also the Ethernet checksum seems to be missing. In this case everything seems to line up (the packet type inside the Ethernet frame, the IPv4 version, the IPv4 packet length, the packet type, i.e. TCP, inside the IP packet,  ...). Then you'd read your packet as in the picture.

The TCP payload is

474554202f20485454502f312e300d0a
557365722d4167656e743a2057676574
2f312e31312e340d0a4163636570743a
202a2f2a0d0a486f73743a207777772e
696574662e6f72670d0a436f6e6e6563
74696f6e3a204b6565702d416c697665
0d0a0d0a

and decodes to:

GET / HTTP/1.0
User-Agent: Wget/1.11.4
Accept: */*
Host: www.ietf.org
Connection: Keep-Alive

which is coherent with the fact that the destination port is 80.


Don't worry – everybody gets confused by the direction of reductions. Even people who've been working in algorithms and complexity for decades occasionally have a, "Wait, were we supposed to be reducing $A$ to $B$ or $B$ to $A$?" moment.

Reducing $A$ to $B$ produces a statement of the form "If I could solve $B$, then I'd also know how to solve $A$". "Solve" in this sense could mean "compute using any Turing machine", or "compute in polynomial time" or whatever other notion of solution your context requires.

This may seem counterintuitive, since "$A$ reduces to $B$" implies that solving $B$ is at least as hard as solving $A$, so you haven't reduced the difficulty. However, you can think of it as reducing the number of problems you need to solve. Imagine that, at the start of the day, your goals were to find an algorithm for $A$ and an algorithm for $B$. Well, now that you've found a reduction from $A$ to $B$, you've reduced your goals to just finding an algorithm for $B$.


You can distinguish between the following types of data (source, see Level of measurement for something similar):

Nominal: You can't calculate with them. They only support checks for identity, e.g. names.
Ordinal: You can order them, but not compare the distance. Examples are grades or sizes for cloths.
Interval scaled: Additionally to identity checks and ordering it supports addition. Examples are temperature in °C / °F
Ratio scaled: They support multiplication in addition to the ones before. Examples are mass and length.

For neural networks, ratio scaled feature make most sense. You can sometimes change your view on things to get it, but most of the time you cannot simply transform an ordinal scaled feature to be ratio scaled.

Two tricks for your example come to my mind:

1-hot encoding: Instead of using one number for the country (e.g. 1 for Australia, 2 for Austria, 3 for France, 4 for Germany, ...) you should use a 1-hot encoding (e.g. one bit per country, the bit is only set if it is this country). I am pretty sure this will work much better, although your feature vector will get much bigger. (Attention: Depending on how much data you have, you might suffer from overfitting. You could also partition your dataset according to this feature. So, for example, you might have a lot of data for the US, for France and Germany. But you only have a little data for african countries. Then you could simply have one bit for each of US, France, Germany and complete Africa)
Latitude / Longitude: Instead of using the citys directly, you can use the citys coordinate. This makes your feature even more meaningful and you have two floats for it which are ratio scaled.

You might also think about transforming the country to something more meaningful for your problem (e.g. membership in an organization like OECD).

You could also combine different classifiers. So you could use the "bad scaled features" for a decision tree and feed the result into a NN.


How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?

This is a classical result of Winograd: On multiplication of 2x2 matrices.

Strassen showed that the exponent of matrix multiplication is the same as the exponent of the tensor rank of matrix multiplication tensors: the algebraic complexity of $n\times n$ matrix multiplication is $O(n^\alpha)$ iff the tensor rank of $\langle n,n,n \rangle$ (the matrix multiplication tensor corresponding to the multiplication of two $n\times n$ matrices) is $O(n^\alpha)$. Strassen's algorithm uses the easy direction to deduce an $O(n^{\log_27})$ from the upper bound $R(\langle 2,2,2 \rangle) \leq 7$.

Winograd's result implies that $R(\langle 2,2,2 \rangle)=7$. Landsberg showed that the border rank of $\langle 2,2,2 \rangle$ is also 7, and Bläser et al. recently extended that to support rank and border support rank. Border rank and support rank are weaker (=smaller) notions of rank that have been used (in the case of border rank) or proposed (in the case of support rank) in the fast matrix multiplication algorithms.


Normalization in IBM hexadecimal floating point

I'm going to start with this famous quote from James Wilkinson's 1970 Turing Award Lecture, Some Comments from a Numerical Analyst.

  In the early days of the computer revolution computer designers and
  numerical analysts worked closely together and indeed were often the
  same people. Now there is a regrettable tendency for numerical
  analysts to opt out of any responsibility for the design of the
  arithmetic facilities and a failure to influence the more basic
  features of software. It is often said that the use of computers for
  scientific work represents a small part of the market and numerical
  analysts have resigned themselves to accepting facilities "designed"
  for other purposes and making the best of them. I am not convinced
  that this in inevitable, and if there were sufficient unity in
  expressing their demands there is no reason why they could not be met.
  After all, one of the main virtues of an electronic computer from the
  point of view of the numerical analyst is its ability to "do
  arithmetic fast." Need the arithmetic be so bad!

In 1970, Fortran had only been cross-platform for four years. A lot of numerical analysis was being done on IBM hardware, and System/360 in particular, but every CPU vendor had its own floating point format, and most of them (as Wilkinson indicated) were not designed by those who demanded high-quality floating point arithmetic.

Today, the industry has standardised on IEEE-754. It's imperfect, because everything is, but it's reliable and can be relied upon.

Wikipedia's definition of "normalised number" (or "normalized number"; I'm going to type it as my dialect spells it) is the current modern definition. It's the one you learned in high school when discussing scientific notation. It's the one used by IEEE-754. It's the one that's in all the modern textbooks.

But it's not the only normal form for floating point that has existed, and I think that's the source of the confusion here.

Interestingly, it's not the only normal form in use today! There is at least one place in modern programming where a different normal form is still in use, because it pre-dates IEEE-754.

The C standard library has a function to extract the parts of a floating-point number's normal form, called frexp. But the normal form that it uses is that the mantissa is in the range $\left[ 0.5, 1 \right)$, not the modern $\left[ 1, 2 \right)$. This is a notorious "gotcha" for numeric analysts working in C or C++ today.


Finding preferences for G-S algorithm (Algorithm Design Chapter 1 exercise 7)

Your algorithm is clean and correct.
Here is an easy proof.
Let $\text{junction}(x,y)$ stand for the junction between input $x$ and output wire $y$. Let $\text{stream}(x,y)$ stand for the stream from input wire $x$ to output wire $y$, which must be switched at $\text{junction}(x,y)$.
The book has proved the Gale-Shapley algorithm must produce a stable and perfect matching. As an application, your algorithm must produce a stable and perfect matching between the input wires and output wires.
Suppose, for the sake of contradiction, an execution of your algorithm produces a matching $M$ that includes $\text{stream}(i,o)$ and $\text{stream}(i',o')$ that meet at some junction $J$. Since $\text{stream}(i,o)$ passes $J$, $J$ is either on the same input wire or the same output wire as $\text{stream}(i,o)$. Similarly, $J$ is either on the same input wire or the same output wire as $\text{stream}(i',o')$. Since input wires are disjoint to each other, $J$ cannot be on $i$ and $i'$ both. Similar, $J$ cannot be on $o$ and $o'$ both. So, $J$ must be either $\text{junction}(i,o')$ or $\text{junction}(i',o).$

Suppose $J$ is $\text{junction}(i,o')$.

Since $\text{stream}(i,o)$ passes $J$, $J$ is upstream to $\text{junction}(i,o)$ on input wire $i$, i.e, $i$ prefers $o'$ to $o$.
Since $\text{stream}(i',o')$ passes $J$, $J$ is downstream to $\text{junction}(i',o')$ on output wire $o'$, i.e, $o'$ prefers $i$ to $i'$.

So $(i, o')$ is an instability with respect to $M$.

Otherwise, $J$ must be $\text{junction}(i',o)$. Symmetrically, we will get that $(i', o)$ is an instability with respect to $M$.

However, $M$ is a stable matching. We have arrived at a contradiction. $\quad\checkmark$


Can a CFG end have a non-terminal symbol in the middle of it?

Both of those are valid context-free grammars. (For the same language.) The requirement for a context-free grammar is just that the left side of the production must have exactly one non-terminal, which both of them satisfy. (Usually, to make this more clear, we'd have a convention like non-terminals are uppercase and variables are lower-case, and we'd specify the start symbol. But it looks clear that you have $A$ and $C'$ as nonterminals and the rest terminals, with $A$ being the start symbol.)


This is just a single-level cache, then? That means just two possibilities when accessing: a hit or a miss, with hit rate + miss rate = 100%. It follows that the average is simply the time spent with hits and the time spent with misses, which comes out to:

hit rate * hit time + miss rate * miss time


Common idea in Karatsuba, Gauss and Strassen multiplication

A partial answer to your question is the group-theoretic approach first developed by Cohn and Umans and further developed by Cohn, Kleinberg, Szegedy and Umans. It can "sort of" capture Strassen and Coppersmith-Winograd for matrix multiplication.


Minimum number of states in dfa accepting binary number with decimal equivalent divisible by $n$

Case 1: $n$ is a power of 2

If you wanted to check whether a decimal number is divisible by some power of 10,  you can just look at the number of trailing zeros. For example, all numbers that are divisible by $100 = 10^2$ end with 2 zeros (this is of course including numbers ending with more than 2 zeros). The same idea can be applied here for binary numbers and powers of 2. Specifically to check for multiples of $n = 2^m$, you can simply check if the string ends in $m$ zeros. For example, if $n = 16 = 2^4$, all multiples of $n$ will end in 0000 (4 zeros). Thus we can create the following DFA for $n = 16$:

This construction can be extended to all multiples of 2, where you have $m+1$ states to ensure that your input ends in at least $m$ zeros (reading a 0 takes you one state forward, reading a 1 takes you back to the start). As suggested in the comments on your question, you can show that you can't do any better than this using a Myhill–Nerode argument.

Case 2: $n$ is odd

The general idea here is that when a number is divided by $n$, the possible remainders are $0, 1, \ldots, n-2$ or $n-1$. We can give our DFA one state for each of these possible remainders so as we process a string, we're keeping track of the remainder of what we've read so far and transitioning to the appropriate remainder based on what character we read. Then, we accept if we finish in the remainder 0 state.

Design DFA accepting binary strings divisible by a number 'n' walks through a detailed method for constructing such a DFA, and you can find out more about this by searching for "DFA based division". This gives a total of $n$ states, which is optimal by Myhill-Nerode because these remainders are exactly the equivalence classes given by the relation $\equiv_L$ for the language $L = \{\text{binary strings divisible by }n\}$.

Case 3: $n$ is even (and not a power of 2)

The technique in case 2 also works here but it isn't optimal. Every $n$ in this case can be expressed as $2^km$ where $m$ is odd (this is the division procedure described in your question). Thus, to check whether a binary string is divisible by $n$, we check whether it is divisible by both $2^k$ and $m$.

We know that it takes $k$ states to check divisibility by $2^k$ (case 1) and $m+1$ states to check divisibility by $m$ (case 2). We can take a DFA for divisibility by $m$, unmark the accepting state and make it the start state for a DFA for divisibility by $2^k$, giving our final DFA $k+m$ states.

As an example, here's the DFA for $n = 6$:

The top three states ensure that the number is a multiple of 3, and the final accept state ensures that it is a multiple of 2.


What is google docs solution to handling multiple users editing and reading at the same time?

Note: there is no way to know how Google does it. All we can do is speculate based on whatever information is publicly available. If you want to know, you have to ask them, not us.

Google Docs' collaborative features are reportedly an offshoot of Google Wave. Google Wave, in turn, reportedly used Operational Transformation.

As a very high-level basic overview, the fundamental idea behind OT is that each collaborator has their own local copy of the document, and the editor infers an operational transformation based on the user's inputs. These transformations can be very simple (insert character x at position y) or more complex (perform an extract method refactoring of the second code block in method foo and name the resulting method bar).

These transformations are then broadcast to the other collaborators and applied to their respective copies.


You have your mapping the wrong way around. As it stands, it would be a reduction from a decidable problem to an undecidable problem. It's certainly possible (see below), but it doesn't tell us anything.

Recall that if $A \leq_{m} B$, then an algorithm solving $B$ (or deciding membership in this case) can be used to solve $A$ (decide membership in $A$). So the reduction you're looking at would tell us that any decider for $E_{LBA}$ could be used to decide $A_{LBA}$. We happen to also know that $E_{LBA}$ is undecidable, but this doesn't prevent there being some decider for $A_{LBA}$ that doesn't decide $E_{LBA}$.

In fact, the reduction that can't exist is $E_{LBA} \leq_{m} A_{LBA}$, as this would imply that we could decide $E_{LBA}$, which we know we can't.

For the second part, the proof (or rather, one of the possible proofs) that $E_{LBA}$ is undecidable is via constructing the mapping $A_{TM} \leq_{m} E_{LBA}$, so again a decider for $E_{LBA}$ would give us a decider for $A_{TM}$, but we already know that $A_{TM}$ is undecidable so $E_{LBA}$ must also be undecidable.

As to why the proof uses a language that involves Turing Machines to show something about linear bound automata, it's because it works.

A Reduction

As $A_{LBA}$ is decidable, we can take the input LBA $M$ and string $w$, and run the decider on $\langle M, w\rangle$. If it accepts, we map this to an LBA $M_{rej}$ that immediately rejects. If the decider rejects, we map it to an LBA $M_{acc}$ that immediately accepts. Thus $M_{acc}$ accepts all input and is not in $E_{LBA}$, and $M_{rej}$ rejects all input and is in $E_{LBA}$.

Note of course that this reduction is in a sense trivial, and the subset of $E_{LBA}$ it maps to is finite and therefore decidable (even regular!).

Another Perspective

Given two languages $A$ and $B$ such that $A \leq_{m} B$, there's two basic (useful) things we might be able to say:

If $B$ is decidable then $A$ is also decidable.
If $A$ is undecidable then $B$ is also undecidable.

In our case $A$ is decidable, and $B$ is undecidable, which matches neither of these possibilities, so the reduction $A_{LBA}\leq_{m}E_{LBA}$ doesn't tell us anything about the decidability of either.


If 3SAT reduces to its complement then PH=NP

Show that in that case $\text{NP=coNP}$ which means $\Sigma^p_1=\Pi_1^p$, so the hierarchy collapse to the first level.


Show $USELESS_{TM}=\{ M | M$ is a Turing machine with at least one useless state$\}$ is recursively enumerable?

The reason you are struggling to reduce USELESS to the Halting problem might be that it is not recursively enumerable after all. Since you already have a proof of undecidability, it is enough to see that USELESS is co-ce:

Given some TM M, we enumerate all its states as $s_1$ ... $s_n$. We can search through potential inputs $w_0,w_1,\ldots$ and mark each state that one of the computation visits. If we ever mark all states, we halt. This gives a procedure that recognizes exactly the complement of USELESS.


NFA: each block of five consecutive characters contains at least two 0's

Your DFA is already a NFA, so you're done.


Is there a crossover operator to cross sections of specific phenotype genes?

Let's say you have two parents. For the sake of clarity, let's say that the first five alleles can be either '*' or '-', and the second five either 'x' or 'o'. Our parents might then look like the following.

- - - - - | + + + + +

x x x x x | o o o o o

I'm interpreting the question to mean that you want an operator which only operates on whole phenotypes. As far as I can see, there's only one way to do that, which is to do one-point crossover with the crossover point fixed to the boundary between the two parts.

I question whether this is a good idea. It's a very weak search operator, and in order for it to work reasonably well, I would guess you'd need a very high mutation rate to provide some search power and some sort of elitist selection to keep the mutation from killing your good solutions.

Without more information about your problem, it's hard to say for sure what your needs really are. However, the standard way of handling multiple phenotypic variables is to encode them into a single chromosome, as you've done, but then treat them as one string free of semantics. You just do whatever crossover operator you'd normally do. Yes, that means that your crossover might take part of one property mixed with part of another, but that's what happens in biology as well. In my example, no matter where you put the crossover point, you still get valid offspring. You might do uniform crossover and get children like

- x x - x | o + + o +

x - - x - | + o o + o

but those are perfectly valid offspring. The result is that crossover can explore a much wider part of the search space.

I'm not aware of a reference off the top of my head that compares the two ideas. Probably someone in the early days of GAs has looked at this. But unless you need to cite an authoritative source to justify your decision, I'd say just implement whichever version seems like the right answer for your problem. Both are trivial to code.


Which algorithm can I use to allocate human resources?

Since Vince asked me to publish my solution, I decided to write this long post.
Please bear in mind that this code is really really basic and absolutely not optimized, written as fast as possible to perform some test.
Credits for Hungarian algorithm code must be done to vivet.

PURPOSE

I need to create shifts for M workers (variable number each week) on N slots (usually 50 each week, but sometimes some slot could be unavailable).
Each worker can suggest slots he wants to take and others he can't absolutely take and, if possible, these requests should be taken in account.

GENERAL IDEA

Given that creating costs matrix for Hungarian solver can be a pain, I decided (just a quick solution) I can create text files for each worker to report his request and one file for unavailable slots.
All these files must be in the same folder.

FILES STRUCTURE

A single text file must have as many rows as daily slots (usually 10) and as many columns as working days (usually 5).
Each cell must contain a preconfigured char:

O means worker really needs that slot assigned
o means worker would like to have the slot assigned
- means no preference on that slot (it's the default naturally)
x means worker would like not to have the slot assigned
X means worker can't work on that particular slot

A sample could be

X x - - O
X x - - O
- - - - O
- - - - -
- - - - -
- - - o -
- - - o -
- - - - -
- - - - -
x x x x x

Unavailable slots file must have a well defined name (always the same) and its content will have the same structure of workers files. Naturally each cell having a value different than - means that slot is not available to workers.

CODE

Source code can be found here.
Unfortunately .NET Fiddle uses framework 4.5, so program can't be compiled and run online due to the fact I use a newer framework (4.7.1).
Also consider my real code is organized into several files!

It works and it's fast, so I'm completely satisfied with this part.

A STEP FURTHER

First problem solved, pretty good. But now I have to face the next one: I have several locations to assign workers shifts to and these locations share the same working hours.
A first attempt was to raise the number of columns on each file: cols 1-10 are for the 1st venue, cols 11-20 for the 2nd and so on.
Code works without any change and Hungarian algorithm processes data in a while, good; but, as expected, I end having overlapping shifts for the same workers on multiple venues (it's random, but always happens).
I could solve this problem by computing 1st venue, then changing each worker requests denying slots already given in the 1st venue before computing the 2nd one; not exactly the best way I'm sure, just an idea I had, and I'm not sure I can always find a solution.

OTHER OPTIMIZATIONS

I could also think about adding other rules (e.g. if possible worker should have max 2 ranges in a day (avoiding for example solutions having slots 0, 2, 4, 6 and 8 and preferring slots 0-2, 6-8 instead) and limits, but this goes too far from the starting question, so it will be something I'm asking in future and I'm quite sure it could need some more complex algorithm or libraries (e.g. ORTools by Google) I'm searching/studying.


Let us consider the recurrence
$$
T(n) =
\begin{cases}
1 & \text{if } n = 1, \\
T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n & \text{if } n \geq 2.
\end{cases}
$$
Using OEIS (A033156), we find that the exact solution to this recurrence is
$$
T(n) = n(\lfloor \log_2 n \rfloor + 3) - 2^{\lfloor \log_2 n \rfloor + 1}.
$$
Curiously, OEIS presents a different recurrence relation with the same solution:
$$
T(n) =
\begin{cases}
1 & \text{if } n = 1, \\
T(n-1) + \lfloor T(n-1)/(n-1) \rfloor + 2 & \text{if } n \geq 2.
\end{cases}
$$
The OEIS entry contains references to articles analyzing the recurrence in the context of divide-and-conquer, which you might find helpful if you want to analyze similar such recurrences.


How does the kleene star and union work in a context free grammar?

This is how you can implement star and union operations over context-free languages given their grammars.

Given a grammar $G$ for the language $L$, we can take a new non-terminal symbol $T$ not appearing in $G$, and add the following production:

$$ T \rightarrow TS \;|\; \epsilon$$

where $S$ is the start symbol of $G$. $T$ is now a new start symbol. The language of the resulting grammar is $L^{*}$.

Similarly, given grammars $G_1$ and $G_2$ for languages $L_1$ and $L_2$, respectively, we can take a new non-terminal symbol $T$ not appearing in $G_1$ nor in $G_2$, and add the following production:

$$T \rightarrow S_1 \;| \;S_2 $$

where $S_1$ and $S_2$ are the starting symbols of $G_1$ and $G_2$, respectively. $T$ is now a new start symbol. The language of the resulting grammar is $L_1 \cup L_2$. Also, make sure that you use different non-terminal symbols in $G_1$ ad $G_2$.


Store a list of all "factorials" (least common multiplies of $\{1,\ldots,k\}$) and use binary search. That reduces the number of divisions in the worst case. If the numbers $n$ you are getting are "random" then you might want to start with smaller trial divisions, or perhaps with an exponentially growing $k$, i.e. try $1,2,4,8,\ldots$ until you find some $k$ for which the LCM does not divide $n$, then take it from there using binary search.

By the way, since the LCM grows exponentially, even your algorithm only requires $\log n$ divisions. Each division takes time $\tilde{O}(n)$, so in total both your algorithm and mine are $\tilde{O}(n)$.


Approximation of minimum bandwidth on binary trees

Blache et. al, On Approximation Intractability of the Bandwidth Problem, 1997 confirms there is no PTAS for the problem unless $\text{P} = \text{NP}$, even for (binary) trees. Unger W, The Complexity of the Approximation of the Bandwidth Problem, 1998 show that for any constant $k \in \mathbb{N}$ there is no polynomial time approximation algorithm with an approximation factor of $k$. So, unfortunately there's no PTAS nor APX for the problem.

However, for some types of graphs, the problem can be solved or approximated in polynomial time. For a recent survey, see Petit J., Addenda to the Survey of Layout Problems, 2011. In the survey, see Tables 3, 4 and 8. The survey also gives a nice list of references if you want to dig in deeper to some direction. This is an more updated version of the older survey by Diaz et al., A survey of Graph Layout Problems, 2002.

In case you are interested in the exact algorithm as well, I think currently the fastest one is given by Cygan M. and Pilipczuk M., Even Faster Exact Bandwidth, 2012. The algorithm runs in $O(4.83^n)$ time.


How to solve an ILP problem with conditions in an objective function?

Introduce integer variables $x^+_i,x^-_i,y_i$, where each $y_i$ is 0 or 1.  The intended meaning of $y_i$ is that $y_i=1$ means $x_i$ is positive, $y_i=0$ means $x_i$ is zero or negative; and that $x^+_i$ captures the positive part of $x_i$ and $x^-_i$ captures the negative part.  We'll enforce that intention by adding the following constraints:

$$\begin{gather*}
x_i = x^+_i + x^-_i\\
0 \le x^+_i \le U \cdot y_i\\
L \cdot (1-y_i) \le x^-_i \le 0\\
0 \le y_i \le 1
\end{gather*}$$

This ensures that the $x_i,y_i,x^+_i,x^-_i$ are consistent.  Finally, note that

$$x_i \cdot f(x_i) = a_i x^+_i + b_i x^-_i,$$

so the objective function can be expressed as

$$\sum_i a_i x^+_i + b_i x^-_i,$$

which is a linear function of the variables.  Now maximize this objective function subject to the constraints above and any other constraints you might have, by feeding it to any ILP solver.

See Express boolean logic operations in zero-one integer linear programming (ILP) for other tricks of the trade.


How is it valid to use oracles in mathematical arguments?

Oracles are a very general formalization of the idea, "If I could solve $X$ efficiently, I could use that to solve $Y$ efficiently."  I accept that it sounds a bit silly to go as far as "If I could solve problem $X$ in constant time, I could use that to solve $Y$ efficiently" but, actually, that doesn't make any real difference at the level of detail we're working at, here.

For example, consider an oracle $O_1$ that can solve SAT in constant time, versus an oracle $O_2$ that solves SAT in, say, cubic time. The problems you can solve in polynomial time with access to $O_1$ are exactly the same as the ones you can solve in polynomial time with access to $O_2$. Sure, the polynomial will be better if you use $O_1$, but it's still a polynomial if you use $O_2$. In fact, the answer won't change whatever polynomial bound you assume on the running time of the oracle so we choose to simplify the analysis by choosing the simplest polynomial possible: $1$.

In some cases, you can see oracle arguments as hedging your bets. Although you lead your question with "Oracles don't exist", we don't actually know that. Suppose somebody produced a polynomial-time algorithm for SAT tomorrow. Wouldn't it be a shame if all we could solve with it was SAT? But because we have all kinds of oracle reductions available to us, we could already solve any NP-complete problem efficiently (the many-one reductions used to prove problems NP-complete are just a very restricted kind of oracle reduction). Conversely, if somebody proves tomorrow that SAT has no efficient algorithm, then all that work on oracles tells us that all the other NP-complete problems are also genuinely hard.

But remember that oracle arguments are conditional: if I could do $X$, then I could also do $Y$. If it turns out that you can't do $X$ then, OK, maybe you can't do $Y$ after all. But it's still a perfectly valid what-if question. So, for example, it still makes sense to consider Turing machines with an oracle for the halting problem, even though we know for a provable fact that no Turing machine can actually solve the halting problem. There's nothing wrong with asking the what-if, as long as we remember that it is a what-if.

To address a couple of other points,

  I don't understand how one can make an mathematical argument based on something that does not exist (excluding unbounded memory machines, of course).

So we're allowed to use some non-existent things but not others?  Why?

  Turing Machines (bizarre fetish formalism if you ask me)

Are you trying to get a rise out of me, Agent Kujan?

  Also, that X historic proofs rely on oracles makes oracle arguments valid is a circular argument.

Yes, that's circular. But it's also a strawman: I've never heard anyone make that argument.


Since $A$ is always the same atomic statement, every direkt translation is going to be weird. Also, natural language does not do well with (nested) implications; we typically say "leads to" not "logically implies" in reality.

I suggest you transform the formula to

$\qquad\begin{align*}
         &(\lnot A \to A) \to A \\
  \equiv &\lnot(\lnot A \to A) \lor A \\
  \equiv &\lnot(A \lor A) \lor A \\
  \equiv &\lnot A \lor A,
\end{align*}$

which is, of course, a tautology (as you've stated):

  You will help me, or you won't [, your choice].

Coming up with more complicated sentences won't give you more (logical) meaning -- all tautologies are equivalent (in Boolean logic), after all.


Approximate a smooth f(x,y) function with a polynomial function

Wikipedia:

  In statistics, polynomial regression is a form of regression analysis in which the relationship between the independent variable $x$ and the dependent variable $y$ is modelled as an $n^{th}$ degree polynomial in $x$.

One possible solution is the polynomial regression, that is, curve fitting method. Given a set of points $Y$ you may use one of two algorithms: closed form solution or gradient descent. When number of points is very large then the gradient descent is  faster than closed form solution. Also note that we measure error using residual sum of squares (RSS). Both algorithms finds coefficients by minimizing the RSS. This post may help as well.


MAP estimation (for stationary iid gaussian environment)

$\newcommand{\bd}{\mathbf{d}}\newcommand{\bw}{\mathbf{w}}\newcommand{\bX}{\mathbf{X}}$Your observation is correct--it appears to be several typos. To see why let's re-write the likelihood equation to something a bit more suitable for differentiating using matrix/vector notation. $$\text{NLL}(w) = \frac{1}{2}||\bd - \bX\bw||^2_2 + \frac{\lambda}{2}||\bw||^2_2,$$

where $\bX$ is our matrix of observations, $\bd$ is our vector of labels and $\bw$ is our vector parameter of interest. Taking the derivative yields,
$$\frac{\partial \text{NLL}}{\partial \bw} = -\bX^t(\bd - \bX\bw) + \lambda\bw.$$

Setting this equal to 0 and solving gives,
$$ \begin{align*}\lambda \bw &= \bX^t(\bd - \bX\bw) \\
&= \bX^t\bd - \bX^t\bX\bw \iff\\
\lambda\bw + \bX^t\bX\bw &= \bX^t\bd \iff \\
(\lambda\mathbf{I} + \bX^t\bX)\bw &= \bX^t\bd \iff \\
\hat{\bw}_{\text{MAP}} &= (\lambda\mathbf{I} + \bX^t\bX)^{-1}(\bX^t\bd).
\end{align*}$$

Notice that $$\bX^t\bX = \sum_i \mathbf{x_i} \mathbf{x_i}^t = R_{xx}$$ and $$\bX^t\bd = \sum_i \mathbf{x_i} d_i = r_{dx}.$$


Local search (Hill Climbing) scope and definition

Local search and hill climbing assume that you have defined a notion of "neighbor" and have defined an objective function.  It's up to you to define those for your particular application.  As you have noticed, some choices of the "neighbor" relation might make local search more effective or less effective.

In the 8-queen problem, there are multiple ways you could define the notion of "neighbor".  One option is to treat two configurations as neighbors if you can get from one to the other by moving one queen one step; then the example in the question shows that local search with this notion of neighbor might get stuck.  That is a consequence of defining "neighbor" in a particular way as much as a consequence of using local search, and is not fundamental to the notion of local search.  Nothing prevents you from defining "neighbor" differently.  For instance, one alternative is that you could consider two configuration neighbors if you can get from one configuration to the other by moving one queen any number of steps in a single direction.  That might have different properties.

What is fundamental is that local search and hill climbing can risk getting stuck in a local minimum (where all neighbors are worse than your current location, but you're not in a global minimum).  The likelihood of this may depend on the particular problem you are working with, the specific notion of neighbor you choose, and which local search method you use.  Hill climbing is particularly susceptible to local minima; other methods are designed to try to reduce the risk of local minima.


Yes, if you could consistently eliminate the offset then that would be enough. But how are you going to do that?

The state's offset is the discrete logarithm of the value in the ancilla register. But you don't know how to compute the discrete logarithm efficiently classically. And the offset changes from sample to sample. And there are so many possible offsets (assuming you picked a big number to factor) that you won't see the same one twice.


Most efficient algorithm to print 1-100 using a given random number generator

Since other folks have given approximate solutions and solutions involving taking indeterminate numbers of deviates, how about a proof that there is no such algorithm that's guaranteed to only require a finite number of RandNum50() calls?

As others have noted, printing the numbers from 1-100 in random order is equivalent to printing a random permutation of these numbers; there are 100! of these permutations, and so any particular permutation must be output with probability $\frac{1}{100!}$.

But if we knew that our algorithm used at most $k$ calls to RandNum50 for some $k$, then we could argue as follows: firstly, pad out those computation paths that make fewer than $k$ calls to RandNum50 to make additional dummy calls (that is, calls where the returned value is irrelevant), so that all computation paths make precisely $k$ calls.  Any given sequence of $k$ results from our calls to RandNum50 must result in some output permutation, and so we can build an 'outcomes table' that maps any given sequence $(r_1, r_2, \ldots, r_k)$ of results from our calls into a particular output permutation.  Since each of these outcomes is equally likely (each of them has probability $\displaystyle\frac{1}{50^k}$), then the probability of getting any particular permutation out of our algorithm must be of the form $\displaystyle\frac{c}{50^k}$ for some $c$.  But $\displaystyle\frac{1}{100!}$ can't be of this form, because $100!$ doesn't divide $50^k$ for any $k$ (for instance, 3 divides $100!$ but can't divide any number of the form $50^k$).  This means that no possible distribution of outcomes to random-number calls can produce a uniform permutation.


Consutrcting a transition diagram of a deterministic Turing machine

This is meant to give you a hint, but if you are lost, you could think about doing it in three large steps:

Make a single pass through, making sure that you encounter $0$s followed by $1$s followed by $2$s followed by $3$s.  You should think through the end conditions if this process goes smoothly, or what items you might encounter on the tape that could send you to a reject state.
Now check that there are the same number of $1$s and $2$s: go back and find the start of the $1$s.  For every $1$, replace it with an $i$, run off to the right and find a corresponding $2$ (which you must also replace with some symbol, such as $T$).  Again, think through the end conditions, and how you will know if something unexpected has happened.
Finally, check if $i=j+k$.  Run to the beginning of the $0$s, and for every $0$ you replacing (with, say, $o$), run off and find the next $T$ or $3$ and replace that with some other symbol ($F$?).  At the end, a pass left will be sufficient to tell you that there are no more $0$s, and a pass right will be sufficient to tell you that there are no remaining $T$s or $3$s.


What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$?

I'm not 100% sure on this, but I believe that the best known bound on this comes from the construction used for the best known bound on creating oblivious Turing machines. See this Gödel's Lost Letter blog post on the relationship between circuit size and oblivious Turing machines, and in particular the "Open Problems" section.

Given an arbitrary deterministic Turing machine that runs in time $T(n)$, it is known how to construct an oblivious deterministic Turing machine that accepts the same language in time $O(T(n) \log T(n))$. I believe that this implies $\operatorname{NTIME}(t) \subseteq \operatorname{DTIME}(t^{2d} \log t)$, where $d$ is the CIRCUIT-SAT exponent from the question (the 2 coming from the fact that you wrote $(nm)^d$ instead of $(n + m)^d$). However, I have not verified the details myself.


How to pick a good structural induction hypothesis

Hint: Prove the identity $\delta^*(q,xy) = \delta^*(\delta^*(q,x),y)$ by induction on $|y|$ (the length of $y$).


Representation of used space and free space in hard drives

Free space is a concept at the level of the filesystem, which is part of the operating system. It is up to the filesystem to determine what space is free, and how to exploit it.

Data is stored on the hard drive in a structured way. The filesystem divides the drive into sectors (basic units, usually 512, 1024, 2048, or 4096 bytes), and maintains data structures on the drive which store which sectors are used and which are available. These data structures also store the directory structure of the drive, which sectors comprise which file, file names, and other metadata (such as various file timestamps).

Your experiment, of storing a repeated pattern on the raw drive, doesn't constitute a legitimate use of the drive. The drive is usually used only via a filesystem. The filesystem presents to the user (i.e., the software programmer) a logical view of the hard drive. Physical details such as were different parts of a file are stored are the business of the filesystem rather than of the user (though sometimes the user would like to know more, for example in order to defragment the drive).

The same, by the way, is true for memory, which is maintained by the memory manager, another part of the operating system. The operating system allocated memory to the user, takes care of swapping, stores the memory when hibernating, and so on. On modern CPUs, the user can't just use unallocated memory - this will trigger an exception. The supporting data structures are perhaps more lightweight, but there is still an infrastructure supporting memory allocation and deallocation.


Here is a different solution than the one I suggested in the comments. Compute the sequence of factorials $1!,2!,3!,4!,\ldots$ until you get a number which is at least $n$. Since $(k+1)!/k! = O(\log (k!))$, you only compute numbers of magnitude $O(n\log n)$ and so of length $(1+o(1))|n|$ (here $|n|$ is the length of $n$ encoded in binary). Having found the least $k$ such that $n \leq k!$, we know that $n \leq m!$ iff $m \geq k$.

Since the sequence of factorials grows so fast, the running time isn't too bad — it's quasilinear in $|n|$ (at least in the RAM model). I'll let you work that out.


Why do Benes networks form bipartite graphs when you build a constraint graph for them?

You didn't explain what Beneš networks are (note that your course notes use the wrong accent on the s!), but from the notes it seems that they describe FFT algorithms. In particular, they seem to be layered graphs. Such graphs have $L$ layers $1,\ldots,L$, and edges only go between adjacent layers $i,i+1$. Color all nodes in odd layers with one color and all nodes in even layers with another color. Since $i,i+1$ have different parities, this is a valid coloring.


How to prove that adding incoming edges to source node doesn't alter the max flow

Let $G=(V,E)$ be your input graph. Now consider a maximum flow $f$ on $G$.

  Let $f$ be a flow in $G$ such that the residual network $G_R$ has no s-t path, then $f$ is a maximum flow.

Let's define $G'=(V,E')$ to be your graph  with $E'=E \cup \{(u_i,s)\}$  for $i=1,...,N$.

Since $f$ is a maximum flow on $G$, then $G_R$ has no s-t paths.
Now you can show that given $G'$, its residual network $G'_R$ does not have any s-t path too. Thus, $f$ is a max flow also for $G'$.


Can't see how this can be true: any connected undirected graph $G$ contains vertex v such that removing v results in another connected Graph $G'$

Suppose to the contrary that removing any vertex of a finite graph $G$ would disconnect it. Then $G$ could not contain any cycles (else we'd have an immediate contradiction) and so $G$ would have to be a tree. However, removing a leaf vertex of $G$ wouldn't disconnect it, contrary again to our assumption.


Getting ALL negative weight cycles of a graph using Bellman-Ford

You can use a brute force over all sequences of vertices, check if the permutation represents a negative cycle, and if so- print the cycle. This is not an efficient algorithm (runs at $O(n^{n+1})$), but a simple one

Suppose all vertices are denoted by $1,2,\ldots,n$. We denote by $C[i]$ the $i^{th}$ node in the cycle, for $i=1,2,\ldots,k$, where $3 \leq k\leq n-1$ is the size of the cycle.

A pseudo code of the algorithm goes as follows:

Let $k\gets 3$
If $k==n$, then terminate the algorithm.
Let $C[i]\gets 1$ for $i=1,2,\ldots,k$
Check if $C=(C[1],C[2],\ldots,C[k],C[1])$ is a negative cycle in the graph. If so- print $C$
If $C[1]=C[2]=\ldots=C[k]=n$, then $k \gets k+1$ and go to step 2.
Otherwise, select $C[j]=\min_i C[i]$ (if there are multiple $j$-s with the minimal value, select the one with the minimal index), assign  $C[j]\gets C[j]+1$ and go to step 4.


Existence / non-existence of a sequence with short longest increasing subsequence and decreasing subsequence?

The answer to the OP's question is, no if $N\le 7$ and yes otherwise.

For given any positive integer $r$ and $s$, the celebrated Erdős–Szekeres theorem shows that for any sequence of distinct real numbers with length at least $(r − 1)(s − 1) + 1$ contains an increasing subsequence of length $r$ or a decreasing subsequence of length $s$.
It turns out that bound, $(r-1)(s-1)+1$ is tight. That is, for any positive number $r$ and $s$, there is a sequence of distinct numbers with length $(r-1)(s-1)$ that contains no increasing subsequence of length $r$ and no decreasing subsequence of length $s$.
Here is such an example.
$$\begin{array} {}
&s-1, &s-2, &\cdots,&2, &1\\
&2(s-1), &(s-1)+ s-2,  &\cdots, &(s-1)+ 2, &(s-1)+ 1\\
&\vdots &\vdots &\vdots &\vdots &\vdots \\
&(r-2)(s-1), &(r-3)(s-1)+s-2, &\cdots, &(r-3)(s-1)+2, &(r-3)(s-1)+1\\
&(r-1)(s-1), &(r-2)(s-1)+s-2, &\cdots, &(r-2)(s-1)+2, &(r-2)(s-1)+1\\
\end{array}$$
Consider the numbers above, reading from left to right and then from top to bottom. In other words, the sequence is $s-1$ down to $1$, followed by $2(s-1)$ down to $(s-1)+1$, etc and finally followed by $(r-1)(s-1)$ down to $(r-2)(s-1)+1$, all in step of $1$.
It is easy to see that there is no increasing subsequence of length r and no decreasing subsequence of length $s$.
For example, when $r=s=5$, we have $$4,3,2,1,\ \, 8,7,6,5,\ \,12,11,10,9,\ \,16,15,14,13$$
which does not have increasing subsequence of length $5$ nor decreasing subsequence of length $5$.

If we let $r=s$, the section above implies that, for any positive number $N$, there exists an integer sequence of length $N$ with all unique elements such that the length of its longest increasing subsequence as well as that of its longest decreasing subsequence is at most $\lceil\sqrt N\rceil$. And $\lceil\sqrt N\rceil$ is the tight upper bound.
Since $$\lceil\sqrt N\rceil\ge \lfloor\frac N2\rfloor\ \text{ for all } N\le 7$$ and $$\lceil\sqrt N\rceil\lt \lfloor\frac N2\rfloor\ \text{ for all } N\gt 7,$$
the answer to the OP's question is, no if $N\le 7$ and yes otherwise.
For example, for $N=8$, we have sequence $3,2,1,6,5,4,9,8,7$.


Why is GFp -> GFq false in LTL, even though GFp and GFq are false?

This happens because of the way LTL formulae are evaluated over Kripke structures: Recall that LTL is first of all a logic of traces; when we say that a Kripke structure $S$ satisfies $\varphi$, we mean that all its traces do, i.e. we have an implicit universal quantification.

The consequence is that, for an LTL formula $\varphi$, it is possible that neither $\varphi$ nor $\neg\varphi$ is true for $S$, because neither holds for all traces. Similarly, none of your three formulas above holds for every trace.

If you are more familiar with predicate calculus, this is just saying that $(\forall x.A)\vee(\forall x.\neg A)$ is not a tautology, and neither is $(\forall x.A)\vee(\forall x.B)\vee(\forall x.A\to B)$.


A decimal number is divisible by 100 if it ends with two zeroes. The same thing happens in your case, and leads to a solution using a single NOR gate.


Fast checking Matrix multiplication in mod 10

I got Accepted by using Freivald's algorithm as suggested by @David Richerby. Thank you very much !

I have not tested the brute-force solution using Coppersmith-Winograd algorithm yet. Will report in a couple of days, by the way I think it might not get Accepted but possibly will gain a fairly amount of points.

For those who want to check your implementation, submit your code on http://vn.spoj.com/problems/VMATRIX/. The problem statement is in Vietnamese, so here is the short description of input format:

  First line is number of testcase (the example gives 2 testcases)
  For each testcase:
  the first line is size of 3 matrices, N. In 20% testcase N <= 100.
  next N * N lines: matrix A
  next N * N lines: matrix B
  next N * N lines: matrix C

Output: YES or NO for the result.


Turing Machines and Algorithm for Language Acceptance

Your guess is correct: deciding whether two Turing machines are equivalent (i.e. accept the same language) is an undedicable problem.

To prove this, it should be possible to reduce this problem to the halting problem.

You can also use Rice's theorem.

The theorem states the following:

  Let P be any non-trivial property of languages of Turing
  machines. Then, the following language is undecidable, $LP=\{\langle M\rangle : L(M) \text{ satisfies } P\}$.

Note that $L \text{ satisfies } P$ means $L \in P$.

Note also that a “trivial property” is a property that is either satisfied by all languages, or a property that is not satisfied by any language.

Now, if you consider two machines $M_1$ and $M_2$, deciding whether $L(M_1) = L(M_2)$ is deciding whether $M_2 \in \{\langle M \rangle : L(M) \text{ satisfies } \{L(M_1)\}\}$.

Since $\{L(M_1)\}$ is non trivial (there exist machines which recognize it and there exist machines which do not recognize it), this problem is undecidable.


There is no need to consider the intersection $L \cap F$. If $F$ is finite, then so is $L \cap F$, but that is not a useful fact here.

Insteed, one should proceed by contradiction. Suppose $L \setminus F$ were a context-free language. Then there exists a context-free grammar $G_1 = (V_1,\Sigma,R_1,S_1)$ such that $L(G_1) = L \setminus F$. But since $F$ is finite, then $F$ is trivially a context-free language. Let $G_2 = (V_2,\Sigma,R_2,S_2)$ be a context-free grammar such that $L(G_2) = F$.

But then $G = (V,\Sigma,R,S)$ where $S \notin V_1 \cup V_2$ and

$$V = V_1 \cup V_2 \cup \{ S \}$$
$$R = R_1 \cup R_2 \cup \{ S \rightarrow S_1, S \rightarrow S_2 \}$$

is a context-free grammar such that $L(G) = L$. This is a contradiction.


Can a perfect matching always be found by a picking sequence?

Yes, it can. This can be proved by mathematical induction on $n$.

Denote by $U$ the set of people. For a subset of people $P$, denote by $N(P)$ the neighborhood of $P$, that is the set of items that at least one person in $P$ likes. By Hall's marriage theorem, $|P|\le |N(P)|$ for all $P$.

If $|P|< |N(P)|$ for all $P\subsetneq U$, then we can let an arbitrary person pick first. After his picking, $N(P)$ is decreased by at most 1 for all $P$, so $|P|\le |N(P)|$ holds for all $P$ in the remaining graph. Therefore there is still a perfect matching in the remaining graph by Hall's marriage theorem, and there is a valid picking sequence by inductive assumption.

If there exists $P\subsetneq U$ such that $|P|=|N(P)|$, then there is a perfect matching in the subgraph induced by $P\cup N(P)$, and by inductive assumption there is a valid picking sequence for people in $P$ in this subgraph. We can apply this picking sequence in our orignial graph first, and the result is the same, that is, exactly all items in $N(P)$ are picked. Note there is still a perfect matching in the remaining graph, so we can again use the inductive assumption to complete the picking sequence.


Exponential separation between NFAs and DFAs in the presence of unions

Consider the language $M_n = (L_n \#)^*L_n$, where $\#$ is a new symbol.
The NFA complexity of $M_n$ is $n$ (allowing for multiple initial states). Indeed, here is one NFA having $n$ states accepting $M_n$. The states are $q_1,\ldots,q_n$, all both initial and final. There is a self-loop around $q_i$ for each $j \neq i$. Furthermore, there are transitions from each $q_i$ to each $q_j$ labeled $\#$. The matching lower bound follows from the DFA complexity of $L_n = M_n \cap \{1,\ldots,n\}^*$ being $2^n$.
In contrast, we will show that the DFA covering complexity of $M_n$ is $2^n$. For the upper bound, consider a DFA whose states are $q_S$ for $S \subseteq \{1,\ldots,n\}$. The states keep track of the letters seen so far: the initial state is $q_\emptyset$, and $\delta(q_S,i) = q_{S \cup \{i\}}$. All states other than $q_{\{1,\ldots,n\}}$ are accepting. When seeing $\#$, if we're in $q_{\{1,\ldots,n\}}$ then we stay put, and otherwise we move to $q_\emptyset$.

Let $[n] = \{1,\ldots,n\}$. For $S \subseteq [n]$, let $w_S$ consist of all letters in $S$ in order. Let $P$ denote all words over $[n]$ containing each letter at most twice, and missing at least one letter.
Suppose that $M_n = \bigcup_{i=1}^N L(A_i)$, where the $A_i$ are DFAs. We can identify $L_i := L(A_i) \cap (P\#)^*P$ with a language over the alphabet $P$ in the natural way ($p_1\#\ldots\#p_\ell$ corresponds to the word of length $\ell$ whose letters are $p_1,\ldots,p_\ell$). Say that $x \in P^*$ is good for $L_i$ if for all $p \in P$ there exists $y_p \in P^*$ such that $xpy_p \in L_i$.
Suppose that no $x$ is good for $L_i$. Let $\ell \geq 0$. For $0 \leq r \leq \ell$, let $S_r$ be the set of length $r$ prefixes of words in $L_i \cap P^\ell$. If $|S_{r+1}| > (|P|-1)|S_r|$ for some $r < \ell$, then by the pigeonhole principle there is some $x \in S_r$ such that $xp \in S_{r+1}$ for all $p \in P$; but then $x$ is good. It follows that $|L_i \cap P^\ell| = |S_\ell| \leq (|P|-1)^\ell |S_0| = (|P|-1)^\ell$.
If no $x$ is good for any $A_i$, then for all $\ell \geq 0$ we have
$$
|P|^\ell \leq \sum_{i=1}^N |L_i \cap P^\ell| \leq N(|P|-1)^\ell,
$$
which is contradictory for large enough $\ell$. Therefore some $x$ is good for some $A_i$.
Let us identify $x \in P^*$ with the corresponding word over $[n] \cup \{\#\}$. Thus for each $p \in P$ there is $y_p \in M_n$ such that
$$
x\# p\# y_p \in L(A_i).
$$
We claim that the $2^n$ words $x \# w_S$ (we allow $S = [n]$) are pairwise inequivalent in the Myhill–Nerode relation of $L(A_i)$, and so $A_i$ has at least $2^n$ states.
Indeed, let $S,T$ be two different subsets of $[n]$. Assume without loss of generality that $j \in T \setminus S$. Since $w_S w_{[n] \setminus \{j\}} \in P$, by assumption $x \# w_S w_{[n] \setminus \{j\}} \# y_p \in L(A_i)$, where $p = w_S w_{[n] \setminus \{j\}}$. In contrast, $w_T w_{[n] \setminus \{j\}}$ contains all letters, hence $x \# w_T w_{[n] \setminus \{j\}} \# y_p \notin M_n$, and so $x \# w_T w_{[n] \setminus \{j\}} \# y_p \notin L(A_i)$. This shows that the two words $x \# w_S, x \# w_T$ are inequivalent.


Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?

Adding a weight to every edge adds more weight to long paths than short paths. (Long in the sense of having many edges.)

For example, suppose the lowest-cost edge has weight $-2$ and there are two paths from $a$ to $b$: a single edge of weight $3$ and a path with two edges, each of weight $1$.  The two-edge path has the lowest weight.  However, if you add $2$ to every edge, the one-edge path has weight $5$ but the two-edge path now has weight $6$, so you get the wrong answer.


What is the difference between Hamming Distance and Manhattan Distance for non-binary data?

The Hamming distance between two length-$n$ vectors is the number of coordinates in which they differ. I've only ever seen it on finite alphabets, i.e. vectors in $\Sigma^n$ where $|\Sigma|\in \mathbb{N}$. In theory there is no problem with extending this to $\mathbb{R}$, but you may have to be careful with how you use equality of floats for instance.
Specifically over $\mathbb{R}^2$, if we consider $x=(x_0,x_1)$ and $y=(y_0,y_1)$:
$$\begin{cases}
dist_\textsf{Manhattan}(x,y)=|x_0-y_0|+|x_1-y_1|\\
dist_\textsf{Hamming}(x,y)=\delta_{x_0,y_0}+\delta_{x_1,y_1}\end{cases}$$
Where $\delta_{a,b}=\begin{cases}1 \text{ if }a\neq b \\0 \text{ otherwise}\end{cases}.$
The two coincide in $\{0,1\}^n$, because in that case we have $\delta_{a,b}=|a-b|$.


Runtime of Divide and Conquer Flavored Bogo Sort

The solution to the recurrence $T(n) = 2T(n/2) + O(2^n)$ is $T(n) = O(2^n)$.


Generate a random graph with geometrical degree distribution

You can use the configuration model for this. Create a "stub" array where each of the $n$ vertices appears in the array $k_i \sim \text{Geom}(p)$ times. Shuffle the array and then treat each adjacent pair in the array as an edge in the graph. Here's some python code to illustrate.

from numpy.random.mtrand import geometric
from random import shuffle
from _collections import defaultdict

if __name__ == '__main__':
    # Number of vertices
    n = 1000

    # Geometric distribution probability parameter
    p = 0.5

    stubs = []
    for i in xrange(0, n):
        # Sample the degree from the geometric distribution
        degree = geometric(p)
        # Insert into the stubs array the current vertex label degree times
        stubs += [i] * degree

    # Shuffle the values
    shuffle(stubs)

    # Build the graph
    G = {}
    for i in xrange(0, n):
        G[i] = []

    for i in xrange(1, len(stubs), 2):
        G[stubs[i]].append(stubs[i-1])
        G[stubs[i-1]].append(stubs[i])

    # Recover the degree distribution
    degrees = { i : len(neighbors) for i, neighbors in G.items() }

    dist = defaultdict(int)
    for (vertex, degree) in degrees.items():
        dist[degree] += 1

    print("Degree, empirical, theoretical")
    for (degree, freq) in dist.items():
        print("%d %f %f" % (degree, freq / float(n),  pow((1 - p), degree - 1) * p ))

Sample output:

Degree, empirical, theoretical
1 0.496000 0.500000
2 0.254000 0.250000
3 0.128000 0.125000
4 0.071000 0.062500
5 0.023000 0.031250
6 0.018000 0.015625
7 0.005000 0.007812
8 0.003000 0.003906
9 0.002000 0.001953

For more detailed description of the the configuration model, see Section 13.2 p. 435 of Networks by Newman.


What is the expressive power of finite-state transducers and pushdown transducers?

we can construct a finite state transducer [that maps $\{ab\}$ to $\{a^nb^n n \geq 1\}$].

No, we can't. REG is closed against finite-state transduction.

Wikipedia hints as much without citation; planetmath.org lists some standard references, in particular Hopcroft/Ullman.


Algorithm notation between two functions

$\frac{f(n)}{g(n)} = \frac{n^{1.6}}{n^{1.5}} = n^{0.1}$ is unbounded. Hence, for any $c > 0$ there is $n_0 \in \mathbb{N}$ such that $n^{0.1} > c$ for all $n > n_0$. As a result, for any $c > 0$, we have $n^{1.6} = n^{0.1} \cdot n^{1.5} > c n^{1.5}$ for all $n > n_0$.

Notice this does not really make use of $1.5$ and $1.6$ other than $1.6 > 1.5$. In fact, using the same method and the fact that $n^\varepsilon$ is unbounded for any $\varepsilon > 0$, you can prove the more general bound $n^a \in \omega(n^b)$ for any $a > b \ge 0$.


Solving/Optimizing a linear system in a finite field (Z/2Z)

(Note that a random assignment has probability at least 1/(1+$\hspace{.03 in}$(size($\hspace{.03 in}$Y$\hspace{.03 in}$)))

of making at least 1/2 of Y's entries equal 1.  That can be derandomized

by sequentially setting each variable to [something that forces at least

as many of Y's entries to 1 as it forces to 0, with ties broken arbitrarily].)

By this paper's proof of Theorem 5.6, for all real

numbers $\epsilon$, if  $0 < \epsilon$  then the promise problem

Input:  instance of your problem in which each row of A has exactly 4 ones

must output YES if:    there is an assignment which makes more than 1-$\hspace{.03 in}\epsilon$ of Y's entries equal 1

must output NO if:     for every assignment, less than  (1/2)$\hspace{.03 in}$+$\hspace{.03 in}\epsilon$  of Y's entries equal 1

is NP-hard.

When parameterized by the number of zeros in Y, your problem is obviously in W$[\hspace{-0.02 in}$P$]$O,

but I don't know anything else about your problem's parameterized complexity.

This paper gives a possible try for your problem,

although it looks like it's just a student's "3rd Year Project Report".


Build single hash table from any column and augment it with counter, set it to 1.
Add second column to the hash table discarding not existing values from the second column. Optionally you can remove values that are still singular.
Add third column element by element, store the maximal encountered triplet.

This will run in expected $\mathcal O(n)$ time, where $n$ is column length.

What you have proposed looks a bit like selection sort. Making it explicit, sort columns in descending order and start checking for triplet. It would give $\mathcal O(n\log(n))$ runtime.


Emergent complexity and Turing Completeness

I suggest you  to give  a look to S. Wolfram's book "A New Kind Of Science" (that is also available online).

The centeral ideas are:

Computation is everywhere
Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication (Principle of Computational Equivalence)
Computation irreducibility: while many computations admit shortcuts that allow them to be performed more rapidly, others cannot be sped up.

Though these ideas are probably not new, they are exposed in a fascinating way (to be honest, a rather informal and non-mathematical "way").


Algorithm to get any spanning tree not necessarily a minimum spanning tree

Use the BFS or the DFS algorithms. They work in $O(n)$ and output a spanning tree if the input is a connected graph


Hint. The definition of reduction from $X$ to $Y$ requires that "yes" instances of $X$ be mapped to "yes" instances of $Y$ and "no" instances to "no" instances.


P=NP giving a deterministic algorithm for SAT

I like the way you think, but there's a gap in your attempt.

$\mathrm{P}$ and $\mathrm{NP}$ are classes of decision problems, i.e., computational tasks where the answer is either "yes" or "no". Nondeterministically generating a satisfying assignment isn't a decision problem, so it isn't in $\mathrm{NP}$, so the assumption that $\mathrm{P}=\mathrm{NP}$ doesn't give you a deterministic algorithm for it. It feels like it ought to, but that's not a proof.


Recall that for $k > 1$, by definition we have $\log^*k = \log^*(\log{k}) + 1$.

By applying the definition twice, we see that $\log^*(2^{2^n}) = \log^*n + 2$.  Now we can compare $\log^*n + 2$ and $(\log^*n)^2$.


Algorithm for creating n-multiset out of x?

Every such arrangement of 15 balls to 21 boxes corresponds, in a one-to-one fashion, to a string of the form *|**||||...|*, where there are a total of 35 symbols in the string, exactly 15 stars and 20 bars.  (Think of each * as a ball, and each | as a divider between two boxes.)  These, in turn, correspond to the set of binary strings of length 35 that contain exactly 20 one's, which in turn corresponds to the set of ways to choose a subset of 20 positions out of a set of 35 possibilities.

It follows that you can enumerate the set of valid nodes by enumerating all ways to choose a subset of size 20 that's contained in $\{1,2,\dots,35\}$.  There are standard ways to perform this enumeration.  One way is to use the combinatorial number system, which creates a correspondence between these subsets and integers in the range $\{1,2,\dots,{35 \choose 20}\}$.  See also https://en.wikipedia.org/wiki/Combination#Enumerating_k-combinations, Get a fixed-size family of k-element subsets, https://cs.stackexchange.com/a/72543/755 for more.


Find height of deepest FULL level in binary tree

How would you determine the answer if you were looking at a graphical representation of the tree? You would scan all the levels from the root downwards until you found one that isn't full.

Formally, that is a breadth-first search of the tree that stops whenever a node with less than two children is found. Since you are working on a tree rather than a generic graph, you may rewrite it as follows:

Let $Q$ be a new queue of nodes, initially containing only the root.
While $v$, the first element of $Q$, has two children $v_l$ and $v_r$, remove $v$ and enqueue both $v_l$ and $v_r$.


Loop invariant condition IsPrime program

The condition $2 \leq i \leq \lfloor \sqrt{n} \rfloor$ is a reasonable part of the invariant you seek. As I think you realize, this is not enough.

You proposed to also require $n \!\!\!\mod i \neq 0 \implies n$ prime, but this can not realistically hold. For instance, take $n=3^2=9$: running the loop we would start from $i=2$ and have $n \!\!\!\mod i = 1 \neq 0$ but clearly $n=9$ is not prime, which makes the condition false. Hence, that is not really an invariant.

What we need is something expressing "we checked all the numbers from $2$ to $i-1$, and we did not find any divisors". This can be written as "for all the numbers $k$ such that $2\leq k < i$, we have $k\!\! \mod n \neq 0$".

That might be enough, but the loop seems to have a bug to me: for e.g. $n=5^2$ we never try to divide for $i=5$, consequently returning that $25$ is prime. Perhaps you should fix the bug first, and then adapt the first "range" invariant accordingly.


Is the language of all TMs accepting all strings starting with 010 decidable?

According to $Rice's$ $theorem$,

$\qquad$ $L$ = { $\langle M \rangle$ | $L (M) ∈ P$ } is undecidable if $P$ is a non-trivial semantic property of $\qquad$$L(M)$.

$\qquad$ P is the set of all languages that satisfies a particular property

If the following two properties hold, it is proved as undecidable −

Property 1 (Semantic) − If $M_1$ and $M_2$ recognize the same language, then either $\qquad$$\qquad$$\langle M_1 \rangle ,\langle M_2\rangle  \in L$ or $\langle M_1 \rangle ,\langle M_2\rangle \notin L$.

Property 2 (Non-trivial) − There exists $M_1$ and $M_2$ such that $\langle M_1 \rangle \notin L$ and $\langle M_2 \rangle \notin L$.

Now,

$\quad$ 1) For any two TMs, $M_1$ and $M_2$ with $L(M_1) = L(M_2)$ either both $M_1$ and $M_2$ both accept all strings starting with 010 or both don't accept.

$\quad$ 2) There exists TMs that accepts strings starting with 010 and not accepting strings that starts with 010.

Therefore, the property of the language of a TM to start with 010 is a semantic and non-trivial. Hence, according to Rice's theorem, the given language is undecidable.

$L$ is recognizable as TMs that accepts when given as input strings starting with 010 always accepts and halts. But complement of $L$ isn't recognizable as both $L$ and complement of $L$ being recognizable will mean that $L$ is decidable(why?).


What is the significance of the following equation in computer vision?

I would agree - energy minimization for snakes (active contours).

It minimizes second derivative - bending of the curve.

Minimizes the difference between the image (probably it's edges) and contour (at discreet contour points - the reason for having Dirac impulse in the expression).

Usually one could expect also to have minimization of the first derivative - stretching of the snake.

More details and references on wiki - active contour


Solving a multivariate equation for asymptotic complexity


What does this definition of a Primary key mean?

Note how $K$ can be a set of columns. Irreducibility means that you have to pick minimal sets of columns.

Nota bene: They should require $K \neq \emptyset$.

For instance, consider this relation.

A   B   C

1   4   4
2   4   6
3   6   6

Let us investigate all possible keys.

A -- unique and irreducible.
B -- not unique.
C -- not unique.
A,B -- reducible to A.
A,C -- reducible to A.
B,C -- unique and irreducible.
A,B,C -- reducible to A.

Hence, there are two choices for primare keys here: A and B,C.


Finding Shortest Paths of weighted graph using stacks

As with most graph searching algorithms, you have to keep the state of each node during the searching. The state would have following values: white, gray, black with following interpretation:

white = node has not yet been discovered during the current search, or it is unreachable.
gray = node that was discovered, but not yet processed by the search algorithm.
black = reachable nodes in your graph, that the search algorithm has discovered and also processed.

This labeling ensures that you do not search in endless loops.

To get all shortest paths from a node s to another node e:

mark all nodes nodes as white.
then as you visit nodes you label them gray and put them on the stack.
If you processed all neighbours of a node, you label it black.
To recover all the shortest paths from s to e, you need to maintain an array, call it parents, i.e. parents(v) = u, meaning v was visited from u.

After you searched the whole graph, you proceed backwards from the end node e via the parents array, to get all the shortest paths from the starting node s.


How to calculate least common multiple (LCM) for two numbers with constants (shifts)?

Given integers $a,b \geq 1$ and $c,d \geq 0$, you are looking for the set of solutions of $ax + c = by + d$ over integers $x,y \geq 0$. We can assume without loss of generality that $d = 0$ (replace $c,d$ with $c-d,0$ or $0,d-c$) and that $(a,b,c) = 1$ (otherwise, divide everything by the GCD).

I claim that if there is any solution then necessarily $(a,b) = 1$. Indeed, suppose that $(a,b) = g > 1$. If $ax + c = by$ then $g \mid ax,by$ implies $g \mid c$, and so $(a,b,c) = g > 1$, contrary to assumption. Therefore $(a,b) = 1$.

If $ax + c = by$ then $ax + c \equiv 0 \pmod{b}$ and so $x \equiv -c/a \pmod{b}$ (note that we can divide by $a$ since $(a,b)=1$). Similarly, $y \equiv c/b \pmod{a}$. These equations essentially give us both the minimal solution and all solutions.

As a demonstration, consider your example: $30x+10 = 25y+5$. This is equivalent to $6x+1 = 5y$, so $(a,b,c) = (6,5,1)$. Any solution must satisfy $x \equiv -1/6 \equiv 4 \pmod{5}$ and $y \equiv 1/5 \equiv 5 \pmod{6}$. Indeed, $6 \cdot 4 + 1 = 5 \cdot 5$. The general solution is $(x,y) = (4+5N,5+6N)$.


Theorem The following are equivalent.

$L$ is accepted by a deterministic LBA with stack
$L$ is accepted by a nondeterministic LBA with stack
$L$ is in $\operatorname{DTIME}(c^n)$ for some constant $c$.

So the computational power of a LBA with stack for decision problems is well understood. The exponential runtime limits the usefulness of this knowledge in practice. But the notion of an LBA with stack can be generalized to an $S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA). It consists of

a read-only input tape, surrounded by endmarkers,
a finite state control,
a read-write storage tape of length $S(n)$, where $n$ is the length of the input string, and
a stack

In "Hopcroft/Ullman (1979) Introduction to Automata Theory, Languages, and Computation (1st ed.) we find:

Theorem 14.1 The following are equivalent for $S(n)\geq\log n$.

$L$ is accepted by a deterministic $S(n)$-AuxPDA
$L$ is accepted by a nondeterministic $S(n)$-AuxPDA
$L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$.

with the surprising:

Corollary $L$ is in $\mathsf P$ if and only if $L$ is accepted by a $\log n$-AuxPDA.

The proof consists of three parts: (1) If L is accepted by a nondeterministic $S(n)$-AuxPDA with $S(n)\geq \log n$, then $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$. (2) If $L$ is in $\operatorname{DTIME}(T(n))$, then $L$ is accepted in time $T^4(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input). (3) If $L$ is accepted in time $T(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input), then $L$ is accepted by a deterministic $\log T(n)$-AuxPDA.

Part (1) is basically a rigorous proof that the "halting problem is decidable", where the number of operations was counted thoroughly. Part (2) is the creative idea that prepares the stage for part (3). Part (3) uses the auxiliary storage for tracking the time step, which allows to reconstruct the head position due to the very simple forward-backward head scan pattern, and the stack for recursive backtracking. (So this proof also contains the two observations which I wanted to make more rigorous. This answer is already long enough anyway, so I won't go into more detail here.)

This leads to the following answer for the initial question Is a LBA with stack more powerful than a LBA without?: The question is equivalent to a well know open problem, and the expectation is that it is indeed more powerful.


Lambda calculus :difficulty in getting hang of induction and conversion

In the definition of substitution $[N_1/ x]N$, we describe how to replace all free occurrences of the variable $x$ by the expression $N_1$ throughout the expression $N$.

The formation rules defining the syntax of $\lambda$-calculus expressions $e$ are

$$ N ::= x \mid \lambda x.P \mid N_1 N_2 $$

where $x$ ranges over a set of variables. One should think of the abstraction $\lambda x.P$ as a function with argument $x$ and body $P$ – or using standard programming terminology, we think of it as a procedure with formal parameter $x$ and body $P$.

In $\lambda x.P$, the variable $x$ is not free within $P$, so a substitution $[N/x](\lambda x.P)$ cannot change anything.

Moreover, writing $\lambda N.P$ does not make sense; the argument/formal parameter must be a variable.

If you are still puzzled, think of an applied lambda-calculus with integer numerals and consider the expression $\lambda x. x +7$ that informally denotes a function that adds $7$ to its argument. Your proposed substitution rule would give us that $[14/x](\lambda x. x+7)  = \lambda 14. x +7$. What would that even mean? (I have no idea.)

By the way, the notion of induction is not esoteric at all. Induction is a central proof technique in mathematics and in computer science, and one cannot understand the lambda calculus without being familiar with it. See https://en.wikipedia.org/wiki/Mathematical_induction for an introduction.


Using Taylor series in 1D Grayscale Image

I am sure these are finite differences, so the first "derivatives" are just

$B_i := I_{i+1} - I_i$

and the second "derivatives" are the differences of those:

$D_i := B_{i+1} - B_i$

Write it out and solve for $I_i$.


How to handle L-attributed SDDs with LR parsers

Let's start with #3: Can you always walk the AST in any way you like after it is built? Yes, you can, and the Dragon book has an extensive discussion about how to do that for a given set of attributes; in particular, how to avoid (or detect) infinite regression.
Moreover, there is really no inefficiency in doing it this way. Or, to put it another way, trying to compute attributes on the fly during the parse does not speed things up much if at all, and can even slow things down. Even if it were slightly inefficient, it generally makes the parser much more complicated than it should be, partly because of the artificial hoops which need to be jumped through to perform the analysis online, and partly because it tends to interlace code which doesn't need to be codependent. Separation of concerns is almost always a good programming model.
With that out of the way, and briefly:

What the Dragon book says (iirc, because I still don't have either of my copies at my fingertips) is that adding markers can destroy the LR property of a grammar. This doesn't happen if the grammar happens to be LL. It's not actually necessary for the whole grammar to be LL, but it's a bit tricky to provide a formal description of what it means for a part of a grammar to be LL, although it's possible. Before LALR parser generators were available, there was quite a lot of research into left corner parsing (LCP), which you could look at if you're interested in the concepts. (I don't have references handy but the phrase should still be usable as a search term.)
If you want to introduce a marker into an LR grammar, you need to ensure that the reduction action for that marker does not conflict with any shift action. For that to be the case, each itemset which contains an item whose • is just before the marker must be free of items which would allow a shift of a symbol which could follow the marker. This is very similar to the LL(1) criterion, because it is effectively saying that the parser needs to be able to predict a single unique production at that point in the parse, something which is not normally required in an LR parser. (Strictly speaking, the parser only needs to be able to predict a single unique production for some lookahead symbols -- as I said, those which might follow the marker -- but that fact doesn't usually help much.)
A common way of creating this sort of conflict is when you have two similar productions with different markers before the same symbol. See the bison manual for some specific examples. (Bison automatically inserts markers for you when you put an action in the middle of the rule, which is why that section is called what it is called.)

LR grammars can recognise a strictly larger set of languages than LL grammars. But here, we're not talking about just recognising whether a sentence is in a language or not. The goal of parsing (outside of some formal language theory discussions) is almost always to recursively break the input into parts (which is the root of the verb "to parse") and understand the relationships between those parts.
All the same, LR parsers are, by and large, more capable at parsing as well. For example, the common language of arithmetic expressions can easily be recognised by an LL parser, and most textbooks insist that students work through the chore of destroying refactoring a simple operator grammar in order to make it possible to parse with a top-down parser. But the resulting LL grammar does not produce the same AST; it has completely lost any information about operator associativity. In order to use the parse, it is necessary to rewrite the AST to recover that information. The fact that an LL grammar cannot produce a parse tree for left-associative operators seems to me like it should count as a weakness.
In any event, if there is an LL grammar which correctly parses a language then you can indeed insert whatever attributes you like wherever you want to insert them. But that grammar will also be an LR grammar, and you will be able to insert markers freely into that grammar without losing the LR property. Unfortunately, it is possible that adding markers to the $LL(1)$ grammar will produce a grammar which is not $LALR(1)$ (since not all $LR(1)$ grammars are $LALR(1)$). But as far as I know this doesn't show up often in practical grammars.
If you want an academic reference, you can look at Beatty, J. C. (1982). "On the relationship between LL(1) and LR(1) grammars", Journal of the ACM, 29 (4 (Oct)): 1007–1022. (doi:10.1145/322344.322350. I got that from a reference in the Wikipedia entry on LL grammars; the reference link is not pay-walled, at least as of today.)


If the Halting Problem was solvable, and we solved it, what would be its implications?

Maybe I should make a more serious answer. First off: the unsolvability of the halting problem by "conventional" computing methods is a logical theorem. It is very simple to prove, and can be proven in almost any reasonable logical framework (that can express the problem).
There are however two questions we can reasonably ask:

What are the mathematical consequences of having a halting oracle? A halting oracle can be imagined as a genie (instantly) giving us the answer to any halting problem we ask of it. This is a rather well studied subject in computability theory and the "world" in which you have access to such a genie is called the first turing degree.
An interesting observation is that even given such an oracle, we can ask computational problems for which we cannot compute the answer, such as "does the turing machine $M$ with access to the halting oracle halt on all inputs"? The proof is almost identical to the original proof of undecidability of the halting problem!

What would happen if we could solve all halting problems that come up "in practice"? This isn't really a mathematical question, since you would need to define in practice but it's a really interesting scientific question. The whole field of termination analysis tries to find such algorithms. It works surprisingly well: if you write a reasonable program to compute some quantity, odds are that there is a tool in this list that can handle it.
It's not too hard to find examples that break these tools though: even a program as simple as the $3n+1$ algorithm would choke them, since there it is not known whether it halts on all inputs. A lot of similar open problems in number theory (the twin primes conjecture, the existence of odd perfect numbers) can be expressed as a halting problem, which suggests that there are many such problems that can't be handled by any "reasonable" automated termination tool.


Solving $\text{key}=(\sum_{K=0}^n\frac{1}{a^K})\bmod m$ with High limits

Solve a linear homogeneous recurrence to obtain the identity $$\sum_{K=0}^n\frac1{a^K}=\begin{cases}\frac{1-1/a^{n+1}}{1-1/a}&\text{if }a\neq1\pmod m\\n+1&\text{if }a=1\pmod m\end{cases}$$ and use efficient algorithms for multiplicative inversion and exponentiation mod $m$.


Tractable usually means decidable in polynomial time.  Under that definition, NP-complete problems appear to be intractable, but they're still decidable.


Shortest Non-Subsequence String With Constant-Size Alphabet

For each $i$, let $s(i)$ be a string of length $f(i)+1$ that is not a subsequence of $S[1\ldots i]$, then what you seek for is exactly $s(n)$. Also denote $g(i) = \min\left(\ell\left(i,\sigma_1\right),\ldots,\ell\left(i,\sigma_{|\Sigma|}\right)\right)$. $g(i)$'s can be computed in $O(n)$ time in advance.

We have
$$
s(i)=s(g(i)-1)S[g(i)].
$$
Firstly $s(g(i)-1)S[g(i)]$ is of length $f(i)+1$. Suppose by contradiction $s(g(i)-1)S[g(i)]$ is a subsequence of $S[1\ldots i]$, then the index that the last character $S[g(i)]$ matches must be less than or equal to $g(i)$, which means $s(g(i)-1)$ is a subsequence of $S[1\ldots (g(i)-1)]$, a contradiction. So the recurrence is correct.

Now you can use this recurrence to compute $s(n)$:

Let $i \leftarrow n$, and let $s$ be an empty string.
If $g(i)$ does not exist, which means there is at least one character not appearing in $S[1\ldots i]$, insert this character to the beginning of $s$ and return $s$.
Insert $S[g(i)]$ to the beginning of $s$.
Let $i\leftarrow g(i)-1$.
Go back to step 2.


Was it known that $\mathsf{LTIME \subsetneq NLTIME}$?

The other answer is quite misleading. The classes $\mathrm{DTIME}(\log n)$ and $\mathrm{NTIME}(\log n)$, usually denoted DLOGTIME and NLOGTIME, do indeed have a sensible and well-accepted meaning in the literature.

When discussing sublinear time classes (deterministic, nondeterministic, alternating, etc.), it is standard to use a Turing machine model that does not have an input tape, but a query tape on which one can write (in binary) the index of an input position, and obtain the input symbol at that position by entering a special state. (The query tape is not cleared or otherwise modified after a query.) This is essentially the same mechanism as used by oracle Turing machines, and the model is sometimes called the random-access Turing machine.

And yes, it is known that $\mathrm{DLOGTIME\subsetneq NLOGTIME}$: a simple NLOGTIME language not recognizable in DLOGTIME is
$$L=\{w\in\{0,1\}^*: \text{$w$ has at least one $1$ at some position}\}.$$
There are unconditional separations like this even for some bigger classes, for example $\mathrm{AC^0}$, whose uniform version coincides with languages recognizable by an alternating TM in time $O(\log n)$ with $O(1)$ alternations.