In cycle stealing mode, Does CPU gets blocked for 1 cycle or blocked till DMA transfer completion?

The CPU doesn't stay idle at all. It just gives the control of the data Bus to the DMA for 1 memory cycle . DMA transfers the data in this cycle which is consistent with it's transfer rate. Meanwhile the CPU can perform operations which do not involve the memory bus (by the means of cache memory and registers). In the scenario which you have presented assuming each instruction takes 1 cycle to complete , every 833rd instruction will have to wait for the DMA to complete its operation.


Assuming that the end goal is to get an asymptotic bound on the time or space complexity of the algorithm that this recurrence relation represents, then start with $n = 4k^2$ s.t. $k > 1$ and notice the following:

$T(4k^2) = T(2k^2 + 2k) + 4k^2$

$T(2k^2 + 2k) = T( k^2 + k + \sqrt{ 2k(k + 1) } ) + 2k^2 + 2k$

$T(k^2 + k + \sqrt{ 2k(k + 1) }) = T(\ldots) + k^2 + k + \sqrt{ 2k(k + 1) }$

Substituting backward

$T(4k^2) = 7k^2  + 3k + \sqrt{ 2k^2 +2k } + T(\ldots)$

Substituting the original value of $n$

$T(n) = \frac{7}{4} n + \frac{3}{2} \sqrt{n} + \sqrt{\frac{1}{2}n + \sqrt{n}} + T(...) $

Each successive term is an order smaller than the one prior and as we look at the asymptotic behavior, those smaller terms will vanish and the linear term will dominate, thus $\mathcal{O}(n)$.


Prove or disprove: L^2 context free implies L is context free

Hint. Let $U\subseteq\mathbb{N}$ be any undecidable set and let $I = \{2u+1\mid u\in U\} \cup \{0, 2, 4, \dots\}$. Let $L = \{a^i\mid i\in I\}$. Now prove that $L^2$ is context-free but $L$ is not.


When is a variable bound or free in a lambda application?

wrong in assuming that bound and free are full complements

Yes. Each occurrence of a variable is either bound or free, but not both. But a variable is considered free if it has any free occurrences, and it's bound if it has any bound occurrences; it can be both at once.


Curious about an old algorithm which calculates modular inverse

You can replace:

$$ ~~q \leftarrow \Big\lfloor\frac{a - 1}{b}\Big\rfloor $$
$$ r \leftarrow a - q ~b  $$

By $q, r \leftarrow \text{divmod}(a, ~ b)$

  Algorithm terminates in even number of steps for some unknown reason

Those matrices assignments seem to be a fancy way of writing:

$$ \gcd(m_0, \color{blue}{a_0}) = \gcd(a_0, \color{red}{m_0 \pmod{a_0}}) = \gcd(\color{red}{m_1}, \color{blue}{\underbrace{a_0 \pmod{m_1}}_{a_1}}) = \dots = \gcd(m_n, 1)$$

So $a_i$ decreases every $2$ iterations, and $\gcd$ stops when $a_n = 1$.

Of course, you're not interested in computing the $\gcd$ per see, since you already know it's $1$, but finding the integers such that $Xm + Ya = gcd(m, a) = 1$.


You can use repeated substitution to obtain
$$
T(n) = f(n) + af(n/b) + a^2f(n/b^2) + \cdots
$$
Now suppose that $f(n) = n^\gamma$. Then
$$
\begin{align*}
T(n) &= n^\gamma + a (n/b)^\gamma + a^2 (n/b^2)^\gamma + \cdots \\ &=
n^\gamma \left[ 1 + \frac{a}{b^\gamma} + \left(\frac{a}{b^\gamma}\right)^2 + \cdots \right].
\end{align*}
$$

Let us assume that $n$ is a power of $b$, and that there is a base case $T(n) = C$ for some $C>0$.

There are three different cases to consider:

If $a < b^\gamma$ then the stuff in the brackets is a converging geometric series, and so $T(n) = \Theta(n^\gamma)$.
If $a = b^\gamma$ then all terms are the same. Since there are $\log_b n+1$ of them, $T(n) = \Theta(n^\gamma \log n)$.
If $a > b^\gamma$ then the terms keeps increasing, and so we can approximate $T(n)$ by the last term, which is $a^{\log_b n} C = \Theta(n^{\log_b a})$.

The condition $a \lesseqqgtr b^\gamma$ is the same as $\log_b a \lesseqqgtr \gamma$, which is how the theorem is usually presented.

The actual theorem has some extra conditions that are needed in some of the cases when $f(n)$ is not a function of the exact form $n^\gamma$, but these are just technicalities.


Can a method be written if the language is undecidable?

(c) If a language is undecidable, we can write a method that returns true for some strings that are an element of the language and false for some strings that are not an element of the language. But such methods will always return an incorrect result or not terminate on at least some elements of in the language.

(b) describes a particular kind of undecidable languages: the languages that are semi-decidable. A semi-decidable language is one such that there is a way to enumerate all the elements of the language with a Turing machine (or other equivalent computation method). So the method can go on enumerating the language until it finds its argument; this method loops indefinitely if the argument isn't in the language.

An example of a semi-decidable language which isn't decidable is the set of provable statements in any reasonable foundation of mathematics. (Note that I wrote provable, not true. The opposite of a provable statement is a statement that admits no proof; this statement might not be false: there may be no way to prove its opposite either.) Given a potential proof, you can easily verify that it's correct, and thus provable statements can always be recognized as such. However, it can happen that neither the statement nor its negation is provable, in which case the search for a proof would loop forever.

An example of a language that isn't semi-decidable, and whose complement isn't semi-decidable either is the set of programs in a Turing-complete programming language that take an argument and return true for all arguments. This is the halting problem. For a language that isn't semi-decidable, (b) doesn't apply: it is impossible to write a function that returns true for all programs that terminate on all arguments and loops forever (or returns false) on all programs that loop on at least one input.


Help with performance and speed-up question related to number of cores and their areas

The problem in an exam is that you need the answer that is expected from you - something I’d have a real problem with. So keep this solution to yourself.

Speed up is always hard to calculate - calculating execution time avoids lots of fractions and is equivalent. Assume your task would take one second on one processor X.

Since S is serial, you need at least S seconds. In that time, your 15 remaining cores can do 15S worth of work. If 15S >= 1-S or S >= 1/16 then all work is done after S. if S <= 1/16 then all cores can work on the task simultaneously, so the work takes 1/16 time. So time = max(S, 1/16) and speed up = min (1/S, 16). Speed up = 4 when S = 1/4.

You can have four processors of type Y at twice the speed or 1 of type Z at four times the speed. The work takes half of max(S, 1/4), that is max (S/2, 1/8) on 4 processors of type Y and it takes 1/4 on one processor of type Z.

X is fastest when S <= 1/8. Y is fastest for 1/8 <= S <= 1/2, and Z is fastest for S >= 1/2.


Time complexity of finding subsequences of a string segmented into parts


Enumerating all ways of pairing odd nodes

Your question doesn't have much to do with the route inspection problem. You are looking for all perfect matchings of $K_{2n}$ (the complete graph on $2n$ vertices), or equivalently, for an algorithm that enumerates all partitions of $\{1,\ldots,2n\}$ into pairs. A simple recursive approach is quite efficient:

Input: A non-empty list $L$ of even size.
Output: All possible partitions of $L$ into pairs.
Algorithm:

If $L = \{a,b\}$, return $(a,b)$.

Otherwise, let $a$ be an arbitrary element of $L$. Go over all elements $b \in L \setminus \{a\}$. For each $b$, generate (recursively) all perfect matchings of $L \setminus \{a,b\}$, and add $(a,b)$ to all of them.

The number of perfect matchings is quite large:
$$
(2n-1) (2n-3) \cdots (1) = \frac{(2n!)}{2^nn!} \sim \frac{\sqrt{4\pi n} (2n/e)^{2n}}{2^n\sqrt{2\pi n}(n/e)^n} = \sqrt{2} \cdot (2n/e)^n.
$$


Why, really, is the Halting Problem so important?

Because a lot of really practical problems are the halting problem in disguise. A solution to them solves the halting problem.

You want a compiler that finds the fastest possible machine code for a given program? Actually the halting problem.

You have JavaScript, with some variables at a high security levels, and some at a low security level. You want to make sure that an attacker can't get at the high security information. This is also just the halting problem.

You have a parser for your programming language. You change it, but you want to make sure it still parses all the programs it used to. Actually the halting problem.

You have an anti-virus program, and you want to see if it ever executes a malicious instruction. Actually just the halting problem.

As for the wikipedia example, yes, you could model a modern computer as a finite-state machine. But there's two problems with this.

Every computer would be a different automaton, depending on the exact number of bits of RAM. So this isn't useful for examining a particular piece of code, since the automaton is dependent on the machine on which it can run.
You'd need $2^n$ states if you have n bits of RAM. So for your modern 8GB computer, that's $2^{32000000000}$. This is a number so big that wolfram alpha doesn't even know how to interpret it. When I do $2^{10^9}$ it says that it has $300000000$ decimal digits. This is clearly much to large to store in a normal computer.

The Halting problem lets us reason about the relative difficulty of algorithms. It lets us know that, there are some algorithms that don't exist, that sometimes, all we can do is guess at a problem, and never know if we've solved it.

If we didn't have the halting problem, we would still be searching for Hilbert's magical algorithm which inputs theorems and outputs whether they're true or not. Now we know we can stop looking, and we can put our efforts into finding heuristics and second-best methods for solving these problems.

UPDATE: Just to address a couple of issues raised in the comments.

@Tyler Fleming Cloutier: The "nonsensical" problem arises in the proof that the halting problem is undecidable, but what's at the core of undecidability is really having an infinite search space. You're searching for an object with a given property, and if one doesn't exist, there's no way to know when you're done.

The difficulty of a problem can be related to the number of quantifiers it has. Trying to show that there exists ($\exists$) an object with an arbitrary property, you have to search until you find one. If none exists, there's no way (in general) to know this. Proving that all objects ($\forall$) have a property is hard, but you can search for an object without the property to disprove it. The more alternations there are between forall and exists, the harder a problem is.

For more on this, see the Arithmetic Hierarchy. Anything above $\Sigma^0_0=\Pi^0_0$ is undecidable, though level 1 is semi-decidable.

It's also possible to show that there are undecidable problems without using a nonsensical paradox like the Halting problem or Liars paradox. A Turing Machine can be encoded using a string of bits, i.e. an integer. But a problem can be encoded as a language, i.e. a subset of the integers. It's known that there is no bijection between the set of integers and the set of all subsets of the integers. So there must be some problems (languages) which don't have an associated Turing machine (algorithm).

@Brent: yes, this admits that this is decidable for modern computers. But it's decidable for a specific machine. If you add a USB drive with disk space, or the ability to store on a network, or anything else, then the machine has changed and the result doesn't still hold.

It also has to be said that there are going to be many times where the algorithm says "this code will halt" because it the code will fail and run out of memory, and that adding a single extra bit of memory would cause the code to succeed and give a different result.

The thing is, Turing machines don't have an infinite amount of memory. There's never a time where an infinite amount of symbols are written to the tape. Instead, a Turing machine has "unbounded" memory, meaning that you can keep getting more sources of memory when you need it. Computers are like this. You can add RAM, or USB sticks, or hard drives, or network storage. Yes, you run out of memory when you run out of atoms in the universe. But having unlimited memory is a much more useful model.


Mcculloch and Pitts Neurons: Is there errata in this article?

In the article mentioned, the figures each have a threshold of 2 for each neuron.  Therefore there is no errata.


Turing machine with an oracle for a proper subset of a known undecidable language

It seems you're working towards the notion of Turing reducibility. For example, adding a nontriviality assumption you're roughly asking here:

  Is there a set which is not computable but also does not compute the halting problem?

This is an excellent question, and the answer is far from obvious - but ultimately yes in a very strong sense (although a subsequent follow-up question is still open and generally believed to have a negative answer). These were some of the first serious results in computability theory:

Kleene and Post in $1945$ showed that the answer to your question is yes in a strong way: there is in fact some $A$ which is strictly intermediate between the computable sets and the halting problem with respect to Turing reducibility. Their argument also showed that we can find an $A$ which is incomparable with the halting problem with respect to Turing reducibility, so we get a strong affirmative answer.
This wasn't the end of the story, though. One year earlier, Post had posed a separate question: is there a computably enumerable set which is noncomputable but does not compute the halting problem? (Such a set would necessarily be strictly weaker than the halting problem as opposed to incomparable.) This was answered affirmatively about ten years later by Friedberg and by Muchnik independently; this required a new idea, the priority argument (although later priority-free proofs were discovered). The priority argument subsequently became one of the most, if not the most, important technique in computability theory, and was rapidly advanced far beyond the point of the Friedberg/Muchnik argument (some relevant results here include Sacks' density theorem and Lachlan's monster theorem).
However, the Kleene/Post and Friedberg/Muchnik degrees were all fairly artificial. Their arguments showed that the interval between the computable sets and the halting problem is extremely rich, and subsequent results would point towards them being "maximally" rich in some senses, but did not construct examples of such sets which are interesting on their own. Indeed, it is still the case that every natural Turing degree is basically just an iterate of the Turing jump (basically, something of the same "flavor" as the halting problem itself). The question of whether there is a natural intermediate Turing degree is still wildly open; there are some not-too-implausible candidates, but also results pointing towards a negative answer (and I think almost everybody believes that the answer is negative). Certainly the discover of any natural degree which isn't an iterate of the Turing jump would be one of the most important results in computability theory.


Can we quantify how close a partially correct programs is to being correct?

Partial correctness does not mean that not all statements of a specification are met by an algorithm. Have a look at the Wikipedia article about correctness:

Partial correctness of an algorithm means that it returns the correct answer if it terminates.

Total correctness means that is it additionally guaranteed that the algorithm terminates.

Such a proof of termination can e.g. be done by a loop variant: To proof that a loop terminates we show that an integer expression is decreased in the loop body and that the expression stays always non-negative. Then the loop can be only iterated a finite number of times.
The B-Method uses such integer variants in its while loops.
An alternative for an integer expression would be a finite set where in each iteration an element is removed.

Example: A simple algorithm to initialise an array of size n with 0:

i := 0
while i<n do
  x[i] := 0
  i := i+1
done

Partial correctness can be proven by using a loop invariant ("all elements of x in 0..i are 0", 0<=i, i<=n). One must show that the invariant is fulfilled when entering the loop and after each iteration. After the loop we know that the invariant is fulfilled and the loop condition not (i>=n together with the loop invariant implies that i=n, that again implies "all elements of x in 0..n are 0").
Even if we forget the line i := i+1, we could prove the partial correctness of the algorithm, i.e. the array will be filled with 0 after termination. The problem would be that it does not terminate.

Termination can be shown by choosing n-i as a variant. With the invariant i<=n it can be proven that the variant is always non-negative and n-i is decreased (by increasing i) in every iteration. Thus the loop must terminate. Together with partial correctness, total correctness is shown.


Please explain a greedy algorithm in a naive manner

In simple words, an algorithm is normally considered "greedy" if

it builds solutions step by step without backtracking
in each step it picks what's best in the current state.

To learn more about it, check this pdf out.

The animated gif above illustrates a greedy algorithm for finding the path that adds up to the biggest number.

It does so by choosing the node with the biggest number at each step. (Since the actual solution is the 7-3-99 path, the greedy approach fails to bring forth the correct path.)

This is why greedy algorithm may not always yield the right solution to a certain instance of a problem.

The gif animation was created by Swfung8 on Wikipedia for the article on Greedy Algorithm.


Finite State Machine that only accepts strings with equal number of 0's and 1's

The question is not really well-defined since there is no FSM that accepts your language $L$, so the existence of such an FSM implies anything – for example, $2+2=3$.

However, the intended solution was to notice that
$$ L \cap 0^*1^* = \{0^n1^n : n \geq 0\}. $$
Since the regular languages are closed under intersection, this shows that an FSM for $L$ can be converted to one of $\{0^n1^n : n \geq 0\}$.

Your attempt claims that an FSM accepting $L$ must have a counter. This is not a formal statement: it has no formal content. It's just intuition. A PDA for $L$ also doesn't have a counter; it has a stack. Counter is not a well-defined technical notion.


Confusion with analysis of hashing with chaining

The reason that we are using $\Theta(1+\alpha)$ rather than $\Theta(\alpha)$ is that $\alpha$ could be very small. Imagine for example that the hidden constant in both $\Theta$s is one, and that $\alpha=0.000001$. There is a large difference between $1.000001$ and $0.000001$.

Regarding your wrong deduction, note that the first paragraph mentions average case and the second worst case. It's true that the average case is at most the worst case, but not the other way around.


Data structure for finding nearest squares from current square

Since you only measure distances from the centers of the squares, you can restate your problem as follows:
Maintain a dynamic collection $X$ of $n$ points in Euclidean space so that you can quickly find the $k$ nearest neighbors in $X \setminus \{p\}$ of a query point $p \in X$.

Using the data structure described here you can maintain such a collection in $O(\log^3 n)$ expected amortized time per insertion and $O(\log^6 n)$ expected amortized time per deletion,  after a preproessing requiring $O(n \log^2 n)$ expected time.

The data structure supports nearest neighbor queries (given a point $q$, report the point in $X$ that is closest to $q$) in $O(\log^2 n)$ worst-case time. Then, you can report the $k$ nearest neighbors of $p \in X$ in $O(k \log^6 n)$ expected amortized time as follows:

Delete $p$ from $X$ in $O(\log^6 n)$ expected amortized time.
Repeat $k$ times:

Query the data structure for the nearest neighbor $p' \in X$ of $p$ in $O(\log^2 n)$ worst-case time.
Report $p'$ as one of the $k$ nearest neighbors of $p$.
Delete $p'$ from $X$ in $O(\log^6 n)$ expected amortized time.

Reinsert all deleted points in $X$ in $O(k \log^3 n)$ expected amortized time.


What is $\tilde O$? There are two different definitions.

According to exercise 3.5 of Introduction to Algorightms by Corman et al., $\tilde O$ can mean $O$ with logarithmic factors ignored: $$\tilde O(g(n))= \{f(n): \text{there exist nonnegative constant } k \\ \text{ and positive constants } c, k, \text{ and }n_0
\text{ such that }\\ 0\le f(n)\le cg(n)(\log n)^k\text{ for all }n\ge n_0\}$$
According to Wikipedia entry, $f(n) = \tilde O(g(n))$ is shorthand for $f(n) = O(g(n)\left(\log g(n)\right)^k)$ for some $k$.

For any value $x>0$, $x^0=1$. If we take $k=0$ simply, we can see that for either definition,
$$f(T)=\sqrt{2}R\sigma\sqrt{T+\log T+1}=O(\sigma \sqrt{T}) =O(\sigma \sqrt{T}\,1)=\tilde{O}(\sigma\sqrt{T})$$

Here is the explanation for the second equality in the above equation.

$\log T=o(T) \Rightarrow
T+\log T+1=\Theta(T) \Rightarrow \sqrt{T+\log T+1}=\Theta(\sqrt T)$

W can also proceed more rigorously, using L'Hôpital's rule once.

$$\lim_{T\to\infty}\frac{\sqrt{T+\log T+1}}{\sqrt T} = \sqrt{\lim_{T\to\infty}\frac{T+\log T+1}{T}} = \sqrt{\lim_{T\to\infty}\frac{1+\frac1T}{1}}=1$$


Is there a similar categorization to Elementary Cellular Automata?

You might take a look at Lindenmayer Systems.

From Wikipedia:

  An L-system consists of an alphabet of symbols that can be used to
  make strings, a collection of production rules that expand each symbol
  into some larger string of symbols, an initial "axiom" string from
  which to begin construction, and a mechanism for translating the
  generated strings into geometric structures.

L-systems can be used to generate a Sierpinski triangle.


Expressing semantics of an array as a function

It makes little sense to think about how we are to encode an array as a function without explaining how we intend to implement the basic array operations. The characteristic property of an array is that we can

access the $i$-th element, and
set the $i$-th element.

In addition, certain equations must be satisfied. For example, if we look up the $i$-th element twice in a row, we will see the same value, etc. (These equations can be looked up in any standard source on the state monad.)

Now, it is quite obvious that an array can be encoded as a function. But we also have to implement get and set. Here is how we might do it in Haskell.

-- An array is represented as a function from integers to floats.
type Array = Int -> Float

-- create a new array all of whose elements are initialized to 0.0
new :: () -> Array
new () = \i -> 0.0

-- get a i returns the i-th element of aray a
get :: Array -> Int -> Float
get a i = a i

-- set a i x returns the array a, but with i-th element set to x
set :: Array -> Int -> Float -> Array
set a i x = \j -> if j == i then x else a j

We are not checking and bounds here, which we should. It may seem a bit unusual that set returns a new array, but there really is no way of modifying an existing one in a purely functional setting. Haskell has the so-called "monadic style" of programming which makes it much easier to work with this sort of encoding (although I wouldn't recommend the encoding for a real appliaction).


How to reach data segment from global pointer in MIPS?

As Yuval Filmus said, addresses are unsigned.


Almost all CPUs contain interrupt lines. Both Bios and UEFI provide services for handling interrupts on these lines. UEFI is an extended version of the old Bios. So, UEFI provides all services provided by Bios.


Update all nodes in a graph in a way that at any step all chosen nodes are disconnected

Hint: Your question is tantamount to finding a partition of the vertices of the graph into as few independent sets as possible. This is the same as finding the chromatic number of the graph, which is NP-complete.


Time complexity of Vertex Cover vs Clique for fixed k

For any fixed $k$, $O(\binom{V}{k}) = O(V^k)$ is polynomial, whereas $O^*(1.47^{V-k}) = O^*(1.47^V)$ is exponential. Exponentials grow much faster than polynomials.

Plotting the curves is not so helpful, since these are asymptotic statements.

That said, if you're interested in particular $V$ and $k$, then your best option is to empirically check which of these algorithms is faster. Asymptotic notation is not helpful here, since it hides constant factors, and these could make a big difference for concrete values of $V$ and $k$.


Getting negative cycle using Bellman Ford

You are right for the most part. Just one more addition. When you go back the predecessor chain when trying to find the cycle, you stop when you either reach the starting vertex $v_1$ or any other vertex that has already been seen in the predecessor chain that you have seen so far. Basically, you stop and output vertices whenever you detect a cycle when going backwards using the predecessors.
As for papers, a simple Google search yields Xiuzhen Huang: Negative-Weight Cycle Algorithms. As a bonus, they also list another algorithm for finding negative weight cycles that are not reachable from the source vertex $s$.


Linear ordering of all subsets of size k

The bijection you are looking for is known as a combinatorial number system. A great further resource is Knuth's TAOCP.


On $1$-way functions and formalizing my intuitions about them

What would a rigorous proof look like?  It would start with the assumptions that are given, and derive the conclusion you want to derive, with each step being logically and rigorously justified.

How should you approach this?  Start with the definitions.  If you know what the definition of a 1-way function is, then you know what you have to prove, to prove that $a \circ b$ is a 1-way function.  Start by trying to prove that, using the assumptions you are given.  You'll probably use a reduction at some point: if there exists an adversary against $a \circ b$, then....

This is a basic question, which suggests to me you should either review the material in your textbook on reduction-based proofs of security, or check whether you have the mathematical maturity for this topic.


Complexity of scalar operations for integers

The quote from Wikipedia doesn't say that scalar operations on integers don't take constant time; on the contrary, it says that the analysis of the matrix multiplication is based on the assumption that those scalar operations do take constant time. This assumption is stated not because it's false, but because it is true only in some contexts.

If you use a fixed-width integer type, such as 32-bit or 64-bit integers, then arithmetic operations such as + or * take asymptotically constant time simply because there are only finitely many different inputs, so whichever inputs they are slowest for is a constant bound on their running time.

On the other hand, if you use a language like Python where integers are not bounded by a fixed number of bits, then arithmetic operations are not constant time, and generally cannot be done in constant time on real hardware.

The algorithm we use to add numbers on paper requires adding the rightmost digits, maybe carrying a 1 to the next column left, adding the digits in that column and carrying, and so on in a loop. This algorithm is O(log n + log m) because the number of digits you need to add is logarithmic. The algorithm for adding integers in Python has a lot of special details regarding the data structure used to represent those integers, but the way it works is essentially the same; a loop over the digits of the number from right to left, in O(log n + log m) time.


With this exact phrasing, and without additional assumptions on the structure of $T$, you can't really say anything about it's asymptotic behavior in general.

First, observe that the function $m^2n^2$ satisfies the constraints, so you can at least $\Omega(m^2n^2)$. However, you can get much more than that.

Let $f(k)$ be some function. Think of $f$ as a very quickly-growing function (e.g. $f(k)=2^k$).

Now, think of $\mathbb{N}^2$ as a two dimensional plane, with the $m$ and $n$ axes. We require that along every vertical and every horizontal line, the function is asymptotically quadratic. This means that we can do whatever we want with finitely many elements of every row/column.

Thus, for example, you can set $T(k,k)=f(k)$ for every $k$, and set $T(m,n)=m^2n^2$ for all entries where $m\neq n$.

The diagonal of this function is huge. That is, $T(k,k)=\Omega(f(k))$. However, the function still satisfies the constraints. Also, note that you can make this function monotonic by adding $f(k)$ to all elements in the relevant row/column. That is, take
$$T(m,n)=f(\min\{m,n\})+m^2n^2$$
This still has the same property, only here we change finitely many elements, instead of a single element.


How to compute the TF-IDF scores for a handful of documents, but without my own corpus?

Answer

What do you value in a ranking function? If you don't value TF or IDF, then it'll be difficult for you to achieve what you want to achieve.

Without a corpus however, you could use a frequency chart as a substitute for TF:

http://www.wordfrequency.info/free.asp?s=y

I had trouble finding a similar list for IDF online. However, you could just remove the IDF term from the TF-IDF equation. Finding an alternative for IDF is difficult.

Your Situation

4-5 documents isn't much, but it's still a corpus. Of course, it'll likely have more error than a larger corpus, but I see no reason why you can't use it. Also, why can't you use IDF? If the term exists in one document, then IDF can be computed, otherwise it shouldn't be in your controlled vocabulary anyway. Although if you're worried about error, then you could probably just discard it at this point.

If you just use your documents as the corpus, you can take advantage their context, which seems to be what you want here. Basically, many words will be more/less common in your subset than in the English language in general due to the specific domain and small sample size.


Terminology for Digitally Interpretting Environment

This falls within the broad field of computer vision.  It's related to object recognition, which is about the following problem: given a picture of an object, figure out what kind of object it is.  More generally, there's "scene analysis" (I think that's the right phrase): given an image, identify the objects in the scene and work out some understanding of their relative position and relationship.


Getting parallel items in dependency resolution

I assume that an edge $(u,v)$ means that $u$ has to be executed before $v$. If this is not the case, turn around all edges. I furthermore assume that you are less interested in paths (those are already given by the DAG) than in a good execution strategy given the dependencies.

You can easily adapt the topological sort procedure: instead of appending, merge all items of the same "depth" to one set. You get a list of sets, each of which contains items you can execute/install in parallel. Formally, the sets $S_i$ are defined thus for the graph $G = (V,E)$:

$\qquad \displaystyle \begin{align}
  S_0 &= \{ v \in V \mid \forall u \in V. (u,v) \notin E \} \\
  S_{i+1} &= \{v \in V \mid \forall u \in V. (u,v) \in E \to u \in \bigcup_{k=0}^i S_k \}
\end{align}$

You can then execute your tasks like this (let's assume there are $k$ sets):

for i=0 to k
  parallel foreach T in S_k
    execute T

Of course, this does not yield maximum throughput if tasks take different amounts of time: two parallel, independent linear chains sync after each element. To circumvent this, I suggest you work directly on the DAG with a parallel traversal starting in the source nodes -- those in $S_0$ -- and syncing/forking in nodes with several incoming/outgoing edges:

parallel foreach T in S_0
  recursive_execute T

where

recursive_execute T {
  atomic { if T.count++ < T.indeg then return }
  execute T
  parallel foreach T' in T.succ
    recursive_execute T'
}

and T.count is a simple counter holding the number of predecessors of T which have been executed already, T.indeg the number of predeccessors and T.succ the set of successors.


Typical NP-complete/hard problems in machine learning

Many theoretical problems in ML are NP-hard.

I think the famous AlphaGo is trying to solve a NP-hard problem.
Contextual bandit problem and its combinatorial variants are np-hard.
In social network analysis, the famous influence maximization problem is a NP-hard problem.
There are many others. You can search in google. Also you can find related papers in two famous ML conferences: NIPS and ICML.


Data structure to report all axis aligned bounding boxes intersecting an axis aligned query line

If your query line is x-axis aligned, this is essentially a 2D problem, as you can project all AABBs on the $(y,z)$-plane and answer the following question:
Given $n$ axis aligned rectangles and a query point $p$, report the rectangles containing $p$.

To answer this question you can build a 2D segment tree. This is similar to a 1D segment tree, except that you start building your segment tree according to the projections of your rectangles on one dimension (say $y$) and instead of having some interval $I$ as a leaf, you replace it with a segment tree storing all projections on the $z$-axis of rectangles whose projection on the $y$-axis contain $I$.

You can then query a point by going down the tree and looking for all rectangles which are potential candidates according to their $y$-coordinates and then check among those which "fit" according to their $z$-coordinates.

This leads to $O(n\log^2(n))$ space used, $O(\log^2(n))$ time per query and $O(n\log^2(n))$ construction time.


Hungarian Algorithm - Bipartite Graph Approach

(Converting a comment into a proper answer. Note that I now use the minimum cost convention of the reference given in the question.)

Any augmenting path serves. Note that you reverse the order of the arcs. Say you choose AW of cost -2 first. Then you have forward arcs AX, BW, BX, and backward arc WA, which has been reversed. Now BW,WA,AX is an augmenting path, of cost -6+2-2=-6, and you end up with backward arcs WB,XA which represent the optimal solution 8.


Minimize sum of $w_i(y_i-y)$ given $|y_i-y| \leq 4w_i$

Write
$$ L = \sum_{i=1}^n w_i y_i - \sum_{i=1}^n w_i y. $$
Thus $L$ is linear in $y$, and moreover, it is a decreasing function. Thus we want to choose the largest $y$ which satisfies the constraints $|y_i - y| \leq 4w_i$, if any. I'll let you figure out how to find this $y$.


Convert this language to Context Free Grammar

If you need to prove the language is context-free, showing a PDA that accepts $L$ is enough.

Sometimes, formulating the rules that generate exactly the language $L$ is not so trivial; in such cases you can start by a constructing the PDA that accepts $L$, then convert it to a CFG.

The transformation PDA $\rightarrow$ CFG can be found:

Lecture notes

Answer on this site


Why high and lower bit of generator must be 1?

The low order bit, also known as the least significant bit (LSB), is the "ones" bit of the number. For example, in 001101, the LSB is the rightmost bit 001101.

The high order bit, also known as the most significant bit (MSB), is the "topmost" bit of the number. In our example 001101, it is the leftmost bit 001101.

The two terms are also used figuratively (in general discourse): a high order bit is something important, and a low order bit is something not important.

Now to your question. We represent a message $m_0,\ldots,m_n$ by a polynomial $M(x) = \sum_i m_i x^i$. Given a generator polynomial $G(x)$, the idea is to extend the message to a new message $M'(x)$ that satisfies $G(x) \mid M'(x)$.

If the low order bit of $G(x)$ is zero, then such an extension isn't always possible. Indeed, the low order bit of $G(x)$ is zero iff $x \mid G(x)$. If this is the case, then $G(x) \mid M'(x)$ implies $x \mid M'(x)$, i.e. $m_0 = 0$. So if the lower order bit of $G(x)$ is zero, we will only be able to extend $M$ to $M'$ if $m_0 = 0$ (and even this is not necessarily a sufficient condition).

If the high order bit of $G(x)$ is zero, then the problem is a different. The probability that $G(x) \mid M'(x)$ for a random $M'$ is $2^{-\deg G(x)}$ (assuming $G$ is irreducible, that is, cannot be factored nontrivially). Therefore CRC offers us $\deg G(x)$ bits of protection. We therefore want $G(x)$ to have the maximum degree possible. This corresponds to having a high order bit of one.

In practice, $G(x)$ is stored without its high order bit: an 8-bit CRC polynomial really corresponds to 9 bits 1xxxxxxxx, but there is no need to store the 1.


Lower bounds: queues that return their min elements in $O(1)$ time

Yes, it can be done in amortized O(1) time (enqueue, dequeue, minimum). Have a look at the code and explanation given here.

Here are the most relevant parts quoted from the above link (emphasis mine; and of course, all credits for the solution go to the original author, Keith Schwarz):

  A FIFO queue class that supports amortized O(1) enqueue, dequeue, and
  find- min.  Here, the find-min returns (but does not remove) the
  minimum value in the queue.  This is not the same as a priority queue,
  which always removes the smallest element on each dequeue.  The
  min-queue simply allows for constant-time access to that element.

  The construction that enables the min-queue to work is based on a
  classic construction for creating a queue out of two stacks.
  ... we apply this construction to two min-stacks instead of
  two regular stacks. The minimum element of the queue can then be found
  by looking at the minimum element of the two stacks taken together.


Shortest path from source to all vertices, but with some wildcards

Take $K+1$ copies of your graph. For each edge $(x,y)$ and for each $i \in \{1,\ldots,K\}$, connect the $i$'th copy of $x$ to the $(i+1)$'th copy of $y$ with a zero weight edge. Also connect the $i$'th and $(i+1)$'th copies of each vertex with a zero weight edge. Now calculate the minimum distance between vertex 1 on the first copy to all vertices in the last copy.

I'll let you figure out why this works.


Can a PDA guess more than once? L = {aⁿ bⁱ aⁿ | i,n > 0 }

Here is a solution with one stack.

Start inserting a's into the stack.
Stop inserting a's when we encounter the first b. Halt any operations with respect to the stack as long as we get b's.
Start popping stack contents immediately when the b's stop and a's start.


Graph Traversal Solutions for "Find all unique paths" Problem

There could be many paths. For example, if the grid is $n \times n$ and all edges are present, then there are $\binom{2n}{n} = \Theta\left(\frac{2^n}{\sqrt{n}}\right)$ paths. You don't want to be going through all of them. Using dynamic programming, you can come up with the answer without going over all paths individually. In other words, dynamic programming is much more efficient than your suggested algorithm.


Is it legal to draw an NFA with fewer nodes than what I normally see?

It is not a convention. You must know that a regular expression denotes one regular language and this language can be generated by an infinite number of differeny automatona (in this case we are talking about NFA).

Why are you always encountering the second automaton in the books? This is probably because the second automaton is obtained from the regular expression $1^*0$ using a well known method called Thompson's construction.

Which of the two automata is better? There isn't just one answer. The first NFA looks simpler but maybe you will have more work when you try to formally prove its correctness. In the other hand the second automaton looks more complex but it was obtained by a proven method so we are sure that it is correct.


(note: the full desciption is a bit complex, and has several subtleties which I prefered to ignore. The following is merely the high-level ideas for the QTM model)

When defining a Quantum Turing machine (QTM), one would like to have a simple model, similar to the classical TM (that is, a finite state machine plus an infinite tape), but allow the new model the advantage of quantum mechanics.

Similarly to the classical model, QTM has:

$Q=\{q_0,q_1,..\}$ - a finite set of states. Let $q_0$ be an initial state.
$\Sigma=\{\sigma_0,\sigma_1,...\}$, $\Gamma=\{\gamma_0,..\}$ - set of input/working alphabet
an infinite tape and a single "head".

However, when defining the transition function, one should recall that any quantum computation must be reversible.
Recall that a configuration of TM is the tuple $C=(q,T,i)$ denoting that the TM is at state $q\in Q$, the tape contains $T\in \Gamma^*$ and the head points to the $i$th cell of the tape.

Since, at any given time, the tape consist only a finite amount of non-blank cells, we define the (quantum) state of the QTM as
a unit vector in the Hilbert space $\mathcal{H}$ generated by the configuration space $Q\times\Sigma^*\times \mathrm{Z}$. The specific configuration $C=(q,T,i)$ is represented as the state $$|C\rangle = |q\rangle |T\rangle |i\rangle.$$
(remark: Therefore, every cell in the tape isa $\Gamma$-dimensional Hilbert space.)

The QTM is initialized to the state $|\psi(0)\rangle = |q_0\rangle |T_0\rangle |1\rangle$, where $T_0\in \Gamma^*$ is concatenation of the input $x\in\Sigma^*$ with many "blanks" as needed (there is a subtlety here to determine the maximal length, but I ignore it).

At each time step, the state of the QTM evolves according to some unitary $U$
$$|\psi(i+1)\rangle = U|\psi(i)\rangle$$

Note that the state at any time $n$ is given by $|\psi(n)\rangle = U^n|\psi(0)\rangle$. $U$ can be any unitary that "changes" the tape only where the head is located and moves the head one step to the right or left. That is, $\langle q',T',i'|U|q,T,i\rangle$ is zero unless $i'= i \pm 1$ and $T'$ differs from $T$ only at position $i$.

At the end of the computation (when the QTM reaches a state $q_f$) the tape is being measured (using, say, the computational basis).

The interesting thing to notice, is that each "step" the QTM's state is a superposition of possible configurations, which gives the QTM the "quantum" advantage.

The answer is based on Masanao Ozawa, On the Halting Problem for Quantum Turing Machines.
See also David Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer.


Grammar still ambigous after removing left recursion LL(1)

Removing left-recursion from a grammar does not make it unambiguous. That's not the intent of removing left-recursion, and an ambiguous grammar is likely to still be ambiguous after left-recursion is removed.

In the case of your grammar, you have two productions which are inevitably ambiguous:

S → a b S
S → S a b

The first production allows an S to start with a sequence of a b, while the second production allows an S to end with such a sequence. However, nothing in the grammar specifies which of these two things takes priority. Since the order of grammar rules is unspecified, there are an exponential number of possible parses; although you might consider all the parses to be semantically equal, the parser needs to produce a single unique parse tree.

The solution, therefore, is to be clear about which parse tree to produce, which can be done fairly simply by creating a new outer production which handles one or the other of the alternatives. So, depending on your preference about associativity, you might use:

S' → S' a b
S' → S
S → a b S

or

S' → a b S'
S' → S
S → S a b

Alternatively, you could define a new non-terminal which just represents a sequence of a b:

S' → A S A
A → A a b
A → ε

In all cases, you should only consider removing left-recursion if you propose to use an LL parser. And if you plan on using an LL parser with only one token of lookahead, you'll have to deal with the prediction conflict resulting from the other rule for S which begins with a (by left-factoring, for example).


Finding the Candidate Keys of a Relation Using the FD's

You are right to start with the closures of the attributes. Finding the closures will help with finding the candidate keys.

There might be more efficient ways to go about this. What works for me at least is to look at the given functional dependencies. If none of them have single attributes on the left-hand side, then don't bother with finding the closures of the individual attributes-- they will just be themselves. I.e. given R(A,B,C) and FDs A,B->C and B,C->A, the closures of each individual attribute {A}+, {B}+, and {C}+, will be, respectively, {A}, {B}, {C}.

Here, though, you have one FD that has a single-attribute on its left-hand side: E->F. The closure of {E}+ is E itself plus whatever E can determine, which is F, thus {E}+ = {E,F}.

Now, you have figured out the closures of the individual attributes. But that doesn't go far since the rest of the FDs have two attributes on their left-hand sides. You can then calculate the closure of, say, {A,B}+. Automatically you can add A and B into that closure since each attribute determines itself. Now look to the set of given FDs and you see that there is one that goes A,B->C. Since you already have A and B inside the closure (you have all of the attributes on the FD's left-hand side in your closure) then you can add whatever attributes are on the right-hand side into your closure. So now the closure of {A,B}+ = {A,B,C}.

Essentially you keep building larger closures with the ultimate goal of finding closures that encompass the entire set of attributes.

In this case, the candidate keys (there are three) all have three-attributes each. Try calculating the closure of {A,B,D}+. You know automatically that A,B,D should go inside it. You can also add whatever attributes are in closures that are subsets of {A,B,D}+, such as {A,B}+ from before. Thus, you can add C to the closure which now looks like {A,B,C,D}. Now check the list of given FDs again and you will see that A,D->E can now be added, since A and D are inside the closure. Thus, the closure is now {A,B,C,D,E}. Finally, you can add in the FD of E->F. And that completes the set of attributes of the relation.

Here is a useful tool for checking your work:
http://raymondcho.net/RelationalDatabaseTools/RelationalDatabaseTools.html

You can use it to check your work on calculating closures and candidate keys.


Maximizing the weighted average value of a set of items by doubling the weight of a subset of items

This can be solved in polynomial time.

Hint: consider the decision version of the problem.

   Suppose I gave you a value $\alpha$ and asked you whether it's possible to find a subset of items so that the weighted average is at least $\alpha$.

Could you solve that version of the problem?  Does this give you any ideas about how to solve the original problem?

Alternate hint:

   Keep trying other greedy strategies.  You've tried one greedy algorithm, but there might be other plausible greedy algorithms.


SAT formula and satisfying assignment yield another different satisfying assignment

Your problem is NP-complete. Let's call it NextSAT$(F,\tau)$: accept iff $\tau$ is a satisfying assignment of $F$ and there exists a satisfying assignment of $F$ different from $\tau$.

NextSAT is clearly in NP. We now show that SAT $\leq$ NextSAT.

Let $F$ be a CNF on variables $X = \{x_1,\ldots,x_n\}$. If $F$ is the empty CNF, it is obviously satisfiable and we can thus pick any satisfiable instance of NextSAT for the reduction.

Assume now that $F$ has at least one clause. Choose $\tau : X \rightarrow \{0,1\}$ that does not satisfy $F$. It is easy to find by simply choosing a clause of $F$ and negating all its literals. Let $$G = F \lor (\bigwedge_{i \leq n} \ell_i) = \bigwedge_{C \in F} \bigwedge_{i \leq n} C \lor \ell_i$$ where $\ell_i = x_i$ if $\tau(x_i) = 1$ and $\ell_i = \neg x_i$ otherwise. We see that $G$ can be written as a CNF of size polynomial in the size of $F$.

Now, clearly, the satisfying assignments of $G$ is the disjoint union of the satisfying assignments of $F$ and $\tau$ since $\tau$ is the only satisfying assignment of $\bigwedge_{i\leq n} \ell_i$ and does not satisfy $F$. Thus, $F$ is satisfiable if and only if there exists a satisfying assignment of $G$ different from $\tau$. That is, if and only if NextSAT$(G,\tau)$ returns $1$.


This is (sort of) a trick question. This is not about a connection between 2SAT and 3SAT, it is that if 3SAT is in P, then anything which is in NP and has at least one true instance and one false instance becomes NP-complete! Let's imagine that we are in a world where 3SAT is in P.

Now consider the simple problem 1-VAR-SAT, which is SAT where we have one variable, and at most two clauses. There are 3 1-VAR-SAT problems, $x$, $!x$, and $x \vee !x$. The last is the only unsolvable one.

Turns out, if 3SAT is in P, then 1-VAR-SAT is NP-complete! Here is the model.

Take a 3SAT instance, and solve it (that's polynomial time, 3SAT is in P). If the problem is solvable, output $x$. If it is unsolvable, output $x \vee !x$. We have turned a 3SAT instance into a 1-VAR-SAT problem, which is solvable if and only if the original is solvable, in polynomial time!


Can the KenKen puzzle be solved using the same ideas as for Sudoku?

I don't think there's a simple way to express KenKen as an exact cover problem, although it's certainly possible since exact cover is NP-complete.

I think it would probably be easiest to express it as a SAT instance. Expressing Sudoku as a SAT instance is not hard, and the arithmetic constraints can just be expressed as the disjunction of all of the possible values which would satisfy the constraint (which you would then need to convert to CNF).


Combinational Logic - Need help with proof by rewrite

The last line is wrong :
1    1    1    1
Should be :
1    1    1    0

But the equations following are correct.

For the simplification :
BC’ + B’C + AB’C’ = BC' + B'.(C+AC') = BC'+B'.(C+A)=BC'+B'C+B'A

(I don't know the name of the rules used, there is some associativity, "X+X'Y = X+Y", etc...)

--- edit ---

Let's prove that X+X'Y = X+Y

Using :

A = A.B + A.B'
A = A+A
A + AB = A.(1+B) = A
A + A' = 1

X+X'Y = XY+XY'+X'Y = Y(X+X') + XY' = Y + XY'

Repeating (A=A+A) :

X+X'Y = X+X'Y + X+X'Y = X+X'Y + Y+XY'

= X + Y + X'Y + XY'

= X+XY' + Y+X'Y

= X + Y


Temporal extent is the same as duration. It is measured in units of time, like second. For example, 1 second is a duration or temporal extent.


Strongly regular graphs fit the bill, i.e., one property is that adjacent vertices have (exactly) $\lambda$ common neighbors. Paley graphs should give you an infinite family and an explicit construction.


How to give an upper bound on this bin packing problem?

Your relaxation is same as original problem.

$$\sum_{i\in S}w_i\leq f_j,\forall j\in S$$

is same condition as

$$\sum_{i\in S}w_i\leq\min\limits_{j\in S}f_j$$.

because

$$\min\limits_{i\in S}f_i \leq f_j,\forall j\in S$$.


Residual graph of a graph with bidirectional edges?

The residual graph is not a graph modeling method. It represents how we can change the flow on edges of a graph $G$ in order to increase the total flow when we compute the maximum flow.

The residual capacity used when you construct the residual graph is defined as
$$
  c_f(u,v) =
  \begin{cases}
     c(u,v) - f(u,v)  & \text{if $ (u,v) \in E$} \\
     f(v,u) & \text{if $ (v,u) \in E$} \\
     0 & \text{otherwise}
  \end{cases}\
$$

So, we cannot have both $(u,v)$ and $(v,u)$ in $E$ even though the antiparallel edges do not contradict the main network flow properties.

Your graph contains antiparallel edges which you should get rid of before you run a maximum flow algorithm on that graph, e.g., Ford-Fulkerson algorithm.

You could transform this graph into equivalent one with no antiparallel edges as following. You choose one antiparallel edge and "split" it into two edges. For example take $AC$ and introduce a new vertex $F$ and two new edges $AF$ and $FC$ with weights equal to $5$, i.e., $w(AF)=w(FC) = 5$. Similarly for every pair of antiparallel edges in the graph.


Two-Sum - Pre-sort Optimization Algorithm Design

The Two Sum solution can be optimized for runtime performance given the input Array is pre-sorted in ascending or descending order.
If Binary Search is used to find the targetCapacity above, it will run in logarithmic, $O(logn)$, average runtime. This is faster than the pseudocode above that runs in linear, $O(n)$, runtime using iteration and hashing.
If sorting was not provided in the input then it would not be possible to sort and search faster than $O(n)$. The best that could be done would be $O(nlogn)$ with a strategy such as Quicksort and Binary Search.
See: Stanford - Two Sum Explanation


LTL: Show $\neg(aUb) \Leftrightarrow \neg b U (\neg a \land \neg b) \lor G \neg b$

$aUb$ means that $a$ holds up to (and not necessarily including) the first point where $b$ holds, which must exist. There are two ways in which this can fail: $b$ never holds, or the first time that $a$ fails precedes the first time in which $b$ is true. The first case is handled by $G \lnot b$. The second case is handled by $\lnot b U (\lnot a \land \lnot b)$ (why?).


Can we minimise regular expressions using known DFA minimisation algorithms?

You should have asked first what you wanted : your second line.
Why assume that you have to reverse the determinization procedure to
get back to a regular expression. You confused your readers. You might add it as a possible way you imagined to go about it, after you stated what you want, not before.

To find out how to get a RE from a FA, just search the web for :
"convert finite automata to regular expressions". It is an interesting topic.

If you want a "minimal regular expression", just search for that.
But I am not sure what minimal would mean (number of operators used
?).

If you want to find a "minimal NFA" search for that, but I gather it is a
rather difficult problem, still under research.

If you want a "minimal DFA", search for that. It is a well explored
problem.


Your idea is correct. After all, $|x|_0 + |z|_0 = |x|_2 + |z|_2$ if and only if $|x|_0 + |z|_0 - (|x|_2 + |z|_2) = |xz|_0 - |xz|_2 = 0$. Note, however, you must (ab)use nondeterminism correctly so as to guess where $y$ is so as to know what belongs to $x$ and what to $z$.

Producing a CFG from a PDA is, unfortunately, not easy in general. There are cases in which, given a CFL, it is (much) easier to construct one than it is to construct the other. Having experience in these kind of exercises might give you a sudden flash of inspiration; failing that, you can always resort to the standard construction.
In this particular case, your "flash of inspiration" could have come from taking a closer look at the equation on the number of zeroes and two's. The idea is the equation holds for the empty word and we can produce symbols while conserving it; that is, for example, if you generate a zero for $x$ (i.e., $|x|_0$ is increased by one), then you also want to generate a $2$ somewhere so the equation still holds. Hence, a CFG with the following set of productions suffices:
$$\begin{align*}
S &\to X_0 S X_2 \mid X_2 S X_0 \mid X S X \mid Y \mid \varepsilon, \\
X_0 &\to X 0 \mid 0 X, \\
X_2 &\to X 2 \mid 2 X, \\
X &\to 0 X 2 \mid 2 X 0 \mid 1 X \mid X 1 \mid \varepsilon, \\
Y &\to 1 Y \mid \varepsilon
\end{align*}$$
A brief reasoning to make sure every word $w = x y z \in L$ is generated: The ones in $x$ and $z$ are generated by $X$, so we can exclude them. Further, any neighboring pair $02$ or $20$ may be generated by $X$ (and we include $X$ everywhere it is possible for such a pair to appear). Removing all such pairs, the only possible word left is of the form $x = 0^n$ and $z = 2^n$ or $x = 2^n$ and $z = 0^n$, and we can generate $w$ by using the appropriate rules for $S$ containing $X_0$ and $X_2$.


Use the following strategy $S$: Put each card $c$ on the stack with the smallest top card $c'$ such that $c' > c$.

Consider a generic strategy $T$, and iteratively simulate $S$ and $T$.
Let $s_i = (s^i_1, s^i_2, \dots, s^i_{h_i})$ be the values on the top of the stacks after placing the $i$-th card $c_i$ according to strategy $S$, in increasing order. Define $t_i = (t^i_1, t^i,_2, \dots, t^i_{k_i})$ similarly for strategy $T$.

Claim: $\forall i=1,\dots,n$, we have: i) $h_i \le k_i$ and ii) $s^i_j \ge t^i_j$ for all $j = 1, \dots, h_i$.

The proof is by induction on $i$.
For $i=1$ we have $h_1=k_1=1$ and $s^1_1 = t^1_1 = c_1$.
For $i>1$ we have two cases.

Case 1) $S$ places $c_i$ in a new stack. Then, by hypothesis we must have $c_i > s^{i-1}_j \ge t^{i-1}_j$ for every $j = 1, \dots, h_{i-1} $. It follows that $k_i \ge h_{i-1} + 1 = h_i$, proving i). Notice that ii) is also verified since, for $j=1,\dots, h_{i-1}$, we have $c_i > s^i_j = s^{i-1}_j \ge t^{i-1}_j = t^i_j$ by induction hypothesis, and $t^i_{h_i} \le c_i = s^i_{h_i}$.

Case 2) $S$ places $c_i$ in an existing stack. Let $\ell$ be the index such that $s^{i}_\ell = c_i$.
We clearly have $k_i \ge k_{i-1} \ge h_{i-1} = h_i$, proving i).
As far as ii) is concerned, for every $j = 1, \dots, \ell-1$ we have $c_i > s^{i-1}_j \ge t^{i-1}_j$, and hence $s^i_j \ge t^i_j$.
Also, $s^i_\ell = c_i = \min\{s^{i-1}_\ell, c_j\} \ge \min\{t^{i-1}_\ell, c_j\} = t^i_\ell$.
Finally, for $j=\ell +1, \dots, h_i$, we have: $s^i_j = s^{i-1}_j \ge \max\{c_i, s^{i-1}_j\} \ge \max\{c_i, t^{i-1}_j\} \ge t^i_j$.

Instantiating the claim with $i=n$ yields $h_n \le k_n$, showing that $S$ is minimizing the number of stacks.


If all computations of non deterministic Turing machine on the input string are all accept then is the boolean formula of them a tautology?

The formula $\Phi_{M,w}$, which says "Turing machine $M$ accepts input $w$" is never a tautology.

If you look at how the formula is defined, the variables denote things like "At time $t$, the machine is in state $q$" and "At time $t$, the $i$th cell of the tape contains symbol $\sigma$" and the clauses say things like, "$M$ is only in one state at a time", "every tape cell contains only one character at a time" and "the tape cells don't change except where the head is."  Thus, any assignment to the variables that violates these conditions (e.g., in two states at once, two characters in the same tape cell, characters on the tape changing without being written by the head), then $\Phi_{M,w}$ is falsified.


How are semaphores and test-and-set instructions connected?

Semaphores are an abstract mechanism to control access to a shared resource. Other such mechanisms exist, for example locks and monitors. These are the counterparts of abstract data structures – they specify an API for a mechanism and its semantics, but not its implementation.
Implementing such mechanisms correctly requires hardware support. One way to implement semaphores is using test-and-set. Another popular instruction is compare-and-swap. Both of these are examples of atomic instructions, which are instructions performing several operations that cannot be interrupted in the middle. Such atomic instructions are necessary to correctly implement mechanisms such as semaphores.
Typically these control mechanisms are implemented by the operating system. For example, POSIX-compliant systems implement POSIX semaphores. Semaphores are just one more service provided by the operating system. Under the hood, semaphores are implemented using atomic instructions provided by the CPU.


What techniques exist for energy-efficient computing and networking?

I only know very little about this topic. But from the algorithmic point of view there is a very nice review article from Susanne Albers, which is probably a good starting point.


Regular expression $(a^{*}b^{*})^{*} = \left( a+b \right)^{*}$ proof

First prove that every word in R1 is also in R2; then prove that every word in R2 is also in R1.  Spend some time on each and see what progress you can make.


Are expert systems outdated, what are better alternatives to them, if any?

Expert systems went through a phase of increasing acceptance and then widespread recognition of their limitations (see Wikipedia). There are many references that consider cons e.g. Problems in expert system development (Kemp, 1993).
In more recent years recommendation systems have taken over some of the function you describe in recommending products to customers. A notable development or historical event was the Netflix contest for movie recommendations which led to a burst of innovation and interest in the area. Another aspect of your question involves learning patterns of human behavior and this can be done with ANNs and similar technology.


Fast polynomial interpolation and Fast polynomial evaluation are algorithms that seem to be discovered back in 1973. They allow to interpolate/evaluate polynomial at N arbitrary points as far as field has 2N (?) roots of unity. Both are based on Fast polynomial division. All three are $O(n\log^2 n)$ time.

Currently they are taught at university courses and I downloaded a lot of lecture notes some time ago. Unfortunately, most links are now dead. So you can download my archive from https://mega.nz/#!ugYRXIYB!T_0cKabvJpZmBNN7ym98nofPIOksqTN5XFxToSKj9Zg

Or read the only course still available at the old address:
http://people.csail.mit.edu/madhu/ST12/scribe/lect06.pdf
http://people.csail.mit.edu/madhu/ST12/scribe/lect07.pdf

Or just look for up-to-date notes among google search results of 1, 2 and 3. Or, yeah, try to understand the original paper.


How to efficiently determine whether a relation is total?

A good first step is to construct a certain matrix corresponding to your relation, which I will let you figure out. Constructing this matrix takes time $O(|X|^2 + |S|)$ (or just $O(|S|)$, depending on your exact model). Given this, you can check antisymmetry in time $O(|X|^2)$, and transitivity in time $O(|X|^3)$.

You can improve the running time of transitivity checking to $O(|X|^\omega)$, where $\omega$ is the matrix multiplication constant; I'll let you figure out how.


What you have implemented is a variation of bidirectional Dijksktra's algorithm.

Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed or undirected graph. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet. When each search is Dijkstra's algorithm, we end up with bidirectional Dijkstra's algorithm.

In which order the algorithm should expand the search in each direction and in which efficient condition the algorithm can stop the search are two obvious and critical factors for a bidirectional search. They are studied in quite a few papers.

It looks like there is not a special or specific name for the variation of bidirectional Dijkstra's algorithm that expands the search from the side whose front is nearer to its starting points. One reason to explain away the lack of a name is that it is not easy to argue that strategy should offer a nicer heuristic when compared to other strategies.

You may want to read the Wikipedia article on bidirectional search.


Uncountable. In fact you can see a decision problem P as a language L (the words corresponds with the inputs that are accepted by P) on alphabet Σ. A language can be encoded by an infinite binary string generating all the strings in Σ* in lexical order and associating 1 if the current string belongs to L, 0 otherwise.

The set of infinite binary strings S is uncountable infinite. Let's assume it is countable infinite. Then we can find an association between natural numbers and the strings in S, and list them. But if we take the string composed of the complement of the bits on the diagonal, then we obtain a new infinite binary string which belongs to S but is not in the list. Contraddiction.

So the set of languages (and the set of decision problems) is uncountable infinite.


Don't understand closure under string reversal

Both $q$ and $r$ are states in this construction. If in original $\delta'$ we can step $r\stackrel{t}{\rightarrow} q$ then in the new $\delta''$  we can step $q\stackrel{t}{\rightarrow} r$. Like stated in the proof the arrows are reversed.

You are right, $\Sigma_\epsilon$ is $\Sigma$ plus the empty word $\epsilon$. The original automaton initially has no $\epsilon$-transitions. However it has multiple final states, and after reversing it would have multiple initial states. A possible solution is given here, using $\epsilon$-transitions, connecting a new final state from the original final ones. This is the first step, from $\delta$ to $\delta'$.

If you are still trying to decipher the construction then of course the induction is not trivial. Once you see the arrows are just reversed, then it is not hard to come up with a possible induction assumption: if I can go from $q$ via string $w$ to $r$ in $\delta'$, then I can go from $r$ via string $w^R$ to $q$ in $\delta''$. Then it is no longer difficult. It would not say "easy" as that depends on your experience with induction.


Is it possible to produce different shortest path trees using bellman ford and Dijkstra algorithm?

If there are multiple shortest paths (equal distances), you could get different results even between two runs of Bellman Ford, if for instance, the two runs consider edges in different orders.  But, for any graph with unique shortest paths, they obviously must both return the unique answer.


Reduction from Steiner tree to minimum set cover

It is your definition of Steiner tree problem that causes the difficulty here.

Your definition does not include the set of terminals $S\subseteq V(G)$. Then, a Steiner tree is a subtree $G'$ of the graph $G$ that spans $S$.

Keep this definition in mind, you can now move on to reduce $\mathrm{EXACT}$-$\mathrm{COVER}$-$\mathrm{BY}$-$3$-$\mathrm{SET}$ to your problem. The set of terminals would be the set of items to be covered, plus the root $r$. The construction is exactly your construction including your weight function.

But, the required weight $k$ is now $|U|/3$ where $U$ is the universe of items to be covered.

Clearly, a Steiner tree that spans $r$ and the whole universe should be a tree that can be rooted at $r$ with $k$ children as the set cover solution. Note that a Steiner tree is by no mean a rooted one but here we see that being seen as rooted at $r$ does help.


Find cut vertex in tree with constraint on the size of largest component

Your algorithm may not work. What you describe, in fact, is an algorithm for computing the center of the tree. The following is a brief theory behind this algorithm.
The distance, denoted by $dist(v,u)$, between two vertices $u$ and $v$ is defined as the shortest path between $u$ and $v$. The eccentricity of a vertex $v$ is defined as
$$ \epsilon(v)=\max_{u \in V}\{dist(v,u)\}$$
In simple words $\epsilon(v)$ is the maximum among all distances from the $v$ to a vertex $u$.
We define the center of a graph $G$ is the set of vertices with minimum eccentricity. Observe that step-by-step leaf removal in your algorithm does not change the eccentricity of the center.
Your algorithm essentially computes the center of the tree but the following is a counterexample. This tree

has the center $v_c$. Your algorithm will return $v_c$ as the cut vertex. But if your threshold is $3$ then the optimal cut vertex would be the vertex $u$.


Time complexity dependent on magnitude of input

Your result of seems correct, assuming none of the omitted operations modify the values of the variables n, L or x.

For a fixed value $k$ of n, the inner loop (for x in range(n):) loops over the set (or list; it is irrelevant for the analysis) $\{ 0, \dots, k - 1\}$, which contains $k$ elements. The outer loop (for n in L:) simply loops over each element of $L$ for a total of $|L|$ iterations, $|L|$ being the length of $L$. Thus, assuming the omitted operations are executed in $O(1)$ time, we obtain a time complexity of $O(m|L|)$ (as you propounded), where $m$ is the maximum value in $L$.

Incidentally, if you know the average value for the elements of $L$ you could also use the above reasoning to derive the average time complexity as well. (Just plug in the average value for $k$.)

As pointed out by @Raphael in the comments, of course, there is plenty of room for improvements if more assumptions are made about the contents of $L$.


How to create a subset with a given length and mean?

For every $i \in \{0,\ldots,|P|\}$, $j \in \{0,\ldots,|S|\}$, and $T \in \{0,\ldots,\mathcal{T}\}$ (I discuss $\mathcal{T}$ below), compute whether there is a subset of size $j$ of $p_1,\ldots,p_i$ which sums to $T$. You should take $\mathcal{T}$ to be your maximum allowable answer – $\max(P) \cdot |S|$ would definitely do, but you can probably pick something which is closer to $\mu_S |S|$, say $\mu_P |S|$. The running time is $O(|P| |S| \mathcal{T})$. In your case, assuming you choose $\mathcal{T} \approx \mu_p |S|$, then $|P| |S| \mathcal{T} \approx 2^{40}$, so this is barely feasible.
This is a naive dynamic programming algorithm, which probably can be improved, especially since you're only looking for an approximation.
For example, you could only look for solutions such that $S \cap \{0,\ldots,i\} \approx \frac{|S|}{|P|} i$ and $\sum(S \cap \{0,\ldots,i\}) \approx \frac{|S|}{|P|} \mu_S$, which will reduce the running time significantly. While this is only a heuristic, it might be possible to show that you get a decent approximation on average, if you randomize the order of $P$.
Another possible optimization is to quantize the partial sums, quantizing more aggressively as $i$ gets larger. If done carefully, you won't lose much in accuracy but will have a significant gain in running time.


Mapping reduction from $A_{TM}$ to $INFINITE_{TM}$ same as to $ALL_{TM}$?

The m-reducibility definition says

Language $A$ is m-reducible to $B$ (denoted $A\leq_mB$) if there is a
computable function $f:\Sigma^* \rightarrow \Sigma^*$ such that for
every $w\in \Sigma^*$, $$w\in A \iff f(w)\in B$$

The point you should pay attention to is that there is no need to talk about every $x\in B$. If you can map all elements of $A$ to one special element of $B$ say $x_0$ and all strings that don't belong to $A$ to string which doesn't belong to $B$ say $y_0$ then you are done!
Maybe if you think of $A\leq_m B$ as language $B$ is harder than $A$ then you feel better about the reduction. This means if you can decide $B$ then you also can also decide $A$.
So by the proof, you have provided we map every $\langle M,w\rangle \in A_{TM}$ to $\Sigma^*$ and every $w' \notin A_{TM}$ to $\emptyset$. Thus $INFINITE_{TM}$ is harder than $A_{TM}$. If you could decide just one elements of $INIFINITE_{TM}$ which is $\langle M \rangle$ that $L(M)=\Sigma^*$ then you could decide $A_{TM}$.


Checking if there are 2 elements in an array that sum to X in O(n lg n)

Sort the array say ascending order- Takes O(nlogn)

Keep two pointers in the array say fingers. Finger f1 at the first element and finger f2 at the last element.

Sum the elements to get f1+f2:
if f1+f2  == X you have found your solution
else if f1+f2 > X decrease f2 to point to the element to its left
else increase f1 to point to the element to its right

This step will take O(n) making the overall cost O(nlogn)

This solution is also referred to as the finger pointing solution. Can be used in any sorted collection where you can traverse in both the direction for eg in trees.


Finding an automaton with a given number of states

Hint: for 0111 you need 4 transitions (one for each input letter). If you have a sequence of 5 separate states (which is probably your first try), than you will have 4 transitions between them. However, if you have 4 states connected in a circle, you will also have 4 transition between them...


Turing Completeness + Dataflow Unification = Arbitrarily invertible (pure, nonrecursive) functions?

Dataflow unification behaves as you expect on first-order data (numbers, booleans, lists, trees, etc.) but can fail for higher-order data such as functions. In general, unifying functions requires using full higher-order unification, which has terrible performance, up to and including frequent failure to terminate (as it must, since otherwise it would solve the halting problem).

Higher-order logic languages such as $\lambda$-Prolog and Curry typically use restricted forms of higher-order unification, to get better efficiency at the price of completeness.


Confused about beta-reduction/shifting in untyped $\lambda$-calculus with de Bruijn terms

I figured it out - I was messing up the $\beta$-reduction in the first step by applying the substitution to $(\lambda. 0_1)_0$ instead of just $0_1$. This is the correct sequence of reduction steps:

$(\lambda. 0_1)_0\ (\lambda. 0_1)_0$
(by def. of $\beta$-reduction) $\rightarrow\ \uparrow^{-1}([0 \mapsto\ \uparrow^1((\lambda. 0_1)_0)] 0_1)$
(by def. of $\uparrow$) $\rightarrow\ \uparrow^{-1}([0 \mapsto (\lambda. 0_2)_1] 0_1)$
(by def. 1 of substitution) $\rightarrow\ \uparrow^{-1}((\lambda. 0_2)_1)$
(by def. of $\uparrow$) $\rightarrow\ (\lambda. 0_1)_0$


Karp-Rabin - what is the input for the worst case time complexity?

It all depends on what hash function you are using for your strings. The worst case for Rabin-Karp would be a case in which every single substring of the text has an equal hash to the pattern, therefore every single substring would be compared and the algorithm is equivalent to brute force.

The first example would be an example of this since the pattern matches in every case, therefore the algorithm would have to individually compare every substring (Assuming you are looking for every match and don't break out on the first one).

The second example would only be an example of a worst case if the hash of "AAB" matches the hash of "AAA," which is unlikely unless you have a really bad hash function. The algorithm would compare the hash of each substring of "AAA" and "AAB" and determine them to be non equal and bypass them until reaching the end where it hits "AAB" and finds and equal hash, comparing the substrings and determining them to be equal.


Randomly assign n elements to n agents such that each agent only knows its own element

This problem is part of a set of problems known as Mental Poker.
There is an excellent and small article by Shamir, Rivest and Adleman that describe a practical way about how to implement such algorithm.
The abstract is gold:

Can two potentially dishonest players play a fair game of poker without using any cards (e.g. over a phone)?
This paper provides the following answers:

No. (Rigorous mathematical proof supplied.)
Yes.(Correct & complete protocol given.)

Basically, from an information-theoretic point of view, playing such a game is impossible without a trusted third party, but it is feasible to design a protocol using well-known hard to reverse cryptographic functions.

The algorithm will work as following:
Suppose you have $n$ nonces (numbers from $1$ to $n$). Each participant in the protocol has access to secret functions $e_i$ and $d_i$ which are used to encrypt and decrypt data. This functions should satisfy few properties, which we will analyze later.
The first participant is given the full set of nonces. It encrypts each nonce with its secret function $e_1$, shuffles them randomly, and passes the resulting data to second participant.
Second participant will do the same, but in this case it doesn't have nonces, but a random permutation of the encrypted nonces. It will also encrypt each element with its own secret function $e_2$ and shuffle the data again.
Then third participant, and so on, until all participants have shuffled and encrypted the data with its secret function.
Overall the setup process is:
data = [1..n]
for i in [1..n]:
    data = [e_i(nonce) for nonce in data]
    shuffle(data)

After this setup, each element of data are the nonces encrypted with all secret functions $e_i$ in a random order unknown to any participant.
Notice that at this point is impossible for each participant to deduce each nonce without the help of other participants. And it is enough that one of the participants to shuffle the data completely random to remove any possible bias in the resulting order, independently if some malicious participant tries to bias the order.
Participant $i$-th is assigned the nonce at position $i$. To recover such nonce, participant $i$ asks each other participant $j \neq i$ to decrypt the value with its secret function $d_j$ in turns. At the end participant $i$ will have its nonce only encrypted with its own secret function $e_i$ so it can recover it using $d_i$.
Recovering nonce $i$:
nonce_i_encrypted = data[i]
for j in [1..n]:
    if j == i:
        continue
    nonce_i_encrypted = d_j(nonce_i_encrypted)

nonce_i = d_i(nonce_i_encrypted)

At the end of this procedure each participant knows its own nonce, but no other participant know anything about it.
After using this values for your current problem a player can claim they are really in control of such nonce, by either publishing the secrets functions $e_i$ and $d_i$, so everyone can compute locally all the values, or decrypting the value data[i] after the first step but before the second step, publishing and then using this value as the input in the second step to fully decrypt it.
The functions $e_i$ and $d_i$ should have the following properties:

$e_i(x)$ is the encrypted version of a message $x$ under key $i$,
$d_i(e_i(x)) = x$ for all messages $x$ and keys $i$,
$e_i(e_j(x)) = e_j(e_i(x))$ for all messages $x$ and keys $i$ and $j$,
Given $x$ and $e_i(x)$ it is computationally impossible for a cryptanalyst to derive $i$, for all $x$ and $i$,
Given any messages $x$ and $y$, it is computationally impossible to find keys $i$ and $j$ such that $e_i(x) = e_j(y)$.

As stated in the paper, most of this assumptions are somehow common except for property 3), which tells the encryption functions must commute.
They propose a simple encryption scheme that satisfies these properties. Let's say all participants agree on some large prime number $P$ (it is ok if it fixed in the protocol). And each participant secretly choose a random number $k_i$ such that $gcd(k_i, P - 1) = 1$. Let's say $q_i$ is such value that $k_i \cdot q_i \equiv 1 \mod(P -1)$. Then participant $i$ can use secret functions:
$$e_i(x) = x^{k_i} \mod(P)$$
$$d_i(y) = y^{q_i} \mod(P)$$
Some caveats about this algorithm: Participants can't cheat in such a way that colluding benefits them in learning the nonce about the other peer (unless of course $n-1$ participants collude, and only one nonce is remaining). However, malicious participants can attack the protocol by no participating, effectively stalling the dealing process, since a lot of actions are required from each participants while they are dealing the nonces. They can also produce gibberish, but this can be mitigated extending the protocol to detect which participant was the culprit and penalizing such participant at a higher level.

I implemented this algorithm for a poker game in NEAR blockchain. You can see the code in rust here. Notice there isn't any trusted third party in a blockchain, but there is a trusted computing environment which all participants can use as a mechanism to run this protocol.


Algorithm to compute partitions of a graph in N cliques

This problem is known as clique cover and it's NP-complete. In other words, no efficient algorithm is known.


Complexity of keeping track of $K$ smallest integers in a stream

If the value of the $i$-th element is $x$, it causes a heapify, if and only if $j < K$ of the previous $i-1$ elements are smaller than $x$. This gives

$$E[X_i] = \frac{1}{N^i} \sum_{x=1}^N \sum_{j=0}^{K-1} c_{j,x},$$

where $c_{j,x}$ is the number of sequences of $i-1$ elements, of which exactly $j$ are smaller than $x$.

Now, to determine $c_{j,x}$, note that there are $\binom{i-1}{j}$ possibilities for the positions of the smaller elements in the sequence. For each of the smaller elements there are $x-1$ possibilities for its value, while for the larger or equal elements there are $N-x+1$ possibilities. This yields
$c_{j,x} = \binom{i-1}{j} (x-1)^j (N-x+1)^{i-1-j}$, and thus overall (after shifting $i$ and $x$ by $1$)

$$E[X] = \sum_{i=0}^{R-1}\frac{1}{N^{i+1}} \sum_{x=0}^{N-1} \sum_{j=0}^{K-1} \binom{i}{j} x^j (N-x)^{i-j}.$$

Unfortunately, all my attempts at bringing this formula into a simpler/closed form have been unsuccessful.


I would suggest that you don't calculate the distance between all pairs of points, but only between pairs of points that are nearest neighbors.  You could store the points in some nearest-neighbor data structure, e.g., an octree, or even a fixed partitioning of space.  Some data structures might allow for relatively rapid updates, so you could even update after every iteration.

I'd also suggest looking at the methods used for simulating the n-body problem, as some of those might be applicable to your situation as well.  See https://en.wikipedia.org/wiki/N-body_problem#Many_bodies and https://en.wikipedia.org/wiki/N-body_simulation.

Also, you might consider adapting your objective function.  Rather than having all points repel, maybe you might have only those points whose neighbor are below a certain threshold repel; or you might make the repelling force a smooth function of the distance between the points, where this function is similar to $f(x) \approx x$ when $x \ll \tau$ (where $\tau$ is the threshold) and $f(x) \approx \tau$ when $x \gg \tau$.  You could select your threshold $\tau$ to be approximately equal to the expected final minimal distance that you think is achievable, or you could set it adaptively in each iteration.  This may require many more iterations, but each iteration can be done much faster, and it will avoid moving points that are already far from all their neighbors.


How do I visit all edges incident to a vertex in a DCEL data structure?

We can do that by exploiting the structure of the DCEL.

Recall first that each half-edge h has a pointer to its twin half-edge, h.twin. Each half-edge h also has a pointer to its successor, h.next, and predecessor, h.prev, half-edges, which lie on the boundary of its incident face (that is, on the boundary of h.face), assuming that the incident face of h lies to its left (if we walk, in a counter-clockwise matter, along the edges incident to h.face by following the "next" pointers).

So, how do we visit all half-edges which have a vertex v as their origin?

The solution consists in exploiting the pointers h.twin and h.next.

Let h be the half-edge such that a vertex v stores h as its own incident half-edge (that is, h == v.inc), where v is the vertex that we want to know all half-edges which have v as its origin, where h is one of those half-edges. We can then access h.twin, which has v as its destination. Hence, h.twin.next is a half-edge which also leaves v. Unless  v is adjacent only to one vertex u, which implies that v.inc == h is the only half-edge leaving v (and we are done), then h.twin.next is different from h. In that case, let w = h.twin.next. Then w.twin is a half-edge which has v as its destination (i.e. like h.twin). Hence, w.twin.next is also a half-edge which leaves v. We can proceed in this matter until w.twin.next is equal to h.

In a more formal way, the algorithm may look as follows.

function all_half_edges_leaving(v):
    h = v.inc
    list = [h]
    w = h.twin.next
    while w != h:
        list.append(w)
        w = w.twin.next
   return list

Clearly, once we have the half-edges leaving v, we can access in constant time also its twins (given that each half-edge stores a pointer to its twin). Alternatively, we may also store the twins in a list during the procedure above.


Count combinations differing by fixed number of elements

The trick to this count is to fix the elements that will be different, then calculate how many different choices we have for this set of elements. For each selected element we will have one less choice then we did originally, and for the elements which are to be the same we have one choice for that character. Let $V$ be the vector of the character set counts for the positions. In your example we would have $V=[3,2,4,2,3,3]$ and let $t$ be the number of differences. For each t-tuple $x$ (set of t positions) we have  $\prod_{i \in x} (V[i]-1)$ strings which differ in exactly those places. The final answer is the sum of this for every t-subset of the positions. Since you character set differs for each position you will need to go through all of the t-tuples to solve this. That is not overly bad since though since the number of t-tuples is polynomial instead of exponential as checking all combinations could have been.


Why is the zero-th power of the empty set {ε}?

Strings with concatenation and the empty word form a monoid.

In monoids, the empty concatenation/sum/product yields the neutral element, i.e. $\varepsilon$/0/1.

An empty concatenation does not need any words to start with, so $\emptyset^0 = \{\varepsilon\}$.

Intuitively, if you specialize

  $L^n$ is the set of all words obtained by $n$-fold concatenation of words in $L$

to

  $L^0$ is the set of all words obtained by zero concatenations (of words in $L$)

you can just stop reading after "concatenations" and the contents of $L$ do not matter; we don't even need it to be non-empty.


Regular expression to show that all strings contain each symbol atleast once

Your solution looks good to me, and it is probably what they expect of you.

It is interesting to consider the more general question: how large does a regular expression for this language be, as a function of the size of the alphabet? Denoting the size of the alphabet by $n$, Theorem 9 here shows a lower bound of $\Omega(c^n)$ for some (explicit) $c > 1$. (The theorem is for context-free grammars, but a regular expression can be translated to a context-free grammar.) Your construction is $O(n\cdot n!) = 2^{O(n\log n)}$, so there is a some gap here.


Generalizing with $kn$ people and $k$ cities we can see "move to city $j$" as a task. Furthermore, we have $n$ copies of each task. For all copies of a task $j$, the cost for person $i$ to move to that task is $c_{i, j}$.

But now the problem is a direct instance of the balanced assignment problem, with complexity $O((kn)^3)$.


One natural approach is to apply the error-correcting code, then encrypt the codeword with a stream cipher (e.g., AES-CTR mode).  The recipient can decrypt (this will not increase the number of bits with an error), then decode the code to correct any errors.  Anyone who does not know the symmetric key will be unable to distinguish the transmitted ciphertext from a random string.


How is Dynamic programming different from Brute force

A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution.

This statement is just plain wrong.

Dynamic programming recurrences do (often) consider all possible ways to split the given problem instance into smaller instances according to some scheme. However, it will not combine all solutions to all partial problems with each other and pick the best -- it combines only optimal partial solutions (and picks the best out of those).

The fact that this yield an optimal solution for the original problem is not trivial and does, in fact, only hold for some problems. Namely those that fulfill the Bellman principle of optimality (one of the most fishy, misunderstood "definitions" that are regularly quoted). See here for some more thoughts on that.

As a concrete example, consider the Bellman-Ford algorithm on a complete graph $K_n$ with unit weights: it only ever considers paths of length one and two (i.e. $\Theta(n^2)$ many) because those using one edge are all optimal. But there are infinitely many solutions if you don't bound the maximum number of edges allowed, and still $\gg (n-1)!$ many if you allow every node to be used only once. So clearly, Bellman-Ford -- a dynamic programming algorithm -- does not perform a brute-force search.


How does this Turing machine accept $a^n b^n$?

The machine just changes the $O$ to $A$ and the $1$ to $B$, in such a
way that it changes a $1$ each time it has changes a $0$. Hence, if
there is the same number of $0$ and $1$, they all end up being changed
at some point. The TM no longer finding any $0$ will go to the bottom
part of the diagram and check that all $1$ have been changed to $B$,
i.e. that the sequence of $B$ is followed by a blank space. In that
case it accepts.

But is some $1$ is left after the $B$, then the TM will block in state
$q_3$ (no transition corresponding to $1$ on the tape) and
reject. Indeed, that means hat there were more $1$ than $0$, which
does not conform.

But if there were more $0$ than $1$, say $0^n1^m$ with $n>m$, the TM
will block in state $q_1$.  The reason is that, after erasing $m$
symbols $0$ and correspondingly $m$ symbols $1$, the TM will erase
another $0$, and try in state $q_1$ to find another $1$ to erase. But
it will find none, only a blank space.


The answer is no. Every finite language is regular, and thus decidable. Therefore the existence of a finite language $L$ in $ \text{RE} \setminus \text{R}$ is impossible. However, note that there languages $L$ in $\text{RE}\setminus \text{R}$ (e.g., $Halt_{TM}$), and by what we have seen previously, such languages have to be infinite.


Asymptotic runtime of recursive algorithm uisng subsitution method

Here is an argument by substitution:
$$\begin{aligned}
T(n) &= 3T(n/2)+2n \\&= 3(3T(n/4)+n)+2n \\&= 3(3(3(T(n/8)+n/2)+n)+2n \\&= \cdots \\&= 3^kT(n/2^k)+\sum_{i=0}^{k-1}{2n\left(\frac{3}{2}\right)^i} \\&= 3^kT(n/2^k)+2n\frac{\left(\frac{3}{2}\right)^k-1}{\left(\frac{3}{2}\right)-1} \\&= 3^kT(n/2^k)+4n\left(\frac{3}{2}\right)^k-4n
\end{aligned}$$
Here, we stop to expand terms when $n/2^k=1$, or equivalently, when $k=log_2n$. Using that knowledge and the identity that you wrote in your question, we get that:
$$\begin{aligned}
T(n) &= 3^{log_2n}T(1)+4n\left(\frac{3}{2}\right)^{log_2n}-4n \\&= n^{log_2{3}}+4n\cdot n^{log_2\frac{3}{2}}-4n \\&= \cdots \\&= 5n^{log_2{3}}-4n \\&\in\mathcal{O}(n^{log_2{3}})
\end{aligned}$$
So as you can see, the fact that you have a factor 3 outside and a factor 2 inside makes your runtime polynomial in $n$.


Algorithm: Calculate every number in a given list using addition and numbers you've created

You're looking for an algorithm to generate an addition chain that includes each of the specified numbers.  As Wikipedia explains, the problem is NP-complete in general.  However, there are approximation algorithms and heuristics.  Searching for algorithms for computing addition chains should give you some candidate methods.


How to select best k fractions out of n fractions (k<=n) so as to have (numerator sum / denominator sum) maximum?

For a list of fractions, define the ratio as (sum of numerator) / (sum of denominator).

Question: Can we find a list of k fractions with the ratio ≥ r, for some given r?

Let the sum of numerators be X, and the sum of denominators be Y, then we require X / Y ≥ r or X - rY ≥ 0. For a single fraction x / y, we can calculate x - ry. We pick the k fractions where x - ry is largest. If the sum X - rY ≥ 0, then we have a list with ratio ≥ r, otherwise there is none.

We have obvious lower and upper bounds for r (the k-largest and the largest value of any fractions). With binary search we can easily find a list with maximum ratio.

Responding to some comments: What I presented is the basic idea. There is plenty of room for improvement.

For example "we pick the k fractions where x - ry is largest" - that can easily be done without sorting the array, much faster than n log n. Start like Quicksort, but only process subarrays that you need to determine the k largest values.

And it's not just binary search, because each time you actually find a list of fractions and can update the lower or upper bound for r or both. (For example if the lower and upper bound were 6.0 ≤ r ≤ 10.0, you look for a list with ratio 8.0 and only find one with ratio 7.6, then in the next search you know 7.6 ≤ r < 8.0 is possible).

Since the lower bound for r is one that was actually achieved, you can also check which is the smallest eps for which you would have put a different fraction in the top k list of fractions.


Why does absence of strongly polynomial time algorithm for LP imply restriction to rational instances?

A strongly polynomial algorithm in the context of linear programming probably means an algorithm in the arithmetic model (where numbers can be added, multiplied, compared and so on), whose running time does not depend on the magnitudes of the numbers involved. Such an algorithm could be applied directly for real numbers. Examples of algorithms of this type are the simplex algorithm and the criss-cross algorithm, both really a collection of related algorithms. However, variants of these algorithm are either known not to be polynomial-time, or (in some cases) not known and not expected to be polynomial-time.

Other algorithms for linear programming exist: the ellipsoid algorithm and the interior-point algorithm (again, there are really many variants of these algorithms). The number of iterations in each case depends on the precision needed to guarantee reaching an optimal solution, and that's why they are not strongly polynomial. While these algorithms can also be implemented in the arithmetic model, convergence is no longer guaranteed to take polynomial time.

When the inputs are rational numbers, then the number of iterations needed to converge is polynomial in the length of the input, and therefore these algorithms become polynomial-time.


Choose the kth choice of choosing n things out of m

This is called unranking.  The combinatorial number system provides a clean solution to this particular problem.

See also https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/ for further reading.


Simplest complete combinator basis pair for flat expressions

Coming back to this nearly a year later, I realized I had missed some critical research before posting.

Jot seems to fit the bill of what I was asking for, with two relatively simple combinators B & X that can be represented by a compact Goedel numbering.

I've simplified his reference implementation with Python:

def S(x): return lambda y: lambda z: x(z)(y(z))
def K(x): return lambda y: x
def X(x): return x(S)(K)
def B(x): return lambda y: lambda z: x(y(z))
def I(x): return x
def J(n): return (B if n & 1 else X)(J(n >> 1)) if n else I

J(n) returns the built up function denoting the program represented by its Goedel number n.

B (equivalent to Church encoded multiply) serves the function of functional application (parentheses), and can isolate the S/K halves of the single-basis Iota combinator X.

There a few important properties of this language that I'm (almost) shamelessly stealing from the website of the language's inventor Chris Barker, circa 2000.

Jot is a regular language in syntax but Turing-complete. You can see from the implementation of J(n) that if a host language supports tail-recursion, there's no stack space required to parse the bitstring program format.

The proof of Turing-completeness comes from Chris's site as well, implementing the already known Turing-complete combinatory logic using the S and K combinators:

K  ==> 11100
S  ==> 11111000
AB ==> 1[A][B], where A & B are arbitrary CL combinators built up from K & S

Jot has no syntax errors, every program given its Goedel number n is a valid program. This is probably the most important aspect to my own research, as it not only simplifies parsing to triviality, but should also in theory make Jot far more parsimonious than any Turing-complete encoding that has to skip over malformed programs.

I've written a few tools to 'solve' via brute force the semi-decideable problem of finding a function's Kolmogorov complexity in Jot. It works by relying on the programmer to specify some very characteristic training examples of a function's mapping, then enumerates all Jot programs until all training examples are matched, and lastly attempts a proof of equality of a found function with the original verbose implementation.

It currently only works for up to ~40 bits with my limited resources. I'm attempting a rewrite with a SAT solver to learn much larger programs. If you know how to unroll bounded nested closures as a boolean formula, please help out with my new question.

Now for some interesting comparisons to John Tromp's Binary Lambda Calculus, which is known for its conciseness, but does have the problem of possible syntax errors. The following programs were generated by my learning program in a few seconds.

Function    Jot       Binary Lambda Calculus   |J| |B|
--------|----------|--------------------------|---|---
SUCC      J(18400)  "000000011100101111011010" 15  24
CHURCH_0  J(154)    "000010"                    8   6
CHURCH_1  J(0)      "00000111010"               1  11
CHURCH_2  J(588826) "0000011100111010"         20  16
IS_ZERO   J(5)      "00010110000000100000110"   3  23
MUL       J(280)    "0000000111100111010"       9  19
EXP       J(18108)  "00000110110"              15  11
S         J(8)      "00000001011110100111010"   4  23
K         J(4)      "0000110"                   3   7
AND       J(16)     "0000010111010000010"       5  19
OR        J(9050)   "00000101110000011010"     14  20

From my own experiments, the hypothesis that Jot leads to smaller programs is slowly being confirmed as my program learns simple functions, composes them, then learns larger functions from an improved ceiling.