Without fancy math, how does the MC-AIXI algorithm work?

I'll assume that the paper you're referring to is Veness et al. (2011) - A Monte-Carlo AIXI Approximation. The paper (and the AIXI model more generally) is rather technical, and so it is difficult to talk about without using much math. I'll do my best to explain informally here.

The question is in two parts, so I'll address each separately.

Models

The full mathematical formulation of AIXI makes use of Solomonoff induction to model the environment. Informally, Solomonoff induction involves enumerating every possible model (program) that is consistent with what has been observed, and weighting their likelihood by the inverse of their length. Solomonoff induction can be thought of as a theoretical upper limit on how well you can learn in the general setting while making no assumptions. As the question points out, it is of course incomputable.

We can relax the requirement that we model the world only using the Solomonoff prior, and introduce some other model class, which we will call $\xi$. Our agent is still a Bayesian expectation-maximizing reinforcement learner, but we can now plug it into a less powerful and less general (but computable) model. Hutter calls these agents AI$\xi$. In Veness et al.'s paper, they adapt the Context Tree Weighting (CTW) compression algorithm so that it can be used as a predictive mixture model of the form of $\xi$.

CTW is essentially a mixture over $n^{\text{th}}$-order Markov Models over bits, up to some finite order $N$. Each so-called context tree models dependencies in sequences of bits up to some finite depth. The CTW algorithm weights each context tree by its complexity (essentially how many nodes are in the tree). In this way, the CTW compressor can be made into an efficient, general, and fully Bayesian approximation of Solomonoff induction, and is great at learning short-term dependencies in bit sequences.

Veness et al. call their algorithm MC-AIXI-CTW, to emphasize that it is a two-fold approximation of AIXI: both in the planner (MC), and in the modelling (CTW). They could have used a different model, but they chose CTW because it makes no assumptions about the environment, and so is a general and principled choice. This allowed them to use the same model to learn to play various games, like rock-paper-scissors, cheesemaze, Pacman, and Tic-tac-toe.

Planner

The other side of the MC-AIXI-CTW implementation is the Monte Carlo planner. The algorithm that the authors develop is a straightforward generalization of the commonly used expectimax algorithm, called Monte Carlo tree search (MCTS). MCTS has been used in various AI applications over the last decade or so, and there are lots of online resources about it; the Wikipedia page is a decent starting point. I'll give my own short overview:

If you've studied game theory or introductory AI, then you'll be familiar with minimax. This algorithm can be used to compute the optimal next move when playing a deterministic two-player game. In the case of AIXI interacting with some environment, we can model this as a two-player game, but we must lift the deterministic assumption, as the environment is unknown, and in general stochastic; our models (which we use to plan with) are probabilistic, and so minimax won't cut it here. We instead use expectimax, which is the stochastic generalization of minimax. Instead of the other player adversarially (and deterministically) choosing the min action every turn, we now have to sample from some probability distribution.

MCTS is a sampling algorithm for doing just this. The general idea is that we plan ahead by simulating potential outcomes, using our model. Our objective is to compute the value of each of the moves available to us, so as to pick the best one. The value is in general a random variable, since our model is probabilistic. Hence we should choose the action that maximizes our expected value. The MCTS algorithm repeatedly plays out (simulates) a game tree, but instead of adversarially picking the opponent's moves, they are sampled from AIXI's model. As we collect more samples, our estimate of the value of each move will become more accurate.

Of course, we don't have infinite compute power, and so we can't simulate the agent-environment interaction ad infinitum; we have to stop at some depth of the MCTS tree. In simple game-playing, like chess, we would use heuristics to generate some intermediate value at this finite depth, so that we have something to work with to propagate up the search tree. In this general setting that MC-AIXI is trying to plan in, we have no such heuristics, and so we have no choice but to stop the search once we reach some finite (and typically small) depth.

This is the biggest limitation of the algorithm: planning is a huge computational bottleneck for MC-AIXI. In the absence of heuristics, it's hard to perform well in environments that demand long-term planning, since MCTS treats $\xi$ as a black-box environment model. To answer your question: once the planner reaches its planning horizon, it has to stop simulating ahead and make do with whatever it's sampled from that play-out. This is of course very limiting, but is unfortunately necessary, since doing anything else would require some kind of domain knowledge, which defeats the purpose of having a maximally general reinforcement learner.

Sorry if this answer is a bit long and hand-wavy. I interpreted the direction 'without using fancy math' in the strongest sense that I felt I could get away with. Hope it helps! Also, because I'm a new user to CS.SE, I'm limited to two links per answer. Once I've accumulated some points, I'll go back and edit this answer to include more links to external resources.


Why is a Fibonacci-Tree of rank 1 consolidated with one of rank n in this Fibonacci-Heap?

Page 8 defines rank:

  rank(x) = number of children of node x

So rank is not the height of the tree. With that, each chain, regardless of its length, has rank 1 and will be consolidated with any other chain.

But in most cases, rank defines the height, so why is it different here? The Reason is, it is simpler to implement. For the number of children, you just need the size of the direct children of a node, in many cases just some array.size, often already saved in a field.

But for the height you'd need additional calculations and fields, which can get complicated, especially for functions like decrease-key (which would make it not O(1) anymore).


Alpha-Beta Pruning with simultaneous moves?

The thing is that with simultaneous moves, the optimal strategy is harder to guess, because you need to compute something that is not always obviously winning.

Have a look at Nash equilibrium and the prisoner's dilemma if you don't know them yet. This is the kind of reasoning that you will need each time you are considering two simultaneous moves, instead of simply choosing a move that goes into a winning configuration in games with non-simultaneous moves. The concept of dominance replaces the concept of winning.

The algorithm in your reference does that when referring to figures 4 and 5 but first try to figure out what those figures are supposed to do before understanding how they do it.


Is there any practical application for arrays that contain themselves?

If you represent a (directed) graph in an adjacency "list" representation, i.e. each node has an array of (pointers to) its immediate successors, then any cyclic graph would arguably be an example of an array that "contains" (really references) itself. In practice, the "object graph" of references between the objects in a program will often be an example of this albeit not quite so cleanly

Indeed, for non-well-founded set theories with an anti-foundation axioms stating that sets can contain themselves, cyclic graph models are quite natural.


The problem is also called scheduling unrelated machines and as observed in the comments, it is NP-hard.

If you really want an optimal solution, I recommend to use an integer linear programming solver, such as lp_solve, SYMPHONY or GLPK. The problem can be formulated as an integer linear program as follows:

$$
\sum_{i=1}^m x_{ij}=1, \qquad j = 1,...,n
$$
$$
\sum_{j=1}^n p_{ij} x_{ij} \le T, \qquad i = 1, ..., m
$$
$$
x_{ij}=0, \qquad \text{if} p_{ij}>T
$$
$$
x_{ij} \in \{0,1\}, \qquad \forall i, j.
$$

Here $m$ is the number of machines, $n$ the number of jobs, $p_{ij}$ the time required to run job $j$ on machine $i$, and the variable $x_{ij}$ stands for 1 or 0 depending whether the job $j$ will be assigned to machine $i$ or not. The number $T$ is a parameter: if the integer linear system can be satisfied, then there is an assignment of jobs to machines that has overall finishing time (makespan) at most $T$. For any given $T$, the integer linear programming solver will tell you if the system is feasible (and if so, what are the values $x_{ij}$). Then you can find the best value of $T$ (and the corresponding $x_{ij}$s) by running a simple binary search.


Consider

(.) :: (a -> b) -> (d -> a) -> d -> b

is the fmap for functor $F_d\colon \mathfrak{C} \rightarrow d/\mathfrak{C}$ from category of types $\mathfrak{C}$ to its coslice category $d/\mathfrak{C}$ on object $d$.  Similarly,

(.) :: ((d -> a) -> d -> b) -> (c -> d -> a) -> c -> d -> b

is considered the fmap for functor $G_c\colon d/\mathfrak{C} \rightarrow c/\big(d/\mathfrak{C}\big)$.

These two functor can be composed to get $G_c \circ F_d\colon \mathfrak{C} \rightarrow c/\big(d/\mathfrak{C}\big)$. Like all compositions of two functors, the fmap of the composed functor is the composition of fmap its two functor operands. In this case, the fmap of $G_c \circ F_d$ is

(.) . (.) :: (a -> b) -> (c -> d -> a) -> c -> d -> b

as in the opening question.


Function minimization as genetic algorithm stop condition

There are three typical stopping criteria:

You have reached a sufficient value
Your new optimal value hasn't changed for the past $n$ minutes/generations
Your time (and patience) runs out.

The best case scenario is Case 1.  These are the cases where you are looking for a good enough solution, and you have found a solution that is good enough.  This criterion depends on you actually being able to set such a value, of course.

Typically Case 2 is better than Case 3 when it works out.  Here you don't abort your simulation as long as "it's improving" and therefore hasn't found the optimal solution.

But some times you get to borrow the cluster for 2 weeks, and then that's when you shut it off.


Minimize number of circles to cover set of points

Set Cover

If you restrict the possible center points of the circles to be the set of points, then this is an instance of set cover where the universe has $|P| \le 1000$ elements and where each set contains $N$ elements.  While set cover is NP-hard, there are algorithms for set cover that are faster than exhaustive search.

For these parameters, I expect it should be possible to find an optimal or near-optimal solution to the associated set cover problem, using standard algorithms for set cover.  I would recommend starting with the integer linear programming formulation and using a standard ILP solver (Gurobi, CPLEX) to find an optimal or near-optimal solution to the set cover problem.  That might be efficient enough for your purposes.

Your approach is known as the greedy algorithm for set cover.  It is known to give a $\lg N$-factor approximation, i.e., a covering that uses no more than $\lg N$ times as many circles as the optimal covering.  Thus, the ILP formulation may yield better solutions.  There are also heuristics for improving the greedy algorithm, e.g., BubbleSearch, which makes small random tweaks to the order suggested by the greedy strategy, repeats that some number of times, and takes the best solution found so far.  You could try them and compare them to how well the ILP formulation works, if you wish.

Geometric Set Cover

You could also look at algorithms for geometric set cover; some of those techniques may be useful here.  In particular, there are approximation algorithms and fast heuristics for geometric set cover, and you could try seeing if they are useful in your particular setting.  They use the extra geometric structure provided by the problem: this is not a totally arbitrary instance of set cover, but there is some additional structure.

Arbitrary Center Points

The above algorithms have one critical limitation: they only consider circles that are centered at some point in $P$.  There's no reason to expect the optimal solution to your problem to have this property.  Thus, they might fail to find the optimal solution to your original problem.

Fortunately, it's possible to fix this limitation.  It's possible to come up with a not-too-large set $U$ of candidate circles, such that the optimal solution is obtained by taking a subset of circles from $U$; then we can apply set-cover techniques to pick a minimal-size subset of $U$ that covers all of $P$.  In particular, we will use the following geometric facts:

Lemma 1. Let $C_0$ be any circle that covers exactly $N$ points.  Let $S \subset P$ be the set of $N$ points covered by $C_0$.  Then there exists a circle $C$ that (i) covers exactly $S$ and no other points and either (ii.1) has at least three points of $S$ along its circumference or (ii.2) has two points of $S$ along its circumference and is centered at their midpoint.

Proof. Consider any circle that covers exactly $S$ (and nothing more).  Pick the point $p \in S$ that is closest to the boundary of this circle.  Reduce the radius of the circle until $p$ is on the boundary.   Now if this circle doesn't have two points of $S$ along its circumference yet, move the center of the circle towards $p$, reducing the radius at the same rate, until the first time some other point is on the boundary -- call it $q$.  At this point we have a circle $C$ that covers all of $S$, contains $p,q$ on its boundary, and doesn't cover any points other than $S$.  Now let $m$ be the midpoint between $p,q$, and let $L$ be the line that is perpendicular to $pq$ and that intersects $m$.  If $C$ is centered at $m$, we're done.  Otherwise, $C$'s center is somewhere on $L$.  Move the center of $C$ along $L$ towards $m$, decreasing its radius at the same time so that $p,q$ remain on its circumference, until either the center reaches $m$ or the circumference hits a third point.  Either way, we are done.  $\Box$

Lemma 2. Given any three non-colinear points $p,q,r$, there is a unique circle that is tangent to all three (i.e., has all three on its circumference).  This circle can be efficiently computed.

Proof. Use the same procedure described in the proof of Lemma 1, but now without worrying about how many points are covered by the circle. $\Box$

Lemma 3. Given any two points $p,q$, there is a unique circle centered at their midpoint and tangent to both $p,q$.

Proof. Obvious.  $\Box$

With these lemmas, we can now suggest an algorithm:

For each set of three points $p,q,r \in P$, find the circle that is tangent to $p,q,r$.  Identify the points covered by this circle (e.g., using a quadtree).  If this circle covers exactly $N$ points, add it to $U$.
For each set of two points $p,q \in P$, find the circle centered at their midpoint and tangent to both.  If this circle covers exactly $N$ points, add it to $U$.

Lemma 1 now ensures that we need only consider circles in $U$; any set of $N$ points that can be exactly covered by some circle, can be covered by some circle in $U$.  Therefore, there exists an optimal solution to the original problem that uses only circles in $U$.  As an optimization, if there are two circles in $U$ that cover the same set of points, you can keep one of them and discard the other.

Therefore, the problem becomes:

Given a set $P$ of points and a set $U$ of circles (each covering exactly $N$ points from $P$), find the smallest subset of $U$ that covers all of $P$.

This is a finite set cover problem, and the solution to this set-cover problem is guaranteed to be optimal.  We obtain a set-cover instance with a universe of size $|P| \le 1000$  and with $|U|$ sets, each of size $N$.  This set cover problem can then be solved using standard algorithms for set cover, e.g., using an ILP solver.  We'll have $|U| \le |P|^3/6$ at worst, though in practice I expect $|U|$ will typically be much smaller (closer to $|P|^2$ or so).  The running time to create the set-cover instance will be at most $O(|P|^3)$; then we have to solve the set-cover instance.  I anticipate that, for these parameters, it might be possible to obtain an optimal or very-nearly-optimal solution to the original problem using off-the-shelf ILP solvers.

My thanks to @j_random_hacker for substantial assistance with this answer.


Here are some pointers to one possible solution, taken from Google's TensorFlow XLA compiler.

Their use case is to partition a computation graph (usually a DAG) into subgraphs and place them on different devices, while satisfying data dependencies and maximizing each subgraph. For instance, in your question, assuming nodes must either be placed on CPU (red) or GPU (black), we would compute subgraph Node{1, 3} on CPU, and then compute Node{2} on GPU, and finally Node{4} on CPU.

The algorithm consists of two parts:

Union-find for keeping track of node merging

Start reading from here, the main loop for contracting edges

An "incremental cycle detection" algorithm

This functionality is implemented in the GraphCycles class
It is based on a dynamic topsort algorithm for DAG as documented here


What's the difference between a calculus and a programming language?

The meaning of the words is not fixed, but I can give you my interpretation.

A calculus is something that we calculate with in the sense of juggling equations (think manipulation of Taylor series or computation of integrals in analysis). A calculus tells us what the rules of manipulation are, but not which ones we should used in a given situation.

A programming language is something that tells us how to calculate. It tells us precisely how to use the rules. We typically let the computer use the rules, as it is much faster. The rules may be non-deterministic, and there may be very good reasons for them being non-deterministic. It may be in the nature of the calculus that it is non-deterministc (think concurrent communicating processes), or fixing a particular strategy may be detrimental to implementation techniques and optimization.

For example, the $\lambda$-calculus is an equational theory. There are expressions and equations telling us when expressions are equal. The equations do not tell us how to apply them, although people usually have hidden agendas and they present the equations so that later on they can derive useful evaluation strategies from them. But in its essence $\lambda$-calculus is a bunch of equations. It is not a programming language.

In contrast, Standard ML is a programming language. It  is given in terms of operational semantics, i.e., rules of computation. There are derived notions of equality (contextual equivalence, observational equivalence, etc.) which we can put on top of it to think of it as a kind of calculus.

Of course, there are often useful connecitons between a calculus and its manifestation as a programming language. Confluent normalization is just one way of passing from the calculus to the programming language (although sadly some people have made it into a religion of sorts). The interplay between calculi and programming languages is important: the programming languages can actually be used, but the calculi explain what the programs are about.

Just to annoy people, let me also state that pretending that there is no difference between a calculus and its operational manifestation sometimes leads to skewed views of programming and mini-religions within the programming community. You may try to guess which language I have in mind. (It's a very cool language!)


If $f(n)=\Omega(g(n))$ and $h(n)=\theta (g(n))$ then does this implies $f(n).g(n)=\Omega(g(n).h(n))$?

I have got the answer. It's easy.

Since $f(n)= \Omega g(n)$

$cg(n)\le f(n)$

Multiplying both sides by h(n)

$cg(n).h(n)<=f(n).h(n)$

$f(n).g(n)=\Omega(g(n).h(n))$


Find two numbers in sorted array whose product is close to N

This answer is compilation of above comments but this include reasoning why this algorithm works.

1. find(A, val)
2.    start = 1
3.    end = A.length
4.    minn = (start,end)                //minn is pair used to store answer
5.    minnErr =   |A[start]*A[end]-val|        //minnErr is difference between best
                                  //pair of values seen so far and targate value.
6.    while(start < end)
7.        if (|A[start]*A[end]-val| < minnErr) //if this pair of values is
                                                      //even better than remember it.
8.            minnErr = |A[start]*A[end]-val|
9.            minn = (start, end)

10.       if A[start]*A[end] > val:              // here
11.           end = end - 1
12.       elif A[start]*A[end] < val:
13.           start = start + 1
14.       else:
15.              break
16. return minn

Algorithm works as follows:

here answer is pair of indices of element of array which has product closest to target
value.

We keep two pointers $start$ and $end$. Which are initialized to $1$ and $array\space size$ respectively.
Now in every iteration we compare $A[start] * A[end]$ with $minnErr$.
If current pair have better solution than we record it.
If $A[start]*A[end] < val$ than we increase $start$ by $1$.
Now note that all $(i,j): i< start, j\le end$ can never be solution because for any
such $(i,j)$ we have $A[i]*A[j] \le A[start]*A[end] < val$.
if $A[start]*A[end] > val$ than we decrease $end$ by $1$.
Now here(considering decremented value of $end$) all $(i,j): i\ge start, j>end$ can never be solution because for any such
$(i,j)$ we have $A[i]*A[j] \ge A[start]*A[end] > val$.
if $A[start]*A[end] = val$ than we stop here as this is best solution.

credits:  @G. Bach, @greybeard


Relative primality is primitive recursive

Two numbers $x,y$ are not relatively prime iff there exists some common factor $a > 1$, which divides both $x$ and $y$. This common factor can be bounded by $a$. Therefore $x,y$ are not relatively prime iff there exist $a,b \leq x$ and $c \leq y$ such that (i) $a \geq 2$, (ii) $x = ab$, and (iii) $y = ac$.


If the distribution on input instances is uniform, then the two are equivalent.  Talking about a distribution has two potential advantages: (1) it allows us to analyze the algorithm using the tools of probability theory, which can sometimes be useful, (2) it allows us to meaningfully talk about average-case running time for a non-uniform distribution on inputs.


Need clarification regarding certificates of coNP problems

The proof does bot need to be a subset. It might be another indicator that the given set has a some stricture preventing it from being a positive instance of the subsetsums problem. A good example with a non-trivial certificate is linear programming. Linear programs admit both a positive and a negative certificate (For the question whether the optimal can be smaller/greater than a value k). The positive instance is of course an assignment of the variable. The negative however is given by Faraks lemma and the weak duality.

A good exercise for you is to look up linear programs, weak duality and Farkas lemma :)


Solving this recurrence: T(n) = 9 T(n/2) + n^3 lg n

You should use the Master Theorem to solve that kind of recurrence relation:

The general form of the Master Theorem is: $T(n) = a T(n/b) + O(n^d)$ or $T(n) = a T(n/b) + f(n)$, where $f(n)$ can take multiple forms (I'll let you dive into that).

That being said, let us begin solving the recurrence relation, step by step:

$$T(n) = 9 T(n/2) + n^3 \lg n$$

Step 1: Identify a, b and d. In your relation $a = 9$, $b = 2$. We need to work a little harder to find $d$, as you can see. The function $f(n)$ is of the form $n^\mathbf{d} \log^k n$. So $f(n) = O(n^3 \lg n)$, thus $\mathbf{d} = 3$.

Step 2: Analyze the a, b, d output of your recurrence relation and decide which of the following cases is valid:

I) $a = b^d$, then $T(n) = O(n^d \log^{k+1} n)$;

II) $a < b^d$, then $T(n) = O(n^d)$;

III) $a > b^d$, then $T(n) = O(n^{\log_b a})$.

In your situation, we have $9 > 2^3$, thus $T(n) = O(n^{\log_29}) = O(n^{3.17})$.

As you can see, this is a simple exercise on asymptotic notation. Next time try to give more insight on your thoughts regarding your problems, don't just post your homework blankly.


How to the examples for using the master theorem in Cormen work?

First of all, please check what $O$ and $\Omega$ and the other Landau symbols mean; that should remove some of the confusion.

Note that $n \log n \in \omega(n)$, that is $n \log n$ grows properly faster than $n$, asymptotically. This can be seen by

$\qquad \lim_{n \to \infty} \frac{n \log n}{n} = \lim_{n \to \infty} \log n = \infty$.

By the same reasonining, though, $n \log n \in o(n^{1 + \varepsilon})$ for every $\varepsilon \in (0,\infty)$.

Therefore, $n \log n \in \Omega(n^\alpha)$ for all $\alpha \in [0,1]$, so in the example you can choose $\varepsilon$ arbitrarily so that $\varepsilon + \log_4(3) \leq 1$. The authors pick one, namely the largest (up to dropped decimal places).

As has been noted, that does not conclude the proof that case three applies; you still have to check that $a f\left( \frac{n}{b} \right) \le c f(n)$ for some $c>1$ and all $n>n_0$, $n_0$ some natural number.

As for the second example, my above explanation shows that there is no $\varepsilon > 0$ so that $n \log n \in \Omega(n^{\log_2(2) + \varepsilon})$, so case three can not apply here. Note that $o(f) \cap \Omega(f) = \emptyset$ for all $f$.


Is this definition of a "complete graph" correct?

I'm not sure what "official definition" you have in mind but your definition of a complete graph is correct: it implies that every pair of distinct vertices are connected by an edge.

At least, it does assuming that by "connected", you mean "has an edge to". It's best to avoid using the word in that way, since "connected" in graph theory refers to the existence of paths that might be longer than a single edge.


Access to publicly available project with all the artefacts (files) created during the development

Your best bet is to go with major open source projects (Apache, Open Office, Mozilla, MySql, perhaps Linux).  Since these are done by large online communities all communication occurs online through bug databases and forums or mailing lists (which are usually archived).  If they do code reviews they may be archived with a tool like Review Board or will be done through the official archived mailing lists.  It seems unlikely that you will find a non-open source project/company willing to provide such detailed information.

An example of an academic software engineering study which quite successfully used open source artifacts is:

  Shan Lu, Soyeon Park, Eunsoo Seo, Yuanyuan Zhou: Learning from mistakes: a comprehensive study on real world concurrency bug characteristics. (ASPLOS-XIII):329-339, 2008.

Prof. Y.Y. Zhou's research team at UCSD has done a variety of other studies mining open source bug databases to understand bug or failure characteristics.  http://opera.ucsd.edu/pub_system_depend.html#characteristic-study


What you want is to have each production be of one of the forms $A \rightarrow BC$, $A \rightarrow x$ (for a terminal $x$), and $S \rightarrow \epsilon$ (where $S$ is the start symbol). The only productions in that grammar which are not of one of these forms are:

$\text{S} \rightarrow I \text{ VP PP}$
$\text{VP} \rightarrow ate \text{ NP}$
$\text{VP} \rightarrow \text{V}$

Hints: try replacing the second production with an equivalent one of the form $A \rightarrow BC$, and try replacing the third production with one of the form $A \rightarrow x$. For the first one, I suggest creating a non-terminal $\text{X}$ such that $\text{X} \rightarrow I \text{ VP}$, and then rewriting the production as $\text{S} \rightarrow \text{X} \text{ VP}$. This production is in the correct form, but now the one for $\text{X}$ isn't; however, it isn't too much work to fix that one as well.


The grammar $S \to aSa \mid bSb \mid cSc \mid a \mid b \mid c \mid \epsilon$ would generate (normal) palindromes.

A simple way to extend this to generate palindromes with non-repeating would be to add for each letter $x$ a new non-terminal $S_{not\text{-}x}$, and adapt the grammar:

$S \to aS_{not\text{-}a}a \mid \dots$

$S_{not\text{-}a} \to bS_{not\text{-}b}b \mid \dots$

There are probably more efficient ways.


Notions of information content and randomness of binary square matrix

You claim that unraveling the (square) matrix into a vector loses some information. However, the transformation is bijective - given the $n^2$ vector, you can easily reconstruct the $n\times n$ matrix. Information theory is oblivious to representation. If you have some random variable $X$ and some bijection defined on its domain $f$ then $H(X) = H(f(X))$. So classical information theory covers the case of matrices.


In what sense if any does java have multiple dispatch?

In what sense is it possible to say java has a kind of multiple-dispatch system due to method overloading?

In no sense. What Java's method overloading gives you is dynamic dispatch, not multiple dispatch.

The most commonly seen example of multiple dispatch in Java is its event listener system, where you can register multiple listeners which will all be triggered when an event occurs.


In two's complement, we compute $a-b$ by adding $a$ and $-b$. To compute $-b$ in two's complement, we invert all bits in $b$, and increment the result by $1$.
Let's see how it works in your example. You haven't specified the bit length, but it appears to be $8$. We have $50 = 00110010$, and so $-50 = 11001101+1 = 11001110$. Similarly, $48 = 00110000$, and so $-48 = 11001111+1 = 11010000$. In order to subtract $-48$ from $-50$, we first negate $-48$: $-(-48) = 00101111+1 = 00110000$. Now we add $-50$ and $-(-48)$: $11001110+00110000 = 11111110$. Since the MSB is $1$, we know that this is a negative number. To find out negative what, we invert it: $-(11111110) = 00000001+1=00000010$, which is $2$. Therefore $-50-(-48)=-2$.


Checking whether a digraph on $n$ vertices contains exactly $10\sqrt{n}$ strongly connected components in NL

Hint: Suppose $C_1,\ldots,C_\ell$ are the connected components and $v_i$ is the minimal vertex in $C_i$. Suppose further that $v_1 < v_2 < \cdots < v_\ell$. Show how to certify the fact that this data is correct in NL by keeping at most two of these indices at a time.

Here are some more details for a slightly simpler problem: verifying whether an undirected graph contains exactly $10\sqrt{n}$ connected components. We keep a counter $k$ of vertices accounted for. Suppose the vertices are numbered $1$ to $n$, and for $t$ going from $1$ to $10\sqrt{n}$, do the following:

Guess a vertex $v_t > v_{t-1}$ (where $v_0 = 0$).
For all $v < v_t$, verify that $v$ is not connected to $v_t$.
For each $v \geq v_t$, guess whether $v$ is connected to $v_t$ or not, and verify the guess; for each vertex connected to $v_t$, increase $k$.

If at the end $k = n$ then all vertices are accounted for, and the graph contains exactly $10\sqrt{n}$ connected components.

I leave the straightforward modification that solves the actual problem to the reader.


$R$ has only five non-trivial functional dependencies (FDs).

No, $R$ has many more non-trivial FDs. For example, Since A-> BC and C -> F, we also  have AC->BF, which is also a non-trivial FD although not a irreducible FD.
What you can say is that all given 5 FDs are non-trivial FDs, since for each given FD, the dependent set is not a subset of the the determinant set.
If you want to see all non-trivial function dependencies of $R$, you have to obtain the dependency closure of the given FDs, following, for example, the procedure given here using Armstrong's axioms.

Step-1 : Add the attributes which are present on Left Hand Side in the original functional dependency.
Step-2 : Now, add the attributes present on the Right Hand Side of the functional dependency.
Step-3 : With the help of attributes present on Right Hand Side, check the other attributes that can be derived from the other given functional dependencies. Repeat this process until all the possible attributes which can be derived are added in the closure.

You can enter R(A,B,C,D,E,F) and A -> B,C; A,D -> B,E; C ->F ; A->F; D-> E into the first two fields on this page. Hit the "Calculate" button and view the result. It will list a lot of related concepts. In particular, it shows the following 43 non-trivial FDs.
A → B,C,F
C → F
D → E
A,B → C,F
A,C → B,F
A,D → B,C,E,F
A,E → B,C,F
A,F → B,C
B,C → F
B,D → E
C,D → E,F
C,E → F
D,F → E
A,B,C → F
A,B,D → C,E,F
A,B,E → C,F
A,B,F → C
A,C,D → B,E,F
A,C,E → B,F
A,C,F → B
A,D,E → B,C,F
A,D,F → B,C,E
A,E,F → B,C
B,C,D → E,F
B,C,E → F
B,D,F → E
C,D,E → F
C,D,F → E
A,B,C,D → E,F
A,B,C,E → F
A,B,D,E → C,F
A,B,D,F → C,E
A,B,E,F → C
A,C,D,E → B,F
A,C,D,F → B,E
A,C,E,F → B
A,D,E,F → B,C
B,C,D,E → F
B,C,D,F → E
A,B,C,D,E → F
A,B,C,D,F → E
A,B,D,E,F → C
A,C,D,E,F → B


Schützenberger (1965) gave an algebraic characterization of the star-free languages: a regular language is star-free if and only if its syntactic monoid is aperiodic. Contrary to the logical characterization (star-free = FO[<]), this algebraic characterization gives an algorithm to decide whether a given regular language is star-free (the regular language can be given by a finite automaton, a regular expression or a regular grammar). Using the logical characterization (due to McNaughton and Papert) one can then decide the following problem: given a WMSO formula, is there a FO formula describing the same language?

M.-P. Schützenberger, On finite monoids having only trivial subgroups, Information and Control 8 (1965), 190-194.

R.~McNaughton and S.~Papert, Counter-free automata, The M.I.T. Press, Cambridge, Mass.-London, 1971.

A full proof of Schützenberger's theorem can be found in various textbooks or survey papers. For an elementary presentation of the corresponding algorithm (without a proof), see

J.-É. Pin, Finite semigroups and recognizable languages : an introduction, in NATO Advanced Study Institute Semigroups, Formal Languages and Groups, J. Fountain (éd.), 1-32, Kluwer academic publishers, (1995).


One general approach to the problem is to prove program equivalence by showing the programs have the same semantics. Hoare-style verification, as you say, is one option categorized as axiomatic semantics. Have a look at this article which describes most of the semantic approaches out there, including denotational semantics and operational semantics.


Minimum spanning tree such that one edge can be minimised

In the following, I assume the set of all feasible solutions is the set $\{(T,uv):T$ is a not necessarily minimum spanning tree of $G$ and $uv$ is a distinguished edge in $T\}$, with the cost of a particular solution $(T,uv)$ being the sum of the edges in $T$ minus $\min(D,w(uv))$.

Let $(T, uv)$ be an optimal solution to the problem you describe, having weight $\sum_{xy \in E(T)} w(xy) - s$, where $s = \min(D, w(uv))$.  There are two possibilities:

Every MST of $G$ contains at least one edge of weight $\ge s$.
At least one MST of $G$ contains no edge of weight $\ge s$.

Case 1

For case 1, we can take any MST $T'$, find an edge in it with weight at least $s$ (since we know by assumption that this exists), and produce a solution having weight at most $\sum_{xy \in E(T')} w(xy) - s$.  This is at most the weight $\sum_{xy \in E(T)} w(xy) - s$ of the optimal solution $(T, uv)$, since $\sum_{xy \in E(T')} w(xy) \le \sum_{ab \in E(T)} w(ab)$ for any tree $T$ by definition of the MST.  That means that for case 1, we can never miss an optimal solution by considering only MSTs.

Case 2

For case 2, consider the edge $uv$ in $T$, which has weight at least $s$.  Let the vertices on one side of this edge be $A$, and the vertices on the other side $B$.  By assumption, there exists an MST in which every edge has weight strictly less than $s$.  In particular, this MST must contain an edge $u'v'$ between the vertex sets $A$ and $B$ having weight strictly less than $s$, since otherwise the MST would be disconnected -- a contradiction.

Suppose $w(uv) > D$.  Then the original solution $(T, uv)$ has weight $X - D$, with $X$ being the weight of the entire tree $T$, while the solution formed by replacing $uv$ with $u'v'$ has weight $X - w(uv) < X - D$.  This contradicts optimality of $(T, uv)$, so it must be that in fact $w(uv) \le D$, in which case both the original and new solutions have weight $X - w(uv)$.  Thus the new solution has weight equal to the old solution, but now falls into case 1 above.

Wrapping up

Since there are only two possible cases for an optimal solution, and in both cases an MST can always be found that leads to a solution that is just as good, it always suffices to find an MST.

The final step is to choose an edge in the MST to minimise.  Clearly it is always optimal to choose the heaviest edge in the MST.


Why does stable matching without Gale-Shapely takes n! steps

Suppose that the group of men is $m_1,\ldots,m_n$ and the group of women is $w_1,\ldots,w_n$. Suppose that man $m_i$ is matched to woman $w_{c_i}$. Then the matching can be described by the sequence $c_1,\ldots,c_n$. Each $c_i$ is in $\{1,\ldots,n\}$, and $c_i \neq c_j$ for $i \neq j$. So $c_1,\ldots,c_n$ is a permutation of $\{1,\ldots,n\}$, of which there are $n!$.


Circle Hough Transform. Improvement by knowing edge direction

Consider circles of the form

$$(x - a)^2 + (y - b)^2 = r^2$$

The Circular Hough Transform with unknown radius and unknown gradient information has a parameter space $(a, b, r) \in H$. Given a single edge point we'd end up drawing a right cone increasing along the positive $r$ axis with its tip centered at $(x, y, 0)$.

Now to your question. When you know the gradient $\nabla I(x,y)$ of an edge point, $(x,y)$ from your image $I$, you have a vector originating from the center of the circle pointing outward. Since you have your edge point $(x,y)$ the center $(a, b)$ must lie somewhere along the lines $(x,y) \pm r \nabla I(x,y)$. There is only one variable in that statement, $r$.

Now the Circular Hough Transform becomes: for each edge point $(x,y)$, and for each plausible radius $r$, calculate $(a, b) = (x, y) \pm r \nabla I(x,y)$ and increment the accumulator array index $(a, b, r)$ by $1$. Then you go a do your usual vote counting to find the most likely parameters $(a, b, r)$.

For further details refer to D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes" Pattern Recognition. Vol.13. 1981. Extends this concept to ellipses, general analytic curves, and the general transform.


What do you call a function from symbols of alphabet to languages?

It looks like it refers to a substitution, but that the given definition is incomplete.

Anyway, in formal language theory, people often use monoid morphisms between free monoids. To avoid overloading the term "morphism", a monoid morphism from a free monoid $A^*$ into the monoid $2^{B^*}$ of languages of $B^*$ (under concatenation product of languages) is often called a substitution.

Now, since a morphism from $A^*$ into any monoid is entirely defined by the image of its letters, a substitution from $A^*$ to $B^*$ might be given as a map $\sigma: A \to 2^{B^*}$. But then it is extended to a map $A^* \to 2^{B^*}$ by setting $\sigma(1) = \{1\}$ and $\sigma(a_1 \dotsm a_n) = \sigma(a_1) \dotsm \sigma(a_1)$.

Reference. Page 5 in First four chapters of
Berstel's book Transductions and Context-Free Languages, Teubner (1979).
(Page 13 in the printed version)


Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?

Broadly speaking, you can normally trade the word "algorithm" for the words "Turing Machine", in the sense that a Turing Machine is not a programmable computer like the one you have in front of you, it is a mathematical embodiment of an algorithm. So for the two cases you mention:

A nondeterministic algorithm is a nondeterministic Turing Machine.
A randomized algorithm is a probabilistic Turing Machine.


How does squaring time complexity imply the same time complexity for multiplying different numbers? Isn't it the other way round?

Of course, we can suppose we are able to do sum and difference in linear time. Now, if we want to calculate $h\cdot k$, we can find in linear time $a$ and $b$ such that $h=a-b$ and $k=a+b$: take $a=\frac{k+h}{2}$ and $b=\frac{k-h}{2}$. Then $h\cdot k=(a-b)(a+b)=a^2-b^2$, so we only need to square two numbers of at most $n$ digits (if $h$ and $k$ have $n$ digits, then also $\frac{k+h}{2}$ has at most $n$ digits) in $O(n\log(n))$ and take their difference in $O(n)$.
Actually, this works if $h$ and $k$ have the same parity, else $a$ and $b$ are not integers; if it is not the case, then you can write $h\cdot k=h\cdot(k-1)+h$ and proceed as above.


The phrase

The speedup we achieve is linear to the number of cores.

refers only to the C portion of the program. Therefore the running time on $N$ cores is
$$ t_A + t_B + \frac{t_C}{N}. $$
The speedup is
$$
\frac{t_A + t_B + t_C}{t_A + t_B + t_C/N} =
\frac{1}{\frac{t_A + t_B + t_C/N}{t_A+t_B+t_C}} =
\frac{1}{\frac{t_A+t_B}{t_A+t_B+t_C}+\frac{1}{N} \frac{t_C}{t_A+t_B+t_C}}.
$$
This is Amdahl's law.


You have an intended postcondition for a loop, and you're looking for an interesting invariant. In this scenario, try taking the intended postcondition, and replacing the total number of iterations (here N) by the number of iterations so far (here i). There's no guarantee that this is an invariant: that's only the case if the way the postcondition is somehow related to the structure of the loop. But if it is an invariant, it's definitely interesting, because it lets you prove the postcondition.

So we're interested in the following property: “the value of found equals the value of the predicate there exists a $k$ in the range $[0, i)$ such that $a[k] = x$”. Note that I use a name other than i for the existential variable, since i is now used in the context. The quantifier pile-up is:
for any value of N set before calling this snippet,
for any value of the variable i,
there exists an index $k$ such that …

It is easy to verify that this is indeed an invariant of the loop.

Intuitively, this property states that found reflects whether the element is in the array up to the point that has been traversed. At the end of the loop that traverses the whole array, found reflects whether the element is in the whole array.


Find optimal quantum at Round Robin Scheduling algorithm

Never mind, I just found how to take the quantum time. Just find 80% of n processes Eg: You have 9 process, 80% from 9 is 7.2 ~ 7. Order the process ascending by BURST and take the burst from 7 process.


Can Strassen's multiplication algorithm be improved if we divide matrices to 3x3 or axa in general?

There is nothing special about 2×2 matrices. In fact you can do much better using larger matrices. The reason that you are only being explained the 2×2 algorithm is that it is simple to describe. The special thing about 2×2 matrices are that they are the smallest square matrices which are larger than 1×1.

You can read more in this recent survey by Dumas and Pan on fast matrix multiplication, which concentrate on practical algorithms.

From a pure mathematical point of view, the following theorem is known:

  Suppose that the algebraic complexity of matrix multiplication is $O(n^\alpha)$. Then for every $\epsilon > 0$ there is a divide-and-conquer algorithm for multiplying matrices in $O(n^{\alpha+\epsilon})$.

Here a divide-and-conquer algorithm is an algorithm which recursively applies some smart algorithm for multiplying $m\times m$ matrices, for some constant $m$.

The fastest theoretical algorithm for matrix multiplication, due to Le Gall, is based on the classical algorithm of Coppersmith and Winograd. Unfortunately, this algorithm isn't practical.


You are missing a major part of the definition of $CoNP$: you need a proof that your machine $M$ runs in nondeterministic polynomial time for all "yes" inputs. Because you have simply taken the NP SAT algorithm and flipped it, it runs in nondeterministic polynomial time for all "no" inputs. But we have no such guarantees for the "yes" inputs.
The real answer is, nobody knows that SAT isn't in $CoNP$. If we knew that, we would know that $CoNP = NP$, but this is still an open problem. So, nobody can point to a specific reason that you can't build a machine that decides the complement of SAT it nondeterministic polynomial time. It's just that nobody has been able to do it yet, or prove that it's impossible.


Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs

Let $M$ be the Turing machine recognizing $B$.
Hint
For a Turing machine, try to encode the running time required for $M$ to accept it into itself, so that one can simulate $M$ on it without going into infinite loop.
Complete Answer

 Let $f$ be a computable bijection from $\mathbb{N}_0^2$ to $\mathbb{N}_0$, where $\mathbb{N}_0$ is the set of non-negative integers.

  Define a state of a Turing machine to be isolated if no state can be transitioned to it and it cannot be transitioned to any state. Obviously adding or deleting isolated states does not affect the function of a Turing machine.

  Define $M_d$ to be a decidable Turing machine, which works as follows on input <$M_w$> where $M_w$ is a Turing machine.

  Compute the number $n$ of isolated states in $M_w$.
  Let $(n_1,n_2)=f^{-1}(n)$.
  Let $M_w'$ be the Turing machine that is almost the same as $M_w$ except it has $n_1$ isolated states.
  Simulate $M$ on <$M_w'$> with at most $n_2$ steps.
  If $M$ accepts, accept; otherwise, reject.

  Consider $M_i$ (recall $M$ accepts <$M_i$>). Suppose $M$ runs in total $n_2$ steps on <$M_i$> and $M_i$ has $n_1$ isolated states. Let $M_i'$ be the Turing machine that is almost the same as $M_i$ except it has $f(n_1, n_2)$ isolated states. Now $M_i'$ and $M_i$ are functionally equivalent, and easy to see <$M_i'$> is accepted by $M_d$.

  On the other hand, suppose <$M_w$> is accepted by $M_d$ and $M_w$ has $n=f(n_1,n_2)$ isolated states. Let $M_w'$ be the Turing machine that is almost the same as $M_w$ except it has $n_1$ isolated states. Now $M_w'$ and $M_w$ are functionally equivalent, and easy to see <$M_w'$> is accepted by $M$.

  So the language deciding by $M_d$ is what we want.


Will the minimum spanning tree not have only those edges specified by the cycle property?

Sorry if I didn't understand your question, but what I think you meant to ask is, whether it is possible for an edge to not be in a MST if this edge is not in a cycle.

Here's my answer.

Let us assume that we have an edge (u,v) in a graph G, that isn't part of a cycle. This would mean that there is no path from u to v that isn't the edge (u,v).
If the edge (u,v) weren't in the MST, this would mean that there is no path from u to v in this MST, meaning that the MST would be disconnected, and thus not an MST at all.
Hence if an edge is not part of a cycle, it must be in the MST of the graph.


How to calculate probability of packet loss and drop rate?

If you study M/M/1 queuing systems you'll probably know that such a queuing system can be seen as a markovian chain with birth rate λ and death rate $\mu$; that is to say that you change your state (and in an M/M/1 the state is the number of clients in the system) by unitary steps: $-1$ with rate $\mu$ and $+1$ with rate $\lambda$.

It is quite hard and long to explain in a thread like this and for this reason I suggest you to take a look at the markovian chains theory to understand why it works like this.
Anyway, I'll try to give you an idea: you can set a basic fluxus equation to describe the system:

$$P[x(t)=k] \mu = P[x(t)=k-1] \lambda$$

and analyzing the transition probabilities you will find:
$$
  P[x(t+h)=k+1 | x(t)=k] = \lambda h + o(h) \\
  P[x(t+h)=k-1 | x(t)=k] = \mu h + o(h)\\
  P[x(t+h)=k | x(t)=k] = 1-\lambda h-\mu h + o(h)\\
  P[x(t+h)=k+j | x(t)=k] = h + o(h)$$

with $h$ defined as very little piece of time.

So, defined $ρ=\frac{\lambda}{\mu}$ as the load factor of the system, you will find that (recalling the total probability theorem):

$$ P[x(t)=k] = (1-ρ) ρ^k $$

If you take a look at this result, you will recognize the answer to your question: if the system is a blocking system with blocking capacity $z$, the probability of packet loss is the following:

$$P[z\,\text{clients in the system}] = P[k\,\text{clients in the system}] = P[x(t)=k] = (1-ρ) ρ^k$$

Is it ok? :)


How can we solve halting problem efficiently?

The idea is to determine how many of the Turing machines halt. We will show more generally that given $N = 2^n-1$ many Turing machines $T_1,\ldots,T_N$, we can determine which of them halt (on the empty input) using only $n$ calls to an oracle that solves the halting problem.
First, let us see how to determine, using a single oracle call, whether at least $\ell$ of the Turing machines halt. The idea is to construct a Turing machine $S_\ell$ which runs all of $T_1,\ldots,T_N$ in parallel, and halts once $\ell$ of the machines have halted.
Given this, we can determine how many of $T_1,\ldots,T_N$ using binary search. In your case, $N = 3$, this proceeds as follows:

Determine whether at least two of $T_1,T_2,T_3$ halt.
If so, determine whether at least three of $T_1,T_2,T_3$ halt.
Otherwise, determine if at least one of $T_1,T_2,T_3$ halts.

Having found out that exactly $\ell$ of the machines halt, we simply simulate all the machines in parallel until $\ell$ of them halt. The remaining machines will not halt.
It would be interesting to figure out whether this is optimal, that is, whether we can determine the halting of more than $2^n-1$ machines using only $n$ oracle calls.


Show that TQBF $\notin$ SPACE$((\log{n})^4)$?

Hint: TQBF is PSPACE-complete, so it "requires" polynomial space. If there were an algorithm to solve TQBF using space $O(\log^4 n)$, you could use it to solve all problems in PSPACE using surprisingly small space. So surprising, in fact, that the space hierarchy theorem says it can't be.


Does time or space complexity of arithmetic operations get affected by the number of digits?

The complexity of arithmetic operations is typically measured in bit operations, though not everybody agrees this is the correct measure. There is a Wikipedia page listing the complexity of the best algorithms currently known for various operations, including addition and multiplication.


Does Damas-Milner still have principal types if existential type schemata are added?

Yes, adding existentials doesn't add many complications for type inference, if quantifier alternation is controlled carefully. This is not surprising since universals and existentials are dual and the the function space operator gives a form of negation. Small type annotations that can help regaining type-inference are discussed in (4).

Adding existentials to pragmatically viable programming languages was first discussed in N. Perry's dissertation (1).  Perry's work was later formalised by Odersky and Läufer in (2). Läufer also described how to integrate existentials with Haskell type classes (3).

1. N. Perry, The Implementation of Practical Functional Programming Languages.

2. K. Läufer, M. Odersky, Polymorphic type inference and abstract data types.

3. K. Läufer, Type classes with existential types.

4. M. Odersky, K. Läufer, Putting type annotations to work.


I think you've misunderstood how to apply ICP.  If you apply it correctly, ICP shouldn't have the problem you're worried about.

You're supposed to apply ICP to all the points.  Don't just select 4 of the points and apply ICP to those points; apply it to the entire set of points.  If you pick only 4 points, yes, ICP will have the problem you describe (it'll be sensitive to small errors in the point locations).  That's why we don't do that.  Instead, ICP applies least-squares regression to all the points.  This eliminates the problem: any small errors in the point locations are averaged out, by the least-squares regression.  So, try that.  I suspect you'll be fine.

I don't expect your centroid method to work very well.  It has several potential problems:

It matches the "centroid of visible points" (from the picture) to "centroid of all points" (from the database). However, there's no reason to expect those two centroids to be in the same place.  Consider an asymmetrical object with parts that are not visible; the two centroids might be at different positions, and if so, this will introduce a systematic and potentially large error into your results.
Matching only one vector isn't enough to allow you to correct for both translation and rotation.
It requires you to know, for the selected point from the picture, which the corresponding point in the database is.  However the whole point of this problem is that we don't know the correspondence.  You could try to select the closest point in the database, but this might be wrong, since the two point-clouds haven't been registered into the same coordinate system, so this might go horribly awry.

For these reasons I don't think your method sounds very promising.

Last remark: The problem you're trying to deal with is called point set registration.  I recommend you read up on standard methods for that problem before trying to invent a scheme of your own.


I finally figure out an answer. This paper "Nim Fractals" by Tanya Khovanova and Joshua Xiong gives a formula to count the solutions to $$\begin{cases} x_0 \oplus \cdots \oplus x_k =0 \\\sum_{i=0}^{k}x_i=S\end{cases}$$ in $O(kS)$. Denote the number as $f(k,S)$. We may utilize $f$ to see that the problem reduces to $\sum_{S=0}^{n-2k}\binom{n-k-S}{k}f(k,S)$. The overall complexity is $O(nk\cdot log(n))$.


efficiently calculate nearest common ancestor in a family tree (each person has two parents)

Just do breadth-first search up the graph, colouring each person you meet as being an ancestor of one person or the other, and stop when you reach a person who's an ancestor of both. You should do the searches in parallel (one generation back on one person, then one generation back on the other, and so on) because any common ancestor will be approximately the same number of generations back on each side.

Indeed, this is exactly what you should do on a tree: going all the way back to the root and then discarding all common ancestors after the first takes more time.


How to Determine Existence of Turing Reducible Languages?

To narrow down the search space, consider what you know about closure properties and HPL.

The class of decidable languages $R$ is closed against complement.
HPL is not in $R$.

You can conclude that $L \not\in R$;¹ otherwise, $\overline{L} \in R$ and therefore $\mathrm{HPL} \not\leq_T \overline{L}$.

On the other end, you need that $L \in RE$ (the set of semi-decidable languages) -- otherwise $L \not\leq_T \mathrm{HPL}$.

In combination, you need $L \in RE \setminus R$ which answers your question².

In particular, $L$ can not be finite since all such languages are decidable. The decider just checks a hard-coded table of all words in the language. With the same table you can also decide the complement.
Note how this implies $\overline{L} \not\in R$ which is enough for $HPL \leq_T \overline{L}$.


We'll use the max-flow min-cut theorem to solve this.

Therefore we map each instance $(G,K,\{c_{1},\dots,c_{k}\})$ to the network $N:=(V(G) \stackrel{.}{\cup} \{C\},E(N),e,K,C)$, where $C$ is a new vertex not in $V(G)$ (our sink), $K$ is our source and $e$ denotes the edge capacities,

$$E(N) := \{(u,v)|\{u,v\}\in E(G)\} \cup \{(c_i,C)|i\in\{1,\dots,k\}\}$$ and
$$e((u,v)) := \begin{cases}2|E(G)|+1&v=C\\1&\text{else} \end{cases}\qquad.$$

Then $(V_1,V_2)$ is a minimum $K$-$C$-cut in $N$ if and only if $(V_1,V_2\setminus\{C\})$ is  minimum cut in $G$ subject to the condition that $K\in V_1,\forall i: \, c_i\in V_2$:

"$\Rightarrow$": Every $K$-$C$-cut with the property $\forall i: \, c_i\in V_2$ has a capacity of at most $2E(G)$, every cut with $\exists i: \, c_i\in V_1$ has capacity of at least $2E(G)+1$. Therefore only those having the desired property can be a minimum cut. Since for each $(u,v), u\in V_1, v \in V_2$ of a minimum cut the edge capacity is $1$, $\mathrm{cap}(V_1,V_2)=||\{\{u,v\}\in E(G)|u\in V_1,v\in V_2\}||$.

"$\Leftarrow$": analogous to second part of "$\Rightarrow$".

If we have computed a maximum flow $f$ by e.g. the Edmonds–Karp algorithm, we compute the residual Network $N_f$ where $e(N_f)=e-f$ and $E(N_f)=E(N)\setminus\{(u,v)|f((u,v))=1\}$, i.e. we remove the edges used by the maximum flow. Let $V_1$ be the set of vertices reachable from $K$ in $N_f$ and $V_2=V(G)\setminus V_1$. Then $(V_1,V_2\cup\{C\})$ is a minimum cut in $N$ and thus $(V_1.V_2)$ is a minimum cut in $G$ separating $K$ and $\{c_1,\dots,c_k\}$.


Can be non-deterministic Turing machine simulated by $k$-tape deterministic TM where $k=\infty$ with preserving polynomially-same accepting times?

This is a very nice question, which rises often in computability courses.

Once you allow infinitely many tapes, with infinitely many read/write heads, then the model becomes way too powerful. Formally, consider any language $L\subseteq \Sigma^*$, here is an algorithm in your model that decides $L$ deterministically, and in linear time:

Scan the input tape, and write every letter on a new tape, move to state $q$.
We define the transition function as $\delta(q,w)=q_{acc}$ if $w\in L$, and $\delta(q,w)=q_{rej}$ otherwise.

By $\delta(q,w)$ we mean that the state is $q$, and the letters that are read by the infinite number of heads form the word $w$.

As you can see, we decide $L$ "by definition", and this definition is legitimate, since the transition table is infinite.

So your model can decide every language, which means that it provides no differentiation of language classes. So theoretically, we just showed that it's "not interesting".


Simple example for Higher Order Abstract Syntax (λ-tree syntax)

Well, this is a bit broad but the basic idea is the following. In First-order abstract syntax (FOAS) we model lambda terms following their syntax tree. E.g., in Coq we would write

(* FOAS *)
Definition variable := string .
Inductive term: Set :=
  | var: variable -> term
  | app: term -> term -> term
  | lam: variable -> term -> term
.

Definition example: term := lam "x" (app (var "x") (var "x")) .

Note how we model $\lambda x. xx$ by storing the name "x" explicitly.
In a sense, a lambda is represented as a pair (variable name, body).

In FOAS we need to carefully handle alpha-conversion and capture-avoiding substitutions.

In HOAS, we model lambdas as functions, not pairs, exploiting the functions in the host language.

(* HOAS *)
Inductive term: Set :=
  | var: variable -> term    (* vars are usually removed in HOAS *)
  | app: term -> term -> term
  | lam: (term -> term) -> term

Definition example: term = lam (fun x: term => app x x) .

(Note that this won't type check in Coq since it does not use positive recursion, as Mario Carneiro points out below. Still, you get the idea.)

No need to handle alpha-conversion (or substitutions) here since the name "x" is no longer stored in the term.

What we lose in HOAS is the ability to dissect the term representation (e.g. structural induction on the syntax tree) as easily as we could in FOAS.


Find longest path in graph with N nodes and N edges

The greedy solution is not correct.

Let me construct a graph with $5$ vertices, $A$, $B$, $C$, $D$, $E$.

$AB$ is an edge with weight $1$.

$BC$ is an edge with weight $2$.

$AC$ is an edge with weight $2$.

$AD$ is an edge with weight $100$.

$CE$ is an edge with weight $100$.

The longest (heaviest) path is $DABCE$ with weight $203$. After removing $AB$, which is the lightest edge of the cycle $ABC$, the longest path is $DACE$ with weight $202$.


Recognizing a language given an automaton

In general, there is a dynamic programming algorithm for converting finite automata into regular expressions. But this one is simple enough that we can eyball it.

From the start state, we have two choices. So we can see our expression has the form | where _ represents the parts of the expression yet to be filled in.

Let's look at the top branch. There we must read two a's, then as many a's or b's as we want. So this part will have the form aa(a|b)*

For the second half, we see we must read at least one a or b. Then we can loop on a or b as many times a we want, and then we must read two a's. So we get (a|b)(a|b)*aa

Notice the patterns here. When we have more than one transition coming out of a state, that represents the "|" operation. A transiton on "a,b" is equivalent to having one transition on a and another on b.

So, our final expression is (aa(a|b)*) | ((a|b)(a|b)*aa).

Any time we have a cycle, either on a particular state, or on a path of states, we get something corresponding to *. And every time we have to read something in sequence, we have concatenation.


What does "finite state transduction" mean?

A finite state transducer is a machine model, much like a finite state automaton, but equipped with two tapes, one for input and one for output. Each specific finite state automaton defines a binary relation between input and output strings.

Your assumption is right: for each input string we look at computations that match that string and output the corresponding strings on the second tape. This process can be highly nondeterministic, as symbols can be deleted and inserted at will (when the automaton is programmed to do so).
This definition is extended to languages: each transducers defines a binary relation on languages too.

Transducers can be found for a very broad class of tasks: homomorphisms, inverse homomorphisms, intersection or quotient with (a fixed) regular language.
Finite state transducers are nice devices, e.g., they can be programmed to deleted every second $a$ in a string, but only for strings ending in a $b$.

The wikipedia article on FST ignores a very important basic fact on transductions. They happen to be equal to the class of operations built from homomorphisms, inverse homomorphisms and intersection with regular languages. Each family closed under these operations is called a trio, and such a class is then closed under all FST's. Examples are the family of regular languages and the family of context-free languages. So as a consequence, given a CFL, the language we obtain by erasing every second $a$ (for strings that end in a $b$) is again context-free.


Pseudo-polynomial time algorithm for NP-Complete Problems

An algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric values in the input. It doesn't make sense to talk about pseudo-polynomial time algorithms for all problems in $NP$ since many of them do not have numeric values in their input at all.

However, if you are looking at two problems for which the definition does apply (for instance 2-Partition (weakly $NP$-complete, has a pseudopolynomial time algorithm) and 3-Partition (strongly $NP$-complete, not believed to have a pseudopolynomial time algorithm) then how is it possible a polynomial reduction from 3-Partition to 2-Partition does not result in a pseudopolynomial algorithm for 3-Partition?

The answer is that a polynomial reduction may create very large numeric values. Every known reduction from 3-Partition to 2-Partition creates numbers that are exponentially bigger than the orignal numbers. Exponentially larger numbers only take polynomially more space to represent, so a polynomial reduction can very easily create exponential numeric values.

So even though we have a pseudopolynomial time algorithm (that runs in polynomial time in the numeric values of the input) for 2-Partition it does not work as a pseudopolynomial time algorithm for 3-Partition, because the reduction makes the numbers much larger, so the algorithm is no longer pseudopolynomial in the original numbers.


What are the best ways to find errors in a sequence of messages (strings)?

Not sure if I get your question right, as you didn't specify whether this is a theoretical problem or a practical.

Assuming it is practical problem, there are quite some algorithms (e.g. TCP) depending on which layer your messages are being send (if they are being send at all).

Assuming it is more of a theorectial problem you can use stuff like the Hamming distance.

Maybe check: Computer Networks by Andrew S. Tanenbaum


Is finding all primes less than n, doable in polynomial time?

No, it doesn't.  There are exponentially many primes less than $n$, so you can't enumerate them in polynomial time.


PDA accepting of a specific symmetric language

There are general constructions that give a PDA given a CFG.
In this case, start with the PDA for $\{a^n b^n \colon n > 0\}$, instead of storing one $A$ on the stack for each input $a$, store two, and the same for $b$. When reaching the middle, start discounting and accept by empty stack.


If your input consists of integers, that is your elements are from the set $\mathcal{U}=\{0,\ldots,u-1\}$, you can sort faster than $O(n\log n)$ assuming your model of computation is the word RAM.

you can sort deterministically (even on using $\text{AC}^0$ computations) in time $O(n \log\log n)$
there is a randomized algorithm that sorts in $O(n \sqrt{\log\log n})$
if your word size $w=\log u$ is in $\Omega( \log^{2+\varepsilon} n)$ for some $\varepsilon>0$ then the input can be sorted in linear time

If you are interested in the references, check out Erik Demaine's lecture notes. Note that all these results use in some sense the effect that you can parallelize some computations on the word ram using bit tricks. It does not requires that the numbers are picked uniformly at random from $\mathcal{U}$.


What is a good path for self-study of CS foundations/fundamentals?

Check out this and this. I prefer the former one cause the number of subjects is relatively small, and they are the core fundamentals.


Applying DFS algorithm to a transition system to find reachable states

You can design an algorithm to traverse the product of two TSs.
With a simple DFS algorithm, start from start state and with rules for handshaking generate next states.
You need to keep the states that has been visited so far to avoid loop.
There may be more efficient ways but here is a sudo-code of a solution:

stack = new Stack()
visited_states = new Array()
stack.push(start_state)
while ~stack.isEmpty() {
    current_state = stack.pop()
    if current_state not in visited_states {
        visited_states.add(current_state)
        next_states = generate_next_states(current_state)
        for each state in next_states {
            stack.push(state)
        }
    }
}

Where generate_next_states is a function that generates next states according to the rule in page 48, Figure 2.11.
Now the set of states in visited_states are reachable states.


Running time of a function $P$ calling itself via $P(P(n/2))$

There is an unwritten assumption that the input is always at least $1$ (otherwise your function never terminates). Under this assumption, it is easy to prove by induction that the function does terminate, and always returns $1$. Therefore in the expression $P(P(n/2))$, we are first invoking $P$ with the input $n/2$, and then with the input $1$. It follows that the running time $T(n)$ of your function satisfies the recurrence $$ T(n) = T(\lfloor n/2 \rfloor) + \Theta(1), $$ with initial condition $T(1) = \Theta(1)$. The solution is $T(n) = \Theta(\log n)$.


How do we analyze Algorithms with parallelism features

The conceptual/abstract model I use when developing a parallel algorithm is (loosely) Leslie Valiant's Bulk Synchronous Parallel model.

You have $P$ processors (where $P$ is typically some small number like 4, 8, 16, maybe 128, but certainly $P \ll N$).  You are trying to design an algorithm where you spend most of your time computing in parallel, then you use a barrier to synchronize the processors, then do some communication between processors, synchronize again, and then go on to the next parallel computation step.  It is called bulk synchronous because you can think of the algorithm as a series of steps where the work inside each step is completely asynchronous, but the steps happen one at a time and in order.

There are a handful of different things you need to worry about that all interact and have inescapable tradeoffs.

Algorithm efficiency.  You should have a best sequential algorithm you are using as a baseline.  Often the best sequential algorithm won't parallelize well (because of all the rest of this list) so your parallel algorithm may require substantially more work.  For example: There are often clever sequential algorithms that are $O(N \log N)$ where the only realistic parallel algorithms are $O(N^2)$.  Alpha-Beta pruning tree search algorithms are another case where you may need to do (significantly) more work to avoid synchronization/communication overheads.
Work independence. You need to choose an algorithm where, in each bulk step, there are approximately $O(N)$ (or more) independent pieces of work to do.
Load imbalance.  During each step of the algorithm you want to break the work into $P$ nearly-equal chunks.  If the chunks are unequal then each bulk synchronous step will take the amount of time for the largest chunk and many of your processors will spend a significant portion of their time idle.  Examples of load imbalance problems happen with:

divide and conquer algorithms (the first step has to happen on one processor, then you get two (perhaps unequal chunks) so the second step happens on two processors.  It takes $O(\log P)$ steps to get all $P$ processors working, and the amount of work they are doing may not be similar, let alone the same.)
hashing algorithms (it depends on whether your hash function is distributing the data evenly among hash buckets or whether there is some bias.  The bias ends up as load imbalance.)
sparse graphs and sparse matrices.  (Similar to the hashing problem.  It may be easy to divide up the number of nodes in your graph evenly, but the number of edges per node determines the amount of work so two chunks with similar numbers of nodes may have very different amounts of work involved.)

Synchronization overhead.  Synchronization is "pure overhead". It is added cost for parallelization that simply isn't required in the sequential algorithm.
Data communication overhead.  This one is quite tricky because it interacts with a problem (cache locality) that is quite difficult in the sequential case as well.
Reductions.  Often some of your work looks unavoidably sequential, but involves associative operators that can be mostly parallelized (with some cleverness, and assuming that your hardware supports it.)  Similarly you sometimes have operators that are (a) associative, (b) commutative and (c) applied sparsely, in which case it may be possible to parallelize a chunk of code using fine-grained mutual-exclusion (locks).
SIMD hardware limitations.  The Bulk Synchronous Parallel model is single-program-multiple-data (SPMD).  In each chunk of work between barrier synchronizations each processor has something like $O(N/P)$ work to do, and that work may require a substantial amount of data-dependent branching.  But most modern parallel hardware exposes a substantial fraction of its parallelism only with single-instruction-multiple-data (SIMD) short-vector units.  This means that you have to go beyond the work independence in step (2) above.  You have to find work to do that is not just independent but where there are few (hopefully none) data-dependent branches for each chunk of work.
Accelerator data marshalling.  This is starting to get better, but for the moment many parallel accelerators (GPGPUs) require you to move data back and forth between the accelerator and the processor at each barrier synchronization point.  This means that you need to find more work independence to make the cost of using the accelerator break even.

That's a lot to keep in mind, but you can often think about it a little more simply.

Rewrite the sequential code using the least clever algorithm you can think of.
Look for the loop nest where you are spending most of your time (use a profiler.)
Choose the outer-most loop where the iterations are independent of one another.
Turn that loop into a parallel-for (using whatever method your programming language and/or libraries provide.)
Hope that everything else works out.


Your problem is #P-hard. Indeed, given a #SAT instance with variables $x_i$ and clauses $C_j$, let $\kappa_{i,b}$ be the product of the clauses $C_j$ satisfied by the truth assignment $x_i=b$, and consider
$$ P = \prod_i (\kappa_{i,0} + \kappa_{i,1}). $$
The coefficient of $\prod_j C_j$ in $P$ is the number of satisfying assignments.

In the other direction, the special case where the input formula is $\Pi\Sigma\Pi$ (that is, the product of polynomials) is #P-complete. Suppose that we are interested in the coefficient of some monomial $m$ in $\prod_k P_k$, where the $P_k$ are polynomials. Substitute zero in all variables not appearing in $m$. Now guess one term from each $P_k$, and accept if the terms together cover $m$.


Language grammar correction with supervised learning

The following paper from 2011 proposes a nice approach for using language modeling to do grammar correction, as well as an evaluation framework.

Park and Levy, Automated whole sentence grammar correction using a noisy channel model. In Proc. 49th Human Language Technologies, volume 1, pp. 934–944. Association for Computational Linguistics, 2011. (Available from the ACM Digital Library.)


Give a grammar for a language on Σ={a,b,c} that accepts all strings containing exactly one a

$$S\rightarrow aA, bS,cS$$

$$A\rightarrow bA, cA, \epsilon$$

Note that you need at least two non-terminals for this language, since you need to differentiate two states, namely whether an $a$ has already been added/found or not.


Which algorithm suits this problem best?

I thought of a method to state this problem completely in terms of metric vertex weights, which could be considered a (very non-standard) kind of TSP.

In particular, look at the following subproblem:

  Given a graph $G=(V,E)$, with an initial vertex $v_0\in V$, a distance function $d : E\rightarrow \mathbb{R}^+$ such that the graph is metric, a function $p : V \rightarrow \mathbb{R^+}$ that assigns points to vertices, a maximum distance $D$, a minimum value $P$ and an integer $k$.
  Determine if there exists a (simple) tour on $G$ starting at $v_0$ of exactly $k$ vertices such that the total distance is less than $D$ and the sum of the points $p(v)$ is at least $P$.

So, we want to find a tour of vertices $v_1,\ldots,v_k$ with total distance at most $D$, so $\sum_{i=1}^{k-1} d(v_i,v_{i+1})\leq D$. Additionally, we want to have enough POI points, so $\sum_{i=1}^{k} p(v_i)\geq P$. We will rewrite to the second condition to be similar to the first.

We can replace the second condition by $\sum_{i=1}^{k} -p(v_i)\leq -P$, but now we have negative weights. Since we have fixed $k$, we can solve this by adding the value $p^* =\max_{v\in V}p(v)$ to every individual point: set $p'(v_i):=p^*-p(v_i)$ and $P':=k\cdot p^* - P$, so we get $\sum_{i=1}^{k} p'(v_i)\leq P'$. Now, $p'(v_i) = p^*-p(v_i)$ is non-negative, and we may assume $P'=k\cdot p^*-P$ non-negative, since we know for sure that we cannot get enough points in any tour of $k$ vertices otherwise.

Now, the difference is that points are assigned to vertices in stead of edges. We solve this by defining $p'(v,w):= \frac{1}{2}(p'(v) + p'(w))$ and now we require $\sum_{i=1}^{k-1} p'(v_i,v_{i+1})\leq P'$. This is still equivalent to the previous condition, as we must leave and enter every vertex on a (simple) tour exactly once. Note that $p'(v,w) \leq p'(v,w)+ p'(u) = \frac{1}{2} (p'(v) + p'(w)) +p'(u) = \frac{1}{2}(p'(v)+p'(u)) + \frac{1}{2}(p'(u) +p'(w)) = p'(v,u) + p'(u,w)$ for any $u,v,w\in V$, since $p'(u)$ is positive. So, the distance $p'$ is metric on $G$, as it satisfies the triangle inequality.

Now, there are no more differences between the pairs $(p',P')$ and $(d,D)$. This means that we can phrase our subproblem as follows: determine if there exists a simple tour of exactly $k$ vertices of length at most $P'$ under metric $p'$ AND of length at most $D$ under metric $d$. I call this the $k$-vertex simultaneous TSP.

Note that this problem, if we assume $(p',P')$ arbitrary, could actually be a lot harder than the current problem. $(p',P')$ is extremely 'regular' for a TSP, since the order in which we visit the vertices doesn't matter for this metric. (which should be the case, since it didn't matter in the original formulation either)

Initially, I thought this approach would lead to a regular TSP problem, but it seemed more unlikely as I wrote it down. Nevertheless, I think the ideas here can be useful in approaching the problem, at least. I don't see a way to 'combine' the different distances for an exact solution, but it might be possible if we are satisfied with an approximation.


How to partition the rows of a matrix in such a way that every column satisfies a given condition?

As suggested by Yuval Filmus, reduce PARTITION to my problem.

Given an instance of PARTITION, that is a set of nonnegative integers $\{b_1, \ldots, b_k\}$, is there a subset $S\subset\{1,\ldots,k\}$, such that $\sum_{i\in S}b_i=\sum_{i\notin S}b_i=\frac{\sum_{i=1}^kb_i}{2}$?

Let $n=2$, $m=k$, $a_{ij}=b_i$ for all $(i,j)\in\{1,\ldots,k\}\times\{1,2\}$ and $V_1=V_2=\frac{\sum_{i=1}^kb_i}{2}$.

This is clearly created in polynomial-time.

PARTITION is solved if and only if my problem is solved.

If PARTITION is solved: there is a set $S\subset\{1,\ldots,k\}$, such that $\sum_{i\in S}b_i=\sum_{i\notin S}b_i=\frac{\sum_{i=1}^kb_i}{2}$. Take $S_1=S$ and $S_2=\{1,\ldots,k\}\backslash S$. Clearly, $S_1\cup S_2=\{1,\ldots,k\}$ and $S_1$ and $S_2$ are disjoint. Further, we have
$$\sum_{i\in S_1}a_{i1}=\sum_{i\in S_1}b_i=V_1\geqslant V_1,\\
\sum_{i\in S_2}a_{i2}=\sum_{i\in S_2}b_i=V_2\geqslant V_2,$$
and my problem is solved.
If my problem is solved: there are disjoint $S_1$ and $S_2$ such that
$$S_1\cup S_2=\{1,\ldots,k\},\\
\sum_{i\in S_1}a_{i1}=\sum_{i\in S_1}b_i\geqslant V_1,\\
\sum_{i\in S_2}a_{i2}=\sum_{i\in S_2}b_i\geqslant V_2.$$
Since $V_1=V_2=\frac{\sum_{i=1}^kb_i}{2}$ and $\sum_{i\in S_1}b_i+\sum_{i\in S_2}b_i=\sum_{i=1}^kb_i$, we must have
$$\sum_{i\in S_1}b_i=\sum_{i\notin S_2}b_i=\frac{\sum_{i=1}^kb_i}{2},$$
and PARTITION is solved.

Therefore, my problem is NP-hard.

To solve the problem, let us write it as integer programming problem as suggested by Yuval Filmus. To do so, introduce the binary variable $x_{ij}$ that is equal to $1$, if $i$ is in set $S_j$, and, $0$ otherwise.

\begin{align}
      & {\underset{\mathbf{ x }}{\text{maximize}}}
      & & 0\\[6pt]
      & \text{subject to}
      & & \sum_{i=1}^ma_{ij}x_{ij}\geqslant V_j,\forall\, j\in\{1,\ldots,n\},\tag{C1}\\[6pt]
      & & & \sum_{j=1}^nx_{ij}=1, \forall\, i\in\{1,\ldots,m\},\tag{C2}\\[6pt]
      & & & x_{ ij }\in\{0, 1\}, \forall (i,j)\in\{1,\ldots,k\}\times\{1,\ldots,n\}\tag{C3}.
    \end{align}

Even though this solves my problem, I need to develop a greedy algorithm for it, can I do that?


How to find rows of matrix that are zero everywhere except for 1 entry?

There is no algorithm with worst-case running time better than $O(n^2)$.  There is a simple adversary argument to prove this.

Consider any algorithm that is purported to be correct, and that always inspects fewer than $n^2$ entries of the matrix. Thus, there must always be some entry that is uninspected.  Consider a matrix that has 1's in the entire first column.  Every time the algorithm inspects any other entry, it will find a 0.  After inspecting at most $n^2-1$ entries, the algorithm terminates and outputs some list of rows.  Pick any entry that was uninspected.  Now we have a freedom about whether to fill it in with a 0 or a 1; and we can always make a choice that will make the algorithm's output wrong (if the algorithm included that row in its output, make it a 1; otherwise make it a 0).  So, for any correct algorithm, it must inspect all matrix entries for at least some inputs, so its running time must be at least $\Omega(n^2)$.

There are various optimizations you can use in practice, like using bitwise operations (depending on how the matrix is stored), and if you see more than a single 1 in any row, don't look at any other entries in that row -- but these won't affect the asymptotic worst-case running time.


Let's consider "half" of your problem: $S\to AbASc \mid \epsilon$, and $A\to aA \mid \epsilon$. It is important to realize that the number of $b$'s and $c$'s generated is equal. Try to express that in your solution.

At the same time, when two $A$'s are generated, they will generate an arbitrary number of $a$'s. One of your solutions claims these numbers are always the same, but they are not.

Personally I would prefer to write this language as $L(G_{\frac12}) = \{ wc^k \mid w\in\{a,b\}^*, k\ge1, \#_b(w) = k\} \cup \{\epsilon\}$, where $\#_b(w)$ is the notation for the number of occurrences of letter $b$ in the string $w$.
Alternatively, if you want to avoid that notation perhaps $L(G_{\frac12}) = \{ a^{n_0}ba^{n_1}b\dots ba^{n_k}c^k \mid k\ge1, n_0,\dots,n_k\ge 0\}\cup \{\epsilon\}$.

It is not immediate how to write this using "regular expressions" as the equality of the number of $b$'s and $c$'s is not regular property itself. Also we cannot put the star-operator inside set brackets, as the star yields a language itself, so it would be proper to write
$L(G_{\frac12}) = \bigcup_{k\ge1} (a^*b)^ka^*c^k \cup \{\epsilon\} = \bigcup_{k\ge0} (a^*ba^*)^kc^k $ .

Sorry about the $\dots \cup \{\epsilon\}$ in several of these solutions. Allowing $k=0$ would not give the right answer, as that would add $a^*$ to the language, which is not generated by the grammar.


Auction where each bidder bids on a bundle of items

This problem is NP-hard, by reduction from 3-dimensional matching.

An instance of 3-dimensional matching involves three disjoint vertex sets $X,Y,Z$ and a set $T \subseteq X \times Y \times Z$ of triples of the form $(x_i,y_j,z_k)$.  The goal is to find a subset $T_0 \subseteq T$ such that each vertex of $X \cup Y \cup Z$ appears in at most one triple of $T_0$, and the cardinality of $T_0$ is maximized.

Given an instance of 3-dimensional matching, we can construct an auction with bidders $X$ and items $Y \cup Z$.  For each $(x,y,z) \in T$, we'll have $x$ bid \$1 on the pair of items $y,z$.  Now the optimal set of accepted bids for the auction is exactly the maximum 3-dimensional matching, so any algorithm to solve your problem would also solve 3-dimensional matching.

Since 3-dimensional matching is known to be NP-hard, it follows that your problem is also NP-hard, and in particular, there isn't likely to be any efficient algorithm for your problem.

The same reduction also shows that your problem is APX-hard, i.e., there is some $c>1$ such that there does not exist any $c$-approximation algorithm for your problem (unless P=NP).

I don't know whether there might be an approximation algorithm for some constant approximation factor.  It's known that 3-dimensional matching can be approximated in polynomial time with a $3/2 + \varepsilon$ approximation factor; you might check whether any of those algorithms can be adapted to provide suitable solutions for your problem.  For instance, one very simple approach might be to find a maximal matching of the associated hypergraph; this will give a $1+k$ approximation, if every bid mentions at most $k$ items.  I don't know if you can find maximal matchings in hypergraphs in polynomial time, like you can in ordinary graphs.

Practical algorithms

If you have to deal with this problem in practice, I suggest formulating it as an integer linear programming (ILP) problem and then applying an off-the-shelf ILP solver.

Introduce zero-or-one variables $x_i$, with the intended meaning that $x_i=1$ means that the $i$th bid is accepted.  Each constraint "at most one bid is accepted from each person" turns into a inequality of the form $\sum_{i \in S} x_i \le 1$.  Each constraint "each item appears in at most one accepted bid" turns into another inequality of the same form.  The objective function is a linear function of the $x_i$'s.  Now apply an off-the-shelf ILP solver, like CPLEX.


Why is the Halting problem decidable for Goto languages limited on the highest value of constants and variables?

There is a finite number of different states (the set of values of the variables and the program counter). Your "limited goto programs" are just a (messy) way to describe a deterministic finite automaton.
Or just reason that the program states being finite, it is certainly possible to map out all possible non-looping computations (by something like a breadth first search of the graph of states and neighbours).


If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?

People are skeptical because:

No proof has come from an expert without having been rescinded shortly thereafter
So much effort has been put into finding a proof, with no success, that it's assumed one will be either substantially complicated, or invent new mathematics for the proof
The "proofs" that arise frequently fail to address hurdles which are known to exist. For example, many claim that 3SAT is not in P, while providing an argument that also applies to 2SAT.

To be clear, the skepticism is of the proofs, not of the result itself.


How to prove that the Church encoding, forall r. (F r -> r) -> r, gives an initial algebra of the functor F?

$\newcommand{\fix}{\mathsf{fix}}$
$\newcommand{\fold}{\mathsf{fold}}$
$\newcommand{\map}{\mathsf{map}}$
Here is, I believe, how one would use parametricity to prove your last lemma. I'm going to rework some stuff slightly for my own understanding. We have: $$C = ∀ r. (F r → r) → r$$ with $F$ functorial. We have: $$\fix : F C → C$$ corresponding to your definition, and I'm going to call a generalization of your m: $$\fold : (F r → r) → C → r \\ \fold\ α\ c = c\ α$$
So, we want to prove that for all $c : C$, $\fold\ \fix\ c = c$
Parametricity looks like this:
$$∀(R : a \Leftrightarrow b).\\ ∀ (α : F a → a) (β : F b → b).\\ (∀ x y. FR(x,y) → R (α\ x, β\ y))\\ → ∀ c. R (c\ α, c\ β)$$
To unpack this a bit, if we have a types $a,b$, a relation $R$ on them, algebra structures $α,β$, and a proof that they preserve the relation, then $R$ relates $c \  α$ to $c \ β$. The idea behind the "preservation" criterion is that $FR(x, y)$ holds if $x$ and $y$ have the same $F$ 'shape', and corresponding occurrences of $a$ and $b$ values are related by $R$.
So, let's make some choices. Suppose we have $ζ : F z → z$. Then: $$a \equiv C \\ b \equiv z \\ R(c, z) \equiv c\ ζ = z \\ α \equiv \fix \\ β \equiv ζ$$ the result of parametricity for these choices will be: $$R(c\ \fix, c\ ζ) \equiv c\ \fix\ ζ = c\ ζ$$
Then by function extensionality we will obtain $c = c\ \fix = \fold\ \fix\ c$. Our obligation is to prove:
$$∀ fc\ fz. FR(fc,fz) → R (\fix\ fc,ζ\ fz)$$
The goal is $$\fix\ fc\ ζ = ζ\ fz$$
By unfolding the definition of $\fix$ we know: $$\fix\ fc\ ζ = ζ (\map_F\ (\fold\ ζ)\ fc)$$
However, the meaning of $FR(fc,fz)$ is actually that $$\map_F\ (\fold\ ζ)\ fc = fz$$ So the result is immediate.
I haven't thought about whether it's possible to make due with dinaturality. I think it is not, but I could be wrong.
Edit:
The free theorem for this scenario is:
$$(∀ x. f (α\ x) = β (\map_F\ f \ x)) \Rightarrow f (c\ α) = c\ β$$
If we choose $$f = \fold\ ζ \\ α = \fix \\ β = ζ$$ then our obligation is:
$$\fold\ ζ\ (\fix\ x) = \fix\ x\ ζ = ζ (\map_F\ (\fold\ ζ)\ x)$$
which is just the definition of $\fix$. The result is:
$$\fold\ ζ\ (c\ \fix) = c\ ζ$$
which again gives us what we wanted. Note that this is also not the same as dinaturality, though. I believe the difference is that dinaturality allows us to shift $f$ around in the expression, but parametricity allows us to absorb it into one of the algebras.


In cache addressing, what value is placed in the offset field?

Paul A. Clayton gives the answer in a comment.

You say a word has 32 bits. An implicit assumption is that we want to be able access every of the four bytes, so we need two bits to make this distinction.


Question about pointer in PCB structure and meaning of job queue

PCB structure exists inside kernel area. And in ready queue, which is Linked List, each Node of the queue is PCB.

This is correct, however in most operating systems, ready tasks are sorted by priority to ensure that the most important task will run next. So the design of the ready queue may be more sophisticated than this in practice.

Does PCB structure has pointer field that has address of next PCB structure??

This is the way that it's usually done. Of course, if it is implemented as a doubly-linked list, it will have a "previous" pointer too.

According to Wikipedia, Job Queue [...]

I can see why this may be confusing. The Wikipedia page that you're talking about is about batch processing systems. This is a related idea, and there are batch processing systems without user interaction, but it's not relevant to what you're trying to understand.


The best way (in terms of laziness)  is to use the freely available tool Sage which has the best support for graph theory.

Example

sage: G = graphs.PetersenGraph()
sage: G.has_homomorphism_to(graphs.CycleGraph(5))
False
sage: G.has_homomorphism_to(graphs.CompleteGraph(5))
{0: 0, 1: 1, 2: 0, 3: 1, 4: 2, 5: 1, 6: 0, 7: 2, 8: 2, 9: 1}


Why table-driven LL (1) parser does not work with division and subtraction?

If you naively generate a parse tree from

$$\begin{align}T\to& FT'\\
T'\to& *FT' \\
\mid&\; /FT' \\
\mid&\; \epsilon\\
\end{align}$$

then you're going to end up with something like this:

         T
        / \
       /   \
      /     \
     F       T'
     |      /|\
     6     / | \
          /  |  \
         *   F   T'
             |  /|\
             3 / | \
              /  |  \
             ÷   F   T'
                 |   |
                 2   ε

What you really want is this:

         T
        /|\
       / | \
      /  |  \
     T   ÷   F
    /|\      |
   / | \     2
  /  |  \
 T   *   F
 |       |
 F       3
 |
 2

But that belongs to a different, left-recursive grammar:

$$\begin{align}T\to& T * F\\
\mid&\; T / F\\
\mid&\; F
\end{align}$$

To use the second grammar, you'd need to use a different parsing technique (not the end of the world :-). To get the second parse tree, you need to do a little surgery while constructing it (or in a post-parse tree-walk, but that seems like overkill).

Because LL grammars cannot deal with left-recursive grammars, they cannot directly represent left-associative operators (which is most operators). Without left-recursion, you only have one way to represent a repetition, which means you have to use the same style to represent both left-associative and right-associative operators. That's not an issue in practice -- you certainly know the associativity of all operators in your language -- but you might find it annoying that you need to annotate the parser in order to get the right parse. If you use a bottom-up parsing technique, this annoyance vanishes.


Show that there are infinitely more problems than we will ever be able to compute

Reformulating in a more mathematically precise way, what the lecturer is trying to say is this: Any algorithm can be (uniquely) encoded as a finite string of bits, and any finite string of bits (uniquely) encodes a program; hence, there is a bijection between $\mathbb{N}$ and the set of algorithms, so both are countable sets. Conversely, having fixed an ordering of strings, any decision problem $P$ can be (uniquely) encoded as an infinite string of bits, where the $i$-th bit represents whether the $i$-th string is in $P$ or not, and any infinite string of bits (uniquely) encodes a decision problem (in the same fashion); hence, $\mathbb{R}$ and the set of decision problems are both uncountable sets.


Classification of technologies used for communication in distributed systems

Finally I decided to classify the distributed system technologies by the communication paradigm that they implement. The categories of communication paradigms I considered are:

Remote Procedure Call
Berkeley Sockets
Message Passing Interface
Message Oriented Middleware
Distributed Shared Memory
Stream Oriented Communication
Multicast Communication (based in peer-to-peer architecture)

I still have to do some research about some more modern implementations that can eventually use a paradigm not listed here.


Can all regular tree types be expressed as $\mu$ types?

You can reduce mutual recursion to a single recursion, see Bekic's Theorem, see e.g. Section 10.1 of Winskel's (1), where Bekic is worked out for programs rather than types. Note however that the details depend on the exact nature of the formal system in question. See A. Bauer's answer in (2) for the case of types.

G. Winskel, The Formal Semantics of Programming Languages.
CSTheory Stackexchange, Can Isorecursive types capture mutually recursive data types?


Can a loop be expressed by only the sequence of statements and the choice of statements?

I convinced myself that this is not possible, I was indeed mixing up the selection structure with conditional jumps; but they're not equally expressive.

The conditional jump is as powerful as both selection and iteration together; this is what compilers use to rewrite both choice statements and loop statements.

As a counterexample for rewriting any loop using only the first two control structures, think of an infinite loop. This can not be rewritten using only sequence and selection while it can be rewritten using sequence and conditional jumps. So, we would lose expressiveness if we went without iterations.

Addendum to clear up the terminology:

Sequence
Selection (synonymous to choice), for example IF or SWITCH
Iteration (synonymous to loop), for example WHILE or FOR


Can someone let me know if my understanding of amortized run time in a dynamic array list is correct?

The cost of adding one item at the end of the array of size n can be as large as O(n), but usually is much faster. That's why we use the term "amortized time". The work you did to add item #512 pays back for items 513 to 1023. It is "amortized".

The amortized cost per items is O(1), since the cost of adding n items individually is O(n).

There are various reasons why you have to be carefully with amortized cost: If you have a real time system where taking O(n) to add a single item in rare cases is not acceptable. For example, a system controlling the brakes of your car that has an amortized cost of 0.001 seconds for using the brakes once, but every 10,000 times takes 10 seconds is going to kill you.

There's also a difference between k individual operations, and combining k operations. If you have a sorted array of n items, and add a random item, keeping the array sorted, that takes O(n). However, if you want to add k items all in one go, keeping the array sorted, that takes O (n + k log k) (by sorting the k items first, then inserting them in one go). It is quite often that doing k operations can be done faster than doing one operation k times.


Let $X = \{x_1, \dots, x_n\}$ be an instance of $3$ partition where $n$ is a multiple of $3$ and each $x_i$ is strictly between $\frac{3}{4n}\sum_{i=1}^n x_i$ and $\frac{3}{2n}\sum_{i=1}^n x_i$. The problem remains NP-hard even with this restriction.

The instance of the job scheduling decision problem has $n$ jobs, $t_i = x_i$, $k=\frac{n}{3}$, and $T=\frac{3}{n}\sum_{i=1}^n x_i$.

If the 3-partition instance is a "yes" instance, then there is a partition of $X$ into $\frac{n}{3}$ sets $X_1, X_2, \dots, X_{\frac{n}{3}}$ such that, for each $j=1, \dots, \frac{n}{3}$, $\sum_{x \in X_j} x = \frac{3}{n}\sum_{i=1}^n x_i$.
Let $\alpha(i)$ be the index $j$ of the unique set $X_j$ containing $x_i$.
Then $\alpha$ is an assignment for the job scheduling instance in which, for each $j=1,\dots,\frac{n}{3}$,  $u_j = \sum_{i : \alpha(i)=j} = \sum_{x \in X_j} x = \frac{3}{n}\sum_{i=1}^n x_i = T$. This shows that the job assignment instance is a "yes" instance.

If the job scheduling instance is a "yes" instance, then let $\alpha$ be a corresponding assignment. For each $j=1,\dots,\frac{n}{3}$:

$|\{i : \alpha(i)=j\}| \le 3$, as otherwise $u_i > 4 \cdot \frac{3}{4n}\sum_{i=1}^n x_i = T$.
$|\{i : \alpha(i)=j\}| \ge 3$, as otherwise $u_i < 2 \cdot \frac{3}{2n}\sum_{i=1}^n x_i = T$, implying that $\max_{j' \neq j} u_j \ge \frac{\sum_{i=1}^n x_i - u_i}{\frac{n}{3}-1} > \frac{\sum_{i=1}^n x_i - T}{\frac{n}{3}-1} = \frac{\frac{n-3}{n}\sum_{i=1}^n x_i}{\frac{n-3}{3}} = \frac{3}{n}\sum_{i=1}^n x_i = T$.

As a consequence, the sets $X_1, \dots, X_{\frac{n}{3}}$, where $X_ j = \{x_i : \alpha(i)=j\}$, contain $3$ elements each and form a partition of $X$. Moreover, $\sum_{x \in X_j} x = u_j \le T = \frac{3}{n}\sum_{i=1}^n x_i$ and an argument similar to the one above shows that $\sum_{x \in X_j} x \ge \frac{3}{n}\sum_{i=1}^n x_i$. This proves that $\sum_{x \in X_j} x = \frac{3}{n}\sum_{i=1}^n x_i$ and hence that the $3$ partition instance is a "yes" instance.


Randomized linear search -- Why does reducing the sample size make the running time constant?

You made a simple algebraic error.  You said $\Pr[Y=i] = 1/n$, then you wrote

$$E[Y] = \sum_{i=1}^n i \Pr[Y=i] = \sum_{i=1}^n {1 \over n},$$

but that is incorrect: you omitted the $i$ in the second sum, i.e., you didn't plug in the value of $\Pr[Y=i]$ correctly.  Assuming that both indexing into the list and removing an item from the list can be done in one time step, the correct derivation is

$$E[Y] = \sum_{i=1}^n i \Pr[Y=i] = \sum_{i=1}^n i \cdot {1 \over n} = n(n+1)/2 \cdot {1 \over n} = (n+1)/2 = \Theta(n).$$