Proving a set is at a certain level of the arithmetical hierarchy

In order to show that a language is in (say) $\Sigma_n^0$ but not in $\Sigma_{n-1}^0$ or $\Pi_{n-1}^0$, we show that the language is complete for $\Sigma_n^0$. Since the arithmetical hierarchy is strict (by a generalization of the proof of the uncomputability of the halting problem by diagonalization, which you can find in many different sources), a $\Sigma_n^0$-complete language cannot be in any lower level of the hierarchy.

How do we show that a language is complete for a level of the hierarchy? Either by a direct proof or by reduction. Let me illustrate both techniques using variants of the halting problem.

We will consider two variants of the halting problem:

$H_1$ consists of all pairs $(\langle M \rangle, x)$ such that $M$ is a Turing machine halting on $x$.
$H_2$ consists of all singletons $\langle M \rangle$ such that $M$ is a Turing machine halting on an empty tape.

Let us show that $H_1$ is $\Sigma_1^0$-complete by a direct proof. In order to show that it is in $\Sigma_1^0$, we notice that $(\langle M \rangle,x)$ iff there exists $t$ such that $M$ halts on $x$ within $t$ steps; the latter predicate is computable.

In order to show that $H_1$ is $\Sigma_1^0$-hard, consider any language $L \in \Sigma_1^0$. By definition, there exists a computable predicate $P$ such that
$$ x \in L \Longleftrightarrow \exists y \, P(x,y). $$
Let $M$ be a Turing machine that on input $x$, enumerates all strings $y$ (say first by length, then lexicographically), for each one computes $P(x,y)$, and halts if $P(x,y)$ holds for any $y$. Then $x \in L$ iff $(\langle M \rangle, x) \in H_1$. The mapping $x \mapsto (\langle M \rangle, x)$ is clearly computable, and so this reduces $L$ to $H_1$.

We now show that $H_2$ is $\Sigma_1^0$-complete by reduction from $H_1$. Given an instance $(\langle M \rangle, x)$, we construct (in a computable way) a new machine $M_x$ that first initializes the tape $x$, and then transfers control to $M$. Clearly $(\langle M \rangle, x) \in H_1$ iff $\langle M_x \rangle \in H_2$. Since the reduction is computable and $H_1$ is $\Sigma_1^0$-hard, this shows that $H_2$ is also $\Sigma_1^0$-hard. Also, $H_2 \in \Sigma_1^0$, using the same proof as above. So $H_2$ is $\Sigma_1^0$-complete.


Find most stable combination of a vector with itself at different periods

Made up rule nr 1: Every number has to be part of the sum. Therefore the sum cannot be x, if there is a number b, such that no combination of numbers can add up to x-b.

So for [0, 0, 2, 3, 2]:

the sum cannot be 2 (because 3 cannot be part of that)
it cannot be 3 (because 3 - 2 = 1 and there is no combination of numbers that add
up to 1 (rule 1))
it cannot be 4 (because 4-3 = 1 again, (rule 1))
it cannot be 5 (because there are twice as many 2-s as 3-s)
it cannot be 6 (because in case of 3-s, only two rows in exactly the
same place can make up that number, and the 2-s would then form 4-s,
which cannot sum up to 6)

Therefore for the specific case of [0, 0, 2, 3, 2], the simplest solution is to have the value of 7

Perhaps this complicated reasoning helps to consider the future vectors as well :)

[0, 0, 2, 0, 3, 0, 4, 0, 2] is more difficult though. While not considering too thoroughly, it looks like for that as well, there isn't anything better than the trivial solution.

Trivial solution:

[a, b, c ....]
   [a, b, c ....]
      [a, b, c ....]
      ...


Direct reduction from Near-Clique to Clique

Let $(G,k)$ be an instance of Near-Clique, construct an instance $(G',k')$ of Clique as follows.

For each $uv \notin E(G)$, add to $G'$ a subgraph corresponding to $(N(u)\cap N(v))$, i.e.,

for each $x \in N(u)\cap N(v)$ add the vertex $x'$ to $V(G')$, and
for each edge pair of vertices $x,y \in (N(u)\cap N(v))$ if $xy \in E(G)$ add the edge $x'y'$ to $E(G')$.

Set $k' = k-2$

As $uv \notin E(G)$, $u \notin N(v)$ and $v \notin N(u)$. Note that each of these corresponding subgraphs is disjoint, so a vertex in $G$ may have several corresponding vertices in $G'$.

Now we claim that $(G,k)$ has a $k$-near-clique iff $(G',k'=k-2)$ has a $k'$-clique.

$(\Rightarrow)$ Let $D$ be the vertices of the near clique, then there are two vertices $u,v \in D$ such that

$uv \notin E(G)$,
$D\setminus\{u,v\}$ forms a clique of size $k-2$, and
$D \subseteq N(u)\cap N(v)$ (by definition).

Then $G[D\setminus\{u,v\}]$ (the subgraph induced by $D$) is a subgraph of $G'$ (via the construct and property 3). Therefore by property 2, $G'$ has a clique of size $k-2=k'$.

$(\Leftarrow)$ Let $C'$ be a $k'=k-2$ size clique in $G'$ and let $C$ be the corresponding vertices in $G$ (with induce a $k-2$-clique in $G$ as well). By the construction, there must exist $u,v\in V(G)$ such that $C\subset N(u)\cap N(v)$ (i.e. $u$ and $v$ are adjacent to all the vertices of $C$), moreover $uv \notin E(G)$. Therefore $C\cup\{u,v\}$ forms a $k$-sized near-clique in $G$.

The last step is to just assure ourselves that this is polynomial-time computable. In constructing $G'$, we examine at most each pair of vertices, and compute the intersection of their neighbourhoods. Just so we don't have to think too hard about details, that is at most $n^{2}$ neighbourhoods, and for each we take $O(n^{2})$ time to compute the intersection. So the total construction can be enacted in polynomial-time.


Propagating node labels upwards in a tree

I understand your problem as follows (the best I could make of your presentation of it).

You have a tree rooted in node B. Each leaf is labeled wih
categories. Each other node is labeled with the categories of all
leaves below that node. The problem is to maintain proper labeling of
all nodes, when changing the labels of leaves or adding or removing
nodes from the tree.

The problem is easy when categories are added. You only have to
propagate new categories from where they are added up to the root.
The addition can come from adding a category to a leaf, or adding a
new node with its own categories as a leaf, or with the categories of
its daughters if it is an intermediate node.

The difficulty comes from removing categories, either by removing them
from a leaf, or by removing a node and all the nodes below it. The
difficulty comes from the fact that the categories it propagated
upward may still have to be kept somewhere on the path, because they are
provided by some other nodes.

However, this can be addressed very simply. Just keep a count of how
many times a category is provided to a node from the leafs below that
node. Then both addition and removal require only a bit of accounting.
You remove a category from the labeling of a node when its count falls to zero for that node.

Time complexity

The complexity analysis below is added by an edit from Billiska. It can only be partial since the OP did not clearly state how the structure is to be used. In particular, it seems that he also intends to add or remove whole subtrees. But the information needed for the purpose is available from the root of the subtrees (assuming categories have been propagated beforehand in subtrees to be added), so that operating on whole subtrees is very similar to operating on leaves.

Let the tree have depth of $d$.

Look-up category of a given node is $O(1)$ since the category information is always stored up-to-date for each node.

Add a category to a given leaf node is $O(d)$ since the count of that category has to be incremented for every ancestor node up to the root.

Remove a category from a given leaf node is $O(d)$. Just the revert of add, we decrements the count of that category for every ancestor node up to the root.


Can a KD tree be used as a decision tree through nearest neighbor queries?

Yes, you can.  The scheme you are thinking of is called the nearest-neighbors classifier.  Read the link for more details.  In many settings it turns out to be a quite effective classification algorithm.


What are the applications of Rose trees?

You seem to have an overly "data structures and algorithms" mindset.  Not every tree is some kind of search tree.  Data structures are often designed to correspond to or capture aspects of a domain model.

S-expressions are almost exactly rose trees. (Or rather, I would say how they are typically thought of is as rose trees.  Wikipedia is correct in saying they are more like binary trees, but what you might call "proper" S-expressions are only slightly different from rose trees.)  At any rate, you can use them as a generic representation for an abstract syntax tree.  The benefit of doing this is that you can easily write generic operations, e.g. "find all variables" or "swap parameters" or "rename this symbol".  It's also extensible in that adding a new type of node to your abstract syntax often doesn't require really changing anything.  The downsides are there aren't really any constraints, so it doesn't a priori prevent you from writing nonsense.  This can be mitigated for users by standard abstract data type techniques, but the implementer of transforms and such must deal with the unstructured representation even though they "know" that the input is structured via a data type invariant.  Of course, when that certainty is misplaced (possibly because things have changed), the errors tend to be unpredictable and hard to debug.

In practice, while the Data.Tree module in the standard libraries provides a rose tree, almost no one uses it in the Haskell community.  Defining custom data types that explicitly capture the constraints is so easy that there is little reason to use a generic library type.  Further, there has been an enormous amount of research and practice around performing generic operations over custom types which eliminates many of the benefits of using a generic representation.  Finally, Haskellers tend to be very much in favor of explicit, enforced constraints and are willing to pay to get it.

To answer your last question, oftentimes searching an AST is unimportant and/or the ASTs are generally assumed to be small enough that just walking the whole thing is acceptable.  Admittedly, it's not uncommon to collect definitions in a separate data structure with references into the AST which could be viewed as a sort of index.  Similarly, some optimization passes will (usually locally and temporarily) build up indexes to simplify and speed up their operation.  The structure of the AST corresponds to the input and so it can't be "rebalanced" or anything like that.  As such, it's uncommon for the AST itself to contain indexing information or information to help "searching".


PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$

Let me prove a more general theorem.

  For $A \subseteq \mathbb{N}^2$, the language $L(A) = \{a^i b^j : (i,j) \in A \}$ is context-free iff $A$ is semi-linear.

One direction is Parikh's theorem. In the other direction, it suffices to show that $L(A)$ is context-free if $A$ is linear (since every semi-linear set is a union of linear sets). Indeed, suppose that $A = (i_0,j_0) + \sum_{t=1}^m \mathbb{N} (i_t,j_t)$. Then $L(A)$ is generated by the grammar
$$
S \to a^{i_0} b^{j_0} \mid a^{i_1} S b^{j_1} \mid \cdots \mid a^{i_m} S b^{j_m}.
$$

A classical result shows that a set is semi-linear iff it is definable in Presburger arithmetic. In particular, if $A$ is the solution set of a system of linear inequalities with rational coefficients (as in your example) then $A$ is semi-linear and so so $L(A)$ is context-free.

In your particular case, ignoring for the moment the condition $i > 0$, we have
$$ A = \{ (i,j) : 2i \leq 2j \leq 3j \} = \mathbb{N}(1,1) + \mathbb{N}(2,3). $$
Indeed, clearly $(1,1),(2,3) \in A$ and $A$ is closed under addition, and so $\mathbb{N}(1,1) + \mathbb{N}(2,3) \subseteq A$. In the other direction, suppose that $2i \leq 2j \leq 3i$. Then
$$
(3i-2j)(1,1) + (j-i)(2,3) = (i,j).
$$
This shows that the following grammar generates your language without the condition $i > 0$:
$$ S \to \epsilon \mid aSb \mid a^2Sb^3. $$
If we bring back the condition $i > 0$, then we get the decomposition
$$
A = \{ (i,j) : 2i \leq 2j \leq 3j \text{ and } i > 0 \} = \{(1,1) + (2,3)\} + \mathbb{N}(1,1) + \mathbb{N}(2,3),
$$
leading to the grammar
$$
S \to ab \mid a^2b^3 \mid aSb \mid a^2Sb^3.
$$

In these examples all linear sets were generated by two vectors ("periods"). Indeed, a classical result (following from Caratheodory's theorem; see for example Slide 24 of these slides by Widjaja Lin) shows that every semi-linear set in dimension $k$ (in our case, $k=2$) is the union of linear sets with at most $k$ periods.

If you are interested in the algorithmic side of things, The taming of the semi-linear set is a good starting point.


Transform unstructured flow charts into structured ones

Yes.  This has been studied in the research literature under the name "goto removal" or "goto elimination": it is the problem of taking a program with gotos, and removing the gotos.

This became of interest after structured programming became more popular; one simplistic interpretation of structured programming was that you shouldn't use gotos.  See also the structured program theorem.

If you search for "goto elimination" on Google Scholar, you will find a number of papers that discuss this topic, and from there you should be able to find many more.


Computing 3SUM problem in $O(n\lg n) + \frac{n^2}{4}$ time

There are known algorithms that take strictly less than $O(n^2)$ time (i.e., they run in $o(n^2)$ time), under certain theoretical computational models.  See, e.g.,

Subquadratic Algorithms for 3SUM.  Ilya Baran, Erik D. Demaine, Mihai Patrascu.

However, it is not clear to me whether this leads to a practical improvement in real implementations.

Did you do a literature search for work on the 3SUM problem?  The above paper immediately comes up as soon as you search for "3SUM" on Google Scholar.  On this site, we expect you to do your own research first before asking here, and to show what you've tried in your question.  Please make sure to read the help center to learn more about how this site works.  You might want to do a literature search, including reading the relevant references cited in the paper above, then editing your question to reflect this research -- or adding an answer to answer your own question.


Word-hyphenation algorithm for monospaced fonts

I assume you are asking about algorithms to decide where to split lines when formatting paragraphs, not about algorithms for deciding where it is legal to insert hyphens into a word?

All algorithms for this kind of problem go back to Knuth, Donald E.; Plass, Michael F. (1981), "Breaking paragraphs into lines", Software: Practice and Experience 11 (11): 1119–1184, doi:10.1002/spe.4380111102, which is also described in this entry on tex.stackexchange: https://tex.stackexchange.com/a/109818/28084.

The key is to define an objective function and then come up with an efficient algorithm for optimizing the objective function.  Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3/e, 2009 gives a super-simplified version in problem 15-4 (page 405) that asks you to minimize the objective function "sum of cubes of number of extra spaces required on each line" using an efficient dynamic programming formulation.

In Knuth and Plass they demonstrate that a bunch of variants of the objective function (including adding a linear penalty for each hyphenation break that is added, and accounting for the extra space consumed by the hyphen) don't require you to go beyond the efficient dynamic programming formulation.


Is machine epsilon the largest relative error in representing a number as a floating point number?

In the most common usage, and in particular in IEEE-754, machine epsilon is the smallest number $\epsilon$ such that $1 + \epsilon \ne 1$.
It does have an interpretation in terms of relative distance between numbers: It is the largest relative separation of two consecutive normal numbers.
There are a couple of important points to understand here:

This is only about normal numbers, as opposed to subnormal numbers (i.e. what older standards called "denormal numbers").
It is about consecutive numbers, namely, some floating point number and its closest neighbour.
Machine epsilon measures separation, not error. It is the relative distance between those floating-point numbers, not the relative error between a floating point number and anything.

So if $x_1$ and $x_2$ are consecutive normal numbers, then:
$$0.5\epsilon \le \frac{|x_2 - x_1|}{\max(|x_1|,|x_2|)} \le \epsilon$$
So if you have a candidate real number, and you want to represent it as a floating-point number, how bad can the relative error be?
As gnasher729 rightly pointed out, it can be as large as you want if the real number would overflow, underflow, or be subnormal. But assuming that it's in a reasonable range, meaning that it is between two consecutive normal numbers, then one of those normal numbers is within $0.5\epsilon$ of it in a relative sense.
Because this is a fraught definition, the term that we usually use is "units of last place", or "ulp" for short. If a real number is within the normal number range, there is a floating point number whose error is at most 0.5ulp.


Here are some examples of slightly different approaches:

Hash-table

Key into hash-table is a vertex, value is a list of vertices it is connected to, the edge is thus a relation between the key and the element of the value in the hash-table.  This is not so different from adjacency list except that testing for presence of the vertex will be faster, but it will take more spece to store the graph.

This, obviously, describes a directed graph.  You could include the reversed edges to make it work as undirected graph.

Example (JavaScript):

function graph() {
    var vertices = {}, g = { vertices: vertices };
    g.getVertex = function (vertex) {
        return vertices[vertex];
    };
    g.getEdge = function (from, to) {
        var adjacent = vertices[from], result;
        if (adjacent.indexOf(to) > -1) result = [from, to];
        return result;
    };
    g.addEdge = function (from, to) {
        var edges = vertices[from] || [];
        edges.push(to);
        vertices[from] = edges;
    };
    [].slice.call(arguments).forEach(function (edge) {
        g.addEdge.apply(g, edge);
    });
    return g;
}
graph([1, 2], [1, 3], [2, 1], [2, 3], [3, 5], [3, 6], [3, 4],
      [4, 7], [5, 2], [5, 6], [6, 3], [6, 7]);
// { vertices:
//    { '1': [ 2, 3 ],
//      '2': [ 1, 3 ],
//      '3': [ 5, 6, 4 ],
//      '4': [ 7 ],
//      '5': [ 2, 6 ],
//      '6': [ 3, 7 ] },
//   getVertex: [Function],
//   getEdge: [Function],
//   addEdge: [Function] }

Graph-proper data structure

We define vertex as a tuple of the value and a list of edges from this vertex to other vertices it is directly connected to.  This is a little bit more compact than the hash-table, but testing whether vertex is in a graph becomes linear (just as in adjacency list / matrix).  Same as before we can add edges in the opposite direction to make this graph undirected.  This is different from adjacency list in that retrieving all adjacent vertices to a given vertex is a constant time operation, while in the list it is linear in time.  Adjacency matrix would also give constant time for this, but will use more space, especially if a graph is sparse.

Example (Prolog):

:- use_module(library(record)).

:- record vertex(value, arcs=[_ | _]).

lookup(X, [X | _]).
lookup(X, [Y | Xs]) :- X \== Y, lookup(X, Xs).

instantiated(Goal, [X | _], []) :- \+ call(Goal, X).
instantiated(Goal, [X | Xs], [X | Ys]) :- call(Goal, X), instantiated(Goal, Xs, Ys).

vertex_instantiated(Vertex) :-
    make_vertex([], Vertex),
    vertex_value(Vertex, Value),
    ground(Value).

find_vertex_helper(Value, _, Vertex) :- vertex_value(Vertex, Value).
find_vertex_helper(V1, Cache, V2) :-
    vertex_arcs(V2, Arcs),
    instantiated(vertex_instantiated, Arcs, InstArcs),
    subtract(InstArcs, Cache, FilteredArcs),
    union(Cache, InstArcs, NewCache),
    findnsols(1, V, (member(V, FilteredArcs),
                     find_vertex_helper(V1, NewCache, V)),
              [V2]).

find_vertex(_, [], _) :- !, fail.
find_vertex(Value, [V | Graph], Vertex) :-
    vertex_value(V, Value), Vertex = V
    ;
    vertex_arcs(V, Arcs),
    instantiated(vertex_instantiated, Arcs, InstArcs),
    include(find_vertex_helper(Value, []), InstArcs, [Vertex])
    ;
    find_vertex(Value, Graph, Vertex).

find_or_create_vertex(Value, Vertex, Graph, Graph) :-
    find_vertex(Value, Graph, Vertex), !.
find_or_create_vertex(Value, Vertex, OldGraph, [Vertex | OldGraph]) :-
    make_vertex([value(Value)], Vertex).

add_arc(From, To, OldGraph, NewGraph) :-
    find_or_create_vertex(From, VertexFrom, OldGraph, Graph1),
    find_or_create_vertex(To, VertexTo, Graph1, NewGraph),
    vertex_arcs(VertexFrom, Arcs),
    lookup(VertexTo, Arcs).

make_graph_helper([], Graph, Graph).
make_graph_helper([From-To | Vs], GraphIn, GraphOut) :-
    add_arc(From, To, GraphIn, NewGraph),
    make_graph_helper(Vs, NewGraph, GraphOut).

make_graph(Vs, Graph) :- make_graph_helper(Vs, [], Graph).

make_graph([x1-x2, x1-x3, x2-x1, x2-x3, x3-x5, x3-x6, x3-x4,
            x4-x7, x5-x2, x5-x6, x6-x3, x6-x7], G).
/*    G = [vertex(x7, [_G3910|_G3911]),
           vertex(x4, [vertex(x7, [_G3910|_G3911])|_G3891]),
           _S1, _S2,
           vertex(x3, [_S2, _S1, vertex(..., ...)|...]),
           vertex(x2, [_S3, vertex(..., ...)|...]), _S3],
           % where
          _S1 = vertex(x6, [...]),
          _S2 = vertex(x5, [...]),
          _S3 = vertex(x1, [...]) */


Proof Idea: How to prove the intersection of regular language and CFL is a CFL?

Look at the product construction for DFAs, it will give you a hint of what the state space of a PDA accepting the intersection will look like.
You can convert $D$ to a PDA, but you have more information than that. It doesn't need to touch the stack at all, since it can be accepted by a DFA.

These should get you close to the answer.


Is the minimum weight independent dominating set np-complete in chordal graphs?

As the article clearly mentions, unweighted minimum independent dominating set can be solved efficiently (in fact, linear time) for chordal graphs. A glance at the paper shows that this works even if the vertices are given $\{0,1\}$ weights (rather than all having unit weight). On the other hand, weighted minimum independent dominating set is NP-complete.


You say in a comment:

  I am interested in combination problems that contain-distribution of distinct/indistinct objects to distinct/indistinct people,also with type of partition not defined,unordered partition etc advanced level problems

It doesn't sound to me like you want a book that covers all of combinatorics. Combinatorics is a vast subject, which includes enumerative combinatorics, probabilistic combinatorics, extremal combinatorics, graph theory, and several other subdisciplines. It sounds to me like you are interested in a subarea of enumerative combinatorics.

Richard Stanley's two-volume series on enumerative combinatorics is quite good, and I suspect it contains the material you want.


Let us assume that $P$ is in general position (no three points colinear, no four points cocircular) to make things easier.

As the Voronoi diagram is the dual of the Delaunay triangulation, this is the same as asking if the edge $xy$ is in the Delaunay triangulation of $P$.

You might know the following characterisation:

  An edge $(a,b)$ is in the Delaunay triangulation of $P$ if and only if there is a disk whose boundary passes through $a$ et $b$ containing no other point of $P$ on its boundary or in its interior.

So let us take a look at the edge $(x,y)$ and let us draw the circle/disk whose diagonal is $(x,y)$.

Notice that if any point other than $x$ or $y$ is in the disk, then it is closer to both $x$ and $y$ then they are to each-other. Thus there is no such point in $P$, as it can't be red nor blue by definition of $(x,y)$. So this disk contains no other point of $P$, which means $(x,y)$ is an edge of the Delaunay triangulation, thus it is an edge of the Voronoi Diagram.

(There was no real need to make a detour through Delaunay triangulations as by duality the characterisation works just as well for Voronoi diagrams but I have always seen that characterisation stated in terms of Delaunay triangulations)


The algorithm in the question can be stated more clearly in the following form since considering the odd $i$ does not have any effect once $i-1$ has been take care of.

for even i from 0 to 2N-2:
    if array[i] and array[i+1] does not constitute a pair:
        find the pair for the i-th one and swap position with i+1 element

Here is an outline of the proof.

Given an array $A$ of size $2N$ with integers ranging from $0$ to $2N-1$, let us construct a graph $G$. Replacing $2i-1$ with $2(i-1)$ for all $i$, we will have a new array $B$ of even integers from $0$ to $2(N-1)$, each of which appears twice. Let $G$ have vertices $0, 2, \cdots, 2(N-2)$.

If $B[0]=2i$ and $B[1]=2j$, we will add an edge between $2i$ and $2j$ in $G$.
If $B[2]=2i$ and $B[3]=2j$, we will add an edge between $2i$ and $2j$ in $G$.
$\cdots$
If $B[2N-2]=2i$ and $B[2N-1]=2j$, we will add an edge between $2i$ and $2j$ in $G$.

Please note since $2i$ might be the same as $2j$, $G$ may have self-loops. Since each even number appears twice in array $B$, the degree of each of vertices of $G$ is 2 (2-regular graph). That means $G$ is a disjoint union of cycles.

Define a function $s$ from arrays which are permutations of $0, 1, \cdots, 2N-1$ to $\Bbb N$, $s(A)=$ the number of cycles in $G$, where $G$ is obtained from $A$ by the above deterministic construction.

Claim (at most 1 increase with one swap). Suppose an array $A$ is changed to $A'$ by a swap of two elements. Then $s(A')\le s(A)+1$.

Suppose we have proved the claim. Notice that $s(A)=N$, the maximum value of $s$ if and only if all pairs are next to each other. Since you can only increase at most 1 to $s(A)$ by each swap and the greedy algorithm does increase $s(A)$ by 1 with each of its swaps, the greedy algorithm must be optimal.

I will leave the gaps in the above proof as two easy exercises.

Exercise 1: The greedy algorithm increase the value of $s$ by 1 with each of its swaps.

Exercise 2: Prove the claim of at most 1 increase with one swap.


How does one enter in a boolean expression into an SAT solver?

Typically, the huge SAT instance is generated by a reduction from some other problem, so it's computer-generated in the first place.  You write it to a file and tell the SAT solver to read it.


Does every infinite context free language contain an infinite regular subset?

No.

A counterexample is simply $E=\{a^nb^n\mid n\ge0\}$, the classic context-free language that is not regular.

For the sake of contradiction, suppose $E$ has an infinite regular subset $S$. So $S$ satisfies the pumping lemma for regular languages. Suppose $p\ge1$ is a pumping length of $S$. Since $S$ is infinite, $w=a^mb^m \in S$ for some $m\ge p$. Since $|w|=2m\gt p$, $w$ can be written as $w=xyz$, satisfying the following conditions:

$|y| \geq 1$
$|xy|\leq p$
$\forall n\geq 0$, $xy^{n}z\in S$

Since $|xy|\le p$ and $w$ starts with at least $p$ $a$'s, $y=a^k$ for some $k\ge1$. Since $xz=xy^0z$ has less $a$'s than $b$'s, $xz\not\in S$. This contradiction shows that $S$ is not regular. That is, no infinite subset of $E$ is regular.

What we just showed above is the fact that given any language, if every word in it cannot be pumped as in the pumping lemma for regular languages, then that language does not contain an infinite regular subset.

Here is a related exercise.

Exercise. A language is called prefix-closed if all prefixes of every string in the language are also in the language. Let $P$ be an infinite, prefix-closed, context-free language. Show that $P$ contains an infinite regular subset.


It's not tautological at all.

A model of computation is Turing-complete if it can simulate all Turing machines, i.e., it is at least as powerful as Turing machines.

One thing that Turing machines can do is simulate other Turing machines (via the universal Turing machine). That means that, if your model of computation can't simulate Turing machines, it can't do at least one thing that Turing machines can do, so it doesn't satisfy the definition, so it isn't Turing complete.  There's no circularity because we didn't define Turing-completeness in terms of itself: we said that Turing-completeness is the property of being able to do everything that Turing machines can.

But there are plenty of other things that models of computation might fail to do. For example, no deterministic finite automaton (DFA) can recognize the class of strings consisting of some number of $a$s followed by the same number of $b$s. Turing machines, on the other hand, can recognize that class of strings. Hence, DFAs are not Turing-complete.

  Is there a way to define the capabilities of Turing Machine without just saying "being able to simulate another Turing Machine"?

I'm not sure what you mean by "define the capabilities of Turing machines". The capabilities are defined in terms of the finite state automaton operating on the infinite tape. (I'll not repeat the full definition but you can find it, e.g., on Wikipedia.)


Are permutations of context-free languages context-free?

Start with simple context-free (or even regular) languages, and see what happens. For instance determine $p(L)$ for $L = (ab)^*$ and $L=(abc)^*$.


Binomial coefficient to approach multi-way choices DP problem?

The binomial coefficient here appears through the formula
$$
\sum_{i=1}^{n-1} i = \binom{n}{2}.
$$
In the formula, $OPT(j)$ is the minimal cost of a solution for the first $j$ servers. Another way of looking it that it's the minimal cost up to $j$ of a solution which puts the file in $S_j$.

Where does the recurrence come form? Take an optimal solution for the first $i$ servers. We know that the file appears in $S_j$. Let $S_i$ be the next largest server it appears on (or $i=0$ if it only appears in $S_j$). Without loss of generality, we can assume that the solution restricted to $S_1,\ldots,S_i$ is optimal, and so of cost $OPT(i)$. Putting the file in $S_j$ costs $c_j$. Accessing the file at positions $i+1,\ldots,j-1$ costs $(j-(i+1)) + \cdots + (j-(j-1)) = \binom{j-i}{2}$. This gives the recurrence formula. (We also have to verify the case $i=0$ separately, which I leave to you.)


Enumerate over all halting Turing Machines?

The paper you're referring to is using "enumeration" just to mean "ordered list". Your feeling that such a list can't be computed by a Turing machine is correct. However, the list exists, even though there's no algorithm that will tell us what its members are.

Also, note that it refers to "an enumeration of halting Turing machines", not "an enumeration of the halting Turing machines". So it's just any ordered list of halting Turing machines, not necessarily all of them. It specifically mentions enumerations of polynomial time Turing machines. You might be surprised that these are enumerable, up to equivalence*. This is because you can turn any Turing machine into a polynomial time Turing machine by picking your favourite polynomial and modifying the machine so it rejects if it hasn't in that many steps. Since you can enumerate all polynomials (say, with nonnegative integer coefficients), and you can enumerate all Turing machines, you can combine the two to enumerate all polynomial time Turing machines.

* Two Turing machines are equivalent if they give the same output for every input.


Algorithm to partition students in two groups maintaining brotherhood (related to COVID19 pandemic)

The very general problem is (weakly) NP-complete if you want the optimal solution, however, in general there aren't arbitrarily large sibling cliques.

The problem can always be modeled as an integer linear program (ILP).

If you just want a good enough solution, then I would start with a greedy algorithm, followed by local search.  You can always keep the local search (with random restarts) running over the night in hope for ever better solutions.

Since you seem to have added some more constraints in comments, if the constraints are really hard constraints, you can consider using an off-the-shelf ILP solver.

For illustrative purposes, I picked the first I could (cvxpy) find in a programming language I am familiar with (Python).  I am not familiar with ILP solvers, so I have no idea if this is a good choice.  (Note that it is not actually a solver, but an interface for several solvers.)

So I wrote a short example just to get you started.  It can be done in about 50 lines.

There are $2 \cdot N$ variables:

$N$ variables representing the $N$ students
$N$ variables representing their genders (linked through a constraint)

There are two constraints:

siblings need to be in the same partition
a helper-constraint to make the balancing of genders simpler

The optimization is basically to optimize (minimize)

$$2 \cdot (N/2 - \sum{s})^2 + (N/2 - \sum{g})^2,$$

where $\sum{s}$ is the number of students put in partition 0 and $\sum{g}$ is the number of girls put in partition 0.

caveat emptor

from collections import namedtuple, Counter
import random
import cvxpy as cp

Student = namedtuple("Student", "name level gender")

def generate_students(N=100):
    # generate random data
    students = [Student(i, 1, random.choice("MF")) for i in range(N)]

    siblings = []
    for i in range(0, N // 2, 3):
        siblings += [(i, i + 1), (i, i + 2), (i + 1, i + 2)]
    return students, siblings

def create_variables(students):
    """Return stud_var and gender_var.

    These will be constrained to be set to the same value, i.e.

    stud[i] == gender[i].

    This is to ensure that we can easily count gender-difference in
    addition to "normal" difference.

    """

    stud_vars = [cp.Variable(1, boolean=True) for s in students]
    gender_vars = [cp.Variable(1, boolean=True) for s in students]
    return stud_vars, gender_vars

def create_constraints(stud_vars, gend_vars, students, siblings):
    stud_const = [stud_vars[l] == stud_vars[r] for (l, r) in siblings]
    link = [stud_vars[i] == gend_vars[i] for i in range(len(stud_vars))]
    return stud_const

def create_objective(stud_vars, gend_vars):
    mid = len(stud_vars) // 2
    objective = cp.Minimize(
        2 * (mid - cp.sum(stud_vars)) ** 2 + (mid - cp.sum(gend_vars)) ** 2
    )
    return objective

students, siblings = generate_students()
stud_vars, gender_vars = create_variables(students)
constraints = create_constraints(stud_vars, gender_vars, students, siblings)
objective = create_objective(stud_vars, gender_vars)
prob = cp.Problem(objective, constraints)

result = prob.solve()
if result is None:
    exit("Could not find feasible solution.")

print(round(result))
print(Counter(int(round(e.value[0])) for e in stud_vars))

def get_gender_count(partition):
    lst = [
        students[idx].gender
        for (idx, s) in enumerate(stud_vars)
        if round(s.value[0]) == partition
    ]
    return Counter(lst)

print("Partition 0:", get_gender_count(0))
print("Partition 1:", get_gender_count(1))

# for idx, e in enumerate(stud_vars):
#    print(students[idx], "\tPartition", int(round(e.value[0])))

for (l, r) in siblings:
    lv = int(round(stud_vars[l].value[0]))
    rv = int(round(stud_vars[r].value[0]))
    assert lv == rv

Running the snippet output:

(e375) [ubuntu ~/textnik]$ time python textnik.py
297.0
Counter({0: 52, 1: 48})
Partition 0: Counter({'F': 27, 'M': 25})
Partition 1: Counter({'F': 25, 'M': 23})

real    0m4,060s
user    0m4,926s
sys 0m1,189s

meaning that it put 52 students in one group and 48 in the other, with 27/25 F/M in the first group and 25/23 F/M in the other group.

All the siblings should be in the same group by constraints.


Prove that the coding $\pi_k$ is effective

Since $\pi_k$ is bijective, for every $x∈N$, there exists a unique tuple $(x_1, ..., x_k)∈N^k$ such that $\pi_k(x_1,...,x_n) = x$. So, how can we define $J^k_i$ ? A solution would be to use a coding that is already known to be effective, let $\alpha_k$ be that effective coding and $\beta^k_1,..., \beta^k_k$ the associated decoding functions. Let $x∈N$, we can put : $$J^k_i(x) = \beta_i^k(\mu y(\ \pi_k(\ \beta^k_1(y)\ , ...,\ \beta^k_k(y)) = x))$$

For $\alpha_k$, we can take the cantor tuple function, which is known to be primitive recursive.

Of course, that's not a proper definition, we need mathematical induction to throw away those horrible dots.


Using Chebyshev to derive an upper bound for Coupon Collecter's Problem

As you should have suspected, there is only a thin line between what you have tried and what is rigorous.

Here it is the rigorous version of your attempt. Since $\beta n\ln n\gt \mu_X$ when $n$ is large enough, the first inequality holds for $n$ large enough.
\begin{align*}
Pr[X>\beta n \ln(n)]
&\leq Pr[|X-\mu_X| \geq \beta n \ln n - \mu_X] \\
&\le \frac{\sigma_X^2}{(\beta n \ln n - \mu_X)^2}.\\
\end{align*}
Now

$$\begin{aligned}
\lim_{n\to\infty}\frac{\frac{\sigma_X^2}{(\beta n \ln n - \mu_X)^2}}{\frac1{\ln^2 n}}
&=\lim_{n\to\infty}{\frac{\sigma_X^2}{n^2}}\lim_{n\to\infty}\frac{(n\ln n)^2}{(\beta n \ln n - \mu_X)^2}\\
&=\frac{\pi^2}{6}\lim_{n\to\infty}\frac{1}{(\beta - \frac{\mu_X}{n\ln n})^2}\\
&=\frac{\pi^2}{6(\beta - 1)^2},
\end{aligned}$$
which implies $$\frac{\sigma_X^2}{(\beta n \ln n - \mu_X)^2} = O\left(\frac{1}{\ln^2n}\right).$$


Could I simulate the implementation of memory components

You can simulate the architecture using a hardware-description language.

Try VHDL (http://esd.cs.ucr.edu/labs/tutorial/) or Verilog ( http://www.asic-world.com/verilog/veritut.html) two of the most popular hardware description languages.


How to calculate the basic steps in Fibonacci sequences to get nFn and n^2

Let's start with the second function, fib2. If you count the number of operations, then you get only $O(n)$. So why is the running time given as $\Theta(n^2)$? The reason is that the Fibonacci numbers grow exponentially, and so addition can no longer be considered an $O(1)$ operation. The $n$-th Fibonacci number is $\Theta(n)$ bits in length, and this leads to a running time proportional to $\sum_{i=2}^n i = \Theta(n^2)$.
As for fib1, we can easily write a recurrence for the running time $T(n)$:
$$
T(n) = \begin{cases}
O(1) & \text{if } n \leq 1, \\
T(n-1) + T(n-2) + \Theta(n) & \text{if } n \geq 2.
\end{cases}
$$
For the sake of asymptotic analysis, we can replace $\Theta(n)$ with $n$ and consider $S(n) = T(n)/n$, which follows the recurrence
$$
S(n) = \begin{cases}
O(1) & \text{if } n \leq 2, \\
S(n-1) + S(n-2) + 1 & \text{if } n \geq 3.
\end{cases}
$$
Thus $R(n) = S(n) + 1$ satisfies $R(n) = R(n-1) + R(n-2)$.
Choosing appropriate initial values (which is fine, for the sake of asymptotic analysis), we find out that $R(n) = F_n$, and so $T(n) = nS(n) = n(R(n) - 1) = \Theta(nF_n)$.


Optimizing for maximum intervals given a distance bound

A simple double pointer $O(n)$ linear scan suffices. Initialize $i = j = 1$.

Increment $j$ until the next step would make $e_j - s_i > b$. Check if $j - i$ is better than the best found result, if yes, store $(i, j)$ (the boundaries of your subset).
Increment $i$. Terminate if we reached the end of the set.

The key observation here is that if a certain $j$ for $i$ is optimal, then for $i' = i+1$, it must be that $j' \geq j$, so we only ever have to scan forwards.


Lower space bound on a turing machine accepting palindromes

Hint: A Turing machine running in space $S$ runs in time at most $\exp S$.


Reference book for Parallel Computing and Parallel algorithms.

Also wanted to know that from which reference book or papers are the concepts in the udacity course on Parallel Computing taught...?

The History of Parallel Computing goes back far in the past, where the current interest in GPU computing was not yet predictable. Some important concepts date back to that time, with lots of theoretical activity between 1980 and 1990. Compared to the complicated trade-offs for current heterogenous systems, those old theoretical algorithms and concepts feel nice, powerful and easy to understand. Uzi Vishkin is a researcher who worked during that period, who still believes in those concepts (without overly compilicated trade-offs):

  Alas, the software spiral is now broken: (a) nobody is building hardware that provides improved performance on the old serial software base; (b) there is no broad parallel computing application software base for which hardware vendors are committed to improve performance; and (c) no agreed-upon architecture currently allows application programmers to build such software base for the future

I recently learned about those old concepts, and corresponding interesting survey articles:

Parallel Algorithms (64 pages)
https://www.cs.cmu.edu/~guyb/papers/BM04.pdf
by Guy E. Blelloch and Bruce M. Maggs – 1996

Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques (104 pages)
http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf
by Uzi Vishkin – October 12, 2010

A Survey of Parallel Algorithms for Shared-Memory Machines (70 pages)
https://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/5865.html
https://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-408.pdf
by Richard M. Karp and Vijaya Ramachandran – March 1988

Limits to Parallel Computation: P-Completeness theory (327 pages)
https://homes.cs.washington.edu/~ruzzo/papers/limits.pdf
by R Greenlaw, H Hoover, W Ruzzo – 1995

Parallel Algorithms (347 pages)
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.466.8142&rep=rep1&type=pdf
by H Casanova, A Legrand, Y Robert – 2008


We usually measure the running time of algorithm as a function of the length of the input.

For example, when we say that an algorithm runs in time $O(n\log n)$, what we mean is:

For every input of length $n$, the algorithm runs in time $O(n\log n)$.

This is an example of worst-case complexity. In your case, you are looking for a function $T(n)$ which satisfies the following:

For every input of length $n$, the algorithm runs in time at least $T(n)$.
Furthermore, for each $n$ there exists an input of length $n$ on which the algorithm runs in time $T(n)$.

To answer your particular questions: the answer should be a function of $n$; and we are looking for the "best-case scenario" of the algorithm for each input length $n$. Whether this best-case scenario is the one you said or not, depends on the algorithm. There might be algorithms for which your best-case scenario is actually a worst-case input (we can construct such algorithms artificially).


Does exist an algorithm to find all equivalence classes of given regular expression without kleene star? If yes then what is it?

No such algorithm is forthcoming. As I mentioned in an answer to one of your other questions, you can encode SAT as a regular expressions that equals $(0+1)^n$ iff the given formula is unsatisfiable. This means that the algorithm you are looking for will be able to solve SAT.


The following code is often used as a standard prefix-code for natural numbers, which bounds the length of each codeword by $\log n+O(\log\log n)$:

At first, we identify the natural numbers by binary strings:
$$(0,\epsilon),(1,0),(2,1),(3,00),(4,01),...$$

Lets call $l(x)$ the length of the binary representation of the natural number $x$. Note that for each $x\ge2$ the following holds:
$$\lfloor\log x\rfloor\le l(x)\le \lceil\log x\rceil$$

Secondly, lets define $s(x_1x_2...x_n)=\underbrace{11...1}_{n\text{ times}}0x_1x_2...x_n$ for binary sequences $x_1x_2...x_n$.

Note that the length of $s(x_1x_2...x_n)$ is $2n+1$. Lets further define $x'=s(l(x))x$, where both, $l(x)$ and $x$ are interpreted as their binary representations.

Finally, the code $D(x')=x$ is a prefix code satisfying that for each natural number $x$, the length of the encoding $x'$ is $\log x+2\log\log x+1$ (ignoring the rounding error).


Demonstrating that probability for every possible result is uniform at the end of an algorithm

The proof is by induction. The base case $t = k$ is clear. Suppose that the claim is true at some time $t$. We will prove it for time $t+1$.

Let the first $t+1$ elements be $x_1,\ldots,x_{t+1}$. By the induction hypothesis, at time $t$ each of the $\binom{t}{k}$ possible $k$-subsets of $x_1,\ldots,x_t$ is found in the array with equal probability. The probability that at step $t+1$ the array remains the same is $1-k/(t+1)$, hence each of the $k$-subsets of $x_1,\ldots,x_t$ appears at time $t+1$ with probability
$$
\frac{t+1-k}{t+1} \frac{1}{\binom{t}{k}} = \frac{1}{\binom{t+1}{k}}.
$$
Now consider some $k$-subset $S$ of $x_1,\ldots,x_{t+1}$ that contains $x_{t+1}$. For this set to be appear at time $t+1$, the following two events need to happen: at time $t$, the array consisted of $S \setminus \{x_{t+1}\}$ together with one of the $t-(k-1)$ remaining elements; and at time $t+1$, this element was replaced by $x_{t+1}$. In total, the probability is
$$
\frac{k}{t+1} \cdot \frac{1}{k} \cdot \frac{t-k+1}{\binom{t}{k}} = \frac{1}{\binom{t+1}{k}}.
$$


Apparently, it's NP-hard.  See the following paper:

Evasion and Hardening of Tree Ensemble Classifiers.  Alex Kantchelian, J.D. Tygar, Anthony D. Joseph.  ICML 2016.

Section 4.2 says that solving the problem exactly is NP-hard.  However, the paper then goes on to develop techniques that, in practice, might often find an approximate maximum, using integer linear programming.

For a proof of NP-hardness, see Section 5.2 of Kantchelian's PhD dissertation.


is it possible to reduce $HALT_{TM}$ to $E_{TM}$?

Nice question.
No, you cannot reduce $HALT_{\text{TM}}$ to $E_{\text{TM}}$, although you can reduce $HALT_{TM}$ to $\overline{E_{\text{TM}}}$. Here we are talking about Turing reduction.
$HALT_{\text{TM}}$ can be reduced to $\overline{E_{\text{TM}}}$
Let $\langle M,w\rangle$ be such that $M\text{ is a }TM\text{ and }M\text{ halts on input }w$.
Now let us construct a TM $M'$. On an arbitrary input $u$, $M'$ will check whether $u$ is the same as $w$.

if it is not, $M'$ will run forever.
if it is, $M'$ will simulate $M$ on input $w$. Then once $M'$ halts, $u$ is considered as accepted.

We can make the transformation from $M$ to $M$ be algorithmic, thanks to the existence of a universal TM machine.
It is routine to verify that $\langle M,w\rangle$ is in $HALT_{TM}$ if and only if $M'$ is in $\overline{E_{\text{TM}}}$.
$HALT_{\text{TM}}$ cannot be reduced to $E_{\text{TM}}$
For the sake of contradiction, suppose $HALT_{\text{TM}}$ is reduced to $E_{\text{TM}}$ by reduction $f$. Then $\overline{HALT_{\text{TM}}}$ is reduced to $\overline{E_{\text{TM}}}$ by reduction $f$ as well. Since $\overline{E_{\text{TM}}}$ is Turing-recognizable, so is $\overline{HALT_{\text{TM}}}$. Since $HALT_{\text{TM}}$ is Turing-recognizable, we have $HALT_{\text{TM}}$ is decidable, which is known to be false, however. This contradiction shows that $HALT_{\text{TM}}$ cannot be reduced to $E_{\text{TM}}$.


Given a number, getting a grid position in a spiral pattern

I'll give a hint by breaking down the problem into nice looking components. I'll leave it to you to implement the components and use them yourself.

1) A function from id to the ring number it is in.
For example,

id 0 is in the 0th ring.
id 1,2,3,4,5,6,7,8 is in the 1st ring.

2) A function from ring number to the last id of the ring.
For example,

0th ring's last id is 0
1st ring's last id is 8
2nd ring's last id is 24

3) A function from ring number to the last pos of the ring. For example,

0th ring's last pos is (0,0)
1st ring's last pos is (-1,1)
2nd ring's last pos is (-2,2)

4) A function from id to the increment of pos to reach the next id. Let's call this function $g$. For example,

$g(10) = (1,0)$
$g(20) = (0,-1)$

It has to do with what part of the ring the id is in.

Hopefully, this has structured the problem in a way you can see the solution easier by yourself.


In general, does $f(g)$ and $f(h)$ have the same time complexity?

No, $f \circ g$ and $f \circ h$ (to use the standard mathematical notation) do not in general have the same complexity. For example, take $g(x) = 1$ (constant function) and $h(x) = x$ (identity function). Then $(f \circ g)(x) = f(1)$ and $(f \circ h)(x) = f(x)$; these functions only have the same complexity if $f = \Theta(1)$ (i.e. $f$ is asymptotically constant). This shows that the only functions $f$ for which all functions of the form $f \circ g$ have the same complexity are the ones that are asymptotically constant.

With the example $f = \lg^*$, growth is very slow, so a lot of functions “collapse” when you plug them into $\lg^*$. Nonetheless it is easy to cancel this collapse: define the function $e(y) = \min\{x \mid \lg^*(x) \ge y\}$. This is essentially an inverse function for $\lg^*$ (growing by $1$ at increasingly long intervals). With this you can easily construct functions that grow at any rate you like: $f(e(x)) \approx x$, $f(e(x^2)) \approx x^2$, etc.

(N.B. In my mathematical statements, I assume functions from $\mathbb{N}$ to $(0,\infty)$.)


Runtime of searching for a number in an array?

Regardless of whether the number is present in the array, all n elements will still be examined in the worse case. For example if searching for the number 5:

array1 = {6, 8, 3, 7, 8, 2}
array2 = {6, 8, 4, 9, 4, 5}

Searching array1 will require looping over all 6 elements (leading to 5 not being found).
Searching array2 will also require examining all 6 elements, with the final element being 5 and the search returning true.

As for the average number of searches, I believe you are referring to the average number of elements examined? This is difficult. If you are wondering what the average case is for arrays of ints with length 6, you would need to generate all possible permutations of arrays  of ints with length 6, then search them all for your desired number (say 5) and calculate the average. This will differ again if you only include permutations that have at least one element which is 5 (average will improve).

For a brute force search algorithm like this, all you can really be certain of is that the average case will be somewhere between the best best case O(1) (5 is first element of the array) and the worst O(n)


Finding $d$ in RSA Encryption mathematically and by hand

Suppose that you know $e$ and $n$, and want to find out $d$ such that $ed \equiv 1 \pmod{n}$ (this is possible if $(n,e) = 1$). An efficient way to do this is to use the extended Euclidean algorithm, which finds two integers $a,b$ such that $an + be = (n,e) = 1$. You can use $d = b \bmod{n}$, since $de \equiv be \equiv 1-an \equiv 1 \pmod{n}$.


There are many ways to do it. The following approach allows to fairly split work between many cores. I believe that it's used even in GPU implementations of radix sort, such as ones provided by Boost.Compute and CUDA Thrust.

I describe here one pass of LSD radix sort that distributes data into R buckets:

First stage: split input block into K parts, where K is number of cores sharing the work. Each core builds histogram for one part of data, counting how many elements from this part of data should go into each bucket: Cnt[part][bucket]++
Second stage: Wait till all cores finished the stage one, and then compute partial sums over counts, thus revealing an initial index of each bucket for every part of data. This is sequential algorithm.
Third stage: each core again process its own part of data, sending each element into position determined by Cnt[part][bucket]

In pseudocode the entire pass looks like:

parallel_for part in 0..K-1
  for i in indexes(part)
    bucket = compute_bucket(a[i])
    Cnt[part][bucket]++

base = 0
for bucket in 0..R-1
  for part in 0..K-1
    Cnt[part][bucket] += base
    base = Cnt[part][bucket]

parallel_for part in 0..K-1
  for i in indexes(part)
    bucket = compute_bucket(a[i])
    out[Cnt[part][bucket]++] = a[i]


Why are linked lists considered O(1) for in-middle insertion/deletion whereas dynamic arrays are considered O(n)?

You are right: if we have to find a particular place and then insert a value there (for example, insert an element in a sorted list), it is $O(n)$ for a linked list.

However, the Wikipedia article you seem to mention considers another operation named insertAfter: given a node, insert an element after that node.
When the particular node after which to insert is given to us, we spend only $O(1)$ time to do so, as we don't have to search for it.

An example usage is "duplicate each value $x$ we find in the list".
An example solution is to traverse a list, and whenever we find an $x$, add a duplicate right after it, and immediately step over it.
Each such insertion takes $O(1)$, and the whole solution is $O(n)$.
Note that, without any preallocation strategy, solving such a problem with a dynamic array is $O(n^2)$ worst case.


How to create RGB-colors with equal vector norm?

So how would one generate RGB vectors with a constant norm that are still valid RGB values? ($0 \le r,g,b \le 255$)

There is a simpler algorithm. Let $L$ be the given norm.

Verify that $0\le L\le 255\sqrt3$.
Let r be a random number between $\sqrt{L^2-\min(2\cdot255^2, L^2)}$ and $\min(255, L)$.
Let $M=\sqrt{L^2-r^2}$. Let g be a random number between $\sqrt{M^2-\min(255^2, M^2)}$ and $\min(255,M)$.
Let $b =\sqrt{L^2-r^2-g^2}$.

Some minor adjustment is needed if $r,g,b$ should be integers, in which case only approximate solutions can be found in general.

Here is the right computation if we want to find the range of $\theta$ and $\phi$.

If $0\le L\le 255$, then $0\le\theta,\phi\le\pi/2$
If $255\lt L\le 255\sqrt3$, let $M=\sqrt{\max(0, L^2-2\cdot255^2})$.
we have
$$\begin{align}
&\quad\quad\begin{cases}b = L \sin(\theta) \cos(\phi)\\
r = L \sin(\theta) \sin(\phi)\\
g = L \cos(\theta)\\
0\le b,r,g\le 255\\
0\le\theta,\phi\le\pi/2
\end{cases}\\
&\Longleftrightarrow
\begin{cases}b = L \sin(\theta) \cos(\phi)\\
r = L \sin(\theta) \sin(\phi)\\
g = L \cos(\theta)\\
\sqrt{\max\left(0,(L\sin(\theta))^2-255^2\right)}\le b,r\le \min(255,L\sin(\theta)) \\
M\le g\le 255\\
0\le\theta,\phi\le\pi/2,\, \theta\not=0
\end{cases}\\
&\Longleftrightarrow
\begin{cases}
\sqrt{\max\left(0,1-\left(\dfrac{255}{L\sin(\theta}\right)^2\right)}\le \cos(\phi)\le \min\left(1, \dfrac{255}{L\sin(\theta)}\right)\\
\sqrt{\max\left(0,1-\left(\dfrac{255}{L\sin(\theta}\right)^2\right)}\le \sin(\phi)\le \min\left(1, \dfrac{255}{L\sin(\theta)}\right)\\
\dfrac{M}{L}\le \cos(\theta)\le \dfrac{255}L\\
0\le\theta,\phi\le\pi/2,\, \theta\not=0
\end{cases}\\
&(\text{the inequalities on}\cos\phi\text{ put on the same restrictions on }\phi\\
&\text { as the inequalities on }\sin\phi)\\
&\Longleftrightarrow
\begin{cases}
\arccos\left(\min\left(1, \dfrac{255}{L\sin(\theta)}\right)\right)\le \phi\\
\phi\le\arccos\left(\sqrt{\max\left(0,1-\left(\dfrac{255}{L\sin(\theta)}\right)^2\right)}\right)\\
\arccos(\dfrac{255}L)\le\theta\le\arccos(\dfrac{M}{L})
\end{cases}
\end{align}
$$

The formula above tells a way to generate RGB vectors with a given norm $L$. Select $\theta$ and $\phi$ in the range given by the inequalities. Compute $r,g,b$ accordingly.

In particular, if you take $L=255\sqrt3=441.67$, then $\dfrac{255}L=\dfrac{M}L=\dfrac3{\sqrt3}$. $\theta=\arccos(255/L)=0.9553$. Since $\dfrac{255}{L\sin(\theta)}=0.7071$, we will get $\arccos(0.7071)\le \phi\le\arccos(0.7171)$. So $\phi=\pi/4$ and we will arrive at $b=255$, $g=255$ and $r=255$, which is the only possible combination of RGB vector for that value of $L$, as expected.

There have been several computational mistakes in the question. There has been a few in the previous versions of this answer as well. The comments below this answer might have become irrelevant.


Hint: Use a union bound.

Note that for $m \geq 2^k$ you cannot provide any non-trivial bound, since there are formulas with $2^k$ clauses of width $k$ that are unsatisfiable. The same example shows that the bounded hinted above is tight (for all $m \leq 2^k$).


How can I calculate tree sizes to "stretch up" a finger tree?

As it turns out, the best way to calculate the necessary tree sizes is not to. While crushing down one copy of the $ys$ finger tree (in a process reminiscent of "zipping" a Huet zipper), I can simultaneously crush down just one side of each of two additional copies, while pulling digits off the other sides to use directly (no calculation!). When I get near the bottom, I finish off the complete 2-3 tree, and then attach the two crushed half-trees to the $xs$ finger tree (once I've replaced its leaves using the complete 2-3 tree).
Edit (March, 2015)
The code (recently simplified and cleaned up) can be found in the GitHub repository. Both the <*> and *> implementations now use this technique; the latter takes advantage of Louis Wasserman's applicativeTree function to obtain asymptotic reductions in time and allocation.


The idea of DeepDream is this: pick some layer from the network (usually a convolutional layer), pass the starting image through the network to extract features at the chosen layer, set the gradient at that layer equal to the activations themselves, and then backpropagate to the image.

Why does it make sense? Intuitively, it amplifies the features that are maximally activated in the network. By backpropagating this gradient, we'll make an image update that will boost any of the existing activations. If there's a cat-like detector in the layer and the image contains some patch that looks a bit like a cat, DeepDream boosts this activation by updating this patch to be even more cat-like. As a result, DeepDream is trying to find cats and dogs everywhere in the image (ImageNet dataset has lots of dogs, so the network has many dog-related neurons).

If you look at the code, the key part is objective_L2 function that makes this: $dx = x$ and then backpropagates.


A number is even if it leaves no remainder when divided by two. Zero leaves no remainder when divided by two.


Construct a grammar over {$a,b$} whose language is {${a^mb^ia^n | i = m+n}$}

You must handle aXb and bYa sequences seperately.
$\\S \rightarrow \  XY\ |\ \epsilon \ \\ X\rightarrow \ aXb\ | \ \epsilon \\ Y\rightarrow  \ bYa\ | \ \epsilon$


First of all, Kd-trees are data-structures for a number of points, while your problem is considered with shapes. Although you can (and we will) represent the shapes as points in a higher dimensional space in some way, querying shapes is an important special case over arbitrary points. I don't see why Z-orders would be interesting for points, so we really want a data-structure for shapes. R-trees store rectangles, but if you are interested in finding intersections of query regions with non-rectangular shapes, R-trees probably aren't very helpful.
Since a general shape is not so clearly enough, I will consider searching for a range in a set of $n$ simple polygons, this should be sufficient for most cases. Querying this structure with a 2D range (that is, an orthogonal rectangle) for shapes can mean two different things:

Find all polygons fully contained in an orthogonal query rectangle.
Find all polygons intersecting an orthogonal query rectangle.

Polygons fully contained in an orthogonal query rectangle
For the first query, note that a polygon is fully contained in a rectangle if and only if its rectangular bounding box is fully contained inside the query rectangle. So, we can search for the bounding boxes of the shapes. To do this, we represent the bounding box of every shape $s$ as a tuple of the bottom left and upper right corner $(p_s, q_s)$. I denote the $x$- and $y$-coordinates of a point using brackets, e.g. $p[x]$. We want to find all $s$ such that $p_r \leq p_s$ and $q_r \leq q_s$ for a query rectangle $r$. We can use a 4D version of your favorite point range query data structure (Kd,R,Range,etc.-tree) to find all those rectangles in $O(\log^3 n + k)$ time, were $k$ is the amount of rectangles reported, and use $O(n\log^3 n)$ storage for the data-structure. You can actually reduce the storage to $O(n\log^2 n)$, using a 2D-Range tree on the points $p_s$ and 'linking' this tree to a priority search tree for the $q_s$ coordinate (since we only have to search in positive direction on the second coordinate). However, Range trees tend to have large coefficients in practice, so you should probably stick to the trees you're familiar with.
Polygons intersecting an orthogonal query rectangle
For the second type of query on points, finding all polygons intersecting an orthogonal query rectangle, searching for intersecting bounding boxes may lead to a lot bounding boxes where the polygon does not actually intersect the query rectangle, so we need another representation. If we represent all polygons by the $m$ segments of their boundaries, we use a Windowing query to find the segments in $O(log^2 m + i)$, where $i$ is the amount of segments found, using a $O(m\log m)$ size data-structure.
However, we missed the polygons that contain our query rectangle, as we only looked for boundary intersections. We can check this by storing the bounding boxes of all polygons in 2 'chained' segment trees (similar to creating from 2D-range trees from BST's) and query for the bounding boxes that contain endpoints of the query rectangle. This has a query time of $O(\log n + k)$ and uses $O(n\log n )$ storage, but this is dominated by the other part, as $n\leq m$ and $k \leq i$.
Now, for z-orders...
First, to summarize, we now have algorithms to solve the following problems with the following bounds:

Finding all polygons fully contained in an orthogonal query rectangle takes $O(\log^3 n + k)$ time and $O(n\log^3 n)$ space, where $n$ is the total number of polygons and $k$ is the number of polygons reported.
Finding all polygons intersecting an orthogonal query rectangle takes $O(\log^2 m + i)$ time and $O(m\log m)$ space, where $m$ is the total number of polygon segments and $i$ is the number of segments of the polygons reported.

Now, I feel that I can finally consider the z-order. I will assume we want to query for shapes fully contained in our rectangle, since the reasoning and conclusion is similar for the other case.
I do not know why you need the objects sorted on z-order, but I assume you want to iterate over all reported shapes in their z-order (If this is not what you want, there might be a far better method than sorting)
If we query as discussed and sort the found rectangles, we get a running time of $O(\log^3 n + k\log k)$. Generally, $k$ is small compared to $n$, so the additional log factor does not do that much so you might as well sort. In fact, $n\log n$ is usually the best you can get for an geometric algorithm that is not a variant of point location/range search.
If $k$ is not small compared to $n$, you're probably better of not running all this complicated range searching and just run the trivial $O(n)$-algorithm that traverses all shapes in their z-order, while checking in constant time if it is in your query range. (I ignore sorting all shapes, as you only need to do that once)
Tldr;+Conclusion
If range searching is your problem, sorting probably isn't and if sorting is your problem, range searching probably isn't.
Although there are probably cases where they both are problem (e.g. zooming in maps), getting a good solution for this case could be rather tricky. I hope that if you learned anything from this answer, it is that range searching can already be quite a tricky business, so I'll leave it at this for now. It might be interesting to look if this specific topic has some useful literature.


What is the relation between EXPTIME and NP HARD complexity classes?

There are NP-hard problems that are not in EXPTIME and vice versa. This is to be expected as NP-hard is defined by a lower bound and EXPTIME mainly by an upper bound. NP is contained in EXPTIME, however, and NP-complete is of course contained in NP.


Prove correctness of recursive algorithm

Generally, you should follow the instructions given by @vonbrand to carry out a mathematical induction proof for a recursive algorithm. Now I would like to show you more hints.

Playing with a small test case, we know that we should prove the following theorem:

   Theorem: The function foo always returns the minimum value of the original list $l$.

To carry out a mathematical induction on the size $n$ of list, we go through the following three steps:

Base Case: $n = 1$. In this case, you obtain $l[0]$ which is trivially the minimum. (Note that foo throws an exception for case $n = 0$.)
Inductive Hypothesis: Suppose that the theorem holds for $2 \le n \le k$.
Inductive Step: Consider $n = k + 1$. You should prove that (This is left as an exercise) $$\min(\text{modified list } l' \text{ by the `if/else` statement and of size } k ) = \min(\text{original list } l \text{ of size } k+1).$$


No.

LR(k) grammars have to be unambiguous, that is there can be only one possible parse tree for every (valid) input. There are left- and right-regular grammars violating that, for example

$\displaystyle\qquad S \to aS \mid aaS \mid a$

or, if that one does not match your definition of right-regular,

$\qquad\displaystyle\begin{align}
  S &\to aS, S \to aA, \\
  A &\to aA, A \to a
\end{align}$

as reinierpost mentions in a comment.

Of course, every regular language does have an unambiguous (right-)regular grammar; get one from its minimal DFA using the standard construction.


Turing machine working only with 1's and blanks - how to encode input?

In the following, I use "0" to denote a blank cell, and I first assume that 1 is not used in the original alphabet. I will deal with this at the end.

A first solution is possible if you assume that the head can go over a cell and read it without writing on it.

If you assume that you can tell the two ends of your input, the answer
to your question is just that you copy/translate the input to unary form on some
other part of the tape, so that you do not run the risk of erasing a
part of the input that has not been copy/translated yet. If you
copy/translate the input from left to right, you start the copying on
some part of the tape that is on the right of the original input.

For that purpose, you need markers, and you can for example use 010 to
mark the place where you copy the translation of the next symbol. You
can erase original symbols as you copy them, and possibly also mark
the last erased symbol with 010 (wich you then do not use as
translation of an original symbol). Part of the control is teh used to
move bertween the two 010 marks during the translation phase.

But you cannot make the number of states dependent on the length of
the input. The TM uses the same finite state control independently of
input size, which implies not changing th number of states.

If you do not allow reading a cell without overwriting it, things are
more complicated. I further assume that the head is initially on the
left side of the input. In ordr to make a copy translation without
destroying the input, one has to start from the left, and make the
copy further on the left.

Since it is impossible to foresee how much space will be needed, the
trick is to copy/translate the input into a mirror image, so that it
grows on the left, and never risk erasing the original input.

Then you can either decide to compute with a mirror image, or you can
just make a second pass on the copy/translated input, so as to reverse
it again and have it in the right order.

Using 1 in the original input.

I think that it is possible to do the same when 1 is used in the original alphabet. But one must be very careful not to confuse its use in the original input, and in the copy part. This can be done with a specific configuration appearing only a fixed number of times in the created copy, the rightmost one dentifying precisely the beginning of the rest of the original input to be copied.


Why does a RNN network output different based on the training sequence

RNNs are pattern recognition tools. It is't entirely clear to me what it is exactly that you are trying to do, but if you simply intend for it to classify positive and negative messages a regular Neural Network might be better suited.

What your RNN does (if implemented correctly) is learn classifications in the context of the sequence. i. e. It is learning: what are the odds of a given input X being positive/negative knowing the preceding N outcomes.

This should already be giving you some insight on why different orderings of the training data skew the results. If your training set is all positives followed by all negatives then the vast majority of your training set will be teaching the network that a sequence of positives almost certainly indicate a positive message and vice versa.

Building a good dataset is by far the most important part of applying machine learning and I suggest you look for some high level explanations of the different types of ML and some general information on bias in data.


Proving a language is not regular using Myhill Nerode Theorem

Take $a^nb$ and $a^mb$ for n != m. Since the first can be followed by $a^n$ and the second can’t, they are in different equivalence classes. Therefore the number of equivalence classes is not finite.

C isn’t even needed.


Solutions to Diophantine Equations using a Min Heap

A min-heap with entries $x_i$ is equivalent to a max-heap with entries $-x_i$ (or more generally, $A - Bx_i$ for any $B > 0$, or even more generally, $\phi(x_i)$ for any monotone decreasing $\phi$). So you can convert your solution with two min-heaps to a solution with one min-heap and one max-heap, as well as to a solution with two max-heaps.


Using transitive closure to determine acyclic property on directed graph

It is possible to use Warshall's algorithm for that also. If there is is a negative entry on the diagonal, then the graph contains a negative cycle. If both the shortest path from i to j and the shortest path from j to i is not infinite, then the graph contains a cycle. If there are no i and j with this property, then the graph is acyclic. (This takes only $O(|V|^2)$ steps to check, while Warshall's algorithm itself takes $O(|V|^3)$ steps.)

However, it's faster to use depth first search and check that there are no backward edges in the depth first search tree. Also note that there exists an algorithm for computing the transitive closure (including the transitive reduction) in $O(|V|\cdot|E|)$ steps. (I think it uses a topological order as a starting point.)


Tarjan's SCC : example showing necessity of lowlink definition and calculation rule?

For a given vertex, the only thing that matters in the algorithm is if there is an edge from the vertex or a child-vertex to a ancestor-vertex in the DFS exploration tree. In this case, we know that the vertex belongs to the same SCC as it's parent. In such a case, we are sure that the vertex itself or a child-vertex has a direct back edge to an ancestor of the vertex, and this ancestor has a lower index that the current vertex, so the v.lowlink will differ from v.index. We actually do not need to know the top-vertex of the SCC at this step.

So, using v.lowlink  := min(v.lowlink, w.lowlink) instead of v.lowlink  := min(v.lowlink, w.index) will lead to a correct algorithm too.
The difference is that in this case, v.lowlink will not represent the vertex with the smallest id reachable from v  nor the SCC top vertex, but just v if there is no such vertices, or any parent vertex that belongs to the same SCC (maybe the top-vertex), depending of DFS order. I think it's just lack in formal definition, and thus, wasn't used.

Let's see what appends when we use this alternative instruction. When we update v.lowlink because we have found a new back edge to a ancestor vertex, we will now set v.lowlink with the value of w.lowlink. But this vertex is an ancestor and is still in the stack: we may not have already explored all the child vertices of this ancestor and thus, w.lowlink can change in the future: this is why we dont's know exactly what will be the final value of v.lowlink because it depends of the DFS order. We can juste be sur that it will be w.index or a vertex with a lower index that belongs to the same SCC (so the algorithm will work as expected): the value of lowlink still differs for differents vertices of the same SCC.

The following example show how DFS order alters lowlink values in this alternative algorithm:

In this case, assuming we are exploring vertices in the order 0-1-2-3-4, when we consider the vertex 3, the vertex 4 has not been explored yet. The lowlink value of vertex 1 is so 1, and vertices 2 and 3 will take the same value. But we will later find the back edge from 4 to 0, and set the lowlink value of vertices 4 and 1 at 0. If we had explored vertex 4 prior to vertex 2, all vertices would have 0 as lowlink value.

And for the last question, yes, all this verteces belong to the same SCC, rooted by x.lowlink or an ancestor of the vertex with id x.lowlink


An alternative approach could be

Scan the vector and insert all elements into a self-balancing BST (AVL or Red-Black Tree etc etc, your pick) along with its index in the vector. $Node := (Value,VectorIndex)$
Then you have two choices

Scan the vector again, and for each element, search for it in the BST, and find its successor. Link the element and its successor in the vector.
Do an inorder traversal of the BST and for every pair of consecutive nodes visited in the BST, link their corresponding elements in the vector.

Either way, step 1 and 2 each take $O(n\space log \space n)$, hence the total algorithm ends up with a time complexity of $O(n \space log \space n)$ and space complexity of $O(n)$.


It would use secure 2-party computation. There would probably be commitments to the statuses of the pieces and oblivious transfers to simulate referee responses and zero-knowledge protocols to show that the players are behaving as they should with respect to the above 2 parts.

If you're taking the oblivious transfer functionality as given and assuming the players are semi-honest, then I'm willing to try coming up with more details here.  On the other hand, if you're interested in how the oblivious transfers would be performed or how the zero-knowledge protocols would work, then you should ask on crypto.


Here is a translation of the answer how to prove 4-SAT CNF is NP-complete to the current situation.

Suppose an instance of 4-SAT over variables $x_1,x_2,\cdots, x_m$ is given as a boolean formula $$f=c_1\land c_2\land \cdots\land c_m,$$ where $c_i$ is a disjunction that has exactly 4 literals for all $i$.

Introduce a new variable $s$. Suppose $c_i=w\lor x \lor y \lor z$ for some literal $w,x,y,z$. Let
$$\begin{aligned}
c_{i+}&=w\lor x \lor y \lor z\lor s\\
c_{i-}&=w\lor x \lor y \lor z\lor \neg s.
\end{aligned}$$

If $c_i$ can be satisfied by an assignment, then $c_{i+}\land c_{i-}$ is satisfied by the same assignment plus $s=0$ (or $s=1$).
If $c_{i+}\land c_{i-}$ can be satisfied by an assignment, the same assignment without considering $s$ must satisfy $c_i$ since one of $s$ and $\neg s$ must be false.

Construct an instance of 5-SAT over variables $x_1,x_2,\cdots, x_m, s$, $$g=c_{1+}\land c_{1-}\land c_{2+}\land c_{2-}\land\cdots\land c_{m+}\land c_{m-}.$$

Because of the relation between $c_i$ and $c_{i+}\land c_{i-}$,

If $f$ is satisfied by an assignment, then $g$ is satisfied by the same assignment plus $s=0$.
Conversely, if $g$ is satisfied by an assignment, then $f$ is satisfied by the same assignment without considering $s$.

The above means the transformation from $f$ to $g$ is a reduction from 4-SAT to 5-SAT. It runs in polynomial time.

For simplicity of explanation, the above restricts $k$-SAT to CNF formulas with exactly $k$ literals without duplicates. Thanks to a similar simple padding technique, it is does not matter to the construction of reduction above whether we allow at most $k$ literals with or without duplicates when we define $k$-SAT.


NAE-SAT is clearly in NP, while MAX-CUT is NP-complete. So by the definition of NP-complete, there is some reduction from NAE-SAT to MAX-CUT.


Linked allocation in operating systems: why not use a doubly linked list?

Singly and doubly linked lists have the identical (terrible) linear access time. Using doubly linked lists would not help performance. The only benefit you'd get is that reading file backwards is more efficient.
No modern file system uses linked allocation anymore. Most use ranges of consecutive blocks, so called extents. Extents are usually more space-efficient and support random access. Neither Singly or doubly linked lists support random access. In practice these days the metadata for a file is read in at once (with all its extents), this is fast. Reading all nodes of the linked lists would mean reading several blocks, one after the other. This is slow, obviously.


Is the potential difference in the two consecutive states of a data structure equal to the credit of the change inducing operation?

The potential function is a fictitious quantity which is used to bound the cost of operations in a data structure. Suppose that our data structure supports only one operation, whose worst-case cost is $C$, and that we want to show that the amortized cost is only $\hat{C}$. What we do is define quantities $\phi(D_i)$ that satisfy the following axioms:

$\phi(D_0) = 0$.
$\phi(D_n) \geq 0$ for all $n \geq 0$.
$\hat{c}(O_i) := c(O_i) + \phi(D_{i+1}) - \phi(D_i) \leq \hat{C}$.

We then have, for all $n \geq 0$,
$$
\begin{align*}
n \hat{C} &\geq \hat{c}(O_1) + \cdots + \hat{c}(O_n) \\ &= c(O_1) + \cdots + c(O_n) + \phi(D_{n+1}) - \phi(D_0) \\ &\geq c(O_1) + \cdots + c(O_n) \, .
\end{align*}
$$
In other words, the amortized cost of each operation is at most $\hat{C}$.

If we define $\phi$ via $c(O_i) = \phi(D_{i+1}) - \phi(D_i)$, then we are really defining some other fictitious quantity. A better choice from the point of view of the analysis above would actually be $\phi(D_i) = 0$, which allows us to recover the bound $C$. The general idea is that we want the fictitious potential function $\phi$ to generally be "small", but sometimes we allow it to grow (we "borrow") so that we can later on take the cost of a costly operation.

Here is a very simple example. Consider a data structure with a single operation in which operation $2^i$ costs $2^i$, and other operations cost $1$. A priori, the worst-case cost is infinite. However, suppose that we define $\phi(D_n) = 2n - 2^k$, where $2^{k-1} < n \leq 2^k$, that is, $2^k$ is the smallest power of $2$ above or at $n$ (and $\phi(D_0) = 0$). Since $n > 2^{k-1}$, when $n > 0$ we indeed have $\phi(D_n) = 2(n-2^{k-1}) > 0$.

When $2^{j-1} < i < 2^j$, we have
$$
\hat{c}(O_i) = 1 + [2(i+1) - 2^j] - [2i - 2^j] = 3.
$$
In this case we are "borrowing", since $\hat{c}(O_i) > c(O_i)$.

When $i = 1$, we get $\hat{c}(O_1) = 1 + [2 - 1] - [4 - 2] = 0$.

When $i = 2^j > 1$, we have
$$
\hat{c}(O_{2^j}) = 2^j + [2(2^j+1)-2^{j+1}] - [2(2^j)-2^j] = 2.
$$
In this case the potential collapses from $2(2^j) - 2^j = 2^j$ to $2(2^j+1) - 2^{j+1} = 2$, allowing us to "pay" for the costly operation $2^j$.

We conclude that the amortized cost per operation is at most $3$.


You are technically right. The correct phrasing should be that there are countably many TMs up to isomorphism of the tape alphabet and the state-space.

Indeed, if you say that a TM with states $\{q,r\}$ is different than the same TM with states named $\{1,2\}$, then not only are TMs not a countable collection, they are not even a set in the ZFC axiom system.
This follows from the fact that the collection of all sets is not a set itself.


LTL is less expressive than $\omega$-regular expressions. For example, the expression
$$((a+b)b)^\omega$$
i.e. "there is $b$ in all the even places"
cannot be expressed in LTL.

In addition, observe that checking whether an $\omega$ regular expression is expressible in LTL is harder than checking universality, which is PSPACE hard.

However, there are ways to tackle this problem. You can start here for a reference.


Quicksort's asymptotic performance for array of [50,...,50,100,...100]

That depends very much on exactly what quicksort variant you use. Perhaps you should take a peek at Sedgewick "Quicksort with equal keys", SIAM J. Comp 6:2 (jun 1977), pp 240-267 (get it here) or Bentley, McIllroy "Engineering a sort function", Software: Practice & Experience 23:11 (nov 1993), pp 1249-1265.


Clarification of Hopcroft's proof that "deciding whether a program halts on all inputs" is not R.E

$M'$ doesn't "need" to do anything.  $M'$ is a machine that we construct for purposes of the proof.  Hopcroft wrote the theorem, so he can design $M'$ however he wanted -- of course, then it's his obligation to show how his choice of machine helps him prove the theorem.  He chose $M'$ cleverly in a way that helps make the proof easy, but that was his choice.

So, it was his choice to make the $M'$ simulate $M$ for only $n$ steps.  He could have chosen something else, but this particular choice makes the proof work out nicely.  In particular, this property of $M'$ is useful for showing that statement 4 is true.  (Exercise: try proving that statement 4 is true, and check where you used the fact that $M'$ will only simulate $M$ for $n$ steps, not more.)


Douglas-Peucker line simplification algorithm time complexity

Your analysis seems correct, except for that you need $T(n)=T(index)+T(n-index+1)+2n$ instead because when $index$ is either $0$ or $n-1$ you won't get in the right hand side another factor of $T(n)$, which is not allowed.
In fact, it will yield something very close to the recurrence of the running time in the quicksort algorithm.
Worst case scenario
When index is either $0$ or $n-1$, the recurrence will boil down to $T(n)=T(1)+T(n-1)+2n = T(n-1) + (2n + T(1))$. You can easily show by induction that $T(n)=\Theta(n^2)$ in this case.
Best case scenario
We assume the input in the recursion will always be cut down by half. That is, the recursion is $T(n)=2T(n/2)+2n$.
Define $b=a=2$ and $f(n)=2n$. Then, $T(n)=aT(n/b)+f(n)$.
We can calculate $c_{crit}=\log_{b}(a)=\log_2(2)=1$ and thus $f(n)=2n=\Theta(n)=\Theta(n^{c_{crit}})$.
Now we can directly use the second case to get that $T(n)=\Theta(n^{c_{crit}}\log(n))=\Theta(n\log(n))=O(n^2)$
Average case scenario
If we assume that the input is a random variable, such that the choice of $index$ is uniformly distributed in $\{0,\dots,n-1\}$, then the algorithm takes expected time $\Theta(n\log(n))$. Take a look at the proof for quicksort to see how its done.


No, determining whether a graph is not Hamiltonian is coNP-complete, and it is believed not to be NP-complete, indeed not in NP. Determining what a graph is Hamiltonian is NP-complete.


Big Oh and Big Omega when $n$ and $\log n$ terms are in $f(n)$

You are right that you cannot a priori ignore additional terms, although morally you can as the "smaller" terms do not contribute to the asymptotic growth.
As an example $f(n) :=n+\log n$ is in $\Theta(n)$. Why? Going back to the definition, we want to show that $f(n)$ is in $O(n)$ and in $\Omega(n)$. Showing $f(n)\in \Omega(n)$ is immediate, as $f(n) \geq n$ for all $n>0$.
To show that $f(n)$ is in $O(n)$, simply notice that for large enough $n$ (say $n>N$ for some constant $N$) we have $\log n \leq n$ and thus $f(n)\leq 2n$ for all $n>N$. By definition $f(n)\in O(n)$.


Is there some theoretical verification or explanation of why KDTree gets slower when the dimensionality gets higher?

The problem arises due to  curse of dimensionality.  If the dimensionality is $k$ , the number of points in the data, $N$ should be $N ≫ 2^k$. Otherwise, when $k-d$ trees are used with high-dimensional data, most of the points in the tree will be evaluated and the efficiency is no better than brute force search. So for high value of $k$, approximate nearest-neighbour methods should be used instead.

  most of the points in the tree will be evaluated

When the dimensionality increases to high value, the volume of the space increases so fast that the available data become sparse.Organizing and searching data often relies on detecting areas where objects form groups with similar properties; in high dimensional data, however, all objects appear to be sparse and dissimilar in many ways, which prevents common data organization strategies from being efficient. Hence $k-d$ trees become ineffiecient for high dimensions.


Complexity of an instance of a NP-complete problem

To show $A$ is NP-complete, you need to prove the following:

$A \in \mathbf{NP}$
$A$ is NP-hard: any problem $B \in \mathbf{NP}$ is poly-time (many-one) reducible to $A$

or

equivalently (because reduction relations are transitive): there is an NP-hard problem $B$ which is poly-time (many-one) reducible to $B$.

You have shown neither, so you cannot say $A$ is NP-complete.

What you did do is a many-one reduction from $A$ to $B$, but you want the other way around. In addition, you also need to show the reduction is efficient, that is, takes polynomial time; you did not explicitly state whether this is the case. And, of course, you must not forget to show $A \in \mathbf{NP}$ (which is usually the easier part).


Actually, there are only $459^3$ transitions, not $459^4$ transitions.  That helps a lot.  This is because a state is a pair $(t,u)$ where $t,u$ are tags, and a transition has the form $(t,u)\to (u,v)$.  In particular, you can't have $(t,u) \to (w,x)$ where $u \ne w$ (given that the state represents the last two tags).  So, there are at most $459^3$ transitions, or at most about 100 million transitions.  You should be able to store that a graph with 100 million edges in memory without too much difficulty.

My guess would be that not all transitions actually occur in the training set, so it's possible this might be a sparse graph, and that might reduce the graph size further.


Prove that any directed cycle in the graph of a partial order must only involve one node

I'm assuming your partial orders are of the type "$a \leq b$" rather than of the type "$a < b$", though the proof is very similar to both cases. Each edge $a \to b$ in the graph corresponds to an inequality $a \leq b$. Now suppose you had a triangle $a \to b \to c \to a$. Such a triangle would imply
$$a \leq b \leq c \leq a, $$
which has some implications since $\leq$ is a partial order. The case of longer (or shorter) cycles is similar.


Mutual Information in a Binary Erasure Channel

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


Is it possible to solve the coin denomination problem using a 1-D array?

It is perfectly possible to solve the problem using a 1D array. Actually, you can even reconstruct the solution using just that 1D array. There are often multiple ways to solve a given problem, and in this case there's a neat time-memory tradeoff: in the 1D example you need $O(m)$ time to compute the value of one array slot, in the 2D example you only need $O(1)$ time but there are $O(nm)$ slots rather than just $O(n)$.


What is the difference between "definition" and "inductive" in Coq?

Inductive creates a new type and gives it a name. It is similar to datatype in SML, data in Haskell, type (defining an ordinary variant or a record) in Ocaml.

In addition to defining the type, Inductive also defines induction principles for that type. These induction principles aren't necessary from a theoretical point of view: all they do is to give a name to a particular well-typed term. They are provided because while you could write that term in your proof, it is mechanical and repetitive.

Definition gives a name to a term. It's broadly similar to let in SML or Ocaml or Haskell (but it doesn't let you write recursive definitions as such). Since Coq is pure (no side effects), if you write two definitions with the same right-hand side, the resulting names are equal. You can use Definition at any level of the sort hierarchy, including for types (in which case the definition is similar to type aliases in SML, Ocaml or Haskell).

Fixpoint is similar to Definition, but allows a recursive definition (like let rec in ML). It's in fact syntactic sugar for Definition plus the explicit fixpoint combinator fix, but definitions made using Fixpoint are easier to read and write.

The best way to understand these is to write a few proofs about some datatype. Try to rewrite some parts of the List library, for example.

There are several ways to implement finite sets in Coq. To to set theory proofs, try Sets.Finite_sets. If you want to have decent extracted code, use MSets.MSetAVL.


How are lookup tables described from the perspective of complexity theory?

Lookup tables take a key, and either provide a value according to the key or tell you that there is no value under this key.

Time and space requirements will depend on the implementation. It's usually not further mentioned if it is obvious what kind of implementation a reasonable person would use.


Why line graph is a proper subclass of claw-free graph?

Your question is answered on Wikipedia:

  "Line graphs may be characterized in terms of nine forbidden subgraphs;[2] the claw is the simplest of these nine graphs."

The reference is to the following paper:

  [2] Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J., Beiträge zur Graphentheorie, Leipzig: Teubner, pp. 17–33.

Wikipedia contains a pictorial description of these nine graphs. One of them is $K_5^-$, obtained from $K_5$ by removing a single edge.

If you take any of the other forbidden subgraphs then you get a claw-free graph which isn't a line graph.


Input that causes an operation on a binomial heap to run in $\Omega(\log n)$ time?

This paper shows that for each priority queue implementation satisfying some technical condition (which holds for binomial heaps) there is a sequence of operations consisting of $n$ INSERTs, $n$ DELETEs and $n$ FIND-MINs that takes time $\Omega(n\log n)$. Since INSERTs are amortized $O(1)$ in binomial heaps, the DELETEs and FIND-MINs together must take time $\Omega(n\log n)$. Unfortunately, in the construction the INSERTs are interspersed between the other operations.

This is of course overkill for the case of binomial heaps.In the implementation in which FIND-MIN is implemented by comparing the roots of all trees. If we INSERT $2^m-1$ elements then we will have $m = \log(n+1)$ trees, and so FIND-MIN will take time $\Omega(\log n)$. In other implementations, it shouldn't be hard to concoct examples in which some MERGE operation (used inside all the others) takes time $\Omega(\log n)$.

You might be worried that even though these examples show that some operations could require logarithmic time, the amortized complexity is still better. You'll have to work harder, but after some though you should be able to come up with a sequence of $n$ INSERTs and DELETEs which takes amortized time $\Omega(\log n)$.


That's not how non-determinism works, though perhaps it's how you'd simulate it in real life. Here are several ways of thinking about non-determinism.

The genie. Whenever the machine has a choice, a genie tells it which way to go. If the input is in the language, then the genie can direct the machine in such a way that it eventually accepts. Conversely, if the input is not in the language, whatever the genie tells the machine to do, it will always reject.

Hints. The machine computes a bivariate function. The first input is a word $w$, and the second input is a "hint" $x$. Whenever the machine faces a non-deterministic choice, it consults the next hint symbol, and operates accordingly. We are promised the following:

Completeness: if $w \in L$ then there is some hint $x$ which causes the machine to accept.
Soundness: if $w \notin L$ then the machine rejects on all hints.

Accepting computations. An accepting computation is a legal computation (one in which the machine always operates according to one of the choices it is faced with) which ends at an accepting state. A word is in the language iff it has an accepting computation.

We can formalize the notion of accepting computation using snapshots. A snapshot is a triple $(q,z,t)$, where $q$ is the current state, $z$ is the part of the word which remains to be read, and $t$ is the contents of the stack. We can define a relation $(q_1,z_1,t_1) \vdash (q_2,z_2,t_2)$ which expresses that the machine can reach snapshot $(q_2,z_2,t_2)$ from snapshot $(q_1,z_1,t_1)$ in one step. An accepting computation for a word $w$ (for the acceptance condition of emptying the stack) is a sequence $\sigma_0 = (q_0,w,\bot),\sigma_1,\ldots,\sigma_N=(q,\epsilon,\epsilon)$, where $q_0$ is the initial state, $\bot$ is the initial state of the stack, $q$ is an arbitrary state, $\epsilon$ is the empty word/stack, and $\sigma_{i-1} \vdash \sigma_i$ for all $i$.

Another equivalent description is in terms of reachability. Consider a directed graph in which vertices are snapshots and there is an edge from $\sigma$ to $\tau$ if $\sigma \vdash \tau$. An accepting computation is a path from $(q_0,w,\bot)$ to $(q,\epsilon,\epsilon)$, for any state $q$.


Range update + range query with binary indexed trees

Suppose you had an empty array:

0  0  0  0  0  0  0  0  0  0  (array)
0  0  0  0  0  0  0  0  0  0  (cumulative sums)

And you wanted to make a range update of +5 to [3..7]:

0  0  0  5  5  5  5  5  0  0  (array)
0  0  0  5 10 15 20 25 25 25  (desired cumulative sums)

How could you store the desired cumulative sums using 2 binary indexed trees?

The trick is to use two binary indexed trees, BIT1 and BIT2, where the cumulative sum is calculated from their contents.  In this example, here's what we'd store in the the two trees:

0   0   0   5   5   5   5   5   0   0  (BIT1)
0   0   0  10  10  10  10  10 -25 -25  (BIT2)

To find sum[i], you compute this:

sum[i] = BIT1[i] * i - BIT2[i]

For example:

sum[2] = 0*2 - 0 = 0
sum[3] = 5*3 - 10 = 5
sum[4] = 5*4 - 10 = 10
...
sum[7] = 5*7 - 10 = 25
sum[8] = 0*8 - (-25) = 25
sum[9] = 0*9 - (-25) = 25

To achieve the desired BIT1 and BIT2 values for the previous range update, we do 3 range updates:

We need to do a range update of +5 to indices 3..7 for BIT1.
We need to do a range update of +10 to indices 3..7 for BIT2.
We need to do a range update of -25 to indices 8..9 for BIT2.

Now let's do one more transformation.  Instead of storing the values shown above for BIT1 and BIT2, we actually store their cumulative sums.  This lets us do the 3 range updates above by making 4 updates to the cumulative sums:

BIT1sum[3] += 5
BIT1sum[8] -= 5
BIT2sum[3] += 10
BIT2sum[8] -= 35

In general, the algorithm to add a value v to a range[i..j] would be:

BIT1sum[i]   += v
BIT1sum[j+1] -= v
BIT2sum[i]   += v * (i-1)
BIT2sum[j+1] -= v * j

where the += and -= syntax simply means to update the BIT cumulative sum data structure with a positive or negative value at that index.  Note that when you update the BIT cumulative sum at an index, it implicitly affects all indices to the right of that index.  For example:

0 0 0 0 0 0 0 0 0 0 (original)

BITsum[3] += 5

0 0 0 5 5 5 5 5 5 5 (after updating [3])

BITsum[8] -= 5

0 0 0 5 5 5 5 5 0 0 (after updating [8])

Fenwick trees store sums in a binary tree.  It is easy to do the updates shown above to a Fenwick tree, in $O(\log n)$ time.


Is "duplicate" in RPN enough for replacing variable binding in term expressions?

Is “duplicate” in RPN enough for replacing variable binding in term expressions?

No, it is not strong enough. One can eliminate $\mathsf{dup}$ by replacing each sequence of $\mathsf{dup}$ by a sequence of $x$ preceded by one $\mathsf{sto}(x)$ operation. Since the single variable "$x$" is enough to eliminate all $\mathsf{dup}$ operations, any term expression which requires more than one variable to be stored efficiently can't be expressed (efficiently) using only $\mathsf{dup}$.

If the $\mathsf{inv}$ operation is omitted, then this whole intended representation by a term expression can be seen as a special case of the directed acyclic graph representation of a polynomial used in arithmetic circuit complexity. So the RPN stack from the question turns out to be just a representation of a tree. Now a directed acyclic graph can't be "emulated easily" by a tree, and especially a non-planar DAG will be "too difficult" for the $\mathsf{dup}$ operation.

In order to add the $\mathsf{inv}$ operation again, note that the ring of polynomials in $x_1,\dots x_n$ over $\mathbb Z$ is just the free commutative ring with generators $x_1,\dots x_n$. The corresponding free algebra with an $\mathsf{inv}$ operation would be the free commutative regular ring with generators $x_1,\dots x_n$. To be faithful to the canonical representation of the free algebra of a variety (equationally defined collection of algebras), the $\mathsf{inc}$ operation should be replaced by $1$.


Find the asymptotic bound $\Theta$ of $t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$

If we are not restricted by "using the master theorem", then either a better version of the master theorem, the versatile Akra-Bazzi method or the elementary way to show many recurrence relations mean $\Theta(n)$ or $\Theta(n\ln n)$ is an easy approach.

Otherwise, let us see how we can use the master theorem. We assume here $t(n)\geq 0$ for all $n \geq 0$, although the final asymptotic answer is actually valid without that non-negativity restriction. Let $c$, $m$ be two positive constants such that $t(n) \lt m$ for all $n < c$.

To bound $t$ from below, let us define function $t_1$ by
  $$t_1(n) = \begin{cases}
    0 & n <= c\\
    t_1\left(\frac{n}{5}\right)  + n & n\gt c
  \end{cases}$$

To bound $t$ from above, let us define function $t_2$ by
  $$t_2(n) = \begin{cases}
    m & n <= c\\
    t_2\left(\frac{n}{5}\right) + (t_2\left(\frac{n}{5}\right) + m) + n & n\gt c
  \end{cases}$$

The rest of this solution will be proving $t_1(n)\leq t(n)\leq t_2(n)$ for all $n\ge 0$ by  induction followed by applying the master theorem to $t_1$ and $t_2$ to show that $t(n) = \Theta(n)$. It is left as an easy exercise for interested readers.


Why do we need "Bloom Filters" if we can use hash tables?

The second paragraph of the Wikipedia article on Bloom filters says the following, with a citation to Bloom's original 1970 paper.

  Bloom proposed the technique for applications where the amount of source data would require an impracticably large hash area in memory if "conventional" error-free hashing techniques were applied. He gave the example of a hyphenation algorithm for a dictionary of 500,000 words, out of which 90% follow simple hyphenation rules, but the remaining 10% require expensive disk accesses to retrieve specific hyphenation patterns. With sufficient core memory, an error-free hash could be used to eliminate all unnecessary disk accesses; on the other hand, with limited core memory, Bloom's technique uses a smaller hash area but still eliminates most unnecessary accesses. For example, a hash area only 15% of the size needed by an ideal error-free hash still eliminates 85% of the disk accesses.

Burton H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM 13(7): 422–426, 1970. (DOI)