Which language is produced by this grammar?

Let's start with the nonterminal $B$. Since all productions of the form $B \to \alpha$ involve only $B$ (and no other nonterminal), we can easily find $L(B) = a^*b$ using Arden's rule. We also have $L(A) = c$. Finally,
$$ L(S) = L(cA) \cup L(bB) = cc + ba^*b. $$


Is there an algorithm to find the best strategy for a game?

Your notion of "strategy" is very ill defined. Exactly what kind of object do you want this algorithm to return? Do you want it to return another algorithm?

There is an algorithm which takes a current board state and returns the optimal move. It's called Mini-Max, you can read about it here. It basically is a depth-first search for a move that doesn't allow for a losing situation. It's called minimax because it alternates for one player minimizing the benefit for player 1 (i.e. player 2) and the other player maximizing the benefit for player 1 (i.e. player 1).

There are techniques, such as Alpha-Beta pruning, which make Minimax faster, however, it is still painfully slow. For Tic-Tac-Toe, it works. For chess, a complete run is completely infeasible. In practice, instead of doing a full search, the search is done to a specific level, and then heuristics are used to evaluate which game states are the most favorable.

So, technically, an algorithm which always returned minimax would fulfill your requirement for a strategy: you could give it a game state and it would output the possible move. However, this is far beyond the capabilities that computers will ever have: expanding the full minimax tree would probably take more memory than there are atoms in the universe.


choose minimum number of M professors in polynomial time in order to design all N course exams

It's a variant of Set cover which is Classical NP-Complete problem.
Here is the problem definition.

Reduction: Take All courses as a Universal set U which you want to cover.
Then make collection of sets $S=\{P_1,P_2,...,P_m\}$ where, $P_i$ is the set of subjects for which a professor $i$ can design a question.
and you can go similarly in reverse direction.

So there is no polynomial time algorithm for your problem unless P=NP.


Determine if there exists a line that intersects all horizontal segments. Better than $O(n^2 \lg n)$?

WLOG, let's rotate your problem so your segments are vertical. Let's say segment $i$ has $x$-coordinate $x_i$ and its low endpoint is $l_i$ and high endpoint $h_i$ (with $l_i < h_i$).

Then our line through it (assuming it exists) has formula $y = ax + b$. Plugging in $x_i$ gives us $y_i = ax_i + b$. And thus we have $l_i \leq ax_i + b \leq h_i$.

Convince yourself that a solution line can always intersect at least one of two points: the one with the highest $l_i$ or the one with lowest $h_i$ (the most extreme requirements).

We try to find a solution line by plugging in one of the two extreme points $p$ (trying the other if the first doesn't work) to find $b = y_p - ax_p$. Then we can substitute to change the inequalities to:

$$l_i \leq a(x_i - x_p) + y_p \leq h_i$$

Now our only variable is $a$ so we can run through the $n$ inequalities, consistently choosing the strictest bounds for $a$ until we find the range of $a$ that works or that there's no solution.

Total runtime is $O(n)$ since we only have to try the above process twice and finding the extreme points also takes only $O(n)$ time.


Complexity analysis of an unsolvable algorithmic problem?

Basically, this is a degenerate case.  We can adopt the convention that the running time of any algorithm is $\infty$ (so its complexity is $\infty$), or we can adopt the convention that it doesn't have a complexity.  For informal conversation, probably it doesn't matter much what convention you adopt, as long as it's clear which you're using and what you mean.

See also how to calculate time complexity of non terminating loops for discussion of the running time of an algorithm that never terminates, and What is the difference between an algorithm, a language and a problem? for background on the difference between the complexity of an algorithm vs the complexity of a problem.


In Ada95 how many bytes does integer occupied in memory?

Ada does not have primitives in the same way as most languages. Instead when you define an Integer or Floating Point Type you provide a range.

The compiler then ensures the Type has that range in whatever underlying type it chooses on that system.

The Standard library does however provide some predefined types...

See http://en.wikibooks.org/wiki/Ada_Programming/Type_System

http://www.adahome.com/rm95/rm9x-03-05-02.html


Arithmetical Hierarchy, show $\Sigma_1$ is Turing recognizable

Suppose that $L = \{x \mid \exists y R(x,y)\}$, where $R(x,y)$ is a decidable predicate.

To recognize $L$, given an input $x$, enumerate all possible $y$, and check whether $R(x,y)$ holds for at least one of them. This will halt iff $x \in L$.


Randomly generating graph based off number of connections on each node

You essentially want to generate a graph with some degree sequence (which you want to be random, but this is not relevant); this is called the graph realization problem which is solved e.g. by the Havel-Hakimi algorithm in the sense that the algorithm will return a (simple) graph with the desired degree sequence if that is possible (such sequences are called graphic). Note that not all finite sequences over $\mathbb N$ are graphic as e.g. any sequence whose members sum to an odd number cannot be graphic by the handshake lemma (which states that the sum of all degrees in a graph is equal to 2 times the number of edges in a graph and thus even).
Further, the solutions will in general not be unique: The degree sequence $(2, 2, 2, 2, 2, 2)$ for example can be realized by the cycle graph $C_6$ of size $6$ or the disjoint union $C_3 \mathop{\dot\cup} C_3$ of two cycle graphs $C_3$ of size $3$ each.
Many graph libraries for programming languages have implementations of algorithms for this problem, for example the Python library networkx.


What is wrong with this solution for $\mathcal{O}({\log({n \choose \frac{n}{2}})})$?

$\mathcal{O}\Big(\log{n} + \log{(n-1)} + \ldots + \log{(1))}\Big)
= \mathcal{O}(\log{n})$

That is not right. When $n$ is large enough,

$$\begin{align}
\log{n} + \log{(n-1)} + \ldots + \log(1)
&\ge \log{n} + \log{(n-1)} + \ldots + \log(n/2)\\
&\ge n/2 \log(n/2)\\
&=\Theta(n\log n)
\end{align}$$

More precisely, since $n!\sim {\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}}$ by Stirling's approximation,

$$\begin{align}
\log{n} + \log{(n-1)} + \ldots + \log(1)
&=\log(n!)\\
&\sim \log\left({\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}}\right) \\
&\sim n(\log(n) -1) \\
&\sim n\log(n)
\end{align}$$

You can take a moment to try understanding intuitively why
$$\lim_{n\to\infty}\frac {\log(n!)}{\log (n^n)} = 1.$$


$u$ can be called the 'head' (or left-hand side)

$v$ can be called the 'body' (or right-hand-side)

sources: source-1, source-2


Understanding the Diameter Constrained MST Problem

The diameter of a graph is the longest shortest-path distance over all pairs of vertices. This distance can be measured in terms of edge weights or in terms of number of edges (which is known as geodesic distance). The measure that you choose depends on your particular application. In the paper that you mention, the authors focus on geodesic distance.

When you want to obtain a Minimum Spanning Tree (MST), you focus on edge weights because all spanning trees have the same number of edges: $|V|-1$.

Aiming for an MST that is constrained by a maximum diameter is perfectly possible. The authors of the paper are not setting two conflicting optimization goals, but, rather, just adding an additional constraint to the MST problem. Adding this contraint, however, turns the MST problem into an NP-Hard problem (even though computing the diameter of a graph and obtaining an MST, separately, are problems that can be solved in polynomial time).

To gain further insight into the notion of diameter (in the context of MSTs), consider the following example:

The spanning tree on the left (whose edges are highlighted in red) is minimum. Its total weight (i.e., the sum of the weights of its edges) is 7 and its diameter is 5 (because the vertices that are farthest from each other are 5 edges apart). If we add the constraint that the diameter must be at most 2 (that is, $d=2)$, then the diameter-constrained MST is the tree on the right. Its total cost is 12 (higher than the tree on the left), but it is the only spanning tree whose diameter (ignoring weights) is $\leq 2$.


Efficiently selecting the median and elements to its left and right

This is a problem of selecting the $k$th smallest element from the list solved by a class of algorithms called the Selection Algorithms. There exist deterministic linear time selection algorithms so your problem can be solved in linear time by selecting the $n/2,n/2-1,n/2+1$th smallest elements from the original unsorted list.


This is known as majority dynamics. Usually the assumption is that all nodes adopt the majority opinion simultaneously, and this is known as the synchronous model. For an arbitrary tie-breaking rule, this converges either to a fixed point or to a cycle of length 2; see for example pages 5-6 of Ginosar and Holzman's The majority action on in nite graphs: strings and puppets. If you break ties in a biased way, then the dynamic probably always converges.

What you describe is the asynchronous model, in which the majority rule is applied in sequence rather than in parallel. In that case the process always converges. See for example Tamuz and Tesler, though their methods are probably overkill for you, since in your case you get to choose the sequence, whereas in their case the sequence is chosen at random.


It is not true. As you know, we can reduce sorting numbers to finding convex hull (see here). So, we know that size of the convex hull, in this case, is $N$. However, we can't compute convex hull in nearly linear time! as lower bound for sorting numbers in general case is $\Omega(n\log n)$.

Anyhow, we have an algorithm to finding convex hull which is output-sensitive and can be run in $O(n\log h)$, which $h$ is the size of convex hull (see here). Hence, if you know the size of the convex hull such that its size is constant, you can compute convex hull in linear time.


Find a string that covers many sets of binary strings with don't-cares

Your problem is NP-hard.  It's basically a variant of SAT.  You shouldn't expect any algorithm that is provably efficient.  Instead, I recommend you use an off-the-shelf SAT solver; since your problem is basically SAT, that's probably about as good as you can do, without a lot of effort tuning for your particular scenario.

NP-hardness: In particular, if every element of every set $S_i$ has exactly $m-1$ don't-cares (has only a single bit set to 0 or 1), then your problem becomes exactly $n$-CNF-SAT with $m$ variables and $N$ clauses.  We know that $n$-CNF-SAT is NP-hard; it follows that this special case of your problem is NP-hard, and thus your problem in general is NP-hard.

Using a SAT solver: Introduce variables $x_1,\dots,x_m$ representing the string you're trying to find.  Then we obtain a formula of the form

$$\Psi(x_1,\dots,x_m) = \bigwedge_{i=1}^N \bigvee_{j=1}^n \phi_{i,j}(x_1,\dots,x_m),$$

where each $\phi_{i,j}$ is a conjunction of literals.  The goal is to find an assignment $x_1,\dots,x_m$ that makes $\Psi(x_1,\dots,x_m)$ true.

You can formulate this as a SAT instance by applying the Tseitin transform.  In other words, introduce variables $y_{i,j}$, then add CNF clauses enforcing that $y_{i,j} = \phi_{i,j}(x_1,\dots,x_m)$ as well as CNF clauses $(y_{i,1} \lor \dots \lor y_{i,n})$ for all $i$.  The Tseitin transform tells you how to add the former clauses.  In particular, you add the clause $(\neg y_{i,j} \lor \neg x_k)$ if the $j$th element of $S_i$ has a 0 in its $k$th bit; add the clause $(\neg y_{i,j} \lor  x_l)$ if the $j$th element of $S_i$ has a 1 in its $l$th bit; and add the clause $(y_{ij} \lor x_k \lor \neg x_l \lor \dots)$ if the $j$th element of $S_i$ has a 0 in its $k$ bit and a 1 in its $l$th bit and so on.  Or, use a SAT front-end that will let you input arbitrary formulas and will do the Tseitin transform for you -- for instance, STP is a nice tool for that purpose.

Then, let the off-the-shelf SAT solver look for a satisfying assignment for you.


If I understand correctly, you have designed a data structure for what is known in the scientific literature as dynamic dictionary problem: keep an index I that can dynamically maintain a set S supporting queries like "is $x \in S$?" under a stream of insertions/deletions.

There are many solutions to this problem. The classical solution is to use a dynamic perfect hash function, which takes $O(1)$ worst case lookup time and $O(1)$ expected amortized update time (it's randomized) and $O(n)$ bits of space.

An arguably more practical solution to your problem is given by Cuckoo hashing, that has the same theoretical bounds of the previous solution but is much easier to understand and implement, and has reportedly better experimental performances.

These solution take much less space than your solution and have favorable time bounds (even if the bound on the update time hold only in expectation).

Moreover, your claim that "add/deletion have no penalty" is unclear to me. If your claim is that an insertion/deletion takes $O(1)$ time, then that's obviously impossible because you cannot build a data structure of size $\Omega(n \log n)$ with time complexity $O(n)$, and if you mean that they take as much time as a look-up, then your solution is no better than any self-adjusting binary tree, like AVLs or Splay trees.

Provided that this problem is well-studied and that there are quite a few high-quality implementations around, I think it is quite hard to design a new competitor that might enjoy commercial success.


Hint: the point $p$ is a vertex of the convex hall iff there are two half-lines from it such that all points fall inside the angle created by them.

Here is an idea for an algorithm based on this hint:

   Design an algorithm with two variables $q$ and $r$ (input points). The algorithm will examine each of the input points and will update $q$ and $r$ so that all points checked so far fall inside the wedge $\angle qpr$.


What is the best known data structure for online dk-NNG?

I'm not familiar with dk-NNG, but have you tried a PH-Tree? It has excellent insertion times and very good kNN search.
I tested several scenarios with up to 40 dimension and $10^6$ and $10^7$ points. It usually competes with R*Tree (R-Star-Tree) for kNN-search, but has much better update performance.

You could also try an R*tree, they are almost always faster than a standard R-Tree. An implementation in Java can be found here.


Time complexity of comparing two $N \times N$ Matrices?

A very simple adversary argument shows that when comparing two vectors of length $M$ (in your case, $M = N^2$), you must query (in the worst case) all positions of both vectors to know whether they are equal. That takes time $\Omega(M)$.


Why isn't a binary counter used for generating $k$-combinations?

For concreteness, suppose you have a string $S$ of length $n = 10$. You want to generate all $k$-combinations of $S$ for some $k$, say $k = 3$. When you use a binary counter (using $n$ bits), you go through $2^n = 2^{10} = 1024$ values, corresponding to all possible subsets. On the other hand, there are only ${10 \choose 3} = 120$ possible 3-combinations choosable from $S$. So wouldn't it be nice if you could only perform 120 steps instead of 1024? I encourage you to play around with larger numbers, and consider how quickly these numbers actually grow.

There might also be other reasons to consider e.g., Gray codes. Some algorithms have particular properties that might be crucial for certain applications. For instance, we might want that there's exactly one change between two adjacent combinations, or so on.


Which machine learning algorithms can be used for time series forecasts?

Here are three survey papers that examine the use of machine learning in time series forecasting:

"An Empirical Comparison of Machine Learning Models for Time Series Forecasting" by Ahmed, Atiya, El Gayar, and El-shishiny provides an empirical comparison of several machine learning algorithms, including:

  "...multilayer perceptron, Bayesian neural networks, radial basis
  functions, generalized regression neural networks (also called kernel
  regression), K-nearest neighbor regression, CART regression trees,
  support vector regression, and Gaussian processes."

"Financial time series forecasting with machine learning techniques: A survey" by Krollner, Vanstone, and Finnie finds:

  "...that artificial neural networks (ANNs) are the dominant machine
  learning technique in this area."

"Machine Learning Strategies for Time Series Forecasting" by Bontempi, Ben Taieb, and Le Borgne focuses on three aspects:

  "...the formalization of one-step forecasting problems as supervised
  learning tasks, the discussion of local learning techniques as an
  effective tool for dealing with temporal data, and the role of the
  forecasting strategy when we move from one-step to multiple-step
  forecasting."


How does treewidth behave under graph minor operations?

The decrease in tree width of any of the three operations will be 0 or 1.  The proof is simple (I will take the case of the vertex deletion).

Let $G$ be the original graph and $G' = G - v$ be the graph obtained by deleting $v$.

Let $T'$ be an optimal tree decomposition of $G'$, with $\text{tw}(G') = w'$.

Now, construct $T$ from $T'$ by adding $v$ to every bag of $T'$.  Clearly, $T$ is a tree decomposition for $G$ with width $\text{tw}(G) \leq \text{tw}(T) = 1 + \text{tw}(G') = 1 + w'$.


Yes, your understanding is right.

The first part (about context-free languages which are decidable) is unneeded. To apply Rice, you only have to show that the property at hand only depends on $L(M)$ (which it does, trivially) and prove that the set is nontrivial. So the whole exercise bogs down to: exhibit $M$ satisfying the reduction property, and $M′$ not satisfying it.

To prove/disprove reduction you may have to use the fact that the language $0^p1^{2p}$ is decidable, as you argued.


Time complexity of code running at most summation(N) times in a loop

If i understand you correctly, then the following holds:
$\sum_{k=1}^nk= \frac{n(n+1)}{2} \ge \frac{n^2}{2} = \Theta (n^2)$

Thus there is no asymptotic gain.


Is there any implementation of AO* algorithm?

I cannot point you towards an existing implementation, but I am pretty confident that it is not too hard to implement yourself. I suggest you to have a look at this paper by Nau, Kumar and Kanal, which has detailed pseudocode for AO* and other related algorithms such as A* and branch and bound. In particular, have a look into Section 7 of that paper and the procedures they call P8 and P9.


I assume that one can also derive some atomic statements from <STMT> and <E-STMT>, otherwise the language of both grammars would be empty and all would be quite trivial. :-) But that aside:

The new grammar should do two things: it should be unambiguous and it should generate the same language.

The variables <E-STMT> and <E-IF-THEN-ELSE> are introduced to remember part of the context in which the variable occurs. What you want to accomplish, is that the variables <STMT>, <IF-THEN> and <IF-THEN-ELSE> cannot occur in a position directly preceeding an else symbol, and also that the variables <E-STMT> and <E-IF-THEN-ELSE> must occur in a position directly preceeding an else symbol. So, if we see a <E-STMT> or <E-IF-THEN-ELSE> somewhere, we know that the next symbol must be else, and if we see an other variable we know that the next symbol cannot be an else. This way we have some week form of "context-awareness".

If we remove the rule for <E-IF-THEN-ELSE> and replace the rule for <E-STMT> by

<E-STMT> -> <IF-THEN-ELSE>

then we can derive the following:

  <STMT> $\to$
  <IF-THEN-ELSE> $\to$
  if condition then <E-STMT> else <STMT> $\to$
  if condition then <E-IF-THEN-ELSE> else <STMT> $\to$
  if condition then if condition then <E-STMT> else <STMT> else <STMT>

and here a <STMT> variable which directly preceeds an else symbol. This will lead to ambiguities.

If we try to fix this and additionally change the if-then-else rule to

<IF-THEN-ELSE> --> if condition then <E-STMT> else <E-STMT>

then we can perform the derivation

  <STMT> $\to$ <IF-THEN-ELSE> $\to$ if condition then <E-STMT> else <E-STMT>

and here we have an <E-STMT> variable without a following else symbol. Since the <E-STMT> generates no if statements without else clause, the language of the new grammar is not the same.

The grammar which was proposed in the book solves both these problems.


Is the language Turing machine-Input pairs for which the computation loops recognizable?

The language $L$ is recognizable: you can build a Turing machine that recognizes $L$ by simulating $M$ and keeping track of all the traversed states. As soon as a state is repeated, you accept. If $M$ halts and no stated is repeated, then reject.
Moreover, $L$ is not decidable. Suppose that $L$ was decidable, then you could do the following to solve the halting problem:

Create a new Turing machine $M'$ behaves as $M$, but instead accepting/rejecting, it goes into some looping state.

Simulate a Turing machine $T$ that decides $L$ to check whether $\langle M', w \rangle \in L$.

If $\langle M', w \rangle \not\in L$ then $\langle M, w \rangle$ must not halt.

If $\langle M', w \rangle \in L$ then either $\langle M, w \rangle$ halts or loops.

Simulate $T$ to check whether $\langle M, w \rangle \in L$.

If $\langle M, w \rangle \in L$ then $\langle M, w \rangle$ loops, and hence it does not halt.

If $\langle M, w \rangle \not\in L$  then $\langle M, w \rangle$ does not loop, therefore it halts.


Do cryptographic hash function solve clustering problems with linear probing?

Cryptographic hash functions are not better than any hash functions with good distribution and "avalanche effect" (eg xxHash) on this regard.

Do they ensure "best possible" lookup performance? In the way you defined that, yes.

Do they eliminate clustering problems? No, clustering is a probabilistic effect that becomes worse as you insert more entries into your hash table, even if they are perfectly distributed. And this effect is already accounted in formulas    of average lookup complexities for linear/quadratic ht algorithm for a given ht load.


Large number of layers in a neural network?

In principle, there is no limit on the number of hidden layers that can be used in an artificial neural network.  Such networks can be trained using "stacking" or other techniques from the deep learning literature.  Yes, you could have 1000 layers, though I don't know if you'd get much benefit: in deep learning I've more typically seen somewhere between 1-20 hidden layers, rather than 1000 hidden layers.  In practice the number of layers is based upon pragmatic concerns, e.g., what will lead to good accuracy with reasonable training time and without overfitting.

Don't confuse artificial neural networks with the brain.  The behavior of artificial neural networks doesn't necessarily tell us anything about the brain, and you can build artificial neural networks whose structure doesn't match anything found in the brain.


Enumerate all pairs, in order of increasing distance, efficiently

Consider all the point on the x-axis, then you are describing sorting $X-X$. A special case of $X+Y$ sorting(one can actually show they are equivalent in terms of running time). This is not known to be sortable in less than $O(n^2 log n)$ time. Interestingly $O(n^2)$ comparisons suffice.


E-Unification: “Goal seeking” pattern matching between directed trees

This is called unification.  There is a one-to-one correspondence between terms and trees; the tree is the parse tree of a corresponding term.  It sounds like you want the most general unifier.  There are standard algorithms for solving this.  However, this doesn't handle equivalence relations like commutativity or associativity.  E-unification might be what you are looking for.


Marginal Probability of Generating a Tree

No.  If $q(x_n,y_n|T_{n-1})$ is arbitrary -- there can be an arbitrary dependence on $T_{n-1}$ -- then this requires exponential time.

Consider a tree $T_N$ that has a single root node, $N-1$ leaves, and an edge from the root to each leaf.  There are $2^N$ subtrees of $T_N$, and in particular, there are $2^N$ possible values of $T_n$ that can occur in the expression

$$\sum_{x, y} \prod_{n = 1}^N q_n (x_n, y_n | T_{n-1} ).$$

One can use a simple adversary argument to prove that evaluating this expression requires exponential time.  Suppose that we evaluate $q_n(x_n,x_n|T_{n-1})$ by querying an oracle with $x_n,y_n,T_{n-1}$.  Suppose there is a single tree $T$ that is never queried to the oracle as any $T_{n-1}$.  Choose all of the $q_n(\cdots)$ values to be strictly positive.  Then since $q_n(x_n,y_n|T)$ wasn't queried during execution, we can choose it after observing the output of the algorithm; but by varying it, we can choose a value that makes the algorithm's output wrong (in particular, the value of the expression depends on $q_n(x_n,y_n|T)$ but the algorithm's output doesn't depend on $q_n(x_n,y_n|T)$, so the algorithm's output cannot correct).  We have proven that, to produce the correct output, any correct algorithm must query the oracle for all $2^N$ possible subtrees of $T_N$.  It takes at least $O(1)$ time to query an oracle.

In conclusion, this argument proves that any correct algorithm for computing this expression must take $\Omega(2^N)$ time.

I don't know whether it can always be done in $O(2^N)$ time, or whether perhaps $O(N!)$ time might be required.


Printing The Longest Path from Root to Leaf in Binary Tree

Though I don't believe this is the most efficient solution to the problem, it definitely works and I figured I would share it here and see if anyone had any feedback.

private static void printMain(BTNode node, String[] path, int arrayCounter) {
    if (node == null) {
        return;
    }

    path[arrayCounter++] = node.data;

    if (node.leftNode == null && node.rightNode == null) {
        printArray(path);
    }
    else {
        printMain(node.leftNode, path, arrayCounter);
        printMain(node.rightNode, path, arrayCounter);
    }
}

This print function adds each node's value to an array until it reaches a node that has a left and right child that is null. This means it has reached the end and the array now has a path from the root node to a leaf node. It's not necessarily the longest path though. Here in the printArray function, it checks to see if the last element of the array is null.

Since the array is initialized to only be as large as the height found in the algorithm in my original question, if the last element is null this is not the longest path. If it is we print.

private static void printArray(String[] path) {
    if (path[max] != null) {
        for (String node : path) {
            System.out.print(node + ", ");
        }
        System.out.print("\n");
    }
}

The added benefit of this approach is that it will print each and every path that is the longest. Meaning if there were 3 nodes that are of height 3, each of the 3 would be printed as opposed to just the one. I still think it could be done more efficiently but this is certainly one solution.


Turing Machine to Accept String from a 3 character alphabet

One idea is to delete characters, to make it easier let me introduce @ character - it will denote empty space after scratching characters.
For example let input string be $BaabccB$, where $B$ is blank symbol.
At first check for $a$ and create state, say $qa$ which looks for $a$ and then replaces it with $@$ switches to $qb$ moves right until it finds $b$.
Then it replaces $b$ with $@$ switches state to $qc$ and moves right until it finds $c$.
Here again replaces $c$ with $@$ and switches to state $ql$ moves to the left until $a$ is found.
While moving right if blank symbol is encountered, it means that there are less symbols of particular character, this is good according to given language, if the next character is also missing otherwise it breaks inequality and we reject. Also when we seek $b$ but encounter $c$ we reject. After consecutive $c$ if there are other symbols, we reject (it is something like $abca$
When moving left, when blank is encountered, we are finished and accept.

It may happen that there are not sufficient number of $a$ or any character, so after reaching blank character we move right to delete $@$ characters. If we clear all and hit blank, we accept, otherwise we reject as some characters broke inequality.

Example: $BaabccB$
$B@abccB$ move right, switch state, replace $b$
$B@a@ccB$ move right, switch state, switch $c$.
$B@a@@cB$ move left until $a$ replace
$B@@@@cB$ move right, switch state, $c$ is encountered in $qb$ state, it means that $#c > #b$ reject.

Excersise 1:
Try to solve similar question where $i \ge j \le k$

Excersise 2:
Try to solve similar question where $i = 2j = 3k$


Finding an element in a sorted array with at most three queries to larger elements

If you have only one life only safe way is to check every element starting from minimal. It's $O(n)$

If you have two lives and limited with $k + 1$ comparisons the minimal element of array you can check first has index $k$, so we still have $k$ comparisons to check all previous elements one by one, if no lives was lost than next element to check has index $k + (k - 1)$ so total numbers of elements we can check is that way $n = k + (k-1) + (k-2) + ... + 1 = \frac{k(k+1)}{2}$ So if you have two lives you can find target element for ($k = \frac{1 + \sqrt{1 + 8n}}{2}$) $+1$ comparisons.
It's $O(\sqrt n)$

So if we have three lives and $k + 2$ comparisons first we should check element of index $\frac{(k + 1)(k)}{2}$ than if we will lost life we will be able to check all earlier elements for $k + 1$ comparisons. So in full analogy $n = \frac{(k+1)(k)}{2} +   \frac{(k)(k-1)}{2} +  \frac{(k-1)(k-2)}{2} + \frac{(k-2)(k-3)}{2} +... + \frac{3\cdot2}{2} + \frac{2\cdot1}{2} = \frac{1}{6}(k+2)(k+1)(k)$

Therefore $n> \frac{1}{6}(k)^3$ and $k < \sqrt[3]{6n}$

So we can solve this for $O(\sqrt[3]{n})$

This is variation of quite known skyscraper and glass or crystal balls puzzle, though I may be didn't find correct name for it in English.


Algorithm for recovering paired lists when elements are broken

Look at the literature on algorithms for the shotgun sequencing and shortest common supersequence problems.  It appears that your problem might not be exactly identical to them, but researchers have developed sophisticated algorithmic techniques for handling this kind of problem.  Therefore, I suspect you might be able to use the same techniques for your problem, or adapt them to work well for your situation.


For an oracle $A\in {\sf P}$ you have ${\sf P}^A={\sf P}$ (since you can encode all requests to the oracle as a submodule of the TM). By the same argument you als have that ${\sf NP}^A={\sf NP}$.

Thus in this case ${\sf NP}^A\neq{\sf P}^A$ would imply ${\sf NP}\neq{\sf P}$.

You basically said this already in your question. Note that we cannot query "exponentially long" strings to the oracle, since we need to write the string on the oracle tape first, and this would clearly take too long. Maybe this caused your confusion?


The Wikipedia proof for the non-deterministic doesn't flip the output. It considers the language
$$ L = \{ (\langle M \rangle, 1^t) : \text{$M$ accepts $(\langle M \rangle, 1^t)$ in space $g(|(\langle M \rangle, 1^t)|)$} \}. $$
This language is in $\mathsf{NSPACE}(g)$. The Immerman–Szelepcsényi theorem shows that if $L \in \mathsf{NSPACE}(f)$ then also $\overline{L} \in \mathsf{NSPACE}(f)$, which leads to a contradiction.


What is 'real time' in a Computer Vision context?

There is no one answer to this question. "Real time" can mean very different things, depending on what kind of sensor or sensors you are using, and what you are trying to do. By the way, editing and storing images may not even qualify as computer vision. Computer vision is about extracting information from images or video, and the meaning of real time depends on the kind of information you are trying to extract.

A typical video camera acquires images at 30 frames per second (fps). So that can be your definition of "real-time", i.e. being able to process images at the rate at which you acquire them.

On the other hand, if your goal is to detect and track objects in videos, then "real-time" is a function of how fast those objects move. For example, 10fps is often sufficient for tracking people walking on the street, but probably not for tracking cars going 70 miles per hour on a highway.


How is $L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $} a regular language?

You don't need to "keep track of $n$ being the same." Another way to write the language is

$$L = \{a^na^ib^jb^n\mid n\geq 1,\ i,j\geq 0\}=\{a^{n+i}b^{j+n}\mid n\geq 1,\ i,j\geq 0\}\,.$$

So, now, given a string $a^sb^t$, you just need to decide if you can choose $n\geq1$ and $i,j\geq 0$ such that $s=n+i$ and $t=n+j$.  If so, then $a^sb^t\in L$; otherwise, $a^sb^t\notin L$. If $s=0$ or $t=0$, we can't choose $n$, $i$ and $j$ as required, since $n\geq 1$. However, as long as $s>0$ and $t>0$, we can take $n=1$, $i=s-1$ and $j=t-1$. Therefore,

$$L = \{a^sb^t\mid s,t\geq 1\}\,,$$

which is the language matched by the regular expression $aa^*b^*b$.


In answer to both of your questions:
  Firstly, note that during the maintenance phase of the loop invariant proof, we are in the process of inserting u into S, and the way that y is defined is that it is a node in V\S while this is happening, therefore u and y exist in V\S at the same time when u is inserted. This answers your first question.
  Secondly, note that in the proof, we assume that u.d ≠ δ(s,u). It therefore follows that there would be a pair of nodes x and y (such that π(y)=x such that x ∈ S and y ∈ V\S) such that y ≠ u and therefore y must come before u, because otherwise from the Convergence Property it would automatically follow that u.d = δ(s,u) which would be a contradiction to our assumption. Therefore from here it must follow that y comes before u. But note that from the first point I made above, y must come after u. And this is exactly the whole point of the proof, both of these things cannot happen simultaneously unless y.d = δ(s,y) = δ(s,u) = u.d.
Note that we used the assumption that u is not the minimal distance from s when added to S by showing that we reach a contradiction if we assume this.


A programming language that can only implement computable bijective functions?

There is no such language.

However, have a look at Boomerang. It is a language for writing bijections between strings. I do not know how wide a class of maps is expressible in it, but I am sure you can find out if you search a bit.

It is reasonable to require of a programming language that the set of valid programs be recognizable by an interpreter or a compiler, i.e., that it be a computably enumerable set. Suppose then we had a programming language whose set of valid programs were computably enumerable and which implemented precisely all computable bijections $\mathbb{N} \to \mathbb{N}$. That would imply that we can computably enumerate all computable bijections (simply enumerate all valid programs in this programming language), but this is impossible by the next theorem.

Theorem: Suppose $f_0, f_1, f_2, \ldots$ is a computable sequence of computable bijections. Then there is a computable bijection which is not in the sequence.

Proof. We construct a bijection $g : \mathbb{N} \to \mathbb{N}$ as follows. To define the values $g(2 k)$ and $g(2 k + 1)$, we look at $f_k(2 k)$:

if $f_k(2 k) = 2 k$ then set $g(2 k) = 2 k + 1$ and $g(2 k + 1) = 2 k$,
if $f_k(2 k) \neq 2 k$ then set $g(2 k) = 2 k$ and $g(2 k + 1) = 2 k + 1$.

Clearly, for every $k \in \mathbb{N}$, $g$ is different from $f_k$ because $g(2 k) \neq f_k(2 k)$. Furthermore, $g$ is computable and it is a bijection because it is its own inverse. QED.


Switching Lemma and AC0 reductions between SAT problems

It is hard to see how you would use the fact that the target of the reduction is 2SAT rather than, for example, 3SAT.

The common way one applies the switching lemma is roughly this. Apply a random restriction that fixes all but a $\lambda$ fraction of the inputs, for some small parameter $\lambda$ which depends on the parameters (size and depth) of the AC0 circuits in question. Then with constant probability, the function computed by the AC0 circuit becomes constant.

Applying this in our case, we have fixed all but $\lambda n$ of the inputs, and in return, some $\mu$ fraction of the outputs is fixed. And now what? We don't know anything about the reduction, so it's not clear how to obtain a contradiction. What's more, I don't see how you would use the fact that the target problem is 2SAT rather than, say, 3SAT, in which case there can be no contradiction.

The switching lemma is at its best when you have a concrete function in mind and you want to prove AC0 lower bounds for this specific function. Another, less typical, use of the switching lemma is to prove some general properties of any function computed by an AC0 circuit. The most famous example is Linial–Mansour–Nisan, which gives bounds on the rate of decay of the Fourier spectrum. It's not clear how you'd use information like this in your case.


Data structure with search, insert and delete in amortised time $O(1)$?

NO.

Fredman and Saks proved that any data structure that supports these operations requires at least $\Omega(\log n/\log\log n)$ amortized time per operation.  (This is reference [1] in the paper by Dietz that you mention in your first comment.)  The lower bound holds in the very powerful cell probe model of computation, which only considers the number of distinct memory addresses accessed by the update and query algorithms.

Without some additional assumptions about the update and query operations, Dietz's data structure is the best possible (at least up to constant factors).


Bipartite graph minimal amount of vertices required

Let's define a graph $G=(V,E)$, for which:

Set of vertices $V$ is identical to your SET1.
Two vertices $v_1,v_2 \in V$ are connected by an edge, if and only if there exists a vertex from the SET2, incident to both $v_1$ and $v_2$ in your bipartite graph.

For instance, the graph below corresponds to the bipartite graph from the example in your question:

Now, your problem is reduced to the Minimum Vertex Cover problem on the graph $G$, defined above, so you'll be able to use known algorithms to find minimum vertex cover in your SET1 only.

This graph $G$ doesn't have any special structure, which could be used to find its minimum vertex cover more effectively than in general case. Also, any graph can be transformed to your bipartite graph form by splitting each edge by a new vertex. So, it means that your problem is equivalent to the minimum vertex cover problem, which is NP-complete - thanks to @narekBojikian for mentioning that in his answer.


Finding the shortest path for synchronized pawns in a maze

I am going to take a guess that you are having trouble with understanding how BFS will work on this game. First, you may wonder "what is the graph we are searching on?" Let's first start with, you are not searching through the game board. This is not what you are doing at all.

How to represent Game State

You are search through game states. I am using game state to mean:

  Game state - a full and unique description of all pieces/players in the game at the start of any "turn" during the duration of game play. A game state is final when pieces are in a position that satisfies the termination constraint.

Termination constraint as you have define is when two pawns are both able to leave the grid with the same move. You could alternatively define it as a state right after this move has been made.

Here are some examples of game states that can be uniquely describe by a $3 \times 8$ matrix $G$ where we make each entry either: Red, Blue, White, or Black.:

We would have $G_{1,1} = \text{Blue}$ and $G_{1,4} = \text{Red}$ and assign the rest of $G_{i,j}$ appropriately.

We would have $G_{0,1} = \text{Blue}$ and $G_{1,3} = \text{Red}$ and assign the rest of $G_{i,j}$ appropriately.

We would have $G_{0,6} = \text{Blue}$ and $G_{1,1} = \text{Red}$ and assign the rest of $G_{i,j}$ appropriately.

One important thing to note here is that the only thing changing in these game states is the location of Red and Blue, everything else stays the same. This should give you some indication that we only need to maintain the location of Red and Blue to get a unique description of the game state. With this idea, we can represent all three of the prior games states as:

$\text{Blue} = (1,1)$ and $\text{Red} = (1,4)$
$\text{Blue} = (0,1)$ and $\text{Red} = (1,3)$
$\text{Blue} = (0,6)$ and $\text{Red} = (1,1)$

To be concise I will represent them as pairs of coordinates:

State = $[(1,1), (1,4)]$.
State = $[(0,1), (1,3)]$.
State = $[(0,6), (1,1)]$.

Another important thing to note here, is that the states do not need to be "possible" in the sense that we can always reach them from our initial state. The purpose of using these states is so that we can create a graph to BFS.

Graph Representation of Game States

To be able to properly "search" through the game states, we will make each state a node in our abstract graph. We will add an edge from state $s_1$ to state $s_2$ if we can get from state $s_1$ to state $s_2$ by moving both players either Up, Down, Left, or Right. Using our first example:

State $[(1,1), (1,4)]$ can move to:

State $[(0,1), (1,4)]$ via the Up move.
State $[(1,0), (1,3)]$ via the Left move.
State $[(1,1), (1,4)]$ via the Down move.
State $[(1,2), (1,5)]$ via the Right move.

So in a graph it would look like this:

How to BFS Game States

We will be looking for the shortest sequence of moves such that we reach a final state. For instance, $[(0,1), (0,6)]$ would be a final state because they can both move Up to leave the grid. One option would be to create the entire graph, then run the BFS from our start node. However, this can be costly. We can instead generate nodes adjacent to our current node on demand. We can also check if we reach a final state on demand. We need to also make sure we cannot visit "invalid" board states. For instance $[(-1,1),(1,4)]$ would be invalid because "-1" is outside our bounds. $[(0,0), (1,4)]$ would also be invalid because $G_{0,0}$ is a black square and we cannot move there.

This should be enough information to get you started. I will leave the analysis up to you. A hint on the analysis would be to consider how many game states are possible as we know in the worst cases we may visit each and all of them.


Is $\{\varepsilon\}$ a conventional way to mark the empty language?

No, that's the language containing one string: the empty string, which is very much distinct from the empty language. The finite state machine on the left accepts language $\{\}$, the finite state machine on the right accepts language $\{\varepsilon\}$. They are not the same.

If a lot of students are confused maybe explicitly show the difference in an exercise/during a lecture.

As an example, we could use the language as a password check. Anyone submitting an accepted word would be let through. Then $\{\}$ means "let no one in" and $\{\varepsilon\}$ means "let anyone that submits a blank password in". Those are quite different indeed!


Is bounded waiting ensured in given version of Dekker's solution for critical section problem?

A reasonable definition of bounded waiting is:

  After a process made a request to enter its critical section and before it is granted the permission to enter, there exists a bound on the number of turns that other processes are allowed to enter.  [1]

In your case each process makes its request to enter by setting its flag (line 5 for Process 0, line 20 for Process 1.  The granting of permission is the test of the other process' flag (flag[1] false on line 6 grants permission to Process 0, flag[0] false on line 21 grants permission to Process 1).

So the only way to test the bounded waiting requirement here is to consider the case that Process 0 has just tested flag[1] on line 6, and found it true, and ask, "how many times can Process 1 leave and reenter the critical section while Process 0 is stuck in the loop?"  (Hint: consider the case where Process 0 has really bad luck, and Process 1 is able to leave and reenter the critical section during Process 0's delay on line 9).

[1] source: http://www.csl.mtu.edu/cs3331.ck/common/05-Sync-Basics.pdf


Modelling 2 object situation with Propositional Logic

Let $P_1$ indicate that Tree 1 has leaves (i.e. $P_1$ is true if Tree 1 has leaves), and $P_2$ indicate that Tree 2 has leaves. Sign 1 states $S_1 = P_1 \land \lnot P_2$, and Sign 2 states $S_2 = (P_1 \land \lnot P_2) \lor (\lnot P_1 \land P_2)$. We are given that $R = (S_1 \land \lnot S_2) \lor (\lnot S_1 \land S_2)$.

In order to solve this, we simply calculate $S_1,S_2$ for each of the possible truth assignments of $P_1,P_2$:
$$
\begin{array}{cc|cc|c}
P_1 & P_2 & S_1 & S_2 & R \\\hline
F & F & F & F & F \\
F & T & F & T & T \\
T & F & T & T & F \\
T & T & F & F & F
\end{array}
$$
The only truth assignment for which $R$ holds is $P_1 = F$, $P_2 = T$. We conclude that Tree 1 has no leaves and Tree 2 does have leaves.


Maximize vertex cover weights with bounded edge weights in a connected subgraph

This is already NP-hard in the special case that the graph is a tree, since Knapsack can be reduced to such an instance of this problem: Let $v_i$ be the value of the $i$-th item, and $w_i$ its weight.  Create a vertex of weight $v_i$ for each item $i$, and a single extra vertex that is connected by an edge of weight $w_i$ to each item $i$.  A capacity-$b$ knapsack can be filled with items of value at least $k$ iff the solution to the constructed instance of your problem with total edge capacity $b$ can achieve a total vertex-value of $k$.


propositional Modal logic filtration definition

You are probably looking for something like:
$L_\Gamma([w]) = L(w) \cap \Gamma$. This will falsify any propositional letter not in $\Gamma$.

(Filtration is (afaik) usually defined as a property that a model may have. There could be several (or none) concrete models satisfying this property.)


how do I find a undecidable subset of a set that's decidable?

Hint: For every language $L$, the language $M = \{ 1^{2x+1} : x \in L \}$ is a subset of $S$.


Number of sentences and sentential forms generated by a grammar

If the context-free grammar is unambiguous, you can count the number of sentences it generates in a linear scan with a carefully chosen order.
I'll assume we have removed all useless symbols and cycles from the grammar.  If it is finite and free of useless symbols and cycles, then it should not contain any recursion.
Let $N(A)$ denote the number of sentences that can be constructed starting from nonterminal $A$, i.e., $N(A) = |L(A)|$.  If the grammar is unambiguous and has no recursion, you can compute $N(A)$ for each nonterminal as follows.  Construct a dependency graph with one vertex per nonterminal, and an edge $A \to B$ whenever the grammar contains a rule $B ::= \cdots A \cdots$, i.e., a rule with $B$ on the left-hand side and $A$ on the right-hand side.  If the grammar has no recursion, then this is a dag.  Visit the vertices of this graph in topologically sorted order.  Then it is easy to compute the number of sentences: for example, if we have the rule $A ::= BaC | DE$, then we have
$$N(A) = N(BaC) + N(DE) = N(B) N(a) N(C) + N(D) N(E).$$
That's an example, but you can do the same for any number of alternatives on the right-hand side and any string of symbols in each alternative.  Note that we have the base case $N(a) = 1$, for any terminal $a$.
I expect this can be adjusted to count the number of sentential forms as well, but I haven't tried to work out the details.
This relies crucially on the grammar to be unambiguous.  If the grammar is ambiguous, I'm not sure whether there is any efficient algorithm -- I just don't know.
For unambiguous grammars, see also https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger_enumeration_theorem, which shows how to count the number of sentences of a particular length, even if the grammar is not finite.


Magic Square Check for NxN Matrix - with Minimum Complexity?

If you have an $N \times N$ matrix, then it has $N^2$ entries, and as you need to check all entries at least once to see if the square is a magic square, any algorithm must have a running time of $\Omega(N^2)$.

For a square to be a magic square, all rows, columns and both diagonals must sum to the same number. There are $N$ rows, $N$ columns and 2 diagonals, each of which have $N$ entries, so you can check this property in $O((2N+2)N) = O(N^2)$ time.

Combining the above: verifying the magicness of a square is in $\Theta(N^2)$.


The number of "work" being done, should be counted with the big-O notation. This means - that you count the while loop as $O(n)$  and any other constant work done (for example, the work after the while) is $O(1)$ and $O(n)+O(1)=O(n)$ so it wont make a difference.

Counting the "work" without big-O is not well-defined in the general case - so you should avoid it altogether


Is there a described algorithm converting _from_ Continuation Passing Style?

I did some additional research to answer this question but find nothing better suited.

To do reverse of CPS to direct programming you have to assign functions to variables, this makes direct structural code.

Automated and well described technique comes from compilers - SSA (Single Static Assignment).
This has additional bonus like compacting code and constant propagating to some extend.

This is not per se technique to reverse CPS, but structure of assignments creates direct code, so it is usable in your situation.


How to prove that one problem belongs to class P?

Yes. In fact, any algorithm that runs in polynomial time counts. For examle, even an $O(n^8)$ would suffice! Therefore, there is no real need to optimize your algorithms to such extremes.


Libgpuarray is package (like in proxy or wrapper) around cuda and opencl ndarray - meaning that computation is done on device side (GPU side) as opposed to host side (CPU).
This is described in documentation, and also defined what were the goals of this particular library.

It makes sense to talk about "faster" in terms of GPU if we are having a lot of data, which can be solved on different threads or vectorised (SIMT - new to Flynn taxonomy due to massive parallel but limited computation).

Strictly sequential algorithms benefit nothing, CPU has higher power for them, because GPU cores are slower.
It is not like it is fancy to compute on GPU disregarding problem statement.

On GPU you have smaller and constrainef memory, you have to take bandwidth (sending data from host to device, computation time and sending results from device to host) ti know whether there is speed up or slow down effect on your program.


There are many "complete bases" for operations on strings. One is based on the representation
$$ \Sigma^* = \epsilon + \Sigma \Sigma^*. $$
In words, a string is either empty or is composed of a character and a string. In order to use this representation, we need the following functions:

nil – the empty string
cons(x,s) – the string consisting of the character x followed by the string s
null(s) – true if s is empty
car(s) – returns the first character of a non-empty string
cdr(s) – returns the string resulting from removing the first character of a non-empty string

The terminology is from Lisp; cdr is read could-er or cudder.

Another basis considers strings as arrays. There is a standard basis for reading strings:

len(s) – the length of s
s[i] – the character at position i

For writing strings there are several options. In the immutable case, one choice is:

"" – the empty string
str(x) – the string consisting of the character x
cat(s1,s2) – the string resulting from concatenating s1 and s2

If strings are allowed to be mutable, we can add an operation s[i] = x, changing the character at position i to be x.

One can think of many other bases. Some will be more efficient than others. It all depends on what exactly you are trying to capture, what your goal is.


Traditionally, in computability theory all problems are encoded in terms of numbers, or sometimes strings of bits $0$ and $1$. This is a very "low level" kind of thing, it is like programming directly in machine code. The reason for doing this is mostly historic. Gödel originally encode first-order logic in terms of numbers to prove his incompleteness theorems. Similarly, if one approaches computability through recursive functions, it is natural to encode everything with numbers. And mathematicians just like numbers anyway.

A computer scientist would recognize the benefits of using a more advanced programming language that supports datatypes. Programmers know that programming in machine code obscures a lot of ideas and makes everything technically difficult. Mathematicians know this too, but since they do not actually write code, just think about writing code, they do not appreciate this point of view sufficiently to switch from their traditional ways.

So, to answer your question, here is a modern way of defining decision problems. Pick your favorite general-purpose programming language. Consider a datatype $D$ (can be numbers, lists, heaps, trees, whatever) and decompose the values into two disjoint sets $D_0$ and $D_1$, so that $D_0 \cap D_1 = \emptyset$ and $D_0 \cup D_1 = D$. Observe that $D_1$ uniquely determines $D_0$ and vice versa, because $D_0 = D \setminus D_1$. So we only have to specify $D_1$.

Now, a decision problem $(D_0, D_1)$ is said to be decidable if there is a program $p : D \to \mathtt{bool}$ such that:

$p$ is total, which means that $p(d)$ halts for every $d \in D$,
if $d \in D_0$ then $p(d) = \mathtt{false}$,
if $d \in D_1$ then $p(d) = \mathtt{true}$.

All that stuff about encodings and finite words over an alphabet etc. is not necessary. It is only useful if you want to prove general theorems about arbitrary decision problems. But if you want to think about a specific decision problem, it is better to do it directly in your favorite programming language.


Here is a simple definition for greedy algorithm.

There are many greedy algorithms for different problems and in order to understand them you must also know well the subject of the problem. This question on stackoverflow gives some examples of greedy algorithms usage.

EDIT :  After you made your question more clear I will try to sketch the algorithms by using "minimum mathematical notation".
Both the Kruskal's and Prim's algorithms build MST in connected graph.

Let we have graph G with vertices V and edges E.

Prim's algorithm

Select some vertex r from V and add it to the tree. r will be the root of the tree
Until all vertexes V are in the tree :

Find the shortest edge from E that has one end in the already constructed tree and the other in some of the vertices of the graph that are not in the tree and add the edge and the new vertex to the tree
When the condition in step 2. is not correct you will have the MST constructed

Kruskal's algorithm

Construct forest of trees where each tree is a single vertex from V
Until all trees are connected into single one :

Find the shortest edge from E that connects two unconnected trees and connect them with it. That step constructs from two trees a new one.
When the condition in step 2. is not correct all the trees will be connected into single one that is the MST

Note: After each iteration we have a tree/trees because there is no way to add a edge that forms a cycle

Note: The tree consists of vertexes and edges (it is kind of graph). When adding a vertex to the tree we add it to the set of vertices and when adding edge - to the set of edges.

Running Time

This part really needs mathematical notation and depends on specifics in the implementation of the algorithms, so I will leave it only with some answers and links to Wikipedia,where there are some general explanations.

Prim's Algorithm = O(E.log E) = O(E. log V)

Kruskal's Algorithm = O(E.log E) = O(E. log V)

Please read the explanations and ask only the things that are unclear to you(maybe in different question if they are related to the asymptotic notations)

"Greedy Part"

The greedy part in both of the algorithms is choosing to add the shortest edge to the tree. The shortest edge is the logically optimal choice when constructing Minimal Spanning Trees.


Why can KARP reductions be used to define completeness for complexity classes in the polynomial hierachy?

Suppose that $f$ is the polynomial reduction between $L'$ and $L$, i.e. $x \in L' \Leftrightarrow f(x) \in L$. If $L \in \Sigma_k^p$ then $y\in L \Leftrightarrow \exists z_1 \forall z_2 \ldots M(y, z_1, \ldots z_k) = 1$. Then $$x\in L \Leftrightarrow f(x) \in L \Leftrightarrow \exists z_1 \forall z_2 \ldots M(f(x), z_1, \ldots z_k) = 1 \Leftrightarrow \exists z_1 \forall z_2 \ldots P(x, z_1, \ldots z_k) = 1$$  $P$ first computes $f$, then applies $M$, so it's polynomial.


Well, a very similar concept, called Tagsystems is an early universal model developed by Post. Here is the description from wikipedia:

  A tag system is a deterministic computational model published by Emil
  Leon Post in 1943 as a simple form of a Post canonical system. A tag
  system may also be viewed as an abstract machine, called a Post tag
  machine (not to be confused with Post-Turing machines)—briefly, a
  finite state machine whose only tape is a FIFO queue of unbounded
  length, such that in each transition the machine reads the symbol at
  the head of the queue, deletes a constant number of symbols from the
  head, and appends to the tail a symbol-string that depends solely on
  the first symbol read in this transition.

It is explained in the introductory part of a paper by Woods and Neary for FOCS 2006 that small universal TM's are actually built from small universal Tag-systems. Hence there is a big competition in finding small Tag-systems.


Here's an alternative to recursion:

You have 3 different outcomes. You can assign each outcome to a digit in $[0, 1, 2]$. E.g. 0 means loosing, 1 means draw, 2 means win.

Then you can represent one combination as a series of digits, e.g. $[1, 1, 2, 0, ...]$ (first two matches ended in a draw, the third one was won, ...).
And you can interprete this series as the digits of a number in base 3.

So obviously all combinations can be described using a number between $0$ and $3^{\#matches}-1$ and you can very easily iterate over them:

for combination in 0 .. 3^(#matches)-1:
    results = combination in base 3 (exactly #matches digits)
    process results


You have 100 examples of the positive class and 100 examples of the negative class.

Now you do:

examples = "List of all 200 examples"
accuracies = Empty list
for(i=0; i<|examples|; i++) {
    one = examples[i]
    training = examples \ {one}

    # !!!!!!!!!!!!!!!!!!!!!!!!!
    majority_clf = get majority in training. This is the other class than the class of "one"
    # !!!!!!!!!!!!!!!!!!!!!!

    accuracies.append(majority_clf.predict(one) == class(one))
}
overall_accuracy = sum(accuracies) / |accuracies|


Length of distinguishing string for a DFA

Distinguishing strings can, in general principle, be of any length, though the specifics will depend on the automaton and states that you're looking at.

For example, consider the usual automaton that accepts even-length strings over the alphabet $\{1\}$. We have states $q_\mathrm{e}$ (which is the start state and is accepting) and $q_\mathrm{o}$ (which is not accepting), and the transition function just swaps state every time a character is read.  For this automaton, every string over $\{1\}^*$, including the empty string, distinguishes the two states. Strings of even length (including $\epsilon$) distinguish because they're accepted by $q_\mathrm{e}$ and rejected by $q_\mathrm{o}$; odd-length strings are the other way around.


What is the range of possible IP addresses when expressed as decimal and hexadecimal?

The number of possible addresses is unaffected by the base you are using to write the addresses. The base is irrelevant to the problem of counting how many possible addresses there are.

Note that the $256^4$ figure you obtained is equal to $2^{32}$. In hexadecimal, the addresses range from $00.00.00.00$ to $\text{FF}.\text{FF}.\text{FF}.\text{FF}$, which gives $16^8 = 2^{32}$ possible addresses. To reiterate: the base only determines how you write the addresses, not the numerical values the address has. There are always $2^{32}$ distinct addresses.


You asked why the "3" is there in that equation.  Here's the explanation.

$t_i$ counts the number of iterations of the inner loop, for a particular value of $i$.  Each iteration executes 3 instructions (3 steps).  Therefore, the total number steps of computations consumed by the inner loop, for a particular value of $i$, is $3 \times t_i$.


When did commercial Speech Recognition first begin using grammar (sentence structure) for prediction?

As far as I know, much of the speech recognition software is build using Hidden Markov Models (HMM) where observations are individual sound phonemes, and the states correspond to words (or some partitions of the words).

I don't think the systems take into account grammar or sentence structure in the sense that they encode rules of English so much as they naturally pick up common structure from training. Because inferring the state in an HMM is based on both the observation (the sound) and the previous state, by adding more training sequences it is possible to capture typical phrases.

For example, there are likely several instances in the training data where the word "English" is followed by the word "grammar", whereas there are very few where it is followed by "grandma", thus the dynamic aspect of the model will capture these connections naturally.


Does amortized complexity always equal to worst case complexity divided by n?

No, if all we know about an operation is that it takes $O(f(n))$ times, then its amortized time is also $O(f(n))$. Sometimes, however, it is the case that while the worst-case running time is $O(f(n))$, the worst case cannot happen all the time. A good example is dynamic arrays. Suppose we want to maintain an increasing array, but we don't know in advance how big the array is going to be. Therefore we use the following algorithm for inserting an element to the array; in the algorithm, $N$ is the current length the array, and $n$ is the current number of elements in the array, both initialized to $1$:

If $n = N$, create a new array of length $2N$, copy the old array into the new array, and free the old array.
Add the new element to the end of the array.

When $n < N$, this operation takes time $O(1)$. However, when $n = N$, we need to copy the entire array, and so it takes $O(n)$. The running time of insertion is therefore not even bounded! Nevertheless, the amortized running time of insertion is $O(1)$. Intuitively, the reason is that the expensive copying operation is very rare.

Indeed, suppose we perform $m$ insertion operations. The expensive operation occurs at the first, second, 4th, 8th, 16th, and so on, insertions, and involve copying $1,2,4,8,16,\ldots,M$ elements, where $M \leq m$. The total number of elements copied is $1+2+4+8+16+\cdots+M = 2M-1 < 2m$, and so the total running time is $O(2m) + O(m) = O(m)$, the first summand corresponding to the copying operations, the other corresponding to the cheap second step of the algorithm above. The amortized running time is therefore $O(m)/m = O(1)$.

There are several methods to prove upper bounds on the amortized running time, such as the accounting method and the potential method. These are just mathematical tricks that are supposed to help you analyze algorithms, though as the example analyzed above shows, you don't really need to use them formally in order to analyze the amortized running time; it's enough to use the definition of amortized running time. In more complicated cases these methods could be more helpful, though I feel that they are being taught mostly for historical reasons such as their inclusion in some influential textbook.


What am I missing in this application of Dijkstra?

current should be the unexplored with the lowest cost. Which means that after you explored $B$ you should have explored $D$ because $2<4$.


Efficiently shuffling items in $N$ buckets using $O(N)$ space

Step 1. Store the buckets cumulatively. E.g. instead of storing $[3, 5, 2, 2]$ you store $[3, 8, 10, 12]$. This allows you to find using binary search in $\log n$ time what bucket the $k$th (out of $T$) item belongs to (and by extension which $a_i$ to output).

Step 2. Use a memory-less permutation of the range $[1, T]$. I personally like Sometimes-Recurse Shuffle. A memory-less permutation can give you $\pi(k)$ directly for arbitrary $k$ in $\log T$ time. Some example code I have written a couple years back show how simple it is (with toy PRF implementation - replace that): https://gist.github.com/orlp/33535eefce782a59e185e4a971cda1a3.

Step 3. To actually shuffle simply enumerate $k = 1, 2, \dots$, compute $\pi(k)$ using the memory-less permutation, and find which bucket $\pi(k)$ belongs to output the proper $a_i$. Total time complexity is $\log(T)$ per item, or $T \log(T)$ for the whole permutation.

The advantage is that you don't have to compute the whole permutation, you can also just directly compute the $k$th element in the permutation.


How to relate circuit size to the running time of Turing machine

The way to show that circuits are equivalent to TMs is as follows: for a TM, you encode it in binary (i.e states, transitions, etc.)

Then, you construct a circuit whose gates represent the transitions between each configuration of the TM. Since configuration transitions are local, then you only need local gates (i.e gates that depend on a constant number of inputs).

The idea is that you can compute configuration $c_i$ from configuration $c_{i-1}$ by examining the contents of 3 adjacent cells, and if the head of the machine is there, update them accordingly. It's rather technical to write formally, but it's a generally simple proof (See "Computational complexity" by Arora and Barak for a proof).

Using this proof, you see that the size of the circuit is polynomial in the running time of the machine and the input length, because the circuit is constructed in "levels", where each level corresponds to a configuration of the TM.


How does the length of the output of a problem inform its complexity?

No, it's not an optimization problem.  It takes at least one step of computation per bit or word of output (depending on the model of computation), so since the output can be $\Omega(2^N)$, that means the worst-case running time will be $\Omega(2^N)$, no matter what algorithm you use.  Thus, the complexity is $\Omega(2^N)$.

Yes, the size of the output is a lower bound on the running time to produce that output.


A multi-user, multi-processing operating system cannot be implemented on hardware that does not support

None of the above.

As you noted, DMA and demand paging can be useful features but are not necessary to support multiple users and multiprocessing.

Address translation is not necessary even for memory protection. Memory protection can be separated from address translation via a protection lookaside buffer or memory protection unit.

Providing a distinct privileged operating mode in the processor is not necessary for a multiuser system. In theory, provable trust of software can provide protection against misuse by users. Another alternative is capability systems; one can use non-forgeable fat pointers to provide resource protection.


Methods for proving upper bound on a-approximiation algorithms?

You mention two results giving tight bounds on the approximability of MAX-E3SAT: an upper bound (algorithm) and a lower bound (hardness). The upper bound is much simpler than the lower bound in this case. Indeed, using basic probability you can show that a random assignment satisfies $7/8$ of the clauses in expectation, which gives an approximation algorithm whose approximation ratio is at least $7/8$ in expectation. If you don't like randomized algorithms, this algorithm can be derandomized using the method of conditional expectations.

The other direction is much harder, and relies on the PCP theorem and Raz's parallel repetition theorem. It was shown by Håstad in his seminal paper Some optimal inapproximability results. This is all described in Arora and Barak's textbook, but I warn you that the textbook is quite advanced.


What language can be created from a regular expression with nulls?

The regular expression $\emptyset$ matches nothing at all: not the empty string, not any non-empty string.

Any concatenation with $\emptyset$ also matches nothing: a string would only match $d\emptyset$ if it could be divided into some part that matches $d$ and some part that matches $\emptyset$, but no such part exists.  So $d\emptyset$ is the same thing as $\emptyset$: it matches nothing at all.

An alternation ("or") of something with $\emptyset$ has no effect: $c\epsilon+\emptyset$ means "anything that matches $c\epsilon$ or matches $\emptyset$" and that's just "anything that matches $c\epsilon$."

So $c\epsilon+d\emptyset$ is the same thing as $c\epsilon$ which, in turn, is the same thing as $c$.  The regular expression you quote is equivalent to the simple $c^*$.

Conceptually, $\emptyset$ plays a similar role to zero in addition and multiplication. Adding zero to anything doesn't change it, just as alternation of a regular expression with $\emptyset$ doesn't change it. Multiplying anything by zero makes it equal to zero, just as concatenation of any regular expression with $\emptyset$ turns it into $\emptyset$.

$\emptyset$ might seem rather pointless as a regular expression. It's needed because, without it, the empty language (the one with no strings at all in it, i.e., the set $\emptyset$) wouldn't be regular. To see this, it's not hard to prove by induction that every regular expression that doesn't contain the character $\emptyset$ must match at least one string. However, we want the empty language to be regular, because it's accepted by an automaton – in fact, by any automaton with no accepting states.


Proper terminology in Prolog/logical programming theory?

If you understand Prolog then you're probably fine. The jargon in Prolog-land is not as fixed as you'd expect, because we really only have three things to refer to, with a dozen or more pieces of jargon to use on. These are my working definitions arrived at from reading books and reading/answering questions about Prolog on Stack Overflow. I may have a misconception in here.

This is a Horn clause:

foo(X) :- bar(X).

It has two components: the head, which is foo(X), and the body, which is bar(Y).

A fact is a Horn clause consisting of just a head:

uncle(bob).

In ISO Prolog, this is transformed into the equivalent clause:

uncle(bob) :- true.

Similarly, a Horn clause with only a body is just a goal or a query:

:- uncle(X).

A predicate is defined by a set of clauses. For instance:

foo(true).
foo(X) :- bar(X).
foo(X) :- succ(X0, X).

The predicate foo/1 is thus defined. The 1 there is the arity. Every clause is a rule. I can talk about a bug in the second rule of the predicate or the second clause of the predicate, and in either case I am clearly referring to foo(X) :- bar(X).

"Goal" and "query" can be used interchangeably. You can prove or call a goal. I would "issue" a query, not sure if others would say that. When a Variable is given a value, I would say the variable unifies with value or the variable receives value. A goal, query or call can succeed or fail (not "return true" or "return false"). When it succeeds, its variables will be bound.

So to answer your questions directly:

A predicate is a unit of code with a name and arity. Its definition is composed of one or more clauses. Each clause can be a rule or a fact, but that distinction is trivial and fairly useless. A predicate is made up of facts and rules. Every fact and every rule is a clause and implies a predicate.
Every clause is an alternative of some predicate. Every predicate has at least one clause.
Predicates can be called. Goals can be proven or called. Queries can be satisfied. Rules are not called (instead, they are chosen out of the set of alternatives while evaluating some query). (foo(X), bar(X)) is a compound goal, more likely called a query (but never called a predicate).
Goal and query are the same.

This is confusing in Prolog because the same syntax is used everywhere. So when you see foo(X), it might be a fact, or it might be a query. It can be given to a meta-predicate to be proven or it can be used simply as a structure. For instance:

foo(X).           % 1. "fact": foo(X) always succeeds.
foo(X) :- true.   % 2. "predicate", same as above
:- foo(X).        % 3. goal: prove foo(X). Will succeed without establishing binding.
:- call(foo(X)).  % 4. goal, same as above
:- write(foo(X)). % 5. struct: print out "foo(_G1657)" (or some other gensym variable name)

For me, what's still vague is when we refer to a term as a structure versus as a functor. I think these usages are basically interchangeable, but I'm not sure.


what is the time complexity for an algorithm that operations to complete grows by 4 when doubling the input length?

Recurrent equation:
$$T(n) = 4 \cdot T(\frac{n}{2})$$
$$T(1) = O(1)$$
Its solution:
$$T(n) = \Theta(n^2)$$


Finding (and possibly extracting) source code in heterogenous text data set

There are many possible ways you might do this.  I'll suggest one.

I suggest you train a classifier to recognize whether a sequence of characters is code or text.  Here, the goal is to build a boolean classifier that either outputs "text" or "code".  You'll train it only on documents that are entirely text or entirely code (no mixed documents).  Build a classifier that not only outputs a classification, but also a confidence (a likelihood value for the chosen classification).

Now, to apply it to mixed documents, run the classifier on all substrings.  If a substring $S$ is classified as "code" with high confidence (high likelihood), above some threshold, and there's no superstring $S'$ of $S$ (of length not too much longer than $S$'s length) that is also classified as "code", then output $S$ as one of the code elements from the mixed document.  You'll need to select a threshold with a little bit of experimentation.

I suspect this might work nicely.  You'll have to try it to see, though.

So, how do you build such a boolean classifier?  One simple approach would be to use a simple linear classifier (e.g., SVM or naive Bayes) with features based on bag-of-words on lexical tokens.  That alone might suffice (e.g., code tends to have many instances of tokens like "{" and "return", but text doesn't).  You could also try bag-of-words on individual characters.  If you want to build a more sophisticated classifier, you could train a character-level recurrent neural network (e.g., a LSTM or a CNN); this might achieve higher accuracy, given a large enough training set, but probably will also require a bit more technical knowledge.


What algorithm could I use to find the largest set of disjoint members from a set of subsets of a set?

The problem you describe is known as set packing, and it has a natural ILP formulation. You can start with some ILP solver you have access to, and it should be a highly competitive solution. There are many heuristics to choose from as well if you don't require optimal solutions.


BigO, Running Time, Invariants - Learning Resources

MIT OCW Introduction to algorithms video lectures
Design and analysis of algorithms stanford class


Prove that this language is decidable or undecidable

Yes, it is decidable.  There is a limited amount of input that any Turing machine could look at in ≤ 100 steps, so you can test a simulation of any given machine $M$ against all of those possibilities.


You need to define first where the recursion ends. And what t(n/4) means if n is not a multiple of 4.
The likely outcome will be that t(n) for 4^k < n < 4^(k+1) is between t(4^k) and t(4^(k+1)).


Is Kolmogorov-random nonsensical for small numbers?

Although one could pick a specific description language to make Kolmogorov complexity into

a function from  {0,1}*  to  {0,1,2,3,...} ,  most people don't pick as described  ( 0 , 1 , 2 , 3 ) ,

so basically:

Kolmogorov complexity is only defined up to an additive O(1), so one

needs an infinite set of strings to make sense of Kolmogorov randomness.

In particular, yes, Kolmogorov-randomness is nonsensical for small numbers.


The general answer to your question is no. Consider a function which measures the length of a linked list. How would you implement that without a branch?

But if you just stick with functions which (say) take a machine word and return a machine word (which your example does) then the answer is "yes, sort of". In fact, when analysing algorithms in the word-RAM model, we conventionally assume that any function which takes a fixed number of machine words and returns a fixed number of machine words is constant-time, because it could (in principle, at least) be implemented with a lookup table or a new CPU instruction.

Whether the branch-free version is more practical or not depends partly on the function and partly on the CPU's instruction set.

Don't forget, by the way, that pretty much all modern CPUs have a conditional move instruction. Some ISAs (e.g. ARM) can do conditional execution of all, or almost all, instructions. So there's even more ways to implement branch-free code there.


Conditions for Linear Diophantine Equations to always have a solution

Short answer: No.  Most likely, no useful constraint exists; and it can't be tested in polynomial time.

Detailed answer, with justification: It cannot be tested in polynomial time, unless P = NP.  In particular, if you could test for existence of a non-negative integer solution to such a system, you could solve integer linear programming (ILP).  Here's how the reduction works:

Suppose we have an ILP instance with variables $x_1,\dots,x_k$.  We'll modify it by introducing variables $x_1^+,\dots,x_k^+$ and $x_1^-,\dots,x_k^-$.  Then we'll replace each inequality

$$c_0 + c_1 x_1 + \dots + c_k x_k \ge 0$$

with the equality

$$c_0 + c_1 x_1^+ - c_1 x_1^- + \dots + c_k x_k^+ - c_k x_k^- = y_j$$

and the inequality $y_j \ge 0$, where $y_j$ is a fresh new variable.  Thus if the original ILP instance has $k$ variables and $m$ inequalities, the new instance will have $2k+m$ variables, $m$ equalities, and $2k+m$ inequalities $x_i^+ \ge 0$, $x_i^- \ge 0$, $y_j \ge 0$.

This now has the form of your problem, i.e., integer linear diophantine equations where we are looking for non-negative solutions, with $n=m$ linear equations and $v=2k+m$ variables.  Note in particular that we are guaranteed to have $v>n$, since we must have $k>0$.  Moreover, any solution to the original integer linear programming instance leads to a solution to this diophantine problem (take $x_i^+ = \max(0,x_i)$ and $x_i^- = \max(0,-x_i)$), and conversely, any solution to this diophantine problem leads to a solution to the original ILP instance (take $x_i = x_i^+-x_i^-$).  Therefore the derived diophantine problem is equivalent to the original ILP instance.

This reduces ILP to testing existence of a solution to a diophantine problem.  Since ILP is NP-hard, it follows that testing existence of solutions to this kind of diophantine problem is NP-hard, too.  That means there is not likely to be any polynomial-time algorithm to it (assuming you believe it is unlikely that P = NP).

For similar reasons, you should not expect a useful condition that is necessary and sufficient to ensure that a solution always exists: any such condition must be infeasible to check in the worst case, unless P = NP.  You can pick two out of any three: necessary; sufficient; efficiently checkable -- but you can't have all three, assuming P != NP (as many expect).


How to prove that Exact Cover is NP-complete using SAT?

I understand how this proves that it is NP-complete

It isn't a "proof" by any means. It's an example of how a reduction might work, but it hasn't been stated as a formal proof.

From your example, it looks like the algorithm/proof is as follows:

The universe consists of $3$ types of elements: one element $x_i$ for every variable $i$, one element $C_j$ for every clause $j$, and one element $p_{i,j}$ for every occurrence of a variable $i$ as a literal in clause $j$.
For every variable $i$, we create two sets; the true set and the false set. The true (resp. false) set contains $x_i$, together with, for every clause in which variable $i$ appears negated (resp. non-negated), $p_{i,j}$. As an example, if $x_1$ appears as a literal in clause $2$ and $\neg x_1$ appears in clauses $3,4$, we create the sets $\{x_1,p_{1,2}\},\{x_1,p_{1,2},p_{3,4}\}$.
For every element $p_{i,j}$, we create a set $\{C_j,p_{i,j}\}$ and a singleton set $\{p_{i,j}\}$.

As the variable true/false sets are the only sets containing $x_i$, for each variable $i$, a solution to Exact Cover must contain exactly one of the corresponding true/false sets. This gives a correspondence between the variable true/false sets selected in Exact Cover solutions and variable assignments to the SAT instance.

Moreover, any Exact Cover solution must, for every clause $j$, contain for some $i$ the set $\{C_j,p_{i,j}\}$ (since these are the only sets containing $C_j$). If $i$ is a positive literal in clause $j$, this means the false set for variable $i$ cannot be in the solution, since it also contains $p_{i,j}$. Similarly, if $i$ is a negated literal in clause $j$, we cannot have selected the true set for variable $i$. Thus, variable $i$ satisfies clause $j$ in the variable assignment corresponding to the selected variable true/false sets.

Conversely, given a satisfying assignment to the SAT instance, we can simply select the variable true/false sets corresponding to the assignment. For every clause we can select any set $\{C_j,p_{i,j}\}$ for which $i$ is a satisfying literal of clause $j$. This covers the $x_i$'s and $C_j$'s. The remaining $p_{i,j}$'s can be covered by singletons.


VC dimension of only the rim of a unit disk

Let us prove the following general result:

  Let $\mathcal F$ be a class of functions from $\mathcal X$ to $\{0,1\}$. If $\mathcal F$ has VC dimension $d$ then $|\mathcal F| \geq 2^d$.

Indeed, if $\mathcal F$ has VC dimension $d$ then $\mathcal F$ shatters some set $S \subseteq \mathcal X$ of size $d$. This means that for any function $\phi\colon S \to \{0,1\}$ we can find a function $f_\phi \in \mathcal{F}$ that agrees with $\phi$ on $S$. Note that if $\phi \neq \psi$ then $f_\phi \neq f_\psi$. Since there are $2^d$ different functions from $S$ to $\{0,1\}$, we conclude that $\mathcal F$ must contain at least $2^d$ functions. $\square$

In particular, the VC dimension of a class of functions containing a single function is zero.


First, we prove that the decision version of the original problem is NP. Since an instance of an assignment can be verified within polynomial time, it's obviously NP.

Now, we try to prove the NP-hardness of the problem.
Well, I believe this problem can be reduced from the bin-packing problem.

The bin-packing problem says the following:
There are $n$ items each with a weight $w_i$ and $m$ bins. We want to put the items to bins. Each bin has a maximum weight limit $\omega$. The problem is to find a item assignment scheme so as to minimize the number of bins needed. Mathematically:
$$\textrm{minimize}~~~ z = \sum_{j=1}^m y_j$$
Subject to:
$$\sum_{i=1}^n w_i x_{i,j} \leq \omega y_j, \forall j \in \{1,2,\cdots,m\}$$
$$\sum_{j=1}^m x_{i,j} = 1, \forall i \in \{1,2,\cdots,n\}$$
$$y_j \in \{0,1\}, \forall j$$
$$x_{i,j} \in \{0,1\}, \forall i, \forall j$$
The problem is NP-hard, and its NP-hardness has already been proved. The decision version of this problem is NP-complete.

Note that in the candy allocation problem, we tend to maximize the number of kids that are completely full. Since the number of kids are the same, the problem is equivalent to minimizing the number of kids that are not full, while ensuring every candy is allocated. The problem is formalized as follow:
$$\textrm{minimize}~~~ \sum_{j=1}^m y_j$$
Subject to:
$$\sum_{i=1}^n x_{i,j}w_i \leq \omega y_j, \forall j \in \{1,\cdots,m\}$$
$$\sum_{j=1}^m x_{i,j}=1 ,\forall i \in \{1,\cdots,n\}$$
$$x_{i,j} \in \{0,1\}, \forall i, \forall j$$
$$y_j \in \{0,1\}, \forall j$$
where $y_j$ denotes if kid $j$ is hungry ("1" is hungry, "0" is full), and $x_{i,j}$ denotes if candy $i$ is allocated to kid $j$.

One can easily see that the problem is equivalently to the bin packing problem. Thus, candy allocation is NP-hard.

Since candy allocation is NP and NP-hard, it's NPC.

The definition of bin packing problem can also be found in https://en.wikipedia.org/wiki/Bin_packing_problem.


How to convert process / cpu core based upon MIPS?

For a modern CPU there is no exact MIPS rating since it depends on the specific instruction stream, power saving mode, and other factors. As a reference number you may look at the BogoMIPS rating that is calculated by the Linux kernel.

A desktop CPU core at 3GHz can process about 2 instructions per clock cycle on average resulting in a rating close to 6000 MIPS (or 6 billion instructions per second), therefore 18 trillion instructions would require about 3000 cores.


What is the running time of generating all $k$ combinations of $n$ items $\binom{n}{k}$?

If you want to generate all items, the runtime is obviously at least O(n over k). To avoid exceeding O(n over k) your algorithm must be quite carefully designed.


What is the difference between operator and function?

Historically, my guess is that the difference is rooted in how things were (and still are) translated into machine code.

An operator such as addition of integers or exclusive-or of booleans would be translated into one (or few) assembler commands which would be directly executed by the processor (resp. its ALU). It would also be part of the syntax.

A function (or procedure, method), on the other hand, is a subprogram the (main) program would explicitly jump to during execution. That is, a new stack frame is allocated, register values are saved, parameters are passed and only then is the function executed. See here for details. Furthermore, functions are defined by the programmer.

Younger programming languages have introduced more abstraction, partially or totally removing the distinction. In C#, for instance, you can overload operators for your own types. In Scala, there are no operators but only syntactic sugar for binary methods. Once these languages are compiled, though, you can see which language elements are translated to flat instructions and which to subroutine calls. Keep in mind that optimising and/or just-in-time compilers may liberally move between worlds.


A Tautology is a formula (in a certain logic) that is true under every model of that logic. That is, it is equivalent to the formula "$True$".

A loop invariant, however, is a certain claim that is usually true under some models, and false under others (a model in this case is an algorithm). Then, you prove that the invariant is true under your specific model.

If you add axioms to your logic that forces then only model to be the one of your specific program, then indeed this would be a tautology. But such a process (adding axioms and proving that something is a tautology), is what is more commonly known as "proof". (For clarification: even if you add enough axioms, you may not be able to prove your claim, even if it's a tautology, in case of incomplete systems).

For example, consider a loop that increases a variable $i$ by $1$. An invariant of the loop may be that if before the loop $i>0$, then after the loop $i>0$. Indeed, this loop satisfies it. But it is not a tautology, since we can come up with other loops that do not satisfy it.


A model of computation vs an abstract machine

An abstract machine typically defines instructions with opcodes and operands. A Warren abstract machine, a java virtual machine, a Turing machine.  A programming model defines operations at a higher level, and could be independently supported by a number of different machines.  For example the actor programming  model says that an actor can send a message, create a new actor, and define internal state for its next message to be handled.  This is said without defining specific opcodes and operands, though one could envision an abstract machine that supported that.


Choose N pairs of (job, time slot) with a constraint on the number of different jobs

The last constraint is also no problem. You already have variables $x_{j,t}$, that say if the person works the $j$th job on the time slot $t$. Now you can introduce new binary variables $y_j$, that represent, if the person works at the job $j$ or not. Then you can model the constraint by:

$$\sum_{j \in J} y_j \le 2$$

The only part left is how you connect the information from the $x_{j,t}$ with $y_j$. But that is also not hard. If any of the $x_{j,t}$ is $1$, then you can force $y_j$ to also be $1$ with the constraints

$$y_j \ge x_{j,t}\qquad\forall t \in T, \forall j \in J$$

and force $y_j$ to $0$ if all $x_{j,t}$ are $0$. This can be done with:

$$y_j \le \sum_{t \in T} x_{j,t}\qquad\forall j \in J$$


Can this Arrow-Ring puzzle be encoded as an integer programming problem?

You can encode this problem using a SMT solver like z3, which translates it to a SAT instance.

Let each $c_{x, y}$ be a free variable for a cell that isn't an arrow. A cell can be one of the following (encode them as integer states or as one-hot states).

Black.
Horizontal.
Vertical.
Top-right turn.
Right-bottom turn.
Bottom-left turn.
Left-top turn.

If you can find an assignment of the above for each $c_{x, y}$ variable, you've found a solution.

Obviously we still need to encode all requirements. First introduce four helper variables for each $c_{x, y}$ to see if it is connected to its top/left/bottom/right neighbour. This is a bit laborious, but it comes down to logic statements such as "I'm vertical and bottom neighbour is either vertical, top-right turn or left-top turn".

Introduce a requirement that each cell $c_{x, y}$ must be connected to at least one neighbour.

Introduce a requirement for each arrow block to say that the number of cells equal to black in the direction it's pointing in must match its number.

Introduce a requirement that no two adjacent $c_{x,y}$ are black.

With all these requirements you know that each free cell is either black, or part of a connected loop. The final struggle is to ensure that there is a single connected loop. This can be done by assigning a single free variable to denote a leader cell, and then using the previous established connections to ensure that each cell is either black or the leader cell, or connected to the leader cell, or connected to a cell connected to the leader cell.

All in all this is quite a tricky and laborious translation into an SMT solver. If you intend to implement this I strongly suggest reading through some example problems from this excellent z3 guide. It has a ton of translations of various problems into a format a SMT solver can understand.


Hierarchial clustering cannonnical representation?

You can always adjust your algorithm to use a deterministic tie-breaking rule, e.g., sort the data points before applying the clustering algorithm, and always break ties in favor of the earliest/leftmost item.  This yields a deterministic algorithm, so if you give it exactly the same input both times, it will produce the same clustering both times.  I can't tell whether this is what you are looking for or not.


What is the relationship between oracle Turing machine $M^O$ and Turing machine $M$ (given $O$)?

The definition of $R$ you gave above doesn't make much sense, it looks like you're trying to build an equivalent TM that doesn't use the oracle, but the point of an oracle machine is to provide the TM with capabilities it wouldn't normally have.

For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the oracle.

If all the oracles you are using are oracles for decidable languages such as those used in complexity theory, then you can obviously simulate them (just construct a universal Turing Machine and use it to carry out the computation), but that's besides the point because it interferes with time/space complexity.

Nondeterministic oracle machines are exactly the same, the nondeterministic part is the transition function, queries to the oracle are treated as though they were a single computational step that magically happens, it is completely orthogonal to nondeterminism.


No, you can delete that edge and the graph remains chordal. This is so because you don't introduce an induced cycle of length 4 or more.


What is the meaning of uniform distribution of elements in an array?

Suppose that the array $A$ is chosen in the following way:

Sample $n$ real numbers uniformly from the interval $[0,1]$.
Sort the $n$ samples.

Suppose that you choose a further uniform random variable $x$ from the interval $[0,1]$. The expected running time of interpolation search on $A$ and $x$ is $O(\log\log n)$, where the expectation is over the choices of both $A$ and $x$.

In fact, if I understand Gonnet's thesis correctly, the expectation is still $O(\log\log n)$ even for any fixed $x$. See also Gonnet et al.


Closest-point heuristic approximation problem

I think there's some problem with the LaTeX formula. It should look like this:
$c(H_i)\leq c(H_{i-1})+2c(u_i, v_i)$
Let's say initially it was $u\to x$. Then you add $v$ directly after $u$, forming $u\to v\to x$. This increases the total distance by $c(u,v)+c(v,x)-c(u,x)$. From the triangle inequality, we have $c(u,v) + c(u,x) \geq c(v,x)$ and thus $2c(u,v)\geq c(u,v)+c(v,x)-c(u,x)$, hence $c(H_i)\leq c(H_{i-1})+2c(u_i, v_i)$.
The next paragraph should make more sense now.


How does the momentum term for backpropagation algorithm work?

Using Backpropagation with momentum in a network with $n$ different weights $W_k$ the $i$-th correction for weight $W_k$ is given by

$\Delta  W_k(i) = -\alpha  \frac{\partial E}{\partial W_k} + \mu  \Delta W_k(i-1)$
where $\frac{\partial E}{\partial W_k} $ is the variation of the loss w.r.t. $W_k$.

Introduction of the momentum rate allows the attenuation of oscillations in the
gradient descent. The geometric idea behind this idea can probably best be understood in terms of an eigenspace analysis in the linear case. If the ratio between lowest and largest eigenvalue is large then performing a gradient descent is slow even if the learning rate large due to the conditioning of the matrix. The momentum introduces some balancing in the update between the eigenvectors associated to lower and larger eigenvalues.

For more detail I refer to

http://page.mi.fu-berlin.de/rojas/neural/chapter/K8.pdf


Definition of NP-hardness for non-decision problems

There is a slight abuse of notation going on. We say that a function $f$ is NP-hard if $f\in FP$ implies $P=NP$. For example, if $L$ is NP complete and $M_L(x,y)$ is a verifier for $L$, then any function $f$ which maps $x$ to some $y$ such that $M_L(x,y)$ whenever such $y$ exists is of course NP-hard in this sense. We don't usually talk about actual reductions in this context, however the natural way to go about saying $L$ reduces to computing $f$ is to say that there exists a polynomial time oracle machine $M^f$ with access to $f$ that decides $L$.
See also the zoo on the class FNP. The fact that "function NP" problems are defined relative to a specific verifier introduces some difficulty when talking about search to decision reduction.


Number of hardware page tables and page directories kept in the MMU

The page tables are not kept in the MMU. In the MMU is a cache called the TLB which holds translated addresses. The TLB holds virtual addresses to physical addresses translations. For example, the TLB on intel core i5 has 64 entries for pages of 4KB.
Since the 10 upper bits are used as the offset in the page directory on 32 bits architecture, there are 2^10 = 1024 possible entries. The page directory has 1024 entries which hold the addresses of the page tables. Each page table has again 1024 entries holding the actual addresses of the page frames.
The CR3 register is used to locate the bottom of the page directory by the MMU. It holds a physical address (doesn't need to be translated).


Minimum difference between two subsets of an array of integers

My algorithm got proven wrong by Ricky Demer in a comment to the OP, with the example [2,2,3,3], for which we have a suboptimal output ({2,2} and {3,3} instead of {2,3} and {2,3}, for those wondering). Altough this flaw could be fixed in my code, it would then perform suboptimally in the example my professore had given me (And that I wrote in the OP).

A good greedy version of the algorithm is given on Wikipedia and is as follows:

def find_partition(int_list):
"returns: An attempt at a partition of `int_list` into two sets of equal sum"
A = set()
B = set()
for n in sorted(int_list, reverse=True):
    if sum(A) < sum(B):
       A.add(n)
    else:
       B.add(n)
return (A, B)

This approach gives a 7⁄6-approximation of the optimal solution, thus the only viable technique to use in case you need an optimal algorithm is dynamic programming. An implementation can be found, again, on Wikipedia and will run in pseudo-polynomial time.