Are there any problems in complexity class EXP that are not in NP? I cannot conceive of any problem that can be solved in exponential time, but cannot be checked in polynomial time.

First of all, we don't know whether $NP=EXP$ or not. So the initial answer is "it is an open question".

However, we strongly believe (and there are supporting evidence) that $NP\neq EXP$. In fact, we believe that $NP\neq PSPACE$ and that $PSPACE\neq EXP$ (that is, there is a strict containment $NP\subsetneq PSPACE \subsetneq EXP$).

Since you are looking into problems that cannot (to our knowlendge) be verified in polynomial time, you can start with any PSPACE complete problem. For example, TQBF, or $ALL_{NFA}$. If you want EXP-complete problems, there are examples here.


Interrupt enabling and disabling While reading about interrupt mechanism, I understood that there is an IRQ signal line on the bus by which an I/O interface
raise an interrupt request.
There is an INTA signal line using which the processor indicates acceptance of to the interrupt request.The processor interrupts the program currently under execution, saves the current PC & PS in the stack and transfers control to the ISR meant for the I/O device concerned.
After completion of execution of the ISR the processor restores the saves PC & PS so as to resume execution of the interrupted program.
But can anyone help me to understand in depth about the mechanism for interrupt enabling and disabling.

The process that you've described happens only if interrupts are enabled. The IRQ request (via INTR line) asks the CPU to handle the interrupt. If the CPU accepts, it will issue an INTA as you describe.
The CPU doesn't always accept interrupts. For instance, if the CPU is "in the middle of something", then it might delay handling the interrupt (for instance, until the instruction which is currently being executed, finishes). Additionally, the CPU has an internal flag that indicates whether or not is should accept interrupts. In the x86 family, this is the IF (interrupt flag), and you can control it by the commands STI (set interrupt flag == enable accepting interrupts) and CLI (clear interrupt flag == disable accepting interrupts). In other CPUs the naming might be different or there might be a more sophisticated mechanism setting/clearing interrupts of specific type/priority.
If the IF is cleared and interrupts are disabled, the CPU just "ignores" the input INTR line. This is known as masking interrupts. The CPU just continues as if the INTR line is low... Once you set the IF, then the CPU will stop ignoring the interrupt and will handle it according to the standard procedure (save flags and return address, and jumps to the ISR, issuing INTA, etc.)
Just to make it clear, enabling/disabling interrupt does not change the way the external I/O creates the interrupt. It just changes the way the CPU behaves in case of an external interrupt: if enabled, the interrupt is processes. If disabled/masked, interrupts are ignored.


Is this a regular grammar? I went through a question asking me to categorize the following grammar.

$$S → AA, S → AB, A → a, A→BB, B → b, B → e$$

From the production rules, clearly it is Context-Free. But it accepts a finite set of strings.
$\{e, a, aa, ab, abb, ba, bba, b, bb, bbb, bbbb\}$
which is regular language.

So, is the above grammar regular? Though it does not follow from the rules.

Basically my question is: Is the grammar $\{S → AA, A → a\}$ regular?.

The answer is no. Whilst the language is finite and therefore regular the grammar itself is not regular. I think you already knew this as you said that this grammar's production rules are not of the form of a regular grammar.

The point here is that just because a grammar isn't regular doesn't mean the language it generates must not be regular.


What is the difference between cyber security ontologies and scenario ontologies in this system? I have been reading the paper Towards a Cognitive System for Decision Support in Cyber Operations. And I have been trying to understand the role of two ontologies proposed here, cyber security ontologies and scenario ontologies.

I have asked a question on CGS SE, What are the practical uses of ontologies? and the role of the ACT-R architecture in this system have become clear to some extent, but the question about the ontologies is that:

Does the cyber security ontologies make the ideas in the TENA's Repo understandable for ACT-R or the ideas that are in the repo has to be represented by an ontology called cyber security ontologies in order to be understandable for the ACT-R architecture?

The Cognitive System realized in the TENA framework:

Questions raising from this Figure can be:

What is the difference between the cyber security ontologies and the scenario ontologies?
What kind of knowledge the scenario ontologies represent?
And of course what is the reason that the scenario ontologies are connected to Event data management module instead of TENA's Repo?

ACT-R Architecture:

TENA Architecture:

Some more detail can be found p97. Here "ontologies" are basically encodings of database contents (which represent cyber attacks, incidents, and malicious/ impacted software programs) parseable by external sources, e.g. ACT-R. The event data management system keeps track of (real) attacks/ incidents, or possibly simulated ones. TENA is a Testing and Training Enabling Architecture. In a sense the Cyber Security Ontologies are all the "Nouns", and the Scenario Ontologies are "Verbs" that operate on the Nouns. ACT-R takes these inputs and attempts to create a conceptual linking or model. In a sense the ACT-R is a machine learning system for cyber-attack-related events and entities. It is a framework for outputting a (maybe statistical) analysis that could be used to predict future attacks from the structure of past ones.

  The need for controlled vocabularies, taxonomies, and
  ontologies to make progress toward a science of cyber security
  is recognized in [26] and [27] as well. In the domain of cyber
  security, the ontologies would include, among other things,
  the classification of cyber attacks, cyber incidents, and
  malicious and impacted software programs. From our point of
  view, which seeks to accurately represent the human-side of
  cyber security, we also expand our analysis to: (i) the different
  roles that system users, defenders and policy makers play in
  the context of cyber security; (ii) the different jobs and
  functions that the members of cyber defender team play and
  the knowledge, skills and abilities needed to fulfill these
  functions. In order to reduce the level of effort, we will reuse
  existing ontologies when possible6 and only create new
  ontologies that support the use cases we select.


Tree with branching factor 1 Something that has been bothering me for a while is the formula for the maximum amount of nodes of a tree with height d and branching factor of b.

$$(b^{d+1}-1)/(b-1)$$

This holds true for all positive integer values of b, including 0, with the exception of b=1.

If b = 1, we would be dividing by 0. Which, well, we all know is not a "legal mathematical move". However, if b = 1, the number of nodes would be equal to the height of the tree + 1.

I'm not sure exactly what my question is. I just feel like it's weird that a tree with branching factor 0 would have 0 nodes, a tree with branching factor 2 would have $$(b^{d+1}-1)/(b-1)$$ nodes
,
but calculating the number of nodes of a tree with branching factor 1 would be impossible using the same formula.

I don't know what I'm missing. Why isn't there a formula that calculates all nodes in a tree that includes branching factor 1 (or rather, why doesn't this formula include b = 1?)? Or does a tree need a branching factor that is anything else than 1 (but larger than -1?) to qualify as a tree? I'm a bit confused. Help is greatly appreciated.

(Not sure if I got all the facts right here. Please forgive me if I didn't)

The formula you state follows from summing a geometric series:
$$
1 + b + b^2 + \cdots + b^d = \frac{b^{d+1}-1}{b-1}.
$$
When $b=1$, the series sums to $d+1$, which is also the limit of the expression above as $b\to1$.

As you mention, the formula is only meaningful when $b \neq 1$, though the correct value can still be recovered by taking a limit. This is perhaps the simplest example of a curious phenomenon in combinatorics, that of the "field with one element". Consider the following two quantities:

The number of subsets of size $k$ of a set of size $n$. These are counted by binomial coefficients $\binom{n}{k}$.
The number of $k$-dimensional subspaces of an $n$-dimensional vector space over the finite field with $q$ elements. These are counted by Gaussian binomial coefficients $\binom{n}{k}_q$, which are rational functions (ratios of two polynomials) in $q$.

The curious thing is that if we substitute $q=1$ in the expression for $\binom{n}{k}_q$, we get back $\binom{n}{k}$ in the limit. (Just as in your case, when $q=1$ the denominator vanishes.) So a set is similar to a vector space over "the field with one element".

More generally, there are other formulas involving "$q$-analogs" (sets replaced with vector spaces over the field with $q$ elements) which degenerate to the correct values when taking the limit $q\to1$. There are some explanations for this phenomenon but it is still somewhat mysterious.


Conversion of $\epsilon$-NFA to a DFA So, I was watching a video about the conversion of $\epsilon$-NFA to a DFA. In the resulted DFA, she didn't write the state 4 in any successor set of the sets containing the state 3, and her explanation was that this happens because the state 3 has no outgoing transitions that are labeled with letters from $\Sigma$ in the input NFA. See the following image.

So my question is, if the state 3 had an outgoing transition labeled with 0 in the input NFA (see the 2nd image below), then does the state 3 contribute the states 2,4,5, and 6 in the successor set upon reading the letter 0?

What she actually describing is the following construction.
For an $\epsilon$-NFA  $ A = \langle Q, \Sigma, \delta, Q_0, F \rangle$, the intuitive idea is as follows. Consider a state $q$. If there is an $\epsilon$-transition from q to $s$, then whenever we reach q, we can also reach $s$. Yet, there may be $\epsilon$-transitions from $s$, so we also need to take them into account.
For every state $q\in Q$, let $EC(q) \in 2^Q$ be the $\epsilon$-closure of $q$ which is formally defined as
$EC(q) = \{s \in Q: \text{ $s$ is reachable from $q$ using only $\epsilon$-transitions}\}$. In particular, for every state $q\in Q$, $q\in EC(q)$ as a state is reachable from itself by a path of length
0.
Now Given the sets $EC(q)$ for every state $q \in Q$, we define the DFA B as follows.
$B = \langle 2^Q, \Sigma, \kappa, \bigcup\limits_{q\in Q_0} EC(q), \{S\in 2^Q: S\cap F \neq \emptyset\}\rangle$, where
$\kappa(T, \sigma) = \bigcup\limits_{q\in T} \bigcup\limits_{s\in \delta(q, \sigma)} EC(s)$, for every set of states $T\in 2^Q$, and letter $\sigma \in \Sigma$. That is, given a non-$\epsilon$ transition $\langle q, \sigma, s \rangle$, we move not only to $s$, but also to all the states that are reachable from $s$ via $\epsilon$-transitions.
So indeed, in the first attached image, the state $3$ has no outgoing transitions that are labeled with letters from $\Sigma$, and thus, for every set $T$ that contains state $3$, the state $3$ does not contribute any states in the set $\kappa(T, \sigma)$, for every letter $\sigma$. However, in the 2nd attached image, there is a 0-labeled transition going out from the state 3. So, in the DFA $B$, when you read the letter 0 from a set $T$ that contains the state $3$, then the state $3$ contributes the states $\kappa(\{3\}, 0)$ in $\kappa(T, 0)$. Now since $\delta(3, 0) = \{4\}$, we have that $\kappa(\{3\}, 0) = EC(4) = \{2, 4, 5, 6\}$, that is, you're right that the state $3$, upon reading the letter 0, contributes the states $2, 4, 5, $ and $6$.
Important note: she is doing $\epsilon$-transitions removal and the subset construction at the same time. I don't like that at all as it is confusing, also I don't see the formal construction itself in the video. I suggest that you try to do $\epsilon$-removal alone (without determinization). That may give you a better understanding as a start.


derandomize a BPP algorithm Suppose we have a BPP algorithm $A$ s.t. its running time is random and is $O(n^2)$ in expectation. How do we create a new BPP algorithm $B$ to solve the same problem s.t. it has deterministic running time $O(n^2)$?
My effort:
Denote the running time of $A$ as $T$. Suppose $E(T)\leq T(n)=O(n^2)$.

Run $A$ at most $kT(n)$ steps.
If it terminates, return its output; otherwise, output Yes with probability $q$.

But I just proved that this cannot be a BPP algorithm for any $q$... Any hint please?

Derandomization is the process in which a randomized algorithm is converted to an equivalent deterministic algorithm. This is not what this exercise is asking you to do. The algorithm $B$ is still randomized – only its running time is deterministic.
Suppose that $A$ decides the problem $L$, in the following sense: if $x \in L$ then $\Pr[A(x) = 1] \geq 2/3$, and if $x \notin L$ then $\Pr[A(x) = 0] \geq 2/3$. Moreover, there is a function $f(n) = O(n^2)$ such that the expected running time of $A$ on $x$ is always at most $f(|x|)$. We want to construct a new algorithm $B$ with the same behavior regarding to $L$, and with the following additional property: there is a function $g(n) = O(n^2)$ such that the running time of $B$ on $x$ is exactly $g(|x|)$.
Suppose that $f(n) = Cn^2$, and consider your solution with $K = 3C$ and $q=1/2$. If we're careful, then there will exist a function $g(n) = O(n^2)$ such that the running time of $B$ on $x$ is exactly $g(|x|)$. What about the other property?
Suppose that $x \in L$ has size $|x|=n$. The expected running time of $A$ on $x$ is at most $f(n) = Cn^2$, and so $A$ terminates within $Kn^2$ steps with probability $p \geq 2/3$. If this happens, the probability that $B$ outputs $1$ is at least $2/3$. Otherwise, the probability that $B$ outputs $1$ is $1/2$. In total, $$\Pr[B(x) = 1] \geq p \cdot \frac{2}{3} + (1-p) \cdot \frac{1}{2} = \frac{1}{2} + p \cdot \frac{1}{6} \geq \frac{1}{2} + \frac{2}{3} \cdot \frac{1}{6} = \frac{11}{18} > \frac{1}{2}.$$
Similarly, if $x \notin L$ then $\Pr[B(x) = 0] \geq 11/18$. This is almost what we want – we want $11/18$ to be replaced by $2/3$.
In order to enhance the success probability ("error reduction"), we need to run $A$ several times and take a majority vote. By running $A$ enough times and by increasing the value of $K$, we get drive the error probability of $B$ down to any positive constant. Details left to you.


Distributed MST Construction in O(log log n) Rounds in a Clique I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5.

It shows by induction on k (phase number), that the spanning tree, for every cluster F (from phase k), is indeed an MST fragment of that cluster of vertices.

The claim is of course trivial for the base case, as the clusters are singletons of vertices. To show the induction step, it suffices to show that each edge $e$ (where $X\left(e\right)=\left(F_{1},F_{2}\right),\ F_{1}\in\hat{F_{1}},\ F_{2}\in\hat{F_{2}}$, where $F_{1},F_{2}$ are the original clusters, that is, the connected components of the previous round, now contracted into one vertex, and $\hat{F_{1}},\hat{F_{2}}$ are their super clusters, that is, the connected components containing them, created as part of this procedure in phase $k$) chosen by the procedure Const_Frags is indeed a minimum weight outgoing edge (MWOE) of either $H_{1}=\underset{F\in\hat{F_{1}}}{\bigcup}F$ or $H_{2}=\underset{F\in\hat{F_{2}}}{\bigcup}F$. They assume wlog that $e$ was chosen as part of $F_1$'s $\mu$ lightest outgoing weight edges, and want to show that $e$ is indeed the MWOE of $H_1$. So they assume otherwise, that there exists $e'$ of lower weight than $e$ that is outgoing from $H_1$.

What I don't understand is, why do they assume that $e'$ is of cluster $F_1$ as well? The only thing we know about $e'$ is that it is outgoing from $H_1$. This means that it can be outgoing from another cluster- $F'\in\hat{F_{1}}\backslash\left\{ F_{1}\right\} $. I would appreciate any help! thanks!

I think I've found an answer, so will post here what I have. My proof seem to cover both scenarios I've mentioned. I still think their proof is incomplete. But in case I'm wrong, I would love to be corrected.

Similar to them assuming there is $e'$ outgoing from $F_1$, I assumed there was $e'$ outgoing from $F_3$ that is in $\hat{F_{1}}$, of lower weight than $e$.

If it was chosen, than it happened before choosing $e$, since its lighter. But then we get a contradiction to $e'$ being outgoing of $H_1$. So it wasn't chosen. If it wasn't chosen because it created a cycle, then it's yet again a contradiction to it being outgoing from $H_1$, since if it created a cycle, then $F_3, F_4$ were already merged by the time we reached $e'$, and therefore when we reached $e$ as well.

Therefore we're only left with the option that it was deemed "dangerous" (and therefore removed). Then either $e'\notin\mathcal{A}\left(F_{3}\right)$ or $\hat{F_{3}}$ was finished by the time we reached $e'$ .

If $\hat{F_{3}}$ was finished , then by the time we get to $e$ (which happens after $e'$, as $e'$ is lighter). But we assumed $F_3$ is part of $H_1$ by the time we reach $e$, therefore $\hat{F_{1}}$ is also finished, which is a contradiction to it being unfinished.

Then $e'\notin\mathcal{A}\left(F_{3}\right)$. This can happen for two reasons (as per their proof):

There exists a lighter (than $e'$) $e''$ in $\mathcal{A}\left(F_{3}\right)$ (such that $e''$ touches the same base fragments $e'$ touchs, which means its basically the same logical edge, just of lower weight). Therefore since $\hat{F_{3}}$ wasn't finished, and there were no cycles, $e''$ was added earlier than $e'$ and therefore than $e$. But then by the time we reach $e$, $e'$ is no longer outgoing from $H_1$. Contradiction yet again.
Then there exists $\mu$ lighter edges in $\mathcal{A}\left(F_{3}\right)$. Let $e''$ be the heaviest there (that is still lighter than $e'$ and therefore than $e$). Therefore after inspecting $e''$, $\hat{F_{3}}$ is deemed finished, which is yet again a contradiction.


What is correct time complexity of the substring generation algo The naive algorithm for generating all unique substrings involves traversing all the string from 1..n, thus takes $\mathcal{O}(n^2)$, but it also involves maintaining a list for all generated substring to check everytime for repetitions.
So the total time can't be $\mathcal{O}(n^2)$, since there is an added checking of uniqueness, which means that I have to maintain a list of all previous generated substrings.
So how is it correct that when it is said that the algorithm takes only $\mathcal{O}(n^2)$ time.
There is obviously an added cost at each substring generation.
The actual time complexity should be as pointed out by Raphael should be something like the following -:
$\mathcal{O}(n^2) + (\mathcal{O}(m^2) * \mathcal{O}(n)))$
where $m$ is the total number of substrings generated $n(n+1)/2$, and the time to compare 2 different strings is the smaller length between two strings, assuming the strings are being compared character by character.
Now if the above is correct then what I am confused about is should it be plus or a multiply with the comparision cost.

To be blunt, the Stack Overflow question and its answers illustrate why you want to ask about such things here.

The propsed algorithm clearly does not run in quadratic time.
Since the length $n$ of the original string is our input size, and the length of the longest possible result string, we can not assume that string comparisons run in constant time.
The bound you give is therefore also wrong, since you can not check in constant time if any string is in a list of size $L$.

Instead, the running time of the algorithm is more complicated and depends on several factors (new variable names).

The length $N$ of the input string.
The number $m$ of output strings. $m \in \Omega(n) \cap O(n^2)$.
The total length $M$ of all output strings. $M \in \Omega(n^2) \cap O(n^3)$.

You should be able to derive rough bounds using standard approaches. Keep in mind to fix the dictionary implementation you use for the "list"! Using, say, tries you get lookup (and insertion) costs bounded by the length of the string at hand.


Can polymorphism be simulated by lazy type operators? In the definition of lambda cubes, type polymorphism is distinguished from type operators/constructors.

I have the nagging feeling that type polymorphism can be constructed through type operators using lazyness. This may be extremely convoluted but I always felt polymorphic types where just functioning "as if" waiting for a concrete type.

Here's an example...

Take (+1)::Num a => a -> a, (+1) pi is Floating whilst (+1) 1.1 is Fractional.

This level of polymorphism above can be constructed through the use of a "universal delayed type constructor" F and a type operator G designed for (+1). Where,

F :: X -> f -> a -> X a

I've tried to upper case type signatures to represent types and lower case for terms.

And where,
G :: a -> B
G ( _ ::Integral) = Integral
G ( _ ::Fractional) = Fractional
G ( _ ::Floating) = Floating

Note that G's implementation is partial, I've not actually said how (+1)::Floating -> Floating  is implemented differently from (+1)::Integral -> Integral .

Therefore, F G (+1) achieves the same as (+1) with polymorphism above. This is a simple example, I may need to go a second level (i.e. operators on type operators) to simulate polymorphic type operators.

So, is true that polymorphism can be simulated by type operators? I'm probably wrong but I don't understand why. Can anyone help?

[EDIT]

My question was ill-posed. I didn't have the concept quite formed in my mind. It actually was triggered by Pierce's comment when a polymorphic function meets a type argument, the type is actually substituted into the body of the function. Based on that, polymorphic functions felt very close to type operators: type operators work on types, polymorphic functions crystalize into proper functions when given a type. I felt that polymorphic types could be replaced by some kind of (recursive) type operator that "fetched" the proper type. I forgot however that polymorphic types have kind $*$ whilst type operators have kind $* \rightarrow *$. So that's at least one difference.

It's not entirely clear to me how your idea is supposed to work, but everything you're doing can just simply be done with a bit of more high-powered type theory. That is, if we allow quantification over types then we can talk about polymorphism. Let's go from easy examples to the ones you're talking about.

A function such as
$$f \, x = (x,x)$$
is polymorphic in the type of $x$: if $x$ has type $A$ then $f$ has type $A \to A \times A$. We can express this sort of dependency by intrducing an extra argument so that $f$ has type $\prod_{A : \mathsf{Type}} A \to A \times A$ and is defined by
$$f \, A \, x = (x, x).$$

Your example is like this, except a bit more complicated. To keep examples simple, let me instead used a simplified class (the whole Num is a bit large)

class Cow a where
  one :: a
  plus :: a -> a -> a

and consider a functio dependent on Cow:

plusOne :: Cow a => a -> a
plusOne x = plus x one

We can express plusOne as before, except that now it takes three extra parameters: a type $A$, an element of $A$, and a function $A \to A \to A$. So its type would be
$$
\prod_{A : \mathsf{Type}} A \to (A \to A \to A) \to A \to A
$$
and it would be defined by
$$\mathtt{plusOne} \; A \; \mathtt{one} \; \mathtt{plus} \; x =
  \mathtt{plus} \; x \; \mathtt{one}.$$
This is a general trick: polymorphism can always be replaced by passing around extra arguments, but the price you pay is that you will have dependent types and there might be many extra arguments.


Branch and bound for minimum linear arrangement I am trying to solve this branch and bound problem but I could not come up with any approximate cost function which is better than the cost.

Let's say $G$ is a graph of $n$ nodes $\{1, 2, 3, \ldots , n\}$. For a permutation $f$ of the nodes of $G$, the  weight  of  each  edge $(x,y)$ will be $|f(x)-f(y)|$. The total weight of $G$ will be the sum of the weights of its edges.  You can think of $f$ as a relabeling of the nodes of $G$, where
$f(x)$ is the new label of node $x$.

I am trying to find a permutation $f$ that results in a minimum total weight of $G$.

Now trying to solve this, all I could come up with is finding the approximate cost that is the sum of weights of each edge completed till now (for each backtracking tree node) and proceed from the minimum cost node. I am wondering if someone can help me with a better approximation formula.

One of the best solution is likely based on a linear programming relaxation or direct integer programming. For the latter, the branching and backtracking will be implicit, and you won't have to manage it yourself.

I have seen it solved in two ways using this technique. We can slightly improve your bounding algorithm as well.

The textbook method

Using binary variables $x_{ij}$ representing $f(i) = j$, you can define continuous variables $f(i) = \sum_{j=1}^n j x_{ij}$

Add constraints $\sum_i x_{ij} = 1$ and $\sum_j x_{ij} = 1$ representing that one position is assigned one and only one node.

For each edge, the cost $c_e$ has two constraints : $c_e \geq f(i) - f(j)$ and $c_e \geq f(j) - f(i)$, and you want to minimize $\sum_e c_e$

You can give this problem to an integer programming solver, which will be happy to do the backtracking for you and more - or you can solve the linear programming relaxation yourself each time (just if you want to learn, the solver optimizes it internally).

Another relaxation

Instead of using the positions as binary variables, you can use $f(i) < f(j)$ i.e. node $i$ goes before node $j$. This is more adapted if you want to do the branching yourself and don't specify those variables explicitly.

With this approach, you can sometimes have a faster problem to solve at each node - here it can be solved as a simpler minimum-cost flow problem as shown by this paper. I wouldn't recomment it unless you are willing to investigate much time and research into your problem.

Other techniques

For branch-and-bound, any lower bound on your cost function will do.
For small problems your bounding approach is perfectly fine.

You could make it tighter: for each edge with an unplaced node, pick the best possible free labeling to estimate its cost. Several edges may use the same placement for different nodes, but this will be better than estimating their cost as 0.

There are many possible variations on this scheme: pick the best free label for each unlabeled node (irrespective of overlaps) or consider overlaps only inside small groups of nodes.


Prove that $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ is partial recursive I'm stuck on this problem:

Given $f:\mathbb{N} \rightarrow \mathbb{N}$ a partial recursive function that is also injective and total. Prove that the function $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ $$f^{-1} = \left\{\begin{array}{rcl} x & \mbox{if} & f(x) = y \\ \uparrow & \mbox{otherwise}\end{array}\right.$$ is partial recursive.

So to prove that a function is partial recursive I have to show that I can build it from basic recursive functions (successor, projection and constant) by applying composition, primitive recursion and then minimization.

I don't know what form $f$ has, but I think I can use it to construct $f^{-1}$. The only problem is that I don't know what to write...

You can partially compute $f^{-1}(y)$ as follows:

  for $x$ from $0$ to $\infty$:

    if $f(x) = y$ then return $x$

If you don't like for loops, you can use the following implementation:

  $x \gets 0$
  if $f(x) = y$ then return $x$
  $x \gets x + 1$
  goto step 2


Role of computational power in recent AI developments Today Google's AI won its first game of Go against Lee Sedol, one of the best Go players on the planet. Image interpretation and self-driving cars are other recent success stories in machine learning. I was under the impression that these advances are largely the result of better algorithms and novel ideas, but some of the guys in my university were claiming these advances are mainly due to increased computational power. Neural networks in particular are an old concept that was largely forgotten for decades and now we're doing all sorts of cool new things with it.

What is the role of computational power with regards to recent successes in artificial intelligence?

This is a broad question, but from the presentations I've seen, there have been three major factors that all have come together over the past decade or two:

More data.  Machine learning algorithms rely upon having many instances, so we can train them.  The more data we have (the more labelled instances we have), the better the algorithms do.  On some of the harder problems people are tackling today, machine learning algorithms only start to do well once you give them millions or billions of examples.  For example, speech recognition is a prime example of this: researchers in the field have told me that progress in speech recognition was closely related to the size of the data sets available for training.  Over the past decade or two, large data sets have become available: it's become possible to train algorithms using every image on Flickr, or every video on Youtube, or every call ever made to Google Voice.  That wasn't possible two decades ago.
More computational power. Processing that much data requires efficient algorithms.  One significant advance was that researchers found out how to use GPU's (graphic cards) as specialized processors: implementing the machine learning algorithm on a GPU could speed up the training process by 10x - 100x.
Better algorithms. Deep learning has been having some significant successes over the past five years or so.  This is a result of decades of hard work.  There's a small subcommunity of researchers who have been working on neural networks for decades, and who have slowly been making progress, finding what kinds of neural networks work well.  They've invented many new algorithmic ideas: autoencoders, stochastic gradient descent with mini-batches, ReLU activation functions, drop-out for regularization, convolutational neural network structures.

It has taken the combination of all of these new algorithmic ideas, plus larger data sets, plus new ways of implementing the algorithms efficiently so we can make effective use of the large data sets, to achieve these gains.  This is a real success story for the field.

Sometimes you hear the stereotype of a lone inventor sitting in their garage, who one day has a "Eureka!" moment and comes up with a brilliant invention fully-formed in a flash of insight.  However, that's typically not how research progresses.  Deep learning is a good example of that.  It has taken decades of work and gradual improvement, exploring many ideas that ultimately didn't pan out, with researchers building on incremental advances and new ideas from other researchers, to reach where we are today.  An inspiring example for the impact of long-term fundamental research.


Choosing a subset to maximize the minimum distance between points I have a set of points $C$, and I have the distance between each point $D(P_i,P_j)$. These distances are euclidean but the points are actually in a feature space.

From the $C$ points I want to choose a subset of $n$ points. Call this subset $s$. I want to choose this subset so as to maximize the minimum distance between all the points in the new set $s$.

$$
\max_{\substack{s \subset C \\ |s| = n}} \left( \min_{\substack{i,j \in s \\ i \neq j} }   D \left( P_i, P_j \right) \right)
$$

Right now I am using hill climbing to solve this problem. I understand that simulated annealing may give a better solution.

Is there a known solution to this type of problem? Or can this problem be reformulated into another problem that is easily solved?

The decision problem version of this optimization problem is:

  Given a threshold $t$, you want to know whether it is possible to find a subset of $n$ points such that every pair of points in the subset are at least $t$ units apart.

Of course, if you can solve the decision problem, we can solve your optimization problem (by binary search on the threshold $t$).

Now this decision problem is the problem of finding an independent set in a Euclidean graph, where points $x,y$ have an edge between them if they are at distance $\le t$ apart.  One approach would be to look at standard approximation algorithms for independent set.

Even better, you can look at algorithms for independent set in geometric intersection graphs.  Consider a set of disks, where each disk has diameter $t$ and is centered at one of the points in your set $C$.  Now we can form a geometric intersection graph, where there is one vertex for each disk and an edge between two vertices if their corresponding discs intersect.  The problem of finding an independent set in this sort of graph has been studied and there are approximation algorithms for this problem that you could try using.

If you want the exact optimum rather than an approximation, you could use any of the standard "big hammers", such as a SAT solver or an ILP solver.  There is a straightforward way to formulate the independent set problem as a SAT instance, and then you could apply a SAT solver to it to find whether there exists a subset of $n$ points which are all $\ge t$ units away from each other.


What is Follow(X) when there's a rule, A -> XBCD where First(B) and First(C) contain empty, but First(D) do not I have a question about follow sets.

Suppose there's a rule,

  A -> XBCD

  B -> $\beta$ | $\epsilon$

  C -> $\gamma$ | $\epsilon$

  D -> $\delta$

What is Follow(X)?

Is it (First(B) - $\epsilon$) $\cup$  (First(C) - $\epsilon$) $\cup$ First(D) = {$\beta$ , $\gamma$, $\delta$ } ?

I am answering my own question. As @rici made a comment, I misunderstood the meaning of Greek letters in the discussion of Follow sets in the book I am reading. Greek letters mean sequences of symbols.

Using the definition,

  If there is a production B-> $\alpha$ A $\gamma$, then First ($\gamma$)
   - {$\epsilon$} is in Follow (A)

First(BCD) is in Follow(X) where

  A -> XBCD

BCD corresponds to $\gamma$ in the definition.


Find the minimum edge size, L, that would allow the construction of a tree whose edges connect all given 2-d points, but no edge exceeds length L Given a set of points in the 2-d plane, find the minimum edge size, L,  that would allow the construction of a tree whose edges connect all given points, but no edge exceeds length L.

Here is an algorithm, which I think might work but seems slow:

Pick a random point
find the distance of its nearest neighbour, store the distance, d
your set of covered points, S, now has 2 points in it
find the nearest neighbour point (which is not in S) to any points in S and compute its distance to a point in S, e. Add this new point to S.
d = max(d,e)
repeat steps 4 and 5 until all points have been added to S. now d is the required distance L.

I need help determining if this is correct and if so, the time complexity. Also can the algorithm be made faster (it will be run over a lots of data)?

Yes, your algorithm is correct. The correctness can be proven by induction on $S$ easily.

Instead of growing by selecting the nearest point to $S$, a faster way in general should be just selecting the shortest edge available and including both of its end points. How to select the next shortest edge available? Construct a min-heap of all edges up front. Pop out the top of the heap one by one. Using a counter you can stop once all points are included. The length of the last edge included is the minimum edge size wanted.


Branch and bound stanford slides doubt On the 6th slide at https://web.stanford.edu/class/ee364b/lectures/bb_slides.pdf, while defining L2 and U2, why are we taking min for both?

The slides are correct: remember that we are trying to find a bound on the optimal value of $f$, which is defined as
$$\Phi_\mbox{min}({\cal Q}_\mbox{init}) =\min_{x\in{\cal Q}_{\tiny\mbox{init}}}f(x)$$

To find that minimum, we approximate it by upper and lower bounds $\Phi_\mbox{ub}$ and $\Phi_{\mbox{lb}}$. Let's concentrate on $\Phi_{\mbox{ub}}$. Note that if ${\cal Q}={\cal Q}_1\cup{\cal Q}_2$, then both
$$ \min(\Phi_{\mbox{ub}}(\cal Q_1),\Phi_{\mbox{ub}}(\cal Q_2))\geq\Phi_\mbox{min}(\cal Q)$$
and
$$ \max(\Phi_{\mbox{ub}}(\cal Q_1),\Phi_{\mbox{ub}}(\cal Q_2))\geq\Phi_\mbox{min}(\cal Q)$$

But we might as well take $\min$, since that is the value that is closer to the global minimum $\Phi_\min(\cal Q)$!

In fact, taking the minimum is going to be necessary if we want the branch and bound method to converge to the minimum as we sub-divide $\cal Q$ into smaller and smaller pieces.


Showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable How would you go about showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable?
Intuitively speaking I think it is indeed undecidable because there seems to be no limit to the possible configurations, however I am not sure.
Thanks a lot in advance!

If $M$ does not have the option to not move its head at all, as stated in a comment to the question, then the problem is trivially decidable by the Turing machine that immediately halts and accepts.
If $M$ might not move its head while computing $T(w)$ and the problem is to decide whether it actually does so, then the problem must be undecidable as otherwise the halting problem would also be decidable.
To see this, construct a Turing machine $M'$ that simulates $M$ while always moving its head. When the simulation terminates, $M'$ keeps its head in place for one more step, and then halts. It is not hard to come up with an algorithm that builds $M'$ from $M$, thus showing that $M'$ is computable.
Then $\langle M', w \rangle \in L$ if and only if $M$ does not halt.


The role of depth of a circuit in its hardware implementation The depth of a circuit is the maximal length of a path from an input gate to the output gate of the circuit [Reference]

Question: What is the relation between the depth of a circuit and hardware implementation of the circuit. In fact, I want to ask this question, why the low depth of a circuit  results in the circuit has a suitable  hardware implementation?

Thanks for all suggestions

In the zeroth order sense, it is correct that the logic depth and the time to execute the logic would be the same.  There are nuances to this because you need to do something with the result.

What logic is a medium to do work.  In the simplest sense, you have a bounded function with inputs and outputs:

In most actual systems, you need a way to hold the data, which is why we have latches:

and with the latch, we introduce the clock.  I will now give you two examples of where logical depth, in a system context, is not representative of speed.

The first assumption that made is "0"s and "1"s are things.  Digital is a special case of analog; however, I personally never run anything at a "1" because it is inefficient for power.  After you are above threshold, you lose transistor gain.  If you are trying to have power performance, you might not make the same choices as for speed performance. You are doing the same electrical work at a high total cost.

The second assumption is that everything is clocked.  In a system context, I often add logic to make things go faster.  Asynchronous systems give you the average speed as a delay, instead of the worst case delay as a synchronous, clocked system.

Another assumption is that logic doesn't have physical space.   Wires are costly even though that they do not add to calculation value.  A good example of this is the S-Box used in AES.  If you look at the "logic", I have often seen hardware implementations that use a lookup table.  This is because it's easy.  If you look at the gate depth alone, without the wires, it also would look to be fast.  When I make the AES S-Box, the circuit implementation looks like:

This circuit has a much larger depth than the lookup table; however, it requires, less power, takes up less area, and is faster than the lookup table implementation even though the logic depth is deeper.


Prime Implicants in Boolean Function A Boolean function $F(X_1, X_2, X_3, X_4, X_5, X_6)$ of six
variables is defined as $F = 1$, when three or more input variables are at logic 1. otherwise 0.
How many essential prime implicants does F have?

How to visualize this problem. A Six Variable k-map is very difficult to manage. Any hints?

An implicant of $F$ is a partial assignment to the variables of $F$ which guarantees that $F$ is satisfied. A prime implicant is a minimal implicant, that is, an implicant that is no longer an implicant if we remove any single variable.

Let us start by finding all the implicants of $F$. Let $\alpha$ be any partial assignment to the variables of $F$, and suppose that $\alpha$ assigns $k$ variables to true. We can complete $\alpha$ to an assignment by assigning the rest of the variables to false, in which case we get an assignment containing $k$ true variables. Hence $\alpha$ can only be an implicant if $k \geq 3$. Conversely, it is not hard to check that if $\alpha$ assigns at least 3 variables to true then it is an implicant of $F$.

When is an implicant a prime implicant? It must be a partial assignment with at least 3 true variables, such that if we remove any single variable, there are at most 2 true variables. Can you figure out how all such implicants look like? Give it a try.

As an aside, your function is monotone, and so its prime implicants are also known as minterms. Minterms have a special structure – they cannot be arbitrary partial assignments. I'll let you figure out the special property that minterms have.


Solving recurrence relation $T(2n) \leq T(n) + T(n^a)$ I want to prove that the time complexity of an algorithm is polylogarithmic in the scale of input.

The recurrence relation of this algorithm is $T(2n) \leq T(n) + T(n^a)$, where $a\in(0,1)$.

It seems that $T(n) \leq \log^{\beta}{n}$ for some $\beta$ depends on $a$.
But I can't prove this inequality. How to solve this recurrence relation?

I just want to get an upper bound polylogarithmic in n.

Your guess is wrong. In fact, it is not hard to show that assuming $T(n) > 0$ for all $n > 0$, then $T(n) = \Omega(\log^k n)$ for all $k$. Indeed, for this to hold we need that for large enough $n$ we would have
$$
(1+a^k) \log^k n = \log^k n + \log^k n^a \geq \log^k (2n),
$$
or $\sqrt[k]{1+a^k} \log n \geq \log n + \log 2$,
which holds as long as $[\sqrt[k]{1+a^k}-1]\log n \geq \log 2$, and in particular for large enough $n$.

What is the correct order of growth of $T(n)$? To try and find out, write $S(n) = T(2^n)$. The recurrence now becomes
$$ S(n+1) = S(n) + S(an). $$
For large $n$, we would expect $S(n+1) - S(n)$ to be very close to $S'(n)$, and so heuristically we would expect that $S$ satisfy $S'(n) = S(an)$. This equation seems a bit hard to solve, but an approximate solution is $S(n) = n^{\Theta(\log n)}$. Substituting back, we deduce that the order of growth of $T(n)$ should be something like $(\log n)^{\Theta(\log \log n)}$.


Are all instructions eventually converted to zero-operand instructions? Recently, my demonstrator said that all instructions are eventually converted to zero-operand instructions just before they get executed. yet another demonstrator said that this "doesn't make any sense", and I don't know who to believe; none of them really gave any logical arguments.

So, I want to know is any of them right at all? I tried searching for the answer but I didn't find anything.

This will depend on the computer architecture.  zero-operand computer architectures use the stack, so to add 2+2:

PUSH 2 (into the stack),
PUSH 2 (again),
ADD (call the instruction - note that no operators are passed by).
POP ( 4 out of the stack)

but most other computer architectures e.g. use registers, memory addresses and values as the parameters to an instruction (in addition to the stack). For example the same 2+2 in a CISC computer.

MOX AX,02 (AX=0)
ADD AX,02 (AX=4)

However, if you're thinking in terms of translating a high level programming language into executable code e.g. one routine calling a subroutine the list of parameters most likely be passed by via stack and the number of parameters be reduced to 0 as in the first example.


I'm trying to prove this language is not context-free: {a^x b^y c^z | where x=z and x<y} So far i've tried with making x = z = p and y = 2*p, but it seems that if I place vxy to represent all b's then I can't get a contradiction.

The pumping lemma for context-free languages says the following:
For every context-free-language $L$ there exists a constant $p$ such that for every word $s \in L$ of length at least $p$, we can write $s = uvwxy$ and:

$|vx| \ge 1$
$|vwx| \le p$
$uv^nwx^ny \in L$ for $n \ge 0$

To prove that $L = \{a^xb^yc^z: x < y \land x = z \}$ is not context-free we will do the following:
Assume language $L$ i context-free and let $p$ be the constant from the pumping lemma.
Take the word $s = a^pb^{p+1}c^p$, which is clearly in $L$, and express it as $s = uvwxy$ as is stated in the lemma.
We know that $|uvw| \le p$ so $v$ consists only of $a$'s.
Denote $s_n = uv^nwx^ny$
Now consider the possible cases:

If either $v$ or $x$ contain more than one letter, than $s_2$ will not be of the form $a^*b^*c^*$, so we know that $v$ and $x$ will consist of at most one letter.
If $v$ is empty and $x$ consists of $b$'s then $s_0$ will not have more $a$'s than $b$'s. If $x$ consists of $c$'s then $s_2$ will have more $c$'s than $a$'s.
If both $v$ and $x$ are non-empty then if $v$ consists of $a$'s and $x$ of $b$'s then we in $s_2$ we will have more $a$'s than $c$'s. If $v$ consists of $a$'s and $x$ of $c$'s than for large enough $m$ in $s_m$ we will have more $a$'s than $b$'s. If $v$ consists of $b$'s and $x$ of $c$'s then in $s_2$ we will have more $c$'s than $a$'s.
If $v$ and $x$ consist of the same letter (i.e $w$ is empty) then following the same type of reasoning we will also reach a contradiction.

Thus we have reached a contradiction for every possible case and so $L$ is not context-free.


Question on NP $\cap$ coNP I'm struggling with a past paper question and would appreciate any hints:

Suppose $L_1, L_2 \in $ NP $ \cap $ coNP and $L_1 \oplus L_2 = \{ x : x $ is in exactly one of $L_1 $ or $ L_2 \} $. Then prove that $L_1 \oplus L_2 \in NP \cap coNP$

Hint: What $L \in \mathsf{NP} \cap \mathsf{coNP}$ means is that if $x \in L$ then there is a witness for this, and if $x \notin L$ then there is a witness this. From these witnesses for $L_1,L_2$ you can easily construct witnesses for $L_1 \oplus L_2$. A witness for $x \in L_1 \oplus L_2$ would be:

A witness for $x \in L_1$ and a witness for $x \notin L_2$; or
A witness for $x \notin L_1$ and a witness for $x \in L_2$.

A witness for $x \notin L_1 \oplus L_2$ is similar and left as an exercise.

More generally, if $L_1,\ldots,L_k \in \mathsf{NP} \cap \mathsf{coNP}$ and $\phi$ is any function on $k$ inputs, then $\phi(L_1,\ldots,L_k) \in \mathsf{NP} \cap \mathsf{coNP}$ (defined analogously to $L_1 \oplus L_2$), for similar reasons.


How to predict the next word in a sentence using N-grams How would I go about predicting the next word in a sentence if I have a n-gram model available? A intuitive solution would be to just ask the probability of all the words that can come next and see which has the highest. But this would be dreadfully slow if I have a very large set of n-grams wouldn't it?

If anyone could point me in the right direction that would be great!

Here is what I have so far. We have a data structure and this data structure will allow lookup of context(so the previous words) via hashing. This can be done in O(m) with m the length of the context but since this is always very short it is safe to say lookup can be done in O(1). Now let's say the previous words are "I want to" I would look this up in my ngram model in O(1) time and then check all the possible words that could follow and check which has the highest chance to come next. But with something as generic as "I want to" I can imagine this would be quite a few words. Our application must run on mobile devices so I would like to know if there is a more efficient way to get the word with the highest chance. I was thinking about maybe sorting the ngrams but since we are using some sort of hashtable this isn't really an option.

The more I think about this however the more I realize that even if it would be lets say 500 words that can come next, that this is still a fairly small number and even a slow processor could easily go over those very quickly so maybe I am over thinking things.

Store the n-grams in a tree or trie, with one level per word, starting from the leftmost word.  Then given some context, e.g., "I want to", you traverse the tree/trie (follow the edge out of the root that is labelled "I", then the edge labelled "want", then the edge labelled "to") and find all children of the resulting node.


Prove that the complements of pumping-style languages are context-free Define $L = L(u,v,x,y,z) = \{uv^ixy^iz : i \geq 0\}$, with $u,v,x,y,z \in \Sigma^*$.  Prove that $\overline{L}$ is a CFL for all $u, v, x, y, z$

Clearly, $L$ is a CFL, as it is generated by the grammar:

$S \longrightarrow uAz$

$A \longrightarrow vAy$

$A \longrightarrow x$

I am struggling with this problem, because I don't see how I'd go about constructing a PDA or CFG for $\overline{L}$.  The fact that L "looks like" the main condition of the pumping lemma for CFLs must somehow relate, but I am not seeing the connection.  Maybe I could do something with morphisms?

The first thing to ask is, why is the claim even true? CFLs, in general, are not closed under compliment, but this language certainly does (yet, it is not regular, so cosure for $\Sigma^*\setminus L$ cannot be used here). So why is the complement a CFL?

The reason is that the language $L$ is actually deterministic context-free, and this class have different closure properties, specifically, it is closed under complementation.

To prove $L$ is a DCFL, we need to build a deterministic PDA for it. There are some technicalities for the case when $v=x$ or $x=y$ or $v=x=y$, but just to give the  idea of the construction, let's assume they are all different, $u\ne v\ne x\ne y\ne z$. Since $x,y,u,v,z$ are fixed, it is easy to construct a Deterministic PDA for $L$: it tries to match the input to $u$ (and rejects if it can't), if it finds $u$ it continues to match the input to $v$ at least once (and count the number of times it succeeds, using the stack), the first time it fails, it assumes the input has gotten into the $x$ part, and from there checking the $xy^iz$ part is obvious.

If you reverse the accept/reject of the DPDA of $L$ you will receive a DPDA for $\overline L$, thus also $\overline L$ is deterministic CFL, and specifically, it is a CFL.


What is the name of this type of function composition? If standard function composition is defined as:

 (define compose
   { (B → C) → (A → B)
             → (A → C) }

   F G -> (λ X (F (G X))))

What type of composition does the below function describe? Is there a particular name for it in category theory?

 (define compose-2
   { (A → (X → C)) → (B → X)
                   → (A → B → C) }

   F G -> (λ Y (compose (F Y) G)))

You composition is of type $\operatorname{comp}:(A \to X \to C)\to (B \to X) \to (A\to B \to C)$. Up to Currying, it can be seen as being of type $(A  \times X \to C)\to (B \to X) \to (A\times B \to C)$. So it's just a composition of a two arguments functions with a one argument function. You take $f$ and $g$ and return $(a,b)\mapsto f(a,g(b))$.

From a general abstract nonsense point of view, you can define the functor $$A\times -:\begin{array}{lll}
O & \mapsto &A\times O\\
g : B \to X&\mapsto &<\operatorname{id}_A;g>:A\times B \to A\times X
\end{array}$$
and then your composition is just $\operatorname{comp}=f\mapsto g \mapsto f\circ (A\times  g)$.


route and/or packing optimization algorithm What type of problem would this question fall under, are there known algorithms/heuristics for it, what would be good resources to learn more about solving it?

Given:

a list of items each with a destination location: the number of items per destination is unbounded (and can be zero for some locations). All items are at a central location.
a number of destination locations, each awaiting a set number of the items: the number of locations is finite, and small [under a thousand]
a number of couriers, all at the same point initially (the same initial location as the items); each courier has a maximum number of items they can carry: the number of couriers is very small [a dozen]
the duration of travel between all locations [all couriers travel at the same speed]

Problem:
minimize the maximum wait time of each location [the time it takes for all the items due at that location to be delivered]
by allocating items to couriers.

This specific problem seems to be an variation of minimizing the makespan in the job shop scheduling problem. Essentially, your couriers are modeled as 'workers' that need to process certain 'tasks', which are the delivery requests. We look for an assignment of tasks to workers that minimizes the time until the last worker is finished, the makespan of the assignment.

The current problem is slightly different from the basic version, as it assumes all workers are equally skilled, but here some workers can process faster, as they can carry more items.

The job shop scheduling problem is an NP-complete problem, which means that we do not expect to solve this problem exactly in polynomial time.

One option is to model this problem and various extensions as an (mixed) integer linear program, but this generally means you either have an exponential time algorithm or have no guarantees over the quality of your result.

A better idea for this specific problem is to use an approximation algorithm for the job shop scheduling problem. These approximation algorithms run in polynomial time and although they do not guarantee an optimal solution, they can give you an upper bound on the quality of the solution (e.g. The solution given will be at most twice the size of the optimal solution). There is extensive literature about this problem, so where to start mostly depends on the type of solution you're looking for.


Is this variation of the traveling salesman problem NP-hard Consider the following setting. You have $n$ cities, and there is a cost to travel from a city $i$ to a city $j$ given by $c_{ij}>0$ where $c_{ij}\neq c_{ji}$. Moreover, if you are traveling to city $i$, you are allowed to stay exactly $d_i>0$ days. The problem is:
Find a travel schedule, this is: a number $m$ and a sequence of different cities $i_1,\dots,i_m\in\{1,\dots,n\}$, such that the cost $\sum_{k=1}^{m-1} c_{i_k,i_{k+1}}$ is minimal and that the whole trip lasts at least $L$, this is $\sum_{k=1}^m d_{i_k}\geq L$.
There are many similarities between this problem and the traveling salesman one. The key differences are the non symmetric costs $c_{ij}\neq c_{ji}$ and that instead of having to travel to all cities once, one just needs to travel to enough cities to make the trip last enough.
I understand that to show that this problem is NP-hard, I need to show that another NP-hard problem can be reduced to this one in polynomial time. I suspect that the original traveling salesman problem may work to do so through some clever trick I haven't found yet. Moreover, since there is plenty of literature on the traveling salesman problem, I suspect a similar problem to this may already be shown to be NP-hard.
My question is: Do you see how to show this problem to be NP-hard? Or, do you recognize this problem to be something standard in some piece of literature you can point me out?

I think if you choose all $d$'s to be exactly $1$ and choose $L$ to be exactly $n$ (number of cities), any solution must visit all cities, so the reduction will work out.


Using Pumping Lemma to prove language $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular I'm trying to use pumping lemma to prove that $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular.

This is what I have so far: Assume $L$ is regular and let $p$ be the pumping length, so $w = (01)^p 2^p$. Consider any pumping decomposition $w = xyz$ such that  $|y| >0$ and $|xy| \le p$.

I'm not sure what to do next.

Am I on the right track? Or am I way off?

Hint: You need to consider what all the decompositions $w=xyz$ look like, so what are all the possible things $x$, $y$ and $z$ can be given that $xyz=(01)^p2^p$. Then you pump each one and see whether you get a contradiction, which will be a word not in your language. Each case needs to lead to a contradiction, which would then be a contradiction of the pumping lemma. Voila! The language would not be regular.

Of course, you need to work through the details and consider all the possible splittings.


Compression technique exploiting common similarities I asked this on StackOverflow, but it was determined more appropriate to post here.

So it goes like this..

For people concerned about users having slow connections and timeout issues, it is known that it can't be just always solved with minification, latency reduction etc..

I'll try to keep this question as short as possible, however retaining clarity where possible.

I've thought about a technique to further reduce uncompressable files (like mp3 and mp4), bear with me please.

What if we could skip chunks/bits/frames of a file being similar and rebuild them locally? Ok, let's explain it with a short example.

Assume you have many files in your computer, and that 3 of them are videos with a knife and a guy with blue eyes non-evenly spread over many frames. You go to this site and there's a post.. this post features a video of a serial killer's life. It is totally unrelated to the videos you have on your pc, except for the killer's knife, and the victim he kills having blue eyes.

What we could do here, is, remotely and locally make the videos (in this case) have "metadata blocks" about the most frequent frames and do a bidirectional check. If the two happen to have the same/similar blocks, the remote server just sends the new blocks, and, we rebuild the missing ones locally.

Like this:

Remote file =
    MetadataBlock:
        knife:
            from (minute 3.12) to (minute 3.59)
                and from (minute 4.40) to (minute 5.20)
        blue eyes:
            from (minute 0.06) to (minute 0.60)
                and from (minute 1.20) to (minute 1.30)
                and from (minute 6.50) to (minute 6.58)

Local file =
    MetadataBlock:
        knife:
            from (minute 8.00) to (minute 8.20)
                and from (minute 40.00) to (minute 40.02)
                and from (minute 42.00) to (minute 42.50)
        blue eyes:
            from (minute 3.05) to (minute 3.15)
                and from (minute 6.08) to (minute 7.40)

Local file.knife.total = 1.12 minutes

Local file.blue_eyes.total = 1.42 minutes

FileTotal = Local file.knife.total + Local file.blue_eyes.total

FileTotal (2.54) * 3 / 1.5 = 5.08 minutes

Remote server remove the blue eyes and knife bits/frames, appending instructions to build them locally from MetadataBlock.

As soon as the file is received, the os reads the instructions and execute them like:

"Replace MetadataBlock(from(knife.minutes)) with local file 1 MetadataBlock(from(knife.minutes))"

, the same goes for other metadata blocks such as blue eyes, black hair, shirt color etc..

Is a technique like, or similar to this feasible, or just pure utopia?

Of course it is possible.
For example, you could define the trailer of a movie as the sequence of movie sequences it shows plus the trailer-specific overhead it uses. If the movie itself is at hand when you want to watch the trailer, then everything goes well.

Yet in general...either you would have to add tons of metadata to each file (e.g. "contains sequences in which blue-eyed guy fiddles around with a knife"), thus increasing all files significantly, or you would have to run some pattern-matching algorithms over all your movie database. And your file will be very context-dependent, i.e. if one of the files you rely on changes, then all hell breaks loose. That does not sound practical to me.

Note that most lossless compression techniques also share patterns that appear across different files. So if you gzip a set of very similar mp3s, then some notable compression should happen.


Is there a simple example of sets such that $A \leq_T B$ but not $A \leq_m B$? I wonder if there is a simple example of sets $A$ and $B$ such that $A$ is Turing-reductible to $B$ but not many-to-one reductible to $B$.

For example sets $H = \{x \, | $ Turing machine with index $x$ halts on input $x\}$ and $\overline{H} = \{x \, | $ Turing machine with index $x$ doesn't halt on input $x\}$.

Because if $\overline{H} \leq_m H$, then $\overline{H}$ would be recursively enumerable and therefore $H$ would be recursive, which is contradiction.

On the other hand $\overline{H} \leq_T H$, because there is Turing machine with oracle $H$ recognizing $\overline{H}$. This machine for input $x$ just checks $x \in H$ and negates the answer.


Prove that there is no computable enumeration of all decidable languages The question:

  Let $L_1,L_2,...$ be an enumeration of $\mathcal{R}$ and define $A_i = \{\langle M\rangle \ | \ L(M) = L_i\}$. Let $L$ be a language in $\mathcal{RE}$ such that $L \subset \{\langle M\rangle \ | \ \text{M is a TM that always halts}\}$. Prove that
  there exists an $i$ for which $L∩A_i = ∅$.

Hint $\downarrow$

  Hint: Build a TM that returns some (which?) element of $L$ and apply a diagonalization argument.

My approach

I thought of the Hint but I am not sure that the language I get is decidable and I don't know how to prove that all its "always halting" TMs are not in $L$.

WLOG assume we are talking about languages over a binary alphabet $\{0,1\}$. Let $M'$ be an enumerating Turing Machine for $L$, i.e., every element of $L$ is eventually output by $M'$. Let $\langle M_j \rangle$ denote the $j$th TM output by $M'$. Define
$$L_D = \{ x \mid M_x(x) \text{ does not accept} \},$$
where $x$ is interpreted as a number in base 2. Note that $L_D$ is decidable: given $x$ you can decide if $x \in L_D$ by running $M'$ until it outputs $x$th TM $M_x$ and then running $M_x$ on $x$ and flipping the output. This is a decider since all TMs output by $M'$ halt on all inputs. Thus $L_D$ appears in the enumeration of R, say, as $L_k$ for some $k$.

It is left to show that $L \cap A_k = \emptyset$. Suppose that there exists a TM $M$ such that $\langle M \rangle \in L \cap A_k$. Then let $\ell$ be the smallest number such that $\langle M \rangle$ is output as the $\ell$th element by the enumerator $M'$, i.e. $M = M_\ell$. Therefore, we have $\ell \in L(M) \iff \ell \in L(M_\ell) \iff \ell \notin L_D \iff \ell \notin L_k \iff \ell \notin L(M)$, which is a contradition.


Data structure optimized for merging maps on partitions My question is a request for literature or pointers that address the following abstracted problem. If I have a finite set (ex. {1..10}) over which I'd like to maintain several "partition maps":

m1 = {1..5}=1, {6..10}=2
m2 = {1..3,8..10}=3, {4..7}=4.

Afterwards I'd like to merge (generalize the operation, but use addition for demonstration) these maps:

m1 + m2 = m3 = {1..3}=4,{4,5,8..10}=5,{6,7}=6.

If n is the size of universal set, and k << n the size of the range of the maps. How does one get performance (and space) closer to O(k) as opposed to O(n) (store an array)?

Edit (2017-11-14): I'm mainly interested in merge performance, lookup can be slow. To sharpen the question, there are a couple of approaches to this problem that don't quiet address this trade off:

Okasaki's Fast Mergeable Integer Maps
Erwig's Diets for Fast Set
Bonichon's A Mergeable Interval Map. This probably gives the closest of what I'm looking for, but unfortunately the exposition is a bit confusing and I'm not certain that there is the same tradeoff of merging above lookup.

Edit (2017-11-15): The application where I'm using this performs millions of merges. In the most common instance I have 4 of these maps and compute a new map. The keys are different states and the values are actually probabilities. The probabilities are discretized which is why lots of different states have the same values. It is a form of "compressed" computations. I can use an array to store these values, but this compressed form provides 100x performance currently, but I'm looking for a technique to improve upon that (I need to do billion of merges). As @D.W. described below, batched techniques would also be of interest.

I can't say that I have a fully satisfactory answer to my question. But I spent a bit of time implementing and writing about a data-structure to solve my needs here. I call the data structure a partition map. It is really just an association lists of list of integer intervals and values. The former have nicer properties, resting on top of fairly straight-forward interval comparison logic.


Which algorithm for game matchmaking in tournament I organize amateur tournaments every week with random players.
Every week, players sign up, and I get a list with:

Name
Rank (1, 2 or 3)
Role (s) (DPS, TANK and HEALER)

I need to get balanced teams of 6.
Ideally, there are 2 DPS, 2 TANKS and 2 HEALERS but in practice there are not enough healers and I have to make 3 DPS, 2 TANKS and 1 HEALER.

The other problem is that some players register together, up to 3 players grouped.

The process is currently done by hand but I would like to automate it.

I learned about the algorithm Knapsack problem, is this a good track?

Do you have any advice to help me in my research?

Thanks you.

One plausible approach is to use local search.  In its simplest form, you could start by randomly assigning people to teams, then repeatedly picking a random pair of people and swapping them gives a better assignment, and iterating.  This kind of approach should be easy to implement and flexible.  But there's a lot more to say, so let me explain in more depth.

First, you need an objective function: a way to measure, quantitatively, how good a candidate assignment is.  In your case, you might define a way of computing a penalty score for any proposed team grouping (say, 2 point penalty for each extra or missing DPS, 2 point penalty for each extra or missing tank, 2 point penalty for each extra or missing healer, 3 point penalty for each extra person on the team over 6 or each missing person under 6; or whatever, you pick the penalty scheme).  Then you could plausibly define the objective function to be the sum of the penalty scores of all of the teams, and your goal is to find an assignment that minimizes this total penalty.

Next, you use some local search procedure to find an assignment that makes the total penalty as small as possible.  The simplest is hillclimbing, which works as follows.  Pick an arbitrary initial assignment (e.g., randomly assign each person to a team; or use any other heuristic method of computing an assignment -- it doesn't have to be optimal).  Then, in each iteration you randomly pick a modification to the assignment, check whether the proposed modification reduces the total penalty, and if so, you apply the proposed modification.  Repeat this over and over, until you go a long time with no improvement.

You need a way to generate a random modification.  A simple one would be to randomly pick two people, and swap which team they are on.  You can also consider more complex modifications.  For instance, randomly pick three  or fourpeople, and randomly permute them among their teams.  Or, randomly pick two people on two different teams, then randomly assign the first person to one of the two teams, then randomly assign the second person to one of the two teams (so this might put both people onto the same team; this modification is useful if you want to consider solutions where some teams have more than 6 people or fewer than 6 people).

This should be easy to program, and I suspect it'll give a reasonable solution.  I suggest trying it and see if you're happy with the solutions it generates.

There are a number of ways to make this more sophisticated, to try to generate solutions that are even better (lower total penalty).  You can use a more sophisticated form of local search.  For instance, you could try hill-climbing with random restarts, where you do the above process 100 times from 100 different random initial assignments, and keep the best solution found.  You could also try simulated annealing, where if the modification makes things worse we still have a (small) probability of applying the proposed modification, and we reduce this probability over time  in a specific way.

You'll have to modify this to deal with people who pre-register as a group.  Fortunately, it should be easy to generate modifications that respect this constraint.  For instance, suppose you randomly pick two people to swap, say Alice and John.  If you Alice is part of a pre-registered group with one other, then you might randomly pick someone on John's team so you can swap Alice + her partner with John + that additional person.    There are many possibilities; you should be able to select something that makes sense for your particular situation.


How to find the size of gaps between entries in an array so that the first and last element of the array is filled and the gaps are all of equal size? I have an array a of n entries. I need to place a token on the first and last position of that array, so a[0] = 1 and a[n-1] = 1.
I now want to place additional tokens into that array with a distance inbetween each index i where a[i] = 1 that is greater than 2 (so placing a token on every index is invalid as well as alternating using and not using an entry is invalid). Phrazed differently: I want that sum(a) < n/2 . The gap inbetween each token should be the same, so say with an array of size 16,
a[0] = 1, a[3] = 1, a[6] = 1, a[9] = 1, a[12] = 1, a[15] = 1
would be a solution with a gap size of 2 (distance of 3).
How do I find all gap sizes that are possible to fill said array with the given constraints?
Imagine a street inbetween two crossroads where a lamppost should be placed on each crossroad and then additional lampposts should be placed equidistant to each other and for some reason only natural number distances are allowed.
(The actual problem I want to solve is where to place Sea Lanterns in my Minecraft Project so do not disregard this problem as an assignment question I want a solution for.)

If I understand your problem correctly, the tokens (lanterns) can be placed every $x$ blocks (starting from $0$) if and only if $x>2$ is a divisor of  $n-1$.
For example, if the array has $n=31$ elements the valid values of $x$ are $3,5,6,10,15,$ and $30$.


What is the shortest total path between pairs of points? I have 2n random points on a plane. Join pairs of points to make paths. Pair the points such that the summed path length is a minimum. In the picture below, we are trying to minimise the total length of all red-line segments. Points cannot be reused.
Obviously there's the naive brute-force solution, but I wonder if there's a better way. I thought about picking the smallest path then eliminating and picking the next smallest path but then that doesn't guarantee the shortest overall path.
Any pointers welcome.

This appears to be a maximum matching problem.  Well, minimum matching, but you should be able to make the necessary adaptations.


Gradient descent overshoot - why does it diverge? I'm thinking about gradient descent, but I don't get it.
I understand that it can overshoot the minimum when the learning rate is too large. But I can't understand why it would diverge.
Let's say we have

$$J(\theta_0, \theta_1) = \frac{1}{2m}\sum_{i=1}^m (h_\theta(x^i)-y^i)^2$$

$$\theta_1 := \theta_1-\alpha\frac{\partial}{\partial\theta_1}J(\theta_1)$$

When the slope is negative the cost will converge to the minimum from the left of the graph, as $\theta_1$ will increase.
When the slope is positive it will converge from the right of the graph, as $\theta_1$ will decrease.
Now it might overshoot when the learning rate $\alpha$ is too large.
In that case it should overshoot again.
But not by much, should it not circle around the minimum? Why would it diverge?

If you overshoot by 10% you are fine, for example if the solution is 0 and the starting value 1000, you go to -100, +10, -1, +0.1 etc. If you overshoot by 80%, you converge but much smaller. If you overshoot by 110% you go from 1,000 to -1,100, +1,210, -1,331 etc. - divergence.


Bisimulations: Proof that the following LTS are not bisimilar I have the two LTS (labeled transition system) as seen in the following picture:

And the book is telling me that between those two LTS, their $1$ and $1'$ are non-bisimilar.

So I tried to get a bisimilation starting from the pair $\{\{1,1'\}\}$ by continuously extending it whenever I found a conflict, ending up with:
$$\{   \{1,1'\} ,\{2,2'\},\{3,3'\},\{2,4'\},\{4,3'\},\{3,5'\},\{4,5'\}               \}$$

Finally, to check whether it truly was a bisimilation, I checked for each pair each node, and asserted that all possible pairs of derivatives were part of the set.

I am arriving that they are a bisimilation - is the crux in the $a$'s and $b$'s? (They didn't really explain what it means)

The left diagram has a b and the right diagram has a c.  Thus, the pair $(2,4')$ does not satisfy the conditions required to be a bisimulation.  In particular, the book is correct that those two systems are not bisimilar.


Given NFA to recognize a language, construct a new NFA for that language without the empty string Describe a (general) procedure that, given some finite automaton M, produces a new finite automaton M’ with:  M’ rejects ε, but accepts otherwise the identical language as M does.Note that M may or may not accept ε, while M’ does not!

My solution is to discuss the different cases. If M doesn't contain ε, then, don't need to produce a new M', but if M contains ε-transition, then convert it to DFA. I'm not sure my procedure is right or not.

Can someone come up with some more effective idea?

Why go for a subtle or elegant answer? You can drive a screw in with a jackhammer, too.

Define a DFA $M_{\epsilon}^{-1}$ for the language $\Sigma^* \setminus \{\epsilon\}$. Hint: it has two states for any $\Sigma$.
Say how to construct $M'$ such that $L(M') = L(M) \cap L(M_{\epsilon}^{-1})$. Hint: use the Cartesian Product Machine construction.


Ordered set cover problem: is it NP-hard? Given a set of elements $U=\{1,2,\ldots,n\}$ and a collection of $m$ sets $\{S_1,S_2,\ldots,S_m\}$ whose union equals $U$. Each element $e$ of a set $S_i$ has a weight $w_i(e)$. The weight $w(S_i)$ of the set $S_i$ is defined as $w(S_i):=\max_{e\in S_i}w_i(e)$.

The problem is to choose an ordered collection of sets $O$ from $\{S_1,S_2,\ldots,S_m\}$ whose union is $U$ and its total weight is minimum.  Here, if $O=\{S_1,S_2,\ldots,S_p\}$, then we choose $S_1$, then we choose $S_2$, etc. We define the total weight $W(O)$ as the sum of the weight of the sets covering new elements, i.e. $$W(O)=w(S_1)+w(S_2\backslash S_1)+\ldots+w(S_p\backslash\bigcup_{i=1}^{p-1} S_i),$$ since we choose $S_1$ first, then all elements of $S_1$ are new. At the time we choose, $S_2$, the newly covered elements are $S_2\backslash S_1$, etc.

The decision version of your problem is NP-hard (and so, NP-complete), by reduction from SAT.

Let $\varphi$ be a SAT formula on variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$. The universe will be $\{x_1,\ldots,x_n,C_1,\ldots,C_m\}$. For every literal $x_i$ or $\bar{x}_i$, there will be a set $S_i$ or $\bar{S}_i$ consisting of $x_i$ together with all clauses satisfied by the literal, in which all elements have unit weight. This instance has a solution of weight at most $n$ if and only if $\varphi$ is satisfiable.

Indeed, if $\varphi$ is satisfiable, then the sets corresponding to a satisfying assignment are a solution of weight $n$, in any order.

Going in the other direction, Suppose that $T_1,\ldots,T_r$ is a solution of weight at most $n$. Any solution must cover $x_1,\ldots,x_n$, so it must contain either $S_i$ or $\bar{S}_i$. If a solution contains both $S_i$ and $\bar{S}_i$, then the one which appears later must have zero cost, that is, its elements must all be covered by preceding sets; so the solution remains a solution even if we remove it. Therefore we can assume that exactly one of $S_i,\bar{S}_i$ appears. The corresponding truth assignment is easily seen to be a satisfying assignment of $\varphi$.


Undirected graph whose BFS and DFS trees have roots of degree 2 Draw a graph on $5$ vertices that satisfies all of the following conditions:

$G$ is an undirected connected graph.
For every node $v∈V$, in the spanning tree received by BFS($v$), $\deg v=2$.
For every node $v∈V$, in the spanning tree received by DFS($v$), $\deg v=2$.

I was trying to draw many graphs but none of them satisfied all of the conditions.
I was also trying to disprove that such a graph exists, but couldn't find any strong claim that I could use for my proof.
Can you give me a hint?

The degree of the root in a BFS tree equals the degree of the vertex in the original graph. Hence condition 2 states that your graph is 2-regular. Since it is connected, it must be a 5-cycle. Running DFS on the 5-cycle results in a path, and in particular, the root has degree 1.
This argument shows that there's nothing special about the number 5: the result remains true for any number of vertices.


Finding a reduction for two-Subset sum problem I'd like to prove that the following problem is NP-complete. I'd just like to know what reduction I should do:

Two Subset Sum: Given a set S of integers and an integer T, determine whether there are two subsets of S such that the sum of the numbers of one is T and the other is 2T. The subsets do NOT have to be disjoint.

And I want to use the classic subset problem to prove this:

Subset Sum: Given a set S of integers and an integer T, determine whether there is a subset of S such that the sum of the numbers is T.

I'm slightly struggling with the reduction from Subset-Sum to 2-Subset-Sum, as simply adding to the set the double of each number and using the same T does not work, e.g S = {1,7,8,5} and S'={1,2,5,10,7,8,14,16} with T = 10 wouldn't work, as S' would return "true" and S should return "false".

Thank you.

There is a trivial reduction from Partition to your problem: given an instance $S$ of partition, construct the instance $(S,\frac{1}{2} \sum_{i \in S} i)$ of your problem. This shows that if you take any reduction from Subset-Sum to Partition, you immediately get a reduction from Subset-Sum to your problem. You can find the reduction from Subset-Sum to Partition in many places, or come up with it on your own.


Reduction to $n\log n$ time problem If a problem $A$ is poly-time reducible to a problem $B$ ($A <_\mathrm{p} B$), and $B$ can be solved in time $O(n\log n)$, can $A$ also be solved in time $O(n\log n)$?

You can't guarantee that $A$ can also be solved in time $O(n\log n)$ because the reduction from $A$ to $B$ might require more time than that (for example, $n^3$ steps).


What is the O time complexity for this algorithm? is the Big-O for this O(1) or some asymptotic like 1/n?

Saying that because if it defaults, the time limits at about 1000000 ns, but if it returns while in the loop, it is about a fraction of that. The time seems to increase very slightly as the inputs increase.

public static int[] call(int b, int c) {
    int[] f = new int[2];
    final double n = 1.13;

    for (int x = -100; x < 100; x++) {
        for (int y = -100; y < 100; y++) {
            if (((n+x)*(n+y)) == ((n*n)+(b*n)+c)) {
                f[0] = x;
                f[1] = y;
                return f;
            }
        }
    }
    return f;

    /* // timer method
     * long startTime = System.nanoTime() ;
     * call();
     * long endTime   = System.nanoTime() ;
     * long totalTime = endTime - startTime;
     * System.out.println(totalTime);
     *
     *      f(2, 1)   : 499284
     *      f(4, 4)   : 487452
     *      f(6, 9)   : 501479
     *      f(8, 7)   : 493296
     *      f(10, 21) : 500602
     *      f(12, 36) : 505862
     *
     */

}

Also, please ignore that the code is wonky.

The upper bound doesn't get affected by inputs b & c so we can say it is $O(1)$.


Find coverage for plane from half-planes The document (see pic. below) states that it is possible to find a cover of the plane by a subset of 3 half-planes. It proposes to use linear programming for this. How to formulate such a program?

The original document can be found here: On the Separation of a Polyhedron from Its Single-Part Mold.

EDIT: For clarity: i need to understand how can i use LP to find subcoverage of size 3 from coverage of bigger size.

I believe the connection between Helly's theorem and linear programming
stems from this paper:

  Amenta, Nina. "Helly-type theorems and generalized linear programming." Discrete & Computational Geometry 12, no. 3 (1994): 241-261.
  (Springer link.)

This arose from Nina Amenta's Ph.D. thesis (PDF download),
under the direction of Raimund Seidel.


What is the maximum possible degrees of a vertex of an MST What is the number that a minimum spanning tree can have a vertex with degree at most? Is there any rule? Is it related to the number of vertex or edge? Or not?

Suppose that the graph is already a tree. Then the minimum spanning tree is the graph itself. In particular, if we take a star on $n$ vertices, we obtain a minimum spanning tree having a vertex of degree $n-1$. This is optimal, since in a graph containing $n$ vertices, all degrees are at most $n-1$.


Proving property of a term using Induction This is one of the example lemma that has been proved in TAPL
book which I'm unable to grasp.

The objective is to prove |Consts(t)| <= size(t) where t is a term.

Now, Consts is a function defined like this:

Consts(true) = {true}
Consts(false) = {false}
... and so on

Similarly

size(true) = 1
size(false) = 1
... and so on

Now the proof in the book starts with something like "By
induction on the depth of t" and then goes to prove the
lemma. But I think I'm missing something here. Induction can be
applied when we have to prove something over natural number. But
there is no natural number involved in the above lemma. How come
then the induction is applied ?

A term is defined recursively.  You can do induction on recursive types, using structural induction.

For instance, suppose we say that a term is something of the form

$c$ (a constant), or
$t_1+t_2$, where $t_1,t_2$ are terms.

Then structural induction is (loosely) similar to doing a proof by (strong) induction on the size of the tree.  You prove that the property holds if the term has the form $c$ (that's the base case).  Then, you prove that if the property holds for terms $t_1$ and $t_2$, then the property holds for the term $t_1+t_2$.  You can probably see how to generalize this to terms whose syntax has a more complicated definition.


Prove transitivity of big-O notation I'm doing a practice question (not graded HW) to understand mathematical proofs and their application to Big O proofs. So far, however, the very first problem in my text is stumping me wholly.

Suppose $f(n) = O(g(N))$ and $g(n) = O(h(n))$ (all functions are positive).

Prove that $f(n) = O(h(n))$.

I am having lots of trouble with this, and it would be greatly helpful if someone showed me how to do this.

Consider using the definition of Big-O. If $f(n) \in O(g(n))$, then there exists a $c, n_0 > 0$ such that $f(n) \leq cg(n)$ for all $n \geq n_0$. Similarly, we can write a similar inequality for $g(n)$. We have that if $g(n) \in O(h(n))$, then there exists a $d, n_1 > 0$ such that $g(n) \leq dh(n)$ for all $n \geq n_1$.

To show what you are trying to show, consider putting both pieces together. Not only do we know that $f(n) \leq cg(n)$, but we also know that $g(n) \leq dh(n)$. Putting these two together gives $f(n) \leq c'h(n)$ where $c' = c \cdot d$, for the appropriate conditions. Can you verify what those are? In particular, for what values of $n$ does this hold?

From there, the desired result follows by definition of Big-O.


Allocating memory via Buddy Allocation I'm trying to learn buddy allocation and whilst I think I understand the basics of it, there is one problem exercise with which I'm struggling with.

So I have an 8K block and I'm using buddy allocation trying to always allocate to the leftmost free memory area.. and I need to allocate a 5K memory block.

Do I split the 4K block into two 2K blocks, and take (from the left) the 1k, 2k, 2k blocks, or do I split the middle 2k block into two 1k blocks and take the 4k and the first 1k block from the right? Or do i simply take the 2k and 4k blocks that I have now?

Or is this type of allocation simply not possible if I need to make use of the whole 8k block (since the first 1k block is being used)?

None of the above.  First, block sizes are rounded up to the nearest power of 2.  If you try to allocate an object of length 5K, it will first round that up to 8K.  Next, it will try to find a free block of size 8K.  In your example, you'll need to look at larger blocks -- the 1K, 2K, and 4K blocks are too small.  You'd better hope there is another 8K block (not shown) that is free, or an even larger block that is free and can be split up to create a 8K block.


Hardness of a special GAP-CLIQUE problem In the GAP-CLIQUE$(k,\ell)$ problem, we are given a graph $G$ over $n$ vertices and have to decide whether $G$ contains a clique of size $k$ or no clique of size $\ell$. Using a PCP system, it can be shown that GAP-CLIQUE$(k,\varepsilon k)$ is NP-hard for any positive constant $\varepsilon$ less or equal to $1$. In fact, even GAP-CLIQUE$(k,n^{\varepsilon - 1}k)$ is NP-hard. However, I am interested in GAP-CLIQUE instances, where $k$ and $\ell$ depend on the size of $G$. In particular, I am wondering if GAP-CLIQUE$(3/4n,1/4n)$ is NP-hard.

The problem is solvable in polynomial time, using the following algorithm:

  Keep removing pairs of unconnected vertices, until a clique remains.

If the graph has a clique of size $(3/4)n$, then the clique you end up with contains at least $n/4$ vertices (exercise).

Source: Boppana and Halldórsson, Alon and Kahale.


How can you see which points in the spectrum is from which pixel in the original image? Take the image and spectrum below.
If I look at the spectrum, it just look like noise....
How to make sense of it intuitively?

Image:

Frequency spectrum of image (using Fourier Transform):

As stated by @tomasz, the fourier transform relates only globally to the image since the pixels of the transform correspond to frequencies in the original image
(which you may intuitively understand - somewhat - as speed of color variation as you move on the original image).
This is well explained on the web : An Intuitive Explanation of Fourier Theory

Look in particular at the bottom of the page.


Finding the k-th smallest ternary sum of elements from three different arrays The problem goes like this:

Given arrays $\{ a_i: 0\leq i \leq n-1 \},\{ b_i: 0\leq i \leq n-1 \} $ and  $\{ c_i: 0\leq i \leq n-1 \}$, we want to know what is the $k$-th smallest combination $a_r+b_s+c_t$ where $r, s, t$ are arbitrary indices.

Since $k$ is relatively much smaller than $n^3$ (we may suppose $k \approx n $ for simplicity), it would be wasteful to: naively enumerate all $n^3$ possibilities and find the $k-$th smallest using a binary heap.

What is a more efficient way (in terms of time complexity) to solve this problem? I try to optimize the naive algorithm described above by first sorting three arrays then do the heaping for $\{ a_r + b_s + c_t: r+s+t < k \}$, but I believe this is far from a most efficient algorithm. Thanks.

(Rmk: the algorithm is intended to be comparison-based, since elements might be non-integers.)

You can first sort the three arrays. In the following answer we assume these arrays are already sorted.

You can maintain a priority queue $Q$. Initially it contains only $a_0+b_0+c_0$. Then in each iteration, you pop the smallest element (say $a_r+b_s+c_t$), and add $a_{r+1}+b_s+c_t$, $a_r+b_{s+1}+c_t$ and $a_r+b_s+c_{t+1}$ (duplicates are not allowed, while it is easy to check whether a combination already exists in $Q$). Now we can claim the popped sum in the $i$-th iteration is the $i$-th smallest sum.

This algorithm takes $O(n\log n)$ time. If the given three arrays are already sorted, the time is reduced to $O(k\log k)$.

We can use mathematical induction on $i$ to prove the correctness. Suppose the $i$-th smallest sum is $a_r+b_s+c_t$, then we have the following chain:

\begin{align}
&a_0+b_0+c_0\\
\le\ &a_1+b_0+c_0 \\
\le\ &\cdots \\
\le\ &a_r+b_0+c_0 \\
\le\ &a_r +b_1+c_0 \\
\le\ &\cdots \\
\le\ &a_r +b_s+c_0 \\
\le\ &\cdots \\
\le\ &a_r+b_s+c_t.
\end{align}

For convenience, we denote by $S_0,\ldots,S_{\ell}$ these sums in the chain. Let $S_j$ be the first sum in the chain that is not popped before the $i$-th iteration. Then in the iteration that $S_{j-1}$ is popped, $S_j$ is added to $Q$ according to our algorithm. This means the sum popped in the $i$-th iteration must be no more than $S_j$, thus no more than $S_{\ell}=a_r+b_s+c_t$. By inductive assumption, the first $i-1$ smallest sums are popped before the $i$-th iteration, so the sum popped in the $i$-th iteration is exactly the $i$-th smallest sum.


Restriction and re-labeling on CCS In a process like
$$
R \stackrel{def}=((a.\bar{b}.0)\setminus\{b\})[a\to b]\mid(\bar{b}.b.0)+\bar{b}.c.0
$$

$b$ is restricted to perform on the inner process of RHS $(a.\bar{b}.0)\setminus\{b\}$, thereafter the $a$ is relabeled to $b$.
What I am confused is in drawing the LTS of it, the $a$ action occur at first process (we can have a transition with label $a$ in the LTS) and it is the next process that renaming takes place?
can the following LTS be valid as first actions transitions? (the bar is replaced by underline)

I am not completely sure about what is causing your confusion, but perhaps this can help:

$a.\bar{b}.0$ can only perform $a$.

$(a.\bar{b}.0)\setminus\{b\}$ can only perform $a$.

$((a.\bar{b}.0)\setminus\{b\})[a\to b]$ can only perform $b$ (i.e. $a$ after substitution).

The full process $((a.\bar{b}.0)\setminus\{b\})[a\to b]\mid(\bar{b}.b.0)+\bar{b}.c.0$ can perform $b$, $\bar b$ (two distinct ways), and $\tau$ (two distinct ways).

Also note that the unrelated process $((a.\bar{b}.0)[a\to b])\setminus\{b\}$ would instead be stuck.


What exactly is label noise? I've been doing research on precollege summer programs, and one ongoing project that has come up is "Improving Label Noise Robustness with data Augmentation and Semi Supervised Learning". So, could someone break this down for me? What is a label, what is label noise, and why is it such a large issue?

One of the main tasks in machine learning is classification. For example, given an image of a digit, which digit it represents? The desired algorithm assigns a label – in this case, a digit, to each sample – in this case, an image.
Supervised machine learning algorithms train classification algorithms using labelled data. The labels in the training set are typically manually generated by humans, who sometimes mislabel data. This is known as label noise. Label noise is usually the result of honest mistakes, but sometimes occurs out of malice. A third possibility is that some samples are genuinely hard to classify. Yet another possibility is that some labels are correct, but for various reasons we do not condone them.
Label noise is an issue since most machine learning models are trained on labelled data, and their performance is closely tied to the quality of the data they are trained on.


Greedy algorithm: Minimizing the maximum of a list Given a list $L$ of positive integers, assuming you can only modify the list by "splitting" its numbers a finite number $n$ of times. Write an algorithm which minimize the maximum of the last generated list.

By "splitting" a number $x$ I mean deleting $x$ from $L$ and adding to $L$ two positive numbers $\alpha,\beta$ verifying $\alpha+\beta=x$. We can only do this $n$ times.

My try was taking the two greatest elements of $L$, $\alpha$ (the maximum) and $\beta$ (the other), then I split $\alpha$ into $c=\min(\alpha/\beta+1,n+1)$ equal parts (the last part will be $\frac{\alpha}{(\alpha/\beta+1)}+\alpha\text{mod}(\alpha/\beta+1)$). So I spend $c$ of the hability.

Then I repeat the process until I run out of the hability or $\beta=1$, so then y take $c=\min(\alpha/\beta+1,n+1)-1$.

I know my try is not correct, as the list $(10, 4, 9)$ for $n=4$ is a counterexample. Any idea?

I'm not looking for efficiency details (it can be achieved working with heaps), only for correctness.

If we use $k$ splits on a single element $x$ of the list, the lowest value we can reach is $\dfrac{x}{k+1}$. In turn, we need $\displaystyle k = \left \lceil\frac{x}{v}\right\rceil - 1$ splits for $x$ to reach a certain value $v$.

Elements do not affect each other, after all to reach some maximum $v$ after splitting each element must reach it individually.

So you simply want to find the smallest possible $v$ such that $$\sum_{x \in L}\left\lceil\frac{x}{v}\right\rceil \leq n + |L|$$

You can find $v$ to arbitrary precision by using a binary search using the above check, starting with range $[0, \max L]$. Finding an exact answer is somewhat trickier though.


Understanding Incentive Compatibility of pooled Bitcoin Mining paper I'm trying to understand the paper Incentive Compatibility of
Bitcoin Mining Pool Reward Functions (Schrijvers, Bonneau, Doneh and Roughgarden, in Financial Cryptography and Data
Security – FC 2016 Workshops, BITCOIN, 2016; PDF).

In page 3 Section 2.1, they say pool operator does not know actual $\alpha_i$ mining power of player $i$. To estimate $\alpha_i$ depends on the reported shares and solutions.

A reward function $ R\colon H \mapsto [0,1]^n$ is a function from a history transcript to an allocation $ \{a_i\}_{i=0} ^ {n} $ with $ \sum_i a_i =1 $.
I don't understand this? What allocation does the authors mean?

What I somewhat understand from next para is $ H(k) = b = (y_1(k), \cdots, y_i(k) ) $ where $y_i(k)$ is no of shares reported by player $i$ in round $k$.
This I am basing on $H$ contains for each miner $i$ the total no of shares $b
_i$ reported in that round. History transcript is given by a vector $b \in N^n $.

Also what do they mean when they say " We use vector notation for $b$, so $b_1 + b_2 $ means component wise addition of these, and  $\|b\|_1 = \sum_{i=1}^n b_i $ is the sum of components of $b$"

Could someone explain with examples or in a more concrete way ?
Also any suggestions for understanding this paper would be much appreciated. Thanks.

Let's assume $n=3$ and at round $t$, miner_1 reported 2 shares, miner_2 reported 3 shares, and miner_3 reported 5 shares. And we'll further assume that in rounds from 0 to $t-1$, none of them reported any shares.

$R$ is the reward function that takes the history of the shares reported by all miners and returns a n-length vector, $a$, consisting of real numbers between 0 and 1.
Where $a_i$ corresponds to the fraction of total reward earned by miner $i$. So $ \sum_i a_i =1 $. $R_i$ corresponds to the reward earned by $i^{th}$ miner. So $R$ returns $<.2, .3, .5>$. When $i=1$, $R_i$ returns $.2$

$b_i$ (normal font) is the total number of shares reported by miner $i$. And $\textbf{b}$ (bold font) is a vector of length $n$, where each element corresponds to the shares reported by each miner. So $\textbf{b} = <2, 3, 5>$. When $i=1$, $b_i = 2$. And vector at round $t$, vector $\textbf{b}$ is denoted as $\textbf{b}_t$. So $\textbf{b}_1$ corresponds to the vector of shares reported at round 1 and $b_1$ corresponds to the shares computed by miner $i$.

Say at round $t+1$, $\textbf{b} = <1, 2, 7>$. So total shares reported in round $t$ and $t+1$ is component wise sum of $\textbf{b}_t$ and $\textbf{b}_{t+1}$.

Hope this helps.


Transforming SAT to Quadratic Programming in polynomial time I would like to show that Quadratic Programming is NP-hard.

I am currently reading a couple of papers which state that QP is NP-Hard and prove it by transforming SAT to QP, however I am finding the diction quite tough since I am just a beginner in the field. Would anyone happen to know the answer to this question who can maybe explain it to me in simpler terms?

The reduction of SAT to quadratic programming is pretty simple. The idea is that we can use the quadratic objective to "force" the variables to be Boolean, and so we can implement an integer linear program whose feasibility is equivalent to the SAT instance.

Given a SAT instance on a set of variables $x_1,\ldots,x_n$, we define the following quadratic program:
$$
\begin{align*}
& \min \sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 \\
\text{s.t.} & \\
& 0 \leq x_i \leq 1 & 1 \leq i \leq n \\
& x_{i_1} + \cdots + x_{i_j} + (1 - x_{k_1}) + \cdots + (1 - x_{k_\ell}) \geq 1 & \forall \text{ cl. } x_{i_1} \lor \cdots \lor x_{i_j} \lor \bar{x}_{k_1} \lor \cdots \lor \bar{x}_{k_l}
\end{align*}
$$
The linear constraints have a $0,1$ solution if and only if the SAT instance is satisfiable. Since $0 \leq x_i \leq 1$, a solution is $0,1$ if and only if $\sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 = 0$, and for any other solution $\sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 > 0$. Therefore the SAT instance is satisfiable if and only if the minimum is $0$ (or at most $0$).