The first and the last statements are correct, while the second one is incorrect.
Statement 1
Denote by $T_{min}$ the actual running time of the algorithm $A$, in the best case, and $T_{max}$ in the worst case. By how we chose $T_{min}$ and $T_{max}$ it follows that $T_{min}\le T_{max}$.
From our assumptions, $T_{min}=\Omega(g(n))\implies T_{min}\ge c_1g(n)$. Also from our assumptions, $T_{max}=O(f(n))\implies T_{max}\le c_2f(n)$.
Combining them together we get:
$c_1f(n)\le T_{min} \le T_{max} \le c_2g(n)$, which means that $f(n)\le \frac{c_2}{c_1}g(n)\implies f(n)=O(g(n))$
Statement 2
Consider the following algorithm:
if lst[0] != 0:
    for x in lst:
        print(x)

And consider the inputs $I_1:=[0,1,2,3,...,n]$ and $I_2:=[1,2,3,...n+1]$.
Clearly, the algorithm takes $O(1)$ time with input $I_1$, but $\Omega(n)$ time with input $I_2$. Obvoiusly, $n\neq O(1)$ and thus the statement is incorrect.
Statement 3
Repeat the proof of statement 1. Note that also $T_{avg}\le T_{max}$ and thus the proof still holds.


Train Neural network with infinite amount of data

You are asking about an "infinite" set of data. The trouble with this question is that backpropagation (BP) is only applicable to a finite set of data (or a finite sample of an infinite population), which is iterated over repeatedly many times in order to converge to a minimum on the error curve. BP is simply not defined for an infinite set of data (outside of batch sampling), because repeated iteration over an infinite set of data is a undefined.

The answer to your question for a finite sample of data depends on the weights used to initialize the BP and how you are defining "optimal."

In the first regard, since the BP algorithm blindly follows the error curve gradient, it is vulnerable to get stuck in local minima, and by definition of the gradient there is no way out unless you reinitialize the weights.
In the second regard, optimality may be defined many ways. For example, it may simply stipulate producing an output error less than some $\varepsilon$ for all training data presented. Or your definition may reward generality of a model by placing less constraint on the error and instead use a threshold on some economic formula based on the likelihood of a data point together with the output error that it produces. Or you might invent some other definition.

Allowing for an infinite number of initial guesses and taking the first definition of "optimal" provided above, then it seems clear to me that Siegelmann and Sontag's theorem of universal approximation guarantees a "yes" answer to the finite-data question. But as D.W. remarked, this isn't very useful in practice.

For a trivial but illuminating example, a neural net may "universally approximate" a completely random stream of data for some finite set of training points, and then proceed to fail any and all optimality definitions for data points outside that set. Real world data can contain a sufficient degree of randomness to render the possibility of satisfying an optimality constraint based on non-training data pretty much indeterminate.


Two Minimax AIs playing against each other

First of all, note that in chess, white players plays first and it is a quite complicated game to build a AI for. The fact it exists several "draw" situations makes the evaluation function even more complicated to build. You may consider practice on another strategy game like checkers.

The evaluation function:

Most of IA are indeed based on an evaluation function. Let's talk about 2 opponents strategy games without random like chess. if we neglect "draw" situation, either you have a possible winning strategy, that will make you win whatever plays the opponent, either your opponent has one. When a "draw" situation exists, one player has a possible win strategy or both have a draw strategy.

All possible combinations are nevertheless impossible to explore and finding this strategy is matter of heuristic. The evaluation fuction is an heuristic to judge if a state of the game is likely to lead to a win. It can be a value the player tries to maximize.

Generally symmetric evaluation function like yours (nb white-nb black) works well for 1vs1 games. If the two players are equivalent AI, you will indeed have

eval player 1 = - eval player 2

Your second proposition is indeed the same thing. As maximizing $A$ is like minimizing $-A$. But for a proper simulation, I would rather prefer your first proposition that treat the 2 IA independantly.

Now about the "draw" situations, a player that can hardly win (having negative eval) can decide to look for a draw instead of a win. His evaluation function may therefore not be symmetric anymore. In the same way, a player dominating the game may use an assymetric evaluation to prevent a draw.

Depth/Minimax:

I think you misunderstood what is the minimax strategy. When it is your turn to decide what to play, you will explore some possibilies. You can for instance try all your possible moves and chose the one maximizing the evaluation function. This is a depth 1 exploration.

You may also try all your moves with all the moves the opponent may do on his next turn. This is depth 2 exploration. But in all these combinations, you have no information on what your opponent will play. The minimax strategy is to assume he will play the move maximizing his evaluation function, therefore minimizing yours.

For instance, let say you have 3 possible moves $M_i$  Each leads to several possible subsequent moves $M_{i,j}$ for your opponent. $E_k$ = $evaluation(M_k)$:

$M_1$ : $E_1 = 3$,  $E_{1,j} = [4, 1]$
$M_2$ : $E_2 = 5$,  $E_{1,j} = [7, 2, -1]$
$M_3$ : $E_3 = -1$,  $E_{1,j} = [-3, 0]$

in $depth 1$, you pick $argmax_i(E_i)$, that is to say $M_2$

in $depth 2$, you pick $argmax_i(min_j(E_{i,j}))$, that is to say $M_1$

You can of course go even deeper, applying minimax strategy on each opponent action. The deeper you go, the better is the heuristic approximation to find the best strategy. But the number of states to explore generally grows as a power law of the depth ($O(a^{depth})$). Thus, all the difficulty is to focus computation on interesting branch. You can have a look to some methods:

Monte Carlo Tree Search
Pruning


How to show that this decision problem is in co-NP?

P is a subset both of NP and of co-NP. Do you think the problem is in P?

(O(n^3) solution is trivial if poster states the problem correctly. As it is, $i_1 = i_2 = i_3  ... = 1$ is a solution.)

You need n/2 different indices $i_j$ such that $a_{i_2} / a_{i_1} = a_{i_3} / a_{i_2}$, $a_{i_3} / a_{i_2} = a_{i_4} / a_{i_3}$, etc.

There are $n^2 - n$ ways to choose $i_1$ and $i_2$. Once you chose these, let $d = a_{i_2} / a_{i_1}$. Then we must have $a_{i_3}$ = $a_{i_2} \cdot d$, $a_{i_4}$ = $a_{i_2} \cdot d^2$, $a_{i_5}$ = $a_{i_2} \cdot d^3$ etc. So all you have to do is check whether there are enough $a_i$ with these values and take their indices.

You can do this faster, but all I cared about was whether it's polynomial time.


Emulating boolean circuits using addition and multiplication (mod 5)

There are many other solutions. For example, even keeping your True and False, you can have $a\lor b = 1 - (1-a)(1-b) = a+b-ab = a + (1-a)b$ and so on.


Is the language of binary strings that contain a substring of the form $ww$, where $w \in (0+1)(0+1)^*$ regular?

Your language is regular.
Let's see which words do not belong to $L$. If a word contains $00$ or $11$ as a substring that it does belong to $L$, hence any word not in $L$ must have alternating $0$s and $1$s. If such a word has length at least $4$ then it must start with $0101$ or $1010$, and so again it is in $L$. We are left with the following words, which comprise $\overline{L}$:
$$ \epsilon, 0, 1, 01, 10, 010, 101. $$
Since $\overline{L}$ is finite, it is regular, hence so is its complement $L$.
What this argument shows is that any word in $L$ contains one of $00,11,0101,1010$ as a substring. This explains the given regular expression.


Welcome to the wonderful world of functional programming and the lambda calculus!

The answer is, there is no reason that you can't do this, and most sufficiently modern programming language (and some ancient ones i.e. LISP) will let you do this.

In a language with first-class functions, functions are data. You can treat them as variables, pass them as parameters, define them as lambda expressions (i.e. a nameless function). So in most languages, you can do something like this:

if (descending)
  comparison = lambda x y -> x < y
else
  comparison = lambda x y -> x > y

The lambda is just a way of saying "comparison a function which takes two arguments and returns the value after the ->".

Treating functions as data is an idea as old as computer science itself: lambda calculus was developed by Alan Turing's supervisor, Alonzo Church, in the 1930s.

Not being able to do this is a restriction of C and Java (although new versions are introducing lambdas), and a few other languages.

What you've shown is probably not possible because it's hard to parse (most parsers rely on the fact that < and > are special characters), but if you treat comparison as a normal function instead of an infix operator, and use a language that allows for higher-order functions, you can indeed do this, and in many cases it is preferable.


Here is Raphael's answer:

Chan and Pătraşcu give an $o(n\log n)$ time algorithm, but as far as I can tell from skimming the paper, they need $\Omega(n)$ space. Furthermore, Ajtai et al. prove that any (exact) $O(n)$ time streaming algorithm needs $\Omega(n)$ space. There seem to be approximations fitting your criteria, though.


Proving the L' = {w|deleting one symbol from a string in L} is regular when L is regular

Maybe the formal proof below will help you to understand the construction using a NFA.
Let $\mathcal{A} = (Q, A, \cdot, i, F)$ be a deterministic automaton recognising your language. For each pair of states $(p, q)$, let $L_{p,q}$ be the language recognised by the automaton $(Q, A, \cdot, p, \{q\})$. Thus $L_{p,q}$ is the set of labels of all paths from $p$ to $q$. By construction, each language $L_{p,q}$ is regular. Let $T$ be the set of transitions of $\mathcal{A}$, that is,
$T = \{ (p,a,q) \in Q \times A \times Q \mid p \cdot a = q \}.$
Let
$$
R = \bigcup_{(p,a,q) \in T}  \bigcup_{f \in F} L_{i,p}L_{q,f}
$$

Claim. $D(L) = R$.

Indeed, let $w \in D(L)$. By definition, there exist some words $u$ and $v$ and a letter $a$ such that $w = uv$ and $uav \in L$. Let $p = i\cdot u$, $q = p \cdot a$ and $f = q \cdot v$. By construction, $u \in L_{i,p}$, $v \in L_{q,f}$, $(p,a,q) \in T$ and $f \in F$. Thus $w \in R$.
Let now $w \in R$. Then there exist some states $p, q \in Q$ and $f \in F$  and some transition $(p,a,q) \in T$, such that $w \in L_{i,p}L_{q,f}$. It follows that $w = uv$ for some $u \in L_{i,p}$, and $v \in L_{q,f}$. Now $i \xrightarrow{u} p \xrightarrow{a} q \xrightarrow{v} f \in F$, which means that $uav \in L$. Consequently, $w \in D(L)$, which proves the claim.
Coming back to your question, the first copy of $\cal A$ in ${\cal A}'$ is used to accept $L_{i,p}$ and the second one to accept $L_{q,f}$. The $\epsilon$-transitions are used to pass from the first copy to the second one.


The problem (are there items such that all except the largest fit, and the total value is ≥ V) is obviously in NP. It is also NP complete because we can use it to solve Knapsack:

Given a knapsack problem, add an item with sufficiently large weight w, and sufficiently large value v, solve the problem with V + v, and the solution with the large item removed is the solution for the knapsack problem.

We can also solve this problem using knapsack: For each item with weight w and value v, solve knapsack removing this item and all items with weight > w and a goal for the value of V - v.


It seems you are looking after (linear) MDS codes. A linear $[n,k,d]$-MDS code  "partitions" the space into $2^k$ balls of size $2^n/2^k$ elements each, so that the minimal distance between any two codewords is at least $d=n-k+1$. This is the maximal possible distance by the singleton bound.

Now, Let $C$ be such a code, and consider its cosets, that is, given any word $w\in \{0,1\}^n$ look at the affine subspace $w+C = \{ w+u \mid u\in C\}$. It is not difficult to see that any such coset is also an MDS code (namely, it partitions the entire space into balls of the same size, with the same distance guarantees; however it are no longer a linear space, but an affine one).

To answer your question, given any $\alpha\in \{0,1\}^n$ and any coset $\beta = w+C$, $\alpha$ is within distance $\lceil d/2\rceil$ from one word in $w+C$ (the center of the appropriate ball where $\alpha$ lies). Due to the singleton bound, such a distance is optimal.


Knapsack problem -- NP-complete despite dynamic programming solution?

Knapsack problem is $\sf{NP\text{-}complete}$ when the numbers are given as binary numbers. In this case, the dynamic programming will take exponentially many steps (in the size of the input, i.e. the number of bits in the input) to finish $\dagger$.

On the other hand, if the numbers in the input are given in unary, the dynamic programming will work in polynomial time (in the size of the input).

This kind of problems is called weakly $\sf{NP\text{-}complete}$.

$\dagger$: Another good example to understand the importance of the encoding used to give the input is considering the usual algorithms to see if a number is prime that go from $2$ up to $\sqrt{n}$ and check if any of them divide $n$. This is polynomial in $n$ but not necessarily in the input size. If $n$ is given in binary, the size of input is $\lg n$ and the algorithm runs in time $O(\sqrt{n}) = O(2^{\lg n/2})$ which is exponential in the input size. And the usual computational complexity of a problem is w.r.t. the size of the input.

This kind of algorithm, i.e. polynomial in the largest number that is part of the input, but exponential in the input length is called pseudo-polynomial.


Is automatic multicore support at the hardware or compiler level possible?

The short answer: yes it's possible, but right now it generates slower code.

The long answer: the thing to keep in mind here synchronization. Computation is not just a bunch of independent computations. The results of one computation are used in other ones. Sometimes the order doesn't matter, and sometimes it does.

Take for example, some hard to evaluate function $f$. If we want to compute $f(f(10) + f(20))$, we can evaluate $f(10)$ and $f(20)$ in parallel, but we can't evaluate the final result until we've done the two inner evaluations and added them together.

This process of making sure things happen in the right order is called synchronization. There are many ways to ensure synchronization happens and that the code produces the same result even if some operations are moved around.

There are many models of concurrency: some have shared memory with locks on variables, some have totally separate processes that pass messages. But in every model, the synchronization carries some overhead. Acquiring a lock, sending a message between processes, each of these adds time that wouldn't be required if you evaluated the code sequentially.

Likewise, scheduling causes some overhead. If you have 200 processes and only 8 cores, you will probably be slower than if you have, say 20 processes and 8 cores, since you have to do a lot more work scheduling, but don't get additional parallelism.

The key, then, is to adjust the "granularity" of your concurrency. Too coarse and you don't make use of all the processors, but too fine and you get too much overhead from synchronization and scheduling.

This sort of analysis is hard, and right now compilers don't do it well enough to make general code faster, but I suspect with heuristics, and maybe even a bit of AI/machine learning, in the future we'll be able to automatically adjust the granularity automatically.

I'm not a hardware person, but my guess is that computing these sorts of things are way too complicated and time-consuming to be done on-the-fly at the CPU level.

At a compiler level, it's possible, but depends on your language constructs. I'm fairly certain finding the "optimal" parallelization of a program is undecidable, since you can probably construct some example where you can parallelize a program iff an arbitrary program halts.

However, like most program analyses, we can do "safe" approximations. In particular, there has been interesting research into automatically parallelizing "pure" functional languages like Haskell. When any side-effects of a function are captured by the type system, it's a lot easier for the compiler to know what operations can safely be performed in parallel. But to my knowledge, none of these efforts have succeeded so far in producing fast code.


A flip-flop is implemented as a bi-stable multivibrator; therefore, Q and Q' are guaranteed to be the inverse of each other except for when S=1, R=1, which is not allowed.  The excitation table for the SR flip-flop is helpful in understanding what occurs when signals are applied to the inputs.

S R  Q(t) Q(t+1)
----------------
0 x   0     0
1 0   0     1
0 1   1     0
x 0   1     1

The outputs Q and Q' will rapidly change states and come to rest at a steady state after signals have been applied to S and R.

Example 1: Q(t) = 0, Q'(t) = 1, S = 0, R = 0.

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 1) = 0
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(0 OR 0) = 1

State 2: Q(t+1 state 1)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 1) = 0
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  =  NOT(0 OR 0) = 1

Since the outputs did not change, we have reached a steady state; therefore, Q(t+1) = 0, Q'(t+1) = 1.

Example 2: Q(t) = 0, Q'(t) = 1, S = 0, R = 1

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(1 OR 1) = 0
         Q'(t+1 state 1) = NOT(S OR Q(t))  = NOT(0 OR 0) = 1

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(1 OR 1) = 0
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  =  NOT(0 OR 0) = 1

We have reached a steady state; therefore, Q(t+1) = 0, Q'(t+1) = 1.

Example 3: Q(t) = 0, Q'(t) = 1, S = 1, R = 0

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 1) = 0
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(1 OR 0) = 0

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 0) = 1
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  = NOT(1 OR 0) = 0

State 3: Q(t+1 state 3)  = NOT(R OR Q'(t+1 state 2)) = NOT(0 OR 0) = 1
         Q'(t+1 state 3) = NOT(S OR Q(t+1 state 2))  = NOT(1 OR 1) = 0

We have reached a steady state; therefore, Q(t+1) = 1, Q'(t+1) = 0.

Example 4: Q(t) = 1, Q'(t) = 0, S = 1, R = 0

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 0) = 1
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(1 OR 1) = 0

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 0) = 1
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  = NOT(1 OR 1) = 0

We have reached a steady state; therefore, Q(t+1) = 1, Q'(t+1) = 0.

Example 5: Q(t) = 1, Q'(t) = 0, S = 0, R = 0

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 0) = 1
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(0 OR 1) = 0

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 0) = 1
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  = NOT(0 OR 1) = 0

We have reached a steady; state therefore, Q(t+1) = 1, Q'(t+1) = 0.

With Q=0, Q'=0, S=0, and R=0, an SR flip-flop will oscillate until one of the inputs is set to 1.

Example 6: Q(t) = 0, Q'(t) = 0, S = 0, R = 0

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 0) = 1
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(0 OR 0) = 1

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 1) = 0
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  = NOT(0 OR 1) = 0

State 3: Q(t+1 state 3)  = NOT(R OR Q'(t+1 state 2)) = NOT(0 OR 0) = 1
         Q'(t+1 state 3) = NOT(S OR Q(t+1 state 2)) =  NOT(0 OR 0) = 1

State 4: Q(t+1 state 4)  = NOT(R OR Q'(t+1 state 3)) = NOT(0 OR 1) = 0
         Q'(t+1 state 4) = NOT(S OR Q(t+1 state 3))  = NOT(0 OR 1) = 0

As one can see, a steady state is not possible until one of the inputs is set to 1 (which is usually handled by power-on reset circuitry).


What is the algorithmic complexity of this?

Your algorithm has O(n^2) worst case complexity. You have a for loop of O(n). Inside your for loop you have a while loop which is O(currentNum). So if your currentNum is O(n) (ex nums[i] = length.nums for each i) then the complexity is O(n*n) = O(n^2).

Hint

Try not to recalculate things. You could use Dynamic programming technique. You need:

def canJump(i):
    if valid[i] has been assigned a True or False value:
        return valid[i]
    #else calculate valid[i]
    if i + nums[i] > len(nums):
        valid[i] = True
        return valid[i]
    for jump in range(1, len(nums[i])):
        valid[i] = any(False, canJump(i + jump))
    return valid[i]

print(canJump(0))

This is just a pseudocode. I have not tried it.
This way you only visit an element of nums once so it’s O(n).

[EDIT]
Actually I am wrong. My code is also O(n^2). Here is an O(n) solution.

at_least = n
for i from n-1 to 0:
    if nums[i] + i >= at_least:
        at_least = i
if at_least == 0: True else False

Now I think this is right. Sorry for the confusion. I got confused too.


Suppose that there were a network using only 4 comparators. The correct order of the inputs can be recovered by known the result of all 4 comparisons, since given these results, you can simulate the effect of the network. However, there are only $2^4 = 16$ possible results of the comparisons, whereas there are $4! = 24$ possible orders of inputs.


Find amortized cost for insertion in binary arrays using accounting/potential methods?

Here is a solution using direct calculation (I never liked all the fancy methods). Consider the cost of the first $n$ inserts, and suppose that $2^k \leq n < 2^{k+1}$. Thus only the arrays $A_0,\ldots,A_k$ are active. The cost of the $m$th operation can be broken down as follows:

Creating the initial array: 1.
If the number of elements (before adding the current one) is odd: 2.
If the number of elements is $3\bmod{4}$: 4.
And so on.

Observe now that:

The number of odd numbers among $0,\ldots,n-1$ is $\lfloor n/2 \rfloor$.
The number of elements $3\bmod{4}$ among $0,\ldots,n-1$ is $\lfloor n/4 \rfloor$.
And so on.

We conclude that the total cost of the first $n$ operations is
$$
\begin{align*}
&n + 2\lfloor n/2 \rfloor + 4\lfloor n/4 \rfloor + \cdots + 2^k \lfloor n/2^k \rfloor \\ \leq
&n + 2(n/2) + 4(n/4) + \cdots + 2^k(n/2^k) \\ =
&n + n + n + \cdots + n \\ =
&(k+1) n \\ =
&(\lfloor \log_2 n \rfloor + 1)n.
\end{align*}
$$
We conclude that the amortized cost is at most $\log_2 n + 1 = O(\log n)$.


Is the language of Turing machines that calculate a given function $f$ in RE or coRE?

Below, we assume $f$ computable, otherwise $L$ is empty, so RE and coRE.

For the "RE" part

This can be done with reductions, but the easy way is to exploit the Rice-Shapiro theorem.

Now, take a set of partial recursive functions $F$ ($F=\{f\}$, in your case), and define $L$ to be the set of TMs that implement some function in $F$.
If $L$ happens to be in RE, then by Rice-Shapiro we must have

if $g\in F$ has infinite domain, some finite restriction of $g$ must belong to $F$ as well
if $g$ is non-total, every computable extension of $g$ must belong to $F$

Often, one of these cases is false, implying that $L$ was not RE (provided it has the form above).

In your case, $L$ can not be RE since $F$ only contains $f$: if $f$ has an infinite domain, 1) is violated, otherwise 2) is violated.

In both these cases, you can replace Rice-Shapiro by suitable reductions from the complement of the halting problem, but doing that you are essentially repeating the proof of Rice-Shapiro. It is still a nice exercise, though: one can define one reduction for each case.

Even more in general, $F$ can never be finite if $L$ is RE. But $F=\{f\}$ is finite.

For the "coRE" part

If $f$ is the always-undefined function, $L$ is coRE. Indeed, for $M$ to implement a different function from $f$, it is enough that $M$ halts on some input, which is a RE problem.

If $f$'s domain is nonempty, say $f(x)=y$, $L$ is not coRE. To prove that, it suffices to reduce the halting problem to $L$.
Given $M$, craft $M'$ which on input $w\neq x$ outputs $f(w)$. When $w=x$, instead, run $M$, and if that halts output $y$ (otherwise we diverge).


Can a solvable problem be encoded in a recursively enumerable language?

Almost immediately from definitions, one has:

A solvable (decidable) problem can be encoded as (not in) a recursive language.
A semi-decidable problem can be encoded as (not in) a recursively enumerable language.


Dynamic Programming Solution to 0,1 KnapSack Problem

The key to understanding a dynamic programing problem is understanding the recursive definition and this can be daunting. For this problem we start with n objects labeled 1 to n.

We define $O(K,W)$ to be the optimal value for the first k items with a total weight W, we need to be able to define this in terms of subproblems now since without that, dynamic programming does not work. To add some quick definitions $W_k$ is the weight of the kth item and $V_K$ is its values.

So we define the recursive formula in 2 cases:

The first case is $O(K,W) = O(K-1,W) \quad \text{if $W_k$>W}$, meaning the k'th item weighs more then are target weight so it cannot be added even if nothing else was in the bag.

The second case is the decision case, $O(K,W) = MAX(O(K-1,W),O(K-1,W-W_k)+V_k)$ it means that either we don't add Item K to our set, in which case our best so far is $O(K-1,W)$, or we do add it, in which case we only have $W-W_k$ weight remaining to be filled with items 1 to k-1 and our total value is $O(K-1,W-W_k)+V_k$, which is our recursive value plus the value of the new Item.

The optimal solution is then $O(n,MaxWeight)$

Now for the dynamic programing part, the best way to start out is with our standard grid, we have our horizontal portion as k, so at any $i$ point we have the first $i$ items available, and our vertical as the total weight from zero to the weight the question was asking. The first row and columns will have a value of zero since with no weight or items, our bag has no value. Below I have put good walk through example. We walk through the algorithm by moving down each column, one column at a time. So at any grid location we check 3 other grid points which correspond to the values from the recursive definition, If we are at grid point $k,W$ and item k has a weight of$W_k$ and a value of $V_K$ we first check if $W<W_K$, if it is we use the square above it, since our item is too big, this is $O(K-1,W)$, if the item is not too big you check locations $k-1,W$ which is $O(K-1,W)$ and compare it to $K-1,W-W_k$ which is $O(K-1,W-W_k)+ V_k$, since we are going column by column from smallest to largest these are already calculated. If we keep doing this we will eventually get to the bottom right corner, which is the solution to the problem. The trick to this is we start at the smallest values and save the answers so for larger one the recursion is only a quick lookup instead of a full call.


Divide and conquer problem:sequence of integers (with possible repetitions)

If you want to use a divide-and-conquer algorithm, you can cut the array $A = [a_1, …, a_n]$ in two arrays by the middle $B = [a_1, …, a_{\frac{n}{2}}]$ and $C = [a_{\frac{n}{2}+1}, …, a_n]$.
Then the longest $k$-separated sequence in $A$ is one of the three following:

the longest $k$-separated sequence in $B$;
the longest $k$-separated sequence in $C$;
the concatenation of the longest $k$-separated sequence in $B$ ending with $a_{\frac{n}{2}}$ with the longest $k$-separated sequence in $C$ beginning with $a_{\frac{n}{2}+1}$, with the condition $a_{\frac{n}{2}+1} - a_{\frac{n}{2}} \leq k$.

Now the first two values can be computed recursively, and the third can be computed easily in time complexity $O(n)$. The complexity of this algorithm verifies $C(n) = 2C\left(\frac{n}{2}\right) + O(n)$, which implies $C(n) = O(n\log n)$.
Without divide-and-conquer, I think there exists a $O(n)$ dynamic programming algorithm:
For $A = [a_1, …, a_n]$ and $i \in [\![1, n]\!]$, define:

$f(i)$: length of the longest $k$-separated sequence in $[a_1, …, a_i]$;
$g(i)$: length of the longest $k$-separated sequence in $[a_1, …, a_i]$ ending with $a_i$.

Then it is easy to see that:

$g(i + 1) = \left\{\begin{array}{rl}1 & \text{if }a_{i+1}-a_i >k\\ 1 + g(i)&\text{otherwise}\end{array}\right.$
$f(i + 1) = \max(f(i), g(i + 1))$

That way, you can easily compute $f(n)$, which is the value you want, in time complexity $O(n)$.


L ={ $a^{m^n}$ | $m$>$n$ } is Regular or not by pumping Lemma

Let $A = \{ m^n : m > n \}$, so that $L = \{a^k : k \in A\}$. It is not clear whether $m,n \geq 0$ or $m,n > 0$. In both cases, every $m > 2$ is in $A$ and $0 \notin A$. If $m,n > 0$ then $1 \notin A$, while if $m,n \geq 0$ then $1 \in A$. In the former case, $L = aa^+$, and in the latter, $L = a^+$. In both cases $L$ is actually regular.

We can also consider the other interpretation, $A = \{mn : m > n\}$; this interpretation is wrong, but it can shed light on your proof. Again we find that every $m > 2$ is in $A$, and that $1 \notin A$. If $m,n$ are allowed to be zero then $0 \in A$, and otherwise $0 \notin A$. In the former case $L = aa^+ + \epsilon$, and in the latter, $L = aa^+$. In both cases $L$ is regular. So something must have been wrong with your proof.


The noise is Gaussian noise because the values you add to your existing images follow a Gaussian distribution, not the locations of where you add the noise - that is uniform (and not random at all - each pixel gets Gaussian noise added to it).


detecting a cycle in an undirected graph problem is in $RL$ complexity class

In fact USTCONN is in L (as shown by Reingold), and you can reduce your problem to USTCONN using non-backtracking walks. These are walks which are not allowed to backtrack, that is, after going from $x$ to $y$ we can't go immediately back to $x$ (but we could go back to $x$ via a different route). The graph contains a cycle iff there is a non-backtracking walk from some vertex to itself. You can formulate this problem as aan undirected connectivity problem, and solve it using the logspace algorithm for USTCONN. As a result, you can detect whether the graph contains a cycle in logspace.


Edge-connectivity of a weighted undirected graph

This is generally known as "edge connectivity augmentation", and there is a lot of literature on the subject. There are several fast algorithms for the task, and they come in different flavors depending on what you know about your graph, or what you specifically care about.

A basic question is "what is the minimum number of edges (or minimum cost of edges) to be added to the graph $G$ to increase its edge connectivity to a certain value?".


Armstrong's axioms more precisely 'inference rules': what's the distinction?

First, terminologically, "axiom" and "inference rule" are often used as roughly interchangeable as they tend to serve similar purposes. There are technical distinctions, which themselves can vary slightly, but outside the study of formal logic or related systems, these distinctions aren't that important.

In the context of formal logic, an axiom is a formula of the logic that is a theorem by definition. A rule of inference is a way of deducing new theorems from old theorems. Rules are always part of the logic, while axioms are separated into logical axioms, which are viewed as part of the logic, and non-logical axioms, which are viewed as part of the particular theory you are studying within the logic. Many logical axioms can be presented as rules and vice versa. For example, the axiom $P\supset(Q\supset P)$ roughly corresponds to the rule of weakening $\cfrac{\Gamma\vdash P}{\Gamma,Q\vdash P}$.

From a meta-logical perspective, rules of inference can be viewed as (definitional) axioms about the logic being studied (not to be confused with the "formal" axioms within the logic. Philosophically, "believing" in the conclusions of a logical theory requires "believing" the rules of inference just as much as "believing" the axioms.

So are Armstrong's "Axioms" axioms or rules of inference? It depends on how you formalize them. The "axioms" strongly suggest a deductive system, i.e. a system of rules, and that deductive system is quite useful in actually calculating functional dependencies. But, we could just as well take $\to$ and $\subseteq$ as relation symbols in a first-order theory and then the "axioms" really would be non-logical axioms of that theory. This could be viewed as meta-logical axioms about the deductive system, but it can just as reasonably be viewed as axiomatizing what "functional dependency" means without any deductive system in mind.

As for how to determine if $Y\subseteq X$ if we do indeed take a deductive system view of Armstrong's Axioms, in this context $X$ and $Y$ are meta-variables that stand for sets of attributes. They would be instantiated with expressions like $\{\mathsf{name},\mathsf{address}\}$. So for the rule you referenced, you'd simply be able to calculate that $\{\mathsf{name}\}\subseteq\{\mathsf{name},\mathsf{address}\}$ and $\{\mathsf{age}\}\not\subseteq\{\mathsf{name},\mathsf{address}\}$. An algorithm to calculate this could be formalized as a collection of inference rules itself, but there is no reason to do this. We can just assume that it can, in fact, be calculated. Obviously it can be in the intended use-case where the "sets" are explicitly presented, finite sets of elements with decidable equality.

Even for modus ponens, we have $P$ and $Q\supset R$ and we can apply modus ponens if $P=Q$, but checking the (syntactic) equality of two formulas while not hard is not completely trivial. Indeed, weakening is often presented with a rule like $\cfrac{\Gamma\vdash P\qquad \Gamma\subseteq\Delta}{\Delta\vdash P}$ and it is just understood that you can, in fact, calculate whether one set of formulas is a subset of another. It may also be presented as $\cfrac{\Gamma\vdash P}{\Gamma\cup\Delta\vdash P}$ where, again, it is just assumed that you have some way of calculating $\Gamma\cup\Delta$.


How to prove that a grammar is unambiguous?

There is (at least) one way to prove unambiguity of a grammar $G = (N,T,\delta,S)$ for language $L$. It consists of two steps:

Prove $L \subseteq \mathcal{L}(G)$.
Prove $[z^n]S_G(z) = |L_n|$.

The first step is pretty clear: show that the grammar generates (at least) the words you want, that is correctness.

The second step shows that $G$ has as many syntax trees for words of length $n$ as $L$ has words of length $n$ -- with 1. this implies unambiguity. It uses the structure function of $G$ which goes back to Chomsky and Schützenberger [1], namely

$\qquad \displaystyle S_G(z) = \sum_{n=0}^\infty t_nz^n$

with $t_n = [z^n]S_G(z)$ the number of syntax trees $G$ has for words of length $n$. Of course you need to have $|L_n|$ for this to work.

The nice thing is that $S_G$ is (usually) easy to obtain for context-free languages, although finding a closed form for $t_n$ can be difficult. Transform $G$ into an equation system of functions with one variable per nonterminal:

$\qquad \displaystyle \left[ A(z) = \sum\limits_{(A, a_0 \dots a_k) \in \delta} \
                \prod\limits_{i=0}^{k} \
                \tau(a_i)\
                : A \in N \right] \text{ with } \tau(a) = \begin{cases}
                                                            a(z) &, a \in N \\
                                                            z    &, a \in T \\
                                                          \end{cases}.$

This may look daunting but is really only a syntactical transformation as will become clear in the example. The idea is that generated terminal symbols are counted in the exponent of $z$ and because the system has the same form as $G$, $z^n$ occurs as often in the sum as $n$ terminals can be generated by $G$. Check Kuich [2] for details.

Solving this equation system (computer algebra!) yields $S(z) = S_G(z)$; now you "only" have to pull the coefficient (in closed, general form). The TCS Cheat Sheet and computer algebra can often do so.

Example

Consider the simple grammar $G$ with rules

$\qquad \displaystyle S \to aSa \mid bSb \mid \varepsilon$.

It is clear that $\mathcal{L}(G) = \{ww^R \mid w \in \{a,b\}^*\}$ (step 1, proof by induction). There are $2^{\frac{n}{2}}$ palindromes of length $n$ if $n$ is even, $0$ otherwise.

Setting up the equation system yields

$\qquad \displaystyle S(z) = 2z^2S(z) + 1$

whose solution is

$\qquad \displaystyle S_G(z) = \frac{1}{1-2z^2}$.

The coefficients of $S_G$ coincide with the numbers of palindromes, so $G$ is unambiguous.

The Algebraic Theory of Context-Free Languages by Chomsky, Schützenberger (1963)
On the entropy of context-free languages by Kuich (1970)


Prove that $L = \{ a^ib^jc^k | i < j \ and \ i+2j +3 < k \}$ is not CFG

Firstly I want to point out that what you want to prove that $L$ is a context free language or CFL not grammar. A CFL can be defined by a CFG, but they are very different things.
Anyway, back to your question.

I'm going to give you somewhat informal reasoning, but I think you will be able to formalize it if necessary.

Let us assume that $L$ is in fact a CFL. Then the pumping lemma for CFL's holds for $L$. Let n be the number of the pumping lemma for L.

Consider the word $w = a^nb^{n+1}c^{3n+4} \in L$

From the pumping lemma we have that $w = uxyzv, |xyz| \leq n, |xz| \geq 1, (\forall i \geq 0)[ux^iyz^iv \in L$]

We have two inequalities we can try to break:

$i < j$
$i + 2j + 3 < k$

Assume $xz$ does not contain $c$. This means that $xz$ contains only $a$'s or $b$'s (or both). Since $xz \geq 1$ This means we can pump up the word as much as necessary to break inequality $(2)$ -The right side of the inequality will remain the same when we pump up, but the left side will increase by at least $1$ on each step.

So we have deduced that $xz$ must contain a $c$.

Assume that $xz$ contains only $c$'s. Since $xz \geq 1$ we can pump down to remove at least one $c$. This will again break inequality $(2)$ since the right side will become less than or equal to the left.

So we have deduced that $xz$ must contain both a $b$ and a $c$. But since $xz$ contains a $b$, this means that we can pump down and remove at least one $b$, thus breaking inequality $(1)$.

Thus we have shown that no matter how we break up $w$ we can always pump it out of the language. This is contradiction with out assumption that $L$ is a $CFL$ so it must mean that $L$ is not a $CFL$.


A decision algorithm to choose what partner to use

Techniques developed for the multi-armed bandit problem might be useful for discovering the partner with the best acceptance rate and dealing with the changing acceptance rate over time.  Those techniques balance "exploration" (sending transactions to a partner as a way to learn more information about their acceptance rate) vs "exploitation (sending transactions to the partner with the highest acceptance rate, to make use of the information gained previously).  You'll probably be especially interested in the non-stationary bandit problem.


It's technically an "extension" in the sense that Ken Thompson's original paper (ACM DL subscription required) doesn't mention it. This is presumably because his regular expression compiler didn't support "+" syntax in 1968.

However, pretty much every textbook presentation of Thompson's algorithm (e.g. see Bruce Watson's 1995 review paper on FA construction) mentions it. It's likely that no one person "extended" the method in Thompson's paper, or the "extension" was done by Thompson when he decided to support "+".


What kind of bigram probability smoothing is this?

This looks like it might be implementing Laplace smoothing (though I can't explain the extra +2 in the first two calculations).

There are many smoothing methods, e.g., Lidstone, Good-Turing, Kneser-Tey,  Witten-Bell.  You can also use interpolation and backoff to handle rare or low-probability events when computing conditional probabilities like this.


If the Clique-k Problem is in P, why not Clique as well?

It's a matter of logical quantifiers.

Consider this statement: "if every natural number $n$ is bounded above by a constant $c$, how come there is no constant $c$ that bounds every natural number $n$ by above?".

The above is an example where $\forall n.\ \exists c.\ \ldots$ does not imply
$\exists c.\ \forall n.\ \ldots$. Indeed, in the former, we can choose $c$ after we see $n$, while in the latter we must do before, and we are unable to do that: whatever $c$ we choose, the statement becomes false for e.g. $n=c+1$.

To decide CLIQUE, once we take the instance $(G,k)$ to be checked,
we can use an algorithm which runs on $O(n^c)$ for some $c$ -- but here we are choosing $c$ after we have seen $k$. This does not prove that CLIQUE is in P. For that, we would need to find a constant $c$, and an associated $O(n^c)$ algorithm, which would decide any instance $(G,k)$, whatever $k$ is. And this is much harder.


What's the name of this packing problem?

The problem can be stated as finding the elementary intervals for a given set of intervals. It is a technique frequently used for problems in computational geometry (as suggested by nir shahar also).


Least common ancestor relative to an arbitrary vertex as root

Let us consider several possibilities:

The root is $r$. In this case, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(u,v)$.
The root is $u$, and $r,v$ are contained in different branches. In this case, $\mathrm{LCA}(r,u,v) = u$.
The root is $u$, and $r,v$ are contained in the same branch. If $r$ is an ancestor of $v$, then $\mathrm{LCA}(r,u,v) = r$. If $v$ is an ancestor of $r$, then $\mathrm{LCA}(r,u,v) = v$. Otherwise, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(r,v)$.
The root is none of $r,u,v$, and all of $r,u,v$ belong to different branches. In this case, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(u,v) = 1$.
The root is none of $r,u,v$, the vertex $r$ belongs to one branch, the vertices $u,v$ to another. In this case, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(u,v)$.
The root is none of $r,u,v$, the vertex $u$ belongs to one branch, the vertices $r,v$ to another. In this case, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(r,v)$.
The root is none of $r,u,v$, and all of $r,u,v$ belong to a single branch, say rooted by a child $s$ of $r$. We apply induction to the subtree rooted at $s$.

To convince yourself of the various claims, I suggest drawing some diagrams, and using the characterization of $\mathrm{LCA}(r,u,v)$ as the vertex on the unique path from $u$ to $v$ which is closest to $r$.


Prove 100,000,000 is a member of the set of functions defined by Big Theta of g(n), where g(n) = 1

You haven't provided a definition, but here is a standard one:

  Let $f,g$ be functions from $\mathbb{N}$ to $\mathbb{R}$. We say that $f(n) \in \Theta(g(n))$ (usually written $f(n) = \Theta(g(n))$) if there exist a natural number $N$ and positive real numbers $0 < a < b$ such that for all natural $n \geq N$ it holds that $$ ag(n) \leq f(n) \leq bg(n). $$

Roughly speaking, this says that the two functions $f,g$ have the same order of growth – they differ by a constant multiple. The definition is reflexive ($f(n) = \Theta(f(n))$), symmetric ($f(n) = \Theta(g(n))$ implies $g(n) = \Theta(f(n))$) and transitive ($f(n) = \Theta(g(n))$ and $g(n) = \Theta(h(n))$ imply $f(n) = \Theta(h(n))$), and so forms an equivalence relation. Each equivalence class is an "order of growth".

In your question, $f(n) = 10^8$ and $g(n) = 1$. So you have to find natural $N$ and positive reals $0 < a < b$ such that the following holds for all $n \geq N$:
$$ ag(n) \leq f(n) \leq bg(n) \Longleftrightarrow a \leq 10^8 \leq b.$$
I'm sure you can find such $N,a,b$.


So a not proven theorem would not be called a theorem

No, it's usually called a proposition, or a conjecture.

  I mean, a theorem is easy to prove because it is defined to be so and people call it theorem because they know how to prove it, no?

Just because you know a proof exists doesn't mean that you can efficiently find that proof.

  From this, I understand that proving theorems is hard

The thing is, there is no mathematical evidence that it's hard, other than the repeated failures of people to prove that it's easy. But of course, the failures of people to prove that it's hard acts as evidence that it's easy.

When people say that proving theorems is harder than checking them, they are speaking from intuition. From a complexity theory standpoint, there is no evidence that proving theorems is harder than verifying them. If there were, we would be able to resolve $P$ vs $NP$. Any guesses one way to the other are just that, guesses.

There is, however, an analogy, from computability theory.

When people are talking about proving versus checking for $P$ vs $NP$, they usually mean things like SAT or Constructive Propositional Logic, or other such systems with no quantifiers, or restricted quantifiers. But if we extend proofs to include predicate logic, with $\forall$ and $\exists$, then we have a firm result: checking proofs of these is decidable, and generating such proofs is undecidable. This is a basic consequence of the undecidability of the halting problem.


A Turing machine going to the right by the first $2 |w|$ steps

Suppose that the Turing machine has $N$ states. We call a state $q$ reachable if for some word $w$ of size at least $N$, when the Turing machine runs on $w$, it finds itself in state $q$ after reading $w$. During the following $N$ steps, the machine must go to the right. If it doesn't halt during these $N$ steps, then some state is repeated, and so the machine never halts. Since we assume that it does always halt, it follows that when the Turing machine is in state $q$ with an empty symbol under the head, it stops within $N$ steps, during which it continues traveling to the right.

The discussion above shows that if $w$ has size at least $N$, then the Turing machine halts within $|w|+N$ steps. This shows that the machine runs in linear time $O(|w|)$, which implies your exercise.

With a bit more work, you can show that the language accepted by the machine is in fact regular. Indeed, if we only consider words of length at least $N$, then we have a machine moving only to the right, so we know that $L(M) \cap \Sigma^N \Sigma^*$ is regular. Since $L(M)$ differs from this language by finitely many words, it follows that $L(M)$ is regular.


Creating admissible heuristics from functions?

Most beginners in the field see heuristics construction more as an art than a science. While I am not claiming here that there is a truly scientific (or even computable) method to derive them, I am sure they are not an art and we know about specific procedures to derive them (some of which are truly computable). In any case, we do not consider the differences in cost between the goal and start states as you suggest in the question. In all cases, admissible heuristics are obtained after relaxing any component in the problem formulation.

Let me just introduce you to three different methods to compute admissible heuristics: constraint relaxation, pattern databases and max heuristics. First, I will just introduce the overall idea. Next, I will provide further details of every technique. I will try to mention also some of the most relevant works that went along any of these lines including merge-and-shrink and Linear Programming.

In all cases, I will refer to the definition of state spaces which consist of two main ingredients:

States: they are defined by any structure that represents the contents of either the start or final state (denoted as $s$ or $t$ respectively) or any other configuration.
Operators: computable functions that are used to derive the immediately reachable descendants of a given state

Also, I will be using the $N$-puzzle as a running example. The proper definition of a state space in the $N$-puzzle is as follows:

States: they are defined by a permutation $\pi$ of symbols such that $\pi[i]$ represents the contents of location $i$
Operators: there is only one move (i,j) which swaps the contents of locations $i$ and $j$ provided that $\pi[i]=0$ (i.e., the blank location) and that $i$ and $j$ are either vertically or horizontally adjacent.

Please, be aware of the following: these techniques are not so simple that I could fully explain them in detail in a single response so that, unfortunately, my explanations will be rather incomplete

Constraint relaxation [Judea Pearl. Heuristics. Addison-Wesley, 1984] Judea Pearl proposed to pay attention to the constraints of the problem (and there should be some, otherwise we would not have an optimization problem), and then to relax a subset of them so that the resulting problem could be optimally solved. The optimal cost of the so-called relaxed problem can be easily proved to be an admissible estimate to reach the goal state. The constraints are usually found (but not only) in the pre-conditions implemented in the operators.

Take the $N$-puzzle. In this case, the constraints are found in the operator move. How would you program such a function? Well, most likely you would verify that $\pi[i]=0$ (i.e., $i$ is the blank location) and that $i$ and $j$ are either vertically or horizontally adjacent locations. Now, select either one of these constraints or both and relax them.

For example, relax both and consider now the resulting (relaxed) problem. For any state, how many moves does it take to get to the target node? If you are not constrained (and this is the point) to consider adjacent locations or the fact that you have to move the blank then you can swap any pair of locations. The optimal solution of the relaxed problems consists just of swapping the misplaced tiles.

Another example, relax only the first one. In this case, you are forced to swap adjacent locations but you are free to ignore the role of the blank tile. Clearly, the optimal solution consists of the sum of the minimum number of horizontal and vertical moves to place every misplaced tile in its goal location. This is known as the Manhattan distance.

In general, the heuristics that relax less constraints produce better estimations and are prefered.

Pattern databases [Culberson, J. C., Schaeffer, J. 1998. Pattern Databases. Computational Intelligence 14(3): 318-334] Constraint relaxation is just a general procedure that you, as an optimizer, have to follow in order to derive an admissible heuristic that you hard-code in your programs. Pattern databases are, instead, computable means to derive automatically the heuristic value of a lot of different configurations which are then stored in a large table.

I will not go here through more detailed explanations and I do suggest you instead to have a look at Need a practical solution for creating pattern database(5-5-5) for 15-Puzzle I am also providing a reply there but I do strongly suggest you to have a look at the response by Shashwat which is more detailed and uses the $N$-puzzle instead for explaining the main ideas. If you are interested in getting the source code for creating Pattern Databases, please e-mail me (carlos.linares@uc3m.es).

In case you are interested in the current state of the art of admissible heuristics in Automated Planning (introduced next) I do recommend you to have a look at merge-and-shrink (which do generalize Pattern Databases). A nice discussion is offered in: Malte Helmert, Patrik Haslum, Jörg Hoffmann and Raz Nissim. Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces. Journal of the ACM. 2013 (which was accepted at the time of writing but has not seen the light yet as far as I know).

Also, there has been some work on using Linear Programming Tasks to get the optimal cost of the relaxed problems:

A. J. Coles and A. I. Coles. LPRPG-P: Relaxed Plan Heuristics for Planning with Preferences. Proceedings of the Twenty First International Conference on Automated Planning and Scheduling (ICAPS-11). June 2011. They do use Linear Programming Tasks to satisfy numeric preferences.
Florian Pommerening, Gabriele Röger, Malte Helmert and Blai Bonet. LP-based Heuristics for Cost-optimal Planning. ICAPS 2014. To appear. This is a work that continues previous work (by the three first authors) for deriving tighter better informed values when using Pattern Databases as discussed here. The idea is really beautiful and this deserves (imho) a lot of attention.
Blai Bonet and Menkes van den Briel. Flow-based Heuristics for Optimal Planning: Landmarks and Merges. ICAPS 2014. To appear. This work is somehow related to the previous one but relates to merge-and-shrink as discussed here.

(NOTE: all this people are really nice, so that if you contact them to get a copy of the paper to appear it is very likely that they will send it to you. The other option is to wait for ICAPS 2014 to take place and then to download the papers: they are absolutely free).

Note please that, in this context, Linear Programming Tasks are used just to derive optimal costs of the relaxed problems precisely in the same way noted by Raphael: you first relax some constraints (according to any procedure) and then you set up a LP task to derive the optimal cost. I do fully believe that this is a hot topic in the field that will get more and more attention.

Max heuristics [Blai Bonet and Héctor Geffner. Planning as Heuristic Search: New Results. Proc. 5th European Conf. on Planning (ECP). Durham, UK. 1999. Springer LNCS 1809. Pages 359-371] The two previous methods for deriving (either automatically or not) admissible heuristics were motivated by the need of creating domain-dependent solvers. However, what if you want to create a single solver that is expected to optimall solve any problem (with some constraints, of course, and not just saying that "The Answer to life, the universe and everything is 42" :) )? This field is known as Automated Planning In this case we relax the reachability analysis by ignoring the delete effects (i.e., the fact that when swapping two locations they are removed from their initial locations; indeed, they are preserved so that the same tile appears in various places at the same time in the relaxed problem).

We just assume that all actions can be executed in parallel and compute the minimum cost to reach every literal (i.e., any atomic observation of our state formulation such as tile 6 is in location 2) from any other literal. You can certainly assume that actions have to be executed in sequence. In this case, the resulting heuristic is known as h add but it is not admissible so I left out of the discussion.

I am just leaving a lot of details out of the discussion here and I do recommend you to have a look at the paper I am just referencing. This is a simple, very simple idea.

Hope all of this helps,


The answer for your question How to improve with an implementation that would be based on saving computed values in an array? is to use memoization (sometimes known as dynamic programming), which incidentally is the same as saving computed values. But this is a somewhat odd solution to the problem. A better solution is computing the binomial coefficient according to the formula and recursion in vonbrand's comment, and use exponentiation to complete the calculation.

For completeness, here are the formula and the recursion:
$$
\binom{n}{k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots (1)}, \qquad \binom{n}{k+1} = \frac{n-k}{k+1} \binom{n}{k}.
$$

There are many ways to use memoization here. One natural way is to loop on n, and compute all values of binomial1 in sequence. This only requires knowing the values of binomial1 on n-1, which you save in an array. (Similarly you store the new values in a second array.) As an optimization, you only need to compute these values up to the given k.

I'll let you come up with matching code and runtime analysis.


Finding a local peak in an array in O(log N)?

No, it is not possible to find the max (peak) element in an unsorted array better than $\mathcal{O}(n)$.

When you executed your algorithm $\mathcal{A}$ that has $c \log n$ compare operations, that means; $\mathcal{A}$ only compared $c \log n$ elements. The remaining are not compared by $\mathcal{A}$.

We can easily construct an adversary argument for any $\mathcal{O}(\log n)$ algorithm by just placing the peak, within the elements for $\mathcal{A}$ didn't touch.


Using Headpose Vector and 2D Points to Compute Distances

You don't have enough information to calculate 3D points for anything--all your information is relative right now. You need something that establishes a measurement, and some way to determine depth. If you know how far a point is from the camera (or can estimate it), then you can at least start calculating locations of features you know to be within the vertical plane containing that point. Or if you know how large a feature is, then you can calculate the sizes of features also assumed to be in the same vertical plane.
Alternatively, if you can use information from other frames, then you can assume a rigid model for certain facial features and begin to make estimates, but it's still all scale-free until you can pin down a distance somewhere.


Situations where Kleene star of A is context-free, but A is not

Let $L$ be any non-context-free language, then we can construct the language $A = \Sigma\cup L$ - i.e. $A$ is either an element of $\Sigma$ or a string from $L$ (these can happily overlap too). This is clearly not context free either (if it were, then we would have a PDA for  it, and we can easily modify this PDA to recognise $L$).

If we now take $A^{\ast}$ however, we get $\Sigma^{\ast}$, which is most certainly context free.


how to calculate $2^{5000}$ mod 10 without calculator in fast way?

Consider the first few powers of 2:

  1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024…

Now take all of those mod 10:

  1, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4…

Try to solve it yourself, from this, before continuing to read.

There's a theorem that says, if $x \times y \cong z \mod m$, then $x' \times y \cong z \mod m$, for any $x' \cong x \mod m$. This means that, if you ever find two powers of two that are congruent (mod 10), the values in between them will form a cycle that loops forever. And it'll always be possible to find such congruent powers, so there'll always be such a cycle with ten or fewer elements in it. (All three of these statements can and should be proven, but those proofs are left as an exercise for the reader.)

In this case, the first such pair of values are 2 and 32. In other words, $2^5 \cong 2^1 \mod 10$. Which means that $2^6 \cong 2^2 \mod 10$, and $2^7 \cong 2^3 \mod 10$, and so on. In general, $2^x \cong 2^y \mod 10$ iff $x \cong y \mod 4$ (for integers $x, y \geq 1$).

So all you have to do now is reduce 5000 mod 4; since we know that $100 \cong 0 \mod 4$, 5000 must also be congruent to zero (and, more relevantly, to four, since our formula only holds for integers ≥ 1—do you see why?). Therefore, $2^{5000} \cong 2^4 \mod 10$. Now you just need to know the first few powers of two, or multiply them out longhand, to find that the answer is $2^{5000} \cong 2^4 \cong 6$.


How does augmenting linear bounded automata tape alphabets increase memory?

If you consider an input, hence a tape, of size $n$ and a tape alphabet of
$b$ symbols, you get $b^n$ configurations possible on your tape. If
you measure memory in bits, the memory size is the base 2 logarithm of
the number of configurations, very simply because that is the number
of bits required to have the same number of configurations (rounding up
to the next integer, because half-bits have not been invented yet).

So the tape memory of your linear bounded automaton (LBA) is $\log_2
b^n$, which is equal to $n\log_2 b$.

Augmenting your tape alphabet does not increase your memory very
fast. Doubling the size of the alphabet is equivalent to a single extra bit per cell, i.e. adding $n$ bits total. The
positive side of it is that it does not take many bits per cell of the
tape to have a huge alphabet.


Meaning of ⟨_⟩ in the context of verifiers

Any reasonable definition would do (I'll provide a formal definition later on). One simple definition, when $w,c$ are strings over some alphabet $\Sigma$ which doesn't contain the space character, is that $\langle w,c \rangle$ consists of $w$, a space, and $c$.

More generally, suppose that $\langle w,c \rangle_1$ and $\langle w,c \rangle_2$ are two definitions of the pairing function such that:

There exists a polytime function $f$ such that $f(\langle w,c \rangle_1) = \langle w,c \rangle_2$.
There exists a polytime function $g$ such that $g(\langle w,c \rangle_2) = \langle w,c \rangle_1$.

Then if we define NP using $\langle,\rangle_1$ and $\langle,\rangle_2$ we obtain the same class. A reasonable definition is one that satisfies (1) and (2) for the pairing function I described above.

This sort of situation happens often in complexity theory. When the details of the input representation don't make a difference, we don't bother specifying them exactly. That's because we never actually refer to these details, so they are "too much information". You only need to worry about such details when you're actually programming, or when you're dealing with very weak complexity classes, for which converting between different input representations can be difficult.


Your problem appears to be a special case of integer programming where the variables are boolean. I could not find it on wikipedia, but a lot of course materials online introduce this problem as Capital Budgeting problem under different models of integer programming. Hope it helps.


How to transpile generic functions into language that do not support generics?

When compiling to a target language without generics, there are two main strategies.

Monomorphization: if you have a generic function, and it's instantiated with types $T_1\ldots T_n$ throughout your program, you make $n$ copies of the function, with the concrete type replacing the generic variable. This tends to result in fast but large code, since there's lots of duplication.
Boxing: you can "box" the generic variables behind some sort of reference type, and cast to and from this type when entering and exiting your generic function. The guarantees of the source language ensure that these casts are always safe. For example, in C you probably want to use void*.

If you're looking for resources, generics are known as "parametric polymorphism" in the Programming Languages literature, so that might help your search.

If you're compiling from a Java-like OO language, you'll also need to attach a VTable to your objects: a table of pointers to their methods, you get Java's dynamic dispatch (i.e. the method of an object depends only on its runtime type, not it's compile-time type).

Having "bounded polymorphism" with option 2 (i.e. the T extends Comparable<T>makes this a little more tricky, since you need to come up with some sort of boxed representation that lets you find your Comparable methods. You could do a dynamic lookup to find such methods, but this is slow. I'd search around for how to compile bounded polymorphism, you'll probably find a better answer.


Modify DFA/NFA that accepts Language Subset with only Palindromes (with Size Limit)?

For DFAs, the size of $D_2$ is always at most $O(P_1|\Sigma|^{P_1/2})$, and this bound is tight up to the $P_1$ factor. For the lower bound, take a DFA for $\Sigma^*$ having $P_1$ states (you haven't specified that $D_1$ is minimal). The DFA $D_2$ accepts all palindromes of length $P_1$, and so Nerode's theorem shows that for even $P_1$, the optimal DFA $D_2$ contains $\Theta(|\Sigma|^{P_1/2})$ states. The upper bound now follows by using the product construction.

The exact same reasoning works for NFAs as well, although you need to replace Nerode's theorem with a suitable "exchange lemma" in order to show that any NFA for the language of all palindromes of length $P_1$ requires $\Omega(|\Sigma|^{P_1/2})$ states (for even $P_1$).

If you insist on $D_1$ being minimal as well, then instead of a DFA for $\Sigma^*$ take a DFA for $(\Sigma^{P_1})^*$, to get the exact same results. This construction works also for NFAs.


Is the following problem decidable in polynomial time?

This is a nice exercise, such as one might find in an undergrad-level algorithms class.  (Congratulate your professor on selecting such a nice exercise.)  Since it's your exercise, I'm going to let you solve it, but I'll give you a series of hints.

Important: Spend at least an hour exploring each hint, before moving on to the next hint.

Hint #1:

  When given an algorithms problem, it is often very helpful to look at some small examples and work out what's going on by hand.

  So, pick a sample problem instance with 3 items (generate the $x_i,y_i$'s arbitrarily); map out all possible timelines (all possible sequences of item removals); and see what you see.  Do another example with 3 items.  Try one with 4 items.  Do a few such examples, and see if you can build some intuition.  I suspect you'll spot what is going on, and then from that you might be able to figure out how to solve the problem.

Hint #2:

   What chapter of the textbook are you currently in?  This is often a good heuristic to help you select a type of algorithm to try.

Hint #3:

   A natural algorithmic approach is to use a greedy algorithm: if multiple items are currently eligible for removal, select the item whose $y_i$ value is _____.  (You fill in the blank.)  So, see if you can determine whether you can find any way to fill in the blank that provides a correct algorithm for your problem.  This gives you a few candidate algorithms; for each candidate, see if you can prove or disprove its correctness.  To do that, try some small examples.  See if you can find a proof of correctness or a counterexample demonstrating it is incorrect.  Once you've worked out whether there is any algorithm of this form that is correct, you should be able to answer your question.

Hint #4:

   If you've tried all of the above diligently, show us your work and where you got stuck and I'll give you one more hint.


Expected number of iterations for bozo sort opt algorithm

The bounds in that paper can be tightened. The tighter bounds in lemma 14 are "..." at most $O(n\log n)$ (resp. $O(n^2\log n))$.

As in the question and the papers, we will fix a set of $n$ elements that are totally ordered. The array $a=(a_1, a_2, \cdots, a_n)$ will be a permutation of the $n$ elements. A pair of element $\{a_i, a_j\}$ is a good pair if $i\lt j$ and $a[i]\lt a[j]$. It is a bad pair if $i\lt j$ and $a[i]\gt a[j]$. A bad pair is also call an inversion.
Fact on inversion. Swapping a bad pair strictly decreases the number of all inversions. An array is sorted if and only if the number of all inversions is 0. The maximum number of all inversions is the same as the numbers of all pairs, $\binom n2$.
Now we will use the fact above to show the tightened version of lemma 14 for one case.
The expected number of comparisons carried out by bozo-sort$_{\text{opt}}$ on a worst-case input $x$ of length $n$ is at most $4n^2\log n + (n-1)$, where $\log$ is the natural logarithm.

Proof: Suppose there are $m$ bad pairs in the array. A run of procedure rand. transpose hit one with probability $p = m/n^2$, so the expected number of runs of that procedure until we hit a bad pair is $1/p=n^2/m$. Since the number of bad pairs decreases each time we swap a bad pair, the expected number of runs of  that procedure until the array is sorted is bounded by
$$\sum_{m=1}^{\binom n2}\frac{n^2}m=n^2\sum_{m=1}^{\binom n2}\frac1m\le 2n^2\log n$$
Note that each procedure rand. transpose makes one comparison. The effect of running procedure sorted before every $n-1$ procedure rand. transpose will at most double number of comparisons besides the initial $n-1$ comparisons. Q.E.D.
The above proof is adapted from Fun sort or the chaos of unordered binary search by T. Biedl, T. Chan, E. D. Demaine, R. Fleischer, M. Golin, J.A. King, and J. I. Munro. Discrete Applied Mathematics, 144(3):231–236, 2004.
Exercises
Exercise 1. Show that $\sum_{m=1}^{\binom n2}\frac1m\le 2\log n.$ (Hint, here is the rate of divergence of harmonic series).
Exercise 2. (One minute or less.) Show that ${m}/\binom n2$ is the probability of procedure rand. transpose in bozo-sort$^+_{\text{opt}}$ hitting one bad pair when there are $m$ bad pairs.
Exercise 3. Show that the expected number of bad pairs found (and, swapped) by a call to procedure randomly permute in bogo-sort$_{\text{opt}}$ when there are $m$ bad pairs is $\Theta(m(n-1)/n^2)$. Show the expected number of total comparisons until the array is sorted is at most by $\Theta(n^2\log n)$.


Hint: Here are a few easier languages to practice on:

Every occurrence of the symbol $a$ is followed by a non-$a$ symbol. (Hint: every $a$ occurs in the context of $ab$ or $ac$.)
No occurrence of the symbol $a$ is followed by another $a$. (The only difference from 1 is that a word could end with $a$.)
Every occurrence of the symbol $a$ is followed by a non-$b$ symbol. (Hint: what are the possible contexts of $a$?)
Your language. (Combine the answers to 3 and 2.)


You can't match 1+2*3+4 with expr * num because 3+4 isn't a num. The only possible match is expr + num, with 1+2*3 as the expr and 4 as the num. To make 1+2*3 an expr, you need to match it with expr * num, and then you can match 1+2 with expr + num. Finally, you can match 1 with num to make the innermost expr.

So the only possible parse is ((((1)+2)*3)+4) and the grammar is not ambiguous.

It is not the grammar we usually use for algebra because it produces an undesired parse, not because it is ambiguous.


The importance of normal forms like Chomsky normal form for CFGs

There are at least two relevant uses.

Simplicity of proofs
There are plenty of proofs around context-free grammars, including reducability and equivalence to automata. Those are the simpler the more restricted the set of grammars you have to deal with is. Therefore, normal forms can be helpful there.

As a concrete example, Greibach normal form is used to show (constructively) that there is an $\varepsilon$-transition-free PDA for every CFL (that does not contain $\varepsilon$).
Enables parsing
While PDAs can be used to parse words with any grammar, this is often inconvenient. Normal forms can give us more structure to work with, resulting in easier parsing algorithms.

As a concrete example, the CYK algorithm uses Chomsky normal form. Greibach normal form, on the other hand, enables recursive-descent parsing; even though backtracking may be necessary, space complexity is linear.


This cannot be true, since you could use such an algorithm to solve SAT itself in polynomial time. Given a SAT instance $\varphi$, construct a much larger instance $\psi$ which contains $\varphi$ as well as many copies of the clause $x$, where $x$ is a new variable not appearing in $\varphi$. It is easy to find an assignment satisfying almost all clauses of $\psi$. Now run your algorithm. If it succeeds, then $\varphi$ is satisfiable; and moreover, if $\varphi$ is satisfiable then it should, indeed, succeed. Thus $\varphi$ is satisfiable iff your algorithm finds a satisfying assignment within the promised running time.

Perhaps the participant meant an assignment which is close to a satisfying assignment, as in Schöning's kSAT algorithm; see for example Eppstein's lecture notes.


Are linear languages always unambiguous?

The linear language $\{ a^ib^jc^k \mid i=j \text{ or } j=k\}$ is inherently ambiguous.


Order preserving encoding of strings to numbers

(I assume that by lexicographic order, you mean lexicographic order. Phone books may have all kinds of oddities due to ordering proper names, such as sorting McDonald near MacDonald.)

Suppose your strings only contained the characters 1, 2, 3, 4, 5, 6, 7, 8 and 9. The mapping from the string $s$ to the decimal number 0.$\!\!s$ is monotonic.

If you have $n$ characters in your alphabet, use base $n+1$.

This encoding accommodates infinite strings too, but you need to use base $n+2$ and skip the largest digit as well as the smallest digit (the largest string beginning with 1 is 1888… $\mapsto 0.1888\ldots$ which is smaller than 2 $\mapsto 0.2 = 0.1999\ldots$).


Why increasing the beam width does not necessarily improve the beam search solution?

Imagine your tree looks as follows:

You are looking for the leaf with minimum label and the label of each internal nodes represents the heuristic value associated with the subtree routed at that node.

If the width of your beam is just $1$, you start at the root and then go $\rightarrow 5\rightarrow7\rightarrow0$.

If the width of your beam is $2$, you first take $[5,6]$ as potential candidates. Look at $5's$ children, so your best candidates at that point for the next level are $[7,8]$. Look at $6's$ children, both better candidates, so your potential candidates become $[3,4]$. Then you'll find only $9$'s going down, which is worse than the solution found with a beam width of $1$.

But if your heuristic is well behaved enough, you might be able to guarantee that increasing the beam width can not degrade the quality of the solution that is found.


Learning parameters of noise and filter coefficients from data where data and noise both have Gaussian distributions

Your problem is that of multivariate linear regression. Finding each row of $A$ corresponds to a classical linear regression problem, which can be solved using the method of least squares, which is optimal here since the noise is Gaussian.

Once you have an estimate for $A$, you can estimate the parameters of $N$ by isolating $N = Y-AX$. (This is not necessarily the optimal method since you only have an estimate for $A$, but practically it might be good enough.)


Since $P \subseteq NP$, every problem in $P$ is also in $NP$. So in both cases there is an $NP$-problem that can be reduced to a $P$-problem. Simply choose a problem in $P$ as the $NP$-problem and the same problem as the $P$-problem.

If you replace $NP$-problem by $NP$-complete problem, both of your statements hold.


Decidability of $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$

We also know that $L(G)=L(H)$ iff both $L(G)\subseteq L(H)$ and $L(H)\subseteq L(G)$.

Now assume $SEQ_{CFG}$ is decidable, then we can decide both ...


How do we know that the reduction is correct?

Your first question is easy to answer: you are confusing "we know" with "it is the case". It can happen that something is the case but we do not know it. In particular, it is the case that $M\#x$ halts or it does not halt, but we do not know which. It will rain a year from now or not, but we do not know which.

To answer the second question, let us see what goes wrong if we try to reduce the Halting Problem to a decidable problem. Consider the problem:

  Given a single-tape Turing machine $M$ and input $x$, decide whether $M\#x$ halts in fewer than $\mathrm{length}(x)$ steps.

Now we need to come up with a reduction, i.e., given any machine $M$ and input $x$, we must produce a machine $M'$ and input $x'$, such that
$$\text{$M$ halts on $x$} \iff \text{$M'\#x'$ halts in fewer than $\mathrm{length}(x')$ steps}$$
Here is an idea: let $x'$ be the pair $(x, 0^k)$ where $0^k$ is a a string of $k$ zeroes, where we are going to determine $k$ later (this trick is know as "padding the input"). The machine $M'$ takes this input $(x, 0^k)$, ignores $0^k$ and just does whatever $M\#x$ would do. Now, for this reduction to work, we just need $k$ such that
$$\text{$M\#x$ halts} \iff \text{$M'\#(x,0^k)$ takes fewer than $\mathrm{length}(x,0^k)$ steps of execution}$$
Such a $k$ exists because $M\#x$ halts if, and only if, $M'\#(x,0^k)$ halts. So there are two cases:

If $M\#x$ halts then so does $M'\#(x,0^k)$ in some number of steps, say $m$, and we can take $k = m + 1$.
If $M\#x$ does not halt then we can take any $k$.

There is a small technical issue: the number $m$ should not depend on $k$. We can arrange this in several ways. One possibility is to allow $M'$ to have an extra symbol which it uses as "ignore input from here onwards". In any case, this is not essential for the discussion at hand.

Can you spot the problem? A reduction needs to be computable, that is, we need a computable procedure which generates $M'$ and $x'$ from $M$ and $x$. We have not given a procedure for computing $k$, even though such a $k$ exists. Perhaps if we think harder we can come up with the required procedure for computing $k$. Or perhaps it does not exist, and our attempt is not worth anything. We just do not know.

So, this is one way in which an attempt at a reduction may fail. It is in fact typical: if we are allowed to use non-computable reductions, then we can reduce any problem to any other non-trivial problem. I leave it as an exercise. (Here "non-trivial" means that the problem has an instance where the answer is "yes" and an instance where the answer is "no".)


As we are talking about IPv4 addresses here, you have to consider two things:

Usually, your Internet Service Provider (ISP) will assign you one IPv4 address. This can either be changing (the common case for private households) or static. However, there is usually one IP address at a time that you can be reached from the outside of your network.
Internally, you can organize your network independent from those policy. For this purpose, some standard IP ranges like 192.168.*.* and 10.*.*.* are reserved to be used arbitrarily by the local network administrator.

Hence, it is up to the network administrator how the additional department is included in the school's local address space.

Generally, you want to talk of different loosely coupled networks in terms of subnets. To determine a certain subnet, you specify a subnet mask, which fixes the first $n$ bits of an IP address as "the network's address".

So, the admin would assign the additional department a "network address" of, e.g., 10.0.54.0/24. This means, the first 24 bits of this IP identify the network and everything after the 24th bit can be assigned arbitrarily to the devices of that network. In this particular example, any device with an IP address between 10.0.54.1 and 10.0.54.254 would be logically seen as part of the network 10.0.54.0/24.

Assuming that the whole school is connected to some kind of router (which uses NAT to "translate" the local IP addresses to the global IP address assigned by the ISP, roughly speaking), it is then up to the router configuration whether the department is reachable directly. This router will most likely run a web server or delegate http requests to a device of the network that runs a web server. Based on the configuration of this delegation or request processing, you can instruct the router to delegate any request to, e.g., department.myschool.com to the web server of the department and then you are fine.

However, you have to have a top level domain for this, even with a wildcard contract such that every request to *.myschool.com is forwarded to your school's router, that then can decide to forward requests to department.myschool.com accordingly.
Another way to have this flexibility would to use different ports for different web servers in your local network. But this would burden anyone who is interested in your department's website to guess or somehow know the port your web server is listening to.


Finding pairs of numbers in array whose reciprocals sum to 1

Assume that $a$ is given. Then a valid $b$ has to satisfy (just rearrange the inequality) :

$$b > \frac{a}{a - 1}$$

Notice, if the array is sorted, then you can find the number of valid $b$ using binary search, which gives $O(n \log n)$ to compute the number of all pairs.

Also notice, that if $a$ gets bigger, then $b$ is allowed to be smaller. So if you you iterate over $a$ in sorted order, and keep a pointer (to indicate the allowed elements for $b$), you don't need to use binary search and can compute the result in $O(n)$.


What is this operator in "The Temporal Logic of Programs" Pnueli 1977?

It's implication as indicated in en.wikipedia.org/wiki/List_of_mathematical_symbols


Convex hull algorithm in $O(\min(mn, n\log n))$

The simplest solution is to run two algorithms in parallel, one which runs in time $O(mn)$, and one which runs in time $O(n\log n)$. When one of the algorithms outputs a solution, you stop the other one. This runs in time $O(\min(mn,n\log n))$.

In fact, you can do better – Wikipedia lists several $O(n\log m)$ algorithms, which is strictly better than the guarantee you are looking for.


What is the difference between classical crypto and post-quantum crypto?

Summary of this paper providing a (partial) answer.

There are two kinds of traditional public-key cryptographic methods: those based on integer factorization, and those based on the discrete logarithm, including elliptic-curve-based methods. These models are believed to be hard in the classical models, but have been shown that neither is hard in the quantum model.

Although Grover developed a quantum algorithm providing quadratic speedup for searching, Bennet, Bernstein, Brassard and Vazirani showed that the quantum model couldn't allow exponential speedup for search problems. This suggests symmetric encryption algorithms, one-way functions and cryptographic hashes should resist quantum-based attacks. The focus, then, should be on developing secure public-key methods.

Lamport signatures may provide a one-time signature mechanism secure against quantum attacks. Lattice problems may form the basis for public-key methods which are resistant to quantum attacks; in particular, the NP-Hard shortest-vector and closest-vector problems are attractive. For both the classical and quantum models, these problems are believed to be hard for lattices of high dimension. The NTRU family of cryptographic algorithms, based on lattice problems, may provide a practical means of achieving public-key cryptography resistant to quantum attacks. Another problem which might serve as a basis for secure public key methods is the syndrome decoding problem. The McEliece encryption system is based on this problem, and variants may provide a way forward.


Assuming that by framebuffer they really mean palette table, then the table consists of 256 entries, each encoding an RGB color ("true color"). An RGB color takes 24 bits (3 bytes), 8 bits per color component, so in total we need 256$\times$3=768 bytes. That said, it may be easier to access the table if each color takes up an entire dword (32 bits, 4 bytes): for example, indexing could be for free in certain processors. In that case the table would take up 256$\times$4=1024 bytes. However, given the data at your disposal, the best guess would be 768 bytes.

Palette tables are most celebrated for their use in the popular GIF format. GIF uses a color palette consisting of 256 colors (in its most popular version), one possibly being reserved for "transparent", and the colors themselves are stored separately, usually as "true color" 24-bit values. The color table indeed uses 3 bytes per color, for a total of 768 bytes.


Pumping lemma on {a^n | n=3^k} — help finishing the proof

It is not enough. Also note that you didn't define $x$ correctly, and forgot $z$.
I would define:
$$x = a^s$$
$$y = a^t$$
$$z = a^{3^m - s -t}$$
such that
$s + t <= m$ and $t >= 1$ (hence $1 <= t <= m$)

You need to show that for $i=2$, you get something that is not in L (meaning, there is no $k$ such that $x(y^2)z = a^{3^k}$ ).

Let's look at $x(y^2)z = a^{3^m+t}$.
Its length is $3^m + t$.

Using the fact that for every $i, i < 3^i$, We get:
$3^m < 3^m + 1 \le |x(y^2)z| = 3^m + t \le 3^m + m < 3^m + 3^m = 3^{m+1}$

We see that the length of $xy^2z$ isn't in the form of $3^n$ (it's something between $3^m$ to $3^{m+1}$, hence it is not in L.
Contradiction to the pumping lemma.


How does an inverted index reduce storage requirements?

I think the author meant that by separating the index into the "dictionary" part and the "postings" part, we reduce the storage requirements of the strings themselves, because now we only have to store one string for each unique word. It's as if you are storing the vocabulary of the language itself, independent from the documents. It is also mentioned later that the dictionary is usually kept in memory, so it is important to make sure it doesn't take up much space.


Recurrence $f(n+1)=2f(n)-f(n-1)$ with initial values $f(0)=0,f(1)=1$

The normal recipe for solving a recurrence of this form goes like this:

Determine the polynomial corresponding to the recurrence, in your case $x^2 - 2x + 1$.
Determine the roots of the polynomial, in your case $x = 1$ (double root).
The solution is a linear combination of $1^n$ and $n1^n$ (more generally, if the roots are $\lambda_1,\ldots,\lambda_r$ with multiplicities $m_1,\ldots,m_r$, then you get a linear combination of $\lambda_1,\ldots,n^{m_1-1} \lambda_1,\ldots,\lambda_r,\ldots,n^{m_r-1}\lambda_r$).
Find the coefficients using the initial conditions. In your case, the general solution is $A + Bn$. Since $f(0) = 0$, we have $A = 0$, and since $f(1) = 1$, we have $A + B = 1$, hence $B = 1$. Thus the solution is $0 + 1 \cdot n = n$.

Here are two more equivalent ways to solve this.
Matrices. Notice that
$$
\begin{pmatrix} 2 & -1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} f(n) \\ f(n-1) \end{pmatrix} =
\begin{pmatrix} f(n+1) \\ f(n) \end{pmatrix}.
$$
It follows that
$$
\begin{pmatrix} f(n+1) \\ f(n) \end{pmatrix} = \begin{pmatrix} 2 & -1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}.
$$
The characteristic polynomial of the matrix is
$$
\det \begin{pmatrix} t-2 & 1 \\ -1 & t \end{pmatrix} = (t-2)t+1 = (t-1)^2,
$$
hence there is a single eigenvalue with multiplicity $2$. To determine the Jordan form of this matrix, which we denote by $A$, notice that
$$
\begin{pmatrix} 2 & -1 \\ 1 & 0 \end{pmatrix} - I = \begin{pmatrix} 1 & -1 \\ 1 & -1 \end{pmatrix}
$$
has rank $1$, and so the Jordan form of $A$ is
$$
\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}.
$$
The above shows that one eigenvector of $A$ is $v = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$. A generalized eigenvector of the matrix is a vector $u$ such $(A-I)u = w$, for example $u = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$. It follows that
$$
\begin{pmatrix} 2 & -1 \\ 1& 0 \end{pmatrix} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{-1} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}
\begin{pmatrix} 0 & 1 \\ 1 & -1 \end{pmatrix}.
$$
It follows that
$$
\begin{pmatrix} f(n+1) \\ f(n) \end{pmatrix} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^n
\begin{pmatrix} 0 & 1 \\ 1 & -1 \end{pmatrix}
\begin{pmatrix} 1 \\ 0 \end{pmatrix} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}
\begin{pmatrix} 0 \\ 1 \end{pmatrix} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} n \\ 1 \end{pmatrix} =
\begin{pmatrix} n+1 \\ n \end{pmatrix}.
$$
In particular, $f(n) = n$.
Generating functions. Let $P(x) = \sum_{n=0}^\infty f(n) x^n$. Then
\begin{align}
P(x) &= x + \sum_{n=2}^\infty f(n) x^n \\&=
x + \sum_{n=2}^\infty [2f(n-1)-f(n-2)] x^n \\ &=
x + 2x\sum_{n=1}^\infty f(n) x^n - x^2 \sum_{n=0}^\infty f(n) x^n \\ &=
x + (2x-x^2) P(x).
\end{align}
It follows that
$$
P(x) = \frac{x}{1-2x+x^2} = \frac{x}{(1-x)^2} = x \sum_{n=0}^\infty \binom{n+1}{1} x^n = \sum_{n=0}^\infty n x^n.
$$
Therefore $f(n) = n$.


Real world applications for Steiner Tree Problem?

I am currently writing my PhD proposal, which is about finding ways to apply theory from parameterized complexity, primarily tree decompositions, to realistic network optimization problems. But I mainly plan to work with Steiner Tree, not in the last place because its simple and there are a lot of papers/benchmarks available.

Stumbled on this question because I too have some trouble finding practical motivations for studying it. I think its practical relevance is more easily motivated by the enormous amount of optimization problems that are generalizations of the vanilla STP but are more flexible. There is a nice list here: http://theory.cs.uni-bonn.de/info5/steinerkompendium/netcompendium.pdf

I think some of the problems mentioned with phylogenetic trees can be directly formulated as STP but I haven't read the papers thoroughly.

This algorithm for connected facility location and single source rent-or-buy is also interesting: http://sma.epfl.ch/~eisenbra/Publications/jcss08cfl_final.pdf
Though not directly modeled as an STP, solutions to these problems have a core that is a Steiner Tree and the algorithm makes use of a STP approximation algo directly to solve that part.

Also regarding heuristics for the STP you might be interested in this page: http://dimacs11.cs.princeton.edu/workshop.html
There are quite a few new competitive algorithms that have been presented there.

Edit: You might also want to take a look at this book by William Cook:

In Pursuit of the Traveling Salesman

It is about the TSP, but that one is similarly theoretical. Chapter 3 contains really a load of concrete practical uses, not just the trivial tour finding stuff, but unexpected problems that can be solved by solving a TSP, including some biology problems as I mentioned. Part of the reason of the applicability seems to be the fact that there is a very powerful and accessible TSP solver out there, making it convenient to rephrase design problems as TSP's. I found it really inspiring as the same type of applications could be found for the STP I think (but there is no 'industry standard' solver for it so it doesn't happen in reality).  Some of the chapter is free on Google books, though I recommend getting you hands on the full version cause some of the best examples are left out.


Why are all problems in FPTAS also in FPT?

There is actually a stronger result; A problem is in the class $\mathrm{FPTAS}$ if it has an fptas1: an $\varepsilon$-approximation running in time bounded by $(n+\frac{1}{\varepsilon})^{\mathcal{O}(1)}$ (i.e. polynomial in both the size and the approximation factor). There's a more general class $\mathrm{EPTAS}$ which relaxes the time bound to $f(\frac{1}{\varepsilon})\cdot n^{\mathcal{O}(1)}$ - essentially an $\mathrm{FPT}$-like running time with respect to the approximation factor.

Clearly $\mathrm{FPTAS}$ is a subset of $\mathrm{EPTAS}$, and it turns out that $\mathrm{EPTAS}$ is a subset of $\mathrm{FPT}$ in the following sense:

  Theorem If an NPO problem $\Pi$ has an eptas, then $\Pi$ parameterized by the cost of the solution is fixed-parameter tractable.

The theorem and proof is given in Flum & Grohe [1] as Theorem 1.32 (pp. 23-24), and they attribute it to Bazgan [2], which puts it two years before Cai & Chen's weaker result (but in a French technical report).

I'll give a sketch of the proof, because I think it's a nice proof of the theorem. For simplicity I'll do the minimization version, just mentally do the appropriate inversions for maximization.

Proof. Let $A$ be the eptas for $\Pi$, then we can construct a parameterized algorithm $A'$ for $\Pi$ parameterized by the solution cost $k$ as follows: given input $(x,k)$, we run $A$ on input $x$ where we set $\varepsilon := \frac{1}{k+1}$ (i.e. we choose the approximation ratio bound $1+\frac{1}{k+1}$). Let $y$ be the solution, $\text{cost}(x,y)$ be the cost of $y$ and $r(x,y)$ be the actual approximation ratio of $y$ to $\text{opt}(x)$, i.e. $\text{cost}(x,y) = r(x,y)\cdot \text{opt}(x)$.

If $\text{cost}(x,y) \leq k$, then accept, as clearly $\text{opt}(x) \leq \text{cost}(x,y) \leq k$. If $\text{cost}(x,y) > k$, reject as $r(x,y) \leq 1+\frac{1}{k+1}$ as $A$ is an eptas and

$$
\text{opt}(x) = \frac{\text{cost}(x,y)}{r(x,y)} \geq \frac{k+1}{1+\frac{1}{k+1}} > k
$$

Of course you get the running time bound for $A'$ simply from $A$ being an eptas. $\Box$

Of course as Pål points out, parameterized hardness results imply the non-existence of any eptas unless there is some collapse, but there are problems in $\mathrm{FPT}$ with no eptas (or even ptas), so $\mathrm{EPTAS}$ is a strict subset of $\mathrm{FPT}$ (in the sense of the theorem).

Footnotes:

An fptas (equivalently eptas or ptas) is an approximation scheme with the running time bounded as described above. The class $\mathrm{FPTAS}$ (equiv. $\mathrm{EPTAS}$, $\mathrm{PTAS}$) is the set of problems in $\mathrm{NPO}$ that have such a scheme.

[1]: J. Flum and M. Grohe, Parameterized Complexity Theory, Springer, 2006.
[2]: C. Bazgan. Schémas d’approximation et complexité paramétrée, Rapport de
DEA, Université Paris Sud, 1995.


The rules for traversing a tree are, to visit all nodes of a tree you do this:

Preorder: (1) visit the root node, then (2) visit all the nodes in the left subtree of the root, then (3) visit all the nodes in the right subtree of the root. In steps (2) and (3), use the same rule as above.
Inorder: (1) visit all the nodes in the left subtree, (2) visit the root node, (3) visit all the nodes in the right subtree.
Postorder: (1) visit all the nodes in the left subtree, (2) visit all the nodes in the right subtree, (3) visit the root.

For example, to do an inorder traversal of your tree,

Visit the nodes, $(12, 25)$, in the left subtree.
Visit the root, $31$.
Visit the node in the right subtree, $(68,50,72,39,56,42,53,60)$

In step (1) we use the same rule: visit the left subtree of 12 (nothing there), then the root, 12, then the right subtree $(25)$. So now you've done task (1), having visited the nodes $12, 25$ in that order.

In step (2) we visit $(31)$, so now we've visited $12,25, 31$.

In step (3) we need to visit the nodes in the right subtree, using the rule Left-Root-Right, as we did before. It turns out that we'll visit the right subtree's nodes in order 39,42,50,53,56,60,72.

Doing this traversal by hand is complicated and prone to error. While computers are easily able to use these recursive rules, humans aren't so good at this. Fortunately, there's a three-step technique that's easy for people to apply.

Draw an upward-pointing triangle around each node in your tree.
"Shrink-wrap" the whole tree by drawing a closed circuit around the whole tree, making your circuit follow the tree as closely as possible, like this:

Starting at the root node, trace the circuit counter-clockwise, listing a node as visited when: for a preorder traversal, you encounter the node for the first time (that is, when you travel along the left side of the node's triangle); for an inorder traversal, mark the node as visited when you encounter the node for the second time (that is, when you travel around the base of the node's triangle); for a postorder traversal, mark the node as visited when you encounter it for the last time (when you travel along the right side of the node's triangle).

Try it for your tree and each of the three traversals and you'll see what happens.


Undecidable unary languages (also known as Tally languages)

Note that $\{1\}^*$ is isomorphic to $\Bbb N$. There are uncountably many subsets of both $\{1\}^*$ and $\Bbb N$.

Perhaps you are confused with the fact that there are only countably many finite subsets of $\{1\}^*$ (and $\Bbb N$).


What does it mean for a function $f\colon M → N$ between *any* sets $M, N$ to be computable?

One convention is as follows. Your sets $\mathbb{N}$ and $M$ come with (injective) encodings as strings. In that way, you can think of $\mathbb{N}$ and $M$ simply as subsets of $\Sigma^*$.

One can think of many other equivalent conventions. For example, you can treat the input as a bona fide natural number, and use the C programming language rather than the string-based Turing machine. All reasonable definitions will result in the same notion of computable function.

In terms of computational complexity, the exact encoding (or other convention) used can be important. For example, graphs can be encoded either using adjacency matrices or as adjacency lists, and this can affect the complexity of algorithms operation on them.


Determine whether a TM visits each of its states exactly once during computation

Hint: If a Turing machine has $m$ states and it visits each of them exactly once, then it terminates after $m$ steps.


Modified Max Product dynamic solution very inefficient

Why do you split it in the middle? Multiplication is associative so you don't have to do that. Considering only the last multiply sign would be fine.
Here's a simpler recursion: $T(1,j,a)=\max\{T(1,v,a-1)\times T(v+1,j,0)\}$. I use the same symbols as yours so you can see the difference. The first dimension is useless so the table is actually an $n \times k$ array. Each function call takes $O(n)$, so the complexity is $O(n^2k)$.


Are there undecidable properties of non-turing-complete automata?

Undecidable problems about context free grammars, and hence, pushdown acceptors as well, which are restricted TMs from Wikipedia...

Given a CFG, does it generate the language of all strings over the alphabet of terminal symbols used in its rules?
Given two CFGs, do they generate the same language?
Given two CFGs, can the first generate all strings that the second can generate?

There are many others about CFGs/PDAs as well as CSGs/LBAs and many other "simpler than TM" models.