Evaluation of reverse Polish notation We only consider the reverse Polish notation as an arithmetic expression.

Formally, RNP is a sequence consisted of numbers and arithmetic operators: $+,-,*,/$, and its syntax is:
$$\newcommand\RNF{\mathrm{RNF}}\newcommand\num{\mathrm{number}}\newcommand\op{\mathrm{operator}}\RNF=\num\,\big\vert\,\RNF,\RNF,\op$$
and its value
$$\newcommand\eval{\operatorname{eval}}\eval\num=\num$$
$$\eval\RNF_1,\RNF_2,\op=\eval\RNF_1\ \op\ \eval\RNF_2$$

The following pseudo code to evaluate $\eval\RNF$ is quoted from K&R:

while (next operator or operand isn't empty)
  if (it's a number)
    push it
  else if (it's an operator, say +,-,*,/)
    pop operands
    do operation
    push result

The algorithm is somewhat straightforward, but it's not as evident as considered. I found it difficult to formulate a loop invariant for the outer while-loop, and it's quite hard to prove the algorithm through Floyd-Hoare logic.

Through some search work, I found a related question, about the unambiguity of RPN. Unfortunately, I don't think the answer to that question is a rigorous proof.

How do you define the semantics of RPN? Ignoring the print commands, I would imagine a recursive definition that, given a sequence of operations, tells you what the state of the stack is like. From this definition it is straightforward to prove the correctness of the algorithm. In order to add prints, the recursive definition should also include the sequence of numbers printed. To add errors, the recursive definition should give either a pair as above or the error symbol.

Edit: Here is how you would formally define the semantics, which in the simplified case are a partial mapping from a sequence of operations to a sequence of numbers (the stack). It is only partial since sometimes arguments might be missing.

The function $F$ is defined as follows. First, $F(\lambda)=\lambda$, where $\lambda$ is the empty sequence. $F(\sigma,n) = F(\sigma),n$, where $\sigma$ is a sequence. If $F(\sigma) = \tau,a,b$ then $F(\sigma,+) = \tau,a+b$. If $|F(\sigma)| \leq 1$, then $F(\sigma,+)$ is undefined. Other arithmetic operations are handled in a similar fashion, only you need to make sure not to divide by zero.

Given the semantics, the proof of correctness is rather boring, and I'd rather not spell it out. The loop invariant is essentially the function $F$.


What Exactly is "Improvement" in Seed AI? From LessWrongWiki, a seed AI

  [I]mproves itself by recursively rewriting its own source code without human intervention.

Some would even say this could bring about an Intelligence Explosion. Many of these sources mention that it recursively "improves" itself. What exactly does that mean? How do you define "improve"?

Many people say that since it "improves" itself recursively, the jumps in intelligence would be ever-increasing. However, they also mention that an AI like this would have a goal; for example maximizing knowledge or maximizing human happiness. How would this translate into maximizing of the ability to maximize? You could also maximize for speed, let's say. How do you measure speed? A test, like the TSP? But then wouldn't the machine optimize specifically for solving the TSP, and nothing else? How would that translate into an increasing ability to optimize itself?

In other words, what would one maximize for in an implementation of Seed AI?

Improves itself by recursively rewriting its own source code without human intervention.

A machine learning technique that has some of the properties of a Seed AI is Meta Genetic Programming.

With Genetic Programming (GP) the system automatically writes code to solve a predefined task. GP evolves computer programs according to a natural evolution paradigm, using various operators and parameters.

Meta-GP allows simultaneous evolution of operators and parameters along with the population of programs.

Of course one can imagine multiple meta-levels in an evolutionary computation system: more levels of populations acting on each other and/or populations that act upon themselves.

It's worth noting that there can be a Free Lunch for Meta-GP / Hyper-Heuristics, but these techniques:

introduce extra computational cost, which have to be weighed against potential advantages;
seem very sensitive to biases in the syntax from which the operators are generated and thus less robust.

Anyway it's an open research field.

  How do you define "improve"?

Usually GP has an objective function (fitness function) to translate a desired behaviour.

Writing these fitness functions is a formidable task and it happens than your GP system optimizes for something other than it was intended for (may it happen for a Seed-AI-system?)

It's not clear if there is a way of doing without defining an objective function.

You can try to mimic Nature using a local, distributed, asynchronous form of competition or, according to the idea that "to achieve your highest goals, you must be willing to abandon them", applying Novelty Search,

but often fitness is still there (although behind the scene).


Does stay put TM recognizes same languages as standard TM I am reading this text book and it says that stay put turing machine recognizes the same languages as regular turing machine by just adding transition functions (without adding any new states or symbols). I am trying to figure that out.. But so far, no luck. I think the key here is "recognizes" rather than "decides"? How do i prove this? Thanks

No, the key terms are not "recognizes" and "decides", but rather "simulates". Given a Turing machine that can stay put, you can simulate it using a Turing machine that doesn't stay put. Given a transition of the form:

On state $s_1$, if the symbol under the head is $\alpha_1$ then change it to $\alpha_2$, stay put and transition to state $s_2$

you replace it with a pair of transitions

On state $s_1$, if the symbol under the head is $\alpha_1$ then change it to $\alpha_2$, move right and transition to $s'$
For every symbol $\beta$: On state $s'$, if the symbol under the head is $\beta$ then change it to $\beta$, move left and transition to state $s_2$

Here $s'$ is a new state that is used only to handle this transition.

The new Turing machine doesn't stay put but simulates the original Turing machine.

As the OP points out, we can actually improve this simulation by not adding new states at all (except for possibly one more state, a "stuck" state). Suppose we are at state $s_1$, see the symbol $\alpha_1$, and stay put. Let us continue to follow the machine. Either the machine never moves away from its spot, or it eventually moves either left or right, transitioning to state $s_2$ after changing the original symbol to $\alpha_2$. In the latter case, we can change the transition to a simple transition to $s_2$. In the former case, we can move instead to a special "stuck" state in which the Turing machine finds itself in an infinite loop; this state can be common for all "stuck" situations.

If we are guaranteed that the original Turing machine never gets stuck, and this is probably the assumption in your textbook, then we can do away with the "stuck" state, so that no new states are needed at all.


Is $\epsilon$ always contained in $\Sigma^*$? Please correct me on any terminology. For some reason I'm a bit confused.

$\Sigma = \{\epsilon, 0, 1\}$

This means my alphabet, $\Sigma$, contains three symbols ($\epsilon, 0, 1$).

$\Sigma^*$ is the language over $\Sigma$, and it equals $\{\epsilon, 0, 1, 01, 10\}$.

My regular expression for $\Sigma^*$: $\epsilon+0+1+(01)+(10)$.

First question: Does every $\Sigma^*$ include $\epsilon$? I see some with, and some without. I feel like this is a big difference because your regular expression and DFSA will be different.

Second question: At this point, I would have five accepting states in a DFSA? Since the first state is the empty string, is it $\epsilon$? Or is the first state just nothing, which transitions to a second state via $\epsilon$ which contains the empty string?

Normally, $\epsilon$ stands for the empty string: the string with no characters, which would be "" is most programming languages. It's too confusing to have $\epsilon$ be a symbol in the alphabet, so I'm going to rename it and write your alphabet as $\Sigma=\{e,0,1\}$. (The alternative would be to use some other symbol to denote the empty string.)

Now, by definition, $\Sigma^*$ is the set of all finite strings that can be written using the characters of $\Sigma$. This always includes the empty string $\epsilon$ and, as long as $\Sigma\neq\emptyset$, it also contains strings of all finite lengths. So the claim in the question that $\Sigma^*=\{e, 0, 1, 01, 10\}$ is incorrect: $\Sigma^*$ is an infinite set.

The regular expression for $\Sigma^*$ is $(e+0+1)^*$; the automaton consists of a single state, which is accepting and has transitions to itself for each symbol in $\Sigma$.


Key secrecy vs Algorithm secrecy it's a well known statement that

"Cryptographic security must rely on a secret key instead of a secret algorithm."

I would like to ask about some details about it. And which are their differences?

I see the obvious thing that for a multi user system, generating a key is overwhelmingly easier than generating a distinct alghorithm for every user pair, (and even for a single pair of users one could argue that updating the key is easier)

But, Is it the only argument?

I mean, if we define

AlgorithmA = AlgorithmX + key A
AlgorithmB = AlgorithmX + key B

Then a change on the key is not different from a change in the algorithm.

The only different I see is that for a new pair of users/keys

Most of the Algorithm structure remains constant in the case of secret key,
Most of Algorithm structure need to change in the case of secret Algorithm

But where is the limit? "most of" meaning?

I would like to have more views and clues to understand why this distinction is usually mentioned.

The distinction you want to make between the key and the algorithm proper is not based on whether most of the operation is contained in one or the other, but on where the complexity lies. I am not talking about algorithmic complexity here, but complexity in its everyday meaning: difficulty to understand and reason about.

The algorithm proper is complex and hard to reason about. It generally does a whole bunch of arbitrary-seeming bit manipulations, logical and arithmetic operations, and general shuffling of the data. It's very hard for a layperson or even for a cryptographer to know how much privacy all those manipulations actually buy you, and what kind of cryptanalysis it might be vulnerable to. So the best way to be confident about the algorithm's security is to put it out in the open and have it reviewed by experts as widely as possible. MAKE IT PUBLIC.

The key, on the other hand, is a simple concept: it's a bunch of bits which need to be random. There is no need to review the key to assure the correctness of the crypto. Any key is supposed to be as strong as any other key (and if this is not true then it can in principle be discovered by review of the algorithm, not the key). We know that the quality of randomness that is available to generate keys is less than perfect, so in practice some keys may be weak due to lack of randomness, but at least everyone can know without needing to be an expert cryptographer and without needing to make a difficult analysis of the key that good randomness WILL lead to a good key. So use the best randomness you've got available then you need not (MUST not!) share the key with everyone in order to have confidence in your crypto.


Why don't nodes carry as many pointers as possible in a skip list? From this main picture explaining how skip lists work from Wikipedia, we see that some nodes carry different amounts of pointers to other parts of the list:

Wouldn't it make more sense to have every node carry 4 pointers (since this is the height of this specific example)? For instance, node with value 2 would also have pointers to nodes 4, 6 and 7 and not just to node 3.

I'm asking because I need a data structure that would allow me to traverse the list as quickly as possible. Having each node carry as many pointers as possible would allow me to carry out lots of parallel requests. Also, each arrow in my implementation is actually a network call, so if I can achieve higher concurrency to retrieve all 10 items would be best.

In the usual way, where each node carries $i$ pointers with probability $2^{-i}$, the average node has size $O(1)$, so the total space used by the skip list is $O(n)$. If each node carried pointers at every level, then each node would have $\theta(\log n)$ pointers in it, since that is the expected height of a skip list with $n$ nodes. The total space used would thus be $\theta(n \log n)$.

A skip list of one million nodes would thus be using roughly 10 times as much space.


Why does heapsort run in $\Theta(n \log n)$ instead of $\Theta(n^2 \log n)$ time? I am reading section 6.4 on Heapsort algorithm in CLRS, page 160.

HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i to A.length downto 2
3   exchange A[i] with A[i]
4   A.heap-size = A.heap-size-1
5   MAX-HEAPIFY(A,1)

Why is the running time, according to the book is $\Theta (n\lg{n})$ rather than $\Theta (n^2\lg{n})$ ? BUILD-MAX-HEAP(A) takes $\Theta(n)$, MAX-HEAPIFY(A,1) takes $\Theta(\lg{n})$ and repeated $n-1$ times (line 3).

Let us count operations line by line. You construct the heap in linear time. Then, you execute the loop and perform a logarithmic time operation $n-1$ times. Other operations take constant time. Hence, your running time is

$\qquad \begin{align}
& n + (n-1) \log n + O(1) \\
&= n + n \log n - \log n + O(1) \\
&= \Theta(n \log n).
\end{align}$

In other words, as $n$ grows the $n \log n$ term dominates. That is, the cost of building the heap on line 1 is negligible compared to the cost of executing the loop.


If L is a regular language, how to prove that L' is also regular? I've been trying to construct a proof of the following statement the whole day but I got stuck:

If $L$ is a regular language, the language $L_{}{'}$ consisting of all words in $L$ containing the letter $\sigma$ (where $\sigma$ is an arbitrary fixed letter in $\Sigma$) is also regular.

I know that the first thing to do is to construct an NFA that recognizes $L_{}{'}$ from the NFA that recognizes $L$, but I can't find a conversion that is general enough. It might me silly, but I think one just have to change the transition function. I hope you guys can give me some advice.

Yes, but changing the transition function also might involve changing the states. In this case, the states should "remember" whether we have seen the letter $\sigma$ in the past.

Alternatively, one can prove closure properties like this using well-known properties, like the fact that regular languages are closed under intersection. The language of all words containing the letter $\sigma$ is regular.


reference request: solving problems by dynamic programming + quantization to avoid combinatorial explosion The context: I have been working lately with problems like the following: Let $x_{k}\in\mathbb{R}^n$ be a state evolving accroding to:
$$
x_{k+1} = f(x_k,u_k), k=0,\dots,N-1
$$
given some $x_0$ and controls $u_0,\dots,u_{N-1}\in\{1,\dots,L\}$ (the set of possible controls is a finite set of "modes").  The goal is to choose the controls to minimize
$$
J = \sum_{k=0}^{N} g(x_k)
$$
In most of my examples, $f$ does provide structure to make $x_k$ lie in a finite set, but may lie an arbitrary place in $\mathbb{R}^n$ in general. The "naive" solution would be to make a tree traversing all combinations of $u_0,\dots,u_{N-1}$, then look for the leaf with the least value of $J$. Of course, branch and bound or other techniques may be used, but as far as I know this approach won't be able to get rid of the exponential complexity $O(L^N)$ (right?).
In order to provide structure to the state space, I decided to quantize $\mathbb{R}^n$ in blocks of length, say $\epsilon$, and assume that $x_k$ won't exit a box $[-B,B]^n\subset\mathbb{R}^n$, so that $x_k$ will always lie in a set of finite size $\mathcal{X}\subset\mathbb{R}^n$ and $\hat{f}:\mathcal{X}\times\{1,\dots,L\}\to\mathcal{X}$ is the approximation of $f$ in this setting. In this context, since $\hat{f}$ transitions between finite sets, one can build a trellis diagram of $N$ stages with weights given by costs $g(x_k)$, then we may apply a shortest path algorithm (viterbi-like approach) which is polynomial. (right?).
To formalize this approach I plan to:

Use the original $f$ to obtain a bound $B$ which will depend on $N$.
Show that for a correct value of $B$, one obtains that the true optimum $J^*$ and our approximated one $J_\epsilon$ comply that $J_\epsilon\to J^*$ as $\epsilon\to 0$.

My questions:

I have read that in other problems, a similar quantization approach have been used to obtain a trade-off between accuracy and computational complexity, e.g. in some knapsack problem solutions or some scheduling problems, although these methods quantize the cost and not the state space. My question is, if this approach (quantization + dynamic programming) is standard, if it has a name and if there is a standard reference for me to read more about it.
Given the problem statement I gave, do you think the solution outline I provided is suitable, or if there is a different approach you can suggest?

This sounds like a reinforcement learning problem.
Construct the following MDP:

The states are the different values of $x$
The actions are $u_1,\dots,u_L$
The transition is given by $f$
The reward is given by $g$ of the current state.

Define it as a finite horizon problem.
Then, if the set of the values of $x$ is finite, use any RL technique to solve the problem (you can use a dynamic programming solution from there to compute the exact solution).
If the state space is infinite, or extremely huge, consider trying to use the equivalent techniques from reinforcement learning.
If you wish, leave here a comment and when I will be able to I will send the algorithms themselves.

Anyways, from my understanding of your solution - it looks correct. But you need to be cautious about the use of $B$ and $\epsilon$ since cutting the space into boxes increases the number of boxes dramatically with the increase of the dimensions


Vertex-disjoint cycles passing through a collection of vertices I am wondering about the complexity of the following problem: given a directed graph $G=(V,E)$ (which may have self-loops at some vertices) and a subset of the vertices $U \subset V$, does there exist a collection of vertex-disjoint cycles $C_1, C_2, \ldots$ such that each $u \in U$ belongs to some cycle $C_i$?

When $U=V$, I can see how to reduce this to the problem of finding a maximum matching in a bipartite graph. I'm not sure how to handle the case when $U$ is a strict subset of $V$.

If $U$=$V$ it reduces to a matching problem by splitting all of the vertices into a left-vertex and a right-vertex to create a corresponding bipartite graph.  All existing edges in the original graph translate to the bipartite graph as low-cost edges directed left-to-right (from the origin's left-vertex to the destination's right-vertex).  For each left/right pair, you add a high cost edge connecting the left to the right.  (Unless it already had an edge due to a loop, in which case the edge remains low cost.)  The minimum cost matching will use as few of those high cost edges as possible.  The resulting matching corresponds to a set of vertex-disjoint cycles with the maximum number of total vertices because for each vertex not in a cycle, the high-cost edge is used.

Now assume $U$ is instead a strict subset of $V$.  For each vertex not in $U$, consider the high cost edge connecting its left-vertex and right-vertex.  Lower the cost of those edges so that the only remaining high-cost edges are the ones connecting left/right vertices in $U$.  (Again, if a vertex in $U$ has a loop, the edge is instead low cost.)  The minimum cost matching will use as few of those high cost edges as possible, thus maximizing the number of vertices in $U$ that are in cycles.


How to prove non-existence of $O(2^n)$ approximation algorithm solving TSP? The following theorem (from "The Design of approximation algorithms" by Williamson & Shmoys, pg 43) states:

  For any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm for the
  traveling salesman problem on $n$ cities, provided $P  \neq NP$. In fact, the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$.

This theorem is given without a proof. It only explains, before the theorem formally stated, that for any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm. This part is clear. But the claim that the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$ is not obvious to me. Could someone give me a hint how to prove it or sketch of proof?

After @YuvalFilmus' hint it turns out the answer lies in this book. The TSP can be used to solve the Hamiltonian Cycle problem by creating a new graph as following. Given $\alpha > 1$ and  a graph $G=\langle V,E \rangle$ we create a new graph $G'=\langle V',E' \rangle$ such that $w(e')= 1$ if $e\in E$, and $w(e')= \alpha n+2$ if $e\notin E$. If $G$ has a Hamiltonian cycle then $G'$ has a tour of length $n$, otherwise each tour has length is at least $(\alpha+1)n + 1$.

Now we run $\alpha$-approximation algorithm for TSP and if the tour computed has cost at most $(\alpha+1)n$ then there is a Hamiltonian cycle in $G$, otherwise there doesn't. If we set $\alpha = O(2^n)$ then we have $O(2^n)$-approximation algorithm. This algorithm runs in $O(f(2^n))$ time for some polynomial $f$, but its time complexity is still polynomial in length of input. This means we would solve the Hamiltonian Cycle problem in polynomial time implying $P=NP$.


Complexity classes closed under finite union and intersection, why not infinite union and intersection? All "nice" Complexity classes are closed under finite union and intersection. (By "nice" I mean ones with complete problems or leaf languages, e.g. P, NP, PSPACE, etc.)

But such classes are not closed under infinite union and intersection. Why?

Consider the "singleton" languages: $L=\{w\}$ for some fixed word $w$.  (e.g., the language $L=\{00010100\}$ would be a singleton language)  Most "nice" complexity classes include the singleton languages.

Every language can be written as an infinite union of singleton languages. So, if all singleton languages are in the class, and if the class is closed under infinite union, then all languages are in the class.

Thus, if there is any language at all that isn't in such a complexity class yet it does contain all the singleton languages, then the class cannot be closed under infinite union.


difference between propagation speed and bandwidth in digital communication I want to know difference between propagation speed and bandwidth in digital communication.I know bandwidth is no of bits in one second and propagation speed of signal is distance traveled by signal is one second.Is there any relation between them or they are totally different.Can anyone tell me exact definition to differentiate these twos.

They are unrelated.

The bandwidth is, as you correctly said, the number of bits per second. The propagation speed is the time until the first bit arrives (this is also called the latency).

Imagine you have an army of snails that can carry SD cards along a straight line. Their propagation speed is very slow, so it takes a long time until a snail arrives after you send it. However, you can send a snail every second, so that after the initial delay your snails deliver one SD card of data every second. That's high bandwidth.


Solving Recurrence Relations 'Chip & Conquer' I've been tasked with solving some recurrence relations, and I've been running into trouble with so called 'chip & conquer' relations.

Here are some example problems:

$$T(n) = T(n-5) + cn^2$$

and

$$T(n) = T(n-2) + \log{n}$$

I'm supposed to be giving an answer in $\Theta$ notation. How do I go around and solving relations like these?


Introduction To Algorithms 3rd Edition MIT Press: Red Black Tree insertion error in pseudo-code? I'm implementing the algorithm on page 316 of the book Introduction to Algorithms. When I look at the pseudo-code, I feel that there is something wrong between line 10 to 14. I feel it's missing a check. There is a YouTube video explaining this whole function (and it includes the pseudo-code plus line numbers): https://youtu.be/5IBxA-bZZH8?t=323

The thing is, I think that //case 2 needs its own check. The else if z == z.p.right is both meant for //case 2 and //case 3. However, the code from //case 2 shouldn't always fire. It should only fire when there is a triangle formation according to the YouTube video. In my implementation it always fires, even when it's a line.

So I feel the pseudo-code is wrong, it's also weird that it has an indentation, but I see no extra check.

Am I missing something?

Maybe superfluous, but I also typed the pseudo code given from the book here:

RB-INSERT-FIXUP(T, z)
  while  z.p.color == RED
    if  z.p == z.p.p.left
      y = z.p.p.right

      if y.color == RED
        z.p.color = BLACK   // case 1
        y.color = BLACK     // case 1
        z.p.p.color = RED   // case 1
        z = z.p.p           // case 1

      else if z == z.p.right
          z = z.p           // case 2
          LEFT-ROTATE(T, z) // case 2
        z.p.color = BLACK   // case 3
        z.p.p.color = RED   // case 3
        RIGHT-ROTATE(T, z.p.p) // case 3

    else (same as then clause with "right and "left" exchanged)

  T.root.color = BLACK

In an email with one of the authors it became clear that the following pseudo-code rule applies.

(this is not an actual quote, but the format seems better for this)

  Whenever there is an else clause. The first statement of that else clause will be on the same line as the else clause. This can be a variable assignment, an if-statement or other things.

If that was too abstract, the code from question should be interpreted as follows:

RB-INSERT-FIXUP(T, z)
  while  z.p.color == RED
    if  z.p == z.p.p.left
      y = z.p.p.right

      if y.color == RED
        z.p.color = BLACK   // case 1
        y.color = BLACK     // case 1
        z.p.p.color = RED   // case 1
        z = z.p.p           // case 1

      else                  // this is the difference compared to code in the question
        if z == z.p.right
          z = z.p           // case 2
          LEFT-ROTATE(T, z) // case 2
        z.p.color = BLACK   // case 3
        z.p.p.color = RED   // case 3
        RIGHT-ROTATE(T, z.p.p) // case 3

    else (same as then clause with "right and "left" exchanged)

  T.root.color = BLACK


Can you have simple unit tests for complicated function? Can you have simple unit tests for complicated function?
For example: Turing test for AI.

Do you always can find simple unit tests for any complicated enough function / algorithm?

The Turing test would make a very poor unit test because (a) it is difficult (impossible ?) to automate and (b) the evaluation of the test output to produce a pass or fail result is subjective. In fact, it might not even be possible to devise useful unit tests (in the usual sense) for strong AI - how would unit tests distinguish between true AI and a program that simply responded by rote ?

But simple unit tests for other complicated functions are certainly possible. As long as the function produces output that can be objectively evaluated then you can write unit test cases for it. For example, a Travelling Salesman Problem solver could be a very complicated program, but a unit test plan is very simple:

(a) test edge cases - 0 cities, 1 city, 2 cities

(b) test some simple cases with known solutions e.g. 3 cities in scalene triangle, 4 cities at corners of a rectangle, solved examples from TSPLIB


The Taylor series and time complexity analysis I was just wondering, if an algorithm $A$ has a time complexity O$(2^n)$, since $2^n$ can be represented using a Taylor series, which is a polynomial, does this mean that $A$ has polynomial time complexity? Generalising even further, does this mean that any algorithm which has a time complexity O($f(n)$) where $f(n)$ has a corresponding Taylor series representation is also a polynomial time algorithm?

Thanks very much in advance.

$2^n$ can be represented as a Taylor series, which is an infinite sum of polynomials. Notably, there is no single polynomial which is equal to $2^n$.

In general, since big-O lets us get rid of lower-degree terms in the polynomial, we can say that something has polynomial time (or space or whatever you're measuring) when it is $O(n^k)$ for some fixed $k$.

Since there's no single $k$ where $\forall n \ldotp O(2^n) = O(n^k)$, we say that $2^n$ is not polynomial.


Print bottom view of a binary tree For a binary tree we define horizontal distance as follows:

    Horizontal distance(hd) of root = 0
    If you go left then hd = hd(of its parent)-1, and
    if you go right then hd = hd(of its parent)+1.

The bottom view of a tree then consists of all the nodes of the tree, where there is no node with the same hd and a greater level. (There may be multiple such nodes for a given value of hd. In this case all of them belong to the bottom view.) I'm looking for an algorithm that outputs the bottom view of a tree.

Examples:

Suppose the binary tree is:

         1
        /  \
       2    3
      / \  / \
     4   5 6  7
            \
             8

Bottom view of the tree is: 4 2 5 6 8 7

    Ok so for the first example,
    Horizontal distance of node with value 1: 0, level = 1
    Horizontal distance of node with value 2: 0 - 1 = -1, level = 2
    Horizontal distance of node with value 3: 0 + 1 = 1, level = 2
    Horizontal distance of node with value 4: -1 - 1 = -2, level = 3
    Horizontal distance of node with value 5: -1 + 1 = 0, level = 3
    Horizontal distance of node with value 6: 1 - 1 = 0, level = 3
    Horizontal distance of node with value 7: 1 + 1 = 2, level = 3
    Horizontal distance of node with value 8: 0 + 1 = 1, level = 4

    So for each vertical line that is for hd=0, print those nodes which appear in the last level of that line.
    So for hd = -2, print 4
    for hd = -1, print 2
    for hd = 0, print 5 and 6 because they both appear in the last level of that vertical line
    for hd = 1, print 8
    for hd = 2, print 7

One more example for reference :

         1
      /     \
    2         3
   / \       / \
  4   5     6     7
 / \ / \   / \    / \
8  9 10 11 12 13 14 15

So the output for this will be :
8 4 9 10 12 5 6 11 13 14 7 15

Similarly for this example
hd of node with value 1: 0, , level = 1
hd of node with value 2: -1, level = 2
hd of node with value 3: 1, level = 2
hd of node with value 4: -2, level = 3
hd of node with value 5: 0, , level = 3
hd of node with value 6: 0, level = 3
hd of node with value 7: 2, level = 3
hd of node with value 8: -3, level = 4
hd of node with value 9: -1, level = 4
hd of node with value 10: -1, level = 4
hd of node with value 11: 1, level = 4
hd of node with value 12: -1, level = 4
hd of node with value 13: 1, level = 4
hd of node with value 14: 1, level = 4
hd of node with value 15: 3, level = 4

So, the output will be:
hd = -3, print 8
hd = -2, print 4
hd = -1, print 9 10 12
hd = 0, print 5 6
hd = 1, print 11 13 14
hd = 2, print 7
hd = 3, print 15

So the ouput will be:
8 4 9 10 12 5 6 11 13 14 7 15

I already know a method in which I can do it using a lot of extra space (a map, and a 1-D array for storing the level of the last element in that vertical line) and with time complexity of $O(N \log N)$.
And this is the implementation of this method:

void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[], int l)
{
     if(node == NULL)
             return;
     if(level == 1){
              if(lev[hd-min] == 0 || lev[hd-min] == l){
                      lev[hd-min] = l;
                      visited[hd-min].push_back(node->data);
              }
     }
     else if(level > 1)
     {
          printBottom(node->left, level-1, hd-1, min, visited, lev, l);
          printBottom(node->right, level-1, hd+1, min, visited, lev, l);
     }
}

int main()
{
    find the minimum and maximum values for hd via DFS

    int lev[max-min+1]; //lev[hd] contains the maximum level for which we have found nodes with this value of hd; initialized with 0's

    map < int, vector<int> > visited; //the nodes in the bottom view

    int h = height(root);

    for (int i=h; i>0; i--){
        printBottom(root, i, 0, min, visited, lev, i);
    }

    output visited
}

I am seeking help to do this in more optimized way, which used less space or time. Is there any other efficient method for this problem?

First, you can get the time complexity down to ${\cal O}(n)$, while keeping the same space complexity. You can do this by filling visited in a single run of printBottom:

void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] < level){
         lev[hd-min] = level;
         visited[hd-min] = new vector<int>; //erase old values, they are hidden by the current node
     }
     if(lev[hd-min] <= level){
         visited[hd-min].push_back(node->data);
     }
     printBottom(node->left, level+1, hd-1, min, visited, lev);
     printBottom(node->right, level+1, hd+1, min, visited, lev);
}

with the initial call printBottom(root, 1, 0, min, visited, lev);

If you insist on the nodes beig output in order of increasing value of hd, I don't think you can improve space consumption. However, if you allow a different order of output, you can get rid of visited, by first determining for each value of 'hd', which level should be output and then making another pass, printing the values that match:

void fillLev(Node *node, int level, int hd, int min, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] < level){
         lev[hd-min] = level;
     }
     fillLev(node->left, level+1, hd-1, min, lev);
     fillLev(node->right, level+1, hd+1, min, lev);
}
void printBottom(Node *node, int level, int hd, int min, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] == level){
         cout << node->data;
     }
     printBottom(node->left, level+1, hd-1, min, lev);
     printBottom(node->right, level+1, hd+1, min, lev);
}

with calls fillLev(root, 1, 0, min, lev); and printBottom(root, 1, 0, min, lev);.


Scheduling algorithm to minimize maximum deadline overshoot in pre-emptive scheduler Suppose there are $n$ tasks, which need to be scheduled by a pre-emptive scheduler. Each task $T_i$ has a deadline $d_i$ and a total processing time $t_i$ associated with it. Now, all $n$ tasks are given a priory to the scheduler. The scheduler can run a task for 1 unit of time in one go. After each unit of time, it can schedule any process (including the current one) for the next 1 unit of time.

The goal of the scheduler is to minimize the maximum overshoot of its deadline by any process. For example, for tasks $T_1: (2, 2)$, $T_2: (1, 1)$ and $T_3: (4, 3)$ are the 3 tasks with their respective $(d_i, t_i)$, then a schedule of $T_2, T_1, T_3, T_1, T_3, T_3$ gives a maximum overshoot of 2. No other schedule can reduce the maximum overshoot.

My solution is to use "Earliest Deadline First Scheduling", with tie-breaks based on most time/work remaining. Further ties are broken arbitrarily. Basically, after each unit of time, the task with the earliest deadline is scheduled first. Any ties are decided on which task has the most work remaining. Further ties are broken arbitrarily. This seems to work on a few small hand-constructed cases. But I could not prove or disprove it.

To make the question more than a yes/no question, I would really appreciate it if someone could prove if this is correct, or provide a correct and efficient (sub-quadratic time) algorithm for this. This is not homework. It was presented to me by someone, and I suspect it might be a popular interview question or a question on a programming forum.

The problem minimizing maximal lateness is discussed in the algorithm book by Kleinberg and Tardos under greedy algorithms. The solution is like yours, ordering the tasks by their deadline. Indeed the length of the tasks is not relevant.

The main ingredient of the proof is that any optimal solution $O$ can be transformed into this greedy one $G$ by swapping two adjacent tasks that do not agree on the greedy ordering.

Assume we have two tasks $(t_i,d_i)$ and $(t_j,d_j)$ with $d_i\le d_j$ and $O$ has scheduled task $j$ just before $i$, while the greedy algorithm wants it the other way. Assume task $i$ starts at time $t$ in $O$. The lateness in $O$ is the maximum $m$  of $t+t_j-d_j$ and $t+t_j+t_i-d_i$.

After swapping we have the maximum of $t+t_i-d_i$ and $t+t_i+t_j-d_j$. This cannot be worse then the performance of $O$ since both these two numbers are at most $t+t_i+t_j-d_i \le m$ (using $d_i\le d_j$). As $O$ is optimal, so must the swapped version, but it looks more like $G$.

This is not the complete proof. E.g., we have to show that always such a pair $i,j$ can be found, to iterate and obtain $G$ from $O$ by swapping. Also we have to consider 'negative values', when actually $i$ or $j$ meet their deadline, and $m=0$.


Local Search vs Classical Search I have some questions regarding local search / optimization as explained in chapter 4 of the book : http://aima.cs.berkeley.edu/

In classical search (Chap 3), the search starts from an initial node, then the search continues based on strategies of BFS, DFS, etc. What I am unsure of is the process of local search (Chap 4).

Does the local search algorithm start from one node in state space? Check if constraints are satisfied? If Yes, this is goal? If not, move to neighbours?
Is the entire state space considered goal state? Even nodes that don't satisfy the constraints?
In optimization, the search is conducted in a part of search space where all constraints are met, but tries to find a better solution. In that case, what if the search algorithm moves to nodes where they don't satisfy the constraints?

Classical local search works as follows. We're trying to optimize some function under some constraints. We start with some feasible point (a point satisfying all constraints). At each step, we consider small changes to the current point which (1) keep it feasible, (2) improve the objective function. If we find such a small change, we modify the point accordingly. Eventually, we reach a local optimum, and we hope that it's not too bad relative to the global optimum.

A classical example is the simplex algorithm for linear programming. The algorithm starts with some feasible point (it's not immediately obvious how to do it; a trick is required). At each step, we try to modify the point by switching one tight constraint with another in a way that improves the objective function while keeping the point feasible. Eventually we reach a local optimum, which turns out to be a global optimum (in this particular case).

The interior-point algorithm for linear programming work differently. They start at some point, and move in a direction that (1) makes the point more feasible, and (2) improves the objective function. In the end, you get close to a feasible local optimum, which turns out to be a global optimum. This is not local search, but it's an example of an algorithm which does not maintain a feasible solution.

Non-oblivious local search is a variant on the theme of local search, in which instead of trying to optimize the actual objective function, you direct the local search using an auxiliary objective function. Sometimes this improves the quality of the local optimum. You can read all about it in a recent PhD thesis by Justin Ward.


Why is the running time of heapsort $O(n\log n)$? Heapsort(A)
1 BUILD_MAX_HEAP(A)
2 for i=A.length downto 2
3    exchange A[1] with A[i]
4    A.heapsize=A.heapsize-1
5    MAX_HEAPIFY(A,1)

In the book on algorithms by CLRS the running time of this algorithm is given to be $O(n\lg n)$ as the for loop is executed $n-1$ times and each call of MAX_HEAPIFY takes $O(\lg n)$.

But my question is does MAX_HEAPIFY not depend on height of subtree at which it is called? Why then should it still be the same for all $n-1$ calls as $h$ will obviously differ?

Each call of MAX_HEAPIFY takes time $O(h) = O(\log n)$, where $h$ is the depth of the heap. Note that big O is an upper bound on the running time, not the exact running time. It is also true that the running time of MAX_HEAPIFY is $O(n)$, for example.


Efficient Data Structure for Closest Euclidean Distance The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628.

  A network of autonomous, battery-powered, data acquisition stations has been installed to monitor the climate in the region of Amazon. An order-dispatch station can initiate transmission of instructions to the control stations so that they change their current parameters. To avoid overloading the battery, each station (including the order-dispatch station) can only transmit to two other stations. The destinataries of a station are the two closest stations. In case of draw, the first criterion is to chose the westernmost (leftmost on the map), and the second criterion is to chose the southernmost (lowest on the map).
  You are commissioned by Amazon State Government to write a program that decides if, given the localization of each station, messages can reach all stations.

The naive algorithm of course would build a graph with stations as vertices and calculate the edges from a given vertex by searching through all other vertices for the closest two. Then, we could simply run DFS/BFS. Of course, this takes $O(V^2)$ time to construct the graph (which does pass the test cases). My question, though, is if we can build the graph any faster with an appropriate data structure. Specifically, given an arbitrary query point $p$ and a given set of points $S$, can we organize the points in $S$ in such a way that we can quickly find the two closest points in $S$ to $p$ (say, in $\log V$ time?).

It seems that the relevant data structure might be a dynamic Voronoi diagram.

Voronoi diagrams are often the answer when a set of points on the plane is involved.

In this case, since the point set is evolving, you want a dynamic version.


Is there an example of how SOS can be used to show infeasibility of a set of multivariable equations? Lets say one is given a set of $m$ real polynomial equations in $n$ variables, $P_1 = P_2 = P_2 .. = P_m =0$. I understand that there is some theorem which says that if there is no solution to these simultaneous equations then one necessarily will be able to find polynomials $Q_1,Q_2,..,Q_m, R_1, R_2,..,R_k$ such that $deg(P_iQ_i)$ and $deg(R_i^2)$ are all  $\leq d$ for some $k$ and $d$ such that,  $\sum_{i=1}^m Q_iP_i + \sum_{j=1}^k R_j^2 = -1$

Can someone kindly reference this theorem and its proof?

Now lets say one is looking at a $d$ which is not sufficiently large. Then one will be looking at the set of all polynomials of the form $S = \sum_{i=1}^m Q_iP_i + \sum_{j=1}^k R_j^2$ such that $deg(P_iQ_i)$ and $deg(R_i^2)$ are all  $\leq d$ for various $k$. But this is a convex set in the set of polynomials? And $-1 \not \in S$. Then there will exist a separating hyperplane between S and $-1$ and the normal to that plane gives a degree-d pseudo-distribution on S.

Does someone have a concrete example of the above phenomenon?
Why is this pseudo-distribution indistinguishable from an actual distribution on $S$ if one is only looking at moments $\leq d$?

The theorem you are referring to is known as the Positivstellensatz, but you are citing it incorrectly; given only polynomial equations, the relevant theorem would be the Nullstellensatz. See also lecture notes of Laurent and blog posts of Amir Ali Ahmadi.

Regarding pseudodistributions, Barak defines them as linear operators for low-degree monomials which satisfy the crucial property $E[P^2] \geq 0$ for low-degree $P$. These are all the properties you need when looking at low-degree moments.


Find a path from s to t using as few red nodes as possible Was doing a little interview prep. Given an undirected graph G, such that each node is colored red or blue and |E|≥|V|, find a path in O(|E|) time such that starting and ending at 2 blue nodes, s and t, that you pass through as few red nodes as possible.

Initial Impressions: Since |E|≥|V|, O(|E|) time would include O(|E|+|V|), which means the solution likely uses BFS or DFS. Modifying the graph such that causing the all red nodes must be forced down a directed path of some long length (after making the whole graph directed) in order to use out-of-the-box BFS seems not viable, as it would mean constructing a new graph would be along O(|E||V|) time.

Another method I toyed around with was propagating values to nodes based on the safest path to that node while doing a DFS search, but not all values were guaranteed to update.

I still want to try to solve this myself, but I'm really stuck right now. Was wondering if there were any hints I could get. There are much simpler ways of doing this if it weren't for the O(|E|) time. Djikstras with creating some edge weights would work, but wouldn't be within the time bound.

To solve this, you need to use $BFS$. But first, manipulate $G$ so that the path will always favor blue vertices.

The solution has 2 parts:

Use $DFS$ on blue vertices only, to find all all-blue connected components. Let's denote each such component by $v'$. Now, each blue $v \in v'$ will be "compressed" to a single vertex $u$, and an edge $(u,x)$ will be added for every $x \in N(v')$.
Note any such $x$ is necessarily red.
This step costs $O(V+E) = O(E)$, since $DFS$ is $O(V+E)$, and you have at most $V$ blue vertices, which make no more than $E$ new edges to add.

Step 1 means all paths that are blue-only will be free. On the new graph, the $BFS$ will only consider the edges which pass through a red vertex.

Use $BFS$ from $s$. That length of the path to $t$ will essentially be the shortest path under the constraint of least red vertices in the path.


Minimizing a multiple output circuit with K-maps - and without I'm currently working on learning to minimize a circuit which has multiple outputs using K-maps. My universities script seems rather unhelpful to me which left me in a spot where I have a very rough understanding of the matter without actually being able to pull it through.

I currently am supposed to first minimize the functions on their own and then compare that to minimizing them together.

The resulting functions are:

$Fa = (bc)+(bd)+(\neg acd)$

$Fb = (b\neg c\neg d) + (b\neg cd) + (bc\neg d)$

So now I think I am supposed to minimize them together. My approach is to mark the 1s in the maps that are unique to one function red and group them first.
After that, I look at the ones that are shared. I can now group these the same way in both maps.
The groups bordered by yellow are the ones that are shared. So I now created the functions for these two.

$Fa = (bcd) + (\neg acd) + (b\neg cd) + (bc\neg d)$

$Fb = (b\neg c\neg d) + (b\neg cd) + (bc\neg d)$

Here I count that they use two unique AND gates for Fa, one unique AND gate in Fb, two unique AND gates across the two and then one OR gate for each of these two. So all in all, they use 7 gates. This is exactly the same as before I minimized them together, thought the assignment heavily implies that the amount of gates should go down.
I simply cannot figure out what I am doing wrong here.

Furthermore, they tell me to then do this without K-maps, which is a task that I don't even know how to begin working on.

Good job on $f_a = \overline acd \lor bc \lor bd$.
With $f_b$, I'd denote it as $b\overline d\lor b\overline cd$ - you missed overlap with $\overline d$: $f_b = b\overline c \lor b\overline d$.
I'd tally that as and inputs: 11 complemented: 3 ands: 5 gates/ors: 2

In the combined implementation, groups are still allowed to overlap: both blue ones can be twice as large, use one input less.
One can share either $bc\overline d$:
$f_a = b\overline cd \lor \overline acd \lor bc$
$f_b = b\overline cd \lor b\overline d$
or $b\overline cd$:
$f_a = bc\overline d \lor \overline acd \lor bd$
$f_b = bc\overline d \lor b\overline c$
and inputs: 10 complemented: 3 ands: 4 gates/ors: 2


Classfication of randomized algorithms From Wikipedia about randomized algorithms

  One has to distinguish between algorithms that use the random
  input to reduce the expected running time or memory usage, but always
  terminate with a correct result in a bounded amount of time, and
  probabilistic algorithms, which, depending on the random input, have a chance of producing an incorrect result (Monte Carlo
  algorithms) or fail to produce a result (Las Vegas algorithms) either
  by signalling a failure or failing to terminate.

I was wondering how the first kind of "algorithms use the random
input to reduce the expected running time or memory usage, but
always  terminate with a correct result in a bounded amount of time?
What differences are between it and Las Vegas algorithms which may
fail to produce a result?
If I understand correctly,  probabilistic algorithms and randomized algorithms are not the same concept. Probabilistic algorithms are just one
kind of randomized algorithms, and the other kind is those use the
random  input to reduce the expected running time or memory usage,
but always  terminate with a correct result in a bounded amount of
time?

An example of such an algorithm is randomized Quick Sort, where you randomly permute the list or randomly pick the pivot value, then use Quick Sort as normal. Quick Sort has a worst case running time of $O(n^{2})$, but on a random list has an expected running time of $O(n\log n)$, so it always terminates after $O(n^{2})$ steps, but we can expect the randomized instance to terminate after $O(n\log n)$ steps, always with a correct answer.
This gives an subset of Las Vegas algorithms. Las Vegas algorithms also allow for the possibility that (with low probability) it may not terminate at all - not just terminate with a little bit more time.
These in turn are really just a type of Monte Carlo algorithm, where the answer can be incorrect (with low probability), which is at least conceptually different to maybe not answering.

There's a whole bunch of detail I've left out of course, you might want to look up the complexity classes ZPP, RP and BPP, which formalise these ideas.


How to choose proper activation functions for hidden and output layers of a perceptron neural network? As far as I know choosing an activation function for the input layer is relatively straightforward: I use Sigmoid if the input data domain is (0,1) and TANH if it is (-1,1).

But what activation functions to set for hidden and output layers? Is there any conventional logic for making thish choice reasonably? How do I know/set the domain of a neuron layer output?

Input: it is not common to use activation functions in the input layer. Just rescale your data to the [-1;1] interval;
Hidden: the $tanh$ activation used to be the most popular. Now, this role has been taken by the $relu$ (rectified linear unit) activation, which produce sparse activations and better preserve the gradients;
Output: here is where you need to chose the activation function according to your problem type. For classification use the softmax activation (the multivariate version of the logistic sigmoid). For regression problems you may use linear outputs (identity activation function).


How to tell if a proof relativizes? If I have a proof for a separation between two complexity classes (using no oracles) and I want to see if it relativizes, how do I go about doing so?

Especially in the case where there already exist proofs for these classes being equal with respect to one oracle and not equal with respect to another oracle. I'm wondering, if I have a proof of inequality with respect to no oracle can I simply reference the oracle to which these classes have been proven equal, call on that example, and be done--since there exists an oracle to which they have already been proven equal this is my proof that the inequality doesn't relativize?

Or do I have to apply oracles specifically to the machines in my proof of the inequality and see if it relativizes?

I'm confused about how proving relativization / non-relativization of a specific proof of some statement relates to the relativization of other proofs of the same statement.

How can I reference the fact that other proofs of a statement relativize / don't relativize to help me prove my own relativization result about my proof of that statement?

Thanks!

A proof relativizes if every step in the proof relativizes. You should go over your proof, and check whether each step remains valid in the presence of an oracle.

In contrast, a result relativizes by definition if it still holds relative to an arbitrary oracle. Hence, to show that a result doesn't relativize, all you have to do is give an oracle with respect to which it fails.

If we're interested in some specific statement, whose truth value we are not sure of, and there are both an oracle relative to which the statement holds and an oracle relative to which the statement doesn't hold, then we can conclude that no relativizing proof can either prove or refute the statement.


What is the resulting set for {0,1}*\{0}*? If we have a language $L = \{0\}^*$ over the alphabet $\Sigma=\{0,1\}$, what is $\Sigma^*\backslash L$?

That's what I think:

$\{0,1\}^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, ... \}$
$\{0\}^* = \{\epsilon, 0, 00, 000, 0000, ... \}$
$\{0,1\}^*\backslash \{0\}^*= \{1,01,10,11,001,...\}$

In other words, the resulting set should contain everything from $\Sigma^*$ except the empty string and any string that contains 0s but not 1s.

If my thinking is correct, then how can I express $\{1,01,10,11,001,...\}$ more succinctly using set notation? I was thinking of something like $\{0,1\}^*\{1\}\{0,1\}^*$ but I'm not sure if it's correct or if there's a better way.

You are correct that the words not in $0^*$ are exactly those words which contain $1$ somewhere. You are also correct that you can represent this complement using the regular expression $(0+1)^*1(0+1)^*$. There are other regular expressions for the same language, for example $0^*1(0+1)^*$ (which is a "deterministic" regular expression).


How can one simulate a PDA with a FIFO queue PDA? I'm trying to figure out how a pushdown automata (PDA), which we know uses a stack (LIFO) can be simulated by a queue (FIFO). I understand that in a regular PDA, we only have access to the top most element which can be popped. When we push something, it goes to the top of the stack.

In a queue, as I understand, elements get "pushed" to the top, but pop from the bottom. Thus, first in first out.

In a stack (LIFO) PDA, let's say we push 'a'. It's at the top of the stack, and when we pop, we pop 'a' since it is at the top.

In a queue (FIFO) PDA, when we push 'a', it is at the top, but when we pop, it will be from the bottom of the queue and thus it will not be 'a' (assuming the size is greater than 2).

So how can we simulate a regular PDA which uses a stack, with a FIFO (queue) PDA?

The answer is: "rotate".

Consider the stack like (bottom) ABCD (top). stack-pop is from top, queue-pop is from bottom (this is directed to myself, I am easily confused). Pushes are from top.

Now, if we want to stack-pop, we push a marker # (to top) then repeatedly queue-pop and push, essentially moving everything from bottom to top. If we delay the pushes by one, we are able to stack-pop, just not pushing the last symbol before the #.

By the way, almost the same trick shows that we can even simulate the Turing machine by a single queue. Which was asked in our sister math department.


Binary tree To Red-Black tree I have a question regarding the solution provided by Karolis Juodelė.
Given in this question; Colour a binary tree to be a red-black tree

Black = black nodes, white = red nodes

So for this tree when I try to manually work out the code, it seems to fail on the node 17. E.G. I have a black quota of 3 so I color the root black. Afterwards I go to the left child (17) and that has the same min height (namely 17 - 21 - 23) -> so I color this black. After this black colour I cannot see how I will end up with a valid tree with 1 black node left.

So if you could provide how to solve it for this example that would be great!

Well, apparently my answer was wrong. The algorithm, at least. The theorem seems to be okay, if a little unreadable.

More in line with that proof, the algorithm should be

if n is root,   # as before
    n.color = black
    n.black-quota = n.height / 2, rounded up.
    # black-quota could start at any value between n.height/2 and n.min-height

else if n.parent is red,   # as before
    n.color = black
    n.black-quota = n.parent.black-quota.

else (n.parent is black)
    n.black-quota = n.parent.black-quota - 1

    # check that the subtree isn't totally uncolorable
    if n.min-height < n.black-quota then
        error "shortest path was too short"

    # use red only if the subtree is not colorable (as a tree), with given quota
    if n.height <= n.black-quota*2  then
        n.color = black

    else
        n.color = red

What I meant by the last condition is that 17 is red for the sole reason that you can't color it black i.e. $b(17) \notin [\frac{1}{2}h(17), m(17)]$.

Hopefully that works. Thanks for pointing out the error!


What does the number of bit of microprocessor mean? Intel 8085 is a 8 bit processor whereas 8086 is a 16 bit processor,what does the number of bit specify?

How many bits wide its registers are: usually, its data registers (the ones which can load and store data and perform logical and arithmetical functions).

The 8086 has 16-bit data and address registers, and a 16-bit data path to external memory.

The 8088 has 16-bit data and address registers, but only an 8-bit data path to external memory. Because it is internally identical to the 8086, it is also considered to be a 16-bit processor.

The 8085 has 8-bit data registers and 16-bit address registers. The address registers (apart from SP) are made up of pairs of 8-bit data registers. The fact that it is possible to add one address register to another isn't enough to make the processor considered to be "16-bit".


Is there a contradiction between "set-theoretic" and "formal" definition of "Big-O"? $O(n) = \{n, n^{2}, n^{1000000}, 2^{n}, ...\}$ [Source A], [Source B]
Say $t_{n} \in O(n)$
By formal definition $t_{n} \leq k \cdot n$  [Source C]

But how can this be? Say $t_{n}$ is actually $n^{2}$, then $t_{n} \leq k \cdot n$ is just false. Would it not be more logical to have $t_{n} \geq k \cdot n$ as a formal definition acompanying $O(n)$?

The first statement you made is not correct. $O(n)$ is the set of all functions $f(n)$ that are bounded above by some constant multiple of $n$ for sufficiently large $n$. The functions you have listed all belong to the set $\Omega(n)$ which is almost like $O(n)$ but instead of being bounded above by $k\cdot n$, this is the set of functions that are bounded below by $k\cdot n$ for sufficiently large $n$.

So, there is no contradiction. But you do need to look at your definitions a bit more carefully.


How to represent a double push or double pop operation in push down automata I want to know the theoretical representation of a double push or a double pop in pda

There are several different definitions of pushdown automata. In the definition I know, every transition pops one stack symbol and pushes an arbitrary number of stack symbols. Thus you cannot "double pop", but you can push more than one element. You can simulate a double pop using $\epsilon$-transitions, but I'll let you figure that out.


Image segmentation generates inclusions and is not smooth I am performing segmentation using opencv, but the segmented image has regions with breaks and also the border isn't smooth. How can I handle this problems?

If I understand correctly, you need to use erosion and dilation morphological filter.
To ged rid of inclusion, like below ring finger, blob detection would be helpful, to detect small blob and erase it (meassure its area and decide based on that).
As for continuity, simple blur after errosion helps to get it smoother, if effect is too small, then use contour trace and smooth it via curves (RDP algorithm, convert it to Catmull-Rom or B-spline and smooth it from here). If you take curves approach, take the contour and discard rest, it automatically solves component inclusions.

The inclusion in index finger is too big to be handled by erosion and dilation, as it may change geometry too much.  Fast idea is to generate circles of estimated radius (you know from scale or further detection that finger should be say 40px wide), so circles should push contour of finger, standardizing it's size). With curves, it is quite simple to handle checking distance to "parallel" wall.

Another approach is to take skeleton and draw fingers yourself, but this requires separate palm handling.


What algorithm to use to generate random path of given length I have a map size of 8 x 8 cells with no obstacles. I should generate random path from start cell to the end cell with given length. Path can move up/down/left/right directions but not cross itself. What algorithm I can use to do this?

Algo for solving problem when path self-intersections are allowed

Auxiliary problem

First let's solve another problem:

  How many paths of length $K$ exists starting at coordinate $(StartRow, StartColumn)$.

Such problem can be solved by dynamic programming: let $dp[K][R][C]$ be answer for question:

  How many paths of length $K$ exists that start in $(StartRow, StartColumn)$ and ends in $(R, C)$".

Base case:
$$
dp[0][StartRow][StartColumn] = 1
$$

Step of dynamic:
$$
dp[K][R][C] = dp[K-1][R-1][C] + dp[K-1][R+1][C] + dp[K-1][R][C-1] + dp[K-1][R][C+1]
$$

Here we suppose $dp[K][X][Y]=0$, for any $X$ and $Y$ that outside of grid (e.g. $X < 1$ or $X > N$ or $Y < 1$ or $Y > N$)
Also we can even add more constraints for problem and add obstacles: for doing so - we need to suppose $dp[K][R][C]=0, \forall K$, where cell $(R, C)$ is impassable (e.g. is obstacle).

This will take $O(N*M*K)$ time, where $N$ - number of rows, $M$ - number of columns, and $O(N*M*K)$ memory if we will keep all steps of dynamic or $O(N*M)$ if we will keep only last step of dynamic.

Original problem

  Generate random path of length $K$ between cells $S(R_s, C_s)$ and $E(R_e, C_e)$.

First of all we need count how many paths of length $K$ exists between this cells, for that we can use previously described dynamic:
futhermore run it from end cell (e.g. count how many paths of length $K$ exist that start at $(R_e, C_e)$) and save all step of dynamic (we will use it in next steps).
Now add order relation between all paths of length $K$ starting at cell $(R, C)$ and ending at cell $E(R_e, C_e)$:

if $K=0$ we have $0$ or $1$ such paths (such collection is always ordered);
if $K>0$ let's suppose: Paths that go UP $<$ Paths that go RIGHT $<$ Paths that go DOWN $<$ Paths that go LEFT (and for ordering paths in each of 4 groups we can recursevly apply this definition again).

Then we know how many paths of length $K$ exist between cells $S$ and $E$, lets name it $A=dp[k][R_s][C_s]$, now we can uniformly at random peek number $L\in[0, A)$ that will identify choosen path among all $A$ available.
We had ordered all $A$ paths and choose some path to output $L$ ($0-indexed$) and just need to find it. Let $choose(R_c, C_c, L, K)$ - function that return $Lth$ path of length $K$ staring at cell $(R_c, C_c)$ and ending at $E(R_e, C_e)$:

$$
 choose(R_c, C_c, L, K) =\small\left\{
                \begin{array}{ll}
                  \langle empty \rangle, K = 0\\
                  \langle UP, choose(R_c - 1, C_c, L - 0, K - 1)\rangle,
                  \\ \hspace{45pt} L \in [0, Count_u)\\
                  \langle RIGHT, choose(R_c, C_c + 1, L - Count_u, K - 1)\rangle,
                  \\ \hspace{45pt} L \in [Count_u, Count_u + Count_l)\\
                  \langle DOWN, choose(R_c + 1, C_c, L - (Count_u + Count_l), K - 1)\rangle,
                  \\ \hspace{45pt} L \in [Count_u + Count_l, Count_u + Count_l + Count_d)\\
                  \langle LEFT, choose(R_c, C_c - 1, L - (Count_u + Count_l + Count_d), K - 1)\rangle,
                  \\ \hspace{45pt} L \in [Count_u + Count_l + Count_d, A)\\
                \end{array}
              \right.\\
$$
$$
Where \forall K, R_c, C_c\\
Count_u=dp[K - 1][R_c - 1][C_c]\\
Count_l=dp[K - 1][R_c][C_c + 1]\\
Count_d=dp[K - 1][R_c + 1][C_c]\\
Count_r=dp[K - 1][R_c][C_c - 1]\\
$$

And $Count_u$ means how many paths of length $K$ starts at $(R_c, C_c)$ and ends at $(R_e, C_e)$ and first move is $UP$, $Count_l$, $Count_d$, $Count_r$ defines respectively for another directions.

More intuitively, imagine we at $X$ cell choosing for $7th$ path:

...
_   4   _
5   X   0
_   9   _
...

If we go $UP$ we will follow paths $\in [0, 4)$, there is no paths to $RIGHT$, if we go $DOWN$ we will follow paths $\in [4, 4+9)$, so we need to go $DOWN$ and choose $(7 - 4)th$ path among all that starts in that cell.

Note: due to we define ordering on paths $I'th$ path everytime will be the same (so it's possible to store path just as index number among all such paths and restore path when it is needed). Also need to notice that order $UP < RIGHT < DOWN < LEFT$ is not only right choise, you can use any order - just keep it thorugh all algorithm flow the same.


Beta reduction of S combinator in pure lambda calculus S is defined as S x y z = x z (y z)
This suggest that (y z) should be evaluated just after x z and the the results of x z is applied to the results of (y z).
I'm implementing call by value in lambda calculus, I would need to support parenthesis when evaluating this expression right? Does this affect the results? I thought that the order would not matter, so why the parenthesis in (y z)?
Regards

Parentheses matter. Honestly, if you are unclear about how $\lambda$-calculus works, it is going to be rather hard to implement it.
Here is an explicit counter-example:
$$(K S)(K S) = S$$
but
$$K S K S = ((K S) K) S = S S \neq S.$$
I would recommend learning about parsers, abstract syntax trees, and other bits and pieces that make up an implementation of a programming language.
An example of the implementation of the $\lambda$-calculus is available as lambda at PL Zoo. See repl-in-browser for an implementation that runs in the browser (an instance of which is available here).


Physical layer services & hardware protocols I am searching the content of this topic but I am not sure what should be the content for this topic. This is relate to Computer Network.
My topic is Physical layer services & hardware protocols.

What should be content for this topic.

Just a quick answer:

Hardware protocols are at the lowest level of the Open System Interconnection (OSI) model and are usually a mix of

hardware specifications (cables, connectors,  signals, ...)
how data is exchanged between the hardware devices (start of communication, end of communication, data exchange, flow of control, timings, error handling, ...)

Typical examples of hardware protocols are: serial port RS-232, Parallel port IEEE 1284, USB , Ethernet, bus protocols, ...

Physical layer services are those functions used to correctly implement and manage the communication between devices at the physical layer: e.g. open a port, convert bits to timed signals, change the bit-rate, close a port, send data, multiplexing, flush data,  ...


A technical clarification on subgraph isomorhism Let $G$ be a graph on $|\mathcal{V}(G)|$ vertices. If $H$ is another graph that contains a clique of size $|\mathcal{V}(G)|$, then does it mean $G$ is subgraph isomorphic to $H$? Does this mean that all graphs with vertices less than $|\mathcal{V}(G)|$ are subgraph isomorphic to $H$?

If the above is not the case, is there another term for the exact presence of $G$ in $H$ as a structure preserved subgraph (when I say structure preserved, that means, edges are mapped to edges and non-edges are mapped to non-edges in the subgraph of $H$)?

The subgraph isomorphism problem is "Is $G$ isomorphic to some subgraph of $H$?" so, yes, if $H$ contains a $k$-clique, that clique on its own has subgraphs isomorphic to any graph on $k$ or fewer vertices. Your "exact presence" version is the induced subgraph isomorphism problem: is $G$ isomorphic to some induced subgraph of $H$? Both versions are NP-complete.

You could have found this trivially by Googling for "subgraph isomorphism problem".


Cover the maximum of elements I have a collection of subsets $\{S_1,\ldots,S_m\}$ where each $S_i\subset \{1,\ldots,n\}$. I would like to cover the maximum number of elements from $\{1,\ldots,n\}$ by choosing a single element from each $S_i$. What is the optimal way to do this?

For example, say I have $S_1=\{1\}$ and $S_2=\{2,3\}$ and $S_3=\{3\}$ and $n=3$. If my algorithm picks randomly (or the maximum number say) a number from each $S_i$, then I could obtain a solution that covers only $\{1,3\}$ but there is a solution that covers all elements.

This problem is the same as the problem of finding the maximum matching in bipartite graphs, which can be solved by the Ford-Fulkerson algorithm in $O((n+m)s)$ time or the Hopcroft-Karp algorithm in $O(\sqrt{n+m}s)$ time, where $s$ is the number of elements in all $S_i$ combined.

Given a collection of subsets $\{S_1,\ldots,S_m\}$ where each $S_i\subset \{1,\ldots,n\}$, let $G$ be the graph with nodes $\{1, 2, \cdots, n, S_1,S_2,\cdots,S_m\}$. Whenever $j\in S_i$, there is an edge $e_{j,S_i}$ in $G$ that connects node $j$ and node $S_i$. $G$ is a bipartite graph with vertex sets $X=\{1, 2, \cdots, n\}$ and $Y=\{S_1,S_2,\cdots,S_m\}$

Suppose we have selected $k_i$ from $S_i$ for all $i$. Having removed duplicate numbers among ${k_1}, {k_2}, \cdots, {k_m}$, we can assume $\{k_i\mid i\in I\}$ for some $I\subseteq
\{1,2,\cdots,m\}$ is the set of distinct numbers among them. Then $\{e_{k_i, S_i}\mid i\in I\}$ is a matching in $G$.

Conversely, if we have a matching $\{e_{k_i, S_i}\mid i\in I\}$ in $G$ for some $I\subseteq \{1,2,\cdots,m\}$, we can select $k_i$ from $S_i$ when $i\in I$ while selecting any element from $S_i$ when $i\not\in I$.

The above two conversions show that the problem in the question, finding the maximal number of selected elements is the same as the problem of find the cardinality of the maximum matching in a bipartite graph. Note that the conversion takes linear time or polynomial time depending on which parameters are used.

Here is a variation for which I do not know if there exists a polynomial algorithm.

Problem. What if we select two elements from each set, assuming each set has at least two elements?


if traveling salesman problem is decidable in polynomial time, can an actual solution be proposed in polynomial time? I'm asking because it seems that P problems refer to decision problems rather than actually propose a solution.

If you have available a TSP decision oracle -- that is, a function that answers questions of the form "Does directed graph $G$ have a TSP tour of length at most $k$?" in constant time -- then the following algorithm will allow you to construct an actual TSP tour using $O(|E|)$ calls to the oracle, and $O(|E|^2)$ time overall:

Run a binary search on $k$, calling the decision oracle at each step, to determine $OPT$, the minimal tour length of the original graph $G$.  (If necessary, the absence of any Hamiltonian cycle at all can be first tested for by calling the oracle with a very large threshold -- e.g., equal to the sum of all edge weights.)
If $G$ contains 3 or fewer edges, then stop.  (These must form a triangle.)
Choose an arbitrary vertex $u$ in $G$.
For each out-edge $uv$ in $G$:

Create a new graph $G'$, which is the same as $G$ except that the edge $uv$ has been collapsed (specifically: delete vertices $u$ and $v$ and all edges they are incident on, and create a new vertex $x$ that has all of $u$'s incoming edges and all of $v$'s outgoing edges).
Run the decision oracle on $G'$ with the length threshold $OPT-w(uv)$.
If the answer is YES, then some optimal solution to $G$ contains the edge $uv$: Replace $G$ with $G'$ and $OPT$ with $OPT-w(uv)$ and go to 2.
If the answer is NO, then no optimal solution to $G$ contains the edge $uv$: Delete $uv$ from $G$, and continue iterating through other out-edges of $u$ in $G$.

The iterations in the loop beginning at step 4 execute at most $|E|-3$ times.  How quickly the graph modification steps (edge collapsing, edge deletion) in each iteration can be performed probably depends on the graph representation used, but they can certainly be done in $O(|E|)$ time each, for $O(|E|^2)$ time overall, which is enough to show the algorithm is polynomial.  (Can anyone think of faster $O(|V|)$ or even $O(|1|)$ ways to perform these modifications?)

The above runs on a directed graph $G$.  If you have an undirected graph, you can first turn each undirected edge into a pair of opposite-facing directed edges having the same weight, and then run the algorithm as before.


What's the complexity of calculating the shortest path from $u$ to $v$ with Dijkstra's algorithm using binary heap? Problem: Consider a graph $G = (V, E)$ on $n$ vertices and $m > n$ edges, $u$ and $v$ are two vertices of $G$.
What is the asymptotic complexity to calculate the shortest path from $u$ to $v$ with Dijkstra's algorithm using Binary Heap ?

To clarify, Dijkstra's algorithm is run from the source and allowed to terminate when it reaches the target. Knowing that the target is a neighbor of the source, what is the time complexity of the algorithm?
My idea:
Dijkstra's algorithm in this case makes $O(n)$ inserts ( $n$ if the graph is complete) and 1 extract min in the binary heap, before calculate the shortest path from $u$ to $v$.
In a binary heap insert costs $O(\log n)$ and extract min $O(\log n)$ too.
So the cost in my opinion is $O(n \cdot \log n + \log n) = O(n \log n)$
But the answer is $\Theta(n)$, so there is something wrong in my thinking.
Where is my mistake?

Your answer actually depends on what implementation of Dijkstra's algorithm is used. The textbook implementation inserts all nodes in the queue, and then proceeds with the extraction. The other starts with only the source in the queue. This is generally more efficient in practice, although it needs a bit of book-keeping.

For the standard implementation, you can do better than $O(n \log n)$. Instead of successively inserting each node in the heap based queue, you create an array, and "heapify" it. "Heapify" is a bulk operation for converting a list of numbers into a heap, in $O(n)$, or rather $\Theta(n)$ (see here or here). After that, there will be only one/two extract-min operations (one or two depending on whether the source is originally in the queue or not) in $O(\log n)$. So overall, $\Theta(n)$.

For the other implementation, you can do it in $\Theta(\Delta \log \Delta)$, where $\Delta$ is the degree of the source $u$.


Help with proof involving weighted full binary tree Given a full binary tree, $T$ (each node is either a leaf or possesses exactly two children), with $n$ leaf nodes: $v_1,v_2,...,v_n$, and weights associated with the leaf nodes: $w_1,w_2,...,w_n$, the cost of the tree, denoted by $|T|$, is defined as:  $$|T|=\sum_{i=1}^{n}w_il_i$$
Where $l_i$ is the depth of $v_i$ in $T$.

Example:

The cost of the above tree is:
$0.25\times 4+ 0.18\times 4+0.5\times 3+0.4\times 2+0.31\times 3+0.2\times 4+0.1\times 4+0.65\times 3+0.2\times 3=8.7$

Now, I need to prove two things. I'll start with the first.
1. Let $T$ be a full binary tree with $n$ terminal (leaf) nodes, then $T$ has $n-1$ internal nodes.

The proof for this is not too difficult. Using induction on the number of terminal nodes, I can easily prove it. The second is not so trivial, and this is where I need help. Before I'll move on to what I'm trying to prove, I'll introduce another concept.
Let's associate now weights with internal nodes: the weight of an internal node is the sum of the weights of its two children.
Example:

Now for the shocker:

Given a full binary tree, the sum of the $n-1$ internal nodes is the cost of the tree.

This looks surprising at first, but when you rethink about it, it makes sense (the picture above demonstrates it). My problem is proving it.
I tried proving by induction, but I got stuck in the inductive step (the base case is obvious).

Any help would be greatly appreciated.

**EDIT

Let me show exactly where I'm stuck:

Base case is easy.
The first way @Yuval Filmus suggested:
For the general case, since the number of leaves $n$ is bigger than $1$, then the tree can be split to two trees; the left subtree of the root, call it $T_l$ and the right subtree of the root, call it $T_r$, each has $n_l$ and $n_r$ leaves ($n_r,n_l\geq 1$ and $n_l+n_r=n$).
Now, according to the induction hypothesis, the cost of $T_l$ is the sum of the $n_l-1$ internal nodes in $T_l$, and the cost of $T_r$ is the sum of the $n_r-1$ internal nodes in $T_r$.
I don't know what exactly does that imply with regards to the entire tree $T$...

The second way @Yuval Filmus suggested:
For the general case: $T$ (with its $n$ leaves) is obtained from a smaller tree, call it $T'$, in which two leaves was removed.
According to the induction hypothesis, the cost of $T'$ is the sum of its $(n-1)-1=n-2$ internal nodes.
Again, how should I proceed? I feel like something is missing...
So suppose I say the cost of $T'$ is: $|T'|=\sum_{i=1}^{n-2}w'_i$, where $w'_i$ corresponds to an internal node. (it is denoted with apostrophe on purpose, to distinguish these weights from the $w_i$s - the weights of the terminal nodes).
Am I on the right track?

There are two basic induction patterns for (non-empty) full binary trees:

A tree is either a leaf or consists of a root and two full binary subtrees.
A tree is either a leaf or can be obtained from a smaller full binary tree by adding two children to a leaf.

Your first question can be proved in both ways. In both cases, the base case is clear: if a tree is a leaf then it has $n=1$ leaves and $n-1=0$ internal nodes.

According to the first way, if the tree $T$ is not a leaf then it has a root and two subtree $T_1,T_2$. By induction we know that if $T_1,T_2$ have $n_1,n_2$ leaves (respectively) then they have $n_1-1,n_2-1$ internal nodes (respectively), and together with the root, this gives $n_1+n_2-1$ internal nodes for $T$, which is exactly one less than the total number of leaves.

According to the second way, the tree $T$ is obtained from a smaller tree $T'$ by adding two children to a leaf. If $T'$ has $n'$ leaves and $n'-1$ internal nodes, then $T$ has $n'-1+2 = n'+1$ leaves and $n'-1+1 = n'$ internal nodes, exactly one less than the number of leaves.

Your other statement can also be proved in both ways. I leave you the details.


Datalog Self Interpretation According to https://link.springer.com/article/10.1007%2Fs001530050135 (Logics that define their own semantics, Imhof 1999) the logic FO[LFP] can define its own semantics, though the proof (of corollary 6.4) is somehow fuzzy. It is known from finite model theory that Datalog is equivalent to FO[LFP] (on ordered structures). Can someone help me see (at least partially) how to write a Datalog self-interpreter? The main difficulty is to express modus-ponens considering unification without involving existential variables in heads (i.e. variables in heads which don't appear in bodies and are understood to be existentially quantified).

Another related puzzle of mine is, if LFP's data complexity is P, and its query complexity is EXPTIME, how come it can interpret itself indeed? (I have no doubt that it can as the paper above supplied two different proofs for that. also we know that provably P!=EXPTIME)

Partial answer only.

For me, the paper is behind a paywall. So I can base this only on its abstract and your question.

I believe you have a point with your complexity doubts. I can see how to write an FO[LFP] self-interpreter, provided there is a way to handle large arities. In particular, the self-interpreter has a single, fixed, maximum arity and number of variables while the interpreted formulae should be unbounded with respect to arity and number of variables. I can see a few ways to go about that:

There is in fact not a single self-interpreter, but a family of such, indexed by maximum arity.
The structure that encodes the input (the formula plus the original structure) has in its domain not only (subformulae of the formula and) elements of the original structure, but also tuples of the original structure up to the required arity. Then, converting the original input into its encoding structure already imposes an exponential blowup.
For infinite structures, tuples can be encoded as single elements using a pairing function. On well-ordered structures, FO[LFP] can define (ordinal) arithmetic and hence such a pairing function. Possibly, the statement in the paper does not address finite structures at all?

For the Datalog self-interpreter, I suggest you start with a Datalog interpreter written in FO[LFP] and then convert that formula into a Datalog query.


Is Knapsack restricted to integers between 1 and 100 still NP-complete? The title pretty much says it all. I want to know if Knapsack is still NP-complete when the weights, values, and weight limit are restricted to a finite set of values. I figure that it wouldn't be because clearly for very small finite sets it isn't. (E.g., if you must use integers from 1 to 3.) That said, I'm struggling to find a polynomial-time algorithm.

One thought I had was since there are a finite set of possible inputs and outputs, could your algorithm just be a massive chain of if statements? I'm not sure whether this even would count as an "algorithm" though.

Let $V(i, W)$ be the maximum sum of the values of the items among the first $i$ items so that the sum of the weights is less than or equal to $W$, then we have

$$V(i, W)=\max\{V(i-1, W), v_i+V(i-1,W-w_i)\}$$

where $v_i$ and $w_i$ are respectively the value and the weight of the $i$th item. Suppose there are $n$ items and the capacity limit is $W_\max$, then the problem is equivalently to compute $V(n, W_\max)$. We can use the recursion formula above to compute the following values in order: $$V(1,1),\ldots,V(1,W_\max),V(2,1),\ldots,V(2,W_\max),\ldots,V(n,1),\ldots,V(n,W_\max).$$

This is the classical dynamic programming method to solve the Knapsack problem. Since it takes $O(1)$ time to compute each $V(\cdot,\cdot)$ and there are $O(nW_\max)$ such values to compute, the overall running time is $O(nW_\max)$. Since you restrict $W_\max\le 100$, the overall running time becomes $O(100n)=O(n)$, which  is indeed polynomial in $n$.


What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements? What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements?

I.e. What is the link between the language and the algorithm

A Turing Machine implements an algorithm.

The algorithm will either accept, reject or loop forever on certain inputs.

If we collect all of the inputs that the Turing Machine halts and accepts on. This is the associated language recognised by the Turing Machine.


The task of recognizing game units in the screenshot I'm new to computer vision and I want to solve the task of recognizing the game units of the game Clash Royale in the screenshot.
Briefly, there are about 70 different types of gaming units belonging to two teams (they differ a little in colors and some are visible in front, others with backs). I want to find game units on the screenshot and classify their type of unit (then health and the team).

What are the best tools for task like this? What libraries will I use to simply teach the model? How many teaching examples do I need to learn the model? It seems that the quality of the screenshots is quite good and the images are clear. To what size should I reduce the screenshoot to get a good model and its speed? Maybe someone had a similar experience?

I think about CNN or a lot of HAAR cascades for each of the types of units, but I would like to receive advice.

Machine learning doesn't seem needed, since the image of each unit is always identical.  One approach is to obtain a clean image of each unit, and then use template matching to find all locations where the template occurs in the screenshot.  You might be able to check all locations in the screenshot whether they exactly match the template image (you will probably want to mask out the part where the health appears, as that will obscure the image).  This can be done very efficiently.

To recover the health, you might also be able to do template matching on the numbers 0-10.

The way to tell what resolution you can downsize to is empirically: you experiment with different resolutions and measure the accuracy for each.  There's probably no way to predict without trying it.

If you want to try machine learning, you could try a CNN, or better yet, you could try retraining the YOLOv3 object detector for your particular images (see, e.g., the YOLO project page or here).  You will probably need a larger training set this way, and you'll have to do a bunch of manual annotation of sample screenshots.

Tool and library recommendations are off-topic here.


Simulating continuous time semi-Markov state machine and changing transition probability on the fly The problem that I'm trying to solve (well, I think that I almost did, but need a review from someone more experienced) is about changing probability of the transition for semi-Markov state machine during simulation.

Let's assume that M=<S,T> defines machine with S states and T probabilistic transitions between states. Elements of T are triplets (s_out, s_in, lambda). So the probability of moving from state s_out to s_in is exponential and defined as exp(-lambda*t).

To simulate it I get random value from [0;1), transform it to exponential and save as next event. What happens is that after saving it but before invoking another event may occur (so it is not a pure Markov state machine) and change the lambda. So the event time should be recalculated.

The problem is that it cannot be just recalculated as such changes may occur quite frequently constantly shifting the event time to the future.

What I think is correct is to adjust recorded event time on ratio time_to_event_from_now * lambda_old / lambda_new. Does it sounds right to you? Maybe the problem description recalls the paper/book where this problem solved?

As it happens, recalculating the event time is exactly the right thing to do.  This follows from the fact that the exponential distribution is memoryless; or from the fact that exponential distribution is the time until the next event in a Poisson process.  I realize this might sound miraculous and unbelievable, so let me explain why, in detail.

Let's suppose that at time $t_0$ you have lambda equal to $\lambda_0$; then at time $t_1$, lambda changes to the value $\lambda_1$.  In other words, at every point in the time interval $[t_0,t_1)$, the value of lambda is $\lambda_0$; at every point in the time interval $[t_1,t_2)$, the value of lambda is $\lambda_1$.

You are simulating a Poisson process with parameter lambda.  During the time interval $[t_0,t_1)$, the Poisson process has parameter $\lambda_0$.  During time interval $[t_1,t_2)$, the Poisson process has parameter $\lambda_1$.  You want to simulate this process.  In particular, you want to simulate the time of the first event.

The brute-force way to simulate this process would be to divide time up into very small increments, say of length $\epsilon$, so that time is broken up into small intervals $[t_0,t_0+\epsilon)$, $[t_0+\epsilon,t_0+2\epsilon)$, $[t_0+2\epsilon,t_0+3\epsilon)$, ..., $[t_2-\epsilon,t_2)$.  In each interval, you have a value for lambda: its value is $\lambda_0$ for the first $(t_1-t_0)/\epsilon$ small intervals and $\lambda_1$ for the next $(t_2-t_1)/\epsilon$ small intervals.  In each small interval, you draw from a Poisson distribution with parameter $\lambda \epsilon$ (i.e., $\lambda_0 \epsilon$ or $\lambda_1 \epsilon$, depending upon whether the small interval falls before or after $t_1$).  Because $\lambda_i \epsilon$ will be a very small value, this is essentially equivalent to flipping a biased coin for each small interval; with probability $\lambda_i \epsilon$, you say that the event has happened in that small interval, and with probability $1-\lambda_i \epsilon$ nothing happens in that small interval.

Thus, this gives you a brute-force strategy to simulate your process.  This brute-force strategy will give you the right distribution of events.  However, it has the disadvantage that it is computationally expensive: it requires $(t_2-t_0)/\epsilon$ coin flips.

Fortunately, there is an equivalent way to do it that yields the same distribution of events, but is much more computationally efficient.  Here is the optimized strategy for how to simulate the time of the first event:

Randomly draw a value $d$ from the exponential distribution with parameter $\lambda_0$.  If $d<t_1-t_0$, then output that the first event happens at time $t_0+d$.
Otherwise (if $d \ge t_1-t_0$), randomly draw a value $d'$ from the exponential distribution with parameter $\lambda_1$ (independent of $d$).  Now, if $d'<t_2-t_1$, then output that the first event happens at time $t_1+d'$; otherwise, output that no event happens during $[t_0,t_2)$.

This optimized strategy lets you simulate the time of the first event.  (If you want to simulate the time of all events in the interval $[t_0,t_2)$, you can simulate the time of the first event, if any, and then iterate to figure out the time of the next event if there was a first event, repeating until done.)  It is efficient, as you can see.

Moreover, this optimized strategy gives the correct distribution.  It is  equivalent to the brute-force method described above: it gives the same distribution on the time of the first event (as $\epsilon \to 0$).  The equivalence follows from the fact that, if you have a Poisson process with parameter $\lambda$, then the time of the first event is exponentially distributed with parameter $\lambda$.  (See Wikipedia.)

Finally, you can note that my optimized strategy is exactly equivalent to recalculating whenever lambda changes.  It follows that recalculating whenever lambda changes does give you the right answer.  Amazing, huh?

Don't expect this to work for all distributions.  This is a special property of the exponential distribution.


How do we generate a depth-first forest from the Depth First Search? I was trying to implement an algorithm which finds the strongly connected components (SCC's) of a directed graph. In order to find the SCC's, as the last step we need to be able to generate the Depth-First Search Forest as mentioned in CLRS:

STRONGLY-CONNECTED-COMPONENTS (G)

 1. Call DFS(G) to compute finishing times f[u] for all u.
 2. Compute G^T
 3. Call DFS(G^T), but in the main loop, consider vertices in order of decreasing f[u] (as computed in first DFS)
 4. Output the vertices in each tree of the depth-first forest formed in second DFS as a separate SCC.

However, I did not understand how to generate the DFS Forests from the Depth First Search. Please explain me how is it possible, and preferably use Cormen's DFS Psuedocode as I am a beginner and am quite familiar with CLRS.

Below is Cormen's DFS psuedocode:

DFS (V, E)

1.     for each vertex u in V[G]
2.        do color[u] ← WHITE
3.                π[u] ← NIL
4.     time ← 0
5.     for each vertex u in V[G]
6.        do if color[u] ← WHITE
7.                then DFS-Visit(u)              ▷ build a new DFS-tree from u

DFS-Visit(u)

1.     color[u] ← GRAY                         ▷ discover u
2.     time ← time + 1
3.     d[u] ← time
4.     for each vertex v adjacent to u     ▷ explore (u, v)
5.        do if color[v] ← WHITE
6.                then π[v] ← u
7.                        DFS-Visit(v)
8.     color[u] ← BLACK
9.     time ← time + 1
10.   f[u] ← time                                 ▷ we are done with u

PS: Rest assured, this is not homework.

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

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


Job Shop Problem: How do you get an ordered sequence of operations from the disjunctive acyclic graph? Intro
The job shop problem is a classic scheduling theory problem. Given $N$ jobs and $M$ machines, a typical goal of the JSP is to minimise the makespan (starting time of the last operation + its processing time) over the set of jobs. Jobs must be processed on a sequence of machines in a particular order. An operation refers to a particular job being processed on a particular machine.

Representation
A disjunctive graph is typically used to represent the problem of minimising makespan. Each node in the graph is labelled $(i,j)$ where $i$ refers to the job, and $j$ to the machine on which the job is to be run. Conjunctive arrows between nodes indicate precedence constraints for a particular job. Each conjunctive edge is given a weight, corresponding to the processing time $P_{i}$ for the particular operation $O_{i}$ at the base of the edge. Disjunctive edges are placed between operations that take place on the same machine. An example of two simple jobs is given below:

Note that $J_{1}$ is comprised of the upper row of nodes, and $J_{2}$ the lower row.

Problem
My problem is with the terminology used to describe how to solve the JSP. The book "Scheduling Theory, Algorithms, and Systems" (Pinedo, 2008) states on page 181 that:

A feasible schedule corresponds to a selection of one disjunctive arc from each pair such that the resulting directed graph is acyclic

However, if I do just that, I can derive a graph that looks something like this:

Now, it is said that:

The makespan of a feasible schedule is determined by the longest path in G(D) from the source U to the sink V

And if I sum the longest weighted path, I can indeed derive a "makespan" value. However, I still don't get why this is a "feasible schedule". Because I don't really have a schedule at all. The path doesn't give me an ordering for how to execute the callbacks. That is because the path necessarily does not visit every operation. Meaning that it does not give a feasible schedule at all.
Verdict
In light of what I have described above, my question is: How can I derive the full sequence of operations to perform from the disjunctive graph model of the job shop problem?
Edit: There's a mistake in my graph, the last edges going to $V$ should be labelled with a weight.

The graph consisting of all vertices corresponding to a particular machine and the induced chosen edges form a directed path. This path tells you exactly which jobs to run on that machine and in what order.
The length of the longest weighted path from u to a job tells you exactly when you can start processing that job.


What is the fastest algorithm to solve $k$-path problem? $k$-Path problem

The problem: Given a graph $G$ with $n$ vertices and $m$ edges, does there exist a path of length $k$ in the graph?

The trivial algorithm to solve is in $O^*(n^k)$ time using dynamic programming. ($^*$ hides the polynomial factor.)

Question: What is the fastest algorithm for the $k$-Path problem?

For FPT algorithms (ignoring the polynomial factors), there is a $2.851^k \cdot n^{O(1)}$ deterministic algorithm and a $1.66^k  \cdot n^{O(1)}$ randomized algorithm.

See Table of FPT races for references.