What is the most compact (space efficient) method of storing an array of distinct integers? I have an array of distinct integers which I want to save in the most compact manner. I may have to do occasional lookups, deletions, and insertions in this array so the compression algorithm must adjust for such cases.
What is the appropriate algorithm/ data structure that I should think of?

Is there anything along the lines of Huffman encoding but for numbers?

If your integers have small difference between them you can use a bitset with an offset. In this way if the difference between the largest and the smallest is n you need n bits + the size of the offset in bits. If your integer set is sparse you can use a sparse bitset implementation like Roaring bitmap .


Euler polygon division algorithm I am trying to enumerate and display all possible divisions of an n-polygon into (n-2) triangles (as in the following mathworld picture)

I know how to count how many divisions (Catalan numbers, 1, 2, 5, 14, 42, ... ), but I am struggling to find a way to generate all the C(n-2) triangulations. Can anyone point to existing software implementation, or at least to an algorithm that generates these triangles?

See: Hurtado and Noy, Graph of triangulations of a convex polygon and tree of triangulations, Computational Geometry 13 (1999) pp179–188.
Section 3 of that paper gives a relatively straightforward method for constructing all triangulations of $n+1$-gons given all triangulations of $n$-gons.


PDA translating $a^{m+n} b^n$ to $x^{2m+2} y^{3n}$ On my compilation theory exam we had the following problem:
Construct a PDA translator (just one stack) such that it translates the language $$ a^{m+n}b^n \rightarrow x^{2m+2}y^{3n}, \text{ where } n,m \geq 0$$
I cant think of any solution. My approach was as follows: I would put in the stack  $m+n$ symbols of $a$. Then, for every $b$ in $b^n$ I would remove one $a$. Then I would be left with $m$ symbols of $a$ in the stack. After, that, I would emit two symbols of $x$ and I would empty the stack. For every $a$ that was left I would emit two symbols of $x$.
I could not figure out how to obtain the second part because in order to determine $m$ I would need subtract the $n$ from $b^n$.
By PDA translator I mean a regular PDA but instead of accepting/rejecting a language, we use it to transform a language into another (every transition in the automaton can emit some symbols).

This seems impossible if the translator has to be deterministic.
Let's clean up the problem and ask the PDA to convert $a^{n+m} b^n$ to $x^m y^n$ (your translator can be converted to such a translator by using a regular transducer). Since your PDA is deterministic, it cannot output anything until it knows whether $m = 0$ or not, which can happen in one of two ways: either it reaches the end of input, or it reads $a^n b^n$ (which must also be the end of input).
Now let us modify your PDA so that instead of outputting $x^m y^n$, it checks that the rest of the input has the form $x^m y^n$. We obtain a deterministic PDA accepting the language of all words of the form $a^{n+m} b^n x^m y^n$, yet this language is not context-free (you can see this by intersecting with $a^*b^*y^*$ to get the language of all words of the form $a^nb^ny^n$).


Iota combinator and implicational propositional calculus There is are two esoteric languages with minimally functionally complete operators, iota and jot, that are closely related to SK combinators. I'm attempting to understand the relationship between these languages and propositional calculus.

We know $K := P → (Q → P)$ and $S := (P → (Q → R)) → ((P → Q) → (P → R))$

My question is this: Is there a relation between iota $λx.xSK$, jot, or iota prime $λx.xKSK$ with Łukasiewicz's axiom system?

$((P → Q) → R) → (R → P) → (S → P)$

The axiom scheme you reference represents a classical logic, i.e. one with excluded middle.  The computational interpretation of Peirce's law (implicitly embodied in Łukasiewicz's system) is call/cc.  Neither iota nor jot support first-class continuations (or continuations of any sort), so they do not encode or imply Peirce's law.

Added much later:

I think I just now realized that the minimally functionally complete is talking about completeness of logical connectives and had originally thought it had been referring to the completeness of the SK basis. This realization doesn't invalidate my answer but makes it so that there is more to say.

The first thing to say is that functional completeness in the context of propositional logic is (usually) talking about Boolean functions and thus we usually talk about collections of connectives (like $\to$ and $\land$) being or not being functionally complete. It doesn't really make sense to use it to refer to programming languages which we usually want to be Turing-complete which is a very different notion.

Nevertheless, taking a logical view of the SK combinatory logic, as the question does, the only connective is $\to$ which is not functionally complete. This is mentioned on the referenced page on Łukasiewicz's system. That page also strongly implies that Axiom 3 is not derivable from Axiom 1 and Axiom 2 which correspond to $K$ and $S$ respectively. If true (which it, of course, is), that would mean that the single axiom can't be derived from Axiom 1 and 2 either, since you would then be able to derive Axiom 3. My original paragraph was a high-level argument of why this is the case. A more direct argument would be to provide a counter-model by using a non-classical model of intuitionistic logic which will validate Axioms 1 and 2 but not Axiom 3 and therefore not the single axiom.

As a final note, in the above I've been assuming a typed version of iota and jot which are untyped languages. This is necessary for the logical reading to be meaningful. It is worth noting that a type version of iota and jot would not be Turing-complete.


Is the complement of this decision problem in $P$? Are there any two primes that are NOT a factor of $M$ that multiply up to $M$?
Fact: Any two primes that multiply up to $M$. Must be factors of $M$!
Thus because of the fact above an $O(1)$ algorithm exists. It always outputs $NO$
Complement
Are there any two primes that are a factor of $M$ that multiply up to $M$?
Fact: A complement of a decision problem does not always require to always return $YES$ or $NO$. It can be either one!
(eg. $M$ = 6 and two primes that multiply up to $M$ are $3$,$2$.)
Well, this I find interesting this is deciding $Semi-Primes$.
Question
Shouldn't $Semi-Primes$ be in $P$, because what was shown above?

Careful how you come up with a complement. The original problem asks to satisfy the following, given M:
$$\exists p,q: ((p\text{ and } q \text{ are prime})\land \neg(p\mid M)\land \neg(q\mid M) \land (pq=M))$$
As you say, the answer is always NO.
The complement of the problem should by definition have the opposite answer (YES) for ever $M$. To see why that's the case, negate the original problem (carefully):
$$\neg\exists p,q: ((p\text{ and } q \text{ are prime})\land \neg(p\mid M)\land \neg(q\mid M) \land (pq=M))$$
Distributing through the $\exists$ gives:
$$\forall p,q: \neg((p\text{ and } q \text{ are prime})\land \neg(p\mid M)\land \neg(q\mid M) \land (pq=M))$$
And distributing again makes this pretty trivial:
$$\forall p,q: ((p\text{ or } q \text{ is not prime})\lor (p\mid M)\lor (q\mid M) \lor (pq\ne M))$$
So the complement is really asking: Given $M$, is it true that every pair of numbers $p$ and $q$ either has a non-prime or a divisor of $M$ or they don't multiply to $M$? It's a bit strange to claim this, but it's always true.


Uniform sampling with constraints Suppose one wants to uniformly sample a string $w$ of a given length over a finite alphabet, such $w$ satisfies a set of structural constraints (such as - "the third character has to be equal to the first character and the last character has to be equal to the second one").
The obvious method is to uniformly sample $w$, check if the constraints hold and return it if so. However, I am dealing with the case where there are many constraints, and the probability of random string to satisfy them is extremely low. Is there a way to sample uniformly from the set of all strings satisfying the set of constraints?

If your constraints can be described using a small DFA, then you can use sampling-by-counting, which works in the following way. For each $\sigma \in \Sigma$, count the number of legal strings starting with $\sigma$ (as explained below), and use this to sample the first character, say $\sigma_1$. Then, count the number of legal strings starting with $\sigma_1 \sigma$ for all $\sigma \in \Sigma$, and use this to sample the second character; and so on.

It remains to explain how to count the number of strings of length $n$ with prefix $x$ accepted by a given DFA. Let me start with the case $x = \epsilon$. The idea is to use the transfer matrix method: construct a matrix $A$ in which $A(q_1,q_2)$ is the number of edges from $q_1$ to $q_2$ in the DFA (that is, the number of symbols $\sigma$ such that $\delta(q_1,\sigma) = q_2$). It is not hard to check that $A^n(q_1,q_2)$ is the number of words of length $n$ which carry the DFA from $q_1$ to $q_2$. Taking $q_1$ as the initial states and summing over all final states for $q_2$, we obtain the number of words of length $n$ accepted by the DFA.

Given a prefix $x$, we do exactly the same, only counting words of length $n-|x|$ that are accepted by the DFA when started at state $\delta(q_0,x)$.

As a simple example, you can use this technique to sample a word of length $2n$ over $\{a,b\}$ having an equal number of $a$ and $b$. Although the corresponding infinite language isn't regular, you can construct a DFA for this language which has $O(n)$ states, making the above approach feasible. In this particular case there are also known closed formulas for the number of words of length $n$ with prefix $x$.

With some work, you can probably extend this approach to context-free grammars. One thing to try would be to extend the CYK algorithm so that it counts the number of words of given length with a given prefix.


Mutual Information in a Binary Erasure Channel Imagine a Binary Erasure Channel as depicted on Wikipedia.

One equation describing the mutual information is:

$$
\begin{align*}I(x;y)
 &= H(x) - H(x|y) \\
 &= H(x) - p(y=0) \cdot 0 - p(y=?) \cdot H(x) -p(y=1)\cdot 0\end{align*}$$

Why is it "$p(y=?) \cdot H(x)$" and not "$p(y=?) \cdot H(x|y=?)$"?

If $y = ?$ then $H(x) = H(x|y=?)$ since $y = ?$ gives you no information about $x$.


Streaming algorithm for counting triangles in a graph As described in the reference, the algorithm (see at the bottom) supposes to output an estimator $\hat T$ for the # of triangles in a given graph $G = (V, E)$, denoted $T$. It is written that "it can easily be shown" that
$$
E[\hat T] = T
$$
But unfortunately, I'm not seeing it. Trying to analyze $E[\hat T]$, I think as follows:

At line 1, denote the probability to randomly (and uniformly) choose an edge which is part of a triangle as $p$. Since triangles can share edges,
$$
   \frac T m \le p \le \frac {3T} m
   $$
For example, consider the following case:

The central triangle doesn't add new edges to the # of possibilities to choose an edge which is part of a triangle. You can imagine a different configuration, in which there are only the 3 outer triangles and they don't touch each other (in this configuration, we won't see the central 4th triangle). In both cases ((case i) 4 triangles as seen in the image; (case ii) 3 disjoint triangles), the probability to choose an edge which is part of a triangle is 1 (although the # of triangles is different).

At line 2, the probability to choose uniformly at random a vertex which "closes a triangle" with the edge from the previous step is exactly $\frac 1 {n-2}$.

Therefore I only see that
$$
T \le E[\hat T] \le 3T
$$
What am I missing?

Another question I have is regarding line 3. The stream is ordered, and we first pick a random edge $(u, v)$ (line 1), then a random vertex $w$ from $V \backslash \{u, v\}$ (line 2). I feel that the analysis should take into account that at line 3 we check whether $(u, w)$ and $(v, w)$ appear after $(u, v)$ in the stream. Maybe after I'll understand the answer to my first question, it will be clearer.

Algorithm:

Pick an edge $(u, v)$ uniformly at random from the stream.
Pick a vertex $w$ uniformly at random from $V \backslash \{u, v\}$
If $(u, w)$ and $(v, w)$ appear after $(u, v)$ in the stream, then output $m(n-2)$. Else, output $0$.

Also, although I didn't see it written, I believe there's an assumption that $V$ is known ahead.

Reference: Data streams lecture notes by Prof. Amit Chakrabarti, section "15.3 Triangle Counting", https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf

Best regards

Let $(u,v,w)$ be a particular triangle in the stream, and suppose that the edge $(u,v)$ appears first. The probability that we chose $(u,v)$ in the first step is $1/m$. The probability that we chose $w$ in the second step is $1/(n-2)$. Hence the probability that we chose the triangle $(u,v,w)$ is $1/[m(n-2)]$. Let us denote this event by $E_{u,v,w}$.
If $(u_1,v_1,w_1)$ and $(u_2,v_2,w_2)$ are two different triangles that the events $E_{u_1,v_1,w_1}$ and $E_{u_2,v_2,w_2}$ are disjoint (note that the triangles don't have to be disjoint). Therefore if there are $T$ triangles, then the probability that we chose one of them is exactly $T/[m(n-2)]$. Therefore the expected output of the algorithm is exactly $T$.


Deciding if language is Context-Free I need help with deciding if $L$ is context-free.

$$L = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$

Can be rewritten into:

$$L = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \ge 0\ , s > t\}$$

When we see the first occurrence of $c$, we push the $c$:s onto the stack. But we can't make difference between $d^q$ and $d^t$,  so comparing $s < t$ is impossible when popping the $d$:s.

Hence $L$ is not Context-Free.

Is my reasoning right ?

Hint: rewrite $L$ as $L = \{a^p b^r b^q c^s d^t d^q e^r e^p \mid p,q,r,s \ge 0, s>t\}$.

Does $L$ now look like something you can generate with a CFG?


Use the pumping lemma to show it's not regular I just learned pumping lemma this week and got confused on this question.

B={$a^{fn}$ | $f_n$ is a Fibonacci number} for $a \in Σ$.

Hint: the sequence of Fibonacci numbers get increasingly further apart.

I am trying to prove this is not regular using pumping lemma, but 'Fibonacci numbers get increasingly further apart' seems really tricky when I try to pump up to prove it's not $\notin$ B.

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

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


How can a problem be undecidable yet enumerable? How can something be enumerable but be un-decidable ie, this states the halting set is un-decidable and enumerable. Enumerable means it can be computed, ie has the same cardinality as natural numbers and can be computed by a program with an output. But if thats the case it should be decidable. Or is decidability separated from computability?

Am I misunderstanding the intuition of the halting set?

For me, the easiest way to think of it is this:

You're asking yourself "out of a bunch of candidates in a set $X$, do any of them fulfill the property $P$"?

Decidable/recursive means that you only need to look at a finite number of elements of $X$ before you hit some point where you know nothing that's left has the property.

A problem that's recursively enumerable, but not recursive, is one where you can look at each $x$ in $X$ one at a time. If you find one, then you're done, you know there exists on that fulfills your property. But there's no way of knowing when you're done, and $X$ is infinite, so if one doesn't exist, you will end up searching forever.

This contains some simplifications over the theoretical definitions, so be careful.

As an example: The halting problem is, you're looking at all $x_1, x_2, \ldots$ where each $x_i$ is a configuration of the turing machine $M$ after $i$ steps. The property is, is $x_i$ in a halting state. If you find one, you're done, but if you don't find one, there's no way to know when you're done.

Compare this to the SAT problem. You've got a Boolean formula, and you want to give each variable a True or False value to make the whole thing true. Even though it's really slow, you can try all true/false combinations. There's an exponential number of them, but it's finite. When you're done, you're done, and if none of them satisfied, you can halt, confident that there's no answer.


Processor pipelining question: number of instructions per second A question from the textbook Modern Operating Systems by A. S. Tanenbaum reads as follows:

  A computer has a pipeline with four stages. Each stage takes the same time to do its work, namely, 1 nsec. How many instructions per second can this machine execute?

This was recently a homework question in my operating systems class (it's already been graded). Here's the reasoning I provided (screenshot):

The book's answer key says the following:

  Every nanosecond one instruction emerges from the pipeline. This means the
  machine is executing 1 billion instructions per second. It does not matter at all how many stages the pipeline has. A 10-stage pipeline with 1 nsec per stage
  would also execute 1 billion instructions per second. All that matters is how
  often a finished instruction pops out the end of the pipeline.

I was wondering if someone could explain this; the book's explanation doesn't make sense to me. One instruction emerges from the pipeline every second only after the first second because we lose those 3 nanoseconds initially. And it's only 1 billion instructions per second if we consider the limit.

The book quite rightfully ignores the three startup cycles. Nobody cares whether it performs $10^9$ or $10^9-3$ instructions. In reality, "1 ns" is never exactly one nanoseconds, so the deviation from the clock rate not being exactly one per nanosecond makes much more difference.


What are the uses of multi-dimensional arrays? While studying arrays a question came to my mind. If only 1D and 2D arrays can be used, then why multi-dimensional arrays exist? Is there any use of multi-dimensional arrays?

One could just as easily ask "what are the uses of multidimensional spaces?"  After all, with space-filling curves, all we really need is one dimension.

But a single dimension, even if it's sufficient, does not always yield useful models.  For example, a 2-dimensional euclidean line would be non-continuous when mapped to a space-filling curve.

It's the same with multi-dimensional arrays -- they're used not because they're inherently necessary, but because they're a useful model.

For example, let's take a look at how one might model a movie.

A movie is nothing more than a time-varying sequence of images -- i.e., an array of images.
Each image is a two-dimensional array, with each element of the array representing a color.
A color has three components:

Red
Green
Blue

So a movie can be modeled as a multidimensional array.


Why is data stored on a flash disk irretrievable if the memory chip is cracked? All data recovery companies, regardless of skill, unanimously say that if the memory chip of a device has just a hair line crack, data recovery is impossible. Not unlikely, not expensive, but impossible. One company even stated that even the FBI can't retrieve the data. Is this true?

Why is this? I find it hard to believe if just a tiny section of an extremely common chip has a tiny crack, all of the data is completely gone.

I would have thought someone talented person somewhere would be able to patch up the area of the chip and get some of the data back...

Is it something to do with the charge? I know flash memory uses transistors to store its ones and zeroes in the form of an electrical charge. If the chip is cracked, do the transistors "short-out", turning them all to zeroes, something like that? Is the data gone rather than irretrievable?

The data may well still be there, the problem is that there is no (reasonable) way to get an electrical signal into or out of the data cells.  When you crack a chip you are cracking wires.  The minimum feature size in many chips made these days is around 20nm=200 Angstroms.  I suppose that if you (a) had an electron microscope, (b) knew exactly how the manufacturer had laid out the chip (what every wire means, and what signals need to be sent where to get the data), and (c) had some kind of electron microscope based soldering iron or micro-manipulator with a tip just a few atoms wide, you could laboriously and painstakingly repair all those broken connections.

But, while data recovery companies (the super duper ones) might have electron microscopes, I doubt they have either (b) any access to the manufacturer's layout or (c) a micromanipulator that could actually be used to do the repair.  Also, we're talking about potentially needing to repair thousands of connections, so even if someone were able to do it, they'd probably charge tens or hundreds of thousands of dollars.


Find all increasing/decreasing sub array I have a question that I still struggle with.
It would be really appreciated if you guys could give me some hints.

Here is the problem :
Assume that $a[1\dots n]$ is an array of $n$ positive real numbers.
Let $\alpha >0$ and $\beta >0$

a subarray $a_1$ with $m$ elements of $a[1 \dots n]$ is called increasing if $\frac{a_1[i]}{a_1[j]}\geq \alpha$, for all $i>j$ and $1 \leq i, j \leq m$.
a subarray $a_2$ with $k$ elements of $a[1 \dots n]$ is called decreasing if $\frac{a_2[i]}{a_2[j]}\leq \beta$, for all $i>j$ and $1 \leq i, j \leq k$.

Question : write a program to find all increasing/decreasing subarrays of $a[1 \dots n]$ ?
thanks so much for your help.

The question is not clear, you say sub-array, but in the comments you say sub-sequence, and also the comment "the array is discrete" (not sure what that means...).

It is also not clear whether you want a sub-sequence that is both increasing and decreasing. I will presume they are disjoint problems.

So, on the assumption that you want to find all increasing sub-sequences of the array: $a[i_1], a[i_2], \dots, a[i_m]$ with $i_1 \lt i_2 \lt \dots \lt i_m$ here is an algorithm.

Given the array $a[1, \dots n]$, you construct a directed acyclic graph of $n$ vertices: $v_i = (a[i], i)$ with a directed edge from $v_i$ to $v_j$ iff $a[j] \ge \alpha a[i]$ and $j \gt i$.

Now you enumerate all the paths in this directed graph. This is $O(n^2 + f(P))$ where $P$ is the number of paths in the graph, and $f$ is the complexity of the algorithm you pick to do the enumeration.

If you just wanted a count of paths rather than the actual paths themselves (which is what I suspect was your original problem, based on asking for a "hint"), then a dynamic programming algorithm which finds the number of sequences ending at a given $a[i]$ could be made to work in $O(n \log n)$ time.


Is it true that PAC is a subset of agnostic PAC? I would like to see the proof or a refernce to it. I feel it is obvious but my tutor insists the other way (agnostic PAC is a subset of PAC, and there are problems in PAC that are not angostic PAC).

The trivial implication is:

$\mathcal{C}\subseteq 2^\mathcal{X}$ is agnostic PAC learnable $\Rightarrow$ $\mathcal{C}$ is PAC learnable

Intuitively, being agnostic PAC learnable is a stronger condition, since you can, for all distributions on $\mathcal{X}\times\{-1,1\}$, get close to the optimal error (in particular, you can do so when the labels are forced to be consistent with some $c\in\mathcal{C}$).

To see this formally, suppose a concept class $\mathcal{H}\subseteq 2^{\mathcal{X}}$ is agnostic PAC learnable. This means that there exists an algorithm $A$, such that for all $\epsilon,\delta>0$ there exists $m\in\mathbb{N}$ such that for all distributions $\mathcal{D}$ over $\mathcal{X}\times\{-1,1\}$, and a set of labeled samples $(x_i,y_i)_{i=1}^{n\ge m}$ drawn from $\mathcal{D}$, $A$ outputs $h\in\mathcal{H}$ such that:

$err(h)\le err^*(\mathcal{D})+\epsilon$, with probability $\ge 1-\delta$, where $err^*(\mathcal{D})$ is the error rate of the optimal hypothesis relative to $\mathcal{D}$.

To show that $\mathcal{H}$ is PAC learnable, let $h\in\mathcal{H}$ be some target concept, and let $\mathcal{D}$ be any distribution over $\mathcal{X}$. Examine the distribution $\mathcal{D}'$ on $\mathcal{X}\times\{-1,1\}$ obtained by drawing $x\in\mathcal{X}$ according to $\mathcal{D}$, and taking the pair $\left(x,h(x)\right)$. Note that $err^*\left(\mathcal{D}'\right)=0$, which means there exists an algorithm $A$ which produces a hypothesis in $\mathcal{H}$ with small generalization error (you can complete the details yourself, this shows you that all you need to do is unfold the definitions).

The opposite implication (agnostic PAC learnability follows from PAC learnability) is also true, since they are both equivalent to $\mathcal{C}$ having a finite VC dimension, but this is much harder to show.


Where does the assembler live inside a CPU? If, it indeed does? Where does the assembler live in the system? I understand that assembly language gets converted to machine code (binary) and that the processor then follows these instructions.

Where does the assembler live? Does it live in some kind of Read Only memory?

A reasonable question when one is unfamiliar with how a computer operates. The answer does depend on what kind of computer one is discussing. Computers range from small systems, like a Raspberry Pi or BBC Micro Bit (or even smaller) up to a large multiprocessor supercomputer.

In a normal typical computer an assembler is just a normal program, like any other application (or App) and it lives in the system in the same places as other Apps. There is nothing special about an assembler. An assembler is just like a compiler. It is a program that translates a sequence of statements described in one language (or notation) to an equivalent sequence in another language (or notation). A Java compiler would convert Java program statements into the equivalent sequence in (Java) Machine Code. An assembler for an ARM processor would convert the assembler statements into ARM machine code.

In a typical computer these programs would reside on the disc.

In something like a smartphone these programs would reside on some other form of persistent storage such as the built-in flash memory or a micro-SD card.

Not all computers need to have the assembler run on them. Very few smartphones would have an assembler App installed (but they could - my phone does have assemblers and compilers installed on its SD card!). For small devices the compilers and assemblers reside on and are run on a large computer and the machine code is generated there. The resulting file of machine code is then downloaded or installed on the computer.

You can thus have machine code without having any assembler on the same computer. The assembly was done somewhere else.

The answer is thus, the assembler could be anywhere!


Can $\emptyset$ be reducible to any other language? While solving some question, that involved the empty set $\emptyset$, I was really wondering, is $\emptyset$ reducible to any other language, i.e., $\emptyset \leq A$ such that $A$ is a language over a given alphabet $\Sigma^*$?

I mean, one can never take $x \in \emptyset$, right? or am I missing anything?

Maybe $\emptyset \leq \emptyset$? because if I take a reduction $f$ such that $x \in \emptyset \Leftrightarrow f(x) \in \emptyset$, this is always true, because $x \in \emptyset$ is never true and $f(x) \in \emptyset$ is also never true, so that function is a reduction function in the empty-concept, no?

$\emptyset$ can be reduced to any other language $L$ except $\Sigma^*$.

Remember that a reduction from $L_1$ to $L_2$ has to map "yes" instances of $L_1$ to "yes" instances of $L_2$ and "no" instances of $L_1$ to "no" instances of $L_2$.  Every input is a "no" instance of the language $\emptyset$ so, to reduce $\emptyset$ to any $L\neq \Sigma^*$, you just need to choose some word $w\notin L$ and your reduction maps everything to $w$.  Obviously, for $L=\Sigma^*$, this doesn't work because there's no $w$ you could use.

Similarly, $\Sigma^*$ can be reduced to any other language except $\emptyset$.


How do I minimize the cost of some algorithm that performs some operation on a list? I stumbled upon this problem whilst studying the complexity of a simple algorithm. I used set-theoretic notation, but all the $S_i$'s are lists (I couldn't think of a better way to write the problem precisely). The "hint" is more of a conjecture which I can't prove than a hint.

Let $S_0 = \{s^0_1, ..., s^0_n\}$ be a list containing $n$ positive integers. Let $k$ be the length of $S_{i - 1}$, and define $S_1, ..., S_{n - 1}$ recursively as follows: choose $1 \leq r, s \leq k, \quad r \neq s$, and define
       \begin{equation*}
       S_i := (S_{i - 1} \setminus (\{s^{i - 1}_r\} \cup \{s^{i - 1}_s\})) \cup \{s^{i - 1}_r + s^{i - 1}_s\}
   \end{equation*}
       E. g.
       \begin{align*}
       S_0 &= \{2, 3, 5\} \\
       S_1 &= \{5, 5\} \\
       S_2 &= \{10\}
   \end{align*}
       Clearly, $S_{n - 1}$ has a single element. Also, define $W_i := s^{i - 1}_r + s^{i - 1}_s$. Consider the quantity $\sum_{i = 1}^{n - 1} W_i$. In the previous example, this quantity can be $15$ or $18$. How do you have to choose $r$ and $s$ in each step so that $\sum_{i = 1}^{n - 1} W_i$ is minimal?

(Hint: Pick $r, s$ such that $s^{i - 1}_r = \min_{x \in S} x$, and $s^{i - 1}_s = \min_{y \in S \setminus \{x\}} y$.)

First, let us understand in more simple terms what you are trying to do. You start with a list of $n$ integers. Then you are repeating $n-1$ times the following operation: take a pair of integers, and replace them with their sum; this costs you the value of the sum. The costs accumulate additively, and your goal is to minimize the total cost.

You can construct a tree from the $n-1$ steps, in the following way. You start with $n$ isolated nodes. When adding two integers, you join them to a new root which represents their sum. In the end, you will have a binary tree whose leaves are the $n$ original integers. You can check that the total cost is $\sum_i d_i x_i$, where $x_i$ is the $i$'th integer and $d_i$ is its depth in the tree (number of edges from root to leaf). (A cost of $x_i$ is incurred each time that you add an integer in whose product $x_i$ was involved.)

At this point we have exactly reached the problem solved by Huffman's algorithm, which is exactly the algorithm given by your hint. You can look up a proof of optimality in many sources.


Find a CFG for a language In an assignment I've been asked to find a CFG for $a^x b^y a^z b^w$, where, $x,y,z,w \in \mathbb{N}^+$, $y > x$, $z > w$, and $x+z = y+w$. A hint was given, think of the language as $(a^p b^p)(b^q a^q)(a^r b^r)$.

I've had a go at it, and have come up with

S -> A
A -> aAbB | ab
B -> bBaC | ba
C -> aCb | ab

This language will give me equal $a$'s and $b$'s. The reason I've chained the productions together is that since $x,y,z,w$ can't be 0, when one production is done, the others must be done as well (that was my thinking). However, I can't help but be worried about order. Even the smallest production won't come out as in the order "abab". Is it possible to construct a CFG that imposes order and memory? Or do I have to go to a PDA then CFG? Or is it irrelevant?

The hint is another way of describing the same language. For the two languages to be the same, one must have: $x=p$, $y=p+q$, $z=q+r$, and $w=r$. Notice that these do satisfy the constraints $y\gt x, z\gt w$ and $x+z=y+w$ provided that $q,r\gt 0$. Now the structure of the hint language makes it easy to write a grammar.

$S \to ABA$

$A \to aAb|ab$

$B \to bBa|ba$


How does a computer interpret real numbers? I understand that the modern day digital computer works on the binary number system. I can also get, that the binary representation can be converted to rational numbers.

But I want to know how does the present day computational model interpret real numbers.

For eg:

  On a daily basis we can see that a computer can plot graphs. But here, graphs may be continuous entities. What is the
  mathematical basis, that transforms a discrete (or countable, at most)
  like the binary system to something mathematically continuous like a
  say, the graph of $f(x) = x$.

They represent continuous quantities with discrete approximations.  Mostly, this is done with floating point, which is analogous to scientific notation.  Essentially, they work with something like $1.xyz\times 10^k$, with some appropriate number of decimal places (and in binary, rather than decimal).

It's also possible to work with some irrational numbers directly.  For example, you could create yourself an object called "$\sqrt{2}$" without particularly worrying about what it is, except that it obeys the usual arithmetic rules and that $(\sqrt{2})^2=2$.  So then you could compute $$(\sqrt{2}-1)(\sqrt{2}+1) = (\sqrt{2})^2 + \sqrt{2} - \sqrt{2} - 1 = 2 - 1 = 1$$
exactly, as an algebraic fact that's not susceptible to rounding errors.

Note that, if you're plotting a graph on screen, regardless of how far you zoom in, you're plotting it as discrete pixels so using an appropriate number of significant figures basically gets you everything you need.


How to prove that a string is made up of subsequences occurring some arbitrary number of times using concatenation? How to prove that a string, s is made up of n > 1 subsequences occurring some arbitrary number of times using concatenation and stripping first and last character?
 E.g s = xyzxyz, subsequence is xyz and it occurs 2 times. The solution is to concatenate the same string e.g. xyzxyzxyzxyz and then strip the first and last character to get yzxyzxyzxy, then you find s (xyzxyz) inside that.

Other examples:

The word Table does not have a subsequence so the above method will give:
Table||Table -> TableTable -> ableTabl -> which does not contain
Table so Table does not contain a subsequence
The word mmebmmebmmeb -> has to return true with the above method because it contains mmeb repeated 3 times. So, mmebmmebmmeb || mmebmmebmmeb -> mmebmmebmmebmmebmmebmmeb -> (strip first and last) mebmmebmmebmmebmmebmme which contains mmebmmebmmeb (meb**mmebmmebmmeb**mmebmme)

My thought was to assume that there is at least one character in s that will invalidate the occurrence of a subsequence. E.g. instead of xyzxyzxyz (xyz occurring three times) we have xyzxyzxya where a is the wrong char. Now we assume that in   yzxyzxyaxyzxyzxy (after concatenation and stripping first and last) that the string s does exist which should be a contradiction - but I am stuck.

Could someone give me a formal mathematical proof?

Looked at this for ideas:
How to prove that the reversal of the concatenation of two strings is the concatenation of the reversals?

Let us first state the theorem that we are trying to prove.

Theorem. Let $w \neq \epsilon$ be a word. Then $w^2 = xwy$ for $x,y \neq \epsilon$ if and only if $w = z^p$ for some $p > 1$.

Proof. Let us first suppose that $w = z^p$ for some $p > 1$. Then $w^2 = z^{2p} = zwz^{p-1}$, where $z,z^{p-1} \neq \epsilon$.

In the other direction, write $w = w_1w_2$, where $|xw_1| = |w_2y| = |w|$. Since $x,y \neq \epsilon$, we see that $|w_1|,|w_2| < |w|$. We have $ww = xw_1w_2y$ implies that $w = xw_1 = w_2y$, and so $x = w_2$ (since $|x| = |w|-|w_1| = |w_2|$). In other words, $w = w_2w_1$.

Now let $w = \sigma_0 \ldots \sigma_{n-1}$, and let $|w_2| = m$. Note that since $|w_1|,|w_2| < n$, we have $0 < m < n$. The equality $w = w_2w_1$ implies (check!) that $\sigma_i = \sigma_{i+m \bmod{n}}$. Let $g$ be the GCD of $m$ and $n$; note that $g < n$. It is known that $g = am + bn$ for some integers $a,b$, and so $\sigma_i = \sigma_{i+bm \bmod{n}} = \sigma_{i+g \bmod{n}}$. Since $g \mid n$, this implies that $w = (\sigma_1 \ldots \sigma_g)^{n/g}$, where $n/g > 1$.


Simple algorithm to generate a linear extension from partial order set I usually do it via topological sort and wonder if there is a simpler way to generate a linear extension from partial orders without consider the graph of the relation.

No, there is no simpler way.  Topological sorting is exactly the problem of generate a linear extension from a partial order.  There are several standard algorithms for topological sorting; they are already pretty simple, and there's no reason to expect anything simpler.


What is the difference between a tight Big $O$ bound, a tight Big $\Omega$ bound and a Big $\Theta$ bound? I occasionally see these terms used and I'm not really sure what is meant by all of them. Is it possible for an asymptotic bound that is not Big $\Theta$ bound to be "tight"? What does it mean for bounds that are not Big $\Theta$ to be tight?

Is there a difference between a tight Big $O$ bound and a Big $\Theta$ bound?

$O$ and $\Theta$ refer to different properties of some function. In a sense, we know more of a function when we can describe it with $\Theta$ than with $O$.

However, usage of $O$ or $\Theta$ doesn't imply tightness of a bound. You have some function $f(n)$ that is a bound which you could either describe with $f(n)\in O(g(n))$ or $f(n)\in \Theta(g(n))$, but whether the bound is tight depends on the actual bound $f$.

So, as a tight bound means simply that there is no 'better' bound for all cases, a tight asymptotic bound (either in $O$ or $\Theta$, or even $\Omega$), simply means that there is no better asymptotic description of a bound.

An example of a tight bound with only $O$ is the time complexity of finding an element in an unordered list of size $n$. This complexity is bounded by $O(n)$ and this is tight. The complexity is not $\Theta(n)$, as there are cases when we find the element without scanning the entire list. (The asymptotic complexity of the worst case is $\Theta(n)$, though)

For more reading on bounds with Landau ('big $O$') notation, see the reference question How does one know which notation of time complexity analysis to use? and its answers.


Online sorting without modifications There is an array with $n$ places. There is a stream of $n$ unique numbers that arrive at a random order (permutation selected uniformly at random).

Whenever a number arrives, we must put it somewhere in the array, and we are not allowed to move it later. The goal is to have as many numbers as possible (in expectation) in their correct location in the final array. The "correct location" is defined as the location where it would appear if the numbers were sorted.

What is known about this problem? What is the best expected success rate, and what algorithm attains it?

Notes:

A related question is: What is the fastest online sorting algorithm? . It discusses a situation in which items can be moved when new items arrive, and the goal is to minimize the running time.
I am mainly interested in maximizing the expected number of the correct positions. However, it is also interesting if there is a way to improve the probability that all numbers are in the correct position, above O(1/n!)

Define a configuration to be a state of the array $A[]$ after receiving some of the numbers.  Define a configuration to be obviously wrong if there exists indices $i<j$ such that $A[i],A[j]$ have already been filled in with numbers such that $A[i]>A[j]$.

A randomized algorithm

Here is a natural algorithm: guess where to put each number uniformly at random, conditioned on the one constraint that you never place a number in an obviously wrong position.

The analysis of this approach seems pretty tricky.  Based on some back-of-the-envelope estimates I conjecture that this attains a $\sim e^{-\Theta(n)}$ probability of placing all numbers in the correct position, which is better than the naive $1/n!$ algorithm.  However I have no proof, so this could be wrong.

A deterministic algorithm

Here's what I can show.  Let's consider a variation on the above algorithm: when you receive each number, find the range of array indices that wouldn't be obviously wrong, and then place that number in the exact middle (median) of that range.  This algorithm is now deterministic.

For this algorithm, I can show that the probability of placing all numbers in the correct position is asymptotically larger than $1/n!$.  In particular, it is at least something like $1/2^{\Theta(n)}$.  Here's a hand-wavy analysis.  For simplicity, let's assume $n$ is one less than a power of two.  Place all $n$ numbers in a complete binary search tree.  Now consider all sequences where you enumerate all the numbers at depth $1$ in some order, then all the numbers at depth $2$ in some order, then all the numbers at depth $3$ in some order, and so on.  A hand-wavy estimate suggests that there are something in the vicinity of $n!/2^{\Theta(n)}$ such sequences, i.e., a random permutation has very roughly a $1/2^{\Theta(n)}$ probability of having this form.  Moreover, the second algorithm above always succeeds in placing every number in the correct position.  Therefore, the second algorithm above achieves a success rate of something in the vicinity of $1/2^{\Theta(n)}$.  In particular, the success rate is significantly larger than $1/n!$.

For values of $n = 2^i-1$, we can characterize the exact probability of being correct: letting $P(n)$ denote the probability that the second algorithm succeeds in placing every number in the correct position, we find

$$P(n) = {1 \over n} \times P(\lfloor n/2 \rfloor)^2,$$

because the first element needs to be the median, and then you have two problems of half the size (the subsequence of numbers smaller than the median has to be a sequence with the same property, and the same for the subsequence of numbers larger than the median).  We have the base cases $P(1)=1$ and $P(3)=1/3$.   This recurrence relation grows like $P(n) \sim 2^{-e/2 \cdot (n+1)}$.   Here $e/2 \approx 1.359\ldots$, so $P(n)$ grows roughly like $2^{-1.36 n}$, and in particular, much faster than $1/n!$.

In particular, here's one way to analyze this recurrence relation.  Let $Q(n) = -\lg P(n)$.  Then we find

$$Q(n) = 2 Q(\lfloor n/2 \rfloor) + \lg n,$$

where $Q(1)=0$ and $Q(3) = \lg 3$.  Letting $R(i) = Q(2^i-1)$, we find

$$R(i) = 2 R(i-1) + \lg(2^i - 1),$$

with base case $R(1)=0$.  Expanding, we find

$$R(i) = 2^{i-1} \times \left(\lg(1) + {\lg 3 \over 2} + {\lg 7 \over 4} + {\lg 15 \over 8} + {\lg 31 \over 16} + \dots + {\lg (2^i-1) \over 2^{i-1}}\right).$$

Summing the series, we find that to an excellent approximation

$$R(i) \approx 2^{i-1} \times e.$$

Therefore, $Q(n) \approx e/2 \cdot (n+1)$ and $P(n) \approx 2^{-e/2 \cdot (n+1)}$.

Credits: My thanks to @Algorithms with Attitude for the recurrence relation and the idea of analyzing the probability in this way.


$1+\epsilon$ approximation for inapproximable problems I am currently confused by the following situation:

1) The metric $k$-center problem is inapproximable in polynomial time within $2-\epsilon$ unless $P=NP$.
2) The metric $k$-center problem can approximated within $1+\epsilon$ in time $O(k^{O(k/ \epsilon)})$

Did I just win a million dollars or why isn't this a contradiction?
I guess my confusion comes from the unprecise statement  "in polynomial time" in 1).

The first sentence says there is no approximation algorithm with $2-\epsilon$ for k-center, which means $k$ is part of an input, because there is no limitation on $k$, so $k$ can be arbitrary large (as $n$). This is common mistake in the context of approximation algorithms and parametrized complexity, this doesn't mean the algorithm runs in polynomial time, this says if you "fix" some parameters (e.g here k) you can have polynomial time algorithm, exactly like what you mentioned, mentioned algorithm is polynomial in $n$ but not in $k$, and when $k$ is not fix and is part of input, the algorithm is not polynomial. You can read more detail on fix parameter tractability in reference question.


Identify balanced and full binary search tree insert order I'm inserting numbers 1 thru 15 into a binary search tree one by one. I need to come up with an order to insert these elements for it to result in a full and balanced binary tree. I've tried to create the binary search tree myself, starting with a root of 8, however I could never get it to be full; the depth would increase from three to four or sometimes five.

How can I come up with an order to insert these numbers into a binary search tree, and get it to be balanced and full?

Keep trying.  Try a recursive algorithm.  You know that the root needs to be 8.  You should be able to infer what numbers need to go in the left subtree of the root.  What order should you insert those numbers in, to ensure that the left subtree results in a full and balanced binary tree?  Hmm, does that resemble a problem you've seen before?  You should be able to take it from there.


Checking if a $k$-subset of a graph is a vertex cover in time $O(kn)$ Given a graph $G=(V,E)$ with $|V|=n,|E|=m$. I am reading a $\textit{brute force}$ solution to determining whether each candidate vertex cover of size $k \leq n$ is a vertex cover. The graph does not have loops.

As per page 2 of the notes here we have:

1) $C(n,k) = O(n^k)$ $k$-subsets of $V$
2) $O(kn)$ time to check whether a subset is a vertex cover

I am considering 2).

What I would think of would be to take each edge in our graph, for which there is a maximum of ${n \choose 2} = O(n^2)$, and check the candidate subset to see if at least one of the vertices is an endpoint of the edge, which would take $O(kn^2)$ checks.

I am not sure how the author arrived at $O(kn)$ operations, any insights appreciated.

The answer depends on the exact computation model and on the representation of the input. But here is one way to check whether a given subset is a vertex cover, assuming the graph is represented using adjacency lists.

Let the purported vertex cover be $S$, of size $k$. Start by counting all edges in $G$, stopping once you reach $kn$. If there are more than $kn$ edges, then $S$ is not a vertex cover, and we can stop. In time $O(|E|) = O(kn)$, you can count (1) $\sum_{i \in S} \deg(i)$ and (2) the number of edges connecting vertices in $S$. The total number of edges covered by $S$ is the difference between these two numbers, which you can compare to $|E|$.


Are $BPP^{BPP^{\oplus P}}$ and $BPP^{NP}$ contained in $BPP^{\oplus P}$? Does $BPP^{NP}\subseteq\Sigma_k^P\cap P/poly^{NP}\subseteq BPP^{\oplus P}$ hold at some $3\leq k<\infty$?
Also is $BPP^{BPP^{\oplus P}}\subseteq BPP^{\oplus P}$ known?

Note Sipser gives $BPP\subseteq \Sigma_2P$ and Adleman gives $BPP\subseteq P/poly$ and so I am tempted to say $k=3$ in $1.$ works. I am not sure relativization plays here.

Adelman's theorem relativizes, i.e. for every oracle $O$ we have $\mathsf{BPP^O\subseteq P/Poly^O}$. To see why you have to go over the proof of Adelman's theorem. The proof goes through showing that given a probabilistic machine with exponentially low error probability, there exists a sequence of coin tosses which produces the correct answer for all (fixed length) inputs. This remains true in the relativized world, use that coin sequence as the advice, and query the oracle whenever necessary while simulating the probabilistic machine with the coins given in the advice.

Additionally, $\mathsf{BPP^{\Sigma_i}}\subseteq \Sigma_{i+3}$. Again, you have to examine the details in the proof of $\mathsf{BPP\subseteq\Sigma_2}$. Suppose $L\in\mathsf{BPP^{\Sigma_i}}$, and $M$ is an oracle probabilistic Turing machine for $L$ with exponentially low error probability. You can use the same idea from $\mathsf{BPP\subseteq\Sigma_2}$, and claim that if $x\in L$ then the set of coin sequences who lead $M$ to accept is big, and in that case it can cover $\{0,1\}^m$ with a small number of shifts, where $m=poly(|x|)$ is the amount of coins used. Similarly, if $x\notin L$ you claim that the set of accepting coin sequences is small and cannot cover $\{0,1\}^m$ with a small number of shifts. All this remains true in the relativized world, as you only reasoned about the "BPP part" of $M$, i.e how it behaves with different coin tosses depending on whether or not the input is in $L$.

What's different is that when you find yourself in need to say "some vector $r\in\{0,1\}^m$ is obtained by shifting an accepting sequence", the part verifying that a sequence is indeed accepting will add additional $i+1$ quantifiers to the formula, after the initial two who talk about space shifting. To be more clear, your final formula has the form:

"$x\in L$ iff there exist shifts such that every vector $r\in\{0,1\}^m$ is obtained by performing one of those shifts on an accepting coin sequence for $x$", this is equivalent to:

"$x\in L$ iff there exists shifts such that every vector $r\in\{0,1\}^m$ can be shifted to generate an accepting coin sequence for $x$". Saying some vector $v$ is an accepting coin sequence requires expressing "$M$ accepts $v$" where $M$ is a poly time machine with access to a $\Sigma_i$ oracle. You can express this using a $\Sigma_{i+1}$ formula (this is analogous to $\mathsf{P^{\Sigma_i}\subseteq \Sigma_{i+1}}$).

The above shows that $\mathsf{BPP^{NP}\subseteq \Sigma_4\cap P/Poly^{NP}}$.
As for your second question, I don't know if there are complete problems for $\mathsf{BPP^{\oplus P}}$, so this might make the class $\mathsf{BPP^{BPP^{\oplus P}}}$ ill defined. One interpretation is asking whether the containment holds for every oracle in that class. I doubt this is known, but no obvious important/terrible implication comes to mind. Note that disproving this containment is out of the question, as it would immediately imply $P\neq \oplus P$.


NP-hardness for one-dimensional facility location problem with entrance fee for each customer We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note that these facilities can be located anywhere on the real line. Each facility $j\in [m]$ is associated with an entrance fee $f_j$, such as the ticket money for a swimming pool. Given a location profile $(y_1, \dots, y_m)\in \mathcal{R}^m$ for the facilities($(y_1, \dots, y_m)$ is not necessarily ordered), the cost for customer $i$ at facility $j$ is $c_{ij} = |x_i- y_j|+f_j$, which can be understood as the aggregate money of the travelling cost and the entrance fee when you taxi to a swimming pool and purchase a ticket to swim inside. And the customer will always choose the facility so as to minimize her cost.
Our goal is to find a location profile $(y_1, \dots, y_m)$ for the given $m$ facilities such that the total minimum cost
$$\sum_{i\in [n]}\min_{j\in [m]}c_{ij}$$
is minimized.
An easy but critical obserbation is that there is an optimal solution where each facility is located in the median agent of the continuous region of agents it serves. If we have identical entrance fees, we only need to find the optimal $m$ continuous partitions, which can be solved by dynamic programming in $O(mn^2)$. For the general case, similar DP algortihm runs in $O(2^mn^2)$. The algorithm, however, is exponential in $m$ and only makes sense after we've proved the problem is NP-hard. Another observation which may be helpful is that for if we have known the optimal $m$ continuous partitions, we just assign the facility of the $k$-th smallest entrance fee to the partition of the $k$-th most customers.
So is this problem NP-hard?  Or is there an algorithm running in polynomial time?
Update
Below is the detailed DP algorithms for the special case where all entrance fees are identical and the general case:

For the spcial case, denote by $M(i,j,k)$ the minimum total cost when customer $i$ is in the $k$-th partition and customer $j$ the right boundary of this partition. Depending on whether or not customer $i-1$ is still in the $k$-partition, we derive the following transition function:
$$M(i,j,k)=  \min\{M(i-1,j,k), M(i-1,i-1,k-1)+c(i,j)\}$$
where $c(i,j)$ is the minimum total cost of partition $[i,j]$, i.e., total cost for these customers when exact one facility is located in the median of $[i,j]$.
Obvious, this DP runs in $O(mn^2)$.

For the general case, the key difference is that we have to decide which facility is located in the rightmost partition since now facilities are heterogeneous. Similarly we denote by $M(i,j,F)$ the minimum total cost when customer $i$ is in the rightmost partiton, customer $j$ is the right boundary of this partition and $F$ is the set of facilities to be located. Similarly again, we can derive the following transition function:
$$M(i,j,F)=  \min\{M(i-1,j,F), \\ \min_{s\in F}\{M(i-1,i-1,F\setminus\{s\})+c^{\prime}(i,j,f_s)\}\}$$
where $c^{\prime}(i,j,f_s)$ is the total cost of $[i,j]$ when a facility with entrance fee $f_s$ is locate in the median of $[i,j]$.
This DP runs in $O(2^mn^2)$

$\require{cancel}$
The answer shows a reduction to the rainbow path problem and thus doesn't prove anything about the complexity of the given problem. See this paper which contains hardness results for related problems (theorem 2.3 states that rainbow s-t path is hard).
The problem is $\cancel{\text{still polynomial}}$, as it can still be reduced to some version of shortest path. Observe that there always exists an optimal solution where the facilities are a subset of $\{x_1,...,x_n\}$ (given an optimal solution and a facility $y_j$ in it, let $A_j$ denote the set of clients attending $y_j$, then replacing $y_j$ with the median of $A_j$ does not increase the value of the solution). Now construct a directed graph whose vertices are $V=\{s,t, v_{il}| i\in[n], l\in[m] \}$ and whose edges are given by:
$$E=\{(v_{il},v_{jk})| i<j\in[n], \text{and } l,k\in[m]\}\cup\{(s,v_{il})|i\in[n],l\in[m]\}\\\cup\{(v_{n,l},t) |l\in[m]\}$$
Interpret the edge $(v_{il},v_{jk})$ as choosing a solution where the clients $x_{i+1},...,x_j$ are members of the facility $y_k$. With this in mind, we set the weights of the edges to be:
$$
w(v_{il},v_{jk})=\sum\limits_{q=i+1}^j |x_q-m_{ij}|+(j-i)f_k\\
w(s,v_{il})=\sum\limits_{q=1}^i|x_q-m_{0,i}|+if_l\\
w(v_{n,l},t)=0, \text{ for all $l\in[m]$}
$$
Where $m_{ij}$ is the median of $x_{i+1},...,x_j$. An optimal solution for your problem is the weight of the lightest path from $s$ to $t$ of length $\le m$ which uses at most one edge from the set $E_i=\left\{(v,v_{l,i})|v\in V, l\in [n]\right\}$ for every $i\in[m]$ (this implies that we do not use the same facility twice). This version of shortest (lightest) path can be solved in polynomial time (think of it as having $m$ different color edges, and we want a path that does not use the same color twice, I believe that a sort of modified Dijkstra should work).


How to find a perfect matching with this constraint? I have a positive integer $n$ and two disjoint sets of nodes $V=\{v_1,\ldots,v_n\}$ and $W=\{w_1,\ldots,w_n\}$. I also have a weight function $f:V\times W\to\mathbb{R}_{>0}$ and a positive number $\alpha$. The function $f$ is represented by the matrix $\mathbf{F}=\left[f_{vw}\right]$ as:

$$\mathbf{F}=\begin{bmatrix}
f_{11} & \cdots & f_{1n} \\
\vdots & \ddots & \vdots \\
f_{n1} & \cdots & f_{nn} \\
\end{bmatrix}.$$

I would like to create a perfect matching between $V$ and $W$ (that is associate one node from $V$ to exactly one node from $W$) such that some constraint is satisfied (it is given explicitly next). Or, I am looking for a function $a:V\to W$ that is bijective between $V$ and $W$.

The constraint is specified by a matrix $\mathbf{G}=\left[g_{vw}\right]$ defined by: $g_{vw}=f_{va(v)},\forall v,w$. For example, if I have $n=3$, $v=\{1,2,3\}$ and $W=\{1,2,3\}$ and $\mathbf{F}$ is given by:
$$\mathbf{F}=\begin{bmatrix}
1 & 3 & 2 \\
4 & 7 & 1 \\
7 & 9 & 5 \\
\end{bmatrix},$$
and the bijection is $a(1)=2,a(2)=3,a(3)=1$. The matrix $\mathbf{G}$ will be:
$$\mathbf{G}=\begin{bmatrix}
3 & 2 & 1 \\
7 & 1 & 4 \\
9 & 5 & 7 \\
\end{bmatrix}.$$

Now, the constraint says that $\alpha\min\limits_{v}g_{vv}\geqslant\max\limits_{v\neq w}g_{vw}$. With the same example, if $\alpha=1$, the bijection $a$ does not satisfy the constraint since $\alpha\min\limits_{v}g_{vv}=1$ and there exists some $w\neq v$ such that $g_{vw}>1$.

In summary, I would like to find a bijection between $V$ and $W$, $a:V\to W$, such that
$$\alpha\min\limits_{v}g_{vv}\geqslant\max\limits_{v\neq w}g_{vw},$$
where $g_{vw}$ is defined previously.

We consider three different cases: $\alpha < 1$, $\alpha = 1$, and $\alpha > 1$.

Suppose first that $\alpha < 1$. Arrange the $n^2$ elements in the matrix in non-increasing order: $x_1,x_2,\ldots$. Note that $x_1,\ldots,x_n$ must belong to the diagonal, and moreover $\alpha x_n \geq x_{n+1}$. Hence the instance is solvable iff $\alpha x_n \geq x_{n+1}$ and $x_1,\ldots,x_n$ belong to different rows and columns.

The case $\alpha = 1$ is very similar. Let $x_1 = x_2 = \cdots = x_m > x_{m+1}$. If $m = n$ then we are back to the previous case. If $m < n$, then $x_1,\ldots,x_m$ must belong to the diagonal. We find out whether it is possible, fix this part of the permutation, and iterate (details left to you). The most interesting case is when $m > n$. In that case, we use a bipartite perfect matching algorithm to find out whether $n$ of these $m$ elements can be put on the diagonal.

The case $\alpha > 1$ is slightly more complicated. Let $A$ be the list of elements larger than $\alpha x_n$. All of these elements (if any) must belong to the diagonal in any solution, since the diagonal always contains an element at least as small as $x_n$. If $A \neq \emptyset$, we first check that they can be put in the diagonal, fix this part of the permutation, and iterate. If $A = \emptyset$, then we check whether the first $n$ elements can be put on the diagonal. If so, we have found a solution. Otherwise, we know that the solution must contain an element at least as small as $x_{n+1}$ on the diagonal, and we let $A$ be the list of these elements. If $A \neq \emptyset$, we do what we did before. Otherwise, we use a bipartite perfect matching algorithm to try and fit $x_1,\ldots,x_{n+1}$ on the diagonal (deleting first elements conflicting with the current partial permutation). If so, we have found a solution. Otherwise, we continue with $x_{n+2}$. Eventually we will have made a conclusion, since when reaching $x_{n^2}$ the answer is positive.


What is the time complexity of finding the residual network in this case? Here are the details:

(1) We are given a number $f$ of units of flow that we wish to transmit from the source node to the sink node. For example, $f=5$ units of flow (data or goods) should be transmitted from the source node to the sink node.

(2) We are not given any plan or policy to transmit the flow. However, we know that $f$ is less than the maximum flow of the network. So, it is possible to transmit such an amount of flow through the network.

(3) We are given the arcs' capacities.

$\bullet$ Now, it is required to determine the residual network after sending these $f$ units of flow.

Very simple:

Input: A network with the given arcs' capacities and an amount of flow $f$. Also, two nodes are specified as source and sink nodes.

Output: A plan to transmit $f$ units of flow from the source node to the sink node, and the corresponding residual network.

It is clear that there may be more than one plan to send $f$ units of flow through the network, and so the residual network may change. It is not important to reach a special residual network. My main concern is only to find the time complexity of such a job (finding a way to transmit $f$ units of flow through the network, and then determining the residual network).

It is easy to see that if I have the plan to send $f$ units of flow, the residual network can be determined with time complexity of $O(m)$, where $m$ is the number of edges in the network.

$\bullet$ I highly appreciate any help in advance.

The time complexity of this problem is (at most) the time complexity of the network flow problem.  You are given a graph and you want to find a flow of size $f$.  You can use any network flow algorithm for this.  Different algorithms have different running time.  Wikipedia has a list of algorithms, with their running times.  There is not a single optimal algorithm; different algorithms work better in different situations.

You mentioned you want to find a flow of size at least $f$, rather than a max flow.  Many of the algorithms for max flow can be adjusted to stop early when you've found a flow that is large enough.  Or, you can adjust the graph to ensure that a flow of size $f$ is a max flow -- if the original source vertex is $s$, add a new vertex $s_0$ and an edge $s_0 \to s$ of capacity $f$, then treat $s_0$ as the new source vertex and solve the max flow problem.

Once you find the flow itself, you can compute the residual network in $O(m)$ time.  For each edge, you compute how much remaining capacity it has (the capacity of that edge minus the amount sent by the flow); and you add a reverse edge if necessary (the amount of the flow).  This is $O(1)$ work per edge.  All known network flow algorithms take $\Omega(m)$ time.  Therefore, the time to compute the residual network once you find the flow is negligible; the bottleneck is finding the flow itself.


Is how much memory a program needs computable? We know that how much time a program needs is not computable.

Do we know how much memory a program needs is decidable?

No, and there's a simple way to see it.

Suppose that there was a way to compute how much memory a program needs. What does it mean precisely? It would mean that there's a way to find, given an arbitrary program¹, a number $n$ such that the program can run on a machine with $n$ bits¹ of memory.

First snag: what about programs that require an infinite amount of memory? Our memory analyzer would have to return something like $\infty$ in that case. Ok, that's not too bad — we could have an analyzer that returns either a (finite) amount of memory or $\infty$. If the program needs an infinite amount of memory, it doesn't terminate (each step of computation can only access a finite amount of memory).

If the memory analyzer returns a finite amount $n$, then we can run the program in a machine with $n$ bits of memory. But a “machine with $n$ bits of memory” is a finite automaton! Deciding whether a finite automaton terminates is easy.

So our memory analyzer has let us decide whether the program terminates. Since this is impossible (it's the halting problem), the hypothesis that there's a way to compute how much memory a program needs is false. If you have a correct memory analyzer (i.e. one that returns $n$ or $\infty$ if a program can run in at most $n$ bits of memory) then there must be programs for which the analyzer returns $\infty$, yet the program could in fact run in a finite amount of memory.

¹  A program including all of its inputs! The amount of memory is a function of the inputs in general.
²  You can use any unit, bits are just an example. That only changes the amount of memory from a finite number to a different finite number.


Applying DFS algorithm to a transition system to find reachable states Currently working on a past exam question which tells me to compute the product of two transition systems and then use DFS to find the reachable states of the product. I learnt how to compute the product of transition systems by looking at pages 43 and 44 in the "Principles of Model Checking" book by Christel Baier and Joost-Pieter Katoen (if anyone has a copy).

I understand that the way they found the reachable states in page 44 is by tracking the value of the variable y for each state and seeing if it holds, but in my particular question I'm not using a program graph; it's a transition system that uses only sigma and gamma (as handshake actions). My first question is how do I determine what is a reachable state and what is not in a product of transition systems?

Secondly, how would I show that I used DFS on paper? I couldn't find any useful articles online about it and our lecture notes don't cover it for some reason.

You can design an algorithm to traverse the product of two TSs.
With a simple DFS algorithm, start from start state and with rules for handshaking generate next states.
You need to keep the states that has been visited so far to avoid loop.
There may be more efficient ways but here is a sudo-code of a solution:

stack = new Stack()
visited_states = new Array()
stack.push(start_state)
while ~stack.isEmpty() {
    current_state = stack.pop()
    if current_state not in visited_states {
        visited_states.add(current_state)
        next_states = generate_next_states(current_state)
        for each state in next_states {
            stack.push(state)
        }
    }
}

Where generate_next_states is a function that generates next states according to the rule in page 48, Figure 2.11.
Now the set of states in visited_states are reachable states.


Are there any theorems/formulas that apply to the height of comparison trees? I have been drawing some binary comparison trees, which correspond to compares made to sort an array, and I was wondering if there is any formula to determine the height of a comparison tree for an array of N values, in Sedgewick's algorithms 4th ed. book for N = 3, the height of a comparison tree is 3.

He draws his comparison trees in such a way that all the internal nodes and the root represent the comparisons, for example (i:j) means compare a[i] to a[j], if a[i] < a[j] then the left subtree represents all the rest of the comparisons that we need to make, to finish the sort, and the leaves represent the permutations that we get after the sort. For example the left path for N = 4 is : (0:1), (1:2), (2:3), (0,1,2,3).

After I drew a tree for N = 4, the height was not 4, more specifically, an example would be the following path : (0:1),(1:2),(2:3), here a[2] > a[3] (3:1),(3:0),(3,0,1,2). So is there a formula?

In the example above we first find out that a[0] < a[1] < a[2] and then we find out that a[2] > a[3], so we need to compare a[3] to a[1] and a[0], so far the path length is 4, but then we add the leaf (3,0,1,2) and now the path length is 5.

Basically, we just need to look at the worst case comparison number, a worst case comparison number is when we  compare 1 with 2...N, then 2 with 3...N, etc. that will take (N^2 - N)/2 steps (arithmetic progression ((N-1)*(N-1+1))/2). So that's the height of that tree.

So for N = 3 we get (3^3 - 3)/2 = (9 - 3)/2 = 3. For N = 4 we have (4^2 - 4)/2 = 6.


Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language For regular languages $A,B\subseteq\{0,1\}^*$, is

$$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$

regular, where $|x|_1$  means the number of appearances of 1 in the word $x$?

i need to demonstrate $L_2$ automata.

Thought about using the multiplication automata, not so sure.

The idea is as follows:

We run two automata in parallel: one verifies that the input is in $A$, and the other verifies the other condition.
The second automaton simulates an automaton for $B$, in the following way. At any point in time it may simulate reading a $0$. It ignores all $0$s in the real input, and forwards all $1$s in the real input.

I'll let you construct an NFA given this description.


Does a turing machine halt with input left on tape? is the string aabb in the language of this Turing machine ?? as upon reading aa it goes to the final state but upon b there is no transition defined so won't it result in a dead configuration?

When a Turing machine enters an accepting state, it immediately stops running and accepts whatever the original input string was (regardless of the state of the tape). So given the input aabb, the Turing machine will read the two as and enter the accepting state $q_2$, at which point it will halt and accept aabb.

In this case it doesn't matter that there's no transition for reading a b from $q_2$ because we've already accepted (though you are correct in general that whenever we're running a Turing machine and we arrive at a state with no transition defined for the character we're reading, we implicitly go to a dead state and reject).


Computer cache - data removing I am programming CPU cache simulator and I am supposed to implement removing of entries. I will not use LRU but just random.

I am not really clear, when should I call the removing function? When cache (2 or 4 caches) are full and CPU wants to write into cache where all (data and tag) of specific indexes are same? Are there some other possible situations, or maybe I am completely wrong?

Hope you understand my question, if no, please tell me and I will edit my question. Thank you in advance.

Cache lines are evicted :

When the OS requests it, it may occur for example in non cache-coherent systems when a peripheral does a DMA transfer (direct transfer from a peripheral to main memory), or if the CPU is shut down to save its state to RAM...
When all the ways of the cache are already used for the requested line.

In a write-through cache, new data can be directly loaded, overwriting previous contents. In a write-back cache, if the cache line was modified, it must be written back before loading new data.

There could be other exceptional cases, for example if a parity error is detected and new data must be loaded...
But, generally, caches are filled but never emptied.


Can the notation for polynomial reduction, A ≤p B be reversed in computability theory? I don't know this is a proper question on this forum but I was reading about computability theory and I saw the reduction concept and its notation like this: $A \le_pB$. I just wanted to know is this notation can be reversed? that is, can I write this down like $A\ge_p B$ And still have a meaning? I searched a lot but this notation always been like the former and I got confused.

The notation $A \le_pB$ means problem $A$ can be reduced to problem $B$ in polynomial time, and that $B$ is at least as hard as $A$, because solving $B$ means solving $A$.

$A \le_pB$ $\equiv$ $B \ge_pA$

It does $\mathbf{not}$, however, mean $B \le_pA$, and to claim as much you would have to show the appropriate reduction.


Dijkstra's algorithm runtime for dense graphs The runtime for Dijkstra's algorithm implemented with a priority queue on a sparse graph is $O((E+V)\log V)$. For a dense graph such as a complete graph, there can be $V(V-1)/2$ edges.

Since $E \sim V^2$, is the runtime $O((V+V^2)\log V)$?

The runtime of Dijkstra's algorithm (with Fibonacci Heaps) is $O(|E|+|V|\log|V|)$, which is different from what you were posting.

If $|E|\in \Theta(|V|^2)$, that is your graph is very dense, then this gives you runtime of $O(|V|^2+|V|\log|V|)=O(|V|^2)$. A better runtime would be "surprising", since you have to look at every edge at least once.

When using binary heaps, you get a runtime of $O((|E|+|V|)\log|V|)$ which for $|E|\in \Theta(|V|^2)$ gives $O(|V|^2\log |V|)$.


Proof regular languages are closed under homeomorphism Let $\Sigma_1 , \Sigma_2$ be alphabets. Let $L\subseteq \Sigma_1^*$ be a regular language, and let $ h:\Sigma_1^* \rightarrow \Sigma_2^* $ be a homomorphism.
Proof $h(L)$ is regular.
I have written a proof using induction over the number of operands in the regular expression $r$ such that $L = L(r)$, that there exists a regular expression $r'$ such that $L(r') = h(L)$.
I divided it to three cases:

$r=r_1 \cup r_2$

$ r= r_1r_2$

$ r =r_1^*$

Since functions union might not always be a function (i.e $f(1)=1$, $g(1) =2$ $\rightarrow f\cup g$ not a function)
I would like to get your opinion for the union case, to verify I didn't do anything wrong there - especially in lines $5,6,7$:

$w\in h(L) \Leftrightarrow w = h(\sigma_1 \dots \sigma_n)\in h(L) \wedge \sigma_1 \dots \sigma_n \in L \Leftrightarrow $
$\sigma_1 \dots \sigma_n \in L(r_1 \cup r_2) \Leftrightarrow $
$\sigma_1 \dots \sigma_n \in L(r_1) \cup L(r_2) \Leftrightarrow $
$\sigma_1 \dots \sigma_n \in L(r_1) \vee \sigma_1 \dots \sigma_n\in L(r_2) \Leftrightarrow $
$h(\sigma_1 \dots \sigma_n) \in h(L(r_1)) \vee h(\sigma_1 \dots \sigma_n) \in h(L(r_2)) \Leftrightarrow $
$h(\sigma_1 \dots \sigma_n) \in h(L(r_1)) \cup  h(L(r_2)) \Leftrightarrow $

Now, using the induction hypothesis, since $r_1$ and $r_2$ has less operands,

$h(\sigma_1 \dots \sigma_n) \in L(r_1') \cup  L(r_2') \Leftrightarrow $
$w \in L(r_1' \cup r_2') $

Is this a valid proof for this case?

This proof looks correct. You can shorten it a bit (it doesn't need to be so descriptive), and you would get the following proof:
$h(L)=h(L(r_1\cup r_2))=h(L(r_1)\cup L(r_2)) = h(L(r_1))\cup h(L(r_2)) = L(r'_1)\cup L(r'_2)=L(r'_1\cup r'_2)$
Where the transition $h(L(r_1)\cup L(r_2)) = h(L(r_1)) \cup h(L(r_2))$ can be shown for any function $h$ (not necessarily a homeomorphism!).


How is Vertex Cover reducable to Independent Set using parametrized reduction with parameter k? We have the following Lemma and proof:

Lemma 5.5. If $A$ if FPT, then $A\leq_{\mathrm{fpt}}$ Independent Set.
Proof. We reduce $A$ to Independent Set parametrised by $k'$, where $k'$ is the size of a sought independent set. Given an instance $(x,k)$ of $A$,

solve $(x,k)$ in $f(k)\cdot \mathrm{poly}(|x|)$ time, (the running time of this reduction is using the running time of problem $A$)

if $(x,k)$ is a yes-instance, then output a one-vertex graph and $k'=1$.

if $(x,k)$ is a no-instance, then output a one-vertex graph and $k'=2$. (Could this need more time to compute?)

It is clear that the input instance is a yes-instance if and only if the output IS instance is, and $k'\leq k+2$. $\quad\square$

The definition of parameterized reduction is as follows:

Definition 13.1 (Parameterized reduction). Let $A,B\subseteq \Sigma^*\times\mathbb{N}$ be two parameterized problems. A parameterized reduction from $A$ to $B$ is an algorithm that, given an instance $(x,k)$ of $A$, outputs an instance $(x',k')$ of $B$ such that

$(x,k)$ is a yes-instance of $A$ if and only if $(x',k')$ is a yes-instance of $B$,
$k'\leq g(k)$ for some computable function $g$, and
the running time is $f(k)\cdot |x|^{\mathcal{O}(1)}$ for some computable function $f$.

Now it seems from what he did is: if $(x,k)$ is yes-instance, then output a one vertex with $k'=1$, otherwise if $(x,k)$ is no-instance, then output a one vertex with $k'=2$. This makes the first condition of Parameterized reduction true. Now,for second condition, we should say $k' \leq g(k)$ where $g(k)=1$ if we have yes-instance, and $0$ otherwise. The running time would be just the running time of the parameterized algorithm. Done.
My question is that when I want to do a reduction, I should take the input of $A$ (like vertex cover) and turn it to input of IS instance. For example assume we have clique of $4$, with $k=3$, the vertex cover algorithm will return a yes-instance, now if we want to turn this instance to IS to make it yes-instance, we need to use $n-k$. But he use different way. Also, when we prove IS to VC using parameterized reduction, it gives us wrong reduction (because of $n-k$ isn't a computable function of $k$). I just want to know here how "VC to IS" using parameterized reduction works.

It seems your confusion comes from the fact that Lemma 5.5 is a bit of a strange statement. In fact, we can replace Lemma 5.5 with the statement that for any problem $B$ such that $B_Y$ is a yes-instance of $B$ and $B_N$ is a no-instance of $B$ we have that $A\leq_{\mathrm{fpt}}B$. The proof of this adapted lemma is precisely the same as Lemma 5.5, only now we use $B_Y$ in the second bullet-point and $B_N$ is the third.

The crucial reason why this works is that we already know that $A$ is fixed parameter tractable. In a sense, this lemma shows that we learn nothing from a fpt-reduction from a problem we already know is fpt.

So, this lemma is in fact useless when trying to create a reduction from a problem we don't know is fpt, such as $k$-Clique.

When you try to apply Lemma 5.5 when $A$ is not fpt (or at least not known to be), you fail to satisfy part 3 of the definition of an fpt-reduction.


Using SMT solvers to generate random solutions to given predicate I am interested in generating random solutions to predicates. I only need SMT for integers with the following predicates/functions <, >, <=, >=, ==, !=, +, *

The algorithm I want should produce a random assignment of variables to values (a substitution) such that applying the substitution to the given predicate yields a true statement. In the UNSAT case I just need to know that it is UNSAT.

It is probably important to clarify what I mean by random. I think a sufficient definition is that there might be an extra parameter that acts as a seed. If I give a different seed the algorithm should give me a very different solution rather than the same solution. Frankly I'm not sure how to cash this out but it much the same way that a typical random number generator generates an integer between X and Y (well with a modulus and an addition anyhow) I'd like to generate to a wider class of predicates.

I would like to use existing SMT solvers ideally in either Haskell or the JVM stack (more ideally Haskell however). I have thought of basically just randomizing the DPLL algorithm and translating the SMT problems into SAT my self but that sounds like a terrible idea when really good existing SMT solvers exist.

Let $\varphi(x)$ be the SMT instance, so the task is to find $x$ such that $\varphi(x)$ is true.

One approach is to fix a hash function $h$ that maps a value of $x$ to an element of some small set $S$.  Then, you randomly select a value $s \in S$, and ask your SMT solver to find a satisfying assignment for the formula $\varphi(x) \land h(x)=s$.

If you want to generate $k$ random satisfying assignments to $\varphi(x)$, you might choose $S$ to have size a bit bigger than $k$; that will probably suffice.

You probably want to make the hash function $h$ as simple as possible.  There is a tradeoff between a simpler hash function (easier for the SMT solver to find satisfying assignments to $\varphi(x) \land h(x)=s$) and a better hash function that mixes the bits better (leads to more random solutions $x$).  In practice, often surprisingly simple hash functions suffice.  For instance, sometimes your hash function can be chosen via the following simple procedure: pick a random subset of the variables in $x$, project to just those variables, and then hash those variables in some simple way.  The hash function itself can be a relatively simple function, e.g., a random linear function: for example, select a random boolean matrix and multiply it with the bit vector obtained from $x$, so that $h(x)=Mx$ for some boolean matrix $M$).

There may be other ways to do it, but this is one way that allows you to use an existing SMT solver, unmodified, as a black box.


Best split with conditions Given this sort of dataset:

ID
Score1
P1
Flag

id1
0.01
0.2
False

id2
0.99
0.9
True

...
...
...
...

The limitations of each variable are:

ID: identifier if each object, unique in the table
Score1: A number between 0 and 1, that represent the value of the object
P1: probability of call, betwen 0 and 1
Flag: should the object be in group <b?

I want to split the dataset in 2 groups (A and B) given the rules:

The sum of P1 on group A should be at least n
The sum of P1 on group B should be at least m
The diference between the average Score1 in the two groups should be minimal
The average of Score1 on all the selected (group A + group B) should be maximum
We don't have to select all the rows
Rows with Flag = True can not be in group A

How can I do this in a smart/fast way?

There is no efficient algorithm to do what you want, unless P=NP.
In fact, there is no efficient algorithm do even decide whether a feasible partition of the dataset into two groups exists.
You can see this by reducing from the partition problem:
Given a (multi-)set of positive numbers $X=\{x_1, x_2, \dots, x_n\}$ we want to decide whether there exists a subsets $S$ of $X$ such that $\sum_{s \in S}  s= \frac{1}{2} \sum_{x \in X} x$. Without loss of generality we can assume that $0 < x_i \le 1$ (by simply dividing all $x_i$ by $\max_{i=1, \dots, n} x_i$).
Then, for each $x_i \in X$ you can create a row in your dataset with:

ID = $i$;
Score = $0$;
P1 = $x_i$;
Flag = false.

Finally, pick $n = m = \frac{1}{2}\sum_{x \in X} x$.
A feasible parition into two groups $A$ a and $B$ induces a subset $S$  such that $\sum_{s \in S}  s= \frac{1}{2} \sum_{x \in X} x$.
Specifically if $i_1, i_2, \dots, i_k$ are the IDs of the rows selected into $A$, you can define $S = \{x_{i_1}, x_{i_2},  \dots, x_{i_k}\}$.
Conversely, given a set $S = \{x_{i_1}, x_{i_2},  \dots, x_{i_k}\}$ such that $\sum_{s \in S}  s= \frac{1}{2} \sum_{x \in X} x$, you can select $A$ as the set of rows with IDs in $\{i_1, i_2, \dots, i_k\}$ and $B$ as the set of rows not in $A$.


Interpretation of Backtracking Algorithm Problem - weighted matching I am attempting to resolve the following problem using Backtracking:

  Suppose that you have $n$ men and $n$ women and two matrices P y Q (n x n); such that $P_{ij}$ is the preference of the man $i$ for the woman $j$ and $Q_{ij}$ is the preference of the woman $i$ for the man $j$.

  Depict an algorithm that follows the Backtracking technique to find the pairs of men and women whose sum of the products of the preferences are the highest possible.
  With help from the matrices
  $P = \begin{bmatrix}
1 & 3 & 2 & 0 \\
2 & 4 & 3 & 1 \\
0 & 3 & 1 & 2 \\
3 & 4 & 2 & 1 \\
\end{bmatrix}
$
  and
  $Q = \begin{bmatrix}
0 & 1 & 2 & 3 \\
4 & 3 & 2 & 1 \\
4 & 2 & 3 & 1 \\
3 & 1 & 4 & 2 \\
\end{bmatrix}
$
  and represent the exploration tree of the exploration of the search space of the solution. Indicate:

  How will you represent the solution and based on that, what are the restrictions of the problem and how will you calculate the value of the objective function.
  In the process of ramification, what will represent the levels and how will you generate the children of each node.

  Analyze the time complexity of the algorithm.

I have the basic ideas of how backtracking works but I am having trouble interpreting the problem. What does it mean by ... the sum of the products of the preferences ...?

Suppose man $i$ is paired with woman $w(i)$, for $1\le i\le n$.

"The sum of the products of the preferences" is the following number.

$$ P_{1,w(1)}Q_{w(1), 1} + P_{2,w(2)}Q_{w(2), 2} + \cdots + P_{n,w(n)}Q_{w(n), n} $$

One can imagine that each individual product $P_{i,w(i)}Q_{w(i),i}$ quantifies how preferred is the pairing between man $i$ and woman $w(i)$.


Advantage of using generating functions in analyzing an algorithm I'm reading through the first chapters of "Introduction to the analysis of algorithm" by Sedgewick. I wasn't familiar with the use of generating functions, and complex analysis in general to analyse algorithms. I do understand the use of the tool is in practice simple (at least it seems to me in that way from what I read so far).

I still don't get though what's the particular advantage of using a generating function over standard techniques of difference equations when analysing some recurrence extrapolated by some algorithm.

What's the benefit of using generating functions?

I can also see "analytic combinatoric" as topic, I haven't read through that yet, what's the advantage of that formalism instead? Is there some case where analysing in that way is really easy while using standard technique isn't?

Generating functions can be used to solve recurrence relations more complicated than linear recurrence relations with constant coefficients. As an example, let us consider quicksort (credit: lecture notes of Rezaul A. Chowdhury). Let us denote by $t_n$ the average number of comparisons performed by quicksort when the pivot is chosen at random. We have $t_0 = 0$ and for $n \geq 1$,
$$
t_n = n-1 + \frac{1}{n} \sum_{k=1}^n (t_{k-1} + t_{n-k}) = n-1 + \frac{2}{n} \sum_{k=0}^{n-1} t_k.
$$
Some work shows that the generating function $T(z)$ of the $t_n$ is
$$
T(z) = \sum_{n=0}^\infty t_n z^n = \frac{2\log \frac{1}{1-z} - 2z}{(1-z)^2}.
$$
From this it is not hard to extract the formula
$$
t_n = 2(n+1)H_n - 4n.
$$

In this particular case, there are more direct ways to calculate $t_n$. However, in more sophisticated situations, such tricks might not work. Furthermore, generating functions lead to mechanical manipulations - in fact, a software package can probably convert the recurrence for $t_n$ to the generating function, and hence to the exact expression. In this sense, generating functions generalize linear recurrence relations with constant coefficients by providing a large class of recurrences whose asymptotics can be ascertained.


Big O running time for this algorithm? Here's the code for the algorithm:

Foo(n)
   lcm = 1
   for i = 2 to n
       lcm = lcm*i/Euclid(lcm,i)
return lcm

The running time of Euclid$(a, b)$ is given as $O(\log(\min(a, b)))$

So the running time of the for loop will be $O(n)$, so would this be the final running time? or do I have to take the $O(\log(\min(a, b)))$ into account as well?

The running time for the loop will be
$$ O\left(\sum_{i=2}^n (1+\log \min(\operatorname{lcm}(1,2,\ldots,i-1),i))\right). $$
The $1$ takes care of the arithmetic operations beyond GCD, and the other term is the running time of GCD, as given to your. The arguments to GCD are lcm and i. The value of lcm at iteration $i$ is $\mathrm{lcm}(1,2,\ldots,i-1)$, explaining the complete formula.

We can upper bound this sum by
$$ O\left(\sum_{i=2}^n (1 + \log i)\right) \leq O\left(\sum_{i=2}^n (1 + \log n)\right) = O(n\log n). $$


Give an example of a connected graph where α(G) =100 and β(G) = 200 So I need to find a form of a graph such that its vertex cover is twice that of its matching, but I am running into problems brainstorming, I know K3 is of this form, but not one at such a magnitude.

You are on the right track, just keep going: what if you take a slightly larger complete graph? Specifically, what if you take a $K_{101}$?


Prove that my NP-complete problem is strong I have two problems, one of which is solved using dynamic programming. I showed that it is NP-complete (a knapsack variant), therefore having this dynamic programming solution says that this one is weakly NP-complete. Right?

Then, in the second problem I have added a new dimension to the problem which makes is more complicated. It is still NP-complete and I assume that this one is strongly NP-complete.

Is there a way to prove that it is 'strongly' NP-complete?

Update:

I can show that the second problem needs to solve $2^n$ instances of the first problem, where $n$ is the size of problem.

You've asked two questions.  To answer the first question:

Not quite right.  It depends on the running time of your dynamic programming algorithm.  To show that the problem is weakly NP-complete, you should show that there is an algorithm whose running time is polynomial if the input is represented in unary.  So, you'll first need to prove that your dynamic programming algorithm has that property.

To answer the second question:

If in doubt, go back to the definition.  Wikipedia has a page with a definition of strongly NP-complete; it says

  A problem is said to be strongly NP-complete (NP-complete in the strong sense), if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the input.

So, that's what you need to prove.  It's hard to say much more without knowing what the specific problem is.


Wanted: Concrete Example of Busy Beaver Holdout I understand from the Wikipedia page on the Busy Beaver problem that the Busy Beaver values for 5-state 2-symbol (quintuple) Turing-machines have not been determined, because there are 'holdout' machines whose halting behavior is as of yet unknown.

Can someone provide me with a concrete example of such a 5-state 2-symbol current (or as close to 'current' as possible) 'holdout'? When looking around on the net, I am finding lots of 'champions', but never any 'holdouts'. Does someone have one or more examples, please?

Thanks!

EDIT

THe linked question asked about 'short programs', but this question is specific to Turing-machines and the Busy Beaver problem. And yes, while that question solicited a response with two Busy Beaver Holdouts of the right kind (Thanks Ricki!), the source provided is 27 years old ... I would like to be able to point to any of these machines and say that these are 'current' holdouts, so if anyone can tell me whether these are still holdouts, or knows of any other, more current, holdouts, I would appreciate it. So, I am holding out for someone who maybe has some more current knowledge regarding the status of these busy beaver holdouts. Thanks!

Skelet has 43 holdouts (those with type = ----).
At least No. 827123 (the very first in the lists) is still open, afaik.
My "feeling" is that all but 6 (no idea, which!) have been shown to be infinite.
Good luck!
http://skelet.ludost.net/bb/nreg.html
No info on actual holdouts, but state-of-the-art in several aspects:
https://www.scottaaronson.com/papers/bb.pdf
These are the 43 holdouts according to Skelet:
Nonregular machines:
    A0  A1   B0  B1   C0  C1   D0  D1   E0  E1   |    id    |

    C1L E1L  H1L D1L  D1R D0L  A1L E1R  B0L C0R  |   827123 |
    C1L E0R  H1L C0R  D1R A0L  A1R D1R  A1L B0R  |  1668912 |
    C1L A0R  H1L E1L  D1R B0L  A1R C1R  C0L D1L  |  2523420 |
    C1L D0R  H1L E0L  D1R C1L  E1L A1R  B1L D0L  |  3911891 |
    C1L A1L  H1L D0L  D1R E0L  A1L C0R  C1R B0L  |  6311798 |
    C1L B0R  H1L D0R  D1L A0R  E1R C0L  C1R E1R  |  7224038 |
    C1L B0R  H1L E1R  D1L A1L  A1R D0L  A0R C1R  | 11799516 |
    C1L B0R  H1L C0R  D1L C0L  E0R C1L  A0R E1R  | 11997798 |
    C1L D1R  H1L C0L  A1R C1L  E1R A0R  B1L E0L  | 18119527 |
    C1L A0L  H1L C0L  D0R A1L  B1L E1R  D1R E0R  | 21181509 |
    C1L A0L  H1L A0R  D0R A1L  E0R D1R  A1L B0R  | 22109761 |
    C1L E0L  H1L E1L  D0R A1L  A0L C1R  C1R B0L  | 22600133 |
    C1L B0R  H1L A1R  D0L E1R  E0R C1L  C1R A0R  | 25621006 |
    B1L H1L  C1R E0R  D1L B0R  D0L A1L  C0R A0L  |  5359517 |
    B1L H1L  C1L B1R  D1R E1L  B1R D0R  A1L C0L  |  6594274 |
    B1L H1L  C0R D1L  D1R C1R  E1L E0L  A0L B0R  | 11530505 |
    B1L H1L  C0R E1L  D0R C1R  A1L B1R  B0L A0L  | 11679832 |
    B1L H1L  C0L D0R  D1L E0R  E1L A0L  C1R D0R  | 14576100 |
    B1L H1L  C0L B0L  C1R D0R  A1L E0R  A0R E0R  | 15076017 |
    B1L H1L  C0L D1L  D0R C1L  E1R A0L  A1L E0R  | 15764213 |

    A0  A1   B0  B1   C0  C1   D0  D1   E0  E1   |    id    |

    C1L E1L  A1L H1L  D1R E0R  B1R E1R  C1R A0L  |   123831 |
    C1L E0L  A1R H1L  D1R A0L  D0R B1R  C0L B0R  |  3198755 |
    C1L C0R  D0L H1L  D1R E0L  C1L E0R  A1R B1L  |  5585454 |
    C1L A1L  E1R H1L  D1R D0R  B0R E0L  A0L C1R  |  6314131 |
    C1L A0R  A1L H1L  D1R E1L  A1R D0R  E0L B0R  |  6929003 |
    C1L E1R  D1R H1L  D1L C0L  A1R D1L  B1R A0R  | 12568936 |
    C1L E0L  D1R H1L  B1L E1L  A1R E1R  A1L D0R  | 17982461 |
    C1L D0R  A0L H1L  A1R D0L  E1R B1L  C1L C0R  | 23741566 |
    C1L E0L  C1R H1L  D0R A1L  A1R E0R  B1R E0L  | 30515821 |
    C1L B0R  E0R H1L  D0L C1L  E1L C0L  A1R C0R  | 33424333 |
    C1L E0R  C0L H1L  D0L B0L  D1R A0R  A1R D1L  | 33938206 |
    C1L D1R  E1R H1L  D0L C0L  B1R A0R  A1R E1L  | 34364505 |
    C1L D1R  E1R H1L  D0L C0L  B1R A0R  A1R A1L  | 34429669 |
    C1L D1R  E1R H1L  D0L C0L  B1R A0R  A1R A0R  | 34508331 |
    C1L E1R  D1R H1L  D0L C0L  B1R A1L  D1L A0R  | 34605254 |
    C1L B0R  C1R H1L  D0L D0R  A1R E0L  D1L E1L  | 36278670 |
    C1L C0L  D1L H1L  B0L D0R  E0R A1L  A1R E1R  | 40470734 |
    B1L D1L  C1R H1L  E1R D1R  E1L C0R  A1L D0L  | 43710027 |
    B1L A0L  C1R H1L  C0R D0R  E1L B0L  E0L A1L  | 45963385 |
    B1L A0R  C1L H1L  D0L E1R  E1L A0L  C1R A0R  | 50233205 |
    B1L E0R  C1L H1L  D0L C0L  D1R A0R  B0R E0R  | 50317033 |
    B1L A0R  C0L H1L  C1R D1L  E1L A1R  B0L D0R  | 54769539 |

This page was last modified at 16 May 2003.
(c) Skelet, May 2003 in terms of GNU GPL


How to work out the odd case? I am trying to solve this by using Substitution method. My solution must work both for even n-s and odd n-s. For evens case I have solved it. But for the odd's case I am stuck at this point. Hot to continue?

If you have a solution for all even numbers, it might be sufficient to realize $T(k+1) \ge T(k)$.
But generally this is proved by induction where the even numbers use the odd ones. There, you have two leads :

Take good care of your bounds during your induction
More simple (but with less efficient approximation) : prove it for powers of two with a given constant ; and then use those to prove the general case for another constant


Complexity Class of an Algorithm with two Inputs Consider a problem with two inputs like (P,L) and |P|=n and L is some positive integer. If my algorithm had a complexity of O(n^L), would that still be polynomial? Or is it exponential? I'm not sure if I should view L as a constant or as 'size of input', since it's not a size but just some number (as in, Knapsack for example, select items of weight <= L). At the same time, L is part of the input and not fixed.

You're confused because you've called part of your input $n$. When we say that the running time is some function of $n$, we almost always mean that $n$ is the length of the input string.

Your algorithm runs in time $|P|^L$, where $P$ is a string contained in the input and $L$ is a number represented in the input, presumably in binary.  If $L$ is a $b$-bit number, it could be as big as $2^b$.  Writing $n$ for the length of the input, we could, for example, have $|P|=n/2$ with $L$ being an $(n/2)$-bit number.  That case gives running time $(n/2)^{2^{n/2}}$, which is a long, long way from being polynomial.


implementing permutation and combination recursively I am still in the early phase of getting comfortable with solving recursive problems. I was given
int p(int n) // number of permutations of n objects
int c(int n, int k) // number of unique combinations of k elements out of n elemnts

For instance, {"abc"} as the given string, permutation will be
{"abc"}, {"acb"}, {"bac"}, {"bca"}, {"cab"}, {"cba"}. However, combination (order does not matter) will be just simply {"abc"}.

A detail representation of Combination by using Pascal's Triangle from Eric Roberts' book.

I am having a hard time seeing how this pascal's triangle representation relate to the idea of combination.

My initial thought process was based on each of their formulae and using factorial to solve the problem. Clearly, that's not what I was asked to do. I was supposed to define them recursively and implement the recursive definitions for both counting techniques. So, basically, I am unable to solve the two functions without getting the help of factorial.

The number of permutations of $n$ distinct objects is $n!$.
The number of $k$ selections out of $n$ distinct objects is $\binom{n}{k}$ known also as a binomial coefficient. Recursive definition of these numbers are trivial:
$$n! = n(n-1)!$$
$$\text{so if } f(n) = n! \text{ then } f(n) = n\times f(n-1), f(0) = 1$$
For binomial coefficients
$${\binom {n}{k}}={\binom{n-1}{k-1}}+{\binom{n-1}{k}}$$
or
$$ b(n,k) = b(n-1, k-1)+b(n-1, k)$$
where
$$b(n,n)=1 = b(n,0)=1 \text{ and } b(n,k)=0 \text{ for } n < k$$

If you want approximate value without too much computation then you may check the Stirling's approximation.

Proof of $${\binom {n}{k}}={\binom{n-1}{k-1}}+{\binom{n-1}{k}}$$
You can prove it using a combinatorial argument or algebraic. The algebraic one is tedious (you need to manipulate factorials). So let's consider a combinatorial proof.

Assume we have $n$ people, numbered from $1$ to $n$, and want to create a team consisting of $k$ people. There are exactly ${\binom {n}{k}}$ ways to create a team, i.e, $k$ people out of total $n$. Consider the first member, number $1$. There are two possibilities: either include her or leave her out.

If we choose that member then we need to choose additional $k-1$
people out of remaining $n-1$ people which is equal to $\binom{n-1}{k-1}$.
If we leave that member out then we have to select $k$ out of $n-1$
people which equal to $\binom{n-1}{k}$.

Since these both options result in different teams the total number of teams is
$$\binom{n-1}{k-1} + \binom{n-1}{k} $$


How are image processing and computer vision related to artificial intelligence.? We have often heard both terms image processing and computer vision in AI sessions

But i am confused, how they both are related to artificial intelligence?

The answer is simple.

Assume you are making a robot for interacting with other people. The first thing that it needs is to recognize people who it sees.

Another application is in self-driving cars. If the car is not able to see the road and read the signs or break when it sees a dangerous obstacle ahead, how could it drive in a safe way?

There are a lot of smart agents who need to see an recognize a scene or a person and many other applications; this is where computer vision and image processing come handy. One of the best techniques that is used in Computer Vision is machine learning which is one of the cutting-edge methods in AI.


Runtime for algorithm I need to get the asymptotic runtime for an algorithm and I'm just stuck.

A python implementation:

def alg3(n):
    for i in range(1, n+1):
        for j in range(1, n+1):
            k = j
            while k <= n:
                k = k*3

I think it should somehow be $\Theta(n^2\log(n))$ but that isn't quadratic.
Can you help?

import time

def alg3(n):
    count = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            k = j
            while k <= n:
                count = count + 1
                k = k*3
    print(count)

n = 10
for i in range(0, 6):
    start_time = time.time()
    # run two times then calculate average time
    for i in range(0, 100):
        alg3(n)
    print("time with size %s: %s seconds" % (n, (time.time() - start_time)/100))
    n = n*2

If you calculate the factors given they give about 4.1.

Let $f(n) = n^2\log n$, with the $\log$ taken to base 2. Then
$$
\frac{f(2n)}{f(n)} = 4 \frac{\log(2n)}{\log n} = 4 \left(1 + \frac{1}{\log n}\right).
$$
That is, for large $n$ you would expect $f(2n) \approx 4f(n)$. This shows that this test isn't sensitive enough to detect logarithmic factors.