why is H = {www | w ∊ (0,1)* } not regular language

You can use the Myhill–Nerode criterion. Consider the words $0^n1$ for all $n$. These are pairwise inequivalent since $0^n10^n10^n1 \in H$ while $0^m10^n10^n1 \notin H$ if $m \neq n$. Since we have found infinitely many pairwise inequivalent words, it follows that the language is not regular.

As mentioned in the comments, you can probably also use the pumping lemma, but it might take more work.


The problem is that the code is ambiguous. You can interpret it either as

If C1 then
   If C2 then
     S1
   else
     S2

or as

If C1 then
   If C2 then
     S1
else
   S2

The compiler needs to choose one way and covert it into machine language. The solution of "choose the last if" means the compiler will choose solution number 1 -- will attribute the "else" to the last (open, non-matched) "if" statement.


per-record timeline consistency vs. monotonic writes

I'm not sure these two concepts are really comparable.

monotonic writes is a client based consistency model. It defines what a process sees.

per-record timeline consistency strikes me as a memory based model. It doesn't even mention what a client sees or does.

So I would say they are not same or even comparable.


How to sample Bivariate Normal Distribution with Accept reject method

I came up with this answer which can approximately sample a bivariate normal distribution with accept reject method and I thought it might be useful for others in future.
we choose a 2D uniform distribution called $F_{X,Y}(x,y) = F_X(x).F_Y(y)$ where both $X$ and $Y$ are uniform distributions in range of $(0, +a)$ and they are independent of each other.
We choose a constant $C$. Both $C$ and $a$ are chosen based on our bivariate normal distribution so that:

for all $x, y$ we have $C.F_{X,Y}(x,y) \geq BN(x,y)$, Where $BN$ is our bivariate normal distribution.
$x, y \in (-a, +a)$ supports most of our $BN$ density.

The Accept Reject Method:

Now we sample from our $F_{X,Y}(x,y)$. Suppose it's $X1 = (x1, y1)$.

We uniformly choose from:
$$X_{1.1} = (x1, y1),$$
$$X_{1.2}=(-x1, y1), $$
$$X_{1.3}=(x1, -y1), $$
$$X_{1.4} = (-x1, -y1)$$
and name that $\hat{X_1}$ so that we consider all four quadrants of $xOy$.

Now we accept $\hat{X_1}$ as a sample of $BN$ with a probability of $p=BN(x1,y1)/C.f_{X,Y}(x,y)$.

We come back to step 1 and do this cycle to collect as much sample from the bivariate normal distribution as we want.


How to prove these two distributions are statistically/computationally indistinguishable

I think your problem is in trying to insist that $k$ is fixed.  That's getting you tied up in knots.

The statement "for fixed $k$, define $D_A$ to be the distribution..." makes no sense to me, because as you have previously defined $k$, $k$ isn't fixed -- $k$ is defined to be a random variable (that is uniformly distributed on $\{0,1\}^n$).  So, it looks to me like you are contradicting yourself.

Instead, let me suggest a better way to think about indistinguishability. Think about indistinguishability as a random experiment.  There is a formal definition of indistinguishability.  In that definition, we define an experiment.  The experiment works by running some algorithms that we have fully specified, and then observing the result.  As part of this you will need to fully specify the probability space and the event you care about.  For instance, if $F,G$ are two algorithms that depend only on a key $k$, then we might define them to be computationally indistinguishable if there does not exist a polynomial-time algorithm $A$ such that

$$|\Pr[k \leftarrow \{0,1\}^n ; A(F(k)) = 1] - \Pr[k \leftarrow \{0,1\}^n ; A(G(k)) = 1]|$$

is non-negligible.  That's a standard definition of computational indistinguishability.  Notice that the event $k \leftarrow \{0,1\}^n ; A(F(k)) = 1$ (and corresponding probability space) is fully defined, by defining some algorithms and then asking about the probability that it outputs 1.  Everything can be expressed as a statement about some random variable, where the random variable is defined by executing a well-specified algorithm (i.e., in pseudocode).  There is no step halfway along that says "fix $k$" (it's not even clear to me what that would mean).

The idea here is that we want to make a statement about the probability of some event.  That event is defined in terms of running a randomized algorithm and checking its output.  This is a well-defined and precise way to define an event in some probability space.  Once you start trying to add "fix $k$" in the middle of that, we lose that property and it's not clear what you mean.

So, stick with the standard definitions, and try to apply them as is.  Don't try to create your own definition.  Or, if you insist on it, first translate your idea to a statement about a probability of some event where the event is defined in terms of a well-specified randomized algorithm.  You should be able to write pseudocode for each step of your algorithm, without needing English (like "fix $k$").  If you try to do that for your idea, probably you'll find that at one step along the way your pseudocode assigns to $k$ (say, by picking a random value from $\{0,1\}^n$), and then $k$ is whatever it is (if it is picked randomly, then it's not fixed; it's a random variable).

For example, here is one fact that is true.  If we define $X$ by $k \leftarrow \{0,1\}^n; X \leftarrow k$ and $Y$ by $k \leftarrow \{0,1\}^n; Y \leftarrow \{0,1\}^n$, then $X,Y$ are computationally indistinguishable and statistically indistinguishable (just apply the definition and see what you get).  Same if you define algorithms $A,B$ as in your question and define $X$ by $k \leftarrow \{0,1\}^n; X \leftarrow A_k()$ and $Y$ by  $k \leftarrow \{0,1\}^n; X \leftarrow B_k()$.

However, if you give the adversary knowledge of $k$, they are no longer distinguishable.  Thus, for instance,

$$|\Pr[k \leftarrow \{0,1\}^n ; \mathcal{A}(A_k()) = 1] - \Pr[k \leftarrow \{0,1\}^n ; \mathcal{A}(B_k()) = 1]|$$

is negligible for all adversaries $\mathcal{A}$, but

$$|\Pr[k \leftarrow \{0,1\}^n ; \mathcal{A}(k,A_k()) = 1] - \Pr[k \leftarrow \{0,1\}^n ; \mathcal{A}(k,B_k()) = 1]|$$

is not.

As an aside, often we use $A$ to represent the adversary/attacker, so using $A$ to represent some other algorithm can potentialy get a little confusing.


Context free grammar to Chomsky's normal form

Every context-free grammar can be converted to Chomsky normal form. Also, note that grammars are by definition finite: a grammar might describe infinitely many strings, but the grammar itself is finite.


Find number of nodes that seperate graph to two or more subgrahps when removed individually - Find articulation points on a non-directed graph

After some searching, I came across exactly what I wanted - seems like knowledge of terms is important. Source from Wikipedia - Biconnected components.

  Linear time depth first search

  The classic sequential algorithm for computing biconnected components in a connected undirected graph is due to John Hopcroft and Robert Tarjan (1973).[1] It runs in linear time, and is based on depth-first search. This algorithm is also outlined as Problem 22-2 of Introduction to Algorithms (both 2nd and 3rd editions).

  The idea is to run a depth-first search while maintaining the following information:

  the depth of each vertex in the depth-first-search tree (once it gets visited), and
      for each vertex v, the lowest depth of neighbors of all descendants of v in the depth-first-search tree, called the lowpoint.

  The depth is standard to maintain during a depth-first search. The lowpoint of v can be computed after visiting all descendants of v (i.e., just before v gets popped off the depth-first-search stack) as the minimum of the depth of v, the depth of all neighbors of v (other than the parent of v in the depth-first-search tree) and the lowpoint of all children of v in the depth-first-search tree.

  The key fact is that a nonroot vertex v is a cut vertex (or articulation point) separating two biconnected components if and only if there is a child y of v such that lowpoint(y) ≥ depth(v). This property can be tested once the depth-first search returned from every child of v (i.e., just before v gets popped off the depth-first-search stack), and if true, v separates the graph into different biconnected components. This can be represented by computing one biconnected component out of every such y (a component which contains y will contain the subtree of y, plus v), and then erasing the subtree of y from the tree.

  The root vertex must be handled separately: it is a cut vertex if and only if it has at least two INDEPENDENT (non-connectible) children. However, since we hold the child count of each visited node, and the count only increments if the adjacent node being checked is not already visited, the root having >=2 children count would surely mean that at least two of the root's children are independent. If there were no 2 independent children of the root, all of the children of the root apart from the first checked would be marked as visited BEFORE the DFS search returned to root and continued the search to the second child, therefore the root's children count would be stuck at 1.

The code below prints the said articulation points, but with minimal changes it can also just print out the count of the said points.

Pseudocode

GetArticulationPoints(i, d)
      visited[i] = true
      depth[i] = d
      low[i] = d
      childCount = 0
      isArticulation = false
      for each ni in adj[i]
          if not visited[ni]
              parent[ni] = i
              GetArticulationPoints(ni, d + 1)
              childCount = childCount + 1
              if low[ni] >= depth[i]
                  isArticulation = true
              low[i] = Min(low[i], low[ni])
          else if ni <> parent[i]
              low[i] = Min(low[i], depth[ni])
      if (parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1)
          Output i as articulation point


A greedy approximation algorithm for max k-cut

The natural greedy approach goes roughly like this:

  Go over the vertices one by one. For each one, allocate it to a part in a way maximizing the total cost of edges cut.

There are at least two natural ways of defining total cost of edges cut:

Total cost of edges between the vertex and vertices already allocated to different partitions.
Same as 1, together with the expected cost of cut edges to vertices not already allocated.

In this case both ways are the same, but the second shows the connection between the greedy algorithm and the trivial randomized algorithm, which allocates the vertices completely randomly.


Proving that the clique cover problem is in NPC by reducing from k-coloring

In the interests of putting up an explicit answer, your approach is correct. The proof is sketched on the Wikipedia page for Clique Cover.

The reduction itself is fairly straightforward. The reasoning is that if a graph is $k$-colourable, then it can be partitioned into $k$ independent sets (one for each colour class), then we just exploit the normal reduction between Independent Set and Clique by taking the complement graph (we swap edges for non-edges and vice versa), so any independent set becomes a clique. So if $G$ is $k$-colourable, it can be partitioned into $k$ independent sets and hence $\overline{G}$ can be partitioned into (i.e. covered by) $k$ cliques (but not necessarily by $k$-cliques ;) ). Conversely if $\overline{G}$ can be covered by $k$ cliques, $G$ has a partition into $k$ independent sets, and hence is $k$-colourable.


How many operations to produce this superposition of 3 qubits?

You don't need a full 8x8 three-qubit operation, but you will need a two-qubit operation of some kind. If you only rotate each qubit independently, you'll find you can only make un-entangled states like:

$(a_1 \left| 0 \right\rangle + b_1 \left| 1 \right\rangle) \otimes (a_2 \left| 0 \right\rangle + b_2 \left| 1 \right\rangle) \otimes (a_3 \left| 0 \right\rangle + b_3 \left| 1 \right\rangle)$

$= a_1 a_2 a_3 |000\rangle + a_1 a_2 b_3 |001\rangle + a_1 b_2 a_3 |010\rangle + a_1 b_2 b_3 |011\rangle + b_1 a_2 a_3 |100\rangle + b_1 a_2 b_3 |101\rangle + b_1 b_2 a_3 |110\rangle + b_1 b_2 b_3 |111\rangle$

But as soon as you have a non-trivial two-qubit operation, like a controlled-NOT, to go with your single qubit gates, you can approximate any larger operation or state arbitrarily well. (This is different from classical reversible computing, where you need a doubly-controlled-not before you get universality.)

The basic idea of how it's done is:

Break a large operation into lots of single-qubit operations, but allowing each to have lots of controls.
Use the fact that all single-qubit operations have a square root to knock controls off of multi-controlled operations until you're left with singly-controlled operations.
Replace controlled-whatevers with controlled-NOTs by finding $A$, $B$, $C$, $\theta$ such that $ABC = I$ but $AXBXC e^{i \theta} = U$ for each single-qubit operation $U$.

The details of these kinds of constructions are covered in textbooks.


For first question: No, it doesn't make sense. If there is no ratio between OPT(ILP) and OPT(LP-relax) (i.e. integrality gap is 1) which is very rarely to happen (only happen with problem that is in $P$), then this means that you reach the optimal solution for this problem. It is known that LP-relax cannot give the optimal solution for a problem (except for problems in P as I said), and this is why we define integrality gap to see how far it from the optimal solution of the problem (or optimal solution of the ILP).

For second question: Yes, it is true, $\alpha = 1$.

For third question: if you design an approximation algorithm for a given a problem, then I believe you are talking about problem that lies in NP-hard. Then the best factor you hope for max/min problem is 1 (Note that max problem has ratios between [0-1], whereas min problem has ratios between [1,$\infty$)). In reality, all NP-hard problems cannot get a polynomial approximation algorithm with ratio 1 unless P=NP "since ratio 1-approximation algorithm is the same as exact algorithm". So, it should be closer to 1 for both max/min problems but not equal 1.


Predicting energy consumption of households

I am not an expert in machine learning, but here is one problem: most of your data is binary. Since you have many such paramters, very little can be derived in terms of correlation between any given parameter and the target quantity. Therefore, statistic methods will have a hard time.

Furthermore, you have a small data set but many parameters. Get rid of some.

Another problem can be that you have mutually exclusive data: for example, the first three parameters (URBAN, RURAL and MOUNTAINOUS) can not be set at the same time. You might want to combine them into one category parameter; thus, the algorithms don't have to find a multi-dimensional anti-correlation and correlate the vector to energy consumption, but use that one parameter directly. Note how this also reduces the number of parameters.
If you can make assumptions about which areas inherently cause more energy consumption, consider turning the parameter into an appropriate interval (of reals).

As a general rule, machine learning is what you do if other methods don't work. In this case, I don't see the need for machine learning unless you show that reasonable other approaches fail.

For instance: Research energy consumption of the appliances you have parameters for and assume average values resp. values fitting the total area covered. Research and/or make reasonable assumptions for the number of light bulbs, air conditioning, etc based on total area. If this does not already solve your problem, it should reduce the number of parameters with unknown influence.


What's wrong with this substitution for master's method

The key thing to note is that you are replacing $T(n)$ function with an exponential $S(n)=2^n$. The variables do not change just the functions. So, $n^2$ stays.


Since $(a+b)^2 = a^2 + 2ab + b^2 \geq 2ab$, it is indeed true that $|V||E|$ is bounded by a polynomial in $|V|+|E|$.


You say  "using a structure similar to an adjacency list". So space complexity required for storing undirected graph using adjacency list is $O(|V| + |E|)$, in your case $O(|V| + 2|E|)$. That is implemented using a list of nodes where each node has two fields: label of the vertex and pointer to the list of adjacent nodes (in your case two lists).

But I don't know how you are going to use the graph. If you are interested in simply a set of edges then you could store them in a list as triples $<u,v,weight>$. But if at some point for a node $v$ you want to systematically loop on all adjacent vertices (inward or outward) then you should use adjacency list.

Finally if you want to decide in $O(1)$ if there is an edge $<u,v>$ then you should use hash like data structure to store pairs $<u,v>$.


Is it possible to implement dependent types by any object oriented language supporting inheritance and classes?

So, things like this are possible, but the usefulness varies depending on your system.

First, you can absolutely model object oriented programming in a functional, formal setting. System F-sub is the classic example of this, but Scala Dependent Object Types are another model.

Secondly, let's talk about the difference between types and classes, without dependent types. A class is essentially just a type, combined with a bunch of methods that operate on that type. Classes can be modeled with recursive record types in some languages. The algebraic data types you see in languages like Haskell and Agda are kind of like regrouped classes. An interface groups functions together, and the type specific implementation of those functions for specific classes are spread out. Conversely, algebraic data types group all the variants of a type together, but the different functions are spread out, with each function specifying how it is implemented for each type.

Finally, how do dependent types play into all this? Well, Agda and other Dependent Type languages have a particular feature, namely that types can be indexed by values, and that types are themselves values. Computation can happen not just in expressions, but in types.

Java, Haskell, and every other mainstream language are weaker than this, since their types can't be indexed by arbitrary values. This is what the dependent in dependent types means, and it's what makes them useful for proving things.

To have dependent object oriented types, you need to overcome a few hurdles. One is, do you have mutation, and how does it affect dependent types? Can types refer to mutable variables, or alter state? How is that possible, when type computation happens at compile time, not runtime?

And then you need to decide whether you want to prove actual theorems in your language. Most OO languages are Turing Complete, meaning that the would be inconsistent if interpreted as a logic. This doesn't mean that Dependent types are useless, you can still enforce sophisticated program invariants using them. But Agda and the others feature termination checkers that make them Turing Incomplete.


Analysis of komi values for increasing Go board sizes and agents strength

From my experience of solving some other games, usually there is a huge difference between optimal player and an average player or even state-of-the-art engine. I bet the results for any other player then optimal will diverge from the results of optimal play. For example see what happened with some famous chess positions when endgame tables where developed (see Tablebases, Fermat, Knights and Knightmares - you might need access to ICGA Journal). Optimal solutions frequently destroy any intuition about a game. I expect that even AlphaGo Zero approach would be not enough even for small boards like 7x7 to approximate the optimal komi value.


If well-founded induction holds, then the relation $\to$ on a reduction system terminates

Well-founded induction, like all other forms of induction, holds for any predicate $P$. That can mean two different things:

Well-founded induction holds for every predicate which you can express in your formal system.
Well-founded induction holds for every subset $P \subseteq A$.

Either way, informally speaking you can define $P$ to be whatever you want.

Formally speaking, you might run into set-theoretic issues, those that separate naive (or elementary) set theory from axiomatic set theory. But presumably this is not the focus of the book, so you can just ignore such issues.

(The gap is that in case 1, you need to show how to express $P$, and in case 2, you need to show that the set $\{x \in A : \text{there exists no infinite chain starting at $x$}\}$ exists.)


Regular expression for words over $\{0,1\}$ containing at least one 1

Your answer is correct. $0^*1$ matches the portion up to the first $1$. After that, any subsequent $1$s may have any number of $0$s between them.

There are slightly simpler regular expressions for the same language. For example,

$$0^*10^*(0^*10^*)^* \ \equiv\  0^*10^*0^*(10^*)^*\ \equiv\ 0^*10^*(10^*)^*\,.$$

You could also observe that a string with at least one $1$ is formed of some number of initial $0$s, followed by the first $1$, followed by anything else, leading to $0^*1(0+1)^*\!$, which is arguably slightly simpler than the teacher's solution.

However, you should consider that you probably lost marks for reasons other than the teacher mistakenly thinking that you were wrong. I wouldn't allocate five marks just for writing down a simple regular expression. To me, that would be either a one-mark question (one mark for right, none for wrong) or a two-mark question (two marks for right, one for being close and maybe missing a corner case, none for wrong). For five marks, I'd expect an explanation of why the regular expression does what it's supposed to do.


How to solve the optimization of bin packing using the decision version

If you could solve the decision problem (do these items fit in k bins) you can obviously solve the optimisation problem (what is the minimum number of bins) using binary search. But you actually want to know what to put into each box. That’s easily done doing the decision problem at most n^2 times.

Let’s say you know k boxes are required and sufficient. Sort the item by descending size. Replace the biggest and second biggest item with one item of their combined size and check if the new items fit into k bins. If not, try the largest and third largest item, and so on. After n attempts, you either know two items that are in the same bin in an optimal solution, or you know the largest item is on its own. And you repeat that, each time you find that you can put two items in the same bin by solving at most n decision problems.


Using de Morgan's laws, we get a more useful characterization of self-dual functions: those are functions satisfying $\lnot F(x_1,\ldots,x_n) = F(\lnot x_1,\ldots,\lnot x_n)$. Suppose that you knew the value of a self-dual function on all inputs in which $x_1$ is false. Can you recover the rest of $F$? Can you deduce the number of self-dual functions?


Non-existence of approximation algorithm for the knapsack problem

Given an instance of knapsack, multiply all values by $k+1$. Any solution satisfyign $OPT(I) - P_A(I) \leq k$ is in fact optimal, so you could use such an algorithm to solve knapsack.


Difference between stable marriage problem and assignment problem

The main difference is the optimization goal.

In classical assignement problem, there is a fitness/cost function to maximize/minimize. Each assignement possibility has a weight and you only sum up all these weights to get the best global result. Only the overall result matters even if it means some individual assignements have a very bad fitness/cost.

In the stable marriage problem, it is the opposite. You do not care about the overall optimality. You just want to guarantee that it does not exist a "male" and a "female" that would both be "happier" together rather than with their assigned partner.

The idea behind the word "stable" is that if such a couple exists, they will tend to get together breaking your initial assignement.

An exemple:
two "males" A and B and two "females" C and D

A loves hardly C (weight 10) and not D (weight 1)
B loves a little more C (weight 3) than D (weight 2)
C loves a little more B (weight 3) than A (weight 2)
D loves hardly B (weight 10) and not A (weight 1)

In assignement problem, you clearly put A&C and B&D to get a fitness score of 24. But this is not a stable marriage as B and C would rather like to be together. A&D and B&C is a stable marriage but only has a fitness score of 8.


Are regular languages closed under sort (Parikh image)?

No. Counterexample: assuming $a < b$, we have $(ab)^\ast \xrightarrow{\;\;\text{sorted}\;\;} \{ a^n b^n \;|\; n \geqslant 0 \}$, which cannot be expressed by a regular expression, by the pumping lemma for regular languages.


Can the height of a binary search tree be less than that of a red-black tree?

The fact that a red-black tree is balanced just means that if it contains $n$ nodes then its depth is $O(\log n)$. There is no requirement for the depth to be optimal (i.e. $\lceil \log_2 (n+1) \rceil-1$), only for it to be optimal up to constants. Therefore it is definitely possible for a red-black tree to be deeper than some other binary search tree.

The advantage of balanced trees is that they are guaranteed to be balanced even after operations on the data structure. Since the running time of operations is usually linear in the depth, it is enough for the depth to be $O(\log n)$ rather than the optimal $\approx \log_2 n$.


How do nondeterministic Turing machines compute general function problems?

One accepted definition is as follows: a function $f$ (whose output is at most polynomial in its input) is in the class $\mathsf{FNP}$ if given $x,y$ one can decide in polynomial time whether $f(x)=y$. Compare this to the class $\mathsf{FP}$, which contains those functions $f$ such that given $x$, the value of $f(x)$ can be computed in polynomial time.


What do time complexity reductions prove?

$A \leq_p B$ denotes that you can reduce $A$ to $B$ in polynomial time. That is, you can always transform an instance of $A$ to an instance of $B$ and you do this in polynomial time. Now if you have a polynomial time algorithm for solving an instance of $B$, you also have a polynomial time algorithm for solving an instance of $A$, clearly.

To show that $C$ is $\mathsf{NP}$-complete, you need two conditions to hold. First, $C$ must be in $\mathsf{NP}$. Second, every problem in $\mathsf{NP}$ is reducible to $C$ in polynomial time.


I'm not sure what metrics have to do with it: convexity is about barycentric coordinates rather than distance.

The surface of the sphere is nasty because of antipodes. Roughly speaking, if there is an open hemisphere which contains all of the input points, you can work in that hemisphere without problems. Otherwise, the convex hull is going to be the entire surface.

Supposing that there is an open hemisphere containing the points, essentially any 3D convex hull algorithm will work by the addition of an extra point at infinity. But it's probably more elegant to take the centroid in $\mathbb{R}^3$, project to the surface, and use it as a centre around which to apply your favourite wrapping algorithm.


Properties of roots of recurrence relations in the context of exponential algorithms in order to decrease the upper bound of the running time

Let's start with your first question. You are considering two polynomials,
$$
P(x) = x^n - a_r x^{n-t_r} - a_{r-1} x^{n-t_{r-1}} - \cdots - a_1 x^{n-t_1}, \\
Q(x) = x^n - a_r x^{n-t_r} - \cdots - b_i x^{n-t_i} - \cdots - a_1 x^{n-t_1},
$$
where all $a_i$ are positive, and $0 < b_i < a_i$. Thus $Q$ results from replacing the term $-a_i x^{n-t_i}$ with $-b_i x^{n-t_i}$.

Let $\tau$ be the largest real root of $Q(x)$; note that $\tau > 0$. Thus
$$ P(\tau) = Q(\tau) + (b_i - a_i) \tau^{n-t_i} < 0. $$
On the other hand, $\lim_{x\to\infty} P(x) = \infty$. Therefore $P$ must have another root beyond $\tau$.

You can try attacking your second question using similar reasoning.


What is the language generated by a given grammar

The language of this grammar is all strings of the form $wb^n$  where $w\in \{a,b\}^*$, and $|w| = n+1$. If I abuse the notation a bit, it is $\Sigma^{n+1}b^n$.

If perchance you mean $S \rightarrow aSa \ | \ bSb \ | \ a\ | \ b$, then the language contains all palindromic strings of odd length.


Canonical representation of finite maps on non-overlapping finite rational intervals

It's possible to build a data structure that in practice has $O(\lg n)$ lookup, $O(\lg n)$ insertion, and $O(1)$ equality-tests.  I'll describe how below.  (If you care about theoretical worst-case complexity, there are some caveats, but those caveats can probably be ignored for practical implementation.)

You can handle the lookup, insertion, and creation operations using a balanced binary search tree on the endpoints of the intervals.  If you have $n$ intervals, you'll have at most $2n$ endpoints, so you have a balanced tree on $O(n)$ leaves.  Lookup and insertion can be done in $O(\lg n)$ time, using an appropriate balanced tree data structure, which is efficient.

Ensuring it has a canonical representation is difficult; I don't know how to do that, while ensuring efficiency.  The standard data structures don't have a canonical representation: there are many possibilities for the structure of the tree, for any given contents, and they use these degrees of freedom to help make the operations efficient.

But we can still support the "equality-test" operation efficient, without needing a canonical representation.  We'll construct a custom hash function, which produces a hash value $H(f)$ based on the contents of the map $f$ (regardless of the underlying structure of the tree or how the map is stored).  Then we can do efficient equality tests: given two maps, we compare their hashes.  If their hashes are different, we know they are different maps.  If their hashes are the same, we can compare them exhaustively; with a reasonable hash function, the chances of two different maps yielding the same hash will have negligible probability.  If you use a cryptographic-strength hash, that possibility is so exponentially rare that you can use a simpler procedure: if the hashes match, then the maps match, and there's no need to check any further.  This yields a procedure that is $O(1)$ time to compare equality in practice.

So how do we build the hash function $H$?  We'll use an associative hash function.  Let $(G,+)$ be an abelian group, and a conventional hash function $h:\{0,1\}^* \to G$.  Suppose the map $f$ maps the interval $[\ell_i,u_i]$ to the value $v_i$ for $i=1,2,\dots,n$.  Then we'll define the hash of $f$ to be

$$H(f) = \sum_{i=1}^n h(\ell_i,u_i,v_i).$$

Notice that the hash value depends only on the map itself, and not on the structure of the tree used to store the map.

We'll update the hash of the map each time that we update the data structure.  This is easy to do, thanks to the structure of $f$ and the fact that $+$ is commutative (since $G$ is abelian).  If the map $f'$ is defined by removing an interval $[\ell,u] \mapsto v$ from the map $f$, then their hashes are related by

$$H(f') = H(f) - h(\ell,u,v),$$

which can be computed in $O(1)$ time.  Similarly for adding an interval that doesn't overlap any other intervals.  Adding an interval that overlaps an existing interval (triggering a split) can be done by deleting the existing intervals and adding in the new intervals.  Each of these operations takes $O(1)$ time.

(Alternatively, you can choose a non-abelian group $G$ and then augment the binary tree: in each node, you store the hash of the map that corresponds to the subtree rooted at that node.  In this way you can update the hash values for all nodes each time you update the tree.)

It remains to instantiate the hash $H$ by choosing an appropriate group $G$ and an appropriate hash $h$.  I suggest that you use a cryptographic hash function for $h$, such as SHA256; that way  you can treat collisions as effectively impossible in practice.  You can find analysis of how to choose the group $G$ in the cryptographic literature: see https://crypto.stackexchange.com/q/11420/351, https://crypto.stackexchange.com/a/17936/351, and https://crypto.stackexchange.com/q/8615/351.


What exactly is Symbolic Model Checking?

Symbolic model checking can be very useful for verifying the correctness of communications and security protocols. For example:

A symbolic model of an OAUTH2 implementation could help check for unintended consequences where an adversary obtains secret authentication tokens or related circumstantial data that could help them contravene the process.
A symbolic model of a cryptographic protocol, such as a TLS handshake, could help verify that the cryptographic design doesn't have any unintended consequences.

This works by writing a symbolic description of all the primitive functions and protocol algorithms, and then having a symbolic model checker, such as ProVerif, traverse the state space and attempt to detect state combinations that produce unfavorable results. In the case of ProVerif, symbolic models are described using the applied Pi calculus as the modeling language. This allows the description of protocols in a functional, ML-like syntax.


In addition to being in agreement with Derek (that the ana/cata terminology doesn't bring much to the table) I'll note that the "category theoretic" terminology for the general map function of type
$$\mathrm{map}:\forall \alpha\beta. (\alpha \rightarrow\beta)\rightarrow(F\ \alpha\rightarrow F\beta) $$
for a functor $F$ is simply "the functorial action of $F$", and is often written as $F$! For example, on lists, map f l would be written $\mathrm{List}(f)(l)$.

For some reason, computer scientists seem to prefer to have a seperate name for the type constructor and the action on morphisms, but mathematicians do not really consider non-functorial constructors anyways.


Sphere, triangle, and other primitive shape intersection

A sphere centered at the origin with a radius $1$ consists of all points whose distance from the origin is at most $1$. The distance between two points $(x_1,y_1,z_1),(x_2,y_2,z_2)$ is $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$. This gives you enough information to describe the sphere: $\{ (x,y,z) : x^2+y^2+z^2 \leq 1 \}$.

A triangle with vertices $p_1,p_2,p_3$ is (by definition) the convex hull of $p_1,p_2,p_3$, which is the set of all points $a_1 p_1 + a_2 p_2 + a_3 p_3$ for $a_1,a_2,a_3 \geq 0$ satisfying $a_1 + a_2 + a_3 \leq 1$. In our case, the triangle is defined by $\{ (x,y,z) : x+y+z = 1, \; x,y,z \geq 0 \}$.

The intersection of a shape $S$ and the ray $r$ is just the set of points which belong to both $S$ and $r$. You can find these points by solving a system of equations: every point $(x,y,z)$ on the ray is of the form $x = 1-t,y = 1-t, z=1-t$ for some $t$. You can simplify this by making the substitution $s = 1-t$ to get $(s,s,s)$ instead of $(1-t,1-t,1-t)$. Now you can find the set of points in the intersection by solving a system of inequalities (I'll leave that to you). Having found the solution, the ray parameter is just the corresponding value of $t$, namely $t = 1-s$.

That should be enough to get you started.


Maximise the value of the minimum weight intra edge

Let $G=\left(V, E=\binom{V}{2}\right)$ be your input graph, let $n=|V|$, and call $w(u,v)$ the weight of edge $(u,v) \in E$. Let $x^* = \max_{A, B} \min_{ (u,v) \in A^2 \cup B^2} w(u,v)$ be the value of an optimal solution to your problem (here $A \cup B = V$ and $A \cap B = \emptyset$).
Suppose that you have a guess $x$ on the value of $x^*$ and let $D_x$ be the set of all edges of weight smaller than $x$. Consider the graph $G'=(V, D)$.
If $G'$ is bipartite, then the two sides of a bipartition will give you a partition of $V$ such that every intra-edge has weight at least $x$. This shows that $x \le x^*$.
If $G_x$ is not bipartite then, for every partition $A,B$ of $V$, you have $D_x \setminus (A \times B) \neq \emptyset$. Since the same must hold for every $x' \ge x$ (since $D_{x'} \supseteq D_x$) this shows that no partition of $G$ can have a measure of at least $x$. I.e., $x > x^*$.
You can then sort the set  $W=\{w(u,v) \mid (u,v) \in E\}$ of all edge weights and
binary search for the value of $x^* \in W$.
The binary search will require at most $O(\log n)$ iterations, and each iteration requires time $O(n^2)$ to check whether $G_x$ is bipartite.
The overall running time is then $O(n^2 \log n)$.

If the edges are already sorted by their weight, or if the edge weights are polynomially bounded (w.r.t. $n$) you can improve the above time complexity by a factor of almost $\Theta(\log n)$.
Indeed, if you have already conducted a bipartiteness test on $G_x$, and $G_x$ was bipartite, and then you are asked to determine whether $G_{x'}$, with $x' > x$, is bipartite there is no need to check all edges in $D_{x'}$. Indeed, you can get away with only checking the edges in $\Delta(x, x') = D_{x'} \setminus D_{x}$.
The idea is as follows: maintain a disjoint-set (union find) data structure $U$ on the vertices of $V$, such that if $u,v \in V$ belong to the same set in $U$, then they must also belong to the same side of the bipartition of the last tested graph $G_x$.
To be more precise: $U$ will contain one set $S$ for each isolated vertex of $G_x$ and two sets $S_1, S_2$ for each connected component $C$ of $G$ with at least $2$ vertices, where $S_1, S_2$ are the unique bipartition of $G$.
It is also convenient to store,  for each set $S_i$ in $U$, the name $\eta(S_i)$ of the set corresponding to the other side of the bipartition. Namely, $\eta(S_1) = S_2$ and $\eta(S_2)=S_1$.
If $S$ is a singleton set, then $\eta(S)$ is undefined.
Initially $x=0$ (assuming w.l.o.g. that all edge weights are non-negative) so $D_0 = \emptyset$ and $U$ contains $n$ singletons.
A bipartitness check on $G_{x'}$ can be done as follows: For each edge $(u,v) \in \Delta(x, x')$ query $U$ to find the sets $S_1,S_2$ such that $u \in S_1$ and $v \in S_2$. We distinguish some cases:

Case 1: $S_1 = S_2$. In this case $G_{x'}$ cannot be bipartite since we already know that $u$ and $v$ must be on the same side of the bipartition.

Case 2: $S_1 \neq S_2$, $\eta(S_1)$ is defined, and $\eta(S_1)=S_2$. In this case $(u,v)$ connects two vertices in different sides of the bipartition of an already existing connected component. Do nothing.

Case 3: $S_1 \neq S_2$ and $\eta(S_1)$ is either undefined or $\eta(S_1) \neq S_2$. In this case we just discovered an edge across different connected components. Perform a union operation between $\eta(S_1)$ and $S_2$ and let $S'$ be the resulting set (if $\eta(S_1)$ is undefined then $S' = S_2$).
Perform a union operation between $\eta(S_2)$ and $S_1$ and let $S''$ be the resulting set (if $\eta(S_2)$ is undefined then $S'' = S_1$).
Set $\eta(S') = S''$ and $\eta(S'')=S'$. See the figure for an example.

If all edges in $\Delta(x, x')$ are processed without ever encountering case 1, then $G_{x'}$ is bipartite.
The final algorithm checks whether $G_x$ is bipartite for $x \in W$ in order, until $G_x$ becomes not bipartite. Then it returns the predecessor $y$ of $x$ in $W$. The actual partition of $V$ can be found using standard techniques (the laziest one is to find a bipartition of $G_y$ from scratch).
All the sets $\Delta(x, x')$ can be found in time $O(n^2)$ once $E$ is sorted w.r.t. $w(\cdot)$ (if $E$ is not already sorted we can use radix sort and the fact that the weights are polynomially bounded).
Moreover, the number of find operations is $O(n^2)$ and the number of union operations is $O(n)$. Thus the overall required time $O(n^2 \alpha(n))$ where $\alpha(n)$ is the inverse Ackermann function.
Notice that $\Omega(n^2)$ is a trivial lower bound for your problem.


Is the height of the tree the number of edges or number of nodes?

As Yuval says, there's no standard definition. This is not because computer scientists are indecisive but because it's sometimes more convenient to use one definition and sometimes more convenient to use the other.  For example, a full, balanced binary tree of height $h$ has $2^h$ leaves if you define height as number of edges and $2^h-1$ vertices in total if you define height as number of vertices. Each of these statements becomes less convenient if you use the other definition and have to keep writing $h-1$ or $h+1$.

The situation is exactly the same as the natural numbers: sometimes, it's more convenient to say that zero is a natural number (for example, the natural numbers are a semiring only if zero is included); other times, it's more convenient to omit zero (for example, if you always want to be able to divide by a natural number).  In fact, similar things happen throughout mathematics. Another example is that it's common to insist that graphs have at least one edge (or at least one vertex) to avoid having to start all your theorems "If $G$ is not trivial, then..."


Longest path with limited edge traversals

In general, for a general graph with an arbitrary number of vertices, no.  The general problem is NP-hard (consider the case where all edge capacities are 1; this is the longest trail problem, which is NP-hard; my thanks to Willard Zhan for pointing out the connection to the longest trail problem),.  Therefore, there is unlikely to be an algorithm that is always correct and is efficient for all graphs.

In your case, it might be possible, as you can represent your problem as a graph with 26 vertices (one per letter) and 60,000 edges (one per word).  Moreover, you can condense it to a graph with 26 vertices (one per letter) and $26^2$ edges (one per pair of vertices).  Then, an exponential-time algorithm might suffice.  I don't know of any such algorithm, but I also can't rule out the possibility, either.

How to condense the graph?  Take all of the words (edges) that start with letter $i$ and end with letter $j$, sum up their corresponding capacities, and then add a new edge $(i,j)$ whose capacity is equal to that sum.  That leaves you with a single edge per pair of letters.  Any path through such a graph that respects the summed capacities can be transformed into a path in the original graph that respects the original capacities.

I realize this doesn't solve your problem, but maybe it is a small step towards that goal.


What is practical difference between NP and PSPACE-complete?

I think it depends on what you're interested in. If you're looking for an exact solution to a problem and you hear that it's either NP-hard or PSPACE-hard, then in either case you won't be able to find an algorithm for that problem that is simultaneously worst-case efficient, deterministic, and always correct unless P = NP or P = PSPACE. Therefore, if you're just looking for whether the problem is efficiently solvable in all cases, both NP-hardness and PSPACE-hardness probably means that you're out of luck.

However, if that's not the lens you're looking through, then (based on the suspicion that NP ≠ PSPACE) there's a difference between NP-completeness and PSPACE-completeness. If a problem is NP-complete, then even if you can't solve the problem efficiently, you can still check "yes" answers efficiently. On the other hand, if NP ≠ PSPACE and you have an instance of a PSPACE-complete problem you're convinced has a "yes" answer, there might not be any efficient way to convince someone else of this.

Hope this helps!


The Interleaved Transition System for 2 Independent and Concurrent Transition Systems

By definition, the interleaving operator is not synchronized, so any transition in $TS1\ |||\ TS2$ corresponds to a transition in a single component while the other one remains in whatever state it is.

More generally, in process algebras like CSP, the parallel composition operator $||$ can be parameterized with a set of symbols on which to synchronize - for example, you could consider $TS1\ |[\{a\}]|\ TS2$, which has the same states and $b$-transitions as $TS1\ |||\ TS2$, but only two (synchronized) $a$-transitions $(l_1,q_1)\to(l_3,q_2)$ and $(l_2,q_1)\to(l_1,q_2)$. In particular, $|||$ is the special case $|[\emptyset]|$.

The point is that (together with additional operations like hiding) this allows you to represent a far greater variety of models of interaction.


No, your proof is faulty.  You claim "we know that $L_1 \in P$", but that doesn't follow.  You haven't justified that claim, and I don't think it's true. It's not clear why you think that would be true, so it's hard to say why you went astray, but that's the first step that is wrong.  Also "is at most $L_3$ is not well-defined, and the intersection of a language in $P$ and a language in $NP$ is not necessarily in $P$.

I think you need to be more careful with your proofs: you have multiple steps where you make claims that simply don't follow from the previous steps.  I recommend you justify each step much more carefully, in more detail -- and if you can't, you should be suspicious of whether it is actually true.


How long does the Collatz recursion run?

This is Collatz conjecture - still open problem.
Conjecture is about proof that this sequence stops for any input, since this is unresolved, we do not know how to solve this runtime recurrence relation, moreover it may not halt at all - so until proven, the running time is unknown and may be $\infty$.


Checking whether a number divides any of a set of other numbers

A silly answer:

Precompute the union of the sets of the factors of all elements in the set.

Then checking if the number is a divisor of any elements in the set is just a single set lookup ($O(1)$). This, however, requires an absurd amount of precomputation (and space to store the resulting set).

The precomputation time can probably be improved - sort the input set, then for each number from 1 to the square root of the largest number in the set, check if any of the numbers from the number squared to the largest number in the set are divisible by the number (add it to the cache if so). It's still absurd, however.


Does a Haskell program count as an inductive proof?

The statement is not true as stated. Even if we imagine a Haskell-like language where all functions terminate and values are non-bottom, only some programs would correspond to inductive proofs (as opposed to proofs not using induction), but it would be the ones that (directly or indirectly) use recursion. That said, what they are doing induction over may not at all be obvious. (For the OP: every inductive type gives rise to a notion of structural induction with "mathematical induction" just being structural induction over the naturals.) Many patterns of recursion in practical programs, e.g. quicksort, do not correspond to a direct structural induction over their inputs.

For real Haskell, for just about any program proving that it terminates for all inputs requires very strong restrictions on those inputs: all values must be fully defined and all passed in functions must terminate on at least the inputs exercised by the current program. The latter isn't checkable in general, but what we can do instead is reduce a value that stands for a putative proof to normal form, and if we succeed then we have a real proof. Unfortunately, Haskell doesn't evaluate things to normal form but only to weak head normal form. For some types we can force the weak head normal form of one expression to correspond to normal forms via rnf, but we can't do this for functions in general.

Even without restrictions, programs in Haskell correspond to proofs in some logic, albeit an inconsistent one. This leads to another aspect that they conveniently didn't elaborate on. They say that certain Haskell programs correspond to proofs of theorems, but they don't say what theorems you can state! Haskell (particularly with higher-rank polymorphism) is closely related to the polymorphic lambda calculus and that corresponds to intuitionistic, second-order propositional logic1 (SOPL) (not to be confused with second-order predicate logic which is usually what "second-order logic" refers to). While SOPL is uninteresting in the classical case, it turns out to be pretty powerful in the intuitionistic case, capable of embedding intuitionistic first-order predicate logic. The embedding is non-obvious and even with it you would not be able to prove something like the Fundamental Theorem of Arithmetic. In practice, most programs correspond to completely trivial theorems or (intutionistic) propositional tautologies.

From my (admittedly very brief) skimming of the paper, it seems that they are more interested in the Prolog-like reasoning the type class system enables than leveraging the propositions-as-types correspondence. So their comments seem to be a bit of a non sequitur anyway.

1 See Chapter 12.


Unique decipherability of infinite regular language

McCloskey gave such an algorithm in his paper An $O(n^2)$ Time Algorithm for Deciding
Whether a Regular Language is a Code. Given an NFA on $n$ states, his algorithm runs in time $O(n^2)$. Since a regular expression of length $n$ can be converted to an NFA with $O(n)$ states in linear time, McCloskey's algorithms runs in quadratic time even when given a regular expression as an input.


Is the weighted transitive reduction problem NP-hard?

Consider $G=(V,E)$. Let $w_{ij} = 1$ if $e_{ij} \in E$ and let $w_{ij} \gg 1$ if $e_{ij} \notin E$. This choice of weights correspond exactly to the constraint $E' \subseteq E$. Thus, if the weighted transitive reduction is polynomial time solvable, then so is the minimum equivalent graph problem.


What is the name for this ... (alerting when threshold is exceeded, but only if dropped enough below threshold first)

Hysteresis is a general concept in control systems that seems relevant.

Debouncing is another specific technique used for post-processing data from switches/buttons that has a similar flavor.  The term has sometimes been used elsewhere in software systems to deal with similar issues.

Finally, take a look at rate limiting for a related technique.


I don't know of any algorithm that will work for all $a,b$, because of the possibility that you might have to use an intermediate value that is extremely large, and I'm not aware of any reasonable bound on how large of an intermediate value you need to contemplate.

However, here's one heuristic.  Suppose we only consider sequences where no intermediate value exceeds some constant $K$.  Then you can use dynamic programming to determine whether it's possible to go from $a$ to $b$, without ever exceeding $K$.  You build an array $A[1..K]$ where $A[i]=1$ means that it's possible to reach $i$ from $a$,  and fill it in via a fixed point computation, as follows:

Set $A[a]=1$ and $A[i]=0$ for all $i \ne a$.
Repeatedly do the following, until you do an entire iteration without changing the array:

For each $i := 1,2,\dots,K/3$, if $A[i]=1$, set $A[3i] := 1$.
For each $i := 3,4,\dots,K$, if $A[i]=1$, set $A[\lfloor i/2 \rfloor] := 1$.

Finally, if $A[b]=1$, you know it's possible to go from $a$ to $b$.  (If $A[b]=0$, you can conclude nothing; maybe there's a way to get from $a$ to $b$ by going through some intermediate value larger than $K$.)


Consider $n$ axis-parallel squares of equal size shifted along the line $y = x$ such that the bottom-left corners of the squares all fit within the first square. E.g. for $n = 4$:

Then you have $2(n - 1)$ external intersection points but $(n-1)(n-2)$ internal ones (and thus $n(n-1)$ total).


(First, a side note: it happens that Connected Vertex Cover isn't actually NP-hard for all classes of graphs. In particular, it's solvable in polynomial time in chordal graphs and graphs with maximum degree 3. However, it is NP-hard for planar graphs with maximum degree 4 in particular, and that's the easiest case to prove.)

For this, you'll want to reduce from Planar Vertex Cover. This is the special case of Vertex Cover where the input graph is planar, and it itself can be proved NP-hard by reduction from Planar 3Sat. (Planar 3Sat is, similarly, the special case of 3Sat where the input graph is planar. Proved NP-hard by reduction from normal 3Sat, and it itself is used to prove that various games are NP-hard, such as Super Mario Bros, Super Mario Bros 3, and Super Mario World.)

This reduction was first done by Garey and Johnson in 1977. I'm currently trying to find the full details of their proof, but these lecture notes provide a general overview.


An obvious approach to explaining NP != coNP, how far has it been pushed?

Not very far. The approach that you are describing is known as proof complexity, and it is covered by several surveys and lecture notes. There are several kinds of proof system being considered:

Frege systems. These are systems in which a proof consists of a sequence of formulas or circuits (depending on the system), and there is a fixed set of derivation rules.
Algebraic proof systems such as the Polynomial Calculus and Nullstellensatz. Here each line is a polynomial.
Cutting planes, in which each line is a linear inequality.

There are also other proof systems such as the Hajos calculus, a proof system for proving that a graph isn't 3-colorable.

We have strong lower bounds for some of these systems, but in the Frege front, the best lower bound is for bounded depth Frege, in which the depth of all lines in the proof is bounded by some constant. This lower bound is similar in some regards to AC0 lower bounds for circuits, but is otherwise more complicated. We have no lower bound for the version in which the depth is bounded but we allow mod $p$ gates; the algebraic methods used to prove lower bounds on circuits don't seem to work, and the problem seems related to derandomizing polynomial identity testing, a notoriously difficult problem in algebraic complexity theory.

The Frege proof system itself has as lines arbitrary formulas, and Extended Frege has arbitrary circuits as lines. It is thought that Extended Frege is stronger than Frege. Other proof systems are conjectured to be stronger than even Extended Frege. It is not clear currently whether there is a "super" proof system, which is optimal up to polynomial factors compared to any proof system. Thus even if we do manage to prove lower bounds for progressively more general proof systems – which is expected to be harder than proving corresponding circuit lower bounds – we wouldn't necessarily be able to prove that NP is different from coNP in this way.


Are weakly polynomial time algorithms truly polynomial?

As Wikipedia says, there are two conditions for strongly polynomial time algorithms:

  the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
  the space used by the algorithm is bounded by a polynomial in the size of the input.

I will simply call these two conditions as condition 1 and condition 2 in this answer.

  The algorithm is already polynomial time in the arithmetic model, so as long as its space is bounded in the TM model then the rest of the algorithm is still polynomial time in the TM model. Think of it like this, when converting from the arithmetic model to the TM model, the only thing that can go wrong is the space. The numbers you produce need to be representable in a number of bits that is polynomial in the number of bits in the input. So long as that holds, the rest of the algorithm is still polynomial time in the TM model.

This paragraphs is describing why condition 2 is necessary for strongly polynomial time algorithm, it is not stating the difference between strongly and weakly polynomial time algorithms. In fact, condition 2 is also necessary for weakly polynomial time algorithm, and the example algorithm that computes $2^{2^n}$ given $2^n$ is NOT weakly polynomial (and is even not a polynomial time algorithm).

In fact, it is condition 1 that describes the difference between strongly and weakly polynomial time algorithms. Note the definition of strongly polynomial time algorithms is equivalent to

  condition 1; and
  the algorithm is a polynomial time algorithm (in the TM model)

While the definition of weakly polynomial time algorithms is equivalent to

  condition 1 is not satisfied; and
  the algorithm is a polynomial time algorithm (in the TM model)

It is more clear to see the difference between strongly and weakly polynomial time algorithms with these two redefinitions.

This post is wrong to suggest the difference is weakly polynomial time algorithms don't run in polynomial time on a TM. I have added a comment on that post addressing this issue.


What other involutions are there besides xor?

Roll your own.

Take an arbitrary bijection $f$ from the integers to integers. This is a permutation of the integers.

Then, take the conjugate of XOR ($\oplus$):
$$
    g(x,y) = f^{-1}(f(x) \oplus f(y))
$$
We then have
$$
g(x,x) = f^{-1}(0)
$$
which now acts as the "new zero" (neutral element)
$$
g(x,f^{-1}(0)) = x
$$
We also have that $g$ is associative and commutative
$$
g(x,y) = g(y,z) \qquad
g(g(x,y),z) = g(x,g(y,z))
$$
So, we still have an abelian group where $x^{-1}=x$. The trick on arrays mentioned by the OP still works.


No. Consider, for instance,
$$T(n,m) = \begin{cases}
m, & \text{$m$ even} \\
\frac{m}{n}, & \text{$m$ odd}
\end{cases}$$
and notice $\frac{m}{f(n)} \le T(n, m) \le m$ holds for $f(n) = n$. Suppose $T(n,m) \in \Theta(m g(n))$ for some $g(n)$, that is, there are $c, c' > 0$ with $cmg(n) \le T(n,m) \le c'mg(n)$ for all but finitely many $m,n$. Since there are infinitely many odd $m$'s we get $g(n) \le \frac{1}{cn}$ for all but finitely many $n$. For even $m$ it then follows
$$m = T(n,m) \le c' m g(n) \le \frac{c'}{c} \frac{m}{n},$$
which can only hold for finitely many $n$.


Why does the denotational semantics for a while loop have a existence quantifier?

The existential quantifier is misplaced. This is due to lack of reasonable notation for what needs to be expressed, namely: "if there is $i$ safisfying condition $C$, then use that $i$", where we make sure that at most one such $i$ exists. It would be better to write (and by the way, you might appreciate LaTeX's cases environment):
$$
\mathcal F^{k}(\bot)(\sigma) =
\begin{cases}
    [\![s]\!]^i  & \text{if $i < k$ and $[\![b]\!] [\![s]\!]^i \sigma = \text{false}$ and, for all $j < i$, $[\![b]\!] [\![s]\!]^j \sigma = true$}\\
     \bot & \text{otherwise}
\end{cases}
$$
It may be helpful to look at a simpler definition. Suppose we want a function $f : \mathbb{N} \to \mathbb{N}$ which maps an odd number to zero and an even number to half of itself. The following is a reasonable definition:
\begin{align*}
f(2 n) &= n\\
f(2 n + 1) &= 0
\end{align*}
as is the following (where $m$ and $n$ range over natural numbers):
$$
f(m) =
\begin{cases}
n & \text{if $m = 2 n$,}\\
0 & \text{otherwise.}
\end{cases}$$
The point is that precisely one branch applies, and in a unique way, as there can be at most one $n$ satisfying the condition $m = 2 n$. However, the following is not a reasonable definition:
$$
f(m) =
\begin{cases}
n & \text{if $\exists n \in \mathbb{N} \,.\, m = 2 n$,}\\
0 & \text{otherwise.}
\end{cases}$$
The problem is that the $n$ outside the $\exists$ quantifier is completely unspecified. This is so because the $n$ inside the $\exists$ quantifier is bound and can therefore be renamed at will:
$$
f(m) =
\begin{cases}
n & \text{if $\exists k \in \mathbb{N} \,.\, m = 2 k$,}\\
0 & \text{otherwise.}
\end{cases}$$
(And we do not rename the outer $n$ because it is not in the scope of $\exists$.) This makes it clear that the existential quantifier has no place there. It is important to understand variable bindings. In the above definition of $f$, the variable $n$ is bound in the entire case, not just in the condition.

From a very formal point of view, the map $f$ is defined here as a relation explaining how an argument of $f$ is related to its value.
A definition of the form
$$f(m) =
\begin{cases}
e_1(m,n) & \text{if $\phi_1(m,n)$} \\
e_2(m,n) & \text{if $\phi_2(m,n)$}
\end{cases}
$$
is equivalent to
$$f(m) = \text{the $v$ such that $\psi(m,v)$}
$$
where
$$\psi(m,v) \iff
(\exists n \,.\, \phi_1(m,n) \land v = e_1(m,n)) \lor
(\exists n \,.\, \phi_2(m,n) \land v = e_2(m,n))$$
Now the quantifiers are justified. By the way, we could have used $\forall$ instead:
$$\psi(m,v) \iff
(\forall n \,.\, \phi_1(m,n) \Rightarrow v = e_1(m,n)) \land
(\forall n \,.\, \phi_2(m,n) \Rightarrow v = e_2(m,n)).$$


Possible ways to have cross and full edges in a mincut maxflow

This is the previous question which defines the terms. I hope this helps you solve the question.

Thus question provides these as true:

always full and always crossing.
always full and sometimes crossing.

We know from the definitions I've provided that the following are also true:

sometimes full and never crossing
never full and never crossing

This is all. The answer is included in the definitions.


What does the posterior probability of a variable mean in the Bayes' rule?

The word posterior stems from the latin word posterior (base form posterus), which means later, after, behind.

In the context of probability and Bayes' theorem it denotes a probability, often written as a symbol $P(A|B)$, where $A$ and $B$ are random variables. This symbol $P(A|B)$ means the probability of $A$ after you have observed $B$. Hence the naming posterior probability, or short posterior.

In this context the probability of observing a certain value of the random variable $B$ is denoted by $P(B)$ and is called prior probability, or just prior for short sometimes. The word prior also stems from a Latin word, pri, which means before. The name hints that you will gather observations of $B$ before you calculate $P(A|B)$.

In this way you use prior information to improve your model of $A$, expressed by the posterior probability $P(A|B)$. By this your probability of $A$ is based on the observed outcome of $B$. Like it has been said by John Maynard Keynes "When the facts change, I change my mind. What do you do, sir?".


Do subqueries add expressive power to SQL queries?

To translate your statement into the relational algebra, I think it asks:

  Can we rewrite $\sigma_A(A)\bowtie \sigma_B(B)$ as $\sigma_A(\sigma_B(A\bowtie B))$?

(Where $\sigma$ is select and $\bowtie$ is join.)

The answer is "Yes," and it's a standard query optimization. To be honest, I'm not sure how to prove this in a non-question-begging manner - it's just a property of selection and join. You can argue inductively to add however many layers of nested queries you want.

Additionally, you might ask:

  Can every sequence of joins be written as $A\bowtie B\bowtie C\bowtie\dots$ [As opposed to, say, $(A\bowtie B)\bowtie(C\bowtie D)$]?

Again the answer is yes, because join is associative. Similar statements can be made about projection as well.

One notable type of "subquery" which I think cannot be "flattened out" is with. One way to see this is to note that if you have a with statement then you can have a recursive function, which cannot be written without using subqueries.

So to sum up: in the specific case you mentioned, no, SQL does not need subqueries, and you can prove it inductively. In general though, there are features which require subqueries.


Is it decidable whether a linear language contains a square?

It is indeed undecidable whether a linear grammar generates a square. Same technique, reduction from PCP.

Starting with the two sequences of strings  $(u_1,\dots,u_n)$, $(v_1,\dots,v_n)$  that define the PCP we can build a linear grammar with strings of the form
$u_{i_1}\dots u_{i_k} j_k \dots j_1 \# v_{j_1}\dots v_{j_k} i_k \dots i_1 \# $.

Rules like $S\to A\#$;

$A \to u_i A i \mid u_i B i$;

$B \to j A v_j \mid j v_j$.

Such a string is a square if both the indices and the strings match, hence iff we generate a solution of PCP.

(I really did not know the answer when I posted the question... Sorry. I started examining ways to show decidability.)


What is the maximum number of indices one can create on a table with N columns?

I assume you mean the following: given $N$ columns, there are

$N$ single columns, giving $N$ different indices
$N(N-1)/2$ pairs of columns, and 2 ways to combine each pair, giving $N(N-1)$ different indices
$\frac{N(N-1)(N-2)}{2 \cdot 3}$ triples of columns, and $3 \cdot 2$ ways to combine each triple, giving $N(N-1)(N-2)$ different indices

and so on. This number doesn't have a (well-known) name, but the sequence does have its own OEIS entry:

  Eighteenth- and nineteenth-century combinatorialists call this the number of (nonnull) "variations" of n distinct objects, namely the number of permutations of nonempty subsets of {1,...,n}.

Various formulas are given to compute it, including a recurrence relation $a_n = n(a_{n-1} + 1)$ and the rather surprising $a_n = \lfloor{e \cdot n! - 1}\rfloor$.

One could argue that you can create more indices by taking into account that columns can be used in ascending and descending mode. For indices with more than one column, this even has an influence on which records are 'near' each other.


Algorithm for scheduling unit time tasks with arrival times and deadlines

The more general version of your problem is the scheduling problem where we have $n$ independent tasks, each with an arrival time, a resource requirement (time), and a deadline. We define the Earliest Deadline First algorithm such that at every timepoint, we choose to process the task with the nearest deadline. While time is continuous, it is trivial to see that we can discretize time to be all points at which a task finishes or a new task arrives.

It is known that EDF is an optimal uniprocessor scheduling algorithm i.e. if there is a feasible schedule, EDF will find it and if EDF does not find a feasible schedule, then no feasible schedule exists. [1], [2]. However, this is not linear time if we aren't guaranteed an ordering of the deadlines of the arriving tasks. Let's use a priority queue to represent the waiting tasks. At every time point, which there are $O(n)$ of, we must insert and/or pull the next task from a priority queue sorted on deadlines. Each insertion is $O(\log n)$ time, thus resulting in $O(n\log n)$ time.

If your input was sorted by arrival, we could easily find whether or not there is a valid schedule by following the algorithm above, iterating through the days, adding tasks for that day to a priority queue and selecting the task with the nearest deadline from the queue. We fail if we ever try to assign a task to a day on or past its deadline.

As mentioned in the comments, we can sort the input by arrival time in linear time using counting sort or pigeonhole sort. The issue then is to somehow make the priority queue also linear time.


Wlog let $g$ be a strong one way function, we will now construct a length preserving oneway function $f$.
Since $g$ is PPT computable by assumption, there is a polynomial $p$ s.t $|g(x)| \le p(|x|)$ for all $x$
Define
$$g'(x) = g(x)||10^{p(|x|) - |g(x)|}$$ this function always has $|g'(x)| = p(|x|)$. and is trivially strongly one way.
We now have to force $|x| = |f(x)|$.
This we can do by taking $p(|x|)$ bits as input and taking only $|x|$ of it into account, i.e
$f(x||y) = g'(x)$ for $|y| = p(|x|) - |x| + 1$.
Strong one-wayness of $f$ follows from the strong one-wayness of $g'$.
Had $f$ not been strongly one way, we could query a PPT adversary of $f$ for  $z = f(y)$  get $x = x_1 || \ldots || x_n$ back and try for each $m \in [n]$ whether $g'(x_1||\ldots||x_m) = z$ and eventually find a preimage of $z$ under $g'$  in polynomial time with non negligible probability. Conradiction.
See the original proof here.


NP-completeness of graph isomorphism through edge contractions with an edge validity condition

The answer is yes.  Suppose that you had a polynomial-time algorithm to solve your revised problem.  Apply that algorithm to the special case where the subset of edges available at each step is the whole set.  We'd then have a polynomial time algorithm for the original, known NP-complete, problem.

To have any hope of dreaming up a non-NP-complete version, you'd need to put a restriction on the subsets that were eligible that would prevent an immediate reduction to the original problem.  At that point you'd have a new problem which you cannot easily show is NP-complete.  However it is in the nature of NP-complete problems that, if your restriction avoids 2+ choices at each step, it very likely to be NP-complete.

(Note, it is currently unknown whether the simpler problem of identifying whether two graphs are isomorphic is NP-complete.)


We prove by induction on $n$ that your sum (with $O(n_1)$ replaced with $n_1$, only taken over non-leaves) is at most $n\log_2 n$. We use the convention $0\log_2 0 = 0$. The base case $n$ = 0 trivially holds, since the sum is empty. Now suppose we have a node with subtrees of sizes $n_1 \leq n_2$; this implies that $n = n_1 + n_2 + 1$. The sum is at most
$$ S = n_1\log n_1 + n_2\log n_2 + n_1. $$
Let's concentrate on the first two terms:
$$
\begin{align*}
n_1\log n_1 + n_2\log n_2 &= (n_1 + n_2) \left[ \frac{n_1}{n_1+n_2} \log n_1 + \frac{n_2}{n_1+n2} \log n_2 \right] \\ &=
(n_1 + n_2) \left[ \frac{n_1}{n_1+n_2} \log \frac{n_1}{n_1+n_2} + \frac{n_2}{n_1+n_2} \log \frac{n_2}{n_1+n_2} + \log (n_1+n_2) \right] \\ &= (n_1+n_2) [\log(n_1+n_2) - h(\tfrac{n_1}{n_1+n_2})],
\end{align*}
$$
where $h(p)$ is the binary entropy function. Let $p = n_1/(n_1+n_2) \leq 1/2$. Then we can bound $S$ by
$$ n \log n + (n_1+n_2)(p-h(p)). $$
One checks that $p \leq h(p)$ for $0 \leq p \leq 1/2$, completing the proof. (In fact, $2p \leq h(p)$, so we can get the better bound $\tfrac{1}{2}n\log_2 n$, which is nearly tight for complete binary trees.)


Optimal Algorithm for Finding Maximal Number of Colinear Points

Algorithm: RANSAC would be a good algorithm for this problem, if you think there exists a line such that a large fraction of points lie on that line.  (However, if there is no such line, RANSAC is not a good choice.)  In each iteration, it randomly selects two points, draws a line through them, and then checks how many other points fall onto that line.  It then does many iterations repeatedly, and keeps the best line it has found so far.

Analysis: Suppose there exists a line $L$ such that a fraction $p$ of the points are on the line $L$.  Then any particular iteration has a $p^2$ probability of picking two points on the line $L$ and discovering the line $L$.  So, if you run RANSAC for $O(1/p^2)$ iterations, then with high probability the line $L$ will be detected.  Each iteration takes $O(n)$ time, so the total running time will be $O(n/p^2)$.  For some values of $p$, this will be faster than your crude algorithm (which has a $O(n^2)$ running time).

In short, the more points on the optimal line, the faster RANSAC will find it.

This doesn't answer your question about the best worst-case complexity.  I don't know if it is possible to beat ${n \choose 2}$ worst-case complexity.  I don't know if this is optimal or if there are better algorithms.  Also, even in the case where we know there is a line containing many points and where we care about average-case complexity, I don't know if RANSAC is optimal or if one can do better.


Is SAT-Problem with XOR and AND NP-complete

Your question is likely answered by Schaefer's dichotomy theorem. In particular, if an instance of your problem is a conjunction of formulas, each one depending on a bounded number of variables, then according to the theorem your problem is either in P or NP-complete; and moreover there is a simple criterion to decide which case it is.


checking '<' for two binary numbers in a cnf-formula

Yuval describes the general approach.

Let the binary representation of the two numbers be $n_1,\dots,n_k$ and $m_1,\dots,m_k$, where $n_1$ is the most significant bit.  Introduce fresh new boolean variables $t_1,\dots,t_k$.  The intention is that these will indicate the common prefix of $n,m$.

In particular, add the following clauses:

$t_{i+1} \implies t_i$ -- this ensures that $t_1,\dots,t_k$ has the form $1,\dots,1,0,\dots,0$.
$t_i \implies (n_i=m_i)$ -- this ensures that $t_1,\dots,t_k$ captures the common prefix of $n,m$
$(t_{i-1} \land \neg t_i) \implies (n_i=0 \land m_i=1)$ -- this ensures that at the first position where $n,m$ differ, $n_i < m_i$.  (For the case $i=1$, treat $t_{i-1}$ as True.)
$\neg t_k$ -- this ensures $n \ne m$

Each of these can be converted to a conjunction of CNF clauses.  For instance, the first corresponds to the CNF clause $\neg t_{i+1} \lor t_i$.  The second corresponds to $(\neg t_i \lor \neg n_i \lor m_i) \land (\neg t_i \lor n_i \lor \neg m_i)$.  The third corresponds to $(\neg t_{i+1} \lor t_i \lor \neg n_i) \land (\neg t_{i+1} \lor t_i \lor m_i)$.

Now your formula is the conjunction of all of these CNF clauses.  You obtain a formula with about $5k$ clauses.  This formula will be satisfiable iff $n<m$.


Dynamic programming approach for finding perfect square subsequence

Let us assume first that by subsequence you mean non-contiguous subsequence.

There are 10 primes in the range $1,\ldots,29$:
$$ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. $$
You can represent each number in the range $1,\ldots,29$ as a vector of length 10 of exponents. A set of such vectors correspond to numbers whose product is a perfect square iff they sum to a vector whose entries are all even. Alternatively, if we think of the exponents modulo 2, then a set of such vectors correspond to numbers whose product is a perfect square iff they sum to zero.

This suggests the following algorithm. Construct a matrix whose rows correspond to the vectors outlined above (modulo 2), and determine its rank. From the rank you can compute the size of the kernel, which is the quantity you’re after.

Suppose now that you’re after contiguous subsequences.

Let $b_i = a_1 \cdot a_2 \cdots a_i$. The subsequence $a_i,\ldots,a_j$ multiplies to a perfect square iff $b_j/b_{i-1}$ is a perfect square, which happens if the vectors corresponding to $b_{i-1}$ and $b_j$ are equal.

This suggests the following algorithm. Compute the vectors corresponding to each $b_i$ (do this by computing the vectors for $a_i$ and summing them as you go), sort them (you can represent them as 10-bit integers in an arbitrary way), and divide them into runs of length $c_1,\ldots,c_\ell$. The answer is then $\sum_i \binom{c_i}{2}$.


Let the $n$ distinct positive integers are represented by $c_1,\ldots,c_n$. Now form a series of sums as;

\begin{align}
S_1 =&\; c_1 \\
S_2 =&\; c_1 + c_2\\
    \vdots & \\
S_n =&\; c_1 + \ldots c_n
\end{align}

Now, use the pigeonhole principle on the $S_i$'s with $m$ holes and place them into the holes according to their result modulo $m$. We know that at least two $S_i$'s are sharing the same hole since $n>m$. Let call them $S_i$ and $S_j$.

$S_i \equiv S_j \bmod m \implies S_j -S_i \equiv 0 \bmod m \implies m| S_j-S_i$

By using the definition of $S_i$ and $S_j$ we can say that if $i<j$ then $m \;|\; a_{i+1} + \ldots + a_{j}$

if $n <= m$ we cannot prove it and even we can find counterexamples.


Using Union find to check whether there is a cycle in a graph

The way it works is that your sets are connected components of the graph. You build such components incrementally, adding one edge at a time. When you add each edge, you ask if the vertices are part of the same component, if so then you have a cycle, if not, then you join the two components (perform a set union). Keep adding edges until you run out of them or found a cycle.

If we look at the definition of connected component, it implies that for each two vertices $u$ and $v$ in the same component, there's a path connecting them.

The algorithm works as follows: you start adding a Singleton set for each vertex to your dsu. These are your first components. Then add the first edge, obviously, the two vertices will be on separate sets (components), and you just found an edge connecting them, so that means they belong to the same component. So you join the two sets (components) into a single one, as your edge is the path connecting them.

You keep going, everytime you find an edge connecting two vertices in different components, you can join the components, as that edge will be a bridge connecting them: if the vertices are $u$ and $v$, and you have $w$ in $u$'s component, you can assert that there's a path from  $w$ to $v$ passing through your current edge. Is easy to see now that all vertices in both components are now connecting. So join the two sets (components) in one.

Finally, when you process an edge which vertices $u, v$ are on the same component, you just found a cycle: since both are on the same component, you know there's a path between them, and your new edge happens to close the cycle.

DSU is typically used for implementing Kruskal's algorithm,  and uses the same properties. You can do a quick Google search for Kruskal with DSU, for examples.


k-basis representation of natural numbers

Hint: For most infinite $S$, the languages $A_2(S),A_3(S)$ will both not be regular. Find some set $S$ for which $A_2(S)$ is regular (since the binary representations of numbers in $S$ are very simple), and with any luck $A_3(S)$ won't be regular. (Don't choose $S = \mathbb{N}$ or $S = \{ ax+b : x \in \mathbb{N} \}$.)


Simulation BPP by Pseudorandom Generator

The idea of a PRNG is coming up with a "deterministic" sequence that "looks like" random, in the sense that programs getting access to it act (roughly) as if they had access to a completely random string. The PRNG takes a seed or a key, and outputs a larger pseudorandom sequence. When simulating some probabilistic algorithm, instead of choosing a completely random string, it is enough to choose a random seed and use a PRNG.

How would you use a PRNG to simulate (say) a BPP algorithm? Suppose we had a PRNG that takes a seed of length $L = O(\log n)$, and $\epsilon$-fools every BPP algorithm. (Pseudorandom sequences don't look completely random, but in this case, using them instead of a random sequence changes the probability of any event by at most $\epsilon$.) That means that if we pick the seed at random, then the BPP algorithm returns the correct answer with probability at least $2/3-\epsilon$ (supposing that the original success probability was $2/3$ - that depends on your definition of BPP). If $\epsilon < 1/3$, then we have the following property:

If we run the algorithm on a YES instance and a random seed, then it returns YES with probability larger than $1/2$.
If we run the algorithm on a NO instance and a random seed, then it returns YES with probability less than $1/2$.

This property assumes we choose a random seed, but we wanted a deterministic algorithm. To that end, we go over all possible seeds, and calculate the probability that the algorithm returns YES. This is just the number of times that the algorithm returns YES divided by $2^L$. If the probability is larger than $1/2$ then it's a YES instance, otherwise its a NO instance. If indeed $L = O(\log n)$, then $2^L$ is polynomial, and we obtain a deterministic polynomial time algorithm.

Now regarding your questions:

I haven't looked at the scribal notes, but the advantage might come from the BPP algorithm.
Looking at a fixed seed is the same as looking at a fixed "random" sequence - you don't need a PRNG for that. All you know is that on average, the performance of the algorithm on a pseudorandom sequence correlates with whether the input is a YES or a NO instance. That doesn't say anything about a single seed.
As to uniformity, the program that your PRNG should fool is $A(x)$ for an arbitrary input $x$. While $A$ is a uniform circuit, $A(x)$ isn't, since $x$ could be arbitrary. Your PRNG should fool at one and the same time $A(x)$ for all possible inputs $x$.


Can Inverse of weights(1/weight,not negation) be used to find the longest path between two points by using dijkstra's algorithm?

Hint: take a graph with all weights equal 1.


I think it helps to keep in mind the propositions as types mantra. Every type can be read either as a propostion or a set. This gives us two readings (let's just consider types dependent on natural numbers):

A dependent type $P : \mathtt{nat} \to \mathtt{Type}$ is like a family of sets $P(0), P(1), P(2), \ldots$
A dependent type $P : \mathtt{nat} \to \mathtt{Type}$ is a property of natural numbers where we think of $P(n)$ as the proofs that $n$ has property $P$

With this in mind it may be easier to make sense of dependent types. For instance, consider:

$\mathtt{Mat}(n)$: the type of matrices of size $n \times n$
$\mathtt{Less}(a,b)$: the proofs that $a < b$

Then $\mathtt{Mat}(n)$ should be thought of as a collection of sets, one for each $n$, while $\mathtt{Less}(a,b)$ is a relation (a binary predicate) on pairs $(a,b)$.

Your first three examples (NVec, NMMatrix, Fin) are dependen types of the first kind. The other ones are of the second kind.

Strictly speaking, when you say "a pair of integers where teh second is greater than the first", that is not a dependent type but an element of the dependent sum, i.e,

$$\mathtt{PAIR} = \textstyle\sum_{(a,b) : \mathtt{nat} \times \mathtt{nat}} \mathtt{Less}(a,b),$$

i.e., a triple $(a, b, p)$ where $p$ is a proof that $a < b$. Similarly, your NBtree and SBTree examples are really dependent sums of the form $\sum_{t : \mathtt{Tree}} P(t)$, not dependent types. The sums of course use dependent types $P(t) = \text{"proofs that the tree $t$ is height-balanced"}$ and $P(t) = \text{"proofs that the tree $t$ is sorted"}$.


As you have seen, $\log(n+1) \in \mathcal{O}(\log n)$. That means that $\log n \in \Omega(\log( n + 1))$. Now you can change $n$ with $n-1$ and have your answer.
To be more precise, $\log(\alpha n^{\beta} + \gamma) \in \Theta(\log n)$ for any $\alpha, \beta, \gamma \in \mathbb{R}_{>0}$.


Algorithm for finding maximum mutually coprime subset of a multiset of integers

Your problem is equivalent in complexity to the maximum set packing problem.  Unfortunately, maximum set packing is NP-hard.  Therefore, you'll need to use one of the methods in Dealing with intractability: NP-complete problems.

Here's the gist of the equivalence.  Each integer in your set A corresponds to a set of its prime factors; now you're looking for a maximum-size collection of those sets that are pairwise disjoint.  That's exactly maximum set packing.  This is only the gist of the idea; this reduction doesn't quite work, because as you noticed, factoring each element of A can take quite a bit of time (there's no known polynomial-time algorithm for factoring).

It's possible to fix up the reduction as follows.  Given an instance of your problem, factor A into a coprime base.  A coprime base is a list of integers that are pairwise co-prime (no two elements in the coprime base any common factor), and where every number in A can be factored into a product of elements of the coprime base.  For instance, a coprime base for A = {30, 105, 126} would be {5, 6, 21}.  Note that the elements of the coprime base do not need to be prime.  There are efficient algorithms for finding a coprime base for A.  Now, associate to each number x in A the set of elements of the coprime base that are divisors of x.  Then you have an instance of the maximum set packing problem.

(Conversely, given an instance of the maximum set packing problem, you can convert it into an instance of your problem, by simply treating the universe for the set packing instance to be the prime numbers.)

So given that you basically have an instance of maximum set packing, what should you do?  Well, maximum set packing has been well-studied, so you can use the literature on that problem.  Here are some candidate approaches:

ILP: It's easy to formulate the maximum set packing problem as an instance of integer linear programming.  You have a zero-or-one variable $x_i$ for each integer $i$ in A, with the idea that $x_i=1$ means that $i$ is included in the output list.  You add a constraint $x_i+x_j \le 1$ for every pair of numbers $i,j$ that have a common factor.  Then, you try to maximize the objective function $\sum_{i \in A} x_i$.  Feed this to an off-the-shelf integer linear programming solver, and it will give you the best solution it could find.

If you want something simple to implement and optimal, I suspect the ILP-based algorithm is your best bet.  It'll be easy to implement.  There's no guarantee that it'll be efficient -- it's an NP-hard problem, after all -- but it might work well enough in practice if the problems sizes are small enough.

Heuristics: You can use any of the known heuristics for set packing.  See, e.g., https://en.wikipedia.org/wiki/Set_packing#Heuristics, or search the research literature.

Approximation algorithms: Wikipedia says that it is known how to approximate maximum set packing to within a factor $k/2$, if $k$ is the size of the largest set.  (In other words, $k$ is the maximum number of elements of the coprime base that can divide any single element of A.)  If the numbers in A aren't too large, then $k$ will be relatively small, so this approximation algorithm might be reasonably effective.  Wikipedia doesn't say what the algorithm is, so you'll have to do some research in the literature.


Wrong DFA from NFA. String Does not contains 110

I don't think you did the conversion correctly.  You don't show your steps so I can't tell where you went wrong, but check your work again.  If the NFA is in state A and it receives a 1, what states might it go to?  If the NFA is in state C and it receives a 1, what states might it go to?  So what state should the DFA (FSA) go to if it is in state AC and receives a 1?

There appear to be multiple errors in the conversion.  For instance, the edge out of AB also looks incorrect.

Try applying the standard algorithm and running it by hand, one step at a time.


Optimal path through a DAG with sparsely available edge weights

Your question is not self-consistent, so you first need to figure out exactly what you are looking for, before we can identify an algorithm to find it.

However, once you figure that out, it is likely that dynamic programming will solve your problem.  Dynamic programming is powerful and likely to solve your problem for any reasonable criterion that depends only on detail and erraticism (assuming it is monotonic in each variable separately).

In particular, define $f(v,d)$ as follows:

  $f(v,d) = $ the smallest possible erraticism that can be achieved by a path from $A$ to $v$ whose detail is $d$.

In other words,

$$f(v,d) = \min \{\text{erraticism}(p) : p \text{ is a path from $A$ to $v$ and } \text{detail}(p)=d\}.$$

Let $\text{pred}(v)$ denote the set of vertices $u$ such that there is a path from $u$ to $v$ where you have the metric for $u$ but not for any other intermediate vertex in the path (i.e., not for any other vertex in the path other than $u$ or $v$).

Notice you can compute $f(v,d)$ given the values of $f(u,c)$ for all $u \in \text{pred}(v)$ and all integers $c$ satisfying $0 \le c \le d$.  Call this "formula (*)".

Since the graph is guaranteed to be a dag, you can linearize it (topologically sort it).  Then, visit the vertices in topologically sorted order.  When you visit $v$, compute $f(v,d)$ for each possible $d$ using formula (*) -- this is possible because the topological sort ensures you will have computed $f(u,c)$ before visiting $v$.

There are $|V|$ possible vertices and at most $|V|$ possible values for the detail.  Calculating $f(v,d)$ can be done in $O(|V|)$ time, since the set $\text{pred}(v)$ has size at most $|V|$.  Therefore, the running time of this will be at most $O(|V|^3)$.

In practice, I expect the algorithm will be faster than that.  For instance, you only need to compute $f(v,d)$ for $d=0,1,2,\dots,\ell$, where $\ell$ is the length of the shortest path from $A$ to $v$.  Also, for most vertices, the size of $\text{pred}(v)$ will usually be much less than $|V|$ -- maybe more like $O(1)$.

Once you have computed $f(Z,0),f(Z,1),f(Z,2),\dots$, where $Z$ is the final node, then you can use all of that information to select which path you want.  For instance, if your criterion is "minimize erraticism, and break ties in favor of greater detail", you just compute $\min \{f(Z,d) : d=0,1,2,\dots\}$, resolving ties in favor of the larger $d$.  As another example, if you want to modify that criterion by ignoring all paths with detail 0, just ignore $f(Z,0)$.  Or, if you want to ignore all paths with detail 0 if there exists any path with detail $> 0$, then check whether any of $f(Z,1),f(Z,2),\dots$ are finite ($< +\infty$); if yes, then you ignore $f(Z,0)$.  And so on.  Hopefully you can see how to adapt the dynamic programming solution to handle many possible variations for the objective function.

For specific objective functions, there might well be even more efficient solutions -- but since it is not clear from your question at the time of writing just what objective function you want to minimize, I thought I would outline a general answer that works for a large class of possible objective functions.


Is a universal assembly language for all computers possible?

Assembly language is a way to write instructions for the computer's instruction set, in a way that's slightly more understandable to human programmers.

Different architectures have different instruction sets: the set of allowed instructions is different on each architecture.  Therefore, you can't hope to have a write-once-run-everywhere assembly program.  For instance, the set of instructions supported by x86 processors looks very different from the set of instructions supported by ARM processors.  If you wrote an assembly program for an x86 processor, it'd have lots of instructions that are not supported on the ARM processor, and vice versa.

The core reason to use assembly language is that it allows very low-level control over your program, and to take advantage of all of the instructions of the processor: by customizing the program to take advantage of features that are unique to the particular processor it will run on, sometimes you can speed up the program.  The write-once-run-everywhere philosophy is fundamentally at odds with that.


Permute an array in O(n) time with O(1) extra space with a given ordering function?

Reverse the last half of the array in-place and then apply one of the interleaving algorithms mentioned in this question.

That question is for even $n$, and I didn't check whether the answers work for odd $n$ as well. If they don't and it's needed you can do a left rotation to move the middle element to the end (its correct position) and then use one of the even-case algorithms to move the first $n - 1$ elements to their correct positions.


Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in $O(n\log(n))$?

After a bit more thinking, I realised it's actually doable in $O(n)$

If you normalise your hypercube onto the origin then to find the face the point lies on you simply need to find the axis of the point with the largest magnitude.

So, if the point is at $(0.2, 0.4, 0.7, 0.5)$, the point will be closest to the face facing in the positive z direction.


Can anyone give an example for worst case of quick sort if we employ median of three pivot selection?

If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also can anyone give an example including integers?

The worst case is when the selected pivot reduces the problem size by the smallest possible amount, i.e. provides as lopsided a partition as is possible.  For the median of three elements, that cannot be either the largest or smallest valued element (assuming distinct values), as the definition of median ensures that in median of 3, there is one larger and one smaller element than the median.

For the rather poor but all too common case of using the median of the first, middle, and last elements (with distinct valued input), that worst case occurs when the median of the three is the second-smallest or second-largest valued element (because the largest or smallest is one of the other two of those three).  That can occur when an in-order sequence of elements is rotated by just one position.  Here are two examples:

1 2 3 4 5 6 7 8 0 (median of 1,5,0 is 1)

8 0 1 2 3 4 5 6 7 (median of 8,3,7 is 7)

When median of first, middle, last pivot selection is combined with most commonly used partitioning methods, the result is disastrous; each partition peels off two elements (the pivot and one extreme value) and leaves another rotated sequence remaining.  The combination of first, middle, last pivot selection and a partitioning method which swaps the pivot to the first (or last) array position (rather common) is worse; it also generates rotated sequences when the input is reverse-sorted (e.g. 8 7 6 5 4 3 2 1 0).

See https://github.com/brucelilly/quickselect/blob/master/lib/libmedian/doc/pub/generic/paper.pdf and/or the video at https://www.youtube.com/watch?v=iWmAf4RMMiM for details and examples of some widely-used implementations that exhibit this behavior.

When input values are not distinct, another bad case for median of first, middle, and last elements is "organ-pipe" (bitonic) input, such as

0 1 2 3 4 3 2 1 0 (median of 0,4,0 is 0)

In the case of organ-pipe input, use of first, middle, and last elements is the worst possible choice of three elements for pivot selection!


Formal grammar with constraints on the number of each symbol

No.

Since the permutation language is finite, you can produce a grammar by enumerating the individual sentences which comprise the language. Some simplifications are possible, for example by finding common prefixes and/or suffixes. But there is no grammar which is significantly smaller than the language itself (for some definition of "significantly").

This is not really as dramatic a conclusion as it sounds. Most finite languages lack compact grammars; grammars achieve concision when they can use recursive constructs which represent infinite languages.

In fact, in an interesting paper cited in the answer to this question on https://cstheory.stackexchange.com/, there's a proof that the no regular expression for the language $P_n$ consisting of the permutations of $\{1,2,\dots,n\}$ can be shorter than $2^n$. However, the (infinite) inverse $\overline{P_n}$ can be described by a regular expression of size $O(n^2)$. (There are lots of other interesting results in that paper.) @yuval-filmus extended that result in Lower Bounds for Context-Free Grammars to a larger set of languages, including the language of permutations of the multiset of $n$ different elements in which each element appears $k$ times.

In the halcyon era of SGML, whose syntax description language included a permutation operator, there was some investigation into how to optimise state machines to recognise such languages. IIRC, the final conclusion was that it can't be done and therefore the permutation operator is not a good idea. In practice, such languages are generally recognised in two phases: first, the input is matched against the infinite language of unrestricted repetitions, and then a second scan (not implemented with a CFG) is done to count repetitions of each element. But that algorithm is not completely sound. First, it assumes that there is a unique decomposition of a string into elements, which is not always the case, although it certainly was the case for SGML. Second, the algorithm greedily processes all successive elements. If the intention of the grammar were to recognise the longest legal permutation, leaving open the possibility that (over-)repeated elements be part of a different syntactic construct, then legal inputs will fail because of the greediness.


Detect non existence of a cycle in a graph using Datalog : SMTLIB Format for Z3

I don't think you can do it in plain Datalog, but you can do it in Datalog plus negation.

I suggest you define a relation $R$, so that $R(x,y)$ is true if vertex $y$ is reachable from vertex $x$ in one or more steps.  You can define $R$ recursively, namely,

$$R(x,y) = E(x,y) \lor \exists w . E(x,w) \land R(w,y),$$

where $E$ is a relation that represents the edges in the graph ($E(x,y)$ is true iff $(x,y)$ is an edge in the graph).  Now the graph has a cycle iff $\exists x . R(x,x)$ is true.  I think you should be able to translate this in Datalog.

From this you can get a Datalog instance that is satisfiable if there is a cycle in the graph, or unsatisfiable if there is no cycle.

If you want the reverse (an instance that is satisfiable iff there is no cycle), I think you need negation.

The details of how to express that in Z3 code seem off-topic here.


Sort array of duplicate integers in place

Use Radix sort. The time complexity is O(kn) and space complexity is O(k + n) . Here n is the number of elements and k is the number of bits required to represent largest element in the array.


Why does Akra-Bazzi need that toll-function g is bounded?

Take a look at Tom Leighton's notes, referenced from the Wikipedia article.
His notes apparently have less typos then the original paper. The condition he demands of $g$ is having polynomial growth, which means that if you scale the argument by a constant, then the amount that the function scales is also bounded by a constant.


The time complexity of the Wikipedia version of Pollards $(p-1)$ algorithm

As you mention, the costliest step is computing $a^M \bmod{n}$. This is done using the repeated squaring algorithm. Each squaring or multiplication modulo $n$ takes time $M(n)$, where $M(n)$ is the time complexity of multiplication.

We can estimate the number of multiplications by
$$
\sum_{\text{prime } q \leq B} \frac{\log B}{\log q} \cdot \log q < \pi(B) \log B = O(B).
$$
This improves slightly on the Wikipedia estimate of $O(B\log B)$.

The school multiplication algorithm takes time $O(\log^2 n)$, which is how Wikipedia got that factor. But nowadays faster algorithms are known, which run in time $\tilde{O}(\log n)$. So a better estimate on the complexity is $\tilde{O}(B\log n)$.


Converting Regular expression to DFA by building syntax tree

No, using complementation yields an exponential blow-up in the size of the DFA.