Minimal DFA accepting strings whose length is divisible by $x$ or $y$

Let $\operatorname{gcd}(x,y) = g$, and suppose that $x,y > g$. If there is a minimal DFA for the language with $n$ states, then according to the pumping lemma, there is $1 \leq m \leq n$ such that the following holds: $\ell \geq n$ is a length of words in the language iff $\ell + m$ is a length of words in the language, that is:

For all $\ell \geq n$: $(x \mid \ell \text{ or } y \mid \ell)$ iff $(x \mid \ell+m \text{ or } y \mid \ell+m)$.

Let $\ell \geq n$ be some multiple of $x$. Then $x \mid \ell$, hence either $x \mid \ell+m$ or $y \mid \ell+m$, which implies that $g \mid \ell$ and $g \mid \ell+m$, and so $g \mid m$.
Suppose that $x \nmid m$. Let $\ell \geq n$ be such that $\ell \equiv -m \pmod{x}$ and $\ell \equiv g \pmod{y}$; there exists such $\ell$ since $g \mid m$. Then $x\nmid \ell$, $y\nmid\ell$ (since $y > g$), but $x\mid \ell+m$, and we reach a contradiction. Therefore $x \mid m$. Similarly, $y \mid m$. Therefore $\operatorname{lcm}(x,y) \mid m$, implying that $n \geq m \geq \operatorname{lcm}(x,y)$ (since $m > 0$).
Conversely, it is easy to construct a DFA for the language with $\operatorname{lcm}(x,y)$ states, showing that this is the number of states in a minimal DFA, assuming that $x,y > g$.
If $x = g$ or $y = g$, then the language consists of all words whose lengths are a multiple of $g = \min(x,y)$, and so the minimal DFA contains $\min(x,y)$ states.
Finally, if we replace or with and in the definition, then we get the language of all words whose lengths are a multiple of $\operatorname{lcm}(x,y)$, whose minimal DFA contains $\operatorname{lcm}(x,y)$ states.


I would suggest that you use an integer linear programming (ILP) solver or a SAT solver.  This will probably be easier to formulate as ILP, so start there.

Let's check whether it is possible to ensure that no group ever gets teamed up with another group more than once.  (We'll ignore the bonus condition.)  Define a zero-or-one integer variable $x_{g,t,r}$, with the intent that $x_{g,t,r} = 1$ if group $g$ plays in team $t$ during round $r$, and $x_{g,t,r} = 0$ otherwise.  Now we can write some linear inequalities to capture the constraints on a valid solution:

$0 \le x_{g,t,r} \le 1$ ensures that each $x_{g,t,r}$ is zero or one.
$\sum_g x_{g,t,r} = 3$ ensures that exactly 3 groups are assigned to each team in each round.
$\sum_t x_{g,t,r} \le 1$ ensures that no group is assigned to more than one team in any given round.
Arbitrarily choose 36 groups to play 5 games; for those groups $g$, the linear equality $\sum_{t,r} x_{g,t,r} = 5$ ensures they will play 5 times.  The other 6 groups will play 6 games; for them, enforce the linear inequality $\sum_{t,r} x_{g,t,r} = 6$.
For each pair of groups $g,g'$, we enforce the linear inequality $x_{g,t,r} + x_{g',t,r} + x_{g,t',r'} + x_{g',t',r'} \le 3$ for all $t,r,t',r'$; this ensures that $g,g'$ never play together on the same team more than once.

Feed this system of inequalities to an ILP solver.  If it has a feasible solution, then you have found a valid schedule for your tournament.

If it has no feasible solution, next check whether there's a feasible tournament where no group ever gets teamed up with any other group more than twice.  Do this by replacing the last set of inequalities above with the following:

For each pair of groups $g,g'$, we enforce the linear inequality $x_{g,t,r} + x_{g',t,r} + x_{g,t',r'} + x_{g',t',r'} + x_{g,t'',r''} + x_{g',t'',r''} \le 5$ for all $t,r,t',r',t'',r''$; this ensures that $g,g'$ never play together on the same team more than twice.

If this doesn't have a feasible solution, check whether there's a way to do it where no group ever gets teamed up with any other group more than three times.  Do a linear search until you find the best solution.

Once you've found the best solution, now you can try to handle the bonus condition.  Let's say you want to see whether there's a way to do it where no group gets teamed up with another group more than once, and (here's the bonus condition:) no group has to wait more than three games.  The bonus condition is easy to enforce: for each $r$, simply add the linear inequality $\sum_t x_{g,t,r} + \sum_{t'} x_{g,t',r+1} + \sum_{t''} x_{g,t'',r+2} \ge 1$.  Now test whether that's feasible.  Of course, you can vary the waiting time (it doesn't have to be three games) to find the smallest waiting time possible.

I'd expect this might find a solution to your problem.  Modern ILP solvers are surprisingly good at solving many ILP instances, if there is sufficient structure -- and in this case I suspect there might be enough structure that off-the-shelf ILP solvers might work well.

There are variations possible to speed up the ILP solver, but I suspect that this straightforward formulation might just work with no tweaks or optimizations needed.  Give it a try!  It shouldn't be too hard to test out and see if it works.


Why ASCII letter A has a Hamming Distance of 3?

Tanenbaum is not saying that ASCII character "A" has a particular Hamming distance. Computerphile has a video that may clear things up.


Find dominated or subsumed linear inequalities efficiently

Unfortunately there is a nearly-quadratic-time lower bound that may prove a barrier.  In particular, you can't solve it in $O(N^{2-\varepsilon})$ time for any $\varepsilon>0$ unless the Strong Exponential Time Hypothesis is false.  In particular, the special case where all coefficients are 0 or 1 and the RHS is the same for all inequalities is equivalent to searching a bunch of sets for a pair that have a subset relationship, and that is hard: see https://cstheory.stackexchange.com/q/9896/5038.
The one saving grace is that this lower bound is for arbitrary sets, i.e., it does not take into account sparsity.  It is possible that you might be able to use sparsity somehow to do better than the general case.
Here is an algorithm that takes advantage of sparsity to do a bit better.  Suppose that every inequality has only $K$ nonzero coefficients.  Form a balanced binary tree on the $N$ inequalities.  Annotate each node with a map that maps $x_i$ to the max of all coefficients of $x_i$ in all inequalities under that node.  Now given an inequality $A$, you can check whether it dominates any other inequality by traversing the tree in a top-down breadthfirst fashion.  Any time you hit a node that maps $x_i$ to something smaller than $x_i$'s coefficient in $A$, there is no need to visit any of the children of that node, and traversal of that subtree can be skipped.  Heuristically, I expect you'll probably need to visit $O(KN/M)$ nodes of the tree on average (well, plus $O(\lg N)$ to account for the fact that each inequality dominates itself, but I'll ignore that as it seems likely to be small in comparison to the other terms).  Creating the tree takes $O(NK)$ time, and visiting each node takes $O(K)$ time, so I expect the overall running time per inequality will be something like $O(KN + K^2N/M)$, on average.  Since you have $N$ inequalities, the total time should be something like $O(KN + K^2N^2/M)$.  I don't know whether this is any better than what you already have in mind, though.


You should think of this as the class of problems who lie in $BPP$, but in a new (relativised) world where the model of computation is slightly different. Turing machines now have an additional query tape and three new special states, $q_{\text{query}},q_{\text{yes}},q_{\text{no}}$. Upon entering the state $q_\text{query}$, if the contents of the query tape is $s\in\Sigma^*$, then the machine goes to either the yes or no state depending on whether or not $s\in SAT$.

The key point is that nothing changes in the BPP part, the only thing different is the computational model. This actually changes everything, but luckily we can integrate the oracle to the standatd Turing machine without changing basic notions such as time/space complexity. This allows us to talk about classes such as $P, NP, BPP$ in the new model (we can define them in exactly the same way).

Note that we don't have a general definition of $A^B$ for two complexity classes $A, B$. We use this notation when $A$ has a natrual extension to the relativised (oracle) world.

Additionally, to define our model of computation precisely we need to specify exactly what is the oracle (we need to define the transition function from $q_{\text{query}})$. Thus, we can't have an algorithm solve every NP problem in a single step, we need to choose a problem in order to specify a well defined behavior for the machine. It is not hard to show that for every two NP complete languages $L,L'$ it holds that $\mathsf{BPP^L=BPP^{L'}}$. So when we write $BPP^{NP}$ we mean languages having a BPP machine with access to a SAT oracle (or any other NP complete language of your choosing). In cases where the definition of $A^B$ might depend on the exact choosing of the oracle, statements involving $A^B$ usually hide a universal quantifier on the oracle, and should be read as "for all $o\in B$ ...".


What is the advantage of Rete algorithm compared to relational database engines?

As you say, relational databases are designed for, essentially, answering queries. Rete, I would rather say, is designed for the specific task of materialized view maintenance (i.e., keeping updated the results of a query, once new changes to the data are applied). Of course, you can answer queries by building a materialized view of them, and this is why SQL query answering and Rete relates to each other.
With regards to efficiency, Rete has been critiziced for wasting too much time mantaining its internal data-structures. This motivated the apparison of other algorithms such as Treat.
In any case, it is worth to hightlight that Rete only deals with relational algebra queries, whereas SQL includes non relational-algebra expressions (e.g.: aggregation functions).


Simplest argument that language decidable in constant time cannot be $\mathsf{NP}$-hard?

Let $L \in P$ be non-trivial (not empty and not containing everything). If $L$ is NP-hard then $P=NP$. Indeed, given any language $L' \in NP$, by definition of NP-hardness there is a polytime reduction $f$ such that $x \in L'$ iff $f(x) \in L$. Since $L \in P$, this gives a polytime algorithm for $L'$, showing that $L' \in P$.

Conversely, if $P=NP$ then $L$ is NP-hard. Indeed, given $L' \in NP$, we can decide $L'$ in polynomial time using some algorithm $A$. Fix some yes instance and some no instance of $L$, and use $A$ to come up with a polytime reduction from $L'$ to $L$, which always returns one of the two fixed instances. This shows that $L$ is NP-hard.

Summarizing, if $L \in P$ is non-trivial then $L$ is NP-hard iff $P=NP$.


How does quicksort with 3-way partitioning ~ $(2 ln 2) NH$ become linear time complexity with many duplicated keys?

Basically yes and slightly no.

The purpose of the quoted paragraphs is to summarize the improvement of quicksort with 3-way partitioning over the basic quicksort (with Hoare partition scheme) in the case of many duplicated keys. The root cause of the improvement is simple, "every item encountered leads to an exchange except for those items with keys equal to the partitioning item’s key". The quantification of the improvement is given by that formula involving the Shannon entropy.

  How does $(2\ln2)NH$ become linear when there are many duplicated keys? So does it mean that I need to prove: $H$ is a constant (or should I say have a upper bound ?), and not related to $N$, when there are many duplicated keys.

I would turn the question around.

How can we define "many duplicated keys"? The book Algorithms chooses to mention this concept casually, probably in an attempt to make the situation sounds immediately familiar to the widest audience at the expense of some rigor.

In fact, the more applicable and rigorous concept should be "stable discrete distributions", i.e., the distribution of all discrete key values stays roughly the same, which is somewhat more technical but still within reach of most of targeted audience of that book. Note that entropy of a multi-set is determined by the frequencies of all values appearing in the multi-set, as explained in the last paragraph quoted in the question. If the distribution of all key values stays the same, the entropy of a sample array viewed as a multi-set will be roughly the same regardless of the sample size. When sample size goes larger and larger, there will be more and more duplicate keys in the sense of the sum of duplicities. For example, if the probability of some key $k$ is 0.2, then there is likely about 20 items with key $k$ when the sample size is 100 and there is likely about 200 items with key $k$ when the sample size is 1000. That is the meaning of "many duplicate keys" here.

In other words, we could simply define "many duplicated keys" by "the same entropy regardless of the size $N$". Then there is, actually, nothing for you to prove once you have agreed that "Quicksort with 3-way partitioning uses $\sim(2\ln2)NH$".

Or, we could try to prove the following more precise proposition.

  It will take quicksort with 3-way partitioning approximately $(2\ln2)NH$ time on average to sort an array of size $N$ that comes from sampling a discrete distribution with entropy $H$, where $H$ is a constant and $N$ goes to infinity.

The following excerpt of the book implies the explanation above implicitly. The boldface is added by me.

  As with standard quicksort, the running time tends to the average as the array size grows, and large deviations from the average are extremely unlikely, so that you can depend on 3-way quicksort’s running time to be proportional to N times the entropy of the distribution of input key values. This property of the algorithm is important in practice because it reduces the time of the sort from linearithmic to linear for arrays with large numbers of duplicate keys. The order of the keys is immaterial, because the algorithm shuffles them to protect against the worst case. The distribution of keys defines the entropy and no compare-based algorithm can use fewer compares than defined by the entropy. This ability to adapt to duplicates in the input makes 3-way quicksort the algorithm of choice for a library sort—clients that sort arrays containing large numbers of duplicate keys are not unusual.

My explanation above suffers the same weakness of ambiguity as the book, although on a slightly different level, since I would also like my explanation to be understood by widest audience easily with least amount of expense of rigor. Hopefully, I have made the point clearly enough so that readers should be comfortable enough to believe he/she has understood the relevant idea in the book.

Assume the Proposition N of the book, which is the first paragraph of this question.

Exercise. Given a constant positive integer $m$, it will take quicksort with 3-way partitioning approximately less than $2N\ln2\log_2m$ time to sort an array of size $N$ whose number of distinct elements is $m$. (Hint, maximum entropy with $m$ possible values is obtained with uniform distribution.)


That's right. You can run all machines in parallel and you'll find shorter and shorter descriptions, but at some point there will always be a shorter program still running, for which you can't prove that it won't halt with $x$ as output.

The probability you describe (of a program not halting, assuming some distribution on inputs) is the complement to Chaitin's omega: the probability that a program will halt. Of course, Chaiting's omega is also not computable and the best way we have of approximating it, is just by running all programs in parallel and summing the probabilities for the ones we've seen halting.

If you start with a probability distribution on outputs, the probabilities have different bounds. If you take a uniform distribution on strings of length $n$, then as $n \rightarrow \infty$, the proportion of strings compressible by more than a few bits is negligible, ie. $K(x) \approx |x|$ with near certainty for large $n$. If you take the universal distribution, then every computable pattern will appear in your string with some probability.


No, your reasoning is not correct, but I think you are very close to a correct answer.

A Turing machine in 2000 steps can only read the first 2000 symbols in the input tape, but is not forced to reject a longer input. In fact, it can accept it. So, the TM can process longer inputs, but its behavior is determined by the first 2000 symbols on the tape.

If $x$ and $y$ are words which are identical on their first 2000 symbols, then they are both accepted/rejected/neither in 2000 steps.

Because of this, we can partition the possible inputs according to their first 2000 symbols. For each of the finitely many partitions, we can extract any element and test for that one, only.

So, our decision procedure is the one given by the OP. The argument for correctness is a bit different, though.


As there is a loop over $F(n-8)$, so we will have 256 times $F(n-8)$. Hence, time complexity would be:
$$T(n) = 256\times T(n-8) = 256\times(256\times T(n-16)) = \Theta(256^\frac{n}{8})$$.

As mentioned in comment $256 = 2^8$, we will have $T(n) = \Theta(2^n)$.


Turing machine that checks whether a given string is an output of a given machine and input

No, in fact any non-trivial semantic property of Turing machines is undecidable. This result is Rice's theorem.


Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free?

If I'm not mistaken, you can pump $\bar L$ using $\sigma = a^{n}b^{n^{2}}$, because $n \mod n^{2} = 0$. The result is that $\bar L$ is not context free. The property that you mentioned has an "iff", then $L$ is not context free.


Words which, cyclically shifted twice, equal their reverse

Let us see which words satisfy $C_2(w) = w^R$. Write $w = \sigma \tau x$, where $\sigma,\tau \in \Sigma$ and $x \in \Sigma^*$. Then $C_2(w) = x \sigma \tau$ and $w^R = x^R \tau \sigma$, and so $C_2(w) = w^R$ iff $x = x^R$ and $\sigma = \tau$.
You should be able to use this information in order to construct a grammar for your language.


How big is the class of problems that can be analysed to halt with static analysis. Is this class sufficient for any practical purposes?

When you hear about "static analysis" in the context of programming languages, you will often have the three results "passes the test", "doesn't pass the test", "is rejected". In that context, the analysis is supposed to help the software developer. If the developer writes code that is too hard to analyse, that's the developer's problem because he isn't going to get the answer he wants.

As an example, the Java language insists that a variable must be assigned a value before it is accessed. Testing that in general would require solving the halting problem. However, the Java language defines a precise method how it would go about verifying this property, and if your program cannot be analysed by this method, then it is rejected. No attempt at solving the halting problem is made.


Let P(M,q,w) = "the computation of M on w visit q"

If we suppose P décidable, then the problem P' defined as :

P'(M,w) = w \in L(M)

is decidable.

Proof :
This a decision procedure for P'. Let M be a machine and w a word.
For each accepting state q of M, we run P(M,q,w).  If the answer
 is "yes" for some q, we return "yes". Otherwise, we return "no".

Since it is well known that P' isn't decidable (Rice theorem), we conclude P isn't decidable.


Bucket Priority Queues with large integers for $O(1)$ insert and extract~min?

Your proposed data structure is simply a hash table with some rounding to reduce the number of buckets. Effectively, all this does is divide the problem complexity by some constant factor (128 in your example).

You have no hierarchy in your design, so there is no way to have O(1) access to the smallest/largest non-empty bucket. To achieve this feature efficiently, you're already pretty much bound to some type of priority queue. This class of data structures is well studied, and has various implementations with typically very low bounds on complexity.


What is the connection between the logic and the logic programming?

First, all this "worlds" stuff is unnecessary. It's a notion used in some semantics of modal logic. You don't need it to understand modal logic, let alone non-modal logics. This isn't to say it can't be useful, it's just that "worlds" is not some fundamental constituent of logic or their semantics, and, regardless, is not typically used outside of modal logics. As common logic programming languages (i.e. Prolog) are not based on modal logic, there's not much reason to bring it up nor concepts sometimes used in its semantics. You can have modalities in a logic programming language, e.g. LolliMon does. The notion of worlds doesn't really map well onto variable assignments. The problem, among other things, is that you can want multiple different assignments to the same variable at the same time.

Sticking to (pure1) Prolog, due to the restrictions on where you can place connectives, it turns out that it can be understood as operating in a logic with no connectives. Let's consider a fairly general example of a Prolog rule:

p(X,Y) :- q(X,Z), r(W); t(Y).

This corresponds to the logical formula: $$\forall X,Y.(t(Y)\lor(\exists Z.q(X,Z)\land r(W)))\to p(X,Y)$$

First, we can eliminate the universal quantifiers and simplify things by considering entailments between open terms where the free variables will behave like constants. This more or less corresponds to $\forall$ introduction. So $\vdash \forall x.\varphi(x)$ becomes just $\vdash\varphi(x)$. Our example becomes:
$$\vdash (t(Y)\lor(\exists Z.q(X,Z)\land r(W)))\to p(X,Y)$$
We can use the $\to$ introduction (aka the deduction theorem) to eliminate the sole occurrence of $\to$ in any particular rule producing for our example:
$$(t(Y)\lor(\exists Z.q(X,Z)\land r(W)))\vdash p(X,Y)$$
We can use the $\lor$ left rule of the sequent calculus LK/LJ to handle the disjunction. Alternatively we could have used the equivalence $(P\lor Q)\to R\equiv (P\to R)\land(Q\to R)$ before eliminating $\to$ and then used $\land$ introduction, then eliminate $\to$ to produce the same result. We could also eliminate disjunctions (';') via a standard source-to-source transformation of the Prolog that is based on these rules. Our example becomes a pair of entailments:
$$t(Y)\vdash p(X,Y)\qquad \exists Z.q(X,Z)\land r(W)\vdash p(X,Y)$$
We can eliminate the existential with a $\exists$ left rule a la LK/LJ which is basically the dual of $\forall$ introduction and works the same way. That is, we just drop the existentials and the bound variables become free and are treated as constants. Alternatively, this could be understood in terms of the equivalence $(\exists x.\varphi(x))\to\psi\equiv\forall x.\varphi(x)\to\psi$. The relevant entailment of our example becomes:
$$q(X,Z)\land r(W)\vdash p(X,Y)$$
Finally, we can use the $\land$ left rule to eliminate conjunctions, producing:
$$q(X,Z),r(W)\vdash p(X,Y)$$
For an arbitrary (pure) Prolog program, the end result is that we have a collection of rules with a list of premises which consist of atomic formulas entailing a single atomic formula. All connectives can be eliminated. If you don't like this, you can easily go from here to the program corresponding to a series of axioms of the form $\forall\vec{X}.(p_1(\vec{X})\land\cdots\land p_n(\vec{X}))\to q(\vec{X})$, which are Horn clauses, or curry this to get rid of $\land$ producing $\forall\vec{X}.p_1(\vec{X})\to(\cdots(p_n(\vec{X})\to q(\vec{X})\cdots)$. This would mean you only need to understand universal quantification and implication, but even then neither ever occurs in a negative position, so you don't need their full generality which is part of why they can be eliminated. If you want to inject classical logic unnecessarily, you can use material implication and write $\forall\vec{X}.\neg p_1(\vec{X})\lor\cdots\lor\neg p_n(\vec X)\lor q(\vec X)$, and, instead of Cut below, we'd talk about Resolution.

Sticking to the connective-free version, how do we actually prove things? Well, we still have the structural rules. In particular, we have Cut which states (for our purposes):
$$\dfrac{\Gamma\vdash P\qquad\Delta,P\vdash Q}{\Gamma,\Delta\vdash Q}$$
where $P$ and $Q$ are atomic formulas and $\Gamma$ and $\Delta$ are lists of atomic formulas. Cut corresponds to calling a subgoal.

For the top-level call that kicks off the execution of a Prolog program, we aren't trying to show whether the universal closure of the top-level goal is true, but rather listing all the bindings to free variables that makes the goal derivable. This can be seen as enumerating the derivations of $\vdash\exists\vec X.q(\vec X)$ if $q(\vec X)$ is the top-level goal.

For the connection to execution, I recommend getting familiar with the concept of an abstract logic programming language as defined in Uniform Proofs as a Foundation for Logic Programming. This shows how we can interpret connectives as instructions to proof search. By constraining the logic, we can make it so this operational interpretation of the connectives (and atomic formulas), can give a complete proof search procedure (for our highly restricted logic). The elimination of connectives that I've done shows that for Prolog (but not $\lambda$Prolog), the only operational interpretation we need is that of atomic formulas. Non-determinism arises from choosing which rule to use to derive the atomic formula and how to instantiate its free variables. Implementation-wise, the former is usually handled by backtracking and the latter by unification.

If you recorded the steps of the execution of a (pure) Prolog program, the result would be a derivation, i.e. a formal proof. There is no "satisfaction" involved. A Prolog program like p :- q, r does not try assigning different truth values to q and r. There's no way to express a contradiction in (pure) Prolog, so every (pure) Prolog program corresponds to a satisfiable formula.

Datalog is usually analyzed with a more semantic approach, but it has additional restrictions over (pure) Prolog to make this well behaved. Datalog is often implemented in a bottom-up manner where we generate a series of single-step deductions and grow the set of derived facts until we reach a fixed point. Prolog, however, is almost always implemented in a top-down manner where we backchain so that we only derive the facts that are relevant for our goal.

1 This excludes this like assert/retract, cut (!), and the negation-as-failure thing.


Why is it important to solve a problem in Polynomial time, In cryptography?

The concept of polynomial time is a theoretical concept that is supposed to capture what kinds of problems are possible to solve "in practice". In practical cryptography, the goal one is interested in is that no government body can break the system in less than a 100 years (say). However, this concept is hard to reason about, for many reasons. One reason is that the set of problems that can be solved in a 100 years depend on your hardware, budget, and so on. Moreover, even given a specific algorithm for a problem, it is hard to estimate how much time exactly it will require to run. To circumvent these difficulties, cryptography theory suggests the following idea:

  Consider a cryptosystem which depends on a parameter $n$ tending to infinity. Analyze the security of the cryptosystem in terms of the asymptotic complexity of breaking it.

The asymptotic complexity doesn't depend too much on the exact hardware (as long as it's not a quantum computer); if next year a new CPU is revealed running 10 times as fast, a system that requires $O(2^n)$ time for breaking will still require $O(2^n)$ time for breaking. Moreover, we make the following assumption:

  An algorithm runs "fast" if it runs in polynomial time (in $n$).

Polynomial time is a natural class for many reasons, the reason here being that it is the smallest class which is closed under function composition and contains superlinear functions. Putting both ideas together, we get:

  A cryptosystem depending on a parameter $n$ is secure if it cannot be broken in time polynomial in $n$.

Here $n$ should be a reasonable parameter. One way of enforcing it is to require the encryption procedure to run in polynomial time in $n$.

This definition has led to a beautiful theory of theoretical cryptography. However, in practice polynomial time is not such a good notion, especially in cryptography, for two reasons:

Polynomial time could be very slow in practical. For example, an encryption procedure running in time $O(n^{10})$ or $10^{10} n$ is not practical.
Super-polynomial time could be practical, depending on the value of $n$. For example, $2^{n/2}$ is very practical for $n = 64$.

In applied cryptography, therefore, one tries to give running time estimates for a particular system (a particular setting of $n$) which is not asymptotic. Usually one calculates the number of "basic operations", a concept which is not defined precisely but is a better proxy than asymptotic complexity. When possible, actual simulations are run to show that the cryptosystem can be broken with weakened parameters, and to extrapolate the time it takes to break the full cryptosystem.

One problem with this approach is that it is going to be very difficult to prove that a system is secure. While this is true even for theoretical cryptography (we cannot prove the security of any cryptosystem), here it is seems that the best one can do is try to break the system and fail; proving a meaningful lower bound is probably too much to ask for.

One way to circumvent this difficulty in some situations is to use oracle (or black box) models. Suppose that a cryptosystem relies on some cryptographic primitive which we trust. We can imagine replacing this primitive by an idealized component. In this case, sometimes lower bounds on the number of queries to the black box can be proved. This allows us to gauge the security of the model, making the implicit assumption that the algorithm implementing the black box is completely opaque.

This is the approach taken by theoretical cryptography – assuming the existence of some secure cryptographic primitive (which we can't prove at the moment), it constructs cryptosystems and proves their security. However, this doesn't necessarily have practical implications, since in reality the parameter $n$ is fixed rather than tending to infinity. Even in cases in which we can rigorously prove that some cryptosystem requires $T(n)$ time to break (given some assumptions on the cryptographic primitives), usually the guarantees are very weak, and in order to get reasonably large $T(n)$, an impractically large $n$ is required.

For more information, check this classic paper on concrete security and this notorious article debunking theoretical cryptography.


It's trivial to do in O (n), using the obvious formula $F_{i+1} = 2F_i - F_{i-k}$. Just write down the definition of $F_{i+1}$ and note that it is mostly (but not quite) the same as the definition of $F_i$.


How to find the element of the Digit Sum sequence efficiently?

Since you asked for " a new direction or a hint " and I don't know the answer, I'll leave this here, I hope it's helpful.
some ideas:

It makes sense there would be a pattern mod 9, since

$\forall k > 1,k \in \mathbb{Z}\quad10^k \equiv 1 \mod 9$

Which you can prove by induction.

This means that all numbers are congruent to the sum of their digits mod 9.

Further,
$a_n = d(a_n) \mod 9 \implies $
$$a_{n} = a_{n-1} + d(a_{n-1}) = 2d(a_{n-1}) \mod 9$$

If we keep expanding this recurrence we get

$a_{n} = 2^n \mod 9$

Which explains the pattern mod 9.

It also gets us $a_n = 9k + 2^n$. Every iteration we get a gap that is divisible by 9. How wide are those gaps?

Here's some less than general code:

import matplotlib.pyplot as plt
import numpy as np

#sum digits of n
def sum_digits(n):
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

#get the sequence to n digits
def calculate(n):
    retval = [1]
    for i in range(n):
        retval.append(retval[-1] + sum_digits(retval[-1]))
    return retval;

#empirically confirm that a_n = 2^n mod 9
def confirmPow2(a):
    count = 0
    for i in a[:10000]:
        if((i%9) != (2**count % 9)):
            print "false"
        count = count + 1

#find gaps divisible by 9 in a subset of a
def find9Gaps(a):
    count = 0
    S = []
    for i in a[:10000]:
         S.append(((2**count ) - i)/9)
         count = count + 1
    return S

#repeatedly sum the digits until they're less than 9...
#gives some interesting patterns
def repeatedDigitSum():
    for i in range(1000, 1100):
         print "=========for ",i
         while i > 9:
                 i = sum_digits(i)
                 print i

a = calculate(10**6)
b = find9Gaps(a)
plt.plot(range(len(b[:100])), b[:100])
plt.show()

The plot (for the first 100) looks exponential, but I don't think it's perfect.

Here's the output of

>>> plt.plot(range(len(b[5:60])), np.log2(np.array(b[5:60])))
>>> plt.show()

The last thing I have is that it seems if you sum the digits of a number, and then sum the digits of the resulting number, and repeat this, you eventually get that number mod 9.

Makes sense given the above fact about powers of 10 mod 9.

$$n \equiv d(n) \equiv d(d(n)) \equiv \cdots \mod 9$$

It gives an interesting sequence of numbers though.

Edit: Apparently this is called a "digital root".


What characterises vertices at fixed indices in all topological orderings?

Theorem: A given vertex $v$ always comes first, $i = 1$, iff it has no incoming edges and every other vertex has at least one incoming edge.

Right-to-left implication: no vertex other than $v$ can come first, since they all have incoming edges.

Left-to-right: for $v$ to come first it has to have in-degree 0.  If some vertex $w$ has in-degree 0 with $w \neq v$ and there's a topological ordering where $w$ has a left neighbour $u$, then swapping $w$ and $u$ yields another topological ordering: the only vertices which have new relative positions are $u$ and $w$, and since $w$ has in-degree 0 no constraint is violated by putting it before $u$.

Repeatedly move the leftmost such $w$ one step to the left; this will end when one such $w$ comes first, contradicting the assumption that $v$ always comes first.  Hence no $w$ exists.

QED

By a symmetric argument, a vertex always comes last if it alone has out-degree 0.

Theorem: $v$ is fixed-index iff it is comparable to every other vertex (i.e. for all $w$, either $w = v$ or there is a path from $v$ to $w$ or there is a path from $w$ to $v$).

Right-to-left: compare $v$ to all other vertices. All $w$ with a path to $v$ must come before $v$ and all $u$ with a path from $v$ to $u$ must come after $v$.  That leaves only one index at which $v$ can occur.

Left-to-right: assume for the sake of contradiction that there exists some $w$ to the left of $v = v_j$ in some topological ordering, where $w$ is incomparable to $v$, i.e. there is neither a path from $v$ to $w$ nor from $w$ to $v$.  Let $u = v_i$ be the rightmost among those, $i < j$.

Consider $t = v_{i+1}$.  By $u$ being the rightmost incomparable vertex left of $v$, either $t = v$ or $t < v$.  If $u$ were comparable to $t$ then $u$ would also be comparable to $v$ (by transitivity through $t$) so it isn't.  Hence we can swap $u$ and $t$ and remain topologically ordered.  Continue doing this until $u$ and $v$ get swapped, contradicting $v$ being fixed-index.

Similarly derive a contradiction from the existence of an incomparable vertex to the right of $v$.  Hence there is no incomparable vertex.

QED

Some consequences:

Let a digraph $G$ be Weakly Connected if the undirected counterpart is connected; define Weakly Connected Components analogously.

Any interleaving of the topological orderings of two weakly connected components is a topological ordering of their union.  In particular, one can put the entire ordering of one component immediately before or after a given vertex in the other component, so no vertex can be fixed-index (so long as both components are non-empty).

Corollary: a DAG with a fixed-index vertex is weakly connected.

A more direct and constructive proof: $path(s, v) + path(v, t) = path(s, t)$ where the precise definition of $path$ and $+$ is left as an exercise ;-)

There is no implication in the other direction: consider the complete bipartite graph on 2+2 vertices, edges left-to right, with $a, b$ on the left and $c, d$ on the right; then $a$ and $b$ come before $c$ and $d$, but $a$ and $b$ can always be swapped, and so can $c$ and $d$.  This graph is weakly connected but has no fixed-index vertex.

It is also not the case that all paths from $v_i$ to $v_k$ go through $v = v_j$ when $i < j < k$.  For (counter)example, $V = \{a, b, c\}$ and $E = \{(a, b), (a, c), (b, c)\}$ which has only one topological ordering. Let $(v_i, v, v_k) = (a, b, c)$; then there is a path of length 1 from $a$ to $c$ which doesn't go through $b$.


Which unit (control unite or logic unit) issue instructions of load/store?

You definitely cannot associate a part of the architecture with an instruction class.

All instructions are concerned by the control unit as it fetches instructions and decode them.
Control instruction mostly concern the controller, but some computations may be done by the ALU. For instance, in branches, addresses are generally given by adding an offset to the program counter and that requires an adder that may be in the ALU. It is the same if a branch instruction has to perform a comparison to decide if branch must be taken or not.
once decoded, arithmetic/logic or data transfer instructions mostly concern the ALU part.

By the schematic that you gave (and my explanations) were true 40 years ago. Modern computers are much more complex. Control is somehow decentralized to allow execution of several concurrent instructions, instruction reordering, branch prediction, register renaming, etc. And the ALU is no longer a monolithic bloc but formed of several functional units dealing with specific computation, memory access, etc. You can find here the microarchitecture of a recent pentium (broadwell) and it is difficult to really identify the two units in your schematic.

So even more than in your question, it is impossible to associate an hardware unit with an instruction type.


Can you give me a hint on how to prove this?

Let $H$ be a class of all functions which map universe $Z_n$ to $Z_m$. We will assume that, any particular mapping is done by exactly one of the functions in the class.
Total functions in $H$  = number of all possible mappings = $m^n$
Given any distinct keys $x$ and $y$, we need to find number of all possible functions (mappings) in which they collide. The remaining $n-2$ keys have total mappings: $m^{n-2}$. The $(x,y)$ pair can collide by mapping to any of the $m$ slots. So,
Total functions in $H$ where $(x,y)$ collide = $m^{n-2}\cdot m = m^{n-1}$
Thus probability of collision = $m^{n-1} / m^n = 1/m$.


From your question it is unclear what $x$, $y$ and $z$ are. However, the two formulas are equivalent. Let me use products to denote a logical "AND" and additions to denote a logical "OR" so that your first formula becomes $xy + xz  + yz$

If you gather $z$ in the last two terms you get:
$xy + (x+y)z$.

Notice how the second term $(x+y)z$ is true iff $z$ is true, and at least one of $x$ and $y$ is true. However, if both $x$ and $y$ are true, the whole formula is true regardless of the truth value of the second term (since the first term is $xy$).
You can then replace $(x+y)$ with $(x \oplus x)$ (where "$\oplus$" denotes the exclusive OR) to obtain:
$xy + (x \oplus y)z$ or, equivalently, $xy + (x'y + xy')z$.


Let us first calculate the coordinates $C(m,n)$ of the center of hexagon $(m,n)$. We assume that the origin is at the center of hexagon $(0,0)$ and that the hexagon radius (distance from center to vertex) is $r$.  A short calculation shows that hexagon $(1,0)$ has its center at $$C(1,0) = a = (\sqrt{3} r, 0)$$ and hexagon $(0,1)$ has its center at $$C(0,1) = b = (\sqrt{3} r/2, 3 r/2).$$
Therefore, hexagon $(m,n)$ has its center at
$$C(m,n) = m \cdot a + n \cdot b = (\sqrt{3} r (m + n/2), 3 r n / 2).$$
Notice that we should allow negative $m$ and $n$ if we want to cover the whole plane.

To get from the center $C(m,n)$ to one of the adjacent centers we need to add to $C(m,n)$ one of the vectors $a$, $b$, $-a$, $-b$, $a - b$, or $b - a$. (If we add $a + b$ or $-a-b$ we go too far). If we travel half the distance we will end up exactly in the midpoint of a side. Therefore, midpoints of sides have coordinates of the form
$$C(m+1/2, n), C(m,n+1/2), C(m-1/2,n), C(m,n-1/2), C(m+1/2,n-1/2), C(m-1/2,n+1/2).$$
We have discovered how to encode sides: just use half-integer coordinates. But this is silly, it is better to multiply everything by two, which leads to the following system.

We represent both hexagons and sides as pairs of integers $(m,n)$. When $m$ and $n$ are both even this encodes a hexagon whose center is at $$C(m/2,n/2) = (m \cdot a + n \cdot b)/2.$$
If either $m$ or $n$ is odd then $(m,n)$ represents a side of a hexagon whose midpoint is at $C(m/,n/2)$.

It is also easy to tell which two hexagons a given side belongs to: the side $(2 i + 1, 2 j)$ belongs to hexagons $(2 i, 2 j)$ and the side $(2 i + 2, 2 j)$, while the side $(2 i, 2 j + 1)$ belongs to hexagons $(2 i, 2 j)$ and $(2 i, 2 j + 2)$.

Similarly, the sides of hexagon $(2 i, 2 j)$ are: $(2 i + 1, 2 j)$, $(2 i - 1, 2 j)$, $(2 i, 2  j + 1)$, $(2 i, 2 j - 1)$, $(2 i + 1, 2 j - 1)$ and $(2 i - 1, 2 j + 1)$.

We now have a good system for representing hexagons and sides as pairs of integers. We still need to solve the original problem, namely which blue hexagons are reachable from a starting hexagon by traveling along certain "black" paths. This is a graph-theoretic reachability problem if we think of sides as edges in a graph and their endpoints as vertices of a graph (as we reach each black side we verify whether it belongs to a blue hexagon). Many algorithms are known on how to solve this. Let me know if you need more details.


Digraph vertices: classification by counting outgoing walks

Let $A$ be the adjacency matrix of the graph, let $\mathbf 1$ be the all-ones vector, and let $\delta_v$ be the indicator of vertex $v$. Then
$$
W_v(t) = \delta_v A^t \mathbf 1.
$$
It follows that $v \sim u$ iff for all $t$,
$$
(\delta_u - \delta_v) A^t \mathbf 1 = 0.
$$
Let $n = |V|$. The Cayley–Hamilton theorem shows $A^t$ is always a linear combination of $A^0,\ldots,A^{n-1}$. Therefore
$$
v \sim u \Longleftrightarrow (\delta_u - \delta_v) A^0 \mathbf{1} = \cdots = (\delta_u - \delta_v) A^{n-1} \mathbf{1} = 0.
$$
The latter property can be checked in polynomial time, so the partition can be computed in polynomial time. This procedure can be optimized by computing the kernel of the matrix
$$
\begin{bmatrix}
A^0 \mathbf{1} \\
\cdots \\
A^{n-1} \mathbf{1}
\end{bmatrix}
$$
and then finding all $\delta_u-\delta_v$ that belong to it.


Inductive proof for the Bubblesort algorithm

What is a Proof of Correctness:
Algorithms are identified with pre-conditions and post-conditions. The pre-conditions are assumptions you make about the algorithm's inputs. Post-conditions describe what we want the algorithm to have accomplished once it terminates.
For an algorithm to be considered "partially correct", whenever the pre-conditions hold, the post-conditions must follow. For it to be considered "totally correct", it must be partially correct and halt, i.e. take a finite number of steps.
Pre and post-conditions are something one specifies about an algorithm, not something one proves about it. A typical precondition for a sorting algorithm might be "A[1...n] is an array of integers". A typical postcondition might be "A[1...n] is a sorted array of integers with the same values it had before the algorithm was executed".
That's a lot of formalism to get out of the way before we even talk about the problem, but it's important to be rigorous.
Showing Bubblesort is correct
To show Bubblesort is correct, we should show that the post-conditions follow assuming the pre-conditions hold. Total correctness will follow since Bubblesort trivially halts.
Loop Invariants
This is something you see everywhere in proofs of correctness that have loops. Instead of talking about the whole algorithm "at once", it's useful to come up with something that will be true for each iteration of the loop. This often lends itself to an inductive argument. The loop invariant you want to come up with is something that will help you conclude what you want to conclude at the end of the day - that A[1...n] is sorted once we terminate.
Here's what I came up with to that end. For any iteration $i$ of the outer loop: For any $a \in \{1,...,n\}$:
If there is a $b \in \{1,...,n\}$ such that $a>b$ but $A[a]<A[b]$ at the start of the iteration, then at some point in the inner loop, $A[a]$ and $A[a-1]$ will swap. Similarly, if there is a $b>a$ such that $A[a]>A[b]$, then $A[b]$ and $A[b+1]$ will have swap at some point in the inner loop.
Else, $A[a]$ won't change.
To prove this, it would be helpful to first show that whenever an $a$ satisfies the conditions in the "If" part, $a \leq i$ is true. This lemma could use an inductive argument. By the way this is one (possible clunky) way of coming up with the invariants, you might have a more concise way of phrasing what you need. I haven't written the full proof so I might have inefficiencies up there.
Wrapping Up
Once you show the loop invariants above are true, we can use them to conclude that $A[1..n]$ comes out the other end a sorted list of integers. Let $A[1..n]$ refer to the original list, and $A'[1...n]$ refer to the modified list. Let $a \in \{1,...,n\}$ be arbitrary, and let $c \in \{1,...,n\}$ be a correct sorted index of $A[a]$ in $A[1..n]$, i.e. $c$ is the index $A[a]$ should be at in a sorted version of $A$. We want to show that $A'[c]=A[a]$.
If $a$ was already in it's correct position in $A[1..n]$ (i.e. $a=c$) then we're done, because this means for any $b < a$, $A[b]<A[a]$, thus the swap condition in the inner loop will never be satisfied, meaning $A'[a]=A[a]$. Otherwise, either there exists some $b<a$ such that $A[b] > A[a]$, or some $b>a$ such that $A[b]<A[a]$. In either case, the loop invariants tell us that $A[a]$ will move at least one step in the correct direction after each outer-loop iteration. The maximum distance between $a$ and $c$ is $n-1$, and since the "Else" of the loop invariant essentially tells us that $A[a]$ will stop moving when $a=c$, we can say that $A[a]$ will get to index $c$ and stop, so $A'[c]=A[a]$ as required.
That's the gist of it, I left out the proofs of the invariants, and there might be other gaps in my response. Hopefully you can fill those in. Sorry for the long answer.


Maximize entrywise 1-norm of matrix product

Here's one approach, where we prune the set of candidates we examine based on the best combination seen so far.  I don't know how well it will work; you'll probably have to implement and try it to find out.

Suppose we have two sets $S_1,S_2$ of matrices, and we want to find $M_1 \in S_1, M_2 \in S_2$ that maximizes $\|M_1 \times M_2\|_1$.  Here's a plausible  approach.  First, sort the matrices in each set by decreasing value of $\|\cdot\|_1$ norm.  At each stage, we'll keep track of the largest value of $\|M_1 \times M_2\|_1$; let $\ell$ denote that largest-seen-so-far value.  We'll exploit the inequality

$$\|M_1 \times M_2\|_1 \le \|M_1\|_1 \times \|M_2\|_1$$

to prune the set of combinations we need to test.  In particular, we'll enumerate matrices $M_1 \in S_1$ in order of decreasing $\|\cdot\|_1$ value.  For a fixed $M_1$, only need to examine matrices $M_2 \in S_2$ such that $\|M_2\|_1 > \ell/\|M_1\|_1$ (thanks to the above inequality, there's no point in examining the other candidates for $M_2$).  For each candidate pair, we'll compute the value of $\|M_1 \times M_2\|_1$ and update $\ell$ if it is larger than any seen so far.

In this way, we obtain the following algorithm:

Set $\ell := -\infty$.
For each $M_1 \in S_1$, in decreasing order of $\|\cdot\|_1$ norm:

For each $M_2 \in S_2$, in decreasing order of $\|\cdot\|_1$ norm:

If $\|M_2\|_1 \le \ell/\|M_1\|_1$, break out of the inner loop and go on to the next iteration of the outer loop.
Otherwise, if $\|M_1 \times M_2\|_1 > \ell$, set $\ell := \|M_1 \times M_2\|_1$.

What's the running time of this approach, if $S_1$ and $S_2$ are each of size $n$? I don't know.  At worst, it is $O(n^2)$, but one could hope that it might be significantly better -- if we're very lucky, it'll be more likely $O(n \log n)$ (to sort the two sets).

How do we apply this to your problem?  Naively, we can set

$$\begin{align*}
S_1 &= \{M_1 \times M_2 \times M_3 \times M_4 : M_i \in E_i\}\\
S_2 &= \{M_5\times M_6 \times M_7 \times M_8 : M_i \in E_i\}
\end{align*}$$

and then apply the above algorithm.  Here $|S_1|=|S_2|=2^{32}$, so if we're very lucky, this might be efficient enough to apply to your situation.

With a bit more sophistication and implementation complexity, you might be able to apply this recursively.  The above procedure gives a way to enumerate products $M_1 \times M_2$ in decreasing order of $\|M_1 \times M_2\|_1$, given a set of candidates for $M_1,M_2$.  So, you could apply that to $E_1 \times E_2$ and $E_3 \times E_4$ to find $S-1 = E_1 \times E_2 \times E_3 \times E_4$, etc.  You could also use some kind of iterative deepening, to only enumerate combinations such that the norm of their product exceeds some lower bound, and gradually decrease the lower bound as needed.


Why do min/max operations in van Emde Boas trees run in $\mathcal{O}(1)$?

No. They are not given as an input! They were stored and updated as an attribute of each tree(Beware that the concept of the "attribute" in real-world programming means a "variable" in a programming language. More details depend on the programming language that you have chosen up to now to develop the data structure). The same situation is taking place in the min[Max]-heap data structure. You can find the minimum [maximum] in a min[max]-heap with $O(1)$ operation by keeping update (in insertion time) the mentioned attribute.


Use the pumping lemma to show it's not regular

Suppose that $B$ were regular. According to the pumping lemma, there exists an integer $p \geq 1$ such that every word $w \in B$ of length at least $p$ has a decomposition $w = xyz$, with $|xy| \leq p$ and $y \neq \epsilon$, such that $xy^tz \in B$ for all $t \geq 0$.

Pick some Fibonacci number $F_n$ such that (1) $F_n \geq p$ and (2) $F_{n+1} - F_n > p$. Then $1^{F_n} \in B$ has length at least $p$, and so it can be decomposed as $1^{F_n} = xyz$, where $|xy| \leq p$ and $y \neq \epsilon$, and $xy^2z \in B$. But $xy^2z = 1^m$, where $F_n < m \leq F_n + p < F_{n+1}$.


Your problem is in NP.  (A certificate for a "yes" answer is to list one of the $k$-cliques that each edge is contained in.)  Therefore, it's not likely to be PSPACE-complete: if it were PSPACE-complete, that would imply NP = PSPACE, which would be surprising.

Your problem is NP-complete.  It is at least as hard as the $k$-clique problem. Suppose we have a graph and we want to know whether it contains a $k$-clique.  Then we can color all edges green, let $\alpha$ be the empty list, and let $\epsilon$ be the list containing only the color green.  Now the graph has a $k$-clique if and only if the answer to your problem is yes.  But testing for a $k$-clique is NP-complete, so it follows that your problem is NP-complete too.


This is likely to be a challenging task, and if you're not familiar with image classification, I suspect it may be beyond what you can reasonably do right now.
I would suggest you investigate classical image processing techniques.  You might try applying morphological operators, such as closing (dilation followed by erosion) or opening followed by thresholding.  You may need to experiment.  If you search on Stack Overflow and Signal Processing sites, you'll find many examples.
See also blob detection and watershed segmentation.


In SAT, do we require an assignment for arbitrary variables?

If the truth value of a formula is determined by setting only a subset of the variables, an author might skip describing the remaining truth values. However, by definition, a truth assignment gives a value to every variable.


Get mathematical relation of node IDs of a subtree based on a given tree

I don't think there is any "mathematical relationship". Observe that if you change the tree around the extracted subtree, the original IDs change arbitrarily.

You should copy properties while creating the copy of the tree you want to extract. Perform a tree traversal on the subtree in question and do everything in one pass.

You can also link new nodes to the old ones in case you need the relationship later.


Explain the difference between Turing Complete and Turing Equivalence

A system is Turing-complete if it is at least as powerful as Turing machines.
A system is Turing-equivalent if it is exactly as powerful as Turing machines.
An example of a Turing-complete system which is not Turing equivalent is Turing machines with oracle access to an oracle for the halting problem.
One can come up with one additional definition to complete the picture: a system is effective if it is at most as powerful as Turing machines, that is, if every function computed by the system is computable by a Turing machine.


The distinguishing factor is that meta-heuristics are problem independent.

Look at something like Travelling Salesman. You have 2-OPT, 3-OPT, Nearest Neighbour heuristics. These are all things that really don't carry much meaning outside the specific problem of Travelling Salesman.

A Meta-heuristic, on the other hand, assumes no prior knowledge of the problem. It's not saying "this is something that's likely to produce a good solution to our problem," it's saying that "this is something that is likely to produce good search results in general."

For TSP, the heuristic is that similar solutions will have correlated fitness values. More precicely, the simple heuristic is that, given your current population, the best solutions will look similar to the best ones in your population.

This is where "meta" comes in. Your population is always evolving, which means your heuristic is evolving as your search continues.

When I learned about metaheuristics, they talked less about pure GAs and more about combined techniques, things like Genetic Local Search or Probabilistic Model-based GAs. For PMBAs, it's easier to see the heuristic evolving: you choose some probabilistic model (such as Baysean networks) modelling correlations between input bits and fitness. You search, but the heuristic for which nodes you look at next isn't something static determined beforehand, it's dynamic, based on your probability model. The model keeps evolving, which means the search keeps evolving.

The slides from the class I took are here, you might find them interesting.


Derivation of the energy function of a hopfield network

I believe what you want to show is that the energy function is monotonically decreasing from time $t$ to time $t+1$ given the state update rules. Since there is only a finite number of states, this means the state must converge to a equilibrium under the given dynamics.

To this end let $\mathbf{s}(t) \in \{0,1\}^n$ be the state of the network at time $t$. We update the network state by picking a unit $s_i(t)$ and updating the state according to
$$
s_i(t+1) = \left\{\begin{array}{r l} 1:& \sum_{j} w_{ij} s_j(t) > 0\\ 0:& \text{otherwise}\end{array}\right.
$$
and define the energy function as
$$
E(\mathbf{s}(t)) = -\frac{1}{2}\sum_i\sum_jw_{ij}s_i(t)s_j(t),
$$
where $w_{ij}$ is the weight between unit $i$ and $j$, $w_{ij} = w_{ji}$ and $w_{ii} = 0$ for al $i$.

WLOG assume we will update the $i^{th}$ unit. First, because of the restrictions on the weights, we may rewrite $E(\mathbf{s}(t))$ as the difference of 2 terms
$$
E(\mathbf{s}(t)) = -\frac{1}{2}\sum_{j\neq i}\sum_{k\neq i}w_{jk}s_j(t)s_k(t) - s_i(t)\sum_jw_{ij}s_j.
$$
Let $c_t = -\frac{1}{2}\sum_{j\neq i}\sum_{k\neq i}w_{jk}s_j(t)s_k(t)$ be the part of the energy function that does not depend on $s_i(t)$. Now if $s_i(t+1) = s_i(t)$ then clearly we have $E(\mathbf{s}(t+1)) = E(\mathbf{s}(t))$, so we only need to consider the 2 other cases.

Case 1: If $s_i(t+1) = 1$ and $s_i(t) = 0$ then it must be that $\sum_{j} w_{ij} s_j(t) = \Delta_t > 0$. So
$$
E(\mathbf{s}(t+1)) = c_{t+1} - \Delta_t = c_t - \Delta_t < c_t = E(\mathbf{s}(t)).
$$
Case 2: If $s_i(t+1) = 0$ and $s_i(t) = 1$ then it must be that $\sum_{j} w_{ij} s_j(t) = \Delta_t \le 0$. So
$$
E(\mathbf{s}(t+1)) = c_{t+1} = c_t \le c_t - \Delta_t = E(\mathbf{s}(t)).
$$
Having considered each case we can conclude that $E(\mathbf{s}(t+1)) \le E(\mathbf{s}(t))$ and is therefore monotonically decreasing.


This problem can be approached with the Coppersmith method. For details, see my answer at MO to a similar question.


Huh? Let's modernise what you are saying a bit. Typical cache size nowadays is 64 bytes. So here is what a processor will typically do for such a cache:

Step 1a: Take the number of bytes accessed by the instruction, and the lowest six bits of the address, and determine whether the data is all within one cache line or straddles over two cache lines. (For example two consecutive bytes will in most cases be in one cache line, except if the lowest six bits are equal to 63. 16 consecutive bytes will often be in one cache line, except if the lowest six bits are greater than 48).

Step 1b: Use the other bits to determine the cache line where the data might be stored. If the cache has more than one way (say four way cache) this actually determines four possible cache lines.

Step 1c: Take the whole of the address to determine which of the possible ways contains the data. Also detect if the data is in the cache at all, and if not, start loading the data into cache which is much too complicated to explain here. When done, start all over again.

Steps 1a to 1c are performed in parallel if at all possible. Once the cache line containing the data, or the first part of the data is found, take the lowest six bits of the address, combine with the data size, and transfer as many bytes as needed and available.

If not all bytes needed are in the same cache line, repeat everything to get the remaining bytes.

Where your ideas went wrong: We don't set any bits of the address to zero, and we don't shift anything. We just take the parts of the address that are needed for every operation. To determine the cache line, you don't shift the address, you just take the address bits that are needed and you don't take the bits that are not needed. Since the lowest two bits are never zeroed, there is no problem accessing a byte anywhere in a cache line.


Computing the running time of a divide-by-4-and-conquer algorithm

The subroutine sub quarters the matrix into four parts. This takes time $f(n)$, and so the running-time of sum (which sums all entries in its input square matrix in a curious divide-and-conquer fashion) satisfies the recurrence
$$ T(n) = \begin{cases} O(1) & n=1 \\ 2T(\lfloor n/2 \rfloor) + 2T(\lceil n/2 \rceil) + f(n) + O(1) & n>1. \end{cases} $$
The subroutine sub is quite simple, and I'm sure you can figure out its running time yourself (though you'll have to be careful about the semantics of list appending in python).


Algorithm to pick elements in one array that sum to a setpoint, and corresponding elements in other array to average to a setpoint?

In general, no; this problem is NP-hard.  Even matching just the sum (without getting into anything about the average) is NP-hard, as it is the subset sum problem.  Thus, you should not expect any efficient algorithm for your problem that works for all possible inputs.

I notice that in your examples, the numbers are all small.  For that special case, there are reasonably efficient algorithms using dynamic programming: see, e.g., https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution.

The dynamic programming algorithm in that link describes how to make the sum match, but you can adapt it to make both the sum and average match.  In particular, you have an array $Q[t_1,t_2,i,k]$, which you will fill in with True if there exists a subset of $k$ out of the first $i$ rows whose first column sums to $t_1$ and whose second column sums to $t_2$.  You can use dynamic programming to fill in this array (in order of increasing $i$) in $O(N^4M^2)$ time, where $N$ counts the number of rows in your spreadsheet and $M$ is the largest number in the spreadsheet.  Then, once you've filled in this array, there will be a selection that sums to $s$ and averages to $a$ if and only if there is some $k$ such that $Q[s,ak,N,k]$ is True.

I recommend implementing this in a programming language (e.g., VBA, not Excel).  Implementing it in Excel might be possible but it sounds painful.  See https://cs.stackexchange.com/tags/dynamic-programming/info for our reference material on dynamic programming; if you're not familiar with that subject, you might want to read a textbook introduction to it.


A continuous optimization problem that reduces to TSP

The differentiability requirement doesn't change the nature of the problem: requiring $\mathcal{C}^0$ (continuity) or $\mathcal{C}^{\infty}$ (infinite differentiability) gives the same lower bound for the length and the same order of points, and is equivalent to solving the traveling salesman problem.

If you have a solution to the TSP, you have a $\mathcal{C}^0$ curve that goes through all the points. Conversely, suppose you have a $\mathcal{C}^0$ curve of finite length that goes through all the points, and let $p_{\sigma(1)}, \ldots, p_{\sigma(n)}$ be the order in which it traverses the points and $t_1,\ldots,t_n$ the corresponding parameters (if the curve traverses a point more than once, pick any of the possible values of $t$). Then the curve built from $n$ segments $[p_{\sigma(1)},p_{\sigma(2)}], \ldots, [p_{\sigma(n-1)},p_{\sigma(n)}], [p_{\sigma(n)},p_{\sigma(1)}]$ is shorter, because for each segment a straight line is shorter than any other curve that connects the point. Thus for every ordering of the points, the best curve is a TSP solution, and the TSP solution provides the best ordering of the points.

Let's now show that requiring the curve to be $\mathcal{C}^{\infty}$ (or $\mathcal{C}^k$ for any $k$) doesn't change the best ordering of points. For any TSP solution of total length $\ell$ and any $\epsilon > 0$, we can round every corner, i.e. build a $\mathcal{C}^{\infty}$ curve that traverses the points in the same order and has a length of at most $\ell + \epsilon$ (the explicit construction relies on algebraic functions and $e^{-1/t^2}$ to define bump functions and from those smooth connections between curve segments such as $e^{1-1/x^2} (x-e^{-1/(1-x)^2})$ which connects with $y=0$ at $x=0$ and with $y=x$ at $x=1$; it is tedious to make these explicit, but they are computable); hence, the lower bound for a $\mathcal{C}^{\infty}$ curve is the same as for a collection of segments (note that the lower bound is not reached in general).


Why does TSP require no repetition of cities?

It doesn't matter exactly how you define it because it's just a way of modelling a real-world problem. In TSP, you just have a set of cities and the cost of travelling between each pair of them. That doesn't exclude the possibility that, in the real world situation you're modelling, the best route between B and C might go through A. If that was the case then, yes, the route that is modeled as ABCA in TSP may very well really involve driving through A an extra time on the way from B to C but such detail is abstracted away in the TSP model.


Will $L = \{a^* b^*\}$ be classified as a regular language?

A language is regular, by definition, if it is accepted by some DFA. (This is at least one common definition.) Can you think of a DFA accepting the language?

A well-known result (that is proved in many textbooks) states that the language of a regular expression is regular. Since $a^* b^*$ is a regular expression, its language must be regular (if you believe this result).

Finally, to answer your question (what difference does the Kleene star make): in the language $\{a^n b^n : n \geq 0\}$, we need to count the number of $a$s and $b$s; in the language $a^*b^*$ we don't.


Why do I need a base case for n=3 when solving a d&c recurrence?

They do not want $T(1)$ to occur as a base case as it causes troubles. $T(3)$ depends on $T(1)$, so if they didn't take $T(3)$ as a base case in addition to taking $T(2)$ as one, they'd run into trouble when applying the inductive step to $T(3)$ as the hypothesis does not hold for $T(\lfloor{\frac{3}{2}}\rfloor)=T(1)$.


Hardware thread context and register renaming

I am not expert about hardware threading but I know two different ways to achieve it with potentially different answers:

Architectures where the CPU executes one thread at a time but switches on some events (quantum expire, cache miss, switch instruction, ...). In that case, the CPU only really needs 32 registers and on a context switch it can store/load them from either physical registers or memory. Another option is to to register renaming (see below)
Architectures where the CPU really executes the thread in parallel: this can be a Barrel processor that switches on every cycle, or a more complicated out-of-order architecture like Hyper-threading. In both cases, the CPU really needs 128 registers. The way it is usually implemented is that registers are renamed: the CPU has registers 0-95, and register i of thread j is renamed to 4*i+j (for example register 2 of thread 3 is renamed 3*32+2=98). The advantage of doing that is that the pipeline and functional units scheduling and all becomes almost thread agnostic.


Depth of a leaf in a prefix tree (Huffman Coding)

Consider a symbol $\sigma$ whose frequency is $f$. During the course of Huffman's algorithm, $\sigma$ is matched with other nodes, and the depth of $\sigma$ is the number of times this happens.

At the first time that $\sigma$ is matched, it is either the symbol with smallest frequency or with second smallest frequency. In the former case, it is merged into a new symbol whose frequency is at least $2f$. In the latter case, after $\sigma$ is merged with the symbol of smallest frequency, all symbols have frequency at least $f$, and so the next time that it is merged, the merged symbol will have frequency at least $2f$.

Summarizing, it takes at most two mergings to double the frequency of a symbol. If its original frequency is $f$, then this shows that the depth of $f$ is at most $2\lceil \log_2(1/f) \rceil = O(\log(1/f))$.


reduce k-colorable to 3-colorable graph problem

It is known that K-Colorability reduces to 3-Colorability in polynomial time as obviously both problems are NP-complete, and NP-complete problems are polynomial-time reducible to each other. However, in order to $k$-color a graph using a 3-coloring oracle, you need a specific reduction from $k$-colorability to $3$-colorability which is constructive in the sense that given a 3 coloring of the output graph, then you have a way to extract from it a $k$-coloring of the input graph (and not only prove that there exists a $k$-coloring). Such a reduction, was shown by László Lovász  here. Specifically, it was shown that Colorability reduces to 3-Colorability in polynomial time which is sufficient to solve your problem using the same reduction. Here is a very good explanation by Vašek Chvátal's for Lovász's reduction. The reduction has the following format:  given an instance to the Colorability problem which is a pair $\langle k, G \rangle $, where $k$ is a positive integer and $G$ is an undirected graph, the reduction outputs in polynomial time, a graph $G'$ such that $G'$ has a 3-coloring iff $G$ has a k-coloring. The proof in the link is actually constructive, in particular, it details how a k-coloring of $G$  can be easily extracted from a 3-coloring of $G'$ (When I say easily, I mean in polynomial time). So to solve your problem: given a graph $G$, you can consider the pair $x = \langle k, G\rangle$ ($k$ is constant in your problem) and feed $x$ as an input to the reduction to get $G'$ in polynomial time. Now using your oracle, you can 3-color $G'$, and then use the 3-coloring of $G'$ to extract a $k$-coloring of $G$.


A random binary tree is any tree that is generated by any random process.  So, yes.  You have described a random process that generates a binary tree; you can describe the result as a random binary tree.

At a technical level, if you have any random variable whose values are binary trees, it would be reasonable to call that a "random binary tree".

Wikipedia is saying that there are two random processes that are particularly commonly considered.  But those aren't the only possibilities.  You've described a third possibility, and that's also valid.


k disjoint triangles with graph splitting to two distinct groups

Color the vertices in $V \setminus X$ with $2k$ colors at random. With probability $e^{-2k}$, the $V \setminus X$ vertices of your $k$ disjoint triangles will be highlighted.
Suppose without loss of generality that $X = [m]$.
Using dynamic programming, determine for each subset $S \subseteq [2k]$ and $i \in [m]$ whether there exist $|S|/2$ disjoint triangles using the colors in $S$ and vertices $1,\ldots,i$ of $X$. This takes time $O^*(2^{2k})$.


Why sequential consistency model is widely used if it is unsound

The underlying hardware often has more relaxed memory ordering compared to SC. For example, the X86 will allow for older stores to be reordered with newer loads for a different address due to store buffers. So instead of having a total order over all loads and stores (SC), you only get a total order over all store (TSO). ARM is even more relaxed. And apart from the hardware, the compiler can also reorder instructions if this isn't prohibited.
There are also weak memory models. Weak memory models are a relaxation of strong memory models like SC/TSO because a distinction is made between plain loads and stores and synchronizing loads/stores.
For most engineer it is way too difficult to reason about any other model than SC. SC is often the most intuitive model and that is why many API's are SC (e.g. a C++ atomic by default is SC or Java volatile) and why language level memory models like the Java Memory Model are rooted in SC. Only the experts understand how to relax consistency in favor of improved scalability/performance.


Check if an array is a substring of another array

The problem is called substring search or string search or string matching. It's called a substring even if the elements of the array aren't characters. In this answer, I'll use character to refer to elements of the arrays, but this can be any kind of data (numbers, nested data structures, …). The standard terminology is:

subset (without multiplicity): all the elements of $A$ are also found in $B$. For example $(1,2,3,1)$ is a subset of $(3,4,1,2)$.
subset with multiplicity: for every element of $A$, there is a corresponding element in $B$. The difference from the basic subset problem is that if an element in $A$ is repeated, it must be repeated at least as many times in $B$. For example $(1,2,3,1)$ is a subset of $(3,4,1,1,2)$ but not of $(3,4,1,2)$. The terminology around this problem isn't completely standardized, sometimes ”subset“ refers to this.
subsequence: the elements of $A$ are also present in $B$, in the same order, but there may be other elements in between. For example $(1,2,3)$ is a subsequence of $(0,1,0,2,3,4)$ and $(1,2,2,3)$ but not of $(3,1,2,0)$.
substring: the elements of $A$ are also present in $B$, in the same order and consecutively. For example $(1,2,3)$ is a substring of $(0,1,2,3,4)$ but not of $(1,2,2,3)$.

Substring search is a very well-studied problem. The naive approach, where you take each possible starting position in $B$ in turn and try to match $A$ there, runs in $O(m\,n)$ where $m$ is the length of $A$ and $n$ is the length of $B$.

The naive approach can be improved because it often ends up making tests which could have been known to be false or whose outcome doesn't affect the final result. For example:

If one of the elements of $A$ never occurs in $B$, this can be noticed with a single pass in $B$, in time $O(n)$: there's no need to test the other characters of $A$. More generally, if a character in $A$ occurs rarely in $B$, it's best to match this one first against the elements of $B$.
When matching abcdabe at the start of abcdefabcdabcdabe, once position $5$ is reached (a ≠ e), the naive algorithm tries to match $A$ starting at position $2$. An improvement is to notice that the first character of $A$ wasn't present in the positions of $B$ that have already been read, so there's no need to test $A$ again against earlier positions.

Improved substring search algorithms rely on preprocessing $A$ to notice opportunities like these to make the matching more efficient. For example, a simple approach from a theoretical perspective is to build a deterministic finite automaton that recognizes the regular expression $\mathord{.}^*A$, which recognizes all strings that end in $A$. If the automaton ever reaches an accepting state, this indicates that $A$ has been found as a substring of $B$. This algorithm requires a preprocessing phase on $A$ which requires $O(m^2)$ time; after this, $B$ can be processed with no backtracking. Each position in $B$ requires $O(1)$ time to analyze the character in $B$ and look it up in the table of transitions from the current node in the automaton. Thus the running time for the search (including preprocessing) is $O(m^2 + n)$.

Two common substring algorithms are:

Knuth-Morris-Pratt, which builds on the same idea as the finite automaton, but constructs a more specialized table in time $O(m)$, for a total running time of $O(n)$.
Boyer-Moore, which also builds a table, and tries matching from the end of $A$, which allows it to skip characters in $B$. The basic Boyer-Moore algorithm has a $\Theta(m\,n)$ worst case (like naive search), but can pass over non-matching strings in time $n/m$ in the best case. There are Boyer-Moore variants with an $O(m+n)$ worst case.

Intuitively, $O(m+n)$ is as good as it gets, since in the worst case all characters in $m$ and $n$ must be read (the worst case being reached when $B$ is full of substrings that are close to $A$ but not identical).


I assume by "comparable part of the area" you mean that they should all scan a region of equal area. Additionally, knowing what kind of plane area you have would be helpful, is it convex, is it concave, is it just a regular polygon? If you know this then there are easier ways to do it.
So assuming you want for the worst case, a concave polygon, the best solution that I know of is this.
This page has a detailed explanation of the algorithm and there's even some comments with implementations.


What is the point of an active shape model in facial recognition?

The active shape model algorithm is used to locate precisely the eyes, eyebrows, nose and mouth of a person. It is also used to align faces that are tilted.
It is not used directly for face matching and it has nothing to do with databases. It is a preprocessing step.
You (I) will need another algorithm to match its result with a database. (ICA for example)


Luckily i had 2 day ago the algorithm exam and so i was able to solve your question :-)
When solving recurrences try first to use the Master method, if you can't succeed than try other methods.


Why is pure literal elimination absent in DPLL-based algorithms like Chaff?

Solvers that use the two-watched-literals algorithm to implement unit propagation don't keep track of which clauses have been deleted (by implication) to produce the subformula implied by the current partial assignment.  By not tracking this information, solvers can avoid touching most of the clauses during assignments and avoid touching any of the clauses during backtracking.  Figuring out which variables are currently pure in the formula means losing these substantial efficiency gains.  Meanwhile there's nothing to suggest that pure literal removal will produce conflicts or satisfying assignments early enough to make up for the heavy tracking cost.

Solvers that do formula simplification before starting the search procedure will generally include pure literal removal since it is quite cheap to do as a preprocessing step and could potentially remove many clauses.


CFG for language of all palindromes whose number of 1s is divisible by 3

One way is to use the closure of context-free languages to intersection with a regular language.

In this case, though, it is simple enough to construct the grammar explicitly. The idea is to have three different symbols, $S_0,S_1,S_2$, where $S_b$ generates all palindromes in which the number of 1s is equivalent to $b$ mod 3. The productions for $S_0$ are
$$
S_0 \to 0S_00 \mid 1S_11 \mid 0 \mid \epsilon.
$$
I'll let you figure out the productions for $S_1,S_2$, as well as which symbol is the starting symbol.


Rigorous reason against the seemingly wrong way of substitution

You're not going to find a rigorous reason, because there is no semantic reason. The reason is purely syntactic.

The key is to remember that lambda calculus expression are, in fact, trees. A node is either a variable, with no children, an application with two children, or a lambda, with two children, one of which is the variable it binds.

Trees are hard to write, so we have a syntax for writing expression trees in a linear way. If we wrap every expression in parentheses, there's an unambiguous mapping between linear expressions and trees. But any time that parentheses are missing, we need precedence rules to disambiguate.

The choice of precedence rules is arbitrary, and is purely catered towards human understanding.

Once you're working with trees, or at least fully parenthesized expressions, then it should be more clear why the argument is given as the outermost bound variable: application is a binary operation between siblings in the trees. Other than the substitution operation, we don't want to have to look up or down the tree when applying a reduction.

If you want a syntax where you don't always apply arguments this way, you may be interested in the spine calculus, which is a syntax that nicely captures the idea of applying multiple arguments to a single core, called the head.


Finding the number of leaves in a imbalanced recursion tree

Why is thetotal number of leaves in $\Theta(n)$? Because each level in recursion tree corresponds to a splitting of an array's range. When we have one element we can't split it any more so we stop. That's $\Theta(1)$ per leaf. How many 1-element areas are there in an $n$ element array? The answer is $n$.

He is summing up all levels. But levels are not all populated. Some paths down are short, some long. The more to the left in the tree, the shorter is the path. So going down the right "spine" of the tree, how many levels are there? $\log_{10/9}(n)$. What each level sums up to? Initially, $cn$ (where $c$ is a constant, $n$ is number of elements in the array) - while the levels are totally populated - i.e. all nodes represent splits - i.e. no one-element ranges are reached yet. Then, we start missing some leaves, so instead of "equal" , we can write $\leq cn$. So the total sum is less than $cn\log_{10/9}(n)$.
Or, let's go down the left spine and sum all levels up. There will be some uncounted tree to the right and down. So the total is greater than this summation, which equals $cn\log_{10}(n)$. He uses "or-equal" just because he's a mathematician who doesn't like to be wrong in some corner cases. :)

This is all pretty straight-forward and intuitive.


Purpose of randomization/derandomization in basic randomized algorithm for MAX SAT

The difference is that the randomized algorithm guarantees an expected 1/2-approximation on any input. By contrast, it is easy for an adversary to construct an input (i.e. an instance of MAX-SAT) for which the deterministic "set all variables to true" algorithm satisifes zero clauses.
Remember that the sample space for a randomized algorithm is over a set of auxiliary random bits. There is no probability distribution assumed over the inputs. The typical goal of randomized algorithm design is for every input to be handled well in expectation. (Analyzing algorithm behavior over an assumed input distribution is called average-case analysis instead.)
What are auxiliary random bits?
Suppose we have a randomized Turing machine $M_1$ that runs on instances of length $n$ for no more than $T(n)$ time, during which it makes no more than $R(n) \le T(n)$ random decisions. We can turn this machine into a deterministic Turing machine $M_2$ that has two input tapes: the usual tape that contains the input string $x$ of length $n$, and a tape that contains a string $r$ of length $R(n)$. The string $r$ is our string of auxiliary random bits; it determines which "random" decisions the Turing machine is to make. When we say that the randomized Turing machine run $M_1(x)$ accepts with probability $p$, this is equivalent to saying that the set
$$A(x) = \left\{r\ |\ r \in \{0, 1\}^{R(|x|)}, M_2(x, r)\text{ accepts}\right\}$$
of $r$ strings that make $M_2(x, r)$ accept constitutes a fraction $p = |A(x)| / 2^{|x|}$ of the set of all $r$ strings.
You might recognize what is going on here if you've seen the analogous construction for nondeterministic Turing machines. We can think of an NP machine as a nondeterministic machine that branches into exponentially many copies of itself. But we can also think of it as a deterministic verifier machine that requires both an input and a "proof" string, with the acceptance criteria that an input string is in the language if any proof string makes the machine accept.
It is often easier to think about this down-to-Earth concept of deterministic verifier machines and which subset of proof strings makes the machine accept on a given input, rather than thinking about very abstract ideas like exponentially branching machines and possible worlds. And it makes it easier to define complexity classes such as co-NP, PP, BPP, ⊕P, etc., all of which are essentially "NP with a different acceptance rule." For example:

NP is the set of languages $L$ for which there exists a polynomial-time verifier machine $M_2$ such that $x \in L$ if and only if there exists an $r$ string such that $M_2(x, r)$ accepts (where the length of the $r$ string is bounded by a polynomial $R(|x|)$).
BPP is the set of languages $L$ for which there exists a polynomial-time verifier machine $M_2(x, r)$ such that $x \in L$ implies that $M_2(x, r)$ accepts for at least ⅔ of $r$ strings and $x \notin L$ implies that $M_2(x, r)$ accepts for at most ⅓ of $r$ strings (where the length of the $r$ strings is bounded by a polynomial $R(|x|)$).

Note: It mostly doesn't matter whether we require the $r$ strings to have length exactly $R(n)$ or at most $R(n)$, since allowing shorter strings only increases the number of possible strings by a constant factor.


How to handle the repeat until convergence condition in time complexity and summarize the time complexity?

First of all, repeat until convergence isn't quite a well-defined command. Typically, such instructions are implemented by checking the "progress" of some performance measure, stopping once progress drops below a certain threshold.

In order to estimate the running time ("big O") of such an algorithm, all you need to do is to estimate the number of iterations until convergence. The running time of a simple "repeat until convergence" loop is simply the running time of the loop body times the number of iterations. This is a good upper bound if each loop iteration takes roughly the same time. In more complicated cases, in which the iterations have greatly varying running times, you can use a more accurate measure, namely the total running time of the loop body (across all iterations).

This is the theory. How do you apply it in your particular case? In the loop highlighted in yellow, the loop body has unvarying running time, so you need to figure out how many iterations it takes the loop to converge, and then you multiply that by the time it takes to run a single iteration. Estimating the number of iterations until convergence is beyond the scope of this answer.


Directed graph where DFS returns on a node before all its child nodes are visited?

Consider the following graph. If DFS will first go to the second node, it will back up even though the third node is reachable from the second.


Since languages $A$ and $B$ are regular, we can assume there are DFAs
$$
M_A = \{Q_A, \Sigma, \delta_A, s_A, F_A\} ~~\text{and}~~ M_B = \{Q_B, \Sigma, \delta_B, s_B, F_B\}
$$
that recognize them, respectively.
Let's call the zig-zag lanuage $Z$. It is easy to see that the alphabet of $Z$ is $\Sigma$.

We will construct a DFA, $M_Z = \{Q_Z, \Sigma, \delta_Z, s_Z, F_Z\}$, for $Z$.

Set of states

$M_Z$ must be such that it will alternately apply $\delta_A$ and $\delta_B$ each time it reads a character from the input string. For that, it must be able to track all possible combinations between states of $M_A$ and $M_B$, as well as which of the two transition functions it should apply on the next transition. We will use 0 to represent that the next transition should be a $\delta_A$-move and $1$ for a $\delta_B$-move. Altogether, we have $Q_Z = Q_A \times Q_B \times \{0,1\}$.

Initial state

Clearly, the initial state of $M_Z$ is $s_Z = (s_A, s_B, 0)$.

Accepting states

For a state $q_f = (q_A, q_B, i)$ of $M_Z$ to be accepting, both $q_A$ and $q_B$ must be accepting states of $M_A$ and $M_B$, respectively. This is to satisfy the conditions $a_1\ldots a_k\in A$ and $b_1\ldots b_k\in B$ in the definition of $Z$. In addition, the last transition before reaching $q_f$ should be a $\delta_B$-move, therefore the next transition (if there is one) is expected to be a $\delta_A$-move, represented with  $i = 0$. So, the set of accepting states is $F_Z = F_A\times F_B\times\{0\}$.

Transition function: Here is where the alternating behavior of $M_Z$ is constructed.

If the DFA is in a 0-state, then it should perform a $\delta_A$-move, leading to a 1-state. The DFA still needs to remember the (non-active, for now) state of $M_B$.
A similar behavior, but with 0 and 1 switched, is adopted for transitions from 1-states.
\begin{align*}
\delta_Z((q_A, q_B, 0), x) &= (\delta_A(q_A, x), q_B, 1)\\
\delta_Z((q_A, q_B, 1), x) &= (q_A, \delta_B(q_B, x), 0)
\end{align*}


Reduction to equipartition problem from the partition problem?

As noted in the comments, the EQUIPARTITION problem is also NP-complete. The basic idea of reducing PARTITION to it is to add elements so that they can be partitioned complementary to the original elements (thus yielding an equipartition) but in a way that ensures that new and old elements can not cancel each other out. The latter can be achieved by choosing the new elements sufficiently large.

Let $A = \{a_1, \dots, a_n\} \subseteq \mathbb{N}_+$ be an instance of PARTITION. Construct an instance $f(A)$ of EQUIPARTITION by

$\qquad \displaystyle f(A) = A \cup \{ a_{n+i} \mid a_{n+i} = 2B \cdot a_i, a_i \in A \}$

with $2B = \sum_{a \in A} a$. It is clear that $f$ can be computed in deterministic polynomial time. We have to show that $A$ is a YES-instance of PARTITION if and only if $f(A)$ is a YES-instance of EQUIPARTITION.

Let $A$ be a YES-instance of PARTITION, that is there is $I \subset [n]$ with $\sum_{i \in I} a_i = B$. Then,

$\qquad \displaystyle I' = I \cup \{n+i \mid i \in \overline{I} = [n] \setminus I \}$

is a solution of $f(A)$; note that $|I'| = n$ and $\sum_{i \in I'} a_i = B + 2B^2 =  \sum_{i \in \overline{I'}} a_i$. Thus, $f(A)$ is a YES-instance of EQUIPARTITION.
Let $f(A)$ be a YES-instance of EQUIPARTITION. Let $I' = I \cup J$ a solution of $f(A)$ with $I \subseteq [n]$ and $J \subseteq [2n] \setminus [n]$ ($I$ contains the indices chosen from $A$, $J$ the new ones), and $\overline{I'} = \overline{I} \cup \overline{J}$ its complement, similarly partitioned. That is, $\sum_{i \in I'} a_i = \sum_{i \in \overline{I'}} a_i$

Assume towards a contradiction that $\sum_{i \in I} a_i \neq \sum_{i \in \overline{I}} a_i$; without loss of generality assume $\sum_{i \in I} a_i > \sum_{i \in \overline{I}} a_i$. Now we have that

$\qquad \displaystyle 0 < \sum_{i \in \overline{J}} a_i - \sum_{i \in J} a_i = \sum_{i \in I} a_i - \sum_{i \in \overline{I}} a_i < 2B$

which contradicts the construction of $f(A)$; elements with indices in $J \cup \overline{J}$ are all (positive) multiples of $2B$ so the assumed difference is impossible. Therefore, $I$ is a solution of $A$ which is thus a YES-instance of PARTITION.

This concludes the proof, that is PARTITION $\leq_p$ EQUIPARTITION by virtue of $f$.


In general, how does a DFA know how to successfully process a string the intended way?

The transition function of a DFA has the type $\delta : (Q \times \Sigma) \rightarrow Q$. That is, it's a function that takes a state (from the set of states) and a symbol (from the set of symbols) and returns another state.
This function doesn't have to know anything about tokenization. It's given a single symbol, and that's all it cares about.
Similarly, the input to a DFA is generally defined to be an ordered series of symbols: this is what "a string over the alphabet $\Sigma$" means mathematically. If it helps, think of it as a "list" rather than a "string" in programming terms. So if the alphabet were $\{x, xx, xxx\}$, then the input might look something like $[x, xx, xxx, x, xx, xxx, x, xx, xxx]$. No ambiguity there.
In practice, most real-world DFA implementations (like foma) do have to care about tokenizing. But the details of how to do that are up to the implementation; the definition of a DFA doesn't care one way or the other.


Create a PDA that accepts the following language

The PDA operates as follows :

Push the symbols you read to the stack

Non-deterministically guess when u ends and w starts

Now for the rest of the string , we consider 2 symbols by 2 symbols , if the 2 symbols are not the same reject , if the 2 symbols are the same , compare them to top of stack , if they are not the same symbol reject , if they are the same pop the stack

After reading the entire input , if the stack is empty accept , else reject

Ex : s = ab bbaa , we push a,b to stack , then we guess u ends and w starts , now we read  b , then b , both are same symbol , we look at top of stack we have  b we pop the b , now the stack has a , and we will read aa , repeat the above again and we accept
If you get how it works , you may want to try to sketch the PDA
Here is a sketch of the PDA to check your answer  :


Bounded waiting and starvation free in critical section problem

No, starvation-free doesn't imply bounded waiting.

For instance, consider a procedure that never even attempts to acquire any lock; but the amount of time it takes is variable and can be arbitrarily long.  Then there is no bound on the amount of time it might take to complete its operation.

Here is another example of how it can fail.  Starvation-free means that every attempt to acquire the lock eventually succeeds -- but that says nothing about how long it might take.  Maybe the amount of time it will take to acquire the lock is variable and can be arbitrarily long -- there is no upper bound on how long it takes to acquire the lock.  Then a procedure that first attempts to acquire the lock before doing anything else won't satisfy bounded waiting.


Proof of composition of one way function is not one way in general

"for a given output of g(x,y) = 0|x| of length l (say)," "the output of g(any x of length l, 0l)"

is "the same as the earlier output", which means that is "a possible preimage of 0|x|".

Accordingly, for  $g\hspace{-0.04 in}\circ \hspace{-0.03 in}f$  to be one-way, it had better be the case that

$\operatorname{Prob}_{\langle \hspace{.02 in}x,y\rangle \hspace{.02 in}\leftarrow \hspace{.02 in}\left(\hspace{-0.03 in}\{\hspace{-0.02 in}0,1\hspace{-0.02 in}\}^{\hspace{.02 in}L}\hspace{-0.03 in}\right)^{\hspace{.05 in}2}}\hspace{-0.1 in}\left[g(x,\hspace{-0.04 in}y) = 0^{\hspace{.03 in}L}\hspace{-0.0 in}\right] \;\;\;$ is negligible.


Hint: Replace every transition labelled $a \in \Sigma$ with a transition labelled $\Sigma$.


This is called the Minimal Clique Cover Problem, and is NP-hard: as a matter of fact, the decision version ("can I do it with only $k$ subgraphs?") is one of Karp's original 21 Problems, the ones that first defined NP-completeness.

Since it's linked to graph coloring, you can't even get a good approximation in polynomial time, unfortunately: everything about this problem is hard.

For further reading, your "super-strongly connected components" are generally called cliques, and a clique cover is a way to "cover" the entire graph with non-overlapping cliques. A minimal clique cover uses the smallest possible number of cliques to do it.


The issue is that you might not enter the second "if" when the current sum is smaller than nums[i].
Imagine, e.g., that at the beginning of the iteration you have  currentSum=-5, max=100, nums[i]=10.
At the end of the iteration you have currentSum=5 and max=100, yet the desired state is currentSum=10, max=100.
A corresponding instance where your algorithm fails is: 100, -105, 10, 95.
To fix this, the condition of the second "if" should be currentSum < nums[i].
Notice that, once you change this condition, you'll also have to revise other parts of your code accordingly: you can no longer unconditionally assign max to nums[i] in the body of the second "if" statement. This can be easily fixed by removing that assignment and swapping the order of your two ifs.
[...]
        if(currentSum < nums[i])
            currentSum = nums[i];

        if(max < currentSum)
            max = currentSum;
[...]


The text has a luminance value $t_0$ and the background occupies a luminance interval $[L_0,H_0]$, $L_0 \le H_0$. I think what you want is to ensure a separation of at least some $s$ between them. There are many degrees of freedom here; one way to capture most of them is to decide beforehand on a way to penalise changes in these variables, as well as the penalty for changing the background interval width $H-L$, and then look for a solution that minimises this penalty cost.
We could use a linear cost model, where the absolute value of the change in each variable is penalised, but this has the disadvantage that optimal solutions are not always unique. So let's use a quadratic cost model (least squares), with penalty weights $c_t, c_L$ and $c_H$ for changes to the main variables, and also a weight $c_d$ for the penalty for changing $H-L$ (i.e., stretching or squashing the background luminance range). Then you want to choose $t, L$ and $H$ to minimise $$p = c_t(t-t_0)^2 + c_L(L-L_0)^2 + c_H(H-H_0)^2 + c_d(H-L-H_0+L_0)^2$$ such that $L \le H$ and either $t \ge H + s$ or $t \le L - s$. This gives a lot of flexibility: Set any of the $c$-parameters to zero to express that you don't care about changes in the corresponding quantity; set it extremely high to try hard to avoid changing it. A sensible first choice might be to set them all equal to 1, and if that yields solutions that "look wrong", increase the weights of whichever values moved around too much.
If $t_0$ is already separated from $[L_0, H_0]$ by $s$, then leaving it unchanged is the optimal solution. Otherwise, intuitively, an optimal solution must have a tight gap, i.e., either $t = H+s$ or $t = L-s$. This can be solved by solving for each of the two cases separately and choosing the better one.
To solve for the first case, substitute $t = H+s$, find the partial derivatives of $p$ w.r.t. the two remaining variables $H$ and $L$, set these to zero:
$$\begin{align}
p & = c_t(H+s-t_0)^2 + c_L(L-L_0)^2 + c_H(H-H_0)^2 + c_d(H-L-H_0+L_0)^2\\
\frac{\partial p}{\partial L} & = 2c_L(L-L_0) + 2c_d(H-L-H_0+L_0) = 0\\
\frac{\partial p}{\partial H} & = 2c_t(H+s-t_0) + 2c_H(H-H_0) + 2c_d(H-L-H_0+L_0) = 0
\end{align}$$, and solve the resulting set of simultaneous equations for these variables to find the minimum:
$$\begin{align}
L & = \frac{c_LL_0 + c_d(H_0-H-L_0)}{c_L - c_d}\\
H & = \frac{c_t(t_0-s) + c_HH_0 + c_d(L+H_0-L_0)}{c_t + c_H + c_d}\\
& = \frac{c_t(t_0-s) + c_HH_0 + c_d(\frac{c_LL_0 + c_d(H_0-H-L_0)}{c_L - c_d}+H_0-L_0)}{c_t + c_H + c_d}
\end{align}$$
Having computed the optimal value of $H$, you can substitute this back into the expressions for $L$ and $t$, and then calculate $p$ for this case. The derivation for the $t=L-s$ case is very similar. Finally, pick whichever gives the lower $p$ value.


No reps to comment.

@Nathan:
The binary address is split as a tag-part and the block size. Basically, the cache is split as many-byte blocks and tag each entry maps to a block and the index, or offset, is added to the address to address a byte.

So the binary addresses are 8-bits long. And based on the question the block seems to be 8 bytes long (hence 3 LSB bits for Index, also called offset). This leaves 5 additional bits for tag (Remember addresses are 8 bits long).


Count points enclosed by several planes in 3D space

A plane divides the 3D space in two regions.  A good method to discern is to apply the plane equation to the point and see if it yields negative or positive result:

$$Ax + By + Cz + D = 0$$

is the equation of a plane in 3D. So if you put the point coordinates you'll get a positive, zero or negative number. (If zero, the point belongs to the plane and so, it's neither in either side of the plane.)

The question asks to count the points that belong to each of the delimited regions for each plane.  Well, you have n planes each dividing the space in two halves (so you have $2^n$ regions at most, except in case you have paralell planes, but this procedure is applicable also in that case ---you'll get regions not accounted for as no point can lie in them), just consider each point and apply it to each plane.  Then construct a number X, making bit $i$ (for plane $i$) of X a 1 in case applying plane to it gives a positive number and 0 in case applying it gives a negative one (in case it returns 0 you have to decide what side to count it ---what value you select for bit $i$--- for (if any) as this is a point that belongs to the plane) then with that number as a key for region X, increment counter of region X selected, so in one pass over all points you'll get all counters actualized with how many points belong to each region.  Each key X, so constructed, identifies each of the possible regions you have divided the space into, so you must cope with $2^n$ regions (and counters) for $n$ planes.