If a number is of the form $n = 2^{2^k}$ then you never encounter the floor as you open up the recursion, and then there is no problem. If you're interested in a general upper bound, you can prove by induction that $T(n)$ is monotone in $n$: if $n \leq m$ then $T(n) \leq T(m)$. Now given $n$, find some $m \leq n^2$ which is of the form $2^{2^k}$, and then
$$ T(n) \leq T(m) = O(\log m \log\log m) = O(\log n \log\log n). $$


You would like to have the ability to extract the minimal array (in terms of length), then extract the next minimal, merge them, and insert them back to the data structure.

Since you want the best performance possible, you now would like to ask yourself how much each operation would cost?

If you use a stack you would have the option to $pop$, which is good if you assume your stack is given you with the arrays already sorted by length (will be $O(1)$). So, you will be able to $pop$ the first two arrays and then merge them. But now, what will you do with the merged array? You have no guarantee that the new array is indeed the shortest one. A simple queue won't do as well.

So, a better option would be to use a priority queue, implemented as a heap. You will have a heap where the values are the length of the arrays. To get the two shortest array you will use $extract-min$. You can use Fibonacci heaps which will give you $O(\log n)$ amortized for extraction. Next, after merging the arrays you can insert it back with $O(1)$ amortized time complexity.

*Note that the complexity times I wrote here are disregarding the length of the arrays themselves. I treated them as simple elements for simplicity, since the question focuses on the use of the data structure.


How do we generate a depth-first forest from the Depth First Search?

Algorithm DFS-Visit(u) finds a tree that consists of vertices that are in the same connected component as vertex u. Basically, when you run DFS-Visit(u), you visit every vertex in the same connected component as u and you change their color to black.

In algorithm DFS(V, E), in steps 5-7, you find a vertex u with color white (which means that it is not in any of the previous trees/visited connected components) and run DFS-Visit(u) in order to find the next tree.


Prove that there is no computable enumeration of all decidable languages

WLOG assume we are talking about languages over a binary alphabet $\{0,1\}$. Let $M'$ be an enumerating Turing Machine for $L$, i.e., every element of $L$ is eventually output by $M'$. Let $\langle M_j \rangle$ denote the $j$th TM output by $M'$. Define
$$L_D = \{ x \mid M_x(x) \text{ does not accept} \},$$
where $x$ is interpreted as a number in base 2. Note that $L_D$ is decidable: given $x$ you can decide if $x \in L_D$ by running $M'$ until it outputs $x$th TM $M_x$ and then running $M_x$ on $x$ and flipping the output. This is a decider since all TMs output by $M'$ halt on all inputs. Thus $L_D$ appears in the enumeration of R, say, as $L_k$ for some $k$.

It is left to show that $L \cap A_k = \emptyset$. Suppose that there exists a TM $M$ such that $\langle M \rangle \in L \cap A_k$. Then let $\ell$ be the smallest number such that $\langle M \rangle$ is output as the $\ell$th element by the enumerator $M'$, i.e. $M = M_\ell$. Therefore, we have $\ell \in L(M) \iff \ell \in L(M_\ell) \iff \ell \notin L_D \iff \ell \notin L_k \iff \ell \notin L(M)$, which is a contradition.


ANN with communication between nodes of same layer

Yes! That is definitely possible. You should know that not all network topologies are layered. You could also have a network which consists of loose neurons which are connected to one another in a more liquid way:

The reason we have 'layers' in networks is not because they add functionality, but because they make coding easier and more overseeable. When you have for example this network:

input: [neuron1, neuron2]
hiddenlayer: [neuron3, neuron4, neuron5]
output: [neuron6]

that is exactly the same as:

[neuron1, neuron2, neuron3, neuron4, neuron5, neuron6]

Because all neurons get activated sequentially.

So what kind of synapses do you want to create inside a layer? Recurrent or feedforward?


Knuth is trying to cover the columns using rows. The solution you describe consists of rows 4, 5, 1, in this order (counting from 1). Each row is represented by its 1-columns. For example, row 4 is 1001000, and its 1-columns are AD.


Classification of recursively enumerable sets

There are lots of these. Even with respect to Turing reducibility (which extends $m$-reducibility: if $A\not\ge_TB$ then $A\not\ge_mB$), the structure of c.e. sets is extremely rich.
That said, constructing an infinite non-recursive r.e. $A$ with $A<_mK$ is significantly easier than constructing one with $A<_T K$. The former was done by Post in 1944 who introduced the notions of creative and simple sets (each of which are necessarily non-recursive), proved that a simple set exists and that $K$ is creative, and proved that no creative set is $m$-reducibile to any simple set; the latter wasn't achieved until a decade later by Friedberg and Muchnik independently, and required a fundamentally new technique (the priority method).


You can do that, beta reduction can be applied at any point where an abstraction is immediately followed by application $((\lambda x. \cdots)t)$. In general, as you ovserved, there might be many redexes, i.e. many points where beta reduction can be applied.

However, note that sometimes we want to study what happens if we restrict ourselves to some reduction strategy. Essentially, a reduction strategy is a rule which chooses which redex to beta reduce when there are many. When doing that, there is a unique reduction sequence, a kind of unique execution run, for any term.

So, unless an exercise mandates the use of a specific reduction strategy, you are free to apply beta reduction at any point.

As a final remark, note that the choice of the redex can affect the termination of our reduction sequence. For instance, $(\lambda x.\ y)\Omega$ where $\Omega=(\lambda w.ww)(\lambda w.ww)$ can immediately reduce to $y$, or can loop indefinitely on reducing $\Omega$ to itself.

The Church-Rosser property (aka confluence, aka diamond property, mentioned above by xuq01) only ensures that, whenever we reduce a term $t$ with many beta reduction steps, possibly in two different ways leading to two terms $t_1,t_2$, there is a way to "reconcile" $t_1$ and $t_2$ and beta reduce those (in many steps) to a common form $t_f$.

This ensures that choosing the "wrong" beta redex does not compromise the reachability of the "intended" result (e.g. a normal form, if it exist). However, as seen in the example above, if we insist in selecting the "wrong" redex, it is possible that we get stuck into an infinite reduction sequence, when another one would lead to the intended result.


Let’s begin by talking about the intuition for universal hash families. Intuitively, a family of hash functions is universal if for any distinct objects x and y that you’d like to hash, if you select a random hash function from the hash family, the probability that you get a collision between those two elements is at most 1/m, where m is the number of buckets. In other words, universal hash families tend to spread elements out in a way where the probability of a pair colliding is the same as if the elements were distributed randomly.

Let’s see how the definition accomplishes this. Here’s the definition from your question:

  H is universal if ∀ x, y ∈ U where x ≠ y | { h in H : h(x) = h(y) } | = |H| / m.

For starters, I’m assuming that we’re talking about hash functions that map from some set U to the integers 1 through m or 0 through m-1. With that in mind, let’s unpack some of this notation.

If we replace the universal quantifier (∀) with the plain English “for all,” this definition says “H is universal if for every choice of two different items x and y to hash, some inequality is true.” So let’s look at that inequality. First, what is this bit?

  | { h in H : h(x) = h(y) } |

The vertical bars here represent the size of a set, and the set in question is this one:

  { h in H : h(x) = h(y) }

Read literally, this is the set of all hash functions h in the family H where h(x) = h(y). Keeping in mind that we’re talking about hash collisions here, we can think of h(x) = h(y) as saying that hash function h causes x and y to collide with one another (have the same hash code). With that in mind, the complex expression

  | { h in H : h(x) = h(y) } |

means “the number of hash functions in H where x and y collide.”
Combining that with our earlier bit, we can rewrite the entire definition as

  H is universal if for any two distinct elements x and y that we want to hash, the number of hash functions in H where x and y collide is at most |H| / m.

So what’s |H| / m? That’s the total number of hash functions (|H|) divided by the number of possible outputs for any one single hash function (m). It might help to divide the entire expression through by |H|, which would then give this final definition:

  H is universal if for any two distinct elements x and y that we want to hash, the probability of picking a hash function h where x and y collide (that is, the total number of hash functions where x and y collide divided by the total number of hash functions) is at most 1/m.

Hope this helps!


Are two strings equal if all deciders for a language take the same amount of time for both?

Your "distance" $d(x,y)$ is never zero for distinct, non-trivial $x$ and $y$.

Let $M$ be a decider for $L$ and $x,y \in \Sigma^*$ with $\varepsilon \neq x \neq y$. Let furthermore $T = 1 + \max \{ t_M(x), t_M(y) \}$. Now we construct a machine $M'$ like this:

M'(z) {
  if x == z or xy is a prefix of z
    wait for T steps
  return M(z)
}

We observe that $t_{M'}(x) - t_{M'}(y) \geq T > 0$ since $x \neq y$. Condition (**) is satisfied by increasing the running-time on all inputs that begin with $xy$ as well; hence, $M' \in X^L_*$ and thus $d(x,y) > 0$.

This constructions works for all pairs of distinct $x$ and $y$, proving the claim. Your claim follows since trivially $d(x,x) = 0$ for all $x$.

I think the problem is that $d(x,y)$ is not well-defined. With a similar construction as above, we can increase the difference between $t_M(x)$ and $t_M(y)$ by an additional $i$ for all $i \in \mathbb{N}$. Since the sum of $t_M(xy)$ and $t_M(yx)$ grows with $i$ as well (unless either is $\varepsilon$), $d(x,y)$ approaches a constant for $i \to \infty$ and the maxium does not exist.


Understanding algorithm for maximum sum of non-consecutive elements

Let me try to explain how to solve the problem. You are looking for a set of non-consecutive array elements with a maximum sum.

Let's say you have an array of 100 elements. Which ones of elements #99 and #100 can be in the optimal solution? They cannot both be present, because they would be consecutive. They cannot both be absent, because then adding #100 would create a larger sum without violating the rules. So one of #99 and #100 is present, and the other is not.

If #99 is present, then the solution is also the optimal solution for 99 elements. If #100 is present, then the items without #100 would be the optimal solution for 98 elements. So there are two possible ways to get an optimal solution for 100 elements: You take the optimal solution for 98 elements and add #100, or you take the optimal solution for 99 elements.

So f (A, n) = max (f (A, n-1), f (A, n-2) + A[n]) if n ≥ 2; f (A, 1) = A[1] and f (A, 0) = 0.

Note that implementing this using recursion is horribly inefficient. It's best to calculate f (A, 1), f (A, 2), f (A, 3) in sequence in linear time.


Can we call deterministic equivalent of all NFA to be finite

Finite automata is defined as a simple machine having small memory.

In fact, they are not defined in this way. You can look up the actual definition on Wikipedia. Even as an informal definition, the adjective small is inappropriate here — in fact, DFAs and NFAs have constant memory.

You are using the letter $n$ to represent the number of states in a finite automaton. The letter $n$ is usually reserved for the input length. The number of states in a finite automaton doesn't depend on the length of the input. On the contrary, the number of states is fixed ahead of time, and the finite automaton then uses exactly the same number of states for any input, of any length. Perhaps it will be less confusing if you use a different symbol, say $m$.

  ... the actual memory will be large ...

In theoretical computer science, there are no arbitrary constants thrown around. Today, $2^{50}$ bytes of memory can be considered large, but next year it might be $2^{60}$ bytes of memory. The same theory should account for both. In theoretical computer science, the formal meaning of large (or, more accurately, super-constant), is "tending to infinity with $n$", where $n$ is the input length. Finite automata use a fixed amount of memory which is independent of the input length, and so they never use a large amount of memory, as far as theorists are concerned.

In practice, some automata are too big to actually implement. But this is a practical restriction rather than a restriction on the actual definition.


If the height is $0$ it is true.
Assume that all binary trees for which inorder is sorted and height smaller than $h$ are BST.
Consider a tree with root $x$, height $h$ and its inorder is sorted. In particular its left and right subtrees' inorder are sorted and have height smaller than $h$. Then, by the assumption, they are BST. Now, in the inorder of the given tree, the node $x$ is listed after all nodes of its left subtree. Since its inorder is sorted, then $x$ is not smaller than any node of its left subtree. Likewise, $x$ is not larger than any node of its right subtree. Therefore, the tree is a BST.
Hence, by induction on the height of the binary tree, all binary trees for which inorder is sorted are BST.


Knapsack-like problem oriented on contiguous selection

You can use dynamic programming.
Define $T^{0}(k_0,m_0,i)$- the optimal subset $S$, that uses $k_0$ elements from the set  $\{a_i,a_{i+1},\ldots,a_n\}$, includes $a_i$  uses less than (or equal to)  $m_0$ subgroups. We define similarly $T^{1}(k_0,m_0,i)$ but it does no includes the element $a_i$. We define $W(S)=\sum_{s\in S} Weight(s)$ for every subset $S$.

For every $k,m\geq 2$ there exists $j>i$ such that begins with the subgroup $[a_{i},a_{i+1},\ldots, a_{j-1}]$. Thus, if we denote $T_j=\{[a_{i},a_{i+1},\ldots, a_{j-1}]\}\bigcup T^1(k_0-(j-i),m_0-1,j)$ then $T^{0}(k_0,m_0,i)$ is the subset with maximum weight among the $T_j$'s, i.e.,

$$T^{0}(k_0,m_0,i)=\arg\max_{T_j| \min(n,k_0+i)\geq j>i} W(T_j)$$

In addition, if the first element of $T^{1}(k_0,m_0,i)$ is $a_j$, then  $T^{1}(k_0,m_0,i)$ equals to $T^{0}(k_0,m_0,j)$. Therefore,
 $$T^{1}(k_0,m_0,i)=\arg\max_{T=T^{0}(k_0,m_0,j)|n\geq j>i} W(T)$$

Note that the initial conditions are  $T^{0}(1,m_0,i)=\{[a_i] \}$, $T^{0}(k_0,1,i)=\{[a_i,a_{i+1},\ldots,a_{i+k_0-1} ]\}$.

The optimal solution for the problem is the subset with the largest weight among the subsets $\{ T^{0}(k,m,1), T^{1}(k,m,1)\}$

We can compute each entry of $T^{0}(k_0,m_0,i_0)$ and $T^{1}(k_0,m_0,i_0)$ in $O(n)$ time. Since there are $O(k\cdot m\cdot n)$ entries of $T^{1},T^{2}$ the time complexity is $O(k\cdot m\cdot n^2)$.


How does Tabu Search cure the problem of getting stuck in a local optimum? Does it increase the search-space?

First, the search method does not affect the size of the search space; it depends only on the problem and it simply contains all possible states. Tabu search (TS) does what local search methods often do: when you get stuck, you allow a non-improving move in the hopes of getting unstuck. TS, in particular, maintains a tabu list. When we do a non-improving move, the tabu list ensures we never move to a previously visited state.

  What is the need of maintaining a list (i.e. Tabu List)? Why not just remember the optimum solution found so far?

As explained, the need of maintaining a list is guiding the search in an "intelligent" way. If you just remembered one state (perhaps that is the best solution found so far), you would be getting out of a local optimum in a "blind way". That is, it is possible you would simply trace your steps back, and then walk into the same local optimum again!

  When the Tabu List is too large, the oldest candidate will be removed. What if this oldest candidate is the global optimum?

If the global optimum is not in tabu list, then it is possible you will find it later. In short, the tabu list (as the name implies) contains all states you for some reason do not want to backtrack to.


Let's look at the form of the allowed paths. As a regular expression, it looks like:

$$r^*\ |\ r(r|g)^*\ |\ rr^*g(r|g|b)^*$$

We can test the three cases separately and then choose the shortest path found among the three cases.

The first case is easy: just remove all the green and blue edges and then find the shortest path from $s$ to $t$ as normal. Of course, there may not be a path from $s$ to $t$ in this red-only subgraph; if this happens, we can say the distance for this case is $\infty$.

For the second case, start with the original graph and remove all the blue edges, leaving only red and green edges. Then add a new vertex $s^\prime$, which has a directed edge to each vertex $v$ exactly when there is a red edge from $s$ to $v$ in the original graph. Then check for the shortest path from $s^\prime$ to $t$ in this modified graph; this corresponds exactly to the shortest path from $s$ to $t$ in the original graph that has the form $r(r|g)^*$. Again, if no such path exists, we can return $\infty$ from this case.

See if you can figure out the third case now.

I have asked and answered a more general form of this question here.


Where does the assembler live inside a CPU? If, it indeed does?

A reasonable question when one is unfamiliar with how a computer operates. The answer does depend on what kind of computer one is discussing. Computers range from small systems, like a Raspberry Pi or BBC Micro Bit (or even smaller) up to a large multiprocessor supercomputer.

In a normal typical computer an assembler is just a normal program, like any other application (or App) and it lives in the system in the same places as other Apps. There is nothing special about an assembler. An assembler is just like a compiler. It is a program that translates a sequence of statements described in one language (or notation) to an equivalent sequence in another language (or notation). A Java compiler would convert Java program statements into the equivalent sequence in (Java) Machine Code. An assembler for an ARM processor would convert the assembler statements into ARM machine code.

In a typical computer these programs would reside on the disc.

In something like a smartphone these programs would reside on some other form of persistent storage such as the built-in flash memory or a micro-SD card.

Not all computers need to have the assembler run on them. Very few smartphones would have an assembler App installed (but they could - my phone does have assemblers and compilers installed on its SD card!). For small devices the compilers and assemblers reside on and are run on a large computer and the machine code is generated there. The resulting file of machine code is then downloaded or installed on the computer.

You can thus have machine code without having any assembler on the same computer. The assembly was done somewhere else.

The answer is thus, the assembler could be anywhere!


Pumping Lemma for Regular Language seems to Fail

The pumping lemma says that there exists a decomposition of $w$ to $xyz$ such that $y$ can be pumped.

It doesn't say that for all decompositions of $w$ to $xyz$, $y$ can be pumped.

In your example, a possible decomposition is:

$x=a$

$y=bb$

$z=cd$


How to compute number of possible paths in directed Traveling Salesman problem?

The way you have written your question makes it very difficult to understand, but let me try to answer one of your points as simply as I can.

Using a "super computer" (however you might define that) will not help us to make significant progress on the travelling salesman problem. The reason is that the time taken to solve a travelling salesman problem increases exponentially with the number of cities.

So suppose we can solve problems with up to 50 cities in a reasonable time on an "ordinary" computer (I have made this number up as an illustration). But let's also suppose that the running time of our most efficient algorithm is $O(2^n)$ - in other words, every time we add a city the time needed to find a solution doubles.

If we had a super computer that was a thousand times faster than an ordinary computer then it could solve problems with $60$ cities in the same time as an ordinary computer took for $50$ cities. This is because adding $10$ cities increases the problem difficulty by a factor of $2^{10} \approx 1000$.

So the super computer gives us a small improvement. But to solve  problems with $100$ cities in a reasonable time we would need a computer that was a million million ($10^{12}$) times faster again.


The min cut capacity in a network based on a bipartite graph (Hall's Theorem)

The flow network $G'$ is constructed from the original bipartite graph $G=(L,R,E)$ by adding two new nodes $s,t$, connecting $s$ to all nodes in $L$, connecting all nodes in $R$ to $t$, and orienting all edges in $E$ from $L$ to $R$. And $s$-$t$ cut in $G'$ has the form $(S,\overline{S})$ where $s \in S$, $t \in \overline{S}$. The edges crossing the cut are:

Edges from $s$ to $\overline{S}$, that is, from $s$ to $\overline{S} \cap L$. There are $|L_2|$ of these.
Edges from $S$ to $t$, that is, from $S \cap R$ to $t$. There are $|R_1|$ of these.
Edges from $S \setminus \{s\}$ to $\overline{S} \setminus \{t\}$, that is, from $S \cap L$ to $\overline{S} \cap R$. There are $\mathrm{edges}(L_1,R_2)$ of these.

It is crucial that in $G'$ the edges are oriented, and that when counting edges crossing the cut $(S,\overline{S})$, we only count edges going from $S$ to $\overline{S}$.


Need help understanding textbook solution

Try to think of it that way. A code $C$, is just a subspace. A generator matrix is simply one basis of that subspace (i.e., each row is a basis element).

So in order to create the subspace $C_1+C_2$, you can take a basis of $C_1$ (for instance, the rows of its generator matrix), and add to it a basis of $C_2$. The new set is not a basis anymore, but if you eliminate dependencies it will be, and this new basis can be seen as the generator matrix of the new subspace (why?).

Same goes with $C_1 \cap C_2$. This subspace contains only elements which are both in $C_1$ and in $C_2$. Stated via  parity matrix, it contains only vectors that are in the kernel of $H_1$ and in the kernel of $H_2$. What happens if you build a matrix $H$ that contains both the rows of $H_1$ and of $H_2$? Which vectors will be in the kernel now?


There are supposedly generations of languages. According to Wikipedia:

First generation: Machine language.

Second generation: Low-level programming languages such as assembly language.

Third generation: Structured high-level programming languages such as C, COBOL and FORTRAN.

Fourth generation: Domain-specific high-level programming languages such as SQL (for database access) and TeX (for text formatting)

The fifth generation was supposed to be developed by Japan's fifth generation project in the 1980s but didn't really go anywhere. Some people consider constraint-based languages to be fifth generation (Wikipedia).

There is also a supposed hierarchy of language power, expressed by Paul Graham as the "Blub Paradox" in his essay Beating the Averages. In this controversial approach, languages such as Basic and Cobol are low in the hierarchy, Python and Perl would be in the middle, and Lisp would be at the top.


The brief survey contained in this paper might be of interest:

J. Swan, Z. A. Kocsis, and A. Lisitsa. 2014. The 'representative' metaheuristic design pattern. In Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO Comp '14). ACM, New York, NY, USA, 1435-1436. DOI=http://dx.doi.org/10.1145/2598394.2609842.

It discusses the existence of canonical forms for various forms of representation (groups, rings, boolean functions etc) and in particular normal forms for the lambda calculus using $\beta$-reduction as a rewrite rule.


You already explained what to do when $k = 2$. Let's see what to do when $k = 3$. Let $P_i$ be the polynomial corresponding to $iS$ (for example, the solution for $k = 2$ is $(P_1^2 - P_2)/2$).

We can construct the following table:
$$
\begin{array}{c|ccc}
& aaa & aab & abc \\\hline
P_1^3 & 1 & 1 & 1 \\
3P_2 P_1 & 3 & 1 & 0\\
P_3 & 1 & 0 & 0
\end{array}
$$
So the solution for $k = 3$ is $(P_1^3 - 3P_2P_1 + 2P_3)/6$.

More generally, the solution will involve terms corresponding to all partitions of $k$. The coefficients presumably appear in some change-of-basis formula for symmetric polynomials, and you can find formulas by browsing monographs on the subject.


In the worst case, the minimum cut itself doesn't convey much information about the maximum flow. Consider a graph $G=(V,E)$ in which the minimum $s,t$-cut has value $w$. If I extend $G$ by adding a new vertex $s'$ and an edge $(s',s)$ with weight $w$, a minimum $s',t$-cut in the new graph consists of just the edge $(s', s)$ but that doesn't give any information about how to get $w$ units of flow from $s$ to $t$.

Effectively, the minimum cut tells you the value of the flow, but not how to achieve that flow. This means that knowing the minimum cut can speed up finding the flow by at most a logarithmic factor, since we could do binary search to find the value of the cut.


FInding the combination with the least number of elements from and array of integers, given an integer sum

Let $f(s, i)$ be the minimum number of elements (only the first $i$ elements of the array are considered) required to sum up to $s$, then we have
$$f(s,i)=\min_{0\le j\le s/A[i]}\left\{j+f(s-jA[i], i-1)\right\}.$$

You can use this formula to compute $f(s,i)$ for all $s$ and $i$. With knowing $f$, you can figure out the optimal combination. This is left as an exercise for you.


Context-free grammar for ${a^n b^n a^n}$

The languages of all palindromes  is context-free.

That does not implies that any language that contains only palindromes is context-free. For example, many language over the unary alphabet $\{a\}$ are not context-free. In fact, they can even be non-context-sensitive or undecidable. Note that any word over a unary alphabet is a palindrome.

In particular, the language of all words like $a^nb^na^n$ is not context-free. The rough intuition to understand why it is not context-free is that a PDA cannot remember two unbounded independent relations. You can either use the pumping lemma to prove that fact.

Exercise. Give an example of a unary language that is not context-free.


Fitting a polynomial to a set of points or to a skeleton

You can try fitting a multi-dimensional polynomial regression. It seems that for your data, a two dimensional regression model should be fine:
$$ (a)x^2 + (b)x + (c)y^2 + (d)y + (e)xy + (f) $$

In python for example, you can fit a proper model using:

import numpy as np
from sklearn.preprocessing import PolynomialFeatures

X = np.array([ [x0,y0], [x1,y1], ...  ])
poly = PolynomialFeatures(2)
poly.fit_transform(X)
poly = PolynomialFeatures(interaction_only=True)
poly.fit_transform(X)


Is it possible to add "memory" to a neural network?

Yes it is possible.
Recurrent neural networks address this issue. They are networks with loops in them, allowing information to persist.These loops make recurrent neural networks seem kind of mysterious. However, if you think a bit more, it turns out that they aren’t all that different than a normal neural network. A recurrent neural network can be thought of as multiple copies of the same network, each passing a message to a successor.

Visit
http://colah.github.io/posts/2015-08-Understanding-LSTMs/
: This blog explains Recurrent Neural Network(RNN) and LSTM from scratch and also discuss few examples where LSTM is preferred over RNN.


Adleman's theorem states that you can amplify the success probability of $M$ so that there will be a single choice for the random string $r$ that works for all $x$:
$$ \exists r \forall x : x \in L(M) \Leftrightarrow M(x,r) = 1. $$
(Here $x$ goes over all inputs of length $n$, and $r$ goes over all possible random strings that $M$ requires for inputs of length $n$.)

Unfortunately, it's not clear how to find $r$, and even worse, if I give you $r$, it's not clear how to verify that it satisfies the property stated above. This is why we have to supply it as advice.

The Sipser–Gács theorem similarly states a different property from what you list. It states that if $M$ is a BPP machine then
$$
\forall x \bigl(x \in L(M) \Longleftrightarrow \exists t_1,\ldots,t_{|r|} \forall r : M(x,r \oplus t_1) = 1 \lor \cdots \lor M(x,r \oplus t_{|r|}) = 1 \bigr).
$$
Here the strings $t_i$ could depend on the input $x$. This is why you get $\Sigma_2^P$ or $\Pi_2^P$ rather than $\mathsf{NP}/\mathsf{poly}$ or $\mathsf{coNP}/\mathsf{poly}$.

Summarizing, you have to be careful with quantifiers when stating a theorem. Changing the order of the quantifiers could drastically change the meaning.


Will the Ford-Fulkerson algorithm always find the max flow if we start from a valid flow?

Yes. If the flow is not maximum, then there is an augmenting path. If there's an augmenting path, Ford-Fulkerson will find it (and continue to find them until the flow is maximum). Starting from a different initial flow does not change this.


Data structure and algorithms for a medical diagnosis software

Machine learning algorithms and techniques are very successful and best practice in this area (clustering and classification techniques could be uses). For example in Machine Learning Techniques for AD/MCI Diagnosis and Prognosis or Medical decision support systems based on machine learning, thesis written by Chih-Lin Chi.

You can use simple records in database as the data model.


Big-O of iterating through nested structure

A better bound on the complexity is $O(k)$, where $k$ is the total number of files.
A similar situation is encountered in algorithms for sparse matrices. Sparse matrices are stored as a list of all non-zero entries. The running time is often analyzed in term of the number of non-zero entries rather than the dimensions of the matrix. The reason is that matrices encountered in practice are often sparse (or can be sparsified), and we are interested in algorithms taking advantage of this.


Why does computer have branch and jump instructions

Theoretically speaking you do not need any branch and jump instructions. This is so because you can encode them into artihmetic. For instance, instead of writing

if p:
   x = a
else:
   x = b

you can write (assuming that $0$ stands for "false" and $1$ for "true"):

x = p * a + (1 - p) * b

Gödel was the first to have realized that when he proved his incompleteness theorem, namely that arithmetic sufficies for all of programming, theoretically speaking. So in this sense you are correct.

Supplemental: we do need some sort of iteration or recursion, as was noted in the comments. By "arithmetic" here I mean general recursive functions which have recursion built in. There is a form of "conditional" in recursion, namely the distinction between zero and a successor.

However, it is impractical to insist that arithmetic is somehow the most important thing. There are many different ways to do computation. For instance, we do not even need any arithmetic or recursion, we could use just pure $\lambda$-calculus, which is a pure theory of functions, without any numbers, booleans, or any other form of data (they can all be built up). Which paticular form of computation should be used actually depends on many factors: What does the hardware support? What makes programming most maintainable? How do we make programs efficient? And so on. The actual programming languages and CPUs that we know today are the result of many years of experience. It's turned out that it's better to have conditional branching than not.


You are asking several questions. Let me answer them one by one, though not in the same order.

Even though context free grammars allow the expression regular languages, do the methods used to check if a grammar is regular allow the expression of all regular languages? You are misunderstanding the article. One does not check that a grammar is regular. Rather, we define a grammar as regular if it satisfies the constraints described in the article. Regular grammars indeed generate all (and only) regular languages, and it's not too hard to show this by interpreting them as NFAs (exercise).

As an aside, the following is undecidable: given a context-free grammar, check whether the language it generates is regular.

Can a language exist that expresses up to the power of finite state machines but nothing higher? Yes, for example the language of regular expression, the language of DFAs, the language of NFAs, the language of regular grammars, and so on.

What calculi exist that cannot express problems above finite state machines, but a programming language could be built on top of. Kind of like the lambda calculus. This question is not really well defined, and it is very easy to cheat. A reasonably natural example is finite automata – if you add two stacks you get a model having the same power as a full-fledged Turing machine.


Topics from theoretical computer science suitable for a bachelor (undergrate) thesis?

As a bachelor student that is writing his thesis in that field I can guarantee you there are a lot of topics suitable for a bachelors degree.
Personally, I am working on graphs and some specific algorithmic problems over those.
I suggest you ask your professors if they have some topics for you.
At my university usually professors have a list of "problems" and we can either choose between one of those or propose our own topic.
Obviously because it is "just" a bachelor thesis you'll have to be specific and concentrate on some smaller problems e.g.

Formal verifiation of smaller programs in some specific language (like haskel)
Finding some polynomial algorithm to a specific problem that hasn't been researched too much. (Also, if you can't find anything new, explaining why the problem is "complex" can also be a good plan b)
Testing of specific cryptographic protocols under specific assumptions (allowing the attacker to have some specific information etc..)


Show that a decidable language is not decided by a decider in a given set

Suppose that $A$ is a recognizable set containing descriptions of always halting Turing machines. We want to show that there exists a decidable language $L$ such that for any $M$ deciding $L$ we have $\langle M\rangle\notin A$.

We can construct such $L$ via simple diagonalization. Assume $A$ is infinite (otherwise the problem is trivial). We will define a Turing machine $M$ such that $L(M)$ does not have a decider in $A$. Let $M_A$ be an enumerator of $A$. Given input $x$, $M$ executes $M_A$ untill it outputs the $|x|'th$ word in the enumeration $\langle M_{|x|}\rangle$. Now, execute $M_{|x|}$ on $x$ and flip its answer.

I leave it to you to show that $M$ always halts and that $L(M)$ disagrees with $L(M_i)$ on at least $2^i$ inputs, where $M_i$ is the i'th Turing machine in the enumeration of $A$.


How can I make k nearest neighbor queries fast on unit hypersphere?

As a rule of thumb, when the number of dimensions $n$ is less than about 10, fancy data structures (like k-d trees) work well; when the number of dimensions is greater than about 30, fancy data structures typically perform poorly and may be no better than a brute-force linear scan.  Wikipedia lists a similar rule of thumb: if $m \gg 2^n$ (where $m$ is the number of points in the data structure and $n$ is the number of dimensions), then k-d trees work well, otherwise they won't.  Exceptions exist, e.g., where your data is "structured" and non-random, but this is probably a good first guideline.

In your example, the number of dimensions is at least 100.  Therefore, I wouldn't expect any of the fancy data structures (k-d trees, M-trees, etc.) to be better than the simple linear scan.

Essentially, you are suffering from the curse of dimensionality.

You mention that your points are all on the surface of the hypersphere.  Unfortunately, this doesn't help much.  Heuristically, points on the surface of a $n$-dimensional hypersphere are a lot like points in a $n-1$-dimensional space.


assign points to non-overlapping rectangles

Most spatial indexes should be good, especially if your rectangles are axis aligned.

Spatial indexes typically have about $O(log{M})$ insertion time so you could build in index in $O(M * log{M})$.
Lookup time is similar, so finding the best/correct rectangle for every point should be around $O(N * log{M})$.

For rectangles, the simplest index is probably a quadtree (but may not scale as well with larger $M$). R-Trees such as the R*Tree (R-Star-Tree) are harder to implement but probably better than plain quadtrees. You could also look into STR-Trees (sort-tile-recurse-loaded R-Trees), they take longer to build but have faster lookup.

In case you are using C++, have a look at libSpatialIndex or the Boost R-Tree. If you are using Java, have a look at my TinSpIn library. In the case of Java I can also strongly recommend the PH-Tree (disclaimer: self advertisement).


prove: max (w(E), w(E)) is a 1/2 approximation to the value OPT

I don't know the definition of $1/2$-approximation algorithm, but it looks like what you will need to do is the following argument:
For an enumeration $\sigma:V\to\{1,2,...,n\}$ of the vertices, let, for each input graph $G=(V,E)$, the output of the algorithm be $A_\sigma(G)=\max(w(\overrightarrow{E}),w(\overleftarrow{E}))$.
We have that $OPT(G)\leq w(E)$.
On the other hand,
$$
\begin{align}
A_\sigma(G)&=\max(w(\overrightarrow{E}),w(\overleftarrow{E}))\\
&\geq\frac{w(\overrightarrow{E})+w(\overleftarrow{E})}{2}\\
&= \frac{w(E)}{2}
\end{align}$$
The last equation is because $\overrightarrow{E},\overleftarrow{E}$ is a partition of $E$.
Putting these two inequalities together we get $$OPT(G)\leq w(E)\leq 2A_\sigma(G)$$
Therefore $$\frac{A_\sigma(G)}{OPT(G)}\geq \frac{1}{2}$$


$L$ is not context free. You can use the Ogden's lemma to show it.

I'll use the Wikipedia notation linked above.

For every $p$ take the word $a^pb^pc^p$. For a the marking where only c are marked whatever the decomposition $uxyzv$ you take, $ux^iyz^iv$ will not be in $L$.
Four cases: $z\in c^*$ then it fails for $i=0$ or $z\notin c^*$ then it fails for $i>0$. And the symmetric cases for $x$.

Hope it helps.


How to find a possibility of match in Naive Bayes Classifier?

Let $A$ and $O$ be the events apple and orange (fruit). Let $R$ and $S$ be the events red and sphere.

By Bayes' law,
$$\Pr[A | R \wedge S] = \frac{ \Pr[R \wedge S | A] \Pr[A] }{ \Pr[R \wedge S] };$$
$$\Pr[O | R \wedge S] = \frac{ \Pr[R \wedge S | O] \Pr[O] }{ \Pr[R \wedge S] }.$$
By total probability adding to 1, we also have
$$\Pr[A | R \wedge S] + \Pr[O | R \wedge S] = 1$$
and therefore
$$\Pr[R \wedge S | A] \Pr[A] + \Pr[R \wedge S | O] \Pr[O] = \Pr[R \wedge S]$$
so
$$\Pr[A | R \wedge S] = \frac{\Pr[R \wedge S | A] \Pr[A] }{ \Pr[R \wedge S | A] \Pr[A] + \Pr[R \wedge S | O] \Pr[O]}.$$
By the Naive Bayes assumption of independence of features conditioned on class,
$$\Pr[R \wedge S | A] = \Pr[R | A] \Pr[S | A];$$
$$\Pr[R \wedge S | O] = \Pr[R | O] \Pr[S | O].$$
Putting it together, we get
$$\Pr[A | R \wedge S] = \frac{\Pr[R | A] \Pr[S | A] \Pr[A] }{ \Pr[R | A] \Pr[S | A] \Pr[A] + \Pr[R | O] \Pr[S | O] \Pr[O]}.$$

Now plug and chug. From the data $\Pr[R | A] = \frac{ \Pr[R \wedge A] }{ \Pr[A] } = \frac{2}{5}$, etc. Note: I am assuming the empirical distribution is the true distribution, an assumption your teacher probably expects you to make but not made in practice.


Generate Regular Grammar for a Language with Modular Condition

Hint: How many states do you need to keep track of $n_a(w)-n_b(w) \pmod{3}$, where $w$ is any prefix of the input? Consider how many possibilities this quantity has, and whether knowing the value for a word $w$ helps you calculate the value for the word $w\alpha$ ($\alpha$ being a single symbol).


Optimising an exhaustive search for a card game

I suspect this may be NP-hard in general but probably feasible to solve efficiently in practice for the parameter sizes you discussion.
I will suggest an approach based on comments from j_random_hacker.  One plausible approach is to express this as an integer linear programming problem.  Let $a_{im}$ be the amount of material $j$ you have after the $i$th step of applying sources, $b_{ir} = 1$ if you apply resource $r$ in the $i$th step or 0 otherwise, and then write constraints to express that each step obeys the rules you've followed.  See Express boolean logic operations in zero-one integer linear programming (ILP) for some general techniques for that.  For instance, you'll have a requirement that $a_{im}\ge 0$ for all $i,m$; that $\sum_i b_{ir} \le 1$, that $\sum_r b_{ir} = 1$; and so on.  If you have a resource that contains multiple alternative combinations, treat each as its own resource and then add a constraint that if you pick one of those combinations in any step you can't pick any of the others ($\sum_i \sum_{r \in R} b_{ir} \le 1$, where $R$ is the set of all combinations associated with a single resource).  If resource $r$ is "1 wood -> 1 steel", then we'd obtain a rule like
$$b_{ir}=1 \implies\\ (a_{i-1,\text{wood}} \ge 1 \land a_{i,\text{wood}} = a_{i-1,\text{wood}} - 1 \land a_{i,\text{steel}} = a_{i-1,\text{steel}}+1).$$
Then, convert that to an ILP constraint using the techniques at the link above.
Finally, you can apply an off-the-shelf ILP solver to search for a solution.
Note that the order in which you applies resources matters, because you can never go negative on any material, which complicates the ILP instance a little bit and requires you to have a separate copy of each variable per step.

If you prefer to adjust your exhaustive search, there may be ways.  One possibility is to use branch-and-bound to prune off some parts of the search space.  At any intermediate point in your search, you can get a simple bound on whether it's possible that a solution could exist from here by picking a single material, say wool, counting how many wool you already have, counting how much more wool you could possibly make if you used every remaining wool-producing resource to produce the maximum amount of wool (assuming optimistically all its preconditions can be met), and checking whether that would give you enough wool to meet the target.  If not, then there's no point continuing the search from here; you can prune the search.  Another way to get a simple bound is to look at the total number of materials, ignoring their type (e.g., total amount of mana, ignoring color); then using each resource that you haven't used so far that increases the number of mana (assuming optimistically that it can be used), and check how much mana total that would give you; if that's not enough for your target, then you can prune the search.
However, ILP solvers already use branch-and-bound, and they are probably doing something that generalizes  this and is more powerful.  So, rather than implementing branch-and-bound yourself with some limited set of bounds, I suspect it might be more powerful to use a full ILP solver.


Using approximations to optimization problems for threshold problems

First off, a technicality: optimization problems aren't NP-complete; only decision problems can be NP-complete (or in NP).  Thus, it's only the decision problem (what you call the "threshold problem") that is in NP, or NP-complete.

On to the substance of your question.  The answer is: You can't.  In general, the approximation algorithm typically doesn't let you solve the decision problem.  Think about it.  We have many problems for where the decision problem is NP-complete, but where we have a polytime approximation algorithm.  If the approximation algorithm let us quickly solve the decision problem (or the corresponding optimization problem), then we'd immediately have a polytime solution to a NP-complete (or NP-hard) problem, and thus a proof that P=NP.  When you start with some assumption and it leads to a conclusion that is too good to be true, that's a sign that the assumption probably wasn't valid.

No, your "obvious answer" doesn't work.  Decision problems aren't allowed to return "I don't know".  No, there isn't a better way (assuming the problem is NP-hard, and assuming $P\ne NP$).


Quickly identify changes in connectivity

You can work your way backwards. Suppose the edges being removed are $e_1,\ldots,e_\ell$, and the rest of the edges form a set $E$. Start by determining the connected components induced by $E$, using a disjoint sets data structure. Now add the edges $e_\ell,\ldots,e_1$ in that order, updating the disjoint sets data structure, until $u$ and $v$ belong to the same connected component. The last edge encountered in this way is the one you seek.


Definition of $\Theta$ for negative functions

This is just a technicality. In asymptotic analysis we are only "really" interested in positive functions like $n^3$ or $n\log n$. However, if we want to be very formal and general, we could take into account non-positive functions (and that could turn it to be useful, see below). The definition of $\Theta$ states that $f(n) = \Theta(g(n))$ if from some point on, $f(n)/g(n)$ is bounded from both sides by constants, and furthermore $g(n) \geq 0$. (That's what you get if you unroll the definition.) In particular, if $f(n) = \Theta(g(n))$, then from some point on, $g$ is non-negative.

Here is an alternative definition of big $\Theta$. Suppose $f,g \colon \mathbb{N} \rightarrow \mathbb{N}$ are positive functions, that is $f(n),g(n)>0$. Then $f(n) = \Theta(g(n))$ if there exist positive constants $c_1,c_2$ such that $c_1 \leq f(n)/g(n) \leq c_2$. I don't know why the more complicated definition is presented in introductory texts.

What are the advantages of the more complicated definition? It can handle functions which have some non-positive values (there has to be a finite number of them). For example, this definition accommodates the (true) statement $n-10 = \Theta(2n-30\log n)$. Although functions encountered in practice are usually positive, sometimes negative functions could be encountered: for example, say we're interested in some genuine complicated function $k$, and we estimate it from below by a function $t$, which is however negative for small $n$.


Find K-subset that includes the most W-subsets

I had the same problem a few days ago and I used the following heuristic to do it. According to my first impression it seems to work.

My specific use case was to determine a strategy in which sequence I should convert function implementations from one programming language into another so that we can execute as many test runs with as little effort as possible (in this case the set of functions is $S$ and the test runs are $\Sigma$ and our goal is to cover as many $\sigma \in \Sigma$ as possible with as few elements from $S$ as possible).

Example Data

So let's setup some example data. We have five sets $\sigma$ with different elements inside.

$$
\sigma_1 = \{s_1, s_3, s_4\} \\
\sigma_2 = \{s_1, s_5, s_6\} \\
\sigma_3 = \{s_1, s_3 \} \\
\sigma_4 = \{s_1, s_3, s_4, s_5, s_6\} \\
\sigma_5 = \{s_1, s_2, s_3, s_6\}
$$

My Current Approach

I give each $s_j$ a rating based on the total number of time it exists. Then I check how many elements each $\sigma$ contains. I will then calculate the division between these two numbers and select the $\sigma$ with the highest rating as first winner.

In my opinion this should give me the quick win sets first. I will get at least one set covered and I try to trade-off between trying to get the smallest set first, and trying to select the $s$ that are used the most (i.e. with which I could probably cover the most $\sigma$).

Let me explain this approach on the example above. If we count the number of occurrences for each $s$, we get:

$$
\text{Usages}(s_1) = 5 \\
\text{Usages}(s_2) = 1 \\
\text{Usages}(s_3) = 4 \\
\text{Usages}(s_4) = 2 \\
\text{Usages}(s_5) = 2 \\
\text{Usages}(s_6) = 3
$$

If we use these and the number of elements in each $\sigma$ we get the following ratings:

$$
\text{Rating}(\sigma_1) = \frac{\text{Usages}(s_1) + \text{Usages}(s_3) + \text{Usages}(s_4)}{3} = \frac{5 + 4 + 2}{3} = \frac{11}{3} = 3.67 \\
\text{Rating}(\sigma_2) = \frac{5 + 2 + 3}{3} = \frac{10}{3} = 3.33 \\
\text{Rating}(\sigma_3) = \frac{5 + 4}{2} = \frac{9}{2} = 4.5 \\
\text{Rating}(\sigma_4) = \frac{5 + 4 + 2 + 2 + 3}{5} = \frac{16}{5} = 3.2 \\
\text{Rating}(\sigma_5) = \frac{5 + 1 + 4 + 3}{4} = \frac{13}{4} = 3.25
$$

In this case, I would add the elements $\{s_1, s_3\}$ to my set $X_k$ first.

For the next iteration I would delete $\sigma_3$ from the candidates and repeat the process.

Related Problems

I think that is problem is closely related to the set cover problem. However, it is different and I did not find a way to convert my problem into a set coverage problem. It also was different to any other algorithm I found in the area of set cover problem (e.g. set packing, dominating set, maximum coverage problem). Maximum coverage problem seems to come very close, but it is again a bit different.


Finding a tree that approximates the distances and total weights

Your problem is solved in the following paper by Khuller, Raghavachari, and Young. They show that you can construct a tree in which distances from the root are stretched by at most $\alpha$ and the total weight of the tree is at most $1 + 2/(\alpha - 1)$ times the weight of the MST. So, with $\alpha=3$, you can get $2$ times the weight of the MST. The algorithm does a depth-first traversal of the MST, and  adds paths from the shortest path tree when necessary, roughly speaking maintaining a shortest path structure in the current graph, which consists of the MST edges and the edges added from the shortest path three. Check the paper for details.

As I mentioned in the comment, there are graphs in which the weight of the shortest path tree rooted at some vertex is greater than the MST weight by $\Omega(n)$. One example is a path of unit weight edges, and edges from the first vertex in the path to the $i$-th vertex of weight just slightly less than $i-1$.


Understanding PDA and Equivalence of PDA and CFG

Your question is, in essence,

  Why does the proof that every context-free grammar can be converted to an equivalent PDA proceed in a particular way rather than in another way?

It's hard to answer such a question unless it gets more specific. For example, you can ask why the resulting PDA have to invoke nondeterminism. The answer is that some context-free languages cannot be accepted by a DPDA. Indeed, while this particular proof uses PDAs acting in a certain way, another proof might use PDAs acting in a different way.

One alternative such proof uses the Chomsky–Schützenberger representation theorem. The theorem states that every context-free language can be realized as
$$ h(D \cap R), $$
where $D$ is a Dyck language (the language of all correctly nested strings of parentheses of some fixed number of sorts), $R$ is a regular language, and $h$ is a homomorphism. This theorem, which can be proved directly using context-free grammars (see, for example, Context-free languages and pushdown automata by Autebert, Berstel and Boasson, from the Handbook of Formal Languages), allows to convert a context-free grammar to a PDA which is more like the one for $0^n 1^n$, along the following lines:

Start with a PDA for $D$. This is a PDA that pushes whenever encountering a left parenthesis, and pops whenever encountering a right parenthesis (checking that the two parentheses, the one on the stack and the one being read, have the same type).
Construct a DFA/NFA for $R$, and use the product construction to construct a PDA for $D \cap R$.
Construct a PDA for $h(D \cap R)$ by replacing each transition on $\sigma$ to a transition on $h(\sigma)$.

If you apply this construction to $0^n1^n$ (which you can realize as $D \cap 0^*1^*$, where $D$ is the Dyck language with a single type of left parenthesis $0$ and the corresponding right parenthesis $1$) then you get a PDA which is remarkably similar to the one you describe.


How to design a turing machine for a context-free grammar? what are the steps?

You should first construct a PDA for your grammar. You can then use the tape in stead of the stack. When pushing something in the stack, write it on the tape of the TM from left to right. When poping the stack, read the tape then move the head left if necessary.
There is no other change (states and transitions can be the same).


If we allow a database, what complexity class it is?

You can say anything you want, if you define your terms and your notation and make it clear what you are saying.

In this case I would not expect someone to know what you mean by $M/f(n)$ or by $A \in M/f(n)$.  Something like $P/\text{poly}$ is well-understood, but $P$ is a complexity class, and $M$ is a specific machine.  Rather than risking confusion, just say what you mean -- it only takes a sentence to say that the problem can be decided by $M$ using advice of size $f(n)$.


Master theorem for $T(n) = 2T(n/2) + n^{2}\log n$

Yes and no. The form of the Master Theorem given on Wikipedia is a bit more restrictive than a fuller version of the theorem, essentially limiting itself to the cases where $f(n)$ is a polynomial.

In this case, where $f(n) \notin \Theta(n^{c})$ for any $c$ (though we do have $f(n) \in \Omega(n^{2})$ and $f(n) \in O(n^{2+\varepsilon})$ for any $\varepsilon > 0$), the condition given on Wikipedia is insufficient.

A more useful (but slightly mathematically harder to work with, sometimes) formulation can be found in Cormen et al.'s "Introduction to Algorithms", or in this convenient worksheet from MIT.

The third case in this version is now

  If
  $$
f(n) \in \Omega(n^{\log_{b}(a)+\varepsilon}) \text{ with } \varepsilon > 0
$$
  where $f(n)$ also has to satisfy a "regularity condition":
  $$
a f(\frac{n}{b}) \leq cf(n) \text{ for some } c>1 \text{ and } n \text{ large enough}
$$
  then
  $$
T(n) \in \Theta(f(n))
$$

For the recurrence $T(n) = 2T(\frac{n}{2})+n^{2}\log n$, we have $\log_{b}a = 1$, so we can pick any $\varepsilon \in (0,1]$ (say for the sake of argument we pick $\varepsilon = 1$) and we have $f(n) \in \Omega(n^{1+\varepsilon}) = \Omega(n^{2})$.

Thus we can conclude $T(n) \in \Theta(n^{2}\log n)$.

In this case we don't need to worry too much about the regularity condition as $n^{2}\log n$ is well behaved - the condition is there to stop tricky things like the ones mentioned in the Wikipedia article, such as $f(n)=n\cdot(2-\cos n)$.


proving existence of TM that accepts the next language

The language $L^*$ consists of all Turing machines $M$ which either eventually halt or repeat a configuration. For each machine $M$, by simulating the machine you can easily observe that one of these possibilities has happened.


You can construct a DPDA for your language as follows. When reading $a$s, the machine pushes $A$s onto the stack. When reading $b$s, the machine pops them, noting to itself if there are more $b$s than $a$s. When it reads the first $c$, it can use the top-of-stack to tell if the number of $a$ was equal to the number of $b$s; if so, it transfers control to a DFA for $(cc)^*$, and otherwise it transfers control to a DFA for $c^*$.


How to use Neural Network classification if data not same size?

You can padd your data.

  I can not delete or add more arbitaly data. It may make the result not correct.

Don't make assumptions about neural networks. They can map any function, and if you don't add more data (padding) then you can't even train your network in the first place.

If your data consists of merely 0's and 1's. You could either do the following:

pad all blanks with 0.5 ([0 1 0 1 0, 0.5, 0.5, 0.5, .0.5]), however the neural network will think that 0.5 is as far from 1 as it is from 0.
pad all blanks with 0.5 (this is what I recommend), if your data is binary (e.g. true/false), then all false must be set to 0 consistently. 0 then has the double meaning: false or not present.

There is no other option besides adding 'blank' data, if you don't add data, the network will still see this as a 0.

But you should try before you ask. "It may make the result not correct." is not a good argument to not do something. Your data doesn't seem that big, so you can easily test through trial and error.


Prove that the set of all total functions is countable

ad a) showing that $g$ is injective should suffice.

ad b) because it's easier. or put differently: how would you define an injective mapping $h: S \rightarrow \mathbb{N}$ ? it is feasible (eg. $f \rightarrow 2^{f(0)}\,*\,3^{f(1)}$) but complicates matters unnecessarily ( to prove injectivity you'd have to exploit additional information eg. the unique prime factor decomposition of natural numbers ).


Minimal positive difference of a mulitset of real numbers

Original formulation

(Originally, the OP was interested in the minimum absolute difference rather than the minimum non-zero absolute difference.)

You are asking two different questions. For the first, consider the restricted version in which all numbers are rational, and the decision variant in which the problem is to decide whether your expression is at most some $\delta$. This problem is NP-complete by reduction from PARTITION. (Wlog all numbers are integers, and you can ask whether the difference is at most $1/2$.)

Your other question concerns the decision variant in which the problem is to decide whether your expression is at least some $\delta$. This problem is coNP-complete, and so unless NP=coNP, no nice lower bounds exist (that is, there are no polysize witnesses that the minimal difference is at least $\delta$ which can verified in polytime).

Revision 1

(The question has been changed, and now we are looking for the minimum non-zero absolute difference.)

The problem is NP-complete by reduction from PARTITION. This time assume all numbers are integers, and add to them the additional number $1/3$. Deciding whether the minimal non-zero absolute difference is at most $1/3$ is tantamount to solving PARTITION, and so is NP-complete.


Hash table: When is it suitable to use modulo power of 2?

The exact size of the backing array is not that important only that it can hold enough buckets.

The reason why power of 2 is often used is because this can be implemented as a bitmask instead of a integer divide. Integer divides are pretty slow compared to other operation so they are often avoided by people trying to optimize data structures.


Does every 3CNF propositional formula has an equivalent 2CNF propositional formula?

The single clause 3CNF:

$\varphi = a\lor b\lor c$

does not have an equivalent 2CNF. Suppose $\psi=\bigwedge\limits_{i=1}^m \psi_i$ is an equivalent 2CNF. Let $\psi_i$ be one of its clauses, and assume it involves the variables $a,b$. An assignment which sets $c=1$, but does not satisfy $\psi_i$, satisfies $\varphi$ but not $\psi$, hence they are not equivalent.


The original division and allocation of IP addresses used a system called classful IP addressing. This is the division to which you are referring, in which a class A network would receive all addresses X.0.0.0-X.255.255.255 and have over 16.5 million host addresses. As designated below, the network bits in classful addressing are divided in 8-bit groupings.

The modern internet utilizes an alternative subnetting system called classless inter-domain routing (CIDR) to more efficiently allocate and distribute IPv4 addresses. This technique is based on variable length subnet masking (VLSM) which allows one to set arbitrary-length prefixes and accordingly allow address space to be allocated on bit lengths other than the previous 8 bit boundaries. This allows one to specify the most significant (i.e. network) bits with CIDR notation by notating the prefix by the number of bits designating the network, yielding the host bits by omission. We'll use your example for specific demonstration.

Utilizing ARIN to search the address number, we can see that the IP block in question is not, in fact 23.0.0.0 - 23.255.255.255, but 23.96.0.0 - 23.103.255.255 with a CIDR notation of 23.96.0.0/13. "/13" indicates that the first 13 bits of the IP address are used to specify the network address space and accordingly the remaining 19 bits specify the host space.

We'll convert the Dotted Decimal Notation (DDN) to binary to show how the math works. Keep in mind, binary is base-2, meaning that each bit is an exponentially higher value of 2:

27  26  25  24  23  22  21  20

-or-

128  64  32  16  8  4  2  1

Each octet has 8 bits, with 1 signifying that bit in use, 0 signifying it not in use. Any value 00000000 - 11111111 inclusive is valid with 00000000 representing 0 and 11111111 representing 255.

00010111.01100000.00000000.00000000           (23.96.0.0 in DDN)
00000000.00000111.11111111.11111111 +      (19 least significant or host bits)
00010111.01100111.11111111.11111111 =      (23.103.255.255 in DDN)


Why do depth-limited search algorithm and BFS have different memory complexity?

Let be b the branching factor of the tree.
Let be d the depth of the shallowest solution.
Let be l the limit given to depth-limited search algorithm

Breadth-first search (BFS)
In the worst case, suppose that our solution is at depth d, and we expand all nodes but the last node at level d, then the total number of generated nodes is $ O(b^{d}) $.
As all these nodes must retain in memory while we expand our search, then the space complexity is $O(b^{d})$.
Depth-limited search algorithm
Unlike BFS, Depth-limited search algorithm has a very modest memory requirements, it needs to store only the path from the root to the leaf node, beside the siblings of each node on the path. Depth-limited search algorithm removes a node from memory once all of its descendants have been expanded.
DFS requires storage of only $O(bl)$ nodes thus space complexity is $O(bl)$.


How to calcualte the Big-O complexity of the following algorithm?

for(i=1;i<=n;i++)
{
    for(j=1 ; j <= i*i ; j++)
    {
        for(k=1 ; k<= n/2 ; k++)
        {
        x = y + z;
        }
     }
}

The triple-nested loop is equivalent to the summation
$$\sum_{i=1}^{n}\sum_{j=1}^{i^2} \sum_{k=1}^{n/2} 1$$
$$=\frac{n}{2}(\sum_{i=1}^{n}\sum_{j=1}^{i^2}1)$$
$$=\frac{n}{2}(\sum_{i=1}^{n}i^2)$$
$$=\frac{n}{2} \cdot (\frac{1}{6}n(n+1)(2n+1))$$
$$=O(n^4)$$

In terms of actual code efficiency, since x=y+z is invariant in the loop, any good optimizing compiler will extract the statement out of the loop (in compiler-speak, hoist the statement to loop preheader), hence making the compiled code run in $O(1)$.


The regular expression is supposed to match (exactly) all of the words that the automaton accepts. If you pretend that some of the transitions of the automaton don't exist, you're effectively converting a different automaton, and that automaton probably accepts different strings from the ones you're supposed to accept.

In this specific case, pretending that there's no $\varepsilon$-transition from the first state to the third one means that the automaton no longer accepts the word $c$.


Floyd Warshall's All pair shortest path problem does not evaluate all possible paths

Yes, the path $(4,2,1,2,5)$ is not evaluated.
However this is not a problem.

Since we assume that the graph doesn't contain any negative cycles (this is a requirement for FW), there exists an optimal path for each pair of nodes that doesn't contain any cycles.
Therefore the algorithm only needs to guarantee, that cycle-less path gets evaluated.

By induction you can show that this is always the case.
Let $k$ be the variable in the most outer loop.
Induction hypothesis: After the $k$th iteration the table contains all the shortest paths between each pair that only uses nodes $\le k$ on the path (without start and end node).

At the beginning this is trivially true.
And also the induction step, going from $k$ to $k+1$, is pretty easy to show:
A minimal path using only nodes $\le k + 1$ from $u$ to $v$ either contains only nodes $\le k$, or it contains a minimal path from $u$ to $k+1$ combined with the minimal path from $k+1$ to $v$. (Here we use the fact that the paths contain no cycles. If a path contains cycles, this statement ca be wrong.)
And exactly this case is handled in the algorithms.

Therefore at the end the table contains all minimal paths.


Is it possible to use machine learning to interpret a programming language and guess it's output

I doubt it.  That requires learning a pretty complex function, which seems beyond the reach of current machine learning techniques.

But there's probably no reason to use machine learning for this, as we already know how to program an interpreter, and that will be more effective than using machine learning.


Reduction from TSP to ATSP does not imply constant factor approximation algorithm

I think the reduction they showed is incorrect. Where it falls is when you connect a node to its "ghost" with 0 cost and add a positive $w$ to all other edges. We will take a look why such a behavior can change the optimal path.
Indeed, take a look at a graph with nodes $v_0,\dots,v_{10}$ where we want to find the shortest path between $v_0$ and $v_{10}$.
The graph's edges will connect $v_i$ to $v_{i+1}$ with weight $1$, and will additionally connect $v_0$ to $v_{10}$ with weight $15$.
Clearly, the path between $v_0$ to $v_1$ and so on until $v_{10}$ has the lowest cost, of $10$.
But now assume we added to all edges a weight $w=1$. Then, this path's value will double to $20$, and the edge between $v_1$ and $v_{10}$ will have weight $16$.
Obviously, the shortest path now is the direct path $v_0,v_{10}$ with cost $16$, hence the optimal path changed.
Important note: Its possible to find a small enough $w$ that will not change the optimal path, but I believe finding one is NP-hard.


Computing epsilon-closure. What does $E(n) \leftarrow \{n\};$ and $E(p)$ mean?

For each state $n \in N$, we maintain a set of states $E(n)$. Eventually, $E(n)$ would contain all states reachable from $n$ via $\epsilon$-transitions.

You can think of $E$ as an array of sets. The notation $E(n)$ just means the value of $E$ at position $n$. So $E(p)$ is just the value of $E$ at position $p$.


How can I produce a summation function from this set of production rules for a grammar?

OK, so the question now has a set of recurrence relations.  To solve these, you can plug them in to each other until you get a single recurrence relation.  First, substitute $c(n)=b(n-4)$ to get rid of all of the $c$'s:
$$a(n) = 2 b(n-4) + 3 b(n-8)$$
$$b(n) = a(n-2) + b(n-8).$$

Now substitute in to get rid of the $a$'s:

$$b(n) = 2 b(n-6) + 3 b(n-10) + b(n-8).$$

So, you've gotten down to a single recurrence relation for the $b$'s.  Solve this using standard methods; see Solving or approximating recurrence relations for sequences of numbers for details.  Then, once you have a solution for the $b$'s, you can reverse the substitutions and obtain a solution for the $a$'s, $c$'s, and finally $s$'s.

If you want to find an exact equation for the $b$'s (rather than an asymptotic estimate), the method of generating functions will probably be useful.  You'll have to find the roots of a 10th-degree polynomial ($x^{10} - 2 x^4 - x^2 - 3$, I think), and the solution will likely be an expression of the form $c_1 r_1^n + \dots + c_{10} r_{10}^n$ where $r_1,\dots,r_{10}$ are the roots and $c_1,\dots,c_{10}$ are the appropriate constants.  This might get a bit messy, but it should be doable.

Or: You can ask Wolfram Alpha to solve the recurrence relation for you.  Sometimes it is able.  Unfortunately, for this one it seems to have failed: output.


Decide whether a DFA accepts the empty language

Re-read your textbook chapter on DFAs and NFAs -- you'll find everything you need to know there.

See also the following questions, which both have answers to your question embedded in their answers (make sure to read carefully):

Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?
Undecidable among these for turing machine

Next time, tell us what you have tried, to solve the exercise on your own.


Algorithm: Shortest path (walk) with keys and doors

This other question about mazes is closely related. It deals with the simpler problem of having to collect each of the items before leaving the maze. One can make the analogy that there is a single door at the end of the maze, but it has a very complicated lock and you must collect all the keys to get through it.

The complexity depends on the structure of the maze. In particular, my answer to the other question proves that, if the maze is a general graph, the collect-all-the-items version of the problem is NP-complete and, in fact, the same holds for planar graphs.  This means that your problem is also NP-complete on general (or planar) graphs.  Here's a sketch of the reduction.  You simulate the door with the complicated lock by replacing the exit to the maze with a very long passage that ends with the $k$ doors one after another. You make the passage long enough that the optimal solution is definitely to collect all the keys first and then walk down that passage and unlock the doors, because walking back and forth between keys and doors would simply be too long. Now the hardness of the collect-all-the-items problem implies that your problem is hard, too.

If your maze is a tree, the problem might be easier – the collect-all-the-items version has a polynomial-time algorithm in that case.  And, in any case, the more general problem being NP-complete doesn't mean there aren't more efficient algorithms than brute force: but it does mean you shouldn't expect a polynomial-time algorithm.


The sparsest cut problem, in which one attempts to minimize the ratio between the number of edges cut to the size of the smaller size of the bipartition, is NP-complete. The "last word" on this problem theoretically speaking is the $O(\sqrt{\log n})$ algorithm by Arora, Rao and Vazirani (affectionately knows as ARV), which has found many uses in the area of approximation algorithms.

You might want to start with the simpler algorithm of Leighton and Rao, which gives an $O(\log n)$ approximation and has a relation to flows. See for example these lecture notes, or many others.


Smallest convex set containing given point

Here is an idea to find a "smallish" simplex containing your given point $x$. It does not find a smallest simplex (except by luck).

Construct the convex hull $H$ of your set of $M$ points.
For each $p$ of your set $M$, shoot a ray from $p$
through $x$ until it hits a facet $F$ of $H$. Then $F \cup p$ is a simplex containing $x$. Repeat for all $p \in M$ and retain the smallest volume simplex.

It is easy to create examples where this is terrible, as it is biased toward a simplex
containing a facet of the hull. One can imagine various heuristics to improve, for
example, discarding from $M$ the vertices of $H$ and repeating.


How to write grammar production rules to describe recursive structures?

Yes, you can use context-free grammars to describe data structures, but only if the data structure is linear (e.g., a linked list of integers).  Context-free grammars are not well-suited for trees or graphs (for those, you need something more powerful).

There's nothing wrong with a production like $A \to AA$; that's a valid rule that can appear in a context-free grammar.


Finding a regular expression for all non-empty binary strings that contain both 0s and 1s but no consecutive 1s

I would suggest you to draw a small finite state automaton. Things to keep track in the states are "seen 0", "seen 1" and "last letter 1" (to avoid consecutive 1's).

There is an "official" algorithm to go from automaton to expression, but with small examples you usually can read the expression directly.


Any problem in NP is in EXPTIME because you can either use exponential time to try all possible certificates or to enumerate all possible computation paths of a nondeterministic machine.

More formally, there are two main definitions of NP.  One is that a language $L$ is in NP iff there is a relation $R$ such that

there is a polynomial $p$ such that, for all $(x,y)\in R$, $|y|\leq p(|x|)$,
given the string $x\#y$, we can determine in time polynomial in $|x\#y|$ whether $(x,y)\in R$, and
$L = \{x\mid (x,y)\in R\}$.

So, if we have exponential time and we want to know if $x\in L$, we can just try all $|\Sigma|^{p(n)}$ possible values for~$y$ and see if $(x,y)\in R$ for any of those.  That takes time $2^{O(p(n))}$, so $L\in\,$EXPTIME.

Alternatively, we can define NP as the set of languages decided by polynomial time nondeterministic Turing machines.  In this case, suppose that $L$ is decided by machine $M$ in time $p(n)$ for some polynomial $p$, for inputs of length $n$.  Then $M$ makes at most $p(|x|)$ nondeterministic choices while determining if $x\in L$. By examining $M$'s transition function, we can find a constant $k$ such that $M$ has at most $k$ nondeterministic choices at each step of the computation (independent of the input), so it has at most $k^{p(|x|)} = 2^{O(p(|x|))}$ different sequences of nondeterministic choices while reading input $x$.  Given exponential time, we can simulate each of these possibilities one after another and see if any of them accepts.


XOR operation to swap to value without additional variable

First, xor is commutative and associative, therefore (a xor b) xor c = a xor (b xor c) = a xor (c xor b) = (a xor c) xor b, and in your case that means (x xor y) xor x = (x xor x) xor y = 0 xor y = y.
But this is just a rather pointless programming trick. It only works for integers, it can't be used for floating point numbers, strings, booleans, pointers etc., so it is pointless. It wouldn't pass any code review, so you can't ever use it in real life.


Finding number not in list with wildcards

Reduce from SAT. Consider a CNF formula $\phi = C_1 \land C_2 \land \ldots \land C_m$ over a set of variables $\{x_i\}_{i=1}^n$. Construct an instance of your problem as follows:

For each clause $C_i$, create a row (i.e. binary string) $B_i = b_1 b_2 \ldots b_n$, where

$$ b_k = \begin{cases}
1 & \text{if }\overline x_k \in C_i \\
0 & \text{if } x_k \in C_i \\
* & \text{if } x_k, \overline x_k \notin C_i
\end{cases}$$

We can preprocess $\phi$ to remove any clauses that contain both a literal and its negation, as these will of course always be satisfied and do not affect the result.

Any binary string $S$ that solves your problem also yields a satisfying assignment to $\phi$, using the reduction that sets  $x_i$ to the value of $S_i$.

Thus your problem is $NP$-hard. Since it is also clearly in $NP$, it is also $NP$-complete.


Regular of language of all words of length 3

Every finite language is regular. If $L$ is a finite language and $p$ is larger than the length of all words in $L$, then $L$ satisfies the pumping lemma with the constant $p$. Indeed, every word in $L$ of length at least $p$ can be pumped (vacuously).


Counting inversions in a list of integers using divide and conquer techniques

You can do the counting in linear time for each merge step by iterating over the right list and keeping track of the following information regarding the left list:

pointers to the first and last element that formed an inversion with the previous element of the right list
the number of elements between those pointers

Since this is homework, I'll leave it to you to work out the details and analysis.


Both avoiding aliases and avoiding excessive cache conflicts are valid reasons for using page coloring. Requiring page coloring to avoid aliases is unpopular because it places a mandatory constraint on page allocation. In general, modern non-embedded processors do not require page coloring to avoid aliasing.

Avoiding aliasing issues in hardware increases hardware complexity, so earlier processors (and perhaps some more recent embedded processors) chose to place the burden on software. Hardware can avoid aliasing issues in a cache with more index+offset bits than bits in the page offset by (for example):

checking alternate sets on a cache miss (as done by AMD's Athlon; when an alias was detected the block was moved to the current virtual index)
including the virtual address bits used for indexing L1 in a (tag) inclusive L2 (on an L1 miss and L2 hit, if the virtual address bits match the corresponding bits for the request, no action is necessary; if the bits do not match, the appropriate set to probe is known [whether the block is also in L1 could also be stored in the L2 tags to reduce coherence overhead, so some probes might be avoided])
using set prediction to guess the extra physical address bits used for indexing (a misprediction would be discovered after TLB access and corrected)
using reverse translation (physical to virtual) on a cache miss to find possible aliases (I think a PA-RISC implementation used reverse translation for coherence)

Using page coloring to reduce conflicts (for caches with simple modulo a power of two indexing) is less unpopular because the page coloring is not required for correctness. If a particular color becomes scarce, a page can be mis-colored with only a possible reduction in performance. This rationale for page coloring also means that the number of bits colored is less constrained. The (less practical) ideal may be to match all physical index bits for the last level cache with the corresponding virtual address bits, but even coloring just four bits can substantially reduce conflict issues.

It might be worth noting that coloring for alias avoidance need not match virtual address bits with physical address bits. As long as all potential aliases share the same virtual address bits used for indexing, alias issues are avoided. However, matching physical and virtual address bits may be convenient (and provide predictable conflict in physically addressed levels of cache).


Write $x = (x_h,x_l)$ and $y = (y_h,y_l)$, where $x_h,y_h$ are the high-order parts.
Alice sends $x_h$ to Bob ($n/2$ bits). Bob sends Alice two bits, indicating which of the following holds: $x_h > y_h$, $x_h = y_h$, $x_h < y_h$. The protocol then proceeds as follows:

If $x_h > y_h$, then Alice sends Bob $x_l$ ($n/2$ bits).
If $x_h < y_h$, then Bob sends Alice $y$ ($n$ bits).
If $x_h = y_h$, then Alice sends Bob $x_l$, and Bob sends Alice $y_l$ ($n$ bits).

In total, at most $\frac{3}{2}n+2$ bits are sent (assuming $n$ is even).


A control-flow graph serves a different purpose than a data-flow graph.  They aren't alternatives.  A control-flow graph represents the flow of control: which instruction can follow another.  A data-flow graph represents the flow of data: which instruction can read data that was created by another.

Perhaps you mean to ask why each vertex in a control-flow graph represents a basic block (a group of instructions) rather than a single instruction.  That's an optimization. You could have each vertex represent a single instruction, but often you'll have a long sequence of consecutive instructions with no control-flow transfer, and they all have the same properties, so it is natural to collapse them into a single vertex.  Also subsequent program analyses may be faster with this optimization; see Why is it better to do the data flow analysis in the basic blocks.


Why do we need binary trees when we have multi branch trees?

Yes, binary trees are used in standard libraries, implementing various data structures. For example, implementation of ordered set in the C++ STL library is typically based on red-black tree, which is a binary search tree of special kind.


find the missing number in a block of 3 numbers

Your current algorithm is linear in the size of your array $A$, which I'll call $n$. We can do a bit better, by observing the following: If some index $3i-1$ comes before the missing number, then $A[3i-1]=i$. Otherwise, $A[3i-1]=i+1$. (I start indexing at $0$)

So, we can do a binary search on $i$, as we always can see whether the index of the missing number is larger or smaller than $3i-1$. This gives an $O(\log n)$ algorithm, which is an improvement on your linear time algorithm.


Vector clocks: Why is it necessary to increment my clock on receiving a message?

Look at the definition of $<_H$.

We say that $e_1<_H e_2$ (event 1 happened before event 2) if:

$e_1,e_2$ took place in the same process, and $e_1$ happened first (events within the same process are ordered).
$e_1,e_2$ are the sending and receiving of some message $m$, correspondingly.

Finally, we take the transitive closure of the above, and this yield Lamport's happened before relation.

Our objective is to assign time stamps to events, $T_{e_i}$ with a partial order $<_t$, such that $e_1<_H e_2 \iff T_{e_1}<_t T_{e_2}$.

The timestamps suggested here are vectors in $\mathbb{N}^n$, with the ordering $T_{e_p}<_t T_{e_q} \iff T_{e_p}[p]<T_{e_q}[p]$ where $e_p,e_q$ are events in processes $p,q$ correspondingly (assume each time stamp contains the process id).

Back to your question, not updating your clock upon receiving a message would cause your new relation $<_t$ to disagree with $<_H$ in events within the same process. For example, you would have $c\not\rightarrow d$ (figure 3). In addition, this is mentioned in the paper (rule 2, increase the local clock at each atomic event, which is either sending or receiving a message).


Can I include some manual effort in creating an otherwise automated research prototype tool?

You can do that.  I have seen other papers that generate dummy classes like that (e.g., Klee).  How useful this will be may depend on how much effort it takes to write those dummy classes and how many are needed.
What matters is less the name (automated vs manual) and more that you describe clearly in your paper what its advantages and drawbacks are.  Usually it is valuable to compare to prior papers.  Can you demonstrate that your method is easier to apply than prior work?  Maybe because it requires less manual work?  If so, you may be in business.


Methods to evaluate a system of written rules

The trick here is that this works well provided that your rules can be expressed in predicate form. Is golf still fun if it's raining, or if you play poorly?

If you need something more flexible, you might want to look at some statistical/Baysean tools. There, you'd say that golf had a high probability of being fun, not that it was always fun all the time ever.


Proving $\{xx^R \mid x\in L_1, x^R\in L_2\}$ is context-free

One way to prove that a language is context-free is to find a context-free grammar that recognizes it. Just go through the definition (on Wikipedia for example) and try to find a context-free grammar for $L_3$ (it's easy). Good luck!


Determine if a language is Decidable or semi decidable

The language $L$ is not in $\text{RE}$. Consider the complement of the halting problem $\overline{Halt_{TM}} = \{ \langle M, w\rangle: \text{ $M$ does not halt on $w$}\}$ which is not in $\text{RE}$. We show that $\overline{Halt_{TM}}$ reduces to $L$ (and therefore, $L \notin \text{RE}$). From this point, I am assuming w.l.o.g that every machine has an input alphabet that contains at least three letters $a, b, $ and $c$.
A mapping reduction from $\overline{Halt_{TM}}$ to $L$ operates as follows. On input $\langle M, w\rangle$ of the reduction, the reduction outputs $\langle K\rangle$, where $K$ is a machine that operates as follows. On input $x$ of $K$, if $x = a$ or $x = b$, $K$ accepts. Otherwise, if $x\notin \{ a, b\}$, then $K$ simulates the run of $M$ on $w$. If $M$ halts on $w$, then $K$ accepts $x$. The reduction is correct. Indeed, if $M$ does not halt on $w$, then $K$ accepts the inputs $x = a$, and $x = b$, and does not halt on any other input. In particular, $K$ accepts at most two single-letter words. Conversely, if $M$ Halts on $w$, then $K$ accepts all inputs $x$, in particular, $K$ accepts at least three single letter words $a, b,$ and $c$.
Since $\text{R}\subseteq \text{RE}$, the above also proves that $L$ is not decidable. Yet, if you want to prove that $L$ is not decidable using Rice's theorem, then you note that the property $\text{P} = \{ M: \text{ $M$ accepts at most two single-letter words} \}$ is a non-trivial semantic property:

$\text{P}$ is nontrivial: it is easy to show that there are machines that accept at most two single-letter words, and there are machines that accept at least three single-letter words. I leave the details to you.

$\text{P}$ is semantic: let $M_1$ and $M_2$ be two machines with $L(M_1) = L(M_2)$. We need to show that both $M_1$ and $M_2$ are in $\text{P}$, or both are not in $\text{P}$. This is also easy as $M_1$ and $M_1$ recognise the same language, in particular, they accept the same single-letter words.


There is no precise answer to this.

The smallest GBA for a given language is never larger than the smallest BA for a given language, simply by the fact that BAs are a special case of GBAs.
It is easy to construct a language for which smaller GBA exist. Example would be (in LTL) $\mathsf{GF}(a \wedge b) \wedge \mathsf{GF}(a \wedge \neg b) \wedge \mathsf{GF}(\neg a \wedge b) \wedge \mathsf{GF}(\neg a \wedge \neg b)$ - a four-state GBA does the trick, but the BA needs more states to encode waiting for the next event (out of $a \wedge b$, $\ldots$, $\neg a \wedge \neg b$) to happen. So whatever fragment of LTL you build, this formula will not be contained therein. But if you now take a disjunction of this property with $\mathsf{GF}(a)$ and then with  $\mathsf{GF}(\neg a)$, then the smallest BA and GBA have the same size (one state). So you cannot give a precise syntactic representation of such a fragment (without making a containment check at least PSPACE-hard).
You can, of course, build an LTL fragment for which containment of the property in the fragment guarantees that the smallest GBA will not be larger than the smallest BA. You would get such a fragment, for example, by including the next-time operator as the only temporal operator in the fragment.
In practice, it doesn't matter anyway. Due to the many different optimizations in LTL-to-BA and LTL-to-GBA tools, you cannot predict very well whether they will compute BAs that are just as small as GBAs.


What is the goal of studying all those NP-complete problems?

No one are offended by that question, and it's an important question to
ask.
When working in graph theory, we don't believe that proving hardness
results for independent set on $\{K_4, K_5, P_3\}$-minor-free graphs are
"important".  However, it is interesting to see why a certain
forbidden minor puts a problem from being, e.g. polynomial time
solvable, to NP-complete.  It is then important that that is the
focus.
Here is an interesting problem:

Does edge deletion to claw-free graphs admit a polynomial kernel?

Why is it interesting?  Because we know almost everything else about
kernels and edge deletion to $H$-free graphs.  This one is interesting
because it is notoriously hard.  And hopefully, once this is solved, we
will understand more about the interplay between $H$-free graphs, edge
deletion, and polynomial kernels.
But I want to also mention that, yes, there are indeed applications that use algorithms for independent set, vertex cover, travelling salesman, etc.   See for example Dependency hell is NP-complete.

Fast forward to industry.  After quitting academia and joining
industry as a developer, I have more than once been able to tell people
that what they are working on is NP-complete, and to provide insight
into a problem that I got from studying these problems in a theoretic
setting.
I have written and published my share of "unusable" algorithms, but it's
not expected that people can take algorithms and plug-and-play them into
their system.  What they can take is the insight we provide in
structures, heuristics, as well as hardness.  Sometimes a problem is
only hard on graphs that have large grids as minors, and if you suddenly
see that your data is "tree-like", then you might have some tricks to
share with your future industry-colleagues.


Using induction to prove a big O notation

In essence, your proof is correct. A more general solution that you can use for recursive algorithms is this.

The way to solve this is to create a function T(n) that measures the runtime of the function and figure out the big O notation for it.

To solve a problem of size n, I must solve a problem of size n - 1. Then I must perform constant time arithmetic to get the answer. Thus :

T(n) = T(n - 1) + O(1)

Prove T(n) is O(n) ie by definition

T(n) <= cn for all n >= n0

Assume:

T(n - 1) <= c(n - 1)

then

T(n) = T(n - 1) + O(1)
T(n) <= c(n - 1) + d
T(n) <= cn + d - c
T(n) <= cn for c >= d

use T(1) as a base case to complete the proof, giving you n0 = 1


Runtime of algorithem when the internal for depend on the external for

For $i=1$ the internal loop runs for $n+r$ times, for $i=2$ the internal loop runs for $\lceil (n+r-1)/2 \rceil+1$ times, for $i=3$ the internal loop runs for $\lceil (n+r-1)/3 \rceil+1$ times, and so on till $i=n$ when the internal loop runs for $\lceil (n+r-1)/n \rceil+1$ times.

You now need to sum these numbers. I suggest you read about harmonic series.


Permute the subintervals of an interval partition to most closely align with a model partition

You can use integer linear programming (ILP) to solve this.  In particular, here is how to use an ILP solver to test whether there exists a way to permute the second partition so that you find $k+1$ alignment points (including the two endpoints).  Given an algorithm for this decision procedure, you can use binary search to find the optimal alignment.

Call a "block" the (non-empty) sequence of consecutive intervals between two alignment points.  The left and right endpoint of the interval are automatically alignment points.  If there are $k+1$ distinct alignment points (including these two endpoints), there will be $k$ blocks.

Let $\ell_1,\ell_2,\dots,\ell_n$ be the set of lengths of the first set of subintervals, and $\ell^*_1,\ell^*_2,\dots,\ell^*_{n^*}$ be the lengths of the second set of subintervals.  These are constants provided as input.

Introduce zero-or-one unknowns $x_{i,j}$ (for $1\le i\le n$ and $1 \le j \le k$), with the intent that $x_{i,j}=1$ means that the $i$th subinterval (of length $\ell_i$) from the first partition will end up in the $j$th block.  Similarly, introduce zero-or-one unknowns $x^*_{i,j}$, with the intent that $x^*_{i,j}$ means that the $i$th subinterval (of length $\ell^*_i$) from the second partition will end up in the $j$th block.

Now we get a set of linear inequalities, as follows:

$\sum_i \ell_i x_{i,j} = \sum_i \ell^*_i x^*_{i,j}$, for all $j$.  (This is two ways of representing the length of the $j$th block.)
$\sum_j x_{i,j} = 1$ (each subinterval from the first partition ends up in exactly one block) and $\sum_j x^*_{i,j} = 1$.
$x_{i,j} = 1 \land x_{i+1,j}=0 \implies x_{i+1,j+1} = 1$ (i.e., each block starts where the previous one ended).   This can be expressed as the ILP constraint $x_{i,j} - x_{i+1,j} \le x_{i+1,j+1}$.  Similarly for the $x^*$'s.
$x_{i,j} = 1 \land x_{i'',j} = 1 \land i < i' < i'' \implies x_{i',j}=1$ (i.e., the subintervals in a block are consecutive).  This can be expressed as the ILP constraint $x_{i,j} + x_{i'',j} - 1 \le x_{i',j}$ for all $i,i',i''$ with $i < i' < i''$.  Similarly for the $x^*$'s.
$x_{1,1} = 1$, $x^*_{1,1} = 1$, $x_{n,k}=1$, $x^*_{n^*,k}=1$.

Of course, in the worst case ILP can take exponential time, but ILP solvers are pretty good and often perform well on many real-world problems, so it is probably worth a try.

(You could also try coding this up using a SAT solver, but you'd need to implement arithmetic, so a front-end like STP would probably be a better bet than a plain SAT solver.)


Bellman-Ford without getting stopped by negative cycles

Solution 1: First pre-process the graph to remove all vertices that cannot reach $a$.  This can be done using depth-first search (backwards in the graph; i.e., in the reverse graph), in linear time.  You can also pre-process the graph to remove all vertices that are not reachable from $s$, again in linear time.

Solution 2: Run Bellman-Ford for $2n$ iterations and see if the value from $s$ to $a$ stays stable for the last $n$ iterations.  This should work: any simple path (with no cycle) from $s$ to $a$ must use at most $n-1$ edges, and if there is a non-simple path from $s$ to $a$ traversing a negative-weight cycle, then there is one with at most $2n-1$ edges.  You might want to double-check your example; maybe you made a mistake when simulating Bellman-Ford by hand.


This isn't a hidden Markov model; this is an ordinary Markov model.  Take a look at Wikipedia's article on Markov chains and specifically the notion of a steady-state distribution (or stationary distribution), or read about the subject in your favorite textbook -- there are many that cover Markov chains.


How to use a CFG to restrict a subset of a*b*c*d* so that there are at most as many a's and b's as d's?

There are lots of answers on this site about this subject. See, for example here and here. The underlying idea that often works for problems like this is to work from the inside out.

The $c^k$ part is easy: just use the production $V\rightarrow cV\mid c$.
The part surrounding the $c^k$ part consists of a bunch of $b$s followed by an equal number of $d$s. That's also easy; it can be generated by $U\rightarrow bUd$. Once we're finished with that, we switch to the $c$ part, so we have $U\rightarrow bUd\mid V$.
Keep going. Now you want to surround that part with a bunch of $a$s followed by the same number of $d$s. With what we've done so far, you should be able to do this part.
Finally, we want $i+j\le h$ so we concatenate the strings we've generated so far with zero or more extra $d$s. See hint (1).

As with many subjects, it gets easier the more examples you've done. Just keep at it.


Complexity of ANOTHER HAMILTONIAN CIRCUIT problem

This result is proved in the senior thesis The complexities of puzzles, cross sum and their another solution problems (ASP) by Takahiro Seta.

The systematic study of ASPs was initiated by Ueda and Nagao in their paper NP-completeness Results for NONOGRAM via
Parsimonious Reductions. See also Takayuki Yato's master thesis, Complexity and completeness of finding another solution and its application to puzzles.


Log-space reduction - How to calculate overall space needed?

The answer depends on how large the output of the reduction $f$ is. Usually, in the context of log-space reductions, there are two main variants of composing reductions (or, in this case, composing a reduction with an algorithm solving the reduced problem directly). Goldreich ("Computational Complexity: A Conceptual Perspective") names these naive and emulative compositions, though I don't believe there is a widely agreed terminology for them. (Please correct me if I'm wrong.)

Let $x$ denote a problem instance of $A$.

Naive composition. If $|f(x)|$ is small, then we can compute the entirety of $f(x)$ and then apply the algorithm solving $B$, reusing the space used to compute $f$. This means the space complexity is on the order of
$$\max(\log(|x|)^{c_1}, \log(|f(x)|)^{c_2}) + |f(x)|$$
plus some minor factors to organize things (e.g., keep track of whether we are performing the reduction or running the algorithm solving $B$).

Emulative composition. If $|f(x)|$ is large, then it makes sense not to generate the entirety of it in a single batch but, rather, to generate it bit-by-bit on the fly (i.e., as the algorithm solving $B$ needs it). Hence, whenever the algorithm solving $B$ needs bit number $i$ of $f(x)$, we run the reduction from scratch up to the point where bit number $i$ is produced and then pass this over to $B$. This means $f(x)$ is a virtual value which we provide to the algorithm for $B$ only on a bit-by-bit basis. Reusing space like this gives a space complexity on the order of
$$\log(|x|)^{c_1} + \log(|f(x)|)^{c_2} + O(\log(|f(x)|))$$
plus some minor factors, as before (e.g., to keep track of what bit of $f(x)$ we have last provided). Note how this is a big improvement whenever $|f(x)|$ is large.