Variation of rank selection in genetic algorithm

For Differential Evolution (DE) there is the Rank-Based Crossover Operator that is quite similar.

It has been proposed in "A line up evolutionary algorithm for solving nonlinear constrained optimization problems" by Haralambos Sarimveis, Athanassios Nikolakopoulos (2005):

  The idea is to line up the solutions in each generation in a descending order according to the corresponding values of the objective function. The crossover and mutation operations are then applied to the solutions as follows: during the crossover operation, for each adjacent pair the difference vector is computed, weighted by a random number between 0 and 1 and added on the first vector of the pair. The produced solution replaces the first vector, if it produces an objective function value that is lower than the fitness value of the second vector. At the end of the crossover operation, the solutions are lined up again.

Of course DE has a peculiar crossover operator but the general idea of lining up individuals (rank based order) to choose crossover pairs is the same.


Distribute to pairs with efficient algorithms

Yes, that works, but I would skip making/faking Eulerian cycles and just execute your idea directly:

If the list is empty, you're done. Otherwise, choose an arbitrary $(a, b)$ from your list, output it and remove it.
Find the unique $(c, b)$ in your list, output it and remove it.
If $(c, d)$ exists in the list, output it and remove it. Otherwise go to 1.
Find the unique $(e, d)$, output it, remove it, let $c \leftarrow e$ and go to 3.


How can I efficiently find the optimal order to apply special offers to a shopping cart?

Interesting problem. As noted, you can easily turn this into an integer programming problem. But if your numbers are small and nobody buys a warehouse full of goods an easy algorithm may work.

All you need to decide is how often each offer is applied. Sort the offers by percentage saved in descending order. Then an outer loop where the most saving offer is applied first as often as possible first descending. Then the second highest percentage saving etc. You reject a search path if it cannot be optimal.

In your example the first offer saves 50% and the second just 25%, so you  would apply the first offer as often as possible,

It gets a bit more complicated if you accept offers where you deliver more than ordered. For example delivering an extra chocolate bar if it saves money

In your second example you would first try to apply the first deal once, then try again without it.


Decide the set of all Turing machines with $L(M)=\left\{\langle M\rangle\right\}$

The recursion theorem states that a Turing machine can get its own description on to its tape. In fact, there is a simple reduction from the acceptance problem (ATM) to this problem.

Assume $L$ is decidable. Suppose I am asked whether a TM $M$ accepts $w$. I will construct a machine $M'$ which on input $x$ checks if $x=\langle M' \rangle$. If it is not $\langle M' \rangle$ it simply rejects $x$. Otherwise it simulates $M$ on $w$, and if $M$ accepts $w$ then $M'$ accepts $x$. So $L(M') = \{ \langle M' \rangle \}$ iff $M$ accepts $w$. Hence we can pass this $M'$ as input to the decider $L$ and obtain answer for "$M$ accepts $w$?". But we know that ATM is undecidable, hence $L$ must be undecidable.


find the actual size of an object from pixel coordinates

Unfortunately you can't estimate the real size of an object from an image, since you do not know the distance of the object to the camera.

Geometric Camera Calibration gives you the ability to project a 3D world point onto your image but you can not project a 2D image point into the world without knowing its depth.


There are several ways to ensure product/code quality and functionality before deployment:

Basic functionality testing
Code Review
Static code analysis
Unit Testing
Single user performance testing


What were the shortcomings of Robinson's resolution procedure?

While "disappointing in practice" is certainly not definable formally, unlike "complete" (which does indeed mean "can eventually prove every true formula"), it's pretty easy to find examples where naive resolution is not even remotely adequate, i.e. examples which should be easy to prove but which resolution is extremely slow on.
A famous example is an encoding of the pigeon hole principle for $n$ holes in propositional logic (which is the statement "$n+1$ pigeons cannot fit in $n$ holes without duplicates). There is no proof of this statement using only resolution in time sub-exponential in $n$.
Things are even worse in predicate logic, where it is very easy to find statements without any fast resolution proofs.
Note that any implementation of resolution must implement a strategy for picking the resolvents, which is already a very difficult problem, and an active area of research, since most practical algorithms for theorem proving are enhancements of naive resolution, e.g. hyper-resolution.


Prove that $L^{\nsubseteq}_{M'}=\{ \langle M \rangle \ | \ L(M) \nsubseteq L(M')\}$ with $M'$ a TM that always halt is undecidable

Don't be confused by this question. Instead of studying $L^{\nsubseteq}_{M'}=\{ \langle M \rangle \ | \ L(M) \nsubseteq L(M')\}$ you might consider as well the language $L_G=\{ \langle M \rangle \ | \ L(M) \nsubseteq G\}$ for $G$ being any language. It is important to notice that there is always a Turing machines $M$ with $\langle M \rangle \in L_G$ but always a machine $M'$ with  $\langle M' \rangle \not \in L_G$. So you are looking for a nontrivial set of Turing machines. This allows you to apply Rice's theorem and you are done.

If you want to get a proof via reduction just look in the proof of Rice's theorem. It shows you how to get a generic reduction for these cases.


Finite subsets of the Halting problem are decidable. Can I prove the correctness of Turing machines computing these subsets?

You cannot always prove the correctness of the true value of $L_M$ (unless your proof system is inconsistent). Indeed, if you could, then given $M$, you could search for proofs that $L_M = \emptyset$ and for proofs that $L_M = \{M\}$, and eventually you'll find one, thus solving the halting problem.

Gödel's incompleteness theorem gives you a specific such machine. Suppose that your proof system is $P$ (for example, ZFC), and consider the machine $M$ that goes over all possible proofs in $P$, searching for a proof of contradiction, and halting if it finds one. Assuming that $P$ is consistent, we have $L_M = \emptyset$, but if $P$ could prove that, then it follows that $P$ proves its own consistency, which is ruled out by Gödel's second incompleteness theorem (assuming $P$ is not too weak).


How do I prove regular/non-regular with Nerode-Theorem? How to use it?

You'd have to prove that the equivalence relation for your language is of infinite index to show it isn't regular. If regular, the equivalence classes are exactly the states of tje minimum DFA for the language.

In this case, both are regular (if I understand the notation correctly, $L_1$ is just strings with no $a$; for $L_2$ you can take $u = \epsilon$ and $v$ the given string, so $L_2 = \{1, 2\}^*$). Nice red hering, BTW.


Kleene Star regex question, sed behavior?

$ printf "ab\n" | sed -En 's/b*// p' | od -t c
0000000   a   b  \n
0000003

This regex expression "$b*$" does match the empty string, which is zero '$b$', at the very front of the input "$ab$". This is in accordance with the definition of Kleene star since $b^*$ stands for the language $\{\epsilon, b, bb, \cdots\}$, where $\epsilon$ stands for the empty string. The matched part, an empty substring is replaced by the empty string. So, the same input string "$ab$" is printed with the newline attached.

Note that sed tries to find a match as early as possible. Although the substring "$b$" of "$ab$" matches "$b*$" more, it is ignored by sed completely since it happens later than the match said above.


find all intersections by checking all pairs of segments, belonging to different curves. Of course, filter them before real check for intersection.
Number all curves 1..n. Set some order of segments in them.
For every point create a sequence of intersections SOI, so: if it starts from the border end, SOI[1] is null. If not, SOI[1]= (number of the first curve it is intersecting with, the sign of the left movement on the intersecting curve). Go on, writing down into SOI every intersection - number of curve if there is some, or 0 if it is the intersection with the border.
Obviously, you are looking only for simple bordered areas, that have no curves inside.
Pieces of curves between two adjacent non-null intersection points we'll call segments.
Having SOI for each curve:

for segment of the curve 1, starting from the first point of the segment, make 2 attempts to draw a polygon of segments. It is 2 because you can go to 2 sides along the first intersecting curve.
For the right attempt, make only left turns, for the left attempt, make only the right turns.
If you arrive at point with no segment in the correct direction, the attempt fails. If you return to the curve 1, it success. You have a closed area.
Remember all successful attempts
Repeat this for all segments of curve 1
Repeat this for all other curves, checking all found areas against the already found ones. Two same adjacent segments is enough to consider areas equal.

Edit:
How to find the orientation of the intersection.

When segment p(p1,p2) crosses segment q(q1,q2), we can count the vector multiplication of vectors pXq. We are interested in only sign of its Z coordinate - that is out of our plane. If it is +, q crosses p from left to right. If it is -, the q crosses p from right to left.

The Z coordinate of the vector multiplication is counted here as a determinant of matrix:

0         0          1
p2x-p1x   p2y-p1y    0
q2x-q1x   q2y-q1y    0

(of course, it could be written more simply, but it is a good memorization trick)

Of course, if you'll change all rights for lefts, nothing really changes in the algorithm as a whole.


As Max said the modification is not difficult, I suggest that you do not read the rest of this answer and think about the problem a little bit more, there is only one part that needs modification and remembering the definition of when a $\mathsf{coNP}$ machine accepts will help you fix that part.

I will explain the required modification below, but first let's have a brief view at the original proof.

In the original proof $A=\bigcup_n A_n$ is built in steps where at step $i$ with make sure that $i$th machine in $\mathsf{P}$, $M_i$, doesn't decide the language $\{x \mid \exists y\in A \ |x|=|y| \}$ correctly. Note that the set is in $\mathsf{NP}^A$.

We achieve this by simulating $M_i$ using the part of $A$ we have built on a $0^m$ where $m$ is large enough (the string is longer than strings considered in previous steps). $M_i$ accepts, we don't add anything, if it rejects we add a string of length $m$ that $M_i$ doesn't make a query to the set (Such a string exists since there are exponentially many strings of length $m$ but $M_i$ cannot ask about all of them in polynomial time). We will not modify this part of $A$ in future steps (i.e. strings of length $m$ or less will stay the same). This makes sure that $M_i^A$ will not decide the language correctly and completes the proof.

   Now, assume that the machines $M_i$ were in $\mathsf{coNP}$ in place of $\mathsf{P}$. We need to modify the proof to make sure that $M_i^A$ will not recognize $L$. If it is accepting we keep $A$ as before and everything works fine as in the original proof. If it rejects, we need to add a string to the set to make sure it doesn't answer correctly. We still can simulate $M_i$ with the part of $A$ we have, the problem is that $M_i$ might query all strings of length $n$. Here the way a $\mathsf{coNP}$ machine works becomes important. It accepts if and only if all computation paths accept. Since it is rejecting in this case, there is a computation path that is rejecting. As long as we keep this path intact everything will work, so we only need to keep the answers to the queries in that path the same. The number of queries in this path is polynomial (since the machine runs in polynomial time), so there are strings of length $m$ that the path doesn't query about, just add one of them to $A$ and the rest of the proof works as before.

The steps are algorithmic, so the set $A$ is recursive (the essential part of the construction is being able to simulate machines which can be done in say $\mathsf{DSpace}(n^{\omega(1)})$).


Placing a point between two nearest ones

Don't add the point between the closest pair of points; add it between the endpoints of the closest edge.


Big-O notation for nested loops that might skip iterations

If the average number of times the inner loop is $O(f(n))$ then the total complexity is $O(n \times f(n))$.

Finding that average can be tricky when the condition is not trivial. however assuming that it never drops a loop will give you a worst case. This worst case will also be valid when the amount of inner loops skipped is a constant factor.

However in the first example the loop can be simplified to

for (var i = 0; i < n; i++) {
  visited[i] = true;

  for (var j = i+1; j < n; j++) {
      //...
  }
}

This is $O(n^2)$. Because $\Sigma_{i=0}^n i = \frac{n(n+1)}{2} = O(n^2)$


If NP is the class of problems that cannot be solved in polynomial time, what is co-NP?

Your prof was absolutely not rigorous (i.e. completely wrong), that's why the distinction between NP and co-NP doesn't make sense with his definition. Better definition:

Def.: A decision problem (that is a problem where the result is either YES or NO and nothing else) is in NP if for every instance where the result is YES there exists a hint such that we can prove that the result is YES in polynomial time in the size of the problem by using the hint. (You will notice that there need not be a hint to prove the answer is NO, if the answer is indeed NO).

An example (not NP complete): If your decision problem is whether a number is composite (YES) or prime (NO), then for every composite number I can give you as a hint one non-trivial factor f. Then you can prove that the answer is YES by checking that the number is divisible by f.

Interestingly, when the number is prime, there isn't such a trivial hint that let's you prove the answer is NO. (There are hints, but nowhere near as simple).

And co-NP is defined almost the same, except there must be a hint if the answer is NO. For every problem X in NP, you can pose the problem Y: "Is the answer to problem X NO", and that problem Y would be in co-NP by definition.


It is undecidable to check whether a turing maching has a smaller encoding than a given one.  Hence there cannot be any such concept as a transition graph.

If you simply want a smaller turing maching for your example, I would guess no, from a quick glance of it.


How do I "tell" a simple perceptron/adaline neural netrork its output can't be negative?

You can put the logistic function on top of the output:

f(z) = 1/(1 + exp(-z)).

You will also need to adjust the cost function accordingly, i.e. use log loss: https://www.kaggle.com/wiki/LogarithmicLoss


Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology?

The statement is: If a problem $P$ is $\mathbf{NP}$-hard, then there is a reduction from $\text{FALSIFIABLE}$ to $P$. ($\text{FALSIFIABLE}$ being the set of formulas for which there is an assignment which makes the formula false; this is trivially equal to the complement of $\text{TAUT}$.)

This statement is correct.

Why? Simply because $\text{FALSIFIABLE}$ is $\mathbf{NP}$-complete. You can prove this exactly the same way $\text{SAT}$ is proven to be $\mathbf{NP}$-complete, only inverting the truth values "true" and "false" (i.e., instead of searching for an assignment which makes the formula true, you search for an assignment which makes the formula false). This is not at all surprising; it is basically the duality principle of Boolean algebra.


What is the complement of Halting Problem?

The complement of a language $L$ is the language of all strings (over the same alphabet) not in $L$. So the complement of any language exists, by definition. It may be empty, which seems to be the case here.

However, your definition of HP is a bit strange, as every program for a given input either halts after a finite number of steps or does not. So, including both in HP obviously gives you all programs.

It might be more useful to consider something similar to the halting set $K := \{ (i, x) | \text{program $i$ halts when run on input $x$}\}$ (see wikipedia),
i.e. the language of all programs that halt.

The complement of $K$ is then, of course, the set of all programs that do not halt.


Sub-linear-time ordered set (!= sorted set) implementation?

Another pretty simple solution is a balanced binary search tree with threading (an overlaid linked list passing through all the nodes of the tree in order of their original insertion). Then insertion/search/removal are all O(log n), and iteration is O(n). You just update insert/remove to either append to the linked list or remove the node from it.


Is it possible to write a wait free leader election algorithm?

I believe that leader election derives from consensus algorithm, not other way around.  When electing leader you need consensus about who was chosen.

I'm not sure what you understand by "wait free". All communication in distributed system is asynchronous, and you always need to wait for reply.

You could start all nodes with ordered list of all possible leaders. When leader goes down all nodes could just pick next one from the list.  But again, to notice that leader goes down you need to ping it, and wait for response.  And probably coordinate (create consensus) that we changed a leader (if not, you will have a problem when encountering partitions).

So, last option is to choose one leader at start (trough config) and not allow any change.  But this does not fulfills requirements of most distributed system or leader election problem.


Number of logic gates for "reasonable" Turing completeness

As soon as you limit "memory" you are talking about machine models that are equivalent to finite automata. If you limit "memory" to input size, you are at linear bounded automata, which are easily seen to be limited to recognizing (some) recursive sets.


Is there a Context-free grammar for this language?

Here is a PDA for this language. While reading $x$, the whole of $x$ is pushed onto the stack. After encountering $\#$, the PDA pops some non-deterministic amount of symbols, then verifies that the top symbol is $1$, and pops $m$ symbols. It acceptes if the stack is empty.

Variant: instead of popping a part of $x$, while reading $x$ the PDA non-deterministically stops pushing symbols into the stack; it only does so after reading a $1$.

As for a CFG for this language, here is the idea:
$$
\begin{align*}
&S \to \Sigma^{m-1} 1 T 1^m \\
&T \to \Sigma^* \#
\end{align*}
$$

I'll let you construct an actual grammar based on this idea.


Space efficient data structure for subsets of [1:n]

Bit vectors fulfill all your requirements.


What is the difference between formal language, regular language and regular expression?

An alphabet $\Sigma$ is a finite collection of symbols. For example, $\Sigma = \{0,1\}$.

A word over an alphabet $\Sigma$ is a finite sequence of letters from $\Sigma$. For example, $0$, $01$ and $1110$ are all words over $\{0,1\}$. The empty word (that is, the empty sequence) is also allowed, and denoted $\epsilon$ (or sometimes $\lambda$).

The collection of all words over $\Sigma$ is denoted $\Sigma^*$.

A formal language over an alphabet $\Sigma$ is a set of words over $\Sigma$. Equivalently, a formal language over $\Sigma$ is a subset of $\Sigma^*$.

A regular language over $\Sigma$ is a formal language over $\Sigma$ which is accepted by some DFA.

A regular expression over $\Sigma$ has the following syntax:

$\epsilon$ is a regular expression.
$\sigma$ is a regular expression for all $\sigma \in \Sigma$.
If $r_1,r_2$ are regular expressions then so are $(r_1)^*$, $(r_1+r_2)$ and $(r_1r_2)$.

In practice we don't write all the parentheses. Each regular expression denotes some formal language (you will learn this translation in class). It turns out that a formal language is regular if and only if there is some regular expression denoting it.

If you have any more questions, I recommend reading a textbook which covers regular languages, for example Hopcroft and Ullman.


Describe in words how a NTM can simulate a DTM

A nondeterministic Turing machine has zero or more possible transitions in every configuration; a deterministic one has exactly one. One is "zero or more".


Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

The class NC is the class of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. Is your problem to decide - or actually compute the Determinant of a Matrix? Chistov's algorithm solves for the determinant in the class NC with $(log$ $n)^2$ processors, and is the best(?) so far for the class NC(Reference:  Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic. A. L. Chistov ). As an aside, the question whether the class  P is equivalent to NC is still open.


Karp hardness of directed monochromatic triangle problem

All directed graphs can be edge-partitioned into two subgraphs that are acyclic and therefore triangle free.

Let $\prec$ be any total ordering of the vertices. For each edge $(u, v) \in A$, put it in $A_1$ if $u \prec v$, and in $A_2$ otherwise. Both $(V, A_1)$ and $(V, A_2)$ must be acyclic.


Algorithm for graph with nodes grouped into sets

The special case of zero-one weights is already NP-hard. In fact, even determining whether there is a choice such that the total weight is zero is NP-hard. See this question on cstheory.se. (You can arrange that all the weights are, say, $1$ or $2$, and then the condition that two connected parts are fully connected is satisfied.)


Machine learning: do the benefits of more data plateau after a certain point?

Yes, typically there will be a plateau.  There's usually no way to guess exactly where the plateau will be, a priori; the only way to find out is to build larger and larger data sets and see what happens.

The size of the data set needed to reach a "plateau" is dependent on many factors, including the specific classification task you're trying to solve, the machine learning algorithm you're using, the set of features you've chosen, and maybe other considerations.  For some tasks, a fairly small training set might be sufficient to reach the "plateau".  For others, you might need an incredibly enormous training set -- so large that you'll never reach it in practice, so effectively you'll never hit a plateau in practice.

There's absolutely no way to answer your specific questions about how many images are needed for particular domains.  I know you're hoping there will be some rule of thumb that'll help you predict how many images you need for some new classification task, but I've got bad news for you; there's not really any useful rules of thumb that I'm aware of.  The only way to find out is to try it, or to read research papers or experience reports from others who have tried to solve the same task or a similar task.

It's also worth keeping in mind that the notion of a plateau should not be taken too seriously.  Rather, you should think of it as diminishing returns.  After some point, increasing the size of the training set will give diminishing returns in accuracy.  It's not to say that there's necessarily a point where you get literally zero improvement; it's just that the improvement available from a larger training set might be extremely small, i.e., where the accuracy curve starts to become nearly horizontal, when graphed as a function of the size of the training set.

In the comments you separately talk about "the point when a classifier reaches 95% of human accuracy".  That's not the same thing as a plateau; that's a totally different measure.  For some classification tasks, humans are way better than any classifier we know of; we don't know of any machine learning approach that will get anywhere near human accuracy, let alone 95% of human accuracy, no matter how large a training set you have.  For other classification tasks, machine learning can do better than any human -- so the classifier gets not just 95% of human accuracy, but maybe 200% of human accuracy.  Comparing a classifier's accuracy to human accuracy is unrelated to the existence and location of a plateau (i.e., diminishing returns as you increase the size of the training set).


Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular

Nice question! This is a very nontrivial problem involving regular languages.
First of all: no, you cannot run an automaton on every substring of a string skipping other letters, you are supposed to run the automaton only once on the target string.
In this case it is simpler to reason on the complementary of the given language, namely on
$$L^C =  \{ w \in  (a,b) ^ * \mid \text{ there is a substring } u \text{ of } w \text{ such that } |u|_a−|u|_b>5 \text{ or } |u|_a−|u|_b<-5\}$$
The language $L^C$ is regular, as it is recognized by the following NFA:

(each state name is the difference $|u|_a−|u|_b$, the first letter of the substring $u$ is "found" nondeterministically by the NFA).
So, as $L^C$ is regular, also $L=(L^C)^C$ is.

Following Hendrick's suggestion, I tried to determinize the NFA and to draw its complement, and I get this nice DFA that recognize $L$:

Each name of an accepting state name is an interval: when, running the automaton, we are in state $[x_1,x_2]$ and we have read the string $z$ this means that for all $x\in [x_1,x_2]$ there is a suffix $u$ of $z$ such that $|u|_a−|u|_b=x$. Otherwise said, following Dmitry's suggestion, the automaton calculate the residual set of $z$.
In a sense, as Hendrick says, it is like we are running the automaton on each substring, but this do not mean that we can directly use a DFA that recognize strings such that the difference between the $a$s and the $b$s is in $[-5,5]$ (which would be easy to realize) and run this automaton on each substring of a given one, and in this way prove that the language is regular.

Lastly, I would write a trivial generalization of the result (I think that this is folklore, but I couldn't find a reference).
Let $T$ be a regular language on an alphabet $\Sigma$ and let $L$ be the language defined as follows:
$$L=  \{ w \in  \Sigma^* \mid \text{ for every substring } u \text{ of } w,\ u\in T\}$$
then also $L$ is regular.
Indeed, as above, consider $L^C$, the complement of $L$, namely
$$L^C =  \{ w \in  \Sigma^* \mid \text{ there is a substring } u \text{ of } w \text{ such that } u\not\in T\}$$
Then $L^C=\Sigma^*T^C\Sigma^*$, and therefore $L=(\Sigma^*T^C\Sigma^*)^C$ is regular, as the family of regular languages is closed under concatenation and complementation.
Cleary the result is still true for every family of languages closed under concatenation and complementation, but this is not a necessary condition. Indeed, the family of finite languages it is not closed under complementation, but clearly if $T$ is finite, then also $L$ is (as it is always the case that $L\subseteq T$).
On the other hand, this is not true for all classes of languages. Consider the family NR of non-regular languages, then $T=\{1^p\mid p\text{ is prime}\}\in\ $NR, but in this case we have $L=\varnothing$, which is regular.


Removing conflicts of LR(1) parsing tables

The ambiguity comes from

I -> id

because that rule means that both I ans E derive id, which in turn means that return id could be a derivation of either:

S -> return E ; S

or

S -> return I ; S

Also, id1 = id2 could be derived from:

I -> id = E

or

I -> id = I

It doesn't make sense for id to be a statement if id + 3 is not; I'd just drop the I -> id production.


Meaning of $\stackrel{*}{\rightarrow}$ production rule?

It's either the transitive closure or reflexive-transitive closure of $\rightarrow$. That is, $A\rightarrow B$ means that you get from $A$ to $B$ in exactly one step; $A\rightarrow^*B$ means either you get to $B$ in one or more steps (transitive closure) or in zero or more steps (reflexive-transitive closure).


Proof that an almost complete binary tree with n nodes has at least $\frac{n}{2}$ leaf nodes

According to this Wikipedia page:

  In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between $1$ and $2^h$ nodes at the last level $h$. An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed. Some authors use the term complete to refer instead to a perfect binary tree as defined below, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree...

So, you are talking about a binary tree with $h$ levels, for which all levels  with numbers $k \in [0,h-1]$ are completely filled up (i.e. have $2^k$ nodes), and the level $h$ is potentially incomplete - it contains $(2^h-r)$ nodes, where $r \in [0, 2^h-1]$ is the number of (rightmost) removed nodes. Total number of nodes of such tree is $(2^{h+1}-r-1)$. Let's find the number of leaves for this tree.

If $r$ is even, then the removal of $r$ nodes on the level $h$ will give you $\frac{r}{2}$ new leaves. So, the total number $l_{even}$ of leaves will be:

$$l_{even}=2^h - r + \frac{r}{2} = 2^h - \frac{r}{2}$$

if $r$ is odd, then the removal of $r$ nodes on the level $h$ will give you $\frac{r+1}{2}$ new leaves. So, the total number $l_{odd}$ of leaves will be:

$$l_{odd}=2^h-r+\frac{r+1}{2}=2^h-\frac{r-1}{2}$$

Now you'll be able to verify, that in both cases:

$$l \ge \frac{2^{h+1}-r-1}{2}$$


Perfectly Secure Ciphers known other than the OTP

I have looked into this question before and came up very short. From it, I believe that it may be the case that a cipher with this property is simply the Vernam Cipher (OTP) in disguise. It is still an interesting question as to how the use of additional resources or changes in protocol can potentially implement an equivalent to OTP with less effort. While it, itself, might not be exactly considered a cipher (or even a huge deviation from the one time pad), I found the following information theoretically cryptosystem to be incredibly interesting when I stumbled upon it a couple years back:

There is a more recent scheme (early 2000's), by Michael Rabin, called hyper-encryption, that can be shown to be information theoretically secure given the assumption that your adversary is space bounded (most others have assumptions on time bounds). As required by the scheme, there must be a very large, public, source of random bits.

The basic premise is for the sender and recipient to use the key to methodically pick out a one time pad from the random source of bits (using randomness extractors). In order to get this pad, the adversary would have to not only store the ciphertext, but also would need to store almost all of the random bits for use later. Their limited ability to store information would prevent them from doing this.

After the transmission is complete, access to the random bits is closed. The theory here is that, even if the key was revealed afterwards, that the adversary would not have enough information to establish anything about the plaintext. This remains true even if they had unlimited computational power, since no amount of post-analysis will get around the fact that the one time pad used depended on information that the adversary did not store. Since this security is not compromised even if the key is revealed after the transmission, the scheme is said to have perfect forward secrecy.


You can have many sales of the same product in the same store and in the same week. Also, a detergent can be sold in different weeks in different stores.

This means that you have to create a class Sale, that associates an OnSaleKey to a DetergentKey.

The Sale class is an association class.

From here you can find an explanation:

  An association may be refined to have its own set of features; that
  is, features that do not belong to any of the connected classifiers
  but rather to the association itself. Such an association is called an
  association class. It is both an association, connecting a set of
  classifiers and a class, and as such could have features and might be
  included in other associations.

  An association class can be seen as an association that also has class
  properties, or as a class that also has association properties.

  An association class is shown as a class symbol attached to the
  association path by a dashed line. The association path and the
  association class symbol represent the same underlying model element,
  which has a single name. The association name may be placed on the
  path, in the class symbol, or on both, but they must be the same name.

In this case it is easier to think about the Sale class as a table in a database that associates an id from OnSaleKey to an id from DetergentKey.


A "simple" way of solving this problem is to write an emulator for the first machine's instruction set on the second machine. Then set the first program as input to this emulator. One could also apply partial evaluation techniques to optimise things a little, which would result in an emulator that runs only the first program (and nothing else).


Minimal paths as solution of a linear program of a special network flow

There is a major flaw in your question: You presented a shortest path formulation and not a special case of a network flow problem.
Your objective function minimizes the cost of the path. The next 5 constraints are the classic flow constraints, which ensure a path between $s$ and $t$. The last constraint is just the bound of variable $x$.

Now, we can start answering your questions:

  Given that every s−t-path fulfills the constraints, we can conclude that if S is an s−t-path, then it is an s−t-path with minimal costs.

Correct. It is the shortest path on the defined graph.

  Further, S can't contain any cycle with positive weight, as we could simply remove this cycle from S and end up with a lower-cost solution that fulfills the constraints.

The solution of a shortest path problem does not contain a cycle, for obvious reasons.

  Did I miss something in the proof?

Sorry, but your proof does not show anything. You are showing that the shortest path is the shortest path.

  This whole procedure seems like a lot for a less efficient method to obtain a shortest path

Because you are solving the shortest path problem :)
However, I still recommend you to stick with Dijkstra's algorithm, which is faster than linear programming.

  Besides the non-negativity constraint, all constraints are actually equalities.

Yes, good observation. You just have the classic flow constraints (which are all equalities). I recommend you to read the Ahuja's book on network flows (is the best I know, by the way).

  The algorithm should be easily adaptable to also allow for negative cycles (by putting some linear restriction on the solution, e.g. that the path mustn't be too long, etc.)

You can do that. However, this constraint lies in enumerating all the cycles of your graph, which cannot be fastly solved.


Many to one reductions from undecidable Turing Machine to a decidable language

From what I read, a many-to-one reduction $A \leq_m B$ means that $\forall x \in A$, there exists a computable function $f$ s.t. $f(x) \in B$.

No. It's not "for each element $x\in A$ there exists a computable $f$ ...", but "there exists a computable total $f$ s.t. for each $x\in A$ we have $x \in A \iff f(x) \in B$".

Your definition is wrong because:

it allows us to pick a different function for each $x\in A$, when we must pick only one;
it only states $x\in A \implies f(x)\in B$, when we need the double implication $\iff$;
$f$ must be total (maybe this is supposed to be implicit when you don't say "partial", but it's important)

  However, $f$ is not necessarily surjective (i.e. not all elements in $B$ have to be mapped).

Correct.

  Where $f$: On input $(i,w)$, if Turing Machine $i$ accepts $w$, then a Turing Machine $M$ outputs a Graph $g$ that has a 2-vertex cover (any arbitrary graph with a valid 2-node vertex cover), and does otherwise.

How do you check that TM $i$ accepts $w$? I guess you are simply suggesting to simulate TM $i$. If you do that, there is a possibility of non termination here: precisely, every time $i$ diverges. Hence, $f$ is not total in this case: since its implementation diverges on some inputs.


Computing a Sequence of People Entering and Leaving a Room

Base case It's easy to generate the combinations when $n=1$: just use the operation $e_1$.

Recursion Now assume that you have a sequence $ops_n$ that will generate all the combinations of $n$ people. Define $rops_n$ to be the sequence of operations that "undoes" $ops_n$, namely first form the reverse of $ops_n$ and then replace all "enter" operations with "leave" operations and vice versa. For example, if $ops_2 = \langle\, e_1, e_2, x_1\,\rangle$, then $rops_n =\langle\, e_1, x_2, x_1\,\rangle$. It's not difficult to see that $ops_n, rops_n$ will generate all the combinations of $n$ people and then produce the same combinations in reverse order.

Finally, show that if $ops_n$ generates all the $n$-combinations, then the sequence $ops_n, e_{n+1}, rops_n$ will generate all the $(n+1)$-combinations: first all the ones without person $n+1$ and then all the ones with person $n+1$. From this construction it's clear inductively that you can generate all $n$ combinations with $2^n-1$ operations.

As per the hint you were given, this is very similar in spirit to the Towers of Hanoi problem: To move $n+1$ disks from peg 1 to peg 2, you first move $n$ disks from peg 1 to peg 3, then move the largest disk to peg 2, and finally move the $n$ disks on peg 3 to peg 2.


Applying SVD compression to integral point images

Does SVD compression only work for floating point images?

It seems quite obvious that it works for arbitrary images.  Whether you are satisfied with the amount of compression or not doesn't really change the fact that it works.

I think looking at the compression ratio is going to lead to misleading results.  Suppose you take two images: $I_1$ uses 8-bit RGB, and $I_2$ is the same image but captured using 24-bit RGB.  Note that it is often fairly challenging to distinguish between two such images, and the differences are often perceptually minor.  Now suppose you compress both with lossy compression.  Suppose that both compressed images happen the same size.  Then the compression ratio of $I_1$ is 3x worse than the compression ratio of $I_2$.  Does that mean that compression doesn't work for 8-bit RGB images?  No, it means that $I_2$ has a bunch of extra information that isn't semantically relevant.  Thus, a compression algorithm that throws away this irrelevant information will achieve a higher compression ratio.  That's not because the compression algorithm is better; it's just a reflection of the fact that $I_2$ has more irrelevant information (or information with low relevance).

And this is exactly the situation you're in.  There is no way that the low 8 bits of those 32-bit floating point numbers are perceptually meaningful; no human is going to be able to perceive those.  So, if you're capturing an image with 32-bit floats, then some of the bits of those floats are pure noise that are perceptually completely irrelevant.  So, of course a compression algorithm that throws away that irrelevant information is going to achieve a higher compression ratio.  Does that mean that compression on 8-bit images doesn't work?  No, it just means there was less irrelevant information to throw away.  This phenomenom is not specific to SVD-based compression; it will likely be true for any form of good lossy compression.

I can always make the compression ratio arbitrarily good by appending a bunch of irrelevant useless information to the input, and then modifying my compression algorithm to throw away the irrelevant information.  That doesn't mean I have a better compression algorithm, or that the compression algorithm doesn't work or is unacceptable on the original images.

For all of these reasons, I think a better way to compare the two schemes is by the size of the compressed image, not by the compression ratio.  And both variants you describe achieve the same size compressed image, so the apparent difference evaporates.

Second, when you're doing your comparison, there is no reason why you need to hold $k$ fixed.  Usually we think of lossy compression as a tradeoff between the size of the compressed image vs the perceptual quality.  You have two tunable parameters: $k$, and the number of bits of precision that use for the entries of the outputs of the compression.  You are free to choose those arbitrarily to maximize the perceptual quality of the image, for a given image.  For instance, instead of using one value of $k$ and 32-bit floats, you might do better to double $k$ and use 16-bit floats.  Probably only empirical experiments can help you set those parameters in the optimal way... but you shouldn't assume what the optimal setting will be, or that it will necessarily be the same for both settings (both 8-bit inputs vs 32-bit inputs).


Do all the numbers belong to same slot in the Hashtable?

Keys are uniformly distributed means that they are drawn from a space with equal probability.

So if we set the hash function to be $h(k)=\lfloor{km}\rfloor$, then each given element is equally likely to hash into any of the $m$ slots. (Refer to the definition of simple uniform hashing in page 259 CLRS)

Yes, it is true that each element with key $k$ will be hashed to the same slot. But the point is the elements are chosen uniformly independently, so they have the same probability to hash to any of the $m$ slots.


Heap - Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list

The purpose of the heap is to give you the minimum, so I'm not sure what the purpose of this for-loop is - for j := 2 to k.

My take on the pseudo-code:

lists[k][?]      // input lists
c = 0            // index in result
result[n]        // output
heap[k]          // stores index and applicable list and uses list value for comparison
                 // if i is the index and k is the list
                 //   it has functions - insert(i, k) and deleteMin() which returns i,k
                 // the reason we use the index and the list, rather than just the value
                 //   is so that we can get the successor of any value

// populate the initial heap
for i = 1:k                   // runs O(k) times
  heap.insert(0, k)           // O(log k)

// keep doing this - delete the minimum, insert the next value from that list into the heap
while !heap.empty()           // runs O(n) times
  i,k = heap.deleteMin();     // O(log k)
  result[c++] = lists[k][i]
  i++
  if (i < lists[k].length)    // insert only if not end-of-list
    heap.insert(i, k)         // O(log k)

The total time complexity is thus $O(k * \log k + n * 2 \log k) = O(n \log k)$

You can also, instead of deleteMin and insert, have a getMin ($O(1)$) and an incrementIndex ($O(\log k)$), which will reduce the constant factor, but not the complexity.

Example:
(using value rather than index and list index and heap represented as a sorted array for clarity)

Input: [1, 10, 15], [4, 5, 6], [7, 8, 9]

Initial heap: [1, 4, 7]

Delete 1, insert 10
Result: [1]
Heap: [4, 7, 10]

Delete 4, insert 5
Result: [1, 4]
Heap: [5, 7, 10]

Delete 5, insert 6
Result: [1, 4, 5]
Heap: [6, 7, 10]

Delete 6, insert nothing
Result: [1, 4, 5, 6]
Heap: [7, 10]

Delete 7, insert 8
Result: [1, 4, 5, 6, 7]
Heap: [8, 10]

Delete 8, insert 9
Result: [1, 4, 5, 6, 7, 8]
Heap: [9, 10]

Delete 9, insert nothing
Result: [1, 4, 5, 6, 7, 8, 9]
Heap: [10]

Delete 10, insert 15
Result: [1, 4, 5, 6, 7, 8, 9, 10]
Heap: [15]

Delete 15, insert nothing
Result: [1, 4, 5, 6, 7, 8, 9, 10, 15]
Heap: []

Done


If both the concatenation of two languages and the second "half" are regular, is the first too?

Suppose that $L_2 = \Sigma^*$ and $L_1$ includes the empty string. Then $L_1 \cdot L_2 = \Sigma^*$, yet $L_1$ doesn't even have to be computable.


Is a set of acyclic |V| - 1 light edges always a Minimum Spanning Tree?

The answer to the question in the title, "Is a set of acyclic $|V|-1$ light edges always a Minimum Spanning Tree?" is no. That is, the second claim in the question is not true. Hence, the third claim is not true, either.

Here is a simple counterexample. Let $H$ be a graph the complete graph with 4 vertices, $\{a,b, c,d\}$ and weights, $ab\rightarrow 1$, $cd\rightarrow 1$, $ac\rightarrow 2$, $ad\rightarrow 2$, $bc\rightarrow 2$, $bd\rightarrow 2$. The weight of a minimum spanning tree $\{ab, ac, cd\}$ is $1+1+2=4$. Consider the spanning tree made by the 3 edges, $\{ac, bc, bd\}$, each of which is light for the cut $\{a, b\}, \{c,d\}$. However, the weight of this spanning tree is $2 + 2 + 2 = 6$, which is greater than $4$.

One might be wondering why it might be so hard to come up with a counterexample. Part of the reason might be that if the weights of edges of $G$ are different, then $G$ has only one minimum spanning tree, which includes all light edges for every cut.


The following algorithm will solve your problem

Strategy

The task is decomposed into 2 subtasks:

Derive an annotated DAG from $G$.
Contract cycles in $G$ to single nodes while traversing the implied spanning tree of a DFS, creating a graph $G'$,
Conduct a BFS on $G'$ with reversed edge orientations, identifying and marking nearly roots.

Details

Perform a DFS on $G$. It's used as a tool to identify and contract cycles while keeping tabs on the number of contracted nodes.
For cycle contraction it suffices to detect backward edges ( mark/unmark nodes when entering a node for the first time / leaving it for the last time ). Each time a backward edge $(w, v)$ has been detected, all nodes on the current DFS path $p = v \stackrel{*}{\rightarrow} w$ are coalesced into a new node $v'$, edges from nodes on $p$ are retained. These modifications can be done in situ ( $V_{i} := (V_{i-1} \ \{ x \in V_{i-1} | x \in p \}) \cup \{ v' \}$, $E_{i} := (E_{i-1} \ \{ (x,y) \in E_{i-1} | x \in p \}) \cup \{ (v',y) \in V_{i}^2 | y \notin p \})$ for the $i$-th contraction, starting with $(V_0, E_0) := (E, V)$). Mark each node in $V_{i}$ with an attribute represents containing the number of nodes from $V$ it represents (i.e. initialising this attribute with $1$ and adding the cycle length subtracted by $1$ for each contraction). in case of contracted nodes also record the represented nodes by adding it to a stack attribute.
The resulting graph $G'$ is cycle-free (in particular: irreflexive). Next perform a BFS on $G'$ with all edges reversed. Propagate an attribute reachable: $V \rightarrow \mathbb{N}$ along the way which locally computes as $\text{reachable}(v) := (\text{represents}(v) - 1) +  \sum_{w \in pred(v)\subset V'} \text{reachable}(w)$ with pred denoting the set of predecessors  and reachable being initialised to $0$ for all maximal elements in $G'$. for all nodes $v \in G'$ with $\text{reachable}(v) \geq |V|/2$, mark all represented nodes from the original graph $G$ as nearly roots.

Complexity

Complexity of this operation is $O(E)$, as each edge is traversed at max 2 times in the course of the DFS and the contraction while the bookkeeping operations are $O(V)$ in total.
Complexity of this operation is $O(E)$, as each edge in $G'$ is traversed once during the BFS and $|E'| \leq |E|$. Updating reachable is $O(V')$ while marking the nodes from $G$ as nearly roots costs at most $O(V)$.


identities property of squaring functor?

Ok, I have worked it out:

$$
id^2 (a, b) = (id(a), id(b)) = (a, b) = id_{A^2} (a, b)
$$


Is it possible to write an AND gate using XOR gates?

You cant.

Since $XOR$ is associative, i.e. $(x_1\oplus x_2)\oplus x_3=x_1\oplus(x_2\oplus x_3)$, you can only implement functions of the form $x_{i_1}\oplus...\oplus x_{i_k}$ where $x_{i_j}\in\{x_1,x_2\}$. This is equivalent to (depending on the parity of the number of instances of $x_1$ and $x_2$) either 0, $x_1$, $x_2$, or $x_1\oplus x_2$, which are not equivalent to AND.


I think I have managed to figure it out from the paper, and would like to leave my explanation for the next person who struggles with this concept.

From my understanding, Tiernan means nothing of a mathematical nature when he says "$u$ is closed to $v$". He's actually trying to say "$u$ is closed off to $v$", i.e. no longer accessible.

By following along with Tiernan's paper and his example, his algorithm manages to discover a cycle with the following vertices:

  $v_1, v_2, v_4, v_3, v_5$

Now that he has discovered a cycle, he removes the last vertex $v_5$ to see whether another vertex, say $v_x$, can be added to the remaining nodes, e.g. $v_1,v_2,v_4,v_3,v_x$, in the hopes of finding another cycle.

However, to avoid rediscovering the same cycle (such that $v_x \ne v_5$), the vertex $v_5$ is now closed to $v_3$ and $v_3$ cannot extend an arc to it again. In the matrix $H$, we now have $H[3,1] = v_5$ (or simply $5$ since Tiernan requires unique integer labels for each vertex). If $v_3$ would become closed to another vertex before $v_3$ was removed from $P$ (to backtrace and attempt to discover cycles using $v_1, v_2, v_4, v_x$), then that vertex would be placed in $H[3,2]$.

In a nutshell, "closed to" should actually be "closed off to/inaccesible" due to the fact that the node was already used as the last node in either a cycle, or a "non-cyclic dead end". This prevents the algorithm from rediscovering the same cycles over and over.


Classes of NFAs which allow efficient subset testing or unambiguity conversions

here are three refs that may be helpful.

Efficient Inclusion Testing for Simple Classes of
Unambiguous $\omega$-Automata
Dimitri Isaaka, Christof Lodinga

  We show that language inclusion for languages of infinite words defined by non-
  deterministic automata can be tested in polynomial time if the automata are
  unambiguous and have simple acceptance conditions, namely safety or reachability conditions. An automaton with safety condition accepts an infinite word
  if there is a run that never visits a forbidden state, and an automaton with
  reachability condition accepts an infinite word if there is a run that visits an
  accepting state at least once.

this 2nd ref is more indirect & would rely on a mapping between NFAs and tree automata.

Antichain-based
Universality and Inclusion Testing
over Nondeterministic Finite
Tree Automata
Ahmed Bouajjani, Peter Habermehl,
Luka´ˇs Hol´ık, Tayssir Touili, and
Toma´ˇs Vojnar

  We show the signiﬁcantly improved efﬁciency of this framework through a series of experiments
  with verifying various programs over dynamic linked tree-shaped data structures

the above ref also cites the following:

Antichains: A New Algorithm for Checking
Universality of Finite Automata, M. De Wulf, L. Doyen, T. A. Henzinger, and J.F. Raskin

  We show that on the difficult instances
  of this probabilistic model, the antichain algorithm outperforms the standard one by several orders of magnitude. We also show how variations
  of the antichain method can be used for solving the language-inclusion
  problem for nondeterministic finite automata...


Algorithm for computing the sum of symmetric sums (better than $\mathcal{O}(2^N)$ )

But $g(x,a)$ is linear in $a$ so if you can compute it efficiently for two different values of $a$ then you can compute it efficiently for all $a$?


Most fast sieves are segmented, so you can get this in efficient amortized time.  When you call to get the next segment, you may have to increase the auxiliary prime list, but that's a trivial amount of time.  Then you just sieve that segment, exactly how it would be done if you were sieving to some large known upper bound.  You can wrap all of that in a next() call.  I believe primesieve and primegen both have setups like this.  This is also how my forprimes and forcomposites work, as well as my iterator in Perl/ntheory.

This is likely faster than prime-by-prime extensible sieves.  I see in the Rosetta Code extensible prime generator task the C solution is a simple segmented generator like I mention above.  The first D solution is the rather horrible method you noted.  A number of the languages, including Go, implement O'Neill's lazy functional sieve which is more directly what you might be asking for.  Ben Tilly shows a lazy sieve using closures in Perl here that should meet your complexity goal.

Of course you can do primality tests, but that takes more time than sieving until your input is large (how large depends on your implementations of both sieve and primality test, but it would certainly be before 10^25).


The given dfa (d) will be formed.
As far as your question about removal of state r: it can't be removed because state q is having transition to state r on input b. This is necessary because a dfa cannot leave any input transition, that is, it must define all the transitions for each and every state and for each and every input given to those states.


You could start your investigation from an online bipartite matching [PDF] point of view.

In specific, in this case, you know one side of the bipartition, namely the seats and their properties, and then you will get orders on-the-fly (online).  The performance you are looking to analyze is the number of matched buyers in the online algorithm versus the number of matched buyers if you'd know the buyers in advance (offline).


How does the computer determine whether a number is smaller or greater than another?

First your integer numbers are converted into binary numbers. For example, the integer 2 is converted to 0010.

The CPU uses a digital comparator:

  A digital comparator or magnitude comparator is a hardware electronic
  device that takes two numbers as input in binary form and determines
  whether one number is greater than or less than or equal to the other
  number.

  Comparators are used in central processing units (CPU) and microcontrollers.

  Source: https://en.wikipedia.org/wiki/Digital_comparator

In comparator hardware some gates are used (AND, OR, NAND, NOR, XOR, etc). These gates take binary inputs and give result in binary. The output can be seen from a truth table.

Inputs           Outputs
A   B     A>B    A=B    A<B
0   0     0       1      0
0   1     0       0      1
1   0     1       0      0
1   1     0       1      0

Here 0 & 1 are  electronic voltages for the gate.
1 - Represents some threshold voltage which indicates some positive voltage. 0 - Represents the voltage below than the threshold.

E.g. suppose a comparator works on 5 volt (it is consideration for explanation) then:
Voltage more than 3 volt can be considered as binary-1.  Voltage below than 3 volt be considered as binary-0

If a gate gets one input as 3.5 volt and another input as 2 volt then it considers as, it takes one input as binary 1 & another input as binary 0.

These sequences of 1's & 0's are provided very fastly through the switching circuit.

The operation of a two bit digital comparator can be expressed as a truth table:

 Inputs                            Outputs
   A1   A0  B1  B0  A>B    A=B   A<B
    0   0   0   0    0      1     0
    0   0   0   1    1      0     0
    0   0   1   0    1      0     0
    0   0   1   1    1      0     0
    0   1   0   0    0      0     1
    0   1   0   1    0      1     0
    0   1   1   0    1      0     0
    0   1   1   1    1      0     0
    1   0   0   0    0      0     1
    1   0   0   1    0      0     1
    1   0   1   0    0      1     0
    1   0   1   1    1      0     0
    1   1   0   0    0      0     1
    1   1   0   1    0      0     1
    1   1   1   0    0      0     1
    1   1   1   1    0      1     0

To quote from Wikipedia:

  Examples:
  Consider two 4-bit binary numbers A and B such that

  Here each subscript represents one of the digits in the numbers.

  Equality

  The binary numbers A and B will be equal if all the pairs of significant  digits of both numbers are equal, i.e.,
   .  .   .

  Since the numbers are binary, the digits are either 0 or 1 and the boolean  function for equality of any two digits  and >  can be expressed as

    is 1 only if  and    are equal.

  For the equality of A and B, all  variables (for i=0,1,2,3) must be 1.
  So the quality condition of A and B can be implemented using the AND operation as

  The binary variable (A=B) is 1 only if all pairs of digits of the two numbers are equal.

  Inequality

  In order to manually determine the greater of two binary numbers, we inspect the relative magnitudes of pairs of significant digits, starting from the most significant bit, gradually proceeding towards lower significant bits until an inequality is found. When an inequality is found, if the corresponding bit of A is 1 and that of B is 0 then we conclude that A>B.
  This sequential comparison can be expressed logically as:


Minimum pumping length of regular language

Your example in fact demonstrates that the pumping length can be smaller than the number of states in the minimal DFA. In your case the minimal DFA contains 3 states, but the pumping length is 2.

The pumping length of a language $L$ is the minimal $p$ such that every word $w \in L$ of length at least $p$ can be written as $w = xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$.

If $L$ contains no words of length $p$ that's not problematic at all. For example, the pumping length of $\{ w \}$ is $|w|+1$. In that case the pumping property holds vacuously.


Complexity for checking if an array is a min-d-heap

Apart from the answer given by rici in the comment to the question, I've come up today with an answer to prove this exact algorithm's time complexity, and it's pretty simple:

Since the algorithm goes over all of the parents in the heap (i.e all the nodes that have children), we only need to look at them while calculating the time complexity. The first parent is obviously the first item in the array. The last parent, is the parent of the last item in the array. The last item in the array is located at index $n-1$, therefore the parent of the last item (and the last parent) is located at index $\lfloor\frac{n-2}{d}\rfloor$ which is $O(\frac{n}{d})$. Therefore - we have $O(\frac{n}{d})$ parents in the array. For each parent we make $d$ comparisons, and finally we get the time complexity of $O(\frac{n}{d}*d) = O(n)$.


Prove Halting on all Inputs is not in RE simulation

What is the Halting on all inputs problem?

It is the problem about the language $TOTAL=\{⟨M⟩\mid M \text{ is a TM and }M\text{ halts on all inputs} \}$.

What are all inputs? Let us fix $\Sigma$, the set of input symbols for Turing machines. The set of all inputs is $\Sigma^*$, the Kleene star of $\Sigma$. Let $E$ be a Turing machine that computes a one-one correspondence $cor$ from $\Sigma^*$ to nonnegative numbers.

In order to specify the behavior of a Turing machine $M$ whose language/encoding is in $TOTOAL$, we will just specify its behavior when the input is a nonnegative integer $n$ with the understanding that we are actually specify its behavior on the input that corresponds to $n$ under $E$.

What is the complement of the halting Halting problem?

It is the problem about the language $\overline{HALT}= \{⟨M, w⟩\mid M \text{ is a TM and }M\text{ does not halt on input } w\}$.

Given a word $⟨M, w⟩$ where $M$ is a Turing machine and $w$ is a input word, how can we construct a new Turing machine related to the way how $TOTAL$ is specified?

  $M'$ = simulate $M(w)$ for $n$ steps; if $M(w)$ halts, make it loop else, stop.

The above quotation of a construction is too brief to be understood correctly easily. Here is a more detailed construction that should be easier to understand.

  $M' = $ "On input $x$, use $E$ to compute $cor(x)$. Simulate $M$ with input $w$ as long as possible but for no more than $cor(x)$ steps. If the simulation halts, continue to loop forever; otherwise, halt."

Now you should be able to check that
$$⟨M, w⟩\in\overline{HALT} \Longleftrightarrow M'\in TOTAL.$$

The too-brief version equates $x$ with $cor(x)=n$, which could be very confusing for beginners although acceptable for users experienced in the theory of computability.

  I don't understand why do I have to make M' simulate M(w) for N STEPS. Why can't I just simulate it one and that's it?

The "N" in "N STEPS" is/represents/encodes the input to $M'$. It is a variable independent of $M'$.


Finding the rows/columns of an m-by-m symmetric similarity matrix M which minimizes the sum of the elements in an n-by-n submatrix N, where n < m

Unfortunately this problem is NP-hard, meaning the best exact algorithm you can hope for will take exponential time in the worst case.
It is NP-hard because any algorithm that would solve this problem can also be used to solve the NP-hard problem Independent Set (IS), in which we have a graph $G = (V, E)$ and an integer $k$, and ask whether there is a subset $X \subseteq V$ of $k$ vertices such that no pair of vertices in this subset are adjacent. Given any algorithm for solving your problem, any instance $G$ of IS can be solved by giving this algorithm the adjacency matrix for $G$, in which every element is 1 (indicating a pair of vertices connected by an edge) or 0 (indicating a pair of vertices that are not) as input, together with $N=k$; there is a size-$k$ independent set in $G$ if and only if there is a subset of $N$ rows/columns in the matrix having sum $N$ (i.e., all diagonal elements are 1 and the rest are 0).


Minimax strategies apply to games with scores. A minimax strategy maximized the guaranteed score. Assuming that you prefer a win to a draw and a draw to a loss, you can choose three scores $a > b > c$ arbitrarily and assign them as your value in the case of a win, a draw, and a loss, respectively.


What Do Logical Operators In a Grammar Mean?

A grammar generates a language, it doesn't accept it. Automata accept languages.

The whole point of gramars is that they are easily able to generate quite complex languages. Even regular languages (accepted by finite automata or denoted by regular expressions) can be very hard to describe in simple terms.

In this case, the grammar generates (a subset of) logical formulas, with connectives and ($\wedge$), or ($\vee$), and not ($\thicksim$).


pictorial representation of pre and post ordering for edge types

"I am assuming that $u$ is the node/vertex we see first and then we see $v$ later." That is a wrong assumption, which makes that summarizing table unintelligible.
The right assumption consists of two parts.

We are given a directed graph that contains $(u,v)$, the edge from $u$ to $v$.
We have just completed one depth first search (DFS) on that graph, which has discovered both $u$ and $v$.

Given the assumption above, that table lists the correspondence between the "pre/post ordering for $u$ and $v$", and the "edge type" of $(u,v)$. Please note that I rephrase "pre/post ordering for $(u,v)$" as in the table to "pre/post ordering for $u$ and $v$", since the meaning of "$(u,v)$", the edge from $u$ to $v$ does not fit the former phrase exactly.

The first row, "$\stackrel{[}{u}\,\stackrel{[}{v}\,\stackrel{]}{v}\,\stackrel{]}{u}\ $ Tree/forward" says that $u$'s discovery time and departure time enclose $v$'s discovery time and departure iff $(u,v)$ is a tree edge or a forward edge. $u$ is visited first in this case.
The second row, "$\stackrel{[}{v}\,\stackrel{[}{u}\,\stackrel{]}{u}\,\stackrel{]}{v}\ $ Back" says that $v$'s discovery time and departure time enclose $u$'s discovery time and departure time iff $(u,v)$ is a back edge. $v$ is visited first in this case.
The third row, "$\stackrel{[}{v}\,\stackrel{]}{v}\,\stackrel{[}{u}\,\stackrel{]}{u}\ $ Cross" says that $v$'s discovery time and departure time are before $u$'s discovery time and departure time iff $(u,v)$ is a cross edge. $v$ is visited first in this case.

Neither do we assume $u$ is visited first nor do we assume $v$ is visited first. The node that is visited first on each row of that table is, of course, the node that appears first from the left on that row.

Exercise (as given in the book). With the same assumption, "do you see why no other orderings are possible?" For example, why is "$\stackrel{[}{v}\,\stackrel{[}{u}\,\stackrel{]}{v}\,\stackrel{]}{u}$" not possible? why is "$\stackrel{[}{u}\,\stackrel{]}{u}\,\stackrel{[}{v}\,\stackrel{]}{v}$" not possible?


Building maze to maximize shortest path, may be given waypoints and teleports

Just a note: even the simpler version without waypoints and teleports is NP-hard:
Start with a maze in which the dots mimic the edges of a grid graph $G$ of max degree 3,  and $X$s are placed "around" them (the dots are "corridors"). Put the $O$ in a corner and the $F$ near it with a dot in the middle.
Maximizing the shortest path (adding more Xs) is equivalent to finding an Hamiltonian path in the original graph $G$ which is NP-complete (each new $X$ must block a "corridor", i.e. it removes an edge of $G$).


Algorithm to find a minimal regular language containing given context-free language

There is no "smallest" regular language containing any non-regular langauge.

First, note that every finite language is regular, so any non-regular language $L$ must be infinite.  Consider some regular language $R\supset L$. $R\setminus L$ must also be infinite since, if it were finite, then $L = R\setminus (R\setminus L)$ would be regular, because regular languages are closed under difference. So, in particular, we can take any finite $S\subset R\setminus L$ and the langauge $R\setminus S$ is regular, is a strict subset of $R$ and a strict superset of $L$.

In other words, whenever you have a non-regular $L$ and a regular $R$ such that $L\subset R$, there is another regular $R'$ such that $L\subset R'\subset R$ (and, in fact, infinitely many of them).


Theoretical question about Zobrist hashing and chances of collision with slight modification

it may be better to store them in separate hash table. or, if you need them in the same table:

tmp = position
if (makeItUnique)
    tmp := [memory address of position object]
hash = zobristHash(tmp);

It's better than your current code since it will avoid collisions of objects with the same position AND similar memory address (the definition of similarity here depends on how you use the hash value to address the hash table)


Relation beetween log-space reduction and polynomial time reduction

Every terminating Turing machine running in logarithmic space terminates in polynomial time. This is because the number of configurations in a logarithmic space Turing machine is polynomial; a logspace Turing machine running longer than the number of configurations will necessarily repeat a configuration, and so will never terminate.

More generally, $\mathsf{SPACE}(f(n)) \subseteq \mathsf{TIME}(2^{O(f(n))})$ for similar reasons. This gives not only $\mathsf{L} \subseteq \mathsf{P}$ but also $\mathsf{PSPACE} \subseteq \mathsf{EXPTIME}$.


Is Carry Look-Ahead adder used in modern ALUs?

“Huge and complicated” is no problem, as long as it is fast. It isn’t.

A good choice seems to be a conditional sum adder (CSA) which has a total delay of O(log n) gates. Log n is nice for 64 bit adders.


Bubble Sort: Runtime complexity analysis line by line

The runtime in the original post is correct.  The O(n) runtime is for a different algorithm, called optimized bubble sort.


Show that $x^3 = O(x^4)$ and $x^4 \neq O(x^3)$

We say that a function $f$ is $O(g)$ if there exist constants $M$ and $C > 0$ such that
$$
 x > M \Longrightarrow f(x) \leq C g(x).
$$

It shouldn't be too difficult to show that $x^3$ is $O(x^4)$ using the definition.

To show that $f$ is not $O(g)$ you need to show that for every $M$ and $C > 0$ there exists $x > M$ such that $f(x) > C g(x)$. While using this to refute "$x^4$ is $O(x^3)$" is a bit awkward, I think that it's a good exercise which is not too difficult.

Later on you might learn other ways of showing that $f$ is not $O(g)$. Very briefly, the idea of the other methods is a two-pronged attack:

If $f$ is $O(g)$ then X.
X is false.
Therefore $f$ is not $O(g)$.

I'll let your professor give you examples of X.


Your algorithm is not really specified completely, since you don't explain how you choose the word $w$. However, even once you do specify how $w$ is chosen, your algorithm will be incorrect. The reason is that it is completely symmetric in $M_1$ and $M_2$. In other words, if the algorithm accepts on the pair $(M_1,M_2)$, then it will also accept on the pair $(M_2,M_1)$. This means that it will necessarily fail for machines satisfying $L(M_1) \subseteq L(M_2)$ but $L(M_2) \nsubseteq L(M_1)$.
Presumably in class you were shown other decision algorithms for regular languages. I suggest you try to emulate them. As an example, here is an algorithm that determines whether $L(M) \neq \emptyset$, for a DFA $M$.

Input: A DFA $M = \langle \Sigma, Q, q_0, F, \delta \rangle$.
Accept if some state in $F$ is reachable from $q_0$, and reject otherwise.

(In class you will probably need to be more verbose.)
To show that this algorithm is valid, we need to show two things:

If $L(M) \neq \emptyset$, then the algorithm accepts.
If $L(M) = \emptyset$, then the algorithm rejects.

To prove the first part, suppose that $w \in L(M)$. By definition, the state $\delta(q_0,w) \in F$ is reachable from $q_0$, so the algorithm accepts.
To prove the second part, we will prove the contrapositive: if the algorithm accepts, then $L(M) \neq \emptyset$. Suppose that some state $q \in F$ is reachable from $q_0$. This means that there is some path from $q_0$ to $q$. If $w$ is the concatenation of all symbols on this path, then $\delta(q_0,w) = q \in F$, and so $w \in L(M)$, showing that $L(M)$ is non-empty.
(Once again, in class you will probably need to be more verbose.)


counterexample for this graph isomorphism algorithm

I've not looked closely at your algorithm so I'm not sure exactly what it does. However, it sounds quite a lot like colour refinement (also known as the 1-dimensional Weisfeiler-Lehman method). I suggest you look at the following paper, which will both explain that method and show a class of graphs whose isomorphism problem it cannot solve, even though graph isomorphism on those specific graphs is in P.  Even if your algorithm turns out to be different from colour refinement, a similar construction might give some graphs it doesn't work on.

J.-Y. Cai, M. Fürer and N. Immerman, An Optimal Lower Bound on the Number of Variables for Graph Identification.  Combinatorica, 12(4):389–410, 1992. (Free PDF)

By the way, one thing you can (probably) do to avoid the labels your algorithm assigns from becoming exponentially long is to just replace them with 1, 2, ... at each round.  You (probably) don't need to know exactly what label each vertex has; rather, you (probably) just need to know whether two vertices have the same label or not.


Capsule networks for classification with limited data

Actually, the literature so far suggests that convolutional networks have better accuracy than capsule networks on many tasks, so it's by no means clear that capsule networks are superior across the board to CNNs.  This is perhaps not surprising; we have many years of experience working out how to engineer convolutional networks so we get the best possible performance out of them, whereas capsule networks are still new and haven't yet benefitted from that degree of engineering.  So, we might see further improvements in the performance of capsule networks in the coming years, now that they are getting more attention.

There are some specific areas where capsule networks have significantly outperformed convolutional networks.  Those seem to be primarily those where viewpoint invariance is especially critical.  There are others where so far they are worse.  For instance, capsule networks so far have done significantly worse than convolutional networks on CIFAR10.  There is active research and an active debate in the machine learning community about how well capsule networks will perform.  I think it's too early to say how that will pan out.

As far as amount of training data, it is likely that this will depend on the task as well, and is probably an open problem at this point.  I would imagine that capsule networks might need significantly less training data for tasks where viewpoint invariance is especially central, but that might not be true across all tasks.

In general, not a lot is known yet about the performance of capsule networks, and the answer to most questions of the form "how well will capsule networks perform on X?" is "you'll have to try it and see".


Besides RTS and CTS, there are a few other "optional" signals such as DTR, DCD,...

These signals are mostly about checking if the other end of the cable is ready. Ready can mean that the internal buffer is not full, or related to some hardware condition, such as being powered or that the phone line is up ("DCD"=Data Carrier Detect).

These signals can be made optional in several cases :

The buffers are very large, or the datarate is low, and there is no practical risk of losing data. The endpoints are always ready. This is the case nowadays with computers used as terminal emulators over asynchronous serial lines.
Some flow control mechanism is used to signal over the data lines when to start and pause transmissions : For example XON / XOFF https://en.wikipedia.org/wiki/Software_flow_control
The protocol has messages and answers, for example an initiator sends a message of predefined lenght, and waits for the answer of the target. There are many other options, such as time-triggered communications. Serial lines can be used for many purposes. There are traditional terminal or teletype connections, there are also gazillions communications protocols for embedded or industrial applications. The protocols can be designed to not need hardware flow control signals.


Does the k-clique problem became easier on sparse graphs?

Let me not completely agree with Yuval's answer.

Indeed, in some sense sparsity does make a maximum clique problem easier, and this is proved also by solving it on real-life networks. Usually benchmarks for a maximum clique are pretty dense. And here is why.

If it is known an integer $k$ that is a lower bound of the clique number (or the number itself, but we are looking for a clique), then one can reduce the graph to $(k-1)$-core, that is the graph where each node has a degree at least $k-1$. The resulting graph might be considerably smaller in size and thus, for example, IP solver might get a huge boost. How to reduce: delete all vertices with degree smaller than $k-1$ until those exist.
If you look at sparsity not from the density perspective, but from the degeneracy perspective, things are even more formalized. Usually we say that graph is "sparse" when its degeneracy is low. And there exists FPT algorithms with running time around $O^{*}(2^{d/4})$ where $d$ is graph's degeneracy (here big-O star means that the algorithm depends polynomially on the graph size).

Conclusively, the maximum clique problem is immensely easier on sparse instances, though it still remains $\mathcal{NP}$-Complete (but FPT on degeneracy).


Suppose you have a tree like

        a           <-- level = 0
      / | \
     b  c  d        <-- level = 1
   /
  f                 <-- level = 2

    v1, v2, v3
Q : b,  c,  d
    1,  1,  1

v3.d <= v1.d + 1   i.e 1 <= (1+1)

Now, suppose head of Q (i.e b) is removed and its neighbors are inserted in Q

    v1, v2, v3
Q : c,  d,  f
    1,  1,  2

v3.d <= v1.d + 1   i.e 2 <= (1+1)

This, v3.d <= v1.d + 1 can be also be seen as v3.d - v1.d <= 1 which means at any point of time distance between elements of queue will always be less than or equal 1. This can also be seen from the fact that during the execution of BFT only elements from 2 successive levels are present in queue. There cannot be case such that 2 elements A and B are present in queue with A at level x and B at level (x + 2).


What is the name of this positive integer set data structure?

The name of the data structure, as @Evil correctly pointed out, is an Inversion List.

And boy is that Wikipedia article a stub.


A data structure to do a specific lookup fast

Using SSE2 operations, you can save the entire dataset in 512 KB and search through it, with 4-core CPU, is less than 10 microseconds.

PCMPB+PMOVMSKB instructions will give you 16-bit mask made from 16 byte-wide comparisons. You need to combine two such masks as a<<16+b and make sure that result is all 0s.

Even faster approach is to make bitmap for each p[i]<k condition, overall you need 30*6=180 bitmaps. Each bitmap takes 30K/8=3.75 KB, overall 675 KB.

You need to AND-combine 30 maps corresponding to chosen x[i], i.e. AND-process 675/6=112.5 KB of data. With 128-bit SSE operations, this requires 7K operations, and on the same 4-core CPU, it's less than microsecond long.


Could min cut be easier than network flow?

Here is a possible approach:

Suppose you know the cut S, then finding the flow from $S$ to $t$ is a min cost network flow problem with zero cost, since you know exactly the outflow at each vertex in $V\setminus S$ and in the inflow at $t$. Suppose $f$ denotes an $S-t$ flow and $A$ the node-arc matrix (i.e. row $i$, col $j$ has 1 if $i$ is the tail of $j$, -1 if its the head, zero otherwise), and let $b$ be such that $Af = b$ if $f$ satistfies the supply/demand, and the flow conservation. Then with gaussian elimination we can find a feasible solution in $|V|^3$ operations.

To find a cut from a flow we need to construct the residual graph which takes at most $|E|$ time, and then potentially traverse $|V|$ vertices.

So for complete graphs and the minimum cut being just the source or just the sink, the reduction takes equal time in both directions worst case. However, I would think that finding a feasible solution to $Af =b$ can be done faster than $|V|^3$ given the special structure. I am not sure how to prove that though.


If the number of steps executed in the $i$th iteration is $i^2$, then the number of steps overall will be asymptotic to
$$
\sum_{i=1}^n (C+i^2) = \Theta(n^3),
$$
for some constant $C$ that comes from the loop control (i.e., incrementing $i$ and checking whether it equals $n$).

To see that $\sum_{i=1}^n (C+i^2) = \Theta(n^3)$, use
$$
\sum_{i=1}^n (C+i^2) \leq n(C+n^2) = Cn+n^3 = O(n^3), \\
\sum_{i=1}^n (C+i^2) \geq \sum_{i=n/2}^n i^2 \geq (n/2) (n/2)^2 = n^3/8 = \Omega(n^3).
$$
(In fact, $\sum_{i=1}^n i^2 \approx n^3/3$, as can be seen by approximating it by the integral $\int_1^n i^2 \, di$, or by using the exact formula $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$.)


As general concepts, the words signal, notification and event are mostly interchangeable, though they carry different connotations and some words wouldn't be used to denote some specific mechanisms. A particular operating system or other concurrency framework may use these terms for different mechanisms.

Some differences to watch for (with signals, events or whatever they're called) include:

Synchronous vs asynchronous: does the sender block until the recipient receives the signal?
Stacking: if multiple identical signals are generated before the recipient acknowledges any of them, will the recipient receive that many signals, or can they be merged?
Associated information: is the signal just “hey, wake up”, or does it have an associated tag, or does it have a payload (which could be a pointer to a larger data structure)?
Destinations: does the signal target a specific task (unicast), or a set of recipients (multicast), or all tasks that care (broadcast)? In the multicast case, will all the specified targets receive the signal, or is the signal cleared as soon as one task acknowledges it (this may be termed unicast rather than multicast)?

For example, POSIX signals are asynchronous, unicast (multicast if sent to a process group), they stack, and have a tag which is a small integer. I'm not familiar with TinyOS; from a quick read of the tutorial I think they are asynchronous, unicast (perhaps with other possibilities), non-stacking, and have a payload (and, incidentally, sending an event is called signalling it; receiption is called triggering, because the event in TinyOS terminology is the handler instance rather than not the message).

I think the word event wouldn't be used if there is no associated information at all. The word signal wouldn't be used if there's a rich payload: with a rich payload, it's a message, possibly an event or a notification. GUI frameworks often call notifications of user input events; GUI events have a payload (e.g. to identify which key was pressed) and don't stack.

The use of the word event tends to promote event-driven architectures, where programs are structured as event callbacks rather than as a thread that checks for notifications periodically, but it isn't limited to this use.


What algorithm is suitable for very small scale, time dependent optimization?

Many optimization procedures are based upon successive approximation: they start with a value of $x$, and try to successively refine $x$ to move it closer and closer to the optimum.  For instance, hill climbing and gradient ascent both have this structure.

You can use this structure to solve your problem.  Let $x_t$ be the maximum for $f_t$.  Then you can use $x_t$ as the starting point (the initial approximation) when looking for the maximum for $f_{t+1}$.  Now iterate, using the maximum for the previous time period as the starting point for hill climbing / gradient ascent / .... in the next time period.  If the maximum for $f_{t+1}$ is close to the maximum for $f_t$, this might work reasonably well.

There are many different possible ways to instantiate this basic approach.  Here are some possible examples of how this might look:

With gradient ascent, you evaluate $f_{t+1}$ three times at three points near $x_t$: e.g., at $x_t$, $x_t+(\varepsilon,0)$, and $x_t+(0,\varepsilon)$.  You use the result to estimate the gradient around $x_t$, and then move in the direction of the gradient.

As a possible optimization/variation, you might align the axes in the direction of the gradient for $f_t$.  For instance, if the gradient was maximum in the angle $\theta$ for $f_t$, you might evaluate $f_{t+1}$ at the three points $x_t$, $x_t+(\varepsilon \cos \theta, \varepsilon \sin \theta)$, $x_t + (\varepsilon \cos (\theta+\pi/2), \varepsilon \sin (\theta+\pi/2))$, then use those values to estimate the gradient.
As another possible optimization, you could follow this with a line search.  Suppose $\delta$ is the direction that maximizes the gradient.  Then you could evaluate $f_{t+1}$ at $x_t,x_t+\delta,x_t+2\delta,x_t+3\delta,x_t+4\delta,\dots$, stopping at the first one that stops providing any improvement.  Or, you could evaluate $f_{t+1}$ at $x_t,x_t+\delta,x_t+2\delta,x_t+4\delta,x_t+8\delta,\dots$.  You could even follow this with an iteration or two of binary search to find the best stopping point, though that might not be worthwhile.
If you are trying hill-climbing, you will do something simple like this: pick a random point $x'$ in the neighborhood of $x_t$, and if $f_{t+1}(x') > f_{t+1}(x_t)$, then move to $x'$.  You can repeat this a few times.

Of course, you can combine these methods.  There may be many other variations you could try.  I would suggest that you read about methods for optimization, brainstorm other similar methods, and then try them all to see which work best.

Also, you might want to try a simulation: choose $f_t$ that you believe to be representative and where you can evaluate them as many times as desired to find the true maximum and their shape, and then simulate each of these strategies to see how well they work.  You might also want to visualize the shape of the $f_t$ and what these strategies are doing (what points they are visiting), in case that helps you refine them or choose suitable constants that are appropriate for your particular application domain.


What is the asymptotic time complexity of the following 2 recurrences?

For the first recurrence, let $n_0 = n$ and $n_{t+1} = n_t/\log n_t$. As long as $n_t \geq \sqrt{n}$, we have $n_{t+1} \leq n_t/\log \sqrt{n_t} = n_t/((1/2)\log n)$, and so we reach $\sqrt{n}$ in $\log_{(1/2)\log n} n \approx \log n/\log \log n$ steps. It takes us another $\approx (1/2) \log n/\log \log n$ steps to get to $\sqrt[4]{n}$, and so on. If you do the calculation in full, you will probably find out that $n_m = O(1)$ for $m = O(\log n/\log\log n)$. In other words, for a constant fraction of the sequence $n_0,\ldots,n_m$, the value of $\log n_t$ is $\Theta(\log n)$. This justifies the approximation $n_t \approx n/\log^t n$. Under this approximation, we find out that (ignoring the $\Theta$)
$$
\begin{align*}
T(n) &\approx n^i \log^k n + \log n \cdot (n/\log n)^i \log^k n + \log^2 n \cdot (n/\log^2 n)^i \log^k n + \cdots \\ &\approx
n^i \log^k n + n^i \log^{k-(i-1)} n + n^i \log^{k-2(i-1)} n + \cdots
\end{align*}
$$
The answer now depends on the value of $i$. If $i > 1$ then the terms keep decreasing, and so we expect $T(n) \approx n^i \log^k n$. If $i = 1$ then the terms are roughly the same size. Since there are roughly $\frac{\log n}{\log \log n}$ of them, we expect the answer to be $T(n) \approx \frac{\log n}{\log \log n} n^i \log^k n$. If $i < 1$ then the terms keep increasing, and so we expect the major contribution to come from $$\log n_0 \log n_1 \log n_2 \cdots T(\mathit{const}).$$ By definition, $\log n_t = n_t/n_{t+1}$, and so
$$
\log n_0 \log n_1 \log n_2 \cdots = \frac{n_0}{n_1} \frac{n_1}{n_2} \frac{n_2}{n_3} \cdots \approx n.
$$
So in this case, $T(n) \approx n$.

If we do the same for your second recurrence, we get
$$
T(n) \approx n^i \log^k n + n \log n \cdot (n/\log n)^i \log^k n + n \log n \cdot (n/\log n) \log n (n/\log^2 n)^i \log^k n + n \log n \cdot (n/\log n) \log n \cdot (n/\log^2 n) \log n (n/\log^3 n)^i \log^k n + \cdots \approx
\sum_{t=0}^m \frac{(n \log n)^t}{\log^{\binom{t}{2}}n} (n/\log^t n)^i \log^k n =
n^i \log^k n\sum_{t=0}^m n^t \log^{-t(i-1)-\binom{t}{2}} n
$$
Let us denote the $t$th term in the sum above by $S_t$. Then
$$
\frac{S_{t+1}}{S_t} = \frac{n}{\log^{i+t+1} n}.
$$
For the largest $t$ we consider, $\log^t n \approx n$, and so we expect the largest term to be near the end. This implies that
$$
\begin{align*}
T(n) &\approx n_0 \log n_0 \cdot n_1 \log n_1 \cdot n_2 \log n_2 \cdots \\ &=
\frac{n_0^2}{n_1} \frac{n_1^2}{n_2} \frac{n_2^2}{n_3} \cdots \\ &=
n_0 n_1 n_2 \cdots.
\end{align*}
$$
The approximation $n_t \approx n/\log^t n$ seems harder to justify in this context, but it should give us a ballpark estimate:
$$
n_0 n_1 n_2 \cdots \approx
n \cdot \frac{n}{\log n} \cdot \frac{n}{\log^2 n} \cdots \approx \frac{n^{m+1}}{\log^{\binom{m}{2}} n}.
$$
We chose $m$ so that $\log^m n \approx n$, and so we expect the ratio to be $n^{\Theta(m)}$. In other words, $T(n) \approx n^{\Theta(\log n/\log \log n)}$.

All the estimates above are non-rigorous, and for this reason, they could be wrong. However, they point the way toward a more rigorous treatment.


In Paxos, what prevents multiple values from being chosen?

I'll assume this is Basic Paxos. Step (4) cannot occur - the acceptor A maintains in nonvolatile memory the largest promise it has made (the highest round it has agreed to vote on). At step (2), the max promise becomes 2. When A recieves P1's accept request in step (3) it will reject it because the accept request is from round 1 (this information is communicated in the accept request).


How to get a base-3 representation of an integer using a stack?

ok I think I found the solution to my question

So if n = 141, 12020 would be printed to the screen.

Solution:

          public static void printBase3(int n){
           if (n/3 == 0)
           System.out.print(n);
          else{
          printBase3(n/3);
          System.out.print(n%3);
          }
        }


Reducing k Vertex Cover to SAT (last clause problem)

First of all, the problem of vertex cover asks whether there is a vertex cover with at most $k$ vertices. Fortunately, there is a vertex cover with at most $k$ vertices iff there is one with exactly $k$ vertices, so your choice of looking for a vertex cover of size exactly $k$ is fine.

Second, you need to describe everything as a CNF, that is, a collection of clauses. You can't just include
$$
y_{i,j} \equiv (y_{i-1,j} \land \lnot v_i) \lor (y_{i-1,j-1} \land v_i).
$$
Fortunately, every formula on $t$ variables can be written as a CNF having at most $2^t$ clauses (exercise), so you can turn this formula into a CNF of constant size.

Finally, you say that you "should write $y_{nk}$ in terms of $v_1 \cdots v_k$", but there is no such requirement. An instance of SAT is just a bunch of clauses. You can use whatever variables and clauses you want; the distinction between original variables $v_i$ and extension variables $y_{i,j}$ is all in your head. If you want to force $y_{n,k}$ to be true, you can just add a singleton clause $y_{n,k}$.


Find Divisible Sum Pairs in an array in O(n) time

Consider in your example the set $S_1=\{1, 4\}$ and the set $S_2=\{2,5\}$. Let $n_1 = 2$ and $n_2=2$, the sizes of sets $S_1$ and $S_2$. All of the elements $x\in S_1$ satisfy $x\equiv 1\pmod 3$ and so are of the form $x=3s+1$ for some $s$. Similarly all $y\in S_2$ are of the form $y=3t+2$ so $x+y=3s+1+3t+2=3(s+t+1)$, which is divisible by 3. The number of such pairs is $n_1\cdot n_2$: pick one element, $x$, from $S_1$ and one element, $y$, from $S_2$ to form the pair $(x, y)$, rearranging, if necessary so that the first element is less than the second. In sum, there will be $n_1\cdot n_2=2\cdot 2$ pairs: $(1, 2), (1, 5), (4, 2), (4, 5)$, which, after arranging the pairs in component orders, gives $(1, 2), (1, 5), (2, 4), (2, 5)$ (your highlighted quote didn't do that).

For a general $k$, then, you'll have sets $S_i$, for $i=1, \cdots k-1$ (ignoring $S_0$ for the moment), so if $n_i$ represents the size of $S_i$, you'll have pairs $(x,y)$ where $x\in S_i$ and $y\in S_{k-i}$. The number of such pairs is $n_1\cdot n_{k-1}+n_2\cdot n_{k-2}+\dotsc$.

[You have to be a bit careful, since, first, the sum only should include those products $n_i\cdot n_{k-i}$ for which $i<k-i$, and second, you'll have to account for the cases where $i$ and $k-i$ are equal. You'll also have to deal with the pairs you get from $S_0$, which have to be counted differently.]

I'd suggest ignoring the sentence where $n(n-1)/2$ appears: it's true but irrelevant.


Generate all combinations of values that are less than array's elements and have a sum = target

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


Regarding part (a): just like in the classical lower bound for sorting, any black box algorithm which queries $f$ can be described as a binary decision tree whose leaves contain the correct answer $\{j_1,j_2\}$. Every pair $\{j_1,j_2\}$ is possible, so the tree must have at least $\binom{n}{2}$ leaves, hence it must have height at least $\log_2 \binom{n}{2} = \Omega(\log n)$.

If you don't understand the argument, look up the $\Omega(n\log n)$ lower bound on sorting in the comparison model (also known as the decision tree model).

Can we do it with $O(\log n)$ queries? Suppose for simplicity that $n = 2^k$ is a power of $2$. If we feed the algorithm the bit string $x(b_{k-1}\ldots b_0) = b_i$ then we get the $i$th bit of $j_1 \oplus j_2$, so using $\log_2 n$ queries we can find $j_1 \oplus j_2$. Suppose for simplicity that $j_1 \oplus j_2 = 1$. If we feed the algorithm the bit string defined by $x(b_{k-1}\ldots b_1 0) = 0$, $x(b_{k-1}\ldots b_1 1) = b_i$, then we recover the $i$th bit of $j_1$ (or $j_2$), so using $\log_2 n - 1$ more queries, we recover $j_1,j_2$. In total, we used $2\log_2 n - 1$ queries, which practically matches the lower bound $\log_2 n + \log_2 (n-1) - 1$.

Unfortunately I can't help you with part (b).


The merge sort algorithm creates a complete binary tree, which has depth 'd' and at each level, a total of n elements.
So, 2d ≈ n, which implies d ≈ log2 n


Do you have idea how to check $x_1 \leq c$ as well? Then just check $(x_1 \leq c) \wedge (x_1 \geq c)$ which implies $x_1 = c$.


Shortest path from that passes through a set of edges once

Assumption: Since you talk about Dijkstra, I assume you have non-negative edge weights.

Remember that Dijkstra already computes shortest paths to all other nodes. That is, after two runs -- one with $A$ and one with $B$ as starting node¹ -- you have shortest paths from $A$ to all nodes incident to $X$, and from $B$ to all nodes incident to $X$.

We just have to make sure that there are no edges from $X$ on these paths. The idea is to make edges from $X$ so expensive that choosing all other edges is better than picking just one edge from $X$. That actually pretty straight-forward to do.

Let $W = 1 + \sum_{e \in E} w(e)$; then modify the weights so that

$\qquad\displaystyle w'(e) = \begin{cases} w(e), &e \not\in X;\\W + w(e), &e \in X.\end{cases}$

A shortest path w.r.t. $w'$ of weight $<W$ is shortest w.r.t. $w$ when ignoring paths that hit $X$; if it has larger weight there is no path that avoids $X$ between the two nodes.

Now, if the shortest path from $A$ to $B$ you find by the two Dijkstra runs has weight $<W$, it is one contender for the shortest path. In addition, you have to find the best pair of paths that connect $A$ and $B$ to different ends of an $X$-edge. Combine for all $e \in X$ the shortest paths to $A$ and $B$, and add the original weight $w(e)$.

Note that there are two pairs of paths for each such $e$! That is, we get $2|X|+1$ paths to chose to minimal one from².
So that is an additional $\Theta(|X|)$ effort, which is dominated by the initial runs of Dijkstra.

In total, this solves your problem with two Dikjstra runs and one graph modification that can be performed in $\Theta(|E|)$, or even on-the-fly if your algorithm is implemented with nice abstractions.

This only works in undirected graphs. If your edges are directed, you need to perform the second run on an reversed copy of $G$.
If there is none with weight $<W$ then the original graph doesn't have any path from $A$ to $B$ that hits $X$ at most once!

This answer saw heavy revision. While the ideas were all there from the start they were presented as two solutions, neither of which worked on its own. Credits to Draex_ for picking the post apart!


Why does going from 2's complement (in binary) to the positive value by completing to 1 then adding 1 work?

Suppose that your integers are $n$ bit long. One's complement changes $x$ to $2^n-1-x$, since adding $x$ to its one's complement gives $\underbrace{1\dots 1}_{n}{}_2 = 2^n-1$.

Subtracting 1 and taking one's complement changes $x$ to $2^n-1-(x-1) = 2^n-x$.

Taking one's complement and adding 1 changes $x$ to $(2^n-1-x)+1 = 2^n-x$.


Proof of a greedy algorithm used for a variation of bin-packing problem

Let $G$ be the solution produced by the greedy algorithm. For each other solution $S$, let $i(S)$ be the index of the first weight at which $S$ diverges from $G$. Let $O$ be an optimal solution maximizing $i(O)$. Thus $G$ places $i(O)$ in bin $j$ (for some $j$), and $O$ places $i(O)$ in bin $j+1$. If we move $i(O)$ to bin $j$ (which is possible since $O$ is ordered), we obtain a solution $O'$ using at most as many bins as $O$, and satisfying $i(O') > i(O)$. This contradicts the choice of $O$.

If we try to run this argument on the unrestricted bin packing algorithm, we will have trouble when moving $i(O)$ to bin $j$, since that bin might be occupied with other elements, not leaving enough room for $i(O)$. In the variant you consider, this cannot happen.


There's no reason to think that reinforcement learning would be effective here.  Indeed, the surprise would be if it did work!  Machine learning isn't a magic silver bullet.  I wouldn't expect it to be of any assistance here; the problem relates to deep questions about the structure of the general linear group, which might be quite challenging for your policy network to learn.

Your problem is known as the membership problem for the general linear group, which might be hard (i.e., no efficient algorithm is known), depending on which field you are working over.  See https://cstheory.stackexchange.com/q/38000/5038.  If we take $T=0$ and are working with $n \times n$ matrices, this is called the matrix mortality problem; it is undecidable for $n \ge 3$.  See also https://en.wikipedia.org/wiki/List_of_undecidable_problems#Problems_about_matrices.  So, in the general case, your problem is undecidable.

Obviously, you shouldn't expect your approach to successfully solve an undecidable problem.