Random forests on monotone training set yields a monotone classifier? Suppose I train a random forests classifier on a monotone training set.  Is the resulting classifier guaranteed to be a monotone function?

Suppose I apply the ID3 algorithm (the greedy algorithm) to learn a decision tree on a monotone training set.  Is the resulting decision tree guaranteed to be a monotone function?

I can formalize this a bit more precisely.  Recall that a function is monotone if $x \le y$ implies $f(x) \le f(y)$, where we define $\le$ on $\{0,1\}^n$ by pointwise comparison ($x \le y$ if $x_i \le y_i$ for all $i=1,2,\dots,n$).

Suppose we have a monotone boolean function $f:\{0,1\}^n \to \{0,1\}$, and suppose that we build a training set as some set of pairs $(x_i,y_i)$ where $y_i=f(x_i)$.  In other words, the training set is consistent with some monotone function, with no errors.

Now train a random forests classifier on a training set of this form.  This will learn a classifier that can be thought of as a map $g:\{0,1\}^n \to \{0,1\}$.  Is it guaranteed that the learned classifier will be a monotone function?  Alternatively, suppose we apply the ID3 algorithm on this training set.  (The ID3 algorithm is the obvious greedy algorithm for recursively building a decision tree that is consistent with the training set.)  Is it guaranteed that the learned decision tree will form a monotone function?

No, it's not guaranteed.  You can end up with a decision tree or classifier that is non-monotone.

Here is an explicit counterexample, i.e., a training set of 5 samples on 5 attributes:

$$\begin{align*}
&(01011, 0)\\
&(01101, 0)\\
&(00111, 1)\\
&(10110, 0)\\
&(11000, 1)
\end{align*}$$

This training set is monotone: it is consistent with the monotone function

$$f(x_0,x_1,x_2,x_3,x_4) = (x_0 \land x_1) \lor (x_2 \land x_3 \land x_4).$$

However, if you run the ID3 algorithm on this training set, you may end up with a decision tree that computes the function

$$g(x_0,x_1,x_2,x_3,x_4) = (\neg x_0 \land \neg x_1) \lor (x_0 \land x_1),$$

which is also consistent with the training set yet is not monotone.  In other words, ID3 might produce the following decision tree:

       x0
     /    \
    /      \
  x1        x1
 /  \      /  \
1    0    0    1

which is quite evidently non-monotone (there's an obvious violation of monotonicity in the lower-left part of the tree, where the tree says that the output should be the negation of $x_1$ -- clearly non-monotonic).

Why can ID3 produce this decision tree?  Starting with the entire training set, splitting on $x_0$ yields predictions (information gain) that is at least as good as splitting on any other attribute.  Then we recursively run ID3 on the subset of training samples where $x_0=0$ and recursively run ID3 on the subset of training samples where $x_0=1$, and on each recursive run we discover an attribute that provides perfect prediction.  Try running the ID3 algorithm by hand to see what I mean.

Now at this point perhaps you are going to object: the ID3 algorithm made a choice that is obviously stupid.  When the training set contained $(01011,0)$, $(01101,0)$, and $(00111,1)$, the algorithm noticed that $x_1$ provides perfect prediction of $y$, via the rule $y = \neg x_1$ -- but this is a stupid choice if we want to end up with a monotone classifier, since even without looking into the future we can immediately see that this is going to yield a non-monotonic result.

So it is natural to try to rescue the ID3 algorithm with a local pruning rule that, at each stage, only considers attributes that aren't obviously dumb -- that aren't obviously going to lead to a violation of monotonicity.  Here is one way we could try to operationalize that idea.  Let's adjust the ID3 algorithm to be locally monotone.  Normally, the ID3 algorithm chooses an attribute $x_i$ that reduces the information gain as much as possible.  We could adjust this to also require that we pick an $x_i$ that is locally monotone, i.e., the fraction of training set pairs with $x_i=0 \land y=1$ is at most the fraction of training set pairs with $x_i=1 \land y=1$.  (If $x_i$ is not locally monotone, then splitting on $x_i$ seems likely to yield a decision tree where we predict an output of 1 more often when $x_i=0$ than when $x_i=1$, which is a violation of monotonicity.)  Out of all locally monotone choices, we'll pick the attribute with the best information gain (or the lowest Gini impurity, if you prefer).

Unfortunately, even with this modification to enforce local monotonicity, ID3 can still fail to yield a monotonic decision tree.  When we run the ID3 algorithm on the above data set, we obtain a decision tree that computes the function

$$g'(x_0,x_1,x_2,x_3,x_4) = (\neg x_0 \land x_2 \land x_3) \lor (x_0 \land x_1),$$

which is consistent with the training set yet is not monotonic.  In particular, we might obtain the following decision tree:

       x0
     /    \
    /      \
  x2        x1
 /  \      /  \
0    x3   0    1
    /  \
   0    1

This decision tree achieves 100% accuracy on the training set, yet it isn't monotone, even though there exists another decision tree (of the same depth) that is monotone and also achieves 100% accuracy.

Why can ID3 produce this decision tree?  Starting with the entire training set, splitting on $x_0$ yields predictions (information gain) that is at least as good as splitting on any other attribute.  Then we recursively run ID3 on the subset of training samples where $x_0=0$ and recursively run ID3 on the subset of training samples where $x_0=1$, and similar comments apply at each stage of the algorithm.  I'll let you run ID3 by hand and see that there is a way to resolve ties at each step that yields the decision tree above.

In short, we can potentially lose either way, whether or not we apply the "locally monotone" constraint.  We might get lucky and end up with a monotone decision tree, but there is no guarantee of that -- we also might unlucky and end up with a non-monotone decision tree, even though there exists a monotone decision tree that would be at least as good.

Similar comments apply to the random forests algorithm, as it merely applies the ID3 algorithm multiple times.  (Each tree is learned on a different subset of the training set, and with different subsets of the features at each node of the tree, but the same kind of anomaly can still occur.)

This proves that it is at least possible to end up with a non-monotonic classifier, even when starting from a monotone data set.  I don't know how likely it is that this will happen in practice, though, when taking the probability over the random choices made in the ID3 algorithm (to resolve ties) and in the random forests algorithm (for bagging and feature subsetting).

In other words, this demonstrates that if our goal is to learn a monotonic classifier, it's not enough to simply apply the standard random forests or ID3 training procedure on a (monotone) training set; something more sophisticated is needed.


P versus NP and what we are looking for I was reading the other day about this problem, refreshing it, and on a couple of places over the internet I read somebody explaining something in the line of '..does not matter as long as is polynomial, a N^20 or N^30 will do it, we know that maybe the solution does not make the problem tractable but if we can produce an algorithm having polynomial time complexity that will be good enough..."

My educated guess makes me think, that, if we can have a polynomial tractable algorithm , with today's computing resources, then that will be great, because we can use the solution, but looks like for P vs NP question as long as is polynomial that would be all.

How accurate are the comments I found on the internet?

P vs NP is settled as soon as we find a $O(n^k)$ algorithm for an NP-complete problem (for any constant $k$) or show that no NP-complete problem has such an algorithm.

Whether or not $k$ is too big to yield a tractable algorithm is a different problem. Having a practical algorithm for, say, SAT, would indeed be very useful, many problems we currently solve heuristically (e.g. in chip design) could then be solved to optimality.


How to convert CFG with Kleene Star, Kleene Plus, and Question Mark to Chomsky Normal Form? I am fairly new to formal language theory but understand how to convert simple CFGs into both Chomsky normal form and Greibach normal form. However, I have not seen any examples of how to do that when you add the Kleene Star *, Kleene Plus +, and question mark ? to that grammar, commonly seen in regular expressions.

How do you do convert CFG's with Kleene Star/Plus, and question mark, to CNF?

Say the grammar is like this:

S -> A+
A -> BX?
B -> a+ // letters
X -> ! // exclamation

How do you convert this to Chomsky Normal Form, given that it uses *, +, and ?? In particular, I am wondering what the general pattern is to convert the Kleene Star/Plus and question mark to CNF, not necessarily how to do it in this example, but whichever is easiest to demonstrate.

Is it something like this?

// first step
S -> A+
A -> BX?
B -> a+
X -> !

// replace + with *
S -> AA*
A -> BX | B
B -> aa*
X -> !

// replace * with new rules and ɛ
S -> AI
I -> A | ɛ
A -> BX | B
B -> aJ
J -> a | ɛ
X -> !

// replace X -> aY with X -> ZY and Z -> a
S -> AI
I -> A | E
A -> BX | B
B -> KJ
J -> K | E
X -> !
K -> a
E -> ɛ

I am just guessing here, not sure how it is typically done. Also, from the few resources I have found, it sounds like you are supposed to also remove the epsilon rules somehow. There doesn't seem to be many thorough online resources demonstrating this though, any book recommendations?

How do you do convert CFG's with Kleene Star/Plus, and question mark, to CNF?

I propose a two-step solution:

Convert your extra-notation-CFG to a normal CFG
Convert the normal CFG to CNF, e.g. as described on Wikipedia.

Do perform step 1, removing the extra notation, apply these rules:

Whenever $A^+$ occurs in a production rule, replace it with $AA^*$.
Whenever $A^*$ occurs in a production rule, replace it with a new non-terminal $B$ and add rules $B \rightarrow \varepsilon$ and $B \rightarrow AB$.
Whenever $A?$ occurs in a production rule, replace it with a new non-terminal $B$ and add rules $B \rightarrow \varepsilon$ and $B \rightarrow A$.

It should be relatively straightforward to see that the transformed versions of +,*,? repeat the argument k times, where k is in $\{1, \ldots\}$, $\{0, \ldots\}$ and $\{0, 1\}$, respectively; i.e. the rewritten version has the same meaning (language) as the input.

To perform step 2, read the Wikipedia article; it is reasonably straightforward (if a bit tedious) to translate this into an algorithm.


Prove a TM problem is NP-complete Question: Show that $T_{NP}$ is NP-complete, where $$T_{NP} = \{m\#w\#^c\mid M_m\text{ is an NTM};M_m(w)\text{ has an accepting computation of $\leq$ c steps}\}$$

This question looks weird to me because itself is a TM.  In general, when we say a problem is in NP, we can give an instance of that problem and using NTM to guess and verify. However, since $T_{NP}$ is a NTM, can we simply say using $T_{NP}$ itself to guess and verify in polynomial time?

Also, for the reduction part, I'm not sure but I think 3SAT is reducible to $T_{NP}$ because each clauses in 3SAT formula $\phi$ is true iff each step in $T_{NP}$ is valid.But I'm still stuck on the detail proof and argue the correctness at this moment. Any suggestion?

Let us first show that $T_{NP}$ is indeed in NP. Given an input, $m\#w\#^c$, nondeterministically guess a sequence $r$ of nondeterministic choices for $M_m$ of length $c$, simulate $M_m$ on $w$ for $c$ steps using $r$, and accept if $M_m$ accepts. This nondeterministic algorithm accepts iff $m\#w\#^c \in T_{NP}$. Furthermore, it runs in polynomial time in the input size (here it is crucial that the input contains $\#^c$ rather than $c$ encoded in binary).

To show that $T_{NP}$ is NP-hard, you can just use the definition. Suppose that $M$ is an NP machine. Then $M = M_m$ for some $m$, and $M$ runs in time $P(n)$ on an input of length $n$. Given an input $w$, map it to $m\#w\#^{P(|w|)}$. It is clear that $M_m$ accepts $w$ iff $m\#w\#^{P(|w|)} \in T_{NP}$. The reduction is polynomial since $P(n)$ is a polynomial.


Is the superset and subset of a semi-decidable language also semi-decidable? Given three languages $L_1, L_2, L_3$ with $L_1$ and $L_3$ being semi-decidable and $L_1 \subseteq L_2, L_2 \subseteq L_3$. Can I deduce from these properties, that $L_2$ is also semi-decidable and how would I proof this?

Intuitionally it seems obvious that $L_2$ is also semi-decidable, but I didn't find a way to prove (or falsify) it.

So far I only found information about the closure of semi-decidability under $\cup$ and $\cap$. Can I use these properties in any way?

No, because every language $L$ satisfies $$ \emptyset \subseteq L \subseteq \Sigma^* $$ and $\emptyset$ and $\Sigma^*$ are both semi-decidable.


How are the control signals derived in the MIPS pipeline? NOTE: Let me point out that I did try extensively to solve this on my own. The problem is that, based on that circuit, it would appear that this processor cannot jump. At best the jump instruction will propagate through the pipeline with no effect. There is no data path defined for a jump that tells the processor to change the PC. The only thing that changes the PC (aside from the normal PC+4) is a beq.

I'm learning about MIPS pipelining and stages, but what is excruciatingly unclear is how a jump instruction is executed. On an assignment question, I'm asked to trace the pipeline with the command "j 16", but there does not appear to be any details about how the logic is handled. The closest thing I can find of any relevance is to do with beq, but the opcodes are different... beq is 000100 and j is 000010. The following table outlines how the control codes work for four classes of opcodes, but it doesn't explain what happens for jump, and subsequently, how the machine knows to jump and what it does with the command...

So, if I have the instruction 000010 00000000000000000000000100, how does this get handled by the data path?

You are correct. The above data path doesn't have the parts that support jump instruction. Yet, those are easy to add.

The pipelined datapath in your question is based on a single-cycle MIPS that doesn't support jumps (Figure 5.21 in Patterson and Hennessy). In order to add jump support, consider the single-cycle MIPS datapath of Figure 5.24; then add the jump parts to the pipelined architecture.

However, note that jumps and branches must be treated correctly in order to avoid control hazards - specifically, new instructions that entered the pipe after the jump should not be executed. The complete datapath that takes care of control hazards (again, for branches only) appears in Figure 6.41.


Give an implementation leveldescription of a TM L = {x=y ⊕ z|x, y, z are binary integers, and x is the XOR of y and z}

is non-regular, i.e., no FA exists that could recognize the language. How can I give an implementation level description of a TM that decides on L?

There is an important gap between human reasoning ("high level") and the formal definition of a Turing Machine ("low level").
If you are approaching these exercises for the first time and you are not yet familiar with TMs, what I recommend is to write down a pseudocode description of the algorithm which is nothing more than a high level description of the Turing machine itself)
and then to "break up" the algorithm into smaller entities, until the transition function of the machine is achieved.

In the case of your example you can consider $x$, $y$ and $z$ as binary encodings of integers, then you need a function that does the following:

Read the input $($$x$, $y$, $z$$)$
Compute $y \oplus z$
Compare  $($$y \oplus z$$)$ to $(x)$

If the equality in point 3 is verified, accept the language.
This TM will always accept membership in your language $L$.


Has this model of random directed graphs been studied? Youtube recently added a feature called autoplay, where each clip is assigned a (presumably related) clip that follows it. This, in effect, defines a directed graph on the set of youtube clips, where each vertex has outdegree 1. The user starts at a vertex of his choice and takes a walk along this graph.

This got me thinking. Since the graph is finite, the user will eventually get stuck in a loop. Each loop acts as a sink, and each vertex will eventually lead the user to some sink. This raises some questions - how many sinks are there? How many steps does it take before the user reaches the loop? What is the distribution of the sink sizes? And so on.

Here is a random graph model that can be used to model this process: For each vertex $v$ we choose a single neighbor $w$ uniformly at random and add the edge $(v,w)$ to the graph. It might be interesting to investigate the properties of this model and to see if they can teach us anything about the Youtube network. Have people looked at this type of thing before?

It is very easy to say something about the expected length before you get stuck in a loop: if there are $n$ videos, it will (starting from a random video) take in expectation $\Theta(\sqrt{n})$ videos before you loop around (the actual value is around $1.25\sqrt{n}$). This is effectively the birthday problem, since each time you draw a video at random.

Since each video in the chain of $\Theta(\sqrt{n})$ videos is equally likely to be the one you loop back to, the average length of a loop is also $\Theta(\sqrt{n})$ videos (actual value $0.625\sqrt{n}$).

This gives the expected length of the loop you end up in after starting from a random video. This means that a loop with many videos leading to it is counted more strongly. If instead you want to know the expected length of a loop if you pick a random loop, this may be found as $T(1)$, where

$$T(i)=\frac{n-i}{n}T(i+1)+\frac{i}{n}\frac{i+1}{2}$$

and $T(n)=\frac{n+1}{2}$. Computing the values of $T$ experimentally it seems to match up with $0.625\sqrt{n}$, so both ways of counting the expected loop length are the same.

Computing the expected number of cycles seems to be a harder problem. We start by counting the expected number of cycles of a given length. The probably that a node is part of a length-1 cycle is $\frac{1}{n}$, so there are in expectation $1$ length-1 cycles. The probability that a node is in a length-2 cycle is $\frac{n-1}{n}\frac{1}{n}$, so there are in expectation $\frac{1}{2}\frac{n-1}{n}$ length-2 cycles. In general, the number of cycles of length $l$ is $\frac{1}{l}\Pi_{i=1}^{l-1} \frac{n-i}{n}$.

We can obtain a crude upper bound on the number of cycles by considering $\Sigma_{i=1}^n \frac{1}{i} = H_n$ which is $O(\log n)$. Unfortunately the number of cycles doesn't seem to converge to $\log n$ so this bound is not tight.


Functional Programming and Parallelism I have  an option to learn a new language for parallel computing.  As a parallel programmer what are the reasons one might want to invest time to learn functional programming for parallel computing?

An important argument for learning one is that operations in a purely functional language does not have side effects.

In this case that means one operation cannot change the state of another parallel operation. That makes it much easier to reason about the behaviour of your program, since you don't need to account for all the possible combinations of states, but rather the input and output of each function.

Some functional languages have both purely functional operations and destructive operations (like Lisp and Scheme) and some have only the former (like Haskell). Which one you choose is dependent on what you are trying to solve.


Explain the proof of allocation problem The problem:

There are $N$ houses for sale. The $i$-th house costs $A_i$ dollars to buy.
You have a budget of $B$ dollars to spend.
What is the maximum number of houses you can buy?

There is an intuitive way to solve this problem in a greedy way: we must at first sort the house costs and then buy houses until we are out of money and it works.
and the proof is:

Let's prove the correctness of this greedy algorithm. Let the
solution produced by the greedy algorithm be $A = \{a_1, a_2, \ldots, a_k\}$ and
an optimal solution be $O = \{o_1, o_2, \ldots, o_m\}$.
If $O$ and $A$ are the same, we are done with the proof. Let's assume that
there is at least one element $o_j$ in $O$ that is not present in $A$.
Because we always take the smallest element from the original set, we
know that any element that is not in $A$ is greater than or equal to any
$a_i$ in $A$. We could replace $o_j$ with the absent element in $A$ without
worsening the solution, because there will always be element in $A$ that
is not in $O$. We then increased number of elements in common between $A$
and $O$, hence we can repeat this operation only finite number of times.
We could repeat this process until all the elements in $O$ are elements
in $A$. Therefore, $A$ is as good as any optimal solution.

I don't understand the proof and I have couple of questions:

What does it mean to replace $o_j$ with an absent element in $A$?
Why do we need to do it?

Could you explain this proof in a simpler way with examples?
You can see this problem here.

I don't like this proof so much. Here is a different one.
We can assume without loss of generality that $A_1 \leq \cdots \leq A_N$. Consider an optimal solution $\{i_1,\ldots,i_\ell\}$, where $i_1 < \cdots < i_\ell$. In particular,
$$
A_{i_1} + \cdots + A_{i_\ell} \leq B.
$$
Intuitively, it is clear that $A_1 + \cdots + A_\ell \leq B$ (we will prove this formally in a moment), and so the greedy algorithm will also choose at least $\ell$ houses.
Now let us prove that $A_1 + \cdots + A_\ell \leq A_{i_1} + \cdots + A_{i_\ell}$.
I claim that $i_j \geq j$. Indeed,
$$
i_j \geq 1 + i_{j-1} \geq 2 + i_{j-2} \geq \cdots \geq j-1 + i_1 \geq j.
$$
This implies that $A_{i_j} \geq A_j$, and so $A_{i_1} + \cdots + A_{i_\ell} \geq A_1 + \cdots + A_\ell$.


What is a not-well-founded cotree? I'm reading the paper "Dual of substitution is Redecoration".
And I'm struggling with understanding the usage of the word "not-well-founded cotrees".

what is a cotree compared to a tree ? I suspect it is a tree for which all relations are inverted, but it is just my assumption.
what it is to be "well-founded" for a tree, for a cotree.

Probably, to have an insight, it would be helpful to give me examples of a well-founded and of a not-well-founded tree/cotree.

I'm not sure what you mean by "all relations are inverted" (what's the relation of a tree?), but perhaps I can provide some insight.

In Haskell, one might write the type of binary trees as such:

data Tree = Leaf | Node Tree Tree

in the terminology of the paper, the type of "incomplete trees" would then be

data ITree a = Leaf | Node ITree ITree | Var a

allowing for an "incomplete" tree with holes marked by an instance of Var a. The paper observes that the type ITree a forms a monad, where a Var a can be "substituted" with f a given a suitable function f :: a -> ITree b.

Now our intuition is that the type Tree is the type of finite, or well-founded binary trees, of which an example is

 myTree :: Tree
 myTree = Node (Node Leaf Leaf) (Node Leaf Leaf)

However, it is untrue in a language like Haskell that all trees are of this form. Indeed, following definition is perfectly acceptable:

infTree :: Tree
infTree = Node infTree infTree

intuitively, this tree represents the infinite "full" binary tree. So really the type Tree may contain either finite binary trees, or trees which may contain infinite paths. Such trees are called non-well founded trees.

So, in Haskell, the type Tree is in reality the type of co-trees, which allows such elements as infTree. This may be a bit confusing, since we rarely think about such elements when considering that type.

Hopefully this provides useful intuition.

The main observation of the paper, is that the type of co-trees has a construction dual to that if ITree, which one might call DTree, defined as

 DTree a = DLeaf a | DNode a (DTree a) (DTree a)

such that we can define a comonad structure:

extract :: DTree a -> a
extract (DLeaf a) = a
extract (DNode a _ _) = a

duplicate :: DTree a -> DTree (DTree a)
duplicate (DLeaf a) = DLeaf (DLeaf a)
duplicate (DNode a l r) = DNode (DNode a l r) (duplicate l) (duplicate r)

The paper goes on to explain some intuition about this structure and why it should be considered as interesting.

Oh by the way, the paper you are reading seems pretty heavy in abstract nonsense, and if you're coming from the CS side of things, you might want to take a look at these blog posts first:

https://bartoszmilewski.com/2013/06/10/understanding-f-algebras/

http://5outh.blogspot.com/2013/01/comonads.html


Why is fully homomorphic encryption so slow? What are the reasons that FHE is so slow? Is it possible to make the FHE algorithm so fast that it can be used in practice (say, the practical FHE algorithm should be slower no more than 10 times compared to conventional calculations)?

Or there is some fundamental limitation and any FHE implementations will always be millions of times slower than usual calculations?

I don't know how to answer why it's slow; it's slow because it's slow? The algorithm involves a lot of computation, and that takes a long time to do.

Is it possible to make a fast FHE?  No one knows.  It's an open problem.  If it was easy, we would have done it so far.  So either it's not possible; or it's possible but it's challenging and we currently don't know how to do it.

In some sense, it's not surprising that FHE is a lot slower than traditional cryptography.  FHE imposes some very strong requirements on the encryption scheme.  This constrains what kind of encryption scheme you can use.  It's no surprise that if you add extra requirements, it's harder to make the scheme also be fast; and it feels reasonable that the stronger the requirements, the slower this might make the scheme.  In this case, the FHE requirement is very strong indeed.

I'm not aware of any proof that FHE must be slow.  However, there are some results that may be somewhat indicative.  In particular, the following paper shows that any FHE scheme can be broken in subexponential time (while we believe that traditional encryption schemes require exponential time to break).  This means that the FHE scheme will require larger parameter sizes to be secure.  Usually, larger parameter sizes mean that the scheme will be slower.  So, that is some weak indication that FHE schemes will need to be slower.  However, it doesn't really answer the question; it's just a hint.

Algorithms for black box fields and their application to cryptography.  Dan Boneh, Richard Lipton. CRYPTO '96.


Finding a subarray of time series data in which all values are less than X for specified time Y? The idea is to find an anomalous value (i.e. it's less than X) in time series data (sorted by time), and check if this behavior continues during specified time (Y=2 hours).

If all values in sub-array (which represents 2 hours period) are ≤  X, the subarray is returned as a result, and we do not continue further.

Else search continues until such sub-array is found or we have no more data.

Is there an algorithm or family of algorithms that are suited for this task?

Example:

X = 10

Y = 2 hours

Data:

(time=00:00, value=4)

(time=01:00, value=4)

(time=02:00, value=11)

(time=03:00, value=4)

(time=04:00, value=3)

(time=05:00, value=3)

Result:

(time=03:00, value=4)

(time=04:00, value=3)

(time=05:00, value=3)

...during these 2 hours all values were consistently ≤ than X=4.

On the other hand, 00:00 - 02:00 range has X=11 at the end, so it isn't included in result.

Update:

There are approx. 1440 data points in the array (1 point per minute x 24 hours).

This shouldn't be a streaming algorithm, all needed data points are already available.

Data points are immutable, values (or time) don't change.

It's important that we use as little memory during the search as possible.

Search is run once a day, so the data is different and does not depend on previous searches.

You don't need a clever or sophisticated algorithm.  It suffices to linearly scan through the time series, in chronological order, and keep track of the length of window of values less than $X$.

At time $t$, remember the length of the longest window ending at time $t$ such that all values in the window are less than $X$.  At time $t+1$, when you see the next value, update this length (it either increases by 1, if the new value is less than $X$, or resets to 0, if the new value is at least $X$).  Keep track of the longest such window that you saw during the entire scan.  If it is longer than $Y$, output it.

This requires very little memory (only an integer to keep track of the length of the window of consecutive values $< X$, and an integer to keep track of the current position in the array).  The algorithm should be extremely fast.


Question regarding terminology used to describe Benes networks I'm studying a routing problem on a cyclic butterfly network. The paper I am reading states that two properties of the cyclic butterfly network make it efficient for the routing algorithm it describes. I'm new to this subject, and I'm struggling to understand the first property, which is:

"(1) It embeds a Benes network - meaning that if we traverse the columns and back any permutation of the row labels can take place without collisions"

It adds that this is trivially true for a square grid. In this context do collisions mean collision of packets of information? Why is this trivially true for a square grid, but not the cyclic butterfly network?

Kind regards

S

I think they are talking about a path that goes from the left edge to the right edge, and then back to the left edge again.  That path will never visit any node more than once.  By "without collisions", they mean that the left-to-right part of the path will never intersect with the right-to-left part of the path.

I think.


How is this the expected number of of probes in open-address hashing? I am reading the "Introduction to Algorithms" by Thomas Cormen et al. Particularly the theorem which says that given an open-address hash table with load factor $\alpha = n/m < 1$, the expected number of probes in an unsuccessful search is at most $1/(1-\alpha)$, assuming uniform hashing.

In the proof they are assuming $p(i)$ to be the probability of exactly $i$ probes where we are finding all of the slots to be occupied. $i$ is $0,1,2,\dots$ so for $i > n$ we have $p(i) = 0$ since we can find $n$ slots already occupied. I have understood upto this point.

Then it says that expected number of probes in an unsuccessful search is
$$1 + \sum_{i=0}^\infty i\,p(i)\,.$$
How is it so?

If there is any confusion to the question please comment. I hope I have explained the question properly. Any help would be appreciated. Thanks in advance.

It is the definition of expectation. When the probability of success in exactly $i$ probes is $p(i)$, it means you've been unsuccessful $i-1$ times before! Hence, the expected of unsuccessful steps is $$\sum_{i = 1}^{\infty}(i-1)\times p(i) = \sum_{i = 1}^{\infty}i\times p(i) + \sum_{i = 1}^{\infty}p(i) = 1 +\sum_{i = 1}^{\infty}i\times p(i)\,.$$


Possible error in Computer Networks, V Edition by Tanenbaum & Wetherall Under section 5.4 Quality of Service on page 404:

Multimedia applications in particular, often need a minimum throughput and maximum latency to work.

Isn't this statement incorrect? Shouldn't it be :
Multimedia applications in particular, often need a maximum throughput and minimum latency to work.

I don't have a copy of this book to confirm the context, but I suspect that the sentence as written was intended to be interpreted as:

Multimedia applications in particular, often need the network to provide guarantees of a certain minimum throughput and maximum latency to work.

In other words, in order for a multimedia application to function, the channel must ensure at least a certain throughput and at most a certain latency—exactly what is written.
The key word to notice here is the indefinite article "a". Both of the following sentences are correct, with different meanings:

Multimedia applications often need a minimum throughput and maximum latency to work.
Multimedia applications benefit from maximum throughput and minimum latency.

To further confuse matters, the following sentence means the same thing as 2.

Multimedia applications benefit from a maximum of throughput and a maximum of latency.

Isn't English grand?


Can you explain this exercise solution to me? A process running on CTSS (Compatible Time Sharing System) needs 30 quanta to complete. How
many times must it be swapped in, including the very first time (before it has run at all)?

•
Answer : The first time it gets 1 quantum. On succeeding runs it gets 2, 4, 8, and 15, so it must be swapped
in 5 times.

why does it get 2,4,8,15 on the succeeding runs?

According to this article: F. J. Corbató, M. M. Daggett, R. C. Daley, An Experimental Time-Sharing System (IFIPS 1962), CTSS uses a "multi-level scheduling algorithm":

  The basis of the multi-level scheduling algorithm is to assign each user program as it enters the system to be run (or completes a response to a user) to an $\text{ell}$-th level priority queue. The process starts with the time-sharing supervisor operating the program at the head of the lowest level occupied queue, $\text{ell}$, for up to $2^\text{ell}$ quanta of time and then if the program is not completed (i.e. has not made a response to the user) placing it at the end of the $\text{ell}+1$ level queue. Programs are initially entered into a level $\text{ell} = 0$.

A program at the ell-th level is assigned $2^{\text{ell}}$ quanta.

Now you know how to solve your exercise.


What is the difference between storage media and storage devices I am having a rather distressing confusion about whether storage media and storage devices are the same terms. I found on this yahoo answers page that there is a subtle difference but very tricky to understand.

I have googled a lot but cannot find the satisfying answer.

Can anyone kindly explain the difference between these two terms with easy-to-understand examples.

Regards

Media is what holds the information, e.g. disk platen, CD, magnetic stripe.
Device is what uses the media and provides a physical interface.

For devices that have removable media, such as CD/DVD players the distinction is easy. For other devices where the media is an integral part of the device, the distinction is not so easy because the media is not designed to be removed, e.g. hard drive, thumb drive.


A PDA to recognize the Intersection of two regular languages? I am studying pushdown automata and I am working on a problem that asks to generate a PDA that accepts the following regular languages:

  Intersection of L1 and L2

L1 = L (aaa* bab)
L2 = L (aab* aba)

I can't tell if this is even possible because I don't see any common string that would be in both languages.

If it is not possible how should I formally state so? I am brand new to PDAs.

If the intersection is empty then you have to show that some PDA accepts the empty language. That doesn't sound too difficult.

More generally, every NFA is secretly a PDA (showing that every regular language is context-free), and so if you can construct an NFA for your language then you can easily convert it to a PDA.


Oracle Turing Machine EXP^EXP I'm reading Arora Barak and in that it is written that when $O \in \mathrm{P}$, then $\mathrm{P}^O = \mathrm{P}$. Can this be generalized?
Intuitively,  I think that $\mathrm{NP}^\mathrm{NP} \neq \mathrm{NP}$ but $\mathrm{EXP}^\mathrm{EXP} = \mathrm{EXP}$.
Am I right? Any elaboration on the same would be appreciated.

No, $\mathsf{EXP^{EXP}=2EXP}$, a set of languages decidable in $O\left(2^{2^{\mathrm{poly}(n)}}\right)$ time.

This is just because you can give exponentially long input to an oracle which can solve it. So, the total power is $\exp(\exp(n))\ne \exp(n)$.

To see why $\mathsf P$ is self-low just take a machine that can run quadratic time and give to it the same oracle. While the resulting machine will be able to solve all languages in $\mathsf{DTIME}(n^4)$ it is still polynomial. Generalizing, $\mathrm{poly}(\mathrm{poly}(n))=\mathrm{poly}(n)$.

Was wrong, now understood that this is the only way to make machine that faster. Thanks to Ariel.

P.S. There is a parsimonious exp-time reduction from $\mathsf{2EXP}$-complete problem to an exponentially longer $\mathsf{EXP}$-complete problem.


Generate all combinations of values that are less than array's elements and have a sum = target I want to find a way to generate sets that contain elements that sum to a certain target. Initially, I have an array that contains elements representing the maximum value that can be stored in that index.

For example, the input is [8,6,1] and the target is 10. The algorithm should produce all sets that have elements [ (<=8), (<=6), (<=1) ] such that their sum is equal to 10. Examples include: [8,1,1], [8,2,0], [7,3,0], ...

A major consideration for this algorithm is that it should work on any input length (the above example has a length of 3).

I think the solution is close to the subset sum problem, but I wasn't able to figure it out. Any help is appreciated.

Side note: python code is preferred, but Pseudo-code should be fine.

Thanks

Where subset sum takes exponential time to find a solution, here you can find one solution quickly, but there are exponentially many solutions, and therefore it will take exponential time to find them all.

Or factorial really, on the length (let's call this $n$) of the array, as every time you have a set of $n$ numbers that add up to the target, all $n!$ permutations of this is a solution in the worst case, when they are within the maximum values (that is, [6,4,0] and [4,6,0] are not the same solution but both valid). So if the target can be summed from $n$ numbers in $k$ different ways, then we can have up to as many as $k * n!$ solutions in the worst case.

For small problems, you should be able to solve this using recursion. Here is a pseudocode representation that should work. Hope it all makes sense.

Pseudocode:

1:$\quad$ function RECURSE( index , sum , value , array )

2:$\quad\quad$ sum $\leftarrow$ sum + value

3:$\quad\quad$ if sum = target and index is last index in array then print result $\quad$// it's a match

4:$\quad\quad$ if sum $\gt$ target or index is the last index in array then return $\quad$// no result here

5:$\quad\quad$ increment index

6:$\quad\quad$ for $i = 0$ to $i =$ max allowed value on index do

7:$\quad\quad\quad$ newArray $\leftarrow$ copy of array

8:$\quad\quad\quad$ newArray[index] $\leftarrow i$

9:$\quad\quad\quad$ RECURSE( index , sum , i , newArray )

10:$\quad\quad$ end for

11:$\quad$ end function

$\\$

12:$\quad$ function MAIN

13:$\quad\quad$ for $i = 0$ to max allowed value on index 0 i array do

14:$\quad\quad\quad$ array $\leftarrow$ new array

15:$\quad\quad\quad$ array[0] $\leftarrow$ $i$

16:$\quad\quad\quad$ call RECURSE( 0 , 0 , $i$ , array )

17:$\quad\quad$ end for

18:$\quad$ end function


Counting number of states from a regular expression Given the regular expression: $r=ab+((a+\epsilon)c^*)^*$.
Let A be a non-deterministic automaton that accepts the language of r.
How many states are in A?
Answer the question without building A explicitly, explain how you got the answer.

I'm having trouble figuring this question out.
The answer that was given is: $5*2+4*2=18$

With the explanation that for the $\epsilon$ regular expression we build an automaton with 2 states.

for each $\sigma \in \Sigma$ for the regular expression $\sigma$ we build an automaton with 2 states

For concatenating we do not add states and for each union or star operation we add 2 states.

But even with this explanation I'm not quite sure did they reach this answer.

I can understand that we have $\epsilon$, so we have 2. Plus we have $\Sigma = \{a,b,c\}$ so we do $2*3$.

Even with the stars, how do we reach $5*2$?

Also I haven't seen this kind of calculation before, are there any additional rules when trying to calculate states from a regular expression?

The rule for the $\sigma\in \Sigma$ must be applied each time a letter appears in the regular expression, not only once per letter : you must build a different automata each time the letter appears. If you see it as some kind of digital circuit, you do not want to use the circuit that recognizes $a$ in $ab$ for the circuit that recognizes $a$ in $a + \epsilon$.

So you have five letters that appear in $r$, that's $5*2$ states. Then you have 2 concatenations, two unions and two stars. That's $2 * 0 + 2*2+2*2 = 4*2$ states.


Is $L_2:=${$$|$L(M)=\overline{A_TM}$} (un-)decidable? I have to prove that the language $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} is (un-)decidable. In a previous assignment we proved that $L_1:=${$<M>$|$L(M)=A_TM$} is undecidable.
I would say that $L_1$ is decidable because we can build a decider S.
S="on input w": (rough outlined)

breadth first search
(a) if no accept state was found, accept
(b) else reject

Am I wrong with my guess?
$\overline{A_TM}$={<M,w>|M is a TM and does not accept w}

For $L_1:$
It's not decidable.
Define $C=\{A_TM\}$.
Now, by Rice's theorem we have that the language $L=\{<M>|L(M)\in C\}$ is undecidable. (By the extended theorem it's not even semi-decidable.)
But notice $L_1=L$ and therefore $L_1$ is undecidable.

For $L_2:$
It's decidable, although your solution is not correct.
Notice that $\overline{A_TM}$ is not semi-decidable, and therefore there is no TM $M$ where $L(M)=\overline{A_TM}$.
Thus, $L_2=\{<M>|L(M)=\overline{A_TM}\}=\emptyset$ and thus a TM that always rejects will decide $L_2$.


Difference Between PTAS and FPTAS According to this link:

  Polynomial Time Approximation Scheme (PTAS) is a type of approximate
  algorithms that provide user to control over accuracy which is a
  desirable feature. These algorithms take an additional parameter ε > 0
  and provide a solution that is (1 + ε) approximate for minimization
  and (1 – ε) for maximization. For example consider a minimization
  problem, if ε is 0.5, then the solution provided by the PTAS algorithm
  is 1.5 approximate. The running time of PTAS must be polynomial in
  terms of n, however, it can be exponential in terms of ε.

  In PTAS algorithms, the exponent of the polynomial can increase
  dramatically as ε reduces, for example if the runtime is O(n(1/ε)!)
  which is a problem. There is a stricter scheme, Fully Polynomial Time
  Approximation Scheme (FPTAS). In FPTAS, algorithm need to polynomial
  in both the problem size n and 1/ε.

What I dont understand is the second paragraph stated above. Can someone explain to me whats the difference between FPTAS from PTAS? Can you enlighten me about exponent of the polynomial can increase dramatically as ε reduces and algorithm need to polynomial in both the problem size n and 1/ε. ? I really dont get it. Please help.

Imagine you have an $\epsilon$-approximation algorithm $A$ which runs in $n^2+2^\frac1\epsilon$ on an instance of size $n$ and another one, $B$ which runs in $n^2+\frac1\epsilon$ (to give you an other example).

(I'm not using big-O notation to make it easier to talk about the polynomial bounds).

Now if you say $1/\epsilon$ is a constant, $2^\frac1\epsilon$ and $\frac1\epsilon$ both become constants, and you can say that the runtime of both $A$ and $B$ is bounded by a polynomial in $n$. Meaning that only $n$ is seen as a variable of that polynomial, as $\epsilon$ is a constant. So both $A$ and $B$ qualify as PTAS.

However, if this time you don't consider $1/\epsilon$ like a constant and want to include it as a variable in a polynomial upper bound, the situation changes.

For $B$, there exists some polynomial $p(x,y)$ of two variables $x$ and $y$, such that the runtime of $B$ is at most $p(n,1/\epsilon)$ for all $n,\epsilon > 0$. For example, $p(x,y) = x^2 + y$ works, because $n^2+\frac1\epsilon \leq p(n,1/\epsilon)$. Thus $B$ qualifies as a FPTAS.
For $A$ however, it is not possible to find such a polynomial. For every polynomial $p(x,y)$, you know that $n^2+2^\frac1\epsilon > p(n,1/\epsilon)$ once $1/\epsilon$ becomes big enough (or equivalently, once $\epsilon$ becomes small enough). Thus $A$ does not qualify as a FPTAS.


Is the halting problem always decidable for non-universal programs? For every non-universal computable program $P$ that takes input of type $D$ does there exist some total computable function $g$ that takes an input $I$ of type $D$ and decides successfully whether $P$ halts on $I$?

Some concrete definitions:
A program $P$ that takes some data type $D$ as input is computable iff there exists some total computable function $h$ that takes a input string and returns a $D$, and some Turing machine $T$, which takes a binary string, such that $P(h(I)) \cong T(I)$ for all strings $I$. "$\cong$" includes both not halting as well as both producing the same output.

A program $P$ that takes some data type $D$ as input is universal iff there exists some total computable function $f$ that takes both a description of a Turing Machine and an input string and produces something of type $D$ such that for every Turing machine $T$ and every string $I$, $P(f(T, I)) \cong T(I)$.

To answer the first part of your question - Two counter machines are not exactly Turing-complete. That is, there are some functions that cannot be computed with them, for certain counter-values. This is a very slight weakness, so 2CM are actually very close to being Turing complete, but still.

As for your suggested model - could you formalize it in more detail? It's not clear enough as it is.


How many minimal spanning trees are there when all edge costs are distinct? Suppose all costs on edges are distinct. How many minimal spanning trees are possible?

I dont know if this question is supposed to be easy or hard, but all I can come up with is one, because Kruskal's, and any other greedy algorithm should choose all the smallest weighted edges first. Then, if all weights on all edges are distinct, then there are no two equivalently weighted minimum spanning trees if a greedy algorithm is used.

Consider Kruskal's or Prim's algorithms to get minimal spanning trees. They consider arcs in increasing order of cost. If all costs are different, the order in which they are added is fixed, and so is the spanning tree constructed. It is unique in this case.


Pumping lemma on {a^n | n=3^k} — help finishing the proof I am working on a pumping lemma question and trying to prove that the following is not regular, but I can't finish the proof, if someone can help me it will be great.

So I am given this language:
$L = \{ a^n | n = 3^k , k≥0 \}$ .
Ok. I choose $w = a^{3^m}$. I know for sure that $y = a^t$ ($y$ must be any number or $a$'s), where $t≥1$. $x = a^{(3^m)-t}$ and $y = a^t$. I pump twice, so $i =2$ and  $xy = a^{(3^m)+t}$.

Now, is this enough to finish the proof? What is my $xyz$? and how do I prove that my $w$ is not in the language?
Thank you so much for whoever decide to help me out!

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

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

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

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

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


Why does the reduction from 3SAT to IS work? I was reading about the reduction from 3SAT (input: formula) to Independent set (input (graph, k)) in order to prove that the latter is in NP-Complete. The reduction i've seen follow the next steps:

For each clause at the input, create a node for every variable it contains in case it doesn't exist yet. Then, create a $K_3$ with these nodes.
Create an edge between a node and its negation.

An example i found:

While proving this reduction is correct, they say:

  $\Rightarrow$) If the formula is satisfiable, there is at least one true literal in each clause. Let S be a set of one such true literal from each
  clause. |S| = k and no two nodes in S are connected by an edge.

I don't understand why this works. I mean, $k$ is fixed at this point (from the input) so if $k=3$ i can take $S=\{x_1, x_3, x_4\}$. If $k=2$ i can take $S=\{x_2, x_4\}$ but if $k=1$ i can't.

Could you explain me why this works or if i am not understanding anything correctly? Thanks.

The $\Rightarrow$ implication means that you need to prove that if the given $3SAT$ formula is satisfiable then there is a maximum IS.

So assume that the formula is satisfiable.

Since the formula is satisfiable each clause has at least one literal (it may be $x_1$ or $\overline{x}_1$ for instance). Now I claim that according to the structure of the graph the maximum IS must have $k$ nodes where $k$ is the number of clauses.

Why?

Because each clause corresponds to a single triangle $K_3$, and hence you can choose only one node from each triangle, where you have exactly $k$ triangles (any two nodes in the $K_3$ are not independent - they are connected by an edge).

But which node do we choose from each gadget/triangle?

You choose those literals which are true. These literals form independent set. Indeed, if two true literals belong to different triangles then they are not connected by an edge since only $x_i$ and $\overline{x}_i$ may be connected by an edge. But $x_i$ and $\overline{x}_i$ cannot be true at the same time (remember that our IS $S$ contains only true literals).

So we have exactly $k$ nodes/true literals which indeed forms a maximum IS. Therefore if the formula is satisfiable then the graph has a maximum IS.

You also need to prove the opposite, namely, if the graph has a maximum IS then the formula is satisfiable. I think you could prove it yourself.


Signed and unsigned numbers How would the ALU in a microprocessor differentiate between a signed number, -7 that is denoted by 1111 and an unsigned number 15, also denoted by 1111?

Short version: it doesn't know. There's no way to tell.

If 1111 represents -7, then you have a sign-magnitude representation, where the first bit is the sign and the rest of the bits are the magnitude. In this case, arithmetic is somewhat complicated, since an unsigned add and a signed add use different logic. So you'd probably have a SADD and a UADD opcode, and if you choose the wrong one you get nonsensical results.

More often, though, 1111 represents -1, in what's called a two's-complement representation. In this case, the ALU simply doesn't care if the numbers are signed or unsigned! For example, let's take the operation of 1110 + 0001. In signed arithmetic, this means "-2 + 1", and the result should be -1 (1111). In unsigned arithmetic, this means "14 + 1", and the result should be 15 (1111). So the ALU doesn't know whether you want a signed or an unsigned result, and it doesn't care. It just does the addition as if it were unsigned, and if you want to treat that as a signed integer afterward, that's up to you.

EDIT: As Ruslan and Daniel Schepler quite rightly point out in the comments, some operands still need separate signed and unsigned versions, even on a two's-complement machine. Addition, subtraction, multiplication, equality, and such all work fine without knowing if the numbers are signed or not. But division and any greater-than/less-than comparisons have to have separate versions.

EDIT EDIT: There are some other representations too, like one's-complement, but these are basically never used any more so you shouldn't have to worry about them.


Are two-level schedulers only useful to manage swapping? Two-level scheduling is useful when a system is running more processes than fit in RAM: a lower-level scheduler switches between resident processes, and a higher-level scheduler swaps groups of processes in and out.

I find no other mention of two-level scheduling in Andrew Tanenbaum's Operating Systems: Design and Implementation, 1st ed. Exercise 2.22 asks why two-level scheduling might be used; I don't know whether it's there as a reading comprehension check or there are other reasons not prominently mentioned in the text.

Is two-level scheduling useful to manage other resource contentions, besides memory?

There are other forms of two-level scheduling than the type you describe.  For example, one level of scheduling could be per-user and the other could be per-process, aiming for giving a user with 20 processes the same amount of CPU time as a user with 1 process.  With a single-level scheduler, each process might get 1/21 of the CPU time.

Another form of two-level scheduling could be per-process and per-thread, aiming to give a process with 20 threads the same amount of CPU time as a process with 1 thread.


Ordering a list of lists subject to constraints I have encountered a surprisingly challenging problem arranging a matrix-like (List of Lists) of values subject to the following constraints (or deciding it is not possible):

A matrix of m randomly generated rows with up to n distinct values (no repeats within the row) arrange the matrix such that the following holds (if possible):

1) The matrix must be "lower triangular"; the rows must be ordered in ascending lengths so the only "gaps" are in the top right corner

2) If a value appears in more than one row it must be in the same column (i.e. rearranging the order of values in a row is allowed).

Example 1 - which has a solution

A B
C E D
C A B

becomes (as one solution)

A B
E D C
A B C

since A, B and C all appear in columns 1, 2 and 3, respectively.

Example 2 - which has no solution

A B C
A B D
C B D

has no solution since the constraints require the third row to have the C and D in the third column which is not possible.

In my attempts to solve this naively (e.g. by sorting shortest rows to longest and then trying to order the rows from "most in common" to least and then simple reordering within the row) there are always scenarios that it thinks aren't solvable but are.  In other words backtracking/exhaustive search appears to be required, which is OK but I haven't yet struck onto a nice concise (ideally functional) algorithm for this.

This problem is an instance of the list coloring problem.  The list coloring problem is a variant of the graph color problem, where additionally have constraints that provide for each vertex a list of allowable colors that can be used for that vertex.

Here's the relationship.  Let $V$ denote the set of distinct values that appear in any row.  In Example 1, $V=\{A,B,C,D,E\}$; in Example 2, $V=\{A,B,C,D\}$.  Form an undirected graph $G$ where $V$ is the vertex set (so each value is a vertex).  Add an edge $(u,v)$ between two values if there is some row where those two vertices appear together.

Now suppose we want to arrange these in a matrix with $c$ columns (i.e., $c$ is the length of the longest row).  We'll imagine having $c$ colors, numbered from $1$ to $c$, where color $i$ corresponds to the $i$th column.  If the value $v$ is colored $i$, we take this to mean that every appearance of value $v$ should appear in column $i$.

Now from each row that is less than $c$ values long, we obtain some constraints.  In particular, if we have a row that is $\ell$ values long, then each value in that row needs to be colored with a color in the set $\{1,2,\dots,\ell\}$ (to ensure the lower-triangular requirement).  These are the lists that make this a list coloring problem.

Now any solution to the list coloring problem yields a solution to your problem: the colors tell you what column to put each value into, which tells you how to permute each of your rows to form a valid solution.  Therefore, you can use any algorithm for the list coloring problem to solve your problem.


Decidability of Machines I cannot understand decidability really well. I have been reading from books and internet, but I am little bit confused.
According to the book (as I understood), we can decide on decidability of a problem by constructing Turing Machines. Let us say that we want to decide whether an NFA is a decidable language. First, we need to construct a Turing Machine that accepts if the run on w in NFA ends in accept state, otherwise Turing Machine rejects.
According to this definition, I can construct any Turing Machine that can decide every NFA. As a result, I can say that every NFA that can be constructed is decidable. Is this true ?

Additionally, I realized that we cannot decide whether two Context Free Grammars produce same languages. However, we can decide whether two NFA produce same language. Therefore, can we conclude that as our machines get complicated, some of the problems get harder to decide ?

I mean lets take an example. Let us say that there is an NFA that accepts some string w whose length is a composite number. I think that this is a decidable problem.

As you can see that I am little bit confused with these concepts. It will be a lot better for me to go over an example, because it is difficult for me to understand only from conceptual explanations.

As a result, I can say that every NFA that can be constructed is decidable. Is this true?

Yes. An NFA can be converted to a deterministic finite automaton, and that can simply be run to decide the output.

  However, is it possible to find a Turing Machine that can accept w whose length is composite number?

Yes, this is possible. It follows from the fact that it can be done in any old Turing-complete programming language, hence also on a TM.

  Is it possible to construct a CFG that accepts this w?

I doubt it. Maybe there is a proof, but I do not see it right away.

Most problems you'll encounter in practice are decidable, because you can come up with an algorithm to decide the answer. If you want an example of an undecidable problem, have a look at this list on Wikipedia.


MOOC recommendations for learning algorithms based on topics covered in Daspupta, Papadimitriou & Vazirani I would appreciate some advise/mentoring on self-study of algorithms. Based on my several years of work as a software developer (non CS background), I have some good grip on standard data structures (linked lists, stacks etc.) and basic sorting and searching algorithm characteristics (time/space complexity).
My goal of learning is to take my knowledge to next level (learning graph theory and advanced algorithm techniques such as dynamic and linear programming) to be able to use it in a variety of situations incl. AI and computationally complex domain problems.
So I purchased 2 books -- Algorithm Design Manual from Skiena and Algorithms by Dasgupta et al. I am aware of the usual advice of CLRS, but decided to skip it for now as my goal at this stage is not proofs.
Now my question is: even though I found the style of writing of Dasgupta book rather appealing, topic is often difficult for unguided, unsupervised learning.
Are there any recommendable online courses (free or otherwise) which would cover topics from Dasgupta book? In general, I found the topics covered in Stanford Algorithm specialization (coursera and edX) rather good, but any further options would be helpful!

While I cannot answer your question (MOOC for Dasgupta et al), I will make a different recommendation.
Since you seem to like the more intuitive and slightly informal approaches to learning, rather than the more formal and proof oriented approach, I think you might like the algorithms book series by Tim Roughgarden, Algorithms Illuminated.
Algorithms Illuminated is a book series of four books,

Part 1: The Basics
Part 2: Graph Algorithms and Data Structures
Part 3: Greedy Algorithms and Dynamic Programming
Part 4: Algorithms for NP-Hard Problems

The books are reasonably priced, and on the plus side, Roughgarden has made a series of videos that can be found on the aforementioned website for the books.
In addition, he has a series of lectures that have appeared as edX and coursera courses on his videos site.


What is a batch based interface? I came across this description of Batch Interface:
"commands and directives are used to manage those commands that are entered into files and those files get executed. "

I would really appreciate if someone explains in detail what Batch Interface is and how it's different from Command Line Interface?

In the olden days, you wrote up a sequence of operations to be executed (typically on punched cards, a job), and handed them to the operator to be loaded. The operating system took such a batch of commands to execute off it's input queue, ran them until the end (or something failed), and took the next one. Output was collected (probably printed out) to return to you.

If the above is what is meant, the crucial difference is that in batch processing you get (perhaps the next day) the feedback that the job failed because of a syntax error or some equally irritating glitch. With a command line interface you run one command, can check it's output or correct the command before entering the next one.


Has Anyone Actually Created a System that Writes Computer Programs from specification? Has anyone ever actually written a system (software or detailed explanation on paper with simple examples) that generates computer programs?  I input $Prime(x) \wedge x<10$ and it creates a program that lists the prime numbers less than 10.  $Prime(x)$ is simply defined as
$$1<x \wedge \not\exists A\; s.t. 1<A \wedge A<x \wedge x=A\times B,\mbox{ with }
A,B\in \mathbb{N}$$
Professors say they can but nobody gives actual complete examples.

This is a very active research topic, very promising, though full
automation of program generation probably has intrinsic limitations (but are human beings any better?).
But the idea is still be very useful in assisting considerably the
creation of programs by mechanizing many steps, and by automatically
checking the correctness of the program generation.

It is strongly related to a result in logic, called the Curry-Howard
correspondance (or isomorphism), that shows that computer programs and
mathematical proofs are very similar.

So the idea is that the system will take your program specification as a
theorem to be proved. In the case of your example, it would be
something like (informally): "there is a set of all prime numbers smaller
than 10".

Then, you will attempt to prove that theorem, and existing systems
will assist you in doing the proof, automating some parts, possibly the whole proof, and making
sure you never make errors.

From that proof one can then extract a program
that actually computes the  wanted list of prime numbers that had been
initially specified.

Several systems were developed in the past to elucidate these ideas. One
of the better known was LCF by Robin Milner, who created the language
ML for that purpose. One of the currently most advanced systems is
Coq.

There are examples fully worked out, some of them quite complex. You may find some in the following article, though it is in no way simple reading and requires advanced knowledge of Logic.


Mutations as a crossover by product Let's say I'm writing a GA to find an optimal path to travel from point $A$ to point $B$. Genotypes are a list of directions (north, south, east, west) to follow.

So a genotype "NENWEE" will move north once, east once, then north again, west once, and finally east twice.

The directions are encoded as follows:

N : 00
E : 01
W : 10
S : 11

Our first genotype, "NENWEE" (let's call it $P$), will thus be encoded as follows:
$00\,01\,00\,10\,01\,01$

Let $Q$ be a second genotype, say "EENEWW", which is encoded as follows:
$01\,01\,00\,01\,10\,10$

Now let's do a one-point crossover operation on genotype $Q$, from $P$. The randomly-chosen crossover point is between the $9$-th and $10$-th bit, so bits $10$, $11$ and $12$ from genotype $P$ will replace those same bits from genotype $Q$. Let's call the resulting genotype $Q'$.

P  :  00 01 00 10 01 01
Q  :  01 01 00 01 10 10
Q' :  01 01 00 01 11 01

After decoding $Q'$ we find that the result is "EENESE". However neither $P$ nor $Q$ contained direction south.

My question is, do crossover operators imply a certain degree of mutation by definition?

I have contacted Inman Harvey from the University of Sussex and here is his answer to my question:

  In your example you have given each genotype $6 \,\,\,\, 2$-bit 'genes'. Let's look at how different your example parents $P$ and $Q$ are:

  In genes $2 (01)$ and $3 (00)$, the genes are identical in $P$ and $Q$
  In genes $1, 4, 5$ and $6$ the $2$-bit genes differ

  Ie $2/3$ of the genes differ between parents.

  If you have $1$-point crossover at any of $12$ positions on the genotype (including here the non-functional case where the crossover-point is 'off-the-end', then:

  $6$ of the possible crossover points are between-genes and hence do not count as sort-of mutations.
  $2$ of the possible crossover points are within the $2$-bit genes that are identical in $P$ and $Q$ – hence do not result in any 'crossover-style-mutation' in $Q'$

  $4$ of the possible crossover points are within non-identical genes, and hence DO result in a crossover-style-mutation in $Q'$.

  So -- with your specific example, $4$ out of $12$, ie $1/3$ of the time, crossover will produce a crossover-style-mutation. Sounds a lot. Sounds like maybe you should be worried about this in terms of impacting on effective mutation rates...

  BUT WRONG!! Your example was atypical. You will find in practice, after only a few generations of evolution, your parents $P$ and $Q$ will be genetically very similar to each other. This is the basic SAGA insight, see any of my papers with SAGA in the title. If you doubt this, then run any binary-style GA for as few as $10$ generations and check on how similar any $2$ randomly chosen parents are. It won't be (as in your example above) $67\%$ of genes differing between parents, it will be more like order of $1\%$ (if your genotypes are say $100$ bits long) differ between parents. Don't believe me, run the tests yourself, it is very easy to do!

  ... and hence your concern about these crossover-style-mutations should, I suggest, diminish to near vanishing point when you take account of the reality that most parents have mostly identical genotypes.

  Anecdotally and simplistically, if human genotypes are $98\%$ similar to chimpanzee genotypes, then you should expect your average human-human parental couple to be $99.99\%$ genetically identical, and only $0.01\%$ open to the possibilities that worry you above (that $\sim 0.01\%$ is of course important and interesting for different reasons). Elephant mating with a flea, then you can expect problems -- in fact what you are discussing above relates closely to inter-species breeding problems. Your standard $GA$ does not run into such problems.

I hadn't thought of it this way. So in fact crossover operators may introduce unwanted mutations in early generations (depending on how they are implemented) but these mutations will have little, if any, effect on the actual optimal mutation rate.


Range of values for Kolmogorov complexity Let $n$ be a positive integer. Is it true that for all $1\leq i \leq n$  there exists a length $n$ binary string $w$ such that $K(w) = i$. Where $K(w)$ is the Kolmogorov complexity of $w$.

For each $i$ there are clearly $2^i$ programs of that length. But can we be sure at least one of them (when executed) generate a length $n$ binary string?

The answer depends on the exact choice of program description language. We can define Kolmogorov complexity with respect to any admissible program description language. A program description language $L$ is admissible if for all program description languages $L'$, we have $K_L(x) \leq K_{L'}(x) + C_{L'}$, for some constant $C_{L'}$ depending only on $L'$.

We start by showing how to construct an admissible program description language in which all Kolmogorov complexities are even. Let $L$ be an admissible program description language. We define a new program description language $L'$ as follows: if $|x|$ is odd or $x = \epsilon$ then $L'(x) = \epsilon$; if $|x|$ is even and $x=0y$ then $L'(x) = L(y)$; and if $|x|$ is even and $x=1y$ then $L'(x) = L(z)$, where $z$ is obtained from $y$ by removing the last symbol. Since $K_{L'}(x) \leq K_L(x) + 2$, $L'$ is admissible. On the other hand, it is easy to check that $K_{L'}$ is always even.

Conversely, we can also arrange that all Kolmogorov complexities would be achieved.  Let $L$ be an admissible program description language. We construct a new admissible program description language $L'$ as follows: $L'(\epsilon) = z$, where $z$ is some string satisfying $K_L(z) < |z|$ (we can choose $z = 0^{2^n}$ for large enough $n$); $L'(0x) = x$; and $L'(1x) = L(x)$. Then $K_{L'}(z) = 0$, and for $w \neq z$, we have $K_{L'}(w) = \min(|w|,K_L(w)) + 1$. For every $n \geq 1$, we can find a string $w$ of length $n-1$ such that $K_L(w) \geq n-1$. This string satisfies $K_{L'}(w) = n$.


Extended NPDA implementation In Formal grammars course we have a task to implement an extended NPDA (a pushdown automata where taking any amount of symbols from the stack is allowed (including ε) and it can be in several states at the same time) in any programming language. It can be one that accepts with a state or an empty stack.
I have looked around and all on the implementation algorithms I have found do not allow for transitions like (ε/ε)/A (read nothing, take out of stack nothing, just add A to stack). The problem of course is that there is (as far as I know) no sure way to terminate this kind of branch and, if indeed, imput string does not belong to this language, it would just infinitely try to loop and loop these kinds of transitions.
So, my question is - how to implement an extended NPDA? How to know when to stop generating a branch and say "this branch goes nowhere, terminate it"?
Here is an example automata - accepts palindromes.

Take a look at this post.
A general way to remove epsilon transitions is to transform the PDA into a CFG, then take this grammar and convert it back to a PDA. This will result an equivalent PDA that does not need epsilon transitions. Take a look here for the algorithms converting the PDA to CFG and back.


Distributing resources for maximum gain This feels like it would be a well researched (or solved) problem, but I can't find the right words to search for it.

Suppose there is a collection of shared resources, and a collection of possible processes. Each process consumes fixed quantities of each resource and provides a fixed benefit. Each process can be applied zero or more times (but no fractional amounts), and resources can be left unused.

How can a distribution which maximises the total benefit be found? Brute-forcing each possible allocation will always find an answer, but is there a more optimal way?

An attempt to formalise the question:

$$
\text{Given resources } R \in \mathbb{R}_{\ge0}^n \\
\text{and process requirements } P \in \mathbb{R}_{\ge0}^{m,n} \\
\text{and process outputs } O \in \mathbb{R}_{\ge0}^m \\
\text{find } N \in \mathbb{Z}_{\ge0}^m \\
\text{such that no resource is over-spent: } \sum_{i=0}^m{N_i P_{i,j}} \le R_j \ \forall \ j \\
\text{and } N \cdot O \text{ is maximised}
$$

This is a knapsack problem. In the most basic version, you have a single resource (e.g., space in your knapsack) and you're trying to choose which items to put in it so you can carry the greatest value. People have also studied multi-constraint knapsack problems, which is the variant you're directly asking about.

The bad news is that knapsack problems are, in general, NP-complete. The good news is that they can be solved in pseudopolynomial1 time using dynamic programming, which is often practical.  They can also be approximated fairly well: for any fixed $\varepsilon$, there is a polynomial time algorithm that will give you the answer to within a factor of $1\pm\varepsilon$. However, the dependence on the running time is superpolynomial, unless P$\,=\,$NP.

1 Pseudopolynomial time means that the running time is a polynomial function of the numbers represented in the input, whereas polynomial time means the running time is a polynomial function of the size of the input in bits. For example, the algorithm read n; for i=1 to n do print "hello"; end is pseudopolynomial: if its input is $n$, it performs $n$ iterations but, if the input is written as a $b$-bit binary number, then $n$ could be as big as $2^b$, so the algorithm isn't truly polynomial.


So if a problem is more difficult the language it represents is smaller? I'm reading the definition of polynomial time reducible:

  Let $L_1, L_2$ be two language. If $L_1$ is polynomial time reducible to $L_2$ then exists $f:\{0,1\}^*$ s.t. $\forall x\in\{0,1\}^*$ $$x\in L_1\iff f(x)\in L_2$$

For me this means the $L_1$ may be bigger (in cardinality) than $L_2$, but $L_2$ is more difficult since $L_1$ can be solved after reduced to $L_2$?

$L_1$ and $L_2$ are always countably infinite, and thus "equally big".

If any language is finite, then it is "constant time" recognizable.


Train a neural network to play tic tac toe using a genetic algorithm I have an assignment for school, in which I have to build a neural network that will play tic tac toe, using genetic algorithms for training. The thing is that I am clueless on how to connect the two. I need help in the design. Should use the GA to generate game boards, to serve as input for the neural network. Or, should I generate the NN weights with the GA. In both cases. I'm having a really hard time with this subject, but I find it extremely fascinating. Any help would be much appreciated. Thanks

this is an unusual assignment or exercise for several reasons. tic tac toe is not a complicated game, there is not a large "state space" so an optimal algorithm is possible even by eg a "relatively small" finite state machine. so even a genetic algorithm or neural network alone would be sufficient (in fact, capable of playing a perfect game) and also, from a practitioner pov, overkill. it suffices as a "toy problem" but almost even too simple to fully demonstrate these techniques. breaking down the problem into a machine learning approach aka "decomposition" is part of the art/ science of the field. here are a few relatively basic/ straightforward possibilities.

genetic algorithm alone: let the candidate solutions aka chromosomes be represented as strings with alternating moves. the fitness function evaluates who wins and if the strings represent valid moves between the two players. it will not take long to find/ enumerate all possible game sequences.
neural network alone: input is (an encoding of) the opponents move, output is the computers move. a data generator must pick valid moves by the opponent.
combination (even bigger overkill): a common scenario in NN+GA technology is for the GA to be used to generate NN architectures. the GA string determines the NN architecture. eg size and possibly connectivity of the different layers. the fitness function is the results of training/ evaluating the NN on the particular GA architecture (ie chance of the computer winning).

and of course there are many other ways to combine NNs+GAs and other ways to decompose the problem into NNs or GAs alone.


Show that for every language there exists a harder language I came across this problem that I could not figure out... For every language $A$, there is supposed to be a language $B$ such that:
$$
A \leq_T B
$$
but:
$$
B \not \leq_T A
$$
If it is $A \leq_TB$ and $B \leq_T A$, this is easy since we can just let $B := \bar{A}$, but for the above I could not think of anything. Any help ?

There are a few ways to approach this.
You can use a counting argument to show that for every $A$ there exists $B$ such that $B\nleq_T A$. Let $L_A=\{B| B\le_T A\}$ denote the set of all languages reducible to $A$. Show that $f:L_A\rightarrow \mathbb{N}$ that maps languages $B\in L_A$ to $n$ such that $M_n$ is a reduction from $B$ to $A$ is an injection, and conclude that there exists a language outside of $L_A$. Next, you want to make it comparable to $A$. We can get such a language with the join operator:
$A\sqcup B=\{0w|w\in A\}\cup\{1w|w\in B\}$.
I leave it to you to show that $A\sqcup B$ is the least upper bound for $A,B$, i.e. $A,B\le_T A\sqcup B$ and additionally for every $L$ such that $A,B\le_T L$ we have $A\sqcup B\le L$ (you only care about the former). Show that if $B\nleq_T A$ then $A\sqcup B\nleq_T A$.
Another way to prove this is to use the jump operator. We need to introduce the notion of oracle machines, and then show that $B=\left\{\left(M^A,w\right)| \text{$M^A$ halts on $w$}\right\}$ is a strictly harder language. The proof is identical to the undecidability of the standard halting problem, only that now we show the stronger property that no machine with oracle access to $A$ can decide $B$.
You can also directly construct such a language via diagonalization. define $B=\left\{n | M_n(n)\notin A\right\}$. We constructed $B$ such that any computable function $M_n$ fails to be a reduction from $B$ to $A$ on at least one input (specifically, the encoding of the reduction). You can now use the join operator to make them comparable.


Bin packing first-fit problem in $O(n \log n)$ time Suppose we have $n$ objects with weights $w_i \in (0,1]$ and we must
  insert them into bins with the constraint that every bin must contain
  objects which weight less than $1 \, kg$.

  The first-fit algorithm must: examine the objects with the order
  they're given $(w_1, w_2, \dots , w_n)$ and insert them into the bins,
  satisfying the above constraint. It must run in $O(n \log n)$ time,
  returning the number of bins which were used and which objects were
  inserted in each bin.

I've constructed an algorithm, using Hash Tables, where the objects' numbers are the keys and the bins' numbers are the values and it basically does this:

for(int i = 0; i < n; i++){
    sum = sum + w[i];

    if(sum < noOfBins){
        BinContent.put(i + 1, noOfBins);
    }

    else {
        noOfBins++;
        BinContent.put(i + 1, noOfBins);
    }

and then it prints noOfBins and BinContent, but I believe this algorithm is $O(n)$ and the proper way would be to use Binary Trees instead of Hash Tables.

Is the complexity of the given algorithm $O(n)$? If so, could you give me a hint on how to achieve $O(n \log n)$ time complexity?

Your solution has $O(n)$ computational complexity but it doesn't implement the first fit algorithm. The thought behind your solution is to insert the items one by one in the given order (that's correct) and to insert the current item in the last bin if it fits in it or to create a new bin if the current item doesn't fit in the current bin (that's wrong).

First of all, this is not what first fit algorithm asks for. You have to insert the current item in the first used bin that it fits in and if it doesn't fit in any already used bin then you will have to use a new one. You shouldn't consider only the last used bin for the insertion, but all the existing bins, that's my point. Additionally as Discrete lizard mentions in his comment, your implementation is wrong even under the wrong perspective.

I will present the correct first fit method using two different algorithms. The first one is sub-optimal, a brute force with $O(n^2)$ computational complexity, because such an algorithm will illustrate better the first fit logic. The second algorithm is the optimal one with $O(nlogn)$ computational complexity.

Now let's consider the first algorithm. We will initially use no bin. As we read the size of each item we will just iterate from left to right over all the already used bins. If we meet a bin where the current item fits (its empty size is at least equal to the size of the current item) then we use this bin, otherwise we have to use a new bin. Note that it will be very helpfull to save the remaining size of each bin and make an update every time a new item is inserted. Bellow I implement this simple solution using C++.

#include <iostream>
#include <vector>
#include <list>
using namespace std;

int n = 0;  // Current number of items

int b = 0;  // Current number of bins

vector<int> IBM;  // Item->bin matching: IBM[i] = bin of i-th item
vector<list<int>> BIM;  // Bin->item matching: BIM[i] = list of items in i-th bin

vector<double> RBS;  // Remaining bin space: RBS[i] = remaining space of i-th bin

int main()
{
    double item_size;  // Current item size
    while (cin >> item_size)  // While there are still items put them in bins
    {
        bool used_bin_used = false;  // Was the current item put in an already used bin?
        for (int i = 0; i < b; i++)  // Iterate over already used bins from left to right
        {
            if (RBS[i] >= item_size)  // If i-th bin has enough space for the current item...
            {
                IBM.push_back(i);  // Current item was put in i-th bin
                BIM[i].push_back(n);  // i-th bin contains the current item
                RBS[i] -= item_size;  // Decrease the available space of the i-th bin
                used_bin_used = true;  // The current item put in an already used bin
                break;  // No more search for current item
            }
        }
        if (!used_bin_used)  // If true, not new bin for current item
        {
            IBM.push_back(b);  // Current item was put in new bin
            list<int> tmp;  // Helping temporary list
            tmp.push_back(n);
            BIM.push_back(tmp);  // The new bin contains the current item
            RBS.push_back(1 - item_size);  // Save the remaining space of the current bin
            b++;  // Increased number of used bins
        }
        // Output current result using numbering starting from 1
        cout << "Item with id = #" << n + 1 << " was put in bin with id = #" << IBM[n] + 1 << ".\n" << flush;
        n++;  // Increased number of items
    }
    // Output bin containing info
    cout << n << " items were inserted in " << b << " bins.\n";
    for (int i = 0; i < b; i++)
    {
        cout << "Bin #" << i + 1 << " contains items: ";
        for (list<int>::iterator it = BIM[i].begin(); it != BIM[i].end(); it++)
        {
            cout << *it + 1 << ' ';
        }
        cout << '\n';
    }
    return(0);
}

Notice that the solution above follows the online fashion. For each of the $n$ items we search linerly $O(n)$ bins in the worst case, so the computational complexity of the above algorithm is $O(n^2)$.

Now let's construct a second, better algorithm. We want to improve the computational complexity of the above algorithm. We would like to reduce the time needed to find the first (leftmost) bin where the current item can fit, which required $O(n)$ time per item. To achieve this goal we can use a segment tree for maximum range queries on the remaining bin spaces. This way every time time a new item is given we can go down the segment tree and find the bin that we should use in $O(logn)$ time for each item. So the computatonal complexity of the algorithm drops down to $O(nlogn)$. We can even follow the online fashion and not require any knowledge about the value $n$, as we did in the previous implementation by doubling the size of the segment tree used every time we have an overflow. The computational complexity will remain $O(nlogn)$ which can be proved using amortized analysis. The C++ implementation of this algorithm is given bellow.

#include <iostream>
#include <vector>
#include <list>
using namespace std;

int n = 0;  // Current number of items

int b = 0;  // Current number of bins

vector<int> IBM;  // Item->bin matching: IBM[i] = bin of i-th item
vector<list<int>> BIM;  // Bin->item matching: BIM[i] = list of items in i-th bin

vector<double> RBS;  // Remaining bin space: RBS[i] = remaining space of i-th bin

vector<double> A;  // Vector with bin remaning sizes used by segment tree

vector<double> tree;  // Vector with segment tree's values

void make_base(int L)
{
    for (int i = A.size(); i < L; i++)
    {
        A.push_back(1);  // New bins will be empty
    }
    for (int i = tree.size(); i < 4 * L + 5; i++)
    {
        tree.push_back(1);  // These values will be overwritten by build
    }
}

void build(int node, int start, int end)
{
    if (start == end)
    {
        tree[node] = A[start];
    }
    else
    {
        int mid = (start + end) / 2;
        build(2 * node + 1, start, mid);
        build(2 * node + 2, mid + 1, end);
        tree[node] = max(tree[2 * node + 1], tree[2 * node + 2]);
    }
}

void update(int node, int start, int end, int idx, double val)
{
    if(start == end)
    {
        A[idx] = tree[node] = val;
    }
    else
    {
        int mid = (start + end) / 2;
        if(start <= idx && idx <= mid)
        {
            update(2 * node + 1, start, mid, idx, val);
        }
        else
        {
            update(2 * node + 2, mid + 1, end, idx, val);
        }
        tree[node] = max(tree[2 * node + 1], tree[2 * node + 2]);
    }
}

int query(int node, int start, int end, double val)
{
    if (start == end)
    {
        return(start);
    }
    int mid = (start + end) / 2;
    if (tree[2 * node + 1] >= val)
    {
        return(query(2 * node + 1, start, mid, val));
    }
    return(query(2 * node + 2, mid + 1, end, val));
}

int main()
{
    double item_size;  // Current item size
    while (cin >> item_size)  // While there are still items put them in bins
    {
        if (tree.empty() || tree[0] < item_size)
        {
            int L;
            if (A.empty()) L = 1;
            else L = 2 * A.size();
            make_base(L);
            build(0, 0, A.size() - 1);
        }
        int idx = query(0, 0, A.size() - 1, item_size);
        if (idx < b)
        {
            IBM.push_back(idx);  // Current item was put in idx-th bin
            BIM[idx].push_back(n);  // idx-th bin contains the current item
            RBS[idx] -= item_size;  // Decrease the free space of idx-th bin
            update(0, 0, A.size() - 1, idx, RBS[idx]);  // Update segment tree
        }
        else
        {
            IBM.push_back(b);  // Current item was put in new bin
            list<int> tmp;  // Helping temporary list
            tmp.push_back(n);
            BIM.push_back(tmp);  // The new bin contains the current item
            RBS.push_back(1 - item_size);  // Save the remaining space of the current bin
            update(0, 0, A.size() - 1, idx, RBS[idx]);  // Update segment tree
            b++;  // Increased number of used bins
        }
        // Output current result using numbering starting from 1
        cout << "Item with id = #" << n + 1 << " was put in bin with id = #" << IBM[n] + 1 << ".\n" << flush;
        n++;  // Increased number of items
    }
    // Output bin containing info
    cout << n << " items were inserted in " << b << " bins.\n";
    for (int i = 0; i < b; i++)
    {
        cout << "Bin #" << i + 1 << " contains items: ";
        for (list<int>::iterator it = BIM[i].begin(); it != BIM[i].end(); it++)
        {
            cout << *it + 1 << ' ';
        }
        cout << '\n';
    }
    return(0);
}

Finally I would like to mention that first fit is a method that doesn't minimize the number of bins used. Solving this problem optimally is NP-hard. First fit algorithm is just a method that usually provides an acceptable solution in a fast manner. It is often used in practice when speed is preffered over optimallity.


Minimum path - robot motion problem combined with freeze tag problem Alright, I am not entirely sure if this is the right place to ask this, but here goes:

I have a map of coordinates of robots and obstacles. The first robot is awake from the start of the problem and it can wake up other robots on the map by walking next to them. Once a robot is woken up by another, it can also traverse the map and wake up other robots. The goal is to awaken all the robots using the minimum possible path.

Below I added an example of how a solution to a certain data set would look like.

I refrain from providing input/output files because I only want to ask for insights into and algorithm in pseudocode or even natural language, but if those would help I could add them as well!

Thank you very much in advance and should I provide any more info, do not hesitate to tell  me!

EDIT #1:
         In the example, both robot A and robot B can traverse the path to C and D. The different colors show that in this example, robot B traversed the path to C and D.
         There are no cases where the robots hull interferes with the obstacles. The 'hull' can touch the obstacles. All robots have the same specifications.
         By minimum path I am trying to refer to the shortest time to wake up all the robots (i.e. time elapsed from when the first robot starts up until all robots are woken up).

Define a fully connected, undirected graph $G$ so that there is a vertex for the initial position of each robot, and an edge between each two vertices whose length corresponds to the time for a robot to move from one position to the other.  The edge lengths can be computed using the A* algorithm or any other pathfinding algorithm.

Now I think you want a rooted spanning tree $T$ for the graph $G$, with the following properties:

The root of the tree is the vertex that corresponds to the initial position of the awake robot.
Every node of the tree has two children, except for the root, which has one child.
The tree is a spanning tree, i.e., every vertex in $G$ appears somewhere in the three.
The "duration" of the tree is minimal among all such trees.

Here we define the duration of a tree to be the maximum of the lengths of all path from the root to some leaf.

I don't know whether there is an efficient algorithm to find such a tree.


What is the difference between the fundamental matrix and the essential matrix? Could someone, in plain english, explain the distinction between the fundamental matrix and the essential matrix in multi-view computer vision?

How are they different, and how can each be used in computing the 3D position of a point imaged from multiple views?

Both matrices relate corresponding points in two images. The difference is that in the case of the Fundamental matrix, the points are in pixel coordinates, while in the case of the Essential matrix, the points are in "normalized image coordinates". Normalized image coordinates have the origin at the optical center of the image, and the x and y coordinates are normalized by Fx and Fy respectively, so that they are dimensionless.

The two matrices are related as follows:
E = K' * F * K, where K is the intrinsic matrix of the camera.

F has 7 degrees of freedom, while E has 5 degrees of freedom, because it takes the camera parameters into account. That's why there is an 8-point algorithm for computing the fundamental matrix and a 5-point algorithm for computing the essential matrix.

One way to get a 3D position from a pair of matching points from two images is to take the fundamental matrix, compute the essential matrix, and then to get the rotation and translation between the cameras from the essential matrix. This, of course, assumes that you know the intrinsics of your camera. Also, this would give you up-to-scale reconstruction, with the translation being a unit vector.


Check the Regularity of the folowing Languages Let $A$ be a regular set. Consider the two sets below.

\begin{align*}
L_1 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n} \}, \\
L_2 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : x =y^{n} \}.
\end{align*}

Which of the following is true?

$L_1$ and $L_2$ are regular
$L_1$ is regular but $L_2$ is not
$L_2$ is regular but $L_1$ is not
Both are not regular

What I knew

$Y \in A $ only but now the relation between $y$ and $x$ is:  $Y  =  X^{n}$  and given the clause there exist associated with the value of $n$, so we can assign any value of $n$ which is $\geq 0$. So if $n = 1$, then $Y = X$ and hence $X$ is obviously regular set.

Similarly on setting $n = 2$, we get $Y = X^{2}$  meaning $Y$ can be partitioned on exactly 2 halves and hence we can say $X$ is $\mathrm{half}(Y)$. And we know given a language or a set $L$ is regular, then $\mathrm{half}(L)$ is also regular.

With this understanding I came to a conclusion that $L_1$ is regular.

But, How to check the regularity of $L_2$? I also wanted to confirm my approach to $L_1$ being regular is correct.

Your reasoning regarding $L_1$ is wrong. What you show is that for each $n$, the following language is regular whenever $A$ is regular:
$$
L_1^{(n)} = \{ x : x^n \in A \}.
$$
The language $L_1$ is the infinite union of $L_1^{(n)}$ for all $n \geq 0$. Unfortunately, regular languages are not closed under infinite union (for example, every unary language is an infinite union of singleton languages).

Nevertheless, $L_1$ is regular. Given a DFA $\langle Q,q_0,F,\delta \rangle$ for $A$, we construct a DFA for $L_1$ whose set of states is the set of all functions $Q \to Q$. The initial state $id$ is the identity function, and we construction the automaton so that $\delta_{L_1}(id,w)$ is the function that maps $\sigma \in Q$ to $\delta(\sigma,w)$. This gives us enough information to determine whether any power of $w$ belongs to $A$.

The language $L_2$, in contrast, is not necessarily regular. For example, if $A = ab^*$ then $L_2 \cap ab^*ab^* = \{ ab^n ab^n : n \geq 0 \}$, which isn't regular.


Maximum number of steps a Turing machine makes Given the Turing machine $M = (  \{q_0, q_1, q_2. q_3,q_4\}, \Sigma= \{a, b, c \}, \Gamma = \{a, b, c, \}, \delta, q_0, , \{q_4\} )$
where $q_0$ is the start state, $q_4$ the end state and  the blank symbol. $\delta$ is defined as:

Let $w$ be any word of length $n$ accepted by the Turing machine $M$. Is it always true, that $M$  will reach $q_4$ in maximum of $1.5 \cdot
 (n+5)$ steps?

Is there a general strategy for this or do we just try different inputs until we find a contradiction? If none is found, how do we go about proving such a statement?

In general, it is impossible to even determine if it will ever halt. And if it halts, determining the number of steps is also impossible. Check out the busy beaver game for details.

There are general techniques that work in a large proportion of cases of practical interest, for a start check out the reference question here. But there have been complete libraries written on the intricacies of the matter...


For s set $S\subseteq RE$, so call feature of language $S=\emptyset$ vs. $S=\{\emptyset\}$ I'm trying to understand what's the difference between $S=\emptyset$ and $S=\{\emptyset\}$
The diffenition that I found for $L_S=\{\langle M\rangle\ | L(M)\in S \}$
I understood that $S=\emptyset$ and $S=RE$ are trivial and
$S=\emptyset \Rightarrow L_\emptyset=\emptyset\in R$
$S=RE \Rightarrow L_{RE}=\Sigma^*\in R$
But can't understand what's going with $S=\emptyset$ and $S=\{\emptyset\}$

Assume that all languages are over the alphabet $\Sigma$. What you have here is a bit of ambiguity in the meaning of $\emptyset$ (recall that the emptyset is defined w.r.t a universal set, and here $\emptyset$ is used w.r.t different universal sets). Indeed, $S = \{ \emptyset\}$ refers the set of languages containing only the empty language, that is,  in this case, $\emptyset\subseteq \Sigma^*$. Also, $S = \emptyset$ refers to the empty set of languages, that is, in this case $\emptyset\subseteq 2^{\Sigma^*}$.
As you noted, if $S = \emptyset$, then $L_S = \{ \langle M\rangle: L(M)\in \emptyset\} = \emptyset \in \text{R}$. Now if $S = \{ \emptyset\}$, then $L_S = \{ \langle M\rangle: L(M)\in \{\emptyset\}\} = \{ \langle M\rangle: L(M) = \emptyset\} = E_{TM}$ which is known to be in $\text{coRE}\setminus \text{R}$.