Proving $P=BPP$ under a assumption Let suppose that there exists deterministic polynomial algorithm $A$ that  approximates the probability that a given boolean circuit $C$ accepts random input with an error at most $\frac{2}{5}$. More precisely, for a boolean circuit $C(x_1, .., x_n)$, $A$ computes a number $A(C)$ such that

$$|\Pr[C(U_n) = 1] - A(C) | \le \frac{2}{5}.$$

$U_n$ is a uniformly distributed random variable with values in $\{0,1\}^n$.

I want to prove that under that assumption $P=BPP$.  How can I do that?

Obviously, the problem is with $BPP \subseteq P$.
I see that I should create a boolean circuit for "coin tosses", but how?

$w$ is an input word, $r$ is a random bits used by a machine to make random decisions.

So, it is obvious that $P \subseteq BPP$, so let's try to show that: $BPP \subseteq P$.

Let $L$ in $BPP$. Then $M(w, r)$ be a machine that decides $L \in BPP$. $M$ is a polynomial probabilistic machine. Let $M'(w, r)$ be an polynomially amplifcated $M$, so:
$$w \in L \implies Pr[M'(w, r) \text{ accepts }w] \to 1$$
$$w \not \in L \implies Pr[M'(w, r) \text{ rejects }w] \to 1$$

Now, we construct machine $M_p$ that recognizes $L$ and works in polynomial time.

Let $w$ be a given word to decide. $M_p$ constructs in polynomial time a boolan circuit $C$ equivalent to $M'(w,r)$ where $w$ be hardcoded in that circuit. So, the input word is a random string, $r$.

Note, that our machine $M_p$ So, for a random input  $r$ our machine for word $w \in L$ must accept it if $M'$ accepts it with probability $\approx 1$.

But, we must show that $L \in P$ so we cannot use a random word $r$.

Instead, we would like to ask our algorithm about probability of acceptance a random word: $A(C)$. The returned value must be $\approx 0.6$ because possible error is $0.4$. So, if A(C) is $\ge 0.6$ then $M_p$ accepts, else rejects.

It works in polynomial and it accepts the same language:

$$w \in L \implies Pr[M' \text{ accepts w is }] \approx 1 $$
$$w \not \in L \implies Pr[M' \text{ rejects w is }] \approx 1 $$


Is the Shakespeare Programming Language Turing complete? I was reading about tge Turing machine. I also came across with the Shakespeare programming language. After trying to understand the basics of the PL, I thought that it must be non-Turing complete. On some page I found out that I was wrong and Shakespeare is actually "turing complete".

I didn't find how can I create while loops or recursive calls in Shakespeare so I can't understand why it us Turing complete.

Will be glad for some explanation.

In that page, the snippet

Juliet:
 Am I better than you?

Hamlet:
 If so, let us proceed to scene III.

essentially means

if (Juliet > Hamlet) goto Scene III

This can be used to implement while loops. In pseudo syntax:

Scene II:
if (Juliet > Hamlet) goto Scene III
... some statements here
goto Scene II
Scene III:
... more statements here

is essentially equivalent to

while (Juliet <= Hamlet) {
   ... some statements here
}
... more statements here


Meta-computational complexity? Computational complexity asks the following question: Given a problem $P$, what is the time-cost of the lowest time-cost machine $M^*$ that solves $P$?

But this misses a certain aspect of the complexity of $P$, namely the complexity of finding $M^*$ in the space of machines. The problem of finding $M^*$ can be seen as an instance in the meta-problem of finding for some problem $P$ in a class class $\mathcal P$, a machine, or the optimal machine (according to some criterion) that solves $P$".

  The meta-problem $\mathcal P$ is: Given a problem $P\in \mathcal P$, find a (Turing) machine that solves $P$, optimized for some resource constraints $C(P)$.

We could turn the set of problems $\mathcal P$ into a single problem $\tilde {\mathcal P}$, where the specification of which $P\in \mathcal P$ we want to solve, is defined within the information describing the instances of $\tilde {\mathcal P}$. However, an efficient machine $\tilde M$ that solves $\tilde {\mathcal P}$, can not necessarily be used to solve the meta-problem $\mathcal P$, since $\tilde M$ might not make use of specific possible optimizations for problems $P\in \mathcal P$. For example. the solution to some specific problem $P_i\in \mathcal P$ might be simply to always output $0$, in which case the solution to $\mathcal P$ for instance $P_i$, is a $C(1)$ complexity machine $M_i$ that ignores input and outputs $0$. But $\tilde M$ might instead do all kinds of complex computations, that still are below the worst-case bound for all problems in $\mathcal P$, but don't make use of this specific feature of the instance $P_i$.

Hence it may be that some problem $P$ has very low computational-complexity, but high "meta-complexity" (i.e. for problems in the class of problems $\mathcal P$ that $P$ is a part of, it is hard to find an efficient algorithm).

Is there a theory akin to this type of "meta-complexity"?

The meta-problem $\mathcal P$ is: Given a problem $P\in \mathcal P$, find a (Turing) machine that solves $P$, optimized for some resource constraints $C(P)$.

It's undecidable* whether a given Turing machine even solves $P$, let alone whether it's optimal according to some criterion.  Since your problem isn't computable even without resource bounds, there isn't really any scope for complexity theory.

And how are you going to specify the problem $P$ anyway, except by giving some Turing machine?

* Off the top of my head, probably not even recursively enumerable.


How to split the array into two subarrays with the smallest sum difference? Given

An array of elements, all elements are positive (unsorted, but sorting is not a problem if required)

The objective:

To create two subarrays, so that abs(sum(array_1) - sum(array_2)) is the smallest possible

The order of elements in the subarrays and the amount of elements don't matter but all elements should be used
E.g.

Input: Starting Array = {5, 8, 13, 27, 14} Result: 3  - smallest possible
difference in sums

Explanation:

First subarray = {5, 13, 14}
Second subarray = {8, 27}
Difference in sums: abs((5+13+14)-(8+27)) = 3 = min

I have a guess that it's something connected to the binary search but I have no clue what is being "binary seached" and what to connect it to.

This problem is the optimization version of the partition problem, and if it was solvable efficiently, that would mean that $P = NP$. That means it is unlikely that there is a polynomial time solution to split an array in two.
There are exact solution algorithms described on the wikipedia page, and some of them are in pseudo-polynomial time.


Aggregate planning with inventory I am lost in formulating a mathematical model for my linear integer program. My problem is; how to include inventory and backlogging.

The following is given:

1100 units can be produced each month
Unit production cost = \$7
Inventory unit cost = \$2
Annual expense = \$10.000
Sales unit price \$12
We have given the demand for 12 month and need to plan for 12 month
If demand is not met in one month, it will be transferred to next month (backlogging)
All demand should be met in the end of the year
The sum of all demand = 12.345 unit

We want to maximize the profit

\begin{align}
\max \sum_{i=1}^{12} x_i 12 - 10.000-\sum_{i=1}^{12} x_i 7 - \sum_{i=1}^{12} y_i 2
\end{align}
where $x_i$ is the amount produced each month, for i=1,...,12 and $y_i$ is the amount of inventory each month. I have defined the following constraints:

\begin{align}
x_i \leq 1100 \\
\sum_{i=1}^{12} x_i = 12345
\end{align}

So if we have $d_i\geq x_i$ we backlog the demand, and if $x_i \geq d_i$ we put it in inventory.
\begin{align}
if: d_i \geq x_i : b_i = d_i-x_i+b_{i+1} \\
if: x_i \geq d_i : y_i = x_i - d_i + y_{i-1}
\end{align}
where $b_i$ is the amount backlogged and $d_i$ is the demand.

But this is not correct, since the inventory constraint should be smaller if we take some of it to meet the demand that exceeds the amount we can produce (if we have something backlogged), and if we have some inventory, then we don't need to backlog it. I really hope that someone can help me formulate it correctly.

Your objective-function seems to only concern inventory (that's the only variable aspect of your problem). Indeed $\sum x_i =12345$ is constant, your profit, excluding inventory cost, will be $5$ times this in any case ($12 - 7$). Your objective can be written more simply as $\min \sum y_i$

$b_i=\max\{0, d_i-x_i-y_{i-1}\}$ and $y_i=\max\{0, x_i+y_{i-1}-d_i\}$ should be the additional constraints.
If production + previous inventory is not enough to satisfy demand, you get a backlog at period $i$ and inventory at $i$ is what remains after satisfying the current demand with the current production + previous inventory.

So $b_i\geq d_i-x_i-y_{i-1}$ and $y_i\geq x_i+y_{i-1}-d_i$ should do.

Since $y_i$ are to be minimized, these variables would equal their lowest feasible bound ($0$ or the difference above).

You will just pay $\$2$ for every unit you produce above demand on a given period. However, from an inventory management point of view, the cost of inventory in your model seems unusually simplistic. A more realistic cost for inventory would consider a holding/carrying cost (cost of holding one unit of inventory for one unit of time) and an ordering cost (cost of ordering raw material or components). The difficulty of inventory problems is typically determining when and how much to order to find the best trade-off between these two costs.

PS. It may make sense at the aggregate level, and intermediate-planning time horizon, to make such a simplification regarding inventory costs. However, aggregate planning and inventory management are two strategic problems in their own rights, over two different time-horizons. They cannot be easily solved by one simple, integrated model (mostly because of different levels of uncertainty in demand over the two time-horizons and at the aggregate vs individual level).


How is the definition of monads in category theory equivalent to the definition in functional programming? In Haskell, Monad is a class of type constructors which act on types that have the following functions implemented:

(>>=)  :: m a -> (a -> m b) -> m b
(>>)   :: m a ->       m b  -> m b
return ::   a               -> m a

and they satisfy the following "laws:"

return a >>= f      = f a
m        >>= return = m
(m >>= f) >>= g = m >>= m >>= (\x -> f x >>= g)

I understand why a type with these functions implemented with those constraints is useful, because I've used them. But to be completely honest, I'm interested in pure mathematics over programming, so I want to understand the category theoretic origins of monads.

Monads in category theory seem very different, they are ordered triples $\langle T, \mu, \nu\rangle$. Where $T$ is an endofunctor on a given category $C$, $\mu : 1_C \rightarrow T$ is a natural transformation as is $\nu : T\circ T \rightarrow T$ such that they all satisfy conditions reminiscent of the one's for Haskell monads. It seems like return, which I understand to be the type constructor for an instance of monad, is the endofunctor $T$.

In essence I want to understand which functions are which natural transformations, and why, but I also want to understand why return is an endofunctor, acting on a category, even though it seems like most types in Haskell are treated as objects.

I was once watching Bartosz Milewski lecture and he said that monads can be thought of as "monoids on the category of endofunctors." I stopped watching because I didn't know what monoids were at the time. But now when I think "monoid on the category of endofunctors" I think "The set of endofunctors on a category under composition." But I don't see how an object like this could relate to the definition of a monad, so if someone could explain that as well it would be greatly appreciated.

The Haskell monads are known as Kleisli triples in mathematics.  I am guessing you're coming from the Haskell land, so let me just put down the translations between the two formulations in Haskell (I define everything from scratch on purpose and avoid clashes with standard notation):

{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE FlexibleInstances #-}

class MyMonad t where
  fun :: (a -> b) -> (t a -> t b) -- functorial action, known as fmap
  eta :: a -> t a
  mu :: t (t a) -> t a

class KleisliTriple t where
  ret :: a -> t a
  (>>==) :: t a -> (a -> t b) -> t b

instance KleisliTriple t => MyMonad t where
  fun f x = (x >>== (ret . f))
  mu x = (x >>== id)
  eta = ret

instance MyMonad t => KleisliTriple t where
  ret = eta
  (>>==) x f = mu (fun f x)

There's a bunch of equations to be verified, but they all work out, which is not to say that you should trust me or anyone else, work them out, it's a good exercise. Actually, you should try to reconstruct things by yourself. Take the code above and delete the two instances. Then try to reconstruct their definitions.

As for your question about monads being monoids in the endofunctor category, you'll just have to unfold all the definitions in the privacy of your own mind. I can give you a roadmap, but until you pick up pencil and paper and go through it all by yourself, it's not going to click.

Recall that a monoid is given by a set $T$, a multiplication operation $\mu : T \times T \to T$, and an element $\eta \in T$ such that

$\mu (x, \eta) = x$
$\mu (\eta, x) = x$
$\mu (\mu (x, y), z) = \mu (x, \mu (y, z))$

$\newcommand{\CC}{\mathcal{C}}$
$\newcommand{\pair}[1]{\langle #1 \rangle}$
This can be generalized as follows. Consider a monoidal category $\mathcal{C}$. It has a tensor product $\otimes$ which behaves a little like ordinary binary products, and it has a special object $I$ which is a unit for the tensor. A monoid object in the monoidal category $\CC$ is given by the following data:

an object $T \in \CC$
an arrow $\mu : T \otimes T \to T$
an arrow $\eta : I \to T$

subject to the laws that correspond to the three laws above. I am not going to reproduce the laws here, you can find them here.

If we take $\CC = \mathsf{Set}$, $A \otimes B = A \times B$, and $I = 1$ then we recover the usual notion of monoid.

Now let $\CC$ be any category (no monoidal structure required). The functor category $\CC^\CC$ is monoidal if we take the tensor to be composition of functors $F \otimes G = F \circ G$, and the unit the identity functor $I = \mathsf{Id}_{\CC}$. What is a monoid object in $\CC^\CC$? It is given by the following data:

a functor $T : \CC \to \CC$
a natural transformation $\mu : T \circ T \to T$
a natural transformation $\eta : \mathsf{Id} \to T$

subject to some laws. When we unfold those laws we get, you guessed it, precisely the laws for a monad.


Thread - contention vs race The terms contention and race are used interchangeably when it comes to thread's state(at critical section). Are they same?

These are two distinct phenomena.   Contention refers to the fact that when thread $A$ has accessed a resource $B$ needs to wait until $A$ frees it.

Race refers to the fact when both threads $A$ and $B$ want to secure access to a resource.  The fastest will secure it and thus lead to contention.


Proving that the set of deciders is not Turing-recognizable Let $A$ be the language consisting of descriptions of Turing machines $\{M_1, M_2, \dots \}$, where each $M_i$ is a decider. Prove that $A$ is not Turing-recognizable.

Then suppose $A$ is Turing-recognizable and suppose $s = \{s_1, s_2, \dots \}$ is a set of all possible binary strings. Then I construct decider $D$ as follows. On input $w$, if $w$ is not equal to binary string, then reject. Else, $w$ is a binary string that is equal to $s_i$ for some $i$. Use the enumerator $E$ to print the $i$-th output which is $M_i$. If $M_i$ accepts $s_i$, $D$ is going to reject $s_i$. Otherwise, accept $s_i$.

But in the last step, what happens when $M_i$ doesn't have defined transition over the alphabet $\{0,1\}$? Does $M_i$ immediately enter a reject state? What should I argue?

The basic idea of the proof is to come up with a Turing machine which doesn't belong to the enumeration, hence contradicting the claim that deciders can be enumerated. To this end, we use diagonalization – for each potential machine in the enumerate, we ensure that there is at least one input on which the diagonalizing machine has a different behavior.

If the diagonalizing machine $D$ has alphabet $\Sigma$, then we already know that any machine in the enumeration with a different alphabet cannot be $D$. Therefore $D$ doesn't care much about these machines. What $D$ has to ensure is that for every machine $M_i$ with alphabet $\Sigma$ there is an input $x_i$ such that $D(x_i) \neq M_i(x_i)$.


Undecidability and Unrecognizability of Language with two Turing Machines I've been working on undecidability proofs and I found this question in the practice problems for the textbook "An Introduction to Automata Theory." I know that we start by contradicting the statement, and assuming that Language1 is decidable, so that there is a decider D which decides Language1. Then we construct a Turing Machine which produces a contradictory result. However, I'm not sure how to do this! Can anyone help me formalize this? The question is:
Consider the following language called Language1:
Language1 = {(⟨M1⟩, ⟨M2⟩) | L(M1) = {⟨M2⟩} and L(M2) = {⟨M1⟩}} .
i.  Prove that Language1 is undecidable.
ii. Prove that Language1 is unrecognizable.

You are going to want to use a many-one reduction for this problem. Note that $ii \implies i$ so it is sufficient to prove statement $ii$. We know that the complement to the halting problem $$ \bar{H}=\{\langle M, w \rangle \mid M \text{ does not halt on }w\}$$ is not recursively enumerable. We can reduce $\bar{H}$ to $Language1$
$S$ = "
$\quad$on input $\langle M,w \rangle$
$\quad$construct $M_1$ = "
$\quad\quad$on input $x$
$\quad\quad$if $x\neq $<$M_2$>, $Reject$
$\quad\quad$run $M$ on $w$
$\quad\quad$$Accept$ "
$\quad$construct $M_2$ = "
$\quad\quad$on input $x$
$\quad\quad$if $x\neq $<$M_1$>, $Reject$
$\quad\quad$run $M$ on $w$
$\quad\quad$$Accept$ "
$\quad$Output $\langle M_1, M_2 \rangle$ "
Notice that if $M$ does not halt on $w$, then $M_1$ accepts string $\langle M_2 \rangle$ and $M_2$ accepts string $\langle M_1 \rangle$, and both reject all other strings, that is $L(M_1)=\{\langle M_2 \rangle \}$ and $L(M_2) = \{\langle M_1 \rangle \}$. On the other hand if $M$ does halt on $w$, $L(M_1)=L(M_2)=\emptyset$. Then $\bar{H} \leq_m Language1$, since $\bar{H}$ is not recursively enumerable, neither is $Language1$.


Techniques for proving NP-completeness I've been reading Garey-Johnson book Computers and Intractability and I am focusin on Section 3.2, Techniques for proving NP-completeness. In these definitions and explanations nothing is formally defined. I was wondering, how would someone define those techniques formally?
The techniques mentioned are restriction, local replacement, and component design. Here are some relevant excerpts:

Proof by restriction is the simplest, and perhaps the most frequently applicable, of our three proof types. An NP-completeness proof by restriction for a given problem $\Pi \in \mathrm{NP}$ consists of simply showing that $\Pi$ contains a known NP-complete problem $\Pi'$ as a special case.
In proofs by local replacement, the transformations are sufficiently nontrivial to warrant spelling out in the standard proof format, but they still tend to be relatively uncomplicated. All we do is pick some aspect of the known NP-complete problem instance to make up a collection of basic units, and we obtain the corresponding instance of the target problem by replacing each basic unit, in a uniform way, with a different structure. The transformation from SAT to 3SAT is of this type.
Our last type of proof, and the one that tends to be the most complicated, is component design. The NP-completeness proofs for 3-DIMENSIONAL MATCHING, VERTEX COVER, and HAMILTONIAN CIRCUIT are typical examples of this type of proof. The basic idea is to use the constituents of the target problem instance to design certain "components" that can be combined to "realize" instances of the known NP-complete problem.

What exactly are those "basic units" and "components"?
I was trying to find some literature about those strict and formal definitions, but couldn't find any.
For restriction, can it be defined as a bijection from instance of one problem to another?

A basic misconception about mathematics is that it is a purely formal game. Promulgated by the formalist school, we are taught that all that matters in mathematics are formal proofs. Yet in practice, completely formal proofs almost never get written; and mathematical thought has a strong informal component. In order to get further in mathematics, you need to understand mathematical concepts intuitively rather than just formally. A formal proof might be the end result, but the thought process is more liberal.

Furthermore, mathematicians are interested in things beyond definitions, theorems and proofs: key insights are sometimes more interesting than the proof itself or the result being proved. The philosophy behind the proof uncovers a deep truth which reaches much beyond the proof itself.

Such is the case here. Garey and Johnson are explaining how they conceive of NP-completeness proofs. They describe three basic types:

Proofs by special case: If a special case of a problem is NP-hard, then so is the original problem. For example, if 3-coloring is NP-hard, then the $k$-coloring problem (with $k$ a parameter) is also NP-hard. This can in principle be modeled formally by using very weak reductions — in this case, to reduce 3-coloring to $k$-coloring, it might suffice to use an $\mathsf{NC^0}$-reduction.  In contrast to what you write, this is certainly not a bijection, since when $k > 3$, the correspondence is less direct.
Proofs by gadget reduction: These are proofs in which each "basic unit" of the original instance is replaced by a "gadget" in the new instance. For example, when reducing SAT to 3SAT, we replace a clause $\ell_1 \lor \cdots \lor \ell_n$ by the clauses $\ell_1 \lor \ell_2 \lor x_2$, $\lnot x_2 \lor \ell_3 \lor x_3$, ..., $\lnot x_{n-2} \lor \ell_{n-1} \lor \ell_n$.  Basic unit is a completely informal concept. It doesn't have a formal definition. It is supposed to help you conceptualize this kind of proof. Garey and Johnson give several examples, which might help you in constructing similar NP-hardness proofs.
Proofs by indirect gadget reduction: These are proofs in which several "components" of the original instance are replaced by several kinds of gadgets. For example, when reducing from SAT, we might have different gadgets representing variables and clauses, which are connected together in an appropriate way.  Once again, component is a completely informal concept. The difference between direct gadget reduction and indirect gadget reduction is significant in our mind, but cannot necessarily be described formally.

This description is useful since it covers many NP-hardness proofs, and even other hardness proofs such as PSPACE-hardness. Understanding these techniques is helpful for coming up with new hardness proofs. However, in no way is this case distinction supposed to be formal. It is just a mental aid.


Intuition behind Relativization I take course on Computational Complexity. My problem is I don't understand Relativization method. I tried to find a bit of intuition in many textbooks, unfortunately, so far with no success. I will appreciate if someone could shed the light on this topic so that I will be able to continue by myself.
Few following sentences are questions and my thoughts about relativization, they will help to navigate the discussion.

Very often relativization comes in comparison with diagonalization, which is a method that helps distinguish between countable set and uncountable set. It somehow comes from relativization that $P$ versus $NP$ question cannot be solved by diagonalization. I don't really see the idea why relativization show the useless of diagonalization, and if it's useless why is actually useless.

The idea behind oracle Turing machine $M^A$ at first is very clear. However, when it comes to $NP^A$ and $P^A$ the intuition disappears. Oracle is a blackbox that is designed for special language and answers the question whether the string on the input of the oracle is in the language in time 1. As I understood TM that contains an oracle is just make some auxiliary operations and ask the oracle. So the core of the TM is the oracle, everything else is less important. What's the difference between $P^A$ and $NP^A$, even thought oracle in both of them works in time 1.

The last  thing is the proving the existence of an oracle $B$ such that $P^B \neq NP^B$. I found the proof in several textbooks and in all of them the proof seems very vague. I tried to use "Introduction to complexity" by Sipser, Chapter9. Intractability, and didn't get the idea of construction of a list of all polynomial time oracle TMs $M_i$.

This is more or less everything what I know about relativization, I will appreciate if someonw would decide to share his/her thoughts on the topic.

Addendum: in one of the textbooks I found example of $NP^B$ language (Computational Complexity: A Modern Approach by Boaz Barak Sanjeev Arora. Theorem 3.7. Page 74). $U_B=\left \{ 1^n:some \space string \space of  \space length \space  n  \space is \space  in \space B\right \} $ it's unary language. I believe that (1,11,111,1111,...) are all in $U_B$. Author affirms that such a language is in $NP^B$ which is I cannot understand why, hence oracle for B can resolve everything in time 1. Why do we need nondeterministic TM with oracle. If it's not good example of $NP^B$ please put yours such that to approve the existence of $NP^B$.

You haven't really asked any question, but it seems like you don't know what $\rm{P}^A$ means and what $\rm{NP}^A$ means for a language $A$.  The class $\rm{NP}^A$ is simply all languages that are decidable in "NP time", given a turing machine with $A$ as an oracle.  This means a non-deterministic turing machine with access to $A$ which runs in polynomial time.  The $\rm{P}^A$ is the deterministic version.


universality of quantum gates Is there a difference between the set of quantum gates that are:

"universal" in the sense that you could calculate anything in BQP with a polynomial number of gates,
"universal" in the sense that you could approximate any arbitrary "gate" (unitary transformation) on a set of qubits?

And if so, what is the proper terminology to distinguish between these? (Or maybe it is exclusively used in only one of the above meanings?)

I believe these are at least different (but maybe the second implies the first). For example, it is my understanding that both of these sets:

Toffoli and Hadamard gates
CNOT gates plus all single qubit gates

are universal in the first sense, yet the first set cannot make phase shifts gates from the later. So Toffoli and Hadamard gates cannot be universal in the second sense.

Does any set meeting the second sense of universality automatically satisfy the first as well (or can some sets so inefficiently approximate calculations that they are not useful for modelling BQP)?

Yes, approximate-any-quantum-gate implies can-solve-BQP-efficiently.

Even if the cost of approximating gates is very high, you only need to approximate Hadamard, CNOT, and $Z^{1/4}$ operations to some constant fidelity before error correction starts to work. So although you may pay a large constant overhead to get "good enough", once you get there the extra overhead to achieve better and better precision becomes reasonable.


How to reconstruct the image from a neural network output? I am trying to use the genetic algorithm to optimise a multi-layered neural network for image classification (i am using a subset of the MNIST handwritten digit data set as my initial dataset, but eventually would like to make it more general).

my neural network is represented by connection weight matrices with inputs as the rows an outputs as the columns (so element (3, 4) is the weight of the connection between input 3 and output 4, etc) and have an extra column and row for the biases of the inputs/outputs

the system seems to work well, it takes an input vector, multiplies it by the first layer matrix, uses the sigmoid function to determine whether that neuron will fire or not, then uses the output vector of that as the input to multiply by the 2nd layer and so on to the final layer, and i am getting the results that i expect with test data that i know the expected output for.

i have an idea of how i will implement the genetic algorithm to search for the best solutions, but my problem is that im having a little bit of trouble understanding how neural networks can be used to reconstruct images so i can test for the error between the input image and the reconstruction to test each solution for fitness.

i understand that i need to first encode the image into a vector of pixels, and that that input needs to be passed through the network to the end layer, but i am not sure what that end data is supposed to represent..

the dataset i am using are images of 28*28 pixels, so the structure of my network is as follows (inspired by the Hinton paper here):

484 -> 1000 -> 500 -> 250 -> 30

so the output of the whole thing will be a vector 31 (30 neurons +1 for the bias column/row) elements long

how should i use this vector to reconstruct the image?

i read somewhere that to decode information from a neural network you need to multiply the output by the transpose of the transformation matrix, but that doesnt really make sense as (for example):

T = [ 1  2 ;
      3  4 ]

A = [ 5  6 ]

A * T = [ 23  34 ] = B

B * T' = [ 91  205 ] != A

clearly this is not a very good reconstruction of the original data..

can someone give an explanation as to how neural nets can be used to reconstruct data, and if possible, point me to some good resources on the subject?

You can't necessarily use the output of a neural network to reconstruct the image, like you want.  The output signals indicate how the neural network has classified the input image.  Beyond that, they don't necessarily have any interpretation as a representation of the original image.  There isn't necessarily any way to do what you want (to reconstruct the image given the output of the neural network), as this kind of neural network inherently throws away information.

Are you familiar with the notion of training "autoencoders"?  One way to train multi-layer neural networks is by building a series of auto-encoders: e.g., to construct the weights for the first layer, you train a 2-layer autoencoder, then throw away the second layer of the autoencoder and use the first layer of the autoencoder as the first layer of your neural network.  You repeatedly do this for each layer of your network.  Autoencoders do reconstruct the original input, so if you're training each layer of the neural network in this way, then you automatically have a way to reconstruct (an approximation to) the original input from the signals at any layer -- if you saved the entire autoencoder at each stage.  However, if your real end goal is to understand why an image was classified a certain way or debug your neural network, I expect this probably won't be helpful for that.

I'm not 100% sure what your real goal is.  You mention "test each solution for fitness", but I'm not sure what you meant by that.  However, my guess is that your best bet will be to figure out what your real goal is, and then ask about how to achieve that goal (which might not be by trying to reconstruct the original image).


Enumerating all set covers when knowing one set at least I have an index taking as keys values from the power set $P(S)$ of a set $S$, except for $\emptyset$ and $S$.

Then I have a query $Q=(s, k)$, where $s \in P(S) - \{\emptyset \cup S\}$ and $ 1 < k \le |S|$.

The result of the query is the set of covers $R$ of $S$; $\forall r \in R,  |r| \le k$.

So for instance, if $S = \{a, b, c, d\}$ and $Q=( \{a,b\}, 3 )$, $R$ should return all covers of $S$ formed by $\{a, b\}$ and $k = (3 - 1 = ) 2$ or less other subsets of $P(S) - \{\emptyset \cup S\}$, namely: $R = \{$
$$ \{a,b\} , \{c\} , \{d\}$$
$$ \{a,b\} , \{c, d\} $$
$$ \{a,b\} , \{a, c, d\} $$
$$ \{a,b\} , \{b, c, d\} $$
$\}$

I want to know if there is an efficient algorithm that can give me all of these combinations of covers.

In other words, I want to know if there is an efficient way to get all covers formed by at most $k$ elements, where I only know 1 element out of k.

The first step is to eliminate the known set $s$. The idea is to find all covers of $S \setminus s$ using at most $k-1$ sets, and then augment the solution by adding all subsets of $s$ to all sets in any given cover in all possible ways. Details omitted.

For the new problem, it is enough to find all covers of $S$ of size exactly $k$ which don't use $S$ or $\emptyset$. In fact, we can ignore these restrictions, and just drop the (relatively) few solutions using these sets. We will generate them ordered, incurring a factor of $k!$ in efficiency; I'm sure that can be avoided, but I'll leave the details for you. Consider the sets $S_1,\ldots,S_k$ in order, and suppose that they cover $a_1,\ldots,a_k$ "new" elements, that is $|S_1| = a_1$, $|S_2 \setminus S_1| = a_2$ and so on. Then $a_1 + \cdots + a_k = |S|$, and we can enumerate over all such sequences (including zeroes). For each sequence, we can enumerate over the new elements themselves. Finally, we enumerate over all possible ways of adding "old" elements to sets, for example $S_3$ could additionally to $a_3$ new elements contain any subset of $S_1 \cup S_2$.


Designing a DFA that accepts strings such that nth character from last satisfies condition This is a homework question, so I am only looking for hints.

I got a question in an assignment which states :

  Design a DFA that accepts strings having 1 as the 4th character from the end, on the alphabet {0,1}

I have been at this for a few hours now, and I think that designing such a DFA is not possible. However, I am not sure how to move forward in this direction to write up a somewhat formal proof.

So, what should I try to do to prove or disprove my hypothesis?

Hint: Your language can be described by the regular expression $\{0,1\}^*1\{0,1\}^3$.

Another hint: Your DFA can remember the last $4$ characters (and maintain that information). You will also need states to handle the case in which less than $4$ characters have been seen so far.


What's the possibility of random guessing a youtube's video ID Let's say i make a program that produces an eleven character long ID like youtube does and tries to find a valid video in youtube. What's the actual possibility that it's going to produce a valid ID corresponding to a real video and also an unlisted one??

Each YouTube id consists of 11 characters denoted by $v = [v_1, ··· ,
v_{11}]$.
  The first $10$ characters of a valid id contain any of the characters
  in $S = \{0 − 9,\_, −, A − Z, a − z\}$, i.e., $v_i ∈ S (i =
1, ··· , 10)$. The last (11-th) character $v_{11}$ only comes from $T =
\{0, 4, 8, A, E, I,M, Q, U, Y, c, g, k, o, s, w\}$, namely, $v_{11} \in T 1$.
  The size of video id space is, therefore, $64^{10}\cdot16$.

  We also observe that YouTube video ids are not generated in any sequence. Instead,
  YouTube picks an unused random id from this pool for each new
  video that is uploaded.

  Source: http://conferences.sigcomm.org/imc/2011/docs/p371.pdf

For instance, they show that YouTube video is randomly generated from the id
space and that the entire YouTube id space can be represented as $S = S^{10} × T$, where:

$S = \{0−9,\_, −, A−Z, a−z\}$
$T = \{0, 4, 8, A, E, I,M,Q, U, Y, c, g, k, o, s, w\}$.

Their estimation of the total number of youtube videos is $502\cdot10^6$.

Given these 2 information (video id space and estimation of the total number of videos) you can deduce the probability that, given an id of $11$ characters in $S^{10} × T$, it corresponds to the id of a valid video.


A variant of the Assignment Problem In my variant of the assignment problem I have a set $A$ of agents and a set (of possibly different cardinality) $T$ of tasks. Each agent needs to be assigned exactly $n$ or $n+1$ tasks, and each task needs to be assigned to exactly $m$ or $m+1$ agents.

It is guaranteed this this is possible: the segment $\left[ |A|n, |A|(n+1) \right]$ intersects the segment $\left[ |B|m, |B|(m+1) \right]$.

Each agent-task combination yields a profit, and I want to maximize the profit.

Is this a special case of one of the known problems? How can this be solved? If not practical for n=100,000, what are good approximations and what is their complexity?

 Not a comp.scientist, but have done the basic research. Please excuse me if I've overlooked anything obvious.

This can be formulated as an instance of min-cost (or in this case, max-profit) flow.

Set up a network as follows. There will be four layers.

The first layer is a single node we call the source. The next layer consists of a node for each agent. The next layer has a node for each task. The final layer is one node we call the sink. For each edge, we give a capacity and a profit. The min-cost flow algorithm can be used to find the flow through this graph that produces the greatest profit.

For each agent, we create two edges connecting the source to that agent, one having capacity $n$ and large profit; the other having capacity 1 and profit 0.

We connect each task to the sink with two edges, one having capacity $m$ and large profit; the other having capacity 1 and profit 0.

We connect every agent to every task, with an edge having capacity 1 and profit given by the agent-task combination.

We now use a min-cost flow algorithm to find the optimum flow. Because the min-cost flow problem has an integrality property, the flow on each agent-task edge will either be 0 or 1. This gives the assignment of the agents to their tasks.

Because the profit on the source-agent edges with capacity $n$ is large, the optimal solution will always use these, ensuring that every agent has at least $n$ tasks. Because the other source-agent edge has capacity 1 (and profit 0), each agent can have at most $n+1$ tasks. Similarly, each task is assigned to either $m$ or $m+1$ agents.

The min-cost flow algorithm won't be practical if each agent needs $100,000$ tasks, though. Is that really what you meant by $n=100,000$? How many tasks and how many agents?


Finding the closest visible vertex among line segments Given a set $S$ of line segments (possibly sharing endpoints) and a query point $q$, how fast can we find the closest visible endpoint from $q$? If $p$ is the closest visible endpoint to $q$, then, in this case, it means that the line segment $pq$ does not intersect with any other line segment in $S$.

I am trying to implement an efficient algorithm in CGAL. I have explored the nearest-neighbor and visibility structures from CGAL but could not conclude anything.

I only noticed after posting that my first answer does not directly address your
specific question. So now my answer is in two parts.

(1) As suggested by @HEKTO, to find the closest segment,
you could first compute the Voronoi diagram:
CGAL 2D Segment Voronoi Diagrams.
Then next you need to perform point location within the (non-rectilinear) cells of the diagram.
That is also discussed, using "the segment Voronoi diagram hierarchy, a data structure suitable for fast nearest neighbor queries..."

CGAL figure.

(2) You specifically ask for the closest segment endpoint, which is not necessarily an endpoint of the closest segment:

Point $x$ is closer to segments $1,2,3,4$ than to the closest endpoint $y$.

For this you might need to look at
"visibility constrained Voronoi diagrams":

  Aurenhammer, Franz, Bing Su, Y-F. Xu, and Binhai Zhu. "A note on visibility-constrained Voronoi diagrams." Discrete applied mathematics 174 (2014): 52-56.
  Elsevier link.

I haven't studied this paper enough to be certain it solves your problem.
And perhaps there is a way to efficiently move from the closest segment to
the closest segment endpoint.


Register Machine code for Fibonacci Numbers I am not sure whether this is the right place to ask this question.

I would like to write a register machine code which when given an input of n in register
1, returns (also in register 1) the nth Fibonacci number. The Fibonacci numbers are
0 (the 0th), 1 (the 1st), 1 = 0 + 1 (the 2nd), etc.

I tried to write few lines of the codes, but unable to do the recursive property of Fibonacci sequence. Here is my code:

Let A, B, C be registers.

(-A; 2,-)
(+C; 1)
(-C; 4,-)
(+B; 5)
(+A; 3)

I know that the fifth line is wrong but have no idea how to fix it. And I want to code to be as simple as possible (i.e. with fewest instructions). Thanks in advance.

Here is some code in C, which you can "compile" into your assembly language:

int x = 0, y = 1, z;
while (n--) {
  z = x;
  x = y;
  y += z;
}
return x;

After $n$ iterations of the loop, $x = F_n$ and $y = F_{n+1}$.


Vertex cover problem with 2-element vertices Let $G = (W, E)$ be an undirected graph, where $W = \{(v_i,v_j) \in V \times V : v_i > v_j\}$ and $E$ is a set of $2$-element subsets of $W$ such that, given two edges $e_1 = (w_1, w_2)$ and $e_2 = (w_1, w_3)$, $(w_2, w_3) \in E$ necessarily if there exists some $v$ belonging to $w_1$, $w_2$ and $w_3$. (For example, if $((v_1, v_2), (v_1, v_3)) \in E$ and $((v_1, v_2), (v_1, v_4)) \in E$, then $((v_1, v_3), (v_1, v_4)) \in E$.)

In such a scenario, we want to remove the minimum number of vertices in $W$ to disconnect the graph, taking into consideration that whenever we remove a vertex $w = (v_1, v_2)$, the rest of the vertices containing $v_1$ or $v_2$ must be removed as well.

My question is whether this is actually the vertex cover problem in disguise or, somehow, the restrictions applied above make it easier or more difficult to solve it.

As an example, consider the following graph, where it's clear that removing $v_2$, $v_3$ or $v_4$ leads to the disconnection of the majority of vertices in $W$.

Assuming you want the resulting graph to be disjoint (contain only isolated vertices), then your problem is as hard as the vertex cover problem.  There is a simple reduction.

Let $G^*=(V^*,E^*)$ be an undirected graph, where $V^* = \{v_1,v_2,\dots,v_n\}$.  Define $V = \{v_1,\dots,v_{2n}\}$, and define $E$ by creating edges $((v_i,v_{i+n}),(v_j,v_{j+n}))$ for each $i,j$ such that $(v_i,v_j) \in E^*$.  Note that this automatically satisfies all of your constraints, as there are no pair of edges $(w_1,w_2)$, $(w_1,w_3)$ in $E$ that share a common $v_i$.  Thus, given $G^*$, we can define a new graph $G$ of your form.

Any way to remove vertices in $G$ corresponds immediately to a way to remove vertices in $G^*$, and vice versa.  Moreover, the minimum number of vertices you can remove from $G$ to leave every vertex isolated is equal to the minimum number of vertices you can remove from $G^*$ to leave every vertex isolated.  The latter is exactly the vertex cover problem.  Therefore, we've shown a reduction from vertex cover to your problem: if we could solve your problem for $G$, we could solve vertex cover for $G^*$.


Find $\epsilon'$ s.t $L_\epsilon$ is $\mathsf{NP}$-hard for any $\epsilon<\epsilon'$ Let $L_\epsilon$ be the language of all $2$-CNF formulas $\varphi$, such that at least $(\frac{1}{2}+\epsilon)$ of $\varphi$'s clauses can be satisfied.

I need to prove that there exists $\epsilon'$ s.t $L_\epsilon$ is $\mathsf{NP}$-hard for any $\epsilon<\epsilon'$.

We know that $\text{Max}2\text{Sat}$ can be approximate to $\frac{55}{56}$ precent of the clauses from a $\text{Max}3\text{Sat}$ reduction. How should I solve this one?

In his famous paper, Håstad shows that it is NP-hard to approximate MAX2SAT better than $21/22$. This likely means that is is NP-hard to distinguish instances which are $\leq \alpha$ satisfiable and instances which are $\geq (22/21) \alpha$ satisfiable, for some $\alpha \geq 1/2$. Now imagine padding an instance so that it becomes a $p$-fraction of a new instance, the rest of which is exactly $1/2$-satisfiable (say it consists of groups of clauses of the form $a \land \lnot a$). The numbers now become $1/2 + p (\alpha - 1/2)$ and $1/2 + p((22/21)\alpha - 1/2)$. The latter number can be made as close to $1/2$ as we want.


Drawing a DFA for a language/regular expression how would you draw a DFA for the language over {a,b,c} of all words where every occurrence of b is preceded and followed by a.

My thinking of this is that the regular expression for this is a* c* (aba)* a* c* although I am not too sure. Any help would be appreciated thanks

So, first, your regular expression

$$a^* c^* (aba)^* a^* c^*$$

is not correct. We need to give it the capacity to deal with many $aba$s, any of which can be surrounded by $a$s and $c$s. So, that would give us

$$(a^* c^* (aba)^* a^* c^*)^*$$

Of course, we still have a few more problems. First, we might have no $b$s, which could still fit into the language you've specified. We can fix that by pulling out the first set from our larger expression:

$$a^* c^* ((aba)^* a^* c^*)^*$$

We can't know the order of the $a$s and $c$s, so we need to use the union operator, which behaves essentially like an or in regexes:

$$(a\cup c)^* ((aba)^* (a\cup c)^*)^*$$

We're not done yet, as Thumbnail pointed out, we still need to allow $ababa$, so this gives us Thumbnail's structure, which allows any number of $baa^*$s after an $a$.

$$(a \cup c \cup a (b a a^*)^*)^*$$

Now, as for your DFA, begin with a start state, and let it accept the empty string:

Clearly, we can have as many $c$s as we want without changing our accept state:

$b$s are a little different, because they may be the start of an $aba$ pattern.  This means that we need a new state to encode that we've encountered n $a$:

Now, if we arrive at a $c$, then our $a$ was not the start of an $aba$, and we can return home.  If we get another $a$, then we may still be at the start of an $aba$ set:

Finally, we might exit with a $b$, followed by an $a$, which could be the beginning of a new set:

At this point, we are done.  What we did not put in were the transitions to the garbage state, which are implicitly anything that wasn't yet defined.  If we were to put them all in, we would have a graph that looks more like this:

Notice that one we get to state $g$, there is no way out, and no way to reach an accept state.


What is the asymptotic runtime of the best known TSP solving algorithm? I always thought that TSP currently requires time exponential in the number of cities to solve.

  How, then, has Concorde optimally solved a TSP instance with
  85,900 cities?!?

Is this a typo? Is the base of the exponential 1.0000000000000001 or similar? Was it an instance specifically constructed to be solvable easily? What is the asymptotic runtime of the best known TSP solving algorithm?

The worst case running time of Concorde or any other known method is exponential in the size of the input. However, sometimes heuristics or other pruning techniques are effective and you are able to solve some, even large, instances pretty quickly. You should define exactly what you mean by TSP as there are many variants, and many algorithms with different worst case run times.

See the accepted answer in this question on CSTheory to see a list of algorithms.


Is at least one of L and L complement Turing recognizable Let the alphabet be {0,1}. Is it true that for every language over this alphabet at least
one of L and L_complement is Turing-recognizable

No, try to think of a counting argument (i.e, the size of each class) in the following way:
There are $2^{\aleph_0}$ possible words in the language, hence $2^{2^{\aleph_0}}$ total languages. However, the number of turing machines is bounded by the total possible number of words (since you can encode a TM as a string), hence there are at most $2^{\aleph_0}$ TMs, and thus we get that $|RE| \le 2^{\aleph_0}$. Follow the definition of $co-RE$, to see that the same argument gives $|co-RE| \le 2^{\aleph_0}$ as well. Thus, $|RE\cup co-RE| \le 2^{\aleph_0}$ as well.
Thus $|RE\cup co-RE|\le 2^{\aleph_0}<2^{2^{\aleph_0}}=|P(\{0,1\}^*)|$, and thus there must be some $L\in P(\{0,1\}^*)\setminus (RE\cup co-RE)$ as you asked.
In fact, this shows there are waaaaay more languages that aren't RE or co-RE than languages that are.


Comparison of running times: Determine largest n to run in given time I am browsing the "Introduction to Algorithms" book by Thomas H. Cormen. One of the very first tasks in the introduction chapter gives a couple of running time functions like

f(n)=lg n
f(n)=n!
f(n)=2^n

and the following durations: 1second, 1minute, 1hour, 1 day, 1month, 1year, 1century

The f(n) functions describe the time taken in microseconds and for each duration I should determine the largest n which still runs in the given time.

Quite easy for potency and faculty, but I am stuck at the logarithm (lg n). Even for one second n gets so sooo huge and later even wolframalpha does not calculate it for 1 day. It is just too huge.

Or ist it wrong to try to calcualte these equations?

1.000.000 = lg n [for 1 second]
60.000.000 = lg n [for 1 minute]

...

That's the answer then. "It's so huge, it can't be written down at all".

If an algorithm takes ln (n) microseconds, where n is the problem size, then there is no way to represent a problem that cannot be solved within a second.

Your equation is absolutely fine, and the solution would be for example $n = e^{1,000,000}$. It's just a very, very large number.

BTW. It's a very useful thing to look at. For example, if your computer can solve a problem of size n in an hour, you would want to know "what size of problem could I solve in an hour if I bought a computer that is twice as fast, or ten times faster".


Method for measuring the 'similarity' between FSA grammars? I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic representation of a music stream (e.g., MIDI data). The music stream has been preprocessed to divide each song into unlabeled 'segments'. An FSA is generated for each segment in each song: if I have $n$ songs, each divided into $y$ segments, I will have $n \cdot y$ separate FSAs.

I would like to compare each segment's FSA with the other FSAs in my corpus. The ultimate goal would be to do clustering within a similarity space and come up with 'classes' of segments according to how similar their construction metrics are. Thus, of particular interest are the grammars that each FSA defines (corresponding roughly certain components of the musical content in the segment). Are there techniques that might be good for comparing something like this? KL-divergence comes to mind (e.g., using it compare the distribution over strings associated with a given FSA), although there may be better/more efficient techniques?

Also, apologies if this question is either (1) trivially easy or (2) indicative of some deeper misunderstanding or (3) answered elsewhere. I'm a real nub, folks!

you might have more luck from another angle & looking into research into music piece similarity, there are researchers studying that, and while your approach can work, there are other approaches. there are large databases that look at many elements/ criteria such as lyrics, genre etc. eg Music genome project.

sometimes when theres a wide variety of algorithms a survey can help. here are two surveys on graph matching.

Matching Structure and Semantics: A Survey on Graph-Based Pattern Matching
Brian Gallagher
Graph Similarity and Matching / Zager


Meaning of Merge[A[1,..n], m] I was reading JeffE's (Prof. Jeffrey Erickson) notes on solving recurrences, and he used Merge[A[1,...n], m] where A is an array(I think) and m is an integer. What does this mean? I thought Merge sort took two arrays as input. He includes psuedo code, but I can't decipher what is means. What is it doing?

Thank you for any help.

Link:
http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

$Merge[A[1,...n], m]$ means merge arrays $A[1..m]$ and $A[m+1..n]$.

They are recursively sorted before merging by

MergeSort(A[1 .. m])
MergeSort(A[m + 1 .. n])


Application of floors and ceilings to the time complexity of loop with constant index increment Consider the number of times that 'statement' runs in the following examples. I am confused as to the applications of floors and ceilings when calculating the loop complexity.
for (int i = 1; i < m; i += a) {
   statement;
}

In this example, I count the loop by establishing a bijection between the loop iteration and the values of i that do not break the termination condition, values identified by sequence 1, 1 + a, 1 + 2a, ..., 1 + (n-1)a.
Solving for the termination condition:
1 + (n-1)a = m => n - 1 = (m - 1)/a, since the only the first n - 1 terms in the sequence are counting the number of iterations.
The number of iterations being an integer becomes floor((m-1)/a), in my understanding. However, in many solutions I see that the number of iterations is just m/a -- the discussion on floors and ceilings is neglected.
How do I get from the ceiling notation to the much simpler looking m/a figure?

You are technically right, and if you want an exact value of the number of loop iterations, you can't forget the floor.
However, when doing asymptotical time complexity analysis, you can often toss terms that are negligible in front of other terms. In this case, $\frac{m}{a} - \left\lfloor\frac{m-1}{a}\right\rfloor \leq 1+\frac{1}{a}$ which is negligible in front of $\frac{m}{a}$ (for $m$ big enough).
See here for more details.


Is Karnaugh Map possible for Maxterms? I read about Minterms i.e. sums of products, simplification using
Karnaugh Graph. Can this graph be used for Maxterms, i.e. products
of sums, as well? If yes, then how?

If not, then is there some other similar way to use, for simplification of Maxterms?  I know, one can always convert Maxterms to Minterms and then use K-Map. I mam looking for some direct way.

Yes you can do it directly on the K-map. In order to get a minimal product of maxterms (aka product-of-sum [POS], aka conjunctive-normal-form [CNF]), you simply circle/unify the zeros that appear in the K-map instead of the ones. (It doesn't matter how you got the K-map, it can be from any representaiton of the function, it's just a table of the function's output after all). You can also build the K-map from a (not necessarily minimal) POS by adding a zero the K-map for every maxterm (with the remaining squares being ones.) This should be said to varying extents in most textbooks, e.g.

Digital Fundamentals by Thomas L. Floyd, 9th edition, pp. 221-224 has a very detailed example. (I'm guessing the latest, 11th edition has it too, but I haven't checked.)
The Electronics Handbook, Second Edition edited by Jerry C. Whitake, pp. 55-57 has an example too, but this isn't as detailed.
Introduction to Digital Electronics by Reid and Dueck, p. 114 also has an example.
Digital Logic Techniques, 3rd Edition by John Stonham, p. 43.

That this approach is correct comes from De Morgan's laws and double negation. It's the same as if you flipped all zeros and ones in the K-map and SOP-minimized the negated function and then finally applied De Morgan to the result double-negating the function. This is explained on an example in

Principles of Modern Digital Design by P.K. Lala, p. 70.

and probably other textbooks as well.


In pipelining (at least, in MIPS), why is the incremented program counter address saved in the IF/ID pipeline register? In D. Paterson's book, Computer Organization and Design, Fifth Edition, there is a paragraph that says

  Instruction fetch: The top portion of Figure 4.36 shows the
  instruction being read from memory using the address in the PC and
  then being placed in the IF/ID pipeline register. The PC address is
  incremented by 4 and then written back into the PC to be ready for the
  next clock cycle. This incremented address is also saved in the IF/ID
  pipeline register in case it is needed later for an instruction, such
  as beq. The computer cannot know which type of instruction is being
  fetched, so it must prepare for any instruction, passing potentially
  needed information down the pipeline.

I'm trying to understand why an incremented address must be saved in the IF/ID pipeline register, at least in MIPS. I understand that it might be needed by some instruction somewhere later.

However, how does an instruction such as beq use the program counter value?

beq doesn't contain the destination address in the instruction, but an offset relative to the location of the instruction. For example "branch if equal to the instruction 12 words ahead of the branch instruction". You cannot execute such an instruction if you don't know what the address of the branch instruction was.


Simplifying a logic function using Boolean algebra Consider this Logic function : D = A B C + A B’ C + A’ B’ C + A B C’ + A’ B C’ + A B’ C’ I am trying to simplify it using Boolean algebra , I am stuck in this step : D= AB +B'C+ A’ B C’ + A B’ C’ So how do I continue simplifying it ?

I'm not sure how to simplify this equation from the point you've gotten to without backtracking (e.g., recognizing that AB implies ABC' + ABC). The way I would do it is, starting from the beginning:

D = ABC + AB’C + A’B’C + ABC’ + A’BC’ + AB’C’

If we rearrange this as follows:

D = ABC + ABC’ + AB’C + AB’C’ + A’B’C + A’BC’

Then you may notice that we have:

D = A(BC + BC' + B'C + B'C') + A’B’C + A’BC’

Simplifying for C, we get:

D = A(B + B') + A’B’C + A’BC’

Which of course is just:

D = A + A'B'C + A'BC'

Since we know that D is always true when A is true, this implies:

D = A + A'B'C + A'BC' + AB'C + ABC'

Which can be rearranged as:

D = A + (A' + A)B'C + (A' + A)BC'

Giving us the final result:

D = A + B'C + BC'

I'm sure there's a way to do this with De Morgan's law, but it's been a while since I've used any Boolean algebra and I couldn't be bothered to look it up.

Alternatively, you can draw out a truth table

D | A  B  C
------------
0 | 0  0  0
1 | 0  0  1
1 | 0  1  0
0 | 0  1  1
1 | 1  0  0
1 | 1  0  1
1 | 1  1  0
1 | 1  1  1

and recognize that D will always be true if A is true (A), and that if A is not true then D will be true when B'C or BC' (B'C + BC'), thus giving us D = A + B'C + BC'

Although the more "correct" way to do this via truth tables would be to use a Karnaugh map


Stretegy to find the min expected cost on a series graph with edge probability pi and search cost ci In a series graph, each edge $e_i$ exists with probability $p_i$. And if you want to examine the existence of edge $e_i$, it will cost you $c_i$. I want to test the connectivity between source $s$ and destination $d$ with the minimum expexted cost.

I have figured out that the expected cost can be caculated below if the edge detection sequence is $e_1, e_2, \cdots e_n$:

$$E(cost) = c_1 + p_1 * (c_2 + p_2 * (c_3 + p_3 * (\cdots (c_{n-1} + p_{n-1} * c_n)\cdots))))$$

So is there a stretegy or algorithm to find out the minimum expected cost and the edge detection sequence?

Suppose that you test the edges in order. The expected cost is thus
$$
\sum_{i=1}^n c_i \prod_{j=1}^{i-1} p_j.
$$
Now suppose that we switch the order of $k$ and $k+1$. The two relevant terms are
$$
c_k \prod_{j=1}^{k-1} p_j + c_{k+1} \prod_{j=1}^k p_j.
$$
After switching $k$ and $k+1$, these two terms become
$$
c_{k+1} \prod_{j=1}^{k-1} p_j + c_k p_{k+1} \prod_{j=1}^{k-1} p_j.
$$
Dividing by $\prod_{j=1}^{k-1} p_j$, these two expressions become
$$
c_k + p_k c_{k+1} \\
c_{k+1} + p_{k+1} c_k
$$
The switch leads to an improvement if
$$
c_k + p_k c_{k+1} > c_{k+1} + p_{k+1} c_k \\ \Longleftrightarrow \\
c_k (1-p_{k+1}) > (1-p_k) c_{k+1} \\ \Longleftrightarrow \\
\frac{c_k}{1-p_k} > \frac{c_{k+1}}{1-p_{k+1}}.
$$
This suggests testing the edges in increasing order of
$$
\frac{c_i}{1-p_i}.
$$


What is the complexity for the universality problem for a NFA with all states accepting? It is well known that the universality problem for NFA (deciding whether $L(A)=\Sigma^*$) is $PSPACE$-complete. However, what if every state of the NFA is known to be accepting? It seems to me that the problem is at most in $co$-$NP$, as a counterexample (unlike in the case of a general NFA) is polynomial (even linear) in the size of the input (the number of states). What is the complexity of this problem?

You problem is PSPACE-complete. I prove that it's PSPACE-hard by reducing universality of NFAs to universality of NFAs with all states accepting.

Let $A$ be a NFA. Add a new final state $q_\$$ to it and for every accepting state $q$, add a transition $q\overset{\$}{\to}q_\$$ where $\$$ is a fresh letter. For every letter $a\in \Sigma\sqcup \{\$\}$, also add a transition $q_\$\overset{a}{\to}q_\$$. And then make all states accepting. The new automaton accepts $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup L'$ for some $L'\subseteq \Sigma^*$.

Now, add some automaton (with all states final) that recognizes the language $\Sigma ^*$ (i.e. the language of words that don't contain $\$$) in parallel. The new automaton will recognize $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup (L' \cup \Sigma ^*)=L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup \Sigma ^*$.

Now, notice that we have $L(A)=\Sigma^*$ iff $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup \Sigma ^*=(\Sigma\sqcup\{\$\})^*$. I.e. the process I described is a reduction from universality of a NFA to universality of a NFA with all states accepting. Since the reduction is polynomial, your problem is PSPACE-hard.


How many number of different binary trees are possible for a given postorder (or preorder) traversal I came across the problem:

  What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A,B,C?

Now 3 being small number I was quick to draw all possible binary trees and come at the conclusion that there can be 5 such binary trees for given postorder.

   C        C      C     C       C
  / \      /      /       \       \
 A   B    B      B         B       B
         /        \       /         \
        A          A     A           A

Then I tried to do the same for 4 nodes postorder traversal A,B,C,D. We will need D at the root. Then all A,B,C can be in the right subtree of left subtree. So there will be $2\times 5$ such formations. Let us denote this as follows:

$\underbrace{1}_{\text{root}}:\underbrace{3}_{\text{#nodes in left subtree}}:\underbrace{0}_{\text{#nodes in right subtree}}  = \underbrace{5}_{\text{#tree arrangements}}$

$1:0:3=5$

Now there is another possibility that 2 nodes are in the left subtree and the 3rd one in the right subtree or vice versa. Then,

$1:2:1=2$

$1:1:2=2$

Total $= 14$

For 5 nodes postorder traversal A,B,C,D,E, I can get

$1:4:0=14$

$1:0:4=14$

$1:3:1=5$

$1:1:3=5$

$1:2:2=4$

Total $=42$

Though, I am able to figure out the number of binary trees required for these post orders, I am unable to come up with defining recurrence relation and any closed formula for number of binary trees possible for given post order traversal. Is such recurrence relation and closed formula possible?

Every binary tree (with the right number of nodes) has exactly one labelling that satisfies a given postorder labelling. So you need to find the number of binary trees. That is the famous Catalan number $C_n = \frac 1{n+1}{2n \choose n}$. Sequence A000108 in Sloane's OIES.

It has a nice recurrence, based on the fact that a tree with $n+1$ nodes has a root and the remaining nodes are distributed into two subtrees with $i$ and $n-i$ nodes respectively: $C_{n+1}=\sum_{i=0}^n C_i\,C_{n-i} $. Such a type of recurrence is called a convolution.

In fact, you have discovered this recurrence yourself! Here are your own numbers, in a slightly changed order:

$1:4:0=14 = 14 \cdot 1$

$1:3:1=5 = 5 \cdot 1$

$1:2:2=4 = 2 \cdot 2$

$1:1:3=5 = 1 \cdot 5$

$1:0:4=14 = 1 \cdot 14$


Algorithm to match timestamped events from two sources does a good known algorithm exists for this problem?

On input I have two series of timestamps "when the event was observed". Theoretically the recorded timestamps should be very well aligned.

Visualized ideal situation on two time lines "s" and "r" as recorded from the two devices:

but more likely they will not be so nicely aligned and there might be missing events from timeline s or r:

I am looking for algorithm to match events from "s" and "r" like this:

So that the result will be something like: (s1,r1); (s2,r2); (s3,null); (s4,r3);(null,r4)... Or something similar. Maybe with some "confidence" rating.

It feels like there should be some well known algorithm for this problem, but I am a bit out of my element here.

Thanks.

Here is a pragmatic approach:

Look for matching pairs.  Consider a pair $(s,r)$ (where $s$ is from the first device and $r$ from the second device) to be a match if their timestamps are very close, i.e., $|s-r| \le \epsilon$ for some small fixed value of $\epsilon$ that you choose in advance.  $\epsilon$ is a tolerance.  To find matching pairs, for each $s$, you look for a value $r$ in the range $[s-\epsilon,s+\epsilon]$.

You can quickly find all matching pairs by first sorting $s$ and $r$ individually, then doing a linear scan across them.
Count how many values don't have a match.  Use the number of values that don't have a match to derive a confidence score.  The more mismatches, the less confident you are.

There are a number of elaborations possible:

For instance, if you've found $n$ matching pairs $(s_1,r_1),\dots,(s_n,r_n)$, you can use $|s_1-r_1|+\dots+|s_n-r_n|$ as an additional confidence measure: the higher this is, the worse a match it is.  You could compute a weighted sum of $|s_1-r_1|+\dots+|s_n-r_n|$ and the number of mismatched pairs.
If you frequently find that many points can be matched to multiple other possible points (one $s$ has multiple $r_i$'s it could match to), you could try framing this as a bipartite graph matching problem.  Basically, you have a vertex for each sample point, and an edge between $s$ and $r$ if $|s-r|\le \epsilon$; now find a maximum matching in this bipartite graph, and that will give you a way to find the maximum number of matched pairs.  Then you can use the number of unmatched values as a confidence score.  You can also use some kind of search over a range of $\epsilon$ values, if it's not clear how to choose $\epsilon$ a priori.

However, this is probably overkill and unnecessary, if events are well-aligned (if the typical distance between two events from a same device is much larger than the typical alignment error in the timestamp for an event at one device vs the timestamp at the other device).  If events are well-aligned, simply choosing a suitable threshold $\epsilon$ and applying the simple approach at the top of my answer will probably suffice.
If you expect systematic clock skew, where one device's clock is a bit ahead of the other device's clock (by a constant), you could correct for this in a number of ways:

One simple pragmatic way is to look for a set of matching pairs $(s_1,r_1),\dots,(s_n,r_n)$ in a first pass (this first pass doesn't have to be perfect, so you could use a larger value of $\epsilon$).  Then, use the median of $s_1-r_1, \dots, s_n-r_n$ as your estimate of the clock skew; say the median is $\Delta$.  Now replace each $s_i$ with $s'_i=s_i-\Delta$.  Finally, do a second pass where you match the (corrected) $s'_i$'s to the $r_j$'s, maybe with a smaller value of $\epsilon$.  In practice this might work very well.
Alternatively, you could use RANSAC to fit a line $s=r+c$ to the data, where the constant $c$ is unknown.  Normally RANSAC is described as a way to fit a line $y=ax+c$ (in this setting, $s=ar+c$), but in your application, we can fix $a=1$ (assuming both clocks run at the same rate and we care only about clock skew) and then apply RANSAC methods to find the best fit line, i.e., to find the constant $c$ that provides the best fit.


How is deciding a problem not equivalent to finding a valid certificate for verification? Take a decision problem $Q$, which maps encoded instances of a problem, i.e., $\lbrace 0, 1 \rbrace \ast$ to the solution set $\lbrace 0, 1 \rbrace$.
Since $Q$ is in $NP$, there exists a verification algorithm $A$, which takes an input and a certificate, in that order, as arguments and maps those to $\lbrace 0, 1 \rbrace$, depending on whether there exists a certificate proving that the solution to the input is $1$.

If this presentation of what a verification algorithm does is correct, then it is unclear to me if, for a binary-encoded problem instance $x$,

$$Q(x) = 1 \iff \exists y (A(x, y) = 1).$$

It seems to me that if there is a certificate, this means that the decision for that input is affirmative, so that in theory, you could attach sufficient information to a certificate such that it characterizes a solution to the decision problem, iterate through the entire set of certificates and, once you have found one that satisfies $A(x, y) = 1$, you have also found a solution to the problem for the respective input.

Maybe someone could explain to me if that equivalency above is wrong and if so, why. I know the difference between a problem and the verification part, but then again, on some level I do not.Neither am I sure about anything else, so feel free to point out mistakes.

The problem is in the following excerpt:

  iterate through the entire set of certificates

There might be many possible certificates. For example, a SAT instance on $n$ variables has $2^n$ certificates. Iterating through all of them would take exponential time. Although processing each takes only polynomial time, processing all would take exponential time. This is the difference between verification and decision.

Your argument does show that if a problem is in nondeterministic time $T(n)$, then it is in deterministic time $\exp T(n)$. For example, $\mathsf{NP} \subseteq \mathsf{EXP}$.


Recover permutation from prefix sums, using segment trees? I encountered the following problem on Codeforces.

  An array of integers $p_1,p_2,…,p_n$ is called a permutation if it contains each number from 1 to n exactly once. For example, the following arrays are permutations: $[3,1,2],[1],[1,2,3,4,5]$ and $[4,3,1,2]$. The following arrays are not permutations: $[2],[1,1],[2,3,4]$.

  There is a hidden permutation of length $n$.

  For each index $i$, you are given $s_i$, which equals to the sum of all $p_j$ such that $j<i$ and $p_j<p_i$. In other words, $s_i$ is the sum of elements before the $i$-th element that are smaller than the $i$-th element.

  Your task is to restore the permutation.

How can I solve this problem using segment trees in $O(n\log n)$ time?

I tried to understand the solution on Codeforces but I could not understand it.  Their solution:

  Let us fill the array with numbers from 1 to $N$ in increasing order.

  1 will lie at the last index $i$ such that $s_i=0$. Find and remove this index $i$ from the array and for all indices greater than $i$, reduce their $s_i$ values by $1$. Repeat this process for numbers $2,3,\ldots,N$. In the $i$th turn, reduce the elements by $i$.

  To find the last index with value zero, we can use segment tree to get range minimum query with lazy propagation.

I do not understand what is stored in segment tree (like least number in the given range) and how the update is done in $O(\log n)$ time in this case.  Can you show me an example input and show me what happens in each iteration?

My attempt: I tried to solve this problem by making a segment tree where each node will contain the smallest number in the range corresponding to that node. But I was not able to solve the problem.

For example: Suppose I have sample input:

5
0 1 1 1 10

My segment tree will look like:

                           [1-5](0)
                          /        \
                      [1-2](0)      [3-5](1)
                    /      \         /      \
                [1-1](1) [2-2](1)   [3-4](1) [5-5](10)
                                   /       \
                              [3-3](1)      [4-4](1)

Value adjacent to each range is minimum value in its sub tree. I failed to solve using this approach since update will take $O(n)$ time.

The segment tree is useful in this problem because you need to maintain an array of values where the supported operations are: 1) decrementing all elements in a range by the same amount and 2) querying a range for its (rightmost) minimum-value location.

In this problem, the values maintained in the array are the sums $s_i$, that have to be adjusted as described by the solution.

In your example, the subsequent contents of the array will be as follows:

0 1 1 1 10 # we query range (1, 5) and obtain position 1 (rightmost minimum)
∞ 1 1 1 10 # we remove the value at position 1, by setting it to INFINITY
∞ 0 0 0 9  # we subtract 1 from all values to its right (range (2, 5))
∞ 0 0 0 9  # we query range (1, 5) and obtain position 4 (rightmost minimum)
∞ 0 0 ∞ 9  # we remove the value at position 4
∞ 0 0 ∞ 7  # we subtract 2 from all values to its right (range (5, 5))
∞ 0 0 ∞ 7  # we query range (1, 5) and obtain position 3 (rightmost minimum)
∞ 0 ∞ ∞ 7  # we remove the value at position 3
∞ 0 ∞ ∞ 4  # we subtract 3 from all values to its right
∞ 0 ∞ ∞ 4  # we query range (1, 5) and obtain position 2 (rightmost minimum)
∞ ∞ ∞ ∞ 4  # we remove the value at position 2
∞ ∞ ∞ ∞ 0  # we subtract 4 from all values to its right
∞ ∞ ∞ ∞ 0  # we query range (1, 5) and obtain position 5 (rightmost minimum)
∞ ∞ ∞ ∞ ∞  # we remove the value at position 5 and stop.

Since the sequence of minimum positions was P = [1, 4, 3, 2, 5], it means that in the hidden permutation number 1 is at position 1, number 2 is at position 4, and so on. Hence the hidden permutation is [1, 4, 3, 2, 5], the inverse of P (although in this case it's the same).


Algorithm for finding "mean center" of unweighted graph I have a large sparse unweighted undirected graph (20M vertices, 60M edges) and would like to find what I'm calling the "mean center" (the vertex w/ shortest mean distance to all other vertices. Does this already have a name?). I know of an $O(N^2)$ solution: Starting at every vertex: BFS to calculate the mean distance to all other vertices, choose the minimum. But $N^2$ is too slow for a graph this size, is there any way to calculate the "mean center" in faster than $N^2$ time? Are there any good approximation algorithms? Or more efficient algorithms which find some similar "center" of a graph?

Another heuristic idea: Find a long shortest path, and pick the vertex halfway along it.

Pick a vertex and run BFS from it. For some small $k$, take the $k$ furthest vertices from the original vertex that the BFS determines, and repeat the process on each of them, keeping the $k$ overall furthest vertices each time. Repeat a few times.

If the graph is a tree, this is in fact guaranteed to find the longest path with $k=1$ after the second iteration! For a general graph, I don't know of any such guarantee -- but you are likely to find a reasonably long shortest path.

Once you have a sufficiently long path, pick the vertex halfway along it. (This is uniquely determined if the path has an odd number of vertices; if it has an even number, you could choose arbitrarily, or run BFS again from the middle two vertices, and pick whichever scores higher.)


What can be said about Θ-classes in m and n if we know that m < n? A function in $\Theta(m + n^2)$ and $0 < m < n^2$, is in $\Theta(n^2)$. Does a function in $\Theta(m\log n)$ and $0 < m < n^2$, imply that it is $\Theta(n^2\log n)$?

If $m=\Theta(n^2)$, then indeed $\Theta(m\log n)=\Theta(n^2\log n)$.

However, you are only given that $0<m<n^2$, that is, $m=O(n^2)$ and you can only infer that the algorithm has complexity $O(n^2 \log n)$, but not $\Theta$ of the same quantity. For instance, assume $m$ is a constant, or assume $m=\sqrt{n}$, and you could see why it cannot be $\Theta(n^2\log n)$.


String matching for all suffixes Given a string $(a_0,a_1,\ldots a_n)$. I want to find the length of the longest common prefix of the substrings $(a_0,a_1,\ldots a_{n-1})$ and $(a_1,a_2,\ldots a_n)$. I know this has atleast $O(n)$ complexity. Lets call this operation as prefix-suffix match.

I want to calculate prefix-suffix match length for all suffixes of a string. Now the naive algorithm which doesn't take into account that all the strings for which I am doing this operation are related has $O(n^2)$ complexity. Now my question is can we do this in better complexity.

Note that what I want is similar to LCP array of a slightly modified suffix array. Where the suffixes are sorted based on length instead of lexicographic ordering.

Expanding on reinierpost's comment, here is how to do it in linear time. Every word $w$ can be decomposed as $w = a_1^{k_1} a_2^{k_2} \cdots a_l^{k_l}$, where $a_i \neq a_{i+1}$ and $k_i \geq 0$. This is just decomposition into runs. The LCP of $w$ and its shift is simply $a_1^{k_1-1}$.

In view of this, here is how to compute the answer for all suffixes of a word $w$ in linear time. We go over the array backwards, populating an array $K$ using the following algorithm:

$K_n = 1$.
For $i = n-1,\ldots,0$:

If $w_i = w_{i+1}$, $K_i = K_{i+1} + 1$, otherwise $K_i = 1$.

The answer for the suffix starting at $w_i$ is $w_i^{K_i-1}$.


Clear, complete, proof that a language is Turing Compete? I have seen web sites that purport to "prove" that HTML5+CSS is Turing Complete.

I have seen web sites that purport to "prove" that SQL is Turing Complete.

I have seen a bunch of web sites that purport to "explain" what it means to be Turing Complete.

Enough!

Where can I find a book (written by an expert in computability theory) or a peer-reviewed article (in a reputable journal) that shows a proof of, "This language XYZ is capable of describing a computational machine which has the same computational power as a Turing Machine"?

Every language that can implement two counters $C_1, C_2$ (i.e. two registers that can store two arbitrarily large integers) and a program made with a labeled sequence of these two elementary instructions is Turing complete:

ADD $1$ to counter $C_i$, GOTO instruction $I_j$
SUBTRACT $1$ from  counter $C_i$ if $C_i > 0$ and GOTO instruction $I_j$; otherwise (if $C_i = 0$) GOTO instruction $I_k$

The result is proved in:

Marvin L. Minsky, "Recursive Unsolvability of Post's Problem of Tag and other Topics in the Theory of Turing Machines" (1961)

Don't forget that a computational model (in your case a programming language + a device that executes programs written in that language) can be considered Turing complete only if it supports access to an unbounded amount of memory (i.e. space) or can store (in some form) arbitrarily large integers. A programming language implementation on a real computer is equivalent to a Linear Bounded Automaton.

You can also find a lot of references on the Wikipedia pages on RAM model and RASP model.

Finally a nice book focused on the equivalence of different models of computation is:

"Models of Computation: An Introduction to Computability Theory", by Maribel Fernandez


Why we need EEPROM in this micro-controller PIC16F887 Block Diagram

According to the block diagram above, since we already have Program Memory, which may be used to store our program, why should we still need EEPROM? What is it for?

See EEPROM#Related_types on Wikipedia. Your Program Memory is likely flash memory, which you'll flash (i.e. completely erase and rewrite) with your program every time you like to change it.
8KB is smaller than the usual size of blocks for flash memory, so its unlikely that you can erase only a half or a quarter of your Program Memory.

The program itself may store small quantities of information (a few bytes for important data) without erasing itself by using the EEPROM, which can be written to bytewise (or wordwise).

So the EEPROM is like a tiny hard disk and the Program Memory is more like a tiny rewritable CD.


Finding largest elements I was asked to find write a pseudocode of an algorithm that extracts the Log(N) largest elements in an array and return them in a sorted list, my attempt is
largestLogn(Arr)

n = Arr.length
j = 0
ans = new array of size Log(n)

Arr = Quicksort(Arr,1,a)

for i=(a-log(n)) ➜ a
ans[j] = Arr[i]
j++

return ans

From my limited understanding, the time complexity of this algorithm is $O(n\log n)$ for the QuickSort and $O(\log n)$ for the loop but in the question they hinted that the time complexity has something to do with the fact that $(\log(n))^{a}=O(n^{b})$ for any $a,b>0$ and now I'm not sure of my answer.

The second loop in your solution requires time $O(\log n)$ and can be safely ignored since its time complexity is dominated by the previous sorting step.
The call to Quicksort requires time $O(n \log n)$ in expectation and $O(n^2)$ in the worst case.
You can solve your problem in $O(n)$ worst-case time as follows:
create a max-heap with the elements in the array. Then, perform $\log n$ extract-max operations.
Creating the heap takes $O(n)$ time while each of the maximum extractions requires $O(\log n)$ time, for a total time of $O(n + \log^2 n) = O(n)$.


How to implement polymorphism in a turing complete environment? I'm currently programming in an unnamed turing complete language which has support for pointers, primitive data types, structures, closures, and garbage collection, among other things.

I'm trying to use this language to implement an object oriented design pattern. So far, I have implemented the following algorithm:

make object (base class) subroutine:
    create data structure
    associate structure as an 'Object'
    return data structure

make shape (extends from object) subroutine:
    call make object
    associate data structure as a 'Shape'
    add 'getPerimeter' & 'getArea' subroutines to data structure
    return data structure

make circle (extends from shape) subroutine:
    call make shape
    associate data structure as a 'Circle'
    add 'getCircumference' as subroutine to data structure
    re-define 'getPerimeter' & 'getArea' subroutines to data structure
    return data structure

output shape area subroutine
    assert shape is a Shape
    print, call shape.getArea

This so far has worked great. Sub-classes correctly inherent the fields of their super-classes.

However, I am no longer able to take the extended classes and 'treat them as their super-class forms' anymore. For example, I can no longer treat a Circle specifically as a Shape, because when it was made into a Circle it was augmented with Circle member functions like getCircumference. I cannot typecast it to be strictly a Shape or an Object, as its now been defined with sub-class functionality.

In Java terms, I can do this:

Fruit a = new Fruit(); // eat()
Apple b = new Apple(); // removeSeeds()
b.removeSeeds();
b.eat();

But I cannot do this:

Fruit a = new Apple();
a.removeSeeds(); // undefined

How can polymorphism be implemented in this sense?

So, first, a question. Are you using dynamic or static dispatch? i.e. if Circle and Shape provide implementations of the same method, and you cast a Circle to a Shape, which one gets called?

If you're using static dispatch, one way to do it is, instead of making a Circle by taking a shape and adding fields, you make Circle its own type, with a special Super field that is a Circle. Any time Circle methods reference Shape fields/methods, you desugar into Super.field. Casting a Circle to a Shape then just involves looking up the shape that's stored.

If you're using Dynamic dispatch, but are using static typing, instead you can use "duck typing" internally, that is, the "type" of something is just which methods/fields are accessible. So in this system, you could construct a Circle as you've described, and when you cast it to a Shape, there's no runtime effect. Your typechecker just ensures that no Circle methods are called on a Shape, even if its runtime representation is a Circle.

Finally, if you're using dynamic dispatch and dynamic typing, then you probably don't need to ever cast a Circle to a Shape (since there's no typechecker to stop you from calling Shape methods on a Circle). The trick here is that your assert shape is a Shape should return True for anything that is a subclass of Shape. So as long as that check succeeds for a Circle, you're fine. This is why such a check is called instanceof in Python: you're not accessing the type of the value, you're checking if it is a subclass of the desired type.

I'm not sure how Turing Completeness factors into anything: Java, Python, and other subclassing languages are all Turing Complete. Java's type system is even Turing Complete!

One final pedantic note: what you call "polymorphism" is better described as "subclass polymorphism". There are, in PL theory, many other kinds of polymorphism, such as parametric (i.e. generics), and ad-hoc (i.e. overloading).


Finding the nodes that have degree at least 3 in an undirected graph I want to come up with a good algorithm that takes as input an undirected graph $G$ and checks which vertices to include in an output graph $G'$, such that each vertex in $G'$ has degree at least 3.

I've thought about traversing the graph once to eliminate any vertex with degree less than 3 since none of these can be included in the output. Then, I could have a set $S$ that initially contains some arbitrary vertex that hasn't been eliminated; the rest of the vertices are kept in the set $T$.

If I keep with this idea, I'm not sure how to start moving in vertices from $T$ to $S$ and at which point to delete them. I also wonder if there's a way to use BFS to scan and see if each vertex has degree at least three in the output tree of the BFS procedure. Any pointers/ideas would be appreciated; thanks!

This problem is known as a maximum $k$- core (in your case $k = 3$) and can be solved in polytime. The idea is the one you mentioned : simply delete vertex with degree less than 3 until you don't have such vertices.

More accurate description of the algorithm:

Store your graph as adjacency list. Whenever you find a vertex with degree less than $k$ mark it as deleted and then remove it from neighbors list of its neighbors. In the end you can shift indices if you really need them to be in consecutive order.


Tree structure that is like a quadtree/octree but splits a different number of times in each dimension? I'm looking for a data structure that is like a quadtree where each level is a subdivision of the previous. However, unlike a quadtree I need the subdivision to occur a different number of times in the horizontal direction to the vertical direction. In a quadtree the space is subdivided once in each dimension (resulting in four children per node). In the tree I'm looking for the space may be divided a given number of times in one dimension and a different number of times in the other. Say for example, twice in the X and once in the Y (resulting in six children per node). Has such a space partitioning tree been given a name? Can anyone point me to an existing data structure that fulfills this requirement? Thanks!

You could use a k-d tree.  A k-d tree normally alternates between partitioning horizontally and partitioning vertically, but you could certainly modify it to change that pattern (e.g., partition horizontally twice in a row; or equivalently, partition horizontally into three or four regions rather than just into two regions).

Not everything has a "name".  There are many more possible algorithms and data structures than there are "names".  So don't take it as some kind of negative if you can't find a "name" for it.  "Modified quadtree" or "modified k-d tree" will do fine, if you need a way to refer to it.


Probability of loss using a binary symmetric channel Today we talked about Information Theory and the binary symetric channel.
For newbies here is a little explanation :

For instance if I want to send a binary to someone :
The bit will be "flipped" with a "crossover probability" of p, and otherwise is received correctly.
Example :

Note that in order to reduce the probability of the "flip" we repeat the bit 2,3,4... times. Here we use a R3 encoding cause the bit is repeated 3 times. Then to decide the transmitted bit we choose the most popular in this packet of 3 bits (in this case).
Up to here it's ok but i'm struggling with a question of my homework :

Let's suppose we use a R3 encoding, what's the probability a bit will be flipped ?

Thanks !

R3 encoding is a pair of algorithms:

Encoding: a bit $b \in \{0,1\}$ is encoded as the packet $bbb$.
Decoding: a packet $xyz \in \{0,1\}^3$ is decoded as the majority bit (the bit occurring most often).

Since the situation is symmetric, in order to understand the transmission error, it suffices to consider the case $b = 0$. Suppose we encode the bit $0$. So we transmit the packet $000$. Every bit is flipped with probability $p$, and this gives us a distribution on the received packet $xyz$. Finally, a transmission error occurs if $xyz$ is decoded as $1$, that is, if the majority of $xyz$ is $1$.
Therefore, the transmission error is the probability of the following event:

If $x,y,z \in \{0,1\}$ are independent identically distributed bits such that $\Pr[x=1] = p$, what is the probability that the majority of bits in $x,y,z$ is $1$?

You can compute this probability by brute force.


Regular expression for a binary number that includes "10" and has an odd number of 0's I have been struggling trying to write a regular expression for a binary number that includes "10" and has an odd number of 0's, so far I have (1) * (00) * 10(1010)   * (00) * (1) * but it doesn't accept 0100 for example or 010101 etc, also if I write a finite automata for this how do I prove its correctness ?

You can write a regular expression directly:

First ignore the odd number of zeroes. You can easily write an expression for this modified language, based on the fact that you can choose to particularize the first occurence of $10$ (namely $0^*1^*10(0+1)^*$ is a valid expression).
Now you want to modify the first part ($0^*1^*$) and the second part $(0+1)^*$ to take into account the odd number of zeroes. Since these two parts have to agree (have the same parity of zeroes) there are two disjoint cases: either you have even numbers of $0$'s before and after the $10$ pattern, or an odd numbers:

To have an even number of $0$'s before the pattern, simply write $(00)^*1^*$. For an even number after the pattern, this is simply an expression for a word with an even number of zeroes: $1^*(01^*0)^*1^*$ (each $0$ has a friend). Together, this gives you the expression: $(00)^*1^*\ 10\ 1^*(01^*0)^*1^*$.
To have odd numbers, you can re-use modified versions of the expressions in 1.: Before the pattern, you add a first $0$ in front: $0(00)^*1^*$; After the pattern, you need a first $0$ but also $1$'s in the middle: $1^*01^*(01^*0)^*1^*$. Together: $ 0(00)^*1^*\ 10\ 1^*01^*(01^*0)^*1^*$.

Globally, you have the disjunction of the two cases:

$$(00)^*1^*\ 10\ 1^*(01^*0)^*1^* + 0(00)^*1^*\ 10\ 1^*01^*(01^*0)^*1^*$$

This is not meant to be the smallest possible expression, but at least it shows how you can construct one. For instance, you can factorize the common parts to obtain
$$ (00)^*(1^*10+01^*101^*0)1^*(01^*0)^*1^*.$$


Online set filling with redistributions Edited: Suppose we have 4 sets $A, B, C, D $ which can can hold a maximum of two elements, each.

Now, elements ($E_i$) arrive serially with properties such as:

E1 : Should be placed in either B or C.
E2 : Should be placed in either A or B or C.
E3 : Should be placed in either A or B.

When an element arrives, we have to place the element in one of the 4 sets, immediately i.e. we cannot wait for all elements to arrive, and then decide.

When a new element arrives:

If there exists space in one or more sets, satisfying the constraints, we place the element in the set with minimum cardinality. Ties are broken randomly.
If there is no space satisfying the constraints, the existing elements may be redistributed to accommodate the new element.
If even after redistribution, there is no space satisfying the constraints, discard the new element.

Objective
Accommodate the newly arriving elements, while having less number of redistribution.

An illustrative example depicting the problem is attached.

What strategy should i choose to achieve the objective? I need an algorithm for the redistributions that is scalable to large number of sets and more than 2 entry for each set.

In the picture, randomly I have chosen 2 possibilities, one of which yields less number of redistribution than the other. So are there any approaches other than exhaustively checking all possible combinations?

I can suggest two approaches:

Brute-force search

First try to find if there is a way to place the element, without redistributing any previously placed elements.

If not, try to find a way to place it, by redistributing exactly one previously placed element.  This can be done by enumerating all possibility for which element you redistribute and where you redistribute it to, to see if that leads to a valid placement.

If not, try to find a way to place it, by redistributing exactly two previously placed elements.  This involves enumerating all combinations of two previously placed elements to redistribute.

In general, if $n$ elements have been previously placed and $r$ redistributions are needed, this will involve enumerating ${n \choose 0} + {n \choose 1} + {n \choose 2} + \dots + {n \choose r}$ possibilities, which is $O(n^r)$.  This might scale OK if you expect $r$ to be very small but becomes slow once $r$ is large.

SAT solver

To get a more scalable solution, I suggest you use a SAT solver.

There's a natural way to encode your problem as SAT.  Introduce boolean variables $x_{i,j}$, meaning that element $i$ gets placed in set $j$ after redistribution.  Each constraint is a clause (disjunction of some $x_{i,j}$'s).  Also, we can represent the requirement that at most $r$ redistributions be used as the sum of $\neg x_{i,j}$ over all pairs $(i,j)$ that correspond to an element that is currently placed in set $j$ (before redistribution).

Thus, you can represent the problem of finding a solution using at most $r$ redistributions as an instance of SAT, and solve it using an off-the-shelf SAT solver.  Use binary search over $r$ to find the minimal number of redistributions needed.

I expect that this will scale much better.


2-tape TM that accepts words from $L := \{bin(n)$#$w \in \Sigma^* | n \in \mathbb N \land w \in \{0,1\}^* \land |w| \le n\}$ in $O(n)$ Let $\Sigma := \{0,1,$#$\}$ be the input-alphabet and $L := \{bin(n)$#$w \in \Sigma^* | n \in \mathbb N \land w \in \{0,1\}^* \land |w| \le n\}$ the alphabet. $|w|$ means the length of the word $w$ and $bin(n)$ the binary representation of $n$.

I need to construct a 2-tape TM which has $O(n)$ complexity and accepts the words from $L$, i.e. the machine terminates in an acceptable state iff the input is contained in $L$ und for all other input words the machine terminates in a not acceptable state.

EDIT: I already constructed a 1-Tape TM which reduces a binary number by 1 and which is supposed to help me with solving this problem but I don't know how.

Think over how to convert binary representation of $n$ into unary one using two tapes. The result should be stored on the second tape. For example, if $n=6$ then the unary representation could be $111111$. Then compare number of symbols of $w$ and number of $1$s of the unary representation of $n$. If the number of $1$s is less than or equal to $|w|$ then accept, otherwise reject.

Since number of bits in $bin(n)$ is no more than $log(n)$ number of unary bits is no more than $2^{log(n)} = n$, so writing down each bit on the tape should not take more than $O(n)$ time, and comparison $w$ with the unary $1$s also takes $O(n)$.

So you just need to design and algorithm for conversion from binary to unary representation of $bin(n)$ using two tapes that runs in $O(n)$ time.


Inapproximability result implies apx-hardness? If an optimization problem is known to be inapproximable up to some precision, does this automatically imply that the problem is apx-hard?

If P$=$NP then there is a polytime algorithm for any NP optimization problem, and so every problem is APX-hard. So from now on, suppose that P$\neq$NP.

We can associate with any decision problem $L \in NP$ an optimization problem $o_L$ by defining $o_L(x) = 1$ if $x \in L$ and $o_L(x) = 2$ otherwise. Suppose $o_L$ reduces to $o_M$ via a PTAS reduction $(f,g,\alpha)$ (notation as in the Wikipedia article). Let $C = 1+\alpha(1/2)$. Thus if $y$ is a $C$-approximation to $o_M(f(x))$ then $g(x,y,1/2)$ is a $3/2$-approximation to $o_L(x)$, from which we can determine whether $x \in L$ or not. Altogether, this gives a polytime reduction from $L$ to $M$. Now take any NP-complete language for $L$ and any NP-intermediate language for $M$ (such a language exists because of Ladner's theorem). On the one hand, since $M \notin P$, you cannot 2-approximate $o_M$. On the other hand, $L$ doesn't reduce to $M$ (since that would apply that $M$ is NP-complete), and so $o_L$ doesn't reduce to $o_M$. We conclude that $o_M$ is not APX-hard.


Design a Turing Machine which accepts strings $x \# y$ where $x \ge y$ Imagine you are designing a TM where $x$ and $y$ are binary representation( $x \ge y$). the TM should accept $1101\#1001$ and reject strings such as $110\#10001$, as well as it could reject if you have more than one $\#$ or less than one $\#$.

Now, I have tried doing this. my idea is that:

For step one is to mark the left side first input as X, then scan to the right until you find a # sign, go to step 2, else if # sign not there reject
For step 2, zigzag left most side and compare each input to compare the 1's with each other. but i think i'm way off.

zigzag left most side and compare each input to compare the 1's with each other.

That is the right idea -- comparing the input one character at a time will work.

However we should be careful that we are comparing the right digits. For example, we don't want to say that 11 is bigger than 101 just because we compared the first two digits only, and said that 11 is bigger than 10. So, maybe it would be helpful to have, as a first step, to see which of them has more digits. Make sure that you ignore leading zeros when doing this.

  but i think i'm way off

Not at all, you have the right idea.


Is knapsack a Linear Programming problem? Since Knapsack give Optimal solution as LP so is it also a LP or not ?

The knapsack problem can be modelled as a mixed integer program (MIP) and the linear-programming relaxation of this model can be solved. The linear relaxation does not give a solution to the problem, but it will provide an upper bound to the solution of the knapsack problem (equivalent to a solution of the MIP) which helps the MIP solver in its quest to find the optimal integer solution.