Superpolynomial time set such that SP=NSP is known?

Take any time complexity class and its corresponding nondeterministic counterpart: $\mathsf{DTime(F)}$ and $\mathsf{NTime}(F)$ where $F$ is a family of nice functions containing polynomials and bounded by exponential functions. You are asking if we know these two classes are equal. We don't know!

Take $SAT$ as an example. A certificate can be verified in linear time so it is in $\mathsf{NTime}(n)$. However there is no algorithm that solves even very simple instances of $SAT$ (e.g. decide if the propositional statement that n+1 pigeons can be mapped into n holes is false) significantly faster than brute-force, i.e. exponential time. In other words, we don't even know if $\mathsf{NTime}(n) \subseteq \mathsf{DTime}(f)$ where $f$ is a little bit smaller than exponential function $2^n$. IF what you are asking was true then the lhs would be subset of your $\mathsf{NTime}(F)$ and therefore by your assumption a subset of $\mathsf{DTime}(F)$ where $F$ is smaller than exponential functions.

The question about $\mathsf{P}$ and $\mathsf{NP}$ is not only important because of Cobham's thesis that efficient computations are captured by $\mathsf{P}$, we don't know any simulation of nondeterminisitic time bounded machines by deterministic ones which doesn't use brute force search for the certificate. So the essential question about $\mathsf{P}$ vs. $\mathsf{NP}$ is can we find a certificate in a space exponentially faster than brute-force search of the space?

In fact, the question was known in Russian literature as the perebor problem (the brute-force search problem).

If you don't accept Cobham's thesis then you can think of $\mathsf{P}$ vs. $\mathsf{NP}$ question as the flagship of questions about the relation between verifying and constructing answers, or as I said above, as the question about existence of deterministic search algorithms which are exponentially faster than brute-force search.


Hint. Can you figure out a regular grammar such that for any $k, m, n$ with $k > n$ and $k > m$, there is a word in its language with that number of a, b and c (in any order)?

Hint. Did you know that you can sort with a context sensitive grammar? See an example for inspiration.


Is a bitstring easier to compress if it has lower Kolmogorov complexity?

I think your intuition is not correct. We can't effectively reason over the space of all programs, even all programs up to a given size (e.g. 90 for A and 10 for b) and it's not certain what the units are in your given KC measures for B and A.

As a simple example, imagine a program B that decompressed a highly compressible message and then encrypted it using some cipher and a hardcoded key. And imagine a different program A that simply output a hardcoded random string of the same length as the one produced in B. Given a long enough output, you could make K(output(B)) << K(output(A)), but both would be highly uncompressible without having the decryption key for B available.

What you're talking about sounds something like this:  https://en.wikipedia.org/wiki/Algorithmic_probability. It is uncomputable, but if you are willing to e.g. limit the execution time of programs and randomly sample from random programs, you can start to analyze very simple examples.


How is Rank Selection better than Random selection and RWS?

It's about controlling selection pressure. With roulette wheel selection, there are several scaling issues. If you have two individuals p1 and p2 with fitness values 1 and 2 versus having values 1001 and 1002, roulette wheel selection behaves drastically differently. Similarly, suppose the optimal fitness value of your function is at some f(x)=100, and you generate an initial population with fitness values all around 1, and one individual at 20. Roulette wheel selection will drastically favor the one best solution, simply because it's so much better than the others. But early in a run, that's probably a mistake. The population will quickly be taken over by copies of that solution. Just being way better than bad alternatives doesn't tell me enough information to be that aggressive in selecting it.

Ranked selection just looks at the rankings and so doesn't have this problem. Whether you're a little better or a lot better, we can precisely control how aggressively to exploit those better solutions.

Darrell Whitley is generally credited with the idea of Rank-biased selection in [1]. He published code for performing selection using this method. I've cleaned up that code a bit below. You'd have to integrated it with your own code to properly get the population size, etc., but it should be fairly self-explanatory aside from the actual formula -- that you can just take on faith or go read Whitley's GENITOR paper for details.

// return the index into the population of the selected parent.
// population must be sorted by fitness first
Chromosome select_parent(Population pop)
{
    double bias = 1.5;
    int index = (int)(pop.size() * (bias - sqrt(bias*bias - 4.0*(bias-1) * rand01()))
        / 2.0 / (bias-1));
    return pop[index];
}

The bias term governs how strongly we want to favor higher ranked individuals. You could tweak that to increase or decrease selection pressure, though in practice, I've never changed it from the default value of 1.5 given in the Whitley paper.

The only other detail is that I invented a notation for "rand01" to mean a function that returns a random floating point number in the interval [0.0, 1.0).

[1] https://www.researchgate.net/profile/Darrell_Whitley2/publication/2527551_The_GENITOR_Algorithm_and_Selection_Pressure_Why_Rank-Based_Allocation_of_Reproductive_Trials_is_Best/links/5632149808ae3de9381e72c5/The-GENITOR-Algorithm-and-Selection-Pressure-Why-Rank-Based-Allocation-of-Reproductive-Trials-is-Best.pdf


Theoretically yes, that NFA could have 9001 unreachable stats that are completely useless.

If you expect that NFA to be connected (common sense) then if you allow epsilon-moves you can have a huge useless cykle.

If you rephrase your question to:

Lets consider any Language and its 'smallest' (min number of states) NFA with $\epsilon$-moves and its 'samllest' DFA then the answer is no and the reason is simple.

any DFA is also NFA (names does not suggest that though).
therefore if we take a 'smallest' NFA and then manage find equivalent DFA that is 'smaller' that would contradict previous NFA being smallest.


Assume we have an algorithm HC for HAMILTONIAN CIRCUIT. How is it possible to convert the HC algorithm to an algorithm HP for HAMILTONIAN PATH?

The wording of the question is a bit unclear. You're supposed to reduce HamiltonianPath to HamiltonianCircuit: in other words, write an algorithm that solves HamiltonianPath by using a subroutine for HamiltonianCircuit.

I assume you're specifically going for a polytime reduction, so you shouldn't do an exponential amount of work in your new program—but there are a few different types of polytime reductions (Karp vs Cook in particular), and I can't get any more specific without knowing which one you're using. In a Karp reduction, for example, you only get to call the HamiltonianCircuit subroutine once, and have to return its output unmodified—all the transformation has to happen before you make the subroutine call. In a Cook reduction you can call it as many times as you want, and transform the outputs however you like before returning.


What are the differences between computer vision and image processing?

In image processing, an image is "processed", that is, transformations are applied to an input image and an output image is returned. The transformations can e.g. be "smoothing", "sharpening", "contrasting" and "stretching". The transformation used depends on the context and issue to be solved.

In computer vision, an image or a video is taken as input, and the goal is to understand (including being able to infer something about it) the image and its contents. Computer vision uses image processing algorithms to solve some of its tasks.

The main difference between these two approaches are the goals (not the methods used). For example, if the goal is to enhance an image for later use, then this may be called image processing. If the goal is to emulate human vision, like object recognition, defect detection or automatic driving, then it may be called computer vision.


What advantage do quadratic basis functions have over gaussian basis functions in RBF implementations?

...a strange choice for a basis function, since distant points in a training data set would seemingly influence the results of a local solution more than nearby points. Why is this function used as a basis function?

The sum of their influences quickly fades away. It's well illustrated in 1d, where we can represent a spline either piece-wise, locally controlled, or as one, 'global' RBF sum with $|x|$ kernel (see here for example). This might seem strange as each $c_i|x-x_i|$ term is unbounded. Yet, together they cancel out automagically at a distance. You can see it by following the derivation at the link. Another example is a system of electric charges overall neutral.

  what advantages does it have over something like a Gaussian basis function?

Multiquadric and other globally supported RBF have a good hole-filling property: if you have holes that are irregular with unknown scales, they're going to be smoothly interpolated over according to surrounding trends from neighborhoods of corresponding scales. If your dataset has a regular sparsity of one radius you can estimate, you can use instead compactly supported RBF, or Gaussian RBF which is practically local.


Are these two sensible and related or unrelated ways of regarding a logic system as a programming language?

Does it mean that a logic system is a programming language, where types are propositions and values of a type are proofs of the proposition?

Not necessarily, being both (logic systems and programming language) formal languages, there certainly is a certain degree of isomorphism between the two concepts, this translates into the fact that we can encode a logical system through a programming language and develop algorithms to identify proofs of the theorems of our logical system.

If you are interested in the similarities between logical propositions and types, I strongly suggest you take a look at Homotopy type theory.


Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial

The Galois field $GF(2^{128})$ has many different "concrete" representations. One popular representation is using polynomials in $GF(2)[x]$ (i.e. with coefficients in $GF(2)$) modulo some irreducible polynomial of degree $128$, say $x^{128}+x^7+x^2+x^1+x^0$. The magic constants $7,2,1,0$ come from this particular irreducible polynomial. You don't see $0$ since there is no need to shift by $0$. Similarly, the magic constants $57,62,63,64$ are the complements of the constants above with respect to $64$. Again, you don't need to shift by $64$ since the registers are $64$ bits wide. If we had used some other irreducible polynomial, the constants would have been different.

Regarding step 4, $[H_1:H_0]$ results from XORing $[E_1:E_0],[F_1:F_0],[G_1:G_0],[X_3:D]$. This implements the operation of MODing by $x^{128} + x^7 + x^2 + x^1 + x^0$. The idea is that modulo this polynomial, $x^{128} = x^7+x^2+x^1+^0$; addition here is XOR. The different summands corresponds to these different monomials – see if you can find the correspondence.


Maximum non-intersecting subset of circles

If it were me, I would encode this as an instance of ILP (integer linear programming) and let an off-the-shelf ILP solver deal with the backtracking and pruning.

Introduce $n$ variables $x_1,\dots,x_n$, where $x_i=1$ means that you include the $i$th circle in the subset and $x_i=0$ means you don't include it.  Add the following constraints:

$0 \le x_i \le 1$, for each $i$: this forces each $x_i$ to be either 0 or 1.
$x_i + x_j \le 1$, for each pair $i,j$ of circles that intersect each other: this enforces that you cannot choose two overlapping circles.

Now maximize the value of $x_1+x_2+\dots+x_n$ (this is the objective function).  Ask an ILP solver to find the optimal solution for you.  Internally, the ILP solver will likely use backtracking, pruning, branch-and-bound, and other sophisticated methods.

This will be a very efficient use of your time: rather than trying to program up each of those methods and debug your implementation, you can rely upon an existing well-tested ILP solver.  Also, given the amount of effort that has gone into optimizing ILP solvers, this approach might well perform better than any backtracking algorithm you're likely to come up with.


Is Turing machine a scientific theory in CS?

No, as Yuval Filmus explained, a Turing machine is not a scientific theory.

Furthermore, something can be both a mathematical model and a mathematical abstraction; for example, if the model is an abstraction.

Types of scientific theories

In the physical sciences, a scientific theory is a set of rules or models that makes testable predictions that could potentially be falsified. A Turing machine just isn't any of those.

In mathematics, the word "theory" may be used to describe a framework for reasoning where we have axioms, definitions, and inference rules for making deductions that follow from those axioms and definitions.  A Turing machine isn't that, either.

Personal opinion

I don't think it's a good use of time to devote a lot of energy to these kinds of questions. Instead, I would suggest that you learn the basic material in textbooks on Turing machines and computability and decidability, and don't worry too much about how to categorize or classify it or what words can be applied to it.  From a computer science perspective, it's more useful to focus on the mathematics without trying to put it into a philosophical framework or trying to come up with definitions of these broad, vague concepts (abstraction, theory, model).


Finding shortest paths in undirected graphs with possibly negative edge weights

I contacted one of the authors (Kevin Wayne; thanks) of the textbook "Algorithms, 4th Edition" and got a hint:

  Try adding "t-joins" or "perfect matching" to your web searches.

Following this, I found the following two lecture notes:

Shortest Path Algorithms Luis Goddyn, Math 408: Using Edmonds' Minimum Weight Perfect Matching Algorithm to solve shortest path problems for undirected graph with negative-weight edges, provided that $(G, d)$ is conservatively weighted, that is, if $G$ has no negative weight directed circuits (circuits $C$ whose total weight $d(C)$ is negative), then Dijkstra’s algorithm stops with a shortest path tree $T$ rooted at $s$.

$T$-joins and Applications from CS 598CSC: Combinatorial Optimization uses the $T$-join techniques.


We can write each permutation of $1,\ldots,n$ in cycle notation, which will help us understand the behavior of the algorithm.

Suppose that $i = 1$. If $1$ is a fixed point, then the algorithm simply moves on. Otherwise, suppose that the cycle involving $1$ is $(1\;a_2\;a_3\;\cdots\;a_\ell)$, which means that $a_2 = A[1]$, $a_3 = A[2]$, ..., $a_\ell = A[a_{\ell-1}]$ and $1 = A[a_\ell]$. The algorithm will exchange $A[1]$ and $A[a_2]$, so that $A[1] = a_3$ and $A[a_2] = a_2$. This has the effect of removing $a_2$ from the cycle. After $\ell-1$ such steps, the cycle is no more, and $i$ will be increased.

If the permutation has cycles of lengths $\ell_1,\ldots,\ell_r$, then the total number of swaps performed by the algorithm is $(\ell_1-1) + \cdots + (\ell_r-1) = n-r \leq n-1$. This explains your observation that the maximum number of swaps is $n - 1$.

At each iteration of the main loop, either we perform a swap, or we increase $i$. The former can happen at most $n-1$ times, and the latter at most $n$ times. Since each iteration runs in time $O(1)$, in total the algorithm runs in $O(n)$.


I don't think you can recover a unit production, unless (and this is probably the common case) the unit production is unambiguous. If there is only one derivation from a non-terminal to a particular terminal -- and it should be easy to figure that out while you are doing the transformation to CNF -- then you can record that derivation and reinsert it when you find the collapsed derivation in the CYK parse.


For multi-tape Turing machines, can we assume that each tape can be in its own state independently of the other tapes?

A Turing machine has just one state, even if it has multiple tapes. If you give each tape a separate state, it’s easy to forget that the action of each tape head can depend on the global state and on the character under every head, which is crucial, because it is the only way the tapes can communicate with each other. A multi-tape TM is a single computer with multiple I/O devices, not multiple computers each with one I/O device.

xskxzr’s answer shows that one state per tape doesn’t actually change the computational power of Turing machines. But it’s important to note that this requires the actions of all tape heads to be allowed to depend on every tape’s state and every tape’s current character. Thinking about each tape having its own state is likely to make you forget this, resulting in a less powerful machine. Conceptually, it’s usually not a good way to think about Turing machines.


Solve a recurrence relation with two recursion calls using the iteration method


Pushdown automaton for complement of { ww | ... }

You write

  So, I already know that $L = \{ww \mid w \in (0,1)*\}$ is not context free. Since CFL are not closed under complement its complement $L'$ is a CFL

Indeed $L'$ is context-free, but your argumentation is ...eeuh... nonsense. Shure, CFL are not closed under complement, meaning there exist context-free languages of which the complement is not context-free. In general however the complement of a CFL can be both CFL or non-CFL. Even if the complement of every CFL would be non-CFL [which is NOT the case] it would NOT follow that the complement of every non-CFL is CFL.

The language $L'$ indeed consists of all strings of odd length (that is a regular language and can be checked without using the stack) plus the strings of even length for which both halves differ. For the latter part see here.

Phrased more explicitly, let $K = \{ xy \mid |x|=|y|, x\neq y \}$ be the language from question 307 linked above. My claim is that $L' = K \cup \{ x \mid |x| \text{ is odd } \}$, as $L$ equals $\{ xy \mid |x|=|y|, x= y \}$. (And so this explains, as you say in your question, why odd and even length strings are treated separately.)

To answer your question how to implement this using a PDA, see the problem I have linked and its answers. A little hint. To check a word is of the form $xy$ with $|x|=|y|$, but $x\neq y$ we must be able to write $x=x_1ax_2$ and $y=y_1by_2$ with $a\neq b$, and both $|x_1|=|y_1|$ and $|x_2|=|y_2|$. Unfortunately we cannot check both length requirements at the same time. We can however test whether $|x_1y_2|= |x_2y_1|$, and that is enough. Essentially we find the matching positions of $a$ and $b$ without expicitly finding the middle of the string. (This is not at all obvious, please make some drawings.)


Approach to find minimum set in one table consisting of all items in second table

This is essentially the Set Cover problem, which is NP-hard, so you should not expect an algorithm that is always both exact and efficient (polynomial-time).

If you really need the minimum set, you have to resort to algorithms that sooner or later have to explore an exponentially large solution space. You might want to cast your problem as an Integer Linear Program (ILP) and use an ILP solver, or cast it as a Satisfiability (SAT) problem and use a SAT solver. If you want to implement the algorithm yourself from scratch, I suggest you have a look into branch and bound methods.

If you don't really need the minimum cardinality set, you can just greedily pick a name that covers as many as possible uncovered items, mark them covered, and repeat, until all items are covered. This won't do too bad, in a specific theoretical sense, although in practice it may be a relatively low quality solution.


What is the difference between "information model" and "conceptual model"?

Conceptual Modeling, Information Modeling and Data Modeling are all terms that more or less specify the same. I do not believe there is a common consensus about these terms.

When reading the articles of the authors you refer to, I get the impression that (for these authors) Conceptual Modeling is broader than Information Modeling.

A Conceptual Model can contain actors other than only computers (e.g. humans), can contain time aspects (e.g. events, and the required reaction to these events, called Behavioral Modeling by Olivé) and can contain concepts that will not necessarily translate into a data model (“we use the name conceptual modeling for the activity that elicits and describes the general knowledge a particular information system needs to know”).

An Information Model, as used by Lee et. al., has a more narrow scope (“The initial phase for developing an information model starts with the definition of the scope of the model’s applicability. The scope specifies the domain of discourse and the processes that are to be supported by the information model. It is a bounded collection of processes, information, and constraints that satisfy some industry need”) and his modeling seems to limit itself to a subset of the conceptual model. Lee et. al. also write their article with a particular industry in mind, manufacturing, where Olivé does not limit himself to an industry.

For example, a Conceptual Model could model a company including less tangible processes such as Strategy development an Marketing, and an Information Model could model some key process of the company derived from the conceptual model, for example purchasing and logistics.

I did not read their full article. I just did a scan to find where they apparently seem to differ and, as said, there is to my knowledge no clear consensus about what each term exactly means.


Matrix of a graph and computational complexity

Let $B_1 = I + A$. Then $B_1(i,j) = 1$ iff $d(i,j) \leq 1$, where $d(i,j)$ is the distance between $i$ and $j$ in the graph. Now $B_2 = B_1^2$, and so by definition,
$$
(B_2)_{ij} = \bigvee_k (B_1)_{ik} \land (B_1)_{kj}.
$$
In words, $(B_2)_{ij} = 1$ iff there exists a vertex $k$ such that $(B_1)_{ik} = (B_1)_{kj} = 1$, i.e. $d(i,k) \leq 1$ and $d(k,j) \leq 1$.

We can now prove that $(B_2)_{ij} = 1$ iff $d(i,j) \leq 2$. Indeed, if $(B_2)_{ij} = 1$ then there exists $k$ such that $d(i,k),d(k,j) \leq 1$, and so $d(i,j) \leq d(i,k) + d(k,j) \leq 2$. Conversely, suppose that $d(i,j) \leq 2$. We consider two cases. If $d(i,j) \leq 1$ then $k := j$ satisfies $d(i,k) \leq 1$ and $d(k,j) = 0 \leq 1$, and so $(B_2)_{ij} = 1$. If $d(i,j) = 2$, choose a shortest path from $i$ to $j$, and let $k$ be the vertex in the middle. Then $d(i,k) = d(k,j) = 1$. In both cases, $(B_2)_{ij} = 1$.

You cannot compute $C_2$ faster than $n^2$, simply because it contains $n^2$ many entries. The asymptotically fastest way known to compute $C_2$ is by squaring $I + A$ (using the usual matrix multiplication), zeroing the diagonal, and replacing each entry larger than 1 with 1. This takes time $O(n^\omega)$, where $\omega$ is the matrix multiplication constant.


call by name : how are clashing variables handled?

Programming languages do not "textually substitute" anything, that would be horribly inefficient. The "textual substitution" definition may be offered sometimes as a sort of textbook explanation, but it usually fails to capture all the details.

There are many techniques for dealing with the problem you describe. By the way, the problem is known as "variable capture" beacuse a binder "captures" a variable.

One possiblity is to eliminate all variable names and use de Bruijn indices instead. Substitution still requires a bit of work, namely shifting of indices, but at least one does not have to generate new names.

Another possibility is to create closures. These are used for evaluation of functions (I did not say "application"!), but in a call-by-name language we could use them for any expression. Briefly, when we evaluate P(i + j) in your code, we create a closure (η, i + j) where η tells us what the values of variables are at that point in the execution (so concretely, η would be something like i ↦ 100, j ↦ 50, P ↦ ..., main ↦ ....). When P actually needs the value of its argument, we evaluate i + j in the environment η (and not in the environment of P), so that i + j gets evaluated in the "old" environment.

There are still many other techniques for avoiding variable capture. Haskell compiles to a spineless tagless G-machine, or at least it used to.


Upper bound on the average number of overlaps for an interval within a set of intervals

If we ignore $L$ and focus only on the parameters $C,K,M$, the following upper bound is asymptotically tight, i.e., it's about the best you can do, up to a constant factor:

$$\text{Avg}(\mathcal{I}) \le \min(MC,K).$$

Proof that it's an upper bound: Fix any interval.  We're promised that it overlaps with at most $K$ others.  Also, the interval has at most $C$ points in it, so by a union bound over those points, we can also infer it overlaps with at most $MC$ others.  Therefore, it overlaps with at most $\min(MC,K)$ others.  Now the average of a bunch of numbers that are all $\le \min(MC,K)$ will itself be $\le \min(MC,K)$.

Proof that it's tight: I will show the construction of a set of intervals where $\text{Avg}(\mathcal{I}) \sim \min(MC,K)/4$.  There are two cases:

Case 1: $K \ge MC$.  Then use $M/2$ copies of each interval of the form $[i,i]$ (i.e., each length-0 interval), and use $M/2$ copies of the interval $[1,C]$.  You can observe that the latter each intersect with $\sim MC/2$ other intervals (and all intersect with fewer than $K$).  So, the average is about $MC/4$.  This gives a collection of intervals where each point intersects with $M$ intervals, each interval intersects with $\le K$ others, and $\text{Avg}(\mathcal{I}) \sim MC/4 = \min(MC,K)/4$.
Case 2: $K < MC$.  Set $C' = K/M$, apply the above construction to the interval $[1,C']$ instead of $[1,C]$, and we obtain a collection of intervals where each point intersects with $M$ intervals, each interval intersects with $\le K$ others, and $\text{Avg}(\mathcal{I}) \sim MC'/4 = K/4 = \min(MC,K)/4$.

If you also care about the dependence on $L$,  you might be able to build on the above analysis to see how it might depend on $L$.


Cache strategies, what reference article could I study?

The best strategy to find the best suitable algorithms for caching is to read survey papers in this area. I recommend the paper A survey of Web cache replacement strategies by Podlipnig and Böszörmenyi (2003) which reviews many general techniques for caching.


How to build the Reduction from Hamiltonian Cycle problem to Subgraph isomorphism?

Reduction $HC \leq SubgraphIsomorphism$ is done as $G \rightarrow \langle G, C_n \rangle$ where $n$ is the number of vertices in $G$, and $C_n$ is the cycle graph with $n$ vertices. This effectively means that $G$ has a subgraph $C_n$ if and only if $G$ has a Hamiltonian Circuit.

There are mainly three types of common reductions. $A \leq_L B$, $A \leq_P B$ and $A \leq_M B$ i.e. log-space reduction, polynomial-time reduction and turing reduction. If we don't specify, it usually means polynomial-time reduction which is also known as Karp reduction.

Let us take $A \leq_P B$. It means we can transform an input $x$ of problem $A$ to an input $f(x)$ of problem $B$ in polynomial-time such that (and this is important) $x$ is a yes-instance of $A$ if and only if $f(x)$ is a yes-instance of $B$. This effectively gives us a polynomial-time algorithm to check yes-instances of problem $A$ if there is a known polynomial-time algorithm to check yes-instances of problem $B$.

Now if $A$ is known to be a tough problem, like Hamiltonian Circuit problem, then $A \leq B$ will imply that $B$ is also a tough problem. That is, since $HC$ is NP-complete, SubgraphIsomorphism is also NP-complete (as we also know additionally that Subgraph Isomorphism is in NP, otherwise we would have only shown its NP-hardness).


Language of binary strings divisible by 7

The langauge is regular, so answers 1–4 are all correct.

The (deterministic) automaton has seven states, $0, \dots, 6$ corresponding to the remainder when the number is divided by 7. The initial state is $0$, which is also the only accepting state.  We adopt the convention that the empty string represents zero (as does the string "$0$", obviously).

To describe the transition function, suppose you're reading in some binary string and the bits you've read so far correspond to the natural number $n$ and the state you're in is $r=n\%7$ (the remainder when $n$ is divided by $7$). Let the next bit be $b\in\{0,1\}$.  When you read that, you'll have seen the number $2n+b$, so you need to move to state

$$r' = (2n+b)\%7 = (2r+b)\%7\,.$$

And, of course, there's nothing special about $7$.


Show that PTIME and PSPACE is closed under Klenee star

Suppose you are given a language $L$ in one of these complexity classes, and you want to decide $L^*$ in the same complexity class. On input $x_1 \ldots x_n$ (where the $x_i$ are bits), use dynamic programming to find out which substrings $x_i x_{i+1} \ldots x_j$ belong to $L^*$. Since there are only $O(n^2)$ such substrings, this will only cause a polynomial blow-up in the resources used.


Proving that recursively enumerable languages are closed against taking prefixes

Below is a hint for working with the Turing Machine (TM) formalism for RE languages. But finishing that approach from the hint depends on how you've been working with TMs.
You have a TM, say $T_L$ to accept L and you want to construct a new TM $T_L^'$ for $\text{Prefix}(L)$.  You can start $T_L^'$ on a string $x$ and then do something to finish up with the hypothetical $y$ that completes $xy\in L$. How you do that depends somewhat on the methods you have been using to work with TMs. But that's a hint so far.


There exist polynomial time algorithms for solving linear programs. These include the ellipsoid algorithm and interior-point methods. See Wikipedia.


Examples of problems for each class in $L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$

You can take complete problems for each class. Think of a complete problem as one which represents the "hardness" of this class, then under the assumption that all of the inclusions are strict, such a problem can not reside in the weaker classes.

If $\mathsf{L\neq NL}$, any $\mathsf{NL}$ complete problem (under logspace reductions) cannot lie in $L$ . An example for such a problem is deciding whether there exists a path between two given vertices in a directed graph.

If $\mathsf{P\neq NL}$, no $P$ complete problem (under logspace reductions) can lie in $\mathsf{NL}$ . One example for such a problem is $CVAL$, given a circuit and input, does the circuit outputs $1$ on the given input. You can find other examples of $P$ complete problems here.

If $\mathsf{P\neq NP}$, then NP-complete problems (under polynomial time reductions) cannot lie in $\mathsf{P}$. You can find hundreds of examples here, traveling salesman, hamiltonian path, SAT, just pick your favorite.

You probably got the point by now, but i'll say it anyway. If $\mathsf{NP\neq PSPACE}$ then PSPACE complete problems (under polynomial time reductions) cannot lie in $\mathsf{NP}$. Famous complete problems here are TQBF (checking if a CNF formula with quantifiers is true), and games (do I have a winning strategy in a game from a given position, of course you need to be careful and precisely define the language). You can find more examples on Wiki.

These were the easy examples, there are problems who are not complete for their class, but still believed to be hard. For example, FACTORING (deciding whether an integer has a factor smaller than some given number), is believed to be NP-intermediate (not NP complete but still not in P). See this question from cstheory about NL-intermediate problems. PSPACE is very far away from NP, and examples are easier here. If the polynomial hierarchy does not collapse, then any complete problem for $\Sigma_i$ with $i\ge 2$ is in PSPACE but not in NP.


What you are finding is that there are multiple versions of DPLL, all of which might have the name DPLL attached to them, even though they are a little different in some specifics.  If you need to distinguish between them, then I suggest you introduce your own terminology.  I don't think it really matters which one you call the "one true DPLL algorithm".  If you have to pick one, you could use the specification in the original paper, but I suspect it's probably best to understand "DPLL" as referring to a family of closely related algorithms that are very similar to each other but not identical.
"backtracking + unit propagation" is not a definition of an algorithm; it is at best a high-level summary.


It might be easier than you have been thinking.

$$\begin{aligned}
S&\rightarrow aS\mid U\\
U&\rightarrow aaUc\mid T\\
T&\rightarrow aTb\mid \epsilon
\end{aligned}$$

The idea is to identify the language that could be obtained by a fixed operation that peels off some symbols. Peeling off $a$'s, we shrink words in $S$ to words in $U$. Peeling off some $a$'s and $c$'s, we shrink words in $U$ to words in $T$.
$$\begin{aligned}
S&=\{a^ka^{2n}a^mb^mc^n \mid k,m,n \in \mathbb{N}_0\}\\
U&=\{a^{2n}a^mb^mc^n \mid m,n \in \mathbb{N}_0\}\\
T&=\{a^mb^m\mid m \in \mathbb{N}_0\}
\end{aligned}$$


It's easy to prove that

$\qquad\displaystyle n^3 \log^k n \in o(n^{3+x})$

for all $k \geq 0$ and $x > 0$. That should give you plenty of $\epsilon$ to choose from.


Is intersection of regular language and context free language is "always" context free language

The claim is that the intersection of a regular language and a context-free language is context-free. You've intersected a regular language ($\{ab\}$) and a context-free language ($\{a^nb^n\mid n\geq 0\}$) and the result was a context-free language ($\{a b\}$). Sure, that language is also regular but every regular language is also context-free. The statement isn't that the intersection of a regular language and a context-free language is a non-regular context-free language.
Analogously, the child of two mammals is a mammal. You've taken two mammals and you're saying, "Why is their child a cat? It's supposed to be a mammal."


First, consider "going through an entire file". There are a few assumptions worth thinking about here.
Files can be very big, and traversing them twice can be expensive. This is one reason why most real-world compression standards are based around blocks or windows.
There are situations where you don't have "the entire file" to begin with, such as a communication channel. TLS (prior to 1.3, at least) supports compression, for example.
Files are not always homogeneous. Archives (e.g. tar) are a case in point. A statistical model that is appropriate for one part of a file may not be appropriate for another part. Adaptive coding adapts to this, too.
As to your final question, if both the encoder and decoder knew the true probabilities of the symbols in the file we are compressing, then that wouldn't need to be transmitted. And, indeed, we sometimes do this in the real world. The JPEG standard, for example, specifies default coding tables for those times when they are appropriate, and lets an encoder supply their own when they are not.
Transmitting a static coding table efficiently (i.e. compressing it) is a nontrivial problem, especially for a large code alphabet. For a well-designed scheme, the cost of transmitting the table should be equal to the "learning cost" of using an adaptive code.


Unambiguousness and determinism of CFGs for them to be LR

Your first and second points are correct, although you need to take more care distinguishing between properties of grammars and properties of languages.

A language is context free if (and only if) there exists a context free grammar for it. It is also deterministic if (and only if) there exists a deterministic context free grammar for it. That doesn't mean that all grammars for the language will be deterministic or even context-free; there are basically an infinitude of possible grammars for any language, deterministic and not, ambiguous and not, and not restricted to the smallest class in the Chomsky hierarchy.

In fact, figuring out whether a language has one of these properties is often not easy. While we can easily see which of Chomsky's classes a grammar belongs to, and we can easily determine whether or not a particular context-free grammar is, for example, $LR(k)$ for any given $k$, similar statements about languages are much harder. In particular, the following questions are undecidable, which means that no algorithm exists which will produce a correct answer for every possible input:

Does a context-free grammar exist for a given language?
Does an $LR(k)$ grammar exist for a given language?
Does a deterministic grammar exist for a given language?

Some questions about grammars are also undecidable:

Is there a $k$ for which an $LR(k)$ parser can be generated for a given grammar?
Do two context-free grammars recognise the same language?
Is a given context-free grammar ambiguous?

(There are many more, but these ones seemed relevant.)

Note that "undecidable" doesn't mean you can't ever figure it out. For certain languages and grammars it is quite possible to answer the above questions. But there is no algorithm which can generate a solution. Finding a solution requires luck and perseverance, and there's no guarantee you'll manage it. (This is somewhat like the problem of proving a given mathematical hypothesis.)

One of the consequences of all that undecidability is that there are no 100% reliable algorithms which can "remove ambiguity" from a grammar, make a grammar deterministic, and so on. All of the procedures recommended in the various textbooks you refer to (and internet sites) are just heuristics: they might work, but there are no guarantees. If you determine that a given grammar is not $LR(1)$, or not $LL(1)$, etc., you can try applying the various procedures mentioned, but you might not be able to find a transformation which works. And the mere fact that you didn't manage that transformation proves absolutely nothing about the language, although again there are cases in which you can prove that a given language has no deterministic grammar, or even that it has no unambiguous grammar. (Languages for which no unambiguous grammar exists are called "inherently ambiguous" and you can find examples by searching for that phrase, if you're interested.)

I understand that this may all seem unsatisfactory. I think you really want there to be some visible attribute of a grammar (or language) which you can point to and say, "because of this feature, this grammar is not $X$" (for some property $X$). But there really isn't a better characterisation of, for example, grammars which are not $LR(1)$ than "the $LR(1)$ parser generation algorithm failed to produce a parser for this language".

So, in short:

A grammar is deterministic if the $LR(k)$ parser generation algorithm works for some $k$, and non-deterministic if it doesn't work for any $k$. But you can't prove non-determinism that way, because you'd have to try all possible values of $k$ and that would literally take you forever.

Furthermore, even if a grammar is non-deterministic, it might or might not be ambiguous. There's no algorithm which can tell you that, either.

Finally, with respect to my answer which you quoted, I think it does explain why that particular grammar is non-deterministic: it's because you need to do the first reduction when you hit the middle of the sentence, but since you don't know where the middle of the sentence is until you reach the end (and the sentence could be arbitrarily long), you cannot know at which point in the input you need to do the first reduction. However, the language is certainly unambiguous: there is only one derivation which works.

(These statements are true of palindrome grammars regardless of how many symbols there are in the alphabet. But if the alphabet contains only a single symbol, then there is a different grammar which happens to be regular. In this particular case it's not hard to figure out what it is.)


Complexity of multiplying two integers of size $n$ and $m$

The multiplication of two integers of size $n$ and size $m$ in base-2 with $n\le m$ can be done in time
$$O(m\cdot\log n\cdot\log\log n)$$
where the product will be given in base-2 as well.

Here is a sketch of the simple idea to prove the above claim.

Let positive integer $a$ has $n$ digits and positive integer $b$ have $m$ digits in base 2. For simplicity, let $m=kn$ for some integer $k$.
$$b=\sum_{i=0}^{k-1}\sum_{j=0}^{n-1}b_{i,j}2^{in+j}=\sum_{i=0}^{k-1}2^{in}b_i$$
where $0\le b_{i,j}\le1$, $b_i=\sum_{j=0}^{n-1}b_{i,j}2^j$. In other words, $b_{k-1}\cdots b_1b_0$ is $b$ in base-$2^n$.
So $$ab= \sum_{i=0}^{k-1}2^{in}(ab_i).$$

Since both $a_i$ and $b_i$ have $n$ digits, the product $ab_i$ can be computed in $O(n\cdot\log n\cdot\log\log n)$ (using FFT method). Multiplying by factor $k=\dfrac mn$, we see that all summands in the above equality and hence $ab$ can be computed in $O(m\cdot\log n\cdot\log\log n)$. Note that the computation cost of various bookkeeping and additions is not substantial enough to invalidate that bound.

This idea of splitting the bits of the bigger number by the length of the bits of the smaller number is articulated here first in Yuval's comment. That idea is, apparently, folklore among users experienced in algorithms.

If we have a smaller bound for the multiplication of the integers of the same size, we will get a smaller bound for the multiplication of integers of different sizes accordingly. For example, an algorithm by Harvey and van der Hoeven gives bound $O(n\log n\cdot 2^{2\log ^{*}n})$. So we will have bound $O(m\log n\cdot 2^{2\log ^{*}n})$ accordingly.


Algorithm for placing circles of Diameter d around the edge of another circle with diameter D

Circles centers form isosceles triangle with base of length $2r$ and arms of length $R+r$, so
$ \tan (\frac{\beta}{2}) = \frac { r}{ r+R} $ hance $\beta = 2\arctan(\frac{r}{r+R}) $


A question regarding definition of Deterministic Subexponential Time (SUBEXP)

In the definition of SUBEXP, $\epsilon$ ranges over all positive reals. But you get the same definition if you ask that $\epsilon < \epsilon_0$, for an $\epsilon_0>0$ of your choice; if you ask that $\epsilon$ be rational; if you only go over $\epsilon = 1/n$; and so on. This is because DTIME is monotone: if $f \leq g$ then $\mathsf{DTIME}(f) \subseteq \mathsf{DTIME}(g)$.
An alternative definition of SUBEXP would be:
$$
\mathsf{SUBEXP} = \bigcup_{g(n) = o(1)} \mathsf{DTIME}(2^{n^{g(n)}}),
$$
often denoted simply by $\mathsf{DTIME}(2^{n^{o(1)}})$.
Some examples: $\mathsf{P} \subseteq \mathsf{SUBEXP}$; a function which can be computed in time $2^{n^{1/\log\log n}}$ is in $\mathsf{SUBEXP}$; and a function which can be computed in time $2^{\log^{10} n}$ is in $\mathsf{SUBEXP}$.
In contrast, a function which can be computed in time $2^{n^{1/10}}$ is not necessarily in $\mathsf{SUBEXP}$ (and by the time hierarchy theorem, there is such a function which lies outside $\mathsf{SUBEXP}$).
A function in $\mathsf{DTIME}(2^{n/\log n})$ lies in SUBEPT but not necessarily in SUBEXP.


If $TS(n) = O(n)$ then $TSS(n,m) = \Theta(n+m)$.

If $TS(n) = O(n^2)$, then all we can say is that $TSS(n,m) = \Omega(n+m)$ and $TSS(n,m) = O(n^2+m^2)$.

How did I reach these conclusions? First of all, clearly $TSS(n,m) = \Omega(n+m)$. If $TS(n) = O(n)$ then $TS(n+m) = O(n+m)$ and so $TSS(n,m) = O(n+m + O(n+m)) = O(n+m)$. Altogether, $TSS(n,m) = \Theta(n+m)$.

If $TS(n) = O(n^2)$ then $TS(n+m) = O((n+m)^2) = O(n^2+m^2)$, since $(n+m)^2 = \Theta(\max(n,m)^2) = \Theta(n^2+m^2)$ (you might prefer the middle form to the one on the right). Therefore $TSS(n+m) = O(n+m+O(n^2+m^2)) = O(n^2+m^2)$.


Proving undecidability of HALT_tm by reduction

Sipser reduces $A_{\mathit{TM}}$ to $\mathit{HALT}_{\mathit{TM}}$. Since $A_{\mathit{TM}}$ is uncomputable, it follows that $\mathit{HALT}_{\mathit{TM}}$ has to be uncomputable. He is using the following general statement:

  If $A$ reduces to $B$ and $B$ is uncomputable, then so is $A$.

You are right that this general statement itself is proved by contradiction. A proof which uses this general statement to prove that a particular problem is undecidable is a proof by reduction – in your case, you prove the undecidability $\mathit{HALT}_{\mathit{TM}}$ by reducing a problem you already know is undecidable to $\mathit{HALT}_{\mathit{TM}}$. In contrast, Sipser's proof that $A_{\mathit{TM}}$ uses a different technique, diagonalization.


I am going to talk about the cache - related questions:

Block size is $$32 \text{words} = 2^5$$ . That, means that you need, 5 bits for offset.
$$\#\text{blocks}=\frac{2^{19}}{2^5}=2^{14}$$, so you need 14 bits for the index ( to indentify which block in cache is going to represent your wanted memory adresss )
For a 32 - bit adress, tag is the rest : $$32 - 14- 5 = 13$$ bits.


It's a big problem if you can't tell whether your proof counts as a proof or not. Perhaps it's better to write the proof "in words". Here is an example.

Since $M \subseteq M^*$ for every language $M$, clearly $L^* \subseteq (L^*)^*$. Now suppose $w \in (L^*)^*$. Then $w = w_1 \ldots w_\ell$ for some $w_1,\ldots,w_\ell \in L^*$. Then for each $i$, $w_i = w_{i,1} \ldots w_{i,\ell_i}$, where $w_{i,j} \in L$. So $w = w_{1,1} \ldots w_{1,\ell_1} \ldots w_{\ell,1} \ldots w_{\ell,\ell_\ell} \in L^*$. This shows that $(L^*)^* \subseteq L^*$, and so $L^* = (L^*)^*$.

This is probably very similar to the proof you give, but your proof is written "in symbols" and so it is somewhat hard to parse.


Justification for neglecting constant factors in Big O

To rationalize how asymptotic notations ignore constant factors, I usually think of it like this: asymptotic complexity isn't for comparing performance of different algorithms, it's for understanding how performance of individual algorithms scales with respect to the input size.

For instance, we say that a function that takes $3n$ steps is $O(n)$, because, roughly speaking, for large enough inputs, doubling the input size will no more than double the number of steps taken. Similarly, $O(n^2)$ means that doubling the input size will at most quadruple the number of steps, and $O(\log n)$ means that doubling the input size will increase the number of steps by at most some constant.

It's a tool for saying which algorithms scale better, not which ones are absolutely faster.


It means the automaton recognizes exactly it. in fact, you can even build an automaton that accepts every word (try to do it yourself), so there would be no meaning in the other definition


Show that the tree resulting from BFS is a spanning tree?

Observe that any spanning tree of $G$ contains every vertex of $G$, and has no cycles. Use induction to show that on every iteration, the process creates no cycles (and also visits every vertex).


Escaping characters is part of an abstraction, most commonly pertaining to programming languages.  Computer architectures, specifically at the sub-ISA level, don't know anything about it.


Finding an MST with one adding and removing vertex operation

After long hours facing this problem, with my advisor help, we could solve this problem in $O(|E(G^{'})| log\text{ }C)$ time complexity by using one iteration of the Boruvka's algorithm, where $C$ is the number of connected components of $G^{''} (V(G^{'}), T\backslash \{(v_k, v_i): v_k \in V(G^{'})\})$, i.e., the number of connected components of the MST $T$ by removing $v_i$ (and edges from $v_i$ to every other vertex in $T$) plus one (due to the inserted vertex $v_j$).
Note that, this solution might have $O(|E(G^{'})| log\text{ }|V(G^{'})|)$ time complexity if the removing of $v_i$ in $T$ (and edges from $v_i$ to every other vertex in $T$) lead to a totally disconnected graph. Also, note that, this solution has $\Omega(|E(G^{'})|)$ if C is equals to 3.


Choosing the optimal radix/number-of-buckets when sorting n-bit integers using radix sort

Minimizing run time is a very different question from minimizing operation counts. Sorting large data sets tends to be memory bound, so the goal of optimization is not to reduce the number of operations, but to try and do make efficient use of memory — for example,

do as much work as possible in L1 cache
use bandwidth to main memory efficiently by writing full cache lines
avoid overflowing the TLB by too much

Increasing the number of buckets works against all three points; it does no good to complete a radix sort in two passes if each pass takes three times as long as each pass of a four pass implementation!


Why no context switch is required in case of spinlock in operating systems?

Ask yourself why you use a context switch in a lock operation in the first place. What are the benefits and the disadvantages?

Now ask yourself if there are situations where the benefits are slim. How does a spin lock minimise the disadvantages of a normal lock operation?

Consider the cases where a lock is released after a minute, second, millisecond, microsecond or nanosecond.


In Constraint Programming, are there any models that take into account the number of variable changes?

It sounds like you want a cost-sensitive (cost-aware, budgeted) optimization technique. Minimizing two values (e.g. the solution of your objective and the cost of operations on $x$ and $y$) is a multicriteria optimization problem, and those tend to be very hard to solve. A common approach is to specify a budget for the maximum allowable costs and then minimize the objective function with respect to $costs(x,y) \le Budget$. This formulation tends to fit nicely into existing frameworks as an additional constraint. Of course, specifying the cost function and the allowable budget in such a way that you get meaningful solutions can be difficult - this will depend on the specific problem you are trying to solve.


Choosing a subset to maximize the minimum distance between points

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.


Difference between a TM with an empty language and the one accepting empty string

The definitions (well, descriptions) look correct, more or less.

A TM accepting the empty language may move directly into the halt reject state, regardless of what may or may not be on the input tape.

A TM accepting the language consisting of only the empty string may examine the first tape symbol. If the symbol is a blank, it could move to the halt accept state. Otherwise, it would move to the halt reject state. We don't have to worry about the user providing an input that starts on some later position in the tape since the blank symbol is not allowed in the input alphabet.

To summarize:

A TM for $\{\epsilon\}$ has pseudocode:

if tape[1] is blank then accept else reject

A TM for $\emptyset$ has pseudocode:

reject

or, if it helps you make the difference even clearer:

if tape[1] is blank then reject else reject

As Yuval points out in the comments, there are infinitely many TMs accepting one or the other of these languages; the two suggested here are for illustrative purposes only.

[EDIT]Some additional discussion motivated by recent comments.

(1) Depending on what your definition of a TM is and/or how explicit you want to be, there are two possibilities. If you want your machine to explicitly enter a halting state for every input tape, then yes, you will have a transition to the halt reject state on every symbol of the input alphabet. If you allow your Turing machine to reject strings by "crashing" (reaching a configuration for which there is no defined transition), then these transitions aren't necessary; simply transition to halt accept on blank, and let the machine crash in all other cases.

(2) Yes, the machine which accepts the empty language always rejects. Notice that it is perfectly acceptable to define automata with accepting states which are never reached (depending upon your definition, of course). In particular, we could take any arbitrary TM and change it to accept the empty language by changing all transitions from the initial state to lead to the halt reject state.

(3) Typically, TMs are understood to have two special states in addition to any "user-defined" states: the halt accept and halt reject states, which the TM enters to explicitly accept or reject, respectively, some input. In addition to these two states, an initial state is required from which to begin processing the input. By my reckoning, this means that every TM has at least three states. Notice, though, that not all of these states needs to be used by any given TM. In particular, a valid TM might endlessly loop on the initial state for all inputs; this TM will accept the empty language (although it doesn't decide it; to decide it, it needs to enter one of the halting states for each input).


Finding coprimes closest to a certain target

If you want the truely closest coprime to $\frac 4 7m$, you could start with $n = \mathrm{round}(\frac 4 7m)$. Then, while $\gcd(n,m) \neq 1$, try again with $n$ being the closest number to $\frac 4 7 m$ such that $n - q \not \equiv 0 \mod \gcd(q,m)$ for any previously checked number $q$ (keep track of previously checked numbers and gcds in a list)

Checking one candidate has complexity $\mathcal O(\log(m))$. The probability of any two numbers being coprime is $\frac 6 {\pi^2} \approx 60\%$ so the numbers of candidates to check should be $\mathcal O(1)$ on average.

Overall this should find you the closest coprime in $\mathcal O(\log(m))$ operations.


How do you find all integers in a sorted array of size n that appear n/k times, given that 0 < k < n, and in O(k log n) time?

Let m = ceil [n/k], so you want numbers occurring m or more times. Since the array is sorted, if you check array elements a [m-1], a[2m-1], a[3m-1] etc. you find all the integers you want (and some you don't want).

So you start with x = a [m-1]. If x == a [2m-1] then you found a number, and you can remove a[3m-1], a [4m-1] etc. as long as they are equal to x.

If x != a [2m-1], then you use binary search to find the largest i from m-1 to 2m-2 that is equal to x, and check whether x = a [i - m + 1]. That's the idea, you have to be a bit careful to implement it.

Since at most you do k binary searches in subarrays of length m, the time is O (k log m) = O (k log (n / k)) which is quite a bit better than O (k log n) when k is large (and if k is small then the execution time is small anyway).

A bit more careful implementation: You want to find all integers in a sorted array that occur at least m times. Let's call these integers "heavy". Let c = 0; throughout the algorithm you have found all heavy numbers before a [c], and there is no array element before a [c] that is equal to a [c].

If c + m - 1 ≥ n then you are done. Otherwise let i = c + m - 1 and x = a [i]. There can be no element in a [c] to a [i - 1] that is heavy and different from x, so the question is whether x is heavy.

Let j = i; and as long as j + m < n and a [j + m] = x, let j = j + m. Use binary search to replace j with the largest index from j to min (j+m-1,n-1) containing an element equal to x. So now a [i] to a [j] are all equal to x, and there is no element at a [j+1] equal to x.

If j ≥ i + m - 1 or a [j - m + 1] == x then x is heavy. In any case, replace c with j + 1 and continue.

We increase c at least by m at the cost of one binary search in an array of length m or less, or we increase c by m again in constant time.

PS. You could improve the execution time slightly as follows: You always check for the last number in an interval of size m-1 which is equal to x. Depending on where that last number is found, the algorithm makes more or less progress. To improve the worst case, you replace binary search by something slightly less balanced that is faster when the result is at the left end of the interval, so that there is less work if there is less progress.


Encoding a list of numbers using gamma coding

I'm assuming that you're referring to the Elias gamma code. This code is a prefix code, also known as a self-terminating code. This means that you can encode a sequence of numbers by simply concatenating the encodings of the individual numbers. Since the code is self-terminating, the concatenated encoding can be decoded into the encodings of the individual numbers.

A prefix code is a code in which no codeword is a prefix of another codeword. This allows you to decode the list as follows. Read bits until you reach a prefix of the encoding which constitutes a codeword. This encodes the first number. Remove and repeat.

Finally, let me stress that the Elias gamma code is a way of encoding numbers using a string of bits. When you write 0001100, you should think of it as a string of 7 bits. Eventually these bits will be decomposed into 8-bit chunks (knows as bytes) and stored or communicated in this way – as a string of bytes.


Time Complexity of Rabin-Karp matching algorithm

As pointed out by vzn above, the wiki article has all the details you are looking for.

Firstly, what is pre-processing and what is the online runtime, depends on what is remaining constant and what is varying. For example, if we are given some fixed text and are asked to match various small strings with that text, pre-processing would be hashing the text.

In this case, let us say we have only one string to be compared with one text, to avoid confusion about pre-processing. The operations that we need to perform are

Hash for string to be searched for ($p$) = $O(m)$
Hash for each $m$-sized substring in the text ($T$) (assuming rolling hash) = $O(n-m+1)$
Number of hash comparisons (one per each $m$ sized substring in $T$) = $O(n-m+1)$
If there are $r$ matches in the hashes, then we compare each of those substrings of $T$ with $p$ (each comparison being $O(m)$) = $O(rm)$

But in worst case, the number of matches in hash can be as large as $n-m+1$. So worst case complexity will be $O(m(n-m+1))$.


Is there an Interval Tree which supports O(1) dynamic space requirements for queries?

Short answer yes, you can achieve this in any type of tree, if there is a pointer from child to parent node.

The purpose of the stack is to remember you have to go back and visit another branch. Without the stack, but with the ability to go back to parent nodes, you can check if there is another branch that you should have visited.

Then the only space you need is 1 node. The query time might be slightly longer, although still log(n). The stack is an optimization, and after you remove it, you need an extra while loop to go back and check the latest other branch.


Unique triangulation duals of simple polygons

Given a tree $T$ with maximum degree three, is there always a simple polygon $P$ such that the dual of every triangulation (without Steiner points) of $P$ is equal to $T$?

Yes. To show this, I will give a procedure to get the seemingly slightly stronger result*:

  Given a tree $T$ with maximum degree three, construct a simple polygon $P$, such that the unique triangulation of $P$ (without Steiner points) has $T$ as its dual.

Start by creating an initial triangle $\Delta_0$, representing some vertex $v_0$ in $T$ and add $v_0$ to the queue $Q$.
Then, repeat the following until $Q$ is empty:

Pop the top element, $v$, from the queue.
For each neighboring vertex $w$ that for which we have not placed a triangle yet, choose a side $AB$ of triangle $\Delta_v$ and a point $D$ inside the conical regions generated by the line through $AB$ and its neighboring segments, such that the triangle $\Delta ABD$ does not intersect any other triangles. (See figure below) Set $\Delta_w\leftarrow\Delta ABD$ and add $w$ to $Q$.

This image gives an example of a possible polygon $P$ (left) for the given $T$ (right)

To see why this procedure works, first note that after creating a new triangle, the segments $AB$ and $AD$ generate a cone that has a non-empty region not-intersecting with the existing triangles (see also the earlier figure), so we can find a suitable point at every step and create a polygon.

Second, we have chosen the triangles such that line segment between $CD$ does not completely lie inside $P$. If there exists a corner-point $Q \notin \{B,D\}$ of the already placed triangles such that $DQ$ is fully in $P$, then it must lie inside the cones generated by $AD$ and $BD$. However, since the part of this cone that does not lie inside $\Delta ABD$ is contained in the cone generated by the earlier placed triangle, such a $Q$ exists only if there exists an analogous point for the earlier placed triangle. Since there does not exist such a point for the first triangle, this means there is no such point for any triangle we add.

This means that all pairs $(X,Y)$ of any corner point of $P$ for which the segment $XY$ is fully contained in $P$ is already in the constructed triangulation, so the triangulation is unique for $P$ (all triangulations add the same number of internal segments)

Note that the polygons constructed in this method tend to have rather sharp angles. I suspect arbitrary large graphs require polygons with arbitrary small angles, which could be a problem when drawing these polygons with finite precision.

*: The difference is that, if we interpret 'unique' as up to isomorphism (which is consistent with uniqueness of triangulations and duals being different), we would be ok with a polygon having multiple triangulations that all have isomorphic duals. However, it is possible to 'attach' more triangles to those polygons to ensure some duals are no longer isomorphic.


First, to dispel a possible cognitive dissonance: reasoning about infinite structures is not a problem, we do it all the time. As long as the structure is finitely describable, that's not a problem. Here are a few common types of infinite structures:

languages (sets of strings over some alphabet, which may be finite);
tree languages (sets of trees over some alphabet);
execution traces of a non-deterministic system;
real numbers;
sets of integers;
sets of functions from integers to integers; …

Coinductivity as the largest fixpoint

Where inductive definitions build a structure from elementary building blocks, coinductive definitions shape structures from how they can be deconstructed. For example, the type of lists whose elements are in a set A is defined as follows in Coq:

Inductive list (A:Set) : Set :=
  | nil : list A
  | cons : A -> list A -> list A.

Informally, the list type is the smallest type that contains all values built from the nil and cons constructors, with the axiom that $\forall x \, y, \: \mathtt{nil} \ne \mathtt{cons} \: x \: y$. Conversely, we can define the largest type that contains all values built from these constructors, keeping the discrimination axiom:

CoInductive colist (A:Set) : Set :=
  | conil : colist A
  | cocons : A -> colist A -> colist A.

list is isomorphic to a subset of colist. In addition, colist contains infinite lists: lists with cocons upon cocons.

CoFixpoint flipflop : colist ℕ := cocons 1 (cocons 2 flipflop).
CoFixpoint from (n:ℕ) : colist ℕ := cocons n (from (1 + n)).

flipflop is the infinite (circular list) $1::2::1::2::\ldots$; from 0 is the infinite list of natural numbers $0::1::2::\ldots$.

A recursive definition is well-formed if the result is built from smaller blocks: recursive calls must work on smaller inputs. A corecursive definition is well-formed if the result builds larger objects. Induction looks at constructors, coinduction looks at destructors. Note how the duality not only changes smaller to larger but also inputs to outputs. For example, the reason the flipflop and from definitions above are well-formed is that the corecursive call is guarded by a call to the cocons constructor in both cases.

Where statements about inductive objects have inductive proofs, statements about coinductive objects have coinductive proofs. For example, let's define the infinite predicate on colists; intuitively, the infinite colists are the ones that don't end with conil.

CoInductive Infinite A : colist A -> Prop :=
  | Inf : forall x l, Infinite l -> Infinite (cocons x l).

To prove that colists of the form from n are infinite, we can reason by coinduction. from n is equal to cocons n (from (1 + n)). This shows that from n is larger than from (1 + n), which is infinite by the coinduction hypothesis, hence from n is infinite.

Bisimilarity, a coinductive property

Coinduction as a proof technique also applies to finitary objects. Intuitively speaking, inductive proofs about an object are based on how the object is built. Coinductive proofs are based on how the object can be decomposed.

When studying deterministic systems, it is common to define equivalence through inductive rules: two systems are equivalent if you can get from one to the other by a series of transformations. Such definitions tend to fail to capture the many different ways non-deterministic systems can end up having the same (observable) behavior in spite of having different internal structure. (Coinduction is also useful to describe non-terminating systems, even when they're deterministic, but this isn't what I'll focus on here.)

Nondeterministic systems such as concurrent systems are often modeled by labeled transition systems. An LTS is a directed graph in which the edges are labeled. Each edge represents a possible transition of the system. A trace of an LTS is the sequence of edge labels over a path in the graph.

Two LTS can behave identically, in that they have the same possible traces, even if their internal structure is different. Graph isomorphism is too strong to define their equivalence. Instead, an LTS $\mathscr{A}$ is said to simulate another LTS $\mathscr{B}$ if every transition of the second LTS admits a corresponding transition in the first. Formally, let $S$ be the disjoint union of the states of the two LTS, $L$ the (common) set of labels and $\rightarrow$ the transition relation. The relation $R \subseteq S \times S$ is a simulation if
$$ \forall (p,q)\in R, %\forall p'\in S, \forall\alpha\in L,
   \text{ if } p \stackrel\alpha\rightarrow p'
   \text{ then } \exists q', \;
   q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R
$$

$\mathscr{A}$ simulates $\mathscr{B}$ if there is a simulation in which all the states of $\mathscr{B}$ are related to a state in $\mathscr{A}$. If $R$ is a simulation in both directions, it is called a bisimulation. Simulation is a coinductive property: any observation on one side must have a match on the other side.

There are potentially many bisimulations in an LTS. Different bisimulations might identify different states. Given two bisimulations $R_1$ and $R_2$, the relation given by taking the union of the relation graphs $R_1 \cup R_2$ is itself a bisimulation, since related states give rise to related states for both relations. (This holds for infinite unions as well. The empty relation is an unintersting bisimulation, as is the identity relation.) In particular, the union of all bisimulations is itself a bisimulation, called bisimilarity. Bisimilarity is the coarsest way to observe a system that does not distinguish between distinct states.

Bisimilarity is a coinductive property. It can be defined as the largest fixpoint of an operator: it is the largest relation which, when extended to identify equivalent states, remains the same.

References

Coq and the calculus of inductive constructions

Yves Bertot and Pierre Castéran. Interactive Theorem Proving and Program Development — Coq'Art: The Calculus of Inductive Constructions. Springer, 2004. Ch. 13. [website] [Amazon]
Eduardo Giménez. An application of co-inductive types in coq: verification of the alternating bit protocol. In Workshop on Types for Proofs and Programs, number 1158 in Lecture Notes in Computer Science, pages 135–152. Springer-Verlag, 1995. [Google Books]
Eduardo Giménez and Pierre Castéran. A Tutorial on [Co-]Inductive Types in Coq. 2007. [PDF]

Labeled transition systems and bisimulations

Robin Milner. Communication and Concurrency. Prentice Hall, 1989.
Davide Sangiorgi. On the origins of bisimulation and coinduction. ACM Transactions on Programming Languages and Systems (TOPLAS), volume 31 issue 4, May 2009. [PDF] [ACM] Associated course slides: [PDF] [CiteSeer]
Davide Sangiorgi. The Pi-Calculus: A Theory of Mobile Processes. Cambridge University Press, 2003. [Amazon]

More references suggested by Anton Trunov

A chapter in Certified Programming with Dependent Types by A. Chlipala
D. Sangiorgi. "Introduction to Bisimulation and Coinduction". 2011. [PDF]
D. Sangiorgi and J. Rutten. Advanced Topics in Bisimulation and Coinduction. Cambridge University Press, 2012. [CUP]


Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$

It is possible, if messy, to convert the proof of the Immerman-Szelepcsényi theorem to the reduction you want. There is absolutely no need to use the NL-completeness of st-connectivity.

Given an instance $G=(V,E),s,t$, we construct a new graph $G'=(V',E'),s',t'$. The "major vertices" of $V'$ record the following information: the current distance $d$ from $s$, the number of vertices of distance at most $d-1$, the number of vertices of distance $d-1$ counted so far, the current vertex we're guessing if it has distance at most $d-1$, the number of vertices of distance at most $d$ counted so far, the current vertex we're determining whether it has distance at most $d$. The minor vertices handle the part where we guess a path of length at most $d-1$ to a vertex which we guess to be of distance at most $d-1$. Edges that involve showing the vertex $t$ is reachable from $s$ are dropped. For each vertex which we're testing at the current distance, we only move forward to the next vertex if we have accounted for all vertices of smaller distance. When moving from distance $d$ to distance $d+1$, we copy the requisite information. The starting vertex $s'$ accounts for the fact that $s$ is the only vertex of distance zero. The ending vertex $t'$ is pointed at by all vertices representing the fact that the process has finished up to (and including) distance $n-1$, where $n=|V|$.

As you can see, it will be quite messy to write everything in full and correctly, but definitely possible. No overt use of NL-completeness was made, in that we never use the configuration graph of any NL machine. That's not needed, since we have something better than the configuration graph - the input instance itself.


I'd say the most well known barriers to solving $P=NP$ are

Relativization (as mentioned by Ran G.)
Natural Proofs - under certain cryptographic assumptions, Rudich and Razborov proved that we cannot prove $P\neq NP$ using a class of proofs called natural proofs.
Algebrization - by Scott Aaronson and Avi Wigderson. They prove that proofs that algebrize cannot separate $P$ and $NP$

Another one I'm familiar with is the result that no LP formulation can solve TSP (It was proved by Yannakakis for symmetric LPs and very recently extended to general LPs). Here is a blog post discussing the result.


Given a new point $x_q$, we find the $k$ closest points $x_1,\ldots,x_k$. Each one of them is associated with a cluster $f(x_1),\ldots,f(x_k)$. We assign $x_q$ to the most common cluster among $f(x_1),\ldots,f(x_k)$. The argmax equation is just a fancy way of expressing this idea: for any cluster $v$, the quantity $\sum_{i=1}^k \delta(v,f(x_i))$ is just the number of $x_i$'s which are assigned to cluster $v$, and the argmax picks up the cluster $v$ maximizing this parameter.


Approximation algorithm for Feedback Arc Set

Kann's online compendium of NPO problems is a good place to start. Feedback Arc Set (the "Directed part is redundant when you use "arc") is:

APX-hard,
Approximable within $\mathcal{O}(\log n \log \log n)$ (where $n$ is the number of vertices).

The problem is also fixed-parameter tractable1, so it might make more sense to solve the problem exactly, rather than use what looks like a bad approximation algorithm. (Or as Pål points out below, the running time is a bit... unpleasant, so maybe not.)

Notes

1 - JACM publication, Razgon & Sullivan's preprint, Chen, Liu and Lu's preprint - the problem was independently solved and the results combined to one publication


Why isn't the Swift programming language type inference more aggressive?

I don't understand Swift's typing system yet, so I can only speculate, but I imagine that it's for the same reason that Scala doesn't have full type inference: nobody knows how to do it in a pragmatically viable way. The combination of parametric polymorphism and subtyping is deadly from the point of view of algorithmic complexity.


How to use Latin hypercube sampling with fixed points?

You've divided the x values into 10 columns, and divided the y values into 10 rows, so we have a 10x10 grid.

Take any row that is already covered by some already evaluated point, and remove it from the set of rows.  Do the same with the columns.  In your picture, we are left with 6 rows and 6 columns.  Consider the 6x6 grid obtained by looking only at those 6 rows and 6 columns.

Now use your Latin hypercube sampling strategy on a 6x6 grid, to cover each of those 6 rows and each of those 6 columns.  This gives you 6 points that cover the 6x6 grid.  Now this can be interpreted as 6 points in the 10x10 grid, and if you combine those 6 points with the 4 existing points, you'll see that the result covers every row and every column exactly once.


The number of iterations for the outer loop is $\lfloor \log n \rfloor$. The number of iterations for the inner loop is $i = 2^k$, where $k$ is the number of current iteration of the outer loop.
So the number of computational steps is proportional to
$$\sum_{k = 0}^{\lfloor \log n \rfloor}{2^k} = 2^{\lfloor \log n \rfloor + 1} - 1.$$
Using the following inequality
$$n - 1 < 2^{\lfloor \log n \rfloor + 1} - 1 < 2n,$$
one can get that the time complexity of the algorithm is $\Theta(n)$.


Proving that NPSPACE $\subseteq$ EXPTIME

The expression $f(n)2^{O(f(n))}$ is simply an upper bound for the number of all configurations a $f(n)$-space bounded TM can have. Here is how to count: We have $|\Gamma|^{f(n)}=2^{O(f(n)}$ different ways how to fill the work tape, and the head can be on $f(n)$ different positions. There is also a constant number of states where we can currently be, but this is hidden in the big-O in the exponent.

If a TM takes more than $f(n)2^{O(f(n))}$ steps, then it has to visit one configuration twice. Hence it cycles and cannot stop.


How to show that there are $\binom{M+K}{M}$ different number of type bins?

The bins contain at most $M$ elements rather than exactly $M$ elements. This is why your formula doesn't work. In order to use your formula, we need to allow for one more type of element, a dummy type, and then we get $\binom{M+(K+1)-1}{M} = \binom{M+K}{M}$.

As an example, suppose that there is one type of element (so $K=1$). In that case, a bin can contain $0,\ldots,M$ elements, in total $M+1 = \binom{M+K}{M}$ choices.


Problem statement

Define the function $f$ by

$$f(a_1,\dots,a_k) = \sum_{i=0}^k \prod_{j=1}^i a_i.$$

In other words,

$$f(a_1,\dots,a_k) = 1 + a_1 + a_1 a_2 + a_1 a_2 a_3 + \dots + a_1 \cdots a_k.$$

Given $n$, you are looking for $a_1,\dots,a_k$ that form a solution to the equation

$$f(a_1,\dots,a_k) = n.$$

A useful lemma

Let me point out a useful property of the function $f$:

$$f(a_1,a_2,\dots,a_k) = 1 + a_1 f(a_2,\dots,a_k).$$

This follows immediately from the identity

$$1 + a_1 + a_1 a_2 + a_1 a_2 a_3 + \dots + a_1 \cdots a_k = 1 + a_1 (1 + a_2 + a_2 a_3 + \dots + a_2 \cdots a_k).$$

An algorithm for your problem

Now we get a reasonable algorithm for your problem, using dynamic programming.

Each subproblem is indexed by $(i,n')$, and records the best sequence $a_i,a_{i+1},\dots,a_k$ such that $f(a_i,a_{i+1},\dots,a_k)=n'$.  Now we can find the best solution to the original problem by enumerating all possible values for $a_1$, then looking for a solution to the $(2,(n-1)/a_1)$-subproblem.  And, we can solve the $(i,n')$-subproblem by enumerating possible values of $a_i$ and looking for a solution to the $(i+1,(n'-1)/a_i)$-subproblem.  Of course, as a straightforward optimization, we can limit our search to only values of $a_i$ that are a divisor of $n'-1$.

How many subproblems are there, in all?  A simple bound is that there are at most $kn$ subproblems, so the running time of this algorithm is at most $O(kn^2)$.  Using the optimization, I expect the running time will be much less in practice, as most values of $n'$ have only a limited number of divisors.  (See also this question for a math question that is related to the efficiency of this dynamic programming algorithm.)

Another optimization

Here is one more optimization you could apply.  You could use modular arithmetic to quickly filter out subproblems that have no solution.

Suppose we have a small prime $p$, and we have fixed values of $k,n$.  Then if there exists a solution to $f(a_1,\dots,a_k) = n$, then there exists a solution $f(a_1,\dots,a_k) \equiv n \pmod p$; conversely, if there is no solution to $f(a_1,\dots,a_k) \equiv n \pmod p$, then there is no solution to $f(a_1,\dots,a_k) = n$.

So, we could pick a small prime $p$, and then tabulate for which values of $(i,n')$ the $(i,n')$-subproblem has a solution.  Note that we only care about the value of $n'$ modulo $p$, so there are only $kp$ such subproblems, and we can enumerate which ones have a solution in $O(kp^2)$ time using dynamic programming.  (We cannot use the divisibility optimization any longer.)

So, we could precompute a table of size $kp$ and use it to filter out subproblems.  Before trying to solve the $(i,n')$-subproblem, we first look up $(i,n' \bmod p)$ in our table to see whether it has a solution modulo $p$.  If it doesn't have a solution modulo $p$, we don't try to explore that subproblem (we don't try to look for a solution in the integers; we know it'll fail).

We can build a table for each of a handful of small primes, say $p=2,3,5,\dots,17$, and check against each of these tables before exploring a subproblem.  This might reduce the number of subproblems that have to be explored, and thus improve efficiency.

Can we use this idea plus the Chinese remainder theorem to solve the original problem?  Unfortunately not: the requirement that $a_i \le m$ does not behave well under modulo arithmetic.  Thus, if all we wanted to know is whether there exists some sequence of positive integers $a_1,\dots,a_k$ satisfying $f(a_1,\dots,a_k)=n$, then we could solve that in $\text{poly} \log (n)$ time by looking for a solution modulo a set of small primes whose product exceeds $n^k$, then applying the Chinese remainder theorem.  However, your question asks whether there exists a sequence $a_1,\dots,a_k$ satisfying $f(a_1,\dots,a_k)=n$ such that $a_i \le m$ for each $i$, and that cannot be solved efficiently in such a way.  If you were willing to drop the requirement that $a_i \le m$, then your problem could be solved a lot more efficiently.


Can we create recursive functions only by using if-else statements?

If a program doesn't include any loop, recursion or equivalent construct, then it cannot express recursive computations.

In order to write a formal proof, you'd need to define your language formally. “Equivalent construct” can include some exotic things such as parallel execution, exception handlers, higher-order functions (leading to fixpoint combinators), meta-execution facilities (eval), etc. that let recursion in through a backdoor.

Suppose that a language contains only the following constructs: constants, assignments, sequence (do a then do b), functions operating on base types (but not functions taking functions as arguments), conditionals (if (x == y)), some primitives on base types (e.g. +, *). Then the execution of the program takes a time that is at most exponential, and in particular bounded, in the size of the program (the unit of time is an elementary expression, e.g. x := y takes one unit, x := y + z takes two units). In a nutshell, function application at most multiplies the complexity of the function by the complexity of the program, and the rest is linear.

Since this language can only express bounded-time computations, it cannot express all recursive programs (and in fact it cannot even express all primitive recursive programs).


Time complexity of a problem inspired by palindromes

After a wrong polynomial-time attempt, this is a more robust idea to prove that the problem is indeed NP-complete.

The reduction is from the 3-PARTITION problem which is strongly NP-complete; i.e. it is still NP-complete even if the numbers are represented in unary.

The problem is to decide whether a given multiset $S = \{a_1,a_2,...,a_n\}$ of $n = 3 m$ positive integers, can $S$ be partitioned into $m$ triplets $S_1, S_2, ..., S_m$ such that the sum of the numbers in each subset is equal?

Let $p = (\sum_i a_i) / m$

Note that the problem remains strongly NP-complete even if $p/4 < a_i < p/2$ (which forces each $S_i$ to contain at exactly three elements); see the original definition of 3-PARTITION in Garey&Johnson, Computers and Intractability.

We can build an equivalent EVEN PALINDROME instance in this way:

We add the long string:

$$w = 1 \, 0^p \, 111 \, 0^p 11111 \, 0^p \, ... \, 0^p \, 1^{2m+1}$$

Then we add $n$ more strings:

$$v_i = 0^{a_i}\; , \;i = 1...n$$

and $1 + 3 + 5 + (2m+1) = \sum_{j=1}^{m+1} (2j-1)$ strings of length 1:

$$r_k = 1 \; , \; k = 1...\sum_{j=1}^{m+1} (2j-1)$$

Note that $|w| = \sum_{i=1}^n |v_i| + \sum_k |r_k|$

Proof:

By construction the $w$ contains substrings of odd increasing length $(1,111,11111, ...)$, so it cannot be "placed" in the middle of $u u^R$; but it must be placed entirely in $u$ or entirely in $u^R$ (without loss of generality suppose that it is placed in $u$.

Now the others $v_i$ must be arranged in the opposite part $u^R$ and in such a way that every $p$ zeroes (that can be "totalized" using the $v_i$) an odd number of the $r_k$ can be placed (to reflect the corresponding $1^{2j+1}$ substring of $w$). Furthermore all elements must be placed, so exactly 3 $v_i$ must be picked to reflect each of the $0^p$ substring of $w$. So if an EVEN PALINDROME can be found it induces a valid 3-partition of the $a_i$ of the original problem.

The opposite direction (a 3-partition exists $\Rightarrow$ there is an EVEN PALINDROME is immediate by construction).

Example:

3-Partition instance: $S = \{1, 1, 1, 2, 2, 3 \}$, strongly NP-complete; so we can also represent the numbers in unary: $S' = \{ 1_1, 1_1, 1_1, 11_1, 11_1, 111_1 \}$

EVEN PALINDROME reduction:

$w = 1000001110000011111$

$v_i = \{ 0, 0, 0, 00, 00, 000 \}$

$r_k = \{ 1,\quad 1,1,1,\quad 1,1,1,1,1 \}$

Solution of EVEN PALINDROME:

$$uu^R = 1000001110000011111 \quad 11111 \; 0 \; 00 \; 00 \; 111 \; 000 \; 0\; 0\; 1\}$$

which corresponds to the 3-partition:

$S_1 = \{ 1, 2, 2 \}, S_2 = \{ 3, 1, 1 \}$


How broad is the meaning of "algorithm"?

No.  A specific neural network is just the (weights) parameters of an algorithm for function approximation.

A neural network in general yes, is the algorithm for classifying a given x into a class, given a probabilistic distribution (weights).

This is like asking weather a specific VAT rate is an algorithm.  The calculation of VAT is an algorithm but the VAT rate is not.


1) $T(n) =  3T(\frac{n}{2}) + n \in \Theta(n\ln(n))$

a = 3, b= 2 and f(n) = $\Theta(n)$

$n^{\log_b a} = n^{\log_2 3} > n^{\log_2 2}  = n = f(n) \therefore f(n) \in \Theta(n^{\log_2 3})$

(Case 1) Proved False

2) It is not in the Master Theorem format $T(n) =  aT(\frac{n}{b}) + f(n) \therefore$

It is not possible to say if the statement is true or false using the Master Theorem

3)  $T(n) =  2T(\frac{n}{3}+1) + n  = 2T(\frac{n+3}{3}) + n \in \Theta(n\ln(n))$

a = 2, b= 3 and f(n) = $\Theta(n)$

$n^{\log_b a} = n^{\log_3 2} < n^{\log_3 3}  = n = f(n) \therefore$

Case 3.

Now we could check if it is the case that $T(n) \in \Theta(f(n))$, but we don't need to, because the only way it would be $\Theta(n\log n)$ was if it was case 2.


You may be interested in the work on Ceptre, a result of the PhD research of Chris Martens, which uses type theory for interactive storytelling. Quoted below is the thesis abstract:

  Interactive storytelling weaves together deep computational ideas with humanity's rich history of story and play, providing an important context for tools and languages to be built. At the same time, formal specification languages offer a palette of representation and inference techniques typically reserved for the analysis of programming languages and complex deductive systems. This thesis connects problems in the interactive storytelling domain to solutions in formal specification.

  Specifically, we examine narrative from a structural point of view and observe that alternative narrative paths play a complementary role to simultaneous interacting timelines. Linear logic provides the representational tools necessary to investigate this structure, and by extending the correspondence to proofs and proof construction, we find a suite of computational possibilities. We present three efforts toward realizing those possibilities: (1) the use of linear logic programming to generate narratives; (2) a new programming language for authoring interactive narratives, games, and simulations; and (3) techniques for stating and proving design-level program properties.

  We find that linear logic programming, enriched with a minimal extension to its logical semantics, enables a wide range of programming idioms and domain encodings. As evidence, we give five case studies, including social simulation, combat-based adventure games, and board games. To support reasoning about design correctness, we present techniques for stating and proving program invariants, as well as a decidability proof for automatically checking those invariants for a large fragment of the language.

  These findings show that linear logic is a fruitful representation language to serve as the basis for modeling and executing interactive worlds, and they invite future investigations on using proof-theoretic methodologies for creative systems.


How to graph search a LTL-generated Buchi automaton to generate valid execution paths

I would interpret your problem as follows:

Given a non-deterministic Büchi automaton representing some language $L$, you want to enumerate all shortest good prefixes of $L$ such that in every character of the good prefix, only at most one atomic proposition has a $\mathbf{true}$ value.

A good prefix of $L$ is a finite word such that every infinite extension of it is in $L$. I call a good prefix a shortest good prefix if and only if every prefix of the prefix is not a good prefix.
A schedule is typically finite even though LTL and Büchi automaton "talk" about infinite executions. Hence this interpretation of your problem.

Note that this is actually a difficult problem -- take for example two Buchi automata for the languages []<>p and <>[]!p -- you can take their disjunction by merging the state sets and having two initial states. You do not see syntactically that every word is a good prefix.

The best way to enumerate good prefixes would thus be to construct a deterministic automaton over infinite words, such as a deterministic Rabin automaton, and enumerating all paths to a strongly connected component in which every state represents the universal language.

Enumerating the paths can be done by a simple depth first search, where you do not abort the search after you found a path to a state with the universal language. Whenever you found a path to such a component, you print it out, and return to the next recursive step. Along the way, you ignore characters with more than one proposition set.

Now in practice, you may have a good luck using LTL-to-Buchi converters. They typically do not guarantee that they find all simplifications of the LTL formula, but enumerating paths to accepting states may do the trick. Note that for non-deterministic automata, you can get duplicate schedules.
If you use modern tools for LTL-to-deterministic-automaton translation (such as Rabinizer), they should also make sure that states belowing to a strongly connected component for the universal language are self-looping on all characters, which makes them easy to detect. But I don't think they guarantee this.


Then you can compress all $g_j ∈ S_N$, by iterating through $A$ until you find $a_i|f(a_i,g_j)−m>0$.

I'm not sure what the notation means (the pipe here, and also $\#A$ elsewhere), but still: this is not a meaningful algorithm since the set

  $\qquad A = \{a_i : \, \forall \, g_j \in S_N \, f(a_i, g_j) \gt \lceil(\log_2{\#A})\rceil\}$

is empty.

I think you got lost in notation. $S_N$ = $\Sigma^{\leq n}$ and $A$ is the set of all algorithms that compress all strings in $S_N$ by at least some non-zero number of bits. As you cited, there are no such algorithms.

In the updated question, you write:

  $\qquad A =  \{a_i : \, \forall \, g_j \in S_N \, \exists a_i \in A : f(a_i, g_j) \gt \lceil(\log_2{\#A})\rceil\}$

This definition is circular, hence $A$ is not well-defined. Did you mean

$\qquad A = \{ a \mid \exists g \in S_N. f(a, g) > x \}$

with $x > 0$ something that does not depend on $A$?

Now $A$ is infinite (and undecidable as per Rice's theorem) and, arguably, completely useless: any string s can be compressed well by the trivial algorithm

compress_s(x) {
    if x == s
        return "0"
    else
        return "0" + x
    end
}

Note that this version of $A$ contains all these bogus algorithms. So, you have thrown all information while compressing, instead encoding the string in the algorithm's source code (mathematically and literally).

And, as others note, the resulting algorithm would still be subject to the pidgeon-hole principle.

  Is there a reason why the above is not done?

Even if it were possible, it'd be horribly inefficient. In essence, the idea of your algorithm is:

  Try all (compression) algorithms (I know); pick the smallest result and encode the result together with its code.

That's clearly neither a clever nor a useful algorithmic idea.


Yes, the processor itself runs the BIOS boot program. Each motherboard has to be equipped with appropriate BIOS that a processor of compatible chip set can use.


Classes of Functions Closed Under Polynomial Composition - Papadimitriou Exercise 7.4.4

For item (d):

Closed under left polynomial composition: Consider an arbitrary $f(n) = 2^{n^{k_1}} \in C$ and an arbitrary polynomial $p(n)$. There exists some $k_2$ such that $p(n) \leq n^{k_2}$, for sufficiently large $n$. For sufficiently large $n$, $p(f(n)) \leq [f(n)]^{k_2} = [2^{n^{k_1}}]^{k_2} = 2^{k_2 n^{k_1}}$. There exists $k_3$ such that $2^{k_2 n^{k_1}} < 2^{n^{k_3}}$ for sufficiently large $n$. Therefore, choosing $g(n) = 2^{n^{k_3}} \in C$ we have $p(f(n)) = O(g(n))$.
Closed under right polynomial composition: Consider an arbitrary $f(n) = 2^{n^{k_1}} \in C$ and an arbitrary polynomial $p(n)$. There exists some $k_2$ such that $p(n) \leq n^{k_2}$, for sufficiently large $n$. For sufficiently large $n$, $f(p(n)) = 2^{[p(n)]^{k_1}} \leq 2^{(n^{k_2})^{k_1}} = 2^{(n^{k_2 k_1})}$. Therefore, taking $g(n) = 2^{(n^{k_2 k_1})} \in C$ we obtain that $f(p(n)) = O(g(n))$.

For item (e):

Closed under left polynomial composition: Consider an arbitrary $f(n) = \log^{k_1} n$ and an arbitrary polynomial $p(n)$. Then, exists some $k_2$ such that $p(n) \leq n^{k_2}$, for sufficiently large $n$. Therefore, for sufficiently large $n$, $p(f(n)) \leq f(n)^{k_2} = (\log^{k_1} n)^{k_2} = \log^{k_1 k_2} n$. Choosing $g(n) = \log^{k_1 k_2} n$ we have $p(f(n)) = O(g(n))$.
Closed under right polynomial composition: Consider an arbitrary $f(n) = \log^{k_1} n$ and an arbitrary polynomial $p(n)$. Then, exists some $k_2$ such that $p(n) \leq n^{k_2}$, for sufficiently large $n$. Take $g(n) = \log^{k_1} n$. We have, for sufficiently large $n$:
$ f(p(n)) = \log^{k_1} p(n) \leq \log^{k_1} (n^{k_2}) =
 (k_2 \log n)^{k_1} = {k_2}^{k_1} \log n^{k_1} = O(\log n^{k_1}) = O(g(n))$.


How to find upper and lower bound without using formula

Another approach:

$n^2/4=(n/2)^2= \underbrace{n/2 + n/2 +\cdots + n/2}_{n/2 \text{ times}} \le 1+2+\cdots + n \le \underbrace{n + n +\cdots + n}_{n \text{ times}} = n^2 $
$n^2= \underbrace{n + n +\cdots + n}_{n \text{ times}} \le n+(n+1)+\cdots + 2n \le \underbrace{2n + 2n +\cdots + 2n}_{n \text{ times}} = 2n^2 $


Printing values of psuedo random numbers in a range

While this looks like a programming question, the real misunderstanding is in how to use pseudorandom number generators.

A pseudorandom number generator is initialized using a seed (we later expand on that). Once initialized, it can be called to output a (seemingly) infinite sequence of random bits or integers (the sequence will be periodic, but the period can be huge). The interface of a pseudorandom number generator thus consists of two functions:

Initialize with a seed – in your case, srand.
Output the next number in the sequence – in your case, rand.

For some reason, you are initializing the seed each time you want a random number. While this is not necessarily wrong (though in your case it is!), it ignores a fundamental feature of most pseudorandom number generators: initializing is slow, and generation is fast. We can effort initialization to be slow since it is only called once, whereas you could be generating many numbers. This is why it is not recommended to initialize your generator for each generated number.

What goes wrong with your code? The problem is that time returns a value which only changes once a second. Since your program executes in much less than a second, it is highly likely that each time you initialize your generator, you will initialize it using the very same value. Therefore you are getting the same number each time – this is by design.

Finally, a few words on how to initialize your generator. One option is to choose a seed at random once and for all. This guarantees that your results are reproducible – each time you run the program, it will be using the same pseudorandom sequence. Another popular option is to use the current time, as you're doing (though it's better to use something with higher resolution than seconds). A third option is to use some "entropy reservoir", such as the Unix /dev/random, which is supposed to pick up entropy from key presses, mouse moves, and so on. A fourth option would be to use thermal noise – that requires specialized hardware.


Implementing the GSAT algorithm - How to select which literal to flip?

Isn't the maximum number of satisfied clauses what we're looking for?

Yes, we're looking for an assignment that satisfies the maximum number of clauses (that is all of them, preferably). And to that end we ask ourselves "Which single variable will bring us closest to this goal when flipping it?" and then flip it.

  It seems to me that we're trying to use the solution or approximations to it to find the solution.

Using the solution would be if we asked "Which combination of multiple flips would give the best result?" or simply "Which assignment would be the best?". However that's not what we're doing, we're only looking one step ahead. Using an approximation of the solution seems like an accurate description. However there's nothing wrong with that. That's how greedy strategies work.

  Generate a state space with all possible flips and search the space for a literal that results in the best approximation to the goal state.

Right.


Condition for infinitude of the language of a finite state automaton

The additional condition allows you write a straight-forward algorithm -- check all strings with lengths in this interval -- for deciding (in)finiteness of the accepted language. Thus, you get a proof that this property is decidable (which it isn't for most automata models with super-regular power).


Model disjunction in a $\{0,1\}$ integer linear program

Let's assume that all variables are Boolean (constrained to $\{0,1\}$). Here is how to encode the constraint "$x+y=1$ or $z=1$". Presumably you can extend this.

$$
\begin{align*}
&x+y+u-v = 1 \\
&z+w = 1 \\
&w+u+v \leq 1
\end{align*}
$$

If $x+y = 1$ then we take $u=v=0$ and $w=1-z$.

If $z = 1$ and $x+y = 0$ then we take $u=1$, $v=0$ and $w=0$.

If $z = 1$ and $x+y = 2$ then we take $u=0$, $v=1$ and $w=0$.

This shows that these equations are solvable when $x+y=1$ and when $z=1$.

Conversely, suppose that these equations are solvable, and so at most one of $w,u,v$ is non-zero. If $w = 0$ then $z = 1$. Otherwise, $u=v=0$ and so $x+y = 1$.