Basic queries for Object Detection using deep learning

The input to your CNN is a small cropped image, and the output will be a prediction at the label (either "airplane" or "not-airplane").  The training set needs to contain example input-output pairs.  So, you need your training set to contain many small images (of the size of a single crop), with a label indicating whether it should be classified as "airplane" or "not-airplane".

How do you do that?  You take many large images where you know where the bounding box of the airplanes in each is.  For each large image, you crop it around an airplane and add that to the training set, labelled as "airplane".  You also crop it somewhere else (in a place not intersecting any of the airplane bounding boxes) and that to the training set, labelled as "not-airplane".  You can do the letter step many times, taking many different crops.  Repeat this for many large images.  Use the resulting training set to train your neural network.


Algorithmic intuition for logarithmic complexity

The $\Theta(\log n)$ complexity is usually connected with subdivision. When using lists as an example, imagine a list whose elements are sorted. You can search in this list in $\mathcal{O}(\log n)$ time - you do not actually need to look at each element because of the sorted nature of the list.

If you look at the element in the middle of the list and compare it to the element you search for, you can immediately say whether it lies in the left or right half of the array. Then you can just take this one half and repeat the procedure until you find it or reach a list with 1 item which you trivially compare.

You can see that the list effectively halves each step. That means if you get a list of length $32$, the maximum steps you need to reach one-item list is $5$. If you have a list of $128 = 2^7$ items, you need only $7$ steps, for a list of $1024 = 2^{10}$ you need only $10$ steps etc.

As you can see, the exponent $n$ in $2^n$ always shows the number of steps necessary. Logarithm is used to "extract" exactly this exponent number, for example $\log_2 2^{10} = 10$. It also generalizes to list lengths that are not powers of two long.


If I can efficiently uniformly sample both $A$ and $B\subset A$, can I efficiently uniformly sample $A-B$?

Theorem: For any given $A$, either there are good algorithms to sample every subset of $A$, or what you're describing is impossible.
Proof (perhaps slightly informal): Suppose there are some "problematic" subsets of $A$ (those which cannot be efficiently sampled). Let $C$ be one of those subsets. From the fact that $C$ is problematic, it follows that $|C| \ll |A|$ (otherwise $C$ could be dealt with by rejection-sampling). Now let $B = A \setminus C$. Clearly, rejection-sampling does work on $B$, because $B$ is almost the entirety of $A$. So now we have algorithms for both $A$ and $B$, but no algorithm for $C$. Q.E.D.
Here's a ridiculous example: $A = \{(x_1, x_2, x_3, x_4) \mid x_i \in \mathbb{Z},\; 2 < x_i < 10^{10^{10^{1000}}}\}$ and $B$ contains only those quadruplets of numbers which are not counterexamples to Fermat's Last Theorem (i.e. such that $x_1^{x_4} + x_2^{x_4} \neq x_3^{x_4}$). It's trivially easy to sample $B$, but that gives us no clue whatsoever about how to do $A \setminus B$.


We do not know for certain that independent set cannot be solved exactly in polynomial time. However, it is considered unlikely, and this is the famous P$\neq$NP conjecture.

In cases where exact optimal solutions cannot (probably) be found in polynomial time, it is natural to look for approximately optimal solutions. Algorithms tackling this are known as approximation algorithms. If an algorithm always returns a solution whose value is within $\rho$ of the optimum, then we call it a $\rho$-approximation algorithm, and say that its approximation ratio is $\rho$.

A good example is MAX-3SAT, in which we are given a 3CNF formula, and our goal is to find an assignment maximizing the number of satisfied clauses. The corresponding decision version is a generalization of 3SAT, and so it is NP-complete. However, if we choose an assignment at random, it satisfies $7/8$th of the clauses in expectation, and we can in fact deterministically find such an assignment. Since the optimal solution satisfies at most a $1$-fraction of the clauses, this algorithm has an approximation ratio of $7/8$. It is a consequence of the PCP theorem that it is NP-hard to do any better (this is a result of Håstad). We say that MAX-3SAT is NP-hard to approximate within $7/8+\epsilon$ for any $\epsilon > 0$.

The independent set problem is much harder than MAX-3SAT. Indeed, it is NP-hard to approximate within $n^{1-\epsilon}$ for any $\epsilon > 0$. The best approximation algorithm known has approximation ratio $O(n(\log\log n)^2/\log^3 n)$ (as per Wikipedia).

In practice, independent set can probably be approximated better, but this is different to formalize, since it is not clear what properties real-world graphs satisfy. For random $G(n,1/2)$ graphs (in which each edge is chosen with probability $1/2$ independently), there is a $1/2$-approximation algorithm (the approximation ratio is with high probability over the choice of the graph).

Sometimes one considers smooth analysis of algorithms to model real-world instances. The idea is that real-world instances are noisy, and so instead of being interested in a specific graph $G$, we should be looking at a "neighborhood" of $G$ formed from graphs close to $G$ (differing by a relatively small number of edges). It could be the case that some algorithm has good approximation ratio on most of the graphs in the neighborhood of any graph $G$. I am not aware of any such analysis for independent set.


Regular expression for strings not starting with 10

If a word doesn't start with $10$, then either it starts with some other combination of two letters, or it is shorter than two letters. All in all, we get the following regular expression for your language:
$$
\epsilon + 0 + 1 + (00+01+11)(0+1)^*.
$$


Strassen, in his paper describing Strassen's algorithm (Gaussian elimination is not optimal) mentions

  the result of Klyuyev and Kokovkin-Shcherbak [1] that Gaussian elimination for solving a system of linear equations is optimal if one restricts oneself to operations upon rows and columns as a whole.

The reference is to

  Klyuyev, V. V., and N. I. Kokovkin-Shcherbak: On the minimizations of the number of arithmetic operations for the solution of linear algebraic systems of equations. Translation by G. I. Tee: Technical Report CS 24, June 14, 1965, Computer Science Dept., Stanford University.

The paper is available online.

In modern literature this result is virtually unknown, and I am not aware of any other lower bound on matrix multiplication beyond the $\Omega(n^2)$ lower bounds of Bshouty and Shpilka and the $\Omega(n^2\log n)$ lower bound of Raz.


Relaxed graph coloring, with penalties for assigning adjacent vertices the same color

Yes. Reduce from graph coloring.

$D$ is given by $d_{i,j} = \begin{cases} 0 & \text{ if } i=j \\ 1 & \text{ if } i \text{ is adjacent to } j \\ 2 & \text{ else}\end{cases}$.


3-coloring a graph with propositional formulas

Hint: Try to formalize the following:

Every node has at least one color.
Every node has at most one color. (This is actually not necessary.)
Any two adjacent nodes cannot have the same color.

Another hint:

   The first can be formalized as $R_i \lor B_i \lor Y_i$ for all $i$.


Neural Networks: Simulate the working of Dynamic Fixed Point representation of the weights on hardware

Start by reading the research literature on this topic.  There's a large number of published papers that discuss how to quantize the weights or intermediate values used in deep learning.  For instance, here are a few papers:

https://arxiv.org/abs/1412.7024, https://arxiv.org/abs/1605.06402, https://arxiv.org/abs/1612.01064, https://arxiv.org/abs/1701.08978

Start by reading them, and do a literature search to identify other relevant papers (e.g., read their related work section and find other earlier papers that are relevant; find papers that cite them using Google Scholar and read them; repeat).

You might also look at the Ristretto tool and this project.


An Answer

I will take your code at face value under the Uniform Cost Model.

Let's now assume $n$ is of the form $n = 2^k$ where $k \in \mathbb{N} \wedge k \geq 0$ (e.g. $n$ is a power of $2$).

We then get a recurrence relation like so:

$$\begin{align}
T(x, n) & = 2 \cdot T\left(x,  \frac{n}{2} \right) + c \\[0.5em]
& = 4 \cdot  T\left(x,  \frac{n}{4} \right) + 2c + c \\
& = \vdots \\[0.5em]
& = \sum_{i = 1}^{\log_2 n} 2^{i - 1} \cdot c\\[0.5em]
& = c(n - 1)\\
& = \Theta(n)
  \end{align}$$

Some Fun

Now let's take a step back and check out the Logarithmic Cost Model. Let's define the cost of multiplication as $g(n)$ where $n = \log_2 x$ (the size of $x$ in binary) and $x$ maximum of the two arguments.

Along with our prior assumption about $n$, let's also assume $x$ is of the form $x = 2^k$ where $k \in \mathbb{N} \wedge k \geq 0$ (e.g. $x$ is a power of $2$).

We get a recurrence of the form:

$$\begin{align}
T(n) & = 2 \cdot T\left(\frac{n}{2} \right) + g\left(\frac{n}{2}\right) \\[0.5em]
& = 4 \cdot  T\left(\frac{n}{4} \right) + 2 \cdot g\left(\frac{n}{4}\right) + g\left(\frac{n}{2}\right) \\
& = \vdots \\[0.5em]
& = \sum_{i = 1}^{\log_2 n} 2^{i - 1} \cdot g\left(\frac{n}{2^i}\right)\\[0.5em]
\end{align}$$

Now we can analyze some interesting multiplication methods:

Multiplication is linear in size, e.g. $g(n) = n$.

$$
\begin{align}
T(n) & = \Theta(n \log n)
\end{align}$$

Multiplication is quadratic in size, e.g. $g(n) = n^2$.

$$\begin{align}
T(n) & = \Theta(n^2)
\end{align}$$

Karatsuba Multiplication, the divide and conquer method, e.g. $g(n) = \Theta(n^{\log_2 3})$

$$\begin{align}
T(n) & = \Theta(n^{\log_2 3})
\end{align}$$

Just for fun, and to plug Yuval's answer to my own question, multiplication is super-linear-polylogarithmic and sub-polynomial-polylogarithmic, e.g. $g(n) = \Theta(n\log n \cdot 2^{\sqrt{2\log n}})$. We also assume size $n$ for $g$ instead of $\frac{n}{2}$.

$$\begin{align}
T(n) & = 2 \cdot T\left(\frac{n}{2} \right) + \Theta\left(n\log n \cdot 2^{\sqrt{2\log n}}\right) \\[0.5em]
\end{align}$$

We use case 3 of the Master Theorem to get:

$$\begin{align}
T(n) & = \Theta\left(n\log n \cdot 2^{\sqrt{2\log n}}\right) \\[0.5em]
\end{align}$$

Essentially, but not exactly, as the time complexity becomes superlinear, the time it takes to multiply overtakes the recursive time. This can be seen as case 3 of the Master Theorem.

Even More Fun!

Now let's say this was implemented in a smart manner, not repeating the recursive calls or using DP.

We get a recurrence of the form:

$$\begin{align}
T(n) & = T\left(\frac{n}{2} \right) + g\left(\frac{n}{2}\right) \\[0.5em]
& = T\left(\frac{n}{4} \right) + g\left(\frac{n}{4}\right) + g\left(\frac{n}{2}\right) \\
& = \vdots \\[0.5em]
& = \sum_{i = 1}^{\log_2 n} g\left(\frac{n}{2^i}\right)\\[0.5em]
\end{align}$$

The major improvement now is when multiplication is linear in size, we now get linear exponentiation!

$$
\begin{align}
T(n) & = \Theta(n)
\end{align}$$


A task-scheduling problem as a matroid (CLRS book)

I believe you are completely correct but mixed up two things from the book, namely the order in which the tasks are selected and the order in which the tasks are scheduled.
The greedy algorithm here indeed orders the task by their weights $w_i$ (as for every max-weight greedy algorithm on matroids). Given a set $A$ of tasks that are independent, i.e. they can somehow be scheduled so that no task is late, one way to schedule those tasks, such that none of them is late is by ordering those tasks (and only those, you omit the the tasks that are not in $A$) in increasing order of their due dates $d_j$.
Regarding your example with 99/100 tasks early: The one with the biggest weight (or penalty) is definitely one of the 99 tasks, as it is the first one to be selected by the greedy algorithm (unless its due date is non-positive). However, this task does not need to be the one that appears in the schedule first.
In essence, the order in which the greedy algorithm selects the tasks is not related to the order in which the tasks are scheduled.
Towards your second question: Whether a task is early only depends on its due date. The corresponding independence check for the matroid would work as follows:

The empty set is independent (no task is late).
Given set $A$ and task $a \notin A$, order all tasks in $A+a = [a_1, \ldots, a_m]$ by $d_j$ (such that $d_1 \leq \ldots \leq d_m$) and check for all $a_j \in A+a$ whether $j \leq d_j$ (as you have unit processing times).

The reason why this works, is subject of Lemma 16.12 (in the 3rd edition at least. the equivalence of three statements).


NFA to recognize bit strings containing 01111110

Might as well go for a DFA directly.

First, recognize the string 01111110. If you see something you don't expect, then the information is malformed and you should enter a dead state.

Once you've seen 01111110, start looking for 01111110 again, but this time, if you see something you don't expect, begin looking for 01111110 again from scratch. Once you see a complete 01111110, you have consumed an entire frame, and you should be in an accepting state.

Then, from this halting state, we add the same transitions we have on our initial state; i.e., we leave open the possibility that there are additional frames. Here's a transition table corresponding roughly to what I've indicated:

  State     Input     New State
  q0        0         q1
  q0        1         dead
  q1        0         dead
  q1        1         q2
  q2        0         dead
  q2        1         q3
  q3        0         dead
  q3        1         q4
  q4        0         dead
  q4        1         q5
  q5        0         dead
  q5        1         q6
  q6        0         dead
  q6        1         q7
  q7        0         q8
  q7        1         dead
  // we've seen the leading 01111110
  q8        0         q9
  q8        1         q8
  q9        0         q9
  q9        1         q10
  q10       0         q9
  q10       1         q11
  q11       0         q9
  q11       1         q12
  q12       0         q9
  q12       1         q13
  q13       0         q9
  q13       1         q14
  q14       0         q9
  q14       1         q15
  q15       0         q16
  q15       1         q8
  // we have now seen the trailing 01111110, a whole frame
  // q16 is the only accepting state.
  q16       0         q2
  q16       1         dead

Naturally, you'll want to check that very carefully. If the goal is outputting the message in between the leading and trailing patterns, you might need some extra states to remember input symbols that may or may not be part of the trailing pattern; but for accepting input which consists of a finite number of valid frames, this (or something close to it, if I've made a silly blunder) should be enough.


For Loop Range with Smaller Number on Right

It is acceptable.

The loop says “do something for each integer $k$ in some range”. If there is no integer in that range, the loop just won’t do anything.


1.) Every context free language is decidable. CFL are not unrecognizable. Refer 1

2.) P is countably infinite because P is the class of decision problem that can be solved on a deterministic turing machine in polynomial time. Every turing machine can be thought of as a finite string over some finite alphabets but all possible set of turing machines are countable infinite hence P is also countably infinite.

3.) NP complete languages are recognizable. A NP Complete languages can be found by modifying the halting problem which is just another form of halting problem(NP-Complete). Halting problems are undecidable but recognizable hence all NP-Complete problems are recognizable. Refer 2 fro details.


Pumping lemma is not a sufficient condition for being regular, it is only a necessarily condition. Satisfying it does not imply that the language is regular.
In the pumping lemma, some parameters are chosen adversarily, i.e. you don't have control over them. If a language is regular then pumping lemma says that "for a long enough string in the language there is a partition s.t. ...". To show that a language is not regular you should show that for all ways of partitioning the conditions will not hold. Your argument does rule out $y=11$ for example, you are only talking about a particular way of partitioning and that does not imply anything.
The language is indeed regular, it is (11)*.


Can an NP-hard problem be polynomial on average?

It would seem that the question has been answered at CSTheory.SE.

Summary: it is, indeed possible.

For example, the Max 2-CSP problem is NP hard with an $O(n)$ expected time algorithm.

This makes sense, I guess. Sometimes only a small subset of instances is needed to make a problem $NP$-hard, like SAT vs 3SAT. But you can expand the problem, and as long as it still contains the hard instances, it will be NP-hard, but the probability of success with a fast algorithm will be raised.


Lower Bounds for the Set Disjointness Problem

That's simply a different problem.  The set disjointness problem is defined, by common agreement, to be the problem where the universe has size $n$ and the inputs (sets) are represented as a bitvector of length $n$.  In other words, when you hear the phrase "set disjointness problem", you can know that's what they're referring to, and not the problem you care about.

It's fair to ask about the communication complexity of your problem.  I don't know what its communication complexity is.  There is no reason to assume your problem will necessarily have the same complexity as the set disjointness problem.

(There's a natural randomized protocol for your problem: if Alice and Bob each have a set of $n$ 64-bit integers randomly pick a universal hash function $f$ from the space of 64-bit integers to the set $\{1,2,\dots,2n\}$, transmit a description of $f$, hash the elements, and check disjointness of the hashed elements.  If there is a common element among the hashes, use binary search to find all common elements and check if the unhashed elements match as well.  The expected communication cost is $\Theta(n)$.  It's also clear that any algorithm must have communication complexity $\Omega(n)$.  This still leaves open what is the communication complexity for deterministic protocols, or the worst-case communication complexity for randomized protocols.)


What does this context-free grammar generate?

You conjecture that your grammar generates the language $L$ of words having as many $a$s as $b$s. In order to prove your conjecture, you should do two things:

Prove that every word generated by the grammar belongs to $L$.
Prove that every word in $L$ can be generated by the grammar.

In this case, the first part is easy to prove by structural induction. The second part is more difficult, so here is a hint. Given any non-empty $w \in L$, show that it can be decomposed as either $w = xayb$ or $w = xbya$ for some $x,y \in L$. Given this lemma, you can use induction on $|w|$.

Here is a hint for the lemma. Let $d_k(w) = |\{i \in [k] : w_i = a\}| - |\{i \in [k] : w_i = b\}|$, and let $d(w) = d_0(w),d_1(w),\ldots,d_{|w|}(w)$. For example, $d(aabb) = 0,1,2,1,0$ and $d(baba) = 0,-1,0,-1,0$. A prefix $w_1\ldots w_k \in L$ corresponds to a position $k$ such that $d_k(w) = 0$.


Integer solution that approximates a desired stock split

Let $d_i$ be the desired dollar amount that you'd ideally like to have invested in the $i$th stock (i.e., $d_1,\dots,d_n$ represent the ideal/model portfolio, without taking the requirement to avoid fractional shares).  Let $p_i$ denote the price of a single share of the $i$th stock.

Then you want to find a solution to the following optimization problem

$$\begin{align*}
\text{minimize } &(p_1 x_1 - d_1)^2 + \dots + (p_{20} x_{20} - d_{20})^2\\
\text{subject to } &p_1 x_1 + \dots + p_{20} x_{20} = 10,000\\
                   &x_1 \ge 0, \dots, x_{20} \ge 0
\end{align*}$$

where you require that the variables $x_1,\dots,x_{20}$ be integers.  Here the $p_i$'s and $d_i$'s are given (they are known constants), and you've solving for the $x_i$'s.

This is an instance of quadratic integer programming: i.e., integer programming with linear constraints and a quadratic objective function.  That in turn is a special case of mixed-integer quadratic programming (MIQP).  In general MIQP allows the problem to contain some integer variables and some continuous variables; your particular instance has only integer variables, so it's a special case of MIQP.  You can find off-the-shelf MIQP solvers out there.  I would recommend that you try applying one to your problem.  Given the problem size you describe, I would expect them to be effective and efficient at your problem.

If you wanted to measure the deviation from the ideal model by the $L_1$ distance (sum of absolute values of differences) instead of the $L_2$ distance (sum of squared differences), that could be expressed as an instance of integer linear programming (ILP), for which solvers are even more effective.


I couldn't find the source, but the idea is simple: Use additional bloom filter to represent the set of the deletions.

As this is a very simple solution, it might be considered as a folklore.

Anyway, I found a short reference to this solution in the following paper (Theory and Practice of Bloom Filters for Distributed Systems):

http://www.dca.fee.unicamp.br/~chesteve/pubs/bloom-filter-ieee-survey-preprint.pdf

Search for:

  Removal of an element can be implemented by using a second Bloom ﬁlter that contains elements that have been removed

In the third section of this paper, you can read about many techniques to deal with deletion. Maybe you will find there some reference (again - I'm not sure there is some paper about it, as it is a simple idea).


Given a constant k, find the biggest possible rooted tree, if for every path from root to leaf, the sum of the arity of its nodes equals k?

Let $B(n)$ be the size of the largest tree, where the arities of each path from root to leaf add up to $n$.

If the root of such a tree has arity $k$, then the paths for each of the $k$ subtrees must add up to $n-k$. As the subtrees must be optimal, the tree has size $1+k\cdot B(n-k)$.

A formula for $B(n)$ just maximizes that expression over $k$, using the previous values $B(n-1), B(n-2),\dots$.

I tried to do this by hand, and found (with the help of @Sudix, thanks) $1,2,3,5,7,11,16,23,34,\dots$. This seems to be A239288 in Sloanes Online Encyclopedia of Integer Sequences. The recursion given there is similar, but not exactly the same.

The explanation of the sequence there is: "Maximal sum of x0 + x0*x1 + ... + x0*x1*...*xk over all compositions x0 + ... + xk = n". That indeed is the same sequence: if the sequence of arities along the path from the root is x0, x1,..., xk these should sum to n, and the number of nodes indeed is the given formula.

Another remark at Sloane is interesting: "For n >= 8 the solution becomes cyclic: a(3n + k) = 3 + 3a(3n - 3 + k)". This seems to suggest that for values larger than 24 the root of the tree always has three children.


Shameless Advertisement: Game Theory proposal
  on Area 51 that you should totally follow!

No. The easiest way to prove this is by counterexample. Expanding matching pennies, we can create a game with two mixed strategies (players either mix between A and B or between C and D):

What might be true about that statement is for a mix of particular pure strategies for two players, there is a unique mixed strategy equilibrium. This presumes that there is a threshold  after which you switch from using strategy $0$ to strategy $1$. At this threshold, your opponent is ambivalent between her strategies. As depicted below, the intersection (and hence mix) will be unique.


Why is 2^32 in a 32-bit system = 4GiB and not 4Gib?

"32-bit" describes the size of many of the units of data that the processor can use. In this context, it refers to the size of memory addresses. A 32-bit address can address $2^{32}$ distinct objects; in a byte addressable system, that means it can address $2^{32}$ distinct bytes.

We don't give addresses to individual bits in memory, but rather groups of bits. In a byte addressable system those are bytes (ie, octets of 8 bits); you can also have a word-addressable system where you can only address groups of, say, 32 bits. In a system with 32-bit addresses addressing 32-bit words, you'd be able to use $32 * 2^{32}$ bits, or 17GB! But nowadays most consumer hardware in phones/computers are byte addressable.

Concretely, in byte-addressable memory, the first 8 bits are referred to as byte 0, the next 8 bits are referred to as byte 1, and the last 8 bits are referred to as byte 4294967295. There is no pointer to individual bit 26; you instead need to read/write the entire byte that contains it (byte with address 3 contains the 27th bit)


Let's start with the general case.
Given a production of a grammar, let's say A -> α where α is a general string, to compute the LL(1) parsing table T the algorithm says:

foreach(A -> α in the grammar):
  write A -> α in T[A,b], ∀  b ∈ first(α);
  if ( ℇ ∈ first(α) ):
     write A -> α in T[A,x], ∀ x ∈ follow(A);

If at the end of the algorithm you have any cell in the table T with more than one entry then the grammar is not LL(1), as in your case.
To run this algorithm you need to compute the set of firsts and follow of a symbol. I see you did right the follows sets, but you mistake in the firsts set of E. So here is the algorithm to compute the firsts set of a symbol X:

if(X is a terminal symbol):
  first(X) = X;
  break;
if (X -> ℇ ∈ productions of the grammar):
  first(X).add({ ℇ });
foreach(X -> Y1....Yn ∈ productions of the grammar):
  j = 1;
  while (j <= n):
    first(X).add({ b }), ∀ b ∈ first(Yj) ;
    if ( ℇ ∈ first(Yj)):
       j ++;
    else:
       break;
if(j = n+1):
  first(X).add({ ℇ });

So going back to your example:

First(E) = {a,y,z,c,x}

and in the table:

T[E,$] = E -> ABC


There is at most one edge cover which touches each vertex an odd number of times. To see this, let us consider a more general problem, in which each vertex is labeled either "odd" or "even". We want to cover each vertex by an odd or even number of edges, according to its label.

If the tree contains more than one vertex, then we can always find some leaf. It it is labeled "odd", every solution must contain the unique edge containing it. We add this edge to the edge cover, remove the leaf, and modify the label at the other end of the edge accordingly. If the leaf is labeled "even", every solution must not contain the unique edge containing it, and so we simply remove the vertex. Eventually only one vertex will remain. There is a solution if and only if this vertex is labeled "even".


center selection problem: Simple greedy algorithm

Given a set of points, the task is to find a set of centers minimizing the covering radius, defined below. The centers themselves could be arbitrary points in space, or sometimes must be selected among the points or among a set of potential centers.

The covering radius is the minimum $r$ such that each point in the set is at distance at most $r$ from a center. Clearly, adding centers can only reduce the radius, and in general it does. As a very extreme examples, given $n$ distinct points, for any $n-1$ centers that we choose, the covering radius will be positive, while if we take all the points as centers, the covering radius drops to zero.

As another example, consider three points on the real line at locations $-1,0,1$. The best choice for a single center is $0$, with covering radius $1$. The best choice for two centers is $-1/2,1/2$, with covering radius $1/2$. However, if we first put a center at $0$, no choice for the second center will reduce the covering radius.


Why are computable numbers (in Turing's sense) enumerable?

I'm assuming that your definition of a computable number is this: there is a Turing machine that on input $n$, halts with the $n$th bit of the number.

Suppose there were a recursive enumeration of Turing machines that produce computable numbers. You can use diagonalization to come up with a new computable number which isn't part of this recursive enumeration.

It is tempting to enumerate computable numbers by enumerating Turing machines, but not every Turing machine corresponds to a computable number, and in general deciding whether a Turing machine halts for all inputs (let alone output either 0 or 1) is not computable. It is, however, possible to enumerate all efficient computable numbers, say ones whose running time is polynomial, by using clocked Turing machines.


Are 'zero-one' jigsaw puzzles NP-complete?

Since you mentioned you are interested in solving this problem for small values of $n$, I would suggest that you try implementing this in a SAT solver or as an integer linear program (ILP).  Either one will be able to encode the constraints, but in a slightly different way:

For SAT, there is a very clean encoding of the choice of which tile goes into each square, and a slightly less clean encoding of the constraint regarding the number of each kind of tile (using bit arithmetic).
For ILP, there is a very clean encoding of the constraint regarding the number of each kind of tile available, and a slightly less clean encoding of the constraints on which tiles can be adjacent to each other (but it is still expressible, since you can express arbitrary boolean formulas in ILP).

I would expect that for small or medium sized $n$, this approach might work efficiently.


Return course order with class prerequisites

As pointed out in a comment, the problem you are trying to solve is an instance of the more general problem of finding a topological sorting of a particular set.
In your case, the ordering is given by the "being a prerequisite of" relation.
At the implementational level, switching your dictionary with an adjacency matrix may improve the runtime.


If you have no formal degree in CS, I think what you need is textbook instead of scientific papers.

Being a self-taught programmer is a great achievement and I think you can build up on that with theory. But, reading papers require some deep knowledge in some area.

I would suggest you to buy one of these books:

Algorithms by Robert Sedgewick and Kevin Wayne

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

Data Structures and Algorithm Analysis in C++, 4th Edition
Mark A. Weiss

In these books, you can also find some references to suggested readings.


What is the worst case for C++ "sort" function?

The worst case for the Quicksort algorithm depends how a pivot is chosen and it can range from $\Theta(n \log n)$ (if you choose the pivot to be the median) to $\Theta(n^2)$ (if the pivot is always a constant number of elements away from the minimum/maximum element).

That said, C++ standards do not mandate any particular implementation of the sort() function. So it is just a "coincidence" that your implementation happens to use Quicksort.

The answer to your question about the worst case depends on which C++ standard you are referring to. Before C++11, sort() was required to take "approximately $O(n \log n)$ comparisons on the average" (whatever "approximately" means) but, since no particular implementation is mandated, you'd have to look at the sources of the standard library you are using.

If you are referring to C++11 or later, then sort() is required to perform $O(n \log n)$ comparisons in the worst case (see Section 25.4.1.1).
To be pedantic, you'd still need to inspect the implementation to know what the worst case is (I could imagine a conforming implementation that first checks whether the input array is any specific permutation (or class of permutations), and then sorts it in linear time).

To be even more pedantic: the standard mandates an asymptotic number of comparisons, so I'm not sure whether a sort() function with a running time of $O(2^n)$ (or some weird function of the input) would conform to the standard, as long as it only performs $O(n \log n)$ comparisons...


Domino tiling of a 2xN rectangle in O(ln n)

In your second attempt you tried to fixate the $(k+1)$th term. But instead of the two cases

1 2 ... k k+1 k+2 ... n
           |
           |

and

1 2 ... k k+1 k+2 ... n
           -----
           -----

there exist a third case:

1 2 ... k k+1 k+2 ... n
        ----
        ----

So if $n = 2 k$, then you have $f(k)f(k-1)$ for the first case, $f(k)f(k-2)$ for the second one, and $f(k-1)f(k-1)$ for the third one. This gives in total:

$f(2k) = f(k)f(k-1) + f(k)f(k-2) + f(k-1)f(k-1) = f(k)[f(k-1) + f(k-2)] + f(k-1)f(k-1) = f(k)^2 + f(k-1)^2$.

Now this formula looks like the formula for $F(2n+1)$ that you posted.

  Because the Fibonacci Numbers can be generated in O(lgn) using

  F(2n)=F(n)F(n+1)+F(n−1)F(n)

  F(2n+1)=F(n)F(n)+F(n−1)F(n−1)

Simple reason: the formula assumes that $F(1) = F(2) = 1$ while you have $f(0) = f(1) = 1$. So after an index shift it should match.

Identical procedure for the odd case $n = 2k + 1$.

edit: Tried to do the index shift but failed. Reason was, that you wrote down the wrong formula for $F(2n+1)$. It should be $F(2n+1)=F(n)^2+F(n+1)^2$. Then the index shift works:

$f(2k) = F(2k+1) = F(k)^2+F(k+1)^2 = f(k-1)^2 + f(k)^2$.


What is the complexity of multiplying a matrix by a scalar?

In general, if you have an $n\times m$ matrix $A=(a_{i,j})$ with $1\le i\le n$ and $1\le j\le m$ then there will be $nm$ entries in the array. To multiply $A$ by a scalar $c$ you multiply each element by c, which (assuming multiplication can be done in constant time) will take $nm$ multiplications. That's not the way to go, though, if $A$ is the adjacency matrix of a directed graph.

For your peoblem, if $A$ is the adjacency matrix of a digraph $G$ on $n$ vertices, then $A$ will be an $n\times n$ matrix $(a_{i, j})$ with $a_{i,j}=1$ when there is a directed edge $e=(i, j)$ from vertex $i$ to vertex $j$ and $a_{i,j}=0$ otherwise. You correctly note that the reversed graph $G'$ will have an adjacency matrix $B=(b_{i,j})$ which is the transpose of $A$, so we'll have $b_{i, j} = a_{j, i}$, since $G'$ will have an edge from vertex $v_i$ to vertex $v_j$ if and only if $G$ has an edge from $v_j$ to $v_i$. To get the transpose of $A$, then, we'll swap $a_{i, j}\leftrightarrow a_{j, i}$ entries of $A$. There will be $n(n-1)/2$ swaps needed, since we swap every element above the main diagonal with its corresponding entry below the main diagonal.

Note that multiplying $A$ by $-1$ won't work, since the entries of an adjacency matrix must be only $1$ or $0$.


Computational power of deterministic versus nondeterministic min-heap automata

It seems that for this model, non-deterministic machines are not equivalent to deterministic ones, for basically the same reason that deterministic PDAs are not equivalent to non-deterministic ones.

Consider the language
$$L =\\{ x\$y \mid |x|=|y| \wedge x\ne y\\}$$
(where $\$$ is a special sign not contained in $x$ and $y$).

I claim that a non-deterministic machine $N$-$HAL$ can decide this language: It performs the same as the PDA for $L$. The standard PDA solution uses the stack only to count offsets: it nondeterministically guesses an offset $i$, remembers the value of $x_i$ (adding a symbol to the stack at each step), then the PDA ignores the input until it find the $\$$, and then it pops symbols out of the stack until it is empty. At this stage we are exactly at $y_i$ and he PDA can check if $x_i \ne y_i$. (if anything goes wrong in the middle, the PDA "dies").
Since the stack alphabet is unary, it can be simulated with a min-heap machine.
Actually: any $L$ that is is accepted by a PDA with a unary alphabet can be accepted by a min-heap machine. (I'm ignoring, maybe, another special sign added to identify an empty stack, but an equivalent sign can be added to the heap)

For the other direction, I don't have the formal proof, but here are my thoughts:

I claim that a deterministic machine $D$-$HAL$ is incapable of deciding this language. Intuitively, the content of the heap can not be correlated with $x$ (otherwise, permute $x$. the content of the heap remains the same..). This suggests that only thing that matters is the number of elements in the heap, but then, if $D$-$HAL$ can decide $L$, so can a deterministic-$PDA$.

Edit: more details about the "permute $x$" claim. Assuming Raphael's conjecture
there exist $x_1$ and $x_2$ that after reading them, the content of the heap is the same.
Then consider the words $x_1\$x_1$ and $x_2\$x_1$. The content of the heap is the same when the HAL gets to the dollar sign, thus it must either accept both or reject both. contradiction.

anyone sees an immediate proof for the conjecture?


Let $a_{n,h}$ denote the number of AVL trees with $n$ nodes and height $h$. It is straightforward to get a recurrence for $a_{n,h}$:

$$a_{n,h} = \sum_{k=1}^n \bigl(a_{k-1,h-1}a_{n-k,h-1} + a_{k-1,h-1}a_{n-k,h-2} + a_{k-1,h-2}a_{n-k,h-1}\bigr),~ n\geq h > 1,$$

with the initial conditions $a_{n,h} = 0$, if $h>n$ or $h\in\{0,1\}, n\neq h$, and $a_{0,0} = a_{1,1} = 1$.

The numbers you are looking for then are $a_n = \sum_h a_{n,h}$.

Unfortunately there apparently is no known closed form for this sequence. The OEIS has a list of the first 1000 terms and maple + mathematica code to compute further ones (via the recursion).


What does $O(\alpha(n))$ amortized time mean?

$\alpha$ indicates the Inverse Ackermann Function: $\alpha(n)$ is the number such that $A(\alpha(n), \alpha(n)) = n$.

In practice, $\alpha(n) \lt 5$ for any input less than about $^72$. So $O(\alpha(n))$ is basically $O(1)$. The difference only matters in theory, never really in practice. You'll find $O(\alpha(n))$ mostly when working with disjoint sets, which are pretty much the fastest data structures you'll ever use.

EDIT: $^nb$ indicates "tetration", that is, iterated exponents. It grows ridiculously quickly: $O(^n2)$ is worse than $O(n!)$.


Here are several examples:

MAX-CLIQUE: The witness is a set of vertices of given size. The verifier checks that edges connect all pairs of vertices in the set.
SAT: The witness is a satisfying assignment. The verifier checks that it satisfies all clauses in the formula.
3COL: The witness is a 3-coloring of the graph. The verifier checks that all edges connect vertices of different color.
SUBSET-SUM: The witness is a subset of the set. The verifier checks that the subset sums to the target number.


Iteratively find and modify a certain element in a set in $\log n$ per iteration

Yes, you can achieve that running time if you use the right data structure.  You might want to look at some other data structures, such as AVL trees, red-black trees, or other similar techniques.  See, e.g., https://en.wikipedia.org/wiki/Search_data_structure, https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree,  or your favorite data structures book.


A O(n) algorithm for a point set triangulation

You can find one triangulation similar to finding the convex hull. On your conditions finding the convex hull can be solved in linear time.

In order to find the convex hull of a set of points in $R^2$ let's do two sweep lines, one from left to right to compute the upper-hull and another from right to left to find the lower-hull. In order to illustrate the algorithm better I will use pseudo from here.

I'll augment it to solve the triangulation problem. My comments start with #

Input: a list P of points in the plane.

Precondition: There must be at least 3 points.

# We can skip this since points are already sorted
Sort the points of P by x-coordinate (in case of a tie, sort by y-coordinate).

# Initialize T as empty list to store triangulation
Initialize U and L as empty lists.
The lists will hold the vertices of upper and lower hulls respectively.

for i = 1, 2, ..., n:
    while L contains at least two points and the sequence of last two points
            of L and the point P[i] does not make a counter-clockwise turn:
        # Add last two points from L and P[i] to T (the triangulation)
        remove the last point from L
    append P[i] to L

for i = n, n-1, ..., 1:
    while U contains at least two points and the sequence of last two points
            of U and the point P[i] does not make a counter-clockwise turn:
        # Add last two points from L and P[i] to T (the triangulation)
        remove the last point from U
    append P[i] to U

Remove the last point of each list (it's the same as the first point of the other list).
Concatenate L and U to obtain the convex hull of P.
Points in the result will be listed in counter-clockwise order.
# Triple of points in T will be the triangles


You forgot to mention that $x$ is in fact $64$ bits long. Write $x$ in binary notation:
$$ x_{63} x_{62} \ldots x_1 x_0. $$
We have
$$
\begin{align*}
op_0 &= x_{63} \cdots x_{56} \\
op_1 &= x_{55} \cdots x_{48} \\
op_2 &= x_{19} \cdots x_{16} \\
op_3 &= x_{23} \cdots x_{20} \\
op_4 &= x_{27} \cdots x_{24} \\
op_5 &= x_{31} \cdots x_{28} \\
op_6 &= x_{35} \cdots x_{32} \\
op_7 &= x_{39} \cdots x_{36} \\
op_8 &= x_{43} \cdots x_{40} \\
op_9 &= x_{47} \cdots x_{44} \\
op_{10} &= x_{15} \cdots x_8
\end{align*}
$$
All these, in binary notation.

I'll let you take it from here.


Arrange in increasing order of asymptotic complexity

You have mistake in $(2.1)^n \cdot n^2<2^n \cdot n^3$, because it is equivalent $\left(\frac{2.1}{2}\right)^n<n$


How to build a finite automaton for right quotient of a regular language?

First of all, note that you are constructing an NFA, and so $\delta'$ should output a set of possible transitions.

You can prove by induction the following identities:
$$
\begin{align*}
\delta'((q,0),w) &= \{ (\delta(q,w),0), (\delta(q,wa),1)\}, \\
\delta'((q,1),w) &= \begin{cases} \{(q,1)\} & w = \epsilon, \\ \emptyset & w \neq \epsilon. \end{cases}
\end{align*}
$$
In particular, $\delta'((q_0,0),w)$ intersects $F \times \{1\}$ iff $\delta(q_0,wa) \in F$. In other words, $w$ is accepted by your NFA iff $wa \in L$, so your automaton is computing $L/a$.

You can simplify your construction by taking the original DFA and simply modifying the set of accepting states, replacing $F$ with
$$
F' = \{ q : \delta(q,a) \in F \}.
$$
The new automaton accepts a word $w$ iff $\delta(q_0,w) \in F'$ iff $\delta(q_0,wa) = \delta(\delta(q_0,w),a) \in F$ iff $wa \in L$.


Why does NTM need to derive certificate to prove "If a language is in in NP iff it is decidable by some nondeterministic polynomial time TM"?

By definition NP is the class of languages for which you can efficiently verify with a certificate that a string is in the language.

Informally; it is the class of problems that you can verify the solution to given a witness, but you cannot find one easily. If you could, then it would be in P.

A NTM can be seen as a unrealistic Turing machine which always guesses the right answer. Since the NTM is non-deterministic given an input x. We cannot be sure exactly what path he took to derive the solution, therefore a witness is needed.

For example;

Problem: Is 24 prime?

A NTM would guess the answer to be no and the certificate would be the number “4”.

A verifier presented with the certificate can divide 24 by 4 and also come to the conclusion that 24 is not prime.


This problem is strongly NP-complete; it is straightforward to reduce 3SAT to this problem.

The clause $C = (x_1 \lor \neg x_2 \lor x_3)$ can be encoded as the polynomial $p(x_1,x_2,x_3,\dots) = [(1-x_1)x_2(1-x_3)]^2$.  The conjunction of clauses $\varphi = C_1 \land \dots \land C_m$ can be encoded as $q(x_1,\dots,x_n) = p_1(x_1,\dots,x_n) \cdots p_m(x_1,\dots,x_n)$, where $p_i(x_1,\dots,x_n)$ is the encoding of clause $C_i$.  Then, the polynomial $q(x_1,\dots,x_n)$ has a solution in $\{0,1\}^n$ if and only if the original formula $\varphi$ is satisfiable.


You are getting into to much detail. You can think of a CPU as some kind of automaton which operates roughly as follows (ignoring pipelining). There is a register called (in x86) IP (Instruction Pointer). The CPU operates an infinite loop (ignoring interrupts):

Read the instruction $\iota$ at address IP; determine its length $\ell$, and increment IP by $\ell$.
Execute $\iota$; this might change IP.
Go back to 1.

This is implemented in some sophisticated way, but if you don't care about performance, it performs as if the CPU was actually running this infinite loop. Control instructions change IP and so control which instructions are executed.

Different programs are just collections of instructions. When you run a program, the operating system loads it into memory and then jumps to the first instruction (i.e., sets IP to the address of the first instruction). From there on, the program executes until it terminates and releases the token back to the operating system. (Modern operating systems, which are multitasking, are more complicated, but DOS ran much according to this description, ignoring interrupts.)


Union of regular languages that is not regular

There's a significant difference between the question as you pose it and the question posed in the exercise. The question asks for an example of a set of regular languages $L_{1}, L_{2}, \ldots$ such that their union
$$
L = \bigcup_{i=1}^{\infty}L_{i}
$$
is not regular. Note the range of the union: $1$ to $\infty$. Regular languages are closed under finite union, and the proofs runs along the lines that you sketch in the question, however this falls apart under infinite union. We can show this by taking $L_{i} = \{0^{i}1^{i}\}$ for each $i$ (with $\Sigma = \{0,1\}$). The infinite union of these languages of course gives the canonical non-regular (context-free) language $L = \{0^{i}1^{i}\mid i \in \mathbb{N}\}$.

As an aside, we can see easily where the normal proof fails. Imagine the the same construction where we add a new start state and $\varepsilon$-transitions to the old start states. If we do this with an infinite set of automata we have build an automata with an infinite number of states, obviously contradicting the definition of a finite automata.

Lastly, I'm guessing the confusion may arise from the phrasing of the original question, which starts "Donner deux exemples des suites de langages...", which is (roughly, my French is a bit rusty, but externally verified!) "Give two examples of sequences of languages...", rather than "Give two examples of languages...". An incautious reading may mistake the second for the first though.


Yes, running back and forth comparing letters is the best you can do. You could always read and remember two, three or any fixed amount of symbols at a time; then there would be less running back and forth, but the programming would be even worse.

And yes, in general you have to rewrite everything when you change something. There are no functions, procedures etc. that you can program in a modular way. In principle, though, you could use different, disjoint sets of states in different parts of your computation. If you change something in one part, you only need to adapt the "interface" where you move from one set of states to another.

If you do not find the right letter, in principle there is no problem with "crashing", because this probably means not accepting. If you want a "controlled" end, you can for example run to the right end of the input and stop there (stopping means entering a configuration where no more move is possible); if this kind of stopping for you is "crashing" you can also enter into an infinite loop.


Is packing a bag of presents easier for Rupert than Santa?

After quickly looking at this question, I believe Rupert's extra knowledge of each child's {behavior, max value present} will not always make Santa's job easier. Santa will still need to perform a 0/1 knapsack to fill the bags and a Hungarian algorithm as well to maximize the happiness each capitalist child receives on Christmas morning. A simple case where it would make Santa's job quite simple is if every child Santa was considering didn't publish a paper and instead played video games all year received a zero from Rupert (each child would get coal).


Distributed parallel computing algorithms for content dependent data

You have a static number of tasks to be executed, and each task is independent (i.e., no communication among tasks is required). However, the chunks assigned to different machines might take a different amount of time for encoding.

In this situation, the simplest and probably the best possible approach, consists in cyclically mapping tasks to processors, in order to balance the computational load. This is a form of probabilistic mapping (see sub-section on Probabilistic Methods and Cyclic Mappings, just before Section 2.5.2 on the linked web page). As an example, if you have $p$ processors and $n$ tasks (with $n > p$), you can simply assign task $i$ to processor $i \mod p$.


Haskell is right.

I do not know whether your Haskell syntax is correct, though it looks plausible to me, but the Haskell typing is the right one.

Since $f$ is applied to the result of $f(x)$, $f$ must be of type $a\rightarrow a$,
$a$ being the type of $x$.


I'll give some hints as plain text, do try to have a go at solving the questions with this help before revealing the spoilers.

The first part you should be able to answer very easily - check the definition of a linear grammar, how many non-terminals can be on the right-hand side of the production?

   At most one, so this isn't a linear grammar, let alone right-linear.

For the second part, perhaps one way to approach it is to first build an NFA that recognises the same language that the grammar generates, then you can use the transitions of the NFA to generate the transitions of the grammar.

   $S\rightarrow 1A$
 $A\rightarrow 0B$
 $B\rightarrow 1B \;|\; 0B \;|\; C$
 $C \rightarrow 1D$
 $D\rightarrow 0$
 This grammar is certainly not the only one, but should look something like an NFA for the same language - the non-terminals are states, and $D$ is the accept state.


How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem?

A grammar $G$ for a language $L$ is ambiguous if there is a string $w \in L$ which has two different parse trees (with respect to $G$). Hence in order to show that ambiguity is still present, all you have to do is to come up with a string generated by your grammar that has two different parse trees.


Using your definition for Church Numerals and trying to see what's going on:

$$ \begin{align} 0 &= \lambda f. \lambda x. x \\
                 1 &= \lambda f. \lambda x. f x\\
                 2 &= \lambda f. \lambda x. f f x\\
                 3 &= \lambda f. \lambda x. f f f x\\
&\vdots
\end{align} $$

Now let's say have a function $g$ and some $a$, try to use $g$ and $a$ as arguments to $0$, that is:

$$ \begin{align} 0 ~ g ~ a &= (\lambda fx. x)~g~a\\
\quad &\rhd_{1\beta} ([g/f] (\lambda x.x)) a = (\lambda x.x) a \\
\quad &\rhd_{1\beta} [a/x]x = a
\end{align} $$

So $g$ applied $0$ times to $a$ returns $a$.

Now try to do the same with $1$.

$$ \begin{align} 1 ~ g ~ a &= (\lambda fx. f~x)~g~a\\
\quad &\rhd_{1\beta} ([g/f] (\lambda x.f~x)) a = (\lambda x.g~x) a \\
\quad &\rhd_{1\beta} [a/x]g~x = g ~ a
\end{align} $$

So $g$ applied $1$ time to $a$ is indeed $g(a)$.

Your problem is $4 ~ g ~ a$, where $g$ is $S$ and $a$ is $Z$.

$$ \begin{align}
S &= \lambda r.\text{“ring the small bell (ding) and apply r”}\\
Z &= \lambda r .\text{“ring the big bell (dong)}”
\end{align}
$$

Doing $1 ~ S ~ Z$ we already know that evaluates to $S(Z)$. And that translates to "print 'Ding' then apply $r$ ", where $r$ just prints 'Dong'. So it outputs 'Ding Dong'.


Understanding the heuristic used for approximate string searching through an FSA

Those two statements are correlated: "giving priority to the highest word position" is the same as "the node that has advanced farthest in the word is given priority".

This appears to be why the algorithm selects state three. State zero does not result in an advancement in word position, whereas the transition to state three is further in the word position and so satisfies their heuristic of highest word position and thus gets priority for first expansion.

To see why this heuristic results in better results, examine the node zero. Deleting 'd' you see all the letters remaining are in the reachable nodes from zero, which means $h = 0$, and we only performed 1 operation, so $f = 1$. However in order to get to the acceptance state along the shortest path we have to take another operation to go to 3 while adding 'c' back, then we transition through the states 5, and 7 making no changes. Obviously the fastest (and shortest) path is to simply swap 'd' to 'c' and transition to state three first, which the heuristic suggests in this case.


What does it mean for a random number generator's sequence to be only 1-dimensionally equidistributed?

This website provides the answer:

  A xorshift* generator with an n-bit state space is $n/64$-dimensionally equidistributed: every $n/64$-tuple of consecutive 64-bit values appears exactly once in the output, except for the zero tuple (and this is the best possible for 64-bit values). A xorshift+ generator is however only $(n/64 − 1)$-dimensionally equidistributed: every $(n/64 − 1)$-tuple of consecutive 64-bit values appears exactly $2^{64}$ times in the output, except for a missing zero tuple.

In the case of a xorshift+ which uses 128 bits of state, n/64 - 1 = 128/64 - 1 = 2 - 1 = 1, so the Wikipedia article was correct in stating that that particular generator is only 1-dimensionally equidistributed.


Finding dimensions of a point cloud - floating point issues

One common way to do this is to apply a Principal Component Analysis (PCA) to your data. The operation essentially consists of rotating the data around the mean to align with the principal components. Most of the variance is moved to the first components. If you know the dimension of your manifold, then you can simply select the first $k$ components and reconstruct the lower dimensionality data. If you don't, there are simple criteria such as threhsolding the ratio of the variances. Of course more elaborate Bayesian methods also do exist, such as this one. I'll quickly give an overview of the simple method. Let $\mathbf{\lambda}=\{\lambda_1..\lambda_N\}$ denote the sorted eigenvalues (giving you the variances).  We could create a monotonically increasing CDF-like curve:

$$
f(i) = \frac{\sum\limits_{j=1}^i \lambda_j}{\sum\limits_{j=1}^N \lambda_j}
$$
where each element represents the variance explained up to that eigenvalue (or component). We could then pick a threshold $\tau$ (e.g. \tau=0.98). Then we throw out the components which remain above that (meaning low contributions)

$$
f(i)>\tau
$$

Similarly, one could also threshold the difference $g(i)=max(f(i)−f(i−1))$, as this will be the value where adding a dimension really makes sense. If $g(i)$ is small, there would be no real contribution to explain the variance.

This problem sounds like 'dimensionality estimation' or 'dimension discovery'. There are also other methods available. PCA is just the most easy-to-implement and famous one. If your structure is linear (such as a triangle as you mentioned) PCA should be suitable.


Nine-input sorting network of optimal depth with minimum number of comparators

I found a 2002 Reference of the Best-Known Sorting Networks for up to 16 Inputs by Ron Zeno including a diagram of a 9-input network that seems to fit the bill.

His nine-input sorting network of depth seven uses the following arrangement of comparators

{0, 7}, {1, 6}, {2, 5}, {3, 4},
{0, 3}, {1, 2}, {4, 7}, {6, 8},
{0, 1}, {2, 6}, {3, 4}, {5, 8},
{1, 2}, {3, 5}, {4, 6}, {7, 8},
{1, 3}, {2, 4}, {5, 7},
{0, 1}, {2, 3}, {4, 5}, {6, 7},
{3, 4}, {5, 6}

Wolfram demonstrations includes a beta about Sorting Networks, which in due course contains an example of an optimal (module count) nine-input network:

  {{1, 2}, {4, 5}, {7, 8}},
  {{2, 3}, {5, 6}, {8, 9}},
  {{1, 2}, {4, 5}, {7, 8}, {3, 6}},
  {{1, 4}, {2, 5}, {6, 9}},
  {{4, 7}, {5, 8}, {3, 6}},
  {{1, 4}, {2, 5}, {6, 8}, {3, 7}},
  {{2, 4}, {5, 7}},
  {{3, 5}, {6, 7}},
  {{3, 4}}

(That's probably about as close as I will get to providing a visualisation:
looks trivial to plug "the Flensburg" or above 7-level configurations.)


How do balancers work in the context of counting and balancing networks?

The book is correct, and the algorithm works as advertised. See if you can prove that it does. No explicit counting is necessary.

A very similar situation occurs for languages: $(ab)^*(a + \epsilon)$ is regular even though  $\{ w : 0 \leq \#_a(w) - \#_b(w) \leq 1 \}$ is not.


How do I find if a programming language is infinite or finite?

An infinite number of potential identifiers results in an infinite language, but this is a "boring" feature with this consequence, because you can do without. We know that two variables are sufficient to compute any Turing computable function, so this is not the crucial part; I'll assume we use only finitely many variables.

Even then, ignoring real-world constraints such as finite memory, programming languages are -- of course -- infinite languages. Consider the following class of programs:

def m(x) {
  x++
  x++
  ...
  x++
  return x
}

It is clear that you can have as many statements as you want (never mind that, depending on the semantics, it might be that only finitely many of them run without error).

Why do I say "of course"? Well, usually programming languages are supposed to be Turing complete (again, assuming infinite memory). There are infinitely many functions that are Turing computable -- consider only $f_i(x) = i$ for $i \in \mathbb{N}$ -- so we must have infinitely many programs.

It is even so that typical programming languages have infinitely many programs for any single (computable) function! Consider, for instance, $f_1$ and all implementations of the form

def f1(x) {
  x++
  x++
  ...
  x++
  return 1
}

If you think about it, you can do stuff like that -- inserting "meaningless" statements -- in any program written in any language.


How to convert two conflicting objective functions into a single objective function

To turn a maximisation problem into a minimisation one (or vice versa), simply multiply the value by -1.

Hence you want w1 * f1 - w2 * f2, for some appropriate choice of weights w1, w2 (which could indeed both be 1).

Unless there's some other requirement you haven't mentioned, there's no specific need for w1 and w2 to add up to 1: it depends on the relative importance of f1 and f2, which is problem-specific.


Max independent set in planar graphs PTAS proof

I haven't got any paper, but looking through my favorite book regarding approximation algorithms i've got something.

It is named: The Design of Approximation Algorithms.
You find it free for download (even legal) on https://www.designofapproxalgs.com.

Take a look at page 269 (ff.) especially page 271 should be interesting for you as they describe and proof a PTAS for max independent set in planar graphs.

It might not be "front of the line" research or results but hope it helps.


How similar are two DFAs? -not just binary equivalence-

This problem seems to ask for co-development of a reasonable distance function and an algorithm to compute it for a given pair of languages.

The paper "The Cost of Traveling between Languages" by Michael Benedikt, Gabriele Puppis, and Cristian Riveros defines one such notion, where we are searching for the largest value $d$ such that there exists a word $w$ in the language of the first automaton such that the edit distance of $w$ to any word in the second language is at least $|w| \cdot d$. The paper gives an algorithm to solve this problem, which involves distance automata.

The paper also has an interesting related work section, with a reference to the paper "Edit-distance of weighted automata: general definitions and algorithms" by Mohri, which seems to solve the same problem without the multiplication with the word length.

Both of these definitions are reasonable from a theoretical point of view - you now only have to evaluate whether they make sense for your particular application.

Both of the paper have author-archived versions available without pay-wall on the web which you should easily find with your favorite search engine.


How to choose the number of HOG pyramid layers?

That's a good question!

All of this will depend in your application and camera setup. Usually, it works like this: if you have a say 128x128 detector template you will be able to detect the object at this size and greater dimensions. When you go up at the pyramid the image size is smaller, but the detected object (w.r.t the original image) is bigger).

One of the main ways to reduce computational time is to reduce the number of pyramid levels. With all things kept unchanged, this will make you not detect very large objects. By the way, a common trick in object detection is to resize the image such that the object in the scene appear at the right scale w.r.t the pyramid.

If, you change the pyramid step, some object could be missed if their scale does not match any of the pyramid levels. In summary, as I said, it will depend on the setup (e.g. if you have a camera send people from a distance, usually you will need fewer leves of the pyramid).

I recently wrote a paper on using the camera calibration to estimate the best scales for people detection in a surveillance scenario. It could help you:

Fuhr, G.; Jung, C.R., "Camera Self-calibration Based on Non-Linear Optimization and Applications in Surveillance Systems," in Circuits and Systems for Video Technology, IEEE Transactions on , vol.PP, no.99, pp.1-1


Why doesn't this derivation of the margin in a SVM give the correct result?

The first line of your equation for $d$ is incorrect.  It should be

$$d = \left\|\vec w\frac{\vec x_+\cdot\vec w}{\vec w\cdot\vec w} - \vec w\frac{\vec x_-\cdot\vec w}{\vec w\cdot\vec w}\right\|.$$

(Why?  The distance between two points $u,v$ is $\|u-v\|$, not $\|u\|+\|v\|$.)

If you continue the derivation from there, you will obtain the result you were expecting.


How do we define if a Turing machine goes to the right or left?

It's not specified in the description you gave, but absent directions to the contrary, a TM is generally understood to start at the leftmost non-blank cell.


How to compare/cluster millions of strings?

The length of each string is at least 200, and you only consider two strings similar if their edit distance is less than 20.  So if $S,T$ are similar, then there must exist $U$ such that (1) $U$ is a substring of $S$, (2) $U$ is a substring of $T$, and (3) the length of $U$ is at least 10.

This suggests that one heuristic is to find all length-10 substrings and look for collisions.  In other words, build a hashmap whose keys are substrings and values are the containing strings; for each string $S$, compute all length-10 substrings $U$, and add a mapping from key $U$ to string $S$ into a hashmap.  This can be done in linear time; a rolling hash may improve efficiency.

Now iterate through the hashmap and find all pairs of strings $S,T$ that share a common length-10 substring.  For each pair $S,T$, compute the edit distance and check whether the edit distance is < 20.  I suggest using the optimized edit distance computation with "early out": if the edit distance is $\ge 20$ you don't care what its actual value is.  This computation can be done in $O(20 \cdot (n+m)) = O(n+m)$ time per pair, where $m,n$ are the lengths of $S,T$.  Length 10 is large enough that probably won't be too many pairs $S,T$ that contain a common length-10 substring but whose edit distance is $\ge 20$, so you probably won't waste too much time computing the edit distance on pairs you aren't interested in.

There are other approaches, based on metric trees, BK trees, and other methods.  See, e.g., Efficient map data structure supporting approximate lookup.  You might also look into the computational biology literature, which deals with a similar problem when clustering DNA sequences.  There the alphabet has 4 characters, rather than 5 characters, and strings can be much longer, but they also want to find similar pairs from a large database, and they have developed practical and efficient algorithms.


How to solve an optimization problem that deals with the optimal combination of given ratios?

If the number of children $n$ is fixed and there is no limit on the number of staff members you can potentially hire, here's one way you can maximize the amount the government pays you:

You can use linear programming (LP).  Let $s_1$ denote the number of staff you hire to manage one-child classrooms; $s_2$ the number of staff you hire to manage two-child classrooms; and $s_3$ the number of staff you hire to manage three-child classrooms.  The number of children you can handle, with this configuration of staff, is $s_1 + 2s_2 + 3s_3$.  Also, the amount paid by the government is $7.28 s_1 + 9.10 s_2 + 14.71 s_3$.  You want to maximize the payoff, subject to the constraints $s_1 \ge 0$, $s_2 \ge 0$, $s_3 \ge 0$ and to the constraint $s_1 + 2 s_2 + 3 s_3 \ge n$ (i.e., you have capacity to take care of $n$ children).

Of course, this formulation is silly, because under this formulation the way to maximize your profit is to maximize the number of staff chosen.  That's because this formulation doesn't take into account the cost of hiring staff or any other consideration.  So you'll need to adjust it to incorporate the additional constraints you have.

Fortunately, this LP formulation makes it easy to incorporate additional constraints.  For instance, suppose there are only 100 qualified people who you'd possible be willing to hire as staff, so you simply can't hire more than a total of 100 staff members.  That can be handled by adding the additional constraint $s_1 + s_2 + s_3 \le 100$.

In practice there's probably some cost per staff member you hire, so in practice we probably want to maximize not the amount the government pays us, but the amount of "profit" left over after paying the staff members.  Suppose each staff member costs 5 dollars per hour.  Then you would adjust the above by maximizing the revenue minus the costs, i.e., $(7.28 s_1 + 9.10 s_2 + 14.71 s_3) - (5.00 s_1 + 5.00 s_2 + 5.00 s_3)$.

In practice you want to only hire an integer number of staff, so you might want to use an integer linear programming (ILP) solver rather than a LP solver.

I still question whether this is the right metric for a non-profit to be maximizing.  Instead of focusing only on "profit", I would anticipate that a non-profit would care about the benefit to stakeholders or soceity: e.g., the benefit to the children served, or the number of children served, or some combination of benefit and leftover "profit".  For instance, all else being equal, is the benefit greater if a child is cared by a single staff member rather than sharing a staff member with two other children? I suspect so, but that isn't incorporated in your "profit maximization" formulation.  Thus, I suspect the right objective function to maximize might be something different, chosen to take into account that the goal of a non-profit is not to derive a profit but to accrue some social benefit.


The closest I can think of is the MetaKlaim language. Klaim is a process calculus with asynchronous communication via tuple spaces. MetaKlaim is an extension of Klaim that integrates the meta-programming features of MetaML, namely multi-stage programming with types. (You may be more familiar with the syntax of MetaOCaml)

I am not an expert in any of these fields, so I don't really know if multi-stage programming fit in this definition of reflection. (I know this does not capture all aspects of reflection anyway so that's at most a partial answer).


Does the Bellman-Ford algorithm find all the negative cycles?

Bellman-Ford simply returns there exists at least one negative-weight cycle, it doesn't actually find all edges part of all such cycles. At best, without extending the algorithm too much, you find at most one edge per negative-weight cycle as cycles may intersect. There are ways to recover a negative weight cycle, see the link you provided, but this is outside the scope of the Bellman-Ford algorithm.

Edit: There is a subtlety that I forgot to mention, Bellman-Ford only returns the existence of a negative-weight cycle if that is cycle is reachable from the source vertex. In a disconnected graph, it may be the case that the negative-weight cycle is unreachable, so it will not be reported. Assume therefore that for every graph with a negative-weight cycle, it is reachable from the source vertex.

The proof is fairly simple. Let $v_1, v_2, \dots, v_k, v_1$ be a reachable negative weight cycle. We assume for contradiction that
$d(v_i) + w(v_i, v_{i+1}) \geq d(v_{i+1}) for all $i = 1, \dots, k$.

If we add all inequalities, we obtain

$$\sum_{i = 1}^{k} d(v_i) + \left(\sum_{i = 1}^{k - 1} w(v_i, v_{i+1}) + w(v_k, v_1)\right) \geq \sum_{i = 1}^{k} d(v_i),$$

and so $\sum_{i = 1}^{k - 1} w(v_i, v_{i+1}) + w(v_k, v_1) \geq 0$. This is a contradiction, thus it must be that there is an edge on the cycle that still can be relaxed. Note that a simple path is of at most length $|V| - 1$, and if an edge can still be relaxed after $|V| - 1$ iterations, it must be an edge of a negative-weight cycle (this is maybe a little too simplified, but the intuition is correct).


Optimal scalability of a distributed algorithm

Yes, your intuition is correct, for all the reasonable models of computation that I'm familiar with.  If it weren't, then we could take a single machine and have it simulate a cluster of n nodes, increasing the cost by only a factor of n.  So, if you had an algorithm that ran on a cluster of n nodes faster than T/n, you'd get an algorithm that runs on a single node faster than T.

Note that the single node might need to have n times as much memory as each node in the cluster.


Parallel programming models: Why do OpenMP and MPI dominate?

I will give you two main reasons why MPI and OpenMP dominate.

The first one is that they are standards. There are several available implementations, and you can be sure to find them available on every possible supercomputer machine. This is strictly related to the concept of portability: you write your parallel code and, if you do not use anything else related to a particular machine, you can run the same code on all of the parallel machines you have available.

The second reason is the programmer's resistance. With MPI and OpenMP covering both message-passing and shared-memory parallel programming (and you can even use them simultaneously if useful and/or required) why a programmer, especially a beginner in the field, should spend his/her time learning new parallel programming languages that are not granted to become standards? Sure, as you pointed out, other languages provide some benefits but the question is, would you invest your time betting on something that may even totally disappear in the future ? Standards are here to stay. Anyway, regarding this specific point, my humble opinion is that, if possible, one should instead spend some time on different languages (not just those one for parallel programming) because this is a useful discipline and learning different paradigms is always beneficial. However, when reading your curriculum vitae for possible hiring, the people that can hire you for a position will be in general mostly interested to your knowledge of the standards, not to your knowledge of niche languages (in general, even though there could be exceptions of course).


When extracting the root, the subtrees of the root remain and have to merged. Merging two leftist trees is done by "zipping" the trees along their rightmost paths. Two short paths together might be rather long. Try some examples.


In branch and bound, you prune a branch if you have an upper bound on the best solution that this branch can provide, and this upper bound is smaller than your current best solution. In your case, you have no current best solution (since you haven't considered any integer solutions), and in particular, you cannot prune any branch.


Why not polynomial-space reductions for $PSPACE$-hardness?

It's never interesting to use reductions that are as powerful as the complexity class you're talking about.  With the exception of $\emptyset$ and $\Sigma^*$, every problem in $\mathbf{PSPACE}$ is $\mathbf{PSPACE}$-complete under poly-space reductions.

To see this, let $X\in \mathbf{PSPACE}\setminus\{\emptyset,\Sigma^*\}$, and choose any fixed pair of strings strings $y\in X$ and $n\notin X$. Now, for any language $L\in\mathbf{PSPACE}$, we can reduce $L$ to $X$ using the function
$$f(w)=\begin{cases}\ y&\text{if }w\in L\\
                    \ n&\text{if }w\notin L.\end{cases}$$
Since $L\in\mathbf{PSPACE}$, we can compute $f$ in polynomial space.

This argument applies for any reasonable complexity class and it's the reason why, for example, we don't talk about problems being $\mathbf{P}$-complete under poly-time reductions: instead, we use something like log-space reductions, there.

In general, hardness or completeness results are "more impressive" using weaker reductions, since the reduction is able to do less of the work. In the case of $\mathbf{PSPACE}$-completeness under poly-space reductions, the reduction is actually doing all the work.


Proof Idea: There are irrational numbers whose decimal expansion cannot be computed

You can't even write a program that outputs one single irrational number. What you can do, is write a program which will output for example every decimal digit of some irrational number, one after the other, assuming unlimited resources and unlimited time, and which will output every single digit eventually (but will never output all digits). We count that as "outputting a number".

If you tried to write a program that first outputs all digits of π, followed by all digits of e, that wouldn't work because it never will finish outputting the digits of π. What you could do is output the first decimal of π, followed by the first decimal of e, followed by the second digits of π and e, and so on. So a program can output two (or three or four or a billion) irrational numbers, if we change the definition a bit.

You could write a program that outputs a countable infinite number of irrational numbers. Start with the first digit of the first number. Then the second digit of the first, followed by the first digit of the second number. Then the 3rd digit of the first, 2nd digit of the second, and 1st digit of the third number, and so on forever. So this program would eventually output each digit of a countable infinite number of irrational numbers.

You can't extend this to an uncountable numbers. Being uncountable, it is impossible for example to output just the first digits of all these numbers.

So the best you can do, with a modified definition of what "outputting an irrational number" means, is that you can have a countable number of programs, which each calculate a countable number of irrational numbers, but countable times countable is still countable, so you cannot output all irrational numbers.


How "add" could be implemented in only bitshift operations

This is impossible, a shift does not combine two operands.


Compound interest with varying compounding frequency

This problem is a good example of problems that can be solved by dynamic programming.

Given original principal $n$, the subproblems are, what is $p(t)$ for $0\le t\le r$, the maximum final principal that can be yielded if aggregate rate is $t$ . We have the following recurrence relation, where $//$ means the integer division, for example, $13 \operatorname{//} 5 = 2$.

$$p(t) = \max( p(0) + p(0)* t \operatorname{//} 100,\ p(1)+p(1) * (t-1) \operatorname{//} 100,\ p(2)+ p(2) * (t-2) \operatorname{//}100,\ \cdots,\ p(t-1)+ p(t-1) * 1 \operatorname{//} 100)
$$

From $p(0)=p$ you can compute $p(1)$. From $p(0)$ and $p(1)$, you can compute $p(2)$. And so on. Finally you can will get $p(r)$, which is what you want.

I will left you figure out the actual implementation. By the way, the code in question, fails when the original principal is 23 and the aggregate rate r is 9.


Doesn't a quantum algorithm being deterministic contradict the superposition principle?

If the algorithm has no error, then the system is not in a superposition when it is measured, but it is possible it was in a superposition during the computation, after which it was cleverly interfered constructively on the right answer(s) and interfered destructively on the wrong one(s).

For example, Deutsch's algorithm has this property, the way he initially introduced it: the system is put into a superposition without entanglement, then it is operated on to produce a superposition in which the two qubits are entangled, and then it is operated on some more so that the final measurement is deterministic.

One way to understand why some deterministic quantum algorithms use superposition is to see that an algorithm is a map from input vectors to output vectors. A good algorithm goes from the input vector to the output vector via the shortest path. The only steps that it can take are elementary gates (Hadamard, CNOT, X, Y, Z, etc.). Sometimes, the shortest path happens to be one in which the intermediate states are in a superposition, even if the final state is not. If this is the case, if all shortest paths involve superposition, then this problem is solvable more quickly by a quantum computer than by a classical computer, which cannot take those paths.


Is it always enough to prove that a subset $L'$ of a language $L$ is unprovable in order to prove that $L$ is undecidable?

No, your conclusion is not correct. The fact that $L'\subseteq L$ is undecidable do not imply anything about $L$. Indeed, consider $L=\Sigma^*$
for some finite alphabet $\Sigma$. Then, $L$ is decidable.

Now consider $L'\subset L$ such that $w\in L'$ iff $w$ is the description of a halting Turing machine written with characters from $\Sigma$. Then, $L'$ is, of course, undecidable.


It depends whether the automaton is deterministic or not. If it is deterministic, then the answer should be yes, just as in the case of DFAs, and you can mimic the proof for DFAs. If it is non-deterministic, then the answer should be no, just as in the case of NFAs; in fact NFAs are a special case of non-deterministic LBAs, and the NFA counterexample can be adapted to the LBA setting.

(The set of languages accepted by non-deterministic LBAs is closed under complementation, but the proof is not quite as straightforward; it is known as the Immerman--Szelepcsényi theorem.)


Double exponentials vs single exponentials

The issue comes down to ambiguous terminology.

$(a^b)^c = a^{bc}$, but $a^{(b^c)} \neq a^{bc}$. In other words, exponents aren't associative.

Conventionally, nested exponentials without parentheses are grouped in this second way, because it's more useful. So $2^{2^n} = 2^{(2^n)} \neq 2^{2n}$. If we wanted to talk about $(2^2)^n$, we could just write $2^{2n}$ instead, so we reserve the double exponential notation for the other case.


Is it 100% OK to say "All software doesn't need to know the system lower than the architecture level"?

Nothing is 100% sure in life.

Abstractions are rarely perfect; they can be leaky.  Nonetheless, just because developers at higher levels sometimes need to know about lower layers doesn't mean they always do, or usually do; and it doesn't mean the abstraction is useless.

Yes, there are cases where it is helpful to know about even lower levels of the architecture.  For instance, cold boot attacks and the row hammer attack are made possible by a property of the physics of DRAM cells, so if you want to analyze the security of a system against that specific threat model, you might need to know about things at the level of devices and physics.  These cases are the exception rather than the norm, but they do exist and are occasionally relevant.


Being stuck and frustrated with my masters project

I have been implementing a branch and bound solver with heuristics for an NP-hard problem. It got complicated at some points and had to reimplement parts a couple of times. The problem was (I think), that I started implementing with only an intuition about the design and how it looks like. That is bad software engineering and is catastrophic in big project.

So forget your computer for now. Bring a bunch of white papers and a pen. Describe the steps of the algorithm precisely. Design the program, decide the data structures and how they will communicate. Decide where data should be kept and how it should be commuted. When you have the details drawn on papers, coding is just a matter of writing it down and doing some optimization.

Another good advise is to start by writing the simplest version you can imagine. Implement only what you need to have, in the simplest way you can think of. No optimization, no copy/reference calls thinking just get it to run correctly at first. Once you are at that point you have something to deliver, start making it better. Check where you are doing stuff naively where you can do it better. Find all copies where you could have just done it on the original structure. Because if you kept optimizing and adding features while implementing you will never finish. There will always be something to add.


Machine learning approach to auction game

There probably is no solution that will be optimal for all possible situations.  So, you are left with heuristics: trying to find a technique that will often work well in the situations that arise for you in practice, but with no guarantees that it will work for everything.  Machine learning might be one possible such approach.

You might start by trying to learn the function $f$.  You said that the agent is free to invoke $f$ on any set of items.  Therefore, a possible starting point is to try to learn a model that predicts $f$: e.g., given a representation of the set $I$, outputs an estimate for $f(I)$.  You can easily collect a training set by querying $f$ on many sets and observing its output.

Reinforcement learning would be a plausible approach to the broader problem.  There are many approaches to reinforcement learning, but in one typical approach, we need to compute a function $V(a)$ that computes the anticipated value of being in state $a$ (i.e., if the agent is in state $a$ and then follows its policy/strategy, what do we expect the final value of $f(I)$ will be?).  Normally machine learning techniques are used to build a model that estimates the value of $V(a)$.  This then requires forming a representation of the state $a$, i.e., a feature vector that summarizes or extract relevant information about the current state.  The current state includes: (a) the set of items bought by this agent so far, (b) the budget and number of slots available to this agent, (c) the number and list of items remaining to be bought, and (d) information about the other agents, including what they've bought so far and the number of slots and budget remaining to them.  So, you can think about how to build a feature vector that represents them, then apply standard methods for reinforcement learning to learn the function $V(a)$.

I suggest reading a tutorial on reinforcement learning to learn more about how it works and see some examples in a simpler setting.


Using amplification lemma to decrease error probability gives 0 as divisor

If the Turing machine has an error probability of $1/2$, the Turing machine is useless and you cannot amplify to reduce the error bound.

Consider: if you just ignore the input and flip a coin and use that to decide whether to accept or reject, you get an error probability of $1/2$ -- yet that is an obviously useless procedure.  A Turing machine with an error probability of $1/2$ is no better than that.

Here's another way to see why it's hopeless.  One standard method of amplification is to run the Turing machine multiple times and take a majority vote.  Suppose we run the Turing machine 3 times, and take a majority vote.  What is the probability that the outcome of the majority vote is correct?  It's not hard to see that this probability is $1/2$ -- no better than running the machine once.  (Why?  Each time you run the Turing machine, it is either correct or incorrect.  Since you run it 8 times, there are 8 cases: CCC, CCI, CIC, CII, ICC, ICI, IIC, III, where C = correct and I = incorrect.  If the Turing machine's error probability is $1/2$, all 8 of those cases are equally likely.  The majority vote after 3 runs will be correct in the cases CCC, CCI, CIC, and ICC; thus, the majority vote is correct with probability $4/8 = 1/2$.)  The same thing happens no matter how many times you run the Turing machine.

To get amplification, you need the error probability to be strictly less than $1/2$.


Understand the DFA: accepting or not accepting "aa" or "bb"

It is not clear if you actually want to construct an automaton for some language, however I can provide some help with understanding the given ones.
The first automaton is a bit complicated.
The language it recognizes should be, in regular expression form,
$$((ab)^\ast (ba)^\ast)^\ast (a + b + \varepsilon)$$
where $\varepsilon$ denotes the empty word.
The second one, as you noted, has no edges returning to the only final state which also happens to be the initial state.
Hence the language it recognizes is $\{\varepsilon\}$, but it surely is a complicated automaton for doing this.
The third automaton recognizes the language $a(ba)^\ast$.
It does not accept any words containing substrings $aa$ or such as starting from any state, taking 2 consecutive $a$-transitions will land you in that bottom sink state from which the accepting state cannot be reached.
The fourth automaton is actually not a DFA but a NFA (but that makes no big difference).
It recognizes the language $a(baa^\ast)^\ast$, which is different from the expression you gave as yours is missing the possibility for taking the loop from the accepting state through the initial state via $b$ and back to the accepting state via $a$.
In particular, this loop shows that if the automaton accepts $w$, then it also accepts $w(ba)^\ast$.
In general, analyzing the language recognized by some DFA boils down to finding the paths from the initial state to a final state and then accounting for loops along the way, which sometimes can be a bit confusing, but try to do this for the third and fourth automata yourself. I am sure that you will be able to understand them that way in no time :)


You can't deduce that $uv = a^{k^2}$, all that the pumping lemma gives you is that $|uv| \leq m$. Not all numbers less than $m$ are squares. Not only that, but even supposing that $uv = a^{k^2}$, there is no reason to assume that $v = a^{2k-1}$; all the pumping lemma gives you is that $v$ is non-empty. Finally, in order to get a contradiction, it is not enough that $x + 2y$ need not be a square, it must not be a square! Since $x$ and $x+y$ are adjacent squares, it is actually case that $x + 2y$ is not a square.


Using pumping lemma to prove {a^ib^j | i > j} non-regular

Now if an $i$ is chosen to be 0, this would conflict with $|y|>0$?

Note it's $|y|>0$, not $|y^i|>0$, so there's no problem.

All your other confusions come from the typos in the proof. I rewrite the proof (the fixed typos are colored red) as follows.

... Clearly $w \in L_2$ and $|w| > p$, so according to the pumping lemma there exist $x, y, z \in \Sigma^∗$ such that $w = xyz,$ $ |xy| \le p,$ $ |y| >
 0$ and for all $i \ge 0$ it holds that $xy^iz \in L$. Since $|xy| \le p$, then $x = a^n, y = a^m$, and $z = a^kb^\color{red}p$ such that $m + n + k = \color{red}{p+1}$, and $m > 0$. We pump with $i = 0$ and get the word $xz = a^nz = a^na^kb^\color{red}p$. Since $m+n+k = p+1$ and $m >0$, then $n+k \color{red}{\le p}$ ...


Machines for context-free languages which gain no extra power from nondeterminism

As far as I know, we do not know whether Non- deterministic context-sensitive languages are more powerful than deterministic context-sensitive languages. And the simplest reason behind this is: Till now no-one has been able to give a language that is accepted by the non-deterministic LBA and not accepted by the deterministic LBA. So if someone can come up with one such language that is accepted by ND LBA and not accepted by deterministic LBA then only this will be proven. As we know this method of proving is called proof by contradiction.
Because proving something is TRUE is a hard problem but proving something FALSE is easy, just get one instance where it fails and we're done.


How to sample uniformly from a stream of elements, some of which are unsuited?

The easiest way to solve this problem might be to randomly permute the input. For example, you could compute a random permutation pi on N elements, and replace the main loop with

for s from 1 to N:
   t = pi[s]
   ...

Edit: If you want to solve this in an online fashion, here is a different suggestion. Consider first the case $B=1$ and a threshold $T$ that always holds. So given a sequence of elements, we want to select a uniformly random one in an online fashion. This is done by the following algorithm:

for t from 1 to N:
  x = input()
  with probability 1/t:
    selected = x
return selected

Now let's still assume that $B=1$, but let the threshold be arbitrary:

 count = 0
 for t from 1 to N:
   x = input()
   if P(x) > T:
     count = count + 1
     with probability 1/count:
       selected = x
 return selected

Now assume we have arbitrary $B \geq 1$, but all the elements cross the threshold:

for t from 1 to N:
  x = input()
  if t <= B:
    selected[t] = x
  else:
    with probability B/t:
      i = random({1,...,B})
      selected[i] = x
return selected

Finally, putting everything together:

count = 0
for t from 1 to N:
  x = input()
  if P(x) > T:
    count = count + 1
    if count <= B:
      selected[count] = x
    else:
      with probability B/count:
        i = random({1,...,B})
        selected[i] = x
return selected

Edit 2: Here is yet another suggestion, assuming that you know both $N$ and the number of elements crossing the threshold, let's say $M$. You choose a random subset $S$ of size $M$ of $\{1,\ldots,N\}$. You select the $k$th element crossing the threshold for each $k \in S$.

If you only have an estimate for $M$, you can try a similar algorithm in which you guess $M$ and hope for the best.

Here is pseudocode for the algorithm:

S = random subset of {1,...,N} of size M
count = 0
for t from 1 to N:
  x = input()
  if P(x) > T:
    count = count + 1
    if count in S:
      select x


In what sense is the Mandelbrot set "computable"?

There are several ways of defining what it means for the Mandelbrot set to be computable. One possible definition is the Blum–Shub–Smale model. In this model, real computation is modelled by a machine similar to a RAM machine, whose access to real numbers is restricted to basic arithmetic and comparisons. Blum and Smale showed that the Mandelbrot set is uncomputable in this model, though its complement can be recursively enumerated using the traditional algorithm used for drawing them.

Another model is computable analysis, in which the Mandelbrot set is probably computable, as shown by Hertling (conditional on a widely believed conjecture, the hyperbolicity conjecture). In this model, computing the Mandelbrot set means being able to compute an approximation to the Mandelbrot set, within any desired accuracy (for the exact definition, see the reference on computable analysis).

Why is it, then, that the computer seems to be able to draw the Mandelbrot set? The main difficulty in showing that the traditional algorithm works is that it is difficult to tell in advance how many iterations to run before we decide that the point belongs to the set. Hertling shows that if the widely believed hyperbolicity conjecture holds, then there is a reasonable such bound. Presumably, the programs simply wait long enough; or they don't wait long enough, but only get a small fraction of the points wrong.


Hoare triple: Loop invariant and correctness

I believe the loop invariant is the same as the postcondition, except with j and m swapped with i and n, respectively. That statement can be proven true at the start and end of each loop. This is true partially by virtue of the fact that the final implication is trivially true when n = 1 (as in the outer else condition), because no k value is in the range.

The fact that j and m are only ever assigned from i and n while the invariant is true, and the postcondition is true prior to the loop, implies that the postcondition holds.

Another key observation is that i+n < len implies i+n+1 ≤ len, so the proposed invariant holds true, even after the loop condition fails.

I hope that helps.


Can I run Dijkstra's algorithm using priority queue?

Yes, you can use priority queues to improve the complexity of the algorithm from $O(V^2)$ to $O(|E| + |V| \log|V|)$ where $E$ is the number of edges and $V$ is the number of nodes.

You should consider carefully the number of nodes in your graph and the desired run time before adding complexity to your implementation.

See here for a brief explanation of performance vs difficulty trade offs.

To summarize the blog, using a regular queue can still speed up Dijkstra's algorithm by up to a factor of 4 in most cases, with rarely occurring graphs running in $O(V^3)$. The link says "never" occurring, but that would depend on the actual problem you are solving.

See this for the original research on using min-priority queues to speed up Dijkstra's algorithm, it is the fastest known implementation for Dijkstra's algorithm.


Cycle of length k with no repeated edges

This problem is NP-Complete.

The $\in NP$ part is simple - guess a trail and check it.

The hardness part comes from the fact Hamiltonicity on a cubic graph is hard, as proved in Garey and Johnson book.

(In a cubic graph, every vertex-simple path walk is edge-simple, as it can not visit a vertex more than once, except maybe the start and end vertex).


There are online lecture notes which give algorithms for getting rid of $\epsilon$ productions ($\epsilon$ is another name for $\Lambda$) and for converting arbitrary grammars into Chomsky normal form. Both are reasonably simple. There is also an algorithm for converting a context-free grammar to a non-deterministic PDA, but if I remember correctly you first have to convert your grammar to Greibach normal form, so it might be better to understand what the language is and come up with a PDA for it directly.

Since you're taking this course online, I think it will be advantageous for you to find useful lecture notes online yourself, as part of your general education. Finding stuff over the internet is extremely useful, and if that's the only thing you get out of this course, you've already benefitted a lot.

I can illustrate the algorithms by solving some of your examples. In order to eliminate $\epsilon$-productions from your (i), the idea is that for every production that has $X$ in it, we create another one in which $X$ is missing. So we add productions $S \to a | b$. This works in general, but has to be applied iteratively.

In order to convert your (i) to Chomsky normal form, we only need to "rename" $S$: replace $S \to SS$ with $S \to TT$, and add $T \to TT|a$. Other cases require other operations; for example, if you had $A \to BCD$ then you would replace it with $A \to ED$ and $E \to BC$; and if you had $A \to Bc$ then you would replace it with $A \to BC$ and $C \to c$. This should be enough for you to work out the other parts of this question.


What programming language should I use to run physics simulations of CO2 being absorbed by different materials?

That depends on a lot of factors, mostly on available software for the task (you don't want to do the whole job yourself, if it is already done, or there are pieces you can combine with little effort, use that), in second line on how detailed your model (and it's computing requirements) is might force the use of inconvenient but efficient languages/packages.
This is probably a question better asked elsewhere, perhaps on a physics or chemistry forum (for the modelling aspects, and possibly for software alternatives in common use), or (given much more detailed requirements and specifications) on a forum on programming.